工程硕士学位论文
?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