（计算机应用技术专业论文）关联规则挖掘的相关问题研究.pdf

论文题目： 专业： 硕士生： 指导教师： 关联规则挖掘的相关问题研究 计算机应用技术 张铁军( 签名) 杨君锐( 签名) 摘要 关联规则挖掘是数据挖掘领域中个重要研究方向，而频繁模式挖掘又是关联规 则、时序模式挖掘等应用中的关键技术和步骤。然而，由于挖掘频繁模式内在的计算复 杂性，为了提高挖掘效率，业界相继提出了频繁闭合模式挖掘和最大频繁模式挖掘问题。 在规模上，频繁闭合模式和最大频繁模式均小于频繁模式。同时频繁闭合模式集可以唯 一地确定频繁模式完全集以及它们的准确支持度，而最大频繁模式隐含了所有的频繁模 式，并且在某些数据挖掘应用中仅需挖掘出最大频繁模式；另外，在实际挖掘应用中， 由于事务数据库可能发生变化，而且用户还会调整最小支持度以满足新的需要，因此如 何对挖掘结果进行更新是一个值得研究的问题；再有，针对关联规则新的度量标准一兴 趣度的度量方法也是业界关心的一个热点问题。因此，对这些问题进行研究具有重要意 义。 本文主要研究了关联规则挖掘中的相关问题，主要包括以下内容： 首先，提出了用于挖掘频繁闭合模式的f c i m i n e r 算法，以及挖掘最大频繁模式的 b f p m i n e r 算法。两个算法均利用改进的f p t r e e 来压缩存储数据库中的事务，并充分 利用该树的特点，使得在挖掘频繁闭合模式和最大频繁模式的过程中不需产生条件 f p t r e e 和候选模式，从而减少了挖掘过程中使用的存储空间和计算时间，实验结果表 明，算法具有较好的性能。 其次，提出了用于解决最小支持度和数据库都发生变化的综合更新挖掘最大频繁模 式问题的i u m f p a 算法。该算法利用完全f p t r e e 并通过调整最大频繁模式进行快速最 大频繁模式更新挖掘，实验测试和分析表明，该算法有较好的时空效率。 最后，针对当前基于支持度一置信度框架挖掘关联规则时所反映的不足，提出了一 种能反映项目集之间相关性和稀有性的度量标准一兴趣度，通过其可用来发现数据库中 支持度低，而置信度强和紧密性高的规则。通过实例分析说明了该度量标准在一些应用 中的有效性和实用性。 关键词：数据挖掘；关联规则；频繁模式；频繁闭合模式；最大频繁模式；综合 更新挖掘；频繁模式树( f p t r e e ) ；兴趣度 研究类型：理论研究 s u b j e c t ：t h er e s e a r c ho nt h e r e l a t e dp r o b l e m so fa s s o c i a t i o nr u l e s p e c i a l t y n a m e m i n i n g ：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 z h a n gt i e ja n i n s t r u c t o r ：y a n g j u n r u i ( s i g n a t ur e ) ( s i g n a t ur e ) a b s t r a c t t h ea s s o c i a t i o nr u l em i n i n gi sav e r yi m p o r t a n tp r o b l e mi nd a t am i n i n g t h ei s s u eo f m i n i n gf r e q u e n tp a t t e r n sp l a y sac r u c i a lr o l ei na s s o c i a t i o nr u l em i n i n g 、s e q u e n t i a lp a t t e r n m i n i n g ，e t c b e c a u s eo ft h et i m e c o n s u m i n gi nm i n i n gf r e q u e n tp a t t e r n s ，m i n i n gf r e q u e n t c l o s e dp a t t e r n sa n dm i n i n gm a x i m a lf r e q u e n tp a t t e r n sh a v eb e e np r o p o s e dt oi m p r o v et h e m i n i n ge f f i c i e n c y t h es e to ff r e q u e n tc l o s e dp a t t e r n so rm a x i m a lf r e q u e n tp a t t e r n si so r d e r s o fm a g n i t u d es m a l l e rt h a nt h es e to ff r e q u e n tp a t t e r n s t h es e to ff r e q u e n tc l o s e dp a t t e r n ss t i l l c o n t a i n se n o u g hi n f o r m a t i o no ft h ef r e q u e n tp a t t e r n sa n di t sa c c u r a t es u p p o r t t h es e to f m a x i m a lf r e q u e n tp a t t e r n sc o n t a i n sa l lt h es e to ft h ef r e q u e n tp a t t e r n sa n dt h e r ea l e a p p l i c a t i o n sw h e r et h es e to fm a x i m a lf r e q u e n tp a t t e r n si sa d e q u a t e i ns o m ea p p l i c a t i o n s ， u s e r sm a ya d j u s tt h em i n i m u ms u p p o r tw h i l ed a t a b a s ec h a n g e d ，a n dh a v et ou p d a t et h ef o r m e r m i n i n gr e s u l t s ，s oi ti sw o r t ho fs t u d y i n gi nt h i sc a s e m i n i n gt h ei n t e r e s t i n gr u l e si sa n o t h e r i n t e r e s t i n gi s s u e i na l l ，i ti sv e r ys i g n i f i c a t i v et od os o m er e s e a r c h so nt h o s ei s s u e s i nt h i s p a p e r , w eh a v ed o n es o m er e s e a r c h e so nt h er e l a t e dp r o b l e m so fa s s o c i a t i o nr u l em i n i n g i ti s s t a t e da sf o l l o w s ： f i r s t l y , t w oe f f i c i e n ta l g o r i t h m sf c i - m i n e rf o rm i n i n gf r e q u e n tc l o s e dp a t t e r n sa n d b f p m i n e rf o rm i n i n gm a x i m a lf r e q u e n tp a t t e r n sa r ep r e s e n t e di nt h i sp a p e r t h et w o a l g o r i t h m sa l lb a s e do nt h ei m p r o v e df p - t r e e ( f r e q u e n tp a t t e r nt r e e ) i no r d e r t oc o m p r e s s a n ds t o r et h er e c o v e r so ft r a n s a c t i o nd a t a b a s e ，a n du s e dd e p t h f i r s ts e a r c hs t r a t e g yw i t h o m g e n e r a t i n gc o n d i t i o n a lf p t r e e sa n dc a n d i d a t ep a t t e r n s t h ee x p e r i m e n t a le v a l u a t i o no i la n u m b e ro fr e a la n ds y n t h e t i cd a t a b a s e ss h o w st h a to u ra l g o r i t h m so u t p e r f o r mp r e v i o u s m e t h o di nm o s tc a s e s s e c o n d l y , an e wi n t e g r a t e du p d m i n ga l g o r i t h mf o rm i n i n gm a x i m a lf r e q u e n tp a t t e r n s i u m f p ai sp r o p o s e d ，w h i c hi sa i m e da th a n d l i n gt h eu s e ra d j u s t i n gt h em i n i m u ms u p p o r t w h i l ed a t a b a s ec h a n g e si no r d e rt of i n dm o r eu s e f u lm a x i m a lf r e q u e n tp a t t e r n s i tm a k e su s e o fi m p r o v e df u l lf p - t r e es t r u c t u r ea n da l s ou t i l i z e st h ef o r m e rf p - t r e ea n dt h em i n e dr e s u l t s s u f f i c i e n t l y t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a ti u m f p ap e r f o r m se f f i c i e n t l y f i n a l l y , w ep r o p o s eab r i e fm e a s u r eo fr u l ei n t e r e s t i n g n e s st oo v e r c o m et h ei n s u f f i c i e n t b a s e do nt h es u p p o r t c o n f i d e n c ef r a m e w o r k i tc a l ld e t e r m i n et h ec o r r e l a t i o na n dr a r i t yo f a s s o c i a t i o nr u l e s ，a n de s p e c i a l l yb eu s e dt od i s c o v e rr u l e sw i t hs t r o n gc o r r e l a t i o na n dh i g h c o n f i d e n c e ，b u tl o ws u p p o r t i nt h ee n d ，w et a k ea ne x a m p l et od e m o n s t r a t ei t se f f e c t i v e n e s s a n d p r a c t i c a 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 ，f r e q u e n tp a t t e r n ，f r e q u e n tc l o s e dp a t t e r n ， m a x i m a lf r e q u e n tp a t t e r n ，i n t e r g r a d e du p d a t i n gm i n i n g ，f r e q u e n tp a t t e mt r e e ( f p - t r e e ) ，i n t e r e s t i n g n e s s t h e s i s：t h e o r e t i c a lr e s e a r c h 要错技太学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 - 学位论文作者签名：刁燃日期：认砷j 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：槲 指导教师签名：t 易老铭 气秒矿夕年月j 日 1 绪论 1 绪论 随着信息技术的进步和数据存储技术的发展，特别是数据仓库的出现，计算机存储 容量更大，速度更快，价格也更便宜，因此在i t 业、商业、科研、行政、医疗、保险 等应用领域中，大量的数据被搜集和存储在各种数据库中，特别是数据仓库已被广泛地 应用于企业管理、产品销售、科学计算和信息服务等领域，由此而引起的数据量快速增 长，对数据库的存储、管理和分析提出了更高的要求，由于这些数据十分繁杂，如何有 效的利用这些数据，从这些数据中发现有价值的信息或知识，达到为决策服务的目的， 就成了一项非常艰巨的任务。目前的数据库系统虽然可以较好地实现数据的录入、查询 和统计等功能，但尚不支持对海量数据背后重要信息的挖掘，从而导致了“数据丰富， 知识贫乏 u j 的现象。 数据挖掘【l 捌( d a t am i n i n g ，简称d m ) 技术正是在上述的应用要求下产生的。它不 但可以帮助人们从数据库特别是数据仓库的相关数据中提取出所感兴趣的知识、规律或 更高层次的信息，而且也可以帮助人们从不同程度上去分析它们，从而可以更有效地利 用数据库或数据仓库中的数据。它不仅可以用于描述过去数据的发展过程，而且还能进 一步预测未来的发展趋势。因此，数据挖掘正成为一个新的、日益受到重视的热点研究 领域。数据挖掘方法的提出，让人们最终有能力认识到数据的真正价值，即蕴含在数据 中的信息和知识。数据挖掘是目前数据库和信息决策领域的最前沿研究方向之一，己经 引起了学术界和工业界的广泛关注。目前在国内外的许多高校和研究机构都在从事此领 域的研究工作，并产生了大量的研究成果。 1 1 数据挖掘概述 1 1 1 数据挖掘的定义 在1 9 8 9 年第1 1 届国际人工智能联合会议的专题讨论会上，首次提出数据库中的知 识发现( 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 ) 技术，而数据挖掘可视为数据 库中知识发现过程的一个核心步骤，许多学者将其视为数据库中知识发现的同义词，本 文也不再将k d d 和d m 作严格地区分。从1 9 9 5 年开始，每年主办一次k d d 国际学术 会议，将k d d 和d m 方面的研究推向了高潮，从此，“数据挖掘 一词开始流行。数 据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含其中的、 人们事先不知的、具有潜在利用价值的信息和知识的过程 2 1 。它作为知识发现过程中一 个特定的步骤，是一系列技术及其应用，或者说是对大容量数据及数据间关系进行考察 西安科技大学硕士学位论文 和建模的方法集。它的目标是将大容量数据转化为有用的知识和信息。 1 1 2 数据挖掘的功能 数据挖掘的目标是从数据库中发现隐含的、有意义的知识。总体来讲，根据数据挖 掘发现的模式分类，可以将其分为两类：描述性数据挖掘和预测性数据挖掘。描述性数 据挖掘意在刻画数据的特性和特征。预测性数据挖掘则是旨在当前数据上进行推断，以 进行预测。另外，数据挖掘能够发现各种位于不同抽象层的模式。这些数据模式由不同 的视角为用户提供领域的知识，为用户聚焦有趣模式的搜索带来了方便。一般来讲，数 据挖掘功能大略可以归纳为6 种：概念描述、关联分析、分类和预测、聚类分析、异类 分析和演化分析，下面分别对其进行简述。 ( 1 ) 概念描述( c o n c e p td e s c r i p t i o n ) 1 1 一个概念常常是对一个包含大量数据的数据集合总体情况的概述。对含有大量数据 的数据集合进行概述性的总结并获得简明、准确的描述，这种描述就称为概念描述。获 得概念描述的方法主要有以下两种：一种是利用更为广义的属性，对所分析数据进行概 要总结，其中被分析的数据就称为目标数据集；另一种是对两类所分析的数据特点进行 对比并对对比结果给出概要性总结，而其中两类被分析的数据集分别被称为目标数据集 和对比数据集。 ( 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) p 4 j 关联分析就是从给定的数据集中发现频繁出现的项集模式知识( 又称为关联规则 a s s o c i a t i o nr u l e s ) 。关联分析广泛应用于市场营销、事务分析等应用领域。 在大型数据库中，存在很多关联规则，对用户来说其中有些是有用的，而有些则是 无用的，因此需要进行筛选。在实际进行关联规则数据挖掘时，一般用支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 两个阈值来淘汰那些无用的关联规则。近年来，关联规则数据 挖掘研究方兴未艾，提出了许多高效的关联规则数据挖掘算法，有关这方面的挖掘方法 将在后面有关章节详细介绍。 ( 3 ) 分类和预测( c l a s s i f i c a t i o na n dp r e d i c a t i o n ) 1 5 j 分类就是找出一组能够描述数据集合典型特征的模型( 或函数) ，以便能够分类识 别未知数据的归属或类别，即将未知事例映射到某种离散的类别之一。分类模型( 或函 数) 可以通过分类挖掘算法从一组训练样本数据( 其类别归属已知) 中学习获得。分类 挖掘所获得的分类模型可以采用多种形式加以描述输出。其中主要的表示方法有：分类 规则、决策树、数学公式和神经网络。 分类通常用于预测未知数据实例的归属类别( 有限离散值) ，如一个银行客户的信 用等级是属于a 级、b 级还是c 级。但在一些情况下，需要预测某数值属性的值( 连 续数值) ，这样的分类就被称为预测。尽管预测既包括连续数值的预测，也包括有限离 2 1 绪论 散值的分类，但一般还是使用预测来表示对连续数值的预测，而使用分类来表示对有限 离散值的预测。 ( 4 ) 聚类分析( c l u s t e r i n ga n a l y s i s ) 7 1 聚类分析与分类预测方法明显不同之处在于，后者所学习获取分类预测模型所使用 的数据是已知类别归属，属于有教师监督学习方法，而聚类分析( 无论是在学习还是在 归类预测时) 所分析处理的数据均是无类别归属，类别归属标志在聚类分析处理的数据 集中是不存在的。聚类分析属于无教师监督学习方法。 聚类分析中，首先需要根据“各聚集内部数据对象间的相似度最大化和各聚集对象 问相似度最小化 的基本聚类分析原则，以及度量数据对象之间相似度的计算公式，将 聚类分析的数据对象划分为若干组。因此一个组中数据对象间的相似度要比不同组数据 对象间的相似度要大。每个聚类分析所获得的组就可视为是一个同类别归属的数据对象 集合，更进一步从这些同类别数据集中，又可以通过分类学习获得相应的分类预测模型 ( 规则) 。此外通过反复不断地对所获得的聚类组进行聚类分析，还可以获得初始数据 集合的层次模型。 ( 5 ) 异类分析( o u t l i e r a n a l y s i s ) 【6 j 一个数据库中的数据一般不可能都符合分类预测或聚类分析所获得的模型。那些不 符合由大多数数据对象所构成的规律的数据对象就被成为异类。以前许多数据挖掘方法 都在正式进行数据挖掘之前就将这些异类作为噪声或意外而排除在数据挖掘的分析处 理范围之外。但在一些应用场合，如各种商业欺诈行为的自动检测，小概率发生的事件 往往比经常发生的事件更有价值。对异类数据的分析处理通常就称为异类挖掘。 数据中异类可以利用数理统计方法分析获得，即利用已知数据所获得的概率统计分 布模型，或利用相似度计算所获得的相似数据对象分布，分析确认异类数据。而偏离检 测就是从数据已有或期望值中找出某些关键测度显著的变化。 ( 6 ) 演化分析( e v o l u t i o na n a l y s i s ) 【l 】 数据演化分析就是对随时间变化的数据对象的变化规律和趋势进行建模描述。这一 建模手段包括：概念描述、对比概念描述、关联分析、分类分析、时间相关数据分析等。 1 1 3 数据挖掘的过程 数据挖掘的过程【l 】一般由确定挖掘对象、数据挖掘、数据挖掘结果分析表述这几个 主要阶段组成。数据挖掘可描述为这几个阶段的反复过程，如图1 1 所示。 3 i 耋兰查：翟：竺耋圭 图i l 数据挖掘过程 ( 1 ) 确定挖掘对象( t a r g e td a t a ) 数据准备阶段又可以进一步分为3 个子步骤：数据选择( d a t as e l e c t i o n ) 、数据预 处理( d a t ap r e p r o c e s s i n g ) 、和数据转换( d a t a t r a n s f o r m a t i o n ) 进而确定挖掘对象。 数据选择。数据选择是指为数据挖掘目标而搜索和选择有关的数据，这包括不 格式数据的转换以及不同部f j 数据的统一和汇总。 数据预处理。数据预处理是对数据进行清理和充实等丁作。数据库中重要的数 据是准确的，不重要的数据可能存在污染。预处理就是为了克服目前数据挖掘工具的局 限性。 数据转换。数据转换的一个重要工作是对数据进行编码。数据库中字段( 属性) 的不同取值转换成数码形式将有利于搜索。 ( 2 ) 数据挖掘( d a t am i n i n g ) 这个阶段进行实际的挖掘操作，即利用机器学习、统计分析等方法，从数据库中发 现有用的模式或知识( 这里，模式是浓缩数据的信息形式，如精练数据库、表格、产生 式规则、决策树、神经网络的权值等) 。 选择数据挖掘方法。如统计分析、机器学爿、模式识别方法和人工神经元方法 等。 选择数据挖掘算法。选择用来查找模式或符合数据模型的算法，确定合适的模 型和参数。另外，数据挖掘方法必须和目标相匹配。 数据挖掘。查找感兴趣的模式。模式一般表示为一种特殊的形式或一套表达方 式，如关联规则，分类规则或分黄树，回归结构和聚类集等。除了选择合适的挖掘算法 以外，其余的一切工作都可自动完成。 ( 3 ) 数据挖掘结果分析表述( p a t t c a li n t e r p r c t a f i o n ) 结果表达。尽量直观的表达挖掘结果，便于用户理解和使用，可使用可视化方 1 绪论 法表示为图表等形式。 结果评价。筛选和评价挖掘结果中的有用部分，查找可接受的结果。可定义兴 趣指标，考虑结果的正确度、新颖度、有用性和简单性，把信息从输出中过滤出来。利 用可视化方法帮助用户解决所提出知识的有效性或对基本的数据或现象做出结论。 知识巩固。把挖掘出的信息结合到执行系统中，了解这些信息的作用或证明这 些信息。用预选知道且可信的信息来检查和验证所挖掘出的信息，解决可能存在的矛盾。 当然，在有些情况下，也可以只是简单地记录所挖掘出的信息并把它报告给用户， 由用户进一步分析。 1 1 4 数据挖掘的对象 数据挖掘可以在任何类型的数据上进行，可以是商业数据、社会科学数据、自然科 学处理产生的数据或者卫星观测得到的数据。它的数据形式和结构也各不相同，可以是 层次的、网状的、关系的数据库，也可以是面向对象和对象关系的高级数据库系统，还 可以是面向特殊应用的数据库，如空间数据库、时间序列数据库、文本数据库和多媒体 数据库等，另外还可以是w e b 信息。当然数据挖掘的难度和采用的技术也因数据存储 系统而异。 ( 1 ) 关系数据库 数据库系统由一组内部相关的数据( 称作数据库) 和一组管理和存取数据的软件程 序( 称作数据库管理系统) 组成。人们常常将数据库系统简称为数据库。数据库因采取 的数据模式不同，分为层次数据库、网状数据库和关系数据库。关系数据库目前应用最 为普遍。药学领域内应用的数据库绝大多数都是关系数据库。 关系数据库是表的集合，每个表都赋予一个唯一的名字。每个表包含一组属性( 称 为列或字段) ，并通常存放大量元组( 称为行或记录) 。每个元组代表一个对象，用唯一 的关键字标识，并被一组属性值描述。关系数据库是数据挖掘最流行、最丰富的数据源， 因此是数据挖掘目前研究的主要数据形式。 ( 2 ) 文本数据库 文本数据库属于高级数据库，它存储的数据主要是对对象的文字描述，而且这种文 字描述不是简单的关键词，而是句子或短文。文本数据库可以是非结构化的，也可以是 半结构化的，还可以是良结构化的。一般采用关系数据库来实现具有良好结构的文本数 据库。例如，药学文献数据库、药品说明书数据库等都是具有良好结构的文本数据库。 对文本数据库的数据挖掘，需要将标准的数据挖掘技术与信息检索技术、文本数据 特有的层次结构以及面向学科的术语分类系统集成在一起。 ( 3 ) w e b 信息 5 西安科技大学硕士学位论文 随着网络的发展，网络数据的规模呈指数级增长。尽管网页信息丰富，但它们实际 上是非结构化的，而且缺乏预定义的模式、类型和格式。目前普遍流行的搜索引擎只能 提供基于关键字的搜索服务。而不理解特定网页的上下文，只能给用户提供有限的帮助。 在输入一两个关键词，甚至关键词组合后，用户依然会面对庞大的鱼目混珠的搜索结果。 因此迫切需要一种高效快速的信息资源分析工具帮助用户快速浏览网页，并能从大量的 信息中剔除无用信息，找出隐含的有效信息，减少用户的负担。w e b 信息挖掘技术应运 而生。它根据互联网分仃式信息资源的特点，设定模式抽取，不仅能查找到分布式信息 资源中已存在的信息，还能识别出数据中隐含的有效的规律。 ( 4 ) 多媒体数据库 多媒体数据库存放图像、音频和视频数据，因此必须支持大对象，需要特殊的存储 和搜索技术。对于多媒体数据库的挖掘，需要将存储和搜索技术与标准的数据挖掘方法 集成在一起，其中一个关键问题是图像和视频数据本身的表示问题。 1 2 数据挖掘的应用及发展趋势 1 2 1 数据挖掘的应用 在1 9 8 9 年8 月在美国底特律召开的首届知识发现与数据挖掘国际叙述会议上，数 据挖掘这一术语被学术界正式提出。学者就对其进行广泛研究，目前，国内外数据挖掘 技术的主要研究方面有：传统的统计学回归法在数据挖掘中的应用、贝叶斯方法的进一 步研究、数据挖掘与数据库的紧密结合、数据挖掘算法的研究、数据挖掘的实际应用以 及有关理论的研究等。 数据挖掘技术旨在发现大量数据中所隐藏的知识，以用来解决“数据丰富、知识贫 乏 的问题。近年来随着数据库和网络技术的广泛应用，加上使用先进的自动数据生成 和采集工具，人们所拥有的数据量急剧增加，使数据挖掘技术在科学研究、金融投资、 市场营销、保险、医疗卫生、产品制造业、通信网络管理等行业已得到应用。 ( 1 ) 科学研究 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量实验和观 测数据靠传统的数据分析工具己难于对付，因此对功能强大的智能化自动分析工具要求 迫切，这种需求推动了k d d 技术在科学研究领域的应用发展，并且已获得一些重要的 应用成果。 ( 2 ) 金融投资 在银行和金融机构中产生的金融数据通常相对比较完整、可靠，而且数据质量较高， 因此，数据挖掘在这一领域中的应用相对比较成熟，也取得较好的社会效益和经济效益。 由于金融投资的风险很大，在进行投资决策时，需要对各种投资方向的有关数据进行分 6 1 绪论 析，以选择最佳的投资方向，而数据挖掘则是通过对己有数据进行处理，并利用学习得 到的模式进行市场预测，以选择最佳的投资方向，可使金融投资的风险降低。通过分析 市场波动的因素，建立预测模型，进行投资分析和预测，改进预测市场波动的能力，为 投资决策提供科学的依据。 ( 3 ) 保险业 随着社会保障体系的日益健全，保险业取得了蓬勃的发展，发挥着越来越重要的作 用。保险是一项风险业务，保险公司的一个重要工作就是进行风险评估。通过研究证明， 可以利用数据挖掘技术来进行风险分析，在保险公司建立的保单及索赔信息数据库的基 础上，寻找保单中风险较大的领域，从而得出一些实用的控制风险的规则，以指导保险 公司的工作。数据挖掘技术在保险业中的应用，有利于保险公司开展业绩评价、财务预 算、市场分桥、风险评估和风险预测等，大大提高企业防范和抵抗经营风险的能力和水 平，也为管理人员提供科学的决策依据。 ( 4 ) 零售业 零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习性和趋向，对于零 售商制定销售策略是至关重要的。销售分析人员运用关联规则挖掘技术对大量的销售数 据进行分析，可以发现顾客购买模式和趋势，改进服务质量，取得更好的顾客保持和程 度，提高货品销售比率，设计更好的货品运输与分销策略，减少商业成本。购物篮分析 是数据挖掘技术应用在零售业中的一种有效方式，可用于销售搭配、产品目录设计、产 品定价和促销等。 ( 5 ) 制造业 随着现代技术越来越多地应用于制造业，产品生产已不是人们想象中的手工劳动， 而是集成了多种先进科技的流水作业。在产品的生产制造过程中常常伴随着大量的数 据，如产品的各种加工条件或控制参数，这些数据反映了每个生产环节的状况，不仅为 生产的顺利进行提供了保证，而且通过对这些数据的分析，得到产品的质量与这些参数 之间的关系。这样通过数据挖掘对这些数据的分析，可以对改进产品质量提出针对性很 强的建议，而且有可能提出新的更高效节约的控制模式，从而为制造厂家带来极大的回 报。 ( 6 ) 电信业 电信业已经从单纯的提供市话和长话服务演变成提供综合电信服务，如语音、传真、 寻呼、移动电话、图像、电子邮件、计算机和w e b 数据传输，以及其他数据通信服务。 而且随着许多国家对电信业的开放和新兴计算与通信技术的发展，电信市场正在迅速扩 张并越发竞争激烈。因此，利用数据挖掘技术来帮助理解商业行为、确定电信模式、捕 捉盗用行为、更好地利用资源和提高服务质量是非常有必要的。 7 西安科技大学硕士学位论文 1 2 2 数据挖掘的发展趋势 数据挖掘任务和数据挖掘方法的多样性，给数据挖掘提出了许多挑战性的课题。数 据挖掘语言的设计、高效而有效的数据挖掘方法和系统的开发、交互和集成的数据挖掘 环境的建立和应用数据挖掘技术解决大型应用问题，都是目前数据挖掘研究人员、系统 和应用开发人员所面临的主要问题。下面是数据挖掘的发展趋势： ( 1 ) 应用的探索【7 8 】：数据挖掘最早应用于零售业和金融业的数据分析。它是一种功 能强大的应用技术，主要为企业和管理人员进行销售和决策提供依据。目前在保险业、 制造业、电信和医学等领域也得到了广泛的应用，并取得了显著的效果。信息产业的发 展为数据挖掘提供了广阔的空间，数据挖掘技术的应用范围将不断得到拓宽，特别是在 生物工程、商业智能、网络服务等领域的应用将成为新的研究热点。 ( 2 ) 可伸缩的数据挖掘方法：数据挖掘必须尽可能交互式地、有效地处理大量数据。 由于数据量在不断地激增，因此针对单独和集成的数据挖掘功能的可伸缩算法显得十分 重要。一个重要的方向是所谓基于约束的挖掘( c o n s t r a i n t b a s e dm i n i n g ) 9 , 1 0 1 。它致力 于在增加用户交互的同时，如何改进挖掘处理的总体效率。它提供了额外的控制方法， 允许用户说明和使用约束，引导数据挖掘系统对感兴趣模式的搜索。 ( 3 ) 数据挖掘与数据库系统、数据仓库系统和w e b 数据库系统的集成【l l 1 2 j ：数据库 系统、数据仓库系统和w w w 己经成为信息处理系统的主流，而数据挖掘系统的理想 体系结构是与数据库和数据仓库的紧耦合方式。事务管理、查询处理、联机分析处理和 联机分析挖掘应集成在一个统一框架中。这将保证数据的可获得性，数据挖掘的可移植 性、可伸缩性、高性能以及对多维数据分析和探查的集成信息处理。 ( 4 ) 数据挖掘语言的研究 1 , 1 3 , 1 4 , 1 5 ：在进行数据挖掘时，让挖掘系统自动挖掘整个大 型数据库或数据仓库中隐藏的所有有价值的知识往往是不切实际的，总是需要在用户的 指导下进行有目的的挖掘。这就需要为用户提供一组与数据挖掘系统通信的语言，可以 把这组语言称为数据挖掘语言。这组语言用于说明用户感兴趣的数据集、要挖掘的知识 类型、用于指导挖掘过程的背景知识、模式评估兴趣度量以及如何显示所发现的知识等 等。这组语言使得用户可以在数据挖掘的过程中与数据挖掘系统进行交互，从不同的角 度和深度检查发现结果。研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言 一样走向形式化和标准化。 ( 5 ) 可视化数据挖掘【1 6 ，l7 j ：可视化数据挖掘是从大量数据中发现知识的有效途径， 系统研究和开发可视化数据挖掘技术将有助于推进数据挖掘作为数据分析的基本工具。 目前数据挖掘的可视化仅体现在结果的简单描述，并没有达到真正意义上的可视化。数 据可视化、挖掘过程可视化和结果可视化，将揭开数据挖掘复杂和神秘的面纱，使其变 得更为生动、形象和具体，用户可以随时了解整个过程的进展情况，减少了行为过程的 8 1 绪论 盲目性。数据和结果的图形展示可以放大、缩小、平移、旋转和变换角度，使分析人员 和用户更加容易理解，这将大大推动数据挖掘工具在发现知识和数据分析中的应用。因 此，加强数据可视化和知识发现过程的可视化具有重要的理论意义和应用价值。 ( 6 ) 复杂数据类型挖掘的新方法【1 , 1 8 , 1 9 , 2 0 , 2 1 】：复杂数据类型挖掘是数据挖掘中一项重 要的前沿研究课题。虽然在地理空间挖掘、多媒体挖掘、时序挖掘、序列挖掘以及文本 挖掘方面取得一些进展，但它们与实际应用的需要仍存在很大的距离。对此需要进一步 的研究，尤其是把针对上述数据类型的现存数据分析技术与数据挖掘方法集成起来的研 究。 ( 7 ) w e b 挖掘【l , 2 2 , 2 3 , 2 4 ：由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来 越重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务，将成 为数据挖掘中一个最为重要和繁荣的子领域。 ( 8 ) 数据挖掘中的隐私保护与信息安全【l ，2 5 】：随着数据挖掘工具和电信与计算机网络 的同益普及，数据挖掘要面对的一个重要问题是隐私保护和信息安全。需要进一步开发 有关方法，以便在适当的信息访问和数据挖掘过程中确保隐私保护与信息安全。 1 - 3 论文的工作 本论文在对已有研究成果进行分析和总结的基础上，主要就关联规则数据挖掘中关 于频繁闭合模式、最大频繁模式、最大频繁模式的综合更新、以及关联规则的兴趣度几 个相关问题进行较深入的探讨。 首先，本文对数据挖掘进行了详细介绍，并对关联规则进行了概述，然后对挖掘频 繁模式的算法进行了分析和总结。之后又详细介绍了两类经典的频繁模式挖掘算法，同 时指出了它们在挖掘频繁模式时存在的不足。 其次，在分析挖掘频繁模式问题的基础上，对挖掘频繁闭合模式、最大频繁模式的 问题分别进行了较深入的探讨。在这部分，首先对目前已有的关于频繁闭合模式挖掘和 最大频繁模式挖掘问题的研究成果进行了分析，指出其中存在的不足；然后在前人的基 础上提出了两个基于带权位对象和改进f p t r e e 的挖掘算法，即频繁闭合模式挖掘算法 f c i m i n e r 和最大频繁模式挖掘算法b f p m i n e r 。通过对这两个算法与其它有代表性的 频繁闭合模式挖掘算法与最大频繁模式挖掘算法的测试比较，验证了这两个算法具有较 高的效率。 再次，本文对关联规则更新挖掘问题进行了较为全面的阐述和分析。在这一部分， 首先对频繁模式、频繁闭合模式以及最大频繁模式的更新挖掘问题进行了介绍，并对已 有研究成果进行了分析和总结；然后针对最大频繁模式更新挖掘问题进行了较深入的分 析，并提出了在最小支持度和数据库同时变化时的综合更新挖掘最大频繁模式算法 9 西安科技大学硕士学位论文 i u m f p a 。通过对该算法和相关算法进行的对比测试和分析得出，算法i u m f p a 能充分 利用完全f p t r e e 快速地进行最大频繁模式的更新挖掘，具有较好的时空性能。 最后，针对关联规则兴趣度的度量方法进行了探讨。在对现有的多种兴趣度度量模 型进行分析与总结的基础上，提出了一种简单、有效的兴趣度度量标准，它能有效的对 那些置信度很高、关联性较强但其支持度较低的规则进行挖掘。另外，针对该度量模型 提出了一个算法，并通过实例分析说明了该模型的有效性和实用性。 上述算法f c i m i n e r 和b f p m i n e r 分别发表在第三届国际智能系统和知识工程会议 论文集( 被e i 和i s t p 收录) 和西南交通大学学报( 被e l 收录) 上；算法i u m f p a 发表在2 0 0 8 中国控制与决策会议论文集上( 被e i 和i s t p 收录) ；文中提出的新的关联 规则兴趣度度量模型也已发表在第3 8 届国际计算机与工业工程大会上( 被i s t p 收录) 。 详情请参考后面的附录。 1 4 论文的组织 论文其余部分组织如下： 第二章，首先对关联规则数据挖掘的相关概念进行了详细介绍，并按照不同的分类 标准对当前的关联规则数据挖掘问题进行了分类；其次对挖掘频繁模式的经典算法 a p r i o r i 【4 1 进行了详细分析与阐述；同时对h a n 等人 2 6 】提出的另一个重要的频繁模式挖掘 算法f p g r o w t h 进行了介绍，最后对挖掘频繁模式的算法进行了总结。 第三章，对频繁闭合模式的相关概念进行了详细介绍，并分析总结了这方面的研究 成果。在研究前人工作的基础上，提出了一种基于带权位对象和改进的f p t r e e 的挖掘 频繁闭合模式算法f c i m i n e r ，并对其进行了性能测试和可扩展性分析。 第四章，首先对最大频繁模式挖掘问题进行了详细介绍，并简要分析和总结了当l j i 在这方面的研究成果，然后提出了一种挖掘最大频繁模式算法b f p m i n e r ，最后对算法 b f p m i n e r 进行了综合测试和可扩展性分析。 第五章，首先对关联规则更新挖掘问题进行了分析和总结，然后针对最小支持度和 数据库同时变化的最大频繁模式更新挖掘问题提出了算法i u m f i a ，并对该算法的性能 进行了测试和分析。 第六章，总结分析了关联规则兴趣度度量模型方面的一些研究成果，在此基础上提 出了一种解决那些置信度很高、关联性较强但其支持度较低的关联规则兴趣度的度量模 型。 第七章，对全文的工作进行了总结，并对以后的研究工作进行了展望。 l o 2 关联规则数据挖掘 2 关联规则数据挖掘 关联规则挖掘是发现大量数据中项集之间的关联或相关联系，它是数据挖掘一个重 要的研究方向。随着收集和存储在数据库中的数据规模越来越大，人们对从这些数据中 挖掘相应的关联知识越来越有兴趣。例如：从大量的商业交易记录中发现有价值的关联 知识就可以帮助进行商品目录的设计、交叉营销或帮助进行其它有关的商业决策。挖掘 关联知识的一个典型应用实例就是市场购物分析。根据被放到一个购物篮中的内容记录 数据而发现的不同商品之间存在的关联知识，无疑将会帮助商家分析客户的购买习惯， 发现常在一起购买的商品( 关联知识) 将帮助商家制定有针对性的市场营销策略。如顾客 在购买牛奶时会有效地帮助商家进行有针对性地促销，以及进行合适的货架商品摆放。 比如可以将牛奶和面包放在相近的地方或许会促进这两个商品的销售。 自1 9 9 3 年a g r a w a l 等人首先提出关联规则概念以来，关联规则挖掘便迅速受到数 据挖掘领域专家的广泛关注。在迄今十几年中，关联规则挖掘技术得到了较为深入的发 展。 2 1 关联规则概述 2 1 1 关联规则的基本概念 设i = ，f 2 ，乙) 是m 个不同项目的集合。d 是所有事务的集合( 即事务数据库) ， 每个事务t 是一些项目的集合，t 包含在i 中，即t c i ，并且每个事务可以用唯一的标 识符t i d 来标识。 定义2 1 ：设x 为i 中某些项目的集合，简称为模式( p a t t e r n ) 或者项集( i t e m s e t ) ，如果模 式x c