（计算机应用技术专业论文）基于web的数据挖掘技术研究.pdf

哈尔滨： 程大学硕七学短论文 ；薯置墨；罱高；= ；i ；i i i i ；暑暑置；_ 盈_ 赢葛i ；i ；, f i - 若；墨； 摘要 随着w w w 上资源的与日俱增，如何使用有效的方法从中获取所需的信 息，成为研究人员所面临的一个重要问题。w e b 挖掘就是从w e b 上的数据( 如 w e b 日志、w e b 页面内容) 发现用户的浏览模式或寻找相关的w e b 页面。通 过w e b 挖掘既可以为站点管理者、投资商和广告商等提供合理建议，也可以 为用户提供功能强大的智能搜索引擎、个性化服务等。由于w e b 是一个无结 构的动态的分布式的信息系统，直接对它进行挖掘是困难的，获取的知识也 是不可靠的。然而，w e b 服务器的 o g 日志有着完整的结构。所以，我们可 以通过对w e b 日志文件的挖掘来实现对w e b 数据的使用挖掘。 本文首先分析了w e b 挖掘的动态，并提出了问题所在；然后介绍了数据 挖掘及w e b 挖掘技术，并阐述了x m l 与w e b 挖掘之间的关系。 详细描述了w e b 数据的使用挖掘系统的三个处理过程。 数据预处理阶段：w e b 使用信息的预处理是w e b 数据的使用挖掘任务中 的重要阶段，也是工作量较大的一部分。数据预处理的质量直接关系到数据 挖掘结果的好坏，本文主要讨论了预处理过程中的数据收集、数据清洗、用 户识别、会话识别、事务识别和路径修 h 等各个环节。 模式发现阶段：这部分工作也是本文研究的一个重点。首先介绍了w e b 日志挖掘中常用的路径分析、关联规则、分类与聚类技术；然后通过对问题 的描述，引出了本文所使用的一种高效的时间序列挖掘算法，该算法既保证 了时间序列挖掘上的完整性，同时又具有更高的效率。 模式分析及应用阶段：主要介绍了模式分析作为w e b 数据的使用挖掘的 最后一个重要步骤，为了让用户能够得到并理解所需要的知识，系统采取三 种方法，即查询机制、o l a p 技术和可视化技术。 针对w e b 数据自身的特点，总结了w e b 数据的使用挖掘的一般过程， 并且在考虑到系统功能扩展的同时，设计了系统的结构图。 关键词：数据挖掘：w e b 挖掘；预处理；模式发现：模式分析 a b s t r a c t t h er e s o u r c e so nw w w a r ei n c r e a s i n gd a yb yd a y o n ei m p o r t a n tp r o b l e m i sh o wt og e tt h er e q u i r e di n f o r m a t i o nv i ae f f e c t i v ea p p r o a c h e s w e bm i n i n gi sa t e c h n o l o g yt of i n du s e r s b r o w s i n gm o d e l o rr e l a t i v ew e bp a g e s w e bm i n i n gw i l t g i v er e a s o n a b l ea d v i e e sf o rw e bm a s t e r s ，i n v e s t o r sa n da d v e r t i s e r s ，e t c i tc a r la l s o p r o v i d ep o w e r f u li n t e l l i g e n ts e a r c h i n ge n g i n ea n dc u s t o m i z e ds e r v i c e s t oe n d 。 u s e r s s i n c ew e bi ss u c ha ni n f o r m a t i o ns y s t e mt h a ti su n s t r u c t u r e d ，d y n a m i ca n d d i s t r i b u t e d ，i ti sd i f f i c u l tt om i n ei td i r e c t l y h o w e v e r ，t h el o g o faw e bs e r v e rh a s a ni n t e g r a t e ds t r u c t u r e w ew o u l dm i n ew e bl o g st oi m p l e m e n tw e bd a t au s a g e m i n i n g t h et h e s i sa n a l y z e st h ec u r r e n tr e s e a r c hs i t u a t i o no fw e bm i n i n ga n d p r o p o s e st h ep r o b l e m d a t am i n i n ga n di t st e c b a a o l o g i e sa r ei n t r o d u c e d t h e r e l a t i o n s h i pb e t w e e nx m l a n dw e bm i n i n gi sp r e s e n t e d t h em e t h o do fa p p l y i n gm i n i n gs y s t e m st ow e bu s a g ei sd e s c r i b e di nd e t a i l ， w h i c hi n c l u d e st h r e ep h a s e s ： f i r s t l y ，t h e d a t aa r ep r e p a r e d t h ep r e p a r a t i o no fw e bi n f o r m a t i o ni s i m p o r t a n ti nw e bu s a g em i n i n g i ti sa l s o ah e a v yw o r k t h eq u a l i t yo fd a t a p r e p a r a t i o nw o u l da f f e c tt h er e s u l t so fd a t am i n i n gd i r e c t l y t h et h e s i sd i s c u s s e s t h ef o l l o w i n gi s s u e sd u r i n gt h ep r e p a r a t i o n ：d a t ac o l l e c t i o n ，d a t ac l e a n i n g ，u s e r i d e n t i f i c a t i o n ，s e s s i o ni d e n t i f i c a t i o n ，t r a n s a c t i o n i d e m i f i c a t i o na n d p a t h c o m p l e t i o n s e c o n d l y , t h ep a t t e r n sa r ed i s c o v e r i e d ，w h i c ha r ei m p o r t a n ti nt h er e s e a r c h t h et h e s i sp r e s e n t ss o m ec o m m o nt e c h n o l o g i e so f p a t ha n a l y s i s ，a s s o c i a t i o nr u l e s ， c l a s s i f i c a t i o na n dc l u s t e r i n g b a s e do nt h ed e s c r i p t i o no ft h e q u e s t i o n s ，a t i m e - s e q u e n c em i n i n ga l g o r i t h m w i t h h i g he f f i c i e n c y i s p r e s e n t e d ，w h i c h g u a r a n t e e st h ei n t e g r a l i t yo f t i m e - s e q u e n c em i n i n ga n dh i g h e re f f i c i e n c y f i n a l l y , p a t t e r na n a l y s i sa n da p p l i c a t i o n sa r ei n v e s t i g a t e d p a t t e r na n a l y s i si s 哈尔滨工程大学硕士学位论文 t h el a s ti m p o r t a n ts t e pi nt h ew e b u s a g em i n i n g t om a k eu s e r sg e ta n du n d e r s t a n d t h ek n o w l e d g e ，t h es y s t e mm a k e su s eo ft h ef o l l o w i n ga p p r o a c h e st e c h n o l o g i e s ： e n q u i r ym e c h a n i s m ，o l a pa n dv i s u a l i z a t i o nt e c h n o l o g i e s a c c o r d i n gt ot h ec h a r a c t e r i z a t i o no fw e bd a t a ，t h ec o m m o np r o c e d u r eo fw e b u s a g em i n i n gi sc o n c l u d e d t h es t r u c t u r eo ft h es y s t e m si sd e s i g n e d ，w h i c ht a k e s t h ee x t e n s i o no fs y s t e mf u n c t i o n si n t oa c c o u n t k e yw o r d s ：d a t am i n i n g ；w e bm i n i n g ；d a t ap r e p a r a t i o n ；p a t t e r nd i s c o v e r y ；p a t t e r n a n a l y s i s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日觏：世一其箩j e t 哈尔滨工程大学硕士学位论文 1 1问题提出的背景 第1 章绪论 近年来，i n t e m e t 使计算机、网络、通信合而为一，网络经济等新概念的 出现，以其巨大的社会效益和极富挑战与机遇的内涵，成为信息科学最引人 注目的研究课题。然而，网络在快捷、方便地带来大量信息的同时，也带来 了一大堆的问题，诸如：信息过量难以消化：信息真假难以辨识；信息安全 难以保证；信息形式不一致、难以统一处理。以及如何快速、准确地获得有 价值的网络信息，如何理解已有的历史数据并将其用于预测未来的行为，如 何从这些海量数据中发现知识，等等。正是这些问题导致了知识发现和数据 挖掘领域的出现。知识发现( k n o w l e d g ed i s c o v e r y 简称k d ) 和数据挖掘( d a t a m i n i n g 简称d m ) 是集统计学、人工知识、模式识别、并行计算、机器学习、 数据库等技术的一个交叉性的研究领域。 数据挖掘是指从大型数据库或数据仓库中提取人们感兴趣的知识，这些 知识是隐含的、事先未知的潜在的有用信息。它是目前国际上数据库和信息 决策领域的最前沿研究方向之一，是在对更深入、更充分地利用信息资源的 迫切需求背景下产生并迅速发展起来的，引起了学术界和工业界的广泛关注。 w e b 上的信息量随着i n t e m e t 的飞速发展正以惊人的速度增长，面对w e b 上海量、分布、动态、异质、复杂、非结构化的丰富信息资源，用户如何从 中查找、抽取自己想要的数据和有用信息成了一大难题，也正是这个难题加 速了w e b 挖掘技术的诞生。w e b 挖掘就是从大量的w e b 文档和w e b 活动中 发现、抽取感兴趣的、潜在的有用模式和隐含的、事先未知的、潜在的信息。 它以数据挖掘、文本挖掘、多媒体挖掘为基础，并综合运用计算机网络、数 据库与数据仓库、人工智能、信息检索、信息提取、机器学习、统计学、概 率理论、可视化、计算机语言学、自然语言理解等多个领域的技术，将传统 的数据挖掘技术与w e b 结合起来 o ”。 w e b 挖掘从数据挖掘发展而来，与传统的数据挖掘相比又有许多独特之 处。传统的数据挖掘的对象限于数据库中的结构化数据，利用关系表格等存 哈尔滨工程大学硕士学位论文 储结构来发现知识，而w e b 挖掘的对象是大量异质、分布、半结构化的w e b 数掘，自身的特殊性决定了w e b 挖掘无法直接应用传统的数据库领域的挖掘 方法和模型【8 1 。如何解决w e b 数据规范化和预处理的问题，使挖掘系统与数 据库紧密耦合，提供一个集成的信息处理环境，成了w e b 挖掘的前提。 w e b 挖掘与w e b 信息检索也不同，区别主要表现在以下几个方面： 1 、目的不同。信息检索的目的在于帮助用户发现w e b 上的资源，从大 量文档中找到能满足其查询请求的文档子集，通常不能发现隐藏在数据后面 的联系；而w e b 挖掘能够将大量看似无关的w e b 数据关联起来，应用数据 挖掘方法发现其中的规则和知识以供决策支持。 2 、着眼点不同。信息检索着眼于文档中显式存储的字词和链接；而w e b 挖掘试图更多地理解其内容、结构和使用。信息检索针对某一特定领域进行 信息或文档的收集，可以看作是用于w e b 挖掘中文档分类的一种情况。 3 、方法论不同。信息检索是目标驱动的，用户需要明确提出查询要求， 咀关键词形式表示的简单目标，无法处理用户给出的样本形式的复杂模糊目 标；而挖掘可以从文本中提取出目标信息的特征，其结果独立于用户的信息 需求，常常是用户无法预知的。 4 、评价方法不同。信息检索使用精度( p r e c i s i o n ) 和召回率( r e c a l l ) 来 评价其性能，要求返回尽可能多的相关文档，同时不相关的文档尽可能少； 而挖掘采用收益( g a i n ) 、置信度( c e r t a i n t y ) 、简洁性( s i m p l i c i t y ) 等来衡量 所发现知识的有效性、可用性和可理解性。 w e b 挖掘不同于w e b 信息检索，它是比信息检索层次更高的技术。然而， 二者又是相辅相成的。一方面，它们各有所长，有各自适用的场合；另一方 面，可以利用w e b 挖掘的研究成果来提高信息检索的精度和效率，改善检索 结果的组织，使信息检索系统发展到一个新的水平。 1 2 课题研究的意义 数据挖掘在传统的结构化的事务数据的挖掘领域，已经取得了比较成功 的应用。然而，w e b 上的信息不同于数据库，数据库有规范的数据结构，而 哈尔滨工程大学硕士学位论文 w e b 上包括文本、图片、v i d e o 等多种信息，它们是半结构化的。因此，w e b 上的挖掘需要用到不同于常规的数据库开采的很多技术。现实领域中，存在 的多是半结构化的、异源的数据，w e b 挖掘的研究也将极大地推动数据挖掘 在其他领域的应用。 随着越来越多组织、企业在互联网上开展业务，传统的市场营销策略、 企业战略制定技术也都纷纷转向i n t e m e t 。w e b 是i n t e r n e t 上存储和发布信息 最普遍的载体，人们从w e b 上获取信息的模式，成了i n t e r n e t 环境下各企业 共同关注的一大热点。分析用户使用模式有助于企业确定顾客消费的生命周 期，针对不同的产品定制相应的营销策略；可以找出如何优化一个网站结构 的策略：可以确定预传哪些页面到客户端，从而提高网站的效率；另外，对 那些要通过w o r l dw i d ew e b 发送广告的企业，分析用户使用模式有助于帮助 改善市场营销策略，如把广告放在适当的w 曲页面上或更好地理解用户的兴 趣。w e b 使用模式的挖掘，能够辅助改进分布式网络的设计性能，如在有高 度相关的站点间提供快速有效的访问通道等。 特别要指出的是，w e b 挖掘技术从一开始就是面向应用的。它不仅是面 向特定数据源的简单检索查询调用，而且要对这些无结构的、异源的数据进 行微观、中观乃至宏观的清洗、集成、统计、分析、综合和推理，以指导实 际问题的求解，并试图发现用户间、页面间的相互关联，甚至利用已有的数 据对用户未来的活动进行预测。因此，w e b 挖掘被信息产业界认为是最有前 途的交叉学科。 1 3w e b 挖掘的研究动态 当前w e b 正在深度和广度方面飞速地发展着，前所未有地改变着我们的 生活，在当今社会扮演着越来越重要的角色。 w e b 是一个巨大的、分布广泛的、全球性的信息服务中心，涉及新闻、 广告、消费信息、金融管理、教育、电子商务和许多其他信息服务，还包含 了丰富和动态的超链接信息，以及w 曲页面的访问和使用信息。 在w e b 迅速发展的同时，我们不能忽视“信息爆炸”的问题，即信息极 哈尔滨工程大学硕士学位论文 大丰富而知识相对匮乏。在这些大量、异质的w e b 信息资源中，蕴含着具有 巨大潜在价值的知识，为数据挖掘提供了丰富的资源 9 - 1 1 o 另外，w e b 上的 一些主要工作，如w e b 站点设计、w e b 服务设计、w e b 站点的导航设计、电 子商务等工作也变得越来越复杂和重要，人们迫切需要能够从w e b 上快速、 有效地发现资源和知识的工具。 从2 0 世纪6 0 年代以来，信息检索领域在索引模型、文档内容表示、匹 配策略等方面取得了许多研究成果，这些成果被成功地应用在w e b 上产生 了搜索引擎，例如y a h o o 、g o o g l e 等。现在大多数的搜索引擎以搜索文字信 息为主，采用集中方式，试图遍历整个w e b ，对其上所有的文档生成索引， 根据用户的查询请求，按照定的算法从索引数据库中查找相应的信息返回 给用户，完成对w e b 的搜索，如定位包含某关键字的w e b 页面等i l 小j 。 搜索引擎部分地解决了资源发现问题，但其覆盖率有限，精确度不高， 硬件设施消耗大，维护起来也比较困难，其效果远不能使人满意。改进的元 搜索引擎方式虽然可以一次让多个w e b 搜索引擎并发查询，扩大了查询的覆 盖面，但元搜索引擎对搜索引擎的依赖，使它无法从根本上解决上述问题( j “。 此外，搜索引擎的目的在于发现w e b 上的资源，但就w 曲上的知识发现而 言，即使检索精度再高，搜索引擎也不能够胜任。为此，需要开发比信息检 索更高的新技术。 从大量数据的集合中发现有效、新颖、有用、可理解的模式，数据库领 域采用了数据挖掘技术。但是，数据挖掘的绝大部分工作所涉及的是结构化 数据库，很少有处理w e b 上的异质、半结构化信息的工作【l 1 。解决这些问题 的一个途径，就是将传统的数据挖掘技术和w e b 结合起来，进行w e b 挖掘。 w e b 挖掘是数据挖掘技术和理论应用于w w w 资源进行挖掘的个新兴 领域，目前在该研究领域中，根据挖掘对象的不同大致分为三个方面的挖掘 研究：w e b 内容挖掘、w e b 结构挖掘和w e b 数据的使用挖掘 1 6 - 1 7 j 。 w e b 挖掘作为数据挖掘的一个新主题，引起了人们极大的兴趣，它实现 了对w e b 存取模式、w e b 结构和规则，以及动态的w e b 内容的查找。w e b 挖掘可以在很多方面发挥作用，如对搜索引擎的结构进行挖掘，确定权威页 4 喻尔滨上程大学硕士学位论文 面，w e b 文档分类，w e bl o g 挖掘、智能查询、建立m e t a - - w e b 数据仓库等a 同时，它也是一个富于争议的研究方向，基于w e b 的数据挖掘的研究才刚刚 起步，需要国内外学者在理论上开展更多的讨论。 目前，国际上对此领域研究主要集中在：搜索引擎的设计、文件自动分 类技术、关键词的自动提取、半结构化信息的提取以及w e b 上新型应用的研 究等1 8 】。应用领域中通用的w e b 挖掘工具还比较少，主要分为文本信息挖掘 工具和用户访问模式挖掘工具。 i b m 公司推出的w e b 文本挖掘工具i n t e l l i g e n tm i n e rf o rt e x t ，是i b m 开 发的i n t e l l i g e n tm i n e r 家族的一个成员，是一个高效的文本信息挖掘工具，可 以实现全文搜索、文本分析、文档查询和检索。主要是由信息提取器工具组 成，包括高级搜索引擎t e x t m i n e r 、w e b 访问工具和文本分析工具三部分，其 中文本分析工具完成的才是对文本信息的挖掘，这部分工具可以独立使用， 但将它与文本搜索工具结合使用才能发挥更强大的作用。 a n a l o g 是一个用来分析服务器日志文件的工具，适用于w i n d o w s 及 u n i x 等操作系统中，可以直接在服务器上运行，也可以将日志文件下载到 客户端运行。适用于个人和小规模分析应用，是一个实用性很强的日志文件 分析工具，从h t t p ：n w w w s t a t l a b c a i n a c u k 上可以免费获得该软件。用户导航 行为挖掘工具w u m ( w e bu t i l i z a t i o nm i n e r ) 是一种序列挖掘器，主要用来 分析用户导航行为，适用于从任何类型的日志文件中发现用户导航信息。可 以从h t t p ：w u m w i w i h u - b e r l i n d e 上免费获得w u m 5 0 的演示版本l 眦叭。 w e b 上的数据的最大特点是半结构化。在众多的研究课题中，对半结构 化数据结构的研究是一个非常重要的方向，半结构化数据模型和半结构化数 据模型抽取技术是面向w e b 的数据挖掘技术实施的前提，是当今数据挖掘研 究领域的热点【2 i 】【8 1 。 可扩展标记语言x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 的出现，弥补了 h t m l 的不足，将成为新一代i n t e m e t 数据组织和交换的事实标准。x m l 是 由w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ，万维网协会) 设计并推荐使用的新一 代标记语言。1 9 9 6 年7 月w 3 c 在j o n b o s a k ( s u n 公司的网络技术专家) 的 喻尔滨“! 一程大掌硕士学位论文 建议下成立了x m l 规范制定小组，其目的是为了将标准通用标记语言s g m l ( s t a n d a r dg e n e r i cm a r k u pl a n g u a g e ) 方便地应用于网络，1 9 9 8 年2 月1 0 日 经w 3 c 认可，x m l l 0 建议书正式公布于众拉“。x m l 改进了h t m l 与s g m l 的不足，是一种使页面更具有弹性、更容易添加新功能而又不失统一标准的 语言格式，为w e b 数据管理提供了新的数据模型。可以说，x m l 是w e b 上 的半结构数据，它的出现推动了半结构数据研究的发展，为半结构数据的研 究提供了广阔的应用前景【8 1 1 2 2 1 。 未来随着x m l 的兴起，大量的w e b 页面用x m l 书写，w e b 页面会蕴 含更多的结构化和语义信息，便于设计和实现基于w e b 的信息搜索和知识发 现语言，有利于促进不同w e b 站点间的信息交换和多层次w e b 数据库的信 息存取。w e b 挖掘工作将变得更为有效，也更为容易。 1 4 作者的主要工作和论文的组织 本文对基于w e b 数据的使用挖掘技术进行了比较全面的研究，针对w e b 数据的使用挖掘的一般过程，即数据准备阶段、模式发现阶段和模式分析阶 段，采用了不同的算法。在此基础上，考虑到系统功能的扩展，作者设计了 系统模型，并对数据准备阶段与模式发现阶段所采用的关键技术，如：数据 清洗算法，识别用户的启发式算法，用户会话识别算法和时间序列算法进行 了重点研究。 论文的具体组织方式如下： 第一章绪论，简要介绍了问题提出的背景、课题研究的意义以及w 曲挖 掘的研究动态，最后介绍了本论文完成的主要工作和论文的组织。 第二章首先介绍了数据挖掘技术，其中包括数据挖掘的定义、数据挖掘 的过程以及数据挖掘的分类；然后介绍了w e b 挖掘的定义和w e b 挖掘的分 类，其中系统地介绍了w e b 的内容挖掘、w e b 数据的使用挖掘和w e b 的结 构挖掘；最后阐述了x m l 与w e b 挖掘之间的关系。 第三章首先介绍了w e b 使用信息的预处理，因为数据预处理的质量直接 关系到数据挖掘结果的好坏，所以在数据的使用挖掘任务中成为工作量较大 哈尔滨工程大学硕士学位论文 的一部分。在此基础上，通过例子详细讨论了预处理过程中包括数据收集、 数据清洗、用户识别、会话识别、事务识别和路径修补等各个环节。 第四章在讨论了数据进行一系列预处理之后，按照相应的数据形式来选 择对应的数掘挖掘算法。首先介绍了w e b 日志挖掘中常用的路径分析、关联 规则、分类与聚类技术；然后通过对问题的描述，引出了本文所使用的一种 高效的时间序列挖掘算法，该算法既保证了时间序列挖掘上的完整性，同时 又具有更高的效率。 第五章主要介绍了模式分析作为w e b 数据的使用挖掘的最后一个重要步 骤，为了让用户能够得到并理解所需要的知识而采取的三种方法，即查询机 制、o l a p 技术和可视化技术。 第六章针对w e b 数据自身的特点，总结了w e b 数据的使用挖掘的一般 过程，并且在考虑到系统功能扩展的同时，设计了系统的结构图。 最后，作者对所做的工作加以总结，并提出了有待进一步探讨的问题。 哈尔滨工程大学硕士学位论文 第2 章数据挖掘与w e b 窆掘技术 2 1 数据挖掘技术 2 ，1 1 数据挖掘的定义 数据挖掘，比较公认的定义是wj f r a w l e y 和gp i a t e t s k ys h a p i r o 等人 提出的：数据挖掘，就是从大型数据库的数据中提取人们感兴趣的知识，这 些知识是隐含的、事先未知的潜在的有用信息，提取的知识表示为概念 ( c o n c e p t s ) 、规则( r u l e ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式怛。 这里把数据挖掘的对象定义为数据库，更广义的说法是：数据挖掘意味 着在一些事实或观察数据的集合中寻找模式的决策支持过程。数据挖掘的对 象不仅仅是数据库，也可以是文件系统，或其他任何组织在一起的数据集合， 例如，本文的研究对象是w w w 信息资源。 从数据开采的定义可以看出作为一个学术领域，数据开采和知识发现 k d d 具有很大的重合度，大部分学者认为数据开采和知识发现是等价的概 念，人工智能领域习惯称k d d ，而数据库领域习惯称数据开采。有学者把 k d d 看作发现知识的完整过程，而数据挖掘只是这个过程中的一个部分。这 里，我们倾向于前一种观点，认为数据挖掘从理论上和技术上继承了知识发 现领域的成果，同时又有着独特的内涵，数据挖掘更着眼于设计高效的算法 以达到从巨量数据中发现知识的目的。 与数据挖掘关系密切的研究领域包括归纳学习( i n d u c t i v el e a r n i n g ) 、机 器学习( m a c h i n el e a r n i n g ) 和统计( s t a t i s t i c s ) 分析。特别是机器学习被认 为和数据挖掘的关系最密切。二者的主要区别在于：数据挖掘的任务是发现 可以理解的知识，而机器学习关心的是提高系统的性能，因此训练神经网络 来控制一根倒立棒是一种机器学习过程，但不是数据挖掘；数据挖掘的对象 是大型数据库，一般来说机器学习处理的数据集要小得多，因此效率问题对 数据挖掘来说是至关重要的。 哈尔滨工程大学硕士学位论文 21 2 数据挖掘的过程 数据挖掘指根据对数据的分析，建立对数据的特性以及数据之间关系描 述的模式的过程。在这个描述中，数据是一系列事实的集合( 例如数据库中 的实例) ，而模式是使用某种语言对数据集合一个子集的描述。过程是指挖掘 中的步骤。数据挖掘一般由三个主要阶段组成：数据准备、数据挖掘，以及 结果的解释评估。知识的发现可以描述为这三个阶段的反复过程。图2 1 给 出了数据挖掘的整个过程，这个过程是交互和迭代的，其中许多时候需要用 户的参与。 数据清洗l l 数据集成l 1 数据选择l e i 数据转换l l 图2 1 数据挖掘的过程 1 数据准备 数据准备又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理 ( d a t ap r e p r o c e s s i n g ) 和数据变换( d a t a t r a n s f o r m a t i o n ) 。数据选取的目的是 确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始数据源 中抽取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消 除重复记录、完成数据类型转换等。一般来说，如果数据挖掘的对象是数据 仓库，则数据预处理已经在生成数据仓库时完成了。数据变换的主要目的是 哈尔滨工程大学硕士学位论文 消减数据维数，即从初始特征中找出真正有用的特征以减少数据开采时要考 虑的特征或变量个数。 2 数据挖掘 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据总结、分类、 聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用 什么样的挖掘算法。同样的任务可以用不同的算法来实现。选择实现算法有 两个因素要考虑：一是不同的数据有不同的特点，因此需要用与之相关的算 法来开采：二是用户或实际运行系统的要求，有的用户可能希望获取描述型 ( d e s c t l p t i v e ) 的，容易理解的知识( 采用规则表示的挖掘方法显然要好于 神经网络之类的方法) ，而有的用户或系统的目的是获取预测准确度尽可能高 的预测型( p r e d i c t i v e ) 知识。 3 结果解释和评估 数据挖掘阶段发现出来的模式，经过用户或机器的评估，可能存在冗余 或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求，这时就 需要整个发现过程退回到发现阶段之前，如重新选取数据、采用新的数据变 换方法、设定新的数据挖掘参数值，甚至更换挖掘算法。由于数据挖掘系统 最终是面向用户的，因此可能要对发现的模式进行可视化，或者把结果转换 为用户易懂的表现形式。 数据挖掘过程应该注意以下几点： ( 1 ) 数据挖掘仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有两 个影响要素：一是采用的数据挖掘技术的有效性，二是用于挖掘的数据的质 量和数量( 数据量的大小) 。如果选择了错误的数据或不适当的属性，或对数 据进行了的错误转换，则有可能得到不正确的挖掘结果。 ( 2 ) 整个挖掘过程是一个不断反馈的过程。假如用户在挖掘途中发现选 择的数据不太好，或使用的挖掘技术产生不了期望的结果，这时就需要重复 先前的过程，甚至从头重新开始。 ( 3 ) 可视化在数据挖掘的各个阶段都发挥着重要的作用。特别是，在数 据准备阶段，用户可能要使用散点图、直方图等可视化统计技术来显示有关 哈尔滨工程大学硕士学位论文 数据，以期对数据有一个初步的理解，从而为更好地选取数据打下基础e 在 挖掘阶段，用户有可能要使用与领域问题有关的可视化工具。在表示结果阶 段，则可能又要用到其他的可视化技术。 2 1 3 数据挖掘的分类 从不同的角度出发，会有不同的关于数据挖掘的划分，我们从数据挖掘 的任务出发，对数据挖掘进行简单的分类。 1 数据总结 数据总结的目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最 简单的数据总结方法是对数据库的各个字段求和、求平均值、求方差值等统 计操作，或者用直方图、饼状图等图形方式表示数据。数据挖掘主要从数据 泛化的角度来讨论数据总结。数据泛化是一个把数据库中的有关数据从低层 次抽象到高层次上的过程。由于数据库上的数据或对象所包含的信息总是最 原始、最基本的信息。人们有时希望能从较高层次的视图上透视数据，因此 需要对数据进行不同层次上的泛化，以适应各种查询要求。数据泛化目前主 要有两种技术：多维数据分析方法和面向属性的归纳方法( a o i ) 。 多维数据分析方法是一种数据仓库技术，也称作联机分析处理( o l a p ) 。 数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合【2 4 】。 决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、 最大、最小等汇集操作，这类操作的计算量特别大。因此一种很自然的想法 是，把汇集操作结果预先计算并存储起来，以便于决策支持系统使用。汇集 操作结果的存储称作多维数据库。多维数据分析技术已经在决策支持系统中 获得了成功的应用，如著名的s a s 数据分析软件包、b u s i n e s so b j e c t 公司的 决策支持系统b u s i n e s so b j e c t ，以及i b m 公司的决策分析工具都使用了多维 数据分析技术。 采用多维数据分析方法进行数据总结，它针对的是数据仓库，存储的是 脱机的历史数据。为了处理联机数据，研究人员提出了一种面向属性的归纳 方法。它的思路是，直接对用户感兴趣的数据视图( 用一般的s q l 查询语言 哈尔滨工程大学硕士学能论文 即可获得) 进行泛化，而不是像多维数据分析方法那样预先就存储好了泛化 数据。方法的提出者称这种数据泛化技术为面向属性的归纳方法。原始关系 经过泛化操作后得到的是一个泛化关系，它从较高的层次上描述了低层次上 的原始关系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足 用户需要的知识，如在泛化关系基础上生成特性规则、判别规则、分类规则， 以及关联规则等。 2 分类发现 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分 类的目的是通过机器学习，产生一个分类函数或分类模型( 也常常称作分类 器，c l a s s f i e r ) ，该模型把数据库中的数据项映射到给定类别中的某一个。分 类和回归都可用于预测。预测的目的是从利用历史数据汜录中自动推导出对 给定数据的推广描述，从而能对未来数据进行预测。和回归方法不同的是， 分类的输出是离散的类别值，而回归的输出则是连续数值。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数 据库记录或元组( t u p l e s ) 构成，每个元组是一个由有关字段( 又称属性或特 征) 值组成的特征向量。此外，训练样本还有一个类别标记。一个具体样本 的形式可为：( v l ，v 2 v 。；c ) ；其中表示字段值，c 表示类别。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统 计方法包括贝叶斯法和非参数法( k 近邻学习或基于事例的学习) ，对应的知 识表示则为判别函数和原型事例。机器学习方法包括决策树法和规则归纳法， 前者对应地表示为决策树或判别树，后者则一般为产生式规则。神经网络方 法主要是b p 算法，它的模型表示是前向反馈神经网络模型( 由代表神经元 的节点和代表联接权值的边组成的一种体系结构) ，b p 算法本质上是一种非 线性判别函数。另外，最近又兴起了一种新的方法；粗糙集( t o u g hs e t ) ，其 知识表示是产生式规则。 不同的分类器有不同的特点。有三种分类器评价或比较尺度：( 1 ) 预测 准确度；( 2 ) 计算复杂度；( 3 ) 模型描述的简洁度。 另外，分类的效果一般和数据的特点有关，有的数据噪声大，有的有缺 哈尔滨工程大学硕士学位论文 值，有的分布稀疏，有的字段或属性间相关性强，有的属性是离散的而有的 是连续值或混合式的。目前普遍认为不存在某种方法能适合于各种特点的数 据。 3 聚类 聚类是把一组个体按照相似性归成若干类别，即“物以类聚”。它的目的 是使得属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体问 的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法 和面向数据库的方法。 在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一( 其 它两种是回归分析和判别分析) 。它主要研究基于几何距离的聚类，如欧氏距 离、明考斯基距离等。传统的统计聚类分析方法包括聚类法、分解法、加入 法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法 是一种基于全局比较的聚类，它需要考察所有的个体才能决定类的划分；因 此它要求所有的数据必须预先给定，而不能动态增加新的数据对象。聚类分 析方法不具有线性的计算复杂度，难以适用于数据库非常大的情况。 在机器学习中聚类称为无监督或无教师归纳：因为和分类学习相比，分 类学习的例子或数据对象有类别标记，而聚类的例子则没有标记，需要由聚 类学习算法来自动确定。很多人工智能文献中，聚类也称概念聚类：因为这 里的距离不再是统计方法中的几何距离，而是根据概念的描述来确定的。当 聚类对象可以动态增加时，概念聚类则称为概念形成。 在神经网络中，有一类无监督学习方法：自组织神经网络方法；如 k o h o n e n 自组织特征映射网络、竞争学习网络，等等。在数据挖掘领域里， 见报道的神经网络聚类方法主要是自组织特征映射方法，i b m 在其发布的数 据挖掘白皮书中就特别提到了使用此方法进行数据库聚类分割。 4 关联规则发现 关联规则是形式如下的一种规则，“在购买面包和黄油的顾客中，有9 0 的人同时也买了牛奶”( 面包+ 黄油( 牛奶) ) 。用于关联规则发现的主要对象 是事务型数据库，其中针对的应用则是售货数据，也称货篮数据。一个事务 哈尔滨工程大学硕士学位论文 一般由如下几部分组成：事务处理时间，一组顾客购买的物品，有时也有顾 客标识号( 如信用卡号) 。 由于条形码技术的发展，零售部门可以利用前端收款机收集存储大量的 售货数据。因此，如果对这些历史事务数据进行分析，则可对顾客的购买行 为提供极有价值的信息。例如，可以帮助如何摆放货架上的商品( 如把顾客 经常同时买的商品放在一起) ，帮助如何规划市场( 怎样相互搭配进货) 。可 见，从事务数据中发现关联规则，对于改进零售业等商业活动的决策非常重 要。 设i = “，i 2 ，i 。) 是一组物品集( 一个商场的物品可能有上万种) ，d 是 一组事务集( 称之为事务数据库) 。d 中的每个事务t 是一组物品，显然满 足t c i 。如果x c t ，称事务t 支持物品集x 。关联规则是- - , e e 蕴含关系： x y ，其中x c i ，y c i ，且x n y = 西。 ( 1 ) 称物品集x 具有大小为s 的支持度，如果d 中有s 的事务支持物 品集x ； ( 2 ) 关联规则x y 在事务数据库d 中具有大小为s 的支持度，如果物 品集x y 的支持度为s ； ( 3 ) 称规则x y 在事务数据库d 中具有大小为c 的可信度，如果d 中支持物品集x 的事务中有c 的事务同时也支持物品集y 。 如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷 多的关联规则。事实上，人们一般只对满足一定的支持度和可信度的关联规 则感兴趣。在文献中，一般称满足一定要求的( 如较大的支持度和可信度) 的规则为强规则。因此，为了发现出有意义的关联规则，需要给定两个阂值： 最小支持度和最小可信度。前者即用户规定的关联规则必须满足的最小支持 度，它表示了一组物品集在统计意义上的需满足的最低程度；后者即用户规 定的关联规则必须满足的最小可信度，它反映了关联规则的最低可靠度。 在实际情况下，一种更有用的关联规则是泛化关联规则。因为物品概念间 存在一种层次关系，如夹克衫、滑雪衫属于外套，外套、衬衣又属于衣服类。 有了层次关系后，可以帮助发现一些更多的有意义的规则。例如，“买外套一 哈尔滨工程大学硕士学位论文 ；i i = = i ；j i = ；i i i ；j i j 目i 目j i _ ；i i - i ；i i - i ；i _ j ；i i s i ；i 日1 1 ； 买鞋子”( 此处，外套和鞋子是较高层次上的物品或概念，因而该规则是一种 泛化的关联规则) 。由于商店或超市中有成千上万种物品，平均来讲，每种物 品( 如滑雪衫) 的支持度很低，因此有时难以发现有用规则；但如果考虑到较 高层次的物品( 如外套) ，则其支持度就较高，从而可能发现有用的规则。 另外，关联规则发现的思路还可以用于序列模式发现。用户在购买物品 时，除了具有上述关联规律，还有时间上或序列上的规律，因为，很多时候 顾客会这次买这些东西，下次买同上次有关的一些东西，接着又买有关的某 些东西。 2 2w e b 挖掘技术 2 21w e b 挖掘的定义 w e b 挖掘是一项综合技术，涉及w e b 技术、数据挖掘、计算机语言学、 信息学等多个领域。不同研究者从