提高Eclat算法效率的策略

Strategies of efficiency improvement for Eclat algorithm

为了提高Eclat算法的效率,从剪枝、项集连接和交叉计数3方面对Eclat算法进行优化.将后缀相同的项集归为一个等价类,使剪枝更充分,剪枝时引入双层哈希表加快搜索候选项集子集的速度;提出项集集合划分链表,以减少项集连接过程中比较判断的环节;提出事务标识(Tid)失去阈值,以加快交叉计数的速度.在此基础上提出一种优化的Eclat_opt算法(ZAKI),把它与Eclat原算法以及其他2种Eclat改进算法Diffset(ZAKI),hEclat(熊忠阳)进行对比实验的结果表明,Eclat_opt算法的效率在稀疏数据集上最高,总体时间性能最好.

For the purpose.of efficiency improvement, Eclat algorithm was optimized in three aspectspruning, itemsets connection and intersection. Firstly, the equivalence classes were divided in the suffixbased way to make the best of pruning in which a double layer hash table was utilized to accelerate the search process of subsets of candidate itemsets. Secondly, a partition list of the set of itemsets was presented to eliminate the connection judgment of itemsets. Finally, a transaction id （Tid） lost threshold was introduced to speed up intersection. Based on the above three improvement strategies an Eclat_opt algorithm was proposed. The performance comparison between the Eclat_opt algorithm, the original Eclat algorithm （ZAKI） and two other improved Eclat algorithms Diffset（ZAKI）, hEclat （XIONG Zhong-yang） showed that the efficiency of the Eclat_opt algorithm ranked the first among the four algorithms on sparse datasets, and its overall time performance was the best.