数据挖掘算法DHP

前言：

Apriori算法是关联规则挖掘经典算法，但不适合在大型数据库中挖掘关联规则，时间太慢，许多学者提出了改进的算法。比如DHP算法。

DHP

1. 减少候选集数量

• 背景：这个操作是基于Ck来做的，我们知道原来的话，Ck的得到是通过L(k-1)*L(1)笛卡尔积连接，去掉k-1项集得到。同时，我们也知道其实Ck还是有很多都不是频繁项集。
  现在的目标就是：扫描一遍数据库，将Ck候选集的数量留下1/2（当然这只是为了形象化，不一定是1/2）。
  要知道，原来的化，假设Ck中有10个候选集，原来是要对每一个候选集扫描一遍数据库，然后统计次数的，也就是要10遍扫描，浪费了时间。而现在将次数降低到1+5=6次。这么神奇，如何做到？
• 做法：
  以对减少C2数量为例。数据库如下表。
  算法的条件为：最小支持度为2。哈希函数为:h{ {x,y} }= ((order of x)*10+order of y) )mod 7 。
  你可以构造其他的的Hash 函数，但是一个较好的Hash 函数能减少冲突。这里为了方便说明DHP 算法的执行过程，取的哈希函数比较简单。对应地，数据库D 中包含的项为A 、B 、C 、D 、E ，其中order of A 为1 ,order of C 为3 。

为C2建立用于快速统计的哈希表H2 。建表的方法是:对读取的每行事务根据要构造的候选集合的长度进行组合分解。例如，为构造候选2-项目集C2 而建立H2时，将数据库分解，如表2 所示。对于每一个2项集分别代入哈希函数，根据算得的哈希值填写哈希表。例如，对于2-项目集{B, D} ， 带入哈希函数得:h{ {B ,D} }=((order of B)10 十(order of D) )mod 7= (210 十4)mod 7=3 。在经历上表中19个2项集的分别计算后，得到下面的表。比如{B,E}的hash的是4，上面19个里面算出来4的就只有{B,E}，所以元素个数为1。

而实际上，上面的表只是为了我们理解，在计算机里面的表其实只是一个位向量（6，2，0，6，1，0，4）。然后根据支持度是否小于2变为：（1，1，0，1，0，0，1)。其中0表示支持度小于2。
下面可以开始缩减C2数量了，我们知道C2最开始L1L1之后应该为：{ {A ,B} , {A ,C } ,{A ,D} ,{A ,E} {B ,C} , {B ,D} ,{B ,E}, {C ,D } , {C ,E} , {D , E } }，一共10项。
接下来，我们把这10项依次带入hash，比如hash(A,B)=5,然后根据（1，1，0，1，0，0，1)，可以知道，其为0，即不是频繁2项集，删除。
这样10次之后，只留下了{ {A ,C} , {A ,D } ,{A ,E} , {B ,D } , {C ,D } , {C ,E} , {D , E } }，只留下了7项。至此，hash表H2的作用已经没了。
延申，如果你可以做一个更大的hash表，使得原来的10项2项集都有一个不一样的hash取值。那么只需要扫描一趟数据库，生成一个hash表，直接就可以得到最终的L2。
2. 减小项的数量
背景：如果原来共有5个项{A,B,C,D,E},现在得到了L1={{A},{B},{C},{D},{E}},L2={ {A ,E }，{A,D} , {C ,D } ，{C,E} }，接下来，按照流程，我们应该做的是L2L1生成候选集C3。现在目标：
我们不需要将L2与L1中的所有项都连接。比如L2不需要连接B。
为什么？因为假设L3中含有B，比如xBy,我们可以推出，L2中一定有{xB},{By},{xy}。即L2中至少要出现两次B，而我们的L2中1次也没有。
做法：
根据上述思路，我们可以通过观察L2得到项的出现次数：
a[0]=2,a[1]=0,a[2]=2,a[3]=2,a[4]=2
由于需要在L2出现2次以上的项才有可能在C3中出现，从而排除1，也就是B。我们L11={A,C,D,E}，我们生成C3的时候应该为L2*L11。
进一步处理
根据上面的数组，发现有刚好出现2次的，
以D为例，从这里我们可以推断：
如果L3里面有D的话，一定是{A,D}+{C,D}={A,C,D}。反过来，若{A,C,D}在L3中，{A,C}必然在L2中，我们观察我们的L2，并不在，所以可以直接排除D。这样我们的L11又变小了。
3.标记无需扫描交易记录
如果我们发现一个交易记录不包含Lk中的任意一个k项集，那么可以把这个交易记录标记为0,以后扫描数据库的时候直接跳过。
原理：不包含Lk中的任意一个k项集，将不可能包含频繁k+1项集。