基于優(yōu)化決策樹和EM的缺失數(shù)據(jù)填充算法*

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

?

基于優(yōu)化決策樹和EM的缺失數(shù)據(jù)填充算法*

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

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

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

數(shù)據(jù)填充；決策樹；EM算法；遺傳算法

0　引言

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

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

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

1　優(yōu)化決策樹

1.1　決策樹

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

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

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

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

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

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

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

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

1.2　決策樹的剪枝優(yōu)化

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

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

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

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

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

1.3 決策樹的染色體編碼

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

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

圖1　樣例決策樹示意圖

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

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

1.4 適應度函數(shù)

為在優(yōu)化后的決策樹集合里挑選出最優(yōu)決策樹作為缺失數(shù)據(jù)的分類器，需要建立衡量決策樹性能的標準?？紤]到建立決策樹的目的是對缺失數(shù)據(jù)進行屬性分類，本文采用決策樹的分類精度作為衡量決策樹性能的指標。

1.5　交叉運算和變異運算

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

1）交叉運算

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

2）變異運算

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

1.6　自適應策略

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

1.7　遺傳算法的精英策略

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

1.8　優(yōu)化決策樹的算法步驟

優(yōu)化決策樹的算法步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟9：令種群P=P；

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

步驟11：適應度最高的決策樹為最優(yōu)的決策樹。

2　EM算法

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

EM算法[12]步驟如下：

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

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

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

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

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

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

其中為收斂參數(shù)；

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

3　基于優(yōu)化決策樹和EM的缺失數(shù)據(jù)填充算法

基于優(yōu)化決策樹和EM的缺失數(shù)據(jù)填充算法步驟：

步驟1：采用最優(yōu)的決策樹對缺失數(shù)據(jù)進行分類，得到若干分類集合；

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

步驟3：執(zhí)行EM算法，完成數(shù)據(jù)填充。

4　實驗與分析

4.1　實驗環(huán)境與參數(shù)設置

本次實驗的CPU為Intel Core i3 3.40 GHz，內存為4 GB，操作系統(tǒng)為Window7 32位，開發(fā)環(huán)境為MATLAB R2013a。相關算法的參數(shù)設置如表2所示。

表2　算法的參數(shù)設置

4.2　實驗結果與分析

4.2.1優(yōu)化決策樹的分類精度測試

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

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

圖2　2種優(yōu)化決策樹算法的分類精度對比圖

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

4.2.2填充算法的耗時對比

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

表4　基于原始決策樹和EM的缺失數(shù)據(jù)填充算法、基于優(yōu) 化決策樹和EM的缺失數(shù)據(jù)填充算法的耗時對比

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

圖3　2種缺失數(shù)據(jù)填充算法平均耗時對比圖

5　結論

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

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

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

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

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

[5] 李忠波,楊建華,劉文琦.基于數(shù)據(jù)填補和連續(xù)屬性的樸素貝葉斯算法[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] 劉全,王曉燕,傅啟明,等.雙精英協(xié)同進化遺傳算法[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年生，博士，教授，博導，主要研究方向：網(wǎng)絡控制與優(yōu)化、組合優(yōu)化、智能優(yōu)化、智能交通系統(tǒng)等。

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