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

閆鑫 閆俊輝

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

關鍵詞： 粗糙集； 增量機制； 屬性約簡； 知識粒度

中圖分類號：TP18 文獻標志碼：A 文章編號：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 引言

隨著通信和計算機技術的迅速發展，各行各業都積累了大量數據，數據每時每刻都在動態變化。例如學校教務部門和人事部門都有教師的信息，如果把教務部門和人事部門的教師信息整合起來，就會造成信息系統屬性增加等。針對決策信息系統屬性增加時如何快速更新約簡問題，如果使用非增量屬性約簡算法[1-3]來處理動態數據屬性約簡時，不能有效利用先前的計算結果，導致運行速度較慢。

由于非增量屬性約簡算法不能有效處理動態變化數據屬性約簡的問題，因此很多學者設計了增量屬性約簡算法去解決動態變化數據屬性約簡的問題。Qian等根據決策信息系統中屬性動態增加和減少情況下的信息粒度變化規律，提出正向近似和逆向近似，并成功應用于啟發式屬性約簡算法的加速，為基于粗糙集的知識發現性能優化提供了新思路[4]；Wang等分析了一些屬性動態增加情況下三種信息熵的增量變化機制，提出了一種基于信息熵的增量屬性約簡算法[5]；Jing針對決策信息系統對象屬性集動態變化時如何快速計算約簡問題，討論了計算等價關系矩陣和相對知識粒度的增量更新原理，提出了基于對象增加時動態屬性約簡算法[6]； 王磊等分析了屬性動態變化下用矩陣方法計算知識粒度的增量更新原理，提出了一種屬性集動態變化增量屬性約簡算法[7]；Zeng等給出了一種新的混合距離概念，結合混合距離和高斯核，分析了當決策信息系統在屬性變化下屬性約簡的增量更新機制，提出了混合決策信息系統中基于模糊粗糙集動態屬性約簡算法，并對該算法進行了實驗驗證[8]。Shu等在不完備系統中，分析了屬性集動態增加或刪除情況下決策信息系統正區域的動態更新機制，提出了基于正區域的動態屬性約簡算法[9]。根據上面分析，當決策信息系統屬性增加時，大多數增量算法主要通過更新信息熵和正區域實現快速獲取變化后決策信息系統的約簡，而通過更新知識粒度實現快速獲取變化后決策信息系統約簡的算法研究較少。

矩陣在處理數值計算方面具有很大的優勢，已被廣泛應用到數據挖掘、數值分析和知識發現等學科領域中。針對決策信息系統屬性增加后如何快速計算變化后決策信息系統約簡的問題，首先探討了計算變化后決策信息系統相對知識粒度和等價關系矩陣的增量更新機制，然后設計了決策信息系統屬性增加后的增量屬性約簡方法，最后通過UCI數據對所提出的增量屬性約簡算法的性能進行了測試，實驗結果驗證了所提出的增量屬性約簡算法能有效處理動態屬性約簡的問題。

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

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

定義2[6] 假設決策信息系統為， U/C={X1，X2，…，Xm}是決策信息系統論域U上的劃分，RC是決策信息系統的等價關系，是等價關系矩陣，則其元素被定義為：

為了表示方便，下文中可簡寫為。

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

定義4[6] 假設決策信息系統為，，分別是決策信息系統論域U上的等價關系矩陣，，決策信息系統C關于D的相對知識粒度定義為：

定義5[6] 假設決策信息系統為，，，，分別是決策信息系統論域U上的等價關系矩陣，，a在決策信息系統C相對于D的重要性（內重要性）被定義為：

定義6[6] 假設決策信息系統為，C0?C，，，，分別是決策信息系統論域U上的等價關系矩陣，，屬性a在屬性C0相對于D的重要性（外重要性）定義為：

定義7[1] 假設決策信息系統為， B?C，B是決策信息系統約簡當且僅當：

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

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

根據上述相關的定義，許多學者提出了一種基于矩陣方法的非增量屬性約簡算法[6]。

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

當決策信息系統增加屬性時，用非增量屬性約簡算法運行變化后的決策信息系統，因為不能有效利用先前的計算結果，導致運行速度較慢。為了快速獲得變化后決策信息系統的約簡，設計了決策信息系統增加屬性后的增量屬性約簡算法。

2.1 知識粒度的增量機制

定義8 假設決策信息系統為，。假設增量屬性集是P，Rp是決策信息系統論域U上的一個等價關系，。決策信息系統增加屬性后的增量矩陣的元素定義為：

定義9 假設決策信息系統為，。假設增量屬性集是P，Rp是決策信息系統論域U上的一個等價關系，。決策信息系統增加屬性后的增量矩陣的元素定義為：

定理1 假設決策信息系統為，是決策信息系統的等價關系矩陣。假設：增量屬性集是P，Rp是決策信息系統論域U上的一個等價關系，決策信息系統增加屬性后的增量矩陣為，決策信息系統增加屬性后的知識粒度變為：

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

定理2 假設決策信息系統為，是決策信息系統的等價關系矩陣。假設增量屬性集是P，Rp是決策信息系統論域U上的一個等價關系，決策信息系統增加屬性后的增量矩陣為，決策信息系統增加屬性后的知識粒度變為：

定理3 假設決策信息系統為，、分別是決策信息系統的等價關系矩陣。假設增量屬性集是P，Rp是決策信息系統論域U上的一個等價關系，決策信息系統增加屬性后的增量矩陣分別為、，決策信息系統增加屬性后的知識粒度變為：

2.2 屬性增加時基于矩陣方法的增量屬性約簡算法

當決策信息系統屬性增加時，根據上述計算決策信息系統等價關系矩陣和相對知識粒度增量機制的定義和定理，在原來決策信息系統相對知識粒度和約簡的基礎上，設計了屬性增加時基于矩陣方法的增量屬性約簡算法，算法的具體過程如Algorithm 1所示。

2.3 算法復雜度分析

基于矩陣方法的增量算法的時間復雜度計算過程如下：當決策信息系統增加屬性時，計算其相對知識粒度的時間復雜度為（其中w為增加屬性的數值），計算屬性增加后決策信息系統約簡的時間復雜度為，刪除屬性約簡中的冗余屬性時間復雜度為。基于矩陣方法的增量約簡算法總的時間復雜度為。而文獻[6]所提出的非增量屬性約簡算法總的時間復雜度為：

通過上述分析，我們可得非增量屬性約簡算法的時間復雜度大于增量屬性約簡算法的時間復雜度，表明了所提出的基于矩陣的增量屬性約簡算法是可以有效處理動態數據。

3 實驗仿真分析

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

仿真實驗的硬件環境：CPU Pentium（R） Dual-Core E5800 3.20GHz，內存Samsung DDR3 SDRAM，4.0GB。

實驗仿真；軟件環境：64-bit Windows 10操作系統，64-bits （JDK 1.6.0_20）和Eclipse 3.7。

表1 數據集具體描述

[序號 數據集 行 條件屬性 決策屬性 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 增量屬性約簡算法與非增量屬性約簡算法運行時間比較

在仿真實驗的過程中，我們把表1的數據集按照屬性分成2部分，其中50%的條件屬性和決策屬性為基本數據集，剩余50%的數據在按照數學的20%、40%、60%、80%、100%依次作為增量屬性集，分別用增量和非增量屬性約簡算法運行這些數據集，仿真實驗結果如圖1（a）-（d）所示，其中縱軸表示計算約簡的運行時間，橫軸表示數據集中增加屬性的百分數。圓形藍色線表示非增量屬性約簡算法的計算時間，方形紅色線表示增量屬性約簡算法的計算時間。

（a） Backup-large

（b） Kr-vs-kp

（c） Ticdata2000

（d） Mushroom

圖1 增量屬性約簡算法和非增量屬性約簡算法運行時間的比較

從圖1可得，當決策信息系統屬性增加時，基于矩陣方法的增量屬性約簡算法的運行時間遠遠小于非增量屬性約簡算法的運行時間，說明了所提出的基于矩陣方法的增量屬性約簡算法是有效的。

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

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

表2 比較增量屬性約簡算法和非增量屬性約

簡算法獲得約簡的分類精確度

[數據集 增量屬性約簡算法 非增量屬性約簡算法 Backup-large 0.811075 0.902280 Kr-vs-kp 0.901439 0.884543 Ticdata2000 0.730849 0.812405 Mushroom 0.997638 0.998819 ]

從表2可以看到非增量和增量屬性約簡算法所獲得約簡的分類精確度的數值是相近的，除數據集Kr-vs-kp，對于剩下的三個數據集，增量屬性約簡算法獲得約簡的分類精確度大于非增量算法獲得約簡的分類精確度。實驗結果表明了，當決策信息系統條件屬性增加時，所提出的基于矩陣方法的增量屬性約簡算法能夠找到一個有效的約簡。

4 結束語

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

參考文獻（References）：

[1] 苖奪謙，范世棟.知識粒度的計算及其應用[J].系統工程理論

與實踐，2002.22（1）：48-5

[2] 王國胤，于洪，楊大春.基于條件信息熵的決策表約簡[J].計算

機學報，2002.25（7）：760-765

[3] 梁吉業，曲開社，徐宗本.信息系統的屬性約簡[J].系統工程理

論與實踐，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] 王磊，葉軍.知識粒度計算的矩陣方法及其在屬性約簡中的

應用[J].計算機工程與科學，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].科學出版社，2001.