计算机类论文范文半监督学习的数据流混合集成分类算法

　　数据流分析和挖掘在数据挖掘和机器学习领域是一个具有挑战性的研究，它已经受到了计算机智能研究者的广泛关注[1-3]。与传统的静态数据相比，数据流具有动态性、高维度、实时性、无限性、顺序性和高速到达等特点[4]，正是这些特点使得传统方法难以实现数据流的挖掘。而数据流分类是数据流挖掘的其中一种，它是从大量数据样本中提取知识和信息的过程，而这些样本中隐含的概念和知识可能随着时间和环境不断的发生变化，即存在的概念漂移[5]给研究带来了挑战。因此，一个高效的数据流分类算法需要在有限的时间和内存下以相当好的准确度完成任务，并且能够自适应地处理概念漂移。

　　摘要：当前已有的数据流分类模型都需要大量已标记样本来进行训练，但在实际应用中，对大量样本标记的成本相对较高。针对此问题，提出了一种基于半监督学习的数据流混合集成分类算法SMEClass，选用混合模式来组织基础分类器，用K个决策树分类器投票表决为未标记数据添加标记，以提高数据类标的置信度，增强集成分类器的准确度，同时加入一个贝叶斯分类器来有效减少标记过程中产生的噪音数据。实验结果显示，SMEClass算法与最新基于半监督学习的集成分类算法相比，其准确率有所提高，在运行时间和抗噪能力方面有明显优势。

　　关键词：数据流,半监督学习,集成分类,概念漂移,混合集成

　　在已有研究中，解决概念漂移问题的方法概括起来有三种[6]：实例选择、实例加权和集成学习。近年来研究最热的当属集成学习方法[7-9]，它克服了运用滑动窗口方法参数难以确定的缺陷。尽管集成学习已经取得了相当客观的研究进展，但它是典型的有监督学习，需要大量的类标数据进行训练学习。而且标记数据是一个耗时又费力的工作，因此便有了近年来半监督学习的研究[10-12]，它通过引入未标记数据来提高分类器的泛化性能。可以说近年来集成学习和半监督学习的研究都有了新的突破，但将两者融合来改善分类性能的研究还是凤毛麟角。2002年Bennett等人[13]提出使用标记和未标记数据共同构造集成分类模型，文中主要运用Boosting方法，它的缺点在于没有一种机制来控制对无类标数据标记的错误率；在文献[14]中Woolam等人融合半监督聚类和集成方法先将无类标数据进行标记，当标记数据占到一定比例时再对数据进行聚类，再运用类标传播技术为剩余无类标数据进行标记，最后更新集成分类器，这样当数据量很大时类标传播会耗费[Ο（n3）]的时间。

　　基于上述研究中存在的缺陷，该文将集成学习和半监督学习有效的融合，提出一种基于半监督学习的混合集成分类算法（Semi-SupervisedlearningBasedMixtureEnsembleClassifier，SMEClass），由于引入未标记数据，使得集成分类器的准确性和泛化性都得到了改善，而且在对未标记数据进行标记时使用集成分类器和在数据块已有的类标数据集上训练的分类器一同进行多数投票，更增加了被标记数据的可信度。同时，在算法中也使用了概念漂移检测和噪声过滤的机制，以便能够更有效的适应含噪音和概念漂移的数据流分类。

　　1SMEClass算法模型的训练和分类的流程

　　数据流分类挖掘面临着两大难题，一是概念漂移和噪音的影响，二是数据流实例标记的高额代价，很少有算法能高效地实现两者的兼顾，因此在标记样本少的情况下，既能兼顾概念漂移和噪音影响，又能确保分类的精度将是一个挑战，SMEClass能够解决这些问题，它假设数据流中的样本数据有一部分是随机标注的，然后使用我们的集成方法来对这些数据中的未标记实例进行标记，以增加分类的性能，而且在训练过程中进行了漂移监测和噪音过滤。

　　由于数据流的特性，在此算法中使用C4.5和Na?veBayes作为基础分类器来构建混合集成模型，在每个数据块上使用类似于self-training的方法来进行半监督学习。

　　首先对方法中涉及到的符号进行说明：如表1所示。

　　2SMEClass算法

　　2.1算法的合理性论证

　　数据块到达后，用其中的有标记数据训练一个C4.5分类器，使用这个分类器和集成分类器一同对未标记数据进行预测，如果预测错误率小于随机错误率，则将这个预测类标作为此数据的类标记。在最坏的情况下，当有噪音实例时，如果拥有足够的类标数据，就能降低分类的错误率，为了达到这样的效果，借鉴了文献[16]中的思想。

　　2.2算法的执行过程

　　3数据流变化的检测和识别

　　3.1概念漂移的检测

　　3.2噪声数据的过滤

　　为了降低噪音数据对概念漂移检测的影响，集成模型中增加了一个朴素贝叶斯分类器，这是因为Na?veBayes算法简单、速度快、准确率高，还有一个重要的特性就是对噪音数据相当敏感，利用它的统计特性，能够及时地发现数据中的噪音，以达到噪音过滤的效果。

　　使用这个计算方法，在[K+1]个分类器进行投票时，如果实例被一半以上的决策树分类器和Na?veBayes分类器同时分类错误，那么概念就存在潜在的漂移，将分类错误的实例放入缓冲区；反之，认为是噪音，不用其构建新的分类器，这样就减少了那些噪音数据对漂移检测的影响。

　　4实验及结果分析

　　基于人工数据集、UCI提供的真实数据集和已有的半监督集成分类方法SEClass[15]进行对比测试。分别从算法的准确率、运行时间和可扩展性三个方面验证SMEClass方法的有效性。实验运行环境为：1.73GHz英特尔奔腾双核PC机，1GB内存，WindowsXP操作系统。

　　为了实现算法，在实验中使用MOA平台，SMEClass的参数设置如下：[K=8]（基分类器个数），[d=5000]（数据块大小）；SEClass参数如下：[L=8]（基分类器个数），[K=50]（微簇个数），[M=5000]，[e=0.9]。采用先测试再训练的顺序，这样可以有效显示模型的泛化能力。人工数据集包括HyperPlane、RandomRBF、RandomTree、SEA和Waveform。具体构造见文献[9]，真实数据集采用UCI提供的ForestCovertype。

　　表2显示了数据集的相关信息，这里对数据集分成大小固定为1000的数据块，使他们分批到达来模拟数据流的特性。

　　4.1算法准确率分析

　　算法的准确率如表3所示，由于现实生活中获得已标记数据代价太大，在实验数据集中我们只利用[20%]的已标记数据，其余[80%]的数据是未标记的，而且在实验过程中增加了噪音数据和噪音属性，以测试SMEClass算法对噪音数据的过滤能力和对含噪音属性数据集的学习能力。

　　由于文献[15]中有两个属性权值处理方式，SEClass-I在训练中不调整属性权值，SEClass-II在训练迭代过程中动态调整属性权值，通过对比实验结果可以发现SMEClass和SEClass-II的准确率较高，由于SEClass-II动态调整属性权值可以减少噪音属性的影响，而SMEClass是采用的C4.5决策树分类模型，也能实现这一点，叶节点在分裂的过程中会选择具有最大增益率的属性进行分裂，这样每次都能选择最重要的属性。而且SMEClass采用的贝叶斯分类器还能够有效降低噪音数据对准确度的影响，而SEClass没有考虑噪音数据的影响，因此在同时含有噪音属性和噪音数据的情况下，SMEClass的分类准确率要略胜一筹。

　　4.2算法的运行时间和可扩展性

　　在人工数据集RandomRBF上测试SMEClass算法和SEClass算法，改变数据集的属性维度[d]来测试两个算法在高维数据情况下的运行时间，从而检验算法的可扩展性。实验结果如图2所示，纵坐标代表算法训练时间和测试时间之和。

　　观察实验结果，两个算法的运行时间都随属性量的增加呈线性增长趋势，这是因为在训练基本分类器和测试过程中他们都是和属性数量成线性关系的，但SMEClass的时间明显少于SEClass，这是因为SEClass算法在聚类过程中需要频繁计算实例间的距离，浪费了大量的时间，而SMEClass算法不存在这样的问题，因此在时间上有明显优势。这说明SMEClass算法在处理高维数据流时比较稳定，具有良好的可扩展性。

　　5结束语

　　针对数据流类标数据获取困难这一现状，该文提出将集成学习和半监督学习有效结合的一种分类算法SMEClass，算法在数据块上采用类似于self-training的学习方法将置信度高的无类标数据赋予标记后加入类标集来改善基分类器的性能，由于在标记过程中使用了集成分类器的多数投票机制，这使加入的无类标数据更加可靠，而且增加了一个Na?veBayes分类器用来去除数据所含噪音，及时更新集成分类器以适应概念漂移。

　　实验表明，与基于聚类的半监督数据流集成分类算法SEClass相比，SMEClass算法具有更高的准确度和较强的抗噪性，而且免去了存储大量微簇的空间，且运行时间随属性维度的增加呈现线性增长，具有一定的可扩展性，因此本文的算法能够用于高维数据流分类问题。

　　参考文献：

　　[1]LiaoSH，ChuPH，HsiaoPY.Dataminingtechniquesandapplications-Adecadereviewfrom2000to2011[J].ExpertSystemswithApplications，2012，39（12）：11303–11311.

　　[2]ReadJ，BifetA，HolmesG，PfahRINGERB.Scalableandefficientmulti-labelclassificationforevolvingdatastreams[J].MachineLearning，2012，88（1-2），243–272.

　　[3]白雪冰，王宝军.数据流分类算法分析[J].电脑知识与技术，2012，8（11）：2445-2446.

　　[4]ZliobaiteI.Learningunderconceptdrift：anoverview[R/OL].Technicalreport，VilniusUniversity，2009.http：//arxiv.org/pdf/1010.4784v1pdf.

　　[5]WidmerG，KubatM.Learninginthepresenceofconceptdriftandhiddencontexts[J].MachineLearning，1996，23（1）：69-101.

　　[6]HoS-s，WechslerH.AMartingaleframeworkfordetectingchangesindatastreamsbytestingexchangeability[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，2010，32（12）：2113-2127.

　　[7]ScholzM，KlinkenbergR.AnEnsembleClassifierforDriftingConcepts[C]//Proceedingsofthe2ndInternationalWorkshoponKnowledgeDiscoveryinData

　　Streams.Portugal：Porto，2005：53-64.

　　[8]AggarwalCC，HanJ，WangJY，etal.AFrameworkforOn-DemandClassificationofEvolvingDataStreams[J].IEEETransactionsonKnowledgeandDataEngineering，2006，18（5）：577-589.[9]BieftA，HolmesG，PfahringerB，etal.NewEnsembleMethodsforEvolvingDataStreams[C]//Proceedingsofthe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMing.France：Paris，2009：139-148.

　　[10]ChapelleO，ScholkopfB，ZienA，editors.Semi-SupervisedLearning[M].Cambridge：MITPress，2006.

　　[11]ZhuX.Semi-supervisedlearningliteraturesurvey[R/OL].TechnicalReport1530，DepartmentofComputerSciences，UniversityofWisconsinatMadison，2006.http：//www.cs.wisc.edu/jerryzhu/pub/ssl_survey.pdf.

　　[12]ZhouZH，LiM.Semi-supervisedlearningbydisagreement[J].KnowledgeandInformationSystems，2010，24（3）：415-439.

　　[13]BennettK，DemirizA，MaclinR.Exploitingunlabeleddatainensemblemethods[C]//Proceedingsofthe8thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.Canada：Edmonton，2002：289–296.