机器学习与知识发现

第四篇学习与发现学习是系统积累经验或运用规律指导自己的行为或改进自身性能的过程。发现是系统从接收的信息中发现规律的过程。人工智能中的机器学习(machinelearning)主要指机器对自身行为的修正或性能的改善〔类似于人类的技能训练和对环境的适应〕和机器对客观规律的发现〔类似与人类的科学发现〕。1/18/20241机器学习主要分为符号学习连接学习统计学习机器对于客观规律的发现，也称为知识发现(KnowledgeDiscovery,KD)。数据挖掘(DataMining)是知识发现的一个重要研究和应用领域。目前的机器学习主要是机器的直接发现性学习，而间接性继承机器学习需要“理解〞为根底。1/18/20242

第9章机器学习与知识发现

9.1机器学习概述

9.2符号学习

9.3神经网络学习

9.4知识发现与数据挖掘1/18/202439.1机器学习概述9.1.1机器学习的概念9.1.2机器学习的原理9.1.3机器学习的分类1/18/202449.1.1机器学习的概念心理学中对学习的解释是：学习是指〔人或动物〕依靠经验的获得而使行为持久变化的过程。Simon认为：如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。Minsky认为：学习是在人们头脑中〔心理内部〕进行有用的变化。TomM.Mitchell在《机器学习》一书中对学习的定义是：对于某类任务T和性能度P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么，我们称这个计算机程序从经验E中学习。当前关于机器学习的许多文献中也大都认为：学习是系统积累经验以改善其自身性能的过程。1/18/20245总之：①学习与经验有关；②学习可以改善系统性能；③学习是一个有反响的信息处理与控制过程。因为经验是在系统与环境的交互过程中产生的，而经验中应该包含系统输入、响应和效果等信息。因此经验的积累、性能的完善正是通过重复这一过程而实现的。1/18/202469.1.2机器学习的原理图9-1机器学习原理1②③①记忆学习、基于范例的学习希望能在积累的经验中发现规律〔知识〕，然后利用知识来指导行为经验积累过程缓慢经验不可靠1/18/20247图9-2机器学习原理2

1/18/20248图9-3机器学习原理31/18/20249图9-4机器学习原理41/18/202410图9-5机器学习原理51/18/2024119.1.3机器学习的分类1.基于学习策略的分类〔1〕模拟人脑的机器学习●符号学习：模拟人脑的宏观心理级学习过程，以认知心理学原理为根底，以符号数据为输入，以符号运算为方法，用推理过程在图或状态空间中搜索，学习的目标为概念或规那么等。符号学习的典型方法有：记忆学习、例如学习、演绎学习、类比学习、解释学习等。●神经网络学习〔或连接学习〕：模拟人脑的微观生理级学习过程，以脑和神经科学原理为根底，以人工神经网络为函数结构模型，以数值数据为输入，以数值运算为方法，用迭代过程在系数向量空间中搜索，学习的目标为函数。典型的连接学习有权值修正学习、拓扑结构学习。1/18/202412〔2〕直接采用数学方法的机器学习●主要有统计机器学习〔贝叶斯学习、贝叶斯网络学习、几何分类学习、支持向量机SVM〕。2.基于学习方法的分类〔1〕归纳学习●符号归纳学习：典型的符号归纳学习有例如学习，决策树学习。●函数归纳学习〔发现学习〕：典型的函数归纳学习有神经网络学习、例如学习，发现学习，统计学习。〔2〕演绎学习〔3〕类比学习：典型的类比学习有案例〔范例〕学习。〔4〕分析学习：典型的分析学习有案例〔范例〕学习、解释学习。1/18/2024133.基于学习方式的分类〔1〕有导师学习〔监督学习〕：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。〔2〕无导师学习〔非监督学习〕：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。〔3〕强化学习〔增强学习〕：以环境反响〔奖/惩信号〕作为输入，以统计和动态规划技术为指导的一种学习方法。1/18/2024144.基于数据形式的分类〔1〕结构化学习：以结构化数据为输入，以数值计算或符号推演为方法。典型的结构化学习有神经网络学习、统计学习、决策树学习、规那么学习。〔2〕非结构化学习：以非结构化数据为输入，典型的非结构化学习有类比学习、案例学习、解释学习、文本挖掘、图像挖掘、Web挖掘等。1/18/2024155.基于学习目标的分类〔1〕概念学习：即学习的目标和结果为概念，或者说是为了获得概念的一种学习。典型的概念学习有例如学习。〔2〕规那么学习：即学习的目标和结果为规那么，或者说是为了获得规那么的一种学习。典型的规那么学习有决策树学习。〔3〕函数学习：即学习的目标和结果为规那么，或者说是为了获得函数的一种学习。典型的函数学习有神经网络学习。〔4〕类别学习：即学习的目标和结果为对象类，或者说是为了获得类别的一种学习。典型的类别学习有聚类分析。〔5〕贝叶斯网络学习：即学习的目标和结果是贝叶斯网络，或者说是为了获得贝叶斯网络的一种学习。其又可分为结构学习和参数学习。1/18/2024169.2符号学习9.2.1记忆学习9.2.2例如学习9.2.3决策树学习9.2.4演绎学习9.2.5类比学习1/18/2024179.2.1记忆学习

记忆学习又称死记硬背学习或机械学习，这种学习方法不要求系统具有对复杂问题求解的能力，也就是没有推理能力，系统的学习方法就是直接记录与问题有关的信息，然后检索并利用这些存储的信息来解决问题。

AAvS1/18/202418记忆学习是基于记忆和检索的方法，学习方法简单,但学习系统需要几种能力：(1)能实现有组织的存储信息。(2)能进行信息综合。(3)能控制检索方向。当存储对象愈多时,其中可能有多个对象与给定的状态有关，这样就要求程序能从有关的存储对象中进行选择，以便把注意力集中到有希望的方向上来。1/18/2024199.2.2例如学习例如学习也称实例学习,它是一种归纳学习。例如学习是从假设干实例(包括正例和反例)中归纳出一般概念或规那么的学习方法。图9-6第一个拱桥的语义网络图9-7第二个拱桥的语义网络1/18/202420图9-8学习程序归纳出的语义网络图9-9拱桥概念的语义网络1/18/202421例9.1假设例如空间中有桥牌中"同花"概念的两个例如:例如1：花色(c1，梅花)∧花色(c2，梅花)∧花色(c3，梅花)∧花色(c4，梅花)→同花(c1，c2，c3，c4)例如2：花色(c1，红桃)∧花色(c2，红桃)∧花色(c3，红桃)∧花色(c4，红桃)→同花(c1，c2，c3，c4)关于同花的一般性规那么:花色(c1，x)∧花色(c2，x)∧花色(c3，x)∧花色(c4，x)→同花(c1，c2，c3，c4)1/18/202422对于这个问题可采用通常的曲线拟合技术，归纳出规那么：(x，y，2x+3y+1)即 z＝2x＋3y＋1例9.2假设例如空间存放有如下的三个例如：例如1：(0，2，7)例如2：(6，-1，10)例如3：(-1，-5，-10)这是三个3维向量，表示空间中的三个点。现要求求出过这三点的曲线。1/18/2024239.2.3决策树学习

1．什么是决策树

2.怎样学习决策树

3.ID3算法

1/18/2024241．什么是决策树决策树(decisiontree)也称判定树，它是由对象的假设干属性、属性值和有关决策组成的一棵树。其中的节点为属性〔一般为语言变量〕，分枝〔边〕为相应的属性值〔一般为语言值〕。从同一节点出发的各个分枝之间是逻辑“或〞关系；根节点为对象的某一个属性；从根节点到每一个叶子节点的所有节点和边，按顺序串连成一条分枝路径，位于同一条分枝路径上的各个“属性-值〞对之间是逻辑“与〞关系，叶子节点为这个与关系的对应结果，即决策。1/18/202425图9-10决策树示意图

规那么：A=a1且B=b1那么d11/18/202426例9.3以下图所示是机场指挥台关于飞机起飞的简单决策树。1/18/202427例9.4以下图是一个描述“兔子〞概念的决策树。1/18/2024282.怎样学习决策树决策树学习首先要有一个实例集。对实例集的要求：实例集中的实例都含有假设干“属性-值〞对和一个相应的决策、结论或结果。一个实例集中的实例要求是相容的，即相同的前提不能有不同的结论。对实例集中的结论不能完全相同也不能完全不同。否那么该实例集无学习意义。1/18/202429决策树学习的根本方法和步骤：首先，选取一个属性，按这个属性的不同取值对实例集进行分类；并以该属性作为根节点，以这个属性的诸取值作为根节点的分枝，进行画树。然后，考察所得的每一个子类，看其中的实例的结论是否完全相同。如果完全相同，那么以这个相同的结论作为相应分枝路径末端的叶子节点；否那么，选取一个非父节点的属性，按这个属性的不同取值对该子集进行分类，并以该属性作为节点，以这个属性的诸取值作为节点的分枝，继续进行画树。如此继续，直到所分的子集全都满足：实例结论完全相同，而得到所有的叶子节点为止。1/18/202430●决策树学习举例设表9.1所示的是某保险公司的汽车驾驶保险类别划分的局部事例。我们将这张表作为一个实例集，用决策树学习来归纳该保险公司的汽车驾驶保险类别划分规那么。1/18/202431表9.1汽车驾驶保险类别划分实例集

1/18/202432将实例集简记为S={(1,C),(2,C),(3,C),(4,B),(5,A),(6,A),(7,C),(8,B),(9,A),(10,A),(11,B),(12,B)}其中每个元组表示一个实例，前面的数字为实例序号，后面的字母为实例的决策项保险类别。用“小〞、“中〞、“大〞分别代表“＜21〞、“≥21且≤25〞、“＞25〞这三个年龄段。1/18/202433对于S，我们按属性“性别〞的不同取值将其分类。由表9.1可见，这时S应被分类为两个子集：S1={(3,C),(4,B),(7,C),(8,B),(11,B),(12,B)}S2={(1,C),(2,C),(5,A),(6,A),(9,A),(10,A)}于是，我们得到以性别作为根节点的局部决策树〔见以下图〕。1/18/202434

决策树生成过程

1/18/202435

决策树生成过程

1/18/202436

决策树生成过程

1/18/202437最后生成的决策树

1/18/202438由决策树所得的规那么集：①女性且年龄在25岁以上，那么给予A类保险；②女性且年龄在21岁到25岁之间，那么给予A类保险；③女性且年龄在21岁以下，那么给予C类保险；④男性且年龄在25岁以上，那么给予B类保险；⑤男性且年龄在21岁到25岁之间且未婚，那么给予C类保险；⑥男性且年龄在21岁到25岁之间且已婚，那么给予B类保险；⑦男性且年龄在21岁以下且未婚，那么给予C类保险；⑧男性且年龄在21岁以下且已婚，那么给予B类保险。1/18/2024393.ID3算法ID3算法是一个经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的根本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变成最小的属性，以构造一棵熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。1/18/202440〔1〕信息熵和条件熵设S是一个实例集(S也可以是子实例集),A为S中实例的一个属性。H(S)和H(S|A)分别称为实例集S的信息熵和条件熵,其计算公式如下:其中,μi(i=1,2,…,n)为S中各实例所有可能的结论；lb即log2。其中,ak(k=1,2,…,m)为属性A的取值,Sak为按属性A对实例集S进行分类时所得诸子类中与属性值ak对应的那个子类。1/18/202441〔2〕基于条件熵的属性选择按性别划分,实例集S被分为两个子类:S男={(3,C),(4,B),(7,C),(8,B),(11,B),(12,B)}S女

={(1,C),(2,C),(5,A),(6,A),(9,A),(10,A)}从而,对子集S男而言,对子集S女而言,1/18/202442于是,由公式(9-1)有:1/18/202443又

1/18/202444将以上3式代入公式(9-2)得:用同样的方法可求得:可见,条件熵H(S|性别)为最小,所以,应取“性别〞这一属性对实例集进行分类,即以“性别〞作为决策树的根节点。1/18/202445〔3〕决策树学习的开展继ID3算法之后，1986、1988年相继提出ID4和ID5算法。1993年Quinlan那么进一步将ID3开展为C4.5算法。还有著名的决策树学习算法CART〔ClassificationandRegressionTrees〕。多变量决策树算法GA-NN-C4.5算法SVM决策树算法1/18/202446

9.3神经网络学习9.3.1生物神经元9.3.2人工神经元9.3.3神经网络9.3.4神经网络学习9.3.5BP网络及其学习举例1/18/202447生物神经元

生物神经元的根本结构1/18/202448人工神经元

人工神经元结构模型人工神经元的输入、输出关系可描述为：

1/18/202449神经元特性函数

1.阈值型2.S型

3.分段线性型

1/18/202450神经元特性函数1/18/2024519.3.3神经网络1.分层前向网络2.反响前向网络3.互连前向网络4.广泛互连网络神经网络结构模型1/18/202452神经网络至少可以实现如下功能：——数学上的映射逼近——数据聚类、压缩通过自组织方式对所选输入模式聚类——优化计算和组合优化问题求解——模式分类——概率密度函数的估计1/18/202453神经网络学习学习〔训练〕是神经网络的重要特征之一。神经网络能够通过学习，改变其内部状态，使输入-输出呈现某种规律性。网络学习一般是利用一组称为样本的数据，作为网络的输入〔和输出〕，网络按照一定的训练规那么〔又称学习规那么或学习算法〕自动调节神经元之间的连接强度或拓扑结构，当网络的实际输出满足期望的要求，或者趋于稳定时，那么认为学习成功。学习规那么权值修正学派相关规那么〔Hebb规那么〕误差修正规那么〔δ学习规那么〕结构修正学派1/18/202454Hebb规那么：如果神经网络中某一神经元与另一直接与其相连的神经元同时处于兴奋状态，那么两个神经元之间的连接强度应该加强。

Wij〔t＋1〕修正一次后的某一权值η为正常量，为学习因子Xi(t),Xj(t)分别表示在t时刻i，j神经元的状态

1/18/202455

最根本的误差修正规那么,即δ学习规那么：步1选择一组初始权值Wij(0)。步2计算某一输入模式对应的实际输出与期望输出的误差。步3用下式更新权值(阈值可视为输入恒为-1的一个权值)Wij(t＋1)=Wij(t)＋η［dj－yj(t)］xi(t)步4返回步2，直到对所有训练模式网络输出均能满足要求。1/18/2024562.学习方法分类

表9.2神经网络学习方法的常见分类

1/18/2024579.3.5BP网络及其学习举例BP(Back-Propagation)网络的特点：(1)BP网络的拓扑结构为分层前向网络。(2)神经元的特性函数为Sigmoid型(S型)函数,一般取为

(3)输入为连续信号量(实数)。(4)学习方式为有导师学习。(5)学习算法为推广的δ学习规那么,称为误差反向传播算法,简称BP学习算法。1/18/202458BP网络举例1/18/202459BP学习算法：步1初始化网络权值、阈值及有关参数。步2计算总误差

其中p为样本个数，ykj为输出层节点j对第k个样本的输入对应的输出〔称为期望输出〕，ykj′为节点j的实际输出。如果误差E满足要求，学习成功。步3对样本集中各个样本依次重复以下过程，然后转步2。1/18/202460

首先，取一样本数据输入网络，然后按如下公式向前计算各层节点(记为j)的输出：

其次，从输出层节点到输入层节点以反向顺序，对各连接权值wij按下面的公式进行修正：

对于输出节点对于中间节点1/18/202461中间层的误差项：对受隐藏单元影响的误差δl进行加权求和，每个误差δl权值为wlj，wlj这个就是从隐藏单元j到输出单元l的权值，这个权值刻画了隐藏单元j对输出单元l的误差应“负责〞的程度。对每个训练样例k，利用有关这个样例的误差Ek的梯度修正权值，对每一个训练样例k，每个权被增加Δwij，即1/18/202462

算法中的δj称为节点j的误差。它的来历如下:

令1/18/202463又当j为输出节点时：当j为中间节点时1/18/202464可以看出，(9―3)式中Ek是网络输出ykj(j=1，2，…，n)的函数，而ykj又是权值wij的函数，所以，Ek实际是wij的函数。网络学习的目的就是要使这个误差函数到达最小值。(9―4)式及δ的定义，就是用梯度下降法，在权值空间沿负梯度方向调整权值wij，以使(9―3)式所示的准那么函数到达最小。所以，BP网络的学习过程就是一个非线性优化过程。1/18/202465由于BP网络的输入(x1,x2,…，xn)∈Rn，输出(y1,y2,…，ym)∈Rm，所以一个BP网络其实就是一个从n维空间到m维空间的高度非线性映射。通过学习，BP网络可以在任意希望的精度上逼近任意的连续函数。所以BP网络可以作为一种函数估计器。BP网络的相邻两层的节点之间的连接权值wij构成一个矩阵，而输入又是一个向量，所以，网络学习中要屡次用到矩阵运算。1/18/202466例9.5设计一个BP网络,对下表所示的样本数据进行学习,使学成的网络能解决类似的模式分类问题。

输入输出x1

x2

x3y1

y2

y30.30.80.10.70.10.30.60.60.610001