楊 濤， 張賢勇,2， 馮 山

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

0 引言

1 基本概念

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

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

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

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

2.1 差別矩陣的空值

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

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

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

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

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

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

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

步驟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，然后對U1中的對象按照決策屬性值的不同劃分成多個對象集，進而減少當決策屬性值相同時的不必要計算，同時也壓縮了差別矩陣中空值元素.一般情形下，算法1的時間復雜度為O(U12).在實際應用中，上述算法雖然有2個循環(huán)，但是內循環(huán)在循環(huán)過程中，當對象xi與xj可以忽略比較，對象xi與xk(k≠j)可以忽略比較時，由傳遞性可得對象xj與xk可以忽略比較.因此,算法在執(zhí)行過程中減少了內循環(huán)次數(shù)，即算法1的時間復雜度為O(U1).

2.2 差別矩陣的屬性集求核機理

在決策表信息系統(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)成立，則利用差別矩陣算法求得的屬性集相同，這不但占用大量存儲空間，而且也浪費了大量計算時間.

定義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且

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

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

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

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

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

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).

通過比較可知，本文算法的時間和空間復雜度均低于文獻[6]和文獻[7]所提算法的時間和空間復雜度.

3 實例分析

表1 決策表S

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

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

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

表3 差別矩陣SIDM

表4 差別矩陣IDM

表5 差別矩陣IDM′

4 實驗結果

采用文獻[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)境下，對文獻[6]、文獻[7]與本文算法進行了比較.UCI數(shù)據(jù)集及其特征如表6所示，其中U/C表示按照條件屬性集C劃分后等價類的數(shù)目；IDM、IDM′、SIDM分別表示文獻[6]、文獻[7]以及本文算法差別矩陣實際存儲元素的個數(shù).可以看出，本文算法創(chuàng)建的簡化差別矩陣中所存儲的元素數(shù)目SIDM要少于文獻[6]和文獻[7]差別矩陣中存儲的元素個數(shù).

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

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

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

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

5 結束語

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

[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]. 模式識別與人工智能, 2013, 26(1): 42-49.

[3] 李少年, 吳良剛. 基于鄰域信息熵度量數(shù)值屬性快速約簡算法[J]. 計算機工程與科學, 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] 葉東毅, 陳昭炯. 一個新的差別矩陣及其求核方法[J]. 電子學報, 2002, 30(7): 1086-1088.

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

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