详解k-means++

一、概述

定义：k-means++是一种为k-means聚类算法选择初始值（或“种子”）的算法。它是NP-hard k-means问题的一种近似算法，它是一种避免标准k-means算法有时发现的较弱聚类的方法。

K-means与K-means++：原始K-means算法最开始随机选取数据集中K个点作为聚类中心，而K-means++按照如下的思想选取K个聚类中心：假设已经选取了n个初始聚类中心(0<n<K)，则在选取第n+1个聚类中心时：距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第一个聚类中心(n=1)时同样通过随机的方法。可以说这也符合我们的直觉：聚类中心当然是互相离得越远越好。这个改进虽然直观简单，但是却非常得有效。

二、k-means算法

首先使用欧式距离平方作为样本之间的距离即有 $d(x_{i},x_{j})=||x_{i}-x_{j}||^{2}_{2}$ ，其中 $x_{i},x_{j}$ 表示样本

1.算法步骤

（1）从样本集中随机抽取K个样本作为初始均值向量
（2）计算样本与各均值向量的距离，根据样本距离最近的均值向量，将样本划入相应的簇
（3）计算新的均值，即聚内平均值 $1/|C_{i}|\sum_{x\in C_{i}}x$ ，将均值向量更新。
（4）重复2,3直到均值向量均为更新

2.k-means

k-means聚类就是求解最优化问题
$min\ E=\sum_{i=1}^{k}\sum_{x\in C_{i}}||x-u_{i}||^{2}_{2}$
其中 $C_{i}$ 为第 $i$ 簇， $u_{i}$ 为第 $i$ 个簇的均值向量, $x$ 为样本

3.NP-hard问题

相似的样本被聚到同类时，损失函数最小，上式中的目标函数的最优化能达到聚类的效果，但是此问题为组合优化问题，n个样本被分到k类，所有可能的分法的数目为
$S(n,k)=i/k!\sum_{l=1}^{k}(-1)^{k-l}C_{k}^{l}k^{n}$
此数字为指数级，则k-means聚类的最优解求解问题问NP-hard问题

三、k-means++算法

1.算法步骤

（1）在数据点之间随机选择一个中心 $u_{1}$ 。
（2）对于尚未选择的每个数据点 $x$ ，计算 $\sum_{i=1}^{i=j}d(x,u_{i})$ ，即x与已经选择的最接近中心之间的距离。
（3）使用加权概率分布随机选择一个新的数据点作为新中心，其中选择的点 $x$ 的概率与 $\sum_{i=1}^{i=j}d(x,u_{i})$ 成正比。
（4）重复步骤2和3，直到选择了 $k$ 个中心 $(即 j = k)$ 。
（5）现在已经选择了初始中心，继续使用标准k均值聚类。

2.例子

假设数据集有8个样本，k为2，分布及其对应序号如下
在这里插入图片描述
假设随机抽取6号点被选择为第一个初始聚类中心，即为 $u_{1}$ ，那在进行每个样本的 $d(x,u_{1})$ 和被选择为第二个聚类中心的概率如下表所示

序号	①	②	③	④	⑤	⑥	⑦	⑧
$d(x,u_{1})$	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

其中的P(x)就是每个样本被选为下一个聚类中心的概率
从上表可以直观的看到第二个初始聚类中心是1号，2号，3号，4号中的一个的概率为0.2+0.325+0.125+0.25=0.9。而这4个点正好是离第一个初始聚类中心6号点较远的四个点。这也验证了K-means的改进思想：即离当前已有聚类中心较远的点有更大的概率被选为下一个聚类中心。