K-means算法

k-means算法属于无监督学习，没有已知的标签

k均值是发现给定数据集的K个簇的算法。

每个簇通过其质心来描述。

k均值算法的工作流程如下，

首先，给定随机的K个初始质心，然后将数据集中的每个点分配到一个簇中，过程是为每个点寻找最近的质心，并将其分配给该质心所对应的簇；

然后为每个簇更新质心，质心为所有点的平均值。

其伪代码如下：

创建k个点作为初始质心

当任意一个点的簇分配结果发生改变时

　　对数据集中的每个点

　　　　对每个质心　　

　　　　　　计算质心和该点的距离

　　　　将该点分配到最近质心的簇

　　对每一个簇，计算均值，更新质心。

重点是：1.随机　　2.按距分配　　3.均值更新

随机性往往使结果并不好，所以产生了后处理以及新的变形二分k-均值算法。

后处理

设置一个判断簇的好坏的标准，使用SSE（误差平方和）来判断。

后处理可以采用，将具有最大SSE的簇划分成两个簇，在这个大簇中采用k-均值；然后再把某两个簇合并，保持总数不变。合并的依据是，合并最近的质心或者合并两个使得SSE增幅最小的质心。

二分K均值算法

该算法首先将所有点作为一个簇，然后将该簇再一分为二，之后选择其中一个再进行划分，选择的依据是划分之后是否可以最大程度降低SSE的值。

这种基于SSE的划分过程不断重复，直到符合用户的簇数目。

伪代码如下：

一个整簇

当簇数目小于K时

　　对每个簇

　　　　计算总误差

　　　　在给定簇上进行K均值聚类（K=2）

　　　　计算划分后的总误差

　　选择误差小的那个簇进行划分

下面是一个简单的Kmeans的代码例子：　

 1 #coding=utf-8
 2 from numpy import *
 3 
 4 def loadDataSet(fileName):
 5     dataMat = []
 6     fr = open(fileName)
 7     for line in fr.readlines():
 8         curLine = line.strip().split('	')
 9         fltLine = map(float, curLine)
10         dataMat.append(fltLine)
11     return dataMat
12     
13 #计算两个向量的距离，用的是欧几里得距离
14 def distEclud(vecA, vecB):
15     return sqrt(sum(power(vecA - vecB, 2)))
16 
17 #随机生成初始的质心（ng的课说的初始方式是随机选K个点）    
18 def randCent(dataSet, k):
19     n = shape(dataSet)[1]
20     centroids = mat(zeros((k,n)))
21     for j in range(n):
22         minJ = min(dataSet[:,j])
23         rangeJ = float(max(array(dataSet)[:,j]) - minJ)
24         centroids[:,j] = minJ + rangeJ * random.rand(k,1)
25     return centroids
26     
27 def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
28     m = shape(dataSet)[0]
29     clusterAssment = mat(zeros((m,2)))#create mat to assign data points 
30                                       #to a centroid, also holds SE of each point
31     centroids = createCent(dataSet, k)
32     clusterChanged = True
33     while clusterChanged:
34         clusterChanged = False
35         for i in range(m):#for each data point assign it to the closest centroid
36             minDist = inf
37             minIndex = -1
38             for j in range(k):
39                 distJI = distMeas(centroids[j,:],dataSet[i,:])
40                 if distJI < minDist:
41                     minDist = distJI; minIndex = j
42             if clusterAssment[i,0] != minIndex: 
43                 clusterChanged = True
44             clusterAssment[i,:] = minIndex,minDist**2
45         print centroids
46         for cent in range(k):#recalculate centroids
47             ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster
48             centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean 
49     return centroids, clusterAssment
50     
51 def show(dataSet, k, centroids, clusterAssment):
52     from matplotlib import pyplot as plt  
53     numSamples, dim = dataSet.shape  
54     mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']  
55     for i in xrange(numSamples):  
56         markIndex = int(clusterAssment[i, 0])  
57         plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])  
58     mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']  
59     for i in range(k):  
60         plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)  
61     plt.show()
62       
63 def main():
64     dataMat = mat(loadDataSet('testSet.txt'))
65     myCentroids, clustAssing= kMeans(dataMat,4)
66     print myCentroids
67     show(dataMat, 4, myCentroids, clustAssing)  
68     
69     
70 if __name__ == '__main__':
71     main()