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

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

2、算法。關(guān)鍵詞 線性分類(lèi)；平分最近點(diǎn)；學(xué)習(xí)機(jī)；凸殼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.線性分類(lèi)最近點(diǎn)法的MATLAB實(shí)現(xiàn). 61.1問(wèn)題的提出. 6 1.1.1例子. 6 1.1.2分類(lèi)問(wèn)題和分類(lèi)學(xué)習(xí)機(jī). 7 1.2 線性分類(lèi)學(xué)習(xí)機(jī). 10 1.2.1線性可分問(wèn)題的線性分劃. 10 1.線性可分問(wèn)題與凸殼. 10 2.平分最近點(diǎn)法. 11 3.

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

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

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

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

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

10、病人的臨床數(shù)據(jù)：病人編號(hào)年齡x1膽固醇水平x2有否心臟病1x1=60x2=165= -12x1=57x2=150= -110x1= 70x2=190= -1表中=1表示該病人屬于正類(lèi)，即有心臟病；= -1表示該病人屬于負(fù)類(lèi)，即無(wú)心臟病。在這里第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(mén)=(x1,y1),(x10,y10)。 （1-1）現(xiàn)在的問(wèn)題是，對(duì)新來(lái)的一位病人，已得知

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

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

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

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

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

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

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

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

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

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

21、最優(yōu)解，相應(yīng)的兩個(gè)最近點(diǎn)分別為，和，。此時(shí)所構(gòu)造的超平面分別為和。為證明超平面的唯一性，只需證明和。先證明。因?yàn)楹投际菃?wèn)題（1-14）（1-16）的最優(yōu)解，所以其目標(biāo)函數(shù)值相等，從而有 ， （1-17）其中是某個(gè)正數(shù)，令 ，。 （1-18）顯然和分別屬于兩個(gè)凸殼，從而有。 （1-19）上式表明式中的第二個(gè)不等式號(hào)可加強(qiáng)為等號(hào)，所以，其中是常數(shù)。由式（1-17）可知。若，則有，即兩凸殼相交，顯然矛盾，所以。即有 ， （1-20）即算法構(gòu)造的唯一。 現(xiàn)在證明。由于正類(lèi)點(diǎn)集的凸殼是一個(gè)非空閉凸集，不屬于這個(gè)凸殼，是該凸殼中距最近的點(diǎn)，由閉凸集投影定理知，對(duì)該凸殼中的任意點(diǎn)有 。 （1-21）特別地，

22、對(duì)，也應(yīng)有。同理，因?yàn)橐膊粚儆谶@個(gè)凸殼，是該凸殼中距離最近的點(diǎn)，可知，由式（1-20），可記 。 （1-22）所以有 。 （1-23）同理，針對(duì)負(fù)類(lèi)點(diǎn)集的凸殼，也可以得到 ， （1-24）由式（1-23）（1-24）和式（1-22）有 ， 。 （1-25）所以，即算法構(gòu)造的唯一，再結(jié)合的唯一性，即知分劃超平面是唯一的。 注1.2.5 在以上證明中我們并未假設(shè)（1-14）（1-16）有唯一的解，這是因?yàn)樗且粋€(gè)凸二次規(guī)劃問(wèn)題，而可能是非嚴(yán)格凸的，因而解可能不唯一。上述定理表明，即使所求得的問(wèn)題（1-14）（1-16）的解可能不同，但所構(gòu)造的分劃超平面卻是相同的。下面對(duì)算法1.2.3進(jìn)行研究.其實(shí)

23、就是求解一個(gè)凸二次規(guī)劃的問(wèn)題： ， ， ， 對(duì)于這個(gè)二次規(guī)劃問(wèn)題，經(jīng)典的解法有積極方法、對(duì)偶方法、內(nèi)點(diǎn)算法等，但是隨著樣本數(shù)目的增多，而求解二次規(guī)劃將涉及m階矩陣的計(jì)算（m為樣本的個(gè)數(shù)），當(dāng)m數(shù)目很大時(shí)該矩陣的存儲(chǔ)和計(jì)算將耗費(fèi)大量的機(jī)器內(nèi)存和運(yùn)算時(shí)間，該二次尋優(yōu)過(guò)程需要占用大量?jī)?nèi)存空間，往往會(huì)導(dǎo)致無(wú)法訓(xùn)練，因此，設(shè)計(jì)一個(gè)快速有效的算法求解，從而更好的應(yīng)用于實(shí)際是近年來(lái)研究的熱點(diǎn)。下面主要是計(jì)算我們假設(shè)當(dāng)時(shí)，；當(dāng)時(shí)，那么經(jīng)過(guò)計(jì)算可以得到：為了討論簡(jiǎn)單，我們?nèi)?，那么上述可以?jiǎn)化為：為了計(jì)算方便，我們?nèi)?那么上式可以化為：，那么二次凸規(guī)劃問(wèn)題可以變?yōu)椋?, , .現(xiàn)在可以求解的最優(yōu)解.用MATLAB

24、程序?yàn)椋合冉oH，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得到兩個(gè)最近點(diǎn)和；即c=-1;d=1;那么，=-2；=0；超平面；由此求得決策函數(shù)=.3推廣的平分最近點(diǎn)法考慮圖1-7（a）所示的2維空間的分類(lèi)問(wèn)題。因?yàn)樗蔷€性不可分問(wèn)題，所以它的兩類(lèi)點(diǎn)的兩個(gè)凸殼已相交，平分最近點(diǎn)法已不適用，然而如果能夠適當(dāng)縮小這兩個(gè)凸殼，

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

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

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