AI-6-机器学习.ppt

第六章 机器学习概述示例学习基于解释的学习遗传算法加强学习基于范例的学习知识发现与数据挖掘6.1 概述机器学习的基本概念机器学习的发展历史机器学习的分类6.1 概述什么是机器学习？代表性代表性观点：点：l 西蒙（西蒙（Simon,1983）：学）：学习就是系就是系统中的适中的适应性性变化，化，这种种变化化使系使系统在重复同在重复同样工作或工作或类似工作似工作时，能，能够做得更好。做得更好。l 明斯基（明斯基（Minsky,1985）：学）：学习是在人是在人们头脑里（心理内部）有用里（心理内部）有用的的变化。化。l 迈克克尔斯基（斯基（Michalski,1986）：学）：学习是是对经历描述的建立和修改。描述的建立和修改。一般性解一般性解释：学学习是一个有特定目的知是一个有特定目的知识获取和能力增取和能力增长过程，其内在行程，其内在行为是是获得知得知识、积累累经验、发现规律等，其外部表律等，其外部表现是改是改进性能、适性能、适应环境、境、实现自我完善等。自我完善等。6.1 概述为什么要研究机器学习？一个真正的智能系一个真正的智能系统必必须具具备真正的学真正的学习功能。功能。不不仅可以根据数据和可以根据数据和经验等构造一个具有等构造一个具有一定智能的系一定智能的系统，而且，而且还可以通可以通过归纳、推理推理等方法等方法进一步丰富自己，完善自己，一步丰富自己，完善自己，使自己适使自己适应外界外界环境。境。.6.1 概述实现的困难：预测难：学习后知识库发生了什么变化，系统功能的变化的预测。归纳推理：现有的归纳推理只保证假，不保证真。演绎推理保真。而且，归纳的结论是无限多的，其中相当多是假的，给生成的知识带来不可靠性。机器目前很难观察什么重要、什么有意义。6.1 概述发展历史 神经系统模型和决策理论50年代开始。其特点是对开始与无初始结构和面向作业知识的通用学习系统感兴趣。包括构造多种具有随机或部分随机的初始结构的基于神经模型的机器。这些系统一般称为神经网络或自组织系统。由于当时计算机技术状态，多停留在理论和硬件上。这些元件类似于神经元，他们实现简单的逻辑功能。6.1 概述发展历史 神经系统模型和决策理论1965年左右，神经网络经验模式导致了模式识别这一新学科以及机器学习的决策理论方法。这种方法中学习就是从给定的一组经过选择的例子中获得判断函数，有线性的、多项式的、或相关的形式。当时，Samuel(1959-1963)的跳棋程序是最著名的成功的学习系统之一。达到了跳棋大师的水平。人工智能第六章 机器学习6.1 概述符号概念获取1975年左右提出的。这类学习过程通过分析一些概念的正例和反例构造出这些概念的符号表示。表示的形式一般是逻辑表达式、决策树、产生式规则或语义网络。代表有Winston的ARCH。人工智能第六章 机器学习6.1 概述知识加强和论域专用学习此方法是70年代中期开始，沿着符号主义路线进行的。在原有基础上逐步加强、重于专业的专用性。强调使用面向任务的知识和它对学习过程的引导作用。系统包括预先确定的概念、知识结构、论域约束、启发式规则和论域有关的变换。系统在开始并不具有所有的属性或概念，在学习过程中系统应得到一些新的属性或概念。没有绝对的学习方法。许多系统体现出上述途径的组合。人工智能第六章 机器学习6.1 概述机器学习进入新阶段的重要表现：（近十年）（1）机器学习已成为新的边缘科学并在高校形成一门课程。它综合应用心理学、生物学和神经生理学以及数学、自动化和计算机科学形成机器学习理论基础。6.1 概述机器学习进入新阶段的重要表现：（近十年）（2）结合各种学习方法，取长补短的多种形式的集成学习系统的研究正在兴起。特别是连接学习，符号学习的耦合可以更好地解决连续性信号处理中知识与技能的获取与求精问题而受到重视。6.1 概述机器学习进入新阶段的重要表现：（近十年）（3）机器学习与人工智能各种基础问题的统一性观点正在形成。例如：学习与问题求解结合进行，知识表达便于学习的观点产生了通用智能系统的组块学习。类比学习与问题求解结合的基于案例学习已成为经验学习的重要方向。6.1 概述机器学习进入新阶段的重要表现：（近十年）（4）各种学习方法的应用范围不断扩大，一部分已形成商品。归纳学习的知识获取工具已在诊断分类性专家系统中广泛应用。连接学习在声图文识别中占优势。分析学习用于设计综合性专家系统。遗传算法与强化学习在工程控制中有较好的应用前景。与符号系统耦合的神经网络连接学习将在企业的智能管理与智能机器人运动规划中发挥作用。6.1 概述机器学习进入新阶段的重要表现：（近十年）（5）与机器学习有关的学术活动空前活跃。国际上除每年一次的机器学习研究会外，还有计算机学习理论会议及遗传算法会议。6.1 概述分类：按学习策略机械学习和直接输入新知识（记忆学习）学习这不需要进行任何推理或知识转换，将知识直接装进机器中。根据示例学习（传授学习、指点学习）从老师或其它有结构的事物获取知识。要求学习者将输入语言的知识转换成它本身的内部表示形式。并把新的信息和它原有的知识有机地结合为一体。6.1 概述演绎学习学习者找出现有知识中所要产生的新概念或技能十分类似的部分。将它们转换或扩大成适合新情况的形式，从而取得新的事实或技能。类比学习演绎学习与归纳学习的组合。匹配不同论域的描述、确定公共的结构。以此作为类比映射的基础。寻找公共子结构是归纳推理，而实现类比映射是演绎推理。6.1 概述基于解释的学习学生根据教师提供的目标概念、该概念的一个例子、领域理论及可操作准则，首先构造一个解释来说明为什么该例子满足目标概念，然后将解释推广为目标概念的一个满足可操作准则的充分条件。归纳学习 给学习者提供某一概念的一组正例和反例，学习者归纳出一个总的概念描述，是它适合于所有的正例且排除所有的反例。（目前研究较多的一种方法）6.1 概述研究目的希望得到通用的算法 研究了解学习知识的模型、认知模型 解决实际问题的知识库域系统，达到工程目标 研究特点不可预测性机械学习n死死记硬背学硬背学习n十分重要的一个十分重要的一个组成部分成部分n基本基本过程是：程是：执行系行系统每解决一个每解决一个问题，系，系统就就记住住这个个问题和它和它的解，当以后再遇到此的解，当以后再遇到此类问题时，系，系统就不必重新就不必重新进行行计算，而可以直接找出原来的解去使用算，而可以直接找出原来的解去使用 机械学习(x1,x2,xn)(y1,y2,yn)(x1,x2,xn),(y1,y2,yn)f存储存储输入模式输入模式执行函数执行函数输出模式输出模式输入输出模式对输入输出模式对机械学习的学习模型机械学习的学习模型6.2 示例学习归纳学习是人类智能的重要体现，从而也成为机器学习的核心技术之一。归纳学习是从教师或环境提供的事例中抽象出结论（对于概念的泛化描述）的知识获取过程。根据所用的具体实例是否由教师来分类（即有无教师指导），可将归纳学习分为示例学习以及从观察和发现中学习。本节将重点分析示例学习的一些基本学习策略，并介绍示例学习的一个变种-决策树学习算法ID3，而在6.7.1节中将介绍从观察和发现中学习的一个例子-定理发现6.2.1 示例学示例学习的基本策略的基本策略示例学习的任务是基于某个概念的一系列实例，生成一个反映该概念本质的定义。这个定义应覆盖所有的正例，而不包含任何反例，同时又可用来指导对新例子的分类识别。下面，首先介绍示例学习过程中搜索和获取概念描述（定义）的基本思路，然后讨论遵从该思路的三种示例学习策略：逐步泛化的学习策略、逐步特化的学习策略、双向学习策略。6.2.1 示例学示例学习的基本策略的基本策略1、概念描述的搜索和、概念描述的搜索和获取取在示例学习中，概括（覆盖）所有正例的概念描述，称为完全描述；而不概括任何反例的概念描述则称为一致描述。对于任何包含正、反例的例子集，都可获得既完全又一致的概念描述，称为解描述；6.2.1 示例学示例学习的基本策略的基本策略示例学习系统应用二个重要概念：例子空间，假设空间（又称概念空间）。所有可能的正、反例构成例子空间；可能的概念描述称为假设，它们构成假设空间。6.2.1 示例学示例学习的基本策略的基本策略下面以某种病态细胞的分类识别为例，说明基于这二个空间的示例学习过程。6.2.1 示例学示例学习的基本策略的基本策略我们可用一个三元组来表示每个细胞体：（核数、尾数、染色状）而每个细胞则可用由二个细胞体三元组组成的集合来表示。例如P1可以表示为(2,2,深)(1,1,浅)6.2.1 示例学示例学习的基本策略的基本策略该假设空间包含二个可能的假设，和b。假设不必给每个特性（属性）都指明应取值，那些没有给出值的特性对于该概念的描述是无关紧要的。例如，假设()说明若某一个细胞中一个细胞体有二个胞核，另一个有一个尾巴，且染色是深的，则该细胞有病症，可表示为：(2,?,?)(?,1,深)6.2.1 示例学示例学习的基本策略的基本策略泛化/特化是反对称、可传递的关系，所以假设空间是个偏序集；即上下层假设间具有泛化/特化关系，而同层假设间是无关的。例如，图6.5中(a)、(b)都是(c)的特化描述,但(a)、(b)之间无泛化/特化关系。6.2.1 示例学示例学习的基本策略的基本策略任何的概念获取过程都可以看成假设空间中的搜索过程，且不同的搜索方式对应于不同的学习策略：逐步泛化的学习策略，对应于自底向上的搜索；逐步特化的学习策略，对应于自顶向下的搜索；双向学习策略，对应于双向搜索。6.2.1 示例学示例学习的基本策略的基本策略2、逐步泛化的学、逐步泛化的学习策略策略逐步泛化的学习策略采用宽度优先、自底向上的搜索方式。返回到右图中所示的例子。6.2.1 示例学示例学习的基本策略的基本策略3、逐步特化的学、逐步特化的学习策略策略与泛化策略相比，特化策略沿相反的方向搜索,但是实施这二种策略的基本方式是类似的,即新例子的加入会导致新假设的增加和已存在假设的删除。但是在特化策略中，正例和反例所起的作用同在泛化策略中的作用是相反的。图6.7是一个例子空间,给出了二个正例和二个反例。6.2.1 示例学示例学习的基本策略的基本策略特化过程如图所示：6.2.1 示例学示例学习的基本策略的基本策略4、双向学、双向学习策略策略米切尔以不同的方式实现双向学习策略，称为版本空间法(VersionSpace），已应用于符号积分系统LEX的学习中。该方法用两个假设集、分别表示作泛化、特化搜索的假设空间。当遇见一个新的正例时，如不能使集的描述覆盖该正例，则在该集中进行泛化搜索；而当一个新的反例产生时，如被集包含，则在该集中进行特化搜索。和实际上指示了期望获取的最终解描述的上、下界，当、合一时，合一的解描述就是期望学到的概念描述（定义）。6.2.1 示例学示例学习的基本策略的基本策略图6.9给出应用版本空间法于图6.3例子集的示例学习情况。6.2.1 示例学示例学习的基本策略的基本策略图6.10展示了当遇见一个反例时的处理过程。第一个反例N1的出现说明G2过于泛化，所以将G2特化为G3，而同时S2中只留下一个假设，转变为S3。6.2.2 决策决策树构造法构造法ID3如果学习的任务是对一个大的例子集作分类概念的归纳定义，而这些例子又都是用一些无结构的属性值对来表示，则可以采用示例学习方法的一个变种决策树学习，其代表性的算法是昆兰（J.R.Quinlan，1986）提出的ID3。6.2.2 决策决策树构造法构造法ID3高度发色眼睛类别矮黑色蓝色高黑色蓝色矮金色蓝色高金色棕色高黑色棕色矮金色棕色高金色蓝色高红色蓝色6.2.2 决策决策树构造法构造法ID36.2.2 决策决策树构造法构造法ID36.2.2 决策决策树构造法构造法ID3产生这种归纳学习方法的关键在于如何选择一系列有用的属性来测试一个对象集，以使生成的决策树是最小的。ID3采用了香农（Shannon）信息论中的方法以使分类时期望（平均）的测试次数最小。决策树的复杂程度与借助这个消息所传递的信息量密切相关。若决策树传递的不同类别消息的概率用P+(对应于+类)和P-表示(对应于-类)，那么这个消息的期望信息量为:-P+log2P+-P-log2P-对给定的物体集C，我们可以把这概率近似地表示为相对频率,此时P+和P-分别等于C中类别为+和-的对象所占的比例。6.2.2 决策决策树构造法构造法ID3从C集对应的决策树中得到消息的期望信息量记为M(C)，并定义M()=0。对于上述例子，C集有八个例子，三个为“+”，五个为“-”，则：M(C)=-（3/8）log2（3/8）-（5/8）log2（5/8）=0.954bits6.2.2 决策决策树构造法构造法ID3图6.13是一个局部决策树，A为构造决策树时下一个可能选取的属性，Ai为属性A的值且是互斥的。属性A将集合C划分为若干个子集合C1，C2，.，Cn。设M(Ci)是值为Ai的子集Ci所对应决策树的期望信息量，则确定以属性A作为树根的决策树的期望信息量B(C,A)可通过权值平均而得到:B(C,A)(A值为Ai的概率)*M(Ci)同样我们把Ai的概率用相对比例来代替，即在所有对象中具有Ai值所占的相对比例。6.2.2 决策决策树构造法构造法ID3我们希望待选的测试属性能使决策树获得最大的信息增益即M(C)-B(C,A)为最大值。二者的差越大，说明测试这个属性所能传递的信息量越大,则判别的速度也就越快。6.2.2 决策决策树构造法构造法ID36.2.2 决策决策树构造法构造法ID3图6.14中，我们选取的属性为“高度”，对高度值为“高”的分支的所需期望信息量为：-（2/5）log2（2/5）-（3/5）log2（3/5）=0.971bits同样对值为“矮”的分支为:-（1/3）log2（1/3）-（2/3）log2（2/3）=0.918bits则以属性“高度”作划分后进一步判别所需的期望信息量为B(C,“高度”)=5/8*0.971+3/8*0.918=0.951则测试这属性传递的信息为:M(C)-B(C,高度)=0.954-0.951=0.003bits。6.2.2 决策决策树构造法构造法ID3如果我们不是选择高度而选用属性头发，如图6.12所示,则有:B(C,头发)=3/8*0+1/8*0+4/8*1=0.5bits则测试属性头发获取的信息为M(C)-B(C,头发)=0.945-0.5=0.45bits。同样对属性眼睛测试，获得信息为0.347bits。根据最大信息量原理,ID3就选取头发为决策树的根节点属性。ID3通过不断的循环处理，逐步求精决策树，直到形成一棵完整的决策树，即树的叶节点所对应的对象（例子）均属于同一类。ID3算法应用实例1Buys_Computer决策树ID3算法应用实例26.3 基于解释的学习基于解释的学习是八十年代中期兴起的新型机器学习方法，其旨在通过应用领域理论（领域知识）对单一事例所作的分析，构造满足预定目标概念并遵从可操作准则的一个解释。基于解释的学习是分析学习的主要方式，本节将重点分析米切尔等人提出的方法-基于解释的泛化（EBG，Explanation-BasedGeneralization），并对基于解释学习方法中的几个主要问题做一些简要讨论。6.3 基于解释的学习1986年，米切尔等人提出的EBG描述框架如下：给定：目标概念：对于所学概念的一个初始描述（其尚不满足可操作准则）；训练例子：目标概念的一个正例；领域理论：解释训练例子为何是目标概念正例时可用的规则和事实集合；可操作准则：学到的知识（对于目标概念的解释）所需遵从的表示形式，以使这些知识能用于问题求解活动。获取：对于目标概念的一个特化描述，其是训练例子的泛化，且满足可操作准则。基于解释学习的工作原理米切尔等人提出基于解释的泛化过程分为二个阶段：(1)解释：使用领域理论建立一个证明训练例子满足目标概念定义（初始描述）的解释结构；该结构可表示为一颗证明推理树，又称解释树，其每个分枝的叶节点上的表达式都必须满足可操作准则。(2)泛化：通过将解释结构中的常量变换为变量（以实现对于训练例子的泛化），获得对于目标概念的一个特化描述,并使其满足可操作准则。这可通过在解释结构中对目标概念进行回归(regressing)来完成。对回归所得的表达式（相应于解释结构中的叶节点）加以合取，就建立了目标概念的一个特化描述。基于解释学习的例子米切尔等人考虑了目标概念为Safetostack(x，y)的学习，即学习任务是识别一对物体(x，y),使得x能安全地放在y上面。这个问题的描述如下：给出：目标概念：一对物体(x，y),使得Safetostack(x，y)训练例子：On(obj1,obj2)ISA(obj1,BOX)ISA(obj2,ENDTABLE)Color(obj1,RED)Color(obj2,BLUE)Volume(obj1,1)Density(Obj1,1)基于解释学习的例子领域理论：not(Fragile(p2)Lighter(p1，p2)Safe-to-stack(p1，p2)Volume(p,v)Density(p,d)Weight(p,v*d)Weight(p1,w1)Weight(p2,w2)less(w1,w2)Lighter(p1,p2)ISA(p,ENDTABLE)Weight(p,5)Less(1,5)基于解释学习的例子可操作准则：目标概念的特化描述必须用那些描述训练例子时使用的谓词来表示（如Volume，Color，Density）或选用领域理论中容易评价的谓词（如Less）。获取：目标概念的一个特化描述，其是训练例子的泛化，且满足可操作准则。基于解释学习的例子在EBG的第一个阶段（即解释阶段）：第二阶段（即泛化阶段）：基于解释学习的例子至此，回归过程已到达图6.15解释结构的所有叶节点。鉴于回归过程中产生的变量置换是x/p1,v*d/w1,y/p2,5/w2，Less(w1,w2)转变为Less(v*d,5)。所以，可以建立目标概念Safetostack(x，y)的一个特化描述，如下：Volume(x,v)Density(x,d)ISA(y,ENDTABLE)Less(v*d,5)显然，该描述满足可操作准则，且是目标概念Safetostack(x，y)的充分解释，因为初始的目标概念是这个特化描述的推理结论。不完善不完善领域理域理论对于基于解释的学习，能否从例子得出一个合理的解释很大程度上依赖于领域理论是否完善。然而，在复杂的实际领域中，往往难以构造出一个完善的领域理论。这就要求我们的学习系统有能力自动检测、改正不完善理论或有方法弥补领域理论的不足。6.4 遗传算法算法遗传算法(GeneticAlgorithm，简称GA)是一种基于进化论优胜劣汰、适者生存的物种遗传思想的搜索算法。上世纪50年代初，由于一些生物学家尝试用计算机模拟生物系统，从而产生了GA的基本思想。美国密执根大学的霍勒德（J.H.Holland）于70年代初提出并创立了遗传算法。遗传算法作为一种解决复杂问题的崭新的有效优化方法，近年来得到了广泛的实际应用，同时也渗透到人工智能、机器学习、模式识别、图像处理、软件技术等计算机学科领域。GA在机器学习领域中的一个典型应用就是利用GA技术作为规则发现方法应用于分类系统。6.4.1 简单遗传算法算法霍勒德提出的遗传算法也称为简单遗传算法（simplegeneticalgorithm,SGA），是一种基本的遗传算法。SGA以0、1组成的串表示问题域中待进化的个体（初始解）。利用遗传操作交换和突变，SGA从当前个体的集合群体的各串中产生下一代群体。这一过程循环进行，直到满足了结束条件（如循环了指定次，或群体性能不再改进）。6.4.1 简单遗传算法算法SGA的处理过程如下：begin1.选择适当表示，生成初始群体；2.评估群体；3.While未达到要求的目标dobegin1.选择作为下一代群体的各个体；2.执行交换和突变操作；3.评估群体；endend6.4.1 简单遗传算法算法u对于一个SGA算法来说主要涉及以下内容：1.编码和初始群体生成；2.群体的评价；3.个体的选择；4.交换；5.突变；6.4.1 简单遗传算法算法1.编码和初始群体的生成和初始群体的生成SGA要求个体均以0、1组成的串来表示，且所有个体串都是等长的。SGA处理的起始点并非一个个体，而是由一组个体所组成的群体。一般可用随机方法来产生初始群体，当然最好能考虑各个体的代表性和分布概率。6.4.1 简单遗传算法算法2.群体的群体的评价价对群体中各个体的适应性评价常需直接利用待优化问题的目标函数。这一目标函数也可称为适应函数，个体选择（或再生）过程正是基于这一函数来评价当前群体中各个体的再生概率。6.4.1 简单遗传算法算法3.个体的个体的选择选择操作是对自然界适者生存的模拟。评价值（目标函数值）较大的个体有较高的概率生存，即在下一代群体中再次出现。SGA采用称为旋转盘（roulettewheel）的方法来产生各个体的再生数。方法是：每一个体均对应于旋转盘中的一个以园点为中心的扇形区域，区域角度为2*fi/fi，因而，各个体的区域角度之和等于2。然后随机产生一个0到2的值，根据该值所对应的区域，再生一个对应个体，直到产生的个体个数达到所需的数目，从而生成下一代的原始群体。这个群体还需进一步应用交换和突变操作。6.4.1 简单遗传算法算法4.交交换SGA采用的是单点交换。设串长为L，交换操作将随机选择一个交换点（对应于从1到L-1的某个位置序号），紧接着两串交换点右边的子串互换，从而产生了两个新串。例如，设1，2为要交换的串，交换点被随机选择为7（串长为10）。11000011111 21111111011交换得新串1，2：11000011011 211111111116.4.1 简单遗传算法算法5.突突变另一种遗传操作是突变，它一般在交换后进行。突变操作的对象是个体（即串），旨在改变串中的某些位的值，即由0变为1，或由1变为0。并非所有位都能发生变化，每一位发生变化的概率是Pm。Pm为事先指定的01之间的某个值，称为突变率。突变的作用是引进新的遗传物质或恢复已失去的遗传物质。6.4.1 简单遗传算法算法下面举一例子来说明遗传算法的一个进化循环。设每一串的长度为10，共有4个串组成第一代群体（POP1），目标函数（适应函数）为各位值之和，因而函数值为010。u群体POP1串 适应值 0000011100 3 1000011111 6 0110101011 6 1111111011 96.4.1 简单遗传算法算法POP1中四个串的适应值分别为：3，6，6，9，所以再生的比例个数为：0.5，1，1，1.5。若最后实际的再生个数为0，1，1，2，则产生选择后的群体POP2。u群体POP2（选择后）串 适应值1000011111 60110101011 61111111011 91111111011 96.4.1 简单遗传算法算法下一步对POP2中各串配对，随机选择串1和串4为一对，串2和串3为另一对。设交换率为0.5，即只有一对串发生交换，如串1和串4。若交换点随机选在位置7，因而交换后产生群体POP3。u群体POP3（交换后）串 适应值1000011011 50110101011 61111111011 91111111111 106.4.1 简单遗传算法算法设突变率为0.05，即在POP3的40个位中，共有2个位发生突变，不妨设突变发生在串2的第6位和串4的第1位，从而产生群体POP4。群体POP4（突变后）串 适应值 1000011011 5 0110111011 7 1111111011 9 0111111111 9注意，仅群体POP4代表新一代的群体（上一代为POP1），POP2和POP3只是一些进化中的中间群体。6.4.1 简单遗传算法算法在SGA算法中，一般采用的群体大小为30到200，交换率为0.5到1，突变率为0.001到0.05。这些参数：群体大小、交换率、突变率，统称为GA的控制参数，应在算法运行前事先设定。当然，已有人研究了控制参数在算法运行中的自适应调整，以提高GA的灵活性。6.4.2分分类系系统遗传算法不仅可作为搜索和优化的一种方法，而且还可作为一种机器学习技术。例如，可以将基于遗传算法的机器学习应用于分类系统。霍勒德等人将分类系统视为一种认知模型，其可在环境中学习一些简单的串规则（stringrules）（又称为分类器），以指导系统的行为。6.4.2分分类系系统一个分类系统包含以下三个组成部分：1、执行系统；2、评价系统；3、遗传算法（GA）。6.4.2分分类系系统1.执行系行系统执行系统实际上是一个简单的产生式系统,产生式规则形如：ifthen在分类系统里，规则的条件和动作都是串（以便于GA处理）。条件部分的串说明了规则所能匹配的消息集合，而动作部分则说明了规则执行时要发送的消息。6.4.2分分类系系统 为简便起见，设串长为k，由表0,1,#中的三种元素组成，其中#表示不关心。条件串中的#表示可与0或1匹配，而动作串中的#表示一种消息传递，即该位的值等于与条件串匹配的消息的对应位值。例如，设k4，有规则为：if#10#then 010#若现有消息1101，与规则匹配后，该规则将发送消息0101。为方便表示，我们可将规则（分类器）的形式改为：:6.4.2分分类系系统执行系统的结构如图6.20。6.4.2分分类系系统执行系统基本上重复执行以下步骤：1、将输入的消息放入消息队列中；2、将消息队列中的所有消息与所有分类器的条件做比较；3、将所有能匹配的分类器所产生的消息放入一个新的消息队列中；4、用新的消息队列取代老的消息队列；5、将消息队列中的消息加以解释并输出。其中24步可循环进行，直到没有分类器可与消息队列中的消息匹配为止。6.4.2分分类系系统下面举一例子来说明这种匹配过程，设输入消息为0111，分类器有四个：1）01#:00002）00#0:11003）11#:10004）#00:0001首先，该消息与分类器1匹配，产生消息0000。消息0000又与分类器2和4匹配，产生两条消息1100和0001。其中1100与分类器3和4匹配，分别产生1000和0001。最后，消息1000与分类器4匹配产生0001，处理过程结束。6.4.2分分类系系统2.评价系价系统-组桶式算法桶式算法评价系统的目的是:给每个分类器在系统运行时对执行结果的贡献作个评价（或打分）。实现评价的方法很多，其中最有名的是组桶式算法（简称BBA）。BBA可理解为一个进行情报买卖的交易所，交易人是分类器。分类器作为一个中间商只与上家（发送消息使该中间商激活的分类器）和下家（其条件部分与该中间商所发器）作交易。因此，分类器形成了一条从消息制造者（系统输入）到消息消费者（系统输出）之间的中间商链。6.4.2分分类系系统作为中间商，分类器的条件获得匹配时，并不马上发送消息，而是与其它几个同样获得匹配的分类器竞争(并非只有一个获胜)。为了表示分类器的竞争力，我们可给每个分类器分配一个参数值以表示它的价值，不妨称之为力度（strength）。力度越大的分类器越有竞争性，亦即越有价值。分类器之间的竞争采用竞价体系。每个获得匹配的分类器根据其力度s按某种比例出个价B。一旦该分类器被激活，其力度将被减去B，同时将所出价B付给提供消息的上家。当然若该分类器能进一步激活其它分类器（下家），它也同样能从中得到补偿。6.4.2分分类系系统下面就以前面提到的例子来说明BBA的工作过程。t0t1t2分类器力度消息 出价力度消息出价力度消息出价01#:0000200 2000#0:110020011#:1000200#00:000120018000002002020020020220180110020020180000118环境0011120206.4.2分分类系系统t3t4t5分类器力度消息出价力度消息出价 力度环境回报01#:0000220 00#0:110021811#:10001801000#00:0001162000116220218196146000122021819619650环境2020206.4.2分分类系系统3.遗传算法算法尽管BBA算法提供了一种评价和选取竞争分类器的方法，但还须有一种产生新的更好的分类器的方法，以不断增强分类系统的性能。这种方法就是遗传算法。由于分类器的条件和动作部分都是固定长度的串，应用遗传算法产生新的分类器就很自然了。设条件和动作串的长度均为L，我们可以将条件和动作串的拼接（代表一个分类器），即长度为2L的串作为GA的操作对象个体，而当前分类器的集合作为当前群体,通过GA的三个操作（选择、交换、突变）来产生新的分类器。6.4.2分分类系系统分类系统中的遗传算法与前面讨论的简单遗传算法（SGA）还略有不同，主要表现在：1)群体的变化。在SGA中，由于我们是寻求问题的最优解，只要求群体能收敛于最优解，因此产生的新一代群体将完全取代上一代群体。而在分类器系统中，我们的目的是要发现有更高性能的分类器集合，因而有必要保留在上一代群体中已有较好性能（力度值较大）的分类器，亦即只要用近期发现的新分类器取代上一代群体中性能较差（力度值较小）的分类器即可。6.4.2分分类系系统2)个体的适应度。SGA用面向优化的目标函数来评价个体的适应度，而分类系统则用分类器的力度去表示分类器的适应度。对于用交换或变异操作产生的新分类器，力度初始值可有多种计算方法。一种典型的方法是：如果后代从交换中产生，则将两个父代的力度值各减去1/3，同时将被减值之和作为后代的力度值；如果后代从变异中产生，则将父代的力度值减半，并将被减值作为后代力度值。6.4.2分分类系系统3)突变操作。在SGA中，串的元素是0或1，因而突变操作是在0和1之间转换，而分类器的串是由0,1,#三种元素组成,因而某一元素的突变是等概率地被转换为其它两个元素,即01或#,10或#,#0或16.4.2分分类系系统在分类系统中，GA仅作为系统的一部分功能，且GA的运行穿插在执行系统的循环中。GA的运行时机可以是确定的（即在执行系统运行t次后，调用一次GA运算）或随机的（即执行系统平均运行t次后，有一次GA调用）；也可以是在某些事件发生后再调用GA（如没有分类器可以匹配或系统性能变差）。6.7 数据挖掘数据挖掘数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程。它通常采用机器自动识别的方式，不需要更多的人工干预。可以说数据挖掘就是知识发现技术在数据库领域中的应用，其在一个已知状态的数据集上，通过设置一定的学习算法，发掘出数据间隐含的一些内在规律，即获取（发现）所谓的知识。6.7 数据挖掘数据挖掘数据仓库的实质就是一个数据库，但是它存储的数据与普通数据库中的数据不太一样，它存储的是从常规数据库抽取出的经过加工整理的数据。例如对于商场应用来说，原有数据库中存储的是每一笔交易的数据，而数据仓库则要根据已往的历史记录进行提炼整理，存放的可能是某种产品某月在某地区的特定销量等记录。数据挖掘可以在数据仓库上进行操作，作为基于数据仓库的分析工具。6.7 数据挖掘数据挖掘1、数据挖掘、数据挖掘应用分用分类根据应用需求，实现数据挖掘的模型可大致分为以下几类：1）分类模型：分类模型的主要功能是根据商业数据的属性将数据分类。2）关联模型：关联模型旨在发现数据项间隐含的相关性，通常表示为关联规则集，并设置信任级别来度量关联规则的强度。3）时序模型：时序(Sequence)模型主要用于分析数据仓库中的某类同时间相关的数据，并发现某一时间段内数据间的时序关系。4）聚类模型：聚类模型按照某种相近度量方法，将待分析数据分成互不相交的一些分组，称为聚类。6.7 数据挖掘数据挖掘2、数据挖掘采用的典型方法及工具、数据挖掘采用的典型方法及工具1）神经网络：神经网络建立在有自学习能力的数学模型基础上，可以对大量复杂的数据进行分析，并完成对人脑或其他计算机来说极为复杂的模式抽取及趋势分析。神经网络的典型应用是建立分类模型。2）决策树：决策树是通过一系列规则对数据进行分类的过程。采用决策树，可以将数据的分类规则可视化，其输出结果也容易理解。6.7 数据挖掘数据挖掘3）粗糙集（roughset）技术：粗糙集理论由波兰科（Z.Pawlak）在1982年提出，是一种新的处理含糊性和不确定性的数学工具，在数据挖掘中发挥了重要的作用，主要用于挖掘关联规则。4）联机分析处理：联机分析处理(OnLineAnalyticalProcessing，OLAP)主要通过多维的方式来对数据进行分析、查询和产生报表。它不同于传统的联机事物处理(OnLineTransactionProcessing，OLTP)应用。5）数据可视化(DataVisualization)：数据仓库中包含大量的数据，并且充斥着各种数据模型，将如此大量的数据可视化需要复杂的高性能可视化工具。3 数据挖掘系统结构数据仓库数据仓库数据清理数据清理 数据集成数据集成过滤过滤数据库数据库数据库或数据仓库服务器数据挖掘引擎模式评估图形用户界面 知识库6.7 数据挖掘数据挖掘数据库、数据仓库或其他信息库：是一个或一组数据库、数据仓库、电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。数据库或数据仓库服务器：根据用户的挖掘请求，数据库或数据仓库服务器负责提取相关数据。知识库：是领域知识，用于指导搜索，或评估结果模式的兴趣度。6.7 数据挖掘数据挖掘数据挖掘引擎：数据挖掘系统的基本部分，由一组功能模块组成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。模式评估模块：使用兴趣度量，并与数据挖掘模块交互，以便将搜索聚焦在有趣的模式上，可能使用兴趣度阈值过滤发现的模式。图形用户界面：该模块在用户和数据挖掘系统之间通信，允许用户与系统交互，指定数据挖掘查询或任务，提供信息，帮助搜索聚焦，根据数据挖掘的中间结果进行探索式数据挖掘。6.7 数据挖掘数据挖掘44数据挖掘数据挖掘过过程程数据挖掘是一个人机交互处理过程。该过程需要经历多个步骤，并且很多决策需要由用户提供。从宏观上看，主要经由三个部分组成，即数据整理、数据挖掘和结果的解释评估。4 数据挖掘过程数据挖掘过程数据清理筛选数据清理筛选数据数据目标数据目标数据预处理预处理及变换及变换变换后的数据变换后的数据数据挖掘数据挖掘解释解释/评估评估数据挖掘的步骤1.数据准备：了解KDD应用领域的有关情况。包括熟悉相关的知识背景，搞清用户需求。2.数据选取：数据选取的目的是确定目标数据，根据用户的需要从原始数据库中选取相关数据或样本。在此过程中，将利用一些数据库操作对数据库进行相关处理。3.数据预处理：对步骤2中选出的数据进行再处理，检查数据的完整性及一致性，消除噪声及与数据挖掘无关的冗余数据，根据时间序列和已知的变化情况，利用统计等方法填充丢失的数据。4.数据变换：根据知识发现的任务对经过预处理的数据再处理，主要是通过投影或利用数据库的其它操作减少数据量。5.确定KDD目标：根据用户的要求，确定KDD要发现的知识类型。6.选择算法：根据步骤5确定的任务，选择合适的知识发现算法，包括选取合适的模型和参数。7.数据挖掘：这是整个KDD过程中很重要的一个步骤。运用前面的选择算法，从数据库中提取用户感兴趣的知识，并以一定的方式表示出来。8.模式解释：对在数据挖掘步骤中发现的模式（知识）进行解释。通过机器评估剔除冗余或无关模式，若模式不满足，再返回到前面某些处理步骤中反复提取。9.知识评价：将发现的知识以用户能了解的方式呈现给用户。其中也包括对知识一致性的检查，以确信本次发现的知识不会与以前发现的知识相抵触。