一种改进的不平衡数据流集成分类算法

刘剑桥

（阜阳师范学院 语言实验室，安徽 阜阳 236037）

当今信息技术快速发展，计算机需要处理的数据量越来越大，数据格式也多种多样。这类数量巨大，并且动态变化、不断到来的数据称为数据流[1]。在电子商务、传感器网络和网络实时监控等方面，数据流分类有着广泛的应用。但是，在这些应用中，很多时候类分布是不平衡的。这种类分布不平衡的数据流称之为不平衡数据流[2]。

这些类分布不平衡的数据使得传统的数据挖掘分类算法[3-4]甚至已有的数据流分类算法[5-7]面临严峻的挑战。现有的数据流分类算法总是假定类分布是均匀的，很少有算法假定类分布是不平衡的。在这些类分布不平衡数据流的应用中，用户往往更关注系统对于少数类的分类性能。如果分类系统对多数类的分类性能很好，即使对少数类的分类性能很差，总体的分类性能也表现为较好，仍然具有较高的分类精度，这种较高的分类精度是没有意义的。例如网络入侵绝大多数是正常访问，非正常访问概率一般为0.1%，如果全部检测识别为正常访问，精度也可以达到99.9%，很明显这一精度对网络入侵检测是没有意义的。

因此，如何适应不平衡数据流环境下构建具有较强泛化能力的在线分类方法成为现实应用领域数据处理的关键且具有挑战的研究任务。针对数据流的类分布不平衡，本文提出了一种集成分类算法(unbalanced data stream classification algorithm，UDSC)。实验结果表明该算法不仅对正类有较好的分类性能，对整体也有较好的分类性能。

1　相关工作

1.1　不平衡数据集成分类方法

对于不平衡数据的处理，一般是通过过抽样和欠抽样对不平衡数据进行处理，使少数类实例和多数类实例的数目达到平衡。过抽样是通过增加少数类实例的数目使少数类和多数类实例的数据平衡[8]。欠抽样和过抽样的处理不同，欠抽样是减少多数类实例的数目使多数类和少数类实例的数目平衡[9]。还有一些研究重新设计或者直接改进已有的分类算法去提高对少数类实例的分类性能[10-11]。

1.2　WE集成分类模型

由于集成分类器综合了多个分类器的分类结果，通常集成分类器的分类性能好于单个分类器。Boosting[12]和Bagging[13]是两种比较有效的集成分类方法，在静态数据集的分类上取得较好的效果，但是不太适用于数据流环境下的数据分类。WE集成分类模型也称为横向集成分类模型，是一种适用于数据流环境下的分类模型。因此，本文使用基于WE集成分类模型，如图1。WE集成分类模型对连续到达的n个数据块D1，D2,…，Dn分别构建相应的分类器，每个分类器根据其分类精度进行不同的加权，分类器加权集成的结果作为最后的分类结果。随着新数据块的不断到来，集成分类器将会根据某种策略进行更新。

4.5 严格餐饮具清洗消毒。餐饮服务单位应配备洗碗机或以蒸汽、煮沸等方式，严格落实餐饮具和工用具使用后清洗，使用前消毒，消毒后的餐饮具应符合GB14934的规定。餐饮服务单位应配备专用、密闭餐饮具保洁设施，消毒后餐饮具和工用具并在保洁设施内存放。已消毒和未消毒的餐饮具和工用具应分开存放，保洁设施内不得存放其他物品。

1.3　不平衡数据流分类性能的评价标准

在分类类别为二分类的情况下，少数类一般称之为正类，多数类称之为负类。对类分布不平衡的数据流进行分类，评价分类器的分类性能，仅仅使用分类精度是不够的。通常对类分布不平衡的数据流的分类算法，评价分类器的分类性能的指标还有查全率、查准率、F-value值和G-mean等[14]。实际为正类的样本，被正确分类的样本数为TP，被错误分类的样本数为FN；实际为负类的样本，被正确分类的样本数为TN，被错误分类的样本数为FP。分类性能指标的计算公式如下：

公式(3)中，参数β是可以调整的，通常β值设置为1。F-value反映的是分类器对正类的分类性能，只有当查准率和查全率都增大时，F-value的取值才会增大。G-mean反映的是分类器的总体分类性能，只有当正类的分类精度和负类的分类精度都比较大时，G-mean的取值才会增大。

2　面向不平衡数据流的集成分类算法

首先对本文提出的UDSC算法中涉及的符号进行说明：Dm是最新到达的数据块，Dm+1是下一时刻到达的数据块，Ei是数据块中的第i个实例。Dm=Pm+Nm，Pm是Dm中的正类实例，Nm是Dm中的负类实例，k是集成分类器中基分类器的个数，errInstP是被错误分类的正类实例集合，d是更新集成分类器的阈值。

2.1　重采样策略

对不平衡数据流进行分类处理时，数据预处理是一个主要的处理策略。已有的重采样方法中随机复制增加小类样本容易造成过拟合和随机删除大类样本易丢失有用信息，而启发式的上采样方法或者利用K-mean算法选择负类样本的下采样方法则由于相对耗时不太适合数据流环境下的采样操作。

受文献[15-16]的启发，本文对重采样方法进行改进，总的思想是对数据块中的负类集合进行划分，使训练子集中负类实例和正类实例的数目达到平衡。具体的做法是：对当前的数据块Dm的负类Nm进行划分，划分成k(k=|Nm|/|Pm|)个负类子集合，且互不相交。然后，子集合和当前数据块的正类集合Pm组合一个类分布平衡的训练子集。由于没有进行欠抽样，没有减少负类实例，所以，负类实例的信息没有丢失。因为没有进行不同数据块的正类实例合并，正类实例和负类实例是在同一个数据块中进行合并的，所以，不会将不同数据块中不同概念的正类实例合并到一个训练子集中，最大程度上保持了原有数据块的概念分布。为了使分类器能够适应数据块中新的概念，在进行重采样时，被错误分类的正类往往代表着数据流中新的概念，因此，把被错误分类的正类实例加入到各个训练子集中。

2.2　集成分类器的建立与更新

通过上述重采样策略得到k个数据分布平衡的子训练集后，采用支持向量机在k个子训练集上建立k个基分类器，基分类器的权重根据分类结果的F-value值大小确定，然后加权组合成集成分类器EC。EC对数据块Dm+1进行预测分类，如果数据块的实例预测错误，并且实例是正类，把该实例加入错误集合errInstP。预测分类结束后，计算前一个数据块的F-value值pF和当前数据块的F-value值nF，如果两个F-value值之差小于给定阈值d，表明该集成分类器的分类性能还可以继续使用，只需使用F-value值调整各基分类器的权重即可进行预测下一个数据块的分类；如果其差大于等于d，表明该集成分类器的分类性能变得较差，不能继续使用，需要更新该集成分类器。

在集成分类器的更新中，确定d是一个重要的问题。如果d设置太大，集成分类器的更新条件将会变得放松，分类性能就会变差；如果d设置太小，集成分类器的更新条件将会变得苛刻，时间性能将会降低。因此，设置阈值的取值时，需要考虑时间性能和分类性能的平衡。

2.3　算法框架

UDSC算法的总体框架如图2所示。

3　实验结果与分析

3.1　数据集

图2　UDSC算法框架

为验证本文提出的算法UDSC对不平衡数据流分类的有效性，选取文[17]的SE算法和文[18]的ClusterS算法作为对比算法。实验使用具有代表性的 SEA、Hyperplane、LED、Waveform 等基准人工数据集均由开源资源MOA中相应的数据生成器生成。这些生成数据集本身不具有不平衡性，为了模拟不平衡数据流，本文从原始的数据流中抽取了正类实例数目比例为p%(p=5，10，15)、块大小为1K的100个数据块组成不平衡数据流。

3.2　分类性能

为验证本文提出的UDSC算法对不平衡数据流的分类性能，本文将UDSC算法与SE算法和ClusterS算法在数据集SEA、Hyperplane、LED和Waveform上进行对比实验。对于d的取值，很难从理论上确定设置多少比较合适，为此，本文进行了大量的实验，实验结果表明d的取值为0.1时分类效果较好。因此，d取0.1，其他基准算法采用相应文献中设置的参数值。评价指标为F-value值和G-mean值，F-value值的大小反映的是分类器的正类分类性能，G-mean值的大小反映的是分类器的整体分类性能。下面对不同正类比例条件下的不平衡数据流进行实验。

实验结果如图3所示。可看出，本文提出的算法对正类的分类性能优于其他基准算法；在实验数据集上，本文提出的算法对整体的分类性能优于其他基准算法。

从上述的实验结果可以看出，本文提出的算法对不同正类比例的不同数据集在F-value和G-mean评价指标上都获得了较好的结果。分析上述实验结果，其原因是本文采用的重采样方法，没有进行欠抽样，也没有进行不同数据块的正类实例合并，最大程度上保持了原有数据块的概念分布；本文采用的WE集成分类模型是一种比较适用于数据流环境的分类模型，最终的分类结果是依据多个基分类器的分类结果综合确定的，这在一定程度上减弱了噪音数据对分类精度的影响。因此，本文提出的UDSC算法不仅对正类有较好的分类性能，对整体也有较好的分类性能。

图3　不同比例的正类实例测试结果

4　小结

目前大多数数据流分类算法都是针对类分布平衡的数据流，而实际应用中存在大量类分布不平衡的数据流。对于类分布不平衡的数据流，不仅关注整体的分类性能，而且还关注少数类的分类性能。针对类分布不平衡的数据流，本文提出一种改进的集成分类算法。首先，针对数据流的类分布不平衡，采用改进的重采样方法，建立平衡的训练子集；然后，采用支持向量机在平衡的训练子集上建立基分类器；最后，采用WE集成模型组合基分类器，构建不平衡数据流的集成分类器。该算法通过设定相邻数据块的F-value的差值大于等于某一阈值作为更新分类器的标准，同时在更新分类器时引入错分正类实例重新训练基分类器。实验结果表明该算法不仅对正类有较好的分类性能，对整体也有较好的分类性能。