·88 智能系统学报 第2卷 2.2概念漂移的检测 表1 StreamClassifier算法中的参数含义 如果概念是稳定的，训练窗口和紧随其后的分 Table 1 Para meters meanings in StreamCassifier algorithm 类间隔中的样本应该具有同样的分布.因此分类模 参数 含义 型不会在训练和分类误差率之间存在统计意义上重 S 训练样本集 要的差异.从已有的静态数据集上的研究得知，与此 A 候选输入属性集（包括离散和连续） 相反，误差比率的剧烈增加暗示着发生了概念漂 E user 用户设定的最大分类误差率 训练窗口中样本的个数 移).应用正态分布近似二项分布，根据下列公式计 将被系统分类的第1个样本号（已经到达im·1 算2个误差率之差61： 个样本) V=Fue1 Eu Ead1 Ea 将被分类的最后一个样本号 1) W Gni 最开始模型的待分类样本个数 式中：W表示训练窗口大小，C表示分类窗口大小， Cine 模型稳定时，模型重建期间样本增加的百分比 E,表示训练误差，Em表示分类误差，'表示2个误 模型重建期间运行的最大样本个数 检测到概念漂移时，模型重建期间样本减少的 差率之差 Cred 百分比 如果概念是稳定的，2种误差率之间在99%置 模型重建期间运行的最小样本个数 信度级别的最大差异为 训练窗口中允许样本的最大个数 Dmax =Zo.99 =2.326 2) 如果2种误差率之间最大差异超过Dx,表示检测 确定了计算训练窗口大小和分类窗口大小的方 到了概念漂移，训练窗口回复到初始值.同时，下一 法以及检测概念漂移是否发生的方法之后，可以构 造完整的StreamClassifier算法，算法首先执行一些 个待分类间隔以百分之C缩减，否则表示概念是 初始化的工作，然后处理连续数据流中输入样本，算 稳定的，训练窗口和待分类间隔均增加到最大尺寸. 法启动时第1批训练样本的分类标签需要显示地指 单纯由式2)来检测概念漂移存在一定的问题， 明.算法的伪代码为 需要加以修正 Procedure StreamClassifier 1)Dmx反映的是2种误差之间存在的差异，如 InputS:S,A Cnit,Cne Cmax Cred,Cmin,Wmax 果训练误差很大，分类误差也很大，那么训练误差和 Output:SDT (Stream Decision Tree) 分类误差之间的差异可能小于Dx,这时系统没有 计算训练窗口的初始训练窗口尺寸W 检测到概念漂移，但是由于分类误差率可能远远超 训练窗口尺寸W=Wm 过了能接受的值，需要重建模型.因此需要设置一个 初始化第1个训练样本的索引i为nmn-W 用户允许的分类误差率E_user.当分类误差率超过 初始化最后一个训练样本的索引j为W E user时，认为产生了概念漂移 初始化分类样本的个数C为C 2)令训练误差E=0,若不发生概念漂移，则由 while j<nmax do begin Ea<Dmmx,可得Ea<5.4/(5.4+g,当C较大时， 对最近W个训练样本使用BuildTree(AtrList,W, E接近0.对于分类误差率，一般不可能达到这样 N)算法得到分类模式SDT 的精确度，这样系统会检测到概念漂移.这时认为， 计算得到模式的训练误差率E 只要E<Euser,则认为没有产生概念漂移 计算最后需要分类样本的索引k=方+C 2.3 StreamClassifier分类算法描述 计算在C个待分类样本上得到模式的分类误 SPRINT算法是JohnShafer和RakeshAgraw~ 差率Ead al于1996年提出的针对大型数据库的一种高速可 更新最近训练样本的索引j=k 伸缩的数据挖掘分类算法.其建树过程如下：1)为每 确定训练误差和分类误差之间的最大差异 个属性建立属性列表：2)对数值属性列表进行排序； Diax 3)不断分割节点生成决策树.SPRINT采用基尼指 if (Eval-Eur)<Dmax Eval E user then/ 数(Gini index)来度量最佳分裂点，进行属性选择. 念不变 Gini值越小，表明信息增益量(information gain)越 C=Min(C(1+(Cne/100)).Cmax) 大，节点分裂质量越好.为便于描述，涉及的参数的 W=Min W+C.Wmax) 含义如表1所示 训练集使用最近分类样本获得的类标签 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net2. 2 概念漂移的检测 如果概念是稳定的 ,训练窗口和紧随其后的分 类间隔中的样本应该具有同样的分布. 因此分类模 型不会在训练和分类误差率之间存在统计意义上重 要的差异. 从已有的静态数据集上的研究得知 ,与此 相反 ,误差比率的剧烈增加暗示着发生了概念漂 移[7 ] . 应用正态分布近似二项分布 ,根据下列公式计 算 2 个误差率之差[6 ] : V = Etr (1 - Etr ) W + Eval (1 - Eval) C . (1) 式中 :W 表示训练窗口大小 , C 表示分类窗口大小 , Etr表示训练误差 , Eval表示分类误差 ,V 表示 2 个误 差率之差. 如果概念是稳定的 ,2 种误差率之间在 99 %置 信度级别的最大差异为 Dmax = Z0. 99 V = 2. 326 V . (2) 如果 2 种误差率之间最大差异超过 Dmax ,表示检测 到了概念漂移 ,训练窗口回复到初始值. 同时 ,下一 个待分类间隔以百分之 Cred缩减 ,否则表示概念是 稳定的 ,训练窗口和待分类间隔均增加到最大尺寸. 单纯由式(2) 来检测概念漂移存在一定的问题 , 需要加以修正. 1) Dmax反映的是 2 种误差之间存在的差异 ,如 果训练误差很大 ,分类误差也很大 ,那么训练误差和 分类误差之间的差异可能小于 Dmax ,这时系统没有 检测到概念漂移 ,但是由于分类误差率可能远远超 过了能接受的值 ,需要重建模型. 因此需要设置一个 用户允许的分类误差率 E_user. 当分类误差率超过 E_user 时 ,认为产生了概念漂移. 2) 令训练误差 Etr = 0 ,若不发生概念漂移 ,则由 Eval < Dmax ,可得 Eval < 5. 4/ (5. 4 + C) ,当 C 较大时 , Eval接近 0. 对于分类误差率 ,一般不可能达到这样 的精确度 ,这样系统会检测到概念漂移. 这时认为 , 只要 Eval < E_user ,则认为没有产生概念漂移. 2. 3 StreamClassifier 分类算法描述 SPRIN T 算法是 JohnShafer 和 RakeshAgraw2 al 于 1996 年提出的针对大型数据库的一种高速可 伸缩的数据挖掘分类算法. 其建树过程如下 :1) 为每 个属性建立属性列表 ;2) 对数值属性列表进行排序 ; 3) 不断分割节点生成决策树. SPRIN T 采用基尼指 数( Gini index ) 来度量最佳分裂点 ,进行属性选择. Gini 值越小 ,表明信息增益量 (information gain) 越 大 ,节点分裂质量越好. 为便于描述 ,涉及的参数的 含义如表 1 所示. 表 1 StreamClassifier 算法中的参数含义 Table 1 Parameters meanings in StreamClassifier algorithm 参数 含义 S 训练样本集 A 候选输入属性集 (包括离散和连续) E_user 用户设定的最大分类误差率 W 训练窗口中样本的个数 nmin 将被系统分类的第 1 个样本号(已经到达 imin - l 个样本) nmax 将被分类的最后一个样本号 Cinit 最开始模型的待分类样本个数 Cinc 模型稳定时 ,模型重建期间样本增加的百分比 Cmax 模型重建期间运行的最大样本个数 Cred 检测到概念漂移时 ,模型重建期间样本减少的 百分比 Cmin 模型重建期间运行的最小样本个数 W max 训练窗口中允许样本的最大个数 确定了计算训练窗口大小和分类窗口大小的方 法以及检测概念漂移是否发生的方法之后 ,可以构 造完整的 StreamClassifier 算法 ,算法首先执行一些 初始化的工作 ,然后处理连续数据流中输入样本 ,算 法启动时第 1 批训练样本的分类标签需要显示地指 明. 算法的伪代码为 Procedure StreamClassifier Inp uts: S , A , Cinit , Cinc , Cmax , Cred , Cmin , W max Outp ut :SD T (Stream Decision Tree) 计算训练窗口的初始训练窗口尺寸 Winit 训练窗口尺寸 W = W init 初始化第 1 个训练样本的索引 i 为 nmin - W 初始化最后一个训练样本的索引 j 为 W 初始化分类样本的个数 C 为 Cinit while j < nmax do begin 对最近 W 个训练样本使用 BuildTree (AtrList , W , N) 算法得到分类模式 SD T 计算得到模式的训练误差率 Etr 计算最后需要分类样本的索引 k = j + C 计算在 C 个待分类样本上得到模式的分类误 差率 Eval 更新最近训练样本的索引 j = k 确定训练误差和分类误差之间的最大差异 Dmax if ( Eval - Etr ) < Dmax & & Eval < E_user t hen / / 概 念不变 C = Min ( C 3 (1 + ( Cinc / 100) ) , Cmax ) W = Min (W + C, W max ) 训练集使用最近分类样本获得的类标签 · 88 · 智 能 系 统 学 报 第 2 卷