（计算机应用技术专业论文）基于模糊集理论的关联规则数据挖掘研究.pdf

摘要 随着信息技术的发展，数据挖掘技术得到了广泛的关注。在数据挖掘技术中 有很多研究领域，关联规则数据挖掘就是其中一个重要的研究方向，对它进行深 入研究不仅有着重要的理论意义，而且有着重要的应用价值。关联规则数据挖掘 于1 9 9 3 年由a g r a w m 等人提出，它最初是以分析事务数据库中项与项之间联系 为目标，后来的研究者们对问题原型进行多方面的改进和扩充。目前。关联规则挖 掘技术已经被应用到商业、电信、金融、农业、医疗等领域，并取得了良好的效 果。 关联规则挖掘算法是关联规则数据挖掘研究中的主要内容之一，迄今为止 己提出了多种关联规则挖掘算法，其中最著名的是a g r a w m 提出的a p f i o f i 算法。 传统的a p r i o r i 算法及其改进算法都是集中在确定的，精确的概念上完成数据 的挖掘，难以对非精确的或者说模糊的概念进行挖掘。本文结合模糊集理论的知 识，对关联规则挖掘算法做了进一步研究，引入模糊关联规则的概念，用模糊概 念表示数据之间的关联关系，拓宽了关联规则的表示和应用范围。并将概念分层 应用到关联规则的挖掘中，引入多层次模糊关联规则挖掘算法，将其应用到商品 交易中，用其解决模糊概念的关联规则挖掘的问题，有利于指导决策的制定 在现有的关联规则研究中，数据库中的各个项目是按平等一致的方式加以 处理的，然而，在现实世界数据库中却并非如此，不同的项目往往有着不同的重 要性本文从实际应用角度，针对传统的a p r i o r i 算法存在的缺陷，通过对属性 出现的频率来计算权重，基于模糊集理论，改进了模糊加权关联规则挖掘算法 通过具体实验验证了算法的可行性，并对算法的性能进行了讨论 关键词：数据挖掘；关联规则；模糊关联规则 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 h s 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 ft h ei m p o r t a n tr e s e a r c hs u b j e 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 st h em o s ti m p o r t a n tv a l u e sn o to n l yi nt h e o r yb u ta l s o i 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 em i n i n gi sp u tf o r w a r db ya g r a w a la n dt h eo t h e r si n 19 9 3 ，f i r s t l yt 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 , r e s e r a r c h e r si 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 ft h eq 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 nr u l e st e c h n o l o g yh a sb e e na p p l i e di nb 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 班c u l t u r e ，m e d i c a lt r e a t m e r ta n ds oo n i th a sb r o u g h tag o o d e 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 f 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 f i o da 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 ft r a n s a c t i o nd a t a b a s e ； t h et r a d i t i o n a ld a t am i n i n ga l g o r i t h m s ，s u c ha sa p f i o da l g o r i t h ma n di t si m p r o v e d a l g o r i t h m s ，a r ef o c u so nt h em i m n gi n a c c u r a t ec o n c e p t s ，a n dc a nn o tm i n et h e i n a c c u r a t eo rf u z z yc o n c e p t s s o ，t h et h e s i si n t e g r a l st h ef u z z y - s e tc o n c e p t sw i t hd a t a m i m n ga l g o r i t h m st om a k ead e e p e rr e s e a r c ho na 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 ， a n di n t r o d u c e st h ec o n c e p to ff u z z ya s s o c i a t i o nm l e s ，w h i c he x p r e s s e st h ea s s o c i a t e d r e l a t i o n s h i pb yf u z z yc o n c e p t s a n de x t e n d st h er a n g eo ft h ea p p l i c a t i o na n d d e s c r i p t i o no fa s s o c i a t i o nr u l e s t h et h e s i si n t r o d u c e saf u z z ym u l t i l e v e la 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 t lt h em u l t i l e v e la 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 ， w h i c hw i l lb ea p p l i e dt ot h ec o m m o d i t ye x c h a n g ea n du s e dt om i n ea s s o c i a t i o nr u l e s i nf u z z yc o n c e p t s i tw i l lb eh e l p f u lt oi n s t r u c td e c i s i o n m a k i n g i nt h ec u r r e n tr e s e a r c h e so fa s s o c i a t i o nr u l e s ，a l lt h ei t e m si nad a t a b a s ea r e t r e a t e di nau n i f o r mw a y h o w e v e r , i ti sn o tt r u ei nt h er e a lw o r l dd a t a b a s e s ，i nw h i c h i i d i f f e r e n ti t e m su s u a l l yh a v ed i f f e r e n ti m p o r t a n c e s c a l c u l a t i n gw e i g h tt h r o u g ht h e f r e q u e n c yo fi t e ma t t r i b u t ea i m e da td e f i c i e n c yw h i c he x i s t si nt h et r a d i t i o n a la p r i o r i a l g o r i t h m i m p r o v i n ga l g o r i t h m sf o rm i n i n gf u z z yw e i g h t e da s s o c i a t i o nr u l e sb a s e d o nf u z z ys e t st h e o r i e s a f t e rt h i s ，t h ef e a s i b i l i t ya n dp e r f o r m a n c eo ft h ea l g o r i t h m s t h r o u g ht h ee x p e r i m e n t s a r cd i s c u s s e d 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 ；f u z z ya s s o c i a t i o nr u l e 1 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得宅辑k 大髻或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 碾诚签字日期：加。7年斗月上7 目 学位论文版权使用授权书 本学位论文作者完全了解有关保留圣f 权么锨用学位论文的规定，有权呆留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本 人授权耍舷太髻可以将学位论文的全部或部分内容编入有关数据库进彳亍检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：张诚 签字日期：2 。7 年4 月l 7 日 学位论文作者毕业去向： 工作单位： 通讯地址： 导师签名 签字臼期 电话 邮编 翔旁式 如叼年争r 巧日 第一章绪论 第一章绪论 随着信息科学技术的发展，数据库管理系统应用越来越广泛，数据库的规 模也在不断地扩大，人们积累了海量的商业数据，例如客户数据、交易历史数据、 销售记录等等。这些数据库中蕴含着大量有价值的商业信息，目前应用的数据库 系统尽管可以高效地实现数据的录入、查询、统计等功能，却无法发现数据中 存在的关系和规则，无法根据现有的数据预测未来的发展趋势，这使得我们的 企业不得不而对“数据丰富，知识贫乏”【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 年在美国召开的第l l 届国际人工智能联合 会议的专题讨论会上提出的。k d d 泛指所有从源数据中发现模式或联系的方 法，常用来描述整个数据挖掘的过程，包括最开始的制定业务目标到最终的结 果分析。关于k d d 与数据挖掘的关系有许多不同的观点，代表了不同的数据 基于模糊集理论的关联规则数据挖掘研究 挖掘技术含义。 第一种观点认为k d d 是数据挖掘的一个特例。这种看法认为既然数据挖 掘系统可以在关系数据库、事务数据库、空间数据库、时序数据库、文本数据 库、多媒体数据库以及w e b 等多种数据组织形式中发现知识，那么数据库中的 知识发现k d d 只是数据挖掘的一个方面【3 】。它是早期比较流行的观点，这种描 述强调了数据挖掘在数据形式上的多样性。第二种观点认为数据挖掘是k d d 过程的一个步骤。这种观点的思想是：k d d 是从数据中发现知识的全部过程， 而数据挖掘则是此全部过程中的一个特定的、关键的步骤 4 1 。虽然数据挖掘可 以从多种数据库及数据仓库中挖掘知识，但是这些数据都是和数据库技术相关 的。而k d d 的过程包括数据清洗、数据集成、数据选择、数据转换、数据挖 掘、模式生成及评估等一系列步骤，它是一个更广义的范畴。把数据挖掘作为 k d d 的一个重要步骤看待，可以使我们聚焦研究重点，有效解决闯题。目前， 人们对数据挖掘算法的研究基本属于这样的范畴。还有一部分人认为，k d d 与 数据挖掘的含义基本相同，只是叫法不一样。事实上，在许多的文献中以及许 多场合中，这两个术语都不加区分被人们所使用。因此也有人称知识发现为数 据挖掘，一般可以不加区别地使用两者。 1 2 数据挖掘过程 数据挖掘是一个多阶段数据处理过程，主要包括以下几个步骤： 第一步：了解应用领域的知识。在开始知识发现之前首先进行的同时也是 最重要的就是了解你的数据和业务问题。 第二步：数据集成与数据清洁。数据集成将与研究问题相关的多文件或多数 据库运行环境的数据进行合并处理，数据清洁则解决数据中的语义模糊性，纠 正不一致，处理数据中的遗漏、噪声和脏数据等。 第三步：数据归约与预处理。数据归约将得到数据集的压缩表示，在归约后 的数据集上挖掘将更有效，并产生相同或几乎相同的分析结果，从而提高数据 挖掘的质量。预处理则是针对特定的算法对数据进行有序的组织和排列。 第四步：选择数据挖掘功能。根据挖掘任务的需要选择相应的挖掘功能，例 如分类、聚类或关联规则挖掘等。 第一章绪论 达。 第五步：选择适合的数据挖掘算法进行数据挖掘。 第六步：模式评估。对挖掘出来的模式进行评估，可视化、转换和知识的表 第七步：知识的应用。 图1 - 1 显示了数据挖掘的基本过程。 1 3 数据挖掘任务 图1 - 1 数据挖掘的基本过程 识 比较典型的数据挖掘任务有概念描述( 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 ga n a l y s i s ) 、孤立点分析( o u t l i e rm i n i n g ) 等。 1 概念描述 ，概念描述本质上就是对某类对象的内涵特征进行概括。一个概念常常是对 一个包含大量数据的数据集合总体情况的概述。如对一个商店所售电脑基本情 况的概述总结就会获得所售电脑基本情况的一个整体概念( 如：基本上为p i i i 以 上的兼容机) 。对一含有大量数据的数据集合进行概述性的总结并获得简明、准 基于模糊集理论的差联规则数据挖掘研究 确的描述，这种描述就称为概念描述。概念描述分为特征化描述和区别性描述。 前者描述目标类数据的一般特征和特性的汇总，后者是将目标类对象的一般特 性与一个或多个对比类对象的特性比较【”。 获得概念描述的方法主要有两种：利用更为广义的属性，对所分析数据 进行概要总结，其中被分析的数据就称为目标数据集；对两类所分析的数据 特点进行对比并对对比结果给出概要性总结，而其中两类被分析的数据集分别 被称为目标数据集和对比数据集。 2 关联分析 从广义上讲，关联分析1 ，5 1 是数据挖掘的本质。既然数据挖掘的目的是发现 潜藏在数据背后的知识，那么这种知识一定是反映不同对象之间的关联。关联 知识反映一个事件和其他事件之间的依赖或关联。数据库中的数据一般都存在 着关联关系，这种关联是复杂的，有时是隐含的。关联分析的目的就是要找出 数据库中隐藏的关联信息。关联分析发现关联规则，这些规则展示属性一值频繁 地在给定数据集中一起出现的条件。这种关联关系有简单关联、时序关联、因 果关联、数量关联等。这些关联并不总是事先知道的，而是通过数据库中数据 的关联分析获得的，因而对商业决策具有新价值。简单关联，例如：购买面包的 顾客中有9 0 的人同时购买牛奶。时序关联，例如：若a t 8 t t 股票连续上涨且 d e c 股票不下跌，则第三大i b m 股票上涨的可能性为7 5 。它在简单关联中 增加了时间属性。 关联分析广泛应用于购物篮或事务数据分析。关联规则挖掘是关联知识发 现的最常用方法，其中最为著名的是a g r a w a l 等提出的a p r i o r i 及其改进算法， 关联挖掘的目的就是从数据库中挖掘出满足最低支持度和最低可信度的关联规 则。关联规则的研究和应用是数据挖掘中比较活跃和深入的分支，已经提出了 许多关联规则挖掘的理论和算法。 3 分类和预测 分类【1 瑚1 是数据挖掘中的一个重要的目标和任务。目前的研究在商业上应 用最多。分类就是找出描述并区分数据类或概念的模型，以便能够使用模型预 测类标记未知的对象类。分类的目的是学会一个分类函数或分类模型( 也常常称 作分类器) 。要构造这样一个分类器，需要有一个训练样木数据作为输入。分类 4 第一章绪论 器的作用就是能够根据数据的属性将数据分派到不同的组中。这样我们就可以 利用该分类器来分析已有数据，并预测新数据将属于哪一个组，即数据对象的 类标记，然而，在某些应用中，人们可能希望预测某些空缺的或不知道的数据 值，而不是类标记。当被预测的是数值数据时，通常称之为预测。分类模式可 以采用多种形式表示，如分类规则，判定树，数学公式或神经网络。分类知识 挖掘的一些有代表性的技术有：决策树、贝叶斯分类、神经网络分类、遗传算法、 类比学习和案例学习，以及粗糙集和模糊集等方法。 分类应用的实例很多。例如，我们可以将银行网点分为好、一般和较差三 种类型，并以此分析这三种类型银行网点的各种属性，特别是位置、盈利情况 等，并决定它们分类的关键属性及相互问关系。此后就可以根据这些关键属性 对每一个预期的银行网点进行分析，以便决定预期银行网点属于哪一种类型。 4 聚类分析 一般把学习算法分成有导师( 或监督) 和无导师学习两种方式，主要区别是 有没有类信息作为指导。聚类】是典型的无导师学习算法。聚类分析数据对象， 而不考虑已知的类标记，它将数据对象分组成为多个类或簇，同一个类中的对 象具有较高的相似度，而不同类中的对象差别较大。一般情况下，训练数据中 不提供类标记，聚类可以用于产生这种标记。聚类按照某个特定标准( 通常是某 种距离) ，最终形成的每个类，在空间上都是一个稠密的区域。所形成的每个类 可以导出规则。通过聚类技术可以把数据划分为一系列有意义的子集，进而实 现对数据的分析。例如，一个商业销售企业，可能关心哪些客户对制定的促销 策略更感兴趣。聚类分析与分类和预测不同，前者总是在类标识下寻求新元素 属于哪个类；而后者通过对数据的分析比较生成新的类标识，它以某种容易理 解的形式展示给用户，刻画了数据所蕴含的类知识。 分类和聚类技术互有交叉和补充。聚类技术主要是以统计方法、机器学习、 神经网络等方法为基础的。常用的聚类算法有基于划分、层次、密度、网格和 模型的五大类聚类算法。聚类分析有很广泛的应用，包括市场或客户分割、模 式识别、数据分析、图像处理及许多其它方面。 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致， 基于模糊集理论的关联规则数据挖掘研究 这些数据对象是孤立点【9 】。在挖掘正常类知识时，通常总是把它们作为噪音来 处理。因此以前许多数据挖掘方法都在正式进行数据挖掘之前就将这类孤立点 数据作为噪声或者意外而将其排出在数据挖掘的分析处理范围之外。然而在一 些应用场合中，如信用欺诈、入侵检测等小概率发生的事件往往比经常发生的 事件更有挖掘价值。因此当人们发现这些数据可以为某类应用提供有用信息时， 就为数据挖掘提供了一个新的研究课题，即孤立点分析。孤立点探测和分析对 于欺诈探测、定制市场、医疗分析及许多其他的任务是非常有用的。发现和检 测孤立点的方法主要有基于概率统计、基于距离和基于偏差等检测技术的三类 方法。 1 4 数据挖掘的应用与发展趋势 数据挖掘的应用极其广泛。目前，数据挖掘技术已经在许多行业都得到应 用并取得了一定的实效，其中包括天文学、生物医学、医疗保健、d n a 分析、 银行、金融、零售业和电信业等o 2 1 。 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量 实验和观测数据靠传统的数据分析工具己难于对付，因此对功能强大的智能化 自动分析工具要求迫切，这种需求推动了数据挖掘技术在科学研究领域的应用 发展，并且已获得一些重要成果。 数据挖掘在市场营销中的应用可分为两类：数据库市场营销和购物篮分析。 前者的任务是通过交互查询、数据分割和模型预测等方法来选择有潜力的顾客 以便向他们推销产品。后者的任务是分析市场销售数据以识别顾客的购买行为 模式，从而帮助确定商店货架的布局，促进商品的销售。 在银行业，数据挖掘主要用于信用欺诈的建模和预测、风险评估、趋势分 析、收益分析以及辅助直销活动。在金融市场，已将神经网络用于股票价格预 测、购买权交易、债券等级评定、资产组合管理、商品价格预测以及金融危机 预测等方面。 电信业已经从单纯的提供市话和长话服务演变成提供综合电信服务，如语 音、传真、寻呼、移动电话、图像、电子邮件、计算机和w e b 数据传输，以及 其他数据通信服务。而且随着许多国家对电信业的开放和通信技术的发展，电 6 第一章绪论 信市场正在迅速扩张并愈发竞争激烈。因此，利用数据挖掘技术来帮助理解商 业行为、确定电信模式、捕捉盗用行为、更好地利用资源和提高服务质量是非 常有必要的。 数据挖掘语言的设计、高效的数据挖掘方法和集成的数据挖掘环境的建立 以及应用数据挖掘技术解决大型应用问题，都是目前数据挖掘研究和应用开发 所面临的主要问题。下面是数据挖掘的发展趋势： 1 算法效率和可伸缩性。目前，数据库的规模呈指数增长。据统计，数据 和计算资源的增长速度符合摩尔定理，每1 8 个月翻一番。因此，海量数据挖掘 的最大挑战不仅仅在于数据库的绝对规模，还在于数据挖掘系统能够处理这些 持续增长的数据集合。为了保证高效率，数据挖掘系统必须能有效地处理海量 数据，其算法必须是高效率和可伸缩的。 2 处理不同类型的数据和数据源 1 3 , 1 4 1 。目前数据挖掘系统处理的数据库大 多是关系数据库。随着数据库应用范围的日益扩大和规模、功能的日益完善， 数据库中将包含大量复杂的数据类型。如结构化的数据，复杂的数据对象，混 合文本，多媒体数据，时空数据，事务数据及历史数据等，甚至出现新的数据 库模型。因此，保证数据挖掘系统能有效地处理此类数据库中的数据是至关重 要的。 3 数据挖掘系统的交互性。数据挖掘中操作者的适当参与能加速数据挖掘 过程。一方面，交互界面接收用户的检索、查询要求和数据挖掘策略，为用户 表达要求和策略提供了方便；另一方面，交互界面又把生成的结果传递给用户， 由于生成的结果可以是多种多样，因此，准确而直观地描述挖掘结果和友好而 高效的用户界面一直是研究的重要课题。 4 w e b 挖掘1 1 5 , 16 】。由于w e b 上存在大量信息，并且w e b 在当今社会扮演越 来越重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服 务，将成为数据挖掘中一个最为重要和繁荣的子领域。 5 数据挖掘中的隐私保护与信息安全【2 0 1 。数据挖掘能从不同的角度、不同 的抽象层上看待数据，这将潜在地影响数据的私有性和安全性。随着计算机网 络的日益普及，研究数据挖掘可能导致的非法数据入侵是实际应用中需要解决 的问题之一。 基于模 胡集理论的关联规则数据挖掘研究 6 探索新的应用领域1 7 , 1 8 1 。早期的数据挖掘主要集中在帮助企业提高竞争 能力。随着数据挖掘的日益普及，它的应用领域也在不断扩大。信息产业的发 展为数据挖掘提供了广阔的空间，数据挖掘技术的应用范围将不断得到拓宽， 特别是在生物工程、商业智能、网络服务等领域的应用将成为新的研究热点。 同时由于通用数据挖掘系统在处理特定应用问题时有其局限性，因此，目前的 一种趋势是开发针对特定应用的数据挖掘系统。 7 数据挖掘语言的标准化。标准的数据挖掘语言或有关方面的标准化工作 将有助于数据挖掘系统的研究和开发，有利于用户学习和使用数据挖掘系统。 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和 标准化。 8 可视化数据挖掘 i9 1 。可视化数据挖掘是从大量数据中发现知识的有效途 径。目前数据挖掘的可视化仅体现在结果的简单描述，丽数据可视化、挖掘过 程和结果可视化，将揭开数据挖掘神秘的面纱，使其变得更为生动、形象和具 体。数据和结果的图形展示可以放大、缩小、平移、旋转和变换角度，使分析 人员和用户更加容易理解，将大大推动数据挖掘工具在发现知识和数据分析中 的应用。因此，数据挖掘的可视化具有重要的理论意义和应用价值。 随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、 越来越复杂，数据挖掘将发挥出越来越大的作用。 1 5 论文的工作 在本章中，我们对数据挖掘的基本概念和挖掘过程。任务有了大体上的了 解，由于数据挖掘技术包含的内容很多，涉及到的知识领域也很广，所以在这 里不能一一详细介绍。在本论文中我仅就关联规则数据挖掘中的相关问题进行 深入的探讨。 在第二章中，本文首先对关联规则数据挖掘的概念进行了详细介绍，并按 照不同的分类标准对当前的关联规则数据挖掘问题进行了分类，其次对挖掘关 联规则的经典算法a p r i o r i 算法进彳亍了详细阐述，并作了举例分析，同时对相关 改进算法也进行了简要介绍。 第三章引入模糊集理论，介绍模糊关联规则及其挖掘算法。 第一章绪论 第四章针对传统单层次模糊关联规则的不足，将概念分层应用到关联规则 的挖掘中，引入多层次模糊关联规则挖掘算法，将其应用到商品交易中，用其解 决模糊概念的关联规则挖掘的问题，有利于指导决策的制定 第五章从实际应用角度，针对传统的a p r i o r i 算法存在的缺陷，通过对属性出 现的频率来计算权重，基于模糊集理论，改进了模糊加权关联规则挖掘算法通过 实验验证了算法的可行性，并对算法的性能进行了讨论 最后对全文作总结，并展望了下一步的工作。 9 基于模糊集理论的关联规则数据挖掘研究 第二章关联规则数据挖掘 关联规则数据挖掘就是从大量的数据中挖掘出有价值的描述数据项之间相 互联系的有关知识。自1 9 9 3 年a g r a w a l 口垮人首先提出关联规则概念以来，关 联规则挖掘便迅速受到数据挖掘领域专家的广泛关注。例如：从大量的商业交 易记录中发现有价值的关联知识，可以帮助进行商品目录的设计、交叉营销或 帮助进行其它有关的商业决策。挖掘关联知识的一个典型应用实例就是市场购 物分析。发现常在一起购买的商品( 关联知识) 将帮助商家分析客户的购买习惯， 从而制定有针对性的市场营销策略。比如顾客在购买牛奶时可以将牛奶和面包 放在相近的地方，这样或许会促进这两个商品的销售。 2 1 关联规则描述 2 1 1 基本概念 关联规则挖掘工作可以描述如下：假设i - 驻l ，i 2 ，i m 是1 1 1 个不同项目 的集合，给定一个交易数据库d ( 即一个交易集合) ，每个事务可以用唯一的标 识符t i d 来标识，d 中的每个元素( 交易) t 是i 中一些项目组成的集合，t c i 。 关联规则表示为：x 等y ，其中x c i ，y c i ，并且x n y = m 。x 表示此关联 规则的前件或前提( a n t e c e d e n t ) ，y 为此关联规则的后件或结论( c o n s e q u e n 0 ，关联 规则的挖掘就是要发现满足用户给定的最低支持度和最低置信度的所有条件蕴 涵式，即关联规则。这些规则的支持度和置信度都大于等于最低支持度和最低 置信度。 置信度是对关联规则的准确度的度量，或者说表示规则的强度；支持度是 对关联规则的重要性的度量，表示规则的频度。支持度说明了这条规则在所有 事务中有多大的代表性，显然，支持度越大，关联规则越重要。有些关联规则 置信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小。反之， 如果支持度很高，置信度很低，则说明该规则不可靠。如果不考虑关联规则的 支持度和置信度，那么在数据库中存在非常多的关联规则。事实上，人们一般 第二章关联规则数据挖掘 只对那些满足一定的支持度和置信度的关联规则感兴趣。因此，为了发现有意 义的关联规则，需要由用户给定两个基本阂值：最低支持度和最低置信度。 有关定义如下所述： 定义2 1 项目( i t e m ) ：交易数据库中的一个属性字段，每个字段有一定的取 值范围。对一超级市场来讲，项目一般是指一次交易中的一个物品。 定义2 2 交易( t r a n s a c t i o n ) ：某个客户在一次交易中，发生的所有项目的集 合。 定义2 3 项目集( i t e m s 哟：包含若干个项目的集合，简称项集。 定义2 4k 一项集：对于项集x ，如果x 中包含有k 个项目，则x 称为k - 项集。例如项集x = a ，b ) 就是一个2 一项集。 定义2 5 支持度( s u p p o r t ) ：称交易数据库d 中包含项目集x 的交易的个数 与d 中总的交易个数之比为x 在d 中的支持度。把x 的支持度记作s u p ( x ) ， 而关联规则x j y 的支持度则记作s u p ( x j y ) ，具体描述是： s u p ( x j y ) 斗( x u y ) 定义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 l v ) s u p ( x ) 。把规则x j y 的置信度记作o o n f ( x y ) 。 事实上，置信度即是指在出现了项目集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 o 对于满足最低支持度和最低置信度要求的关联规则称为强规则。 定义2 9 支持数：d 中包含项目集x 的事务t 的个数，称为x 在d 中的 支持数( s u p p o r tc o u n t ) ，简记为c o u n t 。 设d 中包含的事务数表示为l d | ，根据以上支持度和支持数的定义，可以得 基于模糊集理论的关联规则数据挖妊l | 研究 出某项目集x 的支持数与支持度的关系是c o u n t = s u p p o r t x p i ，另外与最低支持 度相对应，把支持数定义为最低支持数( m i n i m u ms u p p o r tc o u n t ) ，简记为 m i n c o u n t ，它和最低支持度的关系是m i n c o u n t - - m i n s u p xi d i 定义2 1 0 频繁项目集：若项集x 的支持度不小于最低支持度，则称x 为 频繁项目集，即x 满足最低支持度要求。若某一项目m 满足最低支持度要求， 则称m 为频繁项目，所有频繁项目的集合称为频繁1 一项集，记为l 1 ；满足最低 支持度要求的k 一项集称为频繁k - 项集，所有频繁k 一项集的集合记为l k 。 2 1 2 关联规则的分类 传统的关联规则挖掘形式是购物篮分析，但关联规则绝不仅此一种。可以 根据以下标准对这些关联规则进行分类： 1 根据关联规则所处理的具体值来进行分类 若一个规则仅描述数据项是否出现在这种情况间的联系，那么这种关联规 则就是一个布尔关联规则。例如规则( 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 - = 1 5 0 ( 2 1 ) 若一个规则描述的是定量数据项( 或属性) 之间的关系，那么它就是一个定 量关联规则。在这些规则中，数据项的定量数值可以划分为区间范围。例如规 则( 2 2 ) 就是一个定量关联规则。 a g e ( x ，“3 0 3 4 ”) a 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 根据规则中数据的维数来进行分类 若一个规则中的项或属性仅涉及一个维，那么它就是一个单维关联规则。 例如规则( 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 n t e r ”) ( 2 3 ) 若一个规则涉及到两个或更多个维，诸如属性a g e ，i n c o m e ，和b u y s 等等， 那么它就是一个多维关联规则。例如规则( 2 2 ) 就是一个多维关联规则。 3 ，根据规则描述内容所涉及的抽象层次来进行分类 些关联规则挖掘方法可以发现不同抽象层次的关联规则，例如挖掘出规 则( 2 4 ) 和( 2 5 ) 。 第二章关联规则数据挖掘 a g e ( x ，“3 0 3 4 ”) j b u y s ( x ，“i b m n o t e b o o kc o m p u t e r ”)( 2 4 ) a g e ( x ，“3 0 3 4 ”) j b u y s ( x ，“c o m p u t e r ”)( 2 5 ) 在规则( 2 4 ) 和( 2 5 ) 中属性b u y s 的数据项描述了涉及不同抽象层次的内容 ( “c o m p u t e r ”是“i b mn o t e b o o kc o m p u t e r ”的更高抽象层次) ，由于涉及多个 不同抽象层次概念，因此构成了多层关联规则。相反，如果在给定的规则集中， 规则不涉及不同抽象层的项或属性，仅涉及单一层次的概念，那么这样的关联 规则就称为单层关联规则。 4 根据关联挖掘的各种扩充 关联规则可扩展到其它数据挖掘应用领域，如进行分类学习或进行相关分 析( 即可以通过相关数据项出现或不出现来进行相关属性识别与分析) ，还可以 扩充到挖掘最大频繁模式【2 8 0 明和频繁闭项集，使用最大频繁模式和频繁闭项集 可以显著地压缩挖掘所产生地频繁项集数。 2 2 关联规则挖掘算法 2 2 1 关联规则的挖掘步骤 关联规则挖掘就是在事务数据库d 中找出满足用户给定的最低支持度 m i n s u p 和最低置信度m i n c o n f 要求的关联规则，整个挖掘过程可分解为以下两 步： 1 找出事务数据库d 中所有支持度大于等于用户指定最低支持度的项目 集，即频繁项目集。 2 利用频繁项目集生成所需要的关联规则。对每一个频繁项目集a ，找到 a 的所有非空子集a ，如果比率s u p p o a ( a ) s u p p o r t ( a ) _ m i n c o n f , 就生成关联规 则a j ( a - a ) ，s u p p o r t ( a ) s u p p o r t ( a ) 即规则a 毒( a - a ) 的置信度。 事实上，在挖掘关联规则的整个执行过程中第一个子问题是核心问题，寻 求频繁项目集的有效产生算法是问题的关键，而第二个子问题相对较为简单。 因此，在后面的阐述中我们主要对第一个子问题进行详细分析。 基于模糊集理论的关联规则数据挖捌研究 2 2 2 关联规则经典挖掘算法a p r i o r i 单维、单层、布尔关联规则挖掘是最简单形式的关联规则挖掘，其中最著 名最有影响的是由a g r a w a l 等人提出的a p o r i 算法。该算法是挖掘产生单维布 尔关联规则频繁项目集的经典算法，从其产生到现在对关联规则挖掘方面的研 究有着很大的影响。该算法利用一个逐层搜索的迭代方法来完成频繁项目集的 挖掘，这一迭代方法就是利用l 【- 项集来产生o 【+ 1 ) 一项集。具体的做法如下：首 先我出频繁1 项集，记为l l ，然后利用l l 来挖掘k ，即频繁2 一项集：如此不 断地循环下去直至不能找到频繁l 卜项集为止，其中在发现每个l k 的过程中需要 对整个事务数据库扫描一遍。 为了提高频繁项目集逐层产生的效率，a p r i o r i 算法利用了两个重要的性质， 用于压缩搜索的空间。 性质2 1 若x 为频繁项目集，则x 的所有子集都是频繁项目集。 性质2 2 若x 为非频繁项目集，则x 的所有超集均为非频繁项目集。 这两个性质是根据以下观察而得出的结论。根据定义，若一个项目集x 不 满足最低支持度m i n s u p ，则该项目集x 就不是频繁项目集，即s u p p o r t ( x ) m i n s u p ( 8 ) r e t u l r l ll 1 ： ( 9 ) e n d p r o c e d u r ea p r i o r i _ _ g e n ( i , ) ( 1 ) b e g i a ( 2 ) f o r e a c h i t e m s e t l l l k d o f o re a c hi t e m s e t1 2 l kd o b e g i n i f ( 1 l 【1 】= 1 2 【1 】) a ( 1 t 【2 = h 2 1