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

沈陽航空航天大學(xué)ShenyangAerospaceUniversity算法分析題目：基于K-近鄰分類算法的研究院系計(jì)算機(jī)學(xué)院專業(yè)計(jì)算機(jī)技術(shù)姓名學(xué)號(hào)指導(dǎo)教師1月摘要數(shù)據(jù)挖掘是機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)廣泛研究的知識(shí)領(lǐng)域,是將人工智能技術(shù)和數(shù)據(jù)庫技術(shù)緊密結(jié)合，讓計(jì)算機(jī)協(xié)助人們從龐大的數(shù)據(jù)中智能地、自動(dòng)地提取出有價(jià)值的知識(shí)模式，以滿足人們不同應(yīng)用的需要。K近鄰算法（KNN)是基于統(tǒng)計(jì)的分類辦法，是數(shù)據(jù)挖掘分類算法中比較慣用的一種辦法.該算法含有直觀、無需先驗(yàn)統(tǒng)計(jì)知識(shí)、無師學(xué)習(xí)等特點(diǎn)，現(xiàn)在已經(jīng)成為數(shù)據(jù)挖掘技術(shù)的理論和應(yīng)用研究辦法之一。本文重要研究了K近鄰分類算法。首先簡(jiǎn)要地介紹了數(shù)據(jù)挖掘中的多個(gè)分類算法，具體地?cái)⑹隽薑近鄰算法的基本原理和應(yīng)用領(lǐng)域，另首先指出了K近鄰算法的計(jì)算速度慢、分類精確度不高的因素，提出了兩種新的改善辦法.針對(duì)K近鄰算法的計(jì)算量大的缺點(diǎn)，構(gòu)建了聚類算法與K近鄰算法相結(jié)合的一種辦法。將聚類中的K-均值和分類中的K近鄰算法有機(jī)結(jié)合.有效地提高了分類算法的速度。針對(duì)分類精確度的問題，提出了一種新的距離權(quán)重設(shè)定辦法。傳統(tǒng)的KNN算法普通采用歐式距離公式度量兩樣本間的距離。由于在實(shí)際樣本數(shù)據(jù)集合中每一種屬性對(duì)樣本的奉獻(xiàn)作用是不盡相似的,普通采用加權(quán)歐式距離公式。本文提出一種新的計(jì)算權(quán)重的辦法。實(shí)驗(yàn)表明，本文提出的算法有效地提高了分類精確度.最后，在總結(jié)全文的基礎(chǔ)上，指出了有待進(jìn)一步研究的方向。核心詞：K近鄰，聚類算法，權(quán)重,復(fù)雜度，精確度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，HYPERLINK”/sowiki/KNN?prd=content_doc_search"\o"KNN”KNN)分類算法，是一種理論上比較成熟的辦法，也是最簡(jiǎn)樸的機(jī)器學(xué)習(xí)算法之一.該辦法的思路是：如果一種樣本在特性空間中的k個(gè)最相似(即特性空間中最鄰近）的樣本中的大多數(shù)屬于某一種類別，則該樣本也屬于這個(gè)類別。KNN算法中,所選擇的鄰居都是已經(jīng)對(duì)的分類的對(duì)象。該辦法在定類決策上只根據(jù)最鄰近的一種或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。KNN辦法即使從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于KNN辦法重要靠周邊有限的鄰近的樣本，而不是靠鑒別類域的辦法來擬定所屬類別的,因此對(duì)于類域的交叉或重疊較多的待分樣本集來說，KNN辦法較其它辦法更為適合.KNN算法不僅能夠用于分類，還能夠用于回歸.通過找出一種樣本的k個(gè)近來鄰居，將這些鄰居的屬性的平均值賦給該樣本,就能夠得到該樣本的屬性。更有用的辦法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響予以不同的權(quán)值（weight),如權(quán)值與距離成正比。該算法在分類時(shí)有個(gè)重要的局限性是，當(dāng)樣本不平衡時(shí)，如一種類的樣本容量很大，而其它類樣本容量很小時(shí)，有可能造成當(dāng)輸入一種新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。該算法只計(jì)算“近來的"鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不靠近目的樣本,或者這類樣本很靠近目的樣本。無論如何，數(shù)量并不能影響運(yùn)行成果。能夠采用權(quán)值的辦法（和該樣本距離小的鄰HYPERLINK”±????？prd=content_doc_search”\o"居權(quán)”居權(quán)值大）來改善.

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

近鄰搜索通過可擴(kuò)展的選擇距任意顧客節(jié)點(diǎn)鄰近的K

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

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

近鄰搜索辦法DKNNS（distributed

K

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

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

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

個(gè)服務(wù)節(jié)點(diǎn)。且DKNNS的查詢延遲,查詢開銷均明顯低于Meridian算法.最后,DKNNS的返回成果相對(duì)于Meridian含有較高的穩(wěn)定性。3。3改善的K—近鄰算法在中文網(wǎng)頁分類的應(yīng)用K—鄰近算法作為一種比較簡(jiǎn)樸,易于實(shí)現(xiàn)并且錯(cuò)誤低的分類算法，廣泛應(yīng)用于網(wǎng)頁分類、模式識(shí)別和數(shù)據(jù)挖掘等多個(gè)領(lǐng)域中.本文介紹了傳統(tǒng)K-鄰近算法并分析了該算法在網(wǎng)頁相似度值的計(jì)算存在的局限性，在此基礎(chǔ)上,本文提出了基于類中心向量的K—近鄰算法,通過理論分析和仿真實(shí)驗(yàn)成果證明了該算法對(duì)于中文網(wǎng)頁分類含有較好的分類效果?？偨Y(jié)模式分類在現(xiàn)實(shí)領(lǐng)域有著非常廣泛的應(yīng)用。K近鄰算法是模式分類算法中一類慣用的算法。本文針對(duì)傳統(tǒng)的KNN算法的局限性之處,提出了兩點(diǎn)改善方法。針對(duì)KNN算法的計(jì)算量大、速度慢的缺點(diǎn)，對(duì)訓(xùn)練數(shù)據(jù)采用了預(yù)解決的辦法.首先采用某一聚類辦法對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分類，然后再與K近鄰辦法相結(jié)合來判斷待測(cè)樣本的類別.現(xiàn)有的辦法都是通過聚類之后擬定類別,按一定的規(guī)則挑選出來含有代表性的數(shù)據(jù)。然后再將這些挑選出來的數(shù)據(jù)作為訓(xùn)練樣本.但這類辦法能去除的數(shù)據(jù)非常有限，因此對(duì)計(jì)算量大的改善不大，而本文提出的新的算法：在聚類之后，首先計(jì)算出來各個(gè)類別的中心，然后只需要考慮待測(cè)樣本和聚類中心的距離就能夠。然后再根據(jù)最后得到的距離的大小判斷該點(diǎn)所屬的類別。通過實(shí)例驗(yàn)證表明,該辦法在算法的時(shí)間復(fù)雜度方面有一定的改