反频繁集挖掘可计算复杂性问题研究 |
| |
引用本文: | 吕品,陈年生,董武世.反频繁集挖掘可计算复杂性问题研究[J].微机发展,2006,16(4):25-27. |
| |
作者姓名: | 吕品 陈年生 董武世 |
| |
作者单位: | 武汉工程大学计算机科学与工程学院 湖北武汉430073(吕品),湖北师范学院计算机系 湖北黄石435002(陈年生,董武世) |
| |
基金项目: | 湖北省自然科学基金资助项目(2004ADA023) |
| |
摘 要: | 频繁集挖掘是总结二进制数据的重要技术,但如何找到一个二进制数据集与频繁集挖掘结果相一致却十分困难。文中从可计算复杂度的观点研究了频繁集的隐私保持。特别分析了反频繁挖掘问题的可计算复杂度。给出了决定是否存在与一个已知频繁集兼容的数据集是一个NP难度问题;当原始数据集d由6个集合组成时计算与已知频繁集兼容的数据集的数量是一个P类完全问题。
|
关 键 词: | 反频繁集挖掘 隐私保持 投影 |
文章编号: | 1005-3751(2006)04-0025-03 |
修稿时间: | 2005年8月8日 |
Study of Computational
Complexity on Inverse Frequent Set Mining |
| |
Abstract: | Frequent set mining is a well-known technique to summarize 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. |
| |
Keywords: | inverse frequent set mining preserve privacy projection |
本文献已被 CNKI 等数据库收录! |