周 燕，肖 莉

(华南农业大学 数学与信息学院，广东 广州 510642)

0 引 言

网络异常数据挖掘能够在海量网络用户行为数据中分析出有价值信息[1]，用以评估网络环境的安全性并有针对性地阻挡黑客入侵行为。K-means算法(K均值算法)简单易懂、收敛速度快、执行效率高，在数据分析与模式识别等领域应用广泛[2]：杜佳颖等针对K-means算法中心随机性选取导致的收敛效果差的问题进行改进[3]，采用K-means++选择K-means算法的初始中心点，聚类划分质量大幅提升；解滨等对K-means算法固定k值问题改进[4]，通过动态阈值调整优化算法聚类数量，数据攻击类型逐渐增多、攻击行为较为复杂环境下检测率和误检率理想。关联规则算法可挖掘出网络数据中异常数据特征量：杨光辉等使用改进IAA算法识别网络入侵[5]，使用Map-Reduce并行技术与矩阵加强Apriori算法的并行处理能力，产生关联规则的效率更高、用时较短。王婷等基于无监督学习聚类方法Bi-kmeans对网络流量新特征值向量进行聚类，得到未知攻击类型判别纠正项[6]，获取初始化深度神经网络的权重值预判结果，对比未知攻击类型判别纠正项与预判结果完成网络攻击行为判定。

结合以上研究本文提出一种改进关联聚类算法挖掘网络用户数据异常与否，改进关联规则算法用于提取网络数据的特征量，改进K-means算法将网络数据划分为异常数据与非异常数据两个类别，最终取得了理想的应用效果。

1 基于Spark-MML聚类算法的网络异常数据挖掘方法

1.1 改进Apriori关联规则算法

1.1.1 基于关联规则的网络数据特征量提取原理

Apriori算法通过发掘数据之间的关联性表达某事物多个属性同时出现的规律，操作过程简单、容易理解、对数据要求较低。以网络数据为样本基于改进Apriori算法挖掘异常特征数据关联规则，强关联规则挖掘条件如下：支持度大于最小支持度阈值、置信度大于最小置信度阈值[7,8]，由这些强关联规则构成网络异常数据挖掘的数据库[9]。

Apriori算法挖掘网络异常数据特征量过程中，定义m个差异性异常特征量项目的集合为I，I={i1,i2,…,im}， 项目即为其中的一个ik，项集是项目构成的集合。定义网络异常数据库的全部事务集合为数据集D，一个事务用非空项集T描述，即事务T，多个项目组构成了非空项集即一个事务。定义事务T中的两个项集为X和Y，则存在X⊆T，Y⊆T； 如果X和Y均不为空集，同时X∩Y=∅， 那么X⟹Y可以构成事务集D中的一条关联规则。

支持度与置信度是衡量关联规则强度的两个关键变量[10]，事务数据集D内同时并存X与Y项集的事务数量与事务总数的百分比值即为支持度，此处使用support(X⟹Y) 表示；事务数据集D内同时并存X与Y项集的事务数量与包含事务数量的百分比值即为置信度，采用confidence(X⟹Y) 表示。式(1)与式(2)分别为支持度与置信度的计算方法

support(X⟹Y)=P(X∪Y)

(1)

confidence(X⟹Y)=P(Y|X)

(2)

网络异常数据特征量挖掘的强关联规则确定要同时满足最小支持度与最小置信度的预设标准。前者是评估支持度与项集频率的阈值，项集出现的最低频率使用最小支持度来评估[11]，用min_sup表示，取值在0～1之间；关联规则的最低可靠性可通过最小置信度min_conf来评价，最小置信度的取值在0～1之间。而网络异常数据特征量挖掘的强关联规则就是要同时满足预设的最小支持度与最小置信度。

1.1.2 基于Spark的并行化频繁项集挖掘环境设计

Apriori算法经过多次迭代扫描工作量较大，为系统运行造成极大负担。为进一步优化Apriori算法挖掘强关联规则的性能，采用基于项编码和Spark计算框架的Apriori并行化方法[12]，实现Apriori算法的分布式频繁项集挖掘。分布式频繁项集挖掘算法包含两个步骤：

步骤1 应用广播变量存储频繁项集。扫描数据集生成频繁1项集后将其视为频繁k项集存入Spark的广播变量。为了降低数据访问的频次，令所有节点均可共享Spark集群广播变量，此处使用项编码策略，即使用单个项集与其对应编码创建键值对，所占据的存储空间比存储完整数据集占据空间小得多[13,14]，此处设计可以大量降低频繁项集挖掘的时间开销与内存消耗。

步骤2 求取并输出频繁项集k+1。循环迭代，各迭代过程中，节点k+1项集与编码的计算采用并行化策略实现，剪枝完成后将不符合支持度条件的k+1项集删除，从而获取频繁k+1项集；广播变量中的频繁k项集使用上一步骤生成的频繁k+1项集代替，之后的迭代计算中终止条件为：不生成符合支持度条件的深层次频繁项集。

为频繁项集编码策略显著减少计算机存储空间用量，在Spark计算框架展开的并行化频繁项集计算有效节约关联规则挖掘时间，改进Apriori算法减少了传统算法挖掘强关联规则的内存开销与时间复杂程度，为后期K-means算法实现网络异常数据聚类提供有力条件。

1.1.3 基于兴趣度约束与支持度自适应更新的强关联规则提取

传统Apriori算法提取网络异常数据特征量的过程中产生的候选集规模较大，频繁扫描数据库才能求取算法的支持度和置信度，前者提升了算法的内存占用量，后者提升了算法的时间复杂度[15]，为此通过以下两种方式改进Apriori算法提取异常数据特征量的弊端。

(1)兴趣度约束。基于支持度与置信度的关联规则筛选架构存在诸多漏洞：网络数据样本事务集中一部分有价值数据因为其支持度不高而被自动过滤，置信度忽视了规则后项项集在事务集中的支持度，由此获取的网络异常数据关联规则并非完全是感兴趣的。参考郭鹏等的研究引入兴趣度辅助Apriori算法构造关联规则[16]，初步获取频繁项集后基于兴趣度阈值深入筛选有价值的频繁项集[17]。在规则X->Y中，项集X与项集Y间的相关程度即为兴趣度，定义兴趣度阈值为1，式(3)为项集X与项集Y兴趣度的计算方法

(3)

其中，兴趣度大于1情况下项集X与项集Y为正相关关系，兴趣度小于1情况下项集X与项集Y为负相关关系；前者代表若X发生则提高Y发生的几率，后者代表若X发生则降低Y发生的几率；兴趣度值恰好为1说明两个项集之间无相关性。

定义输入数据集为D，基于兴趣度的Apriori算法执行步骤为：

步骤1 输入支持度、置信度阈值与兴趣度三者的阈值；

步骤2 扫描数据库D获取全部出现过的数据，将其视为候选频繁1项集，此刻k=1，那么频繁0项集则为空集；

步骤3 挖掘频繁k项集；

步骤4 设置k=k+1，执行步骤3；

步骤5 基于频繁项集构造提取网络异常数据特征量的规则，这些规则符合预设的置信度阈值与兴趣度阈值。

最后，将满足标准的网络异常数据特征量提取规则输出。

兴趣度在关联规则挖掘中的应用可以避免出现冗余的候选关联规则，使得频繁项集初步生成且未同最小置信度对比的关联规则数量有效精简，这样再进行置信度阈值判断时能够保障待判定关联规则存在现实意义。

(2)支持度自适应更新策略。较长的数据往往存在更多的特征量，存在异常数据的可能性相对较大，传统Ap-riori算法以固定值的方式设置支持度，其缺点是频繁项集随着项数k的增加而快速减少，获取较长的网络用户数据的难度较大[18,19]。为避免这一弊端提出支持度自适应更新机制，设置支持度随着数据长度的增加自适应降低，提高选择异常数据的灵敏程度。定义改进Apriori算法的初始支持度为V0=sup，调整参数定义为ε，增加频繁项集中项目数量并降低支持度[20]，基于式(4)计算迭代第k次时的支持度

Vk=sup*ε*exp(-g)

(4)

上述情况中支持度会随着迭代次数的增加而降低，并且在特定数值时趋于稳定，这样低频并且关键性的信息被保留下来。

1.2 改进K-means聚类算法

改进K-means聚类算法分类网络数据类型过程中通过一个主聚类与多个小分离聚类划分非异常网络数据和异常网络数据，小分离聚类的特点是与主聚类距离较大。此处以Apriori关联规则算法挖掘到的网络数据特征量信息作为K-means聚类的样本数据，进行特征分类。K-means聚类算法的初始聚类中心的选择严重干扰聚类结果的优劣[21]，传统K-means聚类算法初始聚类中心是随机生成，缺点是极易陷入局部最优解导致网络数据分类效果不稳定、波动性较大。为此采用最大最小距离算法(max-min-diatance，MM)确定初始聚类中心并确定K值，降低聚类的不确定性，减少聚类的工作量；但考虑到最大最小距离准则选取聚类中心的依据是距离的远近，首先选取远距离点作为初始点，过于远的距离点极有可能是离群点，离群点作为聚类中心适得其反降低聚类中心确定的精准度；为此，先使用一种基于局部离群因子(LOF)的离群点检测算法剔除K-means聚类的离群点，预处理后基于最大最小距离选择聚类中心并确定K值。

1.2.1 基于可变网格的局部离群点检测

离群点检测目的是初步剔除网络数据样本中的离群点，避免将离群点作为初始聚类中心，应用可变网格策略设计离群点检测算法：该算法利用网格空间作为聚类区域，减少花费在检索聚类区域上的时间开销，保障高精度拾取聚类中心的同时效率大大提升。算法实现过程描述为：

输入：待检测高频数据集、密度阈值、离群点数量，分别用A、Q、v表示；

输出：排名靠前的v个较大的离群因子值对象。

(1)基于可变网格划分策略为待检测高频数据集构建l个网格。网格构建原理如下：确定网格空间作为聚类区域，使用相同大小的间距划分高频数据空间的维度，然后将同此维度类似的区间段合并，得到基于网格划分的空间[22]。一般使用快排法排列原始待检测高频数据集的第i维，相邻区间段相似性求取完毕后依次判断第i维空间中相邻区间段的相似性；反复执行该步骤得到不同维度的相似区间段合并并输出。

(2)各网格单元高频数据点数量求取。定义数据点数量为Ne，e的取值区间为 (1,2,…,l)； 比较密度阈值与数据点数量大小，当数据点数量大于密度阈值时，表示此数据属于异常状态[23,24]，当全部高频数据计算完离群因子方可终止，并记录异常数据结果。待检测数据的离群因子计算方法如式(5)所示

(5)

(3)遍历到异常数据点后需剔除，剔除后继续迭代计算检测异常数据点，最后按照由大至小的顺序排列离群因子值，并保存靠前部分的离群因子值。

1.2.2 基于最大最小距离准则的K值确定

排除离群点后基于最大最小距离准则确定更精准的聚类中心，过程如下：

最大最小距离算法求取欧氏距离后根据最近邻原则将样本点划分到各聚类中心，该算法与传统K-means算法确定中心点策略存在差别，聚类类别K不是凭经验设置，按照以下策略执行：

(1)选择全部数据样本点中的一个对象定义为xi作为首个聚类中心，求取全部数据点与该聚类中心的欧氏距离，方法如式(6)所示

(6)

式中：Xa、Xb均表示样本，d(Xa,Xb) 表示m维空间中两个样本的欧氏距离。欧氏空间内两点的直线距离即为欧氏距离，K-means算法距离过程中样本之间的相似度基于欧氏距离评定。

(2)新的聚类中心即为与xi欧氏距离最大的点，余下全部中心点选择时将这些点归类于集合中：余下全部每个样本点与初始中心点欧氏距离较小者；下一个中心点即为集合中最大值所对应的样本点。基于上述策略循环操作，停止更新聚类中心的条件是不再产生新的聚类中心[25]，高效率得到有效聚类中心K。具体操作步骤如下：

步骤1 在(0,1)区间内选取一个数值并给定，用δ表示，此刻生成初始聚类中心x1，且F1=x1；

步骤2 更新聚类中心的策略如下：首先，求取不同点与F1的欧氏距离用Oi1表示，新的聚类中心F2即为Ok1=max{Oi1} 对应的xk；然后，求取第3个聚类中心，求取前两个聚类中心与不同点之间的距离定义为Oi1、Oi2， 前两个聚类中心之间的距离定义为O12，当面临Ol=max{min(Oi1,Oi2)} 且Ol>δ×O12的情况时 (i=1,2,…,n)， 第3个聚类中心F3即为xl。

确定存在第3个聚类中心之后，确定当前情况是否符合Oj=max{min(Oi1,Oi2,Oi3)} 且Ol>δ×O12， 验证当前存在第4个聚类中心。依照上述推导策略确定下一个聚类中心是否存在，终止更新新的聚类中心的条件是Ol≤δ×O12。

步骤3 汇总聚类中心总数K。

以上算法有机结合了最大最小聚类准则法与局部离群点检测算法，在本次研究中可精准确定聚类中心数值K。

1.2.3 基于改进K-means算法的网络异常数据挖掘

求取各网络用户数据与中心点的距离，对用户数据类型实施分类，操作方法如式(7)与式(8)所示

(7)

(8)

其中，两个网络数据之间的距离以及数据类型集合采用h1,2、Gi描述，特征值描述为c，参数的数量用k表示。

经过以上操作最终得到一个关键聚类与多个分散的聚类，关键聚类视为核心点，计算各点与核心点之间的距离，进而确定当前网络数据是否存在异常：与核心点间的距离越大，验证这一类网络行为数据的异常程度越大；与核心点间的距离越小，验证这一类网络行为数据的异常程度越小。由此可将网络数据划分为异常与非异常两个类别。

1.3 基于Spark-MML聚类算法的网络异常数据挖掘流程

此次研究改进了传统Apriori关联规则算法与传统的K-means聚类算法形成Spark-MML网络异常数据挖掘算法，该算法挖掘网络异常数据方法的流程如图1所示。

图1 基于Spark-MML聚类算法的网络异常数据挖掘流程

图1中基于Spark-MML聚类算法的执行步骤如下：①输入兴趣度阈值、使用自适应更新策略获得支持度值，设置Apriori关联规则算法的初始参数；②在Spark计算模型环境下分布式、并行化的完成频繁项集挖掘工作，引入项编码策略，使用单个项集与其对应编码创建键值对，输出k+1项集当其为空集时输出频繁项集结果，进一步获取网络数据样本的特征量；③基于网格可变离群点检测算法获取离群点并剔除，使用最大最小聚类准则确定K-means聚类的初始聚类中心与K值；④执行K-means聚类算法的步骤获得网络异常数据的分类结果。

2 网络异常数据挖掘测试与分析

本次研究通过仿真实验验证本文方法挖掘网络异常数据的性能。实验采用Matlab进行设计，JDK版本为1.7，Scala版本为2.10.4，实验采用2.5.2版本的Hadoop、2.0.2版本的Spark搭建并行式聚类环境。计算机运行环境均为Intel®CoreTMi5-7200U CPU，2.50 GHz，其中一个主节点内存为8.00 GB，4个从节点内存为4.00 GB；前者硬盘存储空间为1 TB，后者硬盘存储空间为12 TB。

实验采用全面且权威的AWID集作为网络异常数据挖掘的数据集，所用数据集为精简版本，包含4个类型的攻击，分别为DS 1(Normal)、DS 2(Flooding)、DS 3(Impersonation)、DS 4(Injection)；网络异常数据挖掘过程中将本文方法与文献[5]方法、文献[6]方法进行对比测试，以评估本文算法的性能。

2.1 K-means算法聚类中心选取效果分析

本文方法选取K-means聚类中心采用了最大最小距离准则与离群检测算法相结合的策略，避免了聚类中心随机性。为验证此改变有效性采用随机法、最大最小距离准则法、最大最小距离准则+离群检测算法分别确定K-means聚类中心并确定k值，3种方法聚类结果如图2所示。

图2 聚类效果对比

由图2(a)可以看出，随机法共产生6个聚类中心，且其中3个聚类中心集中排列，说明该算法陷入了局部最优，未能科学分类网络的类型，检测出的异常数据包含一定量的正常数据。

图2(b)表明，最大最小距离准则法确定的聚类中心分布相对随机法较为分散、均匀，仅下部两个聚类中心分布相对密集，但仍存在少数聚类中聚集的现象，这是因为该准则虽然采用“距离”变量约束聚类中心的选取很大程度上提升了聚类中心选取的精度，但是该准则中“与已经产生的中心点距离较远的数据点”当选下一个聚类中心的概率极大，所以误选取了离群点作为远距离聚类中心，使聚类中心选择仍存在局部最优情形，导致聚类出现较大偏差，效果仍不理想。

图2(c)显示本文方法获取的聚类中心分布更均匀、未出现聚集性的聚类中心问题，说明该方法没有陷入局部最优；不难分析，该方法使用局部离群点检测算法剔除K-means聚类的离群点，再此基础上基于最大最小距离准则选取正确的聚类中心，为科学聚类提供了双重保障。

2.2 网络异常数据聚类误差分析

测试采用漏报率与误报率评估各个聚类算法分类网络异常数据的性能，衡量算法的准确率情况，两种指标的计算方法如式(9)与式(10)所示

(9)

(10)

式中：B和H分别表示漏报率与误报率，漏报事件数量与误报事件数量分别采用λ1、α1表示，异常事件总数量与事件总数量分别采用λ2、α2表示。

网络异常数据挖掘测试中，统计各算法在3种数据集上的漏报率与误报率表现情况见表1与表2，另外3种方法的平均绝对误差(MAE)、均方根误差(RMSE)见表3。

表1 网络异常数据挖掘的漏报率统计/%

表2 网络异常数据挖掘的误报率统计/%

表3 3种方法的MAE和RMSE均值/%

综合表1与表2数据可知，本文方法挖掘DS 1数据集漏报率为4.32%，比文献[5]方法、文献[6]方法低4.55%、2.32%，误报率比文献[5]方法、文献[6]方法低4.30%、5.02%，其它数据集上本文方法与其它方法

漏报率、误报率差异表现规律亦是如此，可见本文方法挖掘网络异常数据的优势突出。此外，本文方法的MAE、RMSE展现了相对较低的水平。

总体而言，本文方法挖掘3组网络异常数据集类型的准确率较高，漏报率与误报率远远低于另外两种方法。文献[5]算法虽然改进了Apriori算法，但只是对计算支持度、计算并行化策略优化设计，本文方法不仅改进Apriori算法获取关联规则的支持度策略、设计了Spark并行化计算框架，而且在提取异常网络数据过程中引入兴趣度，在基本Apriori算法提取关联规则的基础上加入兴趣度约束，使得关联规则提取水平更高、强度更强，更有利于异常数据的精准挖掘。此外，本文改进了传统的K-means聚类算法，使用“最大最小距离准则+离群点检测算法”联合选取聚类中心，避免了离群点成为聚类中心，因而提高了异常特征量提取的准确度，最后优化了异常数据挖掘的效果。

2.3 网络异常数据挖掘时间曲线分析

测试中3种算法对数据集DS 1～DS 4依次进行迭代聚类，挖掘用户行为数据是否存在异常，统计各算法的时间开销、内存开销如图3所示。

图3 时间开销

曲线图3显示，随着迭代聚类次数的增加，文献[5]方法的时间开销呈现一个峰值状态，在第5次迭代中达到了用时峰值约为23.5 s，当测试结束时算法的用时均值为17.2 s，8次迭代过程中时间曲线为先升高再降低的趋势，但最低用时仍远高于本文方法；同理，文献[6]方法的用时曲线虽为下降趋势，末次迭代用时达到最小值，但仍高达8.5 s，高于本文方法，聚类速度不理想。相比之下，本文方法与文献[6]方法用时曲线走势规律趋近，但时间开销区间仅为[13.5 s,5.1 s]，第3次迭代后的聚类用时较短，挖掘网络异常数据的效率较高。另外，由图4内存开销曲线可知，本文方法聚类过程中计算机内存占用比重较小，且较早的进入内存稳定期，没有显著浮动趋势。

图4 内存开销占比

这是因为本文方法基于Apriori算法求取网络数据的强关联异常特征量过程中，使用项编码策略挖掘频繁项集，首先为生成的频繁项集标记编码，然后在Spark计算框架上实现频繁项集与编码的并行化计算，文献[6]方法虽然使用了高效率的无监督学习聚类方法Bi-kmeans对网络流量特征值进行聚类，但没有布局并行式计算框架，聚类计算的时间开销相对较长；本文方法采用的分布式计算策略有效降低了Apriori算法扫描数据库、挖掘频繁项集的用时，提高了异常特征量提取效率。因此本文方法展现出文献[5]、文献[6]方法不具备的异常数据挖掘效率优势。

3 结束语

本文提出一种改进的关联聚类算法挖掘网络用户数据的异常情况，减少传统算法挖掘强关联规则的内存开销与时间复杂程度，本文网络数据异常分类研究具有以下贡献：使用兴趣度约束关联规则的强度，基于自适应策略确定科学的支持度；基于K-means算法提取网络异常数据特征量过程中进行了离群点检测与剔除，避免离群点成为聚类中心，节约聚类的时间开销。可见，此次研究兼顾了网络异常特征关联规则挖掘与特征分类的性能，未来研究中将考虑引入更多隐藏特征信息作为网络数据异常与否的判断依据，对异常数据的类型进行细分，满足用户对异常行为识别需求。