融合密度與鄰域覆蓋約簡的分類方法

張清華, 艾志華, 張金鎮(zhèn)

(重慶郵電大學(xué) 計算智能重慶市重點實驗室， 重慶 400065)

粗糙集是由Pawlak教授于1982年提出的一種處理不精確、不一致、不完全信息和知識的重要數(shù)學(xué)工具[1]，已經(jīng)被廣泛應(yīng)用于機器學(xué)習(xí)、知識發(fā)現(xiàn)、數(shù)據(jù)挖掘、決策支持與分析等[2-3]。但是Pawlak粗糙集只適用于處理離散型數(shù)據(jù)，對于實際應(yīng)用中普遍存在的數(shù)值型或混合型數(shù)據(jù)，需要將其離散化，從而不可避免地帶來了信息損失[4]，從而影響分類效果。為解決這一問題，Pawlak粗糙集被擴展到鄰域粗糙集[5]和模糊粗糙集[6-7]。實際上，鄰域粗糙集提供了一種構(gòu)造數(shù)據(jù)空間的近似方法[8]。從拓撲學(xué)的角度，證明了鄰域空間比數(shù)據(jù)空間的概念更一般化[9]，這表明將原始數(shù)據(jù)空間轉(zhuǎn)化為鄰域空間有助于數(shù)據(jù)的泛化[10]，因此鄰域粗糙集模型被廣泛應(yīng)用于分類學(xué)習(xí)[11-12]與特征選擇[13-15]中。為了構(gòu)造鄰域空間，可以通過鄰域粗糙集構(gòu)造鄰域覆蓋，在鄰域覆蓋中，每個鄰域中的樣本都是同種類別的，因此鄰域覆蓋提供了一個從鄰域?qū)哟稳ケ硎緮?shù)據(jù)分布[16]的方法。并且，為了更精確地表示數(shù)據(jù)分布，鄰域覆蓋約簡算法通過集合包含關(guān)系剔除冗余的鄰域[17]。

由于鄰域中所有樣本都是同種類別的，所以每個鄰域都對應(yīng)一個分類規(guī)則。因此，文獻[17]提出了基于鄰域覆蓋約簡的規(guī)則學(xué)習(xí)方法(NCR)，該方法通過鄰域覆蓋約簡過濾掉冗余的鄰域得到分類規(guī)則，進而根據(jù)離測試樣本最近的鄰域來匹配規(guī)則對測試樣本分類。由于NCR方法簡單、有效，被廣泛應(yīng)用于數(shù)據(jù)分類中，但該方法對鄰域的約簡過于嚴格，易受到噪聲樣本影響，從而在覆蓋中仍然存在一些冗余的鄰域，對規(guī)則提取帶來較高的復(fù)雜度。另外，僅靠距離最近的鄰域?qū)y試樣本分類可能會導(dǎo)致分類錯誤。針對上述問題，文獻[18]基于三分法，通過控制鄰域半徑大小將鄰域擴展到內(nèi)鄰域和外鄰域，減少了在形成鄰域時噪聲樣本的影響；文獻[19]將鄰域覆蓋擴展到模糊鄰域覆蓋，提出了基于模糊鄰域覆蓋的三支決策分類方法；文獻[20]基于行列式點過程，提出了一個新的鄰域覆蓋約簡方法，有效地約簡了冗余的鄰域，能在更少的鄰域下形成數(shù)據(jù)空間下的覆蓋；文獻[21]通過樣本間的相似度構(gòu)建鄰域，然后采用鄰域覆蓋約簡得到代表樣本，進而通過代表樣本對測試樣本分類；文獻[22]結(jié)合陰影集構(gòu)造了陰影鄰域，并提出了三支決策分類規(guī)則，有效地降低了不確定樣本的分類風(fēng)險；另外，文獻[23]通過隨機化屬性約簡，得到多組屬性集合，在不同組的屬性集合上采用鄰域覆蓋約簡的方法學(xué)習(xí)分類規(guī)則，有效地提高了分類精度。

然而，現(xiàn)有大部分基于鄰域覆蓋的分類方法直接根據(jù)最近的鄰域?qū)y試樣本進行分類，由于不同樣本形成的鄰域是不同的，且噪聲樣本形成的鄰域中對象較少且離中心點較遠，那么此類樣本形成的鄰域分類能力更弱。因此，僅通過最近的鄰域?qū)颖痉诸?，忽略了鄰域中其他樣本的信息，沒有考慮到鄰域間的差異，容易受到噪聲樣本的影響。本文首先通過鄰域中心和鄰域中其他樣本的距離計算出鄰域中心的局部密度[24-25]，用其代表整個鄰域的局部密度，去刻畫鄰域之間的差異性。并且，鄰域中的樣本越多、越緊密，鄰域的密度就越大，那么此種鄰域的分類能力越強。然后將鄰域中心的局部密度轉(zhuǎn)化為權(quán)重，定義了測試樣本到鄰域中心的加權(quán)距離，并對處于不同位置的測試樣本分別定義了內(nèi)部樣本點和外部樣本點。最后基于加權(quán)距離，對兩類點采用了不同的分類策略。實驗結(jié)果驗證了本文方法的優(yōu)勢及有效性。

1 基礎(chǔ)知識

1.1 決策系統(tǒng)

定義1[21,26]決策系統(tǒng)可以表示為一個三元組

S=(U,A,D)。

(1)

式中：U是一個有限非空的樣本集合，稱為論域；A和D分別是有限非空的條件屬性集合和決策屬性集合。

一般地，一個簡單的決策系統(tǒng)如表1所示，其中U={x1,x2,…,x13},A={a1,a2},D=j5i0abt0b。在分類任務(wù)中，常常把論域切分成訓(xùn)練樣本集Utrain和測試樣本集Utest。

表1 決策系統(tǒng)

1.2 鄰域覆蓋模型

鄰域覆蓋是同類鄰域的集合，從而為數(shù)據(jù)分布提供了一個集合水平上的近似[27-28]。由于鄰域覆蓋模型非參數(shù)的特性和對復(fù)雜數(shù)據(jù)的魯棒性，鄰域覆蓋模型已經(jīng)被廣泛應(yīng)用于數(shù)據(jù)挖掘任務(wù)中，如分類[17-23]、特征選擇[29-31]等。鄰域覆蓋的定義如下。

定義2[17,19]設(shè)U={x1,x2,…,xn}是一個論域，且O(xi)={y∈U|Δ(xi,y)≤r(xi)}表示樣本xi的鄰域，其中Δ(·)是一個距離函數(shù)，r(xi)表示樣本xi的半徑。則鄰域集合O={O(xi)|xi∈U}形成了論域U上的一個覆蓋，且C=〈U,O〉表示鄰域覆蓋近似空間。

顯然，在鄰域覆蓋中，可能存在一些鄰域是相互重疊的，因此在維持數(shù)據(jù)空間結(jié)構(gòu)的過程中，某些重疊的鄰域可以進一步被約簡。鄰域覆蓋約簡使得提取的數(shù)據(jù)空間結(jié)構(gòu)具有更小的數(shù)據(jù)冗余性。給出鄰域覆蓋約簡的定義如下。

定義3[17,19]設(shè)C=〈U,O〉是一個鄰域覆蓋近似空間，如果?xi∈U,有∪y∈U-{xi}O(y)=U,那么O(xi)就是可約簡的，否則就是不可約簡的。如果在C中的所有鄰域都是不可約簡的，那么C就是不可約簡的。

為了進一步近似同類樣本的數(shù)據(jù)分布，相對鄰域覆蓋約簡的定義如下。

定義4[17,19]設(shè)C=〈U,O〉是一個鄰域覆蓋近似空間，X?U是一個樣本集合且O(xi)∈O是一個鄰域，如果?O(xj)∈O且i≠j，使得O(xi)?O(xj)?X，那么O(xi)就是對于X相對可約簡的鄰域，否則O(xi)就是相對不可約簡的。如果在C中的所有鄰域都是相對不可約簡的，那么C就是相對不可約簡的。

對于同一類數(shù)據(jù)，通過相對鄰域覆蓋約簡，可以得到該類數(shù)據(jù)分布的近似，進而得到整個數(shù)據(jù)的近似分布，從而可用于數(shù)據(jù)分類任務(wù)中。

2 一種融合密度與鄰域覆蓋約簡的分類方法

本節(jié)首先詳細地介紹鄰域覆蓋的構(gòu)建及鄰域覆蓋約簡算法，然后給出基于密度的兩種分類策略，最后提出融合密度與鄰域覆蓋約簡的分類方法。

2.1 鄰域覆蓋的構(gòu)建

鄰域通過樣本之間的距離或者相似度來構(gòu)建。常用的距離公式有歐式距離、閔可夫斯距離等；常用的相似度公式有余弦相似度、Jaccard相似系數(shù)等。但是，對于實際場景普遍存在的數(shù)值型屬性和名義型屬性的混合屬性數(shù)據(jù)，本文采取混合歐式距離重疊度量[32](HEOM)去衡量樣本間的距離，HEOM距離函數(shù)利用重疊法針對數(shù)值型和名義型數(shù)據(jù)進行度量，還可以為歐式距離計算后的數(shù)據(jù)樣本進行歸一化處理。因此，?x,y∈U，在m個屬性下HEOM距離函數(shù)定義為

(2)

式中:dai(x,y)表示在屬性ai下樣本x和y的距離。dai(x,y)的距離定義為

(3)

因此，對于一個樣本集合U={x1,x2,…,xn}，可以通過樣本間的HEOM距離構(gòu)建鄰域。給定樣本xi∈U，鄰域O(xi)={y∈U|Δ(xi,y)≤r(xi)}由鄰域中心xi附近的樣本組成，Δ(·)是HEOM距離函數(shù)，r(xi)表示樣本xi的鄰域半徑。為了保證鄰域中樣本都是同種類別，樣本xi的鄰域半徑r(xi)與它最近的同類和異類樣本有關(guān)[17,19]。設(shè)NH(xi)是樣本xi最近的同類樣本(如果某類只有一個樣本，則NH(xi)=xi)，NM(xi)為樣本xi最近的異類樣本,則樣本xi的鄰域半徑r(xi)=Δ(xi,NM(xi))-c×Δ(xi,NH(xi))，其中c是一個常數(shù)，控制鄰域半徑大小，在實驗中c=0.01。顯然，由xi形成的鄰域中所有樣本是和xi同類別的。

對于一個樣本集合U={x1,x2,…,xn}，鄰域集合O={O(xi)|xi∈U}形成了論域U上的一個覆蓋。由于鄰域覆蓋中可能包含冗余的鄰域，從而對分類規(guī)則提取造成很高的復(fù)雜度。因此,根據(jù)定義2和3，通過鄰域覆蓋約簡[17]，約簡冗余的鄰域。鄰域覆蓋約簡算法從一個空集開始，采用前向搜索策略，每次添加一個鄰域。在每一步迭代中選擇覆蓋樣本最多的鄰域，而被當前覆蓋樣本最多的鄰域所包含的鄰域會被約簡，依次迭代，直到初始鄰域覆蓋為空。從而得到約簡后的前h個的鄰域集合Or={O(x1),O(x2),…,O(xh)}[17]。

例1在表1中，論域U={x1,x2,…,x13}，將論域U切分為訓(xùn)練樣本集Utrain={x1,x2,…,x10}和測試樣本集Utest={x11,x12,x13}。因此,可以計算出每個測試樣本的鄰域半徑以及形成的鄰域(如表2所示)，得到初始鄰域覆蓋如圖1所示，進而通過鄰域覆蓋約簡算法[17]對冗余的鄰域進行約簡，由于鄰域O(x2)、O(x4)和O(x6)中均覆蓋6個樣本，因此在約簡中隨機選取鄰域O(x2)作為最終約簡后的鄰域。鄰域O(x2)、O(x4)和O(x6)均能刻畫出數(shù)據(jù)分布，對模型的訓(xùn)練沒有影響，且對最后的分類效果影響較小。因此，約簡后得到最終的鄰域集合Or={O(x2),O(x7),O(x10)}如圖2所示。

表2 訓(xùn)練樣本的半徑及鄰域

圖1 初始鄰域覆蓋

圖2 約簡后的鄰域覆蓋

2.2 基于密度的分類策略

在鄰域覆蓋中，由于鄰域中的樣本都是同類的，因此每一個鄰域都對應(yīng)一個分類規(guī)則。在NCR[17]分類時，將測試樣本分類給最近鄰域所在的類，這樣僅考慮了鄰域中心的信息，鄰域中其他樣本的信息被忽略，這種分類方式很容易受到噪聲樣本的影響，而造成分類錯誤。因此，本文引入了局部密度，通過局部密度刻畫鄰域中其他樣本的信息，再將鄰域中心的局部密度轉(zhuǎn)化為權(quán)重，定義了測試樣本和鄰域中心之間的加權(quán)距離，最后對不同情況下的測試樣本提出2種分類策略。

為了刻畫鄰域之間的差異性，受到文獻[24]中密度峰值思想的啟發(fā)，即通過樣本周圍的樣本數(shù)量，以及相互之間的距離來描述樣本的重要性，本文借助此思想計算鄰域中心(樣本)的重要性來刻畫鄰域間的差異。但與文獻[24]定義不同的是，本文的樣本半徑是自適應(yīng)變化的，并不需要人為設(shè)定。因此，給出局部密度的定義如下。

定義5給定約簡后鄰域集合Or,?O(xi)∈Or，則鄰域中心xi的局部密度為

(4)

且歸一化后xi的局部密度為

(5)

式中:r(xi)為樣本xi的鄰域半徑。

從公式(4)、(5)可以看出，鄰域中的樣本越多，樣本離鄰域中心越近，那么該鄰域中心的局部密度就越大。值得注意的是，當鄰域中沒有其他樣本時，則該鄰域中心的局部密度為0，一般這類鄰域是由噪聲樣本所形成的鄰域。

對于一個測試樣本，可以分為3種情況:1)處于一個鄰域之中；2)處于多個鄰域之中；3)不處于任意鄰域之中。

因為在鄰域集合Or中每個鄰域都對應(yīng)著一個分類規(guī)則，所以對于前2種情況都有相應(yīng)的分類規(guī)則與之匹配，而第3種情況沒有對應(yīng)的分類規(guī)則匹配。因此，針對不同情況下的測試樣本，本文采取了不同的分類策略。為了方便敘述，本文分別定義了外部樣本點和內(nèi)部樣本點。

定義6給定一個測試樣本s和約簡后鄰域集合Or，如果?O(xi)∈Or，使得Δ(s,xi)>r(xi)，則稱測試樣本s為鄰域集合Or上的外部樣本點，簡記為外部點。

定義7給定一個測試樣本s和約簡后鄰域集合Or，如果?O(xi)∈Or，使得Δ(s,xi)≤r(xi)，則稱測試樣本s為鄰域集合Or上的內(nèi)部樣本點，簡記為內(nèi)部點。

定義8給定一個測試樣本s和約簡后鄰域集合Or，那么樣本s和?O(xi)∈Or的加權(quán)距離為

(6)

基于加權(quán)距離，分別對內(nèi)部點和外部點采取不同的分類策略，分類策略詳細描述如下所示。

樣本分類策略1針對外部點進行分類。

假設(shè)測試樣本s為鄰域集合Or上的外部點，由于外部點s不處于任何一個鄰域，沒有分類規(guī)則進行分配，因此需要計算所有鄰域中心和外部點s的加權(quán)距離，最后選擇離外部點s加權(quán)距離最小的一個鄰域?qū)ζ浞诸?。?/p>

(7)

樣本分類策略2針對內(nèi)部點進行分類。

(8)

(9)

最后,選擇加權(quán)距離最小的鄰域?qū)颖緎分類，即

(10)

2.3 算法設(shè)計

基于前文中的樣本分類策略，本文D-NCR如算法1所示。

算法1 融合密度與鄰域覆蓋約簡的分類方法

輸入：鄰域集合Or，測試樣本s。

輸出：測試樣本s的類別。

初始化O*←?。

根據(jù)公式(4)計算Or中鄰域中心的局部密度。

通過公式(5)對Or中所有鄰域的密度進行歸一化。

通過公式(6)計算出離樣本s最近的鄰域

else/*測試樣本s為內(nèi)部點*/。

O*←O(xi)。

通過公式(9)計算出離樣本s最近的鄰域

end if。

end if。

將鄰域O*的類標簽分配給測試樣本s。

例2(續(xù)例1)由例1得出的鄰域集合Or={O(x2),O(x7),O(x10)}和測試樣本集合Utest={x11,x12,x13}形成的圖像如圖3所示。根據(jù)算法1，通過Or對測試樣本集Utest={x11,x12,x13}中的樣本分類，分類步驟如下。

圖3 測試樣本和鄰域集合Or

步驟一計算測試樣本和所有鄰域中心的距離。

步驟二計算Or中所有鄰域中心的局部密度。

ρx2≈3.074,ρx7≈1.301,ρx10≈0.987。

步驟三對測試樣本進行分類。

對于x13,由于x13只存在于O(x7)中，即x13是內(nèi)部點且只存在于單個鄰域中，因此將O(x7)的類標簽(Iris-virginica)分配給x13。

3 實驗分析

為了進一步闡述本文D-NCR的優(yōu)勢，分別在UCI的10個數(shù)據(jù)集進行實驗，數(shù)據(jù)集詳細信息如表3所示。對比算法有NCR[17]、TNCR[18]、鄰域分類器[12](NEC)、K近鄰(KNN)、樸素貝葉斯(NB)和決策樹(CART)。實驗采用10折交叉驗證，實驗環(huán)境為Windows 10操作系統(tǒng)，16 GiB內(nèi)存，3.60 GiHz主頻，編程語言采用Python。

表3 實驗數(shù)據(jù)集

3.1 評估指標

為了直觀地展示實驗結(jié)果，本文采用的評價指標有準確率(A)、精確率(PC)、召回率(R)和F1值[33-34]。給定一個數(shù)據(jù)樣本集合，設(shè)P表示正例的個數(shù)，N表示負例的個數(shù)，TP表示正確地預(yù)測為正例的個數(shù)，F(xiàn)P表示錯誤地預(yù)測為正例的個數(shù)，TN表示正確地預(yù)測為負例的個數(shù)，F(xiàn)N表示錯誤的預(yù)測為負例的個數(shù)，那么

(11)

(12)

(13)

(14)

3.2 實驗結(jié)果與分析

分兩部分進行對比分析，第一部分為D-NCR、TNCR[18]、NCR[17]進行對比，第二部分為D-NCR和其他分類算法進行對比。每個數(shù)據(jù)集下評價指標的最優(yōu)結(jié)果用加粗表示。

3.2.1 D-NCR與NCR、TNCR對比

為了體現(xiàn)本文D-NCR的優(yōu)勢，分別與TNCR和NCR進行對比。在10個數(shù)據(jù)下4種指標的實驗結(jié)果如表4所示。

表4 D-NCR、TNCR和NCR在4種指標下的分類結(jié)果

相較于NCR，本文D-NCR通過局部密度刻畫鄰域之間的差異性，能更好地利用樣本信息進行分類。TNCR盡管能通過異質(zhì)率減少受到噪聲點的影響，但是TNCR中的完全三分鄰域覆蓋約簡中的約簡規(guī)則較嚴格，導(dǎo)致約簡后鄰域集合中的鄰域仍然有較多重疊，使得模型的復(fù)雜度提高，影響最后模型的分類效果。且由表4可以發(fā)現(xiàn)，相較于NCR，D-NCR在4個指標下在Credit數(shù)據(jù)集分類效果與NCR基本一致，在其他9個數(shù)據(jù)集上均有相應(yīng)幅度的提升。在Credit數(shù)據(jù)集上，約簡后鄰域中心的局部密度大部分相差不大，從而鄰域的權(quán)重也幾乎一致，導(dǎo)致分類效果和NCR基本一致。在平均指標下，D-NCR在10個數(shù)據(jù)集下分別較NCR提升1.82%、0.81%、2.02%、1.87%。相較于TNCR，D-NCR能在大多數(shù)數(shù)據(jù)集下達到最優(yōu)的效果，且在平均指標下，D-NCR在10個數(shù)據(jù)集下分別較NCR提升1.33%、0.49%、2.49%、2.52%。

在時間復(fù)雜度上，相較于NCR，D-NCR需要花費一定時間計算約簡后所有鄰域中心的局部密度，從而得出測試樣本到鄰域中心的加權(quán)距離，但時間復(fù)雜度和NCR一致，均為O(n2)。

綜上，相比于NCR，本文提出的D-NCR在時間復(fù)雜度不變的情況下有更好的分類效果。

3.2.2 D-NCR與其他分類算法對比

為了進一步體現(xiàn)本文D-NCR的優(yōu)勢，分別與NEC、CART、NB、KNN分類器進行對比，在10個數(shù)據(jù)下4種指標的實驗結(jié)果如表5～8所示。

表5 不同算法的準確率

表6 不同算法的精確率

表7 不同算法的召回率

表8 不同算法的F1

NEC的核心參數(shù)是δ，Hu等通過

δ=min(Δ(xi,s))+ω·range(Δ(xi,s)),ω≤1

來控制鄰域的半徑，且得出ω=0.1左右時達到較好的分類效果[12]，因此本實驗中NEC的ω值取0.1，KNN中K取10。相較于KNN，由于NEC分類器能夠隨數(shù)據(jù)分布的變化來動態(tài)變化半徑值，因此在實驗結(jié)果上有略微的提升。雖然D-NCR、NEC、KNN能實現(xiàn)更好的分類結(jié)果，但是NEC、KNN在不同分布下的數(shù)據(jù)容易受到參數(shù)的影響。由于在D-NCR中可以通過多個鄰域去表示數(shù)據(jù)分布，因此相較于CART、NB、KNN和NEC，D-NCR在Iris、Heart、Wdbc、Segmentatio、Breast-w、Diabetes 6個數(shù)據(jù)集上能達到最優(yōu)的效果，在其他數(shù)據(jù)集上也能有次優(yōu)的效果，且在10個數(shù)據(jù)集上平均分類精度、準確率、召回率和F1，D-NCR都能達到最優(yōu)的分類效果。實驗數(shù)據(jù)表明，本文提出的D-NCR優(yōu)于其他一些分類算法。

4 結(jié)語

NCR直接根據(jù)最近的鄰域?qū)y樣樣本進行分類，未考慮鄰域之間的差異，容易受到噪聲樣本形成鄰域的影響，從而造成分類錯誤。針對此問題，本文提出了融合密度與鄰域覆蓋約簡的分類方法D-NCR。由于噪聲樣本形成的鄰域中樣本少且離鄰域中心遠，此類樣本形成的鄰域的分類能力更弱，因此通過局部密度刻畫鄰域中樣本的信息，并將局部密度轉(zhuǎn)化為權(quán)重，得到測試樣本和鄰域中心之間的加權(quán)距離，通過加權(quán)距離，不僅考慮了測試樣本到鄰域中心的距離，而且考慮了鄰域之間密度的差異性，充分利用了鄰域中其他樣本的信息。并基于加權(quán)距離，對不同的測試樣本提出2種分類策略。在UCI數(shù)據(jù)集上的實驗結(jié)果表明了本文方法的有效性。在大數(shù)據(jù)場景下，研究更加高效的算法是未來的研究重點。