| 标题 | 数据流挖掘抑制概念漂移不良影响研究 |
| 范文 | 卞舒逸 摘要：提升基于数据流的数据挖掘正确率并克服概念漂移的影响是当前的研究热点之一。相对于传统意义上的数据挖据，基于数据流的数据挖掘具有动态、数量多、持续性强等特点。由于传统的数据挖掘算法都是应用于静态数据，挖掘结果并不完全匹配动态变化。将样本数据流进行数据块化处理后使用集成算法，可提升流数据挖掘的准确性。其中集成算法基分类器包括决策树和KNNModel算法等。對于不同算法的效果给予不同权值，提升算法相比于基分类器，能够更加准确地判定概念漂移的发生。实验结果表明，通过集成学习方法可以有效提升学习效果及分类判定准确率，非同质类型的集成算法对于抑制概念漂移的不良影响可起到一定作用。 关键词：数据流挖掘； 概念漂移； 数据块； 集成算法 DOIDOI：10.11907/rjdk.181079 中图分类号：TP3-0 文献标识码：A文章编号文章编号：16727800（2018）009006403 英文标题Research on Data Flow Learning Suppression of Concept Drift Adverse Effects ——副标题 英文作者BIAN Shuyi 英文作者单位（School of Computer， Nanjing University of Posts and Telecommunications， Nanjing 210003， China） 英文摘要Abstract：It is an important research hotspot to improve the accuracy of data mining based on data mining and to deal with the impact of conceptual drift.Compared with data mining in the traditional sense，data mining of the data stream has such characteristics as dynamic， large amount and continuity.As the traditional data mining algorithms are applied to static data， the data mining results do not exactly match.In this paper， we improve the accuracy of streaming data mining by using an integrated algorithm.The integrated algorithm base classifier includes decision tree and KNNModel algorithm.Different weights are given to the corresponding algorithms.Compared with the base classifier， the lifting algorithm can determine the occurrence of concept drift more accurately.The integrated learning method can effectively improve the learning effect.The nonhomogeneous type of integration algorithm plays a certain role in suppressing the adverse effects of concept drift. 英文关键词Key Words：data mining； concept drift； data block； integrated algorithm 0引言 如今，数据流挖掘在越来越多的领域得到大量应用，常见应用有银行业务中的信用卡欺诈判别、阿里巴巴等在线平台对客户消费的推荐与预测，百度、谷歌等公司对于大量搜索信息的挖掘，电信、移动等运营商的通讯信息处理等。数据流挖掘已经成为当前的研究热点之一[1]。然而，由于数据流本身的动态特性，特别是其中存在的概念漂移问题，使传统意义上的数据挖掘算法无法达到令人满意的效果。由于概念漂移现象的影响，数据流挖掘需要在数据特性随时间变化时能够自适应地跟随变化，从而保证流数据挖掘的性能[2]。 最早提出的针对概念漂移的数据流分类方法是2001年Hulten等[3]提出的CVFDT算法，其将VFDT算法进行改进，通过构建替代子树的方法克服概念漂移的影响。当检测到概念漂移时，CVFDT使用所构建的替代子树替换原有VFDT树中的子树，使VFDT能够及时更新，从而适应新数据环境。因此，CVFDT算法不仅继承了VFDT分类效率高的特点，而且能够克服概念漂移对模型造成的影响，以保持分类的准确与稳定。随着研究的深入，利用增量式学习思想对模型进行实时更新成为新的研究热点。Aboalsamh等[4]提出一种使用增量式学习方法的数据流分类模型，通过将分类模型学习过程进行增量式处理，能够加快模型的自我更新速度，从而通过不断更新模型的方式解决概念漂移问题；Kuncheva等[5]对数据流分类模型进行研究，发现分类模型的准确率不仅受到概念漂移及数据本身质量的影响，而且还与滑动窗口大小有关。因此，基于以上观察，提出一种可变滑动窗口的数据流分类模型。当发生概念漂移时，滑动窗口能够自动放大或缩小窗口，使分类模型能够有效地检测概念漂移，以保证分类模型的及时更新，提高分类过程的准确率；Seo等[6]对多变量数据流进行研究，使用时间变量挖掘数据流中各属性之间的关联关系，进而使用这些关系对数据流分类进行指导。 根据强可学习和弱可学习的概念，由于在实际应用中，弱可学习算法更容易被发现，而其又可以被证明与强可学习算法等价[7]，所以使用集成学习方法，对应不同应用条件，相对赋予其中算法不同权值，可以得到更好的学习效果。本文主要研究非同质型集成算法对于概念漂移自适应能力的提升。 1基础分类器算法介绍 1.1基于增量的KNNModel算法 KNNModel算法与传统的KNN算法相比，k值的确定更为容易，而且KNNModel能较好地满足数据流挖掘工作对效率的要求。KNNModel算法的核心思想与KNN相近，以一个特征点为圆心作为分类区域，一方面尽可能包括相同样本，另一方面要避免包括异类，使圆尽量大[8]。保存下来比较有效的模型簇形式是四元组和五元组，包括类别、半径、数量和圆心。通过不断迭代，最终达到分类目的[9]。 层次纠错输出编码相对于传统算法事先构造出同一编码矩阵进行分割，其能使用簇描述数据分布，是一种构建层次的方法。层次纠错输出编码的核心思想是，通过对同类簇采用一一对应的方式编码，使相同簇合并，并按照由多到少、由下到上的顺序将最接近的两个簇合并起来[10]。上述方法的通用性在于其可以与其它算法相融合，扩大算法适用范围，从而使该算法在分类和纠错方面具有突出效果。 在此基础上发展而来的基于增量的KNNModel动态层次纠错输出编码算法可以处理概念漂移问题，其核心思想为：首先将数据流划分为数据块，在第一个数据块上进行学习；然后建立类别规则区域，之后建立层次树层次码，并以中心点和边界距离为依据；最后采用可增量学习分类算法进行学习，生成分类器集合。分类器集合生成过程的终点利用活跃程度进行判断[11]。 基于增量的KNNModel算法学习过程具体步骤如下： （1）在数据块上进行预学习，建立规则区域，选择合适的代表簇，建立层次树层次编码，利用学习算法学习后生成分类器集。 （2）开始进行增量学习，具体步骤为：①数据到来后，根据代表簇对层次树进行更新；②有新类别出现时，依次计算已有类别的漂移度；③从漂移度最小的类别开始，根据情况进行更新。 （3）根据编码矩阵训练单分类器。 （4）学习后检查编码个数，对编码进行修剪。 1.2CVFDT决策树算法 该算法中最重要的步骤是对概念漂移的判断与处理，在接收到数据时，解决窗口内的概念差异。该算法将窗口划分为若干个基本窗口，然后选择最新概念的数据。为了保证准确性，算法记录了滑动窗口的历史分类[12]。若模型判断发生了概念漂移，则选用集成分类器，去掉没有价值的决策树分支子树并进行重建。因为概率分布不均，若滑动窗口概念混乱将造成决策树分类错误，所以不一致的分类属性需要暂时缓存。决定对决策树中各个节点进行分类或替代需要等待一段时间进行处理[13]，该处理方法可以在数据处理过程中减少噪声的影响。 决策树处理过程如下： 输入：W={D1，D2，…，Dm}是滑动窗口数据块集合； 输出：Tree是用来分类的决策树； 过程：For W 中的每个实例K 用Tree将K排入叶子节点L中 For 实例K所经过的每个节点L 更新流入L节点实例概要结构的N For L节点替代子树ALT中的每一个子树 递归调用该过程处理决策树的子树 若L节点观察的实例不全属于同一类，且在当前节点观察的实例数大于数据块 借助概要结构N找到最佳分裂属性Xa和次佳分类属性Xb 若Xa与Xb间的信息熵之差满足在阈值内 则可认为Xa是最佳分裂属性，并在L点进行分裂 初始化各个分裂节点的ALT树与概要结构N 2非同质型集成算法 在集成算法中，分为同质型集成算法即基分类器类别相同，以及非同质型集成算法即基分类器类型不同。当个体分类器差异变小时，不易提高集成分类器的准确率，所以尝试将KNN和决策树两种不同模型进行混合，以期达到更好的学习性能[14]。 在集成策略中，使用最广泛的是经典提升算法Adaboost。Adaboost算法与Bagging算法类似，都有放回抽樣，不同的是训练数据权重不同。在Adaboost算法中，每个训练数据被赋予相同的初始权值。随着分类训练的进行，错误样本会得到更高的权重，而正确分类的数据则会被降低权重。对于分类器，样本权重越高，分类难度越大[15]。由于所有训练数据都被更新过一次，因此需要再次对其进行规范化处理。 算法过程如下： 输入： 训练数据集D 成员分类模型个数k 学习算法SM 输出：集成分类模型M 方法： 将训练数据集D中的每条数据初始化权重置为1/d； For i=1…k 从训练数据集D中挑出高权重样本并产生训练子集D1； 对训练子集Di使用选定算法得到成员分类器Mi； 通过计算成员分类Mi的分类误差； If成员分类器Mi的分类误差>0.5 重新将训练子集数据的初始化权重置为1/d； 再对抽样训练数据子集产生新的成员分类器Mi； End if For 训练子集Di中被正确分类的数据 更新权重，用现有权重乘以error（Mi）/（1-error（Mi）） 对更新完权重的数据作规范化处理； Return M； 通过集成算法可以更加准确地发现概念漂移现象，并及时调整分类模型，提高分类正确率。改进的KNN和CVFDT都对概念漂移有一定自适应能力，将这两个模型作为弱分类器，采用集成算法结合生成混合模型。新模型对数据流变化有更好的适应能力，同时也可通过混合模型方式减少决策树算法对样本的过度依赖。 3仿真验证 为了验证非同质型集成算法的自适应能力与应对概念漂移的有效性，采用MATLAB仿真工具对新集成算法的有效性进行检测与分析，测试该方法在多种数据集下的效果。该仿真数据集由MATLAB仿真工具随机生成，生成的数据集特征如表1所示。 从以上实验结果可以看出，相对于改进的KNN和决策树，其集成后的模型性能得到提升。KNN对概念漂移的自适应是最慢的，最后稳定效果也最差；改进的决策树初始效果超过了KNN，最后的稳定性能也比KNN好，但有可能出现过度依赖样本的状况；集成算法开始时的自适应效果比决策树略差，但之后逐渐提升，最后稳定在比决策树略高的水平上。由此可得，这种差异化的集成算法在应对概念漂移方面具有更好的性能。 4结语 混合模型吸取了集成算法的优点，将弱学习模型通过一定比例组合，以提升模型性能，并通过试验进行了验证，但模型复杂度也相对变大。在决策树算法中由罚函数抑制过拟合问题，可防止决策树模型过于复杂，但只能适应样本，无法适应新数据。对于该项研究的下一阶段目标是仿照决策树方法，构建合适的罚函数模型，以检测该混合模型是否出现了过拟合现象。 参考文献参考文献： [1]李思男，李宁，李战怀.多标签数据挖掘技术研究综述[J].计算机科学，2013，40（4）：1421. [2]ELWELL R，POLIKAR R.Incremental learning of concept drift in nonstationary environments [J].Neural Networks，IEEE Transactions on，2011，22（10）：15171531. [3]KOTSIANTIS S B，PINTELAS P E.Recent advances in clustering：a brief survey [J].WSEAS Trans on Information Science and Application，2004，11（1）：7381. [4]WANG S，MINKU L L，GHEZZI D，et al.Concept drift detection for online class imbalance learning[C].Neural Networks （IJCNN），The 2013 International Joint Conference on.IEEE，2013：110. [5]GUO G，WANG H，BELL D，et al.Using KNN model for automatic text categorization [J].Soft Computing，2006，10（5）：423430. [6]李培培.數据流中概念漂移检测与分类方法研究[D].合肥：合肥工业大学，2012. [7]TSYMBAL A，PECHENIZKIY M，CUNNINGHAM P，et al.Dynamic integration of classifiers for handling concept drift [J].Information Fusion，2008，9（1）：5668. [8]KOLTER J Z，MALOOF M A.Dynamic weighted majority：an ensemble method for drifting concepts [J].Journal of Machine Research，2007，8（12）：27552790. |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。