文档介绍：交互迭代一对一分类算法
第21卷第4期
2008年8月
模式识别与人工智能
PR&AI
Aug2008
交互迭代一对一分类算法球
刘波，郝志峰肖燕珊.
(华南理工大学计算机科学与工程学院广州5
小样本的高效学习机器，支持向量机的引人为机器
引入的，当遇到多分类问题，人们总是组合二分类器
来构造多分类器并通过判别函数进行分类14.
在前人的工作中,Vapnik”提出了一对多(One-
)算法,该方法把一个C-分类问题表示成
c个二分类问题，但是该算法存在不可分区域(落人
此区域的样本不能通过判别函数进行分类)，并且
,Vapnik引
入连续判别函数，这样不可分区域消失了并且分类
,Abe等人提出模
糊判别函数法，稍后Abe [7j证明连续判别函数和
模糊判别函数拥有相同的分类边界，两种算法是
等价的.
KreBel 提出一对一 (-One)算法,
，
然而此算法却存在不可分区域(落人区域中的样本
不能通过判别函数进行分类).为了解决不可分区
域问题,Platt等人提出基于决策树的有向无环图
算法(DecisionDirectedAcyclicGraph,DDAG).Pon—
til等人..采用网球锦标赛的规则来解决不可分区
，并将其命
名为自适应有向无环图算法(AdaptiveDirectedAcy—
clicGraph,ADAG).Abe 的分析显示组成 ADAG
,Abe 等人”］提出基于一对一算法的模糊决策函数判别 法.
Angulou提出支持向量机分类回归算法(Sup一 port )，该方 法 把需要 训练的两类和其它类分别设定为{一 1,0,+1},然 后根据Vapnik... 的精度,Hao等人u提出基于支持向量机的二次映 "把纠错码技术引入多分类算 法,Abe_】等人比较模糊判别支持向量机和纠错码 方法的优越性，实验结果显示两种方法表现出相似 的性能.
自从多分类算法提出来后，很多研究者开始比 较这些算法的性能，文献［17］~［19］显示一对一算 法不管是训练精度还是推广能力都比一对多算法优 秀， 区域，为了解决这一问题我们将提出交互迭代一对
分类算法.
2传统多分类算法
在这一节,我们将简单地介绍一对一算法］, 有向无环图算法和模糊支持向量机算法(Fuzzy Support VectorMachines) ［ 12J.
一对一算法
根据一对一算法的最初描述，对于一个C分类 问题,我们需要构造C(C 一 1)/2个二分类器，第i类 和第类之间的最优超平面为 Dif()=w()+bif=0,( 1)
其中,w是m维的向量b为一个常数,()表示 非线性映射.
在特征空间中，定义超平面的方