第4期 富春岩，等：一种能够适应概念漂移变化的数据流分类方法 ·89· else 模块和分类模块，根据训练精度和分类精度检测概 ifEx=0&&Ea<E_user/1概念不变 念漂移，动态调整训练和分类窗口大小 C=Min(C(1+(Cne/100)),Cmax) 3 性能评价 W=Min(W+C.Wmax) 训练集使用最近分类样本获得的类标签 实验数据集来自http://www.ics.uci.eduW~ else/检测到概念漂移 mlearr/ML Repository.html.数据集是一个葡萄酒 重新计算训练窗口的尺寸W 化学成分的分析，记录总共178条，每条记录包括 训练集采用正确的标签 13个连续属性和1个类标签，整个数据集有3个类 C=Max(C`(1-(Cd/100)),Cmm) 别.系统配置为Celeron2.4GHz/256MB内存 end if 为了模拟数据流，采用Java的面向连接的 end if Socket通信模式，客户端作为数据发生器，服务器 返回当前分类模式SDT 端对接收的样本缓存并执行训练和分类算法.SoCk end do et服务端作为主程序的一个线程，在后台负责监听 其中决策树的构建采用改进的SPRINT分类 客户端连接，建立连接后，利用while循环不断接收 算法.SPRINT算法中，当分割属性和分割点确定 来自客户端的数据，并存储在缓冲区中 后，算法开始对属性列表进行分裂，使其以分裂值为 实验1不同分类策略的比较： 分割点分配到左右子节点.这样要每次为新节点创 在线分类系统的不变参数设定为：E_user= 建一个属性列表集.而每个节点都维护一个属性列 0.4,nmax =178,Gnit =20Cne =0.5,Caax =50,Ched 表集需付出较大的系统开销.为此本文提出的方法 0.75,Cmn=5,Wmx=100.在表2中，将在线分类系 是令所有的节点共用一个属性列表集.将属性列表 统的性能与其他的分类方法做了对比（客户端数据 的记录格式<属性值，类标号，样本号>中添加一个 发送间隔1ms).测试5和测试6是在线分类系统 字段leaf,用于表明当前记录属于哪个节点.初始 运行结果.测试1和测试2显示了模型不重建的方 时，所有记录的leaf都为0，即都属于根节点.当节 法.即分别假设到达50和78个训练样本，启动算法 点分裂时，不用再分裂属性列表，而是将相应记录的 生成决策树，对后面陆续到达的样本进行分类，期间 leaf字段修改，使其隶属于新节点 决策树不再重建.测试1,2显示了静态分类的思想 Procedure BuildTree(AtrList,W,N) 可以看到训练窗口大小对分类精度的影响.如果模 ifN纯then 式发生变化，用较早的分类模式对较晚到达的数据 标记为叶节点，标记类属性 进行分类，容易产生更大的误差.相对于测试1来 else 说，测试2的训练样本更多更新，因此具有更高的分 forN的每一个分割点F生成属性直方图，计 类精度.相对于模型不重建的方法，在线分类系统的 算该节点F上的基尼指数 优势是明显的.测试3和4显示了静态窗口分类的 end for 结果.根据实验结果得知，在线分类系统具有更高的 选出最佳分割点F,以计算得出的分裂值为 精确度，并且运行时间更少，但静态窗口使用的内存 分界生成当前节点的左右子节点N1,N2.在该分割 空间要小一些 点属性列表分割的同时，用该表的td生成记录所 表2 StreamClassifier在不同分类模式的性能对比 属节点的哈希表，并用哈希表分裂其他的属性列表， Table 2 Performance comparison of StreamCassifier BuildTree(AtrList,W,N1) in different classification mode /对左右节点递归调用BuildTree 测试初始化 分类样 窗口 平均 运行 Build Tree(AtrList,W,N2) 编号 窗口 本个数 个数 错误率 时间/s end if 1 50 128 0.469 1.900 基于StreamClassifier算法构建的分类系统包 2 78 100 1 0.260 1.500 括采用客户服务器模式，客户端作为数据采集器 3 40 10 13 0.292 2.750 服务器含3个模块：学习模块：采用StreamClassifi- 4 50 20 6 0.325 2.770 5 30 动态 9 0.278 2.231 er分类算法构建决策树；分类模块：使用学习模块 6 50 动态 14 0.290 2.015 生成的决策树对样本进行分类；控制模块：控制学习 @1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netelse if Etr = 0 & & Eval < E_user / / 概念不变 C = Min ( C 3 (1 + ( Cinc / 100) ) , Cmax ) W = Min (W + C, W max ) 训练集使用最近分类样本获得的类标签 else / / 检测到概念漂移 重新计算训练窗口的尺寸 W 训练集采用正确的标签 C = Max ( C 3 (1 - ( Cred / 100) ) , Cmin ) end if end if 返回当前分类模式 SD T end do 其中决策树的构建采用改进的 SPRIN T 分类 算法. SPRIN T 算法中 ,当分割属性和分割点确定 后 ,算法开始对属性列表进行分裂 ,使其以分裂值为 分割点分配到左右子节点. 这样要每次为新节点创 建一个属性列表集. 而每个节点都维护一个属性列 表集需付出较大的系统开销. 为此本文提出的方法 是令所有的节点共用一个属性列表集. 将属性列表 的记录格式 < 属性值 ,类标号 ,样本号 > 中添加一个 字段 leaf ,用于表明当前记录属于哪个节点. 初始 时 ,所有记录的 leaf 都为 0 ,即都属于根节点. 当节 点分裂时 ,不用再分裂属性列表 ,而是将相应记录的 leaf 字段修改 ,使其隶属于新节点. Procedure BuildTree (AtrList , W , N) if N 纯 t hen 标记为叶节点 ,标记类属性 else for N 的每一个分割点 F 生成属性直方图 ,计 算该节点 F 上的基尼指数 end for 选出最佳分割点 F 3 ,以计算得出的分裂值为 分界生成当前节点的左右子节点 N1 , N2. 在该分割 点属性列表分割的同时 ,用该表的 tid 生成记录所 属节点的哈希表 ,并用哈希表分裂其他的属性列表. BuildTree (AtrList , W , N1) / / 对左右节点递归调用 BuildTree BuildTree (AtrList , W , N2) end if 基于 StreamClassifier 算法构建的分类系统包 括采用客户 —服务器模式 ,客户端作为数据采集器. 服务器含 3 个模块 :学习模块 :采用 StreamClassifi2 er 分类算法构建决策树 ;分类模块 :使用学习模块 生成的决策树对样本进行分类 ;控制模块 :控制学习 模块和分类模块 ,根据训练精度和分类精度检测概 念漂移 ,动态调整训练和分类窗口大小. 3 性能评价 实验数据集来自 http :/ / www. ics. uci. edu/ ～ mlearn/ ML Repository. html. 数据集是一个葡萄酒 化学成分的分析 ,记录总共 178 条 ,每条记录包括 13 个连续属性和 1 个类标签 ,整个数据集有 3 个类 别. 系统配置为 Celeron 2. 4 GHz/ 256 MB 内存. 为了模拟数据流 , 采用 J ava 的面向连接的 Socket 通信模式 ,客户端作为数据发生器 ,服务器 端对接收的样本缓存并执行训练和分类算法. Sock2 et 服务端作为主程序的一个线程 ,在后台负责监听 客户端连接 ,建立连接后 ,利用 while 循环不断接收 来自客户端的数据 ,并存储在缓冲区中. 实验 1 不同分类策略的比较 : 在线分类系统的不变参数设定为 : E_ user = 0. 4 , nmax = 178 , Cinit = 20Cinc = 0. 5 , Cmax = 50 , Cred = 0. 75 , Cmin = 5 , W max = 100. 在表 2 中 ,将在线分类系 统的性能与其他的分类方法做了对比 (客户端数据 发送间隔 1 ms) . 测试 5 和测试 6 是在线分类系统 运行结果. 测试 1 和测试 2 显示了模型不重建的方 法. 即分别假设到达 50 和 78 个训练样本 ,启动算法 生成决策树 ,对后面陆续到达的样本进行分类 ,期间 决策树不再重建. 测试 1 ,2 显示了静态分类的思想 , 可以看到训练窗口大小对分类精度的影响. 如果模 式发生变化 ,用较早的分类模式对较晚到达的数据 进行分类 ,容易产生更大的误差. 相对于测试 1 来 说 ,测试 2 的训练样本更多更新 ,因此具有更高的分 类精度. 相对于模型不重建的方法 ,在线分类系统的 优势是明显的. 测试 3 和 4 显示了静态窗口分类的 结果. 根据实验结果得知 ,在线分类系统具有更高的 精确度 ,并且运行时间更少 ,但静态窗口使用的内存 空间要小一些. 表 2 StreamClassifier 在不同分类模式的性能对比 Table 2 Performance comparison of StreamClassifier in different classification mode 测试 编号 初始化 窗口 分类样 本个数 窗口 个数 平均 错误率 运行 时间/ s 1 50 128 1 0. 469 1. 900 2 78 100 1 0. 260 1. 500 3 40 10 13 0. 292 2. 750 4 50 20 6 0. 325 2. 770 5 30 动态 9 0. 278 2. 231 6 50 动态 14 0. 290 2. 015 第 4 期 富春岩 ,等 :一种能够适应概念漂移变化的数据流分类方法 · 98 ·