K-means算法的改进：K-means++

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

算法步骤

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

算法描述如下：

• 步骤一：随机选取一个样本作为第一个聚类中心 c1；
• 步骤二：计算每个样本与当前已有类聚中心最短距离（即与最近一个聚类中心的距离），用D(x)表示；这个值越大，表示被选取作为聚类中心的概率较大；最后，用轮盘法选出下一个聚类中心；
• 步骤三：重复步骤二，知道选出 k 个聚类中心。
• 选出初始点后，就继续使用标准的 k-means 算法了。
• 效率
• K-means++ 能显著的改善分类结果的最终误差。尽管计算初始点时花费了额外的时间，但是在迭代过程中，k-mean 本身能快速收敛，因此算法实际上降低了计算时间。网上有人使用真实和合成的数据集测试了他们的方法，速度通常提高了 2 倍，对于某些数据集，误差提高了近 1000 倍。
• python实现
• 这里只说明初始点筛选的代码，因为其他步骤和k-means 一样：