李 娟 ， 王 宇 平

（1.西安電子科技大學(xué) 計(jì) 算機(jī)學(xué)院，陜西 西 安 710071；2.陜西師范大學(xué) 遠(yuǎn) 程教育學(xué)院，陜西 西 安 710062）

發(fā)現(xiàn)近鄰是機(jī)器學(xué)習(xí)領(lǐng)域中一種常見且有效的處理思想，被廣泛應(yīng)用到K近鄰算法（KNN）[1－2]中.眾所周知，KNN算法是一種基于實(shí)例的簡單而成熟的分類算法，無需提前訓(xùn)練分類器，而是在訓(xùn)練樣本集中尋找與未知類別樣本最接近的k個樣本，使用“投票”原則作為分類決策，未知類別樣本將被賦予k個最近樣本中最公共的類別信息.KNN算法通常采用距離或相似度函數(shù)作為選取近鄰的度量準(zhǔn)則.因此距離或相似度函數(shù)、k近鄰數(shù)量是KNN算法的核心，更是模式識別的主要研究分支.

針對于不同的數(shù)據(jù)類型及其特點(diǎn)，產(chǎn)生了諸多有效而經(jīng)典的距離和相似度度量函數(shù).常見的經(jīng)典算法中：歐氏距離、曼哈頓距離等用于處理數(shù)值類型；漢明距離[3]、編輯距離[4]、值差度量[5]等用于處理標(biāo)識類型；最大子圖法[6]用于處理圖類型數(shù)據(jù)；異構(gòu)值差度量[5]、后驗(yàn)概率法[7]等可統(tǒng)一解決數(shù)值和標(biāo)識兩種類型.針對于上述經(jīng)典算法，后續(xù)學(xué)者提出的若干的改進(jìn)策略：如文獻(xiàn)[8]提出的近鄰計(jì)數(shù)法可同時處理數(shù)值和標(biāo)識類型；文獻(xiàn)[9]提出的基于偽近鄰的權(quán)重相似度有效利用了多個近鄰樣本的均值信息；文獻(xiàn)[10]提出的基于局部距離函數(shù)和相似度度量的親和函數(shù)等，關(guān)注了個體樣本對整體樣本集的影響.上述算法從不同關(guān)注點(diǎn)分析了樣本間關(guān)聯(lián)：樣本位置、樣本分布概率、權(quán)重調(diào)整等，除文獻(xiàn)[10]算法外，經(jīng)典距離或相似度度量尚未對個體樣本對整體樣本集的影響進(jìn)行深入研究，即未涉及到樣本的不同特征值的有無對整體樣本集該特征的影響.

傳統(tǒng)距離度量策略不能很好地解決樣本特殊分布、噪音點(diǎn)敏感等情況，未能充分利用樣本集的全部內(nèi)部信息，只能得到局部優(yōu)化解.為此，諸多算法對傳統(tǒng)K近鄰算法進(jìn)行改進(jìn)，如文獻(xiàn)[11－13]圍繞樣本權(quán)重、局部均值、雙層自適應(yīng)距離度量等方面.筆者在以往距離和相似度函數(shù)的基礎(chǔ)上，充分考慮到樣本對樣本集的影響因素，提出了一種基于緊密度和分散度的近鄰親和相似度函數(shù)（An Affinity Similarity Function Modified KNN，AMKNN），用于調(diào)整傳統(tǒng)距離度量的不利偏好.

1 親和相似度函數(shù)計(jì)算方法

統(tǒng)計(jì)學(xué)中，使用極值、離差均值、方差、標(biāo)準(zhǔn)差、變異系數(shù)等指標(biāo)衡量一組數(shù)據(jù)的離散度.對比之下，標(biāo)準(zhǔn)差是評價(jià)指標(biāo)中常見且評價(jià)效果較好的一種離散度.同樣，使用均值和中位數(shù)兩個指標(biāo)來衡量一組數(shù)據(jù)的集中度.而均值是一種簡單而實(shí)用的集中度指標(biāo).通常將均值與標(biāo)準(zhǔn)差相結(jié)合，借助特定數(shù)據(jù)的離散度和集中度的指標(biāo)信息，衡量特定數(shù)據(jù)對數(shù)據(jù)集的影響.

筆者借鑒統(tǒng)計(jì)學(xué)的離散度和集中度思想，定義分散度和緊密度作為改進(jìn)的親和距離函數(shù)的權(quán)重系數(shù).

為了便于描述，文中將使用到如下符號：任意數(shù)據(jù)集D ＝ ｛xi＝ （xi1，xi2，…，xid）｜i＝1，2，…，n｝，d為樣本維度，n為樣本總數(shù)；類標(biāo)記集C ＝ ｛c1，c2，…，cm），m 為類別數(shù)；TR＝ ｛（xi，yj）｜i＝1，2，…，N；j＝1，2，…，m；xi∈D；yj∈C｝，表示數(shù)量為N 的訓(xùn)練集；若干樣本的測試集TS；max（dj）與min（dj）分別為數(shù)據(jù)集dj維的兩個極值；mean（dj）為數(shù)據(jù)集dj維的均值；D（·，·）表示歐式距離；M（·，·）表示曼哈頓距離；NM（·，·）表示非曼哈頓距離.

1.1 親和度定義

文中所提出的親和度是體現(xiàn)個體樣本對數(shù)據(jù)集的影響度.個體對集合的影響通過個體的分離度和緊密度來體現(xiàn).以一維樣本為例進(jìn)行介紹.

定義1 個體分散度.個體對集合的分散度表示個體存在與否引發(fā)數(shù)據(jù)集合內(nèi)部樣本間距離標(biāo)準(zhǔn)差的變化率，文中使用S（x，D）表示個體分離度.

定義2 個體緊密度.個體對集合的緊密度表示個體存在與否引發(fā)數(shù)據(jù)集合內(nèi)部均值的變化率，文中使用C（x，D）表示個體緊密度.

定義3 個體親和度.個體對集合的親和度表示個體存在與否引發(fā)集合內(nèi)部樣本均值與方差的變化比率，文中使用A（x，D）表示.比率越大，樣本的親和度越小.由定義1～3可知，分離度越小且緊密度越高，個體對集合的影響力也就越大，故而個體的親和度越小.以1維樣本為例對上述定義進(jìn)行解釋.設(shè)D ＝ ｛1，3，4，2，3，4，6，7｝，x＝4，y＝6，z＝2，計(jì)算Sim（x，y）、Sim（x，z）.

圖1空心點(diǎn)表示該坐標(biāo)位置有樣本分布，實(shí)心點(diǎn)表示集合D的均值，均值位置偏向于小數(shù)據(jù)部分，說明小數(shù)據(jù)部分對樣本集合集中度的貢獻(xiàn)較大.因此相對于偏離均值點(diǎn)的樣本而言，靠近均值點(diǎn)的樣本更具分類特性.然而使用歐式距離，則得出D（4，6）＝2，D（2，4）＝2；使用曼哈頓距離，則M（4，6）＝2，M（2，4）＝2.因 此使用 歐 式 距 離 和 曼 哈 頓 距 離 作 為 相 似 度 度 量 函 數(shù)，將 得 出Sim（x，y）＝ S im（x，z）.

圖1 一維數(shù)據(jù)集合D分布狀態(tài)

由定義1得出，樣本x對D的分散度為：S（x，D）＝std（D｛x｝）std（D）＝1.163 6.

由定義2得出，樣本x對D的緊密度為：C（x，D）＝mean（D｛x｝）mean（D）＝0.990 5.

綜合以上，可以得出，樣本x對D 的 親和度為：A（x，D）＝S（x，D）C（x，D）＝1.174 8.

同理，A（y，D）＝1.007 5，A（z，D）＝0.954 4.

定義4 個體間親和度.個體間親和度表示兩個任意個體對集合的親和度之和，文中使用A（x，y）表示個體間親和度，其中x和y為集合中任意兩個個體.親和度值越小，表明兩個體對集合的影響力和越大.

由定義4得出，樣本x與y間親和度為：A（x，y）＝A（x，D）＋A（y，D）＝2.182 3.

同理，A（x，z）＝A（x，D）＋A（z，D）＝2.129 2.

綜上得出兩個結(jié)論：A（y，D）＞A（z，D），說明點(diǎn)y存在與否對D的影響大于點(diǎn)z存在與否對D的影響；A（x，y）＞A（x，z），表明x與y間的親和度小于x與z間的親和度.根據(jù)一維數(shù)據(jù)集D分布而言，樣本z較樣本y更靠近樣本中心，z對集合的影響力大于y對集合的影響力.

1.2 親和度應(yīng)用

傳統(tǒng)基于距離的度量無法區(qū)分出 〈 x，y〉與〈x，z〉之間的區(qū)別.而使用非曼哈頓距離，則NM（4，6）＝M（4，6）w，其中w為非曼哈頓距離的權(quán)重系數(shù).不同的w值，有著不同的樣本間非曼哈頓距離.文中設(shè)置w＝A（·，·），即上述獲取x，y，z的親和度值A(chǔ)（x，y），A（x，z）作為非曼哈頓距離的權(quán)重系數(shù)，則計(jì)算可得x與y間非曼哈頓距離為

同理，x與z間非曼哈頓距離為

由此獲得NM（x，y）＞NM（x，z）.因距離度量是相似度度量的相逆關(guān)系，故而對于樣本對〈x，y〉與〈x，z〉而言，〈x，z〉間相似度大于〈x，y〉間相似度.可得出基于親和度權(quán)重因子影響下，x與z間相似度略高于x與y間相似度，與上述分析相一致.

2 基于親和度的相似度函數(shù)

親和距離可有效處理傳統(tǒng)歐式距離、曼哈頓距離等較難判斷情況.在1.1節(jié)一維數(shù)據(jù)基礎(chǔ)上進(jìn)行必要擴(kuò)展，以適應(yīng)真實(shí)的多維數(shù)據(jù)樣本分類應(yīng)用需求.

2.1 親和距離

筆者充分考慮計(jì)算難度和樣本維度重要性的兩個層面，采用維度映射作為最小計(jì)算對象，先分別計(jì)算相應(yīng)維度的測試樣本xt和訓(xùn)練樣本xi（i＝1，2，…，N）的維度親和力，再將所有的維度親和力累加作為非曼哈頓距離，并作為KNN分類判斷準(zhǔn)則.采用維度映射優(yōu)勢有：改變傳統(tǒng)樣本整體處理策略，整體策略忽略了樣本不同特征在分類中的不同作用，為此很多學(xué)者專家提出了權(quán)重改進(jìn)策略[2，11－12]，這種處理方法必然引發(fā)運(yùn)算復(fù)雜度的增加，筆者提出的策略也存在此不足；改變了傳統(tǒng)距離處理策略，在獲取兩樣本距離的同時，引入個體特征對該特征集的親和影響力作為維度映射對的權(quán)重系數(shù).

筆者所提出的基于親和度的度量函數(shù)是對非曼哈頓距離權(quán)重系數(shù)的一種新選擇策略.上述1.1節(jié)僅以一維樣本對親和度策略解釋，擴(kuò)展到真實(shí)的d維樣本空間，判斷兩個樣本xt和xi的距離函數(shù)為

遵循緊密度的定義，可見式（1）存在兩個地方需要求解標(biāo)準(zhǔn)差，導(dǎo)致時間復(fù)雜度量級增加.為此，文中采用sstd（D）替代std（D），可簡化運(yùn)算復(fù)雜度，降低運(yùn)算量，但存在光滑性較差的不足.然而在線性分類度量中，光滑性影響可忽略，因

故式（1）轉(zhuǎn)化為

通過式（3）計(jì)算xt和xi的親和距離，公式右側(cè)為所有維度映射對親和距離的累加和.分析各維度映射對的親和距離，分為兩部分：

對于任意xt，xi，親和距離d（xt，xi）均滿足非負(fù)性.當(dāng)xt＝xi時，d（xt，xi）＝0；當(dāng)xt≠xi時，d（xt，xi）＞0.故通過上述觀察，認(rèn)為d（xt，xi）是一種基于親和度的距離函數(shù).

2.2 親和相似度

親和距離并非是相似度，不能直接進(jìn)行分類判斷，需要進(jìn)行轉(zhuǎn)換：親和距離升序或利用核函數(shù)轉(zhuǎn)換為相似度函數(shù).文中使用核函數(shù)轉(zhuǎn)化親和距離為親和相似度

分析式（4），其與常見的高斯徑向核函數(shù)K（xt，xi）＝exp（－v xt－xi2）結(jié)構(gòu)非常相似.然而文中僅采用指數(shù)函數(shù)將親和距離轉(zhuǎn)化為親和相似度，可滿足當(dāng)d（xt，xi）→ ∞ 時 ，Sim（xt，xi）→0；當(dāng)xt＝xi時，Sim（xt，xi）＝1；當(dāng)d（xt，xi）＞d（xt′，xi）時，可得到Sim（xt，xi）＜Sim（xt′，xi），符合距離度量與相似度度量的相逆情況.同時，使用核函數(shù)轉(zhuǎn)換可保證親和相似度范圍為[0，1].

2.3 算法的偽代碼

對于K近鄰分類算法而言，距離函數(shù)或相似度函數(shù)和k值選取是兩大核心.文中提出的親和相似度函數(shù)完成了對距離函數(shù)或相似度函數(shù)的度量任務(wù)，k值除3、5、7等預(yù)設(shè)值外，還采取文獻(xiàn)[14]所涉及的選取方式，k＝N1/2（N為訓(xùn)練集樣本個數(shù)·表示向下取整）.基于親和相似度的分類算法（簡稱AMKNN算法）關(guān)鍵步驟如下：

步驟1 獲取數(shù)據(jù)集D 任 一維dj（j＝1，2，…，d）的 m in（dj）和 m ax（dj）.

步驟2 初始化訓(xùn)練集TR：

若 ? min（dj）＜0，j＝1，2，…，d，則對該屬性集進(jìn)行非負(fù)設(shè)置，即對 ? i＝1，2，…，N，j＝1，2，…，d，設(shè)置dij＝dij－min（dj），用以保障 m ean（dj）、mean（dj｛xij｝）和mean（dj∪ ｛ xij｝）為非零數(shù)值；

計(jì)算各 特征維度 的特征 均 值 m ean（dj），j ＝ 1，2，…，d，用于后 續(xù) 快 速 獲 取 mean（dj｛xij｝）和mean（dj∪ ｛ xij｝）.

步驟3 統(tǒng)計(jì)出TR中各類別樣本的個數(shù)Nc，c＝1，2，…，m：

對任一xt，t＝1，2，…，n－N，進(jìn)行分類操作.

步驟4 由式（3）、（4），計(jì)算非負(fù)設(shè)置后的xt在TR中所有訓(xùn)練樣本xi，i＝1，2，…，N的親和相似度，并對親和相似度進(jìn)行排序，獲取親和相似度前k最大值Siml（xt），l＝1，2，…，k，并得到該k個樣本類別信息.

步驟5 計(jì)算

步驟6 將最大Sj的類別標(biāo)識賦值給xt，即label（xt）＝arg maxSj.

3 性能評估

3.1 理論分析

親和相似度函數(shù)是一種基于充分利用樣本集全部信息的新相似度策略.為此，AMKNN算法仍未脫離傳統(tǒng)近鄰分類算法搜索空間大的狀態(tài)，還需要3d存儲代價(jià)來存儲所有維度的最大值、最小值及均值，因此并未降低空間需求.下面分析算法最壞的時間復(fù)雜度：

步驟1 初始化復(fù)雜度為O（n）；

步驟2 初始化TR的時間復(fù)雜度為O（N）；

步驟3 獲取TR的Nc，c＝1，2，…，m，時間復(fù)雜度為O（N）；

步驟4 計(jì)算親和相似度和排序的時間復(fù)雜度為O（N）＋O（Nlog N）；

步驟5 計(jì)算類別相似度和的時間復(fù)雜度為O（km）；

步驟6 獲取最大類別相似度的時間復(fù)雜度為O（m）.

故任一xt（t＝1，2，…，n－N），分類的時間復(fù)雜度為O（n）＋2 O（N）＋O（Nlog N）＋O（km）＋O（m）.考慮到B交叉驗(yàn)證情形，TR的樣本個數(shù)為N ＝ n（B－1）B，TS的樣本個數(shù)為TS＝n B.對所有測試樣本xt而言，整體分類時間復(fù)雜度為O（n）＋2O（N）＋（n B）（O（Nlog N）＋O（km）＋O（m））.由于k，m ? n，N且N ≤ n，故上述時間復(fù)雜度可簡化為O（n2logn）.雖采取不同的交叉驗(yàn)證模式，如5交叉驗(yàn)證或10交叉驗(yàn)證等，可適度降低時間需求，但不會帶來數(shù)量級上的降低.

傳統(tǒng)KNN和NCM算法時間復(fù)雜度為O（n2logn），而MKNN算法時間復(fù)雜度為O（n3），故AMKNN同對比算法相較，并未引入多余的時間消耗.

3.2 實(shí)驗(yàn)對比

為了全面驗(yàn)證所提出親和相似度函數(shù)的優(yōu)劣性，也更好與文獻(xiàn)[10]MKNN算法及其他成熟的分類算法進(jìn)行比較，文中選取文獻(xiàn)[10]中13個小規(guī)模和其他5個較大規(guī)模UCI數(shù)據(jù)集[16].近鄰數(shù)k除選用最常見的奇數(shù)預(yù)設(shè)值外，還選用k＝[N1/2].18個數(shù)據(jù)集中13個小樣本數(shù)據(jù)集（如表1所示）、5個大樣本數(shù)據(jù)集（如表4所示），對于信息缺失不完整的樣本，其缺失屬性值僅簡單使用所有樣本該屬性的平均值來填充.

表1 小規(guī)模測試數(shù)據(jù)集

為客觀反映算法性能，采用5交叉驗(yàn)證獲得對比算法的平均分類效率及分類速度.文中所列實(shí)驗(yàn)數(shù)據(jù)，均在奔騰IV Intel（R）Xeon（R）2.40GHz 8G的PC硬件、Windows XP 64位及MATLAB 7運(yùn)行環(huán)境下獲取.其中，粗體實(shí)驗(yàn)數(shù)據(jù)表明某個數(shù)據(jù)集下所對應(yīng)的距離函數(shù)或相似度函數(shù)取得最好分類性能.

表2是親和相似度函數(shù)同常見的距離函數(shù)分類精度比較，選取k值為3的5交叉驗(yàn)證.由表2可得出，AMKNN在13個數(shù)據(jù)集對比中，有8個數(shù)據(jù)集的分類性能高于所比較算法；3個數(shù)據(jù)集的分類性能并非最好效果；然而Ionosphere、Ecoli分類性能最差，分析Ionosphere、Ecoli數(shù)據(jù)特點(diǎn)，均為維數(shù)據(jù)分布緊密，其維極值差很小，其個體對整體的維均值和維方差變化極小，說明AMKNN對此類數(shù)據(jù)分布處理能力有待提高.

表2 AMKNN函數(shù)同傳統(tǒng)距離函數(shù)分類精度比較

表3為親和相似度函數(shù)同若干改進(jìn)的距離或相似度函數(shù)的分類精度比較，分類精度優(yōu)勢等結(jié)論同表2相似.在13個數(shù)據(jù)集對比中，AMKNN（5，3）在9個數(shù)據(jù)集的分類性能高于所比較算法；余下數(shù)據(jù)集的分類性能并非最好效果.

表3 小規(guī)模數(shù)據(jù)集下AMKNN函數(shù)同改進(jìn)距離或相似度函數(shù)分類精度比較

表3同時進(jìn)行了不同k值下AMKNN函數(shù)的分類精度比較.表3數(shù)據(jù)顯示當(dāng)k＝N1/2時，仍能保持較高的分類精度，其分類性能不低于預(yù)設(shè)奇數(shù)3、5、7等k值分類性能.筆者所提出的AMKNN函數(shù)同NCM、MKNN處理策略相似，均以維度距離或者維度相似度為處理對象，最終通過累加或累積方式獲取到樣本間的距離度量或相似度度量.故較傳統(tǒng)的以樣本整體為處理對象的算法而言，其運(yùn)算復(fù)雜度有了較大的提升.而圖2數(shù)據(jù)顯示，對NCM、MKNN而言，AMKNN算法在運(yùn)行時間介于兩者之間，并未引入過多的運(yùn)算復(fù)雜度.分析其原因，NCM是三者中運(yùn)算最簡單的算法，而MKNN同AMKNN在計(jì)算樣本距離中時間復(fù)雜度相同，但MKNN較AMKNN在樣本距離獲取及轉(zhuǎn)換為相似度過程中，增加了運(yùn)算時間量.

上述試驗(yàn)表明AMKNN算法在小樣本集處理方面分類精度優(yōu)勢明顯，但伴隨緊密度和分離度的計(jì)算，引入了一定的時間消耗.進(jìn)而得出在大規(guī)模樣本集處理過程中，AMKNN算法必然引入非常大的時間消耗，因此不適合直接應(yīng)用與大規(guī)模樣本集分類.目前K－D樹、B＋樹等樹型索引結(jié)構(gòu)[15]，均采用對數(shù)據(jù)集進(jìn)行空間分割和建立快速索引技術(shù)，實(shí)現(xiàn)對大規(guī)模數(shù)據(jù)快速搜索范圍及近鄰獲取的能力.因此嘗試將AMKNN函數(shù)和K－D樹結(jié)合在一起，借助高效索引算法的快速近鄰搜索優(yōu)勢，降低AMKNN分類算法在大規(guī)模數(shù)據(jù)集上分類速度.

表4 大規(guī)模測試數(shù)據(jù)集

表5是集成AMKNN和K－D樹的AM－KD算法同其他算法的比較，其中傳統(tǒng)的KNN和AMKNN算法無需預(yù)先對數(shù)據(jù)進(jìn)行索引結(jié)構(gòu)預(yù)處理，故無預(yù)處理時間部分，而KD樹和AM－KD算法需要預(yù)處理；K－D樹算法采取傳統(tǒng)的維度分割為索引創(chuàng)建準(zhǔn)則，通過歐氏距離獲取所需近鄰；AM－KD算法首先創(chuàng)建傳統(tǒng)K－D樹結(jié)構(gòu)，其次在近鄰獲取階段擴(kuò)充近鄰個數(shù)，最后使用親和相似度來度量及其分類決策來標(biāo)識未知樣本類別信息.AM－KD并未對K－D樹索引組織準(zhǔn)則改進(jìn)，雖親和距離同歐氏距離準(zhǔn)則不同，但仍得出樣本間歐式距離小，其親和距離也相對較小的結(jié)論.為此，為避免K－D樹分割過程造成的親和距離分割誤差，故通過獲取較多的近鄰個數(shù)來降低影響，在近鄰獲取階段獲取2k近鄰，在分類決策中使用前k最大親和相似度的樣本類別信息.

圖2 AMKNN與NCM、MKNN算法分類速率比較

表5 大規(guī)模數(shù)據(jù)集分類精度和運(yùn)行時間比較

表5中“－”、“－－”分別表示算法分類時間超5、10小時之上；除括號內(nèi)所示的分類時間外，其余數(shù)據(jù)均為各算法的總運(yùn)行時間數(shù)據(jù).表5對比數(shù)據(jù)顯示AMKNN算法雖能保持較好的分類效率，但由于親和相似度計(jì)算的需求，引入了難以接受的時間代價(jià)，故使用單一AMKNN算法解決大規(guī)模數(shù)據(jù)分類問題的可操作性差；AM－KD算法有效利用K－D樹算法快速搜索優(yōu)勢，先獲取初步近鄰集合，在此基礎(chǔ)上應(yīng)用AMKNN算法，既降低了整個搜索空間的運(yùn)算代價(jià)，又較好應(yīng)用親和相似度解決大規(guī)模問題，其時間代價(jià)相對單一AMKNN算法有了數(shù)量級降低.后續(xù)AMKNN算法同其他快速算法如何結(jié)合成為處理高維大規(guī)模數(shù)據(jù)集分類的一個探索方向.

4 結(jié)束語

筆者所提出的基于分散度和緊密度的親和相似度函數(shù)，存在以下創(chuàng)新之處：首先在分析已有的親和度量和近鄰域計(jì)數(shù)等算法基礎(chǔ)上，引入了樣本的緊密度和分散度定義；其次關(guān)注個體樣本對整體數(shù)據(jù)集的親和度影響，通過累加的維親和距離得到樣本的親和距離，進(jìn)而轉(zhuǎn)換為樣本相似度；最后歸一化傳統(tǒng)曼哈頓距離，消除不同屬性量綱級別對分類結(jié)果的影響.算法理論分析及實(shí)驗(yàn)數(shù)據(jù)對比表明，AMKNN算法在保障數(shù)據(jù)處理精度的基礎(chǔ)上，同已有算法運(yùn)算相比，未引入過多的運(yùn)算代價(jià)，故所提出的親和相似度函數(shù)是一種有效的分類相似度策略，但仍存在有待改進(jìn)之處：高維度大規(guī)模數(shù)據(jù)的處理能力仍有待增強(qiáng)；快速搜索能力仍不具備；抗噪音性能未得到明顯改善等，這些將作為后續(xù)研究內(nèi)容.

[1] Wu Xindong，Kumar V，Quinlan J R，et al.Top 10Algorithms in Data Mining[J].Knowledge and Information Systems，2008，14（1）：1－37.

[2] Hakan A.Improving the k－nearest Neighbour Rule：Using Geometrical Neighbourhoods and Manifold－based Metrics[J].Experts Systems，2011，28（4）：391－406.

[3] Towell G，Shavlik J，Noordewier M.Refinement of Approximate Domain Theories by Knowledge－Based Neural Networks[C]//Proceedings of 18th National Conference on Artificial Intelligence.Cambridge：MIT Press，1990：861－866.

[4] Lin Zhiwei，Wang Hui，Sally M.A Multidimensional Sequence Approach to Measuring Tree Similarity[J].IEEE Transactions on Knowledge and Data Engineering，2012，24（2）：197－208.

[5] Olson D L，Delen D.Advanced Data Mining Techniques[M].Berlin：Springer，2008：39－52.

[6] Huan J，Wang W，Prins J，et al.Spin：Mining Maximal Frequent Subgraphs from Graph Databases[C]//Proceedings of the 10th ACM SIGKDD International conference on Knowledge Discovery and Data Mining.New York：ACM，2004：581－586.

[7] 陳鳳，杜蘭，保錚.一種優(yōu)化K近鄰準(zhǔn)則及在雷達(dá)HRRP目標(biāo)識別中的應(yīng)用[J].西安電子科技大學(xué)學(xué)報(bào)，2007，34（5）：681－686.

Chen Feng，Du Lan，Bao Zheng.Modified KNN Rule with Its Application in Radar HRRP Target Recognition [J].Journal of Xidian University，2007，34（5）：681－686.

[8] Hui Wang.Neighborhood Counting Measure and Minimum Risk Metric[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（4）：766－768.

[9] Zeng Yong，Yang Yupu，Zhao Liang.Pseudo Nearest Neighbor Rule for Pattern Classification[J].Expert Systems with Applications，2009，36（2）：3587－3595.

[10] Bhattacharyra G，Ghosh K，Chowdhury A S.An Affinity－based New Local Distance Function and Similarity Measure for kNN [J].Patter Recognition Letters，2012，33（3）：356－363.

[11] Hu Qinghua，Zhu Pengfei，Yang Yongbin，et al.Large－margin Nearest Neighbor Classifiers Via Sample Weight Learning[J].Neurocomputing，2011，74（4）：656－660.

[12] Gou Jianping，Zhang Yi，Du Lan，et al.A Local Mean－Based k－Nearest Centroid Neighbor Classifier[J].Computer Journal，2012，55（9）：1058－1071.

[13] Gao Yunlong，Pan Jinyan，Ji Guoli，et al.A Novel Two－level Nearest Neighbor Classification Algorithm Using an Adaptive Distance Metric[J].Knowledge－based Systems，2012（26）：103－110.

[14] Mitra P，Murthy C A，Pal S K.Unsupervised Feature Selection Using Feature Similarity[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（3）：301－312.

[15] Adam M.An Externalization of the k－d tree[J].Romanian Journal of Information Science and Technology，2007，10（4）：323－333.

[16] Asuncion A，Newman D J.UCI Machine Learning Repository[EB/OL].[2012－06－10].http：//archive.ics.uci.edu/ml/.