基于Web日志的实时推荐模型研究

工程硕士学位论文

基于Web日志的实时推荐模型研究

A Real-Time Recommendation Model

Based on Web Log

摘 要

随着WWW的广泛应用，在WWW服务器上聚集了大量的Web日志，这些数据在很多领域中都至关重要，如Web站点的系统设计、商业市场策略和网站个性化等等。实时推荐就是数据挖掘在Web日志数据中的一个应用，其目的是方便用户对网站的访问，可以预测用户的喜好，并为电子商务提供决策依据。

本文在概述Web挖掘以及Web日志挖掘的相关领域的发展和技术及其理论基础上，详细研究了Web日志挖掘的预处理技术，使用一个基于页面访问时间阈值与会话重组的会话识别算法，并通过实际的Web日志数据加以验证；在数据预处理的基础上，利用模糊聚类技术，根据用户对Web页面的浏览情况分别建立Web用户和Web页面的模糊集，然后用最大-最小法的模糊相似性度量构造模糊相似矩阵，并由此构造了模糊动态聚类算法；在上述工作的基础上，设计了一个基于Web日志挖掘的实时推荐模型系统RTRS（real-time recommendation system）。它分为离线部件和在线部件两部分，其中，前者进行数据收集、预处理、用户和页面的模糊聚类；后者根据用户当前访问行为生成推荐集，它采用的推荐算法是通过用户的访问记录构造BP树（Brows Pattern Tree），产生频繁访问集，从而生成推荐集，该算法只需扫描数据库一次，得到的频繁序列模式可以满足实时推荐的快速需求。

该论文有图10幅，表7个，参考文献52篇。

关键词：数据挖掘；数据预处理；会话识别；模糊聚类；实时推荐

II

Abstract

With the extensive use of WWW, the WWW server has assembled a large number of Web logs, these data are crucial in many fields, such as the Web site, system design, business marketing strategies and Web site personalization and so on. Real-time recommendation is a Web application of data mining in log data in which aims to facilitate users to access the site, you can predict the user's preferences, and offer basis.for making e-commerce decision.

On the basis of an overview of related areas of development and technology as well as theoretical basis of Web mining and Web log mining, this paper made a detailed study of the Web log mining preprocessing techniques, using a threshold based on page access time of the session with a session re-recognition algorithm, inspecting and verifying through the actual Web log data, on the basis of the data preprocessing, using fuzzy clustering technique, establishing Web users and Web pages of the fuzzy set based on user browsing of Web pages, then using the maximum - minimization of fuzzy similarity measure to construct fuzzy similar matrix so as to construct fuzzy dynamic clustering algorithm. Based on the above-mentioned work, the paper designed a real-time recommendation model system RTRS (real-time recommendation system) based on Web-log mining that is divided into two parts, offline part and online part, in which the former is for data collection, preprocessing, user and page of the fuzzy clustering;and the latter is formed into recommendation set,according to user current access behavior, for the recommended algorithm adopted in it is to construct BP tree (Brows Pattern Tree) through the user's access records and produces frequently accessed set, thus generates the recommendation set. This algorithm scans the database only once, and obtains the frequent sequence pattern to meet the rapid demand for real-time recommendation.

The paper has 10 Figures, 7 Tables and 52 references.

Keywords：data mining; data preprocessing; session identification; fuzzy clustering ;

real-time recommendation;

III

目 录

摘要???????????????????????????????I 目录???????????????????????????????Ⅲ 图清单??????????????????????????Ⅶ 表清单????????????????????????????Ⅷ 变量注释表???????????????????????????Ⅸ 1 绪论??????????????????????????????1 1.1 研究的背景和意义????????????????????????1 1.2 研究的现状???????????????????????????3 1.3 论文研究的主要内容???????????????????????6 1.4 论文的结构安排?????????????????????????6 2 相关知识基础?????????????????????????8 2.1 数据挖掘简介?????????????????????????8 2.2 Web挖掘简介???????????????????????8 2.3 Web挖掘的过程????????????????????????12 2.4 小结????????????????????????????16 3 数据预处理???????????????????????18 3.1 Web日志的形成?????????????????????????18 3.2 基本概念???????????????????????????20 3.3 Web日志数据预处理过程????????????????????21 3.4 试验数据???????????????????????????26 3.5 小结?????????????????????????????27 4 基于模糊矩阵的Web日志的动态聚类??????????????? 29 4.1 常用的聚类算法比较与分析???????????????????29 4.2 模糊聚类??????????????????????????32 4.3利用最大-最小相似性度量的实例?????????????????35 4.4 小结???????????????????????????36 5 基于Web日志的实时推荐模型???????????????????37 5.1 问题的提出??????????????????????????37 5.2 RTRS系统的模型???????????????????????38

IV

5.3 在线模块实时推荐???????????????????????39 5.4 实验结果与分析????????????????????????42 5.5 小结???????????????????????????43 6 总结与展望?????????????????????????44 6.1 总结?????????????????????????????44 6.2 进一步工作展望????????????????????????44 参考文献????????????????????????????46 作者简历????????????????????????????49 论文原创性声明?????????????????????????50 学位论文数据集?????????????????????????51

V

Contents

Abstract………………………………………………………………………………I Contents………………………………………………………………………………V List of Figures………………………………………………………………………Ⅶ List of Tables………………………………………………………………………Ⅷ List of Variables……………………………………………………………………Ⅸ 1 Introduction…………………………………………………………………1 1.1 Research Background and Significance…………………………………………1 1.2 Present Research Situation………………………………………………………3 1.3 The Main Contents in the Paper ……………………………………………6 1.4 Structure Arrangment in the Paper………………………………………………6 2 Related Knowledge Foundation……………………………………………8 2.1 Brief Introduction on Data Mining………………………………………………8 2.2 Brief Introduction on Web Data Mining…………………………………………8 2.3 The Web Mining Process…………………………………………………………12 2.4 Summary…………………………………………………………………………16 3 Data Preprocessing………………………………………………………18 3.1 Web Log Formation ……………………………………………………………18 3.2 The Basic Concept ………………………………………………………………20 3.3 Web Log Data Preprocessing……………………………………………………21 3.4 Test Data …………………………………………………………………………26 3.5 Summary………………………………………………………………………27 4 Dynamic Cluster Base on Fuzzy Similarity Matrix Web Log…………… 29 4.1 Comparison and Analysis of Commonly Used Clustering Algorithms………29 4.2 Fuzzy Clustering ………………………………………………………………32

4.3 Real Examples Using the Maximum - Minimization of Fuzzy Similarity Measure…………………………………………………………………………35 4.4 Summary ………………………………………………………………………36 5 Model Base on Web Log Real-Time Recommendation System ………… 37 5.1 Set up Problem…………………………………………………………………37

VI

5.2 RTRS System Model……………………………………………………………38 5.3 Real-Time Recommented Online Model………………………………………39 5.4 The Experimental Results and Analysis…………………………………………42 5.5 Summary ………………………………………………………………………43 6 Conclusions and Prospect …………………………………………………44 6.1 Conclusion………………………………………………………………………44 6.2 Further Work Prospect…………………………………………………………44 References………………………………………………………………………46 Author’s Resume…………………………………………………………………49 Declaration of Thesis Originality…………………………………………………50 ThesisData Collection………………………………………………………51

VII

图清单

图序号 图2-1 Figure 2-1 图2-2 Figure 2-2 图3-1 Figure 3-1 图3-2 Figure 3-2 图3-3 Figure 3-3 图4-1 Figure 4-1 图4-2 Figure 4-2 图5-1 Figure 5-1 图5-2 Figure 5-2 图5-3 Figure 5-3 图名称 Web挖掘分类 Categories of Web data mining Web访问信息挖掘的过程 Process of web usage mining 原始日志 Primitive log 数据预处理过程 The process of data preprocessing 数据清理各部分所占比例 The various parts proportion of data cleaning Web模糊聚类过程模型 Web fuzzy clustering process model 网站拓扑结构图 Site topology structure map RTRS系统的模型 RTRS system model BP树的建立 Establishment of BP tree BP挖掘的实例 BP mining examples 页码 10 10 12 12 20 20 21 21 22 22 35 35 35 35 39 39 42 42 42 42

VIII

表清单

表序号 表2-1 Table 2-1 表3-1 Table 3-1 表3-2 Table 3-2 表3-3 Table 3-3 表3-4 Table 3-4 表4-1 Table 4-1 表5-1 Table 5-1 表名称 Web挖掘的三种方法比较 Three methods comparison in Web mining Web日志记录的主要信息 The main information in Web log records 常用的用户识别方法 Recognition methods for common user 原始日志记录 Primitive log record 经过数据预处理后的用户会话记录 User session record after data pre-processing 聚类算法的分类 Cluster algorithm classification 用户会话 User session 页码 12 12 19 19 24 24 27 27 27 27 29 29 42 42

IX

变量注释表

L Log rij R R′ R\S U δ θ λ ξ 用户访问日志集合 日志文件 相似系数 日志记录 模糊关联度矩阵 模糊相似矩阵 会话集合 用户集合 会话时间延时 会话时间阈值 模糊相似阈值 最小支持度阈值

X

1绪论

1 绪论 1 Introduction

随着Internet的发展，越来越多的人从中获得信息，可是怎样在浩瀚的Internet中获得你想要的，又如何向你的客户推荐他最想了解的信息呢？现在各种基于Internet网络的应用业务也如雨后春笋般的发展起来，例如：网上商店、网上银行、远程教育、远程医疗等。特别是方便、快捷、高效的电子商务发展速度惊人，我们也应当看到Internet在给我们带来机遇的同时也带来了挑战，例如Web站点设计、Web服务设计、Web站点的导航设计、电子商务等工作变得越来越复杂越来越繁重。对于网站经营者来说，他们需要更好的动态设计工具，可以根据用户的访问兴趣、访问频度、访问时间动态的调整页面结构，改进服务，开展有针对性的电子商务，以更好的满足访问者的需求。

1.1研究背景及意义（Research Background and Significance）

1.1.1研究背景

在各种Web站点中，蕴涵着巨大的具有潜在知识的信息空间，在InterNet上既存贮了大量的文档、图形、图像等多样性的Web数据，用户访问又有充分的自由，可以随意链接到Internet的任意站点上，并且用户具有不同的背景、兴趣和使用目的，Web用户也表现出多样性的特点。因此，在Internet给人们带来了方便和丰富多彩的信息资源的同时，也产生了如下急需解决的问题[1]。

（1）、用户容易在巨大的数据中迷失

虽然Internet上存贮了大量的数据，但由于Web是无结构的、动态的并且Web页面的复杂程度远远超过了文本文档，给人们准确查找和定位所需要的信息带来了极大的困难。

用户在Web上浏览或检索信息时，往往通过使用搜索引擎工具，但目前的搜索引擎普遍存在低精度的问题。低精度表现在当用户输入关键词检索信息时，返回的查询结果动辄成百上千条，更有甚者会达到几十万乃至上百万条，而其中大多数是一些与检索内容无关的信息，也包括死链接，用户难以在巨大的数据中寻找所的信息，浪费了很多的时间。

（2）、个性化的信息服务

不同层次、不同爱好和使用目的的浏览者需要个性化的信息服务。但是，这个问题涉及到Web门户站点的管理、组织和经营。Web站点的经营和管理者为提高网站的声誉和效益，需要了解其用户究竟需要什么，其中包括根据大多数用

I

工程硕士学位论文

户的共同兴趣，开展有针对性服务以及对特定用户开展个性化服务，真正地实现以人为本的原则。

从站点经营方来说，他们需要好的自动辅助设计工具，可以根据用户的访问兴趣动态地调整页面结构，改进服务，开展有针对性的服务以更好地满足访问者的需求。

（3）、如何向用户推荐感兴趣的内容

根据用户以往的访问模式动态的推荐用户感兴趣的内容，防止用户在庞大的信息面前迷失自己。对于访问者来说，他们既希望看到个性化页面，又希望得到更好的满足各自需求的服务，还希望从其他具有类似访问兴趣的用户访问行为中得到启发。这些需求从某种意义上说，访问者本身也未必清楚。

解决上述问题的途径之一就是将传统的数据挖掘技术应用于Web访问信息。即利用数据挖掘的原则和思想，针对Web访问信息的新特性，对传统挖掘方法进行扩展和改进，将其应用到Web访问信息上，挖掘出有用的知识。根据用户行为模式改进站点设计和服务，开展个性化和有针对性的服务，抽取有用的感兴趣模式和隐含的知识实现Web信息准确查询。

1.1.2研究意义

网站的所有访问者都会留下浏览的踪迹，这些信息以文本存储在Web服务器的日志文件内。分析互联网背后的用户行为，是获取用户行为偏好的良好途径。由于Web访问信息存在于每一台Web服务器上，因此其具有普遍性，并且遵循共同的标准，那么基于Web日志的数据挖掘主要应用于以下下面[2]:

（1）、系统改进。通过日志挖掘，可以发现用户的需要和兴趣，对需求较多的地方提供优化；用服务器(或代理服务器)预先存储的方法来解决速度缓慢的问题，从而有助于找到平衡服务器的负荷，优化传输，减少阻塞，缩短用户等待时间，提高系统效率和服务质量。对网站而言吸引访问者是其最重要的生存之道，如果一个网站的设计不利于用户的访问，设计者不了解访问者的兴趣，那么必然在激烈的竞争中处于不利的地位。

（2）、 为用户提供个性化服务。对大多数的Web站点来说，让用户感到整个网站是完全为他自己定制的个性化网站是Web网站成功的秘诀。因此可以针对不同的用户，根据用户访问历史，按照其个人的兴趣和爱好(数据挖掘算法得到的用户访问模式)，向用户动态的推荐商品，自动为用户提供个性化的服务。

（3）、提高网站结构设计。通过挖掘提供用户使用网站信息，可以帮助网站设计者对网站的修改更加有目的、有依据，稳步的提高用户的满意程度;用户的导航模式是指用户对Web站点内的页面的浏览顺序模式。路径分析可以被用于判定在一个Web站点中最频繁访问的路径。还有一些其他的有关路径的信息通

2

1绪论

过路径分析可以得出，利用这些信息可以改进站点的设计结构。

（4）、商业智能发现。商业智能发现是通过对用户行为和购物等关系的挖掘，更好理解用户的购买意图，发现其中的用户购物特征和购买趋势、识别电子商务的潜在客户，确定电子商务的潜在客户群，以此进行商业智慧、支持商业决策，合理制订网络广告策略。

（5）、提高网络安全。分析网上银行、网上商店交易用户日志，可以防范黑客攻击和恶意诈骗；同时也可以对网站进行评价。

1.2研究现状 (Research Present Situation)

数据挖掘从20世纪80年代出现以来，帮助企业经理制定决策、促进商业竞争等很多有意义的事情。数据挖掘技术和算法主要包括：智能超市搜索、决策树、神经网络、相关分析、遗传算法、模糊逻辑、粗集、概念学习、归纳逻辑程序和聚类等等。目前使用较多的是关联规则分析、聚类分析、分类和预测等，这些技术大多应用在生物医学、商业、金融和电信等方面[3]。

基于Web日志的挖掘出现在1996年，M.S.Chen. H.Mannila. T.Yan提出了可以将数据挖掘方法应用于Web研究领域[4]。互联网的快速发展，使得对Web访问日志分析的需求越来越迫切。Web日志的挖掘研究大致可以分为三个方向：分析系统性能；改进系统设计；理解用户意图。由于它们针对的功能不同，采取的主要技术也不同。

以分析系统性能为目标的研究，主要是从统计学的角度，对日志数据项进行多种简单的统计，如频繁访问的网页，单位时间访问数，访问数据量随时间分布图等。目前己有的绝大多数商用例如：SPSS、SAS等及免费的Web日志分析工具都属于这种类型。

以改进系统设计为目标的研究，由于Web服务器的设计与建设的主要复杂性是它能随着设计者及用户的变化而不断自我调整，研究如何以日志数据为依据，对Web服务器的组织和表现形式进行自动或半自动调整，从人机交互和软件Agent领域提出adaptive web site的概念。

以理解用户意图为目标的研究，一般是通过算法从Web服务器日志中找出频繁的用户访问路径或访问模式。这些都是为了从大量的Web日志数据中找出一定的模式和规则。

目前，国内外对计算机柔性技术的研究成为热点。所谓柔性技术，它包含粗糙集理论、模糊理论、神经网络、遗传算法等。特别是模糊理论，在解决模糊性问题时体现出较大作用，针对Web用户兴趣的模糊性、非单一性，引入模糊聚类对其浏览路径进行模糊聚类，可以较好地解决此类问题，在很大程度上避免了传统聚类的非此即彼的硬性划分，更客观地体现真实的人类活动。因此，将模糊

3

工程硕士学位论文

聚类应用于Web挖掘，分析用户访问Web的模式，设计出满足不同客户群体需要的智能化网站，进而增加企业的竞争力。

1.2.1国外进展研究

目前，Web访问信息挖掘已经成为国际上一个新兴的重要研究领域。早在1996年就有学者M.S.Chen , H.Mannila , TYan提出了可以将数据挖掘方法用于Web研究领域使用。

1998年Han把Web服务器访问日志集成到数据立方体结构(data cubestructure)中[5]，这样就可以对访问日志用传统的在线数据分析处理过程(OLAP)来处理日志数据了。因为他其分析主要用的是动态网站日志，因此，他假定客户端的缓存影响不大。

1999年，J.Borges等人又提出了引入超链接概率原理，修改了传统意义上对序列的界定，可以把用户的访问在网站结构图中记录下来，根据访问的条件概率判断用户频繁访问路径。2001年，个性化研究已经在商业领域得到越来越广泛的应用。IBM公司在电子商务平台WebSphere中增加了个性化功能，以利于商家开发个性化电子商务网站。

目前，Web日志挖掘方法主要有两种。Chen等人首先将数据挖掘技术应用于Web服务器日志文件，以期发现用户浏览模式，Chen提出了最大前向引用序列MFR的概念，并用它将用户会话分割成一系列的事务，然后采用与关联规则相似的方法挖掘频繁浏览路径。

Han等人则根据Web日志建立数据立方体，即根据Web日志建立数据立方体，然后对数据立方体进行数据挖掘和OLAP[6]。Simon Fraser大学的WeblogMiner将Web日志中的数据组织为数据立方体，然后在其上进行联机分析处理和数据挖掘，用于发现用户的访问模式，并提出了GraphMiner。

Minnesota大学的WEBMINER[7]系统提出一种通用的Web日志挖掘的体系结构，该系统能自动从Web日志中发现关联规则和序列模式等。WEBMINER的思路是通过对Web站点的日志进行处理，将数据组织成传统的数据挖掘方法能够处理的事务数据形式，然后利用传统的数据挖掘方法(如传统的关联规则发现算法)进行处理。

Perkowitz等在人机界面研究领域，提出了Adaptive Web site的概念，主要研究如何以历史访问为依据，使得Web服务器提供的服务页面可以自动或者半自动地调整[8]。

WebLogMiner是用于挖掘Web日志文件的知识发现工具。在WebLogMiner系统中，知识发现总共分为四个步骤：第一阶段根据Web服务器日志文件构建数据库，在此阶段中，从Web日志数据中过滤掉不相关的信息，将剩下的有意

4

1绪论

义信息经过数据转换后构造成一个关系型数据库。第二阶段构造多维Web日志数据立方体。第三阶段根据数据立方体进行联机分析处理。第四阶段进行知识发现和表示。通过联机分析处理发现的潜在知识进行数据特征化、类别比较、关联规则、预测分类和时间序列分析等形式表示出来。

SpeedTracer是一个Web日志挖掘的分析工具[9]。它通过在Web服务器日志数据上使用数据挖掘技术和方法来发现和理解用户的浏览行为。随着WWW的日益普及，各方面有强烈的需求，要理解不同用户的浏览行为。然而Web服务器日志数据的不确定性和不完整性造成人们很难直接在Web日志上执行以用户为导向的数据挖掘和分析。SpeedTrace:通过重建用户访问路径来识别用户会话。它不需要Cookies或用户注册信息来进行会话识别，这样做的一大优点就是能够保护用户的隐私。用户被正确识别以后，数据挖掘算法就能够发现共同的访问模式和频繁共同访问的页面组。

Web日志挖掘是一个较新的研究领域，具有广阔的发展和应用前景。应该指出的是，面对日益增加的商业需求，Web日志挖掘技术还有许多问题需要解决，有待这一领域的研究者深人研究。将来很有用的几个研究方向是如下。

（1）用户访问模式库的动态维护和更新、模式(知识)的评价体系和评价方法；

（2）分类在电子商务市场智能提取中的研究；

（3）关联规则和序列模式在构造自组织站点方面的研究； （4）智能站点服务个性化和性能最优化的研究；

（5）挖掘算法在海量数据挖掘时的适应性和时效性研究； （6）Web日志挖掘中内在机理及新的挖掘体系和结构的研究。

1.2.2国内的研究现状

国内互联网是从1997年开始迅速蓬勃的发展起来的。直到1999年，国内互联网用户达到一定数量以后，国内学者才开始关注Web数据挖掘，相比之下起步较晚。

1999年，陈宁综述了国外应用数据挖掘技术解决Internet应用问题的做法。 1999年，周斌等介绍了采用E-OEM模型，并用5个用户访问模式做训练数据集，尝试着进行了关联规则挖掘。董金样教授等研究Web用户浏览活动的本质，根据Web用户在网站中各页面的停留时间和访问次数等特征，结合用户的参与，识别、建立、调整该用户的喜好，提出兴趣强度及度量方法，使用户能以个性化方式来访问。

庄越挺教授等提出基于神经网络的Web用户行为聚类分析方法[10]，即首先对Web服务器的日志文件进行分析，再进行会话分析，从会话向量中找出频繁

5

工程硕士学位论文

数据集，进行规一化处理后，生成模式向量，采用SOFM模型进行聚类，最后生成用户聚类。

Web数据挖掘在国内已经引起人们的关注，但是，在收集网站访问日志过程中发现国内大多数网站经营管理者对从访问日志中发掘有用信息的重要性认识不充分，仅仅停留在只收集了用户错误的访问记录，网络管理人员还停留在关注服务器性能阶段，没有达到关注网站服务质量的更高层次上。

1.3论文研究的主要内容 (The Main Contents in the Paper)

首先，介绍了Web挖掘技术研究的背景和意义，以及国内外研究现状，并介绍了Web日志挖掘中所涉及到的相关知识，对其中的数据预处理技术进行了较全为全面的阐述，特别是对Web日志挖掘系统中所涉及到基于时间阈值的会话识别算法进行了分析，从而保证数据挖掘的正确性。

接着，对已有的聚类技术进行了简单介绍，并详细分析了一个基于模糊聚类算法对Web日志的用户和网页进行动态聚类，提出用最大-最小法的模糊相似性度量构造模糊相似矩阵的方法，并通过一个实例进行。

最后，详细的介绍了一个基于Web日志的实时推荐模型，通过构造BP树（Brows Pattern Tree）的方法记录用户的历史访问记录，然后通过挖掘算法得到频繁访问集，从而生成推荐集，实现实时推荐的需要。然后结合一个实例对该算法进行了验证。

1.4 论文结构安排 (Structure Arrangement in the Paper)

本论文的后续章节的内容安排如下:

第一章：绪论，主要介绍了Web日志挖掘的背景和意义，以及国内外的研究状况。

第二章：主要介绍本论文所涉及到的基础知识，包括数据挖掘和Web挖掘的定义、Web挖掘的分类、Web日志挖掘相关技术和基于Web日志的数据挖掘系统。

第三章：主要介绍数据预处理技术，尤其是基于Web日志的数据数据预处理技术；还给出了基于Web日志的数据预处理过程，使用一个基于页面访问时间阈值与会话重组的会话识别算法，并通过实际的Web日志数据加以验证。

第四章：首先对已有的聚类技术进行了简单介绍；接着，详细分析了一个典型的基于模糊聚类的算法，针对Web客户聚类和页面聚类的问题，提出了模糊聚类的方法，利用此方法可以很好的解决Web日志中客户聚类和网页聚类。根据用户对Web页面的浏览情况分别建立Web用户和Web页面的模糊集，然后用最大-最小法的模糊相似性度量构造模糊相似矩阵，并由此构造了模糊动态聚类

6

1绪论

算法，实验表明该方法可行而且具有很好的扩展性。

第五章：针对个性化实时推荐系统的不足，提出了一个基于Web日志的实时推荐模型，通过构造BP树的方法压缩访问事务集，将耗时的数据预处理放在离线模块，实时推荐采用动态修剪BP树的方法，穿过访问模式树的相关部分，然后利用网页推荐算法得到频繁访问集，从而生成推荐集。结果表明该算法只需扫描数据库一次，得到的频繁模式可以满足页面实时推荐的快速需求。最后，还对算法的性能进行了简单地分析。

最后，对本论文所做工作进行了总结，并对未来的工作进行了展望。

7

工程硕士学位论文

2 相关知识基础

2 Related Knowledge Foundation

2.1 数据挖掘简介 (Brief Introduction on Data Mining)

数据挖掘(DM：Data Mining)，也称为数据库中的知识发现KDD(Knowledge Discover in Database)，是近年随着数据库和人工智能发展起来的一门新兴的数据库技术[11]。

知识发现，这一术语首先出现于1989年在美国底特律召开的第11届国际人工智能联合会议的专题讨论会上。迄今为止，由美国人工智能协会主办的KDD国际研讨会已经召开了8次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，KDD已经成为当前计算机科学界研究的一大热点。

数据挖掘是一门交叉型学科，涉及到很多的学科，例如：机器学习、模式识别、统计学、数据库、知识获取、知识表达、专家系统、神经网络、模糊数学、遗传算法等多个领域。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、以前未知的、具有潜在的或者现实应用价值的信息和知识的过程[12]。

数据挖掘技术可以分为比较成熟的统计类型挖掘技术、快速发展的知识挖掘技术以及其它一些数据挖掘技术。统计分析技术中使用的数据挖掘模型有线性分析和非线性分析、回归分析、逻辑回归分析、单变量分析、多变量分析、时间序列分析、最近邻算法和聚类分析算法等技术。知识发现类的数据挖掘技术是从数据仓库的大量数据中筛选信息，寻找市场可能出现的运营模式，发掘人们所不知道的事实。知识发现类挖掘技术包含人工神经网络、决策树，遗传算法、规则发现和关联顺序等[13]。

2.2 Web数据挖掘简介 (Brief Introduction on Web Data Mining)

随着Internet的迅速发展，使得WWW上的信息量飞速增长，怎样对这些数据进行分析，成了现今数据库技术的研究热点。因此对强大有力的Web数据分析处理工具提出了要求，而日趋成熟的数据挖掘技术正好为Web挖掘提供了技术基础。Web挖掘是将数据挖掘技术应用于大规模Web数据，以期发现有效的、新颖的、潜在有用的，以及最终可理解的模式和规则的过程。

Web挖掘的定义是从数据挖掘的概念扩展而来，Web数据挖掘[14] (Web Data

8

2 相关知识基础

Mining)就是从大量的Web资源中提取隐含的、未知的、对决策有潜在价值的知识和规则的过程，它把数据挖掘技术应用于对Web资源的挖掘上。简单地说，Web挖掘是指从Web服务器上的数据文件中提取人们感兴趣的知识的过程。这里所谓的“兴趣”与我们前面讲数据挖掘时提到的含义相同。Web挖掘其实就是对文档的内容、可利用资源的使用以及资源之间的关系进行分析，以实现对Web存取模式、Web结构和规则的分析，以及动态Web内容的查找。它所处理的对象包括：用户使用记录、网页内容、Web结构等信息，它是一项综合技术，涉及到Internet技术、人工智能、计算机语言学、信息学、统计学等多个领域。

Web挖掘作为数据挖掘的一个较新的主题，是一个新兴的研究领域，目前国内外的研究重心大多集中在日志的挖掘上，通过繁杂的方法将数据数据库化或仓库存储，从而将Web Mining转化为数据库的知识发现。

2.2.1 与传统数据挖掘的不同

Web挖掘与传统的数据挖掘相比，两者挖掘对象不同:前者的挖掘对象是海量、异构、分布式的Web文档和Web服务器日志，而后者的挖掘对象是数据库，Web数据挖掘具有如下的特点:

（1）、算法的效率要求更高：由于基于Web的数据量比一般的关系数据库或者数据仓库的数据量要大得多，而且数据每天都在迅速的增长和更新，要从如此巨大的数据中有效的提取有价值的信息要求数据挖掘算法必须具有很高的效率;

（2）、广泛的用户群体：Web面对的是一个广泛的形形色色的用户群体，Web的用户群仍在快速地扩张中，并且各个用户具有不同的背景、兴趣和使用目的。大部分用户并不了解信息网络结果，Web上的信息对用户而言，只有很小的一部分是相关的或有用的。很多信息对于用户是无用的，因此极容易在“跳跃式”的访问中烦乱不已和在等待信息中失去耐心。

（3）、具有动态性： Web是一个动态性极强的信息源。Web不仅以极快地速度增长，且其信息还在不断地发生着更新，如：信息、股票市场等，链接信息和访问记录也在频繁地更新之中，需要针对不断新增的数据进行增量挖掘，体现数据挖掘的动态性。

（4）、页面的复杂性：因为Web页面缺乏统一的结构，它包含了远比任何一组书籍或其它文本文档多得多的风格和内容，因此对数据预处理要求高，传统的数据模型和数据库系统难以直接支持Web上的信息资源，因此Web挖掘必须对数据进行数据预处理，从而为下一步的挖掘提供具有良好格式的数据源。

9

工程硕士学位论文

2.2.2 Web挖掘的分类

根据挖掘对象的不同，Web挖掘可分为Web结构挖掘(Web Structure Mining)、 Web内容挖掘(Web Content Mining)和Web使用挖掘(Web Usage Mining)三类[15] [16] [17]。其中，Web结构挖掘是指对Web页面的结构进行挖掘，是Web的组织结构以及引用和被引用之间的链接关系推理知识的过程；Web内容挖掘是指对Web页面内容进行挖掘，主要包括文本信息挖掘和多媒体信息挖掘；Web使用挖掘也称为Web日志挖掘，是指从Web访问日志中抽取知识的过程。图2-1是一个Web挖掘的详细分类图。

Web页 面挖掘搜索结果挖掘 结构 超链接挖 掘 用户访问模式挖掘 分析定制Web站点 Web内容挖掘 Web结构挖掘 Web使用挖掘 Web挖掘 图2-1 Web挖掘分类

Figure 2-1 Categories of Web data mining

（1）、Web内容挖掘

Web内容挖掘是一种基于网页内容的Web挖掘，是从Web上的文件内容或其描述中发现信息、抽取有用知识的过程[18]。这些数据对象既有文本和超文本数据，也有图形、图像、语音、视频等多媒体数据；数据既有来自于数据库的结构化数据，也有用HTML标记的半结构化数据和无结构的自由文本。就方法而言，Web内容挖掘可以分为两大类：信息检索(Information Retrieve，IR)方法和数据库方法[19]。就挖掘策略的不同，Web内容挖掘又可分为Web概要(即直接挖掘Web文档的内容)和搜索引擎结果概要(即对搜索引擎的查询结果做进一步处理，得到更精确和有用的信息，以增强搜索引擎的内容查询功能)。就其处理的内容可分为文本挖掘和多媒体挖掘。

1）、文本挖掘

Web文本挖掘主要是对Web上大量文档集合的内容进行总结、分类、聚类、关联分析以及利用Web文档进行趋势预测等功能，它是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘要和解释，使用户无需浏览全文即可了解文档或文档集合的总体内容。文本总结（文本摘要）是文本挖掘的一个重要内容，在一些场合应用非常广泛，如搜索引擎在向用户返回查询结果时，通常需要给出

10

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

工程硕士学位论文

（6）、统计分析（Statistical analysis）

统计分析是一个利用概率、数据分析及统计知识推理的过程，统计分析技术是最常用的从Web用户行为中抽取知识的方法。通过分析服务器口志文件，可以得到各种统计分析描述，如用户驻留在某页面上的时间，用户浏览路径长度的中值和平均值、导航路径长度以及频繁访问的网页，单位时间访问数，访问数据量随时间分布图等。这种分析虽然看起来缺乏深度，但分析结果往往对提高系统性能，加强系统安全性，辅助网站设计，便于站点修改并可提供决策支持，提供市场决策等方面有着不可替代的作用。

目前己有的绝大多数数据挖掘软件，例如：SPSS、SAS等及免费的Web日志分析工具都属于这种类型。

2.3.3 模式分析

用户访问模式挖掘出来之后，需要把这些模式解释为人们成为可以理解的知识。因此，在研究Web日志挖掘技术时，也要研究、开发能够分析挖掘出来的模式的工具。目前这个领域的工作还不是很多，是一个较新的领域，在Web访问模式分析中人们正在研究应用的技术有: （1）、可视化技术

可视化技术可以有效的帮助人们理解不同的现象，因此对于理解Web用户行为模式来讲也是一个自然的选择。Pitkow等人己经开发了Webwiz系统来将www的访问模式可视化。其中用服务器日志扩展一系列的网页访问模式称作网页路径，它们组成一个路径图。WebViz系统可以过滤无关的Web页面，使人们只分析有意义的部分，最终，形成可视化的结果—一个有向环图，图中的节点是页面，边是页面之间的超级链接。此外联机分析处理(OLAP)技术也可以应用到模式分析中。

（2）、数据知识查询

关系数据库技术成功的原因之一是因为其高层次的语法定义、查询语言的支持，这些使得用户很容易表达自己的要求。对大量的挖掘出来的模式，也需要一种技术使用户可以方便地查询到想要的模式，从而使解释和分析更具针对性。实现这个功能也就是要实现在已经挖掘出来的知识上进行查询。

2.4 小结（Summary）

在Web挖掘中，目前国内外开始重点研究的是Web访问信息挖掘，即通过挖掘Web服务器的日志文件等访问信息，来发现用户访问Web页面的模式，从而可以进一步分析和研究日志记录的规律，来改进网站的组织结构及其性能，构造自适应网站，还可以通过统计和关联分析，增加个性化服务，发现潜在的用户群体，

16

2 相关知识基础

增强对最终用户的因特网信息服务的质量和交付等。

本章详细地介绍了数据挖掘技术与Web数据挖掘的含义及其不同、特点和Web挖掘的应用前景。首先介绍了数据挖掘与知识发现的区别与联系，阐述了数据挖掘的过程;然后引出Web数据挖掘的定义，阐述了Web数据挖掘的分类:Web内容挖掘、Web结构挖掘、Web使用挖掘;最后分析了基于Web访问数据挖掘的过程。

17

工程硕士学位论文

3 数据预处理 3 Data Preprocessing

数据质量的好与坏直接关系到数据挖掘的结果，因此数据预处理是Web日志数据挖掘的关键。针对数据预处理中的关键阶段—会话识别,提出了一个基于IP、会话时间、页面访问时间和网站拓扑结构等要素结合的会话构造算法,从而使会话识别出来的结果更接近于用户的真实会话。

3.1 Web日志的形成（Web Log Formation）

数据收集可以从服务器端数据、客户端数据、代理服务器端数据收集。这些数据不仅意味着存放的位置不同，其中还包含了Web世界中不同的浏览模式。通常，用户端的日志包含了单用户多站点的浏览模式，服务器上的日志则意味着多用户单站点模式，代理服务器上的日志则是多用户多站点模式，Web访问信息挖掘的数据对象主要分布于服务器方。

3.1.1服务器端数据

由于Web服务器详细记录了用户的浏览行为，因此Web服务器是Web挖掘的最直接、最重要的数据来源。Web服务器不但记录了每一个用户每次浏览时诸如访问时间、停留时间、访问次数、下载等具体行为，而且从浏览页面地址还可以获得页面的详细内容。目前在Web服务器端用来记录用户访问日志的格式有三种：

万维网协会（W3C）规定了服务器日志的两种格式：CLF（Common Log Format）和扩展日志格式ECLF（Extended Common Log Format）[26]。

典型的日志包括以下信息：IP地址、请求时间、访问方式(GET/POST)、被请求文件的URL, HTTP的版本号、返回码、传输字节数、引用页的URL(指向被请求文件的页面)和代理。

在日志文件中，每条记录被称作项或条目。其中：

客户端IP地址(Client IP)是发出请求的客户端的IP地址，在Proxy代理服务器的环境下为代理服务器的IP地址。

用户标识符域(User name，User id)一般不填写，只有当存取特定的文件，需要鉴别身份时才需要。时间戳(Date or Time)表示Web服务器接受该请求的时间，在整个日志文件中，每一个项以时间戳递增排列。

请求域(Request)包括请求方法，URI请求的协议。其中请求的方法有：GET、 POST和HEAD。GET从Web服务器得到对象；POST向Web服务器发送信息；

18

3 数据预处理

HEAD仅请求一个对象的HTTP头。

URI或者为服务器上文件系统上的一个静态的文件，或者为一个响应该请求的一个将要被调用的可执行程序。

状态域由Web服务器设置指示出响应该请求的行为：200到299的代码一般指示成功响应；300到399表征某种程度的重定向；400到499指示错误；500到599表示Web服务器有问题。常见的错误代码是404，其指示被请求的文件没有被找到。

Referer：域表征上次被请求的页面，如果用户通过直接键入地址或通过书签访问，那么该域为空。

代理域(Agent)能够指出客户端的操作系统和浏览软件。 表3-1为Web日志记录的主要信息

表3-1 Web 日志记录的主要信息

Table 3-1 The main information in Web log records

域 日期(date) 时间(time) 客户IP 地址(c - ip) 用户名(cs - username) ·服务器名(s - computername) 服务器IP 地址(s - ip) 服务器端口(s - port) 方法(cs - method) URI 资源(cs - uri - stem) URI 查询(cs - uri - query) 协议状态(sc - status) ·发送字节数(sc - bytes) ·接收字节数(cs - bytes) ·所花时间(time - taken) ·协议版本(cs - version) ·主机(cs - host) ·用户代理(cs(User - Agent) ) ·Cookie (cs(Cookie) ) ·参照(cs(referer) ) 描述 用户请求页面的日期 用户请求页面的具体时间 客户端主机的IP 地址或DNS 入口 客户端的用户名 服务器名称 服务器的IP 地址 服务器的端口号 用户请求的方法 用户所请求的页面 用户欲进行的查询 返回http 的状态标识 服务器发送的字节数 服务器收到的字节数 完成浏览所花费的时间 传输用的协议版本 服务器的操作系统 服务的提供者 Cookie 标识号 用户浏览的上一页 表中打黑点的部分是扩展型日志格式中添加的记录项。

19

工程硕士学位论文

原始的日志如图3-1所示：

图3-1 原始日志 Figure 3-1 Primitive log

3.1.2客户端数据

客户端的日志记录是由运行在客户端的程序或浏览器本省记录用户行为得到的记录，客户端的日志记录能够很好的反映用户的访问行为，但由于涉及个人隐私，实际上是很难获得的，也无法精确的知道每个来访者的情况。因而只能开展基于群体特性的，较为粗略的，基于统计特性的挖掘，以得到群体用户的访问偏好。如果要实现较为高级和精细的挖掘活动，通过相应的方法实现单个客户端的访问信息收集工作是必要的。

单个用户端的访问信息收集带来的主要好处是：提供单个用户较为精确的对一个站点或多个站点的访问偏好。这种偏好表现为对一个站点上的一些页面或一些站点的较为频繁的访问，或者通过收集该用户的书签((Bookmark)内容来得到用户的兴趣爱好。如果得到的这种偏好只用于服务该用户，即不向任何外界传递，那么用户一般可以接受，否则用户很难允许自己的访问兴趣以传给服务方。

3.1.3代理服务器端

在网络中，基于安全和效率等方面的考虑，可使用代理服务器技术。代理服务器技术可以是多级联的，它在用户和Web服务器之间扮演中间传递者的角色，代理服务器可以记录多个用户在多个Web站点的用户行为信息，它的访问信息包括用户访问日志和在Cache中被访问的页面，其中代理服务器端记录的用户访问日志同样遵循公共日志格式标准，通过对代理服务器访问信息的挖掘可以得到通过该代理服务器的用户的访问偏好。

3.2 基本概念（The Basic Concept）

相关概念[27]：

20

3 数据预处理

用户（User）：一个用户是通过浏览器访问一个或多个Web服务器的个体。 页面文件（Page File）：一个页面文件是Web服务器通过HTTP请求发给用户的文件。页面文件往往在Web服务器上静态存在。

页面视图（Page View）：一个用户请求的页面，如frame、图片和script等，它们在用户浏览器上同时显示。页面视图通常与一个用户的行为相关，如一次鼠标点击。

点击流（Click Stream）：用户访问的一组连续的页面浏览的序列。 用户访问会话（User Session）：是指由一个用户发出的对Web的一次连续HTTP请求序列。

服务器用户访问会话（Server Session）：简称用户访问事务（UserTransaction）。是指一个用户对一个Web服务器的一次访问，由这次访问网络日志中用户兴趣的挖掘及利用中的请求页面序列组成。

访问片断（Episode）：任何有意义的用户访问会话或用户访问事务的子集。

3.3 Web日志数据预处理过程（Web Log Data Preprocessing）

数据预处理是为了将日志文件转换成数据库文件而进行的工作，其目的就是把Web日志转换为适合进行数据挖掘的精确数据，它包括数据清理、用户识别、会话识别、路径完整等几个阶段[28] [29]。

具体处理过程如图3-2。

页面过滤Web服务器日志文件 数据清理用户识别时间阀值会话识别站点拓扑结构路径完整序列事务文件

图3-2 数据预处理过程

Figure 3-2 The process of data preprocessing

3.3.1数据清理

日志中记录的原始数据通常非常大，存在很多对于挖掘任务没有意义的数据记录和数据项。要删除以下几类[30]：

（1）、图片、音频、框架等非用户请求逻辑单位；HITP协议是一个无连接协议，用户请求的是一个整体页面，而服务器记录的是下传到客户端的一个个文件流，用户的一个HTML页面请求会产生几条日志记录，其中也包括非用户请求的若干图片、框架以及脚本。然而Web日志挖掘的目的是获得用户的行为模式，只有用户请求的HTML页面才一真正代表了用户的意图，不需要关心那些

21

工程硕士学位论文

用户没有显式请求的文件，所以通过检查URL的后缀删除不相关的数据。不相关的数据类型主要有:GIF , JPEG ,JPG, gif, jpg, jpeg, avi, rm, asf, rmvb，map等，应将后缀为这些的记录从原始数据库中删除，过滤掉的图片、动画等文件可能是原始数据的10%-30%，有的甚至更高。

（2）、搜索引擎，这些蜘蛛程序和其它蠕虫（bot）程序与人们在互联网上访问行为是不一样的，他们对于日志的路径分析影响很大。一些搜索引擎需要扩大其数据库，会自动去浏览站点。比如：Crawler,spider和Robot等。它们会在日志中留下一记录，如果不剔除这些项，那么将会影响挖掘的结果。最简单的处理代理访问方法是检查日志中每项的代理域，许多代理和爬虫会在这个域里申明自己，那么通过字符串匹配方法可以容易地删除这些项。另外一种方法是检查“robots.txt\文件，这样的蜘蛛表现在日志的（cs（User-Agent））中，通常含有字符串’bot’,’spider’,’slurp’,’crawler’,’checker’，我们要将日志中Agent项中包含如上字符串的记录删除。

（3）、用户请求访问失败的记录，虽然这些信息中可能包含着某些有用信息 (如测定网站内容的完整性，链接的正确性和统计异常等)，但对浏览模式发现来说输入的信息必须是正确的。这类访问的返回代码为404（请求的页面没有找到)、301(永久删除)、500(内部服务器错误)，将这类记录用SQL语句删除。

（4）、由GET 以外的方式完成的服务。常见的请求方法有GET , POST 和HEAD ,但是只有GET 方法反应了用户的访问行为,所以要清除GET以外的服务。

（5）、其他无关的日志。

以徐州市政府网站2008.12.01为例，对各部分数据清理的结果示例。

1.03%0.44%4.35%1.14%1.99%清理前图片网络蜘蛛失败非GET请求其他清理后41.05P.00%

图3-3 数据清理各部分所占比例

Figure 3-3 The various parts proportion of data cleaning

22

3 数据预处理

3.3.2用户识别

用户识别的目的是识别哪些用户访问了站点。在用户识别的过程中存在以下问题：单个IP对多个服务器会话，多个IP对单个服务器用户会话，多个IP地址单用户，多代理单用户以及单客户端多用户等等。基于以上情况，我们可以按照以下的规则来依次处理日志中的每条记录，从而有助于识别用户[31] [32]。

规则l：不同的IP代表不同的用户。

规则2：如果访问日志中两条记录的IP地址相同，但代理日志表明用户的操作系统或浏览器改变了，那么认为每个不同的代理就表示不同的用户。

规则3：如果访问日志中两条记录的IP地址相同，用户使用的操作系统和浏览器软件也相同,那么根据网站的拓扑结构对用户进行识别,如果用户请求的页面不能从已访问的任何页面到达,则判断这是一个新的用户。

根据上述规则确定用户识别的算法。

定义1：U={UserID,User_IP,User_Refer,User_agent},其中：UserID为用户的标识，User_IP、User_Refer、User_agent分别为用户的IP地址、引用地址和用户客户端的类型。

Log为日志文件；U为用户的集合；R为日志文件中的一条记录；R．user代表记录R 的用户；R.ip代表记录中的IP地址；R.agent为客户端浏览器的类型；R.referer用户浏览的上一页。

算法：用户识别 输入：日志Log 输出：用户集合U For 所有的记录R∈Log {

If (R．ip不同于User 中所有记录的IP)

U=U ∪ UserID++；

else if (R．agent不同于同一IP的记录)

U=U ∪ UserID++；

else if (当前页面的R．referer为空)

U=U ∪ UserID++； else

继续下一日志R；

23

工程硕士学位论文

} return U End

为了识别用户，目前己有多种方法，如cookie和内嵌用户ID、客户端软件agent、注册使用等，但现实情况是用户可能因为安全方面的考虑而关闭。

表3-2常用的用户识别方法

Table 3-2 Recognition methods for common user 方法 IP地址和代理 嵌入会话ID 用户注册 描述 假定每一个IP或代理地址对应一个用户 使用动态的方法产生ID，并嵌入用户访问请求中 用户注册并且使用唯一ID登录 私密性 优点 所需数据均体最低 现在日志中，实现简单 较低 技术简单，脱离了IP限制 可以精确跟踪一个用户的访问情况 可以重复跟踪访问 可以得到一个网站的精确访问情况 可以获得用户的所有访问情况 缺点 不能保证用户与IP/代理一一对应 没有考虑短时间内用户重复访问的情形，只有在动态网站下适用 不是所有的用户都愿意注册，且每一次访问时都愿意登录 用户如果不打开Cookie选项就无法收集信息 只能用于一些特定场合 广泛程度 广泛 多用于个性化 较低 中 Cookie 在客户端写入唯一个标识 在客户端浏览器上嵌入插件，向服务器送回浏览的信息 由浏览器记录用户访问的数据 中高 较低 多用于个 性化方法 代理软件 高 修改浏览器 最高 必须在用户使用了这种修改的浏览器时才会发挥作用 很少使用 3.3.3会话识别

会话识别是指用户在同一时间段内（一般间隔时间是25.5分钟，业界一般取30分钟）访问的页面组成一个用户会话序列，有四种识别会话的模型：页面类型模型(Page Type Model)、参引长度模型(Reference Length Model)、最大前向参引模型(Maximal Forword Reference Model)和时间窗口模型(Time Window Model)。最常采用的是时间窗口模型，如果两个不同页面访问时间的差超过一个阈值，则认为用户开始了一个新的会话。

启发式会话识别算法是常用的会话识别算法，它基于上述四种会话识别模型，其主要思想是:对于每个用户活动L，首先将第一个请求加入到第一个打开

24

3 数据预处理

的会话中，依次对照每个请求时间，如果超过时间阈值θ，则关闭当前会话并打开一个新的会话并将其作为这个会话的开始。再根据用户的浏览特性和页面之间的连接结构确定最终的会话集：假设同一用户依次发出相邻的两个请求a和b(其中a属于会话S)，ta 和tb分别表示页面请求a和b的时间戳(ta

定义2：假设某网站有n个不同的URI，表示为： URI={uri1，uri2，uri3，?urii} ，其中：1

式中，设L是用户访问日志集合，li∈L，urii = li.uri，为被存取页的超链接地址，则m个用户会话的集合就可以表示为：

S={sl，s2，s3,?sj}，1

jjjjjjsj ={ipj,(uri1j,time1j, refer1j)，(uri2,time2, refer2)，?，(urik,timek, referk)}

满足条件：

(timei+1-time1)< θ，i=1，2，?，m (timei+1-timei)< δ，i=1，2，?，m

j式中，ipj代表产生用户会话sj的用户所对应的客户端IP地址，urik代表用j户在用户会话sj中所访问的第k个uri，timek代表用户发出这次访问请求的时间，

θ、δ是预先确定的时间阐值。

算法： 生成会话集合Generate_Session(L，SessionSet)；

输入：经过用户识别后的Web服务器日志L，θ=30min，δ= lmin； 输出：会话集合SessionSet； Generate_ Session(L，SessionSet) { i=1；

r1 ={ ip1，(}； add r1 to SessionSet i=2

while (i≤|L|) {

查找 ipi在SessionSet 是否存在？ If 存在

If Timei-time1<θand （timei-timei-1<δ or urii与前面的refer相同）

25

工程硕士学位论文

ri=ri∪(}； } else

ri ={ ipi，(}； add ri to SessionSet } i++ }

3.3.4 路径完整

在识别用户会话过程中的另一个问题是确定访问日志中是否有重要的请求没有被记录，有一些原因会导致路径的不完整，例如用户在浏览的过程中使用的“后退”按钮，这就使得日志所记录的有关用户浏览的页面少于用户实际所浏览的页面数量，这就是路径缺失，若引用日志不完整，可以使用站点的拓扑结构代替。通过这种方法将遗漏的页面请求添加到用户的会话文件中。

在路径补充中遵循的一个原则就是在用户的一次会话的页面集中，除了起始页面外，每个页面同它上一个页面存在链接关系。

3.3.5事务识别

用户会话是Web日志挖掘中唯一具备自然事务特征的元素，但是，可能它对于某些挖掘算法来说粒度太粗，需要利用分割算法将其转化为更小的事务。 事务识别就是将用户会话分割为更小的事务，也就是从用户会话中次前进浏览的第一页到回退前一页组成的路径，所以我们可以结合网站结构来分割事务，分割好的事务构成事务数据库，可以在此基础上挖掘关则。

常用的事务分割方法有：引用长度(Reference Length)、最大向前路径(Maximal Forwardpath)、时间窗口(Time Window)等[33]。其中引用长度法以浏览时间为依据，把网页分为辅助页和内容页，以此来分割用户会话。最大向前路径法以Web日志访问序列中的访问链的最大向前深度来决定事务。时间窗口法则仅仅通过时间差T来分割事务，同一个事务中的任意两个页面的最大访问时间差不能超过T。

3.4 试验数据（Test Data）

下面取自徐州市政府网站Web服务器上的部分数据，测试上面的用户识别及会话识别技术。为简化表格,X 代表“Mozilla/ 4. 0 ( compatible ; MSIE6. 0 ; Windows NT 5.1) ”,Y 代表“Mozilla/ 4. 0 ( compatible ; MSIE6. 0 ; Win2dows NT

26

3 数据预处理

5. 0) ”, 这里WindowsNT 5. 0 代表的是Windows2000 操作系统,Windows NT 5. 1 代表的是Windows XP操作系统。Date均为2008.12.01，Url也用字母代替。

表3-3 原始日志记录

Table 3-3 Primitive log record 序号 1 2 3 4 5 6 7 8 9 10 IP地址 121.233.43.40 121.233.43.40 218.12.194.18 121.233.43.40 218.12.194.18 202.84.17.181 121.233.43.40 202.84.17.181 58.218.78.194 218.12.194.18 Date/Time 00:00:27 00:00:28 00:00:31 00:00:31 00:00:32 00:00:32 00:00:32 00:00:33 00:00:34 00:00:34 Url index.html a.html index.html d.html k.html index.html m.html q.html w.html s.html Refer index.html a.html index.html d.html index.html k.html Agent X X X X X Y X Y X X 将上面讨论的Web 日志预处理的几个过程中的相关算法作用于表2 中的日志记录,得到的结果如表5 所示

表3-4 经过数据预处理后的用户会话记录

Table 3-4 User session record after data pre-processing 序号 1 IP地址/Agent 121.233.43.40/X Date/Time 00:00:27 00:00:28 00:00:31 00:00:32 2 218.12.194.18/X 00:00:31 00:00:32 00:00:34 3 202.84.17.181/Y 00:00:32 00:00:33 4 58.218.78.194/X 00:00:34 Url index.html a.html d.html m.html index.html k.html s.html index.html q.html w.html Refer index.html a.html d.html index.html k.html index.html 3.5 小结（Summary）

通过对Web 日志挖掘的数据预处理部分进行研究，分析了数据预处理的各个阶段需要解决的问题和采用的解决方法，Web 日志挖掘的数据预处理的结果影响到挖掘算法产生的规则和模式，因此预处理过程也是Web 日志挖掘质量保

27

工程硕士学位论文

证的关键。

本章介绍了Web日志预处理的基本概念和方法，介绍了Web日志数据预处理的五个阶段：数据清理、用户识别、会话识别、路径补充和事务识别，并对各个阶段的任务和处理方法进行了分析。

28

4 基于模糊相似矩阵的Web日志的动态聚类

4 基于模糊相似矩阵的Web日志的动态聚类 4 Dynamic Cluster Based on Fuzzy Similarity Matrix Web Log

聚类（clustering）是指将数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。聚类不需预先定义好类，它是无指导学习，它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。聚类的应用非常广泛，在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征；在保险行业，利用数据挖掘技术，提高保险公司的成本控制、风险预测和防范能力是非常有意义的。

4.1 常用的聚类算法比较与分析（Comparison and Analysis of Commonly Used Clustering Algorithms）

为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为分裂（划分）方法，层次方法，基于密度的方法，基于网格的方法和基于模型的五大类[34]。

表4-1 聚类算法的分类

Table 4-1 Cluster algorithm classification 类别 算法 分裂（划分）法 K-MEANS算法（K-平均）、K-MEDOIDS算法（K-中心点）、CLARANS算法（基于选择的方法） 层次法 BIRCH算法（平衡迭代归约和聚类）、CURE算法（代表聚类）、CHAMELEON算法（动态模型） 基于密度 的方法 基于网络 的方法 基于模型 的方法 DBSCAN算法（基于高密度连接区域）、OPTICS算法（对象排序识别）、DENCUE算法（密度分布函数） STING算法（统计信息网格）、CLIQUE算法（聚类高维空间）、WAVE-CLUSTER算法（小波变换） 统计学方法、神经网络方法

29

工程硕士学位论文

4.1.1 基于分裂（划分）的聚类算法

给定一个有N个元组或记录的数据集，分裂法构造K个分组，每一个分组就代表一个聚类，K

(1)、K-MEANS 算法（K-平均）。该算法首先随机地选择k 个对象，每个对象初始地代表了一个类的平均值或中心，对剩余的每个对象，根据其与各个类中心的距离，将它赋给最近的类；然后重新计算每个类的平均值。聚类结果与数据的输入顺序也有明显的关系，对于“噪声”和孤立点数据也是敏感的，其时间复杂度为O(nkt)。

(2)、K-MEDOIDS 算法（K-中心点）。该算法首先首先为每个簇随意选择一个代表对象，剩余的对象根据其与代表对象的距离分配给最近的一个簇，然后反复地用非代表对象来替代代表对象，以改进聚类的质量。

(3)、CLARANS算法（基于选择的方法）。它在搜索的过程中随机性的选取一个样本，在替换了一个中心点后得到的聚类结果被称为当前聚类结果的邻居，搜索的邻居点数目被用户定义的一个参数加以限制。如果找到一个比它更好的邻居，则把中心点移到该邻居节点上，否则把该点作为局部最小量。该算法的计算复杂度大约是O (n2)。

4.1.2 基于层次的聚类算法

基于层次的聚类算法是将数据对象进行层次分解，直到满足某种条件为止，具体分解是自底向上或者自顶向下形成，分层聚类的方法可以进一步分为凝聚的和分裂的方法，分层聚类方法对样本的输入次序敏感，而且一旦一个步骤(合并或分裂) 完成，它就不能被撤销，因此在合并或分裂时必须慎重。目前基于此的算法有：

(1)、BIRCH 算法：BIRCH 算法引言两个概念：聚类特征和聚类特征树(CF) 两个参数，聚类特征是对给定子聚类的统计汇总，聚类特征树是高度平衡的树，它存储了层次聚类的聚类特征。通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算，故该算法通过一次扫描就可以进行较好的聚类，计算复杂度是O(n)。

(2)、CURE 算法：CURE 算法把每个数据点看成一簇，然后再以一个特定的收缩因子向中心“收缩”它们，即合并两个距离最近的代表点的簇。每个类有多于一个的代表点使得CURE 算法可以适应非球形的几何形状，类的收缩或凝聚可以有助于控制孤立点的影响，但参数的设置对聚类结果有显著的影响，CURE 算法的复杂度是O(n)。

30

4 基于模糊相似矩阵的Web日志的动态聚类

4.1.3基于密度的聚类算法

基于密度的聚类方法的主要思想是只要一个区域中的点的密度( 对象或数据点的数目) 大过某个阈值，就把它加到与之相近的聚类中去。该方法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。其主要算法为DBSCAN 算法、OPTICS算法和DENCUE算法。

(1)、DBSCAN 算法：DBSCAN 算法的基本思想就是检查一个对象的ε领域的密度是否足够高，即一定距离ε内数据点的个数是否超过Minpts 来确定是否建立一个以该对象为核心对象的新簇，再合并密度可达簇，它可以在带有“噪声”的空间数据库中发现任意形状的聚类。在算法复杂度上，若采用空间索引R 3 - 树，其时间复杂度为O(nlogn) ，否则仍为O(n2) 。

（2）、OPTICS 法：OPTICS 法是为了解决DBSCAN 算法中参数ε和Minpts 难以确定而提出来的。它不显式地产生一个数据集合簇，而是为自动和交互的聚类分析计算一个聚类分析方法，因此OPTICS 法产生的是一个基于密度的簇的次序集合，它的时间复杂度与DBSCAN 相同。

4.1.4基于网格的聚类算法

基于网格的方法把数据空间量划分成为有限个单元（cell）的网络结构。所有的聚类都是以单个的单元为对象的。网格聚类法处理速度快，处理时间与数据对象的数目无关，一般由网格单元的数目决定。其主要算法有：

(1)、统计信息网格( STING) 算法：STING是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。对不同级别的分辨率，存在不同级别的矩阵单元，这些单元形成了一个层次结构，高层的每个单元被划分为多个低一层的单元。高层单元的统计信息可以由计算低层单元获得，而统计信息的查询则采用自顶向下的基于网格的方法，其聚类时间复杂度为O(n)。

(2)、CLIQUE 算法：CLIQUE 算法利用自顶向上方法求出各个子空间的聚类单元。 CLIQUE 算法主要用于找出高维数据空间中存在的低维聚类，该方法最主要的优点是能发现数据子空间中的簇，另外，对数据输入顺序不敏感，对数据高维有良好的伸缩性，但需要用户输入数据聚类空间等间隔距离和密度阈值参数。

4.1.5基于模型的聚类算法

基于模型的聚类方法是给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。基于模型的方法主要包括统计学类方法和神经网络类方法。

31

工程硕士学位论文

（1）、COBWEB 算法：COBWEB 法是一个通用且简单的基于统计的聚集方法，它用分类树的形式来表现层次聚集，并用一种启发式的评估衡量标准来引导树的建立。

（2）、竞争学习：竞争学习的方法采用了若干个单元的层次(神经元) ，以一种“胜者全取”的方式对系统当前处理的对象进行竞争。这种方法要输入两个参数：结果簇的数目和每个簇中单元的数目。

4.2 模糊聚类 (Fuzzy Clustering)

在现实中，分类往往伴随着模糊性，在很多场合，一个事务是否形成一个类群，一个事务是否隶属于某个子类，都不是很分明的，因此用模糊集合的理论和方法来描述和处理聚类的问题更为方便。模糊聚类是将模糊集的概念应用到传统聚类分析中，让数据集的对象在分组中的隶属用隶属函数来确定，也就是说，对象在各分组中的隶属度为连续区间[0, 1]之间的某个值，以不同程度隶属于多个簇，而非确定性聚类中的0或1的二值逻辑。

动态聚类的基本思想是：先将所研究的n个样品各自为一类，计算它们之间的相似度或距离，选择最相似的或距离最小的两类归为新的一类，每次归类就减少一个类，直到所有样品都划到一个类为止。

4.2.1相关概念

定义1：Web模糊矩阵 若U={u1,u2,…,un}为聚类的Web对象（用户或页面）集合，设i=1,2,…,n,j=1,2,…,m,都有rij∈[0,1],则称R=（rij）nxm为Web模糊矩阵。

定义2：Web模糊相似矩阵 R为n阶Web模糊矩阵，I为单位矩阵，若R满足 若U={u1,u2,…,un}为聚类的Web对象（用户或页面）集合，设i=1,2,…,n,j=1,2,…,m,都有rij∈[0,1],则称R=（rij）nxm为Web模糊矩阵。

定义3：矩阵A=[aij]mxn称为一个Fuzzy矩阵，如果对任意i≤m及j≤n，都有aij∈[0,1]，我们约定A表示m行n列的模糊矩阵的集合。

定义4：设R是论域U上的一个模糊关系，如果R满足： 自反性 R(u,v）=1； 对称性 R(u,v）=R(v,u）；

则称R是U上的一个模糊相似关系，这里R(v,u）表示U的元素u与v的相关度。

定义5：包含模糊矩阵R的最小的模糊传递矩阵叫做R的传递闭包。记作：t（R）

定义6：模糊等价矩阵，我们把满足自反性、对称性以及传递性R2≤R的模糊矩阵称为模糊等价矩阵[38-39]。

32

4 基于模糊相似矩阵的Web日志的动态聚类

4.2.2相似度的度量

我们用[ 0,1]中的rij来表示X中的元素xi与xj的相似度的程度，为确定相似系数rij，可以用以下方法来进行[40]。

1、夹角余弦[1]

mrij =

?xk?1m2ikk?1ikxjkm （1）

jk?x?xk?12、数量积法 1, i=j rij =

1mxikxjk,i?j （2） ?Mk?1M= max(?xikxjk) k?1i?j3、绝对值减数法

rij = 1-c?|xik?xjk| （3）

k?1mm4、算术平均最小法

2?xik?xjkmrij =

?(xk?1mk?1m （4）

ik?xjk)5、最大最小法

rij =

?(xk?1mk?1ik?xjk) （5）

ik?(x?xjk)4.2.3 Web模糊聚类

在访问信息挖掘中, 模糊聚类的应用主要体现在根据数据预处理后的用户会话信息对用户、页等对象进行分类。

1、 客户群体的模糊聚类算法

在一定时间段内, 根据访问信息挖掘的数据预处理阶段获得的用户会话, 得

33

工程硕士学位论文

到各用户共同访问的页面数等信息, 然后使用模糊聚类方法对用户聚类。

用C表示客户集合, C={C1,C2,…,Ci,… Cm}；用U表示某一站点URL的集合,U={U1,U2,…,Uj… Un}，客户Ci的浏览子图Εci可用站点URL 表示, 即：

Εci={(Uj,fEc(Uj) ︱Uj∈U }

i其中, fEic(Uj)→[0,1]是客户Ci和URL(Uj)之间的关联度函数：

fEc(Uj)=

ihits(Uj)?mi?1hits(Ui) （6）

式中的n为n为URL的数量, hits(Uj )是客户Ci访问URL（Uj）的次数。这样, 就可以根据(5) 式和(7) 式建立模糊相似矩阵, 根据〔6〕式构造相似类, 合并相似类中的公共元素得到等价类。

2、 Web页面的模糊聚类算法

定义与客户群体聚类算法相同, 客户的访问情况可用URL（Uj）表示，即 （Uj）之间的Suj={(Cj,fS(Ci) ︱Ci∈C },其中,fS(Ci)→[0,1]是客户Ci和URL

ujuj关联度：

fSu(Ci)=

jhits(Ci)?mj?1hits(Cj) （7）

式中m为客户的数量, hits (Ci)是客户Ci访问URL（Uj）的次数[41-42]。

4.2.4 Web模糊聚类过程模型

Web模糊聚类的过程就是将Web的访问日志数据集经数据预处理后得到数据矩阵，通过式(6)、（7）将数据矩阵标准转化为适合 [ 0,1] 的Web模糊矩阵，再使用模糊聚类方法进行聚类。在模糊聚类方法中计算被分类对象间相似程度的统计量的方法有很多，常用的有夹角余弦方法、数量积法、绝对值减数法、算术平均最小方法以及最大最小方法。本文在计算被分类对象间相似程度时使用最大最小方法式（5）建立Web模糊相似矩阵，将Web模糊相似矩阵通过循环自乘转化为模糊等价关系，在模糊等价关系的基础上进行模糊聚类分析，最后输出聚类结果。

Web模糊聚类过程模型如图4-1：

34

4 基于模糊相似矩阵的Web日志的动态聚类

Web访问日志 数据清理 Web数 据矩阵 数据标准化 Web模 糊矩阵 标定 Web模糊相似矩阵 聚类过程 聚类结果 图4-1 Web模糊聚类过程模型

Figure 4-1 Web fuzzy clustering process model

4.3 利用最大-最小相似性度量的实例 (Real Examples Using the Maximum – Minimization of Fuzzy Similarity Measure)

我们取某网站的一日内的访问日志，原始日志是248050条，经数据清理后10933条，取其中的部分数据，假设Web站点的页面集合是P={p1,p2,p3,p4,p5,p6,p7,p8},经数据预处理后Web用户的集合为U={u1，u2，u3，u4，u5，u6，u7，u8},网站拓扑结构如图4-2，Web用户访问Web页面的次数如下：

U1:P1(15)-P2(10)-P5(3)-P3(11) U2:P1(10)-P3(5) U3:P1(8)-P3(5)-P6(4)

U4:P1(20)-P3(17)-P6(11)-P8(5) U5:P1(17)-P3(10)-P7(3) U6:P1(25)-P4(20) U7:P1(12)-P2(11)-P3(10) U8:P3(25)-P6(13)-P7(10)

P8 P5 P6 P7 P2 P3 P4 P1 图4-2 网站拓扑结构图

Figure 4-2 Site topology structure map

根据上面提供的数据构造数据矩阵，

35

工程硕士学位论文

?1510110300?10050000?8050060R=?2001700110?170100003?250020000?120100000?0025001310?0?0?0?8? 0?0?0?0??根据式（7）得到它的模糊关联度矩阵

?0.390.26?0.670?0.420R′=?0.360?0.570?0.560?0.360.330??00.2800.08000?0.3300000?0.26000.3200?0.30000.2000.14? 0.330000.10?00.440000?0.3100000?0.52000.270.210??根据最大最小方法式（5）构造的模糊相似矩阵为：

?10.500.480.4710.520.49??10.69?R\=1??????0.500.820.520.4910.240.390.270.220.3910.820.500.460.490.500.2210.16?0.20?0.36?0.33? ?0.28?0?0.18?1??根据模糊矩阵构造的动态聚类图：

U1 U2 U3 U4 U5 U6 U7 U8 λ=1 {U1},{U2},{U3},{U4},{U5},{U6},{U7},{U8} λ=0.8 {U1,U7},{U2,U5},{U3},{U4},{U6},{U8} λ=0.6 {U1,U7},{U2,U5},{U3,U4},{U6},{U8} λ=0.5 {U1,U2,U3,U4,U5,U6,U7},{U8}

4.4 小结 (Summary)

模糊聚类分析中的传递闭包方法和普通的聚类方法一样，首先要计算出样品之间的相似度，即建立Fuzzy相似关系，然后进行动态聚类，实验表明，该方法可以很好的发现相似的客户群体以及相关的Web页面。

36

5 基于Web日志的实时推荐模型

5 基于Web日志的实时推荐模型

5 A Real-Time Recommendation Model Based on Web Log

5.1问题的提出（Set up Problem）

近年来，Web使用挖掘技术能够捕捉到用户的浏览行为和行为的方式作为智能的Web站点，一些研究就是使用的关联规则挖掘作推荐系统，其中大部分的研究也试图在生成推荐或为实时的动态推荐系统之前发现所有的关联规则。

网站实时推荐系统研究的最主要的热点是高质量、高效能的推荐算法的研究，因为推荐算法处于整个推荐系统的核心位置，它的性能最终决定着自适应推荐系统性能。目前主要的推荐技术包括[43]：

（1）、协同过滤推荐

它基于相同类别用户的资料得到用户的推荐，此种推荐的个性化程度高。协同过滤的最大优点就是对推荐对象没有特殊要求，能处理非结构化的复杂对象，但随着站点结构、内容的复杂度和用户人数的不断增加，协同过滤技术的一些缺点逐渐暴露出来，主要有：稀疏性、扩展性及精确性，用户数据相当稀疏，难以找到相似用户集，导致推荐效果大大降低，在数量较大的情况下，推荐的可信度随之降低。

（2）、基于内容的推荐技术

它是信息过滤技术的延续与发展，系统基于用户评价对象的特征学习用户的兴趣，依据用户资料与待预测项目的匹配程度进行推荐，如新闻组过滤系统NewsWeeder[44]。

（3）、基于功能的推荐

它是根据对用户使用项目的功能进行计算的，核心问题是如何为每个用户创建功能函数，并考虑非产品属性，如提供商的可靠性和产品的可用性等。

（4）、基于用户统计信息的推荐

推荐系统基于用户个人属性对用户进行分类，在基于分类中的用户进行推荐时不要求有一个历史的用户数据，而协同过滤和基于内容的推荐技术都需要。

（5）、基于知识的推荐

在某种程度上可以看成是一种推理技术，各方法因所用的知识不同而有明显区别[45]。

（6）、基于关联规则的推荐

它以关联规则为基础，把已购商品作为规则头，推荐对象作为规则体，其中

37

工程硕士学位论文

联规则的发现最关键且最耗时，是算法的瓶颈，但可以离线进行，商品名称的同义性问题也是关联规则的一个难点。

基于上述的推荐技术出现了一些研究，例如：WebWatcher系统[46]，采用跟踪用户浏览Web站点的行为或者访问路径方法，学习用户的访问模式，将用户可能感兴趣的Web页在线推荐给用户。还有利用Apriori 算法[47]用于预处理之后的数据，挖掘出频繁项集，同时把用户最近访问的几个页面和挖掘出频繁项集相匹配，关联规则挖掘计算复杂性高，不易增量挖掘。

目前已经存在很多的实时推荐系统，主要存在以下一些问题：

（1）大多数推荐系统对新用户和访问站点较少的用户的信息推荐考虑不够，因为新用户和浏览站点较少的用户被系统收集的用户信息较少，采用的一些推荐算法并不合适。

（2）算法的伸缩性，推荐系统在处理大规模数据量时面临着越来越严重的问题，难以满足系统实时性要求。

本章研究的问题就是利用 Web使用挖掘动态的引导用户选择适当的网页，我们的研究是基于以往的访问记录，立即推荐给下次合适的网页。通过对当前网站推荐系统以及相关技术的分析，本章设计一个实时推荐系统结构RTRS（real-time recommendation system），主要着重解决以下问题:

（1）对Web日志进行挖掘时，对Web日志文件进行有效的预处理。 （2）在预处理的基础上，采用构造BP树（Brows Pattern Tree）的算法发现用户的频繁访问路径，产生推荐集进行实时推荐。

5.2 RTRS系统的模型（RTRS System Model）

本章给出的模型是根据Web以往的访问日志，应用数据预处理的技术，形成事务文件，然后构造BP树，利用实时推荐算法对事务文件进行挖掘，从而挖掘出用户浏览的频繁访问路径，形成频繁项集，基于这些关联规则设计了一个实时推荐的模块，为用户提供推荐服务，使得浏览的过程就是一个自适应的过程。

实时推荐的模型如图5-1：

38

5 基于Web日志的实时推荐模型

数据预处理站点拓扑结构数据清理用户识别会话识别路径完整事务识别访问模式挖掘模糊聚类技术生成用户和页面的聚类离线模块用户事务文件Web服务器日志文件 增量生成BP树序列事务文件基于关联规则的网站实时推荐Web服务器客户端浏览 实时推荐

在线模块图5-1 RTRS系统的模型 Figure 5-1 RTRS system model

离线模块包括数据预处理子模块和访问模式挖掘子模块[48]，其中：数据预处理首先需要对原始的Web日志文件进行数据预处理，小型的网站每天的日志文件也就几M或者几十M，而大型的网站每天的日志文件则会超过几百M甚至几G，所以对于如此海量的日志文件进行预处理会非常耗时，必须把这一步工作放在离线模块中来进行，否则会大大影响实时推荐的速度。访问模式挖掘是对用户事务文件运用第四章中的模糊聚类技术对用户和网页进行聚类，为实时推荐模块的推荐算法打下基础。

在线模块的推荐集是由与当前用户访问操作窗口相匹配的访问操作模式组成，每一个访问操作模式都是根据用户当前访问站点的方式，结合用户历史访问模式发现潜在的、有用的、相链接的Web页，从而为用户提供实时推荐服务。这些被推荐的链接Web页被添加到用户当前已经访问过的Web页面后面。推荐的生成依赖数据挖掘和分析的结果，也就是用户的访问行为模式。在线模块跟踪用户当前点击流及应用推荐算法计算生成推荐集，实现实时推荐，在增量构造BP树时，只需扫描一次序列事务数据库即可，同时挖掘算法也仅仅挖掘相关部分的结构，减少计算时间，所以整个框架的效率很高。

5.3 在线模块实时推荐（Real-Time Recommend Online Modul）

在线模块根据用户的访问，增量构造BP树，增量的模式可以很快影响下一次的推荐结果。

39

工程硕士学位论文

5.3.1 基本概念

定义1：设对数据进行预处理后可以得到页面集合E={e1,e2,…,en}和序列事务集合S={s1,s2,…,sm},，其中S ∈E是包含一系列E中的一个序列事务，模式X代表浏览行为，我们把项集X中所含的项目个数称为项集的维数或长度，记为：|X|

定义2：设有项目集X∈E，设count(X)为X在S出现的次数，count（S）为S中事务的总数，则X的支持度定义为：Support（X）=count(X)/count(S),如果Support（X）大于用户给定的最小支持度minsp，则称X为频繁项目集[49]。

5.3.2 算法描述

（1）、访问模式树BP树（Brows Pattern Tree）的定义 它是由项头表（header_object）和前缀树（prefix_tree）组成。

项头表由三个域组成：名称（Item）、支持度计数、节点链，其中：支持度计数是指该节点的访问数目，节点链指向相同名字的前缀树的第一个节点。

前缀树包含四个子域：名称、计数、子节点链、节点链，其中：计数代表的是访问这个节点的数目，子节点链是指向前缀树中的下一个节点，节点链是指向前缀树中相同名字下一节点的链接，如果没有下一连接，用“Null”表示[50-51]。

（2）、BP树的构建

首先建立根节点，用Root表示，然后扫描事务数据库S，为第一个事务创建一个分枝，然后将后面的事务插入到树中，当处理一个事务时，首先查看当前事务与树已有的分枝之间是否有相同的共享前缀，如果有，则沿共同路径的前缀上的每个节点的计数增加1，为跟随在前缀之后的项创建节点并与调整相应的项头表中相同节点的链接，如果没有则创建一个新的分枝，计数置为1[52]。

（3）、页面推荐算法

页面推荐算法由二个算法组成：一个构造候选子集，一个在候选子集的基础上产生推荐集。

推荐算法首先遍历项头表，找到与浏览行为X[1]相同的节点，通过发现其节点链一直到查找下去，直到节点链为Null的节点，只需访问相关部分，对树进行修剪，得到第一个候选节点，再通过X的长度L，来控制挖掘的深度，返回与X[index]相同的下一级候选节点，一直持续到项集的长度，再挖掘所有的候选子项后，合并相同的节点，计数求和，假设这组计数满足之前定义的最小支持阈值ξ，记录它的名字作为推荐结果组，否则剪切。

构造候选集算法

输入：BP树，项头表，访问事务X

40

本文来源：https://www.bwwdw.com/article/7ao5.html