KMeans聚类算法

1、什么是聚类

    所谓聚类就是将一组对象按照特征划分不为的小组，使得组内的差异性尽可能的小，组间的差异尽可能的大。例如，粗粒度的分类，按照学校实力，分为985、211高校，普通一本高校，二本高校，三本高校。如果再更加细的分类，一个学校里面会按照所修的课程差异性分为不同学院，不同专业，这些同学院的专业课相差较小，不同的学院的课程相差就很大了。

2、聚类与分类的区别

    分类算法是已知数据的类别，通过对样本数据的学习建立分类模型，属于监督学习；而聚类算法是不知道数据的类别，由算法根据数据的分布进行分类，属于非监督学习模型。

3、Kmeans聚类

    Kmeans聚类属于划分聚类，由用户指定聚类簇的个数k，寻找k个簇中心，按照指定的相似度计算方法将样本划分到这K个聚类中心。

这里的相似度计算有很多种方法，常用的有

欧式距离：            

余弦相似度：

下面全部采用欧式距离作为相似度度量方法

    算法流程：

    随机初始化k个聚类中心（第一次的聚类中心是随机选取的k个样本）

    

    对每个样本数据

        对每个聚类中心

            计算样本与聚类中心的相似度

        将数据点分配到相似度最高的样本中心

    对每个簇，使用簇内的样本数据特征均值更新聚类中心

   重复上述步骤，直至迭代次数达到用户指定的次数或者聚类中心基本没有改变。

    Kmeans聚类算法的优化目标函数：

                                           

    上式的xi为第i个样本点，ci为第i个样本对应的聚类。对所有的样本，寻找c个中心点μ，使得每个样本距离其中心点的欧式距离之和最小。这个函数不是凸函数，无法对其求最优化，因此在聚类的过程中无法保证求得的聚类中心为全局最优的结果。但是可以确定的是t次迭代的过程，使得这个函数的函数值越来越小。其中隐含着EM算法的思想，将所有的样本分配到最近的聚类中心属于E环节求期望，对每个簇的中心进行修正属于M环节求最小化。为了避免局部最优，通常的做法是重复进行多次聚类，每次选择不同的初始聚类中心，比较选取最优的聚类结果。

4、Kmeans聚类算法的改进Kmedoids算法

    Kmeans聚类算法中心的更新采用均值，这种方法计算简单，但是也会带来问题，对异常点会比较敏感，计算平均值时会使聚类中心的位置偏向异常点。一种对Kmeans的改进是，对聚类中心的位置更改限制为样本点。即每次修改不是求样本的均值，而是将簇内的每一个样本点尝试作为这个簇的新中心，选择一个使得簇内差异最小的样本点作为新的聚类中心点，对每个簇进行同样的更新。这种方式对异常点不敏感，但是代价比较高，计算速度，收敛速度都会下降。 

5、Kmeans聚类算法的改进Kmeans++算法

    Kmeans聚类对初始点的选取非常敏感，在大数据集上，同一个算法不同的初始化点得到的结果往往不同。Kmeans++算法改进了Kmeans算法对初始聚类中心的选取方法，聚类过程和Kmeans是一样的。Kmeans++算法选取的方式是，首先从样本点中随机一个样本点作为第一个聚类中心点。计算训练样本距离各自簇中心的距离，将这个距离存储在一个dists数组中，并求距离总和sum,在0至sum区间产生一个随机数dist,使用这个随机数从i=0开始做运算dist-=dists[i],直至dist<0,此时的下标i对应的样本点作为下一个聚类中心点。重复上述步骤，直至选出k个聚类中心点。可以将距离理解为一节线段，数组dists存储了这个线段集合的每个线段长度，而sum则是将这些线段进行了一个拼接，在这个拼接的大线段上面随机选取一个点，那么这个点落在较长的小线段片段上几率更大。这种做法选取的新的中心点不是距离已有的中心点最远的点，而是偏向于较远的点。

6、实现

下面给出了Kmeans、Kmeans++和Kmoids算法的实现

#_*_encoding:utf-8_*_
import numpy as np
import matplotlib.pyplot as plt

class KMeans:
    def __init__(self,n_clusters=3,iterNum=200,type='kmeans',type2='random'):
        self.k=n_clusters
        self.iterNum=iterNum
        self.type=type
        self.type2=type2

    def distCal(self,x,y):                                             #计算欧式距离
        return np.sqrt(np.sum(np.power(x-y,2)))

    def randCent(self):                                                #随机初始化聚类中心点
        self.centroids=np.mat(np.zeros((self.k,self.n)))
        randIndex=np.random.randint(0,self.m,self.k)
        for i in range(self.k):
            self.centroids[i,:]=self.train[randIndex[i],:]

    def Kmeans_plus(self):                                            #Kmeans++初始化聚类中心点
        self.centroids=np.mat(np.zeros((self.k,self.n)))
        firstCent=np.random.randint(0,self.m)
        i=0
        self.centroids[i,:]=self.train[firstCent,:]
        while i<self.k-1:
            self.clusterAssment=self.calClusterAssment(self.train,self.centroids[0:i+1,:])
            distSum=sum(self.clusterAssment[:,1])
            randNum=np.random.randint(0,distSum)
            index=0
            while randNum>0:
                randNum-=self.clusterAssment[index,1]
                index=index+1
            i=i+1
            self.centroids[i,:]=self.train[index-1,:]

    def fit_predict(self,train):                                      #学习数据，返回聚类结果
        self.train=np.mat(train)
        self.m,self.n=np.shape(self.train)

        if self.type2=='random':
            self.randCent()
        else:
            self.Kmeans_plus()

        if self.type=='kmeans':
            self.KMeans_cluster()
        else:
            self.Kmedoids_cluster()

        return np.reshape(self.clusterAssment[:,0],(1,np.shape(self.clusterAssment[:,0])[0]))

    def KMeans_cluster(self):                                        #Kmneas聚类
        iter=0
        while  iter<self.iterNum:
            self.clusterAssment=self.calClusterAssment(self.train,self.centroids)
            for j in range(self.k):
                clust=self.train[np.nonzero(self.clusterAssment[:,0].A==j)[0]]
                self.centroids[j,:]=np.mean(clust,axis=0)
            iter=iter+1

    def calClusterAssment(self,train,centers):                    #分配
        clusterAssment = np.mat(np.zeros((self.m, 2)))
        for i in range(self.m):
            minDist = np.inf
            minIndex = -1
            for j in range(len(centers)):
                dist = self.distCal(self.train[i, :], centers[j, :])
                if dist < minDist:
                    minDist = dist
                    minIndex = j
            clusterAssment[i, 0] = int(minIndex)
            clusterAssment[i, 1] = minDist
        return clusterAssment

    def Kmedoids_cluster(self):                                      #Kmoids聚类
        iter=0
        distSum=np.zeros((self.m,1))
        while  iter<self.iterNum:
            self.clusterAssment=self.calClusterAssment(self.train,self.centroids)
            for i in range(self.k):
                clustIndex=np.nonzero(self.clusterAssment[:,0].A==i)[0]
                for j in clustIndex:
                    distSum[j]=self.calClusterDist(self.train[clustIndex,:],self.train[j,:])

                minDist=np.inf ; minIndex=-1
                for j in clustIndex:
                    if distSum[j]<minDist:
                        minDist=distSum[j]
                        minIndex=j
                self.centroids[i,:]=self.train[minIndex,:]
            iter+=1

    def calClusterDist(self,train,center):                  #计算簇内的距离和
        dists=0
        for i in range(np.shape(train)[0]):
            dists+=self.distCal(train[i,:],center)
        return dists

    def show(self,num=0):                                    #数据显示
        y=self.clusterAssment[:,0]
        fig=plt.figure(num)

        cValue = ['r', 'y', 'g', 'b', 'r', 'y', 'g', 'b', 'r']
        mValue = ['*', '+','s','^','D']
        for i in range(self.m):
            plt.scatter(self.train[i,1],self.train[i,2],marker=mValue[int(y[i,0])],c=cValue[int(y[i,0])])
        for i in range(self.k):
            plt.scatter(self.centroids[i,1],self.centroids[i,2],c='r',marker='D')
        plt.show()


from sklearn import datasets
iris=datasets.load_iris()
x=iris.data
x=np.mat(x)
#x=np.row_stack((x,[6,6,6,6]))
km=KMeans(n_clusters=4,iterNum=50,type='kmeans',type2='kmeans++')
km.fit_predict(x)
km.show()

  

上面采用的鸢尾花数据集加载于sklearn包中。

原始数据标签的分布如下图所示：

设置K=2,选择Kmeans算法进行聚类，结果如下：

设置k=4进行聚类：

可以看出不同的k，得到的聚类簇大小是不一样。在实际使用中选择合适的k值很重要，需要根据具体需求来进行选择（并不是K越大越好）。

选择K值为3，Kmeans的第一次结果：

Kmeans的第二次结果：

,

从上面看到，这种随机初始化聚类中心点，多次运行结果明显不一样。

下面是加入异常点使用Kmeans++初始化聚类中心点效果：

异常点在右上侧，虽然不是很明显，但是依旧可以看出，聚类中心点相对于没有加入异常点向右发生偏移。

使用Kmedoids算法可以减少异常点对聚类中心的影响，下面给出使用Kmedoids算法的效果。

接下来在数据中加入一个异常点，来看看聚类中心是否发生偏移

可以看到上面两张图的显示除了新加入了一个样本点之外，聚类中心没有发现变化。也就是说，Kmoids算法对这种异常点并不敏感。

7、总结

    Kmeans算法是一种高效的聚类算法，易理解易实现，用于发现没有给出标签的数据内部的结构，属于无监督学习。时间复杂度和数据的规模m，迭代次数t,聚类个数k成正比，时间复杂度为O(kmt)。但是Kmeans算法要求数据必须是数值型数据，如果是其它类型数据则需要进行转换。Kmeans算法对异常点敏感，对初始聚类中心的选取敏感，因此有对应的改进算法Kmedoids和Kmeans++算法，这类算法都只适合于发现球型簇，不能用于发现非凸型簇。