聚类分析（Cluster Analysis）

（一）什么是聚类

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

（二）聚类的基本思想：

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

（三）聚类的应用

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

---

（四）聚类的对象

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

image.png

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

---

（五）数据标准化

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

image.png
这种标准化方法所得到的的新数据满足： image.png
（2）标准差标准化，即： image.png
这种标准化方法得到的新数据，各指标的平均值为0，标准差为1，即有： image.png
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

---

image.png 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"