汪琳娜, 楊 新, 楊習(xí)貝

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

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

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

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

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

1 鄰域三支決策模型

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

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

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

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

(1)

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

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

(2)

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

基于上述定義，可以得到相應(yīng)的鄰域關(guān)系為：

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).

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

(4)

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

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

(5)

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

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

(6)

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

(7)

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

(8)

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

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

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

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

(9)

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

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

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

(10)

定義4給出了一種運(yùn)用決策類別信息生成與對(duì)象x相似的監(jiān)督鄰域粒子方法.根據(jù)監(jiān)督類別信息，當(dāng)兩個(gè)對(duì)象屬于同一決策類時(shí)，使用類內(nèi)閾值計(jì)算監(jiān)督鄰域粒子；相反，如果兩個(gè)對(duì)象不屬于同一決策類時(shí)，則使用類間閾值.對(duì)比式(1)，監(jiān)督鄰域粒子可以通過(guò)控制類內(nèi)閾值γIntra和類間閾值γInter優(yōu)化鄰域?；档投嗔６冉Y(jié)構(gòu)下的不確定性.通常有3種方法來(lái)設(shè)置這兩種閾值，即：

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

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

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

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

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

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

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

(10)

對(duì)于所有決策類D，可以得到：

(11)

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

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

(12)

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

(13)

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

(14)

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

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

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

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

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

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

運(yùn)用監(jiān)督鄰域方法構(gòu)建一個(gè)多層次的監(jiān)督多粒度結(jié)構(gòu)來(lái)實(shí)施序貫三支決策過(guò)程，首先給出一個(gè)m層的監(jiān)督多粒度結(jié)構(gòu)定義.

(15)

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

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

(16)

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

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

(17)

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

(18)

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

表3 閾值設(shè)置

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

表4 知識(shí)粒度的對(duì)比

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

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

表6 條件熵的對(duì)比

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

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

5 結(jié)論

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