擴展的三支決策理論

王玲玲,呂王勇,2*

(1.四川師范大學 數學與軟件科學學院,四川 成都 610066;2.可視化計算與虛擬現實四川省重點實驗室,四川 成都 610066)

擴展的三支決策理論

王玲玲1,呂王勇1,2*

(1.四川師范大學 數學與軟件科學學院,四川 成都 610066;2.可視化計算與虛擬現實四川省重點實驗室,四川 成都 610066)

三支決策理論只能將決策對象劃分到接受域、拒絕域和邊界域3類,不能處理把決策對象劃分為更多類的情況,因此,立足于傳統的三支決策理論,對其進行推廣,提出擴展的三支決策理論,結合貝葉斯理論,以決策的平均損失最小為原則,給出擴展的三支決策理論詳細推導過程,使經典的三支決策理論成為特例.

擴展的三支決策; 貝葉斯理論; 三支決策;閥值; 評價函數

1 預備知識

三支決策理論是對傳統的二支決策理論的發展,它在接受和拒絕2種選擇的基礎上引入延遲決策,使最終的決策結果保留待判類,從而避免直接接受或拒絕帶來的風險,也更符合人類直觀的信息處理模式,具有很強的現實意義.

Yao.Y.Y[1]在2012年給出三支決策理論的框架性描述;田海龍等[2]提出基于三支決策的中文微博觀點句識別研究;張聰等[3]提出一種三支決策軟增量聚類算法;薛占熬等[4]提出基于三支決策理論的條件屬性權重構造方法;徐久成等[5]提出基于三支決策的支持向量機增量學習方法;杜麗娜等[6]給出基于三支決策風險最小化的風險投資評估應用研究;王磊等[7]給出基于主題與三支決策的文本情感分析;周哲等[8]提出一種基于動態詞典和三支決策的情感分析方法;黃順亮等[9]提出客戶細分的三支決策方法.此外,還有謝騁等[10]提出的基于三支決策粗糙集的視頻異常行為檢測;李建林等[11]提出的多階段三支決策垃圾短信過濾模型;張燕平等[12]提出的基于CCA的代價敏感三支決策模型.可以看到,三支決策理論的發展側重于應用方面的多樣化,而缺乏對其理論的推廣.

三支決策的思想和方法簡單有效,在解決實際問題時具有很強的應用價值,但是,該理論只能將對象最終決策到接受域、拒絕域和待判域這3類,無法處理需要將對象決策為更多類的問題,因此,在傳統三支決策理論的基礎上進行擴展,三支決策理論的思想能夠應用在將對象劃分為更多類的問題上,不僅保持了三支決策理論應用在對象細分上的優越性,也突破了三支決策理論只能將對象劃分為2類及一個待判類的局限性,擴大其應用范圍.

2 三支決策理論

首先給出對象的價值信息表T=(U,B,{Vb|b∈B},{Ib|b∈B}),其中,U是所需要研究的全部對象組成的有窮集合,在客觀上劃分為2個子集C和Cc,且U=C∪Cc.B是研究對象所有屬性組成的集合,這里具體指對象的評價指標組成的集合,Vb是各屬性所有取值組成的非空集合.Ib:U→Vb是信息函數,將U中每一個對象的某個屬性b映射到Vb上,定義為每個對象在各個指標上的取值,即Ib(x)∈Vb.

定義U上的一個等價關系R,若Ib(x)=Ib(y),則xRy.所有滿足關系R的對象組成等價類[x],則由等價類[x]、閥值(α,β)和評價函數P(C|[x])將全集U劃分為3個兩兩不交的集合,分別表示為接受域POS(C)、待判域BND(C)和拒絕域NEG(C):

(1)

(2)

(3)

這3個概率區間兩兩不交,且其并集就是有限集合U.

由于將某對象劃分到不同區域所需要付出的代價不同,因此,給出形如表1的一張三支決策代價表[13](見表1).

表1 三支決策分類代價表Table 1 The loss table of three-way decision

(4)

則每個對象的決策代價函數為:

(5)

(6)

(7)

RPOS(x)、RNEG(x)、RBND(x)分別表示對象x劃分到POS(C)、NEG(C)、BND(C)所需要付出的總代價,則閥值對(α,β)[14]可以表示為

至此閥值對(α,β)已經可以根據損失函數λxy確定,至于損失函數λxy,直接根據專家評分法可以得到.下面就評價函數P(C|[x])的求解方法[15],借助貝葉斯理論有

(9)

該計算公式中P([x])的求解比較困難,因此選擇求(9)式的近似解

(10)

易知

(11)

其中

最后結合研究對象的評價函數P(C|[x])以及閥值對(α,β),可以將全體研究對象劃分到三支決策的3個域中.

3 擴展的三支決策理論

第一支:rg1={x∈U|[x]?C1},

第二支:rg2={x∈U|[x]?C2},

第三支:rg3={x∈U|[x]?C3},

第四支:rg4={x∈U|[x]∩C1≠φ且[x]C1,[x]∩C2≠φ,且[x]C2,[x]∩C3≠φ,且[x]C3}.

引入評價函數P(Ci|[x]),將上面4個區域換一種描述形式,其中,P(Ci|[x])描述等價類[x]中的對象x屬于集合Ci的概率,則P(Ci|[x])(i=1,2,3)定義為

(12)

其中|·|表示集合的基數.(12)式可表示為:

第一支:rg1={x∈U|P(C1|[x]=1),

第二支:rg2={x∈U|P(C2|[x]=1)},

第三支:rg3={x∈U|P(C3|[x]=1)},

第四支:rg4={x∈U|0

可以看到,雖然借助極端值0和1可以將全集分成互不相交的4個區域,但當0

由于已經定義C1、C2、C3分別表示高價值、較高價值和低價值對象所屬的類別,那么,P(Ci|[x]),i=1,2,3的取值會受到對象各個指標數據的影響,本身存在大小關系,因此,給出如下的擴展三支決策表達形式:

第一支:rg1={x∈U|P(C1|[x])≥α1},

第二支:rg2={x∈U|α3≤P(C2|[x])≤α2},

第三支:rg3={x∈U|P(C3|[x])≤α4},

易知閥值滿足條件0≤α4<α3<α2<α1≤1.

至此,給出四支決策模型,接下來確定評價函數P(Ci|[x])(i=1,2,3)和閥值(α1,α2,α3,α4).

由于將某對象劃分到不同區域所需要付出的代價不同,因此給出一張三狀態四分類結果的代價表(見表2).

表2 擴展的三支決策分類代價表Table 2 The loss table of extended three-way decision

λxy表示采取不同決策時所需要付出的代價,如λ1,1′表示將屬于集合C1的對象劃分為rg1需要付出的代價,且決策代價大小滿足

劃分為rgh的某對象x的代價函數,就是該對象屬于集合C1的概率P(C1|[x])與該對象屬于集合C1又判斷為rgh的代價值λh,1′的乘積,加上該對象屬于集合C2的概率P(C2|[x])與該對象屬于集合C2又被判斷為rgh的代價值λh,2′的乘積,再加上該對象屬于集合C3的概率P(C3|[x])與該對象屬于集合C3又被判斷為rgh的代價值λh,3′的乘積.函數表達式為

(14)

由于總是選擇決策代價最小的行動方案為最優方案,因此決策規則可以描述為:

若Rrg1(x)≤Rrg2(x),且Rrg1(x)≤Rrg3(x),Rrg1(x)≤Rrg4(x),則x∈rg1;

若Rrg2(x)≤Rrg1(x),且Rrg2(x)≤Rrg3(x),Rrg2(x)≤Rrg4(x),則x∈rg2;

若Rrg3(x)≤Rrg1(x),且Rrg3(x)≤Rrg2(x),Rrg3(x)≤Rrg4(x),則x∈rg3;

若Rrg4(x)≤Rrg1(x),且Rrg4(x)≤Rrg2(x),Rrg4(x)≤Rrg3(x),則x∈rg4.

由此可以算出P(C1|[x])、P(C2|[x])、P(C3|[x])滿足條件:

下面就結合前面的決策代價函數關系式,給出4個閥值的表達式.

根據P(C1|[x])來確定閥值組中最大的那個閥值α1.同理,通過次大的條件概率值P(C2|[x])確定閥值α2、α3,通過最小條件概率P(C3|[x])確定閥值α4,則閥值α1、α2、α3、α4表示為

(18)

接下來確定評價函數P(Ci|[x]),i=1,2,3.

借助貝葉斯理論有

(19)

該計算公式中P([x])的求解比較困難,因此選擇先求解

(20)

(21)

先求解出O(P(Ci|[x])),然后根據(21)式最終確定P(Ci|[x])的值,下面分析(20)式的求解.

[x]描述為該等價類中對象在屬性(b1,b2,…,bn)下所對應的取值(v1,v2,…,vn),且Ibk(x)=vk,其中,n為指標的個數,vk為等價類[x]中對象x在第k個指標下的取值.再借助樸素貝葉斯獨立性假設,即假設對任意的k≠l,有vk與vl相互獨立,則有

(22)

其中

最后再根據每個對象的條件概率值P(C|[x])和閾值(α1,α2,α3,α4)實現決策.

4 結束語

立足于傳統的三支決策理論,對傳統三支決策在決策中只能把對象劃分到接受域、拒絕域這2類和待判類的局限性進行改進,提出擴展的三支決策理論,借助貝葉斯理論,以決策的平均損失代價最小為原則,并給出決策代價表,對擴展三支決策理論的三類決策規則進行了合適的描述,從而確定決策中最為重要的4個閥值.接下來還研究了在擴展的三支決策理論下,評價函數的求解方法,最終借助閥值和評價函數成功地將對象劃分為更多類,使傳統的三支決策理論成為特例,將三支決策的思想應用到更多的領域.

致謝 可視化計算與虛擬現實四川省重點實驗室項目 (KJ201410)對本文給予了資助,謹致謝意.

[1] YAO Y Y.An outline of a theory of three-way decisions[C]//Proceedings of the RSCTC 2012.Berlin:Springer-Varlag,2012:1-17.

[2] 田海龍,朱艷輝,梁韜,等.基于三支決策的中文微博觀點句識別研究[J].山東大學學報(理學版),2014,49(8):58-65.

[3] 張聰,于洪.一種三支決策軟增量聚類算法[J].山東大學學報(理學版),2014,49(8):40-47.

[4] 薛占熬,朱泰隆,薛天宇,等.基于三支決策理論的條件屬性權重構造方法[J].計算機科學,2015,42(8):265-268.

[5] 徐久成,劉洋洋,杜麗娜,等.基于三支決策的支持向量機增量學習方法[J].計算機科學,2015,42(6):82-87.

[6] 杜麗娜,徐久成,劉洋洋,等.基于三支決策風險最小化的風險投資評估應用研究[J].山東大學學報(理學版),2014,49(8):66-72.

[7] 王磊,黃河笑,吳兵,等.基于主題與三支決策的文本情感分析[J].計算機科學,2015,42(6):93-96.

[8] 周哲,商琳.一種基于動態詞典和三支決策的情感分析方法[J].山東大學學報(工學版),2015,45(1):19-23.

[9] 黃順亮,李建林,王琦.客戶細分的三支決策方法[J].計算機科學與探索,2014,8(6):743-750.

[10] 謝騁,商琳.基于三支決策粗糙集的視頻異常行為檢測[J].南京大學學報(自然科學),2013,49(4):475-482.

[11] 李建林,黃順亮.多階段三支決策垃圾短信過濾模型[J].計算機科學與探索,2014,8(2):226-233.

[12] 張燕平,鄒慧錦,趙姝.基于CCA的代價敏感三支決策模型[J].南京大學學報(自然科學),2015,51(2):447-452.

[13] 黃順亮,王琦.基于三支決策理論的對象細分方法[J].計算機應用,2014,34(1):244-248.

[14] 劉盾,姚一豫,李天瑞.三支決策粗糙集[J].計算機科學,2011,38(1):246-250.

[15] YAO Y Y,ZHOU B.Naive bayesian rough sets[C]//Proceedings of the 5th International Conference on Rough Sets and Knowledge Technology,6401.Berlin:Springer-Verlag,2010:719-726.

2010 MSC：68T37

(編輯 鄭月蓉)

Extension of Three-way Decision Theory

WANG Lingling1,LYU Wangyong1,2

(1.CollegeofMathematicsandSoftwareScience,SichuanNormalUniversity,Chengdu610066,Sichuan;2.VisualComputingandVirtualRealityKeyLaboratoryofSichuanProvince,Chengdu610066,Sichuan)

In the traditional three-way decision theory,the objects can only be divided into 3 regions: acceptance,rejection or deferment.Therefore the theory can not be applied when the objects must be divided into more than 3 regions.In this paper,an extended theory is proposed,in which,combining the Bayes theory,taking the average minimum loss criterion as principle,the detailed derivation of the extended theory is presented so that the classic three-way dicision theory becomes a special case.

extension-three-way decision; the Bayesian theory; three-way decision; the threshold; evaluation function

2015-10-29

國家自然科學青年基金(11601357)和四川省教育廳自然科學重點基金(15ZA0030)

TP181

A

1001-8395(2017)02-0262-05

10.3969/j.issn.1001-8395.2017.02.019

*通信作者簡介：呂王勇(1979—),女,副教授,主要從事隨機信號處理的研究,E-mail:lvwangy@163.com