基于贝叶斯网络的信息过滤模型研究阮彤.pdf

第 39 卷 第 12 期2002 年 12月计 算 机 研 究 与 发 展JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENTVol. 39, No. 12Dec. 2002原稿收到日期: 2001-09-05; 修改稿收到日期: 2002-04-17本课题得到国家重点基础研究发展规划基金( G1999035807) 和国家自然科学重点基金( 69833030) 资助基于贝叶斯网络的信息 过滤模型研究阮 彤¹ º 冯东雷» 李 京¹ º¹( 中国科学院软件研究所院重点开放实验室 北京 100080)º( 中国科学院软件研究所软件工程技术中心 北京 100080)»( 上海交通大学计算机科学与工程系 上海 200030)(ruan@)摘 要 传统信息过滤模型很难描述对信息过滤结果产生影响的各种因素, 如质量、 内容、 用户偏好之间复杂的关系, 也无合适的方法让用户将知识加入到信息过滤系统中. 因此, 提出了基于贝叶斯网络的信息过滤模型 BMIF(Bayesian model of information filtering) . BM IF 是贝叶斯网络的简化, 它描述了信息过滤的基本结构, 提供了 6种节点用于描述影响信息过滤的事件之间的关系. 在此基础上, 提供了BM IF的各种使用方法, 包括将传统方法使用BM IF 描述, 将词法知识用 BMIF 表示, 以及将自动学习与手动交互结合, 将合作过滤与内容过滤结合等.关键词 信息过滤, 贝叶斯网络, 合作过滤, 基于内容的过滤中图法分类号 TP391. 1AN INFORMATION FILTERING MODEL BASED ON BAYESIAN NETWORKSRUAN T ong¹ º, FENG Dong-Lei», and LI Jing¹ º¹(Key Laboratory of Comp uter Science,Institute of Sof tware,Chinese A cademy of Sciences,Beijing100080)º( Sof tware Research Center, Institute of Sof tware, Chinese A cademy of Sciences, Beijing 100080)»(Dep artment of Comp uter Science and Engineering,Shanghai Jiaotong University,Shanghai200030)Abstract T raditional models of content-based information filtering are clumsy to describe the complex relationships of events that affect filtering process. Furthermore, it is difficult for usersto interact with the filtering system. To address the above problems, BMIF—an informationfiltering model founded on Bayesian network is proposed in this paper. It firstly outlines therelationship of features, interests, queries and other main elements in information filtering with a simplified Bayesian network,and then provides six elementary nodes to characterize therelationships in specific conditions.Some use cases of BMIF are presented as well,whichincludes: ¹Describing traditional models with BMIF; º Adding lexical knowledge to BMIF; » Mixing learning with interaction,and combining content-based filtering with collaborativefiltering.Key words information filtering,Bayesian network,collaborative filtering,content-basedfiltering1 引 言信息过滤是一个将用户感兴趣的文档从某个文档集中筛选出来的过程. 有关信息过滤的研究有多种分类方法. 按照过滤方法分, 有基于内容过滤与基于社会过滤[ 1]两种. 按照过滤的对象分, 有面向新闻组与邮件的过滤系统, 如 SIFT[ 2], 以及面向文章的信息过滤系统, 如 SIFTER[ 3]. 按照信息过滤的目的来分, 有用于防火墙的内容过滤、 用于信息供应商的信息发送[ 4]以及通用的主题探测等.比起文本检索, 文本过滤的用户配置文件有一定的长期性[ 1], 在此过程中, 用户可能会通过人机交互, 干涉过滤的结果.另外, 用户选择信息的原因往往是多维的, 包括内容、 质量、 偏好等多种因素. 再者, 一个信息是否满足需求也可以从多个角度判断, 如通过文章内容中的特征、 通过元信息、 通过相关用户是否对特定内容感兴趣等.而原有的基于文本处理模型如向量模型、 布尔模型、 概率模型以及相关的学习算法, 如最近邻居法、 回归分析等, 均不能描述事件之间复杂关系.贝叶斯网络是一个图模型( graphical model)[ 5, 6],其描述了一组变量之间的概率依赖关系. 由于贝叶斯网络具有将先验知识与数据结合, 以及网络结构对用户可见的优点, 已成为专家系统中记录不确定知识的最流行的方法之一.有关贝叶斯网络在信息处理领域中的应用,ACM Computing Surveys 的一篇文章[ 7]这样评价:“ 贝叶斯方法是最有前景的一种方法, 因为其将领域知识引入信息检索领域中” . 贝叶斯网络被用在信息检索 中始于 Howard R.Turtle 的 博士论 文[ 8].Callan[ 9]将 T urtle 的工作改进后用到信息过滤.Srini Narayanan[ 10]将贝叶斯网络用在单词二义性识别上. 文献[ 9] 的研究只是信息检索模型的简单改进, 没有涉及到合作过滤、 用户交互等信息过滤应用的特点.本文提出了一个基于贝叶斯网络的信息过滤模型 BMIF( Bayesian model of information filtering) ,并且描述了该模型的各种使用方法. 本文第 2 节介绍了 BMIF 模型的结构; 第 3 节给出了模型的各种使用方法; 第 4 节给出了部分实验结果; 第 5 节做了总结.2 BMIF 模型的定义与模型的层次结构2. 1 模型的层次结构 定义 1. 符合 BMIF 模型的实例是一个简化的贝叶斯网络. 其中: ¹网络中的每个节点是一个二值的随机变量. º 每个节点的条件概率表必须满足噪声与( noisy-and) 、 噪声或( noisy- or) 、 非、 权和、 上 下文以及阈值节点中的一种.BMIF 模型的层次结构如图 1所示:图 1 BMIF 模型的层次结构( 1) 兴趣层. 表示了用户最终兴趣所在, 一个系统会有多个用户兴趣焦点, 每个兴趣焦点由不同模式组合. ( 2) 模式层. 模式层通过构造特定特征的组合, 描述用户兴趣的一个侧面, 一种内部表示, 或是某种外在表现. 一个模式映射到信息检索中的多查 询系统中, 就是一个查询. 但模式比查询的含义更广泛, 例如, 它可以是通过合作过滤得出的用户对某条信息感兴趣的概率.( 3) 特征层. 用户可在特征层将元信息、 特殊特 征、 类别等各种信息, 结合起来描述特定模式. 不少语料, 如 ACM 的数字图书馆中的文档, 具有关键词、 类别等许多元信息. T apestry[ 11]是利用元信息的最典型的系统, 它定义了 TQL 语言, 用于描述各 种元信息之间的结构化关系. 向量模型与传统的概率模型不能描述 and, or, not 这 3 种关系, 对于and, or, not 的复合形成的层次状结构, 向量模型 与传统的概率模型也不能描述. 在 BMIF 中, 权和节点可以映射成向量模型, 噪声或节点、 噪声与节点和156512 期阮 彤等: 基于贝叶斯网络的信息过滤模型研究非节点可以映射到布尔模型. 因此, BMIF 模型提供 了将不同类型的特征, 用不同算子组合的基础.( 4) 虚拟特征层. 特征表示了与用户兴趣相关的词汇, 但是, 那些不在特征层中的词汇在语义上也 可能与用户兴趣发生关系. 例如, 在学习文档中出现“ 信息过滤” 这个词, 在过滤文档中出现的是“ 可选择 信息发送” 这个词, 两词意思相近. 虚拟特征层与特征层之间的连接可将未在特征层出现的词汇映射到特征层, 这种映射基于的是已有的词法知识. 2. 2 结构化节点在贝叶斯网络中, 在所有节点值都是二值情况下, 一个有 n 个父亲的变量需要定义 2n个条件概 率. 这使得推理具有指数复杂度. 同时, 学习该网络需要估计指数级数目的参数, 因此, 需要大量的数据. 为减少参数个数, 降低网络的计算与存储开销, 本文结合信息过滤的特点, 使用了 6 种简化节点: 噪声或( noisy-or) 、 噪声与( noisy-and) 、 非( not ) 、权和( weighted sum) 、 阈与上下文节点. 这 6 种节点的共 同特点是参数数目与网络中的连接数成线性关系,使用这些节点构成的网络的推理复杂度为多项式时间. 在 6 种节点中, 非与权和两种节点由 HowardR. Turtle 在其博士论文中提出, 被用在他本人设计 的信息检索系统中. 噪声或和噪声与两种节点由Pearl 在 1988 年提出[ 6], 阈与上下文两种节点由本文提出. 限于篇幅, 本文不列出这些节点的条件概率 表( conditional probability table) .( 1) 噪声或节点 对于噪声或, 当一个或节点 Nj的所有条件节点 Ni均为假时, Nj也为假. 与布尔逻辑不同的是,如果 Ni中有一个为真, 则其结果未必为真. 每个条件节点有一个权 qij, 表明该节点对 Nj的阻止型的 影响度. 也就是说, 如果 Nj只有一个条件节点 Ni,且该节点为真, 则 P( Nj= true) = 1- qij. Cij= 1- qij 表示了 Nj事件的一个独立原因 Ni对 Nj的肯定程度. Nj的概率计算公式如式( 1) :P( Nj= x) =∏i( 1 - CijP( Ni= true) ) ,if x = false,1 -∏i( 1 - CijP( Ni= true) ) ,if x = true. ( 1)( 2) 噪声与节点对于噪声与节点, 当父节点均为真时, 结果为真, 但是, 当一个节点的值为假时, 其结果为未必为 假. 同样, 每个条件节点有一个权 qij. 噪声与节点的计算公式如式( 2) :P( Nj= x) =1 -∏i( 1 - Cij( 1 - P( Ni= true) ) ) ,if x = false, ∏i( 1 - Cij( 1 - P( Ni= true) ) ) ,if x = true.( 2)( 3) 非节点在非节点中, 父亲只能有一个, 当父节点为真时, 子节点为假, 反之亦然. 其计算公式如式( 3) 。