基于邻接比特压缩表的频繁闭项集挖掘算法

频繁闭项集(Frequent Closed Items,FCI)是一种表示事物之间关联关系的有效方式,它能克服频繁项集(Frequent Items,FI)信息冗余的缺点。FCI挖掘算法研究旨在以更优的时空效率,在原始数据集中找到所有的FCI。相关研究成果重在关注时间效率的提升,但空间效率欠佳。提出一种高空间压缩率数据结构——邻接比特压缩表(Compressed Adjacency Byte table,Cab-table),将项集与交易集压缩到剔除全部0之后的比特表中,使空间高度压缩。基于此数据结构的频繁闭项集挖掘算法(Cab-Miner),采用运算栈与检索栈来实现非递归方式的频繁闭项集挖掘,相较于之前普遍采用递归方式的算法,在理论上可使空间占用率由O(L*N+M)降为O(3N)。基于公开数据集与真实数据集的实验表明,上述算法在原始数据集压缩,以及运算内存消耗上,都有较优的表现,尤其在处理真实数据集时,空间表现极佳。另外在某些属性的数据集上也表现出优越的时间效率。