K-means与K-means++

特点对比

原始 K-means 算法随机选取数据集中K个点作为聚类中心。

而 K-means++ 专注于初始化中心位置。按照如下的思想选取K个聚类中心：

• 假设已经选取了n个初始聚类中心(0<n<K)，则在选取第n+1个聚类中心时，距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。
• 在选取第一个聚类中心(n=1)时同样通过随机的方法。

可以说这也符合我们的直觉：聚类中心当然是互相离得越远越好。这个改进虽然直观简单，但是却非常得有效。

经典K-means算法：

步骤

• Step 1: 从数据集中随机选取K个样本作为初始聚类中心${\cal C}={c_1,c_2,...,c_k }$；
• Step 2: 针对数据集中每个样本$x_i$，计算它到K个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中；
• Step 3: 针对每个类别$c_i$，重新计算它的聚类中心$c_i=\frac{1}{|c_i|}\sum_{x \in c_i}x$（即属于该类的所有样本的质心）；
• Step 4: 重复第2步和第3步直到聚类中心的位置不再变化；

最小化势函数(potential function):$\sum_{x \in X}\min_{c \in {\cal C}}||x-c||^2_2$，是一个NP-hard问题。

补充：聚类中心数目的选取

值得一提的是关于聚类中心数目（K值）的选取，的确存在一种可行的方法，叫做Elbow Method：

通过绘制K-means代价函数与聚类数目K的关系图，选取直线拐点处的K值作为最佳的聚类中心数目。

上述方法中的拐点在实际情况中是很少出现的。

比较提倡的做法还是从实际问题出发，人工指定比较合理的K值，通过多次随机初始化聚类中心选取比较满意的结果。

K-means++算法：

原因

由于 K-means 算法的分类结果会受到初始点的选取而有所区别，因此有提出这种算法的改进: K-means++ 。

步骤

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

算法描述如下：

• Step 1: 从数据集中随机选取一个样本作为初始聚类中心 $c_1$；
• Step 2:
  • 首先计算每个样本与当前已有类聚中心之间的最短距离（即与最近一个聚类中心的距离），用D(x)表示；
  • 接着计算每个样本被选为下一个聚类中心的概率$\frac{D(x)^2}{\sum_{x \in X}D(x)^2}$，(D(x)越大，表示被选取作为聚类中心的概率较大)；
  • 最后，用轮盘法选出下一个聚类中心；
• Step 3: 重复第2步，直到选出 K 个聚类中心。

选出初始点后，之后的过程与经典 k-means 算法中第2步至第4步相同。

效率

K-means++ 能显著的改善分类结果的最终误差。同时在速度和解决质量上有提高。

尽管计算初始点时花费了额外的时间，但是在迭代过程中，k-mean 本身能快速收敛，因此算法实际上降低了计算时间。

网上有人使用真实和合成的数据集测试了他们的方法，速度通常提高了 2 倍，对于某些数据集，误差提高了近 1000 倍。

举例

下面结合一个简单的例子说明K-means++是如何选取初始聚类中心的。

数据集中共有8个样本，分布以及对应序号如下图所示：

#1(3,4)

#2(4,4)

#3(3,3)

#4(4,3)

#5(0,2)

#6(1,2)

#7(0,1)

#8(1,1)

假设经过 Step 1 后，6号点被选择为第一个初始聚类中心，那在进行步骤二时每个样本的D(x)和被选择为第二个聚类中心的概率如下表所示：

序号	#1	#2	#3	#4	#5	#6	#7	#8
$D(x)$	$2\sqrt{2}$	$\sqrt{13}$	$\sqrt{5}$	$\sqrt{10}$	1	0	$\sqrt{2}$	1
$D(x)^2$	8	13	5	10	1	0	2	1
$P(x)$	0.2	0.325	0.125	0.25	0.025	0	0.05	0.025
Sum	0.2	0.525	0.65	0.9	0.925	0.925	0.975	1

其中的P(x)就是每个样本被选为下一个聚类中心的概率。

最后一行的Sum是概率P(x)的累加和，用于轮盘法选择出第二个聚类中心。

方法是随机产生出一个0~1之间的随机数，判断它属于哪个区间，那么该区间对应的序号就是被选择出来的第二个聚类中心了。

例如1号点的区间为[0,0.2)，2号点的区间为[0.2, 0.525)。

从上表可以直观的看到第二个初始聚类中心是1号，2号，3号，4号中的一个的概率为0.9。

而这4个点正好是离第一个初始聚类中心6号点较远的四个点。

这也验证了K-means的改进思想：即离当前已有聚类中心较远的点有更大的概率被选为下一个聚类中心。

可以看到，该例的K值取2是比较合适的。当K值大于2时，每个样本会有多个距离，需要取最小的那个距离作为D(x)。

refs

1 K-MEANS++:THE ADVANTAGES OF CAREFUL SEEDING

2 K-MEANS++:THE ADVANTAGES OF CAREFUL SEEDING