k-中心点 基于代表的划分
概述
算法
整体算法
损失计算
优化
优点
缺点
讨论
实现

概述
在 k-means, 我们使用了基于形心(簇均值)来对数据进行划分, 也讨论了 k-means 的初始值选取之重要, 若选得不好, 很容易陷入局部最优解的问题.

实质上来说, 我们会陷入到局部最优解的本质原因是:

当初始值选定之后, 我们有一个初始的簇
均值基本是在这个簇的最大值与最小值之间
每次更新的新的质心(均值)之后, 我们的簇只会有很小的移动, 因为均值无法跳出初始簇的范围

就像, 你已经给定了初始的形状, 而我们只是在这个初始形状上进行增减, 自然很难得到全局的最好的簇了
算法
下面给出 k-中心点的主要算法, 可以与 k-means 做比较
整体算法


初始化选择 k 个质心 (随机选择, 或者领域知识选择), 该选择决定了聚类的速度与效果
为所有点划分簇
计算该种划分的损失
当该损失还能减小时循环以下:

对于每个质心(k个)执行:

a. 随机选择一个新的点

b. 以新的点代替这个质心

c. 重新对所有数据划分簇

d. 计算划分的损失

e. 若 新的损失小于原先的损失, 则 用新的点代替原质心


损失计算

一种简单的方法是每个簇离质心方差的和

$\sum_{i=1}^{k}\sqrt{\sum_{j}^{n}(d_j - d_k)^2}$

优化


原始算法被称为 PAＭ 算法, 特点在于c, d步, 这里对所有数据进行了重新计算损失, 所以只能用于小型数据集.
优化方法是 CLARA算法, 该算法将c,d步改为对抽样数据计算损失, 减少了计算量, 但是, 若在抽样时正好丢失了 最好的 质心, 那么, 将永远无法找到最佳聚类!


优点

跳出均值的局部最优
不容易受离群点与噪声的影响

缺点

时间复杂度高

讨论

可以看到, 这个算法每次代表的选取是从整个数据集随机选取, 因此跳出了初始簇的范围, 使得算法有很大的概率跳出局部最优解, 从而在迭代种得到全局最优解
损失函数的选择对效率与结果很重要, 可以尝试其他的损失函数选择

实现

蓝桥杯算法合集： 蓝桥杯算法合集（终极完结版）
贪心算法：
思想

每一步都采取当前状态下的最优选择 从而希望推出全局最优解
缺点：

用贪心策略求得的不一定是全局最优解。比如换零钱那道题，若换成 25 20 5 1四种面值 按照该算法结果应为 面值25 5 5 5 1一共需要5张，显然不对 。正确结果应该为20 20 1只需要3张即可 。

因为没有遍历全部可能性解，只是当前这一步可以达到的局部最优解，过早做出决定 ，贪图眼前局部利益的最大化 。没有放眼长远未来而是走一步看一步，所以通常作为辅助策略来使用
小知识点：

子序列可以不连续 但是相对位置不改变

子串、子数组、子区间必须连续

下面两个知识点是在01背包问题时用上的

Article类的数组

Article [] articles=new Article[] {
				new Article(35,10),new Article(30,40),
				new Article(60,30),new Article(50,50),
				new Article(40,35),new Article(10,40),
				new Article(25,30)
		};


对article数组按cmp迭代器排序

Comparator<Article> cmp=(Article a1,Article a2)->{return Double.compare(a2.valueOfDensity,a1.valueOfDensity);}
Arrays.sort(articles, cmp);

最优装载问题
问题描述
在北美洲东南部，有一片神秘的海域，那里碧海 蓝天、阳光明媚，这正是传说中海盗最活跃的加勒比海。17 世纪时，这里更是欧洲大陆 的商旅舰队到达美洲的必经之地，所以当时的海盗活 动非常猖獗。有一天，海盗们截获了一艘装满各种各样古董的 货船，每一件古董都价值连城，一旦打碎就失去了它 的价值。
虽然海盗船足够大，但载重量为 30，每件古董的重量分别为 3,5,4,10,7,14,2,11，
海盗们该如何把尽可能多数量的宝贝装上海盗船呢？

package 贪心;
import java.util.Arrays;
public class 最优装载问题 {

	public static void main(String[] args) {
		Integer[] weights= {3,5,4,10,7,14,2,11};
		//从小到大排2 3 4 5 7 10 11 14
		Arrays.sort(weights);
//		for(int i=0;i<weights.length;i++)
//			System.out.println(weights[i]);
		int capacity=30,count=0,newWeight=0;
		//当前所选古董的总重量比船容量小才进入选古董 否则提前跳出外循环
		for(int i=0;i<weights.length&&newWeight<capacity;i++) {
			//尝试将古董装上船
			newWeight=newWeight+weights[i];
			if(newWeight<=capacity) {//满足船的容量则正真装上 计数器加1
				count++;
				System.out.println(weights[i]);
			}
		}
		System.out.println(count);
	}

}

零钱兑换
问题描述
假设有25分、10分、5分、1分的硬币，
先要发给客户41分的零钱，如何办到硬币个数最少？

package 贪心;
import java.util.Arrays;

//用贪心策略求得的不一定是全局最优解  
//此题若换成 25 20 5 1四种面值 按照该算法结果应为 面值25 5 5 5 1一共需要5张
//显然不对 正确结果应该为20 20 1只需要3张即可
//因为没有遍历全部可能性解 只是当前这一步可以达到的局部最优解 过早做出决定 
//贪图眼前局部利益的最大化 没有放眼长远未来 走一步看一步 
//通常作为辅助策略来使用
public class 零钱兑换 {
	static void moneyChange(Integer[] a,int money) {
		Arrays.sort(a,(Integer a1,Integer a2)->{return a2-a1;});
		//25 10 5 1 		41
		int i=0;
		while(i<a.length) {
				if(money<a[i]) {//当剩余的钱小于该面值时 i++跳过该面值
					i++;
					continue;
				}
				//能执行到这里说明当前剩余的前大于该面值却比上一次面值小 该面值为当前最适
				money-=a[i];
				System.out.println(a[i]);
		}
	}
		static void moneyChange2(Integer[] a,int money) {
			//从小往大排：1 5 10 25
			Arrays.sort(a);
			int count=0;
			for(int i=a.length-1;i>=0;i--) {
				if(money<a[i]) {//当所有面值都比剩余的钱大时 结束循环
					continue;
				}
				money-=a[i];
				System.out.println(a[i]);
				count++;
				//选了最大面值之后 还要从最大开开始重新枚举
				i=a.length;
			}
			System.out.println(count);
		
			
		
	}
	public static void main(String[] args) {
		Integer[] faces= {5,10,25,1};
		
		//或者Arrays.sort(faces,(Integer a1,Integer a2)-> a2-a1);
		int money=41;
		//moneyChange(faces,money);
		moneyChange2(faces,money);
		
	}

}

01背包问题
问题描述：
有n件物品，每个物品都有一个大小和价值，给你一个固定容量的背包，要求装的东西价值总和最大
 实例：
 现在有重量分别为35 30 60 50 40 10 25，价值分别为10 40 30 50 35 40 30的物品，
 背包最大承重为150，求该背包所能放置的物品最大价值是多少？

package 贪心;

public class Article {
	public int weight,value;
	public double valueOfDensity;
	Article(int weight,int value){
		this.weight=weight;
		this.value=value;
		this.valueOfDensity=value*1.0/weight;
	}
	@Override
	public String toString() {
		return "Article [weight=" + weight + ", value=" + value + ", valueOfDensity=" + valueOfDensity + "]";
	}
}


package 贪心;


import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class _01背包问题 {
	//传一个比较器Comparator<Article> cmp 按设定关键字排序
	static void select(String title,Comparator<Article> cmp) {
		//将物品变量直接封装在成员方法里作为局部变量 就可以不用通过mian方法传参了
		Article [] articles=new Article[] {
				new Article(35,10),new Article(30,40),
				new Article(60,30),new Article(50,50),
				new Article(40,35),new Article(10,40),
				new Article(25,30)
		};
		Arrays.sort(articles, cmp);
		//将Article类封装到list存储结构
		List<Article> selectedArticles=new LinkedList<>();
		int capacity=150,weight=0,value=0;
		for(int i=0;i<articles.length&&weight<capacity;i++) {
			int newWeight=weight+articles[i].weight;
			if(newWeight<=capacity) {
				weight=newWeight;
				value+=articles[i].value;
				selectedArticles.add(articles[i]);
			}
		}
		for(int i=0;i<selectedArticles.size();i++) {
			System.out.println(selectedArticles.get(i));
		}
		System.out.println(weight);
		System.out.println(value);
		
	}
	public static void main(String[] args) {
		//价值主导
		select("价值主导",(Article a1,Article a2)->{	
			return a2.value-a1.value;
		});
		//重量主导
		select("重量主导",(Article a1,Article a2)->{	
					return a1.weight-a2.weight;
				});
		//价值主导
		//a2.valueOfDensity-a1.valueOfDensity;结果为double型 而迭代器要求返回类型为int
		//Double.compare(double d1,doouble d2)返回int型
		select("价值密度主导",(Article a1,Article a2)->{	
					return Double.compare(a2.valueOfDensity, a1.valueOfDensity);
				});
		
	}

}

使用贪心算法由于其目光短浅，算出来不一定正确，01背包这题用动态规划解，详见：动态规划常见模型之背包专题

---KMEANS的优缺点  密度等的脚本--

优点

k-平均算法是解决聚类问题的一种经典算法，算法简单、快速。
	
对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O（nkt），其中n是所有对象的数目，k是簇的数目，t是迭代的次数。通常k<<n。这个算法经常以局部最优结束。
	
算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果很好。
缺点

K 是事先给定的，这个 K 值的选定是非常难以估计的；
	
对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。一旦初始值选择的不好，可能无法得到有效的聚类结果；
	
该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。
	
不适合于发现非凸面形状的簇，或者大小差别很大的簇；
	
对于”噪声”和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。
	
# -*- coding:utf8 -*-
import numpy as np
import pylab as pl
import pandas as pd
import pymysql
import scipy
from sklearn.model_selection import train_test_split#以前的cross validation已停用
from sklearn.ensemble import RandomForestClassifier
from sklearn import tree#简单决策树
from sklearn.tree import DecisionTreeClassifier
from sklearn.cluster import KMeans
from sklearn.cluster import DBSCAN
from sklearn.externals import joblib


	dbconn = pymysql.connect(

	        host="127.0.0.1",

	        database="test",

	        user="root",

	        password="111111",

	        port=3306,

	        charset='utf8')

	sqlcmd = "select * from forkmeans"

	data = pd.DataFrame(pd.read_sql(sqlcmd, dbconn))
#print data.shape

	x = data.iloc[:,1:5]#前27个字段是特征字段


	clf = KMeans(n_clusters=8,init='k-means++',max_iter=300,tol=0.0001,algorithm='full',random_state=1,verbose=0)
#algorithm可以选EMS算法，就是full算法，还可以auto，还可以elkan三角变化

	clf = clf.fit(x)
print clf.labels_#给出类
[0 0 0 ... 0 0 0]

	r1 = pd.Series(clf.labels_).value_counts()#各个类的样本数目
r2 = pd.DataFrame(clf.cluster_centers_)#聚类中心点的向量

	r = pd.concat([r2,r1],axis=1)#横向连接起来
print  r
          0             1             2          3     0

0  1.140934     58.339642     18.140445   3.115462  2988

1  0.310000    999.000000  60493.550000   1.620000     1

2  0.645000    999.000000  22994.925000  36.545000     2

3  1.109350    984.150956     43.940707   9.491262   523

4  1.310000  11088.000000     11.620000   3.130000     1

5  1.150000    999.000000  13043.750000  10.160000     1

6  1.156250    783.610000   2241.325000   8.651250     8

7  0.897273   2698.112727     37.353636  16.827273    11

 

 

e = pd.concat([data,pd.Series(clf.labels_, index= data.index)], axis=1)
#每个样本对应的类别
e.columns = list(data.columns)+[u'聚类类别']#重命名表头

print e.head(3)


et = e.loc[(e[u'聚类类别'] == 3) , [u'贝塔系数',u'市盈(动)',u'市销率',u'市净率',u'资产负债率']]

print et.head(3)
#概率密度图
def density_plot(data): #自定义作图函数

  import matplotlib.pyplot as plt

  plt.rcParams['font.sans-serif'] = ['SimHei'] #用来正常显示中文标签

  plt.rcParams['axes.unicode_minus'] = False #用来正常显示负号

  p = data.plot(kind='kde', linewidth = 2, subplots = True, sharex = False)
  [p[i].set_ylabel(u'密度') for i in range(k)]

  plt.legend()

  return plt.show()


density_plot(et)#按条件提取，来绘制密度图

更多代码请见：https://github.com/xubo245/SparkLearning 

Spark中组件Mllib的学习之回归分析篇 

1解释 

SGD(Stochastic Gradient Descent-随机梯度下降) 



  sgd解决了梯度下降的两个问题： 收敛速度慢和陷入局部最优。 

  具体的介绍请见【4】、【5】和【6】

背景： 

梯度下降法的缺点是： 

靠近极小值时速度减慢。 

直线搜索可能会产生一些问题。 

可能会’之字型’地下降。

随机梯度下降法stochastic gradient descent，也叫增量梯度下降
由于梯度下降法收敛速度慢，而随机梯度下降法会快很多

–根据某个单独样例的误差增量计算权值更新，得到近似的梯度下降搜索（随机取一个样例）

–可以看作为每个单独的训练样例定义不同的误差函数

–在迭代所有训练样例时，这些权值更新的序列给出了对于原来误差函数的梯度下降的一个合理近似

–通过使下降速率的值足够小，可以使随机梯度下降以任意程度接近于真实梯度下降

•标准梯度下降和随机梯度下降之间的关键区别

–标准梯度下降是在权值更新前对所有样例汇总误差，而随机梯度下降的权值是通过考查某个训练样例来更新的

–在标准梯度下降中，权值更新的每一步对多个样例求和，需要更多的计算

–标准梯度下降，由于使用真正的梯度，标准梯度下降对于每一次权值更新经常使用比随机梯度下降大的步长

–如果标准误差曲面有多个局部极小值，随机梯度下降有时可能避免陷入这些局部极小值中

2.代码：



/**
  * @author xubo
  *         ref:Spark MlLib机器学习实战
  *         more code:https://github.com/xubo245/SparkLearning
  *         more blog:http://blog.csdn.net/xubo245
  */
package org.apache.spark.mllib.learning.regression

import org.apache.spark.{SparkConf, SparkContext}

import scala.collection.mutable.HashMap

/**
  * Created by xubo on 2016/5/23.
  */
object SGDLearning {
  val data = HashMap[Int, Int]()

  //创建数据集
  def getData(): HashMap[Int, Int] = {
    //生成数据集内容
    for (i <- 1 to 50) {
      //创建50个数据
      data += (i -> (20 * i)) //写入公式y=2x
    }
    data //返回数据集
  }

  var θ: Double = 0
  //第一步假设θ为0
  var α: Double = 0.1 //设置步进系数

  def sgd(x: Double, y: Double) = {
    //设置迭代公式
    θ = θ - α * ((θ * x) - y) //迭代公式
  }

  def main(args: Array[String]) {
    val dataSource = getData() //获取数据集
    println("data:")
    dataSource.foreach(each => print(each + " "))
    println("\nresult:")
    var num = 1;
    dataSource.foreach(myMap => {
      //开始迭代
      println(num + ":" + θ+" ("+myMap._1+","+myMap._2+")")
      sgd(myMap._1, myMap._2) //输入数据
      num = num + 1;
    })
    println("最终结果θ值为 " + θ) //显示结果
  }
}


3.结果：



data:
(23,460) (50,1000) (32,640) (41,820) (17,340) (8,160) (35,700) (44,880) (26,520) (11,220) (29,580) (38,760) (47,940) (20,400) (2,40) (5,100) (14,280) (46,920) (40,800) (49,980) (4,80) (13,260) (22,440) (31,620) (16,320) (7,140) (43,860) (25,500) (34,680) (10,200) (37,740) (1,20) (19,380) (28,560) (45,900) (27,540) (36,720) (18,360) (9,180) (21,420) (48,960) (3,60) (12,240) (30,600) (39,780) (15,300) (42,840) (24,480) (6,120) (33,660) 
result:
1:0.0 (23,460)
2:46.0 (50,1000)
3:-84.0 (32,640)
4:248.8 (41,820)
5:-689.2800000000002 (17,340)
6:516.4960000000003 (8,160)
7:119.29920000000004 (35,700)
8:-228.24800000000016 (44,880)
9:864.0432000000006 (26,520)
10:-1330.469120000001 (11,220)
11:155.04691200000025 (29,580)
12:-236.58913280000047 (38,760)
13:738.4495718400013 (47,940)
14:-2638.263415808005 (20,400)
15:2678.263415808006 (2,40)
16:2146.610732646405 (5,100)
17:1083.3053663232024 (14,280)
18:-405.3221465292811 (46,920)
19:1551.159727505412 (40,800)
20:-4573.4791825162365 (49,980)
21:17934.568811813326 (4,80)
22:10768.741287087996 (13,260)
23:-3204.6223861264007 (22,440)
24:3889.546863351681 (31,620)
25:-8106.04841303853 (16,320)
26:4895.6290478231185 (7,140)
27:1482.6887143469353 (43,860)
28:-4806.872757344887 (25,500)
29:7260.309136017331 (34,680)
30:-17356.741926441595 (10,200)
31:20.0 (37,740)
32:20.0 (1,20)
33:20.0 (19,380)
34:20.0 (28,560)
35:20.0 (45,900)
36:20.0 (27,540)
37:20.0 (36,720)
38:20.0 (18,360)
39:20.0 (9,180)
40:20.0 (21,420)
41:20.0 (48,960)
42:20.0 (3,60)
43:20.0 (12,240)
44:20.0 (30,600)
45:20.0 (39,780)
46:20.0 (15,300)
47:20.0 (42,840)
48:20.0 (24,480)
49:20.0 (6,120)
50:20.0 (33,660)
最终结果θ值为 20.0

分析： 

当α为0.1的时候，一般30次计算就计算出来了；如果是0.5，一般15次计算就有正确结果 。如果是1，则50次都没有结果

参考 

【1】http://spark.apache.org/docs/1.5.2/mllib-guide.html  

【2】http://spark.apache.org/docs/1.5.2/programming-guide.html 

【3】https://github.com/xubo245/SparkLearning 

【4】Spark MlLib机器学习实战 

【5】http://blog.csdn.net/zbc1090549839/article/details/38149561 

【6】http://blog.csdn.net/woxincd/article/details/7040944