K-means的改进

前言

k-means算法是数据挖掘十大经典算法之一，已出现了很多的改进或改良算法。例如

• 1、对k的选择可以先用一些算法，分析数据的分布，如重心和密度等，然后选择合适的k。
• 2、有人提出了二分k均值（bisecting k-means）算法，它对初始的k个质心的选择就不太敏感。
• 3、基于图划分的谱聚类算法，能够很好地解决非凸数据的聚类。

一、Canopy算法配合初始聚类 1.1、算法原理

• 选择质心，T1圆内的点归为本簇，T1到T2范围内的点属于可疑点(黑色的点)， T2外的点为簇外点（绿色的点）
• 从簇外点中选择质心，然后根据T1,T2划分
  • T1范围内的可疑点，划到本簇，
  • 直到所有的簇外点划分完成 划分完成， 对于较小的簇将其去掉， 此时的K值可以作为K-means的初始K值

1.2、Canopy的优缺点 1.2.1、优点

• 1、 Kmeans对噪声抗干扰较弱，通过Canopy 对比，将较小的NumPoint的Cluster直接去掉有利于抗干扰。
• 2、Canopy选择出来的每个Canopy的centerPoint作为K会更精确。
• 3、只是针对每个Canopy的内做Kmeans聚类， 减少相似计算的数量。

1.2.2、缺点（问题）

  这和需要设置初始条件的算法都有的通病，就是初始条件的选取

算法中 T1、T2的确定问题

二、K-means++

P = D ( x ) 2 ∑ x ∈ X D ( x ) 2 P= \frac{D(x)^2}{\sum_{x \in X}D(x)^2} P=∑x∈X​D(x)2D(x)2​

参考：https://www.cnblogs.com/wang2825/articles/8696830.html

其实这个算法也只是对初始点的选择有改进而已，其他步骤都一样。初始质心选取的基本思路就是，初始的聚类中心之间的相互距离要尽可能的远。

算法描述如下：

• 步骤一：随机选取一个样本作为第一个聚类中心 c1；

• 步骤二：

  • 计算每个样本与当前已有类聚中心最短距离（即与最近一个聚类中心的距离），用 D(x)表示；这个值越大，表示被选取作为聚类中心的概率较大；
  • 最后，用轮盘法选出下一个聚类中心；

• 步骤三：重复步骤二，知道选出 k 个聚类中心。

• 选出初始点后，就继续使用标准的 k-means 算法了

三、二分K-means 3.1、算法思路

• 所有点作为一个簇
• 将该簇一分为二
• 选择能最大限度降低聚类代价函数（也就是误差平方和SSE）的簇 划分为两个簇。
• 以此进行下去，直到簇的数目等于用户给定的数目k为止。

3.2、算法实现

#二分kmeans        
def biKmeans(dataSet, k, distMeas=distEclud):
    m = shape(dataSet)[0]
    clusterAssment = mat(zeros((m,2)))
    #所有样本看成一个簇，求均值
    centroid0 = mean(dataSet, axis=0).tolist()[0]#axis=0按列，matrix->list
    centList =[centroid0] #create a list with one centroid
    for j in range(m): #计算初始总误差SSE
        clusterAssment[j,1] = distMeas(mat(centroid0), dataSet[j,:])**2
    #当簇数