基于對(duì)象變化的鄰域決策粗糙集動(dòng)態(tài)更新算法

孫海霞

（安徽三聯(lián)學(xué)院 計(jì)算機(jī)工程學(xué)院，安徽 合肥 230601）

粗糙集理論是當(dāng)今知識(shí)發(fā)現(xiàn)領(lǐng)域的一個(gè)研究熱點(diǎn)，決策粗糙集模型[1-2]是粗糙集理論的重要研究分支，由于決策粗糙集在處理噪聲數(shù)據(jù)方面具有較好的泛化性能[2]，因此目前已廣泛應(yīng)用于機(jī)器學(xué)習(xí)[3-4]、圖像處理[5]和數(shù)據(jù)挖掘[6]等諸多領(lǐng)域。

早期的決策粗糙集建立在完備離散型的信息系統(tǒng)上，在其基礎(chǔ)上，學(xué)者們進(jìn)一步地提出了多種擴(kuò)展的粗糙集模型，例如Liu 等[7]將決策粗糙集推廣至不完備信息系統(tǒng)，提出一種改進(jìn)的不完備決策粗糙集模型；Sun 等[8]在粗糙模糊集下提出了相應(yīng)的決策粗糙集模型；Dou 等[9]基于多個(gè)代價(jià)的策略，提出了多代價(jià)的決策粗糙集模型；在數(shù)值型的數(shù)據(jù)集方面，Li 等[10]將鄰域關(guān)系融入決策粗糙集模型中，提出了鄰域決策粗糙集模型，該模型進(jìn)一步提升了決策粗糙集的適用范圍。

然而現(xiàn)實(shí)環(huán)境下的數(shù)據(jù)不總是靜止不變的，而是時(shí)刻處于動(dòng)態(tài)更新之中，為了提高粗糙集模型在動(dòng)態(tài)數(shù)據(jù)下的處理效率，學(xué)者們對(duì)其提出了多種增量式的模型和算法[11-13]。在決策粗糙集等模型中，學(xué)者們同樣提出了多種增量式更新算法。例如，Zhang 等[14]針對(duì)屬性值動(dòng)態(tài)變化情形提出了相應(yīng)的增量式更新算法；針對(duì)流計(jì)算環(huán)境，Xu 等[15]提出了對(duì)象在線增加和減少時(shí)的增量式更新算法；Chen 等[16]利用集合更新的方法設(shè)計(jì)出了決策粗糙集的增量式更新算法；趙小龍等[17]針對(duì)數(shù)值型信息系統(tǒng)，研究了鄰域?；瘲l件熵隨對(duì)象增加和減少時(shí)的增量式更新，并進(jìn)一步地提出了對(duì)應(yīng)的增量式屬性約簡(jiǎn)算法；楊臻等[18]研究了混合型信息系統(tǒng)下對(duì)象變化時(shí)概率的增量式更新，并進(jìn)一步地提出了變精度粗糙集模型的增量式更新；Luo 等[19]通過矩陣方法構(gòu)造出了決策粗糙集的增量式更新算法。然而所提出的這些增量式更新算法僅局限于離散數(shù)據(jù)環(huán)境下的決策粗糙集模型，針對(duì)鄰域型的決策粗糙集還未有相關(guān)研究。

論域中對(duì)象的增加和減少是信息系統(tǒng)最為常見的一種變化形式，本文將針對(duì)這類問題進(jìn)行鄰域決策粗糙集的增量式更新研究。鄰域決策粗糙集通過鄰域關(guān)系來對(duì)數(shù)值型數(shù)據(jù)進(jìn)行信息?；痆10]，而對(duì)其進(jìn)行增量式計(jì)算時(shí)必然涉及鄰域類的更新計(jì)算，鄰域關(guān)系不同于傳統(tǒng)的等價(jià)關(guān)系和容差關(guān)系，其增量式計(jì)算的復(fù)雜程度要更高。在文獻(xiàn)[18]中，楊臻等通過單個(gè)對(duì)象逐步迭代的方式去處理混合型信息系統(tǒng)變精度粗糙集模型的增量式更新，使得問題的處理方式簡(jiǎn)便高效。由于決策粗糙集與變精度粗糙集有一定的相似性，因此本文將借鑒文獻(xiàn)[18]中關(guān)于變精度粗糙集模型的增量式更新研究思路與方法，構(gòu)造出鄰域決策粗糙集的增量式更新模型。文中首先分別研究論域中增加和減少一個(gè)對(duì)象時(shí)，近似集與鄰域類之間概率的變化規(guī)律，然后根據(jù)這種規(guī)律來構(gòu)造單個(gè)對(duì)象變化時(shí)模型上下近似集的增量式更新，最后在單個(gè)對(duì)象變化的基礎(chǔ)上，通過逐步迭代的方式設(shè)計(jì)了對(duì)象批量變化時(shí)的增量式更新算法。實(shí)驗(yàn)分析表明，所提出的算法具有較高的增量式更新性能，適用于動(dòng)態(tài)數(shù)據(jù)環(huán)境下鄰域決策粗糙集模型的動(dòng)態(tài)更新。

1 鄰域決策粗糙集模型

粗糙集理論中，數(shù)據(jù)集表示為信息系統(tǒng)IS=(U,AT)的形式，其中U為信息系統(tǒng)的對(duì)象集，稱為論域。AT 稱為信息系統(tǒng)的屬性集，若屬性集AT可分為條件屬性集C和決策屬性集D，即AT=C∪D，那么該信息系統(tǒng)又稱為決策信息系統(tǒng)。對(duì)于 ?x∈U和 ?a∈AT，a(x) 表示對(duì)象x在屬性a下的屬性值。當(dāng)條件屬性集C中的每個(gè)屬性都為數(shù)值型屬性時(shí)，此信息系統(tǒng)又稱之為鄰域型信息系統(tǒng)。

Yao 等[1-2]提出的決策粗糙集僅應(yīng)用于離散型的信息系統(tǒng)，Li 等將鄰域關(guān)系引入傳統(tǒng)的決策粗糙集模型中，提出了鄰域決策粗糙集[10]。

2 鄰域決策粗糙集模型的增量式更新

由于現(xiàn)實(shí)環(huán)境下數(shù)據(jù)集的動(dòng)態(tài)性，傳統(tǒng)的模型和算法不再有效，針對(duì)該問題，本節(jié)將提出一種論域變化時(shí)鄰域決策粗糙集模型的增量式更新方法。

定義3 已經(jīng)表明，當(dāng)信息系統(tǒng)的決策代價(jià)已經(jīng)確定時(shí)，則鄰域決策粗糙集中的閾值 α和 β 也就確定，因此對(duì)于鄰域決策粗糙集的研究只需考慮概率P(X|δ(x)) 與閾值 α和 β 的關(guān)系即可。

數(shù)據(jù)集論域中對(duì)象的增加和減少往往都是批量的，而這些批量的變化可以分解成對(duì)象的一個(gè)一個(gè)依次變化，每次只考慮數(shù)據(jù)集中一個(gè)對(duì)象增加或減少時(shí)的增量式更新問題，然后逐步對(duì)多個(gè)對(duì)象進(jìn)行迭代，這樣可以簡(jiǎn)化問題的處理[12,17-18]。根據(jù)這一思想，構(gòu)造了本文模型的增量式更新方法。

2.1 論域中對(duì)象增加時(shí)模型的增量式更新

在鄰域決策粗糙集中，研究增量式更新的關(guān)鍵是上下近似區(qū)域的更新問題，由于閾值 α和β已經(jīng)確定，因此主要涉及到對(duì)象與對(duì)象集之間的概率計(jì)算，首先探討論域?qū)ο笤黾訒r(shí)概率的增量式更新。

2.2 論域中對(duì)象減少時(shí)模型的增量式更新

中的對(duì)象計(jì)算概率便可完成最終的更新，因此上近似集的增量式更新同樣具有很高的計(jì)算效率。

定理5 和定理6 分別給出當(dāng)鄰域型信息系統(tǒng)移除一個(gè)對(duì)象時(shí)上下近似集的增量式更新問題，當(dāng)信息系統(tǒng)同時(shí)移除多個(gè)對(duì)象時(shí)，可以根據(jù)定理5 和定理6 逐步進(jìn)行迭代，直至完成最終的更新。

3 鄰域決策粗糙集更新算法

根據(jù)本文所提出的增量式更新方法，接下來將進(jìn)一步提出對(duì)應(yīng)的鄰域決策粗糙集增量式更新算法，具體如算法1 和算法2 所示。

算法1論域增加時(shí)鄰域決策粗糙集的增量式更新算法

算法2論域減少時(shí)鄰域決策粗糙集的增量式更新算法

在算法1 所示的增量式計(jì)算過程中，每次在更新前信息系統(tǒng)的上下近似基礎(chǔ)上進(jìn)一步計(jì)算新的上下近似集，并且定理2 和定理3 已經(jīng)表明，只需要計(jì)算新增對(duì)象的鄰域類，便可以完成最終的更新，而不必去計(jì)算其他對(duì)象的鄰域類，這樣大大減少了重復(fù)的計(jì)算量，提高了更新的效率，因此整個(gè)算法1 和算法2 的時(shí)間復(fù)雜度可表示為O(|A|·|U|·|?U|)。

4 實(shí)驗(yàn)分析

為了驗(yàn)證所提出增量式更新算法的有效性，將通過實(shí)驗(yàn)比較的方式進(jìn)行驗(yàn)證。本實(shí)驗(yàn)主要將文中所提出的增量式更新算法與傳統(tǒng)的非增量更新算法對(duì)同一組數(shù)據(jù)集進(jìn)行動(dòng)態(tài)更新計(jì)算，通過比較他們的動(dòng)態(tài)更新效率來驗(yàn)證算法的有效性，其中表1 所示的是實(shí)驗(yàn)中所使用的數(shù)據(jù)集，這些數(shù)據(jù)集均來源于UCI 數(shù)據(jù)集庫(kù)，其中數(shù)據(jù)集的各個(gè)屬性均為數(shù)值類型。整個(gè)實(shí)驗(yàn)所運(yùn)行的硬件環(huán)境為Intel Core G4560 3.5 GHz 處理器和DDR4 8 GB 內(nèi)存。

表1 所示的均為靜態(tài)的數(shù)據(jù)集，為了模擬數(shù)據(jù)集動(dòng)態(tài)變化的情形，本實(shí)驗(yàn)采用其他學(xué)者常用的處理方法[11-12,17-18]，即讓數(shù)據(jù)集按照論域平均分成多個(gè)對(duì)象集，然后通過將這些對(duì)象集逐漸進(jìn)行合并，達(dá)到了數(shù)據(jù)集論域動(dòng)態(tài)增加的效果，將原始論域逐漸對(duì)這些對(duì)象集進(jìn)行移除，便達(dá)到了數(shù)據(jù)集論域動(dòng)態(tài)的減少。本實(shí)驗(yàn)將論域平均分成9 個(gè)部分，這樣可以構(gòu)造出數(shù)據(jù)集的8 次動(dòng)態(tài)更新。實(shí)驗(yàn)中將數(shù)據(jù)集的決策類作為鄰域決策粗糙集的近似對(duì)象集，即計(jì)算數(shù)據(jù)集每個(gè)決策類的上下近似增量式更新。實(shí)驗(yàn)中每個(gè)數(shù)據(jù)集的屬性值均進(jìn)行歸一化處理，并且統(tǒng)一設(shè)定鄰域半徑δ=0.15，閾值 α=0.75，β=0.55。

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

圖1 為各個(gè)數(shù)據(jù)集論域增加時(shí)增量式更新算法(算法1)與非增量式更新算法計(jì)算鄰域決策粗糙集的時(shí)間比較結(jié)果，非增量式更新算法采用文獻(xiàn)[10]提出的算法。

在圖1 所示的實(shí)驗(yàn)結(jié)果中，增量式算法的更新用時(shí)大幅度低于非增量式算法，并且隨著數(shù)據(jù)集更新次數(shù)的增多，兩類算法的差距不斷增大。這主要是由于非增量式更新算法在進(jìn)行模型的更新時(shí)，每次均基于完整的論域進(jìn)行計(jì)算，產(chǎn)生的時(shí)間會(huì)越來越多。對(duì)于增量式更新算法，隨著數(shù)據(jù)集論域的增大，更新所需的時(shí)間較少且增長(zhǎng)的速率較為緩慢，這主要是由于增量式更新算法采用增量式的方法進(jìn)行更新計(jì)算，每次均在前一次更新的結(jié)果上進(jìn)行進(jìn)一步更新，這樣避免了原有對(duì)象的重復(fù)計(jì)算，大幅度提高更新效率，因此增量式算法更加高效。

圖1 論域增加時(shí)兩類算法的更新用時(shí)比較Fig.1 Comparison of update time of two algorithms when universe is added

圖2 展示的是各個(gè)數(shù)據(jù)集論域減少時(shí)，增量式更新算法(算法2) 與非增量式更新算法計(jì)算鄰域決策粗糙集的時(shí)間比較結(jié)果，非增量式更新算法同樣采用文獻(xiàn)[10]提出的算法。

在圖2 所示的實(shí)驗(yàn)結(jié)果中，可以發(fā)現(xiàn)增量式更新算法的更新用時(shí)同樣大幅度低于非增量式更新算法，對(duì)于非增量式更新算法，隨著數(shù)據(jù)集論域的逐漸減少，其更新模型的用時(shí)也是逐漸減小，這主要是由于非增量式更新算法在進(jìn)行更新時(shí)，對(duì)完整論域進(jìn)行計(jì)算，因此隨著論域的減少，非增量式算法的計(jì)算量也大幅度減小，產(chǎn)生的時(shí)間會(huì)越來越少，但是整體還是高于增量式算法。對(duì)于增量式更新算法，隨著數(shù)據(jù)集論域的減小，其整體更新用時(shí)始終處于一個(gè)較低的水平，并且隨著更新次數(shù)增加，更新用時(shí)也是逐漸減小的。這主要是由于增量式更新算法采用增量式的方法進(jìn)行更新計(jì)算，在前一次更新結(jié)果的基礎(chǔ)上計(jì)算后一次結(jié)果，由于論域逐漸減少，則更新時(shí)間會(huì)更加的少，從而效率遠(yuǎn)高于非增量式算法。

圖2 論域減少時(shí)兩類算法的更新用時(shí)比較Fig.2 Comparison of update time of two algorithms when universe is reduced

綜合圖1 和圖2 的實(shí)驗(yàn)結(jié)果，可以看出本文所提出的增量式更新算法的更新效率均大幅度高于傳統(tǒng)的非增量式算法，并且所提出的算法隨數(shù)據(jù)集論域變化的影響較小，這說明了本文所提出的增量式更新算法具有很高的優(yōu)越性。

另一方面，在本文所提出的鄰域決策粗糙集增量式更新算法中，有3 個(gè)重要的參數(shù)，分別為鄰域半徑 δ，和一對(duì)閾值 (α,β)。由于閾值 (α,β) 可以通過不同的評(píng)價(jià)方式進(jìn)行確定，因此閾值 (α,β) 可認(rèn)定為是固定的值，那么接下來將直接探究鄰域半徑 δ 對(duì)所提算法更新效率的影響。

圖3～6 所示的是部分?jǐn)?shù)據(jù)集在不用鄰域半徑 δ下增量式更新用時(shí)比較結(jié)果，其中包含了論域增加和論域減少的兩種情形，這里設(shè)定鄰域半徑 δ 在[0.1,0.28]內(nèi)以0.02 為間隔分別進(jìn)行取值。

通過圖3～6 的結(jié)果可以看出，隨著鄰域半徑的逐漸增大，增量式更新算法的更新用時(shí)是逐漸增大的，這主要是由于本文所提出的增量更新算法，計(jì)算新論域下的模型時(shí)，需要計(jì)算變化對(duì)象的鄰域類，并基于這些鄰域類進(jìn)行更新計(jì)算，而鄰域半徑的增大無疑會(huì)增加鄰域類中對(duì)象的數(shù)量，因此計(jì)算量會(huì)增加，從而展現(xiàn)出了圖3～6的結(jié)果，但是對(duì)比圖1 和圖2，這種增量式算法的用時(shí)仍然大幅度小于非增量式算法。

圖3 數(shù)據(jù)集pima 在不同鄰域半徑下算法更新用時(shí)比較Fig.3 Comparison of algorithm updating time of pima data set under different neighborhood radius

圖4 數(shù)據(jù)集wdbc 在不同鄰域半徑下算法更新用時(shí)比較Fig.4 Comparison of algorithm updating time of wdbc data set under different neighborhood radius

圖5 數(shù)據(jù)集biodeg 在不同鄰域半徑下算法更新用時(shí)比較Fig.5 Comparison of algorithm updating time of biodeg data set under different neighborhood radius

圖6 數(shù)據(jù)集musk 在不同鄰域半徑下算法更新用時(shí)比較Fig.6 Comparison of algorithm updating time of musk data set under different neighborhood radius

5 結(jié)束語(yǔ)

鄰域決策粗糙集是傳統(tǒng)決策粗糙集的重要拓展，針對(duì)現(xiàn)實(shí)環(huán)境下數(shù)據(jù)集的動(dòng)態(tài)性，本文提出一種論域動(dòng)態(tài)變化時(shí)的鄰域決策粗糙集增量式更新算法。本文首先研究了論域中單個(gè)對(duì)象變化時(shí)，模型的增量式更新問題，然后以單個(gè)對(duì)象變化為基礎(chǔ)，通過迭代方式完成對(duì)象批量變化時(shí)的增量式更新問題，實(shí)驗(yàn)分析表明，所提出的增量式算法在更新動(dòng)態(tài)數(shù)據(jù)時(shí)，其效率大幅度高于非增量式算法，且增量式算法的更新時(shí)間受論域?qū)ο笞兓挠绊戄^小，因此說明了所提出的增量式更新算法具有很高的優(yōu)越性，從而也進(jìn)一步推動(dòng)了決策粗糙集在實(shí)際環(huán)境下的應(yīng)用。在本文研究成果的基礎(chǔ)上，接下來可以進(jìn)一步在鄰域決策粗糙集的增量式屬性約簡(jiǎn)問題上進(jìn)行探索。