基于开项集剪枝的常量条件函数依赖挖掘

Mining of constant conditional functional dependencies based on pruning free itemsets

为了减小常量条件函数依赖的搜索空间,提高挖掘效率,针对常量条件函数依赖挖掘算法CFDMiner,提出了一系列剪枝优化策略。理论研究发现,CFDMiner的输入——关系数据的全部开项集和闭项集对产生有效的常量条件函数依赖仍然存在很多无效、冗余的项集。从理论上证明了通过合理剪枝,选取开项集的子集与对应的闭项集,能够得到与原算法一致的结果。实验表明：相比原始算法CFDMiner,优化后的算法搜索空间更小,实际数据集上平均挖掘效率提高4~5倍。

The search space for discovering constant conditional functional dependencies（CCFDs）is reduced and the efficiency is improved by a series of pruning strategies that optimize the algorithm CFDMiner,which is a popular algorithm for mining CCFDs.Theoretical studies show many invalid and redundant free and closed itemsets for outputting valid CCFDs.Thus,pruning of free itemsets and selecting of corresponding closed itemsets can generate as consistent results as the original algorithm.Tests show that the optimized algorithm has a smaller search space and its efficiency is improved 4~5fold on true data.