序貫三支監(jiān)督多粒度決策方法

汪琳娜, 楊 新, 楊習貝

(1.四川交通職業(yè)技術學院 軌道交通工程系， 成都 611130) (2.西南財經(jīng)大學 經(jīng)濟信息工程學院， 成都 611130) (3.江蘇科技大學 計算機學院， 鎮(zhèn)江 212100)

三支決策是加拿大里賈納大學姚一豫教授提出的一種基于“三”和粒計算理論的思考、復雜問題求解和信息處理方法，其基本思想可以解釋為由三分、治略和成效(trisecting，acting，outcome，TAO)3個基本要素組成的TAO模型[1-3].三支決策方法經(jīng)過孵化期(1980—2006)和羽化期(2007—2016)正逐漸走向成長期(2017—)，可以大致分為狹義三支決策和廣義三支決策[2,4].前者主要是在三支決策發(fā)展早期由解釋粗糙集理論中三種分類規(guī)則(接受、拒絕和延緩/不承諾)演化而來的“三分而治”思想，后者則大大推動了三支決策理論走向更廣闊的應用場景.目前三支決策思想被國內(nèi)外學者成功應用在諸多領域，衍生出一系列的“三支方法”，如三支分類[5-6]、三支聚類[7]、三支沖突分析[8]、三支概念學習[9]、三支主動學習[10]、三支推薦[11]和三支圖像識別[12]等.

傳統(tǒng)的靜態(tài)三支決策只是在單一粒度下考慮實施一次三支決策，而動態(tài)三支決策提供了一種多層次和多視角的多階段決策問題解決方法，其典型模型是序貫三支決策.基于粒結構的結構化思維、結構化問題求解方法和結構化信息處理方式的粒計算三元論思想[13]，序貫三支決策框架主要是通過構建多層次的粒度、多樣性的對象描述和評價、多元化的粒度代價結構來實現(xiàn)一種快速、低成本、高收益和容錯的動態(tài)決策，以此來平衡決策過程代價和決策結果代價[14].近年來，圍繞序貫三支決策的理論和應用研究層出不窮.文獻[12,15]通過構建圖像的多粒度結構提出了一種基于序貫三支決策的代價敏感人類識別方法，并推廣到基于深度神經(jīng)網(wǎng)絡的特征粒度提取和識別問題中.文獻[16]設計了一種基于序貫三支決策思想的粗糙集屬性約簡方法.文獻[17]在局部和全局視角給出一種基于合理信息粒度的序貫三支分類模型.文獻[18-20]提出了一種廣義的增量序貫三支決策框架，并面對多類和混合動態(tài)數(shù)據(jù)構造了高效的序貫三支處理方法.基于序貫三支決策在理論、方法和應用方面的已有研究成果，文中在鄰域系統(tǒng)中用已有或者預測的對象決策類別信息(樣本標記信息)來幫助構建和優(yōu)化多層次的粒度結構，以此來提高序貫三支決策方法的效率.

基于序貫三支決策理論，如何生成和構建合理的多粒度結構是一個關鍵問題.在鄰域系統(tǒng)中，對象的鄰域粒化是構建多層次粒度結構的基本操作.為了在多階段的決策過程中有效快速地降低問題的不確定性，需要在多層次的粒度結構中構造出合適粒度的鄰域粒子，過大或者過小的粒子都會影響序貫三支決策的決策過程代價和決策結果代價.目前針對鄰域系統(tǒng)普遍的造粒方式都是通過一個鄰域閾值δ來定義鄰域關系RN，從而得到鄰域粒子.但該方法在提高鄰域粒子質(zhì)量方面的效率有限.為了解決這個問題，文獻[21]在鄰域關系中增加了對象間偽標記相同的約束條件，采用K-means聚類得到的偽標記來優(yōu)化鄰域粒子.文獻[22]運用監(jiān)督粒化策略構建了一個新的鄰域關系，并驗證了相應的鄰域屬性約簡方法的性能.文獻[23]利用已有的決策類別信息構建了一個監(jiān)督鄰域粗糙集模型，提出的類內(nèi)閾值δIntra和類間閾值δInter能夠更好地控制鄰域粒子的構造過程，且當類間閾值δInter=1時退化為文獻[18-20]提出的方法.

基于以上分析，文中將在鄰域三支決策模型中采用類內(nèi)和類間兩種閾值，借助決策類別等監(jiān)督信息來生成多粒度粒子，以此來提升多層次粒度結構的構造質(zhì)量，實現(xiàn)高效的序貫三支決策.

1 鄰域三支決策模型

傳統(tǒng)決策粗糙集模型只能通過等價關系處理名義型數(shù)據(jù).文獻[24]提出一種可以同時處理數(shù)值型和名義型數(shù)據(jù)的鄰域粗糙集分類模型.此后，文獻[25]提出了一種基于鄰域關系的決策粗糙集模型，并討論了基于最小決策代價的屬性約簡方法.與上述兩種方法不同，文中運用高斯核函數(shù)[26]來構建一種基于鄰域相似閾值的三支決策模型.

定義1假設一個四元鄰域決策信息系統(tǒng)NDS=(U,A,V,f)，其中論域U表示一個非空有限的對象集合；A表示一個非空有限的屬性集合，包含條件屬性集C和決策屬性集D，A=C∪D；V=∪Vb表示值域，Vb是對象在屬性b下的所有可能取值;f:U×A→V是一個映射函數(shù)，使得?b∈A，x∈U,f(x,b)∈Vb.

定義2給定一個鄰域決策信息系統(tǒng)，對任意的x∈U和B?C，定義對象x的鄰域粒子為：

γB(x)={y|y∈U,ΓB(x,y)≥γ}

(1)

式①中：高斯核函數(shù)為：

ΓB(x,y)=exp(-‖x-y‖2/σ)

(2)

式中：σ為高斯核函數(shù)的寬度參數(shù)，相似閾值γ滿足0≤γ≤1.

基于上述定義，可以得到相應的鄰域關系為：

RB(x)={(x,y)∈U×U|ΓB(x,y)≥γ}

(3)

其中滿足以下3條性質(zhì)：

(1) 0≤ΓB(x,y)≤1；

(2)ΓB(x,x)=1；

(3)ΓB(x,y)=ΓB(y,x).

顯然基于相似閾值的鄰域關系RB(x)滿足自反性和對稱性，但不滿足傳遞性.對任意的xi,xj∈U，鄰域關系RB(x)也可以表示為一個n×n的關系矩陣MB=(rij)|U|×|U|(i,j=1,2,…,U)，其中：

(4)

下面給出基于相似閾值的鄰域三支決策模型.

定義3給定一個鄰域決策信息系統(tǒng)，假設一對閾值對(α,β)，其中0≤β<α≤1.對任意的X?U和B?C，論域U可以被劃分為兩兩不相交的3個區(qū)域為：

(5)

其中條件概率Pr(X|γB(x))=|X|γB(x)|/|γB(x)|，也稱為粗糙隸屬度函數(shù)，|·|表示集合的勢.

通過貝葉斯最小風險決策理論可以推導出計算定義2中閾值對(α,β)的數(shù)學公式.假設考慮一個二分類問題.給定決策狀態(tài)集合Ω={X,XC}和決策行動集合A={aP,aB,aN}，其中X和XC互補，行動集中aP,aB,aN分別表示將對象分類到正域、邊界域和負域的決策動作.給定一個損失函數(shù)矩陣為：

(6)

式中：λPP,λBP,λNP分別為當狀態(tài)為X時采取行動aP,aB,aN下的損失；λPN,λBN,λNN分別為當狀態(tài)為XC時采取行動aP,aB,aN下的損失.因此可分別采取行動aP,aB,aN下的期望損失為：

(7)

根據(jù)貝葉斯決策準則，選擇期望損失最小的行動集作為最佳的行動方案.基于此可以推導得出閾值對(α,β)的具體計算公式為：

(8)

2 監(jiān)督鄰域三支決策模型

傳統(tǒng)單一的閾值設置不能更好地處理和優(yōu)化鄰域粒化問題.為了降低鄰域粒子的不確定性，下面通過引入類內(nèi)閾值γIntra和類間閾值γInter生成監(jiān)督鄰域粒子來構造一個監(jiān)督鄰域三支決策模型.

定義4給定一個鄰域決策信息系統(tǒng)，決策屬性D將U劃分為N個決策類，表示為D={D1,D2,…,Dk},k=1,2,…,N.假設類內(nèi)閾值γIntra和類間閾值γInter滿足0≤γIntra≤1和0≤γInter≤1，對任意的x∈U和B?C，對象x的監(jiān)督鄰域粒子為：

U{y|y?Dk(x)∧ΓB(x,y)≥γInter}

(9)

式中：Dk(x)為對象x所在的決策類集合.

根據(jù)定義4，監(jiān)督鄰域關系可以表示為：

γIntra∨y?Dk(x)∧ΓB(x,y)≥γInter}

(10)

定義4給出了一種運用決策類別信息生成與對象x相似的監(jiān)督鄰域粒子方法.根據(jù)監(jiān)督類別信息，當兩個對象屬于同一決策類時，使用類內(nèi)閾值計算監(jiān)督鄰域粒子；相反，如果兩個對象不屬于同一決策類時，則使用類間閾值.對比式(1)，監(jiān)督鄰域粒子可以通過控制類內(nèi)閾值γIntra和類間閾值γInter優(yōu)化鄰域粒化，降低多粒度結構下的不確定性.通常有3種方法來設置這兩種閾值，即：

(1) 0≤γIntra<γInter≤1

(2) 0≤γInter<γIntra≤1

(3) 0≤γIntra=γInter≤1

為了增加鄰域粒子中的類內(nèi)對象，同時減小鄰域粒子中的類間對象，一般可采用第一種方法，對類間對象采取更加嚴格的粒化機制，即讓類間閾值γInter大于類內(nèi)閾值γIntra.文中采用第一種方法.顯然第三種方法會退化為定義2中鄰域粒子的定義.相對于定義2，通過合理設置可以得到鄰域粒子的一些性質(zhì).

通過定義1和定義4很容易證明以上3個性質(zhì).相對于定義1的方法，運用監(jiān)督鄰域的類內(nèi)和類間兩種閾值可以很好地控制鄰域粒子的質(zhì)量，在鄰域粒子中增加類內(nèi)對象，減少類間對象，從而降低多粒度結構的不確定性.

假設把決策類Dk,k=1,2,…,N作為定義3中論域U的子集X，利用監(jiān)督鄰域粒子可以得到一個新的監(jiān)督鄰域三支決策模型.

定義5給定一個鄰域決策信息系統(tǒng)，假設一對閾值對(α,β)，其中0≤β<α≤1.對任意的B?C和決策類Dk,k=1,2,…,N，決策Dk關于屬性B的監(jiān)督鄰域三支決策區(qū)域可表示為：

(10)

對于所有決策類D，可以得到：

(11)

為了分析基于監(jiān)督鄰域下的多粒度結構的不確定性變化，給出3種基于監(jiān)督鄰域的度量方法.

定義6給定一個鄰域決策信息系統(tǒng)，對任意的B?C，監(jiān)督知識粒度可以定義為：

(12)

定義7給定一個鄰域決策信息系統(tǒng)，對任意的B?C，監(jiān)督近似質(zhì)量可以定義為：

(13)

定義8給定一個鄰域決策信息系統(tǒng)，對任意的B?C，監(jiān)督條件熵可以定義為:

(14)

根據(jù)三種不確定性度量定義，相對于定義3的鄰域三支決策模型，當采用提出的監(jiān)督鄰域方法時，可以的得到一些性質(zhì).

性質(zhì)3給定一個鄰域決策信息系統(tǒng)，GKSN表示監(jiān)督知識粒度(采用類內(nèi)閾值γIntra和類間閾值γInter)，GK表示非監(jiān)督知識粒度(采用單一閾值λ)，對任意的x∈U和B?C，當0≤λ=γIntra<γInter≤1時，有GKSN≤GK.

性質(zhì)4給定一個鄰域決策信息系統(tǒng)，AQSN表示監(jiān)督近似質(zhì)量(采用類內(nèi)閾值γIntra和類間閾值γInter)，AQ表示非監(jiān)督近似質(zhì)量(采用單一閾值λ)，對任意的x∈U和B?C，當0≤λ=γIntra<γInter≤1時，有AQSN≥AQ.

性質(zhì)5給定一個鄰域決策信息系統(tǒng)，CESN表示監(jiān)督條件熵(采用類內(nèi)閾值γIntra和類間閾值γInter)，CE表示非監(jiān)督近似質(zhì)量(采用單一閾值λ)，對任意的x∈U和B?C，當0≤λ=γIntra<γInter≤1時，有CESN≤CE.

以上性質(zhì)可通過定義1、定義4和性質(zhì)4容易得到.當采用監(jiān)督鄰域方法，設置閾值滿足0≤λ=γIntra<γInter≤1時，會獲得比非監(jiān)督鄰域方法更小的知識粒度和條件熵，以及更高的近似質(zhì)量.顯然按照這3個度量的解釋，運用監(jiān)督鄰域方法可以大大減小鄰域粒子和多粒度結構的不確定性.

3 基于監(jiān)督多粒度的序貫三支決策模型

運用監(jiān)督鄰域方法構建一個多層次的監(jiān)督多粒度結構來實施序貫三支決策過程，首先給出一個m層的監(jiān)督多粒度結構定義.

(15)

且監(jiān)督鄰域粒子滿足：

則m層的監(jiān)督多粒度結構可以定義為：

(16)

在定義6中，通過在m層的監(jiān)督多粒度結構設置不同的類內(nèi)閾值γIntra和類間閾值γInter，不僅可以得到隨著層次增加逐漸單調(diào)減小的監(jiān)督鄰域粒子，而且將提升監(jiān)督鄰域粒子的質(zhì)量，從而可以大大優(yōu)化多層次的粒度結構.

0≤β1≤β2≤…≤βm<αm≤…≤α2≤α1≤1

(17)

則在監(jiān)督多粒度結構的第i層，對決策類Dk,k=1,2,…,N，監(jiān)督鄰域三支決策區(qū)域的計算可以表示為：

(18)

表1 第i層的7種選擇情況

在監(jiān)督多粒度結構的第i層，所處理的對象Ui全部來自于第i-1層，表1提供了7種選擇情況.在傳統(tǒng)序貫三支決策模型中，通常會選擇第二種情況，即在粒結構的每一層只處理上一層中邊界域中的對象.通過多階段的序貫三支決策，邊界域中的對象逐漸單調(diào)減小，而正域和負域中的對象逐漸單調(diào)增多.其他6種情況也可以被用在多類分類問題、人才選拔和異常檢測等應用領域.

4 實驗分析

文中運用4組UCI數(shù)據(jù)集(只包含數(shù)值型屬性)來驗證所提方法的效率，具體數(shù)據(jù)信息見表2.電腦配置為Intel (R) Core (TM) i5-4210U CPU @ 1.70GHz，12G內(nèi)存，Windows10操作系統(tǒng)，Matlab2016a實驗平臺.

表2 數(shù)據(jù)集描述

針對監(jiān)督多粒度方法和非監(jiān)督多粒方法在序貫三支決策的不確定性方面進行比較，采用了3種度量標準，即知識粒度、近似質(zhì)量和條件熵.

在對比實驗中，采用表1的第二種情況，高斯核參數(shù)均設置為σ=0.8.考慮5層次的多粒度結構，每一層的屬性個數(shù)設置采取均勻遞增方式.比如數(shù)據(jù)集Ionosphere，共34個屬性，可設置第一層為2個屬性，此后每層遞增8個屬性，即第二層到第五層屬性個數(shù)分別為10、18、26和34.其它3個數(shù)據(jù)集按照類似方法設置.監(jiān)督多粒度方法的類內(nèi)閾值γIntra和類間閾值γInter、非監(jiān)督多粒度的相似閾值γ和決策閾值對(α,β)的設置見表3.

表3 閾值設置

表4給出了4個數(shù)據(jù)集在5層粒度結構下監(jiān)督和非監(jiān)督知識粒度的對比情況.GKSN為監(jiān)督知識粒度，而GK為非監(jiān)督知識粒度.由實驗結果可以看出，從第一層到第五層，兩種知識粒度都逐漸遞減.此外，對比兩種知識粒度，可以發(fā)現(xiàn)在大多數(shù)情況下，監(jiān)督知識粒度GKSN都普遍小于非監(jiān)督知識粒度GK.這表明非監(jiān)督多粒度方法可以更好地在多層次粒結構上更好地加速知識粒度的由粗到細的變化過.

表4 知識粒度的對比

表5和表6分別給出了監(jiān)督多粒度和非監(jiān)督對粒度在近似質(zhì)量和條件熵上的對比情況.AQSN為監(jiān)督近似質(zhì)量，AQ為非監(jiān)督近似質(zhì)量；CESN為監(jiān)督條件熵，CE為非監(jiān)督條件熵.由表5可以看出,大部分的近似質(zhì)量都會隨著粒度層次的增加而增加，而且監(jiān)督多粒度方法的近似質(zhì)量基本上都大于非監(jiān)督方法.在表6中，大部分的條件熵都會隨著粒度層次的增加而減小，而且監(jiān)督多粒度方法的條件熵基本上都小于非監(jiān)督方法.由此可見，在序貫三支決策過程中，所提出的監(jiān)督多粒度方法熵在不確定性方面表現(xiàn)出了更好的性能.

表5 近似質(zhì)量的對比

表6 條件熵的對比

表7給出了監(jiān)督多粒度方法和非監(jiān)督多粒度方法在序貫三支決策過程中三個決策區(qū)域的對象百分比變化情況，其中USS3WD表示非監(jiān)督多粒度方法，而SS3WD表示監(jiān)督多粒度方法.由表7可看出，隨著粒度層次的增加，邊界域逐漸減小，而正域和負域逐漸增大，說明決策的不確定性在逐漸減小.對比兩種方法發(fā)現(xiàn)，監(jiān)督多粒度會加速樣本從邊界域轉移到正域或負域的速度，即監(jiān)督多粒度會加快信息不確定性的降低.

表7 序貫三支決策區(qū)域的對比

5 結論

傳統(tǒng)鄰域多粒度方法采用單一閾值粒化得到粒子，大大限制了序貫三支決策中多層次粒結構的構造性能.文中運用已有的對象決策類別信息，采用類內(nèi)閾值和類間閾值的方法在序貫三支決策過程中實現(xiàn)了對鄰域粒子和多粒度結構的優(yōu)化，大大提升了降低不確定性的速度，提高了多階段三支決策的性能.序貫三支決策的關鍵是構建多層次的粒度結構，下一步會考慮更多有用的動態(tài)監(jiān)督信息，研究序貫三支決策中的信息粒化和多粒度結構構建問題.