一种基于属性敏感度的决策树算法① - 计算机系统应用.pdf

算 机 系 统 应 用 2010 年 第 19卷 第 11 期 一种基于属性敏感度的决策树算法① 王 梅 于 京 (北京电子科技职业学院科技工程学院电子工程系 北京市 100016) 刘 光 (北京市电信工程设计院有限公司 北京市 100036) 要: 决策树算法是数据挖掘中重要的分类算法。目前，已有许多构建决策树的算法， 中，ID3 算法是核 心算法。本文首先对ID3 算法进行研究与分析，针对计算属性的信息熵十分复杂的缺点，提出了一种 新的启发式算法SID3，它是基于属性对分类的敏感度的。文章最后通过实例对两种算法进行比较分析， 结果表明，SID3 算法能够生成正确的决策树，并且使建树过程更简便，更快速。 关键词: 数据挖掘; 决策树; 分类; ID3 算法; 属性敏感度 Sensitive Attribute Algorithm for Decision Tree SID3 1 1 2 WANG Mei , YU Jing , LIU Guang (1. Dept. of Electronic Engineering, Institute of Science and Technology Engineering, Beiing Electronic Science and Technology Vocational College, Beijing 100016, China; 2. Beijing Telecom Engineering Design Institute Co, Ltd., Beij ing 100036, China) Abstract: Decision tree is the most important classification algorithm in data mining. At present, there are many decision tree algorithms, ID3 algorithm is the core one. This paper first studies and analyses the ID3 algorithm, then discusses the complicacy of computing the Information Entropy of attribute, and put forward a new heuristic based on the sensitive of attribute contributing to the classification. Finally, this paper compares the two algorithms by experiments, the results show that SID3 can generate the correct decision tree and the process is more simple, more quickly. Keywords: decision tree; ID3 algorithm; sensitive of attribute 决策树方法是目前应用最广泛的归纳推理算法之 的，由于计算信息熵的公式复杂，过程繁琐，本文提 一，是一种以实例为基础的归纳学习算法，通常用来 出了一种新的基于属性对分类的敏感程度的启发式算 形成分类器和预测模型，着眼于从一组无次序、无 法，通过对属性敏感度[3] 的分析，选择敏感度最大的 则的事例中推理出决策树表示形成的分类规则，它采 属性作为