关联规则挖掘算法的研究与改进

武汉理工大学

硕士学位论文

关联规则挖掘算法的研究与改进

姓名：周文秀

申请学位级别：硕士

专业：应用数学

指导教师：王仲君

20081201武汉理工大学硕士学位论文

摘要

随着数据库技术的日益成熟和管理信息系统的广泛普及，人类积累的数据量正在以指数级的速度增长。面临浩渺无际的数据，人们渴望得到从数据中来一个去粗存精、去伪存真的技术。数据挖掘便应运而生了。数据挖掘是从数据中析取、识别和发现潜在正确和有用、前所未知的、最终可理解的知识（规则或模型）的过程。

关联规则挖掘是数据挖掘中最活跃的研究方法之一。它是由Ａｇｒａｗａｌ于１９９３年提出的。关联规则挖掘用于发现交易数据库中不同项目集之间的关系。关联规则的算法可按照需不需要产生候选项集的做法分为两类，以ＦＰ（频繁模式）树法与类Ａ研。一方法为代表。此二者最主要的差异在于，ＦＰ树法并不产生候选项集，后者是需要产生候选项集的方法。本文在数据挖掘研究的基础上深入研究了关联规则挖掘，着重对经典关联规则算法中的Ａ研ｏｒｉ算法进行了深入研究，对它的性能进行了分析，根据它的不足之处提出了两个新的改进算法。论文的主要内容如下：１）对数据挖掘的定义、过程、技术分类以及发展趋势进行了综述。２）对关联规则挖掘的定义，性质、挖掘过程、挖掘算法以及研究现状进行

了综述。３）对经典的关联规则算法Ａｐｆｉｏｒｉ算法进行了详细的介绍，并分析了它的特点，同时还介绍了该算法的一些改进算法。４）根据ｏｐ．Ａ研ｏｒｉ算法的特点，提出了Ｏｍ．Ａｐｒｉｏｒｉ算法；根据ＭＡｐｒｉｏｒｉ算法的特点，提出了ＳＭＡｐｒｉｏｒｉ算法。

本文的主要创新点如下：１）根据ｏｐ．Ａｐ订ｏｄ算法的特点，提出了Ｏｍ．Ａｐｒｉｏｆｉ算法，用ＭＡＴ算法来改进０ｐ—Ａｐｒｉｏｒｉ算法中前两项频繁项集的生成，用文献［３４］中的方法来改进

ｋ（ｋ≥３）一频繁项目集的生成，Ｏｍ．Ａｐｆｉｏｒｉ算法使得算法的效率进一步提高。２）根据ＭＡｐｒｉｏｒｉ算法的特点，提出了ＳＭＡｐｒｉｏｒｉ算法，该算法利用不是所有的项和事务都对产生频繁项集有帮助的性质来缩小布尔矩阵的方法，使得算法的时间复杂度和空间复杂度都有所减少，从而提高了算法的效率。

关键词：数据挖掘，关联规则，Ａ研ｏｒｉ算法，时间复杂性，空间复杂性武汉理工大学硕士学位论文

Ａｂｓｔｒａｃｔ

Ａｓｔｈｅｇｒｏｗｉｎｇｕｐｏｆｄａｔａｂａｓｅｓｔｅｃｈｎｉｑｕｅａｎｄｐｒｅｖａｌｅｎｔｏｆａｄｍｉｎｉｓｔｒａｔｏｒｉｎｆｏｒｍａｔｉｏｎｓｙｓｔｅｍ，ｔｈｅｎｕｍｂｅｒｏｆｕｎｕｓｅｄｄａｔａｈａｓｂｅｅｎｉｎｃｒｅａｓｉｎｇａｔｔｈｅｒａｔｅｏｆ

ｅｘｐｏｎｅｎｔ．Ｉｎｆｒｏｎｔｏｆｌａｒｇｅｎｕｍｂｅｒｏｆｄａｔａ，ｐｅｏｐｌｅｏｆｔｅｎｅｘｐｅｃｔｆｏｒａｔｅｃｈｎｏｌｏｇｙｗｈｉｃｈｅｌｉｍｉｎａｔｅｓｔｈｅｆａｌｓｅｎｕｍｂｅｒｓｂｕｔｒｅｔａｉｎｔｈｅｔｒｕｅｖａｌｕｅｓ．Ｓｏｄａｔａｍｉｎｉｎｇｈａｓｂｅｅｎｐｒｏｐｏｓｅｄ，ｗｈｉｃｈｉｓｔｈｅｃｏｒｅｏｆｋｎｏｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙｉｎｄａｔａｂａｓｅｓ．Ｄａｔａｍｉｎｉｎｇｉｓｔｈｅｐｒｏｃｅｓｓｏｆｅｘｔｒａｃｔｉｎｇ，ｉｄｅｎｔｉｆｙｉｎｇａｎｄｄｉｓｃｏｖｅｒｉｎｇｐｏｔｅｎｔｉａｌｌｙｖａｌｉｄ，ｕｓｅｆｕｌ，ｐｒｅｖｉｏｕｓｌｙｕｎｋｎｏｗｎ，ａｎｄｕｌｔｉｍａｔｅｌｙｕｎｄｅｒｓｔａｎｄａｂｌｅｋｎｏｗｌｅｄｇｅ（ｒｕｌｅｓｏｒｐａｔｔｅｒｎｓ）．

Ｔｈｅｍｉｎｉｎｇｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｉｓｏｎｅｏｆｔｈｅｍｏｓｔａｃｔｉｖｅｒｅｓｅａｒｃｈｅｓｉｎｄａｔａｍｉｎｉｎｇ．ＩｔＷａＳｐｒｏｐｏｓｅｄｂｙＡｇａｗａｌｉｎ１９９３．Ｔｈｅｍｉｎｉｎｇｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｉｓｕｓｅｄｆｏｒ

ｄｉｓｃｏｖｅｒｉｎｇｔｈｅｒｅｌａｔｉｏｎｏｆｄｉｆｆｅｒｅｎｔｉｔｅｍ．ｓｅｔｓｉｎｄａｔａｂａｓｅｓ．Ｔｈｅａｌｇｏｒｉｔｈｍｓｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｆａｌｌｉｎｔｏｔｗｏｃａｔｅｇｏｒｉｅｓａｃｃｏｒｄｉｎｇｔｏｔｈｅｎｅｅｄｓｏｆｐｒｏｄｕｃｉｎｇｃａｎｄｉｄａｔｅｉｔｅｍ。ｓｅｔｓ，ｍａｉｎｌｙＦｒｅｑｕｅｎｔＰａｔｔｅｒｎｔｒｅｅａｎｄＡｐｒｉｏｒｉ＿ｌｉｋｅａｌｇｏｒｉｔｈｍｓ．ＴｈｅｍａｉｎｄｉｆｆｅｒｅｎｃｅｉｓｔｈａｔＦｒｅｑｕｅｎｔＰａｔｔｅｒｎｔｒｅｅｄｏｅｓｎｏｔｐｒｏｄｕｃｅｃａｎｄｉｄａｔｅｉｔｅｍ．ｓｅｔｓ．Ｔｈｅｌａｔｔｅｒｉｓｔｈｅａｌｇｏｒｉｔｈｍｎｅｅｄｓｔｏｐｒｏｄｕｃｅｃａｎｄｉｄａｔｅｉｔｅｍ．ｓｅｔｓ．Ｂｅｂａｓｅｄｏｎｒｅｓｅａｒｃｈｉｎｇｏｆｄａｔａｍｉｎｉｎｇ，ｗｅｄｏｓｏｍｅｄｅｅｐｒｅｓｅａｒｃｈｏｎｔｈｅｍｉｎｉｎｇｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，ｅｍｐｈａｓｉｚｅｏｎＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｉｓａｃｌａｓｓｉｃａｌａｌｇｏｒｉｔｈｍｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｍｉｎｉｎｇ．Ｗｅａｎａｌｙｚｅｉｔ，ｂｒｉｎｇｆｏｒｗａｒｄｉｔｓｓｈｏｒｔａｇｅａｎｄｐｒｏｐｏｓｅｔｗｏｉｍｐｒｏｖｅｍｅｎｔａｌｇｏｒｉｔｈｍｓ．Ｔｈｅｍａｉｎｃｏｎｔｅｎｔａｒｅａｓｆｏｌｌｏｗｓ：１）Ｗｅｄｏａｓｕｍｍａｒｙｔｏｄｅｆｉｎｉｔｉｏｎ、ｐｒｏｃｅｓｓ、ｔｅｃｈｎｉｑｕｅｃｌａｓｓｅｓａｎｄｔｒｅｎｄｏｆＤａｔａＭｉｎｉｎｇ．

２）Ｗｅｄｏａｓｕｍｍａｒｙｔｏｄｅｆｉｎｉｔｉｏｎ、ｐｒｏｐｅｒｔｙ、ｍｉｎｉｎｇｐｒｏｃｅｓｓ、ｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｓａｎｄｐｒｅｓｅｎｔｒｅｓｅａｒｃｈｏｆＡｓｓｏｃｉａｔｉｏｎＲｕｌｅｓＭｉｎｉｎｇ．３）ＷｅｉｎｔｒｏｄｕｃｅｔｈｅｃｌａｓｓｉｃａｌａｓｓｏｃｉａｔｉｏｎｒｕｌｅａｌｇｏｒｉｔｌｌＩ】卜以ｐｒｉｏｒｉｉｎｄｅｔａｉｌ，ｄｏｓｏｍｅ

ａｎａｌｙｓｉｓｏｎｉｔ’Ｓｐｒｏｐｅｒｔｙ，ａｔｔｈｅｓａｍｅｔｉｍｅ，ｉｎｔｒｏｄｕｃｅｓｏｍｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｓｂａｓｅｄ

ｏｎｉｔ．

４）ＷｅｐｒｅｓｅｎｔＯｍ－ＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍａｃｃｏｒｄｉｎｇｔｏＯｐ．Ａｐｒｉｏｒｉ，ａｎｄｐｒｅｓｅｎｔ

ＩＩ武汉理工大学硕士学位论文

ＳＭＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍａｃｃｏｒｄｉｎｇｔｏＭＡｐｒｉｏｒｉ．

ＴｈｅｍａｉｎｉｎｎｏｖａｔｉｏｎｐｏｉｎｔｓｏｆｔｈｉｓＰａｐｅｉ＂ａｒｅａｓｆｏｌｌｏｗｓ：

１）ＷｅｐｒｅｓｅｎｔＯｍ．ＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍａｃｃｏｒｄｉｎｇｔｏｔｈｅｐｒｏｐｅｒｔｉｅｓｏｆＯｐ—Ａｐｒｉｏｒｉ，ｗｈｉｃｈｉｍｐｒｏｖｅｔｈｅｐｒｏｃｅｓｓｏｆｔｈｅｆｉｒｓｔｔｗｏｆｒｅｑｕｅｎｔｉｔｅｍ－ｓｅｔｓｂｙＭＡＴａｌｇｏｒｉｔｈｍ，

ｉｍｐｒｏｖｅｔｈｅｐｒｏｃｅｓｓｏｆｋｆｒｅｑｕｅｎｔｉｔｅｍ—ｓｅｔｓｂｙｔｈｅｍｅｔｈｏｄｉｎｌｉｔｅｒａｔｕｒｅ【３４］，ｗｈｅｒｅ

ｋ≥３；Ｏｍ—ＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｆｕｒｔｈｅｒ．

２）ＷｅｐｒｅｓｅｎｔＳＭＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍａｃｃｏｒｄｉｎｇｔｏｔｈｅｐｒｏｐｅｒｔｉｅｓｏｆＭＡｐｒｉｏｒｉ，ｗｈｉｃｈ

ｍａｋｅｕｓｅｏｆｔｈｅｐｒｏｐｅｒｔｙｏｆｔｈａｔｎｏｔａｌｌｉｔｅｍｓａｎｄａｆｆａｉｒｓａｒｅｕｓｅｆｕｌｆｏｒｐｒｏｄｕｃｉｎｇ

ｆｒｅｑｕｅｎｔｉｔｅｍ－ｓｅｔｓｔｏｓｈｒｉｎｋｔｈｅｍａｔｒｉｘ，ＳＭＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅｔｈｅＭＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｏｎｔｉｍｅｃｏｍｐｌｅｘｉｔｙａｎｄｓｐａｃｅｃｏｍｐｌｅｘｉｔｙ．

Ｋｅｙｗｏｒｄｓ：Ｄａｔａｍｉｎｉｎｇ，Ａｓｓｏｃｉａｔｉｏｎｒｕｌｅ，Ａｐｒｉｏｒｉａｌｇｏｒｉｔｈｍ，Ｔｉｍｅｃｏｍｐｌｅｘｉｔｙ，

Ｓｐａｃｅｃｏｍｐｌｅｘｉｔｙ

ＩＩＩ独创性声明

本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研

究成果。尽我所知，除了文中特另ｔＪＤｉｌ以标注和致谢的地方外，论文中不包含其

他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育

机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何

贡献均已在论文中作了明确的说明并表示了谢意。

关于论文使用授权的说明

本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保

留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或

部分内容，可以采用影印、缩印或其他复制手段保存论文。

（保密的论文在解密后应遵守此规定）

签名：卫卫皇Ｌ笼导师签名：半日期：武汉理工大学硕士学位论文

１．１研究背景第１章绪论

科技的进步，特别是信息产业的发展，把我们带入了一个崭新的信息时代。

随着计算机应用的普及和数据库技术的不断发展，数据库管理系统的应用领域

越来越广泛。条形码和信用卡的普及和使用，进一步加速了商业、金融、保险

等领域的信息化进程。人们已经利用计算机取代了绝大部分手工操作。超级市

场中的交易数据，加油站里的油料购买数据，旅行社中的旅行信息数据等均是

数据库系统的信息来源。最近十几年数据库中存储的数据量急剧增大。例如，

ＮＡＳＡ轨道卫星上的地球观测系统ＥＯＳ每小时会向地面发回５０ＧＢ左右的图像数据；世界上最大的数据仓库之一，美国零售系统Ｗａｌ－Ｍａｒｔ每天会产生２亿左右

的交易数据；人类基因组数据库项目已经搜集了数以ＧＢ计的人类基因编码数据

等。如此多领域的数据各自存放在相应的数据库中，致使数据库的规模日益扩

大，已经达到数十兆字节，有的甚至更大。与此同时，大容量、高速度、低价

格的存储设备也相继问世，管理大量数据的数据库管理系统以及各类数据仓库

已经能够支持存储、检索如此规模的数据。但目前数据库系统所能做到的只是对数据库中已有的数据进行存取，通过这些数据获得的信息量只占整个数据库

信息量的一小部分，因为用来对这些数据进行分析处理的工具很少，而且有局

限性。在信息时代，大量信息在给人们带来方便的同时，也带来了一系列问题，

比如，信息量过大，超过了人们掌握、消化的能力；一些信息真伪难辨，给信息的正确运用带来困难；网络上的信息安全难以保障；信息组织形式的不一致

性，增加了对信息进行有效统一处理的难度等。另一方面，人们意识到隐藏在

这些数据之后的更能深层次、更重要的信息能够描述数据的整体特征，可以预

测发展趋势，这些信息在决策生产过程中具有重要的参考价值。面对海量数据

库和大量繁杂信息，如何才能从中提取出有价值的知识，进一步提高信息的利

用率，由此引发了一个新的研究方向：基于数据库的知识发现（Ｋｎｏｗｌｅｄｇｅ

ＤｉｓｃｏｖｅｒｙｉｎＤａｔａｂａｓｅ）及相关的数据挖掘（ＤａｔａＭｉｎｉｎｇ）理论和技术的研

究。