决策推理与决策支持系统.ppt

数据仓库与决策支持系统,主讲：鲁明羽,大连海事大学信息科学技术学院 研究方向：智能数据分析与数据挖掘 电 话：13889576531 Email：lumingyu,第二章 决策推理与决策支持系统,本章内容,人脑决策推理初探 电脑推理方法介绍 DSS中的决策过程 知识与知识表示方法,1. 人脑决策推理初探,推理（inference）：是由已知事实通过一定逻辑手段获得未知事实的过程。 两种主要的推理方法：演绎(deductive inference)和归纳(inductive inference),图4.1 推理模型图,1. 人脑决策推理初探,（1）演绎推理 演绎推理是从一般到特殊的推理，其中的已知事实部分一般为一般性的规则，而其未知部分则为个体事实。,图4.2 演绎推理模型,1. 人脑决策推理初探,演绎推理是一种常用的推理方法，例如：数学中采用的基本方法，初等几何中由公理推导定理的方法。 专家系统中也经常采用演绎推理，例如医学诊断专家系统。 两种演绎推理方法： （1）三段论推理法 （2）反证法,1. 人脑决策推理初探,（2）归纳推理 归纳推理与演绎推理相反，是从特殊到一般的推理，其中的已知事实部分一般为大量个体事实，而其未知部分则为推导出的一般性规则。,图4.5 归纳推理模型,1. 人脑决策推理初探,归纳推理也是一种常用的推理方法，例如现实生活中的一些谚语，就是通过人们通过对生活中的大量事实进行总结归纳后得出的。 归纳推理得到的一般性规则，又可以用于演绎推理，指导我们的行为和决策。 （图4.7 归纳-演绎推理过程） 数据挖掘就是采用了这个原理。,1. 人脑决策推理初探,（3）联想和类比 从一些已知事实或知识，通过联想，推出其他类似事物的知识。 （4）综合与分析 根据对事物的宏观（整体）知识推断其微观（局部）知识的方法称为“分析”； 从事物的微观（局部）知识推出其宏观（整体）知识的方法称为“综合”。,1. 人脑决策推理初探,（5）预测 根据事物的过去和现在知识，来推断未来的知识，或者从事物局部空间的知识，推断其局部以外的情况。 （6）假设与验证 根据经验作出假设，然后用逻辑推理或实践检验的方法获得新的知识。有时会否定假设或部分修正假设，然后再作验证，也可称为“试探推理法”。,2. 电脑推理方法介绍,电脑推理一般是模仿人脑的推理方式和过程，通过编制软件完成。 2.1 电脑的演绎推理方法 （1）规则模型表示 一般性规则有两种表示方法： 数学方法 人工智能方法,2. 电脑推理方法介绍,（2）基于数学模型的演绎推理 数学方法中一般采用数学模型，例如数学表达式、方程式等。 基于数学模型的演绎推理实际上是数学推演方法，一般将一些常用的演算方法作为固定算法，编程实现后存入方法库中，例如最小二乘法、线性规则、回归分析等。 数学建模和推理时则调用方法库中算法。,2. 电脑推理方法介绍,（3）基于逻辑模型的演绎推理 人工智能常用的知识表示方法包括谓词逻辑、语义网络、Petri网、框架表示等。 其中最常见的是谓词逻辑表示法，即将规则表示为一组数理逻辑中的一阶谓词逻辑的合法公式，采用一阶谓词的推理方法，以实现演绎推理。该推理过程实际上是一种定理证明过程，其规则一般为公理，而结果为个体事实，即推导出的定理。,2. 电脑推理方法介绍,20世纪60年代，美国科学家Robinson证明，存在一种统一的、固定的证明过程，对于所有的一阶谓词逻辑中的定理证明都基本有效，这就是所谓的谓词逻辑的自动定理证明。 利用上述成果，可以将定理证明过程用一种统一算法表示并编程实现，从而使运用人工智能方法进行演绎推理可以用一种统一的程序或过程来实现。 用此方法所实现的软件系统称为推理引擎（inference engine）。,2. 电脑推理方法介绍,2.2 电脑的归纳推理方法 主要有两种：验证型归纳和探索型归纳。 （1）验证型归纳 首先对于推理结果产生一些假设（模型）； 设计一个试验环境，并置入设想模型； 启动试验过程，用大量个体事实做测试，通过人机交互将得到的结果与原设想做比较 如果结果不符，修改试验，反复上述过程,2. 电脑推理方法介绍,（2）探索型归纳 没有明确的假设模型，只有大致的目标，一般采用数据挖掘技术实现，主要方法有： 关联分析(association)：挖掘出潜藏在客体间的内在相互联系； 分类(classifier)：对待分类的客体集合进行分析，找出每个分类的特征； 聚类分析(clustering)：对一组客体按某种规则聚为若干类。,3. DSS中的决策过程,在DSS中，除了决策推理部分之外，还有数据仓库部分。二者相结合，构成了一个完整的决策过程。 3.1 DSS中的演绎型决策过程 在DSS中，演绎型决策过程是由演绎中的一般性规则与数据仓库中的数据共同作为推理前提，通过演绎推理，最终得到个体事实数据作为结论。,3. DSS中的决策过程,基于不同推理模型，DSS的演绎型决策过程有不同的形式。,图4.9 DSS中演绎型决策过程示意图,3. DSS中的决策过程,图4.10 DSS中基于数学模型的演绎型决策过程示意图,基于数学模型的演绎型决策过程 数据仓库数据作为数学模型中的参数输入，而演绎推理则是通过方法库中方法调用方式实现。,3. DSS中的决策过程,基于逻辑模型的演绎型决策过程 数据仓库数据作为假设前提输入，而演绎推理则是用推理引擎实现。,图4.11 DSS中基于逻辑模型的演绎型决策过程示意图,3. DSS中的决策过程,3.2 DSS中的归纳型决策过程 在DSS中，归纳型决策过程是由数据仓库中的数据作为大量个体事实输入，经归纳推理而得到一般性原则。,3. DSS中的决策过程,（1） 验证型归纳的决策过程 其归纳推理部分即为数据实验室的人-机交互试验，简称数据实验室试验。 OLAP是DSS常用的验证型归纳推理。,图4.13 DSS中验证型归纳决策过程示意图,数据 （数据仓库）,一般性规则,数据实验室 试验,3. DSS中的决策过程,（2） 探索型归纳的决策过程 其归纳推理部分即为各种类型算法调用。 数据挖掘是DSS常用的探索型归纳推理。,图4.14 DSS中探索型归纳决策过程示意图,数据 （数据仓库）,一般性规则,算法调用,3. DSS中的决策过程,3.3 包含推理的DSS总体结构图 DSS主要由数据仓库与决策推理两部分组成，加上结果展示模块，构成了完整的决策过程。如图4.15所示。,4. 知识与知识表示方法,知识库：存放各种规则、因果关系和决策人员的经验等 推理机：综合运用知识库、数据库和定量计算的结果，进行推理和问题求解。,DSS能够有效支持单纯用定量方法无法很好解决的半/非结构化问题的求解，主要依靠知识库和推理机的运用。,4.1 基本概念,数据：客观事物的属性、数量、位置及其相互关系等的抽象表示 例如：,二元组：（面粉，白色） 三元组： (中国，亚洲，在东面) (+, 8, 5): 今年8岁的孩子5年后的年龄 五元组： (+, X, Y, Z): X+Y=Z,4.1 基本概念,信息：数据所表示的含义（语义），是对数据的解释。 一般可用一组描述词及其值来表示： （描述词1：值，描述词2：值，）,例： （时间：2006.10.1, 地点：大连地区，天气：晴朗，程度：十分）,4.1 基本概念,知识：以各种科学方式将多个信息关联在一起形成的信息结构。 原子事实：不与任何其他信息发生关联的单独信息，是知识的一个特例。,例： “他是军人”、“他穿军装”均为原子事实； 而“如果他是军人，则他穿军装”是一条常识性知识。 另外，“如果某地重度异常，则有铝矿”是一条知识，但是不正确。,4.1 基本概念,知识的正确型类型： 正确，错误，部分正确，未知真假 知识的关联形式多种多样，可以是分层次的，即可以把知识解释为一种分层次关联的信息结构 可以用BNF形式定义知识,4.1 基本概念,知识:=| | | | :=|(的一个序列） := (的一个序列） :=,4.1 基本概念,知识的分类 事实：指人类对于客观事物属性的值或状态的描述，不包含任何变量，可以用一个值为真的命题陈述，或者用一种状态的描述来表达。 例如：,大海是蓝色的 我今年18岁 今天很热,4.1 基本概念,规则：指可以分为前提（条件）和结论两个部分，用以表达因果关系的知识。 一般形式为：如果A，则B A-B 可以用三段论推理形成一条推理链。,4.1 基本概念,规律：规则知识可分为带变量和不带变量两种形式。将带变量的规则称为规律。 规律中的变量一旦被实例化为一个具体的值，则规律就变成了一条不带变量的规则 一条规律通过变量实例化，可以派生出许多规则。因此，在这种意义上规律表示了一类知识，比规则更宽泛。,4.1 基本概念,知识的属性 真实性：应为经过实践检验的或者可用逻辑推理证明真伪的 相对性：在一定的条件和环境内有效 不完全性：许多知识是部分正确的 模糊性：许多知识不是完全精确的,4.1 基本概念,可表示性：可用某种方式加以描述 符号，图形，形态，等等 可存储性：可存储于人类大脑中，可以记录在书本上，也可以存储在电脑中。 可传递性：知识可通过某种媒体进行传递。 可处理性：知识可以利用各种方法和工具进行处理，从一种形式转变为另一种形式。,4.2 知识表示方法,4.2.1 一阶谓词逻辑 一阶谓词演算是一种形式语言，可用来表示各种“事实”，对知识表示和推理非常重要，在人工智能、知识工程等领域有重要作用。也可以作为知识库系统的推理基础。,4.2 知识表示方法,4.2.1.1 一阶谓词逻辑符号集及其知识表示 常量符号：用大写字母A、B、C、D等表示 变量符号：用小写字母x、y、z等表示 函数符号：用小写字母f、g、h等表示 谓词符号：用大写字母P、Q、R等表示 逻辑符号： 否定 合取 析取 限定量词： 存在量词 全称量词,4.2 知识表示方法,逻辑表达式构成用语的定义 项（iterm） 变量和常量 若t1, t2, , tn为项，则f(t1,t2,tn)为函数 原子逻辑式 若以p为谓词符号，t1, t2, , tn为项，则谓词符号对于项的作用为：p(t1,t2,tn)是函数,4.2 知识表示方法,谓词演算语言-逻辑表达式的几个实例 WRITE(STUDENT,PAPER) WRITE(x, y) WRITE(STUDENT,COMPUTER-CHESS) (x) WRITE(x,COMPUTER-CHESS) MARRIEDfather(JOHN),mother(JOHN) LIVES(JOHN,HOUSE) COLOR(HOUSE,YELLOW) OWNS(JOHN,CAR) = COLOR(CAR,GREEN),4.2 知识表示方法,4.2.2 语义网络表示 1. 语义：是指语义学的符号和表达式同它所描述的对象之间的关系。 2. 语义网络：以网络形式表示人类知识构造的一种图形工具，是一种有向图。,语义网络既可以作为人类联想记忆的心理学模型，又可作为计算机内部知识表达的一种形式。 它既能表达事实性知识，也可以表达事实之间的联系。,4.2 知识表示方法,3. 语义网络中的符号 节点：语义网络所描述的各种对象，表示各种事物、概念、属性及知识实体，有标识，并且可以是一个语义子网络，形成分层描述。 有向边（弧）：表示所连接的语义对象之间存在的某种语义联系（关系），也有标识。 无向边（短线）：语义网络中的节点一般采用具有若干属性的元组或框架来表示，由节点引出的带标识的短线（无向边）表示各个属性值,4.2 知识表示方法,由上图可以看出，由于语义网络中的下层节点可以继承、补充或修改其上层节点的属性值，因此能较好地表示对象之间的继承和变异等概念，适于表示推理、联想、归纳等逻辑概念，可根据其表示的知识来回答各种问题，验证各种事实（定理），乃至模仿人脑的逻辑思维，演绎或归纳出图中没有直接表示出来的新知识。,4.2 知识表示方法,4. 语义网络的形式描述 一个语义网络SN可形式化地描述为： SN= N, E 其中，N 是一个以元组或框架表示的节点的有限集，节点上的元组或框架描述该节点的各种属性值， E是连接N 中节点的带标识的有向边的集合，有向边上的标识描述该有向边所代表的语义联系。,4.2 知识表示方法,语义网络语法结构BNF描述 :=|Merge(, := :=(, ) :=:属性值 := | ,4.2 知识表示方法,5. 常用的语义联系 ISA联系：“是一个（只，条，种,）联系” “A ISA B”表示A是B的一个特例，B是比A更抽象的一个概念。 ISA联系在语义上可以表达很广泛的联系： 子集/超集关系 广义化/特殊化 - 抽象化/具体化,4.2 知识表示方法,概念包含关系 槽(slot)值的限制关系。例如：大象的躯体是一个1.3米长的圆柱体。 集合及其特征类的关系。 集合及其元素间的关系 谓词关系。例如：A是一个红球-红色（A）,4.2 知识表示方法,5. 常用的语义联系 Subset-of/Superset-of联系：A是B的子集/超集 AKO联系：A kingd of联系，例如：企鹅AKO鸟，因此“企鹅”可以继承“鸟”的“有翼”属性值，也有权更改“鸟”的“能飞”属性值。 A-Member-of/A-Element-of联系 A-Part-of联系 Composed-of联系,4.2 知识表示方法,5. 常用的语义联系 Have联系 Before/After/At联系：时间关系 Located-At/On/Under/联系：位置关系 Similar-To联系：相似或相近关系 Infer联系：前提与结论间的推理关系 Possible-Reson联系：是Infer联系的反联系,4.2 知识表示方法,4.2.3 产生式规则,产生式规则是由逻辑学家Post于上世纪40年代提出的，主要通过对符号串作替换运算（称为Post运算）进行推理，已被运用于很多领域，例如：表示形式语言的语法，描述程序设计语言的编译方法，或者用于各种推理系统的形式描述。 在产生式规则系统中，论域知识分为两部分： （1）事实：各种静态知识，如事物、事件和它们之间的关系。 （2）产生式规则：推理过程。,4.2 知识表示方法,由于这类推理系统的知识库中主要存储的是规则，因此又成为基于规则的系统（Rule-based system）,1、产生式规则的定义 一个产生式规则的一般形式为：PQ 其中，Q表示一组前提或状态，P表示若干结论或动作，其含义是：如果前提Q满足，则可推出结论P（或应该执行动作P）。,4.2 知识表示方法,在产生式系统中，一般利用一个解释程序，以匹配-执行的方式运用产生式规则知识。即：当右部Q能与一个已证结论集合（它最初由用户或系统所提供的全部事实构成）中的某个元素匹配（包括可能需要进行变量替换后才能匹配），则可运用该产生式，或推出结论P，并将其纳入已证结论集，或者执行P所代表的动作等。 如此循环往复地运用由一组产生式规则所表示的知识，以求得最终的结论，或解答问题，或证明定理。,4.2 知识表示方法,2、产生式的形式化描述及语义 :=, := :=空|, :=空|, :=| :=(, ) :=(, ),4.2 知识表示方法,3、产生式规则应用举例 35-55岁的人称为中年人 中年人是老练而细心的 老练而细心并且有驾驶技术的人不会出交通事故 吴连生43岁并且有驾驶技术 吴夫人37岁,问题：吴连生会出交通事故吗？,4.2 知识表示方法,首先将上述知识用产生式表示： 中年人(x) 年龄(x,y), 小于等于(y, 55), 大于等于(y, 35) 老练(x) 中年人(x) 细心(x) 中年人(x) 不会出交通事故(x) 老练(x), 细心(x),有驾驶技术(x) 年龄(吴连生，43岁) 有驾驶技术(吴连生) 年龄(吴夫人，37岁) ,4.2 知识表示方法,推理过程如下： 中年人(吴连生) 年龄(吴连生，43岁), 小于等于(43, 55), 大于等于(43, 35) 老练(吴连生) 中年人(吴连生) 细心(吴连生) 中年人(吴连生) 不会出交通事故(吴连生) 老练(吴连生), 细心(吴连生), 有驾驶技术(吴连生),问题：吴夫人会出交通事故吗？,4.2 知识表示方法,4.2.4 框架理论,框架理论是由美国著名人工智能专家Minsky于上世纪70年代初期提出的。他从心理学的证据出发，认为人们在日常的认知活动中使用了大量从以前经验中获取并经过整理的知识。这种知识往往以一种类似于框架结构的形式寄存于人脑中。,当人们面临新的情况，或者对问题的看法有重要变化时，总是从自己的记忆中寻找一个合适的框架，然后根据实际情况对其细节加以修改和补充，形成他对所观察到的事物的认识和处理方法。,4.2 知识表示方法,框架理论提供了一种知识组织结构，其中新的知识将用从过去经验获得的概念来解释，使人们能够利用已有经验处理新的问题，引起对有关事物的注意、回忆和推理，比较符合人们的思维习惯，因此，它是一种理想的结构化知识表示方法。,框架是一种表示定型状态的有层次的数据结构，其顶层是固定的，表示某个固定的概念、对象或事件，其下层由一些称为槽(Slot)的结构组成。每个槽可按实际情况用一定类型的实例或数据所填充（也称赋值，所填充的内容称为槽值）。下层的槽可以是一个能够进一步分层的子框架。,4.2 知识表示方法,相互关联的框架连接起来构成框架系统，或称框架网络。不同的框架网络通过信息检索网络，由可组成更大的网络，代表一块完整的知识模块,1、框架理论的运用 （广义）匹配：寻找一个其槽值与已知项目a, b, z一致的框架 让步：当无法寻找到一个与给定项目完全匹配的框架时，则可重新寻找新的框架，或者做出一些让步，接受一个相近的框架 相似网络：相似框架按照相似度用指针相连，形成一个检索网络。,4.2 知识表示方法,2、框架的形式化描述及语义 := :=框架名 :=| (, ) := :=约束, 框架名:= 约束:=,4.2 知识表示方法,:=, := :=| :=| | | :=| :=|,| ,4.2 知识表示方法,3、框架系统的预定义槽 ISA槽 Subclass/Superclas槽 AKO槽 Instance槽 Part-of槽 Have槽 Before/After/At槽,4.2 知识表示方法,3、框架系统的预定义槽 Locate-At/-On/-Under/-Inside/-Outside槽 Similar-To槽 Near-to槽 Infer槽 Possible-Reson槽 Classification槽 ,