ID3算法及其改进.doc

 总第 240 期 2009 年第 10 期 计算机与数字工程 Co mp ut er Digital Engineering Vol . 37 No . 10 19 3 ID3 算法及其改进 徐 雯 张 扬 (中国地质大学计算机学院 武汉 430074) 摘 要 文章对 ID3 算法的基本概念和原理进行了相应的详细阐述以及解释说明 ,并针对 ID3 算法倾向于取值较多的 属性的缺点 ,引进信息增益率对 ID3 算法作了改进 ,并通过实验对改进前后的算法进行了比较 ,实验表明 ,改进后的算法行 之有效 。 关键词 决策树 ID3 算法 信息增益 增益率 中图分类号 T P301 . 6 I D 3 Al go ri t h m a n d I ts I mp r o ve m e n t Xu We n Z h a ng Ya ng ( D ep a r t me n t of C o mp ut e r Scie nc e C olle ge , C hi na U ni ve rsi t y of Ge osci e nc es , W u h a n 430074) A bs t r a c t Th e a r t icle l a r gel y desc ri bes a n d e xp l ai ns t he basic c o nc ep t a n d t he p ri ncip le of de cisi o n t r e e I D 3 al g o2 ri t h m , h ow e ve r , decisi o n t r e e I D 3 al go ri t h m t e n ds t o c h o ose a t t ri b ut es t h a t a r e s a mp le d m o r e of t e n , s o f oc usi n g o n t his def icie nc y . T he p ap e r i nt r o duc e gai n r a t i o t o i mp r o ve t h e I D 3 al go ri t h m , a n d t he n c o mp a r e t he o ri gi n al al go ri t h m w i t h t he m o dif i e d al go ri t h m by e xp e r i me n t , w h os e r es ul t p r o ves t he i mp r o ve d al g o ri t h m m o r e ef f ici e n t t h a n o ri gi n al o ne . Ke y w o r ds de cisi o n t r e e , I D 3 al go ri t h m , i nf o r m a t i o n gai n , gai n r a t i o Cl a s s N u m b e r T P301 . 6 再设一个属性 A 取 v 个不同的值 { a1 , a2 , , av } 。 1 引言 数据挖掘是在大量的数据中发现潜在的 、有价 利用属性 A 可 以 将 集 合 S 划 分 为 v 个 子 集 { S1 , , S v } , 其中 S j 包含了 S 集合中属性 A 取 a j S2 , 值的模式和数据间关系的过程[ 1 ] 。而在处理实际 的各类问题中 ,决策树 ID3 算法会偏向于选择取值 较多的属性 ,本文针对这个不足之处 ,对 ID3 算法 作了改进 , 并 通过 实 验验 证改 进 后的 算法 是 有 效 的 。 值的数据样本 。若属性 A 被选为测试属性 , 设 S ij 为子集 S j 中属于 C i 类别的样本数 。那么利用属 性 A 划分当前样本集合所需要的信息熵为 : v + S + + S S 1 j 2 j mj E ( A ) = ∑ I ( S 1 j , , S mj ) ( 2) s j = 1 S 1 j + S 2 j + + S mj 其中 是由所有子集中属性 A 取 2 ID3 算法原理 设 S 为一个包含 s 个数据样本的集合 , 其类别 s a j 值的样本数之和除以 S 集合中的样本总数 。 E ( A ) 计 算 结 果 越 小 , 就 表 示 其 子 集 划 分 结 果 越 “纯”。而对于一个给定子集