反频繁集挖掘可计算复杂性问题研究

Study of Computational Complexity on Inverse Frequent Set Mining

频繁集挖掘是总结二进制数据的重要技术,但如何找到一个二进制数据集与频繁集挖掘结果相一致却十分困难。文中从可计算复杂度的观点研究了频繁集的隐私保持。特别分析了反频繁挖掘问题的可计算复杂度。给出了决定是否存在与一个已知频繁集兼容的数据集是一个NP难度问题;当原始数据集d由6个集合组成时计算与已知频繁集兼容的数据集的数量是一个P类完全问题。

Frequent set mining is a well known technique to summartize binary data. However, it is difficult to find a binary data set that is compatible with frequent set mining results. The paper studies the frequent sets preserve privacy from the viewpoint of computational complexity, and specially analyzes the computational complexity of inverse frequent set mining. The paper forwards that deciding whether there is a data set compatible with the given frequent sets is NP- hard and computing the number of data sets compatible with the given frequent sets is P- hard even in the case when the original data set d consists of six sets.