机器学习算法学习-Kmeans

1. 算法

Kmeans应该算是最经典最易懂的机器学习算法之一。其基本数学思想是期望最大化（EM），简单概况就是物以类聚，以特征空间中不同样本之间的“距离”远近作为划分的依据。

2. 优缺点特点

2.1 优点

容易理解，聚类效果不错，虽然是局部最优，但往往局部最优就够了；

处理大数据集的时候，该算法可以保证较好的伸缩性；

当簇近似高斯分布的时候，效果非常不错；

算法复杂度低。

2.2 缺点

K 值需要人为设定，不同 K 值得到的结果不一样；

对初始的簇中心敏感，不同选取方式会得到不同结果；

对异常值敏感；

样本只能归为一类，不适合多分类任务；

不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类。

3. 算法调优与改进

3.1 数据预处理

K-means 的本质是基于欧式距离的数据划分算法，均值和方差大的维度将对数据的聚类产生决定性影响。所以未做归一化处理和统一单位的数据是无法直接参与运算和比较的。常见的数据预处理方式有：数据归一化，数据标准化。

此外，离群点或者噪声数据会对均值产生较大的影响，导致中心偏移，因此我们还需要对数据进行异常点检测。

3.2 合理选择 K 值

K 值的选取对 K-means 影响很大，这也是K-means 最大的缺点，常见的选取 K 值的方法有：手肘法、Gap statistic 方法。

3.3 采用核函数

基于欧式距离的 K-means 假设了了各个数据簇的数据具有一样的的先验概率并呈现球形分布，但这种分布在实际生活中并不常见。面对非凸的数据分布形状时我们可以引入核函数来优化，这时算法又称为核 K-means 算法，是核聚类方法的一种。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

3.4 K-means++

我们知道初始值的选取对结果的影响很大，对初始值选择的改进是很重要的一部分。在所有的改进算法中，K-means++ 最有名。

3.5 ISODATA

ISODATA 的全称是迭代自组织数据分析法。它解决了 K的值需要预先人为的确定这一缺点。而当遇到高维度、海量的数据集时，人们往往很难准确地估计出 K 的大小。ISODATA 就是针对这个问题进行了改进，它的思想也很直观：当属于某个类别的样本数过少时把这个类别去除，当属于某个类别的样本数过多、分散程度较大时把这个类别分为两个子类别。