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

蔡艷婧，程 實(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]在決策粗糙集中提出了最大決策熵的屬性約簡。在另一方面，基于代價(jià)敏感的角度，Jia等[12]在決策粗糙集中提出了最小決策代價(jià)屬性約簡。楊志榮等[13]基于多代價(jià)的策略在決策粗糙集模型上提出了一種改進(jìn)的最小代價(jià)屬性約簡。陳婉清等[14]聯(lián)合決策代價(jià)和分類質(zhì)量，在決策粗糙集下提出了一種新的屬性約簡?？傊梢钥闯龌跊Q策代價(jià)的屬性約簡是目前決策粗糙集的研究熱點(diǎn)[15-18]。

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

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

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

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

利用等價(jià)類作為基本運(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 決策代價(jià)矩陣

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

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

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])

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

(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個(gè)決策規(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確定的等價(jià)關(guān)系為EA。對于屬性子集X?U關(guān)于等價(jià)關(guān)系EA的決策粗糙集下近似和上近似分別定義為

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

特別地，決策屬性集D在論域U上誘導(dǎo)的決策類劃分為U/D={D1,D2,…,Dm}，決策屬性集D關(guān)于等價(jià)關(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種動(dòng)作決策時(shí)所產(chǎn)生的預(yù)期代價(jià)為

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

即

且

即

且

即

且

記

那么有

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

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

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

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

(λ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))≥β時(shí),那么x∈BUN(X)；

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

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

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

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

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

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

3.1 基于特定類的決策代價(jià)

表2 決策類Dt的代價(jià)矩陣

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

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

3.2 基于特定類的測試代價(jià)

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

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

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

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

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

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

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

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

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

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

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

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

輸出：類別Dt的決策代價(jià)和測試代價(jià)多目標(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個(gè)UCI數(shù)據(jù)集[25]，在這6個(gè)數(shù)據(jù)集中包含了4個(gè)混合類型、2個(gè)數(shù)值型和1個(gè)符號型的數(shù)據(jù)集，部分?jǐn)?shù)據(jù)集為完備型的，實(shí)驗(yàn)前隨機(jī)選擇5%的屬性值進(jìn)行刪除，同時(shí)為了消除數(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)各個(gè)決策類的綜合代價(jià)先減少后增大，即過大和過小的鄰域半徑不能夠得到較好的實(shí)驗(yàn)結(jié)果。綜合圖1的每個(gè)子圖的實(shí)驗(yàn)結(jié)果，可以得出當(dāng)鄰域半徑δ介于0.15至0.21區(qū)間時(shí)，得到綜合代價(jià)最小。在接下來的實(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é)，即每個(gè)決策類按照特定關(guān)系選取對應(yīng)的決策代價(jià)，屬性的測試代價(jià)按照區(qū)間[1,20]進(jìn)行隨機(jī)選取等。對于參與比較的算法，是一種基于不完備離散型信息系統(tǒng)的全局最小代價(jià)屬性約簡，因此進(jìn)行實(shí)驗(yàn)時(shí)需要將表3中的數(shù)值型屬性進(jìn)行離散化處理，同時(shí)所有決策類選擇統(tǒng)一的決策代價(jià)，這里也隨機(jī)進(jìn)行選取。

對于本文所提出的多目標(biāo)屬性約簡與決策代價(jià)的屬性約簡，分別讓這兩種算法進(jìn)行相應(yīng)的屬性約簡，然后根據(jù)屬性約簡結(jié)果，我們分別計(jì)算出每個(gè)決策類的決策代價(jià)、測試代價(jià)以及綜合代價(jià)，其結(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é)果的決策代價(jià)比較

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

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

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

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

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

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

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

5 結(jié)束語

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