《基于预分类的逆变异分类器算法》-工学论文，软件工程论文-论文范文参考-科学狗论文网

标题

基于预分类的逆变异分类器算法

范文

蒋然+张光桃

摘要：遗传算法已经在许多领域得到了成功的应用，在解决模式识别问题时，由于遗传中的变异过程的存在导致了模式差异，如果能够减少这种差异性，就可以提高模式分类的正确率。针对这种情况，本文提出了在预分类基础上的一种逆变异算法，该算法采用遗传算法中变异过程的逆过程，来减少模式的差异性，达到提高模式分类正确率的目的。在ORL人脸库上的实验结果表明，该分类器的模式识别率明显高于传统的分类器算法及遗传算法。

关键词：遗传算法；逆变异算法；预分类；人脸识别

中图分类号：TP391.4 文献标识码：A DOI：10.3969/j.issn.1003-6970.2015.02.009

0 引言

遗传算法是根据自然界的“物竞天择，适者生存”现象提出的一种随机搜索算法。该算法具有良好的全局搜索能力，以及处理的并行性、鲁棒性等优点。遗传算法主要被用于解决复杂而又难以处理的问题，如多极值函数优化问题、组合优化问题、调度问题等。

在模式识别领域中，遗传算法也得到了广泛的应用，模式的特征提取是模式识别的主要研究领域之一，目前，模式特征提取的主要方法是Fisher方法、PCA方法、ICA方法等，而遗传算法特别适合解决随机搜索优化问题，它采用自然选择、变异等操作可以选择出最优的模式特征向量。吴建龙等提出了一种基于改进遗传算法（Optimization genetical gorithm，OGA）的人脸特征提取算法，该算法的特点是利用小波和张量PCA提取人脸图像特征，再采用遗传算法进行特征向量优化，该算法还对标准遗传算法进行了改进。但是，该算法还是存在易陷入局部最优、算法多次迭代收敛速度慢等问题。胡选子等提出了条件概率与遗传算法相结合的分类方法，该方法先用条件概率计算单个属性对分类的作用，再用遗传算法判断各属性对分类的重要程度，并将该方法应用于数据挖掘中，取得了很好的效果，但是必须指出，对于图像数据的模式识别问题，如人脸识别，由于图像特征向量的各个属性数据不具有确切的物理含义，因此，限制了该方法在图像数据识别问题方面的应用。

分类器设计是模式识别的另一个主要研究领域，其中，刑宗文等将遗传算法同模糊建模方法结合，提出了一种基于多目标遗传算法的模糊建模方法，该方法实现了最大分类精度于最少特征变量的最优选取，但是该方法需要优化选取模糊隶属度函数和遗传算法中评价函数的多个参数，且该方法没有被应用于解决人脸识别这类复杂的高维小样本数据的识别问题，具有一定的局限性。而在如何解决高维小样本问题方面，遗传算法也有许多研究成果，如陈杰等采用遗传算法来生成虚拟训练样本，提高了人脸检测的正确率。

遗传算法的本质是通过遗传使子代具有父代的基因，而变异可以使子代具有比父代更加优良的基因。对于模式识别问题，可以将训练样本看作父代，而测试样本就可以看作是对训练样本进行遗传及变异操作而得到的子代样本。这时模式识别过程就是在知道子代遗传基因的基础上，如何判断该基因是从哪些父代基因中遗传过来的。因此，模式识别问题的核心转变为判断子代与父代的基因相似性。而在遗传的主要过程中，子代与父代差异性的主要是由变异过程产生的。因此，如果可以降低甚至消除变异过程的影响，则可以大大提高子代与父代的相似度，即可提高模式分类的正确率。

基于上述考虑，本文对遗传算法中变异过程的逆过程进行了分析，在此基础上提出了基于逆变异的分类器算法。该算法选取出子代与父代差异性最大的基因，并将该基因看作是由于基因变异所引起的，因此，在分类识别时将忽略变异基因的影响，从而提高了模式分类的正确率。由于本文的逆变异分类器需要判断子代与父代各个基因的差异性，因此，算法的效率较低，本文采用文献的多种分类器组合方法来进行预分类，对预分类结果不同的测试样本，再采用本文的逆变异分类器进行分类识别，从而极大地提高了算法的效率。

1 本文算法

1.1 本文算法的基本思想

1.1.1 遗传算法

遗传算法主要思想是：首先创建初始种群，并用一串二进制数对每个个体进行编码，然后开始进化。那些相对于目标来说更好的解会获得更多的机会进行繁殖。个体相互之间进行交叉，同时部分个体会进行变异。个体的优劣程度用一个目标函数（适应度函数）来衡量。适应度高的将被保留下来，反之将会被遗弃。一直到满足迭代的终止条件，遗传算法的迭代过程将被终止，从而得到最优解。

假设待优化函数为f（x），x是一个向量，利用f（x）构造出适应度函数g（x）=h（f（x））。当f（x）取得最优值时，g（x）必须取得最大值。因此，遗传算法就可描述为：在变量空间中搜索一个使得g（x）取得最大值的x，则这个x使得f（x）取得最优值，遗传算法的主要步骤如下：

1）确定遗传算法的参数：总个体数为N，遗传代数T，交叉概率为Pc，变异概率为Pm，代沟为G。

2）编码：对样本进行归一化处理，本文采用了浮点编码法。

3）初始化种群：计算个体的适应度，设第i个个体的适应度为Fi，根据G计算代间重叠个体的个数。

4）个体选择：从当前代中选择两个个体，其中第i个个体被选中的概率为，

其中，a为参数取为常数，若a为变量，则此时的交叉运算可称为非均匀算术交叉。离散交叉是指在个体之间交换变量的值，子个体的每个变量可按等概率随机地挑选父个体。

6）变异：变异是指改变个体编码串中的某些基因值，从而形成新的个体。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。

7）评价函数：为了体现染色体的适应能力，引入对问题中的每一个染色体都能进行度量的函数，评价函数可以决定染色体的优劣程度，它体现了自然进化中的优胜劣汰原则。

1.1.2 逆变异过程

逆变异过程的目的就是为了降低遗传算法变异过程造成的父代与子代之间的差异性。对于人脸识别问题，将测试样本看作由训练样本经过遗传变异后得到的子代样本。其识别过程就可以看作是衡量子代和父代的基因相似性，即在知道了子代（测试样本）的遗传基因时，如何判断该基因是从哪些父代（训练样本）基因中通过遗传变异得来的；也就是说这种相似性的计算结果可以直接反应父代与子代之间的差异性的大小。因此，如果可以减少因变异所引起的子代与父代的差异性，就可以提高模式分类的正确率。

人脸识别就是要对子代与父代的基因链码进行相似度测量。较通用的相似度测量方法是最近邻分类器和最小距离分类器。最近邻分类器是将未知样本判别为与它最近的训练样本同类，该算法是采用各类中的全部样本作为代表点。从遗传算法的角度分析，可以将最近邻分类器看作是判断子代同其单个父代的相似性，如判断儿子与父亲或儿子与母亲的相似度。这种分类器的缺点是没有考虑遗传中的交叉和变异对子代基因的影响。

最小距离分类器取各类均值向量作为该类的代表，将未知样本划分到离它最近的代表点所属的类别。如将公式（2）的参数诹为0.5，则公式（2）转变为：

通过上述分析可以得出如下结论：

1）当采用最近邻分类器进行人脸识别时，可以识别出子代与单个父代最相似的个体，即儿子与父亲或母亲最相似的个体；

2）当采用最小距离分类器进行人脸识别时，相当于判断子代基因与父代基因均值的距离，因此，可以识别出子代与所有父代基因均值最相似的个体，即儿子既像父亲又像母亲的个体。由公式（5）可以看出，采用最小距离分类器可以部分克服基因交叉对子代的影响。

3）对于在遗传过程中发生变异的个体，即儿子既不像父亲又不像母亲的个体，采用上述两种分类器就很难做出正确的识别。

变异就是在染色体的基因链码中某个或某些基因发生了突变，本文提出的逆变异分类器就是通过消除基因突变的影响，来提高模式识别的正确率，本文采用以下公式找出变异基因：

满足公式（6）的基因就是子代与父代差异最大的基因，也就是造成模式错判的最大基因。因此，本文采用下式计算两个个体的基因链码相似度：

采用公式（7）计算基因距离时，可以去除差异最大的基因（变异基因）对基因相似度的影响，采用公式（8）重写公式（3）如下所示：

1.2 本文算法具体描述

逆变异分类器对每个测试样本都要计算其基因与全体训练样本基因的相似程度，并找出变异基因，因此，这种分类器算法的效率是比较低的。而传统的分类器方法可以对大多数测试样本给出正确的分类，这些传统的分类器方法包括最小距离分类器、最近邻分类器、Brdyes分类器等。为了提高逆变异算法的效率，本文采用文献的多分类器组合方法对测试样本进行预分类，对于预分类结果不同的测试样本再采用本文的逆变异分类器算法进行分类识别，这样就大大提高了模式的识别效率。

预分类的目的是将测试样本分成两部分，一部分是预分类“可能正确”的，另一部分是预分类“可能错误”的。具体方法是对测试样本同时采用两种不同的分类器进行预分类，并对分类结果进行融合。当两分类器分类结果相同时，就认为该分类结果是“可能正确”的，并将该结果作为预分类结果。当两分类器的分类结果不同时，则认为对该测试样本的分类可能是错误的。对这部分测试样本再采用逆变异算法进行分类识别，并将识别结果与预分类样本集中的样本一起进行正确率测试并输出，预分类算法如下图所示。

从图1中可以看出，经过预分类后，再采用逆变异算法对测试样本集2中的测试样本再次进行分类识别。最后，将分类结果与预分类结果一起进行正确率测试，最后以识别率的形式输出。本文的算法步骤如下：

（1）特征提取：在两个特征子空间中，分别对特征向量进行特征提取，两个特征子空间可以采用Fisher及PCA特征子空间。

（2）预分类：分别采用最小距离和最近邻分类器，对不同特征子空间的特征向量进行分类识别。的类别中。

（5）正确率测试：将步骤（4）的分类结果与预分类结果XS一起进行正确率测试，并将测试结果作为最终结果输出。

从上述算法步骤中可以看出本文算法与文献算法的不同之处在于，在预分类后，文献采用最近邻分类器进行分类识别，而本文采用的是逆变异分类器。

2 实验及分析

本文采用剑桥大学ORL人脸图像库进行对比实验，ORL人脸库是国际上人脸识别领域常用的人脸图像库，该库由40人的准正面灰度脸像组成，每人10幅92×112图像组成。其中有些图像是拍摄于不同时期，人的脸部表情和脸部细节有着不同程度的变化。为了验证本文算法的有效性，训练集人脸图像选择采用随机抽取方式得到，图像的预处理采用两次小波变换，将图像变换为23～28像素。

特征提取方法采用基于类间离散矩阵Sb的主成分分析方法，将模式投影到39维的特征子空间中。本文的逆变异分类器算法，其预分类过程是采用最小距离分类器与最近邻分类组合的方式。

2.1 逆变异分类器算法实验

实验随机选取每人的5幅图像作为训练样本，另外5幅作为测试样本。则训练及测试样本集分别包含200个样本。将随机选择训练及测试样本集的实验过程重复10次，下表给出了逆变异算法的模式识别率。

表1中Aa样本数表示两分类器预分类结果不同的测试样本数。采用这些测试样本组成测试样本集2。As错分数表示两分类器的预分类结果虽然相同，但是该样本被错分的样本数。其中Aa样本数为4，表示在10次重复实验中，有平均4个测试样本的预分类结果不同。AS错分数为3.5，表示在平均196个（测试样本的总数是200个）预分类结果相同的测试样本中，有平均3.5个被错分。采用本文提出的逆遗传算法对测试样本集2中的4个测试样本再次进行分类识别，最后有平均1.8个样本被错分。因此，本文算法最终被错分的样本数是1.8+3.5个，算法的识别率是97.35%，这个识别率在ORL人脸库上是相当高的。说明本文的逆变异算法非常适用于人脸识别问题。

2.2 传统分类器方法的对比实验

实验分别随机选取每人的3、4、5幅图像作为训练样本，对应的取每人其余的7、6、5幅作为测试样本。则测试样本集分别有280、240、200个测试样本。将随机选择训练及测试样本集的实验过程重复10次。将本文算法与传统的最小距离分类器、最近邻分类器、文献的贝叶斯分类器及文献的预分类方法进行对比实验，实验结果如下。

从表2中可以看出，采用不同的训练及测试样本集时，本文算法的模式识别率明显高于传统分类器方法。其中文献的贝叶斯分类器的识别率仍明显低于本文算法。从表中还可以看出，本文的基于预分类的逆变异分类器算法，其识别率的方差明显小于传统分类器算法，说明本文算法比传统分类器算法稳定。由于在进行预分类后，本文算法采用的是逆变异分类器再进行识别，而文献采用的是最近邻分类器，因此，本文算法的识别率明显高于文献的识别率，说明本文算法在进行逆变异操作后，模式识别率明显提高。因此，可以认为对于高维小样本问题，本文提出的基于预分类的逆变异算法在整体性能上明显优于传统的分类器算法。

2.3 与其它遗传算法的对比试验

将本文算法与采用简单遗传算法（Simple genetical gorithm，SGA）、自适应遗传算法（Adaptive geneticalgorithm，AGA）、BP神经网络优化和文献的OGA算法进行对比实验。其中，各遗传算法的参数取值是，样本种群数n=100，交叉概率Pc=0.6，变异概率Pm=0.01，终止代数为500代，精度为0.001；在神经网络中，网络学习速率为0.001，隐层节点10个。结果如下表所示。

从表3中可以看出，其他的遗传算法都需要大量的迭代运算，但是本文的逆变异算法则无迭代过程，因此，本文算法的效率明显高于其他遗传算法。从算法识别率可以看出，本文算法明显高于SGA、AGA及BP神经网络，与OGA算法相当，但是本文算法没有需要优化选取的参数，而OGA算法则需要设置遗传算法的四个基本参数：交叉概率、变异概率、终止代数和精度。因此，可以看出本文算法具有明显的优势。

3 结束语

本文采用多分类器组合的方式，对测试样本进行预分类。在预分类的基础上，本文提出了逆变异分类器算法，并采用该算法对人脸图像进行了分类识别。实验结果说明本文的逆变异算法明显优于传统的分类器算法及遗传算法。这是由于本文算法在模式判别的过程中降低了变异基因的影响，因此，模式识别率高于传统的分类器方法及遗传算法。

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。