頻繁項集挖掘的性能

Question

我已經實現了用於挖掘頻繁項集的apriori算法，它對於樣本數據工作正常，但是當我試圖執行零售數據集時可用的http://fimi.ua.ac.be/data/retail.dat大約3MB數據與88k事務和1600個唯一項目大約需要29個小時。我搜索了性能影響的原因，發現生成候選項目集的算法花費了大量時間。任何人都可以幫助我如何提高性能，或者這是一種正常的算法行爲。

Answer 1

你用什麼算法，什麼是你門檻？

如果您有n滿足最低支持度的1個項目集，Apriori（和許多其他人）必須考慮n*(n-1)/2 2項目集。這當然變得相當昂貴。在Apriori中，2項目組通常是最大和最昂貴的一步（取決於您的設置，3項目組可能更差，但通常你沒有那麼遠......）

根據您的數據特徵，Eclat可能表現更好 - 或更糟糕。 FP-增長非常聰明，但要正確高效地實施，似乎非常棘手。

也存在着變體的無數的，有些是基於概率和可以基本上更快。

但實質上執行和數據集/參數設置無關緊要。在同一組數據中，一種方法可能比另一種更好;實現可能很容易產生10倍的性能差異。特別是對於APRIORI，許多人不完全理解所使用的修剪技巧，最終做了太多的工作。

對於您的示例數據集（不幸的是，如果沒有解釋數字的字典，它是完全無益的），我的APRIORI在minSupport = 1000的低端Atom CPU上在大約1分鐘內完成。發現4項集分別爲：

32, 38, 39, 48: 1236 
32, 39, 41, 48: 1646 
36, 38, 39, 48: 1080 
38, 39, 41, 48: 1991 
38, 39, 48, 110: 1031 
38, 39, 48, 170: 1193 

但正如前面提到的，重要的參數一很多與APRIORI。 APRIORI在交易數量上可以很好地擴展（這可能比主內存更適合），但是它有大量候選，所以您需要將minSupport設置得足夠高。

隨着minSupport = 1000：

1-frequentItemsets (56) 
2-frequentItemsets (49) 
3-frequentItemsets (24) 
4-frequentItemsets (6) 
APRIORI runtime: 55401 ms 

隨着minSupport = 500：

1-frequentItemsets (185) 
2-frequentItemsets (191) 
3-frequentItemsets (79) 
4-frequentItemsets (13) 
5-frequentItemsets (0) 
APRIORI runtime: 136594 ms 

正如你所看到的，運行時間增加了一倍多。原因是1項目組增加了，產生了更多的2項目候選項。在3和4項目中，差異不再那麼大。但總體而言，真正低端CPU的2分鐘運行時間還不錯。

降低最低支持250：

1-frequentItemsets (587) 
2-frequentItemsets (640) 
3-frequentItemsets (273) 
4-frequentItemsets (54) 
5-frequentItemsets (4) 
APRIORI runtime: 954984 ms 

現在運行開始爆炸。將近16分鐘才找到5個項目集：

32, 38, 39, 41, 48: 448 
36, 38, 39, 41, 48: 334 
38, 39, 41, 48, 110: 346 
38, 39, 41, 48, 170: 413 

，你可以看到，38, 39, 41, 48 4項集正在這一數據集的關鍵作用（但我們已經發現了這個在第一次運行）。我們現在還可以給予38, 39, 41, 48 -> 32的信心，這將是最有信心的規則，涉及5個項目：涉及前四項交易的約22.5%也涉及項目32。但鑑於AFAICT這個數據集的數字含義是未知的，我們不知道這個規則在實踐中是否真的很有趣，或者只是一個玩具練習。

要minSupport = 100，運行時間進一步增長：

1-frequentItemsets (1857) 
2-frequentItemsets (2785) 
3-frequentItemsets (1475) 
4-frequentItemsets (306) 
5-frequentItemsets (28) 
6-frequentItemsets (0) 
APRIORI runtime: 8256507 ms 

即超過兩小時。大部分時間花費在2個項目集上：有170萬名候選人，其中2785個頻繁出現。對於3個項目組，可以粗略估計只有幾千名候選人，但不會再有數百萬人。我有一些計劃，通過根據候選人數量在兩個代碼路徑之間切換來進一步改進實施。 （'''更新：'''進行了簡單的修改，我將運行時間進一步縮短了20倍。所以，'''實現很重要''，它可以輕鬆地將因子設置爲100到1000或更多 - 當APRIORI修剪沒有完全實施，例如）

如果我有時間來閱讀Eclat算法並重新實現它，我可以更新與結果。我相信在這裏速度會更快，FP的增長也會更快。

Answer 2

有一個pretty efficient algorithm proposed by Karp Papadimtrioue Shanke，即爲了發現具有用於(0,1)任何theta的至少theta頻率項尋找候選上的數據（它基本上設計成用於流處理）的單個遍歷。

在高一級的算法：

• 收集元件到PF，計數其外觀
• 每當遇到1 /θ不同的元件，由1減少所有計數器和從PF除去那些計數器爲零
• 輸出在PF存活這個過程

算法產率1 /西塔（至多）的候選，並且其具有無假陰性的元素（不錯過任何候選人） - 但確實有一些誤報（有些候選人不常出現）。

爲了簡單起見，假設1 /西塔是整數。

僞代碼：

PF = {} //empty dictionary 
for each element e: 
    if PF.contains(e): 
     PF[e] = PF[e] + 1 
    else: 
     PF[e] = 1 
     if PF.size() == 1/Theta: 
      for each element k in PF: 
       PF[k] = PF[k] - 1 
       if PF[k] == 0: 
        remove k from PF 
When done, all elements in PF are your candidates. 

Answer 3

這取決於您的實施。實現Apriori時可以進行許多優化。

首先，如果您閱讀Agrawal &的原始Apriori論文，您會注意到他們建議使用特殊的哈希樹來有效地計算候選人的支持。如果你想看看這個實現是如何工作的，那麼在SPMF開源數據挖掘庫中有一個使用HashTree實現的Apriori版本。它被命名爲AprioriHT。

避免多次掃描數據庫的另一個優化命名爲AprioriTID。每個項目組都使用包含它的一組事務標識（tid set）進行註釋。然後，當通過組合兩個項目集A和B來生成候選項時，爲了直接統計AUB的支持而不掃描數據庫，可以執行A和B的tid集的交集。爲了進一步優化，您可以實現tid集位矢量。此版本的APriori被稱爲AprioriTID。

在算法Pascal中提出了另一種優化。它是使用生成器的概念來推斷某些項集的支持閾值，而不使用來自形式概念分析的生成器項集的概念來掃描數據庫。

另一個優化是按照詞典順序對Apriori中的每個級別的項目集進行排序，並且還按照詞典順序對每個項目集中的所有項目進行排序。然後，在生成候選項時，可以使用此排序來避免將所有項目集彼此進行比較以生成更大的候選項。

還有其他優化。在FIMI網站上，有不同優化的各種實現。

如果你想看一個優化版本，你可以看看我的實現在SPMF data mining library in Java。此外，在同一個網站上，您將獲得更快的算法實現，如FPGrowth。