（通信与信息系统专业论文）关联规则算法及其在个性化网站的应用研究.pdf

关联规则算法及其在个性化网站的应用研究 摘要 数据挖掘就是从大量数据中提取和挖掘知识，故又称为数据库知识发现。关联分析 发现关联规则是数据挖掘中最活跃的领域。在很多情况下，用户关心的只是关联规则的 一个子集，因此科研人员引入了约束关联规则的概念。本文对关联规则和约束关联规则 挖掘算法进行了研究和分析，发现基于候选集的约束算法仍有很大的缺陷，主要问题是： 1 需要反复扫描数据库 2 产生丈量的候选集 因此基于候选集的约束算法在挖掘低支持度、长模式的规则时效率低下。本文分析 了这些算法，提出了基于h m i n e 算法的c o n - h m i n e 项目约束算法( c o n s t r a i n t b a s e d h y p c r s t r u c t u r em i n i n g ) ，该算法仅需扫描两遍数据库，并且采用模式增长的方法不产 生候选集；采用c o n h - s t r u c t ( c o n s t r a i n t b a s e dh y p e r - s t r u c t u r e ) 结构存储数据集合， 减少了空间的开销。同时该算法也可以适用于大型数据集，在进行数据集划分时能够有 效地进行空间度量。 通过以上改进，设计出一个较好的、有效的数据挖掘算法，效率有所提高，优化了 关联规则的挖掘。并以此算法为基础设计出一个个性化网站的原型系统并验证了可行 性。 关键词：数据挖掘，关联规则，项目约束，c o n h m i n e 算法，个性化网站 关联规则算法及其在个性化网站的应用研究 a b s t r a c t m i n i n ga s s o c i a t i o n r u l e si sa n i m p o r t a n td a t am i n i n gp r o b l e mw h i c hi s t of i n dt h e i n t e r e s t e d , h i d d e na n du n k n o w nk n o w l e d g et h a tc a nb cd i s c o v e r e df r o ml a r g ed a t a b a s e i n m a n yc a s e s ，t h e u s e r sj u s tc o n c e r nas u b s e to fa s s o c i a t i o nr u l e s ，5 0t h ec o n s t r a i n t - b a s e d a s s o c i a t i o nr u l e sm i n i n gi si n t r o d u c e d a f t e ra n a l y z i n ga n ds t u d y i n gc o n s t r a i n t b a s e dd a t a m i n i n ga l g o r i t h m s ，w e f o u n dt h e r ea r et w op r o b l e m se x i s t i n gi nt h e m ： 1 n e e ds c a nd a t a b a s ef r e q u e n t l y 2 p r o d u c el a r g ec a n d i d a t es e t s s oi t sl o we f f i c i e n c yw h e nt h ea l g o r i t h m sa r eu s e dt om i n el o ws u p p o r tt h r e s h o l d l o n g - p a t t e r n s ，t o s o l v et h e s e p r o b l e m s w ei n t r o d u c ea n a l g o r i t h m c o n - h m i n e ( c o n s t r a i n t b a s e dh y p e r - s t r u c t u r em i n i n g ) w h i c hi s b a s e do nh m i n ea l g o r i t h ma n d p r o d u c e n oc a n d i d a t es e t s o u r a l g o r i t h m u s e sc o n - h s t r u c t ( c o n s t r a i n t - b a s e d h y p e r - s t r u c t u r e ) t os t o r e t r a n s a c t i o n ss oi tc a nr e d u c et h e s p a c eo v e r h e a d a i s o o u r a l g o r i t h m c a nb cf i tf o rl a r g ed a t a b a s e ，i tc a nd i v i d et h ed a t a b a s ea c c u r a t e l y an e wg o o da n de f f i c i e n tc o n s t r a i n t b a s e da l g o r i t h mc a nb ew o r k e do u tb yt h ea b o v e i m p r o v e m e n t i t r e a l i z e do n l yp r o v i d i n gt h ei n t e r e s t e dp a t t e r n sa n di m p r o v ea s s o c i a t i v e m i n i n g w ea l s od e s i g n a p r o t o - s y s t e mo fp e r s o n a l i z ew e b s i t ew h i c hu s et h i sn e w a l g o r i t h m ， a n dv a l i d a t ei t sa c t u a l i z 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 ，c o n s t r a i n t b a s e dm i n i n g ，c o n h m i n e a l g o r i t h m ，p e r s o n a l i z ew e b 关联规则算法及其在个性化网站的应用研究 第一章引言 数据挖掘( d m ，d a t am i n i n g ) 是近几年随着数据库和人工智能发展起来的一门 新兴的数据库技术，简单地说，数据挖掘是从大量数据中提取或“挖掘”知识，在大 量数据中发现数据模式，对商务决策、知识库等做出贡献。信息技：术特别是数据库技 术的发展直接导致了数据挖掘的出现。 1 1 课题背景 2 0 世纪6 0 年代，数据库技术从原始的文件处理演化到复杂的、功能强大的数据 库系统。自7 0 年代以来，数据库系统的研究和开发已经从层次和网状数据库系统发展 到开发关系数据库系统、数据建模工具、索引和数据组织技术。此外，用户通过查询 语言、用户界面优化的查询处理和事务管理，可以方便灵活的访问数据库。联机事务 处理将查询看作只读事务，对于关系技术的发展和广泛地将关系技；托作为大量数据的 有效存储检索和管理的主要工具做出了贡献。 自8 0 年代中期以来，数据库技术的特点是广泛接受关系模型，研究和开发新的功 能强大的数据库系统。有些使用了先进的数据模型，如扩充关系模型、面向对象模型、 对象一关系模型和演绎模型。包括时间的、空间的、多媒体的和科学的数据库、知识库 在内的面向应用的数据库系统百花齐放，涉及分布性、多样性的问题被广泛研究。异 构数据库和基于i n t e r n e t 的全球信息系统，如x , v v x v 也已经出现，并成为信息产业的主 力军。 在过去的3 0 年中，海量数据收集、强大的多处理器计算机等基础技术的发展大大 推动了数据库和信息产业的发展，使得大量数据库和信息存储用于事务管理，信息检 索和数据分析，并且数据仓库技术也走向前台。数据仓库将多个异构数据源在单个站 点以统一的模式组织存储以支持管理决策，包括数据清理、数据集成和联机分析处理 ( o l a p ，o n l i n e a n a l y s i sp r o c e s s ) 。尽管o l a p 工具支持多维分析和决策，对于深层 次的分析，如数据分类、聚类和数据随时间变化的情况仍需要其他技术的支持。 快速增长的海量数据存放在大型和大量的数据库中，对它们的理解已经远远超出 了人的能力。由于缺乏挖掘数据背后隐藏的知识的手段，导致了“信息爆炸但知识缺 乏”的现象。人们希望能够对其进行更高层次的分析，以便更好的利用这些数据。目 前的数据库系统可以很好地实现数据的录入、查询、统计等功能，但无法发现数据中 存在的关系和规则，无法根据现有的数据预测未来的发展趋势。这就带来了对强有力 的分析工具的需求，数据挖掘技术应运而生【1 1 。 一般来说，数据挖掘是一系列从数据库或者数据仓库中发现隐藏、未知的和有趣 关联规则算法及其在个性化网站的应用研究 的信息的过程的总称，包括数据清理、数据集成、数据选择、数据转换、数据挖掘、 模式_ 平估和知识表示，故数据挖掘又称为数据库知识发现( k d d ，i q m w l e d g ed i s c o v e r v i nd a t a b a s e ) 【l 】【2 】【3 l 。数据挖掘的主要功能包括聚类分析、分类和预测、关联分析和数 据演变分析等等。 关联分析是数据挖掘领域的重要分支，该阀题在1 9 9 3 年由a g r a w a l 等人在研究购 物篮问题时提出【钔。关联分析发现关联规则，这些规则展示属性值之间频繁在给定的 数据集中一起出现的条件。随着大量数据不停的收集，许多业界人士对挖掘他们之间 蕴含的关联规则越来越感兴趣。从大量的商务事务纪录中发现有趣的关联关系，可以 帮助许多商务决策的制定，被广泛用于购物篮分析、个性化网站和事务分析等等。 目前关联规则挖掘问题已经引起了数据库、人工智能、统计学、信息检索、可视 化及信息科学等诸多领域的广大学者和研究机构的格外重视，并取得了不少研究成果。 由于关联规则形式简洁，便于解释和理解并可以有效的捕捉数据间的重要关系，因此 从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘领域的一个热点。 1 2 本文的主要工作 本文通过对目前的项目约束关联规则挖掘算法进行了分析与研究，发现一些存在 的问题，并采取以下的措施： 在h m i n e 算法( h y p e r - s t r u c t u r em i n i n g ) 1 4 2 】的基础上提出了数据结构 c o n h s t r u c t 和基于项目约束的c o n h m i n e 算法，按照约束条件裁减数据集，存储到 c o n h s t r u c t 中进行挖掘。 对于不能放到主存中的大型数据集按照划分的方法，分别进行挖掘并最终合并 结果集。 基于该算法设计了一个用于个性化网站的原型系统。 1 3 本文以下各部分的主要内容 在第二章中，介绍了数据挖掘的概念、分类和数据挖掘系统的体系结构，挖掘的 数据模式类型以及数据挖掘在一些领域的应用，还探讨了建立未来的挖掘工具所面对 的问题。 在第三章中，介绍了关联规则的基本概念、挖掘关联规则的基本算法和几种改进 途径，并对评价关联规则的几种方法进行了探讨。 第四章中引入约束尤其是项目约束的概念，以基于经典候选集算法a p r i o r i 的 d i t e c t 项目约束挖掘算法为例，分析说明了现存算法的缺点，并在m m i n e 算法的基础 上提出了基于项目约束的c o n h m i n e 算法，给出了试验的数据和对此算法的评价以 2 关联规则算法及其在个性化网站的应用研究 及改进途径。 在第五章中 并验证其可行性。 在第六章中， 给出了一个使用c o n h m i n e 项目约束算法的个性化网站原型系统 给出了全文的总结和展望。 3 关联规则算法及其在个性化网站的应用研究 第二章数据挖掘技术综述 在过去的几十年中，人类产生和收集数据的能力已经迅速的提高，许多商务、科 学和行政事务的计算机化。以及由文本和图像扫描平台到卫星遥感数据的数据收集工 具的进步，作为全球信息系统的万维网的流行，已经将我们淹没在数据和信息的汪洋 大海中。数据挖掘技术的研究目标就是从大型数据库中挖掘出对用户有价值的模式， 它之所以引起信息界的广大关注，正是由于存在广泛可用的数据，：并且迫切需要先进 的技术和工具将海量数据转换成信息和知识，从而帮助商务管理、生产控制、市场分 析和卫星数据处理等应用。 通过研究数据挖掘，为决策者提供重要的有价值的信息和知识可以带来不可估 量的效益。数据挖掘出现于2 0 世纪8 0 年代后期，在9 0 年代有了突飞猛进的发展，并 可望在新千年继续繁荣。 2 1 数据挖掘的概念 确切地讲，数据挖掘是一种决策支持过程，主要基于a i 、统计学等。数据挖掘高 度自动化的分析存储的数据，做出归纳性的推理，从中挖掘出潜在的模式，预测目标 的发展。从而帮助决策者调整策略，做出正确的决策，减少风险。数据挖掘可看作数 据库中的知识发现( k d d ) 。 在k d d 9 6 国际会议上，k d d 被定义为：对数据库中蕴涵的、：表知的、有潜在应 用价值的、非平凡的模式的提取【”。其中，“模式”是指用高级语言表示的表达一定逻 辑含义的信息。通常指数据库中数据之间的逻辑关系( 即要发现的知识) 。而“非平凡” 则是指在k d d 中，知识的发现过程应具有某种不确定性和一定的自由度。对于能够 以确定的计算过程提取的模式( 如在人事数据库中，已知职工的工资，求出职工的总 工资或平均工资等问题) ，一般称之为平凡知识，而平凡知识不是k d d 的目标。也就 是说，数据挖掘是从一些事实和观察数据的集合中寻找模式和规则的过程，它是一个 发现过程，是运用一种数据处理引擎帮助我们理解有关数据的具体含义，并了解数据 之间所存在的内在联系。通过数据挖掘有价值的知识和规则或者高层的信息就能从大 型的数据库的相关集合中被抽取出来，并从不同的角度显示，从而把大型数据库变为 一个丰富可靠的资源为知识归纳服务。 数据挖掘是一个年轻的跨学科领域，源于诸如数据库系统、数据仓库、人工智能、 信息提取和高性能运算。其他做出贡献的领域包括神经网络、模式识别、空间数据分 析、图像数据库、信号处理，其中也包括商务、经济和生物信息学等。 4 关联规则算法及其在个性化刚站的应用研究 2 2 数据挖掘的功能和方法 数据挖掘的功能用于制定数据挖掘任务中要找的模式类型。数据挖掘一般可分为 两类：描述和预测。描述性挖掘刻画数据库中数据的一般特性；预测性数据挖掘则在 当前数据上进行推断，以进行预测。 数据挖掘是一个交叉学科领域，受多个学科影响( 见图2 1 ) ，包括数据库系统、 统计学、机器学习、可视化和信息科学。 数据挖掘是数据库技术的自然延伸和发展，它建立在已有的数据库技术基础之上。 而通常采用的方法可以分为两大类：一类是统计学方法，常用的技术有概率分析、相 关性、聚类分析和判别分析等；另一类人工智能中的机器学习方法，常用的如判定树、 神经网络等。同时信息科学中的许多成熟方法也被应用到数据挖掘中，比如租键集和 模糊集方法可用于分类，以及基于网格的各种聚类算法等等。数据挖掘使用了统计学、 机器学习和信息学的若干概念，比如支持度、置信度和信息熵等。可视化技术应用在 数据挖掘中，可以直观的表示数据，使人们能够快速的指导挖掘过程，理解挖掘结果。 此外，依赖于所挖掘的数据类型或给定的数据挖掘应用，数据挖掘系统也可能集成空 间数据分析、信息检索、模式识别、图像分析、信号处理、计算机图形学、w e b 技术、 经济、商业、生物信息学或心理学领域的技术。 图2 1 对数据挖掘有影响的学科 2 2 1 概念描述：特征化和区分 在很多情况下数据都与某个概念和类相关联。例如学校的选课系统中。课程类包 括数据结构、操作系统等，学生类包括计算机系学生、电子系学生等等。用汇总的简 洁精确的方式描述某个类和概念在这些情况中是有用的，这种描述可以通过以下方法 得到： 关联规则算法及其在个性化网站的应用研究 1 数据特征化 数据特征化是目标类数据的一般特性或特征的汇总。有许多有效的方法可以将数 据特征化和汇总，比如给予数据立方体的o l a f 上卷操作，面向属性的归纳技术等等。 2 数据区分 数据区分是将目标类对象的一般特性与一个或多个对比类对象的一般特性相比 较，目标类和对比类由用户指定，而对应的数据通过数据库查询检索。 2 2 2 关联分析 关联分析发现关联规则，这些关联规则展示属性值频繁的在给定的数据集中一起 出现的条件。更形式的说，个关联规则是形如xy 即“a 1 a a mb l a b n ” 的规则，其中a i ( i 1 ，m t ) ，b i ( j 1 ，n ) 是属性值对。关l 茨规则z l r 解释 为“满足x 中条件的数据库元组在一定程度上也满足l ，中的条件”。一个以上的属性 或谓词之间的关联称为多维关联规则，单个谓词的关联规则称为单维关联规则。有了 这样的规则我们就可以对其中的一项的属性根据其他相关联的属性进行预测。 关联分析中的常用算法有候选集算法和非候选集算法两大类。候选集算法有 a p r i o r i 4 】算法以及许多基于a p r i o r i 的改进算法，比如a p r i o r f f i d 算法和使用哈希技术 改进的a p r i o r i 算法。非候选集算法不产生候选集，包括采用模式增长技术的 f p g r o w t h 3 5 】和h m i n e 4 2 】算法等等。为了有效的评价关联分析的结果，还引入了置信 度和支持度的统计学概念，有的科学家还引入了相关支持度来评价关联分析的结果。 2 2 3 分类和预测 分类找出并区分数据类或概念的模型( 或函数) ，以便能够用模型预测类标记未知 的数据对象，导出模型是基于对训练数据集( 即其类标记已知的数据对象) 的分析， 导出模型可以有多种形式的表示方法，如分类规则、判定树、数学公式或者神经网络。 分类可用来预测数据对象的类标记。在某些情况中，需要预测某些空缺的值或者 未知的数据值，在预测的值是连续值时( 通常使用回归方法) ，通常；际之为预测。 分类借鉴了很多机器学习、统计学和信息科学中成熟的技术和思想，比如决策树、 神经网络、遗传算法等等。 决策树是一个类似流程图的树结构，每个节点代表一个属性值上的测试，每个分 支代表一个输出，树叶代表类或者类分布。要建立决策树，可以利用信息论中的信息 熵寻找数据库中具有最大信息量的字段，建立决策树的一个结点，再根据字段的不同 取值建立树的分支；在每个分支子集中再重复上述过程。决策树容易转换成分类规则。 国际上最有影响和最早的决策树算法是q u f u l a n 研制的i d 3 方法，此后又发展了各种 6 关联规则算法及其在个性化网站的应用研究 决策树方法，如i b i e 方法和c h a i d 等，c h a i d 得到了广泛使用。 扭经网络最早由心理学家和神经生物学家提出，鲁在寻求开发和测试神经的计算 模拟。典型的神经网络模型主要分三大类，其中以感知机、b p 反向传播模型、函数型 网络为代表的前馈式神经网络模型，主要用于分类、预测和模式识别。神经网络的最 大优点是它能精确地对复杂问题进行预测，使用神经网络的预测( 具有连续数值结果) 技术在金融市场和制造业被广泛采用。 遗传算法是一种模拟生物进化过程的算法，由3 个基本算子组成：繁殖( 选择) ； 交叉( 重组) ；变异( 突变) 。这种遗传算法可以起到产生优良后代的作用。这些后代 需满足适应度量值，经过若干代的遗传，将得到满足要求的后代( 问题的解) 。遗传算 法通常和神经网络联合使用，两者结合之后，可直接将输入变量组记录到数据库中， 从而可为每一种神经网络模型提供更详细的文档。用各种模型实验：艺后，通过从数据 库中读出以前模型的变量集，即可以建立最终模型。 贝叶斯分类是统计学分类算法，它基于贝叶斯定理，可以预测类成员关系的可麓 性，包括朴素贝叶斯分类和贝叶斯信念网络等方法。其他的分类算法还有k 最l i 缶近分 类、基于案例推理、粗糙集和模糊集的算法。而线性回归和多元回归、非线性回归等 回归模型常用来进行预测。 2 2 4 聚类分析 与分类和预测不同，聚类在不考虑己知类标记的情况下分析数据。通常训练数据 对象不提供类标记，聚类可以产生这种类标记，数据对象根据最大化类内的相似性、 最小化类间的相似性的原则进行聚类或分组。所形成的每个聚类可以看作一个对象类 由它可以导出规则。聚类也便于分类编制( t a x o n o m yf o r m a t i o n ) ，将观察到的内容组 织成分层类结构，把类似的事件组织在一起。 聚类常用的算法分为几类。包括基于划分的方法，如k 中心点和k - 平均算法；基 于层次的方法，如b i r c h 算法利用层次方法的平衡迭代规约和聚类，c u r e 算法利用 代表点聚类，变色龙算法使用动态模型的层次聚类；其他的还有基于密度的方法和基 于网格的方法等等。统计学方法也可以应用在聚类中，c o b w e b 就是一种流行的简单 增量概念的聚类算法，它以一个分类树的形式创建层次聚类：以a r t 模型、k o h o n e n 模型为代表的神经网络方法，可以用于聚类的自组织映射。这两种方法都是基于模型 的方法。 2 2 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致，这些数 关联规则算法及其在个性化网站的应用研究 据对象称为孤立点( o u t l i e r ) ，大部分数据挖掘方法将孤立点视为噪声或异常而丢弃。 然而在1 些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那些更有趣，孤立点 数据分析称作孤立点挖掘( o u t l i e rm i n i n g ) 。 孤立点可以使用统计试验检测。它假定一个数据分布或概率模型，并使用距离度 量，到其他聚类的距离很大的对象被视为孤立点。基于偏差的方法通过考察一群对象 主要特征上的差别识别孤立点，而不是使用统计或距离度量。 2 2 6 数据演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的数据的规律或趋势并对 其建模。这可能包括时间相关数据的特征化、区分、关联、分类或聚类，主要有时间 序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 2 3 数据挖掘的过程 数据挖掘主要完成数据采集、预处理、数据分析和结果表述一系列任务。根据功 能，一般数据挖掘可概括分为以下步骤： 1 数据准备 又可细分为以下几个步骤：数据选择；数据清洗；数据变换和集成：数据预分析。 1 ) 数据选择，根据数据挖掘的目标建立目标数据集。 2 ) 数据清洗，填写空缺的值，平滑噪声数据，识别删除孤立点，消除二义性数据。 3 ) 数据变换和集成，将数据转换成适于挖掘的统一格式，并将不同数据源的数据 整合成统一的数据存储。 通过对数据样本的筛选，可以减少数据处理量，节省系统资源，使数据更具规律 性。 2 数据预分析 数据预分析用来缩小数据的范围，可以提高挖掘的质量。通常需要对数据进行深 入调查，从样本数据集中找出规律和趋势，用聚类分析区分类别，目的是搞清多因素 相互影响、十分复杂的关系，发现因素之间的相关性。通过上述的操作对数据的状态 和趋势有了进一步的了解，尽可能对问题解决的要求能进一步明确和量化。 数据准备和预处理的工作非常重要，其工作量占到整个k d d 过程的6 0 v 2 上。 3 数据挖掘 数据挖掘根据挖掘目标综合利用关联分析、数据序列分析、分类和聚类分析挖掘 选择合适的算法分析数据，是k d d 中最基础的部分。 关联规则算法及其在个性化网站的应用研究 4 数据表述 数据表述将数据挖掘获得的信息以便于用户理解和使用的方式反映给用户。根据 用户要求的不同，数据挖掘的表述层需要消除对用户无效的模式，利用可视化工具帮 助用户理解结果或者将结果存储在知识库中以便加以进一步的分析和利用。 5 评价 从上述过程中将会得出一系列的分析结果、模式和模型，通常可得到对目标问题 多方面的描述，这时就要综合它们的规律性，提供合理的决策支持信息。评价可以直 接使用原先建立模型的样本数据或者使用另一批已知能反映客观规律性的数据对其进 行检验；还可以在实际运行的环境中取出新数据进行检验。 整个k d d 的过程如图2 2 所示。 2 4 数据挖掘的分类 图2 2 数据挖掘的过程 由于数据挖掘源于多个学科，因此数据挖掘研究就产生了大量的、各种不同类型 数据挖掘系统。这样，就需要对数据挖掘系统给出一个清楚的分类。这种分类可以帮 助用户区分数据挖掘系统，确定最适合其需要的数据挖掘系统。根据不同的标准，数 据挖掘系统可以分类如下： 关联规则算法及其在个性化网站的应用研究 1 根据挖掘的数据库类型分类 数据挖掘系统可以根据挖掘的数据库类型分类。数据库系统本身可以根据不同的 标准( 如数据模型或数据或所涉及的应用类型) 分类，每一类可能需要自己的数据挖 掘技术，数据挖掘系统就可以相应分类。 例如，如果根据数据库模型分类，我们可以有关系的、事务的、面向对象的、对 象一关系的或数据仓库的数据挖掘系统。如果根据所处理的数据的特定类型分类，我们 有空间的、时间序列的、文本的或多媒体的数据挖掘系统，或w w w 数据挖掘系统。 2 根据挖掘的知识类型分类 数据挖掘系统可以根据所挖掘的知识类型分类，即根据数据挖掘的功能，如特征 化、区分、关联、分类聚类、孤立点分析和演变分析、偏差分析、类似性分析等分类。 一个全面的数据挖掘系统应当提供多种和，或集成的数据挖掘功能。 此外，数据挖掘系统可以根据所挖掘的知识的粒度或抽象层进行区分，包括概化 知识( 在高抽象层) ，原始层知识( 在原始数据层) ，或多层知识( 考虑若干抽象层) 。 一个高级数据挖掘系统应当支持多抽象层的知识发现。 数据挖掘系统还可以分类为挖掘数据规则性( 通常出现的模式) 和数据不规则性 ( 如异常或孤立点) 。一般地，概念描述、关联分析、分类、预测和聚类挖掘数据规律， 将孤立点作为噪声排除。这些方法也能帮助检测孤立点。 3 根据所用的技术分类 数据挖掘系统也可以根据所用的数据挖掘技术分类，这些技术可以根据用户交互 程度( 例如自动系统、交互探查系统、查询驱动系统) ，或所用的数据分析方法( 例如 面向数据库或数据仓库的技术、机器学习、统计学、可视化、模式识别、神经网络等) 描述。复杂的数据挖掘系统通常采用多种数据挖掘技术，或采用有效的、集成的技术， 结合多种方法的优点。 4 根据应用分类 数据挖掘系统可以根据其应用分类。例如，可能有些数据挖掘系统特别适合金融、 电信、d n a 、股票市场、e - m a i l 等等。不同的应用通常需要集成对于该应用特别有效 的方法。因此普通的、全能的数据挖掘系统可能并不适合特定领域的挖掘任务。 2 5 数据挖掘的应用 目前数据挖掘可以在很多重要的领域发挥积极作用，尤其是在银行、电信、保险、 交通、零售( 如超级市场) 等商业应用领域。数据挖掘能够帮助解决许多典型的商业 问题，其中包括：数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分( c u s t o m e r s e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、背景分析( p r o f i l e a n a l y s i s ) 、交叉销售( c r o s s - s e l l i n g ) i 0 关联规则算法及其在个性化网站的应用研究 等等。 擞据挖掘技术在企业市场营销中得到了比较普遍的应调，它是以市场营销学的市 场细分原理为基础，假定消费者过去的行为是其今后消费倾向的最好说明。数据挖掘 通过收集、j j 口- r 和处理涉及消费者消费行为的大量信息，确定特定消费群体或个体的 兴趣、消费习惯和消费需求，进而推断出相应消费群体或个体下一步的消费行为，然 后以此为基础对所识别出来的消费群体进行特定内容的定向营销。这与传统的不区分 消费者对象特征的大规模营销手段相比，大大节省了营销成本，提高了营销效果，从 而为企业带来更多的利润。 商业消费信息来自市场中的各种渠道。例如：每当我们用信用卡消费时，商业企 业就可以在信用卡结算过程中收集商业消费信息，记录下我们进行消费的时间、地点、 感兴趣的商品或服务、愿意接收的价格水平和支付能力等数据；当我们在申办信用卡、 办理汽车驾驶执照、填写商品保修单等其他需要填写表格的场合时，我们的个人信息 就存入了相应的业务数据库；企业除了自行收集相关业务信息之外，甚至可以从其他 公司或机构购买此类信息为自己所用。这些来自各种渠道的数据信息被组合，应用超 级计算机、并行处理、神经元网络、模型化算法和其他信息处理技术手段进行处理， 从中得到商家用于向特定消费群体或个体进行定向营销的决策信息。 其它数据挖掘系统的应用有： 1 在生产制造领域 数据挖掘协助管理大数量变量之间的相互作用，并能自动发现出：某些不正常的数 据分布揭示制造和装配操作过程中变化情况和各种因素，从而协助质量工程师很快 地注意到问题发生范围和采取改正措施。 2 在远程通讯方面 基于数据挖掘的分析协助组织策略变更以适应外部世界的变化，确定市场变化模 式以指导销售计划。在网络容量利用方面，数据挖掘能提供对客户聚集服务使用的结 构和模式的了解，从而指导容量计划人员对网络设施做出最佳投资决策。 3 在其他企事业部门 数据挖掘在假伪检测及险灾评估、失误回避、资源分配等很多方面，起着很重要 作用例如在化学及制药行业，将数据挖掘用于巨量生物信息可以发现新的有用化学 成分【1 5 】【1 6 | ；在遥感领域针对每天从卫星上及其它方面来的巨额数据，对气象预报、臭 氧层监测等能起很大作用f 17 】【1 8 j 【1 9 】。 4 在w e b 个性化服务方面 随着互联网信息资源的快速增长，仅靠信息搜索引擎等服务已很难满足人们的信 息服务要求a 将数据挖掘技术应用到网站中，分析和处理用户的浏览过程、次数等各 种信息，使用分类和聚类技术划分用户群。针对不同用户群的行为，综合使用关联分 1 1 关联规则算法及其在个性化网站的应用研究 析、时间序列分析等手段，可以实现对用户的个性化w e b 服务。个性化网站系统根据 用户特征从为数众多的网站自动搜索信息资料，从相关的w e b 网页抽取信息并与当前 网站进行有效综合，使用户能够最大程度的尽快得到用户感兴趣的内容，满足用户的 个性化信息需求。 5 新的应用领域 近年来，数据挖掘在许多新的应用领域蓬勃发展，国内也对此进行了大量的研究。 比如在水电站数字化工程中。老式系统仅为简单的信息查询或数据报表产生系统， 功能极为有限，数据挖掘技术和知识发现技术可以为水电站的优化运行提供必要的、 足够的信息和数据支持，为解决上述问题提供了新的方式【2 。j 。 在远程教育系统中在实行实时教学时，与高速发展的互联网技术、人工智能和数 据库技术相结合，数据挖掘技术通过机器学习、统计分析等方法，设计出个性化处理 引擎，使个性化服务成为可能，并成为目前的远程教育的支撑技术【2 1 1 1 2 2 1 。 从农业环境监测各种数据源提取相关数据，建立数据仓库，在数据仓库之上进行 数据挖掘分析，可以发现各环境要素和制约因子之间的关联，进而提出具有针对性的 解决方案，提高环境主管部门的决策预警能力吲。 数据挖掘技术还可应用在温室作物生长预测中，运用数据挖掘技术来预测作物生 长一方面可以节省大量的人力、物力，另一方面可以很好地控制作物的生长【2 4 1 ， 在官方统计、人口数据分析等应用领域，把数据挖掘技术中的分类、聚类及孤立 点分析等应用到审计风险管理中，不仅减轻审计人员的负担。而且可以提高审计风险管 理的质量i z 5 l “。 在设计网络入侵检测系统时，将数据挖掘技术应用于入侵检测能够广泛地收集审 计数据来计算模型，从而精确地捕获实际的入侵和正常行为模式。这种自动化的方法 无斋手工分析和编码入侵模式，不再象以前一样凭经验来选择统计方法。它更主要的 优点是相同的数据挖掘工具可应用于多个数据流，有利于建造自适应的入侵检测系统 【2 7 1 【2 8 1 。 2 6 数据挖掘的问题 本节提出数据挖掘的主要问题，包括挖掘方法与用户交互问题、性能问题和数据 类型的多样性阀题。 2 6 1 挖掘方法和用户交互问题 挖掘方法和用户交互问题是数据挖掘是否成功应用的关键问题，反映了所挖掘的 知识类型、在多粒度上挖掘知识的能力、领域知识的使用、特定的挖掘和知识显示。 关联规则算法及其在个性化网站的应用研究 1 在数据库中挖掘不同类型的知识 由于不同的用户可能对不同类型的知识感兴趣数据挖掘系统应当覆盖范围很广 的数据分析和知识发现任务，包括数据特征化、区分、关联、分类、聚类、趋势和偏 差分析以及相似性分析。这些任务可能以不同的方式使用相同的数据库，并需要开发 大量数据挖掘技术。 2 多个抽象层的交互知识挖掘 由于很难准确地知道能够在数据库中发现什么，数据挖掘过程应当是交互的。对 于包含大量数据的数据库，应当使用适当的抽样技术进行交互式数据探查。交互式挖 掘允许用户聚焦搜索模式，根据返回的结果提出和精炼数据挖掘请求。特殊地类似于 o l a p 在数据立方体上的操作，应当通过交互地在数据空间和知识空间下钻( r o l l u p ) 、 上卷( d r i l l - d o w n ) 和转轴( p i v o t ) 来挖掘知识。用这种方法用户可以与数据挖掘系统 交互，以不同的粒度以及从不同的角度观察数据和发现模式。 3 结合背景知识 可以使用背景知识或关于所研究领域的信息来指导发现过程，并使得发现的模式 以简洁的形式在不同的抽象层表示。关于数据库的领域知识，如完整性约束和演绎规 则，可以帮助聚焦和加快数据挖掘过程，或评估发现的模式的兴趣度。 4 查询语言和特定的数据挖掘 关系查询语言( 如s q l ) 允许用户提出特定的数据检索查询。与之相似，我们需 要开发高级数据挖掘查询语言( d m q l ，d a t am i n i n gq u e r yl a n g u a g e ) ，使得用户通过 说明分析任务的相关数据集、领域知识、所挖掘的数据类型、被发现的模式必须满足 的条件和约束，描述特定的数据挖掘任务。这种语言应当与数据库或数据仓库查询语 言集成，并且针对有效的、灵活的数据挖掘进行优化。 5 数据挖掘结果的表示和显示 发现的知识应当用高级语言、可视化表示或其他表示形式表示，使得知识易于理 解，能够直接被人们使用，这一点对交互式数据挖掘系统尤为重要。这要求系统采用 有表达能力的知识表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线。 6 处理噪声和不完全数据 存放在数据库中数据可能反映噪声、异常情况或不完全的数据对象。这些对象可 能干扰分析过程，导致数据与所构造的知识模型过分适应，其结果是所发现模式的精 确性可能很差。所以要进行处理数据噪声的数据清理方法和数据分析方法，以及发现 和分析异常情况的孤立点挖掘方法的研究。 1 3 关联规则算法及其在个性化网站的应用研究 7 模式评估一兴趣度问题 数据挖掘系统可能发现数以千计的模式，对于给定的用户，许多模式不是有趣的， 它们表示公共知识或缺乏新颖性。关于开发模式兴趣度的评估技术，特别是关于给定 用户类，基于用户的信赖或期望，评估模式价值的主观度量，仍然存在一些挑战。使 用兴趣度度量指导发现过程和压缩搜索空间，是又一个活跃的研究方向。 2 6 2 性能问题 为了有效地从数据库的大量数据中提取信息，数据挖掘算法必须是有效的。换句 话说，对于大型数据库，数据挖掘算法的运行时间必须是可预计和可接受的，从数据 库角度，有效性是数据挖掘系统实现的关键问题。上面讨论的挖掘方法和用户交互的 大多数问题，也必须考虑有效性。 许多数据库的大容量、数据的广泛分布和一些数据挖掘算法的计算复杂性是促使 开发并行和分布式数据挖掘算法的因素。这些算法将数据划分成各部分，这些部分可 以并行处理，然后合并每部分的结果。此外，有些数据挖掘过程的高花费导致了对增 量数据挖掘算法的需要。增量算法与数据库更新结合在一起，而不必重新挖掘全部数 据。这种算法渐增地进行知识更新，修正和加强已发现的知识。 2 6 3 关于数据库类型的多样性问题 1 关系的和复杂的数据类型的处理 由于关系数据库和数据仓库已经广泛使用，对它们开发有效的数据挖掘系统是重 要的。然而，其他数据库可能包含复杂的数据对象、超文本和多媒体数据、空间数据、 时间数据或事务数据。由于数据类型的多样性和数据挖掘的目标不同，指望一个系统 挖掘所有类型的数据是不现实的。为挖掘特定类型的数据，应当构造特定的数据挖掘 系统。这样，对于不同类型的数据，我们可能有不同的数据挖掘系统。 2 由异构数据库和全球信息系统挖掘信息 局域网和广域网( 如i n t e m e t ) 连接了许多数据源，形成了庞大的、分布式的和异 构的数据库。从具有不同数据语义的结构化的、半结构化的和非结构化的不同数据源 发现知识，对数据挖掘提出了巨大挑战。数据挖掘可以帮助发现多个异构数据库中的 数据规律，这些规律通常难以被简单的查询系统发现，并可以改进异构数据库的信息 交换和互操作性。i n t e r n e t 的普及，使得如何在i n t e m e t 的海量数据中发现知识变得至 关重要。关于w e b 内容、w e b 使用和w e b 动态情况的有趣知识，已经成为数据挖掘 的一个非常具有挑战性的领域。 1 4 关联规则算法及其在个性化网站的应用研究 以上问题是数据挖掘技术未来发展的主要需求和挑战。在近来的数据挖掘研究和 开发中，一些挑战已受到一定程度的关注，并考虑到了各种需求，而另一些仍处于研 究阶段。然而，这些问题将继续激励进一步的研究和改进。 关联规则算法及其在个性化网站的应用研究 第三章常用关联规则挖掘算法 关联规则挖掘就是从大量的数据中挖掘出有价值的、描述数据项之间相互联系的 有关知识。随着收集和存储在数据库中的数据规模越来越大，人们对从这些数据中挖 掘相应的关联知识越来越有兴趣。 关联规则挖掘由a g r a w a l 等人对市场购物篮分析( m a r k e tb a s k e t a n a l y s i s ) 时首先 提出i ”，用以发现商品销售中的顾客购买模式。关联规则可以发现存于数据库的项目 ( i t e m s ) 或属性( a t t r i b u t e s ) 间的有趣的关系，这些关系是预先未知的和隐藏的，也 就是说不能通过数据库的逻辑操作( 例如表的连接) 或统计的方法得出。这说明他们 不是基于数据库本身的固有属性( 如函数依赖关系) ，而是基于数据库中数据项目的同 时出现的特征，所发现的关联规则可以辅助人们进行市场运作( m a x k e t i n g ) ，决策支 持( d e c i s i o ns u p p o f t ) ，及商业管理( b u s i n e s sm a n a g e m e n t ) 和网站设计( w e bs i t ed e s i g n ) 等等。 目前关联规则挖掘问题已经引起了数据库、人工智能、统计学、信息检索、可视 化及信息科学诸多领域的广大学者及研究机构的格外重视，并取得不少的研究成果。 由于关联规则形式简洁、易于解释和理解并可以有效捕捉数据问的重要关系，因此从 大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘领域的一个热点。 3 1 关联规则的基本概念和问题描述 设k i 1 ，i 2 ，i 。 是二进制文字的集合，其中的元素称为项( i t e m ) 。记d 为交易 ( t r a n s a c t i o n ) 的集合，这里交易r 是项的集合，并且延了。对应每一个交易有唯一 的标识，如交易号，记作t i d 。设x 是一个，中项的集合如果艇：r ，那么称交易丁 包含x 。 一个关联规则是形如j y 的蕴涵式，这里x c i , y c i ，并且船1 阽中。z 称为规则 的前提，y 称为规则的结果。 为了进一步说明关联规则的支持率和正确程度，人们引入了支持度和置信度两个 概念。 定义1 ： 规则转，】，在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交易 数与所有交易数之比，记为s u p p o r t ( 盖j y ) ，即 s u p p o r t ( 五；y ) = i p 矾j y e 丁，r e _ o l p 9 i 关联规则算法及其在个性化网站的应用研究 定义2 ： 规则j ，l ，在交易集中的置信度( c o n f i d e n c e ) 是指包含x 和1 ，的交易数与包含x 的交易数之比，记为c o n f i d e n c e ( y ；y ) ，即 c o n f i d e n c e ( 轴y ) = i ax u i 匹_ t ，廷虫) | l 凡埏：r ，廷西 l 定义3 ： 事务数据库上的关联规则x y 的支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 同 时满足最小支持度闽值( m i n _ s u p ) 和最小置信度阈值( r a i n c o n f ) 时，称关联规则 x y 为强关联规则。 例3 1 ：以下是一个关联规则的例子 a g e ( t ，”2 0 3 9 ”) a n dr o l e ( t ，”学生”) p r o d u c ti t , ”m p 3 播放器”) 此处t