面向缺失數(shù)據(jù)的動(dòng)態(tài)特征選擇

王 鋒，宋 鵬

1(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原030006)2(山西大學(xué) 經(jīng)濟(jì)與管理學(xué)院，太原 030006)

1 引 言

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

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

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

2 基本概念

本節(jié)中以粗糙集理論為背景介紹含有缺失數(shù)據(jù)的數(shù)據(jù)集的相關(guān)符號(hào)表示.

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

粗糙集理論中，設(shè)P?C，由P誘導(dǎo)的相容關(guān)系定義為：

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

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

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

上述信息熵的定義見文獻(xiàn)[17].

3 信息熵更新機(jī)制

對于含有缺失數(shù)據(jù)的數(shù)據(jù)集，本節(jié)主要介紹上述信息熵隨數(shù)據(jù)取值動(dòng)態(tài)變化的更新機(jī)制.通過分析給定數(shù)據(jù)集中數(shù)據(jù)取值發(fā)生變化的數(shù)據(jù)對象所在的相容類的變化，在本節(jié)中分析并證明互補(bǔ)信息熵隨數(shù)據(jù)對象取值變化的更新機(jī)制，具體介紹如下.

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

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

證明：當(dāng)數(shù)據(jù)對象x的變化為x′后，論域中與x和x′滿足相容關(guān)系的數(shù)據(jù)主要由分以下幾種情況討論：

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

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

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

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

由于x的取值變化為x′可理解為先從給定數(shù)據(jù)集中去掉數(shù)據(jù)x再添加新數(shù)據(jù)x′.因此，證明過程中先證明從數(shù)據(jù)集中刪除一個(gè)數(shù)據(jù)的信息熵更新機(jī)制，再分析向數(shù)據(jù)集中添加一個(gè)新數(shù)據(jù)的更新機(jī)制.當(dāng)將數(shù)據(jù)x從數(shù)據(jù)集中刪除后，假設(shè)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|)}，則數(shù)據(jù)集U-{x}上的互補(bǔ)信息熵為：

EU-{x}(D|P)

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

-|X-Y|+

-2|X-Y|)

當(dāng)數(shù)據(jù)集U-{x}中添加新對象x′后，令U′表示新數(shù)據(jù)集U-{x}∪{x′}，則根據(jù)文獻(xiàn)[18]中定理1可得U′上的互補(bǔ)信息熵為：

因?yàn)閨U|的值和|U′|的值是相等的，所以上述計(jì)算公式可進(jìn)一步表示為：

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

4 動(dòng)態(tài)特征選擇算法

基于定理1中對信息熵隨數(shù)據(jù)取值更新的分析和證明，本節(jié)中基于信息熵的概念重新定義了特征重要度，并在此基礎(chǔ)上設(shè)計(jì)了一種面向數(shù)據(jù)取值動(dòng)態(tài)更新的特征選擇算法.

4.1 特征重要度的度量

定義2.令S=(U，C∪D)是一個(gè)含有缺失數(shù)據(jù)的數(shù)據(jù)集，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)在粗糙集理論中分別稱為內(nèi)部重要度和外部重要度.其中內(nèi)部重要度主要用于檢測特征子集中的冗余特征，即相對于當(dāng)前特征子集不重要的特征，如果內(nèi)部重要度為0(或小于給定閾值)，則被認(rèn)為是冗余特征；外部重要度主要用于當(dāng)前特征子集不滿足結(jié)束規(guī)則時(shí)，向當(dāng)前特征子集中添加新的重要特征，在搜索過程中通常選擇外部重要度最大的特征添加到當(dāng)前特征子集中.

4.2 面向含有缺失數(shù)據(jù)的動(dòng)態(tài)特征選擇算法

基于第3節(jié)中信息熵的更新機(jī)制和4.1節(jié)特征重要度的度量，本節(jié)中介紹一種可有效處理含有缺失數(shù)據(jù)的數(shù)據(jù)集中數(shù)據(jù)取值動(dòng)態(tài)更新的動(dòng)態(tài)特征選擇算法，算法步驟介紹如下.

算法1.一種面向含有缺失數(shù)據(jù)的動(dòng)態(tài)特征選擇算法(DFSM)

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

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

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

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

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

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

B←B∪{a0}；

}

步驟4.?a∈B執(zhí)行

{計(jì)算其內(nèi)部重要度Sigin(a，B，D)；

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

}

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

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

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

為驗(yàn)證動(dòng)態(tài)特征選擇算法DFSM的有效性，本節(jié)中選取了4組UCI數(shù)據(jù)集(見表1)進(jìn)行測試.程序運(yùn)行的個(gè)人計(jì)算機(jī)配置為CPU Inter(R) Core(TM) i7-6700，3.40GHz，內(nèi)存為8.00GB，操作系統(tǒng)是Windows 7.程序開發(fā)平臺(tái)是 Microsoft Visual Studio 2005，編程語言為C#.

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Data sets for experiments

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

表2 特征選擇結(jié)果比較Table 2 Comparison of feature subsets

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

圖1 Backup-large的計(jì)算時(shí)間Fig.1 Computational timeof Backup-large圖2 Cancer的計(jì)算時(shí)間Fig.2 Computational timeof Cancer

圖3 Mushroom的計(jì)算時(shí)間Fig.3 Computational timeof Mushroom圖4 Shuttle的計(jì)算時(shí)間Fig.4 Computational timeof Shuttle

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

6 結(jié) 論

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