基于半监督学习的数据流分类算法VIP免费

基于半监督学习的数据流分类方法黄树成1,2朱宇光2董逸生11(东南大学计算机科学与工程学院，南京210096)2(常州工学院计算机科学与工程系，江苏常州213006)(schuang6@sohu.com)摘要在数据流上建立有效的分类模型具有许多应用。流数据的动态性给业界提出了两个关键问题：如何监测数据流的变化；一旦发生显著变化,如何高效地组织足够的训练数据,调整无效的模型。本文提出了一个基于半监督学习的分类算法，较好地解决了这些问题。设计了一种识别显著变化的可靠方法；提出了一个基于NaïveBayes的EM算法，利用较少的类标数据来扩大训练数据集，从而极大地降低类标数据的需求量。基于新的训练数据可以构建一个有效的分类器。实验结果证明了算法的优势。关键词数据流分类；显著变化；类标数据；半监督学习；基于NaïveBayes的EM算法。中图法分类号TP311.13Semi-supervisedLearningBasedApproachforClassifyingDataStreamsHuangShucheng1,2DonyYisheng11(SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing,210096)2(DepartmentofComputerScienceandEngineering,ChangzhouInstituteofTechnology,JiangsuChangzhou,213006)AbstractMiningondatastreamsandconstructingaclassificationmodelhasfoundmanyapplications.Thedynamicnatureofstreamingdataposestwokeyissuesfacingassociatedcommunities:oneishowtomonitorthepotentialchangesoccurringindatastreams,andtheotherishowtocollectsufficientlabeleddatatoadjusttheoutdatedmodelforadaptingtosignificantchanges.Inthispaper,asemi-supervisedlearningbasedalgorithmisproposedtoattacktheseproblems.Wedeviseareliablemethodformonitoranddifferingsignificantchangesfromnoisychanges.Wheneverthesignificantchangespresent,anEMwithnaïveBayesalgorithmisemployedtoaugmentcurrentlyinsufficientlabeleddataintoasufficienttrainingdataset.Sotheneedforlabeleddataissharplyreduced,andaneffectiveclassifiercanbegeneratedbasedonthenewtrainingdata.Experimentresultsconfirmtheadvantagesofthealgorithm.KeywordsDataStreamsClassification;SignificantChanges;LabeledData;Semi-supervisedLearning;EMwithNaïveBayesAlgorithm.1.引言数据流挖掘是一个研究热点[1]。数据流的动态性给数据流分类提出了极大的挑战，关键是如何监测潜在的变化和组织新的训练数据响应数据流发生的变化。许多数据流分类方法，比如[2，3，4]，假设类标数据容易获得且随时可以挖掘。但在实际应用中，数据的类标很难及时得到。WeiF.等人在[5，6]中提出主动挖掘的思想，但检测变化的方法缺乏可靠性，而且模型的更新依赖于类标数据的数量。我们提出了一种识别变化的方法和一种基于NaïveBayes的EM算法，可以降低更新分类模型对类标数据的需求量。实验证明了算法的优点。2.数据流变化的监测和识别2.1显著变化和噪声变化假设一个由两类：“+”和“-”数据组成的数据流，如图1,按时间顺序将它分成若干数据块，当前正处于时刻,的分类模型为一个决策树，如图2所示。为了简单起见，图中仅给出四个叶子节点。每个叶子节点包含相应的分类信息，比如表示第二个叶子节点将所有到达它的个对象以概率的准确率分成“-”类，。对整个的平均分类错误率可计算为：。对于数据块来说，为性能最优的分类器，满足，其中为预定的错误率上界，大于上界的分类器无效。相比于，可能发生一定的变化。衡量是否为显著变化的最终标准是变化是否导致对的分类错误率大于。如果，我们称为显著变化，否则为噪声变化。2.2显著变化的识别为了可靠地识别显著变化，我们必须计算：(1)在等式(1)中，如果可知，那么可以很容易地计算出。取的随机样本，使用对其所有对象预测可以得到；但依赖于的真实类标，无法容易地获得，我们用代替，计算的估计值。当，为预定的阈值，22(,)iinp33(,)iinp11(,)iinp44(,)iinp图2决策树分类器概略图图1一个数据流示意图可能发生了显著变化，有必要进一步验证该可疑变化的真实性。验证变化最直接、有效的方法是利用数据的真实类标。使...