监督学习算法学习笔记

1、监督学习1基本概念监督学习又称为分类(Classification)或者归纳学习(Inductive Learning)。几乎适 用于所有领域，包括文本和网页处理。给出一个数据集D,机器学习的目标就是产生一 个联系属性值集合A和类标集合C的分类/预测函数(Classification/Prediction Function)， 这个函数可以用于预测新的属性集合的类标。这个函数又被称为分类模型(Classification Model)、预测模型(Prediction Model)。这个分类模型可以是任何形式的，例如决策 树、规则集、贝叶斯模型或者一个超平面。在监督学习(Supervised L

2、earning)中，已经有数据给出了类标；与这一方式相对 的是无监督学习(Unsupervised Learning)，在这种方式中，所有的类属性都是未知的， 算法需要根据数据集的特征自动产生类属性。算法用于进行学习的数据集叫做训练数据 集，当使用学习算法用训练数据集学习得到一个模型以后，我们使用测试数据集来评测 这个模型的精准度。机器学习的最基本假设是：训练数据的分布应该与测试数据的分布一致。2决策树推理2.1什么是决策树决策树学习算法是分类算法中最广泛应用的一种技术，这种算法的分类精度与其他 算法相比具有相当的竞争力，并且十分高效。例如，对于表2-1所示的贷款申请的数据 集，可以学习到一种

3、决策树结构，表示为图2-1。ID1314AgeHas J obOwnhouscCreditratingClassyoungfalsefalsefairX(youngfalsefalsegoodXoyoungtruefalsegoodYesyoungtruetruefairYesyoungfalsefalsefairNomiddlefalsefal?.cfairXomiddlefalsefalsegoodXomiddletruetruegoodYesmiddlefalsetrueexcellentYesmiddlefalsetrueexcellentYesoldfalsetrueexcellen

4、tYesoldfalsetruegoodYesoldtruefalsegoodYesoldtruefalseexcellentYesoldfalsefalsefairNd表2-1贷款申请数据根据数据集建立的一种决策树结构如下:图2-1对应与表2-1的决策树树中包含了决策点和叶子节点，决策点包含针对数据实例某个属性的一些测试，而 一个叶子节点则代表了一个类标。一棵决策树的构建过程是不断的分隔训练数据，以使得最终分隔所得到的各个子集 尽可能的纯。一个纯的子集中的数据实例类标全部一致。决策树的建立并不是唯一的，在实际中，我们希望得到一棵尽量小且准确的决策树。2.2学习算法学习算法就是使用分治策略，第

5、贵的对训练数据进行分隔，从而构造决策树。递归 的终止条件在算法的14行，当所有的节点中的数据都属于同一个类时，迭代终止。学 习算法中，每一个后续的递归都选择最佳分类属性作为分隔当前数据实例集的属性。最 佳分类属性等的选择通过混杂度函数(Impurity Function来实现，这个函数反映了用 该属性进行数据分隔以后的数据集的混杂度。决策树学习算法如图2-2所示。.Alpr llhm disionTiD, T)if D contaim. only training examples of the same classy g C then.naake T a k-af node hbrlcd w

6、ill chssQ；MMf=0 then.make Ts leaf node labeled with which is die most frequent class, in Dtht V D ton lai ns cxarnplcs hckunging Eo 目 mixEunj of We ficltir! a/ HLlribu* to pardtion D into mubsetE so that5ub*6Ct 祯 pur切所=impurityExal-1 ();Sfo r each attri but-e A g A =l 广4、广& d o/?, = innpuri ty EvaJ

7、-2( A hcmlfiirSelect e Hh -hi，-勺that gives the biggest impurity roductiari,tonipulcd uingii 9 & .theabk to roduicc irnpurriiy 如Make Ta decision node in 4庆Let the possible vcilu.es uf be vis 巧, i i畚 Partilkm D hulo wdisjoint ubs-et Dlt D2l & based an the m values of .4K-for each DJ in ( hM doIXifZ3ih

8、i?ncreate a branch (edge) node Ffcir vas a child node of deci 晶ionTne或耳 A T&K 们七诂 rernovedmdifriiiirurend ifcndlf图2-2决策树学习算法该算法最核心的思想就是选择能最大限度降低类别混杂度的属性作为决策点。其中的第7行使用熵的公式计算：entropy(D)= 一刃 Pr(c )log Pr(c )j=1乙 Pr(c ) = 1jj=1熵在这里代表一个集合的无序程度，集合中的熵偏小，说明该集合中的大部分元素都是同质的。第9行计算划分后的熵大小。采用如下公式：Dentropy (D)=乙

9、一j x entropy (D )1j=1其中v是划分后子集的个数。信息增益计算公式如下：gain(D, A) = entropy(D) - entropy (D)信息增益用来衡量混杂度的减少量。算法第11行进行这个操作，选择最大的Ag使得混 杂度的减少量达到最大。3分类器的评估标准主要的评估标准就是分类精度，它是用在测试集中被正确分类的数据数量除以测试 集中的数据数量得到。在一些实际应用中，我们仅对数量占少数的类别感兴趣，那些用户感兴趣的类别通 常称为正例类别，其他类别称为负例类别。查准率、查全率和F-score是评价分类器的三个常用指标，通过混合矩阵，我们可 以很方便地得到查准率和查全率两

10、个数据，混合矩阵(如表3-1)中包含数据的真实情 况和分类器的预测结果。TPFNFPTN实际上为正例实际上为负例表3-1分类器的混合矩阵分类器认为是正例分类器认为是负例根据上述混合矩阵，正例类别的分类查准率(p)和查全率(r)定义如下TPTPp =, r =TP + FPTP + FN尽管查准率和查全率理论上是不相关的，但是在实际应用中，高查准率往往实在牺 牲查全率的情况下得到的。同样，高查全率是在牺牲高查准率的情况下得到的。在实际 应用中到底哪个标准更重要取决于这个应用，如果仅用一个指标来衡量分类器的性能， 此时常使用F-score：F=业p + rF-score是查全率和查准率的调和平均值

11、。两个数值的调和平均值更加倾向于两个数当中 较小的那个。因此，如果想得到较高的F-score，则p和r都必须很高。4朴素贝叶斯分类4.1准备知识条件概率：设A, B是两个事件，且Pr(A)0称Pr( BIA)=史竺)为在条件A下发生的 Pr( A)条件事件B发生的条件概率。乘法公式： 设 Pr(A) 0 则有 Pr(AB) = Pr(BI A)Pr(A)全概率公式：设随机事件AA2，.，An以及B满足：(1) AA2，An两两互不 相 容；(2) U A广 S 或 者 B u U A ；(3)Pr(A) 0 (n=1,2,.)，贝U 有n=1n=1P B (=3APB (A ,)称为全概率公式

12、。n = 1全概率公式的应用：把事件B看作是某一个过程的结果，把，A2,，An看作 该过程的若干个原因，根据历史资料，每个原因发生的概率已知(即Pr(A.)已知)，且 每一个原因对结果的影响已知(即Pr(B|A.)已知)则可用全概率公式计算结果发生的概 率，即求Pr(B)。4.2朴素贝叶斯文本分类贝叶斯公式：设随机事件A1，A2,，An以及B满足：(1) A1，A2,，An两两互不 相 容；(2)U A= S 或 者 B u U An ；(3) Pr(A) 0 (n=1,2,.)， 则n=1n=1P A (B = W =)B 一 nA !称为成海公式。n P B (立 P B A | A. )

13、 P r ()n=1贝叶斯公式的使用：把事件B看作某一过程的结果，把A1，A2,，An看作该过 程的若干原因，根据历史资料，每一原因发生的概率已知(即Pr(An)已知)，如果已知 事件B已经发生，要求此时是由第i个原因引起的概率，用贝叶斯公式(即求Pr(A.|B)。在贝叶斯分类中，在数据集合D中，令A1,A2,.,A|A|为用离散值表示的属性集合，设C具有ICI个不同值的类别属性，即C1,C2，,，我们设所有的属性都是条件独立于类 别，给定一个测试样例/观察到属性值。1到。问 其中%是气可能的一个取值，那么 预测值就是类别C”使得Pr(C=c.I A=a1，人=气J最大。被称为最大后验概率假设

14、。 TOC o 1-5 h z jj 1IAI AIj根据贝叶斯公式，有Pr(C = c )FIpr(A = a I C = c )ji ijPr(A = a ,., A = a I C = c ) =i=i11 AAIj 四 Pr(C = c )FIpr(A = a I C = c ) HYPERLINK l bookmark91 o Current Document ki ikk =1i =1因为分母对每一个训练类别都是一样的，所以如果仅仅需要总体上最可能的类别为 所有测试样例做预测，那么只需要上式的分子部分即可。通过下式来判断最有可能的类 别： HYPERLINK l bookmark9

15、4 o Current Document c = arg max Pr(C = c )H Pr( A = a I C = c ) ji i jcji=1例如，假设我们有图4-1中的训练数据，有两个属性A和B,还有类别C，对于一个 测试样例：A=m B=q求C=?ABCmbtmstgqthstgqtgqfgsfhbfhqfmibf图4-1训练数据计算如下：对于类别为t的概率Pr(C = t)IPr(A = a IC = t) = Pr(C = t) - Pr(A = m IC = t) - Pr(B = q I C = t) =1 x - x -= j j2 5 5 25j=1125类似的，对于

16、类别为f的概率Pr(C = f )IlPr(A = a I C = f) = - x - x -= j j2 5 5j=1因此C=t的可能性较大，因此将此种情况下的类别判断为t。朴素贝叶斯分类将每篇文档看作一“袋子”的词，需要做以下假设，这也是称作“朴 素的”贝叶斯的由来： 文档中的词都是独立于语境生成的。单词被生成的概率是与它在文档中的位置无关的。文档的长度与类别是无关的。通过公式推导，最后可以得到分类函数Pr(c I d) g Pr(c )世| Pr(w I c )iij ij=1其中，Pr(w I c ) = 一 + T七匕)一。TF(w ,c )是词w.在c.类训练文档集中出 入 IV

17、I +VTF 叫,七) j jk=1现的频率，人是一个因子，一般设为人=1/n，n为训练数据的总数，当人=1时，称 为拉普拉斯延续率。加入平滑算子的目的是解决不经常出现的单词零概率估计的问 题，需要对概率进行平滑处理来避免出现0或1概率。4.3朴素贝叶斯文本分类的优缺点虽然朴素贝叶斯学习所做的大部分假设都与实际情况不符，但研究表明朴素贝叶斯 学习仍然能产生准确的模型。朴素贝叶斯学习效率很高，它只需要对训练数据进行一次 扫描就可以估计出所有需要的概率，所以朴素贝叶斯在文本分类中得到了广泛的应用。 4.4分类器的实现为了对朴素贝叶斯分类器原理理解更加深入，使用Java实现了一个简单的贝叶斯 分类器

18、。分类器由中文分词、训练、分类三个模块组成，系统框图见图4-2所示。中文分词：对于训练集和待分类的文档首先进行预处理，将文章进行中文分词后 才能在后面对其进行词频的统计。分词模块使用中科院ICTCLAS2010版本的分词程序， 模块从训练集中读入所有类别的所有训练文档，调用分词程序对其进行切分，将分词后 的文档按类别保存至另一目录下，等待训练。训练模块：对分词后的训练文档进行词频统计，得到各个类别的训练文档中，每 个词在此类训练文档集合中出现的频率。将得到的词，词频对保存至文件中(也可以 不存到文件中，只保存在内存里，存到文件中的主要作用是为了实现一次训练，多次使 用)。分类模块(待实现):从

19、文件系统中读入训练后的结果(词，词频对)，将待 分类的文档进行分词处理后利用朴素贝叶斯分类函数，计算其属于各个类别的概率，取 最大概率属于的类别，并将这个文档存入相应类别的文档中。分类图4-2贝叶斯文本分类器系统框图5支持向量机5.1概念支持向量机（Support Vector Machine）是Cortes和Vapnik于1995年首先提出的， 它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到 函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上 的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Ac

20、curacy） 和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推 广能力。所谓VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越 高，一个问题就越复杂。正是因为SVM关注的是VC维，后面可以看到，SVM解决问 题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得SVM很适合 用来解决文本分类的问题，当然，有这样的能力也因为引入了核函数）。5.2结构风险机器学习本质上就是一种对问题真实模型的逼近（选择一个我们认为比较好的近似 模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不知道的既然真 实模型不知道，那么我们选择的假设与问

21、题真实解之间究竟有多大差距，我们就没法得 知。这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。 我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从 得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本 数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间 的差值来表示。这个差值叫做经验风险Remp（w）。以前的机器学习方法都把经验风险最 小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确 率，在真实分类时却一塌糊涂(即所谓的推广能力差，或泛化能力差)。此时的情况便 是

22、选择了一个足够复杂的分类函数(它的VC维很高)，能够精确的记住每一个样本， 但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现，此原 则适用的大前提是经验风险要确实能够逼近真实风险才行，但实际上能逼近么？答案是 不能，因为样本数相对于现实世界要分类的文本数来说简直九牛一毛，经验风险最小化 原则只在这占很小比例的样本上做到没有误差，当然不能保证在更大比例的真实文本上 也没有误差。统计学习因此而引入了泛化误差界的概念，就是指真实风险应该由两部分内容刻画， 一是经验风险，代表了分类器在给定样本上的误差；二是置信风险，代表了我们在多大 程度上可以信任分类器在未知文本上分类的结果。很

23、显然，第二部分是没有办法精确计 算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确 的值(所以叫做泛化误差界，而不叫泛化误差)。置信风险与两个量有关，一是样本数量，显然给定的样本数量越大，我们的学习结 果越有可能正确，此时置信风险越小；二是分类函数的VC维，显然VC维越大，推广 能力越差，置信风险会变大。泛化误差界的公式为：R(w)MRemp(w)+(n/h)公式中R(w)就是真实风险，Remp(w)就是经验风险，中(n/h)就是置信风险。统计学 习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。SVM正是这样一种努力最小化结构风险的算法。

24、5.3线性可分如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的(如图 5-1所示)，否则称为非线性可分的。在一维空间里线性函数就是一个点，在二维空间 里就是一条直线，三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维 数，这种线性函数还有一个统一的名称超平面(Hyper Plane)。图5-1线性可分的例子实际上，一个线性函数是一个实值函数(即函数的值是连续的实数)，而我们的分 类问题(例如这里的二元分类问题一一回答一个样本属于还是不属于一个类别的问题) 需要离散的输出值，例如用1表示某个样本属于类别C1，而用0表示不属于(不属于 C1也就意味着属于C2)，这时候只需要简单的在实值函数的基础上附加一个阈值即可， 通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。例如我们有一 个线性函数g (s) = wx + b其中，x是样本的向量表示，wx + b = 0是超平面，w是超平面的法向量。超平面不止 一个，例如和图5-1中所示的超平面平行且可划分类别的直线都是一个超平面，因此， 使用“分类间隔