基于kd-樹的快速鄰域分類方法

張艷芹, 楊習(xí)貝, 陳向堅(jiān)

(1.徐州工程學(xué)院 經(jīng)濟(jì)學(xué)院, 徐州 221018) (2.江蘇科技大學(xué) 計(jì)算機(jī)學(xué)院, 鎮(zhèn)江 212003)

粗糙集理論[1]經(jīng)歷了近40年的發(fā)展,因其不同種類的變型[2]易于適應(yīng)各種結(jié)構(gòu)復(fù)雜、種類繁多的數(shù)據(jù)分析需求,在眾多領(lǐng)域得到了成功的應(yīng)用．在各類粗糙集的擴(kuò)展模型中,文獻(xiàn)[3-5]中提出的鄰域粗糙集方法尤其引人關(guān)注．這主要是因?yàn)猷徲虼植诩椒ú捎镁嚯x度量來構(gòu)建鄰域信息粒,不僅可以有效處理連續(xù)型數(shù)據(jù),還可以對(duì)符號(hào)型與連續(xù)型共存的混合數(shù)據(jù)進(jìn)行分析[6-12]．除此之外,更為重要的是鄰域粗糙集利用半徑來控制樣本間的距離,以判定不同樣本是否屬于同一鄰域信息粒,因此在不同半徑下,自然地為鄰域信息粒構(gòu)建了一個(gè)多粒度結(jié)構(gòu)．這種多粒度結(jié)構(gòu)符合人類分層遞階的認(rèn)知機(jī)理與自然思維模式．

以鄰域粗糙集模型為基本框架，文獻(xiàn)[3-4]中提出了一種基于多數(shù)投票原則的鄰域分類方法(NC),其過程主要分為基于鄰域粗糙集的特征選擇和基于多數(shù)投票原則的鄰域分類兩大部分．NC無論是在特征選擇階段,還是在鄰域分類階段,最為關(guān)鍵的步驟是鄰域信息?；?例如利用較小半徑所得到的鄰域信息?；谝恍┓诸悊栴}上往往能夠展現(xiàn)較好的性能,但這并非絕對(duì)事實(shí),當(dāng)樣本分布不平衡時(shí),小半徑反而會(huì)對(duì)小類樣本的判定帶來困擾．鑒于此,近年來有關(guān)鄰域信息?；椒ǖ难芯看蠖嘁蕴嵘徲蚍诸惖臏?zhǔn)確率為目的,試圖探尋一種數(shù)據(jù)自身性質(zhì)驅(qū)動(dòng)的鄰域半徑自適應(yīng)方法；很少有人注意到良好的鄰域搜索方式對(duì)提升NC效率的重要現(xiàn)實(shí)意義．眾所周知,已有的鄰域信息?；椒ㄍㄟ^線性掃描來尋找特定樣本的鄰域空間．當(dāng)數(shù)據(jù)規(guī)模較為龐大時(shí),線性掃描基于的鄰域搜索方式將會(huì)因需要遍歷所有樣本而變得非常耗時(shí)．

kd-樹作為一種對(duì)k維空間中的樣本進(jìn)行存儲(chǔ)，以便對(duì)其進(jìn)行快速搜索的樹形數(shù)據(jù)結(jié)構(gòu),已被廣泛應(yīng)用于聚類分析[13]、圖像匹配[14]、信息檢索等領(lǐng)域．kd-樹是對(duì)k維空間進(jìn)行劃分的二叉樹,其每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)k維超矩形區(qū)域,利用kd-樹可以省去對(duì)大部分樣本的搜索,從而減少搜索的計(jì)算量．為此,文中將借助kd-樹這一可被用于快速樣本搜索的樹形結(jié)構(gòu),提出一種基于kd-樹的快速鄰域分類方法kdtree-NC,該方法在特征選擇與鄰域分類兩階段的信息?；^程中,均采用基于kd-樹的快速鄰域搜索方式，代替?zhèn)鹘y(tǒng)NC中的線性遍歷搜索．

1 相關(guān)工作

1.1 鄰域粗糙集

分類學(xué)習(xí)任務(wù)可表示為四元組,其中,U={x1,x2,…,xn}，表示所有n個(gè)研究樣本構(gòu)成的集合,稱為論域;A={a1,a2,…,am}，為描述論域中所有樣本的特征集合;Va為特征a的值域;f:U×A→V為信息函數(shù)．特別地,若A=C∪D,C為條件特征集合,D為決策特征,那么分類學(xué)習(xí)任務(wù)可被視作一決策系統(tǒng)DS．

定義1[3]給定任意一樣本xi∈U,B?C,特征集合B下xi的鄰域δB(xi)可定義為:

δB(xi)={xj|xj∈U,ΔB(xi,xj)≤δ}

(1)

式中：δ為鄰域半徑；Δ為度量函數(shù)；?xi,xj,xk∈U,特征集合B下樣本間的度量函數(shù)ΔB滿足:

(1) 非負(fù)性:ΔB(xi,xj)≥0, 其中ΔB(xi,xj)=0當(dāng)且僅當(dāng)xi=xj;

(2) 對(duì)稱性:ΔB(xi,xj)=ΔB(xj,xi);

(3) 三角不等式:ΔB(xi,xj)≤ΔB(xi,xk)+ΔB(xk,xj).

目前,已有大量的度量函數(shù)被廣泛使用[15]．給定m維特征空間A={a1,a2,…,am}中的兩個(gè)樣本xi和xj,f(x,ai)表示樣本x在第ai維上的特征值,那么曼哈頓距離、歐式距離以及高斯距離分別定義:

(2)

(3)

(4)

在定義1中,δB(xi)是由樣本xi在特征集合B下誘導(dǎo)的鄰域信息粒,其大小依賴于鄰域半徑δ的選取,δ越大,將有越多的樣本落入到xi的鄰域空間中．若特征集合B誘導(dǎo)了一系列的鄰域信息粒,則決策系統(tǒng)可被稱為鄰域決策系統(tǒng)NDS．

定義2[3]給定一鄰域決策系統(tǒng)NDS=,δB(xi)是由樣本xi在特征集合B?C下誘導(dǎo)的鄰域信息粒,?S?U,特征集合B下S的下、上近似集合分別定義:

(5)

(6)

定義3給定一鄰域決策系統(tǒng)NDS=,U/IND(D)={πd1, πd2,…, πdp}是由決策特征D誘導(dǎo)的論域上的劃分,?B?C,決策特征D相對(duì)于條件特征集合B的鄰域依賴度可用γ(B,D)表示,其定義:

(7)

式中：|·|為集合的基數(shù)；?πdi∈U/IND(D)；πdi為一決策類．

鄰域依賴度γ(B,D)度量了特征集合B誘導(dǎo)的粒化空間對(duì)決策D上各決策類的近似能力．在鄰域決策系統(tǒng)中,鄰域依賴度具有單調(diào)性,即若B1?B2,則γ(B1,D)≤γ(B2,D)成立,在此基礎(chǔ)上,可以設(shè)計(jì)出鄰域粗糙集下的特征選擇方法．

定義4給定一鄰域決策系統(tǒng)NDS=,?B?C,B為C的一個(gè)約簡(jiǎn)，當(dāng)且僅當(dāng)滿足:

(1)γ(B,D)=γ(C,D);

(2) ?B′?B,γ(B′,D) ≠γ(B,D).

由定義4可知,條件特征C的約簡(jiǎn)是保持決策特征D的鄰域依賴度不變的最小子集．在實(shí)際應(yīng)用問題中,上述約簡(jiǎn)的限制條件過于嚴(yán)格,已有學(xué)者在對(duì)約簡(jiǎn)條件進(jìn)行適當(dāng)放寬的基礎(chǔ)上,提出了ε-約簡(jiǎn)[15],即滿足:

(1)γ(B,D)≥(1-ε)·γ(C,D);

(2) ?B′?B,γ(B′,D) < (1-ε)·γ(C,D).

ε-約簡(jiǎn)旨在保持決策特征D的鄰域依賴度變化在一個(gè)較小的范圍內(nèi)時(shí),盡可能多地消除冗余或無關(guān)的特征,一般而言,ε在0～0.1之間取值．當(dāng)ε=0時(shí),ε-約簡(jiǎn)退化為定義4中的約簡(jiǎn)定義．

1.2 鄰域粗糙特征選擇

在分類學(xué)習(xí)任務(wù)中,特征選擇是一種可以有效地消除冗余和無關(guān)特征的技術(shù)手段．鄰域粗糙集框架下的特征選擇旨在找出和原始條件特征集合具有相同刻畫能力的最小特征子集[16]．

定義5給定一鄰域決策系統(tǒng)NDS=,?B?C,?ai∈C-B,ai的特征重要度可定義為:

Sigout(ai,B,D)=γB∪{ai},D-γ(B,D)

(8)

Sigout(ai,B,D)反映了特征ai加入特征集合B前后，決策特征D的鄰域依賴度的變化程度．基于上述特征重要度的定義,貪心搜索策略可通過迭代，選出鄰域決策系統(tǒng)中最重要的特征子集．

算法1:基于鄰域粗糙集的特征選擇算法

輸入:鄰域決策系統(tǒng),鄰域半徑δ1,允許誤差ε．

輸出:特征子集B．

步驟：

(1)B←?;

(2)?ai∈C,計(jì)算Sigout(ai,B,D),其中γ(?,D)=0;

(3) 選擇特征aj按照:Sigout(aj,B,D)=

max{Sigout(ai,B,D): ?ai∈C};

(4) 當(dāng)γ(B,D) < (1-ε)·γ(C,D)時(shí):

(4.1)B←B∪{aj};

(4.2) ?ai∈C-B,計(jì)算Sigout(ai,B,D);

(4.3) 選擇特征aj按照:Sigout(aj,B,D)=max{Sigout(ai,B,D): ?ai∈C-B};

(5)輸出特征子集B．

算法1通過迭代，將能夠最快速增加鄰域依賴度的特征加入到已選特征集合中,直到所選特征下決策特征D的鄰域依賴度為原始特征集合的100·(1-ε) %時(shí)算法停止．

1.3 鄰域分類器

鄰域分類器在未知樣本的鄰域空間內(nèi),采用多數(shù)投票原則,對(duì)未知樣本的類別進(jìn)行判斷．鄰域分類器在思想上與k近鄰算法類似,其不同之處在于鄰域分類器用鄰域半徑替代了近鄰樣本的個(gè)數(shù),且可以有效地處理離散型和混合型數(shù)據(jù)．

算法2:鄰域分類器

輸入:訓(xùn)練集(特征選擇后) ,未知樣本y,鄰域半徑δ2．

輸出:預(yù)測(cè)的y的類別．

步驟：

(1) ?xi∈U,計(jì)算距離ΔB(xi,y);

(2) 找出y的鄰域δ2內(nèi)的樣本集Uδ2(y);

(3) ?πdi∈U/IND(D),P(πdi,Uδ2(y))=|πdi∩Uδ2(y)|/|Uδ2(y)|;

(4) πdj=arg max{P(πdi,Uδ2(y)): ?πdi∈U/IND(D)};

(5) 輸出y的預(yù)測(cè)類別j．

2 分類學(xué)習(xí)方法

2.1 kd-樹的構(gòu)造與搜索

kd-樹是把二叉搜索樹推廣到多維數(shù)據(jù)的一種主存數(shù)據(jù)結(jié)構(gòu)．kd-樹是一顆二叉樹,可被視作對(duì)k維特征空間的一個(gè)劃分．kd-樹的構(gòu)造相當(dāng)于不斷地采用垂直于坐標(biāo)軸的超平面對(duì)k維特征空間切分的過程,從而形成一系列的k維超矩形區(qū)域．

kd-樹一般按照如下方式構(gòu)造:① 構(gòu)造根結(jié)點(diǎn)，根結(jié)點(diǎn)對(duì)應(yīng)于包含所有樣本的k維特征空間的超矩形區(qū)域;② 通過遞歸，對(duì)k維特征空間切分，在超矩形區(qū)域上選擇某一特定坐標(biāo)軸和特定切分點(diǎn),通過垂直于選定坐標(biāo)軸且經(jīng)過選定切分點(diǎn)的超平面，將當(dāng)前超矩形區(qū)域劃分為左右兩個(gè)子區(qū)域(左子樹和右子樹),該超矩形區(qū)域上的所有樣本被劃分入左右子區(qū)域中．當(dāng)左右子區(qū)域中沒有樣本時(shí),遞歸過程終止．

為了使構(gòu)造的kd-樹平衡,通常將各個(gè)維特征依次作為選定的坐標(biāo)軸,切分點(diǎn)采用所有樣本在選定坐標(biāo)軸上的中位數(shù)．

算法3:平衡kd-樹的構(gòu)造算法

輸入:訓(xùn)練數(shù)據(jù)集U={x1,x2,…,xn},其中xi=[dim1(xi), dim2(xi),…, dimk(xi)]．

輸出:平衡kd-樹．

步驟：

(1) 選擇dim1為坐標(biāo)軸,以U中所有樣本的dim1坐標(biāo)的中位數(shù)為切分點(diǎn),將根結(jié)點(diǎn)對(duì)應(yīng)的超矩形區(qū)域切分成左右兩個(gè)子區(qū)域,即用根結(jié)點(diǎn)生成深度為1的左右子結(jié)點(diǎn),其中左子結(jié)點(diǎn)對(duì)應(yīng)坐標(biāo)dim1小于切分點(diǎn)的子區(qū)域,右子結(jié)點(diǎn)對(duì)應(yīng)坐標(biāo)dim1大于切分點(diǎn)的子區(qū)域;

(2) 對(duì)于深度為j的結(jié)點(diǎn),選擇dimj(mod k)+1為切分的坐標(biāo)軸,以該結(jié)點(diǎn)區(qū)域中所有樣本的dimj(mod k)+1坐標(biāo)的中位數(shù)為切分點(diǎn),將該結(jié)點(diǎn)對(duì)應(yīng)的超矩形區(qū)域切分成左右兩個(gè)子區(qū)域,即用該結(jié)點(diǎn)生成深度為j+1的左右子結(jié)點(diǎn),其中左子結(jié)點(diǎn)對(duì)應(yīng)坐標(biāo)dimj(mod k)+1小于切分點(diǎn)的子區(qū)域,右子結(jié)點(diǎn)對(duì)應(yīng)坐標(biāo)dimj(mod k)+1大于切分點(diǎn)的子區(qū)域;

(3) 返回步驟(2),直到左右兩個(gè)子區(qū)域沒有樣本;

(4) 輸出平衡kd-樹．

采用kd-樹進(jìn)行鄰域搜索,可以省去對(duì)大部分樣本點(diǎn)的查找,從而減少搜索的計(jì)算量．算法4給出了kd-樹下鄰域搜索的具體方法．

算法4:kd-樹下的鄰域搜索算法

輸入:已構(gòu)造的kd-樹,目標(biāo)樣本x,鄰域半徑δ．

輸出:x的鄰域樣本．

步驟：

(1) 從kd-樹的根結(jié)點(diǎn)出發(fā),通過遞歸，向下訪問kd-樹,如果目標(biāo)樣本x當(dāng)前維度的坐標(biāo)小于切分點(diǎn)坐標(biāo),那么移動(dòng)到左子結(jié)點(diǎn),否則移動(dòng)到右子結(jié)點(diǎn),最終到達(dá)的葉結(jié)點(diǎn)即為包含x的葉節(jié)點(diǎn),如果該葉結(jié)點(diǎn)上的樣本到x的距離≤δ,則將該樣本加入到x的鄰域樣本中;

(2)通過遞歸，向上退回,在每個(gè)結(jié)點(diǎn)進(jìn)行操作:

(2.1) 如果該結(jié)點(diǎn)上的樣本到x的距離≤δ,則將該樣本加入到x的鄰域樣本中;

(2.2) 目標(biāo)x的鄰域樣本一定存在于該結(jié)點(diǎn)一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域．檢查該子結(jié)點(diǎn)的父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)區(qū)域的樣本．檢查另一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域是否與以目標(biāo)x為球心,以δ為半徑的超球體相交．如果相交,可能在另一個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)域中存在與x的距離≤δ的點(diǎn),移動(dòng)到另一個(gè)子結(jié)點(diǎn),通過遞歸進(jìn)行鄰域搜索;否則,向上退回．

(3) 當(dāng)退回到根結(jié)點(diǎn)時(shí),搜索結(jié)束;

(4) 輸出x的鄰域樣本．

2.2 kd-樹下快速鄰域分類方法

文中提出的基于kd-樹的快速鄰域分類方法kdtree-NC仍采用特征選擇和鄰域分類兩個(gè)階段,與傳統(tǒng)的鄰域分類方法NC不同的是,kdtree-NC在鄰域信息粒化的過程中,借助可用以實(shí)施快速鄰域搜索的kd-樹這一樹形數(shù)據(jù)結(jié)構(gòu),代替了NC方法中基于線性掃描的鄰域搜索方式,在很大程度上減少了需要查找的樣本點(diǎn),從而降低了鄰域信息?；械乃阉饔?jì)算量．

在算法1中,步驟(2)和步驟(4.2)都通過循環(huán)體迭代，尋找能夠最快速增加鄰域依賴度的特征,而鄰域依賴度刻畫了當(dāng)前特征集合所誘導(dǎo)的?；臻g對(duì)各決策類的近似逼近能力,因此,算法1的時(shí)間開銷主要集中在大量的鄰域信息粒化上．在NC方法中,線性遍歷的鄰域搜索方式的時(shí)間復(fù)雜度為O(n),而采用kd-樹方式進(jìn)行鄰域搜索的平均時(shí)間復(fù)雜度為O(logn),一般而言,當(dāng)樣本數(shù)量遠(yuǎn)大于特征空間的維度時(shí),kd-樹方式進(jìn)行的鄰域搜索較線性遍歷方式更為高效．同樣,在鄰域分類器算法(算法2)的步驟1中,也將先采用算法3來構(gòu)造一棵左右平衡的kd-樹,再借助基于kd-樹的鄰域搜索算法(算法4)以提高鄰域決策的時(shí)間效率．

3 性能分析

為了驗(yàn)證基于kd-樹的鄰域分類方法的有效性,文中選取了18組UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析,數(shù)據(jù)集的基本信息如表1．文中實(shí)驗(yàn)選用配備2.7GHz處理器、4GB內(nèi)存的PC機(jī),編程環(huán)境為Matlab 2016b．實(shí)驗(yàn)分為兩個(gè)部分：① 對(duì)NC和kdtree-NC特征選擇階段的時(shí)間消耗進(jìn)行對(duì)比;② 分別比較了特征選擇前后分類的準(zhǔn)確率和特征選擇后NC和kdtree-NC方法的分類的時(shí)間消耗．

表1 數(shù)據(jù)集基本信息

圖1、2分別展示了鄰域半徑為0.05和0.10時(shí),NC與kdtree-NC中特征選擇的時(shí)間消耗,其中黑柱代表NC的時(shí)間,白柱代表kdtree-NC的時(shí)間．由圖1、2不難發(fā)現(xiàn),在絕大多數(shù)數(shù)據(jù)集上,kdtree-NC中特征選擇的時(shí)間消耗要明顯小于NC,僅在Connectionist Bench和Glass Identification數(shù)據(jù)集上,kdtree-NC特征選擇所耗費(fèi)的時(shí)間要略高于NC,其原因在于這兩個(gè)數(shù)據(jù)集中的樣本數(shù)與特征數(shù)不滿足kd-樹快速搜索策略中樣本數(shù)應(yīng)遠(yuǎn)大于特征數(shù)這一先決條件．

圖1 NC與kdtree_NC特征選擇的時(shí)間對(duì)比(特征選擇鄰域半徑為0.05)Fig.1 Comparision of elapsed time between NC andkdtree_NC based teature selection(neighbor radius is 0.05)

由表1和圖1、2可知，隨著數(shù)據(jù)集中樣本數(shù)與特征數(shù)之比的增大,NC與kdtree-NC中特征選擇的時(shí)間消耗差距也愈發(fā)顯著．

圖2 NC與kdtree_NC特征選擇的時(shí)間對(duì)比(特征選擇鄰域半徑為0.10)Fig.2 Comparision of elapsed time between NC andkdtree_NC based teature selection(neighbor radius is 0.10)

圖3、4分別為特征選擇鄰域半徑為0.05和0.10時(shí),對(duì)NC與kdtree-NC的分類性能進(jìn)行對(duì)比．在鄰域分類階段,在30個(gè)鄰域半徑(0.01～0.30,間隔為0.01)下,文中比較了NC與kdtree-NC的分類時(shí)間消耗．在每個(gè)鄰域半徑點(diǎn),實(shí)驗(yàn)采用了10折交叉驗(yàn)證的方式，分類過程重復(fù)10次并記錄整個(gè)10次分類的總時(shí)間．交叉驗(yàn)證中共有10組測(cè)試樣本集,為此,kdtree-NC方法在分類過程中共需根據(jù)對(duì)應(yīng)的10組訓(xùn)練樣本集來構(gòu)建10棵kd-樹用于鄰域搜索．由圖3、4不難發(fā)現(xiàn),在絕大多數(shù)數(shù)據(jù)集的各個(gè)鄰域半徑點(diǎn)上,kdtree-NC的分類時(shí)間要遠(yuǎn)遠(yuǎn)小于NC的分類時(shí)間,這驗(yàn)證了文中提出的kdtree-NC，通過采用kd-樹型快速鄰域搜索策略,確實(shí)能夠較大程度地縮小鄰域搜索范圍,從而有效地提升鄰域分類的時(shí)間效率．

對(duì)kdtree-NC在鄰域特征選擇前后的分類精度進(jìn)行了對(duì)比，由圖3、4可見，在大部分?jǐn)?shù)據(jù)集上,特征選擇后的鄰域分類精度要高于特征選擇前,這說明算法1可以有效刪除原始特征空間中的冗余信息,進(jìn)而提高鄰域分類準(zhǔn)確度．

圖3 NC與kdtree_NC分類性能的對(duì)比(特征選擇鄰域半徑為0.05)Fig.3 Comparision of classification performances between NC and kdtree_NC(neigbbor radius is 0.05)

圖4 NC與kdtree_NC分類性能的對(duì)比(特征選擇鄰域半徑為0.10)Fig.4 Comparision of classification performances between NC and kdtree_NC(neigbbor radius is 0.10)

4 結(jié)論

(1) 文中通過kd-樹型鄰域搜索策略,提出了一種基于kd-樹的快速鄰域分類方法kdtree-NC,該方法在鄰域信息粒化過程中采用了kd-樹搜索策略代替了傳統(tǒng)鄰域分類方法中的線性遍歷搜索,有效地降低了鄰域搜索的時(shí)間開銷．

(2) 在18組UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)的鄰域分類方法相比,kdtree-NC在特征選擇和鄰域分類階段的時(shí)間效率都有顯著提升．

(3) 在下一步的研究工作中,筆者計(jì)劃將ball-樹搜索結(jié)構(gòu)引入到鄰域分類方法中,以解決kdtree-NC在處理高維特征數(shù)據(jù)時(shí)效率急劇降低的不足．