提高Eclat算法效率的策略

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

Strategies of efficiency improvement for Eclat algorithm

For the purpose of efficiency improvement, Eclat algorithm was optimized in three aspects-pruning, itemsets connection and intersection. Firstly, the equivalence classes were divided in the suffix-based 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.