（计算机应用技术专业论文）蚁群聚类算法在web使用挖掘中的应用研究.pdf

螭群聚典算法在w e b 使用挖冀i 中的皇l 用研究 蚁群聚类算法在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 使用挖掘已经成功应用 于个性化服务、提高系统性能和商业智能等领域。 本文首先介绍了w e b 使用挖掘的框架；数据预处理、模式发现、模式 分析和模式应用，详细地分析了目前应用于模式发现的各种方法及其存在 问题。接下来介绍了基于群体智能的蚁群聚类算法的四种模型，并将最有 优势的基于蚁堆聚类的蚁群算法引入w e b 使用挖掘。然后本文针对w e b 数据呈现的高纬、方向特性，将方向相似性度量与蚁群聚类算法相结合提 出一种基于方向相似性的蚁群聚类算法。实验结果表明，改进后的蚁群聚 类算法的聚类效果比经典的l f 算法要好，特别地，在方向性数据的处理 上，改进后的算法具有明显的优势。最后，将改进的算法应用于w e b 用户 聚类，针对w e b 的动态性，引入了用户兴趣更新和簇解体机制，实现了增 量式用户聚类。实验结果表明，该算法能动态有效地实现增量式用户聚类。 关键词：w e b 使用挖掘蚁群聚类算法方向相似性反应阈值增量 r i ，漳硬研究生论文蚊群鼍套算法在w e b 使用挖掘中的应用日完 t h er e s e a r c ho fw e bu s a g em i n i n gu s i n ga n t c o l o n yc l u s t e r i n ga l g o r i t h m a b s t r a c t w i t h r a p i dp o p u l a r i z a t i o n a n d a p p l i c a t i o n o fi n t e r n e t ，w e b i n f o r m a t i o ng r o w sa ta s t o n i s h i n gs p e e d h o wt of a s ta n de f f e c t i v e l y d i s c o v e r e dt h eu s e f u ii n f o r m a t i o nr e s o u r c eh a sb e c o m et h ep e n d i n gi s s u e a sa t e c h n o l o g yo fm i n i n gt h eu s e f u lk n o w l e d g ef r o mm a g n a n i m o u sw e b i n f o r m a t i o n ，w e bu s a g em i n i n gh a sr e c e i v e dw i d e s p r e a da t t e n t i o na ss o o n a si ta p p e a r e d w e b u s a g em i n i n gi so n eo f t h et h r e em a i nb r a n c h e so fw e bm i n i n g i tt a k e st h ew e bu s a g ed a t aa st h em i n i n go b j e c t ，e x p e c t e dt oa c h i e v et h e i n t e r e s t e d u s a g ep a t t e r n w e bu s a g em i n i n gh a sa l r e a d ya p p l i e d t o p e r s o n a ls e r v i c ea n db u s i n e s si n t e l l i g e n c e t h i sa r t i c l ef i r s t l yi n t r o d u c e st h ef a m eo fw e bu s a g em i n i n g ：d a t a p r e p r o c e s s i n g ，p a t t e r nd i s c o v e r y , p a t t e r na n a l y s i s ，p a t t e r na p p l i c a t i o n s ， a n da n a l y z e st h ee x i s tq u e s t i o no fm e t h o d su s i n gi np a t t e r nd i s c o v e r yi n d e t a i l s e c o n d l yi n t r o d u c e sf o u rk i n d so fm o d e lb a s e do na n tc o l o n y c l u s t e r i n ga l g o r i t h m ，a n da p p l i e sa l g o r i t h mb a s e do na n t - p i l i n gt ow e b u s a g em i n i n g o w i n g t ow e bd a t ah a v et h ec h a r a c t e r i s t i c so f h i g h d i m e n s i o na n dd i r e c t i o n ，w ec o m b i n ed i r e c t i o n a ls i m i l a r i t ym e a s u r e w i t ha n tc o l o n ya l g o r i t h ma n dp r e s e n tau e wa n tc o l o n y c l u s t e r i n g 广r 夫掌硬士研，巴j ；馆二乞h # 聚套算法在w e b 使用挖l 中，应月习| 究 a l g o r i t h mw h i c hn a m e d a n tc o l o n y c l u s t e r i n ga l g o r i t h m b a s e do n d i r e c t i o n a ls i m i l a r i t y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a ti tc a nc l u s t e r d i r e c t i o n a ld a t ae f f e c t i v e l y f i n a l l yw eu s et h en e wa l g o r i t h mt oc l u s t e r i n g w e bu s e r i nv i e wo f t h ed y n a m i cs t a t eo fw e b ，w eu s et w om e c h a n i s m so f r e n e w a lu s e ri n t e r e s t i n ga n dd e c o m p o s i n gc l u s t e r st oa c h i e v ei n c r e m e n t a l c l u s t e r i n g t h e r e s u l ts h o wt h e a l g o r i t h m c a n e f f i c i e n t l y a c h i e v e i n c r e m e n t a lc l u s t e r i n g k e yw o r d s ：w e b u s a g em i n i n g ；a n tc o l o n yc l u s t e r i n ga l g o r i t h m ； d i r e c t i o n a ls i m i l a r i t y ；r e s p o n s et h r e s h o l d ；i n c r e m e n t a l r 口夫掌q h ，c l * 二收霸l 景奥算法在w e b 使用挖掘中的矗【用研究 1 1 研究背景 第1 章绪论 数据挖掘( d a t am i n i n g ) 亦称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) ，是数据库和信怠决策领域的前沿研究方向之一。其目的是从大量的、不完 全的、有噪声的、模糊的、随机的数据中提取潜在的、不为人知的有用的信息、模式 和趋势。数据挖掘是多个研究领域的交汇点，其中包括数据库技术、统计分析、机器 学习、高性能计算和数据可视化技术等；同时它又是一项面向应用的研究，在商业领 域内有很多潜在应用。因此数据挖掘技术得到了学术界和工业界的广泛关注。从1 9 8 9 年数据挖掘概念提出直到现在，数据挖掘技术得到了快速发展，涉及的应用领域日益 广泛。 近年来，随着l i l t e m e t 在全球范围的迅速普及和应用，网络日益成为人们生活、 工作的重要组成部分。据估计，网络已经发展成为拥有3 亿页面的分布式数据空间， 而且这些数据仍以每4 到6 个月增长一倍的速度增加。在这些大量的、结构各异的 w e b 数据中，蕴含着巨大潜在价值的信息，如何快速、有效地发现这些信息资源已成 为亟待解决的问题。人们迫切需要一种能自动地从w e b 上发现、抽取和过滤信息的方 法和技术，w e b 挖掘( w e bm i n i n g ) 技术便应运而生。 从应用的角度来看，w e b 挖掘是应用数据挖掘技术从w e b 数据中发现有用模式的 过程。与传统数据挖掘的对象大都是结构化的数据库相比，w e b 挖掘的对象w e b 数据 具有非结构化、动态、不完全、混沌的特点和巨大、分层、多维的形式。按文献 1 】的 分类方法，w 曲数据主要分为三类： ( 1 ) 内容数据( c o n t e n td a t a ) ：它是提供信息的主体，包括文本、声音、图像和元 数据。内容数据主要以各种文档形式存在，譬如h t m l 文件和其他各种非文本的媒体 文件。内容数据的其他约定成俗的概念还有“w e b 文档”或者“w e b 页面”。 ( 2 ) 结构数据( s t n l c t u r ed a t a ) ：它是对内容数据组织而派生的数据。内容数据大 部分用h t m l 描述，超链接被广泛用于组织w e b 文档和w e b 文档内部的数据实体。 由此w e b 上就存在着由各种超链接形成的结构( 也包含超链接的描述) 。此结构又分为 站点结构和站问结构两部分。 ( 3 ) 使用数据( u s a g ed a t a ) ：它是用户使用w e b 而衍生的数据。w e b 是一个不受 时空限制的交互式媒介，可在多个层面上记录和收集因用户访问而产生的数据。典型 的方法是在w e b 服务器端收集w e b 日志，它包含了大量h t t p 协议层面的数据。 根据使用的w e b 数据类型，w e b 挖掘可分为三类：w e b 内容挖掘( w e bc o n t e n t m i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n g ) 和w e b 使用挖掘( w e bu s a g em i n i n g ) 。目前 国际上对w e b 使用挖掘的研究比较多【2 l 。 收l 置冀算法在w e b 使用挖j 中的应甩研究 w e b 使用挖掘的研究内容主要包括数据的收集与预处理、模式发现的方法和w e b 使用挖掘的应用等。其中模式发现阶段的方法主要有：统计方法，关联规则、序列模 式、分类和聚类等。但是前几种方法都有其自身上难以克服的缺陷：统计方法和关联 规则由于w e b 使用挖掘信息量十分巨大，其计算量是难以承受的；序列模式方法由于 强调访问模式的次序性，往往对数据过于敏感，导致发现的模式粒度小，数量大：分 类方法要从数据集中提取训练集进行训练，而训练集不能反映w e b 使用的动态变化。 由于上述方法的这些缺陷，使得聚类成为w e b 使用挖掘模式发现中的研究热点。 1 i 1w e b 使用挖掘中聚类算法的研究现状 聚类就是将物理或抽象的集合分成由类似的对象组成的多个簇的过程。由聚类所 生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇 中的对象相异。聚类通常用一个距离函数来衡量数据对象之间的相似度，并以此来决 定数据对象的分组。聚类技术已经被广泛的运用在w e b 使用挖掘中。 国外方面，文【3 】首先应用聚类的方法分析相似的用户组会话，并首次提出w e b 使用的挖掘由过去的单用户分析转移到用户组的分析上；文 4 】采用一种序列对齐方法 衡量数据对象之闻的相似度：文【5 提出了一个基于页面访问时间最长公共子序列的相 似图聚类算法；文 6 】通过使用遗传算法处理用户反馈信息来改善聚类结果；文 7 】结合 人工免疫系统和聚类技术提高用户信息的获得；文 8 】利用数据的多重特性构造了多模 式聚类的方法；文【9 】提出一个新的名为p i n g p o n g 算法的矩阵聚类算法，并将其应用 到w e b 存取日志中分析用户和页面之间的关系，解决了w e b 访问日志稀疏问题；文 1 0 】 聚类算法基于用户导航模式、隐马尔可夫模型( h i d d e nm m k o vm o d e l s ) 和用户其它信息； 文【1 1 1 将关联规则和聚类技术结合，提出了一个关联规则超图划分的算法。 国内方面，文 1 2 1 用决策树分类方法对w e b 用户进行分类；文【1 3 】应用关联规则 的方法来实现w e b 个性化服务；文【1 4 】则在w e b 使用挖掘上应用了模糊聚类算法；文 1 5 】将聚类分析方法结合关联规则推荐算法，应用于w e b 日志文件的挖掘；文 1 6 1 在 用户访问模式的聚类过程中引入页面的相似性因子，从用户访问的主要内容和访问路 径两个方面来度量访问模式的相似性，合理地降低了聚类结果的类别数目，能更准确 地发现一个网站的潜在用户类。 总的来说，目前在w e b 使用挖掘上应用的聚类方法主要有四类：( 1 ) k 均值聚类 算法及其改进方法；( 2 ) 模糊c 均值( f c m ) 聚类及其改进方法；( 3 ) 层次聚类方法； ( 4 ) 基于模型的聚类方法。 这些聚类方法还存在着以下问题：( 1 ) 需要先验知识如簇的个数( 1 【均值聚类算法) ； ( 2 ) 难以聚集有噪声的数据或不能聚集形状不规则的类：( 3 ) 对原始划分敏感，结果 易受到前期划分的影响( 层次聚类方法) ；( 4 ) k 均值，c 模糊均值和层次聚类在大规 2 ，r 夫学q i 女研究生| 论文蜕群聚典算法在w e b 使用挖鼻l 中的扈l 甩研究 模数据集上的效果并不理想；( 5 ) 基于模型的聚类方法不适用于数据空间纬数大于3 纬的数据。 1 i 2 蚁群聚类算法的研究现状 蚁群算法是近年来诞生的一种基于群体智能的算法，在若干领域已取得了成功的 应用。例如其在解决组合优化的问题( 如t s p 、q q p 、j o b s h o p 调度等) 上获得了比较理 想的效果：此外，其在一些实际问题的应用也取得一定的进展，如大规模集成电路综 合布线以及网络数据包的路由。随着蚁群算法研究的兴起，人们发现在某些方面采用 蚁群模型进行聚类更加接近实际聚类问题，其在w e b 使用挖掘中的应用正逐步引起人 们的关注。 文 1 7 1 最早提出了基于蚁堆的聚类模型；文 1 8 1 改进了文【1 7 】模型，提出了l f 算 法，并首次应用于数据分析；文 1 9 2 2 1 在l f 算法上，模拟了真实蚂蚁的移动方式， 减少了人工蚂蚁在无数据区域的搜索。文【2 3 】模仿多蚁群的协作性能，将运动速度类 型各异的多个蚁群，独立而并行地进行聚类分析，然后组合其聚类结果为超图，再用 蚁群算法对超图进行2 次划分；文 2 4 】在l f 算法中引入信息熵，改变了拾起放下规则， 力快了聚类速度，减少了参数设置。 随着蚁群聚类算法研究的进一步发展，其他类型的蚁群聚类算法被相继提出。文 【2 5 - 2 7 1 提出了一种基于蚂蚁化学识别系统的蚁群聚类模型，该模型模拟蚂蚁的生理机 制，依靠神经元模板和气味来识别另外的蚂蚁是否和自己是同一个群体的；文 2 8 1 提 出一种基于蚂蚁自我聚集行为的聚类模型，该模型用蚂蚁表示数据并代表该树的节点。 蚂蚁在这棵树上或已经固定在树上的蚂蚁身上移动，来寻找适合自己的位置，最终形 成一棵蚂蚁树：文【2 9 】提出了一种基于蚂蚁觅食原理的蚁群聚类模型，该模型假设数 据为具有不同属性的蚂蚁，聚类中心是蚂蚁所要寻找的“食物源”，那么数据聚类过程 就可以看作蚂蚁寻找食物源的过程。 在这些蚁群聚类模型中，蚁堆聚类模型提出最早，理论最完善，应用也最广泛， 其他的蚁群聚类模型由于提出较晚，处于理论完善和初步应用阶段。 1 2 本文工作 1 2 1 研究内容 数据预处理技术、模式发现的方法，w e b 用户聚类是w e b 使用挖掘领域中的重要 研究内容。本文分析了其中一些重要问题，提出了相应的解决方法。概括起来，本文 研究的主要内容为以下两个部分： ( 1 ) w e b 使用挖掘中的聚类分析。聚类是模式发现的一种重要方法，w e b 使用 挖掘的聚类可分为页面聚类和用户聚类两种。聚类结果可用于个性化服务的设计，系 r r 夫掌日_ ，b 生论文蜮群粟羞i 算涪在w e b 使用挖掘中的应用研究 统性能的提高。使用传统的聚类算法进行模式发现存在诸多问题，往往导致模式发现 低效或者不能发现模式。另外，如何比较数据之间的相似性是聚类分析表示常遇到的 问题。传统的相似性度量方法不能很好地表示w e b 数据之间的相似性。而且，聚类时 仅考虑数据的相似性是片面的。本文研究了更具聚类优势的蚁群算法，根据w e b 数据 具有高维、不区分大小的特点，尝试将方向性数据的知识引入到w 曲数据的相似性计 算当中，另外，在比较相似性的同时考虑形成簇的数量因素，用以提高最终的聚类效 果。 ( 2 ) w e b 用户聚类。在w e b 用户聚类中，通常用访问兴趣来表示用户，这种兴 趣表现在用户对网页的点击频率。传统的方法将每个页面代表一个兴趣，导致用户兴 趣粒度太小且分散。另外，w 曲的动态性也增加了正确聚类w e b 用户的难度。本文研 究了更为合理地表示w e b 用户的策略及在w e b 动态性下正确聚类w e b 用户的算法。 1 2 2 本文贡献 本文的主要贡献如下： ( 1 ) 提出了一种基于方向相似性的蚁群聚类算法。该算法引入了新的数据度量方 法，在决定人工蚂蚁聚类动作时考虑了形成簇的数量因素。实验结果表明此算法比原 有蚁群聚类算法具有更好的性能，特别适合高维的w e b 使用数据聚类。 ( 2 ) 提出一种基于蚁群聚类模型的增量式w e b 用户聚类方法。该方法首先应用 了合并兴趣组策略表示w e b 用户，然后在用户兴趣更新和簇解体策略的基础上，应用 改进的蚁群聚类算法实现了增量式w e b 用户聚类。实验结果表明，该方法能动态有效 地实现w e b 用户聚类。 1 3 本文结构 本文的余下部分组织如下：第二章概述了w e b 使用挖掘的四个主要阶段及其使用 技术和方法。第三章介绍了四种基于蚁群的聚类模型，通过分析了它们的优缺点，选 择最有优势的蚁堆聚类算法应用于w e b 使用挖掘的聚类分析。第四章针对w e b 使用 数据的特点将数据的方向性度量引入蚁群聚类算法，提出了一种基于方向性度量的蚁 群聚类算法，并给出一个较为全面的性能实验分析。第五章针对w e b 用户兴趣的分散 性和w e b 的动态性的难题，在w e b 用户聚类过程中引入合并兴趣组、用户兴趣更新 和簇解体等策略，应用改进的蚊群聚类算法实现了增量式的用户聚类。第六章总结全 文，指出本文的后续研究方向。 4 h o 覃奥算法在w e b 使用挖中的应用日完 第2 章w e b 使用挖掘概述 w e b 使用挖掘的定义是数据挖掘技术应用在大型w e b 资源中以分析w e b 站点的 使用1 3 0 ，这个定义已获得广泛的应用。w e b 使用挖掘主要包含了数据预处理( d a 诅 p r e p r o c e s s i n g ) 、模式发现( p a t t e r nd i s c o v e r y ) 、模式分析( p a t t e r na n a l y s i s ) 和模式应用 ( p a t t e m 印p l i c a t i o 璐) 四个阶段3 1 1 。图2 - 1 给出了一个w e b 使用挖掘的一般过程。 源数据一 用户_ 皇孽嘉规则、模式。 w e b 事务文件一 ”一一 有实际意义的 规则、模式p 数据预处理一模式发现一模式分析p 2 1 数据预处理 图2 - 1w e b 使用挖掘过程 f i 9 2 - 1t h ep r o c e s so f w e bu s a g em i n i n g w e b 使用挖掘的数据源主要来自于服务器端( s e r v e r ) 、客户端( c l i e n t ) 和代理端 ( a g e n t ) ，客户端的数据通常反映单用户多站点的访问行为；服务器端的数据则描述 了多用户单站点的访问行为：而代理端的数据则记载了多用户多站点的使用情况。 这些数据通常是以日志的形式保存的，从不同数据源收集来的日志结构差别较大。 w e b 使用挖掘首先要对这些挖掘数据进行预处理，其目标是将包含在多种数据的 信息转化为适合数据挖掘和模式发现所必需的数据抽象概念，然后在事务数据库上实 施挖掘算法，以期最终获得有价值的规律。数据预处理是w e b 使用挖掘模式发现阶段 质量保证的关键。预处理的过程一般包括数据清洗( d a t ac l e a n i n g ) 、用户识别( u s e r i d e n t i f i c a t i o n ) 、会话识另l j ( i d e n t i f ru s c rs e s s i o n ) 、事务识，j l j ( t 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 hc o m p l e t i o n ) 等步骤【3 2 训。 ( 1 ) 数据清洗。数据清洗就是删除w e b 日志记录中与数据挖掘不相关的数据， 把w e b 日志转化为适合数据挖掘的可靠的精确数据。典型的w e b 日志记录了包括用 g - r 大掌h 究生论文 收群聚奥算法在w e b 使用挖舅l 中的量0 甩研究 户i p 地址、用户i d 、请求访问的u r l 页面、请求方法、访问时间和日期、传输协议、 传输的字节数、错误码、参照页( r e f e r r e r ) 和用户代理( a g e n t ) 等属性。而与数据挖掘有 关的数据只有用户i p 地址，用户i d 、请求访问的u r l 页面和访问时间，其它属性可 以去掉。u r l 页面中用户关心的是正文，其它辅助信息内容( 如图像、声音、视频等) 均可去掉。挖掘w e b 日志的目的是找出用户的共同访问模式，并不关心那些用户没有 请求的文件，关于辅助信息的记录是无用的，可以通过检查u r l 的后缀删除之。如将 日志中文件的后缀名为g i f 、j p e 、j p g 、c g i 、m a p 的项删除。 ( 2 ) 用户识别。用户识别是将用户和请求的页面相关联的过程，其区分办法有如 下几种情况：如果用户的i p 地址不同则认为是不同的用户；如果i p 地址相同但浏览 器软件或操作系统不同，则认为是不同的用户；将访问日志和引用日志与站点的拓扑 结构结合，可构成用户的浏览路径，如果发现用户正在请求页面，又不能从已访问的 任何页面到达，则认为是新用户；如果请求的用户不包含服务器的c o o k i e s ，则认为 是新用户。 ( 3 ) 会话识别。会话是指同一个用户连续请求的页面。不同用户访问的页面属于 不同的会话。用户识别出来之后，就要把每个用户在一段时间内的点击流( 所有的请求 页面) 分解为单个的会话。最简单的方法是利用时间戳( t i m e o u t ) ，如果用户访问的时间 差超过了时间戳，则认为用户开始了一个新的会话。通常默认的时间闽值为3 0 分钟， 但文献 3 5 1 的实验证明，比较合理的时间阈值是2 5 5 分钟。 ( 4 ) 事务识别。事务识别面向以事务为单位的应用，是指将页面访问序列划分为 代表w e b 事务或用户会话的逻辑单元。和用户s e s s i o n 识别不同的是，它以事务为单 位，只包含与事务相关的页面。识别事务比较常用的方法是最大向前引用路径。最大 向前引用路径基于这样的假设：用户访问过程中只有在改变访问主题时，才会返回前 面访问过的页亟以跳转到另外的页面。对于每个用户会话，从开始页面为起点，每个 最大前向引用路径即为一个事务。 ( 5 ) 路径补充。路径补充就是将由于使用本地缓存或代理服务器缓存所遗漏的请 求页面补充完整。一般客户端利用网页缓存进行浏览有三种方式，最常见的一种是利 用“b a c k ”按钮进行后退；第二种是点击一个已经浏览过的链接；第三种是直接从浏 览器的历史列表中点击一个链接。在无法从客户端进行网页浏览跟踪的情况下，如果 一个页面请求信息与该用户上次请求的页面没有直接的链接关系，可以查看参考日志 文件来决定这个页面来自哪个页面的链按。也可以借助网络拓扑结构的信息，将服务 器访问日志文件中一些未扫描的信息补充完整。 2 2 模式发现 模式发现阶段就是利用挖掘算法挖掘出有效的、新颖的、潜在的、有用的及最终 可以理解的信息和知识。模式发现可以采用众多领域的方法和算法，如统计学、数据 6 h 群聚粪算洛在w c b 使用挖l 中的盘用日完 挖掘、机器学习、模式识别等。但从其它领域移植到w e b 挖掘领域的技术还需要考虑 到原有领域与w e b 挖掘领域数据类型或先验知识的差异。例如，原来用于市场分析的 关联规则发现中，并不考虑数据项之间的先后次序问题，而在w e b 使用挖掘中，一个 服务器会话就是一个用户所请求网页的排序序列，不同的序列。因此，相关技术必须 针对w e b 挖掘领域的特点做出相应的修改和完善才能实现成功的移植。模式发现采用 的主要方法有：统计分析、关联规则、序列模式、依赖性建模、路径分析、分类和聚 类。 ( 1 ) 统计方法。统计方法是从w e b 中提取有用信息最常用的一种技术。通过对 s e s s i o n 文件的分析，可以对感兴趣的信息进行统计，一般的包括各种统计数据，如最 频繁访问的n 个页面、每页平均浏览时间、网址路径平均访问长度等，也可能涉及一 些关于限制的错误分析，如统计非法i p 、无效u r l 和未授权访问等。这些信息对于 提高系统性能，加强网站安全起到辅助决策作用1 3 l 】。 ( 2 ) 关联规则。关联规则主要关注事务内的关系，它通过量化的数字，描述事务 a 的出现对事务b 的出现有多人的影响。在w e b 使用挖掘中，关联规则主要用于发现 用户之间、页面之间以及用户浏览页面和网上行为之间存在的潜在关系【3 6 ，3 7 1 。例如， 用a p n o d 算法【3 8 】发现关联规则有可能发现访问包含电子产品的网页的用户和访问有 关体育用品的网页的用户之间存在一定的联系。a p f i o f i 算法是挖掘关联规则的常用技 术，可从事务数据库中挖掘出最大频繁访问项集，该项集就是关联规则挖掘出来的用 户访问模式。除了商业和市场营销方面的应用之外，这类规则发现还有助于网站设计 者重新组织和设计w e b 站点的结构。由于一般网站的用户访问序列数据库其数据量都 很大，目前的关联规则挖掘技术都是致力于降低搜索空间。 ( 3 ) 序列模式。序列模式发现技术试图找出会话间的模式，即一组数据项之后出 现另一数据项，从而形成一组按时间顺序的会话【3 9 l 。在网站服务器日志中，用户的访 问是以一段时间为单位记载的，经过数据精简和事件交易确认以后是一个间断的时间 序列。在电子商务运作中，w e b 市场分析员根据挖掘出的序列能预测出用户未来的访 问模式，这将有助于针对特定用户群来安排广告。其它类型的空间序列模式还可用于 诸如趋势分析、转折点检测和相似性分析。 ( 4 ) 依赖性建模。依赖性建模的目标是开发出一种能表达w e b 领域中各种变量 之间的显著依赖性的模型。例如，在网上商店中一个用户从经常访问的常客到潜在的 购买者的行为选择过程，也许会经历几个不同的阶段。构造一种模型来表达这种过程 有助于分析用户所处的阶段并对其行为进行有效引导。有好几种概率学习方法可以用 来为用户的浏览行为建模，如隐马尔可夫链模型、贝叶斯信念网络等。w e b 使用模式 的建模不仅能为分析用户行为提供理论框架，还具有预测w e b 资源消耗的潜力。这类 信息对设计增加网上产品销量的策略，以及改进用户导航的便利性都将起十分重大的 作用。 7 广酉 掌日，e 生馆文 h 群景鼻算法在w e b 使用挖掘中的矗l 用完 ( 5 ) 路径分析。一个w e b 网站网站的拓扑结构可以看成一幅有向图，图的顶点 是网站中的页面，边是页面之问的超级连接。该图代表了定义在网站l 的页面之问的 联系。在w e b 使用挖掘中，用户在一段时间内的访问模式为其子图。具有相似访问子 图的客户为需求相似的用户，此即用户群体聚类。用户访问频繁的有向边则为频繁路 径。基于w e b 使用挖掘的数据挖掘，就是要从图中确定最频繁的路径访问模式或大 参引访问序列。文献【加j 从原始日志数据中导出最大向前引用序列m f r 的过程，实际 上就是在构造用户的访问子图。路径分析可以用来确定网站上最频繁的访问路径，从 而调整站点的结构。 ( 6 ) 分类。分类是一个两步过程。第一步建立一个模型，通过模型对训练数据的 分析，给出预定数据集或概念集的特征描述；第二步抽取未知数据对象的自身特性， 根据模型中的定义，将其划分到相应的类别中。在w e b 使用挖掘中，分类技术可以根 据访问用户而得到的用户的个人信息或从共同访问模式得出访问某一服务器文件的用 户特征。另外，通过用户注册表和在线调查表也可得到用户的一些特性。但根据用户 注册信息对用户进行分类，需要抽取和选择出最好地描述类别属性的特征。分类方法 有许多种，常使用的监督归纳学习算法，如决策树分类器、原始贝叶斯分类器、k 近 邻分类器等。 ( 7 ) 聚类。在w e b 使用挖掘领域中，存在两种类型的聚类：用户聚类和页面聚 类。用户聚类就是将那些经常访问相同页面的用户群划分出来，他们具有相同的使用 习惯和网上行为，可以对他们开展特定的广告策略或是个性化定制。页面聚类则发现 内容相关的页面组，为搜索引擎和w e b 服务商提供有用信息。上述两类应用都能根据 用户的询问或历史信息来生成静态或动态h t m l 页，从而向用户推荐相关的链接。 2 3 模式分析 模式分析是w e b 使用挖掘中的另一个重要步骤。模式分析主要是为了从模式发现 算法找到的模式集合中筛选出有趣的模式。如果没有合适的工具和机制来辅助分析人 员的理解，采用各种技术挖掘出来的模式，数目庞大，表达晦涩，从而得不到很好的 利用。精确的分析方法通常是由w e b 使用挖掘的具体应用来控制的。常用的模式分析 方法主要包括：统计、图形可视化、可用性分析和智能查询等p 4 1 。 ( 1 ) 可视化技术。可视化良好的系统用图形和图像表示抽象网络中错综复杂的关 系；用文字描述解释和阐述模式之间相互的作用，帮助人们更好地理解w e b 中海量数 据各部分之间的关系，指导和加速查找的过程。文献1 4 1 1 开发出了一个可视化w w w 访 问模式的w e b v i z 系统。该系统提出了在一个w e b 路径聚合体中服务器登录项被用于 抽取称为w e b 路径的w e b 访问模式结果。w e b v i z 允许分析人员有选择性地分析感兴 趣的w e b 部分而过滤掉不相关的部分。w e b 被可视化为一个带环有向图，其中节点 是网页，而边是网页之间的超链接。 ，。r 大掌弓e - 士研，c 生制 ，镕群曩鼻算法在w e b 使用挖l 中应用研究 ( 2 ) 联机分析处理工具o l a p ( o n - l i n ea n a l y t i c a lp r o c e s s i n g ) 1 4 ”。o l a p 在基于 多维数据模型的数据仓库或数据集市上使用，目标是满足决策支持或者满足在多维环 境下特定的查询和报表需求，它将传统数据以多维数据模型重新组织，然后通过上卷、 下钻、切片和切块、旋转等操作实现对多个抽象层上的知识发现。w e b 服务器上的访 问数据随时间呈海量增长趋势，而且用户信息的数据存储也呈现分布的趋势，这两个 特性表明了w e b 使用数据的分析通常需要大型数据仓库的支持，o l a p 技术就是在其 上发展出的技术。它整理信息的结构，允许基于主题对数据进行查询和分析，快速完 成报表和数据分析功能，使分析人员或管理人员能够从多角度对信息进行快速、一致、 交互地存取，这些与可视化工具一起，将大大增强探测式w e b 使用挖掘的能力和灵活 性。这一新兴领域的问题，已引起研究人员的广泛关注，有待进步的讨论和发展。 ( 3 ) 知识查询机制】。知识查询机制首先分析查询目的，然后自动搜索相关的 规则、模式以及其它的知识，可以帮助分析用户日的，用智能的方式回答查询。这样， 它不仅可以直接列出用户所指定属性的项目列表，还可以向用户提供辅助决策的附加 信息。另外，模式的大量聚集常常使用户不知所措。有必要定义一些机制，使用户可 以将焦点聚集在某些感兴趣的细节上。达到这一目的的途径有两个：一是在挖掘之前， 在数据库上设置约束，使挖掘只在一部分数据中进行；二是挖掘过程中执行查询语句。 不断筛选出需要的信息，将无用的数据过滤掉。研究人员已经在s q l 语言的基础上提 出几种适合在数据挖掘过程中使用的查询语言，如d m q l ；也有专门为w e b 挖掘而定 义的w e b s s q l ，w e b l q m 和s q u e a l 等。 2 4 模式应用 模式发现的结果可以客观反映w e b 的组成、内容和访问频度等重要信息，也能帮 助理解用户的网上访问行为。利用这些信息，可以建立如下几个方面的应用； ( 1 ) 对客户的个性化服务与定制。目前主要有三个方面：1 ) 个性化网站。强调信 息个性化，即识别、建立、调整客户的喜好，使客户能以自己的方式来访问。人们越 来越希望网页的内容能够从原先的以“网站”为中心转变成以“用户”为中心，尽可 能地自动调整以迎合每个用户的浏览兴趣。个性化网站建设在现在研究和和作为目的 的应用都是一个具有挑战性的领域。2 ) 个性化广告。当我们打开一个网站时，可能会 弹出我们不需要的广告，这使消费者心烦意乱，而且浪费他们宝贵的时间和精力。个 性化广告就不同，它针对我们需要提供广告，使我们减少搜索的时一间，得到想要的 东西。有针对性的提供个性化广告条，对那些要通过w w w 发送广告的企业，提供个 性化的广告服务要比泛泛的、随意的广告有价值得多。3 ) 在线推荐( o n l i n e r e c o m m e n d a t i o n ) 产品或网页。是根据网络访问者的偏好和导航行为个性化营销。把活 动用户的短期访问历史与前面挖掘的模式进行匹配，为活动用户预测下一步最有可能 访问的页面，并根据得分对页面进行排序后，附在现行用户请求访问页面后推荐给用 9 广r 掌女日，l 生论】t蚁群鼍典算法在w e b 使用挖囊中各应用研究 户】。 ( 2 ) 提高系统性能。对于网络服务提供商来说，用户满意度将是重要的指标：而 对于用户来说，服务质量和服务器性能是关键。w e b 使用挖掘向网站建立者提供了各 种关于网站架构的信息，也提供了用户在使用网站时的习惯。那么，网络管理员可以 在w e b 缓存、网络结构安排、负载平衡和数据分布上进行统筹。 自适应网站是指能根据用户的访问模式自动或半自动地学习和调整自身组织架构 的网站。它使用索引页( i n d e xp a g e ) 合成技术进行快速导航，所谓索引页就是包含了所 有覆盖某个特有主题页面集链接的页面。那么，用户从索引页上就可以轻而易举地获 得自己想要的信息。首先，网络管理员对网站中的每一页所表述的内容做概念上的描 述，然后将这些描述和w e b 日志文件一同输入到系统中。然后，索引构造软件自动处 理大量的用户使用数据，并能给网络管理员提供有关网络内容和结构的有用信息。这 个软件包含三个基本的模块：1 ) e l 志处理模块统计日志文件中的各项参数；2 ) 聚类挖 掘模块将这些信息和网络的拓扑结构联合起来，找出频繁的同时被访问的页面集；3 ) 概念聚类模块从这些页面的概念描述中找出最一般的描述，一起生成候选索引页( 包括 主题) ，提供给网络管理员作选择。一旦网络管理员做出决定，则将最终版本的索引页， 提供给用户。这样，索引页的内容根据用户的历史记录和当前访问不断自我调整，以 达到自适应的能力。在网络管理员的有效指导下，用户可以使用一个不断更新，满足 需要的动态网站；而事实上，网站的物理结构无须大动干戈地重新组织，不仅提高了 系统性能，也节约了资源和成本。 ( 3 ) 商业智能。w e b 使用挖掘对大量用户使用记录的分析，能够为服务商分析 用户行为提供商业智能，使服务商更方便的实施客户关系管理。w e b 使用挖掘对商业 智能的研究主要有以下几个方面： 1 ) 分析潜在的目标市场、优化电子商务网站的经营模型：根据客户的历史资料 不仅可以预测需求趋势，还可以评估需求倾向，有助于提供企业的竞争力。 2 ) 聚类客户：在电子商务中客户聚类是一个重要的方面。通过分组具有相似浏 览行为的客户，并分析组中客户的共同特征，可以帮助电子商务的组织者更好地了解 自己的客户，向客户提供更适合、面向客户的服务。销售商根据分析出来的聚类信息 及时调整页面及页面内容，使商务活动能够在一定程度上满足客户的要求，使商务活 动对客户和销售商来说都更具意义。 3 ) 确定消费者消费的生命周期，针对不同的产品定制相应的营销策略。 4 ) t 解客户，针对不同客户提供“量身定做”的产品。电子销售商可以获取消 费者的个人爱好，更加充分的了解客户的需要，给每一个消费者的独特需要提供个性 化的产品。有利于提高消费者的满意度，使消费者成为长久的客户。 5 ) 延长客户的驻留时间。对客户来说，传统客户与销售商之间的空间距离在电 子商务中已经不存在了，i n t e m e t 上每一个销售商对于客户来说都是样的。通过对客 1 0 7 - i r 大学日r 日究论文h # 聚套算涪在w e b 使用挖 中的应用研究 户访问信息的挖掘，就能知道客户的浏览行为，从而了解客户的兴趣及需求。在i n t e m e t 上的电子商务中的一个典型序列，恰好就代表了一个消费者以页面形式在站点的导航 的行为，所以可运用数据挖掘中的序列模式发现技术。 6 ) 发现潜在用户：对一个电子商务网站来说，了解、关注在册客户群体非常重 要，但从众多的访问者中发现潜在客户群体也同样非常关键。如果发现某些客户为潜 在客户群体，就可以对这类客户实施一定的策略，使他们尽快成为在册客户群体。对 一个电子商务网站来说也许就意味着订单数的增多、效益的增加。 2 5 本章小结 本章系统地介绍了w e b 使用挖掘的框架及其四个阶段：数据预处( d a t a p r e p r o e e s s i n g ) 、模式发现( p a t t e r nd i s c o v e r y ) 、模式分析( p a t t e r na n a l y s i s ) 和模式应用 ( p a t t e r na p p l i c a t i o i l so 重点分析了目前应用于w e b 使用挖掘模式发现阶段的各种技术 和方法。 广i 掌【m 完生论：r 群鼍鼻算法在w e b 健用挖i l 中的应月研究 第3 章蚁群聚类算法概述 群体智能作为一个新兴领域，自从2 0 世纪8 0 年代出现以来，引起了多个学科领 域研究人员的关注，已经成为人工智能以及经济、社会、生物等交叉学科的热点和前 沿领域。由单个复杂个体完成的任务可由大量简单的个体组成的群体合作完成，而后 者往往更具有健壮性、灵活性和经济上的优势。群体智能( s w 锄i n t e l l i g e n c e ) 利用群体 优势，在没有集中控制，不提供全局模型的前提下，为寻找复杂问题解决方案提供了 新的思路。对群体智能的定义进行扩展，普遍意义上可以理解为由一组简单智能体 ( a g e n t ) 涌现出来的集体的智能( c o l l e c t i v ei n t e l l i g e n c e ) ，其中蚁群聚类算法最具有代表 性。 蚂蚁是一种最古老的社会性昆虫，它的起源可追溯到一亿年前，大约与恐龙同一 时代。在漫长的发展历史中，蚂蚁形成了成千上万种类，占据了几乎每一片适于居住 的土地，只有永远雪封的南北两极未曾被涉足。虽然蚂蚁种类繁多，但无一是独居的， 都是群体生活，建立了自己独特的蚂蚁社会。蚂蚁的个体结构和行为很简单，单个工 蚁能做的各种动作不超过5 0 个，其中大部分是传递信息，但由这些简单的个体所构成 的整个群体一蚁群，却表现高度结构化的社会组织，在很多情况下能够完成远远超出 蚂蚁个体能力的复杂任务。蚂蚁社会中的个体从事不同的劳动，群体可以很好地完成 个体的劳动分工。作为社会昆虫的一种，蚂蚁成员除有组织有分工之外，还有相互的 通讯和信息传递。蚁