維度變化的不完備混合型數據增量式屬性約簡

劉桂枝

山西大同大學 物理與電子科學學院，山西 大同037009

屬性約簡[1-2]又稱為維度約簡或特征選擇，是粗糙集理論的重要應用，其目的是為了刪除數據集中對分類不相關的屬性，提高數據的知識發現性能，目前屬性約簡已廣泛用于模式識別和數據挖掘等領域。由于實際工程應用環境下，數據集是不斷動態變化的，傳統的屬性約簡方法面臨著一定的局限性，為了改善這一問題，學者們進一步地提出了增量式的屬性約簡方法，極大地提升了屬性約簡的適用范圍[3-5]。

增量式屬性約簡是屬性約簡領域的熱點研究內容。信息系統的屬性變化又稱為維度變化，是信息系統的一種常見的變化形式，例如在醫療診斷系統中，病人的各項生理指標被采集獲取，那么信息系統的屬性便發生了增加。對于這類變化形式，學者們提出了多種的增量式屬性約簡算法，例如對于傳統的離散型信息系統，Qian等[6]學者利用正區域加速增量運算的方法，提出了一種高效快速的屬性約簡算法；Wang等[7]學者基于信息系統的維度變化，提出信息熵的增量式屬性約簡算法；Qian等[8]學者利用決策正區域的方法提出了屬性變化的增量式屬性約簡算法；Jing等[9]學者利用知識粒度作為屬性約簡的方法，并構造了知識粒度隨屬性變化時的增量式計算，同時進一步地設計了相應的增量式屬性約簡算法；Wei等[10]學者基于區分矩陣的方法，構造了一種屬性變化時的增量式屬性約簡算法；Ni等[11]學者針對決策正區域構造出了一種加速器，提出了大規模數據的快速屬性約簡算法；Liu等[12]學者針對融合決策表利用不可區分矩陣提出了一種高效的快速增量式屬性約簡算法。對于優勢信息系統，Li等[13]學者在優勢粗糙集模型中，研究了優勢近似集隨屬性變化的增量式更新，同時進一步地提出了對應的增量式屬性約簡方法。對于集值信息系統，Lang等[14]學者提出了屬性變化時的增量式屬性約簡，在Lang的基礎上，Luo等[15]學者進一步地提出了集值序信息系統的增量式屬性約簡算法。在概率粗糙集模型中，Liu等[16]學者提出了一種屬性變化時的高效增量式屬性約簡算法。在完備型的混合型信息系統中，Shu等[17]學者針對鄰域粗糙集模型研究了條件信息熵的增量式計算，并設計出了一種增量式屬性約簡算法。在不完備信息系統方面，Shu等[18]學者給出了決策正區域隨屬性變化時的增量式更新，同時提出了對應的增量式屬性約簡；在Shu的基礎上，李成等[19]學者和劉吉超等[20]學者分別提出了對應的改進算法；基于不完備信息系統條件信息熵的視角，Wang等[21]學者提出了條件信息熵隨屬性變化的增量式更新，并提出了一種增量式屬性約簡算法。

然而，實際中存在著較多的離散型屬性和連續型屬性混合的不完備信息系統，目前關于這類信息系統的增量式屬性約簡研究卻比較少。在文獻[22]中，王映龍等學者提出了不完備混合型信息系統下對象變化的增量式屬性約簡，因此在本文，將針對不完備混合型信息系統屬性變化時，研究其增量式屬性約簡的問題。受文獻[8，18]的啟發，本文首先提出了不完備混合型信息系統下鄰域粗糙集正區域隨屬性增加和減少時的增量式更新，理論證明了更新方式的高效性，然后利用這種增量式更新對傳統的正區域屬性約簡進行拓展，提出了一種增量式屬性約簡算法。實驗分析證明了所提出算法的有效性和優越性。

1 基本理論

主要介紹不完備混合型信息系統下的鄰域粗糙集模型。

設一個不完備混合型信息系統表示為S=(U,C?D)，其中U稱為信息系統的論域，即數據集樣本的集合；C和D分別稱為信息系統的條件屬性集和決策屬性集，其中條件屬性集C可分成兩部分，即C=C a?C n，這里的C a稱為條件屬性集C的離散型屬性集，C n稱為條件屬性集C的連續型屬性集。在不完備混合型信息系統中，?x∈U,a∈C使得a(x)=*，其中a(x)表示對象x在屬性a下的屬性值，“*”表示屬性值為缺失的值。

定義1[23]給定不完備混合型信息系統S=(U,C?D)，鄰域半徑δ，設屬性子集A?C，并且A=Ac?An，其中Ac和An分別表示屬性子集A中的離散型屬性集和連續型屬性集。那么屬性子集A在信息系統S下確定的鄰域容差關系定義為：

這里的Δb(x,y)表示對象x與對象y之間的距離度量。

定義2[23]給定不完備混合型信息系統S=(U,C?D)，鄰域半徑δ，設屬性子集A?C確定的鄰域容差關系為，那么對于?x∈U關于的鄰域類定義為：

同時對于論域U在鄰域容差關系下確定的鄰域粒化定義為

定義3[23]給定不完備混合型信息系統S=(U,C?D)，鄰域半徑δ，設屬性子集A?C確定的鄰域容差關系為，對于近似對象集X?U關于的下近似集和上近似集分別定義為：

定義4[23]給定不完備混合型信息系統S=(U,C?D)，鄰域半徑δ，近似對象集X關于鄰域容差關系的正區域表示為：

特別地，對于決策屬性集D關于論域的劃分U/D={D1,D2,…,D m}，那么D關于鄰域容差關系的正區域表示為

在粗糙集理論中，正區域是一個很重要的概念，通過它可以直接度量信息系統屬性集之間的依賴程度，進而定義出信息系統的屬性約簡。

定義5[23]給定不完備混合型信息系統S=(U,C?D)，鄰域半徑δ，若屬性子集red是該信息系統的正區域屬性約簡，那么當且僅當

基于定義5所示的屬性約簡定義，文獻[23]提出了一種不完備混合型信息系統的屬性約簡算法。

2 屬性變化時鄰域粗糙集正區域的增量式更新

信息系統屬性的增加和減少是信息系統最為常見的一種更新變化形式，對于正區域屬性約簡的更新，如何進行正區域的增量式計算是其中的關鍵。本章將針對不完備混合型信息系統屬性變化的情形，提出正區域的增量式更新，為正區域增量式屬性約簡的構造提供理論鋪墊。

定義6給定不完備混合型信息系統S=(U,C?D)，對于對象集X?U，定義X的決策值域為?(X)={D(x)|x∈X}，其中D(x)表示對象x在決策屬性集D下的屬性值。

利用定義6中關于決策值域的定義，接下來可以進一步得到正區域的一種等價表達。

定理1給定不完備混合型信息系統S=(U,C?D)，對于鄰域半徑δ和屬性子集A，那么有：

證明根據定義4中關于正區域的定義，對于?x∈U，若|?(δA(x))|=1，說明δA(x)中對象的決策值是一致的，即所以

即定理1成立。

定理1提供了一種不完備混合型信息系統正區域的快速便捷計算方法。

給定不完備混合型信息系統S=(U,C?D)，鄰域半徑為δ，對于屬性集P,Q?C和?x∈U，那么滿足關系：

證明根據定義1中關于鄰域容差關系的定義，可以得到，再根據鄰域類的定義，可以直接得到成立。

定理2給定不完備混合型信息系統S=(U,C?D)，鄰域半徑為δ，對于屬性集P,Q?C滿足關系：

證明根據定義4中關于正區域的定義，可以直接得到定理2成立。

根據上述得到的定理，接下來將分別給出不完備混合型信息系統屬性增加和減少時，正區域的增量式更新計算。

定理3給定不完備混合型信息系統S=(U,C?D)，鄰域半徑為δ，屬性子集P,Q?C且P?Q=?，決策類劃分為U/D={D1,D2,…,D m}，決策屬性D關于P的正區域為，當增加屬性集Q，新的正區域增量式計算為：

證明對于，根據定義4中關于正區域的定義，滿足δP(x)?D t(1≤t≤m)。而根據定理1有δP?Q(x)?δP(x)，同樣滿足δP?Q(x)?D t(1≤t≤m)，即

那么δP?Q(x)?Dt(1≤t≤m)。根據鄰域類的定義，那么有由于P,Q?P?Q，那么顯然有：

即δP?Q(x)=δP(x)-Y，其中Y={y∈δP(x)|y?δQ(x)}。

即δP?Q(x)=δP(x)-Y，其中Y={y∈δP(x)|y?δQ(x)}。

通過定理1可得到：

因此

綜上所述有：

定理3證明完畢。

定理4給定不完備混合型信息系統S=(U,C?D)，鄰域半徑為δ，屬性子集Q?P?C，決策類劃分為U/D={D1,D2,…,D m}，決策屬性D關于P的正區域為，當從P刪除屬性集Q后，新的正區域增量式計算為：

證明由于P-Q?P,那么根據定理2有：

由于

因此

因此定理4成立。

定理3和定理4分別給出了當不完備混合型信息系統增加和減少屬性集時，決策正區域的增量式更新計算方法，該計算方法表明當屬性發生變化后，不必重新計算論域中每個對象的鄰域類，進而計算每個決策類的下近似集，只需在舊決策正區域的基礎上，進行進一步地相關計算，便可以快速地完成最終新決策正區域的更新，大幅度提高了計算效率，滿足數據集實時更新時的計算速率需求。

3 基于正區域的增量式屬性約簡算法

本章將在傳統的正區域屬性約簡算法基礎上，利用第2章中關于決策正區域的增量式計算方法，分別提出不完備混合型信息系統屬性增加和減少時的增量式屬性約簡算法，具體如算法1和算法2所示。

算法1不完備混合型信息系統屬性增加時的正區域增量式屬性約簡算法

輸入：不完備混合型信息系統S=(U,C?D)，鄰域半徑為δ，信息系統S的屬性約簡集red，決策正區域，新增加的屬性集ΔC，新信息系統記為S+=(U,C+?D)，其中C+=C?ΔC。

輸出：新信息系統S+的屬性約簡結果red+。

步驟1初始化red+=red。

步驟2根據決策正區域增量式計算//定理3。

步驟3如果，那么直接進入步驟6，否則進入步驟4。

步驟4計算C+-red+中每個屬性a的屬性重要度

步驟5找出C+-red+中屬性重要度sigred+(a)最大的屬性，記為amax,若sig red+(amax)＞0,那么red+=red+?{amax}，并重新進入步驟4，否則進入步驟6。

步驟6返回屬性約簡結果red+。

在算法1中，步驟2在原先正區域結果上進行增量式計算，如果新信息系統的正區域和原先約簡集的正區域一致，那么說明原先的約簡結果依然可以作為新信息系統的屬性約簡，則直接返回終止算法。如果不一致，那么需要在剩余的屬性中進行進一步地啟發式搜索，例如步驟4至步驟5，直到滿足正區域的一致性，最終完成屬性約簡的搜索。整個算法1的時間復雜度可表示為O(|ΔC|?|C?ΔC|?|U|)。

算法2不完備混合型信息系統屬性減少時的正區域增量式屬性約簡算法

輸入：不完備混合型信息系統S=(U,C?D)，鄰域半徑為δ，信息系統S的屬性約簡集red，決策正區域，屬性集C中減少的屬性集ΔC，新信息系統記為S-=(U,C-?D)，其中C-=C-ΔC。

輸出：新信息系統S-的屬性約簡結果red-。

步驟1初始化red-=red。

步驟2根據決策正區域增量式計算，根據決策正區域增量式計算//定理4。

步驟3如果，那么red-=red--ΔC并直接進入步驟6，否則進入步驟4。

步驟4計算C-red--ΔC中每個屬性a的屬性重要度

步驟5找出C-red--ΔC中屬性重要度sig red-(a)最大的屬性，記為amax，若sig red-(amax)＞0，那么red-=red-?{amax}，并重新進入步驟4，否則進入步驟6。

步驟6返回屬性約簡結果red-。

在算法2中，與算法1類似，步驟2在原先正區域結果上進行增量式計算，如果新信息系統的正區域和原先約簡集剔除屬性后的正區域一致，那么說明原先約簡集剔除相關屬性的結果依然可以作為新信息系統的屬性約簡，則直接返回終止算法。如果不一致，那么需要在剩余的屬性中進行進一步地啟發式搜索，例如步驟4至步驟5，直到滿足正區域的一致性，最終完成屬性約簡的搜索。類似于算法1，整個算法2的時間復雜度可表示為O(|ΔC|?|C-ΔC|?|U|)。

4 實驗分析

本章將通過實驗的方法驗證所提出的增量式屬性約簡算法的有效性和優越性。表1所示的是實驗數據集，其中均下載至UCI機器學習數據集庫，并且均為混合屬性類型的數據集，部分完備型的數據集隨機選擇了4%的條件屬性值進行刪除。所有的實驗均在Intel?CoreTMi5-6500 CPU 3.2 GHz和8 GB內存的Windows 10操作系統個人PC機上，算法采用Matlab2015b進行編程實現和運行。

表1 實驗數據集

本實驗分為三個環節，第一個環節主要是通過實驗獲得本文算法的合適參數，為后面實驗以及本文算法的實際應用提供參考。第二部分是將本文所提出的增量式屬性約簡算法與傳統的非增量式算法對同一組數據集進行動態屬性約簡，從而驗證本文增量式算法的有效性。第三部分將本文算法與其他的增量式算法進行實驗比較，以此證明本文算法的優越性。

本實驗中所有實驗流程均為動態數據集環境下的屬性約簡，為了實現這一數據環境，這里采用大多數學者的處理方式[18-21]，即通過對完整數據集進行分割，然后不斷地將分割的各個部分進行融合，從而達到了數據集的增加情形，通過將完整的數據集依次移除每個部分，從而達到了數據集的減小情形。這里將各個數據集的屬性大致平均分割成10個子集，隨機選擇某個屬性子集開始不斷進行融合，實現了9次屬性增加，將各個數據集的屬性從屬性全集開始，依次刪除各個屬性子集，從而實現了9次屬性減少。接下來的所有實驗算法均以此實現方案進行。

為了選擇出本文算法中合適的入參鄰域半徑δ，這里將鄰域半徑在0.02至0.3之間以0.02為間隔分別取值，將對應鄰域半徑作為入參進行增量式屬性約簡，每個取值在每次屬性約簡下都會得到對應的約簡結果，然后利用SVM分類器和NB分類器分別計算約簡結果的分類精度，將同一個鄰域半徑得到的所有分類精度結果求取平均值，其中包含了屬性增加和屬性減少的兩種情形，繪制成圖像如圖1所示，由于篇幅的限制，這里只列舉了部分數據集的結果。

觀察圖1各個數據集的實驗結果可以發現，無論是屬性的逐漸增加還是屬性的逐漸減少，隨著鄰域半徑的逐漸增大，其約簡結果的平均分類精度都是先增大然后逐漸大致減小的，因此說明過大和過小的鄰域半徑都不能得到較好的實驗結果。綜合實驗結果，將鄰域半徑選取為δ=0.12較為適宜。

圖1 部分數據集不同鄰域半徑下的分類精度

圖2 屬性增加時增量與非增量算法的約簡時間比較

圖3 屬性減少時增量與非增量算法的約簡時間比較

圖2 和圖3分別所示的是本文的兩種增量式屬性約簡算法與非增量式算法進行動態屬性約簡的用時比較結果，其中圖2展示的是屬性增加時的屬性約簡比較，圖3展示的是屬性減少時的屬性約簡比較。每幅圖的橫坐標代表數據集屬性增量更新次數，縱坐標代表屬性約簡用時。

觀察圖2中各個數據集的結果，可以看出隨著數據集屬性的不斷增加，本文所提出的增量式屬性約簡算法的計算用時大幅度小于非增量式算法，并且隨著更新次數的增加，這種差距愈加明顯。產生這一現象的主要原因是由于隨著屬性的增加，其數據集的規模逐漸增大，而傳統的非增量式屬性約簡算法需要對完整的數據集進行正區域的相關計算，因此計算量會越來越大，對于增量式算法，隨著數據集屬性的增加，該算法通過增量式的計算形式，利用前一次的計算結果進行后一次計算，對原先舊數據集的依賴程度較低，因此計算量大幅度小于非增量式屬性約簡算法。

觀察圖3中各個數據集的結果，可以看出隨著數據集屬性的不斷減少，本文所提出的增量式屬性約簡算法的計算用時同樣大幅度小于非增量式算法，與圖2不同的是，圖3中各個數據集剛開始增量式更新時，其增量式算法與非增量式算法的時間差距較大，隨著更新次數的增多，兩者差距逐漸減小。產生這一現象的原因與圖2的原因相反，即剛開始增量式更新時，數據集的規模比較大，因此非增量式算法的用時比較多，隨著數據集屬性的不斷減少，數據集的規模在減小，因此非增量式算法的約簡用時也在減小，逐漸與增量式算法縮小了差距，最終更新結束時，非增量式算法與增量式算法的用時比較接近。

綜合非增量式屬性約簡算法與增量式屬性約簡算法的動態屬性約簡效率結果，可以看出本文設計的增量式屬性約簡算法大大提高了對動態數據集的屬性約簡效率，證明了該算法的有效性。

為了驗證本文所提出增量式算法的優越性，本實驗選取了三種對比算法。

（1）基于不完備信息系統的條件信息熵增量式屬性約簡算法[21]（記作：對比增量式算法1）。

（2）基于不完備信息系統的正區域增量式屬性約簡算法[18]（記作：對比增量式算法2）。

（3）基于改進的不完備信息系統增量式屬性約簡算法[20]（記作：對比增量式算法3）。

其中這三種對比算法均只適用于離散型的信息系統，因此這三種算法進行實驗前需要將表1中的數據集進行離散化處理。

將本文所提出的增量式算法與參與對比的增量式算法對表1中的數據集分別進行動態屬性約簡，其中圖4和圖5分別所示的是屬性增加和屬性減少時各個算法的動態屬性約簡用時比較結果圖。表2和表3分別所示的是屬性增加和屬性減少時各個算法屬性約簡的屬性數量結果，其中平均屬性數量通過每次更新時的屬性約簡結果求取平均值得到。表4和表5分別所示的是屬性增加和屬性減少時各個算法屬性約簡的分類精度結果，其中分類精度也通過每次更新時的屬性約簡分類精度求取平均值得到。

通過圖4和圖5可以發現，無論是數據集屬性的增加還是屬性的減少，其中對比增量式算法1有著最高耗時，對比增量式算法2的用時次之，本文的增量式算法均具有最少的屬性約簡用時，這主要是由于對比算法1基于條件信息熵進行屬性約簡，因此約簡的過程中計算量比較大，而本文的增量式算法以正區域作為屬性約簡的啟發式函數，并且本文提出了一種等價形式的正區域計算方法，其計算量大幅度降低，因此進行增量式屬性約簡時具有很高的計算效率。

圖4 屬性增加時各個增量式算法的約簡時間比較

圖5 屬性減少時各個增量式算法的約簡時間比較

表2 屬性增加時各個算法約簡結果屬性數量比較

表3 屬性減少時各個算法約簡結果屬性數量比較

表4 屬性增加時各個算法約簡結果分類精度比較%

表5 屬性減少時各個算法約簡結果分類精度比較%

在表2和表3所示的平均屬性數量結果中，本文所提出的增量式算法在大部分數據集有著最少的平均屬性數量，這一方面得益于正區域度量在屬性約簡中發揮的作用，正區域作為一種經典的屬性約簡方法，能夠很精準地鑒別出信息系統的關鍵屬性，并且約簡結果中很少有包含冗余屬性，另一方面由于參與比較的算法需將數據集進行離散化，這一過程丟失了連續型屬性的分類信息，因而約簡得到的屬性會增多，所以本文算法得到的平均屬性數量會更少。對于表4和表5所示的分類精度結果，可以發現在表4中，本文的增量式算法在數據集Thyroid、Gearbox和Musk下有著較高的SVM分類精度，在數據集Sick和Annealing下有著較高的NB分類精度。在表5中，本文的增量式算法在數據集Thyroid、Annealing、Gearbox和Musk下有著較高的SVM分類精度，在數據集Sick、Thyroid和Cylinder下有著較高的NB分類精度，綜合可以說明本文算法的約簡結果在多數數據集下有著較高的分類精度。

5 總結

屬性約簡是粗糙集理論的重要研究內容，然而實際環境下數據集是不斷動態更新的，如何設計出高效的增量式屬性約簡算法是目前該領域的研究重點。在本文，提出一種不完備混合型信息系統的正區域增量式屬性約簡算法，其中分別包含了屬性增加和屬性減少時屬性約簡的增量式更新。首先文中提出了一種不完備混合型信息系統正區域的等價表達形式，理論分析表明這種計算的高效性，然后利用該正區域的表達形式，分別構造出了屬性增加和屬性減少時正區域的增量式更新，并證明了這種更新計算方式主要依賴于新加入的數據信息或者減少的數據信息，最后基于這種正區域的增量式計算，分別設計出了屬性增加和屬性減少時的增量式屬性約簡算法。通過進行一系列的實驗，證明所提出的增量式屬性約簡算法比非增量式的算法具有高效的動態屬性約簡性能，同時，與同類型的增量式屬性約簡算法相比，本文算法也表現出了一定的優越性能。在本文基礎上，接下來可以進一步研究對象和屬性同時變化以及屬性值變化時的增量式屬性約簡問題，從而進一步擴大增量式屬性約簡的適用范圍。