（计算机应用技术专业论文）基于兴趣度的关联规则算法研究.pdf

论文题目：基于兴趣度的关联规则算法研究 专业：计算机应用技术 硕士生：阎婷 指导教师：杨君锐 摘要 。确固鸯 ( 签名) 扬丕。纥 本文介绍了兴趣度的相关理论知识和经典算法，并对兴趣度的概念和典型度量方法 给出了说明。在此基础上对前人的兴趣度算法和理论进行研究，分析它们的不足，提出 了两个有关兴趣度的算法： ( 1 ) 提出了基于坐标的距离关联规则兴趣度挖掘方法。该算法是利用数学中坐标平面 知识得出的一种新兴趣度的度量方法，本方法的思想是考虑到对角线是关联规则在坐标 平面中的极限位置，用其它的关联规则在坐标中的位置和极限位置进行比较，距离极限 位置越近的，认为兴趣度越高；反之，兴趣度越小。 算法的提出主要是针对传统关联规则度量方法的缺点提出的一种新关联规则兴趣 度度量方法，它是在挖掘出强关联规则的前提下进行度量的一种方法，它只有一个阈值 条件，并且兴趣度有一定的范围限制，所以对支持度、置信度的缺点有很好的改正，正 确性也通过数据测试得到了证明；同时，本方法在对关联规则进行度量时，没有将两个 方向的关联规则等同看待，在这方面是对p s 公式缺点有很好的改正。 ( 2 ) 提出了多事务兴趣度的度量方法。该算法仍采用传统知识中常用的概率论知识衡 量兴趣度大小，它是利用力学平衡原理得到的一种兴趣度度量方法，在平衡点时，关联 规则之间的关联度最小，即兴趣度最小。结果大于零，就认为规则是令用户感兴趣的， 否则，剔除掉此规则。 此算法主要是针对p s 公式只能对二维关联规则进行度量的缺点提出的，它也是一 种在挖掘出强关联规则前提下进行度量的方法，但它同时也能够自己进行挖掘工作并且 给出度量结果，因为，在本算法中引入了逆向集，可以解决有些经典算法不能挖掘负项 关联规则的缺点。在算法描述中给出p s 公式只是多事务兴趣度度量算法特例的证明， 所以，多事务兴趣度度量方法是p s 公式的扩展形式，应用更为广泛。 关键词：数据挖掘；关联规则；强关联规则；兴趣度；逆向集；诱导力 研究类型：理论研究 s u b j e c t ：r e s e a r c hb a s e do ni n t e r e s ta l g o r i t h m so f a s s o c i a t i o nr u l e s s p e c i a l t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e：y a n t i n g i n s t r u c t o r ：y a n gj u n r u i ( s i g n a t u r e )益塑互驾 ( s i g n a t u r e ) 堆“尘虹 a b s t r a c t t h i sa r t i c l eh a si n t r o d u c e dt h et h e o r yk n o w l e d g er e l a t e dt oi n t e r e s ta n dt h ec l a s s i c a l a l g o r i t h m , a n dh a se x p l a i n e dt h ec o n c e p tt oi n t e r e s ta n dt h em o d e l m e a s u r e dm e t h o d t h e r e s e a r c hh a sb e e nc o n d u c t e di nt h ef o u n d a t i o nt op r e d e c e s s o r si n t e r e s ta l g o r i t h ma n dm c t h e o r y , w h i c ha n a l y z e dt h e i ri n s u f f i c i 饥c ya n dp r o p o s e dt w or e l a t e di n t e r e s ta l g o r i t h m s ： ( 1 ) i n t e r e s te x c a v a t i o nm e t h o db a s e d0 1 1t h ec o o r d i n a t e sd i s t a n c ea s s o c i a t i o nr u l e t h i sa l g o r i t h mh a su s e do n en e wi n t e r e s tm e a s u r em e t h o dw h i c ho b t a i n e di n m a t h e m a t i c st h ec o o r d i n a t e sp l a n ek n o w l e d g e w h a tt h i sm e t h o dt h o u g h tt a k e si n t o c o n s i d e r a t i o ni st h a tt h eo p p o s i t ea n g l el i n eo f t h ea s s o c i a t i o nr u l ei sl i m i t i n gp o s i t i o ni nt h e c o o r d i n a t e s p l a n e , a n d a q l t i e so nt h e c o m p a r i s o nw i t h o t h e ra s s o c i a t i o nr u l e si nt h e c o o r d i n a t e sp o s i t i o na n dt h el i m i t i n gp o s i t i o n w h e ni ti sa w a yf x o mt h el i m i t i n gp o s i t i o n n e a r e r , t h e nw et h i n kt h ei n t e r e s tg o e sp a s th i g h e r ；o t h e r w i s e ，t h ei n t e r e s tg o e sp a s tm o r e s l i g h t l y t h ea l g o r i t h mp r o p o s e dan e wa s s o c i a t i o nr u l ei n t e r e s tm e a s u r em e t h o dw h i c hm a i n l y a i m sa tt h es h o r t c o m i n go f t h et r a d i t i o n a lp r o p o s e da s s o c i a t i o nr u l em e a s u r cm e t h o d i ti so n e m e t h o dt oc a r r yo nt h em e a s u r e m e n tu n d e rt h ep r e m i s eo f e x c a v a t i n gi nt h es t r o n ga s s o c i a 虹o n r u l e , i to n l yh a sat h r e s h o l dv a l u ec o n d i t i o n , m o r c o v 盯a l s oh a st h ec e r t a i ns c o p el i m i t t h e r e f o r e ，i th a st h ev e r yg o o dc o r r e c t i o nt ot h es h o r t c o m i n go f t h ed e g r e eo f t h es u p p o r ta n d t h ec o n f i d e n c e t h ea c c u r a c ya l s oo b t a i n e dt h ep r o o ft h r o u g ht h ed a t at e s t ；a tt h es a m et i m e , t h i sm e t h o dh a sn o tt a k e nt w od i r e c t i o n sa s s o c i a t i o nr u l e se q u a t e dr e g a r d sw h e nc a r r i e d0 1 1t h e m e a s u r et ot h ea s s o c i a t i o nr o l e i nt h i s 铀p c c t ，i th a sav e r yg o o dc o r r e c t i o nt ot h ep sf o r m u l a s h o r t c o m i n g ( 2 ) t h em u l t i b u s i n e 鲻i n t e r e s tm e a s u r em e t h o d t h i sa l g o r i t h mh a ss t i l lu s e dt h ec o m m o nt h e o r yo fp r o b a b i l i t yk n o w l e d g ei nt h e t r a d i t i o n a lk n o w l e d g et ow e i g h ti n t e r e s t ；i ti so n ei n t e r e s tm e a s u r em e t h o dw h i c ho b t a i n e db y u s i n gt h em e c h a n i c a lb a l a n c ep r i n c i p l e w h e ni tc o m e st ob a l a n c ep o i n t , t h ec o n n e c t i o ni s s m a l l e s tb e t w e e na s s o c i a t i o nr u l e s ，n a m e l yi n t e r e s tw a ss m a l l e s t w h e nt h er e s u l ti sb i g g e r t h a n 删，w et 1 1 i 1 1 i 【t h er u l ei si n t e r e s t i n gt ot h eu s e r ；o t h e r w i s e , f c j e c tt h i sr u l e t op r o p o s et h i sa l g o r i t h mm a i n l ya i m sa tt h es h o r t c o m i n go ft h ep sf o r m u l aw h i c hi s o n l ya b l et oc a r r yo nt h em e a s u r et ot h et w o - d i m e n s i o n a la s s o c i a t i o nr u l e i ta l s oi so n ek i n d m e t h o dt oc a r f yo nt h em e f l s u l 七u n d e rt h ep r e m i s eo f e x c a v a t i n gi i lt h es t r o n ga s s o c i a t i o nr u l e ， b u ta tt h es a m et i m ei ta l s oc a l lc a r r yo nt h ee x c a v a t i o nw o r ka n dp r o d u c et h em e a s t l r er e s u l t o ni t so w n b e c a u s et h en e g a t i v ec o l l e c t i o nh a sb e e ni n t r o d u c e di nt h i sa l g o r i t h m , i tm a y o v e r c o m es u c hs h o r t c o m i n g st h a ts o m ec l a s s i c a la l g o r i t h m sc a n n o tb ea b l et oe x c a v a t et h e n e g a t i v ei t e m sa s s o c i a t i o nr u l e t h ep sf o r m u l ap r o p o s e di nt h ea l g o r i t h md e s c r i p t i o ni so n l y a ne x c e p t i o n a lc a s ep r o o ft ot h em u l t i - b u s i n e s si n t e r e s tm e a s u r ea l g o r i t h m , t h e r e f o r e , t h e m u l t i b u s i n e s si n t e r e s tm e a s u r em e t h o di st h ep sf o r m u l ae x p a n s i o nf o r mw h o s ea p p l i c a t i o n i sm o r ew i d e s p r e a d 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 s t r o n ga s s o c i a t i o nr u l e i n t e r e s t n e g a t i v ec o l l e c t i o n i n d u c t i o ns t r e n g t h 西妻拜技夫擎 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料与我一同工作的同志对本研究所 傲的任何贡献均已在论文中傲了明确的说明并表示了谢意 学位论文作者签名：f 劐彩午日期：办坶7i z s 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学 保密论文待解密后适用本声明 学位论文作者签名；阔婚 指导教师签名：饧磊铭 。 哕年歹月必日 t 绪论 l 绪论 数据挖掘在1 9 8 9 年8 月美国底特律市召开的第十一届国际联合人工智能学术会议 上正式形成。从1 9 9 5 年开始，每年举行一次知识发现( k n o w l e d g ed i s c o v e r y i n d a t a b a s e ，k d d ) 国际学术会议，把对数据挖掘和知识发现的研究推入高潮。数据挖掘还被 译为数据采掘、数据开采和数据发掘等，但数据挖掘还未有一致的定义f l 】。 数据挖掘的主要目的是从大量的数据源中采用和发展有关的理论、方法和工具来提 取有用的和使人感兴趣的知识和模式。数据挖掘是从实际的海量数据源中发现知识。因 此数据的完整性、一致性和正确性难以保证，而数据挖掘算法的效率、有效性和扩充性 非常关键1 2 1 。 尽管任务相关的数据和要挖掘的知识类型的说明可以大幅度减少产生规则的数量， 数据挖掘过程仍然可能产生大量模式。通常，这些模式中只有一小部分是特定用户感兴 趣的。这样，用户需要进一步限制挖掘过程产生的不感兴趣的模式数量。而这一要求可 以通过设定兴趣度度量来实现i l j 。 1 1 数据挖掘的国内外研究动态及发展趋势 1 1 1 数据挖掘的产生 随着人们认识和管理水平的提高，对客观世界的描述越来越全面，存储的数据量越 来越大。然而，对数据库中数据的开发应用主要是检索查询，效率很低，此外，相当数 量的数据具有很强的时效性，数据的价值随着时间的推移而迅速降低。简单的数据查询 或统计虽然可以满足某些低层次的需要，但人们更为需要的是从大量数据资源中挖掘出 对各类决策有指导意义的一般知识，这些知识是对大量数据的高度概括和抽象。 大量的数据未能充分利用这一现象常常被描述为“数据丰富，信息贫乏”。快速增长 的海量数据收集存放在若干大型数据库中，如果没有强有力的工具来帮助，其结果是重 要的决策不是基于数据库中丰富的信息，而是基于决策者的直觉。为此决策者需要从海 量数据库中提取有价值知识的工具，数据挖掘技术正是为满足上述要求而产生的。 数据挖掘( d a t e m i n i n g ) - - 词是在1 9 8 9 年8 月于美国底特律市召开的第十一界国际联 合人工智能学术会议上正式形成的，常常与k d d 混用。1 9 9 5 年开始，每年主办一次 k d d 国际学术会议，将k d d 和d md a t em i n i n g 方面的研究推向了高潮，从此，“数据 挖掘”词开始流行。在中文文献中，d m 有时还被翻译为“数据采掘”、“数据开采”、“数 据挖掘，等 3 1 1 4 1 1 5 1 。 西安科技大学硕士学位论文 1 1 2 国内数据挖掘理论研究现状 近年来，国内的许多科研单位和高等院校竟相开展数据挖掘的基础理论及其应用研 究，取得了较丰硕的研究成果。我国数据挖掘的研究已经初具规模。数据挖掘的理论研究 可分为宏观研究和微观研究两方面，其中宏观研究主要是从总体上进行把握，如数据挖掘 的必要性、内涵和理论综述等；微观研究主要包括：数据挖掘的任务、方法、技术、语言 和系统研究等。 从宏观研究方面数据挖掘的含义可以理解为 6 1 ： ( 1 ) 公认的是w j f r a w l e y 等给出的定义：数据挖掘，就是从大型数据库的数据中提取 人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在有用的信息，提取的知识可表 示为概念( c o n c e p t s ) 、规贝l j ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。此定义把 数据挖掘的对象仅定义为数据库。 ( 2 ) 有人认为，广义地讲，数据挖掘是在一些事实或观察的集合中寻找模式的决策支 持过程。也就是说，数据挖掘的对象不仅是数据库，也可以是文件系统，或其它任何数据集 合。 数据挖掘与数据库知识发现( k d d ) 的区别和联系：长期以来，数据挖掘和数据库知识 发现k d d 两个术语的范畴和使用界限一直不很清晰，直到k d d 9 6 国际会议 上，f a y y a d , p i a t e t s k ys h a p i r o 和s m y t h 就这两个术语的关系作了如下阐述：k d d 是指从数 据库中发现知识的全部过程。d a t e m i n i n g 则是全部过程中的一个特定步骤。 从微观研究方面数据挖掘的功能主要包括以下几类1 7 ： ( 1 ) 关联分析。关联分析指若两个或多个数据项的取值重复出现且概率很高时，它就 存在着某种关联，可以建立起这些数据项的关联规则。 ( 2 ) 分类。分类是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的 内涵描述，一般用规则或决策树模式表示。在数据挖掘中，分类算法的研究成果较多，常用 的数据分类算法有c a r t 、c 4 5 、i d 3 、s l i q 、k n n 、g ak n n 等。 ( 3 ) 聚类。数据聚类是将物理的或抽象的对象分成几个群体，具有群内相似群间差异 的特点。数据聚类常见的算法有p a m 、c l a r a 、c l a r a n s 、b i r c h 等。 ( 4 ) 偏差检测( 异常分析) 。数据库中的数据常有一些异常记录，从数据库中检测出这 些偏差很有意义。偏差检测的基本方法是寻找观测结果与参照之间的差别。 ( 5 ) 预测( 趋势分析) 。预测是利用历史数据找出变化规律：即建立模型，并用此模型来 预测未来数据的种类特征等。 ( 6 ) 最近邻技术。这种技术通过k 个最与之相近的历史记录的组合来辨别新的记录， 有时也称这种技术为艮一最近邻方法。 ( 7 ) 特征规则分析。从与学习任务相关的组数据中提取出关于这些数据的特征式， 2 l 绪论 用以表达该数据集的总体特征。 通过统计分析，我们发现，数据挖掘的方法技术是基础理论工作的微观研究的重点之 一，已经成熟和正在发展的方法较多，但数据挖掘技术并非多种技术的简单组合，而是一个 不可分割的整体，需要各种技术的综合支持，才能挖掘出令用户满意的结果，具体来说，数 据挖掘方法技术【s 】【9 1 n o l 1 1 l 有以下几种； ( 1 ) 统计学方法。统计学方法通过回归分析、时间序列、判别分析、因子分析和聚 类分析等统计分析方法，可以从抽样分析中提取未知的数学模型。数据挖掘主要是对高级 多元统计方法应用的拓展和深化。统计学方法是数据挖掘研究的重要途径之一。 ( 2 ) 关联规则挖掘。挖掘关联规则就是发现存在于大数据集中的关联性或相关性。 用于产生关联规则的方法有a 两嘶方法等。肖利、王能斌等提出了挖掘转移规则，用以 弥补了关联规则的不足，使得在特定的情况下，具有一定的普遍性和实用价值，可以为决策 者提供一个新的预测模型。糜元根认为，云模型可以用于采掘关联规则。云模型还是一种 新模型，其适用范围较窄，有待进一步的深入研究。 ( 3 ) 决策树方法。用树枝状展现训练集中资料受各变量的影响情形之预测模型，根据 对目标变量产生效用的不同而建构分类的规则，在问题维数高的领域可以得到很好的分 类结果。常用的方法有c a r t ( c l a s s i f i c a t i o n a n d r e g r e s s i o n t r e c s ) 及c h a i d ( c h i s q u a r e a u t o m a t i c i n t e r a c t i o n d e t e c t o r ) 。 ( 4 ) 神经网络方法。模拟人脑神经元方法，以m p 模型和h e b b 学习规则为基础，建立 了三大类神经网络模型：前馈式、反馈式、自组织网络，可以完成分类、聚类、特征挖掘 等多种数据挖掘任务。 ( 5 ) 多层次数据汇总归纳。将一个数据集合归纳成更高概念层次信息的数据挖掘技 术被称为数据汇总。概念汇总是将数据库中的相关数据由低概念层抽象到高概念层，主要 有数据立方体和面向对象的归纳两种方法。 ( 6 ) 覆盖正例排斥反例方法。利用覆盖所有正例、排斥所有反例的思想来寻找规则， 比较典型的方法有m i e h a l s k i 等人的a q l 5 方法、洪家荣改进的q 1 5 方法和a e 5 方法。 ( 7 ) 可视化技术。可视化技术采用直观的图形方式将信息模式、数据的关联趋势呈 现给用户，以便用户交互地分析数据关系。 ( 8 ) 粗集方法。粗集作为一种数据分析的方法首先由p a w l a k 提出。它能从不精确的、 模糊的、不确定的数据中发现知识。粗集理论在知识获取和数据挖掘中得到了广泛的应 用，它为数据挖掘提供了理论基础。杨辉，王烷尘提出了一种用于数据挖掘的粗集产生多 重知识库的新方法，改善了分类的精确性，提高了学习过程的有效性。 ( 9 ) 遗传算法。遗传算法是一种仿生全局优化方法。它模拟生命进化机制，将较劣的 初始解通过一组遗传因子，在求解空间按一定的随机规则迭代搜索，直到求得问题的最优 解，但其算法较复杂，还有收敛于局部极小的过早收敛等难题未得到彻底解决。 3 西安科技大学硕士学位论文 ( 1 证据理论。证据理论作为一种不确定推理方法，在数据挖掘中的应用不多见。 a n a n d s 等提出基于证据理论( e v i d e n c e t h e o r y ) 的数据挖掘一般框架e d m ，和其它方法结 合使用，效果更佳。 复杂结构数据特点是信息而非数据( 数字和字符) ，在数据库中以非结构化( 文本，图像 和视频文件) 形式存储。复杂数据挖掘是当前研究的重点和难点，有些文献中把复杂结构 数据挖掘称为下一代数据挖掘或信息挖掘。当前研究包括空间数据、多媒体数据、时序 数据、文本数据和w e b 数据挖掘。复杂类型数据挖掘技术如下【1 2 1 1 3 1 1 1 4 】【1 5 】： ( 1 ) 空间数据挖掘。空间数据挖掘是指从空间数据库中提取用户感兴趣的空间模式 与特征、空间与非空间数据的普遍关系及其它隐含在空间数据库中的普遍的数据特征。 我国在空间数据处理方面的综合能力居世界前列，与此相适应，利用现有的成熟的数据挖 掘技术研制实用的空间数据挖掘系统更有价值。 ( 2 ) 多媒体数据挖掘。以图像数据挖掘为例，包括相似性搜索、分类和预测分析以及 关联挖掘。音频和视频的挖掘可以跟数据挖掘的可视化相结合，用音频数据来代替可视化 挖掘是一个新颖的选择。 ( 3 ) 时序数据和序列数据的挖掘。包括：趋势分析，时序分析中的相似搜索，序列模式挖 掘。周期模式挖掘。 ( 4 ) 文本数据库挖掘。现实世界中可获取的大部分信息都是存储在文本数据库中的， 文档数据的存储格式是呈半结构化。朱锡钧，陆汝占认为目前对半结构化数据进行数据挖 掘采用的途径是：先将u s d 准结构化，再转换成结构化数据，套用现有数据挖掘方法进行 数据挖掘。另外，可以利用半结构化数据自己独特的数据模型、查询语言和存储管理工具 来实现挖掘。国内的研究者也对半结构化数据模型进行了许多研究。 ( 5 ) w e b 数据挖掘。目前w e b 挖掘研究的主要方向包括：w e b 文本的自动分类、多层 次w e b 信息库的建立、w e b 日志挖掘。以及其它涉及信息安全、搜索的效率，查询结果 的质量、搜索工具的可伸缩性等方面的问题研究。陈莉，焦李成认为，目前各种信息检索 工具的研制是i n t e m e tw w w 信息检索与数据挖掘研究的重点，如何在海量的图形，图像 数据、复杂的时空数据中进行数据挖掘，把多分辨分析技术( 如子波、多子波) 、粗集、支 撑矢量机、神经网络、模糊技术、免疫进化等与各种数据库及其相关技术相集成，研究新 型数据库中的数据挖掘是未来的研究方向。晏创业，张玉峰提出应用x m l 语言和关联规 则和分类算法等多种数据挖掘算法可以实现网络数据挖掘对智能检索的支持，包括对用 户知识和网络知识的挖掘。 1 1 3 国外研究现状 世界上对数据挖掘的正式研究始于1 9 8 9 年8 月举行的第一届k d d 国际学术会议， 数据库中的知识发现k d d 在该次会议上被提出。到目前为止，k d d 国际研讨会的研究 4 1 绪论 重点逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间 的相互渗透。与国内相比，国外对数据挖掘的研究较早，已形成整体力量。 1 2 数据挖掘的特点 数据挖掘的主要目的是从大量的数据源中采用和发展有关的理论、方法和工具来提 取有用的和使人感兴趣的知识和模式。数据挖掘是从实际的海量数据源中发现知识。因 此数据的完整性、一致性和正确性难以保证，而数据挖掘算法的效率、有效性和扩充性 非常关键。数据挖掘与传统的数据库查询区别表现在：前者是主动的、不生成严格的结 果集和不同层次的挖掘，而后者则是被动的、只对字段进行严格的查询1 2 】。 归纳起来，数据挖掘有如下特点f 3 】： ( 1 ) 处理的数据规模十分庞大。 ( 2 ) 由于用户不能形成精确的查询要求，因此需要靠数据挖掘技术来寻找其可能感 兴趣的东西。 ( 3 ) 数据挖掘对数据的迅速变化作出快速响应，以提供决策支持信息。 ( 4 ) 数据挖掘既要发现潜在规则，还要管理和维护规则，随着新数据的不断加入， 规则需要随着新数据更新。 ( 5 ) 数据挖掘中规则的发现基于统计规律，发现的规则不必适合于所有数据，而且 当达到某一阈值时，便认为有此规则。 数据挖掘的目标是要从数据库发现隐藏在大量数据中的未知知识，这种知识发现实 际又是人工智能所面临的难题之一。它作为一项新兴的高新技术，理论上或技术上面临 着许多的难点和挑战，但这项技术有着相当大的发展前景，是国际前沿研究开发的新领 域。 1 3 数据挖掘研究的发展趋势 数据挖掘是一个新兴的研究领域，许多问题还有待于研究，目前的研究方向包括下 列几个方面1 1 6 】【1 那8 1 9 】： ( 1 ) 算法效率和可伸缩性。数据挖掘通常是直接面向海量数据库，因此，数据挖掘 系统必须能有效地处理海量数据，其算法必须是高效率的、可伸缩的。 ( 2 ) 处理不同类型的数据和数据源。目前数据挖掘系统处理的数据库大多是关系数 据库。随着数据库应用范围的日益扩大和规模、功能的日益完掣悯。数据库中将包含大 量复杂的数据类型，甚至出现新的数据库模型，因此，保证数据挖掘系统能有效地处理 此类数据库中的数据是至关重要的。 ( 3 ) 数据挖掘系统的交互性。数据挖掘中操作者的适当参与能加速数据挖掘过程。 一方面，交互界面为用户表达要求和策略提供方便：另一方面，交互界面又把生成的结 5 西安科技大学硕士学位论文 果传递给用户，由于生成的结果可以多种多样，因此，准确而直观地描述挖掘结果和友 好而高效的用户界面一直是研究的重要课题。 ( 4 ) w e b 挖掘。由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来越重要的 角色，因此，w e b 挖掘将成为数据挖掘中一个重要和繁荣的子领域。 ( 5 ) 数据挖掘中的隐私保护与信息安全。数据挖掘能从不同的角度，不同的抽象层 上看待数据，这将潜在地影响数据的私有性和安全性。随着计算机网络的日益普及，研 究数据挖掘可能导致的非法数据入侵是实际应用中亟待解决的问题之一。 ( 6 ) 探索新的应用领域。早期的数据挖掘主要集中在帮助企业提高竞争能力。随着 数据挖掘的日益普及，它的应用领域也在不断扩大，由于通用数据挖掘系统在处理特定 应用问题时有其局限性，因此，目前的一种趋势是开发针对特定应用的数据挖掘系统。 数据挖掘语言的标准化。标准的数据挖掘语言或有关方面的标准化工作将有助于数 据挖掘系统的研究和开发，有利于用户学习和使用数据挖掘系统。 ( 7 ) 可视化数据挖掘。它是从大量数据中发现知识的有效途经。系统研究和开发可 视化数据挖掘技术有助于推进数据挖掘。 1 4 论文的工作和创新点 1 4 1 论文的工作 通过以上的描述，我们对数据挖掘的特点和发展趋势有了大体上的了解，并且对数 据挖掘中的兴趣度关联算法的一些定义以及它提出的背景都进行了一定程度的介绍，由 于数据挖掘技术包含的内容很多，而且兴趣度也是现在比较前沿的研究方向，所以涉及 到的知识领域也很广，所以在这里不能一一详细介绍。本论文中对兴趣度的基础知识一 关联规则的相关问题和经典算法进行阐述，特别是对兴趣度的相关知识进行深入地介 绍，在传统的兴趣度度量方法基础上提出了新的有关关联规则兴趣度的算法。本文的主 要工作有： ( 1 ) 关联规则是兴趣度的理论基础，所以首先对关联规则的基本概念以及挖掘频繁 项集的经典a p r i o r i 算法和f p 树算法给出了详细说明，并对这两个经典算法进行了分析 和总结。通过时间复杂度和其它的一些性能指标对它们的挖掘性能进行了分析和比较， 指出了现有经典算法在进行频繁项目集的挖掘方面存在的不足。 ( 2 ) 在分析传统度量关联规则相关性方法缺陷的基础上，提出了兴趣度的概念。关 联规则的算法是从大量的数据中发现数据间的关联模式，为了发现用户感兴趣而且有用 的关联模式，最早采用基于支持度和信任度的度量模式度量关联规则相关性，然而，这 一模型有它的局限性，一些学者也引入了新的度量方法，但仍存在相应缺点。本文对兴 趣度的现有衡量标准和一些定义及算法进行的介绍，尤其对兴趣度的一些传统算法和它 6 1 绪论 们的改进进行了较深入的探讨，并给出几种典型兴趣度模型的介绍。 ( 3 ) 在分析已有兴趣度算法的基础上提出了两种新的兴趣度度量模型。一种是用来 检测频繁项集关联程度的算法，它是在目前现有的关联规则数据挖掘算法的基础上对挖 掘出来的频繁项集给出的度量方法，是一种新的基于坐标的兴趣度度量方法；另一种是 对p s 模型的改进，它不仅可以进行自挖掘，也可以对挖掘出来的关联规则进行度量。 1 4 2 论文的创新点 在整个论文的工作中，通过对前人研究成果的分析和总结，论文有以下两个创新点： ( 1 ) 提出基于坐标的距离关联规则兴趣度挖掘方法，并分析了该方法的性质和特征， 进而给出了详细地证明和测试，这是本文的研究重点之一。在这一部分，针对支持度和 置信度框架的缺点，引入了新的兴趣度度量方法，并用经典的a p r i o r i 和f p 树关联规则 挖掘算法为基础描述了新兴趣度度量算法的使用过程。这个兴趣度度量算法是从另一个 角度考虑得出的一种基于距离和坐标的新型关联算法。传统的兴趣度度量算法都是基于 置信度和支持度的算法，后面一些算法的改进也是在概率的基础上进行的，它的创新点 在于：这个兴趣度算法利用的是各个关联规则在坐标中的位置与对角线( 极限位置) 的距 离关系来衡量的，其中用到了高数的知识和平面图形甚至多维图形的相关知识。本算法 通过对性能的测试和对兴趣度大小的判定说明了算法的正确可行性。 ( 2 ) 提出多事务兴趣度的度量方法，并分析了该方法的性质和特征，进而给出了详 细地证明和测试，这是本文的另一个研究重点。在这一部分，针对目前已有的关于兴趣 度关联规则的度量算法p s 公式的研究成果进行了分析，指出其中存在的不足；在前人 的基础上提出了一种新的兴趣度关联规则度量算法：多事务兴趣度的度量方法。这种兴 趣度算法是对p s 公式中存在的缺陷进行修正，使得p s 公式变得范围更广、适应性更强。 1 4 3 论文的组织 在接下来的几章里，论文安排如下： 第二章，在这一章主要是对兴趣度的相关理论基础进行详细介绍。首先对关联规则 数据挖掘的概念进行了阐述，也对关联规则数据挖掘的概念进行了详细介绍，并对关联 规则的形式和不同分类标准给出了描述；其次对关联规则的频繁项集挖掘算法中的两个 经典算法a p r i o d 算法和f p 树算法分别给出了描述和分析，并对两者有什么样的优缺点 进行了比较。 第三章，在这一章主要是对兴趣度模型进行详细介绍。首先对兴趣度的引入给出了 说明，并且对兴趣度的基本概念和衡量标准给出了详细叙述；其次对传统兴趣度度量方 法给出说明，并指出存在的缺点，以及针对这些缺点提出的典型算法；最后给出了兴趣 度的评价标准和典型度量方法。 7 西安科技大学硕士学位论文 第四章，在这一章主要是对提出的新算法给出说明。首先对基于坐标的距离关联规 则兴趣度挖掘方法给出了算法描述和说明；其次，用具体的例子给出了详细的算法说明， 并且和传统的兴趣度度量算法进行比较，验证了它的正确性和它比传统算法的优势。 第五章，在这一章主要是对提出的另一个新算法给出说明。首先对多事务兴趣度度 量方法的引入给出了说明，并对算法中的概念给出了介绍；其次，对算法给出了描述， 并对所用到的公式给出了证明和推导；最后对算法实现给出了说明。 第六章，对全文的工作进行了总结，并指出以后进一步的工作。 s 2 兴趣度理论基础 2 兴趣度理论基础 兴趣度是对关联规则相关性大小度量的标准，要对兴趣度进行研究，首先要了解它 的相关理论基础。关联规则挖掘是发现大量数据中项集之间有趣的关联或相关联系。随 着大量数据不停的收集和存储，许多业界人士对于从它们的数据库中挖掘关联规则越来 越感兴趣。从大量事务记录中发现有趣的关联关系，可以帮助许多商家制定决策，通过 了解哪些商品频繁的被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。 而关联规则是否有价值，一般是用支持度和置信度的阙值进行度量。 关联规则是数据挖掘中发展最为成熟，应用最广的知识模型，它也是兴趣度模型的 基础知识，所以在这一章给出详细的说明。 2 1 关联规则的基本定义和性质 2 。1 1 关联规则基本定义 定义2 1 关联规则 设x l 】，且x ，y ，x n y = 妒成立，关联规则是形如x j y 的蕴涵式。 定义2 2 关联规则的支持度s u p p o r t 设关联规则x j y 。 有x = 五，x 2 ，也) s ，】r = 锄，儿，嘶，t 且 x 苁y 幺工n y = 办则x y 的支持度为公式2 h s u p p o r t ( x j y ) = p ( x u 驴鬻) 支持度s u p p 反映了x 和y 中的项目有多大可能同时出现。 定义2 3 关联规则的置信度c o n f i d e n c e 设关联规则x jy 满足z 】，i 且x 办y ，z n l ，= ，则x jr ，的置信度 为公式2 2 ： c o n l i d c n c c ( x j y ) = p ( y x ) = 鬻x 1 0 0 。鬻( 2 2 ) 置信度和支持度反映了关联规则的正确程度和支持率。 定义2 4 强关联规则 设关联规则x y ，满足x ，y c _ 1 且彳蟊y ，x n y = 声，对于给定的阈值 m i n s u p 和n l i 删如果s u p p ( x ；y ) n f i n s u p r c o n f ( x 等n 2 m i n c o n f 成立，阈值 n f m s u p 为最小支持度，n f m c o n f 为最小置信度，则x j y 为强关联规则；否则x j r 为 弱关联规则刚。 9 西安科技大学硕士学位论文 定义2 5 频繁项集 设u = u l ，u 2 , ，珊) 为项集，且u c _ l ，u ，对于给定的最小支持度m h ：l s u p ，如果项集u 的频度s u p p ( u ) - m i n s u p ，则称u 为频繁项集，简称频繁集；否则，u 为非频繁集，简 称非频繁集【2 0 】。 2 1 2 关联规则的性质 性质2 1 设u = ( 蜥，u 2 , ，蜥 为项集，且u i ，u ，对于给定的数据库事务集d 和 最小支持度m i n s u p ，如果项集u 为频繁集，则q 也是频繁集【2 ”。 性质2 2 设u = “1 , 1 1 2 ，u k 为项集，且u h ，u m ，对于给定的数据库事务集 d 和最小支持度m i n s u p , 如果项集u 为非频繁集，则h 也一定是非频繁集 2 l 】。 性质2 3 设关联规则彳y ，满足x ，y i r z ，l ，矿，x n y = 矿，对于给定 的最小支持度m i n s u p 和最小信任度n a n c o n f ；x j y 为强关联规则；如果j ，j ，那末 x j r 也为强关联规则【2 。 性质2 4 设关联规则x y ，满足，= j u 】，且x ，y 妒，x n y = ，对于给定的 最小支持度m i n s u p 和最小信任度m i n c o n f 的强关联规则；如果x 彳，满足 i = x 7 u y 且x 破y r 办x n p = 识那么z j y 也为满足给定条件的强关联规则【2 l 】。 2 2 关联规则的形式和分类 2 2 1 关联规则形式 ( 1 ) 关联规则的一般形式 关联规则的形式j jr ，其中x 成为规则的前项项集，y 成为后项项集。它说明 数据库中的某一条记录如果包含了x ，那末也倾向于包含y 或者说，如果数据库中的某 条记录使x 中的属性值为真，那末也倾向于使y 中的属性值为真。用规则2 1 和规则 2 2 ，对关联规则进行说明【1 1 1 2 ”。 c o n t a i n s ( t , “计算机，)c o n t a i n s ( t , “软件 ，) ( 2 1 ) 【s u p p o r t = 2 , c o n f i d e n c e = 5 0 在这里，t 是表示事务记录的变量。该规则表明，如果事务t 中包含“计算机”，则 它同时包含“软件”的可能性为5 0 * 6 ，并且所有事务中有2 包含了两者。 a g e ( t 2 5 - 4 5 ) a b u y s ( t , “计算机，)b u y s ( t , “打印机，) ( 2 2 ) 【s u p p o r t = 1 ，c o n f i d e n c e = 6 0 】 该规则说明，年龄在2 5 - 4 5 之间并且购买计算机的人，并购买打印机的可能性是 6 0 0 6 。关联规则挖掘就是从事务数据库中找出上述形式的规则。 1 0 2 兴趣度理论基础 ( 2 ) 关联规则的扩展形式 按照谓词的格式，可将关联规则石jy 的前项x 和后项y 写成条件的合取范式， 每个条件a i = t u r e f l a s e 为布尔表达式，此时的a i 为集合中的一个元素。如果把结果中 的条件表达式写成，则关联规则的扩展形式1 l 【2 1 1 为规则2 3 ： ( a 1 = t u r e f l a s e ) a ( a 2 = t u r e f l a s e ) a a ( a n = t u r e v a s