基于层次结构的多分类算法研究
摘要:在众多多分类问题的解决方法中,分解策略因其简单易行而成为主要的解决方法,本文对决策有向无环图(Decision Directed Acyclic Graphs,DDAG)和有向二叉树(Directed Binary Tree,DBT)两种层次模型从结构特点、算法执行时间以及分类准确率三个方面进行分析,为模型的择优使用提供参考。
关键词:
多分类;算法;层次模型;研究
中图分类号:TP399
文献标识码: A
分类是数据挖掘的基本任务之一,在图像识别、医疗诊断等领域被广泛应用[1,2]。当分类类别N>2时,称其为多分类问题,且分类复杂度将随N的增大而剧增。在多分类问题的解决方法中,分解策略因可缩小问题规模以及降低分类难度而被广泛采用。常见的分解策略有:一对一分解、一对多分解和多对多分解。分解策略虽然能够减小问题规模,但是当类别数较多时,庞大的子模型数量对最终的分类决策带来新的困难。为了进一步提升多分类模型的性能,克服因分解后子模型数量众多等问题,后期的改进更侧重于研究分解后子模型的组织方式,其中基于层次型结构的组织方式,因可减少性能较差子模型(如二类分类器)出现次数,分类时参与子模型数量少等优点而成为研究焦点,其典型代表为DDAG模型[3]和DBT模型[4]。虽然两类层次模型结构较为相似,但因分类节点组织方式不同性能存在较大差异,所以本文从模型的结构特点、算法执行时间以及分类准确度三个方面对二者进行分析对比,为模型的选择使用提供一定参考。
1DBT和DDAG多分类模型
1.1结构特征与构建算法
两类模型组成元素完全相同,如图1所示。模型中除最低层表示类别标识外,其余节点均为一个二类分类器。
1.1.1DBT模型
DBT模型的逻辑结构是一棵完全二叉树(如图1左),树中节点按以下原则进行排列,作为根节点的二类分类器Mi,j(由类别Ci和Cj训练所得)有左右两个子节点。其中左节点Mk,l必需满足k,l≠j,即该二类分类器的训练不允许包含类别Cj;右节点Mp,q需满足p,q≠i,即对应的二类分类器训练时不能含有类别Ci。树中除叶子节点外,所有子节点的部署必须满足上述约束条件,例如,节点Mk,l的所有子节点中均不能含有类别Cj。具体构造算法如图2所示。
1.1.2DDAG模型
DDAG模型最早是由Platt等人所提出的另一种优秀的层次型多分类方法。该模型逻辑结构为一个有向无环图,也可将其看作一类特殊的树型结构。对于N>2的多分类问题,该模型中...
== 试读已结束,如需继续阅读敬请充值会员 ==
|
本站文章均为原创投稿,仅供下载参考,付费用户可查看完整且有格式内容!
(费用标准:38元/2月,98元/2年,微信支付秒开通!) |
升级为会员即可查阅全文 。如需要查阅全文,请 免费注册 或 登录会员 |