第11章基于数据挖掘的知识推理课件

1、数据挖掘技术与应用 陈燕教授第11章 基于数据挖掘的知识推理 大连海事大学本章提纲 知识推理的分类11.1 基于数据挖掘方法的知识推理11.2 小结11.311.1知识推理的分类 11.1.1 非单调推理 11.1.2 非确定性推理 11.1.3 基于规则的推理 11.1.4 基于案例的推理 11.1.1非单调推理 不完全信息处理问题几乎涉及到AI的所有领域，如机器人规划、视觉、诊断、专家系统、逻辑程序设计语言、自然语言理解及数据库等。正是由于在信息不完全下进行的推理的跳跃性，其结论是可证伪的，因此我们说经典的逻辑系统无法解决不完全信息下的推理问题。因为在经典逻辑系统中由已知事实推出的结论是永

2、真的，它决不会在已知事实增加时丧失。即随着它的公理系统的扩大，或者说加入任何公理到任意理论T中得到的新理论T1仍然保持T中的定理的有效性。即有：IF T P AND TT1 THEN T1 P 11.1.1非单调推理 非单调推理至少在三种场合起到作用： （1）非完全知识库； （2）动态变化的知识库； （3）在问题求解时，常常预作一些临时假设，并在问题求解过程中根据当时情况对这些假设进行修正。 11.1.2 非确定性推理 在实际应用中，各种知识表示及处理系统均会面临不良知识结构的问题，这是由于各种知识本身的表达及推理并不像数学或物理等学科那样严格，或在某些情况下不需要那么严格。这一点在各种专家系

3、统中尤为明显。在实际问题求解时，知识处理系统需要对非精确的数据和知识进行“非精确”处理。因此，提出了许多种非确定性推理模型，包括模糊推理、贝叶斯概率推理、D-S证据理论和粗糙集理论等。 11.1.2 非确定性推理 模糊逻辑与模糊推理 贝叶斯网络推理D-S证据方法粗糙集理论 11.1.3 基于规则的推理 基于规则的推理（Rule Based Reasoning, RBR）是基于规则表示的知识系统，是基于领域专家知识和经验的推理，它将专家的知识和经验抽象为若干推理过程中的规则。推理过程如图11.1所示。 11.1.3 基于规则的推理 图11.1 基于规则的一种推理方法 11.1.4 基于案例的推理

4、1982年美国耶鲁大学 Roger Shank首次提出了基于案例的推理（Case Based Reasoning, CBR）理论的认知模型及框架。CBR是以自然界的两大原则为理论前提：（l）世界是规则的，相似的问题有相似的求解方法和过程；（2）事物总是会重复出现的，我们遇到的（相似的）问题或事物总会重复出现的。 11.1.4 基于案例的推理1994年，Aamodt和Plaza指出一个CBR过程主要有四大步骤：（1）检索（Retrieval）相似度较高的案例；（2）复用（Reuse）案例的方法并通过适当推理解决当前问题，生成新问题的初步解决方案；（3）修正（Revise）前述的解决方案使其更符合

5、问题的描述；（4）学习/保留（Retain）新的案例到案例库中，该过程被成为R4模型。但是R4模型有两个不足之处：一是案例、问题和问题的解没有明确分离，二是该模型假定案例及案例库是已经存在的，回避了构建案例库也是CBR过程的一个重要任务。因此，G.Finnie增加Repartition过程，扩充R4模型形成R5模型，为建设案例库和案例检索提供了基于相似的逻辑推理的数学基础。 11.1.4 基于案例的推理CBR系统具有以下特点：（1）高效的记忆能力。CBR系统直接援引过去的知识和经验，避免一切问题从头再来的弊端。不仅可以进行正面的学习，还可以避免以前的错误，从而一开始就可以直指问题的核心。（2）

6、增量式的自主学习能力。CBR系统具有自主学习的功能，是一种增量式学习方法。随着事例的增加，事例库的覆盖度（求解问题的范围）逐渐提高；同时由于事例比规则获取容易，不需要完整的领域模型，通过事例的积累和经验的增加，使事例推理逐步实用化。（3）集成与扩展能力。它可以方便地采用成本较低的原型系统进行开发，在以后的学习过程中不断增加新事例，修改旧事例，提高自己的判断推理能力。11.1.4 基于案例的推理CBR系统一般工作过程如图11.2所示。图11.2 CBR系统一般工作过程 11.2 基于数据挖掘方法的知识推理 11.2.1 基于决策树的知识推理 11.2.2 基于关联规则的知识推理 11.2.3 基

7、于粗糙集的知识推理 11.2.1 基于决策树的知识推理决策树（decision tree）学习是以实例为基础的归纳学习算法，是数据挖掘中经常要用到的一种简单、有效的分类算法。构造决策树的目的是从一组无次序、无规则的事例中找出属性和类别间的关系，以便用它来预测将来未知类别的记录的类别。决策树可以用来分析数据辅助决策，也可以用来预测，它是一种由节点跟有向边组成的特殊的树结构。 11.2.1 基于决策树的知识推理根据层次的不同，节点分为根节点、内部节点和叶节点三类。树的根节点是整个决策树的开始，对应整个样本集，也就是学习的事例集。树的内部节点代表属性或属性的集合，表示的是对某个属性的测试，在内部节点

8、进行属性值的比较，根据不同的属性值判断该节点向下的分支，分支就是分类的判定条件；树的叶节点代表一个类标号。因此从根到叶节点的一条路径就对应着一条合取规则,整棵决策树对应着一组析取表达式规则。 11.2.1 基于决策树的知识推理决策树的算法：构造决策树算法有多种，较有代表性的有Quinlan的ID3算法（Iterative Dichotomiser 3, 迭代二叉树3代），Breiman等人的CART算法，Loh和Shih的QUEST算法Magidson的CHAID算法等。下面我们介绍一下最常用的ID3算法。早期著名的决策树算法是1986年由Quinlan提出的ID3算法。ID3算法用信息增益（

9、Information Gain）作为属性选择度量。信息增益值越大，不确定性越小。因此，ID3总是选择具有最高信息增益的属性作为当前节点的测试属性。信息增益越大，信息的不确定性下降的速度也就越快。11.2.1 基于决策树的知识推理信息熵定义：假设训练样本集T包含n个样本，这些样本分别属于m个类，其中第i个类在T中出现的比例为pi，那么T的信息熵为： （11.1） 11.2.1 基于决策树的知识推理信息熵（简称为熵 Entropy）表示信源的不确定性，熵越大，把它搞清楚所需要的信息量也就越大。从信息熵的计算公式可以看出，训练集在样本类别方面越模糊越杂乱无序，它的熵值就越高；反之，则熵值越低。熵的

10、单位可以相应地是比特（二进制）、铁特（三进制）、笛特（十进制）或奈特（自然单位），其中比特为最常用的表示方法。 11.2.1 基于决策树的知识推理假设属性A把集合T划分成个V子集 ，其中Ti所包含的样本数为ni，如果A作为测试属性，那么划分后的熵就是： （11.2） 11.2.1 基于决策树的知识推理ni/n充当第i个子集的权，它表示任意样本属于Ti的概率。熵值越小，划分的纯度越高。用属性A把训练样本集分组后，样本集的熵将会降低，因为这是一个从无序向有序的转变过程。 信息增益定义为分裂前的信息熵（即仅基于类比例）与分裂后的信息熵（即对A划分之后得到的）之间的差。简单的说，信息增益是针对属性而言

11、的，没有这个属性时样本所具有的信息量与有这个属性时的信息量的差值就是这个属性给样本所带来的信息量。 （11.3） 11.2.1 基于决策树的知识推理ID3算法描述ID3算法以自顶向下递归的分而治之方式构造决策树。ID3算法就是根据“信息增益越大的属性对训练集的分类越有利”的原则来选取信息增益最大的属性作为“最佳”分裂点。算法描述如下：算法：Generate_decision_tree /根据给定的数据集生成一棵决策树输入：训练样本samples，各属性均取离散数值，可供归纳的候选属性集为attribute_list。输出：决策树11.2.1 基于决策树的知识推理1）创建一个节点N；2）if该节

12、点中所有样本samples均为同一个类C then / 开始根节点对应的训练样本3）返回N作为叶节点，以类C标记；4）if attribute_list为空then；5）返回N作为叶节点，标记为该节点所含样本中类别个数最多的类别；/多数表决6）选择attribute_list中具有最高信息增益的属性test_attribute；7）以test_attribute标记节点N；11.2.1 基于决策树的知识推理8）for each test_attribute中的已知值v；/划分samples9）由节点N长出一个条件为test_attribute= v的分枝，以表示该测试条件；10）设sv是tes

13、t_attribute= v的样本的集合；/一个划分11）if sv为空then12）将相应叶节点标记为所含样本中类别个数最多的类别；13）else 将相应叶节点标志Generate_decision_tree(sv,attribute_list-test_attribute)返回的节点。11.2.2 基于关联规则的知识推理基于规则的知识推理系统中的知识一般的描述形式为： IF THEN 利用关联分析我们可以从大量的资料或数据中得到如下形式的关联规则：A B （支持度，置信度） 11.2.2 基于关联规则的知识推理关联规则分析能够挖掘发现大量数据中项集之间有趣的关联或相关联系，展示“属性-值”

14、频繁地在给定数据集中一起出现的条件。产生支持度和置信度分别大于用户给定的最小支持度和最小置信度的关联规则，形成形如“A B”的逻辑蕴涵式。关于关联规则方法的具体介绍请参见第5章“关联规则模型及应用”。 11.2.3 基于粗糙集的知识推理目前，基于粗糙集的规则获取主要有两种模式。模式A由Pawlak 教授于1991年提出，主要思想是通过寻找属性核及去掉多余的属性求出约简的决策表，并从最简决策表中获取相应的确定规则。模式B由Wakulicz-Deja 等人于1997 年提出，主要思想是直接从原始决策表中求取近似集，并运用推理引擎，分别从下近似集中获取确定规则，从上近似集中获取可能规则。 11.2.

15、3 基于粗糙集的知识推理基于粗糙集理论的推理机制的研究过程包括：（1）根据具体问题构造相应的信息系统；（2）对信息系统中的数据和信息（包括含糊和不确定性信息）按照某种准则进行离散化；（3）将离散化后的数据和信息构建成信息表或决策表的形式；（4）利用粗糙集理论中的核、属性约简、属性值约简、相关度等概念来简化信息表或决策表；（5）求出信息表或决策表的核值表；（6）由核值表求出信息表或决策表的简化形式；（7）从简化后的信息表或决策表中求出最佳决策(或推理)算法；（8）比较粗糙推理机制与其他相关的推理机制的异同点，如模糊推理机制、基于DS证据理论的推理机制等；（9）总结归纳出具有普遍意义的粗糙推理机制、模型和方法，如图11.5所示。 11.2.3 基于粗糙集的知识推理图11.5 基于粗糙集的规则推理模式 11.2.3 基于粗糙集的知识推理基于粗糙集的从不完备信息系统获取确定规则的算法具有以下优点：（1）不改变初始不完备信息系统结构；（2）获取的确定规则不受缺省值的影响；（3）获取的是最简