茍光磊,王國(guó)胤

1(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,重慶 400054) 2(重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400065)

1 引 言

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

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

上述有序信息系統(tǒng)的約簡(jiǎn)方法在不完備情況下不再適用.為得到不完備有序信息系統(tǒng)的約簡(jiǎn),Shao等提出基于擴(kuò)展優(yōu)勢(shì)關(guān)系粗糙集模型的約簡(jiǎn)方法[14]用于處理不協(xié)調(diào)不完備有序決策系統(tǒng).Yang等提出相似優(yōu)勢(shì)關(guān)系粗糙集模型處理不完備有序決策系統(tǒng),進(jìn)一步給出保持上、下近似分布約簡(jiǎn)方法[15].Yang等討論了不完備區(qū)間值信息系統(tǒng)中的多種相對(duì)約簡(jiǎn)方法[16].茍光磊等討論了不協(xié)調(diào)置信優(yōu)勢(shì)原理關(guān)系的屬性約簡(jiǎn)方法[17].以上多種方法都是基于辨識(shí)矩陣的,可獲得所有的約簡(jiǎn),但約簡(jiǎn)過程耗時(shí),效率低.

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

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

2 置信優(yōu)勢(shì)關(guān)系粗糙集

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

設(shè)a∈A具有偏好有序關(guān)系,記為a.xay,x,y∈U表示在屬性a上對(duì)象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 基于分類精度的啟發(fā)式約簡(jiǎn)方法

不完備有序決策系統(tǒng)中,置信優(yōu)勢(shì)關(guān)系粗糙集具有如下性質(zhì).

性質(zhì)1.假設(shè)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)由性質(zhì)1(2)輕松得到.

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

由性質(zhì)1可以發(fā)現(xiàn),基于置信優(yōu)勢(shì)關(guān)系粗糙集的分類精度在屬性域上呈現(xiàn)單調(diào)性,隨著條件屬性的增加,分類精度也隨之增加.

定義4.屬性重要性 設(shè)不完備有序決策系統(tǒng)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對(duì)于屬性集合B而言是冗余的,否則,a就是屬性集合B中的核屬性.

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

因此,根據(jù)置信優(yōu)勢(shì)關(guān)系粗糙集分類精度在屬性域上的單調(diào)性以及屬性重要性,提出保持分類精度不變的啟發(fā)式屬性約簡(jiǎn)方法,見算法1.

算法1.基于分類精度的啟發(fā)式屬性約簡(jiǎn)

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

輸出:屬性約簡(jiǎn)red

1.red=?,core=?

2. 計(jì)算分類精度γ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. 計(jì)算屬性重要性sig(i)=γcore∪{a}(Cl≥)-γcore(Cl≥);

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

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

13.endwhile

14. 根據(jù)屬性重要性對(duì)red里的屬性進(jìn)行降序排序

15.whilered≠φ

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

17.red=red-{a}

18.endif

19.endwhile

算法1的3-6步目標(biāo)是從條件屬性集C中找出核屬性,若核屬性集能夠保持系統(tǒng)的分類精度,則核屬性即為約簡(jiǎn)結(jié)果.若核屬性集不能保持系統(tǒng)的分類精度或者不存在核屬性,算法1的9-13步則從冗余屬性中按照屬性重要性的高低加入到核屬性,直到滿足分類精度不變?yōu)橹?算法1的15-19則對(duì)滿足分類精度不變的約簡(jiǎn)結(jié)果再次精簡(jiǎn).

4 基于分類精度的增量式屬性約簡(jiǎn)方法

上一節(jié),提出基于分類精度的啟發(fā)式屬性約簡(jiǎn)方法.從算法1可以看出每次在增加一個(gè)屬性或者刪除一個(gè)屬性時(shí),都會(huì)重新計(jì)算整個(gè)近似域來獲得分類精度,為此,本節(jié)討論單個(gè)屬性變化時(shí),近似集的動(dòng)態(tài)變化規(guī)律,給出分類精度的增量式算法,提出基于分類精度的增量式約簡(jiǎn)方法,改進(jìn)約簡(jiǎn)效率.

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

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

證明:

2)同理可證.

引理2.假定B?C,a∈B,屬性減少時(shí),置信優(yōu)勢(shì)集、置信劣勢(shì)集的變化滿足

“：”表示非.

證明:

2)同理可證.

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

證明:

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

證明:

根據(jù)定理1-2,在增加或刪除單個(gè)屬性時(shí),得到置信優(yōu)勢(shì)關(guān)系粗糙集的上、下近似集的變化規(guī)律,可給出分類精度的增量式算法見算法2與算法3.

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

輸出:γB-{ai}

1.foreacha∈C

4.end

5.fori=1:n

10.end

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

輸出:γB∪{a}

1.fori=1:|U|

3.end

4.fori=1:n

9.end

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

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

算法4.基于分類精度的增量式屬性約簡(jiǎn)

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

輸出:屬性約簡(jiǎn)red

1.red=?,core=?

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

3. for eacha∈C

4.if算法2計(jì)算γC-{a}≠γC

5.core=core∪{a};

6.endif

7.endfor

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

9.whileγC≠γred

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

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

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

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

14.endwhile

15. 根據(jù)屬性重要性對(duì)red里的屬性進(jìn)行降序排序

16.whilered≠?

17.if算法2計(jì)算γred-{a}=γC

18.red=red-{a}

19.endif

endwhile

5 仿真實(shí)驗(yàn)

我們將通過仿真實(shí)驗(yàn)來驗(yàn)證上述方法的正確性和有效性.為此,我們?cè)赨CI的五個(gè)數(shù)據(jù)集(見表1)進(jìn)行了實(shí)驗(yàn),除了car為完備數(shù)據(jù)集外,其余均為不完備數(shù)據(jù)集,完備數(shù)據(jù)集可視為不完備數(shù)據(jù)集的特例.實(shí)驗(yàn)環(huán)境為L(zhǎng)enovo X220i配置為Intel i3-2370 2.4GHz,內(nèi)存4GB,Windows 7(32bit),使用Matlab R2012b編程實(shí)現(xiàn).

表1 數(shù)據(jù)集描述
Table 1 Description of data sets

ID數(shù) 據(jù) 集|U||C|1Hepatitis155192Ionosphere351343breast-cancer699104mammographic-masses96155car17266

實(shí)驗(yàn)將基于分類精度的啟發(fā)式約簡(jiǎn)方法(算法1)與基于分類精度的增量式約簡(jiǎn)方法(算法4)進(jìn)行比較.實(shí)驗(yàn)結(jié)果如表2,兩種約簡(jiǎn)方法得到的約簡(jiǎn)是一致的.當(dāng)論域?qū)ο髠€(gè)數(shù)較少時(shí),增量式方法并不優(yōu)于啟發(fā)式約簡(jiǎn)方法即算法1,如Hepatitis數(shù)據(jù)集.當(dāng)隨著論域?qū)ο髠€(gè)數(shù)增加時(shí),增量式屬性約簡(jiǎn)算法的效率也逐步優(yōu)于非增量式的約簡(jiǎn)算法.

表2 啟發(fā)式算法與增量式方法運(yùn)行時(shí)間對(duì)比/s

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

ID算法1算法4約簡(jiǎn)后的屬性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以及置信優(yōu)勢(shì)關(guān)系粗糙集分類精度來對(duì)比約簡(jiǎn)前后的分類正確率,實(shí)驗(yàn)結(jié)果見下頁表3,屬性約簡(jiǎn)前后,置信優(yōu)勢(shì)關(guān)系粗糙集的分類精度保持不變.從NaiveBayes、ClassificationTree分類器的正確率可以看出,在完備數(shù)據(jù)集car上,屬性約簡(jiǎn)后的分類正確率有所降低.然而,在不完備的數(shù)據(jù)集中,約簡(jiǎn)前后的分類正確率變化不大.實(shí)驗(yàn)結(jié)果表明基于置信優(yōu)勢(shì)關(guān)系粗糙集分類精度的屬性約簡(jiǎn)方法在不完備有序信息系統(tǒng)中是有效的.

表3 約簡(jiǎn)前后分類正確率對(duì)比/%

總體來說,啟發(fā)式約簡(jiǎn)方法和增量式約簡(jiǎn)方法有效,在數(shù)據(jù)樣本較多時(shí),增量式方法時(shí)間效率上更優(yōu).

6 總 結(jié)

對(duì)于不完備有序決策系統(tǒng),本文在置信優(yōu)勢(shì)關(guān)系粗糙集的基礎(chǔ)上,提出基于分類精度的啟發(fā)式約簡(jiǎn)算法,由于每次增加或刪除一個(gè)屬性,啟發(fā)式約簡(jiǎn)方法都需要重新計(jì)算整個(gè)論域的近似域得到分類精度,為此,給出增量式分類精度算法,從而得到增量式約簡(jiǎn)方法.對(duì)比實(shí)驗(yàn)表明,兩個(gè)方法在屬性約簡(jiǎn)上是有效的,在樣本較多時(shí),增量式約簡(jiǎn)方法更優(yōu).

[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.

附中文參考文獻(xiàn)：

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

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

[6] 張文修,米據(jù)生,吳偉志.不協(xié)調(diào)目標(biāo)信息系統(tǒng)的知識(shí)約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào),2003,26(1):12-18.

[17] 茍光磊,王國(guó)胤.基于不協(xié)調(diào)置信優(yōu)勢(shì)原理關(guān)系的知識(shí)約簡(jiǎn)[J].計(jì)算機(jī)科學(xué),2016,43(6):6-9.