写在前面 今天参加了我在校招季的第一次面试，发现整个过程中只有讲到自己课题的时候才特别流畅，果然熟练度是一样很难替代的东西，只有花时间实践才能不断地加强。和面试官的交流让我意识到自己学习方法的不足，以往对待任何问题，只是习惯地去看公式、敲代码，很少彻底地/从数学的角度思考：这种方法为什么能解决这个问题？所以，今天我想好好总结一下几种最基础的机器学习算法，弥补之前学习的纰漏之处。
K-means聚类是一种无监督的学习方法，它的具体步骤相信动手写过代码的人都很清楚，在这里就简单地描述一下： 首先选择k个初始质心点（k为用户设定的参数，即期望分类的簇个数），然后遍历点集，将每个点分入与质心点距离最近的一类，重复执行上一步直到质心不再发生变化。 注1“距离最近”需要用合适的邻近性度量方法，对于点集通常使用欧式距离，对文档用余弦相似性。 注2 质心通常由簇的均值计算得到。 K-means的主要缺点是，聚类效果依赖于k值和初始质心的选择、对离群点敏感，同时，K-means聚类不能处理非球形簇、不同尺寸和不同密度的簇，如下图所示：
对于邻近性度量为欧式距离的情况，通常用误差平方和（SSE）作为聚类质量的衡量标准，SSE的定义如下，其中Ci为第i个簇，ci是其对应的质心： K-means聚类的迭代过程正是在试图最小化SSE值，然而，不合理的k值或初始质心选择，可能会导致最终只能得到次最优（SSE值局部最小）的聚类结果。
优化初始点的选择 随机的初始质心可能会导致只能得到局部最优的聚类结果，即使通过多次重复运行也不能克服，这里有另一种选择初始质心的方法：随机地选取第一个点，然后对于每个后继初始质心，选择离已经选取过的初始质心最远的点，使用这种方法可以确保初始点是散开的。但是，这种方法也存在选中离群点的可能，同时付出的计算时间也比较多。 使用后处理提高聚类性能 增大k值是一种肯定可以减小SSE值的方法，但这显然违背了聚类的初衷。除此之外，一种改进聚类结果的方法是对生成的簇进行后处理：将具有较大SSE值的簇二分，为了保持簇总数的不变，再将两个簇合并。这里可以选择合并质心最近或者合并后使SSE增幅最小的两个簇。 二分K-means算法 针对K-means聚类收敛于局部最小值的问题，二分K-means算法首先将所有点作为一个簇，然后将该簇一分为二，之后选择其中SSE值最大的簇进行二分，不断重复以上过程直到得到用户指定的簇数目。
基于层次的聚类方法 层次聚类技术主要分为两类：凝聚的和分裂的。凝聚的也可以理解为自下而上的，一开始每个点都各自是一个簇，每一步合并两个最接近的簇；分裂的也可以理解为自上而下的，一开始所有点都在同一个簇中，每一步分裂一个簇，合并/分裂的终止条件取决于用户期望的簇的个数。 凝聚层次分类需要定义簇的邻近性，不同的邻近性定义区分了各种凝聚层次技术，这里主要介绍一下全链（complete）、组平均（average）和Ward方法，三种方法的聚类结果实例如图： 1、complete linkage中，两个簇的邻近度定义为两个不同簇中任意两点之间的最长距离。 2、average linkage中，两个簇的邻近度定义为不同簇的所有点对邻近度的平均值，例如，簇Ci和Cj的邻近度定义为： 其中mi，mj为簇的大小 3、ward linkage中，两个簇的邻近度定义为两个簇合并时导致的平方误差的增量。 凝聚层次聚类避免了初始点的选择，也没有局部极小的问题，它的主要问题是，缺乏全局目标函数、是否应当平等地对待不同大小的簇、以及合并决策是不可逆的，而且凝聚层次聚类的时间复杂度为O(n2logn)，对于数据量大的模型来说过于昂贵。
基于密度的聚类方法 基于密度的聚类方法是一种在稠密区域中建立簇、丢弃噪声点（稀疏区域）的方法。其中，DBSCAN是一种简单、有效的基于密度的聚类算法，具体步骤如下： 首先将所有点标记为核心点、边界点或噪声点，删除噪声点；然后为距离在Eps之内的所有核心点之间赋予一条边，每组连通的核心点形成一个簇；最后将边界点分别划分到与之关联的核心点的簇中。 核心点的定义是，该点给定邻域内的点的个数超过给定的阈值；边界点不是核心点，但落在某个核心点的邻域内；噪声点是既非核心点也非边界点的其它点。 DBSCAN可以处理任意形状和大小的簇，但是当簇密度变化太大时会出现问题，同时，近邻计算的开销有可能会产生很大的开销。
更多聚类算法总结的相关内容可以参考：用于数据挖掘的聚类算法有哪些，各有何优势？ 注3：图片转自Clustering—scikit-learn
