人工智能基础06--专家系统.ppt

1、目录,第一章绪论 第二章知识表示 第三章搜索技术 第四章推理技术 第五章机器学习 第六章专家系统 第七章自动规划系统 第八章 自然语言理解 第九章 智能控制 第十章 人工智能程序设计,6.1 专家系统概述,定义：专家系统是一个智能计算机程序系统，其内部含有大量的某个领域专家水平的知识与经验，能够利用人类专家的知识和解决问题的方法来处理该领域问题。 6.1.1 专家系统的一般特点 1. 专家系统特点 启发性：专家系统能运用专家的知识与经验进行推理、判断和决策。 透明性：专家系统能够解释本身的推理过程和回答用户提出的问题，以便让用户能够了解推理过程，提高对专家系统的信赖感。 灵活性：专家系统能不断

2、地增长知识，修改原有知识，不断更新。,6.1 专家系统概述,2. 专家系统优点 （1）能够高效率、准确、周到、迅速和不知疲倦地进行工作。 （2）解决实际问题时不受周围环境的影响，也不可能遗漏忘记。 （3）能够不受时间和空间的限制，保存、推广珍贵和稀缺的专家知识与经验。 （4）能促进各领域的发展，它使各领域专家的知识和经验得到总结和精炼。 （5）能汇集多领域专家的知识和经验以及他们协作解决重大问题的能力。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 1. 专家系统的简化结构 结构：专家系统各组成部分的构造方法和组织形式。 系统结构选择恰当与否，是与专家系统的适用性和有效性密切相关的。

3、选择什么结构最为恰当，要根据系统的应用环境和所执行任务的特点而定。,知识库,推理机,专家知识,输出或提问,答案,6.1 专家系统概述,6.1.2 专家系统的结构和类型 2. 理想专家系统的结构,知识库,事实 规则,用户,知识库,计划,解释器,议程,中间解,黑板,执行器,调度器,协调器,推理机,6.1 专家系统概述,6.1.2 专家系统的结构和类型 2. 理想专家系统的结构 接口是人与系统进行信息交流的媒介，它为用户提供了直观方便的交互作用手段。 黑板是用来记录系统推理过程中用到的控制信息、中间假设和中间结果的数据库。它包括计划、议程和中间解3部分。 计划：纪录当前问题总的处理计划、目标、问题的

4、当前状态和问题背景。 议程：纪录了一些待执行的动作，由黑板中已有结果与知识库中的罪责作用而得到。 中间解：存放当前系统已产生的结果和候选假设。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 知识库包括两部分：一部分是已知的同当前问题有关的数据信息；另一部分是进行推理时要用到的一般知识和领域知识。 调度器按照系统建造者所给的控制知识，从议程中选择一个项作为系统下一步要执行的动作。 执行器应用知识库中的及黑板中记录的信息，执行调度器所选定的动作。 协调器的主要作用就是当得到新数据或新假设时，对已得到的结果进行修正，以保持结果前后的一致性。 解释器的功能是向用户解释系统的行为，包括解释结论

5、的正确性及系统输出其它候选解的原因。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 一般应用程序与专家系统的区别 前者把问题求解的知识隐含地编入程序，而后者则把其应用领域的问题求解知识单独组成一个实体，即为知识库。知识库的处理是通过与知识库分开的控制策略进行的。 更明确地说，一般应用程序把知识组织为两级：数据级和程序级；大多数专家系统则将知识组织成三级；数据、知识库和控制。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 3.专家系统的类型 （1）解释专家系统 任务 通过对过去和现在已知状况的分析，推断未来可能发生的情况。 特点 数据量很大，常不准确、有错误、不完全能从不完全

6、的信息中得出解释，并能对数据做出某些假设，推理过程可能很复杂和很长。 例子 语音理解、图象分析、系统监视、化学结构分析和信号解释等。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （2）预测专家系统 任务 通过对已知信息和数据的分析与解释，确定它们的涵义。 特点 系统处理的数据随时间变化，且可能是不准确和不完全，系统需要有适应时间变化的动态模型。 例子 有气象预报、军事预测、人口预测、交通预测、经济预测和谷物产量预测等,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （3）诊断专家系统 任务 根据观察到的情况(数据)来推断出某个对象机能失常(即故障)的原因。 特点 能够了解被

7、诊断对象或客体各组成部分的特性以及它们之间的联系，能够区分一种现象及其所掩盖的另一种现象，能够向用户提出测量的数据，并从不确切信息中得出尽可能正确的诊断。 例子 医疗诊断、电子机械和软件故障诊断以及材料失效诊断等。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （4）设计专家系统 任务 寻找出某个能够达到给定目标的动作序列或步骤。 特点 从多种约束中得到符合要求的设计；系统需要检索较大的可能解空间；能试验性地构造出可能设计；易于修改；能够使用已有设计来解释当前新的设计。 例子 VAX计算机结构设计专家系统等。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （5）规划专家系统

8、 任务 寻找出某个能够达到给定目标的动作序列或步骤。 特点 所要规划的目标可能是动态的或静态的，需要对未来动作做出预测，所涉及的问题可能很复杂 。 例子 军事指挥调度系统、ROPES机器人规划专家系统、汽车和火车运行调度专家系统等。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （6）监视专家系统 任务 对系统、对象或过程的行为进行不断观察，并把观察到的行为与其应当具有的行为进行比较，以发现异常情况，发出警报。 特点 系统具有快速反应能力，发出的警报要有很高的准确性，能够动态地处理其输入信息。 例子 粘虫测报专家系统。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （7）控

9、制专家系统 任务 自适应地管理一个受控对象或客体的全面行为，使之满足预期要求。 特点 控制专家系统具有解释、预报、诊断、规划和执行等多种功能。 例子 空中交通管制、商业管理、自主机器人控制、作战管理、生产过程控制和质量控制等。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （8）调试专家系统 任务 对失灵的对象给出处理意见和方法。 特点 同时具有规划、设计、预报和诊断等专家系统的功能。 例子 在这方面的实例还比较少见。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （9）教学专家系统 任务 教学专家系统的任务是根据学生的特点、弱点和基础知识，以最适当的教案和教学方法对学生进

10、行教学和辅导。 特点 同时具有诊断和调试等功能；具有良好的人机界面。 例子 MACSYMA符号积分与定理证明系统，计算机程序设计语言和物理智能计算机辅助教学系统以及聋哑人语言训练专家系统等。,6.1 专家系统概述,6.1.2 专家系统的结构和类型 （10）修理专家系统 任务 对发生故障的对象(系统或设备)进行处理，使其恢复正常工作。 特点 修理专家系统具有诊断、调试、计划和执行等功能。 例子 美国贝尔实验室的ACI电话和有线电视维护修理系统。 此外，还有决策专家系统和咨询专家系统等。,6.1 专家系统概述,6.1.3 专家系统的建造步骤 1. 设计初始知识库，包括： （1）问题知识化，即辨别所

11、研究问题的实质，如要解决的任务是什么，它是如何定义的，可否把它分解为子问题或子任务，它包含哪些典型数据等。 （2）知识概念化，即概括知识表示所需要的关键概念及其关系，如数据类型、已知条件(状态)和目标(状态)、提出的假设以及控制策略等。 （3） 概念形式化，即确定用来组织知识的数据结构形式，应用人工智能中各种知识表示方法把与概念化过程有关的关键概念、子问题及信息流特性等变换为比较正式的表达，它包括假设空间、过程模型和数据特性等。,6.1 专家系统概述,6.1.3 专家系统的建造步骤 （4）形式规则化，即编制规则、把形式化了的知识变换为由编程语言表示的可供计算机执行的语句和程序。 （5）规则合法

12、化，即确认规则化了知识的合理性，检验规则的有效性。 2. 原型机的开发与试验 在选定知识表达方法之后，即可着手建立整个系统所需要的实验子集，它包括整个模型的典型知识，而且只涉及与试验有关的足够简单的任务和推理过程。,6.1 专家系统概述,6.1.3 专家系统的建造步骤 3. 知识库的改进与归纳 反复对知识库及推理规则进行改进试验，归纳出更完善的结果。经过相当长时间(例如数月至二、三年)的努力，使系统在一定范围内达到人类专家的水平。,知识化,知识,问题,概念化,概念,形式化,结构,规则化,规则,合法化,改进,形式,再设计,重新阐述,6.2 基于规则的专家系统,6.2.1 基于规则的专家系统的基本

13、结构 知识库：谓词演算事实 有关主题的规则 推理机：消解 前向推理 反向推理 接口：自然语言接口 图形接口 知识工程师：知识表示 领域专家：提供知识,知识采集 子系统,启发式 知识库,用户接口,推理机,解释 子系统,知识规划,专家,用户,6.2 基于规则的专家系统,6.2.2 基于规则的专家系统的特点 1. 优点 （1）自然表达：IF-THEN语句 （2）控制与知识分离：知识库与推理机控制分离 （3）知识模块性：规则是独立的知识块 （4）易于扩展：添加知识和规则 （5）智能成比例增长：智能级别随规则增多而提高 （6）相关知识的使用：使用与问题相关的规则 （7）从严格的语法获取解释：跟踪所用的规

14、则 （8）一致性检查：规则的一致性,6.2 基于规则的专家系统,6.2.2 基于规则的专家系统的特点 （9）启发式知识的使用：使用启发式信息 （10）不确定知识使用：规则的不确定性 （11）可以使用变量：使用变量改进效率 2. 缺点 （1）必须精确匹配：规则前项与事实严格匹配 （2）有不清楚的规则关系：通过推理链难以判定规则逻辑关系 （3）具有大量规则的专家系统可能较慢：扫描整个规则库 （4）对一些问题不适用：规则对领域知识的自然表示,6.2 基于规则的专家系统,6.2.3 基于规则的专家系统举例 EMYCIN系统 逆向推理的深度优先控制策略 基本规则形式 IFTHENELSE 用-1+1之间

15、的数表示规则致信度,6.3 基于框架的专家系统,基于框架的专家系统建立在框架的基础之上 ，采用框架而不是采用规则来表示知识 ，基于框架的专家系统是个计算机程序，该程序使用一组包含在知识库内的框架对工作存储器内的具体问题信息进行处理，通过推理机推断出新的信息。 特征：匹配和继承,推理机理,框架系统（知识）库,向特定框架发送消息并启动特定的附加过程,依返回值，评价决定下一步的附加过程,6.4 基于模型的专家系统,基于模型的推理：根据反映事物内部规律的客观世界的模型进行推理。 模型的种类： 结构模型表示系统各部件部分-整体关系 几何模型表示各部件几何关系 功能模型表示各部件功能和性能 因果模型表示各

16、部件因果关系 浅层推理：运用启发式规则推理 深层推理：基于模型的推理,6.5 专家系统的设计、评价与开发,6.5.1 专家系统的设计 尽早建立专家系统原型 设计准则： （1）集中精力研究一小部分假设，选取确实可信的观察和肯定的规则。 （2） 选择最有利于区别各个假设的观测。 （3）在确定规则时，首先从确认或区分各种假设所需要的数量最小的观测组合开始。 （4）组合不具有很强预测或区别能力的观测，以便通过观测或结论之间的依赖关系来改善这些观测的区别能力。,6.5 专家系统的设计、评价与开发,6.5.1 专家系统的设计 （5）建立中间假设，以减少规则数量和简化推理过程。 （6） 以各种事例来试验所设

17、计的系统。 从问题的一般特征出发来考虑建立模型的方法 （1）具有可靠知识与数据的小搜索空间问题 使系统具有单调性并采用单路推理路线。 （2）不可靠的数据或知识 采用概率推理、模糊推理等不确定性推理技术。,6.5 专家系统的设计、评价与开发,6.5.1 专家系统的设计 （3）时变数据 涉及时间推理技术。 （4） 大搜索空间的问题 启发式搜索策略、分层体系结构。,6.5 专家系统的设计、评价与开发,6.5.2 专家系统的评价 1. 评价专家系统的意义 设计和建立一个专家系统就是对系统不断评价的过程 （1）所用的知识表达方法是否合适，它是否需要扩展或修改？ （2）这个系统能否提供正确的答案和进行正确

18、的推理？ （3）存入系统的知识是否和专家的知识一致？ （4）使用者和系统相互联系是否方便？ （5）使用者需要系统提供什么方便和要求系统具有什么能力？,6.5 专家系统的设计、评价与开发,6.5.2 专家系统的评价 2. 评价专家系统的方法 两种方法： （1）轶事的方法。简单地启发地利用一组例子说明系统的性能。 （2）试验的方法。用有代表性的事例评价系统在处理各种存储在数据库中的问题事例的性能。困难：分析必须有确定的结束点。,6.5 专家系统的设计、评价与开发,6.5.2 专家系统的评价 3. 评价专家系统的内容 专家系统完成时的评价： （1）系统所做的决定和建议的质量 重点评价系统完成决策任务

19、时的程序性能。 （2）所用推理技术的正确性 重视专家解决问题的推理机理。 （3）人机对话的质量 在提问和由程序来产生解答时用词的选择。,6.5 专家系统的设计、评价与开发,6.5.2 专家系统的评价 解释系统如何做出决策的基本能力以及使系统的解释适合于使用者专门知识水平的能力。 需要帮助时，系统对使用者提供帮助的能力 以易于理解的方式或使用者熟悉的术语提出建议或向使用者进行解释。 （4）效率 （5）成本效果（或工程经济分析）,6.5 专家系统的设计、评价与开发,6.5.3 专家系统开发工具 1. 骨架型开发工具 专家系统一般都有推理机和知识库两部分，而规则集存于知识库内。在一个理想的专家系统中

20、，推理机完全独立于求解问题领域。系统功能上的完善或改变，只依赖于规则集的完善和改变。由此，借用以前开发好的专家系统，将描述领域知识的规则从原系统中“挖掉”，只保留其独立于问题领域知识的推理机部分，这样形成的工具称为骨架型工具。这类工具因其控制策略是预先给定的，使用起来很方便，用户只须将具体领域的知识明确地表示成为一些规则就可以了。,6.5 专家系统的设计、评价与开发,6.5.3 专家系统开发工具 因其程序的主要骨架是固定的，除了规则以外，用户不可改变任何东西，因而骨架型工具存在一些有待解决的问题，影响它的广泛应用。 （1）原有骨架可能不适合于所求解的问题 （2）推理机中的控制结构可能不符合专家

21、新的求解问题方法。 （3）原有规则语言可能不能完全表示所求解领域的知识。 （4）求解问题的专门领域知识可能隐藏在原有系统中。,6.5 专家系统的设计、评价与开发,6.5.3 专家系统开发工具 2. 语言型开发工具 语言型工具提供给用户的是建立专家系统所需要的基本机制，其控制策略也不固定于一种或几种形式，用户可以通过一定手段来影响其控制策略。因此，语言型工具的结构变化范围广泛，表示灵活，所适应的范围要比骨架型工具广泛得多。 典型例子： OPS5，以产生式系统为基础，综合了通用控制和表示机制，向用户提供建立专家系统所需要的基本功能。,6.5 专家系统的设计、评价与开发,6.5.3 专家系统开发工具

22、 3. 构造辅助工具 系统构造辅助工具由一些程序模块组成，有些程序能帮助获得和表达领域专家的知识，有些程序能帮助设计正在构造的专家系统的结构。它主要分两类，一种是设计辅助工具，另一种是知识获取辅助工具。 AGE：斯坦福大学用INTERLISP语言实现的专家系统工具，帮助知识工程师设计和构造专家系统。 TEIRESIAS：典型知识获取工具，用元知识来进行知识获取和管理，帮助知识工程师把一个领域专家的知识植入知识库。,6.5 专家系统的设计、评价与开发,6.5.3 专家系统开发工具 4. 支撑环境 支撑设施是指帮助进行程序设计的工具，它常被作为知识工程语言的一部分。工具支撑环境仅是一个附带的软件包

23、，以便使用户界面更友好。它包括四个典型组件：调试辅助工具、输入输出设施、解释设施和知识库编辑器。 ART：第二代专家工具系统。将基于规则的程序设计、符号数据的多种标识、基本对象的程序设计、逻辑程序设计及黑板模型有效结合在一起。,6.6 专家系统设计举例,汽车维修专家系统 专家知识的描述 知识的使用 决策的解释 MYCIN系统概述,6.7 新型专家系统,1. 并行与分布处理 基于各种并行算法，采用各种并行推理和执行技术，适合在多处理器的硬件环境中工作，即具有分布处理的功能。 2. 多专家系统协同工作 在这种系统中，有多个专家系统协同合作。 3. 高级语言和知识语言描述 专家系统生成系统就能自动或

24、半自动地生成所要的专家系统。 4. 具有自学习功能 新型专家系统应提供高级的知识获取与学习功能。,6.7 新型专家系统,5、引入新的推理机制 在新型专家系统中，除演绎推理之外，还应有归纳推理，各种非标准逻辑推理，以及各种基于不完全知识和模糊知识的推理等等。 6. 具有自纠错和自完善能力 为了排错必须首先有识别错误的能力，为了完善必须首先有鉴别优劣的标准。 7. 先进的智能人机接口 理解自然语言，实现语声、文字、图形和图象的直接输入输出是如今人们对智能计算机提出的要求。,6.8 知识发现,数据库知识发现（Knowledge Discovery in Databases， KDD） 数据挖掘(Da

25、ta Mining DM) 数据分析（Data Analysis） 数据融合(Data Fusion) 决策支持（Decision Supporting）,6.8 知识发现,6.8.1 知识发现的发展和定义 1. 知识发现的产生和发展,苦恼: 淹没在数据中 ; 不能制定合适的决策!,数据,知识,决策,数据爆炸，知识贫乏,6.8 知识发现,1989 IJCAI会议： 数据库中的知识发现讨论专题 Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991) 1991-1994 KDD讨论专题 Advance

26、s in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996) 1995-1998 KDD国际会议 (KDD95-98) Journal of Data Mining and Knowledge Discovery (1997) 1998 ACM SIGKDD, SIGKDD1999-2002 会议,以及SIGKDD Explorations 数据挖掘方面更多的国际会议 PAKDD, PKDD, SIAM-Data Mining, (IEE

27、E) ICDM, DaWaK, SPIE-DM, etc.,6.8 知识发现,6.8.1 知识发现的发展和定义 2. 知识发现的定义 Fayyad, Piatetsky-Shapiro和Smyth在KDD96国际会议的会议论文From Data Mining to Knowledge Discovery一文中将KDD定义为： “The nontrivial process of identifying valid，novel，potentially useful，and ultimately understandable patterns in data.” KDD指大量数据中获取有效的、新颖

28、的、有潜在作用的和最终可理解的模式的非平凡过程。,6.8 知识发现,6.8.1 知识发现的发展和定义 （1）数据集：是指一个有关事实F的集合，它是用来描述事物有关方面的信息，是进一步发现知识的原材料。数据可以是一个或一组数据库、数据仓库、电子表格或其他类型的信息库，在数据上往往需要进行数据清理、集成和规约等预处理。 （2）新颖：经过知识发现提取出的模式必须是新颖的，至少对系统来说应该如此。模式是否新颖可以通过两个途径来衡量：其一是在所得到的数据方面，通过对比当前得到的数据和以前的数据或期望得到的数据之间的比较，来判断该模式的新颖程度；其二是在其内部所包含的知识方面，通过对比，发现的模式与已有的

29、模式的关系来进行判断。,6.8 知识发现,6.8.1 知识发现的发展和定义 （3）潜在有用：提取出的模式应该是有意义的，有潜在的应用价值。这可以通过某些函数的值来衡量。 （4）可理解：知识发现的一个目标就是将数据库中隐含的模式以容易被人理解的形式表现出来，从而帮助人们更好地了解数据库中所包含的信息。 （5）模式：模式是指用语言来表示的一个表达式，它可用来描述数据集的特性，根据某种兴趣度度量，并于数据挖掘模块中进行交互挖掘，以便识别和表示知识的真正有趣的模式。,6.8 知识发现,6.8.1 知识发现的发展和定义 （6）过程：过程是在KDD中包含的步骤，如数据的预处理、模式搜索、知识表示及知识评估

30、、过程优化等。 （7）非平凡：是对数据进行更深层处理的过程，已经超越了一般封闭形式的数量计算，包括对结构、模式和参数的搜索。 （8）有效性：通过KDD从当前数据所发现的模式必须有一定的正确程度，否则KDD就毫无作用。,6.8 知识发现,6.8.2 知识发现的处理过程,6.8 知识发现,6.8.2 知识发现的处理过程 （1）数据选择。根据用户的需求从数据库中提取与KDD相关的数据。 （2）数据预处理。主要是对上述数据进行再加工，检查数据的完整性及数据的一致性，对丢失的数据利用统计方法进行填补，形成发掘数据库。 （3）数据转换。从发掘数据库里选择数据，即根据知识发现的任务对数据进行再处理，主要通过

31、投影或数据库中的其他操作减少数据量。,6.8 知识发现,6.8.2 知识发现的处理过程 （4）数据挖掘： 确定KDD目标： 根据用户要求，确定KDD发现的知识类型，因为对KDD的不同要求，会在具体的知识发现过程中采用不同的知识发现算法。 确定知识发现算法： 根据阶段5所确定的任务，选择合适的数据挖掘算法，包括选取合适的模型和参数，并使得挖掘算法与整个KDD的评判标准相一致。 数据挖掘： 运用选定的挖掘算法，搜索或产生一个特定的感兴趣的模式或数据集，从数据中提取出用户所需要的知识，这些知识可以用某种特定的方式表示或使用一些常用的表示方式，如产生式规则等。,6.8 知识发现,6.8.2 知识发现的

32、处理过程 （5）模式解释： 对发现的模式进行解释，去掉多余的不切题意的模式，转换成某个有用的模式，以使用户理解。在此过程中，为了取得更为有效的知识，可能会返回前面处理中的某些步骤，以便反复提取，从而提取出更有效的知识。 （6）知识评价：这一过程主要用于对所获得的规则进行价值评定，以决定所得的规则是否存入基础知识库。 上述KDD全过程的几个步骤可以进一步归纳为三个步骤，即数据挖掘预处理（数据挖掘前的准备工作）、数据挖掘、数据挖掘后处理（数据挖掘后的处理工作）。,6.8 知识发现,6.8.3 数据挖掘概述 1. 定义 数据挖掘（Date Mining）是从大型数据库或数据仓库中提取人们感兴趣的知识

33、，这些知识是隐含的、事先未知的、潜在的、有用的信息。 广泛观点的定义：是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣的知识过程。 与KDD关系： 观点1：数据挖掘与KDD是同义词。 观点2：数据挖掘是KDD一个基本步骤。 观点3：数据挖据是一个相对独立的领域，如Web挖掘。,6.8 知识发现,6.8.3 数据挖掘概述 2. 数据挖掘的对象 根据信息存储格式，用于挖掘的对象有：关系数据库、面向对象数据库、空间数据库、时序数据库、文本数据源、多媒体数据、异质数据库、遗产数据库，以及Web数据源。,6.8 知识发现,6.8.3 数据挖掘概述 3. 数据挖掘软件 典型数据挖掘系统有：SA

34、S 公司的Enterprise Miner、IBM 公司的Intelligent Miner、SGI 公司的SetMiner、SPSS 公司的Clementine、Sybase公司的Warehouse Studio、RuleQuest Research 公司的See5 、还有CoverStory、EXPLORA、Knowledge Discovery Workbench、DBMiner、Quest、Microsoft SQL Server 2005等。,6.8 知识发现,6.8.3 数据挖掘概述,6.8 知识发现,6.8.3 数据挖掘概述 第一代数据挖掘软件 特点 支持一个或少数几个数据挖掘算

35、法 挖掘向量数据（vector-valued data） 数据一般一次性调进内存进行处理 典型的系统如Salford Systems公司早期的CART系统 缺陷 如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。,6.8 知识发现,6.8.3 数据挖掘概述 第二代数据挖掘软件 特点 与数据库管理系统（DBMS）集成 支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性 能够挖掘大数据集、以及更复杂的数据集 通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言增加系统的灵活性 典型的系统如DBMiner，能

36、通过DMQL挖掘语言进行挖掘操作 缺陷 只注重模型的生成，如何和预言模型系统集成导致了第三代数据挖掘系统的开发,6.8 知识发现,6.8.3 数据挖掘概述 第三代数据挖掘软件 特点 和预言模型系统之间能够无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中 由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能 能够挖掘网络环境下（Internet/Extranet）的分布式和高度异质的数据，并且能够有效地和操作型系统集成 缺陷 不能支持移动环境,6.8 知识发现,6.8.3 数据挖掘概述 第四代数据挖掘软件 特点 目

37、前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个研究领域。 第四代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据,6.8 知识发现,6.8.4 知识发现（数据挖掘）的方法 知识发现的方法有统计方法、机器学习、神经计算和可视化方法等。 1. 统计方法 统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。 （1）传统方法 渐近理论：当样本趋于无穷多时的统计性质 三个阶段：搜集数据、分析数据、推理,6.8 知识发现,6.8.4 知识发现（数据挖掘）的方法 常用方法： 回归分析（多元分析、自回归） 判别分析（贝叶斯判别、费歇尔判别

38、、非参数判别） 聚类分析（系统聚类、动态聚类） 探索性分析（主元分析法、相关分析法）,6.8 知识发现,6.8.4 知识发现（数据挖掘）的方法 1. 统计方法 （2）模糊集 开发数据的不确定性模型 （3）支持向量机 支持向量机（support vector machine, SVM）建立在统计学习理论和结构风险最小化原则之上，其主要思想是针对两类分类问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误。,6.8 知识发现,6.8.4 知识发现（数据挖掘）的方法 1. 统计方法 （3）支持向量机,不同的分类超平面,最优分类超平面及其间隔,线性不可分,6.8 知识发现,6.8.4

39、知识发现（数据挖掘）的方法 1. 统计方法 （4）粗糙集 粗糙集合理论(Rough Set, 也称为RS理论)由波兰数学家Pawlak.Z于1982年提出。粗糙集对不精确概念的描述是通过上近似（upper approximation）和下近似（lower approximation）这两个精确概念来实现的。一个概念（或集合）的下近似是指其中的元组肯定属于该概念；一个概念（或集合）的上近似是指其中的元组可能属于该概念。,6.8 知识发现,6.8.4 知识发现（数据挖掘）的方法 1. 统计方法 粗糙集理论是一种研究不精确、不确定性知识的数学工具，这一方法在数据挖掘中具有重要的作用，通常处理含糊性和

40、不确定的问题，发现不准确数据或噪音数据内在的结构关系，可用于特征的约简和相关分析中。 粗糙集方法优点：不需要预先知道的额外信息，如统计中要求的先验概率和模糊集中要求的隶属度，算法简单，易于操作。,6.8 知识发现,6.8.4 知识发现（数据挖掘）的方法 2. 机器学习方法 可能用于机器发现的机器学习方法有： （1） 规则归纳。 规则反映数据项中某些属性或数据集中某些数据项之间的统计相关性。 （2）决策树。 决策树的每一个非终叶节点表示所考虑的数据项的测试或决策。 （3）范例推理。 范例推理是直接使用过去的经验或解法来求解给定的问题。,6.8 知识发现,6.8.4 知识发现（数据挖掘）的方法 2

41、. 机器学习方法 （4） 贝叶斯网络。 贝叶斯信念网络是概率分布的图表示。贝叶斯网络基于后验概念的贝叶斯定理，是建立在数据进行统计处理基础上的方法，将不确定事件通过网络连接起来，可以对其他相关事件的结果进行预测，其网络变量可以是可见的，也可隐藏在训练样本中。贝叶斯网络具有分类、聚类、预测和因果关系分析的功能，其优点是易于理解，预测效果较好，缺点是对发生频率很低的事件预测效果不好。,6.8 知识发现,6.8.4 知识发现（数据挖掘）的方法 （5）科学发现。 科学发现是在实验环境下发现科学定律。 （6）遗传算法。 在求解过程中，通过最好解的选择和彼此组合，使期望解的集合愈来愈好。 3. 神经计算方

42、法 4. 可视化方法 可视化（visualization）就是把数据、信息和知识转化为可视的表示形式的过程。,6.8 知识发现,6.8.5 数据挖掘的应用 银行 美国银行家协会(ABA)预测数据仓库和数据挖掘技术在美国商业银行的应用增长率是14.9。 分析客户使用分销渠道的情况和分销渠道的容量 ；建立利润评测模型；客户关系优化；风险控制等 电子商务 网上商品推荐；个性化网页；自适应网站 生物制药、基因研究 DNA序列查询和匹配；识别基因序列的共发生性 电信 欺诈甄别；客户流失 保险、零售。,6.8 知识发现,6.8.5 数据挖掘的应用,Open Accnt,Add New Product,De

43、crease Usage,?,Time,序列分析 Sequence Analysis,决策树 Decision Trees,倾向性分析,客户保留 客户生命周期管理 目标市场 价格弹性分析,6.8 知识发现,6.8.5 数据挖掘的应用,神经网络 Neural Networks,聚类分析 Clustering,客户细分 市场细分,倾向性分析 客户保留 目标市场 欺诈检测,关联分析 Association,市场组合分析 套装产品分析 目录设计 交叉销售,6.8 知识发现,6.8.6 数据挖掘技术 数据挖掘任务分类 描述（Description）：了解数据中潜在的规律 预言（Predication）：

44、用历史预测未来 数据挖掘技术 概念/类描述 关联规则分析 分类（预言） 聚类 序列模式 异常检测,6.8 知识发现,6.8.6 数据挖掘技术 1. 概念/类描述（Concept Description)： 特征化和区分（Characterization and Comparision) 概念或类别描述使用汇总的、简洁的、精确的方式描述每个类和概念，可通过前面的方法得到： （1）数据特征化，一般地汇总所研究类的数据； （2）数据区分，将目标类与一个或多个比较类进行比较； （3）数据特征化和比较，两者的结合。 数据特征的输出可以用多种形式输出，包括扇形图、条图、曲线、多位数据立方体和交叉表在内的多

45、维表。结果描述也可以用概括关系或关联规则形式来表示。,6.8 知识发现,6.8.6 数据挖掘技术 2. 关联分析(Association Rules) 关联规则分析就是发现关联规则，在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。 规则形式： Body Head support, confidence 例： buys(x, “diapers”) buys(x, “beers”) 0.5%, 60% major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%,6.8 知识发现,6.8.6 数据

46、挖掘技术 支持度s， 一次交易中包含A,B的可能性 Support(AB)= P(AB)； 可信度 c， 包含A的交易中也包含B的条件概率 Confidence (AB)=P(B|A) 同时满足大于等于最小支持度阈值（min_support）和最小可信度（min_confidence）的规则称作强规则。 满足大于等于最小支持度(min_support), 称项目集X I是频繁项目集(Frequent Itemset)。,6.8 知识发现,6.8.6 数据挖掘技术 对于 A C： support = support(A 、C) = 50% confidence = support(A 、C)/s

47、upport(A) = 66.6%,最小支持度 50% 最小可信度 50%,6.8 知识发现,6.8.6 数据挖掘技术 Apriori算法 基本思想: 频繁项集的任何子集也一定是频繁的。 算法的核心: 用频繁的(k 1)-项集生成候选的频繁 k-项集 用数据库扫描和模式匹配计算候选集的支持度 算法瓶颈: 候选集生成 巨大的候选集: 多次扫描数据库：,6.8 知识发现,6.8.6 数据挖掘技术,数据库 D,扫描 D,C1,L1,L2,C2,C2,扫描 D,C3,L3,扫描 D,6.8 知识发现,6.8.6 数据挖掘技术 3. 分类(Classification) 分类是找出描述并区分数据类或概念

48、的分类函数或分类模型(也常常称作分类器)，该模型能把数据库中的数据项映射到给定类别中的某一个，以便能使用模型预测类标记未知的对象类。 常用的分类方法： （1） 信息论方法：ID3方法； IBLE方法； ID3方法 -决策树方法 利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，并根据字段的不同取值建立树的分枝，在每个分枝子集中重复建树的下层节点。,6.8 知识发现,6.8.6 数据挖掘技术 IBLE方法 - 利用信息论的信息容量寻找数据库中的信息量从大到小的多个字段的取值建立决策规则树。 （2） 集合论方法 粗集方法、概念格方法 （3） 人工神经网络方法 前馈网络：含

49、感知机.反向传输模型.函数式网络。 反馈式网络：用于联想记忆和优化计算。 自组织网络：用于聚类。 （4）遗传算法：模拟生物进化过程的方法。 （5）统计分析方法：贝叶斯网，线性回归分析，线性判别分析，聚类分析，差异分析，因子分析等。,6.8 知识发现,6.8.6 数据挖掘技术 分类器评价或比较尺度 （1）预测准确度 ： 保持（holdout） K-次交叉验证（k-fold cross validation） （2）计算复杂度：空间和时间的复杂度 （3）模型描述的简洁度,6.8 知识发现,6.8.6 数据挖掘技术 保持（holdout） 随机划分为两个独立的数据集： 通常:训练集 (2/3),测试

50、集(1/3) 变形：随机子选样-holdout方法重复k次,数据,训练集,测试集,导出分类法,评估准确性,6.8 知识发现,6.8.6 数据挖掘技术 K-次交叉验证（k-fold cross-validation） 将数据集分为k个子集； 用k-1个子集作训练集，1个子集作测试集，然后k次交叉验证；,数据,S1,S2,Sk,训练集,测试集,6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） （1）BNC流程,应用阶段,6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） （2）贝叶斯公式,先验概率P(cj),后验概率P(cj|x),联合概率P(x|cj),6.8

51、知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） 先验概率P(cj) P(cj)代表还没有训练数据前，cj拥有的初始概率。P(cj)常被称为cj的先验概率(prior probability) ，它反映了我们所拥有的关于cj是正确分类机会的背景知识，它应该是独立于样本的。 如果没有这一先验知识，可以简单地将每一候选类别赋予相同的先验概率。通常我们可以用样例中属于cj的样例数|cj|比上总样例数|D|来近似，即,6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） 联合概率P(x|cj) 联合概率是指当已知类别为cj的条件下，看到样本x出现的概率。 若设x = 则P(x|

52、cj)= P(a1,a2am| cj) 后验概率P(cj|x) 给定数据样本x时cj成立的概率,而这正是我们所感兴趣的 P(cj|x )被称为C的后验概率（posterior probability），因为它反映了在看到数据样本x后cj成立的置信度。,6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） （3） BNC基本概念 原理： 通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。 计算： BNC通常记为： 通过计算每个对象的最大后验概率进行分类，即： P(cMAP|x) = max P(cj|x) j

53、(1,|C|),6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） （3） BNC基本概念 分类：,NB (Nave Bayesian classification) TAN (Tree Augmented Nave Bayesian classification) BAN (BN Augmented Nave Bayesian classification) GBN (General Bayesian Network classification),6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） NB,(1)NB 中，分类节点是所有属性节点的父结点 (2)

54、 所有的属性变量之间是相互独立的 (3)由于(1)(2)两点，NB的结构比较容易构建，不需要结构学习算法,1 Nir Friedman, Bayesian Network Classifiers, Machine Learning, 1997, 29:131163,6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） TAN,(1)TAN 是NB的一个扩展； (2) 分类节点作为所有属性节点的父结点； (3)除(2)之外，属性节点还允许有一个其它 属性节点作为其父节点，父节点的个数最多为2个；,6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） BAN,BAN,B

55、AN是NB和TAN的扩展，它与TAN的不同之处在于，属性节点之间的不再是树形结构，而一个图的结构。(Friedman et al. 1997),6.8 知识发现,6.8.6 数据挖掘技术 贝叶斯分类器（BNC） GBN,GBN与前面的分类器不同之处在于，它把分类节点看成普通的节点，所有的节点构成一个有向无环图。GBN的结构学习常采用贝叶斯网络结构学习的算法，如K2算法。,6.8 知识发现,6.8.6 数据挖掘技术 4. 聚类(Clustering) 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的数据相异。 聚类是一种无监督分类法， 没有预先指定的类。,X值,聚类示例,

56、6.8 知识发现,6.8.6 数据挖掘技术 4. 聚类(Clustering) 与分类的区别： 分类依赖于预先定义的类和带类标号的训练实例，是一种观察式 的学习；而聚类是找到这个簇的特征或者标号的过程。 一个有效的聚类算法必须满足两个条件： 类内数据对象的强相似性，通常用紧致度描述； 类间数据对象的弱相似性，常采用分离度描述。,6.8 知识发现,6.8.6 数据挖掘技术 4. 聚类(Clustering) 聚类算法的分类 聚类分析算法取决于数据的类型、聚类的目的和应用。 （1）基于划分方法 给定一个包含n个对象的数据集和要构建的划分数目k，划分方法首先创建一个初始划分，然后采用一种迭代的重定位

57、技术，尝试通过对象在划分间的移动来改进划分 （2）基于层次方法 层次聚类是将数据集分解成几级进行聚类，层的分解可以用树形图来表示以任一样本,6.8 知识发现,6.8.6 数据挖掘技术 4. 聚类(Clustering) （3）基于密度的方法 点为基础，当该点的给定邻域内包含的数据点个数超过某一给定阈值时，就以其邻域中的数据点为基础继续进行广度或深度探索，扩展簇的大小。 （4）基于网格的方法 基于网格的聚类算法的特点是采用一个多分辨率的网格数据结构，从而在该网格结构上进行聚类。 （5）基于模型的方法 基于模型的方法为每个类假定了一个模型，并试图寻找数据对给定模型的最佳拟合。,6.8 知识发现,6

58、.8.6 数据挖掘技术 4. 聚类(Clustering) K-means算法 （1）从D中随机取k个元素，作为k个簇的各自的中心。 （2）分别计算剩下的元素到k个簇中心的相似度，将这些元素分别划归到相似度最高的簇。 （3）根据聚类结果，重新计算k个簇各自的中心。 （4）将D中全部元素按照新的中心重新聚类。 （5）重复第4步，直到聚类结果不再变化。 （6）将结果输出。,6.8 知识发现,6.8.6 数据挖掘技术 4. 聚类(Clustering) 相似性度量,(1)欧几里德距离(Euclidean Distance),(2)曼哈顿距离(Manhattan Distance),6.8 知识发现,6.8.6 数据挖掘技术 4.