数据挖掘与知识发现(讲稿21知识表示).docx

数据挖掘与知识发现（讲稿21知识表示）知识表示是人工智能研究中极为重要的研究课题之一。不管应用人工智能技术解决什么问题，首先遇到的就是所涉及的各类知识如何加以表示。不一致的知识有不一致的表示方法，研窕知识表示方法，不单是解决如何将知识存储在计算机中，更重要的是应该能够方便与正确地使用知识。合理的知识表示，能够使问题求解变得容易，同时有较高的求解效率。评价一个好的知识表示系统应具有下列几点：具有表示某个专门领域所需要的知识能力,并保证知识库中的知识是相容的;具有从已知知识推导出新知识的能力,容易建立表达新知识所需要的新结构;便于新知识的获取，最简单的情况是能够由人直接输入知识到知识库中；便于将启发式知识附加到知识结构中，以便把推理集中在最希望的方向上。为了实现上述目标，人们至今已提出了几十种甚至上百种的知识表示方法。但没有一种表示能包打天下。较为常见的知识表示方法有： 一阶谓词逻辑表示 产生式表示或者称规则表示 语义网表示 框架表示 面象对象表示 过程表示 脚本表示 神经元表示 特性表表示2.1一阶谓词逻辑表示谓词逻辑是一种形式语言，也是目前能够表达人类思维活动的一种最精确的语言。它与人类的自然语言比较接近，即可方便地存储到计算机中，又可被计算机进行精确处理。因此，谓词逻辑是最早且最要紧用于人工智能知识描述的方法之一。它是一种基于数理逻辑的知识表示方式。而数理逻辑是一门研究推理的科学，它作为人工智能的基础，在人工智能的进展中占有重要地位。人工智能中用到的逻辑可分为两大类：一阶经典命题逻辑与谓词逻辑除经典以外的那些逻辑2.1.1 一阶谓词逻辑表示的逻辑基础谓词逻辑是在命题逻辑的基础上进展起来的,为此先讨论一阶谓词逻辑知识表示中所需要的一些逻辑基础。如命题、谓词、连接词、量词、谓词公式等。1 .命题与真值定义2.1：一个陈述句称之一个断言。凡有真假意义的断言称之命题。（即能够确定真假意义的陈述句）注：命题的意义通常称之真值，它只有真（T）假（F）两种情况。在命题逻辑中，命题通常用大写的英文字母来表示。一个命题不能同时为真又为假。一个命题可在一定条件下为真，在另一条件下为假。如，P：“北京今天有雨”,需根据当天的情况决定其真值。没有真假意义的感叹句、疑问句等都不是命题。如，P：今天好冷呀！；Q：今天的温度有多少度？命题的优点是简单、明确；缺点是无法描述客观事物的结构及其逻辑特征，也无法表示不一致事物间的共性。如，“杨青是教师”与“李文是教师”这两个命题，用命题逻辑表示时，无法把两人都是教师这一共同特征表示出来。2 .论域与谓词论域是由所讨论对象之全体构成的非空集合。论域中的元素称之个体。论域又称个体域。在谓词逻辑中，命题是用谓词表示的。一个谓词可分为：谓词名与个体两部分。其中，个体是用来表示某个独立存在的事物或者者某个抽象的概念；谓词名是用来表示个体的性质、状态或者个体之间的关系等。通常，谓词名用大写英文字母表示，个体用小写英文字母表示。如：王宏是学生谓词表示为：STUDENT（Wanghong）桂林山水甲天下谓词表示为：甲天下(桂林山水)桂林在广西的北部谓词表示为：在(北部，桂林，广西)广西师大校园坐落在桂林谓词表示为：坐落在(广西师大校园，桂林)谓词表示为：县(全州，桂林)谓词表示为：Greater(x,6)谓词表示为：TEACHER (father(Wanghong)全州是桂林的县x>6王宏的父亲是教师谓词的形式定义如下：定义2.2设D是个体域，P:D"T,F是一个映射，其中Dn=(x1,x2,xn)x,.£f),i=1,2,则称P是一个元谓词。记为：P(x1,x2,xw),再"2,，瑞是个体。注：在谓词中，个体能够是常量、变元或者函数。函数的定义形式为：定义2.3设D是个体域，,O"O的一个映射，则称/是D上的一个n元函数。记作：/(x1,x2,xrt),再,2,，匕是个体。说明：谓词与函数的定义形式相似，但却是两个不一致的概念。谓词的真值是T或者F,而函数无真值可言，其值是D中的某个个体。谓词实现的是从个体域中的个体到T或者F的映射，而函数实现的是同一个体域中从一个个体到另一个个体的映射。在谓词逻辑中，函数本身不能单独使用，它务必嵌入到谓词中。假如尸区,乙)中的玉,当，%个体都是常量、变元或者函数，则称其为一阶谓词。若某个再本身又是另一个一阶谓词，则称它为二阶谓词。3 .连接词与量词连接词是用来连接简单命题，并由简单命题构成复合命题的逻辑运算符号。在一阶谓词逻辑中，有5个连接词与2个量词。由于命题逻辑可看作谓词逻辑的一种特殊形式，因此5个连接词同样习惯于命题逻辑，但2个量词仅习惯在于谓词逻辑。：称之“非”。它表示其后命题的否定v：称之“析取”。它表示所连接的两个命题之间具有“或者”的关系A：称之“合取”。它表示所连接的两个命题之间具有“与”的关系:称之“条件”或者“蕴含”。它表示“若则”的语义。如，PQ表示“P蕴含Q”，读作：“假如P,则Q"，其中P称之条件的前件，Q称之条件的后件。<->：称之“双条件”。它表示“当且仅当”的语义。如，Pc。表示P当且仅当Q,即读作“P当且仅当Q“。谓词逻辑真值表PQ-p尸VQ尸AQPTQPCQTTFTTTTTFFTFFFFTTTFTFFFTFFTT在一阶谓词逻辑中，引入了2个量词符号：全程量词符号与存在量词符号3一所有的，任一个三一至少有一个，存在有量词是由量词符号与被其量化的变元所构成的表达式，是用来对谓词中的个体作出量的规定。如，“对论域中的所有个体”，表示为Vx;“对论域中的某个个体”，表示为玉。命题(VX)P(幻为真，当且仅当论域中的所有X,都有P(X)为真命题0x)P(X)为真，当且仅当论域中至少存在一个%O,使得P()为真4 .项与合式公式在一阶谓词逻辑中，合法的表达式称之合式公式(即谓词公式)。定义2.4项满足如下规则：(1)单独一个个体词是项；(2)若小小是项，是n元函数，则/G由,，乙)是项；(3)由(1)、(2)生成的表达式是项。可见，项是把个体常量、个体变量与函数统一起来的概念。定义2.5原子谓词公式的含义为：若"”是项，P是谓词符号，则称P32，,露为原子谓词公式。定义2.6满足如下规则的谓词演算可得到合式公式：(1)单个原子谓词公式是合式公式；(2)若A是合式公式，则也是合式公式；(3)若A、B是合式公式,则AVB,AB,4B,AcB也都是合式公式；(4)若A是合式公式，X是项，则(VX)A与(h)A也都是合式公式。注：在合式公式中，连接词之间的优先级顺序为：,V,5 .自由变元与约束变元当一个谓词公式含有量词时,通常把位于量词后面的单个谓词或者者用括弧括起来的合式公式称之该量词的辖域。辖域内与量词中同名的变元称之约束变元，不受约束的变元称之自由变元。如(Vx)(P(x,y)Q(x,y)vR(X,y)这里，(P3,y)Q(xy)是(VX)的辖域，其中的X是(Vx)的约束变元；Ray)中的X是自由变元。公式中所有的y都是自由变元。注：在谓词公式中，变元的名字是无关紧要的，能够把一个名字换成别的名字。换名时注意两点：当对量词辖域内的约束变元更名时，务必把同名的约束变元都统一换成另外一个相同的名字，且不能与辖域内的自由变元同名；当对辖域内自由变元更名时，不能改成与约束变元同名。如上例可表示为：(VZ)(P(z,y)Q(z,y)vR(X,y)命题公式是谓词公式的一种特殊情况，也可用连接词把单个命题连接起来构成合式公式。如，XPVQ),P(QvR),(PQ)(Q砌都是命题公式。2.1.2 谓词逻辑的知识表示方法谓词逻辑不仅能够用来表示事物的状态、属性、概念等事实性知识，也能够用来表示事物的因果关系。对事实性知识，常用，V,八符号连接起来的谓词公式表示。对事物间的因果关系，通常用蕴含式表示。如，对“假如X则y”可表示为“xy”当用谓词逻辑表示知识时，先要根据所表示的知识定义谓词，然后再用连接词或者者量词把这些词连接起来，形成一个谓词公式。例1用谓词逻辑表示知识“每个人都有一个父亲”。谓词：PERSON(x)：表示X是人Hasfathera,y)：表示X有父亲y则该知识可用谓词表示为：(Vx)0y)(PERSOx)HASFATHERX,y)例2用谓词逻辑表示知识“所有教师都有自己的学生”。谓词：TEACHER(x)：表示X是教师STUDENT(y)：表示y是学生TEACHERS(x,y)：表示X是y的老师则该知识可用谓词表示为：(WX)Qy)(TEACHERA:)TEACHER&x,y)aSTUDENTly)例3用谓词逻辑表示知识“所有的整数不是偶数就是奇数”。谓词：Ia)：X是整数E(x):X是偶数O(X):X是奇数则该知识可用谓词表示为：(x)(Z(x)E(x)vO(x)例4用谓词逻辑表示知识：王宏是计算机系的一名学生。李明是王宏的同班同学。凡是计算机系的学生都喜欢编程序。谓词：COMPUTER):表示X是计算系的学生CLASSMATE(Xj):表示X是y的同班同学1.IKE(xj):表示X喜欢y则上述知识表示为：COMPUTER(Wanghong)CLASSMATE(Liming5Wanghong)gx)(fX)MPUTERx)LIKE(x,Programng)2.1.3 谓词逻辑表示的应用示例1机器人移盒子问题设在一房间里，c处有一个机器，a与b处各有一张桌子，分别称之a桌与b桌,a桌上有一盒子，如图所示。要求机器人从C处出发把盒子从a桌拿到b桌子上，然后再回到C处。试用谓词逻辑来描述机器人的行动过程。分析：此例中的谓词公式，不仅要用来描述事物的状态、位置，而且还要用来表示动作。问题的目标状态: AT(robot,c) EMPTY(robot) ON(box,b) TABLE(a) TABLE(b)定义的谓词：TABLE(X):X是桌子EMPTY(y)：y手中是空中AT(y,z):y在Z的邻近HOLDS(yw):y拿着WON(w5x):wX桌面上由此知，问题的初始状态是：显然，机器人行动的目标是把问题的初始状态转换为目标状态。而要实现问题的状态转换，则需AT(robot,c)EMPTY(robot)ON(box,a)TABLE(a)TABLE(b)要完成一系列的操作。关于每个操作，通常都可分为条件与动作部分。条件部分用来说明执行该操作务必具备的先决条件，动作部分给出了该操作对问题状态的改变情况。条件部分可用谓词公式来表示，动作部分则是通过在执行该操作前的问题状态中删去与增加相应的谓词来实现。本例中，机器人需要执行的操作：Goto(x,y):从X处走到y处Pickup(x):在X处拿起盒子Setdown(X):在X处放下盒子其对应的条件与动作如下：Goto(x,y)条件：AT(robot,x)动作：删除表:AT(Ibot,x)添加表:AT(robot,y)Pickup(x)条件:ON(box,