岳文琦， 張 楠， 童向榮， 張中喜

(1.煙臺大學(xué) 計(jì)算機(jī)與控制工程學(xué)院 山東 煙臺 264005； 2.煙臺大學(xué) 數(shù)據(jù)科學(xué)與智能技術(shù)山東省高校重點(diǎn)實(shí)驗(yàn)室 山東 煙臺 264005)

0 引言

三支決策模型[1-2]是Yao等基于決策粗糙集理論模型并結(jié)合實(shí)際決策情況擴(kuò)展的分類決策,相對于經(jīng)典的粗糙集模型[3]提高了容錯率,較二支決策更符合人們?nèi)粘Q策行為。三支決策模型已得到諸多學(xué)者的完善與發(fā)展[4-13],在數(shù)據(jù)挖掘、集成學(xué)習(xí)和信息處理等眾多研究領(lǐng)域[14-17]得到廣泛應(yīng)用。文獻(xiàn)[18]提出序貫三支決策模型的代價敏感分類方法。文獻(xiàn)[19]提出了基于三角范數(shù)和三角余模的半三支決策空間到三支決策空間的轉(zhuǎn)換方法。文獻(xiàn)[20]提出基于行動的三支決策的有效性度量。文獻(xiàn)[21]和文獻(xiàn)[22]將期望效用理論引入三支決策模型,提出效用三支決策模型。三支決策模型中屬性約簡算法主要有代價敏感近似屬性約簡算法[23]、風(fēng)險最小化屬性約簡算法[24]、正域最大化屬性約簡算法及定性和定量屬性約簡算法[25]。

混合決策信息系統(tǒng)中存在實(shí)值型、布爾型和類別型等混合類型數(shù)據(jù),現(xiàn)有的三支決策模型不能處理混合類型數(shù)據(jù)。本文提出的模糊效用三支決策模型補(bǔ)充了三支決策模型在處理混合類型數(shù)據(jù)方面的空缺。該模型在混合決策信息系統(tǒng)中使用混合距離函數(shù)[26]處理混合屬性,用高斯核函數(shù)定義決策表屬性集的模糊T-等價關(guān)系,然后構(gòu)造相應(yīng)的模糊條件概率,使用效用函數(shù)構(gòu)造概率閾值劃分論域。本文在模糊效用三支決策模型中提出正域分布保持和最大效用屬性約簡算法。正域分布保持屬性約簡算法以保證約簡前后不改變決策表正域?yàn)榧s簡目標(biāo),可以求出不改變所有決策類正域的約簡;最大效用屬性約簡算法以追求決策者最大滿意程度為約簡目標(biāo),可求出比決策表屬性集更大的約簡。近似分類質(zhì)量實(shí)驗(yàn)表明正域分布保持啟發(fā)式算法屬性約簡前后不改變決策表正域。J48正確分類率對比實(shí)驗(yàn)表明本文提出的兩種算法高于文獻(xiàn)[21]和文獻(xiàn)[24]算法分類正確率;算法運(yùn)行時間實(shí)驗(yàn)比較三種不同決策態(tài)度中兩種算法的運(yùn)行效率;約簡效用表明最大效用啟發(fā)式算法可以在混合決策信息系統(tǒng)中找到比決策表屬性集更大效用的約簡。

1 基本概念

1.1 混合決策信息系統(tǒng)

存在多種類型數(shù)據(jù)的信息系統(tǒng)或決策系統(tǒng),稱為混合決策信息系統(tǒng)。本節(jié)主要介紹混合決策信息系統(tǒng)和混合距離函數(shù)定義。

混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),其中：U表示對象的集合；AT表示屬性的集合；C表示混合條件屬性的集合；D表示決策屬性集合；V表示屬性值的集合；f:U×AT→V是一個信息函數(shù),是對象到混合屬性值關(guān)系的映射。

定義1[26]給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),C={a1,a2,…,an},n=|C|, ?x,y∈U,a(x),a(y)∈V,混合距離函數(shù)HD(x,y)定義為

定義2[27-29]給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),?x,y∈U,對于?A?C,對象x和y之間的模糊關(guān)系用高斯核函數(shù)定義為

μA(x,y)反映了論域中的對象x和y對于屬性集A的隸屬程度,σ2的值由專家經(jīng)驗(yàn)給定。

1.2 效用三支決策模型

效用是決策者在決策活動中對于決策后果的偏好[30],假定決策者對備擇選項(xiàng)帶來的效用進(jìn)行預(yù)期,則決策者的最終決策目標(biāo)為最大化期望效用。

給定狀態(tài)集Ω={X,Xc},X表示對象x屬于決策類,Xc表示對象x不屬于決策類,決策方案A′={αP,αB,αN},αP表示判定對象x屬于正域,αB表示判定對象x屬于邊界域,αN表示判定對象x屬于負(fù)域。在不同狀態(tài)下采取不同的決策方案的效用值如表1[21]所示。

表1 效用函數(shù)Table 1 The utility function

2 模糊效用三支決策模型

本節(jié)結(jié)合模糊概念和決策者的主觀效用,提出一種新的模糊效用三支決策模型,在該模型中提出兩個約簡目標(biāo)(最大效用和正域分布保持)。

2.1 期望效用決策規(guī)則

期望效用決策規(guī)則以追求決策者最大滿意程度為決策目標(biāo),通過貝葉斯風(fēng)險決策過程,獲取決策規(guī)則,選取效用值最大的決策方案進(jìn)行決策。

定義3給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),?x,y∈U,?A?C,模糊隸屬度函數(shù)為μA(x,y),包含對象x的模糊類定義為

定義4給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),?x,y∈U,?A?C,模糊隸屬度函數(shù)為μA(x,y),U={x1,x2,…,x|U|},決策類X∈U/D,混合信息系統(tǒng)下的模糊條件概率定義為

P(X|[x]μA)表示模糊T-等價類[x]μA被正確分類到X中的概率,模糊類[x]μA關(guān)于X的隸屬度越高,x被劃分到X中的概率越高；反之,模糊類[x]μA關(guān)于X的隸屬度越低,x被劃分到X中的概率越低。

決策者采取決策方案A′={αP,αB,αN}產(chǎn)生的期望效用為定義5。

定義5給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),?A?C,X∈U/D,模糊類為[x]μA,采取三種決策方案αP、αB和αN的期望效用分別為

Ψ(αP|[x]μA)=u(λPP)P(X|[x]μA)+u(λPN)P(XC|[x]μA),

Ψ(αB|[x]μA)=u(λBP)P(X|[x]μA)+u(λBN)P(XC|[x]μA),

Ψ(αN|[x]μA)=u(λNP)P(X|[x]μA)+u(λNN)P(XC|[x]μA)。

定義6給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),?A?C,決策類X∈U/D,模糊類為[x]μA,對于?x∈U決策規(guī)則為:

1) 若模糊條件概率滿足P(X|[x]μA)≥α,則判定x∈POSA(X)；

2) 若模糊條件概率滿足β

3) 若模糊條件概率滿足P(X|[x]μA)≤β,則判定x∈NEGA(X)。

現(xiàn)實(shí)生活中,決策者進(jìn)行決策時，所有的決策結(jié)果產(chǎn)生的影響并不完全一致。信息系統(tǒng)中,決策表中不同決策類也存在差異。針對決策表中每個決策類生成不同的概率閾值，劃分論域、正域、邊界域和負(fù)域及全部效用為定義7。

定義7給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),決策類集合U/D={X1,X2,…,Xm},m=|U/D|,0≤β<α≤1,對于?A?C,?X?U/D,對象x劃分到所有決策類X的正域、邊界域和負(fù)域產(chǎn)生的正域效用、邊界域效用和負(fù)域效用分別表示為

改革開放以來，歷次黨代會報(bào)告都以一系列新思想新觀點(diǎn)新論斷極大地推進(jìn)了馬克思主義中國化，促進(jìn)了中國特色社會主義理論體系的形成和發(fā)展，黨的十八大報(bào)告（以下簡稱報(bào)告）也是如此。筆者認(rèn)為，報(bào)告對中國特色社會主義理論體系的新發(fā)展，主要體現(xiàn)在以下十三個方面。

2.2 正域分布保持定義

信息量是一個事件所帶來的具體信息的量度,本節(jié)主要內(nèi)容為結(jié)合條件信息量[31]和正域分布保持[32]給出模糊效用三支決策模型下混合屬性條件信息量的定義。

定義8給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),決策類集合U/D={X1,X2,…,Xm},m=|U/D|,0≤β<α≤1,對于?A?C,混合屬性集A的條件信息量定義為

由條件信息量的定義可得

3 混合模糊效用三支決策模型屬性約簡算法

3.1 算法介紹

本節(jié)中兩個約簡目標(biāo)(最大效用和正域分布保持)均采用前向貪婪循環(huán)算法進(jìn)行屬性約簡。

定義9給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),且A?C,當(dāng)且僅當(dāng)A滿足以下兩個條件時,A是C的一個最大效用屬性約簡。

1)UtilityA≥UtilityC；

2) 對于?A′?A,UtilityA′

定義10給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),A?C,ai∈C-A,最大效用啟發(fā)式屬性約簡算法的外部屬性重要度為

定義11給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),A?C,0≤β<α≤1,當(dāng)且僅當(dāng)A滿足以下兩個條件時,A是C的一個正域分布保持屬性約簡。

定義12給定混合決策信息系統(tǒng)HIS=(U,AT=C∪D,V,f),A?C,ai∈C-A,正域分布保持啟發(fā)式屬性約簡算法中的外部屬性重要度為

構(gòu)造混合決策信息系統(tǒng)中的最大效用啟發(fā)式屬性約簡算法(forward greedy algorithm of maximal utility attribute reduction, FG-MUAR),算法如下。

算法1最大效用屬性約簡算法

輸入:混合決策信息表HIS=(U,AT=C∪D,V,f)。

輸出:決策表的一個約簡A。

A=?。

計(jì)算決策表所有屬性集效用UtilityC。

若UtilityA

若不滿足條件則結(jié)束循環(huán)。

對于?ai∈A,若滿足條件UtilityA-{ai}≥UtilityA,則A=A-{ai}。

輸出約簡A。

構(gòu)造混合決策信息系統(tǒng)中的正域分布保持屬性約簡算法(forward greedy algorithm of positive region distribution preservation, FG-PRAR),算法如下。

算法2正域分布保持屬性約簡算法

輸入:混合決策信息表HIS=(U,AT=C∪D,V,f)。

輸出:決策表的一個約簡A。

Core(C)=?。

A=Core(C)。

若不滿足條件，則結(jié)束循環(huán)。

輸出約簡A。

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

本節(jié)實(shí)驗(yàn)采用6個UCI數(shù)據(jù)集(取自http://archive.ics.uci.edu/ml/index.php)進(jìn)行實(shí)驗(yàn),數(shù)據(jù)集均帶有分類屬性。所有實(shí)驗(yàn)均在Windows7、CPU Intel?CoreTMi5-6500、8.00 GB內(nèi)存的個人計(jì)算機(jī)上進(jìn)行,所用編程環(huán)境為Python3.6。實(shí)驗(yàn)分為算法運(yùn)行時間和實(shí)驗(yàn)對比表(近似分類質(zhì)量、J48分類正確率、約簡效用)兩個部分。

使用函數(shù)式u(λΔ)=d(-λΔ+c)b(Δ∈{PP,BP,NP,NN,BN,PN})[30]作為效用函數(shù)式,給定參數(shù)取值范圍d∈[1,10],c∈[1,10],λ∈[0,10]。

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental data sets

4.1 實(shí)驗(yàn)對比表

本文提出的FG-PRAR算法與FG-MUAR算法原始數(shù)據(jù)和屬性約簡后的近似分類質(zhì)量[3]如表3所示。

表3 近似分類質(zhì)量Table 3 Approximate classification quality

FG-PRAR原始數(shù)據(jù)表示FG-PRAR算法中決策表的近似分類質(zhì)量。FG-MUAR原始數(shù)據(jù)表示FG-MUAR算法中決策表的近似分類質(zhì)量。 FG-PRAR算法可以保持所有決策類的正域不變,因此FG-PRAR約簡與FG-PRAR原始數(shù)據(jù)的近似分類質(zhì)量數(shù)值相同。FG-MUAR約簡與FG-MUAR原始數(shù)據(jù)對比,近似分類質(zhì)量發(fā)生改變,原因是FG-MUAR約簡前后會引起決策表正域的改變。近似分類質(zhì)量數(shù)值為0是由于隨機(jī)產(chǎn)生的概率閾值過大,因此劃分出的決策表正域?yàn)榭占?。近似分類質(zhì)量數(shù)值為1是由于隨機(jī)產(chǎn)生的概率閾值過小,導(dǎo)致論域中所有對象均被劃分到?jīng)Q策表正域。

使用Weka軟件中J48分類器并采用十折交叉驗(yàn)證法驗(yàn)證決策表的4種算法屬性約簡后的J48分類正確率。本次實(shí)驗(yàn)使用10次隨機(jī)產(chǎn)生的概率閾值,其平均分類正確率如表4所示。

原始數(shù)據(jù)表示決策表的J48分類正確率。表4中本文所提出的FG-PRAR算法屬性約簡結(jié)果的分類正確率在多數(shù)情況下可以大于等于原始數(shù)據(jù)的分類正確率。本文所提出的FG-PRAR算法的正確分類率均大

表4 J48分類正確率Table 4 Classification accuracy comparision with J48

于文獻(xiàn)[21]中最大期望效用算法(maximum expect utility, MAXEU)和文獻(xiàn)[24]中最小決策損失算法(minimum decision cost, MINDC)的正確分類率,存在兩種原因:1) MAXEU算法和MINDC算法缺乏處理離散型數(shù)據(jù)和混合數(shù)據(jù)的能力,所以要在屬性約簡前對數(shù)據(jù)進(jìn)行預(yù)處理,會對數(shù)據(jù)造成一定的損失,最終對數(shù)據(jù)的分類正確率造成一定的影響;2) MAXEU算法和MINDC算法均未考慮到?jīng)Q策表中不同決策類的差異,沒有為每個決策類生成不同的概率閾值，而是統(tǒng)一采用一致的閾值劃分論域,因此這兩種算法在6個數(shù)據(jù)集上的分類正確率均低于本文提出的FG-PRAR和FG-MUAR算法分類正確率。

FG-MUAR算法保證屬性約簡后不降低原始決策表的效用,約簡應(yīng)該具有比原始決策表更高或者相等的效用,據(jù)決策者對待風(fēng)險的三種主觀態(tài)度,可以將效用函數(shù)分為:當(dāng)b=1時,效用函數(shù)為風(fēng)險中立型(RN)；當(dāng)b>1時,效用函數(shù)為風(fēng)險厭惡型(RA)；當(dāng)b<1時,效用函數(shù)為風(fēng)險喜好型(RP)。FG-MUAR算法在三種風(fēng)險態(tài)度下約簡結(jié)果的效用值如表5所示。

表5 約簡效用Table 5 The utility of decision table and reduct

在三種風(fēng)險態(tài)度下使用的效用函數(shù)參數(shù)不同,因此三種風(fēng)險態(tài)度下的決策表效用不同。FG-MUAR算法的目標(biāo)即為使決策者的效用值最大化,由表5可以得知,FG-MUAR算法在6個數(shù)據(jù)集中約簡結(jié)果的總效用值均大于原始決策表的總效用值,因此約簡結(jié)果有效。對比三種決策態(tài)度中約簡結(jié)果的效用值相差較小,表明三種不同決策態(tài)度中決策者對待決策結(jié)果的滿意程度基本一致。

4.2 算法運(yùn)行時間

不同決策者對待風(fēng)險的決策態(tài)度不同,在決策過程中的決策行為也不完全相同。為分析兩種算法在三種不同決策態(tài)度中的決策效率,比較FG-PRAR和FG-MUAP兩種算法在決策者不同決策態(tài)度中隨著論域變化的運(yùn)行時間。圖1和圖2實(shí)驗(yàn)采取的方式是將每個數(shù)據(jù)集的論域數(shù)目均等分成十份,依次加入一份樣本,比較加入樣本后FG-PRAR算法在三種決策態(tài)度中的運(yùn)行時間,x軸表示樣本份數(shù),y軸表示算法運(yùn)行時間。

圖1 FG-PRAR算法隨論域數(shù)目增加運(yùn)行時間的變化Figure 1 The running time of the FG-PRAR algorithm increases with the sizes of the universe

由圖1可知,隨著樣本數(shù)的增加,三種決策態(tài)度中FG-PRAR算法運(yùn)行時間基本一致,圖1中數(shù)據(jù)集(b)、(d)隨著樣本數(shù)的增加,風(fēng)險中立型的算法運(yùn)行時間沒有嚴(yán)格單調(diào)遞增,是因?yàn)椴煌瑯颖鞠率褂貌煌母怕书撝祫澐值恼蚩赡懿煌?當(dāng)前樣本數(shù)使用的隨機(jī)概率閾值劃分出的正域比前一份樣本數(shù)使用的概率閾值劃分出的正域較小,因此算法運(yùn)行時間略有下降。本文提出的FG-PRAR算法是保持約簡結(jié)果正域與決策表正域一致?？傮w來看,不同決策態(tài)度對于FG-PRAR算法運(yùn)行時間影響較小。

對于FG-MUAR算法,三種決策態(tài)度中樣本數(shù)與算法運(yùn)行時間的關(guān)系如圖2所示。

圖2 FG-MUAR算法隨論域數(shù)目增加運(yùn)行時間的變化Figure 2 The running time of the FG-MUAR algorithm increases with the sizes of the universe

由圖2可知,在決策者不同決策態(tài)度中,隨著論域的增加，運(yùn)行時間曲線的變化并不完全一致,不同決策態(tài)度對于FG-MUAR算法運(yùn)行時間略有影響。FG-MUAR算法計(jì)算正域、負(fù)域和邊界域的全部效用,相對于FG-PRAR算法的運(yùn)行時間更長。圖2數(shù)據(jù)集(b)、(c)、(e)中的三種不同風(fēng)險態(tài)度曲線隨著論域數(shù)目增加,并不是嚴(yán)格單調(diào)遞增,這是由于隨著樣本數(shù)的增加,每個屬性的模糊T-等價關(guān)系表也隨之變化,由此計(jì)算的模糊條件概率可能增加、不變或減少,從而引起效用值的變化,最終影響FG-MUAR算法的運(yùn)行時間。在現(xiàn)實(shí)生活中,決策者的心理滿足程度也可能隨著時間的變化或者事件的改變而發(fā)生變化,圖2曲線的不單調(diào)變化更貼合實(shí)際生活中決策者的決策情況。

5 結(jié)束語

在混合決策信息系統(tǒng)中，本文結(jié)合模糊和效用提出一種新的模糊效用三支決策模型,提高了三支決策模型處理混合數(shù)據(jù)的能力。本文在該模型中提出正域分布保持和最大效用啟發(fā)式屬性約簡算法,實(shí)驗(yàn)表明了兩種算法的有效性。然而效用函數(shù)在決策表屬性約簡過程中并不具有單調(diào)性,兩種算法仍需遍歷刪除冗余屬性求解約簡,尋找三支決策模型中主觀效用與客觀數(shù)據(jù)結(jié)合的單調(diào)啟發(fā)式因子是后續(xù)所要研究的主要內(nèi)容。