基于半监督学习的数据流分类算法.doc

基于半监督学习的数据流分类方法黄树成1,2 朱宇光2 董逸生1 1(东南大学计算机科学与工程学院，南京210096)2(常州工学院计算机科学与工程系，江苏常州 213006)()摘要 在数据流上建立有效的分类模型具有许多应用。流数据的动态性给业界提出了两个关键问题：如何监测数据流的变化；一旦发生显著变化,如何高效地组织足够的训练数据,调整无效的模型。本文提出了一个基于半监督学习的分类算法，较好地解决了这些问题。设计了一种识别显著变化的可靠方法；提出了一个基于Nave Bayes的EM算法，利用较少的类标数据来扩大训练数据集，从而极大地降低类标数据的需求量。基于新的训练数据可以构建一个有效的分类器。实验结果证明了算法的优势。关键词 数据流分类；显著变化；类标数据；半监督学习；基于Nave Bayes的EM算法。中图法分类号 TP311.13 Semi-supervised Learning Based Approach for Classifying Data StreamsHuang Shucheng1,2 Dony Yisheng11(School of Computer Science and Engineering, Southeast University, Nanjing, 210096)2(Department of Computer Science and Engineering, Changzhou Institute of Technology, Jiangsu Changzhou, 213006)Abstract Mining on data streams and constructing a classification model has found many applications. The dynamic nature of streaming data poses two key issues facing associated communities: one is how to monitor the potential changes occurring in data streams, and the other is how to collect sufficient labeled data to adjust the outdated model for adapting to significant changes. In this paper, a semi-supervised learning based algorithm is proposed to attack these problems. We devise a reliable method for monitor and differing significant changes from noisy changes. Whenever the significant changes present, an EM with nave Bayes algorithm is employed to augment currently insufficient labeled data into a sufficient training data set. So the need for labeled data is sharply reduced, and an effective classifier can be generated based on the new training data. Experiment results confirm the advantages of the algorithm.Keywords Data Streams Classification; Significant Changes; Labeled Data; Semi-supervised Learning; EM with Nave Bayes Algorithm.1.引言 数据流挖掘是一个研究热点1。数据流的动态性给数据流分类提出了极大的挑战，关键是如何监测潜在的变化和组织新的训练数据响应数据流发生的变化。许多数据流分类方法，比如2，3，4，假设类标数据容易获得且随时可以挖掘。但在实际应用中，数据的类标很难及时得到。Wei F.等人在5，6中提出主动挖掘的思想，但检测变化的方法缺乏可靠性，而且模型的更新依赖于类标数据的数量。我们提出了一种识别变化的方法和一种基于Nave Bayes的EM算法，可以降低更新分类模型对类标数据的需求量。实验证明了算法的优点。2. 数据流变化的监测和识别 2.1 显著变化和噪声变化假设一个由两类：“+”和“-”数据组成的数据流，如图1,按时间顺序将它分成若干数据块，当前正处于时刻,的分类模型为一个决策树，如图2所示。为了简单起见，图中仅给出四个叶子节点。每个叶子节点包含相应的分类信息，比如表示第二个叶子节点将所有到达它的个对象以概率的准确率分成“-”类，。对整个的平均分类错误率可计算为：。对于数据块来说，为性能最优的分类器，满足，其中为预定的错误率上界，大于上界的分类器无效。相比于，可能发生一定的变化。衡量是否为显著变化的最终标准是变化是否导致对的分类错误率大于。如果，我们称为显著变化，否则为噪声变化。 图1 一个数据流示意图 图2 决策树分类器概略图2.2 显著变化的识别为了可靠地识别显著变化，我们必须计算： (1)在等式(1)中，如果可知，那么可以很容易地计算出。取的随机样本，使用对其所有对象预测可以得到；但依赖于的真实类标，无法容易地获得，我们用代替，计算的估计值。当，为预定的阈值，可能发生了显著变化，有必要进一步验证该可疑变化的真实性。验证变化最直接、有效的方法是利用数据的真实类标。使用适当的资源，从选取部分数据，形成一个子集，为对的预测类标，的大小取决于可用的标记资源。确定中每一个对象的真实类标，得到类标数据集，为的真实类标。利用和可以直接计算：(2)，。如果成立，可以认为发生了显著变化，模型对无效，必须收集足够的训练数据集构建新的模型。3. 半监督学习方法 本节研究利用半监督学习算法来扩大，从而降低类标数据的需求量，提高的分类性能。常用的半监督学习方法有：基于产生式模型的EM算法7、Co-training8、支持向量机9和基于图的方法10。我们采用EM算法来估计数据的类标，产生式模型选用朴素Nave Bayes分类器，它基于以下假定：（1）一个数据流由参数未知的混合分布产生；（2）混合成员和数据类标之间一一对应，一类数据对应一个分布模型；（3）描述对象的属性条件独立于给定的类标。3.1 数据流的产生式模型根据上面的三个假设，一个数据流可以表示为参数集的混合分布模型，每一个混合成员可用不相交的子集表示，对应于一个类标。任一个对象的产生过程是：首先根据类概率分布模型选择一个混合成员分布，然后根据该成员的分布模型生成该对象。对象的似然性为所有混合成员的概率和： (3)在(3)式中，第一项表示第个混合成员，即第类，因为它们一一对应，可以相互表示。如果一个对象由第个混合成员产生，那么它的类标为，所有混合成员表示成参数。式中第二项可以进一步展开： (4)如果描述对象的属性为，根据假设（3）可以将等式(3)简化成：（5）式中表示对象第个属性的取值。将看着相应的参数，混合模型的所有参数可以表示为：，根据这些参数，我们可以推导出一个产生式分类模型。实际应用中，假设（3）一般不成立，而且属性中存在许多冗余属性。我们利用决策树分类模型删除冗余的属性，不但可以降低参数的计算量，而且余下的属性大概满足假设（3），我们称这些属性为不相关主成分属性。定义1 在一个分类问题中，所有的预测属性为。对于一个决策树分类器，每一个内部节点（非叶子节点）对应一个测试属性，所有测试属性称为不相关主成分属性。“主成分”是指任一对象的类标可由这些属性近似地确定。从决策树的根节点开始，根据测试的结果一直到达某个叶子节点，形成一条测试路径，路径上的属性互不相同；“不相关”是指这些属性类条件独立，即同一条测试路径上的所有属性相互独立：。所有其它属性称为次级属性。3.2 一个基于Nave Bayes的轻量级EM算法下面是一个基于Nave Bayes的EM算法： 算法1 一个基于Nave Bayes的EM算法。输入: 类标数据集和无类标数据集。输出: 最终的训练数据集。第一步：初始化。第二步：在上建立一个初始的Nave Bayes 分类器。第三步：循环执行下面EM算法的两个基本步骤，直至无显著的变化。. E-step. 使用当前的分类器预测中的数据类标，将预测结果的置信度高于一定阈值的对象加入到。. M-setp. 在扩大的训练数据集上重新构建最优分类器。 算法首先进行一些必要的初始化。给中的每一个对象赋予最大的权重值1，产生一个带权重的全类标数据集；一个无类标数据集，一个半类标数据集。然后，在上建立一个初始的Nave Bayes分类器，这等价于利用估计产生式模型的参数。假设极大后验似然估计值为，中的各个参数可以通过计数的频率比估计：为所有类标为的对象中属性的值为的个数除以取不同值的总数，具体的计算公式为:(6)式(6)中的相当于一个指示器，它的值取决于第个对象的类标。如果类标满足，那么，否则；同样，当时，否则。采用类似的方法可以估计出：。利用参数的估计值和贝叶斯法则可以推导出一个朴素的贝叶斯分类器：(7)。分别用等式(3)和(5)替换(7)式中相应的项，分类器变成：根据不相关主成分属性的定义和性质，一个对象，代表它的第个属性，可以通过忽略其次级属性近似地简化为。因而，分类器可以极大地简化成：和相比，计算简化后分类器的成本大大地降低了。利用分类器计算中每个对象类标的最优预测值，产生另外一个数据集，为对象类标的预测结果，代表被正确预测的概率或置信度。和具有真实类标的对象相比，称为半类标数据。一个半类标对象的权重，为预定的阈值，将它加入到半类标数据集中：。这就是EM算法中所谓的E步骤。接下来执行EM算法的M步骤。主要是利用重建最优分类器：。这两个基本步骤被迭代地执行直至输出一个扩大了的训练数据集。 在上重建代替，有效地适应显著变化。4 实验结果 我们在模拟的流数据上做了若干试验，结果表明：提出的半监督方法可以有效地适应显著变化，大大地降低更新模型对类标数据的需求量；利用无类标数据可以较大地提高分类的准确率，特别是类标数据严重不足的情况。 模拟的流数据和文献7中的类似，每一个对象被看作维空间的一个点。存在一个超平面，为权重，将空间一分为二，位于上方的点，即被看着“+”类型；下方的点为“-”类型。当时，将空间近似地分成二等分。可以通过下面的方法来模拟数据流的变化：或者通过改变权重，从而改变的位置或方向；或者通过增加或减少某些数据点；或者通过另一个超平面来实现。 初始时，随机地在范围取值，。首先产生一个充足的初始训练数据集，建立一个初始决策树，接着按递增的变化速率产生一系列数据块。为了便于比较，在每一个数据块上组织三个大小不同的类标数据集，分别为该数据块构建三个决策树：一个是基于100个较充足类标数据的基模型；一个是在20个类标数据和200个无类标数据上采用我们方法的半监督模型；另一个是在60个类标数据上采用文献8中方法的主动模型。加上初始模型，四个模型的分类错误率如图3，结果正如期望的那样：随着变化速率的递增，建立在初始训练数据集上的初始模型的分类错误率也近似地递增，建立在较多类标数据上的主动模型性能近似于初始模型；而建立在较充足类标数据上的基模型性能最好且很稳定，我们的半监督模型性能近似于基模型。图3 不同模型的性能比较5 结束语数据流分类具有重要的理论意义和实际应用价值。我们提出了一个基于半监督学习的方法，可以在时变的数据流上保持一个自适应的决策树分类器。其中，监测数据流变化的方法能可靠地识别出显著变化；基于Nave Bayes的EM算法可以高效地适应显著变化。算法不依赖于额外的标记成本，利用无类标数据来扩大训练数据集，解决类标数据不足的问题，大大地提高了模型的分类性能。实验结果证明了方法的优势。参 考 文 献1 B Babcock, S Babu, et al. Models and Issues in Data Streams. In: Proc of ACM symposium on Principles of Database Systems. New York: ACM Press, 2002. 1162 W Fan. StreamMiner: A classifier ensemble-based engine to mine concept-drifting data streams. In:Proc of the 30th VLDB Conference. Toronto: ACM Press, 2004. 125712603 G Hulten, L Spencer, et al. Mining time-changing data streams. In: Proc of Intl Conf on Knowledge Discovery and Data Mining. San Francisco: ACM Press, 2001. 97106 4 Z Jeremy, A Marcus. Using Additive Expert Ensembles to Cope with Concept Drift. In: Proc of Intl Conf on Machine Learning. New York: ACM Press, 2005. 4494565 F Wei, Y Huang, et al. Active mining of data streams. In: Proc of Fourth SIAM Intl Conf on Data Mining. Florida: IEEE Computer Press，2004. 457-4616 F Wei, Y Huang, et al. Decision tree evolution using limited number of labeled data Items from drifting data streams. In: Proc of the 4th IEEE Intl Conf on Data Mining. Brighton, UK: IEEE Computer Press, 2004. 379-382 7 K Nigam. Using unlabeled data to improve text classification: Ph D dissertation. Pittsburgh: Ca