（计算机应用技术专业论文）关联规则数据挖掘方法的研究和应用.pdf

摘要 摘要 随着信息技术的发展，数据挖掘技术得到了广泛的关注。在数据挖掘技术 中有很多研究领域，关联规则数据挖掘就是其中一个重要的研究方向，对它进 行深入研究不仅有着重要的理论意义，而且有着重要的应用价值。关联规则数 据挖掘于1 9 9 3 年由a g r a w a l 等人提出，它最初是以分析事务数据库中项与项之 间联系为目标，后来的研究者们对问题原型进行多方面的改进和扩充。目前， 关联规则挖掘技术已经被应用到商业、电信、金融、农业、医疗等领域，并取 得了良好的效果。 关联规则挖掘算法是关联规则数据挖掘研究中的主要内容之一，迄今为止 己提出了多种关联规则挖掘算法，其中最著名的是a g r a w a l 提出的a p r i o r i 算法。 a p r i o r i 算法属于间接挖掘算法，它挖掘的是事务数据库中的全部关联规则，然 而在实际应用中，企业关心的可能是与该公司某一产品或新推出的产品相关的 关联规则，因此基于固定目标项目的挖掘具有一定的实用价值。本文在a p r i o r i 算法的基础上提出了一种适合目标项目挖掘的算法i b d f m i n e r 算法，同时针 对a p r i o r i 算法的不足之处也作了一些改进，算法以改进的位图数据格式为存储 结构，使得支持度的计算简单方便，而不再需要反复扫描数据库，并通过对位 图矩阵的相应处理有效缩小了频繁项目集的生成空间，实验证明该算法有较好 的执行效率。 根据规则涉及的维数关联规则可分为两种：单维关联规则和多维关联规则。 由于关系数据库是数据挖掘最流行、最丰富的数据源，而关系数据库中隐含的 关联规则通常具有多维性，因此本文对多维关联规则的挖掘算法进行了些研 究。传统的多维关联规则挖掘方法是将分类属性和量化属性进行离散化处理后 采用成功的单维布尔关联规则挖掘算法进行挖掘，本文尝试直接对多维数据利 用标准s q l 语言来进行多维关联规则挖掘，算法的核心是利用s q l 语言的查 询和多表连接等语句对数据库进行操作，完成频繁谓词集和强规则的搜索过程。 在以上研究的基础上，本文将多维关联规则具体应用于道路交通事故数据 4 挖掘中，从记录交通事故的数据库中发现有价值的规律。针对道路交通事故数 关联规则数据挖掘方法的研究和应用 据特点，本文提出了基于约束规则后件的关联规则挖掘算法，并将算法用于交 通事故中“人、车、路”等因素对事故产生的影响的分析研究，得出了一些有 实际意义的结论，这些结论与当地交警的经验基本上是一致的，根据这些结论 可以采取针对性措施，用于辅助交通管理部门对今后的道路交通安全的改进工 作，以预防和减少事故发生，保障人们的生命和财产的安全。 关键词：数据挖掘；关联规则；目标项目；多维关联规则；s q l 语言；道路交 通事故 i i a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，d a t am i n i n gh a sb e e np a i d a t t e n t i o ne x t e n s i v e l y a sw ek n o w , d a t am i n i n gh a sal a r g er e s e a r c hs c o p e ， a s s o c i a t i o nr u l e sd a t am i n i n gi so n eo fi m p o r t a n tr e s e a r c hs u b je c ti ni t d e e p l y r e s e a r c h i n gi n t ot h es u b j e c th a sm o s ti m p o r t a n tv a l u e sn o to n l yo nt h e o r e t i cb u ta l s o o na p p l i c a t i o n s a s s o c i a t i o nr u l e sm i n i n gi sa d v a n c e db ya g r a w a la n dt h eo t h e ri n 19 9 3 ，f i r s tt h ep u r p o s ei sa n a l y z i n gt h er e l a t i o no fi t e m si nt r a n s a c t i o nd a t a b a s e ， l a t e r , i n v e s t i g a t o ri m p r o v e da n de x t e n d e dt h ep r o t o t y p eo fq u e s t i o n a tp r e s e n t ， a s s o c i a t i o n r u l e st e c h n o l o g yh a sb e e na p p l i e dt ob u s i n e s s ，t e l e c o m m u n i c a t i o n ， f i n a n c e ，a g r i c u l t u r e ，m e d i c a lt r e a t m e n ta n ds oo n i th a sb r o u g h ta ng o o de f f e c t i nt h er e s e a r c ho fa s s o c i a t i o nr u l e sd a t am i n i n g ，t h ea l g o r i t h m sr e s e a r c hi si t s i m p o r t a n tp a r tf o rm i n i n ga s s o c i a t i o nr u l e s m a n ya l g o r i t h m si nt h ef i e l dh a v eb e e n p u tf o r w a r df o rm i n i n ga s s o c i a t i o nr u l e ss of a r o n eo ft h e m ，t h em o s tf a m o u si s a p r i o r ia l g o r i t h mp r e s e n t e db ya g r a w a l a p r i o r ia l g o r i t h mb e l o n g st oi n d i r e c tm i n i n g a l g o r i t h ma n dw h a ti tm i n e si st h ew h o l ea s s o c i a t i o nr u l e so f t r a n s a c t i o nd a t a b a s e ； h o w e v e r , i na c t u a la p p l i a n c e ，w h a tt h ee n t e r p r i s e sc a r ei st h ea s s o c i a t i o nr u l e sr e l a t e d t oap r o d u c to rt h en e wp r o d u c tt h ec o m p a n yp u tf o r w a r d ，s ot h em i n i n gb a s e do ns e t t a r g e ti t e mi sp r a c t i c a l l yv a l u a b l e t h i sp a p e ra d v a n c e daa l g o r i t h ms u i t a b l et ot a r g e t i t e mm i n i n gb a s e d0 1 1a p r i o r ia l g o r i t h m ，i b d f - m i n e ra l g o r i t h m ，m e a n w h i l et h i s a l g o r i t h mm a d es o m ei m p r o v e m e n t st ot h es h o r t c o m i n g so ft h ea p r i o r ia l g o r i t h m ， a l g o r i t h mm a k e st h ec o u n to fs u p p o r ts i m p l ea n dc o n v e n i e n ta d o p t i n gt h es t r u c t u r e o fi m p r o v e db i t m a pd a t af o r m a t ，i n s t e a do fr e p e a t e ds c a n n i n gd a t a b a s e ，a n di t e f f e c t i v e l yd i m i n i s h e sg e n e r a t i o ns p a c eo ff r e q u e n ti t e m s e t si nt h ew a yo fp r o p e r h a n d l i n gb i t m a pm a t r i x e x p e r i m e n t sp r o v et h ea l g o r i t h mh a sb a t t e re x e c u t i v ee f f e c t a c c o r d i n gt od i m e n s i o nn u m b e rc o n n e c t e dt ot h er u l e s ，a s s o c i a t i o nr u l e sc a nb e d i v i d e dt ot w ok i n d s ：s i n g l e d i m e n s i o n a la s s o c i a t i o nr u l e sa n dm u l t i d i m e n s i o n a l a s s o c i a t i o nr u l e s o w i n gt or e l a t i o n a ld a t a b a s ei st h em o s tp o p u l a ra n dt h em o s t i i i 关联规则数据挖掘方法的研究和应用 a b u n d a n td a t ar e s o u r c eo fd a t am i n i n g ，a n da s s o c i a t i o nr u l e sc o v e r e db yr e l a t i o n a l d a t a b a s ei so fm u l t i d i m e n s i o n a l ，s ot h ep a p e rm a k e ss t u d i e so fm u l t i d i m e n s i o n a l 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 t r a d i t i o n a lm u l t i d i m e n s i o n a la s s o c i a t i o nr u l e s m i n i n ga l g o r i t h mi s t om i n e ，a d o p t i n gs u c c e s s f u lb o o l e a na s s o c i a t i o nr u l em i n i n g a l g o r i t h ma f t e rd i s p e r s i n gc a t e g o r i c a la t t r i b u t e sa n dq u a n t i t a t i v ea t t r i b u t e s t h ep a p e r t r i e st om i n em u l t i d i m e n s i o n a la s s o c i a t i o nr u l e su s i n gs q ll a n g u a g ed i r e c t l y t o w a r d sm u l t i d i m e n s i o n a ld a t a i ti sc o r eo ft h ea l g o r i t h mt h a tr e l a t i o n a ld a t a b a s ei s o p e r a t e dw i t ht h eg a t h e rs e l e c t i o na n dl i n ks e n t e n c ei ns q ll a n g u a g e ，i no r d e rt o c o m p l e t et h es e l e c t i n gc o u r s eo ff r e q u e n tp r e d i c a t es e ta n de f f i c i e n tr u l e s o nt h eb a s eo fa b o v es t u d i e s ，t h ep a p e rp u t sm u l t i d i m e n s i o n a la s s o c i a t i o nr u l e s t ot h eu s eo f r o a dt r a f f i ca c c i d e n t sd a t am i n i n ga n df i n d so u tv a l u a b l er u l e sf r o mt h e d a t ao fr e c o r d e dt r a f f i ca c c i d e n t s a st ot h ec h a r a c t e ro ft r a f f i ca c c i d e n td a t a ，t h e p a p e ra d v a n c e da s s o c i a t i o n r u l e sm i n i n ga l g o r i t h mb a s e do nc o n s t r a i nr u l e s c o n s e q u e n t ，a n da p p l yt h ea l g o r i t h mi nt h es t u d i e sa n da n a l y s e so ft h ea f f e c t st ot h e a c c i d e n to ft h ee l e m e n t so fm a n ，c a r , r o a di nt r a f f i ca c c i d e n t ，f i n a l l ya c h i e v e ds o m e s i g n i f i c a n tc o n c l u s i o n s ，t h e s ec o n c l u s i o n sa r ei nc o n s i s t e n tt ot h ee x p e r i e n c e so f l o c a lt r a f f i cp o l i c e o nt h eb a s eo ft h e s ec o n c l u s i o n st h e yc a na d o p ts o m ep r o p e r m e a s u r e s ，h e l p i n gt r a f f i ca d m i n i s t r a t i o nd e p a r t m e n ti nt h e i rw o r ko ft r a f f i cs e c u r i t y i m p r o v e m e n t ，t op r e v e n ta n dr e d u c ea c c i d e n th a p p e n i n g s ，t oi n s u r ep e o p l e sl i f ea n d p r o p e r 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 ；t a r g e ti t e m ；m u l t i d i m e n s i o n a la s s o c i a t i o n r u l e ；s q ll a n g u a g e ；r o a dt r a f f i ca c c i d e n t i v 第一章绪论 第一章绪论 随着信息科学技术的发展，数据库管理系统应用越来越广泛，数据库的规 模也在不断地扩大，人们积累了海量的商业数据，例如客户数据、交易历史数据、 销售记录等等。这些数据库中蕴含着大量有价值的商业信息，目前应用的数据库 系统尽管可以高效地实现数据的录入、查询、统计等功能，却无法发现数据中 存在的关系和规则，无法根据现有的数据预测未来的发展趋势，这使得我们的 企业不得不而对“数据丰富，知识贫乏”【l 】的尴尬处境。面对这种数据的汪洋 大海，如何从中发现有价值的信息成为一个急需解决的重要问题。例如：超市的 经营者希望将经常被同时购买的商品放在起，以增加销售量：保险公司想知 道购买保险的客户一般具有哪些特征；医学研究人员希望从已有的成千上万份 病例中找出患某种疾病的病人的共同特征，从而为治愈这种疾病提供一些帮助。 在这种应用需求的驱动下，数据挖掘( d a t am i n i n g ) ，简称d m 研究应运而生。 1 1 数据挖掘概述 数据挖掘是人们多年来对数据库技术进行大量研究和开发的成果，在2 0 世 纪8 0 年代末有了很大的发展。数据挖掘是指从数据库或数据仓库的大量数据中 揭示出隐含的、先前未知的、潜在有用的信息的过程【2 】。它的目标是将大容量 数据转化为有用的知识和信息。数据挖掘不但可以帮助人们从数据库特别是数 据仓库的相关数据中提取出所感兴趣的知识、规律或更高层次的信息，而且也 可以帮助人们从不同程度上去分析它们，从而可以更有效地利用数据；它不仅 可以用于描述过去数据的发展过程，而且还能进一步预测未来的发展趋势。因 此，数据挖掘正成为一个新的、日益受到重视的热点研究领域。 谈到数据挖掘，必须提到数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) ，k d d 是于1 9 8 9 年在美国召开的第1 l 届国际人工智能联合 会议的专题讨论会上提出的。k d d 泛指所有从源数据中发现模式或联系的方 法，常用来描述整个数据挖掘的过程，包括最开始的制定业务目标到最终的结 果分析。关于k d d 与数据挖掘的关系有许多不同的观点，代表了不同的数据 关联规则数据挖掘方法的研究和应用 挖掘技术含义。 第一种观点认为k d d 是数据挖掘的一个特例。这种看法认为既然数据 挖掘系统可以在关系数据库、事务数据库、空间数据库、时序数据库、文本数 据库、多媒体数据库以及w e b 等多种数据组织形式中发现知识，那么数据库中 的知识发现k d d 只是数据挖掘的一个方面 3 1 。它是早期比较流行的观点，这种 描述强调了数据挖掘在数据形式上的多样性。第二种观点认为数据挖掘是k d d 过程的一个步骤。这种观点的思想是：k d d 是从数据中发现知识的全部过程， 而数据挖掘则是此全部过程中的一个特定的、关键的步骤【4 】。虽然数据挖掘可 以从多种数据库及数据仓库中挖掘知识，但是这些数据都是和数据库技术相关 的。而k d d 的过程包括数据清洗、数据集成、数据选择、数据转换、数据挖 掘、模式生成及评估等一系列步骤，它是一个更广义的范畴。把数据挖掘作为 k d d 的一个重要步骤看待，可以使我们聚焦研究重点，有效解决问题。目前， 人们对数据挖掘算法的研究基本属于这样的范畴。还有一部分人认为，k d d 与 数据挖掘的含义基本相同，只是叫法不一样。事实上，在许多的文献中以及许 多场合中，这两个术语都不加区分被人们所使用。因此也有人称知识发现为数 据挖掘，一般可以不加区别地使用两者。 1 2 数据挖掘过程 数据挖掘是一个多阶段数据处理过程，主要包括以下几个步骤： 第一步：了解应用领域的知识。在开始知识发现之前首先进行的同时也是 最重要的就是了解你的数据和业务问题。 第二步：数据集成与数据清洁。数据集成将与研究问题相关的多文件或多数 据库运行环境的数据进行合并处理，数据清洁则解决数据中的语义模糊性，纠 正不一致，处理数据中的遗漏、噪声和脏数据等。 第三步：数据归约与预处理。数据归约将得到数据集的压缩表示，在归约后 的数据集上挖掘将更有效，并产生相同或几乎相同的分析结果，从而提高数据 挖掘的质量。预处理则是针对特定的算法对数据进行有序的组织和排列。 第四步：选择数据挖掘功能。根据挖掘任务的需要选择相应的挖掘功能，例 如分类、聚类或关联规则挖掘等。 2 第一章绪论 达。 第五步：选择适合的数据挖掘算法进行数据挖掘。 第六步：模式评估。对挖掘出来的模式进行评估，可视化、转换和知识的表 第七步：知识的应用。 图1 1 显示了数据挖掘的基本过程。 图1 1 数据挖掘的基本过程 f i g 1 1t h eb a s i c a l 弘o c e s so fd a t am i n i n g 1 3 数据挖掘任务 识 比较典型的数据挖掘任务有概念描述( c o n c e p td e s c r i p t i o n ) 、关联分析 ( a s s o c i 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 na n dp r e d i c t i o n ) ，聚类分析 ( c l u s t e r i n g a n a l y s i s ) 、孤立点分析( o u t l i e r m i n i n g ) 等。 1 概念描述 概念描述本质上就是对某类对象的内涵特征进行概括。一个概念常常是对 一个包含大量数据的数据集合总体情况的概述。如对一个商店所售电脑基本情 况的概述总结就会获得所售电脑基本情况的一个整体概念( 如：基本上为p i i i 以 上的兼容机) 。对一含有大量数据的数据集合进行概述性的总结并获得简明、准 关联规则数据挖掘方法的研究和应用 确的描述，这种描述就称为概念描述。概念描述分为特征化描述和区别性描述。 前者描述目标类数据的一般特征和特性的汇总，后者是将目标类对象的一般特 性与一个或多个对比类对象的特性比较【l l 。 获得概念描述的方法主要有两种：利用更为广义的属性，对所分析数据 进行概要总结，其中被分析的数据就称为目标数据集；对两类所分析的数据 特点进行对比并对对比结果给出概要性总结，而其中两类被分析的数据集分别 被称为目标数据集和对比数据集。 2 关联分析 从广义上讲，关联分析f 1 ，5 1 是数据挖掘的本质。既然数据挖掘的目的是发现 潜藏在数据背后的知识，那么这种知识一定是反映不同对象之间的关联。关联 知识反映一个事件和其他事件之间的依赖或关联。数据库中的数据一般都存在 着关联关系，这种关联是复杂的，有时是隐含的。关联分析的目的就是要找出 数掘库中隐藏的关联信息。关联分析发现关联规则，这些规则展示属性一值频繁 地在给定数据集中一起出现的条件。这种关联关系有简单关联、时序关联、因 果关联、数量关联等。这些关联并不总是事先知道的，而是通过数据库中数据 的关联分析获得的，因而对商业决策具有新价值。简单关联，例如：购买面包的 顾客中有9 0 的人同时购买牛奶。时序关联，例如：若a t & t 股票连续上涨且 d e c 股票不下跌，则第三大m m 股票上涨的可能性为7 5 。它在简单关联中 增加了时间属性。 关联分析广泛应用于购物篮或事务数据分析。关联规则挖掘是关联知识发 现的最常用方法，其中最为著名的是a g r a w a l 等提出的a p r i o f i 及其改进算法， 关联挖掘的目的就是从数据库中挖掘出满足最低支持度和最低可信度的关联规 则。关联规则的研究和应用是数据挖掘中比较活跃和深入的分支，已经提出了 许多关联规则挖掘的理论和算法。 3 分类和预测 分类0 , 7 - g 是数据挖掘中的一个重要的目标和任务。目前的研究在商业上应 用最多。分类就是找出描述并区分数据类或概念的模型，以便能够使用模型预 测类标记未知的对象类。分类的目的是学会一个分类函数或分类模型( 也常常称 作分类器) 。要构造这样一个分类器，需要有一个训练样本数据作为输入。分类 4 第一辛绪论 器的作用就是能够根据数据的属性将数掘分派到不同的组中。这样我们就可以 利用该分类器柬分析已有数据，并预测新数据将属于哪一个组，即数据对象的 类标记，然而，在某些应用中，人们可能希望预测某些空缺的或不知道的数据 值，而不是类标记。当被预测的是数值数据时，通常称之为预测。分类模式可 以采用多种形式表示，如分类规则，判定树，数学公式或神经网络。分类知识 挖掘的一些有代表性的技术有：决策树、贝叶斯分类、神经网络分类、遗传算法、 类比学习和案例学习，以及粗糙集和模糊集等方法。 分类应用的实例很多。例如，我们可以将银行网点分为好、一般和较差三 种类型，并以此分析这三种类型银行网点的各种属性，特别是位置、盈利情况 等，并决定它们分类的关键属性及相互问关系。此后就可以根据这些关键属性 对每一个预期的银行网点进行分析，以便决定预期银行网点属于哪种类型。 4 聚类分析 一般把学习算法分成有导师( 或监督) 和无导师学习两种方式，主要区别是 有没有类信息作为指导。聚类1 1 8 】是典型的无导师学习算法。聚类分析数据对象， 而不考虑已知的类标记，它将数据对象分组成为多个类或簇，同一个类中的对 象具有较高的相似度，而不同类中的对象差别较大。般情况下，训练数据中 不提供类标记，聚类可以用于产生这种标记。聚类按照某个特定标准( 通常是某 种距离) ，最终形成的每个类，在空间上都是一个稠密的区域。所形成的每个类 可以导出规则。通过聚类技术可以把数据划分为一系列有意义的子集，进而实 现对数据的分析。例如，一个商业销售企业，可能关心哪些客户对制定的促销 策略更感兴趣。聚类分析与分类和预测不同，前者总是在类标识下寻求新元素 属于哪个类：而后者通过对数据的分析比较生成新的类标识，它以某种容易理 解的形式展示给用户，刻画了数据所蕴含的类知识。 分类和聚类技术互有交叉和补充。聚类技术主要是以统计方法、机器学习、 神经网络等方法为基础的。常用的聚类算法有基于划分、层次、密度、网格和 模型的五大类聚类算法。聚类分析有很广泛的应用，包括市场或客户分割、模 式识别、数据分析、图像处理及许多其它方面。 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的般行为或模型不一致， 关联规则数据挖掘方法的研究和应用 这些数据对象是孤立点【9 】。在挖掘正常类知识时，通常总是把它们作为噪音来 处理。因此以前许多数据挖掘方法都在正式进行数据挖掘之前就将这类孤立点 数据作为噪声或者意外而将其排出在数据挖掘的分析处理范围之外。然而在一 些应用场合中，如信用欺诈、入侵检测等小概率发生的事件往往比经常发生的 事件更有挖掘价值。因此当人们发现这些数据可以为某类应用提供有用信息时， 就为数据挖掘提供了一个新的研究课题，即孤立点分析。孤立点探测和分析对 于欺诈探测、定制市场、医疗分析及许多其他的任务是非常有用的。发现和检 测孤立点的方法主要有基于概率统计、基于距离和基于偏差等检测技术的三类 方法。 1 4 数据挖掘的应用与发展趋势 数据挖掘的应用极其广泛。目前，数据挖掘技术已经在许多行业都得到应 用并取得了一定的实效，其中包括天文学、生物医学、医疗保健、d n a 分析、 银行、金融、零售业和电信业等| l , l o 1 2 】。 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量 实验和观测数据靠传统的数据分析工具己难于对付，因此对功能强大的智能化 自动分析工具要求迫切，这种需求推动了数据挖掘技术在科学研究领域的应用 发展，并且已获得一些重要成果。 数据挖掘在市场营销中的应用可分为两类：数据库市场营销和购物篮分析。 前者的任务是通过交互查询、数据分割和模型预测等方法来选择有潜力的顾客 以便向他们推销产品。后者的任务是分析市场销售数据以识别顾客的购买行为 模式，从而帮助确定商店货架的布局，促进商品的销售。 在银行业，数据挖掘主要用于信用欺诈的建模和预测、风险评估、趋势分 析、收益分析以及辅助直销活动。在金融市场，已将神经网络用于股票价格预 测、购买权交易、债券等级评定、资产组合管理、商品价格预测以及金融危机 预测等方面。 电信业已经从单纯的提供市话和长话服务演变成提供综合电信服务，如语 音、传真、寻呼、移动电话、图像、电子邮件、计算机和w e b 数据传输，以及 其他数据通信服务。而且随着许多国家对电信业的开放和通信技术的发展，电 6 第一章绪论 信市场正在迅速扩张并愈发竞争激烈。因此，利用数据挖掘技术来帮助理解商 业行为、确定电信模式、捕捉盗用行为、更好地利用资源和提高服务质量是非 常有必要的。 数据挖掘语言的设计、高效的数据挖掘方法和集成的数据挖掘环境的建立 以及应用数据挖掘技术解决大型应用问题，都是目前数据挖掘研究和应用开发 所面临的主要问题。下面是数据挖掘的发展趋势： 1 算法效率和可伸缩性。目前，数据库的规模呈指数增长。据统计，数据 和计算资源的增长速度符合摩尔定理，每1 8 个月翻一番。因此，海量数据挖掘 的最大挑战不仅仅在于数据库的绝对规模，还在于数据挖掘系统能够处理这些 持续增长的数据集合。为了保证高效率，数据挖掘系统必须能有效地处理海量 数据，其算法必须是高效率和可伸缩的。 2 处理不同类型的数据和数据源 1 3 , 1 4 。目前数据挖掘系统处理的数据库大 多是关系数据库。随着数据库应用范围的日益扩大和规模、功能的日益完善， 数据库中将包含大量复杂的数据类型。如结构化的数据，复杂的数据对象，混 合文本，多媒体数据，时空数据，事务数据及历史数据等，甚至出现新的数据 库模型。因此，保证数据挖掘系统能有效地处理此类数据库中的数据是至关重 要的。 3 数据挖掘系统的交互性。数据挖掘中操作者的适当参与能加速数据挖掘 过程。方面，交互界面接收用户的检索、查询要求和数据挖掘策略，为用户 表达要求和策略提供了方便；另方面，交互界面又把生成的结果传递给用户， 由于生成的结果可以是多种多样，因此，准确而直观地描述挖掘结果和友好而 高效的用户界面一直是研究的重要课题。 4 w e b 挖掘 1 5 , 1 6 1 。由于w e b 上存在大量信息，并且w e b 在当今社会扮演越 来越重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服 务，将成为数据挖掘中一个最为重要和繁荣的子领域。 5 数据挖掘中的隐私保护与信息安全【2 0 】。数据挖掘能从不同的角度、不同 的抽象层上看待数据，这将潜在地影响数据的私有性和安全性。随着计算机网 络的日益普及，研究数据挖掘可能导致的非法数据入侵是实际应用中需要解决 的问题之一。 7 关联规则数据挖掘方法的研究和应用 6 探索新的应用领域 1 7 , 1 s 。早期的数据挖掘主要集中在帮助企业提高竞争 能力。随着数据挖掘的日益普及，它的应用领域也在不断扩大。信息产业的发 展为数据挖掘提供了广阔的空间，数据挖掘技术的应用范围将不断得到拓宽， 特别是在生物工程、商业智能、网络服务等领域的应用将成为新的研究热点。 同时由于通用数据挖掘系统在处理特定应用问题时有其局限性，因此，目前的 一种趋势是开发针对特定应用的数据挖掘系统。 7 数据挖掘语言的标准化。标准的数据挖掘语言或有关方面的标准化工作 将有助于数据挖掘系统的研究和开发，有利于用户学习和使用数据挖掘系统。 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和 标准化。 8 可视化数据挖掘【1 9 】。可视化数据挖掘是从大量数据中发现知识的有效途 径。目前数据挖掘的可视化仅体现在结果的简单描述，而数据可视化、挖掘过 程和结果可视化，将揭开数据挖掘神秘的面纱，使其变得更为生动、形象和具 体。数据和结果的图形展示可以放大、缩小、平移、旋转和变换角度，使分析 人员和用户更加容易理解，将大大推动数据挖掘工具在发现知识和数据分析中 的应用。因此，数据挖掘的可视化具有重要的理论意义和应用价值。 随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、 越来越复杂，数据挖掘将发挥出越来越大的作用。 1 5 论文的工作 在本章中，我们对数据挖掘的基本概念和挖掘过程、任务有了大体上的了 解，由于数据挖掘技术包含的内容很多，涉及到的知识领域也很广，所以在这 里不能一一详细介绍。在本论文中我仅就关联规则数据挖掘中的相关问题进行 深入的探讨。 在第二章中，本文首先对关联规则数据挖掘的概念进行了详细介绍，并按 照不同的分类标准对当前的关联规则数据挖掘问题进行了分类，其次对挖掘关 联规则的经典算法a 耐o r i 算法进行了详细阐述，并作了举例分析，同时对相关 改进算法也进行了简要介绍。 由于关联规则经典挖掘算法a p o r i 算法属于间接挖掘算法，在实际应用中 8 第一章绪论 基于固定目标项目的直接挖掘有一定的实用价值，第三章在a p r i o r i 算法的基础 上，对a p r i o r i 算法作了一些改进，提出了一种适合目标项目挖掘的算法 i b d f m i n e r 算法，算法以改进的位图数据格式为存储结构，并通过对位图矩阵 的相应处理策略有效缩小了频繁项目集的生成空间，实验证明该算法有较好的 执行效率。 第四章对多维关联规则基本概念及挖掘技术做了简单介绍，传统的多维关 联规则挖掘方法是将分类属性和量化属性进行离散化处理后采用成功的单维布 尔关联规则挖掘算法进行挖掘，本文尝试直接对多维数据利用标准s q l 语言来 进行多维关联规则挖掘，并给出了利用标准s q l 挖掘多维关联规则的通用算 法。 第五章对多维关联规则作了具体应用。在道路交通事故关联规则的挖掘过 程中，针对道路交通事故数据特点，本章提出了基于约束规则后件的关联规则 挖掘算法，并将算法用于交通事故中“人、车、路”等因素对事故产生的影响 的分析研究，得出了一些有实际意义的结论，这些结论与当地交警的经验基本 上是一致的，根据这些结论可以采取针对性措施，用于辅助交通管理部门对今 后的道路交通安全的改进工作。 最后对全文作总结，并展望了下一步的工作。 9 关联规则数据挖掘方法的研究和戍用 第二章关联规则数据挖掘 关联规则数据挖掘就是从大量的数据中挖掘出有价值的描述数据项之间相 互联系的有关知识。自1 9 9 3 年a g r a w a l 5 1 等人首先提出关联规则概念以来，关 联规则挖掘便迅速受到数据挖掘领域专家的广泛关注。例如：从大量的商业交 易记录中发现有价值的关联知识，可以帮助进行商品目录的设计、交叉营销或 帮助进行其它有关的商业决策。挖掘关联知识的一个典型应用实例就是市场购 物分析。发现常在一起购买的商品( 关联知识) 将帮助商家分析客户的购买习惯， 从而制定有针对性的市场营销策略。比如顾客在购买牛奶时可以将牛奶和面包 放在相近的地方，这样或许会促进这两个商品的销售。 2 ，1 关联规则描述 2 1 1 基本概念 关联规则挖掘工作可以描述如下：假设i = i l ，i 2 ，i m 是m 个不同项目 的集合，给定一个交易数据库d ( 即一个交易集合) ，每个事务可以用唯一的标 识符t i d 来标识，d 中的每个元素( 交易) t 是i 中一些项目组成的集合，t c _ i 。 关联规则表示为：x j y ，其中x c i ，y c i ，并且x n y = 巾。x 表示此关联规 则的前件或前提( a n t e c e d e n t ) ，y 为此关联规则的后件或结论( c o n s e q u e n t ) ，关联规 则的挖掘就是要发现满足用户给定的最低支持度和最低置信度的所有条件蕴涵 式，即关联规则。这些规则的支持度和置信度都大于等于最低支持度和最低置 信度。 嚣信度是对关联规则的准确度的度量，或者说表示规则的强度：支持度是 对关联规则的重要性的度量，表示规则的频度。支持度说明了这条规则在所有 事务中有多大的代表性，显然，支持度越大，关联规则越重要。有些关联规则 置信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小。反之， 如果支持度很高，置信度很低，则说明该规则不可靠。如果不考虑关联规则的 支持度和置信度，那么在数据库中存在非常多的关联规则。事实上，人们般 1 0 第二章关联规则数据挖掘 只对那些满足一定的支持度和置信度的关联规则感兴趣。因此，为了发现有意 义的关联规则，需要由用户给定两个基本阂值：最低支持度和最低霄信度。 有关定义如下所述： 【定义2 1 】项目( i t e m ) ：交易数据库中的一个属性字段，每个字段有一定的 取值范围。对一超级市场来讲，项目一般是指一次交易中的一个物品。 【定义2 2 】交易( t r a n s a c t i o n ) ：某个客户在一次交易中，发生的所有项目的 集合。 【定义2 3 】项目集( 1 t e m s e t ) ：包含若干个项目的集合，简称项集。 【定义2 4 】k ，项集：对于项集x ，如果x 中包含有k 个项目，则x 称为“ 项集。例如项集x = a ，b l 就是一个2 项集。 【定义2 5 支持度( s u p p o r t ) ：称交易数据库d 中包含项目集x 的交易的个 数与d 中总的交易个数之比为x 在d 中的支持度。把x 的支持度记作s u p ( x ) ， 而关联规则x y 的支持度则记作s u po ( j y ) ，具体描述是： s u p ( x j y ) = p ( x uy ) 【定义2 6 置信度( c o n f i d e n c e ) ：对形如x j y 的关联规则，其中x 和y 都是项目集，定义规则的置信度为交易集合d 中既包含x 也包含y 的交易个 数与d 中包含x 的交易个数之比，或者说是项目集x j y 的支持度与x 的支 持度之比，即s u p ( x w y ) s u p ( ) ( ) 。把规则x j y 的置信度记作c o n f ( xy ) 。 事实上，置信度即是指在出现了项目集x 的交易中，项目集y 也同时出现 的概率有多大。支持度和置信度都是规格化的概念，他们的范围都在0 到1 之 间。 【定义2 7 】最低支持度( m i n i m u ms u p p o r t ) ：由用户定义的衡量支持度的一 个阂值，表示项目集在统计意义上的最低重要性，记作m i n s u p 。 【定义2 8 最低置信度( m i n i m u mc o n f i d e n c e ) ：由用户定义的衡量置信度的 一个闽值，表示规则的最低可靠性，记作m i n c o n f 对于满足最低支持度和最低置信度要求的关联规则称为强规则。 【定义2 9 】支持数：d 中包含项目集x 的事务t 的个数，称为x 在d 中 的支持数( s u p p o r tc o u n t ) ，简记为e o t m t 。 设d 中包含的事务数表示为i d i ，根据以上支持度和支持数的定义，可以得 关联规则数据挖掘方法的研究和应用 出某项目集x 的支持数与支持度的关系是c o u n t = s u p p o r t x n l ，另外与最低支持 度相对应，把支持数定义为最低支持数( m i n i m u ms u p p o r tc o u n t ) ，简记为 m i n c o u m ，它和最低支持度的关系是m i n c o u n t ：- m i n s u p x i d i 【定义2 1 0 频繁项目集：若项集x 的支持度不小于最低支持度，则称x 为频繁项目集，即x 满足最低支持度要求。若某一项目m 满足最低支持度要求， 则称m 为频繁项目，所有频繁项目的集合称为频繁1 项集，记为l l ；满足最低 支持度要求的k 一项集称为频繁k 项集，所有频繁k 项集的集合记为l k 。 2 1 2 关联规则的分类 传统的关联规则挖掘形式是购物篮分析，但关联规则绝不仅此一种。可以 根据以下标准对这些关联规则进行分类： 1 根据关联规则所处理的具体值来进行分类 若一个规则仅描述数据项是否出现在这种情况问的联系，那么这种关联规 则就是一个布尔关联规则。例如规贝j j ( 2 1 ) 描述的就是有关市场购物分析所获得 的一条布尔关联规则。 b u y sc o m p u t e r j b u y sp r i n t e r 【s u p p o r t = 2 ，c o n f i d e n c e = 6 0 】( 2 1 ) 若一个规则描述的是定量数据项( 或属性) 之间的关系，那么它就是一个定 量关联规则。在这些规则中，数据项的定量数值可以划分为区间范围。例如规 则( 2 2 ) 就是一个定量关联规则。 a g e ( x ，“3 0 3 4 ”) i n c o m e ( x ，“4 2 k 4 8 k ”) j b u y s ( x ，“c o m p u t e r ”) ( 2 2 ) 2 根据规则中数据的维数来进行分类 若一个规则中的项或属性仅涉及一个维，那么它就是一个单维关联规则。 例如规j j ( 2 3 ) ，由于其只涉及到一维b u y s ，所以是一个单维关联规则。 b u y s ( x ，“c o m p u t e r ”) j b u y s ( x ，“p r i