基于差別矩陣的屬性集求核算法

楊 濤， 張賢勇,2， 馮 山

(1.四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院 四川 成都 610066；2.四川師范大學(xué) 智能信息與量子信息研究所 四川 成都 610066)

0 引言

1 基本概念

定義1[4]決策表信息系統(tǒng)S=(U,C,D,V,F)中，b∈C，如果POSC(D)=POSC-(D)，則稱b為C中相對(duì)D不必要的；否則，稱b為C中相對(duì)D必要的.C中所有必要屬性的集合稱為C相對(duì)D的核，記為coreC(D).

命題1coreC(D)={α(α∈C)∧(?mij((mij∈IDM)∧(mij={α})∧mij=1))}.

定義2表明，差別矩陣算法求不相容決策表信息系統(tǒng)中核屬性時(shí)，首先將論域U中所有對(duì)象分為完全相容子論域U1與完全不相容子論域U2，其次將U1中對(duì)象兩兩比較，并將U1中的對(duì)象與U2中的對(duì)象兩兩比較，最后根據(jù)命題1從差別矩陣中找出簡單屬性(單個(gè)屬性).

2 基于差別矩陣的屬性集求核算法

2.1 差別矩陣的空值

根據(jù)定義2可知，差別矩陣求解核屬性時(shí)會(huì)出現(xiàn)空值，這些空值元素的出現(xiàn)會(huì)占用大量存儲(chǔ)空間，使得求核屬性浪費(fèi)了大量計(jì)算時(shí)間.因此，提出一種壓縮差別矩陣的構(gòu)造方法.

定理1(空值優(yōu)化) 在決策表信息系統(tǒng)S=(U,C,D,V,F)中，記相容子論域U1={x1,x2,…,xk}.當(dāng)?xi,xj∈U1∧F(xi,D)=F(xj,D)時(shí)，則忽略對(duì)象xi，xj的比較運(yùn)算.

證明因?xi,xj∈U1(1≤i≠j≤k)，所以信息系統(tǒng)S中，?b∈C存在如下關(guān)系：①F(xi,b)=F(xj,b);②F(xi,b)≠F(xj,b).由定義2知，當(dāng)?xi,xj∈U1,F(xi,d)≠F(xj,d)時(shí)，mij={b∈CF(xi,b)≠F(xj,b)}，否則，mij=?.因此，差別矩陣中的空值與條件屬性值的取值無關(guān)；顯然，當(dāng)?xi,xj∈U1∧F(xi,D)=F(xj,D)時(shí)，忽略對(duì)象xi，xj的比較運(yùn)算.

算法1空值優(yōu)化執(zhí)行過程.

輸入： 決策表S=(U,C,D,V,F)；輸出： 可以忽略比較的對(duì)象.

步驟1 得到完全相容子論域U1與完全不相容子論域U2,記U1={x1,x2,…,xU1};

步驟2 L=?;//L用于收集U1中可以忽略比較的對(duì)象；

步驟3 for (i=1;i

for (j=2;j≤U1;j++)

if(F( xi,D)=F(xj,D))

L=L∪{xi,xj};

步驟4 輸出L.

算法1以決策表信息系統(tǒng)中的決策屬性值D為劃分依據(jù)，將論域U劃分成相容子論域U1與不相容子論域U2，然后對(duì)U1中的對(duì)象按照決策屬性值的不同劃分成多個(gè)對(duì)象集，進(jìn)而減少當(dāng)決策屬性值相同時(shí)的不必要計(jì)算，同時(shí)也壓縮了差別矩陣中空值元素.一般情形下，算法1的時(shí)間復(fù)雜度為O(U12).在實(shí)際應(yīng)用中，上述算法雖然有2個(gè)循環(huán)，但是內(nèi)循環(huán)在循環(huán)過程中，當(dāng)對(duì)象xi與xj可以忽略比較，對(duì)象xi與xk(k≠j)可以忽略比較時(shí)，由傳遞性可得對(duì)象xj與xk可以忽略比較.因此,算法在執(zhí)行過程中減少了內(nèi)循環(huán)次數(shù)，即算法1的時(shí)間復(fù)雜度為O(U1).

2.2 差別矩陣的屬性集求核機(jī)理

在決策表信息系統(tǒng)S中，若?b∈C,xi,xj∈U1，F(xiàn)(xi,b)=F(xj,b)∧F(xi,D)=F(xj,D)成立，或?b∈C,xi,xj∈U2，F(xiàn)(xi,b)=F(xj,b)∧F(xi,D)≠F(xj,D)成立，則利用差別矩陣算法求得的屬性集相同，這不但占用大量存儲(chǔ)空間，而且也浪費(fèi)了大量計(jì)算時(shí)間.

定義3(決策表化簡) 在決策表信息系統(tǒng)S=(U,C,D,V,F)中，定義新決策表S′=(U′,C,D,V′,F′).信息函數(shù)F′滿足：F′(xi,C)=F(xi,C)，d∈D且

進(jìn)而，F(xiàn)′自然確定U′與V′.

根據(jù)定義2可知，當(dāng)?xi∈U1,xj∈U2時(shí)，mij≠?.當(dāng)?xk∈U2∧F(xk,C)=F(xj,C)∧F(xi,d)≠F(xj,d)成立，則mij=mik.又因xj,xk∈U2，根據(jù)定義2可知mjk=?.故在利用差別矩陣求解核屬性時(shí)，當(dāng)?xj,xk∈U2時(shí)，將U2中具有“相同條件屬性值但不同決策屬性值”的對(duì)象進(jìn)行合并不影響核屬性的求解結(jié)果.在決策表S′中，?xi,xj∈U′，b∈C，均有mij

定理2當(dāng)mik?mjk∧mjk-mik=1∧{(xi,xj)F(xi,b)≠F(xj,b)}=?,?b∈mik時(shí)，mij=mjk-mik∧mij=1.

根據(jù)定理2可知，當(dāng)mik∩mjk=?時(shí)，顯然mij={mik∪mjk}∧mij≥2.定理2揭示了核屬性集的關(guān)系，即在對(duì)象xi，xj比較之前，先判定屬性集mik與mjk是否滿足數(shù)量之差為1.若為1，則判定mik?mjk是否成立.因mik，mjk中的屬性集合是有序的，因此判斷mik?mjk時(shí)，其時(shí)間復(fù)雜度為max(O(mjk)).

其中:“—”表示無需考慮比較的對(duì)象.

2.3 屬性集求核算法描述

算法2基于差別矩陣的屬性集求核算法.

輸入：決策表信息系統(tǒng)S=(U,C,D,V,F)；輸出：決策表信息系統(tǒng)的核coreC(D).

步驟1 執(zhí)行算法1;

步驟2 根據(jù)定義3創(chuàng)建新的決策表S′;

步驟3 coreC(D)=?,core1C(D)=?,core2C(D)=?;

for (r=1;r≤C;r++)

if (F(xi,cr)≠F(xj,cr))

執(zhí)行定理2;

步驟7 coreC(D)=core1C(D)∪core2C(D);

步驟8 輸出coreC(D).

通過比較可知，本文算法的時(shí)間和空間復(fù)雜度均低于文獻(xiàn)[6]和文獻(xiàn)[7]所提算法的時(shí)間和空間復(fù)雜度.

3 實(shí)例分析

表1 決策表S

表2 化簡后的決策表S′Tab.2 Simplified decision table S′

在表2基礎(chǔ)上，根據(jù)定義4方法構(gòu)建差別矩陣SIDM,如表3所示.分析差別矩陣SIDM可知coreC(D)={c1,c2}.

如果采用文獻(xiàn)[6]方法創(chuàng)建差別矩陣IDM為5×8規(guī)模,如表4所示，共有40個(gè)元素；如果采用文獻(xiàn)[7]方法創(chuàng)建差別矩陣IDM′為4×5規(guī)模，如表5所示,共有20個(gè)元素.采用本文方法創(chuàng)建的差別矩陣SIDM為2×4規(guī)模，實(shí)際存儲(chǔ)的元素為7個(gè).可見采用本文方法既減少了樣本對(duì)象的個(gè)數(shù)，又降低了差別矩陣的空間占用，從而減少了數(shù)據(jù)的處理量，提高了求核效率.事實(shí)上，基于表1和表2，“表4→表5→表3”的改變過程清楚地體現(xiàn)了“文獻(xiàn)[6]→文獻(xiàn)[7]→本文”3種算法的差別矩陣改進(jìn)過程.

表3 差別矩陣SIDM

表4 差別矩陣IDM

表5 差別矩陣IDM′

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

采用文獻(xiàn)[7]中使用的UCI數(shù)據(jù)集(http://archive.ics.uci.edu/ml/datasets.html)，在Intel(R) Core(TM) i5-2400 CPU @ 3.10 GHz、RAM 2 GB環(huán)境下，對(duì)文獻(xiàn)[6]、文獻(xiàn)[7]與本文算法進(jìn)行了比較.UCI數(shù)據(jù)集及其特征如表6所示，其中U/C表示按照條件屬性集C劃分后等價(jià)類的數(shù)目；IDM、IDM′、SIDM分別表示文獻(xiàn)[6]、文獻(xiàn)[7]以及本文算法差別矩陣實(shí)際存儲(chǔ)元素的個(gè)數(shù).可以看出，本文算法創(chuàng)建的簡化差別矩陣中所存儲(chǔ)的元素?cái)?shù)目SIDM要少于文獻(xiàn)[6]和文獻(xiàn)[7]差別矩陣中存儲(chǔ)的元素個(gè)數(shù).

表6 UCI數(shù)據(jù)集及其特征

圖1與圖2分別給出3種算法在4種UCI數(shù)據(jù)集上執(zhí)行時(shí)間與執(zhí)行空間的比較.基于圖1，本文求核算法的執(zhí)行效率要優(yōu)于文獻(xiàn)[6]和文獻(xiàn)[7]的求核算法，并且隨著樣本對(duì)象的增加，該算法效率更加明顯.基于圖2，對(duì)于不相容決策表(如Patient與Car)和包含重復(fù)元素比較多的決策表(如Cancer)，本文求核算法在執(zhí)行過程中對(duì)存儲(chǔ)空間的需求小于文獻(xiàn)[6]和文獻(xiàn)[7].

圖1 3種算法執(zhí)行時(shí)間比較Fig.1 Comparison on execution time of 3 algorithms

圖2 3種算法執(zhí)行空間比較Fig.2 Comparison on execution space of 3 algorithms

5 結(jié)束語

文獻(xiàn)[4]的求核算法不能處理不相容決策表，存在一定的局限性.文獻(xiàn)[5]提出了改進(jìn)算法，并解決了文獻(xiàn)[4]算法不能處理不相容決策表的問題，但該算法的時(shí)空效率并不太理想.文獻(xiàn)[7]則在文獻(xiàn)[6]的基礎(chǔ)上，對(duì)決策表中相同對(duì)象合并來提高求核效率.研究發(fā)現(xiàn)，利用差別矩陣求解核屬性的算法效率還能得到進(jìn)一步的提高.因此，本文提出了一種基于差別矩陣的屬性集求核算法.該算法首先將決策表劃分成相容與不相容部分；其次運(yùn)用定理1找到可以忽略比較的對(duì)象，運(yùn)用定義3化簡決策表.算法2給出了基于差別矩陣的屬性集求核算法偽碼，由此設(shè)計(jì)的算法的時(shí)間與空間復(fù)雜度均低于文獻(xiàn)[6]和文獻(xiàn)[7]的時(shí)間與空間復(fù)雜度，實(shí)驗(yàn)結(jié)果表明該算法是有效的.

[1] ZHANG C S,RUAN J,TAN Y H. An improved incremental updating algorithm for core based on positive region[J]. Journal of computational information systems,2011,7(9):3127-3133.

[2] 錢文彬, 楊炳儒, 徐章艷,等. 基于信息熵的核屬性增量式高效更新算法[J]. 模式識(shí)別與人工智能, 2013, 26(1): 42-49.

[3] 李少年, 吳良剛. 基于鄰域信息熵度量數(shù)值屬性快速約簡算法[J]. 計(jì)算機(jī)工程與科學(xué), 2016, 38(2):350-355.

[4] HU X, CERCONE N. Learning in relational databases: a rough set approach[J]. Computational intelligence, 2010, 11(2): 323-338.

[5] 葉東毅, 陳昭炯. 一個(gè)新的差別矩陣及其求核方法[J]. 電子學(xué)報(bào), 2002, 30(7): 1086-1088.

[6] 楊明, 孫志揮. 改進(jìn)的差別矩陣及其求核方法[J]. 復(fù)旦學(xué)報(bào)(自然科學(xué)版), 2004, 43(5): 865-868.

[7] 楊傳健, 姚光順,馬麗生. 改進(jìn)的差別矩陣及其快速求核算法[J].計(jì)算機(jī)工程與科學(xué), 2010, 32(3): 78-81.