（产业经济学专业论文）关联规则的挖掘及其在商业决策中的应用分析.pdf

对丹经济贸易大学硕士论文 摘要 数据挖掘就是从大量数据中提取一部分有价值信息的一个过程，关联规则作为数 据挖掘研究的一个重要分支，在数据挖掘的知识模式中是比较重要的一种，关联规则 挖掘可以发现大量数据项之间有趣的关联和相关联系，通过大量商务事务记录中发现 有趣的关联关系，可以帮助许多商务决策的制定。由于关联规则形式简洁、易于解释 和理解并可以有效的捕捉数据间的重要关系，从大型数据库中挖掘关联规则的问题已 经成为近年来数据挖掘研究领域中的一个热点，也取得了可喜的进步，探索出了许多 独具特色的理论体系。 本文旨在将关联规则理论作为有价值的技术应用于真实世界数据中，来解决现实 商业问题。它首先介绍了关联规则挖掘研究的现状以及研究的目的和意义，并给出数 据挖掘的体系结构和运行过程。接着详细描述了关联规则挖掘的基本理论和经典关联 规则挖掘算法a p r i o r i 算法，通过分析和说明，导出了关联规则的支持度和信任度这两 个阈值，采用经典的a p r i o r i 方法来挖掘有价值的规则。最后从电影评分分析领域以 一组电影评分数据集为基础，通过数据的预处理和对数据挖掘软件工具的选择，对关 联规则的挖掘在商业决策中的应用傲了一定的研究，这个研究主要就是通过分析顾客 的评分行为，从顾客看过且评分较高的的电影与电影之间、顾客与电影之间两个方面 来挖掘关联关系，再对挖掘出来的规则做解释并为商业决策提供一些指导性建议，从 而将信息转化为知识接着进一步转化成为利润。 关键词：关联规则数据挖掘商业决策 对外经济贸易大学硕士论文 a b s 7 嗽c t d a t am i n i n gi sap r o c e s so fd i s c o v e r i n gv a l u a b l ek n o w l e d g ef z o maa b u n d a n to f i n f o r m a t i o n , a s s o c i a t i o nm l e sa sai m p o r t a n tb r a n c ho fd a t am i n i n g , i si m p o r t a n ti n k n o w l e d g em o d e lo f t h ed a t am i n i n g , i tc a l ld i s c o v e ri n t e r e s t i n ga s s o c i a t i o n sa n dc o r r e l a t i v e r e l a t i o n sw h i c h 锄h e l pm a k ed e c i s i o n sf o rb u s i n e s sd e c i s l o n - m a k e ra m o n gl a r g em l m b e r s o f d a t ai t e m si nb u s i n e s sn o t e t h ep r o b l e mo f m i n i n ga s s o c i a t i o nr u l e sf r o mh u g ed a t a b a s c h a sb e c o m eah o ts p o t , s i n c et h eb r i e f l y , e x p l a i n a b l e , u n d e r s t a n d a b l ea n de f f i c i e n c yo f c a t c h i n gi m p o r t a n tr e l a t i o n s h i pa m o n gd a t ao fa s s o c i a t i o nr u l e s , i th a sg r a t i f y i n gp r o g r e s si n e x i s t e do u t c o m e s ，e x p l o r e dm a n yi n d i v i d u a lt h e o r yf a c u l t i e s i nt h i s 耻i p w em a k ea s s o c i a t i o nr u l e sa sav a l u a b l et e c h n i q u et os o l v er e a lb u s i n e s s p r o b l e m sw i l ll a r g e l yd e p e n d0 1 1t h es u c c e s s f u la p p l i c a t i o no ft h i st e c h n i q u eo nr e s l - w o r l d d a t a i tf i r s ti n l r o d u c et h ed | ；s 豳伽o no f d a t am i n i n g , t h em a i nt e c h n i q u e s ，s y s t e ms 舡u c t i l 他 a n dr u n n i n g p r o c e s s ，t h e nd e s c r i b e sb a s i ct h e o r i e sa n da p r i o r ia l g o r i t h m so f a s s o c i a t i o nr i d e s m i n i n gp a r f i c 柚l a r l l y , t h m u g ha n a l y s i s a n de x p l a n a t i o n ,i tr e f e r st oc o n f i d e n c ea n d s u p p o r t a n c e a tl a s t , w ed os g ) m er e s e a r c ho nt h ea p p l i c a t i o no fa s s o c i a t i o nm i n i n gi n b u s i n e s sd e c i s i o nf r o mt h ed a mo ft h er a t i n gf o rf i l m s ，a f t e rt h ee x p l a n a t i o n so ft h e s e a s s o c i a t i o nr u l e sb e t w e e nf i l m sa n df i l m sa n db e t w e e ng u s t o m e r 8a n df i l m s ，g i v e8 0 m e g u i d a n c eo nb u s i n e s sd e c i s i o n i no r d e rt oo b t a i nab e t t e ra n dm o r ei m p r e s s e dd e c i s i o na n d t u r ni n f o r m a t i o ni n t ok n o w l e d g ea n di n t op r o f i l k e y w o r d s ：a s s o c i a t i o nr u l e s , d a t a m i n i n g , d e c i s i o n - m a k i n g 2 对外经济贸易大学硕士论文 第一章绪论 数据挖掘就是从大量数据中提取一部分有价值信息的一个过程，是一个融合了数 据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高 性能计算、以及数据可视化等最新技术的研究成果的多学科交叉研究领域，经过十几 年的研究，产生了许多新概念和方法，特别是最近几年一些基本概念和方法趋于清晰， 它的研究正向着更深入的方向发展。 1 1 研究背景介绍 随着计算机和自动化数据采集工具的广泛应用，在各种应用领域里的数据库中存 储了大量的数据，这使得人们对这些数据进行分析并转化为有用知识的需求变得越来 越迫切。于是知识发现与数据挖掘张w l e d g ed i s v 哪a n dd a i a m i n i n g k d d ) 1 自然成 为近年来人们从大型数据库中获取信息的一个重要的研究领域。一般地，数据挖掘就 是指从数据库或数据仓库中发现隐藏的、预先未知的、有趣的信息的过程，该过程可 以看作是知识发现过程中的一个核心的步骤：数据挖掘的主要功能包括，聚类 ( c l 蜘n g ) 、分类( c l a s s i f i c a t i o n ) 、预测( p r e d i c t i o n ) 、关联分析( a s s o c i a t i o na n a l y s i s ) 、 时间序列分析( t u n es e r i e sa n a l y s i s ) 等。 关联规则挖掘( ( a s s o c i a t i o n r u l e mi n i n g ) 是数据挖掘研究的一个重要分支，关联规则 是数据挖掘的众多知识类型中最为典型的一种。在1 9 9 3 年r a k e s h a g r a w a l 等首次提出了 关联规则挖掘的概念并给出了基于数据库多趟扫描的a i s 算法，此后关联规则由于其可 用性和易于理解的优点获得了广泛的关注和深入的研究，提高获取的关联规则的精确 度和执行效率成为研究的中心议题。a g r a w a l 其后提出了改进的a i s 算法a p r i 嘶， a p r i o r i t i d 及a p r i o r i h y b r i d ，成为众多关联规则算法的基础。2 获取高效率的主要方法是 在不牺牲或者很少牺牲大项集产生精确度的前提下尽量减少数据库数据的扫描次数。 最近也有独立于a 邸柳a l 的频集方法的工作，以避免大项集方法的一些缺陷，探索挖掘 关联规则的新方法。同时随着o l a p 技术的成熟和应用，将o l a p 和关联规则结合也成 了一个重要的方向。也有一些工作注重于对挖掘到的模式的价值进行评估，他们提出 的模型建议了一些值得考虑的研究方向。而在我国，许多单位也己开始进行数据挖掘 技术的研究，但从目前资料来看多还局限于基础技术和算法的研究。 目前，关联规则挖掘问题己经引起了数据库、人工智能、统计学、信息检索、可 视化及信息科学等诸多领域里的广大学者和研究机构的格外重视，并取得了不少的研 1f a y ”d u 啦妯州黔岫i n d 嘶崦t o w z 凼- 呻咄脑喊k i ) d 9 6 p m c 2 0 d m c o d o f l w 蜥 d i s c o r d 卸m 碰略从 l p _ 1 9 9 6 2f z k c s h a 舯w a l , t o m h z l m l c f i 吲d 。 f i m n s w 岫i ：m i 血雌 毒吐妇r n i b e t w e e ns e t s o f h 渊i n 姆m 旧蛔$ 1 g m o d c o n f 煳1 9 9 3 ：2 0 7 - 2 1 6 对外经济贸易大学硕士论文 究成果由于关联规则形式简洁、易于解释和理解并可以有效的捕捉数据间的重要关 系，从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘研究领域中的一个 热点。3 分析目前的研究和应用现状，应该在如下几个方面需要重点开展工作： _ s u p p o r t ( y ) ： ( 2 2 ) ( 2 ) 若x c y 。如果x 是非频集，则y 也是非频集 ( 3 ) 若x c = y ，如果y 是频集，则x 也是频集 定义2 4 若x ，y 为项目集，且x n y = 乃，蕴含式x - y 称为关联规则，x ，y 分别称为关 联规则x = y y 的前提和结论。项目集xu y 的支持度称为关联规则x = y 的支持度，记作： s u p p o r t ( x = y ) ， s u p p o r t ( x - y ) - - s u p p o r t ( 敬月)( 2 3 ) 关联规则x = y 的置信度记作：c o n f d e n c e ( x = y ) ， c o n f d e n c e ( x = y ) = s u p p o r t ( x u y ) s u p p o r t ( x ) x l00(2-4) 通常，用户根据实际挖掘，需要指定最小置信度。最小置信度记为m i n c o n f i d e n c e 。 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个 数据集中的统计重要性，后者用于衡量关联规则的可信程度。9 - 一般来说只有置信度和 可信度都较高的关联规则才可能是用户感兴趣、有用的关联规则。置信度高而支持度 低的关联规则说明其出现机会较少，是非重要的。支持度和置信度能比较直接地形容 关联规则的性质。从关联规则定义可以看出，任意给定事务中的两个项目集，他们之 间都存在关联规则，只不过属性值有所不同。如果不考虑关联规则的支持度和置信度， 那么在事务数据库中则可以发现无穷多的关联规则。 事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣。因此，为 9l h m 硼d m f a m l b c v d m m i n i ：c o m e p t 砌亿b i i i q 日a d c m i c 聃1 2 0 0 01 岫刚蛳g 油k 锄 s w i i m 粗k 咖晰柚d g 硎，如a d a m m 蛐唔f n u n e w o i k 断o p t i l 叫p r o d u c ts c l 6 i n r e t a i l 轴脚m 妇d 蛾 皿c g i i 捌p r o f s e t m o d e l i n p r o c e e d i n g s o f t h e a c ms e v e n t h i n t c m a f i o m l c o 疵k n 慨i g c d i m o v e r y a n d 嘶 m i n i n g , n c w y o d c a c m p f 瞄：3 0 0 - 3 0 4 6 对外经济贸易大学硕士论文 了发现有意义的关联规则，需要给定两个阈值：最小支持度( m i n s u p p o r t ) 和最小可信 度( m i n c o n f i d e n c e ) 前者即用户规定的关联规则必须满足的最小支持度，它表示了一 组商品集在统计意义上的需满足的最低程度：后者即用户规定的关联规则必须满足的 最小可信度，它反应了关联规则的最低可靠度。 定义2 5 若s u p p o r t ( x = y ) m i n s u p p o r tc o n f i d e n c e ( x - - - - - y ) m i n c o n f i d e n c e ， 称关联规则x y 为强规则，否则称关联规则x - y 为弱规则。 2 1 2 关联规则的分类 根据不同的标准，我们将关联规则按如下情况进行分类： ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关 联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系：而数值型关联 规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动 态的分割，或者直接对原始的数据进行处理例如：性别= “女”= 职业= “秘书”，是 布尔型关联规则；性别= “女”= a v g ( 收入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一 个数值型关联规则。 ( 2 ) 基于规则中数据的抽象层次，可分为单层关联规则和多层关联规则。”在单层 的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的：而在多 层的关联规则中，对数据的多层性已经进行了充分的考虑。例如： i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则； 台式和 l = s o n y 打印机，是一个较高层次和细节层次之问的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可分为单维的和多维的。在单维的 关联规则中，我们只涉及到数据的一个维，如用户购买的物品：而在多维的关联规则 中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性中 的一些关系；多维关联规则是处理各个属性之间的某些关系。 例如：啤酒= 尿布，这条规则只涉及到用户购买的物品，是单维关联规则； 性别= “女”= 职业= “秘书，这条规则就涉及到两个字段的信息，所以是一条多 维关联规则。 ( 4 ) 基于规则中涉及到的数据的确定性，关联规则可以分为确定的和模糊的。由于 客观世界的多样性和复杂性，许多事物难以用精确和确定的概念表示，所以就出现了 模糊关联规则。模糊关联规则中的数据项用模糊概念的语义项表示，表达自然，更能 反映商业语义。 例如：职业= “秘书”= 性别= “女”，这条规则只涉及到确定的数据项，是一条确 定性关联规则。注：此处的确定性并非指规则的置信度。 职业= “模特”= 个子= “高”，由于这条规则涉及到“高”这个模糊语义项，因此 1 0 抽w d h n 柚d y o , 瑶j m f u 1 ) i s c a v e l y o f m u 蚯p l e - l e v a a m m c i a t i o n r 妇f r o ml 越弘珐响蛔0 n 砌n 簪o f 2 1 u d i m e m a t i o u a l c o n f e m e o n v e r y t m g e d m a b z u r i , ：h , s w i z e d m 吐1 9 9 5 ：4 2 0 4 3 1 7 对外经济贸易大学硕士论文 是模糊关联规则 给出了关联规则的分类之后，在下面的分析过程中，我们就可以考虑某个具体的 方法适用于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。 2 2 关联规则挖掘的流程 1 2 1 挖掘环境 数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的，有效的， 可实用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘环境示意图如图2 1 图2 1 数据挖掘环境图 资料来源；本研究整理 2 2 2 挖掘过程 图2 2 描述了关联规则挖掘的基本过程和主要步骤： 图2 2 数据挖掘过程的步骤图 资料来源：本研究整理 挖掘过程中各步骤的大体内容如下： 首先确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最 后结果是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘则带 有盲目性，是不会成功的。有些问题的产生是显然的，如：开辟新产品的市场；为现 存的产品和服务定价；了解客户流失的原因同时和各种人员的交流也是很重要的， 当他们了解了数据挖掘之后，他们就有可能提出更好的问题。 其次是数据准备 数据准备阶段又分为三个步骤进行： 8 对外经济贸易大学硕士论文 ( 1 ) 数据的选择 搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据挖 掘应用的数据 ( 2 ) 数据的预处理 研究数据的质量，为进一步的分析傲准备，并确定将要进行的挖掘操作的类型。 ( 3 ) 数据的转换 将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的，建立一个 真正适合挖掘算法的分析模型是数据挖掘成功的关键。 第三步进行数据挖掘 对所得到的经过转换的数据进行挖掘。除了完善从选择合适的挖掘算法外，其余 一切工作都能自动地完成 以下一些情况可能影响数据挖掘的效果： 不好的数据格式。 另人费解的数据格式以及各个系统中数据含义的不一致。 缺少相应可以实照的功能。 挖掘出的结果缺乏充分的理由 企业内部组织的问题。 耗时太长。 第四步是结果分析 解释并评估结果。其使用的分析方法一般应视数据挖掘操作而定，通常会用到可 视化技术。 最后是知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 2 3 关联规则挖掘问题的分解 关联规则挖掘的任务就是要挖掘出数据集d 中的所有强规则。“从关联规则的概念 可知，关联规则挖掘的过程分成两个步骤。第一步，发现所有的频繁项目集，即支持 度大于给定最小支持度阈值的项集，这是关联规则挖掘的中心问题，也是衡量关联规 则挖掘算法的标准：第二步，根据所获得的频繁项目集产生关联规则，根据定义，这 些规则必须满足最小置信度阈值。 这里的第二步相对比较简单，一旦从数据库中产生了频繁集，则可以从中直 接产生强关联规则。 2 3 1 关联规则挖掘的基本模型 i ls b 血，k m 帅n i ，j d u 衄a n ds 1 虹d ，幡叫缸m 删i 啦m d i 埘叫i 鞠妇i n k s f o r 血mb 嗣蛔出饥h a c m s i c 融4 0 d 蛔舶删i o i 山q 州h o n t b c m 删舻嘲帅f d _ 叫j 1 1 9 9 7 9 对外经济贸易大学硕士论文 关联规则挖掘的基本模型可用图2 3 所示： 图2 3 关联规则挖掘的基本模型图 资料来源：本研究整理 图中d 为数据集，算法i 为频繁项目集的搜索算法，算法2 为关联规则的产生算法， r 为挖出的关联规则集合，用户通过指定m i n s u p p o r t 和m i n c o n f i n d e n c e 分别予算法1 和 算法2 角户，并通过与r 的交互对挖掘结果进行解释和评估 关联规则挖掘算法主要考虑的问题有以下两个； ( 1 ) 减少t i o 操作关联规则挖掘的数据集有时可达g b 甚至t b 数量级，频繁的i o 操 作必将影响关联规则的挖掘效率，减少如操作的方法主要是减少扫描数据集d 的次数； ( 2 ) 降低需要计算支持度的项目集( 常称之为候选项目集) 的数量，使其与频繁项目 集的数量接近。候选项目集数量的降低可以节省为处理部分候选项目集所需的计算时 间和存储空间。 2 3 2 发现频繁项目集 寻找大的项集的问题可以归纳成寻找所有含有给定置信度的规则的问题，也就是 说，若给定一个事务集合d ，我们就能给d 中的每个事务加入一个额外项目j ，然后寻找 那些在右侧有j 且置信度为1 0 0 的关联规则，从而找到大项目集。 发现所有大项目集的算法在数据上进行了多次遍历。在每次遍历中，从大项目集 的一个种子集合开始，并用这个种子集合产生新的潜在的大项目集，称为候选项目集。 在遍历数据的时候寻找对这些候选项目集有价值的支持。在遍历的最后，确定候选项 目集中的哪些确实是大的，然后它们就变成下一次遍历的种子。 这个进程持续直到找不到新的大项集。在第一次遍历中，计算单独项目的支持度， 并确定其中哪些是大的。这可看作是潜在大项目集的空间中的宽度优先搜索。 关于频繁项目集的发现算法将在论文后续部分作更为详细的研究。 2 3 3 由频繁项目集产生强关联规则 通过上面的论述，在从数据库d 中挖掘出频繁集合后，就可以获得相应的关联规则。 即产生满足最小支持度和最小信任度的强关联规则，可以利用公式( 3 1 ) 来计算所获 关联规则的信任度。 c o n f i d e n c e ( a = b ) = p ( bia ) = s u p p o r t c o u n t ( a u b ) s u p p o r t c o u n t ( a )( 2 1 ) s u p p o r t c o u n t ( a u b ) 为包含集合a u b 的交易记录数目； 1 0 对外经济贸易大学硕士论文 s u p p o r tc o u n t ( a ) 为包含集合a 的交易记录数目；基于上述公式，描述产生关联 规则的步骤： 对于每个频繁集合l ，产生其所有非空子集； 对于每个l 的非空子集s ， 若s u p p o r t c o u n t ( l ) s u p p o r t c o u n t ( s ) m i n _ c o n f 则产生一个关联规则“s = ( l s ) ”；其中m i n _ c o n f 为最小信任度阈值。 由于规则是通过频繁集合直接产生的，因此关联规则所涉及的所有集合均满足最 小支持度阅值。 推论2 1 对于项目集f 和其子集诵m ，若巨m ，则关联规则m ，= f m ，的置信度 不可能大于关联规则： f m 的置信度。 证明：因为m f ，m ，i f 且哐髓，由定理可知： s u p p o r t ( m ) s u p p o r t ( m ，) s u p p o r t ( f m ) s u p p o r t ( f - r e ) s u p p o r t ( j 一m 而s u p p o r t ( d = f 可) = s u p p o r t ( m 9 s u p p o r t ( f m 1 s u p p o r t ( m = h ) = s u p p o r t ( m ) 因此s u p p o r t ( m = f - m ) s u p p o r t ( m - f - m )得证 在根据频繁项目集产生强关联规则时，利用推论( 3 1 ) 可以减少计算量，进一步提 高强规则的产生效率。 2 4 关联规则挖掘经典算法 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集闻的关联规则问题一 a p r i o r i 算法，其核心方法是基于频集理论的递推方法。它是按项目集从小到大的顺序 寻找频繁项目集，是布尔关联规则挖掘算法中最成功的一类算法。它是层次算法的基 础，其核心技术为其他各类布尔关联规则挖掘算法广泛采用。以后诸多的研究人员对 关联规则的挖掘问题进行了大量的研究。他们的工作包括 对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则 的效率：提出各种变体，如泛化的关联规则、周期关联规则等，对关联规则的应用进行 了推广。 2 4 1 p r i o r i 算法基础 a p r i o r i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法a p r i o r i 算法 使用一种逐层搜索的迭代方法：设有数据集d ，算法在第一次遍历d 时仅仅计算每个项 目的具体值的数量，以确定频繁卜项目集，设大项集l 中包含的项目数为k 。随后的遍 历，以第k ( 1 k k ) 次为例，包括两个阶段。首先，使用在第( k 1 ) 次遍历中找到的大 对外经济贸易大学硕士论文 项集k ，和a p r i o r i - g e n 函数产生候选项集g ，这些候选项目集的所有子集必须都是频 繁项目集：然后扫插数据集，计算c 冲所有项目的支持度，并根据最小支持度确定所有 频繁k 一项目集的集合k ，即大型k - 项集。为提高频繁项集逐层产生的效率， p r i o r i 性 质可以用来有效的修剪候选项目集 a p r i o r i 性质：如果项目集x 是频繁项目集，则其所有的子集都是频繁项目集：如果 x 项目集是非频繁项目集，则其所有的超集( s u p p e r - s e t ，包含项目集x 的项目集) 都是 非频繁项目集。由定理可以很容易的验证该性质该性质属于一种特殊的分类，也称 作反单调性。意指如果一个集合不能通过测试，则它的所有超集也都不能通过相同的 测试。反单调性能迅速减值，提高搜索频繁项集的处理效率 如上述逐层迭代搜索算法，在用k 。，寻找l 的过程中，我们可以利用a p r i o r i 性质 修剪候选项目集q 来压缩搜索空间：任何非频繁的( k - 1 ) 一项集都不可能是频繁k - 项集 的子集。因此，如果一个候选k - 项集的( k - 1 ) 一项集不在k 中，则该候选项也不可能是 频繁的，从而可以从q 中删除。这种子集测试可以使用所有频繁项目集的散列树来快速 完成。 2 4 2a p r i o r i 算法描述 a p r i o r i 算法及其相关过程描述如算法2 1 所示： 算法2 1a p r i o r i 算法 输入：事务数据库d ，最小支持度阈值m i n s u p p o r t 输出：d 中的频繁项集l 。 处理流程：( 1 ) l i = l a r g e 卜i t e m s e t s j ；发现卜项集 ( 2 ) f o r ( k = 2 ：lk - i x ：k + + ) ( 3 ) c k = a p r i o r i g e n ( k 。) ： 新的候选集 ( 4 ) f o re a c ht r a n s a c t i o n st e d ( 5 )c t _ s u b s e t ( c bt ) ：事务t 中包含的候选集 ( 6 ) f o re a c hc a n d i d a t e sc c t ( 7 )c c o u n t + + ； ( 8 ) ( 9 ) l f c e & c c o u n t d l m i n s u p ) ( 1 0 ) ( 1 1 ) r e t u r nl ：u 山 p r o c e d u r ea p r i o r i g e n ( l h ) ( 1 ) f o re a c hp ek l ， ( 2 ) f o re a c hq k i ， ( 3 ) i f ( p i t e m l = q i t e m l ，) ( p i t e m k 一2 = q i t e m k - 2 ) ( p i t e m k 一1 cc o n f i d e n c e s 2 4 = 5 0 a a c = bc o n f i d e n c e s 2 4 = 5 0 b a c = ac o n f i d e n c e = 2 4 = 5 0 a = b a cc o n f i d e n c e = 2 6 = 3 3 b = i a a cc o n f i d e n c e = 2 7 - - 2 9 c = a a bc o n f i d e n c e = 2 ：7 = 2 9 如果最小信任度阈值为4 0 ，那么仅有第1 个、第2 个和第3 个规则，由于它们的 信任度大于最小信任度阈值而被保留下来作为最终的输出。具体说就是“同时购买a 和 b 的人就会购买c ；同时购买a ，c 的人就会购买b ；同时购买b ，c 的人也会购买a ”。 2 4 3 p r i o r j 算法的不足之处及改进 虽然a p r i o r i 算法自身已经根据a p r i o r i 性质裁减了候选集，进行了一定的优化， 但是还存在许多缺点，瓶颈主要集中在： 可能产生大量的候选集。当长度为l 的频繁项集有i 0 0 0 0 个的时候，长度为2 的候选 集个数将会超过1 僦。还有就是如果要生成一个很长的规贝i j 的时候，要产生的中闻元素 也是巨大量的。 对事务数据集的扫描非常频繁。从算法描述部分可以看出，在产生候选项目集的 时候，循环的每一步都需要扫描数据库，而与数据库建立连接及进行操作对于系统资 源的消耗是十分巨大的。如此频繁的操作势必降低算法的效率，造成系统的不稳定。 无法对稀有信息进行分析。由于频繁项集使用了参数m i n s u p ，所以就无法对小于 m i n s u p 的事件进行分析；而如果将m i n s u p 设成一个很低的值，那么算法的效率就成了 一个很难处理的问题。因此许多研究人员提出了很多优化算法。 ( 1 ) 基于划分的方法。 s a v a s e r ”等设计了一个基于划分( p a r t i t i o n ) 的算法，解决了挖掘大规模数据库 1 3j t a w o e 蛐h 啦删& n 删鼻 n c 疵缸蛳树m h 血畸- 并晌“m b 面呻d 蚰峨m 脚o f l k 2 1 。岫f 柚o a 耐* m o n v 日y 婚凸_ h 喇，l 对外经济贸易大学硕士论文 的问题。这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分 块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后 计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个 阶段只需被扫描一次而算法的正确性是由每一个可能的频集至少在某一个分块中是 频集来保证的。该算法可以高度并行的，可以把每一分块分别分配给某一个处理器生 成频集。产生频集的每一个循环结束后处理器之间进行通信来产生全局的候选k 一项 集。通常这里的通信过程是算法执行时问的主要瓶颈：而另一方面，每个独立的处理器 生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个哈希树来产 生频集。 ( 2 ) 基于h a s h 的方法。 由p a r k “等提出来的d h p 算法是一个高效地产生频集的基于哈希( h a s h ) 的算法。通 过实验发现寻找频集主要的计算是在生成频繁2 一项集l k ，p a r k 等利用了这个性质引入 哈希技术加速产生项集时的连接操作并且在挖掘的过程中按照a p r i o r i 性质对数据集 进行裁减。 ( 3 ) 基于采样的方法。 为了减少扫描数据库的次数，t o i v o n e n ”提出了基于采样的算法，先对数据库进行 采样，然后对得到的采样数据库来进行关联规则挖掘，并用数据库的剩余部分验证这 个结果。t o i v o n e n 的算法简单并显著地减少了i o 代价，缺点是产生的结果不精确，即 存在所谓的数据扭曲( d a t as k e w ) 。分布在同一页面上的数据时常是高度相关的，可能 不能表示整个数据库中模式的分布，由此导致采样5 的交易数据所花费的代价可能同 扫描仪一遍数据库相近。 l i n 和d u n h a m ”提出了反扭曲( a n t is k e w ) 算法来挖掘关联规则，使扫描数据库的次 数少于2 次，算法使用采样处理收集有关数据的次数以减少扫描遍数。 b r i n 等提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样 的方法使用更少的候选集，这些改进了算法在低层的效率。b r i n 的算法在计算k 一 项集时，当认为某个( k + 1 ) 一项集可能是频集时，就并行地计算这个( k + 1 ) 一项集的支 持度，算法需要的总的扫描次数通常少于最大的频集的项数，这里他们也使用了哈希 技术。 ( 4 ) 裁减数据集。 1 4s 呲，m ，s c 呱砌只s 抽d 硎v c h 出抽耐蛔触缸蛐g a 鲫i a 蛔椭p 幽鲫f a c m s l 4 3 m o d b m m m i 唯l c 棚矗嘲蛆岫瞄g 鼬吡o f 蝴艄1 7 5 - l 鲢幽- 啦 m 卸r l 螂 朽h t o “札s 蛐慨h 弘山叫柏缸。蚰= i | 豳n m 蛔n 蛐簪o f 曲吐知血疵蚰啦i c , c m f 删( m 珂l 越p d 耐曲n s d 刀b o , u t 删, m d i a ，s 印i 删口b 吖1 9 9 矗 1 6 工l u n - 棚m ， ld l 向i 虮m 缸啦a s 柏c h , t i m l l 山8 ：a n t i - s h w l l 即r 矗h 峨n 呻硎岫“也e i n t e z u 埘o n a l c 慨o f l d a t a b 唱面嚣砷g 【j 】，0 d a 山川堪氓f 曲n m l yl 钙) s 0 1 6 对外经济贸易大学硕士论文 a p r i o r i t i d 算法减少了用于未来扫描的数据集，原理是当一个事务不包含长度为k 的频繁项集，则必然不包含长度为k + l 的频繁项集。可以将这些事务裁减掉以减少在下 一次扫描中数据集的个数。 2 4 4 其他频集算法 上面我们介绍的都是基于a p r i o r i 的频集方法。即使进行了优化，但是a p r i o r i 方 法仍无法克服其固有的缺陷：可能产生大量的候选集；无法对稀有信息进行分析。 f p - g r o w t h 方法”采用不同于a p r i o r i 的思想，利用了分治法策略：第一遍扫描数 据库将数据库中的频集压缩构造一棵频繁模式树( f p - t r e e ) ，并保留其中的关联信息。 第二步把f p - t r e e 分化成一些条件库，每个库和一个长度为1 的频集相关。最后再对这 些条件库分别进行挖掘。当原始数据量很大的时候，可以结合划分的方法，使得一个 f p t r e e 树可以放入主存中。实验表明，f p - g r o w t h 对不同长度的规则都有很好的适应 性，同时在效率上较三l a p r i o r i 算法有巨大的提高。 第二个闯题的解决基于这样一个思想：a p r i o r i 算法得出的关系都是频繁出现的， 但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即使这些元素不 是频繁出现的在a p r i o r i 算法中，起决定作用的是支持度，而我们现在将把置信度放 在第一位，挖掘一些具有非常高置信度的规则整个算法基本上分成三个步骤：计算特 征、生成候选集、过滤候选集。在三个步骤中，关键的地方就是在计算特征时h a s h 方 法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误率和遗漏率。 基本的方法有两类：m i n e sh a s h i n g ( 姗) 和l o c a l i t ys e n s i t i v e e sh a s h i n g ( l s h ) m i n e h a s h i n g 的基本思想是：将一条记录中的头k 个为1 的字段的位置作为一个h a s h 函数。 l o c a l i t ys e n t i t i v eh a s h i n g 的基本想法是：将整个数据库用一种基于概率的方法进行 分类，使得相似的列在一起的可能性更大，不相似的列在一起的可能性较小。我们再 对这两个方法比较一下m e 的遗漏率为零，错误率可以由k 严格控制，但是时空效率相 对的较差。l s h 的遗漏率和错误率是无法同时降低的，但是它的时空效率却相对的好很 多。所以应该视具体的情况而定。 2 。5 相关分析和算法的改进 大多数关联规则的挖掘方法都利用了“支持度一信任度”的基本结构；尽管利用 最小支持阈值和最小信任阈值可以帮助消除或减少挖掘无意义的规则，但其所获得的 许多规则仍是无价值的。 本节将首先分析为何强关联规则仍是无意义的，或其误导性原因；然后将研究增 加相关分析的有关参数，以帮助确定关联规则的相关度。 无价值关联规则 1 7j i 叫删y 拖m 岫喀如m t p a m r n s 岫蛐g m e r a t i o m m p w c 2 0 0 0 a c m s l g m o d h c o u f m a n a g c m e a t o f 啪( s l g m o d 0 0 ) , d 山s , t x , m i y 2 0 0 0 0 1 7 对外经济贸易大学硕士论文 挖掘出一个规则是否具有价值取决于主观与客观两方面，因为是为应用服务的， 所以最终还是要由用户来确定一个规则是否有价值，显然这种判断可能是主观的，因 为它将随用户思维的不同而导致判断结果的不同；但是从客观上进行有价值的判断， 则是基于数据中所包含的具体信息来进行；作为向用户提供有价值规则( 剔除无价值 规则) 前进的第一步。 假如：分析超市中有关购买牛奶( m i l k ) 和可乐( c o k e ) 之间的交易关系。先假 设m i l k 代表包含牛奶的交易记录；而c o k e 则代表包含可乐的交易记录。见表3 2 ，交易 数据显示有6 ，0 0 0 条交易包含牛奶；有7 ，5 0 0 条交易包含可乐：有4 ，0 0 0 条交易记录既 包含牛奶又包含可乐假设利用客户设定的最小支持阈值3 0 和最小信任阈值6 0 所获 得的关联规则为；b u y s ( x ，。m i l k ”) = b u y s ( x “c o k e ”) ( 2 1 ) 其中由于规则( 2 1 ) 是一个强关联规则，因此它将会提供给用户它的支持度为4 ，0 0 0 1 0 ，0 0 0 = 4 0 ；它的 信任度为4 ，o o o 6 ，0 0 0 = 6 6 ；显然分别满足最小支持阈值和最小信任阈值的要求。但是 实际上规则( 2 1 ) 是一个误导( 错误知识) ，因为购买可乐的概率为7 5 ( 本身就) 大 于6 0 ( 最小信任阈值) 。事实上牛奶和可乐之间所存在关系是一种负关联，也就是购 买其中一个商品将会降低购买另一个( 商品) 的可能性 上述表明，规则a = b 的信任度是具有一定误导性的，因为它仅仅是在给定集合后， 对相应集合的个条件概率估计。实际上它并不能真正反映a 和b 之间的内在关联强 度。因此就需要寻找其它度量参数来弥补支持度一信任度基本关联挖掘结构在衡量有意 义数据关系方面所存在的不足 表2 2 有关牛奶、可乐交易数据列表 牛奶非牛奶合计 可乐 4 ，0 0 03 ，5 0 0 7 ，5 0 0 非可乐2 ，0 0 0 5 0 0 2 ，5 0 0 合计6 ，