第2卷第1期 智能系统学报 Vol.2 Ng 1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 基于用户反馈的智能合作过滤模型的研究 柯佳2程显毅2,李晓薇 (1.江苏大学工商管理学院,江苏镇江212013:2.江苏大学计算机科学与通信工程学院,江苏镇江212013) 摘要:为了提供给用户更准确的信息,提出基于用户反馈的智能合作过滤模型和一种基于用户兴趣的动态Q学习 算法,并建立用户兴趣模型.通过隐式反馈和显式反馈这2种反馈方式更新用户模型并实现合作过滤.实验结果表 明,在输入相同查询提问情况下AC℉M在预测用户兴趣的效果和推荐搜索信息的查全率和查准率方面比传统的搜 索引擎有明显改善 关键词:合作过滤;Agent;用户兴趣;Q学习 中图分类号:TP311文献标识码:A文章编号:1673-4785(2007)01-005905 Research of Agent colla borative filtering model based on user's feedback KE Jia'2,CHENG Xiamyi?,LI Xiao-wei? (1.School of Business Administration,Jiangsu University,Zhenjiang 212013,China;2.Computer Science Communication Engineering Institute Jiangsu University,Zhenjiang 212013,China) Abstract:In order to serve users with more accurate information,the Agent collaborative filtering model- ACFM based on users'feedback and the dynamic Q learning algorithm are put forward,and users'inter- esting model is built.ACFM uses the method of users'interesting feedback consisted of implicit feedback and interactive feedback to realize collaborative filtering.Experimental results show that compared with traditional search engine,ACFM is more effective in predicting users'interests,and has more recalls and precision degree in recommending information when inputting the same inquire words. Key words :collaborative filtering;Agent;users'interesting feedback;Q learning algorithm. 随着互联网的迅猛发展,用户在享受它方便和习算法对信息资源进行合作过滤的方法,并提出了 快捷的同时,要在浩瀚的信息资源中找出自己需要 一种基于用户反馈的智能体合作过滤模型(Agent 的内容,无异于大海捞针.信息过滤技术(infor- collaborative filtering model based on users'feed- mation filtering)正日益成为解决信息超载问题的 back,ACFM).实验结果显示,与普通搜索引擎相 必要手段 比,结合了Agent技术的ACFM在预测用户兴趣的 信息过滤中的合作过滤技术根据具有相似兴趣 效果和推荐搜索信息的查全率和查准率方面都有明 的用户对信息做出的评价,对其他用户兴趣进行预 显改善 测并推荐信息,如Web Watcher,GroupLens等) 1 基于用户反馈的智能合作过滤系统 但是,在系统使用初期,由于系统资源还未获得足够 多的评价,很难利用这些评价来发现相似的用户,另 的总体结构 一方面随着系统用户和信息资源的增多,系统的性 ACFM通过建立用户个人兴趣模型和面向合 能会下降,即存在稀疏性和扩展性的问题」 作的共同兴趣模型,定义用户兴趣;学习Aget动 针对上述问题,文中结合Agent技术和机器 态学习用户兴趣,合作过滤模块根据其他用户对文 学习理论),提出了一种基于用户兴趣的动态Q学 档的评价以及用户模型与文档的相似度来预测用户 的兴趣,动态地从不熟悉的文档中抽取信息送至搜 收稿日期:20060407. 基金项目:国家自然科学基金资助项目(60473039) 索引擎给用户.系统的总体结构图如图1所示。 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 基于用户反馈的智能合作过滤模型的研究 柯 佳1 ,2 ,程显毅2 ,李晓薇2 (1. 江苏大学 工商管理学院 ,江苏 镇江 212013 ;2. 江苏大学 计算机科学与通信工程学院 ,江苏 镇江 212013) 摘 要 :为了提供给用户更准确的信息 ,提出基于用户反馈的智能合作过滤模型和一种基于用户兴趣的动态 Q 学习 算法 ,并建立用户兴趣模型. 通过隐式反馈和显式反馈这 2 种反馈方式更新用户模型并实现合作过滤. 实验结果表 明 ,在输入相同查询提问情况下 ACFM 在预测用户兴趣的效果和推荐搜索信息的查全率和查准率方面比传统的搜 索引擎有明显改善. 关键词 :合作过滤 ;Agent ;用户兴趣 ;Q 学习 中图分类号 : TP311 文献标识码 :A 文章编号 :167324785 (2007) 0120059205 Research of Agent collaborative filtering model based on user′s feedback KE Jia 1 ,2 , CH EN G Xian2yi 2 , L I Xiao2wei 2 (1. School of Business Administration , Jiangsu University , Zhenjiang 212013 , China ; 2. Computer Science & Communication Engineering Institute ,Jiangsu University ,Zhenjiang 212013 , China) Abstract : In order to serve users wit h more accurate information , t he Agent collaborative filtering model — ACFM based on users’feedback and the dynamic Q learning algorithm are p ut forward , and users’inter2 esting model is built. ACFM uses the met hod of users’interesting feedback consisted of implicit feedback and interactive feedback to realize collaborative filtering. Experimental results show t hat compared wit h traditional search engine , ACFM is more effective in predicting users’interests , and has more recalls and precision degree in recommending information when inp utting t he same inquire words. Keywords :collaborative filtering ; Agent ; users’interesting feedback ; Q learning algorithm. 收稿日期 :2006204207. 基金项目 :国家自然科学基金资助项目(60473039) . 随着互联网的迅猛发展 ,用户在享受它方便和 快捷的同时 ,要在浩瀚的信息资源中找出自己需要 的内容 ,无异于大海捞针[1 ] . 信息过滤技术 (infor2 mation filtering) 正日益成为解决信息超载问题的 必要手段[2 ] . 信息过滤中的合作过滤技术根据具有相似兴趣 的用户对信息做出的评价 ,对其他用户兴趣进行预 测并推荐信息 ,如 Web Watcher , GroupLens 等[3 ] . 但是 ,在系统使用初期 ,由于系统资源还未获得足够 多的评价 ,很难利用这些评价来发现相似的用户. 另 一方面随着系统用户和信息资源的增多 ,系统的性 能会下降 ,即存在稀疏性和扩展性的问题. 针对上述问题 ,文中结合 Agent 技术[ 4 ] 和机器 学习理论[5 ] ,提出了一种基于用户兴趣的动态 Q 学 习算法对信息资源进行合作过滤的方法 ,并提出了 一种基于用户反馈的智能体合作过滤模型 (Agent collaborative filtering model based on users’ feed2 back , ACFM) . 实验结果显示 ,与普通搜索引擎相 比 ,结合了 Agent 技术的 ACFM 在预测用户兴趣的 效果和推荐搜索信息的查全率和查准率方面都有明 显改善. 1 基于用户反馈的智能合作过滤系统 的总体结构 ACFM 通过建立用户个人兴趣模型和面向合 作的共同兴趣模型 ,定义用户兴趣 ;学习 Agent 动 态学习用户兴趣 ,合作过滤模块根据其他用户对文 档的评价以及用户模型与文档的相似度来预测用户 的兴趣 , 动态地从不熟悉的文档中抽取信息送至搜 索引擎给用户. 系统的总体结构图如图 1 所示
·60 智 能系统学报 第2卷 搜索引繁 为了避免随着Agent学习的进行,在大量的探 索活动后,系统性能的下降,将最近探索盈余引入 合作过滤 到Q学习中: 搜索结果 '(s,ahis,a'Aother)=.(s.ahis,aiher)+ 个人兴趣 共同兴趣 学习Agent 学习Agent a(p:(s,ahis aother))(s,ahis,aother).(4) 式中:p是等待时间的盈余,b(p=a以(pp,是探索 用户相关反馈 个人兴即 的盈余 共同兴趣 知识库 知识库 这样,学习Agent就近探索那些最近未发现的 反馈信息 用户兴趣,并准备适应用户兴趣的任何改变 用户反馈记录分类索引 数据库 2.2用户兴趣学习 设计动态Q学习算法时,首先需要考虑:如何 图1基于用户反馈的智能合作过滤系统的总体结构图 确定状态空间S、动作空间A以及回报值r Fig 1 Structure chart of ACFM 定义1状态S定义为学习Agent接收到的用 2用户兴趣学习算法 户上网行为,它是一个n元组: S=x1,x2,,x,,x) 2.1动态Q学习算法 式中:x是用户兴趣的取值.所有状态s构成的集 文中设计了基于Agent对用户反馈学习的信 合为状态空间S 念(B)的动态Q学习算法,根据当前更新了的环境 定义2兴趣a定义为学习Agent发现的用户 信念(B)做出估计值Q.典型的Q学习算法需观察 兴趣j的取值,即Agent发现了用户新的兴趣,所有 下一个兴趣项的实际回报值和它的Q学习参数6), 的兴趣构成了兴趣状态空间A. 而动态Q学习算法是估计用户兴趣改变和环境的 定义3回报值r定义为 信息(信念) r=( (5) 采用联合策略(ams,aer)对用户输入的用户兴 趣项的Q值进行估计,为用户在某时间段的兴 式中:v(x表示兴趣j的值x,的大小,由于Agent 趣项,在当前环境状态S(即用户输入了欲查询内容 接收到的兴趣是由用户输入关键词后查询得到的结 的关键词)下,学习Agent对用户行为进行分析,估 果,因而可以使用该项兴趣的大小来评价该兴趣是 计用户的下一兴趣项为aer,基于随机策略选择用 否应该存入用户的知识库中,并使用整体的属性评 户当前的兴趣项as: 估值来定义回报值 e2s.ah/ 用户兴趣的学习算法: prbl authis s= Jeet.oyin (1) 1)初始化:s∈S,a∈A,Q(s,ad=1,a= 1,Y=0.5: 式中:Q(s,as)/Y是基于状态S下的信念P,的期 2)在当前环境状态s下,对所有可能的兴趣项 望Q函数值,即: a,基于信念ps,根据式1),学习Agent将选择当前 O(s,ahs)r= 的用户行为为用户兴趣as; ∫es,as,ar)Xp)dp (2) 3)执行步骤2)中选择的as; 在时刻1,环境改变到新的状态s'(即输入了新的关 4)在时刻1,上网用户行为发生变化,记为状态 键字),得到行动的奖励值Y,Agent基于下面的公 s',从用户的行为接收到的用户兴趣为ar,根据式 式更新Q的值: (4),Agent计算回报值,并修改当前学习率a: 2:(s,ahis,ather)=(1-a)e.1(s,atis,ather)+ a= n(s,ais Cther) d(Y +r max 2.)(s aths a'other). (3 this 式中:n(s,ms,aier)为到时刻1为止,Agent得到 式中:a=argmxP.,ai为用户实际感 的经验(s,as,Cthet)的次数, 兴趣的网上内容,a∈0,11,是学习率.a随着时间 5根据式(1),Agent更新信念,得到P: 衰减,以利于学习算法的收敛 6)根据式(2)、(3),Agent依次更新Q,(s,amms, 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 1 基于用户反馈的智能合作过滤系统的总体结构图 Fig11 Structure chart of ACFM 2 用户兴趣学习算法 211 动态 Q 学习算法 文中设计了基于 Agent 对用户反馈学习的信 念(B) 的动态 Q 学习算法 ,根据当前更新了的环境 信念(B) 做出估计值 Q. 典型的 Q 学习算法需观察 下一个兴趣项的实际回报值和它的 Q 学习参数[6 ] , 而动态 Q 学习算法是估计用户兴趣改变和环境的 信息(信念) . 采用联合策略( athis , aother ) 对用户输入的用户兴 趣项的 Q 值进行估计 , athis为用户在某时间段的兴 趣项 ,在当前环境状态 S (即用户输入了欲查询内容 的关键词) 下 ,学习 Agent 对用户行为进行分析 ,估 计用户的下一兴趣项为 aother ,基于随机策略选择用 户当前的兴趣项 athis : prb[ atrhis | s] = e Q(s, a this ) /γ αk∑∈A e Q(s, a k ) /γ . (1) 式中 :Q (s, athis ) /γ是基于状态 S 下的信念 Ps 的期 望 Q 函数值 ,即 : Q(s, athis) ≡ Ps = ∫B ( Q(s, athis , aother ) ×Ps) d P. (2) 在时刻 t ,环境改变到新的状态 s′(即输入了新的关 键字) ,得到行动的奖励值γt , Agent 基于下面的公 式更新 Q 的值 : Qt (s, athis , a 3 other ) = (1 - αi) Qt- 1 (s, athis , a 3 other ) + αi (γt +γ max a′this ∈A Qt- 1 ) (s′, a′this , a′other ) . (3) 式中 : a′other = argm ax a′other ∈A a′other ∈A Ps′, a 3 other为用户实际感 兴趣的网上内容 ,αi ∈[0 ,1 ] ,是学习率.αi 随着时间 衰减 ,以利于学习算法的收敛. 为了避免随着 Agent 学习的进行 ,在大量的探 索活动后 ,系统性能的下降 ,将最近探索盈余[7 ]引入 到 Q 学习中 : Q′t (s, athis , a 3ρother ) = Qt (s, athis , a 3 other ) + σλ(ρt (s, athis , a 3 other ) ) ρt (s, athis , a 3 other ) . (4) 式中 :ρ是等待时间的盈余 , b(ρ) =σλ(ρ) ρ,是探索 的盈余. 这样 ,学习 Agent 就近探索那些最近未发现的 用户兴趣 ,并准备适应用户兴趣的任何改变. 212 用户兴趣学习 设计动态 Q 学习算法时 ,首先需要考虑 :如何 确定状态空间 S 、动作空间 A 以及回报值 r. 定义 1 状态 S 定义为学习 Agent 接收到的用 户上网行为 ,它是一个 n 元组 : s = ( x1 , x2 , …, x j , …, x n ) . 式中 : x j 是用户兴趣的取值. 所有状态 s 构成的集 合为状态空间 S . 定义 2 兴趣α定义为学习 Agent 发现的用户 兴趣 j 的取值 ,即 Agent 发现了用户新的兴趣 ,所有 的兴趣构成了兴趣状态空间 A . 定义 3 回报值 r 定义为 r = j ∑∈J W j v ( x j) . (5) 式中 : v ( x j) 表示兴趣 j 的值 x j 的大小 ,由于 Agent 接收到的兴趣是由用户输入关键词后查询得到的结 果 ,因而可以使用该项兴趣的大小来评价该兴趣是 否应该存入用户的知识库中 ,并使用整体的属性评 估值来定义回报值. 用户兴趣的学习算法 : 1) 初始化 : Πs ∈S , Πa ∈A , Q0 (s, a) = 1 , a0 = 1 ,γ= 015 ; 2) 在当前环境状态 s 下 ,对所有可能的兴趣项 a ,基于信念 ps ,根据式(1) ,学习 Agent 将选择当前 的用户行为为用户兴趣 athis ; 3) 执行步骤 2) 中选择的 athis ; 4) 在时刻 t ,上网用户行为发生变化 ,记为状态 s′,从用户的行为接收到的用户兴趣为 a 3 other ,根据式 (4) ,Agent 计算回报值γt ,并修改当前学习率 at : at = a0 nt (s, athis , a 3 other ) . 式中 : nt (s, athis , a 3 other ) 为到时刻 t 为止 , Agent 得到 的经验(s, athis , a 3 other ) 的次数; 5) 根据式(1) ,Agent 更新信念 ,得到 Ps′; 6) 根据式(2) 、(3) , Agent 依次更新 Qt (s, athis , ·60 · 智 能 系 统 学 报 第 2 卷
第1期 柯佳,等:基于用户兴趣学习的智能合作过滤模型的研究 *61* aihe),并存储Q,值; 兴趣模型为PM.=((信息过滤,0.2),(中文, 7)ss',根据用户上网行为,产生可能出现的 0.1),(机器学习,0.3),(Agent,0.4},此时更准确 各个兴趣项a',并以缺省值存储O(s,a); 地反映了用户的兴趣程度 8)若学习Agent认定该项内容或网页为用户 兴趣模型建立后,根据用户的浏览行为和对搜 的兴趣项收敛于s‘状态),则存入知识库,否则转 索结果进行评价的方法,不断调整用户个人兴趣模 至步骤2)继续执行 型中关键词的权值,从而更新个人兴趣模型 3.2共同兴趣模型 3用户兴趣表示 共同兴趣模型(co-model,CM)与个人兴趣模 3.1个人兴趣模型 型具有相同的形式.设系统中已有k个用户注册.建 建立用户个人兴趣模型(personal model, 立共同兴趣模型的过程如下:查看用户ⅰ的个人兴 PM),ACFM首先采用交互法,在用户初使用本系 趣模型PM,若word.不在CM中,则添加wor 统时,要求注册用户名/口令,并回答一系列问题.系 d.,即CMU(word.,w)→CM:若word.己在 统对用户回答使用文件词频法1抽取关键词,生成 CM中,则将其权值相加.再重新计算权值使其归 用户兴趣生成树,如图2所示.树的每一节点均为抽 一.最后按权值的大小将关键词word,(u=0,1,2, 取出的用户兴趣关键词. k,j=0,1,2,排序,选择其中前1个组成 CM,t值可通过机器学习获得。 兴趣 3.3基于兴趣模型的合作过滤 设在CM中用户X和用户y有m个兴趣项是 音乐 什算机 体育 相同的,且对应m个兴趣项的兴趣度分别为Wx= {ws.1,ws.2,.ws.m wy ={wx.1,wy.2,..wy.m 模式识别 信息过滤 用户X、Y的兴趣相似程度S(x,以可按式6)计算: ∑p-wm(w-w.m S(x.y) Agent 合作过滤 内容过滤 图2用户i的兴趣生成树 (6 Fig,2 Interesting tree of user i Wx,m为用户X对兴趣项的平均评价值.w.mg 用户个人兴趣模型的建立,就是从兴趣生成树 为用户y对兴趣项的平均评价值;wx)三x,w∈ 的根节点通往叶节点的过程.文中采用关键词矢 w,j=0,m.S(x,y以越大,说明用户X和y 量来表示用户个人兴趣模型,设将用户1的兴趣 的兴趣相似程度越大.通过计算,当S(x,y以>3.5 表示为兴趣关键词集合word.1,,word, 时,y为与用户X具有最近似兴趣的那个用户 word.,其中,word.j(j=0,1,2,表示用户i 若用户'具有与用户u的最相似兴趣,那么用 的兴趣项j,n值将随着用户兴趣反馈的过程而不断 户u对关键词word,所在页面的兴趣度的预测值 变化.每一兴趣项word.,根据用户i兴趣的高低赋 为Pre(u,),计算方法为式(7)所示: 予一定的权值w,且,,=1.则用户i的个人兴 Pre(u.j)wnag +k >((w.j-w.ag)XS(u,u). 趣模型为一个二元组集合PM,={(word.1,w.), (7) (word.2,w.2),(word.m,p.}.若用户在某一 U,为对关键词word,所在页面进行评价的所 段时间内不查询某关键词,则认为对此词没有兴趣, 有用户集:k= 1 为根据用户兴趣相似度 则删除此项.用户也可直接修改关键词的权值(修改 s(u.u) r 范围是0~1的实数)以调整自己的兴趣项,系统再 S(x,以计算出的相似度权值.最后系统将预测值高 重新计算各关键词的权值,使其和归一.例如:用户 的页面推荐给用户”. u想搜索输入关键字:信息过滤,中文,机器学习,A 4 gent.用户对这几个关键词的兴趣度分别为0.2, 用户兴趣的反馈机制 0.1,0.3,0.4,可以手工进行修改,则用户u的个人 在建立用户兴趣模型后,使用隐式反馈和显式 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
a 3 other ) ,并存储 Qt 值; 7) s ←s′,根据用户上网行为 ,产生可能出现的 各个兴趣项 a′,并以缺省值存储 Qt (s, a′) ; 8) 若学习 Agent 认定该项内容或网页为用户 的兴趣项(收敛于 s 3 状态) ,则存入知识库 ,否则转 至步骤 2) 继续执行. 3 用户兴趣表示 311 个人兴趣模型 建 立 用 户 个 人 兴 趣 模 型 ( personal model , PM) ,ACFM 首先采用交互法 ,在用户初使用本系 统时 ,要求注册用户名/ 口令 ,并回答一系列问题. 系 统对用户回答使用文件词频法[ 8 ] 抽取关键词 ,生成 用户兴趣生成树 ,如图 2 所示. 树的每一节点均为抽 取出的用户兴趣关键词. 图 2 用户 i 的兴趣生成树 Fig12 Interesting tree of user i 用户个人兴趣模型的建立 ,就是从兴趣生成树 的根节点通往叶节点的过程. 文中采用关键词矢 量[9 ]来表示用户个人兴趣模型 ,设将用户 i 的兴趣 表示为兴趣关键词集合{ wordi ,1 , …, wordi , j , …, wordi , n } ,其中 , wordi , j ( j = 0 ,1 , 2 , …, n) 表示用户 i 的兴趣项 j , n 值将随着用户兴趣反馈的过程而不断 变化. 每一兴趣项 wordi , j根据用户 i 兴趣的高低赋 予一定的权值 w i , j ,且 ∑ n j = 1 wi , j = 1. 则用户 i 的个人兴 趣模型为一个二元组集合 PM i = { ( wordi ,1 , wi ,1 ) , ( wordi ,2 , wi ,2 ) , …, ( wordi , n , wi , n ) } . 若用户在某一 段时间内不查询某关键词 ,则认为对此词没有兴趣 , 则删除此项. 用户也可直接修改关键词的权值(修改 范围是 0~1 的实数) 以调整自己的兴趣项 ,系统再 重新计算各关键词的权值 ,使其和归一. 例如 :用户 u 想搜索输入关键字 :信息过滤 ,中文 ,机器学习 , A2 gent. 用户对这几个关键词的兴趣度分别为 012 , 011 ,013 ,014 ,可以手工进行修改 ,则用户 u 的个人 兴趣模型为 PM u = { (信息过滤 , 012) , (中文 , 011) , (机器学习 , 013) , (Agent , 014) } ,此时更准确 地反映了用户的兴趣程度. 兴趣模型建立后 ,根据用户的浏览行为和对搜 索结果进行评价的方法 ,不断调整用户个人兴趣模 型中关键词的权值 ,从而更新个人兴趣模型. 312 共同兴趣模型 共同兴趣模型 (co2model , CM) 与个人兴趣模 型具有相同的形式. 设系统中已有 k 个用户注册. 建 立共同兴趣模型的过程如下 :查看用户 i 的个人兴 趣模型 PM i , 若 wordi , j 不在 CM 中 , 则添加 wor2 di , j ,即 CM ∪( wordi , j , wi , j ) →CM ; 若 wordi , j 已在 CM 中 , 则将其权值相加. 再重新计算权值使其归 一. 最后按权值的大小将关键词 wordu, j ( u = 0 ,1 ,2 , …, k , j = 0 , 1 , 2 , …, n) 排序 , 选择其中前 t 个组成 CM , t 值可通过机器学习获得. 313 基于兴趣模型的合作过滤 设在 CM 中用户 X 和用户 Y 有 m 个兴趣项是 相同的 ,且对应 m 个兴趣项的兴趣度分别为 w x = { wx ,1 , wx ,2 , …, wx , m }和 wy = { wy ,1 , wy ,2 , …, wy , m } , 用户 X 、Y 的兴趣相似程度 S ( x , y) 可按式(6) 计算 : S ( x , y) = ∑ m j =1 (wi, j - wx , avg ) (wy , j - wy , avg ) ∑ m j =1 (wx , j - wx , avg ) 2 ∑ m i =1 (wy , j - wy , avg ) 2 . (6) wx , avg 为用户 X 对兴趣项的平均评价值. wy , avg 为用户 Y 对兴趣项的平均评价值; wx , j Α wx , wy , j Α wy , ( j = 0 , …, m) . S ( x , y) 越大 ,说明用户 X 和 Y 的兴趣相似程度越大. 通过计算 ,当 S ( x , y) > 315 时 , Y 为与用户 X 具有最近似兴趣的那个用户. 若用户 u′具有与用户 u 的最相似兴趣 ,那么用 户 u 对关键词 word u, j所在页面的兴趣度的预测值 为 Pre ( u , j) ,计算方法为式(7) 所示 : Pre ( u, j) = wu, avg + k u′∑∈Ui ((wu′, j - wu′, avg ) ×S ( u, u′) . (7) Ui 为对关键词 word u, j所在页面进行评价的所 有用户集; k = 1 u′∑∈U i S ( u , u′) 为根据用户兴趣相似度 S ( x , y) 计算出的相似度权值. 最后系统将预测值高 的页面推荐给用户 u. 4 用户兴趣的反馈机制 在建立用户兴趣模型后 ,使用隐式反馈和显式 第 1 期 柯 佳 ,等 :基于用户兴趣学习的智能合作过滤模型的研究 ·61 ·
·62· 智能系统学报 第2卷 反馈2种反馈机制实时更新用户兴趣 试实验系统:机器人足球;入侵检测系统;数据挖掘; 4.1隐式反馈学习 Linux;电子商务.该系统实验评价指标o1为 在用户没有明确参与评价搜索结果的情况下, 查全率Recall,表示为用户预测并推荐给用户 系统在客户端浏览器的后台时刻监视和跟踪用户的 的文档S中真正是用户感兴趣的文档数,与用户感 浏览行为和操作,通过用户在某个网站的停留时间 兴趣的全部文档总数的百分比 或者在一段时间内反复登录某个网站来推断出用户 预测查全率:Recall=SDR4X1O0%.(9 兴趣 IRI 假定用户i在一段时间H内经常上网(以小时 查准率Precision,表示在推荐给用户的文档 为单位),若在此期间花H的时间上网(H以小时 中,真正是用户感兴趣的文档数,与系统提交给用户 为单位),其中用户1对感兴趣的页面总浏览时间为 的页面数的百分比 H,:对一些认为重要的页面浏览了T次,对感兴趣 预测准确率:Precisi0n=SRLX1O0% ISI 的页面浏览次数为T,:对一些认为重要的页面内容 10 保存了s次,对感兴趣的页面保存次数为S.对含 若输入关键字为“机器人足球”,则输出结果如 用户兴趣内容的页面进行词干抽取处理和关键词切 表1所示:其中Recall 1为由ACFM返回的相关结 分,即可获得用户兴趣度.定义用户ⅰ对兴趣项 果的查全率;Recall2为由普通检索工具检索时返 word的兴趣度w为 回的相关结果的查全率.从表1可以看出,ACFM w'=a出+B.+y. 8) H T 与普通的搜索工具在相同的用户兴趣度下,结果有 式中:a,B,Y为浏览时间、浏览次数和保存次数3项 很大的差别,因为ACFM不但具有跟踪用户上网行 对兴趣项word,的影响因子,0≤0≤1,0≤B≤1, 为的能力,而且可以根据用户的兴趣度主动查询出 0y,且a+B+y=1.a,B,Y的取值可通过机器 与该用户兴趣相关的网页,由此提高了查全率 学习得到或通过经验取值 表1查全率比较 式8)计算出w,',0≤w图.设定阈值6,当 ble I Comparison of the alFsearching probability w'>6时,可认为用户i对word感兴趣 用户兴趣度 Recall 1/% Recall 2/% 4.2显式反馈学习 系统根据用户对查询结果的评价信息来学习用 0.10 10 10 户的兴趣.用户对查询结果所在页面的评价可分为 0.20 20 20 3类:正好符合兴趣:与兴趣相关:与兴趣无关 ACFM根据评价信息对用户兴趣模型中w,的权值 0.30 30 20 作调整: 0.40 40 1)当用户i对含有关键词word,的页面评价 是正好符合兴趣,则W加1: 0.50 55 2)当用户i对含有关键词word的页面评价 0.60 65 5 是与兴趣相关,则W加0.5; 3)当用户i对含有关键词word.,的页面评价 0.70 70 6( 是与兴趣无关,则W减1:若此时减为负数,则置 0.80 80 65 0 在系统作下一次预测用户兴趣,向用户推荐页 0.90 90 75 面之前,须更新用户模型 对5个查询提问的搜索结果进行过滤后产生表 5实验结果 2,该图是通过合作过滤后所计算出来的准确率表, 使用来自于江苏大学数字图书馆的数据库的总 并且与使用普通搜索工具的结果进行比较,Preci- 容量近十万字,共含有100多篇科技文献作为测试 sion1为由ACFM返回的相关结果的查准率;Pre 数据.5个覆盖了不同的主题的查询提问被用来测 cision2为由普通检索工具检索时返回的相关结果 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
反馈 2 种反馈机制实时更新用户兴趣. 411 隐式反馈学习 在用户没有明确参与评价搜索结果的情况下 , 系统在客户端浏览器的后台时刻监视和跟踪用户的 浏览行为和操作 ,通过用户在某个网站的停留时间 或者在一段时间内反复登录某个网站来推断出用户 兴趣. 假定用户 i 在一段时间 H 内经常上网(以小时 为单位) ,若在此期间花 H^ 的时间上网 ( H^ 以小时 为单位) ,其中用户 i 对感兴趣的页面总浏览时间为 H^ i ;对一些认为重要的页面浏览了 ^T 次 ,对感兴趣 的页面浏览次数为 ^Ti ;对一些认为重要的页面内容 保存了 S^ 次 ,对感兴趣的页面保存次数为 S^ i . 对含 用户兴趣内容的页面进行词干抽取处理和关键词切 分 ,即可获得用户兴趣度. 定义用户 i 对兴趣项 word i , j的兴趣度 w′i , j为 wi , j′=α· H^ i H^ +β· ^Ti ^T +γ· S^ i S^ . (8) 式中 :α,β,γ为浏览时间、浏览次数和保存次数 3 项 对兴趣项 wordi , j 的影响因子 , 0 ≤α≤1 , 0 ≤β≤1 , 0 ≤γ≤1 ,且α+β+γ= 1.α,β,γ的取值可通过机器 学习得到或通过经验取值. 式(8) 计算出 wi , j′, 0 ≤wi , j ≤1. 设定阈值δ,当 wi , j′>δ时 ,可认为用户 i 对 word i , j感兴趣. 412 显式反馈学习 系统根据用户对查询结果的评价信息来学习用 户的兴趣. 用户对查询结果所在页面的评价可分为 3 类 : 正好符合兴趣; 与兴趣相关; 与兴趣无关. ACFM 根据评价信息对用户兴趣模型中 wi , j的权值 作调整 : 1) 当用户 i 对含有关键词 word i , j 的页面评价 是正好符合兴趣 ,则 W i , j加 1 ; 2) 当用户 i 对含有关键词 word i , j 的页面评价 是与兴趣相关 ,则 W i , j加 015 ; 3) 当用户 i 对含有关键词 word i , j 的页面评价 是与兴趣无关 ,则 W i , j 减 1 ;若此时减为负数 ,则置 0. 在系统作下一次预测用户兴趣 ,向用户推荐页 面之前 ,须更新用户模型. 5 实验结果 使用来自于江苏大学数字图书馆的数据库的总 容量近十万字 ,共含有 100 多篇科技文献作为测试 数据. 5 个覆盖了不同的主题的查询提问被用来测 试实验系统 :机器人足球 ;入侵检测系统 ;数据挖掘 ; Linux ;电子商务. 该系统实验评价指标[10 ]为 查全率 Recall ,表示为用户预测并推荐给用户 的文档 S 中真正是用户感兴趣的文档数 ,与用户感 兴趣的全部文档总数的百分比. 预测查全率 :Recall = | S ∩R | | R | ×100 %. (9) 查准率 Precision ,表示在推荐给用户的文档 中 ,真正是用户感兴趣的文档数 ,与系统提交给用户 的页面数的百分比. 预测准确率 :Precision = | S ∩R | | S | ×100 %. (10) 若输入关键字为“机器人足球”,则输出结果如 表 1 所示 :其中 Recall 1 为由 ACFM 返回的相关结 果的查全率 ; Recall 2 为由普通检索工具检索时返 回的相关结果的查全率. 从表 1 可以看出 ,ACFM 与普通的搜索工具在相同的用户兴趣度下 ,结果有 很大的差别 ,因为 ACFM 不但具有跟踪用户上网行 为的能力 ,而且可以根据用户的兴趣度主动查询出 与该用户兴趣相关的网页 ,由此提高了查全率. 表 1 查全率比较 Table 1 Comparison of the all2searching probability 用户兴趣度 Recall 1/ % Recall 2/ % 0110 10 10 0120 20 20 0130 30 20 0140 40 30 0150 55 45 0160 65 55 0170 70 60 0180 80 65 0190 90 75 对 5 个查询提问的搜索结果进行过滤后产生表 2 ,该图是通过合作过滤后所计算出来的准确率表 , 并且与使用普通搜索工具的结果进行比较 , Preci2 sion 1 为由 ACFM 返回的相关结果的查准率 ;Pre2 cision 2 为由普通检索工具检索时返回的相关结果 ·62 · 智 能 系 统 学 报 第 2 卷
第1期 柯佳,等:基于用户兴趣学习的智能合作过滤模型的研究 *63* 的查准率 [5]BOWL IN G M,VELOSO M.Multiagent learning using a variable learning rate [J ]Artificial Intelligence,2002 表2ACFM与普通检索工具的比较 (136):215-250. Table 2 Comparison between ACFM and the [6]KAELBLING P L,LITTMAN L M,MOORE W A. common searching tool Reinforcement learning:a survey [J ]Journal of Artifi- Search 1 Search 2 Search 3 Search 4 Search 5 cial Intelligence,1996(4):237-285. Precisionl 0.399 0.4510.4580.473 0.499 [7]ZHU S H,DANA H.BALLARD.Overcoming nomsta- tionarity in uncommunicative learning[R].Technical Re- Precision2 0.362 0.3940.4290.3930.452 port 762,Computer Science Dept,U.Rochester,2001. [8]程显毅,于冬梅.基于BDIAgent的Web搜索引擎的研究 6结束语 [U].江苏大学学报(自然科学版),2004,25(6):545. 548 Agent合作过滤技术为用户提供多层次个性化 CHENG Xianyi,YU Dongmei.A search engine of Webr 的信息服务模板,从自动流向用户的大量信息中过 based BDI Agent [J ]Journal of Jiangsu University(Nat- 滤出用户感兴趣的内容,并以不同的形式(如关键 ural Science Edition),200425(6):545-548. 词、摘要、全文等)提交给用户,文中建立描述了用户 [9]曹树金,杨涛.自动分类在搜索引擎性能优化中的应用 兴趣模型和学习Agent如何采用动态Q学习算法 [J].情报科学,2004,22(2):214.219。 进行自学习,跟踪用户行为推断用户兴趣,并利用合 CAO Shujin,YANG Tao.Application of automatic clas- sification in the search engine optimization[].Infor- 作过滤来找出用户兴趣的相似程度.实验结果显示 mation Science,2004,22(2):213,219. 与普通检索工具相比,在用户对某关键词兴趣度相 [10]KOSTOV V,NAITO E.OZAWA J.Cellular phone 同的情况下使用ACFM的查全率较高,对相同查询 ring tone recommendation system based on collaborative 提问ACFM的查准率提高了3%~7%,但是发现 filtering method [A].Proceeding 2003 IEEE Interna- 速度要较普通检索工具稍慢一些,这是由于模型在 tional Symposium on computational Intelligence in Ro- 用户兴趣学习过程中花费了一点时间.因此在以后 botics and Automation[C].Kobe,Japan,2003. 的工作中会对ACFM进行更进一步的研究,以期在 作者简介: 提高过滤信息准确率的同时,过滤速度也有一定的 提高 柯佳,女,1981年生,助教,硕士 研究生,主要研究方向为人工智能、多 参考文献: Agent系统」 [l]肖燕华,邵世煌.一种基于本体论的Internet信息个性化 Email:greenttea @163.com. 检索系统的Aget实现模型U].微计算机信息,2003,19 (6):77.78 XIAO Yanhua,SHAO Shihuang.An agent-realized 程显毅,男,1956年生,教授,博士, model of personalize internet information retrieval syste- 主要研究方向为模式识别、多Agent系 rm based on ontology [J ]Control and Automation, 统 2003,19(6):77.78. [2]LEE C H,KIM Y H,RHEE P K.Web personalization expert with combining collaborative filtering and associa- tion rule mining technique [J ]Expert Systems with Ap- plication,2001(21):1311-137 李晓薇,女,1982年生,助教,硕士 [3 MEL VILL E P.Content-boosted collaborative filtering 研究生,主要研究方向为人工智能、多 for improved recommendations [A ]In Proceedings of Agent系统. AAAF2002[C].Edmonton,Canada,2002. [4]程显毅.Agent计算[M].哈尔滨:黑龙江科学技术出版 社,2003. 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的查准率. 表 2 ACFM 与普通检索工具的比较 Table 2 Comparison between ACFM and the common searching tool Search 1 Search 2 Search 3 Search 4 Search 5 Precision1 01399 01451 01458 01473 01499 Precision2 01362 01394 01429 01 393 01452 6 结束语 Agent 合作过滤技术为用户提供多层次个性化 的信息服务模板 ,从自动流向用户的大量信息中过 滤出用户感兴趣的内容 ,并以不同的形式 (如关键 词、摘要、全文等) 提交给用户. 文中建立描述了用户 兴趣模型和学习 Agent 如何采用动态 Q 学习算法 进行自学习 ,跟踪用户行为推断用户兴趣 ,并利用合 作过滤来找出用户兴趣的相似程度. 实验结果显示 与普通检索工具相比 ,在用户对某关键词兴趣度相 同的情况下使用 ACFM 的查全率较高 ;对相同查询 提问 ACFM 的查准率提高了 3 %~7 % ,但是发现 速度要较普通检索工具稍慢一些 ,这是由于模型在 用户兴趣学习过程中花费了一点时间. 因此在以后 的工作中会对 ACFM 进行更进一步的研究 ,以期在 提高过滤信息准确率的同时 ,过滤速度也有一定的 提高. 参考文献 : [1 ]肖燕华 ,邵世煌. 一种基于本体论的 Internet 信息个性化 检索系统的 Agent 实现模型[J ]. 微计算机信息 ,2003 ,19 (6) :77 - 78. XIAO Yanhua , SHAO Shihuang. An agent2realized model of personalize internet information retrieval syste2 rm based on ontology [J ]. Control and Automation , 2003 ,19 (6) :77 - 78. [2 ]L EE C H , KIM Y H , RHEE P K. Web personalization expert with combining collaborative filtering and associa2 tion rule mining technique [J ]. Expert Systems with Ap2 plication ,2001 (21) :1311 - 137. [3 ] MELVILL E P. Content2boosted collaborative filtering for improved recommendations [ A ]. In Proceedings of AAAI22002[C]. Edmonton , Canada , 2002. [4 ]程显毅. Agent 计算[ M]. 哈尔滨 :黑龙江科学技术出版 社 ,2003. [ 5 ]BOWL IN G M , V ELOSO M. Multiagent learning using a variable learning rate [J ]. Artificial Intelligence , 2002 (136) :215 - 250. [6 ] KA ELBL IN G P L , L ITTMAN L M , MOORE W A. Reinforcement learning : a survey[J ]. Journal of Artifi2 cial Intelligence , 1996 (4) : 237 - 285. [ 7 ]ZHU S H , DANA H. BALLARD. Overcoming non2sta2 tionarity in uncommunicative learning[ R]. Technical Re2 port 762 , Computer Science Dept , U. Rochester , 2001. [8 ]程显毅 ,于冬梅. 基于 BDIAgent 的 Web 搜索引擎的研究 [J ]. 江苏大学学报 (自然科学版) , 2004 , 25 (6) : 545 - 548. CHEN G Xianyi , YU Dongmei. A search engine of Web2 based BDI Agent[J ]. Journal of Jiangsu University(Nat2 ural Science Edition) ,2004 ,25 (6) :545 - 548. [9 ]曹树金 ,杨 涛. 自动分类在搜索引擎性能优化中的应用 [J ]. 情报科学 ,2004 ,22 (2) :214 - 219. CAO Shujin , YAN G Tao. Application of automatic clas2 sification in the search engine∞s optimization [J ]. Infor2 mation Science , 2004 ,22 (2) :213 - 219. [10 ] KOSTOV V , NAITO E , OZAWA J. Cellular phone ring tone recommendation system based on collaborative filtering method [ A ]. Proceeding 2003 IEEE Interna2 tional Symposium on computational Intelligence in Ro2 botics and Automation[C]. Kobe , J apan ,2003. 作者简介 : 柯 佳 ,女 ,1981 年生 ,助教 ,硕士 研究生 ,主要研究方向为人工智能、多 Agent 系统. E2mail : greenttea @163. com. 程显毅 ,男 ,1956 年生 ,教授 ,博士 , 主要研究方向为模式识别、多 Agent 系 统. 李晓薇 ,女 ,1982 年生 ,助教 ,硕士 研究生 ,主要研究方向为人工智能、多 Agent 系统. 第 1 期 柯 佳 ,等 :基于用户兴趣学习的智能合作过滤模型的研究 ·63 ·