二分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收敛到局部最小值的问题。
