基于優勢關系區別矩陣的一種增量求核方法
2008-12-31 00:00:00石為人李偉湋賈修一
計算機應用研究 2008年7期
摘 要：現實中很多數據是增量出現的，就需要對數據進行增量的處理，為此，給出了一種基于優勢區分矩陣的增量求核算法，通過修改矩陣的某一行或某一列來增量得到決策表的核。通過實驗驗證了算法的有效性。
關鍵詞：粗糙集; 增量更新; 優勢區分矩陣; 核
中圖分類號：TP181 文獻標志碼：A
文章編號：1001-3695(2008)07-2050-03
Improvement of dominance discernibility matrixand incremental computation of core
SHI Weiren1，LI Weiwei1，JIA Xiuyi2
(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 dominancebased rough set model， which extended previous reduct studies in capability of dynamic updating and dominance relation. Then redefined the dominance discernibility 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
粗糙集理論是一種新的處理不精確、不完全與不相容知識的數學理論[1]。粗糙集理論已在數據挖掘、機器學習與模式識別等領域得到了廣泛的應用。由于現實數據中存在各種偏好信息，Greco等人擴展了傳統粗糙集方法，提出了基于優勢關系的粗糙集方法DRSA(dominance based rough set approach )。在粗糙集理論中，屬性約簡是一個重要的研究內容之一，受到很多粗糙集研究者的關注[2~4]。而很多屬性約簡都是從核開始的，因此求核成了屬性約簡求解的關鍵步驟。
傳統粗糙集方法中，差別矩陣是一個重要的概念，利用差別矩陣求核是常用的約簡方法。由于優勢關系是一種不同于不可區分關系的非對稱關系，使得該模型不能利用差別矩陣來求核和約簡。文獻[5]中提出了利用類區分矩陣的概念。由于該矩陣定義沒有考慮不一致數據的存在，只能適用于對一致數據的求核。文獻[6]提出一種改進的方法，給出了一個新的優勢區分矩陣的定義和求核方法。但該方法除了具有與文獻[5]的方法同樣的存儲空間外，還在定義優勢區分矩陣中的每個矩陣元素時增加了計算的復雜度。文獻[7]提出一種新的優勢區分矩陣的定義和求核方法，能降低時間復雜度。
1 優勢關系粗糙集理論概念
1．1 優勢關系粗糙集定義
現實中很多屬性是具有偏好信息的，如對評價學生是否優秀的德育成績、智育成績等屬性，決策類別也可以表達偏好，如決策者將破產風險分為高風險、中風險及低風險等級別。通常將具有偏好信息的屬性稱為標準，把在知識發現過程中考慮標準屬性的偏好信息的問題稱為多標準問題[8]。經典粗糙集方法在多標準決策問題中的最早應用是利用其來描述屬性之間的依賴度、計算屬性的重要度和處理不一致數據信息[1]。由于經典粗糙集中只考慮屬性值的是否可區分性，而不考慮其偏好關系，并不能很好地在決策過程中表達其原有的偏好信息。S. Greco等人[9]提出的基于優勢關系的粗糙集方法（DRSA）卻很好地解決了該問題，彌補了經典粗糙集在解決該類問題時的缺陷。
定義1[9] 信息系統S=〈U，Q，V，f〉。其中：U為論域；Q為屬性集，它通常分為條件屬性集C和決策屬性集D；V=∪q∈QVq，這里Vq是屬性q的值域; f:U×Q→V是對任意q×Q，x∈U有f(x，q)∈Vq的映射函數。
解決多標準決策問題通常還要作如下假設：根據決策屬性集D可將U劃分為有窮個數的類集合：Cl={Clt，t∈T}，T={1，…，n}，對任意x∈U屬于且只屬于其中的一個分類Clt∈Cl。
定義2[9] 分類的上聯合和下聯合：Cl≥t=∪s≥tCls；
Cl≤t=∪s≤tCls，t=1，…，n。其中根據決策屬性劃分的類集合也是有序的，也就是說對所有的r，s∈T，若r＞s，則Clr中的對象從決策角度來看要優于Cls中的對象。
經典粗糙集中的不可分辨關系也由優勢關系所替代。
1．2 約簡和核
下面給出基于優勢關系粗糙集的約簡和核的定義。
定義6[9] 決策類D關于條件屬性集屬性PC的近似分類質量：
γP(D)=|U-∪Nn=1BnP(d≥n)|/|U|=|U-∪Nn=1BnP(d≤n)|/U
定義7[9] 設PC，如果滿足γP=γC且對任意RP，有γR≠γC，則稱P是C的一個約簡。所有約簡的交集稱之為核，記為Core(C)。
定義8[9] 如果屬性a∈C滿足γC-{a}＜γC，則稱a是不可或缺的；否則，稱屬性是冗余的。
性質1[9] 屬性a∈core(C)當且僅當屬性a是不可或缺的屬性。
2 已有優勢關系下的區分矩陣
為克服通過求出所有的不可缺少屬性來確定核方法的不足，很多學者對通過差別矩陣求核進行了大量的研究，并取得了很好的效果[2，10]。文獻[5]中提出了類區分矩陣的概念，類區分矩陣M1={a(xi，xj)}定義為
在文獻[6]中，通過表1中的例子證明用該定義進行求核是錯的。按照該定義求核得core(C)={C1，C2，C3}，而依據核的定義可知core(C)={C1}。出錯的原因在于決策表中存在不一致數據：x2和x3，x4和x5。為解決該問題，文獻[6]提出一種優勢區分矩陣定義來計算核。
定義9[6] 對給定的信息系統IS，定義優勢區分矩陣為M2={a#(xi，xj)}：
文獻[6]給出并證明了如下結論：對于給定的信息系統，若記A(C)={a#(xi，xj):a#(xi，xj)}為單個屬性，則有A(C)=core(C)，即當且僅當某個a#(xi，xj)為單個屬性時，該屬性屬于核core(C)。
可以看出，文獻[6]方法能夠解決數據表中存在不一致數據的情況，但在構造區分矩陣時，對每個矩陣元素都要作出判斷，計算代價高。
3 改進的優勢關系下的區分矩陣及增量求核方法
在另一篇文章[7]中筆者給出了一種改進的優勢關系下區分矩陣的定義。
定義10 對給定的信息系統IS，定義優勢區分矩陣為M={a#(xi，xj)}。
在文獻[7]中已經給出了該定理的證明。
為了簡化討論，假設動態增加對象時決策表中決策屬性的取值為1，…，n不變。對于對象x和y，若兩者有相同的條件屬性取值和不同的決策屬性取值，則稱x與y是不一致的。反之就是一致的；設U1=C(Cl≤n-1)∪C(Cl≥2)，對新增加的對象x，如果任意y∈U1，x與y都是一致的，則稱x與U1是一致的；若存在y∈U1，x與y不一致，則稱x與U1是不一致的。
對輸入的U1=C(Cl≤n-1)∪C(Cl≥2)，可以根據定義10求得優勢區別矩陣M2，對新增加的對象x，只要求出U1∪U∪{x}的矩陣M2(x)，再根據定理1求核即可。所以增量求核問題就轉換為增量更新優勢關系區別矩陣的問題。設U2是不一致數據的集合，M2的更新有下面三種情況：
a)如果x與U1是一致的，xU2且對任意的y∈U1都不存在x=y，則只要在矩陣中增加x相應的一行和一列即可，U1=U1∪{x}。
b)如果x與U1是一致的，存在x∈U2或存在y∈U1，使得x=y，則M2不變。
c)如果x與U1不一致，即存在y∈U1，x與y不一致，則刪除y對應行，修改對應列，U1=U1-{y}，U2=U2+{x，y}。
根據以上描述，給出增量求核算法如下。
輸入：a)U1=C(Cl≤n-1)∪C(Cl≥2)，不一致數據集合U2，優勢區別矩陣M2；b)新增加對象x。
輸出：M2(x)和core(C)。
4 實驗結果
4．1 空間和時間復雜度
a)空間復雜度。筆者改進的優勢矩陣中元素個數是|U1|×|U|，而文獻[5，6]定義的矩陣元素個數都是|U|×|U|。
b)時間復雜度比較。新增加一個對象x時，最多只需(|U1|+|U|)步操作來判斷x與U1是否一致，(|U1|+|U|)步操作來更新矩陣，(|U1|+1)+(|U|+1)步掃描矩陣求核。所以增量算法的時間復雜度是O(|U1|×|U|)。
4．2 實驗結果
為進一步驗證算法的性能，在CPU為Pentium(R) D-2.8 GHz CPU，內存為512 MB，操作系統為Windows XP的機器上，用C#語言實現文獻[6]和本文的算法。數據集選取UCI數據集[11]中的iris和mushroom兩個數據集。對iris數據集，選取前100個數據求優勢矩陣，依次動態增加20、50個對象。Mushroom數據集選取前800個作為優勢矩陣的輸入，依次動態增加200、400個對象。實驗結果如表2所示。實驗數據集名稱后面數字分表代表數據集的記錄數、條件屬性個數和決策類別數，時間單位為s。
通過表2可見，本文的增量算法性能要優于文獻[6]的算法，因為只需對已存在的矩陣進行簡單的更新即可。該算法在保證正確的同時，執行時間要少很多。
5 結束語
本文提出一種基于改進優勢區分矩陣的增量求核方法，在保證對不一致數據處理的正確性基礎上，通過對矩陣的某一行或某一列進行修改操作，避免了動態增加對象時矩陣的重新構建，提高了求核效率，并通過對方法的復雜度分析和標準數據集上的實驗，驗證本算法的有效性。
參考文獻：
［1］PAWLAK Z.Rough set:theoretical aspects of reasoning about data[M]. Dordrecht: Kluwer Academic Publishers，1991.
[2]HU Xiaohua，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]苗奪謙，胡桂榮.知識約簡的一種啟發式算法[J].計算機研究與發展，1998，36(6):681-684.
[5]李克星.基于序關系的粗糙集[C]//中國人工智能進展2003:第10屆全國人工智能會議論文集.北京：北京：郵電大學出版社，2003:13591363.
[6]吳毅民，葉東毅.基于優勢關系的粗糙集中的一種求核算法[J].計算機科學，2004，31(10A):138139.
[7]JIA Xiuyi，SHANG Lin，LI Weiwei.An incremental updating algorithm for core computing in dominancebased rough set model[C]//Proc ofRSFDGrC2007，LNAI4482.2007:403-410.
[8]GRECO S， MATARAZZO B， SLOWINSKI R.Rough set approach to multiattribute 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]. 計算機學報，2006，29(3):407-413.
[11]UCI machine learning repository[EB/OL].http://www.ics.uci.edu/ ~mlearning/MLRepository.html.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>
