数学建模系列笔记6：聚类和判别分析

@[toc]

6-1-1 模糊聚类

原理简介：现实中的数学模型可以分为三大类：确定性数学模型、随机性数学模型、模糊性模型，模糊数学正是研究带有模糊性问题的方法，只要定义了隶属函数，有了隶属度，就可以对样本进行模糊识别和模糊聚类。

定义：设 $R = (r_{ij})_{n\times n}$ 是n阶模糊方阵，I是n阶单位方阵，若R满足：

自反性： $I\leq R$
对称性： $R^T = R$
传递性： $R^2 \leq R( \Leftrightarrow max\{r_{ik}\wedge r_{kj}|1\leq k\leq n\}\leq r_{ij})$

则称R为模糊等价矩阵。

定理：设R是n阶模糊等价矩阵，则 $\forall 0 \leq \lambda < \mu \leq 1,R_{\mu}$ 所决定的分类中的每一个类是 $R_{\lambda}$ 所决定的分类中的某个子类。

该定理表明，当 $\lambda < \mu$ 时， $R_{\mu}$ 的分类是 $R_{\lambda}$ 分类的加细，当 $\lambda$ 由1变到0时， $R_{\lambda}$ 的分类由细到粗，形成一个动态的聚类图。

模糊聚类的一般流程

建立数据矩阵，并标准化（去量纲）
建立模糊相似矩阵
求出传递闭包矩阵，根据传递闭包矩阵计算 $\lambda$ 截矩阵，根据 $\lambda$ 截矩阵进行模糊聚类，根据模糊聚类结果画出聚类图

模糊聚类的详细步骤

建立数据矩阵

设论域 $U = \{x_1,x_2,…,x_n\}$ 为被分类对象（样本），每个对象又由m个指标表示其形状： $x_i = \{x_{i1},x_{i2},…,x_{im}\},i=1,2,…,n$ ，则得到原始数据矩阵为 $X = (x_{ij})_{n \times m}$
对数据矩阵进行标准化
建立模糊相似矩阵

建立 $x_i$ 与 $x_j$ 相似程度 $r_{ij} = R(x_i,x_j)$ 的方法主要有：
- 相似系数法
  - 夹角余弦法
    $r_{ij} = \frac{\sum_{k=1}^mx_{ik}x_{jk}}{\sqrt{\sum_{k=1}^mx_{ik}^2\sum_{k=1}^mx_{jk}^2}}$
  - 相关系数法
- 距离法
  
  一般地，取 $r_{ij} = 1-c(d(x_i,x_j))^{\alpha}$ ，其中 $c,\alpha$ 为适当选取的参数，它使得 $0\leq r_{ij}\leq 1$ ,采用的距离有
  - Hamming距离
    $d(x_i,x_j) = \sum_{k=1}^m |x_{ik}=x_{jk}|$
  - Euclid距离
    $d(x_i,d_j) = \sqrt{ \sum_{i=1}^m (x_{ik}-x_{jk})^2 }$
  - Chebysgev距离
    $d(x_i,x_j) = max_{1\leq k \leq n}|x_{ik}-x_{jk}|$
- 贴近度法
  - 最大最小法
    $r_{ij} =\frac{\sum_{k=1}^m (x_{ik}\wedge x_{jk})}{\sum_{k=1}^m(x_{ik}\vee x_{jk})}$
  - 算术平均最小法
    $r_{ij} =\frac{\sum_{k=1}^m (x_{ik}\wedge x_{jk})}{\frac{1}{2}\sum_{k=1}^m(x_{ik}+ x_{jk})}$
  - 几何平均最小法
    $r_{ij} =\frac{\sum_{k=1}^m (x_{ik}\wedge x_{jk})}{\sum_{k=1}^m\sqrt{x_{ik}· x_{jk}}}$
聚类
1. 利用模糊传递闭包法，先求出模糊自相似矩阵R的传递闭包 $t(R)$ ;
2. 按 $\lambda$ 由大到小进行聚类;
3. 画出动态聚类图。

6-1-2 模糊聚类：精准扶贫

6-2 系统聚类分析

聚类分析：群分析，它是研究聚类问题的一种多元统计方法。

将相似元素聚为一类，通常选取元素的许多共同指标，然后通过分析元素的指标值来分辨元素间的差距，从而达到聚类的目的。

聚类分析分为Q型（样品聚类）聚类、R型（指标聚类）聚类。

聚类分析步骤：

确定聚类类型
数据预处理：为了使不同量纲的量能进行比较，需要将数据规格化
研究样品之间的关系
研究类与类之间的关系
- 最短距离法
  $d(G_1,G_2) = min_{x_i \in G_1,x_j \in G_2}\{d(x_i,x_j)\}$
- 最长距离法
  $d(G_1,G_2) = max_{x_i \in G_1,x_j \in G_2}\{d(x_i,x_j)\}$
- 重心法
  $d(G_1,G_2) = \{d(\bar{x},\bar{y})\}$

系统聚类分析聚类数的确定：

可根据经验确定聚类数
聚类后，可以通过计算统计量（比如均值）或不一致系数，来确定聚类数

6-3 动态聚类分析

系统聚类法：优点是聚类比较准确，缺点是聚类的次数较多，每聚类一次只能减少一类或若干类，每一次都需要计算两两样品或小类之间的距离或其他相似性统计量，做起来较麻烦。

对于海量数据，几乎难以实现聚类。动态聚类法对于容量较大的样本聚类会比较方便。

方法理论简介：

先确定若干个样品为初始凝聚点，计算各样品与凝聚点的距离或其他相似性统计量，进行初始聚类后再根据初始聚类计算各类的重心作为新的凝聚点，进行第二次聚类，并且重复多次，直到符合某一最优原则为止。

又称逐步聚类法，关键是凝聚点的选择及聚类结果的跳着，常用的方法有成批调整法与离差平方和法。
成批调整法（k-means法）

总结与体会

k均值方法对初始点敏感
k均值方法的计算比较耗时

6-4 模糊模式识别

模式识别的本质特征：一是事先已知若干标准模式，称为标准模式库；二是有待识别的对象。
所谓模糊模式识别，是指在模式识别中，模式是模糊的，或有待识别的对象是模糊的。

模式识别数学原理

最大隶属原则|：设 $A_1,A_2,…,A_m$ 为给定的论域U上的m个模糊模式， $x_0 \in U$ 为一个待识别对象，若 $A_i(x_0) = max\{A_1(x_0),A_2(x_0),…,A_m(x_0)\}$ ,则认为 $x_0$ 优先归属于模糊模式 $A_i$ 。

最大隶属原则||：设A为给定论域U上的一个模糊模式， $x_1,x_2,…,x_n$ 为U中的n个待识别对象，若 $A(x_i) = max\{A(x_1),A(x_2),…,A(x_n)\}$ ,则认为模糊模式A应优先录取 $x_i$ 。

阈值原则：设 $A_1,A_2,…,A_m$ 为给定论域U上的m个模糊模式，规定一个阈值 $\lambda \in [0,1],x_0 \in U$ 为一个待识别对象。

如果 $max\{A_1(x_0),A_2(x_0),…,A_m(x_0)\}<\lambda$ ,则作“拒绝识别”的判决，这时应查找原因，再做分析。
如果 $max\{A_1(x_0),A_2(x_0),…,A_m(x_0)\}\geq\lambda$ ,并且有k个模糊模式 $A_{i_1}(x_0),A_{i_2}(x_0),…,A_{i_k}(x_0)$ 大于或等于 $\lambda$ ,则认为识别可行，并将 $x_0$ 划归于 $max\{A_{i_1},A_{i_2},…,A_{i_k}\}$

择近原则：

贴近度： $\sigma(A,B)$ 表示两个模糊集A,B之间的贴近程度

格贴近度： $\sigma_0(A,B) = \frac{1}{2}[A\circ B] + (1-A\odot B)]$

其中： $A\circ B = max\{A(x) \wedge B(x) \}$ 表示两个模糊集A,B的内积

        $A\odot B = min \{A(x) \vee B(x)\}$表示两个模糊集A,B的外积

定义（公理化定义）若（A,B)满足

$\sigma(A,A) = 1$
$\sigma(A,B) = \sigma(B,A)$
若有 $A \leq B \leq C,则\sigma (A,C) \leq \sigma(A,B) \leq \sigma (B,C)$ .

则称 $\sigma(A,B)$ 为A与B的贴近度。

模糊模式识别可以广泛被运用到模糊识别的各个方面，使用时最基本的是要建立评价模式和被评价对象的恰当指标，其次才是运用各类识别原则，对被评价对象进行模式识别。

6-5-1 贝叶斯判别

为了能识别待判断的对象 $x= (x_1,x_2,…,x_m)^T$ 是属于已知类 $A_1,A_2,…,A_r$ 中的哪一类，需要有一个一般规则做出判断，这样一个规则为判别规则（用于衡量待判别对象与各已知类别接近程度的方法准则）

判别分析的假设条件：

各个判别变量服从正态分布，由各个判别变量的联合分布是多元正态分布
各判别变量不能存在多重共线性，每个变量在各类中的取值应存在显著性差异

方法理论简介：

假设对所研究的对象有了一定的认识，重新计算样品属于各总体的条件概率：
$f(g|x) (g=1,2,…,k)$
比较这k各概率大小，然后将新样本判归为来自后验概率最大的总体。

Bayes判别法的基本思想

在观测一个样品x的情况下，可用Bayes公式计算它来自第g总体的后验概率
$p(g|x) = \frac{q_j f_j(x)}{\sum_{i=1}^k q_j f_j},j = 1,2,…,k$

计算各类变量的均值以及均值向量，各变量的总均值及均值向量；
计算类内协方差矩阵及其逆矩阵；
计算Bayes判别函数中，各个变量的系数及常数项并写出判别函数；
计算类内协方差矩阵及总各协方差矩阵，作多个变量的全体判别效果的检验；
各个变量的判别能力的检验；
判别新样本应属于的类别。

在得到样本后，首先可以根据样本信息修正之前所获得的先验概率分布，进一步获得后验概率分布，之后可以通过新的后验概率分布进行各种统计推断。

一种好的判别方法，一定要考虑到每个总体出现的先验概率，同时能够对误判所出现的损失进行评估。贝叶斯判别法就具备上述优点。

6-5-2 贝叶斯判别：医疗诊断模型

样本空间的划分

定义：设S为试验E的样本空间， $B_1,B_2,…,B_n$ 为E的一组事件，若

$B_iB_j = \varnothing, i \ne j, i,j = 1,2,…,n;$
$B_1 \cup B_2 \cup …\cup B_n = S.$

则称 $B_1,B_2,…,B_n$ 为样本空间S的一个划分。

全概率公式

试验E的样本空间为S,A为E的事件， $B_1,B_2,…,B_n$ 为S的一个划分，且 $P(B_i)>0(i=1,2,…,n)$ ，则
$P(A) = \sum_{i=1}^n P(A|B_i)P(B_i)$
贝叶斯公式
$P(B_i|A) = \frac{P(B_iA)}{P(A)} = \frac{P(A|B_i)P(B_i)}{\sum_{j=1}^n P(A|B_j)P(B_j)},i = 1,2,…,n$
贝叶斯判别的理论基础

$G_1,G_2—p$ 维总体，密度 $f_(x),f_2(x)$ ,各总体先验概率 $p_1 = P(G_1),p_2 = P(G_2),p_1 + p_2 = 1.$

样品 $x = (x_1,x_2,…,x_p)^T$ 属于G1,G2的后验概率为
$P(G_1|x) = \frac{p_1 f_1(x)}{p_1f_1(x)+p_2f_2(x)},P(G_2|x) = \frac{p_2 f_2(x)}{p_1f_1(x)+p_2f_2(x)}$
两个总体的Bayes判别准则
$x \in G_1,P(G_1|x)\geq P(G_2|x) p_1f_1(x)\geq p_2f_2(x)\\ x \in G_2,P(G_1|x)< P(G_2|x) p_1f_1(x)< p_2f_2(x)$

数学建模系列笔记6：聚类和判别分析