第5章：基于数据仓库的决策支持系统(3).ppt

《第5章：基于数据仓库的决策支持系统(3).ppt》由会员分享，可在线阅读，更多相关《第5章：基于数据仓库的决策支持系统(3).ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第第5章章基于基于数据仓库的数据仓库的决策支持系统决策支持系统 (3)1第（第（3）部分）部分 5.4 数据挖掘数据挖掘 5.5数据挖掘的决策支持数据挖掘的决策支持 5.5.1 数据挖掘的决策支持分类数据挖掘的决策支持分类 5.5.2决策树与决策规则树的挖掘决策树与决策规则树的挖掘 及其应用及其应用5.4 数据挖掘数据挖掘5.4.1知识发现与数据挖掘概念知识发现与数据挖掘概念5.4.2 数据挖掘方法和技术数据挖掘方法和技术5.4.3 数据挖掘的知识表示数据挖掘的知识表示数据挖掘的兴起数据挖掘的兴起 （1 1）8080年在美国召开了第一届国际机器学习研讨会；年在美国召开了第一届国际机器学习研讨

2、会；（2 2）8989年年8 8月月于于美美国国底底特特律律市市召召开开的的第第一一届届KDDKDD国国际际学学术术会议；会议；（3 3）9595年年在在加加拿拿大大召召开开了了第第一一届届知知识识发发现现和和数数据据挖挖掘掘国国际学术会议；际学术会议；（4 4）我国于）我国于8787年召开了第一届全国机器学习研讨会。年召开了第一届全国机器学习研讨会。5.5.4.1 4.1 知识发现与数据挖掘概念知识发现与数据挖掘概念知识发现（知识发现（KDD）：从数据中发现有用知识的整个过程。从数据中发现有用知识的整个过程。数据挖掘（数据挖掘（DM）：KDD过程中的一个特定步骤，它用专门算过程中的一个特定步

3、骤，它用专门算 法从数据中抽取模式（法从数据中抽取模式（patterns）。）。KDD过程定义过程定义：从大量数据中提取出可信的、新颖的、有用的并能被人理从大量数据中提取出可信的、新颖的、有用的并能被人理解的模式的高级处理过程。解的模式的高级处理过程。“模式模式”可以看成是可以看成是“知识知识”的雏形，经过验证、完善后的雏形，经过验证、完善后形成知识。形成知识。数据源数据源数据数据数据集成数据集成目标数据目标数据预处理后预处理后数据数据转换数据转换数据模式模式知识知识数据选择数据选择预处理预处理数据挖掘数据挖掘数据转换数据转换结果表达和解释结果表达和解释数据准备数据准备数据挖掘数据挖掘结果表达

4、和解释结果表达和解释KDDKDD过程过程5.5.4.2 4.2 数据挖掘方法和技术数据挖掘方法和技术（一）归纳学习方法（一）归纳学习方法 分为两大类：信息论方法（决策树方法）和集合论方法。分为两大类：信息论方法（决策树方法）和集合论方法。1 1、信息论方法（决策树方法）、信息论方法（决策树方法）利用信息论的原理建立决策树或者是决策规则树。利用信息论的原理建立决策树或者是决策规则树。（1 1）ID3ID3方法：方法：QuiulanQuiulan研制的研制的ID3ID3方法是利用信息论中互方法是利用信息论中互信息建立决策树。信息建立决策树。（2 2）IBLEIBLE方方法法：我我们们研研制制的的I

5、BLEIBLE方方法法，是是利利用用信信息息论论中中信信道道容容量量，寻寻找找数数据据库库中中信信息息量量大大的的多多个个字字段段的的取取值值建建立立决决策策规规则树。则树。2 2、集合论方法、集合论方法 （1 1）粗糙集（）粗糙集（Rough SetRough Set）方法方法 对对数数据据库库中中的的条条件件属属性性集集与与决决策策属属性性集集建建立立上上下下近近似似关关系系，对对下下近近似集合建立确定性规则，对上近似集合建立不确定性规则（含可信度）。似集合建立确定性规则，对上近似集合建立不确定性规则（含可信度）。（2 2）关联规则挖掘）关联规则挖掘 在在交交易易事事务务数数据据库库中中，

6、挖挖掘掘出出不不同同商商品品集集的的关关联联关关系系，即即发发现现哪哪些些商商品频繁地被顾客同时购买。品频繁地被顾客同时购买。（3 3）覆盖正例排斥反例方法）覆盖正例排斥反例方法 它是利用覆盖所有正例，排斥所有反例的思想来寻找规则。它是利用覆盖所有正例，排斥所有反例的思想来寻找规则。比较典型的有比较典型的有AQ11AQ11方法、方法、AQ15AQ15方法以及方法以及AE5AE5方法。方法。（二）仿生物技术（二）仿生物技术 仿生物技术典型的方法是神经网络方法和遗传算法。仿生物技术典型的方法是神经网络方法和遗传算法。1 1、神经网络方法：、神经网络方法：包括：前馈式网络、反馈式网络、自包括：前馈式

7、网络、反馈式网络、自组织网络等多个神经网络方法。组织网络等多个神经网络方法。2 2、遗传算法：、遗传算法：这是模拟生物进化过程的算法。这是模拟生物进化过程的算法。它由三个基本算子组成：它由三个基本算子组成：繁殖（选择）、交叉（重组）、变异（突变）繁殖（选择）、交叉（重组）、变异（突变）遗传算法起到产生优良后代的作用，经过若干代的遗传，遗传算法起到产生优良后代的作用，经过若干代的遗传，将得到满足要求的后代（问题的解）。将得到满足要求的后代（问题的解）。（三）公式发现（三）公式发现 在工程和科学数据库中对若干数据项（变量）在工程和科学数据库中对若干数据项（变量）进行一进行一定的数学运算，求得相应的

8、数学公式。定的数学运算，求得相应的数学公式。1 1物理定律发现系统物理定律发现系统BACONBACON BACONBACON发现系统完成了物理学中大量定律的重新发现。发现系统完成了物理学中大量定律的重新发现。2 2经验公式发现系统经验公式发现系统FDDFDD 我们研制了我们研制了FDDFDD发现系统，寻找由数据项的初等函数或发现系统，寻找由数据项的初等函数或复合函数组合成的经验公式。复合函数组合成的经验公式。（四）统计分析方法（四）统计分析方法 利用统计学原理通过对总体中的样本数据进行分析得出利用统计学原理通过对总体中的样本数据进行分析得出描述和推断该总体信息和知识的方法。描述和推断该总体信息

9、和知识的方法。（五）模糊数学方法（五）模糊数学方法 利用模糊集合理论进行数据挖掘，如模糊聚类、模糊分利用模糊集合理论进行数据挖掘，如模糊聚类、模糊分类等。类等。（六）可视化技术（六）可视化技术 利用可视化技术分析数据库，找到潜在的有用信息。利用可视化技术分析数据库，找到潜在的有用信息。5.5.4.3 4.3 数据挖掘的知识表示数据挖掘的知识表示主要有：主要有：规则、决策树、知识基、网络权值、公式。规则、决策树、知识基、网络权值、公式。1、规则、规则 规则知识由规则知识由前提条件前提条件和和结论结论两部分组成两部分组成 前前 提提 条条 件件 由由 字字 段段 项项（属属 性性）的的 取取 值值

10、 的的 合合 取取（与与 ）和析取（或和析取（或）组合而成。）组合而成。结论结论为决策字段项（属性）的取值或者类别组成。为决策字段项（属性）的取值或者类别组成。2、决策树、决策树例如：上例的人群数据库，按例如：上例的人群数据库，按ID3ID3方法得到的决策树如下：方法得到的决策树如下：3、知识基（浓缩数据）、知识基（浓缩数据）例如上例的人群数据库，通过计算可以得出例如上例的人群数据库，通过计算可以得出身高身高是不重要的字段，是不重要的字段，删除它后，再合并相同数据元组，得到浓缩数据如下表：删除它后，再合并相同数据元组，得到浓缩数据如下表：4、网络权值、网络权值 神经网络方法经过对训练样本的学习

11、后，所得神经网络方法经过对训练样本的学习后，所得到的知识是网络连接权值和结点的阈值。到的知识是网络连接权值和结点的阈值。Zy2x1 x2 1y1 T1 T2 w12 w21w11 w22 2 ,=0.5 5、公式、公式 例如，太阳系行星运动数据中包含行星运动周期（旋转一周所例如，太阳系行星运动数据中包含行星运动周期（旋转一周所需时间，天），以及它与太阳的距离（围绕太阳旋转的椭圆轨道的需时间，天），以及它与太阳的距离（围绕太阳旋转的椭圆轨道的长半轴，百万公里），数据如下表：长半轴，百万公里），数据如下表：发现的公式为：发现的公式为：d3/p2=255.5.5 5 数据挖掘的决策支持数据挖掘的决策

12、支持 5.5.1 5.5.1 数据挖掘的决策支持分类数据挖掘的决策支持分类 5.5.2 5.5.2决策树与决策规则树的挖掘及其应用决策树与决策规则树的挖掘及其应用 5.5.3 5.5.3关联规则的挖掘及其应用关联规则的挖掘及其应用5.5.1 数据挖掘的决策支持分类数据挖掘的决策支持分类数据挖掘的分类：数据挖掘的分类：关联分析、时序模式、聚类、分类、偏差检测、预测。关联分析、时序模式、聚类、分类、偏差检测、预测。1、关联分析、关联分析 若两个或多个数据项的取值之间重复出现且概率若两个或多个数据项的取值之间重复出现且概率很高时，它就存在某种关联，可以建立起这些数据很高时，它就存在某种关联，可以建立

13、起这些数据项的关联规则。项的关联规则。2、时序模式、时序模式 通过时间序列搜索出重复发生概率较高的模式。通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。这里强调时间序列的影响。3 3、聚类：、聚类：在数据库中找出一系列有意义的子集，在数据库中找出一系列有意义的子集，即类。即类。4 4、分类：、分类：对数据库中的类，找出该类别的概念描对数据库中的类，找出该类别的概念描述规则。述规则。5 5、偏差检测：、偏差检测：在数据库中找出异常数据。在数据库中找出异常数据。6 6、预预测测：利利用用历历史史数数据据找找出出变变化化规规律律的的模模型型，并并用此模型预测未来。用此模型预测未来。

14、5.5.5.2 5.2 决策树决策树的挖掘及其应用（一）的挖掘及其应用（一）1 1、决策树概念：、决策树概念：决策树是用样本的属性作为结点，用属性的取值作决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。性进行分析和归纳而产生的。决策树方法的原理是信息论决策树方法的原理是信息论，信息论是，信息论是C.E.ShannonC.E.Shannon为解决信息传递（通信）过程问题而建立为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。的理论，也称为统计通信理论。2 2、ID3

15、ID3算法算法n当前国际上最有影响的示例学习方法首推当前国际上最有影响的示例学习方法首推J.R.QuinlanJ.R.Quinlan的的ID3ID3。nID3ID3引进了信息论中的引进了信息论中的互信息互信息，他将其称为，他将其称为信信息增益（息增益（information gaininformation gain），作为特征判别作为特征判别能力的度量，并且将建树的方法嵌在一个迭代能力的度量，并且将建树的方法嵌在一个迭代的中。的中。一、一、ID3ID3基本思想基本思想某天早晨气候描述为某天早晨气候描述为:天气天气：多云多云 气温气温：冷冷 湿度湿度：正常正常 风风：无风无风 在一实体世界中，每

16、个实体用多个特征来描述。每在一实体世界中，每个实体用多个特征来描述。每个特征限于在一个离散集中取互斥的值。例如，设实体个特征限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特征为是某天早晨，分类任务是关于气候的类型，特征为:天气天气 取值为：取值为：晴，多云，雨晴，多云，雨 气温气温 取值为：取值为：冷冷 ，适中，热，适中，热 湿度湿度 取值为：取值为：高高 ，正常，正常 风风 取值为：取值为：有风，有风，无风无风n它属于哪类气候（能否打高尔夫球）呢它属于哪类气候（能否打高尔夫球）呢?n每个实体属于不同的类别，为简单起见，假定仅有两个每个实体属于不同的类别，为简

17、单起见，假定仅有两个类别，分别为类别，分别为P P，N N。在这种两个类别的归纳任务中，在这种两个类别的归纳任务中，P P类和类和N N类的实体分别称为概念的正例和反例。类的实体分别称为概念的正例和反例。n将一些已知的正例和反例放在一起便得到训练集。将一些已知的正例和反例放在一起便得到训练集。n下表给出一个训练集。由下表给出一个训练集。由ID3ID3算法得出一棵正确分类训算法得出一棵正确分类训练集中每个实体的决策树，见图。练集中每个实体的决策树，见图。NO.属性属性类别类别天气天气气温气温湿度湿度风风1晴晴热热高高无无风风N2晴晴热热高高有有风风N3多云多云热热高高无无风风P4雨雨适中适中高高

18、无无风风P5雨雨冷冷正常正常无无风风P6雨雨冷冷正常正常有有风风N7多云多云冷冷正常正常有有风风P8晴晴适中适中高高无无风风N9晴晴冷冷正常正常无无风风P10雨雨适中适中正常正常无无风风P11晴晴适中适中正常正常有有风风P12多云多云适中适中高高有有风风P13多云多云热热正常正常无无风风P14雨雨适中适中高高有有风风N天天 气气湿湿 度度风风晴晴雨雨多云多云高高正常正常有风有风无风无风P PN NN NP PP PID3ID3决策树决策树n决策树叶子为类别名，即决策树叶子为类别名，即P P 或者或者N N。其它结点由实体的特其它结点由实体的特征组成，每个特征的不同取值对应一分枝。征组成，每个特

19、征的不同取值对应一分枝。n若要对一实体分类，从树根开始进行测试，按特征的取若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类直进行到叶结点，实体被判为属于该叶结点所标记的类别。别。n 用图来判本节开始处的具体例子，得该实体的类别用图来判本节开始处的具体例子，得该实体的类别为为P P类。类。n ID3ID3方法就是要从表的训练集构造图这样的决策树。方法就是要从表的训练集构造图这样的决策树。n 实际上，能正确分类训练集的决策树不止一棵。实际上，能正确分类训练

20、集的决策树不止一棵。n QuinlanQuinlan的的ID3ID3算法能得出结点最少的决策树。算法能得出结点最少的决策树。二、二、ID3ID3算法算法（一）主算法（一）主算法 1 1、从训练集中随机选择一个既含正例又含反例的子从训练集中随机选择一个既含正例又含反例的子集（称为集（称为 窗口窗口）；）；2 2、用用“建树算法建树算法”对当前窗口形成一棵决策树；对当前窗口形成一棵决策树；3 3、对训练集（窗口除外）中例子用所得决策树进行对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；类别判定，找出错判的例子；4 4、若存在错判的例子，把它们插入窗口，转若存在错判的例子，把它们

21、插入窗口，转2 2，否则，否则结束。结束。n主算法流程用下图表示。其中主算法流程用下图表示。其中PEPE、NENE分别表示分别表示正例集和反例集，它们共同组成训练集。正例集和反例集，它们共同组成训练集。nPEPE，PEPE和和NENE，NENE分别表示正例集分别表示正例集和反例集的子集。和反例集的子集。n主算法中每迭代循环一次，生成的决策树将会主算法中每迭代循环一次，生成的决策树将会不相同。不相同。训练集训练集PEPE、NENE取子集取子集建窗口建窗口窗口窗口PEPE、NENE生成生成决策树决策树测试测试PEPE、NENE扩展窗口扩展窗口PE=PE+PENEPE=PE+PENE=NE+NE=N

22、E+NE此决策树为此决策树为最后结果最后结果存在错判的存在错判的PEPE，NENE吗吗是是否否ID3ID3主算法流程主算法流程（二）建树算法（二）建树算法 1 1、对当前例子集合，计算各特征的互信息；对当前例子集合，计算各特征的互信息；2 2、选择互信息最大的特征选择互信息最大的特征AkAk；3 3、把在把在AkAk处取值相同的例子归于同一子集，处取值相同的例子归于同一子集，AkAk取几个取几个值就得几个子集；值就得几个子集；4 4、对既含正例又含反例的子集，递归调用建树算法；对既含正例又含反例的子集，递归调用建树算法；5 5、若子集仅含正例或反例，对应分枝标上若子集仅含正例或反例，对应分枝标

23、上P P或或N N，返回返回调用处。调用处。3 3、ID3ID3方法应用实例方法应用实例 对于气候分类问题进行具体计算有：对于气候分类问题进行具体计算有：信息熵的计算信息熵的计算信息熵：信息熵：类别出现概率：类别出现概率：|S|S|表示例子集表示例子集S S的总数，的总数，|u ui i|表示类别表示类别u ui i的例子数。的例子数。对对9 9个正例和个正例和5 5个反例有：个反例有：P P（u u1 1）=9/14=9/14 P P（u u2 2）=5/14=5/14H H（U U）=（9/149/14）loglog（14/914/9）+（5/145/14）loglog（14/514/5）

24、=0.94bit0.94bit 条件熵：条件熵：条件熵计算条件熵计算属性属性A A1 1取值取值vjvj时，类别时，类别u ui i的条件概率：的条件概率：A A1 1=天气天气 取值取值 v v1 1=晴，晴，v v2 2=多云，多云，v v3 3=雨雨在在A A1 1处处取值晴取值晴的例子的例子5 5个，个，取值多云取值多云的例子的例子4 4 个，个，取值雨取值雨的例子的例子5 5 个，故：个，故：P P（v v1 1）=5/14 P=5/14 P（v v2 2）=4/14 P=4/14 P（v v3 3）=5/14=5/14取值为晴取值为晴的的5 5 个例子中有个例子中有2 2 个正例、

25、个正例、3 3个反例，故：个反例，故：P P（u u1 1/v/v1 1）=2/5=2/5，P P（u u2 2/v/v1 1）=3/5=3/5同理有：同理有：P P（u u1 1/v/v2 2）=4/4=4/4，P P（u u2 2/v/v2 2）=0=0 P P（u u1 1/v/v3 3）=2/5=2/5，P P（u u2 2/v/v3 3）=3/5=3/5H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)(4/4)log(4/4)+0)+(5/14)

26、(2/5)log(5/2)+(3/5)log(5/3)(4/4)log(4/4)+0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3)=0.694bit)=0.694bit 互信息计算互信息计算 对对 A A1 1=天气天气 处有：处有：I I（天气）天气）=H H（U U）-H-H（U|VU|V）=0.94-0.694=0.246 bit=0.94-0.694=0.246 bit 类似可得：类似可得：I I（气温）气温）=0.029=0.029 bitbit I I（湿度）湿度）=0.151=0.151 bitbit I I（风）风）=0.048=0.048 bitbit

27、 建决策树的树根和分枝建决策树的树根和分枝 ID3ID3算法将选择互信息最大的特征天气作为树根，在算法将选择互信息最大的特征天气作为树根，在1414个例子中对个例子中对天气的天气的3 3个取值进行分枝，个取值进行分枝，3 3 个分枝对应个分枝对应3 3 个子集，分别是个子集，分别是:F1=1F1=1，2 2，8 8，9 9，1111，F2=3F2=3，7 7，1212，1313，F3=4F3=4，5 5，6 6，1010，1414 其中其中F2F2中的例子全属于中的例子全属于P P类，因此对应分枝标记为类，因此对应分枝标记为P P，其余两个子其余两个子集既含有正例又含有反例，将递归调用建树算法

28、。集既含有正例又含有反例，将递归调用建树算法。递归建树递归建树 分别对分别对F1F1和和F3F3子集利用子集利用ID3ID3算法，在每个子集中对各特算法，在每个子集中对各特征（仍为四个特征）求互信息征（仍为四个特征）求互信息.（1 1）F1F1中的天气全取晴值，则中的天气全取晴值，则H H（U U）=H=H（U|VU|V），），有有I I（U|VU|V）=0=0，在余下三个特征中求出湿度互信息最大，以它在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为为该分枝的根结点，再向下分枝。湿度取高的例子全为N N类，类，该分枝标记该分枝标记N N。取值正常的例子全

29、为取值正常的例子全为P P类，该分枝标记类，该分枝标记P P。（2 2）在在F3F3中，对四个特征求互信息，得到风特征互中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为时全为N N类，该分枝标记类，该分枝标记N N。取无风时全为取无风时全为P P类，该分枝标记类，该分枝标记P P。这样就得到图的决策树这样就得到图的决策树 4 4、C4.5C4.5算法算法 ID3ID3算法在数据挖掘中占有非常重要的地位。但是，算法在数据挖掘中占有非常重要的地位。但是，在应用中，在应用中，ID3ID3算法不能够处理连

30、续属性、计算信息增益算法不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。时偏向于选择取值较多的属性等不足。C4.5 C4.5是在是在ID3ID3基础上发展起来的决策树生成算法，由基础上发展起来的决策树生成算法，由J.R.QuinlanJ.R.Quinlan在在19931993年提出。年提出。C4.5C4.5克服了克服了ID3ID3在应用中存在在应用中存在的不足。的不足。C4.5C4.5的进步的进步 （1 1）用信息增益率来选择属性，它克服了用信息增益用信息增益率来选择属性，它克服了用信息增益选择属性时偏向选择取值多的属性的不足；选择属性时偏向选择取值多的属性的不足；（2 2）

31、在树构造过程中或者构造完成之后，进行剪枝；在树构造过程中或者构造完成之后，进行剪枝；（3 3）能够完成对连续属性的离散化处理；能够完成对连续属性的离散化处理；（4 4）能够对于不完整数据的处理，例如未知的属性值；能够对于不完整数据的处理，例如未知的属性值；（5 5）C4.5C4.5采用的知识表示形式为决策树，并最终可以采用的知识表示形式为决策树，并最终可以形成产生式规则。形成产生式规则。C4.5C4.5构造决策树的算法构造决策树的算法 QuinlanQuinlan在在ID3ID3中中使使用用信信息息论论中中的的信信息息增增益益（gaingain）来来选选择择属属性性，而而C4.5C4.5采采用

32、用属属性性的的信信息息增增益益率率（gain gain ratioratio）来选择属性。来选择属性。信息增益率信息增益率 C4.5C4.5对对ID3ID3改进是用信息增益率来选择属性。改进是用信息增益率来选择属性。理论和实验表明，采用理论和实验表明，采用“信息增益率信息增益率”（C4.5C4.5方法）方法）比采用比采用“信息增益信息增益”（ID3ID3方法）更好，主要是克服了方法）更好，主要是克服了ID3ID3方法选择偏向取值多的属性。方法选择偏向取值多的属性。5.5.5.2 5.2 决策规则树决策规则树的挖掘及应用（二）的挖掘及应用（二）我们于我们于9191年研制的年研制的IBLEIBLE

33、方法方法 IBLEIBLE方法是利用信息论中信道容量来选择属性，比互方法是利用信息论中信道容量来选择属性，比互信息更好。信息更好。IBLE IBLE方法建决策规则树，方法建决策规则树，每个结点由多个属性取值组每个结点由多个属性取值组成，成，各特征的正例标准值由译码函数决定。结点中判别各特征的正例标准值由译码函数决定。结点中判别正反例的阈值是由实例中权值变化的规律来确定的正反例的阈值是由实例中权值变化的规律来确定的。决策规则树决策规则树规则1规则2规则nu1u1u1u2u2u2 决策规则树结点决策规则树结点（1）规则表示形式）规则表示形式 决策规则树中非叶结点均为规则。规则表示为：决策规则树中非

34、叶结点均为规则。规则表示为：特征：特征：A1，A2，.，.Am 权值：权值：W1，W2，.，.Wm 标准值：标准值：V1，V2，.，.Vm 阈值：阈值：Sp，Sn该规则可形式描述为：该规则可形式描述为：（1）sum:=0；（2）对）对i:=1到到m作：若（作：若（Ai）=Vi，则，则 sum:=sum+wi；（3）若）若sum sn，则该例为，则该例为N类；类；（4）若）若sum sp，则该例为，则该例为P类；类；（5）若）若snsum220，判定例子，判定例子1属于属于u1类。类。例子例子2的权和的权和sum=130，有，有100sum220，认为例子，认为例子2不能判，不能判，例子例子3有

35、权和有权和sum=90，有，有sum100，判例子，判例子3的类别的类别为为u2类。类。规则中规则中:A1，A2，.，Am为组成规则的特征为组成规则的特征 W1，W2，.，Wm为对应的权值为对应的权值 V1，V2，.，Vm为对应特征取正例的标准值为对应特征取正例的标准值 测试例子在该特征处取值与标准值相同，则测试例子在该特征处取值与标准值相同，则sum（权和）加上对应权值，否则不加。（权和）加上对应权值，否则不加。Sp，Sn是判是、判非、不能判的阈值。是判是、判非、不能判的阈值。测试例子的权和为测试例子的权和为sum:sumSp时判为是类（时判为是类（u1类）类）sum Sn时判为非类（时判为

36、非类（u2类）类）Snsums1 n 非非1类类 1类类n等价规则为：等价规则为：c=2 d=2 a=1 1n c=2 d=2 b=1 1苯等八类化合物的分类问题苯等八类化合物的分类问题类类正正例例认认对对认认错错正确正确百分百分比比反反例例认认对对认认错错正确正确百分百分比比总总正确正确百分比百分比RQRT60TJ类一类二类三类四类五10220505524195153455241751600000931377568100100100100100155100509999999999999991368448997997999999999191622200087774849699899810010

37、01009043979582999999100100100对八类化合物，对八类化合物，IBLE的平均预测正确率为的平均预测正确率为93.967%。IBLE与与ID3的比较的比较类类IBLE%ID3%RT60TJ类类二二81 77976 78698 33472 20370 64389 322预测正确率预测正确率IBLE比比ID3高出近高出近10个百分点。个百分点。原因分析原因分析IBLE的预测正确率之所以比的预测正确率之所以比ID3高的原因在于：高的原因在于：IBLE用用信道容量作为特征选择量信道容量作为特征选择量，而，而ID3用互信用互信息，息，信道容量不依赖于正、反例的比例，互信息信道容量不

38、依赖于正、反例的比例，互信息依赖训练集中正反例的比例。依赖训练集中正反例的比例。ID3在建树过程中，每次选择一个特征作为结点，在建树过程中，每次选择一个特征作为结点，不能较好地体现特征间的相关性。不能较好地体现特征间的相关性。IBLE在建树过程中每次循环在建树过程中每次循环选择多个特征构成选择多个特征构成规则，变量间的相关性得到较好的体现规则，变量间的相关性得到较好的体现。IBLE决策规则树的特点决策规则树的特点 IBLE的决策规则树中的规则的决策规则树中的规则在表示和内容上与在表示和内容上与专家知识专家知识具有较高的一致性。具有较高的一致性。第一条规则指出第一条规则指出在在m/e=27，50

39、-52，62-65，74-78，89-92，104-105处应有峰。处应有峰。有关文献中认为含苯化合物的重要系列应有关文献中认为含苯化合物的重要系列应是是m/e=38-39，50-52，63-65，75-78，91，105，119，113等。等。比较一下知道，在列出的这比较一下知道，在列出的这16个峰中第一条规则就包含个峰中第一条规则就包含了了12个，而且都是权值较大的峰。个，而且都是权值较大的峰。IBLE决策规则树的特点决策规则树的特点 在训练集中，在训练集中，若正、反例数目变化较大，若正、反例数目变化较大，IBLE得得到的规则具有较好的稳定性。到的规则具有较好的稳定性。IBLE得出的各决策规则树中第一条规则，都含有得出的各决策规则树中第一条规则，都含有相同的相同的41个特征。个特征。在相同的变化下在相同的变化下ID3的决策树头两层的决策树头两层7个重要质量个重要质量中，无共同的特征。中，无共同的特征。习题习题 29，31，32，34，36，37，39，42