（计算机应用技术专业论文）关联规则挖掘算法研究及其在crm中的应用.pdf

关联规则挖掘算法1 i j | 死及e “c r m 中的府用摘要 关联规则挖掘算法研究及其在c r m 中的应用 摘要 数据挖掘( 或知识发现) 出现于2 0 世纪8 0 年代末，目前已经成为人工智能 和数据库等领域的研究热点。它有着广阔的应用前景，并将在新的世纪里在各个 领域发挥其强大的生命力。r a g r a w a l 等在1 9 9 3 年提出了关联规则问题，现在 关联规则已经成为数据挖掘研究的重要方向，并且吸引了众多专家和学者的关 注。 本文比较研究了现有的关联规则挖掘算法如a p r i o r i 算法、增量式更新算法 等，发现存在问题有二，其中之一是当数据库中增加新的数据时，多数算法要重 新扫描整个大型数据库，效率较低。另一个问题是由于现有算法中项目集的支持 度是基于整个数据库计算的，当新增的数据中出现新项目时，即使包含新项目的 项目集频繁地出现，现有算法常把这些项目集作为非频繁项目集，由此产生的关 联规则不能反映最近的商业活动。 本文根据以上算法存在的问题，首先提出了一个新的概念敏感性，用来 衡量各种关联规则挖掘算法对新项目的重视情况。然后一方面从改进算法的时间 效率出发，引入一个参数c ( 1 c 。) ，根据旧数据集的支持度大于或等于 m i n s u p c 的频繁项目集和新增数据集发现频繁项目集，而不需扫描整个旧数据 集：另一方面从敏感性出发，对于只出现在新数据集中的频繁项目集，则直接作 为整个数据集的频繁项目集。紧接着本文通过实验把改进的算法与增量式更新算 法进行了比较分析。最后结合数据仓库知识，探讨了如何把关联规则应用于客户 关系管n ( c r m ) e p 。 关键词 数据挖掘，关联规则，数据仓库，客户关系管理 注：本项目获浙江省自然科学基金的资助( 资助号为6 0 1 0 7 6 ) 关联规则挖掘算法研究及其相- c r m 中的廊用 摘要 s t u d yo na l g o r i t h m0 fm i n i n ga s s o c i a t i o n r u l e sa n dt h ea p p l i c a t i o no fi ti nc r m a b s t r a c t d a t am i n i n go rk n o w l e d g ed i s c o v e r ye m e r g e di nt h el a t e1 9 8 0 sh a sb e c o m ea h o t s p o ti nt h ef i e l d s o fa r t i f i c i a l i n t e l l i g e n c ea n dd a t a b a s et e c h n o l o g y d a t am i n i n g h a si t sw i d ea p p l i c a t i o np r o s p e c ta n di se x p e c t e dt oc o n t i n u et of l o u r i s hi nt h en e w m i l l e n n i u m r a g r a w a le t c f i r s tp u tf o r w a r dt h ei s s u eo fm i n i n g a s s o c i a t i o nr o l e si n 1 9 9 3 n o wi th a sb e e na ns i g n i f i c a n tc o n t e n to f d a t am i n i n ga n ds od r a w sa t t e n t i o no f m a n y r e s e a r c h e r s a f t e rw eh a v es t u d i e de x i s t i n ga l g o r i t h m so fm i n i n ga s s o c i a t i o nr u l e ss u c ha s a p r i o r i ，i n c r e m e n t a lu p d a t i n ga l g o r i t h me t c ，t w op r o b l e m sa r ef o u n d o n eo f t h e p r o b l e m s i st h a tm o s to ft h ea l g o r i t h m sm u s ts c a nt h ew h o l el a r g ed a t a b a s ew h e nn e w d a t aa r ea d d e dt oi t s oi tw i l lm a k et h ed i s c o v e r i n gf r e q u e n ti t e ms e t sv e r ys l o w a n o t h e rp r o b l e mi st h a tt h ei t e ms e t sw h i c hi n c l u d e sn e w i t e m sw i l lb eo r e n r e g a r d e d a su n f r e q u e n ti t e ms e t se v e ni ft h e yh a p p e n e df r e q u e n t l yi nn e w d a t as e tb e c a u s et h e s u p p o r to f t h ei t e ms e t si sc a l c u l a t e db a s e do nt h ew h o l ed a t a b a s e s ot h ea s s o c i a t i o n r u l e sc o m ef r o ma b o v e f r e q u e n ti t e ms e t sc a n tr e f l e c tt h er e c e n t b u s i n e s sa c t i v i t y h a v i n g k n o w nt h ep r o b l e m so f e x i s t i n ga l g o r i t h m s ，f i r s tib r i n gf o r w a r da n e w c o n c e p t - - s e n s i t i v i t yt o m e a s u r eh o wm u c ht h ea l g o r i t h m st h i n k so ft h en e wi t e m s w h i c ha p p e a r e di nt h en e wd a t as e t t h e no nt h eo n eh a n dap a r a m e t e rc ( 1 c o 。、i s i n t r o d u c e df o ri m p r o v i n gt h ee f f i c i e n c yo ft h ea l g o r i t h m s d i s c o v e r i n gf r e q u e n ti t e m s e t sa r eb a s e do nt h ef r e q u e n ti t e ms e t s ( s u p p o r t m i n s u p c ) o f t h eo l dd a t as e ta n dt h e n e wd a t as e t ，n o to nt h ew h o l ed a t a b a s e o nt h eo t h e rh a n dt h i n k i n go ft h es e n s i t i v i t y , i ff r e q u e n ti t e ms e t so n l ya p p e a r e df r e q u e n t l yi nt h en e wd a t as e t ，t h e yw i l lb ed i r e c t l y a d d e dt ot h ef r e q u e n ti t e ms e t s i na d d i t i o ni m p r o v e da l g o r i t h mi sc o m p a r e dw i t h i n c r e m e n t a lu p d a t i n ga l g o r i t h mb y e x p e r i m e n t a tl a s tt h ea p p l i c a t i o no f a s s o c i a t i o n r u l e sj nc r mb a s e do nd a t aw a r e h o u s ei sd i s c u s s e d k e y w o r d d a t am i n i n g ，a s s o c i a t i o nr u l e s ，d a t aw a r e h o u s e ，c r m 关联规则挖掘算法研究及其在c i n 中的应用第一章绪论 1 ，1 数据挖掘 1 1 1 数据挖掘的提出 第一章绪论 随着信息技术的发展，人们收集和积累的数据越来越多，今天的我们会发 现自己陷入数据的海洋，无怪乎有人惊呼：“我们正被数据淹没，却饥渴于知 识”，在这种情况下，出现了如何从这些浩如烟海的数据中提取有用的信息， 为人们生活和社会发展的各方面提供正确决策的问题。如何才能不被信息的汪 洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢? 要想使数据真 砸成为一个企业的资源。只有充分利用它为企业自身的业务决策和战略发展服 务才行，否则大量的数据可能成为包袱，甚至成为垃圾。 许多企业在信息技术上投资很多，以帮助其更有效地管理业务并获得竞争 优势。在过去的三十年里，不断增长的商业数据以电子版的方式存储，存储的 数据在不断地增长，所耗费的存储空间也在相应地增长。尽管有如此丰富的数 据，许多企业还是无法充分地利用这些数据的价值，这是因为隐含在数据中的 信息不容易被察觉。例如，零售店储存每天各个顾客的详细购买信息，但是却 很难发现许多细微的购买模式。类似的，保险公司也储存了许多归档的历史信 息，但仍然很难发现可能存在的欺诈行为。 因此，面对“我们正被数据淹没，却饥渴于知识”的挑战，1 9 8 9 年8 月在 美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上首次出现 k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，知识发现或在数据库中发现知识) 这 个术语1 9 9 5 年提出了数据挖掘( d m d a t am i n i n g ) 概念作为知识发现过积 的关键步骤，但是现在人们不区分数据挖掘和知识发现两个概念，常用数据挖 掘来表示知识发现。目前数据挖掘蓬勃发展，将会越来越显示出其强大的生命 力。 数据挖掘是指从数据库或数据仓库中的数据非平凡地提取隐含的、以前未 知的、具有潜在应用价值的信息的过程j 。“非平凡”的意思是指采用一定的技 术和工具进行挖掘。数据挖掘技术是涉及统计学、数据库技术、人工智能和可 视化等学科的一门交叉学科，如图1 1 所示： 关联规则挖掘算法研究及其在c r m 中的应用 第一章绪论 图1 - 1 数据挖捌技术涉及的学科 随着信息技术的发展，传统的数据库已经无法满足大容量历史数据、不同 数据源的数据难以集成等问题，于是数据仓库技术应运而生。数据仓库之父w h i n m o n 在文献 3 8 中对数据仓库的定义是“数据仓库( d a t aw a r e h o u s e ，简称 d w ) 是一个面向主题的、集成的、非易失的且随时间变化的数据集合”。 随着数据仓库技术的发展，大量的数据被集成和预处理，由于数据仓库中 数据的质量较高，在数据仓库中进行复杂的数据分析成为可能，于是基于大型 数据仓库的数据挖掘技术的研究也得到空前的重视。把数据挖掘建立在数据仓 库之上，一方面能够提高数据仓库系统的决策支持能力；另一方面，由于数据 仓库完成了数据的收集、变换、集成、存储和管理工作，数据挖掘面对的是经 过初步处理的数据，从而使得数据挖掘能够更加专注于知识的发现，有利于发 挥数据挖掘技术的潜在能力。 数据挖掘技术允许计算机智能地去研究数据，它提供了一种新的与数据库 或数据仓库交互的方式，这使得它比普通的查询更加抽象、困难。数据挖掘技 术能够帮助用户发现以前未发现的却客观存在于商业中的模式，能够帮助企业 更有效地利用数据并获得有意义的信息，辅助企业决策，从而给企业带来竞争 优势。 在一份最近的c a r t n e r 报告中列举了在今后3 5 年内对工业将产生重要影响 的五项关键技术，数据挖掘就是其中的一项】。数据挖掘技术近年来得到迅猛 的发展，并且已经成为当今人工智能和数据库等领域的研究热点。 1 1 2 数据挖掘的典型分析方法 目前数据挖掘技术的典型的分析方法主要有关联规则、序列模式、分类、 聚类等方法。关联规则是用于发现数据库中各个项目集之间的关联。在数据挖 掘研究领域，对于关联规则的研究开展得比较深入，人们提出了多种关联规则 的挖掘算法，如a p r i o r i 、d h p 和增量式更新算法等。关联规则的目的是挖掘隐 关联规则挖掘算法研究及其在c r m 中的应用第一章绪论 城在数据中的各个项目集之间的相互关系，它能发现数掘库中形如“9 0 的顾 客在一次购买活动中购买商品a 的同时购买商品b ”之类的知识。 序列模式分析和关联分析相似，其目的也是为了挖掘数据之间的联系，但 序列模式分析的侧重点在于分析数据间的前后序列关系。它能发现数据库中形 如“在某一段时间内，顾客购买商品a ，接着购买商品b ，而后购买商品c ，即 序列a b c 出现的频度较高”之类的知识，序列模式分析描述的问题是：在 给定交易序列数据库中，每个序列是按照交易时间排列的一组交易集，挖掘序 列函数作用在这个交易序列数据库上，返回该数据库中出现的高频序列。 设有个数据库，该数据库中的每一个记录都赋予一个类别的标记，这样 的数据库称为示例数据库或训练集。分类分析就是通过分析示例数据库中的数 据，为每个类别做出准确的描述或建立分析模型或挖掘出分类规则，然后用这 个分类规则对其它数据库中的记录进行分类。举一个简单的例子，信用卡公司 的数据库中保存着各持卡人的记录，公司根据信誉程度，已将持卡人记录分成 三类：良好、一般、较差，并且类别标记已赋给了各个记录。分类分析就是分 析该数据库的记录数据，对每个信誉等级做出准确描述或挖掘分类规则，如“信 誉良好的客户是指那些年收入在5 万元以上，年龄在4 0 5 0 岁之间的人士”， 然后根据分类规则对其它相同属性的数据库记录进行分类。目前已有多种分类 分析模型得到应用，其中几种典型模型是线性回归模型、决策树模型、基本觌 则模型和神经网络模型。 与分类分析不同，聚类分析输入的是一组未分类记录，并且这些记录应分 成几类事先也不知道，聚类分析就是通过分析数据库中的记录数据，根据一定 的分类规则，合理地划分记录集合，确定每个记录所在类别。它所采用的分类 规则是由聚类分析工具决定的。聚类分析的方法很多，其中包括系统聚类法、 分解法、加入法、动态聚类法、模糊聚类法、运筹方法等。采用不同的聚类方 法，对于相同的记录集合可能有不同的划分结果。 聚类分析和分类分析是一个互逆的过程。例如在最初的分析中，分析人员 根据以往的经验将要分析的数据进行标定，划分类别，然后用分类分析方法分 析该数据集合，挖掘出每个类别的分类规则：接着用这些分类规则重新对这个 集合( 抛弃原来的划分结果) 进行划分，以获得更好的分类结果，这样分析人 员可以循环使用这两种分析方法直至得到满意的结果。 1 1 3 数据挖掘采用的技术 数据挖掘的研究领域涉及广泛，主要包括数据库系统、人工智能、机器学 习、统计学和数据可视化等领域，其采用的技术也较多，下面我们将对数据挖 掘中经常采用的技术做简单的介绍和分析。 关联规则挖掘算法研究及典礼c 蹦中的应用第一章绪论 在数据挖掘中，我们很少采用一种工具或技术。对于一个给定的闳题，数 据本身的特点会影响如何选择技术，因此，为了发现可能最好的模型，我们应 使用多种技术或工具。 1 神经网络 人工神经网络是模拟人类的形象直觉思维，是在生物神经网络的基础上， 根据生物神经元和神经网络的特点，通过简化、归纳、提炼总结出来的一类并 行处理网络。神经网络对于规模大而复杂的问题，如包含几百个相互作用的独 立变量，可以有效地建立模型，因此人们对神经网络非常感兴趣。它可用于解 决数据挖掘中的分类问题( 输出变量是离散的) 和回归问题( 输出变量是连续 的) 。 2 决策树 决策树的基本思想是它利用树的结构将数据记录进行分类，树的一个叶结 点就代表某个条件下的一个记录集，根据记录字段的不同取值建立树的分支； 在每个分支子集中重复建立下层结点和分支，便可生成棵决策树。 决策树是用一系列规则导出一类值的一种方法。例如，用决策树把贷款申 请者分成好的信用和不好的信用。图i 一2 是一颖用于解决这类问题的一棵简单 的决策树，它包含决策树的所有组成：决策结点、分支和叶子。 7 步5 少太。7 形。 g o o dr i s kb a dr l s kb a dr i s kg o o dr i s k 图i - 2 一棵简单的决策树 根结点是其中的一个组成部分，它说明正在进行的判断条件，图1 2 中的 根结点是“i n c o m e s 4 0 ，0 0 0 ”。判断的结果使树分成两个分支，每个分支代表各 种判断结果的答案。在图1 2 中，根据回答是“y e s ”或者“n o ”，而选择不同 的分支。 根据不周的算法，每个结点可选择两个或更多的分支。例如，c a r t 算法 中每个结点只产生两个分支。每个分支可以是一个决策树，也可以是叶子结点。 有了决策树和贷款申请，我们就能决定申请者是好的信用还是不好的信用。如 一位申请者“i n c o m e s 4 0 ，0 0 0 ”且“h i g h d e b t ”，那么就把他归于信用不好的一 类申请者中，同样如一位申请者“i n c o m e 5 y e a r s ”，那么就 把他归于信用好的一类申请者中。 决策树也能很好地处理非数值型的数据。它能接受分组的数掘，这能减少 关联舰则挖掘算法研究及其在c r m 中的应用 第一章绪论 数据转变的数量，并能使神经网络固有的独立变量的组合爆炸最小化。 3 遗传算法( g a ，g e n e t i c a l g o r i t h m ) 遗传算法就其本身来说并不是用来发现模式，只是用来指导其它数据挖掘 算法的学习过程，遗传算法为在解空间里寻找好的模型作指导。 遗传算法之所以这么称呼是因为它遵循生物进化的模式，把它们的特征 一代一代地遗传下去，直到找到最好的模型。被遗传的信息称为基因，它包含 所建立的模型的参数。 例如，在建一个神经网络对，遗传算法能替代反向传播的方法来调整权值。 在这种情况下，基因包含权值。另外，遗传算法能用来找到最佳构造，这时基 因包含隐含层的数目和每一层的结点数。 4 可视化技术 数据可视化技术经常和其它的数据挖掘技术结合起来用。它能够对数据进 行有效分析，其重要性是不能低估的。 可视化技术能够很好的工作是因为它不同予文本和数值，它能够用图形来 显示。它能让人们在树丛中看到森林和植物园。 除了以上的几种技术外，还有粗糙集、k n n ( k - n e a r e s t n e i g h b o r ) 等技术。 1 2 关联规则挖掘 关联规则的概念首先由r ，a g r a w a l 等人提出，是描述数据库中数据项之间 潜在关系的规则，目前已成为数据挖掘中非常重要的一个方向。关联规则挖掘 的对象一般是大型事务数据库。采用关联模型比较典型的案例是“尿布与啤酒” 的故事。在美国，一些年轻的父亲下班后经常到超市去买婴儿尿布，超市通过 对顾客的购物信息进行挖掘，发现了一条非常有用的规则：在购买婴儿尿布的 年轻父亲们中，有2 0 4 0 的人同时要买一些啤酒。超市随后调整了货架的行 访，把尿布和啤酒放在一起，结果销售额明显增加了。 关联规则，作为数据挖掘中的重要技术之一，诸多的研究人员对它进行了 大量的研究，他们的工作包括对原有的算法进行优化，如引入随机采样、并行 的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化的关联规则、 周期关联规则等，对关联规则的应用进行推广。 关于关联规则的详细内容见第二章。 1 3 现有关联规贝l l 挖掘算法肖存的阃题 关联规则挖掘算法研究及其在c r m 中的应用 第一章绻论 目前关于关联规则的研究有如下几个问题，如关联规则在处理海量的数据 时，如何提高算法效率的问题；如何挖掘迅速更新的数据；在挖掘的过程中， 如何提供一种与用户进行交互的方法，将用户的领域知识结合在其中；如何使 生成的结果更加可视化；如何把关联规则应用到实现中等等。 这里主要讨论的是算法的效率问题。在数据挖掘中，算法的效率是个非常 重要的问题。关联规则的挖掘过程分为频繁项目集的发现和关联规则的生成两 个步骤，而前者的时间代价非常大，它是影响整个算法的效率的关键所在。 现有算法如a p r i o r i 算法、增量式更新算法等在挖掘关联规则过程中主要集 中在频繁项目集的发现上。其中一个问题是，当交易数据库中增加新的数据时， 以上算法中的大部分都要重新扫描整个数据库，而数据库在不断地增大，花费 在扫描整个数据库的时间也会越来越长，效率的低下将会成为关联规则应用的 一个瓶颈。 另一个问题是，在计算各个项目集的支持度时，都是以整个交易数据集的 大小作为基数，这样导致的结果是，当交易数据集中增加新的数据，并且新数 据集中出现了新项目，即使包含新项目的项目集频繁地出现，这些算法却常把 这些项目集作为非频繁项目集，这不符合数据挖掘的新颖性的原则，而且根据 以上的频繁项目集得到的关联规则也不能反映真实的商业活动，由此降低了关 联规则在实际中的应用价值。 1 4 研究目的及论文组织 1 41 研究目的 关联规则已经成为数据挖掘技术的重要研究内容，并且将会在企业中发挥 强大的生命力。关联规则挖掘通常面向大型数据库，其算法的效率问题已经成 为关联规则应用的一个瓶颈。本文在研究已有关联规则挖掘算法的基础上，提 出了一个新的概念敏感性。用来衡量各种关联规则挖掘算法对新项目的重 视情况。从敏感度和时间效率出发对现有关联规则挖掘算法进行了改进。本文 还探讨了如何把关联规则挖掘算法应用于c r l v l 中，辅助企业管理客户。 本研究的目的是从以下几个角度出发， 1 从敏感性、时间效率等方面比较分析各种关联规则挖掘算法： 2 针对已有关联规则挖掘算法的不足，提出改进的关联规则挖掘算法并进 行仿真分析； 3 探讨数据挖掘技术及其关联规则挖掘算法在c r m 中的应用。 关联删则挖掘算法研究及其在c r m 中的应用第一章绪论 1 4 2 论文组织 本文首先提出了一个新的概念敏感性，用来衡量各种关联规则挖掘算 法对新项目的重视情况。然后从算法的效率和敏感度方面出发，对原有算法进 行了改进。最后讨论了如何把数据挖掘技术及其关联规则挖摁算法应用于客户 关系管理( c r m ，c u s t o m e rr e l a t i o nm a n a g e m e n t ) 中。 本论文的组织如下： 第一章，介绍数据挖掘的基本概念、数据挖掘的各种方法和技术，并分析 了现有的关联规则挖掘算法存在的问题； 第二章，介绍关联规则及其挖掘算法的基本概念； 第三章，对现有关联规则挖掘算法进行比较研究i 第四章，提出了用于衡量关联规则挖掘算法对新增项目重视情况的新的概 念敏感性，并且从敏感性、时间效率等方面总结了各种算法，然后提出并 实现了改进的关联规则挖掘算法； 第五章，首先对改进的算法和增量式更新算法进行仿真，然后分析两利，算 法的结果； 第六章，讨论数据挖掘技术及其关联规则挖掘算法在c r m 重的应用； 第七章，对本论文进行总结，并对关联规则的后续研究提出自己的看法。 关联规则挖掘算法研究及其在c r m 中的应用第二章关联规则挖掘问题描述 第二章关联规则挖掘问题描述 2 1 关联规则基本概念 2 1 1 支持度 关联规则是由r a g r a w a l 等人于1 9 9 3 年首先在文献 3 】中提出，关联规则是 知识发现和数据挖掘所要挖掘的一种重要的模式。关联规则挖掘是为了发现大型 数据库或交易数据集中频繁发生的项目子集，并且提取一个项目子集会如何影响 已存在的另一个项目子集的这些规则。 交易数据集d 的记录包含三个属性：序号( n u m ) 、交易编号( t i d ) 和用户 在交易中购买的项目( i t e m ) 。如表2 1 表示： 表2 - 1 交易数据库记录格式 n u mt i di t e m 1l0 21l 32o 421 522 632 734 836 在表2 1 中，序号( n u r n ) 是数据库中各条记录的唯一编号，交易编号( t i d ) 用 于区别各笔不同的交易，项目( i t e m ) 是在交易中用户购买的货物编号，不同的货 物编号对应不同的货物，如这些货物可以是锤子、钉子、钳子。 在数据库中通常一条记录只包含一个项目而每次交易通常包含多个项e 1 ， 所以对于一个交易编号 l i d 对应多条记录。如果把每笔交易看成一条记录，则可 用表2 2 直观她表示各笔交易： 表2 - 2 直观交易表 t i di t e m s e t l0 ，l 20 ，1 2 32 ，4 ，6 关联规则挖掘算法研究及其征c r m 中的应用第二章关联规则挖掘问题描述 1 d 表示数据库中事务d 的交易总笔数，即d 中不两 r i d 的项数，若t 是一 个项集，用 t f 表示项集的长度。如对交易编号t i d = l 的项集为 0 ，1 ，n t t t t i d = l = 2 。 定义1l b = t 1 ，t 2 ，t o 是一个数据集( 事务数据库) ，每个事务t i e d 且t 。= i 1 ， i 2 ，j f ，i p ) ( i = l ，2 ，n ) ，t ；中的元素i ，( j _ 1 ，2 ，p ) 称为项目 ( i t e m ) 。 定义2 设i = i j ，i 2 ，i m ) 是d 中全体项目组成的集合，i 中的任何子集x ( x c i ) 称为d 中的项目集( i t e m s e t ) ，l x l = k 称集合x 为k 项集。设t ：和x 分 别为d 中的事务和项目集，如果x e t 。，则称事务t i 包含项目集x 。 定义3 数据集d 中包含项目集x 的事务数称为项目集x 的支持数，记为a 。 项目集x 的支持度，汜为s u p p o r t ( x ) s u p p o r t 2 1 苛则o o a 若s u 即。r c ( x ) 不 小于用户给定的最小支持度( m i n s u p ) ，则称x 为频繁项目集( f r e q u e n ti t e m s e t ) ， 否则称x 为非频繁项目集。 由定义3 可知，支持度定义了各个项目集在整个交易数据库中所占的比例。 下面我们就以“锤子钉子，钳子”为例，在这个例子中有1 0 0 0 笔交易，各 个项目集的出现情况如下： 包含“锤子”：5 0 ： 包含“钉子”：8 0 ； 包含“钳子”：2 0 ： 包含“锤子”和“钉子”：1 5 ： 包含“钳子”和“钉子”：1 0 ： 包含“锤子”和“钳子”：1 0 ： 包含“锤子”、“钳子”和“钉子”：5 。 先对上面的表示作简单的说明，如第一条： 包含“锤子”：5 0 ， 它的意思是在1 0 0 0 笔交易中，有5 0 笔交易中包含“锤子”，对于第四条： 包含“锤子”和“钉子”：1 5 ， 它的意思是在t 0 0 0 笔交易中，有1 5 笔交易同时包含了“锤子”和“钉子”。 根据支持度的定义，我们可以j 导到其中的一部分项目集： 项目集( 锤子) 的支持度为s u p p o r t 锤子 = 5 0 1 0 0 0 = 5 ： 项目集( 钉子) 的支持度为s u p p o r t 钉子 = 8 0 1 0 0 0 = 8 ； 项目集( 钳子) 的支持度为s u p p o r t 钳子 = 2 0 1 0 0 0 = 2 项目集 锤子，钉子) 的支持度为s u p p o r t 锤子，钉子) = 1 5 1 0 0 0 = i 5 ： 项目集( 锤子，钉子，钳子) 的支持度为s u p p o r t 锤子，钉子，钳 子1 = 5 1 0 0 0 = 0 5 。 9 关联规则挖掘算法 i i f 究及其z i ：c r m 中的应用第二章羌联规则挖掘问题描述 如粟取最小支持度m i n s u p 为1 5 ，那么我们得到的部分频繁项目集为 锤 子) 、 钉子) 、 钳子 、 锤子，钉子) ，而 锤子，钉子，钳子) 因为其支持度小 于最小支持度，所以不是频繁项目集。 由支持度的定义可得到定理1 ： 定理1 设x ，y 是事务集d 中的项目集 ( 1 ) 若x g y ，贝0s u p p o r t ( x ) s u p p o r t ( y ) ； ( 2 ) 若x g y ，如果x 是非频繁项目集，则y 也是非频繁项目集： ( 3 ) 若x _ y ，若y 是频繁项目集，则x 也是频繁项目集【6 】。 2 1 2 关联规则 定义4 若x ，y 为项目集，则关联规则( a s s o c i a t i o nr u l e s ) 是如下定义的 蕴含式：x 寺y ，其中x c _ i ，y g i ，且x n y = m ex ，y 分别称为关联规则x j y 的前件和结论， 关联规则x j y 的支持度就是项目集( x u y ) 的支持度，即交易数据库中 包含x 和y 的交易数与交易总笔数之比，记为s u p p o r t ( x j y ) ，则 s u p p o r t ( x 毒y ) = s u p p o a ( x w y ) 。1 或 s u p p o r t ( x 毒y ) = l t ：x u y g t ，t e d i d i o 刮 我们以“锤子一钉子钳子”为例，如果取x = 锤子 。y = 钉子) ，那么我们 可以得到的关联规则为 锤子) j 钉子) ，其支持度s u p p o r t ( 锤子 j 钉 子 ) = s u p p o r t ( 锤子，钉子) ) = 1 5 ；如果取x = ( 锤子，钉子 ，y = 钳子) ，那么 我们可以得到关联规则为 锤子，钉子) j 钳子 ，其支持度s u p p o r t ( 锤子，钉 子) j 钳子 ) = s u p p o r t ( 锤子，钉子，钳子 ) = o 5 。 2 1 3 可信度 自关联规则的挖掘问题提出后，就不断有人指出关联规则的局限性，为了避 免生成“错觉”的关联规则，人们弓 入各种新的阈值以加强对关联规则臼勺评判， 以下是文献【3 5 提出的可信度的定义： 定义5 关联规则x j y 在交易集中的可信度是指包含x 和y 的交易数与包 含x 的交易数之比，记为c o n f i d e n c e ( ) ( j y ) ， c o n f i d e n c e f x ：y ) ：s u p p o r t ( x u y ) 1 0 0 6 1 。 7 s u p p o r t ( x ) 或 关联规则挖掘算法研究及t e d - c r m 中的应用第二章关联规则挖掘问题描述 c o n f i d e n c e ( x y ) 2 t ：x u y g t ，t d v i t ：x c _ t ，t e d 1 1 q 可定义5 可知，可信度定义了发现关联规则的强度。通常用户根据挖掘需要 指定的最小可信度记为m i n c o n f ，在产生关联规则时，选择可信度c o n f i d e n c e t m i n c o n f 的关联规则，而忽略那些可信度c o n f i d e n c e m i n c o n f 的关联规则。 我们还是以“锤子一钉子钳子”为例，如果取x = 锤子1 ，y = 钉子 ，那么 我们可以得到关联规则 锤子) j 钉子 ，其可信度c o n f i d e n c e ( 锤子) j f 钉 子 ) = s u p p o r t ( ( 锤子，钉子 ) s u p p o r t ( ( 锤子 ) = 1 5 唰5 = 3 0 ：如果x = 锤子，钉 子 ，y = 钳子 ，那么我们可以得到关联规则 锤子，钉子) j 钳子) ，其可信度 c o n f i d e n c e ( 锤子，钉子) j 钳子) ) = s u p p o r t ( 锤子，钉子，钳子) s u p p o r t ( 锤子，钉 子) = 0 5 1 5 。3 3 3 。如果我们取最小可信度m i n c o n f 为3 3 ，那么在以上的 两个关联规则中，由于关联规则 锤子，钉子) j 钳子 的可信度小于最小可信度 m i n c o n f ，所以该关联规则被忽略；而关联规则 锤子，钉子 ； 钳子 的可信度 大于最小可信度m i n c o n f ，所以它是满足最小可信度的关联规则。 214 兴趣度 除了使用支持度和可信度之外，关联规则的描述还存在不完善的地方，首先 是关联规则在其表达形式上没有考虑各秘可能的反面示例的影哟，因两导致知识 表达功能的不够完善：其次是有可能一条规则即使可信度和支持度都很高，仍没 有实际意义，甚至是误导性的。有人把兴趣度闽值运用到关联规则中来，并给出 其形式定义。 定义6 给定数据集d ，d 上的关联规则x j y 的兴趣度为 i：confidence(x j y)-support(x：*y) 6 0 1 ， m a x c o n f i d e n c e ( xjy ) ，s u p p o r t ( xjy ) 这个定义是由关联规则的支持度和可信度而产生的，分母上的 m a x c o n f i d e n c e ( xjy ) ，s u p p o r t ( xjy ) ) 只是个标准化因子，使得l i i s o n y 打印机，是一个细节数据上的单层关联规则；台式机j s o n y 打印机，是一个较高层次和细节层次之阔的多层关联规则。 关联伽则挖掘算法研究及其在c r m 中的应用第二章关联规则挖掘问题描述 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的商品；而在多 维的关联规则中，要处理的数据将会涉及多个维。也就是说，单维关联规则是处 理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如： 啤酒尿布，这条规则只涉及到用户的购买的物品；性别= “女”j 职业= “秘 书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 2 3 关联规则的应用领域 目前关联规则的主要用于菜篮子分析，交易数据库中的项目代表商品。具有 相同交易编号的记录构成一次交易，通过关联规则的挖掘可以了解客户的购买习 惯，由此商场可计划进什么商品、商品的位置该如何摆放等：在保险业中通过关 联规则挖掘可以找出索赔群体的特征：在金融业中，关联规则可用于识别欺诈行 为：关联规则的应用领域还包括商务领域、基因数据分析和仿真。最近王选文等 人在 1 8 中把关联规则成功地应用于人事信息中，为人事部门提供了决策支持信 息。 关联j ；! j l 则挖掘算法研究及其在c r m 中的应用第三章现有关联规则挖掘算法研究 第三章现有关联规则挖掘算法研究 3 1 关联规则挖掘问题分解 关联规则的挖掘算法很多，但所有的挖掘算法不论它是采用什么数据结构， 其复杂度、效率如何，都可以分为如下几个步骤： ( 1 ) 预处理与挖掘任务有关的数据。根据具体问题的要求对数据库进行相应 的操作，从而构成规格化的数据库d 。 ( 2 ) 针对d ，通过迭代检索出事务数据库中的频繁项目集l ，即支持度不低 于用户设定的最小支持度的项目集，即频繁项目集。 ( 3 ) 利用频繁项目集l 构造出满足用户最小可信度的规则【9 】，形成规则集并 用可视化方法进行输出。 在以上几个步骤中，第( 1 ) 、( 3 ) 步骤比较容易，目前大量的研究工作集中在( 2 ) 步骤，挖掘或发现所有频繁项目集是该算法的核心占据整个计算量的大部分， 所以影响算法效率的主要原因在于生成频繁项目集的过程。在生成频繁项目集的 过程中不可避免要扫描交易数据库，对数据的扫描伴随着繁重的i o 任务，算法 对数据库扫描的次数较多，大大限制了发现频繁项目集的速度，因此大量的工作 倾注在如何减少数据库的扫描次数，有效减少数据吞吐量上，很多关联规则挖掘 算法都是从这个角度来考虑的。接下去我们就讨论几种发现频繁项目集的算法。 3 2 经典频繁项目集方法a p r i o r i 算法 在现有的关联规则发现算法中，最著名的是r a g r a w a l 在他的a i s 算法基 础上于1 9 9 4 年提出的a p r i o r i 算法，其核心是基于频繁项目集理论的遂挂方法， 在介绍a p r i o r i 算法的基本思想之前，我们首先了解几个概念： ( 1 ) 候选k 项集：支持度可能大于或等于最小支持度的k 项集； ( 2 ) h ：所有频繁k 项集的集合： ( 3 ) c k ：所有候选k 项集的集合。 a p r i o r i 算法的基本思想是：对事务数据库进行多遍扫描，利用“在给定的 事务数据库d 中任意频繁项目集的子集都是频繁项目集；任意非频繁项目集的 超集都是非频繁项目集【6 l ”这一原理对事务数据库进行多遍扫描。 a g r a w a l 等 1 】在1 9 9 3 年设计了一个基本算法，提出了挖掘关联规则的一个重 要方法一个基于两阶段频繁项目集思想的方法，将关联规则挖掘算法的设计 关联规则挖掘算法研究及其在c r m 中的应用第三章现有关联规则挖掘算法研究 可以分解为两个子问题： ( 1 ) 找到所有支持度大于最小支持度的项目集，这些项目集就是频繁项目集。 ( 2 ) 使用第( 1 ) 步找到的频繁项目集产生期望的可信度大于或等于最小可信度 的规则。 这里的第( 2 ) 步比较简单直观，根掘频繁项目集的支持度，就可以求出各个关 联规则的可信度，找出可信度大于或等于最小可信度的关联规则即可。 关联规则挖掘的算法相当多，但绝大部分是经典算法a p r i o r i 的演绎和改进。 a p r i o r i 通过对数据库d 的多遍扫描来发现所有的频繁项目集，在每一趟扫描中 只考虑具有同一长度k ( 项目集中所含项目的个数) 的所有k 项集。 在第一趟扫描中，a p r i o r i 算法计算数据库d 中所有单个项目的支持度，生 成所有长度为1 的频繁项目集，在后续的每一趟扫描中，首先以前一趟中所发现 的所有频繁项目集为基础，生成所有新的候选项目集，即潜在的频繁项目集，然 后扫描d ，计算这些候选集的支持度，最后确定候选集中那些项目集真正成为频 繁项目集，重复上述过程直到发现不了新的频繁项目集为止。 为了生成所有频繁项目集，a p r i o r i 算法使用了递推的方法，其算法的框架f 7 】 如图3 1 所示，为简单起见，其中各个项目集的支持度用它的支持数来表示： 图3 - 1 a p r i o r i 算法 关联规则挖掘算法研究及其在c 踟中的应用 第三章现有关联规则挖掘算法珂f 究 其中a p r i o r i g e n ( l k _ 1 ) 部分的代码如图3 - 2 所示 图3 - 2 a p r i o r i g e n ( l ) 部分的代码 a p r i o r i 算法运用频繁项目集的子集必然是频繁项目集的思想，通过求得的 频繁项目集构成长度更长的项目集，并将其称为潜在频繁项目集，以后只需计算 潜在频繁项目集的支持度，而不必计算所有不同项目集的支持度，在一定程度上 减少了计算量，其过程如下： ( 1 ) 通过单趟扫描数据库d 汁算出各个l 项集的支持度，从而得到频繁1 项 集构成的集合l l ； ( 2 ) 为了产生频繁k 项集构成的集合l k ，预先生成一个潜在频繁k 项集的集 合c k ，l k _ c c k ，潜在频繁项目集的集合由联合( j o i n ) 运算实现。若p ，q e l k 1 ， p = p 1 ，p 2 ，p k 2 ，p k 1 ) ，q = q l ，q 2 ，q k 2 ，q k 1 ) ，并且当1 i m i n s u p ，则把1 放入l 中，否则就放弃1 为频繁项目集： ( 4 ) ( 4 ) 与( 3 ) 相类似，对于频繁项