原文写于个人博客，欢迎关注www.xiaolewei.com
前言
数据挖掘领域的频繁模式中，Apriori算法算是经典，然而该算法有如下的问题：
- 对数据库多次扫描
- 候选集数量庞大
- 为计算候选集支持度所需负载较重
所以有了很多改进算法，DHP是其中一个基于散列优化的算法，主要用于缩小Ck的项集个数
原理
DHP算法生效于Apriori算法的剪枝步过程中。在第k次扫描时，生成每个事务的k+1项集，代入一个Hash函数中，生成一个Hash表，同时记录每个桶中元素个数。
当生成Ck+1时，对Lk*Lk自连接产生的结果先进行代入上述Hash函数若所落的该桶的计数小于最小支持阈值，则该元素必定不为频繁项集，故可以过滤掉之，不放入Ck+1中
由于所有具有相同Hash值的项的总个数小于最小支持阈值，如：
Hash(A,B) = 4
Hash(X,Y) = 4
不妨假设4号桶元素个数小于最小支持阈值，则单个的 (A,B) 个数也必定小于最小支持阈值。故可排除
样例详解
假设最小支持度计数为2，即min_sup = 2
并使用如下数据：
| 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,并统计其支持度，得到对应L1:
C1 = {{A} ， {B} ， {C} ， {D} ， {E}}
L1 = {{A} ， {B} ， {C} ， {D} ， {E}}
在这次扫描的同时会对每个事务产生所有的2项集，即：
构造2项集的Hash函数，如：
hash(x,y) = (order(x)*10 + order(y)) % 7
order()函数返回参数的序，如本例中 order(A) = 1 , order(B) = 2 ....
将该次扫描得到的所有2项集代入Hash函数，得到对应Hash表：
将L1*L1自连接，得到：
L1 * L1 ={ {A ,C} , {A ,D } ,{A ,E} , {B ,D} , {B ,E} , {C ,D } , {C ,E} , {D , E } }
对于上述结果的每个子集，代入hash(x,y)函数，并丢弃掉hash结果为2、4、5的子集（该桶的对应计数 < min_sup）
得到:
C2 = { {A ,C} , {A ,D } ,{A ,E} , {B ,D } , {C ,D } , {C ,E} , {D , E } }
相比于没有应用Hash过滤的Apriori，可以多去除一个{B, E}项。
后续
后续步骤重复上述过程，指导不能产生频繁项集，则终止。
总结
DHP算法作为Apriori算法的一个优化，基本过程还是与Apriori无异，但是通过建立k项集的Hash表，再生产Ck时，可以有效过滤掉非频繁项集，从而达到压缩Ck的目的,提高剪枝效率。
DHP算法的效率高低直接受所选用的hash函数影响，需要有一个比较好的hash函数
