毕业论文线性分类平分最近点法的matlab实现

1、毕 业 论 文（2006届）线性分类平分最近点法的MATLAB实现学生姓名 朱益锋 学 号 02044142 豆丁文档最好豆丁文档最好英语数学标志销售英语数学标志销售院 系 数理信息学院 专 业 信息与计算科学 指导教师 盛宝怀 完成日期 2006年6月3日 线性分类平分最近点法的MATLAB实现摘 要本文主要介绍了线性分类平分最近点法的理论和主要的思想，运用数学上的理论，对其算法进行了详细的分析，最后转化为求一个凸二次规划的最优解的问题，并提出运用MATLAB对凸二次规划问题进行求解。并且用具体的例子进行了计算。通过对平分最近点法的理论、算法及其思想的研究，本文最后还提出了推广的平分最近点法

2、算法。关键词 线性分类；平分最近点；学习机；凸壳THE REALIZATION OF MATLABUSING LINEAR CLASSIFICATION AMONG RECENT POINT ABSTRACTThe paper mainly introduces the theory of linear classification and its main thinking.It uses the mathematical theory to make a detailed analysis of its calculation,finally it is converted to the

3、best solution of the second protrude planning,And it also proposes to use MATLAB to solve the issue of second protrude planning.The specific examples are listed to calculate it.At last,The paper also presents the extended calculation of the recent points through the research of the recent point theo

4、ry and its calculation as well as its thinking. KEY WORDS Linear classification; Among recent point; Learning motive; protrude carcasses 目 录中文摘要 . 1英文摘要 . 2目录 . 3前言 . 41.线性分类最近点法的MATLAB实现. 61.1问题的提出. 6 1.1.1例子. 6 1.1.2分类问题和分类学习机. 7 1.2 线性分类学习机. 10 1.2.1线性可分问题的线性分划. 10 1.线性可分问题与凸壳. 10 2.平分最近点法. 11 3.

5、推广的平分最近点法. 17小结 . 19参考文献. 19致谢. 20前 言在社会生活和经济、军事活动中，经常碰到各种各样最优化现象，如人力资源如何配置、导弹的最佳射程等，为了取得尽可能好的结果，都想用自己最好的方法，这就是最优问题 分类问题研究决策主体的行为发生在处理大量数据时，人们如何进行分类直接影响到解决问题的好坏平分最近点法是研究线性分类的理论在线性分类分析中，一般都要处理大量的数据，算法的好坏直接影响结果和效率，通过选择最佳算法，来寻求最优化在现实生活中具有普遍性，因此，因此很多最优问题都可以通过分类来解决线性分类在政治学、军事学、生物进化学、心理学、社会学、伦理学、经济学等许多领域都

6、有着广泛的应用在医学中分类问题作为一种重要的分析方法已渗透到几乎所有的领域，每一领域的最新进展都应用了分类问题，分类问题已经成为主流医学的一部分，对医学理论正产生越来越重要的影响当代，分类问题已经在天气预报、卫星航空图片解释、工业产品检测、字符识别、语音识别、指纹识别、医学图像分析、临床医学等许多方面得到了成功的应用。所有这些应用都是和问题的性质密不可分的，至今还没有发展成统一的有效的可应用于所有的分类问题的理论。通过数学家、信息学专家和计算机科学工作者、生理学家、心理学家、生物学家、神经生理学家近几十年来的努力，已经取得了系统的研究成果。寻找一种方法去解决多个问题也成为社会发展的需要鉴于以上

7、几点，我觉得有必要对线性分类的相关知识以及在现代研究领域中如何运用平分最近点法解决最优的问题作进一步探讨，使这种方法在现代经济社会中发挥更好的作用，同时希望能通过编写一个有效的算法，来体现它在实际应用中的价值至今，国内外许多人士对分类问题及其在各方面的应用都有研究：邓乃扬 田英杰编著的数据挖掘中的新方法：支持向量机支持向量机能非常成功地处理回归问题(时间序列分析)和模式识别(分类问题、判别分析)等诸多问题，并可推广于预测和综合评价等领域，因此可应用于理科、工科和管理等多种学科目前国际上支持向量机在理论研究和实际应用两方面都正处于飞速发展阶段希望本书能促进它在我国的普及与提高吴培今、孙德山编著的

8、现在数据分析中从数据的分类方面作了详细的论述，试图构建数据分析的一个平台。P.S.Bradley, O.L.Mangasarian, and W.N.Street, Feature selection via mathematical programming, INFORMS Journal on Computing, 1998，209-217，也作了很多的研究。郑纬明黄刚数据挖掘纵览清华大学出版社1998，论述了分类问题的一些方法。华中理工大学学报（李庆华），对在限制条件下的线性分类算法的研究。对其算法的构造，及其性能的优劣都做了详细的介绍。1.线性分类最近点法的MATLAB实现1.1问题的

9、提出1.1.1例子（心脏病诊断）完全确诊某些疾病，可能需要进行创伤性探测或者昂贵的手段。因此利用一些有关的容易获得的临床指标进行推断，是一项有意义的工作。美国Cleveland Heart Disease Database提供的数据，就是这方面工作的一个实例。在那些对297个病人进行了彻底的临床检测，确诊了他们是否有心脏病。这类问题称为分类问题（classification），也称为模式识别问题，在概率统计中则称为判别分析问题。在本文中我们采用“分类问题”这一术语。为了叙述方便，我们对上述问题加以简化，得到下面示意性的例子。例 假定是否患有心脏病与病人的年龄和胆固醇水平密切相关，下表对应10个

10、病人的临床数据：病人编号年龄x1胆固醇水平x2有否心脏病1x1=60x2=165= -12x1=57x2=150= -110x1= 70x2=190= -1表中=1表示该病人属于正类，即有心脏病；= -1表示该病人属于负类，即无心脏病。在这里第1位病人的数据是x1=(x11,x12)T=(60,165)T,y1= -1 ；第2位病人的数据是x2=(x21,x22)T=(57,150)T,y2= -1 ；第10位病人的数据是x10=(x101,x102)T=(70,190)T,y1= 1 。这些数据可综合为T=(x1,y1),(x10,y10)。 （1-1）现在的问题是，对新来的一位病人，已得知

11、他的年龄x1和胆固醇水平x2，试推断他是否有心脏病，即求对应的y是1还是-1。这个问题是一个2维空间上的分类问题，可以在平面直角坐标系中描述如下：根据病人的2项指标和有无心脏病，把每个病人用一个样本点来表示，参看图1-1样本点的两个坐标由2项指标确定，点的形状由有无心脏病确定：有心脏病者用“+”形点，无心脏病者用圆形点。如第2个病人用图中的最左下方的圆形点来表示。新来一位病人相当于给了平面上的一个点x，现在的问题是要推断它属于正类（y=1）还是负类（y=-1）。换句话说，我们需要把平面划分成两部分，使得当该点落入其中一部分时，推断该病人属于正类；而落入另一部分时，推断他属于负类，关键是如何划分

12、平面。 x2195- 165- 150- 57 60 70 x1 图1-1观察图1-1标出的两类点，可以考虑选择一条适当的直线（）把平面划分成两部分，其中（）是(1,2)T和(1, 2)T的内积。而把直线的两侧分别归为正类和负类。或者说可以按下列方式推断点x所对应的y， （1-2）其中是符号函数 （1-3）当然我们也可以考虑用一般的非线性函数代替线性函数，这样可以得到更灵活的划分方法。1.1.2分类问题和分类学习机前面讲的例子，是一个具体的2维空间上的分类问题，它包含2个指标（即）和10个样本点。一般地，可考虑n维空间上的分类问题，它包含n个指标（即）和个样本点的集合为， （1-4）其中是输入

13、指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标：是输出指标，或称输出，。这个样本点组成的集合称为训练集，所以我们也称样本点为训练点。这时我们的问题是，对任意给定的一个新的模式x，根据训练集，推断它所对应的输出y是1还是-1。用数学语言可以把分类问题描述如下：分类问题 根据给定的训练集，其中，寻找上的一个实值函数，以便用决策函数 （1-5）推断任一模式x相对应的y值。由此可见，求解分类问题，实质上就是找到一个把上的点分成两部分的规则。确切地说，上述分类问题是分成两类的问题。与分成两类的分类问题类似，还有分成多类的分类问题，它们的不同之处仅在于前者的输出只取两个值，而后者则可取多

14、个值，除非特别说明，我们以后说“分类问题”均指分成两类的分类问题。参照机器学习领域中的术语，我们把解决上述分类问题的方法称为分类学习机。当为线性函数，由决策函数（1-5）确定分类准则时，称为线性分类学习机；当为非线性函数时，称为非线性分类学习机。不难想像，分类问题大体有三种类型：对于不同类型的问题，可能需要采用不同的分类学习机。我们还是以输入为2维向量的分类问题为例，从直观上给予以说明。首先，对于图1-2所示的问题，很容易用一条直线把训练集正确地分开（即两类点分别在直线的两侧，没有错分点），这类问题称为线性可分问题。这时显然可以使用简单的线性分类学习机。其次，对于图1-所示的问题，用一条直线也

15、能大体上把训练集正确分开，这类问题称为近似线性可分问题，这时仍可以考虑使用线性学习分类机。最后，对于图1-4所示的问题，显然这时用直线分划会产生很大的误差，这类问题称为（实质）线性不可分问题。这时就必须使用非线性分类学习机了。以下我们将依次讨论线性可分问题，近似线性可分问题和实质线性不可分问题，并建立相应的分类学习机。+ +图1-2+ + 图1-3。 。 。 。+ + + + + + +图1-41.2 线性分类学习机1.2.1 线性可分问题的线性分划1.线性可分问题与凸壳图1-5所示的训练集可以用直线正确分开，这类问题称为线性可分问题，其确切定义如下。定义1.2.1（线性可分） 考虑式（1-4

16、）所示的训练集，其中，。若存在和正数，使得对所有使的下标，有，而对所有使的下标，有，则称训练集线性可分。同时我们也称相应的分类问题是线性可分的。现在考虑线性可分问题的特征，容易想像，它与训练集中正类点集的凸壳和负类点集的凸壳密切相关（关于凸壳的定义请参见附录A）。事实上，我们有下列定理定理1.2.2 考虑训练集，其中，。则线性可分的充分必要条件是，的正类点集的凸壳和负类点集的凸壳不相交。证明 我们分别证明必要性和充分性。必要性 若是线性可分的，则由定义1.2.1，知存在超平面和正数，使得且。 （1-6）而正类点集的凸壳中的任一点和负类点集的凸壳中的任一点可分别表为和， （1-7）其中所有且，。

17、 （1-8）于是由式（1-6）（1-8）有， （1-9）（1-10）由此可见，正类两类点集的凸壳都不与超平面相交，而且它们位于该超平面的两侧。因此这两个凸壳不相交。充分性 设两类点集的凸壳不相交。因为两个凸壳都是闭凸集，且有界，根据凸集强分离定理，可知存在一个超平面强分离这两个凸壳，即存在正数，使得对正负两类点的凸壳中的任意点和分别有， 。 （1-11）显然特别地，对任意的和，分别有且。 （1-12）于是由定义1.2.1可知训练集是线性可分的。2. 平分最近点法现在考虑对线性可分问题如何构造线性分类学习机，或者直观地说，如何进行线性分划？首先来看一维空间上的分类问题。设给定直线上线性可分的两类

18、点正类“+”形点和负类圆形点，如图1-5所示，看来最合理的划分是以线段的中点为分界点，把在点左方和右方的点分别归入正类和负类。如果分别做正类点和负类点的凸壳（线段和），和恰好是这两个凸壳的最近点，可见，我们应该采取“平分”最近点的策略。对于2维空间上的分类问题。可以采取类似的做法。假设已知图1-6给出的两类点，我们还是可以考虑分别做它们的凸壳，找到这两个凸壳的最近点和，作线段的垂直平分线，以此直线把平面划分成两部分。m+ + + + + a c d b图1-5 直线上两类点的线性分划+ +e+ c+ +f b 图1-6 平分最近点法在这里，如何寻求两个凸壳的最近点和呢？这可以通过求解一个最优化

19、问题来解决。事实上，设给定训练集，其中，。它的正类点的凸壳的任何一点可以表示为，它的负类点的凸壳的任何一点可以表示为，其中满足， （1-13）所以要寻求这两个凸壳的最近点和，只需在约束（1-13）下，求解以为变量的函数的极小点。这样便可得到两个凸壳的就近点和。在得到这两个点和后，便可计算线段的垂直平分线就是我们欲求的分划直线。上述做法也可以推广到一般的维空间上的分类问题，从而得到下列算法。算法1.2.3（平分最近点法）（1）设已知训练集，其中，；（2）构造并求解最优问题 ， （1-14） ， （1-15）， （1-16）得其最优解；（3）计算两个最近点和；（4）构造分划超平面，其中，。由此求得

20、决策函数，其中是符号函数。定理1.2.4 若训练集是线性可分的，则平分最近点法求出的分划超平面存在唯一，且此分划超平面能将训练集中的两类点完全正确地分开。证明 因为问题（1-14）（1-16）的可行域是有界闭集，所以它必有最优解，因此，为证明平分最近点法能构造出超平面，只需证明由问题（1-14）（1-16）的最优解构造的。事实上，因为训练集是线性可分的，所以根据定理1.2.2知两类点的凸壳不相交，所以上述平分最近点法找到的两个最近点和不会重合，因而。另外，易证所构造的超平面能将训练集中的两类点正确分开，于是为完成定理的证明，只需证明所构造超平面的唯一性。设和为问题（1-14）（1-16）的两个

21、最优解，相应的两个最近点分别为，和，。此时所构造的超平面分别为和。为证明超平面的唯一性，只需证明和。先证明。因为和都是问题（1-14）（1-16）的最优解，所以其目标函数值相等，从而有 ， （1-17）其中是某个正数，令 ，。 （1-18）显然和分别属于两个凸壳，从而有。 （1-19）上式表明式中的第二个不等式号可加强为等号，所以，其中是常数。由式（1-17）可知。若，则有，即两凸壳相交，显然矛盾，所以。即有 ， （1-20）即算法构造的唯一。 现在证明。由于正类点集的凸壳是一个非空闭凸集，不属于这个凸壳，是该凸壳中距最近的点，由闭凸集投影定理知，对该凸壳中的任意点有 。 （1-21）特别地，

22、对，也应有。同理，因为也不属于这个凸壳，是该凸壳中距离最近的点，可知，由式（1-20），可记 。 （1-22）所以有 。 （1-23）同理，针对负类点集的凸壳，也可以得到 ， （1-24）由式（1-23）（1-24）和式（1-22）有 ， 。 （1-25）所以，即算法构造的唯一，再结合的唯一性，即知分划超平面是唯一的。 注1.2.5 在以上证明中我们并未假设（1-14）（1-16）有唯一的解，这是因为它是一个凸二次规划问题，而可能是非严格凸的，因而解可能不唯一。上述定理表明，即使所求得的问题（1-14）（1-16）的解可能不同，但所构造的分划超平面却是相同的。下面对算法1.2.3进行研究.其实

23、就是求解一个凸二次规划的问题： ， ， ， 对于这个二次规划问题，经典的解法有积极方法、对偶方法、内点算法等，但是随着样本数目的增多，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间，该二次寻优过程需要占用大量内存空间，往往会导致无法训练，因此，设计一个快速有效的算法求解，从而更好的应用于实际是近年来研究的热点。下面主要是计算我们假设当时，；当时，那么经过计算可以得到：为了讨论简单，我们取，那么上述可以简化为：为了计算方便，我们取,那么上式可以化为：，那么二次凸规划问题可以变为： , , .现在可以求解的最优解.用MATLAB

24、程序为：先给H，C，A，b赋值 H=4,2,2,4;2,1,1,2;2,1,1,2;4,2,2,4; C=0,0,0,0; A=1,1,0,0;0,0,1,1;-1,0,0,0;0,-1,0,0;0,0,-1,0;0,0,0,-1; B=1,1,0,0,0,0;在调用优化程序qp =qp(H,C,A,b);即得最优解： = 0.1.0.1得到两个最近点和；即c=-1;d=1;那么，=-2；=0；超平面；由此求得决策函数=.3推广的平分最近点法考虑图1-7（a）所示的2维空间的分类问题。因为它是线性不可分问题，所以它的两类点的两个凸壳已相交，平分最近点法已不适用，然而如果能够适当缩小这两个凸壳，

25、使得缩小后的两个凸壳不再相交，就有可能对缩小后的两个凸壳进行“平分最近点”了。ew+ d + + (a) (b)图1-7推广的平分最近点法对给定的训练集，其中，它的正类点的凸壳的任何一点可以表示为 . （1-26）缩小这个凸壳的一种方式是，取参数，并把式（1-26）中的不等式加强为，即把正类点的凸壳缩小为. （1-27）这里参数D是一个比例因子。当D逐渐减小时，相应的凸壳会逐渐缩小。用同样的方式也可以把负类点的凸壳缩小。图1-7（b）画出了取D=0.5时缩小后的两个凸壳。当两个缩小后的凸壳不再相交时，就可以求它们的最近点，从而得到平分它们的分划超平面。这样我们就得到了如下算法。算法1.3.1（

26、推广的平分最近点）（1）设已知训练集，其中，；（2）选择适当的常数，构造并求解对变量的最优化问题 ， （1-28） ， （1-29）， （1-30）得其最优解；（3）计算两个最近点和；（4）构造分划超平面，其中，。由此求得决策函数，其中是符号函数。本文推广的平分最近点法不做详细的介绍，有兴趣的读者可以继续研究。结束语平分最近点是基于统计学习理论的新一代学习机器，具有很多吸引人的特点，它在函数表达能力、推广能力和学习效率上都要优于传统的，在实际应用中也解决了许多问题，但由于出现比较晚，还处于发展阶段，尤其是其算法实现方面存在着效率低下的问题，这也是限制其很好地应用于数据挖掘中的一个瓶颈。因此设计

27、一个快速有效的算法来处理数据挖掘中的海量数据分类是目前需要岌待解决的问题，将扎实的理论背景和快速的算法相结合应用于数据挖掘中将会使数据的分类过程大大简化，对数据挖掘的发展会有一定的促进作用。参考文献1 王碧泉，陈祖荫. 模式识别理论、方法和应用. 北京：地震出版社，1989.2. 基于支持向量机的决策系统知识发现魏 玲1,祁建军2,张文修1(1.西安交通大学理学院, 710049 ,西安; 2.西安交通大学电子与信息工程学院, 710049 ,西安).3.张学工. 关于统计学习理论与支持向量机. 自动化学报，2000；26(1) : 3244.4.邓乃扬 、田英杰编著的数据挖掘中的新方法：支持向量机.科学出版2004.5.吴培今、孙德山编著的现代数据分析.机械工业出版社，2006.6 郑纬明黄刚数据挖掘纵览清华大学出版社1998 .7 边肇祺模式识别清华大学出版社