清风数学建模学习笔记——系统(层次)聚类原理详解及案例分析

超、凢脫俗 2023-10-11 15:22 67阅读 0赞

### 系统聚类 ###

系统聚类的合并算法通过计算两类数据点间的距离，对最为接近的两类数据点进行组合，并反复迭代这一过程，直到将所有数据点合成一类，并生成聚类谱系图。此外，系统聚类可以解决簇数 K 的取值问题，后文会给出 SPSS 操作的流程。

--------------------

#### 目录 ####

*   *  系统聚类
     *  一、样本与样本间的距离
     *  二、指标与指标之间的距离
     *  三、类与类之间的距离
     *  四、系统聚类法流程
     *  五、案例分析
     *  六、肘部法则对模型的修正
     *  七、模型扩展（★）

--------------------

### 一、样本与样本间的距离 ###

例：下表是30个学生的六门课的成绩。根据这30个人的成绩，对这30个学生进行分类。  
  ![在这里插入图片描述][20210212195723967.png_pic_left]

--------------------

样本与样本之间的常用距离（样本  i i i 与样本  j j j）：  
 1 、 绝 对 值 距 离 ： d ( x i ⃗ , x j ⃗ ) = ∑ k = 1 p ∣ x i k − x j k ∣ 2 、 欧 式 距 离 ： d ( x i ⃗ , x j ⃗ ) = ∑ k = 1 p ( x i k − x j k ) 2 3 、 M i n k o w s k i 距 离 ： d ( x i ⃗ , x j ⃗ ) = \[ ∑ k = 1 p ( x i k − x j k ) q \] 1 q 4 、 C h e b y s h e v 距 离 ： d ( x i ⃗ , x j ⃗ ) = m a x 1 ≤ k ≤ p ∣ x i k − x j k ∣ 5 、 马 氏 距 离 ： d ( x i ⃗ , x j ⃗ ) = ( x i ⃗ , x j ⃗ ) ′ ∑ − 1 ( x i ⃗ , x j ⃗ ) 其 中 ： x ⃗ i = ( x i 1 , x i 2 , . . . , x i p ) ′ , x ⃗ j = ( x j 1 , x j 2 , . . . , x j p ) ′ 1、绝对值距离：d(\\vec\{x\_i\},\\vec\{x\_j\})=\\sum\_\{k=1\}^\{p\}|x\_\{ik\}-x\_\{jk\}|\\\\ 2、欧式距离：d(\\vec\{x\_i\},\\vec\{x\_j\})=\\sqrt\{\\displaystyle\\sum\_\{k=1\}^\{p\}(x\_\{ik\}-x\_\{jk\})^2\}\\\\ 3、Minkowski距离：d(\\vec\{x\_i\},\\vec\{x\_j\})=\\left\[ \\sum\_\{k=1\}^\{p\}(x\_\{ik\}-x\_\{jk\})^q \\right\]^\{\\frac\{1\}\{q\}\}\\\\ 4、Chebyshev距离：d(\\vec\{x\_i\},\\vec\{x\_j\})=\\mathop\{max\}\\limits\_\{1≤k≤p\}|x\_\{ik\}-x\_\{jk\}|\\\\ 5、马氏距离：d(\\vec\{x\_i\},\\vec\{x\_j\})=(\\vec\{x\_i\},\\vec\{x\_j\})^\{'\}\\sum\\nolimits\{\}^\{-1\}(\\vec\{x\_i\},\\vec\{x\_j\})\\\\ 其中：\\vec x\_i=(x\_\{i1\},x\_\{i2\},...,x\_\{ip\})^\{'\},\\quad\\vec x\_j=(x\_\{j1\},x\_\{j2\},...,x\_\{jp\})^\{'\} 1、绝对值距离：d(xi,xj)=k=1∑p∣xik−xjk∣2、欧式距离：d(xi,xj)=k=1∑p(xik−xjk)23、Minkowski距离：d(xi,xj)=\[k=1∑p(xik−xjk)q\]q14、Chebyshev距离：d(xi,xj)=1≤k≤pmax∣xik−xjk∣5、马氏距离：d(xi,xj)=(xi,xj)′∑−1(xi,xj)其中：xi=(xi1,xi2,...,xip)′,xj=(xj1,xj2,...,xjp)′

--------------------

例：

![在这里插入图片描述][20210212195805282.png_pic_left]  ![在这里插入图片描述][20210212193044854.png_pic_left]

--------------------

### 二、指标与指标之间的距离 ###

例：根据这30个人的成绩，将六门课程分为两类。

--------------------

指标与指标之间的常用距离（指标 i 与指标 j ）

相 关 系 数 ： ρ ( X i , X j ) = ∑ k = 1 p ( x ˉ k i − x ˉ i ) ( x ˉ k j − x ˉ j ) ∑ k = 1 p ( x ˉ k i − x ˉ i ) 2 ( x ˉ k j − x ˉ j ) 2 夹 角 余 弦 ： r ( X i , X j ) = ∑ k = 1 p x k i x k j ∑ k = 1 p x k i 2 ∑ k = 1 p x k j 2 相关系数：\\rho(X\_i,X\_j)=\\frac\{\\displaystyle\\sum\_\{k=1\}^\{p\}\{(\\bar x\_\{ki\}-\\bar x\_i)(\\bar x\_\{kj\}-\\bar x\_j)\}\}\{\\sqrt\{\\displaystyle\\sum\_\{k=1\}^\{p\}\{(\\bar x\_\{ki\}-\\bar x\_i)^2(\\bar x\_\{kj\}-\\bar x\_j)^2\}\}\}\\\\ 夹角余弦：r(X\_i,X\_j)=\\frac\{\\displaystyle\\sum\_\{k=1\}^\{p\}\{x\_\{ki\}x\_\{kj\}\}\}\{\\sqrt\{\\displaystyle\\sum\_\{k=1\}^\{p\}\{x\_\{ki\}^2\\displaystyle\\sum\_\{k=1\}^\{p\}\{x\_\{kj\}^2 \}\}\}\} 相关系数：ρ(Xi,Xj)=k=1∑p(xˉki−xˉi)2(xˉkj−xˉj)2k=1∑p(xˉki−xˉi)(xˉkj−xˉj)夹角余弦：r(Xi,Xj)=k=1∑pxki2k=1∑pxkj2k=1∑pxkixkj

用的比较少，了解即可。

--------------------

### 三、类与类之间的距离 ###

类与类之间的距离就是集合与集合之间的距离。

类与类之间的距离有如下两个属性：

1.  由一个样品组成的类是最基本的类；**如果每一类都由一个样品组成，那么样品间的距离就是类间距离。**
2.  **如果某一类包含不止一个样品，那么就要确定类间距离**，类间距离是基于样品间距离定义的。

定义： G p G\_p Gp和  G q G\_q Gq是两个类， D ( G p , G q ) D(G\_p,G\_q) D(Gp,Gq)是这两个类的距离。 x i ∈ G p ， x j ∈ G q x\_i∈G\_p，x\_j∈G\_q xi∈Gp，xj∈Gq， d ( x i , x j ) d(x\_i,x\_j) d(xi,xj)是两个样本之间的距离。

--------------------

类与类之间的距离有如下几种定义：

1.  最短距离法：  
     D ( G p , G q ) = min ⁡ d ( x i ⃗ , x j ⃗ ) D(G\_p,G\_q)=\\min d(\\vec\{x\_i\},\\vec\{x\_j\}) D(Gp,Gq)=mind(xi,xj)

![在这里插入图片描述][20210212202956676.png_pic_center]

1.  最长距离法：  
     D ( G p , G q ) = max ⁡ d ( x i ⃗ , x j ⃗ ) D(G\_p,G\_q)=\\max d(\\vec\{x\_i\},\\vec\{x\_j\}) D(Gp,Gq)=maxd(xi,xj)  
    ![在这里插入图片描述][20210212203111470.png_pic_center]
2.  组间平均连线法  
     D ( G p , G q ) = d 1 + d 2 + d 3 + d 4 4 D(G\_p,G\_q)=\\frac\{d\_1+d\_2+d\_3+d\_4\}\{4\} D(Gp,Gq)=4d1\+d2\+d3\+d4  
    ![在这里插入图片描述][20210212203430324.png_pic_center]
3.  组内平均连接法  
     D ( G p , G q ) = d 1 + d 2 + d 3 + d 4 + d 5 + d 6 6 D(G\_p,G\_q)=\\frac\{d\_1+d\_2+d\_3+d\_4+d\_5+d\_6\}\{6\} D(Gp,Gq)=6d1\+d2\+d3\+d4\+d5\+d6  
    ![在这里插入图片描述][20210212203821824.png_pic_center]
4.  重心法  
     D ( G p , G q ) = d ( x p ˉ , x q ˉ ) , 两 个 类 的 中 心 如 下 ： x ˉ p = x ⃗ p 1 + x ⃗ p 2 2 , x ˉ q = x ⃗ q 1 + x ⃗ q 2 2 D(G\_p,G\_q)=d(\\bar\{x\_p\},\\bar\{x\_q\}),两个类的中心如下：\\bar x\_p=\\frac\{\\vec x\_\{p1\}+\\vec x\_\{p2\}\}\{2\},\\bar x\_q=\\frac\{\\vec x\_\{q1\}+\\vec x\_\{q2\}\}\{2\} D(Gp,Gq)=d(xpˉ,xqˉ),两个类的中心如下：xˉp=2xp1\+xp2,xˉq=2xq1\+xq2  
    ![在这里插入图片描述][2021021220481421.png_pic_center]

--------------------

### 四、系统聚类法流程 ###

流程图如下：

![在这里插入图片描述][20210212210716733.png_pic_center]

--------------------

### 五、案例分析 ###

根据五个学生的六门课的成绩，对这五个学生进行分类。

![在这里插入图片描述][20210213000012333.png_pic_center]

--------------------

1.  写出样品间的距离矩阵(以欧氏距离为例）

![在这里插入图片描述][20210213000819309.png_pic_center]

1.  将每一个样品看做是一个类，即 G1,G2,G3,G4,G5。**观察 D(G1,G5)=15.8最小，故将 G1 与 G5 聚为一类，记为G6**。计算新类与其余各类之间的距离，得到新的距离矩阵D1。

![在这里插入图片描述][20210213001131444.png_pic_center]  
![在这里插入图片描述][20210213001207561.png_pic_center]

1.  **观察 D(G2,G4)=15.9 最小，故将G2与G4聚为一类，记为G7**。计算新类与其余各类之间的距离，得到新的距离矩阵D2。

![在这里插入图片描述][20210213001457859.png_pic_center]  
![在这里插入图片描述][20210213001733845.png_pic_center]

1.  **观察 D(G6,G7) =18.2最小，故将G6与G7聚为一类，记为G8。** 计算新类与其余各类之间的距离，得到新的距离矩阵 D3。

![在这里插入图片描述][20210213003557651.png_pic_center]  
![在这里插入图片描述][20210213003744504.png_pic_center]

1.  最后将G8与G3聚为一类，记为G9。

![在这里插入图片描述][20210213003951123.png_pic_center]

--------------------

SPSS操作：  
  分析 → 分类 → 系统聚类，将变量与标注依据分别加入到对应的组中。 保存图示如下，方法中的标准化，如果量纲不同，则选择 Z 得分。  
![在这里插入图片描述][20210213004725843.png]

--------------------

结果分析：

SPSS运行出的谱系图，可根据自己的需求划分出要聚类的个数，方法是画竖线，如下图，将样本化分为 3 类。第一类是广东、上海，第二类是北京、浙江、天津、西藏、福建，第三类是其余的省份。（这道例题选取：1999年全国31个省份城镇居民家庭平均每人全年消费性支出数据 ）  
  ![在这里插入图片描述][20210213005624536.png_pic_left]  
  虽说系统聚类对于 K 的选取提供了一些方案，但是我们对 K 的选取还存在一定的主观性，因此需要应用肘部法则来修正系统聚类。

--------------------

### 六、肘部法则对模型的修正 ###

肘部法则是通过图形大致的估计出最优的聚类数量。应用了SPSS输出文档中的集中计划中的系数，需要将系数进行排序之后，应用 excel 生成图像，如下图：  
  ![在这里插入图片描述][20210213010542858.png_pic_left]  ![在这里插入图片描述][20210213010636713.png_pic_left]  
  从上图可以看出 K 取1到5时，畸变程度变化最大。超过5以后，畸变程度变化显著降低。因此 K可以取 5，当然 3 也可以，只要给出理由。

--------------------

确定 K 之后，即可重新聚类，注意保存中选取单个解为 K 的值。如 K=3：

![在这里插入图片描述][20210213011535421.png]

--------------------

### 七、模型扩展（★） ###

1.  对于一个实际问题要根据分类的目的来选取指标，指标选取的不同分类结果一般也不同。
2.  样品间距离定义方式的不同，聚类结果一般也不同。
3.  聚类方法的不同，聚类结果一般也不同（尤其是样品特别多的时候）。最好能通过各种方法找出其中的共性。
4.  要注意指标的量纲，**量纲差别太大会导致聚类结果不合理。**
5.  聚类分析的结果可能不令人满意，因为我们所做的是一个数学的处理，对于结果我们要找到一个合理的解释。

--------------------

本文借鉴了数学建模清风老师的课件与思路，如果大家发现文章中有不正确的地方，欢迎大家在评论区留言，也可以点击查看下方链接查看清风老师的视频讲解~

**原文链接：**[https://www.bilibili.com/video/BV1DW411s7wi][https_www.bilibili.com_video_BV1DW411s7wi]

[20210212195723967.png_pic_left]: https://img-blog.csdnimg.cn/20210212195723967.png?#pic_left
[20210212195805282.png_pic_left]: https://img-blog.csdnimg.cn/20210212195805282.png?#pic_left
[20210212193044854.png_pic_left]: https://img-blog.csdnimg.cn/20210212193044854.png?#pic_left
[20210212202956676.png_pic_center]: https://img-blog.csdnimg.cn/20210212202956676.png?#pic_center
[20210212203111470.png_pic_center]: https://img-blog.csdnimg.cn/20210212203111470.png?#pic_center
[20210212203430324.png_pic_center]: https://img-blog.csdnimg.cn/20210212203430324.png?#pic_center
[20210212203821824.png_pic_center]: https://img-blog.csdnimg.cn/20210212203821824.png?#pic_center
[2021021220481421.png_pic_center]: https://img-blog.csdnimg.cn/2021021220481421.png?#pic_center
[20210212210716733.png_pic_center]: https://img-blog.csdnimg.cn/20210212210716733.png?#pic_center
[20210213000012333.png_pic_center]: https://img-blog.csdnimg.cn/20210213000012333.png?#pic_center
[20210213000819309.png_pic_center]: https://img-blog.csdnimg.cn/20210213000819309.png?#pic_center
[20210213001131444.png_pic_center]: https://img-blog.csdnimg.cn/20210213001131444.png?#pic_center
[20210213001207561.png_pic_center]: https://img-blog.csdnimg.cn/20210213001207561.png?#pic_center
[20210213001457859.png_pic_center]: https://img-blog.csdnimg.cn/20210213001457859.png?#pic_center
[20210213001733845.png_pic_center]: https://img-blog.csdnimg.cn/20210213001733845.png?#pic_center
[20210213003557651.png_pic_center]: https://img-blog.csdnimg.cn/20210213003557651.png#pic_center
[20210213003744504.png_pic_center]: https://img-blog.csdnimg.cn/20210213003744504.png?#pic_center
[20210213003951123.png_pic_center]: https://img-blog.csdnimg.cn/20210213003951123.png?#pic_center
[20210213004725843.png]: https://img-blog.csdnimg.cn/20210213004725843.png
[20210213005624536.png_pic_left]: https://img-blog.csdnimg.cn/20210213005624536.png?#pic_left
[20210213010542858.png_pic_left]: https://img-blog.csdnimg.cn/20210213010542858.png?#pic_left
[20210213010636713.png_pic_left]: https://img-blog.csdnimg.cn/20210213010636713.png#pic_left
[20210213011535421.png]: https://img-blog.csdnimg.cn/20210213011535421.png
[https_www.bilibili.com_video_BV1DW411s7wi]: https://www.bilibili.com/video/BV1DW411s7wi