3.5　基于增量SVM与二重检测的概念漂移数据流分类模型TDD-ISVM

在常用的增量式学习算法中，本章选择增量支持向量机学习算法，并同K-means聚类进行有机融合。

3.4节介绍了一种二重概念漂移检测机制，在增量支持向量机分类学习的基础上，利用KMBDP概念漂移检测机制和BDBCP概念漂移检测机制一前一后对数据流进行概念漂移检测。本节在基于数据属性的K-means聚类概念漂移检测算法和基于分类性能的伯努利分布概念漂移检测算法的基础上，引入增量学习的思想，基于支持向量机提出一种基于二重检测的概念漂移数据流分类模型TDD-ISVM。

首先，在训练集上利用K-means聚类算法进行聚类，把聚类结果训练集划分为K个簇，并输出聚簇中心代表。

然后，利用K-means聚类的结果在测试集上进行概念漂移检测。在新窗口数据到来时，利用数据属性的相似性为每个实例分配一个类别标签，当存在不可分实例时，存储该实例并记录不可分实例的个数num；在为每个实例分配了类别标签后，排除不可分实例，利用均值重新计算新的聚类中心及其半径，若新的簇中心的半径覆盖另一个簇的半径，则依次找出该簇内相似度最小（距离最远）的实例，直到两个簇不再有交集时，把这些实例当成未标记实例。若不可分实例的个数没超过预先设定的阈值，则直接利用当前分类器对新窗口数据进行分类；若不可分实例的个数超过阈值，则很可能是新窗口数据出现了新的类别。原有的支持向量集SV决定的分类器可以对新窗口数据中的可分实例进行正确分类，而不可分实例的增多会导致分类效果变差。利用增量学习的思想，把不可分实例作为增量与当前支持向量集合并，重新学习新的分类模型，利用更新后的分类器对新窗口数据进行分类。

最后，利用伯努利分布再次检测数据流中有无概念漂移发生。在利用K-means聚类检测到数据流中发生概念漂移并更新了支持向量机分类模型后，若分类精度没有较大变化，则认为数据流中没有发生其他类型的概念漂移，当前分类器的分类效果好，把检测到的未标记实例当成噪声数据进行抛弃处理。若更新分类器后的分类精度依然不高，则可能是数据流中发生了其他类型的概念漂移现象，如因后验概率P(Y|X)发生变化而导致的概念漂移。发生这种情况时，要把新窗口的全部数据当成增量与模型更新之前的支持向量集合并进行增量学习。利用更新后的分类器对新窗口数据再次进行分类，并保存当前分类器的支持向量集。概念漂移数据流分类模型TDD-ISVM算法伪代码如算法3所示。

算法3　概念漂移数据流分类模型TDD-ISVM算法伪代码

TDD-ISVM的算法流程图如图3.1所示。

图3.1　TDD-ISVM的算法流程图

基于二重检测的概念漂移数据流分类增量SVM算法对流式数据进行两次概念漂移检测，可得到三种不同的情况，根据情况的不同再选择是否利用增量学习更新分类器。两次检测、多次更新的模式有助于提高分类器的分类精度，提高分类器的抗概念漂移能力。