第五章、聚类分析

0. 聚类算法的系统性介绍

聚类被定义为一个数据集的无监督分类。聚类算法的目的是使用距离或者概率度量对给定数据集（点集或者对象的集合）划分成数据实例或者对象（点）的组。根据距离或相似性或其他度量，同一个组中的成员比较接近。换言之，就是最大化类内（内部同质性）的相似性并最小化类间（外部异质性）的相似性。

使用聚类算法一方面是为了数据的进一步分析，另一方面是为了理解数据集的性质。

聚类过程的关键步骤：

①特征选择：从原始数据集中选择重要的特征

②聚类算法设计：基于当前可用的聚类算法设计一个适当的算法，或者可以从头开始建立一个算法。

③聚类验证：该步骤评估聚类，并提供关于聚类结果的置信度。

④结果解释：给出输入数据集的内在思想，或者根据数据集有什么获取到的潜在知识。

主要的聚类方法有基于划分的方法、基于密度的方法、层次方法、谱方法和基于网格的方法等。对于特定的数据集或者条件，每个聚类算法都有其局限性与最佳实践，另一个困难或者目标是任意形状的类、大容量的数据集、高维数据集、对噪声的不敏感性、对用户定义的参数的低度依赖、在初始学习或者聚类后没有学习处理新数据的能力、对类的数目的内在或者本质的敏感性、漂亮的数据可视化，以及同时适用于数值数据的名义数据类型。

1. k均值算法和搜索引擎

1.0 基于划分的聚类算法

基于划分的聚类算法一般过程是迭代，第一步定义或者选择一个预定的类的代表数，每一次迭代后，如果聚类质量有所改善，那么就更新类的代表。在聚类算法中，具体类的质量可以通过很多度量方式来衡量的。

基于划分的聚类算法的特点：(1)在大多数情况下得到的类是互斥的(2)类的形状是球形的，因为采用的大多数度量是基于距离的度量(3)每类的代表通常是所对应的组（类）中的点的均值或者中心点(medoid) (4)一个分区代表一个类(5)这些类适用于小型到中型的数据集(6)在某个收敛目标函数下，该算法将收敛，所得到的类经常是局部最优的。

1.1 k均值聚类算法（基于平方误差的聚类算法）

k均值聚类算法从根本上说是一个贪婪算法，也是一个互斥聚类算法，它用每个类的均值定义其重心。对于处理大型数据集它是有效的。它以一种互斥的方式对数据集进行分类，一个对象至多只能属于一个组或者一个类。它还是一种划分聚类算法，类是在一个步骤中创建的，而不是多几个步骤创建的。

k均值算法执行尽可能多的迭代，直到与前一次聚类得到的类相比没有任何变化。

k均值算法详解以及小例子： https://www.cnblogs.com/yue-guan/p/1072kmeans.html

https://www.jianshu.com/p/c4651e198b1e

事实上，k均值算法可以根据重心不同的初始集合运行多次，以便找到相对较好的结果。

k均值算法的缺点：(1) 类的均值只能用一个函数来表示 (2) 仅适用于数值数据类型(3) k的值需要用户预先定义，而这是很难的。

1.2 核k均值聚类算法

核函数通常与SVM经常结合在一起进行使用。总的来说，核函数，就是将输入空间，映射到高维的特征空间。然后再在高维的数据同看进行数据处理。这种映射的话，是非线性变换的，这也才能能够将输入空间映射出不同特征的高维空间。

算法详细解析：https://www.cnblogs.com/subaiBlog/p/6271315.html

https://blog.csdn.net/zhangping1987/article/details/31366143

1.3 k模式聚类算法

该算法是k均值算法的变体，它可以处理分类数据类型和大型数据集，它可以与k均值方法结合来处理包含所有数据类型的数据集的聚类。

1.4 搜索引擎和网页聚类

网络搜索引擎可能会用到k均值算法来用于网页聚类，算法表现出高效率。

2. k中心节点算法和自动提取文档文本

k中心算法是k均值算法的扩展，以降低对异常数据点的敏感性。

2.1 PAM算法（Partitioning Around Medoids ,PAM）

围绕中心点的划分算法是一种基于划分的聚类算法。

算法思想：

一个聚类与k个中心点的集合相关，可以通过每个类中的成员与相应的代表或者中心点之间的距离来衡量聚类的质量。

从对象的原始数据集中任意选择k个对象是找到k个中心点的第一步。在每一步中，对于一个选定的对象Oi和一个未选择的节点Oh，如果因为交换它们，类的质量得到提升，那么执行交换。在交换之前和交换之后，类的质量应该是成员与中心点之间的所有距离差的和。

PAM算法详细解析： https://www.cnblogs.com/king-lps/p/7775108.html

https://www.cnblogs.com/wenhoujx/p/3147563.html

2.2 自动提取和总结文档文本

提取或者总结已经普遍定义为具有两个步骤的过程。首先，从源文本中提取重要概念来获取一个中间表示。然后，从中间表示生成总结。

对于总结的第一步，它可以很大程度上视为自动索引的一部分。从文档中提取重要概念的词汇链是一种可能的解决方案。词汇链利用任意数量的相关词汇之间的凝聚力，并且通过将语义相关的词汇集进行分组（链接）来计算他们。

3. CLARA算法及实现

3.1 CLARA算法（Clustering LARge Application，大型应用中的聚类算法）

算法思想：不考虑整个数据集合，而是选择实际数据的一小部分作为数据的代表。然后用PAM方法从样本中选择中心点。如果样本是以非常随机的方式选取的，那么它应当接近代表原来的数据集。从中选出代表对象（中心点）很可能和从整个数据集合中选出的代表对象相似（这里可以使用分块来计算，减少了计算量）。CLARA抽取数据集合的多个样本，对每个样本应用PAM算法，并返回最好的聚类结果作为输出。

CLARA的有效性主要取决于样本的大小。如果任何一个最佳抽样中心点不在最佳的K个中心之中，则CLARA将永远不能找到数据集合的最佳聚类。同时这也是为了聚类效率做付出的代价（提高了效率）。是有效处理大样本聚类问题的方法利器。

CLARA算法详细解析： https://blog.csdn.net/u013834836/article/details/41214709

3.2 R语言实现（略）

4. CLARANS算法及实现

4.1 CLARANS算法(A Clustering Algorithm based on Randomized Search，基于随机选择的聚类算法)

此算法是空间挖掘的最佳实践，将采样技术（CLARA）和PAM结合起来，CLARANS在任何时候都不把自身局限于任何样本，CLARANS在搜素的每一步都以某种随机性选取样本。

CLARANS算法详细解析： https://blog.csdn.net/assiduousknight/article/details/16831941

4.2 R语言实现（略）

5. 仿射传播聚类和无监督的图像分类

仿射传播（Affinity Propagation,AP）寻找数据集中的一组样本点Xe={xe1，...,xek},并将未选择的点分配给这些样本点，一个样本点代表一个类。

5.1 仿射传播聚类

AP聚类思想：AP算法的基本思想是将全部样本看作网络的节点，然后通过网络中各条边的消息传递计算出各样本的聚类中心。聚类过程中，共有两种消息在各节点间传递，分别是吸引度( responsibility)和归属度(availability) 。AP算法通过迭代过程不断更新每一个点的吸引度和归属度值，直到产生m个高质量的Exemplar（类似于质心），同时将其余的数据点分配到相应的聚类中。

算法详细解析：

AP近邻传播聚类算法总结：https://blog.csdn.net/manjhOK/article/details/78734025

AP近邻传播聚类算法(Affinity Propagation)：https://blog.csdn.net/captainstudio/article/details/50770316

AP聚类： https://blog.csdn.net/zhouboke/article/details/80626962

5.2 无监督图像分类

无监督图像分类是一种聚类问题。图像聚类是识别一组相似的图像原语，比如像素、线(元)素和区域等。给定复杂的数据集，推荐的方法是使用基于原型的聚类算法。仿射传播可以通过寻找具有代表性的范例的一个子集来应用于无监督分类。

5.3 谱聚类算法（很流行但是很麻烦，原理好像不难）

谱聚类在最近几年变得受欢迎起来，主要原因就是它实现简单，聚类效果经常优于传统的聚类算法（如K-Means算法）

对于谱聚类来说最重要的工具就是拉普拉斯矩阵了

谱聚类算法的详细解析：

一个同学的学习笔记： https://blog.csdn.net/qq_24519677/article/details/82291867

刘建平的谱聚类算法原理总结： https://www.cnblogs.com/pinard/p/6221564.html