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

焦玉清 張 勇

（巢湖學(xué)院信息工程學(xué)院 安徽合肥 238000）

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

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

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

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

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

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

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

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

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

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

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

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

三、實(shí)驗(yàn)分析

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

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

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

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

四、結(jié)語

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