基于优化决策树和EM的缺失数据填充算法.pdf

信息技术 2017 年 第 38 卷 第 5 期 自动化与信息工程 37 * 基金项目：国家自然科学基金（61074147）；广东省自然科学基金 （S2011010005059）；广东省教育部产学研结合项目（2012B091000171， 2011B090400460 ） ； 广 东 省 科 技 计 划 项 目 （ 2012B050600028 ， 2014B010118004，2016A050502060）；广州市花都区科技计划项目 （HD14ZD001）；广州市科技计划项目（201605121347368）。 基于优化决策树和 EM 的缺失数据填充算法 * 梁秉毅 1 蔡延光2 蔡颢2 戚远航2 黄何列2 Ole 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：采集 i 组数据，作为建立决策树分类器 的训练数据集。 步骤 2：所有记录看作一个结点，代表训练样本 的单个结点开始。 步骤 3：遍历每个变量的每一种分割方式，找到 最好的分割点。如果样本都在同一个类，则该结点成 为树叶，并用该类标记；否则算法选择最有分类能力 的属性作为决策树的当前结点。在每次需要分裂时， 计算训练元组每个属性的增益率gain，然后选择增益 率最大的属性进行分裂。 训练元组D 按属性A 进行划分信息增益gain(A) 万方数据 38 具体描述为 gain(A)()() i m i iAi m i Ai n i i pppp D D = -= 1 2 1 2 1 loglog (1) 其中，D 为训练元组的信息量；Di为第 i 个类别分类 的信息量； pAi为第i 个类别在分类元组Di中出现的概 率；pi为第 i 个类别在训练元组D 中出现的概率。 步骤4：分割成2 个结点N1和N2。 步骤 5：如果满足停止条件（剩余训练数据不可 以用来进一步划分属性），决策树停止分类；否则转 步骤3。 1.2 决策树的剪枝优化 在决策树构建时， 决策树反映的是训练数据中的 分类，而训练数据与真实情况是有一定差距的，不一 定能真实反映数据的分类，可能出现过度拟合的问 题。过度拟合会导致决策树分类精度不高，决策时间 变长等情况。因此，本文对由训练数据生成的决策树 进行剪枝， 剪掉不可靠的分支之后， 决策树变得更小、 更简单，不仅可以提高分类精度，还可以缩短分类决 策时间。本文采用后剪枝的方式对决策树进行修剪。 后剪枝的基本思想是建立测试数据集， 对决策树 采取统计度量的方式把最不可靠的分支剪掉， 通过删 除决策树的分支，用树叶代替修剪后的子树，类标号 为子树中最频繁的类标记 8。一般情况下，测试集的 异常值影响决策树评估的结果， 需要先对异常数据进 行隔离，保留测试集有用的部分。决策树后剪枝方法 的基本步骤如下： 步骤1：设训练集生成的决策树表示为M，建立 测试集以评估决策树的分类效果， 建立评价分类效果 的标准； 步骤2： 用测试集中的观察集对决策树M 进行测 试，评估决策树的性能，得出分类情况，并以此评估 原决策树的错误率； 步骤 3：将影响决策树质量的分支予以修剪，并 用子叶代替。 1.3 决策树的染色体编码 遗传算法是一种基于生物进化的参数优化算法， 基本思想是先对优化对象进行二进制编码， 然后经过 一系列的选择、交叉和变异操作，在满足适应度函数 的条件或达到最大迭代次数后，获得近似的最优 解 9。从结构上看，决策树包含若干结点，结点与结 点之间由树枝连接， 可以利用决策树这种独特的结构 进行二进制编码。结合遗传算法的特点，对决策树进 行剪枝优化操作，以降低决策树的规模。 决策树包含若干个结点， 样例决策树示意图如图 1 所示。所有结点按照自顶向下、先左后右的方式进 行编号，编号为A，B，C，D，如此类推；然后 对结点赋予二进制数值，数值1 表示结点存在，数值 0 表示结点不存在； 最后二进制编码按结点编号排列。 图1 中5 号分支将被裁剪， 即E 结点和 F 结点之间的 分支消失，在二进制编码中表示F 结点不存在。 图 1 样例决策树示意图 样例决策树共有6 条分支， 初始样例决策树的染 色体二进制编码可以表示为 1111111。5 号分支被裁 剪后，样例决策树的染色体二进制编码将变为 1111101。样例决策树修剪前和修剪后的染色体数值 变化如表1 所示。 表 1 样例决策树修剪前后的染色体数值变化表 结点序号 A B C D E F G 修剪前的编码 1 1 1 1 1 1 1 修剪后的编码 1 1 1 1 1 0 1 A B E C D F G 1 2 3 4 5 6 万方数据 梁秉毅 蔡延光 蔡颢 戚远航 黄何列 Ole Hejlesen：基于优化决策树和 EM 的缺失数据填充算法 2017 年 第 38 卷 第 5 期 自动化与信息工程 39 1.4 适应度函数 为在优化后的决策树集合里挑选出最优决策树 作为缺失数据的分类器， 需要建立衡量决策树性能的 标准。 考虑到建立决策树的目的是对缺失数据进行属 性分类， 本文采用决策树的分类精度作为衡量决策树 性能的指标。 决策树的分类精度是指从训练集训练出来的决 策树，经过另外的测试集合的验证，计算出分类的准 确率。分类精度是决策树 M 正确分类的测试用例总 数与测试用例总数的比值，比值越高，分类的效果越 好。适应度() n f H具体描述为 () i M n N f H N = (2) 其中，N 为测试数据集上的用例总数； i M N为决策树 i M正确分类测试用例总数。 1.5 交叉运算和变异运算 为使遗传个体得到更好的优化， 提高个体的适应 度，可以用交叉和变异的方式进行染色体编码的改 造。 本文主要采用交叉和变异2 种遗传运算产生后继 染色体。 1） 交叉运算 已知 1 a和 2 a是一对交叉运算前的染色体， 1 a和 2 a是交叉运算后的染色体，染色体长度为 l（l 为正 整数）。染色体 1 a根据染色体长度分为等长度的 2 部分 1first a和 1second a；染色体 2 a根据染色体长度分为 等长度的 2 部分 2first a和 2second a。交叉运算前的染色 体具体描述为 () () 11first1second 22first2second , , aaa aaa = = (3) 其中， 1first a表示 1 a的前半部分； 1second a表示 1 a的后 半部分； 2first a表示 2 a的前半部分； 2second a表示 2 a的 后半部分。 交叉运算后的染色体具体描述为 () () () () 11first1second1first2second 22first2second2first1second , , , , aaaaa aaaaa = = (4) 其中， 1first a 表示 1 a的前半部分； 1second a 表示 1 a的 后半部分； 2first a 表示 2 a的前半部分； 2second a 表示 2 a的后半部分。 2） 变异运算 变异运算是对染色体中任意的一位编码进行取 反，实现染色体的变异。 1.6 自适应策略 交叉和变异操作的概率会影响遗传算法执行的 过程，交叉率 Pc和变异率 Pm过小或过大都会影响收 敛速度。遗传参数自适应策略的基本思想是：对于适 应度低于平均水平的种群，加强交叉和变异操作，加 快适应度低的种群完成进化速度； 对于适应度高的种 群，适当减少交叉和变异操作，以保留较优的种群。 通过式(5)自动改变遗传算法的交叉率 Pc，通过式(6) 实现自动改变遗传算法的变异率Pm。 - - - = ffP ff ff ffPP P P c cc c c , , )( 1 max max21 1 (5) - - - = ffP ff ff ffPP P P m mm m m , , )( 1 max max21 1 (6) 其中，Pc1，Pc2，Pm1，Pm2为常数；fmax是当前染色 体最大的适应值；f是染色体的平均适应值；f 为当 前染色体的适应度。 1.7 遗传算法的精英策略 种群的交叉、变异操作具有不确定性，经过交叉 和变异的子代种群的优劣是未知的， 如果父代种群中 的优良个体也执行交叉操作，最优个体可能会被替 换，因此出现了精英策略 9-11。精英策略的基本思想 是每次迭代的过程中， 从父种群中挑选最优个体添加 到子代种群或替换掉子代种群的最差个体， 因为交叉 万方数据 40 变异的结果是未知的， 而父种群中的最优个体是确定 的，这样能保证子代种群的高适应度，避免进化过程 中最优解变异丢失。 1.8 优化决策树的算法步骤 优化决策树的算法步骤如下： 步骤 1：采集 j 组数据，作为对决策树分类器进 行剪枝操作的测试数据集； 步骤2：设定控制参数、定义适应度函数等； 步骤 2-1：设定控制参数，群体规模 N、最大迭 代次数Kmax； 步骤2-2：变量声明，当前迭代次数k、交叉概率 Pc、变异概率Pm； 步骤2-3：染色体编码； 步骤 2-4：计算交叉概率 Pc、变异概率 Pm，计 算方法如式(5)和式(6)； 步骤2-5：定义适应度函数 f (Hn)，其中Hn为生 成n 个决策树的编号（n = 1，2，N），适应度函 数计算如式(2)； 步骤3： 初始化， 令k = 0 且随机生成n 个决策树 Hn； 步骤4：形成种群P，对每一个决策树Hn，计算 适应度f (Hn)； 步骤 5：选择适应度最高的染色体加入新种群 PN； 步骤6：其余的染色体进行交叉和变异操作； 步骤7：生成种群P ，计算所有新决策树的