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

关联规则维护算法研究 摘要 关联规则挖掘作为数据挖掘的一个重要的研究方向，有着极其重要的应用价 值。频繁项目集的发现是关联规则数据挖掘的核心问题。数据库的动态变化，使 得关联规则与频集的更新维护成为重要的研究内容。 本文在对关联规则挖掘中的一些经典算法进行分析和总结的基础上，提出了 新的解决相应问题的关联规则挖掘算法。 ( 1 ) 提出基于项目增长法求解频繁项集的算法，只需次扫描数据库，即 可得到所有频繁项集，增强了产生候选项的针对性和有效性，提高了候选项的支 持事务计数的效率；在求解最大频繁项集时，由于求解过程中无需用到大量的中 间结果，节省了内存空间，提高了挖掘效率和性能。 ( 2 ) 利用已有挖掘结果，对新增数据集只扫描一次，即可得到事务更新后 的数据集的频繁项集，提高了挖掘效率。 ( 3 ) 提出一种在数据集规模减小而支持度和置信度不变的情况下。负增量 关联规则维护算法。 ( 4 ) 提出一种快速聚焦关联规则维护算法。在需要反复调整最小支持度的 情况下，充分利用以往挖掘过程中的信息，避免多次扫描数据集。 ( 5 ) 基于上述研究，给出了一个实现关联规则维护的原型系统，实现了基 于项目增长求解最大频繁项集算法，实现了正增量式维护算法，实现了负增量更 新算法，实现了最小支持度频繁调整时的快速聚焦算法。实验表明了算法的有效 性和可行性。 关键词：数据挖掘：关联规则；项目增长；增量式发现 s t u d yo fm a i n t e n a n c ea l g o r i t h mf o r a s s o c i a t i o nr u l e a b s t r a c t t h em i n i n go fa s s o c i a t i o nr u l e si sa ni m p o r t a n tr e s e a r c hf i e l di nd a t am i n i n g a n di so fg r e a tv a l u ei na p p l i c a t i o n t h ed i s c o v e r yo f t h ef r e q u e n ti t e ms e t si sak e yt o t h em i n i n go fa s s o c i a t i o nr u l e s t h em a i n t e n a n c eo ft h ea s s o c i a t i o nr u l e sa n dt h e f r e q u e n ti t e ms e t si san e s s e s a r yr e s e a r c hc o n t e n tf o rt h ed a t a b a s ev a r i e s b a s e do na n a l y s i sa n ds t u d yo np r e s e n t e da l g o r i t h m s ，a na s s o c i a t i o nr u l e s a l g o r i t h m sf o rs o l v i n gs o m er e l a t i v ep r o b l e m si na s s o c i a t i o nr u l e s d a t am i n i n gi s p r o p o s e d t h em a i nc o n t e n t sa r ea sf o l l o w s ： 1 a na l g o r i t h ms o l v i n gf r e q u e n ti t e m s e tb a s e do ni t e mi n c r e a s i n gi sp r o p o s e d t h ea l g o r i t h mw i l lg e ta l lf r e q u e n ti t e m s e t sb ys c a n n i n gd a t a b a s eo n l yo n c e ，a n dt h i s w i l lb o o s tu pp e r t i n e n c ea n dv a l i d i t yo ft h ec a n d i d a t ei t e m sa n dw i l li m p r o v et h e e f f i c i e n c yo fc a n d i d a t ei t e m ss u p p o r t i n gi t e mc o u n t i n g d u r i n gt h ep r o c e d u r eo f r e s o l v i n gt h em a x i m a lf r e q u e n ti t e m s e t s ，al a r g ea l l o u n to fm i d d l er e s u l t sa r en o t n e e d e d ，t h e r e f o r em e m o r ys p a c ew i l lb es a v e & b ym e a n so fc o m p a r i s o na n a l y s i s ，t h i s m e t h o di m p r o v e st h ee f f i c i e n c ya n dp e r f o r m a n c eo f t h em i n i n g 2 t h i sa l g o r i t h mm a k e su s eo ft h er e s u l t so fm i n i n ga n dw i l lg e tf r e q u e n t i t e m s e t so ft h ei t e mu p d a t e dd a t as e tb ys c a n n i n gt h en e w l y a d d e dd a t as e to n l yo n c e w i t h o u tr e s c a n i n gt h eo r i g i n a lo n e ，i tg r e a t l yr e d u c e st h er u n - t i m ea n di m p r o v e st h e m i n i n ge f f i c i e n c y 3 p u t sf o r w a r da nu p d a t i n ga l g o r i t h mf o ra s s o c i a t i o nr u l e si nw h i c ht h es i z eo f d a t as e t si sr e d u c e di sp r o p o s e dw i t ht h es u p p o r t i n ga n dc o n f i d e n c el i m i t su n c h a n g e d 4 t h ed i s s e r t a t i o np r e s e n t saf a s tf o c u sa n dm e a n i n g f u lu p d a t i n ga l g o r i t h mf o r a s s o c i a t i o nr u l e s ，w i t ht h ei t e md a t as e t su n c h a n g e d ，b u tt h em i n i m u ms u p p o r t i n g l i m i tc h a n g e di sp r e s e n t e d i te x p l o r e sh o wt om a k et h eb e s tu s eo ft h ek n o w n i n f o r m a t i o no fm i n i n gt oa v o i dr e s c a n n i n gd a t as e t 5 ap r o t o t y p es y s t e mi si m p l e m e n t e df o ra b o v ea l g o r i t h m s t h ee x p e r i m e n t s s h o wt h ep e r f o r m a n c e 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 ；i t e mi n c r e a s i n g ；i n c r e m e n t a ld i s c o v e r y ； 插图清单 图l _ l 数据挖掘过程 图1 2 数据仓库系统结构图 图1 3c r m 系统结构图 图2 1 由算法a p r i o r i 所求得的频繁项目集示例 图2 2 由算法a p r i o r i t i d 求频繁项目集示例 图3 il 。u k 中的项目在d o 中是否频繁分布图 图3 2l d ul d l d 图3 3l 。u l 。一l 。 图3 4l d nl d 图4 1 主界面，。 图4 2 两种测试结果的性能对比， 图4 3 聚焦算法和重新运算的性能对比碍门缸毖驱踮踮诣钾鸱 表格清单 表2 1 数据库d 表2 2 频繁1 项目集l 。， 表2 3 事务数据库d 表2 4 事务数据库d 中每个项目的支持事务i d 表2 5 候选二项集中各项的支持事务i d 表2 6 候选二项集中各项的支持事务i d 表2 7 候选四项集中各项的支持事务i d 表3 1 事务数据库d 和追加事务数据库d 表3 2 事务数据库d 中每个项目的支持事务i d 表3 3 事务数据库d 中每个项目的支持事务i d 表3 4d u d 中的所有1 项目的支持事务集合 表3 5 事务数据库d 表3 6 事务数据库d 表3 7d 中每个项目的支持事务i d 集合及支持数 表3 8d d 中每个项目的支持事务i d 集合及支持数 表3 9 事务数据库d 表3 1 0 事务数据库d 中每个项目的支持事务i d 及支持数 表4 1 使用项目增长法测试数据描述( 时间单位为s ) 表4 2 利用正增量维护方法测试结果( 时间单位为s ) 表4 3 使用聚焦维护算法测试数据描述( 时间单位为s ) 加孔烈蛎饬艏孔弛弛弘蚰锄必舛盯卯盯 ， t - ， ， 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 盒a b 工些盍堂 或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：勃。占年2 月日 学位论文版权使用授权书 本学位论文作者完全了解盒目王些盍堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盒目b 王些盘堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 嘶吻7 每 签字日期：劫。f 年一月日 学位论文作者毕业后去向： 工作单位：缘串群芬1 ，幻 导师签名：1 。 签字日期：汐仍 电话 通讯龇蜘铎釉1 菇枷铲娥景象燃 1 3 ) o z6 9 蟪 2 ；口，0 门“州4 致谢 本文是在导师胡学钢教授的精心指导下完成的，期间受益于导师渊博的学 识、高深的学术造诣，以及严谨的治学态度和求真务实的工作作风，使我得以完 成学业，并将深刻地影响到我以后的工作态度和风格。 在论文完成与研究期间，从论文选题、研究方法和技术路线，直到最后论文 的修改、整体布局和定稿，都是在导师的鼓励和精心指导下完成的，导师的指导 拓宽了我的思路，大大提高了我的工作效率，并将深刻地影响我以后的专业发展。 值此论文完成之际，谨向我的导师及计算机与信息学院的所有领导和老师，尤其 是王浩教授、侯整风教授、沈明玉教授致以深深的谢意与敬意。 最后，衷心感谢为评阅本论文而付出辛勤劳动的各位专家和学者，你们在百 忙之中抽出时间对我的论文提出了宝贵意见和批评，这对于我来说是一笔无价的 财富。 作者：郭有强 2 0 0 6 年1 0 月 第一章数据挖掘概述 1 1 数据挖掘简介 随着以计算机和网络技术为代表的信息技术的发展，越来越多的企业、政府 组织、教育机构和科研单位实现了信息的数字化处理。大型数据库，特别是数据 仓库已被广泛地应用于企业管理、产品销售、科学计算和信息服务等领域，由此 而引起的数据量快速增长，对数据库的存储、管理和分析提出了更高的要求：一 方面，面对庞大的飞速增长的数据量，人们需要新的处理工具，以便能自动化地 把搜集的数据转化为有价值的信息和知识；另一方面，剧增的数据中有可能隐藏 着许多重要的信息，人们希望能够对已经占有的信息进行更高层次的分析，以便 更好地利用这些数据。目前的数据库系统虽然可以较好地实现数据的录入、查询 和统计等功能，但尚不支持对海量数据背后重要信息的挖掘，从而导致了“数据 丰富，知识贫乏” 1 的现象。 数据挖掘( d a t am i n i n g ，简称d m ) 技术正是在上述的应用要求下产生的。 它不但可以帮助人们从数据库特别是数据仓库的相关数据中提取出感兴趣的知 识、规律或更高层次的信息，而且也可以帮助人们从不同程度上去分析它们，从 而可以更有效地利用数据库或数据仓库中的数据：它不仅可以用于描述过去数据 的发展过程，而且还能进一步预测未来的芨展趋势。 因此，数据挖掘正成为一个新的、日益受到重视的热点研究领域。目前在国 内外的许多高校和研究枫构都在从事此领域的研究工作，并产生了大量的研究成 果。与国外相比，国内对数据挖掘和知识发现的研究稍晚，没有形成整体力量。 1 9 9 3 年国家自然科学基金首次支持了对该领域的研究项目。目前，国内的许多 科研单位和高等院校也在竞相开展知识发现的基础理论及其应用研究。 数据挖掘( d a t am i n i n g ) ，有人将其翻译为数据开采、数据采掘等。国外学 者们对它有不同的定义，如：g b a t e t s k y s h a p i r o 等人认为，数据挖掘是数据库知 识发现( k d d ) “3 过程的一个重要步骤：h a n ，r a g r a w a l 等人认为，数据挖掘与数 据库知识发现是两个等价的概念；j a y l o u i s ew e l d o n 则认为，数据挖掘意味着 在一些事实或观察数据的集合中寻找模式的决策支持过程。 目前，比较统一的说法是：从大量的、不完全的、有噪声的、模糊的、随机 的数据中提取隐含在其中的、事先未知的、潜在有用的信息和知识的处理过程。 还有很多与d a t am i n i n g 相近似的术语，如从数据库中发现知识( k d d ： 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 ) 、数据分析、数据融合( d a t af u s i o n ) 以及决策 支持等。原始数据可以是结构化的，如关系数据库中的数据，也可以是半结构 化的，如文本、图形、图象数据，甚至是分布在网络上的异构型数据。发现的 知识可用于信息管理、查询优化、决策支持、过程控制及自身的维护等。因此， 数据挖掘是一门广义的交叉学科，汇聚了不同领域的研究者，尤其是数据库、人 工智能、数理统计、可视化、并行计算等方面的学者和工程技术人员。 1 1 1 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘任务中要寻找的模式类型。数据挖掘的任 务一般可以分两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性： 预测性挖掘任务在当前数据上进行推断，以进行预测。 数据挖掘的功能有：概念类描述、关联分析、分类和预测、聚类分析、孤 立点分析、演变分析。 ( 1 ) 概念类描述( c o n c e p td e s c r i p t i o n ) ”。 数据可以和类或概念相关联。可以用汇总的、简洁的、精确的方式描述概念 和类，称为概念类描述。 ( 2 ) 关联分析( a s s o c i a t i o n a n a l y s i s ) ”“” 关联分析发现关联规则，这些规则展示了给定数据集中数据项之间的潜在的 联系。关联分析广泛应用于购物篮或事务数据分析中。 ( 3 ) 分类和预测( c l a s s i f i c a t i o na n dp r e d i e a t i o n ) “” 分类找出描述并区分数据类或概念的模型，以便能够使用模型预测类、标记 未知的对象类。预测是构造和使用模型评估无标号样本类，或评估给定样本可能 具有的属性值或值区间。分类和预测的区别在于：分类是预测分类标号( 或离散 值) ；预测是建立连续值函数模型。 ( 4 ) 聚类分析( c l u s t e r i n g a n a l y s i s ) ”“ 聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之间有较高 的相似度，而不同簇中的对象差异较大。与分类不同的是，聚类要划分的类是未 知的。 ( 5 ) 孤立点分析( o u t l i e r a n a l y s i s ) “。”1 孤立点可能是度量或执行错误所导致的，也可能是固有的数据变异性的结 果。许多数据挖掘算法试图使孤立点的影响最小化或排除它们。但这可能导致重 要信息的丢失，因为孤立点本身可能是非常重要的。 ( 6 ) 演变分析( e v o l u t i o n a n a l y s i s ) “。 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。它包 括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 数据挖掘发现的知识模式有多种不同的类型，常见的模式有：分类模式、聚 类模式、关联模式、序列模式等。 1 1 - 2 数据挖掘过程 数据挖掘过程一般由确定挖掘对象、数据准备、模型建立、数据挖掘、结构 分析表述和挖掘应用这几个主要的阶段组成。数据挖掘可以描述为这几个阶段的 反复过程。 诸理、集成 图1 i 数据挖掘过程 ( 1 ) 数据准备：数据准备阶段又可以进一步分为4 个子步骤：数据集成、 数据选择、数据预处理和数据转换。 数据集成。数据集成是将多个文件或多数据库运行环境中的数据进 行合并处理，解决语义模糊性，处理数据中的遗漏和清洗数据等。 数据选择。数据选择是指为数据挖掘目标而搜索和选择有关的数据， 这包括不同格式数据的转换以及不同部门数据的统一和汇总。 数据预处理。数据预处理是对数据进行清理和充实等工作。数据库 中重要的数据是准确的，不重要的数据可能存在污染。预处理就是为了克服目 前数据挖掘工具的局限性。 数据转换。数据转换的一个重要工作是对数据进行编码。数据库中 字段( 属性) 的不同取值转换成数码形式将有利于搜索。 ( 2 ) 数据挖掘。这个阶段进行实际的挖掘操作，即利用机器学习、统计 分析等方法，从数据库中发现有用的模式或知识( 这里，模式是浓缩数据的信 息形式，如精炼数据库、表格、产生式规则、决策树、神经网络的权值等) 。 选择数掘挖掘方法。如统计分析、机器学习、模式识别方法和人工神 经元方法等。 选择数据挖掘算法。选择用来查找模式或符合数据模型的算法，确定 合适的模型和参数。另外，数据挖掘方法必须和目标相匹配。 数据挖掘。查找感兴趣的模式。模式一般表示为一种特殊的形式或一 套表达方式，如关联规则，分类规则或分类树，回归结构和聚类集等。除了选 择合适的挖掘算法以外，其余的一切工作都可自动完成。 ( 3 ) 数据挖掘、结果分析表述和挖掘应用。 结果表达。尽量直观的表达挖掘结果，便于用户理解和使用，可使用 可视化方法表示为图表等形式。 结果评价。筛选和评价挖掘结果中的有用部分，查找可接受的结果。 可定义兴趣指标，考虑结果的正确度、新颖度、有用性和简单性，把信息从输 出中过滤出来。利用可视化方法帮助用户解决所提出知识的有效性或对基本的 数据或现象做出结论。 知识巩固。把挖掘出的信息结合到执行系统中，了解这些信息的作用 或证明这些信息。用预选知道且可信的信息来检查和验证所挖掘出的信息，解 决可能存在的矛盾。当然，在有些情况下，也可以只是简单地记录所挖掘出的 信息并把它报告给用户，由用户进一步分析。 1 1 3 数据挖掘的分类与方法 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘对象分，有 关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据库、多媒体 数据库、异构数据库、遗产数据库以及w e b 等。根据挖掘方法，可分为机器学 习方法、统计方法、神经阿络方法和数据库方法，在机器学习中可细分为：归纳 学习方法( 决策树、规则归纳等) 、基于范例学习、遗传算法等。 根据开采目标可分为，数据处理、预测、回归、分类、关联分析、模型可视 化、探索性数据分析等“。应该注意的是，具体应用中可以根据数据挖掘的 不同目标和挖掘方法的不同使用情况，选择适合的方法或把不同的方法组合使 用。 数据挖掘方法有多种，其中比较典型的有分类分析、聚类分析、关联分析、 序列模式分析、可视化、偏差分析、粗糙集和模糊集理论等。 ( 1 ) 分类分析( c l a s s i f i c 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 ) ，若预测的变量是连续的，则 称之为回归( r e g r e s s i o n ) 。分类与回归都可用于预测。预测的目的是根据历史数 据一记录构造出的分类模型自动推导出对原有数据的推广描述，以实现对未来数 据进行预测。 要构造分类模型，需要一个训练样本数据集作为输入，训练样本数据集又称 训练集( t r a i n i n gs e t ) 。分类可描述为：给定- - i ) l l 练数据的集合t ( 训练集或训练数 据库) ，t 中的元素记录由若干个属性描述。在所有属性中有且仅有一个属性作 为类别属性( c a t e g o r y ) 。属性集合用矢量x = ( x x n ) 表示，其中x 。( 1 牛奶，其可信为8 0 。关联规则挖 主要挖掘对象是事务数据库。其任务就是在事务数据库中找出具有用户给定的最 小支持度m i n s u p 和最小可信度m i n c o n f 的关联规则。 关联规则发现的研究趋势一是从单一概念层次关联规则的发现发展到多概 念层次的关联规则的发现，即在具体应用中采掘规则可以作用到数据库不同的层 面上，比如在分析超市销售事务数据库过程中，从数据库原始字段如面包、牛奶 提升到更抽象的概念一食品，就有可能发现更为抽象的规则；二是通过采用减少 数据库扫描次数、采样、并行数据挖掘等技术提高算法效率。 ( 4 ) 序列分析及时间序列 序列分析和时间序列说明数据中的序列信息和与时间相关的序列分析。 序列分析和关联分析相似，其目的也是为了挖掘数据之间的联系。并且序列模式 分析时同样也需要由用户输入最小置信度和最小支持度。但前者的侧重点在于分 析数据间的前后序列关系。如，它能发现数据库中形如“在某一段时间内，顾客 购买商品a ，接着购买商品b ，而后购买商品e ”之类的知识，即序列a - 1 3 - c 出 现的频度较高。序列模式分析的任务就是在给定交易序列数据库中，挖掘出在数 据库中出现的高频序列。 ( 5 ) 偏差分析 偏差分析技术用于抽取数据中的偏差或异常，这类偏差或异常通常包括不适 合于标准类的异常、相邻两时间段内信息的改动、处于模式边缘的冗余等。偏差 分析的一个重要特征就是它强以有效地过滤大量的不感兴趣的模式。 ( 6 ) 可视化技术 可视化技术是指用图形、图像的方式来显示知识，是数据挖掘中一种很重要 的技术“”。它拓宽了传统图表的功能，使用户对数据的剖析更清楚。通过可视化 技术可以把数据库中的多维数据变成多种图形，这对提示数据的状况、内在本质 及规律性起到了很大作用。 可视化数据挖掘可以分为数据可视化、数据挖掘结果可视化、数据挖掘过程 可视化和交互式数据可视化挖掘等。 ( 7 ) 粗糙集方法 粗糙集理论( ( r o u g hs e t t h e o r y ) ”谰来描述知识的不精确性和不完全性。粗 糙集的一些理论和方法可用来从数据库中发现分类规则，其基本思想是将数据库 中的属性分为条件和结论属性，对数据库中的一记录根据各个属性的不同属性值 分成相应的子集，然后基于条件属性划分的子集与结论属住划分的子集间的上下 近似关系生成判定规则。 粗糙集方法一与传统的统计及模糊集“”方法不同的是它只依赖数据内部的 知识，用数据之间的关系表示知识的不确定性：而后者需要依赖先验知识对不确 定性进行定量描述，如统计分析中的先验概率、模糊集理论中的模糊度等。用粗 集处理不确定性问题的最大优点在于不需要数据的预先或附加的信息。而且容易 掌握。 1 2 与数据挖掘相关技术 数据挖掘本身是多种技术的综合实现，与相关技术相互依赖又互不相同。 1 2 1 数据仓库 数据仓库( d a t aw a r e h o u s i n g ，d w ) 是面向主题的、集成的、不可更新的( 稳定 性) 、随时间不断变化( 不同时间) 的数据集合，用以支持经营管理中的决策制定 过程。是一个作为决策支持系统和联机分析应用数据源的结构化数据环境“。 这个定义给出了数据仓库的四个特性： ( 1 ) 面向主题 主题是数据归类的标准，每个主题基本对应一个宏观分析领域。 ( 2 ) 集成性 数据进入数据仓库之前，必须迸数据加工和集成。即要对原始数据中的矛盾 之处进行统一，还要将原始数据结构做一个从面向应用向面向主题的主题转变。 ( 3 ) 稳定性 指数据仓库反映的是历史数据的内容，而不是日常事务处理产生的数据，数 据经加工和集成进入数据仓库后很少修改或根本不修改。 ( 4 ) 不断变化性 数据仓库是不同时间的数据集合，它要求数据仓库中的数据保存时限能满足 进行决策分析的需要，而且数据仓库中的数据都要标明数据的历史时期。数据仓 库随时间变化不段增加新的数据内容以及删除旧的内容。 数据仓库是利用计算机和数据库技术的最新发展，把整个企业中不同地理位 置、不同存储格式和不同通信方式的数据按一定要求集成在一起，并能把当前使 用的业务信息分离出来，保证关键任务的联机事务处理应用的安全性和完整性， 同时可以访问各种各样的数据库。数据仓库不是单一的产品，而是由软硬件技术 组成的环境。它把各种数据库( 源数据库) 集成为一个统一的数据仓库( 目标数据 库) ，并且把各种数据转换成面向主题的格式，能从异构的数据源中定期抽取、 转换和集成所需要的数据，便于最终用户访问，并能从历史的角度进行分析，最 后做出战略决策。 数据仓库并非是一个仅仅存储数据的简单的信息库，而是一个“以大型数据 管理信息系统为基础，附加在这个数据库系统之上并存储了从企业所有业务数据 库中获取的综合数据并能利用这些综合数据为用户提供经过处理后的有用信息 的应用系统”。如果说传统数据库系统的重点是快速、准确、安全、可靠地将数 据存进数据库的话，数据仓库的重点则是能够准确、安全、可靠地从数据库中取 出数据，经过加工转换成有规律信息之后，再供管理人员使用。 数据仓库作为一个系统，从理论上应该包含数据仓库、仓库管理和分析工具 3 个基本部分，其结构形式如图所示。 数据仓库用户查询 系数据库 - 管理工具 综合数据 工具 l 。j 抽取、转 c s 工具【 换、装裁 i 当前敦据l 1 数据文件r 0 l a p 元数据库 工具 其他rl i 历史数据j i d m 工具i l、， 数据建模 j 工戽 数据源 仓库管理数据仓库分析工具 图1 2 数据仓库系统结构图 1 2 2 知识发现 数据库中的知识发现 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 s ，k d d ) 是于 1 9 8 9 年出现的，现在比较认可的一个定义是f a y y a d 等给出的，即：数据库中的 知识发现是从数据中识别出有效的、新颖的、潜在有用的，以及最终可理解的模 式的高级过程。 由于数据库技术和机器学习技术的发展以及为了满足人们实际工作的需要， 数据库中的知识发现技术逐渐发展起来。一般将k d d 中进行知识学习的阶段称为 数据挖掘，它是整个数据库的知识发现过程一个非常重要的处理步骤。一般来说， 在工程应用领域中多称数据挖掘，而在研究领域中则多称为数据库中的知识发 现。 1 2 3 联机分析处理 联机分析处理( o n l i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) “”3 ，即共享多维信 息的快速分析。联机分析处理是独立于数据仓库的一种技术概念，其基本思想是 公司的决策者应能灵活地操纵公司的数据，以多维的形式从多方面和多角度来观 察公司的状态并了解公司的变化。数据挖掘与联机分析处理都属于分析型工具， 但两者有关明显的区别。数据挖掘是一种挖掘型工具，它能自动地、有效地从大 量数据中发现潜在的数据模式，作出预测性分析，它是现有的一些人工智能、统 计学等成熟技术在特定的数据库领域中的应用。而联机分析处理是一种自上而 下、不断深入的分析工具。由用户提出问题或假设，o l a p 从上至下深入地提取 关于该问题或假设的详细信息。 1 2 4 客户关系管理 数据挖掘在客户关系管理( c u s t o m e rr e l a t i o n s h i pm a n a g e m e n t ，c r m ) 的应 用，能够提高企业的商业智能，能够为企业获得可靠的信息支持策略和商业决策， 提高企业的竞争优势。 文献“。给出了数据挖掘在c r m 中的应用领域，包括三个方面： ( 1 ) 通过预测客户保留度，保留好的客度； ( 2 ) 通过建立交叉销售模型，标识下一步策略； ( 3 ) 通过建立标识模型，获得潜在客户。 一个好的c r m 系统结构如下图所示，由此也可以看出数据挖掘在c r m 中 的应用关系。数据挖掘是客户关系管理的主要工具，可以独立作为工具，也可以 嵌入在c r m 或数据仓库的展示工具中。 图1 3c r m 系统结构图 1 2 5 与数据挖掘的其它相关技术 另外数据挖掘与人工智能技术、统计分析技术等都有着相应的联系。这两门 学科也都是致力于模式发现和预测。数据挖掘就是利用了统计分析和人工智能技 术的算法及技术，把这些高深复杂的技术封装起来，使人们不用自己掌握这些技 术也能完成同样的功能，并且更专注于自己所要解决的问题。 数据挖掘与这两者的区别主要在于算法对大数据量的适应性，数据挖掘的算 法必须面对大数量数据( 如数1 0 万条记录以上) 有很好的性能。另外数据挖掘是 面向解决工程问题的。 1 3 数据挖掘的应用和发展趋势 1 3 1 数据挖掘的应用 数据挖掘技术旨在发现大量数据中所隐藏的知识，以用来解决“数据丰富、 9 知识贫乏”的问题。近年来随着数据库和网络技术的广泛应用，加上使用先进的 自动数据生成和采集工具，人们所拥有的数据量急剧增加，使数据挖掘技术在科 学研究、金融投资、市场营销、保险、医疗卫生、产品制造业、通信网络管理等 行业已得到应用。 数据挖掘研究具有广泛的应用前景，它可以应用于决策支持，也可应用于数 据库管理系统( d b m s ) 中，数据挖掘作为决策支持的工具，可以用来构造知识 库d b m s 中数据挖掘，可以用于语义查询优化、完整性约束和不一致性检验。在 统计和机器学习领域，有许多数据挖掘系统。有人认为把数据仓库、o l t p 、o l a p 和数据挖掘技术结合是近期数据库发展的个趋势。数据挖掘已广泛应用于统计 学领域、演义逻辑编程作为逻辑编程的一个迅速发展的分支，与数据挖掘有密切 联系。数据挖掘所能发现的知识有：广义知识：反映同类事物共同性质的知识； 特征知识、关联知识：反映事物之间依赖或关联的知识；预测型知识：根据历 史和当前的数据推测未来数据；偏离型知识：揭示事物偏离常规现象。所有这 些知识都可以在不同的概念层次上被发现，随着概念的提升，从微观到中观、 再到宏观以满足不同用户、不同层次的需要。数据挖掘系统已成功地应用于超 大型数据库( v l d b ) 的知识挖掘。它广泛地被用于市场营销、银行业、生产 销售和零售业、制造业、经济业、保险业、政府防卫、医药业、电信业、公司 经营管理、工具、地质、计算机软件和硬件等各个应用方面，本文尝试将地球物 理勘探中获取的重、磁数据，用于关联规则的算法检验。 1 3 2 数据挖掘发展趋势 数据挖掘任务和数据挖掘方法的多样性，给数据挖掘提出了许多挑战性的课 题。数据挖掘语言的设计、高效而有效的数据挖掘方法和系统的开发、交互和集 成的数据挖掘环境的建立和应用数据挖掘技术解决大型应用问题，都是目前数 据挖掘研究人员、系统和应用开发人员所面临的主要问题。数据挖掘的发展趋势： ( 1 )应用的探索m 2 ”：数据挖掘最早应用于零售业和金融业的数据分析。 它是一种功能强大的应用技术，主要为企业和管理人员进行销售和决策提供依 据。目前在保险业、制造业、电信和医学等领域也得到了广泛的应用，并取得 了显著的效果。信息产业的发展为数据挖掘提供了广阔的空间，数据挖掘技术的 应用范围将不断得到拓宽，特别是在生物工程、商业智能、网络服务等领域的 应用将成为新的研究热点。 ( 2 )可伸缩的数据挖掘方法：数据挖掘必须尽可能交互式地、有效地处 理大量数据。由于数据量在不断地激增，因此针对单独和集成的数据挖掘功能 的可伸缩算法显得十分重要。一个重要的方向是所谓基于约束的挖掘 ( c o n s t r a i n t b a s e dm i n i n g ) 2 4 , z 5 3 。它致力于在增加用户交互的同时，如何改进 挖掘处理的总体效率。它提供了额外的控制方法，允许用户说明和使用约束， 引导数据挖掘系统对感兴趣模式的搜索。 ( 3 )数据挖掘与数据库系统、数据仓库系统和w e b 数据库系统的集成 2 6 , z r j ：数据库系统、数据仓库系统和w w w 己经成为信息处理系统的主流，而 数据挖掘系统的理想体系结构是与数据库和数据仓库的紧耦合方式。事务管理、 查询处理、联机分析处理和联机分析挖掘应集成在一个统一框架中。这将保证 数据的可获得性，数据挖掘的可移植性、可伸缩性、高性能以及对多维数据分析 和探查的集成信息处理。 ( 4 )数据挖掘语言的研究“42 “删：在进行数据挖掘时，让挖掘系统自动 挖掘整个大型数据库或数据仓库中隐藏的所有有价值的知识往往是不切实际 的，总是需要在用户的指导下进行有目的的挖掘。这就需要为用户提供一组与数 据挖掘系统通信的语言，可以把这组语言称为数据挖掘语言。这组语言用于说明 用户感兴趣的数据集、要挖掘的知识类型、用于指导挖掘过程的背景知识、模式 评估兴趣度量以及如何显示所发现的知识等等。这组语言使得用户可以在数据挖 掘的过程中与数据挖掘系统进行交互，从不同的角度和深度检查发现结果。研究 专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准 化。 ( 5 )可视化数据挖掘o 。3 “：可视化数据挖掘是从大量数据中发现知识的有 效途径，系统研究和开发可视化数据挖掘技术将有助于推进数据挖掘作为数据分 析的基本工具。目前数据挖掘的可视化仅体现在结果的简单描述，并没有达到 真正意义上的可视化。数据可视化、挖掘过程可视化和结果可视化，将揭开数 据挖掘复杂和神秘的面纱，使其变得更为生动、形象和具体，用户可以随时了解 整个过程的进展情况，减少了行为过程的盲目性。数据和结果的图形展示可以 放大、缩小、平移、旋转和变换角度，使分析人员和用户更加容易理解，这将 大大推动数据挖掘工具在发现知识和数据分析中的应用。因此，加强数据可视化 和知识发现过程的可视化具有重要的理论意义和应用价值。 ( 6 ) 复杂数据类型挖掘的新方法“”。”3 5 ：复杂数据类型挖掘是数据挖掘 中一项重要的前沿研究课题。虽然在地理空间挖掘、多媒体挖掘、时序挖掘、 序列挖掘以及文本挖掘方面取得一些进展，但它们与实际应用的需要仍存在很 大的距离。对此需要进一步的研究，尤其是把针对上述数据类型的现存数据分析 技术与数据挖掘方法集成起来的研究。 ( 7 )w e b 挖掘“3 7 “哪：由于w e b 上存在大量信息，并且w e b 在当今 社会扮演越来越重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上 的数据挖掘服务，将成为数据挖掘中一个最为重要和繁荣的子领域。 ( 8 )数据挖掘中的隐私保护与信息安全“”1 ：随着数据挖掘工具和电信与 计算机网络的日益普及，数据挖掘要面对的一个重要问题是隐私保护和信息安 全。需要进一步开发有关方法，以便在适当的信息访问和数据挖掘过程中确保隐 私保护与信息安全。 1 4 数据挖掘存在的问题 数据挖掘研究和应用所面临的问题是：在数据准备阶段，还没有较好的方法 快速去除或修改噪声数据及处理空缺的数据。在挖掘对象的问题上，数据挖掘需 要面对更大型的数据库、更高的维数和属性间的更复杂关系。很多数据挖掘系统 还没有建立在较先进的数据仓库基础上。 目前数据挖掘系统还不能支持多平台，导致支持的局限性及不易与其它系统 集成；在算法的执行过程中，只考虑算法的实际执行时间过长，而没有考虑算法 的综合因素；多种数据输入形式，在数据挖掘的定义中所提到的数据概念，其范 围