孟超,余建坤(云南財經(jīng)大學(xué) 信息學(xué)院,昆明 650221)

?

三支決策與決策粗糙集融合模型①

孟超,余建坤
(云南財經(jīng)大學(xué) 信息學(xué)院,昆明 650221)

摘 要:Paw lak粗糙集模型沒有對正域、邊界域和負域賦予語義,不能進行再決策,而三支決策對邊界域賦予了新的語義,可以對邊界域做出進一步刻畫,對于邊界域的進一步劃分,依據(jù)屬性的重要性,使?jié)M足條件的樣本劃入再決策域,不滿足條件的樣本繼續(xù)保留在邊界域中,降低了邊界域樣本處理的失誤率.本文在對概率粗糙集模型、三支決策粗糙集的理論、貝葉斯理論的決策過程和決策粗糙集模型進行研究的基礎(chǔ)上,提出了一種三支決策與決策粗糙集融合模型,與Paw lak-三支決策模型相比,其劃分損失更小,處理結(jié)果更優(yōu).該模型運用三支決策理論對決策粗糙集的邊界域賦予延遲決策的語義,對于延遲決策再運用三支決策理論進行迭代操作,對邊界域樣本進一步處理.在迭代的過程中,依據(jù)屬性的重要程度將屬性排序,從而客觀的得到迭代過程中每次優(yōu)先依據(jù)哪個屬性進行劃分.實驗結(jié)果表明,該模型比單一運用決策粗糙集模型進行決策代價小,三支決策通過迭代對邊界域處理的正確率有所提高,這為準(zhǔn)確決策提供了一種新的方法.

關(guān)鍵詞:三支決策; 決策粗糙集; 邊界域樣本處理

粗糙集理論是由波蘭學(xué)者Z.Paw lak 在1982年提出的[1],它是一種能夠處理不完整性和不確定性的新型數(shù)學(xué)工具,能有效地處理諸如不精確、不一致和不完整等各種不完備的信息,目前,該理論已在眾多領(lǐng)域取得較好的應(yīng)用.傳統(tǒng)的Paw lak理論通過運用等價關(guān)系將論域區(qū)分成多個等價類,引入上近似、下近似等概念來描述知識的不確定性,通過這些等價關(guān)系,論域被劃分成正域、邊界域和負域三個不相交的類,然而,實際應(yīng)用中,這樣的劃分過于嚴(yán)格,將無效的屬性直接剔除,劃分結(jié)果代價較高.

就此問題,Paw lak,Wong和Ziarko提出了0.5-概率粗糙集模型[3],Ziarko提出了變精度粗糙集模型[2],Paw lak和Skowron提出了粗糙隸屬函數(shù)的概念[4],Skowron和Stepaniuk等人提出了參數(shù)化粗糙集模型[5],Slezak提出了貝葉斯粗糙集模型[6]等,這些模型都是用兩個閾值a、b來劃分正域、負域和邊界域的,但是閾值的選取都需要人為主觀的確定.Yao,Wong提出了決策粗糙集模型[7,8],描述了在貝葉斯期望風(fēng)險最小時閾值a、b如何自動獲取.

其派生出的三支決策思想賦予了粗糙集一種新的語義,將邊界域作為延遲決策從而可以進行再決策.粗糙集是直接剔除無用屬性,而三支決策是選取最重要的屬性作為決策依據(jù),決策代價更小.這種模型在對于邊界域樣本處理上,還需要相關(guān)知識的補充,使得邊界域樣本不能有效的作為決策的正確依據(jù).

本文提出的三支決策融合決策粗糙集模型,將邊界域中的樣本依據(jù)屬性的重要程度進行劃分,從而客觀的提高邊界域樣本處理的正確率.本文在對概率粗糙集模型、三支決策粗糙集理論、貝葉斯理論的決策過程和決策粗糙集模型進行研究的基礎(chǔ)上,提出了三支決策融合決策粗糙集模型,該模型將三支決策理論與決策粗糙集相融合,首先運用決策粗糙集模型對整個論域進行第一次劃分,分別得到正域、邊界域、負域; 再將邊界域作為延遲決策,運用三支決策理論進行第二次劃分,把每個屬性的重要性作為劃分依據(jù);迭代使用三支決策理論,將重要度次之的屬性作為劃分依據(jù),直至延遲決策域盡可能的轉(zhuǎn)化成可決策樣本.這種新的模型有效減少決策規(guī)則的代價損失,并為客觀劃分論域提供了客觀的依據(jù),減少失誤決策.本文采用汽車評估數(shù)據(jù)進行驗證,對該數(shù)據(jù)集6種屬性的1728個對象進行分類,從實驗結(jié)果可以看出,這種新的三支決策融合決策粗糙集模型與決策粗糙集模型相比,代價損失更低,劃分依據(jù)不需要主觀的人為設(shè)定,結(jié)果更客觀貼近實際.這對于制造廠商在生產(chǎn)何種車型,保養(yǎng)費用高低,車門數(shù)量選擇,承載人數(shù)選擇,安全系數(shù)等方面的決策提供了重要的依據(jù),驗證了該模型在解決實際問題中,具有更精確的分類效果.關(guān)鍵詞庫的結(jié)合大大提高了信息抽取算法的準(zhǔn)確性和通用性,基于Web信息抽取的混合交通出行方案生成與表示系統(tǒng)的成功實驗也證明了本文提出的Web信息抽取算法的實用性.

1　決策粗糙集理論

決策粗糙集[3]是基于貝葉斯決策思想的,是一種具有合理語義解釋的概率粗糙集.通過考慮在不同狀態(tài)下采取不同行動的損失或代價,將論域進行劃分.

1.1概率粗糙集模型

相在實際應(yīng)用中,我們將知識和屬性集放入一個決策表(一種重要的知識表達系統(tǒng))中.一個決策表描述了所有對象以及它們的條件屬性和決策屬性.

定義1.設(shè)S=(U,A,V,f)是一個決策表,U是論域,A是屬性集,A=C∪D ,C∩D =φ,V是值域,f是一個映射函數(shù),C是條件屬性集,D是決策屬性集.

定義兩個對象x和y是等價的,只有當(dāng)它們在R中具有相同的屬性值.稱這個等價關(guān)系是U上的一個劃分.

設(shè)U中的一個子集為X,上近似、下近似可以定義為[1]:

其中,POS(C)、NEG(C)、BND(C)被稱為C的正域、負域和邊界域.正域是由完全確定屬于某個集合的等價類所構(gòu)成; 負域是由肯定不屬于某個集合的所有的等價類構(gòu)成; 邊界域是由可能屬于某個集合的等價類構(gòu)成.

但是,Paw lak模型中進入正域的必須是完全確定的規(guī)則,這就需要引進概率粗糙集的相關(guān)理論.

概率粗糙集模型[9]是通過引入一對閾值α、β來劃分正域、負域和邊界域的.其取值的不同將產(chǎn)生不同的分類結(jié)果.

定義2.設(shè)S=(U,A,V,f)是一個信息表,其中0≤β≤α≤1,XU,則定義基于α、β的上近似、下近似為[10]:

在經(jīng)典的粗糙集理論中,僅將閾值的取值取為0和1.因此,給出合理的α、β的取值,是十分重要的.將論語劃分成3個區(qū)域,通過引入貝葉斯決策理論,來降低決策風(fēng)險,于是,決策粗糙集相繼被提出[11].

1.2貝葉斯理論決策過程

定義3.給定對象x ,設(shè)一個信息表為S=(U,A,V,f),d={w1,w2,...,wm}是x的m個狀態(tài)集,j={a1,a2,...an}是X的m個行動集.Pr(wi|x)記做X在wi狀態(tài)下的條件概率.λ(αj|wi)記做X在wi狀態(tài)下執(zhí)行aj動作的損失.則對于x的相關(guān)的期望損失[13],也就是條件風(fēng)險可以記做:

根據(jù)以上描述,我們可以求出每個動作的損失函數(shù),并獲得在不同狀態(tài)下采取所有動作的期望損失,按照風(fēng)險最小的動作進行劃分.

1.3決策粗糙集模型

在Paw lak粗糙集理論中,由于實際問題都受到噪聲等因素的影響,而決策粗糙集可以較好的解決這個問題,以下對決策粗糙集模型的理論內(nèi)容進行描述.

為了描述清楚,利用兩個狀態(tài)集和三個決策集來描述決策過程[12].設(shè)狀態(tài)集δ={X,-X}分別表示屬于狀態(tài)集X和不屬于狀態(tài)集X ,設(shè)行動集j={aP,aB,aN}分別表示接受事件的行動、延遲決策事件的行動和拒絕執(zhí)行事件的行動.由于采取不同的行動會產(chǎn)生相應(yīng)的損失,用λPP,λBP,λNP分別表示在aP,aB,aN行動下的損失.由此,三種行動的相應(yīng)期望損失可以描述為:

由貝葉斯公式,通過選擇損失最小的行動可以得到以下3個決策規(guī)則:

(P): 當(dāng)R(aP|[x])≤R(aB|[x])且R(aP|[x])≤R(aN|[x])時,執(zhí)行決策x∈POS (C);

(B): 當(dāng)R(aB|[x])≤R(aP|[x])且R(aB|[x])∈R(aN|[x])時,執(zhí)行決策x∈BND(C);

(N): 當(dāng)R(aN|[x])≤R(aP|[x])且R(aN|[x])≤R(aB|[x])時,執(zhí)行決策x∈NEG(C);

其中,它們損失代價的大小,可以看出有:

λPP≤λBP≤λNP,λNN≤λBN≤λPN,而且Pr(X|[x]R)+Pr(-X|[x]R)=1,再令:

則上述規(guī)則可以描述為:

當(dāng)Pr(X|[x]R)≥λ且Pr(X|[x]R)≥α?xí)r,執(zhí)行決策x∈POS(C);

當(dāng)Pr(X|[x]R)≥β且Pr(X|[x]R)≤α?xí)r,執(zhí)行決策x∈BND(C);

當(dāng)Pr(X|[x]R)≤β且Pr(X|[x]R)≤λ時,執(zhí)行決策x∈NEG(C);

我們加入一個條件在損失函數(shù)中:(λPN-λNN)·(λNP-λBP)＞(λBP-λPP)·(λBN-λNN),通過證明即有α>λ>β.只用α,β來定義決策規(guī)則,可得:

(P): 當(dāng)R(C|[x])≥α?xí)r,執(zhí)行決策x∈POS(C);

(B): 當(dāng)β＜R(C|[x])＜α?xí)r,執(zhí)行決策x∈BND(C); (7)

(N): 當(dāng)R(C|[x])≤β時,執(zhí)行決策x∈NEG(C);

決策粗糙集不但引入了概率統(tǒng)計的概念,而且可以用一種易于理解的計算方法來確定閾值.因此,決策粗糙集在解決數(shù)據(jù)分類問題中具有更重要的可操作價值.

2　三支決策模型語義

在經(jīng)典的Paw lak粗糙集理論中,由于正域是只包含完全確定的規(guī)則,邊界域包含的是可能性規(guī)則,導(dǎo)致了負域恒為空從而失去了實際意義.但是,按照決策粗糙集的理論,通過兩個閾值α、β將論域分成3個區(qū)域,分別是決策正域、決策負域和延遲決策邊界域.在語義上來說,這樣劃分出來的三個區(qū)域是根據(jù)三個確定的規(guī)則得來的,具有更完整的語義.

三支決策粗糙集的語義[13]可以描述為: 當(dāng)[x]R中X發(fā)生的可能性大于α?xí)r,就把[x]R劃分到正域中并立即執(zhí)行這個決策; 當(dāng)[x]R在X發(fā)生的可能性小于β,就把[x]R劃分到負域中并拒絕執(zhí)行這個決策; 當(dāng)[x]在X發(fā)生的可能性在a和b之間,就把[x]R劃分到邊界域中并延遲做出決策.

Yao提出了一種新的決策語義[14],即把三支決策粗糙集中的絕對閾值函數(shù)用相對閾值函數(shù)取代.為選取適當(dāng)?shù)拈撝礱、b提供了依據(jù).

3　三支決策融合決策粗糙集模型

決策粗糙集理論依據(jù)貝葉斯期望損失來確定閾值α、β,可以非常合理、客觀的對論域進行劃分.將三支決策賦予決策粗糙集新的語義,可以對邊界域樣本進行再處理.為了提高邊界域樣本處理的正確性,將對延遲決策域運用三支決策理論進一步劃分.

其基本思想是,將論域運用決策粗糙集理論進行劃分,得到正域、邊界域和負域,正域和負域中的規(guī)則放入最終的二支決策中.運用三支決策理論進行迭代操作.由于第一次劃分是非?？陀^的,閾值α、β可以合理的通過貝葉斯決策確定出來; 第二次為了避免用主觀經(jīng)驗和試湊的方式確定閾值,本文運用屬性的重要性對邊界域進行在處理.

基于文獻[12],從犯錯損失的大小角度,證明在條件:

(C1)、(C2)同時成立的情況下,三支決策融合決策粗糙集模型決策方式比Paw lak-三支決策損失更小,在條件(C1)、(C2)下更優(yōu).

證明: 假設(shè)

新模型與Paw lak-三支決策方式在（0,β]和[α,1)區(qū)間內(nèi)不同,新模型在這兩個區(qū)間內(nèi)的總損失為:

Cost1=λNP·a4+λPN·b4,Paw lak-三支決策在這兩個區(qū)間內(nèi)的總損失為: Cost2=λBP·(a2+ a4)+λBN·(b2+ b4).兩者總損失相減:Cost2- Cost1≥0.

因此,Paw lak-三支決策方式比三支決策融合決策粗糙集模型決策方式總損失更大,新模型在條件(C1),(C2)下更優(yōu),更合理.

3.1三支決策與決策粗糙集融合模型結(jié)構(gòu)

本首先依據(jù)決策粗糙集理論,在等價關(guān)系R下,利用閾值a、b,對數(shù)據(jù)集C進行第一次劃分:

(P): 當(dāng)R(C|[x])≥α?xí)r,執(zhí)行決策x∈POS(α,β)(C);

(B): 當(dāng)β＜R(C|[x])＜α?xí)r,執(zhí)行決策

(N): 當(dāng)R(C|[x])≤β時,執(zhí)行決策x∈NEG(α,β)(C);

定義4. 屬性的重要程度.C是條件屬性集,D是決策屬性集.C的子集對于D的重要程度定義為:

當(dāng)C'={a} 時,屬性a∈C對于D的重要程度為:

將BND(α,β)(C)作為延遲決策域,利用三支決策理論對延遲決策進行迭代操作,在每次的迭代操作過程中,屬性的選取依據(jù)屬性的重要程度,選擇屬性中比重最大的屬性作為依據(jù).屬性A1對于決策屬性集D的重要程度定義為:

屬性粒度信息選擇如圖2.先依據(jù)重要性最大的屬性A1對決策域進行劃分,將劃分結(jié)果中的正域和負域用來支持決策,結(jié)果中的邊界域繼續(xù)作為延遲決策域,依據(jù)屬性A2進行劃分,迭代的重復(fù)運用三支決策進行劃分,直至不能再進行劃分為止.

圖2　屬性粒度信息選擇

3.2三支決策與決策粗糙集融合模型算法

給定一個信息表S=(U,A,V,f),U是論域,A是屬性集,A=C∪D,C∩D=φ,V是值域,f是一個映射函數(shù),C是條件屬性集,D是決策屬性集.則三支決策融合決策粗糙集算法TmD(Three-way Decision mix Decision-Theoretic rough set)如下:

輸入: 決策表S=(U,A,V,f),待劃分對象x

輸出: 正域P ,負域N ,最終延遲決策域B

Step1: P={},B={},P’={},B’={};

Step2: fori= 1，...，m ;

Step3: 由(5),(6)式確定閾值a、b;

Step4: 由(8)式,遍歷x并將其劃分到P={},B={},N={}中;

Step5: 由(9)式,按照重要程度將所有屬性Ai從大到小排列,依次選取Ai作為劃分依據(jù)對B進行劃分,將不滿足條件的樣本繼續(xù)保留在延遲決策域B中;

Step6: 當(dāng)所有屬性迭代完成后,三支決策理論將延遲決策域中所有對象劃分到正域、負域中,或者延遲決策域已經(jīng)不能再進行劃分的時候,得到最終結(jié)果正域P,負域N和邊界域B;

TmD算法首先將全體對象進行劃分,需要計算每個對象被劃分到3個域中的期望損失,然后按照最小的期望損失將論域劃分成3個部分,復(fù)雜度為O(3 n).之后每次在對延遲決策域進行劃分,復(fù)雜度同樣是O(3 n),有t個待決策屬性,復(fù)雜度為O(3 tn).

4　實驗結(jié)果與分析

根據(jù)以上所述,本文提出的TmD模型可以降低決策代價,提高最終二支決策的正確性.為了證明這一點,我們采用了一個對比試驗來說明.該實驗的數(shù)據(jù)來自于UCI數(shù)據(jù)庫(http:.archive.ics.uci.edu/ml/datasets/ Car+Evaluation).實驗采用汽車評估的數(shù)據(jù),共計1728個對象,每條數(shù)據(jù)有6個屬性.基于粗糙集工具Rosetta完成,因為Rosetta所能處理的信息系統(tǒng)的條件屬性的個數(shù)有限,所以本文選用了條件屬性的個數(shù)較少的CarEvaluation數(shù)據(jù)集.

實驗環(huán)境為64位Window 7操作系統(tǒng),Intel 3.20GHz主頻,8.00 GB內(nèi)存.首先將數(shù)據(jù)在Excel中進行分列,導(dǎo)入到工具軟件Rosetta中.由于6個屬性都是離散的數(shù)據(jù),只需將數(shù)據(jù)補全即可.然后將數(shù)據(jù)進行屬性約簡,結(jié)果如圖3.生成規(guī)則Generate rules結(jié)果如圖4.迭代運用三支決策模型,遍歷本題庫求得每一個屬性的比重值,最后調(diào)用Approximate decision class,按照屬性比重的排序依次選取屬性作為決策屬性進行劃分,最終結(jié)果統(tǒng)計如表1.

圖3　屬性約簡結(jié)果

圖4　生成規(guī)則結(jié)果

表1　實驗結(jié)果對比

根據(jù)結(jié)果可以得出,屬性的重要程度依次為價格、發(fā)動機性能、后備箱、安全性、車門數(shù)和乘車人數(shù).因為市場上私家車的可乘人數(shù)基本是固定的,乘車人數(shù)又決定了車門數(shù),所以這兩個屬性重要程度就很低.TmD模型可以有效將粗糙集模型中的邊界域進行再決策,降低了決策代價,客觀的降低了失誤決策的幾率.為生產(chǎn)廠家來生產(chǎn)何種車型和配置提供了重要的決策依據(jù).

由決策粗糙集與TmD模型實驗結(jié)果對比表中可以看出,TmD模型有效的將延遲決策域進行再決策.這種新的模型可以進一步減少決策代價,并提高決策的準(zhǔn)確性,為最終的二支決策提供了有力的支持,這樣對于決策者做出正確的決策來說更為有利.但是再對邊界域進行再處理的時候,仍不能完全劃分成二支決策,需要補充更多的相關(guān)知識才可以進行劃分.目前對邊界域樣本有兩種處理方案,一種是對邊界域樣本進行全部處理,提出了萬有引力原則、 距邊界最近原則、距中心最近原則3種方法,這些方法雖然對邊界域樣本可以完全劃分,但對邊界域樣本處理的正確率較低; 另一種是對邊界域樣本進行部分處理,即作進一步的劃分邊界域樣本滿足一定的條件,這樣邊界域中剩余的樣本是不滿足特定條件的,提高了邊界域樣本處理的正確率,但不能對邊界域進行完全處理.因此對于三支決策融合決策粗糙集模型還需做進一步研究.

5　結(jié)語

本文針對Paw lak粗糙集理論決策代價較高,其派生出的三支決策理對于邊界域樣本處理的正確率較低問題,在對概率粗糙集模型、三支決策粗糙集的理論、貝葉斯理論的決策過程和決策粗糙集模型進行研究的基礎(chǔ)上,提出了三支決策與決策粗糙集融合模型,實驗結(jié)果表明,這種新的三支決策與決策粗糙集融合模型與傳統(tǒng)的決策粗糙集模型相比,延遲決策域樣本處理的正確率提高,決策代價降低,說明該方法是可行的,對拓展決策粗糙集理論的應(yīng)用也有一定的參考價值.

參考文獻

1Pawlak Z.Rough sets.International Journal of Coputer and Information Sciences,1982,11(5): 341–356.

2Ziarko W.Variable precision rough set model.Journal of Computer and System Sciences,1993,46(1): 39–59.

3Paw lak Z,Wong SKM,Ziarko W.Rough sets: Probabilistic versus deterministic approach.International Journal of Man-Machine Studies,1988,29(1): 81–95.

4Paw lak S.Rough Membership Functions.New York: John Wiley and Sons,1994: 251–271.

5Skow Ron S.Tolerance approximation spaces.Fundamental Information,1996,27(2): 245–253.

6Slezak.Rough sets and bayes factor.Lecture Notes in Computer Science,2005: 314–324.

7Yao YY,Wong.A decision theoretic framework for approximating concepts.Inter.Journal of Man-Machine Studies,1992,37(6): 793–809.

8Yao YY.Decision-theoretic rough set models.Lecture Notes in Artificial Intelligence,2007,4481: 1–12.

9Yao YY.Probabilistic approaches to rough sets.Expert Systems,2003,20(5): 287–297.

10李健,常太華,楊婷婷.變精度粗糙集模型屬性約簡分析.計算機工程與應(yīng)用,2012,48(13):130–132.

11Yao YY,Zhao Y.Attribute reduction in decision theoretic rough set model.Information Sciences,2008,49(2): 255–271.

12劉盾,姚一豫,李天瑞.三支決策粗糙集.計算機科學(xué),2011,38(1):246–250.

13李華雄,劉盾,周獻中.決策粗糙集模型研究綜述.重慶郵電大學(xué)學(xué)報(自然科學(xué)版),2010,22(5):624–630.

14Yao YY.Three-way decisions with probabilistic rough sets.Information Sciences,2010,180(3): 341–356.

15Baader F,Horrocks I,Sattler U.Description logics as ontology lanuages for the semantic web.Lecture Notes in Artificial Intelligence,2003.

Merging Three-Way Decisions with Decision-Theoretic Rough Sets

MENG Chao,YU Jian-Kun
(College of Information,Yunnan University of Finance and Economics,Kunming 650221,China)

Abstract:Paw lak rough set model was lacking in giving semantic to positive regions,negative regions and boundary regions.The boundary could not make decision again.But three-way decisions gave a new semantic to boundary regions and we can deal with samples in boundary regions.Based on importance of attribute,samples which meet the conditions were delimit to decision region and others would be maintained in the boundary regions in order to reduce false positives when deal with samples in boundary regions.Based on the study of probabilistic rough set model,three-way decisions-theoretic rough set,Bayesian decision-making process and decisions-theoretic rough set model,this paper presents Three-way Decision mix Decision-Theoretic rough set model(TmD).Compared with the new model with Paw lak-three way decisions model,the loss of division of this model is smaller and the result is more reasonable.This model gives the boundary regions semantic which is delaying decisions.Using three-way decisions makes iterative operation for delaying decisions.In the process of iteration,attributes will be ordered based on the importance of the attribute,thus objectively get the attribute of priority being used in the process of iteration.Experimental results show that the model has a smaller decision cost than only using decision-theoretic rough sets and three-way decisions with iterative operation have a higher accuracy when deal with samples in boundary regions.This paper provides a new method for accurate decision-making.

Key words:three-way decisions; decision-theoretic rough sets; dealing with samples in boundary regions

基金項目:①云南省高校商務(wù)智能科技創(chuàng)新團隊

收稿時間:2015-08-05;收到修改稿時間:2015-09-28