【教学课件】第五章机器学习.ppt

《【教学课件】第五章机器学习.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第五章机器学习.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 机器学习第一节 引言一、学习 如果一个系统能够执行某个过程而改进它的性能，这就是学习。学习是获取知识、积累经验、改进性能、发现规律、适应环境的过程。其基本机制是设法将在一种情形下成功的表现行为转移到另一类似的新情形中去。二、学习分类1、基于归纳的学习（归纳学习）2、基于分析的学习（分析学习）3、基于遗传原理的学习（遗传学习）4、基于海量并行(神经网络)的学习（神经网络学习）第五章 机器学习第二节 归纳学习一、基本含义 给定关于某个概念的一系列已知的正例和反例，从中归纳出一个一般的概念描述的过程。基本操作是泛化(Generalization)和特化(Specialization)二、分类

2、1、实例学习 也称概念获取，确定概念的一般描述，这个描述应能解释所有给定的正例并排除所有给定的反例。这些正例和反例由信息源提供，是有教师学习。第五章 机器学习第二节 归纳学习二、分类2、观察与发现学习 也称描述的泛化，产生能解释所有或大多数观察到的事实的规律和规则。这类学习包括概念聚类、构造分类、发现定理、形成理论等。第五章 机器学习第二节 归纳学习三、归纳学习方法有变型(版本)空间、决策树方法、AQ11算法等。第五章 机器学习第二节 归纳学习四、变型(版本)空间方法(Version Space)以整个规则空间为初始的假设规则集合H，依据训练例子中的信息，对集合H进行泛化和特化处理，逐步缩小集

3、合H。Mitchell假定这个空间是一偏序结构，并将单个概念学习定义为在这个空间的搜索。泛化特化更一般更特殊没有描述GS第五章 机器学习第二节 归纳学习五、AQ归纳学习算法 生成的选择假设的析取，覆盖全部正例，而不覆盖任何反例。AQ11算法搜索规则空间，反复应用消除候选元素，得到尽可能一般的规则，可包含多概念学习。注：AQ11的原理是将样本集构成一个逻辑公式。构成的方法是根据决策属性对样本集的划分，所有正样本与所有反样本构成逻辑公式EpEn，这个逻辑公式就是对正样本集的表示，其中每个样本是“属性值”对的合取连接式。六、产生与测试方法 仅通过正例学习概念，引入“概念窗口”概念。第五章 机器学习第

4、二节 归纳学习七、决策树学习 决策树可以用来表示析取概念。1、CLS学习算法 从一个空决策树开始，通过增加决策结点，逐渐精化，直到树正确分类全部训练实例。其缺陷是学习问题不能太大。2、ID3学习算法 Quinlan 1979 采用训练实例的子集(即，可选择窗口)，通过属性，使用熵概念，来形成决策树。实质是构造一株熵值下降平均最快的判定树。注：ID3的数学基础是商集。第五章 机器学习第二节 归纳学习七、决策树学习3、ID4学习算法 在每个可能的决策树结点创造一系列表。每个表由全部未检测属性值和每个值的正例和反例数组构成。当处理一个新例时，每个属性值的正例和反例递增计量。即，递增概念归纳。4、ID

5、5学习算法 抛弃旧的检测属性下面的子树，从下面选出检测属性形成树。5、C4.5和C5 处理连续属性。第五章 机器学习第二节 归纳学习八、归纳学习的计算理论 学习算法的样本复杂性和计算复杂性。Gold学习理论和Valiant学习理论。Valiant 关于可学习性的理论：概率地、近似地、正确地可学习的(PAC Probably、Approximately、Correct)PAC学习模型。第五章 机器学习第三节 分析学习一、类比学习1、类比 比喻 类比是人类重要的认知方法，是经验决策过程中常用的推理方式，是一种允许知识在具有相似性质的领域中进行转换的学习策略。2、类比学习 把两个或两类事物或情形进行

6、比较，找出它们在某一抽象层次上的相似关系，并以这种关系为依据，把某一事物或情形的有关知识加以适当整理(或变换)对应到另一事物或情形，从而获得另一事物或情形的知识，称为类比学习。第五章 机器学习第三节 分析学习一、类比学习2、类比学习 注：1)类比学习的核心技术是相似性的定义和度量。2)类比有多种形式，如，方法类比、概念类比、图形类比、联想型类比等等。3、类比学习主要步骤a)联想搜索匹配b)检验相似程度c)修正变换求解d)更新知识库第五章 机器学习第三节 分析学习一、类比学习4、类比学习方法a)转换类比b)派生类比c)基于案例的学习第五章 机器学习第三节 分析学习一、类比学习5、转换类比学习系统

7、 主要由比较器、知识库、操作模块、解法栈、检验模块组成。6、派生类比 将转换类比进行扩充，对过去求解的问题进行完整地派生跟踪。第五章 机器学习第三节 分析学习一、类比学习7、基于案例的学习 是基于类比的学习的进一步发展，特别适用于较难发现规律性知识、也不容易找到因果模型的领域。注：1)基于案例的学习所使用的案例库不象规则库那样有知识的不一致问题。2)基于案例的学习从其本性来说就是增量式学习。3)基于案例的学习需要保持和管理一组数量较大的案例。第五章 机器学习第三节 分析学习一、类比学习7、基于案例的学习注：4)基于案例学习的一般过程如下：输入检索信息源范例分析模型范例检索类比映射类比转换类比验

8、证解释过程检索方法映射方法转换规则源范例库范例保存范例修补修改规则新解新范例失败描述或部分解第五章 机器学习第三节 分析学习二、基于解释的学习(解释学习)给定一个具有丰富领域知识的知识库，给定一个目标概念G，输入一个实例e，使用知识库中的知识或在专家的帮助下，证明e是G的一个实例(即解释e是G的一个实例)，对获得的解释进行推广，得到一个更一般的解题过程(泛化)，把通过泛化得到的知识加进知识库中。注：解释可使用目标回归方法和基于解释的特化(EBS)。第五章 机器学习第四节 遗传式学习一、基本原理1、竞争机制 将竞争机制引进系统，以便不断改进和完善系统的工作性能，使系统具有自适应性。注：1)若一系

9、统在工作过程中能够根据外界的反馈信息对自己的工作方式进行调节，甚至对自己的工作机制重新组织(自组织)，使整个系统工作得更好，则称该系统具有自适应性。这种调整和适应的过程，可以看作是系统的学习过程。第五章 机器学习第四节 遗传式学习一、基本原理1、竞争机制注：2)在自适应系统中引进竞争机制，就是将达尔文发现的物种竞争、适者生存的生物进化规律运用到系统的演变中来，并把它们作为一种学习的手段加以运用，以便淘汰不适用的知识，增加有用的知识。第五章 机器学习第四节 遗传式学习一、基本原理2、知识更新的随机性 系统知识的演变是不确定的，方法是作各种随机的改动，然后将改动的结果应用于解题，保留成功的，抛弃失

10、败的。注：1)这相当于在一个庞大的解空间中作随机搜索，在使用适当的启发式原则的前提下，搜索结果将收敛于一个较好的解。第五章 机器学习第四节 遗传式学习一、基本原理2、知识更新的随机性注：2)遗传算法采用的启发式原则主要是爬山法。从一个初始知识库出发，随机地选择能够改进知识库性能的某种变动，这相当于向上的高处爬了一步，结果得到一个新的知识库，然后，再以此知识库为出发点，再作改动，再向上爬一步，这样不断地改进。其中所使用的改进手段称为遗传算子。3)统计抽样是遗传算法的支柱之一。第五章 机器学习第四节 遗传式学习二、基本遗传算法1、给定一个初始知识库2、计算每个知识单元u对外界环境的适应程度f(u)

11、。注：若知识单元是规则，则称为规则强度。3、根据各知识单元对环境的适应度f(u)，计算它们被选中作物种演变的概率值4、根据概率值选出一批知识单元5、运用各种遗传算子于被选中的知识单元，产生一批新的知识单元，即它们的后代6、用这批后代去代替知识库中原有的适应度最低的那些知识单元，实现知识更新第五章 机器学习第四节 遗传式学习二、基本遗传算法7、将新知识库作用于外界环境，解决新的问题，获得新的反馈信息，重新计算各知识单元对环境的适应度，转3注：1)为了便于大规模并行处理，使形式简单、规范化，在遗传算法中通常采用一种称为分类器的语言。该语言是一个三元组(A,#,k)，其中A是字母表，#是一个变量符，

12、k是一个正整数，k=1。L中的每个句子是一个长度为k的符号串，其中每个符号属于集合A#第五章 机器学习第四节 遗传式学习二、基本遗传算法注：2)一个规则型分类器L是一个四元组(A,#,k1,k2)，L中的每个句子是一个长度为k1+k2的符号串，前面k1个符号组成的符号串称为该句子的条件部分，后面k1个符号组成的符号串称为该句子的动作部分。此时，句子也称为规则。3)分类器语言的每个句子相当于一个知识单元。第五章 机器学习第四节 遗传式学习三、遗传算子1、杂交2、变异C(a1,a2)=a1,a2M(a1)=a1第五章 机器学习第四节 遗传式学习三、遗传算子3、逆转i(a1)=a1第五章 机器学习第

13、四节 遗传式学习四、水桶排队算法1、输入界面从外部环境接受消息，如果其中包含对上一步中某个输出消息的肯定，且此输出消息的生产者是规则a，则令 q(a,t):=q(a,t)+B(a,t)，其中，q(a,t)是规则a在时刻t的强度；B(a,t)=C*z(a)*q(a,t)(C是一个常数,C1)z(a)=第五章 机器学习第四节 遗传式学习四、水桶排队算法2、把收到的外部消息记录在消息表上3、把消息表上的全部消息和知识库中所有规则的条件部分匹配4、令匹配成功的规则集为S，若S为空集，则转95、设当前时刻为t，计算每个规则在时刻t的竞争力，根据竞争力算出这些规则被选中的概率，根据这些概率选出一批规则作为

14、获胜者，它们将自己的动作部分作为新消息存于缓冲区中6、若缓冲区中含有矛盾消息，则继续使用竞争的办法消除矛盾中较弱的一方第五章 机器学习第四节 遗传式学习四、水桶排队算法7、用缓冲区中剩余的消息代替消息表上原有的消息8、若经过4、5、6各步后缓冲区中留存的各个消息的生产者是规则组ai，则对每个ai作如下操作：(1)q(ai,t+1):=q(ai,t)-B(ai,t)(2)对任何规则bj，若bj在上一步中产生的消息使ai在这一步匹配成功，则令q(bj,t+1):=q(bj,t)+B(ai,t)/n(n是满足上述条件的bj的个数)第五章 机器学习第四节 遗传式学习四、水桶排队算法9、调用遗传学习算法

15、改进知识库，得到一个新的知识库10、输出界面向外部环境输出消息表中的消息，t:=t+1，转1注：水桶排队算法可作为信任分配机制。第五章 机器学习第四节 遗传式学习五、具体遗传算法1、给定一个初始知识库2、利用水桶排队算法计算知识库中每个规则ai的强度q(ai,t)及标准强度a(ai,t)/q(t)，其中t表示当前时刻(第t个循环)，q(t)是库中全体规则强度的平均值3、根据各规则的标准强度，计算它们被选中作物种演变的概率值4、根据概率值从知识库中选出2n条规则，并构造它们的复制品，其中n应规则的总数第五章 机器学习第四节 遗传式学习五、具体遗传算法5、把2n条规则随机地组成n对，对每一对规则使

16、用杂交算子或其它遗传算子，得到n对新的规则，每一条新规则的强度是它们的父母规则强度的平均值6、用这批新规则取代知识库中原来强度最低的2n条规则，t:=t+1#第五章 机器学习第五节 神经网络学习一、感知机学习 学习权 进行权值调整二、Hebb学习法则 根据输出和教员的指示调整权值的增长幅度三、广义Hebb学习规则学习规则注：在学习规则中，权值调整方向是使各权值的误差平方和变得最小的方向(最小均方差)。四、多层网络的学习 使用反传算法五、Hopfield模型网络使用模拟退火方法。第五章 机器学习第六节 数据挖掘与知识发现一、问题的提出1、网络技术促进信息技术的发展 a)信息过量，难以消化 b)信

17、息真假，难以辨识 c)信息安全，难以保证 d)信息形式不一致，难以统一处理2、数据海洋数据分析 被数据淹没，人们却饥饿于知识3、数据库、人工智能、数理统计、可视化技术、信息基础设施提供必有条件 DMKD成为可能4、首次提出 IJCAI89(第十一届)第五章 机器学习第六节 数据挖掘与知识发现二、基本概念 从大量的、不完全的、有噪声的、模糊的数据中，提取隐含在其中的、人们事先不知道的、但又有潜在有用价值的信息和知识过程。注：1)数据源是真实的、大量的、含噪声 2)数据源支持相应的发现，但发现的知识是隐含的、事先不知道的；是发现，不是证明 3)发现的是人们感兴趣的知识，且一般是从大量的数据中提炼出

18、抽象的知识 4)发现的知识可接受、可理解、可运用 5)不要求发现通用知识，仅支持特定的问题 6)需综合运用统计学、粗糙集、模糊数学、机器学习和专家系统、神经网络、可视化等多学科的手段与方法第五章 机器学习第六节 数据挖掘与知识发现三、最常发现的知识1、广义型知识(Generalization)根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观和宏观的知识2、分类型知识(Classification&Clustering)反映同类事物共同性质的特征型知识和不同事物之间差异型特征知识3、关联型知识(Association)反映一个事件和其它事件之间依赖或关联的知识4、预测型知识(P

19、rediction)通过时间序列型数据，由历史和当前的情况去预测未来的情况第五章 机器学习第六节 数据挖掘与知识发现四、最有影响的发现算法1、概念树提升算法 Simon Fraster大学J.Han2、关联算法 IBM R Agrawal3、分类算法C5/C4.5 Quinlan4、遗传算法 E.Godman第五章 机器学习第六节 数据挖掘与知识发现五、知识发现过程1、数据准备 数据选取、数据预处理、数据变换2、数据挖掘阶段3、结果解释和评价六、活跃的应用领域1、市场营销2、金融与银行业3、电信、交通和保险业4、政府和防卫部分5、商务智能(业务智能，BI)将数据变为知识，并将知识变为商业效益第

20、五章 机器学习第六节 数据挖掘与知识发现七、21世纪初DMKD研究课题1、定性值和定量值之间的转换 a)自然语言在人类思维中具有不可替代性 b)人工智能的最基本问题知识表示 c)Fuzzy Sets,Rough Sets d)从定性到定量的综合集成2、数据仓库技术 数据仓库是面向主题的、集成的、与时间关联的、相对稳定的、支持决策制定过程的数据集合。它从大量的事务数据库中抽取数据，通过转换形成统一的格式。第五章 机器学习第六节 数据挖掘与知识发现七、21世纪初DMKD研究课题3、数据立方体代数 把多维数据模式中的某一属性作为观察对象，称为维(Dimension)。维可以有层次结构。将反映对象特征

21、的属性称为指标(measure)，这样的结构称为数据立方体(Data Cube)。数据立方体的实体化是指预先执行某些计算，存储计算结果，在数据分析时直接使用。4、Text Mining5、Web Mining6、Data Mining for Audio&Video第五章 机器学习第六节 数据挖掘与知识发现七、21世纪初DMKD研究课题7、发现语言的形式化描述8、可视化、交互式发现9、发现知识的维护更新思考题学习的基本机制和主要作用是什么？试举例说明。归纳学习的基本思想是什么？如何在特定的应用领域应用归纳学习方法？如何评价归纳学习效果？类比学习的基本思想是什么？如何在特定的应用领域应用类比学习方法？遗传学习的基本机制是什么？应用遗传学习方法的关键点有哪些？为什么？你认为“数据挖掘与知识发现”方法是一种学习方法吗？为什么？