基于原型分类器

2024-05-01

基于原型分类器（精选八篇）

基于原型分类器篇1

关键词：贝叶斯分类器,文本分类,遗传算法

贝叶斯分类器在文本分类中有着重要的应用, 其中朴素贝叶斯分类器是一种简单有效的概率分类方法。但需要注意的是, 朴素贝叶斯分类器模型在实际应用的过程中往往会出现一定的问题, 例如条件假设难以实现, 属性约简影响分类效果等。

1 文本分类

事先定义好文本类别, 以文本内容为基础, 计算机根据相关自动分类算法, 对文本进行预先定义好的类别划分就是文本分类。文本分类一般可以分为三个步骤, 分别是文本向量模型表示、选择文本特征及分类器训练。

2 遗传算法基本思想

遗传算法是以遗传思想为基础的一种算法, 一定数量的个体经过基因编码之后会组成一个种群, 而遗传算法就从代表问题可能潜在解集的种群开始。

3 基于遗传算法的朴素贝叶斯分类器

本文提出了一种应用于中文文本分类的贝叶斯分类器, 其以自适应遗传算法为基础, 具体设计方案如下:

3.1 设计思路

(1) 进行数据采样、收集、整理等预处理工作, 必要时进行数据的离散化。

(2) 对实体样本数据进行分类, 之后将其随机划分为两个集合, 分别是验证集和训练集, 在训练集中生成S个子集, 每一个子集的属性随机, 针对每一个随机属性子集, 对应的构建一个NBC。

(3) 将构建的NBC作为初始种群, 以上文中提到的遗传算法选择最优解, 在整个遗传操作中, 选择的最优解就是要求的g NBC, g NBC对应的属性集则是所需要的最优属性集。

3.2 g NBC设计

3.2.1 数据预处理

在知识获取系统中, 数据预处理是关键步骤, 这是因为取得的原始数据不能够直接进行知识获取, 需要进行一定的预处理加工才能够满足知识获取条件, 原始数据的采样、收集及整理等都属于数据预处理的范畴。

3.2.2 编码

在遗传算法中, 编码的过程就是基因型与表现型的映射工作, 保证二者的一一对应, 实质上就是解的遗传表示过程。

3.2.3 分类器差异度

差异度指的是空间中分布程度, 将分类精度设为R, 数据集中分类精度数量为m, 则有R1, R2, …, Rm, 用P代表数据集记录个数, 则每一类记录数为P1, P2, …, Pm, 则可以得出以下公式:

Ri为第i类正确分类记录数与所有划分到第i类的记录数之间的比值, 则可以得出分类器差异度D的计算公式:

由上述公式可知, 分类器差异度D的取值范围为 (0, 1) , D的值越大, 即越接近于1, 代表分类器差异性越好。

3.2.4 适应度函数

适应度是度量群体中个体优化计算中接近找到最优解的优良程度的重要标准, 利用适应度函数能够对个体适应度进行评估, 从而对群体中个体优良程度进行评价。

3.2.5 遗传操作

(1) 选择操作, 即个体的优胜劣汰, 选择适应性更强的染色体, 将这些染色体组成新的种群。

(2) 遗传运算, 主要包括交叉运算和变异运算, 形成新的个体并产生相应后代。

4 算法验证

4.1 数据预处理

为了对本文提出方法的有效性和可行性进行验证, 本文以搜狗实验室文本分类数据为语料库, 选取五类中文文档, 分别是汽车类、教育类、体育类、文化类及旅游类, 每类文档中包含新闻报1990篇, 文档数量为9950。

4.2 验证结果分析

将数据库分为验证集和训练集, 前者30%, 后者70%, 测试验证集, 对NBC和g NBC的分类精度进行比较, 结果如表1所示。

由表1可知, 相较于NBC来说, g NBC分类精度普遍更优良, 在同一数据集中, 差异度影响系数取值不同, g NBC分类精度也有着一定多个差异性, 因此, 适当对差异度进行考虑有助于提升文本分类能力。但同时也需要注意, 实验过程中, 如果增加特征数目, 会一定程度影响分查速度, 在应用的过程中需要平衡速度和效率, 这是本方法需要改进之处。

5 结论

综上所述, 贝叶斯分类器在中文文本分类中有着重要的应用, 本文提出了一种以遗传算法为基础的朴素贝叶斯分类器, 分析了分类器的设计流程和功能实现, 通过实例验证表明, 本文提出的贝叶斯分类器在中文文本分类中的应用效果良好, 分类精度较高, 但在实际应用的过程中需要平衡分类效率和速度, 这也是需要进一步改善之处。

参考文献

[1]罗海蛟.数据挖掘中分类算法的研究及其应用[J].微机发展, 2013, 13 (02) :48-50.

[2]王灏, 黄厚宽, 田盛丰.文本分类实现技术[J].广西师范大学学报:自然科学版, 2013, 21 (01) :173-179.

基于原型分类器篇2

关键词 KNN算法；Bayes算法；组合分类器；互信息；交叉验证

中图分类号 O213；TP18 文献标识码 A

1 引言

电子商务的异军突起促使网购走进人们的日常生活，网购的同时，多数网民会在不受约束的情况下对相关产品发表评论，而这种随意性往往使得这些产品评论中充斥了大量无用的、不真实的信息，这些信息就是垃圾评论.垃圾评论在一定程度上影响了评论信息的参考价值，从而误导潜在消费者并干扰销售商对销售业绩的评价.产品垃圾评论的识别旨在解决这一问题，将垃圾评论从评论文本中剔除，保留真实的产品评论，为用户提供可靠的参考依据.

结合近几年垃圾评论识别的文献可知，垃圾评论识别的关键问题是文本特征的提取与分类算法的选择.N Nitin Jamal和Bing Liu等[1]首次对垃圾评论进行了分类，很好地识别了英文领域中存在的无用评论，但由于中英文之间存在差异，往往英文领域的垃圾识别方法不能直接有效地应用到中文领域当中.游贵荣等[2]提出了中文垃圾评论的特征提取方法，邱云飞等[3]、吴敏等[4]、李霄等[5]分别从用户行为、产品特征的显著性检验以及信息的有用性角度对垃圾评论的识别进行了研究，但在分类器的选取上，上述学者均采用单一算法的分类模型，如单一的Logistic回归算法等.大量的理论与实验结果表明，多分类器系统不但可以提高分类的正确率，而且可以提高识别系统的泛化能力和鲁棒性.与此同时所有分类器都参与集成的效果并非最好，从众多分类器中选择部分互补性强的分类器进行集成可以提高集成的效率并改善其效果[6].因此本文在建立文本特征表示模型的基础上，提出了用高互补性组合分类器对评论进行识别和过滤.

2 文本特征的提取

2.1 产品评论的特点与垃圾评论的分类

为了更准确地识别垃圾评论，首先探讨产品评论的特征.

通过对中文产品评论中的评论文本进行分析，总结出中文产品评论领域的特点主要体现在以下几个方面：

1）评论文本格式自由多样；

2）评价对象的多样化；

3）评论内容具有近似重复性；

可分为①由不同评论者针对同一产品发表的近似重复评论；②由同一评论者针对不同产品发表的近似重复评论；③由不同评论者针对不同产品发表的近似重复评论；

4）不真实评论；

5）广告；

6）不带有感情色彩的随机文本.

基于以上分析，将垃圾评论定义为以下5种类型：-

1）非指定产品的评论：该类评论的特点为它虽然是评论，但只对品牌和制造商，甚至是站点评论，而没有针对当前产品本身进行评论，或者确实是对产品进行了评论，但是评错了产品.如在苹果手机的评论中，“买SONYZ3也不错啊，很漂亮，旗舰机...”等

2）虚假评论：如“我这有全新的iPhone6 Plus，只要99元”等.

3）广告评论：如“苹果超爱大屏幕3 500元拿现货QQ热购122929079”

4）无意义文本：

①个人的消费经历，如“再烂都永远有人疯抢，飘扬过海甚至成为一部手机，实在不懂.”②人身攻击，如“用苹果的都是脑残”等，③其他无关文本，如“信号不好等”“转给我呗？”

5）咨询性评论：只是询问关于产品的情况，而不是评论.如“多少钱呢？”.

2.2 特征提取与量化

为了建立产品垃圾评论识别模型，根据2.1节的分析结果，分4个模块对产品评论文本进行特征提取与量化.

模块一数据的搜集

本文采用WebHarvest网络爬虫对京东商城和天猫商城内多个商家的iPhone 6 Plus的产品评论进行爬取，得到由两万条产品评论组成的数据集A0，同时对苹果官网上关于iPhone 6 Plus的产品参数进行爬取，得到产品属性数据集B0.

模块二对爬取的数据集进行预处理

1）构造用户词典.用户词典包括停用词词典、极性词词典，其中极性词词典主要是由HowNet极性词加上一些评论作者常用的、和表达情感有关的网络流行词，及一些口语化的词语与缩写组成，用以表达用户褒贬倾向和感情色彩.停用词词典由网络上现有的停用词词表加上针对垃圾评论特性的停用词组成[7-9].

2）文本分词.中文单词是评论信息处理的基础，分词工具采用中科院提供的分词工具ICTCLAS 2015分词系统[10]，其主要功能包括中文分词、词性标注，同时允许用户向系统中导入自定义词典以提高特定领域的分词效果，因此，将上述用户词典与产品属性数据集B0作为自定义词典导入ICTCLAS分词系统后，对数据集进行逐条分词、词性标注以及情感词标注，得到预处理后的数据集A.

模块三特征的互信息检验

为了选取最能表达文本信息内容的特征，本文从被评论的商品、评论者、文本结构、情感倾向、主题词五个属性提取特征，在提取特征之前，先利用互信息说明这5个属性对识别垃圾评论具有显著相关性.-

互信息是2个事件集合之间的相关性，通常用来衡量某个属性和类别之间的统计独立关系，互信息量越大，代表特征项与类别之间的贡献概率也越大.现对所选特征进行互信息检验，旨在说明所选属性能在一定程度上反应该条评论的信息，即所选属性项是互信息量较大的词条，互信息（MI）定义如下

2）高互补性分类器

高互补性分类器组合的构建流程大致为：首先构造一定数量的候选分类器如Bayes分类器、KNN分类器、SVM分类器和logistics回归分类器等，计算分类器之间的相关程度，然后根据相关系数对候选分类器进行排序，并依据可信度，选择出对目标有较高识别率的分类器组合.

首先，验证单一算法分类器的局限性.利用数学软件MATLAB，对其进行基于多层BP网络的识别模式的标记，对上述四种分类器用SPSS比较其准确率，召回率以及Fmeasure值.得表2.由表2，垃圾评论识别的准确率相对偏低，不少数量的正常评论被识别为垃圾评论；其召回率也不高，直观来看是有些垃圾评论被判别为正常评论.可见单一分类算法的过滤效果并不理想，本质原因是分词的不准确性使得评论文本特征有限的缺点充分暴露，以致于对结果的准确性产生很大影响，而且Bayes分类器要求各个特征项之间相互独立，这显然于现实不符.同时也从侧面说明单一算法的分类器对数据量要求很大，需要对较为完备的训练集特征进行学习[6].

为了更准确地进行垃圾评论识别，本文对各分类器进行组合，得到高互补性分类器.根据高互补性分类器组合理论，利用相关系数对上述4种分类器的互补性进行分析，即相关系数大的分类器组合互补性弱，相关系数小的分类器组合互补性强.

利用SPSS软件对其进行相关分析，见表3.

由表3，相关系数的大小排序为：

SVM+Bayes>SVM+KNN>Bayes+LR> LR+KNN>LR + SVM>Bayes+KNN.

其对偶命题互补性排序为：

SVM+Bayes

LR+KNN

可见Bayes分类器和KNN分类器的相关性最低且显著性均大于0.01，即可认为他们之间的互补性最强，存在统计学意义.而SVM分类器和Bayes分类器的相似度较高，且显著性大于0.01，认为存在统计学意义.为了进一步验证这4种分类器的互补性，对这6个组合进行聚类检验.

用SPSS软件对其进行聚类分析，结果见表4

由上可知，互补性最强的组合分类器为Bayes+KNN分类器.

3.4 模型的交叉验证

本文利用WebHarvest爬虫从天猫和京东商城爬取了20 000条评论作为原始数据集A0，将构建好的用户词典与产品属性数据集B0导入ICTCLAS 2015分词系统后，得到预处理数据集A，对A中的每个数据类型进行人工标记，再随机地将其等分成4份得到A1、A2、A3、A4.

先以数据集A1为检验集，A2，A3，A4为训练集，计算模型的性能指标.首先将数据集A2，A3，A4的特征向量导入Bayes+KNN组合分类器对其进行训练，然后将检验集A1的特征向量导入到已训练好的分类器中，得出检验集中相应评论是非垃圾评论还是垃圾评论，最后根据分类器对每条评论判定的结果以及人工标记，计算该训练集和检验集组合下，分类器的性能指标.用同样的方法得到依次以A2、A3、A4为检验集的分类器的性能指标，相关结果见表5.-将上述3个评价值平均得，基于KNN算法和Bayes算法的垃圾评论识别模型的最终准确率达到75.3%，召回率为82.1%，F1值为77.5%，结果较为理想，有应用价值.

4 结束语

垃圾评论识别的关键问题是文本特征的提取与分类算法的选择.本文根据中文评论的特点提取了14个特征，并利用组合分类器算法对垃圾评论进行了识别，得到了较理想的结果.通过搭建基于Hadoop的大数据平台集群，本模型可推广到一个基于通过海量数据集进行训练的垃圾评论问题，从而实现此模型适用于更一般产品的垃圾评论的检测目标.-

参考文献

[1] N JINDAL， B LIU.Opinion spam and analysis[C]//Proceedings of the first ACM international conference on Web search and data mining，2008：219-229.

[2] 游贵荣，吴为，钱沄涛.电子商务中垃圾评论检测的特征提取方法[J].情报分析与研究.2014，251（10）：93-100.

[3] 邱云飞，王建坤，邵良彬等.基于用户行为的产品垃圾评论者监测研究[J].计算机工程.2012，38（11）：254-257，261.

[4] 吴敏，何珑.融合多特征的产品评论识别[J].微型机与应用.2012，31（22）：85-87.

[5] 李霄，丁晟春.垃圾商品评论信息的识别研究[J].现代图书情报技术.2013，29（1）：63-68.

[6] H J KANG，D DOERMANN.Selection of classifiers for the construction of multiple classifier systems[C]//Proceedings of the 8th- international conference on Document Analysis and Recognition. Seoul， Korea， 2005，1194-1198.

[7] 知网[DB/OL].HowNet Knowledge Database[DB/OL].[2013-11-05]. http：//www.keenage.com/ .

[8] 赵文婧.产品描述词及情感词抽取模式的研究[D].北京：北京邮电大学计算机学院，2010.

[9] 顾益军，樊孝忠，王建华.中文停用词表的自动选择[J].北京理工大学学报.2005，25（4）：337-340.

[10]ICTCLAS 汉语分词系统（ICTCLAS Chinese Lexical Analysis System [CP/OL].[2015-10-05].http：//www.ictclas.org/.

[11]C C CHEN， Y D TSENG. Quality evaluation of product reviews using an imformation quality framework[J].Decision Support Systems. 2011， 50（4）：755-768.

基于判别函数算法的图像分类器设计篇3

MATLAB是当前最流行的、功能强大的高效率的数值计算的可视化科技应用软件和编程语言之一。其特有的图形用户界面开发环境(Graphical User Interfaces Developmen Envronment,简称GUIDE)大大简化了人机交互界面程序的开发过程。

1 判别函数理论简介

模式识别分类问题是提取待识别对象的某方面的特征,根据观察值建立识别对象的训练集,训练集中样本点的类别已知,基于这些条件建立适当的判别函数,并使用已有的样本来估计判别函数的未知参数,最后用判别函数对待测样本的类别进行判别。

1.1 判别函数概念

由于一个模式通过某种变换映射为一个特征向量后,该特征向量可以理解为特征空间的一个点,在特征空间中,属于一个类的点集,总是在某种程度上与输入另一个类的点的集合相分离,各个类之间确定可分离的。因此,如果能够找到一个分离函数(线性或非线性函数),把不同类别的点集分开,则分类任务就解决了。判别函数法不依赖于条件概率密度的知识,可以理解为通过几何方法,把特征向量分解为对应于不同类别的子空间。而且呈线性的分离函数,将使计算简化。找分界线的方法就是判别函数法,判别函数法的结果就是要提供一个确定的分界线方程,这个分界线方程叫做判别函数,因此判别函数描述了各类之间的分界线的具体形式。

1.2 判别函数的类型

判别函数法按照分界函数的形式可以划分为现行判别函数和非线性判别函数两大类。现行判别函数由于涉及的数学方法较为简单,在计算机上容易实现,故在模式识别中被广泛应用。但是在模式识别中仅仅有线性分类器是不够的。在模式识别中的许多问题中,由于线性判别函数有其一定的局限性,它并不能提供理想的识别效果,必须借助于非线性的分类器。而且,有些较为简单的非线性分类器,对于某些模式识别问题的解决,显得简单,效果又好。

1.3 线性判别函数

模式识别中用以对模式进行分类的一种最简单的判别函数。在特征空间中,通过学习,不同的类别可以得到不同的判别函数,比较不同类别的判别函数值大小,就可以进行分类。对于特征空间中的每个特征向量x,可以计算相应于各个决策区的判别函数gi(x),i=1,2,…,m,用判别函数进行分类的方法就是:若对所有的i均有gi(x)≥gj(x),则把x分为第j类,记成r(x)=j。对于线性判别函数,gi(x)的函数形式为

式中x1,x2,…,xd是输入模式特征向量的各个分量,Wi0,Wi1,…,Wid组成与第i类对应的权向量,它们的大小反映与它们对应的特征向量的各个分量在确定第i类判别函数值的重要程度。

特征空间中分别与第i类、第j类相对应的区域之间的决策边界形式为

对于一个两类分类器,可以计算g(x)=g2(x)-g1(x)。若g(x)≥0,则r(x)=2,相应于决策区R2。若g(x)<0,则r(x)=1,相应于决策区R1。这一结果可写成

2 图像分类识别系统实现

2.1 颜色空间与量化

颜色空间有很多类型,常见的有HSV颜色空间、RGB颜色空间等,其中HSV颜色空间更接近人的视觉特性,其中包括色调H(Hue)、饱和度S(Saturation)和亮度V(Value)。在以图像内容为条件的图像识别中,HSV颜色空间比RGB颜色空间更适合辨别。根据人眼的识别能力,颜色大致分为9种:红、黄、绿、青、蓝、紫、黑、灰和白,根据这9种颜色基本可以描绘一幅图像。因此,由这9种颜色可确定图像的主颜色特征,其具体量化方法详见参考文献[5]。

2.2 图像分块主色的实现

该文对识别图像做4*4的划分,得到16个子图像。对每个子图像进行像素颜色统计,取数值最高的颜色为主颜色,这样就得到识别图像对应的16个主颜色特征向量。此种方法突出每个子图像颜色的空间关系,适用于颜色特征固定的分类问题,但对颜色变化明显的图像效果一般。

2.3 主要MATLAB程序

函数名:jiangcheng()

参数:sample:待识别图像特征

返回值:y:待识别图像所属类别

函数功能:判别函数奖惩算法分类器

3 图形用户界面

MATLAB的GUIDE功能提供了便捷的软件界面设计工具箱,利用此工具箱可设计出形象直观的人机交互界面。图像识别系统界面主要内容是各个空间的回调函数,利用回调函数可执行相应控件的功能,下面以菜单“线性函数”下的“奖惩算法”按钮为例,给出其回调函数的Callback的语句

在MATLAB提示符下输入系统名“PDHS”命令,启动如图1所示的系统主界面,用户可用其中的载入图像按钮载入待识别的图像,在菜单项中选择“线性函数”的“奖惩算法”选项按钮,系统就可显示待识别图像的类别,颜色矩阵,分类时间等信息。

4 总结

该文介绍了利用MATLAB软件开发基于判别函数的图像分类系统的方法和步骤,选取了模式识别中常用的基于判别函数的算法,实现了对两类图像的分类问题。利用MATLAB图形用户界面(GUI)方法,设计了良好的人机交互系统的主界面,最后给出了实际例子的程序运行结果,对推动模式识别理论在图像分类问题实践中的应用和普及,具有实际意义。软件系统的性能还需要进一步提高,进一步工作包括增加聚类分析等算法,实现对三类及多类的图像识别问题。

摘要：判别函数法是找分界线的一种算法,其结果就是提供一个确定的分界线方程,这个方程就是判别函数,因此判别函数描述了各类之间的分界线的具体形式。该文主要是基于判别函数模型,对图像分类问题进行了研究,通过实例说明分类方法的有效性和可行性。实验结果表明判别函数模型具有一定的实际应用价值,在图像分类问题上,判别函数方法性能良好,分类准确和高效,最后利用利用MATLAB图形用户界面(GUI)方法,设计了良好的人机交互系统的主界面。

关键词：判别函数,图像分类,MATLABGUI

参考文献

[1]杨淑莹.模式识别与智能计算—MALAB技术实现[M].北京:电子工业出版社,2008:67-78.

[2]陈垚光,王玲.精通MATLAB GUI设计[M].北京:电子工业出版社,2007:21-34.

[3]王家文.MATLAB7.6图形图像处理[M].北京:国防工业出版社,2008:78-100.

[4]余芳.基于颜色特征的图像检索技术研究[D].中国石油大学,2007.

基于原型分类器篇4

关键词：贝叶斯,多分类器,FISHER,人脸识别

0 引言

近年来, 国内外各种研究机构和高等学府都展开了人脸识别技术的前沿研究和探索[1], 并不断涌现出许多新的成果, 这些研究成果大都已进入应用推广阶段。目前, 人脸识别算法所面临的主要问题是:在光照、环境以及被识别人本身的化妆、年龄老化、胖瘦变化、表情变化、脸部装饰等因素的影响下, 识别算法常常不能准确工作。因此, 如何提高识别算法在恶劣光照下和在面对不同时期的人脸时的准确率, 是研究的热点问题。本文研究的基于贝叶斯多分类器融合的人脸识别算法可以在一定情况下较好地提高人脸识别的准确性。

1 贝叶斯分类器

基于正态分布的贝叶斯规则具有很强的区分能力, 非常适合用来对人脸进行区分。这种人脸识别方法在美国DAPAR组织的人脸测试中是效果最好的方法之一。本文将对介绍贝叶斯规则及其相关概率论方面的知识进行介绍[2]。

在随机试验中, 每个可能结果称为基本事件, 记为ω, 基本事件的全体, 即试验中所有可能结果的集合称为试验的样本空间, 记为Ω。随机事件A发生的可能性大小的数值度量就称为事件A发生的概率, 记为P (A) 。条件概率指的是一事件A在另一事件B已发生的情况下可能发生的概率[3]。条件概率的定义如下:

对Ω中任意两个事件A、B, 若P (B) >0, 则称:P (B|A) =P (AB) |P (B) 为在己知事件B发生的条件下, 事件A发生的条件概率。

如果事件组满足:

(1) B1, B2, …, Bn, 互不相容且P (Bi) >0 (i=1, 2, …, n) 。

(2) B1∪B2∪…∪Bn=Ω。

则称B1, B2, ……, Bn为一个完备事件组。完备事件组实际上就是某个样本空间Ω中所有可能发生的事件的集合。设事件Bl, B2, ……, Bn为一完备事件组。则对于任意事件A, 只要 (PA) >0, 就有:

该公式称为贝叶斯公式, 也称逆概率公式。一般而言, 在进行某个试验时, 事件A已经发生, 要求出于某种原因Bj, 导致该结果发生的概率, 往往用贝叶斯公式。贝叶斯公式实际上是通过对事件发生的先验概率进行修改而得到后验概率的一种方法[4]。由于先验概率可以根据大量的统计信息来近似估算, 因此贝叶斯公式被大量应用在分类决策中。

可以将完备事件组B1, B2, ……, Bn看作n个类别, 这样当事件A己经发生, 使用贝叶斯公式可以求出导致A发生的原因属于某类别Bj的概率, 那么就可以选取此概率最大的那个类别作为分类的输出结果。

2 多分类器融合算法

当今较为优秀的算法不仅采用了人脸的全局特征, 同时也采用了人脸的诸如眼睛、鼻子、嘴巴等区分度比较大的局部特征, 将多个局部融合一起后的特征进行匹配, 都取得了比较好的结果[5]。本文所涉及到的通过加权相似度求和策略对多个分类器进行融合的一种综合性人脸识别算法中, 连同人脸的全局特征, 加入眼睛、嘴巴、鼻子等重要局部区域进行融合识别。

(1) 人脸关键局部特征提取。由于人脸的眼睛、鼻子、嘴巴等局部区域包含了大量的人脸纹理信息, 因此对于输入的一幅图像, 提取他的全局、眼睛、鼻子、嘴巴等几个区域特征。

对于输入的人脸图像, 先进行ATICR预处理, 然后选取出全局、眼睛、鼻子、嘴巴4个区域块, 分别对各自的子空间进行投影, 就可以得到该人脸的4个特征向量。

(2) 加权相似度算法。考虑到不同分类器在整体融合时所处的地位和作用不同, 想到一种加权相似度求和的融合算法, 它利用训练数据得到各分类器的表现, 然后根据其识别率为每个分类器算出一个权重。最后把3个分类器的相似度求加权和, 得到最终的相似度, 然后以此相似度算出识别结果[6]。具体步骤如下:

Step1:选择一个具有代表性的测试数据库, 分别计算单独使用某一分类器时的识别率, 然后求出全局特征权重a、眼睛特征权重b、鼻子特征权重c、嘴巴特征权重d, 公式如下:

其中, r1、r2、r3、r4分别表示单独采用全局特征、眼睛特征、鼻子特征、嘴巴特征时的识别率, 其中a、b、c、d也称为各分类器的置信参数。

Step2:以a、b、c、d为各分类器的置信参数, 当要比较某测试图像和数据某图像的距离S时, 令:

其中, S1、S2、S3、S4分别指测试图像和数据库图像各分类器的距离[7]。

这样, 就对各分类器的距离进行了有效融合, 并且根据各分类器的置信参数加权到最终的距离中。

(3) 多分类器融合算法[8]。结合贝叶斯分类规则[9]和FISHER线性判决[10], 并通过加权相似度求和策略的贝叶斯多分类器融合算法, 利用训练数据信息, 对属性进行判决分析后, 再次进行加权。多分类器融合算法实现步骤如下:

Step1:数据预处理, 将训练样本和待分类样本进行补齐和离散化。

Step2:分类器构造。

Step3:扫描所有训练样本, 统计训练集中, 类标签为Ci, 属性Ak取值v的实例集 (Ak=v∧Ci) , 形成统计表。

Step4:计算所有的先验概率P (Ak=v|Ci) , 即在类别Ci中属性Ak的取值v的概率, 每个属性值v的条件概率如下:

Step5:根据统计表, 计算属性P (Ak=v|Ci) 的权值Wk, v, i。

Step6:生成加权属性相似度求和贝叶斯概率表及属性权值列表。

Step7:调用概率表及属性权值列表, 对多个分类器进行融合, 得出数据识别结果。

3 实验测试

3.1 测试内容

为了测试系统的识别效果, 使用常用数据库ORL、Yael、FERET, 以及刑侦项目中公安局提供的数据库对算法进行了测试。主要通过任一数据库对如下4个方面进行算法测试: (1) 算法在光照良好、具有一定表情变化、旋转角度20°以内的变化和面部装饰变化情况下的综合表现; (2) 测试算法在光照变化情况下的鲁棒性; (3) 测试算法在复杂数据库, 尤其是时间跨度大的图像下的识别率; (4) 比较单独使用全局特征与合并使用全局+局部特征在各种情况下的综合表现。

3.2 测试结果

算法的一般性表现测试是在ORL数据库上进行。ORL数据库中共有40个人, 每人10张图片, 共有160张。其图片的特点是光照较好, 但也有个别光照不均的现象。每人都有一定的各种表情变化, 包括人脸的旋转角度等。在测试时, 从ORL中每人抽取4张图片作为训练图片, 剩下的6张中, 3张作为数据库集, 3张作为测试集, 并不断变化各种组合进行测试。数据库例图如图1所示。

ORL数据库的测试结果如表1所示。

在测试结果中, MBFISHER1表示相似度平均的多分类器融合算法, MBFISHER2表示本文所研究的加权相似度求和的多分类器融合算法。从测试结果可以看出, 对于一般情况下无光照处理的人脸图片, 采用加权相似度求和的多分类器融合算法要比采用相似度平均融合算法有更精确的识别表现。

4 结语

通过加权相似度求和策略对多个分类器进行融合的算法较为有效, 从实验可以看出该方法在无光照处理下, 识别效果更为精确。在多属性、多类别数据集及小样本数据集情况下, 如何更好地提高分类器的分类及识别能力, 是后续重要研究方向。

参考文献

[1]张敏, 张海艳, 刘亭, 等.人脸识别系统综述[J].电子世界, 2014 (15) :107-108.

[2]郝宇晨.贝叶斯网络分类器近似学习算法[J].计算机系统应用, 2014 (8) :189-193.

[3]骆名剑.基于ROC的分类算法评估方法[D].武汉:武汉科技大学, 2005.

[4]HAND D J TILL R J.A simple generalization of the area under the curve for multiple class clssification problems[J].Mschine Learning, 2001 (45) :171-186.

[5]祝媛, 常江龙.基于多分类器融合算法的3D人脸年龄识别[J].计算机仿真, 2009 (5) :248-250.

[6]BABACK MOGHADDAM, MING-HSUAN YANG.Learning gender with support faces[J].IEEE Transactions on pattern analysis and machine intelligence, 2002, 24 (5) :707-711.

[7]GRAHAM BYATT, GILLIAN RHODES.Recognition of own-race and other-race caricatures:implicaiton for models of face recognition[J].Vision Research, 1998, 38 (14) :2455-2468.

[8]张欣, 梁宗保.多分类器融合算法研究与应用[J].湘潭大学自然科学学报, 2011 (2) :99-103.

[9]郑默.贝叶斯分类算法的研究与应用[D].重庆:重庆大学, 2011.

基于原型分类器篇5

本文的基本思想, 是通过建立相反分类器使分类算法可以从错误中学习。当一个分类器的期望分类精度较低时, 不是简单放弃该分类器而应建立并验证其相反分类器。当相反分类器和现有概念一致时, 通过更新组合分类器, 就有可能提高组合分类器的分类精度[1]。

定义1相反分类器:一个分类器用C来表示, 对于一个实例X, C (X) =ci, ci∈c, 则分类器C的相反分类器记为, 其中X) =c′i, c′i≠ci, c′i∈c。特别当c=[0, 1]时, 分类器C的相反分类器是

图1中的直线表示目标概念1。图2是分类器C1的相反分类器。图3是目标概念2以及对应的分类器C2。数据流中经常面临概念变化的情况, 当概念由1变化到2时, 用分类器C1去分类, 实际上由概念2决定的实例, 就会出现很大的错误率。此时Weighted Bagging方法就会舍弃分类器C1, 而逐步训练新的分类器以适应概念2。从而会导致分类器收敛速度下降和分类器C1中信息的浪费。而分类器C1的相反分类器却和概念2比较接近, 可以先用去分类概念2标记的实例, 等得到与概念2更近似的高精度分类器时再替换分类器。判断一个分类器的相反分类器是否与最近的概念相近, 必须计算它的期望预测错误率, 只有该相反分类器的分类能力较高时, 才将它加入集合中更新组合分类器。

当数据流逐步流入时, 到来的数据被分成数据段S1, S2, , …, Sn, …, 其中凡是最近时间步到来的数据段。记每个段的大小为Chunk Size, 在每个数据段上训练分类器C1, 组成一个分类器集合。为了对每个分类器进行准确度赋权, 可在测试数据集上计算它的期望预测错误率。如果假设最近的训练数据段和测试集合的类分布非常近似, 则分类器的准确率赋权可以通过在Sn上的分类错误率近似得到。具体来说, 一个分类器C在Sn上的平均平方错误率可定义为:

其中:S n中的每个实例具有形式 (X, ci) , X表示一个实例, Ci是该实例的类标号;fC (X) 是分类器C计算得出的实例X属于类Ci的概率Ci∈c (Sn) 是凡中实例的类标记的集合。分类器C的权应该和平均平方错误率成反比。

另一方面, 当用一个随机分类器来分类数据段Sn时, 它的平均平方错误率为:

当一个分类器的权为负时, 表示该分类器的分类精度比一个随机分类器的精度还要差, 所以Weight Bagging会放弃权为负的所有分类器, 这也反映了该分类器的相反分类器与当前的概念比较接近, 如果这个相反分类器的精度较高, 就可以帮助改进分类的精度。

2 IWB (Improved Weighted Bagging) 算法

推进和装袋是两种经常使用的产生组合分类器的方法, 而推进方法要求对数据点进行重新赋权和对噪音敏感, 因此本文中使用装袋方法来产生组合分类器。[2]

输入:S//数据流中新到来的Chunk Size个点构成的集合

Ec//K个预先训练的分类器组成的集合

K//Ec中的分类器数目的最大值

输出:Ec//分类器的集合, 其中每个元素是一个分类器及其权

算法1是挖掘概念漂移的数据流组合分类器算法。在每一个时间步, 一个新的数据段到达时, 首先在这个数据段上训练一个分类器, 其次在这个数据段上使用基于交叉验证的方法来评价这个分类器, 最后根据公式更新集合中其它基础分类器的权。如果某个基础分类器的权小于0, 就计算其相反分类器, 并在这个数据段上进行评价。只有当相反分类器的权大于0时, 它才被加入集合中。算法最终返回这个集合中权最高的k个分类器。

在预测测试实例的类标号时, 使用集合中所有权大于0的分类器进行赋权投票来决定最终的类标号。

3实验验证

为了验证我们的算法, 首先在STAG-GER概念上和Weighted Bagging方法进行比较。在STAGGER概念中, 每个实例有三个属性值color∈{green, blue, red}, shape∈{triangle, circle, rectangle}和size∈{small, medium, large}。练实例陆续在120个时间点上到达, 在每个时间点, 学习器接收到一个实例[3]。在前40个时间点上, 目标概念是color=red∧size=small接下来的4 0个时间点, 目标概念是size=medium∨shape=cicle, 在最后的40个时间点上目标概念是。为了评价学习器, 在每个时间点上随机地产生100个测试实例, 这100个实例是以当前时间的目标概念标记的。每学习一个新的训练实例后, 用集合中的分类器在相应的100个测试实例上计算正确预测的百分比。在整个的实验中, 重复这个过程50次, 取其平均值。组合分类器中的每个分类器都是采用决策树分类器C4.5。

每当概念发生变化, Weighted Bagging算法重复出现突然地准确度降低。而在概念发生漂移的时候, IWB算法具有更快的收敛到目标函数的能力。不仅在发生概念漂移的时候, 预测的精度下降比较低, 而且收敛到新的目标概念的速度比较快, 更重要的是随着时间的推移, IWB的学习能力越来越强。在时间步240后, 预测的精度不再随着概念的变化而出现突然降低, 一直保持较平稳的预测精度, 预测错误率应该和概念漂移的数目不相关。

4结语

本文定义了相反分类器, 设计并实现了基于相反分类器的组合分类器算法IWB。在基准数据集和移动的超平面数据集上进行了检验。实验结果表明, IWB算法比Weighted Bagging方法在遇到概念漂移的时候具有更快的收敛到目标函数的能力并具有更高的精度。

摘要：本文提出了基于组合分类器的IWB算法, 定义了相反分类器。通过使用相反分类器, 在遇到突然的概念漂移时, IWB算法可以从错误中学习, 具有更快地收敛到新的目标概念的能力, 而当概念稳定时没有大的波动。

关键词：相反分类器,IWB算法,数据流

参考文献

[1]高宏宾, 张小彬, 杨海振.一种实时挖掘数据流近似频繁项的算法[J].计算机应用, 2008 (12) .

[2]Wei　Fan.Systematic　data　selection　to Mine　Concept-Drifting　Data　Streams.In　proceeding　of　the　conference　KDD, 2004:128～137.

基于原型分类器篇6

关键词：浮动车数据,地图匹配,历史匹配数据,支持向量机多分类器

0 引言

浮动车数据(Floating Car Data,FCD)采集技术是近几年发展起来的交通信息采集技术,能够得到城市范围的实时交通状况[1]。其中,地图匹配是FCD处理的重要步骤,直接影响对交通信息估计的准确性。由于电子地图与定位设备存在误差,车辆轨迹在电子地图上与实际道路位置产生了较大偏差。恰当的地图匹配算法能够降低车辆定位误差,使车辆标记到正确道路。

根据匹配方式的不同,地图匹配分为全局匹配和增量匹配。文献[2]中描述了一种简单搜索的点对点增量匹配方法,文献[3]中引入了基于距离和方向的匹配策略,除了位置点外没有使用其他先验知识。文献[4]中的方法建立在前点已匹配基础上,此方法会累积匹配误差。GPS误差对增量匹配算法影响大,匹配结果对于突出点敏感,从而匹配准确度较低。全局匹配算法是寻找与车辆轨迹最接近的路径,文献[4][5]使用Fréchet距离进行相似度计算,匹配准确度比增量方法高。全局匹配算法不仅算法复杂度高、计算代价大,且不能用于FCD实时匹配。

本文提出一种对全局匹配得到的匹配结果进行统计学习的方法,以实现高准确度的FCD实时增量地图匹配。论文组织如下:首先给出了SVM多类分类理论;其次结合历史匹配样本误差特征给出了特征向量的获取方法;然后基于网格划分的SVM分类策略给出了本文的地图匹配算法;最后使用合肥FCD进行了地图匹配实验,给出训练过程及结果分析。

1 SVM多分类器

支持向量机(SVM)理论适合小样本学习及结构风险最小的特性,在机器学习领域产生了很好的应用效果。SVM用于分类的思路是:通过某种非线性映射将输入向量映射到高维特征空间,然后在此空间构造最优超平面,使分类间隔最大,同时保证训练样本的误差尽可能小。

本文采用one-against-one策略解决多分类问题[9]。该方法构造k(k-1)/2个分类器,每个分类器训练多类中的两类数据。对于第i类和第j类组成的训练数据,我们要解决下述二分类问题:

构造完毕后,使用如下投票策略来对未知样本x进行类别预测:每个分类器都给出对x的预测类别,如果分类器将此样本x分到第i类,那么第i类投票加1;否则,第j类票数加1。所有分类器都统计完成后,投票数最多的类别作为样本x的预测类别。

2 FCD误差分析

FCD由大量GPS数据构成,它的误差来源于GPS定位过程。导航卫星、信号传播过程及接收设备都对定位产生误差。Diggelen、Leick等人分别对GPS定位的准确度进行了理论分析和实验验证[6,7,8]。本文在上述研究基础上,作出GPS定位误差分布假设如下:a.GPS误差(在经度、纬度、海拔的每一维度上及时间上的误差)服从高斯分布。b.在水平误差分布上,比如XY平面上的分布,等概率密度线呈圆形。

基于实际FCD匹配结果进行分析(图1),可以观察到,上下两条平行的路段上分别分布了样本。这些样本是分布在路段中心线的周围,离中心线越近,密度越高,且不同路段之间存在一定间隔。通过分析发现,匹配样本可以基于路段来进行分类,即每条FCD记录的正确匹配路段编号作为该记录的类别。

3 FCD样本的特征提取

每个样本提取出来的特征组成了一个特征向量,用于SVM的训练和分类。对于一个好的匹配结果,GPS点离待匹配路段较近。并且匹配到同一路段的不同匹配点通常都聚集在一起,在电子地图准确的情况下,路段中心线处点分布密度较大。另外,对于平行反向的两条路段,通常这两条路段在同一条主干道上,离得非常近,每条路段都有方向性,而GPS点方向角是区别匹配点属于哪条路段的有效信息。因此,对于每个FCD样本(如图2所示),特征向量为:{X,Y,D}。其中,X为经度,Y为纬度,D为方向角。方向角取值范围为[0,359],以正东方向为0度,逆时针增加。

4 基于SVM的地图匹配算法

FCD地图匹配算法流程(如图3所示)分为离线训练和实时匹配。离线部分采用全局匹配[4]得到匹配结果,每个路段会有一组匹配点样本组成。使用每个路段上的匹配结果样本离线训练SVM多分类器。实时匹配部分,将实时匹配到路段的问题看作是匹配点的分类问题,训练好的分类器对匹配点进行分类预测,类别即是匹配后的路段编号。

4.1 基于路网划分的SVM多分类器训练

随着类别数增多,SVM多分类器的训练会耗费越多时间。若以整个城市的路段作为类别,计算代价会非常大。因此,本文对路网划分成nxn网格。设地图长为L,高为H,划分为nxn份,每个网格长l=L/n,高h=H/n,设路网左上角顶点坐标P0:(x0,y0),任意GPS点坐标为p(x,y),那么p所属的网格索引号ID的计算公式:

其中floor()为取整函数,使用该公式可以将GPS点快速定位到所属网格。

网格划分后,就能以网格为单位进行SVM多分类器的训练。对于某些处于网格边缘的样本点,它的匹配路段可能在周围网格内,因此在训练时有必要进行领域网格扩充。训练算法为:从左上角网格开始,依次训练SVM多分类器。对于网格,将邻域网格所包含的路段均加入到训练过程中,使用one-against-one策略学习SVM多分类器i。图4中展示了合肥部分路网的划分情况,为了便于描述,将该部分第一块网格标为1,其他依次类推。依次从网格1开始训练分类器1,在训练多分类器6时,使用第1、2、3、5、6、7、9、10、11网格区域内的路段作为模式样本进行训练。

对于整个路网,使用网格进行划分后,每个网格区域包含路段数远小于总路段数。这样,就避免了同时训练整个路网的所有类别。与不划分网格相比,减少了分类器训练时间和计算资源。

4.2 实时地图匹配

step1得到待匹配FCD记录,其中GPS点的经度为X,纬度为Y,方向角D;

step2获取特征向量F={X,Y,D};

step3根据式(5)在常数时间内得到所属网格gk;

step4使用训练好的SVM多分类器ck,输入特征向量F,得出类别T;

step5将该点匹配为路段编号为T的路段;

5 实验与讨论

实验从合肥市FCD采集系统中选择历史数据,对本文地图匹配算法进行验证。

5.1 实验背景及参数

用于匹配的电子地图采用合肥1:2500比例的GIS地图,网格划分默认为50x50。根据FCD误差分析,分类器采用C-SVC,并使用Gauss核函数:,取核参数。

使用合肥FCD系统采集的2010.01.02 11:00:00~11:05:00数据,采样间隔10秒1次,共18848组FCD记录。使用文献[3]的基于Fréchet距离全局匹配方法得到的匹配结果训练SVM,然后用2010.01.02 11:05:00~11:10:00的人工标记过的FCD进行测试得到匹配准确率。

5.2 训练及匹配结果

高斯核SVM的两个重要参数是惩罚因子C与核函数参数γ,C的作用是调节学习器的推广能力,一般取值范围在[1,10000],γ也会影响学习性能,一般取值范围在[0.01,100]。实验首先固定γ值,对C取不同值进行实验,得出匹配准确率。匹配准确率为:匹配到正确路段上的样本数/样本总数。图5显示了准确率随C的增大而提高,在C>5000后逐渐趋向稳定。图6给出了固定C=6000时,随着核函数参数γ的增大匹配准确率的变化,发现在γ>40后准确率提升趋向水平。

表1给出了四种算法的准确率比较。其中,点到点的方法为文献[2]中的算法1,计算离GPS点最近的路段节点;点到线方法[3]考虑GPS点到各路段的距离,取最近路段作为匹配路段;考虑方向角的点到线算法[2],选择在一定距离内(本文取GPS允许误差15m)方向角与路段方向差最小的路段。本文提出的基于SVM分类匹配算法的匹配准确率较高(表1)。随后我们给出路网网格划分与运行时间、准确率的关系(图7),C和γ同表1取值。我们可以看到在测试范围内,不同网格数对准确率影响不大,但网格数越少,SVM的训练时间越长,这说明一对一的多类SVM在类别多的情况下训练复杂度明显上升。根据实验结果,选择网格划分大于50x50较合适。

6 结论

本文提出了一种新的FCD地图匹配方法,将地图匹配视为分类问题,使用SVM进行多分类学习。为了提高算法性能,减少SVM训练的计算时间,给出了一种有效可行的基于网格划分的多分类器学习策略。实验使用合肥的FCD数据,对SVM的惩罚因子和核函数参数进行调优,最后将本文匹配方法与基于几何信息和拓扑结构(点到点、点到线)的算法进行了比较,确认了较高的匹配准确率。

参考文献

[1]殷伟,郭璘,方廷健,等.一种基于FCD的城市道路车流速度估计算法[J].中国科学技术大学学报.2008,38(9):1113-1117.

[2]White C E,Bernstein D,Kornhauser A L.Some map matching algorothms for personal navigation assistants[J].Transportation Research Part C:Emerging Technologies.2000,8(1):91-108.

[3]Greenfeld J.Matching GPS observations to locations on a digital map[C].Proc.81th Annual Meeting of the Transportation Research Board,Washington,DC,2002.

[4]Brakatsoulas S,Pfoser D,Salas R,et al.On map-matching vehicle tracking data[C]//Proc.21st VLDB Conference,2005:853-864.

[5]Wenk C,Salas R,Pfoser D.Addressing the need for map-matching speed:localizing Globalb curve-matching algorithms[C]//Proceedings of the18th International Conference on SSDBM,2006:379-388.

[6]Diggelen F van.GPS accuracy:Lies,damn lies,and statistics[J].GPS World,1998,9(1):41-45.

[7]Diggelen F van.GNSS accuracy:Lies,damn lies,and statistics[J].GPS World,2007,18(1):Cover Article.

[8]Leick A.GPS Satellite Surveying[M].John Wiley&Sons,Inc.1995.

基于人工免疫分类器的入侵检测方法篇7

入侵检测从计算机网络的若干关键点收集信息,在不影响网络性能的情况下对网络进行检测,从而提供对内部攻击、外部攻击和误操作的实时防护。根据所采用的检测分析技术,入侵检测系统可分为误用检测和异常检测两种。误用检测的分析机制基于攻击方法或攻击特征库建立,目前这种分析机制只能对已知的攻击模式具有检测能力,对未知攻击无能为力。异常检测的分析机制基于正常行为模板建立,这种分析机制对未知的攻击模式具有一定的检测能力[1]。

由于异常检测可以检测未知攻击,因此成为研究热点。这种检测方法必定会采用人工智能算法。国内外学者将各种人工智能算法,如动态贝叶斯网络[2]、模糊支持向量机[3]、小波聚类[4]、遗传算法[5]、人工免疫网络和模糊C-均值聚类[6]等应用到入侵检测领域。

异常检测的难点是正常行为模板的建立,即如何界定正常行为和攻击行为。此一方面问题获得了解决,误报警必然就会减少,因而就能有效实现检测。

建立正常行为模板,其实就是对网络行为进行分类。从这个角度看,入侵检测可以理解为一个分类问题。

1 AIRS算法

生物免疫系统是一种具有高度分布性的自适应学习系统,并具有完善的机制来抵御外来病原体的入侵。人工免疫系统就是受生物免疫系统的启发而设计研发的。因其快速、高效等特点,人工免疫系统正广泛应用到函数优化、分类、图像处理等各个领域[7]。

2002年,Watkins在ai Net网络模型和有限资源人工免疫系统的基础上提出了有限资源人工免疫分类器模型,可简称为AIRS(Artificial Immune Recognition System)[8]。

AIRS算法是一个优秀的人工免疫分类算法,已经在许多公共分类问题数据集合上进行了测试。但迄今该算法在入侵检测领域的应用研究还较少,本文即将该算法应用于入侵检测领域。

AIRS由人工识别球ARB(Artificial Recognition Ball)组成。识别球ARB相当于B细胞,由抗体和识别球所拥有的资源数目及该识别球受到的刺激值组成。在AIRS中,抗体和抗原由一n维的特征向量及该抗体的类别组成。训练针对单个抗原进行,通过刺激度选择最优抗体,并执行抗体竞争,实现记忆抗体种群的进化[9]。

AIRS算法的具体步骤将按如下过程实现。

1.1 初始化

(1)正规化所有的特征向量,使得抗原与ARB或ARB之间的距离均规一化至0到1之间。

(2)计算亲和力阈值。对于固定数目的训练数据集合,亲和力阈值就是亲和力的平均值。如果抗原agi是训练数据集合中的数据,则计算方法如式(1)所示。

式(1)中,函数affinity为特征向量之间的Euclidean距离。

(3)随机地从训练数据集合中选择0个或多个抗原加入记忆细胞集合MC和ARB集合AB中。

1.2 ARB的产生

可根据式(2)找出与抗原ag相同类别的记忆细胞mcmatch,计算公式如下:

在式(2)中,stimulation(ag,mc)=1-affinity(ag,mc),并且如果MCa g.c为空,则将ag加入到集合MCag.c中。

一旦确定了具有最高刺激值的记忆细胞mcm a t c h,就开始利用该记忆细胞产生新的ARB。设

Num Clones=clonal Rate*hyper Clonal Rate*stimulation(ag,mcmatch)。

其中,clonal Rate和hyper Clonal Rate是由用户设定的整数。clonal Rate决定克隆ARB的个数,典型值为10。hyper Clonal Rate是一个乘数,确保了要变异的记忆细胞会比标准的ARB产生更多的新细胞。AIRS克隆Num Clones个记忆细胞mcmatch,并且对每个克隆细胞的特征向量和类别以概率mutation Rate(mutation Rate是一个0~1的用户定义的常数)进行变异,将所有新克隆生成的细胞中发生变异的细胞和记忆细胞mcmatch都加到ARB集合AB中。

1.3 资源的竞争

(1)根据当前抗原ag的刺激进行资源的竞争,找出最大刺激值max stim和最小刺激值min stim。

(2)对于每个ab∈AB,按照式(3)正规化刺激值,其计算公式如下。

(3)对于每个ab∈AB,按照式(4)计算ab的资源。

(4)资源的竞争。竞争过程如下面的代码所示。Procedure资源竞争算法

(5)随机地选择一些获得生存的细胞进行克隆,克隆的数目为clonal Rate*ab.stim。与ARB产生过程中一样,对这些克隆后新生成的细胞的特征向量和类别分别以概率mutation Rate进行变异,并且将发生变异的细胞加入ARB集合AB中。

(6)根据式(5)计算每一类ARB的平均刺激值si(i=1,2,…,nc),如果所有的si不都大于stimulation_threshold(用户定义的常数),则转到本过程的第(1)步。计算公式如下:

1.4 记忆细胞的加入

(1)根据式(6),从与ag相同类别的细胞中找出一个作为候选记忆细胞mccand,并将该候选记忆细胞加入到记忆细胞MC集合中,即,

其公式表示如下:

(2)计算mccand和mcmatch之间的亲和力γ=affinity(mccand,mcmatch)。如果γ小于δ觹η,则将mcmatch从记忆细胞集合MC中删除。δ为初始化时计算的亲和力阈值,η为0到1间的常数。

2 仿真实验及结果分析

2.1 数据处理

1998年,MIT的林肯实验室(MIT Lincoln Laboratory)为DARPA(Defense Advanced Research Projects Agency)进行了一次入侵检测的离线评估活动,使用了人工合成的模拟数据,这就是所谓的DARPA 1998数据集。哥伦比亚大学的Sal Stolfo教授和北卡罗莱纳州立大学的Wenke Lee教授对DARPA 1998数据集作了一些扩展,形成了一个新的数据集。该数据集用于1999年举办的KDD CUP竞赛中,因此被称为KDDCUP 99数据集[10]。

本文选用KDD CUP99数据集来测试AIRS算法的性能。KDD99数据集中每条记录有41个属性,包括34个数值属性和7个分类属性,且均已标识为正常或特定的攻击行为。特定的攻击行为被分为4大类、共39种攻击类型,这4类异常类型为:

(1)DOS:拒绝服务,如TCP同步报文洪泛攻击;

(2)U2R:未授权的本地超级用户特权访问,如缓冲区溢出;

(3)R2L:远端未授权访问,如猜测口令;

(4)PROBING:系统漏洞探测,如端口扫描。

实验从原始的“10percent”样本中选取10 100条记录作为训练数据集,其中正常记录为1 000条,包含DOS、PROBING、R2L这3大类共8种攻击类型的记录为100条。按异常类比为20%、25%、30%分别抽取了测试集1、2、3共9个数据集。测试集1的数据全部来自训练数据集,而测试集2、3的数据都是从原始的剔除训练数据集的“10percent”和“corrected”的样本中选取出来的,包含训练数据集中的8种已知攻击类型,同时又增加了涵盖了4大类的10种未知攻击类型,且测试集3中未知攻击的比例要大于测试集2。

数据集中每一条记录有41个属性,文献[11]指出KDD99数据集的每条记录中有13个属性最为重要。这13个属性中,11个为数值属性,2个为分类属性。在本实验中,即选用这13个关键属性。

AIRS是利用Euclidean距离计算亲和力,而用实数值向量测试分类并不方便,就需要将分类属性转化为数值属性。处理方法是对其进行编码,对于有m种不同取值的分类属性,利用十进制的编码方法,第i种属性对应的编码就是i。例如,属性protocol_type协议类型有3种取值,分别编码为:TCP 0,UDP 1,ICMP 2;属性service目标主机的网络服务类型有70种取值,用十进制编码是0~69。因此对于属性取值种类多的情况,采用十进制编码较为有利,因其不会带来输入矢量过大的问题。数据集中的39种攻击类型也因而采用十进制进行编码,编码范围是0~38。

2.2 参数设置

本实验对AIRS的重要参数设置如下:MC和AB为空;Cloning Rate为11;Mutation Rate为0.1;Resource Allocation Rate为10;Number of Resources Used为300;KNN Value为3;Hyper Clonal Rate为10.0;Stimulation Threshold为0.8;η为0.2。

2.3 分类器性能测试

文献[6]提出的Ai Net_FCM算法是目前最好的入侵检测方法之一。为了检测本文提出的AIRS算法的入侵检测性能,将其与文献[6]提出的Ai Net_FCM算法进行对比实验。

本文对不同异常类比的测试集1、2、3进行测试,统计其各自的检测率和误警率。表1是AIRS算法对不同的异常类比N的实验结果;表2是Ai Net_FCM算法对不同的异常类比N的实验结果。表1和表2中,N代表异常类比,D1、D2和D3分别代表测试集1、测试集2和测试集3的检测率,E1、E2和E3分别代表测试集1、测试集2和测试集3的误警率。

对比表1和表2,对于全部来自训练数据的测试集1,AIRS算法的检测率高于Ai Net_FCM算法8-10个百分点,同时误警率要低0.8-1.5个百分点。对有未知攻击的测试集2、3的测试中,AIRS算法的检测率远远高于Ai Net_FCM算法,最高的达到15个百分点,同时误警率要低0.4-0.8个百分点。因此,无论是检测已知攻击还是未知攻击,本文的AIRS算法性能都比Ai Net_FCM算法性能优越。

在异常类比N为25%时,AIRS算法和Ai Net_FCM算法的整体性能较好,固定此阈值来测试算法对未知攻击的检测性能。表3是当异常类比N为25%时,AIRS算法对测试集2和测试集3进行的未知入侵检测。表4是当异常类比N为25%时,Ai Net_FCM算法对测试集2和测试集3进行的未知入侵检测。表3和表4中,T代表攻击类型,K2和K3分别代表测试集2和测试集3的已知攻击,U2和U3分别代表测试集2和测试集3的未知攻击。

对比表3和表4可知,Ai Net_FCM算法对Do S和Probing的已知和未知攻击的入侵检测效果都已很好,而AIRS算法对Do S和Probing入侵的检测率却已近于100%。在Ai Net_FCM算法对U2R和R2L的检测效果并不算理想时,AIRS算法则是大幅度提高了对U2R和R2L的检测率。

3 结束语

采用KDD CUP99数据集对本文的方法进行测试,并将检测结果与文献[6]进行对比。测试结果表明,AIRS算法在保持高检测率的同时,降低了误警率,对于未知入侵表现出很好的识别能力。

AIRS是一种有监督的机器学习算法,并且具有学习过程简单,模式分类能力强,分类准确率较高,训练速度快等一系列优点,将人工免疫分类器用于入侵检测这种分类准确率、实时性和检测率要求均会很高的系统,则是一种具备实践应用前景的设计方案。

参考文献

[1]胡昌振.网络入侵检测原理与技术[M].北京:北京理工大学出版社,2006.

[2]FENG L,WANG W,ZHU L,et al.Predicting intrusion goalusing dynamic Bayesian network with transfer probability esti-mation[J].Journal of Network and Computer Applications,2-009,32:721-732.

[3]荆春伟,李永忠,曹传林.模糊支持向量机在入侵检测中的应用研究[J].计算机仿真,2011,28(7):132-134,153.

[4]李云,刘学诚.小波聚类算法在入侵检测中的应用[J].计算机应用与软件,2010,27(6):103-104,125.

[5]郭慧玲,唐勇,张冬丽.遗传算法在入侵检测规则提取中的应用[J].哈尔滨工业大学学报,2009,41(1):248-250.

[6]李丽娟,唐文纪.基于人工免疫网络和模糊C-均值聚类的入侵检测方法[J].计算机应用与软件,2011,28(3):282-284,299.

[7]邓泽林,谭冠政,范必双,等.免疫分类研究进展[J].计算机工程与应用,2011,47(16):8-11.

[8]WATKINS A B,BOGGESS L C.A resource limited artificialimmune classifier[C]//Proceedings of the Congress on Evolutio-nary Computation,Part of the 2002 IEEE World Congress onComputational Intelligence.Honolulu,HI,USA,2002-05:926-2-05:926-931.

[9]李涛.计算机免疫学[M].北京:电子工业出版社,2004.

[10]http://www.ll.mit.edu/mission/communications/ist/corpora/idev-al/data/index.html

基于原型分类器篇8

分类方法已经被广泛应用在预测领域,但大多数的分类方法都要求各种类型的数据具有较为均匀的分布。若一种类型的数据与另一种类型的数据严重不均衡,少数类数据就有可能被当作噪声处理掉。现实世界中的数据集却往往呈现不均衡分布的特点,即其中一种类型的数据占绝大多数,另一种类型的数据只有为数不多的几个样本。然而,在一些特殊的情况下这些少数类样本却是人们更加关注的。例如,医生需要关注罕见疾病的诊断,银行信用卡中心需要辨别少数欺诈用户,电信运营商需要辨别少数缺乏信用恶意欠费的用户等等。

由于数量上的严重偏斜,运用常见的分类算法对非平衡数据集进行分类的性能不尽如人意,因为当对非平衡数据集进行训练时,其训练算法通常对多数类样本会产生很高的预测准确率,但是对少数类样本的预测准确性却很差。解决非均衡数据集分类难题的途径,可以粗略地分为两个方向: 一个方向是对数据进行采样处理; 另一个方向是算法设计。数据采样处理又进一步分为两种方法:一种是减少多数法(under-sampling),即减少多数类样本的数量[1,2]; 另一种是增加少数法(over-sampling),即通过复制或插值等方法增加少数类样本的数量[3]。算法设计则主要以线性Logistic回归(LLReg)、决策树(DT)、多层感知器神经网络(NN)、贝叶斯网络(Bnet)、多项Logistic回归、支持向量机(SVM)以和AdaBoost推进算法等为基础,适当予以修正,以尽量适应数据不均衡的特征[4]。

近年来,机器学习领域的一个重要进展是集成的办法,即通过集成多个精度不是很高的分类器来提高整体分类预测的精度。目前,主要运用Boosting和Bagging两种技术构建集成分类器。AdaBoost是一种最常见的Boosting方法, 在每次迭代中, 增加没有正确分类样本的权值, 减少正确分类样本的权值,更加关注于分类错误的样本。因少数类样本更容易被错误分类, 所以有理由相信该方法能够改进对少数类的预测性能。SMOTE技术(synthetic minority over-sampling technique)是非均衡数据集学习的一种新办法, 通过对少数类样本的人工合成提高少数类样本的比例, 降低数据的过度偏斜。SMOTE技术与AdaBoost结合,可有效避免由于赋予少数类样本更大权值而可能产生的过度拟合。SVM具有较强的泛化能力,以RBF为核参数的SVM,只需选择C和σ两个参数,并且选择一个大体合适的C后,通过调节σ,即可改善向量机的性能。

本文将以SVM作为弱分类器,并将SMOTE技术嵌入AdaBoost算法中, 建立非均衡数据集分类模型。研究结果表明:SMOTEBoostSVM集成分类器比单纯运用SMOTE技术、AdaBoost算法、SVM等的分类器,在非均衡数据集的分类预测中具有更好的效果。

2 算法模型

2.1 AdaBoost分类器

AdaBoost算法[5]的基本思想是通过训练一组分量分类器,将多个弱分类器集成为一个强分类器。在训练过程中,每个训练样本被赋予一个初始权值,当一个弱分类器训练完成后,根据其在训练集上的分类结果对所有的样本权值进行调整,使得下一次训练的弱分类器更关注那些被识别错误的样本。最后的强分类器的判决结果是所有弱分类器判决结果的加权和。AdaBoost算法的基本流程为:

(1)输入:标定的训练样本集,(x1,y1),(x2,y2),…,(xm,ym),其中:xi∈X,yi∈Y={-1,+1};

(2)对样本权值进行初始化,w1(i)=1/m;

(3)循环t=1,2,…,T;

①在加权训练样本集上用弱学习算法训练弱分类器Ct得到ht,或训练使用按照wt(i)采样的弱分类器Ct得到ht;

②计算Ct的训练误差εt: $ε_{t} = \sum_{h_{t} (x_{i}) \neq y_{i}} w_{t} (i)$ ;

③求弱分类器Ct的权值: $α_{t} = \frac{1}{2} \ln \frac{1 - ε_{t}}{ε_{t}}$ ;

④更新训练样本的权值:

$w_{t + 1} = \frac{w_{t} (i) \exp (α_{t} y_{i} h_{i} (x_{i}))}{Ζ_{t}} = \frac{w_{t} (i)}{Ζ_{t}} \cdot {\begin{cases} e^{- α_{t}}, \\ e^{α_{t}}, \end{cases} \begin{array}{l} h_{t} (x_{i}) = y_{i} \\ h_{t} (x_{i}) \neq y \end{array}$

其中:Zt为归一化因子,即 $Ζ_{t} = \sum_{i} w_{t} (i) e^{- α_{t} y_{i} h_{t} (x_{i})}$ 。

(4)输出:最后的强分器 $Η (x) = s i g n (\sum_{t = 1}^{Τ} α_{t} h_{t} (x))$ 。

2.2 SMOTE增加少数样本法

增加少数样本法是通过增加数据集中少数类样本的办法,降低类别之间分布的不平衡程度。早期的增加少数法是直接复制少数类样本,以增加其数量。DeRouin等通过神经网络技术, 用仿制取代复制, 以期减少少数类信息的缺失。Chawla则沿用仿制的思路, 提出了少数类信息的仿制技术SMOTE(synthetic minority over-sampling technique)[6]。

设少数类的样本数为T,增加样本后样本增长n倍,最近邻点数为k,SMOTE方法主要处理步骤如下:

(1)计算数据集中每个少数类别的k个最近多数类邻点;

(2)随机抽出少数类样本i的k个最近多数类邻点中的一个多数类样本j;

(3)计算少数类样本i与最近多数类邻点样本j的全部属性差值dif:

$d i f = n n s a m p l e [j] [a t t r] - s a m p l e [i] [a t t r]$

其中:nnsample[][]指最近的多数类邻居样本,sample[][]指少数类样本。

(4)产生一个介于0与1之间的随机数;

(5)生成少数类的合成样本Synthetic[l][attr]:

$S y n t h e t i c [l] [a t t r] = s a m p l e [i] [a t t r] + g a p \cdot d i f$

(6) 重复步骤(2)～(5),直至产生少数类样本i合成n倍个样本为止;

重复步骤(2)～(6),直至所有少数类样本均处理完毕为止。

2.3 支持向量机

支持向量机(support vector machine,SVM)是在统计学习理论基础上发展起来的新型通用分类和回归工具,较好地解决了小样本、非线性、高维数、局部极小点等实际问题,已在模式识别、信号处理、函数逼近等领域得到了较好应用,但是当应用于一种类型数据远多于另一种类型数据的非平衡数据集时,对于少数类的分析性能会急剧下降,分析其原因,主要包括:一是少数类点远离理想分界面,造成训练出的分界面向少数类偏斜;二是非平衡的支持向量比率,使得接近于边界的点更可能被归为多数类[7]。因此,要提高支持向量机对非平衡数据集的分类性能,可从平衡数据和向多数类方向推动分界面着手。

对于一个给定的训练数据集(xi,yi), i=1,2,…,n, xi∈Rd, yi∈R, 其中n为样本总数, d为R空间维数。给定一核函数K,支持向量机通过训练为每一个xi搜索最优的αi,使得分界面与最接近分界面的点之间的距离γ最大。对测试点通过式予以判别分类:

$s i g n (f (x) = \sum_{i = 1}^{n} y_{i} α_{i} Κ (x, x_{i}) + b) (1)$

其中: b为常数阈值。1-范数软边际支持向量机以最小化下列Lagrangian函数予以修正:

$\begin{array}{l} L_{p} = \frac{∥ w ∥^{2}}{2} + C \sum_{i = 1}^{n} ξ_{i} - \sum_{i = 1}^{n} α_{i} [y_{i} (w_{i} x + b - 1 + ξ_{i})] \\ - \sum_{i = 1}^{n} r_{i} ξ_{i} (2) \end{array}$

其中:αi≥0,并且ri≥0,惩罚系数C代表着误差与边际之间的一个折衷[8]。为满足KKT条件,还须满足:

$\sum_{i = 1}^{n} α_{i} y_{i} = 0 且 0 \leq α_{i} \leq C (3)$

2.4 SMOTEBoostSVM集成算法

本文提出的SMOTEBoostSVM集成算法的基本思想是:先运用SMOTE技术合成少数类样本,改善数据的偏斜状况,然后用AdaBoost算法集成多个SVM分类器,从而达到非均衡数据集上更好的分类效果与模型泛化能力。SVM常以RBF为核函数,只需确定C和σ两个参数,并且根据文献[9]可知,尽管当C值过小时,难以训练出好的RBFSVM,但当给出一个大致合适的C值后,训练效果将决定于σ.因此,本文选择RBFSVM作为弱分类器,一方面可简化模型参数的选择; 另一方面,仅调节σ,可实现AdaBoost算法在分类器分类精度与差异性之间的合理平衡。算法的具体流程如下:

(1)输入:标定的训练样本集,(x1,y1),(x2,y2),…,(xm,ym),其中:xi∈X,yi∈Y={-1,+1};RBFSVM的参数σ初始值σini,σ的最小值σmin,以及步长σstep;最大循环次数T;

(2)对样本权值进行初始化,w1(i)=1/m;

(3)当σ>σmin且t<T时循环:

① 用SMOTE算法生成N个少数类样本;

② 在加权训练样本集上用RBFSVM算法训练弱分类器Ct得到ht;

③ 计算Ct的训练误差εt: $ε_{t} = \sum_{h_{t} (x_{i}) \neq y_{i}} w_{t} (i)$ ;

④ 如果εt>0.5,令σ=σ-σstep,t=1,返回至②;

⑤ 求弱分类器Ct的权值: $α_{t} = \frac{1}{2} \ln \frac{1 - ε_{t}}{ε_{t}}$ ;

⑥ 更新训练样本的权值:

⑦ 令t=t+1。

(4)输出:最后的强分器 $Η (x) = s i g n (\sum_{t} α_{t} h_{t} (x))$ 。

3 实例分析

3.1 实验数据

本文使用2组数据对算法进行检验, 并与SVM、AdaBoost、SMOTE方法进行比较。这2组数据皆来源于UCI机器学习数据库,数据的特征信息见表1,数据集名称后的数字表示选择作为少数类的类型代码。

3.2 评估指标

评价分类器性能最直接的办法是基于混淆矩阵的分析。表2列示了二类分类问题的混淆矩阵。通过该矩阵,可能定义常用的错分率、正确率等指标,即:错分率 $E r r = \frac{B + C}{A + B + C + D}$ ,正确率 $A c c = \frac{A + D}{A + B + C + D} = 1 - E r r$ 。但是,由于非均衡数据集的特性,使用上述两个指标(实质上是一个指标)评价分类器的性能并不合适。例如,如果少数类与多数类的比率达到1∶99,那么,即使将所有未知类型的数据归为多数类,那么分类准确率即可达到99%以上,而这样的评价指标对于少数类的分类而言没有任何意义。因此,对非均衡数据集的分类通常引入以下几个指标:

少数类正确率:TP=Pr{predicted P|actually $Ρ} = \frac{A}{A + B}$

多数类正确率:TN=Pr{predicted N|actually $Ν} = \frac{D}{C + D}$

几何平均正确率: $g = \sqrt{Τ Ρ \cdot Τ Ν}$

精确率(Precision,p): $p = \frac{A}{A + C}$

召回率(Recall,r): $r = Τ Ρ = \frac{A}{A + B}$

F-measure: $f = \frac{2 p r}{p + r}$

3.3 结果评价

对Abalone数据集,以第19类作为少数类,其余类型统归为多数类,分别运用SVM、AdaBoost、SMOTE-Boost以及本文提出的SMOTEBoostSVM方法,以前3177点数据进行训练,对后1000点数据进行预测,实验结果如表3所示。

对Letter-recognition数据集,以第26类作为少数类,其余类型统归为多数类,分别运用SVM、AdaBoost、SMOTE-Boost以及本文提出的SMOTEBoostSVM方法,以前18000点数据进行训练,对后2000点数据进行预测,实验结果如表4所示。

实验结果表明:运用本文提出的SMOTEBoostSVM算法,能够在运用SMOTE技术人工合成少数类样本,以及AdaBoost算法增加分类错分样本权重,提高少数类样本预测精确性的同时,借助支持向量机的强泛化能力,能够减少、甚至可不损害对多数类的预测精度,可明显地改善非均衡数据集的分类性能。

4 结语

为解决非均衡数据集训练中易出现的偏斜问题, 提高模型的分类预测精度, 支持向量机、 SMOTE技术、 AdaBoost算法等都具有一定的效果,但目前研究方法的趋势是各种方法的集成。本文将上述几种方法加以集成,提出了SMOTEBoostSVM集成算法, 该算法集成了SMOTE技术、AdaBoost算法,并以SVM为弱分类器。实验结果表明该方法能够有效改进对非均衡数据集分类问题的预测效果。

摘要：在对实际问题进行数据挖掘时面临的多数是非均衡数据集,即各种类型的数据分布并不均匀,且关注的类型常是少数类。运用含有少量少数类型事例的数据集训练后的模型进行预测时,通常对多数类的预测精度很高,而少数类的预测精确性却很差。提出了一种集成方法SMOTEBoostSVM,通过SMOTE技术人工生成增加少数类样本量,以具有较强分类性能和泛化性能的SVM作为弱分类器,并以AdaBoost算法构建集成分类器。实验结果表明,SMOTEBoostSVM集成分类器比单纯运用SMOTE技术、AdaBoost算法以及SVM等的分类器,在非均衡数据集的分类预测中具有更好的效果。

关键词：SMOTE,AdaBoost,支持向量机,非平衡数据集

参考文献

[1]Kubat M,Holte R C,Stan M.Machine learningfor the detection of oil spills in satellite radar im-ages[J].Machine Learning,1998,30(2):195~215.

[2]Randall W D,Martinez T R.Reduction techniquesfor instance-based learning algorithms[J].MachineLearning,2000,38(3):257~286.

[3]Guo H Y,Viktor H L.Learning from imbalanceddata sets with boosting and data generation:the da-ta boost-IM approach[J].SIGKDD Explorations,2004,6(1):30~39.

[4]Daskalaki Sophia,et al.Evaluation of classifiers foran uneven class distribution problem[J].AppliedArtificial Intelligence,2006,20(5):381~417.

[5]Yoav F,et al.A short introduction to boosting[J].Journal of Japanese Society for Artificial intelli-gence,1999,14(5):771~780.

[6]Chawla N,et al.SMOTE:synthetic minority over-sampling Technique[J].Journal of Artificial Intel-ligence Research,2002,16:321~357.

[7]Wu G,Chang E Y.Class-boundary alignment forimbalanced dataset learning[A].ICML 2003 Work-shop on Learning from Imbalanced Data Sets II[C].Washington,D.C.,2003.

[8] Cristianini N, Shawe-Taylor J. An introduction to support vector machines and other kernel-based learning methods[M]. Cambridge,UK:Cambridge University Press,2000.

本文来自 360文秘网(www.360wenmi.com)，转载请保留网址和出处

【基于原型分类器】相关文章：

一种基于概念格的复合分类器算法09-11

基于相反分类器的数据流挖掘方法分析09-11

原型05-06

虚拟原型技术05-08

荣格原型理论05-23

原型设计论文范文05-09

原型设计论文提纲11-15

孟晓骏原型04-28

新文化原型05-03

原型与意义推断论文04-15