（计算机应用技术专业论文）基于模糊聚类的web日志挖掘研究.pdf

基于模糊聚类的w e b 日志挖掘研究 摘要 w e b 数据挖掘包括w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖掘。w e b 使用挖 掘主要是针对w e b 日志数据进行分析处理。通过对用户访问日志进行聚类分析，可 以获得主要的感兴趣的访问模式。由于w e b 日志数据通常是大量和冗余的，日志中 的页面之间关系是模糊和不确定的，为此，本文基于模糊聚类方法进行w e b 日志的 分析研究，主要工作如下： ( 1 ) 概述了w e b 挖掘以及w e b 日志挖掘的相关领域的发展和技术及其理论基础。 ( 2 ) 在详细研究w e b 日志挖掘的预处理技术的基础上，提出一个基于页面访问时 间阈值与会话重组的会话识别算法，并通过实际的w e b 日志数据加以验证。 ( 3 ) 针对w e b 用户聚类及w e b 页面聚类，通过w e b 日志中的数据，根据用户对 w e b 页面的浏览情况分别建立w e b 用户和w e b 页面的模糊集，在此基础上用最大- 最小法的模糊相似性度量构造模糊相似矩阵，并由此构造模糊动态聚类算法d d f c a 。 与传递闭包法和最大树法相比，该算法在时间性能上有所改进。 ( 4 ) 在上述工作的基础上，同时结合各种关键技术，设计了一个w e b 日志挖掘的 原型系统。 关键词：数据挖掘，w e b 日志挖掘，模糊聚类，w e b 数据预处理 1 v t h er e s e a r c ho fw e b l o gm i n i n gb a s e d o nf u z z y c l u s t e r i n g a b s t r a c t t h ew r e bd a t am i n gc o n s i s t so fw r e bc o n t e n tm i i l i n g ，w 曲s t r u c t u r em i n i n ga n d w e bu s a g em i n i n g 。刀留缪动l o gd a t ah a v e b e e na n a l y z e da n dp r o c e s s e di nt h ew e b u s a g em i n i n g t h r o u g hc l u s t e r i n ga n da n a l y z i n go nu s e ra c c e s sl o g s ，i n t e r e s t i n g m a j o ra c c e s sp a t t e r n sc a nb eo b t a i n e d 。t h e 砌l o gd a t ai sg e n e r a l l yr e d u n d a n ta n d t h er e l a t i o n s h i pa m o n gt h ew e bp a g e si sf u z z ya n du n c e r t a i n ，s ot h er e s e a r c ho nw e b l o gm i n i n gw i t hf u z z yc l u s t e r i n ga n a l y s i si sc o n d u c t e d a sf o l l o w s ： 1 t h ed i s s e r t a t i o ns u m m a r i z e st l l ed e v e l o p m e n ta n dt e c h n o l o g yo fw r e bd a t a m i n i n ga n dw r e bu s a g em i n i n go ft h er e l e v a n tf i e l d s ，嬲w e l l 雒t h et h e o r e t i c a lb a s i s f o r t h a t 2 o nt h eb a s eo ft h er e s e a r c ho fw 曲l o gd a t ap r e p r o c e s s i n g ，a l g o r i t h m sb a s e d o np a g e sa c c e s st i m et h r e s h o l da n ds e s s i o n sr e c o n s t r u c t i o na r ep r e s e n t e da n dh a sb e e n p r o v e d t h r o u g ha c t u a lw e bl o g d a t a 3 t h ef u z z yc l u s t e r i n ga l g o r i t h m sf o rw e bu s e r sa n dw e bp a g e sh a v eb e e n p r e s e n t e d t h ef u z z ys e t so fw e bu s e ra n dw e bp a g ea r es e tu ps e p a r a t e l ya c c o r d i n g t o t h er e c o r d si n 乃匆6l o g s ；t h ef u z z ys i m i l a r i t ym a t r i c e sa r ec o n s t r u c t e do nt h eb a s i so f t h ef u z z ys e t sa n dt h em a x - m i ni ns i m i l a r i t ym e a s u r es c h e m e s ow 曲u s e rc l u s t e r s a n dw e b p a g ec l u s t e r sa l ea b s t r a c t e df r o mt h ec o r r e s p o n d i n gf u z z ys i m i l a r i t ym a t r i x b a s e do nt h ea l g o r i t h m s c o m p a r e dt ot h et r a n s f e rb a ga l g o r i t h ma n dt h em a x i m u m t r e ea l g o r i t h m ，t h ea l g o r i t h mh a si m p r o v e da st ot h et i m ep r o p e r t y 4 i n t e g r a t i n gt h ek e yt e c h n o l o g i e sc o n c e r n e d ，aw e bu s a g em i n i n gs y s t e m p r o t o t y p eh a sb e e nd e s i g n e da n da d v a n c e db a s e do nt h er e a l i z a t i o n so ft h ea b o v e w o r k k e yw o r d s ：d a t am i n i n g , w e bl o gm i n i n g , f u z z yc l u s t e r i n g , w e b d a t a v 插图清单 图2 1 知识发现过程图6 图2 2w e b 挖掘的分类7 图3 1 多窗口页面示意图1 7 图4 - 1w e b 用户动态聚类图3 4 图4 _ 2w e b 页面动态聚类图3 5 图5 1w e b 日志挖掘流程图3 7 图5 2w l g m s 系统结构3 8 图5 3 清洗前的原始数据4 0 i x 表格清单 表3 1 典型的日志记录形式1 5 表3 2 各种用户识别方法1 8 表3 3 各种会话识别方法的比较结果2 4 表4 1 源数据表3 3 表5 1 访问日志、引用日志和代理日志的内容4 0 表5 - 2 合并后的日志中的一条记录4 0 x 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得合肥工业大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名：才力蘑 签字日期：刃艿年多月乡日 学位论文版权使用授权书 本学位论文作者完全了解合肥工业大学有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权合肥工业大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：2 卵孑 学位论文作者毕业后去向： 工作单位： 通讯地址： m 导师签名： 签字日期： 啊矾。 嚼年莎月7 日 日 藤弓 无钿历年 形丌， 1；7 、州 彳 话编电邮 致谢 论文的顺利完成，首先要感谢我的导师胡学钢教授。感谢胡老师在我的论 文写作中给予的指导、关心和帮助。胡老师不仅给予我研究方向的指导，还指 点了我有关研究的重要思想方法。导师科学严谨的态度、深厚扎实的理论知识、 忘我敬业的工作精神、脚踏实地的工作作风、平易近人的待人处事方式，这一 切都深深地影响了我，成为我毕生学习的榜样。我所取得的每一点进步，都与 导师的鼓励和指导密不可分。 同时对百忙中抽出宝贵时间对本文进行评阅的专家和学者表示诚挚的谢 意! 感谢研究生院和计算机信息学院的领导和老师给予我的极大的帮助和教 诲! 感谢在课题研究过程中所有列出和未列出的被引用文献的作者! 感谢池州学院的计算机网络中心的领导及全体同事，在我做论文期间，是 他们给予我大力的支持和帮助。特别是在数据收集和程序调试方面，耽误了他 们很多宝贵的时间。 感谢我的家人，特别是我的爱人鲍盛英和我的女儿方佳艳，一直以来她们 都在默默地关心和支持着我，给予我精神上无限的力量! v i 作者：方元康 2 0 0 8 年4 月 1 1 背景 1 1 1 数据挖掘的定义和范畴 第一章绪论 尽管目前无明确的精确学科划定，从广义上来讲，数据挖掘( d a t am i n i n g ) 就是先从巨大的数据体系或数据库里提炼出人们感兴趣的东西( 可能在意料之 中，也可能在意料之外) ，或者说，从庞大的观察数据集中提炼并分析出不可 轻易察觉或断言的关系，最后给出一个有用并可以理解的结论。简单地说，数 据挖掘就是在数据中发现模式，或者说一种知识，也可以说数据间的关系 i - 3 1 。 数据挖掘也常称为知识发现( k n o w l e d g ed i s c o v e r y ) t 4 1 ，这就无怪乎许多知识发 现中的算法，比如人工智能，常被用于数据挖掘的过程中。尽管“数据挖掘” 和“知识发现 的叫法在学术界并行，然而在产业界、媒体和数据库研究界， “数据挖掘 这一术语比“知识发现 更流行，因为后者更能够吸引投资家的 视线，推动数据挖掘的使用和发展。 数据挖掘有以下几个特点。第一个特点就是它的数据量常常是巨大的。因 此如何有效率地存取数据，根据一定应用领域找出数据关系即高效率算法，以 及是使用全部数据还是使用一部分随机或有目的地选择出的数据子集，都成为 数据挖掘工作者要考虑的问题。其次，数据挖掘常常面临的数据是为其它目的 而收集好的数据( 比如说，银行已存有巨大的每日交易数据，这些数据原本是 为其它目的而存储的) 。这常常为数据挖掘提出了一个问题，即收集数据时， 可能没有收集一个或几个重要的变量，而这些变量在后来做数据挖掘时被证明 是有用的，甚至是至关重要的。数据挖掘的另一个特点是数据挖掘工作者常常 不愿把先验知识预先嵌入算法内，因为这样就等于做“假设检验”。数据挖掘 常常要求算法主动性地提示一些数据内在的关系。新颖性是衡量一个数据挖掘 算法好坏的一个很重要标准。当然，这些新颖性的结论必须是可以被人理解的， 绝对不应该是漫无边际的奇怪结论。 1 1 2w e b 挖掘产生的背景 随着计算机网路和通信技术的飞速发展，作为全球最大的信息服务平台的 互联网i n t e r n e t 正在以前所未有的速度渗入到人类的生产和生活的各个方面。 据i d g ( i n t e r n a t i o n a ld a t ag r o u p ) 近期公布的一项报告称，1 9 9 8 年全球使用 i n t e r n e t 的人数已达到3 2 亿左右，到2 0 0 5 年会增加到1 0 亿。i n t e m e t 的普及 同时推动了w w w 即w o r l dw i d ew e b 的迅猛发展，据统计几乎每2 个小时就 有一个新的w w w 服务器产生，1 9 9 8 年已经大约有3 2 0 ，0 0 0 ，0 0 0 个w e b 文档。 w w w 作为信息发布和交流的全球性媒体，它的内容涵盖了包括政治、金融、 军事、科研、教育、商业等各个领域。正是由于w e b 上包含巨大的信息量使得 越来越多的用户感觉到在w w w 上寻找自己想要的信息犹如“大海捞针一样 困难。据说9 9 的w e b 信息相对用户来说都是无用的。用户关心的其实只是 w e b 信息中极少的一部分，而且大量的无关信息会干扰甚至淹没用户感兴趣的 内容，所以如何快速、准确且高效地从浩瀚的w e b 信息资源中搜寻和发现用户 感兴趣的信息和知识已经成为一个迫切需要解决的问题。而将传统的数据挖掘 技术与w e b 有机地结合在一起，进行w e b 挖掘是解决这些问题的一个有效的 途径 5 】【6 】。 因此将数据挖掘和w w w 这两个领域结合起来，就形成了当前的一个热门 研究课题一w e b 挖掘 7 1 。w e b 挖掘可以从海量的数据中自动地、智能地抽取隐 藏在这些数据中的知识。在1 9 9 6 年o e t z i o n i 最早提出w e b 挖掘这个概念。他 认为w e b 网页是有结构的并且是可以挖掘的【8 】。这个观点一经提出，得到不同 学科的许多学者的积极支持。到现在，w e b 挖掘已经得到迅速发展和广泛应用。 w e b 上信息的多样性决定了w e b 挖掘任务的多样性，根据挖掘对象的不 同，可以将w e b 挖掘分为w e b 内容挖掘( w e bc o n t e n tm 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 ) - - - 大类p 儿1 0 j 。其中 的w e b 使用挖掘是挖掘w e b 服务器日志获取的信息来预测用户浏览行为的技 术，指从用户的访问日志中挖掘用户的访问模式，为网站经营管理和结构调整 提供决策支持，为企业发现新市场机会，进行市场决策，提高通过网站施行的 营销效果，以及为企业进行战略决策提供有价值的潜在的信息。 1 2 本文的研究意义 国际互联网加快了信息传播的速度，相关的网络应用都以惊人的速度增 长，例如：电子商务、电子化客户关系管理( e c r m ，e l e c t r o n i c - c u s t o m e r r e l a t i o n s h i pm a n a g e m e n t ) 、远程教育( d i s t a n c el e a r n i n g ) 等。然而，网络上信息 超载( i n f o r m a t i o no v e r l o a d ) 问题的日益严重，却也一直困扰着网站浏览者与经 营者，所以了解网站浏览者的真正信息需求，为用户提供个性化的服务，避免 不必要的信息传输，已成为目前网站经营者相当重视的问题。 近年来，数据挖掘( d a t am i n i n g ) 和国际互联网( w o r l dw i d ew e b ) 应用研究 是信息时代两大活跃的研究领域，两者的结合构成了另外一大活跃的研究领域 一w e b 数据挖掘研究。 w e b 挖掘( w e bm i n i n g ) ，从广义上解释就是通过数据挖掘技术来分析与网 站相关的资料，例如：网站浏览记录( w e bl o g ) 、网页内容( w e bc o n t e n t ) 、网络 链接结构( w e bs t r u c t u r e ) 等。随着w e b 技术的发展，各种网站数量每天都在急 剧增加，特别是将w e b 转化为关键发展工具的信息网站( 电子商务网站) ，采用 2 各种手段使网站更加具有生命力成为每个经营者的首要工作。例如当前各类电 子商务网站风起云涌，建立一个电子商务并不难，困难的是如何使建立的电子 商务网站有收益。电子商务的竞争比传统的业务竞争更加激烈，原因有多方面， 其中一个因素是客户从一个电子商务网站转到另一个网站只需点击几下鼠标 就可以了。所以，及时了解用户的需求和特点，为每个用户提供个性化、智能 化的服务，以吸引大量的用户，就变得尤为重要。其中网站浏览记录，记录了 使用者每次访问网站的一些资料，因此最能反映使用者对网站的浏览需求。因 此以数据挖掘技术来分析网站浏览记录，已成为解决上述问题的主要工具之 一。 同传统的数据挖掘一样，w e b 挖掘主要包括聚类、关联和序列分析。然而 w e b 日志中存在着很多的噪音数据和信息的不完整性，这导致聚集只是一个模 糊的边界，聚集中的对象成员没有一个精确的定义。这样对象成员就有可能不 只属于一个聚类。为解决这一问题，我们采用一种在各个领域已广泛应用的技 术一模糊理论，它主要是一种研究模糊性现象、不精确性现象的数学工具。将 模糊集理论中的模糊聚类应用于w e b 挖掘，分析用户访问w e b 的模式，设计 出满足不同客户群体需要的个性化网站，进而增加企业的竞争力。 目前在w e b 挖掘的研究中，在运用挖掘技术分析时，大多都没有仔细考虑 到网站浏览记录的资料特征与偏离网页( o u t l i e r ) ( 用户访问目的网页所必须经 过的中间链接，大多是用户不感兴趣的网页) 的影响，因此容易造成整个分析 结果的不完整，甚至可能分析出错误的模式( p a t t e r n s ) 。同时，使用者浏览路径 中有可能包含了多种信息需求。例如某一使用者对于“书籍与“软件 或“硬 件”的信息都很有兴趣，因而浏览了网站上有关这三方面的网页，因此在其浏 览路径中就会隐含了三种信息需求。然而，在大多数的w e b 挖掘研究中，利用 传统硬聚类技术来分析使用者较偏好浏览的网页时，只能将使用者浏览路径归 类到某个较偏好的网页群组中，而忽略了浏览路径中，使用者对其它网页的偏 好。因此，就成为不合理的分析。 目前，国内外对计算机柔性技术的研究成为热点。所谓柔性技术，它包含 粗糙集理论、模糊理论、神经网络、遗传算法等。特别是模糊理论，在解决模 糊性问题时体现出较大作用，针对w e b 用户兴趣的模糊性、非单一性，引入模 糊聚类对其浏览路径进行模糊聚类，可以较好地解决此类问题，在很大程度上 避免了传统聚类的非此即彼的硬性划分，更客观地体现真实的人类活动。因此， 将模糊聚类应用于w e b 挖掘，分析用户访问w 曲的模式，设计出满足不同客 户群体需要的智能化网站，进而增加企业的竞争力。 1 3 国内外研究现状 目前，国内外有关w e b 用户模式挖掘的研究已经很多，主要集中在对用户 3 浏览路径进行挖掘1 1 , 1 2 , 1 3 , 1 4 】，到今天已经可以看到很多有价值的研究和应用成 果。 文献 1 1 】中提出了一个基于代理的s y s k i l l & w e b e r t 软件，该软件通过分析 用户访问日志预测哪些页面是用户感兴趣的页面。 文献 1 5 】介绍的w e ba c e 系统采用了分类算法来划分用户的上网访问的 历史记录信息，划分出的每一个分类代表用户在这方面的一个兴趣。 文献【1 6 研究了一种文档聚类算法，利用该算法可以改善网站的设计。但 该文没有考虑个性化推荐的问题。 文献 1 7 】设计了一个w e b 挖掘算法，利用模糊集理论挖掘用户浏览模式。 文献【1 8 】所介绍的系统是一个主动推送网页的系统。它每天提供一些可能 会让用户感兴趣的网页，用户根据自己的兴趣来评价这些网页，系统则根据这 个评价信息自我调整，从而改善推送系统性能。该方法需要用户参与评价。 1 4 论文的组织 全文共分为6 章： 第1 章：阐述问题的提出与研究背景。 第2 章：对w e b 数据挖掘进行综述。包括w e b 数据挖掘的定义、分类、 特点及应用前景。 第3 章：对w e b 日志挖掘的数据预处理进行详细研究，并提出了基于页 面访问时间阈值与会话重组相结合的会话识别算法p a t s r 。 第4 章：分析w e b 日志挖掘研究的理论基础聚类技术，针对w e b 用户聚 类和w e b 页面聚类，提出了动态直接聚类算法d d f c a ，同传递闭包法和最大树 法相比，该算法节省了计算量。 第5 章：将模糊聚类算法及相关技术形成一个整体，在上述工作的基础上 设计了一个w e b 日志挖掘原型系统。 第6 章：对全文进行研究总结及展望，并指出今后的研究方向和需要做的 工作。 4 第二章w e b 挖掘综述 近年来，随着i n t e r n e t 在全球范围的迅速普及和应用，网络日益成为人们 生活、工作的重要组成部分。据估计，网络已经发展成为拥有3 亿页面的分布 式信息空间，而且这些信息仍以每4 到6 个月增长一倍的速度增加。在这些大 量、不同的各类信息数据中，蕴含着巨大潜在价值的信息，如何快速、有效地 发现这些信息资源已成为急待解决的问题。 2 1 数据挖掘和知识发现 数据挖掘( d a t am i n i n g ) 就是为了发现事先未知的规则和联系而对大量数据 进行选择、探索和建模的过程，目的在于得到对数据库的拥有者来说清晰而有 用的结果2 3 】 2 4 1 。也就是从大量的，不完全的、有噪声的、模糊的、随机的实 际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程。这里所说的知识发现，不是要求发现放之四海而皆准的真理， 也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证 明。实际上，所有发现的知识都是相对的，是有特定前提和约束条件的，面向 特定领域，同时还要能够易于被用户理解的。最好能用自然语言表达所发现的 结果【25 1 。 因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进 行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型 化的先进有效的方法。通过数据挖掘，有价值的知识、规则或高层次的信息被 抽取出来，作为丰富可靠的资源更有效地服务于知识归纳，所产生的规则蕴含 数据对象间的特定关系，揭示有用信息，为经营决策、市场策划、金融预测等 提供依据。 所谓知识发现就是k d d ( 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 s ) ，这一术语首 先出现于1 9 8 9 年在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨 论会上。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了 8 次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现 方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间 的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一。 k d d 已经成为当前计算机科学界研究的一大热剧2 6 j 。 目前大家公认的k d d 的严格定义是在1 9 9 6 年知识发现国际会议上由 f a y y a d 、p i a t e s t s k y 、s h a p i r o 和s m y t h 提出的： 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 si s t h en o n t r i v i a lp r o c e s so fi d e n t i f y i n g v a l i d n o v e l ，p o t e n t i a l l yu s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a k d d 是从数据集中提取出有效的、新颖的、有潜在作用的、可信的，并 能最终可被理解的模式的非平凡过程【z 川。 从数据挖掘和k d d 的定义中可以看出二者之间具有紧密的联系。其中的 概念都是相互对应或隐含的，对于二者之间的关系，有两种观点：一种观点认 为数据挖掘和k d d 的含义相同，只是名称不同；而另一种观点认为，数据挖 掘是k d d 中专门发现知识的核心环节，而k d d 是一个交互式、循环反复的整 体过程，除了包括数据挖掘外还包括数据准备和发现结构、解释评估等诸多环 节，以及围绕数据挖掘进行的预处理和结果表达式等一系列的计算步骤。尽管 数据挖掘是整个过程的中心，但它通常只占整个过程的1 5 2 5 的工作量。数 据挖掘着眼于设计高效的算法，以达到在巨量数据库中发现知识的目的。作为 一个科学研究领域，数据挖掘和k d d 的确有一定的重合度。但是数据挖掘也 是一个多学科交叉的研究领域，它包括数据库技术、人工智能、机器学习、神 经网络、概率统计学、模式识别、模糊逻辑、分形几何理论、知识工程、信息 检索、高性能计算和数据可视化等研究领域。 图2 1 知识发现过程图 图2 1 描绘了知识发现的全过程，从中可以明显看出数据挖掘与k d d 的 区别和关系。从知识发现的整个过程看，数据挖掘仅仅是整个过程中的一个步 骤。数据挖掘质量的好坏受到两个要素的影响：一是所采用的数据挖掘技术的 有效性，二是用于挖掘的数据的质量和数量( 数据量的大小) ，如果选择了错误 的数据或不适当的属性，或对数据进行了不适当的转换，或选择了不恰当的挖 掘算法，则挖掘的结果是不会理想的。整个挖掘过程是一个不断反馈的过程。 用户在挖掘途中发现选择的数据不太好，或是使用的挖掘技术不能达到预期的 效果，则可能需要换一种方式重复先前的工作。 2 2w e b 挖掘的定义 应用领域的需求是推动技术发展的源动力。i n t e r n e t 的迅速发展使得w w w 上的信息量飞速增长，怎样对这些数据进行复杂的应用成了现今数据库技术的 研究热点。因此对强大有力的w e b 数据分析处理工具提出了要求，而日趋成熟 6 的数据挖掘技术正好为w e b 挖掘提供了技术基础。w e b 挖掘是将数据挖掘技 术应用于大规模w e b 数据，以期发现有效的、新颖的、潜在有用的，以及最终 可理解的模式和规则的过程。相对于w e b 上的数据而言，传统的数据库中的数 据，其结构性很强，即其中的数据为完全结构化的数据，而w e b 上的数据最大 特点就是半结构化。所谓半结构化是相对于完全结构化的传统数据库的数据而 言。显然，面向w e b 的数据挖掘比面向单个数据仓库的数据挖掘要复杂得多。 w e b 挖掘的定义是从数据挖掘的概念扩展而来。简单地说，w e b 挖掘是指 从w e b 服务器上的数据文件中提取人们感兴趣的知识的过程。这里所谓的“兴 趣 与我们前面讲数据挖掘时提到的含义相同。w e b 挖掘其实就是对文档的内 容、可利用资源的使用以及资源之间的关系进行分析，以实现对w e b 存取模式、 w e b 结构和规则的分析，以及动态w e b 内容的查找。 w e b 挖掘能给我们带来什么呢? 让我们先看一个例子，如果在y a h o o ! 上查 找“d a t am i n i n g ，在显示的结果中会出现有关采矿公司的链接。所以在网上 寻找过资料的人大多会抱怨搜索引擎的查询结果。然而w e b 挖掘技术发展成熟 后，此种情况就会消失。w e b 挖掘可以将w e b 上的文档进行分类、寻找文档 主题、汇总搜索结果，使用户在i n t e r n e t 上查找信息更加全面准确。对w e b 站 点分析的结果可用于重新组织w e b 站点结构，以便更好地为用户提供服务。冗 长的遍历路径或是包含重要的信息但访问率很低的页面，都说明站点设计不合 理。借助用户对浏览站点情况的分析，可以对分布式或并行w e b 服务器页面布 局和高速缓存机制进行改进；也可以为用户提供最受欢迎的站点列表，帮助用 户导航。用于数据库知识发现的特征化( c h a r a c t e r i z a t i o n ) 、分类( c l a s s i f i c a t i o n ) 、 预测( p r e d i c t i o n ) 、聚类( c l u s t e r i n g ) 、关联( a s s o c i a t i o n ) 分析和序列模式( s e q u e n t i a l p a t t e r n ) 分析等技术都可以用于w e b 上的知识发现。 2 3w e b 挖掘研究分类 按照研究的w e b 数据对象，w e b 挖掘可以分为三类：w e b 内容挖掘( w e b c o n t e n tm 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 b u s a g em i n i n g ) 2 8 ，2 9 ，3 0 1 ，如图2 2 所示的w e b 挖掘的分类。 w 曲挖掘 w e b 内容挖掘iiw e b 结构挖掘il w 曲使用挖掘 w e b 文本 挖掘 多媒体 挖掘 一般的访问 模式追踪 图2 - 2w e b 挖掘的分类 7 个性化的使 用记录追踪 在实际应用中，w e b 挖掘的三种任务不是孤立的，而是相辅相成的。尤其 是w e b 内容挖掘和结构挖掘之间关系更为紧密，因为w e b 文档中也包含链接。 有的时候，w e b 内容挖掘和使用挖掘相结合能够更好的完成某个应用任务。例 如：在 3 1 中，j o a c h i m s 等人将w e b 内容和使用纪录相结合建立了一个软件浏 览智能体。这个智能体能够帮助用户更好的浏览网站。总之，w e b 挖掘的这三 个研究方向在实际应用过程中并不是孤立的，而是相互交叉、相互渗透和相互 联系的。 2 3 1w e b 内容挖掘 w e b 内容挖掘是一种基于网页内容的w e b 挖掘，是从大量的w e b 数据中 发现信息、抽取有用知识的过程。这些数据对象既有文本和超文本数据，也有 图形、图像、语音等多媒体数据；既有来自于数据库的结构化数据，也有用 h t m l 标记的半结构化数据和无结构的自由文本。就其方法而言，w e b 内容挖 掘可以分为两大类：信息查询( i n f o r m a t i o nr e t r i e v e ，i r ) 方法和数据库方法。就 其挖掘策略的不同，w e b 内容挖掘又可分为w e b 概要( a p 直接挖掘w e b 文档的 内容) 和搜索引擎结果概要( a p 对搜索引擎的查询结果做进一步处理，得到更精 确和有用的信息，以增强搜索引擎的内容查询功能) 。就其处理的内容可分为 文本挖掘和多媒体挖掘。 ( 1 ) w e b 文本挖掘 w e b 文本挖掘从大量的文本数据中发现和提取隐含的、事先未知的知识， 最终形成用户可理解的、有价值的信息和知识的过程。从功能上，w e b 文本挖 掘主要是对w e b 上大量文档集合的内容进行总结、分类、聚类、关联分析以及 利用w e b 文档进行趋势预测等【3 引。 文档总结又称之为文本摘要，是文本挖掘的一个重要内容。它是指从文档 中抽取关键信息，用简洁的形式对文档内容进行摘要和解释，使用户无需浏览 全文即可了解文档或文档集合的总体内容。文本总结在有些场合十分有用，如 搜索引擎在向用户返回查询结果时，通常需要给出文档的摘要。目前，绝大部 分搜索引擎采用的方法是简单地截取文档的前几行。也有使用中心文档代表文 档集合，使用中心词汇表示文档的方法。 文本分类是指按照预先定义的主题类别，为文档集合中的每个文档确定一 个类别，目前文本分类的算法主要有t f i d f 和n a l v eb a y e s 等方法。文献 3 3 】 提出了一种基于模糊分类模型( f u z z yc l a s s i f i c a t i o nm o d e l ) 的d f i c f 方法，d f i c f ( k ，c i ) = d f ( k ，c i ) * i c f ( k ) ，其中d f ( k ，c i ) 是关键词至少出现一次的文档数， i c f ( k ) = 1 0 9 ( i c i c f ( k ) ) ，i c i 是文档分类的总数，c f ( k ) 是关键词至少出现一次的 文档分类数。 文本聚类是将文档集合分成若干个簇，要求同一簇内的文档相似度尽可能 大，不同簇内的文档相似度尽可能小。目前文本聚类的算法主要有两种类型： 以g h a c 等算法为代表的层次凝聚法和以k m e a n s 算法为代表的平面划分法。 也有两种算法的综合。 然而传统的聚类算法对解空间的搜索带有盲目性和缺乏语义特征，文献 3 4 提出两阶段的半监督文本学习策略，第1 阶段，利用贝叶斯潜在语义模型 来标注含有潜在类别主题词变量的网页的类别；第2 阶段，利用简单贝叶斯模 型，在第1 阶段类别标注的基础上，通过e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算法对 不含有潜在类别主题词变量的文档做类别标注。 关联分析是指从文档集合中找出不同词语之间的关系。如b r i n 提出了一 种从大量文档中发现一对词语出现模式的算法，并用在w e b 上寻找作者和书名 的出现模式，从而发现了数千本在a m a z o n 网站上找不到的新书籍。 趋势预测与分布分析是指通过对w e b 文档的分析，得到特定数据在某个历 史时刻的情况或将来的取值趋势。如f e l d m a n 等人使用多种分布模型对路透社 的两万多篇新闻进行了挖掘，得到主题、国家、组织、人、股票交易之间的相 对分布，揭示了一些有趣的趋势。 ( 2 ) w e b 多媒体挖掘 w e b 多媒体挖掘( m u l t i m e d i am i n i n g ) 就是基于w e b 多媒体的内容特征以及 这些特性相关的语义，从大型w e b 多媒体数据集中发现和分析出隐含的、有效 的、有价值的、可理解的模式。主要有w e b 多媒体图像挖掘和w e b 多媒体文 本挖掘。 w e b 多媒体图像数据挖掘的方法很多，如多媒体图像数据的相似性搜索、 多维分析、关联规则挖掘、分类与聚类分析等。 多媒体图像数据的相似性搜索主要考虑了两种图像标引和检索系统：基 于描述的检索系统，主要是在图像描述之上建立标引和执行对象检索，如关键 字、标题、尺寸和创建时间等；基于内容的检索系统，它支持基于图像内容 的检索，如颜色构成、纹理、形状、对象和小波变换等。 多媒体图像数据的多维分析可以按传统的从关系数据库中构造数据立方 体的方法去设计和构造出图像数据立方体。图像数据立方体可以包含针对图像 信息的维和度量，如颜色、纹理和形状。 多媒体图像数据的关联规则挖掘。在多媒体图像数据库中至少可以挖掘如 下3 类涉及图像对象的关联规则：图像内容和非图像内容特征间的关联； 与空间关系无关的图像内容的关联；与空间关系有关的图像内容的关联。 w e b 多媒体文本挖掘，就是从大量的w e b 多媒体文本数据中发现有意义 的模式的过程 35 1 。w e b 多媒体文本挖掘的方法与w e b 文本挖掘的方法基本类 似。 9 2 3 2w e b 结构挖掘 w e b 结构挖掘的目的是发现页面的结构和w e b 的结构。w e b 结构所包含 的信息有：u r l 字符串中的目录路径结构信息；网页内部内容的可以用h t m l 或x m l 表示成的树形结构；网页之间的超级链接结构。 w e b 页面的u r l 可以反映页面的类型，也可以在一定程度上反映页面间 在存储位置和内容方面的层次关系，u r l 目录解析的概念即通过分析网页的 u r l ，分析这种层次关系。s p e r t u s 提出了与w e b 页面u r l 有关的启发式规则， 并用于寻找个人主页，或者已经改变了位置的w e b 页的新位置。 页面内部的链接主要是用于对于包含大量内容的页面起到页面内w e b 导 航的作用，通过分析网页内部树形结构，可以得到其w e b 结构特征，并用于寻 找与给定的页面集合 p 1 ，v n 内容相关的其它页面。 w e b 页之间的超级链接结构中包含了许多有用的信息，当网页a 到网页b 存在一个超级链接时，则说明网页a 的作者认为网页b 的内容非常重要，且 两个网页的内容具有相似的主题。因此，指向一个文档的超级链接体现了该文 档的被引用情况。如果大量的超级链接都指向了同一个网页，我们就认为它是 一个权威( a u t h o r i t y ) 页；而如果有大量的链接离开它指向其它网页，我们认为 它是一个中心( h u b ) 页。 目前对w e b 超级链接结构进行分析的主要方法是将w e b 对应成有向图或 无向图的形式，然后根据一定的启发规则，用图论的方法对其进行分析。这个 领域的两个比较典型的算法是p a g er a n k 算法和h i t s 算法。 也有一些改进算法，如文献 3 6 提出了f a r m i n g ( 基于频繁度的w e b 图的 权威资源挖掘) 算法，诠释了新的权威页面定义，提出了带阶的频繁子图和权 威社团等概念。文献 3 7 提出了加速评估算法以克服现有w e b 超级链接分析中 一个严重缺陷：页面评价两极分化，一些传统的高质量页面经常出现在w e b 检索结果的前面，而w e b 上新加入的高质量页面很难被用户找到。 w e b 结构挖掘主要应用于w w w 上的信息检索领域，可以指导搜索引擎的 网页采集，因为网页链接分析为判断网页的质量提供了一种方式；可以帮助搜 索结果排序，即先用关键词进行搜索，后对结果用p a g er a n k 算法或h i t s 算 法进行排序；也可进行检索结果聚类、查找相关网页、消除重复网页、确定地 理区域和识别社区等。文献 3 8 】提出了一种不仅基于关键词，而且基于网页间 超级链接的结构化搜索引擎( s t r u c t u r a lw e bs e a r c he n g i n e ，s w s e ) ，其核心是 图形数据挖掘工具w e b s u b d u e ”】。 2 3 3w e b 使用挖掘 w e b 使用挖掘( t g 称为w e b 用户访问模式挖掘) ，是从w e b 的存取模式中 l o 获取有价值的信息或模式的过程，就是对用户访问w e b 时在服务器留下的访问 记录进行挖掘。数据源主要包括w e b 服务器日志、w e b 站点的拓扑结构和站 点文件、用户的注册信息、用户调查信息、c o o k i e s ，以及与网站服务相关的数 据库数据等。w e b 使用挖掘过程分为4 个阶段：源数据收集、数据预处理、模 式发现和模式分析。 源数据收集在w e b 日志挖掘中是第1 步，数据最直接的来源是w e b 服务 器。客户访问服务器就会在服务器上产生相应的服务器数据，这些数据可以分 为日志文件和查询数据。 数据预处理主要对用户访问日志进行数据清洗( 消除不相关的项目，如 以g i f 、j p e g 、j p g 为后缀的记录) 、用户惟一性识别( 可以通过分析用户方 c o o k i e s 文件和采用c a t c hb u s t i n g 技术，并且借助其它一些信息来实现) 、用户 会话识别( 采用超时估计的办法) 、完善访问路径和事务识别等处理。 模式发现阶段就是利用挖掘算法挖掘出有效的、新颖的、潜在的、有用的 及最终可以理解的信息和知识。可用于w e b 使用挖掘的技术有路径分析、关联 规则、序列模式、分类聚类技术和依赖性建模，其中路径分析技术是w e b 使用 挖掘所特有的。 模式分析主要是为了从模式发现算法找到的模式集合中筛选出有趣的模 式。精确的分析方法通常是由w e b 挖掘的具体应用来控制的。模式分析的形 式可以是s q l 那样的知识查询机制。也可以把w e b 使用数据装入数据仓库， 以便执行o l a p 操作。诸如图形化模式或为不同的值赋于不同颜色的可视化技 术，可以使得数据中的总体模式或趋势变得更加直观。 w e b 日志挖掘的目的是在海量的w e b 日志数据中自动、快速地发现用户 的访问模式，如频繁访问路径、频繁访问页面组、用户聚类等。 文献4 0 提出了一种w e b 使用挖掘算法，以w e b 站点u r l 为行，以u s e r i d 为列，建立u r l u s e r l d 关联矩阵，元素值为用户的访问的次数，然后对列向 量进行相似性分析得到相似客户群体，对行向量进行相似性度量得到相关w e b 页面，对后者再进一步处理还可以发现频繁访问路径。文献 4 1 提出了支持- 偏爱度的概念，并利用w e b 日志建立以引用网页u r l 为行、浏览网页u r l 为 列、路径访问频度为元素值的网站访问矩阵( 称为稀疏矩阵) ，并将该