多元统计学-聚类分析

参考：

1.应用统计学与R语言实现学习笔记（十）——聚类分析)
2.厦门大学-多元统计分析
3.DBSCAN 密度聚类法
4.四大聚类算法（KNN、Kmeans、密度聚类、层次聚类）

---

俗话说，物以类聚，人以群分。聚类在日常生活中，非常常见.
就是将相似的物体，放在一起.

image.png

聚类分析概述：

聚类的目的——根据已知数据（ 一批观察个体的许多观测指标） ， 按照一定的数学公式计算各观察个体或变量（指标）之间亲疏关系的统计量（距离或相关系数等）。 根据某种准则（ 最短距离法、最长距离法、中间距离法、重心法等），使同一类内的差别较小，而类与类之间的差别较大，最终将观察个体或变量分为若干类。

根据分类的对象可将聚类分析分为：

• Q型——样品聚类clustering for individuals；
• R型——指标聚类clustering for variables。

样品间亲疏程度的测度

研究样品或变量的亲疏程度的数量指标有两种，一种叫相似系数，性质越接近的变量或样品，它们的相似系数越接近于1，而彼此无关的变量或样品它们的相似系数则越接近于0，相似的为一类，不相似的为不同类；另一种叫距离，它是将每一个样品看作p维空间的一个点，并用某种度量测量点与点之间的距离，距离较近的归为一类，距离较远的点属于不同的类。

变量之间的聚类即R型聚类分析，常用相似系数来测度变量之间的亲疏程度。
而样品之间的聚类即Q型聚类分析，则常用距离来测度样品之间的亲疏程度。

距离

假使每个样品有p个变量，则每个样品都可以看成p维空间中的一个点， n个样品就是p维空间中的n个点，则第i样品与第j样品之间的距离可以进行计算。

如何衡量样本间这个距离？

几种常用方式度量：
欧式距离 L2（Euclidean distance）--- 常用
马氏距离（Mahalanobis distance）---协方差矩阵
Minkowski测度（ Minkowski metric）
Canberra测度（Canberra metric）

有了距离衡量度量，我们可以计算两两的距离，就得到距离矩阵~
比如：下面用dist 计算距离的方法

image.png image.png

详细描述：

• 明氏距离(Minkowski)
  明氏距离、欧氏距离、绝对距离、Chebychev距离。
  明氏距离主要有以下两个缺点
  明氏距离的值与各指标的量纲有关，而各指标计量单位的选择有一定的人为性和随意性，各变量计量单位的不同不仅使此距离的实际意义难以说清，而且，任何一个变量计量单位的改变都会使此距离的数值改变从而使该距离的数值依赖于各变量计量单位的选择。
  明氏距离的定义没有考虑各个变量之间的相关性和重要性。实际上，明氏距离是把各个变量都同等看待，将两个样品在各个变量上的离差简单地进行了综合。
• 兰氏距离(Lance & Williams)
  这是兰思和维廉姆斯(Lance & Williams)所给定的一种距离，这是一个自身标准化的量，由于它对大的奇异值不敏感，这样使得它特别适合于高度偏倚的数据。虽然这个距离有助于克服明氏距离的第一个缺点，但它也没有考虑指标之间的相关性。
• 马氏距离(Mahalanobis)
  这是印度著名统计学家马哈拉诺比斯(P.C． Mahalanobis)所定义的一种距离，里面包含了协方差矩阵，Σ表示观测变量之间的协方差短阵。在实践应用中，若总体协方差矩阵Σ未知，则可用样本协方差矩阵作为估计代替计算。马氏距离又称为广义欧氏距离。显然，马氏距离与上述各种距离的主要不同就是马氏距离考虑了观测变量之间的相关性。如果假定各变量之间相互独立，即观测变量的协方差矩阵是对角矩阵，则马氏距离就退化为用各个观测指标的标准差的倒数作为权数进行加权的欧氏距离。因此，马氏距离不仅考虑了观测变量之间的相关性，而且也考虑到了各个观测指标取值的差异程度。
• 斜交空间距离
  由于各变量之间往往存在着不同的相关关系，用正交空间的距离来计算样本间的距离易变形，所以可以采用斜交空间距离。当各变量之间不相关时，斜交空间退化为欧氏距离。
• 配合距离
  适用于分类变量，尤其是名义尺度变量。
  相似系数
  研究样品间的关系常用距离，研究指标间的关系常用相似系数。相似系数常用的有夹角余弦和相关系数。
• 夹角余弦(Cosine)
  夹角余弦是从向量集合的角度所定义的一种测度变量之间亲疏程度的相似系数。
• 相关系数是将数据标准化后的夹角余弦
  距离和相似系数选择的原则
  一般说来，同一批数据采用不同的亲疏测度指标，会得到不同的分类结果。产生不同结果的原因，主要是由于不同的亲疏测度指标所衡量的亲疏程度的实际意义不同，也就是说，不同的亲疏测度指标代表了不同意义上的亲疏程度。因此我们在进行聚类分析时，应注意亲疏测度指标的选择。通常，选择亲疏测度指标时，应注意遵循的基本原则主要有：所选择的亲疏测度指标在实际应用中应有明确的意义。如在经济变量分析中，常用相关系数表示经济变量之间的亲疏程度。适当地考虑计算工作量的大小。如对大样本的聚类问题，不适宜选择斜交空间距离，因采用该距离处理时，计算工作量太大。
  亲疏测度指标的选择要综合考虑已对样本观测数据实施了的变换方法和将要采用的聚类分析方法。如在标准化变换之下，夹角余弦实际上就是相关系数；又如若在进行聚类分析之前已经对变量的相关性作了处理，则通常就可采用欧氏距离，而不必选用斜交空间距离。此外，所选择的亲疏测度指标，还须和所选用的聚类分析方法一致。如聚类方法若选用离差平方和法，则距离只能选用欧氏距离。
  样品间或变量间亲疏测度指标的选择是一个比较复杂且带主观性的问题，我们应根据研究对象的特点作具体分析，以选择出合适的亲疏测度指标。实践中，在开始进行聚类分析时，不妨试探性地多选择几个亲疏测度指标，分别进行聚类，然后对聚类分析的结果进行对比分析，以确定出合适的亲疏测度指标。

---

层次聚类：

1.定义样本聚类：

定义了距离之后，怎样找到"合理"的规则，使相似的/距离小的个体聚成一个族群？

考虑所有的群组组合显然在计算上很难实现，所以一种常用的聚类方法为层次聚类/系统聚类（hierarchical
clustering）

• 层次聚类有两个方向进行聚类：
  凝聚法（Agglomerative clustering）：由单个个体开始，逐步将最“相似”的个体连结起来，直到所有个体都合并为一个族群。

• 分离层次法（Divisive clustering）：凝聚法的相反方向

• 最终可以绘制出系统发育树，进行展现相关性.
  系统树图显示了层次聚类的每一个步骤及其结果，包括合并族群带来的距离的变化

image.png

2.如何定义族群合并的规则（类与类之间的距离）

从系统树图中可以看出，我们需要度量族群与族群之间的距离，不同的定义方法决定了不同的聚类结果：

image.png

• 简单连接（Single linkage）/最近邻方法（Nearest neighbor method） 定义族群间的距离为两族群中相隔最近的两个体间的距离. 每一次合并最近的两个族群. 如下图：不同城市聚类结果.

image.png

• 完全连接（Complete linkage）/最远邻方法（Farthest neighbor method）中，以两组别中最远个体之间的距离来定义族群之间的距离.

image.png

• 平均连接法（Average linkage）中，两族群之间的距离定义为个A集合点和 个B集合点产生的所有 个距离数值的平均.

image

计算族群距离的三种方法的比较：

image.png

• 质心法（Centroid method）中，两族群的距离定义为两族群各自的质心（Centroid），即样本均值向量，之间的欧式距离. 注意可能出现系统树交叉情况

  image.png

Tips:

• 如果两个族群合并之后，下一步合并时的最小距离反而减小，我们则称这种情况为倒置（Reversal/Inversion），在系统树图中表现为交叉（Crossover）现象.
• 在一些层次聚类方法中，如简单连接、完全连接和平均连接，倒置不可能发生，这些距离的度量是单调的（monotonic）,每一次抽取最近的族群进行合并，所以下一步计算的距离会越来越大.
• 显然质心方法并不是单调的，每一个都会重新计算中心位点.

• Ward法（Ward’s method）/方差平方和增量法（Incremental sum of squares） 由合并前后的族群内方差平方和的差异定义距离. 将哪些族群合并后，方差增加的最小. 当距离很远的族群，合并后方差增加很大.

（可以看到都是小小的族群合并在一起，因为让方差增加最小，倾向与合并小群体）

image.png

其他：

• 最短距离法
• 最长距离法
• 中间距离法
• 可变方法
• 重心法
• 类平均方法
• 可变类平均法
• 离差平方和法
  类似于方差分析的想法，如果类分得恰当，同类内的样品之间的离差平方和应较小，而类间的离差平方和应当较大。当k固定时，选择使SST达到最小的分类。分类可能指数级增长，寻找最优难以完成。离差平方和法的思路：先让n个样品各自成一类，然后缩小一类，每缩小一类离差平方和就要增大，选择使SST增加最小的两类合并，直到所有的样品归为一类为止（局部最优）。
  以上聚类方法的计算步骤完全相同，仅类与类之间距离的定义不同。 Lance和Williams于1967年将其统一成对应的形式。

3.聚完后，如何确定聚类数呢？

一般情况，我们得到系统树，需要对树进行切割. 如下图一条条竖线.

image.png

层次聚类族群数的选择：

• 有时族群个数可根据经验或合理的业务解释预先设定
• 如果由数据驱动，在层次聚类中，可以从系统树图中于给定距离水平下“切分”树图得到 个族群
• 我们希望确定 的值来最好地拟合数据，一种方法是寻找合并组别时较大的距离变化的节点

层次聚类总结：

1、建立n个初始族群，每个族群中只有一个个体
2、计算n个族群间的距离矩阵
3、合并距离最小的两个族群
4、计算新族群间的距离矩阵。如果组别数为1，转步骤5；否则转步骤3
5、绘制系统树图
6、选择族群个数

---

Kmeans 聚类

1.动机:

• 层次聚类有什么缺陷？

在层次聚类中，一旦个体被分入一个族群，它将不可再被归入另一个族群,故现在介绍一个“非层次”的聚类方法——分割法（Partition）。最常用的分割法是k-均值（k-Means）法

k-均值法试图寻找 个族群 的划分方式，使得划分后的族群内方差和（within-group sum of squares，WGSS）最小.

image.png

思路也是将相近的样本,聚在一起，使得组内方差小，组间方差大.

image.png

2.k-means 步骤：

① 选定 个“种子”（Cluster seeds）作为初始族群代表
② 每个个体归入距离其最近的种子所在的族群
③ 归类完成后，将新产生的族群的质心定为新的种子
④ 重复步骤2和3，直到不再需要移动
⑤ 选择不同的k 值，计算WGSS,找到拐点确定最合适的K.

image.png

3.如何选取k个种子具体位置？

有多种初始种子的选取方法可供选择：
1、在相互间隔超过某指定最小距离的前提下，随机选择k个个体
2、选择数据集前k个相互间隔超过某指定最小距离的个体
3、选择k个相互距离最远的个体
4、选择k个等距网格点（Grid points），这些点可能不是数据集的点

• 下面列举k=3,两种初始seed选取的实例：

可以想到，左侧的点收敛更快得到全局最优；左侧可能聚类效果一般，或者收敛非常慢，得到局部最优.

image.png

4.如何确定划分的k值？

我们的目标是使得WGSS足够小，是否应该选取k使得WGSS最小？

image.png

我们需要选择一个使得WGSS足够小（但不是最小）的k值.（PS: 族群内方差和最小时候，k=n,此时WGSS为0，此时是过拟合问题~）

当我们分部计算k=1,2,3,4,5... 时候，WGSS值，就可以绘制下面碎石图。及WGSS 随着k 变化过程。k 越大，WGSS越小.

image.png

• 我们可以用WGSS的碎石图来寻找最优的k，通常选取拐点(knee point)为最优的k.
• 注意与主成分分析和因子分析选取特征值个数的区别（PCA中选取拐点前一个点，作为主成分个数.）
• 图中建议选择 k=3

K-means 总结：

• k-均值法对初始种子的选择比较敏感。可尝试再不同的种子选择下多次进行聚类。如果不同的初始种子造成了聚类结果很大的不同，或是收敛的速度极其缓慢，也许说明数据可能原本并不存在天然的族群.
• k-均值法也可以作为层次聚类的一种改进。 我们首先用层次聚类法聚类，以各族群的质心作为k-均值法的初始种子；这样就在层次聚类的基础上，使得个体有被重新分配到其他族群的机会.