焦玉清 張 勇

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

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

針對增量式屬性約簡，學者在各種類型的信息系統(tǒng)進行了相關(guān)的研究。Shu等[6]在傳統(tǒng)的完備型信息系統(tǒng)中提出了對象增加時的增量式屬性約簡算法；在不完備信息系統(tǒng)方面，丁棉衛(wèi)等[7]利于矩陣的方法設(shè)計出了相應(yīng)的增量式屬性約簡算法，Xie等[8]在其基礎(chǔ)上提出了一種改進的不完備信息系統(tǒng)增量式屬性約簡算法；在數(shù)值型的鄰域信息系統(tǒng)中，趙小龍等[9]研究了鄰域條件熵的增量式更新，并進一步地提出了一種鄰域條件熵的增量式屬性約簡算法；在數(shù)值型和離散型混合類型的信息系統(tǒng)中，段海玲等[10]通過構(gòu)造鄰域知識粒度的增量式更新設(shè)計出相應(yīng)的增量式屬性約簡，同時在不完備混合型信息系統(tǒng)，王映龍等[11]利用變精度粗糙集模型設(shè)計出一種增量式屬性約簡算法。此外，在多粒度的數(shù)據(jù)環(huán)境下，Hu等[12]研究了一種多粒度視角的增量式更新方法；在集值信息系統(tǒng)中，Lang等[13]提出一種高效的增量式屬性約簡算法?？傊黝愋畔⑾到y(tǒng)的增量式屬性約簡研究已是目前屬性約簡領(lǐng)域的研究熱點。

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

一、區(qū)間值信息系統(tǒng)的信息熵模型

二、區(qū)間值信息系統(tǒng)信息熵的增量式屬性約簡算法

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

（一）區(qū)間值信息系統(tǒng)的信息熵增量式更新。

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

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

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

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

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

三、實驗分析

本節(jié)將通過實驗來驗證所提出的區(qū)間值信息系統(tǒng)增量式屬性約簡算法的有效性。整個實驗環(huán)節(jié)主要分為三個部分，第一部分是將本文的增量式屬性約簡算法與文獻[14]所提出的非增量式算法針對動態(tài)區(qū)間值數(shù)據(jù)集進行屬性約簡，比較它們的屬性約簡效率。第二部分將本文所提出的增量式屬性約簡算法與文獻[15]提出的區(qū)間值信息系統(tǒng)增量式屬性約簡算法進行動態(tài)數(shù)據(jù)集屬性約簡效率的比較，驗證本文算法的優(yōu)越性。第三部分是研究不同閾值參數(shù)θ對本文增量式屬性約簡算法的效率影響。

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

表1 實驗數(shù)據(jù)集

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

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

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

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

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

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

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

四、結(jié)語

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