（计算机应用技术专业论文）基于web挖掘的个性化服务.pdf

基于w e b 挖掘的个性化服务 摘要 随着网络技术的高速发展，i n t e r n e t 上的信息呈指数增长。人们要想在众多 的信息资源中找到自己需要的信息非常困难，有时即使找到也是混有“噪音”的 信息。如何能够快速地找到用户所需要的信息，是目前学者所研究的热点。w e b 个性化正是应这种需要而产生的，w e b 个性化即一个w e b 网站根据发现的用户喜 好，动态地为用户定制观看的内容或提供浏览建议，其最直接的实现方式就是向 用户进行推荐，为用户导航。目前存在许多个性化服务系统，根据其实现技术主 要有关联规则方法，协作过滤方法，内容过滤方法。本文主要是对个性服务中的 关联规则方法和协作过滤方法进行研究。 本文首先介绍了数据挖掘、w e 8 挖掘、个性化服务等概念和定义，针对当前 用于计算兴趣度的方法，分析其优点和不足，提出了运用显式和隐式相结合的方 法计算用户的兴趣度，增加了当前常用方法中没有考虑的因素，并给出了相应的 计算公式。 其次，介绍了数据预处理，关联规则挖掘等相关方法，分析了关联规则挖掘 存在一些不足，提出了基于兴趣度的页面关联规则挖掘，主要是将用户兴趣度和 页面关联规则挖掘相结合，并将它用于个性化服务之中，通过实验证明该方法在 推荐准确率上有一定的提高。 然后介绍了协作过滤的定义，协作过滤的算法，协作过滤的实现，利用兴趣 度来处理协作过滤技术，将兴趣相似的用户聚在一起，形成相似用户群体，从而 实现个性化服务，并通过实例说明了协作过滤在个性化技术中的应用。 最后针对协作过滤中存在稀疏问题，本文提出了利用聚类分析方法来形成相 似兴趣度的用户群体来解决稀疏性问题，并给出了基于兴趣度的k - m e a n s 聚类算 法。 关键词：个性化服务数据挖掘w e b 挖掘关联规则协作过滤聚类分析 4 p e r s o n a l i z a t i o ns e r v i c e sb a s e do nt h ew e b m i n i n g a b s t r a c t a st h er a p i d l yg r o w i n go ft h en e t w o r kt e c h n o l o g y , 1 1 坞i n f o r m a t i o ni nt h e i n t e r a c tg o e su pb yi n d e x , i t sd i f f i c u l tt of i n dt h en e c e s s a r yo n ei ns om u c h i n f o r m a t i o n , e v e ni f w ec a l lf i n dt h e mf o rt h e ya r es o m e t i m em i xu pw i t hn o i s e ，h o w t of m do u tt h eu $ e r sn e c e s s a r yi n f o r m a t i o n r a p i d l yi sah o ts t u d yf o rr e c e n tl e a r n e r s t h ew e bp e r s o n a l i z a t i o ni si u s tr e s u l tf r o mt h i s r e q u i r e m e n t t 1 搪w e b p e r s o n a l i z a t i o nm g a n saw e bs i t ed y n a m i c a l l yp r e s c r i b e st h eb r o w s i n gi n f o r m a t i o n , a n dp r o v i d e sb r o w s i n gs u g g e s t i o nf o ru $ e r sa c c o r d i n gt ot h e i rp r e f e r e n c e ，a n dt h e d i r e c tw a yi st or e c o m m e n da n dl e a dt h eu s e r s r e c e n t l yt h e r e r em a n yk i n d so f p e r s o n a l i z a t i o ns e r v i c e ss y s t e m s s u c ha sa s s o c i a t i o nr u l e s 。c o l l a b o r a t i v ef i l t e r i n g a n dc o n t e n tf i l t e r i n gb a s e do nt h e i rp r a c t i c a lt e c h n o l o g y n l i se s s a ym a i n l yp u t s a n a l y s i so nt h es t u d yo fa s s o c i a t i o nr l l l e sa n dc o l h b o r a t i v ef i l t e r i n gi nt h e p e r s o n a l i z a t i o ns e r v i c e s n l i st h e s i sf i r s t l yi n t r o d u c et h ec o n c e p ta n dd e f m i t i o n so fd a t am i n i n g w e b m i n i n g ，p e r s o n a l i z a t i o ns e r v i c e sa n ds oo n i nt h el i g h to ft h er e c e n ta p p r o a c ht o c o u n tt h eu s e r si n t e r e s t s ，t h i st h e s i sa n a l y s i si t sp r o sa n dc o n s ；p u t sf o r w a r da n o t h e r m e t h o dw i t hc o m b i n a t i o no f e x p l i c i ta n di m p l i c i ta p p r o a c h e s ；a d d ss o m ef a c t o r sw h i c h h a v e n tb e e nt a k e ni n t oa c c o u n ti nt h ec o m m o nm e t h o d s t h u sp u t sf o r w a r dt h e r e l e v a n tc o u n t i n gf o r m u l a s s e c o n d l yt h i st h e s i si n t r o d u c e st h ed a t ap r e p r o c e s s i n g a s s o c i a t i o nr u l e sm i n i n g ； a n a l y s e ss o m es h o r t a g e se x i s ti nt h e a s s o c i a t i o nr u l e sm i n i n g ；p u t sf o r w a r dt h e w e b d a g ea s s o c i a t i o nr u l e sm i n i n gb a s e do nt h eu $ e r si n t e r e s t , w h i c hc o m b i n et h e u s e r si n t e r e s t 、i t ht h ew e b p a g ea s s o c i a a o nr u l e sm i n i n g ；a n da p p l i e si t t ot h e p e r s o n a l i z a t i o ns e r v i c e ，a n dp r o v e s t h a tt h i sm e t h o dw o u l di m p r o v et h e r e c o m m e n d a t i o n p r e c i s i o nt h r o u g hm a n ye x p e r i e n c e s t h e ni ta l s oi n t r o d u c e st h ed e f i n i t i o na n dt h ec o u n t i n gm e t h o d so fc o l l a b o m t i v e f i l t e r i n ga l g o r i t h m i ta l s og i v e si n t r o d u c t i o no ft h em e t h o d so fd e a l i n gw i t ht h e c o l l a b o r a t i v ef i l t e r i n gb yn s eo fi n t e r e s t t h u sc o l l e c t st h en s e r sw i t hs i m i l a ri n t e r e s tt o f o r mt h es i m i l a ru s e r sc l u s t e r i n g ，t h e r e f o r e ，p u t st h ep e r s o n a l i z a t i o ns e r v i c e si n t o p r a c t i c ea n di l l u s t r a t e st h ea p p l i c a t i o no fc o l l a b o r a t i v ef i l t e r i n gb ys o m ep r a c t i c a l e x a m p l e s f i n a l l yi nt h el i g h to ft h ec l o s ea n ds p a r s e s t yp r o b l e mi nt h ec o l l a b o r a t i v e f i l t e r i n g ，t h i st h e s i sa l s op u t sf o r w a r dt h ec l u s t e r i n ga n a l y s i sm e t h o dt of o r ms i m i l a r i n t e r e s tu s e r sg r o u p st os o l v et h i sp r o b l e ma n di ta l s op r o v i d e st l l ek - m e a n s c l u s t e r i n gc o u n t i n gm e t h o d sb a s e do nt h ei n t e r e s t i n g k e y w o r d s ：p e r s o n a l i z a t i o ns e r v i c e s d a t am i l l i n gw e bm i n i n ga s s o c i a t i o n r u l e sc o l l a b o r a t i v ef i l t e r i n g c l u s t e r i n ga n a l y s i s 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金a 王些太堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 靴蝴：睁，矸 签字日期d 7 年钿曲 学位论文版权使用授权书 本学位论文作者完全了解盒月墨王些太堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金罡 工些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 嚆，张 签字日期：6 7 年5 月( 矗 f 学位论文作者毕业后去向： c 作单戗豇夭南饭西 通讯地址啦大向洳叶缉批 3 导师签名： 签字日期：o ? 年6 群罚 电话： 邮编： 致谢 衷心感谢我的导师王浩教授在整个论文阶段给予的悉心指导和帮助。王老师 不仅学识渊博，治学严谨，而且思想开明，实事求是。在王老师的关怀和教导下， 我不仅学到了知识，更重要的是学到了思想，领悟到了许多为学的道理，促进了 我学业上的进步，促成了本论文的完成。 非常感谢胡学钢教授。在本论文选题阶段，我多次参加了王老师和胡老师共 同组织的研究生交流学习讲座，使我深受启发，并由此最终确定了选题方向。 同时，我也深深地感谢计算机学院人工智能与知识挖掘研究室的姚宏亮老师， 在论文撰写过程中姚老师给予我无私的帮助和许多有益的建议，使我受益匪浅! 最后，感谢所有对论文提出宝贵意见的老师和同学，感谢在百忙之中评阅论 文和参加论文答辩的各位专家。 6 作者：陈永平 2 0 0 7 年5 月 1 1 背景 第一章绪论 随着人类步入二十一世纪，信息需求快速增长，因特网成为信息传播、 交流与共享的主要媒体，其规模正以惊人的速度发展。全球w e b 站点数目 迅速增长，而在数量增多的同时，网站的规模也日益扩大，各个w 朗站点 的信息量及其复杂度也迅速上升，从而直接导致用户寻找信息的困难。因 此，迫切要求信息服务方式从传统的“一对多”发展到“一对一”的个性 化服务方式，即网站尽可能自动调整以迎合每个用户的浏览兴趣，自动实 时的为用户提供推荐页面，迅速的为用户提供所需的服务，从而让每个用 户能够感觉到他是网站的唯一用户，即个性化服务。个性化服务首先应 该是能够满足用户的个体信息需求的一种服务，即根据用户提出的明确要 求提供信息服务，或通过对用户个性、使用习惯的分析而主动地向用户提 供其可能需要的信息服务。其次，个性化服务也应该成为用户展现自我， 宣传个性的一个窗口。具有一定个性的个体通常都有表现自我、表达自我、 让他人了解自我的愿望。最后，个性化服务应该是一种培养个性、引导需 求的服务，这样可以帮助个体培养个性、发现个性、引导需求，促进社会 的多样性和多元化的发展。个性化服务实施的基本思路是：尽可能使每个 用户在浏览某网站时都有一种他就是该网站的唯一用户的感觉，尽可能地 迎合每个用户的浏览兴趣并且不断调整网站内容来适应用户浏览兴趣的 变化。 目前存在着许多个性化服务系统，根据其实现技术主要有关联规则方 法“1 、内容过滤方法“1 、协作过滤方法h “。关联规则方法是根据用户的 静态特征和动态属性来制定产生式规则，通过规则匹配推算出用户还没有 浏览过但可能是感兴趣的网页，然后依据规则的支持程度排序页面并向用 户推荐排在前n 项的页面。内容过滤方法通过比较资源与用户的兴趣文件 来推荐信息，其关键问题是用户兴趣的提取和相似度的计算。协作过滤方 法通过用户聚类技术来寻找n 个最相似的邻居，根据相似用户预测当前用 户的兴趣并推荐信息，是当前个性化推荐系统中比较成功的方法。 1 2w 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 挖掘的大部分技术来 源于数据挖掘、数据库和信息检索领域。应用研究主要使用关联规则、聚 类、时序序列和路径分析等o ”。 基于w e b 挖掘的个性化服务采用w e b 挖掘技术，与传统的个性化服务相 比具有不要用户提供评价信息，可处理大规模的数据量、用户访问方式可 动态获取、即时和使用方便等优点。因此可以为完全自动、即时的个性化 服务提供支持。 1 。3 基于w e l 3 挖掘的个性化服务 我们将基于w e b 挖掘的个性化服务分为三类o “”：基于w e b 使用挖掘， 基于w e b 内容挖掘，基于w e b 结构挖掘的个性化服务。 ( 1 ) 基于w e b 使用挖掘的个性化服务 基于w e b 使用挖掘的个性化服务就是分析w e b 日志数据和相关数据，利 用数据挖掘方法发现用户的使用模式，从而向用户提供个性化服务”1 。w e b 上每个提供信息资源的服务器上都有一个结构比较好的记录集，即w e b 访问日志。服务器日志文件经常是以扩展的普通日志文件形式来提供信息 的，w e b 日志文件中包含i p ( 主机地址) 、时间戳( 日期时间) 、返回码、传 送的字节数、方法、u r l 、h t t p 、引用页u r l 和浏览器类型等。对于基于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 站点服务。 ( 2 ) 基于w e b 内容挖掘的个性化服务 用户对于w e b 站点页面内容的关注是显而易见的，因此，人们提出基 于w e b 内容挖掘的个性化服务技术。w e b 内容挖掘是从w e b 资源中发现信息 或知识的过程，在创建个性化服务系统时，人们通常应用w e b 内容挖掘对 网页内容进行分析，其中网页的自动分类技术在搜索引擎、数字化图书馆 等领域得到了广泛的应用。根据实现方法的不同可以分成基于代理的方法 和数据库方法。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 的组织结构、w e b 的文档结构及其链接关系中推导知识”1 。由 于w e b 文档之间的关联关系使得w e b 不仅可以揭示w e b 文档所包含的信息， 也揭示了文档间的关联关系所代表的信息，反映了文档之间的某种联系， 同时能体现某个页面的重要程度。因此，利用w e b 结构挖掘技术是提高个 性化服务质量的一个重要途径。通过挖掘w e b 结构信息，对于导航用户浏 览行为、改进站点设计、评价页面的重要性等都非常重要，p a g e r a n k 算法 和c l e v e r 算法利用w e b 页面之间的链接信息来查找“权威”( a u t h o r i t i o ) 网页和“集线器”( h u b s ) 。w e b 结构挖掘通常需要整个w e b 的全局数据，因 此在个性化搜索引擎或主题搜索引擎研究领域得到广泛的应用。 1 4 研究现状及存在的的问题 w e b 挖掘是将传统的数据挖掘技术与w e b 结合在一起的一种技术，w e b 个性化技术是将w e b 挖掘技术应用于个性化服务之中。自上个世纪九十年 代中期出现以来，已经有多种个性化系统：如美国m i n n e s o t a 大学和d e p a u l 大学开发的w e b s i f t 系统致力于w e b 使用挖掘的算法定义及应用工具的研 制；1 9 9 6 年，著名的网络公司雅虎也注意到了个性化服务的巨大优势和潜 在商机，因而推出m yh a y o o 网站，允许用户选择所希望查看的主题中特定 的栏目，并且可指定展示顺序，为自己构造出专用的网页，此后系统能够 进行内容自动更新维护；2 0 0 0 年，n e c 研究院的k u r td b o l l a c k e r 等人为 搜索引擎c i t e s e e r 增加了个性化推荐功能，将c i t e s e e r 个性化；还有象 w e b w a t c h e r 和g r o u p l e n s 主要是基于服务器端的系统，这类系统能够采 集多个用户对某一个网站的访问情况，利用用户之间的相似性提供个性 化服务，但它们不能获得某个用户对多个网站的访问情况，因此很难准确 全面地获取用户的兴趣；w e b m a t e ，p v a ，s y s ki l l & w e b e r t ，l i r a 是基于 客户端的服务系统，但在获取用户兴趣的方式上，它们或者是采用单纯 的显式获取方式，或者只是采用简单的隐式获取方式，不能综合利用用 户的各种行为动态地来提取用户兴趣，并且这些系统很难在算法上对用户 兴趣从时间上进行有效地均衡。2 0 0 0 年4 月，以美国为主的多个国家个性 化研究机构和网络公司成立了个性化服务协会，旨在推动个性化服务的发 展，同时保护个性化服务中涉及的用户隐私。 自2 0 0 0 年我国也开始了个性化服务技术的研究。在我国w e b 个性技术 研究虽然起步较晚，但也取得了一些的成果，如四川大学与香港城市大学 联合开发的个性化远程教学原型系统，南京大学的潘金贵等人设计并实现 了个性化信息搜索智能体d o l t r ia g e n t ，以及目前最大的中文搜索网站百 度等等都是我国在进行个性化研究过程中所取得的成果。 尽管w e b 挖掘技术已经在个性化系统中得到了广泛的应用，但是还是 存在着一些问题，主要有m 1 ： ( 1 ) 性能问题 w e b 个性化系统都不同程度地扩展了传统的浏览器服务器体系结 构，w e b 信息经过相应处理后才能返回客户端，就必然会延长响应时间。 实时个性化系统对响应时间要求比较高，目前的w e b 挖掘算法在处理数据 时通常都采用离线方式，但是由于现有的算法存在一定的不足，造成了性 能的降低。例如关联规则方法如果支持度和置信度选取不恰当，会造成计 算时间太长或较差的推荐性能，一般电子商务网站的网页数目巨大，如果 用关联规则方法进行推荐，会使系统很复杂，效率比较低。 ( 2 ) 隐私问题 这是一个不可回避的问题，因为要想建立个性化w e b 系统就必须有用 户的参与，同时还要分析用户反馈的信息，如果使用c o o k i e s - - 类技术， 这就可能涉及到用户的隐私。目前的w e b 个性化技术还不能很好地解决这 个问题，即在实现个性化服务的同时而又不侵犯用户的隐私。 ( 3 ) 质量评价问题 应用w e b 挖掘技术实现w e b 个性化服务，不同系统采用不同的w e b 挖掘 技术，如何评价它们的建模效果以及系统最终的服务质量也是一个非常重 要的问题。目前对个性化系统服务质量的评价，不同系统采用不同的方式 和测试数据，因此无法评价多个不同个性化系统服务质量的优劣。需要研 究一种通用的性能指标和开发相应的b e n c h m a r k 来评价w e b 各种不同的w e b 挖掘技术。 1 5 本文研究的主要内容和组织结构 本文在对现有的w e b 挖掘和个性化技术进行分析和研究的基础上，针 对目前w e b 挖掘个性化技术研究存在上述的问题，将重点放在支持个性化 服务实现的关联规则方法和协作过滤方法的研究上。应用w e b 挖掘技术， 通过对用户的行为进行分析和研究，得到有用的信息和模式，以满足个性 化服务的需要，解决上述个性化服务中的问题。具体地说，本文进行以下 几个方面的研究和探讨： ( 1 ) 利用w e b 挖掘技术，根据上网用户在网上的行为挖掘出每个用户的 兴趣度。 ( 2 ) 利用w e b 挖掘技术，从上网用户的上网历史中发现那些用户访问页 面之间的关系模式，当用户访问时，如何根据发现的页面关系模式为其推 荐相关的访问页面。 ( 3 ) 利用协作过滤技术为当前用户寻找相似群体，从而为当前用户推 荐将要访问的页面。 ( 4 ) 为了解决协作过滤的不足，将进行当前用户访问模式的聚类规则挖 掘以及相关推荐方法的探讨。 根据上述的研究，本文内容分为五章，每一章的具体内容如下： 第一章绪论。简单介绍了w e b 挖掘和个性化，基于w e b 挖掘的个性化 服务，以及个性化的研究现状及其存在的问题。 第二章相关理论。本章主要详细介绍了数据挖掘，w e b 挖掘和个性 化技术等相关知识，然后介绍了根据用户的访问情况挖掘用户的兴趣度， 分析了已有的兴趣度计算公式的不足，并结合显式和隐式方法给出了一种 兴趣度的计算公式。 第三章页面关联规则挖掘。本章首先介绍w e b 挖掘中的关联规则， 然后介绍了基于兴趣度的页面关联规则挖掘及其在个性化服务中的应用。 主要详细介绍了页面关联规则挖掘算法的描述，实现步骤，并对算法的效 率、推荐的覆盖率和准确率等进行了分析和比较。 第四章协作过滤技术。本章介绍了协作过滤技术，并提出了基于兴 趣度的协作过滤技术，在此基础上，利用一些经典的计算方法寻找相似用 户群体，从而从相似用户群体中为当前用户推荐将要访问的页面，实现个 性化服务。同时也对协作过滤存在的问题，以及目前常用的解决方法进行 了介绍。并且重点介绍了“聚类分析”。主要针对协作过滤产生的相似用 户群体的不足，提出了利用聚类方法产生相似用户群体，实现个性化服务， 从相似用户群体为当前用户推荐将要访问的w e b 页面。采用了基于兴趣度 的聚类分析，对原有的聚类算法进行了改进，并对改进后的算法进行了分 析和比较。 第五章总结了全文的工作并提出了下一步的设想。 第二章相关理论 2 1 引言 数据挖掘( d a t am i n i n g ) 是数据库系统及其应用的学科前沿。数据挖掘 通常又称数据库中知识发现( k d d ) 【9 l ，是自动的或方便的模式提取，这些 模式代表隐藏在大型数据库、数据仓库或其他大量信息存储中的知识。数 据挖掘是一个多学科领域，从多学科汲取营养。这些学科包括数据技术、 人工智能、机器学习，神经网络、统计学、模式识别、知识库系统、知识 获取、信息检索、高性能计算机和数据可视化i l “3 7 1 随着数据处理工具、先进数据库技术以及万维网( w w w ) 技术的迅速发 展，大量的形式各异的复杂类型的数据( 如结构化与非结构化数据、超文 本与多媒体数据) 不断的涌现。因此数据挖掘面临的一个重要课题是针对 复杂类型数据的挖掘，这包括复杂对象、空间数据、多媒体数据、时间序 列数据、文本数据和w e b 数据】，其中w e b 数据尤为重要。 2 2 数据挖掘 2 2 1 数据挖掘技术产生的背景 数据库技术在2 0 世纪8 0 年代的辉煌使得它普及到人类活动的各个角 落，成为各行各业信息化建设的基本工具。经过2 0 多年的数据积累，存 放在大型数据库中的海量数据变成了难得再访问的数据档案。没有强有力 的数据分析工具，理解这些数据已经远远超出了人的能力，同时计算机网 络的广泛应用，加上使用先进的自动数据生成和采集工具，人们所拥有的 数据量急剧增大。i n t e r n & 的迅猛发展使得网络上的各种资源信息异常丰 富，在其中进行信息的查找有如大海捞针。随着信息技术的发展，信息以 指数级增长，而隐藏在其中的知识并没有很好的挖掘和利用，数据的迅速 增加与数据分析方法的滞后之间的矛盾越来越突出，这种突出的矛盾称为 “数据爆炸而知识贫乏”。人们迫切需要利用一种崭新的技术和工具智能 地、自动地将数据转换成有用的信息和知识，获取的信息与知识可以广泛 应用，包括商业决策、生产控制、市场分析、工程设计和科学探索等1 3 a o l 作为计算机的一个领域，机器学习主要的研究问题在于如何通过大量 的训练事例进行学习，产生知识。2 0 世纪9 0 年代机器学习成为研究的热点 之一。将数据库和机器学习结合起来，就产生了海量数据中的知识发现 ( 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 ，这就是数据挖掘这个新兴 的领域。 数据挖掘( d a t a mi n i n g ) 技术是为了解决传统分析方法的不足，并针对 大规模数据的分析处理而出现的，它是架设在数据和信息之间的桥梁，通 过数据挖掘工具可以发现隐藏在大量数据中的丰富知识( 诸如规律、约束、 模式等) 。数据挖掘是信息技术自然演化的结果。数据挖掘可以广泛地用 于各种应用，包括商务管理、生产控制、电子商务、金融投资、欺诈甄别、 市场行销、市场分析、科学探索和通信网路管理等数据挖掘有两个任务： ( 1 ) 机器的数据库理解将数据库变换为在表述上可为计算机理解的 更为简洁的模型，然后利用这个模型求解新问题。 ( 2 ) 数据库理解根据需求简化数据并将其翻译为自然的表示形式 ( 数学公式，自然语言与图表等) ，发现隐含在大量数据中的规律并使之为 人理解。数据挖掘可以从实例数据中直接导出规则，用于构造知识库：也 可在数据库中对已有规则进行验证，因此对知识库的维护和更新也是有用 的。 2 2 2 数据挖掘的定义和过程 2 2 2 1 数据挖掘定义 数据挖掘( d a t am i n i n g ) ，又称知识发现，是在数据库或数据仓库中提 取隐含的、先前未知的、潜在有用的知识或信息模式的决策支持方法“蚓。 同传统的统计分析技术相比，数据挖掘的主要特点是系统的主动性。 传统的统计分析方法具有确定性，是正向思维，即首先由用户设定一个前 提，然后证实或否定它，在此，是用户发挥主动性。而数据挖掘技术具有 探索性，是一种逆向思维，即由系统发现合适的前提。再证实或否定，是 系统在发挥主动性n ”。 2 2 2 2 数据挖掘的过程 数据挖掘的过程一般由3 个主要阶段组成“”：数据准备，挖掘操作、 结果的表述和解释。数据准备阶段包括数据选择和样本数据处理。根据数 据挖掘方法和工具的要求选择合适的数据( 样本、i j i i 练集、测试集等) ，并 对选择的数据进行预处理( 离散化、连续化、编码等) 。挖掘操作包括规则 发现和规则分析及建模。首先将确定的数据挖掘算法在预处理后的数据中 执行，得到相应的结果( 规则) ，再对结果进行辨证分析并将其用于预测、 预报等建模工作中。结果的表述和解释阶段是将建模的结果以容易理解 的、能够接受的形式展现给用户，为用户提供满意的决策支持。 2 2 3 数据挖掘常用的技术 目前常用于数据挖掘的技术有如下几种“： ( 1 ) 人工神经网络它从结构上模仿生物神经网络，是一种通过训练来 学习的非线性预测模型，可以完成分类、聚类、特征挖掘等多种数据挖掘 任务。 ( 2 ) 决策树用树形结构表示决策集合，这些决策集合通过对数据集的 分类产生规则。典型的决策方法有分类回归树( c a r t ) ，一般用于分类规则 挖掘。 ( 3 ) 遗传算法基于生物进化的概念设计一系列的过程来达到优化的 目的。这些过程有基因组合、交叉、变异和自然选择。为了应用遗传算法， 需要把数据挖掘任务表达为一种搜索问题而发挥遗传算法的优化搜索能 力。 ( 4 ) 最近邻技术通过k 个与之最相近的历史记录的组合来辨别新的记 录，有时候也称这种技术为k 一最近邻方法。这种技术可以用作聚类、偏 差分析等挖掘任务。 ( 5 ) 规则归纳通过数理统计方法归纳、提取有价值的i f t h e n 规 则。规则归纳技术在数据挖掘中广泛使用，如对于关联规则的挖掘。 ( 6 ) 可视化可视化就是把数据、信息和知识转化为可视表示形式的过 程。可视化技术为人类与计算机之间提供了一个接口。使用可视化界面， 可以快速高效地与大量的数据交互，以发现其中隐藏的特征、关系、模式 和趋势等。采用直观的图形方式将信息模式、数据关联或趋势呈现给决策 者，决策者可以通过可视化直观地分析数据关系。a n d r e w 等从认识的角度 讨论了可视化在大规模高维数据集中挖掘的作用。l i 采用三维投影技术可 视化关系数据库“”。 2 3w e b 挖掘 2 3 1w e b 挖掘及其分类 万维网目前是一个巨大的、分布广泛的和全球性的信息服务中心，它 涉及新闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其 他信息服务。w e b 还包含了丰富和动态的超链接信息，以及w e b 页面的访 问和使用信息，这为数据挖掘提供了丰富的资源。然而，w e b 挖掘不仅仅 是数据挖掘算法在w e b 数据上的应用，同传统的数据库数据相比，w e b 数 据具有其特殊性，其特点就是数据没有严格的结构模式，含有不同格式的 数据( 文本、声音、图像等) ，面向显示的h t m l 文本无法区分数据类型， 并且存在大量的冗余和噪声，同时w e b 是一个动态性极强的信息源，所以 面向w e b 的数据挖掘研究极具挑战性“。 可以将w e b 挖掘分为以下四个步骤： ( 1 ) 资源搜索检索所需要的w e b 文档或w e b 资源。 ( 2 ) 信息选择和预处理从搜索到的w e b 资源中自动选择特定信息， 并对其进行预处理； ( 3 ) 模式发现自动发现一个和多个站点的模式； ( 4 ) 模式分析 对于发现的规则进行有效性验证或解释。 w e b 挖掘按照挖掘方式一般地可分为三大类，它们是：w e b 使用挖 掘( w e bu s a g em i n i n g ) 、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 ) 。它们又可以根据使用的方法和用途进一步 详细的分类。其分类如下图2 1 所示。 图2 1w e b 挖掘的分类 w e b 挖掘同传统的数据挖掘的区别主要有： ( 1 ) w e b 挖掘的对象是海量、分布、动态、异质的w e b 文档，其信息存 储不同于结化数据库； ( 2 ) w e b 在逻辑上是个由文档节点和超链接构成的图，因此w e b 挖掘 所得到的模式是关于w e b 内容的，也可能是关于w e b 结构的； ( 3 ) w e b 数据的半结构化或非结构的特征，使得这些信息数据难以清楚 地用数据模型加以表示，且缺乏机器可理解的语义，有些数据挖掘技术并 不适用于w e b 挖掘，即使可用也需要建立在对w e b 文档进行预处理的基础 上。因此w e b 挖掘需要用到更多的有别于传统数据挖掘技术。 2 3 2w 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 l o g ) 。 它包括了所请求的u r l ，发出请求的i p 地址和时间戳。对基于w e b 的电子 商务服务器，保存了大量的w e b 访问日志记录。熟点的w e b 站点每天可以 记录下数以百兆字节的w e b l o g 记录。w e b l o g 数据库提供了有关w e b 动态 的丰富信息。因此研究复杂的w e b l o g 挖掘技术是十分重要的。 在开发w e b 使用记录挖掘的技术中，我们可能要考虑如下问题： 首先，虽然w e b l o g 分析可以设想出许多激动人心的潜在应用，但重 要的一点是此类应用的成功要依赖于从这一巨大的原始日志数据中能够 发现什么样可靠和有效的知识，能发现多少。通常，原始的w e b l o g 数据 需要经过清洗、浓缩和转换，以便于检索和分析有意义和有用的信息。 其次，基于u r l 、时间、i p 地址和w e b 页面内容信息，可以在w e b l o g 数据库上构造多维视图，进行多维o l a p 分析，用于找出前n 个用户，前n 个被访问页面以及最频繁访问时间等，这将有助于发现潜在的用户和市 场。 最后，在w e b l o g 记录上可以进行数据挖掘，用于找出关联模式、序 列模式和w e b 访问趋势等。对w e b 访问模式挖掘，通常需要采用进一步的 手段获得用户访问的附加信息，以便于作更为详细的w e b l o g 分析。此类 附加信息包括w e b 服务器缓冲区中用户浏览w e b 页面的序列等。 通过使用这类w e b l o g 文件，可以进行一些研究工作，如系统性能分 析，通过w e b 缓存改进系统设计、w e b 页面预取、w e b 页面交换，认识w e b 信息访问的性质，理解用户的反映和动机。如有些研究提出了可适应站点 的概念，即可以通过用户访问模式的学习改进其自身的w e b 站点。w e b l o g 分析还有助于建立针对个体用户的定制w e b 服务。由于w e b l o g 数据提供 了什么样的用户访问，什么样的w e b 页面的信息，因此w e b l o g 信息可以 与w e b 内容和w e b 链接结构挖掘集成起来，用于w e b 页面的等级划分，w e b 文档的分类和多层次w e b 信息库的结构。 2 3 3w e b 内容挖掘 w e b 内容挖掘是指对w e b 上大量文档集合的“内容”进行总结、分类、 聚类、关联分析以及利用w e b 文档进行趋势预测等，是从w e b 文档内容或 其描述中抽取知识的过程。w e b 上的数据既有文本数据，也有声音、图像、 图形、视频数据等多媒体数据；既有无结构的自由文本，也有用h t m l 标 记的半结构化数据和来自于数据库的结构化数据。根据处理的内容可以分 为两个部分，即文本挖掘和多媒体挖掘。w e b 文本挖掘和通常意义上的平 面文本挖掘的功能和方法相似，但是有其自己的特点，w e b 文本挖掘的对 象除了平面的无结构的自由文本外，还包含有半结构化的h t m l 文本。下 面分别介绍一下w e b 文本挖掘和多媒体文本挖掘。 w e b 文本挖掘是以计算机语言学、统计学理论为基础，结合机器学习 和信息检索技术，从大量的文本数据中发现和提取隐含的、事先未知的知 识，最终形成用户可理解的、有价值的信息和知识过程。内容挖掘多为基 于文本信息的挖掘。按照文本挖掘的对象可把文本挖掘定义为基于单文档 的数据挖掘和基于文档集的数据挖掘。基于单文档的数据挖掘对文档的分 析并不涉及其它文档，其主要的挖掘技术有：文本摘要、信息提取。基于 文档集的数据挖掘是对大规模的文档数据进行模式抽取，其使用的主要技 术有文本分类、文本聚类、个性化文本过滤、文档作者归属、因素分析等。 在w e b 文本挖掘中，文本的特征表示是挖掘工作的基础，文本的分类和聚 类是最重要、最基本的挖掘功能。 多媒体文本挖掘的方法是多媒体文本数据的特征表示、特征抽取以及 多媒体文本挖掘方法进行研究w e b 多媒体文本挖掘通常采用的方法有关 联规则法和特征提取法。对多媒体文本的特征( 描述性特征和语义性特 征) ，其中关键是多媒体文本内容特征的表示和抽取。内容特征在多媒体 数据挖掘中至关重要。获取多媒体文本特征后，通过选定的表示法将其表 示成元数据。对元数据经过结构化处理后存于结构化的元数据库，即多媒 体文本文档特征库。元数据是多媒体文本文档的中间存储形式。可用多媒 体文本挖掘方法对元数据库进行挖掘，寻找其中有用的、新颖的知识。 2 3 4w e b 结构挖掘 w e b 结构挖掘就是挖掘w e b 潜在的链接结构模式，从w e b 组织结构和链 接关系中推导信息与知识的过程。这种思想源于引文分析，即通过分析一 个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。该模 式可用于网页分类，并由此获得有关不同网页间相似度及关联度的信息。 并有助于用户找到指向相关主题的权威站点。w e b 结构挖掘可为超链接挖 掘、内容结构挖掘和u r l 挖掘。 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 表示为有向图，可以得到从一个站点的主页到 它的任意