（计算机应用技术专业论文）关联规则基本技术研究.pdf

论文题目： 专业： 硕士生： 指导教师： 关联规则基本技术研究 计算机应用技术 郭运凯 杨君锐 摘要 ( 签名) 室垦塾 ( 签名) 生老趁 数据挖掘是指从大型数据库中发现潜在的、新颖的、有价值的、可用的及能被用户 理解的模式和信息的过程。关联规则挖掘是数据挖掘的一个重要研究领域，主要是发现 数据库中属性之间的关联关系。 本文在广泛查阅国内外文献的基础上，针对关联规则算法的若于问题进行了深入地 分析研究，论文的主要研究内容和成果如下： 首先，提出了基于排序f p t r e e ( s o r t e df p t r e e ，简称s f p t r e e ) 的最大频繁项目集 挖掘算法s f p m i n e r 。在s f p m i n e r 算法中，通过两次扫描数据库将其中每个事务所包 含的频繁项目压缩存储在s f p t r e e 中。在挖掘过程中，充分利用s f p t r e e 的特点，并 采用合并子树和预剪枝策略在s f p t r e e 上进行深度优先挖掘，而不需要扫描数据库， 减少了算法在挖掘过程中使用的存储空间和计算时间。实验结果表明，该算法有较好的 性能。 其次，提出了基于完全合并s f p t r e e 的最大频繁项目集更新挖掘算法u a m f i 。该 算法基于完全合并s f p t r e e ，直接在树上进行深度优先搜索，能够快速地进行最大频繁 项目集的更新挖掘。实验测试和结果分析，该算法可以高效的更新最大频繁项目集。 最后，针对多值属性关联规则挖掘问题，提出了基于高维聚类的多值属性关联规则 挖掘算法d b s m i n e r 。该算法借鉴a r c s 思想，先将高维数据集的各维进行划分，然后 将密度单元进行排序，并提出一种基于网格的高维聚类算法对划分后的数据进行聚类挖 掘。理论分析和试验结果表明，d b s m i n e r 算法具有较好的执行效率和精确度，能有效 的进行多值属性关联规则的挖掘。 关键词：数据挖掘；关联规则；最大频繁项目集；排序频繁模式树；高维聚类 研究类型：理论研究 s u b j e c t ：r e s e a r c ho nt h eb a s i ct e c h n o l o g yo fa 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：g n oy u n k a i i n s t r u c t o r ：y a n gj u n r u i a b s t r a c t ( s i g n a t u r e ) ( s i g n a t ur e ) 白伽孙如 d a t am i n i n gm e a n sap r o c e s so ff i n d i n gn o n t r i v i a l ，e x t r a c t i o no fi m p l i c i t ，p e r v i o u s u n k n o w na n dp o t e n t i a lu s e f u li n f o r m a t i o nf r o md a t ai nd a t a b a s e a s s o c i a t i o nr u l em i n i n ga s a ni m p o r t a n tf i e l do fd a t am i n i n gd i s c o v e r si 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 ga t t r i b u t e si nt h o s e d a t a b ys t u d y i n gt h el i t e r a t u r ed o m e s t i ca n da b r o a d ，w er e s e a r c hs o m eb a s i cp r o b l e m so f a 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 m s t h em a i nc o n t e x t sa r es h o w e da sf o l l o w s ： f i r s t l y , am a x i m a lf r e q u e n ti t e m s e tm i n i n ga l g o r i t h ms f p - m i n e r , w h i c hb a s e do ns o r t e d f p - t r e ew a sp r o p o s e d t h es f p m i n e rs c a n n e dd a t a b a s et w i c ea n dc o m p r e s ss t o r e dt h e f r e q u e n ti t e m s e ti ns f p - t r e e b yu s i n gd e p t h f i r s ts t r a t e g y , t h ea l g o r i t h mp r u n e dt h e s e a r c h i n gs p a c eb yp r e p r u n ea n dm e r g e n c es t r a t e g ya n dd i s c o v e r e da l lt h em a x i m a lf r e q u e n t i t e m s e te f f i c i e n t l ya n dd i d n tn e e dt os c a nt h ed a t a b a s e t h ee x p e r i m e n t a lr e s u l ti n d i c a t e dt h a t s f p - m i n e ri sa ne f f i c i e n ta l g o r i t h m s e c o n d l y , w ep r e s e n t e dan e wu p d a t i n ga l g o r i t h m ，u a m f i ，f o rm i n i n gm a x i m a lf r e q u e n t i t e m s e t sf r o mt r a n s a c t i o nd a t a b a s ew h e nm i n i m u ms u p p o r tw a sc h a n g e db yc u s t o m e r t h e a l g o r i t h ma d o p t e da n e wd a t as t r u c t u r ef m s f p t r e e ( f u l lm e r g e ds f p t r e e ) w h i c hs t o r e da l l t h ef r e q u e n ti t e m s e t si na n yg i v e nm i n i m u m s u p p o r ta n di td i r e c t l ym i n e da n du p d a t e dt h e m a x i m a lf r e q u e n ti t e m s e t si nf m s f p t r e e i tc a ne f f i c i e n t l ym i n em a x i m a lf r e q u e n ti t e m s e t s 谢t hc h a n g e dm i n i m u ms u p p o r t f r o mt h ee x p e r i m e n t a lr e s u l t w ec a nc o n c l u d et h a tt h e a l g o r i t h mi sh i g h l ye f f i c i e n tt ot h eu p d a t i n gm i n i n gp r o b l e m s f i n a l l y , w ep r e s e n t e dan e wa l g o r i t h m ，d b s m i n e r ( d e n s i t yb a s e ds u b s p a c em i n e r ) ，f o r m i n i n gq u a n t i t a t i v ea t t r i b u t e sa s s o c i a t i o nr u l e t h i sa l g o r i t h m ，w h i c hr e f e r e n c e dt h ea r c s ( a s s o c i a t i o nr u l ec l u s t e r i n gs y s t e m ) ，u s e dag d ds t r u c t u r et oq u a n t i z et h eo b j e c ts p a c ei n t oa f i n i t en u m b e ro fc e l l s ；i ts o r t e da l lt h ed e n s eg r i d sb yd e s c e n d i n go r d e ra n du s e da g r i db a s e d c l u s t e ra l g o r i t h mt oc l u s t e rt h ed a t aw i t ha 1 1a t t r i b u t e s a ti a s t i tc l u s t e r e dt h ea s s o c i a t i o nr u l e s t h e o r e t i c a l a n a l y s i sa n de x p e r i m e n t a lr e s u l t ss h o wt h a t ，d b s m i n e ra l g o r i t h mh a sg o o d p e r f o r m a n c ea n da c c u r a c y i tc a l le f f e c t i v e l ym i n ea s s o c i a t i o nr u l eo fq u a n t i t a t i v ea t t r i b u t e s 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 sm a x i m a lf r e q u e n ti t e m s e t u p d a t i n g m i n i n g s o r t e df r e q u e n tp a t t e r nt r e e h i g hd i m e n s i o nc l u s t e r t h e s i s：t h e o r e t i c a lr e s e a r c h 要料技夫学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究t 作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：前巨凯日期：7 o o i 口6 0 3 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题冉撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：享p 区彰儿 指导教师签名：1 岛哆番够 叫年月夕日 1 绪论 1 绪论 随着数据库技术和计算机网络的广泛应用，人们所拥有的数据量急剧扩大。一方面， 人们积累了海量的商业数据；另一方面，相关的分析方法越来越滞后，数据迅速增加与 分析方法滞后之间的矛盾越来越突出。导致人们面临“数据丰富，知识贫乏 的困境i l j 。 数据挖掘，又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 。其 目的是帮助决策者寻找数据间潜在的关联，发现被忽略的要素。它包含了一系列从大型 数据库或数据仓库中提取有潜在应用价值的信息或模式的技术，是人工智能、神经网络、 数据库、预测理论、机器学习和统计学等多种技术的综合产物。它不但可以帮助人们从 数据库特别是数据仓库的相关数据中提取出所感兴趣的知识、规律或更高层次的信息， 而且也可以帮助人们从不同程度上去分析它们，从而可以更有效地利用数据库或数据仓 库中的数据；另外它不仅可以用于描述过去数据的发展过程，而且还能进一步预测未来 的发展趋势。因此，数据挖掘正在成为一个新的、r 益受到重视的热点研究领域。目前 在国内外的许多高校和研究机构都在从事此领域的研究工作，并产生了大量的研究成 果。 1 1 数据挖掘概述 数据挖掘从诞生到现在有多种定义，其中得到公认的是【2 】： k n o w l e d g ed i s c o v e r yi nd a t a b a s e si st h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ，n o v e l ， p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a 1 1 1 数据挖掘技术的现状 k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上。 随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把专题讨论 会更名为国际会议，在加拿大蒙特利尔市召开了第1 届k d d 国际学术会议，以后每年 召开一次。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了1 3 次， 规模由原来的专题讨论会发展成为国际学术大会。其他内容的专题会议也把数据挖掘和 知识发现列为议题之一，成为当前计算机科学界的一大热点。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟 了k d d 专题或专刊。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊领先在1 9 9 3 年出版 了k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的最新成果。 在k d d 的研究中，当前研究较多的是关联分析，它是由r a k e s ha g r a w a l 等人在文 献【3 】中首先引入的。关联分析是指从给定的数据集中发现关联规贝, l j ( m i n i n ga s s o c i a t i o n 西安科技大学硕士学位论文 r u l e s ) ，这些规则反映了大量数据中项目集之间有趣的关联或相关联系。从2 0 世纪九十 年代初到现在，对关联规则挖掘算法的研究中学者们进行了大量的工作，先后提出了许 多挖掘算法，这些算法按照功能可划分为三大类：( 1 ) 发现频繁项目集的算法p 培j ，如 a p r i o r i 3 1 ，f p g r o w t h 4 1 ，p a r t i t i o n 5 】等；( 2 ) 发现最大频繁项目集的算法，m a x m i n e r 9 1 、 p i n c e r - s e a r c h 1o j 等；( 3 ) 增量式更新算法，如f u p l l 2 j ，i u a 乃j 等。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科 学基金首次支持对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展 知识发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所等。 其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京 大学也在开展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中国科 技大学、中科院数学研究所、吉林大学等单位开展了对关联规则挖掘算法的优化和改造。 1 1 2 数据挖掘的功能 总体来讲，根据数据挖掘发现的项目集类别，可以将其分两种：描述性数据挖掘和 预测性数据挖掘。描述性数据挖掘意在刻画数据的特性和特征。预测性数据挖掘任务在 当f j 数据上进行推断，以进行预测。另外，数据挖掘能够发现各种位于不同抽象层的项 目集。这些项目集由不同的视角为用户提供领域的知识，为用户聚焦有趣项目集的搜索 带来了方便。具体来讲，数据挖掘功能大略可以归纳为6 种：广义知识、关联分析、分 类知识、聚类分析、异常分析和预测分析，下面分别简述此6 种功能。 ( 1 ) 广义知识( g e n e r a l i z a t i o n ) 广义知识指类别特征的概括性描述知识。根据数据的微观特性发现其表征的、带有 普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数据的 概括、精炼和抽象。广义知识的发现方法和实现技术有很多，如数据立方体、面向属性 的归约等。数据立方体还有其他一些别名，如“多维数据库、“实现视图”、“o l a p ” 等。该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如计数、求和、 平均、最大值等，并将这些实现视图储存在多维数据库中。 ( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 1 3 , 4 , 5 1 反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性之间存在关 联，那么其中一项的属性值就可以依据其他属性值进行预测。最为著名的关联规则发现 方法是r a g r a w a l 提出的a p f i o f i 算法。关联规则的发现可分为两步。第一步是迭代识 别所有的频繁项目集，要求频繁项目集的支持率不低于用户设定的最低值；第二步是从 频繁项目集中构造可信度不低于用户设定的最低值的规则。识别或发现所有频繁项目集 是关联规则发现算法的核心，也是计算量最大的部分。 ( 3 ) 分类知识( c l a s s i f i c a t i o n ) 2 1 绪论 反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知识。最为典型 的分类方法是基于决策树的分类方法。它是从实例集中构造决策树，是一种有指导的学 习方法。该方法先根据训练子集( 又称为窗口) 形成决策树。如果该树不能对所有对象给 出正确的分类，那么选择一些例外加入到窗口中，重复该过程一直到形成f 确的决策集。 最终结果是一棵树，其叶结点是类名，中间结点是带有分枝的属性，该分枝对应该属性 的某一可能值。最为典型的决策树学习系统是i d 3 f 1 4 l ，它采用自项向下不回溯策略，能 保证找到一个简单的树。算法c 4 5 和c 5 0 t 1 6 1 都是i d 3 的扩展，它们将分类领域从类 别属性扩展到数值型属性。 数据分类还有统计、粗糙集( r o u g h s e t ) 等方法。线性回归和线性辨别分析是典型的 统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。最近也有人研究使 用神经网络方法在数据库中进行分类和规则提取。 ( 4 ) 聚类分析( c l u s t e r i n ga n a l y s i s ) t 1 7 , 1 8 , 1 9 】 在没有或不用样本所属类别信息的情况下，依据样本集数据的内在结构，在样本间 相似性度量的基础上对样本进行分类的方法。这是一种非监督学习方法( 见监督学习) 。 分类的基础是模式间的相似和不相似关系，这种关系常常用模式特征向量之间的距离来 度量。具体的模型在后面详细阐述。 ( 5 ) 异常分析( o u t l i e ra n a l y s i s ) 2 0 2 1 】 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括 很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的 偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意 义的差别。 数据中异类可以利用数理统计方法分析获得，即利用已知数据所获得的概率统计分 布模型，或利用相似度计算所获得的相似数据对象分布，分析确认异类数据。而偏离检 测就是从数据已有或期望值中找出某些关键测度显著的变化。 ( 6 ) 预测分析( p r e d i c t i o na n a l y s i s ) 2 2 , 2 3 】 预测是数据挖掘中用得最多的技术。在预测中，把历史数据应用到新的变量( 如销 售情况) ，然后分析该变量未来的情况。预测分析可以建立适当的策略来实现长期增长。 预测分析有多种方法，如时间序列回归技术和神经网络。很多技术不仅可以得出长期线 性趋势，还可以分析出的短期循环性波动。 1 1 3 数据挖掘过程 数据挖掘过程一般由确定挖掘对象、数据准备、模型建立、数据挖掘、结构分析表 述和挖掘应用这几个主要的阶段组成。数据挖掘可以描述为这几个阶段的反复过程，见 图1 1 。 3 西安科技大学硕士学位论文 ： ： ；y y y 图1 1 数据挖掘过程 ( 1 ) 数据准备 数据准备阶段又可以进一步分为4 个子步骤：数据集成、数据选择、数据预处理和 数据转换。 数据集成。数据集成是将多个文件或多数据库运行环境中的数据进行合并处 理，解决语义模糊性，处理数据中的遗漏和清洗数据等。 数据选择。数据选择是指为数据挖掘目标而搜索和选择有关的数据，这包括不 同格式数据的转换以及不同部门数据的统一和汇总。 数据预处理。数据预处理是对数据进行清理和充实等工作。数据库中重要的数 据是准确的，不重要的数据可能存在污染。预处理就是为了克服目前数据挖掘工具的局 限性。 数据转换。数据转换的一个重要工作是对数据进行编码。数据库中字段( 属性) 的不同取值转换成数码形式将有利于搜索。 ( 2 ) 数据挖掘 这个阶段进行实际的挖掘操作，即利用机器学习、统计分析等方法，从数据库中发 现有用的模式或知识( 这里，模式是浓缩数据的信息形式，如精炼数据库、表格、产生 式规则、决策树、神经网络的权值等) 。 选择数据挖掘方法。如统计分析、机器学习、模式识别方法和人工神经元方法 等。 选择数据挖掘算法。选择用来查找模式或符合数据模型的算法，确定合适的模 型和参数。另外，数据挖掘方法必须和目标相匹配。 数据挖掘。查找感兴趣的模式。模式一般表示为一种特殊的形式或一套表达方 式，如关联规则，分类规则或分类树，回归结构和聚类集等。 除了选择合适的挖掘算法以外，其余的一切工作都可自动完成。 ( 3 ) 数据挖掘、结果分析表述和挖掘应用 结果表达。尽量直观的表达挖掘结果，便于用户理解和使用，可使用可视化方 法表示为图表等形式。 结果评价。筛选和评价挖掘结果中的有用部分，查找可接受的结果。可定义兴 趣指标，考虑结果的正确度、新颖度、有用性和简单性，把信息从输出中过滤出来。利 4 1 绪论 用可视化方法帮助用户解决所提出知识的有效性或对基本的数据或现象做出结论。 知识巩固。把挖掘出的信息结合到执行系统中，了解这些信息的作用或证明这 些信息。用预选知道且可信的信息来检查和验证所挖掘出的信息，解决可能存在的矛盾。 当然，在有些情况下，也可以只是简单地记录所挖掘出的信息并把它报告给用户， 由用户进一步分析。 1 2 数据挖掘的发展趋势 数据挖掘任务和数据挖掘方法的多样性，给数据挖掘提出了许多挑战性的课题。数 据挖掘语言的设计、高效而有效的数据挖掘方法和系统的开发、交互和集成的数据挖掘 环境的建立和应用数据挖掘技术解决大型应用问题，都是目前数据挖掘研究人员、系统 和应用开发人员所面临的主要问题。下面是数据挖掘的发展趋势： ( 1 ) 并行和分布式挖掘 频繁项集挖掘在很多数据挖掘任务中起着重要作用如关联规则发现、分类、聚类等。 近年来，繁项集又广泛应用于文本挖掘领域，文本分类【2 4 1 、文本聚类【2 5 】等。随着互连网 和信息传播手段的飞速发展，越来越多的企业和机构积累了海量的文本数据。对于这些 海量的文本，常用的挖掘算法例如a p f i o f i 、f p g r o w t h 等都是基于内存的。当其应用于 海量文本数据时，传统的频繁项集挖掘算法遇到了新的挑战：( i ) 文本数据常常是高维和 稀疏的。文本数据库中常常会有上万的常用词，一般的频繁项集挖掘算法难以处理这样 的高维数据。( i i ) 文本数据库可能会非常大，对于上百g b 甚至超过t b 的文本数据，普 通的基于内存的频繁项集挖掘算法无法应用于这样的海量数据集。通常采用的方法是采 用并行【2 6 ，2 7 1 或者分布口8 1 的方法来处理此问题。 ( 2 ) 数据流挖掘 随着数据库技术的发展和信息化的进步，数据规模也越来越大。例如根据2 0 0 0 年 的统计，w a l m a r t 单日的销售记录就有2 0 ，0 0 0 ，0 0 0 个，g o o g l e 每天处理7 0 ，0 0 0 ，0 0 0 次 查询，a t & t 每天有多达2 7 5 ，0 0 0 ，0 0 0 个电话记录。这些数据非常庞大，尽管传统数据 库获得了巨大的成功，但是这个层次的数据比率对于数据的管理、分析和挖掘来说都带 来一些有价值的新问题和挑战。这种新类型的数据应用使人们逐渐认识到：数据的模型 不是建立在一种持续稳定的关系上而是建立在短暂的流数据【2 9 l ( s t r e a m i n gd a t a ) 上。对数 据流的研究分为两种：( i ) 流数据管理系统( d a t as t r e a mm a n a g e m e n ts y s t e m ，简称d s m s ) 研究。在会议p o d s 2 0 0 2 的一篇文献【3 0 j 中给出了一个有深度的完整的有关流数据系统的 讨论。比较有名的流数据管理系统包括：斯坦福大学的s t r e a m 项目、加州大学伯克 力分校的t e l e g r a p h 项目、美国电报电话公司的h a n c o c k 项目、施乐公司的t a p e s t r y 项 目、布朗大学和麻省理工学院合作的a u r o r a 项目等等，这些系统针对具体行业背景， 给出较全面的数据管理解决方案。( i i ) 基于流数据模型的数据挖掘技术研究。相关的技 5 西安科技大学硕士学位论文 术包括：抽样技术3 1 , 3 2 】、s k e t c h 技术3 3 1 、直方图技术和小波分析等。研究方向包括：关 联规则挖掘【3 4 , 3 5 1 、分类【3 6 】、预测【3 7 j 、聚类等。 ( 3 ) 图像挖掘 随着数字图像的广泛应用，挖掘非标准化和多媒体数据是数据挖掘的发展趋势之 一。图像挖掘为多媒体的数据挖掘提供了很好的方法和技术。图像挖掘( i m a g em i n i n g ) 是在图像数据库中抽取隐含的、先前未知的、潜在有用的知识，图像数据关系的非平凡 过程，是集中了计算机视觉、图像处理、图像检索、数据挖掘、机器学习、模式识别、 数据库和人工智能等技术的多学科交叉的研究领域【3 9 】。挖掘模型有功能驱动模型 ( f u n c t i o n d r i v e nm o d e l ) 1 4 0 1 和信息驱动模型( i n f o r m a t i o n d r i v e nm o d e l ) t 4 1 1 。挖掘技术有：相 似性搜索【4 2 】、图像关联规则挖掘【4 3 1 和图像聚类h 5 1 等。 ( 4 ) 可视化数据挖掘 4 5 , 4 6 可视化数据挖掘是从大量数据中发现知识的有效途径，系统研究和开发可视化数据 挖掘技术将有助于推进数据挖掘作为数据分析的基本工具。目前数据挖掘的可视化仅体 现在结果的简单描述，并没有达到真正意义上的可视化。数据可视化、挖掘过程可视化 和结果可视化，使挖掘过程变得更为生动、形象和具体，用户可以随时了解整个过程的 进展情况，减少了行为过程的盲目性。数据和结果的图形展示可以放大、缩小、平移、 旋转和变换角度，使分析人员和用户更加容易理解，这将大大推动数据挖掘工具在发现 知识和数据分析中的应用。因此，加强数据可视化和知识发现过程的可视化具有重要的 理论意义和应用价值。 ( 5 ) 数据挖掘中的隐私保护与信息安全【4 7 4 9 】 随着数据挖掘工具和电信与计算机网络的日益普及，数据挖掘要面对的一个重要问 题是隐私保护和信息安全。需要进一步开发有关方法，以便在适当的信息访问和数据挖 掘过程中确保隐私保护与信息安全。 1 3 论文的工作 由于数据挖掘技术包含的内容很多，涉及到的知识领域也很广，所以在这里不能一 一详细介绍。通过对前人研究成果的分析和总结，本论文主要就关联规则数据挖掘中的 最大频繁项目集挖掘、最大频繁项目集更新挖掘和多值属性关联规则挖掘这三方面进行 了较深入的探讨。 首先，本文对关联规则中挖掘频繁项目集的问题进行了分析和总结。然后，详细介 绍了两类挖掘频繁项目经典算法a p r i o r i 算法和f p g r o w t h 算法。最后，对关联规则挖掘 进行了展望。 其次，在分析频繁项目集挖掘问题的基础上，本文对最大频繁项目集的挖掘问题进 行了较深入的探讨。在这一部分，首先对目前已有的关于最大频繁项目集挖掘问题的研 6 1 绪论 究成果进行了分析，指出其存在的不足：然后在前人的基础上提出了一种高效的最大频 繁项目集挖掘算法s f p m i n e r 。最后通过将算法同业界公认的有代表性的最大频繁项目 集挖掘算法m a f i a 进行测试、比较和分析。结果表明，s f p m i n e r 具有较高的运行效率。 再次，本文对关联规则更新挖掘问题进行了较为全面的阐述和分析。在这一部分， 首先对频繁项目集以及最大频繁项目集的更新挖掘问题进行了介绍，并对已有的研究成 果进行了分析和总结；然后，在s f p m i n e r 算法的基础上，提出了基于完全排序f p t r e e 的解决最小支持度变化时最大频繁项目集更新问题的算法u a m f i 。通过将该算法和相 关算法进行对比测试和分析得出，u a m f i 能充分利用完全排序f p t r e e 储存的信息，在 最小支持度变化时快速地进行最大频繁项目集的更新挖掘，具有较好的性能。 最后，在对多值属性关联规则挖掘算法进行分析与研究的基础上，提出一种适合高 维数据的聚类算法c b s d ，并在此基础上提出了多值属性关联规则挖掘算法d b s m i n e r 。 通过详细的测试分析表明，该算法能较好的解决多值属性挖掘问题。 对于上面提到的第一个算法，我们已发表在第七届全球智能控制与自动化大会论文 集( 被e i 和i s t p 收录) 。对于后面两个算法，已发表在2 0 0 8i e e e 工程管理，服务管理 和知识管理国际会议w i c o m 2 0 0 8 国际会议论文集( 均被e i 和i s t p 收录) ，详情请参考 后面的附录。 1 4 论文的组织 论文其余部分组织如下： 第二章，首先对关联规则数据挖掘的概念进行了详细介绍；其次对两类经典的频繁 项目集挖掘算法a 砸o r i 和f p g r o w t h 进行了介绍。最后，对关联规则挖掘进行了展望。 第三章，首先对最大频繁项目集挖掘问题进行了详细介绍，并简要分析和总结了当 前在这方面的研究成果；然后在前人的基础上提出了一种基于排序f p t r e e 结构的最大 频繁项目集挖掘算法s f p m i n e r ；最后对s f p m i n e r 进行了测试、比较和分析。 第四章，首先对关联规则更新挖掘问题进行了分析和总结；然后针对最小支持度变 化时最大频繁项目集的更新挖掘问题提出了算法u a m f i ，并对其性能进行了测试和分 析。 第五章，首先对多值关联规则挖掘问题进行了分析和总结；提出一种高维聚类算法 c b s d ，并基于此算法提出了一种多值关联规则挖掘算法d b s m i n e r 。最后对其性能进行 了测试和分析。 第六章，对全文的工作进行了总结，并指出以后进一步的工作。 7 西安科技大学硕士学位论文 2 关联规则挖掘研究 关联规则数据挖掘( 简称关联规则挖掘) 就是从大量的数据中挖掘出有价值的描述 数据项之间相互联系的有关知识。随着收集和存储在数据库中的数据规模越来越大，人 们对从这些数据中挖掘相应的关联知识越来越有兴趣。例如：从大量的商业交易记录中 发现有价值的关联知识就可以帮助进行商品目录的设计、交叉营销或帮助进行其它有关 的商业决策。挖掘关联知识的一个典型应用实例就是市场购物分析。根据被放到一个购 物篮中的内容记录数据而发现的不同商品之间存在的关联知识，无疑将会帮助商家分析 客户的购买习惯，发现常在一起购买的商品( 关联知识) 将帮助商家制定有针对性的市 场营销策略。如顾客在购买牛奶时会有效地帮助商家进行有针对性地促销，以及进行合 适的货架商品摆放。比如可以将牛奶和面包放在相近的地方或许会促进这两个商品的销 隹 口。 自1 9 9 3 年a g r a w a l 【3 】等人首先提出关联规则概念以来，关联规则挖掘便迅速受到数 据挖掘领域专家的广泛关注。在迄今十几年中，关联规则挖掘技术得到了较为深入的发 展。本章在提出关联规则基本概念的基础上，首先对关联规则的种类进行全面地分类、 归纳和总结，然后对关联规则经典算法a p r i o r i 算法和f p g r o w t h 算法进行了介绍。 2 1 关联规则描述 2 1 1 基本概念 设仁 f ，i 2 ，) 是m 个不同项目的集合。d 是所有事务的集合( 1 1 j 事务数据库) ，每 个事务丁是一些项目的集合，丁包含在，中，即丁，并且每个事务可以用唯一的标识 符t i d 来标识。 【定义2 1 】设x 为，中某些项目的集合，简称为模式( p a t t e r n ) 或者项目集( i t e m s e t ) ，如 果项目集逛乃则称事务丁包含k 【定义2 2 】项目集x 在d 中的支持数是指d 中包含x 事务丁的个数，记为c o u n t ( x ) ； 项目集x 在d 中的支持度是指d 中包含x 的事务的百分比，记为s u p p o r t ( x ) 。 关联规则表示为：燎j ，的蕴涵式，这旱x c i ，y c i 并且x n y = o 。d 中的规则抽】， 是由支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 来约束的。支持度表示规则出现的频度，置 信度表示规则的强度。具体描述是： s u p p o a ( x = ：, d = p u 的 c o n f i d e n c e ( x = y ) = p ( r l x ) 【定义2 3 】在进行关联规贝i j 挖掘时，要求用户预先设定支持度和置信度阈值，即在挖 8 2 关联规则数据挖掘 掘过程中只产生满足这两个阈值要求的关联规则，对于这样的支持度和置信度通常分别 称为最小支持度( m i n i m u ms u p p o r t ) 和最小置信度( m i n i m u mc o n f i d e n c e ) 。对于满足最小支 持度和最小置信度要求的关联规则称为强规则。 在本文中，为方便起见把支持度和置信度分别简记为s 和c ，最小支持度和最小置 信度分别简记为m i n s u p 和m i n c o n f , 它们的取值在o 到1 0 0 之间。另外d 中包含的 事务数表示为l d i ，x 中包含的项目数表示为冈。 【定义2 4 】对于项集工如果x 中包含有k 个项目，则x 称为肛项集。例如项集胙 a ， b ，就是一个2 项集。 2 1 2 关联规则的分类 传统的关联规则挖掘形式是购物篮分析，但关联规则绝不仅此一种。可以根据以下 标准对这些关联规则进行分类： ( 1 ) 基于规则中处理的变量类别 关联规则可以分为布尔型关联规则和数值型关联规则。 布尔型关联规则处理的变量的取值都是离散的和种类化的，它显示了这些变量之间 存在的相互依存的关系。例如规贝j j ( 2 1 ) 描述的就是有关市场购物分析所获得的一条布尔 关联规则。 b u y sb r e a djb u y sm i l k 【s u p p o r t = 2 0 ，c o n f i d e n c e = 6 0 】 ( 2 1 ) 若一个规则描述的是定量数据项( 或属性) 之间的关系，那么它就是一个定量关联规 则。在这些规则中，数据项的定量数值可以划分为区间范围。例如规则( 2 2 ) 就是一个定 量关联规则。 a g e ( x , “3 0 , - 一3 5 ”) i n c o m e ( x , “4 0 k - - 。5 2 k ) b u y s ( x , “c a r )( 2 2 ) 对于数值型关联规则挖掘最主要考虑的问题是如何把连续的数值属性在值域上进 行划分，将每一个划分的区间映射到布尔属性的取值。对于一个数值属性来讲如果在值 域上划分的区间过多的话，每一个区间的支持度就会s t u d , ，导致包含该属性的关联规则 由于不能满足支持度要求而不能被发现。而区间划分过大时，一些有价值的规则又由于 不能满足可信度的要求而无法发现。 ( 2 ) 根据规则中数据的抽象层次来进行分类 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如挖掘出规则 ( 2 3 ) 和( 2 4 ) 。 c o m p u t e r ( x , “i b mn o t e b o o k _ c o m p u t e r ) jb u y s ( x , “e p s o np r i m e r ”)( 2 3 ) c o m p u t e r ( x , “n o t e b o o k _ c o m p u t e r ”) jb u y s ( x , “p r i m e r )( 2 4 ) 在规则( 2 3 ) 和( 2 4 ) d p ( 属性b u y s ) 的数据项描述了涉及不同抽象层次的内容( “p r i n t e r 9 西安科技大学硕士学位论文 是“e p s o np r i n t e r 的更高抽象层次) ，规则( 2 4 ) 描述的内容涉及多个不同抽象层次概念， 因此构成了多层次关联规则；规则( 2 3 ) 的内容仅涉及单一层次的概念，那么这样的关联 规则就称为单层次关联规则。 ( 3 ) 根据关联规则所涉及到的数据的维数进行分类 基于规则中涉及到的数据的维数，关联规则可以分为单维关联规则和多维关联规 则。 在单维关联规则挖掘中，规则只涉及数据的一个维，如用户购买的物品；而在多维 的关联规则中，要处理的数据将会涉及不同的维度。即单维关联规则是处理单个属性中 的一些关系，而多维关联规则挖掘是处理数据中各个属性之间的某些关系。例如：学历 = “博士 & & 单位= “学校”= 职称= “教授”，这条规则就涉及到三个字段的信息， 是三个维度上的一条关联规则。 2 1 3 关联规则的挖掘步骤 关联规则挖掘就是在事务数据库d 中找出满足用户给定的最小支持度m i n s u p 和最 小置信度m i n c o n f 要求的关联规则，整个挖掘过程可分解为以下两步： ( 1 ) 找出交易数据库d 中所有满足用户指定最小支持度的项目集( i t e m s e t ，i 的一个 非空子集) 。而满足最小支持度的项目集称为频繁项目集( f r e q u e n ti t e m s e t s ) 。 ( 2 ) 利用频繁项目集生成所需要的关联规则。对每一个频繁项目集彳，找到4 的所 有非空子集a ，如果s u p = s u p p o r t ( a ) s u p p o r t ( a ) m i n c o n f , 就生成关联规则口口一矽。其 中s u p 称为规则口j 似训的置信度。 在挖掘关联规则的整个执行过程中第一个子问题是核心问题，而第二个子问题相对 较为简单。因此，目前大量的研究工作都集中在第一个问题上。 2 2 关联规则挖掘算法 自a g r a w a l 等人于1 9 9 4 年提出挖掘频繁项目集的a p f i o d 算法以来，国内外许多研 究人员纷纷加入到此研究领域，提出了大量的研究成果。这些算法中有些是对a p d o d 做进一步的改进，另外一些是采用新的数据结构和搜索方法，从根本上解决a p r i o r i 固 有的缺陷。本节首先对a p r i o r i 算法及其改进算法进行介绍，然后f p - g r o w t h 算法进行简 单介绍。 2 2 1 关联规则经典挖掘算法a p r i o r i 由a g r a w a l 等人提出的a p f i o f i 是经典的关联规则和频繁项集挖掘算法，围绕着它 的改