摘要:本文分析了挖掘頻繁訪問模式的過程和當前Apriori算法的缺陷,提出了一種Apriori算法的改進算法:BI_Apriori算法。改進的算法采用不規(guī)則數(shù)組來保存項集信息,有效省去了掃描數(shù)據(jù)庫所耗費的大量時間,將項集有序性引入到該數(shù)組上,減少了候選項集的個數(shù),并采用二進制來表示1階頻繁訪問模式,提高了模式匹配和連接的效率。試驗結果表明,該改進算法能更有效地發(fā)現(xiàn)各種長度不同的訪問模式。
關鍵詞:數(shù)據(jù)挖掘 關聯(lián)規(guī)則 Apriori算法
Apriori 算法是一個布爾關聯(lián)規(guī)則頻繁項集挖掘算法,它主要是由迭代的方法一步一步使用搜索數(shù)據(jù)庫尋找頻繁項目集。主要步驟是:造成頻繁1-項集的L1,掃描數(shù)據(jù)庫D,在D中,每個數(shù)據(jù)項出現(xiàn)的是一個經(jīng)常一集-項目候選集C1和對每個數(shù)據(jù)出現(xiàn)的次數(shù)的統(tǒng)計項目,比最小支持數(shù)較多(前),由項的集合定義是經(jīng)常1-項集一樓;第一步畝,造成頻繁畝,項目集路加,從上一步驟中頻繁使用造成的(K-1)-項集路加與自己生產(chǎn)1的K-候選項目集一套杉木連接,掃描數(shù)據(jù)庫事務數(shù)據(jù)庫,計算中的每個成員杉木出現(xiàn)的次數(shù)會比候選人的最低支持較少刪除,終于在頻繁的K-項集。
該算法的基本思想是:首先找出所有的頻集,這些項集出現(xiàn)的頻繁性至少和預定義的最小支持度一樣。然后由頻集產(chǎn)生強關聯(lián)規(guī)則,這些規(guī)則必須滿足最小支持 度和最小可信度。然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則,產(chǎn)生只包含集合的項的所有規(guī)則,其中每一條規(guī)則的右部只有一項,這里采用的是中規(guī)則的定義。一旦這些規(guī)則被生成,那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集,使用了遞推的方法可能產(chǎn)生大量的候選集,以及可能需要重復掃描數(shù)據(jù)庫,是Apriori算法的兩大缺點。
Apriori算法的優(yōu)點是結構簡單,易于理解,沒有復雜的推導。另外算法應用Apriori性質而設計的候選產(chǎn)生——檢查方法。在許多情況下大大縮小了需要檢查的候選規(guī)模,使算法效率大幅度提高。但Apriori算法依然存在兩個主要的問題:
1.多次掃描數(shù)據(jù)庫
Apriori算法需要在每進行一次迭代的時候掃描一次數(shù)據(jù)庫,一般挖掘出的最大頻繁項集的長度為N時,需要掃描N次數(shù)據(jù)庫,而在實際應用中經(jīng)常需要挖掘很長的模式,多次掃描數(shù)據(jù)庫帶來巨大開銷。
2.可能產(chǎn)生大量候選
Apriori算法在迭代過程中要在內存中產(chǎn)生,處理和保存候選頻繁項集,這個數(shù)量有時候是非常巨大的,導致算法在廣度和深度上的適應性很差。
即Apriori算法有個嚴重的缺陷:因為需要多次掃描數(shù)據(jù)庫和產(chǎn)生大量的頻繁項集,使得算法的花費在I/0上的時間很多,從而導致挖掘的效率非常低。因此,為了提高Apriori算法的有效性,需要對Apriori算法進行改進。人們對Apriori算法進行了大量的改進,希望能夠找出一個高效、可靠的挖掘頻繁項集的算法。因此本文對Apriori算法進行了改進,提出一種基于劃分的Apriori改進算法。
Apriori算法需要頻繁掃描整個數(shù)據(jù)庫。與Apriori算法相比,基于劃分的改進算法只需要掃描整個數(shù)據(jù)庫兩次。在第一遍掃描中,將產(chǎn)生一組潛在的頻繁項目集,這組項目集是最后要確定的頻繁項目集的超集,它也許包含錯誤的選擇,但絕對不會漏掉正確的選擇。在第二遍掃描中,針對這些潛在的頻繁項目集確定它針對整個數(shù)據(jù)庫的實際支持度,從而可以最后確定所求的真正的頻繁項目集。
數(shù)據(jù)挖掘的研究和應用受到了學術界、實業(yè)界和政府部門的越來越多的重視。Apriori算法是關聯(lián)規(guī)則的基礎算法,對于其他復雜算法的實現(xiàn)也有很大的作用。但對于大型數(shù)據(jù)庫來說,每掃描一次數(shù)據(jù)庫需要很長時間,并用Apriori算法需要k次掃描數(shù)據(jù)庫才能得到k-頻繁項目集,所以從性能上講,Apriori算法并不理想。而改進后的算法,只需要掃描一次數(shù)據(jù)庫得到0-1矩陣,接下來的工作就是對向量的運算就可以得到頻繁項集,而且矩陣是不斷變小的,這樣就可以大大提高算法的執(zhí)行效率。試驗表明,對于大型數(shù)據(jù)庫和長模式的關聯(lián)規(guī)則挖掘,改進的算法有效地壓縮了搜索空間,提高了頻繁項集的生成效率。
作者單位:湖北省襄樊市武漢大學計算機學院