原文寫于個人博客，歡迎關(guān)注www.xiaolewei.com
前言
數(shù)據(jù)挖掘領(lǐng)域的頻繁模式中，Apriori算法算是經(jīng)典，然而該算法有如下的問題：
- 對數(shù)據(jù)庫多次掃描
- 候選集數(shù)量龐大
- 為計算候選集支持度所需負載較重
所以有了很多改進算法，DHP是其中一個基于散列優(yōu)化的算法，主要用于縮小Ck的項集個數(shù)
原理
DHP算法生效于Apriori算法的剪枝步過程中。在第k次掃描時，生成每個事務(wù)的k+1項集，代入一個Hash函數(shù)中，生成一個Hash表，同時記錄每個桶中元素個數(shù)。
當生成Ck+1時，對Lk*Lk自連接產(chǎn)生的結(jié)果先進行代入上述Hash函數(shù)若所落的該桶的計數(shù)小于最小支持閾值，則該元素必定不為頻繁項集，故可以過濾掉之，不放入Ck+1中
由于所有具有相同Hash值的項的總個數(shù)小于最小支持閾值，如：
Hash(A,B) = 4
Hash(X,Y) = 4
不妨假設(shè)4號桶元素個數(shù)小于最小支持閾值，則單個的 (A,B) 個數(shù)也必定小于最小支持閾值。故可排除
樣例詳解
假設(shè)最小支持度計數(shù)為2，即min_sup = 2
并使用如下數(shù)據(jù)：
| TransactionID | ProductID |
|---|---|
| T1 | A D E |
| T2 | B D |
| T3 | B D E |
| T4 | C E |
| T5 | C D |
| T6 | C E |
| T7 | A C D E |
| T8 | C D E |
第一次掃描
生成1-項目候選集C1,并統(tǒng)計其支持度，得到對應(yīng)L1:
C1 = {{A} ， {B} ， {C} ， {D} ， {E}}
L1 = {{A} ， {B} ， {C} ， {D} ， {E}}
在這次掃描的同時會對每個事務(wù)產(chǎn)生所有的2項集，即：
構(gòu)造2項集的Hash函數(shù)，如：
hash(x,y) = (order(x)*10 + order(y)) % 7
order()函數(shù)返回參數(shù)的序，如本例中 order(A) = 1 , order(B) = 2 ....
將該次掃描得到的所有2項集代入Hash函數(shù)，得到對應(yīng)Hash表：
將L1*L1自連接，得到：
L1 * L1 ={ {A ,C} , {A ,D } ,{A ,E} , {B ,D} , {B ,E} , {C ,D } , {C ,E} , {D , E } }
對于上述結(jié)果的每個子集，代入hash(x,y)函數(shù)，并丟棄掉hash結(jié)果為2、4、5的子集（該桶的對應(yīng)計數(shù) < min_sup）
得到:
C2 = { {A ,C} , {A ,D } ,{A ,E} , {B ,D } , {C ,D } , {C ,E} , {D , E } }
相比于沒有應(yīng)用Hash過濾的Apriori，可以多去除一個{B, E}項。
后續(xù)
后續(xù)步驟重復(fù)上述過程，指導(dǎo)不能產(chǎn)生頻繁項集，則終止。
總結(jié)
DHP算法作為Apriori算法的一個優(yōu)化，基本過程還是與Apriori無異，但是通過建立k項集的Hash表，再生產(chǎn)Ck時，可以有效過濾掉非頻繁項集，從而達到壓縮Ck的目的,提高剪枝效率。
DHP算法的效率高低直接受所選用的hash函數(shù)影響，需要有一個比較好的hash函數(shù)
