閆鑫 閆俊輝

摘 要： 隨著通信和計(jì)算機(jī)技術(shù)的迅速發(fā)展，各行各業(yè)都積累了大量數(shù)據(jù)且這些數(shù)據(jù)集每時(shí)每刻都在動(dòng)態(tài)變化，如何快速計(jì)算動(dòng)態(tài)數(shù)據(jù)屬性約簡(jiǎn)的問(wèn)題是人工智能領(lǐng)域中的一個(gè)重要研究課題。針對(duì)決策信息系統(tǒng)屬性增加時(shí)，如何快速計(jì)算變化后決策信息系統(tǒng)約簡(jiǎn)更新的問(wèn)題，首先分析了計(jì)算變化后決策信息系統(tǒng)相對(duì)知識(shí)粒度和等價(jià)關(guān)系矩陣的增量更新機(jī)制，然后提出了決策信息系統(tǒng)屬性增加后的增量屬性約簡(jiǎn)方法，最后從公共數(shù)據(jù)網(wǎng)站下載了4組UCI數(shù)據(jù)集并對(duì)所提出的增量屬性約簡(jiǎn)算法進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明了所提出的增量屬性約簡(jiǎn)算法是有效的。

關(guān)鍵詞： 粗糙集； 增量機(jī)制； 屬性約簡(jiǎn)； 知識(shí)粒度

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2018）03-53-05

Matrix-based incremental attribute reduction method

Yan Xin1， Yan Junhui2

（1. ShanXi University of Finance Economics， Faculty of Information Management， Taiyuan， Shanxi 030006， China；

2. Yuncheng University， Department of Public Computer Teaching）

Abstract： With the fast development of computer network technology and communication technology， many real data in databases may vary dynamically. How to acquiring knowledge effectively and timely from the dynamic data has become an important problem. In this paper， the incremental mechanisms to calculate equivalent relation matrix and relative knowledge granularity based on matrices are introduced when multiple attributes are added into the decision system； The corresponding matrix-based incremental attribute reduction method is developed. Experiments on four data sets downloaded from UCI show that the proposed matrix-based incremental attribute reduction method is effective and efficient.

Key words： rough set； incremental mechanism； attribute reduction； knowledge granularity

0 引言

隨著通信和計(jì)算機(jī)技術(shù)的迅速發(fā)展，各行各業(yè)都積累了大量數(shù)據(jù)，數(shù)據(jù)每時(shí)每刻都在動(dòng)態(tài)變化。例如學(xué)校教務(wù)部門和人事部門都有教師的信息，如果把教務(wù)部門和人事部門的教師信息整合起來(lái)，就會(huì)造成信息系統(tǒng)屬性增加等。針對(duì)決策信息系統(tǒng)屬性增加時(shí)如何快速更新約簡(jiǎn)問(wèn)題，如果使用非增量屬性約簡(jiǎn)算法[1-3]來(lái)處理動(dòng)態(tài)數(shù)據(jù)屬性約簡(jiǎn)時(shí)，不能有效利用先前的計(jì)算結(jié)果，導(dǎo)致運(yùn)行速度較慢。

由于非增量屬性約簡(jiǎn)算法不能有效處理動(dòng)態(tài)變化數(shù)據(jù)屬性約簡(jiǎn)的問(wèn)題，因此很多學(xué)者設(shè)計(jì)了增量屬性約簡(jiǎn)算法去解決動(dòng)態(tài)變化數(shù)據(jù)屬性約簡(jiǎn)的問(wèn)題。Qian等根據(jù)決策信息系統(tǒng)中屬性動(dòng)態(tài)增加和減少情況下的信息粒度變化規(guī)律，提出正向近似和逆向近似，并成功應(yīng)用于啟發(fā)式屬性約簡(jiǎn)算法的加速，為基于粗糙集的知識(shí)發(fā)現(xiàn)性能優(yōu)化提供了新思路[4]；Wang等分析了一些屬性動(dòng)態(tài)增加情況下三種信息熵的增量變化機(jī)制，提出了一種基于信息熵的增量屬性約簡(jiǎn)算法[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]； 王磊等分析了屬性動(dòng)態(tài)變化下用矩陣方法計(jì)算知識(shí)粒度的增量更新原理，提出了一種屬性集動(dòng)態(tài)變化增量屬性約簡(jiǎn)算法[7]；Zeng等給出了一種新的混合距離概念，結(jié)合混合距離和高斯核，分析了當(dāng)決策信息系統(tǒng)在屬性變化下屬性約簡(jiǎn)的增量更新機(jī)制，提出了混合決策信息系統(tǒng)中基于模糊粗糙集動(dòng)態(tài)屬性約簡(jiǎn)算法，并對(duì)該算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證[8]。Shu等在不完備系統(tǒng)中，分析了屬性集動(dòng)態(tài)增加或刪除情況下決策信息系統(tǒng)正區(qū)域的動(dòng)態(tài)更新機(jī)制，提出了基于正區(qū)域的動(dòng)態(tài)屬性約簡(jiǎn)算法[9]。根據(jù)上面分析，當(dāng)決策信息系統(tǒng)屬性增加時(shí)，大多數(shù)增量算法主要通過(guò)更新信息熵和正區(qū)域?qū)崿F(xiàn)快速獲取變化后決策信息系統(tǒng)的約簡(jiǎn)，而通過(guò)更新知識(shí)粒度實(shí)現(xiàn)快速獲取變化后決策信息系統(tǒng)約簡(jiǎn)的算法研究較少。

矩陣在處理數(shù)值計(jì)算方面具有很大的優(yōu)勢(shì)，已被廣泛應(yīng)用到數(shù)據(jù)挖掘、數(shù)值分析和知識(shí)發(fā)現(xiàn)等學(xué)科領(lǐng)域中。針對(duì)決策信息系統(tǒng)屬性增加后如何快速計(jì)算變化后決策信息系統(tǒng)約簡(jiǎn)的問(wèn)題，首先探討了計(jì)算變化后決策信息系統(tǒng)相對(duì)知識(shí)粒度和等價(jià)關(guān)系矩陣的增量更新機(jī)制，然后設(shè)計(jì)了決策信息系統(tǒng)屬性增加后的增量屬性約簡(jiǎn)方法，最后通過(guò)UCI數(shù)據(jù)對(duì)所提出的增量屬性約簡(jiǎn)算法的性能進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出的增量屬性約簡(jiǎn)算法能有效處理動(dòng)態(tài)屬性約簡(jiǎn)的問(wèn)題。

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

定義1[10] 信息系統(tǒng)是一個(gè)四元組，其中U是信息系統(tǒng)論域，C是信息系統(tǒng)的條件屬性集，D是信息系統(tǒng)的決策屬性集，，Va為信息系統(tǒng)條件屬性a的數(shù)值，是信息函數(shù)，且，有。

定義2[6] 假設(shè)決策信息系統(tǒng)為， U/C={X1，X2，…，Xm}是決策信息系統(tǒng)論域U上的劃分，RC是決策信息系統(tǒng)的等價(jià)關(guān)系，是等價(jià)關(guān)系矩陣，則其元素被定義為：

為了表示方便，下文中可簡(jiǎn)寫(xiě)為。

定義3[7] 假設(shè)決策信息系統(tǒng)為，U/C={X1，X2，…，Xm}是決策信息系統(tǒng)論域U上的劃分，決策信息系統(tǒng)條件屬性C的知識(shí)粒度定義為，且是矩陣所用元素的平均值。

定義4[6] 假設(shè)決策信息系統(tǒng)為，，分別是決策信息系統(tǒng)論域U上的等價(jià)關(guān)系矩陣，，決策信息系統(tǒng)C關(guān)于D的相對(duì)知識(shí)粒度定義為：

定義5[6] 假設(shè)決策信息系統(tǒng)為，，，，分別是決策信息系統(tǒng)論域U上的等價(jià)關(guān)系矩陣，，a在決策信息系統(tǒng)C相對(duì)于D的重要性（內(nèi)重要性）被定義為：

定義6[6] 假設(shè)決策信息系統(tǒng)為，C0?C，，，，分別是決策信息系統(tǒng)論域U上的等價(jià)關(guān)系矩陣，，屬性a在屬性C0相對(duì)于D的重要性（外重要性）定義為：

定義7[1] 假設(shè)決策信息系統(tǒng)為， B?C，B是決策信息系統(tǒng)約簡(jiǎn)當(dāng)且僅當(dāng)：

⑴ GD（D|B）=GD（D|C）；

⑵ 對(duì)于，使得GD（D|B-{a}）≠GD（D|C）。

根據(jù)上述相關(guān)的定義，許多學(xué)者提出了一種基于矩陣方法的非增量屬性約簡(jiǎn)算法[6]。

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

當(dāng)決策信息系統(tǒng)增加屬性時(shí)，用非增量屬性約簡(jiǎn)算法運(yùn)行變化后的決策信息系統(tǒng)，因?yàn)椴荒苡行Ю孟惹暗挠?jì)算結(jié)果，導(dǎo)致運(yùn)行速度較慢。為了快速獲得變化后決策信息系統(tǒng)的約簡(jiǎn)，設(shè)計(jì)了決策信息系統(tǒng)增加屬性后的增量屬性約簡(jiǎn)算法。

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

定義8 假設(shè)決策信息系統(tǒng)為，。假設(shè)增量屬性集是P，Rp是決策信息系統(tǒng)論域U上的一個(gè)等價(jià)關(guān)系，。決策信息系統(tǒng)增加屬性后的增量矩陣的元素定義為：

定義9 假設(shè)決策信息系統(tǒng)為，。假設(shè)增量屬性集是P，Rp是決策信息系統(tǒng)論域U上的一個(gè)等價(jià)關(guān)系，。決策信息系統(tǒng)增加屬性后的增量矩陣的元素定義為：

定理1 假設(shè)決策信息系統(tǒng)為，是決策信息系統(tǒng)的等價(jià)關(guān)系矩陣。假設(shè)：增量屬性集是P，Rp是決策信息系統(tǒng)論域U上的一個(gè)等價(jià)關(guān)系，決策信息系統(tǒng)增加屬性后的增量矩陣為，決策信息系統(tǒng)增加屬性后的知識(shí)粒度變?yōu)椋?/p>

其中，為矩陣所有元素的和。

定理2 假設(shè)決策信息系統(tǒng)為，是決策信息系統(tǒng)的等價(jià)關(guān)系矩陣。假設(shè)增量屬性集是P，Rp是決策信息系統(tǒng)論域U上的一個(gè)等價(jià)關(guān)系，決策信息系統(tǒng)增加屬性后的增量矩陣為，決策信息系統(tǒng)增加屬性后的知識(shí)粒度變?yōu)椋?/p>

定理3 假設(shè)決策信息系統(tǒng)為，、分別是決策信息系統(tǒng)的等價(jià)關(guān)系矩陣。假設(shè)增量屬性集是P，Rp是決策信息系統(tǒng)論域U上的一個(gè)等價(jià)關(guān)系，決策信息系統(tǒng)增加屬性后的增量矩陣分別為、，決策信息系統(tǒng)增加屬性后的知識(shí)粒度變?yōu)椋?/p>

2.2 屬性增加時(shí)基于矩陣方法的增量屬性約簡(jiǎn)算法

當(dāng)決策信息系統(tǒng)屬性增加時(shí)，根據(jù)上述計(jì)算決策信息系統(tǒng)等價(jià)關(guān)系矩陣和相對(duì)知識(shí)粒度增量機(jī)制的定義和定理，在原來(lái)決策信息系統(tǒng)相對(duì)知識(shí)粒度和約簡(jiǎn)的基礎(chǔ)上，設(shè)計(jì)了屬性增加時(shí)基于矩陣方法的增量屬性約簡(jiǎn)算法，算法的具體過(guò)程如Algorithm 1所示。

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

基于矩陣方法的增量算法的時(shí)間復(fù)雜度計(jì)算過(guò)程如下：當(dāng)決策信息系統(tǒng)增加屬性時(shí)，計(jì)算其相對(duì)知識(shí)粒度的時(shí)間復(fù)雜度為（其中w為增加屬性的數(shù)值），計(jì)算屬性增加后決策信息系統(tǒng)約簡(jiǎn)的時(shí)間復(fù)雜度為，刪除屬性約簡(jiǎn)中的冗余屬性時(shí)間復(fù)雜度為?；诰仃嚪椒ǖ脑隽考s簡(jiǎn)算法總的時(shí)間復(fù)雜度為。而文獻(xiàn)[6]所提出的非增量屬性約簡(jiǎn)算法總的時(shí)間復(fù)雜度為：

通過(guò)上述分析，我們可得非增量屬性約簡(jiǎn)算法的時(shí)間復(fù)雜度大于增量屬性約簡(jiǎn)算法的時(shí)間復(fù)雜度，表明了所提出的基于矩陣的增量屬性約簡(jiǎn)算法是可以有效處理動(dòng)態(tài)數(shù)據(jù)。

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

為了驗(yàn)證本文增量屬性約簡(jiǎn)算法的有效性，我們從公共數(shù)據(jù)集上下載了4組UCI數(shù)據(jù)集作為仿真實(shí)驗(yàn)數(shù)據(jù)集，數(shù)據(jù)集描述如表1所示，分別用增量和非增量屬性約簡(jiǎn)算法運(yùn)行這些數(shù)據(jù)集，并對(duì)增量屬性約簡(jiǎn)算法和非增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間進(jìn)行比較分析。

仿真實(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ù)集具體描述

[序號(hào) 數(shù)據(jù)集 行 條件屬性 決策屬性 1 Backup-large 307 35 19 2 Kr-vs-kp 3196 36 2 3 Ticdata2000 5822 85 2 4 Mushroom 5644 22 2 ]

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

在仿真實(shí)驗(yàn)的過(guò)程中，我們把表1的數(shù)據(jù)集按照屬性分成2部分，其中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）-（d）所示，其中縱軸表示計(jì)算約簡(jiǎn)的運(yùn)行時(shí)間，橫軸表示數(shù)據(jù)集中增加屬性的百分?jǐn)?shù)。圓形藍(lán)色線表示非增量屬性約簡(jiǎn)算法的計(jì)算時(shí)間，方形紅色線表示增量屬性約簡(jiǎn)算法的計(jì)算時(shí)間。

（a） Backup-large

（b） Kr-vs-kp

（c） Ticdata2000

（d） Mushroom

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

從圖1可得，當(dāng)決策信息系統(tǒng)屬性增加時(shí)，基于矩陣方法的增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)小于非增量屬性約簡(jiǎn)算法的運(yùn)行時(shí)間，說(shuō)明了所提出的基于矩陣方法的增量屬性約簡(jiǎn)算法是有效的。

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

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

表2 比較增量屬性約簡(jiǎn)算法和非增量屬性約

簡(jiǎn)算法獲得約簡(jiǎn)的分類精確度

[數(shù)據(jù)集 增量屬性約簡(jiǎn)算法 非增量屬性約簡(jiǎn)算法 Backup-large 0.811075 0.902280 Kr-vs-kp 0.901439 0.884543 Ticdata2000 0.730849 0.812405 Mushroom 0.997638 0.998819 ]

從表2可以看到非增量和增量屬性約簡(jiǎn)算法所獲得約簡(jiǎn)的分類精確度的數(shù)值是相近的，除數(shù)據(jù)集Kr-vs-kp，對(duì)于剩下的三個(gè)數(shù)據(jù)集，增量屬性約簡(jiǎn)算法獲得約簡(jiǎn)的分類精確度大于非增量算法獲得約簡(jiǎn)的分類精確度。實(shí)驗(yàn)結(jié)果表明了，當(dāng)決策信息系統(tǒng)條件屬性增加時(shí)，所提出的基于矩陣方法的增量屬性約簡(jiǎn)算法能夠找到一個(gè)有效的約簡(jiǎn)。

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

針對(duì)決策信息系統(tǒng)屬性增加時(shí)如何快速更新約簡(jiǎn)的問(wèn)題，本文首先探討了屬性增加后基于矩陣方法計(jì)算等價(jià)關(guān)系矩陣的增量更新機(jī)制，然后提出決策信息系統(tǒng)增加屬性時(shí)的增量屬性約簡(jiǎn)方法，最后在公共數(shù)據(jù)集下載UCI數(shù)據(jù)集并對(duì)所提出的基于矩陣方法的增量屬性約簡(jiǎn)算法進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了屬性增加時(shí)的基于矩陣方法的增量屬性約簡(jiǎn)算法是有效的。下一步將研究多粒度粗糙集模型中屬性變化下如何快速更新約簡(jiǎn)的問(wèn)題。

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

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

與實(shí)踐，2002.22（1）：48-5

[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] 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

[5] Feng Wang， Jiye Liang， Chuangyin Deng. Attribute

reduction：A dimension incremental strategy. Knowledge-

Based Systems，2013.39：95-108

[6] 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

[7] 王磊，葉軍.知識(shí)粒度計(jì)算的矩陣方法及其在屬性約簡(jiǎn)中的

應(yīng)用[J].計(jì)算機(jī)工程與科學(xué)，2013.35（3）：98-102

[8] Anping Zeng， Tianrui Li， Dun Liu， Junbo Zhang， Hongmei

Chen. A fuzzy rough set approach for incremental feature selection on hybrid information systems. Fuzzy Sets and Systems， 2015.258：39-60

[9] Wenhao Shu， Hong Shen. Updating attribute reduct in

incomplete decision systems with the variation of attribute set. International Journal of Approximate Reasoning，2014.55：867-884

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