数据挖掘中关于不一致规则的处理

研究生课程考试成绩单（试卷封面）院系计算机科学与工程学院专业计算机技术学生姓名刘振学号111503课程名称数据挖掘技术授课时间2012年2月至2012年6月周学时3学分1.5简要评语考核论题总评成绩（含平时成绩）备注任课教师签名：日期：注：1.以论文或大作业为考核方式的课程必须填此表，综合考试可不填。“简要评语”栏缺填无效。2.任课教师填写后与试卷一起送院系研究生秘书处。3.学位课总评成绩以百分制计分。数据挖掘中关于不一致规则的处理摘要真实世界中的知识纷繁复杂，如何用接近于人类理解的表达方式来表达这些知识是一个问题。在人类知识中，有很多知识并没有刻意的去强调，因为这些知识属于常识，在本文中，我们将介绍有关缺省（常识）表达方面的内容，我们将展示如何表达缺省规则以及对应于这种缺省规则的各种形式的异常。同时，我们也会讨论这种缺省表达是如何在应用于各种含有不完整的信息的领域。我们也会分析到在某些场合下如何表示缺省规则之间的优先性，这样，我们就可以优先选择某些缺省规则。接着，我们讨论了在表达类的层次结构和类属性继承情况下时，缺省表达的作用。最后我们讨论了对于一个存在不一致情况的原始规则集，我们怎样自动的完成改写它的过程，让其中的规则具有缺省表达和容忍异常情况的能力.关键词缺省表达；异常；不一致TherepresentationofdefaultandexceptioninASPAbstractKnowledgeintherealworldiscomplicated,itisaproblemforustoexpresstheseknowledgeinawaywhichisclosetohuman’scomprehension.Inhumanknowledge,thereissomuchknowledgewhichisn’temphasizedasaresultofitbeingdefaultknowledge.Inthispaperwewillshowhowdefaultsandvariousformsofexceptionstothemarerepresentedandhowthisgeneralrepresentationcanbeusedforreasoninginavarietyofdomains,includingthosethathaveincompleteinformation.Weshowhowdefaultscanbeprioritizedsothat,insomecases,wepreferonedefaultoveranother.Finally,wediscusstheuseofdefaultswhenrepresentinghierarchiesofclassesandtheinheritanceofclasspropertiesbysubclassesandmembers.Keywordsdefaultrepresentation;exception;inconsistency一、引言什么叫缺省表达？一个包含诸如“通常”，“一般”或“大多数情况下”之类的词语的陈述我们就称之为缺省表达。各种各样的诸如此类的信息对人类是非常有用的，因为我们没有对世界的完整信息，但仍必须能够在常识的基础上做出结论。然而，这些结论只是初步得出，当新的信息纳入知识库中时，我们可能会被迫撤回它们。事实上，我们的生活很大一部分似乎就是由各种缺省表达，这些缺省表达的异常，以及运用它们进行推理的而组成。缺省表达不存在于数学语言中，因此，我们并没有研究古典数学逻辑。然而，缺省表达在日常生活，常识推理中扮演一个重要角色，并向人工智能的研究者提出了相当大的挑战。二、缺省表达的一般策略2.1直接用一般规则表达常识在本节，我们将会讨论缺省表达的一般策略。先让我们来看看这样一个例子.例1:UncaringJohn假设你是Sam的老师，你坚信Sam需要一些额外的帮助来通过考试。你将这一信息传达给Sam的父亲John，并希望他能够采取一些行动。那么你的推理可能沿以下线路：1)John是Sam的父母。2)通常情况下，家长关心孩子。3)因此，John关心Sam并且会帮助Sam学习。第二条语句是一个默认也即缺省的一个典型的例子。我们引进关系cares(X,Y)来模拟这种推理：cares(X,Y)—“XcaresforY.我们已有的知识库F中包含：father(john,sam).（john是sam的父亲）mother(alice,sam).parent(X,Y):-father(X,Y).parent(X,Y):-mother(X,Y).child(X,Y):-parent(Y,X).如果忽略第二条推理思路中的词“通常情况下“，仅仅增加这样一条语句，cares(X,Y):-parent(X,Y).(2.1.1)那么更新后的知识库将会推导出：cares(john,sam).即John关心Sam这样一个事实。现在假设，对于默认的“一般父母关心自己的孩子”这条规则，john是这条规则的一个例外，因为他不关心自己的孩子。这一新的信息，在日常推理中不会引起矛盾，我们只需收回之前的结论cares(john,sam)，并用-cares(john,sam).来代替。这种当新的信息可用时允许取消先前推出的结论的推理，被称为非单调推理，由于古典数学逻辑是单调的，它不适合使用缺省表达，但是ASP不会有这样的困难。在ASP中，一个默认情况d是这样被陈述“通常的C类的元素有属性P”，那么这个默认情况d通常被表示成这样一条规则：p(X):-c(X),notab(d(X)),not-p(X).在这里，ab(d(X))读作“通常情况下X具有属性d，但这里是一个异常（例外）”，ab就是abnormal的意思，not-p(X)表示没有证据表明-p(X)成立。让我们来看看刚才的例子，如果说“通常情况下父母是关心孩子的”这条缺省规则用上述模型来建立，我们可以得到：cares(X,Y):-parent(X,Y),notab(dcares(X,Y)),not-cares(X,Y).(2.1.2)让我们来比较下先前增加的规则2.1.1。F是先前已经建立起来的关于父母定义的知识库，我们让规则2.1.1和2.1.2分别加入到F中，我们都可以推出cares(john,sam)。现在让我们看看如果我们事先已经知道John并不关心他的孩子，即-cares(john,X)：-child(X,john)，如果将这条规则加入到FU(2.1.1)中就会产生相互矛盾的推论，导致知识库不一致，然而如果将这条规则加入到FU(2.1.2)中，我们不仅会推出-cares(john,sam)，cares(alice,sam),并且知识库仍然一致。这里要注意，新的关于john的知识让程序取缔了先前的推论并且用新的知识来替换它。2.2强异常（Strongexception）和弱异常（Weakexception）缺省可以有两种类型的异常，强异常（Strongexception）和弱异常（Weakexception）。弱异常使得缺省规则不能被使用，即一个或多个缺省规则的前提不能被满足，这就使得我们的程序无法使用缺省规则来得到相应的结论。强异常反驳缺省规则的结论，也就是说，强例外不仅使得缺省规则不能使用并且得到缺省规则结论的否定。例如上面提到的一个缺省规则：cares(X,Y):-parent(X,Y),notab(dcares(X,Y)),not-cares(X,Y).(defaultrule)它的弱异常(Weakexception)可以是ab(dcares(x,y))，因为有了这个异常我们就不能使用缺省规则了，但同时我们也得不出任何结论，是-cares(x,y)还是cares(x,y),我们无从所知。它的强异常(Strongexception)是-cares(x,y),同样的，由于这个异常我们不能再使用缺省规则，但相对于弱异常不同的是，我们此时还能得到一个确定的结论,即-cares(x,y)。2.3强异常与弱异常的实例现在让我们考虑一个例子，它有既有强异常也包含弱异常。考虑以下信息：1)通常情况下，学生怕数学。2)玛丽不怕数学。3)数学系的学生都不怕数学。4)计算机系的学生可能怕也可能不害怕数学。第一条语句对应于一条缺省规则，d，接下来的两条语句可以视为强异常，第四条语句是一个弱异常。默认规则（第一条语句）可以这样写：afraid(S,math):-student(S),notab(dafraid(S)),not-afraid(S,math).根据语句2，玛丽是一个关于这个默认的强例外，根据我们的方法，它可以表示为：-afraid(mary,math).数学系的学生（语句3）也是个强异常,其表达如下：-afraid(S,math):-student(S),in(S,math_dept).语句4所表达的关于计算机系学生是一个弱异常，其规则如下：ab(dafraid(S)):-student(S)，in(S,cs_dept).那么已有的知识库包含in(john,english_dept).in(mary,cs_dept).in(bob,cs_dept).in(pat,math_dept).这些信息。那么如果将上述四条新的规则添加到知识库，那么我们便可以运用这些规则和原有的知识进行推理，得到新的推论，图1是是关于新知识库的查询和结果。图1查询及结果三、缺省规则之间的优先级在某些情况下，我们希望我们的程序相对于某些规则而言优先选择其他规则。接下来让我们来看看一种用来表示缺省规则之间简单的优先级的方法。考虑下面的例子。entitled(X,1):-orphan(X),notab(d1(X)),not-entitled(X,1).entitled(X,2):-child(X),-dead(X),notab(d2(X)),not-entitled(X,2).第一条规则表达的是通常孤儿都会获得项目1的帮助，第二条规则表达的是通常所有没获得任何项目帮助的孩子都会收到项目2的帮助。如果Joe是一个孤儿，那么按照上述规则表达的意思我们是希望Joe能够获得项目1的帮助而非项目2，但是规则2可以运用到Joe的身上，从而使Joe获得项目2的帮助。因此在面临选择规则1和规则2时，我们优选选择规则1，那怎样表达相对于孤儿规则1的优先性呢。我们增加这样一条规则：ab(d2(X)):-orphan(X).也就是通过一个弱异常使得规则2不能应用于孤儿。那么如果Joe是一个孤儿，那她将获得项目1的帮助，如果Joe不是孤儿，或者不确定他是不是孤儿，那么他将获得项目2的帮助。简而言之，缺省规则之间是通过弱异常使得一部分缺省规则不能使用从而突出另一部分缺省规则的优先性的。四、层次继承中的缺省规则每当Web中的信息具有层次结构时，子类之间通常具有一些继承于父类的共同特性。例如，如果我们判断某个东西是一种动物，那么我们便可以假设它能够进食，呼吸等，之所以这样判断，是因为这个东西是动物，而动物具有这些特性。但是，来自于同一父类的子类之间存在着差异，同时子类与父类也存在着差异。简而言之，问题就在于通常情况下，我们认为子类具有父类的属性，但是同时也存在着异常。我们通过下面这个例子来说明图2。.图2动物类动物在最顶层，是父类，鸟儿也是动物，具有动物的一般属性，但是一般我们认为鸟儿是会飞的，而动物一般是不会飞的，因此父类和子类之间在这一点上存在差异，同样的鹰隼和企鹅都是鸟类的成员，具有鸟的一般属性但是鹰隼是会飞的，而企鹅不会飞。对于这样一个知识结构层次，我们如何表达呢?表达如下文所示。1.动物通常是不会飞的：-fly(X):-is_a(X,animals),notab(d1(X)),notfly(X).2.鸟儿通常会飞：fly(X):-is_a(X,bird),notab(d2(X)),not-fly(X).3.企鹅通常不会飞：-fly(X):-is_a(X,penguins),nota