閆俊輝

摘? 要： 隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和人們生活節(jié)奏的加快，生活中很多數(shù)據(jù)都在隨時(shí)發(fā)生著變化，那么快速及時(shí)的解決數(shù)據(jù)變化后的屬性約簡(jiǎn)問題，就成了信息技術(shù)領(lǐng)域里研究的一個(gè)重要課題。剖析了數(shù)據(jù)更新后相對(duì)知識(shí)粒度和等價(jià)關(guān)系矩陣的增量機(jī)制，提出了對(duì)象屬性值增加后的基于矩陣方法的增量屬性約簡(jiǎn)算法。下載了2組UCI數(shù)據(jù)對(duì)提出的增量屬性約簡(jiǎn)算法進(jìn)行了測(cè)試，結(jié)果證明了增量屬性約簡(jiǎn)算法能夠處理屬性值增加后的屬性約簡(jiǎn)問題。

關(guān)鍵詞： 屬性約簡(jiǎn); 知識(shí)粒度; 等價(jià)關(guān)系; 矩陣; 增量機(jī)制

中圖分類號(hào)：TP18? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：1006-8228（2022）04-47-04

Matrix incremental attribute reduction algorithm based on dimension change

Yan Junhui

（Yuncheng University， School of Mathematics and Information Technology， Yuncheng， Shanxi 044000， China）

Abstract： With the acceleration of computer network technology and people's pace of life， a lot of data in life are changing at any time. Quickly and timely solving the problem of attribute reduction after data changes has become an important topic in the field of information technology research. In this paper， the incremental mechanism of relative knowledge granularity and equivalence relation matrix after data update is analyzed. Then an incremental attribute reduction algorithm is proposed， which is after object attribute value increasing and based on matrix method. Finally， two groups of UCI data are downloaded to test the algorithm， and the results show that the incremental attribute reduction algorithm can deal with the attribute reduction problem with increased attribute values.

Key words： attribute reduction; knowledge granularity; equivalence relation; matrix; incremental mechanism

0 引言

近些年，計(jì)算機(jī)網(wǎng)絡(luò)、通信以及存儲(chǔ)技術(shù)的快速發(fā)展，使得各行各業(yè)信息系統(tǒng)都有大量的數(shù)據(jù)積累，其對(duì)象的屬性值會(huì)發(fā)生動(dòng)態(tài)變化。例如醫(yī)院里醫(yī)教科和人事科都有醫(yī)生的信息，在整合醫(yī)教科和人事科的醫(yī)生信息時(shí)，信息系統(tǒng)的屬性值會(huì)發(fā)生變化。此時(shí)，如何在原來的數(shù)據(jù)分析基礎(chǔ)上，快速更新對(duì)象的屬性值增加發(fā)生變化后決策信息系統(tǒng)的約簡(jiǎn)問題，成為信息科學(xué)研究領(lǐng)域普遍關(guān)注的熱點(diǎn)。假若使用非增量屬性約簡(jiǎn)算法[1-3]處理動(dòng)態(tài)的數(shù)據(jù)屬性約簡(jiǎn)，并不能充分利用先前計(jì)算的結(jié)果，導(dǎo)致運(yùn)行速度減慢。

為了克服非增量屬性約簡(jiǎn)算法在解決動(dòng)態(tài)變化數(shù)據(jù)時(shí)屬性約簡(jiǎn)的缺陷，很多學(xué)者提出了增量屬性約簡(jiǎn)算法。Wang等通過分析三種信息熵在屬性動(dòng)態(tài)增加情況下的增量變化機(jī)制，設(shè)計(jì)了基于信息熵的一種增量屬性約簡(jiǎn)算法[4];根據(jù)屬性在動(dòng)態(tài)增加和減少時(shí)決策信息系統(tǒng)中信息粒度的變化規(guī)律，Qian等提出了正向近似和逆向近似，并將其成功應(yīng)用在啟發(fā)式屬性約簡(jiǎn)算法的加速中，為粗糙集基礎(chǔ)上優(yōu)化知識(shí)發(fā)現(xiàn)性能提出了新思路[5];王磊等分析了矩陣方法計(jì)算相對(duì)知識(shí)粒度在對(duì)象屬性集動(dòng)態(tài)變化時(shí)的增量更新原理，探討了一種屬性動(dòng)態(tài)變化下增量屬性約簡(jiǎn)算法[6]; Jing討論了決策信息系統(tǒng)屬性值細(xì)化時(shí)實(shí)現(xiàn)快速計(jì)算約簡(jiǎn)問題的相對(duì)知識(shí)粒度和計(jì)算等價(jià)關(guān)系矩陣的增量機(jī)制，設(shè)計(jì)了基于對(duì)象屬性集增加時(shí)的動(dòng)態(tài)屬性約簡(jiǎn)算法[7];Shu等在不完備的系統(tǒng)中，討論了對(duì)象屬性集在動(dòng)態(tài)增加或刪除時(shí)基于正區(qū)域的決策信息系統(tǒng)動(dòng)態(tài)屬性約簡(jiǎn)算法[8]; Zeng等提出了新的混合距離的概念，并結(jié)合高斯核和混合距離，探討了決策信息系統(tǒng)在屬性值細(xì)化下的屬性約簡(jiǎn)增量更新機(jī)制，提出了基于模糊粗糙集的混合決策信息系統(tǒng)動(dòng)態(tài)屬性的約簡(jiǎn)算法，并對(duì)該算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證[9]。通過以上分析，對(duì)信息熵和正區(qū)域的更新是大多數(shù)增量算法實(shí)現(xiàn)快速獲取屬性增加后決策信息系統(tǒng)約簡(jiǎn)的主要途徑，而利用更新知識(shí)粒度的方法實(shí)現(xiàn)快速獲取屬性值細(xì)化后決策信息系統(tǒng)的約簡(jiǎn)算法研究很少。

利用矩陣計(jì)算處理數(shù)值是一種非常有效的方法，已被廣泛應(yīng)用到數(shù)值分析、知識(shí)發(fā)現(xiàn)和系統(tǒng)工程等諸多學(xué)科領(lǐng)域。針對(duì)決策信息系統(tǒng)如何快速地更新變化后的決策信息系統(tǒng)約簡(jiǎn)問題，首先探究了矩陣計(jì)算變化后的決策信息系統(tǒng)等價(jià)關(guān)系矩陣和相對(duì)知識(shí)粒度的增量機(jī)制，然后設(shè)計(jì)了增加對(duì)象及其方法，最后通過UCI數(shù)據(jù)仿真實(shí)驗(yàn)的結(jié)果，驗(yàn)證了所提出的增量屬性約簡(jiǎn)算法可以有效處理對(duì)象的屬性值增量后的屬性約簡(jiǎn)問題。

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

依據(jù)以上七個(gè)定義，很多研究該課題的學(xué)者就得到了基于矩陣的非增量屬性約簡(jiǎn)算法[6]。

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

當(dāng)決策信息系統(tǒng)屬性發(fā)生細(xì)微變化，并且對(duì)象值增加時(shí)。仍然用上面的算法來計(jì)算數(shù)據(jù)變化后的決策信息系統(tǒng)，由于不能用到之前的運(yùn)算結(jié)果，要重復(fù)計(jì)算等價(jià)關(guān)系矩陣（定義2）、相對(duì)知識(shí)粒度（定義4）和約簡(jiǎn)（定義7），這樣就浪費(fèi)了更多的時(shí)間和存儲(chǔ)空間，使得運(yùn)算速度變慢。為了解決對(duì)象值變化后決策信息系統(tǒng)約簡(jiǎn)速度變慢的問題，本文提出了決策信息系統(tǒng)屬性值增加后的增量屬性約簡(jiǎn)算法。

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

2.2 屬性增加時(shí)的增量屬性約簡(jiǎn)算法

當(dāng)決策信息系統(tǒng)屬性發(fā)生細(xì)微變化，并且對(duì)象值增加時(shí)，參照上面運(yùn)算得到的等價(jià)關(guān)系矩陣和知識(shí)粒度增量機(jī)制的定義和定理，在原有決策信息系統(tǒng)的知識(shí)粒度和約簡(jiǎn)基礎(chǔ)上，提出了對(duì)象屬性值增加后的增量屬性約簡(jiǎn)算法，算法的具體步驟如下：

3 實(shí)驗(yàn)仿真測(cè)試

為了測(cè)試本文中提出的增量屬性約簡(jiǎn)算法的可行性，我們下載了梁組UCI數(shù)據(jù)集作為仿真實(shí)驗(yàn)的數(shù)據(jù)集，數(shù)據(jù)集描述如（表1）所示，分別對(duì)這些數(shù)據(jù)集用非增量和增量屬性約簡(jiǎn)算法進(jìn)行計(jì)算，并對(duì)非增量屬性約簡(jiǎn)算法和增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間進(jìn)行對(duì)比分析。仿真實(shí)驗(yàn)的硬件環(huán)境要求，中央處理器： 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即可。

3.1 非增量屬性約簡(jiǎn)算法與增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間比較

在仿真實(shí)驗(yàn)中，把表1中的數(shù)據(jù)集，按照屬性分成兩部分，其中50%的條件屬性和決策屬性為基本數(shù)據(jù)集，其余的50%數(shù)據(jù)，按照數(shù)學(xué)的20%、40%、60%、80%、100%作為增量屬性集，非增量和增量約簡(jiǎn)算法分別運(yùn)行這些數(shù)據(jù)集，仿真實(shí)驗(yàn)的結(jié)果（如圖1）中的（a）、（b）所示，其中縱軸是約簡(jiǎn)算法的運(yùn)行時(shí)間，橫軸是數(shù)據(jù)集中增加屬性的百分?jǐn)?shù)。圓形線表示非增量約簡(jiǎn)算法的運(yùn)行時(shí)間，方形線表示增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間。

從圖1可以看出，當(dāng)決策信息系統(tǒng)屬性對(duì)象值增加時(shí)，增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)小于非增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間，結(jié)果證明了增量屬性約簡(jiǎn)算法能夠處理屬性值增加后的屬性約簡(jiǎn)問題，并大大提高了效率。

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

在運(yùn)行分類精度實(shí)驗(yàn)中，把表1中的數(shù)據(jù)按照屬性分成基本數(shù)據(jù)集和增量數(shù)據(jù)集，其中條件屬性和決策屬性由基本數(shù)據(jù)集的50%組成，增量數(shù)據(jù)集由剩余的50%組成，當(dāng)增量數(shù)據(jù)集被增加到基本數(shù)據(jù)集時(shí)，用非增量和增量屬性約簡(jiǎn)算法分別計(jì)算數(shù)據(jù)集的約簡(jiǎn)。然后，運(yùn)用貝葉斯分類方法和十字交叉方法計(jì)算非增量與增量約簡(jiǎn)算法可以得到約簡(jiǎn)的分類精確度，再對(duì)分類精確度進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如表2。

從表2可以看出非，增量約簡(jiǎn)算法和增量約簡(jiǎn)算法獲得約簡(jiǎn)的分類精確度的值是相近的。實(shí)驗(yàn)結(jié)果證明，當(dāng)決策信息系統(tǒng)條件屬性對(duì)象值增加時(shí)，增量屬性約簡(jiǎn)算法所得到的約簡(jiǎn)是有效地。

4 結(jié)束語

本文闡述了決策信息系統(tǒng)對(duì)象的屬性值增加后快速解決約簡(jiǎn)更新的問題，首先分析了對(duì)象的屬性值增加后基于矩陣的等價(jià)關(guān)系的增量機(jī)制，然后提出了對(duì)象屬性值增加后的基于矩陣的增量屬性約簡(jiǎn)算法。最后下載了UCI數(shù)據(jù)集并對(duì)提出的增量屬性約簡(jiǎn)算法進(jìn)行了仿真測(cè)試，結(jié)果證明了增量屬性約簡(jiǎn)算法能夠處理屬性值增加后的屬性約簡(jiǎn)問題。下一步將考慮屬性值和屬性同時(shí)變化時(shí)的增量屬性約簡(jiǎn)算法，并把所提出的增量屬性約簡(jiǎn)算法推廣到多粒度粗糙集模型中。

參考文獻(xiàn)（References）：

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

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

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

[4] Feng Wang， Jiye Liang， Chuangyin Deng. Attributereduction：A dimension incremental strategy.Knowledge-Based Systems，2013，39：95-108

[5] Yuhua Qian， Jiye Liang， Witold Pedrycz， Chuangyin Deng.?Positive approximation： An accelerator for attribute reduction in rough set theory. Artificial Intelligence，2010，174（9-10）：597-618

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

[7] Yunge Jing， Tianrui Li， Chuan Luo， Shi-Jinn Horng，Guoyin Wang， Zeng Yu. An incremental approach for attribute reduction based on knowledge granularity[J]. Knowledge-Based Systems，2016，104（C）：24-38

[8] Wenhao Shu， Hong Shen. Updating attribute reduct inincomplete decision systems with the variation of attribute set. International Journal of Approximate Reasoning，2014，55：867-884

[9] Anping Zeng， Tianrui Li， Dun Liu，? Junbo Zhang， HongmeiChen. A fuzzy rough set approach for incremental feature selection on hybrid information systems. Fuzzy Sets and Systems，2015， 258：39-60

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