（计算机软件与理论专业论文）数据挖掘中关联规则的优化.pdf

数据挖掘中关联规则的优化 摘要 数据挖掘是当前计算机学科的个前沿研究方向。作为一门应用性很强的新 兴技术，它存在很多值得研究的地方。如何合理的应用数据挖掘技术，如何针对 现实生活中的问题改进数据挖掘技术是其中的热点问题。 本文尝试从一个新的角度研究数据挖掘中关联规则的优化问题；加强支持度 羽i 信任度的定义，使其不用增加新的阈值就可以挖掘出无冗余、无虚假的关联规 则。现有的关联规则发现算法基本采用频繁k 项目集来生成候选k + 1 频繁项目 集。当交易数据库很大时，计算频繁项目集的时间较长，并且在降低支持度和信 任度时，关联规则数目会急剧增加，包含了大量的冗余规则，从而影响到整个算 法的效率。同时由于关联规则定义的局限性，使得生成的相当一部分关联规则是 虚假的、无意义的。针对这挖掘出来的问题，本文重新给出关联规则的形式定义， 提出了一个关联规则生成算法，该算法通过引入反向项目来加强支持度和信任度 的定义，并且通过简单冗余规则和严格冗余规则的定义来删除正向规则与反向规 则的冗余项，从而从整体上提高了挖掘出来的关联规则的质量。 【关键词】数据挖掘、关联规则、反向关联规则，冗余关联规则 一 茎堡丝塑! 茎壁塑型竺垡些 t i t l e ：a s s o c i a t i o nr u l e s o p t i m i z a t i o ni nd a t a m i n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：y a n g m i n s u p e r v i s o r ：v i c e p r o f e s s o ry i nj i a n a b s t r a c t t o d a y , d a t am i n i n gi so n eo f t h em o s tp o p u l a rt e c h n o l o g i e so f c o m p u t e rs c i e n c e a san e w t e c h n o l o g y , t h e r ee x i s tm a n yp r o b l e m sa b o u td a t am i n i n gt ob er e s e a r c h e d 。 h o wt ou s ei tc o r r e c t l y , h o wt om a k ea na p p l i c a t i o n ，a n dh o wt oi m p r o v ei t ，a l lt h e s e p r o b l e m s a t t r a c tc o m p u t e rs c i e n t i s t i nt h i sp a p e r , it r yt oi n v e s t i g a t et h eo p t i m i z a t i o no f t h ea s s o c i a t i o nr u l e si nd a t a m i n i n g o nan e w p o i n to f v i e w ：s t r e r i g t h e n t h ed e f i n i t i o no f s u p p o r ta n dc o n f i d e n c eo f t h ea s s o c i a t i o nr u l e s ，s ot h a tw ed o n tn e e dt oa d ds o m en e wt h r e s h o l dt om i n i n g a s s o c i a t i o nr u l e sw i t h o u tr e d u n d a n ta n df a l s e h o o d a l g o r i t h m si ne x i s t e n c ea b o u t a s s o c i a t i o nr u l e sd i s c o v e r ya d o p tf r e q u e n tk - i t e ms e tt oc r e a t ek 十1c a n d i d a t ei t e ms e t 。 i ft h eb u s i n e s sd a t a b a s ei sv e r yb i g ，t h et i m eo f c o u n t i n gf r e q u e n t i t e ms e tw i l lb e c o m p a r a t i v e l yl o n g ，a n d i fw er e d u c et h es u p p o r ta n dc o n f i d e n c e ，t h en u m b e ro f a s s o c i a t i o nr u l e sw i l li n c r e a s er a p i d l yw i t ham a s so fr e d u n d a n i f i e s t h i sw i l lt a k e d o w nt h ee f f i c i e n c yo f t o t a la l g o r i t h m a tt h es a m et i m e ，b e c a u s eo f t h er e s t r i c t i o no f a s s o c i a t i o nr u l e sd e f i n i t o n ，q u i t eab i to fr u l e sa r ef a l s ea n dm e a n i n g l e s s t h i sp a p e r p r e s e n t s an e wd e f i n i t i o no fa s s o c i a t i o nr u l e sa n dg i v e sa na l g o r i t h mo fm i n i n g a s s o c i a t i o nr u l e s t h i sa l g o r i t h ma s en e g a t i v ei t e mt os t r e n g t h e nt h ed e f i n i t i o no f s u p p o r t a n dc o n f i d e n c e ，a n dd e l e t er e d u n d a n c i e so f p o s i t i v ea n dn e g a t i v er u l e sb yt h e d e f i n i t i o no f s i m p l er e d u n d a n tr u l ea n ds t r i c tr e d u n d a n t r u l e i ta d v a n c et h eq u a n t i t y o f a s s o c i a t i o nr u l e si ni n t e g e rs ot h a tt h e ya r ea l ls i g n i f i c a t i v e k e y w o r d s ：d a t am i n i l 】g ，a s s o c i a t i o nr u l e ，n e g a t i v e a s s o c i a t i o nr u l e r e d u n d a n ta s s o c i a t i o nr u l e 数据挖掘中关联规则的优化 日茜 近十儿年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个 数据库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将持续 发展下去。于是，一个新的挑战被提了出来：在这被称之为信息爆炸的时代。信 息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从 中及时发现有用的知识，提高信息利用率呢? 要想使数据真正成为一个公司的资 源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数 据可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥饿于 知识”的挑战，数据挖掘和知识发现( d 5 皿( d ) 技术应运荷生，并得以蓬勃发展，越 来越显示出其强大的生命力。 数据挖掘一面世就以其强大的实用性得到了人们的认同。美国财富杂志5 0 0 强之一的第一数据公司( f i r s td a t ac o r p ) 就在为第一国家银行( f i r s t n a t i o n a lb a n k ) 、美国在线交易( a m e r i t r a d eh o l d i n gc o ) 、奥马哈保险公司 ( m u t u a lo fo m a h ac o ) 等著名的金融证券和保险公司提供数据挖掘的产品服务， 这些企业在风险控制、挖掘客户、降低成本方面的年收益数以亿计。 在数据挖掘的诸多应用当中，关联规则挖掘是其中最活跃的研究方向之一， 其最早是由a g r a w a l 等人提出的。最初提出的动机就是针对购物篮分析问题，其 目的是为了发现交易数据库中不同商品之间的联系规则。这些规则刻画了顾客的 购买行为模式，如购买了某一商品对购买其他商品的影响，因此可以用来指导商 家科学地安排进货、库存、货架设计以及根据购买模式对用户进行分类等。 随着数据库与数据仓库规模的日益庞大，人们根据原有的关联规则挖掘算法 从海量数据中挖掘出来的关联规则的数量也飞速增长，难以从中找出对用户真正 有用的知识，而且挖掘出来的某些关联规则还是冗余的、虚假的。因此，对挖掘 出来的关联规则进行进一步优化，避免生成冗余的或虚假的关联规则，是未来富 有应用前景的一个研究方向。目前在挖掘有意义的关联规则这个问题上开展的研 究工作主要有：专家参与关联规则的评价和进行可视化分析、引入新的阈值来加 强对关联规则的评价。 本文尝试从另一个角度研究关联规则的优化问题：加强支持度和信任度的定 义，使其不用增加新的阈值就可以挖掘出无冗余、无虚假的关联规则。本文详细 介绍了作者在数据挖掘中关联规则优化方面的研究工作，并且在深入了解已有的 数据挖掘中关联规则的优化 关联规则模型及其特性的基础上提出了一个基丁_ i 带负项的反向关联规则与关联 规则冗余性质的关联规则优化算法：o p t - - r u l e s 。该算法与原来的a p r i o r i 算法 相比，首先是考虑了带负项的反向关联规则的存在，并且对关联规则进行了相关 性分析，得到了更多的隐藏在项目中的有用规则，同时也删除了虚假的、无意义 的关联规则；同时，o p t - - r u l e s 算法还引入了关联规则的简单冗余与严格冗余定 义，大大地约简了关联规则的数量，节省了关联规则的生成时间，但却不会丢失 关联规则知识，解决了实际应用中生成的关联规则数目特别是考虑了负项的反向 关联规则数目庞大无比的问题。文章的详细内容包括： 1 考虑关联规则的相关性分析，引入反向项目集来加强原有的关联规则支 持度和信任度的定义； 2 3 引入简单冗余规则和严格冗余规则的定义，然后在反向关联勰则的基础 上对其进行拓展，提出了反向关联规则中的简单冗余和严格冗余规则的 若干定理； 给出关联规则优化算法o p t - - r u l e s 的详细流程描述，并且通过实验表 明，与传统的关联规则挖掘算法a p r i o r i 相比，o p t r u k s 算法能够确 实地剔除掉关联规则中的冗余规则和虚假规则，大大减少挖掘出来的关 联规则数量。 2 第一章数据挖掘概述 1 1 数据挖掘背景 随着时代的进步，人们产生和收集数据的能力迅速提高，越来越多的人加入 到数字世界中，利用计算机提供的各种工具来获得他们所感兴趣的信息。条形码 在大部分商业产品中的广泛使用，许多商务、科学和行政事务的计算机化，以及 由文本和图象扫描平台到卫星遥感系统的数据收集工具的进步，再加上作为全球 信息系统的万维网的流行，w e b 数据的急剧膨胀，已经将我们淹没在数据和信息 的汪洋大海中。数据的丰富带来了对强有力的数据分析工具的需求，传统的数据 库查询手段已经很难满足人们的需要，大量的数据被描述为“数据丰富，但信息 贫乏”。快速增长的海量数据收集、存放在大型和大量的数据库中，却由于缺乏 将这些数据转换成有价值的信息和知识的新技术和自动化工具，使锝收集在大型 数据库中的数据变成了“数据坟墓”难得再访问的数据档案。人们迫切需要 一种能够对庞大的数据进行更高层次处理的技术，从中找出规律和模式，以帮助 人们更好地利用数据进行决策管理和研究，而数据挖掘技术碱大量数据中用 非平凡的方法发现有用的知识的出现，引起了人们广泛的关注，导致了数据 挖掘研究的蓬勃发展。 数据挖掘通常又称为数据中知识发现，就是从存储在大型数据库、数据仓库 或其他信息存储容器中的大量的、不完全的、有噪声的、模糊的、随机的数据里 提取人们感兴趣的知识，这些知识是隐含的、事先未知的、对决策有潜在价值的 有用信息。还有很多近似的术语，如从数据库中发现知识( k d d ) 、数据分析、 数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的源 泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系型数据库中的数 据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异 构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的， 也可以是归纳的。知识用概念、规则、模式、规律等方式来表示。发现了的知识 可以被用于信息管理、查询优化、决蓑支持、过程控制等，还可以用于数据自身 的维护。 数据库中的知识发现是一个多步骤的处理过程，一般分为： ( 1 ) 问题定义：了解相关领域的有关情况，熟悉背景知识，弄清用户要求。 数据挖掘中关联规则的优化 ( 2 ) 数据提取：根据要求从数据库中提取相关的数据。 ( 3 ) 数据预处理：主要对前一阶段产生的数据进行加工，检查数据的完整 性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据进行填补。 ( 4 ) 数据挖掘：运用选定的知识发现算法，从数据中提取出用户所需要的 知识，这些知识可以用一种特定的方式表示或使用一些常用的表示方式。 ( 5 ) 知识评估：将发现的知识以用户能了解的方式呈现，根据需要对知识 发现过程中的某些处理阶段进行优化，直到满足要求。 由此可见，数据挖掘只是数据库中知识发现的一个步骤，但又是最重要的一 步。因此，往往可以不加区别地使用k d d 和数据挖掘。一般在研究领域被称作 数据库中知识发现的，在工程领域则称之为数据挖掘。 数据挖掘是一门广义的交叉学科，涉及多学科技术的集成，包括数据库技术、 人工智能、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索、知识库系统、图象与信号处理和空间数据分析。机器学习和数据分析 的理论及实践是数据挖掘研究的基础，极大的商业应用前景又是数据挖掘研究工 作的巨大推动力。传统的数据库查询和统计、报表的处理方式都是对指定的数据 进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取，因此只能 够提供用户想要的信息，而数据挖掘技术则可以发现用户没有意识到的未知的有 价值信息。作为一种在海量数据中发现知识的手段，与传统的数据分析( 如查询、 报表、联机应用分析0 l a p 等) 的本质区别在于数据挖掘是在没有明确假设的前提 下去挖掘信息、发现知识的，它可以从大型的数据库或数据仓库中提出隐藏的预 测性信息，从浩如烟海的企业信息资料库中挖掘出更有价值的信息，具有广泛的 应用前景。 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性质 的知识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事物 之间属性差别的知识；关联型知识，反映事物之间依赖或关联的知识；预测型知 识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏离常规的 异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升， 从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家 超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客 十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对于 商家开发和实施客户化的销售计划和策略是非常有用的。 数据挖掘所得到的知识应具有先前未知、有效和可实用三个特征。先前未知 是指该知识是预先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信 息或知识，甚至是违背直觉的信息或知识，挖掘得到的知识越是出乎意料，就可 能越有价值。知识的有效性要求挖掘前要对被挖掘的数据进行仔细检查，保证它 们的有效性，才能保证挖掘所得知识的有效性。最为重要的是要求所得的知识有 4 数据挖掘中关联规则的忱化 可实用性，即这些信息或知识对于所讨论的业务或研究领域是有效的，是有实用 价值和可实现的。常识性的结论，早已被人们或竞争对手掌握的或无法实现的事 实都是没有意义的。 数据挖掘起源于2 0 世纪8 0 年代后期，是信息技术自然演化的结果，9 0 年代有 了突弋猛进的发展。自从1 9 9 5 年第一届知识发现和数据挖掘国际会议在加拿大召 开以来，数据挖掘技术已成为机器学习、数据库系统、人t 智能等领域内热门的 研究方向。随后，i e e e 、a c m 、执l 等国际权威机构纷纷组织专题会议，共同 讨论有关数据挖掘方面出现的问题和所取得的成果。 1 2 数据挖掘的应用与发展 1 2 1 数据挖掘的方法 近年来，数据挖掘技术引起了信息产业界的极大关注，其主要原因是存在大 量数据可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取 的信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工 程设计和科学探索等。而用于发现知识的数据挖掘分析方法包括： ( 1 ) 分类( c l a s s i f i c a t i o n ) 分类反映同类事物共同性质的特征型知识以及不同事物之间的差异型 特征知识。它是这样的一个过程，首先找出描述并区分数据类或概念的模型 ( 或函数) ，再使用模型预测类，标记未知的对象类。模型类的个数是确定 的，预先定义好的。一个典型的应用就是银行将信用卡申请者分类为低、中、 高风险来标志申请者的可信度，再根据可信度来给予申请者不同的优惠。 ( 2 ) 估值( e s t i m a t i o n ) 估值与分类类似，不同之处在于，分类描述的是离散型变量的输出，而 估值处理连续值的输出：分类的类别是确定数目的，估值的量是不确定的。 一般来说，估值可以作为分类的前一步工作。给定一些输入数据，通过估值， 得到未知的连续变量的值，然后，根据预先设定的阈值，进行分类。例如： 银行对家庭贷款业务，运用估值，给各个客户记分。然后，根据阈值，将贷 款级别分类。 ( 3 ) 演变分析( e v o l u t i o na n a l y s i s ) 数据演变分析也可以认为足以时间为关键属性的关联知识。是根据时间 序列型数据，描述行为随时间变化的对象的规律或趋势，然后对其建模，并 由历史的和当前的数据去推测未来的数据。分析过程可能包含时间相关数据 的特征化、区分、关联、分类和聚类，这类分析的不同特点包括时间序列数 数据挖掘中关联规则的优化 据分析、序列或周期模式匹配和基丁类似性的数据分析。演变分析在医疗上 有很强的应用前景，例如通过分析患者以往的医疗数据，可以根据患者的实 际情况( 如经济水平、既往病史、具体病情) ，使用演变分析来提前预测病 人手术后的康复进度，合理安排康复计划、用药计划等。 ( 4 ) 相关性分组或关联规则( a f f i n i t yg r o u p i n go ra s s o c i a t i o nr u l e s ) 关联规则是当前数据挖掘研究的主要领域之一，主要作用是确定数据集 中不同领域或属性间的联系，找出可信的、有价值的多个域之间的依赖关系。 这些规则可以找出顾客购买行为模式，如在销售食品柜台发现，在购买牛奶 的客户中，有8 0 的人同时也购买了面包和饼干，用规则：牛奶一 面包十 饼干表示。发现这样的规则可以设计方便顾客购物的商品货架、指导商家进 货，对于确定市场策略是很有价值的。关联规则还可以应用到附加邮递、仓 储规划以及基于购买模式对用户进行分类等方面。 ( 5 ) 聚类分析( c l u s t e r i n g ) 与分类和预测不同，聚类是对记录分组，把相似的记录集中在一个聚类 里，聚类分析数据对象，而不考虑已知的类标记。聚集和分类的区别主要在 于聚集不依赖于预先定义好的类，不需要训练集。聚类分析通常作为数据挖 掘的第一步。例如，“哪一种类的促销对客户响应最好? ”，对于这一类问题， 首先对整个客户做聚类，将客户分组在各自的聚类里，然后对每个不同的聚 类回答问题，可能效果更好。 ( 6 ) 概念描述( c o n c e p td e s c r i p t i o n ) 概念。般是指数据的汇集。而概念描述是指机器自动由现有数据获得需 要描述的概念的定义，即根据数据的微观特性发现其表征的、带有普遍性的、 较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数据的 概括、精炼和抽象。例如，对某一个病症，给出一些确诊病人的例子，计算 机自动归纳该病症患者的特征，然后得到一个关于患此类新病症的病人的一 个通用的描述。 1 2 2 数据挖掘的研究现状 数据挖掘技术从一开始就是面向应用的。它不仅仅是面向特定数据库的简单 的检索查询或者调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、 综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已 有的数据对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新 的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。美国加州 理工学院喷气推进实验室与天文学家合作开发的s k i c a t 系统通过对几百万个 6 数据挖掘中关跌规则的优化 天体进行分类，已帮助天文学家发现了1 6 个新的类星体。美国n b a 篮球队的教 练，利用某公司提供的数据挖掘技术，临场决定替换队员，一度在数据库界被传 为佳话。最近，还有不少d m k d 产品用来筛选i n t e r n e t 上的新闻，保护用户不 受无聊电子邮件的干扰和商业推销，受到极大的欢迎。这样一来，就把人们对数 据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。 这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这里所说的知识 发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定 理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有 特定前提和约束条件、面向特定领域的，同时还要能够易于被用户理解，最好能 用自然语言表达发现结果。 目前，国外数据挖掘的发展趋势主要有：对知识发现方法的研究进一步发展， 如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高；传统的 统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合等。在应用方面包括： k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤 立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多 计算机公司非常重视数据挖掘的开发应用，m m 和微软都成立了相应的研究中 心进行这方面的工作。很多大公司也对数据挖掘应用的研究投入大量精力，经过 十多年的努力，关于数据挖掘技术应用的研究也取得了丰硕的成果。一些公司已 经开发了多种数据挖掘相关的产品，据不完全统计，目前已经有了数百个数据挖 掘软件产品。如i b m 公司开发的q u e s t 和i m e l l i o p t tm i n e r ；a n g o s ss o l t w a r e 开发的基于规则和决策树的k n o w l e d g es e e k e r ；a d v a n c e ds o f t w a r ea p p l i c a t i o n 开 发的基于人工神经网络的d bp r o f i l e ；加拿大s i m o nf r a s e r 大学开发的d bm i n e r ； s g i 公司开发的m i n es e t 等。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关 数据挖掘理论方面的研究，大量的文章已经在各级期刊，各种会议发表，应用数 据挖掘技术开发的产品日渐增多，已经有不少含数据挖掘功能的产品问世，如用 于对股票行情进行分析预测的指南针、神光、r m r 等智能股票分析系统。目前 进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划、 “九五”计划等。 一份最近的g a r t n e r 报告中列举了在今后3 5 年内对工业将产生重要影响的 五项关键技术，其中k d d 和人工智能排名第一。同时，这份报告将并行计算机 体系结构研究和k d d 列入今后5 年内公司应该投资的1 0 个新技术领域。可以 看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视，预计在 2 1 世纪还会形成更大的高潮，研究焦点可能会集中到以下几个方面：研究专门 用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化i 数据挖掘中关联规则的优化 寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理解，也便 于在知识发现过程中的人机交互；研究在网络环境下的数据挖掘技术，特别是在 i n t e m e t 上建立d m k d 服务器，与数据库服务器配合，实现数据挖掘；加强对各 种非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数据。但是无论怎 样，需求牵引与市场驱动是永恒的，d m k d 将首先满足信息时代用户的急需， 大量基于d m k d 的决策支持软件工具产品将会问世。 数据挖掘中关联规则的优化 第二章关联规则挖掘 2 1 关联规则挖掘技术简介 有一段时间，人们常常笑称数据挖掘就是“啤酒与尿布”，这是什么意思呢? 原来，这是一个经典的关于数据挖掘的故事。世界上最著名的商家沃尔玛公司为 了能够最精确地了解到消费者每天在超市里的购买习惯，每天都要利用 n c r t e r a d a t a 数据仓库对商品进行购物篮分析，看看哪些商品顾客最有希望起 购买。这个数据仓库里集中了各个商店一年多详细的原始交易数据。在这些原始 交易数据的基础上，沃尔玛公司利用自动数据挖掘工具对这些数据进行分析和挖 掘。一个意外的发现就是：跟尿布一起购买最多的商品竟是啤酒! 原来美国的太 太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了 两瓶啤酒。既然尿布与啤酒一起购买的机会最多，于是沃尔玛就在它的一个个商 店里将它们并排摆放在一起，结果是尿布与啤酒的销售量双双增长。 这是数据挖掘应用在商业领域并取得成功的一个典型例子，而用到的技术正 是数据挖掘中的关联规则挖掘。关联规则挖掘是数据挖掘中最活跃的研究方向之 一，其最早是由a g r a w a l 等人提出的。最初提出的动机就是针对购物篮分析闯题， 其目的是为了发现交易数据库中不同商品之间的联系规则。这些规则刻画了顾客 的购买行为模式，如购买了某一商品对购买其他商品的影响，因此可以用来指导 商家科学地安排进货、库存、货架设计以及根据购买模式对用户进行分类等。之 后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作涉及到 关联规则挖掘理论的探索、原有算法的改进和新算法的设计、并行关联规则挖掘 ( p a r a l l e l a s s o c i a t i o nr u l em i n i n g ) 以及数量关联规则挖掘( q u a n t i t i v e a s s o c i a t i o n r u l em i n i n g ) 等问题。在提高挖掘规则算法的效率、适应性、可用性以及应用推 广等方面，许多学者进行了不懈的努力。 2 1 1 关联规则定义 为了便于理解，现使用超市的交易数据库来形式化描述关联规则： 设i = i 。i 。，i 。，i 】为项目集，表示超市所有商品的集合，d ： t - ，t z ，t 。) 为交易集，其中每个t i 。 一一 墼塑笙塑! 苤壁塑型塑垡些 一 关联规则是形如下式的蕴含式 x ；y ( 其中x c i ，y c i ，且x n y = a ) 为了进一步说咀关联规则的正确程度和支持率，人们引入了支持度和信任度 两个概念： 支持度：关联规则x 等y 的支持度s 表示在交易集中， 的交易包含了x u y 。 信任度：关联规则xj y 的信任度c 表示在交易集中 交易的集合中有c 包含了y 。 关联规则的支持度和信任度可以如下计算： 在交易集d 中有s 在包含了x 的所有 令p r ( x ) 表示项目集x 的支持度，即在交易集d 中有p r ( x ) 的交易包含了 x ，于是xj y 的支持度p r ( x y ) = p r ( x u y ) ，xjy 的信任度p r ( yj x ) = p r ( x u y ) p r ( x ) 。 从语义的角度来分析，规则的信任度表示这条规则正确程度；支持度表示用 这条规则可以推出百分之几的目标，即这一原因对于这一结果的重要程度，一般 地，用户可以定义两个闽值( t h r e s h o l d ) ，要求数据挖掘系统所生成的规则的支 持度和信任度都不小于给定的阈值。 2 1 2 关联规则分类 基于不同的情况，关联规则可以分类为： 1 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布 尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间 的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来， 对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据 进行处理，当然数值型关联规则中也可以包含种类变量。 例如：性别= “女”j 职业= “公关”，是布尔型关联规则；性别= “女” j a v g ( 收入) = “4 0 0 0 ”，涉及的收入是数值类型，所以是一个数值型关 联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个 不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充 分的考虑。 例如：h p 台式机毒s o n y 打印机，是一个细节数据上的单层关联规则； 而台式机= ： s o n y 打印机，则是一个较高层次和细节层次之间的多层关联 规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品； 而在多维的关联规则中，要处理的数据将会涉及多个维。换句话说，单 维关联规则是处理单个属性中的一些关系，多维关联规则是处理各个属 o 数据挖掘中关联规则的优化 性之间的某些关系。 例如：啤酒等尿布，这条规则只涉及到用户的购买的物品；性别= “女” ；职业= “公关”，这条规则就涉及到两个字段的信息，是两个维上的一一 条关联规则。 2 , 2 关联规则挖掘技术的当前研究 关联规则的挖掘问题就是在交易数据库中找出具有用户给定的最小支持度 和最小信任度的关联规则。由于如今的大规模数据库中存储着极其巨大的数据， 人们从中挖掘出来的关联规则也数量庞大，难以找出对用户真正有用的知识，而 且存在某些关联规则是冗余的、虚假的。因此，对挖掘出来的关联规则进行优化， 避免生成冗余的或虚假的关联规则，是目前富有应用前景的一个研究方向。 目前在挖掘有意义的关联规则这个问题上开展的研究主要有： 1 由专家参与关联规则的评价和进行可视化分析，对于某个领域的关联规 则，由这个领域的专家通过积累的经验和定性分析，来评价挖掘出来的 关联规则是否对这个领域有意义。 2 引入新的闺值以加强对关联规则的评价。在这当中，兴趣度的提出是一 个较为瞩目的观点。s r i k a n t 和a g r a w a i 绘出了愍兴趣的规则的定义。压 来又对此进行改进，把事件依赖性的统计定义扩展到兴趣度的定义上来。 k l e m e t t i n e n 等定义了模板的概念，用户使用它来确定哪些规则是令人感 兴趣的，哪些则不是：如果条规则匹配一个包含的模板( i n c l u s i v e t e m p l a t e ) ，则是令人感兴趣的若它匹配一个限制的模板( r e s t r i c t i v e t e m p l a t e ) ，则被认为是缺乏兴趣的。b r i n 等人把x ，y 的信任度定义为 p ( x ) p ( 、y ) p ( x ，1 y ) ，定义了蕴涵规则( i m p l i c a u o nr u l e ) ，规则的蕴 涵强度在【o ，叫之间变化，其中蕴涵强度为1 表示完全无关的规则。m 表示完备的规则，如果蕴涵强度大于1 则表示更大的期望存在性。 2 3 本文对关联规则挖掘方法的改进 目前，关于关联规则评价方法的专门研究比较少，大多是由专家参与评价和 进行可视化分析，这样就受到专家经验和可视化工具的限制，属于感性的评价和 定性的分析，带有很多人为的因素。西人工智麓中专家系统技术的研究还不成熟， 目前还停留在构造诸如发动机故障判断一类的水平上，难以用常规数理逻辑来评 价表示数据集中不同领域间依赖关系的关联规则。因此，如何实现专家评价关联 数据挖掘中关联规则的优化 规则的客观性、全面性和准确性就是当前关联规则评价研究的主要目标。如果引 入新的阂值来加强对关联规则的评价，就一定要有相对应的算法。因为现有的许 多算法经过理论和实践的证明与运用，已经目趋成熟，这是一种可以充分利用的 宝贵资源。所以，如果可以在不提出新算法的前提下，对现有算法进行改变，使 其能够实现既定目标，将达到事半功倍的效果，这也是目前研究的主要方向。 本文尝试从另一个角度研究关联规则的优化问题：加强支持度和信任度的定 义，使其不用增加新的阈值就可以挖握出无冗余、无虚假的关联规则。在关联规 则中，支持度表征的是规则的频度，信任度表征的是规则的强度，支持度越高， 说明规则经常出现；信任度越高，说明规则越可靠。对于这两者，用户通常都有 一个直观的概念，就是有多少的可能性使得关联规则的出现频度在某个数值以 上，这条规则就是有意义的。本文主要研究如何引入反向项目来加强支持度和信 任度的定义，并且通过简单冗余规则和严格冗余规则的定义来删除正向规则与反 向规则的冗余项，使到最终挖掘出来提供给用户的关联规则都是有意义的。 本文章节组织如下： 第一章介绍了数据挖掘的一些相关知识，包括数据挖掘的产生、应用与 当前研究现状。 第二章简要介绍了关联规则挖掘技术的相关知识与当前国际研究动态， 并且简单说明了本文的主要研究方向。 第三章给出反向关联规则的定义，说明如何引入反向项目和反向项目在 关联规则中的作用。 第四章定义简单冗余规则与严格冗余规则，给出用于删除冗余规则的定 理和相关定义。 第五章详细描述关联规则优化算法o p t - r u l e s 。 第六章说明如何产生实验数据，最后给出了实验结果比较。 数据挖掘中关联规则的优化 第三章反向关联规则 3 1 关联规则的相关性分析 自从a g r a w a l 等于1 9 9 3 年首先提出挖掘顾客交易数据库中项目集的关联规 则问题以后，学术界对关联规则的挖掘问题进行了大量的研究。“在数据挖掘中 发现的所有的关联规则( 即满足最小支持度和最小信任度阈值) 都是真正有意义 而值得向用户提供的吗? ”就是其中的一个研究方向。让我们看看下面的一个例 子所体现出来问题： 假设个超市的交易数据库有1 0 0 个记录，其中购买牛奶的记录2 5 个，购 买啤酒的记录9 0 个，同时购买牛奶和啤酒的记录为2 0 个。如果设定最小支持度 2 0 ，最小信任度6 0 ，那么按照a g r a w a l 的定义可以得到关联规则： 购买牛奶j 购买啤酒( s u p p o r t z 2 0 ，c o n f i d e n c e = 8 0 ) 由上面的规则可以得出这样一个结论：8 0 的人购买了牛奶就会购买啤酒， 也就是说，刺激顾客对牛奶的购买欲望将增加啤酒的销售量。但是，这条规则给 出的信息实际上是误导的，因为我们由数据库中就可以知道9 0 的人肯定会购买 啤酒，比8 0 大，也就是说，一个已知购买了牛奶的顾客购买啤酒的可能性实际 上比一个我们不知道任何信息的顾客购买啤酒的可能性小( 1 0 ) 。我们并不能 肯定地说购买了牛奶就会购买啤酒这条规则一定不正确，但至少它的价值已经不 如我们开始期望的那么高了。事实上，在数据库中牛奶和啤酒是负相关的，购买 其中一种实际上减少了购买另一种的可能性。如果在交易数据库中引入反向项 目，那么得到的规则：购买啤酒不买牛奶( s u p p o r t = 7 0 ，c o n f i d e n c e = 7 8 ) 更具有实际的指导意义。 上面的例子说明了规则x j y 的信任度有一定的欺骗性，它只是给定x 、y 的条件概率的估计，而并没有度量x 和y 之间蕴含的实际强度。因此，我们提 出在支持度一信任度框架的基础上，根据事件相关性来挖掘数据项之间有趣的联 系：如果p r ( x u y ) = p r ( x ) p r ( y ) ，那么我们认为项目集x 的出现独立于项目集y 的出现；否则，项目集x 和y 作为事件是依赖的和相关的。x 和y 的出现之间的 相关性通过公式： 数据挖掘中关联规则的优化 p “x u y l 。o 仃xy 2 p r ( 2 x ) p r ( 一y ) 来计算。如果( 1 ) 式的值小于t ，则x 的出现和y 的出现是负相关的。如果结 果值大于1 ，则x 和y 是正相关的，意味着前一个的出现蕴含另一个的出现。 如果结果值等于1 ，则x 和y 是独立的，两者没有相关性。 这样，整个关联规则的评价体系就统一在概率论的范畴内。也就是说，从概 率论的角度来看，关联规则的相关性反映了关联规则中x 和y 的关系，由它可 以了解x 和y 之间的关系究竟如何密切；而支持度则反映了这种情况在交易中 是否是普遍的规律；信任度则反映了在这种情况下关系的方向，即是从x 到y ， 还是从y 到x 。 3 2 反向关联规则的定义 原有的关联规则的定义已经不能满足关联规则相关性的分析，因此我们给出 了带有负项的反向关联规则定义。我们以商场超市的交易数据库为例来形式化地 描述反向关联规则： 设i = i 。，i 。，i ) 为项集，i 。( 1 j 剑) 为正项，相对应地一i j ( 1 j 列) 为负项， d = t ，t 2 i 一，t n 为交易集，其中t 。i ( 1 i 剑为交易，则反向关联规则是一个 形如 p l p 2 p h = q l q k - - q k * la - q 的蕴含式，其中p 。，q j i ( 1 s i g n ，1 5 j m ) ， p ，p 2 ，p 。) n q ，q 2 ，q i 彩。 该定义强制规则前部为正项，避免了许多类似一i 一一i t 一ijj i w ， 一i 。的规则被挖掘出来。因为这类规则往往有很高的支持度和信任度，但是也很 难理解或具有实用价值。例如规则“不买牛奶j 不买啤酒”，在实际分析预测中 是毫无意义的。更进一步讲，对于规则前部中所有的项都是负的规则，例如“不 买牛奶等购买啤酒”，在语义上往往也是难以理解的，因为关联规则其实是一种 心理暗示，从已知事件推出未知的更加符合人们的习惯思维：“购买啤酒”是发 生的事件，由此可以推测“不买牛奶”，但反过来却会让人提出疑问：为什么“购 买啤酒”是由“不买牛奶”而不是其他事件所引起的呢? 而且在实际应用中，交 易集在记录过程中一般只会记录发生了什么事件，而不会记录，也很难记录什么 事件没有发生，专家和决策人员也只能从已经发生的事件中去分析预测未来没有 发生的事件。因此，强制关联规则前部为正项在很大程度上避免了无意义的“垃 数据挖掘中关联规则的优化 圾”知识的产生。 3 3 反向关联规则的相关定理 完成了反向关联规则的定义之后，我们面临的问题是如何将负项引入原有的 算法，使其能够从数据库中挖掘出反向关联规则。文献【3 】对此提出了对a p r i o r i 的c a n d io p t ( l k _ l ，c k ) 进行修改，生成带否定示例的c k 。但这种作法需要一 个前提，即原始的交易集中必须要记录项目的否定示例，否则算法就成了无米之 炊，而人为地加入否定示例会产生歧义，例如一个项目集i = a ，b ，c ，d ) ，假 定t = f a ，b ，那么加入否定示例后，t j 会有 a ，b ，一c ) ， h ，b ，一d ，( a ，b ， 一c ，- d 3 个选择，它们的解释各不相同，究竟哪个可以替代原有的t 。是个令人 困惑的问题。更进一步，如果将所有不在t 中的项都采用否定示例的形式加入t 中，就会使交易集中交易所包含项的个数成倍增加，对于算法的频繁项目集生成 将成为一个极其巨大的负担。因此，我们考虑在不增加频繁项目集的情况下引入 否定示例，在此需要引进一个反向项目集“”的概念。 反向项目集( n e g a t i v ei t e m s e t ) ：给定正项集i = i ，i 。，。i 。】和一个项目集s = i ，i 2 ，”，i 。 _ c i ，称s n | i “。，i 2 ，- ”，i ”。 为s 的一个反向项目集当且仅