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

張清華, 艾志華, 張金鎮

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

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

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

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

1 基礎知識

1.1 決策系統

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

S=(U,A,D)。

(1)

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

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

表1 決策系統

1.2 鄰域覆蓋模型

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

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

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

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

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

定義4[17,19]設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就是相對不可約簡的。

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

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

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

2.1 鄰域覆蓋的構建

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

(2)

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

(3)

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

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

例1在表1中，論域U={x1,x2,…,x13}，將論域U切分為訓練樣本集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)均能刻畫出數據分布，對模型的訓練沒有影響，且對最后的分類效果影響較小。因此，約簡后得到最終的鄰域集合Or={O(x2),O(x7),O(x10)}如圖2所示。

表2 訓練樣本的半徑及鄰域

圖1 初始鄰域覆蓋

圖2 約簡后的鄰域覆蓋

2.2 基于密度的分類策略

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

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

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

(4)

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

(5)

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

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

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

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

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

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

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

(6)

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

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

假設測試樣本s為鄰域集合Or上的外部點，由于外部點s不處于任何一個鄰域，沒有分類規則進行分配，因此需要計算所有鄰域中心和外部點s的加權距離，最后選擇離外部點s加權距離最小的一個鄰域對其分類。即

(7)

樣本分類策略2針對內部點進行分類。

(8)

(9)

最后,選擇加權距離最小的鄰域對樣本s分類，即

(10)

2.3 算法設計

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

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

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

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

初始化O*←?。

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

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

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

else/*測試樣本s為內部點*/。

O*←O(xi)。

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

end if。

end if。

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

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

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

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

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

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

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

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

3 實驗分析

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

表3 實驗數據集

3.1 評估指標

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

(11)

(12)

(13)

(14)

3.2 實驗結果與分析

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

3.2.1 D-NCR與NCR、TNCR對比

為了體現本文D-NCR的優勢，分別與TNCR和NCR進行對比。在10個數據下4種指標的實驗結果如表4所示。

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

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

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

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

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

為了進一步體現本文D-NCR的優勢，分別與NEC、CART、NB、KNN分類器進行對比，在10個數據下4種指標的實驗結果如表5～8所示。

表5 不同算法的準確率

表6 不同算法的精確率

表7 不同算法的召回率

表8 不同算法的F1

NEC的核心參數是δ，Hu等通過

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

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

4 結語

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