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

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

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

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

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

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

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

1 相關研究

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

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

1.1 KNN算法基本概念

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

算法1 KNN algorithm

輸入：訓練數(shù)據(jù)集t_Set，未知樣本test_Data，k。

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

(1)數(shù)據(jù)歸一化。

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

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

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

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

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

從算法1可發(fā)現(xiàn)，KNN算法對未知樣本分類時，需與數(shù)據(jù)集中的每個數(shù)據(jù)樣本進行距離計算，對于一個D維數(shù)據(jù)集，計算復雜度和數(shù)據(jù)集中的數(shù)量N成正比，則時間復雜度為O(DN2)。因此當分類遇到大規(guī)?；蚋呔S數(shù)據(jù)的數(shù)據(jù)集時，容易發(fā)生維度爆炸，算法分類效率大大降低。

1.2 距離度量方式

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

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

(1)

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

(2)

2 KNN優(yōu)化算法

2.1 建立搜索樹

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

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

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

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

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

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

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

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

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

(3)

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

(4)

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

(5)

2.2 初始化搜索樹

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

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

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

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

2.3 KNN-WST算法

2.3.1 KNN-WST算法基本概念

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

KNN-WST算法對KNN算法優(yōu)化過程具體表現(xiàn)在如下三個方面。

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

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

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

2.3.2 KNN-WST算法流程

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

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

算法2 KNN-WST algorithm

輸入：訓練數(shù)據(jù)集t_Set，未知樣本test_Data，k。

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

預處理階段

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

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

查找階段

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

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

分類階段

(5) ifs_Clusters.num=1。

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

(7) else ifs_Clusters.num

(8) thenk=s_Clusters.num。

(9) end if。

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

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

3 仿真實驗

3.1 數(shù)據(jù)集信息

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

表1 數(shù)據(jù)集基本信息Table 1 Basic information of datasets

3.2 評價指標

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

(4)

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

3.3 最優(yōu)距離計算公式仿真

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

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

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

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

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

3.4 KNN-WST算法仿真

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

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

表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個高維數(shù)據(jù)集上分類準確率的詳細數(shù)據(jù)。KNN-WST算法較KNN算法分類準確率都有所提高，依次提高7.67%、0.28%、4.42%、1.77%、9.80%、1.82%，從一定程度上提高了KNN算法的準確率。

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

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

表4 4種算法對比試驗數(shù)據(jù)Table 4 Comparison test data of four algorithms

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

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

4 結論

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