K均值聚类算法
本博客根据 百面机器学习，算法工程师带你去面试 一书总结归纳，公式图片均出自该书.
本博客仅为个人总结学习，非商业用途，侵删.
网址 http://www.ptpress.com.cn
聚类是在事先并不知道任何样本类别标签的情况下， 通过数据之间的内在关系把样本划分为若干类别， 使得同类别样本之间的相似度高， 不同类别之间的样本相似度低。
如下图是一个聚类示意图：
K均值聚类（KMeans Clustering） 是最基础和最常用的聚类算法。 它的基本思想是， 通过迭代方式寻找K个簇（Cluster）的一种划分方案， 使得聚类结果对应的代价函数最小。
定义代价函数为各个样本距离所属簇中心点的误差平方和，如下式：
其中\(x_i\)代表第i个样本， \(c_i\)是\(x_i\)所属于的簇， \(μ_{ci}\)代表簇对应的中心点， M是样本总数。
K均值聚类的具体步骤:
K均值聚类的核心目标是将给定的数据集划分成K个簇， 并给出每个数据对应的簇中心点。步骤如下：
- 数据预处理，如归一化、 离群点处理等。
- 随机选取K个簇中心，记为
。
- 定义代价函数：
- 令t=0,1,2,… 为迭代步数，重复下面过程直到 J 收敛：
- 对于每一个样本\(x_i\),将其分配到距离最近的簇
- 对于每一个类簇k,重新计算该类簇的中心
K均值算法在迭代时，假设当前J没有达到最小值，那么首先固定簇中心\({μ_k}\)，调整每个样例\(x_i\)所属的类别\(c_i\)来让J函数减少；然后固定\({c_i}\)，调整簇中心\({μ_k}\)使J减小。这两个过程交替循环,J单调递减：当J递减到最小值时\({μ_k}\)和\({c_i}\)也同时收敛。
下面的图示展示了K均值算法的一个迭代过程。首先，给定二维空间上的一些样本点（图a），直观上这些点可以被分成两类； 接下来，初始化两个中心点（图b）中棕色和黄色叉子代表中心点）， 并根据中心点的位置计算每个样本所属的簇（图c用不同颜色表示）； 然后根据每个簇中的所有点的平均值计算新的中心点位置（图d）； 图e 和图f 展示了新一轮的迭代结果； 在经过两轮的迭代之后， 算法基本敛。
K 均值聚类的缺点：
需要手动缺点K值；
- 受初值和离群点的影响每次的结果不稳定；
- 结果通常不是全局最优而是局部最优；
- 无法很好得解决数据簇分布差别比较大的情况（比如一个类是另一类样本数量的100倍）；
不太适用于离散分类。
K 均值聚类的优点：
- 对于大数据集， K均值聚类算法相对是可伸缩和高效的， 它的计算复杂度是O(NKt)接近于线性， 其中N是数据对象的数目， K是聚类的簇数， t是迭代的轮数。
- 尽管算法经常以局部最优结束， 但一般情况下达到的局部最优已经可以满足聚类的需求。
如何针对上面的缺点进行调优：
（1） 数据归一化和离群点处理。K均值聚类本质上是一种基于欧式距离度量的数据划分方法， 均值和方差大的维度将对数据的聚类结果产生决定性的影响。同时，离群点或者少量的噪声数据就会对均值产生较大的影响， 导致中心偏移， 因此使用K均值聚类算法之前通常需要对数据做预处理。
（2） 合理选择K值。K值的选择一般基于经验和多次实验结果。
- 采用手肘法， 我们可以尝试不同的K值， 并将不同K值所对应的损失函数画成折线，如下图横轴为K的取值， 纵轴为误差平方和所定义的损失函数。手肘法认为拐点就是K的最佳值，即K=3时。手肘法是一个经验方法，缺点是不够自动化。
-
Gap Statistic方法
这里我们继续使用上面的损失函数，当分为K簇时，对应的损失函数记为\(D_k\)。 Gap Statistic定义为Gap(K)=E(log\(D_k\))−log\(D_k\) ，其中E(log\(D_k\))是log\(D_k\)的期望， 一般通过蒙特卡洛模拟产生。我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多的随机样本， 并对这个随机样本做K均值， 得到一个\(D_k\)； 重复多次就可以计算出E(log\(D_k\))的近似值。
那么Gap(K)有什么物理含义呢？ 它可以视为随机样本的损失与实际样本的损失之差。试想实际样本对应的最佳簇数为K， 那么实际样本的损失应该相对较小， 随机样本损失与实际样本损失之差也相应地达到最小值， 从而Gap(K)取得最大值所对应的K值就是最佳的簇数。
（3）采用核函数
传统的欧式距离度量方式， 使得K均值算法本质上假设了各个数据簇的数据具有一样的先验概率， 并呈现球形或者高维球形分布， 这种分布在实际生活中并不常见。 面对非凸的数据分布形状时，可能需要引入核函数来优化， 这时算法又称为核K均值算法， 是核聚类方法的一种。 核聚类方法的主要思想是通过一个非线性映射,将输入空间中的数据点映射到高位的特征空间中， 并在新的特征空间中进行聚类。
针对K均值算法的缺点，有哪些改进的模型？
K-means++算法:
K-means++算法是对初始值的选择进行改进。原始K均值算法最开始随机选取数据集中K个点作为聚类中心， 而K-means++按照如下思路选取K个聚类中心。假设已经选取了n个初始聚类中心（0<n<K） ，则在选取第n+1个聚类中心时， 距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。 在选取第一个聚类中心（ n=1） 时同样通过随机的方法。
ISODATA算法（迭代自组织数据分析法）：
当K值的大小不确定时， 可以使用ISODATA算法。在K均值算法中， 聚类个数K的值需要预先人为地确定， 并且在整个算法过程中无法更改。 而当遇到高维度、 海量的数据集时， 人们往往很难准确地估计出K的大小。ISODATA算法就是针对这个问题进行了改进， 它的思想也是：当属于某个类别的样本数过少时， 把该类别去除； 当属于某个类别的样本数过多、 分散程度较大时， 把该类别分为两个子类别。
ISODATA算法在K均值算法的基础之上增加了两个操作， 一是分裂操作， 对应着增加聚类中心数； 二是合并操作， 对应着减少聚类中心数。 ISODATA算法的缺点是需要指定的参数比较多， 不仅仅需要一个参考的聚类数量\(K_o\)， 还需要制定3个阈值。
ISODATA算法的各个输入参数：
（1） 预期的聚类中心数目\(K_o\)。在ISODATA运行过程中聚类中心数可以变化， \(K_o\)是一个用户指定的参考值， 该算法的聚类中心数目变动范围也由其决定。具体地， 最终输出的聚类中心数目常见范围是从\(K_o\)的一半， 到两倍\(K_o\)。
（2）每个类所要求的最少样本数目\(N_{min}\)。 如果分裂后会导致某个子类别所包含样本数目小于该阈值， 就不会对该类别进行分裂操作。
（3） 最大方差Sigma。 用于控制某个类别中样本的分散程度。 当样本的分散程度超过这个阈值时， 且分裂后满足（1） ， 进行分裂操作。
（4） 两个聚类中心之间所允许最小距离\(D_{min}\)。 如果两个类靠得非常近（即这两个类别对应聚类中心之间的距离非常小)，小于该阈值时， 则对这两个类进行合并操作。