《机器学习实战》6：K-均值聚类

有两个月的时间没有更新博客了。最近很忙，中断了机器学习的学习。这两天又把这本书拿出来接着看，SVM还是没有看明白，索性就看了个简单的K-均值聚类。

1、聚类定义：聚类是一种无监督学习(也就是在聚类结果出来之前我们不知道每个簇是什么)，它将相似的对象归为一类，和我们常说的“人以群分，物以类聚”是相似的。

在学习K个好邻居的时候说过数据挖掘的流程，这里再次回忆一下：

2、开发机器学习应用程序的步骤 
(1)收集数据：收集各种样本数据，为了节省时间，可以使用公开的可用数据源 
(2)准备输入数据：确保数据格式符合要求，本书采用的格式是Python语言的List。 
(3)数据分析：人工分析以前得到的数据，确保数据集中没有垃圾数据。 
(4)训练算法，这一步才是机器学习真正的开始，对于监督学习，我们把之前的格式化数据输入到算法中，得到分类模型，方便后续处理。对于无监督学习，不存在目标变量，因此也不需要训练算法!!!
(5)测试算法：这一步使用第4步机器学习的模型。这一步主要测试算法的工作效率。 
(6)使用算法：将机器学习算法转换为应用程序，执行实际任务。 

3、K-均值聚类

首先，随机确定k个初始点作为质心。然后为每个点找距离其最近的质心，将其分配到该质心所对应的簇中。完成这一步之后，更新每个簇的质心为该簇所有点的平均值。迭代以上过程，直到簇分配结果不再改变，完成K-均值聚类。

 伪代码：很重要！！！代表着算法的逻辑

 

随机创建K个质心为起始点
当任意一个点的簇分配结果发生变化时
    对每一个数据点
         对每个质心
              计算数据点和之心之间的距离
         将数据点分配到距离最近的簇中
    对每个簇，计算所有点的均值更新质心

 4、算法的实现

 

（1）创建文件kMeans.py,编写k-均值算法需要用到的通用函数，代码如下：

from numpy import *

#加载数据集
def loadDataSet(fileName):
    dataMat=[]
    fr=open(fileName)
    for line in fr.readlines():
        curLine=line.strip().split('\t')
        #map函数的主要功能是
        #对一个序列对象中的每一个元素应用被传入的函数，并且返回一个包含了所有函数调用结果的一个列表
        #这里从文件中读取的信息是字符型，通过map函数将其强制转化为浮点型
        frtLine=map(float,curLine)
        dataMat.append(frtLine)
    return dataMat

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

#随机构建初始质心
def randCent(dataSet,k):
    #数据列数
    n=shape(dataSet)[1]
    #初始化质心
    centroids=mat(zero(k,n))
    for j in range(n):
        #求每一维数据的最大值和最小值，保证随机选取的质心在边界之内
        minJ=min(dataSet[:,j])
        maxJ=max(dataSet[:,j])
        rangeJ=float(maxJ-minJ)
        centroids[:,j]=minJ+rangeJ*random.rand(k,1)
    return centroids

对上面的随机选点函数进行测试：

 

 

有了以上的通用函数，我们就可以实现k-均值算法了，具体的算法如下：

 

#kMeans算法
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

 

 

测试结果如下：

 

 

经过三次迭代，找到了4个合适的质心。

 

这样我们就完成了k-均值算法的实现，那么我们如何知道我们生成的簇结果是比较好的呢？我们通过点到簇新的平方和来估计结果的好坏，即通过误差平方和SSE（Sum of SquaredError）来度量。由于sse并不是一个凸函数，我们使用K-means算法有些情况下得到的局部最小值，并不是最有的聚类结果。为了改善这种局部最优的缺点，可以通过多次执行k-means算法，找到使得SSE最小的聚类。另一种方法就是有人提出了二分k-均值算法。

5、二分K-均值

 该算法首先将所有的点当成一个簇，然后将该簇一分为二。之后选择其中一个簇进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。不断重复该过程，直到达到用户所需要的簇个数为止。

将所有的点看成一个簇
当簇数目小于k时
   对每一个簇
        计算总误差
        在给定的簇上面进行二分k-均值聚类
        计算一分为二之后的总误差
    选择使得误差最小的那个簇进行划分

 编写代码如下：

def biKmeans(dataSet,k,distMeas=distEclud):
    m=shape(dataSet)[0]
    clusterAssment=mat(zeros((m,2)))
    #创建一个初始簇
    centroid0=mean(dataSet,axis=0).tolist()[0]
    centList=[centroid0]
    #计算初始误差
    for j in range(m):
        clusterAssment[j,1]=distMeas(mat(centroid0),dataSet[j,:])**2
    while(len(centList)<k):
        lowestSSE=inf
        #遍历每个簇,尝试划分每个簇
        for i in range(len(centList)):
            ptsInCurrCluster=\
                dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]
            centroidMat,splitClustAss=\
                kMeans(ptsInCurrCluster,2,distMeas)
            #划分后的误差平方和
            sseSplit=sum(splitClustAss[:,1])
            #剩余的误差之和
            sseNotSplit=\
                sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])
            print "ssesplit,sseNotSplit",sseSplit,sseNotSplit
            if(sseSplit+sseNotSplit)<lowestSSE:
                bestCentToSplit=i
                bestNewCents=centroidMat
                bestClustAss=splitClustAss.copy()
                lowestSSE=sseSplit+sseNotSplit
        #更新分配结果
        bestClustAss[nonzero(bestClustAss[:,0].A==1)[0],0]=\
                    len(centList)
        bestClustAss[nonzero(bestClustAss[:,0].A==0)[0],0]=\
                    bestCentToSplit
        print "the bestCentToSplit is:",bestCentToSplit
        print "the len of bestClustAss is:",len(bestClustAss)
        centList[bestCentToSplit]=bestNewCents[0,:]
        centList.append(bestNewCents[1,:])
        clusterAssment[nonzero(clusterAssment[:,0].A==\
                               bestCentToSplit)[0],:]=bestClustAss
        print centList
    return mat(centList),clusterAssment