基于二叉树的SVM多类分类算法.docx

基于二叉树的SVM多类分类算法
一、前言
SVM，支持向量机的概念是在1992年，由Vapnik和Cortes提出，是很多研究者从事分类问题的时候必备的基础知识。在处理二分类问题时，SVM表现出良好的性能，但是在多类分类问题上，SVM有一定局限性。因为SVM算法是基于二分类数据模型设计的，所以解决多分类问题需要进行改进。本文将深入探讨基于二叉树的SVM多类分类算法。
二、SVM算法
支持向量机（SupportVectorMachine），是一种基于统计学习理论的机器学习方法，主要用于分类问题。SVM能够把低纬度的线性不可分问题通过非线性映射，转换成高纬度线性可分问题。SVM分类的核心是通过找到数据集中的最大间隔来分类。
图1SVM分类
当然，数据点不可能总是在同一个平面上分割。在这种情况下，SVM的做法是把原来的数据升到更高的维度（甚至是无限维度），找到一个超平面划分数据，然后再把该超平面的映射降回到可见维度。
三、SVM无法直接处理多类分类问题
尽管SVM在二分类问题上表现非常优秀，但是当涉及到多类问题时，SVM不能直接使用。多类问题通常有三种解决方法：一对多，一对一和多类SVM。
1.一对多方法
一对多策略（OvR）是最简单并且最常用的方法，使用OvR策略的方法即：
将N分类问题分别进行二分类，每次选取其中一个类别作为正则样本，其他样本作为负样本进行分类。最后利用已经训练出的二分类算法进行多类别分类。
2.一对一方法
一对一（OvO）策略是将多个分类问题转化为两两分类间的二分类问题。假设分类问题中有M个类别，每次选取两个进行二分类，总共可以得到M*(M-1)/2组分类器。最后通过选举方法得到M个类别的分类结果。
3.多类SVM方法
多类SVM是一种比较新的方法，它在SVM的基础上，通过从多个角度来考虑标号之间的状态，建立一种分层聚类的方法来实现多类问题。
四、基于二叉树的SVM多类分类算法
基于二叉树的SVM多类分类算法把多类分类问题转化为一个树形结构。对M类分类问题，构建二叉树，第一次采用递归进行构建。每一层根据样本标记，把样本分类到不同的子节点。特别的，样本标签与节点标记一致时，放在左子树；否则放在右子树。我们可以通过二叉树根节点下有两个子节点的特点，迭代的构建二叉树的流程。在树的叶子中叶节点对应的标记即为对应分类器所训练出的分类结果。
我们可以将每一个二分类分类器紧接着树的节点上，通过样本的标记与节点标记的一致性来决定选择哪个二分类分类器进行训练。对于每个测试样本，从树的根节点开始，不断通过节点的标记以及样本标记的一致性进行遍历，从而找到对应的分类器进行分类。
图2基于二叉树的SVM多类分类算法流程
算法流程如下：
1)通过标记样本建立二叉树遍历树，标记与节点一致的左分支，标记与节点不一致的右分支
2)针对每个节点训练二分类分类器
3)对于新样本，从树根节点开始遍历，通过样本和节点标记是否一致来决定走左还是右分支。
4)直到遍历到树的叶子，叶子对应的分类器对样本进行分类
五、实验和结果
本文采用了莺尾花数据集（IrisDataSet）进行测试，该数据集是一个多类数据集，包含了3种不同的花朵品种，每种品种有50个样本，总共包含150个样本。在本文中，我们采用基于二叉树的SVM多类分类算法来进行多类分类任务。我们同样使用一对多和一对一策略作为对照组，来比较三种方法的分类效果。
以下是结果表格：
从实验结果来看，基于二叉树的SVM多类分类算法表现优于一对多和一对一策略。同时，在基于二叉树的SVM多类分类算法的实现中，节点的选择也会对最终的分类结果产生影响。在实际应用中需要注意这一问题。
六、结论
本文提出了基于二叉树的SVM多类分类算法，该方法将多类问题转化为一个树形结构，取得了不错的分类效果。实验结果表明，该算法对于多类分类问题有一定的优势，可在实际应用中进行尝试。需要注意的是，在实现时需要注意节点的选择问题。