基于用户访问模式的数据挖掘技术在大型图书网站中应用的研究

王宇杰，乔聪

0 引言

数据挖掘是为了帮助用户处理大量存在的数据，发现其后隐含的规律性，同时将其模型化，完成辅助决策的作用。

数据挖掘技术分支很多，其中，基于用户访问模式的挖掘（也称 Web日志挖掘或使用记录的挖掘）是用于发现用户行为及潜在顾客的信息，该种数据的挖掘有助于合理建造网站，帮助更好地组织设计网站主页；帮助改善市场营销决策，有助于商家制定促销策略。所以，对于一个企业网站的建设来说，用户访问模式的挖掘有重要的意义。

本文结合一个大型图书网站的建设，来研究基于用户访问模式的数据挖掘技术在大型网站中的应用。

1 基于用户访问模式的数据挖掘在大型图书网站中的实现

1.1 用户访问模式（Web使用记录）挖掘的基本流程

由于Web包含了丰富和动态的超链接信息，以及Web页面的访问和使用信息，这为数据挖掘提供了丰富的资源。我们可以将Web挖掘一般地定义为：从与WWW相关的资源和行为中抽取感兴趣的、有用的模式和隐含信息。一般Web挖掘可分为3类：Web内容挖掘 (Web content mining)、Web结构挖掘 (Web structure mining)和Web使用记录的挖掘(Web usage mining)。Web使用记录挖掘的主要目标是Web的访问记录中抽取感兴趣的模式。WWW中的每个服务器都保留了访问日志 (Web access log)，记录了关于用户访问和交互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。

在模式发现中，首先要解决的问题就是数据的预处理，它主要包括如下两个部分：①数据清理 (data cleaning)，包括无关记录的剔除、判断是否有重要的访问没有被记录、用户的识别等问题；②事务识别 (transaction identification)，是指将页面访问序列划分为代表Web事务或用户会话的逻辑单元。在对事务进行了划分后，就可以根据具体的分析需求选择访问模式发现的技术，如路径分析、关联规则挖掘、时序模式以及聚类和分类技术。路径分析(path analysis)可以用来发现 Web站点中最经常被访问的路径，从而可以调整站点的结构。在 Web使用记录挖掘的环境下，关联规则挖掘的目标是发现用户对站点各页面的访问之间的关系，这对于电子商务是非常有用的。

对 Web日志进行分析和挖掘要经过一系列的数据准备工作和建模工作。一个基本的流程如下：

（1）要对Web日志进行清洗、过滤和转换，从中抽取感兴趣的数据；

（2）URL、动作、资源的类型、资源的大小、请求的时间、在资源上停留的时间、请求者的Internet域名、用户、服务器状态作为Data Cube的维变量，将对模块、页面和文件请求次数、来自不同Internet域请求次数、事件、会话、带宽、错误次数、不同浏览器种类、用户所在组织作为度量变量建立Data Cub；

（3）利用数据挖掘技术 (如特征、分类、关联、预测、时间序列分析、趋势分析) 进行 Web流量分析、典型的事件序列和用户行为模式分析、事务分析，可以回答成分和特色在什么上下文中被使用，什么是典型的事件序列；在用户中是否有共同的行为模式，是什么；不同用户群在使用和行为上有什么差异；用户的行为是否随时间变化，怎么变化等问题。

通过分析Web存取日志能帮助理解用户的行为和Web结构，因此，可以改进Web页面的设计和Web应用程序，发现潜在的电子商务客户。Web Log数据挖掘提供了深层次的报告，像时间序列分析、相关、分类等。通过使用这类Web Log文件，可以进行一些研究工作，如系统性能分析，通过Web缓存改进系统设计、Web页面预取、Web页面交换 (swapping)；认识 Web信息访问的本质；理解用户的反映和动机。有些研究提出了可适应站点 (adaptive site)的概念，即可以通过用户访问模式的学习改进其自身的 Web站点。

1.2 大型图书网站用户使用模式挖掘系统简介

用户使用模式的挖掘是 Web使用记录挖掘的一个重要组成部分。由于大型图书网站是一个动态性极强的信息源，其信息不断发生更新。出版物的信息越来越多，链接信息和访问记录也处于频繁地更新之中。网站面对的是形形色色的用户群体，大部分用户面对由一两个关键字搜索出来的几十种出版物，不清楚哪一个是对自己有用的信息，极容易不知所措迷失方向，也极容易失去耐心。所以从大量的用户点击出版物的详细信息行为中发现用户使用模式，并不断地更新这种知识，有非常重要的意义。

为了简化数据的预处理过程，使挖掘出来的用户使用模式更有针对性，我们从以下两个方面对用户的点击行为进行了显式记录：①用户进行简单查询的信息；②用户查看出版物详细信息的行为。对这两方面的用户行为记录不断地进行挖掘和更新挖掘，基本上可以满足我们的初始目标。

在出版物查询模块的建设过程中，我们精心构建了用户导航系统。导航系统主要向用户提供如下服务：根据用户以往所查询的出版物种类，向用户推荐一些新的出版物，这些出版物是通过挖掘其他广大用户的出版物查询记录而确定的，对用户有很强的针对性和指导意义。

用户提交了一次查询以后，系统不仅会返回符合查询条件的出版物信息，还会根据用户提交的查询内容，搜索已经挖掘出来的用户行为模式关联规则知识库，得到与用户此次查询相关联的查询关键字，这些关键字经过剪枝（去除用户已经查询过的关键字）和排序（按支持数的多少排序）返回给用户。同样，当用户点击了某一出版物的详细信息链接以后，系统不仅返回这一出版物的所有属性，还返回与这一出版物相关联的出版物的链接。用户可以轻松地找到自己所希望查询的出版物信息。

下面详细地讨论网站中数据挖掘的实现过程。

1.3 系统数据结构

数据库中的出版物信息表包含有所有出版物的标准号、出版物名称、类型、分类、学科所属专业、适用专业、读者层次、作者、定价、封面、目录、内容简介、作者简介、专家点评等等详细信息，其中标准号是其主键，每一种出版物都有自己唯一的标准号。而在用户管理模块中，每个用户都有自己详细的注册信息，包括账号、姓名、性别、出生年月、职业、学历、收入、地址、兴趣爱好等等，还有一些用户自己设定的个性化参数，如是否愿意接受网站提供的导航服务等，注册账号是其主键。

这样，我们在记录用户的点击行为时，所需要记录的数据量就非常小。顾客点击出版物详细信息的行为记录表和简单查询记录表的结构分别如表1所示。

表1 数据记录表结构

用户账号（user_id）和出版物标准号（bzh）分别用来唯一地定位用户和出版物信息。

提交时间（rq）是一个 date类型，Oracle的这一 date类型数据中包含有用户提交购物表单的准确日期和时间。

命中出版物条目数（shoot）字段里存放这一查询条件下返回的出版物的数量。

来源页面（referer）里面包含着用户点击此出版物详细信息链接的所在的页面信息，它可能指向这么几个地方：网站首页，简单查询结果页面，高级查询结果页面，出版物推介页面等。这一字段主要用来统计和挖掘用户浏览网页的习惯。可以注意到，用户的每一次查询行为和每一次浏览出版物详细信息的行为都会作为一条单独的记录保存下来。

导航系统真正的核心是关联规则知识表，它是用来存放经过挖掘后产生的关联规则知识的。由于关联规则知识的多样性，我们把表分成多个子表来管理，分别是1-项集的规则表、2-项集的规则表等等依次类推。例如2-项集的规则知识表结构如表2所示。分开存放可以提高检索速度，节省数据空间。

表2 项集关联规则知识表

bzh1，bzh2，和bzh分别是一个2 项集规则的三个元素，它们共同组成规则（bzh1∧bzh2）⇒ bzh。conf字段里保存着这条规则的置信度。

1.4 数据预处理

一个大型交易数据库中包含有很多信息，它可以是抽象的概括的，比如某种职业的用户喜欢买某一类型的书（多层规则挖掘），也可以是具体的明细的，比如人们在买完某一本书之后又接着买了另外一本书（序列规则挖掘）。由于条件所限，我们只进行了单维布尔关联规则的挖掘，也即所有用户购买图书出版物规则的挖掘。关系数据库仅仅是将所有信息结构化保存，并不考虑现实中数据之间的逻辑联系，所以在进行挖掘以前，必须根据挖掘的特性对数据进行预处理。

如前所述，用户的点击行为记录中包含有四个字段，但要挖掘的只是出版物之间的关联规则，并不考虑用户本身的各种属性及点击的时间之间的关系等，所以真正用到的只是其中的标准号（bzh）字段。数据预处理的主要工作就是把同一用户在一次登陆中提交的查询或者点击的出版物详细信息链接整理成为一条新的记录。判断用户是否是一次登陆的方法是，同一用户ID的两条记录之间的时间差小于一个session的存活时间。具体方法是，在数据分析处理计算机上检索用户购买行为记录表，把记录表中的用户账号（user_id）和出版物标准号（bzh）或查询关键字（keyword）按用户账号和提交时间（rq）排序后提取到数据分析计算机上来，然后把相同账号的记录时间差小于20分钟的所有记录分别作为一条新的事务记录保存在一个文件中。这样就形成了可在其上进行关联挖掘的数据文件，其中每一个标准号就是这条事务中的一个项目。

1.5 应用挖掘算法

网站在最初运行一段时间后，数据挖掘系统要进行第一次基础挖掘，基础挖掘要用改进的Apriori算法进行，这样不仅能得到数据的频繁项集信息，也可以得到其负边界信息。以后每经过一段时间的运行，数据挖掘系统就要进行更新挖掘，更新挖掘算法使用增量式更新算法。应用这一算法，不仅能够更新整个数据库的关联规则知识，还可以得到新增数据库的关联规则，这样就可以为顾客提供全面精准的导航服务了。数据挖掘系统结构如图1所示。

每一次更新挖掘时，对用户行为记录表进行挖掘前的预处理以后，都要将其中的记录进行备份，并将原记录表清空，以使下次处理的数据都是新的数据。而每次进行增量式更新挖掘后，就把新的事务数据库并入原数据库中，作为一个新的“原数据库”以准备下一次挖掘。

图1 数据挖掘系统结构图

更新挖掘出来的整个数据库的频繁项集信息和新增数据库的频繁项集信息分别存放在不同的文件中，以备规则生成程序来检验它们的置信度情况，真正生成关联规则知识。

1.6 规则生成

由行为数据库中的事务找出频繁项集以后，由它们产生强关联规则（既满足最小支持度，又满足最小置信度）的方法是直接了当的。对于置信度，可以用下式来表示，其中条件概率用项集支持度计数表示。

● 对于每个频繁项集l，产生l的所有非空子集。

由于规则由频繁项集产生，每个规则都自动满足最小支持度。当运行算法产生频繁项集后，新增数据的频繁项集和整个数据库的频繁项集连同它们的支持度会分别存放在散列表中，使得它们可以快速被访问。在规则形成阶段，把新增数据库中频繁项集形成的规则和整个数据库中频繁项集形成的规则进行合并，既如果有相同的规则的，按它们中置信度大的那个作为最终置信度进行保存。

关联规则可以是多个项集关联一个项集，也可能是一个项集关联多个项集，也可能是多个项集关联多个项集。规则生成后，按照规则的条件项集数目分别保存入相关的关联规则知识表中，一对多或者多对多的关联规则分成多条规则存放在表中，每一个结果项目都可以作为一个独立的规则来看待。

这样，数据经过预处理，挖掘频繁项集，生成规则并写入数据库后，就可以作为知识对用户的新查询行为提供建议了。

1.7 关联规则知识的应用

挖掘得到的关联规则知识存放在关联规则知识表中（如表3-2），在实际运用中，根据用户本次登陆以来的提交的内容从多到少依次搜索3-项集知识表、2-项集知识表和1-项集知识表。具体方法是，如果是首次提交，就只搜索1-项集知识表；如果是第二次提交，就把这两次提交的内容作为两个条件先查询2-项集知识表，然后再用第二次提交的内容查询1-项集知识表；第三次及以后查询的方法同上。

把满足关联条件的条目所指向的书目标准号组合在一起，按照各个条目的置信度指数进行排序，然后按顺序全部或者取前五个同用户所要查询的内容一起返回给用户，使用户在得到自己想要查询的内容的同时，还可以得到与所提交的条件有关的其他书目的快捷的链接，从而方便了用户的查询过程。

2 小结

本文首先介绍了基于用户访问模式的数据挖掘对对大型系统的重要性，然后结合大型图书网站的建设，详细介绍了用户访问模式（Web使用记录）挖掘的基本流程，接着详细介绍了数据结构的设计，数据预处理，挖掘算法的应用，规则的生成等关键性的数据挖掘技术，最后介绍了产生的规则的应用。

[1] Park J S, Chen M S, and Yu P S. An Effective Hash-based Algorithm for Mining Association Rules.In Proc. 1995 ACM-SIGMOD Int.Conf. Managemeng of Data, San Jose,CA, May1995.

[2] 郑秀丽,王乐宁,陈中柱.基于数据挖掘技术的电子商务客户潜力开发方案.计算机工程与应用,2002-05,194-195.

[3] 韩家炜,孟小峰,王静,李盛恩.Web挖掘研究.计算机研究与发展,2002-04,38(4),405-414.

[4] 陆丽娜,杨怡玲,管旭东,魏恒义.Web日志挖掘中的数据预处理的研究.计算机工程,2000-4,26(4),66-72.

[5] Tomasz Imielinski, Leonid Khachiyan,Amin Abdulghani.Cubegrades:Generalizing Association Rules. Data Mining and Knowledge Discovery, 6, 219-257, 2002.

[6] 寇育敬,王春花,黄厚宽.约束关联规则的增量式维护算法.计算机研究与发展.2001-08,38(8),947-951.

[7] Jiawei Han, Micheline Kamber著.范明,孟小峰等译:数据挖掘:概念与技术.机械工业出版社,2001.