监督学习算法基础知识整理

第三章监督学习算法监督学习又称为分类(Classification)或者归纳学习(InductiveLearning)。几乎适用于所有领域，包括文本和网页处理。给出一个数据集D,机器学习的目标就是产生一个联系属性值集合A和类标集合C的分类/预测函数(Classification/PredictionFunction),这个函数可以用于预测新的属性集合的类标。这个函数又被称为分类模型(ClassificationModel)、预测模型(PredictionModel)。这个分类模型可以是任何形式的，例如决策树、规则集、贝叶斯模型或者一个超平面。在监督学习(SupervisedLearning)中，已经有数据给出了类标；与这一方式相对的是无监督学习(UnsupervisedLearning)，在这种方式中，所有的类属性都是未知的，算法需要根据数据集的特征自动产生类属性。其中算法中用于进行学习的数据集叫做训练数据集，当使用学习算法用训练数据集学习得到一个模型以后，我们使用测试数据集来评测这个模型的精准度。机器学习的最基本假设：训练数据的分布应该与测试数据的分布一致。训练算法：训练算法就是给定一组样本，我们计算这些参数的方法。本节简要介绍以下几种常用的机器学习算法，比如决策树，朴素贝叶斯，神经网络，支持向量机，线性最小平方拟合，kNN，最大熵等。3.1两类感知器见课本3.2多类感知器见课本3.3决策树算法决策树学习算法是分类算法中最广泛应用的一种技术，这种算法的分类精度与其他算法相比具有相当的竞争力，并且十分高效。决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象属性，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值(类别)。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。树以代表训练样本的单个结点开始。如果样本都在同一个类.则该结点成为树叶，并用该类标记。否则，算法选择最有分类能力的属性作为决策树的当前结点。4•根据当前决策结点属性取值的不同，将训练样本数据集分为若干子集，每个取值形成一个分枝。针对上一步得到的一个子集，重复进行先前步骤，形成每个划分样本上的决策树。递归划分步骤仅当下列条件之一成立时停止：给定结点的所有样本属于同一类。没有剩余属性可以用来进一步划分样本。以样本组中个数最多的类别作为类别标记。AlgiJiithmdecisionTreefD,A,T)】 ifDcontainsonlytrainingexamplesofthesameclassqgCthenmakeTaleafnodelabeledwithclassy;dsdf.4—0thenmakeTaleafnodelabeledwithc$whichisthemostfrequentclassinDelse!!Dcontainsexamplesbelongingtoamixtureofclasses.Weselectasingle!!atcributetopartitionDintoSubsetssoLhateachsubseti£purer-impurityEval-1(D);foreachattributeA,eA(={A坯…，禺})dopf三impurityEval-2(AhD)endfoiSelecte 卫工，亠“thatgivesthebiggestimpurityreduction,computedusing-p占ifpo—<thresholdthen//屏甘docsnotsignificantlyreduceimpuritypGmakeTaleafnodelabeledwithCj,themostfrequentclassinD.dse // isabletoredixeimpurityp0MakeTadecisionnodeonLetthepossiblevaluesofbeV|,5卩对PartitionDintomdisjointsubsetsD^D》、…、basedonthemvaluesofAforeachD)in{DhD》,…,doi『0H0thimcreateabranch(edge)node7}forVjasachildnodeofJ;decisionTree(D^AT』/5丁)HA营也removedendifendfoi*endifendif决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集(称为测试数据集)中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。由于数据表示不当、有噪声或者由于决策树生成时产生重复的子树等原因，都会造成产生的决策树过大。因此，简化决策树是一个不可缺少的环节。寻找一棵最优决策树，主要应解决以下3个最优化问题：生成最少数目的叶子节点；生成的每个叶子节点的深度最小；

生成的决策树叶子节点最少且每个叶子节点的深度最小。例如，对于表3-1所示的贷款申请的数据集，可以学习到一种决策树结构,表示为图3-1。ID12ID123456789101112131415AgeOwnhouseCreditratingClassyoungfalsefalsefairXoyoungfalsefalsegoodXoyoungtruefalsegoodYesyoungtruetruefairYesyoungfalsefalsefairXomiddlefalsefalsefairXomiddlefalsefalsegood\omiddletruetnic呂oodYesmiddlefalsetrueexcellentYesmiddlefalsetrueexcellentYesoldfalsetrueexcellentYesoldfalsetrue呂oodYesoldtruefalsegoodYesoldtruefalseexcellentYesoldfalsefalsefairNd表3-1贷款申请数据根据数据集建立的一种决策树结构如下:Youngmiddle1HasJob?Ownhouse?Creditrating?7\truefalse/ xtrue/zxfalse\fairgoodexcellent1、YesNoYesNoNoYesYes(2/2)(3/3)(2/2)(1/1)(2/2)(2⑵图3-1对应与表3-1的决策树树中包含了决策点和叶子节点，决策点包含针对数据实例某个属性的一些测试，而一个叶子节点则代表了一个类标。一棵决策树的构建过程是不断的分隔训练数据，以使得最终分隔所得到的各个子集尽可能的纯。一个纯的子集中的数据实例类标全部一致。决策树的建立并不是唯一的，在实际中，我们希望得到一棵尽量小且准确的决策树。决策树的典型算法有ID3,C4.5,CART（分类与回归树）等。依次得到改进。相对于其它算法，决策树易于理解和实现，人们在通过解释后都有能力去理解决策树所表达的意义。决策树可以同时处理不同类型的属性，并且在相对短的时间内能够对大型数据源做出可行且效果良好的结果。3.4贝叶斯分类算法贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。目前研究较多的贝叶斯分类器主要有四种，分别是：NaiveBayes、TAN、BAN和GBN。▲准备知识条件概率：设A,B是两个事件，且Pr(A)>0称Pr(BIA)二pr(AB)为在条件A下Pr(A)发生的条件事件B发生的条件概率。乘法公式：设Pr(A)>0则有Pr(AB)二Pr(BIA)Pr(A)TOC\o"1-5"\h\z\o"CurrentDocument"全概率公式：设随机事件A],A2,...，An以及B满足：⑴A],A2，…，An两两互不相容；(2)UA=S或者BuUA；(3)Pr(A)>0(n=l,2,...)，则有n nn=1 n=1Pr(B)=FPr(A)Pr(B|A)，称为全概率公式。n nn=1全概率公式的应用：把事件B看作是某一个过程的结果，把A1，A2,…，An看作该过程的若干个原因，根据历史资料，每个原因发生的概率已知(即Pr(Ai)已知)，且每一个原因对结果的影响已知(即Pr(B|Ai)已知)则可用全概率公式计算结果发生的概率，即求Pr(B)。贝叶斯公式：设随机事件A1，A2，…，An以及B满足：(1)A1，A2，…，An两两互不相容；(2)UA=S或者BuUA；(3)Pr(A)>0(n=1,2,...)，则TOC\o"1-5"\h\zn nn=1 n=1PrAB=)PrAnB=—田(AJ APr(称为贝叶斯公式。n PrB)£PrBA)PAr()\o"CurrentDocument"j jn=1贝叶斯公式的使用：把事件B看作某一过程的结果，把A1，A2，…，An看作该过程的若干原因，根据历史资料，每一原因发生的概率已知(即Pr(An)已知)，如果已知事件B已经发生，要求此时是由第i个原因引起的概率，用贝叶斯公式(即求Pr(AJB))。▲朴素贝叶斯(NaiveBayes,NB)算法在贝叶斯分类中，在数据集合D中，令A1?A2,…A为用离散值表示的属性1 2 n

集合，设C具有IC个不同值的类别属性，即c1,c2,^,c|c|,我们设所有的属性都是条件独立于类别，给定一个测试样例d观察到属性值a1到a⑷，其中ai是Ai可能的一个取值，那么预测值就是类别j使得Pr(C=c.I4幻,...比=。⑷)最大。c被称为最大后验概率假设。根据贝叶斯公式，有Pr(C二c)FIpr(A二aIC二c)TOC\o"1-5"\h\zj ii jPr(A=a A=aIC=c)=1 1 IAI IAI j百 可乙Pr(C=c)11Pr(A=aIC=c)k ii kk=1 i=1因为分母对每一个训练类别都是一样的，所以如果仅仅需要总体上最可能的类别为所有测试样例做预测，那么只需要上式的分子部分即可。通过下式来判断最有可能的类别：c=argmaxPr(C=c•jc)FIpr(A=aIC=c=argmaxPr(C=c•jjiiji=1例如，假设我们有图4-1中的训练数据，有两个属性A和B,还有类别C，对于一个测试样例：A=mB=q求C=?ABCmbtmstgqthstgqtgqfgsfhbfhqfrnibf图4-1训练数据计算如下：对于类别为t的概率Pr(C=t)1pr(A=aIC=t)=Pr(C=t)-Pr(A=mIC=t)-Pr(B=qIC=t)=-x-xjj 25j=11类似的，对于类别为f的概率1Pr(C=f)弘(Ajj=1因此C=t的可能性较大，因此将此种情况下的类别判断为t。朴素贝叶斯分类将每篇文档看作一“袋子”的词，需要做以下假设，这也是称作“朴素的”贝叶斯的由来：•文档中的词都是独立于语境生成的。•单词被生成的概率是与它在文档中的位置无关的。•文档的长度与类别是无关的。通过公式推导，最后可以得到分类函数Pr(cId)xPr(c汕Pr(wIc)i i jij=1其中，Pr(wIc)=一入+(wj'ci)_。Tf(w,c)是词w在c.类训练文档

j'九IVI+兰TF(w,c) j' JJkik=1集中出现的频率，九是一个因子，一般设为九=l/n,n为训练数据的总数，当九=1时，称为拉普拉斯延续率。加入平滑算子的目的是解决不经常出现的单词零概率估计的问题，需要对概率进行平滑处理来避免出现0或1概率。▲朴素贝叶斯文本分类的优缺点虽然朴素贝叶斯学习所做的大部分假设都与实际情况不符，但研究表明朴素贝叶斯学习仍然能产生准确的模型。朴素贝叶斯学习效率很高，它只需要对训练数据进行一次扫描就可以估计出所有需要的概率，所以朴素贝叶斯在文本分类中得到了广泛的应用。3.5k最近邻算法(kNN算法)其他学习算法是从数据中得到一个模型，称为迫切学习，因为他们在测试之前学习得到了数据对应的模型。相反，k-近邻(kNearestNeighbor，kNN)是一种惰性的学习方法，因为不需要从训练数据中学习得到模型。学习仅仅在测试样例需要分类时发生。k近邻的想法很直接但是在很多场合很有效，例如文本分类。它是如下实现的：令D为训练数据集。不需要对训练样本做任何操作。当测试样例d出现时，算法将d和D中所有训练样例比较，计算它们之间的相似度(或者距离)。从D中选出前k个最相似(相近)的样本。这个样例集合被称为k-近邻。d的类别由k近邻中最常见的类别决定。如图6-1所示。

I-nearstneighbornearstneighbornearstneighborI-nearstneighbornearstneighbornearstneighbor图6-1k-近邻分类图示优点：kNN方法相当于非参数密度估计方法，在决策时只与极少量的相邻样本有关。另外，由于kNN方法主要靠周围有限的邻近的样本，因此对于类域的交叉或重叠较多的非线性可分数据来说，kNN方法较其他方法更为适合。缺点：kNN的一个不足是判断一个样本的类别时，需要把它与所有已知类别的样本都比较一遍，这样计算开销是相当大的。比如一个文本分类系统有上万个类，每个类即便只有20个训练样本，为了判断一个新样本的类别，也要做20万次的向量比较。这个问题可以通过对样本空间建立索引来弥补。kNN也有另一个不足是当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的k个邻居中大容量类的样本占多数，导致分类错误。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。产生了第一个不足。总结：目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。3・6、支持向量机（SVM）支持向量机（SupportVectorMachine）是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂（即对特定训练样本的学习精度,Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷,以期获得最好的推广（泛化）能力。▲VC维：是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。正是因为SVM关注的是VC维，后面可以看到，SVM解决问题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得SVM很适合用来解决文本分类的问题，当然，有这样的能力也因为引入了核函数）。核函数将原始的样本空间向高维空间进行变换，能够解决原始样本线性不可分的问题。▲结构风险：机器学习本质上就是一种对问题真实模型的逼近（选择一个我们认为比较好的近似模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不知道的，既然真实模型不知道，那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp（w）o以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却一塌糊涂（即所谓的推广能力差，或泛化能力差）。此时的情况即便是选择了一个足够复杂的分类函数（它的VC维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现，此原则适用的大前提是经验风险要确实能够逼近真实风险才行，但实际上能逼近么？答案是不能，因为样本数相对于现实世界要分类的文本数来说简直九牛一毛，经验风险最小化原则只在这占很小比例的样本上做到没有误差，当然不能保证在更大比例的真实文本上也没有误差。统计学习因此而引入了泛化误差界的概念，就是指真实风险应该由两部分内容刻画，一是经验风险，代表了分类器在给定样本上的误差；二是置信风险，代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然，第二部分是没有办法精确计算的，因此只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确的值（所以叫做泛化误差界，而不叫泛化误差）。置信风险与两个量有关，一是样本数量，显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数的VC维，显然VC维越大，推广能力越差，置信风险会变大。（匹配的可能性越小）泛化误差界的公式为：R（w}<Remp（w}+^（n/h）公式中R（w）就是真实风险，Remp（w）就是经验风险，①（n/h）就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。SVM正是这样一种努力最小化结构风险的算法。▲支持向量机：是将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。•先从最简单的线性可分学习，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的（如图5-1所示），否则称为非线性可分的。在一维空间里线性函数就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函数还有一个统一的名称 超平面（HyperPlane）图5-1线性可分的例子实际上，一个线性函数是一个实值函数（即函数的值是连续的实数），而我们的分类问题（例如这里的二元分类问题一一回答一个样本属于还是不属于一个类别的问题）需要离散的输出值，例如用1表示某个样本属于类别C1,而用0表示不属于（不属于C1也就意味着属于C2），这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。（前面提到的两类感知器类似）例如我们有一个线性函数g(x)=wx+b其中，x是样本的向量表示，wx+b=0是超平面，w是超平面的法向量。超平面不止一个，例如和图5-1中所示的超平面平行且可划分类别的直线都是一个超平面，因此，使用“分类间隔”来区分超平面的好坏。定义一个样本点到某个超平面的距离：8=y（wx+b）（称为函数间隔），III进行归一化，用旦和丄分别代替w和b,得8=—I（X，其中llwII是wIIw|| ||w|| ||wi的2-范数°（IIwII叫做向量w的范数，范数是对向量长度的一种度量。）归一化后的8•称作几何间隔，表示点到超平面的欧氏距离。误分次数与几何间隔存在关i系:误分次数＜迭代次数5是样本集合到分类面的几何间隔，R=maxllxII,i=l,...,n,即R是所有样i本中（气是以向量表示的第i个样本）向量长度最长的值。误分次数一定程度上代表分类器的误差。所以几何间隔越大，误分次数的上界越小。因此要选择几何间隔最大的超平面作为支持向量机米用的超平面。HlOHOH2 、°O\O—□wOD」■O□□margin=2w||图5-2支持向量机的超平面其中斗：wx+b=1；H：wx+b=O；H2：wx+b=-1支持向量：落在分类界面上的点（如落在H1和H2上的点）称作支持向量。•如何寻找最佳超平面，即最大化几何间隔，是训练阶段的目标。要使用通过二次优化问题（指目标函数为二次函数，约束条件为线性约束的最优化问题），得到的是全局最优解。由于：函数间隔：5i=yi（wxi+b）=lg（xi）l15二 Ig（x）l几何间隔：HwHi可以看出几何间隔与llwll是成反比的，因此最大化几何间隔与最小化llwll等价。而我们常用的方法并不是固定llwll的大小而寻求最大几何间隔，而是固定间隔即函数间隔，寻找最小的llwll。凡是求一个函数的最值的问题都可以称为寻优问题（也叫作一个规划问题）,又由于找最大值的问题总可以通过加一个负号变为找最小值的问题，因此我们下面讨论的时候都针对找最小值的过程来进行。一个寻优问题最重要的部分是目标函数。例如我们想寻找最小的llwll这件事，就可以用下面完全等价的目标函数来表示，那就是：不难看出当IIwll2达到最小时，llwll也达到最小，反之亦然（前提当然是llwll描述的是向量的长度，因而是非负的）。之所以采用这种形式，是因为后面的求解过程会对目标函数作一系列变换，会使变换后的形式更为简洁（如求导）。目标函数已求出，如果不考虑约束条件同样会造成错误，例如，IIwII最小化可以为0值，反映在图中，就是H1与H2两条直线间的距离无限大，这个时候，所有的样本点（无论正样本还是负样本）都跑到了H1和H2中间。所以要加入约束条件，约束条件就是在求解过程中必须满足的条件，体现在我们的问题中就是样本点必须在H1或H2的某一侧（或者至少在H1和H2上），而不能在两者中间。方便推导和优化的目的我们把间隔固定为1这是指把所有样本点中间隔最小的那一点的间隔定为1，也就意味着集合中的其他点间隔都不会小于1，按照间隔的定义，满足这些条件就相当于让下面的式子总是成立：yi[（w•xi）+b]-1$0（i=1,2,…,n）（n是总的样本数）因此我们的两类分类问题也被我们转化成了它的数学形式，一个带约束的最小值的问题：min斗11"『subjectto对（wx）]+b]-lM0（i=l,2,・・・,n）（n是总的样本数）自变量就是W，而目标函数是w的二次函数，所有的约束条件都是w的线性函数，这种规划称二次规划（QuadraticProgramming，QP），由于它的可行域是一个凸集，也是一个凸二次规划（特点：有解，同时也可以找到）。含有了带不等式的约束条件。将其转化为带等式的约束条件。使用拉格朗日理论求出条件极值。由于w由样本和类别确定，用数学的语言描述，就是w可以表示为样本的某种组合：w=ayx+ayx+...+ayx111 222 nnn这些a被称为拉格朗日乘子，而xi是样本点即向量，yi就是第i个样本的标签，n就是总样本点的个数。其中只有支持向量样本对应的a不为0，其他a都为0。式子也可以用求和符号简写一下：因此原来的g（x）表达式可以写为：g（x）=<W,X>r=l由于式子中只有xi和x是向量，因此一部分可以从内积符号中拿出来，得到g（x）的式子为：3g（x）=》>M<p>+bi=l其中X是变量，也就是你要分类哪篇文档，而所有的xi都是已知的样本。所以对于新点x的预测，只需要计算它与训练数据点的内积即可，这一点至关重要，是之后使用核函数进行非线性推广的基本前提。由于非SupportingVector所对应的系数a都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据。有该式还可以看出对w的求解转化为对a求解。（对偶变量dualvariable的优化问题：是解决此凸优化问题的第二种更为高效的解--对偶变量的优化求解。）完成了一个弱的SVM即只能处理线性的情况，不过，在得到了对偶dual形式之后，通过核函数（Kernel）推广到非线性的情况就变成了一件非常容易的事情了。•核函数前面已经了解到了SVM处理线性可分的情况，而对于非线性的情况，SVM的处理方法是选择一个核函数K（；），通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。由于核函数的优良品质，这样的非线性扩展在计算量上并没有比原来复杂多少。当然，这要归功于核函数一一除了SVM之外,任何将计算表示为数据点的内积的方法，都可以使用核函数进行非线性扩展。在线性不可分的情况下，支持向量机通过某种事先选择的非线性映射（核函数）将输入变量映射到一个高维特征空间，在这个空间中构造最优分类超平面。我们使用SVM进行数据集分类工作的过程首先是同预先选定的一些非线性映射将输入空间映射到高维特征空间（下图很清晰的表达了通过映射到高维特征空间，而把平面上本身不好分的非线性数据分了开来）：Separationmayheeiisierinhrglierdimensionsconripl^jcinlowdimensions simpleinhigherdimensionsconripl^jcinlowdimensions simpleinhigherdimensions使得在高维属性空间中有可能将训练数据实现超平面的分割，避免了在原输入空间中进行非线性曲面分割计算。SVM数据集形成的分类函数具有这样的性质：它是一组以支持向量为参数的非线性函数的线性组合，因此分类函数的表达式仅和支持向量的数量有关，而独立于空间的维度，在处理高维输入空间的分类时，这种方法尤其有效。用一个二维平面中的分类问题作例子：我们把横轴上端点a和b之间红色部分里的所有点定为正类，两边的黑色部分里的点定为负类。试问能找到一个线性函数把两类正确分开么？不能，因为二维空间里的线性函数就是指直线，显然找不到符合条件的直线。但我们可以找到一条曲线，例如下面这一条：显然通过点在这条曲线的上方还是下方就可以判断点所属的类别（你在横轴上随便找一点，算算这一点的函数值，会发现负类的点函数值一定比0大，而正类的一定比0小）。这条曲线就是我们熟知的二次曲线，它的函数表达式可以写为:它不是一个线性函数，转换为线性函数，新建一个向量y和a：£■"1_X,a■■这样g(x)就可以转化为f(y)=va,y>，实际上f(y)的形式就是：g(x)=f(y)=ay在任意维度(四维)的空间中，这种形式的函数都是一个线性函数(其中的a和y都是多(二)维向量，自变量y的次数不大于1)。而转化最关键的部分就在于找到x到y的映射方法。具体到文本分类问题，文本被表示为上千维的向量，即使维数已经如此之高，也常常是线性不可分的，还要向更高的空间转化。Eg：举具体文本分类的例子，看看这种向高维空间映射从而分类的方法如何运作，我们文本分类问题的原始空间是1000维的(即每个要被分类的文档被表示为一个1000维的向量)，在这个维度上问题是线性不可分的。现在我们有一个2000维空间里的线性函数f(x')=vw',x'>+b它能够将原问题变得可分。式中的w'和x'都是2000维的向量，只不过w'是定值，而x'是变量，现在我们的输入是一个1000维的向量X，分类的过程是先把x变换为2000维的向量x'，然后求这个变换后的向量x'与向量w'的内积，再把这个内积的值和b相加，就得到了结果，看结果大于阈值还是小于阈值就得到了分类结果。只关心那个高维空间里内积的值，分类结果就算出来了。核函数K(w,x)接受低维空间的输入值，却能算出高维空间的内积值vw',x'>。如果有这样的函数，那么当给了一个低维空间的输入x以后，g(x)=K(w,x)+b〃低维非线性函数f(x')=vw',x'>+b〃高维线性函数K(w,x)被称作核函数(核，kernel)，核函数的基本作用就是接受两个低维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。高维线性分类器，它的形式应该是：fax》呗VK>+bi=l可以用一个低维空间里的函数来代替，如下:g（H）=力oy店（抵x）+bi=if(x')和g(x)里的a,y,b是一样的，凡是要求内积的时候就用选定的核函数来算。这样求出来的a再和选定的核函数一组合，就得到分类器。针对具体问题，如何选择核函数对核函数的选择？现在还缺乏指导原则！•引入松弛变量问题引入：如果使用核函数向高维空间映射后，问题仍然是线性不可分的。圆形和方形的点各有成千上万个。假如，我们有另一个训练集，只比原先这个训练集多了一篇文章，映射到高维空间以后，也就多了一个样本点，但是这个样本的位置是这样的：图中黄色那个点，它是方形的丿因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。仅有少数点线性不可分叫做“近似线性可分”的问题。以我们人类的常识来判断，说有一万个点都符合某种规律(因而线性可分)，有一个点不符合，那这一个点是否就代表了分类规则中我们没有考虑到的方面呢(因而规则应该为它而做出修改)？其实更有可能的是，这个样本点压根就是错误，是噪声，是提供训练集的人工分类时不小心错放进去的。所以我们会简单的忽略这个样本点，仍然使用原来的分类器，其效果丝毫不受影响。但这种对噪声的容错性是人的思维带来的，程序可没有。由于优化问题的表达式中，要考虑所有的样本点，在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。因此由上面的例子中也可以看出，硬间隔的分类法其结果容易受少数点的控制。解决方法就是引入松弛变量，允许一些点到分类平面的距离不满足原先的要求。由于不同的训练集各点的间距尺度不太一样，因此用间隔（而不是几何间隔）来衡量有利于我们表达形式的简洁。原先对样本点的要求是：y[（wx）+b]>1（i=1,2,...,n）（n是样本数）ii意思是离分类面最近的样本点函数间隔也要比1大。如果要引入容错性，就给1这个硬性的阈值加一个松弛变量，即允许yi[（wxi）+b]>1-^i（i=1,2,・・・，n）（n为样本数）1/1/1/:i>0因为松弛变量是非负的，因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时（这些点也叫离群点），意味着放弃了对这些点的精确分类，而这对我们的分类器来说是种损失。但是放弃这些点也带来了好处,那就是使分类面不必向这些点的方向移动，因而可以得到更大的几何间隔（在低维空间看来，分类边界也更平滑）。显然我们必须权衡这种损失和好处。好处很明显，我们得到的分类间隔越大，好处就越多。回顾我们原始的硬间隔分类对应的优化问题：win i||w||2subjectto耳Ki眄）+切一40W'F）5是总的样本数），-Iw||22""就是我们的目标函数，越小越好，因而损失就必然是一个能使之变大的量。那如何来衡量损失，有两种常用的方式£匚2①i=1'

其中n都是样本的数目。两种方法没有大的区别。如果选择了第一种，得到的方法的就叫做二阶软间隔分类器，第二种就叫做一阶软间隔分类器。把损失加入到目标函数里的时候，就需要一个惩罚因子（cost，也就是libSVM的诸多参数中的C）,原来的优化问题就变成了下面这样：minminsubjecttoy[(wx)+b]>1-Q(i=1,2,...,n)(n是样本数)(式1)i i iQ>0这个式子有这么几点要注意：一、 并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有，没离群的点松弛变量都等于0（对负类来说，离群点就是在前面图中，跑到H2右侧的那些负样本点，对正类来说，就是跑到H1左侧的那些正样本点）。二、 松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点就越远。三、 惩罚因子C决定了你有多重视离群点带来的损失，显然当所有离群点的松弛变量的和一定时，C越大，对目标函数的损失也越大，此时就表示非常不愿意放弃这些离群点，最极端的情况是把C定为无限大，这样只要稍有一个点离群，目标函数的值变成无限大，让问题变成无解，这就退化成了硬间隔问题。四、 惩罚因子C不是一个变量，整个优化问题在解的时候，C是一个你必须事先指定的值，指定这个值以后，解一下，得到一个分类器，然后用测试数据看看结果怎么样，如果不够好，换一个C的值，再解一次优化问题，得到另一个分类器，再看看效果，如此就是一个参数寻优的过程，但这和优化问题本身决不是一回事，优化问题在解的过程中，C一直是定值。五、 尽管加了松弛变量，解它的过程比起原始的硬间隔问题来说是一样的。从大的方面说优化问题解的过程，就是先试着确定一下w，也就是确定了前面图中的三条直线，这时看看间隔有多大，又有多少点离群，把目标函数的值算一算，再换一组三条直线，再把目标函数的值算一算，如此往复（迭代），直到最终找到目标函数最小时的w。松弛变量和核函数的引入都是为了解决线性不可分的问题。松弛变量进一步解决线性不可分问题。以文本分类为例。在原始的低维空间中，样本相当的不可分，无论你怎么找分类平面，总会有大量的离群点，此时用核函数向高维空间映射一下，虽然结果仍然是不可分的，但比原始空间里的要更加接近线性可分的状态（即达到了近似线性可分的状态），此时再用松弛变量处理那些少数的离群点，就简单有效得多了。本节中的（式1）是支持向量机最最常用的形式。至此一个比较完整的支持向量机框架就有了。简单说来，支持向量机就是使用了核函数的软间隔线性分类法。•SVM用于多类分类SVM是一种典型的两类分类器，即它只回答属于正类还是负类的问题。而现实中要解决的问题，往往是多类的问题（少部分例外，例如垃圾邮件过滤，就只需要确定“是”还是“不是”垃圾邮件），比如文本分类，比如数字识别。如何由两类分类器得到多类分类器，在此有三种方法。以文本分类为例，现成的方法有很多，其中最好就是一次性考虑所有样本，次性求解的方法计算量实在太大，基本实现不了。①一类对其余的方法，就是每次仍然解一个两类分类的问题。比如我们有5个类别，第一次就把类别1的样本定为正样本，其余2,3,4,5的样本合起来定为负样本，这样得到一个两类分类器，它能够指出一篇文章是还是不是第1类的；第二次我们把类别2的样本定为正样本，把1，3,4,5的样本合起来定为负样本，得到一个分类器，如此下去，我们可以得到5个这样的两类分类器（总是和类别的数目一致）。文章分类时，挨个分类器进行分类，最终确定文章的类别。这种方法的好处是每个优化问题的规模比较小，而且分类的时候速度很快（只需要调用5个分类器就知道了结果）。但有时也会出现两种很尴尬的情况，

例如拿一篇文章问了一圈，每一个分类器都说它是属于它那一类的，或者每一个分类器都说它不是它那一类的，前者叫分类重叠现象，后者叫不可分类现象。分类重叠时随便选一个结果都可，或者看看这篇文章到各个超平面的距离，哪个远就判给哪个。不可分类时很难解决，由于各个类别的样本数目是差不多的，但“其余”的那一类样本数总是要数倍于正类，这就人为的造成了“数据集偏斜”问题。一对一的方法，还是解两类分类问题，还是每次选一个类的样本作正类样本，而负类样本则变成只选一个类，这就避免了偏斜。过程就是算出这样一些分类器，第一个只回答“是第1类还是第2类”，第二个只回答“是第1类还是第3类”，第三个只回答“是第1类还是第4类”，如此下去。这样的分类器应该有5X4/2=10个（通式是，如果有k个类别，则总的两类分类器数目为k（k-1）/2）。