ch机器学习与知识发现人工智能课程安徽理工大学计

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

6.1机器学习概述

6.2符号学习

6.3神经网络学习

6.4知识发现与数据挖掘6.1机器学习概述6.1.1机器学习的概念心理学中对学习的解释是：学习是指（人或动物）依靠经验的获得而使行为持久变化的过程。Simon认为：如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。Minsky认为：学习是在人们头脑中（心理内部）进行有用的变化。TomM.Mitchell在《机器学习》一书中对学习的定义是：对于某类任务T和性能度P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么，我们称这个计算机程序从经验E中学习。当前关于机器学习的许多文献中也大都认为：学习是系统积累经验以改善其自身性能的过程。

总之：①学习与经验有关；②学习可以改善系统性能；③学习是一个有反馈的信息处理与控制过程。因为经验是在系统与环境的交互过程中产生的，而经验中应该包含系统输入、响应和效果等信息。因此经验的积累、性能的完善正是通过重复这一过程而实现的。6.1.2机器学习的原理图9-1机器学习原理1图9-2机器学习原理2

图9-3机器学习原理3图9-4机器学习原理4图9-5机器学习原理56.1.3机器学习的分类

1.基于学习策略的分类（1）模拟人脑的机器学习●符号学习：模拟人脑的宏观心理级学习过程，以认知心理学原理为基础，以符号数据为输入，以符号运算为方法，用推理过程在图或状态空间中搜索，学习的目标为概念或规则等。符号学习的典型方法有：记忆学习、示例学习、演绎学习、类比学习、解释学习等。●神经网络学习（或连接学习）：模拟人脑的微观生理级学习过程，以脑和神经科学原理为基础，以人工神经网络为函数结构模型，以数值数据为输入，以数值运算为方法，用迭代过程在系数向量空间中搜索，学习的目标为函数。典型的连接学习有权值修正学习、拓扑结构学习。（2）直接采用数学方法的机器学习

●主要有统计机器学习。

2.基于学习方法的分类

（1）归纳学习●符号归纳学习：典型的符号归纳学习有示例学习，决策树学习。●函数归纳学习（发现学习）：典型的函数归纳学习有神经网络学习、示例学习，发现学习，统计学习。（2）演绎学习（3）类比学习：典型的类比学习有案例（范例）学习。（4）分析学习：典型的分析学习有案例（范例）学习、解释学习。3.基于学习方式式的分类（1）有导师学习（（监督学习））：输入数据中有有导师信号，，以概率函数数、代数函数数或人工神经经网络为基函函数模型，采采用迭代计算算方法，学习习结果为函数数。（2）无导师学习（（非监督学习习）：输入数据中无无导师信号，，采用聚类方方法，学习结结果为类别。。典型的无导导师学习有发发现学习、聚聚类、竞争学学习等。（3）强化学习（增增强学习）：：以环境反馈（（奖/惩信号号）作为输入入，以统计和和动态规划技技术为指导的的一种学习方方法。4.基于数据形式式的分类（1）结构化学习：以结构化数数据为输入，，以数值计算算或符号推演演为方法。典典型的结构化化学习有神经经网络学习、、统计学习、、决策树学习习、规则学习习。（2）非结构化学习习：以非结构化化数据为输入入，典型的非非结构化学习习有类比学习习、案例学习习、解释学习习、文本挖掘掘、图像挖掘掘、Web挖挖掘等。5.基于学习目标标的分类（1）概念学习：即学习的目目标和结果为为概念，或者者说是为了获获得概念的一一种学习。典典型的概念学学习有示例学学习。（2）规则学习：即学习的目目标和结果为为规则，或者者说是为了获获得规则的一一种学习。典典型的规则学学习有决策树树学习。（3）函数学习：即学习的目目标和结果为为规则，或者者说是为了获获得函数的一一种学习。典典型的函数学学习有神经网网络学习。（4）类别学习：即学习的目目标和结果为为对象类，或或者说是为了了获得类别的的一种学习。。典型的类别别学习有聚类类分析。（5）贝叶斯网络学学习：即学习的目目标和结果是是贝叶斯网络络，或者说是是为了获得贝贝叶斯网络的的一种学习。。其又可分为为结构学习和和参数学习。。6.2符号号学习记记忆学习记忆学习方法法简单,但但学习系统需需要几种能力力：(1)能实实现有组织的的存储信息。。(2)能进进行信息综合合。(3)能控控制检索方向向。当存储储对象愈多时时,其中可可能有多个对对象与给定的的示示例学习示例学习也称称实例学习,它是一种种归纳学习。。示例学习是是从若干实例例(包括正例例和反例)中中归纳出一般般概念或规则则的学习方法法。图9-6第第一个拱桥桥的语义网络络图9-7第第二个拱桥桥的语义网络络图9-8学学习程序归归纳出的语义义网络图9-9拱拱桥概念的的语义网络例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)对于这个问题题可采用通常常的曲线拟合合技术，归纳纳出规则：(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．什么是决策树树决策树(decisiontree)也称判判定树，它是是由对象的若若干属性、属属性值和有关关决策组成的的一棵树。其其中的节点为为属性（一般般为语言变量量），分枝为为相应的属性性值（一般为为语言值）。。从同一节点点出发的各个个分枝之间是是逻辑“或””关系；根节节点为对象的的某一个属性性；从根节点点到每一个叶叶子节点的所所有节点和边边，按顺序串串连成一条分分枝路径，位位于同一条分分枝路径上的的各个“属性性-值”对之之间是逻辑““与”关系，，叶子节点为为这个与关系系的对应结果果，即决策。。决策树示意图图例9.3下下图所示是机场场指挥台关于于飞机起飞的的简单决策树树。例9.4下图是一个描述述“兔子”概概念的决策树树。2.怎样学习决策策树决策树学习的的基本方法和和步骤：首先，选取一一个属性，按按这个属性的的不同取值对对实例集进行行分类；并以以该属性作为为根节点，以以这个属性的的诸取值作为为根节点的分分枝，进行画画树。然后，考察所所得的每一个个子类，看其其中的实例的的结论是否完完全相同。如如果完全相同同，则以这个个相同的结论论作为相应分分枝路径末端端的叶子节点点；否则，选选取一个非父父节点的属性性，按这个属属性的不同取取值对该子集集进行分类，，并以该属性性作为节点，，以这个属性性的诸取值作作为节点的分分枝，继续进进行画树。如此继续，直直到所分的子子集全都满足足：实例结论论完全相同，，而得到所有有的叶子节点点为止。●决策树学习举举例设表9.1所所示的是某某保险公司的的汽车驾驶保保险类别划分分的部分事例例。我们将这这张表作为一一个实例集，，用决策树学学习来归纳该该保险公司的的汽车驾驶保保险类别划分分规则。表9.1汽车驾驶保险类别划分实例集

将实例集简记记为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””这三个年龄段段。对于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)}于是，我们得得到以性别作作为根节点的的部分决策树树（见下图））。决策树生成过过程决策树生成过过程决策树生成过过程最后生成的决策树由决策树所得得的规则集：①女性且年年龄在25岁岁以上，则给给予A类保险险；②女性且年年龄在21岁岁到25岁之之间，则给予予A类保险；；③女性且年年龄在21岁岁以下，则给给予C类保险险；④男性且年年龄在25岁岁以上，则给给予B类保险险；⑤男性且年年龄在21岁岁到25岁之之间且未婚，，则给予C类类保险；⑥男性且年年龄在21岁岁到25岁之之间且已婚，，则给予B类类保险；⑦男性且年年龄在21岁岁以下且未婚婚，则给予C类保险；⑧男性且年年龄在21岁岁以下且已婚婚，则给予B类保险。3.ID3算算法法ID3算算法法是是一一个个经经典典的的决决策策树树学学习习算算法法，，由由Quinlan于于1979年年提提出出。。ID3算算法法的的基基本本思思想想是是，，以以信信息息熵熵为为度度量量，，用用于于决决策策树树节节点点的的属属性性选选择择，，每每次次优优先先选选取取信信息息量量最最多多的的属属性性，，亦亦即即能能使使熵熵值值变变成成最最小小的的属属性性，，以以构构造造一一棵棵熵熵值值下下降降最最快快的的决决策策树树，，到到叶叶子子节节点点处处的的熵熵值值为为0。。此此时时，，每每个个叶叶子子节节点点对对应应的的实实例例集集中中的的实实例例属属于于同同一一类类。。（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对应应的的那那个个子子类类。。（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女而言言,于是是,由公公式式(9-1)有:又将以以上上3式代代入入公公式式(9-2)得:用同同样样的的方方法法可可求求得得:可见见,条条件件熵熵H(S|性性别别)为为最最小小,所所以以,应应取取““性性别别””这这一一属属性性对对实实例例集集进进行行分分类类,即即以以““性性别别””作作为为决决策策树树的的根根节节点点。。6.3神神经经网网络络学学习习生生物物神神经经元元生物物神神经经元元的的基基本本结结构构人人工工神神经经元元人工工神神经经元元结结构构模模型型人工工神神经经元元的的输输入入、、输输出出关关系系可可描描述述为为：：神经经元元特特性性函函数数1.阈阈值值型型2.S型型3.分分段段线线性性型型神经经元元特特性性函函数数神神经经网网络络1.分分层层前前向向网网络络2.反反馈馈前前向向网网络络3.互互连连前前向向网网络络4.广广泛泛互互连连网网络络神经经网网络络结构构模模型型神经经网网络络至至少少可可以以实实现现如如下下功功能能：———数数学学上上的的映映射射逼逼近近———数数据据聚聚类类、、压压缩缩通通过过自自组组织织方方式式对对所所选选输输入入模模式式聚聚类类———优优化化计计算算和和组组合合优优化化问问题题求求解解———模模式式分分类类———概概率率密密度度函函数数的的估估计计神神经经网网络络学学习习1.学学习习规规则则Hebb规规则则：最基基本本的的误误差差修修正正规规则则,即即δ学习习规规则则：步1选选择一组组初始权权值Wij(0)。。步2计计算某一一输入模模式对应应的实际际输出与与期望输输出的误误差。步3用用下式更更新权值值(阈值值可视为为输入恒恒为-1的一个个权值)Wij(t＋1)=Wij(t)＋η［dj－yj(t)］xi(t)步4返返回步2，直到到对所有有训练模模式网络络输出均均能满足足要求。。2.学学习方法法分类表9.2神经网络学习方法的常见分类

9.3.5BP网络络及其学学习举例例BP(Back-Propagation)网络络的特点点：(1)BP网网络的拓拓扑结构构为分层层前向网网络。(2)神神经元元的特性性函数为为Sigmoid型(S型)函数,一般般取为(3)输输入为为连续信信号量(实数)。(4)学学习方方式为有有导师学学习。(5)学学习算算法为推推广的δ学习规则则,称称为误差差反向传传播算法法,简简称BP学习算算法。BP学习习算法：：步1初初始化网网络权值值、阈阈值及有有关参数数。步2计计算总误误差其中ykj为输出层层节点j对第k个样本的的输入对对应的输输出（称称为期望望输出）），ykj′为节点点j的实际输输出。步3对对样本集集中各个个样本依依次重复复以下过过程，然然后转步步2。首先，取取一样本本数据输输入网络络，然后后按如下下公式向向前计算算各层节