模式识别电子教材-北京航空航天大学

第一章

引论

1·1

概述

1.1.1模式识别

模式识别(PatternRecognition)：确定一个样本的类别属性（模式类）的过程，即把某一样本归属于多个类型中的某个类型。

样本（Sample)：一个具体的研究（客观）对象。如患者，某人写的一个汉字，一幅图片等。

模式(Pattern)：对客体（研究对象）特征的描述（定量的或结构的描述），是取自客观世界的某一样本的测量值的集合（或综合）。

特征(Features)：能描述模式特性的量（测量值）。在统计模式识别方法中，通常用一个矢量表示，称之为特征矢量，记为

模式类(Class)：具有某些共同特性的模式的集合。

1.1.2

模式识别系统

⑴

特征提取

从模式空间中选择最有利于模式分类的量作为特征，压缩模式维数，以便于处理，减少消耗。

特征提取一般以分类中使用的某种判决规则为准则。所提取的特征使在某种准则下的分类错误最少。为此需要考虑特征之间的统计关系，选用适当的正交变换，才能提取出最有效的特征。

⑵

特征选择

特征选择同样需要某种分类准则，在该准则下选择对分类贡献较大的特征，删除贡献较小的那些特征。

⑶

学习和训练

根据已知类别的样本确定分类判决准则矫正特征提取选择方法等

⑷

分类识别

分类是把特征空间划分成类型空间。

把未知类别属性的样本确定为类型空间里的某一类型。

分类错误率越小越好，分类错误率的分析和计算比较困难。

影响分类错误率的因数

–

分类方法

–

分类器设计

–

提取的特征

–

样本质量等

1.1.3模式识别的基本方法

㈠

统计模式识别

理论基础：概率论，数理统计

主要方法：线性、非线性分类、Bayes决策、聚类分析

主要优点：

1）比较成熟

2）能考虑干扰噪声等影响

3）识别模式基元能力强

主要缺点：

1）对结构复杂的模式抽取特征困难

2）不能反映模式的结构特征，难以描述模式的性质

3）难以从整体角度考虑识别问题

㈡

句法模式识别

模式描述方法：

符号串，树，图

模式判定：

是一种语言，用一个文法表示一个类，m类就有m个文法，然后判定未知模式遵循哪一个文法。

在学习过程中，确定基元与基元之间的关系，推断出生成景物的方法。

判决过程中，首先提取基元，识别基元之间的连接关系，使用推断的文法规则做句法分析。若分析成立，则判断输入的景物属于相应的类型。

理论基础：形式语言，自动机技术

主要方法：自动机技术、CYK剖析算法、Early算法、转移图法

主要优点：

1）识别方便，可以从简单的基元开始，由简至繁。

2）能反映模式的结构特征，能描述模式的性质。

3）对图象畸变的抗干扰能力较强。

主要缺点：当存在干扰及噪声时，抽取特征基元困难，且易失误。

㈢

模糊模式识别

模式描述方法：

模糊集合

A={(a,a),(b,b),...(n,n)}

模式判定：

是一种集合运算。用隶属度将模糊集合划分为若干子集，

m类就有m个子集，然后根据择近原则分类。

理论基础：模糊数学

主要方法：模糊统计法、二元对比排序法、推理法、模糊集运算规则、模糊矩阵

主要优点：由于隶属度函数作为样本与模板间相似程度的度量，故往往能反映整体的与主体的特征，从而允许样本有相当程度的干扰与畸变。

主要缺点：准确合理的隶属度函数往往难以建立，故限制了它的应用。

㈣

人工神经网络法

模式描述方法：

以不同活跃度表示的输入节点集（神经元）

模式判定：

是一个非线性动态系统。通过对样本的学习建立起记忆，然后将未知模式判决为其最接近的记忆。

理论基础：神经生理学，心理学

主要方法：BP模型、HOP模型、高阶网

主要优点：可处理一些环境信息十分复杂，背景知识不清楚，推理规则不明确的问题。允许样本有较大的缺损、畸变。

主要缺点：模型在不断丰富与完善中，目前能识别的模式类还不够多。

㈤

人工智能方法

模式描述方法：

字符串表示的事实

模式判定：

是一种布尔运算。从事实出发运用一系列规则，推理得到不同结果，m个类就有m个结果。

理论基础：演绎逻辑，布尔代数

主要方法：产生式推理、语义网推理、框架推理

主要优点：已建立了关于知识表示及组织，目标搜索及匹配的完整体系。对需要众多规则的推理达到识别目标确认的问题，有很好的效果。

主要缺点：当样本有缺损，背景不清晰，规则不明确甚至有歧义时，效果不好。

1·2

特征矢量和特征空间

特征矢量：

设一个研究对象的个特征量测量值分别为

,我们将它们作为一个整体来考虑,让它们构成一个维特征矢量。

特征空间:

各种不同取值的特征矢量的全体构成了维特征空间。

注：特征矢量就是特征空间中的一个点。

1·3

随机矢量的描述

㈠随机矢量的分布函数

设为随机矢量，

为确定性矢量。

随机矢量的联合概率分布函数定义为

(

1-3-1)

写成矢量形式

(

1-3-2)

约定，

随机矢量的联合概率密度函数定义为

(

1-3-3)

设集合由类模式组成，第类记为。类的模式特征矢量的分布函数及密度函数分别定义为

(

1-3-4)

(

1-3-5)

㈡随机矢量的数字特征

⑴均值矢量(期望矢量)

维随机矢量的数学期望定义为

(

1-3-6)

其中，的分量i是各随机分量的均值，即

(

1-3-7)

式中，是的第个分量的边缘密度。

⑵条件期望

在模式识别中，经常以类别作为条件（即，），在这种情况下随机矢量的条件期望矢量定义为

(

1-3-8)

⑶协方差矩阵

随机矢量的自协方差矩阵

表征各分量围绕其均值的散布情况及各分量间的相关关系，其定义为

(

1-3-9)

式中是的个分量与第个分量的协方差，当时，便是的方差。

(

1-3-10)

⑷自相关矩阵

随机矢量的自相关矩阵定义为

(

1-3-11)

由定义可知，的协方差矩阵和自相关矩阵间的关系是

(

1-3-12)

⑸相关系数

(

1-3-13)

由布尼亚科夫斯基不等式知

所以

(

1-3-14)

相关系数矩阵定义为

⑹协方差矩阵的非负定性

显然，协方差矩阵和自相关矩阵都是对称矩阵。设为对称矩阵，对任意的矢量，是的二次型。若对任意的恒有

则称为非负定矩阵。如果对任意的，恒有

则称为正定矩阵。对于正定矩阵，各阶主子式非零(包括)。协方差矩阵是非负定的。

㈢随机变量、随机矢量间的统计关系

⑴不相关

随机矢量的第个分量和第个分量若有

（协方差为0）

则称它们不相关。和不相关等价于

(

1-3-15)

随机矢量和不相关的充要条件是互协方差矩阵，亦即

(

1-3-16)

⑵正交

随机矢量和若满足

(

1-3-17)

则称和正交。

⑶独立

随机矢量和的联合概率密度函数若满足

(

1-3-18)

则称和独立。

（4）两者关系

独立必不相关，反之不然。独立性是比不相关性更强的条件。

㈥随机矢量的变换

设随机矢量是另一随机矢量的函数，即

若它们的函数关系一一对应，这两个随机矢量的概率密度函数之间有关系

式中，雅可比行列式

(

1-3-19)

J表示变换后体积微元的变化，坐标系中体积微元，表示的绝对值。当和之间只是线性变换时，

此时，，表示矩阵取行列式，从而随机矢量的概率密度函数

式中表示行列式取绝对值。

设的均值矢量为，协方差矩阵为，则的均值矢量

的协方差阵

1·4

正态分布

在概率论、数理统计及决策理论的研究和应用中，正态分布是一种最重要的分布。

㈠正态分布的定义

⑴一维随机变量的正态分布

正态分布的一维随机变量的概率密度函数定义为

(

1-4-1)

式中，为随机变量的数学期望，是的方差。它们分别由下式定义和算得

(

1-4-2)

(1-4-3)

随机变量的概率密度函数由两个参数和就可以完全确定，可记为

～或～

任何随机变量的概率密度函数都满足下式，正态分布的随机变量也不例外。

(

1-4-4)

(

1-4-5)

随机变量在其均值周围散布。在以为中心的区间中出现的概率

所以越大，随机变量的取值的分散程度也越大。

图

(1-4-1)

(a)

二维正态分布概密函数，(b)

二维正态分布等概密点轨迹

⑵多变量正态分布

元正态分布的随机矢量的概率密度函数定义为

(

1-4-6)

式中，为的数学期望矢量，为的协方差矩阵。

(

1-4-7)

(

1-4-8)

它们的元素

(

1-4-9)

(

1-4-10)

式中，和为的边缘分布概密，为随机矢量各分量定义域的直积空间。易知为对称正定矩阵。

㈡多元正态分布的性质

多元正态分布有许多易于分析和十分有用的性质，下面给出一些重要的内容。

⑴正态分布完全由和确定

元正态分布随机矢量的概率密度函数由均值矢量的个分量和协方差阵的个独立阵元所完全确定。多元正态分布的随机矢量常简记为

～或～。

⑵等概率密度点的轨迹为一超椭球面

由式(1-4-6)可知，当指数为常数时，的值不变，因此等概率密度点应满足

常数

(

1-4-11)

易证上式的解是一个超椭球面，其中心为，椭球面的形状由确定，取不同的就对应不同的超椭球面，每个等概密椭球面的主轴在协方差矩阵的特征矢量方向上，其长度与相应的特征值的方根成正比。上式中的值称为到的马氏(Mahalanobis)距离，对应于马氏距离为的超椭球的体积为

(

1-4-12)

其中是维单位超球体的体积

可知，对于取定的维数，的散布程度只与有关。

由所定义的椭球体包含的概率值，其中是自由度为的-分布的上百分位数。

⑶对于正态分布，不相关与独立是等价的

如果多元正态分布随机矢量的两个分量和之间是不相关的，则它们之间一定是独立的。这是因为若和不相关，由定义，它们的协方差，从而协方差阵成为对角阵

进而

因此

(

1-4-13)

上式正是独立性的充要条件，从而证明了上面等价性的结论。

⑷多元正态随机矢量的边缘概密和条件概密仍是正态分布

下面只给出二元情况的证明，更多元的情况是类似的。由

可得

由定义可算得

(

1-4-14)

同理，可以推出～。

由贝叶斯定理

(

1-4-15)

并由上面推导可知，可表为

～

(

1-4-16)

同理也可以导出的函数形式。

一般性的结论是，设～，，，，在条件下，的条件概密函数

～

(

1-4-17)

这里、的维数与的行数相同，、的维数与的行数相同。

⑸多元正态随机矢量的线性变换仍为多元正态随机矢量

证：

设～，为非奇异阵，令，有，雅可比行列式，于是的概率密度函数与的概率密度函数之间的关系为

上式中的表示行列式取绝对值，由于

由上面诸式可得

即得证

～

由于是对称阵，必存在非奇异矩阵，使的协方差阵为对角阵，此时的各分量彼此独立。这表明可以通过某种变换使变换后的各分量相互独立。

更一般的有，如果～，是秩为的矩阵，，则服从正态分布。

⑹

多元正态随机矢量的分量的线性组合是一正态随机变量

这实际上是性质⑸简单的引论。若～，则是一个正态随机变量，～。令为非奇异阵，

由性质⑸知，～，又由性质⑷知，～。

习题

（1.1）试证明，对于正态分布，不相关与独立是等价的。

（1.2）试证明，多元正态随机矢量的线性变换仍为多元正态随机矢量。

（1.3）试证明，多元正态随机矢量的分量的线性组合是一正态随机变量。

第二章

聚

类

分

析

2·1

聚类分析(ClusteringAnalysis)的概念

㈠

基本思想

根据各个待分类的模式特征相似程度进行分类，相似的归为一类。

是无监督分类。

㈡

特征量的类型

由于分类对象或目的不同，对象的特征数值化结果有下述三种类型：

⒈

物理量：直接反映特征的实际物理意义，如长度、重量、速度等。处理前需要对这些连续量离散化。

⒉

次序量：按某种规则确定的特征的等级，它只反映次序关系。是离散量，如产品的等级、人的学识、技能的等级、病症的级或期。

⒊

名义量：用数字代表的各种状态。如男性与女性、事物的状态、种类等，无数量含义，也无次序关系。

㈢

方法的有效性

取决于模式特征点在特征空间中的分布情况。如果特征点按类群聚，则分类方法一般是有效的，反之则否。

应重新提取特征，选取它们之间显著不同的特征。

⒈

特征选取不当使分类无效

图(2-1-1)(a)所示

⒉

特征选取不足可能使不同类别的模式判为一类

如图(2-1-1)(b)，

图(2-1-1)

⒊

特征选取过多可能无益反而有害，增加分析负担并使分析效果变差

若新增加的特征和原有特征是相关的，这样并没有引入更多的有用信息但增加了数据的冗余。除了计算量增加外，更为严重的是，由于多了一些相关的特征，可能使对不同类具有显著差别的重要特征在各种特征“总合”中占的比重变小。引入对各类均无显著差别的特征也会产生这个问题。

特征量纲选取：应尽量选用不受量纲影响的相似性测度。

2·2

模式相似性测度

定义模式相似性测度，描述各模式之间特征的相似程度。

㈠

距离测度(差值测度)

两矢量的距离定义应满足下面的公理：设矢量和的距离记为，

⑴

，当且仅当时，等号成立，即；

⑵

；

⑶

；

需要指出，模式识别中定义的某些距离测度不满足⑶，只是在广义意义上称之为距离。下面给出距离测度的几种具体算式。

设，。

⑴

欧氏(Euclidean)距离

(

2-2-1)

⑵

绝对值距离(街坊距离或Manhattan距离)

(

2-2-2)

⑶

切氏(Chebyshev)距离

(

2-2-3)

⑷

明氏(Minkowski)距离

(

2-2-4)

由上面各式可以看出，⑴、⑵、⑶实际上是⑷当、、的特殊情况。在实际中较多地使用欧氏距离。

显然，量纲

“影响作用比重”

例如：和分别表示长度和重量，

长度：毫米，米，

重量：公斤，克。

图(2-2-1)：特征量纲对聚类结果的影响

⑸

马氏(Mahalanobis)距离

设维矢量和是矢量集中的两个矢量，它们的马氏距离定义为

①

(

2-2-5)

式中

(

2-2-6)

(

2-2-7)

容易证明，马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，另外，由于的含义是这个矢量集的协方差阵的统计量，所以马氏距离对特征的相关性也作了考虑。

一般地讲，设、是从期望矢量为、协方差矩阵为的母体中抽取的两个样本，它们间的马氏距离定义为

②

(

2-2-8)

当将和视作两个数据集中的样本时，设是它们的互协方差阵，作为另一种情况的马氏距离的定义是

③

(

2-2-9)

当、、为单位矩阵时，马氏距离和欧氏距离是等价的。前已讲过，在正态分布中，等概密点轨迹是到均矢的马氏距离为常数的点所组成的超椭球面，但此超椭球面各点到的欧氏距离非常数。

例：已知一二维正态母体的分布为

求点和至均值点的距离。

解：由题设，可得

从而马氏距离

它们之比达倍，若用欧氏距离，算得的距离值相同。

由分布函数知，、两点的概率密度分别为

⑹

Camberra距离(Lance距离、Willims距离)

(

2-2-10)

该距离能克服量纲引起的问题，但不能克服分量间的相关性。

以上定义的各种相似性测度算式属距离测度，两模式越相似，其测度值越小。

（二）相似测度

这类测度是以两矢量的方向是否相近作为考虑的基础，矢量长度并不重要。

⑺

角度相似系数(夹角余弦）

矢量之间的相似性可用它们的夹角余弦来度量。两个矢量和的夹角余弦

(

2-2-11)

它对于坐标系的旋转和尺度的缩放是不变的(因矢量的长度已规格化),但对一般性的线性变换和坐标系的平移不具有不变性。

⑻

相关系数

它实际上是数据中心化后的矢量夹角余弦。

(

2-2-12)

此处将、视作两个数据集的样本，和分别是这两个数据集的平均矢量。相似系数对于坐标系的平移、旋转和尺度缩放是不变的。

⑼

指数相似系数

(

2-2-13)

式中为相应分量的协方差，为矢量维数。它不受量纲变化的影响。

⑽

当各特征值非负时，还可定义下列几种相似系数

(

2-2-14)

(

2-2-15)

(

2-2-16)

以上各种定义式均属相似测度，两个模式特征矢量越相似，其值越大，上限为1。

㈢

匹配测度

特征只有两个状态:0=>

有此特征;1=>

无此特征。成称之为二值特征

对于给定的二值特征矢量和中的某两个相应分量与，

若和，则称与是(1-1)匹配；

若和，则称与是(1-0)匹配；

若和，则称与是(0-1)匹配；

若和，则称与是(0-0)匹配。

令

与的(1-1)匹配的特征数目

与的(0-1)匹配的特征数目

与的(1-0)匹配的特征数目

与的(0-0)匹配的特征数目

对于二值维特征矢量可定义如下相似性测度：

⑾

Tanimoto测度

(

2-2-17)

可以看出，等于和共同具有的特征数目与和分别具有的特征种类总数之比。这里只考虑(1-1)匹配而不考虑(0-0)匹配。

例：，

可得

,

,

则

⑿

Rao测度

(

2-2-18)

上式等于(1-1)匹配特征数目和所选用的特征数目之比。

⒀

简单匹配系数

(

2-2-19)

上式表明，这时匹配系数分子为(1-1)匹配特征数目与(0-0)匹配特征数目之和，分母为所考虑的特征数目。

⒁

Dice系数

(

2-2-20)

⒂

Kulzinsky系数

(

2-2-21)

上式分子为(1-1)匹配特征数目，分母为(1-0)和(0-1)匹配特征数目之和即不匹配特征数目之和。

上面给出了许多相似性测度的具体定义式，它们各具特点，我们在实际使用时应根据具体问题进行选择。建立了模式相似性测度之后，两个模式的相似程度就可用数值来刻划了，据此便可以进行分类和识别。

2·3

类的定义与类间距离

2.3.1

类的定义

这里，两个模式相似性测度只取距离而论，对于相似测度、匹配测度也可以类似定义。

设，集合中任两个元素、的距离为，,r为给定的阈值，为集合中元素个数。

定义1：（最大点-点间距离）≤h，称对于阈值组成一类。

定义2：（最大点-点间平均距离）≤h，称对于阈值组成一类。

定义3：（点-点间平均距离）≤h，称对于阈值，r组成一类。

定义4：（最小点-点间距离）≤h，，称对于阈值组成一类。适用于链状情况。

定义5：（类间距离）≤h，称对于阈值组成一类。

若将集合任意分成两类、，这两类间的距离满足

类的划分具有人为规定性，这反映在定义的选取及、的选择上。一个分类结果的优劣最后只能根据实际来评价，应尽可能地分析对象的先验知识才能选择适当的类的定义，从而使分类结果更符合实际。

2.3.2

类间距离测度方法

在有些聚类算法中要用到类间距离，下面给出一些类间距离定义方式。

⑴

最近距离法

两个聚类和之间最近距离定义为

(

2-3-5)

式中，表示和之间的距离。

如果是由和两类合并而成的，则有递推公式：

(

2-3-6)

⑵

最远距离法

两个聚类和之间的最远距离定义为

(

2-3-7)

如果是由和两类合并而成的，则有递推公式

(

2-3-8)

⑶

中间距离法

设类到和的距离分别为和，到的距离为。以这三个距离值为边长作三角形，如图(

2-3-1

)所示，在中，边的中线长的平方等于，以其作为新类与间的距离，即有递推公式

(

2-3-9)

其值介于最近距离和最远距离之间。

图

(2-3-1)

⑷

重心距离法

从物理的观点看，一个类的空间位置若要用一个点表示，那么用它的重心代表较合理。于是类与类之间的距离定义为它们重心之间的距离。设类、的重心分别为、，它们分别有样本、个。将和合并为，则有个样本，易知的重心

(

2-3-10)

设另一类的重心为，则它与的距离平方是

利用

最后有

(

2-3-11)

⑸

平均距离法

两类和之间距离平方也可定义为这两类元素两两之间的平均平方距离，即

(

2-3-12)

设，类平均距离的递推公式为

(

2-3-13)

谱系聚类法中运用该距离定义效果较好。

⑹

离差(散布Scatter)平方和法

设类的重心是，类内离差平方和为

(

2-3-14)

两类合并后，要变大。把两类合并所增加的离差平方和定义为两类平方距离，即当时，定义。可以证明，此时的有

(

2-3-15)

式中，、分别为、的重心，、分别为、的模式个数。离差平方和法的递推公式为

(

2-3-16)

这里，，、、和分别表示、、和所含样本数。

上述的各种类间距离定义的递推公式可以统一成如下公式：

(

2-3-17)

这里。上式中各项系数取不同的值，便可得不同的类间距离递推公式。建立通式的意义在于给编程带来方便。

最近距离法

最远距离法

中间距离法

重心距离法

平均距离法

可变平均法

可变法

离差平方和法

表

(2-3-1)

上表利用了公式

(

2-3-18)

(

2-3-19)

2.3.3

聚类的准则函数

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

需要一个能对分类过程或分类结果的优劣进行评估的准则函数。

⑴

类内距离准则（误差平方和准则）

设待分类模式集=在某种相似性测度基础上被分划为类，其中，类别序号，类内模式序号，，类内距离准则函数定义为

(

2-3-20)

式中，表示类的模式均值矢量

(

2-3-21)

式(2-3-20)刻划了各模式到其被指判的类的类心距离平方和。我们的目标是使。这种准则也称为误差平方和准则。

显然，是模式和类心的函数，在样本集给定条件下，的值取决于类心的选取。

适用于同类样本比较密聚，且各类样本数目差别不大的情况。

加权类内距离准则

(

2-3-22)

(

2-3-23)

式中，表示类内任两个模式距离平方和，共有个组合数，所以表示类内两模式间的均方距离。N为待分类模式总数，表示类先验概率的估计──频率。

⑵

类间距离准则

用总的类间距离最大作为聚类的准则。

(

2-3-24)

这里

（类的模式平均矢量，为类所含模式个数）

（为总的模式平均矢量）

加权的类间距离准则定义为

(

2-3-25)

对于两类问题，类间距离有时取

(

2-3-26)

和的关系是

(

2-3-27)

⑶

基于类内距离类间距离的准则函数

希望：类内距离越小越好、类间距离越大越好。为此构造能反映出类内距离和类间距离的准则函数。

的类内离差阵（ScatterMatrix）定义为

(

2-3-28)

总的类内离差阵定义为

(

2-3-30)

类间离差阵定义为

(

2-3-31)

总的离差阵定义为

(

2-3-33)

SB、SW和ST有下面的关系

ST=SW+SB

(2-3-34)

证明：

聚类的基本目标是使及。利用矩阵的迹和行列式以及正交变换的性质，可以定义如下聚类准则函数

(

2-3-35)

由它们的构造可以看出，为得到好的聚类结果，应该使它们尽量的大。这类准则也大量用在特征提取和选择中。

2·4

聚类的算法

2.4.1

聚类的技术方案

⑴

简单聚类

根据相似性阈值和最小距离原则聚类

xi∈={

x1,x2,…,xn}=

12…c；

if

D(xi,mj)≤T,

mj=(1/nj)xi(j)，xi(j)

∈j，nj是j中的样本个数，T是给定的阀值。

Then

xi∈i

类心一旦确定将不会改变。

⑵

谱系或层次聚类

按最小距离原则不断进行两类合并

类心不断地修正，但模式类别一旦指定后就不再改变。

⑶

依据准则函数动态聚类

影响聚类结果的主要因数：类心、类别个数、模式输入顺序。

所谓动态聚类，是指上述因数在聚类过程中是可变的。

规定一些分类的目标参数，定义一个能刻划聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。这类方法有—均值法、ISODATA法、近邻函数法以及运用图论理论的最小张树法。

2.4.2

简单聚类方法

㈠根据相似性阈值和最小距离原则的简单聚类方法

⒈条件及约定

设待分类的模式为，选定类内距离门限。

⒉算法思想

计算模式特征矢量到聚类中心的距离并和门限比较而决定归属该类或作为新的一类中心。通常选择欧氏距离。

⒊算法原理步骤

⑴取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类的中心。

⑵计算下一个模式特征矢量到的距离。若，则建立新的一类，其中心；若，则。

⑶假设已有聚类中心，计算尚未确定类别的模式特征矢量到各聚类中心的距离，如果，则作为新的一类的中心，；否则，如果

(

2-4-1)

则指判。检查是否所有的模式都分划完类别，如都分划完了则结束；否则返到⑶。

⒋性能

计算简单。

聚类结果很大程度上依赖于距离门限的选取、待分类特征矢量参与分类的次序和聚类中心的选取。

当有特征矢量分布的先验知识来指导门限及初始中心的选取时，可以获得较合理结果。

⒌改进

通常采用试探法，选用不同的门限及模式输入次序来试分类，并对聚类结果进行检验,即用聚类准则函数J1。例如，计算每一聚类中心与该类中最远样本点的距离，或计算类内及类间方差，用这些结果指导及的重选。最后对各种方案的划分结果进行比较，选取最好的一种聚类结果。

图

(2-4-1)

距离阈值及初始类心对聚类的影响

㈡最大最小距离算法

⒈条件及约定

设待分类的模式特征矢量集为，选定比例系数。

⒉基本思想

在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。这种方法通常也使用欧氏距离。

⒊算法原理步骤

⑴

选任一模式特征矢量作为第一个聚类中心。例如，。

⑵

从待分类矢量集中选距离最远的特征矢量作为第二个聚类中心。例如图(

2-4-2)中最大，取。

⑶

计算未被作为聚类中心的各模式特征矢量与、之间的距离并求出它们之中的最小值，即

(

2-4-2)

为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。

⑷

若

(

2-4-3)

则相应的特征矢量作为第三个聚类中心，。此例中。然后转至⑸；否则，转至最后一步⑹。

⑸

设存在个聚类中心，计算未被作为聚类中心的各特征矢量到各聚类中心的距离,并算出

(

2-4-4)

如果，则并转至⑸；否则，转至最后一步⑹。

⑹

当判断出不再有新的聚类中心之后，将模式特征矢量按最小距离原则分到各类中去，即计算

(

2-4-5)

当，则判。在此例中，，；，；，。

这种算法的聚类结果与参数以及第一个聚类中心的选取有关。如果没有先验知识指导和的选取，可适当调整和，比较多次试探分类结果，选取最合理的一种聚类。

图

(2-4-2)

最大最小距离算法举例

2.4.3

谱系聚类法(HierarchicalClusteringMethod)(系统聚类法、层次聚类法）

效果较好、是常用方法之一。

⒈

条件及约定

设待分类的模式特征矢量为，表示第k次合并时的第类。

⒉

基本思想

首先将个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。

⒊

算法步骤

⑴

初始分类。令，每个模式自成一类，即。

⑵

计算各类间的距离，生成一个对称的距离矩阵，为类的个数。

⑶

找出前一步求得的矩阵中的最小元素，设它是和间的距离，将和两类合并成一类，于是产生新的聚类，令。

⑷

检查类的个数。如果类数大于2，令，转至⑵；否则，停止。

如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类可以同时合并。上述算法步骤给出了从类至类的完整聚类过程，

停止条件

以类间距离门限作为停止条件，即取距离门限，当中最小阵元大于时，聚类过程停止；

以预定的类别数目作为停止条件，当类别合并过程中，类数等于预定值时，聚类过程停止。

类间距离的定义与递推

在该算法中可以采用上节已详细介绍过的不同的类间距离定义方式，并使用类间距离递推公式。所采用的类间距离定义不同，聚类过程及结果是不一样的。上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有单调不减关系则称类间距离对并类具有单调性。最近距离法、最远距离法、平均法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。

算法特点

聚类过程中类心不断地调整，但某一模式一旦分划到某一类中就不再改变。

从粗到细的层次聚类

这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式按类至类进行谱系分解，这里不作介绍了。聚类过程可以表示成一个树图。

例：给出个样本特征矢量如下，按最小距离原则进行聚类。

解：

⑴

将每一样本看成自成一类

计算距离矩阵(表

2-4-1)。

⑵

中最小阵元为它是与之间的距离，将它们合并为一类，得一新的分类为

计算合并后的距离矩阵(表

2-4-2)。在这里使用了距离递推公式，如

与距离，与距离

⑶

中距离最小者为它是与间的距离，合并和，得新的分类

同样计算(表

2-4-3)，进一步聚类得

即

计算(表

2-4-4)。

⑷

由表可知，、和可以一起合并成一类。

表(2-4-1)

表(2-4-2)

表(2-4-3)

表(2-4-4)

2.4.4

动态聚类法(Dynamicclusteringalgorithm)

最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了，这类方法效果一般不会太理想。和上述各算法相对应有一种动态聚类法。其要点为：

⑴

确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为，协方差阵为，则模式和该类的距离平方为与该类均矢的马氏距离

⑵

确定评估聚类质量的准则函数。

⑶

确定模式分划及聚类合并或分裂的规则。

动态聚类算法的基本步骤：

⑴

建立初始聚类中心，进行初始聚类；

⑵

计算模式和类的距离，调整模式的类别；

⑶

计算各聚类的参数，删除、合并或分裂一些聚类；

⑷

从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止。

动态聚类原理框图如下：

图

(2-4-3)

㈠

—均值法(—means)

⒈条件及约定

设待分类的模式特征矢量集为，类的数目是取定的。

⒉基本思想

取定c个类别和选取个初始聚类中心，按最小距离原则将各模式分配到类中的某一类，不断地计算类心和调整各模式的类别使每个模式特征矢量到其所属类别的距离平方之和最小

⒊算法步骤

⑴

任选个模式特征矢量作为初始聚类中心：。

⑵

将待分类的模式特征矢量集中的模式逐个按最小距离原则分划给类中的某一类，即

如果

(

2-4-6)

则判

。

式中表示和的中心的距离，上角标表示迭代次数。于是产生新的聚类。

⑶计算重新分类后的各类心

(

2-4-7)

式中为类中所含模式的个数。

因为这一步采取平均的方法计算调整后类的中心，且定为类，故称一均值法。

⑷如果()，则转至⑵；如果，则结束。

⒋

分析

我们以欧氏距离为例，简单地分析该算法的可收敛性。在上述算法中，虽然没有直接运用准则函数

(

2-4-8)

进行分类，但在⑵中根据式(2-4-6)进行模式分划可使趋于变小。设某样本从聚类移至聚类中，移出后的集合记为，移入后的集合记为。设和所含样本数分别为和，聚类、、和的均矢分别为、、和，显然有

(

2-4-9)

(

2-4-10)

而这两个新的聚类的类内欧氏距离(平方)和与原来的两个聚类的类内欧氏距离(平方)和的关系是

(

2-4-11)

(

2-4-12)

当距比距更近时，使得

(

2-4-13)

由式(2-4-11)、(2-4-12)及(2-4-13)可知，将分划给类可使变小。这说明在分类问题中不断地计算新分划的各类的类心，并按最小距离原则归类可使值减至极小值。在上述算法中，也可以利用式(2-4-13)进行模式类别的重新分划。

⒌

性能

算法简单，收敛（已于1974年和1967年分别给出了严格证明）。

如模式分布呈现类内团聚状，该算法是能达到很好聚类结果的，故应用较多。

能使各模式到其所判属类别中心距离(平方)之和为最小的最佳聚类。

以确定的类数、模式输入次序及选定的初始聚类中心为前提，受此限制结果只是局部最优。

⒍

改进

⑴

的调整

作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。

在类别数未知的情况下，可使类数由较小值逐步增加，对于每个选定的分别使用该算法。显然准则函数是随的增加而单调减少。在增加过程中，总会出现使本来较密集的类再拆开的情况，此时J虽减小，但减小速度将变缓。如果作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。另一种方法是利用问题的先验知识分析选取合理的聚类数。

⑵初始聚类中心选取

初始聚类中心可按以下几种方法之一选取：

①凭经验选择初始类心。

②将模式随机地分成类，计算每类中心，以其作为初始类心。

③（最大密度），求以每个特征点为球心、某一正数为半径的球形域中特征点个数，这个数称为该点的密度。选取密度最大的特征点作为第一个初始类心，然后在与大于某个距离的那些特征点中选取具有“最大”密度的特征点作为第二个初始类心，如此进行，选取个初始聚类中心。

④

用相距最远的个特征点作为初始类心。具体地讲，是按前述的最大最小距离算法求取个初始聚类中心。

⑤

当较大时，先随机地从个模式中取出一部分模式用谱系聚类法聚成类，以每类的重心作为初始类心。

⑥设已标准化的待分类模式集为，希望将它们分为类。令模式

，定义

(

2-4-14)

且令

(

2-4-15)

(

2-4-16)

计算

(

2-4-17)

显然，若最接近整数，则把分划至中。对所有样本都实行上述处理，就可实现初始分类，从而产生初始聚类中心。

⑶用类核代替类心

前面的算法存在一个不足，即是只用一个聚类中心点作为一类的代表，但是一个点往往不能充分地反映该类的模式分布结构，从而损失很多有用的信息。当类的分布是球状或近似球状时，算法尚能有较好的效果，但对于如图(2-4-4)所示的那种各分量方差不等的正态分布而两类的主轴和类心又是那样的情况，分类效果就不好了，点应属于类，但由于它距类的均矢更近，按前述的算法则被指判到类。如果已知各类模式分布的某些知识，则可以利用它们指导聚类。为此，我们定义一个类核函数表示类的模式分布情况，其中关于类的一个参数集，是维空间中的特征矢量，可以是一个函数、一个点集或其他适当的模型。为了刻划待识模式和类的接近程度还应规定一个模式特征矢量到核的距离。实际上，马氏距离就是核函数距离的一种简化。

当已知某类的分布近似为正态分布时，可以用以这类样本统计估计值为参数的正态分布函数作为核函数，即

(

2-4-18)

其中

，

，

式中为进行参数估计的该类样本数。则模式与该类的距离为

(

2-4-19)

这实际上是第四章将要讨论的最小误判概率准则下先验概率相同时的判决函数。

当已知各类样本分别在相应的主轴附近分布时，可以定义主轴核函数：

(

2-4-20)

式中，是由和类的统计协方差阵的个最大特征值所对应的已规格化的特征矢量作成的矩阵，即是协方差阵给出的部分主轴系统，给出了样本分布的主轴方向(散布的情况由特征值反映出来)。为轴上的单位矢量。设是类样本的均值矢量，求一点和一个轴的距离可见图(

2-4-5)。模式和类间的距离平方可以用和该类的主轴间的欧氏距离平方来度量。

(

2-4-21)

(a)

各分量方差不等的正态分布

(b)

沿主轴分布

图

(2-4-4)

类的模式分布情况的示例

图

(2-4-5)

求和主轴距离示意图

例：模式分布如图(2-4-6)所示，试用一均值法进行聚类，取=2。

⑴

选

⑵

因

，故

，故

，故

……

得

，；，

⑶

计算新的聚类中心

⑷

因，故转至⑵。

⑵'

由新的聚类中心，得

故得

，

，

⑶'

计算聚类中心

⑷'

因，故转至⑵。

⑵"

求得的分类结果与前一次的结果相同，。

⑶"

各聚类中心必然也与前一次的相同，。

因，不再出现新的类别划分，故分类过程结束。

㈡

改进的—均值法

文献【10】基于核函数的概念提出了一种改进的—均值法，其分类性能要好于通常计算模式到类的距离时采用这个模式到类心的欧氏距离或马氏距离的—均值法。

由于—均值法我们已作详细介绍，这种改进的—均值法只简单表述如下：

⑴

对给定的待分类模式集进行初始分划产生类；

⑵

计算各聚类所含模式数、均值矢量和协方差阵；

⑶

将各模式按最小距离原则分划到某一聚类中。这里采用最小误判概率准则下正态分布情况的判决规则，计算模式到的距离

(

2-4-22)

如果

则判

⑷如果没有模式改变其类别，则停止算法；否则转至⑵。

（三）

ISODATA(迭代自组织数据分析)算法

(IterativeSelf-OrganizingDataAnalysisTechniquesAlgorithm)

特点：具有启发性推理、分析监督、控制聚类结构及人机交互。

⒈

条件及约定

设待分类的模式特征矢量为，算法运行前需设定7个初始参数。

⒉

算法思想

在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。

⒊

算法原理步骤

⑴

预置

①

设定聚类分析控制参数：

=预期的类数，

=初始聚类中心个数(可以不等于)，

=每一类中允许的最少模式数目(若少于此数就不能单独成为一类)，

=类内各分量分布的距离标准差上界(大于此数就分裂)，

=两类中心间的最小距离下界(若小于此数，这两类应合并)，

=在每次迭代中可以合并的类的最多对数，

=允许的最多迭代次数。

②

将待分类的模式特征矢量读入。

③

选定初始聚类中心，可从待分类的模式特征矢量集中任选个模式特征矢量作为初始聚类中心。

⑵按最小距离原则将模式集中每个模式分到某一类中，即

如果

(

2-4-23)

则判

式中表示和类的中心之间的距离。

⑶依据判断合并。如果类中样本数，则取消该类的中心，，转至⑵(或计算，将并入距离最近的那一类中；这时，转至⑵。

⑷

计算分类后的参数:各类中心、类内平均距离及总体平均距离。

①

计算各类的中心

(

2-4-24)

②

计算各类中模式到类心的平均距离

(

2-4-25)

③

计算各个模式到其类内中心的总体平均距离

(

2-4-26)

⑸

依据、判断停止、分裂或合并。

①

若迭代次数已达，则置转到⑼；否则转下。

②

若则转到⑹(将一些类分裂)；否则转下。

③

若,(则跳过分裂处理)转至⑼,否则转下。

⑤

若，当迭代次数是奇数时转至⑹(分裂处理)；迭代次数是偶数时转至⑼(合并处理)。

⑹

计算各类类内距离的标准差矢量

(

2-4-27)

其各分量

(

2-4-28)

式中，为分量编号，为类的编号，为矢量维数，是的第个分量，是的第个分量。

⑺

对每一聚类，求出类内距离标准差矢量中的最大分量

(

2-4-29)

⑻

在中，对任一，若有，同时又满足下面两个条件之一：

①

和

②

则将该类分裂为两个聚类，且令。这两个新类的中心和是这样构成的：和只是在中相应于的分量分别加上和减去，而其它分量不变，其中，的选取应使和仍在的类域空间中且其它类的模式到和距离较远，而原类中的模式和它们距离较小。分裂后，，转至⑵；否则，转下。

⑼

计算各对聚类中心间的距离

(

2-4-30)

⑽

依据判断合并。将与比较，并将小于的那些按递增次序排列，取前个，。从最小的开始，将相应的两类合并。若原来的两个类心为和，则合并后的聚类中心为

(

2-4-31)

（已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。

⑾

如果迭代次数已达次或过程收敛，则结束。否则，，若需要调整参数，则转至⑴；若不改变参数，则转至⑵。

我们将该算法的合并和分裂的条件归纳如下：

合并的条件：

(类内样本数)(类的数目)(两类间中心距离)。

分裂的条件：

(类的数目)(类的某分量标准差)

。

这里，表示“或”的关系；表示“与”的关系。如果类的数目有，当是奇数时分裂，当是偶数时合并。

由上述合并与分裂的判断条件可以看出算法初设的7个参数存在一定的相互制约。

例

：用ISODATA方法聚类图(2-4-7)中的数据

解：在本例中，。

⑴

设定参数和初始值

在无先验知识的情况下，可任意选取这些参数和初始值，然后在逐次迭代中加以调整。

⑵

因只有一个聚类中心，故

，

⑶

因，无合并。

⑷

计算聚类中心、类内平均距离和总的平均距离。

①

计算聚类中心

②

计算类内平均距离

③

计算总的平均距离

⑸

因不是最后一步迭代，且，转至⑹

⑹

求的标准差矢量

⑺

算得

⑻

因且将分裂成两类，取，则

，转至⑵

⑵'

按最小距离原则，新划分的类是

⑶'

因，无合并。

⑷'

计算类的中心、类内平均距离和总的平均距离

①

②

③

⑸'

因这是偶次迭代，满足算法原理步骤⑸中④的条件，故转⑼

⑼'

计算类间距离

由，类不能合并。

⑾'

因不是最后一次迭代(，题设)，，判断是否修改参数。由上面结果可知，已获得所要求类别数目，类间距离大于类内距离，每类样本数都有样本总数的足够大的百分比，因此不改变参数。

⑵"～⑷"

计算结果与前一次迭代结果相同。

⑸"

没有任一种情况被满足，到⑹。

⑹"

计算和的标准差矢量

⑺"

，

⑻"

，分裂条件不满足，转至⑼。

⑼"

与前一次迭代结果相同，

⑽"

无合并发生。

⑾"

，无新的变化，，转至⑵。

⑵"'～⑷"'

与前一次迭代结果相同。

⑸"'

因是最后一次迭代，令，转至⑼。

⑼"'

，同前。

⑽"'

因，无合并发生。

⑾"'

因是最后一次迭代，结束。

实际上，根据第三次迭代发现计算结果不变时，就可以结束算法。

图

(2-4-7)ISODATA算法例题中的模式集

第三章

代数类域界面方程法

3·1

用类域界面方程分类的概念

分类特征空间的分划寻求子空间的界面判别函数

判别函数的结构与参数的确定待识模式特征矢量代入判别函数后取值。

一个模式的维特征矢量对应于维特征空间中一个特征点

判别函数(discriminant

function)

特征点所在子空间可根据它的特征值代入界面方程中的函数后的取值而确定，因此表示界面的函数称为判别函数(discriminant

function)。

线性可分

如果界面是线性方程，即能用线性判别函数正确分类则称为线性可分，否则称为非线性可分。

例：如图(3-1-1)所示，一个模式特征矢量在特征空间平面中对应一个点。不同类别和的模式特征点在不同的类域(类子空间)中散布。首先根据已知类别的模式确定分划各类子空间的界面方程，在此例中，这个界面可以是一条直线：

若，则判

若，则判

若，则的归属不能判定或任判

图(3-1-1)

两类模式判别类域的界面

本章介绍线性与非线性判别函数的一般形式、判别规则及判别函数的产生算法等内容。

3·2

线性判别函数

在维特征空间中，特征矢量，线性判别函数的一般形式是

(

3-2-1)

式中,称为权矢量或系数矢量。写成矢量形式

(

3-2-2)

但这里，，，其中称为增广特征矢量，称为增广权矢量。此时的增广特征矢量的全体称为增广特征空间。

判别规则：

㈠

两类问题

对于两类问题，待识模式增广特征矢量可通过下面的判别规则进行分类。

判别规则：设为判别函数，

(

3-2-3)

上述规则中，表示若成立则成立。

㈡

多类问题

两类判别方法可推广到多类问题，有三个技术途径。

⑴

两分法

判别函数将类和类的模式分划开，于是，类问题转变为个两类问题。如果模式是线性可分的，一般需要建立个独立的判别函数。为了方便，可建立个判别函数。

(

3-2-4)

其中每个判别函数都具有下面的性质

(

3-2-5)

所以对于类问题，判决规则为

如果

则判

。

不确定区域

由两个界面和所分划的类域和类域可能会有部分重迭，类域和也可能会重迭，可能会同时出现两个或两个以上的判别式都大于零或所有的判别式都小于零的情况。出现在这种情况的区域中的点将不能判别出它们的类别，我们称这样的区域为不确定区，用IR表示，类别越多，不确定区也就越多。

由于不确定区的存在，仅用一个判别函数不能可靠地判别出，还必须有，通过多个不等式的联立，才能可靠地判别出。

例：设有一个二维三类问题，判别函数已求得：

，，

有一模式，欲判别其类别。可将该模式特征矢量代入上面三式，有

最后判。

⑵

两分法

对类中的任意两类和都建立一个判别函数，它将属于类的模式与属于类的模式区分开。由于从元中取元的组合数为，所以要分开类需要有个判别函数。通过训练得到的区分两类和的判别函数为

(

3-2-6)

它具有性质

(

3-2-7)

根据的正负不能作出是属于类还是属于类的判别，只能作出是位于含有类的半空间中还是位于含有类的半空间中，而在其中某一个半空间中还可能含有其他的类域。因此除之外还要根据其他的判别函数才能作出正确的判决，所以这种方法的判别规则是

如果

，

则判

这类方法仍然有不确定区。

例：设有一个二维三类问题，三个判别函数为

，

，

有待分类模式，将其代入有

上面三式等效为

，

，

由于，所以判。

⑶没有不确定区的两分法

对方法⑵中的判别函数作如下形式处理，令

(

3-2-8)

则等价于。于是，对类中的每一类均建立一个判别函数，类问题有个判别函数

(

3-2-9)

此种情况下，判别规则为

如果

则判

这种判别规则的另一种表述形式是：

如果

则判

易知，将特征空间分划成个判别类域，当在中时，则有。实际上有的判别类域可能并不相邻。如果和相邻，则它们的界面方程为。如同方法⑴，此方法也只有个判决式是独立的。

例：一个二维三类模式分类器，其判别函数为

，，

属于类的模式应满足和；属于类的模式应满足和。对待分类模式，、、,从而和，故判。

小结

当时，法比法需要更多的判别函数式，这是一个缺点。但是法是将类与其余的类区分开，而法是将类和类分开，显然法使模式更容易线性可分，这是它的优点。方法⑶判别函数的数目和方法⑴相同，但没有不确定区，分析简单，是最常用的一种方法。

3·3

判别函数值的鉴别意义、权空间及解空间

3.3.1

判别函数值的大小、正负的数学意义——点面距离、界面正负侧

（1）系数矢量是超平面的法矢量

在维特征空间中，两类问题的线性判别界面方程为

(

3-3-1)

此方程表示一超平面，记为。系数矢量是该平面的法矢量，

即平面。

证明：

设点、在判别界面中，故它们满足方程，于是有

上面二式相减，可得

(

3-3-2)

上式表明，而差矢量在判别界面中，由于、是中的任意两点，故平面。

（2）的绝对值正比于到超平面的距离

平面的方程可以写成

(

3-3-3)

式中。于是是平面的单位法矢量，上式可写成

(

3-3-4)

设是平面中的任一点，是特征空间中任一点，点到平面的距离为差矢量在上的投影的绝对值，即

(

3-3-5)

上式中利用了在平面中，故满足方程

(

3-3-6)

式(3-3-5)的分子为判别函数绝对值，上式表明，的值正比于到超平面的距离，一个特征矢量代入判别函数后所得值的绝对值越大表明该特征点距判别界面越远。

图

(3-3-1)

点面距离及界面的正负侧示意图

（3）的正（负）反映在超平面的正（负）侧

两矢量和的数积为

(

3-3-7)

显然，当和夹角小于时，即在指向的那个半空间中，>0；反之，当和夹角大于时，即在背向的那个半空间中，<0。由于，故和同号。所以，当在指向的半空间中时，；当在背向的半空间中，。判别函数值的正负表示出特征点位于哪个半空间中，或者换句话说，表示特征点位于界面的哪一侧。

3.3.2

权空间、解矢量与解空间

（1）权空间

增广特征矢量与增广权矢量是对偶的，判别函数可以写成

(

3-3-8)

如果将权系数视为变量，由其组成的增广权矢量的全体称为权空间，这里则应视为相应的的“权”。是一个过增广权空间原点的平面，矢量是它的法矢量，指向平面的正侧，即该半空间中的任一点都使，背向的半子空间中任一点都有。

（2）解矢量

对于两类问题，在对待分类模式进行分类之前，应根据已知类别的增广训练模式确定线性判别函数

实质就是确定增广权矢量，使得当训练模式时有；当训练模式时有，这时的称为解矢量，记为。有时为表述和处理简洁方便，我们需要将已知类别的训练模式符号规范化：当属于类时，不改变其符号；当属于类时，改变其符号。设训练模式

均已符号规范化，如果所建立的判别函数能正确分类训练模式，则有

(

3-3-9)

对于训练模式，界面过增广权空间原点且将其分成两个子空间，界面的法矢量指向正半子空间，所谓正半子空间是指该子空间中任一点都使。显然，解矢量必在正半子空间中。

（3）解空间

个训练模式将确定个界面，每个界面都把权空间分为两个半空间，个正的半子空间的交空间是以权空间原点为顶点的凸多面锥，易知，满足上面各不等式的必在该锥体中，即锥中每一点都是上面不等式组的解，解矢量不是唯一的，上述的凸多面锥包含了解的全体，称其为解区、解空间或解锥。每一个训练模式都对解区提供一个约束，训练模式越多，解区的限制就越多，解区就越小，就越靠近解区的中心，解矢量就越可靠，由它构造的判别函数错分的可能性就越小。

除了采用增加训练模式数目的方法提高解矢量的可靠性之外，还可以在解区的边界基础上“收缩”一个距离，使新的解区在原解区的内部，为此，我们引入余量，寻找满足的解矢量，显然，满足的必满足，即所确定的凸多面锥在所确定的多面锥的内部，并且它的边界离开原解区边界的距离为，这样，有效地避免了量测的误差、引入的误差以及某些算法求得的解矢量收敛于解区的边界上，从而提高了解的可靠性。

求解权矢量的最优解，实质上是求解不等式方程组或等式方程组。原则上讲，可以运用任何有效的方法解决。但常用的计算方法主要有：构造一次或二次准则函数运用最优化技术求解、线性规划法、搜索法、迭代法等等。下面介绍几种常用的线性判别函数的训练算法。

3·4

Fisher线性判别

多维

Fisher变换

利于分类的一维

对于线性判别函数

(

3-4-1)

可以认为是矢量在以为方向的轴上的投影的倍。这里，视作特征空间中的以为分量的一个维矢量

希望所求的使投影后，同类模式密聚，不同类模式相距较远。

求权矢量

求满足上述目标的投影轴的方向和在一维空间中确定判别规则。

从另一方面讲，也是降维，特征提取与选择等问题的需要。（R.A.Fisher，1936）

下面我们用表示待求的。

图

(3-4-1)

二维模式向一维空间投影示意图

（1）Fisher准则函数

对两类问题，设给定维训练模式，其中有个和个模式分属类和类。为方便，各类的模式又可分别记为和，于是，各类模式均值矢量为

(

3-4-2)

各类类内离差阵和总的类内离差阵分别为

(

3-4-3)

(

3-4-4)

我们取类间离差阵为

(

3-4-5)

作变换，维矢量在以矢量为方向的轴上进行投影

(

3-4-6)

变换后在一维空间中各类模式的均值为

(

3-4-7)

类内离差度和总的类内离差度为

(

3-4-8)

(

3-4-9)

类间离差度为

(

3-4-10)

我们希望经投影后，类内离差度越小越好，类间离差度越大越好，根据这个目标作准则函数

(

3-4-11)

称之为Fisher准则函数。我们的目标是，求使最大。

（2）Fisher变换

将标量对矢量微分并令其为零矢量，注意到的分子、分母均为标量，利用二次型关于矢量微分的公式可得

(

3-4-12)

令

可得

当时，通常是非奇异的，于是有

(

3-4-13)

上式表明是矩阵相应于本征值的本征矢量。对于两类问题，的秩为1，因此只有一个非零本征值，它所对应的本征矢量称为Fisher最佳鉴别矢量。由式(

3-4-13)有

(

3-4-14)

上式右边后两项因子的乘积为一标量，令其为，于是可得

式中为一标量因子。这个标量因子不改变轴的方向，可以取为1,于是有

(

3-4-15)

此时的是使Fisher准则函数取最大值时的解，即是维空间到一维空间投影轴的最佳方向，

(

3-4-16)

称为Fisher变换函数。至此可以说解决了将维模式的分类转变为一维模式分类的问题。

（3）Fisher判别规则

由于变换后的模式是一维的，因此判别界面实际上是各类模式所在轴上的一个点。可以根据训练模式确定一个阈值，Fisher判别规则为

(

3-4-17)

判别阈值可取两个类心在方向上轴的投影的连线的中点作为阈值，即

(

3-4-18)

容易得出

(

3-4-19)

显然，这里是和连线的中点。

当考虑类的先验概率时，、应取下面的定义

(

3-4-20)

(

3-4-21)

、可由训练模式估计

(

3-4-22)

这种情况下，应取以类的频率为权值的两类中心的加权算术平均作为阈值，即

(

3-4-23)

易得

(

3-4-24)

这里的是和连线上以频率为比例的内分点。

由上可知，和是等价的。从而可得Fisher线性判别函数为

(

3-4-25)

Fisher判别规则为

(

3-4-26)

我