通信網(wǎng)告警關(guān)聯(lián)規(guī)則的動(dòng)態(tài)挖掘算法

(電子科技大學(xué) 通信與信息工程學(xué)院， 成都 610054)

摘 要：

對(duì)基于數(shù)據(jù)挖掘的通信網(wǎng)告警相關(guān)性分析進(jìn)行了研究。由于通信網(wǎng)絡(luò)是動(dòng)態(tài)變化的，用于動(dòng)態(tài)網(wǎng)絡(luò)資源和服務(wù)的自適應(yīng)關(guān)聯(lián)規(guī)則算法需要充分利用和維護(hù)原有規(guī)則來(lái)發(fā)現(xiàn)新規(guī)則，使網(wǎng)絡(luò)結(jié)構(gòu)與規(guī)則庫(kù)都能快速更新，為此提出了新型的動(dòng)態(tài)關(guān)聯(lián)規(guī)則挖掘算法IDARM。理論分析與仿真實(shí)驗(yàn)都顯示此算法性能優(yōu)越、可擴(kuò)展性好，并在一些特定情況下能顯著提高效率。

關(guān)鍵詞：網(wǎng)絡(luò)差錯(cuò)管理; 數(shù)據(jù)挖掘; 動(dòng)態(tài)關(guān)聯(lián)規(guī)則; 頻繁項(xiàng)集

中圖分類號(hào)：TN91文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)04-1249-04

Novel algorithm for dynamic mining of association rules

WU Jian， LI Xing-ming

（School of Communication Information Engineering， University of Electronic Science Technology of China， Chengdu 610054， China）

Abstract:

This paper described the alarm correlation in communication networks based on data mining. The self-adaptation association rules for dynamic network resource and service built new rules by fully utilizing and maintaining rules formed before， then updated the framework easily and incorporated new discovered rules readily within it. Both theoretical analysis and computer simulations illustrate outstanding performance of the proposed algorithm—IDARM， which can be further optimized by experiments for specific environment.

Key words：network fault management; data mining; dynamic association rules; frequency itemset

0 引言

數(shù)據(jù)挖掘是從數(shù)據(jù)庫(kù)中提取隱含的、事先未知卻又潛在有用信息的一門科學(xué)，也稱數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)(KDD)。通信網(wǎng)中，主要利用挖掘信息快速定位根源告警，恢復(fù)故障，提高網(wǎng)絡(luò)差錯(cuò)管理性能。

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中最為重要的研究課題之一[1，2]。假設(shè)I={i1， i2，…， im}是m個(gè)不同項(xiàng)目的集合，給定交易數(shù)據(jù)庫(kù)D， 其中每個(gè)交易T是I中一組項(xiàng)目的集合， 即TI。每個(gè)交易都有惟一的標(biāo)志符TID。若對(duì)I中任意子集X， 有XT， 就說(shuō)T包含X。一條關(guān)聯(lián)規(guī)則就是一個(gè)形如X≥Y的蘊(yùn)涵式。其中：XI， YI且 X∩Y≠。關(guān)聯(lián)規(guī)則有兩個(gè)固有屬性，即支持度與置信度。若D中s%的交易包含X∩Y， 則關(guān)聯(lián)規(guī)則X≥Y在D中具有支持度s%；若D中c%包含X的交易也同時(shí)包含Y， 則關(guān)聯(lián)規(guī)則X≥Y在D中以可信度c%成立。關(guān)聯(lián)規(guī)則的開采問題就是生成所有滿足用戶指定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則。

1 相關(guān)工作

1.1 經(jīng)典Apriori算法

在眾多關(guān)聯(lián)規(guī)則挖掘算法中，以Agrawal等人[2]提出的Apriori算法最為著名，其后的數(shù)據(jù)挖掘算法大多數(shù)在Apriori算法基礎(chǔ)上進(jìn)行改進(jìn)或衍生變種，如AprioriTid、AprioriHybird等。Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩步：找出事務(wù)數(shù)據(jù)庫(kù)中所有頻繁項(xiàng)集；利用頻繁項(xiàng)集生成所需要的關(guān)聯(lián)規(guī)則。挖掘出所有頻繁項(xiàng)集是算法的核心，占據(jù)整個(gè)計(jì)算量的大部分。基于頻繁項(xiàng)集的向下封閉性，算法采用層次迭代：首先對(duì)數(shù)據(jù)庫(kù)D中所有項(xiàng)目進(jìn)行計(jì)數(shù)，發(fā)現(xiàn)其中的頻繁1項(xiàng)集；由頻繁1項(xiàng)集按一定原則連接生成候選2項(xiàng)集并掃描數(shù)據(jù)庫(kù)進(jìn)行計(jì)數(shù)，發(fā)現(xiàn)所有頻繁2項(xiàng)集；依此類推，直到?jīng)]有新的候選項(xiàng)集產(chǎn)生為止。

1.2 快速動(dòng)態(tài)挖掘FUP算法

Apriori算法能有效挖掘靜態(tài)事務(wù)數(shù)據(jù)庫(kù)中的關(guān)聯(lián)規(guī)則。 然而現(xiàn)實(shí)世界事務(wù)數(shù)據(jù)庫(kù)中， 數(shù)據(jù)是隨時(shí)間的變化而變化的，通信網(wǎng)中的告警也是一個(gè)不斷進(jìn)行的過程，告警行為的模式很可能隨時(shí)間呈現(xiàn)出某種發(fā)展趨勢(shì)， 使得當(dāng)前已發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則不再生效， 而存在新的有效關(guān)聯(lián)規(guī)則有待發(fā)現(xiàn)。因此迫切需要設(shè)計(jì)高效的算法來(lái)更新、維護(hù)和管理已挖掘出來(lái)的頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則。Cheung等人[4，5]提出了增量式更新算法FUP解決關(guān)聯(lián)規(guī)則的高效更新問題。其基本框架與Apriori算法相似，不同之處在于：

a）每次迭代中，原頻繁k項(xiàng)集的支持度由新增數(shù)據(jù)庫(kù)進(jìn)行更新以濾除不再頻繁的項(xiàng)集，這個(gè)過程中只有新增數(shù)據(jù)庫(kù)需要被掃描；

b）在掃描新增數(shù)據(jù)庫(kù)的同時(shí)，其中的候選集被萃取出來(lái)并進(jìn)行計(jì)數(shù)，然后在掃描原始數(shù)據(jù)庫(kù)時(shí)對(duì)計(jì)數(shù)進(jìn)行累計(jì)以找到新頻繁項(xiàng)集；

c）在掃描原始數(shù)據(jù)庫(kù)之前，剪切掉在新增數(shù)據(jù)庫(kù)中已不頻繁的候選集；

d）原始數(shù)據(jù)庫(kù)的保存頻繁k項(xiàng)集與新增數(shù)據(jù)庫(kù)的新頻繁k項(xiàng)集構(gòu)成總頻繁k項(xiàng)集，并進(jìn)行下一輪迭代；

e）每次迭代中，根據(jù)算法刪除更新數(shù)據(jù)庫(kù)中某些交易中的某些項(xiàng)，減小數(shù)據(jù)庫(kù)的大小。

盡管FUP算法能有效發(fā)現(xiàn)和更新頻繁項(xiàng)集，但同樣無(wú)法擺脫Apriori算法的主要缺陷：數(shù)據(jù)庫(kù)規(guī)模通常較大，在每次迭代時(shí)產(chǎn)生候選項(xiàng)目集以及統(tǒng)計(jì)其支持度是非常耗時(shí)的，對(duì)于頻繁項(xiàng)集尤其是頻繁2項(xiàng)集的產(chǎn)生仍需要占用大量的存儲(chǔ)空間；而且在生成Ck的過程中仍需k次掃描整個(gè)事務(wù)數(shù)據(jù)庫(kù)，因而對(duì)海量的數(shù)據(jù)庫(kù)， 算法的效率會(huì)下降， 并且系統(tǒng)開銷也很大。

2 新型的動(dòng)態(tài)挖掘算法

2.1 符號(hào)與定義

為方便描述，給出了如下表示：

DB、DB+、DB-、DB′分別代表原始數(shù)據(jù)庫(kù)、增長(zhǎng)數(shù)據(jù)庫(kù)、刪減數(shù)據(jù)庫(kù)與更新數(shù)據(jù)庫(kù)。

L、L+、L′分別代表原始數(shù)據(jù)庫(kù)，增長(zhǎng)數(shù)據(jù)庫(kù)與更新數(shù)據(jù)庫(kù)的頻繁項(xiàng)集集合。

s代表最小支持度門限。

d、d+、d-、d′分別代表DB、DB+、DB-與DB′的事務(wù)數(shù)據(jù)庫(kù)大小。

Xcount、X+count、X-count、X′count分別代表項(xiàng)集X在DB、DB+、DB-與DB′中的支持?jǐn)?shù)。

易知所有DB′中的項(xiàng)集能夠被劃分為如表1所示的四組。組4中的項(xiàng)集可以忽略；組1、3的項(xiàng)集因在原始數(shù)據(jù)庫(kù)中頻繁記錄，故支持?jǐn)?shù)容易獲得；而組2的項(xiàng)集在DB中未知，需要重新掃描數(shù)據(jù)庫(kù)。因此，如何有效發(fā)現(xiàn)組2中的總頻繁項(xiàng)集對(duì)更新維護(hù)關(guān)聯(lián)規(guī)則非常重要。



2.2 改進(jìn)的IDARM算法

增長(zhǎng)挖掘的首要目標(biāo)是運(yùn)用在早期挖掘中生成的中間數(shù)據(jù)來(lái)避免或者最小化原始數(shù)據(jù)庫(kù)的掃描。本文提出了一種新型的動(dòng)態(tài)增長(zhǎng)關(guān)聯(lián)規(guī)則挖掘算法——IDARM。其創(chuàng)新點(diǎn)主要體現(xiàn)在以下幾個(gè)方面。

a）在FUP中每次迭代只處理一個(gè)長(zhǎng)度的候選項(xiàng)集，導(dǎo)致原始數(shù)據(jù)庫(kù)迭代次數(shù)等同于候選項(xiàng)集的最大長(zhǎng)度。事實(shí)上，當(dāng)掃描DB+后就發(fā)現(xiàn)了所有潛在的候選項(xiàng)集，為減少掃描DB的開銷，只對(duì)其進(jìn)行一次掃描來(lái)計(jì)數(shù)這些1~k項(xiàng)候選項(xiàng)集。因?yàn)闆]有層次迭代剪枝使得一些冗余的候選集也將被計(jì)數(shù)，帶來(lái)了額外開銷，即以計(jì)數(shù)冗余為代價(jià)達(dá)到最小化DB掃描次數(shù)的目的。而DB+往往比DB小很多，故因減少DB迭代次數(shù)而節(jié)約的時(shí)間大于對(duì)DB+中多余候選項(xiàng)計(jì)數(shù)而花費(fèi)的時(shí)間，有助于算法效率的整體提高。

IDARM算法執(zhí)行如下:

a）用Apriori算法掃描DB+找出其中所有頻繁項(xiàng)集并記錄它們的支持?jǐn)?shù)X+count。

b）對(duì)每個(gè)屬于L∩L+的項(xiàng)集X而言，顯然Xcount+X+count≥s*(d+d+)， 將其添加到集合L′中并設(shè)標(biāo)志符為S1(代表屬于組1)。

c)再次掃描DB+更新所有屬于集合L-L+-L′的項(xiàng)集計(jì)數(shù)，即那些DB中頻繁而DB+中不頻繁的項(xiàng)集是否在DB′中頻繁。對(duì)任意滿足最小支持度門限的項(xiàng)集X，將其添加到集合L′中并設(shè)標(biāo)志符為S3(代表屬于組3)。

d)掃描DB更新所有屬于集合L+-L-L′的項(xiàng)集計(jì)數(shù)，即那些DB+中頻繁而DB中不頻繁的項(xiàng)集是否在DB′中頻繁。計(jì)數(shù)完成后，滿足最小支持度門限s的新頻繁項(xiàng)集將加入到集合L′中并設(shè)標(biāo)志符為“S2”(代表屬于組2)。

某些情況下，由于數(shù)據(jù)的偏斜性，大量冗余候選項(xiàng)在DB中掃描的開銷相當(dāng)可觀。為此，又提出另一種解決方案，即當(dāng)且僅當(dāng)k項(xiàng)集的所有k-1項(xiàng)子集在DB∪DB+中頻繁時(shí)才在DB中計(jì)數(shù)。這表明在DB中被計(jì)數(shù)的候選項(xiàng)集已精煉至最小，且數(shù)目不是很多。當(dāng)然這樣對(duì)DB的掃描也不止一次，需要在其中進(jìn)行層次迭代。將對(duì)DB迭代次數(shù)與DB+中生成的冗余候選項(xiàng)集進(jìn)行權(quán)衡，選擇更為適宜的算法。

改動(dòng)后的算法前三步相同，第四步執(zhí)行如下：

 檢驗(yàn)所有屬于集合L+-L-L′的項(xiàng)集計(jì)數(shù)，即那些DB+中頻繁而DB中不頻繁的項(xiàng)集是否在DB′中頻繁。計(jì)數(shù)前先確認(rèn)集合中每個(gè)k項(xiàng)集的所有k-1項(xiàng)子集都在L′中，再進(jìn)行計(jì)數(shù)。任何k項(xiàng)集最多包含k個(gè)k-1項(xiàng)子集，開始時(shí)所有1項(xiàng)集加入到候選集中。這些候選項(xiàng)集的計(jì)數(shù)值由它們?cè)贒B+中的支持度初始化。當(dāng)每輪迭代結(jié)束后，新的頻繁項(xiàng)集及其更新支持度都加入到L′中并設(shè)標(biāo)志符為“S2”(代表屬于組2)。新的候選項(xiàng)是在L′(S2)中用函數(shù)apriori_gen生成的，相當(dāng)于把L+進(jìn)行了剪枝。輸入為所有頻繁k-1項(xiàng)集，輸出為所有頻繁k項(xiàng)集的超集。如此迭代，直到?jīng)]有新的候選項(xiàng)計(jì)數(shù)為止。

b)IDARM算法不僅存儲(chǔ)了頻繁項(xiàng)集，還存儲(chǔ)了潛在頻繁項(xiàng)集，以減少處理更新數(shù)據(jù)庫(kù)的開銷。在某些特殊情況下，可以不用掃描原始數(shù)據(jù)庫(kù)就得到更新后的頻繁項(xiàng)集。本文定義了一個(gè)邊界參數(shù)γ(0 <γ但冗余候選項(xiàng)集的數(shù)目也越多。

先討論增長(zhǎng)情況。當(dāng)掃描DB+時(shí)，原數(shù)據(jù)庫(kù)集合L∪P中的項(xiàng)集支持?jǐn)?shù)被累加，最后判斷是否滿足新的支持度門限s*(d+d+)。而當(dāng)DB+中項(xiàng)集XL∪P時(shí)，定理1指出了它可能頻繁的必要條件。

定理1 若XL∪P且X在DB′中頻繁，則X+count＞s*d+。

證明 用反證法。

if X+count≤s*d+X′count=Xcount+X+count＜d*(s-γ)+X+count≤d*(s-γ)+s*d+＜(d+d+)*s

X在DB′中不頻繁，與題設(shè)矛盾，故X+count必須滿足X+count>s*d+。所有滿足上述定理的項(xiàng)集X都存儲(chǔ)在集合L+中，并設(shè)其中最大支持?jǐn)?shù)為Smax。

定理2 若Smax

證明 由于XL∪PXcount

X′count=Xcount+X+count＜d*(s-γ)+ Smax<

d*(s-γ)+d+*s +d*γ=(d++d)*s= d′*s

這說(shuō)明所有L+中的項(xiàng)集X 都無(wú)法在更新數(shù)據(jù)庫(kù)DB′中頻繁，故無(wú)須再處理原始數(shù)據(jù)庫(kù)DB。

如何設(shè)置參數(shù)γ是一個(gè)非常重要的問題。因?yàn)榇蠖鄶?shù)情況下，d+比d小很多，如果它們的支持度門限一樣，將導(dǎo)致DB+中的頻繁項(xiàng)集十分龐大。例如當(dāng)1/d+與s有著相同量級(jí)時(shí)， DB+幾乎所有項(xiàng)集組合都可能頻繁。定理3給出了此時(shí)設(shè)置r的方法。其余情況下，可設(shè)置γ比s低一個(gè)數(shù)量級(jí)。

定理3 設(shè)γ=(1-s)*d+/d，則不需要處理增長(zhǎng)數(shù)據(jù)庫(kù)DB+。

證明 所有在DB∪DB+中頻繁的項(xiàng)集X必須滿足

X′count=Xcount+X+count≥s*(d+d+)=s*(1+d+/d)*d=

(s+(s-1)*d+/d)*d+d+=(s-γ)*d+d+X′count≤Xcount+d+≥Xcount≥(s-γ)*d

這說(shuō)明所有DB′中頻繁的項(xiàng)集都包含在DB的L∪P集合中， 故只需掃描DB+一次來(lái)更新每個(gè)X∈L∪P 的計(jì)數(shù)X′count，判斷是否頻繁，十分方便。

c）盡管傳統(tǒng)FUP算法只考慮了數(shù)據(jù)庫(kù)增長(zhǎng)的情況， 管理員仍可能移除數(shù)據(jù)庫(kù)中不再具有時(shí)效性的數(shù)據(jù)，這便是要討論的刪減數(shù)據(jù)庫(kù)DB-。當(dāng)集合L∪P的項(xiàng)集出現(xiàn)在DB-中時(shí)，其支持?jǐn)?shù)將會(huì)相應(yīng)減少，而L與P將由新的支持?jǐn)?shù)門限s*(d-d-)與(s-γ)* (d-d-)更新。可以用逆向思維的方法考慮刪減問題：即將原始數(shù)據(jù)庫(kù)視為增長(zhǎng)情況下的總數(shù)據(jù)庫(kù)，將總數(shù)據(jù)庫(kù)視為增長(zhǎng)情況下的原始數(shù)據(jù)庫(kù)，而將刪減數(shù)據(jù)庫(kù)視為增長(zhǎng)情況下的增長(zhǎng)數(shù)據(jù)庫(kù)。易知，經(jīng)過刪減后的新頻繁項(xiàng)集有三種可能：

a）原數(shù)據(jù)庫(kù)與刪減數(shù)據(jù)庫(kù)中不頻繁，但總數(shù)據(jù)庫(kù)中頻繁。

b)原數(shù)據(jù)庫(kù)與刪減數(shù)據(jù)庫(kù)中均頻繁，總數(shù)據(jù)庫(kù)中也頻繁。

c)原數(shù)據(jù)庫(kù)中頻繁，刪減數(shù)據(jù)庫(kù)中不頻繁，而總數(shù)據(jù)庫(kù)中頻繁。

對(duì)情況b)c)，因?yàn)樵瓟?shù)據(jù)庫(kù)的頻繁項(xiàng)集已知，只需掃描刪減數(shù)據(jù)庫(kù)更新它們的計(jì)數(shù)再判定是否頻繁；而對(duì)情況a）而言，就需要進(jìn)一步討論。

定理4與5分別指出了一定情況下，對(duì)刪減問題的處理方法。

定理4 設(shè)項(xiàng)集X不屬于DB的L∪P集合且γ>s*d-/d，則不需要處理更新數(shù)據(jù)庫(kù)DB-DB-。

證明 XL∪P，X′count=Xcount-X-count

即X無(wú)法在刪減后的數(shù)據(jù)庫(kù)DB′中頻繁，故不用考慮。

定理5 設(shè)γ= s*d-/d，則不需要處理刪減數(shù)據(jù)庫(kù)DB-。

證明 所有在DB-DB-中頻繁的項(xiàng)集X必須滿足

X′count=Xcount-X-count≥s*(d-d-)=s*(1-d-/d)*d=(s-γ)*d

X′count≤XcountXcount≥(s-γ)*d

這說(shuō)明所有DB′中頻繁的項(xiàng)集都包含在DB的L∪P集合中， 故只需掃描DB-一次來(lái)更新每個(gè)X∈L∪P 的計(jì)數(shù)X′count來(lái)判斷是否頻繁即可，這其中就包含了情況a)所有可能頻繁項(xiàng)集。

類似于前面的討論，當(dāng)插入與刪減同時(shí)存在時(shí)，也存在一些特殊的情況，如d+

d）本文應(yīng)用了剪枝技術(shù)進(jìn)一步減少原始數(shù)據(jù)庫(kù)大小。

第一次迭代，把增長(zhǎng)數(shù)據(jù)庫(kù)DB+中沒有滿足支持度的所有候選項(xiàng)存儲(chǔ)在集合D中。稍后掃描原始數(shù)據(jù)庫(kù)時(shí)，將交易中所有屬于集合D中的項(xiàng)刪除，因?yàn)樗鼈儾豢赡茉贅?gòu)成更長(zhǎng)的頻繁項(xiàng)。

在第二種方法的第K次迭代，首先由新的k-1項(xiàng)頻繁集產(chǎn)生k項(xiàng)候選集，再刪除k候選集中k-1項(xiàng)子集不頻繁的候選項(xiàng)。其次掃描DB前，對(duì)其中每個(gè)交易的每個(gè)項(xiàng)I，計(jì)算包含I的C(候選集)和L′k的項(xiàng)目數(shù)，此數(shù)目即包含I的頻繁K項(xiàng)集的上限數(shù)。如果小于K，則項(xiàng)I無(wú)法再構(gòu)成K+1頻繁項(xiàng)集，故可調(diào)用函數(shù)prune(DB)將項(xiàng)I從相應(yīng)交易中刪除。

為便于理解，圖1給出了整個(gè)算法的流程。



3 仿真性能分析

3.1 合成告警數(shù)據(jù)

本文告警數(shù)據(jù)由圖2所示的網(wǎng)絡(luò)產(chǎn)生。其中灰色節(jié)點(diǎn)表示中心節(jié)點(diǎn)，其余為邊緣節(jié)點(diǎn)。此網(wǎng)狀通信網(wǎng)產(chǎn)生的告警信息共設(shè)五個(gè)告警屬性，即告警設(shè)備、告警端口、告警級(jí)別、告警類型和告警時(shí)間。所有告警按以下原則生成：

a）任意節(jié)點(diǎn)底層告警可以引發(fā)該節(jié)點(diǎn)上層告警；

b）邊緣節(jié)點(diǎn)產(chǎn)生的告警可以以一定概率向相應(yīng)的中心節(jié)點(diǎn)傳播，中心節(jié)點(diǎn)響應(yīng)的告警級(jí)別比原始告警低；

c）中心節(jié)點(diǎn)產(chǎn)生的告警會(huì)隨機(jī)向與之相連的任意一個(gè)邊緣節(jié)點(diǎn)傳播；

d）中心節(jié)點(diǎn)產(chǎn)生的告警會(huì)向與之相連的所有中心節(jié)點(diǎn)傳播，其余中心節(jié)點(diǎn)響應(yīng)的告警級(jí)別比原始告警低。



插入增長(zhǎng)數(shù)據(jù)庫(kù)DB+的方法是在原始數(shù)據(jù)庫(kù)末尾放入d+個(gè)交易；而刪減數(shù)據(jù)庫(kù)的方法是移除原始數(shù)據(jù)庫(kù)中頭d-個(gè)交易。

3.2 實(shí)驗(yàn)結(jié)果評(píng)價(jià)

在Pentium 4 1.5 GHz CPU、512 MB內(nèi)存和Windows XP環(huán)境下對(duì)IDARM算法進(jìn)行實(shí)驗(yàn)。由上文網(wǎng)絡(luò)合成告警測(cè)試數(shù)據(jù)，算法用Java實(shí)現(xiàn)。

本文對(duì)IDARM與FUP在不同支持度和不同增長(zhǎng)數(shù)據(jù)庫(kù)大小情況下進(jìn)行性能分析對(duì)比。圖3描述了當(dāng)支持度 s從0.01變化到0.1時(shí)，IDARM與FUP相對(duì)Apriori執(zhí)行的時(shí)間比率。DB+與DB分別為1 000和10 000。可以看出，本文方法在不同支持度門限下比FUP有更好的穩(wěn)定性與更高的效率。圖4描述了原始數(shù)據(jù)庫(kù)與支持度分別為10 000和0.02，增長(zhǎng)數(shù)據(jù)庫(kù)從1 000變化到30 000的情況。當(dāng)d+=1 000時(shí)，IDARM與FUP比Apriori分別節(jié)省了約80%和75%的執(zhí)行時(shí)間，而隨著數(shù)據(jù)庫(kù)的逐漸增大，這種差距將越來(lái)越小。盡管如此，僅當(dāng)d+達(dá)到30 k即為原始數(shù)據(jù)庫(kù)的三倍大小時(shí)，IDARM、FUP與Apriori的執(zhí)行效率才相對(duì)一致。這說(shuō)明即使增長(zhǎng)數(shù)據(jù)庫(kù)比原始數(shù)據(jù)庫(kù)大時(shí)，IDARM仍可保持較好的執(zhí)行效率與性能增益。



為進(jìn)一步比較IDARM與FUP算法，第二個(gè)實(shí)驗(yàn)中將不同環(huán)境下IDARM與FUP的執(zhí)行時(shí)間作了對(duì)比。圖5~7分別描述了插入、刪減以及插入與刪減同時(shí)存在情況下，IDARM與FUP的相對(duì)執(zhí)行時(shí)間。每種情況各進(jìn)行了五次數(shù)據(jù)庫(kù)更新，每次插入與刪減數(shù)據(jù)庫(kù)的大小為原數(shù)據(jù)庫(kù)的1%，最小支持度s=1%，討論了γ=0.1%和0.5%的情形。由圖可知，因?yàn)镮DARM中原始數(shù)據(jù)庫(kù)只掃描0或1次， 加之采用了參數(shù)γ與剪枝技術(shù)，它比FUP能節(jié)省約47%~98%的執(zhí)行時(shí)間，大大提高了效率。



4 結(jié)束語(yǔ)

現(xiàn)實(shí)世界中數(shù)據(jù)庫(kù)是不斷更新與變化的，導(dǎo)致原有規(guī)則需要重新驗(yàn)證而新規(guī)則也將加入其中。動(dòng)態(tài)挖掘的首要目標(biāo)就是運(yùn)用早期挖掘的中間數(shù)據(jù)來(lái)避免或最小化原始數(shù)據(jù)庫(kù)的掃描。為有效發(fā)現(xiàn)和維護(hù)更新數(shù)據(jù)庫(kù)中的頻繁項(xiàng)集，提出了IDARM算法。實(shí)驗(yàn)證明IDARM比傳統(tǒng)Apriori與FUP算法性能優(yōu)越，尤其當(dāng)原始數(shù)據(jù)庫(kù)大于增長(zhǎng)數(shù)據(jù)庫(kù)和刪減數(shù)據(jù)庫(kù)時(shí)。用數(shù)據(jù)挖掘進(jìn)行通信網(wǎng)差錯(cuò)管理，能正確診斷與定位告警，減少故障恢復(fù)時(shí)間，意義重大。此外，分布式環(huán)境關(guān)聯(lián)規(guī)則與加權(quán)項(xiàng)集關(guān)聯(lián)規(guī)則的挖掘也是將來(lái)值得探討的課題。

參考文獻(xiàn)：

[1]AGRNWNL R， SRIKANR R， Fast algorithms for mining association rules[C]//Proc of International Conference on Very Large Database. Santiago， Chile:[s.n.]， 1994:487-499.

[2]AGRAWAL R， IMIELINSKI T， SWAMI A. Mining association rules between sets of items in large databases[C]//Proc of ACM-SIGMOD Int Conf on Management of Data. 1993:207-216.

[3]KLEMETTINEN M， MANNILA H， RONKAINEN P， et al. Finding interesting rules from large sets of discovered association rules[C]//Proc of the 3rd Int Conf on Information and Knowledge Management. Gaithersburg， Maryland:[s.n.]， 1994:401-408.

[4]CHEUNG D W， HAN J， NG V T， et al. Maintenance of discovered association rules in large databases: an incremental updating technique[C]//Proc of the 12th International Conference on Data Engineering. Washinton DC:IEEE Computer Society， 1996:106-114.

[5]CHEUNG D W， LEE S D， KAO B. A general incremental technique for mining discovered association rules[C]//Proc of International Conference on Database System for Advanced Applications. 1997:185-194.

[6]CHEUNG D W， FU A W C， HAN J. Knowledge discovery in databases: a rule-based attribute-oriented approach[C]//Proc of Intl Symp on Methodologies for Intelligent Systems. Charlotte， North Carolina:[s.n.]， 1994:164-173.

[7]AYAN N F， TANSEL A U， ARKUN E. An efficient algorithm to update large itemsets with early pruning[C]//Proc of the 5th ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining. San Diego:[s.n.]， 1999:287 -291.

[8]NG K K， LAM W. Updating of association rules dynamically[C]//Proc of Intl Symposium on Database Applications in Non-Traditional Environments. Kyoto， Japan:[s.n.]， 1999:84-91.

[9]LEE K L. Efficient graph-based algorithms for discovering and maintaining knowledge in large databases[C]//Proc of the 3rd pacif-Asia Conference on Methodologies for knowledge Discovery and Data Mi-ning. London: Springer-Verlag， 1999:409-419.

[10]YEN S J， CHEN A L P. An efficient approach to discovering know-ledge from large databases[C]//Proc of IEEE/ACM International Conference on Parallel and Distributed Information System. 1996:8-18.

[11]HAND D， MANILLA H， SMYTH P. Principles of data mining[M]. Cambridge， MA:MIT Press， 2001.

[12]KIMBALL R， ROSS M. The data warehouse toolkit， the complete guide to dimensional modeling[M]. 2nd ed.New York: Wiley， 2002.