原文寫于個(gè)人博客缭裆，歡迎關(guān)注www.xiaolewei.com
前言
數(shù)據(jù)挖掘領(lǐng)域的頻繁模式中，Apriori算法算是經(jīng)典，然而該算法有如下的問題：
- 對數(shù)據(jù)庫多次掃描
- 候選集數(shù)量龐大
- 為計(jì)算候選集支持度所需負(fù)載較重
所以有了很多改進(jìn)算法，DHP是其中一個(gè)基于散列優(yōu)化的算法，主要用于縮小Ck的項(xiàng)集個(gè)數(shù)
原理
DHP算法生效于Apriori算法的剪枝步過程中岸晦。在第k次掃描時(shí)，生成每個(gè)事務(wù)的k+1項(xiàng)集睛藻，代入一個(gè)Hash函數(shù)中启上，生成一個(gè)Hash表，同時(shí)記錄每個(gè)桶中元素個(gè)數(shù)店印。
當(dāng)生成Ck+1時(shí)冈在，對Lk*Lk自連接產(chǎn)生的結(jié)果先進(jìn)行代入上述Hash函數(shù)若所落的該桶的計(jì)數(shù)小于最小支持閾值，則該元素必定不為頻繁項(xiàng)集按摘，故可以過濾掉之包券，不放入Ck+1中
由于所有具有相同Hash值的項(xiàng)的總個(gè)數(shù)小于最小支持閾值，如：
Hash(A,B) = 4
Hash(X,Y) = 4
不妨假設(shè)4號桶元素個(gè)數(shù)小于最小支持閾值炫贤，則單個(gè)的 (A,B) 個(gè)數(shù)也必定小于最小支持閾值溅固。故可排除
樣例詳解
假設(shè)最小支持度計(jì)數(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-項(xiàng)目候選集C1,并統(tǒng)計(jì)其支持度兰珍，得到對應(yīng)L1:
C1 = {{A} 侍郭， {B} ， {C} 掠河， {D} 亮元， {E}}
L1 = {{A} ， {B} 唠摹， {C} 爆捞， {D} ， {E}}
在這次掃描的同時(shí)會對每個(gè)事務(wù)產(chǎn)生所有的2項(xiàng)集跃闹，即：
構(gòu)造2項(xiàng)集的Hash函數(shù)嵌削，如：
hash(x,y) = (order(x)*10 + order(y)) % 7
order()函數(shù)返回參數(shù)的序，如本例中 order(A) = 1 , order(B) = 2 ....
將該次掃描得到的所有2項(xiàng)集代入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é)果的每個(gè)子集，代入hash(x,y)函數(shù)找默，并丟棄掉hash結(jié)果為2艇劫、4、5的子集（該桶的對應(yīng)計(jì)數(shù) < min_sup）
得到:
C2 = { {A ,C} , {A ,D } ,{A ,E} , {B ,D } , {C ,D } , {C ,E} , {D , E } }
相比于沒有應(yīng)用Hash過濾的Apriori惩激，可以多去除一個(gè){B, E}項(xiàng)店煞。
后續(xù)
后續(xù)步驟重復(fù)上述過程，指導(dǎo)不能產(chǎn)生頻繁項(xiàng)集风钻，則終止顷蟀。
總結(jié)
DHP算法作為Apriori算法的一個(gè)優(yōu)化，基本過程還是與Apriori無異骡技，但是通過建立k項(xiàng)集的Hash表鸣个，再生產(chǎn)Ck時(shí)，可以有效過濾掉非頻繁項(xiàng)集布朦，從而達(dá)到壓縮Ck的目的,提高剪枝效率囤萤。
DHP算法的效率高低直接受所選用的hash函數(shù)影響，需要有一個(gè)比較好的hash函數(shù)
