基于偏置采样的高速数据集成分类算法

© 2012年。由爱思唯尔公司出版信息工程研究院负责评选和同行评议可在www.sciencedirect.comwww.sciencedirect.com上在线获取IERI Procedia 3（2012）169 - 1742012年机械与电子工程国际会议基于偏置采样的郭庆军1、李翠正21江苏技术师范大学计算机工程学院2江苏技术师范学院教育学院摘要高速数据流是一种超过集成分类器处理能力的数据流速度，集成分类器训练无法覆盖所有最近的数据来更新分类模型。为此，本文介绍了最优贝叶斯分类器理论，并在此基础上分析了其对集成分类器期望偏差误差的方差分解，最后提出了一种基于采样偏差的高速数据流集成分类算法，理论分析和实验验证表明该算法能有效减少集成分类器训练更新的同时，分类保持高分类性能。© 2012由Elsevier B. V.出版由信息工程研究所负责选择和同行评审根据CC BY-NC-ND许可证开放访问。关键词：高速数据集成，分类，算法1. 介绍数据流分类算法能否成功地应用于实际应用中，需要多个客观因素，如计算机的存储容量和计算能力，足够的存储空间使数据能够连续地保存成流数据，快速的计算速度使每一个数据都能实现高速处理。然而，现有的计算机硬件技术无法满足这些需求。例如，两颗地球观测卫星每天有350 GB的数据;在石油化工行业，一个石油钻井平台平均每秒产生1 MB的数据，用来描述平台的工作。在这种情况下，处理器的计算能力无法处理每个新的单独分类器训练数据的到达，以更新集成分类器模型[1-4]。2212-6678 © 2012由Elsevier B. V.出版信息工程研究院负责评选和同行评议在CC BY-NC-ND许可下开放访问。doi：10.1016/j.ieri.2012.09.028170郭庆军和李翠正/ IERI Procedia 3（2012）169利用采样技术可以有效地减小训练数据集的规模，从而加快集成分类器训练的更新速度，但是不同的采样策略所获得的训练数据集生成的集成分类器，分类性能差异较大。虽然对样本不适当的融合可以提高分类器训练的更新速度，但会降低分类精度[5]，从而降低其价值。如图1所示，将不断流入的数据流分成多个大小相同的数据段，用表示，其中由最近流入的数据组成。每个数据段分为两部分，即数据段和采样数据集，数据段中未采样的数据集用于训练分类器，得到数据段。该算法的目的是从一个数据段中提取出最近的准则数据形式，利用最近的分类器进行训练，使得综合分类器在具有较小训练更新的同时，具有较高的分类精度。图1通过抽样训练的2. 基于集成分类图2显示了集成分类器，阴影区域表示数据集中的各个分类器是正确分类的数据集。对于任意一个数据，如果垂直阴影区域小于空白部分，则综合分类器为分类错误，因此继续训练个体分类器，动态增加被错误数据点的权重，使更多的“注意力”集中在被错误的子数据上，从而提高综合分类器的准确率。图2集成分类器对数据进行了正确分类郭庆军和李翠正/ IERI Procedia 3（2012）169171C在数据流样本中，它将被视为一种特殊的权重分配方法，被抽取的数据权值为1，未被抽取的数据权值为0，当抽取的数据概率越大，权值的可能性越大，新分类器训练出的个体“关注”数据的可能性越大。因此，与随机抽样方法相比，采用有偏抽样方法，动态集成分类器对提高数据抽取概率、提高分类器的误差预期“功不可没”，集成可以显著提高分类精度。3. 设置单个分类器方程（1）表明求解个体分类器是一个设定权值的优化问题，然而，本文研究的对象是高速数据流，无法应用类似于普通数据流的优化计算量大的求解方法来解决，因此本文[6]以正确的方式为个体分类器设定权值，并计算其权值如下：wp（c）（1p（c））2我的（1c x（一）它表示数据集类别的概率分布，表示当数据的真实类别标准太高时，各个分类器为该类别预测概率值。同时当数据发生概念漂移时，为了使集成分类器适应新的概念[7]。4. 模拟和结果分析本 节 通 过 CDSBS 加 权 融 合 算 法 和 随 机 样 本 分 类 算 法 （ Random Sampling Weighted ClassifiersEnsemination，RWECE）的对比实验，验证了分类算法的准确性和时间效率。实验数据集为超平面人工数据集和普查收入标准数据集。实验环境为windows XP操作系统，CPU奔腾IV3.0Ghz，内存512M，算法matlab7编写，个体分类器采用C4.5决策树算法。超平面数据集的实验参数设置如下：数据块大小、保持个体分类器个数、属性维数为5、采样率。图3是稳定时的概念算法和CDSBS RSWCE算法的准确率对比图.图4是两种算法在概念分类精度时的漂移率对比图。为了模拟概念漂移，数据生成器20在分离超平面生成的斜率中为每个数据块的数据变化生成数据。从图3可以看出，当训练数据概念稳定时，CDSBS算法的分类准确率高于RSWCE算法，但前5块的分类准确率相对较低，因为训练开始时包含在单个集成分类器中的分类器数量较少，集成分类器准确率较低，因此基于抽样偏差的算法不能准确计算抽样数据的概率，利用抽样数据建立新的分类不能更“关注”期望大数据的误差贡献，同时降低了样本偏差，因为新训练的个体分类器的准确率，使得包含下一轮个体分类器的综合分类器的准确率下降。随着数据段的增加，使用训练数据段的个体分类器数量不断增加，综合分类器的准确率不断提高，使得算法对样本数据的概率计算更加准确，虽然新训练的个体分类器由于样本偏差会导致分类准确率下降，但由于其更加“注意”，对期望误差数据贡献较大将提高集成分类器的准确性。172郭庆军和李翠正/ IERI Procedia 3（2012）169图3无概念漂移时两种算法分类精度对比图4存在概念漂移时两种算法的分类精度对比图4为训练数据发生概念漂移时两种算法的分类精度对比图从图4中可以看出，当数据流发生概念漂移时，两种算法仍然使用旧概念训练的综合分类器对新概念下产生的数据进行分类，必然导致分类精度大幅度下降。但是，这两种算法都可以在融合的时候删除旧分类概率训练的个体分类器，因此在漂移概念事件发生后RSWCE算法可以更快的达到CDSBS算法的分类精度。Census-income数据集来源于UCI公共数据集，共有48,842条记录，每条记录包括性别、年龄、婚姻状况和教育程度等14个特征，通过学习判断一个人的年收入是否超过50 K。在实验过程中，对数据进行预处理，删除缺失属性的记录，并对剩余的45,222条记录进行实验参数集、数据块大小、保持个体分类器个数等。郭庆军和李翠正/ IERI Procedia 3（2012）169173图5三种算法分类精度对比图6三种算法图5在采样率为0.5、0.6和0.7时，CDSBS算法的分类精度明显优于RSWCE算法，0.4以下的RSWCE算法，由于提取率太小，训练样本有偏差导致个体分类器的分类精度太低，使综合分类器放弃了大部分个体分类器的应有，随着提取率的增加，两种算法融合的分类精度更接近，而加权样本分类算法（Weighted Classifiers Ensemination，WCE）。从图6可以看出，CDSBS算法随着概率抽样数据步长的引入，整体计算时间略高于RSWCE算法，分别高出1.4%、8.3%、5.1%和4.6%，但均明显低于WCE算法。5. 结论针对高速数据流中数据快速流动，集成分类器无法训练出所有新到达的模型数据更新分类的问题，提出一种基于采样偏差的高速数据流集成分类174郭庆军和李翠正/ IERI Procedia 3（2012）169分类算法首先简要介绍了抽样技术和贝叶斯最优分类理论，然后对期望值进行了综合分类误差偏差方差分解分析，并定义了期望值对每个样本数据的误差贡献，最后根据每个样本数据的概率贡献计算出样本数据的抽样偏差，训练个体分类器。理论分析和仿真结果表明，在相同条件下，基于抽样分数加权的集成随机分类算法、基于有偏抽样算法的集成分类器具有更高的分类精度引用[1] 朱晓青，吴晓冬，陈庆军。消除大数据集的类噪声。第二十届机器学习国际会议论文集，华盛顿特区，美国。2003年：920- 927 P。[2] 作者声明：A.分类问题中噪声消除的包围法。第四次多重分类系统讲习班，联合王国，2003年：317- 325 P[3] Tumer K，Ghosh J.线性组合神经分类器中决策边界的分析。模式识别1996，29（2）.[4] Tumer K，Ghosh J.集成分类器中的错误相关性和错误减少。连接科学。1996，8（3-4）：385-403P.[5] Shahshahan B，Landgrebe D.未标记样本在减少小样本问题和缓解huberness现象中的作用。IEEE地球科学与遥感学报，1994，32（5）：1087- 1095 P[6] John G. H.鲁棒决策树：从数据库中删除离群值。第一届知识发现和数据挖掘国际会议论文集，Menlo Park，CA，1995：174- 179 P。[7]李晓波，李晓波.医学领域的噪声过滤实验。第十六届机器学习国际会议论文集，旧金山，美国，1999：143- 151 P。[8]M.P.Vani，Computer Aided InteractiveProcess of Teaching Statistics Methodology - II，IEIT Journal of Adaptive Dynamic Computing，2011（3），2011年7月，第18-21页。DOI=10.5813/www.ieit-web.org/IJADC/2011.3.4[9]Zhou Y.Y.，Measuring Service Quality at University's Libraries，IEIT Journal of Adaptive DynamicComputing，2011（3），Jul 2011，pp：22-25. DOI=10.5813/www.ieit-web.org/IJADC/2011.3.5