K-Means Clustering.
本文目录：
- K-means
- K-medoids
1. K-means
（1）K-Means算法的流程
假设共有$N$个样本点$x_1,…,x_N$，需要将其划分为$K$类。记每一类的聚类中心（cluster centroid）为$μ_1,…,μ_K$。
定义失真函数（distortion function）(也叫畸变函数)，用来选择合适的聚类中心以及对每个样本进行正确的分类:
\[J = \frac{1}{N} \sum_{n=1}^{N} {\sum_{k=1}^{K} {[x_n \in k](x_n-μ_k)^2}}\]这是一个组合优化问题，采用交替优化的方法：
- 簇分配（cluster assignment）：固定聚类中心，把每个样本按照距离划分到最近的类别（即固定$μ$，最小化$J$）；
- 移动聚类中心（move centroid）：固定样本类别，每一类的聚类中心由该类的样本均值确定（即固定每个样本的类别$k$，最小化$J$）。
该算法还需要选择初始聚类中心，可随机选择其中$K$个样本。
（2）K-Means算法的图示
- 随机选择$k$个初始聚类中心；
- 把每个样本点划分到与其最近的聚类中心所属的类别；
- 更新聚类中心为每一个聚类的均值：
- 重复步骤$2$和$3$，直至数据的划分不再变化。
（2）K-Means算法的缺点：
i.
K-Means需要预先给定类别数$K$，可用肘部法则（elbow method）选定。即根据不同的$K$画出失真函数曲线$J$,选取“肘部”的$K$作为最终的类别数：
ii.
由于采用交替优化的方法，容易陷入局部最优；选择初始聚类中心对结果影响较大:
为防止陷入局部极小值，K-Means常循环进行$50$至$1000$次，选择其中失真函数$J$最小的结果。
iii.
需要多次遍历样本集合，计算复杂度高；
iv.
只能找到类球形的类，不能发现任意的类；
v.
对噪声敏感。
2. K-medoids
K-Means与K-Medoids算法过程类似，区别在于：
- K-Means算法用聚类的均值作为新的聚类中心；
- K-Medoids算法用类内最靠近中心的数据点作为新的聚类中心。
K-Medoids算法对outlier不敏感。
