（管理科学与工程专业论文）基于聚类的web使用挖掘研究.pdf

原刨性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：塑! 堕知 日 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件和电子版， 允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和 汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：毫! ! 璺垫导师签 山东大学硕士学位论文 摘要 随着i n t e m e t 的普及和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 曲用户访问路径模式发现、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 数据预处理；w e b 聚类，w e b 关联规则挖掘 7 山东大学硕士学位论文 a b s t r a c t w i t ht h ep o p u l a r i t yo fi n t e n r e ta n dt h ee x p l o s i o no fw w w ：w e bn s a g e i n f o r m a t i o ni sb e c o m i n gt h el a r g e s ti n f o r m a t i o nw a r e h o u s e a sar e s u l t t h ec o n f l i c t b e t w e e nt h el i m i t e dh u m a na t t e n t i o na n dt h eu n l i m i t e di n f o r m a t i o ni sb e c o m i n gm o r e a n dm o r es e r i o u s l u c k i l y , w e bu s a g em i n i n gi sf o u n dt ob ea ne f e c t i v em e t h o dt o s o l v et h i sp r o b l e m i tc a nb eu s e dt of i n do u tu s e 心n o r m a lb r o w s i n gp a t e r n sa n dg i v e s i g n i f i c a n ta d v i s e sf o rw e bs i t es u p e r v i s o r sb ye x t r a c t si n t e r e s t i n gp a t e r n s 舶mt h e o r i g i n a lw e bu s a g ei n f o r m a t i o n b yt h i sm e a r 塔，w e bu s a g em i n i n gi ss i g n i f i c a n tf o r w e bs i t ed e s i g na n dm a n a g e m e n t ，b u s i n e s sa n dm a r k e t i l l gd e c i s i o ns u p p o r ta n di l s e r $ a t t r a c t i o n t m sp a p e rf i r s tf o c u s e so nt h et h e o r e t i c a la n dt e c h n i c a lf o u n d a t i o nr e l a t e dt ow e b u s a g em i n i n g , s u c ha sc l u s t e r i n ga n da s s o c i m i o nr u l e s i th a sf o r m e dt h es y s t e m a t i c f r a m e w o r kf o rw e bu s a g em i n i n ga n di l l u s t r a t e dt h ea p p r o a c ht ow e bu s a g em i n i n gi n t a n i so fd a mp r e p r o c e s s i n g , d i s c o v e r i n gu s e rv i s i t i n gp a t t e r n , w e bc l u s t e r i n ga n d c h a r a c t e r i s t i cr u l e s ，e t e i nt h ef i e l do fd a t ap r e p r o c e s s i n g ，t h i sp a p e rs y s t e m a t i c a l l ys t u d i e st h ep r o c e s s e s o fd a t ac l e a n i n g , u s e fi d e n t i f i c a t i o n , s e s s i o ni d e n t i f i c a t i o n , p a t hc o m p l e t i o na n d t r a n s a c t i o ni d e n t i f i c a t i o n w eh a v ed e s i g n e ds o m er e l a t e da l g o r i t h m s i nt h ef i e l do fd i s c o v e r i n gu s e rv i s i t i n gp a t t e r a , t h i sp a p e rr e s e a r c h e st h et h e o r y a n dm e t h o df o ru s e rv i s i t i n gp a t t e r n o nt h eb a s i so fa n a l y z i n gp r e f e r e n c e ，w eh a v e p r o p o s e dt h em e t h o do ff i n d i n gf r e q u e n tb r o w s i n gp a t h b a s e do np a g el e v e la n dd e g r e e o fl i k i n g f i n a l l yd i s c u s s e dt h et e c h n i q u eo ff i n d i n gf i e q u e n tv i s i t i n gp a t hc o n s i d e r i n g t h es u p p o r t ，b r o w s i n gt i m ea n dp a g el e v e l i nt h ef i e l do fw e bc l u s t e r i n g , t h ep a p e rs y s t e m a t i c a l l ys t u d i e st h em e t h o d so f d e t e r m i n i n gt h el i k e n e s so f c l u s t e r i n go b j o a s c o n s i d e r i n gt h ef e a t u r e so f t h ew e b ，t h e p a p e ra l s os t u d i e st h em e t h o d so fw e bp a g ec l u s t e r i n gb a s e do nl i n kd i s t a n c eb e t w e e n p a g e s i nt h ef i e l do f w e b u s e rc l u s t e r i n g ，w ee x p l o r eac l u s t e r i n ga p p r o a c hc o n s i d e r i n g i n t e r a c t i o na n di n f l u e n c ea m o n gc l u s t e r i n go b j e c t s i naw o r d ，t h ep a p e rs y s t e m a t i c a l l yd i s c u s s e st h ep r o c e s so fw e bu s a g em i n i n g , t h e o r ya n dm e t h o df o rm i n i n gi m p l i c i tk n o w l e d g ef r o mh u g ea n ds c m i s t r u c t u r e dw e b d a t a , t op r o v i d eab r o a dp r o s p e c tf o rt h ed e v e l o p m e n to f w e bu s a g em i n i n g k e y w o r d s ：w e bu s a g em i n i n g ；w e bd a t ap r e p r o c e s s i n g ；w e bc l u s t e r i n g ，w e b m i n i n go f a s s o c i a t i o nm l e 8 山东大学硕士学位论文 1 1 研究的背景和意义 1 1 1 本文的研究背景 第1 章绪论 随着h t e r n e t 的迅速发展和广泛普及，w e b 的信息量以惊人的速度增长。目 前，w o r l dw i d ew e b 己深入到人类社会的每一个角落，成为拥有近亿个工作站， 数十亿页面，蕴含着巨大潜在知识价值的分布式信息空间【l 】。w e b 数据结构复杂， 形式多样，它的许多特点，使得对w e b 进行有效的信息抽取和知识发现面临着极 大的挑战【2 j 。 首先，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 上的极少的一部分信息，那些多余的信息对用 9 山东大学硕士学位论文 户来说价值不大，而且会“淹没”用户期望的搜索结果。9 9 的w e b 资源相对9 9 0 , 6 的用户是没有用处的。所以，虽然网上信息储备量极大，信息内容十分丰富，但 信息的利用率很低例。 w e b 上的信息资源具有开放、动态、异质、海量、分布、复杂、非结构化等 特点，用户如何从这些异构化的数据中查找自己所需要的有用的信息，这就需要 一种新的技术，能自动地从w e b 上发现、抽取和过滤信息，由此产生了w e b 数 据挖掘，即w e bd a t am i n i n 9 1 4 5 l 。我们将传统的数据挖掘的思想和方法应用于半 结构化和无结构的w e b 数据，并研究发现这些知识和模式的技术和方法，从而形 成了“e b 数据挖掘这样一个新的研究方向。 w e b 数据挖掘不同于传统的数据挖掘。传统的数据挖掘是以数据库中的结构 化数据为对象，并以关系表等存储结构来发现知识。w e b 数据挖掘的研究对象是 w e b 数据，这些数据没有统一的模式。这些特点决定了w e b 数据挖掘要比传统的 数据挖掘复杂和困难得多，它要用到更多的有别于传统数据挖掘的技术，需要新 的模型、算法和体系等。 1 1 2 本文研究的意义 论文研究以数据挖掘理论、决策理论为基础，对w e b 使用挖掘的理论和方法 进行研究。本论文研究目的主要是建立w e b 使用挖掘的研究框架，通过对客户访 问网站的行为、频度、内容等进行挖掘分析，提出w e b 使用挖掘的支持机制和模 型，对电子商务和企业建站等提供指导。 w e b 数据挖掘是当前非常前沿的研究领域，许多问题有待于进一步研究和深 化，所以，本课题具有广阔的应用前景和重要的现实意义，特别是对于开展有针 对性的电子商务活动十分重要，这表现在： ( 1 ) 完善w e b 使用挖掘的理论研究框架，对进一步深入开展w e b 使用模式 发现和分析有一定的指导意义。 ( 2 ) 通过掌握访问者在网站上留下的信息，提取相应的商务智能，为改善客 户关系，增加市场效益打下基础。 例如，挖掘用户的访问信息，可以得到群体用户的共性特征和个体用户的偏 好行为，从而向他们推荐其感兴趣的商品，进行个性化行销；根据用户的历史访 问信息，可以推断预测同类用户将来的访问模式和购物行为；在挖掘已有客户知 识的基础上，识别出某种产品或服务的可能购买者，发掘潜在顾客；充分利用各 种营销手段，比如在用户频繁访问路径上设置个性化的广告服务，从而更好地吸 引和维持顾客，提高客户满意度和忠诚度，并为商家营销决策提供正确的指导， 1 0 山东大学硕士学位论文 提高电子商务活动的效率。 ( 3 ) 通过完善w e b 使用模式发现技术，为构建智能化w e b 站点提供理论依 据。通过分析用户的浏览行为，按照用户的兴趣和爱好，向用户提供浏览建议， 把信息以更快的方式传递给用户。并为w e b 站点设计者提供调整网站的关键信 息，使网站的修改和建设更加有的放矢，从而提高网站的智能化程度，提供个性 化全方位的网站服务。 1 2 数据挖掘研究现状 1 2 1 数据挖掘的概念 1 9 8 9 年8 月在美国底特律召开的第l l 届国际人工智能联合会议的专题讨论 会上，首次提出了数据库中的知识发现( 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 ) 这一概念。而后随着研究的不断深入，关于k d d 的定义几经修订并日益完善。 目前学术界公认的比较完整的定义是由f a y y a d 等给出的 6 1 ，即“k d d 是从大量 数据集中识别出有效的、新颖的、潜在有用的以及最终可理解模式的高级处理过 程”。 数据挖掘( d a t am i n i n g ，简称d m ) 的概念，是1 9 9 5 年在美国计算机学会 a c m 会议上首次被提出的。目前对于数据挖掘，并没有一个非常严格的定义， 比较一致的看法是：数据挖掘就是从数据库中抽取隐含的，以前未知的，潜在有 用的信息的过程。 数据挖掘与k d d 这两个术语的内涵大致相同，关于二者的关系，学术界一 直存在两种倾向，一种认为数据挖掘是k d d 从数据库中发现知识过程中的一个 特定步骤；另一种观点认为二者所研究的问题基本致。通常情况下，大多数研 究人员都采用后一种观点，在使用k d d 与数据挖掘时并不严格地划分界限。 1 2 2 数据挖掘的处理过程 k d d 的处理过程较为复杂，涉及多个处理步骤。f a y y a d 等人提出一个k d d 处理模型 6 1 ，如图1 1 所示。在该模型中，k d d 的处理过程共分为九个阶段，它 们是：数据准备、数据选择、数据预处理、数据缩减、k d d 目标确定、挖掘算法 确定、数据挖掘、模式解释及评价。 山东大学硕士学位论文 目标数击瑶篓嚣言簇 模式知识 图l lk d d 的处理过程 数据挖掘是一个往复循环的过程，在k d d 处理过程中，我们可以把数据挖 掘之前的各步看作是数据挖掘的前期准备阶段，把数据挖掘之后的各步看作是数 据挖掘结果的后期处理阶段。在前期处理阶段，需要了解领域的背景知识及用户 需求，选择并分析相关数据或样本，检验数据的完整性和一致性，去除与挖掘无 关的数据，使其成为适合挖掘的形式。接着确定k d d 发现的知识的类型，选择 合适的知识发现算法以完成k d d 目标，然后从数据中挖掘出用户所需要的知识。 在后期处理阶段，需要对挖掘出的知识进行解释，使用可视化或其他知识表示技 术，将挖掘的知识提供给用户并进行正确的评价。 1 2 3 国内外数据挖掘的研究现状 数据挖掘的发展虽然只有短短数年时间，但它的广阔应用前景吸引了大批国 内外研究人员和机构，一系列应用系统或原型被开发出来，它们代表了当前数据 挖掘技术的最新研究成果，并对数据挖掘的蓬勃发展起了巨大的推动作用。 美国b u s i n e s so b j e c t s 公司推出的b u s i n e s s m i n e r ，采用了基于可视化的树型 技术，寻找潜在的趋势，建立正确的模型，为最终确定商业发展的规律提供支持。 s g i ( s i l i c o ng r a p h i c sl n c ) 公司开发了m i n e s e t ，它的特色在于具有强大的 图形工具，用于实现数据和挖掘结果的可视化，如规则可视化工具，多维数据分 散可视化工具，地图可视化工具等。 加拿大s i m o nf r a s e r 大学的j h a n 教授领导的研究小组于1 9 9 7 年研制并开发了 数据挖掘系统d b m i n e r ，这是一个通用的在线分析挖掘系统，目前该研究机构正致 力于研制专业化的数据挖掘系统原型，如多媒体数据挖掘原型m u j 血n e d i am i n e r 。 i b m 公司研制的数据挖掘产品i n t e l l i g e n tm i n e r ，是目前数据挖掘领域较为先 进的产品，通过其较为先进的技术，如序列模式发现、关联、聚类等，自动实现数 据选择、转换、挖掘和结果可视化，可用于销售、财务和客户关系管理等领域。 山东大学硕士学位论文 d m w 是一个应用在信用卡欺诈方面的较为成熟的数据挖掘工具，以自动和 人工两种模式操作，它的欺诈侦测应用程序用于实时分析信用卡事务，在市场上 取得了巨大的成功 美国u m f a y y a d 等人开发的s k i c a t 系统是帮助天文学家发现遥远的类星 体的工具，它将图像处理、数据分类、数据库管理功能集于一身。 其他一些比较有代表性的产品还有a t & t 实验室b r a c h m a n 等人开发的 i m a c s 系统，a n g o s s 国际有限公司开发的k n o w l e d g es e e k e r ，c o g n o s 软件公司 开发的s c e n a r i o ，思维机器公司开发的产品d a r w i n ，a n a n d 等人开发的s p o t l i g h t 等系统。这些系统被广泛地应用于各国的金融、零售业、制造业、保险业、电信 业、计算机软件和硬件等各个领域，带来了巨大的经济效益，显示了数据挖掘系 统在庞大的信息市场中占有的重要位置。 与国外相比，国内对k d d 的研究起步较晚，1 9 9 3 年国家自然科学基金支持 了该领域的项目，反映了学术界对这一研究方向的关注。之后，国内一些学者和 团体组织了很多相关的会议，象p a k d d 这样有影响的国际会议也陆续在国内召 开，所有这些都促进了k d d 的基础理论和应用研究的发展。 到目前为止，全国许多科研院所、高等院校及企事业单位也纷纷从事于数据 挖掘方面的研究，并取得了一定的成果。例如菲奈特融通公司成功地开发了商 业智能套件b i o f f i c e ，该产品能迅速方便地为企业构建决策提供支持，使企业管 理层全面、详细、及时地了解公司运营状况，做出正确地决策。上海宝山钢铁公 司针对钢铁行业的特点开发了数据挖掘软件，成功地挖掘和分析了影响钢铁质量 的因素，创造了巨大的经济效益。 1 3w e b 数据挖掘的研究现状及分析 1 3 1w e b 数据挖掘的概念及特点 目前，对于w e b 数据挖掘的含义、功能等尚无统一的结论，国内外许多学者 在理论上开展了很多讨论，不同研究者从不同角度对w e b 数据挖掘的含义给出了 不同的解释。 m b a u e r 等人认为w e b 数据挖掘就是将传统的数据挖掘技术和w e b 相结合， 进行w e b 知识的提列”。 m p e r k o w i t z 等人认为w e b 数据挖掘是在w w w 上挖掘有趣的、潜在的、有 用的模式及隐藏的信息伟，9 】。 王继成等人将w e b 数据挖掘定义为从大量w e b 文档集合中发现隐含的模式。 山东大学硕士学位论文 它借鉴了数据挖掘的传统定义，认为w e b 数据挖掘是从大量非结构化，异构的 w e b 信息源集合中发现新颖的，有效的，潜在可用的，可理解的知识的非平凡的 过程【l o j 。 王实等人认为，w 曲数据挖掘是针对包括w 曲页面内容、页面之间的结构， 用户访问信息、电子商务信息等在内的各种w e b 数据，应用数据挖掘方法以发现 有用的知识来帮助人们从w w w 中提取知识，改进站点设计，更好地开展电子商 务0 1 , 1 2 1 。 杨文清、邹涛等人也对w e b 数据挖掘从帮助人们从w w w 中提取知识的角 度进行了阐述 1 3 14 1 5 1 。 总之，w e b 数据挖掘是以从w e b 上挖掘有用知识为目标，它将传统的数据挖 掘技术与w e b 结合起来【l ”，利用数据挖掘技术从w e b 文档和w e b 活动中发现有效 的、新颖的、潜在有用的，并且最终可理解的信息和模式，它是一门交叉性学科、 涉及数据挖掘、人工智能、机器学习，数据库与数据仓储、统计学、信息学、计算 机网络技术、计算机语言学等多个领域。w e b 数据挖掘可以在多方面发挥作用。 1 3 2w e b 数据挖掘的分类 丰富的w e b 信息决定了w e b 数据挖掘任务的多样性。现有的研究工作，一 般是按照挖掘对象的不同，将w e b 数据挖掘分为三类17 ，1 8 l ：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 bu s a g e m i n i n g ) ，如图1 - 2 所示： 1 4 图i - 2w e b 数据挖掘的分类 山东大学硕士学位论文 1 3 2 1w e b 内容挖掘w e b 内容挖掘是指对w e b 页面内容进行挖掘，从w e b 文档的内容信息中获取潜在的、有价值的知识和模式的过程i 。 从挖掘的对象上看，w e b 内容挖掘针对的是w e b 文档信息( 包括t e x t ，p d f ， h t m l 等) 和多媒体信息( 包括a u d i o ，v i d e o ， n l a g l o 等) 。对于多媒体数据的挖 掘称为多媒体数据挖掘【2 0 】。w e b 多媒体数据挖掘的主要作用是发现隐藏的知识， 洞察多媒体文档中用传统方法无法发现的模式，为w e b 文本挖掘提供基础。文本 挖掘是基于文本文档的知识提取，挖掘的结果既可以是对某个文本内容的概括， 也可以是对整个文本集合的分类或聚类结果。 从实现方法上，w e b 内容挖掘分为两大类：信息捡索方法和数据库方法。信 息检索方法主要应用信息检索技术，评估和改进搜索信息的质量。数据库方法是 指采用数据挖掘技术，针对w e b 上的半结构化、异质的数据，利用数据转换和析 取的方法，将其映射或转换为结构化的数据，使之成为高质量的资源。数据库方 法的研究主要集中在模型的析取和发现1 2 q 。 1 3 2 2w e b 结构挖掘w e b 结构挖掘是从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 l 2 2 1 ，它们利用了文档间的链接信息，查找相关 的w e b 页并给出页面的重要性。有关这方面研究的算法有h i t s ( h y p e r l i n k - i n d u c e dt o p i cs e a r c h ) ，p a g er a n k 2 3 1 及改进的h r r s 。成型的应用系 统有c l e v e rs y s t e m l 2 4 1 和g o o g l e 等，这些系统纳入了w e b 信息和文本内容 信息，取得了很好的查询效果。 p a g e r a n k 的基本思想是乜2 j ：如果一个页面被其它页面多次链接，则这个页 面可能是重要的；一个页面未被多次链接但被一个重要页面所引用，则这个页面 也可能是重要的；一个页面的重要性被均分并被传递到它所引用的页面中。 h u b a u t h o r i t y 方法1 2 】：该方法的思想是利用h u b 页寻找权威页面。h u b 页面 是一个或多个w e b 页面，它提供了指向权威页面的链接集合，同时还提供了指向 就某个主题而言最为优秀的网站链接。h u b 页面发挥了说明内含某类主题权威页 面的功能。高质量的h u b 链接指向大量高质量的权威( a u t h o r i t y ) 页面；高质量 的权威页面由许多高质量的h u b 页面所链接。这种h u b 页面与权威页面之问的关 系，可用于挖掘权威页面和发现高质量的w e b 结构和资源。 山东大学硕士学位论文 1 3 2 3w e b 使用挖掘w e b 使用挖掘是通过挖掘w e b 日志记录来发现用户 访问w e b 页面的模式 2 5 1 ，研究用户的浏览行为，这是w e b 数据挖掘中最重要的 一种形式。这方面的研究专家r o b e r tc o o l y 将w e b 使用挖掘定义为在大型w e b 资源中应用数据挖掘技术以分析w e b 站点的使用 2 6 1 。w e b 使用挖掘是w e b 数据 挖掘中与传统数据挖掘技术交叉点最多的领域，主要目标是从w e b 的访问记录中 抽取感兴趣的模式。通过w e b 使用挖掘，可发现个人用户的检索偏好和习惯，以 及用户群体的共性行为，来确定产品的市场战略，有效地组织站点，有针对性地 开展电子商务活动，提高商业活动的效率。 首先分析一下三者的区别【2 7 】，主要从数据特征、表示形式、挖掘方法等方面 进行了比较，如表l - 1 所示。 ， 表1 1w e b 内容挖掘、结构挖掘和使用挖掘比较 w e b 数据挖掘 w e b 内容挖掘 w e b 结构挖掘 w e b 使用挖掘 信息检索观点数据库观点 文本文档链接结构、w e i , 页服务器日志、用 数据 超文本文档 超文本文档面户注册信息等 非结构化 半结构化，数据库 数据特征 链接结构交互式数据 半结构化形式的网站 词、短语，概念或 关系型数据 数据表示 实体，关系璎数据对象交换模型 图形 关系表、图 形式 库等( o e m ) t f i d f 、机器学习、专利算法，修改后专利算法、归类、机器学习、关联 方法 统计学的关联规则聚类规则、聚类等 分类、聚类，寻找发掘高频的子结分类、聚类、信息站点管理及优 应用 文本模式，用户建构，发掘网站体系检索，个性化搜索化、网络安全、 模等结构引擎等推荐系统等 三种挖掘都被称为“对网络的挖掘”，都是数据挖掘的有价值的应用。但从商 务的角度考虑，最有意义的部分应该在使用挖掘，因为它同客户行为密切相关。 w e b 使用挖掘一般需要经过数据预处理、模式发现、模式分析等过程1 2 2 l 。 1 6 山东大学硕士学位论文 图1 - 3w e b 使用挖掘的一般过程 ( 1 ) 数据预处理预处理是w e b 数据挖掘中不可缺少的一个阶段，预处理的 目的是为模式发现阶段提供可靠完整的数据源，其质量直接关系到w e b 数据挖掘 结果的好坏。w e b 使用挖掘的数据预处理，内容包括数据清理、用户识别、会话 识别、路径补充、事务识别1 2 6 j 。 ( 2 ) 模式发现数据预处理后，就可根据具体的分析需求选择访问模式的发 现技术，如路径分析、关联规则挖掘、聚类和分类、时序模式识别等。 模式发现可应用许多相关领域的方法，但这些方法不能简单地照搬，需针对 w e b 数据挖掘的特点做出相应的改进。有关w e b 使用挖掘模式发现的理论基础将 在第2 章详细讲述。 ( 3 ) 模式分析为了使各种挖掘方法挖掘出来的模式得到充分的利用，必须 开发各种w e b 分析技术和工具，辅助分析人员加深理解。模式分析的主要目的是 过滤掉冗余、无关和常识性的信息，并对感兴趣的模式进行可视化和解释。比如： 将抽象的使用模式通过模式分析工具处理后，得到清晰的、容易理解的方式，分 析者利用知识查询语言，再对其进行处理，得到感兴趣、有价值的模式，最后将 这些模式采用可视化的技术以图形界面的方式表示给使用者。模式分析的方法有： 联机分析、可视化、知识查询和信息过滤【捌。一些w e b 使用挖掘原型系统象w u m ， w e b m i n e r 嵌入了类s q l 语言的知识查询机制，提供了象支持度、可信度这样的 客观标准，过滤掉被认为是不重要的知识。 1 7 山东大学硕士学位论文 可视化技术在许多领域已经取得了成功的应用，在模式分析中也起到了应有 的促进作用。数据可视化方法包括几何方法，层次化方法，基于图表的方法等。 几何方法着重于数据几何变化和投影过程的可视化，层次化方法把数据以层次化 方式划分成一系列的子空间。 1 3 3 国内外w e b 数据挖掘的研究现状 w e b 数据挖掘是当今的一个十分活跃的研究领域，近些年，许多重要的国际 学术会议都将w e b 数据挖掘作为一项主要的研究内容，国内外许多研究人员和机 构都把目光集中于这一方向上，使得w e b 数据挖掘的理论和方法不断得以发展， 一些w 曲挖掘原型系统和商业系统也相继闯世。 w b i 是i b ma l m a d e n 研究中心开发的中间件系统，支持w e b 服务器和浏览 器之间的信息流转换，能够提供多种w e b 个性化服务 2 9 1 。w e b s i f t ( w e bs i t e i n f o r m a t i o nf i l t e r ) 是美国m i n n e s o t a 大学和d e p a u l 大学开发的一个集w e b 内容 挖掘和使用挖掘结果于一身的个性化推荐系统0 1 ，i r a ( i n t e l l i g e n t r e c o m m e n d a t i o n a n a l y z e r ) 是i b mt j w a t s o n 研究中心开发的集内容过滤和协作 过滤于一体的智能推荐原型系统。该系统在推荐引擎的技术处理上独具特色，蕴 含了较高的技术含量，能直接与产品市场接轨【3 1 1 。w c p e n g 和m s c h e n 首次提 出了用户移动模式( m i n i n g u s e r m o v i n g p a t t e r n s ) 的概念，并提出了一个新的挖 掘方法用于挖掘用户的移动模式，最终改变移动系统的总体性能。w e b v i z 系统是 典型的模式分析工具，在w e b 模式可视化方面做了有益的工作。 目前国内的w e b 数据挖掘尚处于初期探索阶段，有影响的研究还不多见，但 考虑到w e b 数据挖掘的潜在应用价值以及相关技术还有很大的发展空间，必然会 有更多的力量投入到这项研究中来。 西安交通大学的刑东山、沈均毅等人提出了一个基于c o r b a 的分布式使用 挖掘系统，采用c o r b a 技术进行分布式处理，满足了一些挖掘结果实时表示的 要求。中国科学院计算技术研究所高文教授等人，提出了k - p a t h 路径聚类方法， 根据w e b 站点的用户访问兴趣进行用户划分。复旦大学的施伯乐、赵亮对匿名用 户w e b 浏览特征挖掘进行了研究，提出了一种基于会话的特征空间匿名挖掘模 型，同时满足分析用户的短期特征和长期特征。菲奈特一融通公司开发的b i b a n k 是针对银行业的一套商业智能解决方案，它利用数据挖掘、数据仓库及w e b 等核 心技术，为银行提供决策支持和c r m 管理，并实现信息的共享。 1 8 山东大学硕士学位论文 1 3 4w e b 数据挖掘研究中存在的问题 通过对现有成果的分析，可以看到目前w e b 数据挖掘研究中存在以下问题： ( 1 ) 现有w e b 使用挖掘的研究大都从模式发现的某个角度去对系统进行研 究，较少从系统的角度全面地对多种模式进行综合研究。 ( 2 ) 目前很多系统往往单一地采用传统的数据挖掘方法对w e b 进行挖掘， 得到的结果不能完全准确地反映用户的行为特征，有时规则数量过多，难以满足 用户进行决策分析的需求。传统的数据挖掘方法应用于w e b 数据挖掘时，应做相 应的改进。 ( 3 ) 人们往往用指向页面的超链接的数量来衡量w e b 文档的质量和重要性， 例如，某页面被指向的超链接越多，说明该页面的质量越好。但这并不是绝对的， 有的网页虽然被用户点击很多次，但它实际上可能只是通往目标网页的必经之路， 而并非用户真正想要浏览的对象，这些因素都应充分加以考虑。 ( 4 ) 需要进一步提高模式发现方法的实用性。由于w e b 数据挖掘处理的l o g 文件中的数据是海量数据，数据挖掘的效率显得特别重要。 1 4 本文的研究内容及结构安排 1 4 1 本文的研究内容 本文针对w e b 使用挖掘的理论与方法展开了研究，具体研究内容如下： ( 1 ) 数据预处理理论和方法研究预处理的目的是为模式发现阶段提供正确 完整的数据源，预处理过程是保证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 页面保存着对用户来说具有重要价值的信 息，这些信息反映了用户的访问规律和模式。当用户访问网站时，从一个页面游 1 9 山东大学硕士学位论文 历到另一个页面，相关的浏览信息被记录在网站服务器的日志文件中，例如用户 所使用的浏览器类型，用户从服务器上请求了哪些页面，用户在哪类网页的停留 时间较长等。通过对访问者的访问过程和浏览行为特征进行数据挖掘，可以发现 导航模式，获取隐含的知识，提高信息的重要性。 ( 3 ) w e b 聚类模式挖掘研究研究w e b 聚类中度量相似程度的方法以及页 面聚类和用户聚类的理论和方法。这方面的研究有利于为用户提供个性化的服务， 有助于网上营销及商业活动的开展。 1 4 2 本文的结构安排 根据本文研究内容，将结构安排如下： 第1 章绪论。本章阐述了w e b 数据挖掘和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 数据预处理 自动化程度。 第4 章用户访问路径模式挖掘。本章对现有的获得用户浏览模式的方法进行 了分析，在此基础上做了改进研究，提出了一种综合考虑支持度、页面浏览时间 和页面层次等因素的用户浏览模式挖掘方法。 第5 章w e b 聚类。本章在分析了w e b 聚类的特点以后，重点研究了聚类对 象相似程度的度量问题，研究了通过页面被用户使用的数量和页面链接距离来构 造w e b 相似矩阵的页面聚类方法，并提出了一种基于矩阵变换的w e b 用户聚类 方法。 第6 章结论。 山东大学硕士学位论文 论文的研究框架如图l - 4 所示。 图l - 4 论文研究框架 2 1 山东大学硕士学位论文 第2 章w e b 数据挖掘研究理论基础 w e b 使用挖掘是通过挖掘w e b 日志记录等源数据来发现用户的浏览行为和访 问w e b 的模式，获得潜在有用的知识的过程。它将传统的数据挖掘技术与w e b 相结合，其理论基础涉及数据挖掘等多个领域。本章从以下几方面阐述与w e b 使 用挖掘的模式发现直接有关的数据挖掘方面的理论和技术。 2 1 聚类 聚类是通过描述数据对象的一组属性，按照类问相似度最小，类内相似度最 大的原则，将无标识的对象划分成为不同的类属。聚类着重于发现数据的共性和 差异，并把具有相同的类别标识及共同特征的数据对象归入相应的类中。 聚类是数据挖掘中的一个活跃的研究领域，它与统计学、机器学习、生物学 等许多领域有着密切的联系。通过聚类分析。人们可以识别出数据对象相互关联 中最有价值的部分。聚类分析的应用极其广泛。在商业中，通过聚类可以从消费 者中区分出具有不同特征的消费者群，并给出每一类群体的消费模式，从而给商 家进行营销决策提供有力的指导，例如正确地细分产品市场和客户，挖掘潜在顾 客，提高顾客忠诚等。在网络信息中，通过聚类可以识别万维网中不同类型的文 档，挖掘出隐含的模式。聚类分析涉及到人类活动的方方面面，作为一种数据挖 掘技术，它帮助人们分析数据的分布，发现数据类的特征，在市场研究，模式识 别，空间数据库技术，数据分析等许多领域发挥了巨大的作用。 人们对聚类的研究己有相当长的历史。1 9 6 3 年，由r o b e r ts o k a l 等人著的 ( p r i n c i p l e so f n u m e f i c f lt a x o n o m y ) ) 一书对聚类的研究起了