關系矩陣的知識粒度增量式屬性約簡

鄭 誠,王 波,洪彤彤

(安徽大學 計算智能與信號處理教育部重點實驗室,合肥 230601)(安徽大學 計算機科學與技術學院,合肥 230601)

1 引 言

屬性約簡是智能信息處理中一項重要的數(shù)據(jù)預處理方法,目前已廣泛運用于模式識別和機器學習等領域中[1-4].屬性約簡旨在保證較高的分類精度情形下盡可能消除數(shù)據(jù)中不相關的屬性,從而達到降低數(shù)據(jù)規(guī)模,提高學習效率的目的[4].而在如今的大數(shù)據(jù)背景下,數(shù)據(jù)是不斷動態(tài)增加變化的,傳統(tǒng)的屬性約簡算法大多基于靜態(tài)數(shù)據(jù)構建,處理動態(tài)數(shù)據(jù)效率將變得較為低下[5].因此傳統(tǒng)的方法在新環(huán)境背景下面臨著一定的挑戰(zhàn).

屬性的增加是數(shù)據(jù)集動態(tài)變化中一種常見的情形.針對這類問題,學者們作了很多深入的研究,并提出了大量的增量式屬性約簡算法,這些算法大多分為兩大類.第一類是基于粗糙集理論的正區(qū)域增量式約簡,如尹林子[6]等學者利用標記可辨識矩陣構造出增量式約簡算法,龍浩[7]等學者將信息系統(tǒng)的差別矩陣進行改進,提出了相應的增量式約簡算法.第二類是基于信息熵理論的增量式約簡.如劉海濤[8]等學者提出基于信息觀下的增量式屬性約簡,劉薇[9]等學者在基于條件熵理論提出了相應的屬性約簡算法,Wang[10]等學者也提出了類似的算法.

近年來,知識粒度作為一種新的屬性約簡方式受到研究人員們的關注[11].而在目前的增量式約簡算法中,矩陣是一種強有力的分析數(shù)據(jù)的結構形式[6,7,12,13],因此本文將矩陣形式融入到知識粒度中[12],運用關系矩陣來表示知識粒度,當數(shù)據(jù)集屬性增加時,通過矩陣的視角來展示知識粒度的變化機制,并基于這種方法構造出了本文的增量式屬性約簡,最后的實驗分析表明了本文所提出的增量式算法的高效性.

2 基本理論

定義1[14].一個信息系統(tǒng)可以描述成一個三元組IS=(U,A,V)的形式,這里的U被稱為論域,A為非空有限屬性集,并且?a∈A存在映射:U→Va,Va被稱為屬性a的值域,對象x∈U在屬性a下的取值可表示為a(x)=va,va∈Va.當信息系統(tǒng)IS中A=C∪D,且C∩D=φ,這里的C稱為條件屬性集,D稱為決策屬性集,那么這個信息系統(tǒng)又被稱為決策信息系統(tǒng),表示為DIS.

對于信息系統(tǒng)IS=(U,A,V),設B?A,定義等價關系

R(B)={(x,y)∈U×U|?a∈B,a(x)=a(y) }.

顯然,R(B)=∩a∈BR({a}).通過等價關系R(B)可以對論域U誘導出一個劃分,表示為U/R(B),U/R(B)中的每個元素被稱為等價類.U/R(B)被稱為U上的信息,并且其中的每個等價類被稱為信息粒.

定義2[15].對于信息系統(tǒng)IS=(U,A,V),|U|=n,B?A,由等價關系R(B)在U上誘導的粒結構定義為

K(B)=(X1,X2,…,Xn).

這里的|·|表示集合的基數(shù),Xi(1≤i≤n)表示對象xi在等價關系R(B)下的等價類.

定義3[15].對于信息系統(tǒng)IS=(U,A,V),|U|=n,B?A,由等價關系R(B)在U上誘導的粒結構為K(B),那么信息系統(tǒng)IS基于K(B)的知識粒度定義為

性質1.對于信息系統(tǒng)IS=(U,A,V),|U|=n,B2?B1?A誘導的等價關系為R(B2),R(B1),其對應的粒結構為K(B2),K(B1),那么知識粒度滿足關系

GK(B1)≤GK(B2).

定義4[16].對于決策信息系統(tǒng)DIS=(U,C∪D,V),B1?B2?C,由B1導出的粒結構為K(B1),B2導出的粒結構為K(B2),那么定義B1關于B2的相對知識粒度為

GK(B2|B1)=GK(B1)-GK(B2).

由于知識粒度的單調性,目前相對知識粒度已被用于構造信息系統(tǒng)的屬性約簡中.

定義5[16].對于決策信息系統(tǒng)DIS=(U,C∪D,V),B?C是該信息系統(tǒng)的一個相對約簡當且僅當兩點成立:

1)GK(D|C)=GK(D|B);

2)?a∈B,GK(D|B-{a} )≠GK(D|B).

3 知識粒度的增量式屬性約簡

3.1 知識粒度的矩陣形式表示

為了能直觀的展示出知識粒度的度量,Zhang[17]等學者提出了矩陣形式的知識粒度表達,這為本文的知識粒度增量式屬性約簡的構造建立了結構基礎.

定義6[17].對于信息系統(tǒng)IS=(U,A,V),|U|=n,B?A在U上誘導等價關系為R(B),那么等價關系矩陣MB定義為

這里的xi,xj∈U,可以看出,若針對屬性集B,對象xi,xj同屬于一個等價類,那么在等價關系矩陣的對應位置值為1,否則為0.為了簡便,下文中等價關系矩陣簡稱為關系矩陣.

例1.設信息系統(tǒng)IS=(U,A,V)如表1所示,其中A={a,b,c}.

表1 信息系統(tǒng)Table 1 Information system

根據(jù)定義6,此信息系統(tǒng)的等價關系矩陣MA為

在定義3中,知識粒度通過集合的基數(shù)來表示,根據(jù)定義6,這里可以給出知識粒度的另一種表示方式.

定義7.對于信息系統(tǒng)IS=(U,A,V),|U|=n,B?A在U上等價關系矩陣為MB,那么基于R(B)的知識粒度為

例2.(繼續(xù)例1)信息系統(tǒng)IS=(U,A,V)基于等價關系R(A)的知識粒度為

可以看出,知識粒度表示的是非零元素個數(shù)占總個數(shù)的比例.那么根據(jù)定義4,我們可以給出另一種相對知識粒度的定義方法.

定義8.對于決策信息系統(tǒng)DIS=(U,C∪D,V),B1?B2?C,定義B1關于B2的相對知識粒度為

通過定義8可以看出,B1,B2之間的相對知識粒度即為它們矩陣中元素變化數(shù)量占總個數(shù)的比例.

例3.(繼續(xù)例1)設B1={a,c},B2={a,b,c},那么B1關于B2的相對知識粒度為

定義9.對于決策信息系統(tǒng)DIS=(U,C∪D,V),B?C,?a∈C-B在B下關于D的屬性重要度為

SIG(a,B,D)

=GK(D|B)-GK(D|B∪{a} )

由于現(xiàn)實中的數(shù)據(jù)是不斷變化的,當信息系統(tǒng)中的屬性開始增加時,為了避免重復計算,我們需要探究增加屬性后,知識粒度在矩陣視角的變化機制.

定義10.對于信息系統(tǒng)IS=(U,A,V),等價關系R(A)導出的關系矩陣為MA,當增加屬性集ΔA進入信息系統(tǒng)時,此時信息系統(tǒng)變?yōu)镮S=(U,A′,V),設等價關系R(ΔA)導出的關系矩陣為MΔA,那么R(A′)對應的關系矩陣MA′為

并且,定義變化關系矩陣ΔMΔA為

變化關系矩陣ΔMΔA表示了MA至MA′變化情況,其ΔMΔA中值為1的元素表示從MA至MA′值發(fā)生了變化.具體如例4所示.

例4.設信息系統(tǒng)IS=(U,A,V),其中A={a,c}如表1所示,增加屬性ΔA={b},A′={a,b,c}.那么

觀察可以發(fā)現(xiàn),從MA至MA′,值有6處發(fā)生變化,這6處與ΔMΔA非零元素值位置一一對應.因此ΔMΔA中非零元素之和可以表示增加屬性集ΔA后,原先關系矩陣中元素的變化數(shù)量.這是本文所提增量式屬性約簡的關鍵.

性質2.對于信息系統(tǒng)IS=(U,A,V),|U|=n,屬性集A導出的關系矩陣為MA,增加屬性集ΔA進入信息系統(tǒng),此時信息系統(tǒng)變?yōu)镮S=(U,A′,V),A′導出的關系矩陣為MA′,變化關系矩陣為ΔMΔA,那么知識粒度滿足

其中∑ΔMΔA表示變化關系矩陣的元素值之和.

證明:通過定義10可以直接得到.

性質3.對于決策信息系統(tǒng)IS=(U,A=C∪D,V),|U|=n,屬性集A導出的關系矩陣為MA,增加屬性集ΔA進入信息系統(tǒng),此時信息系統(tǒng)變?yōu)镮S=(U,A′,V),A′導出的關系矩陣為MA′,變化關系矩陣為ΔMΔA,那么相對知識粒度滿足

證明:根據(jù)定義4有

通過性質3可以發(fā)現(xiàn),對于增加屬性之后的信息系統(tǒng),我們只需要進行變化關系矩陣的相關運算,即計算∑ΔMA-∑ΔMA∪D,對于GK(D|A)在原先數(shù)據(jù)集已經計算得到,因此就不必進行重復計算,從而降低了時間開銷.

3.2 知識粒度的增量式屬性約簡算法

對于初始時的決策信息系統(tǒng)DIS=(U,C∪D,V),我們基于知識粒度采用常用的重要度方法來構造初始屬性約簡算法.具體如算法1所示.

算法1.關系矩陣的知識粒度初始屬性約簡

輸入:DIS=(U,C∪D,V).

輸出:約簡集redC,知識粒度GKC.

1.初始化redC=φ,GK(D|redC)=1

2.whileGK(D|redC)≠GK(D|C)do

3.for?ai∈C-redCdo

4. 計算SIG(ai,redC,D).

5.endfor

6.選擇ak滿足SIG(ak,redC,D)=max(SIG(ai,redC,D)).

7.ifSIG(ak,redC,D)>0then

8.redC←redC∪{ak}.

9.else

10.returnredC,GK(D|C).

11.endwhile

設|C|=c,|U|=n,那么算法1的時間復雜度為O(c2·n2).根據(jù)算法1的結果,當信息系統(tǒng)增加新的屬性集時,這里給出增量式屬性約簡算法,具體如算法2所示.

算法2.關系矩陣知識粒度增量式屬性約簡(IARRMKG)

輸入:DIS=(U,C∪D,V),redC,GK(D|C),增加的屬性集ΔC

輸出:redC′,GK(D|C′ ),這里令C∪ΔC=C′

1.初始化redC′=redC

2.根據(jù)GK(D|C)計算GK(D|C′ )//性質3

3.ifGK(D|redC′)≠GK(D|C′ )then

4.whileGK(D|redC′)≠GK(D|C′ )do

5.for?ai∈C′-redC′do

6.計算SIG(ai,redC′,D).

7.endfor

8.選擇ak滿足SIG(ak,redC′,D)=max(SIG(ai,redC′,D)).

9.ifSIG(ak,redC′,D)>0then

10.redC′←redC′∪{ak}.

11.else

12.returnredC′,GK(D|C′ ).

13.endwhile

14.else

15.returnredC′,GK(D|C′ ).

設|ΔC|=Δc,|U|=n,那么算法2的時間復雜度為O(Δc2·n2).如果對于新增加的屬性集,我們仍然按照算法1來計算約簡集,那么時間復雜度為O((c+Δc)2·n2),因此本文所提出的增量式屬性約簡算法大大減小了時間的開銷.

4 實驗分析

本節(jié)將通過一系列實驗來驗證本文所提出的增量式屬性約簡算法更具一定的優(yōu)越性.首先,我們在UCI數(shù)據(jù)庫中選取5個數(shù)據(jù)集,如表2所示.然后,本實驗中選取了3個目前已有的增量式屬性約簡算法,它們分別為:基于概率粗糙集的增量式屬性約簡(IARPRS)[18],基于知識粒度的增量式屬性約簡(IARKG)[11]和基于信息熵的增量式屬性約簡(IARIE)[10].最后讓已有的3種算法和本文所提的算法分別進行實驗,通過實驗結果驗證本文所提算法的優(yōu)越性.

在表2中,數(shù)據(jù)集sonar和musk為數(shù)值型數(shù)據(jù),因而在實驗前需要進行離散化處理,本實驗采用等頻離散化法.在實驗中需要進行分類精度的計算,這里我們選用支持向量機分類器(SVM).實驗運行的硬件環(huán)境為CPU Intel core i5 630 3.2GHz和4GB內存的PC機,實驗的編程語言為Java.

表2 UCI數(shù)據(jù)集Table 2 UCI data sets

由于這4種算法均為增量式屬性約簡,本實驗將所有數(shù)據(jù)集按照屬性隨機分成4份,然后通過每次添加一份來模擬數(shù)據(jù)集屬性動態(tài)的增加,并同時讓這4種算法分別對動態(tài)變化的數(shù)據(jù)集進行屬性約簡,并得到相應的約簡結果,為了驗證最終屬性約簡結果的優(yōu)越性,本實驗運用SVM分類器通過十折交叉驗證計算約簡集的分類精度,所有數(shù)據(jù)集的最終約簡集大小和對應的分類精度如表3所示,表中的列名CA表示分類精度.

表3 約簡大小和分類精度比較Table 3 Comparison of size reduction and classification accuracy

注:表中的mushr代表mushroom

圖1 mushroom的運算時間Fig.1 mushroom calculation time

圖2 soybean的運算時間Fig.2 soybean calculation time

圖3 sonar的運算時間Fig.3 sonar calculation time

通過觀察表3可以看出,對于約簡集的結果,本文提出的IARRMKG算法在大部分數(shù)據(jù)集中的實驗結果中均是最小的,對于約簡集對應的分類精度,除了musk數(shù)據(jù)集,IARRMKG算法的約簡結果在其余的數(shù)據(jù)集的分類精度達到最高.因此,IARRMKG算法可以在較高的分類精度下選擇出盡可能小約簡集.

算法的時間復雜度是衡量算法好壞的一項重要的指標,為了驗證本文提出的IARRMKG算法在屬性約簡效率方面的優(yōu)越性,圖1-圖5所示的是4種算法在各個數(shù)據(jù)集上每次數(shù)據(jù)集增加時的計算耗時.為了減小實驗的誤差,所有的結果取3次實驗的平均值.觀察圖1-圖5中每個數(shù)據(jù)集的結果,可以很明顯的發(fā)現(xiàn),隨著數(shù)據(jù)集的屬性逐漸增多,每次約簡的時間消耗是逐漸增多的,但是IARRMKG算法的計算用時明顯低于其它3種算法,這是由于本文所提出的算法利用關系矩陣的形式進行數(shù)據(jù)集知識粒度的計算,當數(shù)據(jù)集發(fā)生變化時,可以減少很多的重復計算,降低了時間消耗.因此本文的算法在計算效率方法仍然有較高的優(yōu)勢.

5 結 語

由于現(xiàn)實中的數(shù)據(jù)集是不斷動態(tài)變化的,傳統(tǒng)的屬性約簡算法在進行屬性約簡時會產生很多的重復計算.本文在前人的工作基礎上,首先引入關系矩陣來表示信息系統(tǒng)的知識粒度,當數(shù)據(jù)集的屬性發(fā)生變化時,運用關系矩陣來描述信息系統(tǒng)中知識粒度的機制,然后我們基于這種變化機制提出了

圖4 ticdata的運算時間Fig.4 ticdata calculation time

圖5 musk的運算時間Fig.5 musk calculation time

信息系統(tǒng)的增量式屬性約簡算法,最后我們進行一系列實驗證明了該算法在動態(tài)變化數(shù)據(jù)集上屬性約簡的有效性.在未來的研究工作中,我們將進一步研究當信息系統(tǒng)數(shù)據(jù)量變化時的高效屬性約簡方法.

：

[1] Shao Ming-wen,Li Ke-wen.Attribute reduction in generalized one-sided formal contexts[J].Information Sciences,2016,378(1):317-327.

[2] Li Hua,Li De-yu,Zhai Yan-hui,et al.A novel attribute reduction approach for multi-label data based on rough set theory[J].Information Sciences,2016,367-368:827-847.

[3] Dai Jian-hua,Han Hui-feng,Hu Qing-hua,et al.Discrete particle swarm optimization approach for cost sensitive attribute reduction[J].Knowledge-Based Systems,2016,102(C):116-126.

[4] Ma Xi-ao,Wang Guo-yin,Yu Hong.Heuristic attribute reduction method of decision domain[J].Software Journal,2014(8):1761-1780.

[5] Ji Su-qing,Shi Hong-bo,Lv Ya-li.Attribute reduction algorithm based on granular computing and distinguishing ability[J].Pattern Recognition and Artificial Intelligence,2015,28(4):327-334.

[6] Yin Lin-zi,Yang Chun-hua,Wang Xiao-li,et al.Incremental attribute reduction algorithm based on discernibility matrix[J].Automation Journal,2014,40 (3):397-404.

[7] Long Hao,Xu Chao.Incremental updating algorithm for attribute reduction based on improved discernibility matrix [J].Computer Science,2015,42(6):251-255.

[8] Liu Hai-tao,Xu Xing-ying,Xie Jun,et al.Research on incremental attribute reduction method of [J].Micro Computer System Information,2016,37(2):375-380.

[9] Liu Wei,Liang Ji-ye,Wei Wei,et al.A scientific conditional entropy incremental algorithm for attribute reduction based on [J].Computer Science,2011,38(1):229-231.

[10] Wang Feng,Liang Ji-ye,Qian Yu-hua.Attribute reduction:A dimension incremental strategy[J].Knowledge-Based Systems,2013,39(2):95-108.

[11] Jing Yun-ge,Li Tian-rui.An incremental approach for reduction based on knowledge granularity[J].Journal of Shandong University,2016,46(1):1-9.

[12] Wang Lei,Li Tian-rui.A matrix based knowledge granularity computing method [J].Pattern Recognition and Artificial Intelligence,2013,25(5):447-453.

[13] Jing Yun-ge.A new incremental reduction algorithm for decision table based on relational matrix [J],Micro Computer System Information,2015,36(5):1069-1072.

[14] Pawlak Z.Rough sets[J].International Journal of Parallel Programming,1982,11(5):341-356.

[15] Huang Bing,Guo Chun-xiang,Li Hua-xiong,et al.Hierarchical structures and uncertainty measures for intuitionistic fuzzy approximation space[J].Information Sciences,2015,336(C):92-114.

[16] Xu Jiu-cheng,Shi Jin-ling,Sun Lin.Attribute reduction algorithm based on relative granularity in decision tables[J].Computer Science,2009,36(3):205-207.

[17] Zhang Jun-bo,Li Tian-rui,Da Ruan,et al.Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems[J].International Journal of Approximate Reasoning,2012,53(4):620-635.

[18] Liu Dun,Li Tian-rui,Jun Bo.Incremental updating approximations in probabilistic rough sets under the variation of attributes[J].Knowledge-Based Systems,2015,73(81):81-96.

附中文參考文獻：

[4] 馬希驁,王國胤,于 洪.決策域分布保持的啟發(fā)式屬性約簡方法[J].軟件學報,2014(8):1761-1780.

[5] 冀素琴,石洪波,呂亞麗.基于粒計算與區(qū)分能力的屬性約簡算法[J].模式識別與人工智能,2015,28(4):327-334.

[6] 尹林子,陽春華,王曉麗,等.基于標記可辨識矩陣的增量式屬性約簡算法[J].自動化學報,2014,40(3):397-404.

[7] 龍 浩,徐 超.基于改進差別矩陣的屬性約簡增量式更新算法[J].計算機科學,2015,42(6):251-255.

[8] 劉海濤,續(xù)欣瑩,謝 珺,等.信息觀下增量式屬性約簡方法研究[J].小型微型計算機系統(tǒng),2016,37(2):375-380.

[9] 劉 薇,梁吉業(yè),魏 巍,等.一種基于條件熵的增量式屬性約簡算法[J].計算機科學,2011,38(1):229-231.

[11] 景運革,李天瑞.基于知識粒度的增量約簡算法[J].山東大學學報(工學版),2016,46(1):1-9.

[12] 王 磊,李天瑞.一種基于矩陣的知識粒度計算方法[J].模式識別與人工智能,2013,25(5):447-453.

[13] 景運革.一種基于關系矩陣決策表增量式約簡算法[J].小型微型計算機系統(tǒng),2015,36(5):1069-1072.

[16] 徐久成,史進玲,孫 林.一種基于相對粒度的決策表約簡算法[J].計算機科學,2009,36(3):205-207.