K-means++简介

K-means++算法是K-means算法的改进版本，由David Arthur 和Sergei Vassilvitskii 于2007年提出。传统的K-means算法需要在初始阶段在数据集中随机选择 $K$ 个点作为聚类中心，而K-means算法的聚类效果和运行时间很大程度上受初始聚类中心的选择的影响。K-means++算法对于初始聚类中心的选择进行了改进。K-means++选择聚类中心的思想为：假设已经选取了 $n$ 个初始聚类中心( $0<n<K$ )，则在选取第 $n+1$ 个聚类中心时：距离当前 $n$ 个聚类中心越远的点会有更高的概率被选为第 $n+1$ 个聚类中心。

K-means++算法描述

Step1:从数据集 $X = \left \{ x_{1} \cdots x_{n} \right \}$ 中随机选择一个样本点 $x_{i}$ 作为初始聚类中心 $c_{1}$
Step2:计算每个样本点 $x_{i}$ 与全部已有聚类中心之间的最短距离，用 $D\left ( x_{i} \right )$ 示。接着计算每个样本被选为下一个聚类重新的概率 $\frac{D\left ( x \right )^{2}}{\sum_{x \in X}^{ } D\left ( x \right )^{2}}$
Step3: 重复Step2，直至选出K个聚类中心 $C= \left \{ c_{1} \cdots c_{K} \right \}$
Step4：针对数据集中的每个样本 $x_{i}$ ，计算 $x_{i}$ 到 $K$ 个聚类中心的距离，并将 $x_{i}$ 分到距离最小的聚类中心所对应的类别中
Step5：针对每个类别 $c_{i}$ , 重新计算它的聚类中心 $c_{i} = \frac{\sum_{x \in c_{i}} x}{\left | c_{i} \right |}$
Step6：重复Step5和Step6直到聚类中心的位置不再变化

示例程序

##做数据预处理
#将数据的特征放缩到 0 - 1之间
trainset = trainset.values
from sklearn.preprocessing import MinMaxScaler
scaler = MinMaxScaler(feature_range=(0, 1))
scaled_data = scaler.fit_transform(trainset)

###K-means++聚类
num_clusters = 8
estimator = KMeans(n_clusters=num_clusters, max_iter=300, n_init=40, 
                    init='k-means++',n_jobs=-1)
estimator.fit(scaled_data)

###获取聚类标签
label_pred = estimator.labels_ 
#获取聚类中心
centroids = estimator.cluster_centers_ 
inertia = estimator.inertia_ 
##聚类中心的原始坐标
centroids = scaler.inverse_transform(centroids)