不完備數據中面向特征值更新的增量特征選擇方法

唐榮，羅川，曹潛，王思朝

（四川大學 計算機學院，四川 成都 610065）

特征選擇的目標是在給定評價標準下選擇非冗余的特征子集，其作為一項重要的數據預處理步驟，能夠有效地提高數據分析模型的準確性和高效性，在數據挖掘與知識發現中起著重要的作用[1]。

數據中存在一些缺失值是一種非常普遍的現象，缺失值給數據中的分類知識帶來了不一致性問題[2]。粗糙集理論是一種能夠有效應對不精確、不一致信息的數據建模與知識獲取工具。近年來，人們基于粗糙集理論針對不完備數據的特征選擇問題進行了深入的分析和討論。Kryszkiewicz[3]認為不完備數據中缺失值應是已有值域中的某一特征值，進而提出了一種基于廣義差別矩陣的特征選擇方法。Parthalin等[4]為了保留分類所產生的不一致決策區域，研究了基于容差粗糙集的特征選擇方法。Meng等[5]討論了不一致不完備決策系統中基于區分矩陣的特征選擇方法。Grzymala-Busse等[6]將缺失值考慮為丟失值和不在乎值，提出了基于廣義特征關系粗糙集模型的特征選擇方法。Qian等[7]提出了一種高效的正向近似加速器，用于加速不完備數據特征選擇的啟發式特征搜索過程。Dai[8]為了處理不完備數值型數據，建立了一種新的容差模糊粗糙集模型，并提出了基于差別矩陣的特征選擇方法。Yang等[9]定義了多準則決策系統中相似優勢關系的概念，提出了4種基于差別矩陣的近似分布約簡方法。Liang等[10]提出了一種不完備信息系統中基于粗糙熵的啟發式特征選擇算法。Qian等[11]基于不完備信息系統中的最大一致塊概念，提出了一種新的組合信息熵用于度量信息系統的不可分辨能力。Dai等[12]在不完備決策系統中提出一種新的滿足單調性約束的條件信息熵。Zhao等[13]提出了一種新的鄰域容差條件熵，并將其應用于混合不完備數據中的特征選擇問題。

另一方面，實際應用中數據隨時間的推移呈現出動態更新的變化趨勢，數據的采集與分析是一個不斷優化升級的動態過程。面向動態數據的高效特征選擇方法成為了當前人們普遍關注的一個研究熱點。增量技術可以利用已有計算結果進行特征選擇增量計算，以發現新的特征子集，從而避免重新計算整個特征空間以獲取新的特征子集[14-15]。近年來，許多學者通過將增量學習技術引入到特征選擇問題中，對動態數據環境下的高效特征選擇方法進行了廣泛深入的研究。Xu等[16]將特征選擇問題轉化為0-1整數規劃問題，提出了一種對象更新條件下的動態特征選擇方法。Qian等[17]設計了一種新的基于相對不可辨識對象對的屬性重要度度量方式，并提出了動態粒度空間下的基于序貫三支決策模型的增量特征選擇方法。Yang等[18]分析了對象動態變化時相對可辨識關系的增量更新機制，提出了基于模糊粗糙集的動態特征選擇算法。Lang等[19]提出了覆蓋信息系統中基于相關族的動態特征選擇方法。Wei等[20]設計了基于辨識矩陣和壓縮辨識矩陣的增量特征選擇算法，以獲得數據動態變化時最優的特征子集。Zeng等[21]基于高斯核模糊粗糙集模型，研究了混合信息系統的動態特征選擇方法。Liang等[22]提出了信息熵的批增量遞推計算機制，可用于多個數據集之間信息熵的高效融合。Shu等[23]針對含有缺失值的不完備數據，提出了基于正域的增量特征選擇算法。Xie等[24]提出了3種不完備數據中相容類的更新策略，并設計了相應的增量特征選擇算法?？紤]到動態數據中特征值存在頻繁的修改和更新操作，Wang等[25]針對完備數據集研究了特征值動態更新時信息熵的增量更新機制，進一步設計了相應的動態特征選擇算法。劉吉超等[26]針對不完備數據中數據集維數動態增加的情形，分析了互補信息熵的更新機制，進而提出了一種增量特征約簡算法。錢進等[27]提出一種基于正域處理面向成組對象集的增量式特征選擇算法。綜合上文所述，大部分研究者針對完備決策系統的動態更新特征選擇問題進行深入的研究，鮮有對不完備決策系統動態更新特征問題研究。基于正域處理不完備決策系統的特征選擇存在無法處理邊界域中的樣本分類的不確定性問題。信息熵作為度量信息不確定性的度量標準，有助于不完備數據特征選擇問題研究，而引入增量計算機制可以加速特征選擇過程，有效減少計算時間。本文針對不完備決策系統，設計了一種面向特征值動態更新的特征選擇算法。文中首先分析了特征值更新時不完備決策系統中相容類和決策類的動態變化模式，并以此給出了條件信息熵的增量計算機制，進而設計了基于增量條件信息熵的動態特征算法，最后通過實驗驗證進一步說明了算法的有效性和高效性。

1 基本概念

粗糙集理論中，信息系統表示為一個四元組S=(U,A,V,f) ， 其中，U表示對象的非空有限集合，稱為論域；A表示特征的非空有限集合，即特征集；Va表示特征a∈A的值域，并且有V=∪a∈AVa；對任意a∈A和x∈U，f:U×A→V是一個信息函數，通過信息函數給每一個對象x∈U一個特定的特征值f(x,a)∈Va，a∈A。決策系統表示為DS=(U,C∪g0gggggg,V,f) ， 其中，C代表條件特征的非空有限集合；d表示決策特征。在實際應用中，信息系統中某些對象的特征值容易丟失，如果一個信息系統中V包含缺失的特征值，記作“*”，那么該信息系統被稱為不完備信息系統(incomplete information system，IIS)；對于決策系統來說，如果?∈VC,??Vd，稱這樣的決策系統為不完備決策系統(incomplete decision system，IDS)；對于??VC,??Vd這樣的決策系統，稱為完備決策系統。

完備信息系統中條件特征的任何子集P?C可誘導一種不可辨識關系 I ND(P)，定義為

IND(P)={(x,y)∈U×U|?a∈P,f(x,a)=f(y,a)}

IND(P)是具有自反性、對稱性與傳遞性的等價關系。等價關系 I ND(P) 將論域U劃分為等價類的集合，表示為U/IND(P)={[x]P|x∈U}，其中[x]P={y|(x,y)∈IND(P)}。為了處理含有缺失值的不完備決策系統，Kryszkiewicz提出一種新的二元關系T(P),P?C，定義為

T(P)={(x,y)∈U×U|?a∈P,f(x,a)=f(y,a)∨f(x,a)=?∨f(y,a)=?}

T(P)是具有自反性和對稱性，但不具有傳遞性的相容關系。在P下任意一個對象x∈U的相容類定義為TP(x)={y∈U|(x,y)∈T(P)}。U/T(P) 表示相容類集合 {T(P)|x∈U}。U/T(P) 中構成論域U上的一個覆蓋，對于論域中任意一個對象x∈U,TP(x)≠?，并且 ∪x∈UTP(x)=U。給定一個不完備決策系統IDS=(U,C∪g0gggggg,V,f) ， 決策屬性d將對象分類為m個確定互斥的子集U/d={D1,D2,···,Dm}。目標決策概念Di∈U/D的上、下近似集定義為

基于粗糙集理論的特征選擇方法根據特征重要度的不同度量標準，可籠統地歸納為依賴性度量、一致性度量、距離度量和信息度量。前面3種度量方法都局限于數據的實際值，對含有噪聲或缺失值的數據處理十分敏感。而基于信息論的度量方法僅關注隨機變量的概率分布，不關注其實際值，成為了高維數據中常用的特征重要度度量方式。借鑒香農熵的傳統定義形式，Dai等[8,12]定義了一種新的滿足單調性的條件熵來度量不完備決策系統協調程度的不確定性。給定一個不完備決策系統 I DS=(U,C∪g0gggggg,V,f)， 其中，U={x1,x2,···,

xn} ；U/T(P)={TP(xi)|i=1,2,···,n} ；U/d={D1,D2,···,Dm} 。決策特征d關于條件特征子集P的條件熵定義為

根據式（1），通過從特征子集P刪除某個特征a引起的條件熵的變化大小，可定義特征的重要度度量函數：

sig(a,P,d)=H(d|P)?H(d|P?{a})

2 不完備數據集中特征值更新的增量特征選擇

當不完備決策系統中特征值發生動態更新時，由特征子集所誘導的相容關系和由決策特征所誘導的等價關系會隨之變化，進而使得特征度量準則條件熵發生變化。下面，首先分析一組對象的特征值發生更新時相容類和決策類的變化情況。由于條件熵的計算與相容類和決策類中的對象順序無關，為了方便闡述，下文中假設決策系統中發生特征值修改的對象集合為 {xi|i=p+1,p+2,···,q}，則更新后不完備決策系統中相容類的更新為

U/T′(P)={T′P(xi)|i=1,2,···,p,p+1,···,q,q+1,···,k,k+1,···,n}

通過分析不完備決策系統中相容類和決策類，以及其交集的動態更新模式，可得特征值發生修改時決策特征d關于任意條件特征子集P的條件熵的增量計算機制為

其中 Δ 的值如下所示：

基于上述分析，算法1給出了不完備決策系統中特征值更新時基于條件熵的增量式特征選擇算法來計算新的特征子集。

算法1 不完備決策系統中基于條件熵的增量式特征選擇算法(IFS-CE-IDS)

輸入 不完備決策系統 I DS=(U,C∪g0gggggg,V,f)，原始數據U上的特征子集 R ED∈C，以及數據中發生修改對象的集合 ΔU；

輸出 特征選擇后的特征子集A。

1)初始化特征子集A=RED；

6)對任意特征a∈A計算 s ig(a,A,d),如果sig(a,A,d)=0 ，則A=A?{a}；

7)返回A。

該算法中條件熵的計算時間是O(|C||U||ΔU|)，在算法IFS-CE-IDS中，步驟1)～3)的計算時間是O(|C||U||ΔU|)，步驟5)的向特征集A中添加特征的計算時間為O(|C|2|U||ΔU|)，步驟6)中刪除掉冗余特征的時間復雜度為O(|A||C||U||ΔU|)。因此，算法IFS-CE-IDS總的時間復雜度為O(|C||U||ΔU|+|C|2|U||ΔU|+|A||C||U||ΔU|)=O(|C|2|U||ΔU|)。

3 實驗及分析

本文選取了9組UCI數據集進行性能測試，數據集詳細信息如表1所示。對于完備數據集Car和kr-vs-kp，隨機刪除原始數據集中5%的已知特征值變為缺失值，使原始完備數據集變為不完備數據集。對含有數值型數據的數據集Hepatitis、Wisconsin、Dermatology和Ozone，將數值型特征進行了離散化處理。如數據集Hepatitis包含19個特征，其中6個為數值型特征；數據集Wisconsin含有1個數值型特征；數據集Dermatology包含1個數值型特征；數據集Ozone都是數值型特征。實驗環境配置為：Intel(R)Core(TM)i5-4210M CPU 2.60 GHz，8 GB內存，操作系統為Windows 10，程序開發平臺為IntelliJ IDEA，編程語言為Java。

表1 數據集描述Table 1 Description of the datasets

為驗證本文所提出算法IFS-CE-IDS處理數據集特征值更新問題具有高效性和可行性，使用傳統批量式特征選擇算法HFS-CE-IDS與算法IFS-CE-IDS在9組UCI數據集上進行測試，從分類精度、決策性能以及計算效率三方面對傳統批量式特征選擇算法HFS-CE-IDS和IFS-CE-IDS進行比較。

3.1 分類精度分析

為比較算法HFS-CE-IDS與算法IFS-CEIDS所得特征子集的分類精度，對表1中9組數據集選擇其中50%對象，并且更新其特征值，然后分別運行傳統批量式算法HFS-CE-IDS和增量式算法IFS-CE-IDS對特征值更新數據集進行特征選擇。使用決策樹J48、Na?ve Bayes、SVM(support vector machines)分類器驗證這兩種算法的分類性能。實驗結果如表2～4所示。

表2 J48分類精度比較Table 2 J48 classification accuracy comparison %

見表2，從兩種算法在J48分類器的分類精度比較可知，算法IFS-CE-IDS在數據集Hepatitis、Audiology和Soybean上所得的分類精度相較算法HFS-CE-IDS所得分類精度差一些，而在其他6個數據集上算法IFS-CE-IDS所得分類精度與算法HFS-CE-IDS所得分類精度相同甚至更好。從表3可知，在Na?ve Bayes分類器中，算法IFS-CEIDS在9個數據集上的分類精度結果表明新提出算法在大部分數據集上的分類精度不比算法HFS-CE-IDS的分類精度差，例如在數據集Cancer、Car和kr-vs-kp上兩種算法的分類精度基本相同。

表3 Na?ve Bayes分類精度比較Table 3 Na?ve Bayes classification accuracy comparison%

從表4可知，在SVM分類器中，與算法HFSCE-IDS相比，新提出算法的分類精度在Hepatitis、Audiology、Cancer、Soybean、Dermatology、Wisconsin、Car、Ozone、kr-vs-kp等7個數據集上相等甚至更好。

表4 SVM分類精度比較Table 4 SVM classification accuracy comparison %

實驗結果表明，算法IFS-CE-IDS在大部分數據集上能夠在特征子集和分類精度上取得和算法HFS-CE-IDS相接近的，甚至更好的結果，可以證明算法IFS-CE-IDS是一種有效的特征選擇算法。

3.2 決策性能分析

為檢驗算法IFS-CE-IDS的決策性能，本文使用文獻[28]中對不完備數據進行評估所提出的6種評估函數評估算法HFS-CE-IDS以及算法IFS-CE-IDS計算的特征子集的決策性能。

6種評估函數中，特征集合C下不完備決策系統 I DS=(U,C∪g0gggggg,V,f) 近似準確評估函數定義為

式中：Ni是在不完備決策表中由最大一致塊Xi所誘導得到決策類數目，且 μ (Zij)=|Xi∩Dj|/|Xi|。

不完備決策系統 I DS=(U,C∪g0gggggg,V,f) 在RULE={Zij|Zij:des(Xi)→des(Dj),Xi∈MCC,Dj∈MCd}下的支持度量 γ 評估函數定義為

式中Nj是條件部分關于Dj的最大一致塊數。

不完備決策系統 IDS=(U,C∪g0gggggg,V,f) 在RULE={Zij|Zij:des(Xi)→des(Dj),Xi∈MCC,Dj∈MCd}下的覆蓋度量 ? 評估函數定義為

選擇表1中每組數據集中50%數據對象，更新其特征值，然后分別運行算法HFS-CE-IDS和算法IFS-CE-IDS對特征值更新數據集進行特征選擇。并且使用上述6種評估函數評估每組數據集更新后兩種算法特征選擇的特征子集的決策性能，實驗結果如表5所示。

表5 HFS-CE-IDS與IFS-CE-IDS的度量比較Table 5 Measurement comparison of HFS-CE-IDS with IFS-CE-IDS

從表5的實驗結果可知，算法IFS-CE-IDS與算法HFS-CE-IDS相比，在近似準確評估aC、一致性度量評估cC以及覆蓋度量評估 ? 這3種評估函數下的評估值是相同的；在數據集Soybean上，算法IFS-CE-IDS與算法HFS-CE-IDS在確定性度量 α 評估函數以及一致性度量 β 評估函數下的評估值不相同，而在其他8個數據集上兩種算法的確定性度量 α 評估函數以及一致性度量 β 評估函數的評估值是相同的；在支持度量 γ 評估函數所得評估值結果中，兩種算法在Cancer、Dermatology、Wisconsin、Car、Ozone、kr-vs-kp這6個數據集上的評估值相同，雖然在其余3個數據集上的評價值不同，但是評估值十分接近。

結合兩種算法在6種評估函數下的結果，表明算法IFS-CE-IDS在大部分數據集下能夠取得與算法HFS-CE-IDS相同的決策性能。

3.3 效率分析

為驗證本文提出的增量式特征選擇算法IFSCE-IDS的高效性，采用傳統的批量式特征選擇算法HFS-CE-IDS作比較，該算法是一種與所提出算法基于相同特征評估準則的非增量方法。對表1中的每組數據集，依次選擇其中的5%, 10%,15%, ···, 50%數據對象并更新其對象特征值。同時發生變化的特征值取決于對象特征的值域。當有不同規模的數據對象特征值發生更新，分別使用增量式特征選擇算法IFS-CE-IDS和傳統批量式特征選擇算法HFS-CE-IDS對數據集進行特征選擇，求解特征選擇結果。計算時間的比較結果如圖1所示，圖中詳細給出兩種算法計算時間隨數據對象特征值更新規模的變化而發生的變化。

圖1 算法HFS-CE-IDS與算法IFS-CE-IDS計算時間比較Fig.1 Computational time comparison between HFS-CE-IDS and IFS-CE-IDS

從圖1可知，當不同規模的數據對象特征值發生更新后，傳統批量式特征選擇算法HFS-CEIDS比增量式特征選擇算法IFS-CE-IDS花費更多時間來選擇特征值更新后的特征子集，主要的原因是增量式算法IFS-CE-IDS能夠避免重復的計算，可以利用之前已有的計算結果，從而使得特征選擇的計算效率得以提高。算法IFS-CEIDS在9組數據集上的計算效率普遍比算法HFSCE-IDS高，尤其是在一些數據規模較大的數據集上，算法IFS-CE-IDS的高效性更加明顯。比如在Ozone數據集上算法IFS-CE-IDS的計算效率遠優于算法HFS-CE-IDS的計算效率。圖1中兩種特征選擇算法的計算時間都存在一些波動，如數據集Ozone中對象數據對象特征值更新20%時，算法HFS-CE-IDS的計算時間突然變得比其他比例耗時更大，因為數據集的數值對象特征值發生更新后，它的相容類與決策類因數據對象特征更新而產生變化，從而導致計算時間發生波動。

在實驗分析中，通過算法HFS-CE-IDS與算法IFS-CE-IDS的分類精度、決策性能和計算效率三部分實驗結果可知，算法IFS-CE-IDS與算法HFS-CE-IDS相比，在大部分數據集上進行特征選擇所得特征子集數量相接近，兩種算法分類精度和決策性能基本相同，但算法IFS-CE-IDS的計算時間小于算法HFS-CE-IDS，尤其在數據規模較大的數據集上計算時間的優勢更加明顯。通過本節分類精度、決策性能和計算效率三部分實驗分析，證明IFS-CE-IDS是一種高效的處理數據對象特征值更新問題的增量式特征選擇算法。

4 結束語

本文提出了不完備決策系統中面向特征值動態更新的增量式特征選擇算法。通過分析不完備決策系統中條件特征值和決策特征值同時更新時相容類和決策類的動態更新模式，構造了條件信息熵的增量計算機制，并進一步設計了一種基于動態不完備決策系統的增量式特征選擇算法。實驗選取了9組UCI公共數據集，并通過分類精度、決策性能以及計算效率3個方面與傳統批量式特征選擇算法進行了性能對比。實驗結果表明，本文算法所選擇的特征子集與批量式算法在分類精度和決策性能具有基本一致的性能表現。同時，在面對不完備數據中特征值的動態變化環境下，本文算法的計算效率遠優于傳統批量式算法，可在較短時間內計算出一個可行的特征子集。實驗中部分數據集使用算法IFS-CE-IDS需要進行特征轉化，導致失去部分有效信息，降低算法結果質量，未來將致力于尋求更有效處理混合數據的增量特征算法。