hash tree 在apriori 演算法中是如何進行支持度計數的？

01-29

我在看數據挖掘導論（完整版）第六章的時候，看不懂作者舉用hash tree 進行關聯規則支持度計數的例子。如圖：
他這裡hash function 是 h(p)=p mod 3 。目的是計算transaction 1 2 3 5 6的3-項集的支持度計數，各位能否解釋下transaction 1 2 3 5 6是如何通過hash function 得到節點下的value的？

HASH演算法的目的是計算出各個候選項集的支持度。

分2個步驟。

第一步，建立HASH樹。將所有需要計算支持度的項集，也就是書中的15
個「候選3項集」建三叉樹。第一層，首項1、3或5的居左，2、5或8居中，3、6或9居右；如果有層的葉子節點超過3個，就開始第二層，繼續往下分。書
中這個建hash樹的過程一筆帶過。這過程，這篇博文Apriori中的hash tree 講得很清楚。

第二步，對於每個事務，來走一遍Hash樹，書中舉了{1.2.3.5.6}這個事務，就和查爾斯周說的相似，但不是簡單的枚舉，而是跟著樹走。

這裡要結合211頁那張圖6-9來看，事務跟著樹的枝分解：

首
先分解成1+[2356]，2+[356]，3+[56]。1+[2356]沿著三叉樹的左子樹再分解成，12+[356]、13+[56]和15+
[6]，再以12+[356]為例，因為第二項是2，所以它再沿著中子樹走，其中125（第三項是5）最後沿著中間走到125/458這個葉子。恰好，葉
子中有125這個項集，那麼這個125這個候選項集的支持度就加1。

當然，效果上和查爾斯周，說的一樣。

剛剛也看到了這裡，不知道我這樣子理解對不對。

首先，對候選3-項集中的每一個3-項集，依次對其每一個項用h(p)=p mod 3來確定哈希樹中每一層的分支方向。比如，頻繁項集{1,2,4}，先用1 mod 3=1，所以它在第一層被劃分到左子樹，然後用2 mod 3=2，所以它在第二層被劃分到中子樹，最後用4 mod 3=1，所以它最後被劃分到第三層的左子樹節點。

然後，對於每一個事務t，先枚舉其所有的3-項集。然後對每一個3-項集按上面劃分候選項集的方法把它劃分到哈希樹的某一個結點中。比如事務t={1,2,3,5,6}有一個3-項集{1,2,5}就會被劃分到哈希樹{1,2,5}和{4,5,8}結點中。

最後，就是比較哈希樹結點中的3-項集與每一個事務t中的3-項集，如果有相同的就增加該3-項集的支持度計算。

謝邀。題主的書我沒看過，為了回答問題再去看這本書也是難為我了。

Apriori演算法是關聯規則的經典演算法。我轉一篇我看到的寫得比較淺顯易懂的文章吧。

Apriori algorithm 是關聯規則領域裡最具影響力的基礎演算法。它是由 Rakesh Agrawal 在 1994 年提出的，詳細的介紹在這裡《Fast Algorithms for Mining Association Rules》。十幾年過去了，不少學者圍繞著 Apriori 進行了諸多改良。但與 1994 年相比，目前基於互聯網的應用，數據量大了幾十倍甚至是幾百倍，因此，基於 Apriori 的演算法逐漸暴露出其運算成本過高的問題。但不管怎樣，對於大師及其做出的貢獻，我們也只有高山仰止的份兒。

Apriori 是一種廣度優先演算法，通過多次掃描資料庫來獲取支持度大於最小支持度的頻繁項集。它的理論基礎是頻繁項集的兩個單調性原則：頻繁項集的任一子集一定是頻繁的；非頻繁項集的任一超集一定是非頻繁的。晦澀的理論我這裡就不多寫了，有興趣的可以去看論文。我把裡面的例子給翻譯一下，圖文並茂，簡明易懂。

某資料庫 DB 里有 4 條事務記錄，取最小支持度（min support）為 0.5，則計算頻繁項集的過程如下：

如上可以看出，在海量數據的情況下，Apriori 演算法的運算過程有 2 個問題：

需要多次掃描資料庫，時間成本很高；
運算過程中需要產生大量的候選集，空間成本也非常高。

針對 Apriori 演算法所做的改進也基本上是圍繞著解決這兩個問題進行的，如在掃描DB前首先進行以便事務合併和壓縮，數據分區或抽樣等。

Weka 里有 Apriori 演算法的 Java 實現，非常值得一看。

相關資料：

推薦系統：關聯規則(1)
推薦系統：關聯規則(2)
推薦系統：關聯規則(3) —— FP-Growth 演算法

基本上看懂了，所以來答一發。

我認為這本書寫得很好，數據挖掘入門首選。

P211中圖6-9就是用Hash方法枚舉事務t={1,2,3,5,6}的3-項集，這個圖應該很好理解。

P212中圖6-11其實是作者舉的一個例子：此圖為一個Hash樹，樹中結點為候選項集，樹中結點為候選項集，樹中結點為候選項集！！！明確這個概念，我們在統計支持度時候建立的Hash樹是以候選項集建立的，而Hash樹的葉結點就是候選項集。也就是說，一旦我們在P208中演算法6.1中第5行中產生了候選集 $C_k$ ，我們就通過此候選集建立Hash樹。（第1次循環得到候選2-項集，我們就建立候選2-項集的Hash樹，第2次循環得到候選3-項集，我們就建立候選3-項集的Hash樹，以此類推）如何建立Hash樹，點擊這裡——&>如何建立Hash樹

而在作者舉的例子中，候選項集為圖6-11 Hash樹的葉結點（不要糾結怎麼來的，就是一個例子而已啊啊啊）。我根據此例講一下如何統計候選3-項集的支持度：拿到一個事務t={1,2,3,5,6}，生成3-項集集合 $Omega_3$ ={{1,2,3},{1,2,5},{1,2,6},{1,3,5},{1,3,6},{1,5,6},{2.3.5},{2,3,6},{2,5,6},{3,5,6}}（如果要統計候選2-項集的支持度，我們就需要將把生成事務的2-項集集合），遍歷這個候選3-項集集合，將每一個3-項集散列到對應的葉子結點，得到：

項集{1,2,3}、{1,2,6}和{1,5,6}被散列到【1 5 9】葉子結點
項集{1,2,5}被散列到【【1 2 5】【4 5 8】】葉子結點
項集{1,3,5}、{1,3,6}被散列到【1 3 6】葉子結點
項集{2,3,5}、{2,3,6}和{2,5,6}被散列到【2 3 4】【5 6 7】葉子結點
項集{3,5,6}被散列到【3 5 6】【3 5 7】【6 8 9】葉子結點

所以在這個例子中，訪問了9個葉子結點中的5個，15個項集中的9個與事務t={1,2,3,5,6}進行比較（這5個葉子結點中共有9個項集），也就是P213上面最後一句話。

PS.事務的項集被散列到哪個葉子結點就和該葉子結點中的候選項集進行比較，而不用和全部的候選項集進行比較，這就是Hash樹的優勢！

這本書看到這裡也非常困擾然後來網上搜索，得到這個帖子。

所以是先有了這15個3-項集，然後根據規則分到了對應的位置，具體的規則就是上面鏈接里提到的mod3還有一個根下面超過3要繼續分

所以我還是不明白這15項是哪兒來的，尤其譬如123根本沒有包括在裡面

先除以3取餘數，然後根據餘數分為三類。左中右。這裡從，【1，2，3】開始分，然後是【4，5，6】、最後是【7，8，9】然後餘數相同的分一起。就得到了左上角的hash樹圖。

然後再對候選項級別進行分類，比如事物的項集為：【1，4，7】然後跟著hash樹走。【1】在hash樹圖的最左邊，那麼就放在最左邊。滿了三個項集的時候就看【1，中間的數字，7】對照樹看在哪裡。滿了三個的時候看【1，4，最後一位】在哪裡，然後根據hash樹圖繼續劃分。

應該看得懂了吧 QWQ