（计算机软件与理论专业论文）单维关联规则挖掘算法研究.pdf

硕十论文：单维关联规则挖掘算法研究 郑卅1 人学计算机系 摘要 关联规则揭示项集间有趣的相联关系，可广泛应用于购物篮分析、相关 分析、分类、网络个性化服务等领域，是数据挖掘的重要研究课题。自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 算法，在挖掘频繁模式时需要产生大量 候选项集，多次扫描数据库和维护一棵很大的h a s h 树，时空复杂度过商。 本文提出基于被约束子树的：项繁模式挖掘算法f p m i n e 和基于线索频繁 模式树的关联规则产生算法s p f ，有效解决了数据库中单维关联规则挖掘问 题。实验表明，在相同数据集上，与f p g r o w t h 算法相比，算法f p m i n e 的 挖掘速度提高了一倍以上，而所需的存储空间减少了一半；随着数据库规模 的增大，算法f p m i r t e 具有很好的可伸缩性；对于稠密数据集，本文算法也 具有良好的性能；s p f 算法具有极好的时空效率；f p m i n e s p f 算法挖掘关 联规则的速度远快于较长期以来广泛使用的a p r i o r i 算法，并有相当好的可 伸缩性。 关联规则挖掘往往生成过多的规则，使用户很难进行耿舍。为此，近年 的研究提出一种有效的替代手段一挖掘频繁闭项集规则。频繁闭项集规则蕴 含了所有关联规则，数目却大为减少。挖掘频繁闭项集规则大幅提高了挖掘 的效率和规则的有效性，解除了用户的负担。 本文实现了频繁闭项集、频繁闭项集规则的挖掘算法f c i s 和 c i r u l e s 。实验表明，在相同数据集上，与已发表的最新成果一h a n 的 c l o s e t 算法相比，本文算法f c i s 速度提高两个数量级以上，并有极好的 可伸缩性；c i _ r u l e s 算法挖掘频繁闭项集规则的运行速度较f p m i n e s p f 算法挖掘关联规则的速度快两个数量级以上，并有非凡的可伸缩性。 关键字：数据挖掘关联规则 笫1 顷 堡丝兰! 苎丝茎丛塑型笙塑笠鲨业窒 型型叁堂生竺型! 墨 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 e e ti nd a t am i n i n g , r e v e a l st 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 nb ew i d e l ya p p l i e dt o m a n yf i e l d ss 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 t i o na n a l y s i s ，c 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 ds e r v i c e ，e t c s i n c e1 9 9 3w h e nr a g r a w a l ，r s r i k a n tf i r s t l y p 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 pi n m i n i n g o fa s s o c i a t i o nr u l e s w h i l em o s to ft h e s ea l g o r i t h m sa r eb a s e do n a p r i o r il i n e ，w i l lg e n e r a t eah u g en u m b e ro fc 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 e s 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 gb a s h t r e e ，s o t h et i m ea n d s p a c e c 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 dt h ec o n s t r a i n e d - 4 r e eb a s e da l g o r i t h mf p m i n ef o rf a s t m i n i n go ff r e q u e n tp a t t e r n s ，a n d t h ea s s o c i a t i o nr u l e sm i n i n ga l g o r i t h ms p f b a s e do nt h r e a d e df r e q u e n tp a t t e r nt r e e t h et w oa l g o r i t h m sd w e l lo nt h es i n g l e d i m e n s i o na s s o c i a t i o nr u l e sm i n i n gi nd a t a b a s e e x p e r i m e n t ss h o wt h a tf p m i n e r u n st w ot i m e sa sf a s ta st h em o s tr e c e n t l yp r o p o s e da l g o r i t h mf p g r o w t ha n d s a v e sh a l ft h em e m o r y ；m o r e o v e r 0 1 7a l g o r i t h mh a saq u i t e g o o dt i m ea n d s p a c es c a l a b i l i t y w i t ht h en u m b e ro ft r a n s a c t i o n s ，a n dh a sa ne x c e l l e n t p e r f o r m a n c e i nd e n s ed a t a b a s em i n i n ga sw e l l ；s p fh a se x c e l l e n tt i m ea n ds p a c e e f f i c i e n c y ；f p m i n e - - s p fa l g o r i t h mh a saf a r f a s t e rs p e e di na s s o c i a t i o nr u l e s m i n i n gt h a nt h ew i d e l yu s e da p r i o r ia l g o r i t h ma n dh a s w o n d e r f u ls c a l a b i l i t y a s s o c i a t i o nr u l e sm i n i n ga l w a y sg e n e r a t e st o om a n yr u l e s ，w h i c hm a k e si t d i f f i c u l tt op i c kt h ev a l u a b l er u l e sw h e r e l f r o m i no r d e rt ot a c k l et h i sp r o b l e m ， r e c e n ts t u d i e sr a i s e da ne f f e c t i v ea l t e r n a t i v e ，m i n i n gf r e q u e n tc l o s e di t e m s e t s r u l e s f r e q u e n tc l o s e di t e m s e t sr u l e si m p l ya l lt h ea s s o c i a t i o nr u l e sb u tg r e a t l y r e d u c et h er u l e sn u m b e r m i n i n go f f r e q u e n tc l o s e di t e m s e t sg r e a t l yi m p r o v e t h e r u l e sm i n i n ge f f i e n c ya n de f f e c t i v i t yo ft h er e s u l t i n gr u l e s ，h e n c er e l e a s et h e u s e r so ft h eb u r d e n w ei m p l e m e n tt h ef r e q u e n tc l o s e di t e m s e t sm i n i n ga l g o r i t h mf c i sa n dt h e f r e q u e n tc l o s e di t e m s e t sr u l e sm i n i n ga l g o r i t h mc i r u l e s e x p e r i m e n t sd i p l a y t h a t c o m p a r e d w i t ht h el a t e s t p u b l i s h e da l g o r i t h m - - t h e c l o s e ta l g o r i t h m p r o p o s e db yj i a w e ih a n ，o u ra l g o r i t h mi sm o r et h a nt w om a l g t i t u d e sf a s t e ra n d h a sf a b u l o u ss c a l a b i l i t y ；a r u l e sa l g o r i t h mo v e r t a k e sf p m i n e - s p fa l g o r i t h m b ym o r et h a nt w om a l g t i t u d e sa n dh a se x t r a o r d i n a r ys c a l a b 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 第2 页 硕十论文：单维关联规则挖掘算法w f 究 郊i ，i 1 人学计算机系 第一章绪论 1 1 研究背景 自7 0 年代关系数据库产生以来，各行各业相继采用关系数掘库系统作为 事务处理和企业内部管理的手段，促进了社会信息化程度的提高和计算机在 社会生活晕的普及应用。进入8 0 年代以来，关系数据库已深入军事、经济、 文化、政治、社会生活的各个角落。信息以规范的模式进行组织，方便地进 行读取、插入、修改、删除操作。s q l 语言的设计与实现，d b m s 优化策略的 有效实施使得数据查询方便而高效。前端应用的开发和图形可视化技术的发 展为事务处理提供了更多的自由，数据库不再仅仅支持本地使用，在远程终 端用户获得相应操作权限同样可以进行数据库操作，用户界面不再是单调的 d o s 屏幕，而是图文并茂。数据库管理系统、面向对象、网络技术、软 f - l ：- e 程与过程的发展和进步促使计算机应用更紧密地与信息处理的结合，成为人 们工作、生活不可缺少的伙伴。进入9 0 年代以来，信息作为一种战略资源被 提到议事日程。国防部门收集情报、制定策略、科技研发、军事部署、作战 指挥，无不需要信息系统的支持；政府要了解民情民意、公丌政府政策措施、 沟通协调各机构组织、为经济实体服务，于是产生了电子政务；企业公司进 行客户分析、市场调查、协商谈判、商务交易，电子商务应运而生；高校和 研究机构为了共享资源、合作研究，组建教育科研网从好莱坞大片的 制作到逼真梦幻的电脑游戏，从无线上网的手机到微软家庭娱乐的载体 x - b o x ，信息技术的发展为想象插上了翅膀，为人类的未来勾画出更精彩的 l j i 景。而数据库。作为信息时代核心基础设施扮演着越来越重要的角色。 随着数据库在各个领域的推广应用，尤其是于特定领域的应用需要，时 问数据库、空间数据库、文本数据库、多媒体数据库、x m l 数据库纷至沓来。 层次数据库、网状数据库、关系数据库、特种数据库，以及w w w 逐渐构筑了 新一代的全球信息源，数据被迅速地收集和集中。 第5 页 硕士论文：单维关联规则挖掘算法研究 然而，传统数据库仅仅提供一 查询操作，虽然已经带来无以伦比 的利用。快速增长的数据规模。但 据丰富，但信息贫乏”的局面，收 墓”。决策不是根据记录各方面信 直观，难免异想天开，有失偏颇。 数据库技术进一步的研究试图 是数据库中知识发现- - k n o w l e d g e 利用数据 非一般的 的知识和 因此又名 的鸿沟， 郑卅1 人学计算机系 般的投影、选择、连接、并交简单的检索 的方便，但大量的数据显然仍未得到充分 缺乏有效进行数据分析的软件，形成“数 集在大型数据库中的数据变成了“数据坟 息的数据来进行，而是凭借决策者感性的 从海量数据中发现更有价值的信息，这就 d is c o v e r yi nd a t a b a s e 的由来。k d d 综合 库系统、统计分析、人工智能、神经网络等学科的既有成果，采用 方法旨在从数据库、数据仓库中探寻用户更感兴趣的隐藏在数掘中 规律，这过程有时被形容为“从数据的海洋中挖掘知识的金块”， 数据挖掘，d a t am i n i n g 。数据挖掘弥合了感觉的直观和客观实际 为决策的正确性提供了事实依据。 数据挖掘是一个应市场需求而生的学科，又是一个多学科相互融合相互 渗透而产生的交叉学科。八十年代早期人工智能领域过大的投入如石沉大 海，远远没有带来预想的收获，研究于是转向更为实际可行的商业和民用项 目，渐渐演化为早期的数据挖掘研究。数据库技术、人工智能、统计学、心 理学、哲学的发展为数据挖掘的诞生奠定了理论基础，不可限量的市场需求 为数据挖掘的发展提供了广阔的空间。 专家预见，在今后的5 一l o 年内，随着数据量的日益积累以及计算机的 广泛应用，数据挖掘将在中国形成一个产业。全球数据挖掘产业的市场收入 预计将由1 9 9 9 年的2 0 亿美元，以每年2 8 豹增长率快速增长，到2 0 0 4 年达到 6 0 亿美元。数据挖掘的概念和演化详见第二章。 关联规则挖掘是数据挖掘的重要研究课题。一个关于关联规则的典型的 例子是它在购物蓝分析中的应用。比如，有5 6 的顾客同时购买了面包和牛 奶，在购买面包的顾客中，8 0 同时购买了牛奶，我们可以得到规则： 第6 页 硕士论文：单维关联规则挖掘算法研究 郑州大学计算机系 面包j 牛奶 支持度= 5 6 ，置信度= 8 0 】 它说明两点，首先，面包和牛奶都很畅销，其次，面包能够促进牛奶的 销售。这样我们就可以根据分析所得到的信息来重构超市。不同商品的销售 间常有某种内在的关联，通过数据挖掘得到事物间的内在关联，不仅客观可 信而且关联的程度能够量化，因而有着重要的价值。 在商业领域，关联规则能够协助企业决策者完成市场分析，进行客户关 系管理。1 ；在基因生物学中，关联规则可用来分析基因表达谱数据“1 ，揭示 不同基因间或环境硝烟与基因表达之间在生物学相关的联系：在国家安全领 域，关联规则能够识别危险与攻击“1 ；在网络信息领域，关联规则能为用户 提供个性化的服务“3 。此外，关联规则还可应用于相关分析、分类等数据挖 掘领域。据i d c 报道，客户关系管理软件的增长在数据挖掘市场份额里保持 最快的势头，1 9 9 9 年增长率为7 5 ，预计2 0 0 4 年将突破2 3 亿美元0 1 。随着市场 对关联规则挖掘工具需求的增加，关联规则挖掘得到了日益深入的研究。 1 2 研究现状 r a g r a w a l ，r s r i k a n t1 9 9 3 年首次提出关联规则的定义”3 ，并提出 了关联规则挖掘的“项集”方法一关联规则的挖掘分两步完成： ( i )从数据库中找出所有的频繁项集。 ( 2 )由频繁项集产生所有的强关联规则。 1 这两步中第( 1 ) 步的性能更为重要，因为它常常需要更多的i o 。 频繁项集的挖掘是关联规则“、相关分析“”、序列模式、显露模式 “4 1 等许多重要数据挖掘任务的基本步骤。长期以来，挖掘频繁模式主要采用 a p r i o r i 算法1 及其改进形式。这些算法利用a p r i o r i 性质：如果数据库中 一个长度为k 的模式不是频繁的，则它的长度为( k + 1 ) 的超模式不可能是频 繁的。利用这一性质，可以在候选频繁( k + 1 ) 项集中进行有效的过滤。然 而，a p r i o r i 及其类似算法仍然产生大量候选项集，并需要反复扫描数据库， 第7 页 硕士论文：单维关联规则挖掘算法研究 郑州大学计算机系 这严重影响了算法的效率。此外，为有效地过滤不可能是频繁项集的候选， 这些算法通常需要维持一个很大的h a s h 树，这需要很大的时间和空间开销。 j i a w e ih a n j i a np e i $ 口y i w e ny i n 提出的f p g r o w t h 算法是一种本质 上不同于a p r i o r i 算法的挖掘频繁模式的有效方法”1 。f p g r o w t h 算法只需要 两次扫描数据库。第一次扫描数据库，得到频繁l 一项集。第二次扫描数据库， 利用频繁卜项集过滤数据库中的非频繁项，同时生成f p - 树。由于f p - 树蕴涵 了所有的频繁项集，其后的频繁项集的挖掘只需要在f p 一树上进行。实验分 析表明，f p g r o w t h 算法l l a p r i o r i 算法快一个数量级。 f p g r o w t h 算法开辟了有效挖掘频繁模式的新途径。然而，它的时间和 空间效率还不足够高，仍需进一步改进。f p g r o w t h 算法的主要问题是：在 挖掘频繁模式时，它需要递归地生成条件f p 一树，并且每产生个频繁模式 就要生成一个条件f p 一树。在支持度阈值较小时，即使对于很小的数据库， 也将产生数以十万计的频繁模式。动态的生成和释放数以十万计的条件f p 一 树，将耗费大量时间和空间。此外，f p 一树和条件f p - 树需要自顶向下生成， 而频繁模式的挖掘需要自底向上处理。由于递归地生成条件f p - 树，因此f p 一 树和条件f p 一树必需双向可遍历。这样，f p 一树和条件f p 一树的节点中就需要 更多的指针，从而需要更大的内存空间来维护f p 一树和条件f p 一树。 关联规则挖掘第二步如何由频繁模式挖掘关联规则，少有文献论及。虽 然f p g r o w t h 算法能够有效地从数据库中挖掘频繁模式，但如何由其挖掘出 的频繁模式有效地产生关联规则仍是一个相当复杂的问题。事实上，为产生 所有强规则，我们需要对每个频繁模式j ，和它的任意非空真子集 确定爿j y z 是否是强规则。为此，我们需要从频繁模式集中检索z 得到朋勺支 持度。由于频繁模式集通常是一个很大的集合，如果不很好地加以组织，这 种检索的效率可能极低。此外，尽管j ，的绝大部分非空真子集都不可能成 为强规则的左部，但是j ，的非空真子集多达2 1 r l 一2 个。如果不能有效地对j ，的 子集空间进行剪裁，产生强规则的算法将是十分低效的。 第8 页 堡主笙苎! 望丝茎壁塑型垫塑簦鲨堕壅 塑型奎堂生簦塑! 墨 关联规则挖掘往往得到过多规则，使得用户挑选有价值的规则变得很 难。近来研究提出一种有效的替代手段一挖掘频繁闭项集、频繁闭项集规则。 频繁闭项集规则蕴含了所有关联规则，数目却大为减少。挖掘频繁闭项集规 则可以大幅提高规则挖掘的效率和得到规则的有效性，更好地服务用户。 现有的频繁闭项集挖掘算法如a c l o s e 、c h a r m 效率都过低下，难以有效 处理大规模数据集。2 0 0 0 年j i a w e i ，h a n 提出挖掘频繁闭项集的c l o s e t 算法， 大大提高了频繁闭项集的产生速度。但是，h a n 的算法复杂度仍然过高，实 际数据集的实验中表现得更为明显。1 。而对于频繁闭项集规则挖掘，更少有 相关研究。 1 3 我的工作 本文系统地研究了关联规则挖掘的整个过程，对频繁模式之挖掘、关联 规则的产生都进行了有创造性的工作。此外，我们设计实现了频繁闭项集、 频繁闭项集规则的挖掘算法。实验表明，本文提出的算法都具有相当高的时 空效率。 在频繁模式挖掘方面，本文科学地借鉴t j i a w e i ，h a n 的f p 一树，并对f p 一 树进行了改进。改进的f p 一树是单向的，不存在从树根到树叶的路径。f p 一树 高效完整地存储事务数据库，蕴含了数据库里所有的频繁项信息。通过引入 被约束子树，本文的算法在挖掘频繁模式时不生成条件f p 一树，从而大大提 高了频繁模式挖掘的效率。实验表明，与f p g r o w t h 算法相比，在相同的数 据集上，本文算法的挖掘速度提高一倍以上，而所需的存储空间却至少节省 半：随着数据库规模的增大，本文的算法具有很好的可伸缩性；对于稠密 数据集，本文的算法也具有良好的性能。 在关联规则产生方面，本文的主要工作有： ( 1 ) 提出线索频繁模式树( t h r e a d e df r e q u e n tp a t t e r nt r e e ，简记 为t f p t ) ，用于组织频繁模式； ( 2 ) 使用两种优化策略对模式j ，的子集空间进行有效地剪裁； 第9 页 堡主堡苎! 望丝茎壁塑型垄塑簦鲨堑壅 塑型奎鲎生簦垫墨 ( 3 ) 在此基础上，给出一种最短模式优先( s h o r t e s t p a t t e r nf i r s t ， 简记为s p f ) 的关联规则挖掘算法。s p f 算法可以与任何基于频繁模式增长的 频繁模式挖掘算法相结合，直接从事务数据库挖掘关联规则； ( 4 ) 通过一系列实验，分析t s p f 算法的性能，并将f p m i n e s p f 算法 ( f p m i n e 算法与s p f 算法的结合) 与a p r i o r i 算法的性能进行了对比分析。 实验表明：s p f 算法具有很好的时空效率；f p m i n e - s p f 算法挖掘关联规 则的速度远快于较长期以来广泛使用的a p r i o r i 算法，并有相当好的可伸缩 性。 此外，本文实现了频繁闭项集挖掘算法f c i s 和频繁闭项集规则的挖掘 算法c ir u l e s 。实验表明，在相同的数据集上，与已发表的最新成果一h a n 的c l o s e t 算法相比，本文算法f c i s 速度提高两个数量级以上，并有极好 的可伸缩性；c i r u l e s 算法挖掘频繁闭项集规则的运行速度较f p m i n e s p f 算法挖掘关联规则的速度快两个数量级以上，并有非凡的可伸缩性。 1 4 论文结构 论文结构安排如下： 第一章绪论 第二章对数据挖掘进行概述， 第三章讲述关联规则挖掘领域的相关工作， 第四章讲述挖掘频繁模式的f p m i n e 算法， 第五章讲述线索频繁模式树t f p i t 和关联规则挖掘算法s p f ， 第六章讲述频繁闭项集和频繁闭项集规则的概念并展示本文算p j i f c i s 和c i r u l e s 的优异性能， 第七章对本文进行总结，展望将来的工作。 第l o 页 硕士论文：单维关联规则挖掘算法研究 郑州大学计算机系 第二章数据挖掘概述 2 1 为什么数据挖掘 随着数据收集到数据库，大量数据被存储起来，仅仅对这些数据作简单 的查询、报告处理已不能满足日益增长的市场需要。如何对大量的数据进行 分析，从中提取有价值的信息和知识被放入议事日程。数据挖掘继数据收集、 数据库创建、数据提取、事务处理之后成为信息技术发明的又一领域。 信息技术自然演化的进程印证了数据挖掘产生的必然性，如图1 所示。 6 0 年代，信息技术开发出原始的文件系统来进行事务处理。7 0 年代网状数 据库、层次数据库诞生并开始流行起来。8 0 年代关系数据库系统得到了飞 速发展。s q l 语言、面向对象技术为数据库应用提供了简单、直观、可靠、 友好的用户界面，访问数据交得十分方便。8 0 年代中期以来，应用新模型 的数据库，如扩充关系的、面向对象的、对象一关系的和演绎的数据库，以 及特种数据库包括空间的、时间的、多媒体的、主动的和科学的数据库相继 出现。进入9 0 年代，i n t e r n e t 的飞速发展进一步形成全球信息系统。为了 更好地支持用户决策，数据仓库应运而生。数据仓库是多个异种数据源在单 一站点一致模式的存储。数据仓库是面向主题的、集成的、时变的和非易失 的数据存储，并能很好地支持联机分析处理( o l a p ) 。联机分析处理( o l a p ) 是一种分析技术，包括上卷、下钻、切片、切块等操作，具有汇总、合并和 聚集的功能，提供用户不同的角度和抽象层的数据视图。但是，对于关联、 分类等深层数据分析，联机分析无能为力。 海量数据被快速地收集、存入数据库，没有强有力的数据分析工具，大 量的数据没有被充分利用，除简单查询之外，很难从中得到有价值的规律性 知识，形成所谓“数据丰富，但信息贫乏”。致使大型数据库变成了“数据 坟墓”一难得再被光顾的数据档案。用户决策往往根据感觉做出而不是基于 数据库中丰富的数据，难免出现不必要的差错。 第1 l 页 堡主堕奎! 璺丝茎壁塑型丝塑簦婆婴窒 塑盟盔堂生竺! 堕墨 7 0 年代 发明d b m s 网状数据库 层次数据库关系数据库 用户界面 8 0 年代 关系d b m s 的广泛应用 s q l 的不断演进 优化技术的发展 前端应用的开发 8 0 年代到2 0 0 0 年 高级数据库系统 演绎、扩充关系、 面向对象、对象关系 特种数据库 空间、时间、主动的、 科学的、知识库 8 0 年代后到2 0 0 0 年 数据仓库和数据挖掘 数据库中知识发现 2 1 世纪 新一代信息系统 图2 1 信息技术的演化 为了使海量数据发挥其应有的价值，解决数据库知识提取的热切渴望， 为用户决策提供有力支持。数据挖掘应运而生。数据挖掘可以由海量数据库 中发现重要的模式，弥合数据和信息之间的鸿沟，指导实践活动的进行，把 “数据坟墓”变成了知识“金块”，对政府政务、商务策略、科学和医学研 究尤其有重要意义。 第1 2 页 硕士论文：单维关联规则挖掘算法研究 郑州大学计算机系 2 2 数据挖掘的概念 简而言之，数据挖掘是由大量数据中通过非一般方法发现知识的过程， 又称数据库中知识挖掘、知识提取、数据分析、数据考古或数据捕捞。数据 挖掘可被视为另一常用术语“数据库中知识发现”即k d d 的同义语，也可以 被视为k d d 过程的一个基本步骤。k d d 过程包含如下几个步骤： ( 1 ) 数据清理( 清除数据噪音和不一致数据) ( 2 ) 数据集成( 多种数据源的致模式存储) ( 3 ) 数据选择( 提取与分析任务相关的数据) ( 4 ) 数据转换( 数据转换成适合挖掘的形式) ( 5 ) 数据挖掘( 使用智能方法提取数据模式) ( 6 ) 模式评估( 根据兴趣度，识别有趣模式) ( 7 ) 知识表示( 可视化技术提供挖掘的知识) 图2 2 k d d 过程 第1 3 页 硕士论文：单维关联规则挖掘算法研究 郑州大学计算机系 数据清理、数据选择到数据转换都可看作数据挖掘的准备工作。数据挖 掘是知识发现过程最最重要的一个步骤。用户在数据挖掘步骤指定感兴趣的 模式描述，通常是兴趣度闽值或者是模型和模板，系统根据用户指示调用数 据挖掘引擎，运行结果返回用户。所以，数据挖掘的广义观点认为：数据挖 掘是由数据库、数据仓库或其它信息仓库的大量数据中挖掘用户感兴趣知识 的过程。 数据挖掘涉及数据库技术、统计分析、人工智能、算法设计、计算理论、 模式识别、神经网络、数据可视化等多学科技术的集成，发现有趣的模式、 知识，并提供各个不同的视角。所发现的知识可以用于决策、过程控制、信 息管理、查询处理，是联机分析处理的高级阶段。数据挖掘提供较联机分析 更为深入的统计分析功能，是数据库技术发展最重要的前沿，也是最有前途 的数据库新应用。 2 3 数据挖掘的功能 总体来讲，根据数据挖掘发现的模式类型，数据挖掘可以分两种：描述 性数据挖掘和预测性数据挖掘。描述性数据挖掘意在刻画数据的特性和特 征。预测性数据挖掘任务在当前数据上进行推断，以进行预测。另外，数据 挖掘能够发现各种位于不同的抽象层的模式。这些数据模式由不同的视角为 用户提供领域的知识，为用户聚焦有趣模式的搜索带来了方便。具体来讲， 数据挖掘功能大略可以归纳如下： ( 1 ) 概念描述 描述数据的分布是很有意义的。比如，对学生性别、年龄、家庭、学习 情况的刻画可以分别寻找优等生、良好学生、中等生、差生几个类型的特征， 并根据其特征进行区分。用概括的、简明的方式描述每个学生类能够帮助老 师和校方分析影响学生成绩的因素，改善教学环境、提高学生成绩。这种对 类的描述称为概念描述。概念描述可以由如下角度得到： 数据特征化( 汇总目标类的数据，发现特征) 第1 4 页 硕士论文：单维关联规则挖掘算法研究 郑州人学计算机系 数据区分( 比较目标类对比类，找到差异) 数据特征化和比较( 同时进行汇总和比较) 概念描述包括特征描述与区分描述。特征描述是对数据总体特征的刻 画，旨在发现目标类数据的大致分布特点。区分描述将目标类的特性与对比 类特性进行比较，旨在发现目标类和对比类数据分布的大体差异。 概念描述通常采用的有效方法有： 联机分析处理的上卷操作( 沿着指定维进行数据汇总) 面向属性的归纳( 自动进行数据的泛化和特化) 概念描述通常采用的特征输出方法有： 饼图、柱图、曲线、多维数据方、数据透视表 泛化关系、比较度量、特征规则、区分规则 概念描述往往是比较一般的轮廓，比如7 0 男同学英语成绩为优良， 7 0 背诵古诗的同学语文成绩为优秀。沿着指定维下钻，如a g e ( ，) ，添加新 维，如s t u d y _ h a b i t s ( ，) ，可以帮助发现两类之间的更多区分特性。 ( 2 ) 关联分析 关联分析发现展示在给定的数据集中属性值出现的关联关系。关联分 析广泛用于购物篮或事务数据分析。关联分析发现一批满足用户支持度和置 信度的关联规则。关联规则是形如xjy ，即”a l a 。jb l b 。”的蕴 涵式：其中，a i ( i l ，m ”，a j 0 1 ，n ) ) 是属性- 值对。关联规则解释为“满 足x 中条件的数据库元组多半也满足y 中条件”。 例2 , 1 给定某学校学生a l l s t u d e n t s 关系数据库，一个规则可能形如： g r a d e ( x , o n e ”) a g e ( x , 2 2 ”) e n g l i s h ( x , h i g h s c o r e d ”) m a t h ( x , m i d d l e s c o r e d ”) 【s u p p o r t = 2 ，c o n f i d e n c e = 8 0 】 规则表明，该校有2 的学生是2 2 岁，是一年级学生，英文成绩都很好，而 数学成绩一般。所有2 2 岁的一年级学生中有8 0 英文成绩好而数学成绩一 般。因为该规则涉及了多个维度，因此，上面的规则称作多维关联规则。 如果作为a l l s m d e n t s 学校的校长，想了解学生成绩分布的规律，规则 第1 5 页 堡主堡奎! 兰丝差壁塑型笙塑簦鲨塑窒 塑型奎堂堕墨型! 墨 e n g l i s h ( x , p a s s ”) je n g l i s h ( x , g o o d ”) s u p p o r t = 2 0 ，c o n f i d e n c e = 7 0 描述 了英语成绩的分布规律。该规则表明，英语成绩通过且成绩为好的学生占学 生总数的2 0 ，所有通过的学生中，成绩为好的占7 0 。规则涉及单个谓 词( e n g l i s h ( ，) ) 称作单维关联规则。而且，规则实际上涉及两个概念层次， “通过”包含“好”，所以称为多层次关联规则。 本文讨论的是单维关联规则的挖掘算法。 ( 3 ) 分类和预测 分类是通过训练数据集和测试数据集试图发现精度达到一定程度的分 类模型的过程。分类模型的建立能够用来预测类标号未知的对象的类。分类 模型可以用多种形式表示，如分类( i f t h e n ) 规则、判定树、数学公式、 或神经网络。判定树是一个类似于流程图的结构，每个树内结点代表一个属 性值上的测试，每个分枝代表一个测试路经，树叶节点代表类。判定树容易 转换成分类规则。神经网络是线性阈值单元的集合，可以识别不同的类对象。 分类用于预测数据对象的类标号。然而，某些应用中，可能希望预测某 些遗漏或空缺值，而非类标号，通常称预测。预测，通常限于值预测，不同 于分类。数据发展趋势预测，如人口发展趋势，天气预报都属于预测。 例2 2 如果作为a l l s t u d c n t s 的学校校长，想根据学生平时的学习习惯对 其成绩进行分类。学习成绩分为优秀、良好、中等、较差几类。 图2 3 判定树示例 第1 6 页 堡圭造壅! 璺丝差壁塑型堡塑簦堡婴窒 塑型奎堂生簦垫墨 通过训练数据集得到该判定树，就可以根据学生平时的表现推测其成绩优 良。 ( 4 ) 聚类分析 聚类不同于分类，事先不知道有几个类，聚类分析数据点之间的相似程 度，根据类内尽可能相似和类间尽可能不同的聚类原则对数据对象进行分组 并生成新的类标号。聚类分析广泛应用于客户分析、市场划分、模式识别、 数据预处理。 例2 3 聚类分析可在a l l s t u d e n t s 的数据上进行通过学生不同特点和习 惯进行聚类，以便根据学生的特点因材施教。 ( 5 ) 演变和偏差分析 演变分析描述事物随时间变化的规律性或趋势，包括时间相关数据的特 征、区分、关联、分类或聚类，这类分析的不同特点包括时间序列分析、序 列或周期模式匹配和类似性数据分析。 例2 4 如果你有股票交易所过去几年的股票走势历史数据，希望对股票 走势的运行规律进行分析研究的话，可以应用演变分析。股票历史数据演变 分析可以识别股票的演变规律。这种规律有助于预测股票的变化趋势，协助 进行投资决策。 2 4 数据挖掘的分类 数据挖掘是一个建立于包括数据库系统、统计分析、机器学习、人工智 能、信息科学等多个领域的交叉学科。同时，哲学、心理学等学科为数据挖 掘的发展导引方向。数据挖掘采用的技术十分广泛，如神经网络、模糊集理 论、知识表示、归纳逻辑程序设计、或高性能计算等。对于不同数据类型或 不同应用，数据挖掘系统还可集成空间数据分析、信息提取、模式识别、图 象分析、信号处理、计算机图形学、w e b 技术、经济、或心理学等领域的 技术。 第1 7 页 硕士论文：单维关联规则挖掘算法研究郑州i 大学计算机系 计算理论 图2 4 数据挖掘基于多个学科领域 根据不同的角度，数据挖掘系统可以分类如下 ( 1 ) 根据数据库类型分类 数据挖掘系统可以根据被挖掘的数据库类型分类。 不同数据库系统可能采用不同的数据模型，需要不同的数据挖掘技术。 数据挖掘系统就可以相应分类。根据数据不同模型，有关系的、面向对象的、 对象一关系的、或数据仓库的数据挖掘系统。 ( 2 ) 根据应用背景分类 不同数据库系统有不同的应用背景，需要不同的数据挖掘技术。根据所 处理的数据的不同类型分类，有空间的、时间序列的、文本的、多媒体的、 w w w 的、主动的数据挖掘系统。还有异种数据库挖掘系统和遗产数据挖掘 系统等。 ( 3 ) 根据挖掘的知识类型分类 根据数据挖掘系统所挖掘的知识类型，即根据数据挖掘的不同功能，如 特征、区分、关联、聚类、趋势和演化分析等进行分类。数据挖掘系统还可 以根据所挖掘的知识的不同粒度或抽象层进行区分，包括泛化知识，原始层 知识，或多层知识等。 ( 4 ) 根据应用的不同技术分类 第1 8 页 硕士论文：单维关联规则挖掘算法研究郑州大学计算机系 数据挖掘可以根据所用不同数据挖掘技术进行分类。这些技术可以根据 用户交互程度，或所用的数据分析方法描述，例如，面向数据库或数据仓库 的技术、机器学习、统计、显象、模式识别、神经网络等。复杂的数据挖掘 系统通常采用多种数据挖掘技术，或采用有效的、集成的技术，结合一些方 法的优点【1 1 。 第1 9 页 堡圭笙苎! 苎丝羞壁塑墨! 垫塑竺鎏盟壅 塑型查兰生墨塑至 第三章问题描述和相关工作 3 1 关联规则的背景 关联规则发现数据彼此之间的相联关系，是数据挖掘的重要内容 1 5 , 1 7 】。 哲学上讲，知识、规律就是事物之间的联系。在高度数字化的环境下，挖掘 关联规则就是找寻现实世界中的真理。关联规则挖掘在聚类、分类、预测、 孤立点发现中有重要的角色，在基因生物学、地质开采、商务分析、企业内 部管理、工业过程重工程、全质量管理、政府决策领域有重要的应用。研究 关联规则产生的高效算法对于科学研究、生产实践具有重要意义。 根据关联规则涉及的维数、各个维的概念层次、值的离散度、规则的特 征可以将关联规则按不同的角度进行分类。 ( 1 ) 根据规则处理值的类型： 如果规则各个项讨论的是项的是否存在，则是布尔关联规则。反之，如 果规则考虑的是不同项间关联的量化程度，则规则是量化关联规则。对薰化 规则，项的值被划分为各个不同区间。 下面分别给出布尔关联规则和量化关联规则的例子： 布尔关联规则 s t u d y c u s t o m s ( x , m o r n i n g r e a d i n g ”) je n g l i s h ( x , p a s s ”) 【s u p p o r t = 2 0 ，c o n f i d e n c e = 5 0 】 量化关联规则 e n g l i s h ( x , 7 0 8 0 ) m a t h ( x , 8 0 1 0 0 ) j s c h o l a r s h i p ( x , 力打一s t u d e n t ) 【s u p p o r t = 5 0 ，c o n f i d e n c e = 2 0 】 ( 2 ) 根据规则涉及的数据维数： 根据关联规则涉及维数，可以分为单维关联规则和多维关联规则。关 联规则只涉及一个维时，称为单维关联规则。例如 第2 0 页 硕士论文：单维关联规则挖掘算法研究 郑州火学计算机系 s t u d y h a b i t ( x , m o r n i n g r e a d i n g ”) js t u d y h a b i t ( x , e v e n i n g r e a d i n g ”) s u pp o r t = 2 0 ，c o n f i d e n c e = 5 0 1 该关联规则只涉及一个维s t u d y h a b i t ( ) 。 如果规则涉及多个维，称为多维关联规则“，如 s t u d y h a b i t ( x ，”m o r n i n g r e a d i n g ”) je n g l i s h ( x , e x c e l l e n t ”) s u p p o r t = 5 0 ，c o n f i d e n c e = 2 0 】 关联规则涉及维s t u d y h a b i t ( ) ，e n g l i s h ( ) 两个维度 ( 3 ) 根据规则所涉及的抽象层： 根据关联规则涉及的不同抽象层，关联规则可分为单层关联规则和多层 关联规则。如果关联规则的各个维度仅涉及一个概念层，称为单层关联规则， 例如 s t u d y h a b i t ( x , m o r n i n g r e a d i n g ”) js c h o l a r s h i p ( x , m e d i a n ”) s u p p o r t = 2 0 ，c o n f i d e n c e = 5 0 】 如果规则涉及不同的抽象层，如 c h i n e s e ( x , p a s s ”) 等e n g l i s h ( x , g o o d ”) 【s u p p o r t = 5 0 ，c o n f i d e n c e = 2 0 嘲 称为多层关联规则 ( 4 ) 根据关联规则涉及关联的自然特性进行分类：识别相关的项是否 存在。 3 2 关联规则的定义 1 9 9 3 年，r a g g r a w a l 首次提出关联规则的定义和挖掘关联规则的“项 集”方法“，从此开始了对关联规则挖掘的研究。近年来出现了很多高效的 关联规则挖掘算法。一些新的兴趣度度量也陆续被提出。但关联规则的基本 定义延续下来，关联规则挖掘的基本方法一“项集方法”也沿用下来。 定义3 1 项( i t e m ) 是一个文字；在交易数据库中，它可以代表商品；在 分类时，它可以代表属性值对。 定义3 2 设，2 i z ，i 2 ，i m ) 为项的全集，d = 乃，乃，n ) 为事务数 第2 1 页 硕士论文：单维关联规则挖掘算法研究 郑州