集值決策信息系統的增量式屬性約簡算法

王映龍，華佳佳，錢文彬，柳 軍

1(江西農業大學 計算機與信息工程學院，南昌 330045)

2(江西農業大學 軟件學院，南昌 330045)

3(江西省高等學校農業信息技術重點實驗室，南昌 330045)

1 引 言

粗糙集理論是一種用來處理各種不精確、不確定和模糊知識的軟計算工具，已被成功地應用于數據挖掘，模式識別，人工智能，機器學習等多個領域[1，2].屬性約簡是粗糙集研究的核心內容之一，屬性約簡是在保持決策系統分類能力不變的前提下，刪除不必要的和冗余的屬性，以保證知識的簡潔性[3-5].目前粗糙集模型屬性約簡大多針對靜態信息系統，而在大數據時代，信息系統每時每刻會增加大量的實時數據，信息系統中的對象經常隨著時間的變化而增加，在數據動態變化的環境下，傳統的靜態屬性約簡方法較難高效地從動態數據中提取有用的知識，因此，對于粗糙集的數據增量式更新方法的研究有著重要的現實意義.增量式更新方法是在原有的知識基礎上，將原有知識與新產生的數據相結合，通過更新部分變化的數據，避免重復計算原有數據，從而直接獲取到新的知識.文獻[10]利用簡化二進制差別矩陣和位圖運算的設計思想，提出了一種基于決策表的屬性約簡增量式更新算法；文獻[11]結合云計算中的并行計算模型MapReduce和增量更新方法，設計了兩種并行增量更新近似集算法；文獻[12]定義了標記函數，提出了一種基于標記可辨識矩陣的增量式約簡模型.目前，增量式方法研究主要針對完備的信息系統，即屬性值是完備的，不缺失的.但在現實應用中，許多數據由于記錄的疏忽，獲取的誤差，技術的限制等等因素而無法準確獲取完備的數據集，從而產生了不完備信息系統，集值信息系統作為一般信息系統的推廣，可用來處理數據缺失和數據不完備的信息系統[13，14].近年來，許多學者對集值信息系統做了大量的研究，提出了很多有效的知識約簡算法.文獻[15]在集值信息系統中提出了一種基于概念格的知識獲取模型，討論了粒化模型和格代數結構；文獻[16]在集值序信息系統中提出了δ-優勢關系，利用信息熵和知識粒度來度量信息系統的不確定性；文獻[17]在優勢關系基礎上提出了一種多粒度優勢關系粗糙集模型，能夠適應復雜的多源信息環境.然而，對于集值決策信息系統的對象屬性增量式變化對屬性約簡的算法研究，報道相對較少，在對象屬性發生動態變化的環境下如何快速高效地找到一個新的約簡知識，已成為信息系統動態屬性約簡課題的研究熱點.

為此，本文針對集值決策信息系統中對象的動態變化問題，研究了新增對象對信息系統中分布協調集的影響，討論了對象與分布約簡的理論關系，在靜態分布約簡的算法基礎上，提出了集值決策信息系統的增量式屬性約簡算法，當新增對象加入到決策信息系統時，能夠利用原決策信息系統的約簡知識，快速更新分布協調集，通過極小析取范式得到屬性約簡.增量式算法能夠避免大量的重復計算，在一定程度上能有效提高算法的計算效率，滿足數據挖掘需求.

2 相關知識

定義1[6]. 設S=(U，A，D，V，f)是集值決策信息系統，其中，U為有限非空論域，U={x1，x2，…，xn}；A為條件屬性集合，A={a1，a2，…，an}；D為決策屬性集合，D={d1，d2，…，dn}；V=∪a∈A∪DVa，Va為屬性a的值域；f：U×A∪D→V為信息映射函數，對于?a∈A∪D，x∈U，有f(x，a)∈Va.

={y∈U|fa(x)∩fa(y)≠φ，?a∈B}，則稱[xi]B為相似類.

定義3.設S=(U，A，D，V，f)是集值決策信息系統，則U上的決策劃分定義為：

={y∈U|fd(x)∩fd(y)≠φ，?d∈D}，[x]D為決策等價類.

定義4.[7]設S=(U，A，D，V，f)是集值決策信息系統，有?xi∈U，記：

定理2. 設S=(U，A，D，V，f)是集值決策信息系統，B?A，若B為分布協調集，則：

證明:由定理1可知.

3 集值決策信息系統的增量式屬性約簡算法

當有新對象增加到決策信息系統時，若使用靜態屬性約簡算法重新計算所有數據，將會耗費大量的計算時間和存儲空間，為了有效提高約簡效率，能夠在原有的知識基礎上，快速找到對象增加后的屬性約簡，提出了集值決策信息系統的增量式屬性約簡算法.

3.1 增量式屬性約簡原理

定義8. 設S=(U，A，D，V，f)是集值決策信息系統，決策等價類D={D1，D2，…，Dr}，論域U中增加一個對象xn+1，記S′=(U′，A，D，V，f)，則定義：

γA(xi，xn+1)={a∈A|fa(xi)∩fa(xn+1)=φ，1≤i≤n}，

記γA={γA(x1，xn+1)，γA(x2，xn+1)，…，γ(xn，xn+1)}.

定理4. 設S=(U，A，D，V，f)是集值決策信息系統，決策等價類D={D1，D2，…，Dr}，若論域U中增加一個對象xn+1，記S′=(U′，A，D，V，f)，則有：

1)若?xi∈U，fa(xi)∩fa(xn+1)≠φ，則有γA(xi，xn+1)=φ，xn+1的相似類[xn+1]A={xi，xn+1}.

(4)Ⅱ中雖未檢測出Cl2,但Cl-在陽極是否放電仍需進一步驗證。電解pH=1的NaCl溶液做對照實驗,記錄如表2。

證明：

1)由于fa(xi)∩fa(xn+1)≠φ，γA(xi，xn+1)={a∈A|fa(xi)∩fa(xn+1)=φ，1≤i≤n}得知γA(xi，xn+1)=φ.由定義2可知xn+1的相似類[xn+1]A={xi，xn+1}.

3.2 屬性約簡的增量機制

圖1 屬性約簡增量機制Fig.1 Incremental mechanism of attribute reduction

根據上述分析可知，當對象增加到信息系統中時，存在四種不同的分布協調集更新情況，為此得到在集值決策信息系統中屬性約簡的更新機制，如圖1所示.

3.3 集值決策信息系統的增量式屬性約簡算法

3.3.1 算法描述

根據定義6和定理2得到集值決策信息系統的分布協調集B，當集值決策信息系統S中有新的對象增加時，更新原有的分布協調集，不必對全部知識進行重新操作.并根據增量式屬性約簡原理和增量機制圖，設計了集值決策信息系統的增量式屬性約簡算法，算法能夠在原有的知識基礎上，快速得到更新后的屬性約簡，算法如下：

算法1. 集值決策信息系統的增量式屬性約簡算法

輸入：集值決策信息系統S=(U，A，D，V，f)，分布協調集B，分布函數值μ(xi)，1≤i≤n.新增對象xn+1，新決策信息系統記為S′=(U′，A，D，V，f)，新決策信息系統的分布函數值為μ′(xi)，1≤i≤n+1.其中，U′=U∪xn+1，U={x1，x2，…，xn}；

Step1. 根據定理4，對象xn+1加入信息系統時，生成關于對象xn+1的協調集：γA={γA(x1，xn+1)，γA(x2，xn+1)，…，γ(xn，xn+1)}；

Step2. if(γA(xi，xn+1)≠φ，即fa(xi)∩fa(xn+1)=φ)

Step2.1. if(fa(xi)∩fa(xn+1)=φ∧xn+1∈Dr)

由定理3可知[xn+1]A={xn+1}；

γA=γA-γA(xi，xn+1)；

更新分布協調集B=B∪γA(去除重復的差別屬性集)；

elseB=B∪γA(去除重復的差別屬性集)；

Step2.2. if(fa(xi)∩fa(xn+1)=φ∧xn+1?Dr)

由定理3可知[xn+1]A={xn+1}；

γA=γA-γA(xi，xn+1)；

更新分布協調集B=B∪γA(去除重復的差別屬性集)；

elseB=B∪γA(去除重復的差別屬性集)；

Step3. if(γA(xj，xn+1)=φ，即fa(xj)∩fa(xn+1)≠φ)

Step3.1. if(fa(xj)∩fa(xn+1)≠φ∧xn+1∈Dr)

由定理4可知[xn+1]A={xj，xn+1}；

{xj，xn+1}?[xj]A；

elseB=B；

則γA=γA-γA(xi，xn+1)，B=B∪γA(去除重復的差別屬性集);

elseB=B∪γA(去除重復的差別屬性集)；

Step3.2. if(fa(xi)∩fa(xn+1)≠φ∧xn+1?Dr)

由定理4可知[xn+1]A={xj，xn+1}；

{xj，xn+1}?[xj]A；

elseB=B；

則γA=γA-γA(xi，xn+1)，B=B∪γA(去除重復的差別屬性集)；

elseB=B∪γA(去除重復的差別屬性集)；

Step4. 根據定義7可計算極小析取范式：

3.3.2 算法復雜度分析

Step1. 將新增對象xn+1加入U中，生成關于xn+1的協調集γA，其時間復雜度為O(|U′||A|)；

Step2. 判斷γA(xi，xn+1)是否為空集，只需掃描一次γA中的差別屬性即可，時間復雜度為O(|U|).

Step4. 根據更新后的分布協調集，計算極小析取范式的時間復雜度為O(|A|2).

綜上所述，該算法的時間復雜度為O(|U′||A|)，空間復雜度為O(|B||A|).

3.3.3 同類算法的比較與分析

文獻[8]提出了一種信息觀下基于不一致領域的批增量式約簡模型，算法時間復雜度為O(|U′|2·(|A|-|red|)3)，文獻[8]在計算找到新增樣本的不一致鄰域時，將原樣本集與新增樣本集一起進行約簡，在這個過程中需消耗較多的時間，計算過程較為復雜.本文只需考慮新增樣本對分布協調集的影響，從而更新分布協調集得到最后的約簡結果，故本文的算法在計算效率上較好于文獻[8].文獻[9]提出了一種基于關系矩陣決策表的增量式屬性約簡算法，算法需計算條件屬性下的等價關系矩陣，矩陣算法操作比較容易，但在處理大規模數據或者增量式數據時，算法需要消耗許多存儲空間，此算法的時間復雜度為O(|U′/A|2|A|)，空間復雜度為O(|U′|2|A|).本文若采用文獻[9]中矩陣的思想，當有新的對象增加時，需消耗|U′|2|A|個存儲空間來存儲矩陣元素，而本文只需要|B||A|個存儲空間.為此，本文算法的計算效率和所需的存儲空間在一定程度上好于文獻[9].下面給出不同算法的比較與分析結果，如表1所示.

表1 不同算法的比較與分析Table1 Comparison and analysis of different algorithms

4 實例分析

為了進一步分析本文算法的有效性，下面將以表2集值決策信息系統S=(U，A，D，V，f)為例進行詳細地分析和驗證.集值決策信息系統中論域U={x1，x2，x3，x4，x5，x6}，條件屬性A={a1，a2，a3，a4}，決策屬性D=g0gggggg，新增對象為xn+1，新的集值決策信息系統為S′={U′，A，D，V，f}，其中U′=U+{xn+1}，1≤n≤6.

表2 集值決策信息系統Table 2 Set-valued decision information system

根據定義4-7和定理2可得到如下知識：

每個對象的μA(xi)值：

分布協調集為：B={(a4)(a4)(a4)(a1，a2，a4)(a3，a4)(a1，a4) (a4)(a4)(a3)(a3)(a3)}；

分布約簡結果為(a3，a4).

根據算法1計算增量式屬性約簡過程如下：

1)新增對象x7=[{2}，{3}，{3，4}，{2}，2]；

(1)根據算法的Step 1得到關于x7的協調集：

γA={(a1a2)(a2)(a2a4)(a1a2a4)(a2a4)(a2a4)}；

(2)根據算法Step 2可知γA(xi，x7)≠φ，fa(xi)∩fa(x7)=φ且x7∈Dr，故屬于情況(1)：

x7的相似類為[x7]A={x7}；

決策等價類D1={x1，x2，x4，x6}，D2={x3，x7}，D3={x5}；

故根據算法Step 2.1 得計算得到：

γA=γA-γA(x3，x7)={(a1a2)(a2)(a1a2a4)(a2a4)(a2a4)}；

③更新分布協調集B=B∪γA(去除重復的差別屬性集)

得B={(a1a2)(a2)(a1a2a4)(a4)(a3a4)(a1a4)(a3)}；

(3)根據算法Step 4計算極小析取范式：

(a3∨a4)∧(a1∧a4)∧a3

=a2∧a3∧a4

因此得到最終的增量式屬性約簡為(a2，a3，a4).

2)新增對象x7=[{2}，{3}，{3，4}，{2}，4]；

(1)根據算法的Step 1得到關于x7的協調集：

γA={(a1a2)(a2)(a2a4)(a1a2a4)(a2a4)(a2a4)}；

(2)根據算法Step 2可知γA(xi，x7)≠φ，fa(xi)∩fa(x7)=φ且x7?Dr，故屬于情況(2)：

x7的相似類為[x7]A={x7}；

故根據算法Step 2.2 可計算得：γA=γA-γA(x3，x7)={(a1a2)(a2)(a1a2a4)(a2a4)(a2a4)}；

③更新分布協調集B=B∪γA(去除重復的差別屬性集)

得B={(a1a2)(a2)(a1a2a4)(a4)(a3a4)(a1a4)(a3)}

(3)根據算法Step 4計算極小析取范式：

(a3∨a4)∧(a1∧a4)∧a3

=a2∧a3∧a4

因此得到最終的增量式屬性約簡為(a2，a3，a4).

3)新增對象x7=[{2，3}，{2}，{4}，{1，2}，3]；

(1)根據算法的Step 1得到關于x7的協調集：

γA={(a1)(a3)(a1a3)(a3)(a2a3)}；

(2)根據算法Step 2可知γA(x3，x7)=φ，fa(x3)∩fa(x7)≠φ且x7∈Dr，故屬于情況(3)：

x3的相似類為[x3]A={x3，x7}；

x7的相似類為[x7]A={x3，x7}；

決策等價類D1={x1，x2，x4，x6}，D2={x3}，D3={x5，x7}；

故根據算法Step 3.1 得B=B∪γA；

④更新分布協調集B=B∪γA(去除重復的差別屬性集)得：B={(a4)(a1a2a4)(a3a4)(a1a4)(a3)(a1)(a1a3)(a2a3)}；

(3)根據算法Step 4計算極小析取范式：

因此，得到最終的增量式屬性約簡為(a1，a3，a4).

4)新增對象x7=[{2，3}，{2}，{4}，{1，2}，4]；

(1)根據算法的Step 1得到關于x7的協調集：

γA={(a1)(a3)(a1a3)(a3)(a2a3)}；

(2)根據算法Step 2可知γA(x3，x7)=φ，fa(x3)∩fa(x7)≠φ且x7?Dr，故屬于情況(4)：

x3的相似類為[x3]A={x3，x7}；

x7的相似類為[x7]A={x3，x7}；

④更新分布協調集B=B∪γA(去除重復的差別屬性集集合)得B={(a4)(a1a2a4)(a3a4)(a1a4)(a3)(a1)(a1a3)(a2a3)}；

(3)根據算法Step 4計算極小析取范式：

因此得到最終的增量式屬性約簡為(a1，a3，a4).

通過上述實例分析可知，本文增量式屬性約簡算法能有效利用原信息系統的分布協調集知識，避免了許多重復計算，并節省了一定的存儲空間，當數據新增到信息系統中時，只需更新原有的分布協調集，快速獲得更新后的屬性約簡.而在文獻[9]中計算等價關系矩陣需消耗較多的存儲空間，在實例中，若采用文獻[9]中矩陣的思想需開辟49×4個存儲空間用來存儲數據，而本文增量式算法在(1)和(2)情況下僅需開辟25個存儲空間，在去除重復屬性后，需12個存儲空間用來存儲非空差別元素，在(3)和(4)情況下需開辟22個存儲空間，在去除重復屬性后，需14個存儲空間用來存儲非空差別元素，讓空間資源得到了有效的利用.

5 結 語

集值信息系統作為單值信息系統的擴展，可用來處理不完備信息系統，隨著集值信息系統在實際應用中的廣泛應用，如何在數據信息增量式更新的情況下，快速得到屬性約簡已成為一個備受關注的問題.因此本文針對集值決策信息系統，討論了新增對象與分布約簡的理論關系，設計了對象增加時快速更新分布協調集以得到更新后的屬性約簡算法，算法能有效利用原有的分布協調集知識，避免了許多重復計算，并利用極小析取范式獲得更新后的屬性約簡，為研究集值決策信息系統的增量式更新屬性約簡問題提供了一種可借鑒的方法.

：

[1] Pawlak Z.Rough set theory and applications to data analysis[J].Cybernetics and Systems，1998，29(7)：661-688.

[2] Wang Guo-yin.Rough set theory and knowledge acquisition [M].Xi′an ：Xi′an Jiaotong University Press，2001.

[3] Xu Zhang-yan，Liu Zuo-peng，Yang Bing-ru，et al.An quick attribution reduction algorithm with complexity of max (O(|C||U|)，O(|C|2|U/C|))[J].Chinese Journal of Computer，2006，29(3)：391-399.

[4] Chen Hao，Yang Jun-an，Zhuang Zhen-quan.The core of attributes and minimal attributes reduction in variable precision rough set[J].Chinese Journal of Computer，2012，35(5)：1011-1017.

[5] Eskandari S，Javidi M M.Online streaming feature selection using rough sets[J].International Journal of Approximate Reasoning，2016，69(1)：35-57.

[6] Zhang J B，Li T R，Ruan D，et al.Rough sets based matrix approaches with dynamic attribute variation in set-valued information systems[J].International Journal of Approximate Reasoning,2012，53(4)：620-635.

[7] Zhang Wen-xiu，Mi Ju-sheng，Wu Wei-zhi.Knowledge reductions in inconsistent information systems[J].Chinese Journal of Computer，2003，26(1)：12-18.

[8] Zhang Kuo，Xu Xin-ying，Xie Jun，et al.Batch of incremental attribute reduction based on inconsistent neighborhood[J].Computer Engineering and Design，2017，38(6)：1526-1531.

[9] Jing Yun-ge.Incremental reduction algorithm for decision table based on relationship matrix[J].Journal of Chinese Computer Systems，2015，36(5)：1069-1072.

[10] Qian Wen-bin，Yang Bing-ru，Xu Zhang-yan.Quick and incremental updating algorithm for attribute reduction in decision table[J].Journal of Chinese Computer Systems，2012，33(2)：254-258.

[11] Zhang Jun-bo，Li Tian-rui，Pan Yi，et al.Parallel and incremental algorithm for knowledge update based on rough sets in cloud platform[J].Journal of Software，2015，26(5)：1064-1078.

[12] Yin Lin-zi，Yang Chun-hua，Wang Xiao-li，et al.An incremental algorithm for attribute reduction based on labeled discerniblility matix[J].Acta Automatica Sinica，2014，40(3)：397-404.

[13] Mo Jing-lan，Zhu Guang-sheng，Lv Yue-jin.Dominance-based rough set approach and knowledge reductions in generalized incomplete ordered system[J].Journal of Chinese Computer Systems，2015，36(12)：2735-2739.

[14] Wang G Y，Ma X A，Yu H.Monotonic uncertainty measures for attribute reduction in probabilistic rough set model[J].International Journal of Approximate Reasoning，2015，59(C)：41-67.

[15] Kang Xiang-ping，Miao Duo-qian.A knowledge acquisition method based on concept lattice in set-valued information systems[J].CAAI Transactions on Intelligent Systems，2016，11(3)：287-293.

[16] Bao Zhong-kui.Information entropy and knowledge granulation for set-valued ordered information systems[J].Computer Engineering and Applications，2014，50(24)：38-41.

[17] Zhuang Ying，Liu Wen-qi，Fan Min，et al.Multi-granulation dominance relation and information fusion based on set-valued information system[J].Pattern Recognition and Artificial Intelligence，2015，28(8)：741-749.

附中文參考文獻：

[2] 王國胤.Rough集理論與知識獲取[M].西安：西安交通大學出版社，2001.

[3] 徐章艷，劉作鵬，楊炳儒，等.一個復雜度為max(O(|C||U|)，O(|C|2|U/C|))的快速屬性約簡算法[J].計算機學報，2006，29(3)：391-399.

[4] 陳 昊，楊俊安，莊鎮泉.變精度粗糙集的屬性核和最小屬性約簡算法[J].計算機學報，2012，35(5)：1011-1017.

[7] 張文修，米據生，吳偉志.不協調目標信息系統的知識約簡[J].計算機學報，2003，26(1)：12-18.

[8] 張 擴，續欣瑩，謝 珺，等.基于不一致鄰域的批增量式屬性約簡[J].計算機工程與設計，2017，38(6)：1526-1531.

[9] 景運革.一種基于關系矩陣決策表增量式約簡算法[J].小型微型計算機系統，2015，36(5)：1069-1072.

[10] 錢文彬，楊炳儒，徐章艷.一種基于決策表的屬性約簡增量式快速更新算法[J].小型微型計算機系統，2012，33(2)：254-258.

[11] 張鈞波，李天瑞，潘 毅，等.云平臺下基于粗糙集的并行增量知識更新算法[J].軟件學報，2015，26(5)：1064-1078.

[12] 尹林子，陽春華，王曉麗，等.基于標記可辨識矩陣的增量式屬性約簡算法[J].自動化學報，2014，40(3)：397-404.

[13] 莫京蘭，朱廣生，呂躍進.廣義不完備序值信息系統中的知識約簡[J].小型微型計算機系統，2015，36(12)：2735-2739.

[15] 康向平，苗奪謙.一種基于概念格的集值信息系統中的知識獲取方法[J].智能系統學報，2016，11(3)：287-293.

[16] 鮑忠奎.集值序信息系統的信息熵和知識粒度[J].計算機工程與應用，2014，50(24)：38-41.

[17] 莊 穎，劉文奇，范 敏，等.集值信息系統上的多粒度優勢關系與信息融合[J].模式識別與人工智能，2015，28(8)：741-749.