V506合集-人工智能基础-浙大

人工智能基础浙江大学计算机学院高济4.3.专家系统实例——MYCINMYCIN概况通过提供咨询服务来帮助普通内科医生诊治细菌感染性疾病的专家系统。1972年开始研制，74年基本完成，并投入实际应用。MYCIN的取名来自多种治疗药物的公共后缀，如clindamycin、erythromycin、kanamycin等。最有影响力的专家系统，围绕着MYCIN的各种研究工作一直沿续了10年，对于推动知识工程以及专家系统学科的建立和发展具有重要影响。典型的产生式系统——深度优先的逆向链推理控制策略；INTERLISP编程，运行于DECPDP-10的操作系统TENEX下。主要内容：MYCIN知识库的构造，MYCIN推理机的设计，MYCIN系统服务设施，开发工具EMYCIN。4.3.1.知识库的构造以前提-动作型产生式规则来表示诊断和治疗细菌感染性疾病的专家级医学知识。规则的BNF定义：<规则>:=RULE<规则号>PREMISE($AND{<条件>}+)ACTION{<动作>}+<条件>:=<简单条件>|（$OR{<简单条件>}+）规则可视为前提-结论型，并能表示不确定性；前提部分中的简单条件常用：（SAME<对象><属性><值>）；最常用的动作：(CONCLUDE<对象><属性><值>TALLY<结论CF>)；TALLY——存放规则前提的实际可信度(CF—CertaintyFactor)；<结论CF>——规则前提CF为1（真）的情况下，结论为真的可能程度；规则结论的实际CF——TALLY与<结论CF>的乘积。MYCIN系统建立的初期就以上述格式表示和收集了200多条规则于知识库。规则例：4.3.1.知识库的构造关联三元组：对象——CNTXT（上下文），区分为10类，通过关联三元组中的属性名隐含指示；属性——属性名隶属于特别类型的上下文对象；值——通过向用户询问获取或基于规则推导出。4.3.2.推理机的设计分二个阶段四个步骤诊断和治疗细菌感染性疾病诊断阶段：确定病人有无治疗细菌感染的需要，确定引起感染的细菌；治疗阶段：制定若干可能的治疗方案，从中制定最佳的综合治疗方案。整个推理过程通过称为目标规则的092号规则来启动：4.3.2.推理机的设计

1诊断的推理控制

逆向推理和深度优先的搜索策略MYCIN由医生启动；以建立病人的治疗方案

(REGIMEN)为目标，激活规则092；通过逆向激活和使用规则，形成规则链，直到链末端规则的前提包含的条件都能直接由原始证据（医生提供的观测结果）证实；推理过程导致与或推理树（或称目标树）的建立——简单条件有与或关系，同一子目标（条件）激活多条规则。参见图4.9通过程序MONITOR和FINDOUT的嵌套调用推进整个推理（咨询）过程。MONITOR——分析相关的规则能否激活，参见图4.11，FINDOUT——搜索规则激活所需的数据（属性值及其CF），参见图4.12，导致深度优先的穷尽搜索。1诊断的推理控制在综合数据库（MYCIN称为动态数据库）中建立关于病人的上下文树（图4.10）。MYCIN将规则按上下文对象分类：每次对于一个目标作推理时，只需考虑该目标涉及的那个上下文对象相关的规则，大幅度提高了推理的效率。2不确定推理（略）3治疗选择机制（略）

4.3.3.系统服务设施

1推理解释

对医生的每次咨询都建立相应于病人的与或推理树和上下文树。在推理过程中或推理结束后可以回答医生（用户）对推理过程和推理结果的各种询问。规则追踪型推理解释——回答三种询问：WHY、HOW和WHYNOT。高级解释功能：基于记载于推理树中的推理链，设置了参数：复杂性和重要性，量化知识单元（规则和对象属性）的可解释性，依据用户知识水平加以裁剪的解释，为重要的且复杂性高的推理设置了封装的细化解释（超出规则本身的文字描述），以解释规则的前提和结论间的因果关联细节。2知识库维护

知识库中包含的推理规则，尽管形式上相互独立，但语义上却相互关联，形成推理树，语义上的关联，使知识库的维护面临困难。三类问题：包含（Subsumption）问题，单一规则的不一致，多规则的不一致——推理链的不一致。推理解释机制为知识库的维护提供了有力的支持。TEIRESIAS——高性能编辑器，能自动发现前述的包含和单一规则不一致问题，辅助知识库维护。3教学MYCIN的知识库包含了医学专家提供的丰富经验知识；GUIDON——基于MYCIN知识库的医疗教学。4.3.4.开发工具EMYCIN从MYCIN系统抽取出的与应用领域无关的骨架型专家系统开发工具。用于开发任何旨在提供咨询服务的专家系统，尤其适合故障诊断问题。

EMYCIN继承了MYCIN的主要特点，如下：采用逆向链深度优先的控制策略；使用产生式规则表示领域知识；允许事实和规则具有不确定性（以可信度指示）。规则的BNF定义：<规则>:=(IF<前提>THEN<动作>[ELSE<动作>])<前提>:=<条件>的与或组合<条件>:=<关联三元组><动作>:=<关联三元组><关联三元组>:=(<属性><对象><值>)EMYCIN开发的专家系统：PUFF、HEADMED、SACON、ONCOCIN、CLOT、DART。4.4.问题求解的结构化组织开发和维护KB系统的困难一直困扰着知识工程；传统的观点——知识获取瓶颈：知识获取比喻为采矿，而KB系统则视为存放知识的容器，未揭示困难的本质，并在某种程度上误导了了克服困难的努力方向。建模观点：KB系统是模拟人的问题求解行为和应用领域世界的模型，按系统化、结构化和功能化的方式来分析人的问题求解行为和领域世界。以概念模型作为语义框架，指导和约束知识获取及知识库维护。建模观点需要问题求解的结构化组织。主要内容：结构化组织的需求，事务表，黑板法，问题求解建模（略），新一代KB系统技术（略）。4.4.1结构化组织的需求

表示和组合应用领域知识的最简单策略——把问题求解所用的全部知识统统表示为规则。随着要求解决的实际问题越来越复杂，规则库也越来越大；产生式系统的缺点就显示出来：（1）难以扩展。尽管规则形式上相互独立，但在问题求解中却往往彼此相关。例如MYCIN系统使用逆向规则，每一规则之前提部分的谓词公式只要不与事实匹配，就必须通过别的规则作逆向推理，以搜索支持解答的证据。显然，这些规则具有紧密的相关性。实际上，MYCIN的规则构成了推理网。随着规则数目的增加，要使新加入的规则不与原有的规则发生矛盾变得越来越困难，即随着规则库的扩展，一致性维护越加困难。（2）选择规则的低效性。由于规则是堆积在规则库里的，问题求解中的每一推理步都要对规则库作穷尽的匹配检查，以便选择合适的规则。显然规则库大时，效率就低。实际上，一个推理步只涉及若干特别的规则，可以把它们构成一个规则组。只有上一规则组用完后，才考虑下一规则组。4.4.1结构化组织的需求（3）不灵活的控制策略。产生式系统往往采用单一的控制策略（例如按顺序考察规则库中每一规则），而实际问题的求解常需要综合应用不同的控制技术。（4）单一的表示形式。尽管从理论上讲，产生式系统可以表示任何推理知识，但对于有结构的知识或许以语义网络和框架系统表示更为有效。克服缺点的方法——将求解复杂问题的知识划分为一组相对独立的模块。模块的划分：面向动作——以推理动作的选取为核心组织问题求解所需的知识：面向“怎么做”知识的组织，医疗诊断中，知识是以症状和疾病间的关联、疾病与治疗动作间的关联等方式表示和组织的；面向对象——以概念和个体为单元组织问题求解所需的知识：面向“是什么”知识的组织，建立关于疾病的分类体系和疾病症状的分类体系。4.4.2.事务表事务表(Agenda)——

一张应由系统执行的事务的列表，也称任务表。面向动作的问题求解组织方式。结构化组织（图4.13）：表中元素——表示一个等待执行的任务，任务——由特定的推理模块执行，按优先级大小排序——按理由表来计算，每个任务附有一张理由表，记载由其它任务提出的支持或反对执行该任务的理由。优先级最高的任务意味着它的执行最为紧迫和最有意义。模块间通信——对执行某些任务提出支持或反对理由，模块间保持着相对的独立性。4.4.2.事务表数论概念发现系统AM——

应用事务表的典型系统：任务——从集合论的一些基本概念出发，发现数论新概念，发现大量数论新概念(对AM来讲)：从质数到哥德巴赫猜想；基本概念和发现的新概念组织为一个概念网(图4.14)；概念以框架形式表示；启发式推理规则——附加于表示基本概念的框架，指导新概念的提出和完善。执行任务的推理模块不固定——任务执行时动态构成系统在概念网中收集(沿着该任务拟发现的概念到顶点的路径)分散于基本概念框架中的启发式规则。通过事务表，把有关问题求解的各种信息汇集起来，使独立的模块能在推理过程中合作求解问题。设计决策——复杂问题分解为子问题的精细程度：分解太细：大幅度增加事务表中排序子任务的工作量；分解太粗：不利于发挥模块化的优点；需作权衡利弊。4.4.3.黑板法

起源：70年代，口语理解系统HEARSAY—Ⅱ。面向动作的组织方式。结构化组织——一组知识源，信息黑板。知识源(KS—KnowledgeSource)——独立推理模块（图4.15）：触发模式——以谓词公式表示：与黑板上的内容匹配时，产生一个激活记录；记载该KS的名字、触发上下文和模式中变量的约束值。直接码——

一段Lisp代码：参考触发上下文和模式变量的约束值加以执行，将该KS有关的调度控制信息加进激活记录。4.4.3.黑板法KS体——规则组甚至一段任意的程序，包含求解问题所需的专门知识。KS激活时，KS体不立即执行而是置于一排序表；排序KS体——

一个调度程序分配和修改每个激活记录的优先级；具有最高优先级的KS体——下一个要执行的，其参考激活记录中的触发上下文和模式变量的约束值，KS体一经执行，不能中断，直至结束。信息黑板——所有KS可以访问的公共数据区：黑板的内容由解答空间(状态空间)中的对象构成：这些对象可以是输入数据、部分解答和最终解答。黑板的分划：记载于黑板中的对象层次地划分到不同的分析级，每一级均设计一组相应的KSs：以该级对象作为输入，计算(推理)结果加到该级或其它级。HEARSAY—Ⅱ（图4.16）将关于口语识别的假设(可能的解答，表示为对象)分为8个等级，从关于声音的低级假设到关于整个句子文法分析的高级假设。4.5基于本体的知识系统

基于本体的语义知识表示推动了各种基于本体的知识系统（KnowledgeSystems）的开发，去实现智能信息服务、语义网格、知识管理、协同问题求解等，极大地丰富了语义Web的建设和应用。这些知识系统不同于传统封闭型KB系统的根本区别在于：前者是开放的，往往由分布于因特网的异构成员系统静态或动态构成，须依赖基于本体的语义互操作来实现协同工作，以及信息和计算资源的共享和重用。共享本体成为开发上述知识系统的基础，导致了本体工程从传统的知识工程脱颖而出，成为独立的研究领域。本体工程的研究可以划分为2个范畴：基础级本体工程——聚焦于本体开发方法和支持工具；高级本体工程——研究本体的学习、映射、演化和融合，以提高本体构建和管理的自动化程度。4.5.1基础级本体工程

本体工程（OntologicalEngineering）研究本体开发方法论，并提供本体表示语言和开发工具。可以说本体工程是知识工程的后继，但远远超出知识工程的研究范围和效用。尽管知识工程促进了专家系统的成功，但维护、共享和重用知识库中的知识面临较大的困难。知识工程自90年代初开始从传统的面向表示的研究方式转变到面向内容的方式，旨在给知识库的设计、领域世界的概念化和概念的语义约束提供基本原理，以及知识积累的理论和技术。语义Web技术的兴起，推动了本体工程从面向知识库和专家系统的知识工程脱颖而出，成为新兴的研究领域。4.5.1基础级本体工程聚焦于本体开发的手工方式：由本体工程师借助本体编辑器来进行本体的人工构建。可以说，目前的本体开发大多采用手工方式。手工方式构建本体的成功关键：本体工程师必须充分理解应用域的概念化模型及其演化趋势，并广泛听取专家和潜在用户的意见，以使建立的本体能够正确反映世界本质，并获得应用域的一致赞同。手工方式面临耗时费力、易于出错、且不利于本体维护和更新的困境。通过提高自动化程度，高级本体工程技术有助于克服这种困境，但目前尚没有成熟的本体自动化生成方法。4.5.1基础级本体工程

1本体构建的准则和过程构建本体的基本准则（史忠植和王文杰）：明确性和客观性一致性可扩展性最小编码偏差最小本体承诺目前尚无公认的本体设计和评价标准，以及相应的质量保障体系。应用域共享本体的构建是一个循序渐进、逐步深化的过程（史忠植和王文杰提议的8-步骤过程）：1）分析构建本体的功能需求和非功能需求2）规划本体的开发任务3）获取应用域基本信息4）确定本体应包含的概念、属性和关系5）编码抽取的概念化描述时6）评价建立的本体7）本体演化8）本体展示应该指出，上述8-步骤过程只是本体构建过程的一种粗略表征。4.5.1基础级本体工程

2本体开发方法存在一些可以参考的方法，例如：METHONTOLOGYOn-To-Knowledgemethodology米泽格奇（Mizoguchi）提议将本体开发的指导划分为三层（图4.22）：顶层——以粗线条方式指导本体开发过程。鉴于开发的本体也可视为一种计算机程序，本体开发过程应遵从常规的软件开发过程。中层——说明本体开发的主要步骤和次序，作为约束和指导。底层——给设计本体的细节提供指导。米泽格奇设计了面向中层和底层的指导。4.5.1基础级本体工程

3本体开发工具

本体开发方法必须有相应的支持工具，并选用适当的语言表示建立的本体。本体表示语言的研究——已逐渐收敛到RDF、DAML+OIL、OWL系列。支持本体开发的工具和环境：

OntoEdit、WebODE、Protégé、Hozo它们都覆盖大范围的本体开发过程，而非单一目的工具。WebODE体系结构的示意图WebODE体系结构4.5.1基础级本体工程

4已开发的本体及其应用已经存在相当数量的本体开发成功并投入应用，其中最著名的是Cyc自84年开始建立，初期作为一个常识性知识库，现已发展为拥有10万个概念和一万个谓词的特大型“upper”本体，用于描述关于“自然存在”的高级范畴，包括数量、性质、关系、位置、时间等通用概念。其它著名的本体有Wordnet（美国普林斯顿大学开发的联机词汇参考系统）、Enterpriseontology（英国爱丁堡大学）、Geneontology、Processontology:PSL、UpperOntology(SUO)、DAML+OILontologylibrary该库已包含251个以DAML+OIL或OWL表示的本体。依据本体的角色和特征，可以将本体的应用大致划分为5种类型：

作为公共词汇、作为信息存取的辅助、作为相互理解的媒介、 作为规格说明、作为实现知识系统化的基础OpenCyc的顶层分类体系

4.5.2高级本体工程高级本体工程旨在研究本体的学习、映射、演化、合并和融合等，以提高本体构建和管理的自动化程度。书上简略介绍了本体的映射、演化和学习，本体的合并和融合可视为以本体映射为基础的上层任务。4.5.3开发基于本体的知识系统

本体工程和基于本体的语义知识的研究和开发，推动了以资源共享和协同工作为目标的大量因特网计算环境下知识系统的开发。下面从3个范畴：语义Web、知识管理、分布协同，来讨论基于本体的知识系统。1语义Web语义Web又称第二代WEB，与基于HTML页面的第一代Web主要供人浏览和搜索文字内容的特点相比较，语义Web旨在使机器能理解信息和加以自动处理，以支持对信息源和网上服务的集成和统一存取，以及关于Web信息处理的智能应用，如信息代理、搜索Agent、信息筛选。4.5.3开发基于本体的知识系统2知识管理随着信息和网络技术的发展，介绍和阐述先进和创新理念的信息体越来越多地发布于组织内网和因特网,促使知识管理（KM,KnowledgeManagement）成长为实现知识共享，进而提高人类组织竞争力的重要技术。将内涵（隐含）于信息体的先进和创新理念作为共享的关键知识，通过收集、分析（和解释）、查询、推送和维护内涵这些知识的信息体，KM系统旨在使合适的知识能够在合适的时间，以可操作的方式到达组织中需要它的合适成员，以求最大化创新潜力和工作效益。3分布协同因特网环境下的分布协同旨在促进Web资源的共享和跨平台协同问题求解，其高级阶段是支持虚拟组织（VO,VirtualOganization）的按需动态组建和运作。人工智能基础浙江大学计算机学院高济6.2示例学习

归纳学习——从教师或环境提供的事例中抽象出结论（对于概念的泛化描述）的知识获取过程。归纳推理的理论——研究如何运用各种推理技术，在符号表示的空间中进行启发式搜索。常用推理技术：泛化(generalizing)特化(specializing)转换(transforming)知识表示的修正和提炼(correcting&refining)主要内容：示例学习的基本策略概念描述的搜索和获取三种示例学习策略：逐步泛化的学习策略逐步特化的学习策略双向学习策略。示例学习的一个变种——决策树学习算法ID36.2.1示例学习的基本策略示例学习是机器学习中研究得最深入的一种方法。结构化概念学习程序：七十年代中期，温斯顿(Winston)，积木块玩具世界的线条画；近似匹配、概念泛化和概念特化技术；从一系列正、反示例中归纳出某类积木块（例如拱形物）的概念定义：表示为语义网络的结构化描述。示例学习遵从一般的归纳推理模式:已知：１）关于观察（观察到的事例）的描述Ｆ；２）初始的归纳断言；３）问题域的背景知识；求：归纳断言Ｈ，其应蕴涵关于观察的描述，并满足背景知识。1概念描述的搜索和获取

解描述——通过示例学习获取的知识：完全、一致地包含正、反例子集的概念描述：概括（覆盖）所有正例的概念描述，称为完全描述；不概括任何反例的概念描述则称为一致描述。一般情况下，解描述可以有无数个。背景知识提供约束和评判标准——使归纳推理的结果集中于一个或几个有限的最优假设。例子空间和假设空间：例子空间——所有可能的正、反例构成的空间；假设空间（又称概念空间）——所有可能的概念描述（称为假设）构成的空间；假设空间中的每一假设都对应于例子空间中的一个子集，使得该子集中的例子均是该假设的例子。假设的泛化和特化：假设D2是D1的泛化——D1所对应的例子集是D2所对应例子集的子集，假设D1是D2的特化。泛化关系——反对称、可传递的，假设空间是半序集（偏序集）。示例学习的过程——在假设空间（概念空间）中搜索的过程，米切尔（T.Mitchell,1982）。1概念描述的搜索和获取病态细胞的分类识别例：正例——三个病细胞(P1,P2,P3)，反例——二个正常细胞(N1,N2)；每个细胞由二个细胞体组成：细胞体表示为三元组：（核数、尾数、染色状），P1：{(2,2,深)(1,1,浅)}。学习任务——从例子集中归纳出有病状Ｘ的细胞概念描述。假设不必给每个特性（属性）都指明应取值：没有给出值的特性（以？指示）——对于该概念的描述无关紧要；病细胞假设(ａ)：{(2,?,?)(?,1,深)}，一个细胞体有二个胞核；另一个有一个尾巴，且染色是深的。1概念描述的搜索和获取病细胞假设空间的半序图（图6.5）：图6.5假设之间的关系弧指示泛化/特化关系，假设空间上的一个泛化/特化关系（图6.4）：假设（ｂ）不考虑细胞体是否有尾巴，比假设（ａ）复盖更多的例子；假设（ｂ）比假设（ａ）泛化；假设（ａ）比假设（ｂ）特化。底层假设——最特化（具体）的概念描述：所有特性都给定特别值，图6.4

对应于例子空间中的一个例子。顶层假设——最泛化的概念描述：不指定任何具体的特性值，表示为{(???)，(???)}。1概念描述的搜索和获取假设空间中的搜索方式：特化搜索——从最泛化的假设（概念描述）出发，每次取用一个新的例子，就产生一些特化的描述，直到将初始最泛化的假设特化为解描述。泛化搜索——从最特化的假设（相应于例子空间中的一个例子）开始，每次取用一个新的例子时，就产生一些泛化的描述，直到产生出足够泛化的解描述。大多数示例学习方法都采用这二种方法或这二种方法的结合。2逐步泛化的学习策略采用宽度优先、自底向上的搜索方式：将第一个正例（P1）作为初始假设（H1）——极端特化的假设；正例（P2）用于指导系统生成泛化的假设（H2和H3）：多个泛化的假设——不同的映射会导致不同的假设，假设H1中包含了二个对象（细胞体）；采用保守原则——

最低限度的泛化：新的假设刚好覆盖现有的假设/例子。2逐步泛化的学习策略反例（N1）用来剪裁过于泛化的假设：图6.6

H3是过于泛化的假设，因为其蕴涵了反例N1。基本策略：遇见正例就泛化某些假设以保证假设的完全描述性,遇见反例则删去某些假设以保证假设的一致描述性,直至得到一个既完全又一致的解描述

(假设)为止。这个解描述作为满足给定例子集的概念定义——学习系统获得的新知识。实现逐步泛化学习策略的算法。3逐步特化的学习策略

采用宽度优先、自顶向下的搜索方式（与泛化策略相反）：新例子的加入会导致新假设的增加和已存在假设的删除（与泛化策略类似）。正例和反例所起的作用与泛化策略相反：反例——生成一些特化假设；采用保守的原则——最低限度的特化：新的假设在覆盖已有正例的同时只是刚好能排斥反例；正例——剪裁过于特化的假设。实现逐步特化学习策略的算法（参见书上）。以特化策略获得的解描述（学习系统期望的概念描述）是特化程度最低的；以泛化策略获得的解描述则是泛化程度最低的；只要给出充分多的例子，二者的结果应是相同的概念描述。4双向学习策略

将上述二种策略结合起来,同时从二个方向搜索假设（概念描述）空间；以期获得仅用单一策略所不具有的优点。版本空间法（米切尔）：用两个假设集Ｓ、Ｇ分别表示作泛化、特化搜索的假设空间。遇见一个新的正例时，如未被Ｓ集包含，则在该集中进行泛化搜索；一个新的反例产生时，如被Ｇ集包含，则在该集中进行特化搜索。Ｇ和Ｓ指示期望获取的最终解描述的上、下界，当Ｓ、Ｇ合一时，合一的解描述就是期望学到的概念描述（定义）。版本空间法的特点：系统不必保留正例和反例：Ｓ本身蕴涵了已取用的所有正例，可用来删除Ｇ集中过于特化的假设；Ｇ本身蕴涵了对所有已取用反例的排斥，可用来消除Ｓ集中过于泛化的假设。系统知道何时推理任务完成，即当Ｓ、Ｇ合一时。实现双向学习策略的算法（参见书上）。6.2.2决策树构造法ID3任务——对大的例子集作分类概念的归纳定义：例子用无结构的属性-值对来表示：每一个例子用相同的一组属性来表示，每一个属性又有自身的属性值集；构造决策树的目的是为了对事物作出正确的分类；ID3——昆兰（J.R.Quinlan，1986）。学习的结果——决策树：判别树，转而表示为决策规则的一个集合，用于区分待识别事物的类属。决策树构成：非叶节点对应一个需测试的属性，每个分叉就是该属性可能的取值，树的叶节点指示一个例子事物的类别。6.2.2决策树构造法ID3优点——归纳学习花费的时间和所给任务的困难度成线性增长关系：例子个数，对象的属性个数，所学习概念的复杂度——

决策树的节点数。

人分类例（图6.11）：预先定义一组属性及其可取值：高度{高，矮}，发色{黑色,红色，金色}和眼睛{兰色，棕色}；人分为两类，分别以＋、－来指示；选取属性“发色”为树的根节点：三值——三个对象子集（分支）；按属性“眼睛”划分“金色”这一分支（对象子集）：二值——对应于兰色和棕色的对象子集；二级决策树生成——所有叶结点相应的对象子集只含同一类的对象；带有类别名的决策树——用相应的类别名（＋和－）来取代各子集（图6.12）。6.2.2决策树构造法ID3图6.11图6.126.2.2决策树构造法ID3属性的优先选用决策：选择一系列有用的属性来测试一个对象集，以使生成的决策树是最小的；香农（Shannon）信息论中的方法：决策树可看成一个信息源——给定一个要检测的对象，可从决策树产生一个该对象所属类别的消息(比如类别"+"或"-")。对给定的物体集C：M(C)——从C集对应的决策树中得到消息的期望信息量：用于量度判别一个对象的类属所需的测试工作量，决策树传递的不同类别消息的概率用P+(对应于"+"类)和P-表示(对应于"-"类)，

M(C)=-P+log2P+-P-log2P-，把概率近似地表示为对象类属在示例集中发生的频率。对于人分类例：C集有八个例子，三个为“+”，五为“-”，

M(C)=-（3/8)•log2(3/8）-（5/8•log2(5/8）=0.954bits6.2.2决策树构造法ID3对给定的物体集C：B(C，A)——按属性A构造决策树后，从树的其余部分得到消息的期望信息量：Ai为属性A的值且是互斥的，属性A将集合C划分为若干个子集的集合{C1，C2，...，Cn}，M(Ci)——从对应于值为Ai的子集Ci，为判别一个对象的类属，能从子决策树中获取消息的期望信息量，期望信息量B(C，A)

可通过权值平均而得到（图6.13）:B(C，A)＝∑(A值为Ai的概率)*M(Ci)。选定的测试属性应使决策树获得最大的信息增益：M(C)－B(C，A)最大。6.2.2决策树构造法ID3

图6.14以“高度”判别的决策树

6.3基于解释的学习

八十年代中期兴起的新型机器学习方法：通过应用领域理论（领域知识）对单一事例所作的分析，构造满足预定目标概念并遵从可操作准则的一个解释。知识密集型的，可克服归纳学习因缺乏领域知识的引导而面临的问题；与基于大量训练例作归纳推理的数据密集型学习方法不同。基于解释的学习是分析学习的主要方式：利用丰富的领域背景知识，将单一例子（或几个例子）泛化为对目标概念的解释；依赖于演绎推理，产生更有效的问题求解知识，如搜索控制知识；主要目的——提高问题的求解效率而非获取新的概念描述。主要内容：基于解释的泛化（EBG，Explanation-basedGeneralization），基于解释学习的若干基本问题。6.3.1基于解释的泛化（EBG)米切尔(T.Mitchell)，1986EBG的问题描述：给定：

·

目标概念：对于所学概念的一个初始描述（其尚不满足可操作准则）；

·

训练例子：目标概念的一个正例；

·

领域理论：解释训练例子为何是目标概念正例可用的规则和事实集合；

·

可操作准则：学到的知识（对于目标概念的解释）所需遵从的表示形式，以使这些知识能用于问题求解活动。获取：对于目标概念的一个特化描述，其是训练例子的泛化，且满足可操作准则。基于解释的泛化过程（二个阶段）：

(1)解释：使用领域理论建立一个证明训练例子满足目标概念定义（初始描述）的解释结构；该结构可表示为一颗证明推理树，又称解释树，其每个分枝的叶节点上的表达式都必须满足可操作准则。

(2)泛化：通过将解释结构中的常量变换为变量（实现对于训练例子的泛化），获得对于目标概念的一个特化描述，使其满足可操作准则：基于解释结构对目标概念进行回归(regressing)，对回归所得的表达式（相应于解释结构中的叶节点）加以合取。6.3.1基于解释的泛化（EBG)EBG的第一个阶段（即解释阶段）：确定例子的哪些特性与目标概念有关，哪些特性是无关的，建立关于训练例子如何满足目标概念的一个解释：解释结构：一个证明

——演绎推理过程。第二阶段（泛化阶段）：在解释结构中对目标概念Safe－to－stack(x，y)进行回归（图6.16）；自顶向下地遵从解释结构去逆向应用推理规则；使目标概念回归到能推出它的泛化的（常量变换为变量）初始条件（相应于解释结构中的叶节点）；建立目标概念的特化描述：满足可操作准则，目标概念

Safe－to－stack(x，y)的充分解释，初始的目标概念是这个特化描述的推理结论。6.3.1基于解释的泛化（EBG)EBG的重要特性：学习活动特别依赖于学习程序已经知道了什么:EBG方法对它的领域理论是高度依赖的，EBG方法是依赖领域理论中的知识对例子进行解释的。领域理论中知识结构的缺陷可能导致解释失败，从而EBG过程失败。规则矛盾、规则遗漏（不完全）等。可操作准则是学习程度的重要指标。本例中的可操作准则是静态（即不随系统性能的改善而变化）和离散的（即只将表达式分为可操作和不可操作二种）。为了提高利用（识别）目标描述的效率，可操作准则应可以随系统性能的提高而变化。6.3.2基于解释学习的若干基本问题

基于解释学习的可操作性可操作准则用于评价使用概念描述的有效性。可操作准则作为搜索终止的标准。可操作准则的定义应满足：能用性：能够被学习系统用来识别所描述概念的实例。效用性：当学习系统使用该描述时，系统的执行性能应得到改善。可操作准则的特性度量：可变性，粒度，确定性。不完善领域理论：能否从例子得出一个合理的解释依赖于领域理论是否完善。在复杂的实际领域中，往往难以构造出一个完善的领域理论：不完全的理论，不一致的理论，不可控的理论。要求学习系统有能力自动检测、改正不完善理论或有方法弥补领域理论的不足。人工智能基础浙江大学计算机学院高济6.7知识发现与数据挖掘

技术开发背景：随着数据库技术和计算机网络的发达和普及应用，全世界数据库和因特网中的数据总量正以极快的速度增长。数据的急剧膨胀和时效性、复杂性远远超过了人们的手工处理能力，人们突然发现自己面临着信息海洋，却无法及时和有效地从中获取所需的知识。人们迫切需要高性能的自动化数据分析工具，以高速、全面、深入、有效地加工数据。主要内容：知识发现（以定理发现为例），数据挖掘（综述），数据库及网络中的知识发现（介绍）。6.7.1定理发现

早期科学研究中，经验公式（定理）的发现有举足轻重的作用。基本方法：给出：一系列相关数据项x1，x2，…，xn和相应的一组观察值(vi1,vi2,……vin)；i=1,2,...,m；找出：一个公式f,使f(x1,x2,…xn)=0满足这组观察值。BACON系列：BACON1－BACON5兰利（P.Langley），1978，以英国科学哲学家培根(1561-1626)命名。BACON3——重新发现了理想气体定律、开普勒第三定律、库仑定律、欧姆定律及伽利略单摆和匀加速度等定律。BACON4：重点是通过发现学习，把数据集合描述成某种简洁的形式，包括收集数据、形成解释性理论和实验预测等技术。产生式系统，OPS5，数据驱动型（正向推理）通用发现学习系统。关键技术——假说形成、推理项确定、符号型变量的固有性质。1形成假说

标准的科学分析方法把世界划分成数据(观察事实)和假说(定律)二部分：假说是对这些数据的解释和归纳。BACON4的层次描述方法： 最低层的描述信息就是数据；最高层是称为定律的假说；中间层次的描述——双重身份：作为上层描述参考的数据，作为下层描述的假说。例子：理想气体定律：PV/nT＝8.32n—克分子量对于多组数据（下层描述），若部分自变量取值固定时，不管其它自变量怎么改变，因变量的值总是保持不变；则形成假说——在这些自变量取该固定值时，因变量有相应固定值：P、n、T

V（第一层描述）当T=300，n=1时，总有PV=2496.0（第二层描述）；T、n

PV当n=1时，总有PV/T=8.32（第三层描述）；n

PV/T逐层归纳，最后获得理想气体定律：PV/nT＝8.321形成假说指导对观察描述的逐层归纳——经典的归纳推理启发式：IF在L层中存在一组描述,且这些描述中的因变量D具有相同的值V；

THEN生成一个L+1层的描述,其指出D取值为V,且把L层的那组描述中的所有公共条件作为D取值为V的条件。指导寻找因变量取值相同的一组描述（n=1时，总有PV/T=8.32），因变量的值既可为数值也可为符号。2确定推理项被归纳的因变量(V,PV,PV/T)逐步变得复杂：V用在第一层描述中，PV用于第二层，最后的定律描述中所用的是复杂的算术组合项PV/nT。推理项——由可直接观察的变量（这些变量的值可直接测量到）组合而生成的项（因变量）；推理项的取值并不是通过直接观察获到的，而是由计算得来的。用以简化复杂规律的描述。2确定推理项推理项的确定：使用称为趋势探测器的启发式搜索方法来搜索推理项空间,

寻找数值-变量对间的单调上升/下降关系。启发式规则（参见书上）：若发现因变量与自变量取值有递减关系，则计算关系曲线的斜率。若斜率是常数，则建立二个新的推理项：斜率项和截距项。开普略第三定律发现例：D3＝kP2；D/P，D2/P，D3/P2。推理项的逐层确定：推理项定义后，和直接观察的变量（自变量）没有区别；可作为上层描述（假说）参考的数据。递归地应用相同的启发式逐步生成更复杂的高层次描述，使系统具备相当强大的搜索经验定律的功能。3提出固有性质

趋势探测器不能使用于符号型变量；例子：在一个电路中接入不同的线圈X、Y、Z时，电流发生了变化。固有性质（如电导率）：启发式规则来假设符号型变量（电线）具有某种固有性质（如电导率）：若在其它条件固定时（用同一电源），该符号型变量取值的变化引起某因变量（电流）随着变化；则该符号型变量具有某种固有性质，其取因变量（电流）的值。假想性质——新变量:假想性质＝因变量值/固有性质值，例：I/C＝电流(I)/电导率(C)；初始时，值为1.0(此时固有性质的取值就是因变量值)；随着观察条件的改变（用另一种电源），假想性质的值会不同（≠１）；系统可以发现新的推理项，以建立新的经验定律。

3提出固有性质欧姆定律发现例：为符号变量“电线”设立固有性质“电导率C”——作为推理项：“电导率C”的值＝“电流I”（因变量）的值；建立假想性质I/C作为新变量，初始值取1；假想性质＝因变量值/固有性质值改变条件：电池A改变为B，假想性质I/C随着改变（变成1.14）；为符号变量“电池”设立固有性质“电压V”——作为推理项：“电压V”的值＝新因变量I/C的值；建立假想性质I/CV作为新变量，初始值取1；欧姆定律发现：I/CV＝1：无其它有实质性影响的自变量存在；指示因变量“电流I”、符号变量“电线”的固有性质“电导率C”、符号变量“电池”的固有性质“电压V”三者的关系。符号变量“电线”固定时，符号变量“电池”的值改变，导致因变量（电流）的值随着改变：符号变量“电线”的固有性质（导电率）值保持不变；指示“电池”的变化不会影响“电线”的固有性质——电导率和电池无关。

6.7.2数据挖掘

一般概念：从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程。通常采用机器自动识别的方式，不需要更多的人工干预。知识发现技术在数据库领域中的应用：在一个已知状态的数据集上，通过设置一定的学习算法，发掘出数据间隐含的一些内在规律。数据仓库——

一种特别的数据库：它存储的数据与普通数据库中的数据不太一样：从常规数据库抽取出的经过加工整理的数据。数据挖掘的应用：为用户的决策分析提供智能的、自动化的辅助手段：零售业、金融保险业、医疗行业等多个领域。能解决的典型商业问题：数据库营销、客户群体划分、背景分析、交叉销售等市场分析行为，以及客户流失性分析、客户信用打分、欺诈发现。6.7.2数据挖掘数据挖掘的应用市场正在逐渐形成，应用前景十分广阔：很多厂商（IBM、SGI、Neovista等）投入研发工作，提供商业化的数据挖掘工具，并已应用到多个数据仓库系统中。1数据挖掘应用分类分类模型——通过归纳推理去分析样本数据的分类属性，找出基于这些属性作分类的模式。关联模型——发现数据项间隐含的相关性，通常表示为关联规则集，并设置信任级别来度量关联规则的强度。时序模型——发现某一时间段内数据间的时序关系，可视为增加了时间属性的关联模型。聚类模型——按照某种相近度量方法，将待分析数据分成互不相交的一些分组（聚类）。6.7.2数据挖掘2数据挖掘采用的典型方法及工具神经网络——复杂的模式抽取及趋势分析。决策树——对数据进行分类，并将数据的分类规则可视化。粗糙集（roughset）——新的处理含糊性和不确定性的数学工具，主要用于挖掘关联规则。联机分析处理——基于称为数据立方体的多维数据模型，通过对数据立方体的切片、切块、旋转、钻取等操作来实现快速的多维存取；支持数据分析、查询和产生报表。数据可视化——按恰当的隐喻来表示数据，为数据分析人员提供帮助。6.7.3数据库及网络中的知识发现数据挖掘仅是从数据库（或数据仓库）中发现知识的一个特定步骤发现知识的完整过程——还需要有数据收集、数据整理、知识验证等作为前序和后验步骤。数据挖掘技术可以推广到网络数据的挖掘中。6.7.3关联规则挖掘关联规则的挖掘是较早得到密集研究，且应用最为广泛的数据挖掘技术。作为一种常见、又十分重要的知识模式，关联规则用于反映事物间的相互依存关系，使得这些事物中的1-多个能通过其它事物的出现来预言。关联规则的概念由Agrawal、Imielinski和Swami于1993年提出，属于描述性模式，发现关联规则的算法则属于无监督学习方法。6.7.3关联规则挖掘

1关联规则的基本概念关联规则常用于描述从事务数据库中抽取出的不同数据项（作为对事物自身的原始描述）间同时出现的规律性知识模式相关于关联规则挖掘的概念和术语定义如下：1）项和项集设I=(i1,i2,…,im)是事务数据库中被关注的m个数据项的集合，每个数据项ij(j=1,2,…,m)就简称为项，并有唯一标识；项的集合称为项集，包含k(≤m)个项的项集称为k-项集，I是项全集(即m-项集)。2）事务和事务数据库设数据挖掘任务关注的事务数据构成事务数据库D，描述单一事务的数据简称为事务，从而D是所有事务的集合。显然，每个事务d包含的项集T(d)⊆I。每个事务有一个标识符（如交易编号），记作TID。超市交易数据库:每个购物篮的交易记录、所有购物事务、购买的物品、项全集I6.7.3关联规则挖掘

1关联规则的基本概念3）项集支持度项集支持度是包含该项集的事务出现的概率，可以通过取包含该项集的事务数与事务数据库D包含的事务总数之比作为近似值。所以项集W(⊆I)的支持度

support(W)=|{d∈D|W⊆T(d)}|/|D|6.7.3关联规则挖掘

1关联规则的基本概念4）关联规则的支持度和置信度关联规则表示为形如X⇒Y的蕴涵式，其中X⊂I，Y⊂I，且X⋂Y=∅。X、Y分别作为规则的前提和结论。令规则的支持度support(X⇒Y)=support(X⋃Y)，并定义规则的置信度为事务数据库D中包含X的事务同时也包含Y的条件概率，可近似表示为

confidence(X⇒Y) =|{d∈D|X⋃Y⊆T(d)}|/|{d∈D|X⊆T(d)}|=support(X⋃Y)/support(X)支持度指示了作为关联规则前提和结论的项集X和Y同时出现于D中事务的频度，而置信度则指示了结论Y依赖于前提X的关联程度。6.7.3关联规则挖掘

1关联规则的基本概念5）频繁项集min-sup——挖掘关联规则时需满足的最小支持度，取值区间为(0,1)；频繁项集（或称大项集）——满足mi-sup的项集，频繁k-项集的集合记为Lk。频繁项集的鉴别使得关联规则挖掘的注意力集中于出现频度较高的事务，大幅度提高了工作效率。min-conf——最小置信度其反应了关联规则的最低可靠性，即只有满足min-conf的关联规则才是可信任的。称支持度和置信度分别不小于min-sup和min-conf的关联规则为强规则，挖掘关联规则的任务实际上就是寻找强关联规则。6.7.3关联规则挖掘

1关联规则的基本概念例子：某超市一个月的购物交易记录（事务）有9万个，其中包含啤酒的记录2万个，同时包含啤酒和尿布的记录1万个。超市已指定min-sup和min-conf分别为0.1和0.4，则可以发现：“啤酒”⇒“尿布”是一条强关联规则。由此规则的前提和结论构成的项集：{“啤酒”，“尿布”}具有支持度0.11，即support(“啤酒”⇒“尿布”)=0.11>0.1；且规则的置信度confidence(“啤酒”⇒“尿布”)=0.5>0.4。依据上述概念，可以将关联规则的挖掘设计为一个两步过程：（1）发现所有的频繁项集——包含这些项集的事务出现的频度不应低于预先给定的最小支持度min-sup。（2）从获得的频繁项集产生相应的强关联规则——这些规则必须满足最小支持度min-sup和最小置信度min-conf。6.7.3关联规则挖掘

2面向关联规则挖掘的经典算法AprioriApriori算法——一种最有影响力的挖掘关联规则频繁项集的算法使用称为逐层搜索的迭代方法去逐层产生频繁项集：从频繁k-项集搜索频繁(k+1)-项集。首先，从事务库搜索所有频繁1-项集，并将它们收集于L1；再从事务库搜索所有频繁2-项集并建立L2，如此迭代下去，直到对于某个k，搜索不到频繁k-项集为止。Apriori性质：频繁项集的非空子集必定也是频繁的大幅度提高了逐层产生频繁项集的效率；该性质的成立是显然的。令包含频繁项集H的事务集为D1，则min-sup≤support(H)=|D1|/|D|；显然，包含H的事务必定包含H的任意非空子集H’；令包含H’的事务集为D2，则必有|D1|≤|D2|，进而有min-sup≤support(H)≤support(H’)。表示为规范的蕴涵式：项集H是频繁的⇒H的子集H’是频繁的。6.7.3关联规则挖掘

2面向关联规则挖掘的经典算法Apriori逆反蕴涵式：H的子集H’是不频繁的⇒项集H是不频繁的可断言：非频繁项集的超集必定也是非频繁的。正是这个推论构成Apriori算法的基础。设计Apriori算法的核心是如何从频繁k-项集的集合Lk获得Lk+1，其由2个处理步骤构成：连接、修剪。连接——为建立Lk+1，可以先通过连接Lk中的2个k-项集来生成(k+1)-项集的集合Ck+1，然后再将其修剪成Lk+1。显然，只有单一项不同（其余项都相同）的k-项集才可用于生成(k+1)-项集。为方便作连接处理，令项集中的项按字典序排序，则2个k-项集l1和l2是可连接的，仅当它们的前(k-1)个项相同，即l1(1)=l2(1)∧l1(2)=

l2(2)∧…∧l1(k-1)=

l2(k-1)∧l1(k)<

l2(k)。这里条件l1(k)<l2(k)用于确保不会生成重复的(k+1)-项集。6.7.3关联规则挖掘

2面向关联规则挖掘的经典算法Apriori修剪——删除Ck+1中包含的所有非频繁(k+1)-项集，得到Lk+1因为通过连接步骤生成的(k+1)-项集可能是非频繁的，即Ck+1是Lk+1的超集。可以直接按照频繁项集的定义来甄别非频繁(k+1)-项集，这就需要计算每个(k+1)-项集的支持度，但Ck+1往往比Lk+1大得多，这时计算量太大。其实，完全可以依据上述Apriori性质的推论：非频繁项集的超集必定也是非频繁的，来甄别出大部分非频繁(k+1)-项集；即只要检查Ck+1中的每个(k+1)-项集是否包含非频繁k-项集。若包含，则该(k+1)-项集必定是非频繁的，就可从Ck+1中修剪掉。修剪完成后，Ck+1只包含少得多的(k+1)-项集作为候选项集，从而大幅度压缩了通过最小支持度能否满足来甄别频繁(k+1)-项集的工作量。Apriori算法的细节和示例略6.7.3关联规则挖掘

3关联规则的生成

建立由所有强关联规则构成的集合R：从Apriori算法返回的包含所有频繁项集的集合L，枚举出支持度满足min-sup（强关联规则应满足的最小支持度）的关联规则r；再修剪掉置信度不满足min-conf（强关联规则应满足的最小置信度）的关联规则。对于每个k>1的频繁k-项集W，都可枚举出2—多条形如“X⇒Y”的关联规则。鉴于X⋃Y（=W）和X（⊂W）都是频繁项集，已经在执行Apriori算法的过程中存储了它们的支持度，可直接用于计算规则的置信度： confidence(X⇒Y) =support(X⋃Y)/support(X) =support(W)/support(X)例：从包含于L的频繁3-项集：{A,B,E}，建立所有关联规则（略）6.7.3关联规则挖掘

4提高Apriori算法的有效性

尽管Apriori算法通过连接-修剪方法大幅度压缩了甄别频繁项集的工作量，但对于大型事务数据库，多遍扫描（对于k的每个取值，只要修剪后的Ck+1非空，就须扫描一遍）仍然计算开销很大。书上介绍了3种改进技术（略）散列项集计数事务数据库划分事务数据库采样6.7.3关联规则挖掘

5不依赖候选项集的频繁项集挖掘方法Apriori算法需要通过扫描事务数据库D来甄别候选项集，使得候选项集较大时计算开销很大。称为FP-增长（Frequent-PatternGrowth）的方法能在不产生候选项集的情况下挖掘全部频繁项集，可以大幅度降低搜索开销。该方法采用如下分治策略：将D包含的关于频繁项集的信息浓缩到一颗FP-树（频繁模式树），并保持信息对于频繁项集挖掘的完备性；然后分别对树的不同部分进行搜索，就可挖掘出所有频繁项集，而不需产生候选项集。6.7.3关联规则挖掘

5不依赖候选项集的频繁项集挖掘方法FP-增长方法分2个阶段来完成频繁项集的挖掘任务：阶段1：构建FP-树（1）扫描D，获取频繁1-项集；（2）将频繁1-项集按支持度从大到小排列，并记排序后的列表为S；（3）再次扫描D，构建FP-树。阶段2：挖掘FP-树（1）搜索FP-树中对应于叶子节点的每个项的条件模式集；（2）从每个条件模式集构建条件FP-树；（3）从每颗条件FP-树递归地挖掘频繁模式（即频繁项集）。第2阶段结束时，就可挖掘到所有可能的频繁项集。书上通过一个示例来说明FP-增长方法的应用细节。（略）6.7.3关联规则挖掘

6关联规则挖掘研究的发展

鉴于关联规则的挖掘具有广泛的实用背景，相关的研究工作不断地深化，主要体现在以下3个方面（略）关联规则的挖掘从单一概念层次扩展到多概念层次关联规则的挖掘从单维发展到多维从关联挖掘发展到相关分析6.7.4数据库及网络中的知识发现

1数据库中的知识发现

KDD——KnowledgeDiscoveryinDatabase：融数据库技术、人工智能技术、数理统计技术和可视化技术为一体，是一个多学科相互交叉融合所形成的一个新兴的具有广泛应用前景的研究领域。研究围绕理论、技术和应用3个方面展开。KDD发现的知识模式(从用户的角度看)：依赖关系，分类知识，描述性知识，偏差型知识。KDD的处理过程：多步骤，（循环和反复）；主要处理步骤：准备，确定KDD的目标，数据收集和选择，数据预处理，确定知识发现方法，发现知识，知识解释和评价。KDD系统的结构，参见图6.26。2面向因特网的数据挖掘

比面向单个数据仓库的数据挖掘要复杂得多因特网上数据的最大特点是半结构化的——传统数据库中的数据是结构化的；从不同网站集成异构的数据源；因特网上的数据构成复杂，没有特定的描述模型可用；基于HTML（超文本标记语言）的网页面向人浏览，机器不可读（不支持计算机自动处理）。基于XML（可扩展标记语言）的语义Web：对文档（数据）包含的语义作清晰的结构化描述，机器可读，支持对于文档内容的精确查询，大幅度促进因特网上的数据挖掘。面向因特网的数据挖掘是一种前瞻性的研发工作，应用前景十分广阔，有重要的理论意义和实用价值。人工智能基础浙江大学计算机学院高济4实现启发式搜索的关键因素

鉴于启发式搜索在提高搜索效率和解决组合爆炸问题中的作用，相关的研究成为人工智能形成和成长期的重要议题之一，也产生了许多成熟的研究成果，并且至今启发式搜索仍是一个活跃的研究领域。

1）搜索算法的可采纳性(Admissibility)

定义：在搜索图存在从初始状态节点到目标状态节点解答路径的情况下，若一个搜索算法总能找到最短（代价最小）的解答路径，则称算法具有可采纳性。宽度优先的搜索算法就是可采纳的，只是其搜索效率不高。评价函数f*(n)=g*(n)+h*(n)

f*(n)——当经由节点n的最短（代价最小）解答路径找到时实际的路经代价（长度）。g*(n)——该路径前段（自初始状态节点到节点n）代价。h*(n)——该路径后段（自节点n到目标状态节点）代价。在存在多个目标状态的情况下，h*(n)取h*(n，ngi)中最小者。

评价函数f与f*相比较——f(n)、g(n)和h(n)分别是f*(n)、g*(n)和h*(n)的近似值。1）搜索算法的可采纳性(Admissibility)

理想的情况：g(n)=g*(n),h(n)=h*(n),搜索过程中,每次都正确选择，不扩展任何无关的节点。

g*(n)和h*(n)在最短解答路径找到前是未知的，故而几乎不可能设计出这种理想的评价函数；而且对于复杂的应用领域，即便是要设计接近于f*的f往往也是困难的。一般来讲，g(n)的值容易从迄今已生成的搜索树中计算出来，不必专门定义计算公式。例如就以节点深度d(n)作为g(n),并有g(n)≥g*(n)。然而，h(n)的设计依赖于启发式知识的应用。

如何挖掘贴切的启发式知识是设计评价函数乃至算法A的关键。w(n)——不够贴切，错误选用节点d加以扩展。p(n)——更接近于h*(n)的h(n)，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步的总和。p(n)比w(n)更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离（移动次数）。

应用启发式函数p(n)(而非w(n))的八数码问题搜索图：参见图2.10。算法A的可采纳性——确保h(n)≤h*(n)的情况下，A可采纳，称为A*。宽度优先算法——h(n)≡0＜h*(n)，确保搜索到最短路径。八数码游戏采用w(n)和p(n)作为启发式函数时，算法A都是可采纳的。

4实现启发式搜索的关键因素2）启发式函数的强弱及其影响h(n)接近h*(n)的程度——衡量启发式函数的强弱。h(n)＜h*(n)，差距较大时，h(n)过弱，OPEN表中节点排序的误差较大，产生较大的搜索图；h(n)>h*(n),h(n)过强，算法A失去可纳性，不能确保找到最短解答路径。恒等于h*(n)的h(n)最理想，但无法设计。设计接近、又总是≤h*(n)的h(n)——应用A*算法搜索问题解答的关键。算法A1和A2，若总有h1(n)≤h2(n)≤h*(n)，则t(A2)≤t(A1)。w(n)≤p(n)≤h*(n),采用p(n)扩展出的节点总数≤t(w(n))。宽度优先法解决八数码问题，h(n)≡0，搜索树庞大得多。

3）设计h(n)的实用考虑设计接近、又总是≤h*(n)的h(n)的问题：随着问题求解任务复杂程度的增加,设计变得更困难，往往会导致在h(n)上的繁重计算工作量。搜索代价高居不下——路径选择代价随h(n)的计算开销而大增。3）设计h(n)的实用考虑删除h(n)≤h*(n)的约束，使h(n)易于设计，但丢失可采纳性：在许多实用场合，人们并不要求找到最优解答（最短解答路径）；通过牺牲可纳性来换取h(n)设计的简化和减少计算h(n)的工作量。对评价函数f(n)=g(n)+h(n)作分析：h(n)≡0——倾向于先进入OPEN表的节点会优先被考察和扩展，先进入的节点n往往具有较小的g(n)值，接近于宽度优先的搜索策略；g(n)≡0,——倾向于后进入OPEN表的节点会优先被考察和扩展，后进入的节点n往往更接近于目标状态，即h(n)值较小，接近于深度优先的搜索策略。评价函数f(n)=g(n)+wh(n)，w用作加权：搜索图的浅层（上部）——让w取较大值，使g(n)所占比例很小，突出启发式函数的作用，加速向纵深方向搜索；搜索到较深的层次——让w取较小值，以使g(n)所占比例很大，并确保wh(n)≤h*(n),搜索向横广方向发展，寻找到较短的解答路径。

5回溯策略和爬山法

简单的搜索策略：g(n)≡0,f(n)=h(n),局部排序——只排序新扩展出来的子节点；简单易行，适用于不要求最优解答的问题求解任务。

1）爬山法——实现启发式搜索的最简单方法。类似于人爬山——只要好爬，总是选取最陡处，以求快速登顶。求函数极大值问题——非数值解法，依赖于启发式知识，试探性地逐步向顶峰逼近。适用于能逐步求精的问题。爬山法特点：只能向上，不准后退，从而简化了搜索算法；体现在：从当前状态节点扩展出的子节点中，将h(n)最小的子节点（对应于到顶峰最近的上爬路径）作为下一次考察和扩展的节点，其余子节点全部丢弃。不需设置OPEN和CLOSE表，因为没有必要保存任何待扩展节点；爬山法对于单一极值问题（登单一山峰）十分有效而又简便，对于具有多极值的问题无能为力——会错登上次高峰：不能到达最高峰。

5回溯策略和爬山法2）回溯策略可以有效地克服爬山法面临的困难——保存了每次扩展出的子节点，并按h(n)值从小到大排列。相当于爬山的过程中记住了途经的岔路口——路径搜索失败时回溯（后退），向另一路径方向搜索（参看图2.11）。递归过程——实现回溯策略的有效方式：算法就取名为BACKTRACK(n),参数n为当前被扩展的节点，初次调用时n即为初始状态节点s；分二个部分：*判断当前节点n的状态，*作搜索工作——扩展节点n，递归调用该算法，处理返回结果。三种失败状态：不合法状态（如传教士和野人问题中所述的那样），旧状态重现（如八数码游戏中某一棋盘布局的重现，会导致搜索算法死循环），状态节点深度超过预定限度（例如八数码游戏中，指示解答路径不超过6步）。

2）回溯策略回溯条件搜索进入“死胡同”，由该算法的第(4)句定义。

失败状态，由算法第（2）句指示，第（7）句执行回溯。解答路径的生成——从相应于目标状态节点的空表开始，递归返回PATH。

2）回溯策略影响回溯算法效率的关键因素——回溯次数：回溯——搜索到失败状态时的一种弥补行为，准确选择下一步搜索考察的节点——大幅度减少甚至避免回溯。设计好的启发式函数h(n)是至关重要的。四皇后问题例：国际象棋棋盘的一个4×4区域放置四个皇后棋子，并满足约束：每行、每列和对角线上只允许出现一个皇后，以避免皇后间发生冲突。问题状态——用列表L指示，L的元素就是皇后在棋盘中的位置ij(1≤i，j≤4).为简化解答的搜索，限定按自上而下的次序在棋盘的4行中放置皇后。空表L指示初始状态；当表L包含4个满足约束的皇后位置时，到达目标状态；当皇后位置发生冲突时，意味着进入不合法状态（失败状态）。设计D(n)作为启发式函数h(n)——其值为状态n下最新一个皇后位