机器学习

支持向量机、逻辑回归、决策树等经典的机器学习算法主要用户分类问题，即根据一些给定类别的样本，训练某种分类器，使得它能够对类别未知的样本进行分类，与分类问题不同，聚类是在事先不知道任何样本类别标签的情况下，通过数据之前的内在关系把样本划分为若干类别，使得同类样本之间的相似度高，不同类别之间的样本相似度低。

分类问题属于监督学习的范畴，而聚类问题属于非监督学习。K均值聚类，即K-means算法是最基础和最常用的聚类算法。它的基本思想是通过迭代方式寻找K个簇的一种划分方案，使得聚类结果对应的代价函数最小。特别地，代价函数可以定义为各个样本距离所属簇中心的误差平方和。

K均值聚类的和弦目标是将给定的数据集划分成K个簇，并给出每个数据对应的簇中心点。具体步骤：

1）数据预处理，如归一化，离群点处理等。

2）随机选取K个簇中心，记为U0,U1,...,Uk

3）定义代价函数：J(c,u)=minmin∑||x-Uc||^2

4）令t=0,1,2,...为迭代步数，重复下面过程知道代价函数J收敛：

a对于每一个样本，将其分配到距离最近的簇

b对于每一个类簇，重新计算该类簇的中心。

K均值算法在迭代过程中，假设当前J没有达到最小值，那么首先固定簇中心，调整每个样例所属的类别来让J函数减少；然后固定类别，调整类簇中心，从而使J减小。这两个过程交替循环，J单调递减，当J递减到最小时，类簇和簇中心也趋于收敛。

K均值算法有一些缺点，受初始值和离群点的影响每次的结果不稳定、结果通常不是全局最优而是局部最优解、无法很好的解决数据簇类分布差别比较大的情况，例如一类是另一类样本数量的100倍的情况。K均值也不太适用于离散分类等。K均值的优点也是很明显的，主要体现在对于大数据集，K均值聚类算法相对是可伸缩和高效的，它的计算复杂度是O（NKt）接近于线性，其中N是数据对象的数目，K是聚类的簇数，t是迭代的轮数。

K均值算法的调优一般可以从以下几个角度出发。

(1) 数据归一化和离群点处理。

K均值聚类本质上是一种基于欧氏距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性的影响，所以未做归一化处理和统一单位的数据是无法直接参与运算和比较的。同时，离群点或者少量噪声数据就会对均值产生较大的影响，导致中心偏移，因此使用K均值聚类算法之前通常需要对数据做预处理。

（2）合理选择K值。

K值的选择是K均值聚类最大的问题之一，这也是K均值聚类算法的主要缺点。K值的选择一般基于经验或者多次实验结果。例如手肘法，就是尝试不同的K值，并将不同K值所对应的损失函数画成折线，横轴为K的取值，纵轴为误差平方和定义的损失函数。手肘法认为拐点就是K的最优值。

手肘法是一个经验方法，缺点是不能够自动化，因此研究员又提出来更先进的方法，其中包括比较有名的Gap Statistics方法，Gap Statistics方法的优点是不需要肉眼判断，只需要找到最大的Gap Statistics所对应的K即可，因此该方法也适用于批量优化作业。

（3）采用核函数。

采用核函数是另一种可以尝试的改进方向。传统的欧氏距离度量方式，使得K均值算法本质上假设了各个数据簇的数据具有一样的先验嫌疑，并呈现球形或者高维球形分布，这种分布在实际生活中并不常见。面对非凸的数据分布数据时，可能需要引入核函数来优化，这时算法又是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。