Kmeans++ Theory.md

Kmeans & Kmeans++

---

• Kmeans 聚类

样本集合， 为样本个数。，为每个样本的特征个数。

要把这些样本分为类，个类别的样本集合分别为。

得到的个类别要使得下式取得最小值：

其中表示第个类别的样本集合中样本的个数；

表示第个类别的中心；

表示第个类别的样本集合中的第个样本。

表示第个类别的样本集合中的样本与该类别中心的距离。

• 不同的距离计算方式 有两个点, 坐标分别为。

  • 欧几里得距离

  

  • 曼哈顿距离

  

  • 闵可夫斯基距离

  

根据样本特征选择不同的距离公式，本算例采用欧几里得距离。

• Kmeans 聚类步骤

  1. 随机选择个类别中心；

  2. 对每一个样本计算和个类别中心的距离，找到距离最小的，

  然后将该样本添加到样本集合中；

  3. 计算得到的个类别的样本集合中样本的均值，作为新的个类别中心；

  4. 满足迭代次数或者类别个类别中心不再变化，则停止。

Kmeans聚类算法的结果会因为初始的类别中心的不同差异很大，为了避免这个缺点，下面介绍对初始类别中心的选择进行了优化的Kmeans++聚类算法。

• Kmeans++聚类步骤

  1. 从样本集合中随机选择一个样本作为第1个类别中心；

  2. 对于样本集合中的每一个样本，计算其与上一个刚被选择成为

  类别中心的样本之间的距离；

  3. 较大的样本，被选取作为类别中心的概率较大；

  4. 重复步骤和直到个初始的类别中心被选出；

  5. 进行Kmeans算法。