原文写于个人博客，欢迎关注www.xiaolewei.com

前言

数据挖掘领域的频繁模式中，Apriori算法算是经典，然而该算法有如下的问题：

1. 对数据库多次扫描
2. 候选集数量庞大
3. 为计算候选集支持度所需负载较重

所以有了很多改进算法，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函数