第五 机器学习

第五机器学习第1页，共42页，2023年，2月20日，星期一第五章机器学习第二节归纳学习一、基本含义给定关于某个概念的一系列已知的正例和反例，从中归纳出一个一般的概念描述的过程。基本操作是泛化(Generalization)和特化(Specialization)二、分类1、实例学习也称概念获取，确定概念的一般描述，这个描述应能解释所有给定的正例并排除所有给定的反例。这些正例和反例由信息源提供，是有教师学习。第2页，共42页，2023年，2月20日，星期一第五章机器学习第二节归纳学习二、分类2、观察与发现学习也称描述的泛化，产生能解释所有或大多数观察到的事实的规律和规则。这类学习包括概念聚类、构造分类、发现定理、形成理论等。第3页，共42页，2023年，2月20日，星期一第五章机器学习第二节归纳学习三、归纳学习方法有变型(版本)空间、决策树方法、AQ11算法等。第4页，共42页，2023年，2月20日，星期一第五章机器学习第二节归纳学习四、变型(版本)空间方法(VersionSpace)以整个规则空间为初始的假设规则集合H，依据训练例子中的信息，对集合H进行泛化和特化处理，逐步缩小集合H。Mitchell假定这个空间是一偏序结构，并将单个概念学习定义为在这个空间的搜索。泛化特化更一般更特殊没有描述GS第5页，共42页，2023年，2月20日，星期一第五章机器学习第二节归纳学习五、AQ归纳学习算法生成的选择假设的析取，覆盖全部正例，而不覆盖任何反例。

AQ11算法搜索规则空间，反复应用消除候选元素，得到尽可能一般的规则，可包含多概念学习。注：AQ11的原理是将样本集构成一个逻辑公式。构成的方法是根据决策属性对样本集的划分，所有正样本与所有反样本构成逻辑公式Ep~En，这个逻辑公式就是对正样本集的表示，其中每个样本是“属性—值”对的合取连接式。六、产生与测试方法仅通过正例学习概念，引入“概念窗口”概念。第6页，共42页，2023年，2月20日，星期一第五章机器学习第二节归纳学习七、决策树学习决策树可以用来表示析取概念。

1、CLS学习算法从一个空决策树开始，通过增加决策结点，逐渐精化，直到树正确分类全部训练实例。其缺陷是学习问题不能太大。2、ID3学习算法——Quinlan1979

采用训练实例的子集(即，可选择窗口)，通过属性，使用熵概念，来形成决策树。实质是构造一株熵值下降平均最快的判定树。注：ID3的数学基础是商集。第7页，共42页，2023年，2月20日，星期一第五章机器学习第二节归纳学习七、决策树学习3、ID4学习算法在每个可能的决策树结点创造一系列表。每个表由全部未检测属性值和每个值的正例和反例数组构成。当处理一个新例时，每个属性值的正例和反例递增计量。即，递增概念归纳。4、ID5学习算法

抛弃旧的检测属性下面的子树，从下面选出检测属性形成树。5、C4.5和C5处理连续属性。第8页，共42页，2023年，2月20日，星期一第五章机器学习第二节归纳学习八、归纳学习的计算理论学习算法的样本复杂性和计算复杂性。Gold学习理论和Valiant学习理论。Valiant——关于可学习性的理论：概率地、近似地、正确地可学习的(PACProbably、Approximately、Correct)PAC学习模型。第9页，共42页，2023年，2月20日，星期一第五章机器学习第三节分析学习一、类比学习1、类比——比喻类比是人类重要的认知方法，是经验决策过程中常用的推理方式，是一种允许知识在具有相似性质的领域中进行转换的学习策略。2、类比学习把两个或两类事物或情形进行比较，找出它们在某一抽象层次上的相似关系，并以这种关系为依据，把某一事物或情形的有关知识加以适当整理(或变换)对应到另一事物或情形，从而获得另一事物或情形的知识，称为类比学习。第10页，共42页，2023年，2月20日，星期一第五章机器学习第三节分析学习一、类比学习2、类比学习注：1)类比学习的核心技术是相似性的定义和度量。2)类比有多种形式，如，方法类比、概念类比、图形类比、联想型类比等等。3、类比学习主要步骤a)联想搜索匹配b)检验相似程度c)修正变换求解d)更新知识库第11页，共42页，2023年，2月20日，星期一第五章机器学习第三节分析学习一、类比学习4、类比学习方法a)转换类比b)派生类比c)基于案例的学习第12页，共42页，2023年，2月20日，星期一第五章机器学习第三节分析学习一、类比学习5、转换类比学习系统主要由比较器、知识库、操作模块、解法栈、检验模块组成。6、派生类比将转换类比进行扩充，对过去求解的问题进行完整地派生跟踪。第13页，共42页，2023年，2月20日，星期一第五章机器学习第三节分析学习一、类比学习7、基于案例的学习是基于类比的学习的进一步发展，特别适用于较难发现规律性知识、也不容易找到因果模型的领域。注：1)基于案例的学习所使用的案例库不象规则库那样有知识的不一致问题。2)基于案例的学习从其本性来说就是增量式学习。3)基于案例的学习需要保持和管理一组数量较大的案例。第14页，共42页，2023年，2月20日，星期一第五章机器学习第三节分析学习一、类比学习7、基于案例的学习注：4)基于案例学习的一般过程如下：第15页，共42页，2023年，2月20日，星期一输入检索信息源范例分析模型范例检索类比映射类比转换类比验证解释过程检索方法映射方法转换规则源范例库范例保存范例修补修改规则新解新范例失败描述或部分解第16页，共42页，2023年，2月20日，星期一第五章机器学习第三节分析学习二、基于解释的学习(解释学习)

给定一个具有丰富领域知识的知识库，给定一个目标概念G，输入一个实例e，使用知识库中的知识或在专家的帮助下，证明e是G的一个实例(即解释e是G的一个实例)，对获得的解释进行推广，得到一个更一般的解题过程(泛化)，把通过泛化得到的知识加进知识库中。注：解释可使用目标回归方法和基于解释的特化(EBS)。第17页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习一、基本原理1、竞争机制将竞争机制引进系统，以便不断改进和完善系统的工作性能，使系统具有自适应性。注：1)若一系统在工作过程中能够根据外界的反馈信息对自己的工作方式进行调节，甚至对自己的工作机制重新组织(自组织)，使整个系统工作得更好，则称该系统具有自适应性。这种调整和适应的过程，可以看作是系统的学习过程。第18页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习一、基本原理1、竞争机制注：2)在自适应系统中引进竞争机制，就是将达尔文发现的物种竞争、适者生存的生物进化规律运用到系统的演变中来，并把它们作为一种学习的手段加以运用，以便淘汰不适用的知识，增加有用的知识。第19页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习一、基本原理2、知识更新的随机性系统知识的演变是不确定的，方法是作各种随机的改动，然后将改动的结果应用于解题，保留成功的，抛弃失败的。注：1)这相当于在一个庞大的解空间中作随机搜索，在使用适当的启发式原则的前提下，搜索结果将收敛于一个较好的解。第20页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习一、基本原理2、知识更新的随机性注：2)遗传算法采用的启发式原则主要是爬山法。从一个初始知识库出发，随机地选择能够改进知识库性能的某种变动，这相当于向上的高处爬了一步，结果得到一个新的知识库，然后，再以此知识库为出发点，再作改动，再向上爬一步，这样不断地改进。其中所使用的改进手段称为遗传算子。3)统计抽样是遗传算法的支柱之一。第21页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习二、基本遗传算法1、给定一个初始知识库2、计算每个知识单元u对外界环境的适应程度f(u)。注：若知识单元是规则，则称为规则强度。3、根据各知识单元对环境的适应度f(u)，计算它们被选中作物种演变的概率值4、根据概率值选出一批知识单元5、运用各种遗传算子于被选中的知识单元，产生一批新的知识单元，即它们的后代6、用这批后代去代替知识库中原有的适应度最低的那些知识单元，实现知识更新第22页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习二、基本遗传算法7、将新知识库作用于外界环境，解决新的问题，获得新的反馈信息，重新计算各知识单元对环境的适应度，转3注：1)为了便于大规模并行处理，使形式简单、规范化，在遗传算法中通常采用一种称为分类器的语言。该语言是一个三元组(A,#,k)，其中A是字母表，#是一个变量符，k是一个正整数，k>=1。L中的每个句子是一个长度为k的符号串，其中每个符号属于集合A{#}第23页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习二、基本遗传算法注：2)一个规则型分类器L是一个四元组(A,#,k1,k2)，L中的每个句子是一个长度为k1+k2的符号串，前面k1个符号组成的符号串称为该句子的条件部分，后面k1个符号组成的符号串称为该句子的动作部分。此时，句子也称为规则。3)分类器语言的每个句子相当于一个知识单元。第24页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习三、遗传算子1、杂交2、变异C(a1,a2)={a1’,a2’}M(a1)=a1’第25页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习三、遗传算子3、逆转i(a1)=a1’第26页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习四、水桶排队算法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是一个常数,C<<1)

z(a)=第27页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习四、水桶排队算法2、把收到的外部消息记录在消息表上3、把消息表上的全部消息和知识库中所有规则的条件部分匹配4、令匹配成功的规则集为S，若S为空集，则转95、设当前时刻为t，计算每个规则在时刻t的竞争力，根据竞争力算出这些规则被选中的概率，根据这些概率选出一批规则作为获胜者，它们将自己的动作部分作为新消息存于缓冲区中6、若缓冲区中含有矛盾消息，则继续使用竞争的办法消除矛盾中较弱的一方第28页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习四、水桶排队算法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的个数)第29页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习四、水桶排队算法9、调用遗传学习算法改进知识库，得到一个新的知识库10、输出界面向外部环境输出消息表中的消息，t:=t+1，转1注：水桶排队算法可作为信任分配机制。第30页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习五、具体遗传算法1、给定一个初始知识库2、利用水桶排队算法计算知识库中每个规则ai的强度q(ai,t)及标准强度a(ai,t)/q(t)，其中t表示当前时刻(第t个循环)，q(t)是库中全体规则强度的平均值3、根据各规则的标准强度，计算它们被选中作物种演变的概率值4、根据概率值从知识库中选出2n条规则，并构造它们的复制品，其中n应<<规则的总数第31页，共42页，2023年，2月20日，星期一第五章机器学习第四节遗传式学习五、具体遗传算法5、把2n条规则随机地组成n对，对每一对规则使用杂交算子或其它遗传算子，得到n对新的规则，每一条新规则的强度是它们的父母规则强度的平均值6、用这批新规则取代知识库中原来强度最低的2n条规则，t:=t+1#第32页，共42页，2023年，2月20日，星期一第五章机器学习第五节神经网络学习一、感知机学习学习权进行权值调整二、Hebb学习法则根据输出和教员的指示调整权值的增长幅度三、广义Hebb学习规则——学习规则注：在学习规则中，权值调整方向是使各权值的误差平方和变得最小的方向(最小均方差)。四、多层网络的学习使用反传算法五、Hopfield模型网络使用模拟退火方法。第33页，共42页，2023年，2月20日，星期一第五章机器学习第六节数据挖掘与知识发现一、问题的提出1、网络技术促进信息技术的发展

a)信息过量，难以消化b)信息真假，难以辨识c)信息安全，难以保证d)信息形式不一致，难以统一处理2、数据海洋——数据分析被数据淹没，人们却饥饿于知识3、数据库、人工智能、数理统计、可视化技术、信息基础设施提供必有条件DMKD成为可能4、首次提出IJCAI’89(第十一届)第34页，共42页，2023年，2月20日，星期一第五章机器学习第六节数据挖掘与知识发现二、基本概念从大量的、不完全的、有噪声的、模糊的数据中，提取隐含在其中的、人们事先不知道的、但又有潜在有用价值的信息和知识过程。注：1)数据源是真实的、大量的、含噪声

2)数据源支持相应的发现，但发现的知识是隐含的、事先不知道的；是发现，不是证明

3)发现的是人们感兴趣的知识，且一般是从大量的数据中提炼出抽象的知识

4)发现的知识可接受、可理解、可运用

5)不要求发现通用知识，仅支持特定的问题

6)需综合运用统计学、粗糙集、模糊数学、机器学习和专家系统、神经网络、可视化等多学科的手段与方法第35页，共42页，2023年，2月20日，星期一第五章机器学习第六节数据挖掘与知识发现三、最常发现的知识1、广义型知识(Generalization)根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观和宏观的知识2、分类型知识(Classification&Clustering)反映同类事物共同性质的特征型知识和不同事物之间差异型特征知识3、关联型知识(Association)反映一个事件和其它事件之间依赖或关联的知识4、预测型知识(Prediction)通过时间序列型数据，由历史和当前的情况去预测未来的情况第36页，共42页，2023年，2月20日，星期一第五章机器学习第六节数据挖掘与知识发现四、最有影响的发现算法1、概念树提升算法SimonFraster大学J.Han2、关联算法IBMRAgrawal3、分类算法C5/C4.5

Quinlan4、遗传算法

E.Godman第37页，共42页，2023年，2月20日，星期一第五章机器学习第六节数据挖掘与知识发现五、知识发现过程1、数据准备数据选取、数据预处理、数据变换2、数据挖掘阶段3、结果解释和评价六、活跃的应用领域1、市场营销2、金融与银行业3、电信、交通和保险业4、政府和防卫部分5、商务智能(业务智能，BI)将数据变为知识，并将知识变为商业效益第38页，共42页，2023年，2月20日，星期一第五章机器学习第六节数据挖掘与知识发