基于多叉樹Apriori的網(wǎng)絡(luò)管理數(shù)據(jù)挖掘

李卓卡+周亮+羅雙虎

摘要：在網(wǎng)絡(luò)管理系統(tǒng)中，通過SNMP、探針、Agent等采集到了大量的性能數(shù)據(jù)，想要從這些數(shù)據(jù)中快速挖掘出有用的數(shù)據(jù)，就需要有先進(jìn)的數(shù)據(jù)挖掘算法，傳統(tǒng)的Apriori算法會(huì)產(chǎn)生大量的候選集，占用大量主存空間，降低了效率，該文結(jié)合多叉樹的思想對(duì)Apriori進(jìn)行了改進(jìn)，一次掃描數(shù)據(jù)庫之后生成一個(gè)多叉樹鏈表，可以很快地計(jì)算項(xiàng)集的支持度，并且無需考慮重復(fù)項(xiàng)集，最后通過實(shí)驗(yàn)數(shù)據(jù)證實(shí)了改進(jìn)算法在處理網(wǎng)絡(luò)流量分析的效率。

關(guān)鍵詞：網(wǎng)絡(luò)管理；數(shù)據(jù)挖掘；多叉樹；Apriori；剪枝

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）29-0235-02

在網(wǎng)絡(luò)管理系統(tǒng)中的各類數(shù)據(jù)通過SNMP、探針、Agent等收集并匯集到數(shù)據(jù)庫中，想要快速地從系統(tǒng)數(shù)據(jù)庫挖掘出這些有用的信息，就需要先進(jìn)的挖掘算法來實(shí)現(xiàn)。在數(shù)據(jù)挖掘技術(shù)中，關(guān)聯(lián)規(guī)則挖掘是一個(gè)經(jīng)典的挖掘方法[1]，本文針對(duì)上述問題對(duì)關(guān)聯(lián)規(guī)則中的Apriori算法進(jìn)行優(yōu)化來提升關(guān)聯(lián)規(guī)則的質(zhì)量，更有組織的處理挖掘到的關(guān)聯(lián)規(guī)則，提高系統(tǒng)的挖掘效率，為后續(xù)的運(yùn)維工作提供有力支撐。

1 相關(guān)技術(shù)介紹

1.1 關(guān)聯(lián)規(guī)則基本概念

關(guān)聯(lián)規(guī)則是挖掘事務(wù)或數(shù)據(jù)之間存在的關(guān)聯(lián)關(guān)系[2]，以統(tǒng)計(jì)學(xué)和集合的角度一般定義如下：設(shè)I={I1，I2，…，In}是項(xiàng)集合，In表示一個(gè)項(xiàng)，n是I的維數(shù)，事務(wù)T是項(xiàng)的集合，每個(gè)事務(wù)有一個(gè)標(biāo)識(shí)符為TID。在網(wǎng)絡(luò)管理系統(tǒng)的數(shù)據(jù)庫中，I就是整個(gè)系統(tǒng)中事件的種類，In就是一類事件，n為種類數(shù)，T為具體解決網(wǎng)絡(luò)故障的方法。

1.2 Apriori算法基本原理

Apriori算法在關(guān)聯(lián)規(guī)則研究中屬于經(jīng)典且比較成熟的算法，該算法通過幾次迭代來計(jì)算數(shù)據(jù)庫中的頻繁項(xiàng)集。第k次迭代計(jì)算出所有頻繁k-項(xiàng)集（含k個(gè)元素的項(xiàng)集）。每次迭代都有兩步：產(chǎn)生候選集；計(jì)算和選擇候選集。

Apriori算法的計(jì)算過程分為發(fā)現(xiàn)頻繁集和提取強(qiáng)規(guī)則兩步，主要思想是設(shè)定最小支持度，對(duì)數(shù)據(jù)庫進(jìn)行第一次掃描，生成頻繁1-項(xiàng)集L1，L1經(jīng)過連接生成C2，然后第二次掃描數(shù)據(jù)庫，通過最小支持度得到L2，迭代終止的條件是第k步的迭代，頻繁k-項(xiàng)集的候選頻繁項(xiàng)集Ck=?，此時(shí)就會(huì)產(chǎn)生規(guī)則的全部最大頻繁項(xiàng)集L={L1，L2，...，Lm}。

傳統(tǒng)的Apriori算法會(huì)產(chǎn)生大量的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫這兩大缺陷會(huì)導(dǎo)致巨大的I/O開銷以及在產(chǎn)生頻繁項(xiàng)集的過程中，對(duì)候選項(xiàng)集進(jìn)行剪枝的過程會(huì)增加運(yùn)算時(shí)間，占用大量主存空間，這會(huì)在很大程度上降低系統(tǒng)的運(yùn)行針對(duì)算法的運(yùn)行效率。

2 網(wǎng)絡(luò)管理系統(tǒng)多叉樹Apriori算法改進(jìn)

2.1 事務(wù)項(xiàng)目的多叉樹鏈表表示

多叉樹算法基本思想：采用基于多叉樹的孩子兄弟表示法的數(shù)據(jù)結(jié)構(gòu)，其中兄弟節(jié)點(diǎn)根據(jù)數(shù)據(jù)庫掃描的順序從左到右橫向排列，樹的每一個(gè)節(jié)點(diǎn)由項(xiàng)和頻度變量構(gòu)成，設(shè)Ii（其中i=1，2，...，m；m 為項(xiàng)目總數(shù)）為項(xiàng)的編號(hào)，j為頻度變量，節(jié)點(diǎn)可表示為，在事務(wù)數(shù)據(jù)庫的項(xiàng)集中，每個(gè)項(xiàng)后緊跟的項(xiàng)作為該項(xiàng)的孩子，如果有重復(fù)的項(xiàng)集，將節(jié)點(diǎn)中的頻度變量加1。利用這種結(jié)構(gòu)，對(duì)數(shù)據(jù)庫只需要進(jìn)行一次掃描，后續(xù)只需對(duì)多叉樹鏈表進(jìn)行操作，避免多次掃描數(shù)據(jù)庫，可以顯著減少I/O開銷，大大提高了系統(tǒng)的性能。

假如在某個(gè)事務(wù)數(shù)據(jù)庫中，經(jīng)過預(yù)處理后得到的數(shù)據(jù)庫模式為〈事務(wù)標(biāo)識(shí)， 事件1， 事件2 ， …，事件6〉，它按事務(wù)標(biāo)識(shí)值由小到大排列，如表1所示。掃描數(shù)據(jù)庫時(shí)，將緊跟這個(gè)項(xiàng)的項(xiàng)作為該項(xiàng)的孩子，如果該項(xiàng)已存在相同的孩子只需要將頻度變量i加1。在本算法中，將根節(jié)點(diǎn)表示為1，子節(jié)點(diǎn)為Ii，根據(jù)出現(xiàn)的順序依次向下分支節(jié)，每個(gè)分支為一個(gè)事務(wù)，其對(duì)應(yīng)的事務(wù)項(xiàng)目多叉樹結(jié)構(gòu)如表 1所示。

按照上述思想構(gòu)造多叉樹結(jié)構(gòu)：

設(shè)最小支持度為Minsup=3，根據(jù)節(jié)點(diǎn)的頻度和與最小支持度比較，刪除小于最小支持度的節(jié)點(diǎn)，可以得到k-items頻繁項(xiàng)集，思路如下：

① 計(jì)算1-items頻繁項(xiàng)集L1；

② 在L1的基礎(chǔ)上生成2-items頻繁項(xiàng)集L2；

③在L2的基礎(chǔ)上生成3-items頻繁項(xiàng)集L3；

④在L3的基礎(chǔ)上生成 items頻繁項(xiàng)集L4的支持度都小于最小支持度，算法結(jié)束。

2.2 基于多叉樹的Apriori算法

根據(jù)上述事務(wù)項(xiàng)目的多叉鏈表表示法，將事務(wù)數(shù)據(jù)庫的掃描轉(zhuǎn)化為對(duì)多叉鏈表的操作，并對(duì)多叉鏈表進(jìn)行頻繁項(xiàng)目集的挖掘。設(shè)項(xiàng)目集合I={I1，I2，...，Im}，Ic（c的取值范圍為[1，m]）表示一個(gè)項(xiàng)目；Lk表示頻繁k項(xiàng)集，當(dāng)Li=?時(shí)，k=i-1；TID={T1，T2，...，Tn}表示事務(wù)的集合，H={h1，h2，...，hn}表示各個(gè)事務(wù)所包含的項(xiàng)目數(shù)集合，TID和H是一一對(duì)應(yīng)的關(guān)系，TID為多叉樹的所有分支；treeNode表示所有的節(jié)點(diǎn)，treeNode[index]（1≤index≤h1+h2+...+hn）表示某個(gè)具體節(jié)點(diǎn)，treeNode[index].obj表示節(jié)點(diǎn)中的具體對(duì)象，treeNode[index].obj∈{I1，I2，...，Im}，treeNode[index].count表示該對(duì)象的頻度；minsup表示最小支持度，根據(jù)minsup進(jìn)行多叉樹鏈表的剪枝操作。

首先掃描數(shù)據(jù)庫，將事務(wù)集合中所有的項(xiàng)目轉(zhuǎn)化為多叉樹的節(jié)點(diǎn)，根據(jù)上述規(guī)則將所有節(jié)點(diǎn)構(gòu)成多叉樹鏈表；根據(jù)節(jié)點(diǎn)對(duì)象的頻度與minsup進(jìn)行對(duì)比，刪除小于minsup的節(jié)點(diǎn)以及其子節(jié)點(diǎn)，可得到頻繁1項(xiàng)集L1，并重新生成鏈表；根據(jù)頻繁1項(xiàng)集對(duì)項(xiàng)目進(jìn)行兩兩組合，并對(duì)重新生成的鏈表進(jìn)行遍歷，計(jì)算組合項(xiàng)的頻度并與minsup進(jìn)行比較，舍去小于minsup的組合項(xiàng)，可得到頻繁2項(xiàng)集L2；同理可得到頻繁3項(xiàng)集L3，頻繁4項(xiàng)集L4，……，頻繁k項(xiàng)集Lk（當(dāng)L（k+1）=?時(shí)）。改進(jìn)多叉樹Apiori算法的具體運(yùn)行步驟如下：endprint

步驟1 掃描數(shù)據(jù)庫構(gòu)造多叉樹鏈表：

首先掃描數(shù)據(jù)庫，根據(jù)事務(wù)中的項(xiàng)得到節(jié)點(diǎn)集合，節(jié)點(diǎn)由節(jié)點(diǎn)對(duì)象Ii和該對(duì)象的頻度count組成。對(duì)于多叉樹的每一個(gè)分支，如果存在重復(fù)節(jié)點(diǎn)對(duì)象，則該對(duì)象的頻度為出現(xiàn)的次數(shù)。

步驟2 遍歷多叉樹生成1-items頻繁項(xiàng)目集L1：

根據(jù)生成的多叉樹鏈表遍歷所有節(jié)點(diǎn)，將所有節(jié)點(diǎn)對(duì)象Ii相同的頻度相加，可以得到Ii項(xiàng)的頻度和，如果Ii項(xiàng)的頻度和小于最小支持度，刪除與該項(xiàng)有關(guān)的節(jié)及該節(jié)點(diǎn)下面的所有孩子節(jié)點(diǎn)，剩余項(xiàng)即為1-items頻繁項(xiàng)集，并可生成剪枝后的鏈表。

步驟3 計(jì)算k-items頻繁項(xiàng)目集：

根據(jù)1-items頻繁項(xiàng)集，可組合2-items的項(xiàng)，根據(jù)2-items項(xiàng)的第二項(xiàng)遍歷剪枝后的鏈表，得到該項(xiàng)的頻度和。去掉項(xiàng)數(shù)少于最小支持度的2-items項(xiàng)，就可以得到2-items頻繁項(xiàng)集，同理計(jì)算頻繁3-items頻繁項(xiàng)集， items頻繁項(xiàng)集L4，...，k-items頻繁項(xiàng)集Lk。

3 實(shí)驗(yàn)結(jié)果及結(jié)論分析

本文在相同環(huán)境下用C++ 分別實(shí)現(xiàn)了Apriori 算法、基于數(shù)組的Apriori 算法、基于十字鏈表Apriori 算法與本文改進(jìn)的Apriori 算法程序，并對(duì)運(yùn)行結(jié)果進(jìn)行比較測(cè)試。測(cè)試環(huán)境為：Intel Core i7-4770 CPU 、8GB 內(nèi)存， Win7操作系統(tǒng)。圖 3為四種算法在10種不同最小支持度下處理數(shù)據(jù)庫中所有事務(wù)時(shí)的運(yùn)行時(shí)間曲線。

從圖 3可以看出，無論最小支持度大還是小，改進(jìn)的基于多叉樹的Apriori算法運(yùn)行時(shí)間曲線都在其他幾個(gè)算法的下面，且與未改進(jìn)的Apriori算法相比時(shí)間開銷顯著降低；改進(jìn)的基于多叉樹鏈表的Apriori 算法，可以快速高效地得到遠(yuǎn)洋漁船補(bǔ)給信息系統(tǒng)中各個(gè)漁船物資情況所需要的強(qiáng)關(guān)聯(lián)規(guī)則。該算法采用多叉樹鏈表的數(shù)據(jù)結(jié)構(gòu)，只需要訪問一次數(shù)據(jù)庫，多叉樹鏈表的剪枝操作，避免了對(duì)重復(fù)項(xiàng)集的考慮，減少了事務(wù)數(shù)據(jù)的大小，大大提高了算法的運(yùn)行效率。

4 結(jié)束語

在網(wǎng)絡(luò)管理過程中，首先要分析造成網(wǎng)絡(luò)異常的原因才能找出相應(yīng)的解決方案。本文網(wǎng)絡(luò)管理系統(tǒng)中如何快速找到有用信息的問題，利用多叉樹數(shù)據(jù)結(jié)構(gòu)來這種對(duì)原始的Apriori算法進(jìn)行改進(jìn)，一次掃描數(shù)據(jù)庫之后生成一個(gè)多叉樹鏈表，可以很快地計(jì)算項(xiàng)集的支持度，并且無需考慮重復(fù)項(xiàng)集，最后通過實(shí)驗(yàn)數(shù)據(jù)證實(shí)了改進(jìn)算法在處理網(wǎng)絡(luò)流量分析的效率。

參考文獻(xiàn)：

[1] 何勝文，周紹梅，姚華.基于二叉樹結(jié)構(gòu)的關(guān)聯(lián)挖掘算法[J].福建電腦，2007，3（1）.

[2] 李曉虹，尚晉.一種改進(jìn)的新Apriori算法[J].計(jì)算機(jī)科學(xué)，2007.

[3] 張世勛.基于.NET的招生管理信息系統(tǒng)開發(fā)與研究[D].大連海事大學(xué)碩士論文，2007.

[4] 章義來，劉少蘭，李云輝，等.數(shù)據(jù)挖掘在電子政務(wù)數(shù)據(jù)分析的應(yīng)用研究[J].情報(bào)雜志，2005.

[5] 張彥，劉偉結(jié).合超市數(shù)據(jù)的關(guān)聯(lián)規(guī)則Apriori算法淺析[C].2007北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)通信與信息技術(shù)會(huì)議，2008.

[6] 段繼光.基于LBS的個(gè)人監(jiān)控服務(wù)系統(tǒng)的研究和實(shí)現(xiàn)[D].河北師范大學(xué)碩士論文，2014.

[7] 徐從富.關(guān)聯(lián)規(guī)則挖掘技術(shù)研究進(jìn)展程舒通[J].計(jì)算機(jī)應(yīng)用研究，2009.

[8] 陳宇暉，曹敦，傅明.一種用作頻繁項(xiàng)集挖掘的改進(jìn)Apriori算法[J].微計(jì)算機(jī)信息，2010.

[9] 王梟翔.基于相關(guān)興趣度的關(guān)聯(lián)規(guī)則挖掘[D].蘭州交通大學(xué)碩士論文，2013.endprint