如何正确选择聚类算法？

作者 | Josh Thompson

来源 | 数据派THU

Choosing the Right Clustering Algorithm for your Dataset - KDnuggets

聚类算法十分容易上手，但是选择恰当的聚类算法并不是一件容易的事。

数据聚类是搭建一个正确数据模型的重要步骤。数据分析应当根据数据的共同点整理信息。然而主要问题是，什么通用性参数可以给出最佳结果，以及什么才能称为“最佳”。

本文适用于菜鸟数据科学家或想提升聚类算法能力的专家。下文包括最广泛使用的聚类算法及其概况。根据每种方法的特殊性，本文针对其应用提出了建议。

四种基本算法以及如何选择

聚类模型可以分为四种常见的算法类别。尽管零零散散的聚类算法不少于100种，但是其中大部分的流行程度以及应用领域相对有限。

基于整个数据集对象间距离计算的聚类方法，称为基于连通性的聚类（connectivity-based）或层次聚类。根据算法的“方向”，它可以组合或反过来分解信息——聚集和分解的名称正是源于这种方向的区别。最流行和合理的类型是聚集型，你可以从输入所有数据开始，然后将这些数据点组合成越来越大的簇，直到达到极限。

层次聚类的一个典型案例是植物的分类。数据集的“树”从具体物种开始，以一些植物王国结束，每个植物王国都由更小的簇组成（门、类、阶等）。

层次聚类算法将返回树状图数据，该树状图展示了信息的结构，而不是集群上的具体分类。这样的特点既有好处，也有一些问题：算法会变得很复杂，且不适用于几乎没有层次的数据集。这种算法的性能也较差：由于存在大量的迭代，因此整个处理过程浪费了很多不必要的时间。最重要的是，这种分层算法并不能得到精确的结构。

同时，从预设的类别一直分解到所有的数据点，类别的个数不会对最终结果产生实质性影响，也不会影响预设的距离度量，该距离度量粗略测量和近似估计得到的。

根据我的经验，由于简单易 *** 作，基于质心的聚类（Centroid-based）是最常出现的模型。 该模型旨在将数据集的每个对象划分为特定的类别。 簇数（k）是随机选择的，这可能是该方法的最大问题。 由于与k最近邻居（kNN）相似，该k均值算法在机器学习中特别受欢迎。

计算过程包括多个步骤。首先，输入数据集的目标类别数。聚类的中心应当尽可能分散，这有助于提高结果的准确性。

其次，该算法找到数据集的每个对象与每个聚类中心之间的距离。最小坐标距离（若使用图形表示）确定了将对象移动到哪个群集。

之后，将根据类别中所有点的坐标平均值重新计算聚类的中心。重复算法的上一步，但是计算中要使用簇的新中心点。除非达到某些条件，否则此类迭代将继续。例如，当簇的中心距上次迭代没有移动或移动不明显时，聚类将结束。

尽管数学和代码都很简单，但k均值仍有一些缺点，因此我们无法在所有情景中使用它。缺点包括：

因为优先级设置在集群的中心，而不是边界，所以每个集群的边界容易被疏忽。 无法创建数据集结构，其对象可以按等量的方式分类到多个群集中。 需要猜测最佳类别数（k），或者需要进行初步计算以指定此量规。

相比之下，期望最大化算法可以避免那些复杂情况，同时提供更高的准确性。简而言之，它计算每个数据集点与我们指定的所有聚类的关联概率。用于该聚类模型的主要工具是高斯混合模型（GMM）–假设数据集的点服从高斯分布。

k-means算法可以算是EM原理的简化版本。它们都需要手动输入簇数，这是此类方法要面对的主要问题。除此之外，计算原理（对于GMM或k均值）很简单：簇的近似范围是在每次新迭代中逐渐更新的。

与基于质心的模型不同，EM算法允许对两个或多个聚类的点进行分类-它仅展示每个事件的可能性，你可以使用该事件进行进一步的分析。更重要的是，每个聚类的边界组成了不同度量的椭球体。这与k均值聚类不同，k均值聚类方法用圆形表示。但是，该算法对于不服从高斯分布的数据集根本不起作用。这也是该方法的主要缺点：它更适用于理论问题，而不是实际的测量或观察。

最后，基于数据密度的聚类成为数据科学家心中的最爱。

这个名字已经包括了模型的要点——将数据集划分为聚类，计数器会输入ε参数，即“邻居”距离。因此，如果目标点位于半径为ε的圆（球）内，则它属于该集群。

具有噪声的基于密度的聚类方法（DBSCAN）将逐步检查每个对象，将其状态更改为“已查看”，将其划分到具体的类别或噪声中，直到最终处理整个数据集。用DBSCAN确定的簇可以具有任意形状，因此非常精确。此外，该算法无需人为地设定簇数 —— 算法可以自动决定。

尽管如此，DBSCAN也有一些缺点。如果数据集由可变密度簇组成，则该方法的结果较差；如果对象的位置太近，并且无法轻易估算出ε参数，那么这也不是一个很好的选择。

总而言之，我们并不能说选择了错误的算法，只能说其中有些算法会更适合特定的数据集结构。为了采用最佳的（看起来更恰当的）算法，你需要全面了解它们的优缺点。

例如，如果某些算法不符合数据集规范，则可以从一开始就将其排除在外。为避免繁琐的工作，你可以花一些时间来记住这些信息，而无需反复试验并从自己的错误中学习。

我们希望本文能帮助你在初始阶段选择最好的算法。继续这了不起的工作吧！

1 系统聚类法 :由N类--1类
2 分解法 ：由1类---N类
3 K-均值法 ：事先在聚类过程中确定在K类，适用于数据量大的数据
4 有序样品的聚类 ：N个样品排序，次序相邻的样品聚成一类
5 模糊聚类法 ：模糊数学的方法，多用于定性变量
6 加入法 ：样品依次加入，全部加入完得到聚类图。

a夹角余弦
b相关系数

a常用的类间距离定义有8种之多，与之相应的 系统聚类法 也有8种，分别为
a 中间距离法
b 最短距离法 ：类与类之间的距离最近两个样品的距离。
c 最长距离法 ：类与类之间的距离最远两个样品的距离。先距离最短，后距离最远合并
d 类平均法 ：两类元素中任两个样品距离的平均。
e 重心法 ：两个重心xp 和xq 的距离。
f 可变类平均法
e 离差平方和法（Ward法） ： 该方法的基本思想来自于方差分析，如果分类正确，同 类样品的离差平方和应当较小，类与类的离差平方和较大。 具体做法是先将 n 个样品各自成一类，然后每次缩小一类，每 缩小一类，离差平方和就要增大，选择使方差增加最小的两 类合并，直到所有的样品归为一类为止。

a 最短距离法的主要缺点是它有链接聚合的趋势，容易形 成一个比较大的类，大部分样品都被聚在一类中，所以最短 距离法的聚类效果并不好，实际中不提倡使用。
b 最长距离法克服了最短距离法链接聚合的缺陷，两类合 并以后与其他类的距离是原来两个类中的距离最大者，加大 了合并后的类与其他类的距离。

a 定义 ：主成分分析（Principal Component Analysis，简记 PCA）是将 多个指标化为少数几个综合指标的一种统计分析方法 ，通常我们把转化成的综合指标称为主成分。

b 本质：降维

c 表达 ：主成分为原始变量的线性组合
d 即信息量在空间降维以后信息量没有发生改变，所有主成分的方差之和与原始的方差之和

e 多个变量之间有一定的相关性，利用原始变量 的线性组合形成几个综合指标（主成分），在保留原始变量主要信息的前提下起到降维与简化问题的作用。

f 累积贡献率一般是 85% 以上

（1）每一个主成分都是各 原始变量的线性组合
（2）主成分的数目大大少于原始变量的数目
（3）主成分保留了原始变量绝大多数信息
（4）各主成分之间 互不相关

a 基本目的：用 少数几个综合因子去描述多个随机变量之间的相关关系 。
b 定义：多个变量————少数综合因子（不存在的因子）
c 显在变量：原始变量X；潜在变量：因子F
d X=AF+e公共因子+特殊因子
e 应用： 因子分析主要用于相关性很强的多指标数据的降维处理。
f 通过研究原始变量相关矩阵内部 的依赖关系，把一些具有错综复杂关系的变量归结为少数几个综合因子的一种多变量统计分析方法。
g 定义：原始的变量是可观测的显在变量，而 综合 的因子是 不可观测 的 潜在变量 ，称为因子。

i 根据相关性大小把原始变量分组，使得同组内的变量之间相关性较高，而不同组的变量间的相关性则较低。
ii 公共因子 ：每组变量代表一个基本结构，并用一个不可观测的综合变量表示。
iii 对于所研究的某一具体问题，原始变量分解成两部分：

i R 型因子分析——研究变量之间的相关关系
ii Q 型因子分析——研究样品之间的相关关系

a 因子载荷 是第i个变量与第j个公共因子的相关系数，绝对值越大，相关的密切程度越高。

a 变量 Xi 的共同度是因子载荷矩阵的第i行的元素的平方和。记为

b 所有的公共因子与特殊因子对变量 Xi 的贡献和为1。

a 确定因子载荷
b 因子旋转
c 计算因子得分

a 寻找简单结构的载荷矩阵：载荷矩阵A的所有元素都接 近0或±1，则模型的公共因子就易于解释。
b 如果各主因子的典型代表变量不突出，就需要进行旋转使因子载荷矩阵中载荷的绝对值向0和1两个方向分化。

a意义：对公共因子作正交旋转相当于对载荷矩阵 A 作一正交变换 ，右乘正交矩阵 T ，使 A = AT 能有更鲜明的实际意义。
b几何意义：是在 m 维空间上对原因子轴作一刚性旋转。 因子旋转不改变公共因子的共同度，这是因为 A A '=ATT'A'=AA'
c 旋转方法有：正交旋转和斜交旋转
d 最普遍的是： 最大方差旋转法

a 定义：通过坐标变换使各个因子载荷的方差之和最大。
b 任何一个变量只在一个因子上有高贡献率，而在 其它因子上的载荷几乎为0；
c 任何一个因子只在少数变量上有高载荷,而在其 它变量上的载荷几乎为0。

思想相同： 降维
前提条件：各变量间必须有 相关性 ，否则各变量之间没有共享信息

无监督学习（Unsupervised learning） ：训练样本的标记信息是未知的，目标是为了揭露训练样本的内在属性，结构和信息，为进一步的数据挖掘提供基础。

· 聚类（clustering）

· 降维（dimensionality reduction）

· 异常检测（outlier detection）

· 推荐系统（recommendation system）

监督学习（supervised learning） ：训练样本带有信息标记，利用已有的训练样本信息学习数据的规律预测未知的新样本标签

· 回归分析（regression）

· 分类（classification）

聚类 ：物以类聚。按照某一个特定的标准（比如距离），把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不再同一个簇内的数据对象的差异性也尽可能的大。

簇 （或类cluster）：子集合。最大化簇内的相似性；最小化簇与簇之间的相似性。

聚类可以作为一个单独过程，用于寻找数据内在分布结构，也可以作为其他学习任务前驱过程。

聚类和分类的区别：聚类是无监督学习任务，不知道真实的样本标记，只把相似度搞得样本聚合在一起；分类是监督学习任务，利用已知的样本标记训练学习器预测未知样本的类别。

聚类相似度度量： 几何距离

几种距离度量方法：

· 欧式距离（Euclidean distance）:p=2的Minkowski距离， 

· Minkowoski距离：

  · 曼哈顿距离 （Manhattan distance）:p=1的Minkowski距离 

· 夹角余弦 ：

` 相关系数 （Pearson correlation coefficient）： ,等式右面的x其实是 （x方向的均值），y其实是 （y方向的均值）,对于这个表达式很不友好，所以在此说明一下。

聚类类别：

· 基于划分的聚类（partitioning based clustering）：k均值（K-means）, Mean shift

· 层次聚类（hierarchical clustering）：Agglomerative clustering, BIRCH

· 密度聚类（density based clustering）：DBSCAN

· 基于模型的聚类（model based clustering）：高斯混合模型（GMM）

· Affinity propagation

 · Spectral clustering

聚类原理：

划分聚类（partition based clustering）：给定包含N个点的数据集，划分法将构造K个分组；每个分组代表一个聚类，这里每个分组至少包含一个数据点，每个数据点属于且只属于一个分组；对于给定的K值，算法先给出一个初始化的分组方法，然后通过反复迭代的的方法改变分组，知道准则函数收敛。

K均值算法（Kmeans）:

` 给定样本集：D={ , }, k均值算法针对聚类所得簇：C={ , }

` 最小化平方差： ,其中：  簇 的质心，上面的2代表平方，下面的2代表范数2

具体的K均值算法过程 ：

1 随机选择K个对子女给，每个对象出事地代表了一个簇的质心，即选择K个初始质心；2 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；3 重新计算每个簇的平均值。这个过程不断重复，直到准则函数（误差的平方和SSE作为全局的目标函数）收敛，直到质心不发生明显的变化。

初始质心优化:Kmeans++：

输入：样本集D={ , } 聚类簇的数量K

选取初始质心的过程：

1 随机从m个样本点中选择一个样本作为第一个簇的质心C1；2 计算所有的样本点到质心C1的距离： ;3 从每个点的概率分布  中随机选取一个点作为第二个质心C2。离C1越远的点，被选择的概率越大；4 重新计算所有样本点到质心的距离；5 重复上述过程，直到初始的K个质心被选择完成  ；按照Kmeans的算法步骤完成聚类。

输出：C= { , }

K均值算法（Kmean）的优缺点 ：

优点：1 简单直观，抑郁理解实现；2 复杂度相对比较低，在K不是很大的情况下，Kmeans的计算时间相对很短；3 Kmean会产生紧密度比较高的簇，反映了簇内样本围绕质心的紧密程度的一种算法。

缺点：1 很难预测到准确的簇的数目；2 对初始值设置很敏感（Kmeans++）；3 Kmeans主要发现圆形或者球形簇，对不同形状和密度的簇效果不好；4 Kmeans对噪声和离群值非常敏感（Kmeadians对噪声和离群值不敏感）

层次聚类（hierarchical clustering） ：

· 主要在不同层次对数据集进行逐层分解，直到满足某种条件为止；

· 先计算样本之间的距离。每次将距离最近的点合并到同一个类，然后再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成一个类。

· 自底向上（bottom-up）和自顶向下（top-down）两种方法：

top-down： 一开始每个个体都是一个初始的类，然后根据类与类之间的链接（linkage）寻找同类，最后形成一个最终的簇

bottom-up：一开始所有样本都属于一个大类，然后根据类与类之间的链接排除异己，打到聚类的目的。

类与类距离的计算方法 ：

最短距离法，最长距离法，中间距离法，平均距离法

最小距离：

最大距离：

平均距离：

单链接（single-linkage）:根据最小距离算法

全连接（complete-linkage）：根据最大距离算法

均链接（average-linkage）：根据平均距离算法

凝聚层次聚类具体算法流程：

1 给定样本集，决定聚类簇距离度量函数以及聚类簇数目k；2 将每个样本看作一类，计算两两之间的距离；3 将距离最小的两个类合并成一个心类；4重新计算心类与所有类之间的距离；5 重复（3-4），知道达到所需要的簇的数目

层次聚类的优缺点：

优点：1可以得到任意形状的簇，没有Kmeans对形状上的限制；2 可以发现类之间的层次关系；3不要制定簇的数目

缺点：1 通常来说，计算复杂度高（很多merge/split）；2噪声对层次聚类也会产生很大影响；3不适合打样本的聚类

密度聚类（density based clustering） :

  ` 基于密度的 方法的特点是不依赖于距离，而是依赖于密度，从而客服k均值只能发现“球形”聚簇的缺点

· 核心思想：只要一个区域中点的密度大于某个阈值，就把它加到与之相近的聚类中去

· 密度算法从样本密度的角度来考察样本的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果

· 对噪声和离群值的处理有效

· 经典算法：DBSCAN（density based spatial clutering of applications with noise）

DBSCAN 基于近邻域（neighborhood）参数（ ）刻画样本分布的 紧密程度的一种算法。

基本概念：

· 样本集： D={ }

` 阈值： 

·  ：对样本点 的 包括样本集中与 距离不大于 的样本

· 核心对象（core object）：如果 的 至少包含MinPts个样本，那么 就是一个核心对象 ,

假设MinPts=3,虚线标识为

·密度直达（directly density-reachable）:如果 位于 的 中，并且 是和新对象，那么 由 密度直达

· 密度可达（density-reachable）：对 ,如果存在一串样本点p1,p2pn =  ，pn =  ,且 由

` 密度直达,则称 由 密度可达

· 密度相连：存在样本集合中一点o,如果 和 均由O密度可达，那么 和 密度相连

上图中： 是核心对象，那么从 出发， 由 密度直达； 由 密度可达； 与 密度相连。

DBSCAN算法的过程：

1 首先根据邻域参数（ ）确定样本集合D中所有的核心对象，存在集合P中。加入集合P的条件为 有不少于MinPts的样本数。

2 然后从核心对象集合P中任意选取一个核心对象作为初始点，找出其密度可达的样本生成聚类簇，构成第一个聚类簇C1。

3 将C1内多有核心对象从P中去除，再从更新后的核心对象集合任意选取下一个种子样本。

4 重复（2-3），直到核心对象被全部选择完，也就是P为空集。

聚类算法总结：

基于划分的聚类：K均值（kmeans），kmeans++

层次聚类：Agglomerative聚类

密度聚类：DBSCAN

基于模型 的聚类：高斯混合模型（GMM）,这篇博客里咩有介绍

虽然稀里糊涂，但是先跟下来再说吧：

---