基于预处理的决策树在化学数据挖掘中的应用

1、基于预处理的决策树在化学数据挖掘中的应用李 琳 陈德钊 3 束志恒 叶子青(浙江大学化工系仿真中心 , 杭州 310027摘 要 化学数据挖掘可从海量数据中提取蕴含的知识 , 决策树方法是一种重要的挖掘工具 。 鉴于决策树在 处理连续数据上的局限性 , 本研究提出先进行预处理 , 将连续属性离散化 , 通过特征选择删除其冗余量 , 以此 为基础构建决策树 。 该方法可防止决策树模型“ 过细 ” , 使之具有良好的预报性能 。将此方法应用于两个化 学样品分类实例 , 效果良好 。 与贝叶斯分析和单一的决策树方法相比 , 其预报正确率有显著提高 , 且表达形式 直观明确 , 易于理解和分析 , 适

2、用于化学分类知识模式的挖掘 。 关键词 数据挖掘 , 决策树 , 离散化 , 特征选择 , 化学模式分类 2004207209收稿 ; 2005201231接受本文系国家自然科学基金项目 (No . 20276063 、 浙江省重点科技项目 (No . 2004C21054 资助课题1 引 言数据挖掘可从海量的 、 存在噪声的 , 可从冗余和缺损的数据中提取蕴藏其中的有用知识 1, 挖掘化学分类知识模式常用的方法有现代统计和神经网络两类2, 3, 现代统计方法要求样本数据遵从一定的概率分布 , 神经网络的训练时间长 , 不确定性大 , 可解释性较差 。决策树4是基于机器学习的数据挖掘技术 ,

3、它形式简单 , 分类速度快 , 无需先验知识 , 对样本分布也无要求 。 而且由决策树表达的规则直观清晰 , 便于专业人员分析 。本研究拟用 C4. 5算法 5生成决策树 , 针对其处理连续数据的局限性 , 先进行离散化和特征选择 。 经葡萄酒和玻璃两个连续数据集的验证 , 表明该方法效果良好 , 适用于化学分类数据挖掘 。2 决策树的基本概念和方法决策树为树结构分类器 , 由内部节点 (包括根节点 和叶节点构成 , 每个内部节点表示一个属性测 试 , 测试的每个可能结果将输出一个分枝或子树 , 最后生成的叶节点表示一个类 。 2. 1 决策树的生成和应用决策树的生长是通过对训练样本不断分组长

4、出分枝 。 当一组数据的分组不再有意义时 , 相应的分 枝就停止生长 。 当所有数据的分组都无意义时 , 决策树的构建就完成了 。为防止决策树“ 过于精确 ” 影 响推广性 , 可采用预修剪的方式提前终止分枝与树的生长 。 决策树生成后 , 从其根节点到叶节点的每条 路径可构建为分类规则 。 对于待分类的对象 , 按规则选择属性值所满足的路径 , 到达叶节点以确定类别。 2. 2 判定属性的选择判据为导出结构简单的决策树 , 可以以信息增益 、 信息熵等为判据 , 选择判定属性 。样本集 S 的容量为n, 它有 m 类 :C i (i =1, 2, , m , C i 的容量为 n i , 为

5、个体分类的期望信息如 (1 式所示 。其中 p i 为个体属于 C i 的概率 P i =n i /n 。I (S =-6mi =1log (P i (1设属性 A 有 v 个值 a 1, a 2, , a v , 由 A 可将 S 分为 v 个子集 S 1, S 2, , S v , n ij 为 S j 中归属 C i 类的个 体数 。 以 A 为判定属性 , 由 A 划分子集的信息熵和信息增益如式 (2 和式 (3 所示 :E (A =6vj =1I (S j (n 1j + +n m j /n (2 Gain (A =I (S -E (A (3第 33卷2005年 8月 分析化学 (F

6、E NX I HUAXUE 研究报告 Chinese Journal of Analytical Chem istry 第 8期109110942. 3 C4. 5算法及其改进传统的决策树算法通常只用于处理离散型数据 , C4. 5算法也可处理连续数据 , 通常对连续数据排 序 , 以相邻两值的中点为阈值 , 将所有样本记录分为大于和小于阈值两部分 , 方式较为单一 , 分类效果受 限 6。 本研究则先对数据预处理 , 包括离散化连续属性和特征筛选 , 然后再应用 C4. 5算法 。3 数据预处理3. 1 连续属性的离散化离散化就是找出区间划分的断点 , 划分数越少越好 7。基于信息熵的最小描

7、述长度划分法 8 (m ini m um descri p ti on length partiti on,MDLP , 先对连续属性的取值排序 , 以不同类别的分界点作为划分 断点的候选点 9, 考察它们可否为最终划分断点 , 其选择过程先假设样本 S 的容量为 n, 以连续属性 A的某一候选点将 S 划分为 S 1 和 S2, 容量分别为 n 1、 n 2, 按 (1 式算出 I (S 1 , I (S 2 , 其划分信息熵为 : E (A =n 1I (S 1 +n 2I (S 2 /n (4按式 (3 计算 Gain (A , 其中的 E (A 如 (4 式所示 。 进而检查式 (5

8、是否成立 , 若成立 , 该候选点将被选 为划分断点 。Gain (A >log 2(n -1 +(A, S 1, S 2 /n (5 其中 , (A, S1, S 2 =l og (3k -2 -k 3I (S -k 13I (S 1 -k 23I (S 2 ,而 k 、 k 1、 k 2分别为 S 、 S 1、 S 2所含 的类别个数 。3. 2 特征选择剔除对分类无显著影响的属性可减少工作量 , 获取简洁的分类目标模式 ; 可消除属性间的相互干 扰 , 提高分类的准确性 ; 还有助于更直观地理解目标知识模式的专业意义 10。将用于分类的属性称为 特征 , Las Vegas 筛选法

9、 11(Las Vegas Filter, LVF 是一种有效的特征选择法 , 它以不一致率 12作为特征 对分类影响的度量 , 从原有全部特征中随机选取子集 , 计算其不一致率 , 若未超过给定的临界值 , 且其特 征数又小于当前最佳子集的特征数 , 则以该子集替代 , 作为最佳子集 。依次循环 , 直至循环数达到规定 的上限 。4 化学分类知识模式的挖掘4. 1 两个化学样本数据集玻璃 (glass 和葡萄酒 (wine 两个数据集均取自 UC I 数据库 13。 玻璃按其性能分为门窗玻璃和非 门窗玻璃两类 , 两类的化学成分组成有所不同 。玻璃数据集的样本容量为 214, 有 9个连续属

10、性 , 分别 为折射率 (R I , 以及 Na 、 Mg 、 A l 、 Si 、 K 、 Ca 、 Ba 和 Fe 8种化学元素在其对应的氧化物中的质量百分含量 , 可将它们作为衡量指标确定玻璃种类 。葡萄酒数据为产于意大利同一地区不同种植园的 3种葡萄酒的成分分析样本 。容量为 178, 共有 13个属性 , 分别为酒精度 、 灰分及其碱度 、 Mg 含量 (mg/L 、 酒的色度 、 色调 、 经稀释后的吸光度比值 OD280/OD315(OD280/OD315of diluted wine 、 以及下列成分在葡萄酒中的浓度 :苹果酸 (g/L 、 酚类 (mg/L 、 黄烷类 (mg

11、/L 、 非黄烷类 (mg/L 、 原花色素类 (mg/L 、 脯氨酸 (mg/L , 也可由这些属性确定 葡萄酒出产的种植园 。4. 2 数据挖掘的步骤与结果分析为从这两个数据集中挖掘分类目标知识模式 , 将先进行数据预处理 , 包括连续属性的离散化和特征 筛选 , 再据此构建决策树 , 并以其作为分类器 , 由样品各属性取值判定其类别 。4. 2. 1 连续属性的离散化 采用 MDLP 方法对两数据集的各属性离散化 , 结果列于表 1和表 2中 , 包 括初始候选点数 、 划分断点数以及划分断点的取值 。 从表 1和表 2可见 , 离散化效果十分明显 。 各属性 的初始候选点有几十至上百个

12、 , 离散化后只划分为 2至 6段 , 各属性取值对个体分类的影响更趋清晰 。 4. 2. 2 特征选择 采用 LVF 方法对离散化后的两个数据集进行特征选择 , 设定搜索循环的上限为 1000次 , 不一致率的临界值为 0. 05。 筛选结果列于表 3中 , 包括原有特征数 、 所选特征数和所选特征 ,所选特征按 4. 1节列出的顺序以序号标识 。 由表 3可见 , 特征选择后两数据集都有 较大约简 。 玻璃的特征从 9个降至 5个 , 葡 萄酒的从 13个降至 3个 , 降幅很大 。这样 可简化计算处理 , 还可消除冗余特征的干 扰 , 提高决策树的推广能力 , 也便于专业人 员分析各特征

13、对分类的影响 。4. 2. 3 决策树的构建与性能 采用 C4. 5算法为预处理后的数据集构建决策树 (简 称预处理决策树 , 为全面检测其分类性 能 , 将以交叉验证方式实施 , 对玻璃 、 葡萄酒 表 1 玻璃数据集属性离散化结果属性A ttributes初始候选点数Number of initialcutting points划分断点数Number ofcutting points划分断点 Cutting points折射率Refractive index 15111. 51556 Na 115313. 99 14. 36 14. 86 Mg 8612. 68A l 10231. 71

14、2. 09 2. 12 Si 107373. 27 73. 88 74. 45 K 5210. 05Ca 11216. 96Ba 2910. 27表 2 葡萄酒数据集属性离散化结果Table 2 The result of attributes discretizati on of the wine dataset属性 A ttributes初始候选点数Number of initialcutting points划分断点数Number ofcutting points划分断点 Cutting points酒精度 A lcohol 103512. 17 12. 79 13. 49 13. 71

15、 13. 88灰分 A sh 6112. 02灰分碱度 A lkalinity of ash 48417. 8 19. 4 20. 5 27Mg 39389 104 132色度 Col or intensity 11233. 4 4. 8 7. 5色调 Hue 6440. 78 0. 92 0. 96 1. 28吸光 度 比 (OD280/OD315The rati o of abs orbances 9522. 11 2. 47苹果酸 Malic acid 10241. 41 2. 16 3. 91 4. 04总酚 Total phenols 7231. 83 2. 32 2. 61黄烷类

16、Flavanoids 11430. 96 1. 57 2. 29非黄烷类 Nonflavanoid 2840. 34 0. 48 0. 5 0. 63原花色素类 Pr oanthocyanins 7641. 26 1. 54 1. 56 2. 96脯氨酸 Pr oline 1024166 750 885 985数据集分别按序每次取出 21、 18个个体作为测试 样本 , 其余作为训练样本用于构建决策树 。 所建决 策树对训练样本检测的正确率 , 称为自检正确率 , 对测试样本的为预报正确率 。两种正确率的均值 列于表 4。为作对照比较 , 以同样的交叉验证方 式 , 采用 C4. 5算法对未经

17、预处理的数据集构建决 表 3 特征选择的结果Table 3 The result of feature selecti on数据集Dataset原有特征数Number oforiginalfeatures所选特征数Number ofselected features所选特征序号 No . of selected feature玻璃 Glass 952 3 4 5 6葡萄酒 W ine 1336 10 13策树 (简称单一决策树 , 并用现代统计的贝叶斯判别方法 14建立贝叶斯分类模型 , 其检测正确率也列 于表 4。 从表 4可见 , 贝叶斯模型和单一决策树的自检正确率很高 , 但预报正确率却

18、较低 。贝叶斯判别 法 对样本分布有一定要求 , 这就限制了算法的通用性 , 使对预报正确性不高 。 而直接处理连续属性的表 4 3种方法建模的性能比较Table 4 The comparis on of three models比较项目 Comparative item s贝叶斯分类模型Model of Bayes discri m inant自检正确率Correctself 2check rate预报正确率Correctp redicti on rate处理连续属性的 C4. 5决策树C4. 5decisi on tree f orcontinuous attributes自检正确率Cor

19、rectself 2check rate预报正确率Correctp redicti on rate基于预处理数据的 C4. 5决策树 C4. 5Decisi on tree f or p retreat m ent data自检正确率Correctself 2check rate预报正确率 Correct p redicti on rate玻璃 Glass (% 98. 1986. 6798. 8289. 8295. 5094. 76葡萄酒 W ine (% 99. 2390. 5698. 8493. 2496. 8896. 67C415算法 , 其处理方法较为单一 , 又未消除冗余数据 ,

20、易使决策树过于细化 , 与训练样本完全吻合 , 各叶 节点仅呈现少数训练样本的数据特点 , 失去了代表性 , 影响了决策树的分类推广能力 。为此 , 可先将连 续属性离散化 , 再剔除冗余属性 , 为 C4. 5算法提供适用的数据 , 以此构建的决策树可避免过于细化 。此时自检正确率虽有所下降 , 但预报正确率却明显提高 , 具有较强的推广能力 , 而这是考察分类器优劣 的最重要的标志 。预处理决策树可导出简洁的分类规则 。 以葡萄酒为例 , 可列举其中两条规则 :(1 若样品的黄烷类 浓度大于 2. 29, 而脯氨酸浓度大于 750时 , 它归属于第一类 。脯氨酸浓度小于或等于 750时 ,

21、 则为第二 类 ; (2 若样品的黄烷类浓度在 1. 57和 2. 29间 (含上限 , 它归属于第二类 。这些规则直观明确 , 统计 模型和神经网络无法与之相比 ; 可直接分析数据间的联系 , 发现蕴藏其中的有用知识和规律 。References1 Han J, Ka mberM , D ata m ining:Concepts and Techniques , Morgan Kauf mann Publishers, 20002 Zhang Haixia (张海霞 , Zhang Ruisheng (张瑞生 , L iu Mancang (刘满仓 , Hu Zhide (胡之德 , Fan

22、 B T . Chinese J. A nal . Che m. (分析化学 , 2000, 28(9 :133613433 Shu Zhiheng (束志恒 , Fang Shi (方 士 , Chen Dezhao (陈德钊 , Chen Yaqiu (陈亚秋 . Chinese J. A nal . Che m. (分 析化学 , 2003, 31(10 :116911724 Quinlan J R. M achine L earning , 1986, 1:811065 Quinlan J R. C 4. 5:Program s forM achine L earning, Morga

23、n Kauf mann, 19936 Quinlan J R. Journal of A rtificial Intelligence R esearch , 1996, 4:77907 L iu H, Hussain F, Tan C L, Dash M. M achine L earning and Kno w ledge D iscovery, 2002, 6:3934238 Dougherty J, Konavi R, Saha m iM. In Proceeding of I C M I 295, 12th International Conference on M achine L

24、 earning, Morgan Kauf mann, 1995:1942029 Fayyad U, Irani K . In Proceedings of IJCA I 293, 13th International Joint Conference on A rtificial Intelligence , Morgan Kauf 2 mann, 1993:1022102710 Dash M , L iu H. Intelligent D ata A nalysis , 1997, 1:13115611 Dash M , L iu H. A rtificial Intelligence ,

25、 2003, 151:15517612 L iu H, Seti ono R. Expert Syste m w ith A pplication, 1998, 15:33333913 M ur phy P M , Aha D W. UC I Repository of M achine L earning D atabase , 199614 Chen Dezhao (陈德钊 . M ultivariate Processing (多元数据处理 . Beijing (北京 :Che m ical I ndustry Press (化学工业出 版社 , 1998D ec isi on Tree

26、 Ba sed on Pretrea t m en t and Its Appli ca ti oni n Chem i ca l Da t a M i n i n gL i L in, Chen Dezhao 3, Shu Zhiheng, Ye Ziqing(D epart m ent of Che m ical Engineering, Zhejiang U niversity, Hangzhou 310027Abstract Che m ical data m ining can discover valuable knowledge fr om a large a mount of

27、data . A s a data m ining technique, decisi on tree is an i m portant t ool . Considering its li m itati on in dealing with continuous data 2 sets . The p retreat m ent including discretizati on and feature selecti on was used t o discretize continuous data and reduce the redundant attributes . Based on these step s, app