基于優(yōu)勢(shì)關(guān)系區(qū)別矩陣的一種增量求核方法

摘 要：現(xiàn)實(shí)中很多數(shù)據(jù)是增量出現(xiàn)的，就需要對(duì)數(shù)據(jù)進(jìn)行增量的處理，為此，給出了一種基于優(yōu)勢(shì)區(qū)分矩陣的增量求核算法，通過(guò)修改矩陣的某一行或某一列來(lái)增量得到?jīng)Q策表的核。通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的有效性。

關(guān)鍵詞：粗糙集; 增量更新; 優(yōu)勢(shì)區(qū)分矩陣; 核

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)07-2050-03



Improvement of dominance discernibility matrixand incremental computation of core

SHI Weiren1，LI Weiwei1，JIA Xiuyi2

(1.College of Automation， Chongqing University， Chongqing 400030， China;2.National Key Laboratory for Novel Software Technology， Dept. of Computer Science Technology， Nanjing University， Nanjing 210093， China)

Abstract:This paper analyzed incremental updating for core computing in a dominancebased rough set model， which extended previous reduct studies in capability of dynamic updating and dominance relation. Then redefined the dominance discernibility matrix and presented an incremental updating algorithm. In this algorithm， when new samples arrived， the proposed solution only involved a few modifications to relevant rows and columns in the dominance discernibility matrix instead of recalculation. Both of theoretical analysis and experimental results show that the algorithm is effective and efficient in dynamic computation.

Key words:rough set; incremental updating; dominance discernibility matrix; core



粗糙集理論是一種新的處理不精確、不完全與不相容知識(shí)的數(shù)學(xué)理論^[1]。粗糙集理論已在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)與模式識(shí)別等領(lǐng)域得到了廣泛的應(yīng)用。由于現(xiàn)實(shí)數(shù)據(jù)中存在各種偏好信息，Greco等人擴(kuò)展了傳統(tǒng)粗糙集方法，提出了基于優(yōu)勢(shì)關(guān)系的粗糙集方法DRSA(dominance based rough set approach )。在粗糙集理論中，屬性約簡(jiǎn)是一個(gè)重要的研究?jī)?nèi)容之一，受到很多粗糙集研究者的關(guān)注^[2~4]。而很多屬性約簡(jiǎn)都是從核開(kāi)始的，因此求核成了屬性約簡(jiǎn)求解的關(guān)鍵步驟。

傳統(tǒng)粗糙集方法中，差別矩陣是一個(gè)重要的概念，利用差別矩陣求核是常用的約簡(jiǎn)方法。由于優(yōu)勢(shì)關(guān)系是一種不同于不可區(qū)分關(guān)系的非對(duì)稱關(guān)系，使得該模型不能利用差別矩陣來(lái)求核和約簡(jiǎn)。文獻(xiàn)[5]中提出了利用類區(qū)分矩陣的概念。由于該矩陣定義沒(méi)有考慮不一致數(shù)據(jù)的存在，只能適用于對(duì)一致數(shù)據(jù)的求核。文獻(xiàn)[6]提出一種改進(jìn)的方法，給出了一個(gè)新的優(yōu)勢(shì)區(qū)分矩陣的定義和求核方法。但該方法除了具有與文獻(xiàn)[5]的方法同樣的存儲(chǔ)空間外，還在定義優(yōu)勢(shì)區(qū)分矩陣中的每個(gè)矩陣元素時(shí)增加了計(jì)算的復(fù)雜度。文獻(xiàn)[7]提出一種新的優(yōu)勢(shì)區(qū)分矩陣的定義和求核方法，能降低時(shí)間復(fù)雜度。

1 優(yōu)勢(shì)關(guān)系粗糙集理論概念

1．1 優(yōu)勢(shì)關(guān)系粗糙集定義

現(xiàn)實(shí)中很多屬性是具有偏好信息的，如對(duì)評(píng)價(jià)學(xué)生是否優(yōu)秀的德育成績(jī)、智育成績(jī)等屬性，決策類別也可以表達(dá)偏好，如決策者將破產(chǎn)風(fēng)險(xiǎn)分為高風(fēng)險(xiǎn)、中風(fēng)險(xiǎn)及低風(fēng)險(xiǎn)等級(jí)別。通常將具有偏好信息的屬性稱為標(biāo)準(zhǔn)，把在知識(shí)發(fā)現(xiàn)過(guò)程中考慮標(biāo)準(zhǔn)屬性的偏好信息的問(wèn)題稱為多標(biāo)準(zhǔn)問(wèn)題^[8]。經(jīng)典粗糙集方法在多標(biāo)準(zhǔn)決策問(wèn)題中的最早應(yīng)用是利用其來(lái)描述屬性之間的依賴度、計(jì)算屬性的重要度和處理不一致數(shù)據(jù)信息^[1]。由于經(jīng)典粗糙集中只考慮屬性值的是否可區(qū)分性，而不考慮其偏好關(guān)系，并不能很好地在決策過(guò)程中表達(dá)其原有的偏好信息。S. Greco等人^[9]提出的基于優(yōu)勢(shì)關(guān)系的粗糙集方法（DRSA）卻很好地解決了該問(wèn)題，彌補(bǔ)了經(jīng)典粗糙集在解決該類問(wèn)題時(shí)的缺陷。

定義1^[9] 信息系統(tǒng)S=〈U，Q，V，f〉。其中：U為論域；Q為屬性集，它通常分為條件屬性集C和決策屬性集D；V=∪q∈QVq，這里Vq是屬性q的值域; f:U×Q→V是對(duì)任意q×Q，x∈U有f(x，q)∈Vq的映射函數(shù)。

解決多標(biāo)準(zhǔn)決策問(wèn)題通常還要作如下假設(shè)：根據(jù)決策屬性集D可將U劃分為有窮個(gè)數(shù)的類集合：Cl={Clt，t∈T}，T={1，…，n}，對(duì)任意x∈U屬于且只屬于其中的一個(gè)分類Clt∈Cl。

定義2^[9] 分類的上聯(lián)合和下聯(lián)合：Cl≥t=∪s≥tCls；

Cl≤t=∪s≤tCls，t=1，…，n。其中根據(jù)決策屬性劃分的類集合也是有序的，也就是說(shuō)對(duì)所有的r，s∈T，若r＞s，則Clr中的對(duì)象從決策角度來(lái)看要優(yōu)于Cls中的對(duì)象。

經(jīng)典粗糙集中的不可分辨關(guān)系也由優(yōu)勢(shì)關(guān)系所替代。

1．2 約簡(jiǎn)和核

下面給出基于優(yōu)勢(shì)關(guān)系粗糙集的約簡(jiǎn)和核的定義。

定義6^[9] 決策類D關(guān)于條件屬性集屬性PC的近似分類質(zhì)量：

γP(D)=|U-∪Nn=1BnP(d≥n)|/|U|=|U-∪Nn=1BnP(d≤n)|/U

定義7^[9] 設(shè)PC，如果滿足γP=γC且對(duì)任意RP，有γR≠γC，則稱P是C的一個(gè)約簡(jiǎn)。所有約簡(jiǎn)的交集稱之為核，記為Core(C)。

定義8^[9] 如果屬性a∈C滿足γC-{a}＜γC，則稱a是不可或缺的；否則，稱屬性是冗余的。

性質(zhì)1^[9] 屬性a∈core(C)當(dāng)且僅當(dāng)屬性a是不可或缺的屬性。

2 已有優(yōu)勢(shì)關(guān)系下的區(qū)分矩陣

為克服通過(guò)求出所有的不可缺少屬性來(lái)確定核方法的不足，很多學(xué)者對(duì)通過(guò)差別矩陣求核進(jìn)行了大量的研究，并取得了很好的效果^[2，10]。文獻(xiàn)[5]中提出了類區(qū)分矩陣的概念，類區(qū)分矩陣M1={a(xi，xj)}定義為

在文獻(xiàn)[6]中，通過(guò)表1中的例子證明用該定義進(jìn)行求核是錯(cuò)的。按照該定義求核得core(C)={C1，C2，C3}，而依據(jù)核的定義可知core(C)={C1}。出錯(cuò)的原因在于決策表中存在不一致數(shù)據(jù)：x2和x3，x4和x5。為解決該問(wèn)題，文獻(xiàn)[6]提出一種優(yōu)勢(shì)區(qū)分矩陣定義來(lái)計(jì)算核。

定義9^[6] 對(duì)給定的信息系統(tǒng)IS，定義優(yōu)勢(shì)區(qū)分矩陣為M2={a#(xi，xj)}：

文獻(xiàn)[6]給出并證明了如下結(jié)論：對(duì)于給定的信息系統(tǒng)，若記A(C)={a#(xi，xj):a#(xi，xj)}為單個(gè)屬性，則有A(C)=core(C)，即當(dāng)且僅當(dāng)某個(gè)a#(xi，xj)為單個(gè)屬性時(shí)，該屬性屬于核core(C)。

可以看出，文獻(xiàn)[6]方法能夠解決數(shù)據(jù)表中存在不一致數(shù)據(jù)的情況，但在構(gòu)造區(qū)分矩陣時(shí)，對(duì)每個(gè)矩陣元素都要作出判斷，計(jì)算代價(jià)高。

3 改進(jìn)的優(yōu)勢(shì)關(guān)系下的區(qū)分矩陣及增量求核方法

在另一篇文章^[7]中筆者給出了一種改進(jìn)的優(yōu)勢(shì)關(guān)系下區(qū)分矩陣的定義。

定義10 對(duì)給定的信息系統(tǒng)IS，定義優(yōu)勢(shì)區(qū)分矩陣為M={a#(xi，xj)}。

在文獻(xiàn)[7]中已經(jīng)給出了該定理的證明。

為了簡(jiǎn)化討論，假設(shè)動(dòng)態(tài)增加對(duì)象時(shí)決策表中決策屬性的取值為1，…，n不變。對(duì)于對(duì)象x和y，若兩者有相同的條件屬性取值和不同的決策屬性取值，則稱x與y是不一致的。反之就是一致的；設(shè)U1=C(Cl≤n-1)∪C(Cl≥2)，對(duì)新增加的對(duì)象x，如果任意y∈U1，x與y都是一致的，則稱x與U1是一致的；若存在y∈U1，x與y不一致，則稱x與U1是不一致的。

對(duì)輸入的U1=C(Cl≤n-1)∪C(Cl≥2)，可以根據(jù)定義10求得優(yōu)勢(shì)區(qū)別矩陣M2，對(duì)新增加的對(duì)象x，只要求出U1∪U∪{x}的矩陣M2(x)，再根據(jù)定理1求核即可。所以增量求核問(wèn)題就轉(zhuǎn)換為增量更新優(yōu)勢(shì)關(guān)系區(qū)別矩陣的問(wèn)題。設(shè)U2是不一致數(shù)據(jù)的集合，M2的更新有下面三種情況：

a)如果x與U1是一致的，xU2且對(duì)任意的y∈U1都不存在x=y，則只要在矩陣中增加x相應(yīng)的一行和一列即可，U1=U1∪{x}。

b)如果x與U1是一致的，存在x∈U2或存在y∈U1，使得x=y，則M2不變。

c)如果x與U1不一致，即存在y∈U1，x與y不一致，則刪除y對(duì)應(yīng)行，修改對(duì)應(yīng)列，U1=U1-{y}，U2=U2+{x，y}。

根據(jù)以上描述，給出增量求核算法如下。

輸入：a)U1=C(Cl≤n-1)∪C(Cl≥2)，不一致數(shù)據(jù)集合U2，優(yōu)勢(shì)區(qū)別矩陣M2；b)新增加對(duì)象x。

輸出：M2(x)和core(C)。

4 實(shí)驗(yàn)結(jié)果

4．1 空間和時(shí)間復(fù)雜度

a)空間復(fù)雜度。筆者改進(jìn)的優(yōu)勢(shì)矩陣中元素個(gè)數(shù)是|U1|×|U|，而文獻(xiàn)[5，6]定義的矩陣元素個(gè)數(shù)都是|U|×|U|。

b)時(shí)間復(fù)雜度比較。新增加一個(gè)對(duì)象x時(shí)，最多只需(|U1|+|U|)步操作來(lái)判斷x與U1是否一致，(|U1|+|U|)步操作來(lái)更新矩陣，(|U1|+1)+(|U|+1)步掃描矩陣求核。所以增量算法的時(shí)間復(fù)雜度是O(|U1|×|U|)。

4．2 實(shí)驗(yàn)結(jié)果

為進(jìn)一步驗(yàn)證算法的性能，在CPU為Pentium(R) D-2.8 GHz CPU，內(nèi)存為512 MB，操作系統(tǒng)為Windows XP的機(jī)器上，用C#語(yǔ)言實(shí)現(xiàn)文獻(xiàn)[6]和本文的算法。數(shù)據(jù)集選取UCI數(shù)據(jù)集^[11]中的iris和mushroom兩個(gè)數(shù)據(jù)集。對(duì)iris數(shù)據(jù)集，選取前100個(gè)數(shù)據(jù)求優(yōu)勢(shì)矩陣，依次動(dòng)態(tài)增加20、50個(gè)對(duì)象。Mushroom數(shù)據(jù)集選取前800個(gè)作為優(yōu)勢(shì)矩陣的輸入，依次動(dòng)態(tài)增加200、400個(gè)對(duì)象。實(shí)驗(yàn)結(jié)果如表2所示。實(shí)驗(yàn)數(shù)據(jù)集名稱后面數(shù)字分表代表數(shù)據(jù)集的記錄數(shù)、條件屬性個(gè)數(shù)和決策類別數(shù)，時(shí)間單位為s。

通過(guò)表2可見(jiàn)，本文的增量算法性能要優(yōu)于文獻(xiàn)[6]的算法，因?yàn)橹恍鑼?duì)已存在的矩陣進(jìn)行簡(jiǎn)單的更新即可。該算法在保證正確的同時(shí)，執(zhí)行時(shí)間要少很多。

5 結(jié)束語(yǔ)

本文提出一種基于改進(jìn)優(yōu)勢(shì)區(qū)分矩陣的增量求核方法，在保證對(duì)不一致數(shù)據(jù)處理的正確性基礎(chǔ)上，通過(guò)對(duì)矩陣的某一行或某一列進(jìn)行修改操作，避免了動(dòng)態(tài)增加對(duì)象時(shí)矩陣的重新構(gòu)建，提高了求核效率，并通過(guò)對(duì)方法的復(fù)雜度分析和標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證本算法的有效性。

參考文獻(xiàn)：

［1］PAWLAK Z.Rough set:theoretical aspects of reasoning about data[M]. Dordrecht: Kluwer Academic Publishers，1991.

[2]HU Xiaohua，CERCONE N.Learning in relational databases:a rough set approach[J].Computational Intelligence，1995，11(2):323-338.

[3] JELONEK J，KRAWIEC K，SLOWINSKI R.Rough set reduction of attributes and their domains for neural networks[J].Computational Intelligence，1995，11(2):339-347.

[4]苗奪謙，胡桂榮.知識(shí)約簡(jiǎn)的一種啟發(fā)式算法[J].計(jì)算機(jī)研究與發(fā)展，1998，36(6):681-684.

[5]李克星.基于序關(guān)系的粗糙集[C]//中國(guó)人工智能進(jìn)展2003:第10屆全國(guó)人工智能會(huì)議論文集.北京：北京：郵電大學(xué)出版社，2003:13591363.

[6]吳毅民，葉東毅.基于優(yōu)勢(shì)關(guān)系的粗糙集中的一種求核算法[J].計(jì)算機(jī)科學(xué)，2004，31(10A):138139.

[7]JIA Xiuyi，SHANG Lin，LI Weiwei.An incremental updating algorithm for core computing in dominancebased rough set model[C]//Proc ofRSFDGrC2007，LNAI4482.2007:403-410.

[8]GRECO S， MATARAZZO B， SLOWINSKI R.Rough set approach to multiattribute choice and ranking problems，ICS Research Report 38/95[R].Warsaw：Warsaw University of Technology，1995.

[9]GRECO S，MATARAZZO B， SLOWINSKI R. Rough sets methodology for sorting problems in presence of multiple attributes and criteria[J].European Journal of Operational Research，2002，138（2）:247-259.[10]楊明.一種基于改進(jìn)差別矩陣的核增量式更新算法[J]. 計(jì)算機(jī)學(xué)報(bào)，2006，29(3):407-413.

[11]UCI machine learning repository[EB/OL].http://www.ics.uci.edu/ ~mlearning/MLRepository.html.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”