%0 Journal Article
%T 基于开项集剪枝的常量条件函数依赖挖掘<br>Mining of constant conditional functional dependencies based on pruning free itemsets
%A 周金陵
%A 刁兴春
%A 曹建军
%J 清华大学学报（自然科学版）
%D 2016
%R 10.16511/j.cnki.qhdxxb.2016.21.026
%X 为了减小常量条件函数依赖的搜索空间, 提高挖掘效率, 针对常量条件函数依赖挖掘算法CFDMiner, 提出了一系列剪枝优化策略。理论研究发现, CFDMiner的输入——关系数据的全部开项集和闭项集对产生有效的常量条件函数依赖仍然存在很多无效、冗余的项集。从理论上证明了通过合理剪枝, 选取开项集的子集与对应的闭项集, 能够得到与原算法一致的结果。实验表明: 相比原始算法CFDMiner, 优化后的算法搜索空间更小, 实际数据集上平均挖掘效率提高4~5倍。<br>Abstract：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~5 fold on true data.
%K 条件函数依赖
%K 函数依赖
%K 开项集
%K 闭项集
%K 剪枝
%K &lt
%K br&gt
%K conditional functional dependency
%K functional dependency
%K free itemset
%K closed itemset
%K pruning algorithm
%U http://jst.tsinghuajournals.com/CN/Y2016/V56/I3/253