kMeans

• kMeans是一种无监督学习聚类算法，也就是给样本分簇。是一种适合用在数据分布未知时的聚类算法，聚类的目的是最大化簇的内聚性（同一簇距离近），最小化簇间的耦合性（不同簇距离远）。

  

  kMeans算法过程

工作流程

1. 首先随机确定$k$个初始点作为簇心；
2. 查询数据集每个点距离最近的簇心点，分配到该簇中；
3. 将簇心更新为该簇所有点的特征均值；
4. 重复上述流程直到所有点都距离它对应簇心最近时结束（收敛）。

评价指标

• 在线性回归中我们使用MSE来评价性能并以此为目标进行优化，在kMeans中使用**误差平方和SSE（Sum of Squared Error）**来进行评价

  $$\mathrm{SSE} = \min{\sum_i^{d(x_i, c(x_i))}}$$

  其中$c(x_i)$代表第$i$个对象$x_i$所处的簇中心（特征均值），当然这里还涉及到距离的计算，在回归篇中已经介绍了多种距离算法，这里不再赘述。

和kNN的对比

• 我们会发现kMeans也是使用距离度量对样本进行“抱团”。同时k的值也会严重影响算法的结果，因为选取不当很有可能只收敛到局部最优解。

  对于kMeans来说，其更适合“球形”数据，即每一簇都较为集中，在各个维度呈圆形分布在簇心周围。如果离群点较多的话，对kMeans的质心计算影响较大。

二分kMeans算法

• 在介绍kMeans时提到其可能只收敛到局部最优解，此时我们可以合并最近的簇心或者合并两个使得SSE增幅最小的簇心，除此之外我们还可以使用一种新的kMeans算法：二分kMeans算法

  该算法按照如下规则操作：

  1. 将所有点看成一个簇；
  2. 当簇数目小于$k$时，对每一个簇计算总误差，并单独对于该簇的样本选择参数$k=2$进行kMeans聚类，得到两个子簇，再计算将该簇一分为二之后的总误差；
  3. 选择上述操作中误差最小的簇划分为子簇；
  4. 回到第二步，直到簇数目等于$k$为止。

  另一种做法给定$m>k$个簇，选择SSE最大的簇进行划分，直到簇数目达到$k$个为止。因为每次都会固定增加/减少一个簇，所以可以在指定次数内收敛到$k$个簇。

  相比kMeans而言，在大规模数据集上效率更高，因为它不需要每次迭代重新计算所有样本点的距离，同时也弱化了初始簇心的选取对最终聚类效果的影响。不过它依然需要手动进行参数选择，也就是$k$的值，同样也会由于$k$的值过大/过小导致各类问题。