多種關聯(lián)規(guī)則挖掘算法的研究與分析

程險峰

（長春市公安局交通警察支隊，長春 130000）

數(shù)據(jù)關聯(lián)是數(shù)據(jù)庫中存在的一類重要的可被發(fā)現(xiàn)的知識。若兩個或多個變量的取值之間存在某種規(guī)律性，則稱之為關聯(lián)，關聯(lián)可以分為簡單關聯(lián)、時序關聯(lián)、因果關聯(lián)。關聯(lián)分析的目的是從大型數(shù)據(jù)中找出隱藏的屬性之間存在的關聯(lián)和規(guī)律。有時并不知道數(shù)據(jù)庫中數(shù)據(jù)的關聯(lián)函數(shù)，即使知道也是不確定的，因此關聯(lián)分析生成的規(guī)則帶有可信度。

自Agrawal等人首次提出了挖掘顧客交易數(shù)據(jù)庫中項集間的關聯(lián)規(guī)則問題以來，研究人員對原有的算法進行了大量研究和進一步優(yōu)化，例如，提出了隨機采樣、并行等思想，使得挖掘規(guī)則算法的效率和伸縮性都有了提高，并且推廣了關聯(lián)規(guī)則的應用范圍。

1 傳統(tǒng)的關聯(lián)規(guī)則挖掘算法

1.1 Apriori算法

Apriori算法最初是由 Agrawal等人提出的，Apriori算法是一種經(jīng)典的規(guī)則挖掘算法，通過挖掘布爾關聯(lián)規(guī)則頻繁項集挖掘數(shù)據(jù)。其基本原理如下：

（1）通過事物數(shù)據(jù)庫得到大一項集L1。若L1為非空的，則由L1產(chǎn)生長度為2的候選項集合C2；

（2）對事務數(shù)據(jù)庫中的每一個事務 t，求出 t在C2中的全部子集Ct，對于Ct中的每一個長度為2的候選項集c進行加1操作。

（3）完成一次事務數(shù)據(jù)庫的掃描，篩選出C2中滿足最小支持度的項集組成了長度為2的頻繁項集合。

（4）重復以上步驟，處理新得到的頻繁項集合，直到不再產(chǎn)生頻繁項集合為止。Apriori算法的缺點是掃描事務數(shù)據(jù)庫次數(shù)過多、在頻繁項長度變大的情況下，運算時間顯著增加、不能直接用于關系數(shù)據(jù)庫的關聯(lián)規(guī)則挖掘、不適于海量數(shù)據(jù)環(huán)境下的關聯(lián)規(guī)則挖掘。

1.2 基于劃分的算法

A.Savasere等人提出的Partition算法和S.Brin等人提出的DIC算法均屬于基于劃分的算法。這些算法為了節(jié)省訪問外部存儲器I/O的開銷，將整個數(shù)據(jù)集劃分為數(shù)據(jù)塊，然后將這些數(shù)據(jù)塊存放在內(nèi)存中進行處理。與 Apriori算法相比，數(shù)據(jù)集劃分算法高度并行并且候選項目集數(shù)量比較大，是各種并行關聯(lián)規(guī)則和分布式關聯(lián)規(guī)則挖掘算法的基礎。該算法先把每個分塊數(shù)據(jù)分別分配給某一個處理器生成頻集，產(chǎn)生頻集的每個循環(huán)結(jié)束以后，處理器之間通過通信產(chǎn)生全局的候選k-項集，算法的執(zhí)行時間主要取決于該通信過程，這也是算法的主要瓶頸；另一個瓶頸即每個獨立的處理器生成頻集所消耗的時間。

1.3 FP-樹頻集算法

頻繁項集挖掘算法 FP-樹算法的基本原理是通過兩次掃描數(shù)據(jù)庫，將數(shù)據(jù)信息存到一種高度壓縮的數(shù)據(jù)結(jié)構(gòu) FP-樹里，避免生成候選項集，縮小了搜索空間，減少了數(shù)據(jù)模式匹配的開銷，進而有效地避免了多次掃描數(shù)據(jù)庫和生成大量候選項集所造成的時間、空間上的浪費。但由于 FP-樹算法沒有充分考慮層次數(shù)據(jù)的自身特點，在查找頻繁項集的過程中，計算了大量的無用項集。使得該算法不能根據(jù)層次數(shù)據(jù)的特點去除關聯(lián)規(guī)則的冗余，從而產(chǎn)生大量冗余關聯(lián)規(guī)則。

2 幾種關聯(lián)規(guī)則挖掘算法的改進

基于 FP-樹頻集算法的改進算法，針對層次結(jié)構(gòu)數(shù)據(jù)的內(nèi)在特征，研究高效的去冗余多層關聯(lián)規(guī)則挖掘算法。通過采取聚類的方法，對已有的評價關聯(lián)規(guī)則的支持度和可信度（兩個常用的客觀性指標），增加一個相關的業(yè)務參數(shù)，達到對樹的進一步劃分，不斷減小頻繁項集挖掘時需要掃描的數(shù)據(jù)庫，進而提高挖掘效率，以便挖掘出收益較高、值得關注的業(yè)務。

基于遺傳算法的思想改進 Apriori算法，只需要對數(shù)據(jù)庫進行一次掃描，便可以給定一個映射，實現(xiàn)據(jù)庫到矩陣的映射，以下均可通過在矩陣上的運算來完成所有對數(shù)據(jù)庫的掃描。將某個生物種群對環(huán)境的適應性問題轉(zhuǎn)化為求解關聯(lián)規(guī)則最長頻繁項集的問題，生物種群的進化過程即為優(yōu)化問題的求解過程，生物種群的個體即為優(yōu)化變量?；谶z傳算法改進Apriori算法的基本思想：

（1）進行二進制或十進制編碼；

（2）根據(jù)實際要求，選取遺傳算法的適應度函數(shù)，并由適應度函數(shù)求出頻繁 1-項集，進行交叉、變異運算進化該組項集；

（3）進行選擇運算產(chǎn)生下一代頻繁項集，反復迭代運算若干代，直至最終滿足遺傳算法的終止條件，此時得到一組最長頻繁項集。

3 改進算法分析

（一）基于 FP-樹頻集算法的改進算法以大型的商業(yè)交易為例，每次商業(yè)交易都有層次結(jié)構(gòu)樹的特征，對整個交易樹利用特定的業(yè)務參數(shù)進行分類，通過自頂向下方式（下層分類是在上層分類結(jié)果基礎上進行的），依次對各層子樹（第1層根節(jié)點除外）進行分類。分類過程主要分為以下幾個步驟：

（1）對于交易樹的第i層，若第i-1層中每個分類交易子樹的層數(shù)是第2層，則考察整個交易子樹；

（2）對于交易樹的第i-1層，若其中1-項集不是頻繁項集的子樹，則將其從交易數(shù)據(jù)庫中刪除且不納入后續(xù)分類；

（3）對于交易樹的第i-1層，若每棵待分類的交易子樹，則計算所有子樹兩兩之間的業(yè)務參數(shù)。

由于包含這兩棵交易子樹的2-項集(subtree-i，subtree-j)表示的是這兩類交易在事務數(shù)據(jù)庫中同時出現(xiàn)的頻率，值越大，則這兩類交易子樹參數(shù)相關性程度可能會越高，按每一層上交易子樹之間的業(yè)務參數(shù)相關程度，根據(jù)層次連接聚類算法的方法，就可以得到該層上各交易子樹之間相互獨立(或說弱利潤相關)的分類，然后依此對上層交易數(shù)據(jù)庫進一步進行劃分，使得生成k-項集時須掃描的數(shù)據(jù)庫變得越來越小，以此達到提高生成頻繁項集和關聯(lián)規(guī)則的效率。因此該改進算法適用于大型的金融交易之中，比如銀行交易、大型企業(yè)交易等。

表1 算法參數(shù)Tab.1 Parameters of algorithm

（二）應用遺傳算法的思想改進Apriori算法，應用此算法進行求解，算法參數(shù)見表1。

在算法中還隨機產(chǎn)生了一組具有2000個事務、30個項的數(shù)據(jù)。

表2顯示了在不同支持度下所得到的最大頻繁項集的個數(shù)、消耗時間和循環(huán)次數(shù)。相對于原始的Apriori算法改進后的算法節(jié)省了時間，提高了效率。

表2 實驗運行結(jié)果Tab.2 Result of experiment

4 結(jié)論

根據(jù)理論以及實驗結(jié)果分析，改進算法相比與傳統(tǒng)的算法，調(diào)高了效率，且節(jié)省了時間，在實際應用中有一定的可行性，根據(jù)不同算法的不同特點，可以應用到相應的領域中去。

［1］馮潔，陶宏才.典型關聯(lián)規(guī)則挖掘算法的分析與比較［J］.計算機技術與發(fā)展，2007，17（3）：121-124.

［2］陳沛玲.決策樹分類算法研究［D］.中南大學，2007.

［3］Perner P.Recent advances in data mining［J］.Engineering Appli-cations of Artificial Intelligence，2006，19（4）：361-362.

［4］劉建.商務智能中關聯(lián)規(guī)則挖掘算法的研究及應用［D］.長春理工大學，2009.