作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (19): 41-44,48. doi: 10.3969/j.issn.1000-3428.2012.19.010

• 软件技术与数据库 • 上一篇    下一篇

基于排序索引矩阵的频繁项集挖掘算法

荀 娇1,2,徐连诚1,2,杨仁华3   

  1. (1. 山东师范大学信息科学与工程学院,济南 250014; 2. 山东省分布式计算机软件新技术重点实验室,济南 250014;3. 山东省信息中心,济南 250013)
  • 收稿日期:2011-12-06 出版日期:2012-10-05 发布日期:2012-09-29
  • 作者简介:荀 娇(1987-),女,硕士研究生、CCF会员,主研方向:数据挖掘,网络与信息安全;徐连诚,副教授;杨仁华,硕士
  • 基金资助:
    国家自然科学基金资助项目(60873247);山东省自然科学基金资助项目(ZR2011FM030, ZR2012FM038);山东省社会科学规划研究基金资助项目(10BSHJ03);山东省教育厅科技计划基金资助项目(J09LG52)

Frequent Itemsets Mining Algorithm Based on Sorting Index Matrix

XUN Jiao 1,2, XU Lian-cheng 1,2, YANG Ren-hua 3   

  1. (1. School of Information Science and Engineering, Shandong Normal University, Jinan 250014, China; 2. Shandong Provincial Key Laboratory for Distributed Computer Software Novel Technology, Jinan 250014, China; 3. Shandong Province Information Center, Jinan 250013, China)
  • Received:2011-12-06 Online:2012-10-05 Published:2012-09-29

摘要: 针对Apriori算法产生候选项集的问题,提出一种基于排序索引矩阵(SIM)的频繁项集挖掘算法。将频繁1-项集形成的1-项集向量依次与对应矩阵相乘,生成频繁2-项集。从频繁3-项集开始,对每次生成的频繁k-项集建立SIM,借助SIM结构实现项集的跨越式搜索和连接。整个过程只需扫描一次数据库,不会产生候选项集。实验结果表明,该算法能提高频繁项集的挖掘效率。

关键词: 关联规则, 排序索引矩阵, 候选项集, 频繁项集, 跨越式搜索, 数据挖掘

Abstract: Aiming at the problem that Apriori algorithm generates candidate itemsets, this paper presents a frequent itemsets mining algorithm based on Sorting Index Matrix(SIM). The algorithm directly generates frequent 2-itemset through 1-itemset vector and the corresponding matrix multiplication sequentially. From the frequent 3-itemset, it establishes simple SIM for the frequent k-item sets to realize itemsets’ spanning search and connection with the SIM. The whole process just scans the database once, and does not produce candidate itemsets. Experimental result shows that the algorithm improves the efficiency of mining frequent itemsets.

Key words: association rule, Sorting Index Matrix(SIM), candidate itemsets, frequent itemsets, spanning search, data mining

中图分类号: