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

亓 慧 魏 巍 王文劍,3

1(太原師范學(xué)院計(jì)算機(jī)系 山西 晉中 030619)2(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 山西 太原 030006)3(山西大學(xué)計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室 山西 太原 030006)

0 引 言

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

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

另一方面，經(jīng)典粗糙集模型由于其不可分辨關(guān)系的特殊性，僅能處理離散型數(shù)據(jù)，尚不能有效處理連續(xù)型數(shù)據(jù)甚至混合復(fù)雜數(shù)據(jù)。鑒于此，Lin[23]建設(shè)性地將鄰域拓?fù)涞乃枷胍胗诖植诩O(shè)計(jì)出了鄰域粗糙集的最初模型。Hu等[24-25]從粒計(jì)算的角度重新闡釋且設(shè)計(jì)了鄰域粗糙集模型，取得了豐富的研究成果。在鄰域粗糙集理論中，其相應(yīng)的決策錯(cuò)誤率是一個(gè)重要的概念[26]。鄰域決策錯(cuò)誤率為從分類學(xué)習(xí)的視角研究屬性子空間的提取問(wèn)題提供了一種新的度量標(biāo)準(zhǔn)。由鄰域決策錯(cuò)誤率約簡(jiǎn)構(gòu)建而來(lái)的屬性子空間可以獲得較為理想的鄰域決策錯(cuò)誤率[27]。

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

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

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

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

(1)

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

(2)

BND(E)={x∈U:β

(3)

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

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

(4)

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

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

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

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

(5)

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

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

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

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

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

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

(6)

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

(7)

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

(8)

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

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

(9)

(10)

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

(11)

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

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

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

(12)

由此可得鄰域錯(cuò)誤率如下：

(13)

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

利用鄰域決策錯(cuò)誤率，眾多學(xué)者[28-31]探索了基于鄰域決策錯(cuò)誤率的屬性約簡(jiǎn)準(zhǔn)則，其定義如下。

定義3令S為一決策信息系統(tǒng)，對(duì)于?A?AT，A為決策信息系統(tǒng)的一個(gè)鄰域決策錯(cuò)誤率約簡(jiǎn)，當(dāng)且僅當(dāng)：

(1)NDERA≤NDERAT。

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

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

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

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

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

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

(14)

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

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

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

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

1. ?→BG，?→BL；

2. Do

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

4. 選取最大的重要度及對(duì)應(yīng)的屬性aj；

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

BG=BG∪{ai}；

End If

6. 計(jì)算NDERBG；

7. UntilNDERBG≤NDERAT

8. Fori=1:|BG|

9.BL=BL∪{ai}；

11. Break；

12. End If

13. End For

14. 返回BG和BL

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

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

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

輸出：測(cè)試樣本s的標(biāo)記。

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

2. 計(jì)算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. 分配測(cè)試樣本s正標(biāo)簽；break；

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

14. 分配測(cè)試樣本s負(fù)標(biāo)簽；break；

15. Else

16.BL=BL∪{ai}；

21. End if

22.i=i+1；

23. End if

24. End While

25. If 測(cè)試樣本x未分配標(biāo)記

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

27. End if

28. 測(cè)試樣本x的標(biāo)記

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

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

(15)

3 結(jié)果分析

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

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

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

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

圖2 運(yùn)行時(shí)間比較

圖3 分類精度比較

考察圖中的實(shí)驗(yàn)結(jié)果，可得到如下結(jié)論：

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

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

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

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

4 結(jié) 語(yǔ)

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