基于web使用挖掘关联规则的网站个性化系统(翻译)

基于web使用挖掘关联规则的网站个性化系统

出处：ACM SIGMOD workshop on research issues in data mining and knowledge discovery 2001

摘要

Web早期网站为了吸引参观者所采用的个性化工具主要依靠在服务器日志上捕捉到的点击流数据。我们具有大容量的数据，但是用户和点击率和知识资源依然稀缺， 标准协作过滤技术（collaorative filtering） 可测量性和效率方面都有问题。类似聚类的web使用挖掘技术是依赖用户事务数据的离线模型发现，可以提升协作过滤技术的可测量性，然而，会降低推荐的精确率。本文提出了一种有效且可扩展的基于关联规则发现的个性化技术。通过对真实web使用数据的详细地经验估测，我们提出了一种方法学，他可以提高推荐的有效性，同时保持传统写作过滤技术如k近邻算法的可计算收益。

关键字：个性化，关联规则，web使用挖掘，协作过滤

1.介绍

构建个性化推荐系统最成功，使用最广泛的技术是协作过滤（CF）[20]。给定一个目标用户的活动记录，基于CF的技术例如k近邻法，将之与其他用户的历史记录相比较，从而发现最有类似体验和兴趣的k个用户。一个访问者的数据将会根据与他具有相似项的等级，相似的访问页，或者相同的购买记录而判断它属于谁的邻居。进行邻居识别然后可以用来为当前活动用户推荐一些尚未被访问和购买的信息。

CF技术有许多众所周知的限制[17]。其中很多与可测量性和效率有关。基本上K近邻算法在建立邻居阶段需要在线处理，对于大数据集来说这段时间显得不可接受。当然也有很多优化的策略[3，18]，包括相似索引和维度缩减。

设计有效的web个性化系统的问题是提升CF在离线模型发现过程的可测量性的同时保证全部推荐系统的有效性。而且，系统的有效性在覆盖范围和精确性方面必须是可度量的。推荐引擎的精确度直接影响推荐系统的精确性，而覆盖范围将涉及到推荐系统生成用户可能访问到地页面的能力。这是一个推荐系统最基本的评价标准。比如在电子商务领域，低精确性将会对用户产生困扰，而低覆盖率可能会导致在用户导航的关键点漏掉交叉出售（cross-sale）和顶级出售（up-sell）的机会。

近年来，人们对web使用挖掘的兴趣和所作的工作不断增加[16]，因为它是一种重要的获取和对用户行为模型进行坚膜的方法，起源于电子商务只能。Web使用挖掘技术例如聚类使用用户事务的离线模型发现，可以用来提升CF的可测量性。例如，以前的研究[9，10，12]实现了基于用户事务和浏览页聚类的自动个性化系统。然而推荐精确度不够高。一个解决的方法是使用预处理技术提升性能，比如标准化和大量过滤。另一个方法是考虑订购信息。相对于聚类和关联规则这样的非序列化模型而言，序列化模型包含更准确的用户导航行为的信息。使用序列化模型进行预测型用户建模也已经得到广发研究[5，14，19]。这些研究的主要目的是进行业面的预提取以提升服务器效率（比如预取用户下一个将要提取的页面），降低网络延迟。但在个性化的环境下，这样的导航式序列化经常导致产生的推荐系统的覆盖范围不够大。

最近的一些研究考虑了在推荐系统中使用关联规则[6，7]。然而大部分研究发现所有的关联规则比生成推荐页面（推荐阶段需要搜寻所有规则）或在特定用户邻居的子集中关联规则的实时生成的优先级要高。也有少数在用户历史记录添加支持度阈值等方法来对数据进行压缩从而提高推荐的效率。

本文我们从点击流数据中使用关联规则为推荐系统提出了一个可测量的框架。我们特别建立了一种适合于推荐系统的频繁项集发现和存储的数据结构。我们的推荐算法使用这种数据结构能实时有效的产生推荐内容，而不需要从频繁项集里面生成所有关联规则。而且通过详细的经验估测，我们对不同浏览页和不同大小的用户历史记录使用不同支持度，我们的框架能克服目前使用关联规则的缺点，同时比k近邻等直接的方法在覆盖范围和精确性方面能获取更好的结果。

2.基于关联规则的个性化框架

通常来说，基于使用记录挖掘的web个性化系统[10]包含三个阶段的工作：数据预处理和事务识别，模型发现，推荐内容的生成。其中，推荐阶段使用的是一个实时组件，其他两者是离线运行的。模型发现阶段包含关联规则发现，序列化导航模型发现，用户或会话的聚类，浏览页或产品的聚类。推荐系统将会考虑活动用户会话和提供个性化内容的模型。个性化内容包括与用户使用模型匹配的推荐的链接，推荐的产品，零售广告等。我们展示了这个通用框架的一个实例，其中推荐内容可以根据匹配的当前的活动用户会话生成，工具是对用户事务的关联规则的模型发现。首先，我们简要讨论一下数据准备和模型发现过程，然后主要讨论我们推荐引擎的细节。

2.1数据准备和模型发现

基于数据使用记录的个性化服务的开始和关键的部分是数据预处理过程。其中的高层次任务包括数据清理，用户识别，会话识别，浏览页识别，缓存中丢失的引用页的推断。为了在每个用户会话区分相关浏览页的子集，数据预处理阶段优先任务是事物识别。页面识别决定针对单个浏览器哪些网页文件被访问。对网站使用cookies或者嵌入会话ID将会使用户和会话识别变的简单。如果没有这些有利的信息，那么用户和会话识别需要依赖启发式（heuristic）学习的方法。这些细节在[4]中有详细介绍，我们不再深入讨论。

以上预处理过程最终会得到n个浏览页的集合，还有m个用户事务的集合，其中每个是的子集。我们把每个事务看作长度为l的序列：

，

在这里，每个，，是事务中对应页面的权重。权值的确定可以有很多方式，在这里我们根据点击流，主要数据来源是服务器访问日志。我们可以为浏览页选择两种权值：权值可以是一个二进制数，表示一个产品购买是否发生，或者事务中的一个文档是否被访问；或者可以是在用户会话中关联页面的持续时间。既然我们主要讨论关联规则挖掘，我们在用户事务中取浏览页的权值为二进制数，而且，我们不考虑浏览页中的次序问题。于是一个事务可以看作是一个浏览页的集合： 。

关联规则根据同时发生的事务获取项之间的关系。在web事务的例子中，关联规则就是根据用户导航模型获取浏览页之间的关系。目前我们使用Apriori算法[2，15]。Apriori算法首先找出在多个事务中频繁（频繁度至少要和用户的最小支持度相等）同时出现的项集（在这里是在预处理的日志里面的浏览页），这样的项集被称为频繁项集。

给定一个事务集和上的频繁项集合，每个项集的支持度定位为：

支持度的一个重要属性是它的向下封闭性：如果一个项集不满足最小支持度的标准，那么他的超集也不满足。这个属性对于Apriori算法每次迭代的搜索空间的优化是最基本的。

满足最小信任阈值的关联规则将从频繁项集中生成。关联规则是这种形式的表达式，这里和都是项集，是的支持度而是的置信度，通过给出。

使用全局最小支持度阈值的一个问题是发现的模型将不包含“稀值”（rare）， 但这些“稀值”是在事务数据中可能不会频繁发生但非常重要的项。这在当前使用环境中是特别重要的:当处理web使用数据时，经常会有这样的例子，就是用户通过深层次的引用才到达的内容或产品页面的频率相对要低于在用户导航页面上最靠前链接的那些页面。然而，对于有效的web个性化服务而言，获取包含这些项的模型是非常重要的。Liu et al.[8]提议了一种挖掘方法，使用多个最小支持度，并允许用户针对不同的项指定不同的支持度阈值。在这种方法中，一个项集的支持度被定义作包含在这个项集中所有项集的最小支持度。对于潜在的包含稀值的项集也可以指定多个最小支持度。利用实验数据，我们的在下节中将展示多支持度的关联规则的使用能保持推荐内容的精确性，同时扩大覆盖范围。

2.2推荐引擎

推荐引擎的任务是以频繁项集作为输入，通过匹配当前用户行为与发现的模式，生成每个用户的推荐集。推荐引擎是一个在线处理模块，因此它的效率和可测量性是很重要的。在本节内容，我们介绍一种存储频繁项集的数据结构和推荐生成算法，这种算法使用这种数据结构直接从项集中实时生成推荐集而不用首先生成关联规则。

在当前活动会话中，我们用一个固定大小的滑动窗口获取当前用户的历史记录的长度。例如，如果当前会话（窗口大小为3）为，并且用户引用页面为，则当前会话变为。既然用户在发现需要的信息时经常执行后退或者前进操作这是非常有意义的。而且使用用户早期的历史记录生成推荐集并不是很合适。于是，大小为的滑动窗口的只允许最后第n个访问页影响推荐值。

推荐引擎匹配当前用户会话窗口发现候选浏览页集。给定一个活动会话窗口，我们只认为所有大小为的项集满足支持度的阈值和包括当前会话窗口。每个候选页面的推荐值是根据关联规则的置信度得出的，而关联规则的结果只包含将要的被评价的浏览页。如果规则不小于特定置信度阈值，候选页面将被加到推荐集中。

为了方便搜索包含当前会话窗口的大小为的项集在挖掘过程中，发现的项集被保存在一个有向无环图中，这里我们称它为频繁项集图。聘繁项集图是在[1]中所说的辞典编辑树结构的一个扩展，图有不同层次，从0到，是所有聘繁项的大小的最大的值。在深度中的每个节点对应个一个项集，，大小为，并且指向大小为的包含的项集，当然是在层。层次为0的单根节点代表空项集。为了能够辟配一个活动会话的不同顺序，所有项集在插入到图中之前将被按照辞典顺序排列。用户的活动会话在进行模式匹配之前也以同样的方式排序。

给定一个活动会话窗口，以词典顺序排序在层次上执行频繁项集的深度优先搜索。如果发现一个匹配的项，则包含的匹配的结点的孩子将被用来生成候选推荐项。每个孩子节点对应一个频繁项集，在每一步，如果支持率大于或等于平均值，览页被加到推荐集中，在这里是最小信任阈值。注意是关联规则的置信度。这个规则的置信度也可以用作览页的推荐评估。很容易观察到在这个算法中，搜索处理需要的时间负责度为。

为了描述这个过程，考虑在表1给出的例子。用这些事务，Apriori算法给定的频繁阈值为4，生成表2中的项集。图1显示的是在表2的频繁相继的基础上构建的图状结构。现在，给定用户活动会话窗口，推荐生成算法发现项和作为候选推荐内容。和的推荐评价值是1和4/5，分别对应规则和的置信度。

应该注意的是，依靠指定支持度阈值，可能很难发现足够大的相继能用来提供推荐集，因为他的覆盖范围缩减了。对一个平均流量比较小的网站尤其如此。另一个方法是不减少支持度而减少会话窗口大小。因为我们可能不会考虑足够多的用户活动历史纪录，所以第二种方法可能会产生难以预料的影响。通常在推荐系统得环境下，用一个较大的活动窗口可能会获得更好的精确率。但是如果支持度更高，大的活动窗口也会降低覆盖范围。为了克服这个

图1.频繁项集的图形表示

 

问题，我们采用all-kth-order方法[14]在马尔科夫链模型中进行处理。在马尔科夫模型中，模型的顺序对应的预测过程中每个事件的优先级。all-kth-order方法通常在每个序列的单个模型生成时通常会导致更大的时间复杂度。

我们的算法是生成all-kth-order推荐内容的扩展。首先推荐引擎用最大可能的活动会话窗口作为输入。如果引擎不能生成任何推荐内容，活动绘画窗口的大小将不断降低知道一个推荐集出现或者窗口大小变为0。我们也注意到了相对于标准all-kth-order的马尔科夫模型，我们的框架不需要额外的存储空间，因为所有需要的信息将能从频繁项集图中获取。

 

 

3.实验测量

在这部分内容中我们将使用实验数据集测试我们推荐系统的效率，根据这些结论得出研究的结论。

3.1实验的设置和测度

对我们的实验而言，我们用顾客搜索相关的网站(ACR)NewsLetter的访问日志。经过与处理后，总共包含18342条事务和122个URL。我们消除了出现率不超过0.5%和超过80%的浏览页。这个数据集被分为一个训练集和一个估测集。预处理过后，浏览页URL的数量为40。大约70%的事务随机被选为训练集，剩下的为估测集。

我们的估测方法如下，每个事务在估测集中被分为两部分。首先中个页面用来生成推荐集。剩余的用来估测生成推荐集的准确性。反映了实验的最大可能的窗口大小。给定一个窗口大小，我们选择了一个个页面的子集作为一个用户活动窗口的代替。活动会话窗口是点击流的一部分。我们称这部分事务为的活动会话，标记为，推荐引擎将和推荐阈值作为输入，生成一个推荐的浏览页的集合。我们记这个推荐集为。这里包含了所有推荐评价至少为的浏览页（特别的，如果=0，则，这里是所有浏览页的集合）。

现在与剩下的浏览页进行比较，我们记这部分为。我们对两者的比较的内容包括度量，名称，精度和覆盖率。的精度定义为：

覆盖率定义为：

精确度代表了推荐集的精确性。覆盖率代表了推荐引擎生成所有用户可能访问的页面的能力。

最后，对于一个推荐阈值,在评价集中所有事务作为全部评价级别进行计算。我们对实验集在阈值范围0.1到1.0进行计算。结论如下所示。

3.2实验结论

我们在阈值为0.1到1.0对推荐的精度和覆盖率进行了计算和测量。考虑窗口大小的影响，我们把窗口大小设为从1到4。而且，我们还考虑到了一个全局支持度阈值作为最小支持度的影响。我们把利用多支持度和all-kth-order得出的结果进行比较。最后我们与KNN技术的结果进行比较，在使用KNN时我们设置k=20，对于我们的数据集，20这个值几乎可以提供最好的结果，我们在KNN中也使用了向量空间余弦相似测量来生成最近邻居。

图2显示了窗口大小对于精度和覆盖率的影响。结果清楚显示了随着用户历史被用来生成推荐的量的增大，精度也在增长。覆盖率从另一方面讲被窗口大小所影响，尽管推荐阈值越高窗口大小变得越小。

就像预期的一样，支持度的影响显示了较高的最小支持度导致较低的覆盖率（丹精度只有较小的提升）。结论并未在这里显示。通常，为了保证模型尺寸较小以确保关联规则挖掘算法的可测量性，可以使用较高的支持度阈值。在web个性化服务的点击流数据中，漏掉的浏览页往往是最重要的（更深的内容或产品页面）。用多支持度的Apriori[8]有助于降低这个问题。图3显示了使用多支持度对算法的影响。在这个实验数据中我们选择了几个内容页

 

面然后分配了一个较小的阈值0.01。其他的页面分配给较高的阈值0.1。结果与用单支持度阈值0.1的算法结果相比较。事实证明前者保证了推荐内容的精确度同时增加了覆盖率（即使推荐阈值较高）。

All-kth-order模型的使用（在活动会话使用动态滑动窗口）也像使用多支持度阈值类似。图4显示了使用All-kth-order模型得到更好的精确度，同时提升了推荐内容的覆盖范围。图中给出了在窗口大小为3而支持度阈值为0。04的条件下得出的结果，但是相关结果与其他窗口大小或阈值得出的结果类似。

图5比较了使用KNN方法和关联规则（包括多支持度阈值，all-kth-order推荐模型）的推荐系统的效率。设置窗口大小为4得出的结果显示在精确度和覆盖率方面有较大的提升。而其他窗口大小指出随着窗口大小的提升，效益提高并不明显。

4结论

基于点击流数据的有效的推荐引擎在早期与用户的交互中非常重要（当不能获得更明确的例如点击率或个人代理等用户输入时）。个性化的服务可以让用户更深入的参与网站和提高网站与用户交互的效率。标准的CF技术需要实时的当前用户记录于其他用户的历史记录进行比较。这种方法当用户数量增大时所花费的时间将不可预测的增加。KNN的不可测量性当处理大容量点击流数据时捉襟见肘。

在本文中，我们提出了一种基于从点击流数据中使用关联规则的框架可以为web个性化服务。我们的框架包括有效的数据结构以保存推荐算法中用来生成推荐集的频繁项集。我们也研究了针对不同类的浏览页，和可变大小的用户历史记录使用多支持度阈值对结果产生的影响。我们的结果显示这个框架的效率较CF机制要高。特别我们展示了关联规则的推荐算法在精确度和覆盖率方面比kNN方法有所提升，同时又可以保持离线频繁模型发现的过程的可测量性。