[1]吕品 陈年生 董武世.反频繁集挖掘可计算复杂性问题研究[J].计算机技术与发展,2006,(04):25-27.
　Lu Pin,CHEN Nian-sheng,DONG Wu-shi.Study of Computational Complexity on Inverse Frequent Set Mining[J].,2006,(04):25-27.
点击复制

反频繁集挖掘可计算复杂性问题研究()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2006年04期
页码:
25-27
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Study of Computational Complexity on Inverse Frequent Set Mining
文章编号:
1005-3751（2006）04-0025-03
作者:
吕品1 陈年生2 董武世2
[1]武汉工程大学计算机科学与工程学院[2]湖北师范学院计算机系
Author(s):
Lu Pin;  CHEN Nian-sheng;  DONG Wu-shi
[1]School of Computer Science, Wuhan University of Technology[2]Department of Computer Science, Hubei Normal University
关键词:
反频繁集挖掘; 隐私保持; 投影
Keywords:
inverse frequent set mining;  preserve privacy;  projection
分类号:
TP301.5
文献标志码:
A
摘要:
频繁集挖掘是总结二进制数据的重要技术，但如何找到一个二进制数据集与频繁集挖掘结果相一致却十分困难。文中从可计算复杂度的观点研究了频繁集的隐私保持。特别分析了反频繁挖掘问题的可计算复杂度。给出了决定是否存在与一个已知频繁集兼容的数据集是一个NP难度问题；当原始数据集d由6个集合组成时计算与已知频繁集兼容的数据集的数量是一个p类完全问题
Abstract:
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

相似文献/References:

[1]吕品 陈年生 董武世.面向隐私保护的数据挖掘技术研究[J].计算机技术与发展,2006,(07):147.
　Lü Pin,CFIEN Nian-sheng,DONG Wu-shi.Study of Data Mining Technique of Privacy Preserving[J].,2006,(04):147.

备注/Memo

备注/Memo:
湖北省自然科学基金资助项目（2004ADA023）吕品（1973-），女，湖北鄂州人，硕士，讲师，研究方向为数据挖掘、算法分析与设计、软件工程；董武世，副教授，研究方向为数据库、高性能计算机网络
更新日期/Last Update: 1900-01-01