卓雪雪 朱蒼璐

（安徽三聯(lián)學院計算機工程學院 安徽合肥 230000）

Yao等學者提出的決策粗糙集模型是傳統(tǒng)粗糙集理論的重要推廣[1]。決策粗糙集模型通過引入貝葉斯理論來最小化決策的風險，利用參數閾值的限制來對概率粗糙集劃分的區(qū)域給出了語義解釋，在決策粗糙集中，閾值可以通過最小化代價函數進一步計算得到，因此給定決策代價，我們可以直接確定信息系統(tǒng)三支決策的區(qū)域劃分，并誘導出相應的決策規(guī)則[2]。

屬性約簡是粗糙集理論最重要的應用之一。屬性約簡其目的是尋找原始屬性集中的一個最小子集，使得與整個屬性集的分類能力相當。在決策粗糙集模型中，Yao等[3]學者提出了基于決策粗糙集正區(qū)域的屬性約簡；Ma等[4]學者在Yao的基礎上，提出了決策區(qū)域保持的屬性約簡，同時，Meng等[5]學者針對決策粗糙集提出了一種快速屬性約簡；基于熵度量的方法，Gao等[6]學者在決策粗糙集下提出了最大決策熵模型，并提出一種屬性約簡方法；姚晟等[7]學者基于正區(qū)域非單調性方法，提出一種改進的屬性約簡；Li等[8]學者利用多目標優(yōu)化的方法提出一種新的決策粗糙集屬性約簡；楊璇等[9]學者提出了一種決策粗糙集最優(yōu)尺度選擇的約簡。另一方面，決策粗糙集建立在代價的基礎上，因此有學者通過決策代價作為出發(fā)點進行屬性約簡的構造。例如，Jia等[10:1-2]學者針對決策粗糙集三區(qū)域劃分的決策代價，提出了最早的最小化決策代價屬性約簡算法；Song等[11]學者在模糊決策粗糙集下提出了最小化決策代價的屬性約簡，F(xiàn)ang等[12]學者提出了一種改進的決策粗糙集屬性約簡。到目前為止，決策粗糙集的屬性約簡受到了研究人員越來越多的關注。

然而，在實際應用環(huán)境下，我們可能往往只關注某一個決策類，例如，在醫(yī)療診斷中，決策者往往只關注患病的樣本集，同時實際應用環(huán)境下的數據可能是數值型的，并且具有一定的模糊性，因此傳統(tǒng)的決策粗糙集屬性約簡很難直接對其應用。針對信息系統(tǒng)中所關注的決策類，Ma等[13-14]學者提出了特定類的決策粗糙集屬性約簡，李明等[15]學者提出了集成學習方法的特定類決策粗糙集屬性約簡，彭莉莎等[16]學者提出了特定類的三支概率屬性約簡。但是這些成果很少有對模糊性數據環(huán)境進行相關研究，針對這一問題，本文提出一種模糊決策粗糙集的特定類最小化決策代價屬性約簡算法。

針對傳統(tǒng)的決策粗糙集，本文將考慮信息系統(tǒng)的模糊性，提出一種模糊相似關系的決策粗糙集，稱之為模糊決策粗糙集，然后在該模型中考慮特定決策類的決策劃分，提出了模糊決策粗糙集的三支決策規(guī)則，最后基于最小化決策代價原則，提出了一種基于特定決策類的最小化代價屬性約簡算法。實驗結果證明了本文所提出算法的有效性。

一、基本理論

對于決策粗糙集，給定一個對象集X，狀態(tài)集由兩個類表示，即Ω ={X,～X}，分別表示對象x屬于或不屬于X；動作集Γ ={aP,aB,aN}，aP,aB,aN分別表示三個動作：aP表示對象x被劃分為X的正區(qū)域；aB表示對象x被劃分為X的邊界域；aN表示對象x被劃分為X的負區(qū)域。關于兩種不同狀態(tài)下的三個動作的代價矩陣如表1所示。

表1 代價矩陣

在表1中，λPP，λBP和λNP分別表示對象x屬于X時進行aP，aB和aN動作的代價；λPN，λBN和λNN分別表示對象x不屬于X時進行aP，aB和aN動作的代價。通常，代價滿足0≤λPP≤ λBP< λNP<1，0≤ λNN≤ λBN< λPN<1。

對于決策粗糙集中，對象隸屬于集合概率的閾值是由每個分類決策的最小代價來確定，這提供了決策區(qū)域劃分的語義解釋，具體定義結果如定義1所示。

這里的閾值(α,β)是由代價矩陣確定的一對數值，定義為

定義2[4].考慮決策信息系統(tǒng)IS=(U,AT=C∪ D)，對于對象集X?U和屬性集A?C，那么對象集X?U在閾值(α,β)下的決策近似區(qū)域劃分為

與經典粗糙集中的規(guī)則不同，決策粗糙集中三個區(qū)域獲得的三種規(guī)則可能是不確定的，它們代表了在做出決策時對錯誤的容忍程度，因而具有更高的泛化性能。

二、特定類下的模糊決策粗糙集

由于實際應用環(huán)境下，我們可能往往只關注某一個決策類，同時實際應用環(huán)境下的數據可能具有一定的模糊性。針對這一情形，本節(jié)將提出一種基于特定類的模糊決策粗糙集模型。

定義3[11].考慮決策信息系統(tǒng)IS=(U,AT=C∪D)，屬性集A? C。如果二元模糊關系滿足如下3個條件，那么又被稱為模糊T等價關系：

在本文，我們利用高斯核函數[17]來構造對象之間的模糊關系。

定義4[17].考慮決策信息系統(tǒng)

IS=(U,AT=C ∪ D)，屬性集A? C，?x,y∈U之間的模糊相似度定義為

接下來，在模糊關系的基礎上提出特定類視角下的模糊決策粗糙集模型。

在模糊決策粗糙集模型中，給定一個特定類的對象X，該對象集的狀態(tài)集由兩個類表示，即Ω={X,～X}，分別表示對象x屬于或不屬于X；動作集Γ ={aP,aB,aN}，aP,aB,aN分別表示三個動作：aP表示對象x被劃分為X的正區(qū)域；aB表示對象x屬于X的邊界域；aN表示對象x屬于X的負區(qū)域。關于特定類兩種不同狀態(tài)下的三個動作的代價矩陣如表2所示。

表2 特定類X的代價矩陣

針對特定類X，對象x采取三種動作的預期成本可以表示如下：

因此我們可以得到基于特定類的模糊決策粗糙集模型以及三個決策區(qū)域的劃分。

定義6.考慮決策信息系統(tǒng)IS=(U,AT=C∪ D)，屬性集A?C。信息系統(tǒng)特定類X代價函數確定的一對決策閾值為αX和βX，那么特定類X關于(αX,βX)確定的模糊決策粗糙集上下近似集定義為

定義7.考慮決策信息系統(tǒng)IS=(U,AT=C∪ D)，屬性集A?C。信息系統(tǒng)特定類X代價函數確定的一對決策閾值為αX和βX，那么特定類X關于(αX,βX)的模糊決策粗糙集三個決策區(qū)域定義為

在定義7中，特定類的三個決策區(qū)域可以根據三支決策進行語義解釋。由(αX,βX)確定的決策正區(qū)域可以誘導用于進行接受決策的規(guī)則，由(αX,βX)確定的決策負區(qū)域可以誘導用于做出拒絕決策的規(guī)則，由(αX,βX)確定的決策邊界域可以產生非承諾規(guī)則。根據非承諾規(guī)則，我們既不做出接受或拒絕的決策，而是做出非承諾的決策。

三、特定類的最小化代價屬性約簡

三支決策在日常決策中起著關鍵的角色，它們可以根據成本進行評估決策。在現(xiàn)實世界的應用中，往往需要考慮決策的成本，尋找一個條件屬性的最小子集，使得所關注的特定決策類具有最小化的決策成本，這種稱之為最小化決策代價的屬性約簡。在本節(jié)，我們將提出一種特定類視角下基于模糊決策粗糙集的最小化代價屬性約簡算法。

考慮決策信息系統(tǒng)IS=(U,AT=C∪D)，屬性集A? C。信息系統(tǒng)特定類X關于(αX,βX)的模糊決策粗糙集三 個 決 策 區(qū) 域 分 別 為

根據模糊決策粗糙集的代價矩陣和決策規(guī)則，我們可以得出特定類在正區(qū)域、邊界區(qū)域和負區(qū)域的三個規(guī)則的決策成本：

根據特定類X的三個決策成本，可以進一步得到特定類的決策總成本，表示為

基于特定類的決策代價，我們提出一種特定類的最小化決策代價屬性約簡。

定義8.考慮決策信息系統(tǒng)IS=(U,AT=C∪ D)，特定類X代價函數確定的一對決策閾值為αX和βX，那么特定類X的最小化決策代價屬性約簡集red定義為

(1)Costred(X)≤CostC(X);

(2)?a ∈ red,Costred(X)

在定義8所示的最小化決策代價屬性約簡中，(1)限制了特定類X在屬性約簡集red下的決策代價不大于在屬性全集下的決策代價；(2)要求該屬性約簡集red是極小的，移除任意一個屬性會增加決策代價。

在粗糙集理論中，學者們通過兩種方法來計算尋找屬性約簡[10:6-7]：窮舉算法和啟發(fā)式算法。窮舉算法通過可識別矩陣構造所有約簡的集合，然而，該算法是一個NP難問題。啟發(fā)式算法引起了學者們的廣泛關注，目前基于粗糙集理論的屬性約簡大多采用啟發(fā)式的方法。本文將采用啟發(fā)式的方法實現(xiàn)所提出的屬性約簡算法，首先給出了啟發(fā)式函數的定義。

定義9.考慮決策信息系統(tǒng)IS=(U,AT=C∪D)，A?C，對于?a∈A關于特定類X的屬性重要度定義為

由于CostA(X)是固定的，即只需要計算代價Cost{a}(X)，那么Sig(a,A,X)適用于確定屬性a的顯著性。Sig(a,A,X)表示在特定類X下屬性a相對于屬性集A的顯著性程度，當Sig(a,A,X)的值越大，屬性a就越顯著，反之亦然。

基于定義9的屬性重要度作為啟發(fā)式函數，我們提出一種基于模糊決策粗糙集模型的特定類最小化決策代價屬性約簡算法。

算法1：基于模糊決策粗糙集的特定類最小化決策代價屬性約簡算法

輸入：決策信息系統(tǒng)IS=(U,AT=C∪ D)，信息系統(tǒng)特定類X?U，特定類X的代價矩陣。

輸出：特定類X的最小化決策代價屬性約簡結果red。

1.利用特定類X的代價矩陣計算出決策閾值αX和βX；

2.初始化設置red← ?，A← C；

3.對于?a∈A，計算每個屬性的屬性重要度Sig(a,A,X)；

4.選擇屬性集A中屬性重要度最大的屬性amax，若滿足關系CostA-{amax}(X)

5.對于 ?a∈red，如果滿足關系 Costred-{a}(X)≤Costred(X)，那么進行red ← red-{a}。

6.返回屬性約簡結果red。

算法1的基本思想是從空集開始不斷搜索出一個屬性約簡結果，根據屬性重要度函數，選擇顯著性值最大的屬性作為候選屬性，直到滿足定義8中的條件(1)，然后，我們按照定義8中的條件(2)逐個刪除屬性約簡集中的屬性，直到滿足屬性約簡結果的極小性。算法1的計算量主要集中在計算屬性的重要度上，因此算法1的時間復雜度為O(|C|2·|U|2)。

四、實驗分析

本節(jié)將進行一系列實驗來測試所提出屬性約簡算法的有效性。實驗各個環(huán)節(jié)在操作系統(tǒng)Windows7、CPU i3-6100 3.7GHz和內存8GB的個人計算機上，算法通過Matlab2012b進行實現(xiàn)運行。實驗從UCI數據集庫中選取了5個數值型類型的公用實驗數據集，具體如表3所示，同時在實驗前對這些數據集進行標準化處理。

表3 UCI實驗數據集

對于本文所提出算法,我們進行如下設置:(1)設置高斯核函數的δ=1.0；(2)設置特定類的代價矩陣里面的，其余選擇區(qū)間[0,1]范圍內的隨機值，并滿足關系

利用本文所提出的屬性約簡算法對表3中各個數據集的每個決策類進行最小化決策代價屬性約簡，并計算每個決策類在屬性約簡集下的決策代價，重復進行實驗10次并記錄其平均值。表4展示了各個數據集每個決策類在原始屬性全集下和屬性約簡集下的決策代價結果，其中Xi表示每個數據集第i個決策類。觀察表4的實驗結果可以看出，相比較于各個決策類屬性全集的決策代價，屬性約簡集的決策代價有著大幅度的減少，其平均結果降低了39.32%。因此，本文所提出的屬性約簡算法可以大幅度降低信息系統(tǒng)進行決策的代價。

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

表5所示的是表3中各個數據集屬性約簡的平均長度結果，觀察表5可以看出，每個決策類對應的屬性約簡結果均少于原始數據集的屬性集，部分數據集的約簡長度大幅度少于原始數據集，例如，數據集Ionosphere的原始屬性集長度為34，而決策類X2的平均約簡長度為12.3，數據集Sonar的原始屬性集長度為60，而決策類X2的平均約簡長度為15.8。各個數據集每個決策類屬性約簡的平均長度為10.49，各個數據集屬性全集的平均長度為25.92，降低了59.53%。因此本文所提出的屬性約簡方法可以大幅度降低屬性的數量。

表5 屬性約簡長度結果

本實驗通過支持向量機(SVM)分類器基于十次交叉訓練分類的方法評估各個數據集對于每個決策類屬性約簡集的分類精度，表6所示的是各個數據集每個決策類屬性約簡的SVM分類精度結果，通過表6可以看出，屬性約簡后每個決策類的分類精度均高于原始屬性集，其中對于原始屬性集，每個決策類的平均分類精度為83.35%，對于約簡集，其平均分類精度為89.11%，整體提升了6.91%。因此本文所提出的屬性約簡在降低決策代價的同時，可以進一步提高特定類的分類性能。

表6 屬性約簡分類精度結果(%)

五、結語

屬性約簡是粗糙集的重要研究內容。在決策粗糙集模型中，基于代價敏感的屬性約簡是當前的研究熱點。在實際應用環(huán)境下，我們往往只關注某個特定的決策類,同時實際的數據可能是數值型或模糊型,這給傳統(tǒng)的決策粗糙集屬性約簡帶來一定的挑戰(zhàn)。針對這一問題，本文提出一種基于模糊決策粗糙集模型特定類的最小化決策代價屬性約簡真法，實驗分析表明，本文算法得到的約簡結果在降低屬性數量和決策代價的同時，可以提高數據集的分類性能,具有一定的優(yōu)越性。接下來，我們可以將本文屬性約簡方法進行推廣，提出大數據環(huán)境下的屬性約簡算法，進一步提升實際環(huán)境下的應用性能。