kmeans算法k值的确定和初始点的选择

k值的确定

首先kmeans算法有以下目标函数：

$Obj=\sum_{k}\sum_{i\in S_k}(x_i-c_k)^2$

其中$c_k$是第$k$类的中心点，$S_k$是第$k$类的点集。手肘法通过枚举$k$并画出每个$k$对应的目标函数曲线，曲线的梯度会从小变大，曲线的拐点就是最适合的$k$值。当数据量很大时，枚举的每轮的计算量都非常大，注意到目标函数的曲线呈手肘状，可以使用二分法快速定位到最适合的$k$值。

每个样本点都可以计算一个轮廓系数，公式如下：

$s(i)=\frac{b(i)-a(i)}{max(a(i),b(i))}$

$a(i)$是样本$i$与同类的样本的平均距离,$b(i)$是样本$i$与最近类样本的平均距离,$s(i)$就是样本$i$的轮廓系数，轮廓系数的取值范围是$[-1,1]$，越大表示聚类效果越好。和手肘法一样，通过枚举$k$并计算每个$k$对应的所有样本点的平均轮廓系数，选择轮廓系数最佳的$k$值。

除了目标函数和轮廓系数，还可以使用其他的指标去衡量和选择$k$值。

直接随机选择$k$个样本作为$k$类的初始点。

(1) 随机选择第一个初始中心点
(2) 每个样本计算与该样本最近的初始中心点的距离
(3) 每个样本的距离作为该样本的权重，是该样本被选中的概率的度量，根据这个概率分布选出新的一个初始中心点
(4) 重复(2)(3)直到选出$k$个初始中心点

使用层次聚类对所有样本进行聚类，当剩下$k$个类别时结束聚类，从$k$个类别中随机选择$k$个初始中心点。

上述初始点的选取方法都会受到离群点的干扰，所以在之前需要使用一些方法去除噪声点。