基于关联规则的数据挖掘算法研究

基于关联规则的数据挖掘算法研究

北京工业大学硕士学位论文

基于关联规则的数据挖掘算法研究

姓名：安颖申请学位级别：硕士专业：计算机应用技术指导教师：毛国君

20090201

基于关联规则的数据挖掘算法研究

摘要

摘要

数据挖掘是当今人工智能和数据库研究方面最富活力的领域。关联规则是数据挖掘的一个主要研究内容。关联规则描述了给定数据项集之间的有趣联系。目前，已经提出了许多挖掘关联规则的算法，其中最著名的是Ａｐｒｉｏｒｉ算法及其变形。针对Ａｐｆｉｏｆｉ算法中频繁项集产生效率低和产生无用规则、丢失有用规则两个核心问题，本文提出了两种改进的Ａｐｆｉｏｆｉ算法，它们能有效提高频繁集的产生效率和产生更为合理的关联规则。本文主要工作包括以下几个方面。

１、本文首先概述了数据挖掘理论和发展，以及主要的数据挖掘技术；然后研究了关联规则挖掘的步骤。对经典的Ａｐｒｉｏｒｉ算法做了全面的分析并指出算法的不足。

２、

针对Ａｐｒｉｏｒｉ算法的不足，提出了一种基于事务标号集的Ａｐｒｉｏｒｉ改进

ｏｎ

算法——ＢＴＡ（Ｂａｓｅｄ

ＴＩＤｓｅｔｓ

Ａｐｒｉｏｒｉ）算法。ＢＴＡ算法的特点在于：在首次扫描

数据库生成候选卜项集的同时，记住包含每一个项集的事务标识符ＴＩＤ集合。这样，只要统计候选项集所对应的ＴＩＤ集合的元素个数，就可以得到该候选项集的支持度计数，从而找到频繁项集。生成下一级候选项集时，只需将用于相连接的两个频繁项集的ＴＩＤ集合相交，就得到了该候选项集的ＴＩＤ集合。依次类推，直到找到所有的频繁项集。与Ａｐｒｉｏｒｉ算法不同的是，ＢＴＡ算法只在产生候选卜项集时需要遍历一次数据库，其他候选项集的支持度计算只需统计相应ＴＩＤ集合的元素个数即可，而不必象Ａｐｆｉｏｆｉ算法那样反复地遍历数据库，从而大大节省了运行时间。相同条件下的实验结果表明，优化后的算法能有效地提高关联规则挖掘的效率。

３、Ａｐｆｉｏｆｉ算法认为每个数据对规则的重要性相同。但在实际应用中，用户会比较倾向于自己最感兴趣或认为最重要的那部分项目，因此有必要加强这些项

目对规则的影响。为此，论文提出了一种基于兴趣集和权值的挖掘算法——

ＩＷＡ（Ｉｎｔｅｒｅｓｔｓｅｔ

库中找出与该项目相关联的项目组成兴趣项扩展集，后面的挖掘工作将针对该项目集进行。这样，利用用户的约束有效地缩小了挖掘范围。其次，通过给每个项目赋予不同的权值来标识数据库中项目不同的重要性，使算法更切合现实，从而发现用户需要的关联规则。

关键词数据挖掘；关联规则；Ａｐｆｉｏｆｉ算法；算法改进；加权

基于关联规则的数据挖掘算法研究

曼曼！！詈曼！曼皇詈鼍！皇！皇詈鼍Ｉｌｌ——．

一

Ａｂｓｔｒａｃｔ

ｍ．

．

；。！！鼍！！暑！曼詈！苎皇曼皇皇曼詈鼍皇曼曼曼皇！曼！曼暑曼皇詈曼詈曼曹

Ａｂｓｔｒａｃｔ

ＤａｔａＭｉｎｉｎｇｉｓ

ｏｆｔｈｅｍｏｓｔａｃｔｉｖｅｒｅｓｅａｒｃｈｆｉｅｌｄｓ，ｅｓｐｅｃｉａｌｌｙｉｎｔｈｅｆｉｅｌｄｓｏｆ

ａ

ｏｎｅ

ａｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｇｅｎｃｅａｎｄｄａｔａｂａｓｅ．Ｔｈｅａｓｓｏｃｉａｔｉｏｎｒｕｌｅｍｉｎｉｎｇｉｓ

ｍａｉｎｒｅｓｅａｒｃｈ

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

ｂｅｅｎｂｒｏｕｇｈｔｆｏｒｗａｒｄ．Ｔｈｅｍｏｓｔｆａｍｏｕｓａｌｇｏｒｉｇｈｍｓ

ａｒｅ

Ａｐｒｉｏｒｉａｎｄｉｔｓｔｒａｎｓｆｉｇｕｒａｔｉｏｎ．

Ｉｎｔｈｉｓｐａｐｅｒ，ＩｐｒｅｓｅｎｔｔｗｏｉｍｐｒｏｖｅｄＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｓａｉｍａｔｌｏｗ

ｅｆｆｉｃｉｅｎｃｙｏｆ

ｏｎ

ｍｉｎｉｎｇｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓａｎｄｃｒｅａｔｉｎｇｕｓｅｌｅｓｓｒｕｌｅｓ，ｌｏｓｉｎｇｕｓｅｆｕｌｒｕｌｅｓ．Ｂａｓｅ

ｍｙ

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

１、Ｔｈｉｓｔｈｅｓｉｓｆｉｒｓｔｓｕｍｍａｒｉｚｅｓｄａｔａｍｉｎｉｎｇｔｈｅｏｒｙ，ｉｔｓｅｖｏｌｕｔｉｏｎａｎｄｉｔｓｐｒｉｍａｒｙｄａｔａｍｉｎｉｎｇｔｅｃｈｎｏｌｏｇｙ；Ｔｈｅｎｔｈｅｓｔｅｐｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｍｉｎｉｎｇｉｓｓｔｕｄｉｅｄ．Ａｎｏｖｅｒａｌｌ

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

ｉｓｐｏｉｎｔｅｄ

ｏｕｔ．

２、ＡｎｉｍｐｒｏｖｅｄＡｐｒｉｏｒｉ

ａｌｇｏｒｉｔｈｍ

ｂａｓｅｄ

Ｃａｌｌ

ｏｎ

ＴＩＤｓｅｔｓ，ＢＴＡ（Ｂａｓｅｄ

ｏｎ

ＴＩＤｓｅｔｓ

Ａｐｒｉｏｒｉ），ｉｓ

ｐｕｔ

ｆｏｒｗａｒｄ

ｉｎｔｈｉｓｐａｐｅｒ，ｗｈｉｃｈｍａｋｅｕｐｔｈｅａｂｏｖｅ—ｍｅｎｔｉｏｎｅｄｆｌａｗｏｆ

ｌｉｅｓｉｎ：ＴｈｅＴＩＤｓｅｔｓｈａｖｅｂｅｅｎ

Ａｐｒｉｏｒｉｖｅｒｙｗｅｌｌ．ＢＴＡａｌｇｏｒｉｔｈｍｃｈａｒａｃｔｅｒｉｓｔｉｃ

ｒｅｃｏｒｄｅｄｗｈｉｌｅｓｃａｎｎｉｎｇｔｈｅｄａｔａｂａｓｅ

ｃｏｕｎｔ

ｔｏ

ｇｅｎｅｒａｔｅｃａｎｄｉｄａｔｅ－１

ｉｔｅｍｓｅｔｓ．Ｔｈｕｓ，ｔｈｅ

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

ｎｅｘｔｒａｎｋｏｆｃａｎｄｉｄａｔｅ

ｃｏｒｒｅｓｐｏｎｄｉｎｇＴＩＤｓｅｔｓ．ＴｈｅＴＩＤｓｅｔｓｏｆｔｈｅ

ｉｔｅｍｓｅｔｓ

ａｒｅ

ｇｏｔ

ｏｎｌｙｂｙｉｎｔｅｒｓｅｃｔｉｎｇｔｈｅＴＩＤｓｅｔｓｏｆｔｈｅｔｗｏｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓｗｈｉｃｈａｒｅｕｓｅｄ

ｌｉｎｋｅｄ．Ｔｈｅ

ｒｅｓｔ

ｔｏｂｅ

ａｒｅ

ｍａｙ

ｂｅ

ｄｅｄｕｃｅｄ

ｂｙ

ａｎａｌｏｇｙ，ｕｎｔｉｌ

ｏｎｅ

ａｌｌ

ｆｒｅｑｕｅｎｔ

ｉｔｅｍｓｅｔｓ

ｃｏｕｎｔ

ｆｏｕｎｄ．ＤｉｆｆｅｒｉｎｇｆｒｏｍＡｐｒｉｏｒｉ，ＢＴＡｎｅｅｄｓｏｎｌｙｃａｎｄｉｄａｔｅ

ｉｔｅｍｓｅｔｓ

ｍｅｍｂｅｒｓ

ｉｓ

ａｄｄｅｄｆｏｒ

ｔｈｅ

ｕｐ

ｄａｔａｂａｓｅｓｃａｎ，ａｎｄｔｈｅｂｙ

ｃｏｕｎｔｉｎｇ

ｔｏ

ｏｆｏｆ

ｏｎｌｙ

ｔｈｅｎｕｍｂｅｒ

ｃｏｒｒｅｓｐｏｎｄｉｎｇＴＩＤｓｅｔｓ，ｅｘｃｅｐｔ

ｆｉｒｓｔｔｉｍｅ

ｓｃａｎｃｒｅａｔｅ

ｃａｎｄｉｄａｔｅ一１

ｉｔｅｍｓｅｔｓ．Ｔｈｕｓ，ｔｈｅ

ｅｆｆｉｃｉｅｎｃｙ

ｔｉｍｅｓｐｅｎｄｉｎｇｉｓｃｕｔｄｏｗｎｇｒｅａｔｌｙ．Ｕｎｄｅｒｔｈｅ

ｓａｍｅｃｏｎｄｉｔｉｏｎｓ，ｔｈｅ

ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｏｐｔｉｍｉｚｅｄ

ｏｆｍｉｎｉｎｇａｓｓｏｃｉａｔｉｏｎ

ａｌｇｏｒｉｔｈｍ

ｃａｎ

ｅｆｆｅｃｔｉｖｅｌｙｉｍｐｒｏｖｅｔｈｅ

ｒｕｌｅｓ．

ａＳ

３、Ａｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｔｒｅａｔｓｅａｃｈｉｔｅｍ

ｕｓｅｒｓ

ｕｎｉｆｏｒｍｉｔｙ．Ｈｏｗｅｖｅｒｉｎｒｅａｌａｐｐｌｉｃａｔｉｏｎｓ，

ａｒｅ

ａｒｅｍｏｒｅｉｎｃｌｉｎｅｄ

ｔｏ

ｓｕｃｈｉｔｅｍｓａｓｔｈｅｙ

ｔｏ

ｏｎｅ

ｍｏｓｔｉｎｔｅｒｅｓｔｅｄｉｎ

ｏｒ

ｆｅｅｌｍｏｓｔ

ｔｏ

ｉｍｐｏｒｔａｎｔａｂｏｕｔ．Ｓｏ，ｉｔ’Ｓｎｅｃｅｓｓａｒｙｒｕｌｅｓ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓ

ｅｍｐｈａｓｉｚｅｔｈｅａｆｆｅｃｔｉｏｎｏｆｓｕｃｈｉｔｅｍｓ

ｋｉｎｄｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄ

ｕｓｅｒｓ

ｏｎ

ｉｎｔｅｒｅｓｔｓｅｔｓ

ａｎｄｗｅｉｇｈｔ，ＩＷＡ（Ｉｎｔｅｒｅｓｔｓｅｔ－ｗｅｉｇｈｔＡｐｒｉｏｒｉ）．Ｆｉｒｓｔｌｙ，ｔｈｅ

．１１１．．

ｐｒｏｐｏｓｅｔｈｅｉｔｅｍ

基于关联规则的数据挖掘算法研究

北京Ｔ业大学Ｔ学硕ｌ？学位论文

ｗｈｉｃｈｔｈｅｙ

ａｒｅ

ｉｎｔｅｒｅｓｔｅｄｉｎ．ｔｈｅｎｆｉｎｄ

ｏｕｔｔｈｅｉｔｅｍｓｒｅｌａｔｅｄｔｏｉｔ

ｆｒｏｍｔｈｅｄａｔａｂａｓｅ

ｔｏ

ｃｏｍｐｏｓｅｅｘｐａｎｓｉｏｎ

ｓｅｔｓ

ｏｆｔｈｅｉｎｔｅｒｅｓｔｅｄ

ｉｔｅｍ，ｔｈｅ

ｆｏｌｌｏｗｉｎｇ

ｍｉｎｉｎｇｗｏｒｋ

ｉｓ

ｐｒｏｃｅｓｓｅｄａｇａｉｎｓｔｔｈｅｉｔｅｍｓｅｔｓ．Ｔｈｕｓ，ｉｔＣａｎｒｅｄｕｃｅｔｈｅｍｉｎｉｎｇｓｃｏｐｅｅｆｆｅｃｔｉｖｅｌｙｕｓｉｎｇ

ｕｓｅｒ’ｓ

ｃｏｎｓｔｒａｉｎｔ．Ｓｅｃｏｎｄｌｙ，ｉｎｏｒｄｅｒｔｏｍａｋｅｔｈｅａｌｇｏｒｉｔｈｍｃｏｒｒｅｓｐｏｎｄｗｉｔｈｔｈｅｒｅａｌｉｔｙ，

ｗｅｏｆｆｅｒｅａｃｈｉｔｅｍ

ａ

ｄｉｆｆｅｒｅｎｔｗｅｉｇｈｔｖａｌｕｅ

ＳＯ

ｔｈａｔｉｔ

Ｃａｎ

ｒｅｐｒｅｓｅｎｔｔｈｅｉｍｐｏｒｔａｎｃｅｏｆ

ｉｎｄｉｖｉｄｕａｌｉｔｅｍｓｆｒｏｍｄａｔａｂａｓｅｓ．Ｉｎｔｈｉｓｗａｙ，ｗｅｍａｙｄｉｓｃｏｖｅｒｔｈｅｕｓｅｆｕｌａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓｆｏｒ

ｕｓｅｒｓ．

ＫｏｗｏｒｄｓＤａｔａＭｉｎｉｎｇ；Ａｓｓｏｃｉａｔｉｏｎ

ｒｕｌｅｓ；Ａｐｒｉｏｒｉ；Ａｌｇｏｒｉｔｈｍｉｍｐｒｏｖｅｍｅｎｔ；Ｗｅｉｇｈｔ

．ＩＶ．

基于关联规则的数据挖掘算法研究

独创性声明

本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。

关于论文使用授权的说明

本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。

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

签名：专颏

导师签名：二鲤日期：

基于关联规则的数据挖掘算法研究

第１奄

绪论

第１章

绪

论

１．１数据挖掘产生与发展

科技的进步，特别是信息产业的发展，把我们带入了一个崭新的信息时代。随着计算机应用的普及和数据库技术的不断发展，数据库管理系统的应用领域越来越广泛。大量的数据被搜集和存储在各种数据库中，并成指数性增长。让我们来看～些身边俯拾即是的现象：ＷａｌＭａｒｔ公司（美国最大的零售连锁店）每天产生两千万个事务；又如美国航天局１９９９年发射的地球观测系统每天要产生１２００Ｇｂ的图像数据；还有生物学领域中数以百万计的遗传基因，世界各国定期进行的人口普查，国土资源地理信息，铁路动态调度控制，公安司法部门的案件处理等等都是海量数据。但是对如此众多的数据的利用还主要是检索查询，效率很低，而且相当数量的数据具有很强的时效性，往往很多数据还没来得及分析就已经过时，数据的价值没有得到充分利用【ｌ】。

面对数据的急剧膨胀和高度时效性，一方面，人们苦于不能及时得到科学决策所必须的可靠知识，另一方面，大量宝贵的数据资源甚至还没有得到利用就已经过时，这导致了一个新的问题，即所谓的“数据丰富，知识贫乏”问题，结果是数据库往往变成了“数据的坟墓”，很少被人访问，决策更多地不是依赖信息，而是依赖决策者的直觉。“我们淹没在信息之中，但仍处于知识的饥渴中＂ＪｏｈｅＮａｉｓｂｅｔｔ说。我们迫切需要研究新一代数据处理技术，以提高数据的利用率。数据挖掘技术就是在这样的背景下产生的。它的宗旨就是分析处理海量数据，以发现有用的知识，为用户提供所需问题的答案，将“数据的坟墓”变成隐藏着知识的“金矿”。

数据挖掘技术的产生也不是一蹴而就的，它的产生和发展其实是一个逐渐演

变的过程。电子数据处理的初期，人们就试图通过某些方法来实现自动决策支持，当时机器学习成为人们关注的焦点。机器学习的过程就是将一些已知的并已被成功解决的问题作为范例输入计算机，机器通过学习这些范例总结并生成相应的规则，这些规则具有通用性，使用它们可以解决某一类的问题。随后，由于神经网

络技术的形成和发展，人们的注意力转向知识工程，知识工程不同于机器学习之处就是直接给计算机输入已被代码化的规则，专家系统就是这种方法所得到的成果，但由于它投资大、效果不甚理想。８０年代人们又在新的神经网络理论的指

导下，重新回到机器学习的方法上，并将其成果应用于处理海量商业数据。直到

１９８９年在美国底特律举行了第十一届国际人工智能学术会议，在这次会议上定

基于关联规则的数据挖掘算法研究

北京Ｔ一业大学］二学坝ｉ：掌佗论文

义了一个新的术语，它就是数据库中的知识发现（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙｉｎ

Ｄａｔａｂａｓｅ），简称ＫＤＤ。人们接受了这个术语，并用ＫＤＤ来描述整个发现知识的过程，包括最开始的制定业务目标到最终的结果分析，而用数据挖掘（ＤａｔａＭｉｎｉｎｇ，ＤＭ）来描述使用挖掘方法进行数据挖掘的子过程。随后，知识发现与数据挖掘流行起来了，大量学者及产业界参与进来，取得长足的进展。数据挖掘是一个众多学科诸如人工智能、机器学习、模式识别、统计学、数据库和知识库、数据可视化等相互交叉、融合所形成的一个新兴的且具有广阔前景的领域。从数据库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许多方面【２】１３］【４】。

所以，数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。从早期的数据搜索到现在的数据挖掘大约可以分为四个阶段，如表１．１【５１所示：

表１．１

数据挖掘的进化历程

Ｔａｂｌｅ１－１ＴｈｅｅｖｏｌｕｔｉｏｎｏｆＤａｔａＭｉｎｉｎｇ

发展阶段数据搜索（６０年代）

提出问题

“在过去五年中我的总收入是多少？

支持技术计算机，磁带和

产品厂家产品特点提供历史性

ＩＢＭ，ＣＤＣ

磁盘

据信息

关系数据库

Ｏｒａｃｌｅ，

的、静态的数

数据访问（８０年代）

在记录级提供

“在上海地区去年三月份销售额是多少？

（ＲＤＢＭＳ），结构化查询语言（ＳＱＬ），ＯＤＢＣ

“在上海地区去年三月

数据仓库，

份销售额是多少？老板

决策支持（９０年代）

么结论？”

库

高级算法、多处

数据挖掘（正在流行）

“下个月上海地区销售

理器计算机、海

额是多少？为什么？”

量数据库

其他初创公司

ＳＧＩＳｙｂａｓｅ，Ｉｎｆｏｒｍｉｘ，

历史性的、动态的数据信息

ＩＢＭ．Ｍｉｃｒｏｓｏｆｔ

Ｐｉｌｏｔ，

联机分析处理（ＯＬＡＰ），多维数据库、数据仓

在各层次上回

Ｃｏｍｓｈａｒｅ，

溯的、动态的

根据此数据可以得出什

Ａｒｂｏｔ，Ｃｏｇｎｏｓ，

数据信息

Ｍｉｃｒｏｓｔｒａｔｅｇｙ

Ｐｉｌｏｔ，

Ｌｏｃｋｈｅｅｄ，ＩＢＭ

提供预测性的信息

从表中我们可以看到，第四步进化是革命性的，因为从用户的角度来看，这

一阶段的数据库技术已经可以快速地回答商业上的很多问题了。

１．２传统分析方法与数据挖掘的区别

传统分析方法包括查询、报表、联机应用分析等，它与数据挖掘的本质区别

基于关联规则的数据挖掘算法研究

第１荦

绪论

是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先前未知性、有效性和可实用性三个特征。先前未知性是指挖掘出的信息是预先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识。挖掘出的信息越是出乎意料，就可能越有价值。在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布

和啤酒之间有着惊人的联系。有效性是指挖掘出的信息必须是有效信息，无效信

息对我们是没有任何价值的。可实用性是指挖掘出的信息必须能应用于实际的操作，指导实际的决策。

１．３数据挖掘的研究现状

从出现数据挖掘至今，由美国人工智能协会主办的ＫＤＤ国际研讨会已经召开了１８次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论，甚至到了脍炙人口的程度。

除此之外，在Ｉｎｔｅｍｅｔ上还有不少ＫＤＤ电子出版物，其中以半月刊Ｋｎｏｗｌｅｄｇｅ

Ｄｉｓｃｏｖｅｒｙ

Ｎｕｇｇｅｔｓ最为权威（ｈｔｔｐ：／／ｗｗｗ．ｋｄｎｕｇｇｅｔｓ．ｃｏｒｎ／ｓｕｂｓｃｒｉｂｅ．ｈｔｍｌ）。在网上

Ｅｍａｉｌ

还有许多自由论坛，如ＤＭ

Ｋｎｏｗｌｅｄｇｅ

Ｃｌｕｂ等。至于ＤＭＫＤ（ＤａｔａＭｉｎｉｎｇ

ａｎｄ

Ｄｉｓｃｏｖｅｒｙ）书籍，可以在任意一家计算机书店找到十多本。目前，世

界上比较有影响的典型数据挖掘系统有：ＳＡＳ公司的ＥｎｔｅｒｐｒｉｓｅＭｉｎｅｒ、ＩＢＭ公司的ＩｎｔｅｌｌｉｇｅｎｔＭｉｎｅｒ、ＳＧＩ公司的ＳｅｔＭｉｎｅｒ、ＳＰＳＳ公司的Ｃｌｅｍｅｎｔｉｎｅ、Ｓｙｂａｓｅ公司的ＷａｒｅｈｏｕｓｅＳｔｕｄｉｏ、ＲｕｌｅＱｕｅｓｔＲｅｓｅａｒｃｈ公司的Ｓｅｅ５、还有ＣｏｖｅｒＳｔｏｒｙ、

ＥＸＰＬＯＲＡ、Ｋｎｏｗｌｅｄｇｅ

Ｄｉｓｃｏｖｅｒｙ

Ｗｏｒｋｂｅｎｃｈ、ＤＢＭｉｎｅｒ、Ｑｕｅｓｔ等。

ｈｔｔｐ：／／ｗｗｗ．ｄａｔａｍｉｎｉｎｇｌａｂ．ｃｏｍ网站为用户提供了许多数据挖掘系统和工具的性能测试报告。

我国的数据挖掘研究开始于９０年代中期，到９０年代中后期，初步形成了知

识发现和数据挖掘的的基本框架。自９０年代中期一批研究成果（学术论文）逐渐发表《计算机学报》、《计算机研究与发展》、《软件学报》、《人工智能与模式识别》等刊物上，研究重点也正在从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。但是基本上还是以学术研究为主，实际应用上处于起步阶段。１９９３年国家自然科学基金首次支持对该领域的研究

项目目前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应

用研究，研究涉及的领域很多，一般集中于算法的研究，数据挖掘的实际应用以及有关数据挖掘理论方面的研究，如北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究；北京大学也在开展对数据立方体代数的研究；华

基于关联规则的数据挖掘算法研究

北京Ｔ业大学Ｔ学硕ｌｊ学位论迂

中科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及Ｗｅｂ挖掘。但是到

目前为止还没有商用工具问世，像复旦大学设计的基于关联规则的数据挖掘工具

ＡＲＭｉｎｅｒ等也只是处于实验室研究阶段。与国外相比，国内对ＤＭＫＤ的研究还

没有形成整体力量【６】ｏ

１．４数据挖掘中的关联规则

数据挖掘可以采用多种技术对数据进行分析处理，其中，关联分析是最重要

的技术之一。关联规则是由ＩＢＭ研究中心的Ｒ．Ａｇｒａｗａｌ等人于９０年代初期提出

的１７１，它主要用来发现数据项之间的关联关系，如购买面包和黄油的人有９０％的

可能性购买牛奶。发现这些项目之间的关联关系，则可以用来指导超市管理人员

的决策，如对于刚才发现的关联规则，超市人员就可以有针对性地进行货物的摆放，可以把面包、黄油和牛奶摆放在一起，或者将面包、黄油和牛奶分别放在货

物架的两端。这样，对于前者，顾客一进入超市，就能很快地购买到他们需要的

东西，为顾客购物提供方便；而对于后者，顾客在购买的过程中会途经一些地方，

顺便会购买一些其他东西，带动了其他商品的销售。

关联规则已经成功地应用到市场购物分析中，至今已提出了很多的关联规则

挖掘算法，如Ａｐｒｉｏｒｉ［引、ＤＨＰ［们、ＦＰ．Ｇｒｏｗｔｈ／１０】等算法，这些算法从不同角度来挖掘关联规则，有的从深度，有的从广度进行挖掘，取得了一定的成效。目前，挖掘关联规则的技术正处在一个不断发展的过程中，有着很好的发展前景。对关联规则的应用也已从最初的商业指导到生活中其他领域，如教育、科研、医学等。

１．５本文的主要工作

数据挖掘是数据库研究、开发和应用最活跃的分支之一，同时也逐渐成为整个计算机科学中的一个重要领域。关联规则挖掘是数据挖掘最重要的研究方向之一，也是一个处于不断发展过程中的研究方向。正是出于对这项技术的兴趣，我选择了这个命题作为自己的研究课题。

本文的研究工作源于上述的背景，经过一段时间的资料查阅、理论研究和与指导教师及同学的讨论后，我对关联规则挖掘这一技术有了自己的一些心得与体会。在总结这些心得的基础上，我撰写了“基于关联规则的数据挖掘算法研究”的毕业论文。目的是对数据挖掘进行深入的研究，针对数据挖掘中的关联规则经典算法——Ａｐｒｉｏｒｉ算法的缺陷，探讨优化问题，以提高算法的挖掘效率和挖掘质量，本文主要做了以下几方面的工作：

基于关联规则的数据挖掘算法研究

１、数据挖掘背景与现状研究。在介绍数据挖掘研究背景的基础上，分析了数据

挖掘的现状并引出了关联规则研究的现实意义。

２、数据挖掘技术的研究。对数据挖掘的基本概念、挖掘过程、系统总体结构、

任务、常用技术及实际应用做了简单介绍，并指出数据挖掘的研究方向。

３、关联规则分析与研究。在介绍关联规则基本概念的基础上，对概念所涉及的术语及性能进行了说明，对关联规则的性质做了详细的介绍，对关联规则发现任务和价值衡量标准进行简单概括，对关联规则典型算法做了总结。

４、关联规则挖掘经典算法Ａｐｒｉｏｒｉ算法的分析与研究。在介绍Ａｐｒｉｏｒｉ算法思想的基础上，给出了算法的流程及算法的伪代码，并通过～个具体实例来演示算法的挖掘过程，然后分析Ａｐｒｉｏｒｉ算法的优缺点，提出该算法的性能瓶颈。

５、Ａｐｒｉｏｒｉ算法的改进。首先，研究了Ａｐｒｉｏｒｉ优化算法的现状，然后针对Ａｐｆｉｏｄ算法的不足，本文提出了一种高效的关联规则挖掘算法ＢＴＡ（Ｂａｓｅｄ

ｏｎ

ＴＩＤｓｅｔ

Ａｐｒｉｏｒｉ），通过候选集项目的事务标识符集做交运算的方法计算支持度，而不必每次计算支持度时都要扫描整个数据库，通过实验对ＢＴＡ算法与Ａｐｒｉｏｒｉ算法的效率进行比较，证明ＢＴＡ算法提高了运行效率。

此外，为改善Ａｐｒｉｏｒｉ算法挖掘质量，从数据约束角度考虑改进算法，提出ＩＷＡ（Ｉｎｔｅｒｅｓｔｓｅｔ

目找出数据库中的相关项组成兴趣项扩展集，这样会减小挖掘规模，提高算法效率。然后对兴趣项扩展集中的项目根据重要程度分别赋以不同的权值，区别对待每个项目，从而可以挖掘出用户关心的具有价值的关联规则，提高挖掘的质量。

基于关联规则的数据挖掘算法研究

第２章

数据挖掘技术

第２章数据挖掘技术

２．１数据挖掘的定义和特点

数据挖掘是一类深层次的数据分析方法，被认为是解决“数据爆炸知识贫乏＂的有效方法之一，在最近几年里已被数据库界广泛研究。

从广义上讲，数据挖掘（ＤａｔａＭｉｎｉｎｇ——ＤＭ）是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。这个定义包括以下四个层次的含义：

１、数据源必须是真实的、大量的、含噪声的；２、发现的是用户感兴趣的知识；

３、发现的知识要可接受、可理解、可运用，最好能用自然语言表达结果；４、并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的，是有特定前提和约束条件、面向特定领域的。

数据挖掘是一门很广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。通过数据挖掘，有价值的知识、规则、高层次的信息就能从数据库的相关数据集合中抽取出来，并从不同角度显示。这些挖掘出来的规则蕴涵了数据库中一组对象之间的特定关系，揭示出一些有用的信息，为经营决策、市场策划、金融预测等提供依据。

数据挖掘的特点如下：

１、处理对象为大规模数据库，数据规模十分巨大；

２、信息查询一般是由决策指定者（用户）提出的即时随机查询，往往没有精确的查询要求，需要靠数据挖掘技术寻找用户可能感兴趣的东西：

３、在一些应用中，某些行为并没有实际发生或者很少发生，因而它们对输出所造成的影响没有在数据库中体现出来，需要利用数据挖掘技术从数据库中提取有用的规则，为这种情况提出预测；

４、在一些应用中，由于变化迅速，数据可能很快过时，因此要求数据挖掘技术能很快对数据变化作出反应以提供决策支持，数据挖掘既要发现潜在的规则，还要管理和维护规则，而规则是动态的，当前的规则只能反应当前状态的数据库特征，随着新数据的不断加入，规则需要随之更新；

５、数据挖掘中规则的发现主要基于大样本的统计规律，发现的规则不必适用于所有的数据，当达到某一个阀值时便可认为有此规律。

基于关联规则的数据挖掘算法研究

２

２数据挖掘的过程

从知识发现的角度，可以把数据挖掘视为数据库中知识发现过程的一个基本

步骤。一般知识发现的过程山以下几个步骤组成，如图２．１所示：

Ｒ＊１１，

图２一Ｉ数据挖掘的过程

Ｆｉｇｕｒｅ２－】ＴｈｅＰｒｏｃｅｓｓｏｆＤａｔａＭｉｎｉｎｇ

ｌ、数据清理与集成：消除噪声或不一致的数据，将多种数据源可以组合在

一起；

２、数据选择与变换：从数据库中检索与分析任务相关的数据，将数据变换或统一成适合挖掘的形式，如通过汇总或聚类操作：

３、数据挖掘：基本步骤，使用智能方法提取数据模式；

４、模式评估与表示：根据某种兴趣度量．识别表示知识的真正有趣的模式，使用可视化和知识表现技术，向用户提供挖掘知识。

２

３数据挖掘系统总体结构

数据挖掘步骤町以与用户或知识库交互。有趣的模式提供给用户，或作为新

的知识存取放在知识库中。从数据挖掘的广义观点来看，数据挖掘是从存放在数据库、数据仓库、或其他信息库中的大量数据中挖掘有趣知识的过程。基于图２－１所示的数据挖掘过程，一个典型的数据挖掘系统应具有以下主要结构，如图

２－２所示。

基于关联规则的数据挖掘算法研究

第２章数据挖掘技术

图２－２典型的数据挖掘系统

Ｆｉｇｕｒｅ２－２ＴｈｅＴｙｐｉｃａｌＤａｔａＭｉｎｉｎｇＳｙｓｔｅｍ

根据文献【ｌｌ】可知，典型的数据挖掘系统具有以下主要部分：

数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子表格或者其他类型的信息库。可以在数据上进行数据清理和集成。

数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服务器负责提取相关数据。

●知识库：这是领域知识，用于指导搜索或评估结果模式的兴趣度。这种知识可能包括概念分层，用于将属性或属性值组织成不同的抽象层。用户确信的知识也可以包含在内。

数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。

◆模式评估模块：通常，此部分使用兴趣度度量，并与数据挖掘模块交互，

以便将搜索聚焦在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模式

评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。

对于有效的数据挖掘，建议尽可能深地将模式评估推进到挖掘过程之中，以便将

搜索限制在有兴趣的模式上。

图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系

统交互，指定数据挖掘任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结

果进行探索式数据挖掘。此外，此部分还允许用户浏览数据库和数据仓库模式或

者数据结构，评估挖掘的模式。

基于关联规则的数据挖掘算法研究

北京Ｔ业大学工学硕士学位论文

２．４数据挖掘的任务

数据挖掘技术来自应用的需要，要对这些数据进行微观、中观乃至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，利用已有的数据对未来的活动进行预测。所以数据挖掘任务一般可以分为两类：描述和预测。描述性挖掘是刻画数据库中数据的一般特性。预测性挖掘任务是对当前数据进行推断，以进行预测。数据挖掘的任务主要包括（１２１：

ｌ、分类（Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）。其目的是得到一个分类函数或分类模型（Ｃｌａｓｓｉｆｉｃａｔｉ

ＯＦ／Ｍｏｄｅｌ，也称为分类器），该模型能按照事先定义的分类标准，把数据库的数

据项映射到给定类别中的某一个，即对数据进行归类，而且能够把分类模型，对其他未分类的或是新的数据做出预测。使用的技术有决策树（ＤｅｃｉｓｉｏｎＴｒｅｅ），记忆基础推理（Ｍｅｍｏ巧．ｂａｓｅｄＲｅａｓｏｎｉｎｇ）等。例如：可以根据已有的个人住房贷款的历史数据，来建立一个借款人信用风险等级分类模型，把贷款申请人的风险等级划分高、中、低三级，以后就可以利用这个模型来对数据库的其他申请者或是新的申请者做出预测。

２、聚类（Ｃｌｕｓｔｅｒｉｎｇ）。是把一组个体按照相似性归纳成若干类别，即“物以类聚”。它的目的是使属于同一类别的个体之间的距离尽可能的小，而不同类别的个体间的距离尽可能的大。例如，一些特定症状的聚集可能预示了一个特定的疾病；租借图书类型不相似的客户聚集，可能暗示成员属于不同的文化群。

３、关联和序列发现（ＣｏｒｒｅｌａｔｉｏｎＤｉｓｃｏｖｅｒｙ）。决定哪些事情将一起发生。是形式如下的一种规则，“在购买面包和黄油的顾客中，有９０％的人同时也买了牛奶”（面包＋黄油＋牛奶）。关联规则发现的思路还可以用于序列模式发现。用户在购买

物品时，除了具有上述关联规律，还有时间或序列上的规律。例：①超市中客户在购买Ａ的同时，经常会购买Ｂ，即Ａ＝＞Ｂ（关联规则）。②客户在购买Ａ后，隔

一段时间，会购买Ｂ（序列分析）。

４、估计和预钡ＪＪ（ＥｓｔｉｍａｔｉｏｎａｎｄＰｒｅｄｉｃｔｉｏｎ）。估计是根据已有的长期累积的资

料来推测某一属性未知的真值。例如按照贷款申请人的教育程度、年龄及收入来

推估贷款的金额。使用的技术有回归分析和人工神经网络等。预测是根据对象属性过去观察值来估计该属性未来的值。例如由借款人的过去还贷款情况来预测其未来的还贷款情况（及时还贷款还是拖欠贷款）。使用的技术有回归分析、时间序列分析及人工神经网络等。

５、描述（Ｄｅｓｃｒｉｐｔｉｏｎ）。描述的功能是对复杂的数据库提供简要的描述，提供诸如汇总，均值，方差等。这个功能的主要目的是当未来使用别的功能时对数据先有较好的了解。在建立任何模型之前先做数据描述的工作是十分重要的，将会指导如何去建模。

基于关联规则的数据挖掘算法研究

第２章数据挖掘技术

６、偏差分析和异常检验（Ｄｅｖｉａｔｉｏｎ

ａｎｄＦｒａｕｄ

Ｄｅｔｅｃｔｉｏｎ）。数据库中的数据常

有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括很多潜在的知识，

如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值

随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的差别。例如：在银行的１００万笔交易中有５００例的欺诈行为，银行为了稳健经营，就要发现这５００例的内在因素，减小以后经营的风险。

２．５数据挖掘的技术及其应用

根据数据挖掘的任务和模型，通常采用的技术是贝叶斯网络、决策树、遗传算法、神经网络和统计分析、粗糙集方法、关联规则分析。

贝叶斯网络Ｉｌ列是用来表示变量集合的连接概率分布的模型，它提供了一种自然的表示因果关系的方法。贝叶斯网络本身并没有输入和输出的概念，各结点的计算是独立的，因此，贝叶斯网络的学习既可以由上级结点向下级结点推理，也可以是由下级结点向上级结点推理。

贝叶斯网络最初是由ＲＨｏｗａｒｄ和Ｊ．Ｍａｔｈｅｓｏｎ于１９８１年提出，后来Ｃｏｏｐｅｒ．Ｇ与Ｈｅｒｓｋｏｖｉｔｓ．Ｅ给出了ＢＤ（ＢａｙｅｓｉａｎＤｉｒｃｈｌｅｔ）度量模型【ｌ４１，Ｈｅｃｋｅｒｍａｎ．Ｄ等扩展了ＢＤ的思想【１５１。贝叶斯网络其它方向的研究也层出不穷，例如非线性动态模型

的Ｇｉｂｂｓ抽样模型【１６】，贝叶斯分类剁１７】０８１等等。

决策树ｆ１９】方法首先选择训练样本的一个子集以形成一个决策树，如果此树没有为所有的对象给出一个正确的答案，则将例外情况加入树中，不断重复这一个过程，直到发现正确的决策集。最终形成这样一颗树：每一个叶子代表一个类名，每一个内部节点描述一个属性，节点的每一个分支代表对应于该属性的每一个可能的值。ＩＤ３ｔ２０１算法是一个决策树中最基本的算法，Ｃ４．５【２１】也是一个非常经典的算法。

遗传算法【２２】是模拟生物进化过程的算法。由３个基本算子组成。繁殖（选择）：是从１个旧种群（父代）选出生命力强的个体，产生新种群（后代）的过程。交神经网络方法【２３】是基于生物神经系统的结构和功能而建立起来的，模拟人叉（重组）：选择２个不同个体（染色体）的部分（基因）进行交换，形成新个体。变异（突变）：对某些个体的某些基因进行变异（１变０，０变１）。这种遗传算法可以起到产生优良后代的作用。这些后代满足适应度值，经过若干代的遗传，将得到满足要求的后代（问题的解）。遗传算法已在优化计算和分类机器学习方法方面显示了明显的优势。

脑神经元的方法。以ＭＰ模型和ＨＥＢＢ学习规则为基础，可以建立三大类神经网络模型：前溃式网络（以感知机、反向传播模型、函数型网络为代表，可用于

预测、模式识别等方面），反馈式网络（以Ｈｏｐｆｉｅｌｄ的离散模型和连续模型为代

基于关联规则的数据挖掘算法研究

北京工业人学Ｔ学硕｛二学位论文

表，分别用于联想记忆和优化计算），自组织网络（它以ＡＲＴ模型、Ｋｏｈｏｌｏｎ模型

为代表，用于聚类）。利用神经网络所固有的并行结构、并行处理、自适应性、

知识的分布存储、较强的容错性、本质的非线性系统等特性，通过网络训练，可以建立数据库信息的非线性模型，并从中提取相应的规则。

粗糙集方法［２４１是利用模糊集理论对实际Ｉ＇ａＪ题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确能

力就越低，即模糊性就越强。

关联规则１２５Ｊ是由ＲａｋｅｓｈＡｇｒａｗａｌ等人首先提出的。两个或两个以上变量的取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、

可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找出数据库中隐藏的关联网。一般用支持度和置信度两个阀值来度量关联规则的相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。关

联规则是本文重点讨论的内容，我们将在后面章节展开讨论。

近年来随着数据库和网络技术的广泛使用，加上使用先进的自动数据采集工

具，人们所拥有的数据量急剧增加，使得数据挖掘技术得到广泛的应用。如零售、

金融保险、产品制造、电信、科学研究等行业。文献【２６】列举了数据挖掘技术的一些应用领域，见表２．１。

表２．１数据挖掘的应用领域表

Ｔａｂｌｅ２ ｌＤａｔａＭｉｎｉｎｇａｐｐｌｉｃａｔｉｏｎｆｉｅｌｄｓ

技术方法关联分析决策树遗传算法贝叶斯网络粗糙集方法神经网络统计分析

主要功能和特点分类、聚类

归类分类，可理解性聚类、优化、高效性分类、聚类和预测，易理解不确定分类

预测、分类、聚类、解释性差聚类、结果精确、易理解

主要应用领域

零售业、保险业和制造业制造业、医学和零售业等金融业、保险业和农业等医学、制造业和电信业零售业、金融业和制造业金融业、保险业和制造业金融业、制造业和医学

ｌ、零售业：零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习惯和趋向，对于零售商制定销售策略是至关重要的。销售分析人员运用关联规

则挖掘技术对大量的销售数据进行分析，可以发现顾客购买模式和趋势，以便改

进服务质量，取得更好的顾客保持力和满意程度，提高货品销售比率，设计更好的货品运输和分销策略，减少成本。购物篮分析是数据挖掘技术应用在零售业中的一种有效的方式，可用于销售搭配、产品目录设计、产品定价和促销等。

２、金融投资与保险：在银行等金融机构中产生的金融数据通常相对比较完整，可靠和质量较高，因此，数据挖掘在这一领域中的应用相对比较成熟，也取

基于关联规则的数据挖掘算法研究

弟２审数据挖掘技术

得了较好的社会效益和经济效益。由于金融投资风险很大，在进行投资决策时，需要对各种投资方向的有关数据进行分析，以选择最佳的投资方向。而数据挖掘是通过对已有的数据进行处理，并利用学习得到的模式进行市场预测，以选择最佳的投资方向，从而可以使金融投资的风险降低。通过分析市场波动的因素，建

立预测模型，进行投资分析和预测，改进预测市场波动的能力，为投资决策提供

科学的依据。

随着社会保障体系的日益健全，保险业取得了蓬勃的发展，发挥着越来越重

要的作用。保险是一项风险业务，保险公司的～个重要工作就是进行风险评估。通过研究证明，可以利用数据挖掘技术来进行风险分析。在保险公司建立的保单及索赔信息数据库的基础上，寻找保单风险较大的领域，从而得出一些实用的控制风险的规则，以指导保险公司的工作。数据挖掘技术在保险业中的应用，有利于保险公司开展业绩评价、业务预算、市场分析、风险评估和风险预测等，大大提高企业防范和抵抗经营风险的能力和水平，也为管理人员提供科学的决策依据。

３、产品制造业：随着现代技术越来越多的应用于制造业，产品生产已不是

人们想象中的手工劳动，而是集成了许多先进技术的流水作业。在产品的生产制

造过程中常常伴随着大量的数据，如产品的各种加工条件或控制参数，这些数据

反映每个生产环节的状态，不仅为生产的顺利进行提供了保证，而且通过这些数据的分析，得到产品质量与参数之间的关系。这样通过数据挖掘对这些数据的分

析，可以对改进的产品质量提出针对性很强的建议，而且可以提出新的更高效节

约的控制模式，从而为制造厂家带来极大的回报。

４、电信业：电信业已经从单纯的提供市话和长话服务演变成提供综合服务的电信业务，如语音、传真、寻呼、移动电话、图像、电子邮件、计算机和Ｗｅｂ数据传输，以及其他数据通信服务。而且随着许多国家对电信业的开放和新兴计算与通信技术的发展，电信市场正在迅速扩张并越发竞争激烈。因此，利用数据挖掘技术来帮助理解商业行为、确定电信模式、捕捉盗用行为、更好的利用资源和提高服务质量是非常必要的。

５、科学研究：在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量实验和观测数据靠传统的数据分析工具己难于对付，因此对功能强大的智能化自动分析工具要求迫切，这种需求推动了数据挖掘技术在科学研究领

域的应用发展，并且已经获得一些重要的应用成果。

当然，数据挖掘的应用领域还远远不止以上所提到的。对医疗数据的挖掘用于病例、病人行为特征的分析，以及用于药方的管理；对司法数据的挖掘可用于案件调查、案例分析、犯罪监控；对生产加工数据的挖掘可用于进行故障诊断、生产过程优化；对网络入侵检测数据的挖掘可以发现异常的访问模式，从而有效

基于关联规则的数据挖掘算法研究

北京工业大学工学硕＿｛：学位论文

地防止黑客的攻击等等。

２．６数据挖掘的趋势和面临的困难

尽管取得了许多进展，数据挖掘仍面临着许多困难与挑战：

ｌ、源自于数据库本身。现实世界数据库中的数据是动态的且数量庞大，有时数据是不完全的，并且存在噪音、不确定性、信息丢失、信息冗余、数据分布

稀疏问题。

２、数据挖掘技术与特定数据存储类型的适应问题。数据库类型多样，不同

的数据存储方式会影响数据挖掘的具体实现机制、目标定位、技术有效性等。比

如适用于关系数据库的算法未必适用于非结构化数据的挖掘。指望一种通用的应

用模式适合所有的数据存储方式来发现有效知识是不现实的。因此，针对不同数据存储类型的特点，进行针对性研究是目前流行而且也是将来一段时间所必须面

对的问题。

３、知识的表示形式。它包括如何对挖掘到的知识进行有效的表示，使人们容易理解。比如如何对数据进行可视化，推动人们主动地从中发现知识。可视化

要求已经成为目前信息处理系统的必不可少的技术。对于一个数据挖掘系统来

说，它更是重要的。可视化挖掘除了要和良好的交互式技术结合外，还必须在挖掘结果或知识模式的可视化、挖掘过程的可视化以及可视化指导用户挖掘等方面

进行探索和实践。因此知识表示的深入研究将是数据挖掘实用化的一个重要步

骤。

４、现有的理论和算法本身还有待发展完善。像定性定量转换、不确定性推理等一些根本性的问题还没有得到很好地解决。同时为了有效地从数据库的大量数据中提取信息，数据挖掘算法必须是有效的和可伸缩的。换句话说，对于大型数据库，数据挖掘算法的运行时间必须是可预计的和可接受的。所以需要发展高效的数据挖掘算法。

另外数据挖掘系统与实际应用结合得还不够。除了经典的“啤酒”与“尿布”

外，还没有太多数据挖掘成功的范例。因此，数据挖掘与其他技术特别是数据仓

库技术的结合将是今后一个重要的发展方向。

２．７本章小结

本章以数据挖掘为主线，首先介绍了数据挖掘的基本概念和特点，阐述了数据挖掘的过程以及与之配合的系统总体结构；介绍了数据挖掘的任务和相关技术

以及它们的应用方向。最后讨论了数据挖掘的发展趋势以及面临的主要困难。

基于关联规则的数据挖掘算法研究

第３章

关联规则研究

第３章关联规则挖掘

在数据挖掘的知识模式中，关联规则模式是比较重要的一种，也是最活跃的一个分支。关联规则表示数据库中一组对象之间某种关联关系的规则。例如，关联规则可以表示为“购买了项目Ａ和Ｂ的顾客中有９５％的人又买了Ｃ和Ｄ”。从这些规则可找出顾客购买行为模式，可以应用于商品货架设计、生产安排、针对性的市场营销等。

采用关联模型比较典型的例子是“啤酒和尿布”的故事。在美国，一些年轻的父亲下班后经常到超市去买婴儿尿布，超市经过对顾客的购物信息进行挖掘，发现在购买婴儿尿布的年轻父亲中，有３０％。４０％的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起。结果是：销售额明显增加。关联规则问题由Ａｇｒａｗａｌ等人于１９９３年首先提出，随即引起了广泛的关注。许多研究者（包括Ａｇｒａｗａｌ本人）对关联规则挖掘问题进行了深入地研究，对最初的关联规则挖掘算法进行了改进和扩展。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想、增加衡量标准、规则约束、改变存储结构等，以提高算法挖掘规则的效率；对关联规则的应用进行推广，从最初的商业指导到生活中的其他领域，如：教育、科研、医学等，取得了良好的挖掘效果。

’

３．１关联规则基础知识

Ａｇａｗａｌ等人在１９９３年首先提出了从顾客交易数据库中发现用户购买模式的相关性问题，并提出了基于频繁项集的Ａｐｒｉｏｒｉ算法。在现有的关联规则挖掘算法中，广泛采用了“支持度－置信度”（Ｓｕｐｐｏｒｔ—Ｃｏｎｆｉｄｅｎｔ）的评价标准。

以下说明关联规则的一些相关定义【２７１［２８１１２９］［３０１及常用性质【３１】【３２１１３３］。

３．１．１关联规则的相关定义

设事务数据库Ｄ＝｛ｔｌ，ｔ２，…，ｔｍ｝是由一系列具有惟一标识ＴＩＤ的事务组成，Ｉ＝｛ｉｌ，ｉ２，．一，ｉｍ｝是由数据库Ｄ中所有项目构成的集合，每个事务ｔｉ（ｉ＝ｌ，２…，ｎ）都对应Ｉ上的一个子集。

定义１：数据项集的支持度

设Ｘｃ＿．Ｉ，项目集Ｘ在数据集Ｄ上的支持度（Ｓｕｐｐｏａ）是包含Ｘ的事务在Ｄ中

所占的百分比，即

ＳｕｐｐｏＩｒｔ（Ｉｉ）＝№∈ＤＩｘ∈ｆ）１１／１１Ｉｌ

（３－１）

基于关联规则的数据挖掘算法研究

北京Ｔ业人学Ｔ学硕ｌ‘学位论文

定义２：频繁项集与非频繁项集

支持度大于等于最小支持度的非空数据项集称作频繁项集（或大项集），否则称为非频繁项集。

定义３：关联规则

形同ＸｊＹ的蕴涵式就称为数据集Ｄ中的关联规则。其中Ｘ，ＹｃＩ，并且Ｘ１７Ｙ＝Ｏ。Ｘ称作规则的前提，Ｙ是结果。

定义４：关联规则的支持度与置信度

支持度（Ｓｕｐｐｏｒｔ）：规则ＸｊＹ的支持度为Ｓ是指在数据集Ｄ中有ｓ％的事务既包含Ｘ同时又包含Ｙ，即同时出现数据项集Ｘ和Ｙ的概率，其表达式为：

Ｓｕｐｐｏｒｔ（ＸｊＹ）２Ｓｕｐｐｏｒｔ（ＸｕＹ）＝Ｐ（Ｘ

ｕ

Ｙ）（３－２）

置信度（Ｃｏｎｆｉｄｅｎｃｅ）：规则ＸｊＹ的置信度为ｃ是指在数据集Ｄ中，包含Ｘ的事务中有Ｃ％的事务同时又包含Ｙ，即出现数据项集Ｘ的前提下，出现数据项集Ｙ的概率，其表达式为：

Ｃｏｎｆｉｄｅｎｃｅ（ＸｊＹ）＝ＳｕｐｐｏＩｒｔ（ＸｔＪＹ）／Ｓｕｐｐｏｒｔ（Ｘ）＝Ｐ（ＹＩＸ）

（３ ３）

支持度体现了项目集在交易中出现的频度，而置信度体现了项目集之间的关联程度。

定义５：强关联规则与弱关联规则

一般地，用户可以定义两个阀值，分别设为最小支持度阀值和最小置信度阀值，要求数据挖掘系统所生成的关联规则的支持度和置信度都不小于这两个给定的阀值，此时我们就说这个规则是强关联规则，否则就是弱关联规则。

３．１．２关联规则的两个重要定理

定理１设Ｕ＝｛ｕｌ，Ｕ２，…，ｕｋ｝为项集，且Ｕｃ＿Ｉ，Ｕ≠巾，Ｑｃ＿Ｕ，对于给的数据库事务集Ｄ和最小支持度ｍｉｎｓｕｐ，如果项集Ｕ为频繁项集，则Ｑ也是频繁项集。即父集是频繁集则其子集也一定是频繁集

定理２设Ｕ＝｛ｕｌ，Ｕ２，…，ｕｋ｝项集，且Ｕｃ—Ｈｃ—Ｉ，对于给定的数据库事务集Ｄ和最小支持度ｍｉｎｓｕｐ，如果项集Ｕ为非频繁项集，则Ｈ也一定是非频繁项集。即子集是非频繁集则其父集也一定是非频繁集

３．２关联规则的分类

我们将关联规则按不同的情况进行分类【３４】【３５】：

１、基于规则中处理的变量的类别，可以分为布尔型和数值型。布尔型关联规则处理的数据都是离散的、分类化的，它显示了这些变量间的关系。数值型关

基于关联规则的数据挖掘算法研究

第３章

ＩＩＩＩ

●Ｉ

ＩＩＩ

ＩＩＩ

关联规则研究

ｍ＿

ＩＩ

１１｜

ＩＩ｜

联规则处理的变量包含有数量信息，它表示的是属性值之间的关联关系。在挖掘数值型关联规则时要先对数值型变量进行离散化处理，再对处理后的数据进行挖

掘。例如：性别＝“女”一职业＝“秘书”，是布尔型关联规则：职业＝“秘书”

－－，－ａｖｅｒａｇｅ（收入）＝２３００，涉及的收入是数值类型，所以是一个数值型关联规则。

２、基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层

次的：而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如：

ＩＢＭ台式机一ＨＰ打印机，是一个细节数据上的单层关联规则；台式机－＂ＨＰ打印机，是一个较高层次和细节层次之间的多层关联规则。

３、基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中的一些关系：多维关联规则是处理各个属性之间的某些关系。例如：啤酒一尿布，这条规则只涉及到用户购买的物品；性别＝“女”一职业＝

“秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。

３．３挖掘关联规则的步骤

关联规则挖掘的问题就是要找出这样的一些规则，它们的支持度或置信度分别不小于指定的最小支持度值和最小置信度阀值，因此挖掘关联规则的过程分为两个步骤．

第一步，发现所有的频繁项集，也就是支持度不小于事先给定最小支持度的

项集；

第二步，在找出的频繁项集的基础上产生强关联规则，即产生那些支持度和置信度分别大于或等于事先给定的最小支持度和最小置信度的关联规则。

其中第一步是关联规则挖掘算法的核心，关联规则挖掘的问题的主要特征是数据量巨大。挖掘关联规则的总体性能由第一步决定。要求解第一个子问题，往往需要多次扫描数据库，这意味着大量的时间将花在数据库扫描和Ｉ／Ｏ操作上。

因此，如何迅速、高效地找出所有的频繁项目集是各种关联规则挖掘算法需要解决的主要问题，也是衡量各关联规则挖掘算法的标准，而第二步相对来说是很容

易实现的。

３．４关联规则的研究方向

目前，关联规则的研究已经取得了令人瞩目的成绩，但对下列问题的研究仍

本文来源：https://www.bwwdw.com/article/uxdj.html