聚类分析 cluster analysis

聚类分析方法是按样品（或变量）的数据特征，把相似的样品（或变量）倾向于分在同一类中，把不相似的样品（或变量）倾向于分在不同类中。聚类分析根据分类对象不同分为Q型和R型聚类分析

在聚类分析过程中类的个数如何来确定才合适呢？这是一个十分困难的问题，人们至今仍未找到令人满意的方法。但是这个问题又是不可回避的。下面我们介绍几种方法。 1、给定阈值——通过观测聚类图，给出一个合适的阈值T。要求类与类之间的距离不要超过T值。例如我们给定T=0.35，当聚类时，类间的距离已经超过了0.35，则聚类结束。

聚类分析的出发点是研究对象之间可能存在的相似性和亲疏关系。

样品间亲疏程度的测度

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

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

定义：在聚类分析中反映样品或变量间关系亲疏程度的统计量称为聚类统计量，常用的聚类统计量分为距离和相似系数两种。距离：用于对样品的聚类。常用欧氏距离，在求距离前，需把指标进行标准化。相似系数：常用于对变量的聚类。一般采用相关系数。相似性度量：距离和相似系数。距离常用来度量样品之间的相似性，相似系数常用来度量变量之间的相似性。样品之间的距离和相似系数有着各种不同的定义，而这些定义与变量的类型有着非常密切的关系。

距离和相似系数这两个概念反映了样品（或变量）之间的相似程度。相似程度越高，一般两个样品（或变量）间的距离就越小或相似系数的绝对值就越大；反之，相似程度越低，一般两个样品（或变量）间的距离就越大或相似系数的绝对值就越小。

一、变量测量尺度的类型为了将样本进行分类，就需要研究样品之间的关系；而为了将变量进行分类，就需要研究变量之间的关系。但无论是样品之间的关系，还是变量之间的关系，都是用变量来描述的，变量的类型不同，描述方法也就不同。通常，变量按照测量它们的尺度不同，可以分为三类。 (1)间隔尺度。指标度量时用数量来表示，其数值由测量或计数、统计得到，如长度、重量、收入、支出等。一般来说，计数得到的数量是离散数量，测量得到的数量是连续数量。在间隔尺度中如果存在绝对零点，又称比例尺度。

(2)顺序尺度。指标度量时没有明确的数量表示，只有次序关系，或虽用数量表示，但相邻两数值之间的差距并不相等，它只表示一个有序状态序列。如评价酒的味道，分成好、中、次三等，三等有次序关系，但没有数量表示。 (3)名义尺度。指标度量时既没有数量表示也没有次序关系，只有一些特性状态，如眼睛的颜色，化学中催化剂的种类等。在名义尺度中只取两种特性状态的变量是很重要的，如电路的开和关，天气的有雨和无雨，人口性别的男和女，医疗诊断中的“十”和“一”，市场交易中的买和卖等都是此类变量。

数据的变换处理所谓数据变换，就是将原始数据矩阵中的每个元素，按照某种特定的运算把它变成为一个新值，而且数值的变化不依赖于原始数据集合中其它数据的新值。 1、中心化变换中心化变换是一种坐标轴平移处理方法，它是先求出每个变量的样本平均值，再从原始数据中减去该变量的均值，就得到中心化变换后的数据。设原始观测数据矩阵为：

中心化变换的结果是使每列数据之和均为0，即每个变量的均值为0，而且每列数据的平方和是该列变量样本方差的(n—1)倍，任何不同两列数据之交叉乘积是这两列变量样本协方差的(n—1)倍，所以这是一种很方便地计算方差与协方差的变换。2、极差规格化变换规格化变换是从数据矩阵的每一个变量中找出其最大值和最小值，这两者之差称为极差，然后从每个变量的每个原始数据中减去该变量中的最小值，再除以极差，就得到规格化数据。即有：经过规格化变换后，数据矩阵中每列即每个变量的最大数值为1，最小数值为0，其余数据取值均在0－1之间；并且变换后的数据都不再具有量纲，便于不同的变量之间的比较。3、标准化变换标准化变换也是对变量的数值和量纲进行类似于规格化变换的一种数据处理方法。首先对每个变量进行中心化变换，然后用该变量的标准差进行标准化。即有：

经过标准化变换处理后，每个变量即数据矩阵中每列数据的平均值为0，方差为1，且也不再具有量纲，同样也便于不同变量之间的比较。变换后，数据短阵中任何两列数据乘积之和是两个变量相关系数的（n－1）倍，所以这是一种很方便地计算相关矩阵的变换。 4．对数变换对数变换是将各个原始数据取对数，将原始数据的对数值作为变换后的新值。即：

  系统聚类法的算法

  1．取每个观察值为一个类；

  2．将性质最近的两个类合并为一个类，类的数目减1；

  3．如类的数目³2，转2）；

  4．结束聚类过程。

聚类分析可分为对变量聚类（如在儿童的生长发育研究中，把以形态学为主的指标归于一类，以机能为主的指标归于另一类等）和对样品聚类（如解剖学上依据骨骼的形状和大小等，不仅可以区别样品是人还是猿，还可以区别性别、年龄等）。

聚类分析的基本思想：是认为我们所研究的样本或指标（变量）之间存在着程度不同的相似性（亲疏关系）。于是根据一批样本的多个观测指标，具体找出一些彼此之间相似程度较大的样本（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样本（或指标）又聚合为另一类，关系密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到把所有样本（或指标）都聚合完毕，把不同的类型一一划分出来，形成一个由小到大的分类系统。最后把整个分类系统画成一张谱系图，用它把所有样本（或指标）间的亲疏关系表示出来。这种方法是最常用的、最基本的一种，称为系统聚类分析。

依据研究对象（样品或指标）的特征，对其进行分类的方法，减少研究对象的数目。

　　各类事物缺乏可靠的历史资料，无法确定共有多少类别，目的是将性质相近事物归入一类。

　　各指标之间具有一定的相关关系。

Q型（对样本的聚类分析）是对样本进行分类处理，其作用在于:

1.能利用多个变量对样本进行分类

2.分类结果直观，聚类谱系图能明确、清楚地表达其数值分类结果

3.所得结果比传统的定性分类方法更细致、全面、合理

R型（对指标变量的聚类分析）是对变量进行分类处理，其作用在于：

1.可以了解变量间及变量组合间的亲疏关系

2.可以根据变量的聚类结果及它们之间的关系，选择主要变量进行回归分析或Q型聚类分析

三、聚类过程

1.数据预处理（标准化）

2.构造关系矩阵（亲疏关系的描述）

3.聚类（根据不同方法进行分类）

4.确定最佳分类（类别数）

标准化：

1.为什么要做标准化：指标变量的量纲不同或数量级相差很大，为了使这些数据能放到一起加以比较，常需做变换。

2.相关说明：假设有N个样本1,2，…n，每个样本有m项指标x1,x2,…，xm,用xij表示第i个样品第j个指标的值，则可得到样品数据矩阵。

3. 常用方法 

1)Z Scores：标准化变换

作用：变换后的数据均值为0，标准差为1，消去了量纲的影响；当抽样样本改变时，它仍能保持相对稳定性。

2)Range –1 to 1：极差标准化变换

作用：变换后的数据均值为0，极差为1，且|xij*|<1，消去了量纲的影响；在以后的分析计算中可以减少误差的产生。

3)Maximum magnitude of 1

作用：变换后的数据最大值为1。

4)Range 0 to 1（极差正规化变换 / 规格化变换）

作用：变换后的数据最小为0，最大为1，其余在区间[0，1]内，极差为1，无量纲。

5)Mean of 1

作用：变换后的数据均值为1。

6)Standard  deviation  of  1

作用：变换后的数据标准差为1。

选择聚类方法：

对样本的聚类分析（Q型）：

一．系统聚类：Hierarchical Cluster也叫分层聚类法

系统聚类法的基本思想：令n个样品自成一类，计算出相似性测度，此时类间距离与样品间距离是等价的，把测度最小的两个类合并；然后按照某种聚类方法计算类间的距离，再按最小距离准则并类；这样每次减少一类，持续下去直到所有样品都归为一类为止。聚类过程可做成聚类谱系图(Hierarchical diagram)。

开始将个样品各自作为一类，并规定样品之间的距离和类与类之间的距离，然后将距离最近的两类合并成一个新类，计算新类与其他类的距离；重复进行两个最近类的合并，每次减少一类，直至所有的样品合并为一类。  系统聚类法是最常用的一种聚类方法，常用的系统聚类方法有最短距离法、最长距离法、中间距离法、类平均法、重心法、Ward最小方差法、密度估计法、两阶段密度估计法、最大似然估计法、相似分析法和可变类平均法。

大多数的研究表明：最好综合特性的聚类方法为类平均法或Ward最小方差法，而最差的则为最短距离法。Ward最小方差法倾向于寻找观察数相同的类。类平均法偏向寻找等方差的类。具有最小偏差的聚类方法为最短距离法和密度估计法。拉长的或无规则的类使用最短距离法比其他方法好。最没有偏见的聚类方法为密度估计法。

步骤：

s1.构造n个类，每个类包含且只包含一个样品。

s2.计算n个样品两两间的距离，构成距离矩阵，记作D0。

s3.合并距离最近的两类为一新类。

s4.计算新类与当前各类的距离。若类的个数等于1，转到步骤(5)，否则回到步骤(3)。

s5.画聚类图。

s6.决定类的个数，及各类包含的样品数，并对类作出解释。

方法：

1.类平均法(average)

例：

2.最短距离法(single linkage)

定义类与类之间的距离为两类最近样品间的距离，即

聚类步骤：

(1) 规定样品之间的距离，计算n个样品的距离矩阵D（0），它是一个对称矩阵。(2) 选择D（0）中的最小元素，设为，则将和合并成一个新类，记为，即(3) 计算新类与任一类之间距离的递推公式为

在D（0）中，和所在的行和列合并成一个新行新列，对应，该行列上的新距离值由（6.3.2）式求得，其余行列上的距离值不变，这样就得到新的距离矩阵，记作。

(4) 对重复上述对D（0）的两步得D（2），如此下去直至所有元素合并成一类为止。如果某一步D（m）中最小的元素不止一个，则称此现象为结(tie)，对应这些最小元素的类可以任选一对合并或同时合并。例：

3.最长距离法(complete linkage)

类与类之间的距离定义为两类最远样品间的距离，即

最长距离法与最短距离法的并类步骤完全相同，只是类间距离的递推公式有所不同。递推公式：最长距离法容易被异常值严重地扭曲，一个有效的方法是将这些异常值单独拿出来后再进行聚类。

4.中间距离法(median method)

类与类之间的距离既不取两类最近样品间的距离，也不取两类最远样品间的距离，而是取介于两者中间的距离。，

5.重心法(centroid)也称为样品的均值法

6.密度估计法（Density estimation method）

DBSCANDensity-Based Spatial Clustering of Applications with Noise

（一种基于密度聚类算法）

将簇定义为密度相连的点的最大结合，并且有较强的抗“噪声”能力。

（1） 基本定义

点的领域：已选定点为中心，以为半径的区域。

密度估计法是一类使用非参数概率密度的聚类方法。包括两个步骤：①使用一种基于密度估计的新的非相似测度来计算样品和的近邻关系；②然后根据基于方法计算的距离，采用最小距离法进行聚类。

有三种不同的密度估计法：

①        最近邻估计法

最近邻估计法（Wong和Lane 1983）使用最近邻密度估计来计算距离。令为点到第个最近观察的距离。考虑以点为中心为半径的封闭球，在点的密度估计函数等于球内的观察数目除以球的体积所得比值。这样，新的非相似测度距离为：

最近邻估计法适用于样品数目较多且密度较高的类。

②        均匀核估计法

均匀核估计使用了均匀核密度估计来计算距离。考虑以点为中心为半径的封闭球，在点的密度估计函数等于球内的观察数目除以球的体积所得比值。它与最近邻估计法的主要区别为半径是一个指定的值，即封闭球大小是一样的（均匀核）。这样，新的非相似测度距离为：

③        Wong混合法

Wong混合法初始聚类时采用最近邻估计法，得到初始分类、和，及也可从输入数据集得到类的均值、和，样品数、和。判断这三个初始分类中某二个初始分类是近邻的标准为：（假设判断类和）

那么，新的非相似测度距离为

其中，和是初始分类和的直径，计算公式见式(39.14)。为观察样品的变量维数。Wong混合法适用于大的数据集而不适用于小的数据集。

7.离差平方和法(Ward's Method)，即Ward法

其中Wm是由Gp和Gq合并成的Gm类的类内离差平方和。可以证明离差平方和的聚类公式为

离差平方和法的思路是，当k固定时，选择使S达到最小的分类。先让n个样品各自成一类，然后缩小一类，每缩小一类离差平方和就要增大，选择使S2增加最小的两类合并，直到所有的样品归为一类为止。离差平方和法定义类间的平方距离为

*可变距离法(flexible median)

*可变类平均法(flexible average)

类平均法的递推公式中，没有反映Gp类和Gq类的距离有多大，进一步将其改进，加入D2Pq，并给定系数 <1，则类平均法的递推公式改为：

用此递推公式进行聚类就是可变类平均法。递推公式由： p类和q类与L类的距离的加权平均数 p类和q类的距离两项的加权（eg：加权：p类和q类与L类的距离的加权平均数）和构成，β的大小根据哪项更重要而定。

*可变法(flexible median)

如果让中间距离法的递推公式前两项的系数也依赖于 ，则递推公式为：用上式作为递推公式的系统聚类法称为可变法。

*重心聚类法（Centroid clustering）

*中位数法（Median clustering）

二．动态聚类Dynamic Cluster Analysis快速聚类法quick cluster

逐步聚类、迭代聚类、K均值法

基本思想：开始将n个样品粗略地分成若干类，然后用某种最优准则进行调整，一次又一次地调整，直至不能调整了为止。此法非常类似于计算方法的迭代法。

基本思想是，选择一批凝聚点或给出一个初始的分类，让样品按某种原则向凝聚点凝聚，对凝聚点进行不断的修改或迭代，直至分类比较合理或迭代稳定为止。类的个数k可以事先指定，也可以在聚类过程中确定。选择初始凝聚点(或给出初始分类)的一种简单方法是采用随机抽选(或随机分割)样品的方法。

1.K均值法（K-means method）

快速聚类(k-means cluster)是一种基于迭代(iteration)算法的聚类方法，在数据量不大的情况下，不失为一种有效的方法。

    使用快速聚类，首先要确定凝聚中心，有几个凝聚中心，就得到几个类。凝聚中心有两种确定法：

  1．由系统根据数据情况和指定的类数，自动确定；

  2．人工输入。

k均值法的基本步骤：

(1) 选择k个样品作为初始凝聚点，或者将所有样品分成k个初始类，然后将这k个类的重心(均值)作为初始凝聚点。

(2) 对除凝聚点之外的所有样品逐个归类，将每个样品归入凝聚点离它最近的那个类（通常采用欧氏距离），该类的凝聚点更新为这一类目前的均值，直至所有样品都归了类。

(3) 重复步骤(2)，直至所有的样品都不能再分配为止

最终的聚类结果在一定程度上依赖于初始凝聚点或初始分类的选择。经验表明，聚类过程中的绝大多数重要变化均发生在第一次再分配中。也就是：先算各类的均值

再算各类中样本到本类及其他类的均值的绝对值距离（欧氏距离）

将样本重新归类到欧氏距离较小的类中（重新归类就得算均值）

对指标变量的聚类分析（R型）：

三．分割聚类varclus过程

基本思想：它的程序正好和系统聚类相反，开始时所有的样本都在一类，然后用某种最优准则将它分成两类。再用同样准则将这两类各自试图分裂为两类，从中选出一个使目标函数较好者，这样由两类变成了三类。如此下去，一直分裂到每类只有一个样品为止（或用其他停止规则）。

分割聚类的过程如下：

首先给出一个初始分类，然后重复以下步骤：(1)挑选一个欲分割的类，这个被分割的类的类内差异最大。(2)把选中的类分割成两个类。再根据某准测把此类中所有变量分别归入这两个类。这种分割过程一直进行下去，直至达到某种分割停止准则为止。

分割停止准则可为：(1) 已达到了用户指明的所期望分类的最大个数。可用MAXC=变量数。(2)每类类成份所能解释的方差所占比例都大于某指定值。(3)每类第二特征根均小于某指定值。第(2)和(3)意味着每个类别内各指标间的关系都很密切，不需要再进一步分割。PROC VARCLUS有很多选择项，但用缺省值通常就能够得出很好的结果，因而在一般情况下均使用缺省说明。

四．作变换dij= 1 - | rij |后采用系统聚类cluster过程（加入法？）

加入法基本思想：将样品依次输入，每次输入后将它放到当前聚类图的应有位置上，全部输入后，即得聚类图。

 ：

聚类分析的分类：

按聚类方法分：

系统聚类法，也叫分层聚类法，hierarchical cluster动态聚类法，也叫快速聚类法quick cluster逐步聚类、迭代聚类k-均值聚类 k-means cluster最优分割法（有序样品聚类法）模糊聚类法图论聚类法聚类预报法等

按聚合方式分：

聚合法: 分类开始时每个样品自成一类。最常用，分类结果常用分类谱系图表达。分裂法:分类开始将全部样品看成一类。通常只能是求局部最优解的方法。调优法: 首先对样品进行粗糙的分个类。动态聚类法就是其中最典型的方法。加入法:业已存在一个分类结果，确定每个新加入样品在分类结构中最合适的位置。等

按聚类对象分：

Q型聚类：对样品的聚类 (cases)R型聚类：对变量的聚类

聚类分析基础知识总结