蔡艷婧，程 實(shí)，王 強(qiáng)

(1.南通大學(xué) 信息科學(xué)技術(shù)學(xué)院，江蘇 南通 226009； 2.江蘇商貿(mào)職業(yè)學(xué)院 電子與信息學(xué)院，江蘇 南通 226009)

0 引 言

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

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

在粗糙集理論中，測試代價[21,22]也是學(xué)者們重點(diǎn)關(guān)注的內(nèi)容，目前已有多種測試代價的屬性約簡算法被提出。在本文，將提出一種不完備混合決策粗糙集模型，該模型進(jìn)一步擴(kuò)大了決策粗糙集的應(yīng)用范圍。接著在不完備混合決策粗糙集的基礎(chǔ)上，定義了特定類別的決策代價，并將決策代價和屬性集的測試代價同時作為屬性約簡的優(yōu)化目標(biāo)，提出一種特定類的多目標(biāo)代價敏感啟發(fā)式屬性約簡算法，該算法得到的屬性約簡可以使決策代價和測試代價綜合最小。實(shí)驗(yàn)結(jié)果表明，所提算法具有更高的代價敏感屬性約簡性能，同時屬性約簡結(jié)果針對的是特定的決策類，不同的類可以得到不同的約簡結(jié)果，因此所提算法具有更高的實(shí)用性能。

1 基本理論

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

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

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

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

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

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

表1 決策代價矩陣

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

因此，對于信息系統(tǒng)?x∈U可以得到采取3種動作決策時所產(chǎn)生的預(yù)期代價

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個決策規(guī)則進(jìn)行進(jìn)一步推導(dǎo)，可以得到

使得

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

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

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

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

同時對象集X?U關(guān)于等價關(guān)系EA的決策粗糙集正區(qū)域、邊界域和負(fù)區(qū)域分別定義為

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

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

Yao提出的決策粗糙集建立在離散完備的信息系統(tǒng)下。近年來，Li等[18]學(xué)者在數(shù)值型的信息系統(tǒng)下提出了鄰域決策粗糙集，進(jìn)一步地?cái)U(kuò)大了決策粗糙集模型的適用范圍。然而實(shí)際應(yīng)用中的數(shù)據(jù)類型是復(fù)雜多樣的，其中數(shù)值型屬性和符號型屬性并存的不完備混合型信息系統(tǒng)便是最為常見的一種。本節(jié)將在不完備混合型信息系統(tǒng)下對決策粗糙集模型進(jìn)行推廣，提出一種更為廣義化的模型。

在文獻(xiàn)[23]中，Zhao等學(xué)者在不完備混合型的信息系統(tǒng)下構(gòu)造了鄰域容差關(guān)系，并且提出了對應(yīng)的粗糙集模型，該模型在處理不完備混合型數(shù)據(jù)方法表現(xiàn)出了良好的性能，因此本節(jié)將采用Zhao等學(xué)者提出的鄰域容差關(guān)系，用于不完備混合型決策粗糙集模型的構(gòu)造。

類似于經(jīng)典的決策粗糙集，對于不完備混合型信息系統(tǒng)中的對象?x∈U，采取3種動作決策時所產(chǎn)生的預(yù)期代價為

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

即

且

即

且

即

且

記

那么有

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

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

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

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

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

那么可以得到關(guān)系0≤β<γ<α≤1。因此

(1)當(dāng)P(X|nδ(x))≥α?xí)r,那么x∈POS(X)；

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

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

根據(jù)如上推導(dǎo)，接下來可以得到不完備混合型決策信息系統(tǒng)下的決策粗糙集模型。

3 基于特定類的多目標(biāo)屬性約簡算法

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

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

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

3.1 基于特定類的決策代價

表2 決策類Dt的代價矩陣

同時信息系統(tǒng)中對象決策為Dt的決策總代價表示為

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

3.2 基于特定類的測試代價

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

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

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

3.3 基于特定類的多目標(biāo)代價敏感屬性約簡

實(shí)際應(yīng)用中可能需要同時考慮信息系統(tǒng)的決策代價和測試代價，因此需要將這兩種代價進(jìn)行綜合。本節(jié)中，我們將這兩種代價都作為屬性約簡的目標(biāo)，提出一種基于特定類的多目標(biāo)代價敏感屬性約簡算法。

由于多目標(biāo)的屬性約簡需要同時考慮多個目標(biāo)的情形，這往往很難保證屬性約簡結(jié)果使得每個目標(biāo)都是最優(yōu)的，因此需要對每個目標(biāo)的結(jié)果進(jìn)行權(quán)衡，即多目標(biāo)的結(jié)果應(yīng)該使整體達(dá)到最優(yōu)。為此，這里定義了一個關(guān)于決策代價和測試代價的多目標(biāo)綜合代價函數(shù)。

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

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

尋找屬性約簡是一個NP難問題，而啟發(fā)式搜索是求解屬性約簡的一種有效方法[9，10,18,23]，其中啟發(fā)式搜索的關(guān)鍵是構(gòu)造屬性約簡的啟發(fā)式函數(shù)。根據(jù)定義7所示的多目標(biāo)綜合代價，我們可以進(jìn)一步誘導(dǎo)出對應(yīng)的啟發(fā)式函數(shù)，即屬性重要度函數(shù)。

根據(jù)定義9中屬性重要度函數(shù)的定義，進(jìn)行啟發(fā)式搜索的屬性約簡算法如算法1所示。

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

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

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

步驟1 初始化red←?。

步驟6 返回最終屬性約簡結(jié)果red。

4 實(shí)驗(yàn)分析

在本節(jié)將通過實(shí)驗(yàn)來驗(yàn)證所提出算法的有效性。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

表3所示的是參與實(shí)驗(yàn)的6個UCI數(shù)據(jù)集[25]，在這6個數(shù)據(jù)集中包含了4個混合類型、2個數(shù)值型和1個符號型的數(shù)據(jù)集，部分?jǐn)?shù)據(jù)集為完備型的，實(shí)驗(yàn)前隨機(jī)選擇5%的屬性值進(jìn)行刪除，同時為了消除數(shù)值型數(shù)據(jù)量綱的影響，進(jìn)行實(shí)驗(yàn)前需要將所有數(shù)值型屬性進(jìn)行標(biāo)準(zhǔn)化處理，本實(shí)驗(yàn)標(biāo)準(zhǔn)化為[0,1]區(qū)間。

表3 實(shí)驗(yàn)數(shù)據(jù)集

4.2 參數(shù)選取

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

4.3 實(shí)驗(yàn)比較

接下來將本文所提出的算法與文獻(xiàn)[25]的屬性約簡算法進(jìn)行實(shí)驗(yàn)比較，來驗(yàn)證本文算法的有效性。

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

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

綜合表4、表5和表6的實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)：

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

表5 屬性約簡結(jié)果的測試代價比較

表6 屬性約簡結(jié)果的綜合代價比較

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

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

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

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

綜合以上實(shí)驗(yàn)結(jié)果，可以表明本文提出的算法在代價敏感的屬性約簡方面具有更高的性能，同時約簡的目標(biāo)針對具體的類，因此更加滿足實(shí)際中的應(yīng)用需求。

5 結(jié)束語

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