基于區間值信息系統的信息熵增量式屬性約簡算法

焦玉清 張 勇

（巢湖學院信息工程學院 安徽合肥 238000）

屬性約簡是粗糙集理論和粒計算理論的重要研究問題[1-2]，其目的是為了消除數據集內部的冗余屬性，提高數據集的知識發現性能。然而實際應用中的數據集總是處于不斷動態更新之中，針對這類數據環境，一種被稱為增量式屬性約簡的方法被提出[3-5]，從而提高了動態數據的屬性約簡性能。

針對增量式屬性約簡，學者在各種類型的信息系統進行了相關的研究。Shu等[6]在傳統的完備型信息系統中提出了對象增加時的增量式屬性約簡算法；在不完備信息系統方面，丁棉衛等[7]利于矩陣的方法設計出了相應的增量式屬性約簡算法，Xie等[8]在其基礎上提出了一種改進的不完備信息系統增量式屬性約簡算法；在數值型的鄰域信息系統中，趙小龍等[9]研究了鄰域條件熵的增量式更新，并進一步地提出了一種鄰域條件熵的增量式屬性約簡算法；在數值型和離散型混合類型的信息系統中，段海玲等[10]通過構造鄰域知識粒度的增量式更新設計出相應的增量式屬性約簡，同時在不完備混合型信息系統，王映龍等[11]利用變精度粗糙集模型設計出一種增量式屬性約簡算法。此外，在多粒度的數據環境下，Hu等[12]研究了一種多粒度視角的增量式更新方法；在集值信息系統中，Lang等[13]提出一種高效的增量式屬性約簡算法。總之各類信息系統的增量式屬性約簡研究已是目前屬性約簡領域的研究熱點。

區間值信息系統是一種以區間值為屬性值的信息系統，多見于醫學診斷應用中，然而對于這種類型的信息系統，目前很少有相關的增量式屬性約簡研究。在文獻[14]中，Xie等在區間值信息系統下提出了一種θ信息熵的不確定性度量方法，并利用θ信息熵提出了相應的屬性約簡算法。本文將在該算法的基礎上，進一步提出一種論域動態增加的θ信息熵增量式屬性約簡算法。文章中采用由簡單到復雜的研究思路，首先研究區間值信息系統論域增加單個對象時θ信息熵的增量式更新，然后在其基礎上，進一步研究增加多個對象時θ信息熵的增量式更新。根據θ信息熵的增量式更新方法，本文提出了相應的增量式屬性約簡算法，實驗證明了所提出算法的有效性和優越性。

一、區間值信息系統的信息熵模型

二、區間值信息系統信息熵的增量式屬性約簡算法

由于實際環境下的信息系統是不斷動態更新的，因此傳統的屬性約簡算法不再有效。近年來，學者們進一步提出了增量式屬性約簡，使得大幅度提升了動態環境下屬性約簡的性能[3-5]。本文將針對區間值信息系統對象增加的環境，提出一種信息熵的增量式屬性約簡算法。

（一）區間值信息系統的信息熵增量式更新。

定理2表明，當區間值信息系統論域增加多個對象時，可以依次對每個增加的對象在對應的論域下計算相應的相似類，然后按照定理2所示的增量式更新公式得到最終新的θ信息熵，大幅度減少了重復的計算量。

（二）增量式屬性約簡算法。

以上推證得到了區間值信息系統信息熵隨對象增加時的增量式變化關系，利用這種關系可以進一步得到區間值信息系統的信息熵增量式屬性約簡算法。

定義6表明，屬性約簡集與條件屬性全集具有相同的θ信息熵結果，并且刪除屬性約簡集中任意一個屬性都不滿足此條件。當區間值信息系統增加對象后，對應的θ信息熵會發生變化，我們需要進一步探究θ信息熵的大小是具體如何變化的，這樣為增量式屬性約簡算法的構造提供一定的理論基礎。

算法1所示的增量式屬性約簡算法，不同于文獻[14]的非增量式算法，算法2在原先舊區間值信息系統的信息熵和約簡集的基礎上進行進一步屬性約簡搜索，首先根據舊信息熵計算新的信息熵，然后比較新舊信息熵的大小來進行相應的搜索屬性策略，最后得到新信息系統的屬性約簡結果。文獻[14]中所示的非增量式屬性約簡算法的時間復雜度為O(|C|2?|U?ΔU|2),本文算法2的時間復雜度可表示為O(|C-red|?|red|?|U|?|ΔU|).

三、實驗分析

本節將通過實驗來驗證所提出的區間值信息系統增量式屬性約簡算法的有效性。整個實驗環節主要分為三個部分，第一部分是將本文的增量式屬性約簡算法與文獻[14]所提出的非增量式算法針對動態區間值數據集進行屬性約簡，比較它們的屬性約簡效率。第二部分將本文所提出的增量式屬性約簡算法與文獻[15]提出的區間值信息系統增量式屬性約簡算法進行動態數據集屬性約簡效率的比較，驗證本文算法的優越性。第三部分是研究不同閾值參數θ對本文增量式屬性約簡算法的效率影響。

表1所示的是實驗中進行屬性約簡的數據集，這里的數據集1～3來源于UCI數據集庫，數據集4～5為人工隨機生成的區間值數據集，其中每個數據集均為靜態的，為了模擬數據集對象動態增加的環境，本實驗采用文獻[3,9-10]的處理方法，將原始數據集根據對象平均分割成多個子數據集，然后將這些子數據集進行逐步合并，其中合并的過程便構造出數據集對象的動態增加，本實驗將數據集平均分割成10個部分，這樣可以構造數據集的9次更新。本實驗運行的硬件環境為英特爾酷睿i57500CPU(主頻3.4GHz)，內存為DDR4 8GB，算法采用Matlab2016進行編程實現。

表1 實驗數據集

圖1所示的是區間值信息系統θ信息熵的非增量式屬性約簡和增量式屬性約簡的用時比較結果,其中θ取值為0.7進行實驗，并且實驗結果采用的是多次重復實驗的平均值。觀察圖1中各個數據集的實驗結果，可以發現隨著數據集增量次數的增加，非增量式屬性約簡算法的處理時間大幅度高于本文提出的增量式屬性約簡算法，并且非增量式屬性約簡算法的時間增長速率也是高于本文的算法，本文算法的約簡用時增長得較為緩慢。產生這一差距的主要原因是由于它們的算法機制不同導致的，對于區間值數據集的每次增量式更新，非增量式屬性約簡算法基于新的完整數據集進行屬性約簡計算，而增量式屬性約簡算法是在原始信息系統約簡結果的基礎上進行進一步的計算，這樣避免了對舊信息系統的重復計算，提高了約簡的效率，因此隨著數據集的逐漸增大，增量式屬性約簡算法的約簡用時增長的較為緩慢，效率更加的高。

圖1 增量式算法與非增量式算法的動態屬性約簡時間比較

圖2所示的是本文提出的區間值信息系統增量式屬性約簡算法與文獻[15]提出的增量式屬性約簡算法(記為對比增量式算法)在各個數據集的區間值信息系統下進行動態屬性約簡的時間比較結果，其中每個子圖對應了每個數據集的結果。觀察每個子圖可以發現，本文提出的增量式屬性約簡算法的更新約簡用時低于對比增量式屬性約簡算法，并且隨著增量更新次數的增加，這種時間的差距愈加明顯。產生這一現象的主要原因是由于這兩種算法屬性約簡的度量方法不一樣導致的，本文提出的增量式算法以區間值信息系統的信息熵為基礎，每次僅需要計算對象的相似類，然后按照信息熵的計算公式便可完成信息熵結果的更新計算，而對比增量式算法是一種基于正區域的方法計算約簡，首先需要計算對象的相似類，然后利用相似類進行決策類下近似集的計算，這額外增加了一定的計算量，因此進行增量式計算時產生更高的時間消耗，因此更新屬性約簡的效率略低于本文算法。

圖2 本文算法與對比增量式算法的效率比較

圖1和圖2的實驗結果表明了所提出的增量式屬性約簡算法有效性和優越性，接下來將進一步分析區間值信息系統中閾值θ對本文增量式屬性約簡算法效率的影響。

圖3所示的是選取不同閾值θ進行各個數據集增量式屬性約簡的用時比較結果，其中閾值θ在區間[0.5,0.9]中以0.1為間隔分別進行取值。觀察圖3可以發現，無論θ取為何值，隨著數據集增量次數的增加，其屬性約簡的用時都是逐漸增大的，同時，對于閾值θ的逐漸減小，其同一次增量式屬性約簡的約簡用時是逐漸增大的。這主要是由于隨著閾值θ的減小，區間值信息系統中每個對象的相似類都是增大的，而本文算法在進行增量式計算中，需要計算新增對象的相似類，因而其計算時間會增加，所以表現出了圖3所示的結果。

圖3 不同閾值θ時增量式屬性約簡用時比較

四、結語

區間值信息系統是一種較為常見的信息系統類型，基于區間值信息系統的屬性約簡是目前粗糙集領域的研究熱點之一。然而由于實際環境下數據集的動態性，使得傳統的屬性約簡算法不具有較高的約簡性能。本文針對區間值信息系統論域中對象逐漸動態增加的情形，提出一種信息熵的增量式屬性約簡算法。文中首先研究了信息系統論域增加單個對象時，區間值信息系統信息熵的增量式更新，然后以單個對象變化為基礎，通過迭代的方式給出了信息系統增加多個對象時的信息熵增量式更新問題，最后設計出對應的增量式屬性約簡算法，實驗分析證明所提出增量式屬性約簡算法的有效性。本文所研究的是區間值信息系統對象增加環境下的增量式屬性約簡問題，因此接下來可以進一步探索區間值信息系統屬性增加時的增量式屬性約簡，從而可以進一步推動區間值信息系統屬性約簡的實用化進程。