机器学习笔记-聚类介绍1

前言：hello，我是你们的好朋友小花，由于最近事情也比较忙，导师天天说要写一篇文章发表一下，正好我想写一篇关于聚类的，那我就用这篇博客来为我的论文理一理知识脉络吧。

1.1问题引入

最近美国大选终于落下了帷幕，川普以微弱优势击败希拉里老阿姨当选美国第46任总统，现在用大数据谈选举属于老生常谈了。川普得票率是51%，希拉里得票是49%，如果其中有2.00001%的人改变自己的选择那么将会对人类的历史产生重大的影响，当然这个在天朝除外，大家懂得。大家想每一次票选，一定会有一些人摇摆不定，如果我们找到这些人，制定相关的政策得到他们的票选，希拉里将会当选第一位美国总统。那如何找到呢，下面我们来说说思路。

1.2思路

如下图，假设希拉里和川普的死忠党都是40%，现在我们的目标就是吸引2.000001%的人给希拉里，所以我们通过收集到的数据（我们不管这些数据如何得到）对他们进行聚类，很容易找到哪些是死忠，哪些是动摇者。

机器学习笔记------聚类介绍1

1.3何为聚类

迄今为止,聚类还没有一个学术界公认的定义.这里给出 Everit在 1974 年关于聚类所下的定义:一个类簇内的实体是相似的，不同类簇的实体是不相似的，一个类簇是测试空间中点的会聚,同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离，类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离。

聚类过程:

1) 数据准备:包括特征标准化和降维。

2) 特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中。

3) 特征提取:通过对所选择的特征进行转换形成新的突出特征。

4) 聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量; 而后执行聚类或分组。

5) 聚类结果评估:是指对聚类结果进行评估.评估主要3 种，外部有效性评估、内部有效性评估和相关性测试评估.。

二聚类的种类

这里来说说聚类与分类的区别，分类是处理有标签的数据，分类属于监督学习，聚类是处理无标签数据，所以属于无监督学习。聚类的方法有很多种，我来给大家说说聚类的几种方法。

传统聚类算法多数属于硬聚类，每个元素只能属于一个集合，在元素特征模糊时聚类结果将受到影响。此外，一些传统聚类算法需要输入子集数量的初始值，这使得在处理大数据时聚类效果不佳。但传统聚类是现代聚类发展的理论基础和实践先驱，因此对于传统聚类的介绍和理解具有重要意义。

2.1层次法

层次法的指导思想是对给定待聚类数据集合进行层次化分解。此算法又称为数据类算法，此算法根据一定的链接规则将数据以层次架构分裂或聚合，最终形成聚类结果。

从算法的选择上看，层次聚类分为自顶而下的分裂聚类和自下而上的聚合聚类。

分裂聚类初始将所有待聚类项看成同一类，然后找出其中与该类中其他项最不相似的类分裂出去形成两类。如此反复执行直到所有项自成一类。

聚合聚类初始将所有待聚类项都视为独立的一类，通过联接规则，包括单链接、全连接、类间平均连接，以及采用欧氏距离作为相似度计算的算法，将相似度最高的两个类合并成一个类。如此反复执行直到所有项并入同一个类。

BIRCH算法是层次算法中的典型代表算法，其核心是CF（Cluster Feature）和CF树。

CF是一个存储了聚类信息的三元组，其中包含了N（待聚类项个数），（N个数据点的线性和），SS（N个数据点的平方和）。和SS分别反映了聚类的质心和聚类的直径大小。

CF树有两个参数：分支因子和阈值T。分支因子包括非叶节点CF条目的最大个数和叶节点CF条目的最大个数。这里叶节点看作聚合而成的一个簇。阈值T限定了所有条目的最大半径或直径。

BIRCH算法主要有四个阶段。第一阶段扫描待聚类的所有数据项，根据初始阈值T初始化一颗CF树。第二阶段采用聚合思路，通过增加阈值T重建CF树，使其聚合度上升。第三、四阶段，对已有的CF树实行全局聚类以得到更好的聚类效果。

然而BIRCH算法并未给出详细的设定初始阈值T的方法，只是简单地赋值T=0，在第二阶段中，BIRCH算法也并未给出增加T值的规则。

2.2划分法

划分法属于硬聚类，指导思想是将给定的数据集初始分裂为K个簇，每个簇至少包含一条数据记录，然后通过反复迭代至每个簇不再改变即得出聚类结果。划分聚类在初始的一步中即将数据分成给定个数个簇。在算法过程中还需使用准则函数对划分结果进行判断，易产生最有聚类结果。

K-Means算，中文译为K均值算法。这种算法通过迭代不断移动个聚簇中心和簇类成员，直到得到理想的结果。通过K均值算法得到的聚簇结果，簇内项相似度很高，簇间项相似度很低，具有较好的局部最优特性，但并非是全局最优解。此外，K均值只能定义在数值类属性值上，无法处理其他类型的数据。针对于无法产生全局最优解问题，算法的研究者们一部分倾向于通过优化初始簇的选择算法和均值计算改善算法性能，另一部分则允许簇分裂与合并，来调整簇间关系。

K-Harmonic Means（K调和均值）算法是建立在中心基础上的迭代算法。其评价函数为所有点到所有中心的均方距离的调和平均值函数。P个数，的调和平均值定义为HA=P/。这样的评价函数，通过对于项的分布给不同项赋值不同权重，可以将过于集中的中心点移到数据附近没有中心点的区域上。这种算法降低了对初始点选取的依赖，提高了算法的鲁棒性。

2.3基于密度的方法

上文中提到的两类算法，其聚类的划分都以距离为基础，容易产生类圆形的凸聚类。而密度算法很好的克服了这一缺点。密度算法的指导思想是将空间中密度大于某一阈值的点加入到一个聚类中。

DBSCAN算法是基于密度聚类的经典算法。它将簇定义为密度相连的点的最大集合，将足够高密度的区域划分为簇。这样的算法对噪声具有健壮性，并且可以发现任意形状的聚簇。DBSCAN的基本算法流程为，从任意对象P开始根据阈值和参数通过广度优先搜索提取从P密度可达的所有对象，得到一个聚类。若P是核心对象，则可以一次标记相应对象为当前类并以此为基础进行扩展。得到一个完整的聚类后，在选择一个新的对象重复上述过程。若P是边界对象，则将其标记为噪声并舍弃。

尽管DBSCAN算法改进完善了上述两种算法的一些缺陷，但此算法也存在不足。如聚类的结果与参数关系较大，阈值过大容易将同一聚类分割，阈值过小容易将不同聚类合并。此外固定的阈值参数对于稀疏程度不同的数据不具适应性，密度小的区域同一聚类易被分割，密度大的区域不同聚类易被合并。