基于组合增量聚类的数据流异常检测研究∗

许福徐建

基于组合增量聚类的数据流异常检测研究∗

许福徐建

（南京理工大学计算机科学与工程学院南京210094）

面向数据流的异常检测方法在诸如实时监控、网络入侵检测等领域有着广泛的应用。然而，数据流连续不断的特点，以及数据流处理的特殊性和时效性等限制使得传统的聚类算法已不再适用，因此增量聚类成为当前面向数据流异常检测的研究热点。论文在改进了两类增量聚类方法的基础上，针对单一增量聚类检测率低，误报率较高的问题，提出了一种基于组合增量聚类的数据流异常检测方法，该方法以改进的增量聚类算法为基础，设计了有效的共识函数对多种聚类算法的结果进行融合。实验结果表明，改进的聚类算法在处理效率上有明显提升，适用于增量聚类，并且提出的组合增量聚类相比于单一聚类方法，具有更好的聚类性能。

数据流；异常检测；增量聚类；子空间聚类；聚类融合

Class NumberTP391

1引言

数据流异常检测技术［14～15］是数据挖掘领域的研究热点之一，在网络安全、信用欺诈和金融分析等领域有着广泛的应用。随着大数据时代的到来，许多数据如电话记录、网络文件等都以数据流的形式出现，然而数据流具有的海量、概念漂移等特点对于现有的数据挖掘方法研究提出了一些新的挑战。目前，研究人员针对数据流的上述特点，开展了不少研究工作来应对这些挑战。例如，文献［1］中提出基于CluStream算法的数据流聚类框架，引入了微簇和时间帧概念，将数据流聚类过程分为在线和离线两个阶段，在线部分实时处理流数据，离线部分提供所有时间的聚类结果。文献［11］提出一种基于数据流聚类，尽管这些研究工作取得了不错的检测效果，然而仍然面临着一些问题，比如聚类算法的处理效率不高，随着新数据的不断到来，需要不断调整和更新聚类的结果，增量聚类［8］的效率不高等。此外，任何聚类算法本身都有一定的局限性，将不同聚类算法相结合，采用分阶段、分层次的增量聚类，即将聚类对象加细，或者将同一时刻不同的聚类结果进行融合来考虑，有机会去进一步改善聚类的结果稳定性，提升聚类质量。基于上述分析，研究有效的增量聚类方法来进一步提升聚类的效率和检测效果成为一个重要的研究课题。

本文针对传统聚类方法［9，12］的局限性以及单一增量聚类方法存在的随机性大、不稳定和准确性低等缺点，在比较分析不同聚类算法的思想、应用领域和应用特点的基础上，提出一种基于组合增量聚类的数据流异常检测方法，该方法以改进的子空间聚类算法和DBSCAN聚类作为基聚类算法，设计基于投票策略的共识函数用于实现不同聚类结果融合，并验证了算法的有效性。

2改进的子空间聚类算法

在面向数据流异常检测的聚类研究中，所要处理的数据通常是高维数据。作为一种有效的解决高维数据［6］聚类的方法，子空间聚类［2，5，10］在诸如图像处理、计算机视觉等领域有着重要的应用。文献［3］提出了一种基于稀疏表示的隐子空间聚类算法LSC（Latent Subspace Clustering），其使用K-SVD算法训练字典，虽然字典有优秀的重构能力，但是缺乏足够的判别信息，导致LSC算法的聚类精度不高。针对以上问题，Jiang等［7］提出了具有标签一致性的LC-KSVD算法来改进字典训练方法以提高LSC算法的聚类精度，然而，字典训练阶段的耗时也随之大幅增加，数据流聚类受到时间和内存、CPU等资源的限制。为了缓解这些方面的限制，能将LSC应用于组合增量聚类方法中，本文提出了一种新的增量式字典训练方法，使其效率能满足增量聚类要求。

稀疏表示［17～18］是指用尽可能少的基或字典原子的线性组合表示数据，其目的在于刻画数据的子空间特性，提供了一种高维数据在低维子空间表示的自然模型。字典训练表示是从数据中学习稀疏表示下的最优表示，同时训练初始字典使得字典的原子特性更接近于所需表示的原始信号，以此获得误差更小的新字典。LSC算法在构建字典的过程中具有一定的随机性，使得训练出的字典缺少足够的重构能力和判别能力。为了改进这一缺陷，综合考虑重构误差，判别能力以及线性分类性能这三方面因素提出了新的学习模型：

其解为

参数W的初始化与参数A类似，利用上诉模型求得如下的解：

其中，参数X是在已知初始字典D0的情况下，使用K-SVD算法所求得的信号Y的稀疏表示系数矩阵。

具体的增量式字典训练算法如算法1所示。

算法1增量式字典训练算法

输入：Y，m，D1，A1，W1，ρ，n，M，μ，v1，v2，b

输出：测试信号Y2的聚类标签

1）将信号Y分为Y1∈RK×T和Y2∈RK×N两部分，Y1为带有标签信息的训练信号用于训练字典，Y2为不带标签信息的测试信号用于聚类算法。

2）求得训练信号Y1的判别式稀疏编码矩阵Q∈RM×T和类标矩阵H∈Rm×T。

3）增量式训练字典D：

for i=1…n：

（1）依次从信号Y1中随机抽取一批信号

其中D代表字典矩阵，X是稀疏表示稀疏矩阵，A=|X|，W是非负临接矩阵，α和β是平滑因子，Q是关于信号Y的判别式稀疏编码矩阵。

在使用字典学习模型时，需要对参数D，A，W进行初始化，具体方法如下：

对于字典D的初始化，针对每一类别的信号用K-SVD算法训练得到各自类别的字典，再将训练得到的字典合并为一个完整的初始字典D0，即所有类共享的字典。

对于参数A的初始化，使用多元岭回归正则化模型来求解其初始值，相应的目标函数如下计算其对应的qi∈Q和 hi∈H。

for j=1…T/b：

（2）计算y(i)的稀疏表示xi。

（3）根据xi中非零值的位置，得到索引集合Ai，并计算辅助变量φ1和φ2。

（4）选择学习率ρi=min(ρ，ρi0/i)。

（5）通过公式更新参数D，A，W

end for

end for

4）使用OMP算法，利用字典D构建测试信号Y2的稀疏表示矩阵C∈RM×N，使得Y=D C。

5）构建矩阵A=|C|，计算度矩阵D1和D2，求得矩阵

6）使用SVD奇异值分解算法计算矩阵An的前[logm2]个左右奇异向量和

8）对logm2维数据集Z进行K-means［13］聚类，聚类标签的最后N行是测试信号Y2的聚类结果。

在增量式字典训练算法中，使用的字典训练模型与LSC算法类似，但求解最优化的方式不同，使用增量式算法每次读取一小批信号来训练字典，并用梯度下降算法更新最优参数，由于梯度下降算法拥有较快的寻优速度，因此增量式字典训练算法在保证字典判别性的同时，减少了字典训练的耗时。

3增量DBSCAN聚类算法

DBSCAN［4］是代表性的基于密度的聚类算法，其显著优点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。然而，此算法［16］每次只能孤立地处理一个更新，存在太多的冗余操作，从而增量聚类的效率很低。为了克服上述缺点，本文提出一种支持批量更新的改进算法，该算法利用基于密度的聚类特性来提高增量聚类的效率。

·ε邻域：以对象p为中心，ε为半径的空间，其中ε＞0；

·核心对象：如果对象p的ε邻域内的样本数大于等于Minpts，则称p为核心对象；

·直接密度可达：如果对象p在核心对象k的ε邻域内，则p是从k直接密度可达的；

·密度可达：存在对象链p1，p2，…，pn，pi+1是从pi直接密度可达，则pn从p1密度可达；

假设D为对象集合，p为插入或移除的对象，

分别表示对象插入和移除操作，Near(x)表示x的邻域对象，n与x均为核心对象。

在批量模式中，无论插入还是移除对象p时，都会影响其ε邻域对象密度。插入对象时，可能会出现噪声、新的聚类、归入某一聚类、合并相邻聚类等影响；而移除对象时，可能会出现噪声、聚类撤销、聚类对象减少、分裂聚类等影响。因此，下文依次阐述支持批量更新是对象插入和对象移除的方法。

假设批量插入对象集合为InsList。对象插入的处理过程如下：

1：forall p in InsList

2：If InsNod es(p)=φand Near(p)内无核心对象then p→噪声

3：If核心对象in InsNodes(p)且不与任一聚类核心对象密度可达

4：then创建新聚类

5：If核心对象in InsNod es(p)均属于同一个聚类，then将p归入此聚类中

6：If核心对象in InsNod es(p)不属于同一个聚类，且互相密度可达，

7：then合并这些聚类

8：end for

批量插入新对象时，算法以插入对象为核心点进行扩充，寻找从该对象出发的所有密度可达的数据点，与InsList顺序无关，因此能较快发现新聚类中的对象，减少了聚类合并的处理。聚类合并时，算法也能快速发现不同聚类间的核心对象，减少了部分不必要的聚类生成再合并的处理，提高了聚类合并的效率。批量插入模式中，算法只需检索一次插入对象，避免了更新对象的重复检索。

删除对象时，由于待删除对象具有聚类的标识，可能会对原聚类产生影响，例如引起聚类分裂，此时处理方法为：记录下密度不可达的点，找出所有可能引起分裂的核心对象后，再选择任一核心对象检索其密度可达对象，最终求出对象的直接密度可达对象。该方法最多检索一遍聚类中的对象，就可得到聚类最后的分裂情况，提高了增量聚类的效率。

假设待删除对象集合为DelList，其具体处理过程是：

1：从DelList中选取属于同一个聚类的一组对象，设为S

2：forall p in S

3：If DelNodes(p)≠φand DelNod es(p)内对象彼此不能直接密度可达

4：then从对象集选取代表点加入到d_link

5：If p in d_link

6：if p有直接密度可达核心对象and D为p的直接密度可达核心对象集合

7：then从D中选择任一对象替换p

8：else delete p from d_link（p直接密度可达的对象变为噪声）

9：end for

10：while d_link≠φ（删除对象p）

11：p=pop（d_link）p加入到分裂后形成的聚类Q R为p的密度可达对象集合

12：for q in R

13：ifq in d_link

14：then delete q and Q=Q+｛q｝

15：End for

16：end while

假设算法已有N个对象，增量插入M个对象时，原算法可能需要检索M次已有对象集，时间复杂度为O（N*M），而以上算法的处理思路最多检索一遍已有对象集即可得到最终分裂结果，时间复杂度为O（N），算法时间复杂度大大降低，提高了增量聚类的效率，同时该算法也消除了一些删除对象的多余的密度可达关系的检索。

4基于聚类融合的增量聚类算法

为了避免使用单一聚类算法的局限性，本文设计一种组合聚类分析算法，并以改进的子空间聚类算法和DBSCAN聚类算法作为基聚类算法，设计基于投票策略的共识函数实现不同聚类结果融合，综合利用了不同聚类算法的优点，从不同角度对空间样本进行全方位的聚类。

聚类融合是指将多个聚类算法或者同一个聚类算法不同参数下得到的聚类成员进行合并，其可形式化地表述为：假设有n个数据点x= {x1，x2，x3，…，xn}，对数据集x使用H个聚类算法或用一个聚类算法运行H次得到H个聚类成员，H={h1，h2，h3，…，hH}，其中hk(k=1，2，3，…，H)为对第k次聚类结果，然后设计一种有效的共识函数，将H个聚类成员的聚类结果进行合并，得到聚类融合的结果，具体过程如图1所示。

图1 聚类融合过程

聚类融合［19～20］技术主要分为两个阶段：1）产生n个具有差异性的聚类结果，本文中主要采用两种改进的聚类算法，对同一个数据集进行多次聚类得到；2）设计有效的共识函数，对聚类成员进行集成得到聚类结果。下面重点介绍共识函数的设计。

目前常用的共识函数构造方法主要有信息论方法、投票法、共联矩阵法、超图法和混合模型法等。本文采用基于投票策略的聚类融合策略，如算法2所示。

算法2：基于投票策略的聚类融合

输入：数据集S，异常簇记录数阈值θ，异常次数阈值λ

输出：异常集OS

1：初始化la［N］=0 j=0

2：while j＜h do

3：采用LSC/DBSCAN作为基聚类算法，生成簇集合C={C1，C2，…，Cw}

4：l=0

5：while l＜w do

6：if|Cl|＜θ

7：then Cl被标记为候选异常

8：∀pi∈Cl(i∈[1，N])

9：la[i-1]++

10：end if

11：l++

12：end while

13：i=0，OS=ϕ

14：while i＜N do

15：if la[i]＞λ

16：then pi被标记为真正的异常，O S=OS∪{pi}

17：end if

18：end while

其中，N表示记录总数，h表示融合次数，元素la[i](i∈1，N)表示在h次不同划分中对象pi被标记为异常的次数。以子空间聚类算法和DB⁃SCAN算法为基础，对数据集进行多次聚类，将每次聚类形成的簇集合中包含对象数小于阈值θ的簇所有对象都作为候选异常点，统计异常次数加1。最后，将多次检测结果进行融合，如果一个数据点的异常投票数超过异常阈值λ，这个数据点看作异常点。

5实验

本文选用KDD Cup99数据集进行模型实验。该数据集是麻省理工学院提供的网络入侵检测评估测试数据集，被广泛应用于入侵检测算法的检验。数据集收集了9个星期网络连接和系统审计数据，大约500万条连接记录。本次实验从KDD Cup99中随机抽取40000条网络连接记录，分为四组数据子集test1，test2，test3，test4。每个测试集包含10000条网络连接记录，其中正常行为占90%，异常行为占10%。

为了评价和比较各种异常检测方法的优劣，需要利用相关的评价指标体系来衡量。检测率、误报率，两者是评价异常检测最重要的指标。两者具体用公式描述为

即

标准化信息（Normalized Mutual information，NMI）常用在聚类中，度量两个聚类结果的相近程度。

为了验证改进的子空间聚类算法的精度和运行时间开销，将改进的增量子空间聚类与LSC算法进行比较。在字典训练中，为了保证实验的随机性，实验中随机选取m=2，…，8类，即m个尺度划分，每个类别选取T=60个信号构成包含T*m列的训练数据集，用于字典训练，剩余的信号构成测试数据集，用于测试。每个类别实验重复40次，统计两种聚类算法的整体耗时和聚类精度，实验结果如图2，图3所示，增量LSC相比LSC不同类簇之间区分度更明显，聚类效果更好，还能保证较快的运行速度。

即

图2 NMI值

图3 算法耗时

我们将本文提出的批量模式的DBSCAN与非批量的增量聚类进行比较。实验每个测试集选取2000个对象进行DBSCAN聚类，然后模拟数据流批量插入新数据，进行增量聚类。如图4所示，可以看出批量模式处理效率高于非批量模式，特别是随着数据的不断插入，当形成新聚类时或发生聚类合并时批量模式速度优势更明显，与预期结果相符合。

图4 算法耗时

为了验证本文提出的模型聚类效果优于单一聚类算法，将组合模型的聚类结果与单独使用子空间聚类算法和DBSCAN算法的聚类结果进行了比较。为了保证实验的正确性，针对每个模型每个测试子集进行了10次实验，如图5和图6所示。

图5 10次实验检测率平均值

图6 10次实验误报率平均值

从图5和图6可以看出，组合模型算法检测率较高，误报率较低，且对不同数据集的检测率稳定，使用子空间聚类、密度聚类算法进行数据集的组合聚类分析，能够在不改变原有数据属性的情况下，通过多次和多角度的聚类，有效提高入侵行为的检测率。

6结语

鉴于传统增量聚类算法存在的不足，本文将聚类融合方法引入数据流增量聚类中，提出了基于聚类融合的数据流异常检测方法，以避免由单一聚类带来的局限性和随机性的缺点。该算法由子空间聚类算法和DBSCAN聚类算法产生聚类成员，采用聚类融合方法进行融合，从而获得聚类的结果。通过对KDD数据集进行实例分析，表明了改进的组合增量聚类算法能够改善单一聚类不稳定性和随机性，具有很好的聚类效果。

［1］Aggarwal C C，Yu P S.A Framework for Clustering Uncer⁃tain Data Streams［C］//IEEE，International Conference on Data Engineering.IEEE，2008：150-159.

［2］朱林，雷景生，毕忠勤，等.一种基于数据流的软子空间聚类算法［J］.软件学报，2013（11）：2610-2627.

ZHU Lin，LEI Jingsheng，BI Zhongqin，et al.Soft Sub⁃ space Clustering Algorithm for Streaming Data［J］.Journal of Software，2013（11）：2610-2627.

［3］Adler A，Elad M，Hel-Or Y.Probabilistic Subspace Clus⁃tering Via Sparse Representations［J］.IEEE Signal Pro⁃cessing Letters，2013，20（1）：63-66.

［4］Ester M，Kriegel H P，Sander J，et al.Incremental Clus⁃tering for Mining in a Data Warehousing Environment［C］//VLDB'98，Proceedings of，International Conference on Very Large Data Bases，August 24-27，1998，New York City，New York，USA.1998：323-333.

［5］Ller E，Nnemann S，Assent I，etal.Evaluating clustering in subspace projections of high dimensional data［J］.Pro⁃ceedings of the VLDB Endowment，2009，2（1）：1270-1281.

［6］Kriegel H P，Ger P，Zimek A.Clustering high-dimension⁃al data：A survey on subspace clustering，pattern-based clustering，and correlation clustering［J］.ACM Transac⁃tions on Knowledge Discovery from Data，2009，3（1）：337-348.

［7］Karimian S H，Kelarestaghi M，Hashemi S.I-IncLOF：Im⁃proved incremental local outlier detection for data streams［M］.2012.

［8］蒋盛益，杨博泓，王连喜.一种基于增量式谱聚类的动态社区自适应发现算法［J］.自动化学报，2015（12）：2017-2025.

JIANG Shengyi，YANG Bohong，WANG Lianxi.An Adap⁃tive Dynamic Community Detection Algorithm Based on Incremental Spectral Clustering［J］.Acta Automatica Sini⁃ca，2015（12）：2017-2025.

［9］李桃迎，陈燕，秦胜君，等.增量聚类算法综述［J］.科学技术与工程，2010（35）：8752-8759.

LI Taoying，CHEN Yan，Qin Shengjun，etal.Review of In⁃cremental Clustering Algorithm［J］.Science Technology and Engineering，2010（35）：8752-8759.

［10］刘展杰，陈晓云.局部子空间聚类［J］.自动化学报，2016，42（8）：1238-1247.

LIU Zhanjie，CHEN Xiaoyun.Local Subspace Clustering［J］.Journal of Automatica Sinica，2016，42（8）：1238-1247.

［11］李艳红，李德玉，崔梦天，等.基于数据流的网络入侵实时检测框架［J］.计算机应用，2015，35（2）：416-419.

LI Yanhong，LI Deyu，CUI Mengtian，et al.Real-time Detection Framework for Network Intrusion Based on Da⁃ta Stream［J］.Computer Application，2015，35（2）：416-419.

［12］Akter M，Rahman M O，Islam M N，et al.Incremental clustering-based object tracking in wireless sensor net⁃works［C］//International Conference on NETWORKING Systems and Security.IEEE，2015：1-6.

［13］Jonathan D A S，Hruschka E R.Extending k-Means-Based Algorithms for Evolving Data Streams with Variable Number of Clusters［C］//International Con⁃ference on Machine Learning and Applications and Workshops.IEEE Computer Society，2011：14-19.

［14］耿志强，姬威，韩永明，等.基于维度最大熵数据流聚类的异常检测方法［J］.控制与决策，2016（2）：343-348.

GENG Zhiqiang，JI Wei，HAN Yongming，et al.Data Stream Clustering Algorithm Based on the Maximum En⁃tropy of Data Dimension and its Applications for Anoma⁃ly Detection［J］.Control and Decision，2016（2）：343-348.

［15］Sommer R，Paxson V.Outside the Closed World：On Us⁃ing Machine Learning for Network Intrusion Detection［C］//Security and Privacy.IEEE，2010：305-316.

［16］Patwary M M A，Palsetia D，Agrawal A，et al.A new scalable parallel DBSCAN algorithm using the dis⁃joint-setdata structure［C］//SC Conference，2012：1-11.

［17］Elhamifar E，Vidal R.Clustering disjoint subspaces via sparse representation［C］//Acoustics Speech and Signal Processing（ICASSP），2010 IEEE International Confer⁃ence on.IEEE，2010：1926-1929.

［18］Feng J，Lin Z，Xu H，etal.Robust Subspace Segmenta⁃tion with Block-Diagonal Prior［J］.2014：3818-3825.

［19］周林，平西建，徐森，等.基于谱聚类的聚类集成算法［J］.自动化学报，2012（8）：1335-1342.

ZHOU Lin，PING Xijian，XU Sen，et al.Cluster Ensem⁃ble Based on Spectral Clustering［J］.Acta Automatica Si⁃nica，2012（8）：1335-1342.

［20］李桃迎，陈燕，张金松，等.基于聚类融合的混合属性数据增量聚类算法［J］.控制与决策，2012（4）：603-608.

LI Taoying，CHEN Yan，ZHANG Jinsong，et al.Incre⁃mental Clustering Algorithm of Mixed Numericaland Cat⁃egorical Data Based on Clustering ensemble［J］.Control and Decision，2012（4）：603-608.

Research on Data Stream Amonaly Detection Using Incremental Clustering Ensemble

XU Fu XU Jian
（Schoolof Computer Science and Engineering，Nanjing University ofScience and Technology，Nanjing 210094）

Anomaly detection in data stream has gained a high attraction due to its applications，including real-time surveil⁃lance，network intrusion detection.However，traditionalclustering is no longer suitable due to the particularity and timeliness ofthe data stream and the continuous characteristics of the data flow.Therefore，incremental clustering has become the research hotspots towards anomaly detection in data stream.An anomaly detection modelin data stream is proposed based on two improved incremen⁃tal clustering aiming at the problem of low efficiency，high false positives and lack of pertinence of single clustering.The mothod is based on improved incrementalclustering and an effective consensus function is designed to merge the results ofa variety ofcluster⁃ing algorithms.The experimental results show that the improved clustering algorithms are applicable to incremental clustering and they have better efficiency and better clustering resultthan single clustering method.

data stream，anomaly detection，incrementalclustering，subspace clustering，clustering ensemble

TP391

10.3969/j.issn.1672-9722.2017.08.003

2017年3月19日，

2017年4月23日

国家自然科学基金项目“虚拟计算环境下的软件自愈机理和方法研究”（编号：61300053）资助。

许福，男，硕士，研究方向：数据挖掘。徐建，副教授，博士，研究方向：数据挖掘。