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

中文摘要 中文摘要 万维网是到目前为止世界上最丰富和最密集的信息来源。如何开发和利用这 些丰富的资源就成了人们普遍关注的闯题。于是，数据挖掘技术和网络应用研究 的结合- w 曲数据挖掘技术( w e bm i n i n g ) 构成了当今比较活跃的一个研究 领域。w e b 日志挖掘是w e b 使用挖掘的一个分支，它作为w 曲挖掘的一个重要 组成部分，具有独特的理论和实践意义。 本文系统地阐述了从数据挖掘、w 曲数据挖掘到w e b 日志挖掘整个过程， 重点讨论w e b 日志挖掘。w e b 日志挖掘通过对日志记录的挖掘，发现用户访问 页面的模式，从而进一步分析和研究日志记录中的规律，以期改进站点的性能和 组织结构，提高用户查找信息的质量和效率，并通过统计和关联的分析找出特定 用户与特定地域、特定时间、特定页面等要素之间的内在联系。 w e b 日志挖掘预处理对象是原始日志文件中包含的数据，其中不完整的、 冗余的、错误的数据需要进行处理。本文针对数据预处理过程中涉及到的关键问 题和技术进行详细的剖析和论述。w e b 日志挖掘中模式分析与模式表达通过发现 的模式研究用户w e b 浏览行为，理解访问者的浏览兴趣，这些都是提高w e b 质 量和改善站点结构设计的重要环节。本文研究了规则归纳的模式挖掘方法，探讨 了关联规则和序列模式的挖掘算法，比较各算法优劣，提出使用f p和t r e e p r e f i x s p a n 应用于关联规则和序列模式的挖掘。最后将w e b 日志挖掘技术应用到 天津铁路工程学校网站，对其w e b 服务器的日志记录进行挖掘，建立一个w e b 日志挖掘系统。网络管理人员可以根据w e b 日志的分析结果改进网站的设计， 实现网站的有效管理。 关键词：数据挖掘w e b 数据挖掘w e b 日志挖掘关联规则序列模式 模式分析 a b s t r a e t a b s t r a c t t h ew o r l dw i d ew e bi sad i s t r i b u t e dg l o b a li n f o r m a t i o nr e s o u r c ec o n t a i n i n ga l a r g ea m o u n to fd a t ar e l e v a n tt oe s s e n t i a l l ya l ld o m a i n so fh u m a na c t i v i t y i t i s b c c , o m eaq u e s t i o nt op a ya t t e n t i o nh o wt od e v e l o pa n du s et h er i c hr e s o u l - c e t h e r e f o r e i tc o n s t i t u t eaa c t i v er e s e a r c hf i e l da l p r e s e n t t h a td a t am i n i n g t e c h n o l o g yc o m b m ew i t hn e t w o r ka p p l i c a t i o nr e s e a r c h i e w e bd a t am i n i n g t e c h n o l o g y w e bl o gm i n i n gi sa b r a n c ho fw e bu s a g em i n i n ga n dh a ss p e c i a lt h e o r y a n dp l d c l d c es i g n i f i c a n c ea sa ni m p o r t a n tp a r to f w e bm i n i n g i nt h i st h e s i s ，t h ep r o c e s so fd a t am i n i n g ，w e bd a mm i n i n ga n dw e bl o gm i n i n g w a sr e p o r t e d f o c u s i n go nt h ew e b l o gm i n i n g i td i s c o v e r st h a tu s e rv i s i t e sw e bp a g e p a t o mb yw e bl o gr e c o r dm i n i n g f u r t h e r , i ta n a l y s i sa n ds t u d i e st h eo r d e ro f w e bl o g r e c o r ds ot h a tt oi m p r o v et h ec h a r a c t e r i s t i ca n do r g a n i z a t i o n a ls m m t u r eo fw e b s i t s ，t o i m p r o v et h eq u a l i t ya n de f f i c i e n c yt h a t u s e rr e s e a r c h e si n f o r m a t i o n , t of i n dt h e r e l a t i o nb e t w e e ns p e c i a lu s e ra n ds p e c i a la r e a , t i m e ，p a g eb ys t a t i s t i c a la n da s s o c i a t i o n a n a l y s i s t h eo b j e c to fd a t a p r c p r o c e s s i n gi sd a t at h a ti sc o n t a i n e di ni n i t i a lw e bl o gf i l e s t h o s eh a l f - b a k e d , r e d u n d a n t , i n a c o u r a t ed a t an e e dt op r o c e s s i nt h i st h e s i s ，t h ek e y t e c h n o l o g ya b o u td a t a p r e p r o e e s s i n gi ss t u d i e da n dd i s e u s s e d t h ep a t e r na n a l y s i sa n d p a t o r ne x p r e s s i o ni nw e bl o gm i n i n gi ss t u d i e st h ew e bh o w s eb e h a v i o ro fu s e r , s o t h a tt ou n d e r s t a n dt h ei n t e r e s tt h a tv i s i t o rb r o w s e t h e ya r ei m p o r t a n tr a t h et oe n h a n c e w e bq u a l i t ya n dt oi m p r o v ew e b s i t ss t r u c t u r ed e s i g n - i nt h i st h e s i s ，t h em e t h o do f p a t c r nm i n i n gw e r ed i s c u s s e d i ts t u d i e s t h ea l g o r i t h m so fa s s o c i a t i o nr u l ea n d s e q u e n t i a lp a t e mm i n i n g i tb r i n gf o r w a r dt h a tt h ef pt r e ea n fp r e f i x s p a na p p l yt o a s s o c i a t i o nr u l ea n ds e q u e n t i a lp a t e r nm i n i n gb a s e so nt h ea l g o r i t h m sc o m p a r e f i n a l l y , t h et e c h n o l o g yo f w e bl o gm i n i 】【l gw a sa p p l i e dt ot i m 日i i lr a i l w a ye n g i n e e r i n g s c h o o lw e bs t a t i o n ( h t t p ：w w w t j t d x y c n ) t h r o u g ht h em i n i n go fi t sw e bs e v g rl o g f i l e s ，ad a t am i n i n gs y s t e mb a s e do nw e bl o gm i n i n gw a se s t a b l i s h t h ee s t a b l i s h e d d a t am i n i n gs y s t e mw i l lf a c i l i t a t es t a t i o nm a n a g e m e n t , t h ei m p r o v e m e n to f t h ed e s i g n o f w e bs t a t i o n k e yw o r d s ：d a t am i n i n gw e bd a t am i n i n g w e bl o gm i n i n ga s s o c i a t i o n r u l e s e q u e n t i a lp a t e r n p a t e r na n a l y s i s i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁鲞盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者躲秘签字吼。年蝴7 日 学位论文版权使用授权书 本学位论文作者完全了解鑫壅盘至有关保留、使用学位论文的规定。 特授权叁鲞盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 躲孚 签字日期：如订年垃月2 7 日 导师签名： 沼龛万 签字日期：订年f 月刁日 第一章前言 1 1 研究背景与意义 第一章前言 2 0 世纪9 0 年代以来，i n t e m e t 得到了飞速的发展，使得w w w 成为了全球 最大、最方便的信息集散地，积聚了海量的信息，成为人们工作与学习的最大支 持平台。据估计，w e b 已经发展成为了拥有3 亿页面的分布式信息空间，而且这 个数字仍以每4 至6 个月翻一番的速度增加。在这些海量的、异构的w e b 信息 资源中，蕴含着具有巨大潜在价值的知识。然而，i n t 矗 n e t 是一个具有开放性、 动态性和异构性的全球分布式网络，资源分布很分散，且没有统一的管理和结构， 这就导致了信息获取的困难，如何从数以亿计的页面中发现需要的内容，如何合 理有效的组织网站的页面链接结构，如何将用户、网页进行合理聚类【1 】，以提 供个性化服务【2 5 】，如何对使用有限资源的用户实现信息的预取【2 7 】，成了 困扰网络用户的一大难题，即所谓的砒c hd a t ap o o ri n f o r m a t i o n 问题，这也是人 们迫切希望解决的问题。人们迫切需要能够从w e b 上快速、有效地发现资源和 知识的工具，提高在w e b 上检索信息的效率。 为了解决上述问题，w e b 挖掘【7 1 3 】应运而生，w e b 挖掘源于数据挖掘【1 】 和i n t e r n e t 技术的结合，并涉及到计算语言学、信息学等多个领域。w e b 挖掘主 要是研究w e b 文档和w e b 活动，从中抽取感兴趣的潜在的有用模式和隐藏的信 息。w e b 挖掘可以在多个方面发挥作用，如确定权威页面、w e b 文档分类、w 曲 页面聚类、客户聚类、w e b 页面预取、智能查询等【1 4 1 9 。 由于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 挖掘技术的思想、方法和策略，研究了规则归纳的挖掘 方法，探讨了关联规则和序列模式的挖掘算法，比较各算法优劣，提出了使用 f p 缸臂和应用于关联规则和序列模式的挖掘。本文提出的方法对于学prefixspan 习和研究基于i n t e r n e t 的数据挖掘技术或者建造一个w e b 使用挖掘系统，具有很 好的参考价值。 1 2 国内外研究应用情况 早在1 9 9 6 年就有国外学者m s c h e n 2 0 1 、h m a n n i l a 2 1 】、t y a h 【4 4 】 提出了可以将数据挖掘方法用于w e b 研究领域使用。 m a n n i l a 和c h e r t 在研究过程中都假定去掉了图形文件、声音文件。以后的 w e b 服务器日志就如实的反映了用户在网站中的访问情况。m a n n i l a 把用户访问 页面当作事件，从网站访问日志中试着寻找用户访问网站的周期。c h e n 提出了 最大前向参引模型，同时也提出用这种方法来分解用户访问的s e s s i o n 成为一个 个的事务( t r a n s a c t i o n ) ，然后就可以在事务的基础上，挖掘用户访问模式。t y a h 研究了如何动态的根据用户当前访问提供推荐页面。他首先对用户进行分类，然 后根据同类用户访问过的页面情况，决定为当前用户提供的页面内容。 1 9 9 7 年d s w n g u 和x w u 等人也研究了s i t e h e l p e r 系统，其主要方法是 使用信息提取的方法提取页面信息，并且结合用户访问历史、用户个人资料提供 的线索，向用户动态推荐访问的页面。但是，由于这个系统主要是根据页面内容 和链接提供信息，对用户行为考虑的相对较少，另外，他要求用户注册，已取得 用户个人信息，这又引起了用户个人隐私问题，因此，这个系统没有投入市场。 1 9 9 7 年p e r k o w i t z 等人在人机界面研究领域，提出了a d a p t i v ew e bs i t e 的概 念，主要研究如何以历史访问为依据，使得w e b 服务器提供的服务页面可以自 动或者半自动的调整。 1 9 9 8 年h a n 把w e b 服务器访问曰志集成到数据立方体结构( d a t ac u b e s t r u c t u r e ) 中，这样就可以对访问日志用传统的在线数据分析处理过程( o l a p ) 来处 理日志数据了。因为其分析主要用的是动态网站日志，因此，他假定客户端的缓 存影响不大。 2 第一章前言 y a h 和h a n 都认为区分用户和用户访问s e s s i o n 是一件比较困难的事情，但 是可惜都没有提出解决的方法。s c h e c h t e r 等人也提出了对用户访问请求进行预 测的想法。根据用户访问的情况提前动态生成用户下一个即将访问的页面内容。 1 9 9 9 年，j b o r g e s 等人提出了引入超链接概率原理，修改了传统意义上对 序列的界定，可以把用户的访问在网站结构中记录下来，根据访问的条件概率判 断用户频繁访问路径。 2 0 0 0 年，台湾学者j u d y 等人提出了t a m 模型，对访问某网站的2 0 0 个学 生，进行问卷调查，以寻找评价网站提供信息质量的要素。 目前，在一些国外专业研究w e b 数据挖掘的网站上面出现了几种比较简单 的用户访问日志分析工具。主要是统计每一个页面访问的频次，以及用户访问页 面的时间分布情况，其中比较成功的w e b t r e n d 软件己经可以统计出所有类型的 错误访问。 互联网的快速发展，对w e b 用户访问日志分析的需求也越来越迫切，许多 国家把这方面的研究作为重点资助科研项目之一。 与国外相比，国内学者开始关注w e b 数据挖掘，起步较晚。1 9 9 9 年，陈宁 综述了国外应用数据挖掘技术解决i n t e m e t 应用问题的做法。1 9 9 9 年，周斌等介 绍了采用e 0 e m 模型，并用5 个用户访问模式做训练数据集，尝试着进行了关 联规则挖掘。 w e b 数据挖掘在国内已经引起了人们的关注，现如今研究这方面的科研人 员也很多，但是都是处于起步阶段。 1 3 本文的内容和安排 本文工作的立足点是通过对数据挖掘的研究，从网络中提取大量的日志文 件，然后分析网络日志文件，从中得到一些有用的信息，进而改进网站的设计， 提出建立一个基于w e b 日志的数据挖掘系统，帮助网站管理人员更好地管理w e b 站点为用户提供更好的服务，提高站点的访问量，从而提高站点的知名度。 本文主要完成了以下几方面的工作：w e b 日志挖掘技术的研究、w e b 日志 挖掘的过程和建立一个w e b 日志挖掘系统。 全文有6 章组成。 第一章介绍基于w e b 日志的数据挖掘研究背景与意义，目前国内外对w e b 日志挖掘的研究及应用情况。 第二章介绍与本文有关的数据挖掘的知识，简要概述了数据挖掘的产生、 定义、分类及数据挖掘过程。 第一章前言 第三章详细介绍了w e b 日志挖掘的整个过程，主要描述日志挖掘中的数据 收集，进行日志挖掘对数据进行预处理的过程。 第四章详细介绍了基于规则归纳的模式挖掘算法。 第五章重点介绍应用在天津铁路工程学校网站上的w e b 日志挖掘系统。 第六章为结束语，对本文工作进行了总结，并提出进一步研究的方向。 4 第二章数据挖掘综述 第二章数据挖掘综述 本章主要介绍数据挖掘的产生、数据挖掘定义、数据挖掘分类、数据挖掘过 程、数据挖掘技术的发展。 2 1 数据挖掘的产生 上个世纪九十年代，随着数据库系统的广泛应用和网络技术的高速发展， 数据库技术发展到了一个全新的阶段，从过去仅管理一些简单数据发展到了必须 管理由各种设备、装置、计算所产生的图形、图像、音视频、电子档案、w e b 网 页等等多种类型的复杂数据，并且数据量也越来越多。这一变化给数据库技术带 来了很多的挑战，需要我们研究许多新的问题。世界各地数以十亿计的计算机上 存储的海量数据里包含着许多重要信息，人们希望能对其进行深入的分析，发现 并提取隐藏在其中的信息，以更好地利用这些数据。数据库系统可以高效地实现 数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根 据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致 了“数据爆炸但知识贫乏t 6 l ”的现象。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果，它使数据 库技术进入了一个更高级的阶段。数据挖掘不仅能对存储在数据库中的过去的数 据进行查询和遍历，并且能够找出过去数据之间的潜在联系，找出新的信息。因 此，数据挖掘是从大型数据库或数据仓库中发现并提取隐藏在其中的信息的一种 新技术，目的是帮助决策者寻找数据间潜在的关联，发现被忽略的要素。数据挖 掘技术从大量数据中提取出可信、新颖、并被人理解的模式，分析数据，挖掘大 量数据背后的知识。 数据挖掘技术促成了“数据库中的知识发现【2 4 】( k d d ：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 ) 。”的产生。1 9 8 9 年美国底特律召开的第1 l 届国际人工 智能联合会议的专题讨论会上【2 2 】k 2 3 】首次出现了k d d 这个术语。随着来 自各个领域的研究人员和应用开发者不断增多，1 9 9 5 年在加拿大蒙特利尔召开 了首届k d d 国际学术年会。数据挖掘技术演变为工程领域的数据挖掘与科研 领域的k d d 。2 0 0 3 年8 月在美国华盛顿召开了第九届k d d 国际年会。现在 对k d d 的研究围绕理论、技术和应用3 个方面展开。理论方面的研究包括： 数据和知识的表示；结构化、文本和多媒体数据的模型构造；不确定性管理；知 第二章数据挖掘综述 识的实用性评测；数据挖掘的算法复杂性和效率分析；海量数据集的统计学等。 技术方面的研究主要包括数据挖掘方法、数据挖掘算法和知识发现过程。数据挖 掘方法包括分类、聚类、预测和评估、相关性分析、搜索和优化等。数据挖掘算 法包括空间数据、文本数据和多媒体数据的数据挖掘算法、并行和分布式数据挖 掘技术等。知识发现过程包括数据预处理技术，如数据去噪、有效样本选取、数 据缩减等，此外还有知识的评估、统一和解释、数据和知识的可视化。应用研究 包括开发各种k d d 系统和工具及其在各个行业中的应用，另外还包括一些有 关数据保密的问题研究。 2 2 数据挖掘定义 从技术上来说，所谓数据挖掘( d a t am i n i n g ，简称：d m ) ，又称数据库的知识 发现( 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 ) 是指从大量的原始数据中挖掘 出隐含的、有用的、尚未发现的知识和信息，对数据进行较高层次的处理，从中 找出内在规律和模式。人们把原始数据看作是形成知识的源泉，就像从矿石中采 矿一样。原始数据可以是结构化的，如关系数据库中的数据，也可以是半结构化 的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的 方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现 了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于 数据自身的维护。 因此，数据挖掘是一门交叉学科，它综合了机器学习 3 5 1 、统计分析【3 3 】 和数据库技术1 3 6 1 ，它把人们对数据的应用从低层次的简单查询，提升到从数 据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者， 尤其是数据库技术、人工智能技术1 3 4 1 、数理统计、可视化技术、并行计算等 方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技 术热点。 从商业角度来说，数据挖掘也是一种新的商业信息处理技术，其主要特点 是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从 中提取辅助商业决策的关键性数据。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已 经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外， 由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限 制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这 些数据不再是为了分析的目的而收集的，而是由于纯机会的商业运作而产生。分 6 第二章数据挖掘综述 析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值 的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大， 而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利 于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得 名。 2 3 数据挖掘的主要过程 数据挖掘可以视为k d d 的同义词，通常知识发现的过程可以有以下步骤组 成k 6 1 ( 参看图2 1 ) 。 图2 1 数据挖掘过程 1 、问题定义 数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息，因此发现何种 知识就成为整个过程中第一个也是最重要的一个阶段。在问题定义过程中，数据 挖掘人员必须和领域专家以及最终用户紧密协作，一方面明确实际工作对数据挖 掘的要求：另一方面通过对各种学习算法的对比进而确定可用的学习算法。后续 的学习算法选择和数据集准备都是在此基础上进行的。 2 、数据收集和数据预处理 数据准备又可分为三个子步骤：数据选取、数据预处理和数据变换。 数据选取的目的是确定发现任务的操作对象，即目标数据，是根据用户的需 要从原始数据库中抽取的一组数据。数据预处理一般可能包括消除噪声、推导计 算缺值数据、消除重复记录、完成数据类型转换( 如把连续值数据转换为离散型 的数据，以便于符号归纳，或是把离散型转换为连续值型的，以便于神经网络) 等。当数据挖掘的对象是数据仓库时，一般来说，数据预处理己经在生成数据仓 库时完成了。数据变换的主要目的是消减数据维数或降维，即从初始特征中找出 7 第二章数据挖掘综述 真正有用的特征以减少数据挖掘时要考虑的特征或变量个数。 3 、数据挖掘 数据挖掘阶段首先根据对问题的定义明确挖掘任务或目的，如分类、聚类、 关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的算 法。选择实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用 与之相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获 取描述型的、容易理解的知识，而有的用户只是希望获取预测准确度尽可能高的 预测型知识，并不在意获取的知识是否易于理解。 4 、结果解释和评估 数据挖掘阶段发现出来的模式，经过评估，可能存在冗余或无关的模式，这 时需要将其剔除：也有可能模式不满足用户要求，这时则需要整个发现过程回退 到前续阶段，如重新选取数据、采用新的数据变换方法、设定新的参数值，甚至 换一种算法等等。另外，k d d 最终是面向人类用户的，因此可能要对发现的模 式进行可视化，或者把结果转换为用户易懂的另一种表示，如把分类决策树转换 为“i t h e n ”规则。 数据挖掘质量的好坏有两个影响要素：一是所采用数据挖掘技术的有效性， 二是用于挖掘数据的质量和数量( 数据量的大小) 。如果选择了错误的数据或不适 当的属性，或对数据进行了不适当的转换，则挖掘的结果是不会好的。 整个挖掘过程是一个不断反馈的过程。比如，用户在挖掘途中发现选择的数 据不太好，或使用的挖掘技术产生不了期望的结果；这时，用户需要重复先前的 过程，甚至从头重新开始。 可视化在数据挖掘的各个阶段都起着非常重要的作用。特别是在数据准备阶 段，用户可能要使用散点图、直方图等统计可视化技术来显示有关数据，以期望 对数据有一个初步的了解，从而为更好地选取数据打下基础。在挖掘阶段，用户 则要使用与领域问题有关的可视化工具。在表示结果阶段，则可能要用到可视化 技术使得发现的知识更易于理解、更易于被用户接受。 2 4 数据挖掘的体系结构及最常用技术 2 4 1 数据挖掘的体系结构 数据挖掘不是人工智能、机器学习、统计等多项技术的简单组合，而是一个 完整的整体，它还需要其它辅助技术的支持，才能完成数据收集、预处理、模式 识别、模式分析等一系列的任务，最后将分析结果呈现在用户面前。 在数据挖掘体系结构中，数据挖掘整个分析过程分为三部分：数据准备、数据 第二章数据挖掘综述 挖掘和数据结果表述和评价。数据挖掘算法是整个数据挖掘的核心部分，它将原 始数据从库中取出来，然后选择相应的数据挖掘算法进行处理，最后输出结果。 数据挖掘系统的体系结构( 参看图2 2 ) 图2 2 数据挖掘系统的体系结构 2 4 2 数据挖掘中最常用的技术 l 、人工神经网络：仿照生理神经网络结构的非线形预测模型，通过学习进 行模式识别。 2 、决策树：代表着决策集的树形结构。 3 、遗传算法：基于进化论，并采用遗传结合、遗传变异以及自然选择等设 计方法的优化技术。 4 、近邻算法：将数据集合中每一个记录进行分类的方法。 5 、规则推导：从统计意义上对数据中的“如果一那么”规则进行寻找和推导。 2 5 数据挖掘技术的向前发展 随着各种应用技术如数据处理工具、数据库技术以及网络技术的迅速发展， 大量的形式各异的复杂类型的数据，如非结构化数据、超文本与多媒体类型的数 据不断涌现。由此，数据挖掘技术也向前不断发展而产生许多新的数据挖掘领域。 9 第二章数据挖掘综述 2 5 1 空间数据库挖掘 空间数据库存储的是与空间有关的数据，包含了拓扑、距离信息，比如地 图，预处理后的遥感和图象数据等，通常按复杂的、多维的空间索引结构组织数 据。空间数据挖掘是指对空间数据库中非显式存在的知识、空间关系或其它有意 义的模式等的提取。空间数据挖掘要综合数据挖掘与空间数据库技术。它可用于 对空间数据的理解，空间关系和空间与非空间数据间关系的发现，空间知识库的 构造，空间数据库的重组和空间查询的优化。空间数据挖掘在地理信息系统、地 理市场( g o a m a r k e t i n g ) 、遥感、图象数据库探测、医学图象处理、导航、交通控 制、环境研究以及许多使用空间数据的领域中有广泛的应用。由于空间数据的大 数据量和空间数据类型和空间访问方法的复杂性，空间数据挖掘面临的主要挑战 是研究高效的空间数据挖掘技术。 2 5 2 多媒体数据库挖掘 多媒体数据库是指存储和管理大量多媒体对象的数据库，如音频数据、图象 数据、视频数据等。由于音频视频设备、c d r o m 和因特网的流行和普及，多 媒体数据库系统变得日益常见。多媒体数据库挖掘主要包括对多媒体数据的相似 性搜索、多媒体数据的多维分析、关联模式发现、多媒体数据的分类和预测分析 等。 2 5 3 时序数据和序列数据的挖掘 时序数据库是指由随时间变化的序列值组成的数据库。值通常是在等时间 间隔测得的数据。许多应用中时间序列数据库很普遍。如股票市场的每日波动， 动态产品加工过程，科学实验等等。时序数据库也是一种序列数据库。 时序数据库和序列数据库的挖掘主要包括趋势分析、时序分析中的相似搜 索、序列模式挖掘、周期分析等。趋势分析主要分析趋势变化、循环性、季节性 变动和非规则变动；时序分析中的相似搜索负责找出与给定查询序列最接近的数 据序列；序列模式挖掘发现相对时间或其它模式出现频率高的模式；周期分析负 责对周期模式进行挖掘，即在时序数据库中找出重复出现的模式。 2 5 4 文本数据库挖掘 在现实世界中，人们可获取的大量信息是由文档组成的，如新闻文章、研究 论文、书籍、数字图书馆和电子消息等等，这些数据基本上是半结构化数据，传 统的信息检索技术不适合这种结构的信息的处理。文本数据库挖掘主要包括：文 1 0 第二章数据挖掘综述 本数据分析和信息检索、基于关键字的关联和文档分类等等。 2 5 5w e b 数据挖掘 w e b 数据挖掘将传统的数据挖掘技术和w e b 结合起来，进行w e b 知识的 提取，从w e b 文档和w e b 活动中抽取感兴趣的潜在的有用模式和隐藏的信息。 w e b 挖掘可以在很多方面发挥作用，如对搜索引擎的结构进行挖掘、确定权威 页面、w 曲文档分类、w e b 日志挖掘、智能查询等。 2 6w e b 数据挖掘技术 w e b 挖掘是一项综合技术，涉及w e b 技术、数据挖掘、计算机语言学、 信息学等多个领域。不同研究者从自身的领域出发，对w e b 挖掘的含义有着不 同的理解，项目开发也各有其侧重点。例如，有些计算机语言学家认为，w 曲文 档为自然语言的理解提供了丰富的资料，可以从中自动地学习词语的意义，以进 行词义辨析或确定词语所属的概念。我们从更为一般的角度出发，对w e b 挖掘 作如下定义。 w e b 挖掘是指从大量w e b 文档的集合c 中发现隐含的模式p 。如果将c 看作输入，将p 看作输出，那么w e b 挖掘的过程就是从输入到输出的一个映 射；：c p 。 w e b 挖掘从数据挖掘发展而来，因此其定义与我们熟知的数据挖掘定义相类 似。但是，w e b 挖掘与传统的数据挖掘相比有许多独特之处。首光，w e b 挖掘 的对象是大量、异质、分布的w e b 文档。其次，w e b 在逻辑上是一个由文档节 点和超链接构成的图，因此w e b 挖掘所得到的模式可能是关于w 曲内容的， 也可能是关于w e b 结构的。此外，由于w e b 文档本身是半结构化或无结构的， 且缺乏机器可理解的语义。而传统数据挖掘的对象局限于数据库中的结构化数 据，并利用关系表格等存储结构来发现知识，因此有些数据挖掘技术并不适用于 w e b 挖掘，即使可用也需要建立在对w e b 文档进行预处理的基础之上。 w e b 挖掘当前研究的主要有三种技术：w e b 内容挖掘( w e bc o n t e n t m i n i n g ) ，w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) ，w e b 使用挖掘( w e bu s a g em i n i n g ) 。 3 7 ，3 8 ，3 9 1 其分类的结构( 参看图2 3 ) ： 第二章数据挖掘综述 2 6 1w e b 内容挖掘 图2 3w e b 挖掘分类 w e b 内容挖掘是从w e b 文档内容或其描述中抽取知识的过程 3 7 1 ，不同于 传统的数据挖掘技术，w e b 挖掘主要是针对各种非结构化的数据，如文本数据、 音频数据、视频数据、图形图像数据等多种数据相融合的多媒体数据挖掘【4 0 】。 又可将其分为基于文本的挖掘和基于多媒体的挖掘两种。 2 6 2w e b 结构挖掘 w e b 结构挖掘是从w w w 的组织结构和链接关系中推导知识的过程 3 7 1 。 它试图发现w e b 链接结构中潜在的模型，而这种模型是建立在超链拓扑基础上 的。同时，挖掘出的模型能够被用于w e b 页面分类，并且有助于生成一些有用 的信息( 例如w e b 站点之间的相似性和关系信息) 。值得一提的是，w e b 结构挖掘 能够用于发现某个主题的权威网站和关于此主题的所有网站的概貌。这方面工作 的代表有p a g e r a n k 4 1 】，m t s 4 2 】和c l e v e r 4 3 】。 p a g e r a n k 技术不仅提高了搜索引擎的有效性而且改善了它们的效率。 p a g e r a n k 被用于衡量某个页面的重要性，并且根据传统搜索引擎搜索返回的页 面的重要性来进行排序。这种方法有效性的一个最好例证就是g o o g l e 的成功。 一个页面的p a g e r a n k 值是根据此页面的导入链接( b a e k l i n k ) 数目计算得来的。导 入链接是指指向此页面的链接，而不是由此页面发出的链接。p a g e r a n k 方法并 不是简单的计算导入链接的数目，而是根据来自不同重要性页面的导入链接赋予 不同的权值( w e i g h t i n g ) ，即来自越重要页面的导入链接的权值越大。p a g e r a n k 的基本思想是：一个页面被多次引用，则这个页面很可能是重要的；一个页面尽管 没有被多次引用，但是被一个重要页面引用，则这个页面也可能是重要的：一个 第二章数据挖掘综述 页面的重要性被均分并被传递到它所引用的页面。例如：给定某个页面聃p 表示 页面p 的导入链接集合，f p 表示页面p 发出的链接集合，则页面p 的p a g e r a n k 傩( p h 罗丝泣 可定义为： ”。 这里n q = l f q l 。常数c ( o 雯1 1 ) 用于标准化。一个页面的p a g e r a n k 被分配到 所有它指向的页面中，每个页面求和所有指向它的导入链接所带来的p a g e r a n k 以得到它的新的p a g e r a n k 。该公式是一个递归公式，在计算时可以从任何一个 页面开始反复计算，直到其收敛。 对于搜索引擎的搜索结果来说，p a g e r a n k 是一个很好的评价结果的方法， 查询的结果可以按照p a g e r a n k 从大到小依次排列输出。c l e v e r 方法本质上和 p a g e r a n k 是一致的。 2 6 3w e b 使用挖掘 w e b 使用挖掘主要是对用户访问w 曲时在服务器上留下的访问记录进行的 挖掘，即对用户访问w e b 站点的存取方式进行挖掘，以发现用户访问站点的浏 览模式、页面的访问频率等信息。这种数据挖掘是一种很重要的信息获取方式， 它挖掘的数据般是在用户和网络交互的过程中抽取出来的第二手的数据。这些 数据包括：w e b 服务器日志记录、代理服务器的日志记录、客户端的日志记录、 用户简介、注册信息等等。 w e b 使用挖掘主要有两个研究发展方向：一般化的访问模式追踪( g e n e r a l a c c e s sp a t t e r nt r a c k i n g ) 2 7 ，2 8 ，2 9 和个性化的使用记录追踪( c u s t o m i z e du s a g e t r a c k i n g ) 【3 0 。 一般化的访问模式追踪是从w 曲日志中挖掘用户的访问模式和预测用户的 访问趋势。这些挖掘出来的模式和规则对w e b 站点的改进包括 3 1 】： 使用户所关心的页面更加容易访问； 使用户所关心的超链接更加醒目； 链接相关的页面； 聚合相似的页面； 增加缓冲预取机制、改善服务器响应时间： 合理设置广告： 个性化的使用记录追踪是挖掘某一类或某几类用户( 甚至某个用户) 访问网 站的行为规律，这使得网站能够动态地为用户提供个性化的服务以极大地满足用 户的需求。所谓的个性化服务是指w e b 站点为适应某一类或某一个特定用户的 需要而实时地调整数据的组织和显示。一种实现个性化服务的方法是允许用户手 第二章数据挖掘综述 工定制w e b 站点显示选项，系统将记住每个用户的定制，并在该用户再次进入 该网站时进行相应的调整。例如微软的m s n 站点o a t t p ：w w w m s n c o m ) 允许用户 只看到用户自己选择的新闻栏目。 1 4 第三章w e b 日志挖掘的预处理阶段 第三章w e b 日志挖掘的预处理阶段 本章介绍了w e b 日志挖掘的整个过程，主要描述日志挖掘中的数据收集，进 行日志挖掘对数据进行预处理的几种情况。 3 1 前言 w e b 日志挖掘是通过分析w 曲服务器的臼志文件，以发现用户访问站点的 浏览模式，为站点管理员提供各种利于站点改进或可以带来经济效益的信息( 如： 聚类分析可以把具有相似特征的用户或数据项归类来帮助进行市场决策) 。w e b 服务器日志也可以结合其它数据库( 如：电子商务、银行数据库) 一同进行挖掘，以 获得更详细的信息。w e b 日志挖掘能带来许多方面的好处：分析网站流量模式； 发现系统性能瓶颈；测定广告和促销计划的成功度及测定投资回报率；发现用户 的需要和兴趣等。 3 1 1 日志介绍 所谓w e b 日志，是指在服务器上有关w e b 访问的各种日志文件，它记录着 用户访问该站点时每个页面的请求信息，包括访问日志、引用日志、代理日志、 错误日志等文件。这些文件里包含了大量的用户访问信息，如用户的p 地址、 所访问的u r l 、访问日期和时间、访问方法( g e t 或p o s t ) 、访问结果( 成功、 失败、错误) 、访问的信息大小等。 日志记录的格式主要分为两种：通用日志格式( c o m m o nl o g f 0 锄a t c f l ) 和扩展型日志格式( e x t e n d e d l o g f o r m a t ) 。其主要结构如表3 1 所示。 表3 1 中阴影部分是扩展型日志格式中添加的记录项，带的数据域是我们 进行挖掘时所保留的内容，仅供参考。 典型的日志记录形式如下： 2 1 2 1 1 3 9 2 4 2 - 2 9 j u l 2 0 0 2 ：0 0 ：3 5 ：3 3 - 0 5 0 0 】f i g e t s u r v e y h i s t o r y h t m h t t p 1 1 ”2 0 01 1 6 3 1 ”h t t p ：w w w t j u e d u c n ”m o z i l l a 4 0 ( c o m p a t i b l e ；m s i e 5 5 ；w i n d o w sn t5 o r 由于服务器并不记录用户的浏览行为，所以如果用户的请求是通过本地( 如 在浏览器中按“后退键”) 或p r o x y 端的缓冲区得到满足，则服务器端并不 第三章w e b 日志挖掘的预处理阶段 记录此次请求，因此日志文件中的记录并不能完全地反映用户的访问行为。 表3 - 1w e b 日志记录的主要信息 域描述 日期( d a t e )用户请求页面的日期