MachineLearning-Kmeans

标签： MachineLearning 数据挖掘

---

算法概述

  K-均值聚类（K-means）算法属于无监督学习中的聚类算法。其优势在一般情况下算法收敛，并且容易实现；但是也有一定的可能性收敛到局部的最小值，并且其在较大规模的数据集上收敛较慢。

算法思路

  K-means算法的思路较为简单：首先随机确定k个初始点作为质心（k为需要聚类的簇个数)，然后根据样本点到初始点的距离不断的更新质心的位置，直到质心的位置收敛，然后为每个样本点找到距离最近的质心作为其分类的标准。
  算法如下：
   1.随机初始化聚类中心sigma_1…sigma_k
   2.重复下列迭代过程，直到收敛：
    （1）对于每个i：
               
    （2）对于每个j：
                 
  上述算法的迭代过程中，循环体内实现两个步骤：第一步是将每个样本点分配给距离最近的质心；第二步是将每个质心更新到已分配的点中的均值的位置。
  对于算法的收敛性，利用失真函数作为检测标准：
                 
  可以发现，K-means是对于J的下降过程。

算法实现

  本文中K-means，实现的参考《MachineLearnigninAction》。
  算法实现函数如下：

def kmeans(dataSet,k,distMeas=distEclud,creatCent=randCent):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    centroids = creatCent(dataSet,k)
    clusterChanged = True
    count = 0
    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
        count = count +1
        print count
        print centroids
        for cent in range(k):
            ptsInclust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]
            centroids[cent,:] = mean(ptsInclust,axis=0)
    return centroids,clusterAssment

  测试结果如下：

  其中红色点为迭代之后的质心。

算法拓展

  为了克服K-均值算法收敛于局部最小值的问题，可以使用“二分K-均值”算法。该算法的思路是：首先将所有的点作为一个簇，然后将该簇划分为二，之后选择其中一个簇继续划分，选择哪一个簇进行划分取决于对其划分知否可以最大程度减低误差平方和。上述基于误差平法和的划分过程不断重复直到指定的簇数为止。
  一般而言二分K-均值效果好于K均值算法，具体的介绍可以参考《MachineLearnigninAction》一书。