基于层次聚类的自适应信息过滤学习算法

摘 要：本文采用一种基于层次聚类的自适应学习策略，从系统反馈的信息流中，动态提取一类最优信息的质心更新用户模型，有效屏蔽了阈值失真和初始信息稀疏造成的大量反馈噪声，并且能够近似模仿人工反馈，完善自适应学习机制的智能性。

关键词：计算机应用；中文信息处理；自适应信息过滤；用户模型；相关反馈；阈值；层次聚类

中图分类号：TP391　文献标识码：A

1 引言

随着搜索引擎技术的应用，人们找到了一条从海量信息中获取知识的捷径，但是伴随其产生的许多问题却不能仅仅依靠检索技术的改进得到很好的解决，其中最突出的两类问题是如何屏蔽垃圾信息和如何个性化推送信息，因此，更加智能化的信息过滤技术成为弥补这些缺陷的最佳助手^[1,2]。传统的信息过滤，如批过滤和信息路由，都需要大量初始信息训练用户模型，并且在处理信息的过程中欠缺自发的学习与更新能力，这就极大地制约了信息过滤技术在实际应用中的发展。智能性更强的自适应信息过滤技术是一项在初始信息相对稀缺的情况下高效完成过滤任务并自动优化的课题，其通过在线学习反馈信息来更新用户模型，并时刻监控信息流与用户模型的相关度指标，同时从中选择相关度高于阈值的信息作为反馈。传统自适应信息过滤系统主要包含四个组成部分^[3,4]，其相互关系如图1所示。

1)用户模型：描述用户需求信息的特征空间。用户模型的构造策略包括向量空间模型、浅层语义索引、n元语法模型和树，其中向量空间模型是最常用的一种方法。

2)相关度计算：计算信息与用户模型的相似度。选择相关度计算的策略必须依据系统选择用户模型的方法，比如：向量空间模型的相似度一般采用特征向量空问的余弦夹角进行计算；浅层语义索引则采用奇异值分解。

3)阈值估计：阈值是区分相关与不相关信息的边界，阈值的存在显示信息过滤可以看作一种二元分类问题。

4)自学习算法：自学习机制的核心思想是通过反馈更新和改进当前用户模型的特征空间。目前效果较好的自学习策略包括LR^[5]和Rocchio^[6,7]等。

同比于人的学习习惯，对于一个自适应过滤系统而言，怎样获取最优信息进行学习是提高其学习效果的中心问题。传统的做法分为两类，一类是完全依赖阈值的精准截取；一类是凭借伪相关反馈的排序算法。基于这两种方法的学习机制在很大程度上提高了自适应信息过滤系统的智能，但同时在实际应用中也暴露了许多缺陷，其中最为明显的两个问题是：

1)阈值估计偏差问题^[8,9]：早期的阈值估计一般都是在大规模语料中预先训练得到的，这种阈值在过滤过程中不进行调整，从而使判断信息相关性的过程存在偏见。为了应对自适应信息过滤的要求，许多学者从事了阈值估计方面的研究，比如CMU的Yi Zhang^[9]采用统计策略对阈值进行估计，其观测到相关信息与用户模型的相关度成正态分布，而不相关信息的相关度成指数分布，并根据这种规律，采用两种分布的联合概率估计阈值。该方法在TREC评测中得到的结果并不出色，主要问题在于其不能考虑系统每次相关反馈对阈值的影响，在用户模型时刻更新，同时相关度指标整体浮动的环境下，设置固定的阈值截取信息并不能有效解决偏差问题。此外，Yiming Yang采用MLR^[10]算法，在正例①边界和反例②边界之间的带状地带动态更新阈值。其问题在于两个边界逐渐归一并且成递减趋势，从而阈值的估计也恢复静态，因此也不能彻底解决阈值偏差问题。

2)伪相关反馈初始信息稀疏问题：基于伪相关反馈的学习机制通常选择所有反馈，或经过排序后相关性指标靠前的反馈更新用户模型。其缺陷在于忽视了用户模型先天的信息稀疏性。根据TREC对自适应信息过滤任务的定义，每个用户模型的初始训练正例规模很小，而在实际应用中，用户通常也不会给出需求信息的详细描述，因此过滤结果的相关性指标并不能精确指向用户的真正意图。此外，稀疏的初始信息赋予关键特征的上下文环境非常有限，而语言本身又存在歧义性问题，仅仅依靠统计学原理得到的相关性指标很有可能指向了一个错误的需求意图。基于这些因素，传统的学习算法无法屏蔽反馈中大量的噪声并可能误导用户模型。

本文采用一种基于层次聚类的自适应学习机制，通过对伪相关反馈进行聚类，选择最优的一类信息更新用户模型，从而削弱阈值估计偏见性和用户模型初始信息稀疏问题对过滤性能的影响。本文组织形式如下，第二节介绍基于层次聚类的自适应信息过滤学习算法；第三节介绍实验使用的语料及评价策略；第四节介绍实验流程与安排；第五节分析实验结果；第六节结论。

2 基于层次聚类的自适应信息过滤学习算法

如第1节所论述，制约自适应信息过滤学习机制效果的两个主要因素是阈值估计的偏差性和可供伪相关反馈对比的初始信息稀疏性。受这两个情况的影响，伪相关反馈中相关度排序位置靠前的信息不一定满足真正的用户需求，而相关度排序位置偏低的信息却有可能成为重要的相关信息。图2是采用Rocchio学习算法的自适应信息过滤系统针对用户模型的一次随机反馈记录，横轴记录当前所有反馈信息与最优类质心的相关度，纵轴记录所有反馈信息与用户模型的相关度。从图中我们可以观测到如下现象：

1)当前反馈中，许多正例与用户模型相关度偏低，许多噪声与用户模型相关度很高。

2)当前反馈中，正例与最优类质心相关度很高，噪声与最优类质心相关度偏低。

因此，如果选择所有伪相关反馈对用户模型进行更新，则会引入大量噪声信息；而截取相关度靠前的反馈更新用户模型，则遗漏了一定规模的正例信息。从另一个角度观察，一类最优的正例反馈与大部分噪声信息的相关性很低，同时包含了许多与用户模型相关度偏低的正例。这说明，上下文环境稀疏和特征歧义使用户模型与正例信息的匹配存在误差，这造成自学习模块无法正确抽取更有价值的反馈信息用于用户模型的更新，但反馈信息间内在的相关性却可以将正例反馈尽量聚集，同时疏远它们与噪声反馈的距离。因此，通过聚类获取一类最优反馈参与用户模型的学习，既可以屏蔽噪声反馈也可以减少学习中正例反馈的遗失。

本文陈述的基于层次聚类自适应信息过滤学习算法(以下简称HCR)采用BIRCH算法对伪相关反馈聚类，选择最优的一类信息结合增量式Roc—chio算法参与用户模型的学习。

2．1增量式Rocchio学习算法

Rocchio^[6,7]学习算法利用相关信息的质心强化用户模型的正确特征，而利用不相关信息的质心削