第二章 聚类分析

对一批没有标出类别的模式样本集，按照样本之间的相似程度进行分类，相似的归为一类，不相似的归为另外一类，称为无监督的分类。特征向量作为特征空间中的一些点，把点和点之间的距离作为模式相似性的测量依据。聚类分析就是根据不同对象之间的差异，根据距离函数的规律（通常是大小）进行分类。聚类分析的有效性，与模式特征向量的分布形式有很大关系。如果向量点的分类是一群一群的，同一群样本密集，而不同群样本距离很远，就容易聚类。若不同样本集的向量聚成一团，不同群的样本混在一起，就很难分类。特征维数的选择，需要去掉相关程度过高的特征，就是进行降维处理。相关系数等于0，表明两个完全无关，相关系数等于1，表明两个完全相关。如果第i维度和第j维之间的相关系数接近，可以进行合并特征，进行降维处理。模式对象进行数值化，把连续的进行量化。名义尺度，即特征向量间没有数量关系，也没有明显的次序关系，指定性的指标。

相似性的测度和聚类准则，可以将模式集划分为不同的类别。包括欧式距离、马氏距离、一般化的明式距离。偶是距离的概念和习惯上距离的概念是一致的。量纲对分类有较大的影响。马氏距离中，x是模式向量，m是均值向量，C是模式总体的协方差矩阵，马氏距离排除了模式样本之间的相关性。 一般化的明式距离是欧式距离的推广。角度相似性函数表示的是向量之间夹角的余弦的计算。 这种距离不受坐标系的旋转、放大和缩小的影响。

有了相似性测度，还需要一个基于数值的聚类准则，能把相同的聚为一类，而把不相似的聚为异类。 聚类准则反应的是类别见相似性或者分离性的函数。聚类准则的函数为模式样本集和模式类别的函数，从而使聚类分析变成最优极值的函数。  聚类的过程，就是使得J值达到最小的聚类形式。第一种是基于试探的聚类算法，基于最近邻规则的简单试探法。 最大最小的距离算法，计算聚类中心。 系统聚类法是按照距离准则逐步分类，类别由多到少，逐渐合适。 进行聚类合并的关键是每次迭代中形成的聚类之间和样本之间距离的计算，采用不同的距离函数，会得到不同的结果。最短距离法，就是两类间的最短距离。最长距离法，就是两类之间的最短距离。还有就是重心法，类平均距离法。

模式相似性的测度和聚类准则。基于试探的聚类方法、系统聚类法、动态聚类法。 将两类合并成一类。 计算合并后，新类别之间的距离，可以得到新的类别之间的距离。 动态聚类法选择若干个样本点作为聚类中心，再按照聚类准则 使样本点向中心聚集，从而得到初始聚类。有K-均值算法，或者迭代自组织数据分析算法。选K个初始聚类中心， 然后将所有需要分类的模式样本按照最小距离准则分配给K个聚类中心中的某一个。计算各个聚类中心的新的向量值。以均值向量作为新的聚类中心。K均值受如下选择的影响 ，所选聚类的 数目。聚类中心的初始分布。欧式样本的几何性质。

第三章 判别函数

最简单的是线性判别函数，Fisher先行判别，感知器算法，决策树的介绍。判别函数主要用来分类，最简单的事对两类问题的判别。对于二维的模式类，可以用直线来划分，或者叫线性可分的。N维的线性判别函数，用线性判别函数将属于w类的模式与不属于w类的模式分开，M类多类问题划分为M个两类问题。采用没对划分。对于M类模式的分类，多类情况1需要M个判别函数，多类情况2需要M*M-1/2个判别函数。 广义线性判别函数简单，容易实现，非线性判别函数复杂，不容易实现。在低维空间中线性不可分，在高维空间中可能是线性的。单值实函数。Fisher线性判别。感知器算法，一旦判别函数的形式确定下来，不管它是线性还是非线性的，剩下的是如何确定它的系数。感知器算法就是通过训练样本模式的迭代和学习，产生线性可分的判别函数。感知器算法的实质是一种赏罚过程，感知器算法判别函数的推导。可训练的确定性分类迭代算法。线性，平面，超面都是判别函数，但是系数需要确定下来。 系数的确定是根据已知样本的训练和学习来获得。感知器算法就是训练样本模式的迭代和学习，产生系数。感知器算法不需要对统计判别。感知器的训练算法，权向量的初始值。梯度法，改变权向量的值。梯度就是一个向量，最重要的性质是给出了函数在自变量增加时最大增长率的方向。权向量按照梯度值减小，这种方法称为梯度法。感知器算法其实是梯度法的一个特例，还有固定增量算法。若模式是线性可分的，选择合适的准则函数，算法就能给出解。最小平方误差的算法，在一个特定的判别界面分开时才能收敛，对于类别不可分的情况可以指出来。两类问题的解，相当于求一组线性不等式的解。H-K算法求解Xw=b的方程。利用势函数的概念来确定判别函数和判别类别界面。把样本附近空间x点的点位分布，看成一个势函数。

决策树，或成为多级分类器，是模式识别中进行分类的一种有效方法。对多类问题，或者多峰问题。一般来说，一个决策树有一个根基点，一组非终止节点，和一些终止节点组成。一种最简单的决策树，就是二叉树，每个非终止节点有且只有两个子节点。把每一个部分分下去，直到分成没一个部分只包含同一类别的样本。对未知的样本，只需要把样本从根节点到叶节点进行逐个的分支。选择合适的树结构，在非终止节点上选择合适的决策规则。性能良好的决策树结构用该有效地错误率和低的决策代价。极小化整个树的节点数目，从根节点到叶节点的最大路径长度。通过对识别对象的观察和测量，构成特征向量，然后设计分类器和判别规则，对模式进行分类。

第四章 统计分类

对随机采样的进行判别，就是根据贝叶斯判别准则。判别的时候采用贝叶斯判别，就是采用概率判别规则，属于第一类的概率大于属于第二类的概率，则属于第一类。先验概率和条件概率的乘积。似然比大于阈值的是一类，小于阈值的是另一类。贝叶斯最小风险判别，贝叶斯的最小风险判别，M类问题的条件平均风险。最小平均条件分类器。按照贝叶斯公式，最小平均条件风险。

第五章特征选择与提取

先是无监督的分类，然后确定性的判别函数，特征向量的点的位置很重要。分类器的设计的时候假定特定的特征已经确定的，特征的选择和提取是构造模式识别系统的重要课题。特征维数灾难问题，在保证一定分类精度的前提下，减少特征的维数，使分类器快速、准确和高效的分类。实际上特征选取和提取在分类器设计之前。特征选择就是从N个 度量值中，按照某一准则选取特征子集形成特征集。另外 一种方法是采取映射和变换的方法，就是特征的提取。点到点集之间的距离。类内距离。类内散步矩阵，类间散步矩阵。对于特征点的选择，减少特征空间，可以穷举法，寻找一种简便的可分性准则。各个原始特征测量值是统计独立的。分子是均值的平方，分母是方差的和，类似FISHER准则。 按照大小排队，选出最大的M个对应的测度作为分类特征。基于距离的可分性准则，气适用范围和模式特征分布有关。均值和方差不足以用来区分可分性。类间离散度越大，类内离散度越小，则可分性越好。离散K-L变换，从n个中选出k个来反映原有模式。原来的n个数据。随机实函数，可用正交函数集的线性组合展开。KL展开就是把随机向量展开另外一组正交向量的系数和。正交向量集的总体自相关矩阵。不同特征值对应的特征向量是正交的。随机向量的自相关矩阵。从n个特征向量中，取出m个组成变换矩阵。KL变换也称为主成分变换，本质上把差异性最大的特征保存下来。计算自相关矩阵。均值点的距离