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

朱輝，竇慧莉

（江蘇科技大學計算機科學與工程學院，江蘇鎮江212003）

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

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

1 相關概念

1.1 Pawlak粗糙集

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

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

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

1.2.1 正域、負域、邊界域

在上下近似集的概念之上，研究者將由其產生的劃分區域分為3類：正域、負域以及邊界域。正域即為下近似集合形成的劃分區域；負域即為不屬于上近似的區域；邊界域變為上近似比下近似多出的一部分不確定性區域。

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

1.2.2 三支決策

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

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

2 屬性約簡

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

2.1 決策保持屬性約簡

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

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

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

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

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

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

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

2.2 決策單調屬性約簡

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

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

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

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

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

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

3.1 實驗算法

3.1.1 重要度函數

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

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

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

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

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

3.1.2 算法流程

屬性約簡的啟發式算法

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

4 實驗分析

為了驗證第1節中Local思想的性能上的優越性，本小節中通過約簡后屬性的個數和規則數目兩個方面為標準，對本文中的理論進行實驗。實驗硬件配置Inter Core i3 CPU（2.67 GHz）、內存4.0 GB的計算機上，用Matlab R2010b實現算法，其中實驗中所用的數據集信息如表1，實驗數據集均來自于UCI標準數據集。

表1 實驗數據集及其相關信息

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

表2所示為基于決策保持的全局屬性約簡和局部屬性約簡實驗的對比結果。以Blood數據集為例，在達到相同的目的（決策保持）的前提下，局部約簡可以得到更為精確的屬性，在相同的方法下，平均多約簡了12.5%的冗余屬性。因此，局部屬性約簡在約簡后的屬性（特征）數目方面比全局屬性約簡要有優勢。基于這一優點我們可以在屬性約簡的試驗中加入局部的思想可以提高效率，節省資源，避免浪費。

表3 全局約簡和局部約簡下的確定性規則變化（10組數據平均值）

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

5 結束語

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

1）通過局部思想和其他算法結合挖掘其在屬性約簡方面的優點；

2）將局部思想應用和其他約簡方法結合，進一步挖掘和認識局部思想。

[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]賈修一，商琳，李家俊.決策風險最小化屬性約簡[J].計算機科學與探索，2011，5（2）：155-160.

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

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

[15]宋晶晶，楊習貝，戚愑，等.可調節模糊粗糙集：模型與屬性約簡[J].計算機科學，2014，12（41）：183-188.