置信優勢關系粗糙集的屬性約簡方法

茍光磊,王國胤

1(重慶理工大學 計算機科學與工程學院,重慶 400054) 2(重慶郵電大學 計算智能重慶市重點實驗室,重慶 400065)

1 引 言

優勢關系粗糙集模型(Dominance-based Rough Set Approach,DRSA)[1,2]常被用于處理序信息系統的決策問題.與經典粗糙集[3]基于等價關系不同,DRSA基于優勢關系,其條件屬性及決策屬性具有偏好有序的特性.實際應用環境中,由于數據采集技術的限制、傳輸故障等因素造成數據缺損和丟失,形成不完備有序信息.然而,DRSA無法處理不完備有序信息,因而,通過拓展優勢關系,置信優勢關系粗糙集[4]被提出用于處理不完備有序決策系統(Incomplete Ordered Decision System,IODS).

屬性約簡是粗糙集理論及其擴展模型研究的核心問題之一[5,6].在完備有序信息系統中,多種約簡方法被提出.其中,Dembczyński[1]等給出了基于分類精度的約簡概念,卻沒有提出相應的約簡方法.徐偉華等提出了多種基于DRSA的約簡方法,包括分布約簡和最大分布約簡[7],可能分布約簡(分配約簡)及相容分布約簡[8].Inuiguchi等提出了基于決策屬性聯合類的上、下近似、邊界域不變的約簡方法[9],Kusunoki進一步給出決策屬性基于類的上、下近似、邊界域不變的約簡方法[10].Susmaga提出了經典粗糙集和優勢關系粗糙集的約簡的統一定義框架和構造方法[11].Gou等提出基于優勢原理的屬性約簡方法[12].Chen等提出了基于優勢的領域粗糙集并行屬性約簡方法[13].

上述有序信息系統的約簡方法在不完備情況下不再適用.為得到不完備有序信息系統的約簡,Shao等提出基于擴展優勢關系粗糙集模型的約簡方法[14]用于處理不協調不完備有序決策系統.Yang等提出相似優勢關系粗糙集模型處理不完備有序決策系統,進一步給出保持上、下近似分布約簡方法[15].Yang等討論了不完備區間值信息系統中的多種相對約簡方法[16].茍光磊等討論了不協調置信優勢原理關系的屬性約簡方法[17].以上多種方法都是基于辨識矩陣的,可獲得所有的約簡,但約簡過程耗時,效率低.

1Lichman, M. UCI Machine Learning Repository[OL] http://archive.ics.uci.edu/ml. 2013.

本文將討論基于置信優勢關系粗糙集的約簡方法,首先討論了在屬性域上,分類精度呈現單調性;然后給出核屬性概念,提出置信優勢關系粗糙集基于分類精度的啟發式屬性約簡方法;由于啟發式約簡方法中,每次增加或刪除一個屬性,都會重新計算整個上、下近似集而得到分類精度,為此,討論了增加或刪除一個屬性后,上、下近似集的變化情況,從而改進啟發式約簡方法,提出增量式屬性約簡方法.最后,在UCI1數據集上的實驗結果表明,增量式約簡方法相對于啟發式約簡方法,時間效率更高.

2 置信優勢關系粗糙集

假設決策系統DS=(U,A,V,f),U表示論域,A是屬性集合,A=C∪D,其中C和D分別表示條件屬性集合決策屬性集.V是屬性值域,具有偏好.f:U×A→V是信息函數.f(xi,a)表示對象xi在屬性a上的取值.如果所有的屬性值都已知,則稱為完備有序決策系統.如果存在缺失值,則稱為不完備有序決策系統(Incomplete Ordered Decision System,IODS).缺失值用 “*”表示.

設a∈A具有偏好有序關系,記為a.xay,x,y∈U表示在屬性a上對象x至少和y一樣好.增序偏好下,xay表示f(x,a)≥f(y,a),降序偏好下,則表示f(x,a)≤f(y,a).為便于討論,在不作特別說明的情況下,本文將采用增序偏好.

(?q∈P(f(x,q)≠*)→(f(y,q)f(x,q)))}

邊界域的表示如下:

定義3.[4]分類精度定義如下

3 基于分類精度的啟發式約簡方法

不完備有序決策系統中,置信優勢關系粗糙集具有如下性質.

性質1.假設IODS=(U,A,V,f),其中A=C∪D,Cl={Clt|t∈{1,2…,n}}.

3)γB(Cl≥)=γB(Cl≤)

5)B?C?γB(Cl≥)≤γC(Cl≥),γB(Cl≤)≤γC(Cl≤)

證明:

3)由性質1(2)輕松得到.

5)由性質1(4)輕松得到.

由性質1可以發現,基于置信優勢關系粗糙集的分類精度在屬性域上呈現單調性,隨著條件屬性的增加,分類精度也隨之增加.

定義4.屬性重要性 設不完備有序決策系統IODS=(U,A,V,f),A=C∪D,B?C,其中a?C-B,屬性a的重要性表示為:

sig(a,B)=γB(Cl≥)-γB/{a}(Cl≥).

顯然,0≤sig(a,B)≤1.如果sig(a,B)=0,該屬性a對于屬性集合B而言是冗余的,否則,a就是屬性集合B中的核屬性.

定義5.設不完備有序決策系統IODS=(U,A,V,f),若γB(Cl≥)=γC(Cl≥),且B的任何真子集B′,滿足γB′(Cl≥)=γC(Cl≥),稱B是IODS的約簡.

因此,根據置信優勢關系粗糙集分類精度在屬性域上的單調性以及屬性重要性,提出保持分類精度不變的啟發式屬性約簡方法,見算法1.

算法1.基于分類精度的啟發式屬性約簡

輸入:不完備有序決策表IODS=(U,A,V,f)

輸出:屬性約簡red

1.red=?,core=?

2. 計算分類精度γC(Cl≥);

3.foreacha∈C

4.ifγC-{a}≠γC

5.core=core∪{a};

6.endif

7.endfor

8.A=C-core;red=core;

9.whileγC≠γred

10. 計算屬性重要性sig(i)=γcore∪{a}(Cl≥)-γcore(Cl≥);

11. 選擇屬性a∈C得到最大的sig;

12.red=red∪{a};A=A-{a};

13.endwhile

14. 根據屬性重要性對red里的屬性進行降序排序

15.whilered≠φ

16.ifγred-{a}=γC

17.red=red-{a}

18.endif

19.endwhile

算法1的3-6步目標是從條件屬性集C中找出核屬性,若核屬性集能夠保持系統的分類精度,則核屬性即為約簡結果.若核屬性集不能保持系統的分類精度或者不存在核屬性,算法1的9-13步則從冗余屬性中按照屬性重要性的高低加入到核屬性,直到滿足分類精度不變為止,算法1的15-19則對滿足分類精度不變的約簡結果再次精簡.

4 基于分類精度的增量式屬性約簡方法

上一節,提出基于分類精度的啟發式屬性約簡方法.從算法1可以看出每次在增加一個屬性或者刪除一個屬性時,都會重新計算整個近似域來獲得分類精度,為此,本節討論單個屬性變化時,近似集的動態變化規律,給出分類精度的增量式算法,提出基于分類精度的增量式約簡方法,改進約簡效率.

定義6.假定IODS=(U,A,V,f),對任意的x∈U,有

引理1.假定IODS=(U,A,V,f),B?C,a∈C-B,增加屬性時,置信優勢集、置信劣勢集的變化滿足

證明:

2)同理可證.

引理2.假定B?C,a∈B,屬性減少時,置信優勢集、置信劣勢集的變化滿足

“：”表示非.

證明:

2)同理可證.

定理1.假定B?C,a∈B,屬性增加時,上、下近似變化

證明:

定理2.假定B?C,a∈B,屬性減少時,上、下近似變化

證明:

根據定理1-2,在增加或刪除單個屬性時,得到置信優勢關系粗糙集的上、下近似集的變化規律,可給出分類精度的增量式算法見算法2與算法3.

算法2.刪除單個屬性后的分類精度

輸出:γB-{ai}

1.foreacha∈C

4.end

5.fori=1:n

10.end

算法3.增加單個屬性后的分類精度

輸出:γB∪{a}

1.fori=1:|U|

3.end

4.fori=1:n

9.end

在條件屬性集B中刪除單個條件屬性或增加單個條件屬性時,算法2,3利用已知的條件屬性集B的上、下近似等知識,增量式更新分類精度,無需重新計算整個論域.

我們使用算法2替換算法1中的4,16行,用算法3替換算法1中的10行,利用增量式方式更新論域的上、下近似得到分類精度,得到基于分類精度的增量式約簡方法,見算法4.

算法4.基于分類精度的增量式屬性約簡

輸入:不完備有序決策表IODS=(U,A,V,f)

輸出:屬性約簡red

1.red=?,core=?

2. 計算分類精度γC(Cl≥);

3. for eacha∈C

4.if算法2計算γC-{a}≠γC

5.core=core∪{a};

6.endif

7.endfor

8.A=C-core;red=core;

9.whileγC≠γred

10.算法3計算γcore∪{a}(Cl≥)

11. 計算屬性重要性sig(i)=γcore∪{a}(Cl≥)-γcore(Cl≥);

12. 選擇屬性a∈C得到最大的sig;

13.red=red∪{a};A=A-{a};

14.endwhile

15. 根據屬性重要性對red里的屬性進行降序排序

16.whilered≠?

17.if算法2計算γred-{a}=γC

18.red=red-{a}

19.endif

endwhile

5 仿真實驗

我們將通過仿真實驗來驗證上述方法的正確性和有效性.為此,我們在UCI的五個數據集(見表1)進行了實驗,除了car為完備數據集外,其余均為不完備數據集,完備數據集可視為不完備數據集的特例.實驗環境為Lenovo X220i配置為Intel i3-2370 2.4GHz,內存4GB,Windows 7(32bit),使用Matlab R2012b編程實現.

表1 數據集描述
Table 1 Description of data sets

ID數 據 集|U||C|1Hepatitis155192Ionosphere351343breast-cancer699104mammographic-masses96155car17266

實驗將基于分類精度的啟發式約簡方法(算法1)與基于分類精度的增量式約簡方法(算法4)進行比較.實驗結果如表2,兩種約簡方法得到的約簡是一致的.當論域對象個數較少時,增量式方法并不優于啟發式約簡方法即算法1,如Hepatitis數據集.當隨著論域對象個數增加時,增量式屬性約簡算法的效率也逐步優于非增量式的約簡算法.

表2 啟發式算法與增量式方法運行時間對比/s

Table 2 A comparison of running time between incremental and non-incremental(s)

ID算法1算法4約簡后的屬性12．2192553．0408582，4，5，6，10，11，15，16，17，18，19248．4789147．05986，8，10，14，17，24，29323．269720．841731，2，4，5，6，7，8，9，10426．387521．853981，2，3，4，5585．2206474．551854，6

接著,我們選用了NaiveBayes、ClassificationTree以及置信優勢關系粗糙集分類精度來對比約簡前后的分類正確率,實驗結果見下頁表3,屬性約簡前后,置信優勢關系粗糙集的分類精度保持不變.從NaiveBayes、ClassificationTree分類器的正確率可以看出,在完備數據集car上,屬性約簡后的分類正確率有所降低.然而,在不完備的數據集中,約簡前后的分類正確率變化不大.實驗結果表明基于置信優勢關系粗糙集分類精度的屬性約簡方法在不完備有序信息系統中是有效的.

表3 約簡前后分類正確率對比/%

總體來說,啟發式約簡方法和增量式約簡方法有效,在數據樣本較多時,增量式方法時間效率上更優.

6 總 結

對于不完備有序決策系統,本文在置信優勢關系粗糙集的基礎上,提出基于分類精度的啟發式約簡算法,由于每次增加或刪除一個屬性,啟發式約簡方法都需要重新計算整個論域的近似域得到分類精度,為此,給出增量式分類精度算法,從而得到增量式約簡方法.對比實驗表明,兩個方法在屬性約簡上是有效的,在樣本較多時,增量式約簡方法更優.

[1] Dembczynski K,Greco S,Kotlowski W,et al.Quality of rough approximation in multi-criteria classification problems[C].Rough Sets and Current Trends in Computing,Springer Berlin Heidelberg,2006:318-327.

[2] Greco S,Matarrazzo B,Slowinski R.Rough approximation by dominance relations[J].International Journal of Intelligent Systems,2002,17(2):153-171.

[3] Pawlak Z,Skowron A.Rudiments of rough sets[J].Information Sciences,2007,177(1):3-27.

[4] Gou Guang-lei,Wang Guo-yin,Li Jie,et al.Confidential dominance relation based rough approximation model[J].Control and Decision,2014,29(7):1325-1329.

[5] Chang Li-yun,Wang Guo-yin.An approach for attribute reduction and rule generation based on rough set theory[J].Journal of Software,1999,10(11):1206-1211.

[6] Zhang Wen-xiu,Mi Ju-sheng,Wu Wei-zhi.Knowledge reduction in inconsistent information systems[J].Chinese Journal of Computers,2003,26(1):12-18.

[7] Xu Wei-hua,Zhang Wen-xiu.Methods for knowledge reduction in inconsistent ordered information systems[J].Journal of Applied Mathematics and Computing,2008,26(1):313-323.

[8] Xu Wei-hua,Li Yuan,Liao Xiu-wu.Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems[J].Knowledge Based Systems,2012,27(3):78-91.

[9] Inuiguchi M,Yoshioka Y.Several reducts in dominance-based rough set approach[M].Interval/Probabilistic Uncertainty and Non-Classical Logics,Springer Berlin Heidelberg,2008:163-175.

[10] Kusunoki Y,Inuiguchi M.A unified approach to reducts in dominance-based rough set approach[J].Soft Computing,2010,14(5):507-515.

[11] Susmaga R.Reducts and constructs in classic and dominance-based rough sets approach[J].Information Sciences,2014,271(7):45-64.

[12] Gou Guang-lei,Wang Guo-yin.Inconsistent dominance principle based attribute reduction in ordered information systems[C].10th International Conference on Rough Set and Knowledge Technology,Tianjin,China,LNCS Volume,2015,9436:110-118.

[13] Chen Hong-mei,Li Tian-rui,Cai Yong,et al.Parallel attribute reduction in dominance-based neighborhood rough set[J].Information Sciences,2016,373(12):351-368.

[14] Shao Ming-wen,Zhang Wen-xiu.Dominance relation and rules in an incomplete ordered information system[J].International Journal of Intelligent Systems,2005,20(1):13-27.

[15] Yang Xi-bei,Yang Jing-yu,Wu Chen,et al.Dominance-based rough set approach and knowledge reductions in incomplete ordered information system[J].Information Sciences,2008,178(4):1219-1234.

[16] Yang Xi-bei,Yu Dong-jun,Yang Jing-yu,et al.Dominance-based rough set approach to incomplete interval-valued information system[J].Data & Knowledge Engineering,2009,68(11):1331-1347.

[17] Gou Guang-lei,Wang Guo-yin.An approach to knowledge reduction based inconsistent confidential dominance principle relation[J].Computer Science,2016,43(6):6-9.

附中文參考文獻：

[4] 茍光磊,王國胤,利 節,等.基于置信優勢關系的粗糙集近似模型[J].控制與決策,2014,29(7):1325-1329.

[5] 常犁云,王國胤.一種基于Rough Set 理論的屬性約簡及規則提取方法[J].軟件學報,1999,10(11):1206-1211.

[6] 張文修,米據生,吳偉志.不協調目標信息系統的知識約簡[J].計算機學報,2003,26(1):12-18.

[17] 茍光磊,王國胤.基于不協調置信優勢原理關系的知識約簡[J].計算機科學,2016,43(6):6-9.