基于K近鄰的分類算法研究

沈陽航空航天大學(xué).專業(yè)整理.4.學(xué)習(xí)幫手..專業(yè)整理..學(xué)習(xí)幫手.沈陽航空航天大學(xué)ShenyangAerospaceUniversity算法分析題目：基于K-近鄰分類算法的研究院系計算機學(xué)院專業(yè)計算機技術(shù)姓名學(xué)號指導(dǎo)教師2015年1月.學(xué)習(xí)幫手..學(xué)習(xí)幫手.摘要數(shù)據(jù)挖掘是機器學(xué)習(xí)領(lǐng)域內(nèi)廣泛研究的知識領(lǐng)域，是將人工智能技術(shù)和數(shù)據(jù)庫技術(shù)緊密結(jié)合，讓計算機幫助人們從龐大的數(shù)據(jù)中智能地、自動地提取出有價值的知識模式，以滿足人們不同應(yīng)用的需要。K近鄰算法（KNN）是基于統(tǒng)計的分類方法，是數(shù)據(jù)挖掘分類算法中比較常用的一種方法。該算法具有直觀、無需

先驗統(tǒng)計知識、無師學(xué)習(xí)等特點，目前已經(jīng)成為數(shù)據(jù)挖掘技術(shù)的理論和應(yīng)用研究方法之一。本文主要研究了K近鄰分類算法。首先簡要地介紹了數(shù)據(jù)挖掘中的各種分類算法，詳細(xì)地闡述了K近鄰算法的基本原理和應(yīng)用領(lǐng)域，其次指出了K近鄰算法的計算速度慢、分類準(zhǔn)確度不高的原因，提出了兩種新的改進方法。針對K近鄰算法的計算量大的缺陷，構(gòu)建了聚類算法與K近鄰算法相結(jié)合的一種方法。將聚類中的K-均值和分類中的K近鄰算法有機結(jié)合。有效地提高了分類算法的速度。針對分類準(zhǔn)確度的問題，提出了一種新的距離權(quán)重設(shè)定方法。傳統(tǒng)的KNN算法一般采用歐式距離公式度量兩樣本間的距離。由于在實際樣本數(shù)據(jù)集合中每一個屬性對樣本的貢獻作用是不盡相同的，通常采用加權(quán)歐式距離公式。本文提出一種新的計算權(quán)重的方法。實驗表明，本文提出的算法有效地提高了分類準(zhǔn)確度。最后，在總結(jié)全文的基礎(chǔ)上，指出了有待進一步研究的方向。關(guān)鍵詞：K近鄰，聚類算法，權(quán)重，復(fù)雜度，準(zhǔn)確度ABSTRACTDataminingisawidelyfieldofmachinelearning,anditintegratestheartificialintelligencetechnologyanddatabasetechnology.Ithelpspeopleextractvaluableknowledgefromalargedataintelligentlyandautomaticallytomeetdifferentpeopleapplications.KNNisausedmethodindataminingbasedonStatistic.Thealgorithmhasbecomeoneofthewaysindataminingtheoryandapplicationbecauseofintuitive,withoutprioristatisticalknowledge,andnostudyfeatures.Themainworksofthisthesisisknearestneighborclassificationalgorithm.First,itintroducesmainlyclassificationalgorithmsofdatamininganddescriptstheoreticalbaseandapplication.Thispaperpointsoutthereasonsofslowandlowaccuracyandproposestwoimprovedways.InordertoovercomethedisadvantagesoftraditionalKNN,thispaperusetwoalgorithmsofclassificationandclusteringtoproposeanimprovedKNNclassificationalgorithm.Experimentsshowthatthisalgorithmcanspeedupwhenithasafeweffectsinaccuracy.Accordingtotheproblemofclassificationaccuracy,thepaperproposesanewcalculationofweight.KNNthetraditionalmethodgenerallyusedContinentaldistanceformulameasurethedistancebetweenthetwosamples.Astheactualsampledatacollectionineveryattributeofasampleofthecontributionisnotthesame,oftenusingtheweightedContinentaldistanceformula.Thispaperpresentsacalculationofweight，thatisweightedbasedonthecharacteristicsofKNNalgorithm.AccordingtothisExperimentsonartificialdatasetsshowthatthisalgorithmcanimprovetheaccuracyofclassification.Last,thepaperindicatesthedirectionofresearchinfuturebasedonthefull-text.Keywords:KNearestNeighbor,ClusteringAlgorithm,FeatureWeighted,ComplexDegree,ClassificationAccuracy.前言K最近鄰(k-Nearest

\o"neighbor"neighbor，\o"KNN"KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學(xué)習(xí)算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成正比。該算法在分類時有個主要的不足是，當(dāng)樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當(dāng)輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。該算法只計算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標(biāo)樣本，或者這類樣本很靠近目標(biāo)樣本。無論怎樣，數(shù)量并不能影響運行結(jié)果。可以采用權(quán)值的方法（和該樣本距離小的鄰\o"居權(quán)"居權(quán)值大）來改進。

該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分.學(xué)習(xí)幫手.目錄摘要 IABSTRACT II前言 III1緒論 11.1選題背景和研究現(xiàn)狀 11.1.1數(shù)據(jù)挖掘 11.1.2國內(nèi)外研究現(xiàn)狀 21.2研究內(nèi)容和目的 31.2.1研究內(nèi)容 31.2.2研究目的 42 K-近鄰分類算法 62.1分類算法 62.1.1數(shù)據(jù)分類 62.1.2分類方法 72.2基于實例的學(xué)習(xí)算法 102.3K-近鄰方法 102.3.1最近鄰分類算法簡介 102.3.2K-近鄰算法實現(xiàn) 112.4算法分析 112.4.1算法實現(xiàn) 112.4.2算法的優(yōu)缺點 122.4.3KNN的改進 133 算法應(yīng)用 153.1k—近鄰算法在肝癌檢測中的應(yīng)用 153.2面向延遲敏感性應(yīng)用 153.3改進的K-近鄰算法在中文網(wǎng)頁分類的應(yīng)用 16總結(jié) 17致謝 18參考文獻 19.學(xué)習(xí)幫手.1緒論1.1選題背景和研究現(xiàn)狀1.1.1數(shù)據(jù)挖掘隨著數(shù)據(jù)庫技術(shù)的飛速發(fā)展，人工智能領(lǐng)域的一個分支——機器學(xué)習(xí)的研究自20世紀(jì)50年代開始以來也取得了很大進展。用數(shù)據(jù)庫管理系統(tǒng)來存儲數(shù)據(jù)，用機器學(xué)習(xí)的方法來分析數(shù)據(jù)，挖掘大量數(shù)據(jù)背后的知識，這兩者的結(jié)合促成了數(shù)據(jù)庫中的知識發(fā)現(xiàn)（KnowledgeDiscoveryinDatabases，簡記KDD）的產(chǎn)生，也稱作數(shù)據(jù)挖掘（DataMing，簡記DM）。數(shù)據(jù)挖掘是信息技術(shù)自然演化的結(jié)果。信息技術(shù)的發(fā)展大致可以描述為如下的過程：初期的是簡單的數(shù)據(jù)收集和數(shù)據(jù)庫的構(gòu)造；后來發(fā)展到對數(shù)據(jù)的管理，包括：數(shù)據(jù)存儲、檢索以及數(shù)據(jù)庫事務(wù)處理；再后來發(fā)展到對數(shù)據(jù)的分析和理解，這時候出現(xiàn)了數(shù)據(jù)倉庫技術(shù)和數(shù)據(jù)挖掘技術(shù)。數(shù)據(jù)挖掘是涉及數(shù)據(jù)庫和人工智能等學(xué)科的一門當(dāng)前相當(dāng)活躍的研究領(lǐng)域。數(shù)據(jù)挖掘是機器學(xué)習(xí)領(lǐng)域內(nèi)廣泛研究的知識領(lǐng)域，是將人工智能技術(shù)和數(shù)據(jù)庫技術(shù)緊密結(jié)合，讓計算機幫助人們從龐大的數(shù)據(jù)中智能地、自動地抽取出有價值的知識模式，以滿足人們不同應(yīng)用的需要[1]。目前，數(shù)據(jù)挖掘已經(jīng)成為一個具有迫切實現(xiàn)需要的很有前途的熱點研究課題。數(shù)據(jù)挖掘技術(shù)能從數(shù)據(jù)倉庫中自動分析數(shù)據(jù)，進行歸納性推理，從中發(fā)掘出潛在的模式，或產(chǎn)生聯(lián)想，建立新的業(yè)務(wù)模型，這是一個高級的處理過程。高級的處理過程是指一個多步驟的處理過程，多步驟之間相互影響、反復(fù)調(diào)整，形成一種螺旋式上升過程。數(shù)據(jù)挖掘的功能用于指定數(shù)據(jù)挖掘任務(wù)中要找的模式類型，其任務(wù)一般分為兩類：描述和預(yù)測。描述性挖掘任務(wù)刻畫數(shù)據(jù)庫中數(shù)據(jù)的一般特性，預(yù)測性挖掘任務(wù)在當(dāng)前數(shù)據(jù)上進行推斷，以進行預(yù)測。在實際應(yīng)用中，往往根據(jù)模式的實際應(yīng)用細(xì)分為以下六種：①分類模式；②回歸模式；③時間序列模式；④聚類模式；⑤關(guān)聯(lián)模式；⑥序列模式。在解決實際問題時，經(jīng)常要同時使用多種模式。分類模式和回歸模式是使用最普遍的模式。分類模式、回歸模式、時間序列模式也被認(rèn)為是受監(jiān)督的知識，因為在建立模式前數(shù)據(jù)的結(jié)果是已知的，可以直接用來檢測模式的準(zhǔn)確性，模式的產(chǎn)生是在受監(jiān)督的情況下進行的。一般在建立這些模式時，使用一部分?jǐn)?shù)據(jù)作為樣本，用另一部分?jǐn)?shù)據(jù)來檢驗、校正模式。聚類模式、關(guān)聯(lián)模式、序列模式則是非監(jiān)督知識，因為在模式建立前模式是未知的，模式的產(chǎn)生不受任何監(jiān)[2]。1.1.2國內(nèi)外研究現(xiàn)狀本論文主要研究的是數(shù)據(jù)挖掘分類算法中的K近鄰算法。國內(nèi)外學(xué)者針對此算法做了許多研究工作。例如文獻[3]研究了計算復(fù)雜性的優(yōu)化和分析方法以及如何減少計算量的做法等。香港中文大學(xué)的WaiLam等人KNN方法和線性分類器結(jié)合，取得了較好的分類效果，在召回率接近90%時準(zhǔn)確率超過80%[4]。WlodzislawDuch提出了通過選取特征對加權(quán)KNN算法的研究[5]。文獻[4]提出了一種基于近鄰搜索的快速K近鄰分類算法——超球搜索法。該方法通過對特征空間的預(yù)組織，使分類能在以待分樣本為中心的超球內(nèi)進行。超球半徑由零開始逐漸增大至超球內(nèi)包含K個以上模式樣本為止。這一方法有效地縮小了算法搜索范圍，同時預(yù)組織和預(yù)分類簡單明了，無需復(fù)雜的訓(xùn)練，不存在收斂性問題。文獻[8]研究了回歸函數(shù)K-近鄰估計的漸進性質(zhì)，得到了回歸函數(shù)的K-近鄰估計的漸進正態(tài)性和它的Bootstrap統(tǒng)計量的相合性。文獻[5]為近鄰算法建立一個有效的搜索樹，提高了查詢速率。文獻[6]提出了一種迭代近鄰法，用以解決KNN算法在小樣本庫的環(huán)境下分類效果不佳的問題，在無法得到足夠的定類樣本時，通過檢索的方法將待分樣本的局部主題特征放大，進而得到足夠定類的相似樣本。文獻[7]分析了傳統(tǒng)的近鄰文本分類方法技術(shù)以及Web文本的特點，充分利用了Web文本的結(jié)構(gòu)信息進行特征詞加權(quán)，以類軸向量為核心構(gòu)建分類器。文獻[8]提出了加權(quán)K近鄰的方法，對訓(xùn)練集X內(nèi)的每一個樣本點，給定一個臨界半徑，對一個待識別樣本，比較其與訓(xùn)練集中每個樣本點的加權(quán)距離。文獻[9]針對歐幾里德空間的K近鄰，給出了在可重構(gòu)網(wǎng)孔機器上(RMESH)的并行算法等。1.2研究內(nèi)容和目的1.2.1研究內(nèi)容近鄰方法是在一組歷史數(shù)據(jù)記錄中尋找一個或者若干個與當(dāng)前記錄最相似的歷史紀(jì)錄的已知特征值來預(yù)測當(dāng)前記錄的未知或遺失特征值[9]。近鄰方法是數(shù)據(jù)挖掘分類算法中比較常用的一種方法。K近鄰算法（簡稱KNN）是基于統(tǒng)計的分類方法[15]。KNN分類算法根據(jù)待識樣本在特征空間中K個最近鄰樣本中的多數(shù)樣本的類別來進行分類，因此具有直觀、無需先驗統(tǒng)計知識、無師學(xué)習(xí)等特點，從而成為非參數(shù)分類的一種重要方法。大多數(shù)分類方法是基于向量空間模型的。當(dāng)前在分類方法中，對任意兩個向量：x=（x1,x2,…,xn）與x’=(x1’,x2’,…xn’)存在3種最通用的距離度量：歐氏距離、余弦[16]和內(nèi)積[17]。有兩種常用的分類策略：一種是計算待分類向量到所有訓(xùn)練集中的向量間的距離：如K近鄰選擇K個距離最小的向量然后進行綜合，以決定其類別。另一種是用訓(xùn)練集中的向量構(gòu)成類別向量，僅計算待分類向量到所有3類別向量的距離，選擇一個距離最小的類別向量決定類別的歸屬。很明顯，距離計算在分類中起關(guān)鍵作用。由于以上3種距離度量不涉及向量的特征之間的關(guān)系，這使得距離的計算不精確，從而影響分類的效果。下面分3種情況說明：①無用特征的影響：在分類算法的向量空間模型中，向量常常是多維的。所謂無用特征是指與類別無關(guān)的特征。也就是各個類別中均可以出現(xiàn)的特征，它不代表類別的特點,必須要進行刪除，否則他們將會導(dǎo)致距離的計算不準(zhǔn)確，即向量間的距離遠(yuǎn)近將被無關(guān)特征的出現(xiàn)所影響。②特征間關(guān)系的影響：我們認(rèn)為如果不考慮特征間的關(guān)系，距離的計算同樣會存在問題。例如在文本分類中，可分兩種情況說明：一種是同義詞的影響，另一種是具有某種語義關(guān)聯(lián)詞的影響。③特征間地位不平等性的影響：特征對類別支持作用大小盡管可用權(quán)值大小來體現(xiàn)，但我們覺得還不夠。存在一些特征對類別具有較強的支持作用（決策特征），它們的存在可以在很大程度上決定類別的歸屬。而在向量空間模型中，這種決策作用將被眾多非決策特征的影響所淹沒掉。其次對于K近鄰算法中，選取不同的K值對分類結(jié)果有較大的影響，也就是說，不同的K值直接決定分類結(jié)果的正確率。如圖1.1所示：圖1.1K值對分類的影響其中具有空心方格和實心圓圈兩類數(shù)據(jù)，待測數(shù)據(jù)點（問號代表）如果采用1近鄰則其所屬類別應(yīng)該是如圖所示的屬于方格類，如果采用3近鄰則屬于圓圈類。所以說，采用怎樣的K近鄰個數(shù)是分類結(jié)果正確與否的關(guān)鍵條件之一。最后查找近鄰的效率問題也是值得研究的一項內(nèi)容。K近鄰分類算法需要進行全局搜索，計算的時間復(fù)雜度大，速度慢。當(dāng)訓(xùn)練集數(shù)據(jù)量非常大時，尋找近鄰就需要相應(yīng)的提高效率算法，使得查找速度提高。像在文中1.1.2中所述的，目前已有的一些快速K近鄰分類算法，盡管在提高快速性方面作了一些改進，但是有的需要事先進行大量復(fù)雜的訓(xùn)練并且存在著收斂性問題，有的同樣需要進行全局搜索并且對搜索順序有較強的敏感性。分類算法中，KNN算法是實現(xiàn)簡單、分類效果較好的一種方法。1.2.2研究目的本論文主要針對KNN算法的計算速度慢，準(zhǔn)確度不高的缺點進行改進，提出一種能在保持準(zhǔn)確度的前提下減少搜索范圍、有效提高算法速度的改進方法。雖然許多學(xué)者都在這兩個方面做了大量的研究，但還存在著一些值得研究的問題。針對KNN算法計算量大的缺點，目前提出較多的快速算法主要有分塊Voronoi圖方法，但是速度的改善均不是很大。本文利用分塊的策略，提出一種KNN與聚類算法相結(jié)合的改進算法，使得能夠在對準(zhǔn)確度影響不大的前提下提高算法的收斂速度。其次針對分類準(zhǔn)確度的問題，構(gòu)造新的相似性度量或特征權(quán)重型的距離度量，以達到提高分類的準(zhǔn)確度的目的。最后可以嘗試關(guān)于特征選擇方面的研究，以達到能同時提高速度和準(zhǔn)確度。以上三個方面在新的算法提出之后可以通過實例驗證算法的可行性并與常規(guī)分類算法進行比較，以驗證算法的優(yōu)越性。2 K-近鄰分類算法2.1分類算法2.1.1數(shù)據(jù)分類分類模式挖掘技術(shù)作為數(shù)據(jù)挖掘的重要分支將對電信、銀行、保險、零售、醫(yī)療等諸多行業(yè)提供決策支持，對未來商業(yè)和人們的生活也將產(chǎn)生深遠(yuǎn)的影響。數(shù)據(jù)分類（DataClassification）是數(shù)據(jù)挖掘中一項非常重要的任務(wù)，目前在商業(yè)上應(yīng)用最多。分類的目的是學(xué)會一個分類函數(shù)或者分類模型（也常常稱為分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個。例如：可以建立一個分類模型，對銀行貸款的安全或風(fēng)險進行分類。許多分類的方法已被機器學(xué)習(xí)、專家系統(tǒng)、統(tǒng)計學(xué)和神經(jīng)生物學(xué)方面的研究者提出。數(shù)據(jù)分類實際上就是從數(shù)據(jù)庫對象中發(fā)現(xiàn)共性，并將數(shù)據(jù)對象分成不同類別的一個過程，可分成兩步進行（圖2.1）。第一步，建立一個模型，描述預(yù)定的數(shù)據(jù)類集或概念集。通過分析由屬性描述的數(shù)據(jù)元組來構(gòu)造模型。假定每個元組屬于一個預(yù)定義的類，有一個類標(biāo)號屬性（ClassLabelAttribute）的屬性確定。對于分類，數(shù)據(jù)元組也稱為樣本、實例或者對象。為建立模型而被分析的數(shù)據(jù)元組形成訓(xùn)練數(shù)據(jù)集（TrainingSet）。訓(xùn)練數(shù)據(jù)集中的單個元組稱為訓(xùn)練樣本，并隨機的從樣本集中選取。由于預(yù)先知道每個訓(xùn)練樣本的類標(biāo)號，這個建立模型的學(xué)習(xí)過程屬于有指導(dǎo)的學(xué)習(xí)，即模型的學(xué)習(xí)是在知道每個訓(xùn)練樣本屬于哪個類的指導(dǎo)下進行的。這不同于無指導(dǎo)的學(xué)習(xí)（如聚類），無指導(dǎo)的學(xué)習(xí)中每個訓(xùn)練樣本的類標(biāo)號事先是未知的，要學(xué)習(xí)的類集合或者數(shù)量也是事先不知道，整個學(xué)習(xí)的過程是在無指導(dǎo)的情況下進行的。通常，通過第一步的學(xué)習(xí)建立的模型用分類規(guī)則、決策樹或數(shù)據(jù)公式的形式表示。如給定一個顧客信用信息的數(shù)據(jù)庫，通過分類算法學(xué)習(xí)得出分類規(guī)則，根據(jù)這些規(guī)則，決定顧客的信譽好壞。即這些規(guī)則就是分類模型，可以利用這個模型對其他數(shù)據(jù)樣本進行分類，同時也能對數(shù)據(jù)庫的內(nèi)容提供更好的理解。圖2.1（a）表示一種學(xué)習(xí)過程：在訓(xùn)練數(shù)據(jù)上用分類算法學(xué)習(xí)，學(xué)習(xí)模型用分類規(guī)則的形式表示。圖2.1（a）學(xué)習(xí)過程測試數(shù)據(jù)分類規(guī)則新數(shù)據(jù)圖2.1（b）分類過程第二步圖2.1（b）表示一種分類過程：在測試數(shù)據(jù)上評估分類規(guī)則的準(zhǔn)確率，如果準(zhǔn)確率可以接受，則分類規(guī)則可用于新的數(shù)據(jù)的分類。首先要評估模型的預(yù)測準(zhǔn)確率。最常用的一種方法是保持（HoldOut）方法，該方法使用類標(biāo)號樣本測試集，這些樣本隨機選取，并獨立于訓(xùn)練樣本集，即測試樣本集完全不同于訓(xùn)練樣本集。模型在測試樣本集上的準(zhǔn)確率是指被模型正確分類的測試樣本的百分比。對于每個測試樣本，按照分類模型學(xué)習(xí)得出的預(yù)測類別與已知的類別標(biāo)號進行比較，如果相同，則表示分類成功；不相同，表示分類不成功。使用完全不同于訓(xùn)練樣本集的測試樣本集，是因為學(xué)習(xí)模型傾向于過分適合數(shù)據(jù)，即學(xué)習(xí)模型可能并入訓(xùn)練數(shù)據(jù)中某些特別的異常數(shù)據(jù)，而這些異常不出現(xiàn)在總體樣本集中。如果仍使用訓(xùn)練數(shù)據(jù)評估分類模型，則可能評估總是樂觀的。如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以利用該模型對類標(biāo)號未知的數(shù)據(jù)元組或?qū)ο筮M行分類。如在通過分析現(xiàn)有顧客數(shù)據(jù)學(xué)習(xí)得到的分類規(guī)則可以預(yù)測新的顧客信譽的好壞。分類算法具有廣泛的應(yīng)用，包括信譽證實、學(xué)習(xí)用戶興趣、性能預(yù)測、市場調(diào)查[21]、新聞分發(fā)[22]、郵件分類以及醫(yī)療診斷等。2.1.2分類方法目前，有多種分類方法和算法，主要有統(tǒng)計方法、機器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法等。分類算法一般分為Lazy和Eager兩種類型。Lazy學(xué)習(xí)算法思想是從局部出發(fā)，推遲對訓(xùn)練例子的歸納過程，直到一個新的測試?yán)映霈F(xiàn)，例如K近鄰（KNearestNeighbor）算法、局部加權(quán)回歸（LocallyWeightedRegression）、基于案例的推理（Case-basedReasoning）等；而Eager學(xué)習(xí)算法則是從全局出發(fā)，在新的測試?yán)映霈F(xiàn)之前，由訓(xùn)練例子總結(jié)歸納出相似判斷的目標(biāo)函數(shù)，這個目標(biāo)函數(shù)應(yīng)用于訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)，例如決策樹（DecisionTree）、BP（Back-Propagation）神經(jīng)網(wǎng)絡(luò)算法、徑向基函數(shù)（RadialBasisFunctions）、遺傳分類方法、粗糙集分類方法等。我們將在2.3中以K近鄰舉例介紹Lazy算法，現(xiàn)以決策樹為例介紹Eager方法。歸納學(xué)習(xí)旨在從大量的經(jīng)驗數(shù)據(jù)中歸納和提取一般的判定規(guī)則和模式，它是機器學(xué)習(xí)最核心、最成熟的分支。以Quinlan在1986年提出的ID3為代表決策樹歸納學(xué)習(xí)算法，它是一種基于信息增益的典型自上而下的決策樹歸納方法。以決策樹為知識表達形式，具有描述簡單、分類速度快、計算量小的特點，能歸納出一種較“好”的決策樹，且適用于大規(guī)模數(shù)據(jù)集的學(xué)習(xí)問題。模糊ID3算法（Fuzzy-ID3）是傳統(tǒng)ID3算法在模糊環(huán)境下的一種推廣，這種算法能處理與人的思維和感覺相關(guān)的不確定性，因而應(yīng)用更為廣泛。模糊ID3算法的核心是使用模糊信息熵來選擇擴展屬性，根據(jù)所選的屬性來分割決策樹中當(dāng)前節(jié)點的數(shù)據(jù)，從而生成一棵決策樹。模糊決策樹產(chǎn)生過程包括以下幾個步驟：①訓(xùn)練數(shù)據(jù)的模糊化。將數(shù)據(jù)集按一定比例分成訓(xùn)練集和測試集，模糊化過程使用所有訓(xùn)練例子，根據(jù)迭代自組織的模糊聚類算法產(chǎn)生全局中心，并由此中心模糊化所有訓(xùn)練例子及測試?yán)印＂贗D3算法是在模糊化后的所有訓(xùn)練例子的基礎(chǔ)上進行。決策樹的建立過程如下：對每一屬性計算信息增益，用具有最大信息增益的屬性來擴展根節(jié)點。刪除節(jié)點的空分支，對節(jié)點的每一非空分支計算屬于這一分支的所有對象分到每一類的真實水平S。若分到某一類的真實水平超過閾值β，則終止這一分支作為一個葉子（標(biāo)記為當(dāng)前類）。否則考察另一個屬性是否能繼續(xù)分割這個分支并進一步增加信息增益。如果能，則選擇具有最大信息增益的屬性作為決策節(jié)點，如果不能，則終止這一分支作為一個葉子。在葉子節(jié)點，所有的對象以最高的真實水平屬于同一類。對于每一新生成的決策節(jié)點重復(fù)第2步，直到不能向下擴展。決策樹建立完成。③將決策樹轉(zhuǎn)化為一組規(guī)則，其中每條規(guī)則是從根節(jié)點出發(fā)到葉子節(jié)點的一條路徑。④將得到的這組全局規(guī)則應(yīng)用于訓(xùn)練例子，得到分類的訓(xùn)練準(zhǔn)確率；然后將所有測試?yán)优c規(guī)則逐一匹配，得到分類的測試準(zhǔn)確率。從以上二個算法中，我們可以看出Lazy和Eager這兩種分類方法有本質(zhì)的不同。從計算時間的角度講，Lazy方法的訓(xùn)練階段基本不需要計算時間，但是當(dāng)一個新例子到來時就需要預(yù)測目標(biāo)函數(shù)值，所以測試階段的計算量比較大。而Eager方法則與之相反，訓(xùn)練階段需要計算得到目標(biāo)函數(shù)，所以訓(xùn)練階段的計算量比較大；從對新例子分類的角度講，Lazy方法總是當(dāng)新例子到來時才開始預(yù)測，而Eager方法在訓(xùn)練階段就完成了對所有例子目標(biāo)函數(shù)的建立。因此，它們的歸納偏好不同，Lazy方法側(cè)重當(dāng)前具體例子具體分析，而Eager方法在遇到測試?yán)又熬鸵呀?jīng)為其選擇了對應(yīng)的目標(biāo)函數(shù)。這兩種分類方法哪一種更具有概括性呢？假設(shè)在同樣的假說空間中解決問題，Lazy方法明顯具有更豐富的假說空間，因為它可以選擇多個局部相似的組合來表示目標(biāo)函數(shù)；Eager方法則在訓(xùn)練階段必須確定一個全局相似。所以通過實驗對兩者進行研究比較，從而可以對實際應(yīng)用算法選擇提供經(jīng)驗性結(jié)論，具有很好的實際意義。現(xiàn)在廣泛應(yīng)用的基于統(tǒng)計的模型有向量空間模型、NaiveBayes概率模型、實例映射模型和支持向量機模型。NaiveBayes模型是基于兩項假設(shè)之上的一種概率分類模型。支持向量機是一個用于解決模式識別問題的機器學(xué)習(xí)方法，它主要基于結(jié)構(gòu)風(fēng)險最小化原理。映射模型的主要思想是把分類問題轉(zhuǎn)化為矩陣變換的問題。其中變換矩陣用奇異值分解的方法求得。但實例映射模型需要大量的良好代表性數(shù)據(jù)。相對于支持向量機模型，實例映射模型計算量大，分類速度慢且精度較低。向量空間模型（VectorSpaceModel.VSM）是由G.Salton等人在20世紀(jì)60年代提出的。它把文檔分類簡化為以項的權(quán)重為分量的向量表示，把分類過程簡化為空間向量的運算，使得問題的復(fù)雜性大大減低。此外，向量空間模型對項的權(quán)重評價、相似度的計算都沒有作統(tǒng)一的規(guī)定，只是提供了一個理論框架，可以使用不同的權(quán)重評價函數(shù)和相似度計算方法，使得此模型有廣泛的適應(yīng)性。2.2基于實例的學(xué)習(xí)算法基于實例的學(xué)習(xí)算法并不像上面介紹的決策樹算法等分類算法一樣建立明確的分類規(guī)則，而是直接存儲訓(xùn)練樣本，并沒有在訓(xùn)練樣本的基礎(chǔ)上獲取一個模擬輸出函數(shù)。當(dāng)一個測試樣本點到來時，才開始計算訓(xùn)練樣本與其的相似度，從而確定未知樣本的分類。也就是說，基于實例的學(xué)習(xí)算法是對每一個測試樣本點都創(chuàng)建相應(yīng)不同的目標(biāo)輸出函數(shù)，這是與神經(jīng)網(wǎng)絡(luò)算法、決策樹算法不同的思想。事實上，很多技術(shù)都對測試樣本點的某一個近鄰范圍內(nèi)創(chuàng)建局部模擬函數(shù)，而不是在整個訓(xùn)練樣本空間創(chuàng)建測試樣本的模擬輸出函數(shù)。這種局部近似的優(yōu)點是當(dāng)目標(biāo)函數(shù)比較復(fù)雜時，可以選擇相對簡單的局部模擬函數(shù)進行分類輸出。但是基于實例的學(xué)習(xí)算法有一個明顯的缺點是對每一個測試樣本點分類的計算代價相對較高。這主要是因為算法把所有的計算都在一個測試樣本點到來的時候開始的。另一個缺點是在尋求測試樣本點與訓(xùn)練樣本點的相似度的時侯，考慮了描述樣本點的所有屬性，那么就有可能出現(xiàn)第一章1.2中敘述的，如果不考慮所有屬性而只參考一部分屬性的話,兩個樣本點相似度將會有很大的變化。2.3K-近鄰方法2.3.1最近鄰分類算法簡介近鄰算法是基于實例學(xué)習(xí)的分類算法中比較常用的一種方法。令x={x1,…,xn},其中每一個樣本xi所屬的類別均已知。對于測試樣本點x，在集合中X中距離它最近的點記為x',那么，最近鄰規(guī)則的分類方法就是把點x分為x'所屬的類別。通常最近鄰規(guī)則方法的誤差率比最小可能誤差率（即貝葉斯誤差率）要大。然而，在無限訓(xùn)練樣本的情況下，這個誤差至多不會超過貝葉斯誤差率的兩倍。最近鄰點的標(biāo)記ωi（某個i）是一個隨機變量。ωi的概率為后驗概率,當(dāng)樣本個數(shù)非常大的時候，有理由認(rèn)為x’距離x足夠近，使得p(wi|x)=p(wi|x).因為這恰好是狀態(tài)位于wi的概率，因此最近鄰規(guī)則自然是真實概率的一個有效的近似。2.3.2K-近鄰算法實現(xiàn)KNN算法最早是由Cover和Hart提出的一種非參數(shù)分類算法，現(xiàn)已廣泛應(yīng)用于模式識別和數(shù)據(jù)挖掘的各個領(lǐng)域。分類思想是：給定一個待分類的樣本x，首先找出與x最接近的或最相似的K個已知類別標(biāo)簽的訓(xùn)練集樣本，然后根據(jù)這K個訓(xùn)練樣本的類別標(biāo)簽確定樣本x的類別。算法步驟：①構(gòu)建訓(xùn)練樣本集合X。②設(shè)定K的初值。K值的確定沒有一個統(tǒng)一的方法（根據(jù)具體問題選取的K值可能有較大的區(qū)別）。一般方法是先確定一個初始值，然后根據(jù)實驗結(jié)果不斷調(diào)試，最終達到最優(yōu)。③在訓(xùn)練樣本集中選出與待測樣本最近的K個樣本。假定樣本點x屬于n維空間Rn，樣本之間的“近鄰”一般由歐式距離來度量。2.4算法分析2.4.1算法實現(xiàn)defclassify0(inx,dataset,lables,k): dataSetSize=dataSet.shape[0] diffMat=tile(inX,(dataSetSize,1))-dataSet sqDiffMat=diffMat**2 sqDistances=sqDiffMat.sum(axis=1) distances=sqDistances**0.5 sorteDistIndicies=distances.argsort() classCount={} foriinrange(k): voteIlabel=labels[sortedDistIndicies[i]] classCount[voteIlabel]=classCount.get(voteIlabel,0)+1] sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True) returnsortedClassCount[0][0]2.4.2算法的優(yōu)缺點KNN分類方法是一種非參數(shù)的分類技術(shù)，對于未知和非正態(tài)分布的數(shù)據(jù)可以取得較高的分類準(zhǔn)確率，具有概念清晰、易于實現(xiàn)等諸多優(yōu)點。但同時也存在分類過程中計算量過大、對樣本庫過于依賴和度量相似性的距離函數(shù)不適用等問題。KNN分類方法的主要優(yōu)點包括：①算法簡單直觀，易于實現(xiàn)；②不需要產(chǎn)生額外的數(shù)據(jù)來描述規(guī)則，它的規(guī)則就是訓(xùn)練數(shù)據(jù)（樣本）本身，并不是要求數(shù)據(jù)的一致性問題，即可以存在噪音；③KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。因此，采用這種方法可以較好地避免樣本數(shù)量的不平衡問題④從分類過程來看，KNN方法最直接地利用了樣本之間的關(guān)系，減少了類別特征選擇不當(dāng)對分類結(jié)果造成的不利影響，可以最大程度地減少分類過程中的誤差項。對于一些類別特征不明顯的類別而言，KNN法更能體現(xiàn)出其分類規(guī)則獨立性的優(yōu)勢，使得分類自學(xué)習(xí)的實現(xiàn)成為可能。傳統(tǒng)的KNN方法的不足之處主要包括：1)分類速度慢最近鄰分類器是基于實例學(xué)習(xí)的懶惰學(xué)習(xí)方法，因為它是根據(jù)所給訓(xùn)練樣本構(gòu)造的分類器，是將所有訓(xùn)練樣本首先存儲起來，當(dāng)要進行分類時，就臨時進行計算處理。需要計算待分樣本與訓(xùn)練樣本庫中每一個樣本的相似度，才能求得與其最近的K個樣本。對于高維樣本或樣本集規(guī)模較大的情況，其時間和空間復(fù)雜度較高，時間代價為O(mn)，其中m為向量空間模型空間特征維數(shù)，n為訓(xùn)練樣本集大小。2)樣本庫容量依賴性較強對KNN算法在實際應(yīng)用中的限制較大：有不少類別無法提供足夠的訓(xùn)練樣本，使得KNN算法所需要的相對均勻的特征空間條件無法得到滿足，使得識別的誤差較大。3)特征作用相同與決策樹歸納方法和神經(jīng)網(wǎng)絡(luò)方法相比，傳統(tǒng)最近鄰分類器認(rèn)為每個屬性的作用都是相同的（賦予相同權(quán)重）。樣本的距離是根據(jù)樣本的所有特征（屬性）計算的。在這些特征中，有些特征與分類是強相關(guān)的，有些特征與分類是弱相關(guān)的，還有一些特征（可能是大部分）與分類不相關(guān)。這樣，如果在計算相似度的時候，按所有特征作用相同來計算樣本相似度就會誤導(dǎo)分類過程。4)K值的確定KNN算法必須指定K值，K值選擇不當(dāng)則分類精度不能保證。2.4.3KNN的改進對于KNN分類算法的改進方法主要可以分為加快分類速度、對訓(xùn)練樣本庫的維護、相似度的距離公式優(yōu)化和K值確定四種類型。①加快KNN算法的分類速度就學(xué)習(xí)而言，懶惰學(xué)習(xí)方法比積極學(xué)習(xí)方法要快，就計算量而言，它要比積極學(xué)習(xí)方法慢許多。因為懶惰學(xué)習(xí)方法在進行分類時，需要進行大量的計算。針對這一問題，到目前為止絕大多數(shù)解決方法都是基于減少樣本量和加快搜索K個最近鄰速度兩個方面考慮的：1)濃縮訓(xùn)練樣本當(dāng)訓(xùn)練樣本集中樣本數(shù)量較大時，為了減小計算開銷，可以對訓(xùn)練樣本集進行編輯處理，即從原始訓(xùn)練樣本集中選擇最優(yōu)的參考子集進行K最近鄰尋找，從而減少訓(xùn)練樣本的存儲量和提高計算效率。這種途徑最主要的方法是Hart的Condensing算法、WilSon的Editing算法和Devijver的MultiEdit算法，Kuncheva使用遺傳算法在這方面也進行了一些研究。2)加快K個最近鄰的搜索速度這類方法是通過快速搜索算法，在較短時間內(nèi)找到待分類樣本的K個最近鄰。在具體進行搜索時，不要使用盲目的搜索方法，而是要采用一定的方法加快搜索速度或減小搜索范圍，例如可以構(gòu)造交叉索引表，利用匹配成功與否的歷史來修改樣本庫的結(jié)構(gòu)，使用樣本和概念來構(gòu)造層次或網(wǎng)絡(luò)來組織訓(xùn)練樣本。此類方法主要可分為三類：空間（數(shù)據(jù)）分區(qū)方法、以掃描作為基礎(chǔ)的方法和線性化方法。②相似度的距離公式的優(yōu)化為了改變傳統(tǒng)KNN算法中特征作用相同的缺陷，可在相似度的距離公式中給特征賦予不同權(quán)重，例如在歐氏距離公式中給不同特征賦予不同權(quán)重特征的權(quán)重。③對訓(xùn)練樣本庫的維護對訓(xùn)練樣本庫進行維護以滿足KNN算法的需要，包括對訓(xùn)練樣本庫中的樣本進行添加或刪除。對樣本庫的維護并不是簡單的增加刪除樣本，而是可采用適當(dāng)?shù)霓k法來保證空間的大小，如符合某種條件的樣本可以加入數(shù)據(jù)庫中，同時可以對數(shù)據(jù)庫庫中已有符合某種條件的樣本進行刪除。從而保證訓(xùn)練樣本庫中的樣本提供KNN算法所需要的相對均勻的特征空間。文獻[39,40,41]從不同角度對樣本庫進行了維護，提高了KNN算法的分類精度和減少了樣本量。但有時由于樣本庫中無法提供每一個類的足夠訓(xùn)練樣本，使得KNN算法所需要的相對均勻的特征空間條件無法得到滿足。并且考慮到單純靠增加樣本也會帶來計算量過大的問題，P.Viswannth等提出了OLP-synthesis算法，以獲得一個壓縮的具有普遍性的訓(xùn)練樣本集合。④K值選擇K值的選擇原則一般為：1)K的選擇往往通過大量獨立的測試數(shù)據(jù)、多個模型來驗證最佳的選擇；2)K值一般事先確定，也可以使用動態(tài)的，例如采用固定的距離指標(biāo)，只對小于該指標(biāo)的樣本進行分析。文獻[43]就采用了動態(tài)K值。有時類別之間樣本極為不平衡，K值的選擇更為困難，文獻[44]針對這種類的樣本數(shù)量不平衡的情況提出了K值的選擇方法。還有一些其他方面對KNN算法性能進行改進的方法，例如迭代近鄰法等。3 算法應(yīng)用3.1k—近鄰算法在肝癌檢測中的應(yīng)用肝癌是一種常見的惡性腫瘤，發(fā)病率呈逐年升高態(tài)勢。臨床醫(yī)學(xué)中對肝癌的診斷準(zhǔn)確率要求較高。利用計算機輔助診斷檢測、判定肝癌可提高診斷的速度與精度。如何正確判斷肝臟的健康狀況及病變類別是肝癌檢測的最終任務(wù)。目前，主要利用提取肝臟的紋理特征與形狀特征，并結(jié)合相應(yīng)的數(shù)據(jù)挖掘分類算法實現(xiàn)肝癌的具體分類與識別。在肝臟CT圖像中，病變肝臟與正常肝臟的區(qū)別主要反映為不同的紋理特征，肝癌類別主要反映為不同的形狀特征。因而可利用肝臟的紋理特征與形狀特征進行肝癌的分類檢測。紋理特征用于識別正常肝臟與病變肝臟，形狀特征用于肝癌類型的識別。該文將K-NN算法分別應(yīng)用于基于紋理特征的分類與基于形狀特征的分類。3.2面向延遲敏感性應(yīng)用為了降低用戶訪問延遲,延遲敏感型網(wǎng)絡(luò)應(yīng)用需要選擇合適的鄰近服務(wù)節(jié)點響應(yīng)用戶訪問請求.分布式K

近鄰搜索通過可擴展的選擇距任意用戶節(jié)點鄰近的K

個服務(wù)節(jié)點,可以有效滿足網(wǎng)絡(luò)應(yīng)用延遲優(yōu)化的目的.已有工作在精確度以及可擴展性等方面存在不足.針對可擴展精確的K

近鄰搜索問題,文中提出了分布式K

近鄰搜索方法DKNNS(distributed

K

nearestneighborsearch).DKNNS將大量的服務(wù)節(jié)點組織為鄰近性感知的多級環(huán),通過最遠(yuǎn)節(jié)點搜索機制選擇優(yōu)化的K

近鄰搜索初始化節(jié)點,然后基于回退方式快速的在目標(biāo)節(jié)點鄰近區(qū)域發(fā)現(xiàn)K

個近鄰.基于理論分析,模擬測試以及真實環(huán)境下的部署實驗發(fā)現(xiàn),在不同規(guī)模的節(jié)點集合下,DKNNS算法能夠確定近似最優(yōu)的K

個服務(wù)節(jié)點.且DKNNS的查詢延遲,查詢開銷均顯著低于Meridian算法.最后,DKNNS的返回結(jié)果相對于Meridian具有較高的穩(wěn)定性.3.3改進的K-近鄰算法在中文網(wǎng)頁分類的應(yīng)用K-鄰近算法作為一種比較簡單,易于實現(xiàn)并且錯誤低的分類算法,廣泛應(yīng)用于網(wǎng)頁分類、模式識別和數(shù)據(jù)挖掘等多個領(lǐng)域中.本文介紹了傳統(tǒng)K-鄰近算法并分析了該算法在網(wǎng)頁相似度值的計算存在的不足,在此基礎(chǔ)上,本文提出了基于類中心向量的K-近鄰算法,通過理論分析和仿真實驗結(jié)果證明了該算法對于中文網(wǎng)頁分類具有較好的分類效果.總結(jié)模式分類在現(xiàn)實領(lǐng)域有著非常廣泛的應(yīng)用。K近鄰算法是模式分類算法中一類常用的算法。本文針對傳統(tǒng)的KNN算法的不足之處，提出了兩點改進措施。針對KNN算法的計算量大、速度慢的缺點，對訓(xùn)練數(shù)據(jù)采用了預(yù)處理的方法。首先采用某一聚類方法對訓(xùn)練數(shù)據(jù)進行分類，然后再與K近鄰方法相結(jié)合來判斷待測樣本的類別。現(xiàn)有的方法都是經(jīng)過聚類之后確定類別，按一定的規(guī)則挑選出來具有代表性的數(shù)據(jù)。然后再將這些挑選出來的數(shù)據(jù)作為訓(xùn)