基于決策粗糙集模型的局部屬性約簡

朱輝，竇慧莉

（江蘇科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院，江蘇鎮(zhèn)江212003）

近年來，隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展，我們世界的信息量正在以爆炸性的速度增長著。各行各業(yè)均存在著大量的的信息，如何從中選取出有效的信息早已經(jīng)成為我們亟待解決的一個難題。當(dāng)前特征選擇[2]已經(jīng)成為了我們解決這一問題的最主要和高效的方法之一，也是學(xué)者們研究的重點(diǎn)之一[10]。

特征選擇在Palwlak粗糙集模型[6]和其衍生模型中也被稱為屬性約簡，是整個粗糙集領(lǐng)域中非常重要的一個方面。屬性約簡工作[8]的完善與否直接影響了我們整個模型在分類等方面的精度等指標(biāo)的優(yōu)劣。決策粗糙集模型(Decision-Theoretic Rough Set Model，DTRSM)是姚一豫教授在1989年提出基于Palwlak粗糙集模型的一個拓展模型的粗糙集模型。DTRSM解決了傳統(tǒng)的粗糙集理論不涉及代價的問題，使得粗糙集也變得代價敏感，更加吻合實(shí)際生活中的語義。DTRSM提出之后，姚一豫教授在對其不斷研究地過程中，提出了三支決策理論，其主要目的是為粗糙集正域、邊界域和負(fù)域3個域提供合理的語義解釋。之后很多學(xué)者基于這一模型進(jìn)行了很多相關(guān)的研究。劉盾等對三支決策模型進(jìn)行了深入的研究和拓展[14]。賈修一等基于三支決策進(jìn)行了最小風(fēng)險代價的研究[12]。然后，眾多學(xué)者在研究過程中采用的都還是基于全部決策類的屬性約簡，在面對某個特定決策類進(jìn)行屬性約簡的問題時，便造成了很大程度上的資源浪費(fèi)和求解結(jié)果的不準(zhǔn)確性。為此，程德剛教授[1]提出了局部的思想，只針對某個或多個需要考慮的決策類進(jìn)行約束來求取約簡。

1 相關(guān)概念

1.1 Pawlak粗糙集

粗糙集理論[1]是由波蘭學(xué)者Pawlak提出的一種解決含糊性和不確定性問題的數(shù)學(xué)工具。其最主要是以集合近似的思想來進(jìn)行相關(guān)的數(shù)據(jù)挖掘、數(shù)據(jù)分析和推理。粗糙集理論采用了基于等價關(guān)系的數(shù)據(jù)分析方法。

為了去刻畫一個信息系統(tǒng)，Pawlak引入了上下近似集的概念。能根據(jù)條件判斷出屬于等價類X的元素構(gòu)成的集合，我們稱為X的下近似集；能根據(jù)條件判斷出有可能屬于等價類X的元素構(gòu)成的集合，我們稱為X的上近似集。

1.2 決策粗糙集理論（DTRS）與三支決策規(guī)則（Three-Way decision）

1.2.1 正域、負(fù)域、邊界域

在上下近似集的概念之上，研究者將由其產(chǎn)生的劃分區(qū)域分為3類：正域、負(fù)域以及邊界域。正域即為下近似集合形成的劃分區(qū)域；負(fù)域即為不屬于上近似的區(qū)域；邊界域變?yōu)樯辖票认陆贫喑龅囊徊糠植淮_定性區(qū)域。

所以，正域和負(fù)域均為確定性的區(qū)域，而邊界區(qū)域也是我們在判斷問題的時候最關(guān)鍵的要素。如何減小不確定性也是本文我們討論的一個關(guān)鍵點(diǎn)。

1.2.2 三支決策

三支決策是在傳統(tǒng)的兩支決策(接受、拒絕)上加入了延遲決策。定義分類狀態(tài)Ω={X，～X}，動作集：t={eP，eB，eN}，其中：X表示成功劃分進(jìn)該域，～X則表示錯誤劃分進(jìn)該域。eP，eB，eN分別表示將一個對象劃分進(jìn)正域、邊界域和負(fù)域的動作，那么劃分的代價我們分別定義為：λPP，λPN，λBP，λBN，λNP，λNN。其中λPP、λBP、λNP分別表示正確將對象劃分進(jìn)正域、邊界域、負(fù)域的代價；λPN，λBN，λNN則分別表示錯誤將對象劃分進(jìn)對應(yīng)區(qū)域的代價。那么我們有如下代價表達(dá)式：

R(ep|[x]A)、R(eb|[x]A)、R(en|[x]A)表示劃分在正域、邊界域、負(fù)域的代價，由此可得總的劃分代價：

2 屬性約簡

屬性約簡在粗糙及理論方面是極為重要的一個研究方向，它集中了該領(lǐng)域非常多的學(xué)者的關(guān)注。傳統(tǒng)的粗糙集中屬性約簡效率一般，在處理許多復(fù)雜的數(shù)據(jù)時會消耗大量的時間，這無疑會大大降其應(yīng)用的效率。針對這一問題，Yao等人將DTRS模型引入其中，并定義了包括保持正域和負(fù)域不變的屬性約簡在內(nèi)的一系列屬性約簡方法。從該點(diǎn)出發(fā)，在本節(jié)我們將會把局部思想引入其中，分析DTRS模型在全局和局部條件下屬性約簡。

2.1 決策保持屬性約簡

粗糙集理論中，對于決策保持方法約簡，通常是通過保持正域不變[12]或正域和負(fù)域二者不變來進(jìn)行約簡，以此保留完整的正域決策規(guī)則。本段我們將從保持正域和負(fù)域二者保持不變方面進(jìn)行屬性約簡的研究。

定義 1在一個信息系統(tǒng)I=＜U，AT∪j5i0abt0b＞，U為其論域，AT為其屬性集，d為決策屬性，?A?AT，U/IND(d)={X1，X2，…，Xn}，?Xj(j=1，2…n)，如果滿足

那么，我們稱A是一個基于決策保持的全局屬性約簡。

定義表明：一個約簡如果滿足保持上下近似集不變即正域和負(fù)域不變，便能保持了決策規(guī)則的完整。我們就可以將其稱為決策保持屬性約簡。

定義2在一個信息系統(tǒng)I=＜U，AT∪j5i0abt0b＞，U為其論域，AT為其屬性集，d為決策屬性，?A?AT，U/IND(d)={X1，X2，…，Xn}，如果對于一個或多個指定Xj(j=1，2…n)，如果滿足：

那么，我們稱A是一個基于決策保持的局部屬性約簡。

定義2是我們引入局部思想后的一個變形的公式。正如實(shí)際應(yīng)用中可能遇到的，只需針對少數(shù)關(guān)鍵性對象進(jìn)行有針對行屬性篩選一樣，我們只是在需要考慮的決策類中做決策保持的工作，對于不需要考慮的決策類中我們無需浪費(fèi)效率對其進(jìn)行決策保持。由此可以得到與我們考慮決策類最相關(guān)的屬性。

2.2 決策單調(diào)屬性約簡

定義 3在一個信息系統(tǒng)I=＜U，AT∪j5i0abt0b＞，U為其論域，AT為其屬性集，d為決策屬性，?A?AT，U/IND(d)={X1，X2，…，Xn}，?Xj(j=1，2，…，n)，如果滿足

那么，我們稱A是一個基于決策單調(diào)的全局屬性約簡。

定義 4 在一個信息系統(tǒng)I=＜U，AT∪j5i0abt0b＞，U為其論域，AT為其屬性集，d為決策屬性，?A?AT，U/IND(d)={X1，X2，…，Xn}，如果對于一個或多個指定Xj(j=1，2…n)，如果滿足

那么，我們稱A是一個基于決策單調(diào)的局部屬性約簡。

定義4相比與定義3而言，著重關(guān)注了需要關(guān)鍵性對象的屬性，弱化了非關(guān)鍵性對象在其中的影響。這將會有助于我們篩選出最能夠刻畫關(guān)鍵性對象的對應(yīng)屬性。

3 測試基于三支決策規(guī)則的屬性約簡

3.1 實(shí)驗(yàn)算法

3.1.1 重要度函數(shù)

文中采用了啟發(fā)式算法(Heuristic)，高效地獲取屬性約簡。在啟發(fā)式算法中，最為重要的便是重要度的定義和計算。在文中，重要度函數(shù)按如下的定義給出：

定義5令A(yù)T為屬性集合，A?AB，a∈AT，U/IND(d)={X1，X2，…，Xn}，決策保持重要度函數(shù)：

其中，?X，Y?U，X⊕Y=(X-Y)+(Y-X)

定義6令A(yù)T為屬性集合，A?AT，a∈AT，U/IND(d)={X1，X2，…，Xn}，決策保持的重要度函數(shù)：

其中，如果X?Y，X⊙Y=|Y-X|；否則，X⊙Y=-∞。

3.1.2 算法流程

屬性約簡的啟發(fā)式算法

該算法中，第二步每次計算后校驗(yàn)得到的約簡是否滿足指定約簡條件(定義1～4)，滿足條件添加元素進(jìn)Red集合，否則不添加；第三步，在添加的元素中再次檢查是否存在冗余屬性，有則刪除。

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

為了驗(yàn)證第1節(jié)中Local思想的性能上的優(yōu)越性，本小節(jié)中通過約簡后屬性的個數(shù)和規(guī)則數(shù)目兩個方面為標(biāo)準(zhǔn)，對本文中的理論進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)硬件配置Inter Core i3 CPU（2.67 GHz）、內(nèi)存4.0 GB的計算機(jī)上，用Matlab R2010b實(shí)現(xiàn)算法，其中實(shí)驗(yàn)中所用的數(shù)據(jù)集信息如表1，實(shí)驗(yàn)數(shù)據(jù)集均來自于UCI標(biāo)準(zhǔn)數(shù)據(jù)集。

表1 實(shí)驗(yàn)數(shù)據(jù)集及其相關(guān)信息

表2 全局約簡和局部約簡下的屬性數(shù)目（10組數(shù)據(jù)平均值）

表2所示為基于決策保持的全局屬性約簡和局部屬性約簡實(shí)驗(yàn)的對比結(jié)果。以Blood數(shù)據(jù)集為例，在達(dá)到相同的目的（決策保持）的前提下，局部約簡可以得到更為精確的屬性，在相同的方法下，平均多約簡了12.5%的冗余屬性。因此，局部屬性約簡在約簡后的屬性（特征）數(shù)目方面比全局屬性約簡要有優(yōu)勢?；谶@一優(yōu)點(diǎn)我們可以在屬性約簡的試驗(yàn)中加入局部的思想可以提高效率，節(jié)省資源，避免浪費(fèi)。

表3 全局約簡和局部約簡下的確定性規(guī)則變化（10組數(shù)據(jù)平均值）

表3顯示的是全局約簡和局部約簡在規(guī)則數(shù)方面的結(jié)果，從該表中我們可以看出：局部下的實(shí)驗(yàn)結(jié)果的規(guī)則數(shù)相比于全局下有了不同程度的增長。以Blood數(shù)據(jù)集為例，由于它是一個二類的數(shù)據(jù)集，所以只有X1和X2兩個等價類?；赬1這個等價類，規(guī)則數(shù)量不變，但是基于X2下規(guī)則數(shù)量有了明顯的增加，從平均90.4條規(guī)則增加到了97.9條規(guī)則數(shù)，有了8.3%的提升。這對于我們在輔助決策等方面具有較為重要的意義。

5 結(jié)束語

本文基于三支決策規(guī)則，對局部思想進(jìn)行了屬性約簡方面的研究。通過對比局部約簡和全局約簡的定義認(rèn)識局部約簡的原理與可能優(yōu)點(diǎn)。再結(jié)合算法、實(shí)驗(yàn)，用實(shí)驗(yàn)結(jié)果來驗(yàn)證理論。由結(jié)果可知：局部屬性約簡在刪除冗余屬性和確定性規(guī)則獲取等方面較全局屬性約簡相比具有明顯優(yōu)勢。這將會對我們研究決策問題提供較為重要的作用。在本文研究的基礎(chǔ)上，下一步研究主要集中在：

1）通過局部思想和其他算法結(jié)合挖掘其在屬性約簡方面的優(yōu)點(diǎn)；

2）將局部思想應(yīng)用和其他約簡方法結(jié)合，進(jìn)一步挖掘和認(rèn)識局部思想。

[1]Chen DG，Zhao SY.Local reduction of decision system with fuzzy rough sets[J].Fuzzy Sets and Systems，2010（161）：1871-1883.

[2]Chen G，Chen J.A novel wrapper method for feature selection and its applications[J].Neurocomputing，2015（159）：219-226.

[3]Lee J，Kim DW.Fast multi-label feature selection based on information-theoretic feature ranking[J].Pattern Recognition，2014（48）：2761-2771.

[4]Jia X Y，Liao W H，Tang Z M，et al.Minimum cost attribute reduction in decision-theoretic rough set models[J].Information Sciences，2013（219）：151-167.

[5]Jiang F，Sui Y F，Zhou L.A relative decision entropy-based feature selection approach[J].Pattern Recognition，2015（48）：2151-2163.

[6]Pawlak Z.Rough Sets-theoretical aspects of reasoning about data[J]. Dordrecht：Kluwer Academic，1991.

[7]Qian Y H，Liang J Y，Pedrycz W，et al.Positive approximation：An accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence，2010（174）：597-618.

[8]Shu W H，Qian W B.A fast approach to attribute reduction from perspective of attribute measures in incomplete decision systems[J].Knowledge-Based Systems，2014（72）：60-71.

[9]Wang W Y，Ma X A，Yu H.Monotonic uncertainty measures for attribute reduction in probabilistic rough set model[J].International Journal of Approximate Reasoning，2015（59）：41-67.

[10]Zeng Z L，Zhang H J，Zhang R，et al.A novel feature selection method considering feature interaction[J].Patten Recognition，2015（48）：2656-2666.

[11]Zong W，Wu F，Chu L K，et al.A discriminative and semantic feature selection method for text categorization[J].Int.J.Production Economics，2015（165）：215-222.

[12]賈修一，商琳，李家俊.決策風(fēng)險最小化屬性約簡[J].計算機(jī)科學(xué)與探索，2011，5（2）：155-160.

[13]賈修一，商琳.一種求三支決策閾值的模擬退火算法[J].小型微型計算機(jī)系統(tǒng)，2013，11（34）：2603-2606.

[14]劉盾，姚一豫，李天瑞.三枝決策粗糙集[J].計算機(jī)科學(xué)，2011，1（38）：246-250.

[15]宋晶晶，楊習(xí)貝，戚愑，等.可調(diào)節(jié)模糊粗糙集：模型與屬性約簡[J].計算機(jī)科學(xué)，2014，12（41）：183-188.