焦玉清 張 勇

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

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

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

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

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

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

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

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

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

（二）增量式屬性約簡(jiǎn)算法。

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

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

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

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

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

表1所示的是實(shí)驗(yàn)中進(jìn)行屬性約簡(jiǎn)的數(shù)據(jù)集，這里的數(shù)據(jù)集1～3來(lái)源于UCI數(shù)據(jù)集庫(kù)，數(shù)據(jù)集4～5為人工隨機(jī)生成的區(qū)間值數(shù)據(jù)集，其中每個(gè)數(shù)據(jù)集均為靜態(tài)的，為了模擬數(shù)據(jù)集對(duì)象動(dòng)態(tài)增加的環(huán)境，本實(shí)驗(yàn)采用文獻(xiàn)[3,9-10]的處理方法，將原始數(shù)據(jù)集根據(jù)對(duì)象平均分割成多個(gè)子數(shù)據(jù)集，然后將這些子數(shù)據(jù)集進(jìn)行逐步合并，其中合并的過(guò)程便構(gòu)造出數(shù)據(jù)集對(duì)象的動(dòng)態(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)θ信息熵的非增量式屬性約簡(jiǎn)和增量式屬性約簡(jiǎn)的用時(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ù)的增加，非增量式屬性約簡(jiǎn)算法的處理時(shí)間大幅度高于本文提出的增量式屬性約簡(jiǎn)算法，并且非增量式屬性約簡(jiǎn)算法的時(shí)間增長(zhǎng)速率也是高于本文的算法，本文算法的約簡(jiǎn)用時(shí)增長(zhǎng)得較為緩慢。產(chǎn)生這一差距的主要原因是由于它們的算法機(jī)制不同導(dǎo)致的，對(duì)于區(qū)間值數(shù)據(jù)集的每次增量式更新，非增量式屬性約簡(jiǎn)算法基于新的完整數(shù)據(jù)集進(jìn)行屬性約簡(jiǎn)計(jì)算，而增量式屬性約簡(jiǎn)算法是在原始信息系統(tǒng)約簡(jiǎn)結(jié)果的基礎(chǔ)上進(jìn)行進(jìn)一步的計(jì)算，這樣避免了對(duì)舊信息系統(tǒng)的重復(fù)計(jì)算，提高了約簡(jiǎn)的效率，因此隨著數(shù)據(jù)集的逐漸增大，增量式屬性約簡(jiǎn)算法的約簡(jiǎn)用時(shí)增長(zhǎng)的較為緩慢，效率更加的高。

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

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

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

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

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

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

四、結(jié)語(yǔ)

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