————————————
作者简介作者简介：：章淑云(1989－)，女，硕士研究生，主研方向：数据仓库，数据挖掘；张守志，副教授。 收稿日期收稿日期：：2012-12-10 修回日期修回日期：：2013-04-07 E-mail ：10210240047@https://www.doczj.com/doc/8517852472.html,
基于不确定性数据的频繁闭项集挖掘算法
章淑云章淑云，，张守志
(复旦大学计算机科学技术学院，上海 200433)
摘 要：对于不确定性数据，传统判断项集是否频繁的方法并不能准确表达项集的频繁性，同样对于大型数据，频繁项集显得庞大和冗余。针对上述不足，在水平挖掘算法Apriori 的基础上，提出一种基于不确定性数据的频繁闭项集挖掘算法UFCIM 。利用置信度概率表达项集频繁的准确性，置信度越高，项集为频繁的准确性也越高，且由于频繁闭项集是频繁项集的一种无损压缩表示，因此利用压缩形式的频繁闭项集替代庞大的频繁项集。实验结果表明，该算法能够快速地挖掘出不确定性数据中的频繁闭项集，在减少项集冗余的同时保证项集的准确性和完整性。
关键词关键词：：不确定性数据；频繁闭项集；数据挖掘；水平挖掘；置信度概率
Mining Algorithm of Frequent Closed Itemsets
Based on Uncertain Data
ZHANG Shu-yun, ZHANG Shou-zhi
(School of Computer Science, Fudan University, Shanghai 200433, China)
【Abstract 】For the uncertain data, traditional method of judging whether an itemset is frequent cannot express how close the estimate is, meanwhile frequent itemsets are large and redundant for large datasets. Regarding to the above two disadvantages, this paper proposes a mining algorithm of frequent closed itemsets based on uncertain data called UFCIM to mine frequent closed itemsets from uncertain data according to frequent itemsets mining method from uncertain data, and it is based on level mining algorithm Apriori. It uses probability of confidence to express how close the estimate is, the larger that probability of confidence is, the itemsets are more likely to be frequent. Besides as frequent closed itemsets are compact and lossless representation of frequent itemsets, so it uses compacted frequent closed itemsets to take place of frequent itemsets which are of huge size. Experimental result shows the UFCIM algorithm can mine frequent closed itemsets effectively and quickly. It can reduce redundancy and meanwhile assure the accuracy and completeness of itemsets. 【Key words 】uncertain data; frequent closed itemsets; data mining; level mining; probability of confidence DOI: 10.3969/j.issn.1000-3428.2014.03.010
计 算 机 工 程 Computer Engineering 第40卷 第3期
V ol.40 No.3 2014年3月
March 2014
·先进计算与数据处理先进计算与数据处理·· 文章编号文章编号：：1000-3428(2014)03-0051-04
文献标识码文献标识码：：A
中图分类号中图分类号：：T P311.12
1 概述
现实应用中经常出现噪声和不完整的数据，比较常见的应用有传感网络[1]和隐私保护[2]等数据挖掘应用，又如医院对于病人的诊断数据也存在许多不确定性因素。因此，如何对这些不确定性数据进行分析和挖掘成为了数据挖掘中的一个重要研究领域。
近年来，有许多关于不确定性数据的频繁模式挖掘的研究，其中有U-Apriori 算法[3]、UF-tree 算法[4]、UD-FP-tree 算法[5]、U-Eclat 算法[6]等，但其均采用项集概率分布的期望值定义频繁项集，即将期望支持度大于等于最小支持度阈值的项集定义为频繁项集。但这种对支持度的估计方法并未表示出其所估计的准确度，因此本文采用文献[7]提出的概率频繁项集定义，定义了项集的支持度分布，并用大于
等于最小支持度阈值的支持度概率总和定义项集的频繁概率。传统意义上频繁闭项集是对频繁项集的一种压缩无损表示，从文献[7]中的概率频繁项集出发，文献[8]对概率频繁闭项集作出了进一步阐述，定义了项集概率支持度的最大频繁度，并用概率支持度定义频繁闭项集。本文从概率频繁项集和概率频繁闭项集出发，利用可能性世界模型表示不确定性数据库，根据概率频繁闭项集的定义，提出一种在不确定性数据中进行频繁闭项集挖掘的算法UFCIM (Uncertain Frequent Closed Itemsets Mining)。
2 相关知识
对于不确定性数据以及可能性世界模型，不同的文献给出了类似的定义[9-11]。
本文采用文献[7]中的概率矩阵表示不确定性数据库。项集I ={x 1,x 2,…,x m }，事务集合T ={t 1,