模式识别研究进展
刘成林，谭铁牛
中国科学院自动化研究所 模式识别国家重点实验室
北京中关村东路95号
摘要
自20世纪60年代以来，模式识别的理论与方法研究及在工程中的实际应用取得了很大的进展。本文先简要回顾模式识别领域的发展历史和主要方法的演变，然后围绕模式分类这个模式识别的核心问题，就概率密度估计、特征选择和变换、分类器设计几个方面介绍近年来理论和方法研究的主要进展，最后简要分析将来的发展趋势。
1. 前言
模式识别(Pattern Recognition)是对感知信号（图像、视频、声音等）进行分析，对其中的物体对象或行为进行判别和解释的过程。模式识别能力普遍存在于人和动物的认知系统，是人和动物获取外部环境知识，并与环境进行交互的重要基础。我们现在所说的模式识别一般是指用机器实现模式识别过程，是人工智能领域的一个重要分支。早期的模式识别研究是与人工智能和机器学习密不可分的，如Rosenblatt的感知机[1]和Nilsson的学习机[2]就与这三个领域密切相关。后来，由于人工智能更关心符号信息和知识的推理，而模式识别更关心感知信息的处理，二者逐渐分离形成了不同的研究领域。介于模式识别和人工智能之间的机器学习在20世纪80年代以前也偏重于符号学习，后来人工神经网络重新受到重视，统计学习逐渐成为主流，与模式识别中的学习问题渐趋重合，重新拉近了模式识别与人工智能的距离。模式识别与机器学习的方法也被广泛用于感知信号以外的数据分析问题（如文本分析、商业数据分析、基因表达数据分析等），形成了数据挖掘领域。
模式分类是模式识别的主要任务和核心研究内容。分类器设计是在训练样本集合上进行优化（如使每一类样本的表达误差最小或使不同类别样本的分类误差最小）的过程，也就是一个机器学习过程。由于模式识别的对象是存在于感知信号中的物体和现象，它研究的内容还包括信号/图像/视频的处理、分割、形状和运动分析等，以及面向应用（如文字识别、语音识别、生物认证、医学图像分析、遥感图像分析等）的方法和系统研究。
本文简要回顾模式识别领域的发展历史和主要方法的演变，介绍模式识别理论方法研究的最新进展并分析未来的发展趋势。由于Jain等人的综述[3]已经全面介绍了2000年以前模式分类方面的进展，本文侧重于2000年以后的研究进展。
2. 历史回顾
现代模式识别是在20世纪40年代电子计算机发明以后逐渐发展起来的。在更早的时候，已有用光学和机械手段实现模式识别的例子，如在1929年Gustav Tauschek就在德国获得了光学字符识别的专利。作为统计模式识别基础的多元统计分析和鉴别分析[4]也在电子计算机出现之前提出来了。1957年IBM的C.K. Chow将统计决策方法用于字符识别[5]。然而，“模式识别”这个词被广泛使用并形成一个领域则是在20世纪60年代以后。1966年由IBM组织在波多黎各召开了第一次以“模式识别”为题的学术会议[6]。Nagy的综述[7]和Kanal的综述[8]分别介绍了1968年以前和1968-1974的研究进展。70年代几本很有影响的模式识别教材（如Fukunaga [9], Duda & Hart [10]）的相继出版和1972年第一届国际模式识别大会（ICPR）的召开标志着模式识别领域的形成。同时，国际模式识别协会（IAPR）在1974年的第二届国际模式识别大会上开始筹建，在1978年的第四届大会上正式成立。
统计模式识别的主要方法，包括Bayes决策、概率密度估计（参数方法和非参数方法）、特征提取（变换）和选择、聚类分析等，在20世纪60年代以前就已经成型。由于统计方法不能表示和分析模式的结构，70年代以后结构和句法模式识别方法受到重视。尤其是付京荪（K.S. Fu）提出的句法结构模式识别理论在70-80年代受到广泛的关注。但是，句法模式识别中的基元提取和文法推断（学习）问题直到现在还没有很好地解决，因而没有太多的实际应用。
20世纪80年代Back-propagation (BP) 算法的重新发现和成功应用推动了人工神经网络研究和应用的热潮。神经网络方法与统计方法相比具有不依赖概率模型、参数自学习、泛化性能1良好等优点，至今仍在模式识别中广泛应用。然而，神经网络的设计和实现依赖于经验，泛化性能不能确保最优。90年代支持向量机(SVM)的提出吸引了模式识别界对统计学习理论和核方法(Kernel methods)的极大兴趣。与神经网络相比，支持向量机的优点是通过优化一个泛化误差界限自动确定一个最优的分类器结构，从而具有更好的泛化性能。而核函数的引入使很多传统的统计方法从线性空间推广到高维非线性空间，提高了表示和判别能力。
结合多个分类器的方法从90年代前期开始在模式识别界盛行，后来受到模式识别界和机器学习界的共同重视。多分类器结合可以克服单个分类器的性能不足，有效提高分类的泛化性能。这个方向的主要研究问题有两个：给定一组分类器的最佳融合和具有互补性的分类器组的设计。其中一种方法，Boosting，现已得到广泛应用，被认为是性能最好的分类方法。
进入21世纪，模式识别研究的趋势可以概括为以下四个特点。一是Bayes学习理论越来越多地用来解决具体的模式识别和模型选择问题，产生了优异的分类性能[11]。二是传统的问题，如概率密度估计、特征选择、聚类等不断受到新的关注，新的方法或改进/混合的方法不断提出。三是模式识别领域和机器学习领域的相互渗透越来越明显，如特征提取和选择、分类、聚类、半监督学习等问题成为二者共同关注的热点。四是由于理论、方法和性能的进步，模式识别系统开始大规
1泛化性能指分类器在测试样本（没有用于训练的新样本）上的分类正确率。提到“分类性能”时一般也是指泛化性能。
模地用于现实生活，如车牌识别、手写字符识别、生物特征识别等。
模式识别方法的细节可以参考一些优秀的教材，比如Bishop (2006) [11], Fukunaga (1990)[12], Duda, Hart & Stork (2001)[13]等。
3. 模式识别研究现状
3.1 模式识别系统和方法概述
模式识别过程包括以下几个步骤：信号预处理、模式分割、特征提取、模式分类、上下文后处理。预处理通过消除信号/图像/视频中的噪声来改善模式和背景间的可分离性；模式分割是将对象模式从背景分离或将多个模式分开的过程；特征提取是从模式中提取表示该模式结构或性质的特征并用一个数据结构（通常为一个多维特征矢量）来表示；在特征表示基础上，分类器将模式判别为属于某个类别或赋予其属于某些类别的概率；后处理则是利用对象模式与周围模式的相关性验证模式类别的过程。
模式识别系统中预处理、特征提取（这里指特征度量的计算，即特征生成）和后处理的方法依赖于应用领域的知识。广义的特征提取包括特征生成、特征选择和特征变换（维数削减）2
。后两个过程和分类器设计一样，需要在一个样本集上进行学习（训练）：在训练样本上确定选用哪些特征、特征变换的权值、分类器的结构和参数。
由于句法和结构模式识别方法是建立在完全不同于特征矢量的模式表示基础上且还没有得到广泛应用，本文与Jain 等人[3]一样，主要关注统计模式识别（广义地，包括神经网络、支持向量机、多分类器系统等）的进展。
Bayes 决策是统计模式识别的基础。将模式表示为一个特征矢量x （多维线性空间中的一个点），给定M 个类别的条件概率密度(|)i p ωx ，i =1,…,M , 则模式属于各个类别的后验概率可根据Bayes 公式计算： 1()(|)()(|)
(|)()()(|)i i i i i M j j
j P p P p p p P p ωωωωωωω===∑x x x x x ，
其中()i P ω是第i 类的先验概率。根据Bayes 决策规则，模式x 被判别为后验概率最大的类别（最小错误率决策）或期望风险最小的类别（最小代价决策）。后验概率或鉴别函数把特征空间划分为对应各个类别的决策区域。
模式分类可以在概率密度估计的基础上计算后验概率密度，也可以不需要概率密度而直接近似估计后验概率或鉴别函数（直接划分特征空间）。基于概率密度估计的分类器被称为生成模型(Generative model)，如高斯密度分类器、Bayes 网络等；基于特征空间划分的分类器又被称为判别模型（Discriminative model），如神经网络、支持向量机等。生成模型每一类的参数在一类的 2“特征提取”在很多时候就是指特征变换或维数削减，有时候也指从模式信号计算特征度量的过程（特征生成）。这就需要根据语言的上下文来判断它的意思。
训练样本上分别估计，当参数模型符合样本的实际分布或训练样本数比较少时，生成模型的分类性能优良。判别模型在训练中直接调整分类边界，以使不同类别的样本尽可能分开，在训练样本数较多时能产生很好的泛化性能。但是，判别模型在训练时每一类参数的估计要同时考虑所有类别的样本，因而训练的计算量较大。
3.2 概率密度估计
概率密度估计和聚类一样，是一个非监督学习过程。研究概率密度估计主要有三个意义：分类、聚类（分割）、异常点监测(Novelty detection)。在估计每个类别概率密度函数的基础上，可以用Bayes决策规则来分类。概率密度模型经常采用高斯混合密度模型(Gaussian mixture model, GMM)，其中每个密度成分可以看作是一个聚类。异常点监测又称为一类分类(One-class classification)，由于只有一类模式的训练样本，在建立这类模式的概率密度模型的基础上，根据相对于该模型的似然度来判断异常模式。
高斯混合密度估计常用的Expectation-Maximization (EM)算法[14]被普遍认为存在三个问题：估计过程易陷于局部极值点，估计结果依赖于初始化值，不能自动确定密度成分的个数。对于成分个数的确定，提出了一系列的模型选择准则，如Bayes准则[15]、最小描述长度(MDL)、Bayesian Information Criterion (BIC)、Akaike Information Criterion (AIC)、最小消息长度(MML)等[16]。Figueiredo和Jain在一个扩展的EM算法中引入密度成分破坏(Annihilation)机制[16]，可以达到自动确定成分个数的目的。Ueda和Ghahramani提出一种基于变分Bayes的准则，并用分裂-合并算法进行估计自动确定成分个数[17]。分裂-合并算法还可以同时克服局部极值影响。
高斯混合密度用于高维数据时会造成密度函数的参数太多，用于分类时还会降低泛化性能。这个问题可以通过限制协方差矩阵（为对角矩阵或单位矩阵的倍数）、参数共享或特征降维来克服。在多类分类时，不同类别的概率密度要建立在相同的特征空间。如果对不同类别或不同密度成分提取不同的子空间，则要将子空间的密度函数反投影到原来的特征空间[18]。Moghaddam和Pentland 的概率密度模型是主成分分析(PCA)子空间内的混合高斯密度和补子空间中的高斯密度的结合[19]。
最近，Bouguila等人提出一种新的混合密度形式：Dirichlet混合密度[20][21]。Dirichlet分布表示离散概率（介于0到1之间且和等于1）的联合分布，可以用于直方图、和归一化特征矢量等的概率密度估计。Dirichlet密度可以是非对称的，比高斯密度函数更为灵活，但计算也更复杂。Dirichlet 混合密度可以用类似于EM的随机优化算法进行估计，在模式分类和图像聚类等应用中取得了优异的性能[21]。
概率密度估计的另一种新方法是稀疏核函数描述（支持向量描述）[22][23]。Sch?lkopf等人采用类似支持向量机的方法，用一个核特征空间的超平面将样本分为两类，使超平面外的样本数不超过一个事先给定的比例[22]。该超平面的函数是一个样本子集（支持向量）的核函数的加权平均，可以像支持向量机那样用二次规划算法求得。Tax和Duin的方法是用核空间的一个球面来区分区
域内和区域外样本[23]，同样地可以用二次规划进行优化。
3.3 特征选择
特征选择和特征变换都是为了达到维数削减的目的，在降低分类器复杂度的同时可以提高分类的泛化性能。二者也经常结合起来使用，如先选择一个特征子集，然后对该子集进行变换。近年来由于适应越来越复杂（特征维数成千上万，概率密度偏离高斯分布）的分类问题的要求，不断提出新的特征选择方法，形成了新的研究热点[24]。
特征选择的方法按照特征选择过程与分类器之间的交互程度可以分为过滤式(Filter)、 Wrapper[25]、嵌入式、混合式几种类型。过滤式特征选择是完全独立于分类器的，这也是最常见的一种特征选择方式，选择过程计算量小，但是选择的特征不一定很适合分类。在Wrapper方法中，特征子集的性能使用一个分类器在验证样本上的正确率来衡量，这样选择的特征比较适合该分类器，但不一定适合其他的分类器。由于在特征选择过程中要评价很多特征子集（子集的数量呈指数级增长），即使采用顺序前向搜索，Wrapper的计算量都是很大的，只适合特征维数不太高的情况。Wrapper的另一个问题是当训练样本较少时会造成过拟合，泛化性能变差。
嵌入式方法是在分类器的训练过程中包含了特征选择功能，因此跟Wrapper一样也是依赖于分类器的。一个经典的方法是LASSO[26]。近来有代表性的两种嵌入式方法是稀疏支持向量机[27]和Boosting特征选择[28]。混合式特征选择结合不同的方法以实现更好的计算复杂性-分类性能的折衷，在初始特征数量非常大时经常使用，如[29]的方法在三个阶段先后用三种方法削减特征个数：过滤、聚类、组合式选择。过滤方法和Wrapper也经常结合使用。
特征选择领域大部分的研究工作都集中在过滤式方法。模式识别领域早期的工作多把关注点放在搜索策略上[30][31]，特征子集评价准则多采用基于高斯密度假设的距离准则，如Fisher准则、Mahalanobis距离等。其实，特征子集的评价准则更为重要，当准则较好地衡量特征子集的可分性且比较稳定时，简单的搜索策略就能产生良好的分类性能。下面分析两类比较有代表性的特征评价方法：基于间隔(Margin)的方法和基于互信息的方法。
RELIEF[32]是一种被广泛引用的过滤式特征选择方法，基本思想是根据特征空间中每个样本在正确类别和不同类别中的最近邻距离之差迭代调整特征的权值。这两个距离之差即我们今天所说的间隔。不过RELIEF并没有对一个全局的目标函数进行优化。最近提出来的一种迭代RELIEF （I-RELIEF）方法设计一种基于间隔的全局目标函数，用类似EM的算法对特征的权值进行优化[33]。另一种方法则对特征子集的空间中最近邻分类的间隔进行优化[34]。
特征选择的基本原则是选择类别相关（Relevant）的特征而排除冗余的特征。这种类别相关性和冗余性通常用互信息(Mutual information, MI)来度量。特征与类别之间的互信息很好地度量了特征的相关性，而特征与特征之间的互信细则度量他们之间的相似性（冗余性）。因此，基于互信息的特征选择方法一般遵循这样一种模式：在顺序前向搜索中寻找与类别互信息最大而与前面已选特征互信息最小的特征[35]。[36]中提出的条件互信息用来度量在一个已选特征的条件下另一个新
的候选特征对分类的相关性。[37]通过分析一种相关度，Symmetrical Uncertainty (SU)与特征的Markov blanket之间的关系，设计一种快速的两步特征选择方法：先根据单个特征与类别之间的相关度选出相关特征，第二步对相关特征根据特征-类别相关度和特征-特征相关度进行筛选。
3.4 特征变换
特征变换也常被称为特征提取，指从原始信号经过变换得到特征量的过程。传统的线性变换方法主要有主成分分析(PCA)和线性鉴别分析(LDA)，后者又叫Fisher鉴别分析(FDA)。LDA的子空间学习是有监督的，目的是使子空间中类间离散度(Sb)和类内离散度(Sw)的行列式之比达到最大。LDA 假设各类样本服从高斯分布且不同类的协方差矩阵相同，而且所有样本在总体上服从高斯分布。另外，LDA提取的特征个数受到类别数的限制，而当训练样本数相对特征维数较小时，Sw为奇异，会带来很多计算上的问题。
由于非高斯分布、小样本等问题的存在，特征变换也是近年来研究的一个热点，这方面的工作可以分为以下几个方向：(1)针对小样本的线性特征提取方法；(2)类内协方差矩阵不同时的异方差(Heteroscedastic)鉴别分析；(3)非高斯分布下的特征提取方法；(4)局部空间特性保持的特征提取方法；(5)非线性特征提取方法；(6)二维模式特征提取方法。
小样本学习的一个典型例子是图像分类，如果直接用图像中所有象素点的值作为特征量，矢量的维数非常高，而每一类的样本数又很少。克服Sw奇异性的一个直接方法是正则化(Regularized)鉴别分析[38]，通过矩阵平滑使Sw变得非奇异。Fisherface方法则用PCA把特征维数从D降到N-M （N是样本数，M是类别数）使Sw变得非奇异[39]。但是，Sw的维数由D降到N-M会损失一些鉴别信息，而降到N-1维则不会有损失[40]。而这时Sw仍然是奇异的，就需要从Sw的零空间（对应本征值为0）提取一些特征[41]。与一般的LDA方法先对Sw对角化然后对Sb对角化相反，一种Direct LDA方法先对Sb对角化后从变换后的Sw提取对应较小本征值的鉴别矢量[42]。
对于类别协方差矩阵不同的情况异方差鉴别分析方法（如[43]）可以得到比LDA更好的分类性能。对于非高斯分布或任意分布的情况，非参数鉴别分析[44]是提取鉴别特征的一个基本思路。由此发展起来的方法还包括基于决策边界的鉴别分析[45][46]。在不假设参数概率密度的情况下，也可以用分类性能准则直接对鉴别投影矢量进行优化，这样的准则如最小分类错误(MCE)[47]和特征与类别之间的互信息[48]。对于每类样本为多模态分布的情况可以采用基于混合高斯密度的鉴别分析[49][50]。
局部性保持特征提取方法借鉴了流形学习（如LLE和Isomap）的思想，目的是在子空间中保持样本点之间的相邻关系。流形学习的问题是只对训练样本进行投影，要推广到测试样本就需要用一个参数模型或回归网络来表示投影的过程。He等人提出的局部性保持投影(LPP)方法通过优化一个局部性保持准则来估计投影矢量，可转换为矩阵本征值分解问题[51]。Yan等人提出一种基于样本邻近关系分析的特征提取的统一框架，称为嵌入图(Embedded graph)，并在此基础上提出一种新的鉴别分析方法[52]。LPP是一种非监督学习方法，被推广到监督学习和核空间 [53]。另外，Isomap
流形学习方法也被推广到监督学习用于非线性特征提取[54]。
几乎所有的线性特征投影方法都可以推广到核空间。Sch?lkopf等人最先将核函数引入PCA，提出Kernel PCA (KPCA)方法[55]。类似地，将核函数引入Fisher鉴别分析，提出了Kernel FDA (KFDA)[56]。[57]对核空间中结合PCA降维和FDA特征提取进行了深入的分析并提出了有效的算法。核空间的特征提取方法还有Kernel Direct LDA [58], Kernel LPP [53]等。
二维模式主成分分析(2D-PCA)[59]或鉴别分析(2D-LDA)[60][61]是近年提出的一种针对图像模式的特征提取方法。这类方法直接在图像矩阵上计算协方差（离散度）矩阵。该矩阵的维数等于图像的行数或列数，计算起来简便多了。另外，矩阵投影到每个本征矢量得到一个矢量，而不是一个值，这样得到的特征值个数也远远多于LDA。在高维图像人脸识别实验中，2D-PCA和2D-LDA的分类性能分别优于PCA和LDA。二维变换方法实际上是基于图像行或列的变换方法[62]，即对每一行或每一列分别投影得到特征，可以推广到基于图像块的投影。
3.5 分类器设计
模式分类是模式识别研究的核心内容，迄今为止提出了大量的分类方法。Jain等人把分类器分为三种类型：基于相似度（或距离度量）的分类器、基于概率密度的分类器、基于决策边界的分类器。第一种分类器的性能取决于相似度或距离度量的设计，同时也取决于标板(Prototype)的学习。标板学习有多种方法[63]，如聚类、LVQ (Learning Vector Quantization)、经验风险最小化等。LVQ和经验风险最小化可以看作是决策边界调整的学习方法，而聚类的作用类似概率密度估计。因此，我们把分类器分为以下三类：生成模型（包括概率密度模型）、判别模型（决策边界学习模型）、混合生成-判别模型。由于前面已专门介绍了概率密度估计，下面我们着重介绍后两类分类器。
判别学习分类器包括我们熟知的人工神经网络、LVQ[63]、支持向量机(SVM)[64]、Boosting[65]等。其共同特点是在学习过程中最优化一个目标函数（准则），该函数表示训练样本集上的分类错误率、错误率的上界、或与分类错误率相关的损失，称为经验风险(Empirical loss)。常见的风险函数如神经网络中常用的平方误差函数、交叉熵（Cross entropy, 又称为对数损失或对数似然度）、最小分类错误准则(MCE)[66]、SVM中的间隔（Margin）、Boosting中的指数损失、以及最近常用的条件似然度(Conditional likelihood)等。指数损失即间隔的指数，是分类错误率的一个上界。对数损失也被用于Boosting学习，称为LogitBoost[67]。条件似然度是训练样本正确类别后验概率的对数。在二类情况下，条件似然度等同于对数似然度。
混合生成-判别学习的模式识别方法近年来受到广泛的关注[68-71]。这种方法结合了生成模型和判别模型的优点：生成模型表示了类别的概率分布或内部结构、在少量样本上学习可得到较高的泛化性能、对噪声/异常模式具有抗拒性；判别模型在概率分布不容易用参数模型表示和训练样本较多时泛化性能优异，而且判别学习得到的模型一般较小（参数较少）。混合生成-判别学习的方法一般是先对每一类模式建立一个生成模型（概率密度模型或结构模型），然后用判别学习准则对
生成模型的参数进行优化[71]。学习的准则可以是生成模型学习准则（如最大似然准则）和判别学习准则（如条件似然度）的加权组合[72][73]。结合判别学习的Bayes网络（如[74][75]）也可以看作是混合生成-判别学习模型。
分类器模型和学习方法多种多样，性能各有特点。一般来说，SVM和Boosting在大部分情况下分类性能优异，但也有他们自身的不足：SVM的核函数选择和Boosting的弱分类器选择对性能影响很大，分类的计算复杂度较高（如SVM的支持向量个数往往很大）。
多分类器方法被认为是结合不同分类器的优点、克服单个分类器性能不足的一个有效途径。早期的多分类器研究主要集中在对给定多个分类器的有效融合[3]。由于单个分类器之间的发散性(Divergence)或互补性对融合后的分类性能起重要作用，近年来的研究主要集中在如何设计互补性强的分类器组(Ensemble或Committee)。这方面的方法主要有集成神经网络(Ensemble neural network)、 Bagging[76]、 Boosting[77]、随机子空间(Random subspace)[78]、特征选择法[79]、纠错输出编码(Error-correcting output codes, ECOC)[80]等。Bagging和Boosting都是通过对训练样本集进行重采样或加权来训练多个分类器，不过Bagging是并行的，而Boosting是串行的。随机子空间法和特征选择法都是从原有的特征集选择多个特征子集，特征子集的独立性决定了分类器的互补性。
与其他学习方法对样本集或特征集进行分解不同的是，ECOC是对类别集进行分解，通过组合多个二类分类器（这里的一类可以是一个类别子集）来实现多类分类。另外一种通过二类分类器实现多类分类的方法是把一对样本之间的关系分为“同类”(Intra-class)和“不同类”(Extra-class)两类，输入特征从两个样本提取（如两个样本对应特征的差），二类分类器的输出给出两个样本“同类”的概率或相似度，多类问题采用近邻规则进行分类。这种方法可以克服训练样本不足的问题，而且在训练后可任意增加或减少类别而不必重新训练，近年来已广泛用于人脸识别等生物特征识别问题[81]。
4. 发展趋势
除了上面介绍的最新研究进展，模式识别领域的前沿研究方向还有：Bayes学习、半监督学习、弱监督学习等。Bayes学习得到的分类器参数并不是一些固定值，而是参数的概率分布。参数的先验概率分布函数形式的选择、超参数（先验概率分布的参数）的确定在计算上是比较复杂的。在识别时，需要对分类器的参数进行随机采样，然后把很多个参数值得到的分类结果组合起来，因而识别的计算量也是很大的。近年来，基于Bayes学习的分类器设计取得了明显进展[11][82]等，得到了优异的分类性能。但是，这些方法的计算还是很复杂的，对于大类别数、大样本集的学习问题还难以实现。
在大部分应用情况下，模式分类器经过训练后就固定不变，或者使用相当长一段时间才重新训练一次。在训练分类器时，样本的数量和代表性总是不够的，这就希望分类器能不断地适应新的样本而不损失对原来训练过的样本的分类性能。这样的增量学习问题很早就受到关注，提出了很多具
体的方法（如[83][84]），但还没有一个统一的理论框架。新增加的样本可能是没有类别标记的，因为无标记样本很容易得到，而标记过程费时费力。同时对标记样本和无标记样本进行学习的过程称为半监督学习，这是近年来机器学习领域的一个研究热点[85]。在标记样本比较少的情况下采用无标记样本能有效提高完全监督学习的分类性能。
大多数模式识别问题假设模式是与背景信号和其他模式分离的且表示成一个特征矢量。实际上，模式的分割不是一件简单的事情，一个固定长度的特征矢量也不一定能最好地表示模式的特性。在实际应用问题中经常要将模式分类与分割问题统一考虑，有些模式被表示成结构性数据结构（如属性图、概率图）。这些方面出现了大量的研究工作，这里不打算细述。目前有一类广受关注的模式识别问题，识别对象是没有分割的图像，训练图像的标记是其中有没有某一类目标，而不知道目标的具体位置、大小和方位。对这种标记不足的样本进行训练和识别的方法可以统称为弱监督学习[86][87]，可用于目标识别、图像检索、景物分类等。
研究计算机模式识别的目的是让机器具备人的感知和认知能力，代替人完成繁重的信息处理工作。当我们把计算机的模式识别能力与人的模式识别（视觉、听觉感知）能力相比，就会发现现有的模式识别方法与人的感知过程有很大区别，在性能上也相差很远，很多对人来说是轻而易举的事情对计算机来说却很难做到。这是由于目前对人的感知过程的机理和大脑结构还不是很了解，即使已经了解的部分也不容易在计算上或硬件上模拟。进一步研究人的感知机理并借鉴该机理设计新的模式识别计算模型和方法是将来的一个重要方向。
5. 总结
本文围绕模式分类这个模式识别的核心问题概述了近年来在概率密度估计、特征选择和变换、分类器设计等方面的重要研究进展，并分析了最近的发展趋势。由于篇幅限制，对模式识别的其他问题，包括分割、上下文处理、计算机视觉、以及重要的应用领域（语音识别、文字识别、生物特征识别等）没有展开讨论。本文力求引用本领域最有代表性的研究工作，但难免会遗漏一些重要的工作，请有关作者谅解。
参考文献
[1] F. Rosenblatt, The perceptron: a probabilistic model for information storage and organization in the brain,
Psychological Review, 65: 386-408, 1958.
[2]N.J. Nilsson, Learning Machines, McGraw-Hill, New York, 1965.
[3] A.K. Jain, R.P.W. Duin, J. Mao, Statistical pattern recognition: a review, IEEE Trans. PAMI, 22(1): 4-37,
2000.
[4]R.A. Fisher, The use of multiple measurements in taxonomic problems, Annals of Eugenics, 7: 179-188,
1936.
[5] C.K. Chow, An optimum character recognition system using decision functions, IRE Trans. Electronic
Computers, 6: 247-254, 1957.
[6]G. Nagy, Pattern Recognition 1966 IEEE Workshop, IEEE Spectrum, 92-94, Feb. 1967.
[7]G. Nagy, State of the art in pattern recognition, Proc. IEEE, 56(5): 836-862, 1968.
[8]L.N. Kanal, Patterns in pattern recognition: 1968-1974, IEEE Trans. Information Theory, 20(6): 697-722,
1974.
[9]K. Fukunaga, Introduction to Statistical Pattern Recognition, Academic Press, 1972.
[10]R.O. Duda, P.E. Hart, Pattern Classification and Scene Analysis, John Wiley & Sons, New York, 1973.
[11] C.M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.
[12]K. Fukunaga, Introduction to Statistical Pattern Recognition, second edition, Academic Press, 1990.
[13]R.O. Duda, P.E. Hart, D.G. Stork, Pattern Classification, second edition, John Wiley & Sons, New York,
2001.
[14] A.P. Dempster, N.M. Laird, D.B. Rubin, Maximum-likelihood from incomplete data via the EM
algorithm, J. Royal Statistics Society B, 39: 1-38, 1977.
[15]S.J. Roberts, D. Husmeier, L. Rezek, W. Penny, Bayesian approaches to Gaussian mixture modeling,
IEEE Trans. PAMI, 20(11): 1133-1142, 1998.
[16]M.A.T. Figueiredo, A.K. Jain, Unsupervised learning of finite mixture models, IEEE Trans. PAMI, 24(3):
381-396, 2002.
[17]N. Ueda, Z. Ghahramani, Bayesian model search for mixture models based on optimizing variational
bounds, Neural Networks, 15(10): 1223-1241, 2003.
[18]P.M. Baggenstoss, The PDF projection theorem and the class-specific method, IEEE Trans. Signal
Processing, 51(3): 672-685, 2003.
[19] B. Moghaddam, A. Pentland, Probabilistic visual learning for object representation, IEEE Trans. PAMI,
19(7): 696-710, 1997.
[20]N. Bouguila, D. Ziou, J. Vaillancourt, Unsupervised learning of a finite mixture model based on the
Dirichlet distribution and its application, IEEE Trans. Image Processing, 13(11): 1533-1543, 2004. [21]N. Bouguila, D. Ziou, A hybrid SEM algorithm for high-dimensional unsupervised learning using a finite
generalized Dirichlet mixture, IEEE Trans. Image Processing, 15(9): 2657-2668, 2006.
[22] B. Sch?lkopf, J. Platt, J. Shawe-Taylor, A.J. Smola, R.C. Williamson, Estimating the support of a
high-dimensional distribution, Neural Computation, 13(7): 1443-1471, 2001.
[23] D.M.J. Tax, R.P.W. Duin, Support vector data description, Machine Learning, 54(1): 45-66, 2004.
[24]I. Guyon, A. Elisseeff, An introduction to variable and feature selection, J. Machine Learning Research, 3:
1157-1182, 2003.
[25]R. Kohavi, G. Tohu, Wrappers for feature selection, Artificial Intelligence, 97(1-2): 273-324, 1997.
[26]R. Tibshirani, Regression selection and shrinkage via the lasso, J. Royal Statistical Society Series B, 58(1):
267-288, 1996.
[27]J. Bi, K. Bennett, M. Embrecht, C. Breneman, M. Song, Dimensionality reduction via sparse support
vector machines, J. Machine Learning Research, 3: 1229-1243, 2003.
[28]P. Viola, M.J. Jones, Rapid object detection using a boosted cascade of simple features, Proc. CVPR 2001,
Hawaii, 2001, Vol.1, pp.511-518.
[29]J. Bins, B.A. Draper, Feature selection from huge feature sets, Proc. 8th ICCV, 2001, Vol.2, pp.159-165,
2001.
[30] A. Jain, D. Zongker, Feature selection: evaluation, application and small sample performance, IEEE
Trans. PAMI, 29(2): 153-158, 1997.
[31]M. Kudo, J. Sklansky, Comparison of algorithms that select features for pattern classifiers, Pattern
Recognition, 33(1): 25-41, 2000.
[32]I. Kononenko, Estimating attributes: analysis and extensions of RELIEF, Proc. ECML, Catana, Italy,
Springer-Verlag, 1994, pp.171-182.
[33]Y. Sun, Iterative RELIEF for feature weighting: algorithms, theories, and applications, IEEE Trans.
PAMI, 29(6): 1035-1051, 2007.
[34]R. Gilad-Bachrach, A. Navot, N. Tishby, Margin based feature selection—theory and algorithms, Proc.
21th ICML, Alberta, Canada, 2004.
[35]R. Battiti, Using mutual information for selecting features in supervised neural net learning, IEEE Trans.
Neural Networks, 5(4): 537-550, 1994.
[36] F. Fleuret, Fast binary feature selection with conditional mutual information, J. Machine Learning
Research, 5: 1531-1555, 2004.
[37]L. Yu, H. Liu, Efficient feature selection via analysis of relevance and redundancy, J. Machine Learning
Research, 5: 1205-1224, 2004.
[38] D.-Q. Dai, P.C. Yuen, Regularized discriminant analysis and its application to face recognition, Pattern
Recognition, 36(3): 845-847, 2003.
[39]P.N. Belhumeur, J.P. Hespanha, D.J. Kriegman, Eigenfaces vs. fisherfaces: recognition using
class-specific linear projection space, IEEE Trans. PAMI, 19(7): 711-720, 1997.
[40]J. Yang, J.-y. Yang, Why can LDA be performed in PCA transformed space? Pattern Recognition, 36(2):
563-566, 2003.
[41]L.-F. Chen, H.-Y. M. Liao, M.-T. Ko, J.-C. Lin, G.-J. Yu, A new LDA-based face recognition system
which can solve the small sample size, Pattern Recognition, 33(10): 1713-1726, 2000.
[42]H. Yu, J. Yang, A direct LDA algorithm for high-dimensional data---with application to face recognition,
Pattern Recognition, 34(10): 2067-2070, 2001.
[43]M. Loog, R.P.W. Duin, Linear dimensionality reduction via a heteroscedastic extension of LDA: the
Chernoff criterion, IEEE Trans. PAMI, 26(6): 732-739, 2004.
[44]K. Fukunaga, J. Mantock, Nonparametric discriminant analysis, IEEE Trans. PAMI, 5: 671-678, 1983.
[45] C. Lee, D.A. Landgrebe, Feature extraction based on decision boundary, IEEE Trans. PAMI, 15(4):
388-400, 1993.
[46]J. Zhang, Y. Liu, SVM decision boundary based discriminative subspace induction, Pattern Recognition,
38(10): 1746-1758, 2005.
[47]X. Wang, K.K. Paliwal, Feature extraction and dimensionality reduction algorithms and their applications
in vowel recognition, Pattern Recognition, 36(10): 2429-2439, 2003.
[48]K.E. Hild II, D. Erdogmus, K. Tokkola, J.C. Principe, Feature extraction using information-theoretic
learning, IEEE Trans. PAMI, 28(9): 1385-1392, 2006.
[49]T. Hastie, R. Tibshirani, Discriminant analysis by Gaussian mixtures, J. Royal Statist. Soc. Ser. B, 58(1):
155-176, 1996.
[50]M. Zhu, A.M. Matinez, Subclass discriminant analysis, IEEE Trans. PAMI, 28(8): 1274-1286, 2006.
[51]X. He, S. Yan, Y. Hu, H.-J. Zhang, Learning a locality preserving subspace for visual recognition, Proc.
9th ICCV, Nice, France, 2003, pp.385-392.
[52]S. Yan, D. Xu, B. Zhang, H.-J. Zhang, Q. Yang, S. Lin, Graph embedding and extension: a general
framework for dimensionality reduction, IEEE Trans. PAMI, 29(1): 40-51, 2007.
[53]J. Cheng, Q. Liu, H. Lu, Y.-W. Chen, Supervised kernel locality preserving projections for face
recognition, Neurocomputing, 67: 443-449, 2005.
[54]X. Geng, D.-C. Zhan, Z.-H. Zhou, Supervised nonlinear dimensionality reduction for visualization and
classification, IEEE Trans. SMC Part B, 35(6): 1098-1107, 2005.
[55] B. Sch?lkopf, A. Smola, K.-R. Müller. Nonlinear component analysis as a kernel eigenvalue problem,
Neural Computation, 10(5): 1299-1319, 1998.
[56]G. Baudat, F. Anouar, Generalized discriminant analysis using a kernel approach, Neural Computation,
12(10): 2385-2404, 2000.
[57]J. Yang, A.F. Frangi, J.-y. Yang, D. Zhang, Z. Jin, KPCA plus LDA: a complete kernel Fisher
discriminant framework for feature extraction and recognition, IEEE Trans. PAMI, 27(2): 238-244, 2005.
[58]J. Lu, K.N. Plataniotis, A.N. Venetsanopoulos, Face recognition using kernel direct discriminant analysis
algorithms, IEEE Trans. Neural Networks, 14(1): 117-126, 2003.
[59]J. Yang, D. Zhang, A.F. Frangi, J.-y. Yang, Two-dimensional PCA: a new approach to appearance-based
face representation and recognition, IEEE Trans. PAMI, 26(1): 131-137, 2004.
[60]J. Yang, D. Zhang, X. Yong, J.-y. Yang, Two-dimensional discriminant transform for face recognition,
Pattern Recognition, 38(7): 1125-1129, 2005.
[61]J. Ye, R. Janardan, Q. Li, Two-dimensional linear discriminant analysis, Advances in Neural Information
Processing Systems, 2004.
[62]L. Wang, X. Wang, X. Zhang, J. Feng, The equivalence of two-dimensional PCA to line-based PCA,
Pattern Recognition Letters, 26(1): 57-60, 2005.
[63] C.-L. Liu, M. Nakagawa, Evaluation of prototype learning algorithms for nearest neighbor classifier in
application to handwritten character recognition, Pattern Recognition, 34(3): 601-615, 2001.
[64]N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines, Cambridge University Press,
2000.
[65]Y. Freund, R.E. Schapire, A decision-theoretic generalization of on-line learning and an application to
boosting, Journal of Computer and System Sciences, 55(1): 119-139, 1997.
[66] B.-H. Juang, S. Katagiri, Discriminative learning for minimum error classification, IEEE Trans. Signal
Processing, 40(12): 3043-3054, 1992.
[67]J.H. Friedman, T. Hastie, T. Tibshirani, Additive logistic regression: a statistical view of boosting, The
Annals of Statistics, 38(2): 337-374, 2000.
[68]Y.D. Rubenstein , T. Hastie, Discriminative vs informative learning, Proc. 3rd Int. Conf. Knowledge
Discovery and Data Mining, Newport Beach, CA, 1997, pp.49-53.
[69] A.Y. Ng, M.I. Jordan, On discriminative vs. generative classifiers: a comparison of logistic regression and
na?ve Bayes, Advances in Neural Information Processing Systems 14, T.G. Dietterich, S. Becker, A.
Ghahramani (eds.), MIT Press, 2002.
[70]I. Ulusoy, C.M. Bishop, Generative versus discriminative methods for object recognition, CVPR 2005,
Vol.2, pp.258-265.
[71] A. Holub, P. Perona, A discriminative framework for modeling object classes, CVPR 2005, Vol.1,
pp.664-671.
[72] C.-L. Liu, H. Sako, H. Fujisawa, Discriminative learning quadratic discriminant function for handwriting
recognition, IEEE Trans. Neural Networks, 15(2): 430-444, 2004.
[73]J.A. Lasserre, C.M, Bishop, T.P. Minka, Principled hybrids of generative and discriminative models,
CVPR 2006, New York, Vol.1, pp.87-94.
[74] D. Grossman, P. Domingos, Learning Bayesian network classifiers by maximizing conditional likelihood,
Proc. 21th ICML, Alberta, Canada, 2004.
[75]R. Greiner, X. Su, B. Shen, W. Zhou, Structural extension to logistic regression: discriminative parameter
learning of belief net classifiers, Machine Learning, 59(3): 297-322, 2005.
[76]L. Breiman, Bagging predictors, Machine Learning, 24(2): 123-140, 1996.
[77]Y. Freund, R.E. Schapire, A decision-theoretic generalization of on-line learning and an application to
boosting, Journal of Computer and System Sciences, 55(1): 119-139, 1997.
[78]T.K. Ho, The random subspace method for constructing decision forests, IEEE Trans. Pattern Analysis
and Machine Intelligence, 20(8): 832-844, 1998.
[79] D. Opitz, Feature selection for ensembles, Proc. AAAI, 1999.
[80]T.G. Dietterich, G. Baliri, Solving multiclass learning problems via error-correcting output codes, Journal
of Artificial Intelligence Research, 2: 263-286, 1995.
[81] B. Moghaddam, T. Jebara, A. Pentland, Bayesian face recognition, Pattern Recognition, 33(11):
1771-1782, 2000.
[82]M.A.T. Figueiredo, Adaptive sparseness for supervised learning, IEEE Trans. PAMI, 25(9): 1150-1159,
2003.
[83]R. Polikar, L. Udpa, A.S. Udpa, V. Honavar, Learn++: an incremental learning algorithm for supervised
neural networks, IEEE Trans. SMC—Part C: Applications and Review, 31(4): 497-508, 2001.
[84]G. Cauwenberghs, T. Poggio, Incremental and decremental support vector machine learning, Advances in
Neural Information Processing Systems 13, T. Leen, T. Dietterich, V. Tresp (eds.), MIT Press, 2001.
[85]O. Chapelle, B. Scholkopf, A. Zien, Semi-Supervised Learning, The MIT Press, 2006.
[86]R. Fergus, P. Perona, A. Zisserman, Object class recognition by unsupervised scale-invariant learning,
Proc. IEEE Int. Conf. CVPR, 2003, Vol.2, 264-271.
[87] D. Crandall, D. Huttenlocher, Weakly supervised learning of part-based spatial models for visual object
recognition, ECCV 2006, LNCS 3979, Springer, 2006.
作者介绍
刘成林，中国科学院自动化研究所研究员、模式识别国家重点实验室副主任。1995年在中国科学院自动化研究所获得工学博士学位。中国计算机学会高级会员。研究兴趣包括模式识别、机器学习、文字识别与文档分析等。
谭铁牛，中科院自动化所研究员，模式识别国家重点实验室主任。1989年获英国帝国理工学院博士学位。中国图形图像学会常务副理事长、中国计算机学会与中国自动化学会副理事长、IEEE与IAPR Fellow。研究兴趣包括模式识别、计算机视觉、生物特征识别等。
模式识别的研究现状与发展趋势 摘要：随着现今社会信息技术的飞速发展, 人工智能的应用越来越广泛, 其中模式识别是人工智能应用的一个方面。而且现今的模式识别的应用也越来越得到大家的重视与支持，在各方面也有重大的进步。模式识别也成为人们身边不可或缺的一部分。关键词：人工智能，技术，模式识别，前景 Abstract：In the modern society with the rapid development of information technology, the application of a rtificial intelligence is more and more extensive, among them pattern recognition is one of the ap ply of artificial intelligence. And now the application of pattern recognition is also more and more to get everyone's attention and support, in various aspects have significant progress. Pattern rec ognition has become an integral part of people around. Keywords: Artificial Intelligence, Technology,Pattern Recognition, prospects 一，引言 如今计算机硬件的高速发展, 以及计算机应用领域的不断开拓, 人们开始要求计算机能够更有效地感知诸如声音、文字、图像、温度、震动等人类赖以发展自身、改造环境所运用的信息资料。但就一般意义来说, 目前一般计算机却无法直接感知它们, 我们常用的键盘、鼠标等外部设备, 对于这些外部世界显得无能为力。虽然摄像机、图文扫描仪、话筒等设备业已解决了上述非电信号的转换, 并与计算机联机, 但由于识别技术不高, 而未能使计算机真正知道采录后的究竟是什么信息。计算机对外部世界感知能力的低下, 成为开拓计算机应用的瓶颈, 也与其高超的运算能力形成强烈的对比。于是, 着眼于拓宽计算机的应用领域, 提高其感知外部信息能力的学科———模式识别, 便得到迅速发展。 人工智能所研究的模式识别是指用计算机代替人类或帮助人类感知模式, 是对人类感知外界功能的模拟, 研究的是计算机模式识别系统, 也就是使一个计算机系统具有模拟人类通过感官接受外界信息、识别和理解周围环境的感知能力。现将人工智能在模式识别方面的一些具体和最新的应用范围遍及遥感、生物医学图象和信号的分析、工业产品的自动无损检验、指纹鉴定、文字和语音识别、机器视觉地圈模式识别等方面。 二，现状 以地图模式识别为例，地图模式识别是由计算机来对地图进行识别与理解, 并借助一定的技术手段, 让计算机研究和分析地图上的各种模式信息, 获取地图要素的质量意义。其计算处理的过程类似于人对地图的阅读。 地图模式识别是近年来在地图制图领域中新兴的一门高新技术, 是信息时代人工智能、模式识别技术在地图制图中的具体应用。由于它是传统地图制图迈向数字地图制图的一座桥梁, 因此,地图模式识别遥感技术、地理信息系统一起, 被称为现代地图制图的三大技术。 目前, 地图模式识别由于具有广泛的应用价值和发展潜力,因而受到了人们的普遍重视。尤其是随着现今的计算机及其外部硬件环境的不断提高, 科技不过发展的情况下，
聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇；
（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
1.简述模式的概念及其直观特性，模式识别的分类，有哪几种方法。（6’） 答（1）：什么是模式？广义地说，存在于时间和空间中可观察的物体，如果我们可以区别它们是否相同或是否相似，都可以称之为模式。 模式所指的不是事物本身，而是从事物获得的信息，因此，模式往往表现为具有时间和空间分布的信息。 模式的直观特性：可观察性；可区分性；相似性。 答（2）：模式识别的分类： 假说的两种获得方法（模式识别进行学习的两种方法）： 监督学习、概念驱动或归纳假说； 非监督学习、数据驱动或演绎假说。 模式分类的主要方法： 数据聚类：用某种相似性度量的方法将原始数据组织成有意义的和有用的各种数据 集。是一种非监督学习的方法，解决方案是数据驱动的。 统计分类：基于概率统计模型得到各类别的特征向量的分布，以取得分类的方法。 特征向量分布的获得是基于一个类别已知的训练样本集。是一种监督分类的方法， 分类器是概念驱动的。 结构模式识别：该方法通过考虑识别对象的各部分之间的联系来达到识别分类的目 的。（句法模式识别） 神经网络：由一系列互相联系的、相同的单元（神经元）组成。相互间的联系可以 在不同的神经元之间传递增强或抑制信号。增强或抑制是通过调整神经元相互间联 系的权重系数来（weight）实现。神经网络可以实现监督和非监督学习条件下的分 类。 2.什么是神经网络？有什么主要特点？选择神经网络模式应该考虑什么因 素？（8’） 答（1）：所谓人工神经网络就是基于模仿生物大脑的结构和功能而构成的一种信息处理系统（计算机）。由于我们建立的信息处理系统实际上是模仿生理神经网络，因此称它为人工神经网络。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。 人工神经网络的两种操作过程：训练学习、正常操作（回忆操作）。 答（2）：人工神经网络的特点： 固有的并行结构和并行处理； 知识的分布存储； 有较强的容错性； 有一定的自适应性； 人工神经网络的局限性： 人工神经网络不适于高精度的计算； 人工神经网络不适于做类似顺序计数的工作； 人工神经网络的学习和训练往往是一个艰难的过程； 人工神经网络必须克服时间域顺序处理方面的困难； 硬件限制； 正确的训练数据的收集。 答（3）：选取人工神经网络模型，要基于应用的要求和人工神经网络模型的能力间的匹配，主要考虑因素包括：
人工智能与模式识别 摘要：信息技术的飞速发展使得人工智能的应用围变得越来越广，而模式识别作为其中的一个重要方面，一直是人工智能研究的重要方向。在介绍人工智能和模式识别的相关知识的同时，对人工智能在模式识别中的应用进行了一定的论述。模式识别是人类的一项基本智能，着20世纪40年代计算机的出现以及50年代人工智能的兴起，模式识别技术有了长足的发展。模式识别与统计学、心理学、语言学、计算机科学、生物学、控制论等都有关系。它与人工智能、图像处理的研究有交叉关系。模式识别的发展潜力巨大。 关键词：模式识别；数字识别；人脸识别中图分类号； Abstract: The rapid development of information technology makes the application of artificial intelligence become more and more widely. Pattern recognition, as one of the important aspects, has always been an important direction of artificial intelligence research. In the introduction of artificial intelligence and pattern recognition related knowledge at the same time, artificial intelligence in pattern recognition applications were discussed.Pattern recognition is a basic human intelligence, the emergence of the 20th century, 40 years of computer and the rise of artificial intelligence in the 1950s, pattern recognition technology has made great progress. Pattern recognition and statistics, psychology,
模式识别研究进展 刘成林，谭铁牛 中国科学院自动化研究所 模式识别国家重点实验室 北京中关村东路95号 摘要 自20世纪60年代以来，模式识别的理论与方法研究及在工程中的实际应用取得了很大的进展。本文先简要回顾模式识别领域的发展历史和主要方法的演变，然后围绕模式分类这个模式识别的核心问题，就概率密度估计、特征选择和变换、分类器设计几个方面介绍近年来理论和方法研究的主要进展，最后简要分析将来的发展趋势。 1. 前言 模式识别(Pattern Recognition)是对感知信号（图像、视频、声音等）进行分析，对其中的物体对象或行为进行判别和解释的过程。模式识别能力普遍存在于人和动物的认知系统，是人和动物获取外部环境知识，并与环境进行交互的重要基础。我们现在所说的模式识别一般是指用机器实现模式识别过程，是人工智能领域的一个重要分支。早期的模式识别研究是与人工智能和机器学习密不可分的，如Rosenblatt的感知机[1]和Nilsson的学习机[2]就与这三个领域密切相关。后来，由于人工智能更关心符号信息和知识的推理，而模式识别更关心感知信息的处理，二者逐渐分离形成了不同的研究领域。介于模式识别和人工智能之间的机器学习在20世纪80年代以前也偏重于符号学习，后来人工神经网络重新受到重视，统计学习逐渐成为主流，与模式识别中的学习问题渐趋重合，重新拉近了模式识别与人工智能的距离。模式识别与机器学习的方法也被广泛用于感知信号以外的数据分析问题（如文本分析、商业数据分析、基因表达数据分析等），形成了数据挖掘领域。 模式分类是模式识别的主要任务和核心研究内容。分类器设计是在训练样本集合上进行优化（如使每一类样本的表达误差最小或使不同类别样本的分类误差最小）的过程，也就是一个机器学习过程。由于模式识别的对象是存在于感知信号中的物体和现象，它研究的内容还包括信号/图像/视频的处理、分割、形状和运动分析等，以及面向应用（如文字识别、语音识别、生物认证、医学图像分析、遥感图像分析等）的方法和系统研究。 本文简要回顾模式识别领域的发展历史和主要方法的演变，介绍模式识别理论方法研究的最新进展并分析未来的发展趋势。由于Jain等人的综述[3]已经全面介绍了2000年以前模式分类方面的进展，本文侧重于2000年以后的研究进展。
计算机工程与应用2006.16 引言 聚类分析是数据挖掘领域中的一个重要分支[1],是人们认 和探索事物之间内在联系的有效手段,它既可以用作独立的 据挖掘工具,来发现数据库中数据分布的一些深入信息,也 以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一 簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。 受生物进化机理的启发,科学家提出许多用以解决复杂优 问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他 其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得 著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体 仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上 出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内 到应用。 2聚类概念及蚁群聚类算法 一个簇是一组数据对象的集合,在同一个簇中的对象彼此 类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x 1 ,x 2 ,…,x n },!i∈{1,2,…,n},x i ={x i1 ,x i2 , …,x
模式识别研究进展 摘要：自20 世纪60年代以来，模式识别的理论与方法研究及在工程中的实际应用取得了很大的进展。本文先简要回顾模式识别领域的发展历史和主要方法的演变，然后围绕模式分类这个模式识别的核心问题，就概率密度估计、特征选择和变换、分类器设计几个方面介绍近年来理论和方法研究的主要进展，最后简要分析将来的发展趋势。 1. 前言 模式识别（Pattern Recognition）是对感知信号（图像、视频、声音等）进行分析，对其中的物体对象或行为进行判别和解释的过程。模式识别能力普遍存在于人和动物的认知系统，人和动物获取外部环境知识，并与环境进行交互的重要基础。我们现在所说的模式识别一般是指用机器实现模式识别过程，是人工智能领域的一个重要分支。早期的模式识别研究是与人工智能和机器学习密不可分的，如Rosenblatt 的感知机和Nilsson 的学习机就与这三个领域密切相关。后来，由于人工智能更关心符号信息和知识的推理，而模式识别更关心感知信息的处理，二者逐渐分离形成了不同的研究领域。介于模式识别和人工智能之间的机器学习在20 世纪80 年代以前也偏重于符号学习，后来人工神经网络重新受到重视，统计学习逐渐成为主流，与模式识别中的学习问题渐趋重合，重新拉近了模式识别与人工智能的距离。模式识别与机器学习的方法也被广泛用于感知信号以外的数据分析问题（如文本分析、商业数据分析、基因表达数据分析等），形成了数据挖掘领域。模式分类是模式识别的主要任务和核心研究内容。分类器设计是在训练样本集合上进行优化（如使每一类样本的表达误差最小或使不同类别样本的分类误差最小）的过程，也就是一个机器学习过程。由于模式识 别的对象是存在于感知信号中的物体和现象，它研究的内容还包括信号/图像/ 视频的处理、 分割、形状和运动分析等，以及面向应用（如文字识别、语音识别、生物认证、医学图像分析、遥感图像分析等）的方法和系统研究。 本文简要回顾模式识别领域的发展历史和主要方法的演变，介绍模式识别理论方法研究的最新进展并分析未来的发展趋势。由于Jain 等人的综述[3] 已经全面介绍了2000 年以前模式分类方面的进展，本文侧重于2000 年以后的研究进展。 2. 历史回顾 现代模式识别是在20 世纪40 年代电子计算机发明以后逐渐发展起来的。在更早的
K-Means聚类算法 1.算法原理 k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。 k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。k-means算法的处理过程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下： 这里E是数据库中所有对象的平方误差的总和，p是空间中的点，mi 是簇Ci的平均值。该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧几里得距离,当然也可以用其他距离度量。k-means聚类算法的算法流程如下： 输入：包含n个对象的数据库和簇的数目k； 输出：k个簇，使平方误差准则最小。 步骤： (1) 任意选择k个对象作为初始的簇中心； (2) repeat； (3) 根据簇中对象的平均值，将每个对象(重新)赋予最类似的簇； (4) 更新簇的平均值，即计算每个簇中对象的平均值；
(5) 直到不再发生变化。 2.主要代码 主程序： clc; clear; close all; %% 聚类算法测试 nSample = [500, 500, 500]; % 3维情况 dim = 3; coeff = { [-2 0.8; -1 0.9; 2 0.7;], .... [1 0.9; -2 0.7; -2 0.8; ], ... [-2 0.7; 2 0.8; -1 0.9; ], }; data = createSample(nSample, dim , coeff); %% 得到训练数据 nClass = length(nSample); tlabel = []; tdata = []; for i = 1 : nClass
K-means聚类算法研究综述 摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means 聚类的进一步研究方向。 关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵 Review of K-means clustering algorithm Abstract: K-means clustering algorithm is reviewed. K-means clustering algorithm is a NP hard optimal problem and global optimal result cannot be reached. The goal，main steps and example of K-means clustering algorithm are introduced. K-means algorithm requires three user-specified parameters: number of clusters K，cluster initialization，and distance metric. Problems and improvement of K-means clustering algorithm are summarized then. Further study directions of K-means clustering algorithm are pointed at last. Key words: K-means clustering algorithm; NP hard optimal problem; number of clusters K; cluster initialization; distance metric K-means聚类算法是由Steinhaus1955年、Lloyed1957年、Ball & Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然K-means聚类算法被提出已经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。 文中总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究方向。 1经典K-means聚类算法简介 1.1K-means聚类算法的目标函数 对于给定的一个包含n个d维数据点的数据集 12 {x,x,,x,,x} i n X=??????，其中d i x R ∈，以及要生成的数据子集的数目K，K-means聚类算法将数据对象组织为 K个划分{c,i1,2,} k C K ==???。每个划分代表一个类c k，每个类c k有一个类别中心iμ。选取欧氏距离作为相似性和 距离判断准则，计算该类内各点到聚类中心 i μ的距离平方和 2 (c) i i k i k x C J xμ ∈ =- ∑（1） 聚类目标是使各类总的距离平方和 1 (C)(c) K k k J J = =∑最小。 22 1111 (C)(c) i i K K K n k i k ki i k k k x C k i J J x d x μμ ==∈== ==-=- ∑∑∑∑∑ （2）其中， 1 i i ki i i x c d x c ∈ ? =? ? ? 若 若 ，显然，根据最小二乘 法和拉格朗日原理，聚类中心 k μ应该取为类别 k c类各数据点的平均值。 K-means聚类算法从一个初始的K类别划分开始，然
模式识别发展及现状综述 xxx （xxxxxxxxxxxxxxxxxxx） 摘要 [摘要]：通过对模式识别的发展及现状进行调查研究，了解到模式识别的理论和方法在很多科学和技术领域中得到了广泛的应用，极大的推动了人工智能系统的发展，同时扩大了计算机应用的可能性。模式识别 的研究主要集中在研究生物体(包括人)是如何感知对象的，以及在给定的任务下，如何用计算机实现模式 识别的理论和方法。本文详细的阐述了模式识别系统的组成结构以及模式识别的现状并展望了未来的模式 识别的发展趋势。 [关键词]：模式识别;模式识别的应用 Abstract [Abstract]:through the investigation and Study on the present situation and development of pattern recognition, knowing that the theory and method of pattern recognition has been widely used in many fields of science and technology and greatly promoting the development of artificial intelligence systems as well as expanding the fields of computer applied to.The research of pattern recognition mainly concentrated on the research of the theory and method of pattern recognition which how the organisms(including humans)to perceive objects as well as,in a given task,how to realize the pattern recognition with computer.This paper expounds the present situation and system structure of the pattern recognition as well as prospects the development trend in the future of pattern recognition. [keyword]:pattern recognition;pattern recognition applications 1前言 模式识别诞生于20世纪20年代，随着40年代计算机的出现，50年代人工智能的兴起，模式识别在60年代初迅速发展成一门学科。什么是模式和模式识别呢？广义地说，存在于时间和空间中可观察的事物，如果可以区别它们是否相同或相似，都可以称之为模式；狭义地说，模式是通过对具体的个别事物进行观测所得到的具有时间和空间分布的信息；把模式所属的类别或同一类中模式的总体称为模式类(或简称为类)[1]。而“模式识别”则是在某些一定量度或观测基础上把待识模式划分到各自的模式类中去。 经过多年的研究和发展，模式识别技术已广泛被应用于人工智能、计算机工程、机器人学、神经生物学、医学、侦探学以及高能物理、考古学、地质勘探、宇航科学和武器技术等许多重要领域，如语音识别、语音翻译、人脸识别、指纹识别、生物认证技术等。模式识别的技术对国民经济建设和国防科技发展的重要性已得到了人们的认可和广泛重视。本文将就模式识别所涉及的基本问题、研究的领域及其当前进展现状进行详细的介绍，并对模式识别的发展趋势进行展望。 2模式识别 2.1模式识别系统 一个计算机模式识别系统基本上是由三个相互关联而又有明显区别的过程组成的，即数据生成、模式分析和模式分类。有两种基本的模式识别方法，即统计模式识别方法和结构
模式识别基础概念文献综述 一．前言 模式识别诞生于20世纪20年代。随着20世纪40年代计算机的出现，20世纪50年代人工智能的兴起，模式识别在20世纪60年代迅速发展成为一门学科。在20世纪60年代以前，模式识别主要限于统计学领域的理论研究，计算机的出现增加了对模式识别实际应用的需求，也推动了模式识别理论的发展。经过几十年的研究，取得了丰硕的成果，已经形成了一个比较完善的理论体系，主要包括统计模式识别、结构模式识别、模糊模式识别、神经网络模式识别和多分类器融合等研究内容。 模式识别就是研究用计算机实现人类的模式识别能力的一门学科，目的是利用计算机将对象进行分类。这些对象与应用领域有关，它们可以是图像、信号，或者任何可测量且需要分类的对象，对象的专业术语就是模式（pattern）。按照广义的定义，存在于时间和空间中可观察的事物，如果可以区别它们是否相同或相似，都可以成为模式。 二．模式识别基本概念 <一>.模式识别系统 模式识别的本质是根据模式的特征表达和模式类的划分方法，利用计算机将模式判属特定的类。因此，模式识别需要解决五个问题：模式的数字化表达、模式特性的选择、特征表达方法的确定、模式类的表达和判决方法的确定。一般地，模式识别
系统由信息获取、预处理、特征提取和选择、分类判决等4部 分组成，如图1-1所示。 观察对象→→→→→→→→→类→类别号信息获取预处理特征提取和选择分类判决 图1-1模式识别系统的组成框图 <二>.线性分类器 对一个判别函数来说，应该被确定的是两个内容：其一为方程 的形式；其二为方程所带的系数。对于线性判别函数来说方程 的形式是线性的，方程的维数为特征向量的维数，方程组的数 量则决定于待判别对象的类数。对M类问题就应该有M个线 性判别函数；对两类问题如果采用“+”“-”判别，则判别函数 可以只有一个。既然方程组的数量、维数和形式已定，则对判 别函数的设计就是确定函数的各系数，也就是线性方程的各权 值。在计算机上确定各权值时采用的是“训练”或“学习”的 方法，这就是待识别的模式集中挑选一批有代表的样本，它们 经过人工判读成为已知类别的样本，把这批样本逐个输入到计 算机的“训练”程序（或算法）中去，通过一次一次的迭代最 后得到正确的线性判别函数，这样一个迭代的运算的过程成为 训练过程。由于样本的分类首先经过人工判读，因而这样的构 成分类器也称为有人监督或有教师的分类器。 <三>.特征选择和提取 <1>、特征选择 特征的获取是依赖于具体的问题和相关专业的知识的，无法进
信息疼术2018年第6期文章编号=1009 -2552 (2018)06 -0092 -03 DOI：10.13274/https://www.doczj.com/doc/df17910188.html,ki.hdzj.2018. 06.019 基于聚类的图像分割方法综述 赵祥宇\陈沫涵2 (1.上海理工大学光电信息与计算机学院，上海200093; 2.上海西南位育中学，上海200093) 摘要：图像分割是图像识别和机器视觉领域中关键的预处理操作。分割理论算法众多，文中 具体介绍基于聚类的分割算法的思想和原理，并将包含的典型算法的优缺点进行介绍和分析。经过比较后，归纳了在具体应用中如何对图像分割算法的抉择问题。近年来传统分割算法不断 被科研工作者优化和组合，相信会有更多的分割新算法井喷而出。 关键词：聚类算法；图像分割；分类 中图分类号：TP391.41 文献标识码：A A survey of image segmentation based on clustering ZHAO Xiang-yu1，CHEN Mo-han2 (1.School of Optical Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai200093，China；2.Shanghai Southwest Weiyu Middle School，Shanghai200093，China) Abstract:Image segmentation is a key preprocessing operation in image recognition and machine vision. There are many existing theoretical methods,and this paper introduces the working principle ol image segmentation algorithm based on clustering.Firstly,the advantages and disadvantages ol several typical algorithms are introduced and analyzed.Alter comparison,the paper summarizes the problem ol the selection ol image segmentation algorithm in practical work.In recent years,the traditional segmentation algorithms were improved and combined by the researchers,it believes that more new algorithms are blown out. Key words:clustering algorithm；image segmentation；classilication 0引百 近年来科学技术的不断发展，计算机视觉和图像 识别发挥着至关重要的作用。在实际应用和科学研 究中图像处理必不可少,进行图像处理必然用到图像 分割方法,根据检测图像中像素不重叠子区域，将感 兴趣目标区域分离出来。传统的图像分割方法:阈值 法[1]、区域法[2]、边缘法[3]等。近年来传统分割算法 不断被研究人员改进和结合，出现了基于超像素的分 割方法[4]，本文主要介绍超像素方法中基于聚类的经 典方法，如Mean Shift算法、K-m eans 算法、Fuzzy C-mean算法、Medoidshilt算法、Turbopixels算法和 SLIC 算法。简要分析各算法的基本思想和分割效果。 1聚类算法 1.1 Mean Shil't算法 1975年,Fukunaga[5]提出一种快速统计迭代算法，即Mean Shilt算法（均值漂移算法）。直到1995 年,Cheng[6]对其进行改进，定义了核函数和权值系 数，在全局优化和聚类等方面的应用，扩大了 Mean shil't算法适用范围。1997至2003年间，Co-maniciu[7-9]提出了基于核密度梯度估计的迭代式 搜索算法,并将该方法应用在图像平滑、分割和视频 跟踪等领域。均值漂移算法的基本思想是通过反复 迭代计算当前点的偏移均值，并挪动被计算点，经过 反复迭代计算和多次挪动，循环判断是否满足条件, 达到后则终止迭代过程[10]。Mean shil't的基本形 式为： 收稿日期：2017-06 -13 基金项目：国家自然科学基金资助项目（81101116) 作者简介：赵祥宇（1992-)，男，硕士研究生，研究方向为数字图像处理。 —92 —
模式识别研究进展 摘要：自20世纪60年代以来，模式识别的理论与方法研究及在工程中的实际应用取得了很大的进展。本文先简要回顾模式识别领域的发展历史和主要方法的演变，然后围绕模式分类这个模式识别的核心问题，就概率密度估计、特征选择和变换、分类器设计几个方面介绍近年来理论和方法研究的主要进展，最后简要分析将来的发展趋势。 1. 前言 模式识别(Pattern Recognition)是对感知信号（图像、视频、声音等）进行分析，对其中的物体对象或行为进行判别和解释的过程。模式识别能力普遍存在于人和动物的认知系统，人和动物获取外部环境知识，并与环境进行交互的重要基础。我们现在所说的模式识别一般是指用机器实现模式识别过程，是人工智能领域的一个重要分支。早期的模式识别研究是与人工智能和机器学习密不可分的，如Rosenblatt 的感知机和Nilsson的学习机就与这三个领域密切相关。后来，由于人工智能更关心符号信息和知识的推理，而模式识别更关心感知信息的处理，二者逐渐分离形成了不同的研究领域。介于模式识别和人工智能之间的机器学习在20 世纪80 年代以前也偏重于符号学习，后来人工神经网络重新受到重视，统计学习逐渐成为主流，与模式识别中的学习问题渐趋重合，重新拉近了模式识别与人工智能的距离。模式识别与机器学习的方法也被广泛用于感知信号以外的数据分析问题（如文本分析、商业数据分析、基因表达数据分析等），形成了数据挖掘领域。模式分类是模式识别的主要任务和核心研究内容。分类器设计是在训练样本集合上进行优化（如使每一类样本的表达误差最小或使不同类别样本的分类误差最小）的过程，也就是一个机器学习过程。由于模式识别的对象是存在于感知信号中的物体和现象，它研究的内容还包括信号/图像/ 视频的处理、分割、形状和运动分析等，以及面向应用（如文字识别、语音识别、生物认证、医学图像分析、遥感图像分析等）的方法和系统研究。 本文简要回顾模式识别领域的发展历史和主要方法的演变，介绍模式识别理论方法研究的最新进展并分析未来的发展趋势。由于Jain 等人的综述[3]已经全面介绍了2000 年以前模式分类方面的进展，本文侧重于2000 年以后的研究进展。 2. 历史回顾
收稿日期:2006201204;修返日期:2006203219基金项目:国家自然科学基金资助项目(60473117) 数据挖掘中的聚类算法综述 3 贺 玲,吴玲达,蔡益朝 (国防科学技术大学信息系统与管理学院,湖南长沙410073) 摘 要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。全面总结了数据挖掘中聚类算法的研究现状,分析比较了它们的性能差异和各自存在的优点及问题,并结合多媒体领域的应用需求指出了其今后的发展趋势。 关键词:数据挖掘;聚类;聚类算法 中图法分类号:TP391 文献标识码:A 文章编号:100123695(2007)0120010204 Survey of Clustering A lgorith m s in Data M ining HE L ing,WU L ing 2da,CA I Yi 2chao (College of Infor m ation Syste m &M anage m ent,N ational U niversity of D efense Technology,Changsha Hunan 410073,China ) Abstract:Clustering is an i m portant technique in Data M ining (DM )f or the discovery of data distributi on and latent data pattern .This paper p r ovides a detailed survey of current clustering algorith m s in DM at first,then it makes a comparis on a mong the m,illustrates the merits existing in the m,and identifies the p r oblem s t o be s olved and the ne w directi ons in the fu 2ture according t o the app licati on require ments in multi m edia domain .Key works:Data M ining;Clustering;Clustering A lgorith m 1 引言 随着信息技术和计算机技术的迅猛发展,人们面临着越来越多的文本、图像、视频以及音频数据,为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识,数据挖掘(Data M ining,DM )技术应运而生。所谓数据挖掘,就是从大量无序 的数据中发现隐含的、有效的、有价值的、可理解的模式,进而发现有用的知识,并得出时间的趋向和关联,为用户提供问题求解层次的决策支持能力。与此同时,聚类作为数据挖掘的主要方法之一,也越来越引起人们的关注。 本文比较了数据挖掘中现有聚类算法的性能,分析了它们各自的优缺点并指出了其今后的发展趋势。 2 DM 中现有的聚类算法 聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中,聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。 本文以聚类算法所采用的基本思想为依据将它们分为五类,即层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法,如图1所示。 聚类 层次聚类算法 聚合聚类:Single 2L ink,Comp lete 2L ink,Average 2L ink 分解聚类 分割聚类算法基于密度的聚类基于网格的聚类 基于图论的聚类 基于平方误差的迭代重分配聚类:概率聚类、最近邻 聚类、K 2medoids 、K 2means 基于约束的聚类算法 机器学习中的聚类算法 人工神经网络方法 基于进化理论的方法:模拟退火、遗传算法用于高维数据的聚类算法 子空间聚类 联合聚类 图1 聚类算法分类示意图 211 层次聚类算法 层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类,它又可以分为两类,即自底向上的聚合层次聚类和自顶向下的分解层次聚类。聚合聚类的策略是先将每个对象各自作为一个原子聚类,然后对这些原子聚类逐层进行聚合,直至满足一定的终止条件;后者则与前者相反,它先将所有的对象都看成一个聚类,然后将其不断分解直至满足终止条件。 对于聚合聚类算法来讲,根据度量两个子类的相似度时所依据的距离不同,又可将其分为基于Single 2L ink,Comp lete 2L ink 和Average 2L ink 的聚合聚类。Single 2L ink 在这三者中应用最为广泛,它根据两个聚类中相隔最近的两个点之间的距离来评价这两个类之间的相似程度,而后两者则分别依据两类中数据点之间的最远距离和平均距离来进行相似度评价。 CURE,ROCK 和CHAME LE ON 算法是聚合聚类中最具代 表性的三个方法。 Guha 等人在1998年提出了C URE 算法 [1] 。该方法不用 单个中心或对象来代表一个聚类,而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类,这样就可以