未来面试之四：聚类

胡说八道

时间过的真快呀，又到了周六了。还赶上五一小长假，别提有多惬意啦。还是放假比较好呀，唉。可是学习还是得学呀，不然谁来为你的未来负责，今天来写写非监督学习：聚类。

学习

一般来说，训练深度学习网络的方法主要有四种：监督学习、非监督学习、半监督学习和强化学习（强化学习可能是后来才有的，以前没有听说过这个东西）。

先说说监督学习：通过已有的训练样本来训练，从而得到一个最优模型，再利用这个模型将所有新的数据样本映射为相应的输出结果，对输出结果进行简单的判断从而四线分类的目的。（这句话是搜来的）

无监督学习：一看名字就知道是跟监督学习对着来的，无监督学习就是事先没有训练数据样本，直接对数据进行建模，比如说聚类。

半监督学习：是监督学习和非监督学习相结合的一种方法。半监督学习使用大量的未标记数据，以及同时使用标记数据，来进行模式识别工作。（这个我了解的也不多）

强化学习：又称励志学习、评价学习（有兴趣的话可以搜集网络上的知识进行学习，还是挺有趣的）

监督学习与非监督学习的一个最本质的区别用简单容易理解的话来说就是：监督学习的应用要求数据集事先有标签，而非监督学习则不需要标签。

聚类定义

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一簇中的对象相似度较高，与其它簇中的对象相似度较低。相似度是根据描述对象的属性值来度量的，距离是经常采用的度量方式。

聚类常用算法

聚类的算法hin多，我曾经从一本书上看到过好多的聚类算法，有的甚至连听都没听说过，但是呢，现阶段知道辣么多也没用哈，因此，这里参考《数据挖掘R语言实战》那本书给大家介绍常用的五种：K-均值聚类、K-中心点聚类、密度聚类、系谱聚类、期望最大化聚类。需要说明的是，这些算法本身无所谓优劣，而最终运用于数据的效果却存在好坏差异。

必备概念

讲聚类之前我们需要提前了解几个概念，首先第一个就是簇的概念：聚类将数据集中的样本划分为若干个通常是不想交的子集，每个子集称为一个“簇”。实际上簇这个词没有一个比较规范而且准确的定义，所以说上边这个定义是方便理解簇的概念而做的一个简单的解释。

类的度量：常用的类的度量方法有两种，距离和相似系数。距离用来度量样品之间的相似性，相似系数用来度量变量之间的相似性。

距离中我们常采用：闵可夫斯基距离、兰氏距离、马哈拉诺比斯距离（具体公式就不写了，度娘都知道）

相似系数：通常用夹角余弦、相关系数来衡量。

根据聚类的原理可以将聚类分为：划分聚类、层次聚类、基于密度的聚类、基于网格的聚类、基于模型的聚类。

K-均值聚类

K-均值算法是最早出现的聚类分析算法之一，它是一种快速聚类方法，但对于异常值极其敏感，因此较适合处理分布集中的大样本数据集。

它的思路是：以随机选取的K（预设类别数）个样本作为起始中心点，将其余样本归入相似度最高中心点所在的簇，再确立当前簇中样本坐标的均值为新的中心点，依次循环迭代下去，直至所有样本所属类别不再变动。至于什么是相似度，什么是簇，就不细说了，因为我也说不好。别说错了误导大家。

K-中心点聚类

K-中心点算法与K-均值算法在原理上十分接近，它是针对于K-均值算法易受极值影响这一缺点的改进算法。在原理上的差异在于选择各类别中心点时不取样本均值点，而在类别内选取到其余样本距离之和最小的样本为中心。

系谱聚类

系谱聚类的过程可以通过类似于系谱图的形式呈现出来，相对于K-均值聚类算法与K-中心点算法，系谱算法的突出特点在于不需要事先设定类别数K，这是因为它每次迭代过程仅将距离最近的两个样本/簇聚为一类，其运作过程将自然得到K=1至K=n(n为待分类样本总数)个类别的聚类结果。

密度聚类

DBSCAN算法是基于密度的聚类方法中最常用的代表算法之一，它相对于K-均值、K-中心点以及系谱聚类这些基于距离的聚类算法，其优势在于弥补了他们只能发现“类圆形”聚类簇的缺陷，该类算法由于是基于“密度”来聚类的，可以在具有噪声的空间数据库中发现任意形状的簇。

首先明确其输入值为待聚类数据集、半径E（即为例图中各圆形的半径大小）与密度阈值MinPts，具体步骤如下：

1，从数据集中选择一个未处理的样本点,，如我们第一次选择图I中的点1；

2，以该点1为圆心，作半径为E的圆，由于圆内圈入点的个数为3，满足密度阈值MinPts，因此称点1为核心对象（用黑色实心圆点表示），且将圈内的4个点形成一个簇，其中点1直接密度可达周围的3个灰色实心圆点；

3，同理考察其他样本点，重复步骤2若干次，得到图III，其中点1直接密度可达核心对象3，且点2密度可达点3；

4，当该过程进行到图IV，我们发现点4的E邻域内仅有2个点，小于阈值MinPts，因此，点4为边缘点（非核心对象），然后继续考察其他点；

5，当所有对象都被考察，该过程结束，得到图VIII。我们看到椭圆形内有若干核心对象和边缘点，这些点都是密度相连的。

6，最后一步即为将各点归类，见图IX

DBSCAN算法的不足在于它对于用户定义参数半径E及密度阈值MinPts很敏感，参数取值细微的不同可能会导致差别很大的结果，而且参数的选取无规矩可循，只能不断尝试靠经验确定。

期望最大化聚类

期望最大化算法（以下简称EM算法）的思路十分巧妙，在使用该算法进行聚类时，它将数据集看作一个含有隐性变量的概率模型，并以实现模型最优化，即获取与数据本身性质最契合的聚类方式为目的，通过“反复估计”模型参数找出最优解，同时给出相应的最优类别数K。

该算法相比于前面介绍的几种聚类算法要更为抽象，以下我们继续以图示的方式来直观解说。下图中，图II是对图I中的10个样本点随机聚类的初始结果，可以明显看到聚类效果很差；随后进行第一、二次迭代，聚类结果分别如图III、IV所示，每一次都比前一次更契合数据，至V完成第三次迭代，聚类结束。

总结

聚类这一部分在机器学习中是一大重点，如果要详细写起来的话可以出本书了。这里介绍的这部分用来应付四五千级别（北京）的面试应该是没有问题了。如果想详细的了解更多聚类的知识的话可以参考周英、卓金武写的《大数据挖掘 系统方法与实例分析》和周志华的《机器学习》，但是周志华的这本书偏数学，对于我这种数学渣渣只能看前边的那本啦。上面有错误的地方烦请批评指正，方便大家共同学习。