聚类分析（Cluster Analysis）

（一）什么是聚类

聚类，将相似的事物聚集在一起，将不相似的事物划分到不同的类别的过程。是将复杂数据简化为少数类别的一种手段。

（二）聚类的基本思想：

有大量的样本。
假定研究的样本之间存在程度不同的相似性，可以分为几类；相同类别的样本相似度高，不同类别的样本相似度差。
用一些数据指标来描述样本的若干属性，构成向量。
用某种方法度量样本之间或者类别之间的相似性（或称距离），依据距离来进行分类。
根据分类来研究各类样本的共性，找出规律。

（三）聚类的应用

商业领域-识别顾客购买模式，预测下一次购买行为，淘宝商品推荐等。
金融领域-股票市场板块分析
安全和军事领域
- 破解GPS伪随机干扰码和北斗系统民用版的展频编码密码
- 识别论坛马甲和僵尸粉
- 追溯网络谣言的源头
生物领域
- 进化树构建
- 实验对象的分类
- 大规模组学数据的挖掘
- 临床诊断标准
机器学习
- 人工智能

（四）聚类的对象

设有m个样本单位，每个样本测的n项指标（变量），原始资料矩阵：

image.png

指标的选择非常重要：
必要性要求：和聚类分析的目的密切相关，并不是越多越好
代表性要求：反映要分类变量的特征
区分度要求：在不同研究对象类别上的值有明显的差异
独立性要求：变量之间不能高度相关（儿童生长身高和体重非常相关）
散布性要求：最好在值域范围内分布不太集中

（五）数据标准化

在各种标准量度值scale差异过大时，或数据不符合正态分布时，可能需要进行数据标准化。
（1） 总和标准化。分别求出各聚类指标所对应的数据的总和，以各指标的数据除以该指标的数据的总和。

image.png

这种标准化方法所得到的的新数据满足：

image.png

（2）标准差标准化，即：

image.png

这种标准化方法得到的新数据，各指标的平均值为0，标准差为1，即有：

image.png

PS：比如说大家的身高差异
（3）极大值标准差
经过这种标准化所得到的新数据，各指标的极大值为1，其余各数值小于1.

image.png

PS：课程难易，成绩高低。
（4）极差的标准化：

image.png

经过这种标准化所得到的新数据，各指标的极大值为1，极小值为0，其余的数值均在0与1之间。
PS：高考算标准分。

（六）聚类的分类：

根据聚类对象的不同，分为Q型聚类，R型聚类

Q型聚类：样本之间的聚类即Q型聚类分析，常用距离来测度样本之间的亲疏程度
- 闵可夫斯基距离
- 马氏距离
- 文本距离
- 秩距离
R型聚类：变量之间的聚类即R型聚类分析，常用相似性系数来测度变量之间的亲疏程度
- 相关系数
- 夹角余弦

（1）常见距离统计量 - 闵可夫斯基距离系列（线性距离）

image.jpeg

p=1，时为曼哈顿距离（出租车距离）

image.png

p=2，时为欧氏距离（n维空间中的几何距离）
p=∞，时为切比雪夫距离（棋盘格距离）

image.jpeg

（2）常见距离统计量 - 马氏距离（协方差距离）
均值为μ，协方差矩阵为∑的向量x=(1,2,...n)
相比于欧式距离，马氏距离考虑到各种指标之间的联系（如身高和体重并不独立，）且马氏距离具有尺度无关性（scale-invariant），因此可不必做标准化。
如果协方差矩阵为单位矩阵（各指标之间完全相互独立），则马氏距离化为欧几里得距离。
如果协方差矩阵为对角矩阵，则马氏距离化为正规化的欧几里得距离（normalized Euclidean distance）

（3）常见距离统计量 - 文本距离
文本距离通常用来度量文本之间的相似度，在生物研究中常见于序列比对分析。

Hamming distance: 汉明距离，两个等长字符串之间直接逐位比较，有多少位不同。
缺点：必须要两个等长的字符串
Levenshtein distance：编辑距离，两个字符串之间，从一个字符串出发进行多少次的修正（每次一个字符串的替换，插入或删除）可以得到第二个字符串。求解过程类似于Needleman-Wunsch 算法中的搜索和回溯过程。
（4）常见距离统计量 - 秩距离
序列型变量需要用秩（rank）的概念来计算距离
例如：选美大赛时有ABCDE五名参赛选手，评委需要对其表现作出排名。这个排名就称为“秩”（rank）。
将每个变量的值域（上例中为[1,5]）映射到[0,1]范围上
然后用前述某种距离计算方法来计算距离

常见相似系数统计量
相似系数= 1，表明完全相似
相似系数= -1 表明完全相反
相似系数 = 0 表明完全独立
相关系数：

image.png

回归的时候要算相关系数，
夹角余弦：

image.png

类与类之间距离的度量方法：
系统聚类法不仅需要度量个体与个体之间的距离，还要度量类与类之间的距离。类间距离被度量出来之后，距离最小的两个小类将首先被合并成为一类。由类间距离定义的不同产生了不同的系统聚类法。

最短距离法(Nearest Neighbor)
- 以两类中距离最近的两个个体之间的距离作为类间距离
最长距离法（Further Neighbor)
- 以两类中距离最远的两个个体之间的距离作为类间距离
组间平均连接法（Between-group linkage，UPGMA）
- 以两类个体两两之间的距离的平均数作为类间距离。
组内平均连接法（Within-group linkage）
- 将两类个体合并为一类后，以合并后类中所有个体之间的平均距离作为类间距离
重心法（Centroid clustering）
- 以两类变量均值（重心）之间的距离作为类间距。
中位数法（Median clustering）
- 以两类变量中位数之间的距离作为类间距离
离差平方和法（Ward’s method）
- Ward方法并类时总是使得并类导致的类内离差平方和增量最小。仅能用于欧氏距离。
  
  image.png

聚类算法的分类：

目前有1000多种聚类算法：没有一种聚类算法可以包打天下，聚类算法中的各种参数也必须依据具体问题而调节
常见聚类算法的分类：
1，层次聚类（Hierarchical clustering）
2，划分聚类（Partitioning clustering）
3，密度聚类（Density-based）
4，期望最大化聚类（Expectation Maximization）
5，网格聚类（Grid-based）
6，模型聚类（Model-based）

1. 层次聚类的方法
基本思想：
在聚类分析的开始，每个样本（或变量）自成一类；然后，按照某种方法度量所有样本（或变量）之间的亲疏程度，并把最相似的样本（或变量）首先聚成一小类；接下来，度量剩余的样本（或变量）和小类间的亲疏程度，并将当前最接近的样本（或变量）与小类聚成一类；如此反复，知道所有样本聚成一类为止。
举例：
有一组数据D={a,b,c,d,e} 给了它们之间的距离矩阵。
首先，每一个例子都是一个类：

image.jpeg

将最近的两个类合并为一个新的类，并重新计算类之间的距离然后更新距离矩阵：
d(a,b)=0.18距离最近，合并为一类ab,然后计算ab,c,d,e之间的距离

image.jpeg

选择距离最近的两个类合并为新的类：
[图片上传失败...(image-62f70-1573443086632)] 距离最近，因此d,e合并为一类

image.jpeg

不断重复上述两个步骤，最终只剩下一个类的时候，停止：

image.jpeg

类别的数量取决于你剪的位置
层次聚类中，通常用组间平均连接法（UPGMA)和离差平方和法（Ward）比较稳健。
层次聚类的优缺点：

适用于大多数情况，稳健性比较好
易于生成系统发育树，分类类数可以随意选取
计算量大（两两计算距离）
需要仔细选择距离计算方法和组间距离计算方法

2. 划分聚类的方法
划分聚类算法：
给定一个包含n个样本的数据集，基于划分的方法（Partitioning Method）就是将n个样本按照特定的度量划分为k个簇（k≤n），使得每个簇至少包含一个对象，并且每个对象属于且仅属于一个簇，而且簇之间不存在层次关系。

基于划分的方法大多数是基于距离来划分的，首先对样本进行初始化分，然后计算样本间的距离，重新对数据集中的样本进行划分，将样本划分到距离更近的簇中，得到一个新的样本划分，迭代计算直到聚类结果满足用户指定的要求。

要想得到最优的聚类结果，算法需要穷举数据集所有可能的划分情况，但是在实际应用中数据量都比较大，利用穷举方法聚类显然是不现实的，因此大部分基于划分的聚类方法采用贪心策略，即在每一次划分过程中寻求最优解，然后基于最优解进行迭代计算，逐步提高聚类结果的质量。虽然这种方式有可能得到局部最优结果，但是结合效率方面考虑，也是可以接受的。

算法：

选择 K 个初始质心，初始质心随机选择即可，每一个质心为一个类
把每个观测指派到离它最近的质心，与质心形成新的类
重新计算每个类的质心，所谓质心就是一个类中的所有观测的平均向量（这里称为向量，是因为每一个观测都包含很多变量，所以我们把一个观测视为一个多维向量，维数由变量数决定）。
重复2. 和 3.
直到质心不在发生变化时或者到达最大迭代次数时

举例：
有一个二维空间的一些点，我们要将它们分成3个类，即K=3。

我们首先随机选择3个初始质心，每一个质心为一类：

image.jpeg

然后我们计算每一个不是质心的点到这三个质心的距离：

image.jpeg

将这些点归类于距离最近的那个质心的一类：

image.jpeg

重新计算这三个分类的质心：

image.jpeg

不断重复上述两步，更新三个类：

image.jpeg

当稳定以后，迭代停止，这时候的三个类就是我们得到的最后的三个：

image.jpeg

最著名的是k-means聚类算法和K-medoids算法（中心点聚类）

要求事先确定分类数
运算速度快（特别是对于大样本）
初始值敏感
对噪声和孤立数据点敏感
倾向于每一类别的样本数量相等，因此常出现错误

image.png

3. 基于密度的方法

处理“大海中的若干孤岛”，以密度来区分岛

大部分基于密度的方法（Density-based Method）采用距离度量来对数据集进行划分，在球状的数据集中能够正确划分，但是在非球状的数据集中则无法对样本进行正确聚类，并且受到数据集中的噪声数据影响较大。基于密度的方法可以克服这两个弱点。

基于密度的方法提出“密度”的思想，即给定邻域中样本点的数量，当邻域中密度达到或超过密度阈值时，将邻域内的样本包含到当前的簇中。若邻域的密度不满足阈值要求，则当前的簇划分完成，对下一个簇进行划分。基于密度的方法可以对数据集中的离群点进行检测和过滤。

算法：

从数据集中随机选择核心点
以一个核心点为圆心,做半径为V的圆,选择圆内圈入点的个数满足密度阈值的核心点,因此称这些点为核心对象,且将圈内的点形成一个簇,其中核心点直接密度可达周围的其他实心原点;
合并这些相互重合的簇

4. 基于网格的方法

基于网格的方法（Grid-based Method）将数据集空间划分为有限个网格单元，形成一个网络结构，在后续的聚类过程中，以网格单元为基本单位进行聚类，而不是以样本为单位。由于算法处理时间与样本数量无关，只与网格单元数量有关，因此这种方法在处理大数据集时效率很高。基于网格的方法可以在网格单元划分的基础上，与基于密度的方法、基于层次的方法等结合使用。

5. 基于模型的方法

基于模型的方法（Model-based Method）假定数据集满足一定的分布模型，找到这样的分布模型，就可以对数据集进行聚类。基于模型的方法主要包括基于统计和基于神经网络两大类，前者以高斯混合模型（Gaussian Mixture Models，GMM）为代表，后者以自组织映射网络（Self Organizing Map，SOM）为代表。目前以基于统计模型的方法为主。

聚类结果的解释和验证：

对每个类别进行命名
提取这一类别的共同特征，确定边界
进行验证
- 先对“训练集”进行聚类
- 然后用已知对象特性的“测试集”根据特征边界来将样本进行归类，检验特征边界的合理性
- 经过验证的聚类结果才可用于对未知样品的可靠分类（例如临床诊断）
解释分类形成的原因，提出可能的机制假说，进行更深入的研究

以下内容后续补充：

K-means算法的R实现：

数据示例：

x = rbind(matrix(rnorm(100,sd=0.3),ncol=2),matrix(rnorm(100,mean=1,sd=0.3),ncol=2))
cl = kmeans(x,2,20)
plot(x,col = cl$cluster,pch=3,lwd=1)

image.png

points(cl$centers,col=1:2,pch=7,lwd=3) # 画出中心点
segments(x[cl$cluster==1,][,1],x[cl$cluster==1,][,2],cl$centers[1,1],cl$centers[1,2]) # 画出每个点到中心点的连线。
segments(x[cl$cluster==2,][,1],x[cl$cluster==2,][,2],cl$centers[2,1],cl$centers[2,2],col=2)

image.png

层次聚类算法的R实现：

数据示例：

data("USArrests")
hc = hclust(dist(USArrests),"ave")
plot(hc,hang = -1)

image.png

解释说明

为了有效利用聚类算法，首先需要度量观测值见的距离，在R中常通过stats包里的dist函数来实现：
dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2)
dist 函数计算对象（矩阵或数据框）中两两间的距离，返回的是距离矩阵（dist类对象）。dist函数的参数描述如下。

dist参数	描述	默认值
x	用于计算矩阵的对象，可以使矩阵，数据框，dist对象
method	设置计算距离的方法：method="euclidean",计算欧氏距离（2-norm）；method="maximum"计算最大距离（supremum-norm）method="manhattan"计算绝对距离（1-norm）method="canberra" 计算兰氏距离 method="binary"将非0元素看作1，零看作0； method="minkowski" 计算闵式距离（p-norm）	euclidean
diag	逻辑值，控制是否打印距离矩阵的对角元素	FALSE
upper	逻辑值，控制是否打印上对角元素	FALSE
p	闵可夫斯基距离的范数	2

另一个计算点之间的距离的方法是cluster包里面的daisy函数：

daisy(x, metric = c("euclidean", "manhattan", "gower"),
      stand = FALSE, type = list(), weights = rep.int(1, p),
      warnBin = warnType, warnAsym = warnType, warnConst = warnType,
      warnType = TRUE)

daisy函数计算数据集中每对观测值的不相似度。daisy函数的参数描述如下：

daisy参数	描述	默认值
x	用于计算距离的数值型矩阵或数据框
metric	指定计算距离的方法：metric="duclidean"，计算欧氏距离；metric="manhattan"计算曼哈顿距离；metric="gower", 计算高氏距离；	euclidean
stand	逻辑值，计算距离前是否标准化化样本	FALSE
type	控制x中变量的类型。值为“ordratio”时，表示原始数据，“logratio”为对数变换，“assym”为非对称二元，“symm”为对称二元

k-means聚类是最简单的聚类算法之一。R中可以通过stats包里面的kmeans函数实现k-means聚类：
kmeans(x, centers, iter.max = 10, nstart = 1, algorithm = c("Hartigan-Wong", "Lloyd", "Forgy", "MacQueen"), trace=FALSE)
kmeans函数的参数描述如下：

参数	描述	默认值
x	用于聚类的数值型矩阵（或者可以转换成矩阵的对象）
centers	若是数值，则为簇的个数；若是数值向量，则为初始簇的中心
iter.max	最大迭代的次数（数值型）	10
nstart	如centers是数值，则为随机抽取的数据集的个数	1
algorithm	用于聚类的算法，可选项包括algorithm="Hartigan-Wong",algorithm="Lloyd", algorithm="Forgy",algorithm="MacQueen"