矩陣增量屬性約簡(jiǎn)算法

閆 鑫，景運(yùn)革

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

2(運(yùn)城學(xué)院 公共計(jì)算機(jī)教學(xué)部，山西 運(yùn)城 044000)

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

1 引 言

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

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

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

2 基于矩陣方法的非增量屬性約簡(jiǎn)算法

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

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

2)對(duì)于?a∈B，使得

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

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

3 基于矩陣方法的增量屬性約簡(jiǎn)算法

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

3.1 知識(shí)粒度的增量機(jī)制

定義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)被細(xì)化為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ì)化后，集合X中對(duì)象屬性值沒(méi)有發(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 屬性值細(xì)化且對(duì)象增加時(shí)基于矩陣方法的增量屬性約簡(jiǎn)算法

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

算法.屬性值細(xì)化且對(duì)象增加時(shí)基于矩陣方法的增量屬性約簡(jiǎn)算法

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)仿真分析

為了驗(yàn)證本文提出的屬性值細(xì)化且增加對(duì)象時(shí)基于矩陣方法的增量屬性約簡(jiǎn)算法的有效性，我們把基于矩陣方法的增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間和非增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間作比較，并下載了4組UCI數(shù)據(jù)集作為仿真實(shí)驗(yàn)數(shù)據(jù)集，數(shù)據(jù)集的具體描述如表1所示，實(shí)驗(yàn)仿真的硬件環(huán)境：CPU Pentium(R) Dual-Core E5800 3.20GHz，內(nèi)存：Samsung DDR3 SDRAM，4.0GB實(shí)驗(yàn)仿真的軟件環(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 增量屬性約簡(jiǎn)算法與非增量屬性約簡(jiǎn)算法運(yùn)行時(shí)間比較

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

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

圖1 增量屬性約簡(jiǎn)算法和非增量屬性約簡(jiǎn)算法運(yùn)行時(shí)間的比較Fig. 1 Comparison between incremental reduction method and non-incremental reduction method on computation time

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

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

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

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

4.3 增量屬性約簡(jiǎn)算法與其他增量屬性約簡(jiǎn)算法比較

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

表3 增量屬性約簡(jiǎn)算法和其他增量屬性約簡(jiǎn)算法運(yùn)行時(shí)間的比較Table 3 Comparison between incremental reduction method and other incremental reduction method on computation time

5 結(jié)束語(yǔ)

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

附中文參考文獻(xiàn)：

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

[2] 王國(guó)胤，于 洪，楊大春.基于條件信息熵的決策表約簡(jiǎn)[J].計(jì)算機(jī)學(xué)報(bào)，2002，25(7)：760-765.

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

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

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

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

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

[15] 羅來(lái)鵬.一種增量式屬性約簡(jiǎn)更新算法[J].沈陽(yáng)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013，25(3)：246-249.