数据挖掘与知识发现(讲稿4---决策树学习技术)

1、1 /221 / 22第四章 决策树（decision tree）决策树也是归纳学习中常用的一种知识表示形式，常用于分类。同时，也是发 现概念描述空间的一种有效方法。决策树的主要优点是描述简单，分类速度快，特 别适合大规模的数据处理。教学目的：掌握决策树学习的概念重点掌握ID3ID3学习算法以及决策树的构造 了解目前常用的决策树改进方法4.14.1概念描述空间的归纳学习归纳学习旨在从大量的经验数据中归纳抽取出一般的规则和模式，因而成为知识获取的主要手段，在专家系统、模式识别、图像处理、语音识别等领域都有重要 应用。归纳学习是机器学习最核心、最成熟的分支。示例数字识别应用：假设有三类数字，即0，

2、1, 2。每类有两个例子，每个例子有四个属性描述，即孔数（#hole）、端点数（#end）、交叉点数（#crosS）、右上 弧数（#right-arc）。如表所示。例子国CIDSIS廉1答肚ate类1O10012C120031020041033015202215212412可归纳产生三类数字的如下规则：0 类：#hole=1#cross=01类：#hole=0#right-arc=02类：#end=2#right-arc=1归纳学习是符号学习中研究得最为广泛的一种方法。思想是：给定关于某个概念的一系列已知的正例和反例，从中归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新

3、的理论 。它的一般操作是2/222 / 22泛化和特化。泛化用来扩展某一假设的语义信息，使其能包含更多的正例，应用于 更多的情况；特化是泛化的相反操作，用于限制概念描述的应用范围。示例假设我们被要求从一副扑克牌中选择一张牌，如果选到好牌就可以获奖。已 知前面被抽出的牌有：梅花4、梅花7、黑桃2、红桃5和黑桃J,其中前三 张都获奖，后两张没有获奖。试用归纳学习帮助选择能获奖的好牌。解：取纸牌的一组属性：y-花色（Suit）和阶V2-（ Rank）,女口：梅花4显然，纸牌的示例空间V V就是所有牌的集合。它是由属性 Suit和Rank所定 义的，其中，属性Vi,V2的可观察值集合为：Vcl u b

4、s,s p a d,edsi a m o nhdesa rt-s-梅花、黑桃、方块、红桃V =1,2,3,4,5,6,7,8,9,10, J,Q,K每个示例就是单张牌。设X X是一组确定属性决定的示例空间 （如，V1 V2）; H是定义在X上的假设空 间（如, H=梅花4、梅花7、黑桃2、红桃5和黑桃J ），也就是用X的属性按一 定的逻辑形式定义的一组概念。Q是定义在X上的目标概念c的示例有限集，我们 定义Q的描述空间是由H中适合Q的全部示例的假设构成的集合。如果示例空间是有限的，且目标概念c是H的成员。当新的示例添加到Q中时, Q描述空间将收缩，最终直到仅包含目标概念 c,这时称描述空间被穷

5、尽。对描述空间可以用描述图来表示，它是一个无回路的有向图，其中各节点是描述 空间的元素。如果从节点p到q有一条弧，当且仅当下面两条性质成立：p比q特殊；不存在节点r，它比p普遍，比q特殊。取PE=梅花4、梅花7、黑桃2为正例；NE=红桃5和黑桃J 为反例。这样对，梅化4是冃疋示例，其描述图为ba*ba*bnbnbjTbjT黒桃2怒加反例黑桃J於 后的矗述国加石的搐述国这里，c clubs; b-black; n-num; a-any-suit 或 any-rank。图中从左至U右表示 suit从特殊到普遍，垂直方向从下到上表示Rank从特殊到普遍；ba表示的概念为梅花4鞫腹的椅述国C3 -*

6、baf .aa 43/222 / 22（suitblaOk （Ra nkan y r a n）k,即所有黑色的牌。这时增加新的示例，如梅花7,能修剪描述空间。删除三个涉及阶是 4的概念，因为 它们不能覆盖该肯定示例，得到新的描述图。同理，由否定示例红桃5可修剪掉aa和an,因为这两个概念覆盖该否定示例；肯定示例黑桃 2剪掉梅花，最后由否定示 例黑桃J将描述空间缩小到单个概念bn,即黑色数字牌。4.24.2决策树学习决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用 信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有样 本信息中信息量最大的属性。中间结点是以

7、该结点为根的子树所包含的样本子集中 信息量最大的属性。决策树的叶结点是样本的类别值。决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则 的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递推方式，在决策 树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分枝，在 决策树的叶结点得到结论。所以，从根结点到叶结点的一条路径就对应着一条合取 规则，整棵决策树就对应着一组析取表达式规则。决策树的内部结点是属性或属性集，称为测试属性；叶结点是所要学习划分的 类。先用训练实例集产生决策树，然后用其对未知实例集进行分类。对实例进行分类时，由树根开始对该对象的属性逐渐测试

8、其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。例如一棵基于表1中数据的用于检测网络入侵行为的决策树。这个决策树，用IP端口和系统名称标示内部结点，用入侵和正常表示叶结点， 如下图描述。表1入侵数据例子System nameIP PoriSystem nameCategoiyApollo yf Arte inis004020ArtemisHoimal0D4020ApolloIntrusiohIF PortNormal002210ArtemisHortnal/002210ApolloIntrusiDii000010 004020000010ArtemisNomi

9、al/(J02000010ApolloNormalWoermal决策树可转换成如下的规则：(C+C+表示)If (System n ame=Artemis)4/222 / 22In trusi on=false;ElseIf (IP port=002210) In trusi on=true; else if (IP port=004020)In trusi on=true;Else if (IP port=000010) In trusio n=false;根据决策树的各种不同属性，有以下几种不同的决策树：决策树的内结点的测试属性可能是单变量的，即每个内结点只包含一个属性，也可能是多变量的，

10、即存在包含多个属性的内结点；根据测试属性的不同属性值的个数，可能使每个内结点有两个或多个分支。如果每个内结点只有两个分支，则称之为二叉树决策树；每个属性可能是值类型，也可能是枚举类型；分类结果既可能是两类，也可能是多类。如果二叉决策树的结果只能有两类，则称之为布尔决策树。对布尔决策树可很容易以析取范式的方式表示。如下图为 （X3 X2） （X3 X4 一xj的析取范式另外，所有的决策树学习都有一些等价的网络表示形式。如上图的人工神经网 络与决策树表达了同一个析取概念（3 X2） （X3 X4 XJ，所执行的功能相同。4.34.3 CLSCLS学习算法概念学习系统（CLS: Concept Le

11、arning System 是1966年由Hunt等人提出的, 是早期决策树学习算法，后来的决策树学习算法均可视为CLS算法的改进和更新。CLSCLS算法的主要思想是：从一个空的决策树出发，选择某一属性（分类属性） 作为测试属性，该测试属性对应决策树中的决策结点，根据该属性值的不同，可将 训练样本分成相应的子集。如果该子集为空，或该子集中的样本属于同一类，则该 Jt示AJC A-5/222 / 22子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点。需再选择一个 新的分类属性对该子集进行划分，直至所有的子集者为空或属于同一类为止。例如，假设有一组人，眼睛和头发的颜色及所属的人种情况如下

12、表：人员服睛硕色头垸靈色所属人种1黑色黒色董种人2金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色全芭混血儿7灰色黑色温血儿8蓝色黒色混血儿假设首先选择眼睛颜色作为测试属性，贝以该结点引出三个分支图：选择眼睛颜色作为决策属性这三个分支将样本集分成三个子集1，6、2，4，8和3，5, 7。但这三个子集 中的元素都不属于同一结果类，因此它们都不是叶结点，需要继续划分，即需要添 加新的测试结点。女口 头发颜色，由于头发颜色=黑色，金色，红色，所以从子 集中可引出三个新的分支：通过增加结点逐步求精，直到生成一棵能正确分类训练样本的决策树。学习算法CLS算法的步骤可描述为：令决策树T的初

13、始状态只含有一个树根（X，Q），其中X是全体训练实例 的集合，Q是全体测试属性的集合；若T的所有叶结点（X,Q）都有如下状态：或者第一个分量 X中的训练6/222 / 22信源 P(Y | X) X信宿Y其中,实例都属于同一个类，或者第二个分量Q为空，则停止执行学习算法，学 习的结果为T ；否则，选取一个不具有步骤所述状态的叶结点（X,Q）；对于Q，按照一定规则选取测试属性b,设X被b的不同取值分为m个 不相交的子集X；仁im，从（X,Q）伸出m个分叉，每个分叉代表b的 一个不同取值，从而形成 m个新的叶结点（X,Q-b） , H岂m ；转步骤。从CLS的算法描述可以看出，决策树的构造过程也就

14、是假设特化的过程。 但CLS 算法并没有规定采用何种测试属性。然而，测试属性集的组成以及测试属性的先后 都对决策树的学习有着举足轻重的影响。此外，CLS算法所能处理的学习问题不能太大。4.44.4 ID3ID3 （IterativeIterative DichotomizerDichotomizer3 3）学习算法CLSCLS算法的思路是找出最有分辨能力的属性，把数据库划分为许多子集（对应 树的一个分枝），构成一个分枝过程，然后对每个子集递归调用分枝过程，直到所有 子集包含同一类型数据。最后得到的决策树能对新的例子进行分类，但CLS的不足是（1） 没给出如何选取测试属性b；（2） 它处理的学习

15、问题不能太大。为此，Quinlan提出了著名的以属性为分类节点 的ID3学习算法，他是以信息熵 的下降速度作为选取测试属性的标准，通过窗口来形成决策树。信息熵的下降也就是信息不确定性的下降。1 1）信息论简介信息论是由C.E.Shannon （信息论的创始人）1948年为解决信息传递（通信）过 程问题而提出的以数学的方法来度量并研究信息 的理论，也称为统计通信理论。他把一个传递信息的系统 视为，由发送端（信源）、接收端（信宿）和连接两者的通道（信道）三者组成。P（Y |X）称为信道的传输概率或转移概率，它反映信道的输入与输出关系7/222 / 22用矩阵来表示，称为转移概率矩阵。P(Vi|Ui

16、) P(V2|uJP(Vq |Ui)P(Vi|U2) PW2IU2) P(Vq |U2)P(Y|X)=r qP(Vi |Ur) P(V2|Ur) P(Vq|U_q这里， P(Vj |uj =1, i =1,2, ,r。j 4从此通信模型可看出，在进行实际的通信之前，收信者(信宿)不可能确切了 解信源究竟会发什么样的具体信息，也不可能判断信源会处于什么样的状态。这种 情形就称为信宿对于信源状态具有不确定性，而且这种不确定性是存在于通信之前 的，因此又叫做 先验不确定性。在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消 除或者被减少。如果干扰很小，不会对传递的信息产生任何可察觉

17、影响，信源发出 的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。 但是，在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信 息不完全。因此，先验不确定性不能全部被消除，只能部分地消除。换句话说，通 信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性。显然，后验不确定性总要小于先验不确定性，不可能大于先验不确定性。(1)如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿 根本没有收到信息。(2)如果后验不确定性的大小等于零，这就表示作宿收到了全部信息。可见，信息是用来消除(随机)不确定性的度量。信息量的大小，由所消除的不确定性的大

18、小来计量。下面介绍几个概念：信息(符号)Ui ( i =1,2,，r )的发生概率p(Ui)组成信源数学模型(样本空间 或概率空间)：5u2 urX,P=12rILP(Ul) P(U2)P(Ur)自信息量：消息Ui发生后所含有的信息量。即在收到Ui事件之前，收信者对 8/222 / 22信源发出Ui的不确定性，定义为信号符号Ui的自信息量l(Ui)。即l(Ui) =log2log2 P(Ui)P(u其中，P(Ui)为信源发出Ui事件的概率； 信息熵：自信息的数学期望。因为自信息量只能反映符号收到前的不确定性， 而信息熵可以用来度量整个信源 X整体的不确定性，即信源发出信息前的平 均不确定性。定

19、义如下：rE(X)二 P(Ui)l(Ui) P(U2)l(U2)P(Ur)l(Ur)=7. P (Ui ) l 0 g P(U i )i 4其中，r为信源X所有可能的符号数Ui,U2/ ,Ur，即用信源每发一个符号所 提供的平均自信息量来定义信息熵。上式中， 对数底数b可为任何正数，不 同的取值对应熵的不同单位 ，但通常取b=2 ;并规定：当p(uj=o时,P(Ui)log b P(uJ =0。当对数的底为2时，l(u的单位为比特(bit)；当对数的底为e时，l(uj的单位为奈特(nat);当对数的底为10时，l(u)的单位为哈特(hart)；1奈特=1.44比特；1哈特=3.32比特。E(X

20、)的性质如下：E(X) =0时，说明只存在着唯一的可能性，不存在不确定性；如果n种可能的发生都具有相同的概率，即对所有的ui，有P(Ui) =1/n，则E(X)达到最大值log2n，说明系统的不确定性最大；P(ui)互相越接近，E(X)就越大；P(Ui)相差大，则E(X)就小。如果信道中无干扰(噪声)，信道输出符号与输入符号一一对应，那么接收到传 送过来的符号后，就消除了对发送符号的先验不确定性。后验熵一般信道中有干扰存在，信宿接收到符号 V后，对信源发出的是什么符号仍有 不确定性。对此如何度量？当没有接收到输出符号V时，已知发出符号U的概率分布P(U)，而接收到输出 9/222 / 22符号

21、V二Vj后，输入符号的概率分布发生了变化，变成了后验概率分布P(U |Vj)。10/222 / 22n=hil| lLCJX)如果a为X中取有限个不同值$42,，am的属性，样本集X划分为m个不同的子E(X |C- C2IH C,n那么，接收到输出符号V = Vj后，关于U的平均不确定性为:E(U |Vj)八 P(Ui |Vj)log-iP(Ui |Vj)这就是接收到输出符号Vj后关于U的后验熵。即后验熵是当信道接收到输出符号Vj 后，关于输入符号U的信息度量。条件熵后验熵在输出符号集V的范围内是个随机量，所以对于后验熵在输出符号集V中求期望，得到条件熵：E(U |V)八 P(Vj)E(U |

22、Vj)j1八 P(Vj) P(Ui |Vj)log2-(*)j iP(Ui |Vj)这个条件熵称为称为信道 疑义度。它表示在输出端收到全部输出符号 V后，对于输 入端的符号集U尚存在的不确定性(存在疑义)。对U集尚存在的不确定性是由于 干扰(噪声)引起的，如果是一一对应，那么接收到符号集 V后，对U集的不确定 性完全消除，则信道疑义度E(U |V) =0。在决策分类中，假设X是训练样本集，|X|是训练样本数；样本划分为n个不同 的类C-,C2,Cn，则任意样本X属于类Ci的概率为所以，样本X的平均信息熵为集X-,X2，Xm，则由式(* )知，由属性a划分的决策树分类的平均条件熵为mE(X |a

23、) = p(Xj)E(Xj |a)j丘mn=-S p(Xj)迟 p(Ci |Xj)log p(Ci |Xj)j =1i =1若设|Xij |表示为子集Xj中类Ci的样本数，贝U P(Ci|Xj)二1| x |11 / 2210 / 22 信息增益：一般E(X|a)=E(X)，样本分类的熵值发生了变化，即属性 a对于分类提供了信息，熵的变化量称为属性 a对于分类的信息增益Gain(a)，则Gai(a) =E(X)E(X|a) _0(证明略)从上式知，测试属性将减少决策数分类的不确定程度。2 2)ID3ID3学习算法QuinlanQuinlan的ID3ID3算法就是选择使Gain(a)最大的属性作

24、为测试属性，即选择使 E(X|a)最小的属性a a作为测试属性。此外，ID3ID3中还引入了窗口方法进行增量学习 来解决实例过大问题。具体算法为： 选出整个训练实例集X的规模为W的随机子集Xi ；( W称为窗口规模，子 集称为窗口) 以使得式(* )的值最小为标准，选取每次的测试属性，形成当前窗口的 决策树； 顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外，则 训练结束； 组合当前窗口的一些训练实例与某些在中找到的例外，形成新的窗口，转。示例表4.1给出了一个可能带有噪声的数据集合。它有4个属性：Outlook,Temperature Humidity和windy。它被分为两类：P

25、和N分别表示正例和反 例。试构造决策树将数据进行分类。解：因为初始时刻属于P类和N类的实例个数均为12个，所以初始时刻的熵值 为：H(X)12log12-12log12=124242424如果选取Outlook属性作为测试属性，则由式(* )有H (X | Outlook ) ( log _ _ log)_( log _ _ log )24999924_Z(_| o g_)= 0.5 5 2 82477H (X84444114477| Temp )(loglog )(loglog)248888241111111154411(l o gIo 旷)-0.673924555512 / 2211 /

26、22可以看出，H(XOutlook)最小，即有关Outlook的信息对于分类有最大的帮助，提 供最大的信息量，即I(X;Outlook)最大。所以选择Outlook属性作为测试属性，就可 将训练实例集分为三个子集，生成三个叶结点，对每个叶点依次利用上面的过程, 则最终生成如下的决策树:3 3)基于ID3ID3的信息增益的决策树构造算法ID3算法有着广泛的应用，其中较为著名的有C4.5、C5.0系统。C4.5的新功能是它能将决策树转换为等价的规则表示，并且 解决了连续取值的学习问题。12 (-4log 48812 -)+(448 8 log)=0.H (X | Humi )=24121212lo

27、g122412log1212 1284 ,455、 6 ,3333、-log)+ =( -lo-)H (X|Windy )24(-888log8246log66 6/ 5,5、+10( -55-log )=12410log101010表4.1样本数据集属性OutbokTemperatuieHumidityVftndy类1OicasiHotHighNotN2gicsstHotHighVeryN3mastHotHighMediumN4SunnyHotMghNatF5SunnyHotHighMediumP15RainMildH妙NotN1RjainMildHighNtdiumH8RainHotNbn

28、mlNotP9RixiCoolNoanalMediumN10RainHotNormalVeryN11SurmyCoolMorml.VeryP12SurmyGoodNomual.MediumF13Ove nc fistWdHighNotN14OwitastMildHighMediumN15ucastCoolNormalNotF16OitastCoolMcmnalMediumF17RainMildNomialNoti-I1SWdNormalMediumN19OVE ivastMildWomiAlMediumF206 icestMildNormlUetyP21SurmyMildHighVeiyP22

29、SunnyMildHighMediumP23SunnyHotNoiimalNotP24RainMildHighVeiyN918313 / 2212 / 22如果属性A作为决策树的根且A具有v个值，则A可将E分成v个子集ni个反例，那么Ei所需的期望信息是设样本集E共有C类样本，每类样本数为以属性A作为决策树的根,A具有v个值可将E分成v个子集E-E2,Ev。假设Ei中含有j类样本的个数为Pij ， j - 1,2, c 0则子集Ei的信息量为Ell简log 2 Pij(* )(1)(1) ID3ID3算法的基本原理设E=Fi F2Fn是n维有限向量空间，Fj是有限离散符号集，E中的每 一元素e

30、 =(vV2,，vj称为例子，Vj Fj, j =1,2，n。设PE和NE是E的两个例 子集，分别称为正例集和反例集。| PE |= p,| NE |二n，则ID3基于如下两种假设： 在向量空间E上的一棵正确决策树，对任意例子的分类概率同E中正例、反例的概率一致； 一棵决策树对一例子做出正确分类判别所需的信息为i(p,n) p log2 p n p + n p + nEI,E2, ,Ev。假设Ei中含有Pi个正例和 1( Pi, nJ，以属性A为根分类所需的期望熵为v p nE(A)日 I ( Pi, nJ y p + n则A根的信息增益为gai(A) =l(p,n) -E(A)ID3ID3的

31、思想是选择gain(A)最大(即E(A)最小)的属性A作为根结点。其方法 可推广到多类情况。(上面只研究正、反两类)cPi，i h,2, ,c，即 | E |八 pi。若i 二以A为根分类的信息熵为v | Ei |E(A): I(Ei)i | E |所以，选择属性A*使E(A)最小。(2)(2) 建树的算法步骤 对于任意的选择属性A,假设A有v个属性值，对应的概率分别为p, p2,pv14 / 2213 / 22I（A10）151533log 2log 22020 2020202220-0.792815151515115log 2丄=3.11552 1l （中）-bog 21 - ？ log

32、2333送吨心681（优）=0所以,153E（A320 丨（良）20 1 仲）1（优）=2.5016220以属性A扩展，生成v个子结点EI，E2,，Ev , Ei是属性A取i个值时，按照最小的信息熵原理选择的A的后继属性，分别对应的信息熵为I（EI）,I（E2）, ,l（Ev）； 根据公式（* ）计算E（A）； 选择A*使E（A*）最小，将A*作为根属性； 利用步骤的计算结果，建立结点 A*的后继结点EE2,EV; 对所有的Ei，若为叶结点，则停止扩展此结点。否则递归执行的过程。（3 3）应用实例决策树的构造主要分为两个阶段：建树阶段和调整阶段。例如下面以某课堂教学评估数据库中的数据挖掘和知识

33、发现为例。该课堂教学评估指标体系表共分为若干项，经研究可归纳为：教学态度（A6 ）、教学内容（A7 ）、教学方法（A8 ）、教学效果（A9 ）、评价（A.0）共五项，实际数据 见表1所示由于属性初值为连续值，需进行离散化处理。将属性划分为若干个区段，C1:95100 分、C2: 8094 分、C3: 7079 分、C4: 6069 分、C5: 60 分。见表 2 所示。解：去掉属性A1。因为A1对于结论属性而言，无互信息，亦称无信息增益，即gain （AJ = 0。计算测试集的全部信息量:然后计算各结点的信息量I （Ei），如A6gain（A6）=1（几0）-E（A6）二1.7053415 /

34、 2214 / 22AAAAA血192.692 6913392 5592.6287.0586.27SOP85 0587.05390.4592.77S6.2E9 9SO 45438.396.9397.0397.1593.3591491 S384,9788 8591.1695.6556 13S5 3395 9595.65pF59.337.23342S3 1S9 3TS3.2580.67763SO392.S591.4EE 28992 851084.55S4-4779 3EQ 554 65u93393.3791.0790.393.312Pl 0591.7785.686.1591.051387 .S58

35、889.17 87 287 6 5149019590.9386.27 88 9590.951595.296.0739(5392 695 21691.38S.63S3 9E7S591317S7.15S7 534.17873587 151893.0590 486.63E7 1593 05197E.567.377.7573.52087.4P2.4779 132.7即4AAAAAAr1C2C2C2C22C2C2C2C2良C2C2C2C2良4ClClClCl忧5C2C2C2C2罠6ClClClCl忧702C2C3C3良s02C3C3C3中9C2C2C2C2良10C3C3C3C3中11C2C2C20212

36、C2C2C2C2良13C2C2C2C2艮.14C2C2C2C2良15ClClC2C2罠C2C2C2C217C2C2C2C2良12C2C2C2C2良19C3C3C3C3中20C2C2C3C3同理，可计算出ASA8,A信息熵:gai n( A7) =0.65876, gain( As)= 0.411, gain( A9) = 0.5 50 1故取A7为根属性。同样对Ci这一分支继续使用ID3 方法进一步划分，可得到如图所示的决策树。该决策树完全概括了教师教学评估的三个等级的 20个记录。从图中可以看出：教学A7是一重要指标。表1或表2中隐藏的知识有如下几种情况:规则1：IF(A7=C2) THEN

37、(良)规则2：IF(A7 =C3) THEN仲）规则3：IF(A7 = GA9 = C1)THEN(优)规则4：IF(A7 = G a A9 = C 2)THEN(良)即，如果教学内容为良，则课堂教学质量评价等级一定为良；如果教学内容为中, 则课堂教学质量评价等级一定为中；如果教学内容和教学效果均为优，则课堂教学 质量评价等级一定为优；如果教学内容为优而教学效果为良，则课堂教学质量评价 等级为良。因此，从这些规则中，可以归纳出一条重要的知识，就是：教学内容组 织好的老师，其课堂教学质量的综合评价成绩较好。4.54.5 C4.5C4.5 方法表仝16 / 2215 / 22（1）类别Cj的发生概

38、率:心)旦j |T|freq(Cj,T)|T|（2）属性V =Vj的发生概率:/、|T | P（Vi八帀P(5 |Vi|j，I Ti Ik=-j Wfreq(Cj ,T)log 2(freq(C,T)=inf o(T)ID3算法在数据挖掘中占有非常重要的地位。 但是在应用中，ID3ID3算法存在不能 够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。C4.5是在ID3 基础上发展起来的决策树生成算法， 由J.R.Quinlan在1993年提出。C4.5克服了 ID3 在应用中存在的不足，主要体现在以下几个方面：（1）用信息增益率来选择属性，它克服了信息增益选择属性时偏向于选择取值较

39、多的属性的不足；（2）在树构造过程中或者构造完成之后，进行剪枝；（3）能够完成对连续属性的离散化处理；（4）能够对于不完整数据进行处理；（5）C4.5采用的知识表示形式为决策树，并最终可以形成产生式规则。4.5.14.5.1构造决策树设T为数据集，类别集合为G,C2,，Cd，选择一个属性V把T分为多个子集。设V有互不重合的n个值VV2，,vj，则T被分为n个子集卫,，Tn，这里中 的所有实例的取值均为Vi。令|T|为数据集T的例子数，|T |为V的例子数，|Cj卜freq（Cj,T）为Cj类的例子数，|CjV|为V =Vi例子中，具有Cj类别的例子数。则有：（3）属性V二w的例子中，具有类别C

40、j的条件概率:Quinlan在ID3中使用信息论中的信息增益（Gain）来选择属性，而C4.5C4.5采用属 性的信息增益率（GainGain RatioRatio）来选择属性。1 1、类别的信息熵H(C) p(Cj)log2(p(Cj) logC)jj |T |T |2 2、类别条件熵17 / 2216 / 22j |T|Ti|92|CjV|H(V)=二iP(vi)log2(p(vj)送号i二 |T |og(#)=spl _t nO(V)按照属性V把集合T分割，分割后的类别条件熵为:H(C|V)p(Vj) p(Cj |vJlogp(Cj |vjjio(TJ = inf Ov(T)3 3、信息

41、增益，即互信息I (C,V)二H(C)-H(C|V )=in 0(T) - in 0V(T) = g a i(V)4 4、属性V V的信息熵5 5、信息增益率gain _ratio = I (C,V) / H (V) = gain(V)/ split _inf o(V)C4.5对ID3改进是用信息增益率来选择属性。理论和实验表明，采用“信息增益率” （C4.5）比采用“信息增益” （ID3）更好, 主要是克服了 ID3方法选择偏向于取值多的属性的不足。4.5.24.5.2连续属性的处理在ID3中没有处理连续属性的功能。在 C4.5中，设在集合T中，连续属性A的取值为w,v2,，vm，则任何在v

42、i和vi 1之间的任意取值都可以把实例集合分为两部分T1 =t| A Zi和Tt | A vi可以看到，一共有m-1种分割情况。对属性A的m-1种分割的任意一种情况，作为该属性的两个离散取值，重新构 造该属性的离散值，再按照上述公式计算每种分割所对应的信息增益率 gai _ rati（vi），在m-1种分割中，选择最大增益率的分割作为属性A的分枝：T h r e s h W)d= vk其中，ga in _ ratio (vQ二max gai n_ ratio (vj，则连续属性A可以分割为:18 / 2217 / 224.5.34.5.3决策树剪枝由于噪声和随机因素的影响，决策树一般会很复杂。

43、因此，需要进行剪枝操作。1 1什么时候剪枝？剪枝操作有两种策略：（1）在树生成过程中判断是否继续扩展决策树。若停止扩展，则相当于剪去该结点以下的分枝；（2） 对于生成好的树剪去某些结点和分枝。C 4 .5采用的是第二种方法。 剪枝之后的决策树的叶结点不再只包含一类实例。结点有一个分布描述，即该叶结点属于某类的概率。2 2、基于误差的剪枝决策树的剪枝通常是用叶结点替代一个或者多个子树，然后选择出现概率最高 的类作为该结点的类别。在 C4.5中，还允许用其中的树枝来替代子树。如果使用叶结点或者树枝代替原来的子树之后，误差率若能够下降，则就使用 此叶结点或者树枝代替原来的子树。3 3、 误差率的判断

44、设一个叶结点覆盖N个实例，其中E个为错误的。对于具有信任度 CF的实例, 计算一个2项分布，UCF（E,N），该2项分布，即实例的误判概率，那么N个实例判 断错误的数目为N UCF（E,N）。子树的错误数目为所有叶结点的总和。如：注：（）中为覆盖的实例数目设CF=0.25,贝U U该子数的实例判断错误数目为:19 / 2218 / 226 U 0.25 (0,6)9 U 0.25 (0,9)1 U 0.25 (0,1)=6 0.2069 0.143 1 0.750 二 3.273若以一个结点C1代替该子树，则16个实例中有一个错误（C3）,误判实例数目为16xU0.25（1,16） =16 x

45、0.157=2.51 2由于判断错误数目小于上述子树，则以该叶结点代替子树。4.5.44.5.4从决策树抽取规则在C4.5中，从决策树抽取规则需要两个步骤：获得简单规则、精简规则属性。1 1获得简单规则对于已生成的决策树，可以直接从中获得规则。从根到叶的每一条路径都可以是 一条规则。例如，下面的决策树中可以得到规则决策树：F =0J = 0: c I a SDsX = 0: c l a 0s J = 1K =1: cl a Ss* F =1G =1: cl aSsJ = 0: c l a S0sG=0K=0:clas）sJ =1*5 = 1: c l a1a规则：if F =1,G =0, J

46、 =1, K =1 the nclass2 2、精简规则属性在上述获得的简单规则中，可能包含了许多无关的属性。在上面的规则中，条件 F和G的取值对于结论没有任何影响。在不影响规则的预测效果的情况下，可以删 除一些不必要的条件。设规则的形式为R：If A the n class C精简之后的规则为R:If A_ then class C其中，A是从A中删除条件之后的形式 4.64.6决策树的改进算法20 / 2219 / 22E(X,a)l(X,a)V(X,a)|a 二 a)(1)(1) 二叉树算法Kononenko等人认为Quinlan的熵函数并不理想，有偏向于取值较多的属性的毛 病。为了克服

47、这个毛病，Kononenko等人建议限制决策树为二叉树，使得取值多的 属性与取值少的属性有同等的机会。此法已在 ASSISTANT系统中实现。改进思想和缺点见知识发现，史忠植著，清华大学出版社，2002P28-29(2)(2) 按信息比值进行估计的方法由于每个实例关于属性a的取值，需要做试验，计算等，这是需要付出一定代 价的。设属性 a取值印，玄2,，它们拥有的实例个数分别为n?,m，且ka ni二n，其中n为训练实例属于属性a的总数。Qui nlan利用属性a的熵值V(X,a)i 4来定义为了获取实例关于属性 a的取值所需要付出的代价：；niniV(X,a)-logy n n在属性a提供相同

48、的信息量I(X,a)的同时，V(X,a)的取值越小越好。Qui nlan定义 了另一种测试属性选取标准：即选取使得E(X,a)最大的属性a作为测试属性。优点：能有效克服偏向取值多的属性的毛病。缺点：更偏向于选择对统一属性值取值比较集中的属性(即熵值最小的属性)，而并不一定是对分类贡献最大最重要的属性。另外，当属性a只有一个取值时，V(X,a) =0，则 E(X,a)没意义。(3)(3) 按分类信息估值Cendrowska根据属性为实例分类提供了多少有用信息来选取测试属性。将训练 实例分为l类G,C2, ,Cl。设属性a的取值ag,ak，取其中所有|C |=0类，设有m个，定义:F(X,a)二C

49、endrowska认为，应选取使得F(X,a)最大的属性a作为测试属性。(4)(4) 按划分距离估值的方法21 / 2220 / 22PC i j)logPC i 1 j)PG i)De Mantaras建议利用划分距离的办法来选择测试属性。设待分类属性分别属于I 个不同的类Ci,C2,C|，如果有一种划分方法能够把X 一下分为I个子集 Xi,X2，X|，其中每个Xi中的实例恰好属于Ci类，这称之为理想划分。另一方面， 如果根据某个属性的各个可能取值把 X分为子集，这也是一个划分。如果能够在两 个划分之间定义一种距离，则可以在由各个属性定义的划分当中选择离理想划分最 近的那一个，将此属性定为当前的测试属性。De Ma ntaras定义的距离也是以信息和熵为基础的。将H（X,C）简记为H（C）。设：一、宀，:*表示X的某种划分，贝U其信息熵 为mH（：）-八 p（： i）logo（： i）i=1设二】