文本分类器

文本分类器（精选7篇）

文本分类器 篇1

0 引 言

文本分类是网页自动分类的基础。由于当前绝大部分采用向量空间模型标引文本,直接采用词条作为特征项形成特征集,而这些高维的特征集对分类未必全是重要的和有效的。特征降维,也叫属性约简,或特征集缩减,通过特征选择或特征抽取达到降低特征空间维数、提高计算效率的目的,是文本分类的一个关键步骤。目前常用的属性约简算法分为两大类[1]:一类是基于评估函数的特征选择,主要有信息增益、互信息、统计量、期望交叉熵等[2],研究资料显示:没有哪一种降维方法对分类效果具有绝对优势[3];另一类是特征抽取,包括潜在语义索引等[4],这类方法很少丢失原特征空间的信息,但计算复杂度高,在大规模数据集上难以实现。

文本特征矢量的约简过程实质上是从大量候选特征中找出代表问题空间的最小特征子集的寻优过程,可归结为0-1组合优化问题。受进化算法成功解TSP等组合优化难题的启发,很多学者将进化算法运用到属性约简中,如基于遗传算法[5] 、蚁群算法[6]、粒子群算法[7]的属性约简等,这些算法都是基于VSM,其词条集不能完全、准确地反映文本内容(语义),分类精度不是很理想[8]。本文提出一种基于概率潜在语义分析PLSA和自适应广义粒子群算法AGPSO的文本属性约属方法:首先用PLSA将隐含语义体现于向量空间中,并通过最大期望算法EM得到中间特征子集,在此基础上再用ADPSO算法继续降维。实验结果表明此方法效果良好。

1 概率潜在语义分析

概率潜在语义分析通过计算文档中共现词的分布来分析文档语义,用概率模型表示“文档—潜在语义—词”间的关系,文档和词可映射到同一语义空间,多义词和同义词均可得到合理表示。通过计算语义空间中的夹角而量化文档和词间的相似度。在计算模型方面,PLSA使用EM算法迭代求解,大大降低了时间复杂度[9]。

给定文档集D={d1,d2,…,dM}、词集合W={w1,w2,…,wN}及文档和词的共现频率矩阵N=(nij)i,j,其中n(di,wj)表示词wj在文档di中出现的频率,Z={z1,z2,…,zK}表示潜在语义集合,K为指定常数。假设文档—词对和潜在语义在文档或词上分布是条件独立的, 则词—文档的条件概率可表示为:

${\rm P}(d{}_i,w{}_j)={\rm P}(d{}_i){\displaystyle \sum _{k=1}^{{\rm K}}{\rm P}}(w{}_j|z{}_k){\rm P}(z{}_k|d{}_i)(1)$

其中P(wj|zk)为潜在语义在词上的分布概率或词对潜在语义的贡献度,排序P(wj|zk)可得到词的潜在语义的一个直观表示;P(zk|di)表示文档中的潜在语义分布概率。

PLSA用EM算法对潜在语义模型进行拟合。随机初始化后交替实施E步骤和M步骤,在E步骤,计算每一个(di,wj)对产生潜在语义ZK的先验概率:

${\rm P}(z{}_k|d{}_i,w{}_j)=\frac{{\rm P}(w{}_j|z{}_k){\rm P}(z{}_k|d{}_i)}{{\displaystyle \sum _{{\rm I}=1}^{{\rm K}}{\rm P}}(w{}_j|z{}_{{\rm I}}^{}){\rm P}(z{}_{{\rm I}}|d{}_i)}(2)$

在M步骤中,使用下列两式对模型重新估计:

${\rm P}(w{}_j|z{}_k)=\frac{{\displaystyle \sum _{i=1}^{{\rm N}}n}(d{}_i,w{}_j){\rm P}(z{}_k|d{}_i,w{}_j)}{{\displaystyle \sum _{m=1}^{{\rm M}}{\displaystyle \sum _{i=1}^{{\rm N}}n}}(d{}_i,w{}_m){\rm P}(z{}_k|d{}_i,w{}_m)}(3)$

${\rm P}(z{}_k|d{}_i)=\frac{{\displaystyle \sum _{j=1}^{{\rm M}}n}(d{}_i,w{}_j){\rm P}(z{}_k|d{}_i,w{}_j)}{n(d{}_i)}(4)$

当期望值的增加量小于阈值时停止迭代,即可认为达到最大值,并获得最优解:

$E(L)={\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm M}}n}}(d{}_i,w{}_j){\displaystyle \sum _{k=1}^{{\rm K}}{\rm P}}(z{}_k|d{}_i,w{}_j)\log n[p(w{}_j|z{}_k){\rm P}(z{}_k|d{}_i)](5)$

2基于自适合广义粒子群算法的文本特征降维

针对传统粒子群算法局限于速度—位移更新算子,不能有效拓展到离散及组合优化领域,文献[10]中提出了广义粒子群算法:在保留粒子群算法核心思想的基础之上,利用交叉操作描述粒子当前解的变化,粒子的历史最优位置和种群全局最优位置对粒子当前位置的影响通过交叉操作来实现;加入变异操作增加种群的多样性,提高局部搜索能力,从而解决了由于组合优化问题解空间的限制而导致粒子速度难以表达的难题。

2.1 算法分析

Web文本是由众多特征词条构成的多维信息空间,文本属性约简过程实质上是计算机在难以获得相应的语法、语义和语用知识前提下的寻优过程。从大量候选特征中找出代表问题空间的最优特征子集可归结为0-1组合优化问题。广义粒子群算法是基本粒子群算法在解决组合优化问题时的推广,应用到文本特征选择问题上来具有良好前景和实施可能性。由于原始特征空间维数一般很高,若直接用粒子群算法约简,粒子编码过长,搜索空间太大,影响算法的有效性和实用性,而且可能收敛到分类性能较差的局部最优解。因此先用概率潜在语义分析降维,得到中间特征子集,再用广义粒子群算法约简,以保证所选特征子集的组合最优化。

2.2 粒子编码和初始种群的生成

通过概率在语义分析生成的中间特征子集剔除了大部分不相关特征,特征项的个数已大大减少,适合采用二进制编码,即用二进制基因位表示所选特征子集的特征,0表示没被选用,1表示被选用。以粒子群对应特征词集,每个粒子代表不同候选特征子集,文本集中每个特征属性对应粒子不同维度。初始种群用随机函数生成,形成初始矩阵,其中每一行代表一个特征粒子,每一行中的每个元素代表一个特征,矩阵的行数代表种群中粒子的数目,列数代表文本集的特征维数。

2.3 适应度函数的构造

综合分析文本降维的特点,要求特征子集必须在一定程度上代表该文本类别,能将该文本同其他文本区分开,且特征向量的维数应尽可能少,因此适应度函数设计为:

$fitness(x{}_i)=\alpha \times \overline{\omega }{}_i+\beta \times sim(x{}_i)+\gamma \times \frac{zero\_num(x{}_i)}{n}(6)$

这里,α、β、γ为权重系数,且α+β+γ=1,实验时取α=0.7,β=0.2,γ=0.1。词条平均权值$\overline{\omega }{}_i=\frac{1}{n}{\displaystyle \sum _{k=1}^n\omega }{}_{ik}$越大,特征子集越能代表文本类别;通过类内相似度$sim(x{}_i)=\frac{|sim\_num(x{}_i)|}{m}$来度量区分度(sim_num(xi)={set(xj)|j≠i∧sim(xi,xj)≥θ},sim_num(xi)为与xi相似度超过阈值θ的粒子数,sim(xi,xj)表示粒子xi和xj的相似度);zero_num(xi)表示粒子xi中0的个数,“0”的数目越多,特征数目越少,分类性能越好。

2.4 自适应策略

为使GPSO算法兼顾全局与局部寻优,既加强局部搜索能力,又避免早熟现象,本文采用自适应方法动态调节变异概率pm,使pm随适应值大小自动改变。当种群各粒子适应值趋于一致或趋于局部最优时,pm增加;而当群体适应值比较分散时,pm减少。同时对于适应值高于群体平均适应值的个体,对应于较低的pm,使该解得以进入下一代;而低于平均适应值的个体,对应于较高的pm使该解被淘汰。变异概率pm计算表达式如下:

$p{}_m=\{\begin{array}{l}p{}_{m1}-\frac{(p{}_{m1}-p{}_{m2})(f{}_{\max }-f)}{f{}_{\max }-f{}_{\text{a}\text{v}\text{g}}}f\ge f{}_{\text{a}\text{v}\text{g}}\\ p{}_{m1}f＜f{}_{\text{a}\text{v}\text{g}}\end{array}(7)$

式中pm1=0.1,pm2=0.001,fmax为要交叉的两个粒子中较大的适应度值,f为要变异粒子的适应度值,favg是每一代群体的平均适应度。

为了提高算法的寻优能力,实现算法平衡,本文引入模拟退火机制有选择地更新gBest。在算法运行初期,由于粒子群具有较高的变异概率,粒子群可依靠自身动态变化跳出局部极值点,模拟退火概率较高。随着算法的运行,粒子群跳出局部极值点的能力越来越弱,此时模拟退火概率应较小,以克服早熟收敛现象。本文采用的模拟退火概率见式(7)。适应度值增加时接受该解作为下一个当前解;否则以概率Pr接受该解。

${\rm P}{}_r=\{\begin{array}{l}1f{}_{i+1}＞f{}_i\\ \exp \left(\frac{f{}_{i+1}-f{}_i}{{\rm T}}\right)f{}_{i+1}＜f{}_i\end{array}(7)$

其中fi+1为子个体的适应值,fi为父个体的适应值,温度T随算法进程递减,其值由控制参数担当。

2.5 算法设计

本文运用AGPSO模型在解决文本特征约简问题时以遗传操作为粒子更新算子,在此基础上进行特征降维。

输入:概率潜在语义分析约简后的中间词条子集。

输出:特征词。

Step1 随机选择种群规模为n的中间特征词条子集,保证一定的分布性。

Step2 初始化每个粒子的最优位置并计算群体最优位置。

Step3 个体极值的更新。根据粒子适应度更新个体极值,比较当前与前代粒子的个体极值。若当前值优于前代值,更新个体极值;否则保持个体极值不变。

Step4 全局极值的更新。根据粒子适应度更新全局极值。

Step5 粒子与个体极值交叉。粒子以给定概率与个体极值交叉,实现个体极值获得更新信息的目的。本文采用两点交叉,即交换两个粒子的维中间部分,产生相应后代。

Step6 粒子与全局极值交叉。粒子以一定概率与其全局极值交叉,具体过程与Step5类似。

Step7 粒子自身的动态变异。用基于概率的变异进行随机或局部搜索,以实现算法随机搜索与局部搜索的平衡。本文对粒子以变异率Pm选择其中一个维(特征)发生突变,如由“0”变为“1”,同时随机选择另一值为“1”的维发生相反的突变,即加入一个特征同时剔除一个特征,反之变然。

Step8 计算粒子适应值的变化量△E,若模拟退火概率Pr>random,则接受新位置;否则保持不变。

Step9 算法停止条件。评价更新后的粒子种群,若达到最大迭代次数或在指定迭代次数内解无明显改进,算法停止,输出群体最优位置和对应的目标函数值;否则,返回Step3。

3 基于PLSA+AGPSO的网页分类器设计

本文通过引入已有的分类算法如KNN算法,设计并实现了一个基于PLSA和AGPSO的网页文本分类器。网页分类器的构建包括二部分:训练器和分类器,启动后首先进行训练,然后再进行分类。分类器流程图如图1所示。

首先根据应用需求建立专用词典;从Web通过常用搜索引擎采集网页,人工分成不同的类别,每个网页只属于一个类,并以此为分类标准判别分类准确性,取其中一部分建立训练语料库;利用词典词条对训练语料库进行词条切分、词频统计等预处理工作,生成训练语料库的特征向量表;利用本文PLSA+AGPSO属性约简方法实现降维:首先用PLSA将维数降到几十至一百维,再用AGPSO继续约简;对降维后的特征向量矩阵运用常用分算法,如KNN算法进行分类,达到满意效果后,得到特征项向量类列表,并与预先确定每个类的最优截尾阈值作为分类知识存储,从而完成训练器的工作。分类器训练完后即可对待分类网页进行分类,其过程和训练过程大致相同,首先进行分词等预处理工作得到待分网页的特征向量,运用PLSA+AGPSO算法降维后用KNN等分类算法分类并比较各类阈值得到结果类别表。

4 实验结果

从搜狐、雅虎和新浪上采集的网页人工分为人文艺术、体育、计算机、科技教育、财政金融共五类作为分类类别,从中选取1000个网页,随机分为680个训练集和320个测试集,每个网页只属于一个类别。首先将数字和标点用空格代替,然后去掉高频率词;使用在国际上广泛获得好评的中文分词系统ICTCLAS(中科院计算所汉语词法分析系统)分词,得到18321个词条。本文实验所用分类算法为KNN,需预先确定每个类的最优截尾阈值,选用RTCut阈值策略[11]。属性约简后经KNN分类器分类,比较五个类别的F1测试值和宏平均F1测试值,实验结果如图2、图3所示(其中横坐标1:人文艺术;2:体育;3:计算机;4:科技教育;5:财政金融)。

从以上实验结果可得出如下结论:

1) 对于类别特征不明显的类效果不太好。因为经过权值离散化和特征提取后,丢失了文本特征项的一些细节信息,如体育类效果最好是因为在该类分类歧义较少,界限较清晰,文本特征较明晰,离散化后丢失的信息较少。

2) 使用互信息评估函数进行特征降维的平均分类精度最差(55.6%),这个测试结果恰恰和文献[12]中的测试结果相一致。

3) 使用PLSA+GPSO算法进行特征属性约简,得到的分类精度有明显的提高,例如:在体育类F1测试值提高了13.5%,宏平均F1提高了12.9%。

5 结束语

文本属性约简是网页分类的重要步骤,实质是一个组合优化问题。本文将概率潜在语义分析和自适应广义粒子群算法相结合进行文本属性约简:应用概率潜在语义分析理论, 将隐含语义体现于向量空间中,并通过EM算法大大降低向量的维数;得到中间特征子集,再用自适应广义粒子群算法继续降维:用二进制字符串序列表示粒子位置,解释了位置和速度的更新方法以及适应度函数的选择,同时引入自适应策略,动态调节变异概率,避免算法早熟,进而获得较理想的特征子集。这样充分发挥两者的优势,大大降低向量的维数, 并提高分类的速度和精度。实验结果表明,该算法有较高查全率和查准率。

摘要：将概率潜在语义分析PLSA(probabilistic latent semantic analysis)和自适应广义粒子群算法AGPSO(adaptive general particle swarm optimization)相结合,提出了一种文本特征降维新方法,进而实现了基于PLSA和AGPSO的网页分类器。采用概率潜在语义分析将语义关系体现在VSM(Vector Space Model)中,通过EM算法有效地降低向量空间的维数;设计交叉操作模拟粒子飞行速度的变化,变异操作保持种群的多样性,同时引入自适应策略动态调整变异概率,以求最优特征子集。在用自适应广义粒子群算法约简前,先用概率潜在语义分析对原始特征空间约简,得到中间特征子集,然后再用自适应广义粒子群算法继续约简,充分发挥两者的优势。实验表明此算法能有效降低文本维数,提高分类精度。

关键词：网页分类,属性约简,广义粒子群,概率潜在语义分析,自适应策略

参考文献

[1]Dunija Mladenic,Marko Grobelnik.Feature selection on hierarchy of web documents[J].Decision Support Systems,2003,35:45-87.

[2]Yiming Y,Pedersen J O.A comparative study on feature selection in text categorization[C]//Proceedings of the14th International Confer-ence on Machine Learning(ICML97),1997:412-420.

[3]Zhihua,Zhou KaiJiang,Ming Li.Multi-instance learning based web mining[J].Applied Intelligence,2005,22:135-147.

[4]Lin J,Gunopulos D.Dimensionality Reduction by Random Projection and Latent Semantic Indexing[C]//Text Mining Workshop at the3rd SIAMInternational Conference on Data Mining,2003:301-309.

[5]Oh I S,Lee J S,Moon B R.Hybrid genetic algorithms for feature selec-tion.IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(11):1424-1437.

[6]LKe e.An efficient ant colony optimization approach to attribute reduc-tion in rough set theory.Pattern Recognition Lett.2008,2(6):2231-2241.

[7]吴永芬,杨明.基于ACO及PSO的特征选择算法[J].江南大学学报:自然科学版,2007,6(6):758-761.

[8]盖杰,王怡,武港山.基于潜在语义分析的信息检索[J].计算机工程,2004,30(2):58-60.

[9]Hofmann T.Unsupervised Learning by Probabillistic Latent Semantic analysis[J].Machine Learing,2001,42(1):177-196.

[10]Gao HaiBing,Zhou Chi,Gao Liang.General Particle Swarm Optimiza-tion Model[J].Chinese Journal of Computers,2005,28(12):1980-1987.

[11]刘勇国,李学明,张伟,等,基于遗传算法的特征子集选择[J].计算机工程,2003,22(6):19-20.

[12]AMIR Z O,Grouper O E.A dynamic clustering interface to web search results[J].Computer Networks:the international Journal of Computer and Telecommunications Networking,1999,31(11-16):1361-1374.

基于预分类的逆变异分类器算法 篇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

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

$p(D{}_j|x;\widehat{\theta })=\frac{p(D{}_j|\widehat{\theta })p(x|D{}_j;\widehat{\theta })}{p(x|\widehat{\theta })}。$

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

$p(D{}_j|\widehat{\theta })=\frac{{\displaystyle \sum _{i=1}^{|D{}_s|}p}(D{}_j|x)}{|D{}_s|}。$

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

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

$\begin{array}{l}p(x|D{}_j;\widehat{\theta })={\displaystyle \prod _{i=1}^{|E|}(}w{}_{i}p(e{}_i|D{}_j,\theta )+\\ (1-w{}_i)(1-p(e{}_i|D{}_j;\theta ))。\end{array}$

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

$p(e{}_i|D{}_j,\theta )=\frac{1+{\displaystyle {\sum }_{k=1}^{|S|}w}{}_{ki}{\rm P}(D{}_j|x{}_k)}{2+{\displaystyle {\sum }_{k=1}^{|S|}{\rm P}}(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;$\widehat{\theta }$),见下式。注:下式中,为了方便起见,省写了待估参数。

$\begin{array}{l}p(x{}_1|D{}_0;\widehat{\theta })=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,\theta )=\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;\widehat{\theta })=\frac{(1/2)\times (2/4){}^6\times (3/4){}^3}{p(x|\widehat{\theta })}。$

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

$p(D{}_1|x{}_1;\widehat{\theta })=\frac{(1/2)\times (1/4){}^5\times (2/4){}^4}{p(x|\widehat{\theta })}。$

显然,p(D0|x1;$\widehat{\theta })>p(D{}_1|x{}_1$;$\widehat{\theta }$),因此判定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

文本分类器 篇4

网络流分类是认识、管理、优化各种网络资源的重要依据, 随着动态端口和加密技术的广泛使用, 传统的基于端口号映射和基于载荷分析的网络流量分类方法[1]不再具有普遍适用性。为克服上述方法的不足, 许多学者运用基于流统计特征的机器学习[2]方法来解决流量分类问题, 该方法利用流在传输层表现出的各种特征统计信息进行分类, 不受动态端口、载荷加密及网络地址转换的影响。但绝大多数的网络流量分类方法的性能在分类器间的互补性和预测阶段的开销方面受限, 难以适应网络环境的动态变化, 在不同环境下分类效果不明显。

集成学习[3]通过对样本学习训练出若干个分类器 (称为基分类器) , 然后通过某种规则将这些分类器的分类结果进行整合以解决某一具体的问题。传统的集成学习方法如Bagging、Adaboost等都是将所有分类器进行集成, 而近来研究发现, 选择部分分类器进行集成学习比选择所有的分类器进行学习具有更好的泛化性能, 这种方法称为选择性集成[4]。国内外学者对选择性集成的研究主要集中在基分类器的选择上, 一方面, 通过剔除对集成学习有负面影响的基分类器, 进一步提高分类精度;另一方面, 通过去掉冗余的基分类器, 降低预测时间复杂度。

本文基于流统计特征的机器学习方法, 同时考虑单个基分类器的预测精度和多个基分类器间的多样性, 通过选择性集成方法MCSE对多个分类器进行集成来实现网络流量分类。在Moore数据集上进行实验, 实验表明, 与同类集成学习和选择性集成算法相比较, 本文提出的算法在分类准确率、分类器选择时间和目标集成分类器大小方面更具优势。

1 国内外研究现状

分类器选择性集成学习的目的是在不降低甚至进一步提供原数据集成学习机预测精度的前提下, 尽可能减少参与集成学习的基分类器数目。周志华提出基于遗传算法的选择性集成算法GASEN[4], 通过遗传算法对每个分类器的权重进行调整, 直至各分类器权重的分布接近全局最优, 最后选择权重大于阈值的分类器参与集成, 但遗传算法需要大量的计算和存储空间;基于分簇的选择性集成模型 (CPF) [5], 把所有的基分类器进行分组, 在各个分组内部进行选择, 其缺点是运算量和存储空间占用大, 选择的效率不佳;方向排序OO (Oriented Order) 算法[6]是目前速度最快、空间效率最好的选择性集成算法, 其缺点是无法给定一个恰当的名次判断标准, 得到的集成分类器规模较大。

此外, 盛高斌针对小数据量的有标记样本问题, 提出一种基于半监督回归的选择性集成学习算法SSRES[7]。同时用有标记样本和未标记样本训练学习器, 使用选择性集成算法GRES对不同学习器进行适当的选择, 但该方法仅局限于回归情况;汪为汉等人[8]提出基于贝叶斯学习的集成流量分类方法, 利用测试集获得各贝叶斯分类器的权重, 并通过加权平均组合各分类器来实现网络流量分类, 此方法虽然在准确率上有一定提高, 但计算开销较大;孔蓓蓓等人[9]提出一种多分类器联合的集成网络流量分类方法, 通过对不同算法的分类器采用投票和实例选择性集成来实现流量分类, 增加实现的复杂度和计算开销。

2 选择性集成学习流量分类框架

选择性集成网络流量分类框架的关键是如何从若干基分类器中, 挑出差异性大、分类能力强的基分类器集合, 并准确地组合各个体分类器的输出结果, 来更好地提升集成分类器的整体性能。如图1所示, 选择性集成的思想是从多个分类器中选择一部分具有代表性的分类器进行组合, 剔除掉分类性能差且具有冗余的分类器, 从整体上提高分类器的泛化能力。

如图2所示, 在选择性集成基本思想的基础上, 提出了选择性集成网络流量分类框架。网络流量分类就是把具有相同五元组 (源IP、目的IP、源端口、目的端口、协议类型) 的网络流 (flow) 按照不同的应用类型分类[10]。整个过程可分为四个阶段:第一阶段, 流量捕获。利用流量捕获软件如Net Mate、Netflow、Ether Peek等从真实的网络环境中捕获数据包, 并将其抽象为包含网络属性的流向量;第二阶段, 特征提取和选择。根据捕获流量统计属性 (如分组数量、分组到达时间间隔、最大分组长度、分组数量等) , 进行特征提取和特征选择, 得到最优或者次优的特征子集用于训练分类器模型。第三阶段, 多分类器选择性集成。选取网络应用类型多样、规模适中的样本组成训练集, 结合相关的流量分类算法如支持向量机、贝叶斯、决策树和神经网络等对其进行训练, 构造多个独立的基分类器, 采用选择性集成的方法, 从多个级分类器中选出一部分差异性大且分类能力强的基分类器来提高集成分类器的效果;第四阶段, 分类模型测试。为了验证流量分类基分类器的可靠性, 需要选取一定的测试集, 验证网络流量分类的准确性, 并根据验证结果对分类算法进一步进行优化和改进, 以确保分类的有效性。

3 多分类器选择性集成网络流量分类方法

3.1 分类器差异性度量

分类器差异性体现在至少有分类器对其它分类器预测错误的样本作出正确的预测。比较典型的是Castro[11]的人工免疫算法, 周志华的基于遗传算法的GASEN[4], 但人工免疫和遗传算法在选择部分个体分类器的时间复杂度较高。Kuncheva[12]在研究成果中总结了10种差异性度量方法, 常见的分类器差异性度量方法包括Q统计量法、相关系数法、不一致度量法、熵度量法、双错度量法。根据Kuncheva等人对各种度量方法进行的试验来看, 以上各种度量方法分类准确率近似, 但由于不一致度量方法具有较好的可理解性和稳定性, 被广泛地运用于度量分类器间的差异性。分类器di和dj之间的不一致度量定义如下:

对不同的分类目标, N11与N00分别表示对分类样本均预测正确和均预测错误, N10表示基分类器di预测正确而dj预测错误, N01表示基分类器di预测错误而dj预测正确。dij的值的变化范围在[0, 1]之间, dij值越大, 表示分类器间的差异性越大。

3.2 改进不一致性度量方法

为选出具较大差异性的分类器, 需要将分类器与其他分类器进行比较, 得出相应的差异性值。应用不一致度量策略度量n个分类器间的差异, 可得如下所示的分类器差异性矩阵D, 其中dij表示分类器di与dj的差异性值。

将分类器差异性矩阵D中各分类器的差异性与平均差异性值进行比较, 选择差异性值大于平均差异性值的分类器参与分类器的集成, 此时比较的次数为nxn。注意到, 当分类器的数目n较大时, 比较次数是n2, 急剧增加了算法计算的复杂度和计算存储空间, 为减少算法的比较次数, 降低计算的时间复杂度和空间复杂度, 本文对该方法进行改进, 作了进一步的简化:

令:

其中, 表示分类器di在整体分类器中的差异性值, 则分类器差异性矩阵可得如下优化:

式 (3) 表示第i个分类器di与其他所有分类器差异性值总和的平均值, 本文将该值作为分类器di在整体分类器中的差异性值。

整体分类器平均差异性值是指n个分类器差异性值总和的平均值, 用AV表示整体分类器平均差异性值, 计算公式为:

此时, 选取具有较好差异性的分类器的策略为:当, 则选重分类器i参与最后的集成预测, 否则将其删除, 最终选出m (m≤n) 个具有较好差异性的分类器, 这个过程的比较次数为n, 有效地减少了计算的开销, 提高了效率。

3.3 MCSE方法描述

MCSE方法结合半监督学习技术, 同时利用已标记的流量样本和无标记的流量样本训练分类器, 设定分类器准确率阈值λ以保证选择具有较高正确率的分类器。MCSE分两阶段对多分类器选择性集成:第一阶段选择具有较高正确率的分类器, 以保证分类器集的鲁棒性;第二阶段筛选具有较好差异性的分类器, 以保证分类器集的高效性。MCSE方法的描述如下:

阶段一选择分类识别率高的基分类器

输入:有标记的网络流量样本集L, 无标记网络流量样本集U, 测试样本集Y

输出:S个分类识别率高的基分类器集PS

(1) 用样本集L和U同时训练N (N>S) 个分类器Ci (1≤i≤N) 。

(2) 用Y测试各个基分类器di, 计算每个分类器的分类识别准确率Ri, 得R={R1, R2, …, Rt}。

(3) 对集合R中的元素按降序进行排列, 取大于准确率阈值λ的分类器, 得S={d0, d1, …, dn-1}。

阶段二从识别率高的基分类器中选出差异性大的分类器

输入:基分类集S

输出:新的差异性集合C

(1) 根据不一致性度量公式 (1) 计算分类器集Pk中各分类器间的差异性值dij, 得分类器差异性矩阵D;

(2) 令, 得优化的分类差异性矩阵DS;i=1

(3) 计算整体分类器的差异性平均值

(4) 选择差异性分类器:

为了从所有的分类器中选出同时满足出泛化能力强、差异性大条件的基分类器, MCSE方法将“选优”和“剔差”的思想相结合, 首先选出分类精度较高的分类器, 以丢弃可能对选择性集成学习造成负面影响的基分类器, 再剔除选出的分类器集中相关或者冗余的基分类器, 剩余的就是用于集成的个体分类器。在剔除基分类器的过程中, MCSE方法利用半监督学习能同时利用有标记样本和无标记样本的优势来训练初始分类器, 并用改进的不一致度量方法对分类器的差异性进行评估, 相比多对多的选择方法, 该方法能明显减小搜索空间, 提高多分类器选择性集成系统的性能。

4 实验与结果分析

4.1 实验数据

实验采用剑桥大学Moore教授在文献[13]中使用的数据集[14], 本文称之为Moore-set, 该数据集共包含377526个网络流量样本, 分为10大类, 每类的统计信息如表1所示。由于IN-TERACTIVE和GAMES的数量较少, 不具代表性, 因此在本实验中不采用这两种数据。

每个在Moore-set中的样本都是完备的TCP双向流, 有249种特征属性, 由端口号等网络属性和平均间隔时间等统计属性组成, 最后一项属性为分类目标属性, 表明该样本的流量类型。众多的特征中存在不相关或者冗余的特征, 首先使用FCBF (fast correlation-based filter) 特征选算法进行特征选择。实验所用的数据处理和分析工具是Matlab 7.1.0和weka3.7.0。

本文选择Bagging、GASEN和MCSE算法作对比实验, 其中, Bagging是最传统、最常用的集成算法, 将所有分类器直接进行集成。GASEN是典型的选择性集成算法。

实验采用重复抽样的方式, 以训练出不同类型的分类器, 从Moore-set中抽取每类应用的1%构成训练集trian-set和每类应用的1%为测试集test-set。为进一步验证选择性集成的作用, 分别用Bagging、GASEN和MCSE算法进行网络流量分类, 比较基分类器数目在20、40、60、80、100、120和140下的分类性能。评价指标是分类准确率、分类器训练时间和参与集成的分类器数目。其结果分别如图3-图5所示。

4.2 实验结果分析

在分类精度方面, 两种选择性算法MCSE、GASEN在不同基分类器数目下, 分类精度都优于Bagging算法。当基分类器的数目在20以GASEN的分类精度与MCSE方法无太大的差距, 但当基分类器的数目超过20后, MCSE的分类精度开始不断提高, 明显高于GASEN, 选择性集成的正面效应越来越明显。在训练时间方面, Bagging方法直接对所有基分类器的预测结果进行多数投票法组合, 需要考虑的基分类器数目较多, 消耗了更多的时间, GASEN选择性集成算法是基于遗传算法的, 需要运算和存储空间开销都较大, MCSE简化了比较模式, 从而减少了比较时间开销, 具有较好的优势。从图5可以看出, 选择性集成算法选择出来的基分类器数目远远小于原始的基分类器数目, 当基分类器的数目大于40的时候, MCSE选择性集成方法的优势越来越明显。

实验结果表明, 从基分类器的精度和差异性来设计和改进多分类系统是非常有效的。MCSE方法结合基分类器个体的精度和基分类器间的差异性, 避免了选择过程中重复进行基分类器预测结果, 能剔除对提高泛化能力不起作用的基分类器。但选择性集成必须在具备一定规模的分类器上才能发挥其作用, 因为对许多算法, 集成分类器越小, 越不容易被分辨出性能不佳的基分类器, 选择性过程中越可能将有用的基分类器丢弃。本实验中, 当分类器规模超过40后, MCSE选择性集成的优势越越来越明显。

5 结语

本文在基于选择性集成网络流量分类框架下, 提出了一种多分类器选择性集成的网络流量分类算法, 改进不一致性度量策略, 将单个分类器的精度和多个分类器间的差异性有机结合进行选择性集成, 比同类算法具有更好的分类性能。在高速网络环境中, 下一步的研究工作是:把增量学习技术运用到选择性集成方法中, 结合高性能计算平台, 研究选择性集成算法的并行化, 选择尽可能少的基分类器进一步提升流量分类的性能。

摘要：针对多分类器集成方法产生的流量分类器在泛化能力方面的局限性, 提出一种选择性集成网络流量分类框架, 以满足流量分类对分类器高效的需求。基于此框架, 提出一种多分类器选择性集成的网络流量分类方法 MCSE (Multiple Classifiers Selective Ensemble network traffic classification method) , 解决多分类器的选取问题。该方法首先利用半监督学习技术提升基分类器的精度, 然后改进不一致性度量方法对分类器差异性的度量策略, 降低多分类器集成方法实现网络流量分类的复杂性, 有效减少选择最优分类器的计算开销。实验表明, 与Bagging算法和GASEN算法相比, MCSE方法能更充分利用基分类器间的互补性, 具有更高效的流量分类性能。

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

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

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.

基于SVM算法的分类器设计 篇6

1 支持向量机算法

1.1 算法思想

支持向量机算法的主要思想可以概括为:(1)它针对线性可分情况进行分析，而对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。(2)它基于结构风险最小化理论，在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并在整个样本空间的期望风险以某个概率满足一定上界。

1.2 原理简介

支持向量机基于线性划分，但可以想象，并非所有数据均可线性划分。如二维空间中的两个类别的点可能需要一条曲线来划分其边界。支持向量机的原理是将低维空间中的点映射到高维空间中，使其成为线性可分的。再使用线性划分的原理来判断分类边界。在高维空间中，它是一种线性划分，而在原有的数据空间中，它是一种非线性划分[2]。

但讨论支持向量机的算法时，并不是讨论如何定义低维到高维空间的映射算法，而是从最优化问题的角度来考虑的。求最优解的问题可分为无约束最优问题和有约束最优问题。无约束最优算法可表达为mxinf(xi)。可用数值计算方法中的牛顿法、最速梯度下降法等，通过多次循环，求得一次近似的最优解。

有约束问题，一般表达为

支持向量机对于非线性可分的情况，可使用一个非线性函数φ(x)将数据映射到一个高维特征空间，再在高维特征空间建立优化超平面，分类函数变为

通常无法了解φ(x)的具体表达，也难以知晓样本映射到高维空间后的维数和分布等情况，不能在高维空间求解超平面;b是分类阙值，可用任意一个支持向量求得，或通过两类中任意一对支持向量取中值求得。由于SVM理论只考虑高维特征空间的点积运算φ(xi)·φ(xj)，而点积运算可由其对应的核函数直接给出，即K(xi,xj)=φ(xi)·φ(xj)用内积K(xi,xj)代替最优分类面中的点积，就相当于将原特征空间变换到了某一新的特征空间，得到新的优化函数

求解上述问题后得到的最优分类函数是

上式中的求和实际上只对支持向量进行。其中核函数K(xi,x)可有多种形式，常用的有

(1)线性核K(x,y)=(x·y)。

(2)多项式核K (xi,x)=(xi·x+1)d,d是自然数。

(3) Radial Basis Fuction(RBF)核(径向基核)

支持向量机的一个显著特点是，计算的复杂度程度与输入空间映射成的核空间的维数无关。因此，就没有了维数问题。换言之，人们在高维空间中进行设计，不必使用大量参数的显模式，其由空间的高维数决定。这也对扩展性产生了影响，而实际上SVM具有较好的扩展性。

支持向量机的一个局限是，直到目前为止也没有最佳方法选择核函数，这仍是一个未解决的问题。但通常而言，径向基核函数不会有过大偏差，对大部分分类问题的效果不会有较大差异，故是首选。

1.3 支持向量机的一般特性

(1) SVM学习问题可表示为凸优化问题，因此可利用已知的有效算法发现目标函数的全局最小值。而其他分类方法都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。(2) SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。(3)通过对数据中每个分类属性引入一个哑变量，SVM可应用于分类数据。(4) SVM一般只能用在二类问题，对于多类问题效果不佳。

2 基于SVM的分类器设计

2.1 分类器原理

数据分类是数据挖掘中的一个重要题目。数据分类是指在已有分类训练数据的基础上，根据某种原理，经训练形成一个分类器;然后使用分类器判断测试数据的类别[5]。

基于SVM的分类器是一种基于分类边界的方法。其基本原理是:若训练数据分布在二维平面上的点，按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是，通过训练找到这些分类之间的边界。对于多维数据，可将其视为N维空间中的点，而分类边界就是N维空间中的面，称为超面。线性分类器使用超平面类型的边界，非线性分类器使用超曲面。

线性划分如图1所示，可根据新的数据相对于分类边界的位置来判断其分类。一般首先讨论二分类问题，然后再拓展到多分类问题。

2.2 基于SVM算法的分类器的实现步骤

(1)将数据集转化为SVM支持的格式。(2)数据预处理，将数据集的分类属性值归一化并选择训练集和测试集。(3)选择核函数类型。(4)采用交叉验证和网格搜索方法寻找最优的参数c和gamma。(5)用最优化的参数训练出分类器。(6)用设计的分类器进行测试[3,4,5,6]。

3 实验与结果分析

实验以Matlab为开发平台[7]，用Libsvm工具箱设计了一个简单的分类器，并用公共数据库中的数据集为训练样例和测试样例，重点对其从训练集的选择方法，参数的选择与优化方面进行测试与验证。

3.1 数据集的划分

为方便结果的可视化，本文测试数据集的特征向量为二维，共包含210个样例，其中前100个为正例，后110个为反例。将数据集按3种方法划分出训练集和测试集。取参数c=16,g=0.01，然后分别对这其进行测试，测试结果如表1所示。

从实验结果可看出，前两种均分法不佳，这是因训练集包含的正反例涵盖不全，导致一些特例分类错误。第3种分法涵盖较均匀且全面，分类效果最佳，为方便验证算法参数的影响，本实验选择第3种分法进行测试验证。

3.2 参数c和g的优化

令c=2-5,2-3，…，215,g=2-15,2-13，…，23，采用交叉验证和网格搜索的方法寻找最优的参数bestc和bestg，搜索结果如图2所示。得出最好的参数bestc=23 170,bestg=0.000 244 14，对应的准确率为96.666 7%(58/60)。最优的参数bestc和bestg对应的可视化分类结果如图3所示。

3.3 参数c的选择及影响

固定选取g=0.000 244 14，测试不同参数c值对应的分类准确度，测试结果如表1所示。

参数c的值在变化过程中的一些典型值对应的分类结果如图4所示。

从测试结果可以看出，惩罚因子c决定了有多重视离群点点来的损失，随着c值的增大，对目标决策函数的损失也越大，此时则暗示非常不愿放弃这些利群点，如果继续将c值增大，增大到无穷大时，只要稍有一个点离群，目标决策函数的值就会变为无限大，使问题无解，这样分类器的分类效果则会很差。

惩罚因子c不是一个变量，整个分类器优化过程中，c是一个必须事先制定的值，制定这个值后，解得一个分类器，然后用测试数据查看结果，若不理想，则更换c值再得到一个分类器，再看效果，如此则是一个参数寻优的过程，最终可以求出分类器效果最好的c值。根据对这些离群点的重视程度来选择合适的c值，如果对离群点不是很重视，则可选择个小的c值，若这些离群点重要，则应选择较大c值。

3.4 参数g的选择及影响

固定选取c=23 170，测试不同参数g对应的分类准确度，测试结果如表2所示。

参数g在变化过程中典型值对应的分类结果如图5所示。

gamma参数是选择径向基函数作为kernel后，该函数自带的参数。隐含地决定了数据映射到新特征空间后的分布。从实验结果中虽然无法直接观测到数据映射到新特征空间后的分布情况，但是通过支持向量的变化可以看出gamma参数对分类器的影响，随着gamma参数的增大，分类器的支持向量越多越分散，说明数据映射到新特征空间后的分布也越复杂，从而使目标决策函数越复杂，影响分类器的分类效果。因此可以通过选择不同的gamma参数值来观测分类器的效果，逐步优化gamma参数，最终选择出最优值。

4 结束语

用公共数据库中的数据集作为训练样例和测试样例，对设计的基于SVM算法的分类器进行了实验，研究了SVM算法中主要参数c和gamma的物理意义。从实验结果可看出，在将SVM算法应用于数据分类时，参数c和gamma对结果的影响仍不容忽视，因此在应用时，应选择合适的参数c和gamma类优化分类效果。

参考文献

[1]Tom M Mitchell.机器学习[M].曾华军,张银奎,译.北京:机械工业出版社,2003.

[2]Crist Anne.支持向量机导论[M].李国正,王猛,曾华军,译.北京:电子工业出版社,2004.

[3]Chih-wei Hsu,Chang Chihchung,Lin Chih Jen.A practical guide to support vector classification[M].Korea:Seoul University,2010.

[4]徐义田.基于SVM的分类算法与聚类分析[J].烟台大学学报,2004,17(1):9-13.

[5]杨铁建.基于支持向量机的数据挖掘技术研究[D].西安:西安电子科技大学,2005.

[6]魏蕾,何东健,乔永亮.基于图像处理和SVM的植物叶片分类研究[J].农机化研究,2013(5):12-17.

海上伤员分类器的研究与应用 篇7

伤员分类是根据伤情的需要和医疗后送条件的可能, 将伤员区分为不同处置类型的活动, 是战时伤员医疗后送工作的程序之一, 是做好伤员收容、治疗和后送工作的前提[1]。海上批量伤员的伤情种类多样, 轻重不一, 加上一线医务人员相对较少, 影响伤员急救的时效性[2], 以致错过海战创伤抢救的“黄金时间”, 造成不必要伤亡。为此, 我们设计、研制了海上伤员分类器。海上伤员分类器 (personal digital assistant, PDA) 能够对伤员伤情与救治信息进行快速采集、存储、转发和利用, 实现对海上批量伤员的快速分类, 及时救治。

2 海上伤员分类器功能总体设计

海上伤员分类器可快速实现对伤员伤情信息的采集、伤情查看、战创伤评分、战创伤分类、伤情标记、伤员分流;指导医护人员对伤员进行急救处置、医疗后送;通过无线局域网将伤员信息实时传输到一线救治机构服务器, 对伤员信息自动进行分类汇总, 并实现对伤员信息的查询功能;通过远程网络实现及时与上级医疗机构沟通, 进行远程会诊或提前将后送伤员的信息传输到后方, 以利后方医院做好接收准备;与“北斗”卫星通讯系统兼容, 实现数据的实时通讯;与“军卫一号”系统衔接, 支持“军卫一号”系统的信息读取、存储和共享, 构成海上批量伤员战伤评分系统, 满足伤员的急救与医疗后送信息的查询需求[3]。

海上批量伤员战创伤评分系统的核心是海上伤员分类器, 此外还包括大容量医疗信息卡、系统服务器、各组室PC、Web服务器、无线局域网、北斗卫星通讯系统等, 这些部分是海上伤员分类器各个功能实现的前提与技术保障。

3 海上伤员分类器功能实现的基础

海上伤员分类器是海上批量伤员战创伤评分系统的核心, 利用PDA进行快速检伤分类, 方便随身携带, 抗损毁, 具备一定的存储容量;可快速、准确地读取采集伤员信息并形成电子伤票;满足全天候与恶劣环境下作业;具备双向通信能力;适用于计算机管理、网络功能与流程控制[4]。PDA界面设计具有如下特点:数据输入多为触屏式点击输入, 输入速度快, 操作简便;通过手写识别和虚拟键盘用笔取代键盘;下拉式选择框, 界面简洁, 包容信息量大[5]。海上伤员分类器产品规格见表1。

4 海上伤员分类器功能模块的组成

4.1 伤票信息采集功能模块

海上伤员分类器采用射频识别技术对大容量医疗信息卡内的基本信息进行采集。射频识别技术 (radio-frequency identification, RFID) 以无线信道作为传输媒体, 通过双向非接触数据通信实现对目标信息的获取。海上伤员分类器通过射频天线发射一定频率的射频信号, 这些射频信号在天线的周围产生电磁场。位于电磁场内的大容量医疗信息卡利用感应得到的能量将存储在芯片中的信息编码调制后发送出去, 海上伤员分类器接收天线接收大容量医疗信息卡发送来的信号。经解调、解码后传输到系统数据单元进行相关处理, 经过识别完成信息的采集和管理[6]。

4.2 伤票信息查询功能模块

利用海上伤员分类器完成对大容量医疗信息卡的伤票信息采集后, 点击分类器屏幕上的伤票信息查询按钮, 会跳转出伤员基本信息记录, 其内容包括:

(1) 基本信息:电子伤票号、人员编号、姓名、性别、年龄、职务、军衔、部别、填写单位、经治军医、信息读取日期等。

(2) 伤情图片:伤情图片为由初级救治单位采集并保存在大容量医疗信息卡内的珍贵伤情信息, 它对后级救治单位确定采取何种治疗措施具有重要的指导意义。

(3) 负伤情况:负伤时间、负伤地点、紧急处置情况、到达时间、救护方式、伤情种类、伤势等。

(4) 伤病史:救治经过、症状及体征、其他信息。

此功能有助于医护人员快速准确地掌握伤员的伤情伤势、救治经过, 可以及早地采取相应的治疗措施, 能为伤员的紧急救治节省宝贵的时间。

4.3 战创伤评分功能模块

战创伤评分是通过定量记分方法对战创伤的严重程度和预后进行评估, 并根据判定结果指导治疗。现场急救是战创伤急救的关键所在, 根据伤员现场急救的需求, 应对批量伤员快速实施检伤分类、伤势评估, 初步确定合理治疗方案, 决定是否后送等, 并且在后续治疗过程中进行疗效评价和治疗水平的比较。

海上伤员分类器软件汇集了6种目前国际上使用较为普遍的创伤评分方法, 分别为:简易战伤评分法、创伤指数评分法 (trauma index, TI) 、院前评分指数 (prehospital index, PHI) 、CRAMS评分法、创伤评分法 (trauma score, TS) 、修正的创伤评分法 (revisional trauma score, RTS) 。因此, 海上伤员分类器软件适合不同形式下批量伤员的快速战创伤评分, 能为战创伤的急救赢得宝贵时间, 降低不必要伤亡率, 提升我军卫勤保障能力。以创伤评分法为例, 该方法以5项指标对伤员进行评估, 见表2。

注:1 mm Hg=133.322 Pa

创伤评分法是从生理学角度来评价创伤程度的数字分级方法, 观察指标包括人体对创伤的生理和病理反应, 其中意识状态按照GCS评分标准计分。总分为1~16分, 总分越少, 伤情越严重。以上5项积分能比较客观地反映循环系统、呼吸系统和中枢神经系统功能, 评估伤员的创伤程度, 辅助决定是否需要创伤救治[7]。

4.4 战创伤分类功能模块

利用PDA完成对伤员的伤势评估后, 点击战创伤分类按钮, 跳转出战创伤分类界面。战创伤分类的基本依据有:

(1) 伤类:炸伤、枪弹伤、器皿伤、挤压伤、冲击伤、撞击伤、烧伤、冻伤、毒剂伤、电离辐射伤、生物武器伤、激光损伤、微波损伤、复合伤、其他损伤。

(2) 伤部:头部、面部、颈部、胸背部、腰腹部及骨盆会阴、脊柱脊髓、上肢、下肢、多发伤、其他。

(3) 伤型:贯通伤、穿透伤、盲管伤、切线伤、骨折、皮肤及软组织伤、断肢和断指 (趾) 、其他。

(4) 并发症:大出血、窒息、休克、抽搐、气胸、截瘫、气性坏疽、其他。

战创伤分类是伤员分流的基础, 战创伤分类的情况及速度在很大程度上影响着伤员的后续治疗及预后情况。

4.5 伤标选择功能

利用分类器完成对伤员的伤势评估、伤情分类后, 需对伤员进行伤标标识, 以便后续的医护人员快速采取相应的救治措施。点击伤标选择按钮, 分类器操作界面跳转出2个选择按钮, 分别标示为战争军事行动和非战争军事行动。战争军事行动则采用野战伤标:红色 (大出血) 、白色 (骨折) 、黑色 (传染病) 、蓝色 (辐射伤) 、黄色 (毒剂伤) ;非战争军事行动采用国际通用伤标:黑色 (死亡伤员) 、蓝色 (特重伤员) 、红色 (危重伤员) 、黄色 (可延期处理伤员) 、绿色 (轻伤伤员) 。2种可供选择的伤标可以满足多样化军事行动卫勤保障的需求[8]。

4.6 伤员分流功能模块

一线医护人员在完成对伤员进行创伤评分、分类以后, 面临的首要问题是快速将伤员分流到各个医疗组室接受诊疗。医护人员点击PDA界面上的分类意见和分类去向功能, 并根据创伤评分、分类的结果, 迅速将伤员分流到各个医疗组室。

(1) 分类的意见:重伤救治、抗休克、紧急手术、收容留治、传染病隔离、心理咨询、其他。

(2) 分类去向:医护组、抗休组、手术组、分类组、其他。

利用PDA对伤员进行分流, 提高了分类的速率和效率, 而且可以将伤员信息预先传送到各接收组室, 使其做好接收准备, 提高了伤员的救治成功率。

4.7 战创伤急救处置指导功能模块

伤员被分流到各医疗组室后, 医务人员对伤员实施的一切医疗救治措施均可用PDA进行记录, 并且PDA中预先置留的战创伤急救记录对医护人员进行伤员的进一步急救工作也起到很好的指导作用。战创伤急救处置功能包括以下几个方面:

(1) 抗感染。抗感染的指导栏目中包括:注射破伤风类毒素/毫升、注射破伤风抗血清/单位、注射不同种类的抗生素/单位、注射其他的药物/单位等。

(2) 抗休克。抗休克的指导栏目中包括:输血 (血型) /毫升、输液 (种类) /毫升、止痛 (药品名) /剂量/应用时间、吸氧、是否穿抗休克裤、其他相关处置。

(3) 手术。手术的指导栏目中包括:气管切开、血管结扎、开放气胸封闭、血气胸闭式引流、深筋膜切开、导尿、膀胱穿刺、清创、其他。

(4) 其他处置。此指导栏目包括:交换绷带、石膏制动、夹板制动、固定夹固定、加压包扎、洗消、服抗辐射药、服解毒药、复温。

这些医疗处置指导为一线医护人员进行伤员的紧急救治提供了参考。

4.8 伤员后送指导功能模块

某些战创伤伤员在一线接受医疗救治后仍需要后送治疗, 这时就可以利用PDA对伤员的后送进行详尽的指导和规范, 伤员后送指导功能主要包括:后送时间;后送单位, 即送往何地;后送方式, 如救护艇、医院船、救护直升机、运输机、卫生运输船、回程空车船、其他;后送体位, 如坐位、半卧位、俯卧位、平卧位。

医疗后送指南对批量伤员的后送具有重要的指导意义, 严格规范伤员的医疗后送对于提高后送伤员的长期生存率可发挥重要作用。

4.9 伤员基本信息的传输功能模块

无线局域网利用无线信道进行信息传输。分类现场环境复杂, 布线繁琐、移动受限, 利用无线局域网进行信息传输, 不但能保证用户的安全和设备性能, 而且方便快捷。根据需要, 我们采用了Wireless Fidelity (Wi-Fi) 局域网, 其标准是IEEE802.11b/g, 最大传输速率为54 Mbit/s, 保证了信息传递的时效性。PDA具备Wi-Fi通讯功能, PDA将信息卡上的基本信息采集后, 经过数据压缩或文字编码, 通过Wi-Fi将数据传输到系统服务器上, 系统服务器通过专用的读写器将相应的信息记录到大容量医疗信息卡上, 保证了信息传输的连续性和时效性。PDA的Wi-Fi通讯装置的信号传输距离理论上室内为100 m, 室外为400 m。Wi-Fi传输范围广, 抗干扰能力强, 不易被窃听, 并且耗能低、成本小。

5 海上伤员分类器的应用

在多次卫勤演习中, 我们模拟海上军事行动时批量伤员被救护艇等救援力量送上医院船, 在甲板上医护人员应用海上伤员分类器对伤员进行快速的战创伤评分, 记录伤员的伤情和基本体征, PDA自动给出评分结果、显示商标颜色, 并给出紧急救治的参考。这一切信息通过无线局域网传输至系统服务器, 系统服务器根据信息类别, 将伤员信息自动传输至医院船上相应的急救组室。各组室接收到信息后, 在伤员未到的情况下提前做好接收准备, 减少了伤员等待时间, 提高了救治成功率[2]。需要后送或远程会诊的伤员信息, 由Web服务器通过“北斗”通讯卫星传至后方医院。另外, 数据库服务器统计的伤员信息, 通过有线或卫星网络传至各级指挥部, 供各级指挥人员查询参考, 指导决策。系统实施方法如图1所示。

6 结论

海上伤员分类器为伤员的分类、后送、救治及其质量的评价提供了科学和快捷的工具。它利用RFID技术和芯片存储技术实现伤员基本信息的获取和存储;与“军卫一号”系统及“北斗”通讯卫星对接, 全面实现了数据传输的时效性和连续性, 并规范了数据库管理。它具有操作简单、信息容量大、覆盖范围广、数据传输量大、安全稳定等优点。因此, 它非常适合于批量伤员现场, 能为各种战伤救治及指挥决策提供丰富、准确的信息支持, 也能为今后开展各种战、创伤救治的研究提够更加详实的资料。在“联卫-2009”等海上卫勤演习中, 运用海上伤员分类器准确地实现了对伤员的快速评分、分类及数据的综合管理。它可以在海上伤员急救与医疗后送中发挥至关重要的作用, 还可以应用于陆地战伤以及非战争军事行动伤员的快速分类。

摘要：目的:实现海上批量伤员伤情与救治信息的快速采集、存储和传输, 实现对海上批量伤员的快速分类, 进行伤员信息自动化管理。方法:运用PDA、Wi-Fi、射频识别、北斗卫星通讯等技术, 开发研制海上伤员分类器, 系统包括伤票采集、查询模块, 战创伤评分模块, 伤票标识模块, 伤员分流模块等。结果:海上伤员分类器能够快速地进行批量伤员的战创伤评分、分类, 实现教学模拟训练、综合演练等功能。结论:海上伤员分类器实现了伤员信息的智能化管理, 保证了伤员救治的时效性和连续性, 有效提升了军队海上伤员救护的信息化水平。

关键词：海上医疗救护,战创伤评分,卫勤保障,分类器

参考文献

[1]鱼敏.军队卫生勤务学[M].北京:人民军医出版社, 2007:177.

[2]王力, 张树华, 王永进, 等.成批伤员救治信息管理系统的设计与应用[J].医疗卫生装备, 2008, 29 (9) :58-60.

[3]郝林源, 徐雷.电子伤票信息系统数据库分析与设计[J].医疗卫生装备, 2008, 29 (4) :38-39.

[4]连平, 张革军, 栾颖, 等.电子伤票系统核心技术选择与应用改进[J].医疗卫生装备, 2008, 29 (7) :64-65.

[5]闫庆广, 吴宝明, 黄华, 等.一种新型电子伤票与急救辅助系统的研制[J].医疗卫生装备, 2007, 28 (5) :1-3.

[6]卞姜宁, 来欣, 吴占敖, 等.基于RFID的智能化战备药箱系统[J].医疗卫生装备, 2008, 29 (8) :9-11.

[7]杨震.急危重症抢救技术[M].北京:中国医药科技出版社, 2006.