基于對象變化的鄰域決策粗糙集動態更新算法

孫海霞

（安徽三聯學院 計算機工程學院，安徽 合肥 230601）

粗糙集理論是當今知識發現領域的一個研究熱點，決策粗糙集模型[1-2]是粗糙集理論的重要研究分支，由于決策粗糙集在處理噪聲數據方面具有較好的泛化性能[2]，因此目前已廣泛應用于機器學習[3-4]、圖像處理[5]和數據挖掘[6]等諸多領域。

早期的決策粗糙集建立在完備離散型的信息系統上，在其基礎上，學者們進一步地提出了多種擴展的粗糙集模型，例如Liu 等[7]將決策粗糙集推廣至不完備信息系統，提出一種改進的不完備決策粗糙集模型；Sun 等[8]在粗糙模糊集下提出了相應的決策粗糙集模型；Dou 等[9]基于多個代價的策略，提出了多代價的決策粗糙集模型；在數值型的數據集方面，Li 等[10]將鄰域關系融入決策粗糙集模型中，提出了鄰域決策粗糙集模型，該模型進一步提升了決策粗糙集的適用范圍。

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

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

1 鄰域決策粗糙集模型

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

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

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

由于現實環境下數據集的動態性，傳統的模型和算法不再有效，針對該問題，本節將提出一種論域變化時鄰域決策粗糙集模型的增量式更新方法。

定義3 已經表明，當信息系統的決策代價已經確定時，則鄰域決策粗糙集中的閾值 α和 β 也就確定，因此對于鄰域決策粗糙集的研究只需考慮概率P(X|δ(x)) 與閾值 α和 β 的關系即可。

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

2.1 論域中對象增加時模型的增量式更新

在鄰域決策粗糙集中，研究增量式更新的關鍵是上下近似區域的更新問題，由于閾值 α和β已經確定，因此主要涉及到對象與對象集之間的概率計算，首先探討論域對象增加時概率的增量式更新。

2.2 論域中對象減少時模型的增量式更新

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

定理5 和定理6 分別給出當鄰域型信息系統移除一個對象時上下近似集的增量式更新問題，當信息系統同時移除多個對象時，可以根據定理5 和定理6 逐步進行迭代，直至完成最終的更新。

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

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

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

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

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

4 實驗分析

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

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

表1 實驗數據集Table 1 Experimental data set

圖1 為各個數據集論域增加時增量式更新算法(算法1)與非增量式更新算法計算鄰域決策粗糙集的時間比較結果，非增量式更新算法采用文獻[10]提出的算法。

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

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

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

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

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

綜合圖1 和圖2 的實驗結果，可以看出本文所提出的增量式更新算法的更新效率均大幅度高于傳統的非增量式算法，并且所提出的算法隨數據集論域變化的影響較小，這說明了本文所提出的增量式更新算法具有很高的優越性。

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

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

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

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

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

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

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

5 結束語

鄰域決策粗糙集是傳統決策粗糙集的重要拓展，針對現實環境下數據集的動態性，本文提出一種論域動態變化時的鄰域決策粗糙集增量式更新算法。本文首先研究了論域中單個對象變化時，模型的增量式更新問題，然后以單個對象變化為基礎，通過迭代方式完成對象批量變化時的增量式更新問題，實驗分析表明，所提出的增量式算法在更新動態數據時，其效率大幅度高于非增量式算法，且增量式算法的更新時間受論域對象變化的影響較小，因此說明了所提出的增量式更新算法具有很高的優越性，從而也進一步推動了決策粗糙集在實際環境下的應用。在本文研究成果的基礎上，接下來可以進一步在鄰域決策粗糙集的增量式屬性約簡問題上進行探索。