聚类算法-kmeans

K-means（k均值）算法

   一.方法和算法流程：

        k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。

   k-means算法以k为参数，把n个样本分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。k-means算法的处理过程如下：首先，随机地 选择k个样本，每个样本初始地代表了一个簇的平均值或中心;对剩余的每个样本，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。 这个过程不断重复，直到准则函数收敛。

m个样本

伪代码如下：

K-means算法公式化解释

 记k个簇中心分别为u1,u2,u3……uk,每个簇的样本数目为N1、N2……Nk。

使用平方误差做为误差函数，得：

将该函数做为目标函数，求解该函数的最小值。可以使用梯度下降法求，该函数为凸函数，驻点为：

可以看到，要想使损失函数最小，聚类中心要为各簇中样本点的平均值。由此可以看出，K-means算法在每次迭代更新时使用各簇中样本点的平均值为聚类中心是有道理的。

误差函数使用曼哈顿距离时，簇中心点是各样本点的中值；

解释：在整个过程中都是使聚类的距离达到最小；

在当前簇划分下，寻找新的簇中心点使得当前簇划分下的距离达到最小；然后每个点寻找离自己最近的中心点，重新划分簇，使得聚类距离进一步缩小，以此循环；当达到聚类距离最小时，重新划分簇，再求中心点，中心点不再发生变化；

具体k-means算法的执行过程可以参加下图：

二.初值敏感：

k-means算法的问题：K-means算法是将簇中左右点的均值做为新的质心，但是当有异常值是，质心可能就会离大多数点比较远。比如1,2,3,4,100五个样本，均值是22，这样类别中心就离样本较远，这时选取中位数做为质心是更好的选择，这就是k-Mediods（k-中值）聚类算法。同时k-means是初值敏感的，即当选取不同的初始值时分类结果可能不同，如下图：

三.总结：

K-means的复杂度大概是T*K*N，T为迭代次数，K为中心点数，N为样本数；

优点：

1、解决聚类问题的经典算法，简单、快速

2、当处理大数据集时，该算法保持可伸缩性和高效率

3、当簇近似为高斯分布时，它的效果较好；

缺点：

1、在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用

2、k值的选择是用户指定的，不同的k得到的结果会有挺大的不同

改进：对k的选择可以先用一些算法分析数据的分布，如重心和密度等，然后选择合适的k

3.对k个初始质心的选择比较敏感，容易陷入局部最小值

改进：二分k均值（bisecting k-means）算法，它对初始的k个质心的选择就不太敏感

4、不适合非凸形状的簇或者大小差别很大的簇

4、对噪声和孤立点敏感

5.数据集比较大的时候，收敛会比较慢。

四.代码实现：

    注：1.每次重新构建的中心点不一定是存在的点，而是多个维度的中心；

   

from numpy import *
    
 # 计算欧几里得距离
def distEclud(vecA, vecB):
     return sqrt(sum(power(vecA - vecB, 2))) # 求两个向量之间的距离

 # 构建聚簇中心，取k个(此例中为4)随机质心
def randCent(dataSet, k):
    n = shape(dataSet)[1]  #特征数
    centroids = mat(zeros((k,n)))   # 每个质心有n个坐标值，总共要k个质心
    #print(centroids)
    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)
    #print(centroids)
    return centroids

#x轴随机值，y值随机值
    
 #k-means 聚类算法
def kMeans(dataSet, k, distMeans =distEclud, createCent = randCent):
    m = shape(dataSet)[0]  #样本数
    clusterAssment = zeros((m,2))   # 用于存放该样本属于哪类及质心距离
     # clusterAssment第一列存放该数据所属的中心点，第二列是该数据到中心点的距离
    centroids = createCent(dataSet, k)
    #print("-----",centroids)
    clusterChanged = True   # 用来判断聚类是否已经收敛
    while clusterChanged:
        clusterChanged = False
        for i in range(m):  # 把每一个数据点划分到离它最近的中心点
            minDist = inf; 
            minIndex = -1;
            for j in range(k):
                distJI = distMeans(centroids[j,:], dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI; 
                    minIndex = j  # 如果第i个数据点到第j个中心点更近，则将i归属为j
            if clusterAssment[i,0] != minIndex: 
                clusterChanged = True;  # 如果分配发生变化，则需要继续迭代
            clusterAssment[i,:] = minIndex,minDist**2   # 并将第i个数据点的分配情况存入字典
  #0,1,2,3四个聚簇中心点index          
        
        
        for cent in range(k):   # 重新计算中心点
            ptsInClust = dataSet[clusterAssment[:,0]==cent]   # 去第一列等于cent的所有列
            centroids[cent,:] = mean(ptsInClust, axis = 0)  # 算出这些数据的中心点
    return centroids,clusterAssment