基于優化決策樹和EM的缺失數據填充算法*

梁秉毅 蔡延光 蔡顥 戚遠航 黃何列 Ole Hejlesen

?

基于優化決策樹和EM的缺失數據填充算法*

梁秉毅1蔡延光2蔡顥2戚遠航2黃何列2Ole Hejlesen3

（1.廣州市第三公共汽車公司 2.廣東工業大學自動化學院 3.奧爾堡大學健康科學與工程系）

針對大數據管理與應用中數據缺失的問題，提出一種基于優化決策樹和EM的缺失數據填充算法對多屬性缺失數值型數據進行填充。為解決決策樹過分擬合問題，該算法采用基于精英策略的自適應遺傳算法優化后的決策樹對數據進行分類，再結合EM算法實現數值型數據的填充。仿真結果表明：對比優化前的決策樹算法，優化后的決策樹分類精度更高，平均填充耗時更少。

數據填充；決策樹；EM算法；遺傳算法

0　引言

數據缺失是數據管理中經常面臨的問題，含有缺失數據的多變量數據無法在絕大多數的統計模型中直接分析。當數據庫中出現缺失數據時，一般采用數據刪除或數據填充的方法。如果缺失數據較少，可直接刪除有缺失的記錄，但缺失數據較多時，刪除大量數據會給研究結果帶來一定的誤差。因此，數據填充是當前解決數據缺失的主要方法。

近年來，許多學者在數據填充領域進行了深入的研究。李宏等提出一種基于貝葉斯網絡和期望最大值法的缺失數據填充算法[1]；武森等提出不完備數據聚類的缺失數據填補方法，并以不完備數據聚類的結果為基礎進行缺失數據的填補[2]；張嬋提出一種基于支持向量機和回歸填充法的缺失數據填充算法[3]；袁景凌等提出一種基于完備相容類的不完備大數據填補算法、一種基于離散弱相關的決策森林并行分類算法和一種增量更新決策森林的算法[4]；李忠波等提出一種新的樸素貝葉斯分類器進行數據填充[5]；Amiri M采用模糊粗糙集進行數據填充[6]；Turrado C C提出一種混合算法解決數據填充問題，并把該算法應用在相關的電力數據中[7]。但這些數據填充算法普遍存在分類精度低、填充耗時長等問題。

因此，本文提出了一種基于優化決策樹和EM的缺失數據填充算法，以基于精英策略的自適應遺傳算法優化后的決策樹和EM算法相結合的方式，解決多屬性數值型數據缺失的問題，提高數據填充精度和降低數據填充耗時。

1　優化決策樹

1.1　決策樹

決策樹算法是一種典型的分類算法，構建決策樹的思想與貪婪算法類似，采用自頂向下遞歸的方式[8]。先對原始數據進行處理，得出觀察樣本；再從訓練集和它們相關聯的類標號生成可讀的規則和決策樹。隨著樹的構建，訓練集遞歸地劃分成較小的子集。決策樹構建分為5個步驟。

步驟1：采集組數據，作為建立決策樹分類器的訓練數據集。

步驟2：所有記錄看作一個結點，代表訓練樣本的單個結點開始。

步驟3：遍歷每個變量的每一種分割方式，找到最好的分割點。如果樣本都在同一個類，則該結點成為樹葉，并用該類標記；否則算法選擇最有分類能力的屬性作為決策樹的當前結點。在每次需要分裂時，計算訓練元組每個屬性的增益率gain，然后選擇增益率最大的屬性進行分裂。

訓練元組按屬性進行劃分信息增益gain()具體描述為

其中，為訓練元組的信息量；D為第個類別分類的信息量；p為第個類別在分類元組D中出現的概率；p為第個類別在訓練元組中出現的概率。

步驟4：分割成2個結點1和2。

步驟5：如果滿足停止條件（剩余訓練數據不可以用來進一步劃分屬性），決策樹停止分類；否則轉步驟3。

1.2　決策樹的剪枝優化

在決策樹構建時，決策樹反映的是訓練數據中的分類，而訓練數據與真實情況是有一定差距的，不一定能真實反映數據的分類，可能出現過度擬合的問題。過度擬合會導致決策樹分類精度不高，決策時間變長等情況。因此，本文對由訓練數據生成的決策樹進行剪枝，剪掉不可靠的分支之后，決策樹變得更小、更簡單，不僅可以提高分類精度，還可以縮短分類決策時間。本文采用后剪枝的方式對決策樹進行修剪。

后剪枝的基本思想是建立測試數據集，對決策樹采取統計度量的方式把最不可靠的分支剪掉，通過刪除決策樹的分支，用樹葉代替修剪后的子樹，類標號為子樹中最頻繁的類標記[8]。一般情況下，測試集的異常值影響決策樹評估的結果，需要先對異常數據進行隔離，保留測試集有用的部分。決策樹后剪枝方法的基本步驟如下：

步驟1：設訓練集生成的決策樹表示為，建立測試集以評估決策樹的分類效果，建立評價分類效果的標準；

步驟2：用測試集中的觀察集對決策樹進行測試，評估決策樹的性能，得出分類情況，并以此評估原決策樹的錯誤率；

步驟3：將影響決策樹質量的分支予以修剪，并用子葉代替。

1.3 決策樹的染色體編碼

遺傳算法是一種基于生物進化的參數優化算法，基本思想是先對優化對象進行二進制編碼，然后經過一系列的選擇、交叉和變異操作，在滿足適應度函數的條件或達到最大迭代次數后，獲得近似的最優解[9]。從結構上看，決策樹包含若干結點，結點與結點之間由樹枝連接，可以利用決策樹這種獨特的結構進行二進制編碼。結合遺傳算法的特點，對決策樹進行剪枝優化操作，以降低決策樹的規模。

決策樹包含若干個結點，樣例決策樹示意圖如圖1所示。所有結點按照自頂向下、先左后右的方式進行編號，編號為A，B，C，D，…，如此類推；然后對結點賦予二進制數值，數值1表示結點存在，數值0表示結點不存在；最后二進制編碼按結點編號排列。圖1中5號分支將被裁剪，即E結點和F結點之間的分支消失，在二進制編碼中表示F結點不存在。

圖1　樣例決策樹示意圖

樣例決策樹共有6條分支，初始樣例決策樹的染色體二進制編碼可以表示為1111111。5號分支被裁剪后，樣例決策樹的染色體二進制編碼將變為1111101。樣例決策樹修剪前和修剪后的染色體數值變化如表1所示。

表1　樣例決策樹修剪前后的染色體數值變化表

1.4 適應度函數

為在優化后的決策樹集合里挑選出最優決策樹作為缺失數據的分類器，需要建立衡量決策樹性能的標準。考慮到建立決策樹的目的是對缺失數據進行屬性分類，本文采用決策樹的分類精度作為衡量決策樹性能的指標。

1.5　交叉運算和變異運算

為使遺傳個體得到更好的優化，提高個體的適應度，可以用交叉和變異的方式進行染色體編碼的改造。本文主要采用交叉和變異2種遺傳運算產生后繼染色體。

1）交叉運算

交叉運算后的染色體具體描述為

2）變異運算

變異運算是對染色體中任意的一位編碼進行取反，實現染色體的變異。

1.6　自適應策略

交叉和變異操作的概率會影響遺傳算法執行的過程，交叉率P和變異率P過小或過大都會影響收斂速度。遺傳參數自適應策略的基本思想是：對于適應度低于平均水平的種群，加強交叉和變異操作，加快適應度低的種群完成進化速度；對于適應度高的種群，適當減少交叉和變異操作，以保留較優的種群。通過式(5)自動改變遺傳算法的交叉率P，通過式(6)實現自動改變遺傳算法的變異率P。

1.7　遺傳算法的精英策略

種群的交叉、變異操作具有不確定性，經過交叉和變異的子代種群的優劣是未知的，如果父代種群中的優良個體也執行交叉操作，最優個體可能會被替換，因此出現了精英策略[9-11]。精英策略的基本思想是每次迭代的過程中，從父種群中挑選最優個體添加到子代種群或替換掉子代種群的最差個體，因為交叉變異的結果是未知的，而父種群中的最優個體是確定的，這樣能保證子代種群的高適應度，避免進化過程中最優解變異丟失。

1.8　優化決策樹的算法步驟

優化決策樹的算法步驟如下：

步驟1：采集組數據，作為對決策樹分類器進行剪枝操作的測試數據集；

步驟2：設定控制參數、定義適應度函數等；

步驟2-1：設定控制參數，群體規模、最大迭代次數max；

步驟2-2：變量聲明，當前迭代次數、交叉概率P、變異概率P；

步驟2-3：染色體編碼；

步驟2-4：計算交叉概率P、變異概率P，計算方法如式(5)和式(6)；

步驟2-5：定義適應度函數(H)，其中H為生成個決策樹的編號（=1，2，…，），適應度函數計算如式(2)；

步驟3：初始化，令=0且隨機生成個決策樹H；

步驟4：形成種群，對每一個決策樹H，計算適應度(H)；

步驟5：選擇適應度最高的染色體加入新種群P；

步驟6：其余的染色體進行交叉和變異操作；

步驟7：生成種群′，計算所有新決策樹的適應度(H)；

步驟8：′淘汰最小適應度的決策樹，加入來自步驟5的決策樹，形成新種群P；

步驟9：令種群P=P；

步驟10：當=max，轉步驟11；否則轉步驟4；

步驟11：適應度最高的決策樹為最優的決策樹。

2　EM算法

本文采用數據樣本總體平均值填充缺失數據。缺失數值型數據所在集合的數據作為填充數據的參考樣本。數據按照時間順序排列，數據表示為{1，2，…，X}，是按時間排列的序號且為正整數。數據總體分為觀察數據和缺失數據，觀察數據是實際存在的數值，觀察數據集合為obs= {1，2，…，X}，缺失數據集合為miss= {X1，X2，…，X}，是按時間排列的序號且為正整數，。

EM算法[12]步驟如下：

步驟1：變量聲明，當前迭代次數（為正整數）、收斂參數（為正數）、迭代次時評價參量(k)，最大期望值(fillobs，(k))、預測值fill；

步驟3：執行最大期望步（E步），計算方法如式(7)所示；

其中，(fillobs，(k))為迭代第次時填充數據期望值；(k)、(k?1)分別為迭代第次、第?1次的評價參量；

步驟4：執行最大化步（M步），計算方式如式(8)所示；

其中，(k)、(k?1)分別為迭代第次、第?1次的評價參量；X為觀察數據，obs= {1，2，…，X}；

步驟5：判斷是否滿足收斂條件，若是轉步驟6；否則=+1，轉步驟3，計算方式如式(9)所示；

其中為收斂參數；

步驟6：輸出預測值fill，并使用該值作為對本數據集所有缺失數據的填充值，計算方式如式(10)所示。

3　基于優化決策樹和EM的缺失數據填充算法

基于優化決策樹和EM的缺失數據填充算法步驟：

步驟1：采用最優的決策樹對缺失數據進行分類，得到若干分類集合；

步驟2：EM算法初始化，以缺失數值型數據所在集合的數據作為填充數據的參考樣本；

步驟3：執行EM算法，完成數據填充。

4　實驗與分析

4.1　實驗環境與參數設置

本次實驗的CPU為Intel Core i3 3.40 GHz，內存為4 GB，操作系統為Window7 32位，開發環境為MATLAB R2013a。相關算法的參數設置如表2所示。

表2　算法的參數設置

4.2　實驗結果與分析

4.2.1優化決策樹的分類精度測試

為驗證算法準確性，本文采用車載健康監測設備的30000條數據作為原始數據，包括心率、血壓和體溫等數值型數據，且所有數據都是同一人在同一環境下連續獲取。原始數據生成的決策樹分類精度為82.8%。在測試樣本數分別為400，600，800，1000，1200時，采用相同的測試樣本，分別用遺傳算法和改進遺傳算法對決策樹進行優化操作。每個算法運行5次，選取分類精度最好的決策樹進行對比。實驗結果如表3、圖2所示。

表3　原始決策樹、遺傳算法的優化決策樹和改進遺傳算法的優化決策樹的分類精度測試結果

圖2　2種優化決策樹算法的分類精度對比圖

由表3、圖2可知，由于剪去了不可靠的分支，優化后的決策樹分類精度明顯提高。從測試樣本方面看，參與決策樹剪枝的測試樣本越大，決策樹的分類精度越高，剪枝效果越好。從分類精度方面看，改進遺傳算法的優化決策樹分類效果優于遺傳算法的優化決策樹。這是因為改進遺傳算法在運行過程中對較優個體進行保留操作或者減少交叉變異操作，提高了決策樹的適應度。

4.2.2填充算法的耗時對比

從原始數據集中隨機抽取5組樣本數據個數為3000的樣本作為數據測試集。每組測試集隨機刪除若干個數據，生成4個不同的數據測試集，缺失數據個數分別為200，400，600，800。對每個數據集分別用基于原始決策樹和EM的缺失數據填充算法、基于優化決策樹和EM的缺失數據填充算法填充缺失數據。5組實驗數據完成后，得出每個數據測試集的缺失數據填充時間，按缺失數據個數求出平均值。實驗結果如表4、圖3所示。

表4　基于原始決策樹和EM的缺失數據填充算法、基于優 化決策樹和EM的缺失數據填充算法的耗時對比

由表4、圖3可知，缺失數據填充的平均耗時與缺失數據個數增加基本呈正相關的關系，缺失數據個數越多，填充數據平均耗時越長。通過對比優化前后的決策樹對填充缺失數據過程平均耗時可知，優化后缺失數據填充算法的平均耗時減少了。這是因為決策樹分支數減少，縮短了決策樹分類器對缺失數據分類的時間。

圖3　2種缺失數據填充算法平均耗時對比圖

5　結論

本文提出了一種基于優化決策樹和EM的缺失數據填充算法。該算法主要基于精英策略的自適應遺傳算法對決策樹進行優化，克服了決策樹的過分擬合問題，然后結合優化后的決策樹和EM算法，實現多屬性數值型數據的分類和填充。本文采用車載健康監測設備采集的數據作為原始數據進行仿真，結果表明，相對于優化前的決策樹算法，優化后的決策樹分類精度更高，所提出算法的平均填充耗時更少。該算法具有較高的實用價值，可以有效解決多屬性數值型數據缺失問題。

[1] 李宏,阿瑪尼,李平,等.基于EM和貝葉斯網絡的丟失數據填充算法[J].計算機工程與應用,2010,46(5):123-125.

[2] 武森,馮小東,單志廣.基于不完備數據聚類的缺失數據填補方法[J].計算機學報,2012,35(8):1726-1738.

[3] 張嬋.一種基于支持向量機的缺失值填補算法[J].計算機應用與軟件,2013,30(5):226-228.

[4] 袁景凌,鐘珞,楊光,等.綠色數據中心不完備能耗大數據填補及分類算法研究[J].計算機學報,2015,38(12):2499-2516.

[5] 李忠波,楊建華,劉文琦.基于數據填補和連續屬性的樸素貝葉斯算法[J].計算機工程與應用,2016,52(1):133-140.

[6] Amiri M, Jensen R. Missing data imputation using fuzzy-rough methods[J]. Neurocomputing, 2016, 205:152-164.

[7] Turrado C C, Sánchez L F, Calvorollé J L, et al. A hybrid algorithm for missing data imputation and its application to electrical data loggers[J]. Sensors, 2016, 16(9):1467.

[8] Dong Y J, Liu T Z. Parameter optimization based on genetic algorithm in the research of equivalent pruning effect on fuzzy decision tree[J]. Advanced Materials Research, 2013, 756-759: 3809-3813.

[9] 劉全,王曉燕,傅啟明,等.雙精英協同進化遺傳算法[J].軟件學報,2012,23(4):765-775.

[10] Leno I J, Sankar S S, Ponnambalam S G. MIP model and elitist strategy hybrid GA–SA algorithm for layout design[J]. Journal of Intelligent Manufacturing, 2015:1-19.

[11] Tretyakova A, Seredynski F. A novel genetic algorithm with asexual reproduction for the maximum lifetime coverage problem in wireless sensor networks[C]. The Third International Conference on Advanced Communications and Computation, 2013: 87-93.

[12] Lin T H. A comparison of multiple imputation with EM algorithm and MCMC method for quality of life missing data[J]. Quality & Quantity, 2010, 44(2):277-287.

Missing Data Imputation Algorithm Based on Optimal Decision Tree and EM

Liang Bingyi1Cai Yanguang2Cai Hao2Qi Yuanhang2Huang Helie2Ole Hejlesen3

(1. Guangzhou No.3 Bus Company 2. School of Automation, Guangdong University of Technology 3. Department of Health Science & Technology, Aalborg University)

Focusing on the problem of missing data in large data management and application, a missing data imputation algorithm based on an optimal Decision Tree and EM is proposed to fill the tmultiple attributed missing numeric data. In order to solve excessive fitting problem of Decision Tree, the proposed algorithm adopts an optimal Decision Tree which is optimized by an adaptive genetic algorithm based on elitist strategy to classify the data, and combines with the EM to fill the numeric data. The simulation results show that: comparing with Decision Tree algorithm without optimization, the classification accuracy of the optimal Decision Tree is better and the proposed algorithm need less time to fill data.

Data Imputation; Decision Tree; Expectation Maximization Algorithm; Genetic Algorithm

梁秉毅，男，1991年生，碩士，研究方向：計算機技術與應用。E-mail: byleuang@foxmail.com

蔡延光，男，1963年生，博士，教授，博導，主要研究方向：網絡控制與優化、組合優化、智能優化、智能交通系統等。

國家自然科學基金（61074147）；廣東省自然科學基金（S2011010005059）；廣東省教育部產學研結合項目（2012B091000171，2011B090400460）；廣東省科技計劃項目（2012B050600028，2014B010118004，2016A050502060）；廣州市花都區科技計劃項目（HD14ZD001）；廣州市科技計劃項目（201605121347368）。