kNN的計(jì)算方法綜述

[20]的ML-KNN是一種KNN<K-NearestNeighbor>與貝葉斯法則相結(jié)合的排序分類算法,具有思路簡(jiǎn)單、非參數(shù)化和性能優(yōu)越等優(yōu)點(diǎn),其局限性在于計(jì)算量大、分類效率偏低,因此不適用于實(shí)時(shí)性要求較高的場(chǎng)合。最近鄰選擇的相似度定義兩個(gè)基本的求解步驟組成：<1>從已分類數(shù)據(jù)實(shí)例集Ω=d1,d2,…,dΩ?D設(shè)預(yù)先定義的數(shù)據(jù)實(shí)例特征集為C=c1,c2,…,cC。根據(jù)向量空間模型,di∈D可表示為由其特征值構(gòu)成的特征向量di=ci1,ci2,…,ciCT。因此,待分類實(shí)例du可表示為特征向量du=cu1SIM<SEQ公式\*ARABIC3>而基于曼哈頓距離<ManhattanDistance>的相似度則可定義為：SIM<SEQ公式\*ARABIC4>不同的相似度定義將產(chǎn)生不同的最近鄰選擇結(jié)果,從而對(duì)分類效果產(chǎn)生很大影響。最近鄰選擇的相似度定義任意已分類數(shù)據(jù)實(shí)例di∈Ω的標(biāo)簽集可表示為l根據(jù)待分類數(shù)據(jù)實(shí)例的k個(gè)最近鄰進(jìn)行該實(shí)例的排序分類是本文算法的基本思想。首先根據(jù)相似度從Ω中選擇k個(gè)du的最近鄰形成集合Ndu=n1,n2,…,nk；然后找出最近鄰中擁有標(biāo)簽數(shù)的最大值lCntmax,統(tǒng)計(jì)擁有L中l(wèi)j的最近鄰數(shù)dCntj及其最大值dCntmax；最后按公式REF_Ref387610740\h<5>和l<SEQ公式\*ARABIC5>r<SEQ公式\*ARABIC6>其中threshold和const為常數(shù),s為拉普拉斯平滑因子。具體算法的時(shí)問(wèn)復(fù)雜度分析在上述FKMC中,僅利用du的k個(gè)最近鄰的局部信息進(jìn)行du的排序分類,省去了非常耗時(shí)的全局訓(xùn)練過(guò)程,這樣可以極大地降低計(jì)算復(fù)雜度。其最近鄰選擇部分的時(shí)間復(fù)雜度為OΩ,其余部分的時(shí)間復(fù)雜度為O1,所以總體時(shí)間復(fù)雜度為OΩ。分析文獻(xiàn)REF_Ref387604490\h[20]以看出,ML-KNN利用已分類數(shù)據(jù)實(shí)例集Ω的全局信息,先根據(jù)其中每個(gè)實(shí)例的k個(gè)最近鄰計(jì)算該實(shí)例擁有每一個(gè)標(biāo)簽的先驗(yàn)概率和最大后驗(yàn)概率,并據(jù)此進(jìn)行分類器的訓(xùn)練,然后將訓(xùn)練后的分類器用于du的排序分類過(guò)程,其運(yùn)行時(shí)間主要花在了計(jì)算已分類數(shù)據(jù)實(shí)例集中的每個(gè)實(shí)例擁有標(biāo)簽集中每個(gè)標(biāo)簽的先驗(yàn)概率和后驗(yàn)概率上,其時(shí)間復(fù)雜度為OΩ2,其余部分的時(shí)間復(fù)雜度為OΩ,所以總體時(shí)間復(fù)雜度為OΩ2kNN算法的應(yīng)用kNN算法作為最經(jīng)典的機(jī)器學(xué)習(xí)分類算法之一,必然有其十分廣泛的應(yīng)用。在這里僅僅列舉一些常見(jiàn)的應(yīng)用,并重點(diǎn)介紹以下kNN算法在文本分類中的應(yīng)用。kNN算法的主要應(yīng)用領(lǐng)域模式識(shí)別,特別是光學(xué)字符識(shí)別；統(tǒng)計(jì)分類；計(jì)算機(jī)視覺(jué)；數(shù)據(jù)庫(kù),如基于內(nèi)容的圖像檢索；編碼理論〔最大似然編碼；數(shù)據(jù)壓縮〔MPEG-2標(biāo)準(zhǔn)；向?qū)到y(tǒng)；網(wǎng)絡(luò)營(yíng)銷；DNA測(cè)序；拼寫檢查,建議正確拼寫；剽竊偵查；相似比分算法,用來(lái)推斷運(yùn)動(dòng)員的職業(yè)表現(xiàn)。kNN算法處理文本分類問(wèn)題文本分類介紹文本自動(dòng)分類最初是應(yīng)信息檢索〔IR系統(tǒng)的要求而出現(xiàn)的。隨著全球互聯(lián)網(wǎng)絡(luò)的普及,文本自動(dòng)分類對(duì)于信息處理的意義變得更加重要。在互聯(lián)網(wǎng)上,電子文檔信息每天都在急劇增加,通過(guò)網(wǎng)絡(luò),人們可以很方便地共享巨大的信息資源。但是,網(wǎng)絡(luò)信息的快速膨脹,信息資源無(wú)法有效利用。面對(duì)網(wǎng)上的海量信息,傳統(tǒng)的做法是,對(duì)網(wǎng)上信息進(jìn)行人工分類,并加以組織和整理,為人們提供一種相對(duì)有效的信息獲取手段。但這種人工分類的做法存在著許多弊端：一是耗費(fèi)大量的人力、物力和精力；二是分類結(jié)果一致性不高。即使分類人的語(yǔ)言素質(zhì)較高,對(duì)于不同的人來(lái)分類,其分類結(jié)果仍然不盡相同。甚至同一個(gè)人,在不同時(shí)間做分類也可能會(huì)有不同的結(jié)果。網(wǎng)絡(luò)信息的激增一方面增加了對(duì)于快速、自動(dòng)文本分類的迫切需求。另一方面又為基于機(jī)器學(xué)習(xí)的文本分類方法準(zhǔn)備了充分的資源。電子化信息的自動(dòng)分類處理技術(shù)正越發(fā)顯示著其優(yōu)越性,文本自動(dòng)分類及其相關(guān)技術(shù)的研究也正日益成為一項(xiàng)研究熱點(diǎn)。文本分類主要應(yīng)用于信息檢索,機(jī)器翻譯,自動(dòng)文摘,信息過(guò)濾,郵件分類等任務(wù)。文本分類在搜索引擎中也有著大量的使用,網(wǎng)頁(yè)分類/分層技術(shù)是檢索系統(tǒng)的一項(xiàng)關(guān)鍵技術(shù),搜索引擎需要研究如何對(duì)網(wǎng)頁(yè)進(jìn)行分類、分層,對(duì)不同類別的網(wǎng)頁(yè)采用差異化的存儲(chǔ)和處理,以保證在有限的硬件資源下,提供給用戶一個(gè)高效的檢索系統(tǒng),同時(shí)提供給用戶相關(guān)、豐富的檢索結(jié)果。在搜索引擎中,文本分類主要有這些用途：相關(guān)性排序會(huì)根據(jù)不同的網(wǎng)頁(yè)類型做相應(yīng)的排序規(guī)則；根據(jù)網(wǎng)頁(yè)是索引頁(yè)面還是信息頁(yè)面,下載調(diào)度時(shí)會(huì)做不同的調(diào)度策略；在做頁(yè)面信息抽取時(shí),會(huì)根據(jù)頁(yè)面分類的結(jié)果做不同的抽取策略；在做檢索意圖識(shí)別的時(shí)候,會(huì)根據(jù)用戶所點(diǎn)擊的url所屬的類別來(lái)推斷檢索串的類別。文本分類過(guò)程以Internet中的文本為例,待分類文本以HTML格式存儲(chǔ)的半格式化的Web頁(yè)面、文檔為主,也是當(dāng)前Internet信息的主要組織形式。文本知識(shí)挖掘就是要發(fā)現(xiàn)其中隱含的規(guī)則,以便于實(shí)現(xiàn)Internet數(shù)據(jù)挖掘的智能化,離開了文本知識(shí)挖掘,智能化是不能實(shí)現(xiàn)的。最常用的文本知識(shí)挖掘方法是基于文檔特征向量空間模型〔CharacteristicVectorSpaceModel,CVSM的。文檔模型建立預(yù)處理過(guò)程。一是要根據(jù)禁用詞集去除文檔中的語(yǔ)義虛泛的禁用詞；二是要利用特征詞典集〔包括通用集和專業(yè)集進(jìn)行分詞,如果出現(xiàn)詞集中沒(méi)有的詞,則將它整體作為一詞并記錄以便人工分詞。概念映射和概念消歧。有些詞形式不同但概念相同,要求根據(jù)概念集將它們映射為同一概念；對(duì)于未登錄詞,則選擇與之共現(xiàn)率最多的詞作為其概念；對(duì)于一詞具有多概念標(biāo)注的,選擇概念標(biāo)注出現(xiàn)次數(shù)最多者為其標(biāo)注。一般特征項(xiàng)提取和姓名日期數(shù)字等特征抽取,結(jié)果存入文檔矢量庫(kù)。特征集縮減。通過(guò)以上方法得到的特征集數(shù)目巨大,所以必須對(duì)其進(jìn)行縮減。其算法一般是構(gòu)造一個(gè)評(píng)價(jià)函數(shù),對(duì)每個(gè)特征向量進(jìn)行評(píng)估,然后根據(jù)評(píng)估值的大小選取一定數(shù)量或超過(guò)閾值的特征向量子集。特征集縮減的結(jié)果存入文檔矢量庫(kù)。知識(shí)發(fā)現(xiàn)文本摘要。采用基于統(tǒng)計(jì)的自動(dòng)生成方式較多,其基本思想是把文中與主題密切相關(guān)的句子挑選出來(lái),這樣的句子往往位于特殊的部分或含有較多的特征項(xiàng),一般以句子權(quán)重函數(shù)為評(píng)價(jià)標(biāo)準(zhǔn)。文本分類。文本分類是文本知識(shí)挖掘的主要目的,基本思想是將訓(xùn)練集、矢量集與文檔矢量集相比較,方法有樸素貝葉斯分類算法和K－最近鄰居分類算法等。模型評(píng)價(jià)文本評(píng)價(jià)的模型比較多,一般是將數(shù)據(jù)集分為訓(xùn)練集與測(cè)試集。學(xué)習(xí)—測(cè)試循環(huán)反復(fù)執(zhí)行,最后用一個(gè)指標(biāo)來(lái)衡量模型質(zhì)量。模型評(píng)價(jià)具體指標(biāo)有分類正確率、查準(zhǔn)率、查全率、查準(zhǔn)率、查全率的平均和信息估值等。kNN算法實(shí)現(xiàn)文本分類文本自動(dòng)分類的一個(gè)關(guān)鍵問(wèn)題是如何構(gòu)造分類函數(shù)〔分類器,并利用此分類函數(shù)將待分類文本劃分到相應(yīng)的類別空間中。訓(xùn)練方法和分類算法是分類系統(tǒng)的核心,這里介紹采用KNN分類算法對(duì)文本知識(shí)進(jìn)行類別學(xué)習(xí)。kNN算法的基本思路是：在給定新文本后,考慮在訓(xùn)練文本集中與該新文本距離最近〔最相似的K篇文本,根據(jù)這K篇文本所屬的類別判定新文本所屬的類別,具體的算法步驟如下：根據(jù)特征項(xiàng)集合重新描述訓(xùn)練文本向量；在新文本到達(dá)后,根據(jù)特征詞分詞新文本,確定新文本的向量表示；在訓(xùn)練文本集中選出與新文本最相似的K個(gè)文本,計(jì)算公式為：Simd在新文本的K個(gè)鄰居中,依次計(jì)算每類的權(quán)重,計(jì)算公式：px,Cj=di∈KNNSimx,d比較類的權(quán)重,將文本分到權(quán)重最大的那個(gè)類別中。參考文獻(xiàn)[SEQ參考文獻(xiàn)\*ARABIC1]Cover,HartT,P.Nearestneighborpatternclassification[J].IEEE,1967<1>:21-27.[SEQ參考文獻(xiàn)\*ARABIC2]CoverT.RatesofConvergenceforNearestNeighborProcedures[J].SystemsSciences,1968.[SEQ參考文獻(xiàn)\*ARABIC3]StoneCJ.ConsistentNonparametricRegression[J].InstituteofMathematicalStatistics,1977<7>,5<4>:595-620.[SEQ參考文獻(xiàn)\*ARABIC4]ClevelandWS.RobustLocallyWeightedRegressionandSmoothingScatterplots[J].JournaloftheAmericanStatisticalAssociation,1979,74:829-836.[SEQ參考文獻(xiàn)\*ARABIC5]Brown,T.,Koplowitz,Jack.Theweightednearestneighborruleforclassdependentsamplesizes<Corresp.>[J].IEEE,1979<9>.IT-25:617-619.[SEQ參考文獻(xiàn)\*ARABIC6]ShortR,FukunagaK.Anewnearestneighbordistancemeasure[J].IEEE,1980:81-86.[SEQ參考文獻(xiàn)\*ARABIC7]Short,RobertD.;Fukunaga,K.TheOptimalDistanceMeasureforNearestNeighborClassification[J].IEEE,1981<9>,27<5>:622-627.[SEQ參考文獻(xiàn)\*ARABIC8]MylesJ,HandD.TheMulti-ClassMetricProbleminNearestNeighborDiscriminationRules[J].PatternRecognition,1990,23<11>:1291–1297.[SEQ參考文獻(xiàn)\*ARABIC9]AltmanNS.AnIntroductiontoKernelandNearest-NeighborNonparametricRegression[J].,1992,46<3>:175-185.[SEQ參考文獻(xiàn)\*ARABIC10]ZhangM,ZhouZ.ML-KNN:Alazylearningapproachtomulti-labellearning[J].PatternRecognition,2007<7>,40<7>:2038–2048.[SEQ參考文獻(xiàn)\*ARABIC11]HallP,SamworthBUPARJ.ChoiceOfNeighborOrderInNearest-NeighborClassification[J].TheAnnalsofStatistics,2008<10>,36<5>:2135-2152.[SEQ參考文獻(xiàn)\*ARABIC12]PanJ,Manocha,D.Bi-levelLocalitySensitiveHashingfork-NearestNeighborComputation[J].IEEE,2012<4>:378-389.[SEQ參考文獻(xiàn)\*ARABIC13]MichelMDeza,ElenaDeza.EncyclopediaofDistances.Springer,2009[SEQ參考文獻(xiàn)\*ARABIC14]周靖,劉晉勝.一種采用類相關(guān)度優(yōu)化距離的KNN算法[J].微計(jì)算機(jī)應(yīng)用,2010<11>,31<11>:7-12.[SEQ參考文獻(xiàn)\*ARABIC15]SebastianiF．Machinelearninginautomatedtextcategorization[J].ACMComputingSurveys,2002,34<1>:1-47.[SEQ參考文獻(xiàn)\*ARABIC16]趙繼東,魯坷,吳躍．一種基于譜圖理論的web圖像搜索方法[J].計(jì)算機(jī)應(yīng)用研究,2008<5>:12-13.[SEQ參考文獻(xiàn)\*ARABIC17]張華．www圖像語(yǔ)義信息提取方法研究[D].XX：XX師范大學(xué),2004.[SEQ參考文獻(xiàn)\*ARABIC18]溫小斌．Interact圖像搜索引擎的研究與實(shí)現(xiàn)[D]．XX：XX大學(xué),2006.[SEQ參考文獻(xiàn)\*ARABIC19]CaiDang,HeXiaofei,LiZhiwei,eta1．HieraehicalclusteringofWWWimagesearchresultsusingvisual．textualandlinkInformation[C]//ProceedingsoftheACMInternationalConferenceonMultimedia,NewYork,USA,2004：952—959．[SEQ參考文獻(xiàn)\*ARABIC20]ChengEn,JingFeng,ZhangChao,eta1.Searchresultclusteringbasedrelevancefeedbackforwebimageretrieval[C]//InteractionalConferenceonAcoustics,Speech,andSignalProcessing,Hawaii,2007:961-964.[SEQ參考文獻(xiàn)\*ARABIC21]謝同．基于文本的Web圖片搜索引擎的研究與實(shí)現(xiàn)[D].XX：電子科技大學(xué),2007.[SEQ參考文獻(xiàn)\*ARABIC22]CaiD,YuS,WenJR,eta1.VIPS:avision-basedpagesegmentationalgorithm,MSR-TR-2003-79[R].MicrosoftResearch,2003.[SEQ參考文獻(xiàn)\*ARABIC23]亢世勇,劉艷．漢語(yǔ)動(dòng)詞謂語(yǔ)句的語(yǔ)義成分和語(yǔ)義句式[J].唐都學(xué)刊.1998,14<1>:89-93.[SEQ參考文獻(xiàn)\*ARABIC24]徐斌基于PCFG-HDSM模型的語(yǔ)義句式識(shí)別[D].XX:XX航天航空大學(xué),2008.[SEQ參考文獻(xiàn)\*ARABIC25]PEHar.Thecondensednearestneighborrule.IEEETransonInformationTheory,1968,IT-14<3>:515-516.[SEQ參考文獻(xiàn)\*ARABIC26]李榮陸,胡運(yùn)發(fā).基于密度的k