《机器学习实战》kMeans算法（K均值聚类算法）

============================================================================================

《机器学习实战》系列博客是博主阅读《机器学习实战》这本书的笔记，包含对其中算法的理解和算法的Python代码实现

另外博主这里有机器学习实战这本书的所有算法源代码和算法所用到的源文件，有需要的留言

============================================================================================

Scikit-learn 实现的K-Means 算法请参考 ：点击阅读

二分K-Means算法请参考：点击阅读

        机器学习中有两类的大问题，一个是分类，一个是聚类。分类是根据一些给定的已知类别标号的样本，训练某种学习机器，使它能够对未知类别的样本进行分类。这属于supervised learning（监督学习）。而聚类指事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别，这在机器学习中被称作 unsupervised learning （无监督学习）。在本文中，我们关注其中一个比较简单的聚类算法：k-means算法。 

        k-means算法是一种很常见的聚类算法，它的基本思想是：通过迭代寻找k个聚类的一种划分方案，使得用这k个聚类的均值来代表相应各类样本时所得的总体误差最小。

其Python实现的代码如下：

#encoding:utf-8
from numpy import *

def loadDataSet(filename):
	dataMat = []          #创建元祖
	fr = open(filename)
	for line in fr.readlines():
		curLine = line.strip().split("\t")
		fltLine = map(float,curLine) #使用map函数将curLine里的数全部转换为float型
		dataMat.append(fltLine)
	return dataMat

def distEclud(vecA,vecB):          #计算两个向量的欧式距离
	return sqrt(sum(power(vecA-vecB,2)))

def randCent(dataSet,k):            #位给定数据集构建一个包含k个随机质心的集合
	n = shape(dataSet)[1]   #shape函数此时返回的是dataSet元祖的列数
	centroids = mat(zeros((k,n)))       #mat函数创建k行n列的矩阵，centroids存放簇中心
	for j in range(n):
		minJ = min(dataSet[:,j])           #第j列的最小值
		rangeJ = float(max(dataSet[:,j]) - minJ)
		centroids[:,j] = minJ + rangeJ * random.rand(k,1)  #random.rand(k,1)产生shape(k,1)的矩阵
	return centroids

def kMeans(dataSet,k,disMeas = distEclud,createCent = randCent):
	m = shape(dataSet)[0] #shape函数此时返回的是dataSet元祖的行数
	clusterAssment = mat(zeros((m,2)))      #创建一个m行2列的矩阵，第一列存放索引值，第二列存放误差，误差用来评价聚类效果
	centroids = createCent(dataSet,k)  #创建k个质心，调用createCent()函数
	clusterChanged =True #标志变量，若为true则继续迭代
	print "质心位置更新过程变化："
	while clusterChanged:
		clusterChanged = False
		for i in range(m):
			minDist = inf #inf为正无穷大
			minIndex = -1  #创建索引
			for j in range(k):
				#寻找最近的质心
				disJI = disMeas(centroids[j,:],dataSet[i,:]) #计算每个点到质心的欧氏距离
				if disJI
  
  
  					minDist = disJI
					minIndex = j
			if clusterAssment[i,0] != minIndex:
				clusterChanged = True
			clusterAssment[i,:] = minIndex,minDist**2 
			print centroids
			#更新质心的位置
			for cent in range(k):
				ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#通过数组过滤来获得给定簇的所有点
				#nonzero(a)函数返回值为元祖a的所有非零值得下标所构成的元祖
				#eg：b2 = array([[True, False, True], [True, False, False]])
				#print nonzero(b2)
				#=>(array([0, 0, 1]), array([0, 2, 0]))
				#print array(nonzero(b2))
				#=>[[0, 0, 1],[0, 2, 0]]
				centroids[cent,:] = mean(ptsInClust,axis=0)  #计算所有点的均值，选项axis=0表示沿矩阵的列方向进行均值计算
	return centroids,clusterAssment  #返回所有的类质心与点分配结果


datMat = mat(loadDataSet('data.txt'))
myCentroids,clustAssing = kMeans(datMat,2)
print "最终质心：\n",myCentroids
print "索引值和均值：\n",clustAssing

  k-means算法比较简单，但也有几个比较大的缺点：
1）k值的选择是用户指定的，不同的k得到的结果会有挺大的不同，如下图所示，左边是k=3的结果，这个就太稀疏了，蓝色的那个簇其实是可以再划分成两个簇的。而右图是k=5的结果，可以看到红色菱形和蓝色菱形这两个簇应该是可以合并成一个簇的：

2）对k个初始质心的选择比较敏感，容易陷入局部最小值。例如，我们上面的算法运行的时候，有可能会得到不同的结果，如下面这两种情况。K-means也是收敛了，只是收敛到了局部最小值：

3）存在局限性，如下面这种非球状的数据分布就搞不定了

4）数据库比较大的时候，收敛会比较慢.

  K均值聚类中簇的值k是用户预先定义的一个参数，那么用户如何才能知道k的选择是否正确？如何才能知道生成的簇比较好？在计算的过程中保留了每个点的误差，即该点到簇质心的距离平方值，下面将讨论利用该误差来评价聚类质量好坏的方法，引入度量聚类效果的指标SSE（sum of squared Error，误差平方和），SSE值越小，越接近于他们的质心，聚类效果也越好，有一种可以肯定减小SSE值得方法是增加k的数目，但这个违背了聚类的目标，聚类的目标是在保持簇数目不变的情况下提高簇的质量。

接下来要讨论的是利用簇划分技术得到更好的聚类效果——二分K-均值算法