基于維度變化的矩陣增量屬性約簡算法

閆俊輝

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

關鍵詞： 屬性約簡; 知識粒度; 等價關系; 矩陣; 增量機制

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

近些年，計算機網絡、通信以及存儲技術的快速發展，使得各行各業信息系統都有大量的數據積累，其對象的屬性值會發生動態變化。例如醫院里醫教科和人事科都有醫生的信息，在整合醫教科和人事科的醫生信息時，信息系統的屬性值會發生變化。此時，如何在原來的數據分析基礎上，快速更新對象的屬性值增加發生變化后決策信息系統的約簡問題，成為信息科學研究領域普遍關注的熱點。假若使用非增量屬性約簡算法[1-3]處理動態的數據屬性約簡，并不能充分利用先前計算的結果，導致運行速度減慢。

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

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

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

依據以上七個定義，很多研究該課題的學者就得到了基于矩陣的非增量屬性約簡算法[6]。

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

當決策信息系統屬性發生細微變化，并且對象值增加時。仍然用上面的算法來計算數據變化后的決策信息系統，由于不能用到之前的運算結果，要重復計算等價關系矩陣（定義2）、相對知識粒度（定義4）和約簡（定義7），這樣就浪費了更多的時間和存儲空間，使得運算速度變慢。為了解決對象值變化后決策信息系統約簡速度變慢的問題，本文提出了決策信息系統屬性值增加后的增量屬性約簡算法。

2.1 知識粒度的增量機制

2.2 屬性增加時的增量屬性約簡算法

當決策信息系統屬性發生細微變化，并且對象值增加時，參照上面運算得到的等價關系矩陣和知識粒度增量機制的定義和定理，在原有決策信息系統的知識粒度和約簡基礎上，提出了對象屬性值增加后的增量屬性約簡算法，算法的具體步驟如下：

3 實驗仿真測試

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

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

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

從圖1可以看出，當決策信息系統屬性對象值增加時，增量屬性約簡算法的運行時間遠遠小于非增量屬性約簡算法的運行時間，結果證明了增量屬性約簡算法能夠處理屬性值增加后的屬性約簡問題，并大大提高了效率。

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

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

從表2可以看出非，增量約簡算法和增量約簡算法獲得約簡的分類精確度的值是相近的。實驗結果證明，當決策信息系統條件屬性對象值增加時，增量屬性約簡算法所得到的約簡是有效地。

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] 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] 王磊，葉軍.知識粒度計算的矩陣方法及其在屬性約簡中的應用[J].計算機工程與科學，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].北京：科學出版社，2001