【多元统计分析】16.聚类基础

统计分析】16.聚类基础"/>

【多元统计分析】16.聚类基础

文章目录

• 十六、聚类基础
• • 1.聚类概述
  • 2.样本间的距离
  • 3.变量相似度的度量
  • 4.类间距离
  • 回顾总结

十六、聚类基础

1.聚类概述

聚类与分类不同，在分类问题中，样本被给定了所属的类别，因此每个类别中的样本会有一些数字特征，基于此可以进行判别；聚类问题中每一个样本都是同等的、没有任何类别信息的个体，要根据样本自身的特征以及全部样本的分布特征，对全部样本进行划分。这里，依照什么标准划分、划分成几类效果最好，在聚类开始之前都是未知的。

聚类发挥作用依靠的是类的相似度，而类的相似度就需要以某种方法定义。

2.样本间的距离

类由一系列样本构成，最简单的类中只包含一个样本，因此，样本间的距离可以作为定义类间相似度的基础。现在我们假设样本 X ( i ) ∈ R m X_{(i)}\in \R^m X(i)​∈Rm一共有 n n n个。

我们最为熟知的距离是欧氏距离，但它其实是Minkowski距离的一种，现在给出Minkowski距离的定义。

Minkowski距离：定义 q q q阶Minkowski距离为
d i j ( q ) = [ ∑ t = 1 m ∣ x i t − x j t ∣ q ] 1 / q . d_{ij}(q)=\left[\sum_{t=1}^m|x_{it} -x_{jt}|^q \right]^{1/q}. dij​(q)=[t=1∑m​∣xit​−xjt​∣q]1/q.

Minkowski距离的具体形态与参数 q q q有关，当参数取不同值时，Minkowski距离表现为以下几种不同的形式：

1. q = 1 q=1 q=1时，表现为绝对值距离，即
   d i j ( 1 ) = ∑ t = 1 m ∣ x i t − x j t ∣ ; d_{ij}(1)=\sum_{t=1}^m |x_{it}-x_{jt}|; dij​(1)=t=1∑m​∣xit​−xjt​∣;

2. q = 2 q=2 q=2时，表现为Euclidean距离，即
   d i j ( 2 ) = ∑ t = 1 m ( x i t − x j t ) 2 ; d_{ij}(2)=\sqrt{\sum_{t=1}^m (x_{it}-x_{jt})^2}; dij​(2)=t=1∑m​(xit​−xjt​)2 ​;

3. q = ∞ q=\infty q=∞时，表现为Chebyshev距离，即
   d i j ( ∞ ) = lim ⁡ q → ∞ [ ∑ t = 1 m ∣ x i t − x j t ∣ q ] 1 / q = max ⁡ t ∣ x i t − x j t ∣ . d_{ij}(\infty)=\lim_{q\to \infty}\left[\sum_{t=1}^m|x_{it}-x_{jt}|^q \right]^{1/q}=\max_t|x_{it}-x_{jt}|. dij​(∞)=q→∞lim​[t=1∑m​∣xit​−xjt​∣q]1/q=tmax​∣xit​−xjt​∣.

其中，欧氏距离是我们最常用的距离，但它的显著缺陷是容易受量纲影响——如果有一个分量的数量级比较大，它对欧氏距离的影响就比较显著，这与属性间的平等性产生了冲突。为了避免这种情况，我们常常会对样本数据进行预处理。一般有以下几种预处理方式：

1. 中心化变换： x i t ∗ = x i t − x ˉ t x_{it}^*=x_{it}-\bar x_t xit∗​=xit​−xˉt​。经过中心化变换后数据阵的均值变为 0 ′ \boldsymbol 0' 0′，而协方差阵不变。

2. 标准化变换(scale)：
   x i t ∗ = x i t − x ˉ t s t t , s t t = 1 n − 1 ∑ l = 1 n ( x l t − x ˉ t ) 2 . x_{it}^*=\frac{x_{it}-\bar x_t}{s_{tt}},\quad s_{tt}=\frac1{n-1}\sum_{l=1}^n(x_{lt}-\bar x_t)^2. xit∗​=stt​xit​−xˉt​​,stt​=n−11​l=1∑n​(xlt​−xˉt​)2.
   经过标准化变换后，数据阵的均值变为 0 ′ \boldsymbol 0' 0′，协方差阵变为主对角线元素为1的对称阵，且去量纲化。

3. 极差标准化变换：
   x i t ∗ = x i t − x ˉ t R t , R t = max ⁡ i , j ∣ x i t − x j t ∣ . x_{it}^*=\frac{x_{it}-\bar x_t}{R_t},\quad R_t=\max_{i,j}|x_{it}-x_{jt}|. xit∗​=Rt​xit​−xˉt​​,Rt​=i,jmax​∣xit​−xjt​∣.
   经过极差标准化后，数据阵的均值变为 0 \boldsymbol 0 0，且 ∣ x i j ∗ ∣ < 1 |x_{ij}^*|<1 ∣xij∗​∣<1，去量纲化。

4. 极差正规化变换：
   x i t ∗ = x i t − min ⁡ j x j t R t , R t = max ⁡ i . j ∣ x i t − x j t ∣ . x_{it}^*=\frac{x_{it}-\min\limits_jx_{jt}}{R_t},\quad R_t=\max_{i.j}|x_{it}-x_{jt}|. xit∗​=Rt​xit​−jmin​xjt​​,Rt​=i.jmax​∣xit​−xjt​∣.
   经过极差正规化后，数据满足 0 ≤ ∣ x i j ∗ ∣ ≤ 1 0\le|x_{ij}^*|\le 1 0≤∣xij∗​∣≤1，极差为1，去量纲化。

5. 对数/多项式变换： x i t ∗ = ln ⁡ ( x i t ) x_{it}^*=\ln (x_{it}) xit∗​=ln(xit​)或 x i t ∗ = x i t 1 / n x_{it}^*=x_{it}^{1/n} xit∗​=xit1/n​，这种变换意在去除数据的指数特征或多项式特征。

如果要消除欧氏距离中，量纲对距离计算的影响，一般我们会使用标准化变换，将数据分布改为零均值标准方差的。

除此外，还有以下的几种距离定义方式：

1. 兰氏距离(Canberra)：定义为
   d i j ( L ) = 1 m ∑ t = 1 m ∣ x i t − x j t ∣ x i t + x j t . d_{ij}(L)=\frac 1m\sum_{t=1}^m\frac{|x_{it}-x_{jt}|}{x_{it}+x_{jt}}. dij​(L)=m1​t=1∑m​xit​+xjt​∣xit​−xjt​∣​.
   Canberra距离也是无量纲的，克服了Minkowski距离中与量纲有关的缺点。

2. 马氏距离(Mahalanobis)：定义为
   d i j ( M ) = ( X ( i ) − X ( j ) ) ′ S − 1 ( X ( i ) − X ( j ) ) . d_{ij}(M)=(X_{(i)}-X_{(j)})'S^{-1}(X_{(i)}-X_{(j)}). dij​(M)=(X(i)​−X(j)​)′S−1(X(i)​−X(j)​).
   这里 S S S是样本协方差阵，Mahalanobis距离不仅是无量纲的，且一定程度上克服了前面几种距离中没有考虑变量相关性的缺点。

3. 斜交空间距离：定义为
   d i j = [ 1 m 2 ∑ k = 1 m ∑ l = 1 m ( x i k − x j k ) ( x i l − x j l ) r k l ] 1 / 2 . d_{ij}=\left[\frac 1{m^2}\sum_{k=1}^m\sum_{l=1}^m(x_{ik}-x_{jk})(x_{il}-x_{jl})r_{kl} \right]^{1/2}. dij​=[m21​k=1∑m​l=1∑m​(xik​−xjk​)(xil​−xjl​)rkl​]1/2.
   这种距离定义方式克服了变量之间相关性的影响。

3.变量相似度的度量

在定义距离的时候，我们发现之间的距离，除了斜交空间距离与部分考虑了相关性的马氏距离，其他都没有考虑变量之间的相关性。实际生活中，我们也可能对变量之间进行聚类，这样就可以把变量选择的过程变得更加有效。

将用于概括变量之间相似性的指标记作相似系数 C i j C_{ij} Cij​。很多时候，我们选择相关系数作为变量之间相似度的度量，其实余弦相似度也是描述变量之间相似度的一种指标。

夹角余弦，就是将各个变量的 n n n次观测值看作一个 n n n维向量，计算两个 n n n维向量的相似度，计算公式是
C i j ( 1 ) = ∑ t = 1 n x t i x t j ∑ t = 1 n x t i 2 ∑ t = 1 n x t j 2 . C_{ij}(1)=\frac{\sum\limits_{t=1}^n x_{ti}x_{tj}}{\sqrt{\sum\limits_{t=1}^nx_{ti}^2}\sqrt{\sum\limits_{t=1}^n x_{tj}^2}}. Cij​(1)=t=1∑n​xti2​ ​t=1∑n​xtj2​ ​t=1∑n​xti​xtj​​.
相关系数则是标准化后的夹角余弦。如果一组数据全是正值，则夹角必定位于第一象限，差异不大，标准化有助于拉大相似度的取值范围。
C i j ( 2 ) = ∑ t = 1 n ( x t i − x ˉ i ) ( x t j − x ˉ j ) ∑ t = 1 n ( x t i − x ˉ i ) 2 ∑ t = 1 n ( x t j − x ˉ j ) 2 . C_{ij}(2)=\frac{\sum\limits_{t=1}^n(x_{ti}-\bar x_i)(x_{tj}-\bar x_j)}{\sqrt{\sum\limits_{t=1}^n(x_{ti}-\bar x_i)^2}\sqrt{\sum\limits_{t=1}^n(x_{tj}-\bar x_j)^2}}. Cij​(2)=t=1∑n​(xti​−xˉi​)2 ​t=1∑n​(xtj​−xˉj​)2 ​t=1∑n​(xti​−xˉi​)(xtj​−xˉj​)​.
由于 ∣ C i j ∣ |C_{ij}| ∣Cij​∣越接近0，就代表相似度越低，距离越远，所以可以用 d i j = 1 − ∣ C i j ∣ d_{ij}=1-|C_{ij}| dij​=1−∣Cij​∣或者 d i j 2 = 1 − C i j 2 d_{ij}^2=1-C_{ij}^2 dij2​=1−Cij2​来定义变量间的距离。

当然，最直观的方法还是直接将数据矩阵转置，交换变量与样本的地位，这样就可以将变量的处理方式与样本作等同。

4.类间距离

最后，由于系统聚类法将最相似的两个类作合并，所以定义类间距离，用它来刻画两个类之间的相似度。如果类间距离小，则视为相似。以下设 G p , G q , G r , G k G_p,G_q,G_r,G_k Gp​,Gq​,Gr​,Gk​等为类， D p q D_{pq} Dpq​为 G p , G q G_p,G_q Gp​,Gq​间的距离， i ∈ G p i\in G_p i∈Gp​指的是 X ( i ) X_{(i)} X(i)​是 G p G_p Gp​中的个体。

首先定义三种基于类内单个样本的类间距离刻画方法：最短距离法(single)、最长距离法(complete)、中间距离法(median)，这三种方法的特点是基于类内的最有代表性个体，具体定义方式与合并递推式（假设 G r G_r Gr​为 G p , G q G_p,G_q Gp​,Gq​的合并类）如下：

1. 最短距离法：类与类之间的距离定义为两类中相距最近的样品之间的距离，即
   D p q = min ⁡ i ∈ G p , j ∈ G q d i j , D_{pq}=\min_{i\in G_p,j\in G_q}d_{ij}, Dpq​=i∈Gp​,j∈Gq​min​dij​,
   合并后距离递推式为 D r k = min ⁡ { D p k , D q k } D_{rk}=\min \{D_{pk},D_{qk} \} Drk​=min{Dpk​,Dqk​}。

2. 最长距离法：类与类之间的距离定义为两类中相距最远的样品之间的距离，即
   D p q = max ⁡ i ∈ G p , j ∈ G q d i j , D_{pq}=\max_{i\in G_p,j\in G_q}d_{ij}, Dpq​=i∈Gp​,j∈Gq​max​dij​,
   合并后距离递推式为 D r k = min ⁡ { D p k , D q k } D_{rk}=\min\{D_{pk},D_{qk} \} Drk​=min{Dpk​,Dqk​}。

3. 中间距离法：类与类之间的距离是介于最短、最长之间的距离，在每类仅含一个样本时与最短、最长距离一致。

   取合并后距离递推公式为 D r k 2 = 1 2 ( D p k 2 + D q k 2 ) − 1 / 4 D p q 2 D_{rk}^2=\frac12(D_{pk}^2+D_{qk}^2)-1/4D_{pq}^2 Drk2​=21​(Dpk2​+Dqk2​)−1/4Dpq2​，这样的 D r k D_{rk} Drk​就是以 D p q , D p k , D q k D_{pq},D_{pk},D_{qk} Dpq​,Dpk​,Dqk​为边的三角形中， D p q D_{pq} Dpq​边上的中线长度。

这三种定义距离的方法主要作用在类内的代表个体上，而没有考虑每一类中所含样品的个数。以下的重心法(centroid)、类平均法(average)、McQuitty相似分析法(mcquitty)主要注重于类的总体性质。

4. 重心法：将样品均值视为每一类的重心，类与类之间的距离定义为两类重心的距离，即
   D p q = d p q ( X ˉ p , X ˉ q ) , D_{pq}=d_{pq}(\bar X_{p},\bar X_q), Dpq​=dpq​(Xˉp​,Xˉq​),
   在欧氏距离下，合并后距离递推式是
   D r k 2 = n p n r D p k 2 + n q n r D q k 2 − n p n q n r 2 D p q 2 . D^2_{rk}=\frac{n_p}{n_r}D^2_{pk}+\frac{n_q}{n_r}D^2_{qk}-\frac{n_pn_q}{n_r^2}D^2_{pq}. Drk2​=nr​np​​Dpk2​+nr​nq​​Dqk2​−nr2​np​nq​​Dpq2​.

5. 类平均法：用两类样品两两之间距离的平均作为类间距离，即
   D p q = 1 n p n q ∑ i ∈ G p , j ∈ G q d i j 2 , D_{pq}=\frac1{n_pn_q}\sum_{i\in G_p,j\in G_q}d^2_{ij}, Dpq​=np​nq​1​i∈Gp​,j∈Gq​∑​dij2​,
   合并后距离递推式是
   D r k 2 = n p n r D p k 2 + n q n r D q k 2 . D^2_{rk}=\frac{n_p}{n_r}D^2_{pk}+\frac{n_q}{n_r}D^2_{qk}. Drk2​=nr​np​​Dpk2​+nr​nq​​Dqk2​.

6. McQuitty相似分析法：使用平方距离平均的距离递推式，即
   D r k 2 = D p k 2 + D q k 2 2 . D^2_{rk}=\frac{D^2_{pk}+D^2_{qk}}2. Drk2​=2Dpk2​+Dqk2​​.

此外，还有一种基于组内离差平方和定义类间相似度，进而刻画距离的方法——离差平方和法(ward)，它基于以下考量：如果分类是正确的，那么类内离差平方和应该较小，类间离差平方和应该较大。因此，距离的定义为合并类后，增加的类内离差平方和。首先， G r G_r Gr​中的离差平方和是
W r = ∑ i = 1 n r ( X ( i ) ( r ) − X ˉ ( r ) ) ′ ( X ( i ) ( r ) − X ˉ ( r ) ) . W_r=\sum_{i=1}^{n_r}(X_{(i)}^{(r)}-\bar X^{(r)})'(X_{(i)}^{(r)}-\bar X^{(r)}). Wr​=i=1∑nr​​(X(i)(r)​−Xˉ(r))′(X(i)(r)​−Xˉ(r)).
于是，类间距离定义为 D p q 2 = W r − ( W p + W q ) D^2_{pq}=W_r-(W_p+W_q) Dpq2​=Wr​−(Wp​+Wq​)，当采用欧氏距离定义时，有
D p q 2 = n p n q n p + n q d 2 ( X ˉ p , X ˉ q ) , D^2_{pq}=\frac{n_pn_q}{n_p+n_q}d^2(\bar X_p,\bar X_q), Dpq2​=np​+nq​np​nq​​d2(Xˉp​,Xˉq​),
合并类的距离递推式为
D r k 2 = n p + n k n r + n k D p k 2 + n q + n k n r + n k D q k 2 − n k n r + n k D p q 2 . D^2_{rk}=\frac{n_p+n_k}{n_r+n_k}D^2_{pk}+\frac{n_q+n_k}{n_r+n_k}D^2_{qk}-\frac{n_k}{n_r+n_k}D^2_{pq}. Drk2​=nr​+nk​np​+nk​​Dpk2​+nr​+nk​nq​+nk​​Dqk2​−nr​+nk​nk​​Dpq2​.

回顾总结

1. 数据准备的方式有：中心化、标准化、极差标准化、极差正规化，其中，标准化或正规化得到的数据是无量纲的。除此之外，还可以用对数或者根式进行处理。
2. 样品间距离的刻画方式有Minkowski度量、Canberra度量、Mahalanobis度量、斜交空间度量等，其中Minkowski度量包含了绝对值度量、Euclidean度量、Chebyshev度量。
3. 变量相似度可以用余弦相似度、相关系数度量，进而基于相似度计算变量间距离；也可以将数据矩阵进行转置，刻画变量间的距离。
4. 类间距离定义方式有最短距离(single)、最长距离(complete)、中间距离(median)、重心距离(centroid)、类平均距离(average)、McQuitty相似分析法(mcquitty)、离差平方和法(ward)等。它们在合并类时的距离递推式各不相同。