K-Means

基本步骤

来源: https://zhuanlan.zhihu.com/p/149441104
KMeans算法本身思想比较简单，但是合理的确定K值和K个初始类簇中心点对于聚类效果的好坏有很大的影响。

缺点:

K的选择需要事先预定。
K个初始质心的位置选择对聚类结果和运行时间都有很大影响。
不能保证全局最优，可能是局部最优解。

来源: https://zhuanlan.zhihu.com/p/149441104

k-means优化

基于欧几里得距离，K-Means算法需要优化的问题就是，使得簇内误差平方和(within-cluster sum of squared errors,SSE)最小，也叫簇惯性(cluster intertia)。

K-Means算法需要随机选择初始化的中心点，如果中心点选择不合适，可能会导致簇的效果不好或产生收敛速度慢等问题。解决这个问题一个比较合适的方法就是，在数据集上多次运行K-Means算法，根据簇内误差平方和(SSE)来选择性能最好的模型。

除此之外，还可以通过**K-Means++**算法，让初始的中心点彼此的距离尽可能的远，相比K-Means算法，它能够产生更好的模型。

确定K个初始类簇中心点

参考: https://www.cnblogs.com/yunshangkanjing/p/12907374.html

1. 随机选择k个点作为初始的类簇中心点，但是该方法在有些情况下的效果较差.

2. 选择彼此距离尽可能远的K个点

首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。这种方法效果还不错.

step1：计算所有样本点之间的距离，选择距离最大的一个点对（两个样本C1, C2）作为2个初始中心点，从样本点集中去掉这两个点。

step2：如果初始中心点个数达到k个，则终止。如果没有，在剩余的样本点中，选一个点C3，这个点优化的目标是：
在这里插入图片描述
来源: https://blog.csdn.net/ten_sory/article/details/81016748

4. 先对数据用层次聚类算法或者Canopy算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。

Canopy算法:
首先定义两个距离T1和T2，T1>T2.从初始的点的集合S中随机移除一个点P，然后对于还在S中的每个点I，计算该点I与点P的距离，如果距离小于T1，则将点I加入到点P所代表的Canopy中，如果距离小于T2，则将点I从集合S中移除，并将点I加入到点P所代表的Canopy中。迭代完一次之后，重新从集合S中随机选择一个点作为新的点P，然后重复执行以上步骤。

Canopy算法执行完毕后会得到很多Canopy，可以认为每个Canopy都是一个Cluster，与KMeans等硬划分算法不同，Canopy的聚类结果中每个点有可能属于多个Canopy。我们可以选择距离每个Canopy的中心点最近的那个数据点，或者直接选择每个Canopy的中心点作为KMeans的初始K个类簇中心点。