不完備混合決策粗糙集特定類多目標屬性約簡

蔡艷婧，程 實，王 強

(1.南通大學 信息科學技術學院，江蘇 南通 226009； 2.江蘇商貿職業學院 電子與信息學院，江蘇 南通 226009)

0 引 言

決策粗糙集[1]是著名學者Yao在傳統粗糙集理論上的重要推廣，目前決策粗糙集成果已應用于數據分類[2,3]、數據聚類[4]、圖像處理[5,6]以及模式識別[7]等領域。屬性約簡是粗糙集理論的核心研究內容[8]，針對決策粗糙集的屬性約簡問題，目前學者們進行了廣泛深入的研究。Yao等在文獻[9]中最早研究了決策粗糙集的屬性約簡問題。Ma等[10]基于保持決策正區域提出了決策粗糙集的正區域屬性約簡算法，Gao等[11]在決策粗糙集中提出了最大決策熵的屬性約簡。在另一方面，基于代價敏感的角度，Jia等[12]在決策粗糙集中提出了最小決策代價屬性約簡。楊志榮等[13]基于多代價的策略在決策粗糙集模型上提出了一種改進的最小代價屬性約簡。陳婉清等[14]聯合決策代價和分類質量，在決策粗糙集下提出了一種新的屬性約簡?？傊梢钥闯龌跊Q策代價的屬性約簡是目前決策粗糙集的研究熱點[15-18]。

然而，實際應用中的環境是復雜多樣的，首先很多信息系統都是不完備混合型的，即數值型屬性和符號型屬性并存，然后在某些情形下，我們只需要關注信息系統中某個類或者某幾個類[19,20]，并且在進行最小化決策代價屬性約簡的同時，可能也希望約簡結果的測試代價盡量小[21，22]。例如在醫療診斷信息系統中，我們往往都只關注患病的樣本病例，然后選擇決策代價小的病理指標降低誤診的風險，但是某些指標的采集會產生高昂的費用，這時就需要將測試代價考慮進來，因此針對信息系統的特定類別，同時考慮決策代價和測試代價具有很高的現實意義。

在粗糙集理論中，測試代價[21,22]也是學者們重點關注的內容，目前已有多種測試代價的屬性約簡算法被提出。在本文，將提出一種不完備混合決策粗糙集模型，該模型進一步擴大了決策粗糙集的應用范圍。接著在不完備混合決策粗糙集的基礎上，定義了特定類別的決策代價，并將決策代價和屬性集的測試代價同時作為屬性約簡的優化目標，提出一種特定類的多目標代價敏感啟發式屬性約簡算法，該算法得到的屬性約簡可以使決策代價和測試代價綜合最小。實驗結果表明，所提算法具有更高的代價敏感屬性約簡性能，同時屬性約簡結果針對的是特定的決策類，不同的類可以得到不同的約簡結果，因此所提算法具有更高的實用性能。

1 基本理論

在本節將簡要介紹決策粗糙集的基本內容，為后文的展開提供鋪墊。

定義1[8]在粗糙集中，數據集表示成決策信息系統S=(U,AT=C∪D) 的形式，其中U稱為信息系統的論域，AT稱為信息系統的屬性全集，并且C和D分別稱為條件屬性集和決策屬性集。給定論域中的對象?x∈U在屬性a∈AT下的屬性值表示為a(x)，若信息系統包含缺失的屬性值，該信息系統又稱為不完備信息系統。

在粗糙集理論中，對于屬性子集A?AT在信息系統下確定的等價關系[8]EA定義為

EA={(x,y)∈U×U|?a∈A,a(x)=a(y)}

等價關系EA可以在信息系統論域U上誘導出一個劃分U/EA，其中劃分結果中的每個成員稱之為等價類，對象x∈U在EA上的等價類表示為[x]A={y∈U|(x,y)∈EA}。

利用等價類作為基本運算單位，Pawlak提出了經典的粗糙集模型[8]。隨著近幾十年來粗糙集理論的研究和發展，學者們對傳統的粗糙集模型進行了不斷的擴展和改進，其中Yao等學者根據貝葉斯決策理論，將概率粗糙集進行推廣，提出了決策粗糙集模型[1]，并且在該模型下誘導了三支決策理論，使得決策粗糙集成為了當今粗糙集領域最為活躍的研究分支。

表1 決策代價矩陣

表1中，代價值λPP,λBP和λNP表示對象x∈U處于狀態X時采取aP,aB和aN這3種動作所產生的代價，代價值λPN,λBN和λNN表示對象x∈U處于狀態Xc時采取aP,aB和aN這3種動作所產生的代價。

因此，對于信息系統?x∈U可以得到采取3種動作決策時所產生的預期代價

CostP(x)=λPP·P(X|[x])+λPN·P(Xc|[x])
CostB(x)=λBP·P(X|[x])+λBN·P(Xc|[x])
CostN(x)=λNP·P(X|[x])+λNN·P(Xc|[x])

基于最小化決策代價原則，可以得到：

(1)若CostP(x)≤CostB(x) 且CostP(x)≤CostN(x)，則x∈POS(X)。

(2)若CostB(x)≤CostP(x) 且CostB(x)≤CostN(x)，則x∈BUN(X)。

(3)若CostN(x)≤CostP(x) 且CostN(x)≤CostB(x)，則x∈NEG(X)。

將上述的3個決策規則進行進一步推導，可以得到

使得

(1)當P(X|[x])≥α且P(X|[x])≥γ，那么x∈POS(X)；

(2)當P(X|[x])≤α且P(X|[x])≥β，那么x∈BUN(X)；

(3)當P(X|[x])≤β且P(X|[x])≤γ，那么x∈NEG(X)。

定義2[1]設決策信息系統S=(U,AT=C∪D)，屬性子集A?C確定的等價關系為EA。對于屬性子集X?U關于等價關系EA的決策粗糙集下近似和上近似分別定義為

同時對象集X?U關于等價關系EA的決策粗糙集正區域、邊界域和負區域分別定義為

特別地，決策屬性集D在論域U上誘導的決策類劃分為U/D={D1,D2,…,Dm}，決策屬性集D關于等價關系EA的決策粗糙集正區域、邊界域和負區域分別定義為

2 不完備混合決策粗糙集模型

Yao提出的決策粗糙集建立在離散完備的信息系統下。近年來，Li等[18]學者在數值型的信息系統下提出了鄰域決策粗糙集，進一步地擴大了決策粗糙集模型的適用范圍。然而實際應用中的數據類型是復雜多樣的，其中數值型屬性和符號型屬性并存的不完備混合型信息系統便是最為常見的一種。本節將在不完備混合型信息系統下對決策粗糙集模型進行推廣，提出一種更為廣義化的模型。

在文獻[23]中，Zhao等學者在不完備混合型的信息系統下構造了鄰域容差關系，并且提出了對應的粗糙集模型，該模型在處理不完備混合型數據方法表現出了良好的性能，因此本節將采用Zhao等學者提出的鄰域容差關系，用于不完備混合型決策粗糙集模型的構造。

類似于經典的決策粗糙集，對于不完備混合型信息系統中的對象?x∈U，采取3種動作決策時所產生的預期代價為

基于最小化決策代價原則，可以得到

即

且

即

且

即

且

記

那么有

(1)當P(X|nδ(x))≥α且P(X|nδ(x))≥γ時，那么x∈POS(X)；

(2)當P(X|nδ(x))≤α且P(X|nδ(x))≥β時，那么x∈BUN(X)；

(3)當P(X|nδ(x))≤β且P(X|nδ(x))≤γ時，那么x∈NEG(X)。

通常表1中的代價滿足λPP≤λBP<λNP且λNN≤λBN<λPN，此外，Yao[1]進一步假設代價滿足

(λNP-λBP)·(λPN-λBN)>(λBP-λPP)·(λBN-λNN)

那么可以得到關系0≤β<γ<α≤1。因此

(1)當P(X|nδ(x))≥α時,那么x∈POS(X)；

(2)當P(X|nδ(x))≤α且P(X|nδ(x))≥β時,那么x∈BUN(X)；

(3)當P(X|nδ(x))≤β時,那么x∈NEG(X)。

根據如上推導，接下來可以得到不完備混合型決策信息系統下的決策粗糙集模型。

3 基于特定類的多目標屬性約簡算法

決策粗糙集是建立在代價基礎上的粗糙集模型，因此基于代價敏感的屬性約簡是其研究的重點。在決策粗糙集模型中，目前學者們主要關注于決策代價的研究，而對于測試代價的研究比較少，然而在實際應用中，很多情形需要同時考慮這兩方面的代價。

另一方面，傳統的屬性約簡方法是全局的，即屬性約簡的結果是針對信息系統所有決策類的最優屬性子集，然而實際應用中，可能往往只關注某個具體的類別，例如在醫療診斷中只關注患病的樣本。因此針對這一問題，Yao和Zhang[19]提出了基于特定類屬性約簡的概念，進一步提高了屬性約簡的實用性。

綜合考慮以上兩個問題，本節將在不完備混合型決策粗糙集的基礎上，提出一種特定類別的多目標最小化代價屬性約簡算法，該算法以信息系統特定類別為視角，通過同時最小化決策代價和測試代價兩個代價目標來設計屬性約簡算法。

3.1 基于特定類的決策代價

表2 決策類Dt的代價矩陣

同時信息系統中對象決策為Dt的決策總代價表示為

定義5是通過特定決策類的角度來分析信息系統的決策代價，并且特定決策類的代價矩陣可以單獨地進行指定，即信息系統中每個決策類可以設定不同的決策代價。例如在醫療診斷中，對于患病的病人，可以設定更高的誤分類代價，而對于正常的人可以設定較低的誤分類代價，另外對于不同嚴重程度的疾病，也可以設定不同程度的代價。因此基于類別設置不同代價矩陣具有更好的適用性和靈活性。

3.2 基于特定類的測試代價

在決策粗糙集模型中，對象分類入不同的決策結果將會產生相應的代價，并且不同的屬性具有不同的代價結果。例如對于醫療診斷，判斷病人的病情需要采集病人的各項生理指標，而采集的這些指標需要付出相應的金錢代價，并且對于不同的生理指標，其金錢代價也是不同的，因此這時測試代價的問題就要考慮進來。

在文獻[24]中，Min等學者提出了多種最小化測試代價的屬性約簡算法?；贛in等學者的方法，本節這里進行延伸和拓展，提出不完備混合型信息系統的測試代價敏感模型。

定義6表明，當信息系統中每個屬性的測試代價都為0時，則測試代價決策信息系統就退化為傳統的不完備混合型信息系統。

3.3 基于特定類的多目標代價敏感屬性約簡

實際應用中可能需要同時考慮信息系統的決策代價和測試代價，因此需要將這兩種代價進行綜合。本節中，我們將這兩種代價都作為屬性約簡的目標，提出一種基于特定類的多目標代價敏感屬性約簡算法。

由于多目標的屬性約簡需要同時考慮多個目標的情形，這往往很難保證屬性約簡結果使得每個目標都是最優的，因此需要對每個目標的結果進行權衡，即多目標的結果應該使整體達到最優。為此，這里定義了一個關于決策代價和測試代價的多目標綜合代價函數。

其中，wdc≥0,wtc≥0,并且wdc+wtc=1，它們分別代表了決策代價和測試代價占據綜合代價的比重。

根據定義7給出的綜合代價，接下來可以得到特定類的多目標代價敏感屬性約簡的定義，具體如定義8所示。

尋找屬性約簡是一個NP難問題，而啟發式搜索是求解屬性約簡的一種有效方法[9，10,18,23]，其中啟發式搜索的關鍵是構造屬性約簡的啟發式函數。根據定義7所示的多目標綜合代價，我們可以進一步誘導出對應的啟發式函數，即屬性重要度函數。

根據定義9中屬性重要度函數的定義，進行啟發式搜索的屬性約簡算法如算法1所示。

算法1：不完備混合型決策粗糙集的特定類多目標代價敏感屬性約簡算法。

輸入：不完備混合型測試代價決策信息系統為S=(U,AT=C∪D,tc)，鄰域半徑為δ，特定決策類Dt∈U/D，Dt的決策代價矩陣。

輸出：類別Dt的決策代價和測試代價多目標屬性約簡red。

步驟1 初始化red←?。

步驟6 返回最終屬性約簡結果red。

4 實驗分析

在本節將通過實驗來驗證所提出算法的有效性。

4.1 實驗數據集

表3所示的是參與實驗的6個UCI數據集[25]，在這6個數據集中包含了4個混合類型、2個數值型和1個符號型的數據集，部分數據集為完備型的，實驗前隨機選擇5%的屬性值進行刪除，同時為了消除數值型數據量綱的影響，進行實驗前需要將所有數值型屬性進行標準化處理，本實驗標準化為[0,1]區間。

表3 實驗數據集

4.2 參數選取

通過圖1可以發現，隨著鄰域半徑的逐漸增大，信息系統各個決策類的綜合代價先減少后增大，即過大和過小的鄰域半徑不能夠得到較好的實驗結果。綜合圖1的每個子圖的實驗結果，可以得出當鄰域半徑δ介于0.15至0.21區間時，得到綜合代價最小。在接下來的實驗部分，我們選擇δ=0.18進行實驗。

4.3 實驗比較

接下來將本文所提出的算法與文獻[25]的屬性約簡算法進行實驗比較，來驗證本文算法的有效性。

在本小節進行實驗前，本文算法的參數選取類似于4.2節，即每個決策類按照特定關系選取對應的決策代價，屬性的測試代價按照區間[1,20]進行隨機選取等。對于參與比較的算法，是一種基于不完備離散型信息系統的全局最小代價屬性約簡，因此進行實驗時需要將表3中的數值型屬性進行離散化處理，同時所有決策類選擇統一的決策代價，這里也隨機進行選取。

對于本文所提出的多目標屬性約簡與決策代價的屬性約簡，分別讓這兩種算法進行相應的屬性約簡，然后根據屬性約簡結果，我們分別計算出每個決策類的決策代價、測試代價以及綜合代價，其結果見表4、表5和表6，由于實驗結果是進行重復多次實驗得到，因此實驗結果以“均值±標準差”形式來表示，加粗的值表示的是最小的結果。

綜合表4、表5和表6的實驗結果，可以發現：

表4 屬性約簡結果的決策代價比較

表5 屬性約簡結果的測試代價比較

表6 屬性約簡結果的綜合代價比較

(1)對于每個決策類的決策代價，文獻[25]基于決策代價的屬性約簡在所有數據集中有7個決策類的決策代價最小，本文提出的特定類多目標屬性約簡在10個類中具有最小的決策代價。文獻[25]的算法是一種全局的屬性約簡算法，即對所有的決策類選擇出一個共同的屬性子集使得決策代價最小，因而不能保證每個決策類都是決策代價最小的，而本文所提出的特定類多目標屬性約簡算法基于每個類進行屬性選擇，則多數類下具有較小的決策代價，部分決策類的決策代價稍高于文獻[25]主要是由于本文是一種多目標的屬性約簡算法，屬于約簡的同時也考慮了測試代價的極小性。因此在決策類的決策代價方面，本文算法具有較優的屬性約簡性能。

(2)對于屬性約簡結果的測試代價，除數據集Cmc的決策類D2以外，本文提出的特定類多目標屬性約簡算法均具有較小的測試代價結果，這主要是由于本文的算法將測試代價作為一個優化目標進行屬性約簡，算法在進行屬性選擇的過程中，某個時刻可能有多個屬性使得決策代價降低，但是本文的算法可以選擇出測試代價較小的那個，而文獻[25]中基于決策代價的屬性約簡算法，進行屬性約簡時只考慮決策代價最小，這使得選擇的屬性可能具有較高的測試代價，因而最終得到的約簡結果測試代價較高。

同時可以發現，同一個數據集，基于決策代價的屬性約簡算法結果在每個決策類下的測試代價是一樣的，這主要是由于該算法是一種全局的屬性約簡，即所有決策類得到了同一個約簡結果，因此出現了這種現象。

(3)對于屬性約簡結果的綜合代價，除了數據集Cmc的決策類D2和數據集German的決策類D1，本文提出的算法具有更低的綜合代價，產生這一結果主要是由于本文的算法是在特定類別下進行多目標的屬性約簡，同時考慮了決策代價和測試代價，并且代價優化的對象具體到了對應的類別，因而屬性約簡的結果比全局的決策代價屬性約簡具有更好的約簡性能。

綜合以上實驗結果，可以表明本文提出的算法在代價敏感的屬性約簡方面具有更高的性能，同時約簡的目標針對具體的類，因此更加滿足實際中的應用需求。

5 結束語

決策粗糙集是粗糙集理論的重要研究分支，屬性約簡是粗糙集理論的核心問題。本文將傳統的決策粗糙集模型進行擴展和延伸，提出一種不完備混合決策粗糙集模型。決策代價和測試代價是決策粗糙集中兩種重要的代價形式，本文基于特定類別的視角，將這兩種代價同時作為屬性約簡的優化目標，提出一種特定類別的多目標屬性約簡算法。實驗結果分析表明，所提出算法的屬性約簡結果能夠使決策代價和測試代價綜合最小，并且不同類別有著不同的屬性約簡，更加符合實際的應用。本文的研究拓寬了決策粗糙集屬性約簡的應用范圍，因此接下來將在動態數據以及大數據環境下進行進一步研究。