屬性集變化條件下集值決策信息系統的增量屬性約簡方法

劉 超，王 磊*，楊 文，鐘強強，黎 敏

（1.南昌工程學院信息工程學院，南昌 330099；2.江西省水信息協同感知與智能處理重點實驗室（南昌工程學院），南昌 330099）

0 引言

由波蘭數學家Pawlak［1］所提出的經典粗糙集理論是一個強大的數學工具，可用于描述屬性間的依存關系，評估屬性的重要性，并從決策表中導出規則。運用粗糙集理論還可以用來解決很多帶有不確定性、模糊性的實際問題，目前在醫學、金融、特征選擇、圖像處理、語音識別等領域都有著非常重要的應用。

經典粗糙集理論主要是運用不可分辨關系，即等價關系對論域上的對象在屬性集上進行劃分。它的應用是面向完備系統的，也就是說每個對象的屬性值都必須是完整的、精確的、沒有缺失值的。然而由于現實因素的影響，數據存在多樣性，一個對象的某些屬性值可能含有多個值，即決策信息系統中出現了集值型數據。這些集值通常用于描述決策信息系統中的不確定信息和缺失信息。集值決策信息系統被認為是單值決策信息系統的一個重要拓展模型，因此等價關系模型下的屬性約簡不再適用于集值系統。對此，許多學者針對集值系統進行了一系列的研究。Kryszkiewicz［2］提出了基于容差關系的粗糙集模型；吳鵬等［3］提出了一種基于集值的k度相容關系的粗糙集模型；喬全喜等［4］提出了一種集值系統下基于相對限制容差關系的屬性約簡方法；Guan 等［5］為了從集值決策信息系統中導出最優決策規則，提出了最大容差類的相對約簡的概念，并定義了一種差別函數，通過布爾推理技術計算相對約簡；Qian 等［6］針對集值序信息系統提出了一種基于優勢關系的粗糙集方法；Dai 等［7］在集值系統中定義了信息熵和粒度測度的概念，并研究了它們的一些性質；Wei 等［8］提出了兩種模糊粗糙近似模型，并定義了兩種相應的相對正區域約簡方法；馬建敏等［9］在集值信息系統中基于相容關系給出了信息量的概念，提出了一種啟發式約簡方法；劉瑩瑩等［10］將相似度的概念引入到集值信息系統中，對無核型的集值信息系統求取屬性約簡更加有效。以上研究均是基于靜態下的集值系統，對于一部分問題能夠得到有效處理。

在實際應用中，許多實際信息系統的屬性集會發生動態變化，由此屬性約簡的結果也會隨之而變化。非增量式方法通常是不可行的，這是由于它們需要從頭開始計算并消耗大量的計算時間，而增量式方法被認為是處理動態變化數據的有效技術，因為它們可以在先前的計算結果基礎上直接進行計算。鑒于集值決策信息系統中數據的動態變化，許多學者在此方面進行了系統、深入的研究。如：Zhang 等［11］在集值系統中提出了一種構造關系矩陣的方法來求解上下近似，并且在屬性增加時給出了相應的增量式方法來更新近似集；鄒維麗等［12］給出了在相容關系和擬序關系下的集值粗糙集模型的近似增量式更新方法；王映龍等［13-14］針對集值決策系統下屬性集增加的情形，提出了一種基于信息量的動態屬性約簡方法，在對象增加時，討論了新增對象與分布式約簡的理論關系，并提出了一種快速更新分布協調集的增量式方法；Luo 等［15］提出了在集值決策系統中通過增加和刪除標準值來計算近似集的增量式方法。上述研究推動了集值決策信息系統領域各方面研究的蓬勃發展，然而，在集值決策信息系統的屬性集發生變化條件下有關增量式屬性約簡方面的研究報道相對較少。

鑒于此，本文針對集值決策信息系統，首先引入集值關系矩陣，隨后將知識粒度的矩陣表示方法拓展到集值決策信息系統，并將其應用于啟發式屬性約簡的計算；然后，分析集值決策信息系統在屬性增加條件下屬性約簡的增量機制，設計了一種增量式屬性約簡方法；最后通過實驗驗證了方法的有效性。

1 集值決策信息系統基本概念

本章首先介紹集值決策信息系統的基礎知識，然后給出集值決策信息系統中集值關系矩陣的定義，在此基礎上將文獻［16］中知識粒度的矩陣表示推廣至集值決策信息系統之中。

定義1集值決策信息系統SDS=(U，A，V，f)。其中：U為非空有限對象的集合；A=C∪D是一個非空有限的屬性集合，C是條件屬性的集合，D是決策屬性的集合，對于?a∈C∪D，a的屬性值Va的取值為一個集合；V是信息函數f的值域，滿足V=；f是一個信息函數，它指定U中每一個對象的屬性值。

例1 表1 是一個集值決策信息系統，其中U={x1，x2，x3，x4，x5，x6，x7，x8}為論域，條件屬性集為C={a1，a2，a3，a4，a5}，決策屬性集為D=g0gggggg。

表1 集值決策信息系統Tab.1 Set-valued decision information system

定義2給定一個集值信息系統SIS=(U，C，V，f)，對于?B?C，SB是論域U上的集值關系，表示為：

定義3給定一個集值決策信息系統SDS=(U，A，V，f)，A=C∪D，條件屬性子集B?C，且有?b∈B，決策屬性D=g0gggggg，決策屬性d所對應的U上的決策劃分為U/d={(xi，xj)|(xi，xj)∈U2，f(xi，d)=f(xj，d)}；屬性集B∪d的集值關系矩陣為，那么SB∪d(i，j)表示為：

定義4［16］給定一個集值決策信息系統SDS=(U，A，V，f)，對于B?C，SB是U上的集值關系，表示集值關系矩陣，參考文獻［16］中知識粒度定義方法，那么B在U上的知識粒度定義為：

定義5給定一個集值決策信息系統SDS=(U，A，V，f)，對于B?C，則決策屬性D關于條件屬性B的相對知識粒度定義為：

那么條件屬性C在U上的知識粒度為，同理可計算出相對粒度GPU(D|C)=。

定義6已知集值決策信息系統SDS=(U，A，V，f)，B?C，對于?a∈B，屬性a關于條件屬性集B相較于決策屬性集D的內部屬性重要度定義為：

定義7已知集值決策信息系統SDS=(U，A，V，f)，A=C∪D，B?C，對于?a∈C-B，屬性a關于條件屬性集B相較于決策屬性集D的外部重要度定義為：

定義8［17］給定一個集值決策信息系統SDS=(U，A，V，f)，對于B?C，B是系統的相對屬性約簡當且僅當滿足以下兩個條件：

1)GPU(D|B)=GPU(D|C)；

2)?a∈B，GPU(D|B-{a})≠GPU(D|B)。

2 基于知識粒度的啟發式屬性約簡

基于知識粒度的啟發式屬性約簡方法（Heuristic Attribute Reduction Method based on Knowledge Granularity，HARM-KG）的具體描述如方法1 所示。

3 屬性增加條件下的增量式屬性約簡

該部分介紹集值決策信息系統屬性約簡的增量式更新機制。當有新的屬性添加到系統中的屬性集時，研究新的增量關系矩陣、知識粒度和相對知識粒度發生變化的規律，由此設計相應的增量式屬性約簡方法，進而更新屬性約簡。

3.1 屬性約簡的增量式更新機制

當屬性集P添加到集值決策信息系統中時，集值關系矩陣必然會發生相應的變化，從而導致新的知識粒度也隨之細化。如果可以運用增量式更新策略來更新知識粒度，而不是從頭開始計算，這樣勢必會減少更新時間。

定義9給定一個集值決策信息系統SDS=(U，A，V，f)，集值關系矩陣。假設P是新增加的屬性集，SP是U上的集值關系，并且，那么增量關系矩陣定義為：

定理1給定一個集值決策信息系統SDS=(U，A，V，f)，A=C∪D，B?C，條件屬性集B增加條件下（B增加為B∪P），知識粒度更新為：

其中：GPU(B)是條件屬性為B時的知識粒度；是增量關系矩陣所有元素之和。

證明 由式（4）和式（8）容易證明該定理。

定理2給定一個集值決策信息系統SDS=(U，A，V，f)，GPU(D|B)是相對知識粒度，假設P是新添加的屬性集，和分別是增量關系矩陣，然后，則更新后的相對知識粒度變為：

證明 根據式（5）和式（9），有：

故定理2 得證。

3.2 屬性增加條件下的增量式屬性約簡方法

本節針對集值決策信息系統下屬性集的動態變化，構造一種增量式屬性約簡方法。可概括為以下3 個步驟：

1）根據增量式方法計算更新后的知識粒度；

2）從非核屬性集中選擇具有最高外部重要性的屬性，將其逐步添加到屬性約簡中；

3）刪除屬性約簡中的冗余屬性。

增加屬性集時基于知識粒度的增量屬性約簡方法（Incremental Attribute Reduction Method based on Knowledge Granularity when increasing attribute set，IARM-KG）的具體描述如方法2 所示。

3.3 時間復雜度分析與比較

當屬性集P添加到集值決策信息系統時，非增量式方法的時間復雜度討論如下：計算論域中的相對知識粒度的時間復雜度，即起點的時間復雜度為O((|C|+|P|)|U|+|C||U|)，所以非增量式方法的總的時間復雜度為O((|C|+|P|)2|U|+(|C|+|P|)|U|)。增量式方法的時間復雜度討論如下：計算新的相對知識粒度的時間復雜度為O((|C|+|P|)|U|+|P||U|)，當屬性集增加時，依據原有的屬性約簡結果，僅需對新增的屬性集P進行處理，因此，所提出的增量式方法的時間復雜度為O((|C|+|P|)2|U|+|P||U|)。可以看出，非增量式方法的時間復雜度通常比增量式方法高得多。換句話說，增量式方法比非增量式方法更加快速。

通過上述分析，本文所提出的增量式方法的時間復雜度為O((|C|+|P|)2|U|+|P||U|)。若采用文獻［9］中提出的信息量與屬性重要性概念來求得屬性約簡，其時間復雜度為O(|C|2|U|2+|C|3|U|2)；當有新的條件屬性集P加入到集值系統中時，方法的時間復雜度更新為O((|C|+|P|)2|U|2+|(C|+|P|)3|U|2)，計算過程復雜，需要消耗大量的時間，本文方法計算用時較短。若采用文獻［10］中提出的基于相似度的屬性約簡方法，時間復雜度為O(|U|2|C|3)；該方法需要計算集值系統中每一個屬性的相似度，當新增屬性集P添加進來時，總的時間復雜度為O(|U|2(|C|+|P|)3)，也需花費較多時間。因此，本文方法在計算時間上對比于其他方法具有一定的優勢。

4 實驗與結果分析

4.1 實驗數據集

為了驗證本文提出的增量式方法的準確性和有效性，本文從UCI 機器學習數據庫（http：//archive.ics.uci.edu/ml/index.php）中下載了3 個數據集。為了得到集值數據集，對這3 個數據集進行如下預處理：對含有缺失值的數據集，定義缺失的屬性值為其對應屬性上的所有屬性值的集合；對于完整型數據集，隨機選擇10%的屬性值進行剔除，然后分別對各缺失值取其對應屬性上的所有屬性值的集合。各數據集的具體信息如表2 所示。

表2 實驗數據集Tab.2 Experimental datasets

4.2 實驗方案

實驗均在PC 上進行操作，實驗分析所搭載的硬件環境為：Intel Core i5-8300H CPU @ 2.3 GHz；內存為8 GB；方法在Matlab R2019a 軟件平臺上編程實現。為了比較非增量式方法和增量式方法的屬性約簡時間，將每個數據集的屬性集分成6 個部分：第1 部分作為原始數據集，剩余部分作為候選集。其中將候選集的第1 部分與第2 部分組合視為第1 增量數據集，將第1 增量數據集與第3 部分組合視為第2 增量數據集，以此類推。然后分析通過增加屬性集更新基本數據集后，基于知識粒度的增量式和非增量式屬性約簡方法的運行效率。

4.3 兩種方法運行時間比較

為了驗證增量式方法的高效性，本文通過添加屬性集來使原始的屬性集發生變化，并比較了在不同數據集上非增量式方法和增量式方法的運行時間，實驗結果如圖1 所示。圖1 描述了隨著數據集中屬性數目的增加，集值決策信息系統中非增量式方法和增量式方法在計算屬性約簡所消耗時間上的變化趨勢。其中x軸表示增加屬性集的百分比，y軸表示運行時間。由圖1 可得出以下結論：

圖1 非增量式方法與增量式方法的屬性約簡時間比較Fig.1 Comparison of attribute reduction time between non-incremental method and incremental method

1）當屬性集不斷被添加到集值決策信息系統中的原始屬性集中時，增量式方法在更新屬性約簡方面始終比非增量式方法更快；

2）非增量式方法在時間消耗上的增長幅度較大，而增量式方法的增長幅度則較為平緩；

3）隨著數據集大小的增加，兩種方法在時間消耗上差異越來越明顯。

4.4 兩種方法的屬性約簡結果比較

兩種方法的屬性約簡結果如表3 所示。從表3 可看出：非增量式方法和增量式方法的屬性約簡結果非常接近，并且增量式方法可以在更短的時間內獲得一個可行的約簡。結果表明，增量式方法能高準確度地獲取屬性約簡。

表3 兩種方法的屬性約簡結果比較Tab.3 Comparison of attribute reduction results of two methods

4.5 分類精度比較

為了驗證兩種方法得出的約簡結果的準確性，在Weka機器學習軟件上，用軟件自帶的貝葉斯分類器進行測試，并通過十折交叉驗證的方式來計算非增量式方法和增量式方法所獲得的屬性約簡結果的分類精確度，結果如表4 所示。從表4 可以看出，集值決策信息系統下非增量式方法與增量式方法的分類精確度是十分接近的，在個別數據集上甚至完全相同。這說明本文提出的增量式屬性約簡方法是可行和有效的。

表4 兩種方法的分類精度比較 單位：%Tab.4 Comparison of classification accuracy of two methods unit：%

5 結語

本文使用知識粒度來度量集值決策信息系統中的屬性重要度，并在此基礎上構建了屬性集增加條件下的基于知識粒度的增量式屬性約簡方法。為了證實所構建的增量式約簡方法的有效性和約簡結果的準確性，借助于Matlab 編程平臺上對UCI 上選取的3 組數據集進行了實驗驗證。從實驗結果可得出，當集值決策信息系統中的屬性集增加時，本文方法能夠高效率地更新屬性約簡。但是本文只考慮了集值決策信息系統中屬性集發生變化的情況，未來研究工作的重點是當有多個對象添加或刪除的情況下，設計基于知識粒度的增量式屬性約簡方法。