基于鄰域決策的序貫三支分類方法

亓 慧 魏 巍 王文劍,3

1(太原師范學院計算機系 山西 晉中 030619)2(山西大學計算機與信息技術學院 山西 太原 030006)3(山西大學計算智能與中文信息處理教育部重點實驗室 山西 太原 030006)

0 引 言

三支決策理論的原生模型為粗糙集和決策粗糙集，該理論的衍生與拓展實則為粗糙集理論中三個區(qū)域提供了恰當?shù)恼Z義解釋[1-2]。其核心思想是將一個統(tǒng)一集劃分為三個互不相交的不同區(qū)域，進而對每一個區(qū)域采取相應的決策策略[3]。例如，在粗糙集理論研究中，通過下近似集合與上近似集合的定義，論域可被劃分為正域、負域、邊界域。作為傳統(tǒng)二支決策理論的一種重要推廣，三支決策理論給決策者分別分配接受、拒絕、不承諾決策。而在面向實際問題的決策過程中，人們最初面對的信息往往是不確定的，不足以完成確切的決策，而是需要另外一個待定漸進的過程來進行新的有效信息的補給。因此，在真實環(huán)境中，伴隨著信息的迭代補充，決策過程以及決策結果也應更新與遞進。事實上，我們就將這種從粗粒度到細粒度的決策過程稱之為序貫決策方法[4]。

在原有三支決策研究成果的基礎上，Yao等[4-5]于2003年開創(chuàng)性地構建了序貫三支決策的研究理念，并進一步地給出了一種具體的序貫三支決策算法。在此思想的引導下，眾多研究工作者從不同方面針對序貫三支決策思想開展了大量的工作。Li等[6-7]提出了代價敏感的序貫三支決策方法；Qian等[8-9]在動態(tài)粒度方法下研究了基于序貫三支決策的屬性約簡方法；Li等[10-12]探索了圖像等非結構化數(shù)據(jù)中的序貫三支決策模型，用以平衡決策過程中的決策代價和時間代價，并將序貫三支決策與自編碼網絡相結合，尋找總代價最低的合適粒度。Yang等[13-16]系統(tǒng)研究了概率粗糙集下序貫三支決策的框架；Yang等[17]基于粗糙集方法研究了代價敏感序貫三支決策的最優(yōu)粒度選擇問題。此外，三支決策和序貫三支決策在分類問題中也發(fā)揮著獨特的作用。Zhang等[18]研究了基于分類錯誤的三支決策模型；Yao等[19]提出了三支決策分類的基本框架；Yue等[20]基于模糊覆蓋粗糙集構建三支分類技術。在序貫三支分類的研究過程中，如何界定屬性集序列是序貫分類的重要問題之一。在已有的研究成果中，大多建立在前向式框架上，即以第一個屬性為起始序列，以全部屬性集為終止序列[13]。然而，在高維數(shù)據(jù)背景下，數(shù)據(jù)中存在大量的冗余屬性，現(xiàn)有的屬性序列非常耗時且低效。針對這一問題，Ju等[21-22]首先借鑒局部約簡的思想，將局部約簡設置為屬性序列的起始集，將全局約簡設置為屬性序列的終止集。進一步地，Ju等基于合理粒度準則，提出了一種新穎的多粒度分類預測方法。

另一方面，經典粗糙集模型由于其不可分辨關系的特殊性，僅能處理離散型數(shù)據(jù)，尚不能有效處理連續(xù)型數(shù)據(jù)甚至混合復雜數(shù)據(jù)。鑒于此，Lin[23]建設性地將鄰域拓撲的思想引入于粗糙集，設計出了鄰域粗糙集的最初模型。Hu等[24-25]從粒計算的角度重新闡釋且設計了鄰域粗糙集模型，取得了豐富的研究成果。在鄰域粗糙集理論中，其相應的決策錯誤率是一個重要的概念[26]。鄰域決策錯誤率為從分類學習的視角研究屬性子空間的提取問題提供了一種新的度量標準。由鄰域決策錯誤率約簡構建而來的屬性子空間可以獲得較為理想的鄰域決策錯誤率[27]。

鄰域決策錯誤率為序貫三支分類問題中局部和全局屬性子空間的設定提供了一種新穎的思路?；谝陨嫌懻?，本文系統(tǒng)研究了基于鄰域決策的序貫三支分類方法。首先，通過基于鄰域決策錯誤率的屬性約簡方法構建序貫三支分類問題中的局部屬性子空間和全局屬性子空間?；诖?，可獲取鄰域粗糙集在兩種不同屬性子空間下的正域、負域和邊界域，用于后續(xù)的預測工作。在預測階段，若樣本不能在當前屬性子空間中得到明確分類則需要在更細的屬性子空間進行判斷，并更新相應的三域信息和鄰域信息，以實現(xiàn)不同樣本能夠在合適的屬性子空間上進行分類。

1 序貫三支決策與鄰域粗糙集

事實上，首先將給定對象分為三個獨立的分支，進而對不同分支分別采取不同的應對措施是三支決策的核心機制，該舉措也為認知與決策任務提供了一種分層遞進的信息處理范式。需要注意的是，本文引入實體函數(shù)和閾值來獲取三支決策中三個獨立的區(qū)域。令U為論域，對于論域中的任意對象x∈U，令E表示評價函數(shù)，其中E(x)表示對象x的決策狀態(tài)值。借助閾值α和β，可將正域、邊界域和負域形式化地表示為：

POS(E)={x∈U:E(x)≥α}

(1)

NEG(E)={x∈U:E(x)≤β}

(2)

BND(E)={x∈U:β

(3)

縱觀現(xiàn)有關于粗糙集和三支決策的研究工作，其討論核心大多圍繞非動態(tài)的決策系統(tǒng)或數(shù)據(jù)描述。但是，在面向真實場景的決策問題中，人們最初收集到的信息往往是不確定的，此外，伴隨著信息的迭代補充，決策過程以及決策結果也應更新與遞進。令DesAk(x)表示信息粒Ak對于對象x給出的刻畫，若給定n個不同粒度，則可知對象x在這些粒度上的n個刻畫與描述，記為：

DesA1(x)DesA2(x)DesAk(x)DesAn(x)

(4)

在粗糙集理論中，數(shù)據(jù)集往往被描述為一個二元組，稱作決策信息系統(tǒng)，一般被形式化地刻畫為S=，其中:U為所有樣本或對象組成的集合，常被稱作論域(universe)；AT(condition attribute)表示所有條件屬性的非空有限集合;D(decision attribute)為決策屬性的集合。

對于?a∈AT∪D,定義映射:U→Va,Va表示屬性a的值域,即a(x)∈Va(?x∈U)。

定義1令S為一決策系統(tǒng)，對于?xi∈U，B?AT，對象xi基于屬性子空間B的鄰域則可定義為：

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

(5)

式中：ΔB為利用屬性子空間B上的信息計算對象xi與xj之間的距離函數(shù)。距離函數(shù)需滿足以下條件：

(1)ΔB(xi,xj)≥0。

(2)ΔB(xi,xj)=0當且僅當xi=xj。

(3)ΔB(xi,xj)=ΔB(xj,xi)。

(4)ΔB(xi,xk)≤ΔB(xi,xj)+ΔB(xj,xk)。

在本文中，運用了高斯核距離。對于任意的對象xi和xj，高斯核數(shù)可定義為：

(6)

式中：σ為給定的參數(shù)。進一步地，可將距離函數(shù)定義為：

(7)

根據(jù)徑向基函數(shù)核距離，可得任意兩兩對象之間的距離如下：

(8)

基于徑向基函數(shù)核距離函數(shù)可定義鄰域粗糙集如下。

定義2令S為一決策系統(tǒng)，對于?X?U，B?AT，對象xi基于屬性子空間B的鄰域表示為δB(xi)，上、下近似集就可分別被定義為：

(9)

(10)

在鄰域粗糙集模型中，根據(jù)決策屬性D的信息可將論域劃分為{X1,X2,…,Xl}，則近似質量可表示為：

(11)

2 基于鄰域決策錯誤率的序貫三支分類

在粗糙集屬性約簡方法中，近似質量經常作為度量屬性分類能力的重要指標之一。Hu等[26]認為樣本落入粗糙集邊界域中并不表示其一定會被錯分，只有邊界域中的少數(shù)類樣本存在被錯分的可能。為此Hu等基于鄰域粗糙集模型，從樣本錯誤分類角度提出了鄰域決策錯誤率，并將其作為提取屬性子空間的指標[26]。

假設δB(xi)為樣本xi的鄰域，P(ωj|δB(xi))(j=1,2,…,c)為δB(xi)在類別ωj下的類別概率。根據(jù)此概率可預測樣本xi的對應標記。若P(ωl|δB(xi))=maxjP(ωj|δB(xi))，則樣本xi的類別標記為ωl，表示為ND(xi)=ωl。顯然，ND(xi)=ω(xi)表示對于樣本xi而言，其預測標記與真實標記無差?；诖?，Hu等給出樣本誤分類的損失函數(shù)如下：

(12)

由此可得鄰域錯誤率如下：

(13)

式中：n表示樣本數(shù)。

利用鄰域決策錯誤率，眾多學者[28-31]探索了基于鄰域決策錯誤率的屬性約簡準則，其定義如下。

定義3令S為一決策信息系統(tǒng)，對于?A?AT，A為決策信息系統(tǒng)的一個鄰域決策錯誤率約簡，當且僅當：

(1)NDERA≤NDERAT。

(2) 對于任意的A′?A，都有NDERA′>NDERA。

如定義3的約簡集合不僅能夠刪除決策信息系統(tǒng)中的冗余屬性，而且能夠使得原決策系統(tǒng)的鄰域決策錯誤率盡可能地降低。因此，本文將其定義為序貫三支分類框架中的全局屬性子空間。

在序貫三支分類架構中，局部屬性子空間是全局屬性子空間的真子集。為此，可從全局屬性子空間中截取一部分屬性子集作為局部屬性子空間，且該截取子集也應盡可能地降低鄰域決策錯誤率，其形式化定義如下。

由定義4可知，基于局部屬性子空間的決策信息系統(tǒng)不僅鄰域決策錯誤率相較于原始決策信息系統(tǒng)已降低了至少一半以上，而且壓縮了原決策信息系統(tǒng)的屬性規(guī)模。從序貫三支分類角度看，局部屬性子空間也降低了其屬性搜索規(guī)模。

根據(jù)鄰域決策錯誤率約簡的定義，對于任意的B?AT，a∈AT-B，屬性a相對于屬性子集B的重要度為：

SIG(a,B,D)=NDERB-NDERB∪{a}

(14)

根據(jù)屬性重要度，可設計全局和局部屬性子空間求解算法如算法1所示。

算法1基于鄰域決策錯誤率的全局和局部屬性子空間

輸入：鄰域決策系統(tǒng)S=，鄰域半徑δ，參數(shù)ε。

輸出：全局和局部屬性子空間BG和BL。

1. ?→BG，?→BL；

2. Do

3. ?ai∈AT-BG，計算重要度SIG(ai,BG,D)；

4. 選取最大的重要度及對應的屬性aj；

5. IfSIG(aj,B,D)>0 then

BG=BG∪{ai}；

End If

6. 計算NDERBG；

7. UntilNDERBG≤NDERAT

8. Fori=1:|BG|

9.BL=BL∪{ai}；

11. Break；

12. End If

13. End For

14. 返回BG和BL

基于以上討論，本文以局部屬性子空間為起始序列，以全局屬性子空間為終止序列設計一個如算法2所示的序貫三支分類器。

算法2基于鄰域決策錯誤率的序貫三支分類算法

輸入：鄰域決策系統(tǒng)S=，鄰域半徑δ，參數(shù)ε;測試樣本x。

輸出：測試樣本s的標記。

1. 根據(jù)算法1求得BG和BL；

2. 計算M=BG-BL，得到M={a1,a2,…,al}；

3. 令X=argmaxXj{|Xj|}，其中Xj={x∈U:ω(x)=ωj}；

9.i=1；

10. Whilei≤|M|

11. Ifδ(x)?POS，then

12. 分配測試樣本s正標簽；break；

13. Else ifδ(x)?NEG，then

14. 分配測試樣本s負標簽；break；

15. Else

16.BL=BL∪{ai}；

21. End if

22.i=i+1；

23. End if

24. End While

25. If 測試樣本x未分配標記

26. 根據(jù)δ(x)中多數(shù)對象的標記分配給x；

27. End if

28. 測試樣本x的標記

本文將所提算法命名為基于鄰域決策錯誤率的序貫三支分類算法，并簡寫為NR-S3WC。NR-S3WC主要分為5個環(huán)節(jié)：(1) 根據(jù)局部屬性子空間信息，進行初始化運算；(2) 分析測試樣本與訓練樣本兩兩之間的高斯核距離度量值；(3) 求得測試樣本的鄰域信息粒；(4) 觀測當前屬性子空間下鄰域信息粒中訓練樣本的標記，進而給出待預測標記；(5) 如若1至4環(huán)節(jié)過程未能得出確切的標記信息，則根據(jù)全局屬性子空間下的信息粒，由多數(shù)投票原則預測測試樣本的標記。

在鄰域類分類器中，鄰域閾值的確定也是關鍵之一。本文借鑒Hu等提出方法，根據(jù)式(15)設置鄰域。

(15)

3 結果分析

為了驗證所提NR-S3WC分類方法的有效性，本節(jié)在6組公共UCI數(shù)據(jù)集上進行了一系列相關的對比實驗，其具體信息如表1所示。本節(jié)所用數(shù)據(jù)均下載于UCI公共數(shù)據(jù)庫，且都為完備數(shù)據(jù)。此外，本文還采用10折交叉驗證方法，將原始數(shù)據(jù)集隨機劃分為互不相交的訓練集與測試集。其中:訓練集用以構建NR-S3WC分類模型；測試集則用以評估分類預測的準確性。

表1 數(shù)據(jù)描述

為了驗證本文方法的有效性，圖1至圖3分別從屬性個數(shù)、運行時間和分類精度角度對比了本文方法和Hu等提出的鄰域分類方法[32]。

圖1 屬性個數(shù)比較

圖2 運行時間比較

圖3 分類精度比較

考察圖中的實驗結果，可得到如下結論：

(1) 從屬性個數(shù)角度不難看出，隨著閾值w的不斷增大，NR-S3WC算法所需要的屬性個數(shù)不斷增大。這意味著當算法選擇相對較高的w值，那么其需要的屬性數(shù)則越多。此外，當w值越接近于1時，NR-S3WC算法所需要的屬性數(shù)也越接近于全局屬性子空間的屬性個數(shù)。

(2) 從算法運行時間來看，Hu等提出的鄰域分類方法優(yōu)于本文方法。這是由于算法不同運行機制導致的。眾所周知，Hu等提出的鄰域分類方法是基于某一特定的屬性子空間，本文算法基于鄰域錯誤率約簡屬性子集，并在分類中作出一次性決斷。而NR-S3WC算法則是基于序貫三支分類思想，針對每個測試樣本，均需尋找其最合適的屬性子空間，故需耗費更多的時間。

(3) 從分類精度結果來看，不難得出本文方法在多數(shù)w值下，分類精度優(yōu)于鄰域分類方法。有趣的是，當閾值w取兩端極值時即w=0或w=1時，兩種算法的分類效果均一般。

綜上所述，相較于Hu等提出的鄰域分類方法，本文方法雖需耗費更多的運行時間，但在相對較少屬性的條件下能夠獲取更高的分類精度，提高了數(shù)據(jù)的分類性能，是一種有效的分類方法。

4 結 語

為了進一步豐富和發(fā)展序貫三支分類方法的研究，本文引入鄰域決策錯誤率約簡構建序貫三支框架中的全局屬性子空間，并基于此提出合理的局部屬性子空間?；诰植亢腿謱傩宰涌臻g，提出一種基于鄰域決策錯誤率的序貫三支分類算法。公共數(shù)據(jù)集上的對比實驗表明，該方法雖消耗了更多的運行時間，但能夠在相對較少屬性的條件下獲取更高的分類精度，提高了數(shù)據(jù)的分類性能，故本文方法是一種有效的分類方法。