基于多叉树Apriori的网络管理数据挖掘

李卓卡+周亮+罗双虎

摘要：在网络管理系统中，通过SNMP、探针、Agent等采集到了大量的性能数据，想要从这些数据中快速挖掘出有用的数据，就需要有先进的数据挖掘算法，传统的Apriori算法会产生大量的候选集，占用大量主存空间，降低了效率，该文结合多叉树的思想对Apriori进行了改进，一次扫描数据库之后生成一个多叉树链表，可以很快地计算项集的支持度，并且无需考虑重复项集，最后通过实验数据证实了改进算法在处理网络流量分析的效率。

关键词：网络管理；数据挖掘；多叉树；Apriori；剪枝

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）29-0235-02

在网络管理系统中的各类数据通过SNMP、探针、Agent等收集并汇集到数据库中，想要快速地从系统数据库挖掘出这些有用的信息，就需要先进的挖掘算法来实现。在数据挖掘技术中，关联规则挖掘是一个经典的挖掘方法[1]，本文针对上述问题对关联规则中的Apriori算法进行优化来提升关联规则的质量，更有组织的处理挖掘到的关联规则，提高系统的挖掘效率，为后续的运维工作提供有力支撑。

1 相关技术介绍

1.1 关联规则基本概念

关联规则是挖掘事务或数据之间存在的关联关系[2]，以统计学和集合的角度一般定義如下：设I={I1，I2，…，In}是项集合，In表示一个项，n是I的维数，事务T是项的集合，每个事务有一个标识符为TID。在网络管理系统的数据库中，I就是整个系统中事件的种类，In就是一类事件，n为种类数，T为具体解决网络故障的方法。

1.2 Apriori算法基本原理

Apriori算法在关联规则研究中属于经典且比较成熟的算法，该算法通过几次迭代来计算数据库中的频繁项集。第k次迭代计算出所有频繁k-项集（含k个元素的项集）。每次迭代都有两步：产生候选集；计算和选择候选集。

Apriori算法的计算过程分为发现频繁集和提取强规则两步，主要思想是设定最小支持度，对数据库进行第一次扫描，生成频繁1-项集L1，L1经过连接生成C2，然后第二次扫描数据库，通过最小支持度得到L2，迭代终止的条件是第k步的迭代，频繁k-项集的候选频繁项集Ck=?，此时就会产生规则的全部最大频繁项集L={L1，L2，...，Lm}。

传统的Apriori算法会产生大量的候选集，以及可能需要重复扫描数据库这两大缺陷会导致巨大的I/O开销以及在产生频繁项集的过程中，对候选项集进行剪枝的过程会增加运算时间，占用大量主存空间，这会在很大程度上降低系统的运行针对算法的运行效率。

2 网络管理系统多叉树Apriori算法改进

2.1 事务项目的多叉树链表表示

多叉树算法基本思想：采用基于多叉树的孩子兄弟表示法的数据结构，其中兄弟节点根据数据库扫描的顺序从左到右横向排列，树的每一个节点由项和频度变量构成，设Ii（其中i=1，2，...，m；m 为项目总数）为项的编号，j为频度变量，节点可表示为，在事务数据库的项集中，每个项后紧跟的项作为该项的孩子，如果有重复的项集，将节点中的频度变量加1。利用这种结构，对数据库只需要进行一次扫描，后续只需对多叉树链表进行操作，避免多次扫描数据库，可以显著减少I/O开销，大大提高了系统的性能。

假如在某个事务数据库中，经过预处理后得到的数据库模式为〈事务标识， 事件1， 事件2 ， …，事件6〉，它按事务标识值由小到大排列，如表1所示。扫描数据库时，将紧跟这个项的项作为该项的孩子，如果该项已存在相同的孩子只需要将频度变量i加1。在本算法中，将根节点表示为1，子节点为Ii，根据出现的顺序依次向下分支节，每个分支为一个事务，其对应的事务项目多叉树结构如表 1所示。

按照上述思想构造多叉树结构：

设最小支持度为Minsup=3，根据节点的频度和与最小支持度比较，删除小于最小支持度的节点，可以得到k-items频繁项集，思路如下：

① 计算1-items频繁项集L1；

② 在L1的基础上生成2-items频繁项集L2；

③在L2的基础上生成3-items频繁项集L3；

④在L3的基础上生成 items频繁项集L4的支持度都小于最小支持度，算法结束。

2.2 基于多叉树的Apriori算法

根据上述事务项目的多叉链表表示法，将事务数据库的扫描转化为对多叉链表的操作，并对多叉链表进行频繁项目集的挖掘。设项目集合I={I1，I2，...，Im}，Ic（c的取值范围为[1，m]）表示一个项目；Lk表示频繁k项集，当Li=?时，k=i-1；TID={T1，T2，...，Tn}表示事务的集合，H={h1，h2，...，hn}表示各个事务所包含的项目数集合，TID和H是一一对应的关系，TID为多叉树的所有分支；treeNode表示所有的节点，treeNode[index]（1≤index≤h1+h2+...+hn）表示某个具体节点，treeNode[index].obj表示节点中的具体对象，treeNode[index].obj∈{I1，I2，...，Im}，treeNode[index].count表示该对象的频度；minsup表示最小支持度，根据minsup进行多叉树链表的剪枝操作。

首先扫描数据库，将事务集合中所有的项目转化为多叉树的节点，根据上述规则将所有节点构成多叉树链表；根据节点对象的频度与minsup进行对比，删除小于minsup的节点以及其子节点，可得到频繁1项集L1，并重新生成链表；根据频繁1项集对项目进行两两组合，并对重新生成的链表进行遍历，计算组合项的频度并与minsup进行比较，舍去小于minsup的组合项，可得到频繁2项集L2；同理可得到频繁3项集L3，频繁4项集L4，……，频繁k项集Lk（当L（k+1）=?时）。改进多叉树Apiori算法的具体运行步骤如下：endprint

步骤1 扫描数据库构造多叉树链表：

首先扫描数据库，根据事务中的项得到节点集合，节点由节点对象Ii和该对象的频度count组成。对于多叉树的每一个分支，如果存在重复节点对象，则该对象的频度为出现的次数。

步骤2 遍历多叉树生成1-items频繁项目集L1：

根据生成的多叉树链表遍历所有节点，将所有节点对象Ii相同的频度相加，可以得到Ii项的频度和，如果Ii项的频度和小于最小支持度，删除与该项有关的节及该节点下面的所有孩子节点，剩余项即为1-items频繁项集，并可生成剪枝后的链表。

步骤3 计算k-items频繁项目集：

根据1-items频繁项集，可组合2-items的项，根据2-items项的第二项遍历剪枝后的链表，得到该项的频度和。去掉项数少于最小支持度的2-items项，就可以得到2-items频繁项集，同理计算频繁3-items频繁项集， items频繁项集L4，...，k-items频繁项集Lk。

3 实验结果及结论分析

本文在相同环境下用C++ 分别实现了Apriori 算法、基于数组的Apriori 算法、基于十字链表Apriori 算法与本文改进的Apriori 算法程序，并对运行结果进行比较测试。测试环境为：Intel Core i7-4770 CPU 、8GB 内存， Win7操作系统。图 3为四种算法在10种不同最小支持度下处理数据库中所有事务时的运行时间曲线。

从图 3可以看出，无论最小支持度大还是小，改进的基于多叉树的Apriori算法运行时间曲线都在其他几个算法的下面，且与未改进的Apriori算法相比时间开销显著降低；改进的基于多叉树链表的Apriori 算法，可以快速高效地得到远洋渔船补给信息系统中各个渔船物资情况所需要的强关联规则。该算法采用多叉树链表的数据结构，只需要访问一次数据库，多叉树链表的剪枝操作，避免了对重复项集的考虑，减少了事务数据的大小，大大提高了算法的运行效率。

4 结束语

在网络管理过程中，首先要分析造成网络异常的原因才能找出相应的解决方案。本文网络管理系统中如何快速找到有用信息的问题，利用多叉树数据结构来这种对原始的Apriori算法进行改进，一次扫描数据库之后生成一个多叉树链表，可以很快地计算项集的支持度，并且无需考虑重复项集，最后通过实验数据证实了改进算法在处理网络流量分析的效率。

参考文献：

[1] 何胜文，周绍梅，姚华.基于二叉树结构的关联挖掘算法[J].福建电脑，2007，3（1）.

[2] 李晓虹，尚晋.一种改进的新Apriori算法[J].计算机科学，2007.

[3] 张世勋.基于.NET的招生管理信息系统开发与研究[D].大连海事大学硕士论文，2007.

[4] 章义来，刘少兰，李云辉，等.数据挖掘在电子政务数据分析的应用研究[J].情报杂志，2005.

[5] 张彦，刘伟结.合超市数据的关联规则Apriori算法浅析[C].2007北京地区高校研究生学术交流会通信与信息技术会议，2008.

[6] 段繼光.基于LBS的个人监控服务系统的研究和实现[D].河北师范大学硕士论文，2014.

[7] 徐从富.关联规则挖掘技术研究进展程舒通[J].计算机应用研究，2009.

[8] 陈宇晖，曹敦，傅明.一种用作频繁项集挖掘的改进Apriori算法[J].微计算机信息，2010.

[9] 王枭翔.基于相关兴趣度的关联规则挖掘[D].兰州交通大学硕士论文，2013.endprint