动态数据流具有数据量大、变化快、随机存取代价高、详细数据难以存储等特点，挖掘动态数据流对计算能力与存储能力要求非常高。针对动态数据流的以上特点，设计了一种基于自助抽样的动态数据流贝叶斯分类算法，算法运用滑动窗口模型对动态数据流进行处理分析。该模型以每个窗口的数据为基本单位，对窗口内的数据进行处理分析；算法采用自助抽样技术对待分类数据中的属性进行裁剪和优化，解决了数据属性间的多重线性相关问题；算法结合贝叶斯算法的特点，采用动态增量存储树来解决动态样本数据流的存储问题，实现了无限动态数据流无信息失真的静态有限存储，解决了动态数据流挖掘最大的难题——数据存储；对优化的待分类数据使用all-贝叶斯分类
1202011,47(8) Computer Engineering and Applications计算机工程与应用 3滑动窗中的贝叶斯分类挖掘 屮,读取该数据记录,沿着增量存储树进行查找该数据,如果 数据挖掘分类方法一般分为两个步骤:第1步根据一组己存储树中已存在该数据,则对应的 rootcount-+1, attrcount+1, 知目标类别的训练样本生成一个分类器,用以描述数据属性 valuecount+1, classcoun+1,如果存储树中不存在该数据,则生 与目标类别的概念;第2步则根据前面生成的分类器对其他未成属性A,生成属性A,生成类别叶子节点C,使 rootcoun 经分类的测试数据进行分类,以评估由第1步所生成的分类器1, attrcour=1, valuecount==1, classcount=1 的精度。分类方法根据训练样本荻取方式的不同,分为增量 (2)随着数据的快速产生,现实世界中的训练样本数据几 式和非增量式两种。其中非增量式方法是当数据全部准备好乎已无法一次全部获得,而是以数据流的方式不断产生,每当 后,再根据全部训练样本进行学习。而增量式方法则是在训新数据到达时,采用样本增量方式不断生成动态增量存储 练样本不能一次全部获取的情况下,先利用已获得的样本建树。构建增量存储树的过程同上 立分类器,再用新到的样本修正之前的分类器,以使分类器能 动态增量存储树打破了训练集记录存储的方式,大大缩 够适应最新的环境。在数据流挖掘分类方法的应用上,如电减了存储空间,从而解决了动态数据流的存储问题。该树具 子邮件的区分、个性化网站、电脑入侵检测等,因为无法在一有四层,ro作为根节点,属性A作为树的第二层节点,属性 个分类器建立完成前获取到所有适合用来做训练样本的数的值A作为树的第三层,类别C属性作为叶子节点。假设 据,因此必须采用增量式方法。 提出的动态数据流的贝叶斯分类挖掘算法:以滑功窗/训练样本有m个类C1,C2…,Cm,有n个属性A1A2,…,A,, 中的基本窗口为计算单位,每一个数据块作为一个基本窗 每个属性的取值可以离散化为r,该存储树所占用的空间复杂 口。首先,采用初始训练集牛成初始的增量存储树,后续到达度为O(mxnx),对J末知样本进行贝叶斯分类时,查找时间 的流式増量训练集对増量存储树进行不断更新,该存储结构 复杂度也为OⅧm×n×)。假设该数据流存储在文本中,则占 从根本上解决了数据流训练样本的存储问题。其次,根据贝用空间为On),对于O()的数据,首先在存储方面是无法接 叶斯分类的属性独立性要求,算法采用 Bootstrap方法对窗口受的,在数据查询时更是无法满足快速分类的需求。由此看 中的待分类数据集属性进行筛选,对多重共线的属性进行删见增量存储树结构在存储数据空间和数据杳询时间方面解决 除,一方面满足了贝叶斯要求属性间的独立性要求,而且大大了动态数据流数据量大的难题。 降低了算法运行期间的内存开销和时间开销,提高了算法的32待分类数据的自助抽样 执行效率。最后对处理后的待分类数据集运用贝叶斯分类算 待分类数据的自助抽样属于数据挖掘的数据预处理阶 法,算法结合训练集存储树中的数据对待分类数据进行分类,段。自助拙样是以滑动窗口屮的基本窗口为最基本单位,采 实现了动态数据流的分类挖掘。图3是第法流程图 用 Bootstrap方法对数据的属性进行筛选,以实现数据的优 流式增量训练集 化。设标准化的原始样本集为Snx(p+1)],其中自变量观测 分类结果 矩阵为xx=(x1x2,…x),因变量观测矩阵为Y21=() 初始训练集-动态增量存储树 叶斯分类 (i=1.2,…,n)。自助抽样的过程如下 待分数据集 →自助抽样 (1)由原始数据建立偏最小二乘回归模型:y=1x1+ 图3算法流程图 B2x2+…+Bx,拟检验的H设H0:B1=0,H1:B≠0,其 3.1流式训练集构建动态增量存储树 中产1,2,…,P。 根据 Bayesian算法的特点,在计算P(XC)时,算法使用 (2)在S中随机抽取一个样本点(10,xm,x,…x),记其 的是分类和某个属性的乘积即:P(XC)=P(xAC),这样, 数值后再放回S,然后再抽取第二个,记其数值后再放回。这样 重复n2次,得到一个 Bootstrap样本S"=by1,x1,xB,…,x), 只要把数据俫存成分类类别与各个属性的树,就可以实现 Bayesian算法的存储要求,于是提出了数据的增量存储树结其中;=1,2,…,n2(本文n2等于n,当建模的样本点个数较多 构。增量存储树的生成过程如下 时,可以适当减小其数值) (1)采用初始训练样本构建增量存储树,数据流入滑动窗 (3)以 Bootstrap样本作偏最小二乘回归,得到模型:j 口,对每个基本窗口数据生成增量存储树: BI,+B2x2 +B ①初始化k-增量存储树,根节点为( kroot,O);初始化ll 4)重复步骤(2)(3)共K次,得到K组偏最小二乘回归系 增量存储树,根节点为( allroot,0)。 数{0,p,…),其中k=1,2,…,K。一般而言,随着B ②对于k增量存储树把数据存储到k存储树中,读取该的增大,佔计的精度也会相应提高,在K大于1200时,虽然求 数据记录,沿着增量存储树进行查找该数据,如果存储树中已得的系数临界值有微小差异但所选变量不再发生变化。 存在该数据,则对应的 rooicount+1,n1+1,m+1,l2+1;如果 (5)记 6其中b=12,…,B;=1,2,…,P 存储树中不存在该数据则生成属性A1,生成属性A,生成类 别叶子节点C且使moy-1,n=1,m-1,41-1;如果故检验水平为0a1,将排序后取位于K处的值() 滑动窗口的数据已满,当有新到的基本窗口时,使n1=m1-1,… 作为拒绝城的临界值。 几1,mk=m ,lk=lk-1,…,l=l1,n1=0,m1=0 (6)判别住则为:如果|>B(a),则拒绝H假设,B显 1=0。当新窗口的数据记录进入时,使n1=1,m1=1,1=1 著不为0.自变量x,通过显著性检验,予以保留;否则.不拒绝 ③3对于al增量存储树把数据存储到 allrooti增量存储树H设,自变量x,未通过显著性检验,予以舍去。将所有通 琚春华,殷贤君,许翀寰:结合自助抽样的动态数据流贝叶斯分类算法 2011,47(8)121 过显著性检验的自变量重新与因变量建立回归方程,重复步 实验2给出了算法所需运行时间的比较,结果如图5所 骤(1)~(6),直到剩下的所有变量都通过显著性检验,通过检示。a值越小算法运行所需的时间越大。这是因为a值越小, 验的变量就是建立估测模型的最优变量。 生成的存储树越大,在算法执行时,遍历搜索耗时越多,从而 33待分类数据的贝叶斯分类 使时间开销越大 数据的贝叶斯分类的工作过程如下 a=0.3a=0.5·a=0.7 (1)每个待分类数据一个n维特征向量X={x1,x2…,x 表示,分别描述对n个属性A,A2,…,A,样本的n个度量 数据进入第一个基本窗口,设检验水平为a,对向量X运用基 于偏最小二乘回归的 Bootstrap变量筛选方法,得到新的分类 02030405060708090 数据流大小MB 数据向量X 图5运行时间图 (2)分别用存储树al-增量存储树和k-增量存储树的数据 实验3给出了算法的分类挖掘结果准确度受参数p的影 作为待分类数据X={x,x2,…,x}的训练集样本 响,结果如图6所示,在采用分类器和k分类器分别对未知 (3)分别计算待分类数据在l增量存储树和k增量存储样本进行分类得到概率P、P"。设参数p,p<,则木知样本 树中的P(C),类的先验概率可以用P(C)=s/s计算,其中s 是类C中的训练样本数而s是训练样本总数。 X属于C的概率为P=(P阱+P(1-p),越小则a分类 (4)分别计算待分类数据在a增量存储树和k增量存储器的分类结果所占的比重越小,k分类器的分类结果所占的比 重越大,分类的结果受最近训练样本的影响比较大;反之亦 树中的P(XC): 然。所以要想使得分类的算法更高,p的取值非常关健。 P(XC)=P(x IC) 100 其中概率P(x1C),P(x2C)…,P(xC)可以由训练样本估值。 E-FPMFI (5分别计算待分类数据在al增量存储树和k-增量存储 树中的P(CX),根据朴素贝叶斯分类定理得: 泜0010.20.3040.50.6070809 参数P P(CIX) P(XCp(C) 图6结果精确度图 P(X) 对未知样本X分类,由于P(X)对于所有类为常数也就是5结语 对每个类C计算P(XC)P(C)。样本X被指派到类C,当且 提出了一种在薮据流上基于自助抽样的贝叶斯分类挖掘 仅当PCX)>PCA),1s/≤m,≠1。换而言之,x被指派到算法,该算法根据动态数据流的特性,使用滑动窗口技术,从 其P(HC)P(C)最大的类C1。 而可以使无限数据在以窗口基本单位的范围内进行分析处 (6计算未知样本所属概率P。l1类器对未知样本进理。为了解决数据流的存储问题结合贝叶斯算法的特点,创 行分类得到概率P1(P为类别C对应的概率),k分类器对样 新性地提岀了增量存储树概念,该树解决了具有无限、不间断 特点的训练样本(记录的空间复杂度为n)存储问题,利用该 本进行分类得到概率P(P为类别C对应的概率)。设参数, 存储树在无信息丢失的前提下,使动态流式训练集的存储空 p<1,则未知样本X属于C的概率为P=(P1阱+P(1-p))。间复杂度降到 O(m anxI),对于未知样本进行贝叶斯分类时, 查找时问复杂度也为 O(m anxI)。采用自助抽样方法对待分 4“实验测试 类数据属性进行筛选,解决了属性间多重共线问题,大大提髙 使用Ⅴ isual c艹编程语言实现,实验环境为 Intel o了贝叶斯分类的效率。实验测试的结构证明基于自助抽样的 Core-2 DuO CPU E7200a2.53GHz,2.00GB的内存。Red-贝叶斯分类挖掘算法,具有很好的时效性和精确度。虽然结 ha90操作系统。采用数据是 IBM Almamen Quest研究小组合贝叶斯分类算法特点,实现了数据流无丢失存储但这种存 开发的数据产生器产生的数据集。设滑动窗口的大小容纳2储打破了原有的数据记录,该存储方式对于以记录为单位的 万条记录。实验分别从算法的内存雷求算法运行时间、算法其他分类算法是不可行的。所以针付如何更高质量地存储动 准确度三个方面进行比较和分析。 态数据流数据仍是接下来需要探讨的工作。 实验1比较算法所使用的内存大小的情况,结果如图4所 示,数据筛选算法的检验水平a值越小所消耗的内存越大。因参考文献: 为α越小,样本数据的属性就越多,在使用存储树存储数据时, Widmer G, Kubat M. Learning in the presence of concept drift 所占用的空间越大,算法执行时内存消耗越大 and hidden contexts[J]. Machine Learning, 1996, 23(1): 69-101 [2] Hulten G, Spencer L, Domingos P. Mir a=0.3 至A==07 streams[C]i/Proc of the Int'I Conf on Knowledge Discovery and Data Mining. New York: ACM Press, 2001: 97-106 [3 Wang Hai-xun, Han Jia-wei Mining concept-drifting data streams using ensemble classifiers[C] /Proc of the Int'I Conf on Knowl- 02030405060708090 数据流大小/MB cdgc Discovcry and Data Mining. Ncw York: ACM Prcss, 2003 图4内存消耗图 (下转142页)