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

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

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

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

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

20090201

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

摘要

摘要

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

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

２、

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

ｏｎ

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

ＴＩＤｓｅｔｓ

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

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

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

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

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

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

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

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

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

一

Ａｂｓｔｒａｃｔ

ｍ．

．

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

Ａｂｓｔｒａｃｔ

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

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

ａ

ｏｎｅ

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

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

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

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

ａｒｅ

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

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

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

ｏｎ

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

ｍｙ

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

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

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

ｉｓｐｏｉｎｔｅｄ

ｏｕｔ．

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

ａｌｇｏｒｉｔｈｍ

ｂａｓｅｄ

Ｃａｌｌ

ｏｎ

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

ｏｎ

ＴＩＤｓｅｔｓ

Ａｐｒｉｏｒｉ），ｉｓ

ｐｕｔ

ｆｏｒｗａｒｄ

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

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

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

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

ｃｏｕｎｔ

ｔｏ

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

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

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

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

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

ｉｔｅｍｓｅｔｓ

ａｒｅ

ｇｏｔ

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

ｌｉｎｋｅｄ．Ｔｈｅ

ｒｅｓｔ

ｔｏｂｅ

ａｒｅ

ｍａｙ

ｂｅ

ｄｅｄｕｃｅｄ

ｂｙ

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

ｏｎｅ

ａｌｌ

ｆｒｅｑｕｅｎｔ

ｉｔｅｍｓｅｔｓ

ｃｏｕｎｔ

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

ｉｔｅｍｓｅｔｓ

ｍｅｍｂｅｒｓ

ｉｓ

ａｄｄｅｄｆｏｒ

ｔｈｅ

ｕｐ

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

ｃｏｕｎｔｉｎｇ …… 此处隐藏：14500字，全部文档内容请下载后查看。喜欢就下载吧 ……