1、数据挖掘技术与应用数据挖掘技术与应用 陈燕教授第11章 基于数据挖掘的知识推理 大连海事大学辽宁省物流航运管理系统工程重点实验室本章提纲 知识推理的分类知识推理的分类11.1 基于数据挖掘方法的知识推理基于数据挖掘方法的知识推理11.2 小结小结11.3辽宁省物流航运管理系统工程重点实验室11.1知识推理的分类知识推理的分类 v11.1.1 非单调推理非单调推理 v11.1.2 非确定性推理非确定性推理 v11.1.3 基于规则的推理基于规则的推理 v11.1.4 基于案例的推理基于案例的推理 辽宁省物流航运管理系统工程重点实验室11.1.1非单调推理 u不完全信息处理问题几乎涉及到AI的所有
2、领域，如机器人规划、视觉、诊断、专家系统、逻辑程序设计语言、自然语言理解及数据库等。正是由于在信息不完全下进行的推理的跳跃性，其结论是可证伪的，因此我们说经典的逻辑系统无法解决不完全信息下的推理问题。因为在经典逻辑系统中由已知事实推出的结论是永真的，它决不会在已知事实增加时丧失。即随着它的公理系统的扩大，或者说加入任何公理到任意理论T中得到的新理论T1仍然保持T中的定理的有效性。即有：IF T P AND TT1 THEN T1 P 辽宁省物流航运管理系统工程重点实验室11.1.1非单调推理 u非单调推理至少在三种场合起到作用：（1）非完全知识库；（2）动态变化的知识库；（3）在问题求解时，常
3、常预作一些临时假设，并在问题求解过程中根据当时情况对这些假设进行修正。辽宁省物流航运管理系统工程重点实验室11.1.2 非确定性推理 u在实际应用中，各种知识表示及处理系统均会面临不良知识结构的问题，这是由于各种知识本身的表达及推理并不像数学或物理等学科那样严格，或在某些情况下不需要那么严格。这一点在各种专家系统中尤为明显。在实际问题求解时，知识处理系统需要对非精确的数据和知识进行“非精确”处理。因此，提出了许多种非确定性推理模型，包括模糊推理、贝叶斯概率推理、D-S证据理论和粗糙集理论等。辽宁省物流航运管理系统工程重点实验室11.1.2 非确定性推理 u模糊逻辑与模糊推理 u贝叶斯网络推理u
4、D-S证据方法u粗糙集理论 辽宁省物流航运管理系统工程重点实验室11.1.3 基于规则的推理 u基于规则的推理（Rule Based Reasoning,RBR）是基于规则表示的知识系统，是基于领域专家知识和经验的推理，它将专家的知识和经验抽象为若干推理过程中的规则。推理过程如图11.1所示。辽宁省物流航运管理系统工程重点实验室11.1.3 基于规则的推理 图11.1 基于规则的一种推理方法 辽宁省物流航运管理系统工程重点实验室11.1.4 基于案例的推理u1982年美国耶鲁大学 Roger Shank首次提出了基于案例的推理（Case Based Reasoning,CBR）理论的认知模型及
5、框架。CBR是以自然界的两大原则为理论前提：（l）世界是规则的，相似的问题有相似的求解方法和过程；（2）事物总是会重复出现的，我们遇到的（相似的）问题或事物总会重复出现的。辽宁省物流航运管理系统工程重点实验室11.1.4 基于案例的推理u1994年，Aamodt和Plaza指出一个CBR过程主要有四大步骤：（1）检索（Retrieval）相似度较高的案例；（2）复用（Reuse）案例的方法并通过适当推理解决当前问题，生成新问题的初步解决方案；（3）修正（Revise）前述的解决方案使其更符合问题的描述；（4）学习/保留（Retain）新的案例到案例库中，该过程被成为R4模型。但是R4模型有两个
6、不足之处：一是案例、问题和问题的解没有明确分离，二是该模型假定案例及案例库是已经存在的，回避了构建案例库也是CBR过程的一个重要任务。因此，G.Finnie增加Repartition过程，扩充R4模型形成R5模型，为建设案例库和案例检索提供了基于相似的逻辑推理的数学基础。辽宁省物流航运管理系统工程重点实验室11.1.4 基于案例的推理uCBR系统具有以下特点：（1）高效的记忆能力。CBR系统直接援引过去的知识和经验，避免一切问题从头再来的弊端。不仅可以进行正面的学习，还可以避免以前的错误，从而一开始就可以直指问题的核心。（2）增量式的自主学习能力。CBR系统具有自主学习的功能，是一种增量式学习
7、方法。随着事例的增加，事例库的覆盖度（求解问题的范围）逐渐提高；同时由于事例比规则获取容易，不需要完整的领域模型，通过事例的积累和经验的增加，使事例推理逐步实用化。（3）集成与扩展能力。它可以方便地采用成本较低的原型系统进行开发，在以后的学习过程中不断增加新事例，修改旧事例，提高自己的判断推理能力。辽宁省物流航运管理系统工程重点实验室11.1.4 基于案例的推理uCBR系统一般工作过程如图11.2所示。图11.2 CBR系统一般工作过程 辽宁省物流航运管理系统工程重点实验室11.2 基于数据挖掘方法的知识推理基于数据挖掘方法的知识推理 v11.2.1 基于决策树的知识推理基于决策树的知识推理
8、v11.2.2 基于关联规则的知识推理基于关联规则的知识推理 v11.2.3 基于粗糙集的知识推理基于粗糙集的知识推理 辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理u决策树（decision tree）学习是以实例为基础的归纳学习算法，是数据挖掘中经常要用到的一种简单、有效的分类算法。构造决策树的目的是从一组无次序、无规则的事例中找出属性和类别间的关系，以便用它来预测将来未知类别的记录的类别。决策树可以用来分析数据辅助决策，也可以用来预测，它是一种由节点跟有向边组成的特殊的树结构。辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理u根据层次的不同，
9、节点分为根节点、内部节点和叶节点三类。树的根节点是整个决策树的开始，对应整个样本集，也就是学习的事例集。树的内部节点代表属性或属性的集合，表示的是对某个属性的测试，在内部节点进行属性值的比较，根据不同的属性值判断该节点向下的分支，分支就是分类的判定条件；树的叶节点代表一个类标号。因此从根到叶节点的一条路径就对应着一条合取规则,整棵决策树对应着一组析取表达式规则。辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理u决策树的算法：构造决策树算法有多种，较有代表性的有Quinlan的ID3算法（Iterative Dichotomiser 3,迭代二叉树3代），Breiman等人
10、的CART算法，Loh和Shih的QUEST算法Magidson的CHAID算法等。下面我们介绍一下最常用的ID3算法。早期著名的决策树算法是1986年由Quinlan提出的ID3算法。ID3算法用信息增益（Information Gain）作为属性选择度量。信息增益值越大，不确定性越小。因此，ID3总是选择具有最高信息增益的属性作为当前节点的测试属性。信息增益越大，信息的不确定性下降的速度也就越快。辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理u信息熵定义：假设训练样本集T包含n个样本，这些样本分别属于m个类，其中第i个类在T中出现的比例为pi，那么T的信息熵为：（1
11、1.1）imiippTI21log辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理u信息熵（简称为熵 Entropy）表示信源的不确定性，熵越大，把它搞清楚所需要的信息量也就越大。从信息熵的计算公式可以看出，训练集在样本类别方面越模糊越杂乱无序，它的熵值就越高；反之，则熵值越低。熵的单位可以相应地是比特（二进制）、铁特（三进制）、笛特（十进制）或奈特（自然单位），其中比特为最常用的表示方法。辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理u假设属性A把集合T划分成个V子集 ，其中Ti所包含的样本数为ni，如果A作为测试属性，那么划分后的熵就是：（11
12、.2）vTTT,.,21 iviiTInnAE1辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理uni/n充当第i个子集的权，它表示任意样本属于Ti的概率。熵值越小，划分的纯度越高。用属性A把训练样本集分组后，样本集的熵将会降低，因为这是一个从无序向有序的转变过程。信息增益定义为分裂前的信息熵（即仅基于类比例）与分裂后的信息熵（即对A划分之后得到的）之间的差。简单的说，信息增益是针对属性而言的，没有这个属性时样本所具有的信息量与有这个属性时的信息量的差值就是这个属性给样本所带来的信息量。（11.3）AETIAGain辽宁省物流航运管理系统工程重点实验室11.2.1 基于决
13、策树的知识推理uID3算法描述算法描述uID3算法以自顶向下递归的分而治之方式构造决策树。ID3算法就是根据“信息增益越大的属性对训练集的分类越有利”的原则来选取信息增益最大的属性作为“最佳”分裂点。算法描述如下：u算法：Generate_decision_tree/根据给定的数据集生成一棵决策树u输入：训练样本samples，各属性均取离散数值，可供归纳的候选属性集为attribute_list。u输出：决策树辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理u1）创建一个节点N；u2）if该节点中所有样本samples均为同一个类C then/开始根节点对应的训练样本u
14、3）返回N作为叶节点，以类C标记；u4）if attribute_list为空then；u5）返回N作为叶节点，标记为该节点所含样本中类别个数最多的类别；/多数表决u6）选择attribute_list中具有最高信息增益的属性test_attribute；u7）以test_attribute标记节点N；辽宁省物流航运管理系统工程重点实验室11.2.1 基于决策树的知识推理u8）for each test_attribute中的已知值v；/划分samplesu9）由节点N长出一个条件为test_attribute=v的分枝，以表示该测试条件；u10）设sv是test_attribute=v的样本
15、的集合；/一个划分u11）if sv为空thenu12）将相应叶节点标记为所含样本中类别个数最多的类别；u13）else 将相应叶节点标志Generate_decision_tree(sv,attribute_list-test_attribute)返回的节点。辽宁省物流航运管理系统工程重点实验室11.2.2 基于关联规则的知识推理u基于规则的知识推理系统中的知识一般的描述形式为：IF THEN 利用关联分析我们可以从大量的资料或数据中得到如下形式的关联规则：A B（支持度，置信度）辽宁省物流航运管理系统工程重点实验室11.2.2 基于关联规则的知识推理u关联规则分析能够挖掘发现大量数据中项集
16、之间有趣的关联或相关联系，展示“属性-值”频繁地在给定数据集中一起出现的条件。产生支持度和置信度分别大于用户给定的最小支持度和最小置信度的关联规则，形成形如“A B”的逻辑蕴涵式。关于关联规则方法的具体介绍请参见第5章“关联规则模型及应用”。辽宁省物流航运管理系统工程重点实验室11.2.3 基于粗糙集的知识推理u目前，基于粗糙集的规则获取主要有两种模式。模式A由Pawlak 教授于1991年提出，主要思想是通过寻找属性核及去掉多余的属性求出约简的决策表，并从最简决策表中获取相应的确定规则。模式B由Wakulicz-Deja 等人于1997 年提出，主要思想是直接从原始决策表中求取近似集，并运用
17、推理引擎，分别从下近似集中获取确定规则，从上近似集中获取可能规则。辽宁省物流航运管理系统工程重点实验室11.2.3 基于粗糙集的知识推理u基于粗糙集理论的推理机制的研究过程包括：u（1）根据具体问题构造相应的信息系统；u（2）对信息系统中的数据和信息（包括含糊和不确定性信息）按照某种准则进行离散化；u（3）将离散化后的数据和信息构建成信息表或决策表的形式；u（4）利用粗糙集理论中的核、属性约简、属性值约简、相关度等概念来简化信息表或决策表；辽宁省物流航运管理系统工程重点实验室u（5）求出信息表或决策表的核值表；u（6）由核值表求出信息表或决策表的简化形式；u（7）从简化后的信息表或决策表中求出
18、最佳决策(或推理)算法；u（8）比较粗糙推理机制与其他相关的推理机制的异同点，如模糊推理机制、基于DS证据理论的推理机制等；（9）总结归纳出具有普遍意义的粗糙推理机制、模型和方法，如图11.5所示。辽宁省物流航运管理系统工程重点实验室11.2.3 基于粗糙集的知识推理图11.5 基于粗糙集的规则推理模式 辽宁省物流航运管理系统工程重点实验室11.2.3 基于粗糙集的知识推理u基于粗糙集的从不完备信息系统获取确定规则的算法具有以下优点：（1）不改变初始不完备信息系统结构；（2）获取的确定规则不受缺省值的影响；（3）获取的是最简规则，具有较好的可理解性和较强的泛化能力。粗糙集在知识推理领域的主要研究方向是对粗糙逻辑的研究，它能使单调逻辑非单调化，从而在不确定性推理中发挥巨大作用。另一个研究方向是粗糙函数的理论和应用，它促进了定性推理的发展。关于粗糙集理论的具体介绍请参加第7章“粗糙集方法与应用”。辽宁省物流航运管理系统工程重点实验室11.3 小结u本章主要介绍了知识推理的主要分类，包括：非单调推理、非确定性推理、基于规则的推理、基于案例的推理和定性推理以及基于决策树、关联规则和粗糙集的数据挖掘和知识发现方法在知识推理中的应用。辽宁省物流航运管理系统工程重点实验室
