数据挖掘算法之K-means

一、K-means算法

• 解释
  精髓：随机选取k个聚类中心，利用最小距离方法判断每一个样本点的所属类别

• Formulation
  $E=\displaystyle\sum_{i=1}^n\sum_{x\isin C_{i}}{\lVert x-\mu_{i}\lVert ^2 _{2}}$E=i=1∑n​x∈Ci​∑​∥x−μi​∥22​
  $\mu_{i}$μi​为第i个聚类中心的样本均值
  
  二、K-means算法的k类初始点的选取：

• 方法一 ：

  • 先选取 一个点，然后找距离此点距离最远的一个样本点最为第二个初始点，第三个选取距离此两个距离最远的点，以此类推。

• 方法二：

  • canopy 算法
    （1）、将数据集向量化得到一个list后放入内存，选择两个距离阈值：T1和T2，其中T1 > T2，对应上图，实线圈为T1，虚线圈为T2，T1和T2的值可以用交叉校验来确定；

    （2）、从list中任取一点P，用低计算成本方法快速计算点P与所有Canopy之间的距离（如果当前不存在Canopy，则把点P作为一个Canopy），如果点P与某个Canopy距离在T1以内，则将点P加入到这个Canopy；

    （3）、如果点P曾经与某个Canopy的距离在T2以内，则需要把点P从list中删除，这一步是认为点P此时与这个Canopy已经够近了，因此它不可以再做其它Canopy的中心了；

    （4）、重复步骤2、3，直到list为空结束。
    所得到的canopy可以作为初始点k的值。

  三、K-means的改进
  加速算法：elkan K-Means
  利用三角形的两边之后大于第三边，两边之差小于第三边。减少一些不必要的计算距离。