三支決策理論的擴展與仿真實驗

王玲玲，呂王勇，高艷萍，蔡林芝

（1.四川師范大學 數(shù)學與軟件科學學院；2.可視化計算與虛擬現(xiàn)實四川省重點實驗室，成都 610068）

0 引言

三支決策是一種在不確定或不完整信息條件下的決策方式，主要用于當可用信息不足時，做出待判從而進一步觀察的決策。自三支決策理論提出以來[1]，三支決策理論迅速發(fā)展，并取得了眾多成果。如針對三支決策中閥值對的確定進行的研究，賈修一等[2,3]提出的一種自適應求三支決策中決策閥值的算法，及一種求三支決策閾值的模擬退火算法；陳剛等[4]給出了求三支決策最優(yōu)閥值的新算法。另外，很多學者從三支決策的理論擴展方面進行了深入研究，張艷萍等[5]研究了基于CCA的代價敏感三支決策模型，薛占熬等[6]進行的基于概率圖的三支決策模型研究，李麗紅等[7]提出了三支決策中不承諾決策的轉(zhuǎn)化代價與風險控制。三支決策理論在應用方面也取得了很多成果，如李建林等[8]研究出了多階段三支決策垃圾短信過濾模型，謝騁等[9]給出了基于三支決策粗糙集的視頻異常行為檢測模型，黃順亮等[10]提出了基于三支決策理論的客戶細分方法，徐久成等[11]研究的基于三支決策的支持向量機增量學習方法等。

目前三支決策理論只能將對象最終劃分到接受域、拒絕域和暫時不能判定的待判域，在處理需要將對象劃分到更多區(qū)域的問題面前就無能為力了。本文在傳統(tǒng)三支決策理論的基礎上進行擴展，使其能夠應用于將對象劃分到任意多區(qū)域的問題上。

1 三支決策理論

其中，|·|表示集合的基數(shù)。

首先給出對象的價值信息表 T=(U，B，{Vb|b∈B}，{Ib|b∈B})，其中，U是所需要研究的全部對象組成的有窮集合；B是研究對象的所有屬性組成的集合，這里具體指的是對象的評價指標組成的集合；Vb是各屬性所有取值組成的非空集合；Ib:U→Vb是信息函數(shù)，它將U中每一個對象的某個屬性b映射到Vb上，定義了每個對象在各個指標上的取值，即，Ib(x)∈Vb。

對于全集U，在客觀上可以將其劃分為兩個子集C和Cc，分別表示滿足條件的對象組成的集合和不滿足條件的對象所組成的集合，且有U=C∪CC。

定義U上的一個等價關系R，若有Ib(x)=Ib(y)，則x和y等價，記為xRy。所有滿足等價關系R的對象可以組成等價類[x]。引入評價函數(shù)P(C|[x])，表示將等價類[x]中對象x劃分到集合C的概率，由評價函數(shù)P(C|[x])和一對閥值(α，β)可以將全集U劃分為三個兩兩不交的區(qū)域，分別表示為正域POS(C)、邊界域BND(C)和負域NEG(C)，且有 U=POS(α，β)(C)∪ BND(α，β)(C)∪NEG(α，β)(C)：

由于將對象x劃分到不同區(qū)域所需要付出的代價不同，記λap、λrp、λdp分別表示當對象 x屬于集合C時，被劃分到POS(C)、NEG(C)、BND(C)所需要付出的代價，λapˉ、λrpˉ、λdpˉ分別表示當對象 x 屬于集合CC時，被劃分到POS(C)、NEG(C)、BND(C)所需要付出的代價。給出形如表1的一張三支決策代價表[10]。

表1 三支決策代價表

在表1給出的六個代價中，λap、λap表示正確分類的代價，λrp、λapˉ表示錯誤分類的代價，λdp、λdpˉ表示將對象劃分到邊界域的代價，因此決策代價值有如下關系成立：0≤ λap≤ λdp≤ λrp,0 ≤ λrpˉ≤ λdpˉ≤ λapˉ。

下面給出對象x的決策代價函數(shù)：

RPOS(x)、RNEG(x)、RBND(x)分別表示對象x被劃分到POS(C)、NEG(C)、BND(C)所需要付出的總代價。

選擇決策損失最小的行動方案為最優(yōu)方案，因此決策規(guī)則可以描述為：

若 RPOS(x)≤RNEG(x)，且 RPOS(x)≤RBND(x)，則 x∈POS(C)

若 RNEG(x)≤RPOS(x)，且 RNEG(x)≤RBND(x)，則 x∈NEG(C)

若 RBND(x)≤RPOS(x)，且 RBND(x)≤RNEG(x)，則 x∈BND(C)

則閥值 (α，β)可以表示為[12]：

下面就給出評價函數(shù)P(C|[x])的求解方法[13]。

借助貝葉斯理論,P(C|[x])可以如下計算：

式（3）中P([x])不易直接求得，因此借助公式P(C|[x])=O(P(C|[x]))·P(CC|[x]) 求解 P(C|[x])，為求解 P(C|[x])，先求解O(P(C|[x]))：

又P(CC|[x])=1-P(C|[x])，因此：

至此評價函數(shù)和閥值都已經(jīng)確定，則可以將對象劃分到正域、負域和邊界域中。

2 N支決策理論

第i支：

第N支：

引入評價函數(shù)P(Ci|[x])，定義為：

進一步將式（6）用如下形式表示：

第i支：

第N支：

rgN={x∈U|0＜P(Ci|[x])＜1，i=1，2，…，N-1} （7）

從上面公式可以看到，雖然借助極端值0和1可以將全集分成互不相交的N個區(qū)域，但當0＜P(Ci|[x])＜1時，P(Ci|[x])的具體取值大小在分類中卻并沒有發(fā)揮作用，而且概率取1的可能性太小，并沒有很好地將所有客戶劃分開來，因此本文提出用閥值 (α0，α`1，α2，…，α2(N-1)-1)來代替公式中的0和1，（7）式可以表示為如下形式：

第i支：

第N支：

至此已經(jīng)給出了N支決策模型，接下來就是評價函數(shù) P(Ci|[x])(i=1，2，…，N-1) 和 閥值 (α1，α2，…，α2(N-1)-1) 的確定。

由于將對象x劃分到不同區(qū)域所需要付出的代價不同，設λj，i表示將屬于集合Ci的對象劃分到rgj的代價，如，λ1，N-1表示將屬于集合CN-1的對象劃分到rg1的代價。因此給出形如表2的一張N個分類結(jié)果N-1個狀態(tài)的決策代價表。

表2 N支決策代價表

劃分為rgj的對象x的代價函數(shù)就是該對象屬于集合Ci的概率P(Ci|[x])與該對象屬于集合Ci又被劃分為rgj的代價值 λj，i(i=1，2，…，N-1)的乘積的累加之和。

則對象x被劃分到rgj的決策代價函數(shù)為：

由于總是選擇決策損失最小的行動方案為最優(yōu)方案，因此決策規(guī)則可以描述為：

若對?j，有：

成立，則 x∈rgj。

此決策過程的實際意義是：當采取某種決策動作所帶來的風險代價不超過其他N-1種決策動作所帶來的風險時，就采取該決策動作，表現(xiàn)形式為將對象劃分到相應區(qū)域。

根據(jù)式（10）解得 P(Ci|[x])(i=1，2，…，N-1)滿足的條件：

其中當 i=r時，λd，i-λj，i=0 。

由P(C1|[x])的值來確定α1的取值，由P(C2|[x])的值來確定α2，α3的取值，依此類推，由 P(CN-1|[x])的值來確定α2(N-1)-2，α2(N-1)-1的取值，下面是閥值 α1，α2，…， α2(N-1)-1的表達式：

其中，當i=1時，α2i-2=α0=1；當 i=N-1時，α2i-1=α2(N-1)-1=1。

閥值確定后，下面確定評價函數(shù)P(Ci|[x])，i=1,2,…，N-1。

借助公式（5），可以求得P(Ci|[x])。由于其中，P(C)為先驗概率，且

下面就分析式（11）中P([x]|Ci)和P([x]|)的求解。

[x]在這里描述為對象集合在屬性 (b1，b2，…，bn)下所對應的取值 (v1，v2，…，vn)，且 Ibk(x)=vk，其中，n 為指標的個數(shù)，vk為等價類[x]中某對象x在第k個指標下的取值。

再借助樸素貝葉斯獨立性假設，即假設對任意的k≠l有vk與vl相互獨立，有如下公式成立：

將式（12）代入式（11）即可求得O(P(Ci|[x]))，從而由式（5）可以解得 P(Ci|[x])。

至此，評價函數(shù)P(Ci|[x])就最終確定了。

3 仿真實驗

檢驗N支決策理論的有效性和K-均值聚類方法進行對比，主要通過對比此兩種分類結(jié)果誤判率的大小來最終驗證N支決策模型分類方法的有效性。

主要用誤判率的大小來檢驗N支決策理論的有效性。選取鳶尾花的150個數(shù)據(jù)[14]進行擴展三支決策理論分類的仿真實驗。

3.1 仿真步驟及相關理論推導

此組數(shù)據(jù)收集了150朵鳶尾花的4個屬性萼片長、萼片寬、花瓣長、花瓣寬的取值，序號為1～150，也給出了先驗信息：序號為1～50的鳶尾花分為第一類，51～100的鳶尾花為第二類，101～150的鳶尾花為第三類，則每類的先驗概率為接下來就依N支決策模型的步驟對這150朵鳶尾花進行分類。首先將150朵鳶尾花數(shù)據(jù)標準化、離散化，再將具有相同屬性值的花劃分到同一類，至此獲得此組數(shù)據(jù)的眾多等價類；接下來獲得分類的決策代價表，以及根據(jù)決策規(guī)則獲得的閾值；最后求每一等價類下的評價函數(shù)p(Ci|[x])，由第三部分知此評價函數(shù)的求解公式如下：

且有：

令先驗概率 P(C1)、P(C2)、P(C3)分別為 π1、π2、π3，化簡可得：

同理可得到 p(C2|[x])、p(C3|[x])的表達式。

3.2 數(shù)據(jù)仿真結(jié)果

首先將此150個數(shù)據(jù)進行標準化和離散化處理，進一步以所有對象的屬性為依據(jù)，劃分為以下18個等價類（見表3）。

然后給出分類所需要的決策代價，獲得如下決策代價表，見表4。

借助上一部分 p(Ci|[x])的求解方法對每一等價類的概率進行求解，結(jié)果見表5。

將每個對象的概率值代入決策代價函數(shù)式中，可以得到此N支決策的閾值，而后可以將對象做如下劃分，見表6。其中括號中表示與原始分類有差異的四個對象對應的序號。對于以上四個對象，本文進一步分析：

表3 等價類的劃分

表4 決策代價表

表5 每個等價類的概率值

表6 分類結(jié)果對比

由于原始分類時每類都有類中心，那么若對象離該類類中心最近，就會被劃分到該類別中去，對以上四個有差異的對象，有如下結(jié)論，見表7。

表7 個別分類有差異的對象的進一步分析

其中b1表示萼片長，b2表示萼片寬，b3表示花瓣長，b4表示花瓣寬；d1表示對象到第一類類中心的距離，d2表示對象到第二類類中心的距離，d3表示對象到第三類類中心的距離。

可以看到，將對象107和120劃分到第二類更合理，從而說明此N支決策理論誤判率為1.3%。

而在用K-均值快速聚類法時，同樣可以對與給定的標準有偏差的14個對象與三個類的類中心的距離進行比較，可以得到此判斷方法的誤判率為6%，因此可以看到N支決策理論分類效果更好，此方法更有效。

4 總結(jié)

本文立足于傳統(tǒng)的三支決策理論，對傳統(tǒng)的三支決策理論在決策中只能把對象劃分為正域、負域和邊界域三個區(qū)域的局限性進行改進，提出了N支決策理論，它借助貝葉斯理論和決策代價表，以決策的平均損失代價最小為原則，對N支決策理論的決策規(guī)則進行了合理的定義，從而確定了N支決策中最為重要的閾值。另外還給出了評價函數(shù)的求解方法，并給出了詳細的推導過程，從而借助閾值和評價函數(shù)就能將對象劃分為N類。本文最后借助N支決策模型對鳶尾花的分類問題進行分析驗證，并與K-均值快速聚類法分類結(jié)果進行比較，說明了本文提出的N支決策理論的有效性。N支決策理論使傳統(tǒng)的三支決策理論成為特例，拓寬了三支決策理論的應用領域，使三支決策理論能夠應用到更多的實際問題中。