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

卓雪雪 朱蒼璐

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

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

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

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

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

一、基本理論

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

表1 代價矩陣

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

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

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

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

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

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

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

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

在本文，我們利用高斯核函數(shù)[17]來構(gòu)造對象之間的模糊關(guān)系。

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

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

接下來，在模糊關(guān)系的基礎(chǔ)上提出特定類視角下的模糊決策粗糙集模型。

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

表2 特定類X的代價矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.初始化設(shè)置red← ?，A← C；

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

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

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

6.返回屬性約簡結(jié)果red。

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

四、實驗分析

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

表3 UCI實驗數(shù)據(jù)集

對于本文所提出算法,我們進(jìn)行如下設(shè)置:(1)設(shè)置高斯核函數(shù)的δ=1.0；(2)設(shè)置特定類的代價矩陣?yán)锩娴模溆噙x擇區(qū)間[0,1]范圍內(nèi)的隨機值，并滿足關(guān)系

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

表4 屬性約簡決策代價結(jié)果

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

表5 屬性約簡長度結(jié)果

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

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

五、結(jié)語

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