（信号与信息处理专业论文）关联规则挖掘算法研究.pdf

摘要 f 知识就是力量。当前快速发展的新的i t 技术、电子商务及互联网的迅速普及， 导致在各个应用领域的数据库中存储了大量的数据，这些数据集中包含了很多有 用的知识，出此如何发现各种大型数据库中所隐藏的、预先未知的信息以辅助相 应的应用显得尤为重要，这正是数掘挖掘所要完成的任务。近年来国外学者提出 了一系列的数据挖掘理论，世界上的主要i t 公司，如i b m 、o r a c l e 及m i c r o s o f t 等也己相继推出了各自的数据挖掘产晶。关联规则挖掘作为数据挖掘的一个重要 研究分支，其主要的研究目的是从大型数掘集中发现隐减的、有趣的、属性问存 在的规律。由于形式简单、易于理解，且是从人型数据中提取知识的主要手段， 因此关联规则挖掘的研究与应用已经得到了数据库、人工智能及统计学等领域罩 的学者的极大关注，并取得了不少的研究成果。与人工智能中的神经网络、遗传 算法及统计学不同的是，关联规则挖掘处理的对象是大型的数据集，而神经网络 和遗传算法等人工智能方法通常处理的数据对象通常相对较小，且人工智能的方 法重在寻找输入输出i 刈的模型，而关联规则的挖掘则是用于发现数据集合中所包 含的属性问的规律，其结果不是一个具体的模型而是数量众多的规则。此外，统 计学中的方法尽管处理的对象也可以是大量的数据，然而其主要作用是用于确定 数据的统计分布或统计模型，而不能描述数据集中所包含的属性恻的规律本文 在国家8 6 3 项目的资助下，主要对含有项目约束的关联规则挖掘、模糊数值约束 的关联规则挖掘、优化关联规则的解空间、w e b 使用挖掘及数值型关联规则挖掘 的统计方法进行了深入的研究和探讨，提出了一系列的定义、定理及新算法，解 决了若干理论和实际方面的问题。 第2 章系统地介绍了含有约束的关联规则挖掘的分类，给出了含有约束的关 联规则挖掘的定义、定理及算法。从技术的观点详细介绍了其目前的发展状况， 给出了关联规则挖掘中( 特r 0 是合有项目约束的关联规则挖掘中1 相关的定义及名 词解释，提出了挖掘含有项目约束的关联规则的一些重要定理，设计了高效的挖 掘算法，本文提供的方法可以有效地解决低支持度、长模式的关联规则挖掘问题。j 第3 章利用模糊集理论解决了现有的关联规则挖掘方法中未考虑与项目相关 的数值信息的缺陷，提出了含有模糊数值约束的关联规则的定义、算法。f 将模糊 查询和规则模板的概念有机的结合起来，给出了挖掘含有模糊数值约束的关联规 则的公式和完整的挖掘方法，给出了相关的实验设计。f 实验结果表明本文给出的 研究方法对于挖掘含有数值约束的关联规则具有一定的指导意义“ 第4 章讨论了如何优化关联规则的解空间的问题。提出了意想不到的关联规 则( 即对用户来说是有趣的规则) 的定义、算法。恰出了两类意想不到的关联规 则的定义，一类是意想不到的模板规则，本文认为模板规则中的一部分有必要进 行更新，以纠正领域知识的偏差，纠正后的模板规则对于以后的挖掘具有非常重 要的作用。另外一类是与规则模板后项不同的意想不到的规则，这类规则实际上 就是我们最终需要提交给用户的主要结果，即那些事先无法预见的规则。给出了 相关的挖掘算法，提出了利用x 2 检验的方法去除那些缺乏相关的项集的方法t 提 出了利用信息增益对第二类规则进行排序的方法，并指出信息增益越大的规则是 有趣度越大的规则。在算法设计时，提出了修改后的a p r i o r i 框架，使得生成的频 繁集数量得到了大大的减少，从而提高了算法的效率i 。 第5 章给出了对w e b 日志数据进行挖掘的相关定义及算法( e l iw e b 使用挖掘) 。 f 给f 了聚合记录、客户记录、及客户序列的定义及它们恻的包含关系等，这些定 义为进一步的算法设计提供了有力的工具和理论基础。| 在讨论对w 曲日志文件进 行挖掘的相关算法时，本文充分考虑了时阳j 约束的问题，给出了利用新颖的数据 结构( p t 树) 生成备选集的重要方法。哒与其他文献中利用散列树生成备选集的 方法相比具有很大优越性，第一减少了不必要的节点的生成，因此树的体积变得 相对较小；此外，p t 树的查找方法更为简单，无需采用散列函数，因此降低了算 法的运行时问，提高了效率。设计了相关的实验数据，并用实验说明了所给算法 的有效性。) 第6 章给出了多概念层次的数值型关联规则挖掘定义及算法的框架，多概念 层次的数值关联规则挖掘实际上是利用了统计学中的假设检验的方法来确定规则 的有趣程度，由于这类规则在提交给用户的时候需要个比较项，因此有利于用 户的理解，同时对它的挖掘可以回避最小信任度门限的指定。介绍了利用修正差 值分析作为有趣度评判标准的数值型关联规则挖掘的定义及算法。咳算法的优点 是既可以发现正相关的规则也可以发现负相关的规则，同时可以避免人为指定最 小信任度门限的麻烦，特别是该算法发掘的规则往往是其他算法所忽略的重要规 则。本文所有各章的工作均是围绕如何提高关联规则的挖掘效率进行的，所不同 的是研究角度不一样罢了。、 关键词：数据挖掘 关联规则挖掘 数值型关联规则 项目约束 模糊数值约束 w e b 使用挖掘 a b s t r a c t k n o w l e d g ei ss t r e n g t h w i t ht h er e p a i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , t h e d e v e l o p m e n to f e c o m m e r c ea n dd e v e l o p m e n to fw w w a p p l i c a t i o n s ，m a s s i v ea m o u n t s o fd a t ah a v eb e e nc o n t i n u o u s l yc o l l e c t e di nt h ed a t a b a s e so fm a n ya p p l i c a t i o na r e a s ， w h i c hc o n t a i nm u c hu s e f u lp a t t e r n s ，a n di ti s v e r yi m p o r t a n tt o f i n dt h eh i d d e na n d p r e v i o u s l y u n k n o w ni n f o r m a t i o nf o rt h e s ea r e a s ，d a t am i n i n ga i m sa tt h et a s ko ft h e a b o v ew o r k i nr e c e n ty e a r s ，s o m en e w c o n c e p t sa n dt h e o r i e so f d a t am i n i n gh a v eb e e n p r o p o s e d 、a n dm a n y d a t am i n i n gp r o d u c t sa r ea l s op r e s e n t e db ys o m ew o r di m p o r t a n ti t c o m p a n i e s ( s u c ha si b m ，o r a c l ea n dm i c r o s o f t ，e t c ) a s s o c i a t i o nr u l em i n i n gi s af o r m o fd a t a m i n i n g t od i s c o v e r p r e v i o u s l yu n k n o w n ，i n t e r e s t i n gr e l a t i o n s h i p sa m o n g a t t r i b u t e sf r o ml a r g ed a t a b a s e s d u et oi t ss i m p l ef o r ma n db e i n ge a s yt ou n d e r s t a n d ， a s s o c i a t i o nr u l em i n i n gh a sa t t r a c t e dg r e a ta t t e n t i o ni nd a t a b a s e ，a r t i f i c i a li n t e l l i g e n ta n d s t a t i s t i c sc o m m u n i t i e s ，a n dal o ta c h i e v e m e n t sh a v eb e e nm a d ei ni t ss t u d y c o m p a r e d w i t ha r t i f i c i a lm e t h o d ，s u c ha sn e u r a ln e t w o r k ，g e n e t i ca l g o l 。i t t u na n ds t a t i s t i c s ，i tc a n p r o c e s s e sl a r g e rd a t a s e t ，o nt h eo t h e rh a n d ，a r t i f i c i a lm e t h o du s u a l l yp r o c e s s e sas m a l l s e to fd a t a ，a n di ta i m sa tf i n d i n gam o d e lb e t w e e ni n p u t sa n do u t p u t s a s s o c i a t i o nr u l e m i n i n g c a nf i n dl a r g en u m b e ro f p a t t e r n sa m o n ga t t r i b u t e s f u r t h e r m o r e ，a l t h o u g hl a r g e d a t a s e t sc a nb ep r o c e s s e di ns t a t i s t i c s ，t h e s ew o r ka i m sa tf i n d i n gd a t ad i s t r i b u t i o n so r s t a t i s t i c a lm o d e l s u p p o r t e db yn a t i o n a l8 6 3p r o j e c t ，t h i sd i s s e r t a t i o nm a i n l yf o c u so n s o m e k e yp r o b l e m s ，i n c l u d i n ga s s o c i a t i o nr u l em i n i n gw i t hi t e mc o n s t r a i n t s ，a s s o c i a t i o n r u l em i n i n gw i t hf u z z yq u a n t i t a t i v ec o n s t r a i n t s ，o p t i m i z e da s s o c i a t i o nr u l em i n i n g ，w e b u s a g em i n i n ga n dq u a n t i t a t i v ea s s o c i a t i o nr u l em i n i n gu s i n gs t a t i s t i c a lm e t h o d s o m e n e wd e f i n i t i o n s ，t h e o r e m sa n da l g o r i t h m sa r ep r e s e n t e da n dt e s t e d ，a n ds o m ep r o b l e m s i nb o t h t h e o r y a n d p r a c t i c a la p p l i c a t i o n s a r es o l v e d s u c c e s s f u l l y t h em a j o r a c h i e v e m e n t so ft h i sd i s s e r t a t i o na r e ： i nc h a p t e r2 ，t h ec a t e g o r i e so fc o n s t r a i n t si na s s o c i a t i o nr u l em i n i n ga r ei n t r o d u c e d ； d e f i n i t i o n s ，t h e o r e m sa n da l g o r i t h m so fa s s o c i a t i o nr u l em i n i n gw i t hi t e mc o n s t r a i n t s a r ep r e s e n t e d i t sc u r r e n td e v e l o p m e n ti sd e t a i l e df r o mt h ep o i n to ft e c h n o l o g y ；s o m e a s s o c i a t e dc o n c e p t sa n dd e f i n i t i o n sa r ee x p l a i n e d t h ee f f e c t i v ea l g o r i t h mp r e s e n t e di n t h i s c h a p t e ri sv e r y s u i t a b l ef o rm i n i n ga s s o c i a t i o nr u l e sw i t hl o ws u p p o r ta n dl o n g p a t t e r n s i n c h a p t e r 3 ，t h ep r o b l e mi n a s s o c i a t i o nr u l e s m i n i n gt h a t f a i lt oc o n s i d e rt h e q u a n t i t a t i v e i n f o r m a t i o na s s o c i a t e dw i t hi t e m si ss o l v e db a s e do n f u z z yt h e o r y a s s o c i a t e dd e f i n i t i o n sa n da l g o r i t h m sa r ep r e s e n t e d f u z z yq u e r ya n dr u l e t e m p l a t e c o n c e p t s a r ec o m b i n e de f f e c t i v e l y , f o r m u l a sa n dc o m p l e t em i n i n gm e t h o da r ep r e s e n t e d ， e x p e r i m e n t s a r ed e s i g n e dt h ee x p e r i m e n tr e s u l t ss h o wt h em e t h o dp r e s e n t e di sau s e f u l g u i d ef o rm i n i n g a s s o c i a t i o nr u l e sw i t hq u a n t i t a t i v ec o n s t r a i n t s a n di nc h a p t e r4 ，t h ep r o b l e m so fo p t i m i z e da s s o c i a t i o nr u l em i n i n ga r ed i s c u s s e d s o m ed e f i n i t i o n sa n dt h e o r e m so fu n e x p e c t e da s s o c i a t i o nr u l e sa r ep r e s e n t e d t w ok i n d s o fu n e x p e c t e da s s o c i a t i o nr u l e sa r ed e f i n e d ，o n ek i n di su n e x p e c t e dt e m p l a t er u l e s ， a n o & e rk i n di sa s s o c i a t i o nr u l e sw i t hd i f f e r e n tc o n s e q u e n tw i t ht e m p l a t er u l e s ，t h i sk i n d o fr u l e sa r et h ef i n a lr e s u l t sp r e s e n t e dt ou s e r s a s s o c i a t e da l g o r i t h m sa r ep r e s e n t e d ， m e t h o do fp r u n i n gi t e m s e t sw i t hx 2t e s ti sp r o p o s e d ，m e t h o do fo r d e r i n gt h es e c o n d k i n dr u l e su s i n gi n f o r m a t i o ng a i ni sa l s op r e s e n t e d ，a n dt h ei d e at h a tt h el a r g e rt h e i n f o r m a t i o ng a i n ，t h el a r g e rt h ei n t e r e s tm e a s u r ei sp o i n t e d i nd e s i g no f a l g o r i t h m s ，t h e a d j u s t e da p r i o r if r a m e w o r ki sp l e s e n t e d ，i tg e n e r a t e ss m a l ls e t so fi t e m s e t s ，l e a d i n gt o e f f i c i e n c yi m p r o v e m e n t so f t h ea l g o r i t l u n s i nc h a p t e r5 ，t h ep r o b l e m so fw e b u s a g em i n i n ga r ed i s c u s s e d t h ed e f i n i t i o n sa n d i n c l u s i o nr e l a t i o n so fc l u s t e r e dr e c o r d ，c l i e n tr e c o r da n dc l i e n ts e q u e n c ea r ep r e s e n t e d ， t i f f s g i v e s t h eb a s i so ff u r t h e rd e s i g no fa l g o r i t h m s i nd i s c u s s i n gt h ea l g o r i t h m so f m i n i n gm e t h o d ，t h i sd i s s e r t a t i o nc o n s i d e r sm u c hi nt i m ec o n s t r a i n t s ，a n dp r e s e n t e da n o v c ld a t as t r u c t u r e ( p tt r e e ) f o rg e n e r a t i n gc a n d i d a t ei t e m s e t s ，c o m p a r e dw i t ho t h e r m e t h o d st h a tu s e sh a s ht r e es t r u c t u r e ，i th a st w oi m p o r t a n t a d v a n t a g e s ：f i r s t l y , i ta v o i d s g e n e r a t i n gm o r en o d e s ，s ot h ev o l u m eo f p tt r e ei sr e l a t i v e l ys m a l l s e c o n d l y , i ta v o i d s u s i n gh a s hf u n c t i o ni ns e a r c h i n go f t h et r e e ，t h i si m p r o v e sr u n n i n gs p e e da n de f f i c i e n c y o f a l g o r i t h m s i nc h a p t e r6 ，w ed e s c r i b et h e p r o b l e m so fq u a n t i t a t i v ea s s o c i a t i o nr u l em i n i n gu s i n g s t a t i s t i c a lm e t h o d a na l g o r i t h m su s i n ga d j u s t e dd i f f e r e n c ea n a l y s i sa st h e i n t e r e s t i n g m e a s u r ei si n t r o d u c e d ，p o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e sc a nb em i n e d u s i n gt h i s m e t h o d a n d c o n c e p t s o fm i n i n g m u l t i - c o n c e p tq u a n t i t a t i v e a s s o c i a t i o nr u l e sa r e p r e s e n t e d i nf a c t ，w ef o c u so nt h ek e yp r o b l e mt h r o u g h o u tt h ed i s s e r t a t i o nt h a ti sh o w t o i m p r o v et h ee f f i c i e n c i e so fa s s o c i a t i o nr u l em i n i n g t h eo n l yd i f f e r e n c eb e t w e e n c h a p t e r si st h e i rs t u d y i n gp o i n t 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 em i n i n g q u a n t i t a t i v ea s s o c i a t i o nr u l em i n i n g f u z z yq u a n t i t a t i v ec o n s t r a i n t s w e b u s a g em i n i n g i t e mc o n s t r a i n t s 第一章绪论 l 第一章绪论 本章主要介绍了数据挖掘和关联规则挖掘的基本概念，概述了关联规则挖掘 的研究进展和现状，阐述了其与数据库、人工智能及统计学等领域的关系，列举 了本丈的主要研究工作，并给出了全文的内容安排。 1 1 数据挖掘和关联规则挖掘的概念 随着计算机和自动化数据采集工具的广泛应用，在各种应用领域里的数据库 中存储了大量的数据，这使得人们对这些数据进行分析并转化为有用知识的需求 变得越来越迫切【l 】。于是知识发现与数据挖掘( k n o w l e d g ed i s c o v e r y a n dd a t a m i n i n g ，k d d ) 自然成为近年来人们从大型数据库中获取信息的一个重要的研究领 域。一般地，数据挖掘就是指从数据库或数据仓库中发现隐藏的、预先未知的、 有趣的信息的过程，该过程可以看作是知识发现过程中的一个核心的步骤【2 1 。数 据挖掘的主要功能包括，聚类( c l u s t t e r i n g ) 、分类( c l a s s i f i c a t i o n ) 、预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 i m e s e r i e sa n a l y s i s ) 等。 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是数据挖掘研究的一个重要分支，关联 规则是数据挖掘的众多知识类型中最为典型的一种。该问题于1 9 9 3 年由a g r a w a l 等人在对市场购物蓝问题( m a r k e tb a s k e ta n a l y s i s ) 进行分析时首次提出日】，用以发 现商品销售中的顾客购买模式。关联规则挖掘可以发现存在于数据库中的项目 ( i t e m s ) 或属l 生( a t t r i b u t e s ) l h q 的有趣关系，这些关系是预先未知的和被隐藏的，也就 是说不能通过数据库的逻辑操作( 如：表的联接) 或统计的方法得出。这说明它 们不是基于数据自身的固有属性( 例如函数依赖关系，f u n c t i o n a ld e p e n d e n c y r e l a t i o n s h i p ) ，而是基于数据项目的同时出现特征( c h a r a c t e r i s t i c so fc o o c c u r e n c e o f d a t ai t e m s ) ，所发现的关联规则可以辅助人们进行市场运作( m a r k e t i n g ) 、决策支 持( d e c i s i o ns u p p o r t ) 及商业管t 里( b u s i n e s sm a n a g e m e n t ) ，网站设计( w e b s i t ed e s i g n ) 等。一个关联规则例子是：“9 8 的购买轮胎和汽车配件的顾客也购买汽车保养服 务”。由于关联规则是数据挖掘研究的一个分支，因此在不至混淆的情况下，下述 在介绍其应用与研究进展时可能在用词上对二者不加区别。 目前关联规则挖掘问题已经引起了数据库、人工智能、统计学、信息检索、 可视化及信息科学等诸多领域里的广大学者和研究机构的格外重视，并取得了不 少的研究成果。由于关联规则形式简洁、易于解释和理解并可以有效的捕捉数据 间的重要关系，因此从大型数据库中挖掘关联规则的问题已经成为近年来数据挖 2博士学位论文： 关联规则挖掘算法研究 掘研究领域中的一个热点f 2 】【3 】f 4 】【5 1 1 6 】 7 】【8 】【9 】【1 0 1 1 1 1 】【1 2 j 【1 5 【1 6 j 【3 5 】【1 0 6 1 。 关联规则是什么? 一般地，关联规则挖掘是指从一个大型的数据集( d a t a s e t ) 中发现有趣的关联 r a s s o c i a t i o n ) 或相关( c o r r e l a t i o n ) 关系，即从数据集中识别出频繁出现的属性值集 f s e t so fa t t r i b u t e v a l u e s ) ，也称为频繁项集( f r e q u e n ti t e m s e t s ，简称频繁集) ，然后 再利用这些频繁集创建描述关联关系的规则的过程。关联规则研究中所使用的很 多词汇都与其诞生时的背景有关，a g r a w a l 等人首先研究的是顾客对商品的购买行 为，并为一些术语给出了原始的解释，如项目( i t e m ) 是指顾客所购买的商品，而项 集( i t e m s e t s ) 指的是顾客所购买的一组商品。其后的研究一直沿用了这些称谓，只 不过在具体的应用环境中，这些词汇所代表的内容不同罢了。关联规则的形式为 x j y ，x 称为规则的前项项集( a n t e c e d e n ti t e m s e t ) ，简称前项；y 称为后项项集 f c o n s e q u e n ti t e m s e t ) ，简称后项。它说明数据库中的某一条记录如果包含了x ，那 么也倾向于包含y ，或者说，如果数据库中的某条记录使x 中的属性值为真，则 也倾向于使y 中的属性值为真。一个较为详细的例子是：“9 8 的购买轮胎和汽车 配件的顾客也购买汽车保养服务( 在全部客户中有1 5 的客户同时购买了轮胎、 汽车配件及汽车保养服务) ”。这里的轮胎和汽车配件是前项项集，汽车保养服 务是后项项集，9 8 是规则的信任度( c o n f i d e n c e ) ，而1 5 是规则的支持度( s u p p o r t ) 。 支持度说明了数据库中对规则支持的客户的比例，即，使( x u y ) 为真的客户在整个 数据库中所占的比例，信任度说明了同时满足前、后项( x u y ) 的记录占满足前项( x ) 的记录的比例，即规则值得信任的程度。通常，用户为了达到一定的要求，都需 要指定规则必须满足的支持度和信任度的门限，称其为最小支持度( m i n i m u m s u p p o r t ) 和最小信任度( m i n i m u mc o n f i d e n c e ) 。 给定一个事务数据集( t r a n s a c t i o nd a t a s e t ) d 及用户指定的最小支持度( m i n )sup 与最小信任度( m i n ，关联挖掘问题即是发现所有满足最小支持度与最小信任_conf) 度约束的关联规则。 例1 1 下面是关联规则的两个例子， 1 ) p r o d u c t ( t ，“联想家用电脑”) = p r o d u c t ( t , “清华紫光扫描仪”) 此处，t 是表示事务记录( t r a n s a c t i o nr e c o r d ) 的变量，它对应了某个用户的一次购 买行为。这种情况下，数据库中的项目是顾客所购买的商品，而每一条记录则表 示了一个顾客购买的所有商品的集合。该规则的含义是，如果某位贵客( t ) 购买了 联想家用电脑，则他( 她) 也倾向于同时购买清华紫光扫描仪。 2 ) a g e ( t , “3 0 一3 9 ，) ，o c c u p a t i o n ( t , “学生”) j p r o d u c t ( t , “膝上电脑”) 该规则说明一个年龄在3 0 3 9 之间的学生将很可能购买膝上电脑。 通常为了表述的方便，关联规则中都省略了t ，而是采用如下的表述形式( 以 上述两个例子为例) ： 第一苹绪论 3 3 r 联想家用电脑”“清华紫光扫描仪” 4 、a g e = “3 0 3 9 ”a n do c c u p a t i o n = “学生”j “膝上电脑” 其中“联想家用电脑”、“清华紫光扫描仪”、“膝上电脑”称为布尔属性 ( b o o l e a na t t r i b u t e s ) ，因为它们只有两个状态，包含或不包含；a g e 为数值属性 ( q u a n t i t a t i v ea t t r i b u t e s ) 而o c c u p a t i o n 为分类属。i 生( c a t e g o r i c a la t t r i b u t e s ) ，因为它们 有不止一个的类别。布尔属性可以看作分类属性的一种特例，即只有一种分类的 属性。 1 2 关联规则挖掘与其它研究领域的关系及其研究现状 1 2 1 关联规则挖掘与其它研究领域的关系 与关联规则挖掘最相关的三个重要的研究领域是，统计学( s t a t i s t i c s ) 、机器学 习( m a c h i n el e a r n i n g ) ( 或称人工智能，a r t i f i c i a li n t e l l i g e n t ) 及数据库( d a t a b a s e ) 。关 联规则挖掘与统计学和机器学习的共同特点是：都是从数据集中发现知识：而不 同点主要表现为：1 ) 对于统计学来说，其主要任务是分析数据或用相对复杂的模 型匹配数据。如：计算方差、均值、重要性及偏差等，或者寻找与大量数据匹配 的统计模型( 统计分布) ，其所描述的都是关于数据自身的固有属性。而关联规则挖 掘则是自动地对大量的、相对简单的特性进行估价，其所描述的是数据中所隐藏 的特性，且规则的数量大、形式简单。2 ) 许多机器学习( 或人工智能) 领域里的 学者认为，机器学习涵盖了数据挖掘，实际上二者之间也存在许多不同之处：通 常机器学习的主要任务是发现输入和输出属性间的规律或模型，而关联挖掘则挖 掘通常并不硬性规定哪些项目定为输出，哪些项目为输入属性( 在没有项目约束 的前提下) ，其作用是发现所有属性间可能存在的规律。此外，数据挖掘中所处理 的数据的量要远远大于机器学习中所处理的数据量。尽管存在很多的不同点，但 是他们之间的联系仍然是较为紧密的，统计学和机器学习中的许多概念和成果仍 然在数据挖掘研究中起着重要的作用，例如关联规则挖掘中的支持度、信任度等 概念就体现了统计的概念，人工智能领域中的遗传算法、分类、聚类及模糊数学 的概念也在数据挖掘中得到了广泛的应用：另一方面，数据挖掘的成果也经常被 应用于人工智能领域，如在含有众多变量的环境里如何有效的选择输入和输出的 变量问题，就可以借助数据挖掘的方法。3 ) 关联规则挖掘与数据库研究领域中的 关系最为紧密，因为关联规则挖掘的对象就是现有的数据库或数据仓库，且数据 库技术( 如在线分析处理、索引技术等) 对于关联规则挖掘的研究起重要作用。 不过二者间仍然有很大的不同：数据库中的功能通常是数据库中信息的逻辑操作 结果( 例如两个表的i o i n 操作) ，并且可以证明得出的是关于数据的正确的结论( 只 4博士学位论文：关联规则挖掘算法研究 i i i i i i i i i i i n i h l i l i i i i i i i i i ；i 要数据库中提供的数据是正确的) 。而关联规则挖掘所得出的结果仅能证明数据库 中的数据支持这些规则，但是这些规则在现实世界中是否适用则不能肯定，因此 数据挖掘的主要任务是选择那些被数据库所支持的、看上去最为合理的和有趣的 规则或规律。目前数据挖掘查询语言( d a t am i n i n gq u e r yl a n g u a g e ) 及在线分析 挖掘技术( o n 1 i n ea n a l y t i c a lm i n i n gt e c h n o l o g y ) 等就是数据库技术与数据挖掘结 合应用的具体体现。 1 2 2 关联规则挖掘研究的现状 由于关联规则挖掘可以发现用传统的人工智能和统计方法所无法发现的规则 或规律，因此其具有重要的研究价值。且由于其处理的数据量十分巨大( 从几m 到几百m ，甚至更大的数据量) ，所得的规则往往数量大，因此也迎合了人们从当 今日益增长的电子化数据中获取知识的迫切需求。目前世界上知名大学的研究机 构和各大i t 公司的研究部门都投入了大量精力对其进行研究，并取得了诸多的研 究成果。美国斯坦福大学智能数据库系统实验室开发出了大量的商用化数据挖掘 系统，如d b m i n e r 挖掘系统，该系统包含了许多先进的挖掘算法，并有很多优秀 的特点：用户无需具有高级的统计知识和培训即可使用该软件，因为底层的挖掘 细节对于用户是不透明的：掘的知识类型多种多样，从关联规则、序列模式 f s e q u e n c ep a t t e m ) 至f j 发现驱动( d i s c o v e r y d r i v e n ) 的分类等；并且由于采用了许多先 进的研究成果，因此该产品的速度声称是其同类竞争者的2 0 倍：此外该系统可以 在多种平台上运行，并与许多主流的数据库系统( 如：s q l s e v e r 、o r a c l e 等) 结合 紧密；同时还引入了在线分析挖掘技术，使得系统更能充分发挥数据仓库的分析 优势。i b m 的a l m a d e n 实验室所进行的q u e s t 项目同样也是数据挖掘研究领域中 的佼佼者，该项研究包含了对关联规则、序列模式、分类及时间序列聚类( t i m e s e r i e sc l u s t e r i n g ) 的研究，其代表性的产品有：d b 2i n t e l l i g e n tm i n e rf o rd a t a ，该产 品是在i b m d b 2 平台下的系统，当然也有w i n d o w s n t 下的类似产品。此外，美 国的宾西法尼亚大学的数据挖掘研究小组也在这些方面取得了显著成果，其主要 研究包括：利用注释和文本对数以百万计的文章进行聚类和分析：从多家医院的 病人数据库中发现可以提高医疗质量和降低医疗费用的模式：在构建一个模型中 选择合适的变量：基于d n a 序列预测基因模式等等。目前世界上比较知名的数据 库公司，如o r a c l e 、s y b a s e 等都已经在不同程度上将数据挖掘的有关技术结合到 其对应的数据库产品中来，使得大型数据库的功能向智能化的方向迈进了重要的 一步。除了上面提到的世界上比较知名的公司和研究机构外，其他还有很多大学 的研究机构和学者也对该领域的发展做出了重要贡献，如加拿大的s i m o nf r a s e r 大学的j i a w e ih a n ，比利时赫尔辛基大学的m a n n i l a 、t o i v o n n e n 等都是享誉世界的 数据挖掘研究的顶尖学者，它们的许多工作都是该领域中具有奠基性的。总之， 目前美国、欧洲及日本等发达国家在这方面的研究投入巨大，主要的研究成果也 第一章绪论 5 集中于这些国家的研究机构和大学。在国内，数据挖掘研究的起步只是最近几年 的事，主要的研究机构有：中科院、清华大学、西安交大、上海交大及国防科大 等少数几所院校和研究机构，在国内外权威刊物上发表的有关文章也寥寥无几。 尽管如此，由于数据挖掘技术的广泛应用前景，和其具有的强大功能，促使我们 必须迅速展开对其深入的研究。下面我们将要归纳一下其在应用和研究上的分类 情况，以便对其有一个概括性的了解。 数据挖掘的应用分类 尽管关联规则挖掘始源于商业上对市场购物篮进行分析的问题( m a r k e tb a s k e t a n a l y s i s ) 1 3 】，但是它的应用却不止于此，不过要列举出各种实际应用的具体案例也 不是件容易的事。其主要原因是：目前的用户都是第一批使用数据挖掘技术的 用户，且该技术正处于发展阶段，这些顾客出于保密和竞争的需要，并不愿意公 开其目前正在使用的技术，目的是依靠这些新技术增加在领域里的竞争力，这种 情形与人工智能领域在最初的发展是类似的。概括起来关联规则的应用领域也就 是数据挖掘的应用领域包括：商业与金融、人口普查数据分析踟、工程技术数据 分析、医疗【2 0 】【2 3 1 、财政【2 4 1 、宏观决策支持、电子商务、网站设计1 2 2 10 8 1 、通信和 互联网等1 1 7 ”】1 2 1 】 1 0 引。而且作为数据挖掘中的一个基本任务，关联规则挖掘已经 用于其他的数据挖掘任务中，例如数据建模、分类及决策支持f 驯等。如下是其几 个典型的应用领域， 市场菜篮分析 理解用户的购买习惯和喜好对于零售商做出相应的销售决策是十分重要的， 这些决策包括销售哪些商品、如何设计商品的式样、如何设计目录及怎样陈列商 品以达到促销的目的等，关联规则挖掘可以向用户提供上述信息。一个零售环境 中的典型应用便是市场菜篮分析或称购物蓝分析( s h o p p i n gb a s k e ta n a l y s i s ) 。由于 条码技术的广泛应用，客户的购买信息可以完全自动化地以电子数据的形式记录 在客户的数据库中，通过分析数据项目间的关系( 这里的项目指的是顾客所购买 的商品) ，可以利用所发现的关联规则指导商家的销售行为或广告行为等。例如后 项中包含“t v ”的规则将帮助用户决定怎样做才能促进电视机的销售；另外的一 个例子是，b 商品经常和a 商品一起被用户所购买，即存在规则a b ，由于b 的价格远远小于a ，因此为了促销a ，可以将b 作为与a 起销售的免费商品， 进行捆绑销售。 交叉销售( c r o s s i n gs a l e ) 在目前激烈的商业竞争中，留住现有的顾客，充分利用这些现有的顾客资源 甚至比吸引更多的新顾客更为重要。许多公司提供了不止项的服务或产品，公 司可以通过对现有的客户数据进行分析而达到促销的目的，如：向这些客户推销 他们目前尚没有购买的商品( 或服务) 被认为是一种快速获取收益的好方法。交 6博士学位论文：关联规则挖掘算法研究 叉销售就是用于描述这类问题