2 相关知识基础
文档的摘要。目前，绝大部分搜索引擎采用的方法是简单地截取文档的前几行。也有使用中心文档代表文档集合，使用中心词汇表示文档的方法。
2）、Web多媒体挖掘
Web多媒体挖掘(Multimedia Mining)就是基于Web多媒体的内容特征以及这些特性相关的语义，从大型Web多媒体数据集中发现和分析出隐含的、有效的、有价值的、可理解的模式。Web多媒体挖掘主要有Web多媒体图像挖掘和Web多媒体文本挖掘。Web多媒体图像数据挖掘的方法很多，如多媒体图像数据的相似性搜索、多维分析、关联规则挖掘、分类与聚类分析等。
Web内容挖掘可以对Web上大量文档集合的内容进行摘要、分类、聚类、关联分析，以及利用Web文档进行趋势预测等。Web内容挖掘的重点是页面的分类和聚类，Web页面的分类是根据页面的不同特征，将其划分为事先建立起来的不同的类。Web页面的聚类是指在没有给定主题类别的情况下，将Web页面集合聚成若干个簇，并且同一簇的页面内容相似性尽可能大，而簇间相似度尽可能小。
（2）、Web结构挖掘
WWW是由分布在世界各地的Web站点组成的全球信息系统，每个Web站点又是一个由许多Web页面构成的子系统。Web页面并不是孤立存在的，相关的文档之间通常有超链接链接，超链接体现了文档之间的逻辑关系，同时为用户浏览Web站点提供了可用的路径[20]。
Web结构挖掘主要是对Web文档之间的结构和链接关系进行挖掘，这种结构挖掘尤其应用于Web文档结构。在Web文档空间里，有用的知识不仅包含在Web页面的内容之中，而且也包含在页面的结构之中。例如，当一个页面经常被引用或一个页面引用大量其它页面，那么这个页面一定非常重要，发现的这种知识可以被用来改进搜索引擎，并且由此可以获得有关不同网页间的相似度及关联度的信息。
目前对Web超级链接结构进行分析的主要方法是将Web对应成有向图或无向图的形式，然后根据一定的启发规则，用图论的方法对其进行分析。Web结构挖掘主要应用于WWW上的信息检索领域，可以指导搜索引擎的网页采集，因为网页链接分析为判断网页的质量提供了一种方式，帮助搜索结果排序。
（3）、Web使用挖掘
Web使用挖掘（也称为Web用户访问模式挖掘），Web内容挖掘和Web结构挖掘的挖掘对象是网上的原始数据，而Web使用记录挖掘面对的则是在用户和Web交互的过程中发现用户访问模式，并抽取感兴趣的模式，包括网络服务器访问记录、代理服务器日志记录、用户对话或交易信息、用户提问方式等[21]，
11
工程硕士学位论文
WWW中的每个服务器都保留了访问日志(Web Access Log)，记录了关于用户访问和交互的信息。
Web访问挖掘一般分为两种：一般访问模式跟踪和定制使用跟踪，一般访问模式跟踪通过分析Web日志来理解用户的访问模式和倾向；定制使用跟踪分析单个用户的偏好，根据其访问模式为每个用户定制符合个人特点的Web站点。
对日志数据挖据采用的算法有：路径分析、关联规则和序列模式的发现以及聚类分析等，Web访问挖掘主要的应用是：个性化、系统改进、站点修改、商业智能和页面推荐等。
表2-1显示了Web三种挖掘方法的就数据源、表示方法、处理方式以及应用等方面进行比较：
表2-1 Web挖掘的三种方法比较
Table 2-1 Three methods comparison in Web mining 处理数据类 型 主要数据 Web内容挖掘 信息检索IR方法 数据库方法 Web结构挖掘 Web结构挖掘 文档内及文档间的超链接 图 Web访问挖掘 Web访问挖掘 服务器日志、客户日志、代理服务器日志 关系表、图 结构化与半结构化数据 半结构化数据 自由文本、HTML标记的超文本 HTML标记的超文本 目标交换关系 表示方法 词集、段落、概念及信息检索的模型 处理方法 统计、机器学习、自然语言理解 数据库技术 模式发现、数据向导、多维数据库 机器学习 页面权重分类聚类、模式发现 统计、机器学习、关联规则 用户个性化、自适应Web站点、商业决策 主要应用 分类、聚类、模式发现 2.3 Web挖掘的过程 (The Web Mining Process)
Web使用挖掘的过程一般分为三部分，预处理阶段、模式发现、模式分析阶段。图2-2显示了Web使用挖掘的过程[22]。
图2-2 Web访问信息挖掘的过程 Figure 2-2 Process of web usage mining
Web服务器日志 预处理 模式发现 预处理后的数据 模式和规则 模式分析 潜在的知识和规则 12
2 相关知识基础
源数据收集在Web日志挖掘中，数据最直接的来源是Web服务器。客户访
问服务器就会在服务器上产生相应的服务器数据，这些数据可以分为日志文件和查询数据。
2.3.1 数据预处理
由于原始日志文件是简单的文本文件,包括了一些不完整的、冗余的、错误的数据,同时原始Web 日志文件具有半结构化的特点,于是需要对原始日志文件进行预处理,否则将影响挖掘的效果。Web日志预处理是在进行Web日志挖掘前，对Web日志进行清理、过滤以及重新组合的过程。Web日志预处理的目的是剔除日志中对挖掘过程无用的属性及数据，并将Web日志中的数据转换为挖掘算法可识别的形式。目前，常用的数据预处理技术包括：数据净化、数据集成和数据约束，其中数据净化可以去掉数据中的噪声，纠正数据的不一致性；数据集成将多个数据源合并成一致的数据存储；数据变换，规范化可以改进涉及距离度量的数据挖掘算法的精度和有效性；数据规约可以通过聚集、删除冗余特性或聚类等方法来压缩数据。这些数据预处理技术在数据挖掘之前使用，可以大大提高数据挖掘模式的质量，降低实际挖掘时所需要的时间和空间。
数据预处理技术可以改进数据的质量，有助于提高其后的挖掘过程的精度和性能。因此高质量的决策必须依赖于高质量的数据，数据预处理是知识发现过程的重要步骤，在第三章中就如何进行数据的预处理还会详细的介绍。
2.3.2 模式发现
模式发现就是用户访问模式的发现，采用了来自人工智能、数据挖掘、信息论等领域的成熟技术，从Web使用记录中挖掘知识。在对数据预处理后得到事务集，就可以根据具体的需求选择访问模式发现的技术，如路径分析、关联规则挖掘、时序模式、聚类和分类技术。路径分析可以用来发现Web站点中最经常被访问的路径，从而帮助管理员调整站点的结构。在Web使用记录挖掘的环境下，关联规则挖掘的目标是发现用户对站点各页面的访问之间的关系，这对于电子商务是非常有用的。各种聚类和分类技术的采用对于Web使用记录中的模式发现都有其各自的作用。
Web使用挖掘的相关算法[23]： （1）、关联规则 (Association Rules)
关联规则挖掘是数据挖掘中最活跃的研究方法之一，同时也是数据掘研究的主要模式之一。最早是由Agarwal等人提出[24]，最初是针对购物篮分析(Basket Analysis) 问题提出的，其目的是为了发现交易数据库(Transaction Database)中不同商品之间的联系规则。通过对交易数据库中数据的智能分析，可以获得有
13
工程硕士学位论文
关顾客购买模式的一般性规则。这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货、库存以及货架设计等。关联规则最经典的是：啤酒与尿布的问题。
关联规则是寻找在同一事件中出现的不同项的相关性。关联规则挖掘技术主要用于从用户访问序列数据库的序列项中挖掘出相关的规则，在Web数据挖掘中，关联规则挖掘就是要挖掘出用户在一个访问期间( Session)从服务器上访问的页面/文件之间的联系，这些页面之间可能并不存在直接的参引(Reference)关系。
最常用的是Apriori算法，从事务数据库中挖掘出最大频繁访问项集，这个项集就是关联规则挖掘出来的用户访问模式，称为频繁集，是否“频繁”取决于是否满足用户指定的最小支持度闭值。在用户访问日志挖掘研究中，人们希望通过关联规则的挖掘找到用户访问页面之间的联系，这种联系关系有助于改进缓存策略，来达到提高服务质量的目的。
（2）、序列模式 (sequential pattern)
序列模式最早是由Agarwal和Srikant提出的，序列模式的定义是：给定一个由不同序列组成的集合，其中，每个序列有不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持阈值。序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持阈值。
序列模式与关联模式相仿，差别在于序列模式把数据间的关联性与时间先后顺序联系起来。即不仅需知道事件是否发生，而且需要确定事件发生的时间先后。序列模式根据数据随时间变化的趋势，发现某一时间段内数据的相关处理模型，预测将来可能出现值的分布。可以把它看成是一种特定的关联模型，它在关联模型中增加了时间属性，需要考虑时间的先后对关联规则的影响。
序列模式数据挖掘就是要挖掘出交易集之间的有时间序列的模式。在网站服 务器日志里，用户的访问是以一段时间为单位记载的，经过数据净化和事件交易 确认以后是一个间断的时间序列，这些序列所反映的用户行为有助于帮助商家印 证其产品所处的生命周期阶段。
在Web访问信息挖掘领域中，序列模式识别指寻找用户会话中在时间上有先后关系的页面请求。利用发现的序列模式可以预测用户即将可能请求的页面，这样就可以针对特定的用户组在页面中放置不同的广告条来增加广告的点击率。
（3）、聚类 (Clustering)
聚类是将数据点集合分成若干类或簇(cluster)，使得每个簇中的数据点之 间最大程度地相似，而不同簇中的数据点最大程度地不同;从而发现数据集中有
14
2 相关知识基础
效的、新颖的、可以理解的数据模式分布[25]。聚类与分类不同，分类之前已经知道要把数据分成哪几类，每个类的性质、特点是什么;聚类则恰恰相反，聚类是一种无监督分类法，没有预先指定的类别，在聚类之前并不确切的知道最后会聚为几类。
在Web访问信息挖掘中，可以进行两种聚类:用户聚类(包括用户访问会话聚类和用户访问事务聚类)和页面聚类。用户聚类是要建立具有相似浏览模式的用户聚类。页面聚类是要发掘具有相关内容的页面聚类,这对于Internet搜索引擎和Web提供商都是非常有用的。在第五章中还会详细的介绍聚类分析和基于模糊聚类的数据挖掘。
（4）、分类 (Classification)
分类的主要目的是分析输入数据，通过在训练集中的数据表现出来的特征，为每一类找到一种准确的描述或模型，可具体描述为：输入数据或称训练集（training set），是由一条条的数据源记录（record）组成的，每条记录包含了若干属性（attribute）而组成一个特征向量。训练集的每条记录还有一个特点的类标签（class label）与之对应，该类标签是系统的输入，通常是以往的一些经验数据，一个具体样本的形式可为样本向量：（v1，v2,?vn；c），在这里vi（i=1,2,?，n）表示字段值，c表示类别。
分类模式把数据集中的数据项映射到某个给定的类上，它反映同类事物共同 性质的特征型知识和不同事物之间的差异型特征知识。最为典型的分类方法是基 于决策树的分类方法，它是从实例集中构造决策树，是一种有指导的学习方法。 分类还有统计、粗糙集(RoughSet)等方法。线性回归和线性辨别分析是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。最近也有人研究使用神经网络方法在数据库中进行分类和规则提取。
在Web访问信息挖掘中，分类可用于为一组特定用户建立简档，这需要抽取并选择最能描述这组特定用户的特征。分类可以使用监督学习算法，如决策树、Naive Bayesian分类器、K-Nearest Neighbor分类器等。
（5）、路径分析技术 (Path analysis technology)
路径分析可以改进页面之间的链接关系以及网站结构。用路径分析技术进行Web日志的数据挖掘时，最常用的是图。因为一个图代表了定义在网站上的页面之间的联系。图最直接的来源是网站结构图，网站上的页面定义成节点，页面之间的超链接定义成图中的边。其他的各式各样的图也都是建立在页面和页面之间联系或者是一定数量的用户浏览页面顺序基础之上的。那么基于Web日志的数据挖掘，就是从图中确定最频繁的路径访问模式或大的参引访问序列，路径分析可以用来确定网站上最频繁的访问路径。
15