（计算机应用技术专业论文）关联规则在物流网站设计与实现上的应用.pdf

摘要 摘要 数据挖掘( d a t am i n i n g ) 作为数据库研究领域中的热点，正受到越来越多的关注，其任 务是从大量数据中发现有用的数据，提取隐含在其中的、人们事先不知道的但又可能有 用的信息和知识。数据挖掘是目前国际上数据库和信息决策领域的最前沿研究方向之 一，基于关联规贝j j ( a s s o c i a t i o nr u l e ) 的挖掘是其中一个重要的研究方法，具有重要的理 论价值和广泛的应用前景。 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关联系。从大量商务事物 记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和 贱卖分析。关联规则中最经典的算法是a p r i o r i 算法，但它有两个致命的性能瓶颈：多 次扫描事务数据库，需要很大的i o 负载、可能产生庞大的侯选集。基于项目集格空间 理论的i s s d m 算法很好地克服了a p r i o d 算法的缺点。 本文重点介绍了以下几方面的工作： ( 1 ) 数据挖掘现状研究。 ( 2 ) 对关联规则算法( 特别是a p r i o r i 算法，i s s d m 算法) 进行深入研究，并提出一 种高效的关联规则算法( i s s d m _ ) 。 ( 3 ) 完成大连物流网的设计与开发，包括初步设计、详细设计以及软件开发。大连 物流网主要包括海运中心、陆运中心、空运中心和后台管理系统等。本文的关联规则主 要以大连物流网为背景。所开发的系统现已正常运行。 ( 4 ) 在关联规则理论与研究的基础上，将改进后的算法应用于大连物流网系统，效 果良好。 关键词：数据挖掘；关联规则；a p r i o r i 算法；i s s d m 算法；i s s d m 一算法 大连交通大学t 学硕十学位论文 a b s t r a c t d a t am i n i n ga sd a t a b a s ef i e l d si nt h eh o t ，b e i n gm o r ec o n c e m e da b o u ti t sm a n d a t ef r o m t h el a r g ea m o u n t so fd a t af o u n du s e f u ld a t a , w h i c hi m p l i e df r o m ，p e o p l ed on o tk n o wi n a d v a n c eb u tp o t e n t i a l l yu s e f u li n f o r m a t i o na n dk n o w l e d g e d a t am i n i n gi st h ec u r r e n t i n t e r n a t i o n a ld a t a b a s e sa n di n f o r m a t i o no nt h ef o r e f r o n to fd e c i s i o n m a k i n gi nt h ed i r e c t i o no f o n eo ft h es t u d y ，b a s e do na s s o c i a t i o nr u l e se x c a v a t i o ni so n eo ft h ei m p o r t a n tr e s e a r c h m e t h o d sh a v ei m p o r t a n tt h e o r e t i c a lv a l u ea n db r o a da p p l i c a t i o np r o s p e c t s m i n i n ga s s o c i a t i o nr u l e si st h ed i s c o v e r yo fl a r g ea m o u n t so fd a t ac o l l e c t e di nt h e c o r r e l a t i o nb e t w e e ni n t e r e s t i n go rr e l e v a n tc o n n e c t i o n b u s i n e s sr e c o r d sf r o mah o s to ft h i n g s f o u n di n t e r e s t i n gr e l a t i o n s h i p sc a nh e l pm a n y b u s i n e s s d e c i s i o nm a k i n g ，s u c ha s t h e c l a s s i f i c a t i o no fd e s i g n ，a n dt h ec r o s s s h o p p i n ga ta na n a l y s i s a s s o c i a t i o nr u l e si nt h e c l a s s i c a l a l g o r i t h mi sa p r i o r ia l g o r i t h m ，b u ti t h a st w of a t a lp e r f o r m a n c eb o t t l e n e c k s ： s c a n n i n gs e r v i c ed a t a b a s er e p e a t e d l yt a k eag o o dd e a lo fi ol o a da n dm a yg e n e r a t eh u g e i t e m s e t s b a s e do ns p a c ep r o j e c t sl a t t i c et h e o r yi s s - d ma l g o r i t h mg o o da p r i o r ia l g o r i t h m o v e r c o m e st h es h o r t c o m i n g s t h i sp a p e rf o c u s e so nt h ef o l l o w i n ga s p e c t so fw o r k ： ( 1 ) r e s e a r c ho nd a t am i n i n g ( 2 ) t h ea s s o c i a t i o nr u l e sa l g o r i t h m ( e s p e c i a l l ya p r i o r ia l g o r i t h m s ，i s s - d ma l g o r i t h m ) f o rf u r t h e rs t u d ya n dp r o p o s ea ne f f i c i e n ta l g o r i t h ma s s o c i a t i o nr u l e s ( i s s d m 一) ( 3 ) t h ed e s i g na n dd e v e l o p m e n to fd a l i a nd r i f t - n e t s ，i n c l u d i n gp r e l i m i n a r yd e s i g n ， d e t a i l e dd e s i g na n ds o f t w a r ed e v e l o p m e n t d a l i a no fd r i f t n e tm a i n l yi n c l u d e sm a r i t i m ec e n t e r ， g r o u n dt r a n s p o r t a t i o nc e n t e na n da i rc a r g oc e n t e ra n dm a n a g e m e n ts y s t e m s t h i sp a p e r m a i n l yt ot h ea s s o c i a t i o nr u l e so nd a l i a nd r i f t n e ta st h eb a c k g r o u n d t h ed e v e l o p e ds y s t e mi s n o wi nn o r m a lo p e r a t i o n ( 4 ) i nt h e o r y ，a n dr e s e a r c ha s s o c i a t i o nr u l e so nt h eb a s i so ft h em o d i f i e da l g o r i t h mu s e d i nd a l i a no fd r i f t n e ts y s t e m ，g o o dr e s u l t s k e yw 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 ；a p r i o r ia l g o r i t h m ；i s s d ma l g o r i t h m ； i s s - d m 一1a l g o r i t h m 绪论 绪论 数据挖掘( d a t am i n i n g ) ，又称为数据库中的知识发现( 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 ) ，就是从大量数据中获取有效的、新颖的、潜在有用的、最终可理解的 模式的非平凡过程，简单的说，数据挖掘就是从大量数据中提取或“挖掘 知识。数据 挖掘的主要技术为关联规则、聚类、粗糙集、神经网络和遗传算法等。 关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由a g r a w a l 等人提出的 ( 1 9 9 3 ) | 。最初提出的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据 库中不同商品之间的联系规则。这些规则刻画了顾客购买行为模式，可以用来指导商家 科学地安排进货、库存以及货架设计等。之后诸多的研究人员对关联规则的挖掘问题进 行了大量的研究【2 2 4 l 。他们的工作涉及到关联规则的挖掘理论的探索、原有算法的改进 和新算法的提出、并行关联规则挖掘( p a r a l l e la s s o c i a t i o nr u l em i n i n g ) 以及数量关联规则 挖掘( q u a n t i t i v ea s s o c i a t i o nr u l em i n i n g ) 等问题。在提高挖掘规则算法的效率、适应性、 可用性以及应用推广等方面，许多学者进行了不懈的努力。关联规则的算法有很多，经 典的关联规则算法有a p r i o r i 算法，随着新的挖掘理论的产生，陆续提出了c l o s e 算法、 f p t r e e 算法、i s s d m 算法等。 a 研o r i 算法有两个致命的性能瓶颈： ( 1 ) 多次扫描事务数据库，需要很大的i o 负载。对每次k 循环，侯选集c k 中的每 个元素都必须通过扫描数据库一次来验证其是否加入l k 。假如有一个频繁大项集包含 1 0 个项的话，那么就至少需要扫描事务数据库1 0 遍。 ( 2 ) 可能产生庞大的侯选集。由l k 1 产生k 侯选集c k 是指数增长的，例如1 0 4 的1 一频繁项集就有可能产生接近1 0 。7 个元素的2 一侯选集。如此大的侯选集对时间和主存 空间都是一种挑战。 i s s d m 算法是基于项目序列集格理论的，不仅具有严格的理论基础，而且是一个 通过一次事务数据库扫描就可以获得最大频繁项目序列集的高效算法。i s s d m 算法的 优势还表现在它仅使用i s s 和i s s * 两个线性的数据结构，相比f p t r e e 算法存储结构简 单，而且通过及时裁减提高了内存中i s s 和i s s * 的利用率。因此本论文主要研究该算法 的改进，并应用于大连物流网系统。 大连交通大学：f 学硕十学位论文 第一章课题概述 1 1 数据挖掘技术的产生及研究现状 科技的进步，特别是信息产业的发展，把我们带入了一个崭新的信息时代。随着计 算机应用的普及和数据库技术的不断发展，数据库管理系统的应用领域越来越广。最近 几十年中，数据库中存储的数据量急剧增加。与此同时，计算机硬件性能越来越高，并 行多处理机技术也已经成熟，管理大量数据的数据库管理系统以及各类数据仓库已经能 够支持存储、检索如此规模的数据。但目前的数据库系统可以高效地实现数据的录入， 查询，统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未 来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏” 的现象。 计算机技术的另一领域人工智能自1 9 5 6 年诞生之后取得了重大进展。经历了 博弈时期，自然语言理解，知识工程等阶段，目前的研究热点是机器学习机器学习是用 计算机模拟人类学习的一门科学，比较成熟的算法有神经网络、遗传算法等。 用数据库来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后的知识， 这两者的结合促成了数据挖掘的产生。数据挖掘也称为数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ) 。实际上，数据挖掘是一门交叉性学科，涉及到人工智能、数据 库、统计学( 机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、高 性能计算、专家系统) 等多个领域。数据挖掘发现的知识可以用在信息管理、过程控制、 科学研究、决策支持等许多方面。 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科 学基金首次支持我们对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相 开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究 所、空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在 知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究， 华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等 单位开展了对关联规则开采算法的优化和改造；南京大学、四j i i 联合大学和上海交通大 学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。 最近，g a r t n e rg r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未来三到五 年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据挖掘 列为未来五年内投资焦点的十大新兴技术前两位。根据最近g a r t n e r 的h p c 研究表明， 4 第一章课题概述 “随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需要采用新技术 来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增长点 。 1 2 关联规则 当前，数据挖掘的主要技术为关联规则、聚类、粗糙集、神经网络和遗传算法等， 其中关联规则是比较重要的一种，也是最活跃的一个分支。关联规则表示数据库中一组 对象之间某种关联关系的规则。例如，关联规则可以表示为“购买了项目a 和b 的顾 客中有9 5 的人又买了c 和d ”。从这些规则可以找出顾客购买的行为模式，可以应用 于商品货架设计、生产安排、针对性的市场营销等。 1 9 9 4 ，a g r a w a l 等在先前工作的基础上，完善了一个称为a p r i o r i 的关联规则挖掘算 法【2 】。这个算法一直作为经典的关联规则挖掘算法被引用，以后诸多的研究人员对关联 规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随 机采样、规则约减、改变存储结构等，提高算法的效率。近年，随着新的挖掘理论的产 生，提出了许多新的算法，如基于关闭项目集挖掘理论的c l o s e 算法、基于项目序列集 格空间理论的i s s d m 算法。关联规则应用于许多领域，如金融、电信、零售业和医学 植 守o 1 3 本文的主要工作 本文的研究工作源于上述的背景，目的是对数据库知识发现进行深入的研究。主要 围绕关联规则对数据挖掘理论和方法进行了以下几方面的工作： ( 1 ) 归纳了数据挖掘技术的总体研究情况，包括数据挖掘的概念、挖掘的过程、分 类和主要技术手段。 ( 2 ) 对关联规则算法( 特别是a p r i o r i 算法，i s s d m 算法) 进行深入研究，并提出一 种高效的关联规则算法( i s s d m 。1 ) 。 ( 3 ) 完成大连物流网的设计与开发，包括初步设计、详细设计以及软件开发。大连 物流网主要包括海运中心、陆运中心、空运中心和后台管理系统等。本文的关联规则主 要以大连物流网为背景。所开发的系统现已正常运行。 ( 4 ) 在关联规则理论与研究的基础上，将改进后的算法应用于大连物流网系统，效 果良好。 本章小结 本章主要对课题进行了概要论述并提出了本文的主要工作。 大连交通人学j r 学硕十学位论文 第二章数据挖掘 数据挖掘作为一个较新的研究领域，许多概念和技术是逐步发展起来的。以下着重 阐述与数据挖掘有关的概念和技术。 2 1 数据挖掘概述 2 1 1 数据挖掘的定义 数据挖掘的概念分为广义和狭义两种，目前比较公认的是f a y y a d l 2 5 】等人提出的广 义数据挖掘概念，具体如下： 定义2 1 数据挖掘( d a t am i n i n g ) 又称数据库中的知识发现( 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 ) ，是指从大量数据中发现有效的、新颖的、具有潜在作用的、最 终可被理解的模式的非平凡过程。 数据：指一个有关事实f 的集合，用以描述事物的基本信息。如关系数据库中记录 的集合。 模式：语言l 中的表达式e ，e 所描述的数据是集合f 的一个子集f e 。f e 表明数据 集f 中的数据具有特性e 。作为一个模式，e 比枚举数据子集f e 简单。 非平凡过程：k d d 是由多个步骤构成的处理过程，包括数据预处理、模式提取、 知识评估及过程优化。所谓非平凡是指具有一定程度的智能性和自动性，而绝不仅仅是 简单的数值统计和计算。 有效性( 可信性) ：从数据中发现的模式必须有一定的可信度，通过函数c 将表达式 映射到度量空间m c ，c 表示模式e 的可信度，c = c ( e ，f ) 。其中e l ，e 所描述的数据 集合f e c f 。 新颖性：提取出的模式必须是新颖的。模式是否新颖可以通过两个途径来衡量：一 是通过比较当i j 得到的数据和以前的数据或期望得到的数据来判断；二是通过对比发现 的模式与已有模式的关系来判断。通常用一个函数来表示模式的新颖程度n ( e ，f ) ，该 函数的返回值是逻辑值或是对模式e 的新颖程度的一个判断数值。 潜在作用：指提取出的模式将来会被实际运用。 可理解性：发现的模式应该能够被用户理解，以帮助人们更好地了解和使用数据库 中的信息，这主要体现在简洁上。要想让一个模式更容易地被人们理解并不是一件容易 的事，需要对其简单程度进行度量。 6 第二章数据挖掘 2 1 2 数据挖掘的任务 根据定义我们可以知道，数据挖掘的任务就是从数据中发现模式。根据模式的实际 作用将数据挖掘需要挖掘的模式主要分为以下3 种： ( 1 ) 关联模式 关联模式又称关联规贝, u ( a s s o c i a t i o nr u l e ) ，它反映一个事件和其他事件之间依赖或 关联的知识。主要目的是数据间的关联性。世界上存在着事物间的多种相关性，如下雪 则打车的比较多，如购买面包后大都购买牛奶等，而这些相关性有时蕴含在内部，人们 不易发现，而现在可以通过关联规则找出其内部相关性并以模式或规则形式将其表现出 来。关联规则的挖掘可分为两步：第一步找出所有的频集，这些项集出现的频繁性至少 和预定义的最小支持度一样；第二步由频集产生强关联规则，这些规则必须满足最小支 持度和最小可信度。挖掘关联规则的总体性能由第一步决定，第二步相对容易实现。关 联规则常用的算法是a p r i o r i 算法，这是一种统计型算法，它效率高、效果好，是目前 最为流行的挖掘算法之一。目前以该算法为基础推广产生了很多种能适应不同环境的扩 充的a p r i o r i 算法。 ( 2 ) 分类模式 分类( c l a s s i f i c a t i o n ) 是对一组已分类数据为对象作分析，找到每一类的规律称分类规 则或简称分类。目的是提出一个分类函数或分类模型( 即分类器) ，通过分类器将数据对 象映射到某一个给定的类别中。分类方法的主要工作是如何由不同表象进一步挖掘出其 内在性质的不同。分类法中的算法有很多，有决策树方法、粗糙集算法、贝叶斯算法、 人工神经网络以及遗传算法等。 ( 3 ) 聚类模式 聚类( c l u s t e r i n g ) 是将数据对象进行分组并将相似对象归为一类的过程。数据聚类是 将数据的对象分成几个群体，在每个群体内部对象之间具有较高的相似性，而不同群体 的对象之间则具有较高相异性或较低相似性，它的目的是使属于同一类别的个体之间的 距离尽可能地小，而不同类别的个体问的距离尽可能地大。一般来说，一个群体称为一 个类，如果对一个对象集合事先并不知道对象所属的类，这就需要定义一个衡量对象之 间相似性的标准，并通过一定的算法用于决定类。例如，在商业领域，聚类可以帮助市 场营销人员分析客户数据库，发现不同类型的客户群，按照购买习惯分类并刻画客户群 的特征：在生物学界，聚类可以用于动物和植物分类，对具有功能的基因进行分类，了 解种群的内在结构。聚类法中的算法也很多，有遗传算法、划分法、层次法、基于密度 方法、基于网格方法等。 7 大连交通人学t 学硕十学位论文 2 1 3 数据挖掘的过程 数据挖掘是一个反复迭代的人机交互处理过程。该过程需要经历多个步骤，并且很 多决策需要用户提供。从宏观上看，数据挖掘主要由三个部分组成，即数据准备、挖掘 信息和解释评估，具体步骤参见图2 1 。 目标数据 己预处理 数据 图2 1 数据挖掘过程 f i g 2 1p r o c e s so fd a t am i n i n g 知识 ( 1 ) 确定挖掘主题 数据挖掘时首先要明确挖掘主题，它包括挖掘的要求以及需要达到的目标，这是数 据挖掘首先要明确的内容。 ( 2 ) 数据准备 数据挖掘的对象是数据，因此在数据挖掘前必须对所挖掘的数据作处理，数据整理 包括以下3 部分： 数据选取 数据选取的目的是确定目标数据，根据用户的需要从原始数据库中选取相关数据或 8 i 解释评价i | 数据挖掘 p ：、 变换 卜一 _ 弃繇r | | | | | | 第二章数据挖掘 样本。 数据预处理 对中选出的数据进行再处理，检查数据的完整性及数据一致性，消除噪声，滤除 与数据挖掘无关的冗余数据等。 数据转换 将数据转换成一个分析模型，建立一个真正适合挖掘算法的分析模型。 ( 3 ) 挖掘信息 对所得到的经过转化的数据进行挖掘。主要由以下几部分构成： 确定挖掘的任务类型 选择合适的挖掘技术 如分类模型常由有指导的神经元网络或归纳技术来实现：聚类常用聚类分析技术； 关联分析使用关联发现和序列发现技术等。 选择算法。 根据选定的技术选择具体的算法，如a p r i o r i 算法是关联分析中常用的算法。 进行挖掘 利用选定的算法从数据集合中抽取出隐藏的模式。 结果展示 可以通过多种可视化形式表示，主要工作是选择合适的展示工具，使结果能按不同 需要充分展示。 ( 4 ) 解释评估 根据最终用户的决策目的对提取的信息进行分析，把最有价值的信息区分出来，并 且通过决策支持工具提交给决策者。因此，这一步骤的任务不仅是把结果表达出来( 例 如采用信息可视化方法) ，还要对信息进行过滤处理。如果不能令决策者满意，需要重 复以上数据挖掘的过程。可见，数据挖掘过程可能需要多次的循环反复，每一个步骤一 旦与预期目标不符，都要回到前面的步骤，重新调整，重新执行。 2 2 数据挖掘的特点 数据挖掘的特点有三个方面。 ( 1 ) 数据挖掘的数据量是巨大的。因此，如何高效率地存取数据，如何根据一定应 用领域找出数据关系即提高算法的效率，以及是使用全部数据还是部分数据，都成为数 据挖掘中必须考虑的问题。 ( 2 ) 数据挖掘面临的数据常常是为其他目的而收集的数据，这就为数据挖掘带来了 9 大连交通人学t 学硕士学位论文 一定的困难，即一些很重要的数据可能被疏漏或丢失。因此，未知性和不完全性始终贯 穿数据挖掘的全过程。 ( 3 ) 数据挖掘常常要求算法主动地提示一些数据的内在关系。新颖性是衡量一个数 据挖掘算法好坏的重要标准。 显然，数据挖掘有别于传统的数据分析方法，它常常是在没有前提假设的情况下， 从事信息的挖掘与知识提取。在保险投资风险管理中，如果能够对以往和当前的投资组 合收益情况进行充分的数据挖掘，就可能发现一些隐藏在组合内部或者不同时期组合之 间的特殊关系，给新的投资组合和风险管理提供重要的参考。数据挖掘已经成为风险管 理的重要工具之一。 2 3 数据挖掘技术的应用 数据挖掘的应用十分广泛，比较典型的领域包括： ( 1 ) 在金融领域中的应用 多数银行和金融机构都提供丰富多样的储蓄，信用，投资，保险等服务。他们产生 的金融数据通常比较完整、可靠，这对系统化的数据分析和数据挖掘相当有利。在具体 的应用中，采用多维数据分析来分析这些数据的一般特性，观察金融市场的变化趋势； 通过特征选择和属性相关性计算，识别关键因素，进行贷款偿付预测和客户信用分析； 利用分类和聚集的方法对用户群体进行识别和目标市场分析；使用数据可视化、链接分 析、分类、聚类分析、孤立点分析、序列模式分析等工具侦破洗黑钱和其他金融犯罪行 为。 ( 2 ) 在电信业中的应用 现在的电信业已不再单纯地提供市话和长话服务，他的业务范围涵盖语音、传真、 寻呼、移动电话、图像、e m a i l 、计算机和w e b 数据传输，以及其他数据通信服务。随 着电信业的开放和相关技术的发展，电信市场正在迅速扩张且竞争越发激烈，此时，利 用数据挖掘技术来帮助理解商业行为、确定电信模式、捕捉盗用行为、更好的利用资源 和提高服务质量是非常有必要的。 ( 3 ) 在零售业中的应用 零售业是数据挖掘的主要应用领域，这是因为零售业积累了大量的销售数据，如顾 客购买史记录、货物进出、消费与服务记录以及流行的电子商务等等都为数据挖掘提供 了丰富的数据资源。零售数据挖掘有助于划分顾客群体，使用交互式询问技术、分类技 术和预测技术，更精确地挑选潜在的顾客；识别顾客购买行为，发现顾客购买模式和趋 势，进行关联分析，以便更好地进行货架摆设；改进服务质量，获得更好的顾客忠诚度 l o 第二章数据挖掘 和满意程度：提高货品的销量比率，设计更好的货品运输与分销策略，减少商业成本； 寻找描述性的模式，以便更好地进行市场分析等等。口 ( 4 ) 在医学上的应用口 近年来，生物医学研究有了迅猛地发展，从新药的开发到癌症治疗的突破，到通过 大规模序列模式和基因功能的发现，进行人类基因的识别与研究。在人类基因研究领域 具有挑战性的问题是从中找出导致各种疾病的特定基因序列模式。由于数据挖掘中已经 有许多有意义的序列模式分析和相似检索技术，因此数据挖掘成为d n a 分析中的强有 力工具。利用数据挖掘技术在d n a 数据的分析研究中可以进行d n a 序列间的相似搜 索和比较，对同时出现的基因序列的相关分析，遗传研究中的路径分析等。近期d n a 分析的研究成果已经促成了对许多疾病和残疾基因成因的发现，以及对疾病诊断、预防 和治疗的新药物、新方法的发现。 ( 5 ) 教育方面 分析学生的选课情况，制定适当的选课计划，满足学生的要求。分析教师的年龄、 学历、职称等与评学结果的关系，制定教学方案，提高教学质量。 ( 6 ) 网站方面 网站作为电子商务的平台，它的设计直接影响电子商务的正常开展。通过网络挖掘 我们可以从用户的访问信息中发现有价值的信息，从而指导网站设计者更新网站结构与 内容，更好地与客户交流。而且可以进一步实施针对个性化用户或用户群的访问界面， 从而开展有针对性地电子商务 2 6 , 2 7 。 ( 7 ) 过程控制 协助管理大量变量之间的相互作用。通过分析能识别出某些不正常的数据分布，协 助查找制作和装配操作过程中的变化情况和各种影响因素，从而协助质量工程师很快地 注意到问题的发生范围和采取改正措施。 总之，d m 正广泛应用于各行各业，并发挥着重要作用。 2 4 数据挖掘面临的问题 数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力将会不停 地促进它的发展每年都有新的数据挖掘方法和模型问世，人们对它的研究正日益广泛 和深入。尽管如此，数据挖掘技术仍然面临着许多问题和挑战，这也为数据挖掘的未来 的发展提供了更大的空间。 ( 1 ) 数据挖掘的基本问题就在于数据的数量和维数，数据结构也因此显的非常复杂， 如何进行探索，选择分析变量，也就成为首先要解决的问题。 大连交通大学t 学硕士学位论文 ( 2 ) 面对如此大的数据，现有的统计方法等都遇到了问题，我们直接的想法就是对 数据进行抽样，那么怎么抽样，抽取多大的样本，又怎样评价抽样的效果，这些都是值 得研究的难题。 ( 3 ) 既然数据是海量的，那么数据中就会隐含一定的变化趋势，在数据挖掘中也要 对这个趋势做应有的考虑和评价。 ( 4 ) 各种不同的模型如何应用，其效果如何评价。不同的人对同样的数据进行挖掘， 可能产生不同的结果，甚至差异很大，这就涉及到可靠性的问题。 ( 5 ) 当前互联网的发展迅速，对w e b 数据进行挖掘，发现关于w e b 内容、w e b 使 用和w e b 动态情况的有用知识，也已成为数据挖掘中的一个非常具有挑战性的领域。 ( 6 ) 数据挖掘能从不同的角度、不同的抽象层上看待数据，这会潜在地影响到数据 的私有性和安全性。研究数据挖掘可能导致非法数据入侵，同样是实际应用过程中需要 解决的问题。 ( 7 ) 数据挖掘的结果是不确定的，要和专业知识相结合才能对其做出判断。 本章小结 本章介绍了数据挖掘的产生背景，数据挖掘的基本概念，数据挖掘的基本任务，详 细介绍了数据挖掘的过程和相关研究领域，并阐述了数据挖掘面临的问题。 1 2 第三章关联规则 第三章关联规则帚二早大驮觑火u 在数据挖掘的知识模式中，关联规则是比较重要的一种，也是最活跃的一个分支。 最早由a g r a w a l 1 j 等于1 9 9 3 年提出，随即引起广泛关注。关联规则表示数据库中一组对 象之间某种关联关系的规则。例如，关联规则可以表示为“购买了项目a 和b 的顾客 中有9 5 的人又买了c 和d ”。从这些规则可以找出顾客购买的行为模式，可以应用于 商品货架设计、生产安排、针对性的市场营销等。 3 1 关联规则挖掘概述 3 1 1 关联规则的基本概念 令i = ( i l ，i 2 ，i m ) 是一个符号的集合，其中的每一个符号，我们称之为一个 项目( i t e m ) 。令d = t l ，t 2 ，t n ) ，其中t i c i ，称为为一个交易或事务( t r a n s a c t i o n ) ， 称d 为交易集或简称数据库，反映了数据关联中的挖掘对象。 定义3 1 关联规贝j j ( a s s o c i a t i o nr u l e s ) 关联规则是形如x j y 规则，其中x _ c i ，y _ c i ，并且x n y = 。 衡量关联规则是否有意义的标准主要有两个：支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 。 定义3 2 关联规则的支持度( s u p p o r t ) 项目集x 在d 上的支持度( s u p p o r t ) 是指包含x 的事务( 记为口，) 在d 中所占的百分 比。即： s u p p o a ( x ) = 斋x 1 0 0 ( 3 1 ) i l 若s u p p o r t ( x ) 不小于用户指定的最小支持度( m i n s u p p o r t ) ，则称x 为频繁项目集( 或 大项目集) ，否则称x 为非频繁项目集( 或小项目集) 。 定理3 3 频繁项目集的子集是频繁项目集；非频繁项目集的超集是非频繁项目集。 即： 若x y ，如果y 是频繁项目集，则x 也是频繁项目集； 若x cy ，如果x 是非频繁项目集，则y 也是非频繁项目集。 定义3 4 关联规则的支持度( c o n f i d e n c e ) 关联规则x j y 的置信度指d 中包含x 的事务的同时也包含y 的百分比。即： c o n f i d e n c e ( x = y ) ：s u pp o r t ( xuy ) 10 0 ( 3 2 ) 、7 s u p p o r t ( x ) 、 7 1 3 大连交通大学t 学硕士学位论文 定义3 5 强关联规则、最小支持度( m i n s u p p o r t ) 、最小置信度( m i n c o n f i d e n c e ) 给定d 和关联规则x jy ，并给定m i n s u p p o r t e ( 0 ，1 ) 和m i n c o n f i d e n c e e ( o ，1 ) ，当 s u p p o r t ( x m i n s u p p o r t 且c o n f i d e n c e ( xj m i n c o n f i d e n c e 时，称关联规则x y 为数据集d 上的强关联规则，简称强关联规则。最小支持度和最小置信度是由用户自定 义的阙值。 3 1 2 关联规则的种类 ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系； 而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理， 将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以 包含种类变量。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多维 的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单 个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。 3 2 关联规则的算法 ( 1 ) 多循环方式挖掘算法 核心思想是“层次算法( 1 e v e l w i s ea l g o r i t h m s ) ”，顾名思义是算法将整个挖掘过程 分成若干层次，待各层次挖掘完成，再组合成最后的结果。这类算法包括a g r a w a l 等人 提出的a p r i o r i 、a i s 、a p r i o r i t i d 和a p r i o r i h y b r i d ；p a r k 等人提出的d h p ；s a v a d e r e 等人 提出的p a r t i t i o n ；t o i v o n e n 提出的抽样算法s a m p l i n g ；f p g r o w t h ；d i c 等。其中最有效 和最有影响的算法包括a p r i o r i 和f p g r o w t h 算法。 a p r i o r i 算法，其核心是基于两阶段频集思想的递推算法。首先产生频繁l 一项集l l ， 然后是频繁2 项集l 2 ，直到有某个r 值使得l r 为空，这时算法停止。这里在第k 次循 环中，过程先产生候选k 项集的集合c k ，c k 中的每一个项集是对两个只有一个项不同 的属于l k 1 的频集做一个( k 2 ) 连接来产生的。c k 中的项集是用来产生频集的候选集， 最后的频集l k 必须是c k 的一个子集。c k 中的每个元素需在交易数据库中进行验证来决 定其是否加入l k ，这罩的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能 1 4 第三章关联规则 很大的交易数据库，即如果频集最多包含1 0 个项，那么就需要扫描交易数据库1 0 遍， 这需要很大的i o 负载。 可能产生大量的候选集，以及可能需要重复扫描数据库，是a p r i o r i 算法的两大缺 点。 f p g r o w t h 算法：针对a p r i o r i 算法的固有缺陷，j h a n 等提出了不产生候选挖掘频 繁项集的方法_ f p g r o w t h 频集算法 h i 。采用分而治之的策略，在经过第一遍扫描之后， 把数据库中的频集压缩进一棵频繁模式树( f p t r e e ) ，同时依然保留其中的关联信息，随 后再将f p t r e e 分化成一些条件库，每个库和一个长度为1 的频集相关，然后再对这些 条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法，使得一个 f p t r e e 可以放入主存中。实验表明，f p g r o w t h 对不同长度的规则都有很好的适应性， 同时在效率上较之a p r i o r i 算法有巨大的提高。 散列( d h p 算法) ：该算法由p a r k 等在1 9 9 5 年提出1 2 8 1 。通过实验发现寻找频繁项集 的主要计算是在生成频繁2 项集l 2 上，p a r k 就是利用这个性质引入散列技术来改进产 生频繁2 项集的方法。 其基本思想是：当扫描数据库中每个事务，由c l 中的候选1 项集产生频繁1 项集 l l 时，对每个事务产生所有的2 项集，将它们散列到散列表结构的不同桶中，并增加对 应的桶计数，在散列表中对应的桶计数低于支持度阈值的2 项集不可能是频繁2 项集， 可从候选2 项集中删除，这样就可大大压缩了要考虑的2 项集。 p a r t i t i o n ：s a v a d e r e 等设计了一个基于划分的算法1 3 1 i ，这个算法先把数据库从逻辑 上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生 的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小 选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由 每一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并 行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束 后，处理器之间进行通信来产生全局的候选k 一项集。通常这里的通信过程是算法执行时 间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的 方法还有在多处理器之间共享一个杂凑树来产生频集。 s a m p l i n g ：基本思想是在给定数据的一个子集挖掘。对前一遍扫描得到的信息，仔 细地组合分析，可以得到一个改进的算法，m a n n i l a 等先考虑了这一点1 3 2 1 ，他们认为采 样是发现规则的一个有效途径。随后又由t o i v o n e n 进一步发展了这个思想1 3 引，先使用 从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据 库的剩余部分验证这个结果。t o i v o n e n 的算法相当简单并显著地减少了i o 代价，但是 大连交通人学工学硕士学位论文 一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲( d a t as k e w ) 。分布在同 一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导 致的是采样5 的交易数据所花费的代价可能同扫描一遍数据库相近。 ( 2 ) 增量式更新挖掘算法 包含两种情况：第一，数据库中记录发生变化( 增加或删除) 时的更新；d w c h e n g 等给出层次算法所对应的更新算法f u p ，在此基础上，提出了f u p 2 算法，从而不仅可 以处理交易的增加，而且还可以处理交易的删除或修改。第二，在关联规则的度量( 支 持度、置信度、兴趣度等) 发生改变时的更新。冯玉才等对此种情况进行了研究，提出 了相应的算法i u a ，p i u a 。f e l d m a n 提出了一种称为b o r d e r 算法的关联规则更新技术。 在用户指定的最低支持度为绝对数且不变的条件下，该算法只需考察所有真子集均为频 繁项目集，而本身却不是频繁的项目集( 这些项目集称为b o r d e r ) 。但是该算法仍然需要 存储相关的频繁项目集结果，以减少关联规则的更新代价。 算法f u p1 3 9 i 的基本思想为：对任意一个k ( k 1 ) 项集，若其在d b 和d b 中都是大项 集，则其一定是大项集；若其在d b 和d b 中都是弱项集，则其一定是弱项集；若其仅 在d b ( d b ) 中是大项集，则其支持数应加上其在d b ( d b ) 中的支持数以确定它是否为大项 集。算法f u p 假设在d b 中发现的大项集l = w t = l l ( n 为l 中最大元素的元素个数) 已被 保存下来。它需要对d b 和d b 进行多次扫描，在第1 次扫描中，算法先扫描d b ，将l l 中的元素仍为d b ( d b ) 中的大项集的元素记入l t l ，并生成候选大l 项集c l ，c l 中的元素 为d b 中的大l 项集且不包含在l l 中；然后扫描d b 以决定c l 中的元素是否为d b ( d b ) 中的大项集，并将是d b ( d b ) 中的大项集的元素记入l t l 中。在第k ( k 1 ) 次扫描前，先对 l k - l 用a p r i o r ig e n 0 函数生成候选大k 项集c k