·90 智能系统学报 第2卷 实验2检测算法对概念漂移的适应情况」 表3系统运行时间表 图2显示了每次训练分类的训练误差和分类误 Table 3 Sending interval Vs.running time 差，图3显示了对应的训练窗口和分类窗口.算法刚 客户端发送间隔 运行时间 开始时采用正确的类标签进行训练，因此训练误差 1.000 158.0 为0.这时概念稳定，分类训练窗口和分类窗口不断 0.500 79.0 扩大，分类误差也不断上升，第3次分类结束后检测 0.100 17.3 到概念漂移，模型采取相应调整措施，训练窗口恢复 0.050 9.9 0.010 2.5 到初始窗口，大幅度缩小分类窗口的大小.采用正确 0.001 2.5 的类标签进行训练，训练误差率回到0.然后概念恢 复稳定，在第5次分类时再次检测到概念漂移，第6 从表3中的数据测试发现，对50个样本一次建 次调整恢复正常.因此6、7、8次分类和1、2、3次分 树时间63ms,对128个样本分类时间为1.83s,建 类的窗口和错误率发展情况类似.第8次的分类窗 树时间约为分类时间的3%左右.分类的时间开销 口本应大于第7次，但由于数据流接近末尾，提供的 主要来自于读缓冲区，因为缓冲区使用了并发控制， 分类样本数量比较少，分类完后算法就结束了，所以 客户端不断将样本写进缓冲区，导致分类时从缓冲 出现图示的情况 区读取样本可能等待，所以耗费了大量时间.从发送 概念漂移检测 +川练误差率 间隔0.1s开始，系统运行时间和样本的总传输时 0.6 +分类误差率 0.5 间相当 .4 03 4 结束语 0 0.1 在许多数据流应用中，短时间内有大量数据连 5 续到达，这些数据具有随时间动态变化的趋势，往往 分类次数/次 又是高维的，怎样使用有限存储空间对这些数据流 进行快速处理以获取有用信息，为数据挖掘及其应 图2分类的训练误差率与分类误差率 用研究带来了新的机遇和挑战.本文针对数据流的 Fig.2 Error rate training and classifying error rate 特性，提出了一个能够适应概念漂移发生的在线分 类算法，实验证明基于此算法构建的在线分类系统 可以对连续变化的数据流进行分类，耗用较少的资 口分类窗口人小 源，并具有较高的分类精度.目前的工作尚不完善 a训练窗口人小 还需要运用更多的实时数据集来测量系统的性能， 可以探究其他的方法检测概念漂移的发生」 参考文献： 34567 [1]QUINLAN J R.Induction on decision trees[J ]Machine 分类次数/次 Learning,1986,13(1):81-106 [2 ]QUINLAN J R.C4.5:programs for machine learning 图3训练窗口和分类窗口变化情况 M].San Mateo:Morgan Kaufmann,1993. ig.3 The change of training and classifying window [3 ]BREIMAN L,FRIEDMAN J ,OLSHEN R,et al.Classifi- cation and regression trees monterey[M].Belmont:Wad- Java定时器的精度只能达到1ms,可以看到 sworth International Group,1984. 系统有个运行的极小时间2.5ms,当发送间隔在 [4]HEL MBOLD D P,LONG P M.Tracking drifting con 10ms以内时发送速度对运行时间不构成影响.当 cepts by minimizing disagreements[J].Machine Learn- ing,1994,21(14):27.45. 发送间隔1ms时，发送178个数据需要0.178s, [5]WANG H,FAN W,YU P,HAN J.Mining concept- 但系统运行2.5s左右，其主要时间开销来自缓 drifting data streams using ensemble classifiers[A].The 冲区的读写. 9th ACM International Conference on Knowledge Discov- ery and Data Mining (SIGKDD's03)[C].New York: 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net实验 2 检测算法对概念漂移的适应情况. 图 2 显示了每次训练分类的训练误差和分类误 差 ,图 3 显示了对应的训练窗口和分类窗口. 算法刚 开始时采用正确的类标签进行训练 ,因此训练误差 为 0. 这时概念稳定 ,分类训练窗口和分类窗口不断 扩大 ,分类误差也不断上升 ,第 3 次分类结束后检测 到概念漂移 ,模型采取相应调整措施 ,训练窗口恢复 到初始窗口 ,大幅度缩小分类窗口的大小. 采用正确 的类标签进行训练 ,训练误差率回到 0. 然后概念恢 复稳定 ,在第 5 次分类时再次检测到概念漂移 ,第 6 次调整恢复正常. 因此 6、7、8 次分类和 1、2、3 次分 类的窗口和错误率发展情况类似. 第 8 次的分类窗 口本应大于第 7 次 ,但由于数据流接近末尾 ,提供的 分类样本数量比较少 ,分类完后算法就结束了 ,所以 出现图示的情况. 图 2 分类的训练误差率与分类误差率 Fig. 2 Error rate training and classifying error rate 图 3 训练窗口和分类窗口变化情况 F ig. 3 The change of training and classifying window J ava 定时器的精度只能达到 1 ms ,可以看到 系统有个运行的极小时间 2 . 5 ms ,当发送间隔在 10 ms以内时发送速度对运行时间不构成影响. 当 发送间隔 1 ms 时 ,发送 178 个数据需要 0 . 178 s , 但系统运行 2 . 5 s 左右 ,其主要时间开销来自缓 冲区的读写. 表 3 系统运行时间表 Table 3 Sending interval Vs. running time s 客户端发送间隔 运行时间 1. 000 158. 0 0. 500 79. 0 0. 100 17. 3 0. 050 9. 9 0. 010 2. 5 0. 001 2. 5 从表 3 中的数据测试发现 ,对 50 个样本一次建 树时间 63 ms ,对 128 个样本分类时间为1. 83 s ,建 树时间约为分类时间的 3 %左右. 分类的时间开销 主要来自于读缓冲区 ,因为缓冲区使用了并发控制 , 客户端不断将样本写进缓冲区 ,导致分类时从缓冲 区读取样本可能等待 ,所以耗费了大量时间. 从发送 间隔 0. 1 s 开始 ,系统运行时间和样本的总传输时 间相当. 4 结束语 在许多数据流应用中 ,短时间内有大量数据连 续到达 ,这些数据具有随时间动态变化的趋势 ,往往 又是高维的 ,怎样使用有限存储空间对这些数据流 进行快速处理以获取有用信息 ,为数据挖掘及其应 用研究带来了新的机遇和挑战. 本文针对数据流的 特性 ,提出了一个能够适应概念漂移发生的在线分 类算法 ,实验证明基于此算法构建的在线分类系统 可以对连续变化的数据流进行分类 ,耗用较少的资 源 ,并具有较高的分类精度. 目前的工作尚不完善 , 还需要运用更多的实时数据集来测量系统的性能 , 可以探究其他的方法检测概念漂移的发生. 参考文献 : [ 1 ]QUINLAN J R. Induction on decision trees[J ]. Machine Learning ,1986 ,13 (1) :81 - 106. [ 2 ] QU INLAN J R. C4. 5 : programs for machine learning [ M ]. San Mateo :Morgan Kaufmann ,1993. [ 3 ]BREIMAN L ,FRIEDMAN J ,OLSHEN R ,et al. Classifi2 cation and regression trees monterey[ M ]. Belmont :Wad2 sworth International Group , 1984. [4 ] HELMBOLD D P , LON G P M. Tracking drifting con2 cepts by minimizing disagreements[J ]. Machine Learn2 ing , 1994 ,21 (14) :27 - 45. [5 ] WAN G H , FAN W , YU P , HAN J. Mining concept2 drifting data streams using ensemble classifiers[ A ]. The 9th ACM International Conference on Knowledge Discov2 ery and Data Mining ( SIGKDD’s03) [ C ]. New York : · 09 · 智 能 系 统 学 报 第 2 卷