多種關聯規則挖掘算法的研究與分析

程險峰

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

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

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

1 傳統的關聯規則挖掘算法

1.1 Apriori算法

Apriori算法最初是由 Agrawal等人提出的，Apriori算法是一種經典的規則挖掘算法，通過挖掘布爾關聯規則頻繁項集挖掘數據。其基本原理如下：

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

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

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

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

1.2 基于劃分的算法

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

1.3 FP-樹頻集算法

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

2 幾種關聯規則挖掘算法的改進

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

基于遺傳算法的思想改進 Apriori算法，只需要對數據庫進行一次掃描，便可以給定一個映射，實現據庫到矩陣的映射，以下均可通過在矩陣上的運算來完成所有對數據庫的掃描。將某個生物種群對環境的適應性問題轉化為求解關聯規則最長頻繁項集的問題，生物種群的進化過程即為優化問題的求解過程，生物種群的個體即為優化變量。基于遺傳算法改進Apriori算法的基本思想：

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

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

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

3 改進算法分析

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

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

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

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

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

表1 算法參數Tab.1 Parameters of algorithm

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

在算法中還隨機產生了一組具有2000個事務、30個項的數據。

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

表2 實驗運行結果Tab.2 Result of experiment

4 結論

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

［1］馮潔，陶宏才.典型關聯規則挖掘算法的分析與比較［J］.計算機技術與發展，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］劉建.商務智能中關聯規則挖掘算法的研究及應用［D］.長春理工大學，2009.