模糊二叉树支持向量机算法研究

张加建

【摘 要】支持向量机算法是90年代由 Vapnik 等人在统计学习理论的基础上提出的一种新式的机器学习算法，由于其卓越的学习能力，尤其是泛化能力，从而引起了人们对这一领域的极大关注。传统支持向量机是做二元分类的，而现实中更多的是多类分类。现有的多类分类算法中，二叉树支持向量机整体性能优于“一对一”、“一对多”等其它多类分类方法，但是二叉树支持向量机由于存在“差错积累”问题，使得分类准确率较低。本文针对二叉树支持向量机分类精度较低的缺点，将模糊支持向量机与二叉树支持向量机相结合，将模糊技术应用到支持向量机中，从而提高了分类准确率。

【关键词】支持向量机；二叉树；模糊理论

【Abstract】The support vector machine algorithm based on statistical learning theory is a new kind of machine learning algorithm proposed by Vapnik et al， Because of its excellent learning performance， especially the generalization ability， it has aroused great concern in this field. Traditional support vector machine is to do two yuan classification， and more in fact is a multi class classification. Existing multi class classification method， the binary tree support vector machine overall performance is better than that of “a”， “a pair of many” other multi class classification method， but binary tree support vector machine due to the presence of “error accumulation” problem， the classification accuracy rate is low. In this paper， for binary tree support vector machine classification accuracy lower shortcomings， fuzzy support vector machine and the binary tree support vector machine and the fuzzy techniques are applied to support vector machine ， so as to improve the classification accuracy.

【Key words】Support vector machine； Binary tree； Fuzzy theory

0 引言

支持向量机（support vector machine，SVM）是在统计学习理论[1]的基础上发展起来的一种新的学习算法，是 AT&T Bell 实验室的 Vapnik 等[2]人在90年代提出来的针对分类和回归问题的新型机器学习算法。统计学习理论是一种在小样本情况下研究其规律的机器学习算法，支持向量机作为一种近几年发展起来的数据挖掘技术，由于它基于结构风险最小化原则，能有效地避免过学习问题，具有良好的泛化能力[1]。这些优良特性使支持向量机成为了继神经网络、模式识别之后的又一研究热点。最有代表性的是美国邮政手写数字库识别研究成功地应用了支持向量机[3]，在其它应用领域，比如人脸检测与识别[4]、文本分类[5]、回归分析[6]等方面也取得了许多研究成果。

支持向量机算法是近几年研究分类问题较为典型的方法，它提供了一种实现自动、主动学习分类的途径。在实际应用中，多类分类问题更加常见，对于支持向量机多类分类方法的研究具有很大的实际应用价值，是支持向量机研究中的重要方向。在多类分类问题中，常见的“一对一”和“一对多”算法存在不可识别区域，训练速度慢，分类效率不高等缺点。二叉树支持向量机多类分类方法的主要优点是需要训练的支持向量机数目和各支持向量机的训练样本数目都较少，并且分类时也不必遍历所有的支持量机分类器，具有较高的训练速度和分类速度，对于类别数目多的分类问题，它具有更大的优势[7]。但是，二叉树支持向量机存在“差错积累”问题，使得分类准确率较低。针对这一问题，将模糊支持向量机与二叉树支持向量机相结合，将模糊理论应用于支持向量机中，对每个样本采用不同的惩罚系数，从而在构造目标函数时，不同的样本存在不同的贡献值，对含有噪声或野值的样本点赋予较小的惩罚系数，从而降低噪声与野值点的影响，以此来提高分类准确率。

1 二叉树支持向量机

二叉树支持向量机[8]（Binary tree support vector machine， BT-SVM）是先将全部类别划分为两个子类，然后又将之前的每个子类划分为两个子类，循环下去，直到划分出最终类别时停止。通过这种方法将一个多分类问题变成了求解多个二分类问题，在每个节点处采用二分类支持向量机进行机器学习，并且每学习一次，二分类问题的规模随之下降。图1描述了一个五分类问题的一种二叉树结构图，其它的二叉树结构与之类似。

在生成二叉树的过程中， 应该让最容易分割的类提前分割出来，基于这种思想，有两种构造二叉树的方法。类距离法：其基本思想是让与其他类相隔最远的类先分离出来，此时构造的超平面具有良好的推广性；空间分布法：根据训练样本在属性空间的几何分布情况来生成二叉树的方法。分割的顺序不一样，每个类的分割区域也是不同的，先分割出来的类更容易有较大的分割区域，为了让一个范围分布广的类有更大的分割区域， 它应该第一个被分离出来。

二叉树支持向量机解决了传统的支持向量机存在的不可分区域问题，将一个k类分类问题转化为求解k-1个二分类问题，减少了问题规模，当测试遍历二叉树时，没有必要计算所有的分类判别函数，从而提高了分类速度。但是二叉树支持向量机存在“差错积累”问题，使得分类准确率较低[2]，如何提高其的分类准确率，是亟待解决的问题。

2 模糊支持向量机

传统的支持向量机所能解决的是训练集是一般集合的情形。但是，现实世界存在大量的不确定信息，即模糊信息，如果支持向量机的训练集中含有模糊信息，那么传统的支持向量机分类将出现差错，所以人们提出了模糊支持向量机[9]的概念，来进一步完善支持向量机多类分类方法及满足解决实际问题的需要。模糊支持向量的主要思想是：针对噪音和孤立点对支持向量机分类的影响，在支持向量机中引入模糊参数，以此来减弱噪音及孤立点对分类造成的影响。

3 模糊二叉树支持向量机

由于二叉树支持向量机存在“差错积累”问题，我们可以在每个二分类处用一个模糊支持向量机来确定最优分解面。使用模糊支持向量机可以在保证既定的分类器结构下，通过隶属度函数有效减少孤立点和噪声的影响，提高分类的准确性。具体分类过程如下：

（1）令初始状态只含有一个类（X），其中X为训练样本的集合；

（2）采用基于类距离法的模糊二叉树支持向量机，将距离最远的类先分离出来，如果只含有一个类，则将其标志为与初始类相同，学习算法结束，否则转第（3）步。

（3）标志新的两类X■■和X■■为初始决策集，将输入样本的子集的隶属度分别计算，并使用模糊支持向量机的学习算法，以获得最佳的决策节点的分类面；

4 仿真实验

将模糊支持向量机算法应用于酒类分类中，本次实验的酒类数据是从UCI下载的5种酒类178*13的数据，将前100个数据作为训练集，后78个数据作为测试集，采用Libsvm_3.21实验平台进行实验。对二叉树支持向量机和模糊二叉树支持向量机的分类准确率进行比较如下：

上述实验数据表明，模糊二叉树支持向量机在数据分类上优于二叉树支持向量机，由此可见，模糊二叉树支持向量机是一种切实可行的多类分类算法。

【参考文献】

[1]邓乃扬，田英杰.支持向量机一理论、算法与拓展[M].北京：科学出版社，2009：115-132.

[2]Cortes C， Vapnik V. Support-vector networks[J]. Machine Learning， 1995， 20（3）：273-297.

[3]Schrlkopf B.， Williamson R.，and Shawe-Taylor J. Single-class support vector machines[C].Unsupervised Learning， Dagstuhl Semianr Report 235， 1999： 19-20.

[4]Osuna E.，Freund R， Girosi F. An improved training algorithm for support vector machine[C]. Proceedings of 1997 IEEE workshop on neural networks for signal processing. Amelea Island， 1997： 276-285.

[5]Ostma E.，Freund R， Girosi F. Training support vector machines： An application to face detection[C]. Proceedings of CVPR， 97. NY， 1997： 130-136.

[6]马潜云，张学工.支持向量机函数拟合在分形插值中的应用[N].清华大学学报（自然科学版），2000，40（3）：76-78，103.

[7]孟媛媛.模糊支持向量机的研究与应用[D].济南：山东师范大学，2006.

[8]孟媛媛，刘希玉.一种新的基于二叉树的 SVM 多类分类方法[J].计算机应用，2005，25（11）：2653-2657.

[9]杨志民.模糊支持向量机及其应用研究[D].北京：中国农业大学，2005.

[责任编辑：朱丽娜]