面向缺失數據的動態特征選擇

王 鋒，宋 鵬

1(山西大學 計算機與信息技術學院，太原030006)2(山西大學 經濟與管理學院，太原 030006)

1 引 言

隨著各種數據觀測和數據獲取工具的更新和迅速發展，使得數據庫中數據更新的速度越來越快，同一時刻有大量數據發生變化.尤其目前在大數據背景下，數據更新的速度和規模都在發生著巨大的變化，這對如何高效地從更新后的數據中獲取知識帶來了全新而巨大的挑戰.數據挖掘技術旨在研究如何從數據中挖掘潛在的信息，即發現知識.面對快速更新的動態數據集，探索和發展高效的可有效處理動態數據集的數據挖掘技術也已迅速成為目前數據挖掘研究中的一個熱點問題[1,2].

數據挖掘技術的探索中表明，對數據進行有效的預處理可進一步方便或加快數據中知識的獲取.特征選擇作為一種常用的數據預處理技巧已經被廣泛用于許多實際應用領域中，如：圖像檢索，入侵檢測以及文本分類等[3-8].隨著對動態數據挖掘技術的分析和探索，面向動態數據集的有效特征子集的選取也引起研究者的關注，且隨著研究的逐步深入，目前已經取得了一系列的研究成果.針對數據集規模的不斷增大，Liu基于引入布爾矢量到特征表示中，提出了一種針對無類信息數據的增量式特征選擇更新算法，是一類無監督的特征選擇算法[9].Orlowska和Yang等基于粗糙集理論，分別設計了面向有類信息數據集的一種增量式特征選擇算法[10,11].Liang等通過分析三種常見信息熵的增量式更新機制，一種基于信息熵的特征選擇的組增量更新算法，即該算法可一次處理一組新增的數據集[12].針對數據集維數的動態更新，Wang等設計了一種維數增量式特征選擇處理機制，當給定數據集增加一個特征集后，該算法可高效地求解到維數增加后的有效特征子集[13].針對數據表中數據取值的動態更新，Wang等基于粗糙集理論和信息熵的概念，提出了一種可有效處理數據取值動態變化的特征子集更新算法[14].在該算法的基礎上，Zhang等發展了一種可有效處理一批數據取值發生變化特征選擇更新機制[15].

實際應用中數據取值缺失的現象是廣泛存在的，為此眾多研究者已經提出了一系列面向含有缺失數據的數據挖掘算法和技術[16,17].其中針對面向含有缺失數據的特征選擇的研究也取得了可觀的成果.隨著面向動態數據集特征選擇技術的深入探索，如何高效地求解含有缺失數據的動態數據集的有效特征子集也成為了特征選擇研究中的一個重點研究問題.Wang等通過分析含有缺失數據的數據集中新增數據后，信息熵的單增量和組增量更新機制，通過重新定義特征重要度，提出了一種面向含有缺失數據數據集的組增量特征選擇更新算法[18].本文針對數據取值動態更新的含有缺失數據的數據集，基于粗糙集理論和信息熵的概念[19-21]，設計了一種面向缺失數據的動態特征選擇算法.為有效求解數據集更新后的特征子集，本文中首先討論并分析了當數據取值變化后，數據集上互補信息熵的更新機制，并重新定義了特征重要度.在此基礎上，設計了基于信息熵的動態特征選擇算法.為進一步驗證本文提出特征選擇算法求解過程中的高效性以及其選擇結果的有效性，實驗分析中選取了4組UCI中含有缺失數據的數據集進行仿真實驗，并分別與基于信息熵的經典算法進行了比較，實驗結果進一步驗證了新算法的高效性和可行性.

2 基本概念

本節中以粗糙集理論為背景介紹含有缺失數據的數據集的相關符號表示.

對給定的數據表，粗糙集理論中令S=(U，C∪D)表示一個數據表，其中C表示數據表的特征集，D表示數據表的類信息，U是數據表的論域.對任意的a∈C，有a:U→Va，其中Va是特征a的值域，即對任意的a∈C，x∈U有f(x，a)∈Va，其中f(x，a)是一個信息函數，它對數據表中每個對象的每個特征賦予一個具體的值.如果至少有一個特征a∈C使得Va中含有空值，即表示數據表S中含有缺失的數據取值，粗糙集中稱該類數據表為非完備數據表，并使用*表示數據表中的空值，即缺失掉的數據取值.

粗糙集理論中，設P?C，由P誘導的相容關系定義為：

SIM(P)={(x，y)∈U×U|?a∈P，f(x，a)=f(y，a)或f(x，a)=*或f(y，a)=*}.

在此基礎上，令SP(x)={y∈U|(x，y)∈SIM(P)}表示與數據對象x可能不可區分的數據的最大集合.U/SIM(P)是數據表上的一個分類，其中的每個元素稱為相容類.

定義1.令S=(U，C∪D)是一個含有缺失數據的數據表，P?C，則互補信息熵的條件熵定義為

上述信息熵的定義見文獻[17].

3 信息熵更新機制

對于含有缺失數據的數據集，本節主要介紹上述信息熵隨數據取值動態變化的更新機制.通過分析給定數據集中數據取值發生變化的數據對象所在的相容類的變化，在本節中分析并證明互補信息熵隨數據對象取值變化的更新機制，具體介紹如下.

定理1.令S=(U，C∪D)是一個含有缺失數據的數據集，P?C，且有U/SIM(P)={SP(x1)，SP(x2)，…，SP(x|U|)}和U/SIM(D)={SD(x1)，SD(x2)，…，SD(x|U|)}.論域U上D關于P的互補信息熵記為EU(D|P).當數據對象x∈U的取值發生變化，變化為x′.設與原數據x在特征集P上滿足相容關系的數據集為X，在D上與x滿足相容關系的數據集為Y，與變化后的數據x′在P和D上滿足相容關系的數據集分別為X′和Y′.則論域U上新的互補信息熵為

E′(D|P)=EU(D|P)+Δ，

證明：當數據對象x的變化為x′后，論域中與x和x′滿足相容關系的數據主要由分以下幾種情況討論：

1) 對?y∈U-X∪Y(或?y′∈U-X′∪Y′)，x和y(或x′和y′)在P和D上均不滿足相容關系；

2)對?y∈Y-X(或?y′∈Y′-X′)，x和y(或x′和y′)在D上滿足相容關系，而在P上不滿足相容關系；

3) 對?y∈X-Y(或?y′∈X′-Y′)，x和y(或x′和y′)在P上滿足相容關系，而在D上不滿足相容關系；

4) 對?y∈X∩Y(或?y′∈X′∩Y′)，x和y(或x′和y′)在P和D上都滿足相容關系.

由于x的取值變化為x′可理解為先從給定數據集中去掉數據x再添加新數據x′.因此，證明過程中先證明從數據集中刪除一個數據的信息熵更新機制，再分析向數據集中添加一個新數據的更新機制.當將數據x從數據集中刪除后，假設l=|U-X∪Y|，U-{x}/SIM(P) ={SP′(x1)，SP′(x2)，…，SP′(x|U|)}，且U-{x}/SIM(D) ={SD′(x1)，SD′(x2)，…，SD′(x|U|)}，則數據集U-{x}上的互補信息熵為：

EU-{x}(D|P)

∩(SD(xi)-{x})|)-|X-Y|

-|X-Y|+

-2|X-Y|)

當數據集U-{x}中添加新對象x′后，令U′表示新數據集U-{x}∪{x′}，則根據文獻[18]中定理1可得U′上的互補信息熵為：

因為|U|的值和|U′|的值是相等的，所以上述計算公式可進一步表示為：

由定理1可得，當給定數據集中有數據的取值發生變化后，通過分析與該數據變化前后滿足相容關系的數據子集，即可通過上述定理中的計算公式求解到數據集上新的熵值，降低了計算代價，提高了計算效率.

4 動態特征選擇算法

基于定理1中對信息熵隨數據取值更新的分析和證明，本節中基于信息熵的概念重新定義了特征重要度，并在此基礎上設計了一種面向數據取值動態更新的特征選擇算法.

4.1 特征重要度的度量

定義2.令S=(U，C∪D)是一個含有缺失數據的數據集，P?C，對任意特征a∈P的特征重要度定義為

Sigin(a，P，D)=E(D|P-{a})-E(D|P)，

而任意特征a∈C-P的特征重要度定義為

Sigout(a，P，D)=E(D|P)-E(D|P∪{a}).

上述定義中的Sigin(a，P，D)和Sigout(a，P，D)在粗糙集理論中分別稱為內部重要度和外部重要度.其中內部重要度主要用于檢測特征子集中的冗余特征，即相對于當前特征子集不重要的特征，如果內部重要度為0(或小于給定閾值)，則被認為是冗余特征；外部重要度主要用于當前特征子集不滿足結束規則時，向當前特征子集中添加新的重要特征，在搜索過程中通常選擇外部重要度最大的特征添加到當前特征子集中.

4.2 面向含有缺失數據的動態特征選擇算法

基于第3節中信息熵的更新機制和4.1節特征重要度的度量，本節中介紹一種可有效處理含有缺失數據的數據集中數據取值動態更新的動態特征選擇算法，算法步驟介紹如下.

算法1.一種面向含有缺失數據的動態特征選擇算法(DFSM)

輸入：含有缺失數據的數據集S=(U，C∪D)，U上的特征選擇結果R，數據對象x取值更新為x′；

步驟1.B←R，計算X和Y：?y∈U，如果x與y在B上滿足相容關系，則X=X∪{y}，如果x與y在D上滿足相容關系，則Y=Y∪{y}；

步驟2.計算X′和Y′：?y∈U′，如果x′與y在B上滿足相容關系，則有X′=X′∪{y}，如果x′與y在D上滿足相容關系，則Y′=Y′∪{y}；

步驟3.whileEU′(D|B)≠EU′(D|C)do

{?a∈C-B，計算其外部重要度Sigout(a，B，D)；

選擇外部重要度最大的特征a0=max{Sigout(a，B，D)}，a∈C-B；

B←B∪{a0}；

}

步驟4.?a∈B執行

{計算其內部重要度Sigin(a，B，D)；

如果Sigin(a，B，D)=0，則B←B-{a}；

}

當給定含有缺失數據的數據集中有數據的取值被更新后，使用上述算法可快速求解到新的特征選擇結果，有效節省了重新計算的計算代價和耗時.算法1中的步驟3的操作是向當前特征子集中添加新的特征，步驟4的操作是檢測特征選擇結果中的冗余特征.

算法DFSM的計算時間復雜度分析：根據定理1，當有一個數據對象的取值被更新后，計算新的信息熵的時間復雜度是O(|U||C|+|X||Y||C|).則有算法步驟1-3的時間復雜度是O(|U||C|2+|X||Y||C|2)；步驟4的時間復雜度是O(|U||C||B|+|X||Y||C||B|)；所以算法總的時間復雜度是O(|U||C|2+|X||Y||C|2).

5 實驗分析

為驗證動態特征選擇算法DFSM的有效性，本節中選取了4組UCI數據集(見表1)進行測試.程序運行的個人計算機配置為CPU Inter(R) Core(TM) i7-6700，3.40GHz，內存為8.00GB，操作系統是Windows 7.程序開發平臺是 Microsoft Visual Studio 2005，編程語言為C#.

表1 實驗數據集Table 1 Data sets for experiments

為有效驗證算法DFSM的有效性，對表1中的每組數據集，實驗中選取40%數據作為取值發生變化的數據子集.當每組數據集中部分數據取值被更新后，本節實驗中分別使用算法DFSM和基于信息熵的經典特征選擇算法[17]求解數據集上的特征選擇結果.為進一步驗證本文中新算法的性能，本節中引入了兩個常見分類器(樸素貝葉斯和決策樹)來測試上述兩個算法特征選擇結果的分類精度.特征選擇結果的分類精度和計算時間見表2，其中NBC表示樸素貝葉斯分類器，C4.5表示決策樹，N為選擇到的有效特征個數，IFS表示面向含有缺失數據的基于信息熵的粗糙特征選擇算法[17].

表2 特征選擇結果比較Table 2 Comparison of feature subsets

為進一步驗證算法DFSM的高效性，對表1中的每組數據集，依次選取其中的10%，20%，30%，40%，50%規模的數據并更新其數據取值.然后分別使用算法DFSM和IFS來計算數據取值發生變化后的新數據集上的特征選擇結果，上述兩個算法的計算時間見圖1-圖4，其中x軸表示10%-50%數據取值被更新的不同規模，y軸表示計算時間.

圖1 Backup-large的計算時間Fig.1 Computational timeof Backup-large圖2 Cancer的計算時間Fig.2 Computational timeof Cancer

圖3 Mushroom的計算時間Fig.3 Computational timeof Mushroom圖4 Shuttle的計算時間Fig.4 Computational timeof Shuttle

由表2和圖1-圖4的實驗比較結果可得，與經典的基于信息熵的粗糙特征選擇方法相比較，本文中的新算法在求解特征選擇過程中明顯降低了計算耗時，提高了計算效率.而且，求解到的特征子集的分類性能并未降低.由圖1-圖4中計算時間的比較可進一步得到，隨著取值被更新的數據子集規模的不斷增大，本文新算法都能節省大量的計算時間，高效性非常明顯.因此，本節中實驗結果表明，算法DFSM可在更短的時間內求解到一個有效的特征子集.

6 結 論

數據觀測和數據獲取工具的更新和迅速發展，使得可有效處理動態數據集的數據挖掘技術引起眾多研究者的廣泛關注.本文以含有缺失數據的數據集為背景，通過分析并證明信息熵的更新機制，發展了一種基于信息熵的動態特征選擇算法.實驗分析進一步驗證了當給定數據集中的部分數據取值被更新后，新算法在節省大量計算耗時的同時，可求解到一個有效的特征子集.海量高維的數據集中經常存在著大量的過時而冗余的數據，為進一步提高信息獲取的時效性，可考慮直接將這類無效的數據更新為最新的取值，再進行知識獲取.這樣既可節省大量存儲空間，也可基于原有的信息獲取結果發現新的知識.本文的算法為探索數據取值動態更新的數據挖掘技術提供了新的思路和可以借鑒的研究途徑.