聚类分析和matlab实现

一、定义

​ 聚类分析又称群分析，是对多个样本(或指标)进行定量分类的一种多元统计分析方法。对样本进行分类称为Q型聚类分析，对指标进行分类称为R型聚类分析。

区别聚类与分类

• 聚类是将数据进行划分不同的类别，类别是未知的
• 分类是将数据进行分配到不同的类别中，此类别是已知的

二、Q型聚类分析

1 样本的相似性度量

​ 一个样本往往由多个变量$x_1,x_2,...,x_n$进行描述。而当这些变量组合起来的时候：($x_1,x_2,...,x_n$)，则可看成是一个在$R^n$空间中的一个点，或者是n维向量空间中的一个向量。

​ 由于聚类分析是要求使用定量化的方法对样本进行分类，所以需要用数量来描述样本之间的相似程度。由上一段所提，很自然想到使用距离来度量样本点之间的相似程度。

​ 下面便是计算样本点之间距离的常用方法：

(一) 闵氏距离 (MinKowski)

$$d_q(\mathbf{x},\mathbf{y})=[\sum _{k=1}^p|x_k-y_k{|}^q{]}^{\frac{1}{q}},$$

当$q=1,2$或$q⟶+\infty$时，分别得到：

(二) 绝对值距离

$$d_1(\mathbf{x},\mathbf{y})=\sum _{k=1}^p|x_k-y_k|,$$

(三) 欧几里得距离

$$d_2(\mathbf{x},\mathbf{y})=[\sum _{k=1}^p(x_k-y_k{)}^2{]}^{\frac{1}{2}},$$

(四) 切比雪夫距离

$$d_{\infty }(\mathbf{x},\mathbf{y})=\underset{1\le k\le p}{\max }|x_k-y_k|，$$

​ 在Minkowski距离中，最常用的是欧几里得距离，它的主要优点是当坐标轴进行正交旋转时，欧氏距离是保持不变的。因此，如果对原坐标系进行平移和旋转变换，变换后样本点间的距离和变换前完全相同。

​ 同时要注意，采用Minkowski距离时，

• 一定要采用相同量纲的变量

• 尽可能避免变量的多重相关性。多重相关性会导致信息重叠，会片面强调某些变量的重要性。

  由于Minkowski距离由这些缺点，便有了改进的马氏距离。

(五) 马氏距离 (Mahalanobis)

$$d(\mathbf{x},\mathbf{y})=\sqrt{(\mathbf{x}-\mathbf{y}{)}^T{\mathbf{\Sigma }}^{-1}(\mathbf{x}-\mathbf{y})}$$

​ 式中：$\mathbf{x},\mathbf{y}$ 是来自p维总体 $Z$ 的样本观察值；$\mathbf{\Sigma }$ 为 $Z$ 的协方差矩阵，实际中 $\mathbf{\Sigma }$ 往往是未知的，常常需要同样本协方差来估计。

​ 马氏距离对一切线性变化是不变的，故不受量纲的影响。

2 类的相似性度量

（一）最短距离法 (Nearest Neighbor or Single Linkage Method)

$$D(G_1,G_2)=\underset{\genfrac{}{}{0ex}{}{x_i\in G_1}{y_j\in G_2}}{\min }|d({\mathbf{x}}_i,{\mathbf{y}}_j)|,$$

​ 即两个类中最近的两点间的距离。

（二）最长距离法 (Farthest Neighbor or Complete Linkage Method)

$$D(G_1,G_2)=\underset{\genfrac{}{}{0ex}{}{x_i\in G_1}{y_j\in G_2}}{\max }|d({\mathbf{x}}_i,{\mathbf{y}}_j)|,$$

​ 即两个类中最远的两点间的距离。

（三）重心法 (Centroid Method)

$$D(G_1,G_2)=d(\bar{\mathbf{x}},\bar{\mathbf{y}}),$$

​ 其中，$\bar{\mathbf{x}},\bar{\mathbf{y}}$ 分别为 $G_1,G_2$ 的重心。

（四）类平均法 (Group Average Method)

$$D(G_1,G_2)=\frac{1}{n_1{n}_2}\sum _{x_i\in G_1}\sum _{x_j\in G_2}d({\mathbf{x}}_i,{\mathbf{x}}_j),$$

​ 它等于 $G_1,G_2$ 中两样本点距离的平均，其中：$n_1,n_2$ 分别为 $G_1,G_2$ 中的样本点个数。

（五）离差平方和法 (Sum of Squares Method)

若记：
$$D_1=\sum _{x_i\in G_1}({\mathbf{x}}_i-{\bar{\mathbf{x}}}_1{)}^T({\mathbf{x}}_i-{\bar{\mathbf{x}}}_1)$$

$$D_2=\sum _{x_j\in G_2}({\mathbf{x}}_j-{\bar{\mathbf{x}}}_2{)}^T({\mathbf{x}}_j-{\bar{\mathbf{x}}}_2)$$

$$D_{12}=\sum _{x_k\in G_1\cup G_2}({\mathbf{x}}_k-\bar{\mathbf{x}}{)}^T({\mathbf{x}}_k-\bar{\mathbf{x}})$$

式中：
$${\bar{\mathbf{x}}}_1=\frac{1}{n_1}\sum _{x_i\in G_1}{\mathbf{x}}_i$$

$${\bar{\mathbf{x}}}_2=\frac{1}{n_2}\sum _{x_j\in G_2}{\mathbf{x}}_j$$

$$\bar{\mathbf{x}}=\frac{1}{n_1+n_2}\sum _{x_k\in G_1\cup G_2}{\mathbf{x}}_k$$

所以则定义：
$$D(G_1,G_2)=D_{12}-D_1-D_2$$
​ 若 $G_1,G_2$ 内部点与点距离很小，则它们能很好地各自聚为一类，并且这两类又能够充分分类(即 $D_{12}$ 很大)，这时必然有 $D=D_{12}-D_1-D_2$ 很大。因此，按定义可以认为，两类 $D_1,D_2$ 之间的距离很大。

​ 又称为Ward方法。

3 Matlab聚类分析相关命令

（一）pdist

​ 使用方法：Y = pdist(X, ‘metric’)

​ 表示用’metric’指定的方法计算矩阵X中对象间的距离。其中：

• 矩阵X为 $m\times n$ 矩阵，可看作 $m$ 个 $n$ 维行向量，每一个行向量就是样本点
• 输出的Y是包含距离信息的长度为 $\frac{m(m-1)}{2}$ 的行向量，由于距离的两两组合后的距离，所以由排列组合可知共有 $\frac{m(m-1)}{2}$ 个组合。

下面是’metric’常用字符串值：

字符串	含义
‘euclidean’	欧式距离（默认）
‘seuclidean’	标准欧几里得距离
‘cityblock’	绝对值距离
‘minkowski’	闵氏距离
‘chebychev’	切比雪夫距离
‘mahalanobis’	马氏距离

注意：使用闵氏距离时，Y = pdist(X, ‘minkowski’, p)，其中p为闵氏距离计算需要用到的指数值，默认为2.

（二）linkage

​ 使用方法：Z = linkage(Y, ‘method’)

​ 表示使用由’method’指定的算法计算生成聚类树，其中：

• Y为pdist函数输出的 $\frac{m(m-1)}{2}$ 维距离行向量
• Z为包含聚类树信息的 $(m-1)\times 3$ 矩阵。每一行表示一个类(样本)和另一个类(样本)的合并，所以相当于每一个样本都要合并一次，而第一次合并是两个样本进行的，所以总共有 $m-1$ 行。
  • 第一二列表示两个合并类(样本)，其中：$1\sim m$ 表示初始样本；超过 $m$ 的是由样本组成的类，记作 $m+j$ ，其中 $m$ 为样本总数，$j$ 表示该类是在第 $j$ 行新形成的。
  • 第三列表示对应两个类(样本)间的距离。

​ 下面是’method’常用的字符串：

字符串	含义
‘single’	最短距离（默认）
‘average’	无权平均距离
‘centroid’	重心距离
‘complete’	最大距离
‘median’	赋权重心距离
‘ward’	离差平方和方法
‘weighted’	赋权平均距离

（三）cluster

​ 使用方法：T = cluster(Z, ‘cutoff’, c)

​ 表示将由linkage产生的信息矩阵Z分成c类，其中：

• Z为linkage函数生成的 $(m-1)\times 3$ 矩阵
• c 表示分成类的数量
• T为长度为 $m$ 的列向量，其中每行对应着X中的行(样本)，T中数字相同的为同一类

（四）dendrogram

​ 使用方法(常用)：

• H = dendrogram(Z, P)
• H = dendrogram(Z, P, ‘ColorThreshold’, cutoff)

表示画出由linkage产生的信息矩阵Z对应的聚类树状图。其中：

• Z为linkage函数生成的 $(m-1)\times 3$ 矩阵
• P为树状图显示的最大基础类数量(结点数量)，默认值为30，0表示全部画出
• ‘ColorThreshold’ 表示不同类显示不同颜色
• cutoff与’ColorThreshold’ 配合使用，表示不同颜色类的最小距离

4 举例

（一）

clc, clear;	% 清除页面和工作区
a = [1,0;1,1;3,2;4,3;2,5];	% 5组样本
Y = pdist(a);   % 计算两两样本之间的欧式距离
Z = linkage(Y); % 使用最短距离算法生成具有层次结构的聚类树
T = cluster(Z,3);	% 将聚类树分成3类
H = dendrogram(Z,0);	% 将聚类树Z全部画出

得到下聚类图：

（二）

clc, clear;	% 清除页面和工作区
a = [1,0;1,1;3,2;4,3;2,5];	% 5组样本
Y = pdist(a);   % 计算两两样本之间的欧式距离
Z = linkage(Y); % 使用最短距离算法生成具有层次结构的聚类树
T = cluster(Z,3);	% 将聚类树分成3类
cutoff = median([Z(end-2,3) Z(end-1,3)]);	% 让其最小距离在倒数第二三行中，其取倒数第二行，即分成三类
H = dendrogram(Z,0,'ColorThreshold',cutoff);% 将Z带不同颜色画出

得到下聚类图：

---

参考资料：
[1] 司守奎, 孙兆亮. 数学建模算法与应用[M].北京:国防工业出版社,2020:2.