人工智能导论：第四章 机器学习.ppt

第四章 机器学习l“如果一个系统能够通过执行某个过程改进它的性能，这就是学习”西蒙l现在的机器学习方法主要是统计机器学习l统计学习就是计算机系统通过运用数据及统计方法提高系统性能的机器学习1l统计学习从数据出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，又回到对数据的分析与预测中l统计学习的目标就是考虑学习什么样的模型和如何学习，以使模型能对数据进行准确的预测和分析2l分类：监督学习非监督学习半监督学习强化学习3l统计学习三要素：模型：学习什么样的模型l条件概率分布、决策函数策略：模型选择的准则l经验风险最小化、结构风险最小化算法：模型学习的算法l一般归结为一个最优化问题4过拟合与泛化能力5机器学习的应用l应用广泛，信息处理的各个方面几乎都要用到机器学习文字、语音识别，输入法搜索引擎推荐、广告文本处理、机器翻译图像、视频处理674.1 朴素贝叶斯法（Nave Bayes）l朴素贝叶斯法属于一种分类方法，基于特征条件独立假设学习输入/输出的联合概率分布，以此为模型，对于给定的输入x，利用贝叶斯定理求出后验概率最大的输出yl简单有效，是一种常用的机器学习方法8l设输入空间 为n维向量的集合l输出空间为类标记集合lX是定义在输入空间上的随机变量lY是定义在输出空间上的随机变量lP(X,Y)是X和Y的联合概率分布l是由P(X,Y)独立同分布产生的训练集9贝叶斯法则10l为此引入独立性假设，即：l得到朴素贝叶斯分类器：11参数估计极大似然估计1213参数估计贝叶斯估计14l试用下表的训练数据学习一个朴素贝叶斯分类器，并确定x=(2,S)T的类标记y。

l其中X(1)、X(2)为特征，取值的集合分别为A1=1,2,3,A2=S,M,L，Y为类标记，取值范围为1,-1l（用最大似然估计）15举例训练数据12345678X(1)11111222X(2)SMMSSSMMY-1-111-1-1-11169101112131415X(1)2233333X(2)LLLMMLLY111111-11718朴素贝叶斯法用于文本分类l关键是如何把问题映射到朴素贝叶斯分类法l词袋模型（Bag of words）一篇文章的内容只与所用的词汇有关，而与词汇的位置无关19lLearn_naive_Bayes_text(Examples,C)lExamples为一组文本文档以及它们的类标记C=ck为所有可能类标记的集合l此函数的功能是学习概率项P(wj|ck)，它描述了从类别ck中的一个文档中随机抽取的一个单词为单词wj的概率该函数也同时学习类别的先验概率P(ck)20训练过程1，Vocabulary在Examples中任意文本文档中出现的所有单词及记号的集合2，对C中每个类标记ckdocskExamples中类标记为ck的文档子集P(ck)|docsk|/|Examples|Textk将docsk中所有单词连接起来建立的单个文档nTextk的长度（以词为单位）对Vocabulary中每个单词wjlnj单词wj出现在Textk中的次数lP(wj|ck)(nj+1)/(n+|Vocabulary|)21lClassify_naive_Bayes_text(Doc)l对文档Doc返回其估计的类标记。

ai代表在Doc中的第i个位置上出现的单词1，positions在Doc中包含的能在Vocabulary中找到的所有单词位置2，返回22分类过程4.2 支持向量机（SVM）lSupport Vector Machines,SVMl二类分类器l特征空间上的间隔最大化线性分类器l通过核技巧可实现非线性分类l根据模型的复杂程度可划分为：线性可分支持向量机线性支持向量机非线性支持向量机23线性可分支持向量机24ABCD最优分界面2525l定义4.1：给定线性可分训练集：其中：这里xi为第i个特征向量，yi为xi的类标记，+1表示正类，-1表示负类通过间隔最大化得到分类超平面：相应的决策函数：称为线性可分支持向量机26函数间隔l设训练集T和超平面(w,b)，定义超平面(w,b)关于样本点(xi,yi)的函数间隔为：l定义超平面关于T的函数间隔为：27几何间隔2829ABw函数间隔与几何间隔的关系30间隔最大化31l由于函数间隔是可缩放的，成比例变化不影响最优化问题，所以可取 l同时，最大化 与最小化 是等价的，于是问题转化为如下的凸二次规划问题：l使上式等式成立的点构成了支持向量32最优分界面3333wl例：设正例：x1=(3,3)T,x2=(4,3)T,l 负例：x3=(1,1)，求最大间隔超平面34学习的对偶算法l原始问题：l定义拉格朗日函数：35l根据拉格朗日对偶性，原始问题的对偶问题为极大极小问题：l对w,b求偏导令其为0求解并代入，得到对偶问题：36l目标函数由求极大转换成求极小，得到等价的对偶问题：373839l因此线性可分支持向量机就是求解如下的优化问题：40l例：设正例：x1=(3,3)T,x2=(4,3)T,l 负例：x3=(1,1)，l用对偶问题求线性可分支持向量机。

41424344线性支持向量机45AB回顾：线性可分支持向量机l某些点线性不可分，意味着这些点不满足函数间隔大于等于1的条件l为此引入松弛变量 ，使得：46l为使 尽可能的小，优化目标增加惩罚项，变为：l称为软间隔最大化l其中C0为惩罚参数，C大时对误分类的惩罚增加，C小时对误分类的惩罚减少l上式的含义：间隔尽量最大，同时误分类的点数尽可能小，二者由C调和47线性支持向量机就转化为如下的优化问题（原始问题）：可以证明w的解是唯一的，但b的解不唯一，而是存在于一个区间48l同样，通过求解对偶问题求解原始问题4950l分类超平面：l分类决策函数为：515253非线性支持向量机545556l用线性分类的方法求解非线性分类问题（1）使用一个变换，将原空间数据映射到新空间；（2）在新空间用线性分类方法从训练数据中学习分类模型57核技巧应用于支持向量机l通过一个非线性变换将输入空间X（欧式空间或者离散集合）对应于一个特征空间H（希尔伯特空间），使得在输入空间X的超曲面模型对应于特征空间H中的超平面模型（支持向量机）l分类问题的学习就可以通过在H空间中求解线性支持向量机完成5859核函数60616263常用的核函数64一个非线性分类的例子65SVM用于求解多类问题l一对多某类为正例，其余类为负例。

分类时将未知样本分类为具有最大分类函数值的那类l一对一任意两类构造一个SVM，分类时采取投票法决定类别l层次法所有类先分成两类，每类在分为两类66llibSVM：一个开源的SVM软件包l台湾大学林智仁教授开发67SVM用于文本分类l文本的向量空间模型文本表达为一个向量(w1,j,w2,j,wn,j)Twij表示词项i在文档j中的权重词项频率tfij权重tf-idf权重68ltfij权重lwij=tfijtfij表示第i个词项在第j个文档中出现的次数69ltf-idf权重文档频率：dfi=出现词项i的文档数逆文档频率：idfi=log(N/dfi),l(1)wij=tfij*idfil(2)wij=(1+logtfij)*idfi，当tfij=0时wij=0l第二种更常用，此外还有很多变形70分类问题评价指标l设正确分到k类的文本数为ak，错误分到k类的文本数为bk，属于该类而未被分到该类的文本数为ckl则(宏平均)：71lF值(F_measure)：l是准确率与召回率的调和平均值72交叉验证l当数据充分时，可以随机地将样本划分为三类：训练集验证集测试集l现实中数据往往不足73l交叉验证的基本思想就是重复使用数据l简单交叉验证将数据集划分为训练集和测试集，通过测试集选择模型S折交叉验证随机地将数据集划分为S个子集，S-1个子集用于训练，一个子集用于测试，重复S次留一交叉验证当S=N时的特殊情况，其中N为数据集的规模74实际中的问题l分类体系的建立l数据的收集l预处理分词停用词（Stop word）处理词干化（Stemming）特征选择754.3 决策树l决策树模型是一种描述对实例进行分类的树形结构，由节点和有向边组成。

节点有两种类型：内部节点和叶节点内部节点表示一个特征或者属性，叶节点表示一个类7677成绩90no成绩80yes优秀良好成绩70yesno成绩60yes中及格不及格yesnono7878成绩80no成绩70yes优秀良好成绩60noyes及格不及格no成绩90yesno中yesl决策树可以看成是一个if-then规则的集合l决策树还表示给定特征条件下类的条件概率分布，当某个条件概率大于0.5时，则认为条件成立79决策树学习l决策树学习就是从训练集中归纳出一组分类规则，得到一个与训练集矛盾较小的决策树80l对于给定的训练集，可以构造出多个决策树，一般以损失函数最小化作为优化目标l从所有决策树中选取最优决策树是一个NPC问题，所以一般采用启发式方法，得到一个近似解81l决策树学习包括特征选择决策树生成决策树剪枝82特征选择l一个问题中可能有不同的特征，不同的特征具有不同的分类能力，特征选择就是如何选取出那些分类能力强的特征l决策树中一般按照信息增益选择特征l所谓的信息增益就是某个特征A对数据集D进行分类的不确定性减少的程度83信息增益84l特征A对数据集D的信息增益定义为：l表示特征A对数据集D的分类的不确定性减少的程度l信息增益大的特征具有更强的分类能力85l设训练集D，K个类Ck，特征A有n个不同的取值ai,an，A的不同取值将D划分为n个子集D1Dn，Di中属于类Ck的样本的集合为Dik，|表示样本个数。

l信息增益计算如下：86决策树的生成l两个常用的算法lID3一个基本的决策树生成算法lC4.5对ID3的改进87ID3算法l输入：训练集D，特征集A，阈值el输出：决策树Tl1，若D中所有实例属于同一类Ck，则T为单节点树，将Ck作为该节点的类标记，返回Tl2，若A为空，则T为单节点树，将D中实例数最大的类Ck作为该节点的类标记，返回Tl3，否则计算A中各特征对D的信息增益，选择信息最大的特征Agl4，如果Ag的信息增益小于阈值e，则置T为单节点树，将D中实例数最大的类Ck作为该节点的类标记，返回T88l5，否则对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回Tl6，对第i个子节点，以Di为训练集，以A-Ag为特征集，递归地调用步1步5，得到子树Ti，返回Ti89l例：贷款申请样本如下表所示，试用ID3算法构建决策树9091ID年龄年龄 A1有工作有工作 A2有房子有房子 A3信贷情况信贷情况 A4类别类别1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否9293l生成的决策树如下：lID3只有树的生成，所以容易产生过拟合94是是是是否否否有房子有工作ID3存在的问题l信息增益倾向于选择分枝比较多的属性l比如前面贷款的例子中，如果用ID做属性，将获得最大的信息增益值95信息增益比l其中A为属性，A的不同取值将D划分为n个子集D1Dn96C4.5的生成算法lC4.5与ID3的唯一不同，就是根据信息增益比选择特征，其他与ID3完全一样。

l同时C4.5增加了对连续值属性的处理，对于连续值属性A，找到一个属性值a0，将a0的划分到左子树，a0的划分到右子树97决策树的剪枝l为了防止出现过拟合，对生成的决策树进行简化的过程称为剪枝也就是从已经生成的树上裁掉一些子树或者叶节点l树T的叶节点个数为|T|，t是树T的叶节点，该节点有Nt个样本，其中k类的样本点有Ntk个（k=1,K），Ht(T)为叶节点t上的经验熵，a=0为参数98l定义损失函数：99l剪枝，就是当a确定时，选择损失函数。