352 MURTHY
decision trees (common in medicine) is also not considered. We do not discuss regression
trees. There is a rich body of literature on this topic which shares many issues with the deci-
sion tree literature. For an introduction, see (Breiman, et al. 1984, Chaudhuri, et al. 1995).
We do not discuss binary decision diagrams and decision graphs (Kohavi, 1994). We do
not discuss patents.
6
3. Finding splits
To build a decision tree, it is necessary to find at each internal node a test forsplitting the data
into subsets. In case of univariate trees, finding a split amounts to finding the attribute that
is the most “useful” in discriminating the input data, and finding a decision rule using the
attribute. In case of multivariate trees, finding a split can be seen as finding a “composite”
feature, a combination of existing attributes that has good discriminatory power. In either
case, a basic task in tree building is to rank features (single or composite) according to their
usefulness in discriminating the classes in the data.
3.1. Feature evaluation rules
In pattern recognition and statistics literature, features are typically ranked using feature
evaluation rules, and the single best feature or a good feature subset are chosen from
the ranked list. In machine learning, however, feature evaluation rules are used mainly for
picking the single best feature at every node of the decision tree. Methods used for selecting
a good subset of features are typically quite different. We will postpone the discussion of
feature subset selection methods to Section 5.1.1.
Ben Bassat (1987) divides feature evaluation rules into three categories: rules derived
from information theory, rules derived from distance measures and rules derived from
dependence measures. These categories are sometimes arbitrary and not distinct. Some
measures belonging to different categories can be shown to be equivalent. Many can be
shown to be approximations of each other.
Rules derived from information theory: Examples of this variety are rules based on
Shannon’s entropy.
7
Tree construction by maximizing global mutual information, i.e., by
expanding tree nodes that contribute to the largest gain in average mutual information of
the whole tree, is explored in pattern recognition (Glesser and Collen, 1972, Sethi and
Sarvarayudu, 1982, Talmon, 1986).
8
Tree construction by locally optimizing informa-
tion gain, the reduction in entropy due to splitting each individual node, is explored in
pattern recognition (Hartmann, et al. 1982, Wang and Suen, 1984, Casey and Nagy, 1984,
Hanisch, 1990), in sequential fault diagnosis (Varshney, Hartman and De Faria, Jr., 1982)
and in machine learning (Quinlan, 1986b). Mingers (1987) suggested the G-statistic, an
information theoretic measure that is a close approximation to χ
2
distribution, for tree con-
struction as well as for deciding when to stop. De Merckt (1993) suggested an attribute
selection measure that combined geometric distance with information gain, and argued that
such measures are more appropriate for numeric attribute spaces.
Rules derived from distance measures: “Distance” here refers to the distance between
class probability distributions. The feature evaluation criteria in this class measure sep-
arability, divergence or discrimination between classes. A popular distance measure is
剩余44页未读，继续阅读
CyberNinja
- 粉丝: 27
- 资源: 297
我的内容管理
展开
最新资源
- Vue实现iOS原生Picker组件：详细解析与实现思路
- Arduino蓝牙小车：参数调试与功能控制
- 百度Java面试精华：200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南：CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略：44步详解流程
- RecyclerView全面解析：替代ListView的新选择
- Android开发：自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发：BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0：Android事件总线详解与实战应用
- Android FileUtil：全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
