异常分类器

2024-05-25

异常分类器（精选7篇）

异常分类器篇1

1 概述

高速公路的建设情况可以反映一个国家和地区的交通发达程度、乃至经济发展的整体水平。保证高速公路的安全畅通对促进国民经济发展, 具有重要的现实意义。快速地应对高速公路交通异常事件可以有效降低对高速公路交通的影响, 从而提高高速公路运营效率。对高速公路异常事件的及时处理需要高效的异常事件检测技术, 从而对高速公路上出现的异常事件进行快速响应[1]。

与发达国家相比, 我国高速公路建设起步相对较晚, 计算机辅助监控系统还有一些需要完善的地方。随着近些年高速公路信息化建设速度的加快, 高速公路信息化监控系统的建设水平有所提高, 在理论研究和应用推广方面取得了一些成果。

梁新荣等人利用支持向量机 (Support Vector Machine, SVM) 进行高速公路交通事件检测, 通过分析交通事件对交通流参数的影响规律, 确定支持向量机的输入量, 利用分类算法进行异常事件的识别[2]。张存保等人对传统的基于固定式检测器的交通事件判别算法的缺陷进行了分析, 充分考虑了异常事件会明显降低高速路的车速这一规律, 提出一种基于浮动车数据的交通事件自动判别算法[3]。裴瑞平等人提出了一种基于小波变换和最小二乘支持向量机的交通事件自动检测算法, 利用小波变换提取特征数据, 使用最小二乘法支持向量机进行交通异常事件的分类[4]。陈斌等人研究了基于支持向量机的高速公路异常交通事件检测算法, 通过EAD2Simulations系统所建立的数据库进行仿真试验[5]。姜桂艳等人提出了基于支持向量机的高速公路交通事件自动检测算法, 依据所选取的交通参数设计了反映交通状态的特征向量, 并运用模拟数据进行了对比分析[6]。

国外学者和研究机构也对高速公路异常事件的检测进行了研究, 相关研究成果如下:

Y.Li和M.Mc Donald等人提出了一种基于浮动车的高速公路交通事件检测算法, 该算法基于平均行程时间和相邻两时段平均行程时间差双变量分析模型而设计[7]。Fang Yuan和Ruey Long Cheu等人将支持向量机技术应用到高速公路异常事件检测, 分别运用主干路网的模拟数据和加利福尼亚的I-880高速公路实测数据进行了实验测试[8]。

根据对以上研究的分析, 采用基于支持向量机的高速公路异常事件检测是一个研究热点。目前, 利用SVM进行高速公路异常事件检测主要有两种模式。第一种是选取若干与异常事件检测有关的参数, 将各参数在特定时段的采样数据作为向量的一个维度, 构成特征向量。第二种是选择若干异常事件检测参数, 为每个参数在不同时段中的采样数据单独构造特征向量, 从而组成多个特征向量。接下来, 为每个交通特征对应的识别结果进行有效融合, 从而得到高速公路异常事件检测结果。特征向量的选择是否有效对高速公路异常事件检测的准确率影响重大, 所使用的特征向量应该能够多角度、多层次地反映影响异常事件检测的诸多因素。

但是上述两种模式未能充分融合影响高速公路异常事件检测的各种因素, 检测结果还未能让人十分满意。因此, 本文将探索新方法, 重点研究如何有效融合各类影响异常事件检测的诸多因素, 利用多SVM分类器进行更为准确的高速公路异常事件检测。

2 多SVM分类器融合算法

支持向量机是Corinna Cortes和Vapnik等人于1995年首先提出的, 它在解决小样本、非线性及高维模式识别中表现出许多特有的优势, 并能够推广应用到函数拟合等其他机器学习问题中。

SVM分类器利用径向基核函数进行非线性变换, 将输入数据映射到特征空间, 该过程可以形式化描述如下:

3 基于多SVM分类器的高速公路异常事件检测算法

高速公路异常事件的发生过程可以细化为“事件发生”、“事件持续”和“事件消散”3个主要时间阶段, 在不同时间段以及高速公路的不同位置, 影响交通的各个参数均表现出不同的特性。因此, 本文对交通参数的选择充分考虑了影响高速公路异常事件检测的两大因素, 即时间信息和位置信息。这样能更为正确地描述异常事件发生时, 对不同时间段和不同地点交通流量的影响。需要特别说明的是, 考虑到在线检测无法等到事件消散后才报警, 本文只将时间信息的细化用于分类器的训练过程中。

在上一节提出的多SVM分类器融合算法的基础上, 高速公路异常事件检测问题就可以转换为多SVM分类问题。简言之, 该过程可以表示根据高速公路待检测区域的上游监测站的各种交通参数 (包括:车流量、行车速度、道路占用率、相邻监测站的车流量差值、速度差值、道路占用率差值等) , 将每组交通参数表示为特征向量, 使用经过训练的多个SVM进行分类, 将多SVM分类器融合后的分类结果作为判别异常事件的依据。使用一个SVM分类器只能反映交通参数的一部分变化情况, 无法进行异常事件的有效监测。因为, 本文通过对多SVM分类结果进行有效融合, 从而得到高速公路异常事件检测结果, 该方法的实现过程见图1。

本文所采用的多SVM分类器由6个独立的SVM分类器构成, 每个SVM分类器使用影响高速公路异常事件检测的一个特征进行计算。假设实验数据集中共有K个监测站 (K="1, 2, g, k, ) , 并为每个监测站采集了T个时间段 (T="1, 2, g, t, ) 的交通数据。SVM1-SVM6使用的特征向量如下:

SVM的训练问题可以转换为二次规划问题, 多SVM分类器的参数选择直接影响最终的分类结果。本文采用具有量子行为的粒子群优化算法 (Quantum behaved particle swarm optimization, 简称QPSO) [9]对多SVM分类器的参数进行训练。QPSO算法不仅调整参数少、容易实现, 且搜索效率高, 比其他进化算法的全局收敛能力强。本文提出的多SVM分类器性能的关键环节在于各分类器权重的确定, 为了更加准确地确定各分类器权重, 本文用QPSO算法对多SVM分类器中的6个权值参数同时进行快速寻优。各SVM分类器的权重值 (SVMi的权值表示为a i) 见表1。

如表1所示, 文本所提出的异常事件检测算法由6个SVM分类器和多SVM分类器融合模块构成。各个SVM分类器利用不同的高速公路交通参数作为特征向量, 经过分类后将结果统一送入多SVM分类器融合模块, 最终检测出异常事件。

4 实验结果及分析

本章中, 通过高速公路中的实际交通数据对上述算法进行性能评测。选择5个具有代表性的高速路段。下面以路段1为例进行实验数据说明, 路段1包括了各种几何线形变化、驶入和驶出匝道以及道路瓶颈。该路段全长4.2 km, 为双向4车道, 车道宽度为3.5 m。根据道路的具体情况, 将该路段分为5个子路段, 每个路段的平均长度为840 m。观测到的交通流量为7∶00~19∶59这一时段, 数据集中某一天检测到的数据见表2。

表2所示的测试数据包括6个监测点, 共有5个流量监测区域。为每个路段采集了80 d的交通流量信息, 其中60 d的数据作为训练集, 另外20 d的数据作为测试集。为了验证本文提出的多SVM融合算法的有效性, 首先对该算法进行评测。图2给出了分别采用各单独的SVM分类器以及融合后的多SVM分类器对本文收集的实验数据进行异常事件检测的结果。

为了进一步说明本文所提出的算法的有效性, 下面将本文提出的方法 (简称MSVM) 与其他相关方法进行性能对比。进行性能对比的方法包括: (1) SVM (只用一个SVM分类器) [8]; (2) 基于LS-SVM的方法 (简称LS-SVM) [4]。利用收集到的5个路段进行异常事件检测, 并采用检测率 (Detection Rate, 简称DR) 作为测度, 实验结果见图3。

综合上述实验结果可知, 本文提出的多SVM分类器融合算法可以有效地整合高速公路的各类交通参数, 与已有方法相比, 可以提高高速公路异常事件检测的准确性和可靠性, 弥补了仅使用单一交通参数进行异常事件检测的不足。

此外, 高速公路异常事件检测的实时性对于检测结果的有效性至关重要, 如果不能及时对异常事件进行报警, 异常事件的检测就失去了意义。为了提高检测的准确性, 本文使用了大量的训练数据进行训练, 并用具有量子行为的粒子群优化算法对多SVM分类器的参数进行训练。由于上述训练过程都是离线进行的, 并不会影响异常事件检测的实时性。

本文提出的基于多SVM分类器的高速公路异常事件检测算法综合考虑了影响高速公路异常事件检测的时间信息和位置信息, 将时间信息细化为“事件发生”、“事件持续”和“事件消散”3个主要时间段, 并充分利用上下游监测站的交通流量的动态变化情况进行异常事件检测。本文提出的算法能够显著提高异常事件检测的准确率, 是因为本文提出的6类交通参数能够揭示高速公路发生异常事件的规律。

从实验结果发现如下规律:交通流量平稳时, 交通流量呈现出相对平稳的变化态势;在异常事件发生的初期, 上游监测站的交通流量会下降, 占有率提高, 行车速度会下降, 下游监测站受其影响, 车流量会显著上升;在异常事件持续阶段, 上游监测站的车流量和行车速度会持续下降, 道路占有率会显著提高, 下游监测站的车流量和道路占有率持续降低;当异常事件处理完毕后, 上游监测站的车流速度提高, 道路占有率下降, 异常事件发生地下游检测站的车流量也随之提高, 行车速度和道路占有率会提升至异常事件发生之前的水平。

5 结论

本文提出了一种通过多SVM分类器对高速公路中的复杂交通参数有效融合, 进行异常事件检测的方法。利用概率方法将多SVM分类器分类结果进行融合, 将具有最大后验概率的异常事件作为检测结果。异常事件的检测使用“车流量”、“行车速度”、“道路占用率”、“相邻监测站的车流量差值”、“速度差值”以及“道路占用率差值”等6个交通参数。在今后的研究中, 将从以下几方面对本文工作进行更加深入的研究: (1) 进行异常事件检测时采用更多的交通参数, 使得高速公路异常事件的检测准确率进一步提高; (2) 进一步扩大实验数据集的规模, 使得实验结果更加客观、准确。

参考文献

[1]陈斌.高速公路意外事件影响下的车辆行为模型与事件检测研究[D].成都:西南交通大学, 2005.

[2]梁新荣, 刘智勇.基于支持向量机的高速公路事件检测[J].计算机工程与应用, 2006 (14) :213-218.

[3]张存保, 杨晓光, 严新平.基于浮动车的高速公路交通事件自动判别方法研究[J].武汉理工大学学报 (交通科学与工程版, 2006, 30 (6) :973-975.

[4]裴瑞平, 梁新荣, 刘智勇.基于小波变换和LS-SVM的事件检测算法[J].计算机工程与应用, 2007, 43 (1) :229-231.

[5]陈斌.基于支持向量机的高速公路意外事件检测模型[J].中国公路学报, 2006, 19 (6) :107-112.

[6]姜桂艳, 蔡志理, 冮龙晖, 等.基于支持向量机的高速公路交通事件自动检测算法研究[C]//第六届全球智能控制与自动化大会会议论文集, 大连:2006, 12 (10) :8769-8773.

[7]Li Y, Mcdonald M.Motorway incident detection using probe vehicles[J].Proceedings of the Institution of Civil Engineers, 2004, Transport (158) :11-15.

[8]Fang Yuan, RueyLong Cheu.Incident detection using support vector machines[J].Transportation Research, 2003, Part (11) :309-328.

[9]Omkar S N, Khandelwal Rahul, Ananth T V S.Quantum behaved Particle Swarm Optimization (QPSO) for multi-objective design optimization of composite structures[J].Expert Systems with Applications, 2009, 36 (8) :11312-11322.

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

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

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

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

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

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

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) 取得最优值, 遗传算法的主要步骤[7]如下:

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

2) 编码:对样本进行归一化处理, 本文采用了浮点编码法。

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

4) 个体选择:从当前代中选择两个个体, 其中第i个个体被选中的概率为,

在公式 (1) 中采用的是“轮盘赌法”, 适应度大的样本具有更多被选中的机会, 然后再对选中的样本进行交叉和变异。

5) 交叉:对于浮点编码可采用算术交叉、离散交叉。算术交叉[8]是指由两个个体的线性组合而产生出新的个体, 假设两个个体XA, XB之间进行算术交叉, 则交叉运算后所产生的两个新个体为:

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

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

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

1.1.2 逆变异过程

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

模式分类器是通过计算模式在特征空间中的距离来获得相似度结果的。对于种群PX1, X2, ..., Xu中任意2个个体Xi (xi1, xi2, ..., xil) 与Xj (xj1, xj2, ..., xjl) , 定义它们之间的距离为:

对于实数编码, 设L为决策变量的个数, 则两个个体之间的欧氏距离为:

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

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

从公式 (5) 中可以看出, 当参数α取为0.5时, 由父代XA、XB经过交叉后, 得到的子代是相同的, 而就是样本XA和XB的均值。因此, 当采用各类均值向量作为该类的代表时, 可以在一定程度上克服因基因交叉对基因相似性的影响。

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

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

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

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

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

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

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

公式 (8) 就是进行逆变异操作后, 计算两个个体di和dj基因相似度的公式。当di为父代个体, dj为子代个体时, 公式 (8) 就是进行逆变异后的最近邻分类器。当di为父代个体的均值, dj为子代个体时, 公式 (8) 就是进行逆变异后的最小距离分类器。

1.2 本文算法具体描述

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

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

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

(1) 特征提取:在两个特征子空间中, 分别对特征向量进行特征提取, 两个特征子空间可以采用Fisher及PCA特征子空间。

(2) 预分类:分别采用最小距离和最近邻分类器, 对不同特征子空间的特征向量进行分类识别。

, 其中表示将第i个测试样本判别为第k及第j类。

(3) 生成新的测试样本集:对预分类的结果, 按照下述公式将其划分到不同的样本集中, 并得到新的测试样本集, 对于测试样本

若k=j, 将加入到XS中,

否则, 将加入到Xd中。

, 经过上述处理后, 将预分类结果相同的样本加入到样本集XS, 预分类结果不同的样本加入Xd中, 则Xd就是新的测试样本集。

(4) 逆变异分类器:采用本文的逆变异分类器, 对新的测试样本集Xd进行分类识别, 具体方法是采用公式 (7) 计算变异基因, 然后在采用公式 (8) 计算测试样本与训练样本的距离, 并将该测试样本判别到与其最近的类别中。

(5) 正确率测试:将步骤 (4) 的分类结果与预分类结果XS一起进行正确率测试, 并将测试结果作为最终结果输出。

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

2 实验及分析

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

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

2.1 逆变异分类器算法实验

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

表1中Ad样本数表示两分类器预分类结果不同的测试样本数。采用这些测试样本组成测试样本集2。AS错分数表示两分类器的预分类结果虽然相同, 但是该样本被错分的样本数。其中Ad样本数为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次。将本文算法与传统的最小距离分类器、最近邻分类器、文献[9]的贝叶斯分类器及文献[6]的预分类方法进行对比实验, 实验结果如下。

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

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

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

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

3 结束语

异常分类器篇3

数据挖掘技术[1,2]是一门主要由统计学和人工智能组成的交叉学科。它的主要任务是从海量的数据集中提取隐藏的、有用的信息。目前, 数据挖掘技术已被广泛应用于电信、金融、网络安全、天气预报等领域[3]。随着信息技术的广泛应用, 数据在不断地以几何级数增长, 而且不少数据以数据流 (datastream) 的形式存在。如何处理这些数据流, 提取有价值信息已经成为了数据挖掘领域新的挑战。

数据流模型可以表示成, 其中t为时间戳并且单调递增, at为t时间到达的数据。数据流模型在以下几个方面不同于传统的数据模型:

1) 数据高速到达, 实时性要求高;

2) 数据的到达顺序无法控制;

3) 数据可能是无限多的, 数据流中的元素被处理后将被抛弃, 无法存档 (archive) 。

传统的数据挖掘技术要求数据全部保存在存储介质上, 因此不适用于数据流挖掘。由于数据流的无限性、实时性、连续性等特点, 数据流挖掘研究已经成为数据挖掘领域的研究热点。

在数据流挖掘过程中, 通常会在新到达的数据流中蕴含新的目标概念 (targetconcept) , 即概念漂移[4,5,6,7] (conceptdrift) 。这种随着时间而变化的目标概念给数据流的挖掘造成了极大的困难。为了解决这个问题由Wang等人[8]提出了一种利用加权的多个分类器挖掘概念漂移数据流的方法。该方法首先训练几个基础分类器 (比如C 4.5, RIPPER和贝叶斯等分类器) , 然后对分类器进行测试, 根据测试结果计算分类精度期望值, 依据精度期望值对各个分类器进行加权。Street等[9]提出了基于多分类器集成学习的概念漂移检测算法SEA。以上组合方法是目前比较流行的数据流挖掘算法。

SEA方法在更新集成分类器时总是把权值最低 (即:已经过时的分类器) 的单体分类器直接抛弃, 轻易地放弃了已经掌握的知识, 以后再遇到相同概念的时候需要重新训练学习, 导致算法效率不高。

如果集成分类器保留学习过的概念, 以后再遇到此概念时就不必重新训练, 节省训练时间。在概念重复频率高的情况下, 这种思想能够提高数据流分类算法的效率。

1概念重复出现的数据流分类模型和算法设计

1.1概念重复出现的数据流模型

数据流中蕴含的概念是随着时间而变化的。有一种数据流模型, 如图1所示, 它的最新到达的数据流中蕴含的概念是以前出现过的目标概念。

图1中, t为时间戳, 可以在时间轴上无限延伸。ai为t=i时到达的数据集, 可以为单个数据, 也可以为数据序列。如果在时间段宽度d内到达的数据集都属于同一个概念范畴, 则该概念的宽度为d。图1中, 时间段i<t<i+d内到达的数据集属于概 (1) 念范畴;时间段j<t<j+d内到达的数据集属于概念 (2) 范畴;时间段k<t<k+d内到达的数据集属于概念 (3) 范畴, 与时间段i<t<i+d内到达的数据集属于同一概念范畴。在概念 (1) 在时间段i<t<i+d第一次出现时, 集成分类器对其进行了学习, 如果在概念 (1) 出现时需要更新分类器, 这时把概念 (1) 的分类器抛弃了, 概念 (1) 第二次出现时就需要重新训练分类器, 造成了极大的资源浪费。

1.2算法设计

在以往的集成分类方法的基础上, 我们设计并实现了名为ECRRC的算法。首先采用ID 4算法作为基础分类算法, 利用集成分类器技术求出全局结果。一旦数据流中发生概念漂移, 集成分类器会自动更新, ECRRC把被抛弃的概念保存到外存中。在数据流中概念重复出现时, 算法读取已经学习了的概念用于数据流分类, 从而节省了重新训练的时间, 提高了执行效率。分类器更新过程如下:

e为新训练出来的单体分类器, En为集成分类器, En的容量是En能够装载的最大分类数量, w为En中单体分类器的权值 (w表示分类器概念与当前数据流蕴含的概念的相似程度) , 如图2。

算法给出集成分类器的更新过程。关于基础分类器的权值衰减过程, M ID 4算法[9]以及SEA算法已经有良好的表现了。针对概念重复出现的数据流, 我们在这里没有设定阈值用来删除基础分类器, 而是选择了权值w最小的删除, 保证每次只删除一个基础分类器, 尽量多保存目标概念。并将这个被集成分类器删除了的基础分类器保存到外存中去。

集成分类器中保存的是最新流行的概念, 对于旧的概念, 我们使用另外附加一定数量的基础分类器。这些基础分类器中的概念随机地从外存中调入到内存中。

同时维护一个能够描述集成分类器中附加分类器所占的比率的因子rate, 这个数值根据概念重复的频度成正比, 这代表着如果当前数据段中概念重复出现的情况比较严重, 那么就相应地增加附加分类器的比率。

有一种特殊的情况, 就是在提取概念到外存时, 我们以前已经提取过同样的概念了, 算法依然会将此概念保存到外存中。这样做的原因是:

首先, 存储一个概念不需要太大的系统资源, 一颗普通的二叉树只有几KB的大小。

其次, 由于我们后期在外存中提取概念是随机提取的, 对于同样的概念保存的次数越多, 提取此概念的概率也就越大, 也就是说数据流中隐含该概念的数据量大, 进而算法找到正确的基础分类器的几率也提高了。

在提取概念并保存到外存的过程中。我们提取的概念是一颗二叉树, 这颗树可以被还原到集成分类器中。这样不必存储数据流数据也能保存已经学习过的知识。首先求出树的先序序列, 再保存这个序列到外存, 以后提取的时候可以使用这个先序序列建立二叉树的二叉链表。

2实验

我们使用SEA数据集模拟概念漂移, 其结构为 (f0, f1, f2, f3, f4, f5, f6, f7, f8, f9, C}其中f是条件属性 (取值范围1～10) , C是决策属性 (例如, 当样本属性满足条件f1+f2<p时, 属于class1, 否则属于class2) 。产生10 000条样本, 其中包含8个概念, 有3个概念分周期地重复出现在数据流中。因此, 它可以被用来评价算法处理概念重复数据流的能力。

为了使用标准的SEA概念来衡量ECRRC算法和SEA算法, 使用了SEA数据集。数据块D=500, 分别在无噪音和含有5%噪音两种情况下进行实验。集成分类器含有6个基础分类器, 附加2个保存旧概念的基础分类器。

实验方案:在相同的数据集上测试算法, 在特定的数据段上提高概念变化的频度迫使集成分类器进行更新。这个数据段中会重复出现以前有可能被集成分类器抛弃的概念, 用以测试算法处理概念重复出现的数据流能力。

两个算法的实验结果对比如图3、图4所示。在无噪音情况下ECRRC算法与SEA的准确率基本相同。在数据段分别为100到150, 250到300阶段, 350到400阶段 (在这3个阶段数据流中发生较多的概念漂移, 并且概念重复出现的概率加大。ECRRC捕获到一些重复概念, 因而准确率明显优越于SEA算法。

在5%噪音情况下, ECRRC算法表现出了较好的抗噪性, 另外在150到250的位置数据流发生概念漂移的频率骤然升高导致准确率下降, 在这个阶段ECRRC捕获到了少量旧概念, 2种算法表现相差不大。在350到450的位置, 数据流发生概念漂移的频率变得更大, 概念重复出现的频率更高, 由于ECRRC捕获到了较多的旧概念, 所以准确率明显高于SEA。

3结论

本文提出了一种使用集成分类器方法提取并保存数据流中所出现过概念的方法。实验表明, 针对概念重复出现频度较高的数据流, 该算法有较好的适应性。

参考文献

[1]Han J, Kamber M.Data mining:concept and techniques.2ed.San Fransisco, CA.Higher Education Press, 2001:1—7

[2]Tan Pang ning, Sreinbach M, Kumar V.数据挖掘导论.范明, 范宏建, 译.北京:北京大学出版社, 2006

[3]王涛, 李周军, 颜跃进, 等.数据流挖掘分类技术综述.计算机研究与发展, 2007;44 (11) :1809—1815

[4]Widmer G, Kubat M.Learning in the presence of concept drift and hidden contexts.Machine Learning, 1996;23 (1) :69—101

[5]金激清, 钱卫宁, 周傲英.流数据分析与管理综述.软件学报, 2004;15 (8) :1172—1181

[6]史金成, 胡学刚.数据流挖掘研究.计算机技术与发展, 2007;17 (11) :11—14

[7]Domingos P, Hulten G.Mining high—speed data streams.Proc of ACM SIGKDD Inter Conference Knowledge Discovery in Databases (KDD’00) , 2000:71—80

[8]Wang H, Yin J, Pei J.Suppressing model over-fitting in mining con-cept-drifting data streams.SIGKDD’06.Philadelphia.[s.n.], 2006:736—741

基于复杂网络的分类器融合篇4

随着信息技术的发展,Internet上的信息越发丰富,成为名副其实的全球最大的分布式信息库。如何有效地管理、利用、挖掘该资源库已成为具有挑战性的研究课题。信息检索、数据挖掘等是解决这一问题的重要技术手段。其中,文本分类是信息检索和文本挖掘的重要基础,在自然语言处理与理解、信息组织与管理、内容信息过滤等领域都有着广泛的应用[1]。

文本分类方法可分为有监督、无监督和半监督3种。有监督指从给定类别的训练例中学习分类模型的过程;无监督指从事先未标注的训练例中学习分类模型的过程;半监督则指从部分被标注、部分未被标注的训练例中学习分类模型的过程。无论哪一种,分类的主要任务都是根据某给定文本的内容判定它的类别。本文的工作仅在有监督学习的框架内展开讨论,有监督的文本分类的方法有很多[1],如:贝叶斯、线性分类、决策树、k-NN、神经网络、支持向量机等。

有监督的文本分类包括以下几个主要步骤:(1)词表生成;(2)特征提取/抽取(feature selection/extraction);(3)文本表示(text representation);(4)分类器训练;(5)性能评价(evaluation)。其中,第2、3、4步是影响性能的关键步骤。要获得理想的性能,最理想的情况是:第2步提取/抽取最“优”的特征;第3步采用最“优”的表示方法;第4步训练最“优”的分类器。而要同时达到最“优”,显然是非常困难的[1],这就使得分类器在实际应用中的分类效果往往不尽如意。为了提高分类精度,有研究人员尝试组合多个分类器来进行文本分类[1,2]。分类器融合,亦称集成学习(ensemble learning),它的出发点是:由于不同的分类方法之间往往存在着互补性,因此,利用多个模型的差异性可以提高学习系统的泛化性能,从而降低识别错误率及增强识别系统的鲁棒性。

1 基于个体分类器输出的复杂网络的构造

分类问题属于概念学习的范畴。分类问题是集成学习的基本研究问题,简单来说就是把一系列实例根据某种规则进行分类,这实际上是要寻找某个函数y=f(x),使得对于一个给定的实例x,找出正确的分类。机器学习中的解决思路是通过某种学习方法在假设空间中找出一个足够好h的函数来近似f,这个近似函数h就叫做分类器[7]。

传统的机器学习方法是在一个由各种可能的函数构成的空间(称为“假设空间”)中寻找一个最接近实际分类函数f的分类器h[4]。单个分类器模型主要有决策树、人工神经网络、朴素贝叶斯分类器[4]等等。集成学习的思路是在对新的实例进行分类的时候,把若干个单个分类器集成起来,通过对多个分类器的分类结果进行某种组合来决定最终的分类[1,2,3,4],以取得比单个分类器更好的性能。如果把单个分类器比作一个决策者的话,集成学习的方法就相当于多个决策者共同进行一项决策。图表 1表示了分类器融合的基本思想。图表 1中的集成分类器包括了m个单一的分类器,对于同样的输入,m个分类器分别给出各自的输出(O1, O2, …, Om),然后这些输出通过整合以后得到集成分类器整体的输出结果作为最终分类。

本文方法的步骤如下:(1)训练个体分类器;(2)利用每个个体分类器对训练例进行预测;(3)构造复杂网络及训练融合器。

假设个体分类器训练完毕(由于个体分类器可以利用传统方法训练获得,此不赘述)。此后,利用个体分类器对训练例进行预测,对第i个样本而言,可得向量<Oi1, Oi2, …., Oim>,Oij表示第j个分类器对第i个样本的预测。将个体分类器在每个训练例上的输出表示为一决策表S=(U,A,V,f)。其中,U为样本的非空有限集,即论域;A=C∪D, C∩D为空,C为条件属性集(即个体分类器),D为决策属性集(即类别集); $V = \underset{a \in A}{\cup} V_{a}$ ,Va是a的值域(本文取Va={0, 1});f:U×A→V是一个信息函数,它为每个样本的每个属性赋予一个信息值,即:∀a∈A,x∈U,f(x,a)∈Va。

根据决策表S,按算法1为某一类别(不妨设为Di)的样本集构造复杂网络。算法1的基本思想是:将在同一个样本中共现的属性节点进行连接,两个节点间的边的权重代表这两个属性在样本集中的共现次数。另外,本文认为,任何一个节点都与自身共现。算法1中的w(x,y)表示节点x与y间的权重。

下面,以一个例子来说明复杂网络的建立。表1给出了一个示例决策表。表1中,(ai,xj)单元的值表示第i个个体分类器对第j个训练样本的预测值。本例中,1≤i≤4, 1≤j≤4。当算法1扫描到x1时,将在a1与a2、a1与a3、a2与a3之间建立连接,也将建立a1、a2、a3的自连接,同时这些连接的权重被置为1。以此方法,直到扫描完所有的样本,将得到如图1所示的两个网络。图1(a)是类别0的复杂网络,图1(b)是类别1的复杂网络。当新样本到达时,根据各个体分类器的输出,网络中不同的节点和边将被激活,依据激活情况,则可输出各个体分类器对新样本的类别判定的融合结果。下文加以讲述。

2 复杂网络分析及融合算法

2.1 网络分析方法

目前,复杂网络研究的内容主要包括[5]:网络的几何性质、网络的形成机制、网络演化的统计规律、网络上的模型性质、以及网络的结构稳定性、网络的演化动力学机制等问题。其中,在自然科学领域,网络研究的基本测度包括:度(degree)及其分布特征、,度的相关性、集聚程度及其分布特征、最短距离及其分布特征、介数(betweenness) 及其分布特征、连通集团的规模分布等。这些分析手段使我们可以了解节点和边的分布情况。进一步,根据这些先验分布,可计算给定的子图(由激活的节点和边形成)属于某父图的后验概率。本文即是应用特定的网络分析手段,计算新样本属于某一类别的后验概率。

2.2 网络分析算法

复杂网络建立相当于完成了融合器学习的过程。此后,网络可以用于判定新样本x的类别。分类的第一步,根据C中属性在新样本中的出现情况,激活不同类别的复杂网络中的节点和边。具体而言,若ak和al(k, l=1, …, |C|)在x中共现,则激活ak与al之间的边,ak的自连接边和al的自连接边。从而,一个样本就被表示成了有限条边的无序集合。第二步,计算后验概率。

本文基于贝叶斯定理[6]提出了一种基于复杂网络的后验概率计算方法。贝叶斯方法假设文本数据由一个参数模型产生,根据训练例,可使用“贝叶斯-优化”方法估计模型中的参数,以下设待估计的参数为 $\hat{θ}$ 。对于样本x,为了判定它的类别,首先要计算它属于Di的后验概率p(Dj|x; $\hat{θ}$ )(Dj为第j类,j=0, …, |D|);之后再根据相应的决策规则判定x的类别。p(Dj|x; $\hat{θ}$ )的计算公式为:

$p (D_{j} | x; \hat{θ}) = \frac{p (D_{j} | \hat{θ}) p (x | D_{j}; \hat{θ})}{p (x | \hat{θ})} 。$

上式中,尽管p(x| $\hat{θ}$ )的计算非常困难,但因为它对于p(Di|x; $\hat{θ}$ )都是相等的,因此,这一部分可忽略不计。p(Dj| $\hat{θ}$ )是类先验概率参数,其最大似然估计如下式:

$p (D_{j} | \hat{θ}) = \frac{\sum_{i = 1}^{| D_{s} |} p (D_{j} | x)}{| D_{s} |} 。$

其中,Ds为训练集,|Ds|为训练样本集大小。

p(x|Dj; $\hat{θ}$ )为类条件先验概率参数,这是本文方法的关键。本文按下式计算p(x|Dj; $\hat{θ}$ )。

$\begin{array}{l} p (x | D_{j}; \hat{θ}) = \prod_{i = 1}^{| E |} (w_{i} p (e_{i} | D_{j}, θ) + \\ (1 - w_{i}) (1 - p (e_{i} | D_{j}; θ)) 。 \end{array}$

上式中,E为各类别的复杂网络的边集(如:在图1中出现了9条边),wi=1表示边ei被激活,p(ei|Dj,θ)定义的计算如下:

$p (e_{i} | D_{j}, θ) = \frac{1 + \sum_{k = 1}^{| S |} w_{k i} Ρ (D_{j} | x_{k})}{2 + \sum_{k = 1}^{| S |} Ρ (D_{j} | x_{k})} 。$

上式中,S是训练样本集,p(Dj|xk)为1,若xk的类别是Dj,否则为0。

当新样本x属于各类别的后验概率得以计算后,则可取最大后验概率对应的那个类别进行输出。

3 算法示例及分析

3.1 算法示例

本文采用表1中的数据作为示例数据集,验证本文方法的正确性。以计算x1属于”0”类别(记为D0)的后验概率为例。

图1所示的复杂网络中,共有9条不同的边(设x, y是节点,记x<->y为它们之间的边),分别是:a1<->a1,a1<->a2,a1<-> a3,a1<->a4,a2<->a2,a2<->a3,a2<->a4,a3<->a3,a4<->a4。依次记上述9条边为:e1,e2,…,e9。x1激活了这9条边中的6条边,分别是:e1, e2, e3, e5, e6, e8。

为了计算x1属于D0的概率,首先要计算p(D0|),显然其值0.5;之后需要计算p(x1|D0; $\hat{θ}$ ),见下式。注:下式中,为了方便起见,省写了待估参数。

$\begin{array}{l} p (x_{1} | D_{0}; \hat{θ}) = p (e_{1} | D_{0}) p (e_{2} | D_{0}) ‚ \\ p (e_{3} | D_{0}) p (e_{5} | D_{0}) p (e_{6} | D_{0}^{}) p (e_{8} | D_{0}) ‚ \\ (1 - p (e_{4} | D_{0})) (1 - p (e_{7} | D_{0})) (1 - p (e_{9} | D_{0})) 。 \end{array}$

可见,需要计算p(ei|D0,θ) (i=1, …, 9)。根据上文给出的公式,先求p(e1|D0,θ),如下式:

$\begin{array}{l} p (e_{1} | D_{0}, θ) = \frac{1 + 1 \times 1 + 1 \times 1 + 0 \times 0 + 0 \times 0}{2 + 1 + 1 + 0 + 0} = \\ \frac{3}{4} 。 \end{array}$

其他p(ei|D0,θ)(i=2, 3, …, 9)的值不难依次求得:3/4,2/4,2/4,3/4,2/4,2/4,2/4,2/4。

从而,可得:

$p (D_{0} | x_{1}; \hat{θ}) = \frac{(1 / 2) \times (2 / 4)^{6} \times (3 / 4)^{3}}{p (x | \hat{θ})} 。$

同理,可计算x1属于D1的后验概率:

$p (D_{1} | x_{1}; \hat{θ}) = \frac{(1 / 2) \times (1 / 4)^{5} \times (2 / 4)^{4}}{p (x | \hat{θ})} 。$

显然,p(D0|x1; $\hat{θ}) > p (D_{1} | x_{1}$ ; $\hat{θ}$ ),因此判定x1的类别为“0”。按上述方法,我们还判定了x2,x3,x4的类别,都取得了正确的结果。上述计算示例说明,本文方法是正确可行的。

4 结束语

文本分类是数据挖掘领域长兴不衰的研究课题,具有更好效果的新颖的分类方法是永远的追求目标。本文作者的创新点为:将复杂网络的分析理论引入到分类器融合的设计、研究中,这是一种新的尝试。这种方法不单只考虑个体过滤器的输出,还考虑个体过滤器间的相互作用。

参考文献

[1] 苏金树, 张博锋, 徐昕. 基于机器学习的文本分类技术研究进展. 软件学报, 2006;17(9):1848—1859

[2] 李文斌, 刘椿年, 陈嶷瑛. 基于混合高斯模型的电子邮件多过滤器融合方法. 电子学报, 2006;34(2):247—251

[3] Dietterich T G. Ensemble learning. In:The Handbook of Brain Theory and Neural Networks, Second Edition, 2002

[4] Mitchell T M. Machine learning. McGraw Hill, 1997

[5] 周涛, 柏文洁, 汪秉宏, 等. 复杂网络研究综述. 物理, 2005;34(1):31—36

异常分类器篇5

关键词：纹理,分类,特征提取,支持向量机,查找表

0 引言

对于依赖高空间高分辨率复杂遥感图像对地面目标进行侦察的任务来说,要从大量的遥感图像中找出感兴趣的目标,如识别出各种农作物、树林、住房建筑等,一直是一项重要而繁琐的工作。在对这些图像识别中,建立一种对遥感图像数据库有效且快速的查询方法具有重要意义。而这种查询方法,又必须依赖于对图像很好的分类效果。在图像分类方面,一些工作人员近期已经做了一些研究,如从文献[1]可看出,单一特征在某些应用中不如多特征融合提取的图像信息更加完整。这说明在特征提取上,不同算法得到的图像信息具有一定的互补性,只有通过特征组合指导形成的分类器才能给出好的分类效果。

支持向量机SVM作为一种较新的也是最有效的统计学习方法,近年来成为模式识别与机器学习领域一个新的研究热点。文献[2]利用 SVM方法提取空间特征,对遥感影像进行图像分类,文献[3]基于SVM的图像分类,这些实例表明SVM可有效地应用于遥感图像的分类,并利用 SVM对高维输入向量具有高推广能力的优点进行遥感信息提取。就目前的研究来看,任何一种分类器在实际应用中都达不到百分之百的正确分类结果。这驱使我们考虑同时利用分类正确与错误的结果,以期达到更高的分类正确率。而查找表建立原则简单、效果直观、逻辑清晰,我们可以通过设计合适的策略,同时利用被正确分类的以及那些被错误分类的样本信息,形成一种索引关系,快速准确地对新样本进行归类。

1 原理概述

1.1 纹理特征提取算法

要对各种光学图像进行比较好的分类和查询,首先得提取图像的纹理特征。根据纹理的基本特征,目前已经出现了很多纹理特征描述方法,其中最重要的应用最广的是基于统计和基于结构的方法。本文应用了三种提取图像纹理特征的算法,分别是Gabor小波变换、GMRF和GLCM。

1.1.1 Gabor小波[4]

Gabor特征利用其Gabor小波自身具有的多尺度多方向分析能力,在周期性或方向性纹理上具有良好的分类效果。Gabor小波是将 Gabor 基函数经过移位、旋转和比例变换后得到的一组相似90°相移的Gabor函数。一个二维Gabor函数g(x,y)可以表示为:

$g (x, y) = (\frac{1}{2 π σ_{x} σ_{y}}) \exp [- \frac{1}{2} (\frac{x^{2}}{σ_{x}^{2}} + \frac{y^{2}}{σ_{y}^{2}}) + 2 π j W x] (1)$

其中,W为高斯函数的调制频率,g(x,y)是经过复数正弦函数调制的高斯函数。令g(x,y)为母小波,可通过下列函数膨胀、旋转g(x,y)获得一组自相似滤波器(称为Gabor小波),即:

gmn(x,y)=a-mg(x′,y′) a>1 m,n∈Z (2)

给定一幅图像I(x,y),则它的离散Gabor小波变换定义为:

$W_{m n} (x, y) = \sum_{s} \sum_{t} Ι (x - x_{1}, y - y_{1}) g_{m n} * (x_{1}, y_{1}) (3)$

其中,*表示复数共轭,它假设局部纹理区域在空间上是同性质的。x1、y1是滤波器模板大小的变量。

利用系数幅度序列确定纹理的主方向,在不同方向和尺度上计算变换后的系数幅度序列,这些系数幅度值在不同方向和尺度上表征了图像的能量,即:

$E_{m n} = \sum_{x} \sum_{y} | W_{m n} (x, y) | m, n = 1, 2, \dots (4)$

求出能量的均值μmn和方差σmn就可以得到一组特征向量,用来描述图像的纹理特征。

$μ_{m n} = \frac{E_{m n}}{Μ \times Ν}$

$σ_{m n} = \frac{\sqrt{\sum_{x} \sum_{y} (| W_{m n} (x, y) | - μ_{m n})}}{Μ \times Ν} (5)$

Gabor算法纹理特征提取具体编程方法如下:构造滤波器大小p×q,选取0°方向为主方向并将其转化为弧度制进行后续计算,本文滤波器构造函数为:

$g_{m n} * (x_{1}, y_{1}) = \frac{1}{50 π m^{2}} \exp (- \frac{4 x^{2} + y^{2}}{100}) * (\cos (x) + j \sin (y)) (6)$

给定一幅图像I(x,y),选择3,0°作为滤波器尺度和方向的大小,将该图像和滤波器函数做卷积。用程序控制实现滤波器在图像上以步长3滑动并对每一子块进行滤波提取有效信息。卷积结果即表征了该图像的能量,如公式(4),再进一步利用MATLAB 编程语言应用原理式(5)对图像求均值和方差的编程方法,获得图像在Gabor滤波器下的纹理特征向量,通过for循环编程将所有特征向量存进一个n×2矩阵中,n为样本个数。

1.1.2 高斯马尔柯夫随机场(GMRF)[5]

高斯马尔柯夫随机场模型最初是在二十世纪六十年代后半期LeonardE.Baum和其他一些作者在一系列的统计学论文中描述的。一幅图像中某像素点所属的类别和它周围的领域像素的类别有一定的相关性,这种相关性即为马尔柯夫相关性。一幅图像可以视为二维的随机过程,可以用条件概率来描述影像数据分布,MRF的假设前提是影像中每一个像元的像元值仅仅依赖于其邻域中像元的像元值。一个马尔柯夫随机场通常用如下的局部条件概率密度(PDF)来描述:

N(m,n)是中心像素的邻域像素点,如果PDF服从高斯分布,就称MRF为GMRF。用邻域信息来估计像素点灰度值的预测公式可以表示为:

$f (m, n) = \sum_{(t, s) \in Ν} θ (t, s) f (m - t, n - s) + e (m, n) (8)$

$e (m, n) ~ Ν (0, \sum) \sum = [\begin{matrix} σ^{2} & 0 \\ 0 & σ^{2} \end{matrix}] (9)$

公式(9)中邻域坐标为:

θ(t,s)为每个邻域像素点贡献于中心像素点灰度值的权值,e(m,n)为均值为零,方差为σ2的高斯噪声序列。

本文采用最小二乘估计方法LSE方法估计高斯马尔柯夫随机场模型参数,构成了中心像素点6维特征矢量。

GMRF算法提取特征具体编程方法为:用GMRF对图像进行二阶参数估计,设参数估计矩阵为G,图像中任一3×3的窗口为W,即图像采样模板的尺寸范围。因为对角线像素点的权值基本相同,可加以弱化,只取4个非对称的方向对应的四维参数向量{θ(t,s),(t,s)∈N},则窗口的中心像素点坐标为cr,核心编程为:

设图像的灰度矩阵为L,则用程序可实现3×3的窗口W在矩阵L内自动循环,以实现中心像素位置的变换,求得以矩阵L内除最外层行和列以外所有像素点为中心的参数估计矩阵G,因一个窗口求得的矩阵G大小为1×4,则循环中心像素点后可得G大小为:((length(L)-1)×(length(L)-1)×4),length表示长度。同样,对每个3×3的窗口求一次方差,则可得到方差矩阵σ,其大小为:(length(L)-1)×(length(L)-1)。

其中X为矩阵L除去最外层行和列后的矩阵,即中心像素点循环过的区域,则θ即为θ(t,s)。将θ和σ合并可得大小为(length(L)-1)×(length(L)-1)×5的矩阵,再加矩阵X中所有像素点灰度值的均值,得GMRF的六个特征。

1.1.3 GLCM灰度共生矩阵[6]

一幅图像的灰度共生矩阵能反映出图像灰度关于方向、相邻间隔、变化幅度的综合信息,它是分析图像的局部模式和它们排列规则的基础。1973年Haralick从纯数学的角度,研究了图像纹理中灰度级的空间依赖关系,提出灰度共生矩阵的纹理描述方法,其实质是从图像中灰度为i的像素(其位置为(x,y))出发,统计与其距离为d灰度为j的像素(x+Dx,y+Dy)同时出现的次数p(i,j,d,θ),数学表达式为:

式中:x,y=0,1,2,…,N-1是图像中的像素坐标;i,j=0,1,2,…,L-1 是灰度级;Dx,Dy是位置偏移量;d为生成灰度共生矩阵的步长;θ生成方向,可以取0°,45°,90°,135°四个方向,从而生成不同方向的共生矩阵。要使其特征值不受区域范围的影响,还需对此灰度共生矩阵进行归一化处理:

$\overset{\land}{p} (i, j) = \frac{p (i, j)}{\sum_{i = 0}^{L - 1} \sum_{i = 0}^{L - 1} Ρ (i, j)} (13)$

为了能更直观地以共生矩阵描述纹理状况,本文使用了从共生矩阵导出的一些最常用的反映矩阵状况的特征提取参数来提取图像的特征,包含能量ASM、熵ENT、对比度CON、逆差分矩IDM,计算式分别为:

这四个特征之间不相关,可以有效地描述光学或遥感图像的纹理特征,便于计算又具有较好的鉴别能力。

由于要处理的原始图像灰度级比较大,从计算时间和纹理可分性上对其灰度级压缩至9级,考虑到参数的旋转不变性,选取4个方向上的均值作为纹理特征参数,步长d为1。由灰度共生矩阵的的定义进而求出原始图像的灰度共生矩阵,并依据公式(13)进行归一化处理,计算出灰度共生矩阵下的4个纹理特征,作为分类器的输入。

具体纹理特征提取编程方法如下:首先由(12)式计算图像的灰度共生矩阵,从x和y方向统计次数,核心编程为:

然后应用原理式(13)对上步所得到的共生矩阵进行归一化并通过公式(14)计算四个纹理特征值。

1.2 SVM支持向量机[7]

支持向量机是Cortes和Vapnik于1995年首先提出的,它在解决小样本非线性及高维模式识别中表现出许多特有的优势,其分类的查全率和查准率几乎超过了现有的所有方法,具有很好的泛化能力及其它机器学习方法不可比拟的优势。

SVM的原理是用分离超平面作为分离训练数据的线性函数,解决非线性分类问题。SVM求取最优分类面的优化函数(极大化泛函)定义如下:

$Q (a) = \sum_{i = 1}^{n} a_{i} - \frac{1}{2} \sum_{i, j = 1}^{n} a_{i} a_{j} y_{i} y_{j} (x_{i} \cdot x_{j}) (15)$

式中,x为样本,n为样本个数,y为类别编号,ai(= 1,2,…,n)是函数优化时的Lagrange系数,对应的判别函数为:

$D (x) = sgn (\sum_{i = 1}^{n} a_{i}^{*} y_{i} (x \cdot x_{i}) + w_{o}^{*}) (16)$

目前有以下两种多类SVM分类器:(1) 一对一:构造所有可能的2类SVM分类器,每个分类器的训练数据集都只取相应的两类。(2) 一对多:对于k类问题,构造k个2类SVM分类器,每个类对应其中的一个,使第i个2类SVM分类器所构造的分类超平面,把第i类与其它的i-1类分割开。测试时,对测试数据分别计算对应于各个类分类器的决策函数值并选择最大的函数值所对应的类别作为测试数据的所属类别。本文选用了一对多的SVM分类器,将以上三种算法提取的纹理特征作为分类器的入口完成纹理图像的分类。

1.3 查找表[1]

本文提出了基于三维 LUT 结构的光学图像数据纹理分类编码的方案:首先运用SVM对不同算法下的训练样本图像数据进行分类得到每幅图像在各种算法下的分类类别号,将各种可能分类类别号组合进行编码,编码结果即作为测试样本数据分类结果的纹理查找表。在实际进行分类阶段,对测试图像提取Gabor、GMRF和GLCM三种纹理特征,输入训练好的分类器,根据三种分类器给出的类型响应,结合查找表,进行查表操作。本文研究的数据量不是很大,不需要考虑时间和空间问题,直接列出了查找表进行平均查准率的统计,具有简易直观的特点。

2 实验结果与分析

实验环境是MATLAB语言编程环境,使用计算机处理器是Pentium(R) Dual-Core CPU E5300,处理速度2.60GHz,内存为2G,对于原始图像特征的提取运行速度还比较快,原始数据来源于brodatz光学纹理图像集。

MATLAB能将数值分析、矩阵计算、科学数据可视化等诸多强大功能集成在一个易于使用的视窗环境中,功能强大,在图像的读写、转换及计算等多方面都具有广泛的应用,为多种类型图像的处理提供了极为方便的编程环境。遥感图像由于分析处理的需求不同于常规光学图像,传感器类型,成像角度,分辨率等诸多因素的的影响导致目标散射特性与光学存在较大差异。本文选取的brodatzs光学纹理图像集中的图像,它是研究面目标图像分类识别上目前公用的样本库,在这种数据库上的实验结果更具可比性。

在选择底层特征基础上,采用基于支持向量机组的方法从图像底层视觉特征实现多类目标分类,将一幅图像归于一类或几类图像,本实验算法流程如下:(1) 从光学纹理图像数据库中选出要研究的具有代表性的三类纹理图像,进行预处理;(2) 对样本的图像特征进行特征选择,选择三种算法对于图像特征提取的最优参数选择方案;(3) 对3类图像构造1个SVM三类分类器,通过选择底层特征训练样本集来构造分类器,对测试样本测试求平均查准率;(4) 设置核函数参量,利用SVM分类器对输入图像进行分类,并列查找表。

两组实验如下,每组每类均选择该类其中十张数据图像作为训练集样本:第一组实验由米粒、毛发、石头三类不规则纹理图像组成,共410张。其中米粒的数量为160,主要包含图1所示两种类型;毛发共100张,主要有图2所示三种类型;而石头有150张,如图3所示。

第二组由木纹(图4),针织物(图5)和砖(图6)三种纹理规则的三类图像组成,共440张图片,其中木纹和砖的测试集数量均为160;针织物测试集数量为120。这三类图像均具有规则的纹理,木纹主要有着90°方向的线条和不同的尺度。

针织物各种方向线条都有,且具有对称重复的纹理,而砖则具有横竖方向的线条纹理。在针织物中,虽然类别一样,但是各种类型针织物又具有很大的差别,本组实验中主要有如图5所示的六种类型的针织物。

砖块中图像除了尺度上的不同还有材料的不同,主要有如图6所示几种。

两组每类十个训练样本分类生成的查找表如表1和表2所示。

表1表示对训练集出现的组合情况的一种编码,是基于训练集得到的,表示当测试集中如果一幅图像出现与表中对应类的任意编码时则可认为该图像属于该类。

两组测试样本的分类平均查准率列成柱状图如图7和图8所示。

在第一组实验中,选择的是不规则杂乱纹理图像的比较分类,这三类图像在Gabor、GMRF、GLCM三种特征提取算法下的纹理特征分类组合中得到了比较好的分类效果:对于同一类,包含的种类不多,彼此的差异不是很大;对于不同类,毛发与另外两类砖和石头纹理相差较大,试验结果表明所运用的方法能够很好地将它与米粒和石头区别出来;而对于米粒和石头,这两类虽然属不同类别,虽尺度上相差较大,但纹理的杂乱又有些类似,故容易将两者混淆错分,引起石头类分类平均查准率不是很高。对比中发现,在GLCM单一特征下,各类平均查准率和多特征组合的相差比较大,这是因为对于单特征,三类的分类类别号必须分别为1、2、3,如果每类的测试样本分类类别号不是该类本应该出现的类别号,则认为该图像被错分,因此可验证不同的特征提取算法对不同的样本信息具有的识别能力不一样。

第二批实验中三类主要是规律的纹理图像,木纹主要具有90°方向光滑的纹理,针织物具有多种方向上的对称纹理,砖则有0°和90°方向的纹理,三类之间还具有尺度或材料上的差异。而每一类之间,所包含的不同类型数比前一组试验的要多,其中针织物类就有六种。这一组实验更加丰富,分类效果也比较好,说明在这种方案下SVM支持向量机构造的分类器有很好的泛化能力,能够将这三种光学纹理图像区分开来。

比较各组图像的纹理和分类结果,还可以说明方向、尺度对分类效果具有一定的影响作用。而在实际的遥感图像处理场景中,大部分是面目标,方向不定,可以通过取多个方向求平均值或者根据对称性等方法来弱化方向对图像纹理特征提取的影响,以达到更好的分类效果。实验还说明单一特征对于光学纹理图像的分类在一定条件和目标数据上不一定都比多特征组合的分类效果更差,但是多特征组合建立查找表的方法对于错类的判别应该具有很好的识别效果。试验中发现当训练集样本个数发生很小的改变时,测试精度也会有很大的改变,如果增加训练集个数,将会得到更高的测试精度。

实验时,SVM分类器构造参数以及训练集样本数的不同都能影响到查准率的改变。如何针对某一具体应用自动寻找合适的分类器参数以及训练样本,并将其推广到遥感图像中,则是下一步要面对的重要问题。

3 结语

在图像分类技术中,特征的提取和分类器的设计是两个重要的环节。本文提出的利用多特征提取图像纹理并构造查找表,以修正SVM的分类结果的方法,取得了比较好的纹理图像分类效果。在实际应用中,往往是对大规模数据进行测试,要对大范围的数据进行训练则比较难以执行,训练的数据量太小,会影响分类的准确性,这就要求不仅要选择适当量的数据集,还应选择合适的特征提取算法及分类器。实验由于所用技术本身的局限性以及实验并非基于海量的数据进行训练等因素,避免不了有些图像被错分到其他类。在高分辨率影像中,纹理特征非常复杂,如果采用简单的线性分类模型不一定完全能够将特征空间中的各个类别有效地区分开来,所以必须采用非线性的复杂映射模型来建立分类判别函数。利用SVM方法通过非线性决策函数进行训练分类,不需要大量的样本就可以得到满意的分类效果,分类错误率较低。特征提取算法的丰富、快速算法的实现、分类器设计的优化无疑都将进一步提升方案的分类性能。同时也可以进一步推广到遥感图像中,验证是否可以提高遥感图像的分类正确率。

参考文献

[1]张斌,高鑫.一种基于Gabor滤波器组和LBP的多特征联合SAR纹理图像分类方法[J].科学技术与工程,2010,10(17).

[2]骆剑承,周成虎,梁怡,等.支撑向量机及其遥感影像空间特征提取和分类的应用研究[J].遥感学报,2002,6(1).

[3]胡斌斌,姚明海.基于SVM的图像分类[J].微计算机信息,2010(1).

[4]Dengsheng Zhang,Aylwin Wong,Maria Indrawan.Indrawan Content-based Image Retrieval Using Gabor Texture Features[J].IEEE Trams-actions DAMI,2000:13-15.

[5]明冬萍,骆剑承,沈占锋.基于GMRF-SVM的高分辨率遥感影像目标区域划分方法[J].测绘科学,2009(2).

[6]李莉,木拉提.哈米提,艾克热木.阿西木,等.基于灰度共生矩阵的新疆地方性肝包虫CT图像特征提取方法[J].科技导报,2010,28(16).

浅谈多分类器动态集成技术篇6

关键词：分类,分类器,动态集成

0 引言

分类技术是数据挖掘、机器学习及模式识别中一个重要的研究领域, 已在生物认证、手写体识别和文字识别、医疗诊断、图像识别、网络安全入侵检测等众多领域得到广泛应用。分类的准确性是衡量分类器性能的最重要指标之一, 集成分类器的目的在于获得高性能的分类结果。分类器集成主要是通过对多个单分类器进行组合来提高分类性能。尽管传统的集成分类技术已经应用到很多领域, 但随着科技的发展, 人们对应用结果有了更高的要求。这就意味着人们希望通过对传统的静态集成分类技术的改进, 得到满足应用领域深层次要求的高性能的集成算法。于是, 多分类器动态集成技术应运而生, 研究分类器集成技术以提高集成分类的性能指标, 已成为众多领域的研究热点。

1 多分类器集成

1.1 背景

分类器集成利用单分类器的互补功能, 获得比单个分类器更好的分类性能。按照是否针对待分类样本的具体特征来自适应地选取分类器, 得到静态集成 (Static Ensemble) 和动态集成 (Dynamic Ensemble) 两种多分类器集成方法。多分类器静态集成方法在训练过程中就将最终识别模型的分类器权重和数目都确定下来, 就这意味着在分类预测的过程中所有待分类样本均使用相同的识别模型。和静态集成方法相比较, 分类器动态集成方法在预测过程中会根据待分类样本的具体特征来自适应地选取适合的分类器进行集成, 这种特性说明动态集成具有更好的针对性和灵活性。另外, 分类器动态集成受抽取样本的影响小于静态集成, 可以显著提高分类系统的泛化能力, 进而有效地保证了分类的精度。

1.2 多分类器集成的框架

多分类器集成系统虽然可以有效提高分类的精度, 但是构造多分类器系统确是一个复杂的事情。由于目前对于多分类器集成技术的理论分析还不尽完善, 在应用的过程中主要依赖于学者们的实践经验。通常来说, 多分类器集成问题包含分类器集合的构造和组合方法两大部分。分类器集合构造部分用于生成多个分类器, 组合方法部分则是通过某种方法根据单个分类器的预测情况形成最终的判决, 其框架如图所示[1]。

在分类器集成系统中, 组成识别模型的单个分类器的输出形式要受到所使用的集成方法的影响。一般来说, 单个分类器有决策级输出、排序级输出和度量级输出三种主要的输出形式。通常而言, 集成的信息量和单分类器的输出等级有关。单分类器的输出级别越高, 所集成的信息就越丰富, 理论上可以获得的分类结果就越好。单分类器的三种输出形式如下:

(1) 决策级输出:没有其他附加的信息, 输出结果仅用于单纯的分类决策, 如身份识别后输出接受和拒绝两种结果;

(2) 排序级输出:通常用于目标类别数目众多的情况, 且输出的类别按可能性由大到小进行排序;

(3) 度量级输出:输出的结果为概率、信度、距离等度量值。

1.3 单分类器的设计

在单分类器的设计中, 一些方法考虑显示地实现分类器的多样性, 另一些方法则是隐含地实现了分类器的多样性。将已知的单分类器设计方法归纳如下:

(1) 在同一个训练集中生成一组不同类型的单分类器[2]。比如使用决策树、神经网络、贝叶斯分类算法训练单分类器, 将这些类型不同的单分类器作为集成所用的成员分类器。这组分类器在分类的侧重点和效果上存在差别, 并且所得分类结果的输出表示方法也不相同, 因此在使用这些单分类器集成分类结果的时候需要进行调整。

(2) 从初始的训练样本中抽取得到不同的训练集, 训练多个类型相同的单分类器[3,4]。这种方法通过可重复的随机抽样, 根据样本分类的难易程度分别赋予不同的权重得到多个训练集, 从而训练出一组具有多样性的单分类器。

(3) 根据样本的属性特征划分不同的训练样本子集生成多个单分类器, 实现分类器的多样性[5]。将一个大的特征向量空间划分为若干较小的特征空间, 分别构建一个单分类器, 再将这些单分类器集成到一起。这种方法比在整个特征空间中训练一个分类器获得更高的时间、空间效率。

(4) 通过调整训练样本的标记属性得到不同的训练集, 分别训练得到单分类器[6]。这种方法不仅改变了训练样本的标记属性, 同时也增加了训练样本标记属性的噪声, 从而实现分类器之间的多样性。

(5) 合并类别标号。对于类别数目较大的训练集, 随机将多个类别的样本划为两个子集, 并将同一子集中的训练样本归为一类。对于合并后的两类训练集用拟合算法训练单分类器。这种方法通过多次重复的随机类别合并得到成员分类器。

1.4 单分类器的集成方式

在训练得到一组单分类器之后, 即可进行单分类器的输出集成, 以获得待分类样本的目标类别。单分类器的集成分为全部集成和部分集成两种类别:

(1) 直接进行集成, 即是集成全部单分类器。如果通过训练集生成的单分类器分类精度和相互之间的多样性较高, 则可以直接采取某种集成方法来融合各个单分类器的输出结果。

(2) 进行选择性集成。许多集成方法都选择使用大量单分类以得到较高的分类性能, 但是这种做法会带来一些问题, 例如增加计算和存储的开销;随着单分类器规模的增加, 难以保证分类器之间的差异度等等。有研究证明只选择一部分适合的单分类器同样可以取得集成所有分类器的分类性能, 甚至得到更好的分类效果。这类研究方法的主要思想是首先生成一组初始单分类器序列, 然后根据一定的准则从中选择合适的单分类器进行集成。

2 多分类器动态集成技术

2.1 动态集成技术的原理

动态集成的原理是利用不同的分类模型的错误分布信息来指导分类器的集成过程, 即是对于给定的一个待分类样本, 尽可能地选择那些能够将其正确分类的分类器进行分类。其原理为不同类型的分类器具有不同的错误分布, 而对于同种类型的分类器来说, 错误分布往往集中于某一特定的区域中。唐春生和金以慧[7]在研究中给出了动态集成技术的4个基本出发点:

(1) 在样本空间中, 不同的样本处于不同的区域, 并且具有不同的特征;

(2) 针对不同的样本, 各个分类器的分类效果是有差别的;

(3) 在样本空间的不同区域, 同一个分类器的分类性能会有所变化;

(4) 分类器对最终判决具有一定的支持作用, 且分类器输出的不同待测类别与实际类别之间存在一定的相似性。

根据以上内容总结得出分类器动态集成的思想:分析对于不同待分类样本所在区域上的各个单分类器的性能, 使其自适应地选择一组分类器, 最后利用某些特定的组合方法集成判决分类结果。分类器动态集成方法考虑了各个单分类器的特性和待分类样本的自身特征, 具有比静态集成方法更好的针对性和灵活性。通常来说, 动态集成方法能够获得比静态集成方法更好的分类效果。

2.2 多分类器动态集成的框架和方法

如图2所示为多分类器集成的框架的三个主要部分:

(1) 在训练集TS中训练生成一组单分类C;

(2) 使用训练集TS或测试集VS来生成能力区域Ro C (Region ofCompetence) ;

(3) 得到各个单分类器在能力区域内的性能, 这一过程需要根据待分类样本Xt的自身特征来确定。随后自适应地选择部分分类器或者指定分类器权重用于最终的动态集成分类。

要实现分类器动态集成, 关键在于如何构建能力区域和选择何种集成方法[8]。能力区域的构建需要选择出一组能够反映单分类器预测性能的样本集, 单分类器在样本中训练得到的分类器必须具备良好的分类效果。

总结一下目前流行的能力区域构建方法:

(1) 基于KNN的方法。该方法的核心思想是假如一个样本在特征空间里的k个最相邻的大多数样本都属于某一个类别, 则该样本也被判为这个类别, 并具有这个类别上样本的特性。KNN方法经常使用欧几里德距离、曼哈顿距离等来求解, 在确定分类决策上只依据最邻近的一个或者几个样本的类别来判决待分样本所属的类别, 如DCS-LA (Hard Selection) 方法, DCS-LA (Soft Selection) 方法, KNORA-E方法等。

(2) 基于不同数据集的方法。该方法是通过利用一定的技术得到不同的能力区域, 用于构建单分类器, 如AO-DCS算法等。

(3) 基于聚类的方法。该方法采用聚类算法产生规定数目的训练样本集, 在分类阶段通过计算待分类样本和样本集聚类中心的距离得到距离最近的一组训练样本进行分类。如CS (Clustering and Selection) 方法, M3CS方法等。

集成方法的选择也是分类器动态集成中的重要环节之一。流行的集成方式有:

(1) 动态选择方法。该方法的思想是通过对待分类样本的特征分析从单分类器序列中选择部分性能优良的单分类器实现集成分类。

(2) 动态投票方法。该方法的思想是在分类迭代过程中根据待分类样本的特征为各个单分类器动态分配权重, 然后执行加权集成分类。

(3) 结合动态选择和动态投票的混合集成方法。该方法集合了前两种方法的优势, 先根据待分类样本特征选择单分类器序列, 再为其动态分配权重, 最后执行集成判决。

3 多分类器动态集成技术的不足

和静态集成分类方法相比, 分类器动态集成方法在预测时可以动态地、实时地组合单分类器或者为其分配权重, 获得更好地分类性能。但是动态集成本身存在一些缺点, 在应用过程中需要注意。比如, 动态集成过程中需要调用其他方法, 如特征选择、聚类分析、KNN方法等;由于待分类样本和训练集分布的差异引起分类性能显著下降;对于不同的待分类样本进行分类器序列的优选, 造成算法时间复杂度的增加;还有部分动态集成方法, 为了追求优良的局部性能, 需要一些特定的训练集, 当训练集规模不足的情况下就会影响分类性能。

4 结束语

为了在各个应用领域中更好地满足人们对分类性能的需求, 由于分类器动态集成技术更加灵活、更具针对性, 并且能够取得更好的分类效果, 因此成为了机器学习和数据挖掘等领域的一个研究热点, 分析和研究分类器动态集成技术具有较高的理论价值和应用价值。本文介绍了分类器动态集成技术的原理、框架和方法, 总结了该技术在应用中存在的一些不足之处, 为后继的应用研究提供了理论参考。

参考文献

[1]Jiawei Han, Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社, 2004.

[2]W.B.Langdon, S.J.Barrett, B.F.Buxton.Combining decision trees and neural networks for drug discovery[C].Genetic Programming Proceedings of the 5th European Conference, Euro GP 2002, Kinsale, Ircland, 2002, 60-70.

[3]Y.Freund, R.E.Schapire.Experiments with a new boosting algorithm[C].Proceedings of the 13th International Conference on Machine Learning, Morgan Kaufmann, 1996, 148-156.

[4]Loris Nanni, Alessandra Lumini.Fuzzy Bagging:A novel ensemble of classifiers[J].Pattern Recognition, 2006 (39) :488-490.

[5]Yong Seog Kima, W.Nick Streetb, Filippo Mencaer.Optimal ensemble construction viameta-evolutionary ensembles[J].Expert Systems with Applications, 2006 (30) :705-714.

[6]Gonzalo Martinez-Munoz, Alberto Suarez.Switching class labels to generate classification ensembles[J].Pattern Recognition, 2005, (38) :1482-1494.

[7]唐春生, 金以慧.基于全信息矩阵的多分类器集成方法[J].软件学报, 2003 (6) :1103-1109.

异常分类器篇7

车载多障碍物分类一直是智能交通和模式识别领域的一个重要研究课题,是智能车辆周边环境感知技术领域中的重要组成部分。近几年,在国内外ITS以及IV研究领域中,关于车载多障碍物的识别研究,提出了许多算法和实施手段。沈志熙等人提出一种基于Boosting集成学习的二叉树支持向量机( BBT-SVM) ,根据城区交通环境中各类障碍物出现概率、模式间的类间差异,设计基于Boosting的智能车辆障碍物识别的SVM树型结构。张秋豪等人应用BP神经网络理论进行障碍物的模式识别,构造一种基于BP神经网络分类器。本文研究一种具有通用性的车载障碍物分类方法,基于概率模型的朴素贝叶斯分类器对车载多障碍物进行分类。并根据理论描述使用MATLAB环境构建了一个朴素贝叶斯文本分类器,以概率的方式对障碍物进行分类。

1 障碍物分类处理流程

在本文中利用朴素贝叶斯分类器对车载多障碍物进行分类。朴素贝叶斯( Naive Bayesian Classifier,NBC) 分类器是基于独立假设的,假设各个属性是条件独立的,互不影响、互不依赖。在车载多障碍物分类使用该分类器有利于选取互不相关的特征。图1 为朴素贝叶斯分类器的流程图。

根据流程图所示,朴素贝叶斯分类器分为三个阶段: ①准备工作阶段: 朴素贝叶斯分类器首先是训练样本的选取和样本特征选取,样本的特征属性决定分类器的质量; ②分类器训练阶段: 计算每个类别在训练样本中出现的频率及每个特征属性划分对每个类别的条件概率估计,将数据记录; ③应用阶段:使用分类器对待分类项进行分类。

2 特征提取

基于贝叶斯进行障碍物分类,必须先确定障碍物的特征,特征的选取很重要,它是识别障碍物的依据。本文选取了三个特征: 目标对称性、目标水平边缘直线度和目标长宽比。

2. 1 目标对称性

道路图像中,行驶的车辆正面具有一定对称性,对目标进行对称性检测,利用对称性这个特征这样可以有效地将正面车辆和骑自行车/摩托者、行人分类。由于贝叶斯分类器输入是特征值本文使用对称性算法提取目标对称性。对称性特征提取首先对图片进行预处理,为提高图像检测的准确性,对目标要进行灰度化和高斯平滑滤波去噪声。由于检测图像左右对称性,于车辆图像的垂直边缘具备最强的对称性,为排除干扰并减少计算量,本算法仅对边缘的垂直分量进行处理。使用Sobel算子对图像垂直方向进行边缘检测。

得到垂直边缘检测图像,将垂直边缘检测图像各点的垂直梯度值做垂直方向投影。

其中,H为目标区域的高度; B为目标区域的垂直叠加投影; x为垂直叠加投影的列位置。

利用图片中奇函数分量和偶函数分量比值提取目标对称性。

2. 2 目标水平边缘直线度

由于车辆的水平边缘直线度较高,可以有效地将侧面车辆和骑自行车/摩托者、行人分类。本文利用Hough算法提取目标水平边缘直线度。车载多障碍物中汽车的水平边缘直线度较好,其次是骑自行车/摩托者最后是行人。Hough变换检测直线效果较好,检测出直线后,本文提取水平直线,统计直线斜率k在[- 0. 2,0. 2]之间的直线长度和作为目标水平直线度,这样结果较理想,误差较小。

2. 3 目标长宽比

目标长宽比可以有效地将行人和骑自行车/摩托者、车辆分类。计算目标区域的像素点可以得到目标的长宽比。

3 贝叶斯分类器设计

朴素贝叶斯分类是一种简单、高效的分类方法,车载多障碍物属性独立,相关性小,为了准确对车载障碍物进行分类,本文么选取了三个特征: 目标对称性、目标水平边缘直线度和目标长宽比。分类器设计步骤如下:

( 1) 设x = { a1,a2,a3} 为一个待分类项,而每个a为x的一个特征属性,其中a1表示目标长宽比,a2表示目标对称性,a3表示目标边缘水平直线度。

( 2) 有类别集合C = { y1,y2,y3,y4} 。其中y1表示骑自行车/ 摩托者,y2表示汽车侧面,y3表示汽车正面,y4表示行人。

(3)计算P(y1|x),P(y2|x),…,P(y4|x)。

计算步骤如下:

①找到一个已知分类的待分类项集合,即为训练样本集。

②统计得到在各类别下各个特征属性的条件概率估计。即P(a1|y1),P(a2|y1),P(a3|y1);P(a1|y2),P(a2|y2),P(a3|y2);…;P(a1|y4),P(a2|y4),P(a3|y4)。

③默认各个特征属性是条件独立的,则根据贝叶斯定理有如下推导:

其中,i取1,2,3,4。

式中P( x) 为常数,比较P( yi| x) 即比较P( x |yi) P( yi) 。又因为各特征属性是条件独立的,所以有:

( 4) 如果

P(yk|x)=max{P(y1|x),P(y2|x),…,P(y4|x)}则x∈yk,所以贝叶斯分类器P(yk|x)=max{P(y1|x),P(y2|x),…,P(y4|x)}可以转化为:

这样有效将未知图片进行分类,分类器错误率较低。

4 实验结果

4. 1 训练图像选取和处理

选取拍摄效果较好的目标图片120 幅作为贝叶斯分类器的训练样如图2 所示。分别提取训练图片三个特征: 目标对称性、目标水平边缘直线度和目标长宽比。统计的得到训练样本特征值的平均值和方差如表1 训练样本特征值统计所示。得到训练样本的平均值和方差,作为贝叶斯分类器输入。

4. 2 贝叶斯分类器处理结果

本实验是在Windows 7 的微机上完成,采用MATLAB_R2009a实现代码编程。贝叶斯分类器输入Train Samples( 训练样本) ,Test Samples( 测试样本) ,Class Number( 类别数) 。Train Samples将120幅图片三个特征值分别提取生成120( 行) × 3( 列)的矩阵。Test Samples有40 个样本提取特征值选取100 幅测试图片,应用贝叶斯分类器进行分类。测试分类准确度如表2 所示。

5 结束语

本文提出一种基于贝叶斯分类器的车载多障碍物分类器,依据最大后验概率决策规则正确的分类。准确率达到97% ,这样的分类不管概率估计轻度的甚至是严重的不精确都不影响正确的分类结果,具有足够的鲁棒性去忽略朴素贝叶斯概率模型上存在的缺陷。尤其是应用在车载多障碍物分类中,车载多障碍物具有相对独立的特征,这样分类准确度得到保证。素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果,但分类决策中存在错误率,对于P( x | yi) 参数估计通过大量的样本数据计算可以得到更准确的数据分布,降低错误率。

参考文献

[1]Chow T W S,Rahman M K M.A new image classification technique using tree-structured regional features[J].Neurocomputing,2007,70:1040-1050.

[2]Chang Y,Huang H.An Automatic Document Classifier System based on Naíve Bayes Classifierand Ontology[C].Machine Learning and Cybernetics,2008 International Conference on.IEEE,2008:3144-3149.

[3]Zielke T,Brauckmann M,Vonseelen W.Intensity and Edge-Based Symmetry Detection with an Application to Car-Following[J].CVGIP:Image Understanding,1993,58:177-190.

[4]董立岩,苑森淼,刘光远,等.基于贝叶斯分类器的图像分类[J].吉林大学学报:理学版,2007(2):249-253.

[5]王洪刚.贝叶斯理论在医学图像处理中的研究与应用[D].长春:吉林大学,2006.

[6]付丽,孙红帆,杨勇,等.基于贝叶斯分类器的图像分类技术[J].长春理工大学学报:自然科学学版,2009(1):132-134.

[7]高磊,李超,朱成军,等.基于边缘对称性的视频车辆检测算法[J].北京航空航天大学学报,2008(9):1113-1116.

[8]魏浩,丁要军.基于属性相关的朴素贝叶斯分类算法[J].河南科学,2014(1):42-46.

【异常分类器】推荐阅读：

文本分类器05-26

贝叶斯分类器05-13

KNN分类器06-11

决策树分类器06-12

多分类器组合07-04

多类SVM分类器07-10