聚类算法（三）——二分K-means算法

简介

由于传统的KMeans算法的聚类结果易受到初始聚类中心点选择的影响，因此在传统的KMeans算法的基础上进行算法改进，对初始中心点选取比较严格，各中心点的距离较远，这就避免了初始聚类中心会选到一个类上，一定程度上克服了算法陷入局部最优状态。
二分KMeans(Bisecting KMeans)算法的主要思想是：首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大限度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇。以此进行下去，直到簇的数目等于用户给定的数目k为止。以上隐含的一个原则就是：因为聚类的误差平方和能够衡量聚类性能，该值越小表示数据点越接近于他们的质心，聚类效果就越好。所以我们就需要对误差平方和最大的簇进行再一次划分，因为误差平方和越大，表示该簇聚类效果越不好，越有可能是多个簇被当成了一个簇，所以我们首先需要对这个簇进行划分。
二分K-means算法是基于层次的聚类算法

算法

误差函数

SSE作为度量质量的目标函数，衡量的是簇的聚类效果，值越小表明簇的中元素分布越紧密

Python实现

基于K-means的算法进行改进，便可以实现二分K-means算法
脱离循环的条件变更为获得k个簇

while len(self.clusterList) != self.k:

每次都选择SSE值最大的簇进行分裂

for i in self.clusterList:
    if i.SSE() > maxSSE:
        maxSSE = i.SSE()
        tmp_c = i

对该簇进行m次K-means算法聚类，分裂成两个簇，并从m次聚类中选出生成最小SSE的两个簇

#　尝试ｍ次ＫＭＥＡＮＳ算法
for i in range(self.m):

    tmpList = []
    tmpNote = np.zeros(tmp_c.node_num) - 1

    for i in range(2):
        c = clusterUnit()
        initcentroid = random.choice(tmp_c.get_node_list())
        c.add_node(initcentroid)
        tmpList.append(c)

    clusterChange = True
    while clusterChange == True:
        clusterChange = False
        for i, data in enumerate(tmp_c.get_node_list()):
            minDist = 100000
            minIndex = -1
            for j in range(2):
                distance = clusterUnit.distance(tmpList[j].centroid, data)
                if distance < minDist:
                    minDist = distance
                    minIndex = j
            if int(tmpNote[i]) != minIndex:
                clusterChange = True
                if int(tmpNote[i]) != -1:
                    tmpList[int(tmpNote[i])].remove_node(data)
                tmpList[minIndex].add_node(data)
                tmpNote[i] = minIndex
    tmpSSE = sum(i.SSE() for i in tmpList)
    #　选出生成最小ＳＳＥ的两个簇
    if tmpSSE < minSSE:
        min_cluster_list = tmpList
        minSSE = tmpSSE

输出得到的聚类效果图

分析

可以发现，与K-means相比，二分K-means聚类效果更好，算法不再受初始化节点的影响，但算法花销也更大，对于K值以及m值需要多次调整才可获得更好的聚类效果。

Ref

• https://www.cnblogs.com/eczhou/p/7860435.html
• 《数据挖掘原理与实践》