聚类和分类

机器学习中，有聚类和分类两种问题，前面的两篇相关博文介绍了最简单的分类算法KNN算法，今天我们来谈谈最简单的聚类算法K-means算法。

什么是分类

就像前面介绍KNN时那样，分类是在一群已经知道类别标号的样本中，训练一种分类器，让其能够对某种未知的样本进行分类。这属于监督学习（supervised learning）。

什么是聚类

区别于分类，聚类是在一群未知类别标号的样本上，用某种算法将它们分成若干类别。这是一种非监督学习（unsupervisedlearning）。考虑到，第一次接触聚类，所以也选取最简单的聚类算法k-means算法来介绍。

两者的区别

最大的区别莫过于，分类的目标事先标明，而聚类则没有标明。

k-means算法

算法引入（背景）

在2000年和2004年美国总统大选中，候选人的得票非常接近，候选人的得票率最高才50.7%，最低的为47.9%，如果1%的选民将手中的选票投给另外的候选人，那么选举的结果就会完全不同，世界的格局也会有不小的变化。如何找到这1%的选民？答案就是聚类（Clustering）

k-means算法的基本思想

基本思想是：通过迭代寻找k个聚类的一种划分方案，使得这k个聚类的均值来代表各自样本时所得的误差最小。

其代价函数定义为：

μc(i)表示第i个聚类的均值。

好了，接下来就应该到如何去通过迭代得到结果的步骤了。

k-means算法的步骤

和kNN一样，作为适用领域最简单的聚类方法，其步骤非常容易想到。

这里用伪代码表示：
创建k个点作为起始质心（通常可以随机选择）

当任意一个点的簇陪陪结果发生改变时
  对数据集中的每个质点
    对每个质心
      计算质心与数据点之间的距离
    将数据点分配到距其最近的簇
  对每一个簇，计算簇中所有点的均值并将均值作为质心

上面的步骤里，提到了最近，意味着要进行某种距离的计算，通常我们选取的是欧几里得距离，当然，我们也可以自行选择其他距离。

算法的python实现

前期准备部分

在实现k-means算法之前，我们需要先做好三件事，以便我们focus on k-means算法本身：

从文件中读取数据
计算欧式距离
构建一个包含k个随机质心的集合

    from numpy import *
    from numpy.random.mtrand import power

    def loadDataSet(fileName): #文件的导入
        dataMat=[]
        fr=open(fileName)
        for line in fr.readlines():
            curLine=line.strip().split('\t')
            fltLine=map(float,curLine)
            dataMat.append(fltLine)
        return dataMat
    
    def distEclud(vecA,vecB):   #计算欧式距离
        return sqrt(sum((vecA-vecB) ** 2))
    
    def randCent(dataSet,k): #构建一个包含k个随机质心的集合
        n=shape(dataSet)[1]
        centroids = mat(zeros((k,n)))
        for j in range(n):
            minJ=min(dataSet[:,j])
            rangeJ=float(max(dataSet[:,j])-minJ)
            centroids[:,j]=minJ+rangeJ*random.rand(k,1)
        return centroids
````     
  
### k-means算法部分

def kMeans(dataSet, k ,distMeas = distEclud, createCent=randCent):
    m=shape(dataSet)[0]
    clusterAssment=mat(zeros((m,2)))
    centroids=createCent(dataSet,k)
    clusterChanged=True
    while clusterChanged:
        clusterChanged=False
        for i in range(m):
            minDist = inf ; minIndex=-1
            for j in range(k):
                distJI=distMeas(centroids[j,:],dataSet[i,:])
                if distJI<minDist:
                    minDist=distJI
                    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]]
            centroids[cent,:]=mean(ptsInClust,axis=0)
    return centroids,clusterAssment

该函数接受四个参数，其中，计算距离参数和随机产生质心的参数默认情况下为上面实现的欧式距离和randCent函数。python语言并不是本文介绍的重点，语法部分就不多提了。

函数一开始确定了数据集中数据点的总数，也就是m个。然后创建一个矩阵来存储每个点的簇分配结果，即clusterAssment，它包含两列，一列记录**簇索引值**，另一列记录**误差**（到当前质心的距离）。

按照上面的方式反复迭代，直到所有数据点的簇都不再发生变化为止。

### 主函数调用

主函数调用

from numpy import mat
import kmeans

__author__ = 'Chih-Hao'
dataMat=mat(kmeans.loadDataSet('testSet.txt'))
myCentroids,clusterAssing=kmeans.kMeans(dataMat,4)

````

总结和后续…

运行上面的程序，会发现经过三次迭代后，算法收敛了。

关于聚类，一切进行的都挺顺利的，但事情并不总是如此，下几篇博文将写k-means算法会出现的一些问题以及解决方案。

附录：数据集

数据集比较长，放在本文最后。

1.658985    4.285136
-3.453687    3.424321
4.838138    -1.151539
-5.379713    -3.362104
0.972564    2.924086
-3.567919    1.531611
0.450614    -3.302219
-3.487105    -1.724432
2.668759    1.594842
-3.156485    3.191137
3.165506    -3.999838
-2.786837    -3.099354
4.208187    2.984927
-2.123337    2.943366
0.704199    -0.479481
-0.392370    -3.963704
2.831667    1.574018
-0.790153    3.343144
2.943496    -3.357075
-3.195883    -2.283926
2.336445    2.875106
-1.786345    2.554248
2.190101    -1.906020
-3.403367    -2.778288
1.778124    3.880832
-1.688346    2.230267
2.592976    -2.054368
-4.007257    -3.207066
2.257734    3.387564
-2.679011    0.785119
0.939512    -4.023563
-3.674424    -2.261084
2.046259    2.735279
-3.189470    1.780269
4.372646    -0.822248
-2.579316    -3.497576
1.889034    5.190400
-0.798747    2.185588
2.836520    -2.658556
-3.837877    -3.253815
2.096701    3.886007
-2.709034    2.923887
3.367037    -3.184789
-2.121479    -4.232586
2.329546    3.179764
-3.284816    3.273099
3.091414    -3.815232
-3.762093    -2.432191
3.542056    2.778832
-1.736822    4.241041
2.127073    -2.983680
-4.323818    -3.938116
3.792121    5.135768
-4.786473    3.358547
2.624081    -3.260715
-4.009299    -2.978115
2.493525    1.963710
-2.513661    2.642162
1.864375    -3.176309
-3.171184    -3.572452
2.894220    2.489128
-2.562539    2.884438
3.491078    -3.947487
-2.565729    -2.012114
3.332948    3.983102
-1.616805    3.573188
2.280615    -2.559444
-2.651229    -3.103198
2.321395    3.154987
-1.685703    2.939697
3.031012    -3.620252
-4.599622    -2.185829
4.196223    1.126677
-2.133863    3.093686
4.668892    -2.562705
-2.793241    -2.149706
2.884105    3.043438
-2.967647    2.848696
4.479332    -1.764772
-4.905566    -2.911070

转自：http://zhihaozhang.github.io/2014/11/21/K-means