（计算机应用技术专业论文）数据挖掘算法库体系结构的研究.pdf

摘要 摘要 伴随着数据库技术的快速发展以及数据获取技术手段的提高，数据信息量急 剧膨胀并呈现多样化趋势，如何揭示这些数据背后所隐含的重要信息成为人们关 注的焦点。在这种情形下，数据挖掘技术应运而生。经过二十多年的时间，数据 挖掘系统得到了很大发展，作为数据挖掘系统的核心部件，算法库也获得了较大 的进步，但其目前在通用性、扩展性等方面仍存在不足：首先，数据挖掘系统之 间无法实现算法库共享：其次，当挖掘系统更新时，无法对算法库进行升级；最 后，对算法库的二次开发要做很多重复性的工作，从而造成大量人力物力的浪费 以及开发成本的增加。 针对上述问题，在分析现有数据挖掘系统算法库的基础上，基于可复用性思 想，提出一种独立于任何数据挖掘系统的算法库d m a l ( d a t am i n i n ga l g o r i t h m s l i b r a r y ) 模型。首先，从技术可行性上对该算法库模型进行论证；其次，基于可 扩展性思想，设计算法库的总体结构；再次，在算法库的具体设计方面，利用元 数据技术以及x m l 技术对算法及其参数信息进行管理，便于对其进行控制，从 而实现算法库与挖掘系统其他组件之间的灵活交互；利用映像和元对象协议对算 法进行匹配调用，较好地体现算法库的可扩展性及可复用性。 在数据挖掘算法库d m a l 模型的基础上，构建算法库原型系统。首先，利 用u m l 可视化建模思想，分析设计算法库原型的用例图、静态行为模型以及动 态行为模型；然后，采用j a v a 编程语言、m v c 设计模式，在开源软件e c l i p s e 平台上，开发图形界面化算法库原型系统，实现算法的示例调用和管理，提供友 好的用户界面，便于对系统进行管理维护和升级。通过原型的实现，为进一步实 现数据挖掘算法库系统的强大功能提供一定的参考价值。 关键词数据挖掘；数据挖掘算法库；体系结构；可扩展性 a b s t r a c t a b s t r a c t w i t ht h ef a s td e v e l o p m e n to f d a t a b a s et e c h n o l o g ya n dt h ei m p r o v e m e n to f m e a n s o fa c c e s st od a t a ，d a me x p a n d sr a p i d l ya n dp r e s e n t sd i v e r s i f i c a t i o nt r e n d u n d e rt h e c o n d i t i o n , p e o p l es t a r tt of o c u so nh o w t oo p e no u tt h eh i d d e ni m p o r t a n ti n f o r m a t i o n b e h i n dt h e s ed a t a ，t h u sd a t am i n i n gt e c h n o l o g ye m e r g e sa st h et i m e sr e q u i r e d u r i n g t h ep a s tt w e n t i e sy e a r s ，d a t am i n i n gs y s t e m sh a v ed e v e l o p e dg r e a t l y a st h ec o r e c o m p o n e n to ft h e s es y s t e m s , d a t am i n i n ga l g o r i t h m sl i b r a r ya l s og o tm u c hp r o g r e s s ， b u ti ts t i l lh a ss e v e r ed e f i c i e n c i e si ng e n e r a l i t y ，e x p a n s i b i l i t ye t c f i r s t l y , a l g o r i t h m s l i b r a r yo fo n ed a mm i n i n gs y s t e m sc o u l dn o tb e e ns h a r e db yo t h e r s ；s e c o n d l y , a l g o r i t h m sl i b r a r yc a l ln o tb eu p g r a d e ds y n c h r o n o u s l yw h e nd a t am i n i n gs y s t e mw h i c h b e l o n g st oi su p d a t e d ；f i n a l l y , s e c o n d a r yd e v e l o p m e n to fa l g o r i t h m sl i b r a r yn e e d sa g r e a td e a lo fr e p e t i t i v ew o r k , w h i c hw a s t e sm u c hm a n p o w e ra n dm a t e r i a lr e s o n r c e sa s w e l la si n c r e a s e sd e v e l o p m e n tc o s t i no r d e rt os o l v et h ea b o v ep r o b l e m s ，an e wd a t am i n i n ga l g o r i t h m sl i b r a r y d m a l ( d a t am i n i n ga l g o r i t h m sl i b r a r y ) m o d e li sp u tf o r w a r db a s e do nt h ea n a l y s i s o fa l g o r i t h m sl i b r a r yo fe x i s t i n gd a t am i n i n gs y s t e m s ，w h i c hi si n d e p e n d e n tf r o ma n y d a t am i n i n gs y s t e m ，a n da d o p t sr e u s a b i l i t yt h o u g h t f i r s t l y , t e c h n o l o g yf e a s i b i l i t yo f t h i sd m a lm o d e li sp r o v e d ；s e c o n d l y , t h ew h o l ef r a m eo ft h i sm o d e li sd e s i g n e d b a s e do ne x p a n s i b i l i t ya n dg e n e r a l i 哆；t h i r d l y , a sd e m i ld e s i g n , m e t ad a t at e c h n o l o g y a n dx m lt e c h n o l o g ya r ea d o p t e dt om a n a g ea l g o r i t h m sa n dp a r a m e t e r so ft h e s e a l g o r i t h m s ，a n dt h i sd e s i g ni m p l e m e n t sf l e x i b l ei n t e r a c t i o no ft h ea l g o r i t h m sl i b r a r y ； f m a l l y , b yu s i n gm a p p i n ga n dm e t ao b j e c tp r o t o c o l ，a l g o r i t h m sm a t c h i n gc a l l i s c a r r i e do u t ，a n dw h i c hi m p l e m e n t sf l e x i b i l i t ya n de x p a n s i b i l i t yo fa l g o r i t h m sl i b r a r y s y s t e m o nt h eb a s eo fd m a lm o d e l ，aa l g o r i t h m sl i b r a r yp r o t o t y p es y s t e mi sd e v e l o p e d b yu s i n gu m lv i s u a l i z a t i o nm o d e l i n gt h o u g h tt oa n a l y z ea n dd e s i g nd i a g r a mo fu s e c a s e ，s t a t i c a c t i o nm o d e la n d d y n a m i c a c t i o nm o d e l ，t h e na d o p t i n gj a v a p r o g r a m m i n gl a n g u a g ea sw e l la sm v cd e s i g np a t t e r no nt h ep l a t f o r mo fe c l i p s e ， w h i c ha f f o r d sg r a p h i c a li n t e r f a c e s t h i sp r o t o t y p es y s t e md e m o n s t r a t e sh o wt oc a l l a n dm a n a g ea l g o r i t h m ，a n di ts u p p o r t sf r i e n d l yu s e ri n t e r f a c ef o rt h em a i n t e n a n c ea n d u p g r a d i n go fs y s t e m sm a n a g e m e n ti n aw o r d ，i tp r o v i d e sac e r t a i nr e f e r e n c ef o r r e a l i z i n gp o w e r f u lf u n c t i o no fa l g o r i t h m sl i b r a r ys y s t e m k e y w o r d sd a t am i n i n g ；d a t am i n i n ga l g o r i t h m sl i b r a r y ；s y s t e mf r a m e ；e x p a n s i b i l i t y 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：圣) ：坠日期：逝里= 多0 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学问论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：型：垒导师签名： 日期：2 巡厶一? 第1 章绪论 第1 章绪论 1 1 选题背景以及研究意义 由于数据库技术的广泛应用以及获取数据手段的多样化，导致数据急剧增 加，人们迫切希望能够揭示这些数据背后隐藏的信息，实现对其更高层次的分析， 以便更好地利用。但是目前的数据库系统虽然可以高效地实现数据录入、查询、 统计等功能，却无法发现数据背后的知识，无法根据隐藏的信息提供决策支持， 导致了“数据爆炸但知识贫乏”的现象。在这样的背景下，数据挖掘技术 ( d a m m i n g ，简记为d m ) 应运而生。 数据挖掘从产生至今已有多种定义【1 1 ，其中得到公认的是：数据挖掘是从 大量数据中揭示出有效的、新颖的、潜在有用的、以及最终可理解的知识和模式 的非平凡过程。采用数据挖掘技术，对企业数据进行挖掘分析可以帮助企业在此 基础上进行决策和分析、对未来事务趋向和走势进行科学预测。数据挖掘的目的 主要是从关系数据库、数据仓库、多媒体数据库以及互联网等数据源上设法获取 诸如分类模型、聚类模型、回归模型、关联模型和时间序列模型等多种知识模型。 从而使其在购物篮数据( b a s k e td a t a ) 分析、金融风险预测、产品质量分析、分子 生物学、基因工程研究、i n t e r n e t 站点访问模式发现以及信息搜索等领域得到了 广泛的应用。 在实施数据挖掘过程中，算法库扮演着极为重要的角色【2 1 。它有效集成各种 高效率的数据挖掘算法，并实现对其的有机统一管理，是实现数据挖掘任务的核 心部件。目前的算法库大多是集成在数据挖掘系统中的，与系统是融为一体的， 不能独立于系统之外；此外，算法库往往是针对特定的数据挖掘任务而设计的， 当在原来任务基础上，对数据挖掘系统增添新的功能时，就需要对原算法库进行 升级。另外由于目前常用的算法库缺乏扩展性【3 】，在二次开发过程中，不可避免 的出现大量的重复性工作，这将会延长数据挖掘系统的开发周期，同时导致人力 物力的浪费以及产品成本的增加。 目前数据挖掘系统中，算法库的设计主要关注于数据挖掘算法本身，即如何 改进与提高算法的效率以获得更好的挖掘效果，但是其忽略了算法之间的内在联 系，不能从算法的内在联系去解决问题；其次，算法库中的算法设计只是针对特 定领域的应用以及具体问题的解决，如对规模压缩的研究，数据挖掘算法在入侵 检测系统中的应用，基于数据挖掘技术对考试成绩的分析等。而数据挖掘算法本 身具有通用性的，一个算法可以应用到很多领域中，用来解决各种不同的问题。 而现有得数据挖掘系统中的算法库模型却限制了挖掘算法的通用性。 北京工业大学工学硕士学位论文 面对着数据仓库技术的飞速发展以及数据挖掘行业的巨大发展潜力和上升 空间，针对当前数据挖掘系统算法库存在的缺陷，开发与具体问题、应用领域及 操作平台无关的数据挖掘算法库具有很重要的意义，这样可以降低数据挖掘算法 模型实现过程中的重复劳动，减少人力物力的浪费，从而提高挖掘软件的开发效 率，节约开发成本。 1 2 相关领域研究现状 1 2 1 国外研究及应用现状 自从数据挖掘技术诞生以来，经过二十多年的时间，数据挖掘系统算法库在 体系结构方面得到了很大的进步和提高。目前数据挖掘系统算法库从总体上可以 划分为高中低三个档次。 低端数据挖掘系统算法库的体系结构比较简单，所支持的数据挖掘算法也比 较少。一般情况下，低端挖掘系统算法库只包括决策树、神经网络等为数不多的 数据挖掘算法。而且由于数据挖掘算法的计算过程必须一次性进入内存，因此从 本质上来说，该类算法库不具有可扩展性。这是低端数据挖掘算法库的一大缺陷。 处于中间层次的数据挖掘系统数量众多。这类系统的算法库部分综合了数据 分析和量身解决问题两方面的优点，从理论上分析具有广阔的应用空间。但由于 受挖掘系统核心架构的限定，在扩展性、灵活性、易用性等方面仍然存在严重缺 陷。另外，由于这些数据挖掘系统厂商不提供广大用户买得起的桌面版系统，以 至于购买和维护这些中端挖掘系统的成本费用高昂。 高端数据挖掘系统主要来自于那些将数据挖掘工具与其数据库系统捆绑的厂 商，这种硬件与软件系统相捆绑的方式保证了挖掘产品的可扩展性，从而相应地 使得算法库部分就有较好的扩展性。但是高端数据挖掘算法库在对数据挖掘任务 进行处理时，其所依赖的实施流程反映出很大e r p 和c r m 的痕迹，往往不能很 好满足用户在运行效率和投资回报方面的期望，用户不可以动态的构造面向领域 应用的数据挖掘任务，选择合适的算法进行数据挖掘分析。只能被动地接受数据 挖掘系统厂商所提供的数据挖掘模型和算法。 综上所述，虽然经过几十年的发展，国外的数据挖掘系统算法库部分已经趋 于成熟。但是到目前为止，算法库主要是集成融合于数据挖掘系统，具有很大的 系统依赖性，不易扩展 国外除了上述的商业挖掘系统外，还出现一大批优秀的开源数据挖掘系统， 其中w e k a 就是一个典型的代表。w e k a l 4 】是新西兰w a i k a t o 大学开发的全面的数 据挖掘系统。w e k a 算法库集合了大量能承担数据挖掘任务的挖掘算法包括对数 第1 章绪论 据进行预处理、分类、聚类、关联规则以及算法性能评估的多种方法。w e k a 算法库是由j a v a 语言实现的，具有良好定义的数据结构和基本的统计接口，用 户可以根据具体需要将个性化的算法封装进算法库，从而保证了算法库的扩展性 和兼容性，使得用户可以较好地完成挖掘任务。 1 2 2 国内研究及应用现状 根据设计与实现技术特点，国内数据挖掘系统的算法库可以分为以下几类： ( 1 ) 在一些专用数据挖掘产品中，算法库主要是由针对某一特定用户或者特 定应用开发的专用数据挖掘系统衍化而来的。因此这类算法具有针对性强、设计 科学严谨、功能强大等优点，但其存在通用性差、不易修改、无法移植等缺点。 ( 2 ) 一些国内自主研发的数据挖掘系统中，算法库集成很多数据挖掘算法， 使其在更多领域内得到广泛应用，同时具有可修改、可维护性较强等优点。但由 于某些方面的因素，这些算法库未遵照国外数据挖掘业界的工业标准，导致其存 在扩展性及兼容性差等不足。 ( 3 ) 有些算法库是在国外产品的基础上经过二次开发而来的，从而导致数据 挖掘产品不具有完全的自主知识产权。 从以上分析可以看出，国内的数据挖掘算法库在可扩展性、易用性可复用性 等方面都存在一定程度的缺陷。为了弥补这些方面的缺陷，有些数据挖掘系统如 s m a r t m i n e r 、m s m i n e r 等采用专门的算法管理技术对算法库进行设计。 数据挖掘系统【5 j s m a r t m i l l e r 中，其算法库模块采用了组件对象模型c o m 技术 进行构造。在这种模型的结构体系设计中，一个算法对应一个c o m ，从而保证 了系统的可扩展性。在c o m 接口不发生变化的情况下，当需要修改算法时，只 需修改相应的c o m 构件，通过算法描述库为其提供注册机制，任何符合c o m 标 准的算法模块可方便地加入到系统中。但是c o m 主要是m i c r o s o f t 软件界的应用 系统集成标准，只能在m i c r o s o f t 平台上运行，跨平台性差，无法满足异构环境下 应用的需求。 在史忠植等研究开发的m s m i n e r 系统【6 】中各种数据挖掘核心算法是以动态链 接库d l l 的形式实现与存在的。数据挖掘算法的这种实现形式可以在系统运行过 程中动态加载同时，该系统还引入专门的数据挖掘算法管理与协调机制，设计 了相应的管理实现模块，从而使系统能够通过挖掘算法库管理各种挖掘算法，并 通过元数据的形式提供算法的注册机制。该数据挖掘算法库的设计主要具有两大 特色：( 1 ) 以d l l 可执行代码实现的算法在系统运行时动念载入，保证了算法的 执行效率；( 2 ) d l l 算法库独立于系m s m i n e r 系统而存在，便于维护、升级和扩 展，同时具有良好的通用性。但是d l l 本身也有它自己的缺点：( 1 ) 函数重名问 北京工业大学工学硕士学位论文 题；( 2 ) 各编译器对c + + 函数的名称修饰不兼容问题；( 3 ) 安装与使用路径问题 的差异；( 4 ) d l l 与e x e 的依赖关系。 此外，由上海复旦德门软件公司开发的d m i n e ，】采用基于构件的软件设计方 法，利用插件的概念实现了系统对新算法的可扩展性；由海尔青大公司开发的 i d m i n 一8 】是具有自主知识产权的数据挖掘系统系统中的数据挖掘算法符合o l e d bf o r d a t a m i n i n g 规范，并且被独立封装，与应用服务层之间存在统一的接口： 算法与算法之间不存在任何联系，只需对算法的d l l 动态链接库进行注册、注销 操作，即可增删算法，系统具有良好的可扩展性；四川省电信有限公司商务领航 解决方案中，提出采用j 2 e e 标准实现数据挖掘算法法对应一个e j b 。这种设计 保证了系统的可扩展性，当需要修改算法以及优化算法时，在e j b 接口不发生变 化的情况下，不需要重新编译系统，只需修改相应的商业逻辑构件。 综上所述，经过二十多年的发展，数据挖掘系统算法库的研究取得了显著的 进步，但是在其通用性、扩展性、可移植性、易用性等方面存在的不足还远没有 得到解决，对于国内的数据挖掘系统来说，其算法库设计的主要发展趋势包括以 下几个方面：首先，关注数据挖掘算法的行业适用性及灵活的嵌入、更新策略。 利用数据挖掘算法对数据进行挖掘是整个挖掘过程的核心。因此，开发通用性、 移植性以及行业适用性强的数据挖掘算法是今后数据挖掘算法库研究的一大热 点。其次，利用图像可视化技术开发友好的人机交互界面。友好、方便的算法设 置、结果显示等图形可视化技术，是数据挖掘算法库得以广泛应用的良好保证； 最后，采用数据挖掘业界的通用标准c r i s p d m ，p m m l ，o l ed bf o rd m 等，这 样可以使得设计开发出来的算法库能够更好地与国际标准接轨。 1 3 研究内容 综合国内外相关领域的研究现状，为解决现有数据挖掘系统算法库存在的不 足，在对现有数据挖掘系统算法库分析的基础上，基于可复用性思想和面向方面 编程技术，提出一种独立于数据挖掘系统的算法库d m a l ( d a t am i n i n g a l g o r i t h m sl i b r a r y ) 模型。该模型体系结构具有通用性、交互性、灵活性及扩展 性等特点，为数据挖掘技术的提高以及数据挖掘产品的开发的提供一定参考价 值。 主要内容包括：首先，在分析各种数据挖掘算法之间差异的基础上，提出算 法库对算法差异的屏蔽策略，通过向用户提供统一接口，允许用户添加新的数据 挖掘算法，实现数据挖掘算法库系统的可扩展性：其次，通过对数据挖掘算法库 系统进钆：优化，使其能史加有效地对数据挖掘算法进行统一管理与调用，从而提 o 第l 章绪论 高数据挖掘速度和效率，同时能有效地降低资源消耗；再次，研究算法库自身的 可移植性问题，提高算法库已有功能模块的重复利用率，缩短数据挖掘系统的开 发周期，有效地降低成本；最后，搭建算法库d m a l 模型的体系结构，明确各 子系统的功能以及相互间的坍调机制，并完成功能模块的设计与实现。 1 4 本文结构和组织 结合以上主要研究内容，本文的组织结构如f ： 第1 章绪埝 介绍课题的研究背景、国内外研究现状、主要内容以及文章结构组织。 第2 章对数据挖掘算法库设计与实现所涉及的相关技术进行了介绍。首先 简单介绍数据挖掘技术的基本概念及数据挖掘系统的发展历程；其次，着重介绍 几种主要数据挖掘算法的思想及其典型应用案例：再次，阐述典型数据挖掘系统 的体系结构：最后，介绍系统可移植性、可扩展性的实现技术一x m l 技术、实 现算法管理的元数据技术、实现算法调用的映像和元对象协议以及数据库连接技 术等。在该章的最后对本章内容做了小结 第3 章数据挖掘算法库模型设计。首先在分析现有数据挖拥i 算法库的基础 上，指出其存在的不足和缺陷，明确算法库系统所应具备的功能：其次，基于面 向方面编程技术，提m 了一种新型的算法库模型，捂建了该模型的总体框架：再 次，对算法库体系结构进行功能模块划分，并详细介绍了各模块问的协调机制： 然后，给出算法库各功能模块的设计方案：最后，对本章内容进行小结。 第4 章数据挖掘算法库的详细设计实现。结台所提出的算让库模型，基于 u m l 可视化建模思想，采用m v c 设计模式，在e e l i p 平台上，利用j a v a 编 程语言开发了图形界面化算法库原型系统通过试验演示，验证了算法库设计 的优越性和合理性。最后对该章的内容做了小结。 最后，对全文做了总结井对后续工作做了展望。 第2 章相关文献综述 第2 章相关文献综述 本章首先阐述了数据挖掘技术、典型的数据挖掘算法以及数据挖掘系统中的 一些基本理论和相关研究。然后对现有数据挖掘系统算法库进行了简要介绍和优 缺点分析，明确了算法库系统研究和发展的方向。最后介绍了算法调用技术映像 和元对象协议以及算法存储表示技术x m l 技术。 2 1 数据挖掘概述 2 1 1 数据挖掘定义 g p i a t e t s k y - s h a p i r o 等将数据挖掘定义为基于数据库的知识发现( k d d ) ， k d d 的定义随着人们研究的不断深入也在不断完善，s a s 研究所：“在大量相 关数据基础之上进行数据探索和建立相关模型的先进方法”。b h a v a n i ：“使用模 式识别技术、统计和数学技术，在大量的数据中发现有意义的新关系、模式和趋 势的过程”。h a n d e t a l ：“数据挖掘就是在大型数据库中寻找有意义、有价值信息 的过程”。目前比较公认的定义有两个，一种是g p i a t e t s k y s h a p i r o 等人提出，数 据挖掘是指从数据库的大量数据中揭示出隐含的、先前未知的、潜在有用的信息 的非平凡过程；另一种是由f a y y a d 9 , 1 0 l 等给出：k d d 是从数据集中识别出有效 的、新颖的、潜在有用的以及最终可理解模式的高级处理过程。后者实际上是对 前者的发展与综合，两者都将数据挖掘定义为一个过程，就是应用一系列技术从 大型数据库或数据仓库中提取人们感兴趣的信息和知识的过程，这个过程是对数 据集及数据仓库的一个不断发现，发掘信息的过程，并不单纯定义为一种研究方 法，分析方法，而提取的知识或信息是隐含的，事先未知而潜在有用的，提取的 知识表示为概念、规则、规律、模式等。由此可以看出，数据挖掘一开始就是面 向用户，面向应用的。随着数据爆炸式的增长，数据挖掘的应用需求将会越来越 大。 2 1 2 数据挖掘技术的起源 数据挖掘是应用需求推动下多种学科融合的结果】。 首先是数据库技术。随着数据库技术的不断发展及数据库系统的广泛应州， 人类积累的数据量正以指数速度增长。例如：w a lm a r t 公司每天要处理二千万个 事务；美国航天局1 9 9 9 年发射的地球观测系统每小时要产生5 0 g b 的图像数据。 北京工业大学工学硕士学位论文 毫无疑问，这些庞大的数据库及其中的海量数据中蕴藏着丰富的信息。但是仅仅 依靠传统的数据检索机制和统计分析方法还不能揭示出其中所蕴含的知识【1 2 1 。数 据挖掘技术正是在这种强烈需求背景下，由数据库技术推动、演化而来的。 其次，在数据库技术飞速发展的同时，人工智能领域的一个分支一机器学 习的研究也取得很大进展。自5 0 年代开始机器学习的研究以来，先后经历了神经 模型和决策理论、概念符号获取及知识加强、领域专用学习三个阶段，根据人类 学习的不同模式人们提出了很多机器学习方法，如：实例学习、观察和发现学习、 神经网络和遗传算法等等。其中某些常用且较成熟的算法已被人们运用于实际的 应用系统及智能计算机的设计和实现中。数据挖掘中的许多方法就来源于机器学 习。 最后，使数据挖掘能够得到广泛应用的关键一点是计算机性能的迅速发展。 计算机存储设备性价比的迅速提高，使许多企业有能力收集和存储海量数据，而 计算机计算能力性价比的提高，则为数据挖掘的实旖扫清了障碍。随着计算机硬 件性能的不断提高、数据挖掘技术的不断改进，数据挖掘应用将会越来越普及。 2 1 3 数据挖掘过程 一般情况下，可以将数据挖掘的整个过程u 3 , 1 4 】分为三个阶段：数据的准备， 数据的挖掘，数据挖掘的结果表达和解释。并且在整个挖掘过程中，离不开用户 的参与，整个过程是个反复精炼的过程。 对于据挖掘流程还有其他的提议，如a n a n t h a n a r a y a n a v s 【1 5 1 等提出来的知识 发现过程，主要包括知识理解，数据理解，数据集成与选择，数据预算理，数据 挖掘，结果表达和解释，评价数据挖掘模型，应用所建模型等步骤，并反复进行 人机交互的复杂过程。此模型最大特点在于其主要是面向应用的，如果经过挖掘 所获得的知识不能使决策者满意，则重复数据挖掘阶段操作，最后把整个知识运 用到生产实际中去，评价所建立的模型是否能够满足生产实际需要，如果不满足 则重复整个数据挖掘过程。 目前，通用的数据挖掘系统大致分为两种类型：一种是f a y y a d 总结提出的过 程模型，另一种是遵循c r j s p d m l l 6 】标准的过程模型。f a y y a d 过程属于一个高级处 理过程，它从数据集中识别出以模式来表示的知识。它包含多个处理步骤：确定挖 掘目标，了解应用领域和相关知识，从用户的观点出发确定数据挖掘的目标，建立 目标数据集，从现有的数据中，确定哪些数据是与本次数据分析任务相关的；根 据挖掘h 标从原始数据中选择相关数据集，并将不同数据源中的数据集中起来：数 8 第2 章相关文献综述 据清洗和预处理，对选择的数据，需要进行数据清洗工作，将数据转换成满足数 据挖掘要求的数据；数据降维和转换：降维是减少变量的实际数目，并设法将数 据转换到一个更容易找到的空间上：数据挖掘算法：使用合适的数据挖掘算法进 行数据分析，模型的评价和解释。上述各个步骤之间互相影响并反复调整，最终 形成一种螺旋上升的过程。 c r i s p - d m ( c r o s s - i n d u s t r ys t 粗d a mp r o c e s sf o rd a t am i n i n g ) 是由s p s s d a i m l e r - b e n z 等几家跨国公司支持的特别兴趣小组，在1 9 9 7 年7 月到1 9 9 9 年4 月间研究后提出。c r i s p d m 强调数据挖掘不只是数据的组织、呈现、数据分析 和建模，而是一个从理解企业需求、寻求解决方案到实践检验的完整过程。采用 分层方法将一个数据挖掘项目周期定义为6 个阶段：定义商业问题、数据了解、 数据前置处理、建立模型、模型评估、扩展模型，阶段间有循环，项目的总体实 施是分阶段循环进行的。 李雄飞、李军【17 】等提出的数据挖掘过程可粗略地理解为三部曲：数据准备 ( d a t ap r e p a r a t i o n ) 、数据采掘( d a t am i n i n g ) ，以及结果的解释评估( i n t e r p r e t a t i o n a n de v a l u a t i o n ) 。数据准备又可分为三个子步骤：数据选取( d a t as e l e t i o n ) 、数据 预处理( d a t ap r e p r o c e s s i n g ) 和数据变换( d a t at r a n s f o r m a t i o n ) 。 数据准备的目的是确定发现任务的操作对象，即目标数据( ( t a r g e td a t a ) ，它 是根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般包括消除噪 声、推导计算缺值数据、消除重复记录、完成数据类型转换如把连续值数据转换 为离散型的数据，以便于符号归纳或是把离散型值转换为连续型值，以便于神经 网络归纳等。当数据采掘的对象是数据仓库时，一般来说，在生成数据仓库时数 据预处理已经完成。数据变换的主要目的是降维( d i m e n s i o nr e d u c t i o n ) ，即从初 始特征中找出真正有用的特征以减少数据挖掘时要考虑的特征或变量个数，将数 据转换成适合于挖掘的形式】。 数据挖掘阶段首先要确定挖掘的任务或目的，如数据总结、分类、聚类、关 联规则发现或序列模式发现等。确定挖掘任务后，就要决定使用什么样的挖掘算 法。同样的任务可以用不同的算法来实现，选择实现算法需要考虑如下两个因 素：( 1 ) 不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；( 2 ) 满足 不同用户或实际运行系统的要求，有的用户可能希望获取描述型的( d e s c r i p t i v e ) 、 容易理解的知识，而有的用户或系统的目的是获取预测准确度尽可能高的预测型 ( p r e d i c t i v e ) 知识。完成了上述准备工作后，就可以实施数据挖掘操作了。需要指 出的是，尽管数据挖掘算法是数据挖掘的核心，也是目前研究人员需要努力的方 向，但要获得好的挖掘效果，必须对各种挖掘算法的要求或前提假设有充分的理 解。 数据挖掘阶段所得模式，经过用户或机器的评估，可能存在冗余或无关的模 一北京工业大学工学硕士学位论文 式，这时需要将其剔除；也有可能这些模式不能满足用户要求，这时则需要整个 发现过程退回到发现阶段之前，然后重新选取数据、挖用新的数据变换方法、设 定新的数据挖掘参数值，甚至换一种挖掘算法( 如当发现任务是分类时，有多种 分类方法，而不同的方法对不同的数据有不同的效果) 。另外，由于最终是面向 人类用户的，数据挖掘系统必须具备发现模式可视化界面或者把结果转换为用户 易懂的另一种表示，如把分类决策树转换为“i t h e n 规则。 2 1 4 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖 掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能。 ( 1 ) 自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析 的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场预测问 题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它 可预测的问题包括预报破产以及认定对指定事件最可能作出反应的群体。 ( 2 ) 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量 的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因 果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中 数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可信度。 ( 3 ) 聚类 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们 对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统 的模式识别方法和数学分类学。8 0 年代初，m c h a l s k i 提出了概念聚类技术物其 要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内 涵描述，从而避免了传统技术的某些片面性。 ( 4 ) 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对缘的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类埘象之问的区别。生成一个类的特征性描述只涉及该类坩象中所有对象的 共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 ( 5 ) 偏差榆测 第2 章相关文献综述 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏 差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与 模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结 果与参照值之间有意义的差别 2 1 5 数据挖掘的相关领域 图2 1 展示了一些数据挖掘方法。数据挖掘方法的三个主要来源是机器学习、 数据库技术和统计学，与数据挖掘相关的理论和技术可以分别按挖掘任务、挖掘 对象和挖掘方法来分类。 基于烂则 可视 巍矬 水 习 炳 经弼络 图2 - 1 数据挖掘方法与相关领域 f i g2 - i d a t am i n i n gm e a n sa n dc o r r e l a t i v ef i e l d s ( 1 ) 按挖掘任务分类：包括分类与预测、聚类、关联规则、时序模式、数据总结、 依赖关系或依赖模型发现、异常和趋势发现等。 ( 2 _ ) 按挖掘对象分类：包括关系数据库、而向对象数据库、空间数据库、时态数 据库、文木数据库、多媒体数据库、异构数据库、数据仓库、演绎数据库和w e b 数据库等。 ( 3 ) 按挖掘方法分类：包括机器学习方法、统计方法、数据库方法和神经网络方 法等。机器学习方法可以细分为归纳学习方法( 决策树、规则归纳等) 、基于范例 学习、遗传算法等。统计方法又可细分为回归分析( 多元回归、自回归等) 、判别 分析( 贝叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类 等) 、探索性分析( 主成分分析、相关分析等) 等。数据库方法主要是多维数据分析 和o l a p 技术，此外还有一而向属性的归纳方法。神经网络方法可以进步分为 前向神经网络( b p 算法等) ，h o p f i e l d 神经网络，自组织神经网络( 自组织特征映 射、竞争学习等) 。 北京工业大学工学硕士学位论文 2 2 典型数据挖掘算法 2 2 1 关联规则算法 关联规则( a s s o c i a t i o nr u l e ) 的概念首先是由i l a g r a w a l 等人于1 9 9 3 年在 文献 1 8 q a 提出的，此后他们又在文献【1 9 】【2 0 】中对关联规则进行了更深入的研 究。关联规则挖掘用来发现大量数据中项集之间有趣的关联或相关联系。随着大 量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越 来越感兴趣。从大量商业事务记录中发现有趣的关联关系，可以帮助制定商务决 策，如货架布置、捆绑销售等。 引发关联规则挖掘的典型例子是购物篮分析。它通过发现顾客放入其购物篮 中不同商品之问的联系，分析顾客的购买习惯，这种关系的发现可以帮助零售商 制定营销策略。例如，在设计商店布局时，可以将经常一块购买的商品放近一些， 以刺激这些商品一起销售；也可以将这些商品放在货架的两端，诱发购买这些商 品的顾客一路挑选其他商品。 关联规则挖掘是从大量数据中挖掘出有趣规则的过程，是数据挖掘中重要的 研究领域。设i = i l , i 2 ，i 3 ，i m ) 是项的集合。设与任务相关的数据d 是数据库事 务的集合，其中每个事务t 是项的集合，使得。每个事务有个标识符，成为t i d 。 设a 是一个项集，事务t 包含a 当且仅当关联规则是形如的蕴涵式，其中并且 anb = 中。规则 在事务集d 中成立，具有支持度s ，其中s 是d 中事务包含aub ( 即a 和b - - 者) 的百分比。它是概率p ( a u b ) 。规则在事务集d 中具有置信度c ， 如果d 中包含a 的事务同时也包含b 的百分比是c 。这是条件概率p ( b i a ) 。即是 s u p p o r t ( a = b ) = p ( a = _ b ) c o n f i d e n c e ( a = b ) = p ( b i a ) 如果对于预先指定的最小支持度阈值m i n - s u p p o r t ，s u p p o r t ( a = b ) 大于等于 m i n s u p p o r t ，项集a 是频繁的。频繁项集挖掘问题就是找出d 中所包含的全部 频繁项集。一旦找出全部频繁项集，就可以生成同时满足最小置信度和最小支持 度的强关联规则。 关联规则的挖掘是一个两步的过程： ( 1 ) 找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最 小支持计数一样。 ( 2 ) 有频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和 最小置信度。如果愿意，也可以使用附加的兴趣度度量。 第2 章相关文献综述 a p f i o f i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法使用 频繁项集的先验知识。a p r i o r i 使用一种称作逐层搜索的迭代算法，k - 项集用于探 索( k + 1 ) 一项集。找出频繁1 项集的集合。该集合记作l l 。l l 用于寻找频繁2 项集的集合l 2 ，而l 2 用于寻找l 3 ，如此下去，直到不能找到频繁k 项集。 自a g a w a l 等人【2 i 】于1 9 9 3 年提出频繁模式挖掘问题依赖，频繁模式挖掘方法 得到了很大发展，针对如何提高算法的效率很多人提出了改进算法。 a p f i o f i 算法产生巨大的候选项集，需要频繁的扫描数据库。针对a p d o n 的缺 陷，j i a w e i h a l l 等人提出了一种改进算法f p g r o w t h m ，f p g r o w t h 算法是一种不产 生候选项集而采用频繁模式增长的方法挖掘频繁模式的算法，效率比a p f i o f i 算法 提高了近一个数量级。 关联规则算法最典型的用途就是对客户的事务进行购物篮分析，这样可以知 道哪些产品比较热销，以及一个特定的产品与另一个产品一起被购买的可能性是 多大，从而有针对性开展促销工作。 2 2 2 分类算法 分类在数据挖掘中是一项非常重要的任务，目前在商业上的应用也最多。分 类的目的是学会一个分类函数或分类模型，该模型能把数据库中的数据项映射到 给定类别中的某一个【2 3 1 。分类器的构造方法有统计方法、机器学习方法、神经网 络方法等。统计方法包括贝叶斯和非参数法，对应的知识表示为判别函数和原型 事例。机器学习方法包括决策树法和规则归纳法。神经网络方法主要是b p 算法， 它的模型表示是前向反馈神经网络模型。还有一种粗糙集方法，其知识表示是产 生式规则。分类的典型应用：信用卡系统中的信用分级、市场调查、疗效诊断、 寻找店址等。 决策树算法是应用最广的分类算法之一，用决策树进行分类主要包含两步。 第一步是利用训练数据集构造一棵决策树模型。这个过程实际上是一个从数据中 获取知识，进行机器学