第4期 富春岩，等：一种能够适应概念漂移变化的数据流分类方法 ·87· 个连续的样本目标函数不一致的概率.他们提出 构建了数据流分类算法StreamClassifier. 一种在固定数据集上最小化这种不一致的算法，其 算法反复从滑动的窗口获取最近的样本来重建 复杂度为样本数量的多项式规模.然而，对于海量非 分类模型，使用最新的模型为下次模型重建期间的 固定的数据流，漂移发生的实际速率事先无法知道， 样本进行分类，并暂存最新的分类结果以便为下次 其算法的运行时间可能不确定地增加 模型重建提供训练样本.当分类误差相对与可以接 数据流社区中有关数据流的分类问题研究比较 受的训练误差出现大幅的上升时，意味着检测到概 活跃，近几年出现了许多研究成果.Wang等提出一 念漂移.当概念稳定时，系统不断增加训练窗口和分 个通用框架用于挖掘概念漂移数据流)，Ganti等 类窗口的大小直到一个预定的上限.当出现概念漂 开发了一个在插入和删除数据记录时维护模型的算 移时，训练窗口和分类窗口被重置，并提供正确的分 法o],Widmer和Kubat!)提出了一簇纯增量算法 类标签用于下次训练」 来处理概念漂移，Domingos等开发了VFDT8),Pa 本文提出数据流分类算法StreamClassifier的 padimitriou等提出AWSOM(arbitrary window 基本思想如图1所示，在连续不断的样本数据流中 stream m odeling method)用于在传感器网络中发 用间隔[0,1中的6个训练样本产生的模式，对 现感兴趣的模式)，Aggarwal等采用On-Demand 间隔[h,31中V。个验证样本进行分类.训练窗口 分类中CluStream的微簇思想，获得了很高的分类 中的样本数与待测试窗口中的样本数不必相等.在 精度o],Last提出可以适应概念漂移的在线分类系 时刻B,学习模块使用训练间隔[，飞]中的T个样 统)，Ding等开发了基于Peano Count Tree数据 本，对网络进行重建，然后对测试窗口[3,41中的 结构的决策树2)，Gaber等开发了Lightweight轻 V1个样本进行分类.假设在间隔[s,4中的第1个 权值分类L WClass模型) 样本在分类模式已经重建完成后才到达 上述己存在的数据流分类模型和算法存在2方 当前窗口（个样本）6个样本个样本 面问题，首先，未能有效地解决数据流在线训练、测 当前窗口(T个样本) 试、分类的速度问题，对于大规模高维数据流的在线 数据流 分类，目前还没有公认的解决方案，其次，都没有较 好地解决变化数据流上的概念漂移问题，未能有效 地解决当概念漂移发生时，分类模式快速转变的问 图1 StreamClassifier算法训练分类工作原理 题，分类精度偏低 Fig.I Principle of training and classifying of StreamClassifier algorithm 2 StreamClassifier分类算法 算法运行需要计算下列参数：训练窗口的尺寸， 决策树学习是一种逼近离散值目标函数的有指 待分类窗口的尺寸，训练误差和分类误差之间的最 导的学习方法，在这种方法中学习到的函数被表示 大差异 为一棵决策树.学习得到的决策树也能被表示为多 2.1计算分类窗口中的样本个数 个if-then规则，以提高可读性.这种学习算法是最 待分类窗口中的样本个数即2次分类模型重建 流行的归纳推理算法之一，已经被成功地应用到从 的间隙，为了能够自适应概念漂移的发生，采用概念 学习医疗诊断到学习评估信贷申请的信用风险等广 漂移发生的频率直接决定待分类窗口中的样本个数 阔领域： 的思想.为了检测概念是否发生了偏移，采用纯粹增 D3、C4.5算法仅适用于小规模数据集，在大规 量的方法对于海量数据流是不合适的，因为在连续 模数据的数据挖掘中具有可伸缩性的决策树算法包 的样本实例抵达的间隙，概念通常并不会剧烈频繁 括SLIQ1I、SPRIN TUSI、SLIQ和SPRINT算法使 地变化，对此Hulten等提出的CVFDT算法仅在固 用预排序技术以及新的数据结构，大大提高了对于 定个数的样本(20000)之后才检测一次漂移是否发 大规模数据集的可扩展性.其中SPRINT算法还非 生.本文参照OLN里采用的一种启发规则，动态 常容易并行化.但是，这些常见的决策树算法无法处 调整2次模型重建的间隙之间的样本的个数：如果 理连续的数据流，并且不具备增量学习能力，使其应 概念呈现稳定态势，为当前的模型保留更多的样本： 用受到了较大限制.鉴于SPRINT算法在可伸缩 如果检测到概念漂移的发生，就大幅度减小待分类 性、并行性方面的优点，在SPRINT算法的基础上 窗口的尺寸 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net个连续的样本目标函数不一致的概率[ 4 ] . 他们提出 一种在固定数据集上最小化这种不一致的算法 ,其 复杂度为样本数量的多项式规模. 然而 ,对于海量非 固定的数据流 ,漂移发生的实际速率事先无法知道 , 其算法的运行时间可能不确定地增加. 数据流社区中有关数据流的分类问题研究比较 活跃 ,近几年出现了许多研究成果. Wang 等提出一 个通用框架用于挖掘概念漂移数据流[5 ] , Ganti 等 开发了一个在插入和删除数据记录时维护模型的算 法[6 ] ,Widmer 和 Kubat [7 ] 提出了一簇纯增量算法 来处理概念漂移 ,Domingos 等开发了 VFD T [8 ] ,Pa2 padimitriou 等 提 出 AWSOM ( arbitrary window stream m odeling met hod) 用于在传感器网络中发 现感兴趣的模式[ 9 ] , Aggarwal 等采用 On2Demand 分类中 CluStream 的微簇思想 ,获得了很高的分类 精度[ 10 ] ,Last 提出可以适应概念漂移的在线分类系 统[11 ] ,Ding 等开发了基于 Peano Count Tree 数据 结构的决策树[12 ] , Gaber 等开发了 Lightweight 轻 权值分类 L WClass 模型[13 ] . 上述已存在的数据流分类模型和算法存在 2 方 面问题 ,首先 ,未能有效地解决数据流在线训练、测 试、分类的速度问题 ,对于大规模高维数据流的在线 分类 ,目前还没有公认的解决方案 ;其次 ,都没有较 好地解决变化数据流上的概念漂移问题 ,未能有效 地解决当概念漂移发生时 ,分类模式快速转变的问 题 ,分类精度偏低. 2 StreamClassifier 分类算法 决策树学习是一种逼近离散值目标函数的有指 导的学习方法 ,在这种方法中学习到的函数被表示 为一棵决策树. 学习得到的决策树也能被表示为多 个 if2t hen 规则 ,以提高可读性. 这种学习算法是最 流行的归纳推理算法之一 ,已经被成功地应用到从 学习医疗诊断到学习评估信贷申请的信用风险等广 阔领域. ID3、C4. 5 算法仅适用于小规模数据集 ,在大规 模数据的数据挖掘中具有可伸缩性的决策树算法包 括 SL IQ [ 14 ] 、SPRIN T [15 ] 、SL IQ 和 SPRIN T 算法使 用预排序技术以及新的数据结构 ,大大提高了对于 大规模数据集的可扩展性. 其中 SPRIN T 算法还非 常容易并行化. 但是 ,这些常见的决策树算法无法处 理连续的数据流 ,并且不具备增量学习能力 ,使其应 用受到了较大限制. 鉴于 SPRIN T 算法在可伸缩 性、并行性方面的优点 ,在 SPRIN T 算法的基础上 构建了数据流分类算法 StreamClassifier. 算法反复从滑动的窗口获取最近的样本来重建 分类模型 ,使用最新的模型为下次模型重建期间的 样本进行分类 ,并暂存最新的分类结果以便为下次 模型重建提供训练样本. 当分类误差相对与可以接 受的训练误差出现大幅的上升时 ,意味着检测到概 念漂移. 当概念稳定时 ,系统不断增加训练窗口和分 类窗口的大小直到一个预定的上限. 当出现概念漂 移时 ,训练窗口和分类窗口被重置 ,并提供正确的分 类标签用于下次训练. 本文提出数据流分类算法 StreamClassifier 的 基本思想如图 1 所示 ,在连续不断的样本数据流中 , 用间隔[ t0 , t2 ]中的 T0 个训练样本产生的模式 ,对 间隔[ t2 , t3 ]中 V 0 个验证样本进行分类. 训练窗口 中的样本数与待测试窗口中的样本数不必相等. 在 时刻 t3 ,学习模块使用训练间隔[ t1 , t3 ]中的 T1 个样 本 ,对网络进行重建 ,然后对测试窗口[ t3 , t4 ]中的 V 1 个样本进行分类. 假设在间隔[ t3 , t4 ]中的第 1 个 样本在分类模式已经重建完成后才到达. 图 1 StreamClassifier 算法训练分类工作原理 Fig. 1 Principle of training and classifying of StreamClassifier algorithm 算法运行需要计算下列参数 :训练窗口的尺寸 , 待分类窗口的尺寸 ,训练误差和分类误差之间的最 大差异. 2. 1 计算分类窗口中的样本个数 待分类窗口中的样本个数即 2 次分类模型重建 的间隙 ,为了能够自适应概念漂移的发生 ,采用概念 漂移发生的频率直接决定待分类窗口中的样本个数 的思想. 为了检测概念是否发生了偏移 ,采用纯粹增 量的方法对于海量数据流是不合适的 ,因为在连续 的样本实例抵达的间隙 ,概念通常并不会剧烈频繁 地变化 ,对此 Hulten 等提出的 CV FD T 算法仅在固 定个数的样本(20 000) 之后才检测一次漂移是否发 生. 本文参照 OL IN [11 ]里采用的一种启发规则 ,动态 调整 2 次模型重建的间隙之间的样本的个数 :如果 概念呈现稳定态势 ,为当前的模型保留更多的样本 ; 如果检测到概念漂移的发生 ,就大幅度减小待分类 窗口的尺寸. 第 4 期 富春岩 ,等 :一种能够适应概念漂移变化的数据流分类方法 · 78 ·