李卓卡+周亮+羅雙虎

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

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

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

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

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)計學(xué)和集合的角度一般定義如下：設(shè)I={I1，I2，…，In}是項集合，In表示一個項，n是I的維數(shù)，事務(wù)T是項的集合，每個事務(wù)有一個標(biāo)識符為TID。在網(wǎng)絡(luò)管理系統(tǒng)的數(shù)據(jù)庫中，I就是整個系統(tǒng)中事件的種類，In就是一類事件，n為種類數(shù)，T為具體解決網(wǎng)絡(luò)故障的方法。

1.2 Apriori算法基本原理

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

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

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

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

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

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

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

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

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

① 計算1-items頻繁項集L1；

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

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

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

2.2 基于多叉樹的Apriori算法

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

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

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

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

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

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

步驟3 計算k-items頻繁項目集：

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

3 實驗結(jié)果及結(jié)論分析

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

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

4 結(jié)束語

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

參考文獻：

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

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

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

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

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

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

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

[8] 陳宇暉，曹敦，傅明.一種用作頻繁項集挖掘的改進Apriori算法[J].微計算機信息，2010.

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