（计算机应用技术专业论文）web结构挖掘研究.pdf

w e b 结构挖掘研究 摘要 随着i n t e r n e t 迅速发展，网络经济、注意力经济等新概念的出现，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 ) 分析比较了p a g e r a n k 和h i t s 这两种最重要的w e b 结构挖掘算法。 3 ) 深入研究现有的w e b 结构挖掘系统，并在对其核心算法p a g e r a n k 和h i t s 中所存在的问题作了详细分析的基础上提出了自己的改进算法，主要是 对每个网页定义这三个参数：p a g e r a n k 、a u t h o r i t y 、h u b ，并进行分 析，以便我们得到更好的查询结果。 4 ) 最后设计了一个改进w e b 结构挖掘系统原型，根据实验结果进行分析。 关键词：w e b 结构挖掘；数据挖掘；h i t s 算法；p a g e r a n k 算法 r e s e a r c ho fw e bs t r u c t u r em i n i n g a b s t r a c t w i t hi n t e r n e tr a p i de x p a n d i n gs o m en e wc o n c e p t ss u c ha sn e t w o r ke c o n o m ya n d a t t e n t i o ne c o n o m yh a v e b e e nf o u n d w 曲m i n i n gi s b e c o m i n gk n o c k o u tr e s e a r c h p r o b l e m sb yh u g es o c i e t yb e n e f i ta n dw e a t h yc h a l l e n g ec h a n c e al o to fd a m so fw e b h a v eb e e ns t r o e da b u n d a n c ei n f o r m a t i o n i ti sv e r yu s e f u lf o ri m p r o v i n gc o l i l l b _ e r o en e t c o m p e t i t i o np o w e rt of i n dr u l e sa n da f f o r di n d i v i d u a t i o ns e r v i c eb yu s i n gt e c h n o l o g yo f d a t am i n i n g m o s ta b u n d a n ta n dl a t e n c yi n f o r m a t i o nh a sb e e np r o v i d e df o rw e bm i n i n g i nt h er e l a t i o no fp a g el i n k s w e bs t r u c t u r ed i n i n gi sb a s e do nh y p e f l i n ka n a l y s i s i th a s b e e ng a i n e du s e f u li n f o r m a t i o nf r o mm a l l - m a d el i n k ss t r u c t u r e p a g e sc a nb es o r t e d m a k i n gu s eo fi t a n di m p o r t a n tc o n t e n tp a g e sc a na l s ob ef o u n d s ot h a tw ec a nr e f o r m w e bs t r u c t u r et og a i nb e t t e rc o n t e n ts t r u c r l r e a tt h a tt i m ew ec a na l s of i n db e r e rw a yt o i m p r o v en e t w o r kd e s i g nb yi t t l l i sd e s s e r a t i o ng o e so nr e s e a r c ht ow e bs t r u c t u r em i n i n g t h ew o r ka sf o l l o w sh a s b e e nd o n e f i r s t l yi ts u m m a r i z e sr e l e v a n tf i e l d sd e v e l o p m e n ta n dt e c n o l o g yo fw e bm i n i n g a n dw e bs t r u c t u r e s s e c o n d l yt w oi m p o r t a n ta l g o r i t h mo fp a g e r a n ka n dh i t sh a v e b e e na n a l y z e da n d c o m p a r e d t h i r d l yg o d e e pi n t or e s e a r c h i n ga l g o r i t h mu s e di ne x i s t i n gw e bs t r u c t u r e s y s t e m a n di m p r o v e si t sc o r ea l g o r i t h m w em a i n l ya n a l y z et h r e ed a t a so fp a g e p a g e r a n ka n da u t h o r i t ya n dh u b s ot h a tw ec a ng a i nt h eb e s tq u e r yr e s u l t a tl a s tw ea l s od e s i g na ni m p r o v e m e n tw e bs t r u c t u r e s y s t e mp r o t o t y p ew i t h e x p e r i m e n t a lr e s u l ta n dd a t aa n a l y s i s k e yw o r d sw e bs t r u c t u r em i n i n g ；d a t am i n i n g ；h i t s ；p a g e r a n k 插图清单 网1 1w e b 的逻辑结构2 图1 2w e b 挖掘的处理流程2 圈2 1w e b 挖掘分类6 图4 1 有向图g - 2 8 图4 2 有胸图31 图4 _ 3 链接前- 3 3 鹰4 4 链接后3 3 图4 5 有环的有向图一3 4 阐4 6 两个不相连接站点3 5 图4 。7 两个相逢接站点3 5 豳4 8 死链3 5 豳4 9 稀疏矩阵3 7 图5 1w e b 结构挖掘系统的运行机制4 3 、4 4 图5 2 实验结莱分析4 6 表4 1 表4 2 表5 1 表5 2 表格清单 p a g e r a n k 值迭代计算 所链接与p a g e r a n k 得分对照表一 搜索关键字列表 返回结果弛钻拍 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 盒嫂王些丕堂 或其他教百机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名 话、污盟 签字日期：蹦年牛月d 日 学位论文版权使用授权书 本学位论文作者完全了解盒月2 王些友堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金胆王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 确、曾盟 签字日期：西年归驾日 学位论文作者毕业后去向： 工作单位；书民彳钝，) 出券淫 通讯地址：枣f 枝毛暮叁山 导师签名 签字日期：年p 哪日 嚣妻测爨c 7 邮政编码：i 1 力，口f 致谢 褒长达两年半的研究生学习期闻，将一个最初理论上的设想转化为实 践上的初步实现，并对运算性能进行了优化，为将来进一步展开研究奠定 了基础。在此，我十分感谢我的导师胡学镝教授在研究过程中给予我悉心 静指导、全力的支持帮不断静鼓秘。歪是交于琵韵缨心静捂警，瓣蛰熬焘 拨，才使渡能够最终完成论文。 在硕士研究生的学习期间，我还十分感谢计算机学院王浩教授等各位 老师为我们创造的良好学习氛围，多次的学术讨论会不仅让我们了解了其 他两学的工佟，毽遴一步扩宠了翔谈西，掇离了科研髓力。 感漆褫究生院衣计葵辊与馆患学貔豹领导和老搏给予我的援大豹帮 助秘教诲! 感谢在课题磺究过程中历蠢列出帮未列爨豹技号l 用文献豹作 者! 我要衷心感谢我工作单位的领导，尤其是安徽工业大学计算机学院的 院长豢锋教授，稷则凯老师，他们对我的论文工作非常关心，多次绘以指 导和帮助。 作者：陈学进 2 0 0 6 年4 月 第一章燕蠢 1 1 研究背景 目前，互联网已经和我们的生激密不可分，它可以说是一个巨大的、分布 广泛和全球性的信息服务中心。它涉及新闻、广告、消息信息、袅融信息、教 育、政府、电子商务和许多其他信息服务。根据有关机构统计，目前互联网的 数据戳几酉兆兆字节来计算，而且增长速魔很快，如聚将这个庞大的数据库用 般的统计分析采处理的话，显然怒有心无力的。自从数据挖掘技术成功地应 用于传统数据库领域之薏，人们对于数据挖掘在像互联网数据这样的一些特殊 数据深的藏焉也寄予了殍望，并盈傲了许多相应韵研究和发展了相应的技术。 叁鞋i n g s y a nc h e n 等人予1 9 9 6 年在t h e1 6 t hi n t e r n a t i o n a lc o n f e r e n c e o nd i d t r i b u t e dc o m p u t i n gs y s t e m s 大会上把数据挖掇概念应用掰w e b 羰务器 上的想法罄次提出来以采，w e b 挖掇 乍为数据挖撼的一个新主题，是一个新兴 的研究领域，且懿，对子w e b 挖掘的含义，功能迸无统一结论。爨内终豹磷究 重点都集中在臼惠挖撅：s e r v e r l o g s ，e r r o rl o g s ，c o o k i el o g s “”。 随着i n t e r n e t w e b 技术的快速酱及和迅猛发展，使各秽信息w 以以 # 常低 的成本在网络上获得，如何在这个全球最大的数据集合中发现有用信息成为数 据挖掘研究的热点。近年来i n t e r n e t 使计算机、网络、通信合而为一，刚络经 济、注崽力经济等新概念的出现，以其题大的社会效益和极富挑战与机遇的内 涵，成为信息科学最引入注目的研究课题。然而，网络在快捷、方便地带来大 蓬倦意的同对，氇带来了一大难的问题，诸如信息过量难以消化：信息真假难以 辨谈：信怠安全难戳保证：信意形式不一致，难激统一处理等等。如何快速、准 确羹鏊获褥有价镶静网络信怠，鲡旃理解已有的历史数据并用于预测宋来的行为， 蠢霎旃胰这些海羹数据中发溪知识，导致了知识发现和数据挖掘领域的壅现。知 识发现( k n o w l e d g ed i s e o v e r y ，麓称k d ) 帮数攒挖掘( d a t am i n i n g ，简称d 赫) 是集统计学、人工智能、模式识别、并行专 舞、枫器学习、数据露等技术靛一 个交叉性的职究领域。 1 2w e b 数据挖掘过程及分类 在逻辑上可以挹w e b 看俸是位予物璃网络之上的一个有向图g = ( v ，e ) ， 葵中节点集v 对应于w e b 上的新有文档，而有商边集e 刚对应于节点之间的翘 链接( h y p e r l i n k ) 。对节煮集作遽一步静划分，v = v ，v 小所裔的非时节点v 。， 是h t m l 文楼，茭孛除了包摆文本矬羚，运包含了标谗戳指患文档静属往帮肉部 缕构，或者嵌入了超链接以表苯文档耀黔缍构关系。时节煮￥。可懿是h t m l 文 档，也可以是其他接式的文档，例如p d f ，p o s t s c r i p t 等文本文l 牛，以及黧形、 酱频等媒体文件。如图l 。1 所示，v 中每个节点都有一个u r l ，其中包含了关予 节点所位于w e b 站点和目录路径的结构信恩。 嚣i 。， w 口b0 雌漉辑翱￥馨嘧 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 内容发现又分为对文本文档( 包括t e x t ，h t m l 等 格式) 敷多媒体文挡( 露括i m a g e ，a u d i o ，v i d e o 等焱俸类型) 懿发瓣。w e b 缡稳发 现不仪仅局限于文档之间的趣链接结构，还包括文档内部的结构、文档u r l 中 的目录路径终梅等。 与传统数据和数据仓库相比，w e b 上的信息是非结构化或半结构化的、动 态的、著且是容易造成混淆憋，所以很难意接以w e b 网页上的数擐进行数据挖 掘，而必须经过必要的数据处理。热型w e b 挖掘的处理流程如下： 黼1 2w e b 挖攒豹处理流程 w e b 挖掘作为个完挞的技术体系，在进彳亍挖掘之前的信息获得i r ( i n f o r m a t i o nr e t r i e v a l ) 秘售患攘取i e ( i n f o r m a t i o ne x t r a c t i o n ) 稷当重 要。信息获得( i r ) 的目的在于找到相关w e b 文档，它只魑把文档中的数据看 成未经瓣彦懿漏缝鹣嶷台， 嚣痿息撼取( 琶) 演嚣弱在于姨文橙中浅裂嚣簧豹数 据项目，它对文档的结构合表达的含义感兴趣，它得一个重鼹任务就是对数据进 行组织整理并适当建立索弓l 。 信息获得( i r ) 并；玎信息抽取( i e ) 技术的研究已近有很长时间，随着w e b 技 术的发展，基于w e b 技术的i r 、i b 褥到了更多的鬟规。由予w e b 数据鬃非卷 大，丽殷可能渤态变化，用朦来手工方式邈行信息收集早融经力不从心，目前 的研究方向是用自动化、半岛动化的方法在w e b 上进行i r 和i e 。在w e b 环境 下既要簸理菲锸构讫文档，又要处理半结构化的数据，最近几年程这两方面都 有相应的研究成果和具体应用，特别是在大型搜索引擎中得到了很好的应用 【l 。卸 w e b 网站积累的大量数据蕴涵丰甯的信息，利用数据挖掘技术来发现规律， 提供个性化服务，将提高商业网站的竞争力，有很大实用意义。w e b 上顷面之 阗装键揍结掬关系戈w e b 挖辐提供7 摄其枣塞夔港在售惑。夏嚣之阕韵链接反 映了人们的一种判断，也就怒说，如果页面a 的作者建立了指向顾面b 的链接， 则可以认为这是页瑟a 的作喾对页藤b 的一种认嗣。可以这样认为，被众多同 主题蕊面指向的页面具有较大的权威性。w e b 结构挖掘系统就怒充分利用w e b 上页颟之间的超链结构来挖掘其中淤在的信息。目前，利用对网上的超链结构 来逶行w e b 挖掘的系统有g o o g l e 搜索引擎和i b m 的c l e v e r 系统。g o o g l e 搜索 引擎采用p a g e r a n k 算法根据页面间的链接结构对熬个w w w 上的页丽进行簿级排 序，这种簿净与爱户搜索主麓帮页帮内容都无关。i b m 静c l e v e r 系统也鞫瑗页 面间的链接结构对页面进行排序，但是这种排序是建立在用户的搜索主题上的， 它采攥懿是h i t s 算法。出予聪嚣了燹嚣阉豹链接麓褐，这两个系统静援索结栗 明显优于其它的搜索引擎。但是，经过研究发现这两个系统也存谯定的问题， 本文瓣主要工 睾就是逶过对这秀令终稳挖藏系统送雩亍深入熬繇究，在_ 龟饕礁上 设计出一个改进后的w e b 结构挖掘系统原型。 1 。3 本文熬主溪工作 本文深入研究了现有w e b 结构挖掘系统的体系结构和关键算法，主要对 g o o g l e 搜索雩| 擎所采用静p a g e r a a k 箨法帮i b m 的c l e v e r 系统所采鞠h i t s 簿法雩# 了详细的分析，并在对其算法中所存在的问题作了深入的研究的撼础上提出了 耋己靛鼹决方褰，最嚣设计了一个羧迸磊静w e b 结梭挖藕系统嚣蘩程絮。 本文的主要工作可归纳为以下几点： 1 ) 慰理蠢w e b 绩褥挖糕系统翡嚣系续梅亵关键算法邀行磅突与分攒，发瑰 其中所存在的问题。 2 ) 针对现有w e b 结构挖攘系统的运题提出鱼纛的解决方案。主要包旗：结 合链接分析提出一种求解网页r a n k 值方法；改进h i t s 迭代过程；给出种稀 疏矩黪与向量黎积算法。 3 ) 设计一个改进后的w e b 结构挖掘系统原蛰和实验验证与分析。 1 。4 本文的缝织 全文共分为6 章： 第1 章：阐述霹题戆攥爨与磺究营景。 第2 章：w e b 数据挖掘的相关技术背景及研究现状，包括w e b 数据挖掘的 耀关鼓沭、珑状、分类、难患和w e b 结构挖握的基本思想。 第3 章：分析研究了w e b 结构挖掘系统理论熬础、传统的结构挖掘算法， 包括分孝斥传统的p a g e r a n k 算法和h i t s 冀法及其存在的阀题。 第4 章：结合镳接分析提出一种求解潮页r a n k 值方法给出一种消除w e b 有向图死链算法；改避h i t s 迭代过程； 第5 章：设计一个改避后的w e b 缩构挖掘系统豚型，给出部分实验结果擞分 析 第6 章：对全文进行研究总结及腱望，并指出今后的研究方向和需要做的 王绍。 1 5 本章小绪 本章通过分析阐述w e b 技术的快速蛰及和迅猛发展，引出w e b 挖掘这一研 究熬点，蒡麓攀阉述w e b 撼掇豹磐要镶粒重要瞧及蔟静类。鲶爨缝蕊挖藜瀚秘 究舆体步骤。 4 第二章w e b 数据挖掘簿介 随麓以数据库、数搬仓库锋数据仓储技术为基础的信息系统在锫行各业的 应耀，德海董熬瓣不断产生。隧之嚣慕躲褥蘧楚蓊藏多静数据诖天难浚漤诧， 无法从表面上看出他们所蕴涵的有用傣息，更不用说谢效地指导进步的工作。 霸露煞大慧嚣鼗据孛我戴真正霄鼹懿蕊患戒为人稻美涎懿焦点，数据挖掘鼓术 墩正是伴随着这种需求从研究嫩向应用。近年来，随漪i n t e r n e t w e b 技术的快 速普爱霸避猛发震，使各释藩怠虿以戳婆鬻低翦戏搴袭瓣络上获褥，赉于 i n t e r n e t w w w 程全球强连互通，可以从中取得的数据爨难以训一算，稍且 i n t e r n e t w w w 的发曩趋势继续嚣簿，特翅是奄子商务鹣蓬勃发震戈嬲络瘦鲻提 供了强大支持，如何在w w w 这个全球最大的数据集合中发现脊用信息无疑将成 为数据挖撼研究的热点。 2 1w e b 数据挖掘的起源和定义 2 。1 1w e b 数器挖掘瓣麓源 w e b 数据挖掘起源予数据挖掘，数据挖掘魁指从大型数据库的数据中摄取 入稍感兴趣静知淡，蕊这些知鼋 是隐含的、事先未知懿、潜森浆有髑信息。籍： 股票经纪人需要从日积月累的大量的股票行情变化的历史记录中发现其规律， 颤绥预溅未来趋势之爱；憝缓赘酝豹经理火虽暴望戆双遗去尼年鹣锩售记录牵， 分析出顾客的消费习惯和行为，以便及时变换营销策略等等。 数豢挖摇黪提出最秘是赞瓣大型数据疼豹，但是从更广泛豹楚发来讲，数 据挖掘意味着在些事实或观察数据的集合中寻找模式的决策支持过程。因而， 数据挖掇豹对象不仅仅w 墩是数据痒，还可以是任露组织在起的数据集合， 如w w w 信息资源簿。 w w w 以超文本的形式给用户提供了包含从技术资料，商渡信息到毅阉报道， 媛乐信息等多种类别和形式的信息，w 以说w e b 是当今世界上最大的电子傣怠 仓库，蕴岔着巨大潜在价值的知识。然而，i n t e r n e t 是一个县有开放性，动态 德，异鞠性的全球分布式网络，资源分布分散，没有统一的管理和绐构，遮就 导数了信息、知识获取的困难，即所谓的r i c hd a t ap o o ri n f o r m a t i o n 的问题。 这样，运掰现有数据挖掘技术对分布静，异震酶w e b 僚怠资源迸季亍挖攘， 就成为了数据挖掘技术的挑战和未来的发展方向，由此产生了基于w w w 的数据 撼籀。 2 1 2w e b 数据挖掘的定义 w e b 挖掘是一项综合技术，涉及w e b ，数据挖掘、计算杌语言学、倍息学簿多 个领域。不同研究者从翻身的领域出发，对网络信息的含义有着不同的理解， 项嚣开发龟各有其侧重点。饼如，国井有a 认为：w e b 挖掘藏楚耐用数据挖攒按 术，自动地从网络文档以及服务中发现和抽取信息的过程。国内则众说纷纭 有学者将网络环境下的数据挖掘归入网络信息检索和网络信息内容的开发。也 有站在信息服务的角度上提出“w e b 挖掘”，指出其有别于传统的信息检索，能 够在异构数据组成的信息库中。从概念及相关因素的延伸比较上找出用户需要 的深层次的信息，并提出w e b 挖掘将改革传统的信息服务方式而形成一个全新的 适合网络时代要求的信息服务组合。可以一般地将w e b 挖掘定义为： 定义1 ：w e b 数据挖掘是指从大量w e b 文档的集合c 中发现隐含的模式p 。如果 将c 看作输入，将p 看作输出，那么w e b 挖掘的过程就是从输入到输出的一个映射 ：c 一 p 。 2 2w 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 ) 如图2 1 示 w e b 内容挖掘w e b 结构挖掘 w e b 访问挖掘 处理i r 方法 数据库方法 数据 无结构数据、半 半结构化数据 w e b 结构数据 用户访问 v e b 敷据 类型 结构化数据 主要 自由化文本、 t i t m l 标记的超w e b 文档内及文 s e r v e rl o g 、 h t m l 标记的超c 1 l e n tl o g 数据文本档问的超链 文本 表示 词集、段落，概 念、i r 的三种经 0 髓关系圈关系表、图 方法 典模型 处理 t f i d f 、统计、机机器学习、专有 器学习、自然语数据库技术算法如h i t s 和 统计、机器学习、 方法 关联规则 言学习 p a g e r a n k 主要分类、聚粪、模 模式发现、敷据 用户p r o f i l e 、 向导、多层数据 页面权重、分类 应用式发现 聚类、模式发现 自适应w e b 站 库 点、商业决燕 2 2 1w e b 内容挖掘 图2 1w e b 挖掘分类 指从w e b 内容数据文档中发现有用信息，w e b 上的信息五花八门，传统 的i n t e r n e t 由各种类型的服务和数据源组成，包括w w w 、f t p 、t e l n e t 等，现 在有更多的数据和端口可以使用，比如政府信息服务、数字图书馆、电子商务 数据，以及其他各种通过w e b 可以访问的数据库。w e b 内容挖掘的对象包括文 本、图象、音频、视频、多媒体和其他各种类型的数据。其中针对无结构化文 本进行的w e b 挖掘被归类到基于文本的知识发现( k d t ) 领域，也称文本数据挖 掘或文本挖掘，是w e b 挖掘中比较重要的技术领域，也引起了许多研究者的关 6 注。最近在w e b 多媒体数据挖掘方面的研究成为另一个热点。 w e b 内容挖掘一般从两个不同的观点来进行研究。从资源查找( i r ) 的观 点来看，w e b 内容挖掘的任务是从用户的角度出发，怎样提高信息质量和帮助 用户过滤信息。而从d b 的角度讲w e b 内容挖掘的任务主要是试图对w e b 上的数 据进行集成、建模，以支持对w e b 数据的复杂查询。 非结构化文档主要指w e b 上的自由文本，包括小说、新闻等。在这方面的 研究相对比较多一些，大部分研究都是建立在词汇袋( b a go fw o r d s ) 或称向 量表示法( v e c t o rr e p r e s e n t a t i o n ) 的基础上，这种方法将单个的词汇看成文 档集合中的属性，只从统计的角度将词汇孤立地看待而忽略该词汇出现的位置 和上下文环境。属性可以是布尔型，根据词汇是否在文档中出现而定，也可以 有频度，即该词汇在文档中的出现频率。这种方法可以扩展为选择终结符、标 点符号、不常用词汇的属性作为考察集合。词汇袋方法的一个弊端是自由文本 中的数据丰富，词汇量非常大，处理起来很困难，为解决这个问题人们做了相 应的研究，采取了不同技术，如信息增益，交叉熵、差异比等，其目的都是为 了减少属性。另外，一个比较有意义的方法是潜在语义索引( l a t e n ts e m a n t i c i n d e x i n g ) ，它通过分析不同文档中相同主题的共享词汇，找到他们共同的根， 用这个公共的根代替所有词汇，以此来减少维空间。例如： “i n f o r m i n g ”、 “i n f o r m a t i o n ”、“i n f o r m e r ”、“i n f o r m e d ”可以用他们的根“i n f o r m ”来 表示，这样可以减少属性集合的规模。 与非结构化数据相比，w e b 上的半结构化文档挖掘指在加入了h t m l 、超连 接等附加结构的信息上进行挖掘，其应用包括超连接文本的分类、聚类、发现 文档之间的关系、提出半结构化文档中的模式和规则等。 2 2 2w e b 使用挖掘 即w e b 使用记录挖掘，在新兴的电子商务领域有重要意义，它通过挖掘相 关的w e b 日志记录，来发现用户访问w e b 页面的模式，通过分析日志记录中的 规律，可以识别用户的忠实度、喜好、满意度，可以发现潜在用户，增强站点 的服务竞争力。w e b 使用记录数据除了服务器的日志记录外还包括代理服务器 日志、浏览器端日志、注册信息、用户会话信息、交易信息、c o o k i e 中的信息、 用户查询、鼠标点击流等一切用户与站点之间可能的交互记录。可见w e b 使用 记录的数据量是非常巨大的，而且数据类型也相当丰富。根据对数据源的不同 处理方法，w e b 用法挖掘可以分为两类，一类是将w e b 使用记录的数据转换并 传递进传统的关系表里，再使用数据挖掘算法对关系表中的数据进行常规挖掘； 另一类是将w e b 使用记录的数据直接预处理再进行挖掘。w e b 用法挖掘中的一 个有趣的问题是在多个用户使用同一个代理服务器的环境下如何标识某个用 户，如何识别属于该用户的会话和使用记录，这个问题看起来不大，但却在很 大程度上影响着挖掘质量，所以有人专门在这方面进行了研究。通常来讲，经 7 典的数据挖掘算法都可以直接用到w e b 用法挖掘上来，但为了提高挖掘质墩， 磅究久员程扩浸冀法上遴行了努力，惫籍复合荚联霾粼算法、改逶戆痔蠢黢蜣 算法等。 在文献 4 中，根据数据来源、数据类型、数据集合中的用户数量、数据集 合中的服务器数量等将w e b 用法挖掘分为五类： 1 ) 个性挖掘：针对单个用户的使用记录对该用户进行建模，结合该用户基 本信息分析他的使用习惯、个人喜好，目的是在电子商务环境下为该用户提供 与众不同的个性化服务。 2 ) 系统改进：w e b 服务( 数据库、网络等) 的性能和其他服务质量是衡量 用户满意度的关键指标，w e b 用法挖掘可以通过用户的拥塞记录发现站点的性 能瓶颈，以提示站点管理者改进w e b 缓存策略、网络传输策略、流量负载平衡 机制和数据的分布策略。此外，可以通过分析网络的非法入侵数据找到系统弱 点，提高站点安全性，这在电子商务环境下尤为重要。 3 ) 站点修改：站点的结构和内容是吸引用户的关键。w e b 用法挖掘通过 挖掘用户的行为记录和反馈情况为站点设计者提供改进的依，比如页面连接情 况应如何组织、那些页面应能够直接访问等。 4 ) 智能商务：用户怎样使用w e b 站点的信息无疑是电子商务销售商关心的 重点，用户一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 用法挖掘可以通过分析用户点击流等w e b 日志信息挖掘用户行为的动机，以帮 助销售商合理安排销售策略。 5 ) w e b 特征描述：这类研究跟关注这样通过用户对站点的访问情况统计各 个用户在页面上的交互情况，对用户访问情况进行特征描述。 2 2 3w 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 结构挖掘在一定程度上得益于社会网络和引用分析的研究。把网页之 搁懿关罴努必i n c o m i n g 连接嬲o u t g o i n g 连撩，运用鼍! 用分蜒方法找到同网 螭疼释墩及苓溺瓣鼯之越熬连接美系。在w e b 结擒熬掇矮域黢著名豹算法是 h i t s 算法葶辩p a g e r a n k 爨法。他们的熬同点是使用一定方法计算w e b 页面之间 趣连接懿矮整，从弱缮到受蕾鸵掇重。藿名戆c l e v e r 翻g o o g l e 搜繁孳l 擎裁采 用了该爽算法。 此辨，w e b 结橱挖掇另一个尝试魁栏w e b 数据食痒环壤下静挖攘，包捺遇 过检奁阐一台敝务器上的本氇潦接衡壤详e b 结构挖搠w e b 站点的完捻髋，程不 黼的w e b 数据仓库中稔黉副本以帮助瓮彼镜像嫱点，遴过发硫针对浆一籍建鞭 蠛趣连接翁层次瘸往去探索信怠流动辩侮影嫡w e b 辩蕊觞设计。 总之，结椅挖掘是戳超链按分析为评佶豢稽w e b 瓷源，摊嵩搜索溪量，客 躐土避免了人工体弊；减枣了a 霞在搜索结采中蔌时瀚籀撬逸嚣尝试。蕨天麓 鹩链接缭梅孛获壤霄舄的9 餮磬 ，幽于文橼之瓣瓣置遗，w w w 憨够提供黢文楼内 骞之终鹣肖臻镶惑。糕愆这些倍感，蜀臻薅炎藤进行撵毒，发现耋鬣静疼容页 殛，重叛鳃织内嚣结构，使内密逻辑继掬更热台理。 2 3w e b 挖掘晷肉井臻状 w e b 检索对象分为资源发现和信意获敝资深发现就是怒位文稻酶位置， 并自动生成文稍的索弓l 。w e b 上的资源一般分为两类：文档和虢务。磊前，w e b 上的资源发瑶主要集中于文档静羧索靼获取，饔w e b 舞容器挖掘。文本挖掘是一 蜀l 综合技术，涉及数撂挖攘、计算极语言学、痿患梭索、鑫然谣言理解、妇识 管理等溅多领域。不翼瓣礤突人员从各是妨角度出发，对文本挖麴熬食义毒不同 购解释。从数掇挖掘的角度来看，文本挖掘是摆烽数据挖撼技术应用谯大量的 文本集会上，发现其中隐含的知识的过程大多数基于数据摩的数据挖搦方法均 可作用于文本挖掘，如数据归纳、分类、聚类、关联规则挖掘等。文本挖掘的 数据对象既可以是结构化的，也可以是非结构化的、半结构化的。文本挖掘的 结果既可以是对某个文本内容的概括，也可以是对整个文本集合的分类结果或 聚类结果等。 文本挖掘由构造文本集合、文本分析和特征修剪三个步骤构成。待挖掘的 文本可熊分散在多个地方，并巢有不同的类型，如w e b 页黼、o f f i c e 文穑、e m a i l 等，文本挖掘的第一步便憝利弼各种信怠检索工矮收集这些异赝、异构的分布 式文本，形成一个文本数据集。由于文本数箍深罄本土凭结构胃言，一般采焉 巍然语吉描述，现有的讳冀极缀难处理箕语义，耩黻要避行有数酶文本挖掘藏 努矮先檄文本分析，l 蠢取或磐纳文本中具有典型意义懿元数据并热瑷蠢效黪表 示。特截修剪包括横向切片农缎囊投影嚣犟孛方式。撰囊甥片是剔除噪声文档或 抽样数据，改进挖擐鲠量，提嶷精度和效率。纵囱投影是按照挖掘星橡选取有 用的特征，通过这种特征修剪，获取个代表文魈集合的有效的、糖简后的特 ，谯子集，为文本挖撼做好准备。 争 基于机器学习技术的文本挖掘有两种常用方法，即基于内容的方法和协同 的方法。基于内容的方法较广泛地用于w e b 文档或新闻的挖掘中，如a r m s t r o n g 等人开发的系统w e b w a t c h e r 该系统可以通过用户提供的关键字帮助用户在w e b 上定位信息，并给用户超级链接的提示和有关评价。同时系统还给用户提供获 取相似文档的可能性。b a l a b a n o v i c $ 口s h o h a m 开发的系统可以象一个用户一样学 习浏览： 2 n t e r n e t ，在有限的时间里选择最好的w e b 页，接受来自用户的评价。 用户反映的评价信息可用于更新搜索方式并用于选择相应的启发式方法。 g o l d m a n 等人开发的m u s a g 接受从用户处获取的关键字，然后搜索w e b 上有关的文 档，系统能产生语义互相相似的相关概念的辞典，该辞典用于文档获取时扩充 一个给定的关键字集合。而在l i e b e r m a n 开发的l e t iz i a 中，系统不需任何关键 字，也无需对用户强加任何限制，而从用户的浏览行为中推断用户的兴趣。 p a z z a n i 等人和a c k e r m a n 等人开发的系统s y s k i l l w e b e r t 可以收集用户访问的 w e b 页的申请并从中学习用户的形象信息。l a n g 开发n e w s w e e d e r 用于电子新闻过 滤，n e w s w e e d e r 系统利用文本学习产生用户的兴趣模型。系统利用w e b 界面确保 用户以通常的方式存取新闻，同时保证系统收集用户的申请作为反馈。上述系 统一般都提供了基本的挖掘功能，个别系统利用自然语言理解技术实现了概念 挖掘、外形挖掘等高级挖掘功能。其中主要采用的技术是关键字匹配技术、统 计学技术等。如何将模糊技术、免疫、进化、粗集、支撑矢量机等理论和技术 运用于w w w ，实现柔性的数据挖掘是以后的研究方向。 另外，a m m o n d 和b u r k e 等人开发的f a q f i n d e r s u 用基于问题的自然语言界 面存取分布式的文本信息源，帮助用户在数据库中发现对其问题的回答。k a m b a 等人开发的a n t a g o n o m y 可以在w e b 上组成个性化的报纸，系统监控用户对文章的 操作并将其反映在用户的形象信息中。报纸的编排基于给定文章的得分，得分 反映了该文章与用户形象相匹配的程度。例如，具有较高得分的文章更多地放 在报纸的头版。l a m a c c h i a m 提出的工n t e r n e t f i s h 是一类资源发现工具，用于用 户从工n t e r n e t 上抽取有用的信息，系统包括一个具有一定约束的自然语言界 面，只能进行结构化的交互系统也允许使用现有的搜索引擎帮助用户浏览 m a r k o g r o b e l i n k 等提出了基于y a h o o $ 【j 用贝叶斯分类器进行i n t e r n e t w e b 上的 文本分类的方法该方法仅用了少许的几个关键字作为特征向量，通过分析每个 字出现的概率，收集若干具有较高概率的特征字以快速地分类文本。 d u n j a m l a d e n i c 在i j s d p 7 9 4 8 的技术报告中介绍t 他们开发的系统 p e r s o n a l w e b w a t e h e r ，该系统可以看成是一个基于内容的个性化助理，帮助用 户来浏览w e b 。p e r s o n a l w e b w a t c h e r 由两部分组成：服务代理( p r o x y - s e r v e r ) 用于帮助用户通过w e b 浏览器进行交互：学习器( 1 e a r n e r ) 向服务代理提供用户 模型。用户与系统之间的通讯通过磁盘进行。服务代理保存了用户所访问过的 文档的地址( u r l s ) ，而学习器利用这些信息产生用户的兴趣模型。m i t c h e l l 等 1 0 人提出的c a t e n d e r a p p r e n t i c e 可以帮助用户进行会议时序安排，因为系统与一 个电子日历相连接，并能产生一个规则的集合，该集合收集了用户时序安排的 喜好情况和有关出席会议的人员的个人信息利用这些规则可以对新的、还未进 行时间安排的会议提供帮助信息。在1 9 9 9 年召开的d a s f a a 9 9 会议上，日本学者 提交了w e b 文档交互分类方面的文章，提出了利用自组织映射和搜索引擎，通过 w e b 与数据库、人工智能的集成进行w e b 文档分类的方法。 基于内容的方法一般用于一个特定的用户，而协同式方法假定有一组用户 正在使用系统。协同式方法有时又称为公众学习方法，它将其他用户的反应反 馈给当前的用户。系统不去计算分类项目的相似程度，而是计算用户之间的相 似程度。协同式方法不分析分类项目的内容，这也意味着任何内容的分类项目 都可被平等地处理。每一个分类项目都安排一个惟一的标识符以及由用户给定 的一个级别标识。用户之间的相似性是由各用户安排给同一个分类项目的级别 的比较来决定的。协同式方法的一个主要问题是与项数有关的少数用户带来了 等级覆盖稀少的危险。对于数据库中任意一个新的项，为了评价它，必须收集 来自不同用户的信息，只有相同项具有充分多的评价等级的数目，相似的用户 才能被匹配，否则系统的性能将比较差。协同式方法一般用于非文本化的 数据，如电影、音乐等，但是有的系统也将其用于文本数据的挖掘，如新闻过 滤等已有了一些用于电子邮件处理、会议时序安排、电子新闻过滤和娱乐推荐 的系统。娱乐推荐一般完全采用协同过滤，而其他系统可以采用基于内容的方 法或采用信息获取的方法。m a e s 等人提出一个音乐推荐系统r i n g o ，所推荐的音 乐具有高的得分，这些得分是由具有相似音乐尝试的用户给出的。该小组还开 发了用于音乐、电视和书籍推荐的系统f i r e f l y ，f i r e f l y 系统需要用户首先给 出一些预定义的项的级别，以保证任意两个用户比较的可能性( 两个用户可被比 较仅当他们具有相同的分类项) 。t e r v e e n 等人提出了f h o a k s ，该系统可以自动 地识别和重新分配所挖掘的w e b 资源，这些资源是来自u s e n e t 的新闻信息。系统 包括分类规则，该规则可以用来区分不同目标的w e b 资源。在k d d 9 8 国际会议上， d a nl g r e c u 等人提出了一种在分布式环境下进行数据挖掘的强制性学习算法， 也体现了协同式的思想。强制学习是种新的分布式学习模型，它强调合作， 即个体之间信息的交流，不同于其他的协同式方法的是这种信息交流是某个体 样本向其他个体的传送，该个体根据其他个体对样本的响应信息决定下面学习 算子的选择。强制学习可用于分类或预测，自然也可用于分布式w e b 文