基于權重搜索樹改進K近鄰的高維分類算法

梁淑蓉, 陳基漓,2*, 謝曉蘭,2

(1.桂林理工大學信息科學與工程學院, 桂林 514004； 2.廣西嵌入式技術與智能系統重點實驗室, 桂林 514004)

技術的發展促使數據集凸顯規模和復雜性，與低維數據相比，高維空間中不同數據之間的相似性概念變得模糊，因此對高維數據的挖掘，機器學習方法將面臨嚴峻考驗。一方面，根據數據索引構造的數據挖掘性能減退；另一方面，根據距離度量函數的全維度挖掘失去效果。例如：在高維空間中的K近鄰分類算法(Knearest neighbors，KNN)，由于數據之間距離的概念不復存在，距待分類數據的最近點和最遠點之間的距離幾乎相等，使得最近鄰計算無法區分最近鄰域。如何提高算法的效率是高維數據分類面臨的挑戰。

針對這一問題，許多學者對高維空間中維數災難問題開展研究。一類研究通過降維技術去除冗余信息，來實現減少計算量和時間的目的。李勇等[1]提出一種通過可變K近鄰局部線性嵌入(locally linear embedding,LLE)降低數據維度的方法，使得即使在維數減小后的特征向量情況下，也可以在高維空間中保留拓撲結構并實現高檢索精度。萬靜等[2]為了降低不確定數據對聚類產生的影響，將數據劃分為值不確定和維數不確定，并采用期望公式度量距離，再通過K近鄰查詢來找尋不確定數據的近似值，此算法具有良好的抗噪聲特性和可伸縮性。還有一些研究通過對特征屬性進行加權，“忽略”某些屬性以實現降維的效果。為了提高高維數據中KNN分類的準確性，Zhu等[3]提出了一種新的KNN方法，該方法實現高維數據的屬性選擇和屬性權重加權，能消除不相關屬性并獲得原始預測屬性的表達式。李金孟等[4]提出一種HWNN算法，用于高維不平衡數據的維度災難和類不平衡分布的問題，通過類加權方法增加少數類在所有樣本中的分布系數，在普通維度的不平衡數據中，該算法的預測精度也很顯著。Hadi等[5]在初始階段使用平滑修剪的絕對偏差(smooth integration of counting and absolute deviation，SCAD)Logistic回歸，同時構建每個特征在相異度度量的重要性，并使用特征貢獻作為歐幾里德距離中SCAD系數的函數，該方法能消除幾乎所有非信息性特征，在準確性和降維方面均具有良好的性能。

以上方法均從如何降低維度進行研究，未考慮距離計算公式的優劣對高維數據的影響。一類研究則是通過優化距離計算方式來提高分類效率，雷宇曜等[6]提出一種歸一化函數，在演化過程中對密度函數應用了Minkowski距離差“K近鄰”的方法，以加快算法收斂速度，其性能相對其他算法具有優勢。Huang等[7]提出了一種基于自適應簇距離限制的改進的KNN搜索算法，該算法通過減少處理器成本來實現高維索引，使用三角形不等式濾除不必要的距離計算而實現，但該算法預處理成本較高。Wang[8]提出一種算法，這種算法使用聚類和三角形不等式減少距離的計算，加速高維空間中近鄰搜索，將距離計算減少2～80倍，并將速度提高了2～60倍。

綜上，高維數據不僅使數據挖掘呈現“維度災難”，同時常用的歐式距離公式不能很好地面對日漸增長的數據規模。為了解決這些問題，本文提出基于權重搜索樹改進K-近鄰(K-nearest neighbor algorithm based on weight search tree, KNN-WST)的高維分類算法，需先根據數據集屬性按一定規則構造搜索樹，把數據按搜索樹劃分成不同的矩陣區域，樹的葉子結點存儲對應矩陣區域數據的索引，其中由于矩陣區域所包含的數據都經過相同分支路徑，因此這些數據之間互為相似。當需要對未知樣本進行分類時，未知樣本查找搜索樹可以得到與其最為接近的葉子節點，并只與存儲在該葉子結點的索引映射數據計算相似性。簡言之，僅計算未知樣本與查找搜索樹所獲數據之間距離。一方面針對高維數據中數據之間距離的概念變得模糊，分類效率下降的情況，研究和討論適合高維數據的距離計算方式。另一方面針對高維數據“維災”的特征，引入樹形結構，利用部分特征屬性按一定規則構造搜索樹，將高維數據劃分為不同的矩陣區域，分類僅與一個矩陣區域內數據距離度量，減少距離比較次數，從而達到降維和提高KNN算法在高維數據中分類效率的目的。

1 相關研究

Cover等[9]提出的KNN算法是最簡單、最高效的機器學習算法之一，在實踐應用中發揮著積極的作用[10-12]。該算法是一種惰性學習，即在分類過程中沒有訓練的階段，數據集事先已知分類類別和特征屬性，需要分類的未知樣本直接進行分類處理。

該模型結構簡單且易于理解，通常無需多個參數即可獲得良好的性能。許多研究者對KNN算法的改進方法及應用方向仍保持熱忱。例如：齊斌等[13]改進了表示KNN加權局部線性文本特征的方法，對表示系數進行加權使其稀疏，并引入非負約束來避免噪聲對表示系數的干擾。李峰等[14]將標簽空間劃分為幾個顆粒狀標簽，計算每個標簽的權重系數，解決了算法忽略標簽之間相關性的問題。朱利等[15]提出了一種基于K-d樹的近似KNN空間聚類算法，利用K-d樹的數據結構進行空間聚類，具有更好的性能。但這些改進方式未能考慮高維數據的影響，不能很好地適應當今大數據分析能力的要求。

1.1 KNN算法基本概念

KNN分類算法的核心思想是判斷數據之間距離的大小，距離越近則兩數據之間的相似性越大。具體的實現步驟為：通過未知樣本與數據之間的距離計算，在最接近未知樣本的k個“最近鄰”中找到最常出現的類別，這個類別為未知樣本經過分類得到的類別。實現具體形式如算法1介紹。

算法1 KNN algorithm

輸入：訓練數據集t_Set，未知樣本test_Data，k。

輸出：未知樣本的分類類別。

(1)數據歸一化。

(2)計算未知樣本test_Data與t_Set之間的距離D, {d1,d2,…,di}∈D,i=1,2,…,t_Set.num。

(3)D按距離遞增次序排序。

(4)選取與未知樣本距離最小的k個點。

(5)計算這k個點所在類別出現的頻率。

(6)返回出現頻率最高的類別作為未知樣本的分類類別。

從算法1可發現，KNN算法對未知樣本分類時，需與數據集中的每個數據樣本進行距離計算，對于一個D維數據集，計算復雜度和數據集中的數量N成正比，則時間復雜度為O(DN2)。因此當分類遇到大規模或高維數據的數據集時，容易發生維度爆炸，算法分類效率大大降低。

1.2 距離度量方式

歐氏距離是一種常用的距離度量方式，隨著數據集維度的增長，歐氏距離已無法高效地度量全空間相似性[16-17]。通過論述不同距離公式，包括曼哈頓距離、歐氏距離和切比雪夫距離，實驗驗證何種方式更適合在高維數據中度量相似性距離。

閔氏距離最早由Minkowski提出，且閔氏距離與特征屬性的量綱有關，設n維空間中有兩點坐標x、y，閔氏距離定義為

(1)

式(1)中：xu、yu為u(u=1,2,…,n)維空間中的兩點坐標；p為常數，不同的p分別代表不同的度量方式，具體表示為

(2)

2 KNN優化算法

2.1 建立搜索樹

樹形結構具備三大特點：強直觀、數據存儲低冗余和高效遍歷，在大量數據處理方面優勢更為突出。搜索樹的建立是一個自上而下的過程，根據數據集特征屬性的權重以及一定分支規則對數據空間劃分，構成一系列不同的矩陣區域，稱這些區域為訓練數據集的粗略簇，此時粗略簇內的數據相互之間都是“相似”的。

構建搜索樹模型方法如下。

步驟1在有n維特征屬性的維數據集中，使用熵權法計算特征屬性權重。

步驟3將影響因子集結點按序取出作為結點node建樹，使用三等分法得到每個屬性包含數據的左中值Lmid和右中值Rmid兩個劃分閾值，根據兩閾值作為分支條件，生成3個分支。

步驟4根據步驟3 的分支規則，將影響因子集中每個結點都作為一個父節點，與3個分支構成一棵子樹，直至完畢。

步驟5將步驟4中生成的子樹按影響因子集中原結點順序排序。

步驟6排序好的子樹逐一取出建樹，第1棵子樹的父結點放在第0層，作為搜索樹的根結點，因根結點有3條分支，即第1層結點數為3，且均為第2棵子樹的父結點。以此類推，第i層結點對應第i+1棵子樹的父結點，直到n/3棵子樹均被取出。

其中，作為一種客觀加權法，熵權法可以確定指標的權重，剔除對評價結果無明顯貢獻的指標。對于一項數據樣本，由于樣本中每個特征屬性與同一類別中的其他特征屬性相比，其作用和影響力各不相同，從而對樣本分類的貢獻值也不同。故認為，權重值越大的特征屬性，對于數據的重要性越高，越能決定數據的類別。對于包含m個樣本，n個特征數的數據集，形成初始數據矩陣R=(rij)m×n，其中rij為第j個特征下第i個樣本的評價值。其特征屬性權重計算方法如下。

(1)計算第j個特征下第i個樣本的指標值比重pij，公式為

(3)

(2)根據第j個特征的比重pij計算其熵值ej，公式為

(4)

(3)可得第j個特征的熵權wj，即第j個特征的權重，表示為

(5)

2.2 初始化搜索樹

初始化搜索樹的過程即對數據劃分過程，訓練數據從搜索樹的根結點root進入，根據每個結點node不同的分支條件，將訓練數據劃分到不同矩陣區域。

其中，每個結點node記錄經過結點的數據索引并傳到與之連接的下一結點中，直到數據到達最高層葉子結點，最高層葉子結點記錄數據集由搜索樹劃分后屬于該矩陣區域的數據索引，搜索樹結構如圖1所示。

圖1 搜索樹模型結構Fig.1 Search tree model structure

對一個有n個特征屬性的數據集，取n/3項屬性構建搜索樹，此時樹的每層結點均為同一特征屬性結點，第l層的結點數量為3l[l∈(0,1,…,n/3)]個。初始化搜索樹的過程是將數據集按搜索樹的分支規則劃分為不同的矩陣區域，矩陣區域內數據索引I存儲在相應的葉子結點中，此時的矩陣區域稱為數據集經過搜索樹劃分出的粗略簇。

2.3 KNN-WST算法

2.3.1 KNN-WST算法基本概念

針對高維數據對智能算法造成的短板，提出的KNN-WST算法利用樹形結構改進KNN算法，此改進達到了降維的目的，加速了最近鄰的確定，從而減少了KNN算法分類時距離的計算次數。

KNN-WST算法對KNN算法優化過程具體表現在如下三個方面。

(1)預處理階段，將數據樣本集通過上述建樹、初始化搜索樹兩步驟，劃分出一系列不同的矩陣區域，此時的矩陣區域可視為訓練數據集的粗略簇。

(2)在查找階段，依據未知樣本特征屬性查找搜索樹，得到的粗略簇視為與之最相似的相似簇。

(3)最后的分類階段，將待未知本與相似簇中的數據進行相似性計算，從而得到未知樣本的預測分類結果。

2.3.2 KNN-WST算法流程

KNN-WST算法的偽代碼如算法2所示，其流程圖由圖2給出。

圖2 KNN-WST算法流程圖Fig.2 KNN-WST algorithm flow chart

算法2 KNN-WST algorithm

輸入：訓練數據集t_Set，未知樣本test_Data，k。

輸出：未知樣本的分類類別。

預處理階段

(1) 利用訓練數據集t_Set特征向量構建搜索樹s_tree。

(2) 將訓練數據集t_Set對s_tree進行初始化。

查找階段

(3) 查找未知樣本test_Data經過s_tree分支規則得到的葉子結點。

(4) 對照葉子結點存儲的索引取出t_Set中數據樣本，構成一個相似簇s_Clusters。

分類階段

(5) ifs_Clusters.num=1。

(6) then 未知樣本test_Data分類結果與s_Clusters中數據類型一致。

(7) else ifs_Clusters.num

(8) thenk=s_Clusters.num。

(9) end if。

(10) 根據算法1計算test_Data與s_Clusters內點之間的相似性，得到test_Data分類類別。

算法的實現通過對訓練數據集進行屬性權重計算，根據占權重值最大的1/3項屬性構建搜索樹，并對此搜索樹初始化，此時搜索樹中葉子結點存儲索引所對應數據構成了許多粗略簇，粗略簇中數據互為“相似”。當未知樣本分類時，將通過搜索樹查找“相似”于未知樣本的粗略簇，由于未知樣本和粗略簇所經過的劃分規則一致，可視未知樣本與粗略簇中的數據最為相似，此時粗略簇又可稱為相似簇。分類計算需判斷相似簇中數據數量，特別的是當僅有一個數據時，則認為未知樣本與該數據同類，該數據的類別即為未知樣本的預測類別；或當數據數量小于預設k時，需將k更新后再度量距離。因為經過搜索樹的劃分，未知樣本與對應相似簇內數據具有較高的相似性，所以能在縮小計算規模的同時保證分類的準確率。

3 仿真實驗

3.1 數據集信息

在仿真實驗中，實驗環境為：Windows 7操作系統，1.50 GHz CPU，8 GB內存，通過MATLAB仿真驗證算法。從UCI數據集中選擇了11個標準數據集進行模擬，分別驗證本文算法的有效性。同時為提高模型的泛化能力，實驗使用留出法按3∶7對數據集隨機劃分為測試集和訓練集。數據集基本信息如表1所示，其中前5個數據集Haberman、Heart、Cancer、Vehicle、Ionosphere為低維數據集，后6個數據集German、Seismic-bumps、Cardiotocography、Spambase、Robotnavigation、Letter為高維數據集。

表1 數據集基本信息Table 1 Basic information of datasets

3.2 評價指標

主要采用分類計算損耗時間(T)和準確率(A)兩個指標評估算法性能，分類計算損耗時間T為從開始分類到最終得出未知樣本的類別所消耗的時間，準確率A指全部測試樣本使用算法自動分類的結果同人工分類結果一致的比率。A計算表達式為

(4)

式(4)中：TP為正確分類的正例數目；TN為正確分類的負例數目。

3.3 最優距離計算公式仿真

由于在高維數據中，數據之間距離的概念變得模糊，歐式距離不能很好應對維災的挑戰，所以對閔式距離進行實驗討論。通過對曼哈頓距離、歐氏距離和切比雪夫距離三種距離計算方式結合KNN算法，仿真采用準確率Acc評價不同距離公式的優劣性，仿真結果如表2所示。

表2為k取2～24時，不同度量方式得到的最優分類準確率，通過表2比較可得出如下結論。

表2 不同距離度量公式分類準確率Table 2 Classification accuracy of different distance measurement formulas

(1)在數據集特征屬性和實例數都少的情況下，3種距離度量方式計算出的結果近似，其中歐氏距離在3個低維數據集中表現良好，曼哈頓距離和切比雪夫距離只在一個低維數據中具有較好的分類準確率。

(2)隨著數據維數增高，在實例數達到千量級以上的6個高維數據集中，曼哈頓距離度量方式在5個高維數據集中表現最好，歐式距離只在一個高維數據中略微優于曼哈頓距離，切比雪夫公式計算結果最差。因此，相比常用的歐氏距離，曼哈頓距離更適合度量在高維數據中度量數據之間的距離。

3.4 KNN-WST算法仿真

KNN-WST算法相較KNN算法引入樹形結構，把數據集劃分成不同的矩陣區域，可以大幅減少數據規模，降低時間復雜度。為了驗證假設，對KNN-WST算法與KNN算法在6個高維數據集開展對比實驗，其中經3.3節可知，曼哈頓距離度量方式更適用于高維數據，因此以下實驗中KNN-WST算法和KNN算法均使用曼哈頓計算距離。

表3為不同k下，KNN算法和KNN-WST算法在6個高維數據集中分類計算損耗時間T，可以觀察到KNN-WST算法比KNN算法平均損耗時間T上最少降低了12.7%，最多降低了80.1%。改進后的KNN-WST算法降低了數據集維度，計算復雜度下降，分類時間得到大幅優化。

表3 KNN算法和KNN-WST算法在不同k值下分類所需時間對比Table 3 Comparison of the T required for classification under different k value in case of KNN and KNN-WST

圖3顯示了k為2～24時，KNN算法和KNN-WST算法分別在6個高維數據集上分類準確率的詳細數據。KNN-WST算法較KNN算法分類準確率都有所提高，依次提高7.67%、0.28%、4.42%、1.77%、9.80%、1.82%，從一定程度上提高了KNN算法的準確率。

圖3 KNN算法和KNN-WST算法在6個數據集上的分類準確率Fig.3 Classification accuracy of KNN and KNN-WST on six datasets

同時，為了進一步驗證提出算法的有效性，KNN-WST算法還同經典的分類算法：決策樹和支持向量機(support vector machine，SVM)在6個標準高維數據集中進行比較，比較各類算法分類損耗時間和分類準確率，4種算法對比試驗數據如表4所示。

表4 4種算法對比試驗數據Table 4 Comparison test data of four algorithms

表4顯示了KNN-WST算法與KNN算法、決策樹、SVM算法的對比實驗結果，從實驗數據來看：KNN-WST算法在時間開銷和分類準確率都優于KNN算法和決策樹；對比公認適合處理高維特征的SVM算法，KNN-WST的分類準確率與其不相上下，在5個數據集中表現最優，SVM算法在3個數據集中準確率最高，并且由于SVM算法需對參數尋優，在分類時間開銷上遠遠大于KNN-WST算法，因此KNN-WST算法較優于SVM算法。

通過以上仿真可知：隨著數據集規模的增大，曼哈頓距離度量方式相對于常用的歐氏距離更適合在高維數據中計算相似性。同時通過仿真證明，KNN-WST算法能在略微提高分類準確率的情況下，大幅優化分類的時間開銷，減少計算能耗，為今后高維數據分類的相關問題提供一定的參考。

4 結論

針對KNN算法在高維數據環境下分類存在占用資源高、計算量大等缺陷，提出KNN-WST算法：利用數據集特征屬性權重按一定規則構建搜索樹，使數據集劃分成不同的矩陣區域，未知樣本只與“相似”的矩陣區域計算距離，減小未知樣本與數據計算規模從而達到優化。其優點在于采用樹形結構減少數據規模，距離計算次數大幅減少，使得分類的時間開銷減少，同時分類準確率也有所提高。同時也討論了在高維環境下，不同距離度量公式的優劣，得出曼哈頓距離更適合在高維數據中使用?；贙NN-WST算法設計更優改進算法，對矩陣區域中數據量唯一時，未知樣本分類結果如何確定可作為下一步研究方向。