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

??

?

??

基于多叉树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.2Apriori算法基本原理

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}表示各个事务所包含的项目数集合