- 作者：M.Narasimha Murty, V. Susheela Devi
- 翻译：王振永
- 出版社：哈尔滨工业大学出版社
导论
模式识别可以定义为基于已知知识或者依据模式标书所抽象出来的统计信息进行数据分类的方法。
模式识别有很多重要的应用，例如多媒体文档自动识别(MDR)和自动医疗诊断。在进行MDR时，必须处理文本、音频和视频数据的集合。文本数据可以由对应一个或多个自然语言的字符和数字组成。音频数据可能是语音或音乐。视频数据可能是一个单一的图像或图像序列。
一个典型的模式识别应用程序中，需要对原始数据进行吹了，将其转换为一种可被机器使用的形式。音频可悲表示为现行预测编码的系数，而视频数据则可以转换到变换域来表示，比如小波变换和傅里叶变换。信号处理可以将原始输数据转换为矢量数据。
模式识别涉及到分类和聚类。在模式识别中，使用一组训练模式或领域知识分配类类标签。聚类可以将数据分区，这有助于我们制定决策，我们感兴趣的决策制定是数据分类。
什么是模式识别
在模式识别中，为模式制定标签。有时候，可以使用分类规则而不进行任务抽象。模式是别的重要方面之一是应用前景，在农业、教育、安全、交通、金融、医疗和娱乐等领域中有着广泛的应用，具体应用包括生物识别、生物信息学、多媒体数据分析、文档识别、故障诊断以及专家系统。分类是人类的一种基本思维模式，所以模式识别可以应用在任务领域。
模式识别的数据集合
在互联网有大量的数据集可供使用。一个受欢迎的网站是UCIrvine的机器学习库(www.ics.uci.edu/MLRepository.html)，它包含许多不同大小的数据集，可以用于各种分类算法。其中很多设置给出了一些分类方法的分类精度，可以作为研究的基准。用于数据挖掘的大型数据集可在网站kdd.ics.uci.edu和www.kdnuggets.com/datasets/中找到。
模式识别的理论框架
有多重理论框架能解决模式识别问题，其中最主要的两种为：
- 统计模式识别
- 结构模式识别
在这两种方式中，统计模式识别使用更为广泛，在文献中大量出现。
模式集合的表征
模式是一个物理对象或抽象概念。
模式结合表征的数据结构
矢量的模式集合表征
矢量是一种显而易见的模式表征。
字符串的模式模式集合表征
字符串可以看做某种语言的句子，例如一个DNA序列或蛋白质序列。举例说明，某遗传因子可以被分别由A、G、C和T表示的腺嘌呤、鸟嘌呤、胞嘌呤和胸嘌呤四种含氢基构成的染色体DNA的一片区域。基因数据被排列在一个序列中，例如
GATTGTCAAG…
模式集合的逻辑表述方法
(此处无内容)
模式的模糊集合及粗糙集合
模糊可以用在无法精确表述的情况下，因此可以用来对主观的、不完备的以及不精确的数据进行建模。在一个模糊集合中，对象从属于成员值从0至1变化的集合。
基于树和图的表征
树和图是用来表征模式和模式类别的常见数据结构。树或图中的每一个节点可以表示一个或多个模式。
- 最小生成树
- 频繁模式树
模式聚类的表征
聚类是将含有相似特征的模式组在一起并将不同特征的对象放在不同的组的过程。这里有两个数据结构，一个是模式的划分P，另一个是一系列簇的代表C。
相似度量方法
为了对模式进行分类，模式之间需要相互比较并与某个标准进行比较。
- 基于距离的度量方法
一个量化的方法具有如下性质- 正自反性d(x,y)=0
- 对称性d(x,y)=d(y,x)
- 三角不等性d(x,y)<=d(x,z)+d(z,y)
常用的度量方法成为民科夫斯基计量，形式如下
$$d^m(X,Y)=(\sum_{k=1}^d|x_k-y_k|^m)^{\frac{1}{m}}$$
当m为1时称它为曼哈顿距离或$L_1$距离。最常用的距离为当m的值为2时的欧式距离或$L_2$距离。可以得到
$$d^2(X,Y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+…+(x_d-y_d)^2}$$
在这种模式下，$L_{\inf}$为
$$d^{\infty}=max_{k=1,…,d}|x_k-y_k|$$
当使用距离度量时，应当保证所有的特征有相同的取值范围，舍弃那些被认为更重要的具有更大范围的属性，就好像赋予它更大的权重。为保证所有特征具有相同的范围，应当采取特征值标准化。
马氏距离也是一种在分类中常见的距离度量，它可由下式得出
$$d^2(X,Y)=(X-Y)^T\sum^{-1}(X-Y)$$
其中$\sum$是西方差矩阵。
- 基于加权距离的度量方法
当认为某个属性更重要时，可以再它们的值上加权重。加权的距离度量形式如下
$$d(X,Y)=(\sum_{k-1}^d\omega_k*(x_k-y_k)^m)^{\frac{1}{m}}$$
其中$\omega_k$是第k维相关的权重。 - 非度量相似函数
相似函数在此范畴下既不遵从三角不等式也不遵从对称性。这些相似函数往往在图像以及数据串中十分有效。它们对异常值和极端噪声数据具有鲁棒性。
一种不具有对称性的非量化聚利是发散度距离(KL距离)。它是一个从“真实”概念分布p到”目标”概念分布q的自然距离函数。对于离散概率分布，如果$p={p_1,..p_n}$并且$q={q_1,…q_n}$，那么KL距离定义为
$$KL(p,q)=\sum_ip_i\log_2(\frac{p_i}{q_i})$$
对于连续概率密度，用积分代替求和。 - 编辑距离
编辑距离计算两个字符串之间的距离，它也称为莱文斯汀距离。 - 互近邻距离
- 概念内聚性
- 核函数
核函数可以用来描述模式x和y之间的距离。- 多项式核函数。x和y之间的相似度可以用多项式核函数表述为$$K(x,y)=\epsilon(x)^{
}\epsilon(y)=(x^{}y+1)^2$$
通过这种方法，输入空间中的线性相关矢量转换为核空间的线性无关矢量。 - 径向基(RBF)核函数。核定义如下$$K(x,y)=\exp^{\frac{-|x-y|^2}{2\sigma^2}}$$
- 多项式核函数。x和y之间的相似度可以用多项式核函数表述为$$K(x,y)=\epsilon(x)^{
模式的尺寸
样本的大小取决于所考虑的属性。
数据归一化
数据标准化的过程可以使所有的模式具有统一的尺度。
相似度度量的选择方法
相似度计算可以处理不等长度问题，一个相似度计算的例子为编辑距离。
数据集合的抽象
特征提取
特征提取涉及到对所需样本特征的发掘和提取。特征操作从数据中提取特征以识别或解析有意义的信息。这在图像中有重大意义，因为此时特征提取需要自动识别多种特征。特征提取是模式识别中一部重要的预处理步骤。
Fisher线性判别法
Fisher线性判别法将高纬度数据映射到一条线上并在这个空间上施行分类。如果有两个类别，那么映射最大化了两个类别之间的均值的距离并且最小化了美衣美类别中的方差。能够最大化所有线性映射V的Fisher准则定义如下：$$J(V)=\frac{|mean_1-mean_2|^2}{s_1^2+s_2^2}$$
其中，$mean_1$和$mean_2$分别代表类别1和类别2样本的均值；$s_1$与$s_2$分别代表了各自的方法。
主成分分析法
主成分分析(PCA)是一个数学方法，它将大量相关变量转化为小数量的不相关变量，这些不相关变量称为主要成分。最主要成分尽可能地反映了数据中的变化性，次之成分尽可能地反映了剩余的变化。PCA在更低纬的空间内找出了最精确的数据代表。数据被映射到方差最大的方向上。
特征选择
用于分类的特征并不总是有意义的，移除那些对于分类没用的特征，可能会得到哦更高的分类准确度。特征选择则可以加速分类过程，同时确保分类精确是最佳的。特征选择有如下特点
- 减少样本分类以及分类设计的开销、维度简化等。使用一个有限的特征集简化样本的描述以及分类复杂度。因此分类将变得更快，使用更少的存储器。
- 分类精度的提高。分类精度的提高取决于以下因素
- 样本的大小、特征数量、分类复杂度
- 在同一个光以及和的情况下，随着维度的增加，到最近点的距离逐步接近最远点的距离。
所有特征的选择基本上都是遍历不同的特征子集。
穷举搜索法
穷举搜索法是解决所有特征选择问题的最直接方法，搜索所有特征子集并且找到最佳子集。
分支定界搜索法
分支定界搜索法通过利用在获得最终准则值过程中所产生的一些中间结果避免了穷举搜索。
最优特征选择法
最有特征选择法是一种只选择最有特征的简单方法。独立计算所有特体特征，并选择m个最佳特征。这种方法虽然简单，但是很可能失败，由于特征之间并非完全独立。
顺序选择法
浮动顺序选择法
最大最小特征选择法
随机搜索法
人工神经网络
分类分析方法
在使用分类器之前，有必要评估它的表现。需要考虑的分类器参数列举如下
- 分类器的准确性
- 设计时间和分类时间
- 所需要的空间
- 解释说明能力
如果一种对样本的分类方法对使用者解释得很清楚，那么它的解释说明能力就很好。 - 噪声容限
它是指一个分类器处理异常值和错误分类样本的能力。
要想评估一个分类方法有多好，可以凭他提训练集本身。不同的检验方法列举如下
- 保持法
- 随机子抽样
- 分叉校验
- 拔靴法
聚类分析方法
最近邻分类器
贝叶斯分类器
隐式马尔科夫模型
决策树
支持向量机
多分类组合
聚类方法
本书总结
应用实例：手写数字识别
数字数据的描述
数据预处理
分类算法
典型模型的选择
识别结果
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！