模式识别与机器学习(二)

视屏链接

类间距离测度方法

1. 最近距离法

1. 最远距离法

1. 中间距离法

2. 重心距离法

1. 平均距离法

1. 离差平方和法

点与集合间的距离

• 第一类: 对集合的分布没有先验知识时，可采用类间距离计算方法进行


• 第二类: 当知道集合的中点分布的先验知识时，可用相应的模型进行计算(点模型，超平面模型，超球面模型等)

判别分类结果好坏的一般标准: 类内距离小，类间距离大

聚类的准则函数

类内距离准则：

设有待分类的模式集{\(\vec{x_1},\vec x_2,...,\vec x_N\)}在某种相似性测度基础上被划分为\(C\)类，{\(\vec x_i^{(j)}; j=1,2,...c;i=1,2,...,n_j\)}类内距离准则函数\(J_W\)定义为：(\(\vec m_j\) 表示 \(w_j\)类的模式均值矢量。)
\[J_W = \sum^c_{j=1} \sum_{i=1}^{n_j} ||\vec x_i^{(j)} - \vec m_j ||^2\]

类间距离准则
\[J_B = \sum_{j=1}^c (\vec m_j - \vec m)^`(\vec m_j - \vec m) => max\]
其中,\(\vec m_j\)为\(w_j\)类的模式平均矢量，\(\vec m\)为总的模式平均矢量。设\(n_j\)为\(w_j\)类所含模式个数，
\[\vec m_j = \frac{1}{n_j} \sum_{\vec x_i \in w_j} \vec x_i, \vec m = \frac{1}{N}\sum^N_{i=1} \vec x_i\]

对于两类问题，类间距离有时取
\[J_{B2} = (\vec m_1 - \vec m_2)^`(\vec m_1 - \vec m_2)\]
\(J_{B2}\)和\(J_{WB}\)的关系是
\[J_{WB} = \frac {n_1}{N} \frac{n_2}{N} J_{B2}\]

基于类内距离类间距离的准则函数
我们希望聚类结果使类内距离越小越好，类间距离越大越好。为此构造能同时反映出类内距离和类间距离的准则函数。
设代分类模式集{\(\vec x_i, i=1,2,...,N\)}，将它们分成\(c\)类，\(w_j\)含\(n_j\)个模式，分类后各模式记为
\[\{ \vec x_i^{(j)}, j = 1,2,...,c;i=1,2,...,n \}\]

\(w_j\)的类内离差阵定义为：
\[S^{(j)}_W = \frac{1}{n_j} \sum_{i=1}^{n_j} (\vec x_i^{(j)} - \vec m_j)(\vec x_i^{(j)} - \vec m_j)^` , (j=1,2,...,c)\]
式中\(\vec m_j\)为类\(w_j\)的模式均值矢量
\[\vec m_j = \frac{1}{n_j} \sum_{i=1}^{n_j} \vec x_i^j , (j=1,2,...,c)\]

总的类内离差阵定义为：\(S_W = \sum^c_{j=1} \frac{n_j}{N}S_W^{(j)}\)
类间离差阵定义为: \(S_B = \sum^c_{j=1} \frac{n_j}{N} (\vec m_j - \vec m)(\vec m_j - \vec m)^`\)
其中，\(\vec m\)为所有待分类模式的均值矢量: \(\vec m = \frac{1}{N} \sum_{i=1}^N \vec x_i\)
总的离差阵\(S_r\)，定义为：\(S_r = \frac{1}{N} \sum_{i=1}^N(\vec x_i - \vec m)(\vec x_i - \vec m)^`\)
于是有：\(S_r = S_W + S_B\)

基于类内距离类间距离的准则函数
聚类的基本目的是使\(Tr[S_B] => max\)或\(Tr[S_W] => min\)。利用线性代数有关矩阵的迹和行列式的性质，可以定义如下4个聚类的准则函数：
\[J_1 = Tr[S^{-1}_W S_B] \\\\J_2 = |S^{-1}_W S_B| \\\\J_3 = Tr[S^{-1}_W S_T] \\\\J_4 = |S^{-1}_W S_T|\]
为了得到好的聚类结果，应该使这四个准则函数尽量的大。

聚类分析聚类分析算法归纳起来有三大类：

1. 按最小距离原则简单聚类方法
2. 按最小距离原则进行两类合并的算法
3. 依据准则函数动态聚类的算法

简单聚类方法
针对具体问题确定相似性阙值，将模式到各聚类中心间的距离与阙值比较，当大于阙值时，该模式就作为另一类的类心，小于阙值时，按最小距离原则将其划分到某一类中。
该类算法运行中，模式的类别及类的中心一旦确定将不会改变

按最小距离原则进行两类合并的算法
首先视各模式自成一类，然后将距离最小的两类合并成一类，不断重复这个过程，直到成为两类为止。
这类算法运行中，类心会不断进行修正，但模式类别一旦指定后就不会再改变，即模式一旦划为一类后就不再被分划开，这类算法也成为谱系聚类法。

依据准则函数动态聚类的算法
设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。
算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类算法有--C均值法、ISODATA法等

根据相似性阙值的简单聚类方法

1. 根据相似性阙值和最小距离原则的简单聚类方法
2. 最大最小距离算法

谱系聚类法
按最小距离原则不断进行两类合并，也称为层次聚类法，系统聚类法

模式识别与机器学习(一)