ISSN 1000-0054
CN 11-2223/
N
清华大学学报 (自然科学版)
J T singhua U niv (Sci & T ech),
2004 年第44 卷第6 期
2004,Vol. 44,No. 6
12/ 37
762-765,777
管理分类规则的广义决策树
刘红岩
1
, 何 军
2
(1. 清华大学 经济管理学院,北京 100084;2. 中国人民大学 信息学院,北京 100872)
收稿日期:2003-07-02
基金项目:国家自然科学基金资助项目 (70273055);
国家自然科 学基金创新研究群体科学基金项目
(70321001)
作者简介:刘红岩(1968),女 (汉 ),山东,副教授。
E -m ail:hyliu@ tsinghua. edu. cn
摘 要:为了将传统的决策树无法管理的、由各种分类算法
所发现的大量的有意义的规则进行有效的存储、剪裁和使
用,提出了广义决策树结构。它将传统决策树的结构进行扩
展,能够以较少的存储代价管理所发现的所有分类规则,且
易于表达规则之间的关系。提出了有效的优化策略。以此树
为基础,将决策树分类算法与基于关联规则的分类算法进行
了概括统一,并提出了相应的算法。实验结果证明,广义决策
树克服了传统决策树的缺点,并且适宜于维护、剪裁以及快
速搜索大量的分类规则。
关键词:信息处理;数据挖掘;分类;决策树;关联规则
中图分类号:
TP
311;
TP
391 文献标识码:
A
文章编号:1000-0054(2004)06-0762-04
Generalizeddecisiontreefor
managing classification rules
LIU Hongyan
1
,HE J un
2
(1. School of Econ omics and M anagement,
T sing hua U n iver sity,Beijing 100084,China;
2. Information School,Renmin University of China,
Beijing 100872,China)
Abstract:A generalized decision tr ee w as developed to effectively
store,prune and use large amounts of meaningful rules used by
various classification algorithms w hich can not be m anaged by
traditional decision trees. T he system extends the str uct ure of
traditional decision trees so it can store all the classification rules
found w ith less storage cost and can more easily express the
relationships between r ules. An effective optim ization strategy w as
developed to speed up th e rule search process. T h e structure can
generalize and unify decision tr ee classifications and classificatio ns
based on association rules. T est results show that the generalized
decision tree over com es the w eaknesses of tr aditional decision tr ees
and can be easily m aintained,pruned and searched.
Key words:inform ation processing; data mining; classification;
decision tree;associatio n rule
分类是数据挖掘中应用领域极其广泛的一种技
术。分类算法用于发现属于同一类别的对象的共同
特点,并据此对未知类别的对象进行分类。已经提出
的分类算法包括决策树算法、基于统计原理的
Bayes
算法、神经网络算法以及基于关联规则的分
类算法等。其中决策树算法
[1,2]
是使用比较多的一种
算法。但是由于在构造树的过程中忽略了很多信息,
因此它发现的只是隐藏在数据集中的部分规则,并
且可能导致对同一数据集构造出多棵不同的决策
树,从而引起分类的不一致性。与此不同的是,基于
数据之间的关联特性发现分类规则是近年来被广泛
研究的一种分类方法
[3～ 5]
。这类方法通常可以发现
数据集中更多有意义的规则,通过综合所有分类规
则为未知类别的对象分类,从而使得该类算法具有
更高的分类准确度。然而这些规则与决策树的结构
是不相容的,因而通常以简单的形式存放,这导致了
如下问题:1)每个规则都独立存储,浪费空间;2 )
搜索大的规则集效率低下;3 )由于无法表达规则
之间的关系,对规则进行剪裁困难。
文 [6]提出了一种 ADT 树 (association based
decision tree
)用于解决第 3 个问题,但此树仍然无
法解决前 2 个问题。针对这些问题本文作者提出了
广义决策树(
generalized decision t ree
,
GDT
),它
具有如下特点:
1)可以较少的存储代价表达决策树以及非决
策树算法所发现的所有分类规则,利用这些规则通
常可以更准确地实现分类,避免分类的不一致。
2)广义决策树可以将决策树算法以及基于关
联规则的分类算法进行统一概括。
3)利用广义决策树所表达的分类规则易于利
用决策树的剪裁方法进行剪裁。
资源评论
