面向不完全标记数据流的集成分类算法

王中心，孙　刚，2，王　浩

（1.阜阳师范学院 计算机与信息工程学院，安徽 阜阳 236037；2.合肥工业大学 计算机与信息学院，安徽 合肥 230009）

面向不完全标记数据流的集成分类算法

王中心1，孙刚1，2，王浩1

（1.阜阳师范学院 计算机与信息工程学院，安徽 阜阳 236037；2.合肥工业大学 计算机与信息学院，安徽 合肥 230009）

实际数据流中许多数据是无标签的，且其中隐含着不同类型的概念漂移。为此，本文提出了一种面向不完全标记数据流的集成分类算法，该算法利用K均值聚类算法标记无标签实例，利用Hoeffding Bounds不等式确定的双阈值检测概念漂移，同时动态地更新分类模型以适应数据流环境的变化。实验结果表明，本文提出的算法能够在类传播过程中具有较高标记正确率，又能从噪音中识别出不同类型的概念漂移。

数据流；分类；集成模型；不完全标记；概念漂移

数据流分类在电子商务、传感器网络、网络入侵检测等实际应用领域有着广泛的应用，但是，实际应用中存在许多数据是没有类标签的。例如，Web网页中存在许多无标签的网页，网络入侵检测的数据包中存在许多无标签的数据包，电子商务网站存在许多无标签的商品评论数据。无标签数据加剧了数据流分类的难度，传统的数据挖掘分类算法和已有的数据流分类算法［1-5］对于包含许多无标签数据的数据流分类面临着严峻的挑战。已有的数据流分类算法总是假设数据流中的数据具有完整的类标签，这个假设明显和实际应用领域的情况不符；或者简单地丢弃无标签数据，仅利用数据流中有标签的数据构建分类模型，这将导致由于训练数据的不足，构建的分类模型的泛化能力不强、分类精度不高。Miller和Uyar于1997年从数据分布估计的角度已经证实，利用无标签数据的信息去构建分类模型，有助于提高分类模型的泛化能力和分类精度［6］。因此，如何利用无标签数据和有标签数据构建具有较强泛化能力和分类精度的数据流分类模型或算法已经成为不完全标记数据流分类研究的热点和难点。

针对不完全标记数据流分类问题，研究利用无标签数据和有标签数据的信息进行类标签的传播及数据流中的概念漂移检测和分类方法。本文提出一种新的不完全标记数据流集成分类算法，该算法使用K均值聚类标记无标签数据，使用支持向量机作为基分类器，采用贝叶斯分类器过滤噪音，利用Hoeffding Bounds不等式确定双阈值检测概念漂移，并用实验结果证明算法的有效性。

1　相关工作

对于不完全标记数据流的分类问题，主要是解决两个方面的问题：一是如何正确地标记数据流中的无标签数据，二是如何检测隐含在数据流中的概念漂移。基于此，学者们开展了一系列的研究。2004年Fan等提出一个基于需求驱动的数据流分类算法，该算法估计模型在新实例的损失值，如果损失值大于设定的最大阈值，则从新到来的实例中选择少量的实例重新构建模型［7］。2007 年Widyantoro等提出一个用于概念漂移学习的数据流分类算法，该算法利用无标签实例增量式地构建概念层次结构来标记无标签实例［8］。2008年Masud等提出基于半监督学习的数据流分类算法，该算法利用聚类技术形成聚类簇集合，利用聚类簇集合中的有标签实例标记无标签实例［9］。2009年Li等提出一种基于正例和无标签实例的数据流分类算法，该算法仅需利用少量的正例和无标签实例就可以构建出具有较高分类精度的分类器［10］。2010年Lindstrom等提出一种基于主动学习的数据流分类算法，该算法仅需少量的有标签实例就可以检测出概念漂移问题［11］。2011年Masud等提出一种考虑新类别检测机制的数据流分类算法，该算法可以在真实类别到来之前检测出数据流的新类别［12］。2012年徐等提出基于半监督学习的数据流集成分类算法，该算法使用聚类算法标记无标签实例，通过集成技术提高分类器的泛化能力和分类精度［13］。2014年Bertini等提出一个基于图结构的半监督数据流分类算法，通过图结构建立分类模型，利用已标签实例的类标签对无标签实例进行标记［14］。2015年熊等提出一种针对标记数据不足的数据流分类算法，选择分类置信度较低的无标签实例进行标记，极大地减少了需要人工标记的无标签实例的数量［15］。

上述的研究虽然在一定程度上解决了不完全标记数据流中的无标签实例的标记问题和概念漂移检测问题，但是忽略了不完全标记数据流中概念漂移类型的多样性和噪音问题。因此，针对这种考虑，本文提出了一种新的不完全标记数据流集成分类算法，该算法使用K均值聚类标记无标签实例，使用支持向量机作为基分类器，采用贝叶斯分类器过滤噪音，利用Hoeffding Bounds不等式确定的双阈值检测概念漂移。与经典数据流分类算法相比，本文提出的算法能在不完全标记数据流环境下正确地标记无标签实例，检测出不同类型的概念漂移，并且具有较好的分类精度。

2　面向不完全标记数据流的集成分类算法

一个好的不完全标记数据流分类算法应满足以下两个要求：1）对无标签实例，应该具有较高的标记正确率；2）对隐含在数据流中的概念漂移，应能够从噪音中检测出不同类型的概念漂移。基于此，本文提出一种面向不完全标记数据流的集成分类算法 ECDSUD（An Ensemble Classification Algorithm for Data Streams with Unlabeled Data）。它利用K均值聚类算法将实例划分成不同的聚类簇，进而利用簇中有标签实例标记无标签实例；同时，该算法利用Hoeffding Bounds不等式确定的双阈值检测概念漂移，并动态地更新分类模型以适应数据流环境的变化。实验结果表明，本文提出的面向不完全标记数据流的集成分类算法能够较准确地标记无标签实例，又能从噪音中检测出不同类型的概念漂移，并且具有较好的分类精度。

2.1ECDSUD算法框架

首先对算法中要用到的符号进行说明，D表示数据流中的当前数据块，Ei表示数据块D中第i个实例。EC表示所有支持向量机基分类器的集合，Ci表示EC中第i个基分类器，n表示EC中基分类器的总数，num表示EC中当前基分类器的个数，d表示一个数据块中实例的总数。

ECDSUD算法的具体构建过程描述如下：

图1　ECDSUD算法框架

2.2无标签实例标记方法

定义1只有满足下列条件之一，则聚类簇CLk是同质的。

定义2根据所有实例的相似度，K均值聚类把所有实例划分成K个簇｛CL1，CL2，...，CLk｝，K个簇中心表示为M=｛M1，M2，...，Mk｝，每个簇中心Mk是一个n维向量Mk=（Mk1，Mk2，…，Mkn）。dis（Em，

K均值聚类的目标就是使有标签实例和无标签实例到簇中心的欧式距离之和最小，并且，保证每个簇都是同质的。因此，这是一种基于半监督学习的K均值聚类，目标函数O（CL，M）：Mk）表示实例Em和簇中心Mk间的欧氏距离平方：

其中，Lk表示聚类簇CLk中有标签实例的集合，hk表示聚类簇CLk的同质度量函数，pkc表示聚类簇CLk中类标签为Yc的有标签实例的先验概率，则

hk的值越大，聚类簇CLk中的类别越分散；hk的值越小，聚类簇CLk中的类别越集中。当hk的值为0时，聚类簇CLk中的实例具有相同的类标签；当hk＜1-e2时，聚类簇CLk满足簇的同质性定义，则聚类簇CLk是同质的。当聚类簇CLk是同质时，使用聚类簇CLk的类标签标记无标签实例，聚类簇CLk的类标签认为就是无标签实例的类标签。

2.3概念漂移检测方法

ECDSUD算法的概念漂移检测机制是基于双阈值的检测机制，仍然是通过计算时间窗口上的分类错误率从噪音数据流中检测出不同的概念漂移。双阈值检测机制是一种有效的概念漂移检测方法。不同于其他算法中的双阈值检测方法，受参考文献［16］的启发，本文利用Hoeffding Bounds不等式确定双阈值来检测噪音数据流中的概念漂移。本文检测概念漂移方法的实现过程如下：首先计算集成分类器EC对当前和上一个数据块的分类错误率，然后计算两个数据块分类错误率的差值Δe，

其中，ec是集成分类器EC对当前数据块的分类错误率，eb是集成分分类器EC对上一个数据块的分类错误率。

假设eb和ec是独立的两个变量，都服从正态分布，根据正态分布的性质可以得出，Δe也服从正态分布。如果数据流没有发生概念漂移，那么集成分类器EC在当前数据块和上一个数据块上的概率分布应该是不变的。因此，根据Hoeffding Bounds不等式：

可以得到：

其中，R=log2C，C表示类别数。

Δe的真实值位于ec-eb±kε区间的置信度是1-δ。根据Hoeffding Bounds不等式，可以得出三个变量k、Δe和δ之间的关系：如果k值比较大，那么Δe值也就越大，δ值就变得越小。Δe值越大，说明数据流中相邻的两个数据块的数据分布变化越大，数据流中发生概念漂移的概率也就越大。ECDSUD算法利用由Hoeffding Bounds不等式确定的双阈值k1ε和k2ε进行概念漂移检测，其中，k1＜k2。如果Δe≥k2ε，说明数据流中发生了真正的概念漂移；如果Δe≤k1ε，说明数据流中发生了潜在的概念漂移；如果k1ε＜Δe＜k2ε，说明仅仅是受到噪音数据的影响，数据流中没有发生概念漂移。

3　实验结果与分析

为了验证ECDSUD算法的有效性，本文在SEA、HyperPlane和KDDCup数据集上进行了实验，并且和其他经典数据流分类算法CVFDT［2］、Bag-ASHT［4］和Clustering-training［5］进行了比较。实验中使用的SEA、HyperPlane概念漂移数据集是通过开源工具MOA［17］中的数据生成器生成。本文实验所使用的环境是3.4 GHz处理器、4 G内存的PC机；操作系统是Windows 7，开发环境是Weka平台。实验主要从标记正确率、概念漂移检测、分类性能和抗噪性能等方面进行考察。

3.1数据集

SEA概念漂移数据集：该数据集有三个属性维，两个类标签。在三个属性维中，前两个属性维是相关的，满足f1+f2≤θ，f1和f2分别表示第一个和第二个属性维；第三个属性维是不相关的。θ是一阈值，当θ的值取9、8、7和9.5时，可以形成四个概念，三次漂移。SEA概念漂移数据集是经典的突变式概念漂移数据集，常用来检测数据流中的突变式概念漂移。

HyperPlane概念漂移数据集：该数据集是由随机生成并且均匀分布在［0，1］d空间的点（x1，x2，...，xd）组成的一个超平面，超平面表示为。如果实例满足条件将此实例标记为正例，否则，将此实例标记为负例。该数据集通过调整权值的大小来改变飞行器的位置和方向，是典型的渐进式概念漂移数据集，常用来检测数据流中的渐进式概念漂移。

KDDCup数据集：该数据集是一个网络入侵监测的真实数据集，包含了一系列网络访问记录，也是一个比较常用的数据集。该数据集包含41个属性维和24个类标签，其中34个属性维是连续属性。通过对该数据集进行极小类的过滤，得到了包含12个类标签的数据集。对过滤后的数据集进行处理，模拟成数据流。

3.2参数分析

ECDSUD算法采用集成框架，包括K个基分类器和1个贝叶斯分类器。很难从理论上确定使用多少个缓冲数据块构建集成分类器最合适。如果缓冲数据块过多，那么就会增加算法的时空开销，而且缓冲数据块中会包含较多的过时数据，这将降低算法的分类精度；如果缓冲数据块较少，那么就会难以消除噪音数据对算法分类的干扰。在K均值聚类算法中，随着K值的增大，算法的分类精度也在不断提高，但是K值增加到一定数值时，分类精度提高不明显。K值比数据集的类别数稍多，大约2～3倍即可。为此，本文进行了大量的实验，实验结果表明使用8个缓冲数据块，每个数据块包含500个实例时，构建集成分类器比较合适；无标签实例标记方法中的参数K和e分别设置为数据集类别数的2倍和0.9；检测概念漂移的参数k1和k2分别设置为3和2时，效果比较好。其他基准算法采用相应文献中设置的参数值。

3.3标记正确率

为了考察算法对无标签实例的标记正确率，本文对无标签实例在总实例中的比例（ulp）取不同值条件下的标记正确率（lc）和分类精度（ca）进行了实验。在SEA数据集上，当ulp从10%增加到50%时，标记正确率从95.2%减少到90.3%，分类精度从86.5%减少到85.9%。在HyperPlane数据集上，当ulp从10%增加到50%时，标记正确率从94.6%减少到91.5%，分类精度从89.2%减少到87.3%。在KDDCup数据集上，当ulp从10%增加到50%时，标记正确率从94.8%减少到90.2%，分类精度从87.1%减少到86.4%。由实验结果可知，随着ulp取值的增加，标记正确率缓慢下降，而分类精度也在缓慢降低。在ulp取值不高于50%时，标记正确率仍保持在85%以上，此时分类精度的下降幅度也不超过2%。这些实验结果表明：该算法在类标签大量缺失的情况下仍具有较高的标记正确率与分类精度。

表1　标记正确率统计值

3.4概念漂移检测

为了验证该算法的概念漂移检测机制的有效性，对ulp取值为30%时的概念漂移进行了实验，其他情况下概念漂移检测的变化规律和ulp取值为30%时的变化规律相同。对数据流中概念漂移检测方法性能的评价通常使用检测概念漂移过程中概念漂移被误报的概率和检测概念漂移时没有被检测到概念漂移的个数。表2显示了本文提出的概念漂移检测方法在数据集SEA、HyperPlane 和KDDCup上的概念漂移检测的统计值，其中：False alarms表示概念漂移检测中误报的概率；Missing表示概念漂移检测时未检测到的概念的个数。在SEA数据集上，ECDSUD算法使用Hoeffding Bounds不等式确定的双阈值检测概念漂移时，误报的概率是5.86%，未检测到的概念的个数是0。在HyperPlane数据集上，误报的概率是6.91%，未检测到的概念的个数是7。在KDDCup数据集上，误报的概率是5.62%，未检测到的概念的个数是4。HyperPlane数据集是渐进式的概念漂移数据集，在渐进地发生概念漂移的过程中平均分类错误率增大，导致概念漂移的误报次数相对较大。误报通常发生在训练的开始阶段，因为在开始阶段，训练数据不足，导致分类错误率会产生比较大的波动，因此，容易发生概念漂移的误报。但是，对表中的实验结果从总体上来看，本文提出的概念漂移检测方法的性能还是比较好的，能够检测出数据流中大多数的概念漂移。

表2　概念漂移检测统计值

3.5分类性能

为验证ECDSUD算法的分类性能，本文使用ECDSUD算法和其他经典数据流分类算法CVFDT、Bag-ASHT和半监督分类算法Clustering-training在不同ulp取值下的数据集SEA、HyperPlane和KDDCup上进行了实验，实验结果如图2、图3和图4所示。在SEA数据集上，随着ulp取值的不断增加，这4种算法的分类精度不断下降。在相同的ulp值条件下，这4种算法的分类精度相差不是很大，ECDSUD算法的分类精度没有明显的优势，比CVFDT和Bag-ASHT算法的分类精度稍微高一些，和Clustering-training算法的分类精度基本相同。对其进行分析，可能的原因是SEA数据集中数据维数较小，只有3维，体现不出该算法的分类优势。在HyperPlane数据集上，随着ulp取值的不断增加，这4种算法的分类精度不断下降。但是，在相同的ulp值条件下，ECDSUD算法的优势较明显。在ulp取值为50%的条件下，ECDSUD算法的分类精度比CVFDT算法高8.1%，比Bag-ASHT算法高6.0%，比Clustering-training算法也高5.2%。在KDDCup数据集上，随着ulp取值的不断增加，各算法的分类精度不断下降。在ulp取值为10%的条件下，ECDSUD算法的分类精度比CVFDT算法高2.9%，比Clustering-training算法高 1.2%，但是，比 Bag-ASHT算法低0.5%。对其进行分析，可能的原因是KDDCup数据库的数据分布不平衡，不利于该算法的分类能力的提高。在ulp取值为50%的条件下，ECDSUD算法的分类精度比Bag-ASHT算法高1.3%。这说明ECDSUD算法能够有效地利用无标签实例的信息去提高分类器的分类性能。从总体上来看，ECDSUD算法对不完全标记数据流的分类效果比其他经典算法的分类效果较好。

图2　不同ulp条件下的SEA数据集上的分类精度

3.6抗噪性能

为了验证ECDSUD算法的抗噪能力，本文对ulp取值为30%条件下含噪率分别为10%、20%和30%的数据集SEA、HyperPlane和KDDCup上进行了实验，实验结果如图5、图6和图7所示。从图中可以看出，随着数据流中噪音数据的不断增加，各算法的分类精度也在不断下降，但是在相同的含噪率条件下，ECDSUD算法比其他算法的分类效果要好，该算法的分类精度最高。在含噪率较低的数据上，ECDSUD算法的分类精度和其他算法相比，优势不明显；但是，在含噪率较高的数据集上，ECDSUD算法的分类效果要明显好于其他分类算法。对其进行分析：在含噪率较高的数据集上，真实类别的数据相对较少，并且，局部数据可能发生概念漂移，因此，随着含噪率的增高，分类精度不断下降。当检测到概念漂移后，分类模型根据当前的数据分布进行更新，并且，贝叶斯分类器过滤掉了噪音数据，所以，更新后的分类模型能够很快地适应数据流环境的变化，提高了分类精度。其他ulp取值条件下的变化规律和ulp取值为30%时的变化规律相同。因此，可以说，ECDSUD算法对噪音环境下不完全标记数据流的分类具有较强的抗噪性能。

图3　不同ulp条件下的HyperPlane数据集上的分类精度

图4　不同ulp条件下的KDDCup数据集上的分类精度

4　结束语

现实应用领域中的数据流大多是无标签的，且其中隐含着不同类型的概念漂移，使已有的模型与方法难以满足用户的要求。针对不完全标记数据流的分类问题，本文提出了一种面向不完全标记数据流的集成分类算法，该算法利用K均值聚类算法将实例划分成不同的聚类簇，进而利用簇中有标签实例标记无标签实例；同时，该算法利用Hoeffding Bounds不等式确定的双阈值检测概念漂移，并动态地更新分类模型以适应数据流环境的变化。实验结果表明，本文提出的面向不完全标记数据流的集成分类算法能够在保证类传播过程中具有较高标记正确率的同时，又能从噪音中识别出不同类型的概念漂移。然而，实际数据流中的类分布往往是不平衡的，即某些类别的实例数量很少，而其他类的实例数量则相对较多，因此，如何在类分布不平衡的数据流环境下，构建具有较强泛化能力的数据流分类算法将是下一步的主要研究内容。

图5　不同噪音率条件下的SEA数据集上的分类精度

图6　不同噪音率条件下的HyperPlane数据集上的分类精度

图7　不同噪音率条件下的KDDCup数据集上的分类精度

［1］ Quinlan J R.C4.5：Programs for Machine Learning ［M］.Morgan Kaufmann Publishers Inc.，1993：68-70.

［2］ Hulten G，Spencer L，Domingos P.Mining time-changing data streams［C］//The International Conference on Knowledge Discovery and Data Mining，2001：97-106.

［3］ Wu D，Liu Y，Gao G，et al.An adaptive ensemble classifier for concept drifting stream［C］//The IEEE Symposium on Computational Intelligence and Data Mining，2009：69-75.

［4］ Bifet A，Holmes G，Adaptive Parameter-free Learning from Evolving Data Streams［C］//The International Symposium on Intelligent Data Analysis，2009：249-260.

［5］ Wu S，Yang C，Zhou J.Clustering-training for Data Stream Mining［C］.The IEEE International Conference on Data Mining Workshops，2006：653-656.

［6］ Miller D J，Uyar H S.A mixture of experts classifier with learning based on both labeled and unlabelled data ［J］.Advances in Neural Information Processing Systems，1997，9（3）：571-577.

［7］ Fan W，Huang Y，Yu P S.Decision tree evolution using limited number of labeled data items from drifting data streams［C］//Fourth IEEE International Conference on Data Mining，Proceedings，2004：379-382.

［8］ Widyantoro D H.Exploiting unlabeled data in concept drift learning［J］.Jurnal Informatika，2007，8（1）：54-62.

［9］ Masud M M，Gao J，Khan L，et al.A Practical Approach to Classify Evolving Data Streams：Training with Limited Amount of Labeled Data［C］//The IEEE International Conference on Data Mining，2008：929-934.

［10］Li X L，Yu P S，Liu B，et al.Positive Unlabeled Learning for Data Stream Classification［C］//The International Conference on Data Mining，2009：259-270.

［11］Lindstrom P，Delany S J，Namee B M.Handling Concept Drift in a Text Data Stream Constrained by High Labelling Cost［C］//The International Florida Artificial Intelligence Research Society Conference，2010：32-37.

［12］Masud M M，Gao J，Khan L，et al.Classification and novel class detection in Concept-Drifting data streams undertimeconstraints［J］.IEEETransactionson Knowledge and Data Engineering，2011，23（6）：859-874.

［13］徐文华，覃征，常扬.基于半监督学习的数据流集成分类算法［J］.模式识别与人工智能，2012，25 （2）：292-299.

［14］Bertini J R，Lopes A A，Zhao L.Partially labeled data stream classification with the semi-supervised K-associated graph［J］.Journal of the Brazilian Computer Society，2014，18（4）：299-310.

［15］熊忠阳，周兴勤，张玉芳.针对标记数据不足的数据流分类器［J］.计算机工程与应用，2013，51（6）：124-128.

［16］张玉红.数据流分类技术研究［D］.合肥：合肥工业大学，2011.

［17］Holmes G，Kirkby R，Pfahringer B.MOA：massive online analysis［EB/OL］.［2010-04-20］.http：//sourceforge. net/projects/moa-datastream.

Ensemble classification algorithm for data streams with unlabeled data

WANG Zhong-xin1，SUN Gang1，2，WANG Hao1

（1.School of Computer and Information Engineering，Fuyang Normal University，Fuyang Anhui 236037，China；2.School of Computer Science and Information，Hefei University of Technology，Hefei Anhui 230009，China）

In real data streams many data are unlabeled，and different types of concept drifts are hidden in data streams. Therefore，an ensemble classification algorithm for data streams with unlabeled data is presented in the paper.The algorithm uses K-means clustering algorithm to label unlabeled data，and uses dual thresholds determined by Hoeffding bounds inequality to detect concept drifts，and dynamically updates classification model to adapt to changes in data stream.Experimental results show that the presented algorithm can more accurately label unlabeled data in the process of class label transmission，and effectively detect different types of concept drifts in noisy data streams.

data streams；classification；ensemble model；unlabeled data；concept drifts

TP3

A

1004-4329（2016）03-046-07

10.14096/j.cnki.cn34-1069/n/1004-4329（2016）03-046-07

2016-05-15

国家自然科学基金项目（51174257，F030504）；中央高校基本科研业务费专项资金项目（2013BHZX0040）；安徽省教育厅自然科学重点项目（KJ2016A549）；阜阳师范学院自然科学项目（2016FSKJ17）资助。

王中心（1976-），男，硕士，讲师，研究方向：数据挖掘、人工智能和模式识别。