基于网格耦合的数据流异常检测*

杨 杰，张东月，周丽华，黄 皓，丁海燕

(云南大学信息学院,云南 昆明 650504)

1 引言

数据流是一种随着时间增加而顺序、快速、大量、连续到达的数据序列。近年来，随着计算机技术的发展，大量的数据流不断产生，如网络流量、金融数据、气象数据等。数据流中存在一些对象与其他数据对象显著不同，好像它们是由不同的机制产生的，这些对象被称作异常[1]。对数据流中异常进行检测可以预测数据对象的行为和发展趋势，对于人们的工作、生活具有重要意义。数据流的异常检测广泛应用于网络入侵检测、金融风险分析和异常天气检测等领域，已经成为数据挖掘中的一个重要研究热点[2 - 5]。然而，由于数据流具有连续、无限和时变等特点，数据流的异常检测仍面临许多挑战，比如数据流不能以有限内存进行存储，流中的数据对象不能随机访问，数据对象对于决策的影响随时间的流逝逐渐衰减，如何提高数据流异常检测的精确度和效率等。

针对数据流异常检测存在的诸多挑战，许多数据流异常检测算法被提出[4,6,7]。这些算法利用距离、密度或聚类等手段来区分正常数据和异常，虽然能够较精确地检测数据流中的异常，但是它们均以数据对象为处理单元，需要对数据流中每个数据应用详尽的策略进行异常判断，这大大降低了算法处理数据流的速度，影响了算法的效率。而为了快速处理数据流，Chen等人[8]将网格引入到了数据流聚类中，将不断到达的数据流映射到一组支持快速查找的网格结构中，以此汇总数据流并提取数据流的概要信息，然后以网格为单元进行后续处理。与以数据对象为处理单元的算法相比，网格的应用大大加快了数据流的处理速度，进而提高了算法的效率。但是，Chen等人[8]在将数据对象映射到网格并增量更新网格时，独立处理每个网格，忽略了网格之间的相互影响,使得提取的数据流概要不够精确,从而影响了算法的精确度。张东月等人[9]也采用了网格的方式进行数据流的聚类，但是在将数据对象映射到网格后不是独立处理网格，而是考虑了网格之间的相互影响(即网格耦合)，该方法有效提高了聚类的精确度。

受此启发，本文提出了一种基于网格耦合的数据流异常检测算法GCStream-OD(Grid Coupling based data Stream Outlier Detection)。首先，基于网格内的数据对象定义网格权重，并在数据映射到网格的过程中不再独立处理网格，而是基于网格内数据对象的分布状态考虑网格之间权重的相互影响，即一个网格权重的变化会使相邻网格的权重增加或减小。网格的耦合能更加准确地捕捉数据之间的相关性，从而提高检测精确度。其次，基于网格内数据分布的密度和网格间的距离度量每个网格的异常程度，使得异常度量更为准确。最后，在实时映射数据流更新网格的过程中，通过剪枝策略周期性地去除那些数据量较多、不可能为异常的网格，缩小了异常的查找范围，从而提高算法的效率。

本文的主要贡献包括：

(1)提出了一种基于网格耦合的数据流异常检测算法GCStream-OD。该算法以网格为处理单元，以网格耦合的思想更新网格，并基于网格内数据分布的密度和网格间的距离度量每个网格的异常程度。网格的耦合以及网格内数据分布的密度和网格间距离的融合，更为精确地捕捉了数据之间的相关性，从而提高检测精确度。

(2)提出了一种剪枝策略。该策略在实时映射数据流更新网格的过程中，周期性地去除不可能成为异常网格的网格，从而缩小异常的查找范围，提高算法效率。

(3)在5个真实数据集上，分别对GCStream-OD算法的检测质量和效率进行了实验验证。实验结果表明GCStream-OD算法具有较高的检测质量和效率。

2 相关工作

数据流异常检测是检验数据流中是否有不符合常理的数据对象的过程。这些异常如果不被检测出来，会对数据流的挖掘分析结果产生负面影响。近年来，提出了一些针对数据流的异常检测算法[10,11]。这些算法主要分为4类：基于距离的算法、基于密度的算法、基于统计的算法和基于聚类的算法。

基于距离的异常检测算法最早是由Knorr等人[12]提出的，其主要思想是计算数据对象之间的距离，然后以距离定义它们之间的邻近度，而异常往往是那些远离大部分数据的对象。基于密度的异常检测算法是根据对象的密度定义异常，如果某些点周围的数据点比较稀疏，则这些点会被算法视为异常进而从数据流中过滤出来。最典型的算法为局部异常因子LOF(Local Outlier Factor)算法[13]，它根据每个数据对象的k近邻密度，为每个数据对象分配了1个表示异常可能性大小的LOF得分。iLOF算法[14]为LOF算法的增量版本。MiLOF算法[15]是一种能够在有限的内存环境中完成数据流的异常检测的基于密度的数据流异常检测算法。基于统计的异常检测算法最早是由Barnett等人[16]和Hawkins[17]提出的。这类算法的主要思想是利用平均值、方差等对数据进行统计，进而确定那些明显不同于大部分数据的对象。基于聚类的异常检测对数据对象进行聚类，以此来获取不属于簇的点或者一些明显小于其它簇的数据集合。这种方法的主要过程是将数据聚集成簇，并判断簇的大小，将小于阈值的簇视为异常。典型的算法有CORM(Cluster based OutlieR Miner)[6]、ROCK(RObust Clustering using linKs)[18]、CLARANS(Clustering Large Applications based on RANdomized Search)[19]等。CORM算法利用滑动窗口将数据流分块，对于第1个窗口中的数据流，该算法先使用K-means算法将其划分为k个簇，只保留每个簇的中心。对于后续窗口中的数据，首先根据数据对象到各个簇中心的距离进行对象所属簇的划分，然后每个簇根据其分得的新数据更新簇中心。根据当前窗口中的数据对象和更新后的簇中心距离得到候选异常数据。当候选异常数据经过L个窗口后仍为候选异常值时，则将其声明为异常。CORM并没有使用网格或微簇汇总数据流，而是以数据流中的每个数据对象为处理单元，这会降低算法的效率，并占用较大的内存。

iForest(isolation Forest)算法[20]使用称为隔离树的二叉树结构，它可以有效构建并且隔离数据对象。异常更容易被分离到更靠近隔离树的根部，而正常点更可能在隔离树的更深层被隔离掉。与其他异常检测算法通过距离、密度等量化指标来刻画样本间的疏离程度不同，iForest算法纯粹基于隔离概念检测异常。该算法大致可以分为2个阶段；第1个阶段需要训练出多棵孤立树，组成孤立森林；第2阶段将每个样本点代入森林中的每棵孤立树，计算平均高度，然后再计算每个样本点的异常值分数。iForest算法是一种半监督的算法，需要一定的训练数据，这在一些应用场景下是不适用的。

3 基于网格耦合的异常检测算法

本节首先介绍网格耦合的思想及概念，然后给出基于网格耦合的异常检测算法GCStream-OD。

3.1 网格耦合

输入数据流中的每个数据对象x=(x1,x2,…,xd)都是d维空间中的一个点，xi表示数据对象在空间的第i维上的取值。如果x1属于s1的j1区间，x2属于s2的j2区间，以此类推xd属于sd的jd区间，则可以将数据对象x映射到空间S的网格g=(j1,j2,…,jd)中。映射到同一网格中的数据对象距离相近，因此可以对各个网格内的数据进行汇总，形成概要。后续的数据分析可以只针对概要进行处理，从而降低存储空间和计算成本。

网格权重定义为网格内各个数据对象的权重之和，数据的权重用于体现数据对象的“新鲜”程度。随着时间的推移数据对象的“新鲜”程度越来越低，因此网格权重的大小是对网格内数据对象的数目和“新鲜”程度的反映。数据对象权重和网格权重的定义分别如定义1和定义2所示。

定义1(数据对象权重[9]) 如果数据对象x在tp时刻到达，那么x在t时刻的权重W(x,t)的计算公式如式(1)所示：

W(x,t)=λ-a(t-tp)

(1)

其中，λ-a(0<λ-a<1)为衰减因子。参数λ和a控制衰减因子的衰减速度，a的绝对值越大，衰减速度越快。

定义2(网格权重[9]) 设E(g,t)表示到时刻t为止，映射到网格g中的数据对象集合，则网格g在时刻t的权重W(g,t)定义为网格g内所有数据对象的权重之和。W(g,t)的计算如式(2)所示：

(2)

数据流中的数据对象顺序到达，因此各个网格映射的数据随时间不断变化，每个网格的概要需要随时间不断更新。网格耦合的思想是在更新网格的概要时，根据网格中数据的分布状态考虑网格之间的相互影响。网格之间的相互影响是由网格内的数据分布来决定的。为了表示网格内数据对象的分布状态，张东月等人[9]将网格内带权数据对象的中心定义为网格质心，利用网格质心的位置来表示网格内的数据分布状态。数据流的动态性使得网格质心是随时间变化的。网格质心的定义如定义3所示。

定义3(网格质心[9]) 网格g在t时刻的质心C(g,t)定义为网格g内带权数据对象的加权平均[9]。根据式(3)进行计算可以得到C(g,t):

(3)

网格之间的相互影响与网格的质心距离有关，网格质心距离越近，网格之间的影响越大，反之越小。网格质心之间的距离disC(gi,gj)使用质心之间的欧氏距离进行度量。设网格的影响区域阈值为Dislen，disC(gi,gj)≤Dislen表示网格gi对网格gj产生正影响，反之表示产生负影响。当网格gi对网格gj产生正影响时，网格gj的权重会随着网格gi权重的增大而增大，当产生负影响时，网格gj的权重会随着网格gi权重的增加而减小。设网格gi的权重增量为ΔW(gi)，则对网格gj的权重影响按式(4)进行更新。

(4)

其中,MaxCdis是相邻网格质心间的最大距离，MaxCdis可以按式(5)计算：

(5)

其中，len为网格边长，Dim为数据维度。

另外，为体现Dislen影响范围内网格之间的权重关系，引入了核心网格的概念。

定义4(核心网格[9]) 设L(g,t)是网格g在Dislen影响范围内的网格集合，如果L(g,t)内所有网格的权重之和大于阈值θ，即LW(g,t)=∑g′∈L(g,t)W(g′,t)>θ，则称网格g为核心网格。所有核心网格的集合表示为LD。

3.2 GCStream-OD算法

本节分别从相关定义、算法框架、剪枝策略以及算法描述4个方面对GCStream-OD算法进行阐述。

3.2.1 相关定义

GCStream-OD算法在使用网格来检测异常时，从网格密度和网格距离2个因素进行考虑。密度因素从网格的邻居网格数目和网格本身密度2个方面度量网格是异常网格的可能性，如果1个网格周围含有数据的邻居网格数较少且本身密度较低，则该网格中的数据对象是异常的可能性较大。距离因素从网格与其它网格的距离方面度量网格是异常网格的可能性，如果1个网格距离其它大部分网格较远，则该网格中的数据对象为异常的可能性较大。

GCStream-OD算法为每个网格分配1个异常因子，每个异常因子由密度异常因子和距离异常因子2部分组成。异常因子的定义如定义5所示。

定义5(网格异常因子(GOF)) 每个网格的异常因子的计算如式(6)所示：

GOF(g)=denF(g)+disF(g)

(6)

其中,denF为密度异常因子，disF为距离异常因子。GOF值表示网格的异常程度，值越大表示其越可能为异常网格，值越小表示其越不可能为异常网格。

密度异常因子denF的计算类似于LOF[13]的计算，因此需要定义网格的k距离、网格k距离邻域、网格可达距离、网格局部可达密度等概念。

定义6(网格的k距离) 对于网格gp，如果存在网格go满足至少存在k个网格gq使得disC(gp,gq)≤disC(gp,go)和至多存在k-1个网格gq使得disC(gp,gq)

k-distance(gp)用来度量网格gp局部区域的密度，其值越小，局部区域密度越大；其值越大，局部区域密度越小。

定义7(网格的k距离邻域) 与网格gp之间距离小于或等于k-distance(gp)的网格集合称为gp的k距离邻域，记为Nk(gp)，如式(7)所示：

Nk(gp)={go|disC(gp,go)≤k-distance(gp)}

(7)

定义8(网格可达距离) 网格gp和go之间的可达距离的定义如式(8)所示：

reachdist(gp,go)=

max(k-distance(go),disC(gp,go))

(8)

定义9(网格局部可达密度) 网格gp的局部可达密度为Nk(gp)中所有网格平均可达距离的倒数，可以通过式(9)计算得到：

(9)

定义10(网格密度异常因子) 网格gp密度异常因子定义为其k距离邻域Nk(gp)内网格的局部可达密度与网格gp局部可达密度之比的平均数，如式(10)所示：

(10)

其中，局部异常因子denF(gp)越大，表示网格gp为异常的可能性越大，反之成立。

denF(gp)从密度的角度表征了网格gp为异常的程度。从距离角度表征1个网格异常的程度的距离异常因子disF由定义11给出。

定义11(距离异常因子disF) 设gc是1个核心网格，L(gc,t)是与网格gc最近的低权重网格集合，gi∈L(gc,t)，则网格gi的距离异常因子定义为gi与gc之间的距离与L(gc,t)内的网格与gc之间的最大距离之比，通过式(11)计算得到:

(11)

其中，任意网格g的距离因子满足0

定义12(异常网格) 在当前时刻t如果网格g的异常因子大于一定阈值εo，即GOF(g)>εo，则将网格g视为异常网格。异常网格中的数据对象即为异常。

3.2.2 算法框架

由于数据流具有快速、大量、连续到达的特性，为了更好地处理数据流，GCStream-OD算法采用在线/离线的框架。在线阶段处理源源不断到达的数据，离线阶段进行离群点检测。GCStream-OD算法流程图如图1所示。

Figure 1 Flow chart of GCStream-OD algorithm图1 GCStream-OD算法流程图

GCStream-OD算法分为在线阶段和离线阶段2个部分。在线阶段的主要工作是将随时间到达的数据流映射到网格中，然后根据网格耦合思想更新网格，最后周期性地检测网格权重并保留低权重网格作为异常的候选集合。离线阶段的主要工作是计算每个低权重网格的异常因子，并根据异常因子判断网格是否为异常网格。具体操作将在后面2节进行介绍。

3.2.3 剪枝策略

在上述框架中，周期性检测过程中若简单地将除核心网格外的所有网格作为低权重网格存至lwGirdList，将会使离线阶段需要大量的计算，影响算法效率。针对这一问题，本文根据异常数据量较少、密度较低的特点，提出了一种剪枝策略。剪枝策略的主要思想是在周期性检测过程中判定低权重网格时，根据网格权重的大小筛选网格，保留权重较小的网格，去除网格权重大的非核心网格，判定标准为将网格权重低于μθ的网格划为低权重网格，其中θ为判断核心网格时所取的阈值，μ∈(0,1)。一个网格如果权重较大，表示该网格内数据对象数目多或权重高，则该网格内的数据对象为异常的可能性小，其被剪枝后对算法的精确度基本没有影响，但能很好地提升算法的效率。如图2所示，在ta时刻数据流映射到网格1～12，网格3是核心网格，其余网格均是非核心网格。经过剪枝之后，权重较大的网格1、2、4、5和6会被去除，而网格权重较小的网格7～12以及核心网格3会被保留。进行异常检测时，只需对网格7～12进行处理，减少了离线阶段的计算量，极大地提高算法运行效率。

经过剪枝之后，一些权重较低的网格，原本距离高权重网格较近不属于异常，但这类网格由于高权重邻居网格的剪枝使得周围邻居网格数骤减、密度降低，很容易被视为异常，进而影响算法精确度。距离异常因子的引入可以避免这种问题。比如，图2b中网格7，图中五角星表示每个网格的质心位置。网格7周围数据量较少，其密度比较低，但是网格7与网格3质心距离较近，即denF(7)较大,disF(7)较小，所以网格7的异常因子不会太高。图2b中只有网格12为异常。由于考虑了网格耦合，图2b中只有网格12为异常，若不考虑网格耦合，网格8、9、10和11均为异常。因此，该剪枝策略适用于GCStream-OD算法。

Figure 2 Data distribution within the grid up to time ta图2 截止到ta时刻网格内的数据分布

3.2.4 算法描述

GCStream-OD算法在线阶段将到来的数据流映射到对应网格并通过周期性检测得到低权重网格，具体细节如算法1所示。算法1需要1个数据流和1个检测周期tp作为输入。算法1首先初始化网格列表为空和tc=0，之后开始接收数据流中的数据，直到数据流结束后停止算法执行。每当从数据流中获得1个新数据对象x，先将对象x映射到对应的网格gx。若网格gx不存在，则创建网格gx并将其插入到网格列表中，再将对象x映射在所属的网格gx。之后根据网格耦合思想更新网格gx的属性：(1)根据式(2)计算网格权重；(2)根据式(3)计算网格质心；(3)根据式(4)更新gx周边网格的权重。更新网格后可能造成核心网格的变更，因此需要更新核心网格。每当处理完1个数据对象x后，tc加1，同时判断1个周期是否结束，若结束，先更新核心网格，再将通过剪枝策略得到的低权重网格存至lwGirdList，之后触发执行离线阶段。

算法1GCStream-OD在线阶段

输入：数据流，检测周期tp。

输出：低权重网格列表lwGirdList。

1.初始化网格列表，tc=0;

2.while(数据流没有结束)

3. 从流中获取数据对象x=(x1,x2,…,xd);

4. 确定数据对象x所属的网格gx;

5. if(网格gx不存在于网格列表)

6. 创建网格gx并将其插入到网格列表;

7. end if

8. 将数据对象x映射到网格gx；

9. 更新网格gx；

10.tc=tc+1;

11. if (tcmodtp==0)

12. 更新核心网格；

13. 通过剪枝策略得到低权重网格并将其存至lwGirdList;

14. end if

15.end while

GCStream-OD算法在离线阶段为每个网格分配1个异常因子来定量度量网格的异常程度，具体细节如算法2所示。算法2需要低权重网格列表lwGirdList作为输入，对于lwGirdList中的每一个网格g，先根据式(10)计算密度因子denF(g)，再根据式(11)计算距离因子disF(g)，之后根据式(6)计算低权重网格的异常因子GOF(g)，最后比较异常因子与异常阈值εo，若GOF(g)>εo将网格g加入到异常网格列表，反之不做处理。异常网格列表中的网格所对应的数据对象都是异常。

算法2GCStream-OD离线阶段

输入：lwGirdList。

输出：异常值检测结果。

1.for (lwGirdList中的所有网格g)

2. 计算denF(g);

3. 计算disF(g);

4.GOF(g)=denF(g)+disF(g);

5. ifGOF(g)>εo

6. 将网格g加入到异常网格列表;

7. end if

8.end for

假设当前时刻tc进行异常检测，此时低权重网格列表lwGirdList中的网格数据为N，核心网格集合LD的大小为Ncg。GCStream-OD算法首先计算密度因子，由于此步骤是将LOF算法扩展到网格，所以该步骤的时间复杂度为O(N2)。然后计算距离因子，在此步骤中需要先计算低权重网格与核心网格的距离，时间复杂度为O(Ncg×N)。紧接着遍历低权重网格列表lwGirdList，计算距离因子，时间复杂度为O(N)。综上所述，GCStream-OD算法的时间复杂度为：O(N2+Ncg×N+N)。在GCStream-OD算法中处理单位为网格，因为低权重网格数N和核心网格集合LD的大小Ncg都是非常小的，使得该算法具有较高的效率。GCStream-OD算法最糟糕的情况是为每个到达的数据创造1个网格，因此GCStream-OD算法的空间复杂度最高为O(n)，其中n为到达数据的总数。

4 实验评估

本节包含GCStream-OD 算法的实验准备、参数选择以及实验结果3个部分。

4.1 实验准备

数据集：实验使用了KDD CUP99[21]、CoverType[22]、Poker Hand[23]、data_http[20]、data_OD共5个数据集来测试GCStream-OD算法的检测质量和效率。KDD CUP99、CoverType、Poker Hand 数据集均来自UCI数据集。KDD CUP99是一种网络入侵检测数据集，由原始数据集抽样10%形成，包含494 020个数据对象，每个数据对象有34种连续属性。CoverType是一种森林植被数据集，包含581 012个数据对象，并且每个数据对象记录1块30*30平方英尺上的54个地理数据。Poker Hand共有1 000 000个数据对象，其中每个数据对象表示由5张从52张标准牌组中抽出的扑克牌组成的手牌记录，每张卡片使用2种属性(花色和大小)进行描述，因此共10个预测属性。data_http[20]数据集和data_OD数据集由原始KDD CUP99数据集中567 497个相同的数据对象保留不同的属性组成，data_http数据集保留了duration、src_bytes和dst_bytes属性，data_OD数据集保留了hot、srv_count和dst_host_count属性。KDD CUP99、data_http、data_OD均由原始KDD CUP99数据集抽样而成，KDD CUP99保留了34种属性而data_http和 data_OD只保留了3种属性。

在测试过程中，本文以上述数据集中数据的输入顺序作为数据流的传输顺序，将所有数据集转为流。除此之外，本文将测试数据流中规模小于5%的簇视为噪声，即当一个簇规模小于数据集总数据量的5%时被视为噪声。表1汇总了各个数据集的特征。

Figure 3 Influence of different len values on F1 on different data sets of GCStream-OD algorithm图3 GCStream-OD算法在不同数据集上不同len值对F1的影响

表1 数据集特征汇总

对比算法：使用CORM算法[6]和iForest算法[20]作为本文的对比算法。CORM算法将数据流异常检测过程分为在线/离线2个阶段，这与GCStream-OD算法的处理方式相同，具有可比性。iForest算法基于隔离概念检测异常，而不采用任何距离、密度测量，是目前很好的数据流异常检测算法。

评价指标：使用精确度(Precision)、召回率(Recall)和F-Measure(F1)作为评价指标，各项指标的定义分别如式(12)～式(14)所示：

Precision=TP/(TP+FP)

(12)

Recall=TP/(TP+FN)

(13)

F1=Precision*Recall*2/(Precision+Recall)

(14)

为了便于统计，将异常视为正的(Positive)数据对象，非异常视为负的(Negative)数据对象。因此，式(12)和式(13)中TP表示被识别为异常的异常数据的个数，FN表示被识别为非异常的异常数据的个数，FP表示被识别为异常的非异常数据的个数。F-Measure是Precision和Recall的加权调和平均。

4.2 参数选择

为了保证算法结果更具可比性，在进行对比实验之前，统一环境变量、调整算法参数是非常必要的。环境变量主要包括：数据流的速度、数据对象的衰减速度。本文默认将数据流中数据对象的到达速率设为1 000 pt/ms，统一算法中数据对象的权重衰减函数f=λ-a=0.998，而对比算法的参数设置参考其原始论文。在GCStream-OD算法中对异常检测结果有较大影响的参数主要有网格边长len、核心网格集合LD的大小Ncg、网格第k距离中的k值以及异常网格阈值εo。为了对这些参数进行合理选择，本文对其进行了实验探索。

4.2.1 网格边长len

GCStream-OD算法中，若len太小，网格切分太小，将会花费大量的时间在网格耦合的处理上，不能满足实时性要求；若len过大，容易将异常和非异常划分到同一网格中，对算法精确度会造成影响。对于不同数据集，数据的最大值与最小值的差值不同，需要对不同数据集选取不同的len。图3展示了在不同数据集上，不同len值对算法F1指标值的影响。从图3中可以看出,GCStream-OD算法在数据集KDD CUP99上当len取值为1 200时F1值最大，所以对于KDD CUP99数据集实验选取len=1000。同理可得，在CoverType数据集上选取len=1500，在data_OD数据集上选取len=7，在data_http数据集上选取len=2000，在Poker Hand数据集上选取len=6。

Figure 4 Influence of different Ncg values on F1 on different data sets of GCStream-OD algorithm图4 GCStream-OD算法在不同数据集上不同Ncg值对F1的影响

Figure 5 Influence of different k values on F1 on different data sets of GCStream-OD algorithm图5 GCStream-OD算法在不同数据集上不同k值对F1的影响

4.2.2 核心网格集合大小

核心网格集合由权重大于阈值的网格组成，并且核心网格集合的大小对GCStream-OD算法的结果有直接影响。本节以评估指标F1的大小来探索参数Ncg的最佳取值，实验结果如图4所示。在KDD CUP99数据集上,当Ncg=7时取得最好的F1值。在CoverType数据集上，当Ncg=4时取得最好的F1值。对于数据集data_OD，当Ncg=1时取得最好的F1值。在data_http数据集上，当Ncg=12时取得最好的F1值。在Poker Hand数据集上，当Ncg=6时取得最好的F1值。综上所述，在KDD CUP99、CoverType、data_OD、data_http和Poker Hand数据集上，Ncg的取值分别为7,4,1,12和6。

4.2.3 网格第k距离中的k值

网格第k距离用来度量网格局部区域的密度，k值越小，局部区域密度越大；反之，k值越大，局部区域密度越小。不同数据集的数据映射到网格后所得到的网格局部区域的密度值不同，因此对于不同的数据集需要找到其最佳的网格第k距离。本节将根据评估指标F1的好坏来探索不同数据集的最佳k值，实验结果如图5所示。在KDD CUP99数据集上，当k=6时取得最好的F1值，因此在KDD CUP99数据集上设置k=6。在CoverType数据集上，当k=5时取得最好的F1值，因此设置k=5。对于数据集data_OD，当k=7时取得最好的F1值，因此设置k=7。在data_http数据集上，当k=11时取得最好的F1值，因此设置k=11。在Poker Hand数据集上，当k=5时取得最好的F1值，因此设置k=5。

4.2.4 异常网格阈值εo

异常网格阈值εo直接影响异常数据的检测。当εo取值过小时，许多非异常数据对象会被划分为异常数据对象，造成精确度过低；当εo取值过大时，许多异常数据对象会被划分为非异常数据对象，造成召回率过低。对于不同数据集，异常网格阈值εo也不尽相同。通过评估指标F1的大小，本节将对不同数据集最适合的εo值进行探索，实验结果如图6所示。在KDD CUP99数据集上，当εo=3.5时F1值最高。在CoverType数据集上当εo=2.4时F1值最高。对于data_OD数据集当εo=2.4时F1值最高。在data_http数据集上，在εo=19时取得最好的F1值；在Poker Hand数据集上，在εo=1时F1值最高。综上所述，在KDD CUP99、CoverType、data_OD、data_http和Poker Hand数据集上εo的取值分别为3.5，2.4，2，19和1。

Figure 6 Influence of different εo values on F1 on different data sets of GCStream-OD algorithm图6 GCStream-OD算法在不同数据集上不同εo值对F1的影响

4.3 实验结果

本节主要对GCStream-OD算法的检测质量以及效率进行实验评估。

4.3.1 算法检测质量

图7展示了GCStream-OD算法与CORM和iForest算法的实验结果对比情况。其中，GCStream-OD算法的F1值在CoverType、data_OD和Poker Hand数据集上均高于基准算法。虽然iForest算法在KDD CUP99和data_http上获得了更好的F1值，但GCStream-OD的F1值仍接近于iForest。

Figure 7 Precision,recall and F1 comparison of different algorithms on different data sets图7 各算法在不同数据集上的Precision、Recall和F1对比

通过对实验结果的分析可知，在KDD CUP99数据集上，GCStream-OD算法略低于iForest算法的主要原因是部分真实异常在分布上与非异常数据接近，被划分到非核心的高权重网格中；且数量较少，对网格权重影响小，使得所在网格被剪去而不能被检测出来，造成Recall值过低。在data_http数据集上本文算法的F1略低于iForest算法主要包含2个原因，第1个原因与KDD CUP99数据集相同;第2个原因是非异常数据被剪去，造成数据密度因子denF过高，而距离因子disF不能消除其影响，使得正常数据被划为异常，导致Precision值变低。

CORM算法与本文算法原理类似，首先对数据流进行划分，然后丢弃正常值区域，保留每个簇的中心和候选异常。但是，CORM算法忽略了数据对象之间的影响，而GCStream-OD算法采用网格耦合的方式，更多地考虑了数据对象之间的相互影响，因此GCStream-OD算法在整体性能上优于CORM算法。

4.3.2 算法效率

实时检测异常数据对于数据流异常检测算法至关重要，所以本文对GCStream-OD算法、CORM算法以及iForest算法的效率进行了对比。实验结果如图8所示，时间单位为ms。从图8可以看出，本文算法在各个数据集上的耗时均较少。这是因为本文以网格汇总数据流并采用剪枝策略，最终仅对少量的低权重网格进行处理，大大降低了算法需要处理的对象数目，提高了算法效率。

Figure 8 Time efficiency comparison of different algorithms on different data sets图8 各算法在不同数据集上的时间效率对比

5 结束语

本文针对现有数据流异常检测算法大都以每个数据对象为处理单元，算法效率较低，而以网格结构汇总并提取数据流摘要信息，能够较快地处理数据流，但是假设网格之间彼此独立，忽略数据之间的相关性的不足，提出了一种基于网格耦合的数据流异常检测算法GCStream-OD。首先，通过网格耦合实现了对数据流更精确的汇总，同时配合剪枝策略提高处理效率；其次，本文根据异常周围邻居较少、密度较低并且距正常值较远的特点为每个网格分配异常因子度量其异常程度；最后，通过在真实数据集上进行实验，对比了本文算法与其他算法检测质量和效率等，实验结果表明，本文所提GCStream-OD算法具有较高的异常检测质量和效率。

GCStream-OD算法以网格为处理单元，采用了网格耦合的思想来提升算法质量，并通过实验证明网格耦合是有效的，但对于一些数据集(如Poker Hand)该算法取得的结果还不尽人意。为了提高GCStream-OD算法的泛化能力，设计更好的网格耦合方式和剪枝策略将是我们未来工作的研究重点。