一種多屬性和準(zhǔn)則定序分類模型

朱顥東，鐘 勇

(1.中國科學(xué)院 成都計(jì)算機(jī)應(yīng)用研究所，成都610041，zhuhaodong80@163.com;2.中國科學(xué)院 研究生院，北京100039)

多屬性和準(zhǔn)則定序分類是現(xiàn)實(shí)生活中一類重要的決策問題［1-2］，對(duì)于該問題的現(xiàn)有解決方法在獲取決策者的偏好信息方面都存在困難.關(guān)系模型和函數(shù)模型是解決該方法的主要模型，但是這兩個(gè)模型需要事先給出較多的偏好信息，例如準(zhǔn)則權(quán)重、滿意度等［3-4］，這為那些不熟悉這兩個(gè)模型的用戶增加了難度.粗糙集理論的出現(xiàn)為這類問題提供了較為可行的解決辦法［5］.但是粗糙集理論是利用不可區(qū)分關(guān)系來解決問題的，但它在解決多屬性和準(zhǔn)則定序分類問題時(shí)能力較弱.Greco 等［6-9］學(xué)者使用優(yōu)勢(shì)關(guān)系來代替不可區(qū)分關(guān)系以增強(qiáng)粗糙集解決多屬性和準(zhǔn)則定序分類問題的能力，但也存在一定的局限性.本文在這些文獻(xiàn)的基礎(chǔ)上，對(duì)經(jīng)典粗糙集理論進(jìn)行了擴(kuò)展，并給出了一個(gè)基于擴(kuò)展粗糙集的決策分析方法.該方法使用“不可區(qū)分-相似-優(yōu)勢(shì)”關(guān)系來代替經(jīng)典粗糙集理論中的不可區(qū)分關(guān)系來獲取知識(shí)的粗糙近似.

1 一種新的不一致問題

經(jīng)典粗糙集方法是通過不可區(qū)分關(guān)系來實(shí)現(xiàn)知識(shí)的獲取，每個(gè)非空的屬性子集P 都對(duì)應(yīng)著U上的一個(gè)不可區(qū)分關(guān)系，記作IP:IP={(x，y)∈U×U:q(x)=q(y)，?q ∈P}，如果(x，y)∈IP，則稱x 和y 是p 不可區(qū)分的，這樣定義的不可區(qū)分關(guān)系是一種等價(jià)關(guān)系，即滿足自反性、對(duì)稱性、傳遞性.關(guān)系IP的所有等價(jià)類的集合記作U/IP(形成U 上的一個(gè)劃分).關(guān)系IP中的等價(jià)類稱為P 初等集.對(duì)于由信息粒度引起的不一致問題，經(jīng)典粗糙集理論是可以解決的，但是有準(zhǔn)則屬性出現(xiàn)時(shí)，需要在數(shù)據(jù)分析時(shí)考慮優(yōu)勢(shì)關(guān)系.

以公司進(jìn)行破產(chǎn)風(fēng)險(xiǎn)評(píng)估作為例子.其中，用一個(gè)準(zhǔn)則(投資回報(bào))和一個(gè)屬性(所在城市)來描述該公司.

表1 破產(chǎn)風(fēng)險(xiǎn)評(píng)估表

表1 表明:因?yàn)锳 的投資回報(bào)高于B 的投資回報(bào)，而A 的風(fēng)險(xiǎn)低于B 的風(fēng)險(xiǎn)，并且它們所在城市相同，因此A 的評(píng)估結(jié)果比B 的評(píng)估結(jié)果好，這是合理的.D 的評(píng)估結(jié)果也比B 的評(píng)估結(jié)果好，雖然B 的投資回報(bào)較高，但是B 和D 位于不同的城市，其投資條件可能不同，此結(jié)果并不違背優(yōu)勢(shì)原理.C 的評(píng)估結(jié)果好于B 的評(píng)估結(jié)果，雖然B 的投資回報(bào)較高，但是C 和B 處在相同的城市，評(píng)估結(jié)果違背了優(yōu)勢(shì)原理，使得B 和C 是一對(duì)不一致樣本.

2 對(duì)經(jīng)典粗糙集的擴(kuò)展

2.1 對(duì)優(yōu)勢(shì)關(guān)系的擴(kuò)展

已知S= ( U ，C ∪D，V，f)，其中，C～為定量屬性子集為定性屬性子集，C＞為準(zhǔn)則子集，則且此外，對(duì)任意的P ?C，記

1)對(duì)?q ∈C～，Rq為U 上一個(gè)相似關(guān)系，xRqy 為在定量屬性 q 上 x 相似于為給 定的閾值 ).若?x，y ∈U，?q ∈P～?C～，有xRqy，則在P～上x 相似于y.

2)對(duì)?q ∈C＞，Sq為U 上一個(gè)優(yōu)勢(shì)關(guān)系，xSqy 在準(zhǔn)則屬性q 上x 至少同y 一樣好(f(x，q)≥f(y，q)).若，有xSqy，則在P＞上x 優(yōu)于y.

3)對(duì)?q ∈C≡，Iq為U 上一個(gè)不可區(qū)分關(guān)系，xIqy 為在定性屬性q 上x 同y 不可區(qū)分(f(x，q)=f(y，q)).若?x，y ∈U，?q ∈，有xIqy，則在上x 和y 不可區(qū)分.

另外，如果決策屬性集D 把論域U 劃分為若干個(gè)決策類，令cl={clt|t ∈T，T=1，2，…，n}，為決策類集合，那么?x ∈U 且僅屬于一個(gè)clt∈cl，而且?r，s ∈T，若r ＞s，則clr中的對(duì)象(嚴(yán)格地或弱地)優(yōu)于cls的對(duì)象.定義［x ∈clr，y ∈cls，r ＞s］?［xSy］，其中，xSy 為x 不劣于y.由于決策類的這種偏好序關(guān)系，令={x|(x ∈clt)∨(?y ∈clt∧xSy)}稱為決策類clt的向上并集，稱為決策類clt的向下并集，即.顯然，

2.2 新的粗糙近似

經(jīng)典粗糙集是用一種知識(shí)近似另一種知識(shí)，其中被近似的知識(shí)是決策屬性集D 劃分U 所形成的決策類，用于近似的知識(shí)是條件屬性集C 劃分U 所形成的基本集.但對(duì)定序分類而言，不但決策類具有偏好序，而且條件屬性集含有準(zhǔn)則，此時(shí)被近似的知識(shí)是決策類的向上并集和向下并集，用于近似的知識(shí)不再是僅由不可區(qū)分關(guān)系定義的對(duì)象集，而是由相似、優(yōu)勢(shì)和不可區(qū)分關(guān)系共通定義的對(duì)象集，這也是擴(kuò)展方法與經(jīng)典方法的主要區(qū)別.

對(duì)于?P ?C，定義DP和為U 上的兩個(gè)自反二元關(guān)系，稱為“不可區(qū)分-相似-優(yōu)勢(shì)”關(guān)系，對(duì)?x，y ∈U:①xDPy iff ?q ∈P＞，xSqy;?q ∈，xIqy ∧?q ∈P～，yRqx.②iff?q ∈P＞，xSqy;?q ∈，xIqy ∧?q ∈P～，xRqy.

給定P ?C，x ∈U，擴(kuò)展方法中，用于近似的“知識(shí)?！睘?

1)在P＞上，y 優(yōu)于x;在上，y 和x 不可區(qū)分;在P～上，x 相似于y 的對(duì)象y 的集合(x)={y ∈U:yDPx}.

2)在P＞上，y 優(yōu)于x;在P≡上，y 和x 不可區(qū)分;在P～上，y 相似于x 的對(duì)象y 的集合:(x)={y ∈U}.

3)在P＞上，y 劣于x;在P≡上，y 和x 不可區(qū)分;在P～上，x 相似于y 的對(duì)象y 的集合(x)={y ∈U:}.

4)在P＞上，y 劣于x;在P≡上，y 和x 不可區(qū)分;在P～上，y 相似于x 的對(duì)象y 的集合(x)={y ∈U:xDPy}.

所以，?P ?C，必定屬于cl≥t 的全部對(duì)象形成了的P-下近似，記作)={x ∈U:;可能屬于的全部對(duì)象形成了的P-上近似，記作t=1，2，…，n.類似地，可以定義的P-下近似和P-上近似.因此，決策類的邊界為:?P ?C，定義和的關(guān)于P 的近似精度為

此近似精度描述的是利用P 對(duì)對(duì)象分類時(shí)可能決策中正確決策的百分比.

定義 劃分cl 關(guān)于P 的近似分類質(zhì)量為

式中:P 能確切地劃入cl 類的對(duì)象的百分比.

條件屬性集C 的最小子集P ?C 稱為決策表的一個(gè)約簡(jiǎn)，當(dāng)且僅當(dāng)γP(cl)=γC(cl).一個(gè)決策表可能有多個(gè)約簡(jiǎn).

2.3 提取決策規(guī)則

由決策類的向上和向下并集的粗糙近似，可以獲得3 類決策規(guī)則:

1)D≥-決策規(guī)則，由形成:若f(x，q1)≥rq1，…，f(x，qu)≥rqu且f(x，qu+1)=rqu+1，…，f(x，qv)=rqv且f(x，qv+1)相似于rqv+1，…，f(x，qz)相似于rqz，則x ∈;其中，P={q1，…，qz}?C，P＞={q1，…，qu}，={qu+1，…，qv}，P～={qv+1，…，qz}，{rq1，…，rqz}∈Vq1×Vq2×…×Vqz，t ∈T;

2)D≤-決策規(guī)則，由形成:若f(x，q1)≤rq1，…，f(x，qu)≤rqu且f(x，qu+1)=rqu+1，…，f(x，qv)=rqv且f(x，qv+1)相似于rqv+1，…，f(x，qz)相似于rqz，則x ∈;其中，P={q1，…，qz}?C，P＞={q1，…，qu}，P≡={qu+1，…，qv}，P～={qv+1，…，qz}，{rq1，…，rqz}∈Vq1×Vq2×…×Vqz，t ∈T;

3)D≥≤-決策規(guī)則，由形成:若f(x，q1)≥rq1，…，f(x，qu)≥rqu且f(x，qu+1)≤rqu+1，…，f(x，qv)≤rqv…，f(x，qv)=rqv且f(x，qv+1)=rqv+1，…，f(x，qw)=rqw且f(x，qw+1)相似于rqw+1，…，f(x，qz)相似于rqz，則x∈cls∪cls+1∪…∪clt;其中，P={q1，…，qz}?C，P＞={q1，…，qu}∪{qu+1，…，qv}，={qv+1，…，qw}，P～={qw+1，…，qz}，{rq1，…，rqz}∈Vq1×Vq2×…×Vqz，s，t ∈T，s ＜t，{q1，…，qu}和{qu+1，…，qv}能夠相交.

3 實(shí)例驗(yàn)證

表2 是一個(gè)決策表，其中有8 家商場(chǎng)作為決策對(duì)象，其中，A1為交通條件、A2為位置、A3為面積，m2、A4為商場(chǎng)內(nèi)環(huán)境、A5為同類商品平均價(jià)格、A6為服務(wù)態(tài)度、A7為客流量，d 為決策屬性.表2 中d 把論域劃分為贏利、盈虧平衡、虧損3 類.

表2 一個(gè)具有多屬性和準(zhǔn)則的決策表

3.1 經(jīng)典粗糙集方法的結(jié)果

顯 然，C = {A1，A2，A3，A4，A5，A6，A7}，D =j5i0abt0b.其中，cl1為虧損的商場(chǎng)類，cl2為盈虧平衡的商場(chǎng)類，cl3為贏利的商場(chǎng)類.cl1={1，4，8}，cl2={3，6}，cl3={2，5，7}.cl1，cl2，cl3的C-下近似、C-上近似、C-邊界分別為，BnC(cl1)={7，8={3，6}(cl2)={3，6}，BnC(cl2)=φ={2，5})={2，5，7，8}，BnC(cl3)={7，8}.

因此，cl1，cl2，cl3的近似精度分別為0.5，1，0.5.分類質(zhì)量為0.75.存在約簡(jiǎn){A2，A3}或{A3，A6}.

以約簡(jiǎn)集{A3，A6}為例，可以得到的最小決策規(guī)則集為(其中:(x，A3)，(x，A6)為支持對(duì)應(yīng)規(guī)則的對(duì)象，(1，…，8)為所對(duì)應(yīng)的商場(chǎng)):

1)若f(x，A3)=510，則x ∈cl1(1).

2)若f(x，A3)=450，則x ∈cl2(3).

3)若f(x，A3)=475，則x ∈cl3(5).

4)若f(x，A3)=425，則x ∈cl2(6).

5)若f(x，A3)=400，f(x，A6)=“中”，則x ∈cl3(2).

6)若f(x，A3)=400，f(x，A6)=“良”，則x ∈cl1(4).

7)若f(x，A3)=350，則x ∈cl1或x ∈cl3(7，8).

3.2 使用“不可區(qū)分－相似－優(yōu)勢(shì)”關(guān)系的近似結(jié)果

同樣是C ={A1，A2，A3，A4，A5，A6，A7}，D =j5i0abt0b，但觀察到A1或A7是一個(gè)準(zhǔn)則屬性.對(duì)A1來講，“方便”優(yōu)“一般”.而對(duì)A2、A3來講，它們?cè)傧嚓P(guān)域上不存在優(yōu)勢(shì)關(guān)系.對(duì)屬性A2而言，使用經(jīng)典的不可區(qū)分關(guān)系，即?x，y ∈U，xIqy，則有f(x，A2)=f(y，A2).對(duì)屬性A3來說，定義一個(gè)相似關(guān)系， 使 得 ?x，y ∈ U，xRqy， 則 有.因?yàn)榭紤]了3 個(gè)決7}，它們的C-下近似、C-上近似、C-邊界分別為= {1，4，6，7，8}，策類，所以需要近似{1，4，8}= cl1∪ cl2= {1，3，4，6，8}，=cl2∪cl3={2，3，5，6，7}=cl3={2，5，={1，3，4，6}，={7，8}，= {2，3，4，5，6，7，8}，)= {2，5}，= {7，8}.的近似精度分別為0.2、0.67、0.43、0.5，而分類質(zhì)量為0.5.存在約簡(jiǎn){A2，A3}或{A3，A6}.

以{A3，A6}和準(zhǔn)則屬性A1為例，則可獲得最小決策規(guī)則集(其中，(x，A3)，(x，A6)為支持對(duì)應(yīng)規(guī)則的對(duì)象，(1，…，8)為所對(duì)應(yīng)的商場(chǎng)):

1)若f(x，A3)為“中”，f(x，A3)相似于510，則

2)若f(x，A1)至少為“方便”，f(x，A6)為“中”，則

3)若f(x，A6)為“中”，f(x，A3)相似于450，則x ∈cl2(3).

4)若f(x，A6)為“良”，f(x，A3)相似于400，則x ∈cl1∪cl2(4，6).

5)若f(x，A1)至少為“方便”，f(x，A3)相似于475，則

6)若f(x，A3)相似于350，則x ∈cl1∪cl2∪cl3(7，8).

3.3 結(jié)果對(duì)比

僅使用不可區(qū)分關(guān)系時(shí)，近似分類質(zhì)量為0.75，這是因?yàn)樯虉?chǎng)7、8 是不可區(qū)分的卻屬于不同的決策類.使用不可區(qū)分-相似-優(yōu)勢(shì)關(guān)系時(shí)，近似分類質(zhì)量為0.5，這是因?yàn)樯虉?chǎng)4、6 存在不一致:在準(zhǔn)則屬性A1上，商場(chǎng)4 優(yōu)于商場(chǎng)6;在屬性A2上，商場(chǎng)4 和商場(chǎng)6 是不可區(qū)分的;在屬性A3上，商場(chǎng)6 相似于商場(chǎng)4，因此有4DC6(同時(shí)也因商場(chǎng)4 相似于商場(chǎng)6，也有).可是，對(duì)商場(chǎng)4 的綜合評(píng)估為虧損，對(duì)商場(chǎng)6 的綜合評(píng)估為盈虧平衡，商場(chǎng)4 劣于商場(chǎng)6，這明顯不符合優(yōu)勢(shì)原理.僅使用不可區(qū)分關(guān)系對(duì)這種不一致無能為力，而利用“不可區(qū)分-相似-優(yōu)勢(shì)”關(guān)系卻可以揭示這種不一致.

4 結(jié) 論

1)經(jīng)典粗糙集中的不可區(qū)分關(guān)系對(duì)解決多屬性和準(zhǔn)則定序分類問題能力較弱.

2)本文把經(jīng)典粗糙集中的不可區(qū)分關(guān)系擴(kuò)展為“不可區(qū)分-相似-優(yōu)勢(shì)”關(guān)系，實(shí)例表明該關(guān)系不但能夠解決此問題而且還能處理決策表中可能存在的不一致現(xiàn)象，同經(jīng)典粗糙集中的不可區(qū)分關(guān)系相比具有較好的有效性與優(yōu)越性.

［1］GRECO S，MATARAZZO B，SLOWINSKI R.Rough sets theory for multicriteria decision analysis［J］.European Journal of Operational Research，2001，129(1):1-47.

［2］GRECO S，MATARAZZO B，SLOWINSKI R.Rough sets methodology for problems in presence of multiple attributes and criteria［J］.European Journal of Operational Research，2002，138(2):247-259.

［3］BELACEL N.Multicriteria assignment method:Methodology and medical applications［J］.European Journal of Operational Research，2000，125(1):175-183.

［4］ZOPOUNIDIS C，DOUMPOS M.Multicriteria classification and sorting methods:A literature review［J］.European Journal of Operational Research，2002，138(2):229-246.

［5］胡壽松，何亞群.粗糙決策理論與應(yīng)用［M］.北京:北京航空航天大學(xué)出版社，2006:23-33.

［6］GRECO S，SLOWINSKI R，STEFANOWSKI J，et al.Incremental versus non-incremental rule induction for multicriteria classification［C］//Transactions on Rough Sets II.Berlin Heidelberg:Springer-Verlag，2004:33-53.

［7］DEMBCZYNSKI K，GRECO S，SLOWINSKI R.Secondorder rough approximations in multi-criteria classification with imprecise e-valuations and assignments［C］//RSFDGRC 2005.Berlin Heidelberg:Springer-Verlag，2005:54-63.

［8］BLASZCZYNSKI J，DEMBCZYNSKI K，SLOWINSKI R.Interactive analysis of preference-ordered data using dominance-based rough set approach［C］//ICAISC 2006.Berlin Heidelberg:Springer-Verlag，2006:489-498.

［9］ZARAS K，THIBAULT J.Ranking by rough approximation of preferences for decision engineering applications［C］//RSKT2007.Berlin Heidelberg:Springer-Verlag，2007:142-148.

［10］LI Ming，ZHANG Baowei，WANG Tong，et al.Approximation of class unions based dominance-matrix within dominance-based rough set approach［C］//ACII2005.Berlin Heidelberg:Springer-Verlag，2005:795-802.

［11］ZARAS K.Rough approximation of a preference relation by a multi-attribute stochastic dominance for determinist and stochastic and fuzzy problems［J］.European Journal of Operational Research，2004，159(1):196-206.

［12］SHAO Mingwen，ZHANG Wenxiu.Dominance relation and rules in an incomplete ordered information system［J］.International Journal of Intelligent Systems，2005，20(1):13-27.

［13］JIA Xiuyi，SHANG Lin，JI Yangsheng，et al.An incremental updating algorithm for core computing in dominance-based rough set model［C］//RSFDGrC2007.Berlin Heidelberg:Springer-Verlag，2007:403-410.

［14］YUE Chaoyuan，YAO Shengbao，ZHANG Peng，et al.Rough approximation of a preference relation for stochastic multi-attribute decision problems［C］//FSKD 2005.Berlin Heidelberg:Springer-Verlag，2005:242-1245.

［15］桂現(xiàn)才.優(yōu)勢(shì)關(guān)系下信息系統(tǒng)的信息量與粗糙熵［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29(24):6340-6343.

［16］賈修一，于紹越，商琳，等.基于優(yōu)勢(shì)關(guān)系的粗糙集應(yīng)用研究［J］.計(jì)算機(jī)科學(xué)，2008，35(8):901-904.

［17］徐偉華，張文修.基于優(yōu)勢(shì)關(guān)系下信息系統(tǒng)分配約簡(jiǎn)的矩陣算法［J］.計(jì)算機(jī)工程，2007，33(14):4-7.

［18］袁修久，何華燦.優(yōu)勢(shì)關(guān)系下的相容約簡(jiǎn)和下近似約簡(jiǎn)［J］.西北工業(yè)大學(xué)學(xué)報(bào)，2006，24(5):604-608.

［19］趙越嶺，王建輝，顧樹生.基于優(yōu)勢(shì)關(guān)系粗糙集的數(shù)據(jù)分類［J］.控制工程，2007，14(3):51-54.