畢業(yè)論文線性分類平分最近點法的matlab實現(xiàn)

1、畢 業(yè) 論 文（2006屆）線性分類平分最近點法的MATLAB實現(xiàn)學生姓名 朱益鋒 學 號 02044142 豆丁文檔最好豆丁文檔最好英語數(shù)學標志銷售英語數(shù)學標志銷售院 系 數(shù)理信息學院 專 業(yè) 信息與計算科學 指導教師 盛寶懷 完成日期 2006年6月3日 線性分類平分最近點法的MATLAB實現(xiàn)摘 要本文主要介紹了線性分類平分最近點法的理論和主要的思想，運用數(shù)學上的理論，對其算法進行了詳細的分析，最后轉(zhuǎn)化為求一個凸二次規(guī)劃的最優(yōu)解的問題，并提出運用MATLAB對凸二次規(guī)劃問題進行求解。并且用具體的例子進行了計算。通過對平分最近點法的理論、算法及其思想的研究，本文最后還提出了推廣的平分最近點法

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實現(xiàn). 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前 言在社會生活和經(jīng)濟、軍事活動中，經(jīng)常碰到各種各樣最優(yōu)化現(xiàn)象，如人力資源如何配置、導彈的最佳射程等，為了取得盡可能好的結果，都想用自己最好的方法，這就是最優(yōu)問題 分類問題研究決策主體的行為發(fā)生在處理大量數(shù)據(jù)時，人們?nèi)绾芜M行分類直接影響到解決問題的好壞平分最近點法是研究線性分類的理論在線性分類分析中，一般都要處理大量的數(shù)據(jù)，算法的好壞直接影響結果和效率，通過選擇最佳算法，來尋求最優(yōu)化在現(xiàn)實生活中具有普遍性，因此，因此很多最優(yōu)問題都可以通過分類來解決線性分類在政治學、軍事學、生物進化學、心理學、社會學、倫理學、經(jīng)濟學等許多領域都

6、有著廣泛的應用在醫(yī)學中分類問題作為一種重要的分析方法已滲透到幾乎所有的領域，每一領域的最新進展都應用了分類問題，分類問題已經(jīng)成為主流醫(yī)學的一部分，對醫(yī)學理論正產(chǎn)生越來越重要的影響當代，分類問題已經(jīng)在天氣預報、衛(wèi)星航空圖片解釋、工業(yè)產(chǎn)品檢測、字符識別、語音識別、指紋識別、醫(yī)學圖像分析、臨床醫(yī)學等許多方面得到了成功的應用。所有這些應用都是和問題的性質(zhì)密不可分的，至今還沒有發(fā)展成統(tǒng)一的有效的可應用于所有的分類問題的理論。通過數(shù)學家、信息學專家和計算機科學工作者、生理學家、心理學家、生物學家、神經(jīng)生理學家近幾十年來的努力，已經(jīng)取得了系統(tǒng)的研究成果。尋找一種方法去解決多個問題也成為社會發(fā)展的需要鑒于以上

7、幾點，我覺得有必要對線性分類的相關知識以及在現(xiàn)代研究領域中如何運用平分最近點法解決最優(yōu)的問題作進一步探討，使這種方法在現(xiàn)代經(jīng)濟社會中發(fā)揮更好的作用，同時希望能通過編寫一個有效的算法，來體現(xiàn)它在實際應用中的價值至今，國內(nèi)外許多人士對分類問題及其在各方面的應用都有研究：鄧乃揚 田英杰編著的數(shù)據(jù)挖掘中的新方法：支持向量機支持向量機能非常成功地處理回歸問題(時間序列分析)和模式識別(分類問題、判別分析)等諸多問題，并可推廣于預測和綜合評價等領域，因此可應用于理科、工科和管理等多種學科目前國際上支持向量機在理論研究和實際應用兩方面都正處于飛速發(fā)展階段希望本書能促進它在我國的普及與提高吳培今、孫德山編著的

8、現(xiàn)在數(shù)據(jù)分析中從數(shù)據(jù)的分類方面作了詳細的論述，試圖構建數(shù)據(jù)分析的一個平臺。P.S.Bradley, O.L.Mangasarian, and W.N.Street, Feature selection via mathematical programming, INFORMS Journal on Computing, 1998，209-217，也作了很多的研究。鄭緯明黃剛數(shù)據(jù)挖掘縱覽清華大學出版社1998，論述了分類問題的一些方法。華中理工大學學報（李慶華），對在限制條件下的線性分類算法的研究。對其算法的構造，及其性能的優(yōu)劣都做了詳細的介紹。1.線性分類最近點法的MATLAB實現(xiàn)1.1問題的

9、提出1.1.1例子（心臟病診斷）完全確診某些疾病，可能需要進行創(chuàng)傷性探測或者昂貴的手段。因此利用一些有關的容易獲得的臨床指標進行推斷，是一項有意義的工作。美國Cleveland Heart Disease Database提供的數(shù)據(jù)，就是這方面工作的一個實例。在那些對297個病人進行了徹底的臨床檢測，確診了他們是否有心臟病。這類問題稱為分類問題（classification），也稱為模式識別問題，在概率統(tǒng)計中則稱為判別分析問題。在本文中我們采用“分類問題”這一術語。為了敘述方便，我們對上述問題加以簡化，得到下面示意性的例子。例 假定是否患有心臟病與病人的年齡和膽固醇水平密切相關，下表對應10個

10、病人的臨床數(shù)據(jù)：病人編號年齡x1膽固醇水平x2有否心臟病1x1=60x2=165= -12x1=57x2=150= -110x1= 70x2=190= -1表中=1表示該病人屬于正類，即有心臟病；= -1表示該病人屬于負類，即無心臟病。在這里第1位病人的數(shù)據(jù)是x1=(x11,x12)T=(60,165)T,y1= -1 ；第2位病人的數(shù)據(jù)是x2=(x21,x22)T=(57,150)T,y2= -1 ；第10位病人的數(shù)據(jù)是x10=(x101,x102)T=(70,190)T,y1= 1 。這些數(shù)據(jù)可綜合為T=(x1,y1),(x10,y10)。 （1-1）現(xiàn)在的問題是，對新來的一位病人，已得知

11、他的年齡x1和膽固醇水平x2，試推斷他是否有心臟病，即求對應的y是1還是-1。這個問題是一個2維空間上的分類問題，可以在平面直角坐標系中描述如下：根據(jù)病人的2項指標和有無心臟病，把每個病人用一個樣本點來表示，參看圖1-1樣本點的兩個坐標由2項指標確定，點的形狀由有無心臟病確定：有心臟病者用“+”形點，無心臟病者用圓形點。如第2個病人用圖中的最左下方的圓形點來表示。新來一位病人相當于給了平面上的一個點x，現(xiàn)在的問題是要推斷它屬于正類（y=1）還是負類（y=-1）。換句話說，我們需要把平面劃分成兩部分，使得當該點落入其中一部分時，推斷該病人屬于正類；而落入另一部分時，推斷他屬于負類，關鍵是如何劃分

12、平面。 x2195- 165- 150- 57 60 70 x1 圖1-1觀察圖1-1標出的兩類點，可以考慮選擇一條適當?shù)闹本€（）把平面劃分成兩部分，其中（）是(1,2)T和(1, 2)T的內(nèi)積。而把直線的兩側分別歸為正類和負類?；蛘哒f可以按下列方式推斷點x所對應的y， （1-2）其中是符號函數(shù) （1-3）當然我們也可以考慮用一般的非線性函數(shù)代替線性函數(shù)，這樣可以得到更靈活的劃分方法。1.1.2分類問題和分類學習機前面講的例子，是一個具體的2維空間上的分類問題，它包含2個指標（即）和10個樣本點。一般地，可考慮n維空間上的分類問題，它包含n個指標（即）和個樣本點的集合為， （1-4）其中是輸入

13、指標向量，或稱輸入，或稱模式，其分量稱為特征，或?qū)傩?，或輸入指標：是輸出指標，或稱輸出，。這個樣本點組成的集合稱為訓練集，所以我們也稱樣本點為訓練點。這時我們的問題是，對任意給定的一個新的模式x，根據(jù)訓練集，推斷它所對應的輸出y是1還是-1。用數(shù)學語言可以把分類問題描述如下：分類問題 根據(jù)給定的訓練集，其中，尋找上的一個實值函數(shù)，以便用決策函數(shù) （1-5）推斷任一模式x相對應的y值。由此可見，求解分類問題，實質(zhì)上就是找到一個把上的點分成兩部分的規(guī)則。確切地說，上述分類問題是分成兩類的問題。與分成兩類的分類問題類似，還有分成多類的分類問題，它們的不同之處僅在于前者的輸出只取兩個值，而后者則可取多

14、個值，除非特別說明，我們以后說“分類問題”均指分成兩類的分類問題。參照機器學習領域中的術語，我們把解決上述分類問題的方法稱為分類學習機。當為線性函數(shù)，由決策函數(shù)（1-5）確定分類準則時，稱為線性分類學習機；當為非線性函數(shù)時，稱為非線性分類學習機。不難想像，分類問題大體有三種類型：對于不同類型的問題，可能需要采用不同的分類學習機。我們還是以輸入為2維向量的分類問題為例，從直觀上給予以說明。首先，對于圖1-2所示的問題，很容易用一條直線把訓練集正確地分開（即兩類點分別在直線的兩側，沒有錯分點），這類問題稱為線性可分問題。這時顯然可以使用簡單的線性分類學習機。其次，對于圖1-所示的問題，用一條直線也

15、能大體上把訓練集正確分開，這類問題稱為近似線性可分問題，這時仍可以考慮使用線性學習分類機。最后，對于圖1-4所示的問題，顯然這時用直線分劃會產(chǎn)生很大的誤差，這類問題稱為（實質(zhì)）線性不可分問題。這時就必須使用非線性分類學習機了。以下我們將依次討論線性可分問題，近似線性可分問題和實質(zhì)線性不可分問題，并建立相應的分類學習機。+ +圖1-2+ + 圖1-3。 。 。 。+ + + + + + +圖1-41.2 線性分類學習機1.2.1 線性可分問題的線性分劃1.線性可分問題與凸殼圖1-5所示的訓練集可以用直線正確分開，這類問題稱為線性可分問題，其確切定義如下。定義1.2.1（線性可分） 考慮式（1-4

16、）所示的訓練集，其中，。若存在和正數(shù)，使得對所有使的下標，有，而對所有使的下標，有，則稱訓練集線性可分。同時我們也稱相應的分類問題是線性可分的?，F(xiàn)在考慮線性可分問題的特征，容易想像，它與訓練集中正類點集的凸殼和負類點集的凸殼密切相關（關于凸殼的定義請參見附錄A）。事實上，我們有下列定理定理1.2.2 考慮訓練集，其中，。則線性可分的充分必要條件是，的正類點集的凸殼和負類點集的凸殼不相交。證明 我們分別證明必要性和充分性。必要性 若是線性可分的，則由定義1.2.1，知存在超平面和正數(shù)，使得且。 （1-6）而正類點集的凸殼中的任一點和負類點集的凸殼中的任一點可分別表為和， （1-7）其中所有且，。

17、 （1-8）于是由式（1-6）（1-8）有， （1-9）（1-10）由此可見，正類兩類點集的凸殼都不與超平面相交，而且它們位于該超平面的兩側。因此這兩個凸殼不相交。充分性 設兩類點集的凸殼不相交。因為兩個凸殼都是閉凸集，且有界，根據(jù)凸集強分離定理，可知存在一個超平面強分離這兩個凸殼，即存在正數(shù)，使得對正負兩類點的凸殼中的任意點和分別有， 。 （1-11）顯然特別地，對任意的和，分別有且。 （1-12）于是由定義1.2.1可知訓練集是線性可分的。2. 平分最近點法現(xiàn)在考慮對線性可分問題如何構造線性分類學習機，或者直觀地說，如何進行線性分劃？首先來看一維空間上的分類問題。設給定直線上線性可分的兩類

18、點正類“+”形點和負類圓形點，如圖1-5所示，看來最合理的劃分是以線段的中點為分界點，把在點左方和右方的點分別歸入正類和負類。如果分別做正類點和負類點的凸殼（線段和），和恰好是這兩個凸殼的最近點，可見，我們應該采取“平分”最近點的策略。對于2維空間上的分類問題。可以采取類似的做法。假設已知圖1-6給出的兩類點，我們還是可以考慮分別做它們的凸殼，找到這兩個凸殼的最近點和，作線段的垂直平分線，以此直線把平面劃分成兩部分。m+ + + + + a c d b圖1-5 直線上兩類點的線性分劃+ +e+ c+ +f b 圖1-6 平分最近點法在這里，如何尋求兩個凸殼的最近點和呢？這可以通過求解一個最優(yōu)化

19、問題來解決。事實上，設給定訓練集，其中，。它的正類點的凸殼的任何一點可以表示為，它的負類點的凸殼的任何一點可以表示為，其中滿足， （1-13）所以要尋求這兩個凸殼的最近點和，只需在約束（1-13）下，求解以為變量的函數(shù)的極小點。這樣便可得到兩個凸殼的就近點和。在得到這兩個點和后，便可計算線段的垂直平分線就是我們欲求的分劃直線。上述做法也可以推廣到一般的維空間上的分類問題，從而得到下列算法。算法1.2.3（平分最近點法）（1）設已知訓練集，其中，；（2）構造并求解最優(yōu)問題 ， （1-14） ， （1-15）， （1-16）得其最優(yōu)解；（3）計算兩個最近點和；（4）構造分劃超平面，其中，。由此求得

20、決策函數(shù)，其中是符號函數(shù)。定理1.2.4 若訓練集是線性可分的，則平分最近點法求出的分劃超平面存在唯一，且此分劃超平面能將訓練集中的兩類點完全正確地分開。證明 因為問題（1-14）（1-16）的可行域是有界閉集，所以它必有最優(yōu)解，因此，為證明平分最近點法能構造出超平面，只需證明由問題（1-14）（1-16）的最優(yōu)解構造的。事實上，因為訓練集是線性可分的，所以根據(jù)定理1.2.2知兩類點的凸殼不相交，所以上述平分最近點法找到的兩個最近點和不會重合，因而。另外，易證所構造的超平面能將訓練集中的兩類點正確分開，于是為完成定理的證明，只需證明所構造超平面的唯一性。設和為問題（1-14）（1-16）的兩個

21、最優(yōu)解，相應的兩個最近點分別為，和，。此時所構造的超平面分別為和。為證明超平面的唯一性，只需證明和。先證明。因為和都是問題（1-14）（1-16）的最優(yōu)解，所以其目標函數(shù)值相等，從而有 ， （1-17）其中是某個正數(shù)，令 ，。 （1-18）顯然和分別屬于兩個凸殼，從而有。 （1-19）上式表明式中的第二個不等式號可加強為等號，所以，其中是常數(shù)。由式（1-17）可知。若，則有，即兩凸殼相交，顯然矛盾，所以。即有 ， （1-20）即算法構造的唯一。 現(xiàn)在證明。由于正類點集的凸殼是一個非空閉凸集，不屬于這個凸殼，是該凸殼中距最近的點，由閉凸集投影定理知，對該凸殼中的任意點有 。 （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）有唯一的解，這是因為它是一個凸二次規(guī)劃問題，而可能是非嚴格凸的，因而解可能不唯一。上述定理表明，即使所求得的問題（1-14）（1-16）的解可能不同，但所構造的分劃超平面卻是相同的。下面對算法1.2.3進行研究.其實

23、就是求解一個凸二次規(guī)劃的問題： ， ， ， 對于這個二次規(guī)劃問題，經(jīng)典的解法有積極方法、對偶方法、內(nèi)點算法等，但是隨著樣本數(shù)目的增多，而求解二次規(guī)劃將涉及m階矩陣的計算（m為樣本的個數(shù)），當m數(shù)目很大時該矩陣的存儲和計算將耗費大量的機器內(nèi)存和運算時間，該二次尋優(yōu)過程需要占用大量內(nèi)存空間，往往會導致無法訓練，因此，設計一個快速有效的算法求解，從而更好的應用于實際是近年來研究的熱點。下面主要是計算我們假設當時，；當時，那么經(jīng)過計算可以得到：為了討論簡單，我們?nèi)?，那么上述可以簡化為：為了計算方便，我們?nèi)?那么上式可以化為：，那么二次凸規(guī)劃問題可以變?yōu)椋?, , .現(xiàn)在可以求解的最優(yōu)解.用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;在調(diào)用優(yōu)化程序qp =qp(H,C,A,b);即得最優(yōu)解： = 0.1.0.1得到兩個最近點和；即c=-1;d=1;那么，=-2；=0；超平面；由此求得決策函數(shù)=.3推廣的平分最近點法考慮圖1-7（a）所示的2維空間的分類問題。因為它是線性不可分問題，所以它的兩類點的兩個凸殼已相交，平分最近點法已不適用，然而如果能夠適當縮小這兩個凸殼，

25、使得縮小后的兩個凸殼不再相交，就有可能對縮小后的兩個凸殼進行“平分最近點”了。ew+ d + + (a) (b)圖1-7推廣的平分最近點法對給定的訓練集，其中，它的正類點的凸殼的任何一點可以表示為 . （1-26）縮小這個凸殼的一種方式是，取參數(shù)，并把式（1-26）中的不等式加強為，即把正類點的凸殼縮小為. （1-27）這里參數(shù)D是一個比例因子。當D逐漸減小時，相應的凸殼會逐漸縮小。用同樣的方式也可以把負類點的凸殼縮小。圖1-7（b）畫出了取D=0.5時縮小后的兩個凸殼。當兩個縮小后的凸殼不再相交時，就可以求它們的最近點，從而得到平分它們的分劃超平面。這樣我們就得到了如下算法。算法1.3.1（

26、推廣的平分最近點）（1）設已知訓練集，其中，；（2）選擇適當?shù)某?shù)，構造并求解對變量的最優(yōu)化問題 ， （1-28） ， （1-29）， （1-30）得其最優(yōu)解；（3）計算兩個最近點和；（4）構造分劃超平面，其中，。由此求得決策函數(shù)，其中是符號函數(shù)。本文推廣的平分最近點法不做詳細的介紹，有興趣的讀者可以繼續(xù)研究。結束語平分最近點是基于統(tǒng)計學習理論的新一代學習機器，具有很多吸引人的特點，它在函數(shù)表達能力、推廣能力和學習效率上都要優(yōu)于傳統(tǒng)的，在實際應用中也解決了許多問題，但由于出現(xiàn)比較晚，還處于發(fā)展階段，尤其是其算法實現(xiàn)方面存在著效率低下的問題，這也是限制其很好地應用于數(shù)據(jù)挖掘中的一個瓶頸。因此設計

27、一個快速有效的算法來處理數(shù)據(jù)挖掘中的海量數(shù)據(jù)分類是目前需要岌待解決的問題，將扎實的理論背景和快速的算法相結合應用于數(shù)據(jù)挖掘中將會使數(shù)據(jù)的分類過程大大簡化，對數(shù)據(jù)挖掘的發(fā)展會有一定的促進作用。參考文獻1 王碧泉，陳祖蔭. 模式識別理論、方法和應用. 北京：地震出版社，1989.2. 基于支持向量機的決策系統(tǒng)知識發(fā)現(xiàn)魏 玲1,祁建軍2,張文修1(1.西安交通大學理學院, 710049 ,西安; 2.西安交通大學電子與信息工程學院, 710049 ,西安).3.張學工. 關于統(tǒng)計學習理論與支持向量機. 自動化學報，2000；26(1) : 3244.4.鄧乃揚 、田英杰編著的數(shù)據(jù)挖掘中的新方法：支持向量機.科學出版2004.5.吳培今、孫德山編著的現(xiàn)代數(shù)據(jù)分析.機械工業(yè)出版社，2006.6 鄭緯明黃剛數(shù)據(jù)挖掘縱覽清華大學出版社1998 .7 邊肇祺模式識別清華大學出版社