關(guān)聯(lián)規(guī)則算法的計(jì)算效率優(yōu)化研究

劉建花

（晉中師范高等專科學(xué)校，晉中 030600）

1 引言

關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘中是非常重要的一個(gè)技術(shù)，主要用于在數(shù)據(jù)庫(kù)中尋找各個(gè)不同方面間的關(guān)聯(lián)度，即在頻率盡可能低的限制下從數(shù)據(jù)庫(kù)中尋找頻繁項(xiàng)集。

2 Apriori 算法

Apriori 算法在關(guān)聯(lián)規(guī)則算法中占了很大比重。Apriori 算法通常情況下分兩步進(jìn)行：第一步，滿足使用者要求的頻繁項(xiàng)目集，在全部的數(shù)據(jù)庫(kù)中挑選出大于使用者約定的最小支持度臨界值的頻繁項(xiàng)目集。第二步，在使用頻繁項(xiàng)目集的過(guò)程中總結(jié)出滿足預(yù)期的關(guān)聯(lián)規(guī)則。置信度一定要大于等于使用者約定的最小置信度總臨界值，這是找出關(guān)聯(lián)規(guī)則的最根本條件。

Apriori 算法：

輸入：總數(shù)據(jù)庫(kù)；最小支持度臨界值

輸出：數(shù)據(jù)庫(kù)中的頻繁項(xiàng)目集

方法：

①?gòu)臄?shù)據(jù)庫(kù)中產(chǎn)生頻繁項(xiàng)目集；②命令條件：For（k=2；1k-1 ≠null，k + +）；③得出k-1 個(gè)頻繁集新產(chǎn)生的k-1 個(gè)候選集；④確認(rèn)總數(shù)據(jù)庫(kù)中的每一個(gè)候選集的支持度；⑤得出特定事務(wù)的候選集；⑥確認(rèn)特定事務(wù)的候選集中每個(gè)候選集的支持度；⑦c.count+ +；⑧}；⑨返回L=∪kLk

Procedure apriori_gen（LK-1：frequent（k-1）-itemsets；

Min sup：min nimum suo port threshold）

（1） For each itemset I1∈Lk-1

（2） For each itemset I2∈Lk-1

（3） If（I1[1]=I2[1]∩I1[2]=I2[2]∩... ∩I1[k-2]=I2[K-2]）∩I1[k-1]=I2[k-1]）then

（4）{c=I1∞I2；

（5）If has_inf requent_subset（c，Lk-1）then

（6）Delete c

（7）Else add c to CK

（8）{

（9）Return Ck

Pr oxedure has_inf requent_subset（c：candiate k - itemet；frequent（k-1）-itemset）

（1）for each （k-1）-subset s of c

（2）If not （s ∈Lk-1）then

（3）Return TRUE

（4）Return FALSE

Apriori_gen 函數(shù)包含兩部分內(nèi)容：連接和剪枝。連接部分是步驟（1）-（4），把有可能產(chǎn)生候選集的部分對(duì)Lk-1 和Lk-1進(jìn)行連接。剪枝部分是步驟（5）-（7），利用Apriori 算法的性質(zhì)對(duì)含有不是頻繁子集的候選集進(jìn)行刪除。has_inf requent_subset函數(shù)的作用檢測(cè)不是頻繁子集的候選集。

此算法中不足的地方：會(huì)產(chǎn)生數(shù)量龐大的候選集會(huì)造成占用內(nèi)存多的結(jié)果；通過(guò)反復(fù)對(duì)總數(shù)據(jù)進(jìn)行掃描的方式來(lái)對(duì)比檢測(cè)數(shù)據(jù)量大的候選集會(huì)耗廢大量時(shí)間[3]。

3 優(yōu)化算法

為了解決Apriori 算法存在的對(duì)支持度計(jì)算的耗時(shí)問(wèn)題，得出的方案是減少候選集的數(shù)量，把尋找頻繁項(xiàng)目集改為尋找最大頻繁項(xiàng)目集。提出了一種新的算法MFLA：在頻繁模式樹Fp-tree的基礎(chǔ)上尋找最大頻繁項(xiàng)目集。新算法可以不必重復(fù)匹配數(shù)據(jù)庫(kù)，僅需一次就足夠，因此使運(yùn)行效率得到了提升。

3.1 構(gòu)造Fp-tree 算法

（1）僅對(duì)總數(shù)據(jù)庫(kù)進(jìn)行一次掃描，得出頻繁項(xiàng)目集和與之對(duì)應(yīng)的支持度。根據(jù)得出的支持度按從大到小的順序進(jìn)行排序，列出頻繁項(xiàng)目集的數(shù)據(jù)表。

（2）建立Fp-tree 的根節(jié)點(diǎn)NULL 將總數(shù)據(jù)庫(kù)中的每件事物進(jìn)行如下操作：

按已經(jīng)列出的頻繁項(xiàng)目集進(jìn)行排序，將數(shù)據(jù)庫(kù)中的每個(gè)數(shù)據(jù)都進(jìn)行排序，將排列后的結(jié)果記作為[p │P]，p 為項(xiàng)目的第一個(gè)，P 為其余剩下的項(xiàng)目的列表；然后對(duì)inset_tree（p │P ]，T）進(jìn)行調(diào)用；當(dāng)出現(xiàn)P 的列表中不是空的的情況，遞歸調(diào)用inset_tree（P，N） 緊接著完成接下來(lái)的操作。假如T 存在子女N 能夠使N.node_name=name，那么 的計(jì)數(shù)將增到：新建立一個(gè)節(jié)點(diǎn)N，同時(shí)把名稱 （node_name） 和計(jì)數(shù)（node_count） 設(shè)為P、L 使父指針節(jié)點(diǎn)（node_count） 與父節(jié)點(diǎn) 相連，最后經(jīng)過(guò)節(jié)點(diǎn)鏈（node_link） 使之與名稱相同的節(jié)點(diǎn)進(jìn)行連接。

運(yùn)用了Fp-tree 的MFLA 算法，將長(zhǎng)頻繁模式轉(zhuǎn)換為短模式，緊跟著連接后綴。后綴改為不頻繁項(xiàng)能夠?yàn)樗阉魈峁└咝У倪x擇，進(jìn)而降低耗費(fèi)。因?yàn)槭窃谧饔昧?Fp-tree 的基礎(chǔ)上進(jìn)行的新算法構(gòu)造，所以無(wú)論在長(zhǎng)頻模式還是在短頻模式，新算法都有效。

3.2 選取數(shù)據(jù)庫(kù)中最大頻繁項(xiàng)集算法

輸入：數(shù)據(jù)庫(kù)中的頻繁模式樹Fp-tree；頻繁項(xiàng)目頭表；最小支持度臨界值；數(shù)據(jù)庫(kù)中的頻繁項(xiàng)目數(shù)據(jù)

輸出：數(shù)據(jù)庫(kù)中的最大頻繁項(xiàng)目集

（1） MFCID=NULL

（2）確定MFCID 為數(shù)據(jù)庫(kù)中的最大頻繁項(xiàng)目集

（3）當(dāng)條件為MFCID ≠NULL 時(shí)

（4）進(jìn)行條件循環(huán) or（i=k；i＞0；i ——）

（5） 最后一個(gè)項(xiàng)目為MFIi

（6）MFCID= MFCID - MFCI

（7）進(jìn)行調(diào)用，計(jì)算項(xiàng)目集在總數(shù)據(jù)庫(kù)中的支持度

（8）for all m ∈ MFCII

（9）If（m.supd≥min sup）MFCID ∪m

（10）else

（11）for all item e ∈m

（12）m-{e} MFCID MFCID= MFCID ∪{e}

（13）計(jì)算 MFCII 的項(xiàng)目集在總數(shù)據(jù)庫(kù)里的支持度，基于前面步驟已經(jīng)將其項(xiàng)目集中的羨慕按順序排列，使接下來(lái)確定路徑數(shù)時(shí)更加高效，此時(shí)僅需將父指針向根節(jié)點(diǎn)搜索即可。

（14） 搜索項(xiàng)目頭表的項(xiàng)目名稱域，設(shè) head[ql ┛.item=I

（15）根據(jù)head[ql ┛.item=I 尋找tree 中i 名稱的節(jié)點(diǎn) nd1，nd2，...ndh

（16）根據(jù)nd1，nd2，...ndh 和前綴節(jié)點(diǎn)的指針區(qū)域找出有的全部路徑p1，p2...ph

（17）for all m ∈ MFCII

（18）如果路徑Pj 內(nèi)含有 m，則m 的支持度增長(zhǎng)

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

在實(shí)際中，各領(lǐng)域的數(shù)據(jù)庫(kù)都相當(dāng)龐大，需要找出一種更高效的算法去解決現(xiàn)實(shí)問(wèn)題。MFIA 算法是對(duì)Apriori 算法的優(yōu)化，提高了效率。