（计算机应用技术专业论文）基于关联规则的数据挖掘算法研究(1).pdf

摘要 关联规则揭示项集阃有趣的相联关系，可广泛应用于购物篮分析、相关分析、分 类、网络个性化服务等领域，是数据挖掘的重要研究课题。自1 9 9 3 年r a g r a w a l ， r s r i k a n t 首次提出该闯题以来，已出现了许多关联规则挖掘算法。这些算法大多基于 a p r i o r i 算法，在挖掘频繁模式时需要产生大量候选项集，多次扫描数据库，时空复 杂度过高。 本文提出的第一种频繁集挖掘算法一s u p p o q u i 算法，扫描1 遍数据库，查找出频 繁i - 项集，然后只扫描1 遍最大频繁集长度的结点集合，就可查找出所有的无冗余的 频繁集。 传统的关联规则挖掘都是基于频繁集来进行的，往往生成过多的规则，使用户很 难进行取舍。为此，本文又提出了第二种关联规则挖掘算法s g 算法，s g 算法避开 了频繁集的求解而直接挖掘出无冗余的关联规则 与基于a p f i o d 算法的传统算法相比，s u p p o q u i 算法和s g 算法无论从时间上还 是从宅塑圭墨递壑丝数量錾壅尘! 因此都是高效、可行的。 关键词：数据挖掘；关联规则；事务树i 事务规则树 a b s t r a c t a s s o c i a t i o nr u l e sm i n i n g ，a st h em o s ti m p o r t a n ts u b j c o ti nd a t am i n i n g ，r e v e a l s t h ec o r e l a t i o n sb e t w e e ni t e m s e t sa n dt h e r e f o r ec a n b ew i d e l ya p p l i e dt om a n yf i e l d s s u c ha sm a r k e tb a s k e ta n a l y s i s ，c o r e l a f i o na n a l y s i s jc l a s s i f i c a t i o n ，w e b - c u s t o m i s e d s e r v i c e ，e t c s i n c e1 9 9 3r a g r a w a l ，r s r i k a n tf i r s t l yp r o p o s e dt h ec o n c e p to f a s s o c i a t i o nr u l e s ，al o to f a l g o r i t h m sh a v ec o m eu p i nm i n i n go fa s s o c i a t i o nr u l e s w h i l em o s to f t h e s ea l g o d t h m sa r eb a s e do n a p r i o r ia l g o r i t h m ，w i l lg e n e r a t e a h u g e n u m b e ro f c a n d i d a t ei t e m s e t s ，n e e dm u l t i p l es c a n so v e rd a t a b a s e ，a n dm a i n t a i nab i g h a s ht r e e ，s ot h et i m ea n ds p a c ec o m p l e x i t yi st o oh i g h t h i sp a p e rp r o p o s e df i r s ta l g o r i t h mo f f r e q u e n c yi t e m s e t sm m i i l 乎一s u p p o q u i i t s c a nd a t a b a s eo n c ea n df i n df r e q u e n t1 i t e m s e t s ，t h e n ，m e r e l ys c a r f i n gn o e d s e t sw i t h l e n g t ho fl a r g e s tf r e q u e n c yi t e m s e t so n c e f i n a l l y , f i n d i n g a l ln or e d u n d a n c y i t e m s e t s t r a d i t i o n a la s s o c i a t i o nr u l e s m i n i n g a r ea l lb a s e d f r e q u e n c y i t e m s e t sa n d s o m e t i m e sc r e a t em o r er e d u n d a n c yr u l e s ，s oa st ou s e rh a r d l ya c c e p to rr e j e c t ， t h e r e f o r ，t h i sp a p e rp r o p o s e ds e c o n da l g o r i t h mb a s e da s s o c i a t i o nr u l e sm i n i n g s g i ti m m e d i a t e l ym i n ea l ln o r e d u n d a n c yr u l e sb ya v o i d i n gf i n df r e q u e n c y i t e m s e t s n om a t t e rw h a tt i m ea n d s p a c e ，s u p p o q u ia n d s gd e c r e a s e a c c o r d i n g t o q u a n t i t a t i v el e v e lw i t ht r a d i t i o n a la l g o r i t h m sb a s e da p r i o r i s o ，t h e yh a v eh i g h e r e f t i c i e n c ya n df e a s i b i l i t y k e y w o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e s ；t r a n s a c t i o nt r e e ；t r a n s a c t i o n r m e 1 l e e 1 1 i 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包括其他人已经发表或撰写过的研究成果，也不包含为 获得西北师范大学或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 签名：重玺查日期：兰堕三：! ! 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵守此规定) 签名：睫佼盎 导师签名：j 毫二纽! 日期导师签名：，蒸。2 型缘!日期 j t o o 1 、毫2 。 基于关联规则的数据抡橱算法研究 第一章绪论 1 1 数据挖掘的研究背景 科技的进步，特别是信息产业的发展，把我们带入了一个崭新的信息时代。随着计算 机应用的普及和数据库技术的不断发展，数据库管理系统的应用领域越来越广泛。条形码 和信用卡的普及和使用，迸一步加速了商业、金融、保险等领域的信怠化进程。在工业、 商业、科研、行政、医疗、保险等应用领域中，大量的数据被搜集和存储在各种数据库中， 例如：美国的w a l m a r t 公司每天增加两千万条事务数据记录。由于这些数据十分繁杂，如 何有效的利用这些数据，从这些数据中发现有价值的信息或知识，达到为决策服务的目的， 就成了一项非常艰巨的任务。 采用传统的数据分析方法和数据查询、验证方法，对这些巨量数据进行分析和处理， 不仅耗费大量的计算时间，而且完全依赖于预先对数据之间关系的假设和估计，这些方法 已经不能满足人们日益增长的对数据中隐含知识的渴求。大量的信息在给人们带来方便的 同时，也带来了一系列问题，面对海最数据库和大量繁杂信息，如何才能从中提取有价值 的知识，进一步提高信息的利用率，由此引发了一个新的研究方向：数据挖掘( d a t a m i n i n g ) ，也就是基于数据库的知识发现( k d d ) ，其中关联规则数据挖掘算法尤为引人注 目。 数据挖掘方法的提出，让人们最终有能力认识到数据的真正价值，即蕴含在数据中的 信息和知识。数据挖掘是目前国际数据库和信息决策领域的最前沿研究方向之一，己经引 起了学术界和工业界的广泛关注。一些国际上高级别的实验室，例如i b m a l m a d e n 、g t e 以及众多的学术单位都在这个领域开展了各种各样的研究计划。研究的目的主要是发展有 关的方法、理论和工具，以支持从大量的数据中提取有用的、让人感兴趣的知识。 数据库中的知识发现始于8 0 年代后期，1 9 8 9 年召开了第一次关于知识发现和数据挖 掘的国际会议。1 9 9 5 年8 月，在加拿大的m o n t r e a l ，召开了首届知识发现和数据挖掘的 国际讨论会。亚太地区于1 9 9 7 年在新加坡举行了首届亚太知识发现和数据挖掘的国际会 议( e a k d d ，9 7 ) ；欧洲也于1 9 9 8 年召开了首届欧洲知识发现和数据挖掘的学术会议。 知识发现和数据挖掘的研究直作为数据库和机器学习的一个分支，处于依附的地 位。直到1 9 9 8 年6 月，a c m s l g k d d ( a s s o c i a t i o n f o rc o m p u t i n g m a c h i n e r y ，s p e c i a l i n t e r e s t g r o u p o n k n o w l e d g ed i s c o v e r ya n d d a t am i n i n g ) i e 式成立，标志着知识发现和数据挖掘正 式成为一个独立的学科。 基于关联规月口的数据挖掘算法研究 数据挖掘的研究已经和数据仓库的研究结合起来。数据仓库也是近年来才提出的新概 念。所谓数据仓库是一种数据的存储地，来自于异地、异构的数据源或数据库的数据经过 加工后在数据仓库中存储、提取和维护。传统数据库主要面向业务处理，而数据仓库面向 复杂的数据分析、高层决策支持。数据仓库提供来自于种类不同的应用系统的集成化和历 史化的数据，为有关部门或企业进行全局范围的战略决策和长期分析提供了有效的支持。 数据仓库捌有任意提取数据的自由，而不干扰数据库的正常运行。 目前，在国外，数据挖掘技术及其相关的决策支持系统发展彳导很快，它们在商业晁， 公共服务行业等众多行业被广泛应用，并快速、直接的带来了令人吃惊的利润，同时也带 动了这些行业的飞速发展。因此，有人称这项技术为二十世纪影响人类的计算机方面的三 大事件之一。 1 2 数据挖掘中的关联规则 目前，数据挖掘的主要研究领域为数据总结、分类、聚类、关联规则等方面。关联规 贝d 表示数据库中一组对象之间某种关联关系的规则。例如，关联规则可以表示为“购买了 项目a 和b 的顾客中有9 5 的人又买了c 和d ”。从这些规则可找出顾客购买行为模式， 可以应用于商品货架设计、生产安排、针对性的市场营销等。采用关联模型比较典型的例 子是“啤酒和尿布”的故事。在美国，一些年轻的父亲下班后经常到超市去买婴儿尿布， 超市经过对顾客的购物信息进行挖掘，发现在购买婴儿尿布的年轻父亲中，有3 0 4 0 的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起。结果是： 销售额明显增加了。 关联规则问题由a g r a w a l t l 】等于1 9 9 3 年首先提出，以后诸多的研究人员对关联规则的 挖掘问题进行了大量的研究【2 】- 【6 1 。他们的工作包括对原有的算法进行优化，如引入随机采 样、并行的思想、增加衡量标准、规则约减、改变存储结构等，以提高算法挖掘规则的效 率；对关联规则的应用进行推广，从最初的商业指导到生活中的其他领域，如教育、科研、 医学等。 1 3 本文的主要工作 本文的研究工作源于上述的背景。目的是对数据库知识发现进行深入的研究，探讨 数据挖掘中的关联规则算法优化问题，以及研究如何更好地应用于实际工作中。主要工作 包括以下几部分： 1 对数据挖掘技术进行研究，探讨其应用领域的广泛性、功能、分类以及未来的开发 方向。 2 研究关联规则算法。对经典的a p r i o r i 算法和f p g r o w t h 算法进行全面的分析，以 2 基于关联规则的数据挖掘算法研究 及指出了挖掘中的关键步骤和算法的缺陷。介绍了对a p r i o r i 算法的几种优化算法：基于 划分的方法、基于h a s h 的方法、基于采样的方法。 3 针对a p r i o r i 算法和f p g r o w t h 算法的不足，提出了频繁集挖掘算法s u p p o q u i 算法， 该算法在时空效率上有了很大的提高。并与a p r i o r i 算法作了对比。 4 提出了关联规则挖掘算法一s g 算法，建立新的思路简化了传统算法基于频繁集挖 掘规则的过程。s g 算法避开频繁集而直接挖掘出无冗余的关联规则。并与传统算法作了 对比。后两部分工作是本文的核心。 基于关联规则的数据挖掘算法研究 第二章数据挖掘技术综述 2 1 数据挖掘的概念 从1 9 8 9 年到现在，k d d 的定义随着人们研究的不断深入也在不断完善，目前比较公 认的定义是f a y y a d 4 1 ( m 噜给出的：数据挖掘是从数据集中识别出有效的、新颖的、潜在 有用的以及最终可理解模式的高级处理过程。还有很多和这一术语相近似的术语，如从数 据库中发现知识( k d d ) 、数据分析、数据融合( d a t af u s i o n ) 以及决策支持( d e c i s i o ns u p p o r 0 等。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿样。原始数据可以是结 构化的，如关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至 是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以 是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、 过程控制等。还可以用于数据自身的维护。因此。数据挖掘是一门根广义的交叉学科，它 汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方 面的学者和工程技术人员。 简单地说，数据挖掘就是从大量的数据中提取或者“挖掘”知识。在许多场合下，数 据挖掘又被称为数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a a b a s e ，简称k d d ) 。但是， 更科学的说法是将数据挖掘视为数据库知识发现的一个基本步骤。在这种情况下，数据库 的知识发现过程如图2 1 所示，由以下几个步骤组成n ( 1 ) 数据清理：消除噪声或者不一致数据。 ( 2 ) 数据集成：多种数据源可以组合在一起。它和数据清理一起被视为预处理步骤， 结果数据存放在数据仓库中。 ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据。 ( 4 ) 数据变换：将数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作。在有 些场合下，数据变换在数据选择过程之前迸行，特别是在数据仓库的情况下。 ( 5 ) 数据挖掘：使用智能方法提取数据模式。 ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式。 ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 4 基于关联规的数据挖掘算法研究 图2 1 数据挖掘的过程 尽管将数据挖掘视为数据库知识发现过程的一个基本步骤更为科学，但是在产业界、 媒体和数据库研究界，将数据挖掘直接当作数据库中的知识发现更为流行。因此数据挖掘 有了一个更加广泛的概念：数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量 数据中挖掘有趣知识的过程。基于这种观点，一个典型的数据挖掘系统可以由以下几个主 要成分组成f 如图2 2 所示1 ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子表格或 其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服务器负 责提取相关数据。 知识库：用于指导搜索或评估结果模式的兴趣度。 数据挖掘引擎：数据挖掘系统基本的部分，由一组功能模块组成，用于特征化、关 联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互，以使将搜 索聚焦在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模式评估模块也可以与 挖掘模块集成在起，这依赖于所用的数据挖掘方法的实现。 图形用户界面：实现用户和数据挖掘系统之间的通信，允许用户与系统交互，指定 数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结果进行探索式数 据挖掘。此外，此成分还允许用户浏览数据库和数据仓库模式或数据结构，评估挖掘的模 式，以不同的形式对模式可视化。 基于关联规则的效据挖掘算法研究 图形用户界面 lf 模式评估 if 数据挖掘引擎 lf 数据库或数据仓库服务器1 倒2 ，2 典型的数据挖掘系统结构 要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据库的 简单检索查询调用，而且要对这些数据进行微观、宏观的统计、分析、综合和推理，以指 导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据对未来的活动进行 预测。这样一来，就把人们对数据的应用，从低层次的末端查询操作，提高到为各级经营 决策者提供决策支持。这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这 里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科 学定理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有特定 前提和约束条件、面向特定领域的，同时还要能够易于被用户理解，最好能用自然语言表 达发现结果。因此d m k d ( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 的研究成果很讲求实 际。 2 2 数据挖掘的功能和分类 2 2 。1 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般可以分为 两类：描述和预测。描述性挖掘任务刻划数据库中数据的般特性，而预测性挖掘任务则 在当前数据上进行推断，以进行预测。 在很多情况，用户并不知道什么样的模式是有趣的，因此可能想探索多种不同的模式， 以从中选择出自己感兴趣的模式。这就要求数据挖掘系统应该能够挖掘多种类型的模式， 基于关联觑剧的数据挖搁算法研究 以适应不同的需求。此外，数据挖掘系统应该能够发现各种粒度( 即不同的抽象层) 的模式， 应当允许用户给出提示，指导或聚焦有趣模式的搜索。 数据挖掘的功能以及可以发现的模式类型有【8 l ：类，概念描述、关联分析、分类和预 测、聚类分析、孤立点分析和演变分析。 1 、类概念描述 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和概念可能 是有用的。这种类或概念的描述称为类概念描述。这种描述可以通过以下方法得到： 数据特征化：是目标类数据的一般特征或特性的汇总。 数据区分：将目标类对象的一般特性与一个或多个对比类对象的一般特性比较。 数据特征化和区分：同时应用数据特征化和数据区分进行描述。 2 、关联分析 关联分析用于发现关联规则，关联规则描述了给定数据集中的项之间的有趣联系。 关联分析广泛应用于购物赡或事务数据分析。从大量商务事务记录中发现有趣的关联关 系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析等。 3 、分类和预测 分类是找出描述并区分数据类或概念的模型的过程，以便能够使用模型预测类标号 未知的对象类。预测是构造和使用模型评估无标号样本类，或评估给定样本可能具有的属 性值或值区间。分类和预测之间的区别在于，分类是预测类标号( 或离散值) ，丽预测是建 立连续值函数模型。例如，可以建立一个分类模型，对银行贷款的安全或风险进行分类； 同时可以建立预测模型，给定潜在顾客的收入和职业，预测他们在计算机设备上的花费。 4 、聚类分析 聚类将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相似度， 而不同簇中的对象差别较大。与分类不同的是，它要划分的类是未知的。 5 、孤立点分析 在数据库中经常存在一些数据对象，它们不符合数据的一般模型。这样的数据对象被 称为孤立点，它们与数据的其他的部分不同或不一致。孤立点可能是度量或执行错误所导 致的。例如，数据库记录中有一些人的年龄是一9 9 9 ，这可能是这些人年龄没有被记录，而 系统给未记录的年龄的缺省值就是一9 9 9 。孤立点也可能是固有的数据变异后的结果。例如， 一个公司总裁的薪水可能远远高于其他职员的薪水，他的薪水就成为了一个孤立点。在许 多时候，孤立点被视为噪声或遗产而被丢弃，但是，在一些应用中，孤立点可能会很有用。 例如，在医疗分析中，某些对多种治疗方式的不寻常的反应数据可能成为孤立点，但是这 基于关联规则的数据挖掘算法研究 些数据对于治疗却非常重要。对孤立点数据进行分析称为孤立点分析。 6 、演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。这种分析可 能包括时间相关数据的特征化、区分、关联、分类或聚类，但是它的不同特点包括时间序 列数据分析、序列或周期模式匹配和基于类似性的数据分析。 2 2 2 数据挖掘的分类 从不同的角度看，数据挖掘技术有几种分类方法：根据发现知识的种类进行分类；根 据挖掘的数据库的种类进行分类和根据采用的技术分类。 1 、根据发现知识的种类分类。这种分类方法有：总结幅u m m a r i z a t i o n ) 挖掘、特征 ( c h a r a c t e r i z a t i o n ) 挖掘、关联( a s s o c i a t i o n ) 挖掘、分类( c l a s s i f i c a t i o n ) 挖掘、聚类( c l u s t e r i n g ) 挖掘、趋势c n e n d ) 分析、偏差( d e v i a t i o n ) 分析、模式( p a t t e ma n a l y s i s ) 分析等。如果以挖掘 知识的抽象层次划分，又有原始层次( p r i m i t i v el e v e l ) 的数据挖掘、高层次( h i g hl e v e l ) 的 数据挖掘和多层次( m u l t i p l el e v e l ) 的数据挖掘。 2 、根据挖掘数据库的类型分类。数据挖掘基于的数据库有：关系型( r e l a t i o n a l ) 事务 型( t r a n s a c t i o n a l ) 、面向对象型( o b j e c t - o r i e n t e d ) 、主动型( a c t i v e ) 、空间型r s p a t i a l ) 、文本 型( t e x t ) 、多媒体( m u l t i - m e d i a ) 、异质( h e t e r o g e n e r o u s ) 数据库等等。 3 、根据采用的技术，最常用的数据挖掘技术有： 人工神经网络：它从结构上模仿生物神经网络，是一种通过训练来学习的非线性预测 模刑。可以完成分类、聚类、特征挖掘等多种数据挖掘任务。 决策树：用树型结构来表示决策集合。这些决策集合通过对数据集的分类产生规则。 典型的决策树方法有分类回归树。 遗传算法：是一种新的优化技术，基于生物进化的概念设计了一系列的过程来达到 优化的目的。这些过程有基因组合、交叉、变异和自然选择。为了应用遗传算法，需要把 数据挖掘任务表达为一种搜索问题而发挥遗传算法的优化搜索能力。 最邻近技术：这种技术通过k 个与之最相近的历史记录的组合来辨认新的纪录。也称 k 一最邻近方法。这种技术可以用作聚类、偏差分析等数据挖掘任务。 规则归纳：通过统计方法归纳、提取有价值的i f - t h e n 规则。规则归纳的技术在数据 挖掘中被广泛使用，例如关联规贝挖掘。 可视化：采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策者，决策者 可以通过可视化技术交互式的分析数据关系。 2 3 数据挖掘面临的主要问题 基于关联规则的数据挖掘算法研究 数据挖掘面临的主要问题有三大类：挖掘方法和用户交互的问题、性能问题和存储数 据的数据库类型具有多样性的问题。 1 、挖掘方法和用户交互问题 这类问题涉及到数据挖掘技术的多个方面，主要有以下一些内容： 在数据库中挖掘不同类型的知识：由于不同的用户感兴趣的知识类型可能会很不相 同，这就要求数据挖掘系统应当覆盖范围很广的数据分析和知识发现任务，包括数据特征 化、区分、关联、分类、聚类、趋势和偏差分析以及类似性分析。这些方式可能以不同的 方式使用相同的数据库，并需要开发大量的数据挖掘技术。 多个抽象层的交互知识挖掘：由于在进行数据挖掘之前很难知道将要挖掘出来的是 什么样的知识，因此需要数据挖掘的过程具有交互性。对于大型的数据库，应当使用抽样 技术进行交互式的数据探查。交互式挖掘允许用户聚焦搜索模式。根据返回的结果提出和 精炼数据挖掘请求，从而使用户可以以不同的粒度和从不同的角度观察数据和发现模式。 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现过程，并使 得发现的模式以简洁的形式在不同的抽象层表示。关于数据库的领域知识，如完整性约束 和演绎规则，可以帮助聚焦和加快数据挖掘过程，或评估发现的模式的兴趣度。 数据挖掘查询语言和特定的数据挖掘：与现在存在大量的高级程序开发语亩相比， 数据挖掘还缺乏一门统一的高级语言用于描述数据挖掘的过程和结果。关系查询语言f 如 s q l l 只能允许用户提出特定的数据检索查询，而对数据挖掘高级语言的要求则更高，它 应该能够使用户通过说明分析任务的相关数据集、领域知识、所挖掘的数据类型、被发现 的模式必须满足的条件和约束，描述特定的数据挖掘任务。这种语言应当与数据库或数据 仓库查询语言集成，并且对于有效的、灵活的数据挖掘是优化的。 数据挖掘结果的表示和显示：高级语言、可视化表示或其他形式的表示方法可以使 知识易于理解，能够被人们直接使用。这要求系统采用有表达能力的知识表示技术，如树、 表、规则、图、图表、交叉表、矩阵或曲线等。 处理噪声和不完全数据：存放在数据库中的数据可能反映嗓声、异常情况或不完全 的数据对象，它们可能搞乱分析过程，导致数据与所构造的知识模型过分适应，由此导致 所发现的模式精确性很差。这就需要处理数据噪声的数据清理方法和数据分析方法，以及 发现和分析异常情况的孤立点挖掘方法。 模式评估兴趣度问题：数据挖掘方法发现的模式通常数以千计，怎样从中选择出 用户感兴趣的模式是一个极具拂战性的问题。 2 、性能问题 9 基于关联规则的数据挖掘算法研究 数据挖掘算法的有效性和可伸缩性：数据挖掘算法的有效性要求算法的运行时间应 尽可能地少，而可伸缩性则要求算法能够适应不同大小的数据库容量，算法的运行时间应 尽可能地与数据库的容量保持线性比例的增减关系。 并行、分布式和增量挖掘算法：并行和分布式数据挖掘算法将数据划分成多个部分， 这些部分可以并彳亍处理，然后将各个处理结果合并；这_ 种类型的算法可以对付数据库的大 容量、数据的广泛分布和一些数据挖掘算法的计算复杂性的问题。而数据挖掘过程的高花 贽导致了对增量挖掘算法的需求，这种类型的算法和数据库更新结合在一起，它不必随着 数据库的更新重新挖掘全部数据，而只需要在原有挖掘结果的基础上修正和加强已发现的 知识。 3 、关于数据库类型的多样性问题 关系的和复杂的数据类型的处理：由于数据库类型的多样性，指望一个系统挖掘所 有类型的数据是不现实的。为挖掘特定类型的数据，应当构造特定的数据挖掘系统。 由异种数据库和全球信息系统挖掘信息：局域网和广域网( 如互连网) 提供了大量庞 大的、分布式的和异种的数据库。从具有不同语义的结构化的、半结构化的和非结构化的 不同数据源发现知识，是数据挖掘技术面临的一个巨大挑战。 2 4 数据挖掘的研究与开发方向 数据挖掘现在是数据库研究、开发和应用最活跃的分支之一，它涉及了计算机科学中 的多个领域，这些领域包括传统的数据库技术、人工智能、机器学习、神经网络、统计学、 模式识别、知识库系统、知识获取、信息提取、高性能计算和数据可视化等学科。随着这 些学科的不断发展，数据挖掘也需要不断的发展。作为- f - j 新兴的技术，数据挖掘的发展 也应适应科技发展大潮流的需要。针对数据挖掘现在面临的主要问题，数据挖掘的研究与 开发最主要的方向有以下些： 与数据仓库与在线分析处理技术结合：数据仓库可以为在线分析处理和数据挖掘提 供经过滤化的、完整的数据资源。在线分析处理可以看作为一个简化的对数据进行聚合的 数据挖掘形式。与在线分析处理工具相结合，一个数据挖掘器( d a t am i n e r ) 能够深入到一个 数据立方体( a a t ac u b e ) 的任意维，从而在不同的抽象层上找到用户感兴趣的形式，由此 也增加了数据挖掘与数据仓库系统的用途。 挖掘多种类型的知识：数据挖掘除了最常见的分类与关联之外，还有许多重要的任 务待开发，包括描述、比较、聚合、预测模型以及时间相关形式分析等等。 提供对数据挖掘的查询语言和高效、交互式及特殊数据挖掘的支持：与相关语言类 似，高层次的数据挖掘语言应该能够允许用户定制特殊的数据挖掘任务。 1 0 基于关联规则的数据挖橱算法研究 处理复杂数据：挖掘关联性和事务性的数据是目前数据挖掘的中心。但是对于半结 构化以及非结构化的数据进行挖掘，也是一个非常重要而极富挑战性的方面。 高性能的数据挖掘：高效性和可伸缩性是目前数据挖掘算法的焦点，随着并行的、 分布式的以及增长式的数据挖掘技术的发展，这种趋势将会继续得到发展。 可视化和数据挖掘：数据库内容和数据挖掘结果的可视化可以帮助用户理解和评估 挖掘结果，从而对数据挖掘进行相应的调整。对交互式的挖掘来说，开发易用与易看的工 具是个很有发展空间的领域。 数据挖掘的应用：如何将数据挖掘技术应用于现实世界也是一个非常重要的课题。 基于关联规则的数据挖橱算法研究 第三章关联规则算法研究 关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由a g r a w a l 等人于1 9 9 3 i l j 年提出了挖掘交易数据库中项集问的关联规则问题，关联规则是发现数据库中不同商品 ( 项) 之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的 影响。一个典型例子是购物篮分析p l 。该过程通过发现顾客放入其购物篮中不同商品( 图 3 i ) 之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这 种关联的发现可以帮助零售商制定营销策略。例如，在同一次去超级市场，如果顾客购买 牛奶，他也购买面包( 和什么类型的面包) 的可能性有多大? 通过帮助零售商有选择地经 销和安排货架，这种信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进 步刺激一次去商店同时购买这些商品。 购物篮 幽癌曲 顾客1顾客2顾客3 顾客n 图3 1 购物篮分析 3 1 关联规则的基本概念 一个事务数据库中的关联规贝q 挖掘可以描述如下： 设1 = ，乏，) 是一个项目集合。设任务相关的数据d 是数据库事务的集合，其 中每个事务t 是项目的集合，使得r 妄，。每一个事务有一个标识符，称作t i d 。设a 是 个项集，事务t 包含a 当且仅当爿量t 。关联规贝# 是彤如a j b 的蕴涵式，其中彳c ， b c ，并且a n b = o 。规则a b 在事务集d 中成立，具有支持度s u p p o r t ，其中s u p p o r t 是d 中事务包含a u b ( 即a 和b 二者) 的百分比。它是概率p ( a u b ) 。规则a j b 在事务集d 中具有置信度c o n f i d e n c e ，如果d 中包含a 的事务同时也包含b 的百分比是 c o n f i d e n c e 。这是条件概率p ( bia ) 。即是 s u p p o r t ( a 等b ) = p ( a t , 3 b ) 基于关鞋规劓的数据挖掘算法研究 c o n f i d e n c e ( a j b ) = p ( b f a ) = s u p p o r t ( a u b ) s u p p o f t ( a ) 挖掘关联规则的问题就是找出这样一些规则，它们的支持度和置信度分别大于用户指 定的最小支持度阚值( r a i n _ s u p ) 和最小置信度闽值( m i n _ c o n f i ) ，将这样的规则称作强 规则。为方便计，我们用o 和1 0 0 之间的值而不是用0 到1 之间的值表示支持度和置信 度。 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集称为k - 项集。集合 c o m p u t e r ， m a n a g e m e n ls o i t w a r e 是一个2 项集。项集的出现频率是包含项集的事务数，简称为项集 的支持计数。项集满足最小支持度m i n _ s u p ，如果项集的出现频率大于或等于m i n _ s u p 与 d 中事务总数的乘积。如果项集满足最小支持度，则称它为频繁项集( f r e q u e n t r e m s e t ) 。 频繁k 项集的集合通常记作l k 。 例如用关联规则来表示上述购物篮分析的具体应用情况，购买牛奶的同时趋向于购 买面包的具体情况可以用如下的关联规则来表示： 面包j 牛奶( 支持度= 7 5 ，置信度= 7 5 ) 规则的支持度与置信度是衡量规则兴趣度的两个度量。支持度用于衡量规则的有用 性，7 5 的支持度表示了占全部事务总数的7 5 的事务同时购买了牛奶和面包。置信度用 于衡量规则的确定性，7 5 的置信度表示了购买牛奶的顾客中有7 5 的顾客同时又购买了 面包。如果上述的支持度和置信度的值均大于事先给定的支持度阀值和置信度阀值，那么 这个关联规则就是有趣的。 3 2 关联规则的种类 我们将关联规则按不同的情况进行分类n ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔类型关联 规则处理的值都是离散的、种类化的；而数值型关联规则可以和多维关联或多层关联规则 结合起来，对数值型字段进行处理，当然数值型关联规则中也可以包含种类变量。 例如；性别= “女”j 职业= “秘书”，是布尔型关联规则；性别= “女”a v g ( 收 ) k ) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。本文正是基于所处理变 量的类别提出了两个挖掘算法。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层的关 联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的关 联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机；s o n y 打印机，是一个细节数据上的单层关联规则；l b m 台式视 号s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 基于关联规则的数据挖掘算法研究 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维的关 联规则中，我们只涉及到数据的一个维；而在多维的关联规则中，要处理的数据将会涉及 多个维。 例如：啤酒j 尿布，这条规则只涉及到用户的购买的物品；性别= “女”等职业= “秘 书”，这条规则就涉及到两个字段的信息，是两个维上的条关联规则。 给出了关联规则的分类之后，在以后的分析过程中，就可以考虑某个具体的方法适用 于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。 3 3 关联规则挖掘的经典算法一a p r 南r i 算法 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集闻的关联规则问题，其 核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了 大量的研究。 3 3 1 关联规则挖掘步骤 a g r a w a l 等在1 9 9 3 年设计了一个基本算法，提出了挖掘关联规则的一个重要方法， 这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计可以分解为两步过程： ( 1 ) 找出所有频繁项集 通过用户给定的m i n _ s u p ，寻找所有频繁项集，即满足s u p p o r t 不小于r a i n _ s u p 的项 集。事实上，这些频繁项集可能具有包含关系。一般地，我们只关心那些不被其它频繁项 集所包含的所谓频繁大项集( f r e q u e n tl a r g ei t e m s e t ) 的集合。这些频繁大项集是形成关联规 则的基础。 ( 2 ) 由频繁项集产生强关联规则 通过用户给定的m i n _ c o n f i ，在每个最大频繁项集中，寻找c o n f i d e n c e 不小于r a i nc o n f i 的关联规则。 这两步中，第二步最容易。挖掘关联规则的总体性能由第一步决定。第一步是近年来 关联规则挖掘算法研究的重点。 3 3 2 发现频繁项目集算法- a p r i o r i 算法l i i i 该算法的主要思想是频繁项集的任何非空子集必定也是频繁的，换句话说，任何非频 繁项集的超集必定是非频繁的。如果项集 b e c r ，d i a p e r ，n u t s ；，那么项集 b e e r ， d i a p e r 也一定是频繁的。这一性质极大的降低了候选项集求解的规模，提高了算法的效率， 尤其当k = l ，2 时。 a p d o f i 性质：频繁项集的任何非空真子集必定也是频繁的，非频繁项集的任何其超 集必定不是频繁的。 1 4 基于关联规则的数据挖掘算法研究 a p r i o r i 算法由l b j 找k 的过程可以分为连接和剪枝两步，a p r i o r i 性质的应用大幅减 少了候选项集的产生。 连接步：为找l k ，通过l k j 与自己连接产生候选k - 项集。该候选项集记作c k ，执行连 按l k 1 + l k - l ；其中l k - 1 的元素是可连接，如果它们有( k - 2 ) 个相同的项，即l k i + l t 1 = a + b i a ， b l k q ，l a n b f = - k 一2 a 剪枝步：c k 是l k 的超集：即，它的成员可以是也可以不是频繁的，但所有的频繁k - 项集都包含在c k 中。扫描数据库，确定c k 中每个候选项集的计数，从而确定l k ( 即，根 据定义，计数值不小于最小支持度的所有候选项集是频繁的，从而属于l k ) 。然而，c k 可 能很大，这样所涉及的计算量就很大。为压缩c k ，可以用以下办法使用a p r i o r i 性质：任 何非频繁的( k - 1 ) 一项集都不可能是频繁k 一项集的子集。因此如果一个候选k _ 项集的( k 1 ) ， 项子集不在l k 1 中，贝该候选项集也不可能是频繁的，从而可以由c k 中删除。 算法1 ( a p r i o d ) 使用逐层迭代找出频繁项集 输入：事务数据库d ；最小支持度阈值 输出：d 中的频繁项集l 方法： 1 ) b e g i n 2 ) l l = l a r g e1 - i t e m s e t ；产生成含有1 个项目的频集， 3 ) f o r ( k = 2 ；l k 一1 m “+ + ) d o 4 ) b e g i n 5 ) c k a p r i o r i - g e n ( l k 1 ) ； 6 )f o ra l lt r a n s a t i o nt dd o 7 ) b e g i n 8 ) c t = s u b s e t ( c k ，t ) ：产产生事务t 中包含的k 项目集c 。+ 9 )f o r a l lc a n d i d a t e c c f d o 1 0 ) c c o u n t + + ；p 计数+ 1 1 ) e n d ； 1 2 ) l k = c c kjc c o u n t r a i n _ s u p ) 1 3 ) e n d ： 1 4 ) a n s w e r = u k l k ； 1 5 ) e n d 下面描述如何产生候选项集： 基于关联规则的数据挖掘算法研究 假定在l 卜l 中项目按某一次序排列，候选项集产生由如下两步组合而成 连接步：a p f i o r i g e n ( l k - 1 ) 的j o i n 算法步骤 b e g i n i n s e r ti n t oc k s e l e c tp i t e m l ，p i t e m 2 ，p i t e m k 1 ，q i t e m k _ l f r o m l k 4 p ，l k 1 q w h e r e