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

王文琦，馮琴榮

山西師范大學數學與計算機科學學院，山西 臨汾 041000

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

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

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

1 預備知識

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

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

當αh>βh時，關于(αh,βh)的X的正域，負域，邊界域為

在經典粗糙集及其擴展模型中，許多學者使用上、下近似兩個精確的集合來描述目標集.最優近似是一個與目標集具有最大相似度的可定義集，相較于上、下近似，最優近似可以更好地描述目標概念.

(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]給定一個信息系統S=(U,C,V,f)，對于任意的集合X?U,O(X)∈D(D是可定義集族)，如果O(X)滿足以下條件：

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

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

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

從例1中可以看到序貫三支決策中，最優近似等于該決策過程中某幾個參數對(αh,βh)對應的正域.由最優近似的啟發式算法可知最優近似是在下近似的基礎上添加等價類，也就是說，αh只有變化到某個等價類的包含度時，該等價類才可以加入最優近似中，由此可得使正域與最優近似相同的這些αh值是介于等價類包含度之間的.進而通過大量例子，我們得到以下結論.

在序貫三支決策中，邊界域中的一些等價類在閾值變化的過程中會逐步添加到負域中去，而且對象集的負域相當于對象集補集的正域.所以，我們可以把研究序貫三支決策中變化的負域等價為研究對象集補集的正域.

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

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

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

從表2中可以看出，當我們對等價類的包含度按數值大小排序后，相鄰大小的兩個包含度構成一個區間，處在同一區間的αh、βh分別對應的正、負域是相同的，而且它們的并集就是論域.

命題3 給定信息系統S=(U,C,V,f)及一個動態閾值序列(α,β)l={(α1,β1),(α2,β2),...,(αl,βl)},αh≥βh(h=1,2,...,l)在序貫三支決策中，X?U,U/C={e1,e2,...,em},X相對于等價類ei(i=1,2,...,m)的包含度為P(X|ei)，不妨假設，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 給定信息系統S=(U,C,V,f)及一個動態閾值序列(α,β)l={(α1,β1),(α2,β2),...,(αl,β)},αh≥βh(h=1,2,...,l)在序貫三支決策中，X?U,U/C={e1,e2,...,em},X相對于等價類ei(i=1,2,...,m)的包含度為P(X|ei)，不妨假設，P(X|e1)

在序貫三支決策中，閾值參數αh,βh∈[0,1]，αh,βh可以組成無限多個閾值對，我們研究發現閾值參數可以區間化，而且每個區間的端點值可以取為等價類的包含度.這樣就可以把無限多可能的閾值對離散化為有限多個閾值參數區間，從而對應有限多個正域和負域.這一發現對序貫三支決策閾值對的選取具有很大的指導意義.因此，通過計算等價類的包含度來選取αh,βh的值，可以大大減少不必要的計算.

我們將序貫三支決策中不同的閾值區間與不同正、負域的對應關系總結如下.

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

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

在序貫三支決策過程中，隨著參數的變化，目的是縮小邊界域，擴大正域和負域.因此，當我們選擇閾值對(αh,βh)時，可以在等價類的包含度構造的區間中任選一個值，這樣可以大大減少運算量，提高序貫三支決策的效率.

3 結論與建議

本文主要研究了序貫三支決策閾值對的選取問題.我們首先發現了序貫三支決策過程和尋找最優近似的過程很類似，并進一步發現了序貫三支決策的閾值參數可以進行區間化，在同一區間中選擇不同的閾值參數得到的決策結果是相同的.因此，本文的主要工作是把序貫三支決策中閾值對的無限多可能取值減少為有限個可能取值，這對序貫三支決策的理論和應用都有重要意義.