近似反频繁集挖掘可计算复杂度分析与研究

数据挖掘作为应用于数据分析的工具,往往会从大型数据库中毫无保留地揭露某些重要信息,这些重要信息由于一定的原因不能向外界透露。所以可以通过构造具有与原始的频繁集一样的特征的虚拟数据集来替代频繁集挖掘结果。文章给出了一种近似的反频繁集挖掘方法,分析了它的可计算复杂度,得出了近似反频繁集挖掘是一个NP完全问题,提出了近似的反频繁集挖掘的下一步研究重点。

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

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