關聯規則算法的計算效率優化研究

劉建花

（晉中師范高等專科學校，晉中 030600）

1 引言

關聯規則在數據挖掘中是非常重要的一個技術，主要用于在數據庫中尋找各個不同方面間的關聯度，即在頻率盡可能低的限制下從數據庫中尋找頻繁項集。

2 Apriori 算法

Apriori 算法在關聯規則算法中占了很大比重。Apriori 算法通常情況下分兩步進行：第一步，滿足使用者要求的頻繁項目集，在全部的數據庫中挑選出大于使用者約定的最小支持度臨界值的頻繁項目集。第二步，在使用頻繁項目集的過程中總結出滿足預期的關聯規則。置信度一定要大于等于使用者約定的最小置信度總臨界值，這是找出關聯規則的最根本條件。

Apriori 算法：

輸入：總數據庫；最小支持度臨界值

輸出：數據庫中的頻繁項目集

方法：

①從數據庫中產生頻繁項目集；②命令條件：For（k=2；1k-1 ≠null，k + +）；③得出k-1 個頻繁集新產生的k-1 個候選集；④確認總數據庫中的每一個候選集的支持度；⑤得出特定事務的候選集；⑥確認特定事務的候選集中每個候選集的支持度；⑦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 函數包含兩部分內容：連接和剪枝。連接部分是步驟（1）-（4），把有可能產生候選集的部分對Lk-1 和Lk-1進行連接。剪枝部分是步驟（5）-（7），利用Apriori 算法的性質對含有不是頻繁子集的候選集進行刪除。has_inf requent_subset函數的作用檢測不是頻繁子集的候選集。

此算法中不足的地方：會產生數量龐大的候選集會造成占用內存多的結果；通過反復對總數據進行掃描的方式來對比檢測數據量大的候選集會耗廢大量時間[3]。

3 優化算法

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

3.1 構造Fp-tree 算法

（1）僅對總數據庫進行一次掃描，得出頻繁項目集和與之對應的支持度。根據得出的支持度按從大到小的順序進行排序，列出頻繁項目集的數據表。

（2）建立Fp-tree 的根節點NULL 將總數據庫中的每件事物進行如下操作：

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

運用了Fp-tree 的MFLA 算法，將長頻繁模式轉換為短模式，緊跟著連接后綴。后綴改為不頻繁項能夠為搜索提供高效的選擇，進而降低耗費。因為是在作用了 Fp-tree 的基礎上進行的新算法構造，所以無論在長頻模式還是在短頻模式，新算法都有效。

3.2 選取數據庫中最大頻繁項集算法

輸入：數據庫中的頻繁模式樹Fp-tree；頻繁項目頭表；最小支持度臨界值；數據庫中的頻繁項目數據

輸出：數據庫中的最大頻繁項目集

（1） MFCID=NULL

（2）確定MFCID 為數據庫中的最大頻繁項目集

（3）當條件為MFCID ≠NULL 時

（4）進行條件循環 or（i=k；i＞0；i ——）

（5） 最后一個項目為MFIi

（6）MFCID= MFCID - MFCI

（7）進行調用，計算項目集在總數據庫中的支持度

（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）計算 MFCII 的項目集在總數據庫里的支持度，基于前面步驟已經將其項目集中的羨慕按順序排列，使接下來確定路徑數時更加高效，此時僅需將父指針向根節點搜索即可。

（14） 搜索項目頭表的項目名稱域，設 head[ql ┛.item=I

（15）根據head[ql ┛.item=I 尋找tree 中i 名稱的節點 nd1，nd2，...ndh

（16）根據nd1，nd2，...ndh 和前綴節點的指針區域找出有的全部路徑p1，p2...ph

（17）for all m ∈ MFCII

（18）如果路徑Pj 內含有 m，則m 的支持度增長

4 結束語

在實際中，各領域的數據庫都相當龐大，需要找出一種更高效的算法去解決現實問題。MFIA 算法是對Apriori 算法的優化，提高了效率。