有關Apriori算法的拙見

摘要:本文分析了挖掘頻繁訪問模式的過程和當前Apriori算法的缺陷，提出了一種Apriori算法的改進算法:BI_Apriori算法。改進的算法采用不規則數組來保存項集信息，有效省去了掃描數據庫所耗費的大量時間，將項集有序性引入到該數組上，減少了候選項集的個數，并采用二進制來表示1階頻繁訪問模式，提高了模式匹配和連接的效率。試驗結果表明，該改進算法能更有效地發現各種長度不同的訪問模式。

關鍵詞:數據挖掘 關聯規則 Apriori算法

Apriori 算法是一個布爾關聯規則頻繁項集挖掘算法，它主要是由迭代的方法一步一步使用搜索數據庫尋找頻繁項目集。主要步驟是:造成頻繁1-項集的L1，掃描數據庫D，在D中，每個數據項出現的是一個經常一集-項目候選集C1和對每個數據出現的次數的統計項目，比最小支持數較多(前)，由項的集合定義是經常1-項集一樓;第一步畝，造成頻繁畝，項目集路加，從上一步驟中頻繁使用造成的(K-1)-項集路加與自己生產1的K-候選項目集一套杉木連接，掃描數據庫事務數據庫，計算中的每個成員杉木出現的次數會比候選人的最低支持較少刪除，終于在頻繁的K-項集。

該算法的基本思想是:首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然后由頻集產生強關聯規則，這些規則必須滿足最小支持 度和最小可信度。然后使用第1步找到的頻集產生期望的規則，產生只包含集合的項的所有規則，其中每一條規則的右部只有一項，這里采用的是中規則的定義。一旦這些規則被生成，那么只有那些大于用戶給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推的方法可能產生大量的候選集，以及可能需要重復掃描數據庫，是Apriori算法的兩大缺點。

Apriori算法的優點是結構簡單，易于理解，沒有復雜的推導。另外算法應用Apriori性質而設計的候選產生——檢查方法。在許多情況下大大縮小了需要檢查的候選規模，使算法效率大幅度提高。但Apriori算法依然存在兩個主要的問題:

1.多次掃描數據庫

Apriori算法需要在每進行一次迭代的時候掃描一次數據庫，一般挖掘出的最大頻繁項集的長度為N時，需要掃描N次數據庫，而在實際應用中經常需要挖掘很長的模式，多次掃描數據庫帶來巨大開銷。

2.可能產生大量候選

Apriori算法在迭代過程中要在內存中產生，處理和保存候選頻繁項集，這個數量有時候是非常巨大的，導致算法在廣度和深度上的適應性很差。

即Apriori算法有個嚴重的缺陷:因為需要多次掃描數據庫和產生大量的頻繁項集，使得算法的花費在I/0上的時間很多，從而導致挖掘的效率非常低。因此，為了提高Apriori算法的有效性，需要對Apriori算法進行改進。人們對Apriori算法進行了大量的改進，希望能夠找出一個高效、可靠的挖掘頻繁項集的算法。因此本文對Apriori算法進行了改進，提出一種基于劃分的Apriori改進算法。

Apriori算法需要頻繁掃描整個數據庫。與Apriori算法相比，基于劃分的改進算法只需要掃描整個數據庫兩次。在第一遍掃描中，將產生一組潛在的頻繁項目集，這組項目集是最后要確定的頻繁項目集的超集，它也許包含錯誤的選擇，但絕對不會漏掉正確的選擇。在第二遍掃描中，針對這些潛在的頻繁項目集確定它針對整個數據庫的實際支持度，從而可以最后確定所求的真正的頻繁項目集。

數據挖掘的研究和應用受到了學術界、實業界和政府部門的越來越多的重視。Apriori算法是關聯規則的基礎算法，對于其他復雜算法的實現也有很大的作用。但對于大型數據庫來說，每掃描一次數據庫需要很長時間，并用Apriori算法需要k次掃描數據庫才能得到k-頻繁項目集，所以從性能上講，Apriori算法并不理想。而改進后的算法，只需要掃描一次數據庫得到0-1矩陣，接下來的工作就是對向量的運算就可以得到頻繁項集，而且矩陣是不斷變小的，這樣就可以大大提高算法的執行效率。試驗表明，對于大型數據庫和長模式的關聯規則挖掘，改進的算法有效地壓縮了搜索空間，提高了頻繁項集的生成效率。

作者單位:湖北省襄樊市武漢大學計算機學院