序貫三支決策閾值選取策略研究

王文琦，馮琴榮

山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西 臨汾 041000

三支決策作為一種典型的粒計(jì)算方法，其研究可分為靜態(tài)和動(dòng)態(tài)兩部分.根據(jù)三支決策的基本思路，如果信息不足或證據(jù)不足，就會(huì)推遲決策，直到出現(xiàn)更多、更充分的信息可以用于進(jìn)一步?jīng)Q策.因此，從本質(zhì)上講，三支決策是一種動(dòng)態(tài)的決策.Yao[1]提出的序貫三支決策模型是動(dòng)態(tài)三支決策的典型代表，該模型的關(guān)鍵是借助新加入的信息，逐步將難以決策的部分轉(zhuǎn)化為接受或拒絕決策.近幾年，序貫三支決策作為一種有效、靈活的工具，受到了學(xué)者們的廣泛關(guān)注[2～6].

在經(jīng)典粗糙集及其擴(kuò)展模型中，許多學(xué)者用一對(duì)上、下近似來(lái)表示對(duì)象集，但是，下近似縮小了對(duì)象集的研究范圍，上近似擴(kuò)大了對(duì)象集的研究范圍.為了更準(zhǔn)確地描述對(duì)象集，張等人[7]提出利用模糊割集構(gòu)造對(duì)象集的近似集，找到了一個(gè)相對(duì)較好的近似集R0.5(X)，并研究了它的一些性質(zhì).張等人[8]在文獻(xiàn)[7]的基礎(chǔ)上提出了一般近似Rλ(X)所滿足的運(yùn)算規(guī)則,找到了能夠比上、下近似更好的描述X的λ成立的區(qū)間，稱之為最優(yōu)近似,并討論了Rλ(X)作為X的最優(yōu)近似所滿足的條件.Janicki R等[9]研究了不同相似度指標(biāo)下最優(yōu)近似的計(jì)算,并給出了相對(duì)應(yīng)的算法.李[10]給出了經(jīng)典粗糙集模型下求最優(yōu)近似的啟發(fā)式算法.王[11]基于極大一致塊，設(shè)計(jì)了一種不完備信息系統(tǒng)下求最優(yōu)近似的算法.高[12]研究了最優(yōu)近似的矩陣計(jì)算方法及其增量更新.

我們注意到序貫三支決策過(guò)程與求最優(yōu)近似的過(guò)程之間有著很大的相似性，受此啟發(fā)，本文研究了序貫三支決策閾值對(duì)的選取問(wèn)題并給出了一些有效建議，使得在序貫三支決策過(guò)程中省掉大量不必要的計(jì)算，提高了序貫三支決策的效率.

1 預(yù)備知識(shí)

在本節(jié)中，我們簡(jiǎn)要回顧粗糙集，上、下近似等基本概念.

定義1[13](粗糙集) 給定一個(gè)信息系統(tǒng)S=(U,A,V,f)，?B?A，?X?U，RB是U上的等價(jià)關(guān)系，X關(guān)于RB的上、下近似集分別定義如下：

當(dāng)αh>βh時(shí)，關(guān)于(αh,βh)的X的正域，負(fù)域，邊界域?yàn)?/p>

在經(jīng)典粗糙集及其擴(kuò)展模型中，許多學(xué)者使用上、下近似兩個(gè)精確的集合來(lái)描述目標(biāo)集.最優(yōu)近似是一個(gè)與目標(biāo)集具有最大相似度的可定義集，相較于上、下近似，最優(yōu)近似可以更好地描述目標(biāo)概念.

(1)0≤S(A,B)≤1;

(2)S(A,B)=S(B,A);

(3)S(A,B)=1?A=B;S(A,B)=0?A∩B=?,

則稱S(A,B)是集合A和B的相似度.

定義4[8]給定一個(gè)信息系統(tǒng)S=(U,C,V,f)，對(duì)于任意的集合X?U,O(X)∈D(D是可定義集族)，如果O(X)滿足以下條件：

則稱O(X)是X的最優(yōu)近似.

2 序貫三支決策的閾值選取

表1 正、負(fù)域隨閾值對(duì)(αh,βh)的變化情況Tab.1 Change of positive and negative region with threshold pairs (αh,βh)

從例1中可以看到序貫三支決策中，最優(yōu)近似等于該決策過(guò)程中某幾個(gè)參數(shù)對(duì)(αh,βh)對(duì)應(yīng)的正域.由最優(yōu)近似的啟發(fā)式算法可知最優(yōu)近似是在下近似的基礎(chǔ)上添加等價(jià)類，也就是說(shuō)，αh只有變化到某個(gè)等價(jià)類的包含度時(shí)，該等價(jià)類才可以加入最優(yōu)近似中，由此可得使正域與最優(yōu)近似相同的這些αh值是介于等價(jià)類包含度之間的.進(jìn)而通過(guò)大量例子，我們得到以下結(jié)論.

在序貫三支決策中，邊界域中的一些等價(jià)類在閾值變化的過(guò)程中會(huì)逐步添加到負(fù)域中去，而且對(duì)象集的負(fù)域相當(dāng)于對(duì)象集補(bǔ)集的正域.所以，我們可以把研究序貫三支決策中變化的負(fù)域等價(jià)為研究對(duì)象集補(bǔ)集的正域.

由以上分析可知,隨著αh,βh的變化，序貫三支決策正、負(fù)域可能不會(huì)變化，而且在Li[15]中，已經(jīng)發(fā)現(xiàn)當(dāng)a,b∈(ri-1,ri]，POSa(Y)=POSb(Y)，但文獻(xiàn)中并沒(méi)有給出如何確定ri-1和ri的值.結(jié)合最優(yōu)近似的啟發(fā)式算法，我們發(fā)現(xiàn)ri-1，ri的值可以取為等價(jià)類的包含度.接下來(lái)我們用例子來(lái)具體說(shuō)明.

例2 (續(xù)例1)在序貫三支決策中，針對(duì)不同的閾值對(duì)(αh,βh)，相應(yīng)的正、負(fù)域是如何變化的.

表2 正、負(fù)域隨閾值對(duì)(αh,βh)的變化情況Tab.2 Change of positive and negative region with threshold pairs (αh,βh)

從表2中可以看出，當(dāng)我們對(duì)等價(jià)類的包含度按數(shù)值大小排序后，相鄰大小的兩個(gè)包含度構(gòu)成一個(gè)區(qū)間，處在同一區(qū)間的αh、βh分別對(duì)應(yīng)的正、負(fù)域是相同的，而且它們的并集就是論域.

命題3 給定信息系統(tǒng)S=(U,C,V,f)及一個(gè)動(dòng)態(tài)閾值序列(α,β)l={(α1,β1),(α2,β2),...,(αl,βl)},αh≥βh(h=1,2,...,l)在序貫三支決策中，X?U,U/C={e1,e2,...,em},X相對(duì)于等價(jià)類ei(i=1,2,...,m)的包含度為P(X|ei)，不妨假設(shè)，P(X|e1)

(1)?(αp,βp),(αq,βq)∈(α,β)l,若αp、αq∈(P(X|ei-1),P(X|ei)],則POS(αp、βp)(X)=POS(αq、βq)(X).

(2)?(αp,βp),(αq,βq)∈(α,β)l,若βp,βq∈[P(X|ei-1),P(X|ei)),則NEG(αp、βp)(X)=NEG(αq、βq)(X).

命題4 給定信息系統(tǒng)S=(U,C,V,f)及一個(gè)動(dòng)態(tài)閾值序列(α,β)l={(α1,β1),(α2,β2),...,(αl,β)},αh≥βh(h=1,2,...,l)在序貫三支決策中，X?U,U/C={e1,e2,...,em},X相對(duì)于等價(jià)類ei(i=1,2,...,m)的包含度為P(X|ei)，不妨假設(shè)，P(X|e1)

在序貫三支決策中，閾值參數(shù)αh,βh∈[0,1]，αh,βh可以組成無(wú)限多個(gè)閾值對(duì)，我們研究發(fā)現(xiàn)閾值參數(shù)可以區(qū)間化，而且每個(gè)區(qū)間的端點(diǎn)值可以取為等價(jià)類的包含度.這樣就可以把無(wú)限多可能的閾值對(duì)離散化為有限多個(gè)閾值參數(shù)區(qū)間，從而對(duì)應(yīng)有限多個(gè)正域和負(fù)域.這一發(fā)現(xiàn)對(duì)序貫三支決策閾值對(duì)的選取具有很大的指導(dǎo)意義.因此，通過(guò)計(jì)算等價(jià)類的包含度來(lái)選取αh,βh的值，可以大大減少不必要的計(jì)算.

我們將序貫三支決策中不同的閾值區(qū)間與不同正、負(fù)域的對(duì)應(yīng)關(guān)系總結(jié)如下.

命題5 給定信息系統(tǒng)S=(U,C,V,f)及動(dòng)態(tài)閾值序列(α,β)l={(α1,β1),(α2,β2),...,(αl,βl)},αh≥βh(h=1,2,...,l)在序貫三支決策中，X?U,U/C={e1,e2,...,em},X相對(duì)于等價(jià)類ei(i=1,2,...,m)的包含度為P(X|ei)，不妨假設(shè)，P(X|e1)

命題6 給定信息系統(tǒng)S=(U,C,V,f)及動(dòng)態(tài)閾值序列(α,β)l={(α1,β1),(α2,β2),...,(αl,βl)},αh≥βh(h=1,2,...,l)在序貫三支決策中，X?U,U/C={e1,e2,...,em},X相對(duì)于等價(jià)類ei(i=1,2,...,m)的包含度為P(X|ei)，不妨假設(shè)，P(X|e1)

在序貫三支決策過(guò)程中，隨著參數(shù)的變化，目的是縮小邊界域，擴(kuò)大正域和負(fù)域.因此，當(dāng)我們選擇閾值對(duì)(αh,βh)時(shí)，可以在等價(jià)類的包含度構(gòu)造的區(qū)間中任選一個(gè)值，這樣可以大大減少運(yùn)算量，提高序貫三支決策的效率.

3 結(jié)論與建議

本文主要研究了序貫三支決策閾值對(duì)的選取問(wèn)題.我們首先發(fā)現(xiàn)了序貫三支決策過(guò)程和尋找最優(yōu)近似的過(guò)程很類似，并進(jìn)一步發(fā)現(xiàn)了序貫三支決策的閾值參數(shù)可以進(jìn)行區(qū)間化，在同一區(qū)間中選擇不同的閾值參數(shù)得到的決策結(jié)果是相同的.因此，本文的主要工作是把序貫三支決策中閾值對(duì)的無(wú)限多可能取值減少為有限個(gè)可能取值，這對(duì)序貫三支決策的理論和應(yīng)用都有重要意義.