二分K-均值算法

为了解决K-均值算法收敛于局部最小值的问题，有人提出了二分K-均值的算法。首先，将整个数据集作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续划分。选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述过程不断重复，直到得到用户指定的簇数目为止。
伪代码如下：

将所有点看成一个簇
当簇数目小于k时：
    对于每一个簇：
        计算总误差
        在给定的簇上面进行K-均值聚类（k=2）
        计算将该簇一分为二之后的总误差
    选择使得误差最小的那个簇进行划分

另一种做法是选择SSE最大的簇进行划分。

def biKmeans(dataSet, k, distMeas=distEclud):
    m = dataSet.shape[0]
    clusterAssment = np.mat(np.zeros((m,2)))
    # 计算初始簇的质心
    centroid0 = np.mean(dataSet, axis=0).tolist()[0]
    # 保存质心的列表
    centList = [centroid0]
    # 计算并保存每个点到初始质心的误差
    for j in range(m):
        clusterAssment[j, 1] = distMeas(np.mat(centroid0), dataSet[j, :]) ** 2
    while len(centList) < k:
        lowestSSE = np.inf
        # 遍历当前所有的簇
        for i in range(len(centList)):
            # 当前簇的所有点
            ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:,0].A == i)[0], :]
            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
            # 被划分的SSE
            sseSplit = np.sum(splitClustAss[:, 1])
            # 没有被划分的簇的SSE
            sseNotSplit = np.sum(clusterAssment[np.nonzero(clusterAssment[:,0].A != i)[0], 1])
            if (sseSplit + sseNotSplit) < lowestSSE:
                bestCentToSplit = I
                bestNewCents = centroidMat
                bestClustAss = splitClustAss.copy()
                lowestSSE = sseSplit + sseNotSplit
        # 更新
        bestClustAss[np.nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)
        bestClustAss[np.nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit
        centList[bestCentToSplit] = bestNewCents[0, :]
        centList.append(bestNewCents[1, :])
        clusterAssment[np.nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :] = bestClustAss
    centList = list([np.matrix.tolist(i)[0] for i in centList])
    print(centList)
    return np.mat(centList), clusterAssment

下面看一下实际运行效果。

data = np.mat(loadDataSet('testSet2.txt'))
centList, clustAssing = biKmeans(data, 3)

cluster1 = data[np.nonzero(clustAssing[:,0].A == 0)[0]]
cluster2 = data[np.nonzero(clustAssing[:,0].A == 1)[0]]
cluster3 = data[np.nonzero(clustAssing[:,0].A == 2)[0]]

import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']

plt.scatter(cluster1[:, 0].T.tolist()[0], cluster1[:, 1].T.tolist()[0], marker='s')
plt.scatter(cluster2[:, 0].T.tolist()[0], cluster2[:, 1].T.tolist()[0], marker='o')
plt.scatter(cluster3[:, 0].T.tolist()[0], cluster3[:, 1].T.tolist()[0], marker='*')
plt.scatter(centList[:,0].T.tolist()[0], centList[:,1].T.tolist()[0], marker='+', s=150)
plt.title('二分K-均值算法聚类结果')
plt.show()

结果如下。

小结

• 聚类是无监督学习。
• 聚类将相似数据点归于同一簇，不相似数据点归于不同簇。
• 聚类可以使用多种不同的方法来计算相似度。
• Kmeans算法从k个随机质心开始，简单有效但容易受到随机的初始质心影响。
• 二分K-均值算法可以解决Kmeans收敛到局部最小值的问题。