（管理科学与工程专业论文）web使用挖掘在电子商务推荐系统中的应用研究.pdf

中文摘要 电子商务的流行使数据挖掘成为商业竞争中一项必不可少的技术。用户对网 站的访问产生了海量的原始数据，这些数据以w e b 日志文件格式存储于w e b 服务 器中，没有数据挖掘技术便不可能将这些海量数据转化为有用的信息。本论文主 要研究w e b 使用挖掘，因为可以通过w e b 使用挖掘了解到用户的浏览行为模式， 而这恰恰是电子商务推荐系统成败的关键。w e b 使用挖掘是数据挖掘技术在w e b 日志文件上的应用，其目的是从中获取有价值的信息为电子商务推荐系统所用。 本文首先提出了一个电子商务推荐系统的体系结构，然后详细讲解了该系统 中各个模块的构造、功能以及如何相互协作从而最终完成推荐任务。并着重研究 了数据预处理和序列模式挖掘的实现。数据预处理是w e b 使用挖掘过程中关键一 步，其处理结果的质量直接影响后续步骤比如事务识别、路径分析、关联规贝q 挖 掘和序列模式挖掘等的效果。提出了数据预处理算法u s i a ，不但在一次处理过 程中可以识别出用户和会话，而且实验证明其处理效率较高而且识别准确。 为了满足关联规则和序列模式挖掘的需要，提出了一个简洁但是高效的算法 p r e d i c t o r 。经第一阶段实验检验基本满足了页面实时推荐的需要，而且该算法同 时实现了数据的增量挖掘。所有实验数据完全为实际网站w e b 同志数据，非模 拟生成，进一步保证了实验结果的准确性和可靠性。 关键词：w e b 使用挖掘电子商务推荐系统数据预处理序列模式 a b s t r a c t t h er i s i n g p o p u l a r i t y o fe l e c t r o n i cc o m m e r c em a k e sd a t a m i n i n g a l l i n d i s p e n s a b l et e c h n o l o g yf o rb u s i n e s sc o m p e t i t i v e n e s s c u s t o m e r s a c c e s sp r o d u c e s a b u n d a n tr a wd a t ai nt h ef o r mo fw e ba c c e s sl o gt h a ti ss t o r e di nw e b s e r v e r w i t h o u t d a t am i n i n gt e c h n o l o g y ，i ti si m p o s s i b l et om a k ea n ys e n s eo fs u c hm a s s i v ed a t a i n t h i st h e s i s w ef o c u s e do nw e bu s a g em i n i n gb e c a u s ei t h e l p sm o s ta p p r o p r i a t e l y u n d e r s t a n du s e r s b e h a v i o r a lp a t t e r n s ，w h i c hi st h e k e yt o s u c c e s s f u le l e c t r o n i c c o m m e r c er e c o m m e n d a t i o ns y s t e m w e bu s a g em i n i n gi st h ea p p l i c a t i o no fd a t a m i n i n gt e c h n i q u e st ow e bl o g sf i l e si no r d e rt op r o d u c er e s u l t su s e di ns o m ea s p e c t s ， s u c ha se l e c t r o n i cc o m m e r c er e c o m m e n d a t i o ns y s t e m f i r s t l y ，af r a m e w o r ko fe l e c t r o n i cc o m m e r c er e c o m m e n d a t i o ns y s t e mw a s p r e s e n t e d t h e ni t se v e r ym o d u l e sf u n c t i o na n dh o wt h e yc o r r e s p o n da n dw o r k t o g e t h e rw a se x p a t i a t e d d a t ap r e p r o c e s s i n ga n df r e q u e n tp a t t e r n sm i n i n gw e r e f o c u s e d d a t ap r e p r o c e s si sf lc r i t i c a ls t e pi nw c bu s a g em i n i n g t h er e s u l t so fd a t a p r e p r o c e s s i n ga r er e l e v a n tt ot h en e x ts t e p s ，s u c ha st r a n s a c t i o ni d e n t i f i c a t i o n ，p a t h a n a l y s i s ，a s s o c i a t i o nr u l e sm i n i n g ，f r e q u e n tp a t t e r n sm i n i n g ，a n ds o f o r t h a n a l g o r i t h mc a l l e du s i ai sp r e s e n t e da n de x p e r i m e n t a l l ye v a l u a t e dt h a ti t se f f i c i e n c yi s h i g ha n di ta l s oc a ni d e n t i 匆u s e ra n ds e s s i o ne x a c t l y as i m p l ea n de f f i c i e n ta l g o r i t h mc a l l e dp r e d i c t o rw a sp r e s e n t e d t tc a nm i n e a s s o c i a t i o nr u l e sa n d 疔e q u e n tp a t t e r n se f f e c t i v e l ya n dc o r r e c t l y i tc a ns a t i s f yt h en e e d o fr e a lt i m ew e bp a g er e c o m m e n d a t i o na n da l s oc a nb eu s e dt oi n c r e m e n t a lm i n i n g e x p e r i m e n t sc o n d u c t e do nr e a lw e b s e r v e r1 0 9 sv e i l f yt h eu s e f u l n e s sa n dp r a c t i c a l i t y o fo u rp r o p o s e dt e c h n i q u e s k e yw o r d s ：w e b u s a g em i n i n g ；e l e c t r o n i cc o m m e r c er e c o m m e n d a t i o ns y s t e m ； d a t ap m p r o c e s s i n g ；f r e q u e n tp a t t e r n s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他入已经发表 或撰写过的研究成果，也不包含为获得叁盗盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：谭。粘 ri 签字e l 期：二。o 声年 ，月，2 日 学位论文版权使用授权书 本学位论文作者完全了解鑫凄盘鲎有关保留：”使用学位论文的规定。 特授权鑫望盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名珲啼导师签名：磁錾轭 签字日期：扩。导年，月，2 - 日签字日期：2 吖年月1 = 1 天津大学硕士学位论文第一章前言 1 1 研究背景 第一章前言 随着互联网的普及以及企业信息化程度的不断提高，电子商务这种商业模 式受到越来越多的重视，电子商务网站已经超越了单纯的企业门户的概念，在起 到沟通企业内外的同时人们开始重视这种新的商业模式如何给企业带来收益。不 论是b 2 b 还是b 2 c ，电子商务网站更多的利用互联网的天然优势发挥了营销的 职能。 最初的电子商务网站只是商家将产品在网站上展示出来，等待和前来浏览 的客户发生交易，显而易见的，这种方式非常被动，而且随着互联网的普及和电 子商务的发展，网站的内容越来越丰富，产品越来越多。电子商务系统在为用户 提供越来越多选择的同时，其结构也变得更加复杂，同时“o n e s i z e f i t s a l l ”的 方法根本不考虑不同用户的需求、偏好、行为特点以及他们的人口信息等等，总 是以同一种方式对待所有不同的用户。如此，导致用户经常会迷失在大量的商品 信息空间中，无法顺利找到自己需要的商品，这样就产生了许多亟待解决的问题： 1 没有针对性的提供信息，客户如何轻易的定位到自己关注过的产品? 2 客户以前浏览、购买过何种商品? 3 客户对何种商品感兴趣? 4 如何向客户推荐他( 她) 可能感兴趣的商品? 5 网站的结构是否合理，是否有利于客户搜寻感兴趣的信息? 以上任何一个环节处理不好都会使客户满意度降低，造成客户流失，而客 户的流失对任何一个电子商务站点都是致命的。基于以上原因，电子商务网站的 个性化技术孕育而生，其目的就是针对不同的客户提供更有针对性地服务，而在 个性化的服务内容中，电子商务推荐系统无疑是核心一环。 电子商务推荐系统是基于w e b 数据挖掘技术发展起来的，它让我们可以从 海量的w 曲数据中只获取自己感兴趣的信息，真正的把数据转化为信息，以供 人们决策。早期的推荐系统提供的推荐信息是对全体用户提供相同的信息，如商 品销售排行榜等，并不是针对单独的用户进行推荐，这类推荐系统在个性化推荐 方面存在不足。随着电子商务的发展，为适应实际商务中客户要求得到一对一的 服务的需要，应用于电子商务网站的推荐系统逐渐向能实时地为客户提供符合其 个人需要的推荐服务的方向发展，电子商务推荐系统直接与用户交互，模拟商店 销售人员向用户提供商品推荐，帮助用户找到所需商品，顺利完成购买过程，从 墨兰查竺堡主! 堡笙苎 笙二兰萱童 _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ - - _ _ _ - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - - 而提高客户对自身网站的信任度。在同趋激烈的竞争环境下，电子商务推荐系统 能有效保留用户、防止用户流失，提高电子商务系统的销售。最终为企业的数字 化发展和企业经济效益的增长提供更广阔的发展前景。 如何通过对用户访问数据的分析，从中获取有价值的电子商务信息，从而 得到详细的商务行为细节，用于商业决策，已成为电子商务发展所面临的一种挑 战a 为此，早在w e b k d d 2 0 0 0 国际学术会议上就已经明确提出了“面向电子商 务的数据挖掘技术”主要集中在w e b 个性化及推荐系统、实现的体系结构及导 航分析三个研究方向”。 电子商务推荐系统具有良好的发展和应用前景，加强对电子商务推荐系统 的研究具有非常重要的现实意义，该领域逐渐成为电子商务i t 技术的一个重要 研究领域，得到了越来越多研究者的关注。国外有一些公司和大学已经进行了这 方面的研究工作，并取得了一定的进展。如今，如何构建一个推荐系统使它能够 实时、准确和高效地向访问网站的不同用户提供更有针对性的服务已经成为 k d d 领域一个新的课题。国外在1 9 9 6 年已经开始有了相关的研究，但是由于我 国电子商务起步较晚，相对来说进行这方面的研究工作起步也较晚，但是由于该 领域所体现出的重要的现实意义，已有一些大学和研究机构在进行这方面的研究 工作。 1 2 本文的工作 电子商务推荐系统在理论和实践中都得到了很大发展，但是随着电子商务系 统规模的进一步扩大，电子商务推荐系统也面临一系列挑战，比如推荐精度不高， 实时性不强等。针对电子商务推荐系统面临的主要挑战，本文对电子商务推荐系 统中推荐算法的设计以及推荐系统体系结构等关键技术进行了有益的探索和研 究。本文的研究内容主要包括提出算法来提高电子商务推荐系统推荐精确度，同 时对电子商务推荐系统实时性以及电子商务推荐系统体系结构进行了有益的探 索，主要工作有以下三点： 1 给出了基于w e b 使用挖掘的推荐系统框架。传统的协同过滤推荐很难为非注 册用户提供高质量的推荐。针对传统的协同过滤推荐存在的上述不足，本文 提出了基于w e b 使用挖掘的具有多推荐模型的电子商务推荐系统体系结构， 推荐引擎对所有推荐模型进行统一管理，并根据不同场合的需要选择不同的 推荐模型，从而向用户提供更有针对性的推荐服务。相对于单独采用传统协 同过滤推荐技术而言，该推荐系统由于考虑的影响因素更多，所以推荐精度 也更高。 2 提出了u s n 算法( u s e ra n ds e s s i o ni d e n t i f i c a t i o n ) ，该算法主要用来进行用 户和会话识别。 天津大学硕士学位论文 第一章前言 3 提出了p r e d i c t o r 算法，p r e d i c t o r 算法主要用来进行序列模式的挖掘。 1 3 论文的结构安排 第二章重点介绍相关理论原理和研究现状，从“数据挖掘”的定义开始，由 粗而细逐一介绍了“数据挖掘”、“w e b 数据挖掘”和“w e b 使用挖掘”的提出、 产生的背景、技术要点、主要理论与发展现状。 第三章对电子商务推荐系统体系结构进行了探索，提出一个离线模块与在线 模块相结合的体系结构，将复杂耗时的计算放在离线模块，避免将其放在在线模 块所导致的在线模块效率的低下，同时研究在线模块的推荐算法，提高在线模块 实时推荐的效率。如此，把离线模块与在线模块充分整合在一起提高整个电子商 务推荐系统的推荐精确度和推荐效率。同时把整个推荐过程分为如下几个主要步 骤：数据预处理、模式挖掘、模型选择和推荐，并分别进行阐述。 第四章主要介绍u s i a 算法( u s e ra n ds e s s i o ni d e n t i f i c a t i o n ) ，u s i a 算法主 要用来进行用户和会话识别，最后通过实验对u s i a 算法进行测试与评价。 第五章介绍了p r e d i c t o r 算法，p r e d i c t o r 算法主要用来进行序列模式的挖掘， 然后通过实验对p r e d i c t o r 算法进行测试与评价。 第六章为论文的结束部分，对论文进行了总结，指出了存在的不足以及进一 步的研究方向。 天津大学硕士学位论文 第二章相关理论和研究现状 第二章相关理论和研究现状 2 1 数据挖掘技术简介 商业用户平时需要处理日常积累的各种数据，对于这些海量信息，用传统的 方法很难从如此大量的数据中找到自己感兴趣的信息，如果因此把这些日常积累 的信息弃之不用是很不明智的，也会因此忽略其中隐含的商业规律。 数据挖掘是一种系统地检查和理解大量数据的工具，它根据预定义的商业目 标，对大量的企业数据进行探索和分析，揭示其中隐含的商业规律，并进一步生 成相应的分析、预测模型来完成辅助决策的作用。它要求从大量的、不完全的、 有噪声的、模糊的和随机的数据中，提取人们事先不知道的但又是潜在有用的信 息和知识。 数据挖掘发现的是以前未知的、可理解的、可执行的信息，所以也被称为“知 识发现”( k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ) 。与统计分析技术相比，数据挖掘技 术能很好地和数据库技术相结合，而且数据挖掘工具用以发现数据中隐含的商业 规律的方法已不局限于统计技术，还包括神经网络、遗传算法、自组织图、神经 模糊系统等统计学科以外的方法。数据挖掘发现的“知识”一方面可以用于构建 预测模型，另一方面可以被用于丰富统计分析师的背景知识，再被统计分析师应 用到数据分析中。 数据挖掘任务一般可以分两类：描述和预测。描述性挖掘任务刻划数据库中 数据的一般特性。预测性挖掘任务在当前数据上进行推断，以进行预测。 简而言之。数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经 有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另外， 由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到很大限 制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这 些数据不再是为了分析的目的而收集的，而是由于商业运作而产生，分析这些数 据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有价值的信息， 进而获得利润。但所有企业面临的一个共同问题是：企业数据量非常大，而其中 真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业 运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘也因此而得名。 数据挖掘技术的发展主要经历了以下几个阶段，如表2 1 所示： 4 天津大学硕士学位论文第二章相关理论和研究现状 2 2 w 曲数据挖掘 现今i n t e m e t 的飞速发展在不断改变着我们的生活，各种各样的网站相继出 现，从站点经营的角度来看，网站的经营者也需要好的自动辅助设计工具，可以 根据用户的访问兴趣、访问频度等信息动态地调整页面结构，改进服务，开展有 针对性的服务以满足不同访问者的需要。这种需求从某种意义上说，访问者本身 可能并不清楚，因此，要解决这两方面需求的一个强有力的工具就是w e b 数据 挖掘，即把数据挖掘的思想和方法运用到w e b 上，对相关信息进行挖掘，获取 有价值的信息。 2 2 1 w e b 数据挖掘简介 现有的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 ) 的方法和技术已不能满足人 们从w e b 中获取知识的需要，这是因为： 1 w e b 数据是异质、异构、动态、模糊的半结构化，非结构化，或数据库 信息： 2 异质、异构以及动态性给数据仓库带来极大的困难； 3 语义理解难度加大，造成基于内容的信息检索难以实现； 4 挖掘算法、信息模型的动态性以及大样本空间搜索能力要求很高： 5 现有的k d d 方法和d m 技术不能直接用于w e b 挖掘。 因此，人们迫切需要一种新技术基于w e b 的数据挖掘技术，以便从w e b 海量的数据中自动地、智能地抽取隐藏在这些数据中的知识。在这种情况下， o e t z i o n i 2 】于1 9 9 6 年最早提出w e b 挖掘这个概念。他认为w e b 网页是有结构的 天律人学硕七学位论文第二章相关理论和研究现状 并且是可以挖掘的。这个观点一经提出，得到不同学科的许多学者的积极支持。 w e b 数据挖掘是数据挖掘技术在w e b 信息源上的具体应用，它是指从大量 的w e b 信息源中发现蕴涵的、未知的、有潜在应用价值的、非平凡的模式。它 所处理的对象包括：用户使用记录、网页内容、w e b 结构等信息。它是一项综合 技术，涉及到i n t e r n e t 技术、人工智能、计算机语言学、信息学、统计学等多个 领域。 与传统的数据挖掘相比，w e b 数据挖掘具有如下的特点： 1 算法的效率要求更高：由于基于w e b 的数据量比一般的关系数据库或者数据 仓库的数据量要大得多，而且数据每天都在迅速的增长和更新，要从如此巨大 的数据中有效的提取有价值的信息要求数据挖掘算法必须具有很高的效率； 2 具有分布性、并行性：网络上的资源是分布的，针对站点上的应用逻辑处理也 是分布的，这就要求w e b 数据挖掘能够在分布式环境下也可以挖掘相关有价 值的信息： 3 具有动态性：w e b 上的数据更新迅速，需要针对不断新增的数据进行增量挖掘， 体现数据挖掘的动态性； 4 数据预处理要求高：由于w e b 上的信息往往是半结构化或者非结构化的，难 以简单的映射成一个固定的模式，这就使传统的数据模型和数据库系统难以直 接支持w e b 上的信息资源，因此必须对数据进行数据预处理，从而为下一步 的挖掘提供具有良好格式的源数据。 2 2 2 w e b 数据挖掘分类 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 ) ，这 三类挖掘技术各有侧重，下面分别进行介绍。 1 w e b 使用挖掘： 用户使用w e b 获取信息的过程中需要不停地从一个w e b 页面通过链接跳转 到另一个w e b 页面，如果某个页面有用户感兴趣的信息他( 她) 在这个页面停 留的时间可能长一些，否则可能关闭这个页面或者跳转到其它的页面，相关的这 些信息都保存在网站服务器的日志文件中，这些信息包括：页面的地址、用户访 问的时间、用户的i p 地址、用户的操作系统版本、用户的浏览器版本、用户的 停留时间、当前页面的引用地址等等，如下所示为一条实际的日志记录： 2 2 1 2 0 2 4 1 8 3 一一 ” 2 5 d e e 2 0 0 3 ：0 5 ：0 0 ：0 0+ 0 8 0 0 1 g e t h t t p ：n e w s t o m c o m p i c l i b 4 19 _ 11 h t m l ”2 0 015 7 6 3 ”h t t p ：n e w s t o m c o m p i c ” ”m o z i l l a 4 0 ( c o m p a t i b l e ；m s i e5 0 ：w i n d o w s9 8 ；d i g e x t ) “ 天津大学硕士学位论文第二章相关理论和研究现状 把其中有价值的信息提取出来如下表所示： 表2 - 2 从同志文件中提取的信息 i p 地址 2 2 1 2 0 2 4 1 8 3 访问时间 访问页面 w e b 服务器对于该请求返回的状态信息 返回给客户端的内容的大小( 以字节为单位) 该请求的引用地址 用户客户端类型 2 5 d e c 2 0 0 3 ：0 5 ：0 0 ：0 0 h t t p ：n e w s t o m c o m p i c l i b 4 1 9 1 1 h t m l 2 0 0 1 5 7 6 3 h t t p ：n e w s t o m c o r n p i e m o z i l l a 4 0 ( c o m p a t i b l e ；m s i e 5 o ；w i n d o w s9 8 ；d i g e x t ) 通过对这些信息的挖掘便可以发现用户的访问模式。它是对现代电子商务战 略的一个重要支持，面向w e b 用户访问模式的挖掘是关于用户行为及潜在顾客 信息的发现，它包括三个阶段，即数据预处理、模式发现及模式分析。 w e b 使用挖掘的数据源主要是w e b 日志文件，通过挖掘w e b 日志我们可以 发现用户访问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 特征描述：这类研究关注用户对站点的访问情况，统计各个用户在 页面上的交互情况，对用户访问情况进行特征描述。 w e b 使用挖掘的主要应用领域便是电子商务推荐系统，电子商务推荐系统是 指根据用户的兴趣特点，向用户推荐其感兴趣的信息。其原理是根据用户模型寻 找与其匹配的信息，或者寻找具有相近兴趣的用户群而后相互推荐浏览过的信 息。这个构造用户模型和“寻找具有相近兴趣用户群而后相互推荐浏览过的信息” 的阶段便是w e b 使用挖掘发挥作用的过程，它的实质是一种“信息找人”的服务 模式，可以减少用户寻找信息的时间，提高浏览效率。此项技术的研究已经取得 显著的成果，且有不少成果已应用到学术、商业领域。目前，世界上比较有影响 的个性化推荐系统有斯坦福大学的l i r a 和f a b 、麻省理工学院的l e t i z i a 。此外， 我国清华大学的o p e n b o o k m a r k 系统也采用了个性化推荐技术。个性化推荐技术 正在迅速朝商业网站领域进军，可以预见，在不久的将来，此项技术将在商业领 域得到更为广泛的应用，并将获得巨大的商业效益。 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 内容挖掘的重点是页面的分类和 聚类。w e b 页面的分类是根据页面的不同特征，将其划分为事先建立起来的不同 的类。w 曲页面的聚类是指在没有给定主题类别的情况下，将w e b 页面集合聚 成若干个簇，并且同一簇的页面内容相似性尽可能大，而簇间相似度尽可能小。 w e b 内容挖掘的应用领域主要是个性化w e b 信息检索，现有i n t e m e t 信息检 索系统一般包含5 个基本部分：自动信息采集器r o b o t 、分析器、索引器、检索 器和用户接口。 ( 1 ) 自动信息采集器负责对w e b 进行遍历并下载文档； ( 2 ) 分析器负责对下载的文档进行分析以用于索引： ( 3 ) 索引器负责将文档表示为便于检索的方式并存储在索引数据库中； ( 4 ) 检索器负责从索引中找出与用户查询请求相关的文档； ( 5 ) 用户接口为用户提供可视化的查询输入和结果输出界面。 这种信息检索服务没有考虑用户的差异，对于任何用户，只要输入的关键词 相同，返回的检索结果就完全相同。而现实中，不同的用户由于背景知识、兴趣 爱好等方面的差异，需要的信息往往是不同的。特别是由于一些词存在多义性， 这些不同领域的内容将混合呈现在返回的结果中。随着i n t e m e t 信息薰的迅猛增 天津大学硕士学位论文 第二章相关理论和研究现状 长，这种不区分用户的检索必将大大耗费检索的时间，导致检索信息的效率低下。 个性化信息检索是指根据用户的兴趣和特点进行检索，返回与用户需求相关 的检索结果。由于在检索中考虑了用户的差异，个性化信息检索可以大大提商检 索的效率。个性化信息检索目前尚处于研究阶段，还没有成熟的系统问世。但随 着智能技术的不断发展以及学术理论的逐渐成熟，个性化信息检索必将取得突破 性的进展。 3 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 算 法1 3 j 和p a g e r a n k 算法1 4 j 。他们的共同点是使用一定方法计算w e b 页面之间超链接 的质量，从而得到页面的权重。著名的c l e v e r 和g o o g l e 搜索引擎就采用了该类 算法。 此外，w e b 结构挖掘另个尝试是在w e b 数据仓库环境下的挖掘，在不同的 w e b 数据仓库中检查副本以帮助定位镜像站点，通过发现针对某特定领域超链 接的层次属性去探索信息流动如何影响w e b 站点的设计。 w e b 结构包括不同网页之间的超链接结构和一个页面的内部结构等。w e b 在 结构上可以用有向图表示出来，页面对应图中的点，超级链接对应图中的边。通 过把w e b 表示成有向图，可以得到从个站点的主页到它的任意一个定点的最短 路径，r o b o t 沿最短路径浏览w e b 站点，就可以以较小的代价发现较多的文档。 微软亚洲研究院在这方面做了一些研究工作。“近十年以来，链接分析和网 页分类作为两种重要的w e b 结构化技术，在w e b 搜索中起了重要作用。为了使 w e b 搜索更加智能化，w e b 结构挖掘技术持续不断地将w e b 搜索推进到新的高度。 媒体管理组正致力于从w e b 中挖掘出不同的结构，包括超级链接结构，网页内部 布局结构，新闻组结构，w e b 团体结构，从用户访问和查询日志中发现的隐式链 接结构，以及h i d d e nw e b 的深层次结构。对于布局结构，我们发明了一种基于 视觉的方法将网页自动分割为语义块，并且找到了许多新方法对它们的重要性进 行建模。通过对网页的这种详细分析，我们可以显著提高“查询扩展”，“图像 检索”以及“网页分类”等许多传统的搜索技术的性能。对于深层次结构挖掘， 我们开发了多项新技术来解析和理解深层网站的结构，从自动学习到全局的结 天津大学硕士学位论文 第二章相关理论和研究现状 构、界面结构以及结果结构之间的映射关系，从而便于w e b 数据集成和深层次 w e b 搜索。对异质w e b 对象进行聚类是w e b 挖掘的另一重要方面。现有的聚类算 法对各种数据对象单独进行聚类，不同数据对象之间的关系通常没有予以考虑， 或仅仅被作为静态特征空间与对象的属性一同处理。我们开发了一种崭新的聚类 算法以处理多种类型的数据对象，名为r e c o m ( 即多类型互联数据对象的互增强 聚类) 。在这种算法下，数据对象之间的关系被用于一个迭代增强的过程，不断 改进他们的聚类效果。这些w e b 分析和挖掘技术对于w e b 结构化起着重要作用， 而且将推动下一代的网络计算。”1 5 2 3 w e b 使用挖掘相关理论 2 3 1 关联规则 关联规则是寻找在同一事件中出现的不同项的相关性，比如发现交易数据库 中不同商品( 项) 之间的联系，这些规则找出顾客购买行为模式，如购买了某一 商品对购买其它商品的影响。发现这样的规则可以应用于商品货架设计、货物安 排以及根据购买模式对用户进行分类。 a g r a w a l 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规 则问题【6 j ，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们 的工作包括对原有的算法进行优化。如引入随机采样、并行的思想等，以提高算 法挖掘规则的效率，对关联规则的应用进行推广。 基本概念： 设，= 力 2 , ，谢是二进制文字的集合，其中的元素称为项( i t e m ) 。记d 为交 易( t r a n s a c t i o 曲r 的集合，这里交易r 是项的集合，并且t _ d 。对应每一个交易 有唯一的标识，如交易号，电作t i d 。设是一个，中项的集合，如果施，那 么称交易r 包含瓜 一个关联规则是形如x j y 的蕴涵式，这里x c ，y c l ，并且x c t y = a p 。规则 x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交易数 与所有交易数之比，记为s u p p o a ( x j y ) ，即： s u p p o r t ( x y ) = i t ：x u y c _ t ，t d i i d l 规则x j y 在交易集中的置信度( c o n f i d e n c e ) 是指包含x 和y 的交易数与 包含x 的交易数之比，记为c o n f i d e n c e ( x j y ) 。即 c o n f i d e n c e ( x j y ) = l t ：x w y t ，t a d i i t ：x 匕_ t ，t e d i 给定一个交易集d ，挖掘关联规则问题就是产生支持度和置信度分别大于用 户给定的最小支持度( m i n s u p p ) 和最小置信度( m i n c o n o 的关联规则。 最近也有独立于a g r a w a l 的频集方法的工作【7 】【甜，以避免频集方法的一些缺 1 0 天津大学硕士学位论文 第二章相关理论和研究现状 陷，探索挖掘关联规则的新方法。同时随着o l a p 技术的成熟和应用，将o l a p 和 关联规则结合9 1 0 1 也成了一个重要的方向。也有一些工作1 1 注重于对挖掘到的模 式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。 关联规则算法同样适用于w e b 使用挖掘当中，在电子商务中关联规则的发现 也就是要找到用户对网站上各个页面之间访问的相互关系。比如，采用关联规则 发现技术，我们可以抽取出如下所示的页面之间的访问相关性： 1 访问页面p 1 的用户中有3 0 也访问了页面p 3 ； 2 访问页面p l 和p 3 的用户中有3 5 的用户也访问了页面p 5 ： 利用这些相关性，我们就可以更好的组织站点的内容和结构，实施更有效的 市场策略，比如利用页面之间的这种相关性可咀进行交叉销售，从而提高销售量。 2 3 2 聚类 聚类是将数据点集合分成若干类或簇( c l u s t e r ) ，使得每个簇中的数据点之 间最大程度地相似，而不同簇中的数据点最大程度地不同；从而发现数据集中有 效的、新颖的、可以理解的数据模式分布。聚类与分类不同，分类之前已经知道 要把数据分成哪几类，每个类的性质、特点是什么；聚类则恰恰相反，聚类是一 种无监督分类法，没有预先指定的类别，在聚类之前并不确切的知道最后会聚为 几类。 聚类方法常见的有划分的方法( p a r t i t i o n i n ga l g o r i t h m s ) 、层次的方法 ( h i e r a r c h ya l g o r i t h m s ) 、基于密度( d e n s i t y b a s e d ) 的方法、基于网格 ( g r i d b a s e d ) 的方法和基于模型( m o d e l b a s e d ) 的方法，下面给出简要的介 绍： 1 划分的方法给定一个n 个对象或者元组的数据库，一个划分方法构建数据的k 个划分，每个划分表示一个簇，并且k m - d 一 e ： 针对l 。我们可以在页面b 上直接添加想传达给用户的各种信息，或者通过 链接指向相应的页面，从而提高该信息的点击率；针对2 ，可以在页面a 、d 、f 和h 上添加相应的广告宣传信息，从而提高广告点击率；针对3 ，可知路径 c 一 m _ d 一 e 为频繁访问路径，可以在这几个页面上添加其它超链接或者促销信 息，从而增加其它信息的访问频度。 2 4w e b 使用挖掘研究现状 1 9 9 5 年3 月，卡内基梅隆大学的r o b e r ta r m s t r o n g 等人在美国人工智能 协会上提出了个性化导航系统w e b w a t c h e r ”j ，斯坦福大学的m a r k ob a l a b a n o v i c 等人在同一次会议上推出了个性化推荐系统l i r a ( l e a r n i n gi n f o r m a t i o n r e t r i e v a la g e n t s ) 1 1 4 ) 。麻省理工学院的h e n r yl i e b e r m a n 在国际人工智能联合 大会( i j c a i ) 上提出了个性化导航智能体l e t i z i a 【l5 1 。这三个系统被公认为个性 化服务发展初期最为经典的系统，它们在用户访问网站的过程中为用户提供个性 化的信息，标志着个性化服务的开始。 天津火学硕十学位论文第二章相关理论和研究现状 此后，个性化服务开始受到学术界广泛的关注。1 9 9 6 年，卡内基梅隆大 学的d u n j am l a d e n i e 在w e b w a t c h e r 的基础上进行了改进，提出了个性化推荐系 统p e r s o n a lw e h w a t c h e r 1 6 】。1 9 9 6 年，著名的网络公司y a h o o ! 推出了个性化入 口m yy a h o o ! 。1 9 9 7 年，a t & t 实验室提出了基于合作方式的个性化推荐系统 p h o a k s 17 1 和r e f e r r a lw e b 他1 。 斯坦福大学的m a r k ob a l a b a n o v i c 和y o a vs h o h a m 推出了基于内容和合作方 式的个性化推荐系统f a b 。f a b 主要由三部分组成：收集a g e n t 、中心分发器和 选择a g e n t ，其体系结构如图2 1 所示 图2 - 1f a b 系统结构 每个收集a g e n t 维护个主题模型，从w e b 中收集与主题模型匹配的页面， 提交给中心分发器；中心分发器维护所有用户的用户模型，根据页面与用户模型 的匹配程度向用户推荐页面：每个用户的选择a g e n t 维护包含该用户的用户模 型，对中心分发器推荐给用户的页面进行筛选，删去用户已经浏览过的页面，并 对每个站点只保留一个推荐页面，而后将经过筛选的页面推荐给用户。这一过程 的实质是基于内容的推荐。用户浏览过推荐的页面后，f a b 要求用户对推荐的页 面进行标注，用户对页面的标注反馈给选择a g e n t 、中心分发器和收集a g e n t ， 用于更新用户模型和主题模型。同时，用户评价很高的页面直接推荐给具有相近 兴趣的用户，实现合作推荐i 悖1 。 1 9 9 7 年3 月， c o m m u n i c a t i o n so ft h ea c m 组织了个性化推荐系统的专 题报道，标志着个性化服务已经被技术界高度重视。 1 9 9 9 年，德国d r e s d e n 技术大学的t a n j aj o e r d i n g 实现了个性化电子商务 原型系统t e l l i m ；麻省理工学院的h e n r yl i e b e r m a n 提出了基于合作方式的个 性化导航系统l e t sb r o w s e 。个性化服务开始向全球发展。 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 的个性化【2 0 j ；同年4 月，以美国为主的多国 天津大学硕士学位论文 第二章相关理论和研究现状 个性化研究机构和网络公司成立了个性化协会，旨在推动个性化服务的发展，同 时保护个性化服务中涉及的用户隐私。这一年，我国也开始了个性化服务的研究。 清华大学的路海明等提出了基于多a g e n t 混合智能实现个性化推荐。 到2 0 0 1 年，个性化研究已经在商业领域得到越来越广泛的应用。纽约大学 的g e d i m i n a sa d o a v i c i u s 和a l e x a n d e rt u z h i l i n 实现了个性化电子商务网站的 用户建模系统l ：i p r o 2 1 j ；i b m 公司在其电子商务平台w e b s p h e r e 中增加了个性 化功能，以