（计算机应用技术专业论文）基于web服务的数据挖掘系统关键技术的研究及其原型设计.pdf

基于l t e b 服务的数据挖掘系统关键技术的研究及其原型设计摘要 捅要 随着数据积累的越来越多，企业迫切希望挖掘出隐藏在大量数据背后的知识以支 持决策。现有的数据挖掘工具如i b m 的i n t e l l i g e n c em i n e r ，s a s 的e n t e r p r i s em i n e r 虽然提供了较丰富的挖掘功能，但是这些工具不能够挖掘i n l e r n e t e x t r a n e t 上的分布 式和高度异质的数据，不能有效地与操作型系统集成，而且针对性不强。企业如果采 用这些工具投资很大，某些挖掘功也用不上，而且算法库升级非常困难。本文提出了 一种基于w e b 服务的数据挖掘系统架构。它能够与原有操作型系统良好集成，能够 挖掘分布式数据库中的数据，而且具有跨平台、跨语言、易于部署和可动态管理算法 库等优点。 本文首先给出了基于w e b 服务的数据挖掘系统的总体架构，将w e b 服务这优 秀的面向服务的企业架构的实现技术引入了数据挖掘系统中。然后详细研究了构建数 据挖掘系统的关键技术，包括数据的预处理、挖掘算法的管理、算法库的构建以及数 据挖掘模型的可视化。数据挖掘的结果模型用p m 础l 表示，可以实现数据挖掘模型 的共享和再利用。接着研究了关联规则挖掘算法并给出了关联规则挖掘算法的一种实 现。最后给出了一个b s 结构的基于w e b 服务的数据挖掘系统原型的实现，并利用 该原型系统对某超市的购物篮数据进行了关联规则挖掘，从而证明了本文提出的数据 挖掘系统架构具有较高的可伸缩性、可信度和可实施性。 关键词：数据挖掘w e b 服务关联规则挖掘数据预处理p m m l 作者：王卓滂 指导老师：徐汀荣 a b s w a a 基于托b 服务的数据挖掘系统关键技术的研究及其原型设计 a b s t r a c t w i t ht h er a p i di n c r e a s e m e n to fd a t a , t h ee n t e r p r i s e sw a n tt om i n et h ek n o w l e d g e b e h i n dt h el a r g ea m o u n t so fd a t ai no r d e rt os u p p o r td e c i s i o n s o m ee x i s t i n gd a t am i n i n g t o o l ss u c ha si n t e l l i g e n c em i n e r ，e n t e r p r i s em i n e r s u p p l yr i c hd a t am i n i n gf u n c t i o n s ，b u t t h e s et o o l sc a n tm i n ed i s t r i b u t e da n dh e t e r o g e n e o u sd a t ao ni n t e m e t e x t r a n e t ，a n dt h e y c a n ti n t e g r a t ew i t ho p e r a t i n gs y s t e me f f e c t i v e l ya n dh a v en op e r t i n e n c e s i f t h ee n t e r p r i s e s l l s ct h e s et o o l s t h e yw i l le x p a n dm o r em o n e yb u tm a n ym i n i n gf u n c t i o n sb e c o m eu s e l e s s a n di t sv e r yd i f f i c u l tt ou p g r a d et h ea l g o r i t h m sl i b r a r y t h i st h e s i sp u t sf o r w a r dad a t a m i n m gs y s t e ma r c h i t e c t u r eb a s e do nw e bs e r v i c e s i tc a ni n t e g r a t e 谢t he x i s t i n go p e r a t i n g s y s t e ma n dc 锄m i l l et h ed a t ai l ld i s t r i b u t e dd a t a b a s e b e c a u s eo f u s i n gt h ew e bs e r v i c e s i t c a l lb ei n d e p e n d e n to f p l a t f o r ma n dp r o g r a m m i n gl a n g u a g e e a s et ob ed e p l o y e da n dt o m a n a g ea l g o r i t h m sl i b r a r yf l e x i b l y f i r s t l y , t h i st h e s i sg i v e sag e n e r a la r c h i t e c t u r ea b o u td a t am i n i n gs y s t e mb a s e do nw e b s e r v i c e sa n di n t r o d u c e sw e bs e r v i c e st e c h n i q u ew h i c hr e a l i z e ss e r v i c e s o r i e n t e d a t e h i t e e t u r e a n dt h e ni tr e s e a r c h e st h ek e yt e c h n i q u e so fd a t am i n i n gs y s t e mi nd e t a i l ， i n c l u d i n gd a t ap r e p r o c e s s ，a l g o r i t h mn m n a g e m e n t , b u i l d i n ga l g o r i t h ml i b r a r ya n dd a t a m i n i n gm o d e lv i s u a l i z a t i o n u s i n gp m m l t oe x p r e s st h er e s u l tm o d e lo fd a t am i n i n g , i t c a ns 1 1 a ma n dr e u s et h ed a t am i n i n gm o d e l a n dt h e ni tr e s e a r c h e sa s s o c i a t i o nr u l e sm i n i n g a l g o r i t i n na n di m p l e m e n ti t a tl a s ti tg i v e st h ei m p l e m e n t a t i o no fd a t am i n i n gs y s t e m p r o t o t y p eb a s e do nw e bs e r v i c e su s i n gb sa r c h i t e c t u r e 。a n dh a sm i n e da s s o c i a t i o nr u l e si n t h em a r k e tb a s k e td a t ao fo n es u p e r m a r k e t t h er e s e tp r o v e st h a tt h ea r c h i t e c t u r eo fd a t a m i n i n gs y s t e mi se x p a n s i b l e ，b e l i e v a b l ea n df e a s i b l e k e y w o r d s ：d a t am i n i n g , w e bs e r v i c e s , a s s o c i a t i o nr u l e sm i n i n g ，d a t ap r e p r o c e s s , p m m l i l w r i t t e nb yw a n gz h u o p a n g s u p e r v i s e db yx ut i n g r o n g x9 5 7 0 0 5 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名： 蔓塞瘥 日飘：加。st j 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 王童建 日 导师签名： 彳釜盗笙 日 期：扣j 。砑 期：! 堕 基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计 第一章引言 1 1 课题的研究背景 第一章引言 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个数据 库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将持续发展下去 于是，一个新的挑战被提了出来：在这个被称之为信息爆炸的时代，信息过量几乎成 为人人需要面对的问题，如何才能不被信息的汪洋大海所淹没，从中及时发现有用的 知识，提高信息利用率昵? 要想使数据真正成为一个公司的资源，只有充分利用它为 公司自身的业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为 垃圾。因此，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识 发现( d m k d ) 技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘【1 1 ( d a mm i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过 程还有很多和这一术语相近的术语，如从数据库中发现知识( k d d ) 、数据分析、数 据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的源泉，就像 从矿石中采矿一样。原始数据可以是结构化的，如关系型数据库中的数据，也可以是 半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知 识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现 了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据 自身的维护因此，数据挖掘是一门广义的交叉学科，它汇聚了不同领域的研究者， 尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和工程技术人 员。 特别要指出的是数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据 库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、 综合和推理，企图发现事件问的相互关联，甚至利用已有的数据对未来的活动进行预 测，以指导实际问题的解决。例如加拿大b c 省电话公司要求加拿大s i m o nf r a s e r 大 学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新的电话收费和 管理办法，制定既有利于公司又有利于客户的优惠政策。美国著名国家篮球队n b a 的教练，利用某公司提供的数据挖掘技术，l 晦场决定替换队员，一度在数据库界被传 第一章弓l 言基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计 为佳话。这样一来，就把人们对数据的应用，从低层次的末端查询操作，提高到为各 级经营决策者提供决策支持。这种需求驱动力，比数据库查询更为强大。同时需要指 出的是，这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去发 现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。所有发现的知识都 是相对的，是有特定前提和约束条件、面向特定领域的，同时还要能够易于被用户理 解，最好能用自然语言表达发现结果。因此d m k d 的研究成果很讲求实际。1 9 9 7 年 第3 届k d d 国际学术大会上进行的实实在在的数据挖掘工具的竞赛评奖活动，就是 一个生动的证明。最近，还有不少d m k d 产品用来筛选i n t e m 雠上的新闻，保护用 户不受无聊电子邮件的干扰和商业推销，受到极大的欢迎。 随着d m k d 研究逐步走向深入，人们越来越清楚地认识到，d m k d 的研究主要 有三个技术支柱，即数据库、人工智能和数理统计。 数据库技术在经过了8 0 年代的辉煌之后，已经在各行各业成为一种数据库文化 或时尚。数据库界目前除了关注分布式数据库、面向对象数据库、多媒体数据库、查 询优化和并行计算等技术外，已经在开始反思。数据库实质的应用仅仅是查询吗? 理 论根基最深的关系型数据库最本质的技术进步点，就是数据存放和数据使用之间的相 互分离。查询是数据库的奴隶，发现才是数据库的主人。数据只为职员服务，不为老 板服务! 这是很多单位的领导在热心数据库建设后发出的感叹。 由于数据库文化的迅速普及，用数据库作为知识源具有坚实的基础；另一方面， 对于一个感兴趣的特定领域一客观世界，先用数据库技术将其形式化并组织起来， 就会大大提高知识获取起点，以后从中发掘或发现的所有知识都是针对该数据库而言 的。因此，在需求的驱动下，很多数据库学者转向对数据仓库和数据挖掘的研究，从 对演绎数据库的研究转向对归纳数据库的研究。 专家系统曾经是人工智能研究工作者的骄傲。专家系统实质上是一个问题求解系 统，目前的主要理论工具是基于谓词演算的机器定理证明技术二阶演绎系统。领 域专家长期以来面向一个特定领域的经验世界，通过人脑的思维活动积累了大量有用 信息。 在研制一个专家系统时，知识工程师首先要从领域专家那里获取知识，这一过程 实质上是归纳过程，是非常复杂的个人到个人之间的交互过程，有很强的个性和随机 性。因此，知识获取成为专家系统研究中公认的瓶颈问题。其次，知识工程师在整理 表达从领域专家那里获得的知识时，用i f - t h e n 等类的规则表达，约束性太大，用常 2 基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计 第一章引言 规数理逻辑来表达社会现象和人的思维活动局限性太大，也太困难，勉强抽象出来的 规则有很强的工艺色彩，差异性极大，知识表示又成为一大难题。 此外，即使某个领域的知识通过一定手段获取并表达了，但这样做成的专家系统 对常识和百科知识出奇地贫乏，而人类专家的知识是以拥有大量常识为基础的。人工 智能学家f e i g e n b a u r a 估计，一般人拥有的常识存入计算机大约有1 0 0 万条事实和抽 象经验法则，离开常识的专家系统有时会比傻子还傻。 以上这3 大难题大大限制了专家系统的应用，使得专家系统目前还停留在构造诸 如发动机故障论断一类的水平上。人工智能学者开始着手基于案例的推理，尤其是从 事机器学习的科学家们，不再满足自己构造的小样本学习模式的象牙塔，开始正视现 实生活中大量的、不完全的、有噪声的、模糊的、随机的大数据样本，也走上了数据 挖掘的道路。 数理统计是应用数学中最重要、最活跃的学科之一，它在计算机发明之前就诞生 了，迄今已有几百年的发展历史。如今相当强大有效的数理统计方法和工具，已成为 信息咨询业的基础。信息时代，咨询业更为发达。然而，数理统计和数据库技术结合 得并不算快，数据库查询语言s q l 中的聚合函数功能极其简单，就是一个证明。咨 询业用数据库查询数据还远远不够。一旦人们有了从数据查询到知识发现、从数据演 绎到数据归纳的要求，概率论和数理统计就获得了新的生命力，所以才会在d m k d 这个结合点上，立即呈现出“忽如一夜春风来，千树万树梨花开”的繁荣景象。一向 以数理统计工具和可视化计算闻名的美国s a s 公司，领先宣布进入d m k d 行列。 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性质的知 识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事物之间属性 差别的知识；关联型知识，反映事物之间依赖或关联的知识；预测型知识，根据历史 的和当前的数据推测未来数据；偏离型知识，揭示事物偏离常规的异常现象。所有这 些知识都可以在不同的概念层次上破发现，随着概念树的提升，从微观到中观再到宏 观，以满足不同用户、不同层次决策的需要。例如，从一家超市的数据仓库中，可以 发现的一条典型关联规则可能是“买面包和黄油的顾客十有八九也买牛奶”，也可能 是“买食品的顾客几乎都用信用卡”，这种规则对于商家开发和实旋客户化的销售计 划和策略是非常有用的。至于发现工具和方法，常用的有分类、聚类、模式识别、可 视化、决策树、遗传算法、不确定性处理等。 当前，d m k d 研究正方兴未艾，估计在2 l 世纪还会形成更大的高潮，研究焦点 第一章引言 基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计 可能会集中到以下几个方面：研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化；寻求数据挖掘过程中的可视化方法，使得知识发现的 过程能够被用户理解，也便于在知识发现过程中的人机交互；研究在网络环境下的数 据挖掘技术，特别是在i n t e m e t 上建立d m k d 服务器，与数据库服务器配合，实现 数据挖掘；加强对各种非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数 据。但是，无论怎样，需求牵引，市场驱动是永恒的。d m k d 将首先满足信息时代 用户的急需，大量基于d m k d 的决策支持软件工具产品必将问世。 当前数据挖掘的应用范围越来越广。人们对数据挖掘的认识不仅仅局限于理论阶 段，很多的数据挖掘系统已经走出实验室，应用到了实际的企业应用当中。数据挖掘 适用的范围也非常的广泛，包括客户关系管理，地理信息系统，电子商务系统，w e b 挖掘系统等。我们相信在不久的将来，越来越多的企业，无论是实力雄厚的大公司， 还是实力稍逊的中小企业，都会认识到数据挖掘系统对企业信息化建设和决策支持的 价值。总有一天，数据挖掘系统会像现在的数据库系统一样，随着技术的不断更新， 会被越来越多的企业认可和采用，数据挖掘系统给人f f l g , j 造信息，创造财富的那一天 也终究会到来。 1 2 本文所要解决的问题 虽然对数据挖掘的研究已经取得了一定的成果，然而其研究还很不够成熟，尤其 是对数据挖掘系统的研究和应用存在着较大的局限性。正是这些局限性限制了数据挖 掘研究的进一步发展。目前，数据挖掘系统的应用面临着以下几点挑战： ( 1 )数据挖掘过程需要专家的积极参与。目前，几乎所有的数据挖掘系统都 需要数据挖掘专家和领域专家的广泛参与。从挖掘最初始阶段的数据处理部分一直到 最后的模式评估，离开了专家的参与，数据挖掘就很难完成。如果在数据挖掘过程中， 从数据处理，到建模，再到模型评估尽量减少专家的参与程度，使普通决策者也能够 很好的使用数据挖掘系统，将对数据挖掘系统的进一步推广带来很大的好处。 ( 2 )数据挖掘系统与原有操作型系统的集成问题。与原有操作型系统的集成 是第三代数据挖掘产品的主要特征。用于数据挖掘的大量数据一般都来源于操作型系 统，而且许多企业的信息管理系统希望数据挖掘系统和操作型系统集成在一起，提供 统一的界面，供企业内部不同角色的用户使用。另外，与操作型系统的集成也有利于 数据挖掘模型的应用。比如在电子商务系统中，用户浏览页面时，同时也启动挖掘过 4 基于b 服务的数据挖掘系统关键技术的研究及其原型设计 第一章引言 程，产生一个个性化推荐页面提供给用户，以方便用户的网上购物。这样，电子商务 系统中，业务系统需要和挖掘系统集成在一起。 ( 3 )对i n t e r n e t e x t r a n e t 上的分布式、异构数据源的挖掘。大量局域及广域计 算机网络，包括因特网，连接了许多的数据源并且形成了海量的分布式、不均匀的数 据库。从不同的格式化或非格式化并有不同语义的数据中挖掘知识对数据挖掘系统提 出了新的挑战。 ( 4 )算法库的定制，共享和维护。目前企业所提供的数据挖掘系统有两种： 综合性的数据挖掘系统和单一性的数据挖掘系统。无论那种系统，都无法定制和共享 算法库，而且如果升级算法库，都二次开发，升级成本较高。 鉴于以上对数据挖掘系统所面临的挑战，本文从应用角度提出了一个基于w e b 服务的数据挖掘系统架构，目的是为大型企业或中小型企提供一个有效、可信、安全、 可行和有良好伸缩性的数据挖掘解决方案。本数据挖掘系统采用w e b 服务封装各种 挖掘算法，实现了挖掘系统和挖掘算法的松散耦合，以方便对挖掘算法的动态管理。 1 3 本文的组织结构 本文共分六章，其中第三，第四，第五章为重点。 第一章为引言部分。介绍了论文的研究背景，本文所解决的问题以及本文的组 织结构。 第二章为数据挖掘概述和w e b 服务技术介绍。详细阐述了数据挖掘的基本知识， 面向服务的软件架构和w e b 服务的基本知识，为开发基于w e b 服务的数据挖掘系统 作出了一定的理论和技术准备。 第三章为数据挖掘系统关键技术的研究。根据引入了w e b 服务的数据挖掘系统 的特点，对数据挖掘系统的各组成部分的关键技术进行了研究。 第四章为关联规则挖掘算法的研究及实现。详细研究了关联规则挖掘算法，并给 出了a p r i o r i 算法的j a v a 实现。 第五章为基于w e b 服务的数据挖掘系统原型的实现。给出了基于w e b 服务的数 据挖掘系统原型的详细结构，各模块的主要功能以及实现方法。最后给出了原型系统 的一个应用实例，并收到了良好的挖掘效果。 第七章为总结和展望部分。对本数据挖掘系统的优点和不足之处进行了总结，并 提出了改进方向和未来的工作。 第二章数据挖掘概述和w e b 服务技术介绍基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计 第二章数据挖掘概述和w e b 服务技术介绍 2 1 数据挖掘概述 随着现代信息技术的迅猛发展，在全球范围内掀起了信息化的浪潮。信息产生的 渠道越来越多，更新的频率日益加快，各行业均产生了数以亿计的数据记录。人们面 对着大量的数据，却往往很难发现有用的知识，这就是所谓的“数据丰富，信息贫乏”。 如何充分、有效地利用这些宝贵的数据资源成为当今世界共同关心的热点课题。随着 数据库技术，人工智能、数理统计和并行计算等技术的发展与融合，数据挖掘技术应 运而生。它是一门新兴的交叉学科，是现代科学技术相互渗透的必然结果，基本目标 就是从大量的数据中提取隐藏的、潜在的和有用的知识和信息，为解决上述问题提供 有效的途径。 本节详细介绍了数据挖掘的基本概念、发展历程、挖掘步骤、任务和方法、p m m l 以及挖掘工具和应用状况，这是后面章节的理论基础。 2 1 1 数据挖掘的基本概念 数据挖掘，也叫数据库中的发现知识( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 。 k d d 2 i - - 词首次出现在1 9 8 9 年8 月举行的第1 l 届国际联合人工智能学术会议上。随 着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把专题讨论 会更名为国际会议，在加拿大蒙特利尔市召开了第一届k d d 国际学术会议，以后每 年召开一次。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了1 1 次，规模由原来的专题讨论会发展到国际学术大会，人数由二三十人发展到一千多人， 论文收录比例从2 ：1 到6 ：1 以上，研究重点也逐步从发现方法转向系统应用，并且注 重多种发现策略和技术的集成，以及多种学科之间的相互渗透。其他内容的专题会议 也把数据挖掘和知识发现列为议题之一，成为当前计算机科学界的一大热点， 那么，究竟什么是数据挖掘呢? 目前还没有一个所有人都认可的关于数据挖掘的 定义。通俗的讲，数据挖掘( d a t am i n i n g ) 0 1 是从大量的、不完全的、有噪声的、模 糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。 6 基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计第二章数据挖掘概述和w e b 服务技术介绍 数据挖掘就是要在“数据矿山”中找到蕴藏的“知识金块”，帮助企业减少不必 要投资的同时提高资金回报。数据挖掘给企业带来的潜在的投资回报几乎是无止境 的。世界范围内具有创新性的公司都开始采用数据挖掘技术来判断哪些是他们的最有 价值客户，以便重新制定他们的产品推广策略，用最小的花费得到最好的销售。比如， 电信公司可以利用数据挖掘技术发现流失概率很高的客户、可能出现的欺诈行为、潜 在的大客户等等【”。 最近，c l a l t n c rg r o u p 的一次高级技术调查将数据挖掘和人工智能列为一未来三到 五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据 挖掘列为未来五年内投资焦点的十大新兴技术前两位。根据g a r 咂盯的h p c 研究表明： “随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需要采用新技 术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增长点”。 以后，对数据挖掘的研究不再局限于实验室内，而是会越来越多的应用于企业管理系 统中，支持企业决策。随着对数据挖掘研究的进一步深入，如何开发出更好的适应企 业应用的数据挖掘系统成为了各个研究机构和数据挖掘工具开发企业研究的重点。 2 1 2 数据挖掘系统的发展历程 数据挖掘的核心技术是人工智能、机器学习、统计学等，但一个数据挖掘系统不 是多项技术的简单组合，而是一个完整的整体，它还需要辅助技术的支持，才能够完 成数据采集、预处理、数据分析、结果表述以及将分析结果呈现在用户面前等这一系 列任务。按特征划分的数据挖掘的系统结构【4 1 娜6 7 1 如表2 1 所示。 表2 1 按特征划分的数据挖掘的系统结构 代特征数据挖掘算法集成分布计算模型数据模型 第一代数据挖掘作支持一个或者独立的系单个机器向量数据 为一个独立多个算法 统 的应用 第二代和数据库以多个算法能够数据管理同质局部区域的有些系统支持对 及数据仓库挖掘一次不能系统，包计算机群集w 象、文本和连续的 集成 放进内存的数 括数据库媒体数据 据和数据仓 库 第三代和预言模型多个算法数据管理 i n t r a n e t e x t r a n支持半结构化数 系统集成和预言模e t 网格计算据和w e b 数据 型系统 7 第二章数据挖掘概述和w e b 服务技术介绍基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计 第四代和移动数据多个算法 数据管 移动和各种计算 普遍存在的计算 各种计算数 理、预言 设备 模型 据联合 模型、移 动系统 第一代数据挖掘系统支持一个或少数几个数据挖掘算法，这些算法用来挖掘向量 数据。在挖掘时候，数据一般一次性被调进内存进行处理。许多这样的系统已经商业 化。第一代系统的数据挖掘过程的成功依赖于数据的质量，数据的量也不能太大。 第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有较 高的可扩展性，而且能够挖掘大数据量、更复杂的数据集以及高维数据。这一代系统 通过支持数据挖掘模式和数据挖掘查询语言增加了系统的灵活性。在实施策略方面， 如果数据量足够大，并且频繁的变化，这就需要利用数据仓库或数据库技术进行管理。 因此第二代数据挖掘系统是必须的。不幸的是，目前的数据仓库设计是方便o l a p 操作的，而不是数据挖掘应用。这意味着真正的第二代数据挖掘系统必须使用自己专 门的数据管理系统，作为弥补目前数据库及数据仓库管理系统的缺陷，直到数据库和 数据仓库厂商对合适的数据挖掘原语提供充分的支持。第二代数据挖掘系统还应该能 够产生p m m l 或者类似p m m l 的开放格式，使得挖掘结果能够与预言模型系统集成。 第三代数据挖掘系统的特征是能够挖掘i n t c r n e v e x t r a n e t 的分布式和高度异质的 数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是对 建立在异构系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别的 支持。第三代系统另外还提供数据挖掘系统和预言模型系统之间的有效接口。在实施 策略方面，如果使用多个预言模型，或者预言模型需要经常修改，那么应该选择正在 出现的第三代数据挖掘系统，以支持这些功能。当然，这一代系统也能与数据库或者 数据仓库集成。第三代数据挖掘系统的一个重要的优点是由数据挖掘系统产生的预言 模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模块相结合提供决策 支持的功能。 第四代数据挖掘系统能挖掘嵌入式系统、移动系统和普遍存在的计算设备产生的 各种类型的数据。目前在公司的日常营运中，移动计算越来越重要，第四代数据挖掘 系统能够在此起关键的作用。将数据挖掘和移动计算相结合是当前的一个研究领域。 目前，第一代数据挖掘系统仍未发展完全，第二代、第三代数据挖掘系统已经出 现但还很不完善，第四代数据挖掘系统还没有出现。要使数据挖掘系统能够像数据库 系统一样被企业应用还需要很多的路要走。 8 基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计第二章数据挖掘概述和w e b 服务技术介绍 2 1 3 数据挖掘的步骤 数据挖掘的步骤可粗略地分为：问题定义、数据收集和预处理、数据挖掘算法执 行，以及结果的解释和评估，数据挖掘过程【l 】如图2 1 所示。 图2 - 1 数据挖掘过程示意图 嚣 1 闯题定义 数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息。因此，发现何种知 识就成了整个过程中第一个也是最重要的一个阶段。在问题定义过程中，数据挖掘人 员必须和领域专家以及最终用户紧密协作，一方面明确实际工作对数据挖掘的要求： 另一方面通过对各种学习算法的对比进而确定可用的学习算法。后续的算法选择和数 据准备都是在此基础上进行的。 2 数据收集和数据预处理 数据准备可分为三个子步骤：数据选取、数据预处理和数据交换。数据选取的目 的是确定发现任务的操作对象，即目标数据。目标是根据用户的需要从原始数据库中 抽取的组数据。数据预处理一般包括消除噪声、处理空值数据、消除重复记录、完 成数据类型转换( 如把连续数据转换为离散型的数据或是把离散型数据转换为连续型 数据) 等。当数据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成数据 仓库时完成了。数据变换的主要目的是消除数据维数或降低维数，即从初始特征中找 出真正有用的特征，以减少数据挖掘时需要考虑的特征或变量个数。 9 第二章数据挖掘概述和w e b 服务技术介绍基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计 3 数据挖掘算法执行 数据挖掘算法执行阶段首先根据对问题的定义明确挖掘的任务或目的，如分类、 聚类、关联规则分析或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的 算法。选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与 之相关的算法来挖掘：二是用户或实际运行系统的要求，有的用户可能希望获取描述 型的容易理解的知识，而有的用户只是希望获取预测准确度尽可能高的预测型的知 识，并不在意获取的知识是否易于理解。 4 ，结果解释和评估 数据挖掘阶段发现的模式，经过评估，可能存在冗余或无关的模式，这时需要将 其删除；也有可能模式不能满足用户要求，这时则需要将整个发现过程回退到前一阶 段，如重新选取数据、采用新的数据变换方法、设定新的参数值，甚至换一种算法等。 另外，数据挖掘最终是面向用户的，因此可能要对发现的模式迸行可视化，或者把结 果转换为用户易懂的另一种表示，如把分类决策树转换为“i f ”t h e n ”的形式。 数据挖掘算法执行，仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两个 影响要素：一是所采用的数据挖掘技术的有效性；二是用于挖掘的数据的质量和数量。 如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换，则挖掘的结 果是不会理想的。 整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现选择的数量不 太好或使用的挖掘技术产生不了期望的结果，这时，用户需要重复先前的过程，甚至 从头重新开始。 可视化在数据挖掘的各个阶段都扮演着重要的作用。特别是在数据准备阶段，用 户可能要使用散点图、直方图等统计可视化技术来显示有关数据，以期对数据有一个 初步的了解，从而为更好地选取数据打下基础。在挖掘阶段，用户则要使用与领域有 关的可视化工具。在表示结果阶段，则可能要用到可视化技术以使得发现的知识更易 于理解。 2 1 4 数据挖掘的任务和方法 数据挖掘的任务主要有两类，一个是描述型数据挖掘，一个是预测型数据挖掘。 描述型数据挖掘用于了解系统实际数据存在的特性，其目的是为预测作准备。预测型 数据挖掘是在描述型数据挖掘得出结论的基础上对系统的发展进行估计，通过预测型 1 0 ， 1 基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计 第二章数据挖掘概述和w e b 服务技术介绍 数据挖掘能得到最终需要的结果，能够为决策者提供直接的依据。大致来讲，数据挖 掘中的方法可以分为以下几个大类： 1 关联分析p j ( a s s o c i a t i o na n a l y s i s ) 关联分析就是发现事物之间有意义的联系和规则。如果事物若干属性中的两项或 多项之间存在关联，那么其中一项的属性值就可以依据其他的属性值进行预测。关联 规则挖掘问题可描述如下：设i = i 。，i ：，i 。j 是项的集合，d 是数据库事务的集合， 每个事务t 是不同项的集合，使得t i 。设a ，b 均是一个项集，事务t 2 a ，且t b 。 关联规则是形如a j b 的蕴含式，其中a c i ，b c i ，并且a n b 巾。规则a ；b 在事 务集d 中成立，具有支持度s u p p o r t 和置信度c o n f i d e n c e ，s u p p o r t ( a j b ) = p ( a n b ) ； c o n f i d e n c e ( a j b ) = p ( afb ) 。同时满足最小支持度阈值( m i ns u p p o r t ) 和最小 置信度阈值( m i n _ c o n f i d e n c e ) 的规则，就是可作为知识输出的强关联规则。 最著名的关联规则算法是a p r i o r i 算法嘲该算法发现关联规则分为两步第；， 步是迭代识别所有的频繁大项目集，要求频繁大项目集的支持度不低于用户设定的最 小支持度；第二步是从频繁大项目集中找出置信度不低于用户设定的最小置信度的关 联规则，构成规则集。发现所有的频繁大项目集是关联规则算法的核心，也是计算量 最大的部分。这种关联规则挖掘算法有很广泛的应用，如库存的策划、置物架的排放、 超级市场以及电子商务网站的推荐等。在每一个关联规则中都会包含每一个关联的关 系程度，通过此关联程度我们可以知道关联规则之间的关系程度大小。例如：5 的顾 客在购买啤酒之后有6 0 的机会去购买花生米，我们就可以知道，购买啤酒也购买花 生米的几率是6 0 ，而这种人有5 这么多。 2 分类分析( c 1 a s s i f i c a t i o na n a l y s i s ) 分类要解决的问题是为一个事物或对象归类。在使用上既可以用此方法分析已有 的数据，也可以用它来预测未来的数据。例如，用分类来预测哪些客户最倾向于对直 接邮件推销作出回应，又有哪些客户可能会换他的手机服务提供商，在医疗领域遇到 一个病例时用分类来判断一下从哪些药物着手比较好。常用的分类算法有决策树算 法。决策树算法分两个部分，一个是建立决策树部分，一个是修剪决策树部分。建立 部分要对所有的数据一直进行演算，直到所有的数据都拥有自己的类别。修剪部分则 对决策树最优化，大部分的算法都遵守最小长度决策树的原则。最典型的决策树算法 是i d 3 ，它采用自顶向下不回溯策略，能保证找到一个简单的决策树。还有其他的分 类算法，如c 4 5 ，c a r t ，s l i q ，s p r i n t 等。其中c 4 5 是对i d 3 的扩展，它将分类领 第二章数据挖掘概述和w e b 服务技术介绍基j = w e b 服务的数据挖掘系统关键技术的研究及其原型设计 域从类别属性扩展到数值型属性。 决策树使我们更了解数据库中的每个类别，并可以对未来的数据作分类。比如以 “好”与“坏”做分类，属于好的类别具有某种规则，属于坏的类别具有另外的规则。 找出这些规则，就可以预测未来数据归属于那个类别。 数据分类还有统计、粗糙集等方法。线性回归和线性辨别分析也是典型的统计模 型。近年来也有许多人研究使用人工神经网络方法作为在数据库中分类和规则提取方 法。 3 聚类分析( c l u s t e r i n ga n a l y s i s ) 聚类是借鉴统计学中基于距离的聚类方法对数据集的无指导划分的一种数据挖 掘方法，它在事先不规定分组规则的情况下，将数据按照其自身特征划分成不同的群 组。要求是在不同群组的数据之间有明显的差别，而每个群组内的数据之间尽量相似。 目前，聚类分析的算法可以分为以下几大类：分裂法、层次法、基于密度的方法、 基于网格的方法和基于模型的方法。下面是常见的几大类聚类分析算法的基本思想。 ( 1 ) 分裂法 给定一个有n 个元组或记录的数据集，分裂法将构造k 个分组，每个分组就代表 一个聚类，k n 。而且这k 个分组满足下列条件：每一个分组至少包含一条数据记录； 每个数据记录属于且仅属于一个分组；对于给定的k ，算法首先给出一个初始的分组 方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一 次好，而所谓好的标准就是；同一个分组中的记录越近越好，而不同分组中的记录越 远越好。使用这个基本思想的算法有k - m e a n s 算法、k - m e d o i d s 算法、c l a r a n s 算法。 ( 2 ) 层次法 这种方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分 为“白顶向上”和“自顶向下”两种方案。例如在“自底向上”方案中，初始时每一 个数据记录都是一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一 个组，直到所有的记录组成一个分组或者某个条件满足为止。代表算法有：b i r c h 算 法、c u r e 算法、c h a m e l e o n 算法等。 ( 3 ) 基于密度的方法 基于密度的方法与其他方法的一个根本区别是：它不是基于各种各样的距离的。 而是基于密度的，这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。 这个方法的指导思想是，只要一个区域中的点的密度大过某个阈值，就把它加到与之 1 2 基于w e b 服务的数据挖掘系统关键技术的研究及其原型设计第二章数据挖掘概述和n b 服务技术介绍 相近的聚类中去。代表算法有：d b s c a n 算法、o p t i c s 算法、d e n c l u e 算法等。 ( 4 ) 基于网格的方法 这种方法首先将数据空间划分为有限个单元的网格结构，所有的处理都是以单个 单元为对象的。这样处理的一个突出的优点就是处理速度很快，通常与目标数据库中 的记录的个数无关的，它只与把数据库空间分为多少个单元有关。代表算法有：s t i n g 算法、c l i q u e 算法、w v e c l u s t 职算法。 ( 5 ) 基于模型的方法 基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模 型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其他。它的一 个潜在的假定是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向： 统计的方案和神经网络的方案。 聚类分析方法在以下几个领域非常有用：数据挖掘、图像分割、模式分类、文件 恢复和机器学习等。但在这些问题中，几乎没有有关数据的先验信息可用，而用户又 要求尽可能少地对数据的可能性进行假设。在这些限制条件下，聚类方法特别适合于 挖掘数据间的内在关系以对它们的结构进行评估。 4 预测分析( p r e d i c t i o na n a l y s i s ) 预测分析是预测某些遗失数据的可能值，或者预测在某一个集合中某些属性值的 分布情形的一种数据挖掘方法。它包含了根据某种统计分析而得到的兴趣相关的属性 集合，并能依据这些集合来预测值的分布。它根据时间序列型数据，由历史的和当前 的数据去推测未来的数据的值，也可以认为是以时间为关键属性的关联知识。 目前，预测分析方法有经典的统计方法、神经网络和机器学习等。1 9 6 8 年b o x 和j e n k i n s 提出了一套比较完善的时间序列建模理论和分析方法，这些经典的数学方 法通过建立随机模型，如自回归模型、自回归滑动平均模型、求和自回归滑动平均模 型和季节调整模型等，进行时间序列的预测。由于大量的时间序列是非平稳的，其特 征参数和数据分布随时间的推移而发生变化。因此，仅仅通过对某段历史数据的训练， 建立单一的神经网络预测模型，还无法完成准确的再训练任务，当发现现存预测模型 不再适应于当前数据时，需要对模型重新训练，获得