二分 K-Means 算法

该算法补充自 《机器学习实战》 一书

常规的 K-Means 算法的误差通常只能收敛到局部最小,在此,引入一种称为二分 K-Means(bisecting kmeans)的算法,相较于常规的 K-Means,二分 K-Means 不急于一来就随机 个聚类中心,而是首先把所有点归为一个簇,然后将该簇一分为二。计算各个所得簇的失真函数(即误差),选择误差最大的簇再进行划分(即最大程度地减少误差),重复该过程直至达到期望的簇数目。

二分 KMeans 算法流程大致如下:

  1. 初始时,所有样本被看做在同一个簇:
  2. while 表示当前的簇数):

for to (对于每一个簇):

  • 计算误差
  • 在该簇上进行 K-Means 聚类,其中
  • 计算将该簇一分为二后的总误差,该误差在之后将会被用于比较

选择使得总误差最小的簇进行划分。

虽然二分 K-Means 能带来全局最优解,但是我们也可以看到,该算法是一个贪心算法,因此计算量不小。

results matching ""

    No results matching ""