矩陣增量屬性約簡算法

閆 鑫，景運革

1(山西財經(jīng)大學(xué) 信息管理學(xué)院，太原 030006)

2(運城學(xué)院 公共計算機教學(xué)部，山西 運城 044000)

3(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756)

1 引 言

在現(xiàn)實生活中，隨著計算機網(wǎng)絡(luò)、存儲和通信技術(shù)迅猛的發(fā)展，許多決策信息系統(tǒng)的對象和屬性值都會同時發(fā)生變化.例如學(xué)校里每年都會有新教師增加，同時教師的職稱每年也會發(fā)生更新，如原來部分教師的職稱是講師可能會變成副教授等.針對決策信息系統(tǒng)對象增加且屬性值發(fā)生細化問題，如何在原有數(shù)據(jù)分析的基礎(chǔ)上快速更新變化后決策信息系統(tǒng)約簡問題，是信息科學(xué)領(lǐng)域研究的一個普遍關(guān)注熱點.如果使用非增量屬性約簡方法[1-3]來處理動態(tài)數(shù)據(jù)屬性約簡問題時，需要重新計算變化后決策信息系統(tǒng)的屬性約簡，不能充分利用先前知識粒度和約簡，導(dǎo)致運行速度較慢.

為了有效解決非增量約簡算法在處理動態(tài)數(shù)據(jù)時存在的缺陷，許多研究者提出了增量屬性約簡方法.針對決策信息系統(tǒng)對象變化增量屬性約簡問題，楊明針對決策信息系統(tǒng)對象集動態(tài)更新問題，對差別矩陣進行改進，分析了改進差別矩陣的增量更新機制，設(shè)計了增量屬性約簡算法[4]；Jiang等根據(jù)決策樹自適應(yīng)算法，提出了增量屬性約簡算法，并把所提出的增量屬性約簡算法應(yīng)用到網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)檢測中[5]；Jing針對決策信息系統(tǒng)對象屬性集動態(tài)變化時如何快速計算約簡問題，討論了計算等價關(guān)系矩陣和相對知識粒度的增量更新原理，提出了基于對象增加時動態(tài)屬性約簡算法[6]； Xu等分析了一些對象增加到?jīng)Q策信息系統(tǒng)情況下屬性約簡的更新機理，在0-1運算的基礎(chǔ)上，提出了一種對象集動態(tài)增加時的增量屬性約簡算法[8]；針對動態(tài)大數(shù)據(jù)屬性約簡問題，Jing等利用多粒度理論和“分而治之”方法，設(shè)計了對象變化時基于多粒度粗糙集增量屬性約簡算法[11]；羅來鵬根據(jù)決策信息系統(tǒng)對象動態(tài)增加情況，分析了二叉樹增量更新機制，提出了基于對象動態(tài)增加時的增量屬性約簡算法[15].針對決策信息系統(tǒng)屬性值變化增量屬性約簡問題，Chen等討論了屬性值變化下優(yōu)勢特性關(guān)系粗糙集模型中近似集更新的原理，設(shè)計了向上向下近似集及屬性值約簡增量更新算法[9]；Jing探討了對象屬性值變化時等價關(guān)系矩陣和相對知識粒度的增量更新機制，設(shè)計了基于屬性值動態(tài)變化的增量屬性約簡算法[7]；針對決策表屬性值發(fā)生細化問題時，唐定勇等分析了基于矩陣方法計算正域的增量更新原理，設(shè)計了屬性值細化時的增量屬性約簡算法[10]；針對集值決策信息系統(tǒng)中屬性值動態(tài)更新變化問題，Lang等提出了基于不可分辨矩陣的動態(tài)屬性約簡算法[14].根據(jù)上面分析，決策信息系統(tǒng)對象的屬性值被細化且增加對象時增量屬性約簡算法研究較少.

代數(shù)中矩陣計算是一種非常有效的計算工具，已經(jīng)被廣泛應(yīng)用到系統(tǒng)工程和數(shù)值分析等諸多學(xué)科領(lǐng)域中.針對決策信息系統(tǒng)對象集屬性值發(fā)生細化且增加對象后如何快速更新約簡的問題，首先討論了基于矩陣方法計算決策信息系統(tǒng)等價關(guān)系矩陣和相對知識粒度的增量機制，然后提出了屬性值細化且對象增加時增量屬性約簡算法，最后通過仿真實驗結(jié)果表明了所提出的增量屬性約簡算法是有效的.

2 基于矩陣方法的非增量屬性約簡算法

定義7[1]. 如果S=(U，A=C∪D，V，f)是決策信息系統(tǒng)，B?C，B為決策信息系統(tǒng)的約簡當(dāng)且僅當(dāng)：

1)GD(D|B)=GD(D|C)；

2)對于?a∈B，使得

GD(D|B-{a})≠GD(D|C).

根據(jù)上面的相關(guān)定義，研究者提出了一種基于矩陣方法的屬性約簡算法(非增量屬性約簡算法)[6，7，10].

3 基于矩陣方法的增量屬性約簡算法

當(dāng)決策信息系統(tǒng)對象的屬性值被細化且增加對象時，非增量屬性約簡算法計算變化后決策信息系統(tǒng)約簡時，需要重復(fù)計算決策信息系統(tǒng)等價關(guān)系矩陣、相對知識粒度及約簡，導(dǎo)致運行時間和儲存空間耗費較多.為了能夠快速獲得變化后決策信息系統(tǒng)的約簡，提出了屬性值細化且增加對象時增量屬性約簡算法.

3.1 知識粒度的增量機制

定義8[10]. 如果S=(U，A=C∪D，V，f)是決策信息系統(tǒng)，B?A，B≠?,al∈B且Vl是條件屬性al的值域，[xi]al={xi，xj∈U,|f(xi,al)=f(xj,al)}.?xk∈[xi]al，若有f(xk，al)=v，且v?Vl，則屬性值f(xk，al)被細化為v.

假設(shè)X=[xi]al，Y={xm∈U|f(xm,al)=v}，則X-Y={xn∈U|f(xn,al)≠f(xm,al)}為條件屬性al數(shù)值細化后，集合X中對象屬性值沒有發(fā)生變化的集合.

假設(shè)IX-Y={i|ui∈X-Y}，IY={i|ui∈Y}，則IX-Y為集合X-Y中所有元素下標(biāo)的集合，IY為集合Y中所有元素下標(biāo)的集合.

其中，Sum(…)代表矩陣所有元素的和.

3.2 屬性值細化且對象增加時基于矩陣方法的增量屬性約簡算法

當(dāng)決策信息系統(tǒng)條件屬性ai的數(shù)值被細化且增加了對象集UX時，根據(jù)上述的增量機制的定義和定理，在決策信息系統(tǒng)原來等價關(guān)系矩陣和約簡的基礎(chǔ)上，設(shè)計了屬性值細化且對象增加時基于矩陣方法的增量屬性約簡算法，該算法的具體過程描述如下：

算法.屬性值細化且對象增加時基于矩陣方法的增量屬性約簡算法

輸入：決策信息系統(tǒng)S=(U，A=C∪D，V，f)，決策信息系統(tǒng)的約簡REDU，增量對象集UX及屬性ai的數(shù)值被細化；

輸出：決策信息系統(tǒng)增加了對象集UX且屬性ai的數(shù)值被細化后的約簡REDU′∪UX.

步驟2. 計算決策信息系統(tǒng)增加了對象集UX且屬性ai的數(shù)值被細化后的相對知識粒度GDU′∪UX(D|B) ，GDU′∪UX(D|C)；

步驟3. 如果GDU′∪UX(D|B)=GDU′∪UX(D|C)，則執(zhí)行步驟6，否則執(zhí)行步驟4；

步驟5. 對于?a∈B，計算D相對于(B-{a})的相對知識粒度GDU′∪UX(D|B-{a})，如果GDU′∪UX(D|B-{a})=GDU′∪UX(D|C)，則B←B-{a}；

步驟6.REDU′∪UX←B，輸出增加對象性集UX且屬性ai的數(shù)值被細化后的決策信息系統(tǒng)約簡REDU′∪UX，算法結(jié)束.

3.3 算法復(fù)雜度分析

從上面分析可得增量屬性約簡算法的時間復(fù)雜度小于非增量屬性約簡算法的時間復(fù)雜度，驗證了所提出的增量屬性約簡算法是有效的.

4 實驗仿真分析

為了驗證本文提出的屬性值細化且增加對象時基于矩陣方法的增量屬性約簡算法的有效性，我們把基于矩陣方法的增量屬性約簡算法的運行時間和非增量屬性約簡算法的運行時間作比較，并下載了4組UCI數(shù)據(jù)集作為仿真實驗數(shù)據(jù)集，數(shù)據(jù)集的具體描述如表1所示，實驗仿真的硬件環(huán)境：CPU Pentium(R) Dual-Core E5800 3.20GHz，內(nèi)存：Samsung DDR3 SDRAM，4.0GB實驗仿真的軟件環(huán)境：64-bit Windows 10操作系統(tǒng)，64-bits (JDK 1.6.0_20)和Eclipse 3.7.

表1 數(shù)據(jù)集描述Table 1 Description of date sets

4.1 增量屬性約簡算法與非增量屬性約簡算法運行時間比較

在實驗仿真過程中，我們把表1的數(shù)據(jù)按照對象均勻分成2部分，其中50%的數(shù)據(jù)集作為基本數(shù)據(jù)集，基本數(shù)據(jù)集中一半數(shù)據(jù)集20%、40%、60%、80%、100%的屬性值進行細化，另一半數(shù)據(jù)集的屬性值沒有發(fā)生變化，剩余50%的數(shù)據(jù)按照對象的20%、40%、60%、80%、100%依次作為增量對象集，并用增量屬性約簡算法和非增量屬性約簡算法運行這些數(shù)據(jù)集，實驗的仿真結(jié)果如圖1中各個子圖所示，縱軸表示算法的計算時間，橫軸表示數(shù)據(jù)集中對象屬性值發(fā)生細化且增加對象的百分?jǐn)?shù).圓形代表非增量屬性約簡算法的運行時間，方形代表增量屬性約簡算法的運行時間.

從仿真實驗結(jié)果可以得出，當(dāng)決策信息系統(tǒng)對象的屬性值被細化且增加對象時，所提出的增量約簡算法的計算時間遠遠小于非增量屬性約簡算法的計算時間，從而說明本文所提的屬性值細化且對象增加時的增量屬性約簡算法是有效的.

圖1 增量屬性約簡算法和非增量屬性約簡算法運行時間的比較Fig. 1 Comparison between incremental reduction method and non-incremental reduction method on computation time

4.2 增量屬性約簡算法與非增量屬性約簡算法所得約簡分類精確度比較

在分類精度仿真實驗中把表1的數(shù)據(jù)按照對象均勻分成兩部分，其中一部分的數(shù)據(jù)作為基本數(shù)據(jù)集，另一部分作為增量數(shù)據(jù)集，當(dāng)基本數(shù)據(jù)集中的一半數(shù)據(jù)集的屬性值發(fā)生了細化，另一半數(shù)據(jù)集的屬性值未發(fā)生變化，并把增量數(shù)據(jù)集添加到基本數(shù)據(jù)集中，分別用增量屬性約簡算法和非增量屬性約簡算法運行這些數(shù)據(jù)集.最后，運用十字交叉法和貝葉斯分類算法計算不同屬性約簡算法所得約簡的分類精確度并對其進行分析比較，所獲結(jié)果描述如表2.

表2 比較增量屬性約簡算法和非增量屬性約簡算法獲得約簡的分類精確度Table 2 Comparison of incremental reduction method and non-incremental reduction method on classification accuracy

從表2可以得到增量屬性約簡算法和非增量屬性約簡算法所得到約簡的分類精確度的值是相近的.結(jié)果說明了，當(dāng)決策信息系統(tǒng)對象的屬性值被細化且增加對象時，本文所提出的屬性值細化且對象增加時的增量屬性約簡算法所得到的約簡是有效的.

4.3 增量屬性約簡算法與其他增量屬性約簡算法比較

在實驗仿真過程中，我們把表1的數(shù)據(jù)按照對象均勻分成2部分，其中50%的數(shù)據(jù)集作為基本數(shù)據(jù)集，基本數(shù)據(jù)集中一半數(shù)據(jù)集的屬性值進行細化，剩余50%的數(shù)據(jù)作為增量對象集，并用增量屬性約簡算法和文獻[6]及文獻[10]提出的增量屬性約簡算法運行這些數(shù)據(jù)集，實驗的仿真結(jié)果如表3所示.結(jié)果表示增量屬性約簡算法的計算時間小于文獻[6]及文獻[10]提出的增量屬性約簡算法的計算時間.驗證了所提出的增量屬性約簡算法在處理動態(tài)變化數(shù)據(jù)屬性約簡是非常有效的.

表3 增量屬性約簡算法和其他增量屬性約簡算法運行時間的比較Table 3 Comparison between incremental reduction method and other incremental reduction method on computation time

5 結(jié)束語

如何能夠快速更新動態(tài)數(shù)據(jù)屬性約簡是信息科學(xué)領(lǐng)域中的研究的一個熱點課題.當(dāng)決策信息系統(tǒng)對象的屬性值被細化且增加對象時，本文首先討論了基于矩陣方法計算決策信息系統(tǒng)等價關(guān)系矩陣和相對知識粒度的增量機制，然后提出了屬性值細化且增加對象時基于矩陣方法的增量屬性約簡算法，最后利用UCI數(shù)據(jù)集對所提出的增量屬性約簡算法進行仿真驗證，仿真實驗結(jié)果表明了屬性值細化且增加對象時的增量屬性約簡算法是有效的.下一步研究將考慮在多粒度粗糙集模型下實現(xiàn)屬性值、對象集和屬性集同時變化下的增量屬性約簡算法來解決大數(shù)據(jù)動態(tài)環(huán)境下快速更新屬性約簡的問題.

：

[1] Miao Duo-qian，F(xiàn)an Shi-dong.The calculation of knowledge granulation and its application[J].Systems Engineer-Theory & Practice，2002，22(1)：48-56.

[2] Wang Guo-yin，Yu Hong，Yang Da-chun.Decision table reduction based on conditional information entropy[J].Chinese Journal of Computer，2002，25(7)：760-765.

[3] Liang Ji-ye，Qu Kai-she，Xu Zong-ben.Reduction of attribute in information systems[J].Systems Engineer-Theory & Practice，2001，12(12)：76-80.

[4] Yang Ming.An incremental updating algorithm for attribute reduction based on improved discernibility matrix[J].Chinese Journal of Computer，2007，30(5)：815-822.

[5] Jiang Feng，Sui Yue-fei，Cao Cun-gen.An incremental decision tree algorithm based on rough sets and its application in intrusion detection[J].Artificial Intelligence Review，2013，40(4)：517-530.

[6] Jing Yun-ge，Li Tian-rui，Luo Chuan，et al.An incremental approach for attribute reduction based on knowledge granularity[J].Knowledge-Based Systems，2016，104(C)：24-38.

[7] Jing Yun-ge，Li Tian-rui，Huang Jun-fu，et al.A group incremental reduction approach with varying data values[J].International Journal of Intelligent Systems，2016，32(9)：1-26.

[8] Xu Yi-tian，Wang Lai-sheng，Zhang Rui-yan，et al.A dynamic attribute reduction algorithm based on 0-1 integer programming[J].Knowledge-Based Systems，2011，24(8)：1341-1347.

[9] Chen Hong-mei，Li Tian-rui，Ruan Da.Maintenance of approximations in incomplete ordered decision systems while attribute values coarsening or refining[J].Knowledge-Based Systems，2012，31(7)：140-161.

[10] Tang Ding-yong，Jing Yun-ge.A reduction algorithm of positive domain for decision table based on values refining[J].Microelectronics & Computer，2015，32(3)：23-27.

[11] Jiang Yun-ge，Li Tian-rui，Hamido Fujita，et al.An incremental attribute reduction approach based on knowledge granularity with a multi-granulation[J].Information Sciences，2017，411：23-38.

[12] Liu Qing.Rough set and rough theory[M].Beijing：Science Press，2001：7-16.

[13] Wang Lei，Ye Jun.Matrix-based approach for calculating knowledge granulation and its application in attribute reduction[J].Computer Engineering & Science，2013，35(3)：98-102.

[14] Lang Guang-ming，Li Qing-guo，Yang Tian Y.An incremental approach to attribute reduction of dynamic set-valued information systems[J].International Journal of Machine Learning and Cybernetics，2014，5(5)：775-788.

[15] Luo Lai-peng.An incremental updating algorithm for attribute reduction[J].Journal of Shenyang University (Natural Science)，2013，25(3)：246-249.

附中文參考文獻：

[1] 苖奪謙，范世棟.知識粒度的計算及其應(yīng)用[J].系統(tǒng)工程理論與實踐，2002，22(1)：48-56.

[2] 王國胤，于 洪，楊大春.基于條件信息熵的決策表約簡[J].計算機學(xué)報，2002，25(7)：760-765.

[3] 梁吉業(yè)，曲開社，徐宗本.信息系統(tǒng)的屬性約簡[J].系統(tǒng)工程理論與實踐，2001，12(12)：76-80.

[4] 楊 明.一種基于改進差別矩陣的屬性約簡增量式更新算法[J].計算機學(xué)報，2007，30(5)：815-822.

[10] 唐定勇，景運革.一種決策表屬性值細化的正域約簡算法[J].微電子學(xué)與計算機，2015，32(3)：23-27.

[12] 劉 清.Rough set 及Rough推理[M].北京：科學(xué)出版社，2001：7-16.

[13] 王 磊，葉 軍.知識粒度計算的矩陣方法及其在屬性約簡中的應(yīng)用[J].計算機工程與科學(xué)，2013，35(3)：98-102.

[15] 羅來鵬.一種增量式屬性約簡更新算法[J].沈陽大學(xué)學(xué)報(自然科學(xué)版)，2013，25(3)：246-249.