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

研究生课程考试成绩单（试卷封面）院 系计算机科学与工程学院专业计算机技术学生姓名刘振学号111503课程名称数据挖掘技术授课时间2012年 2月至 2012年 6月周学时3学分1.5简要评语考核论题总评成绩（含平时成绩）备注任课教师签名： 日期： 注：1. 以论文或大作业为考核方式的课程必须填此表，综合考试可不填。“简要评语”栏缺填无效。2. 任课教师填写后与试卷一起送院系研究生秘书处。3. 学位课总评成绩以百分制计分。数据挖掘中关于不一致规则的处理摘要 真实世界中的知识纷繁复杂，如何用接近于人类理解的表达方式来表达这些知识是一个问题。在人类知识中，有很多知识并没有刻意的去强调，因为这些知识属于常识，在本文中，我们将介绍有关缺省（常识）表达方面的内容，我们将展示如何表达缺省规则以及对应于这种缺省规则的各种形式的异常。同时，我们也会讨论这种缺省表达是如何在应用于各种含有不完整的信息的领域。我们也会分析到在某些场合下如何表示缺省规则之间的优先性，这样，我们就可以优先选择某些缺省规则。接着，我们讨论了在表达类的层次结构和类属性继承情况下时，缺省表达的作用。最后我们讨论了对于一个存在不一致情况的原始规则集，我们怎样自动的完成改写它的过程，让其中的规则具有缺省表达和容忍异常情况的能力.关键词 缺省表达；异常；不一致The representation of default and exception in ASPAbstract Knowledge in the real world is complicated, it is a problem for us to express these knowledge in a way which is close to humans comprehension. In human knowledge ,there is so much knowledge which isnt emphasized as a result of it being default knowledge. In this paper we will show how defaults and various forms of exceptions to them are represented and how this general representation can be used for reasoning in a variety of domains, including those that have incomplete information. We show how defaults can be prioritized so that, in some cases, we prefer one default over another. Finally, we discuss the use of defaults when representing hierarchies of classes and the inheritance of class properties by subclasses and members. Keywords default representation; exception; inconsistency一、引言什么叫缺省表达？一个包含诸如“通常”，“一般”或“大多数情况下”之类的词语的陈述我们就称之为缺省表达。各种各样的诸如此类的信息对人类是非常有用的，因为我们没有对世界的完整信息，但仍必须能够在常识的基础上做出结论。然而，这些结论只是初步得出，当新的信息纳入知识库中时，我们可能会被迫撤回它们。事实上，我们的生活很大一部分似乎就是由各种缺省表达，这些缺省表达的异常，以及运用它们进行推理的而组成。缺省表达不存在于数学语言中，因此，我们并没有研究古典数学逻辑。然而，缺省表达在日常生活，常识推理中扮演一个重要角色，并向人工智能的研究者提出了相当大的挑战。二、缺省表达的一般策略2.1直接用一般规则表达常识在本节，我们将会讨论缺省表达的一般策略。先让我们来看看这样一个例子.例1: Uncaring John 假设你是Sam的老师，你坚信Sam需要一些额外的帮助来通过考试。你将这一信息传达给Sam的父亲John，并希望他能够采取一些行动。那么你的推理可能沿以下线路：1)John是Sam的父母。2)通常情况下，家长关心孩子。3)因此，John关心Sam并且会帮助Sam学习。第二条语句是一个默认也即缺省的一个典型的例子。我们引进关系cares(X,Y)来模拟这种推理： cares(X,Y)“ X cares for Y . 我们已有的知识库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), not ab(d(X) , not -p(X).在这里，ab(d (X) 读作“通常情况下X具有属性d，但这里是一个异常（例外）”，ab就是abnormal的意思，not -p(X)表示没有证据表明-p(X)成立。让我们来看看刚才的例子，如果说“通常情况下父母是关心孩子的”这条缺省规则用上述模型来建立，我们可以得到： cares(X,Y) :- parent(X,Y), not ab(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)，如果将这条规则加入到F U (2.1.1)中就会产生相互矛盾的推论，导致知识库不一致，然而如果将这条规则加入到F U (2.1.2)中，我们不仅会推出-cares(john,sam)，cares(alice,sam),并且知识库仍然一致。这里要注意，新的关于john的知识让程序取缔了先前的推论并且用新的知识来替换它。2.2强异常（Strong exception）和弱异常（Weak exception）缺省可以有两种类型的异常，强异常（Strong exception）和弱异常（Weak exception）。弱异常使得缺省规则不能被使用，即一个或多个缺省规则的前提不能被满足，这就使得我们的程序无法使用缺省规则来得到相应的结论。强异常反驳缺省规则的结论，也就是说，强例外不仅使得缺省规则不能使用并且得到缺省规则结论的否定。例如上面提到的一个缺省规则：cares(X,Y) :- parent(X,Y), not ab(dcares(X,Y) , not -cares(X,Y). (default rule)它的弱异常(Weak exception)可以是ab(dcares(x,y)，因为有了这个异常我们就不能使用缺省规则了，但同时我们也得不出任何结论，是-cares(x,y)还是cares(x,y),我们无从所知。它的强异常(Strong exception)是-cares(x,y),同样的，由于这个异常我们不能再使用缺省规则，但相对于弱异常不同的是，我们此时还能得到一个确定的结论,即-cares(x,y)。2.3强异常与弱异常的实例现在让我们考虑一个例子，它有既有强异常也包含弱异常。考虑以下信息： 1)通常情况下，学生怕数学。 2)玛丽不怕数学。 3)数学系的学生都不怕数学。 4)计算机系的学生可能怕也可能不害怕数学。第一条语句对应于一条缺省规则，d，接下来的两条语句可以视为强异常，第四条语句是一个弱异常。默认规则（第一条语句）可以这样写： afraid(S,math):- student (S) , not ab(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), not ab(d1(X), not -entitled(X,1). entitled(X,2) :- child(X), -dead(X), not ab(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),not ab(d1(X),not fly(X).2.鸟儿通常会飞：fly(X) :- is_a(X,bird),not ab(d2(X),not -fly(X).3.企鹅通常不会飞：-fly(X) :- is_a(X,penguins),not ab(d3(X),not fly(X).4.如果X是一只企鹅，那么它就是关于语句2的一个异常ab(d2(X) :- is_a(X,penguins).5.如果X是一只鸟儿，那么它就是关于语句1的一个异常ab(d1(X) :- is_a(X,birds). 由此我们可以发现，正是通过弱异常，即ab(d(X)来使得父类的某些属性无法承。由此达到继承于父类并区别于父类的目的。五、自动完成原始规则集的改写让我们考虑这样的一组规则集，里面的规则表达了关于动物和鸟的知识：通常动物不会飞，鸟儿是动物，通常鸟类会飞，鸟类通常有腿，企鹅通常是鸟类，企鹅通常不会飞，鹰隼是鸟，鹰隼会飞，= r1 = -fly:-animal , r2 =animal:- bird , r3 =fly:-bird , r4 =bird:-penguin,r5=-fly:-penguin,r6=bird:-eagle,r7=fly:-eagle。这组规则集中存在着缺省表达，那么我们怎样对这些规则进行处理，已达到第四部分中例子的效果呢？5.1分层规则有着适用范围的差别，比如动物不会飞的使用范围就比鸟儿会飞要广，究其原因就在于鸟儿是动物的一个子集，根据这一特点我们将规则进行分层次，比较特殊，适用范围较窄的规则放在下层，比较普遍，适用范围更广的规则我们放在上层。定义1：一个原子集A在一个程序P下是闭包的当且仅当对于P中的每一条规则r，如果有body(r) A那么head(r) A。定义2：一条规则r能够被一个缺省规则集所容忍，除非存在一个原子集A，A在下闭包且一致，而且能够验证r。A如果能够验证r，除非有B A且lA.依照容忍性的不同，我们就可以将缺省规则集划分为0,1,2m，其中：0包含来自的规则且能够被容忍，1包含0的规则并且能够被0所容忍，2包含(0U1）的规则并且能够被(0U1)所容忍，以此类推.那么对于上述关于动物和鸟的规则集我们对它进行分层，得到的结果为：0= r1 = -fly:-animal Ar1=animal,-fly1= r2 =animal:- bird , r3 =fly:-bird Ar2=animal, bird, fly, Ar3= bird, fly, animal2=r4 =bird:-penguin,r5=-fly:-penguin,r6=bird:-eagle,r7=fly:-eagleAr4，Ar5=bird, penguin , -fly ,Ar6，Ar7=bird, eagle, fly这样经过分层后，原先的规则信息就有了层次结构，上层的信息更普遍，更通俗，下面的规则更具体，更细致。5.2改写对于经过分层后的规则，下一步就要对他们进行改写，已达到可以容忍异常的效果。即，上层的规则会出现异常，这种异常就是来自于下层的那些更具体的规则。规则重写的主要思路就在于，根据分类后的0,1,2m，重新将缺省规则的条件部分进行改写，将可能出现的异常包含进去，因此，原先的缺省规则将变为严格规则。首先，层次分类后，最底层规则集m是最特殊的，其中的规则不承认任何异常，它们直接被纳入到严格规则集当中，较高层次的缺省规则要考虑到较低层次中的出现的异常，我们在缺省规则的条件部分详尽的描述异常情况使之成为严格规则。整个过程一直进行到所有的层次规则集都被考虑过。下面，让我们对上面分层好的规则集进行改写：1） 将最下层的规则直接放入严格规则集S中将2放入S，所以放入后，S=r4 =bird:-penguin,r5=-fly:-penguin,r6=bird:-eagle,r7=fly:-eagle2） 每一层规则集在放入S中前，先将其中每一条规则与S中的每一条规则进行比较，比如i层中的规则r正在和S中的规则t进行比较，若有head(r)与head(t)互为否定并且body(r)与body(t)一致（所谓一致即不存在互为否定的literal），则要对r进行改写，在r的规则体中添加两个literal，一个是not ab(d),一个是not -head(r),并且添加一条新的规则ab(d):-body(t).在1放入S前，我们要对它进行改写，根据上面的方法，改写后我们得到:1=r2=animal:- bird , r3=fly:-bird, not ab(d1),not fly, r3=ab(d1):-penguin 将1放入S，我们会得到新的S= r2=animal:- bird , r3 =fly:-bird, not ab(d1),not fly, r3=ab(d1):-penguin r4 =bird:-penguin,r5=-fly:-penguin,r6=bird:-eagle,r7=fly:-eagle然后我们在考虑0，对0进行改写，我们得到0= r1 = -fly:-animal ,not ab(d2),not fly,r1=ab(d2):-bird,r1=ab(d2):-eagle将0放入S，我们得到新的S= r1 = -fly:-animal ,not ab(d2),not fly,r1=ab(d2):-bird,r1=ab(d2):-eagle， r2=animal:- bird , r3 =fly:-bird, not ab(d1),not fly, r3=ab(d1):-penguin ，r4 =bird:-penguin,r5=-fly:-penguin,r6=bird:-eagle,r7=fly:-eagle至此，所有层的规则都考虑完毕，现在的S即为严格规则集。严格规则集S中的规则更加规范，它们可以表达更多的信息并且可以接受异常的出现，所以S中的规则表达能力更强，表示的信息更精确。六、相关工作尽管关于缺省表达方