●陶剑文(浙江工商职业技术学院计算机应用研究所, 浙江宁波315012)
摘要: 解决用户的模糊查询问题一直以来是信息检索领域研究的热点。为了解决不同用户间的查询差异, 一种称为个性化搜索的技术得以提出, 其通过获取用户的喜好来识别查询意图, 但研究发现很少有用户愿意直接或间接提供个人信息。本文提出一种基于用户点击历史信息自动获取用户兴趣进而对搜索结果进行个性化呈现的W eb搜索系统架构。基于主题相关PageRank技术, 设计了用户兴趣学习算法和个性化搜索页面排序算法。实验表明该算法能有效学习用户的兴趣信息, 提高了个性化W eb搜索质量。 关键词: 信息检索; 模糊检索; 用户兴趣; 算法
Abstract: To so lve u ser’s am biguo us query p rob lem has long been a hotspo t for study in info rm ation retrieval field. In order to settle the query difference among different users, a personalized search techno l og y is p ut forward, which identifies the intention of a query by user’s p reference. However, studies show that few user s are willing to p rovide personal info rm ation directly or indirectly. This paper introduces a W eb search system model, which learns user’s p reference au tom atically based on his click history and p rovides personalized search resu lts.
U ser’s p reference learning algo rithm and personalized page ranking algo rithm based on subject2related PageRank techno log y are introduced. The experiment show s that these alg o rithm s can effectively learn u ser’s p reference and imp rove the quality of personalized W eb search.
Keywords: info rmation retrieval; fuzzy retrieval; u ser’s p reference; algo r ithm
1 引言
解决用户的模糊查询问题一直以来是信息检索领域研
究的热点[ 1 ] 。为了解决不同用户间的查询差异, 基于用
户喜好信息定制搜索结果的个性化搜索( Personalized
Search) 得以出现, 其能显著增强用户的个性化体验, 但研
究发现很少有用户愿意直接或间接提供个人信息, 这为当前个性化搜索研究带来一定的困难[ 2 ]。为此, 本文提出一种基于用户点击历史信息自动获取用户兴趣进而对搜索结果进行个性化定制的W eb搜索系统架构。如图 1 所示, 本文提出的个性化搜索系统架构主要由两部分构成: 离线处理部分与在线处理部
分, 其中离线处理部分主要是面向主题的W eb信息搜索, 由主题搜索引擎完成, 最后将搜索到的信息进行索引并存入本地索引数据库中, 供用户查询时检索; 在线处理部分主要包括: 用户查询接口、查询预处理、兴趣抽取、结果优化排序。①查询预处理, 主要捕捉用户的点击历史信息如何同其兴趣相关, 从而构造一个页面—主题关系表。②兴趣抽取, 通过学习用户的点击
3 本文受到浙江省教育厅科研项目资助( 20040120 ) ; 浙江省教
育厅青年教师科研基金资助。
图 1 基于用户兴趣的个性化搜索系统历史数据来学习用户的个人兴趣。③结果优化排序, 通过学习到的用户兴趣信息来对搜索结果予以优化排序, 从而实现个性化搜索信息呈现。
2 相关概念
定义 1 访问一致性(V isit Coherence) , 指用户在同一个会话过程中所访问的页面在概念逻辑上是一致的。
在标准的PageRank计算情形下, 对于任何查询, 每个页面均被独立赋予一个单一的全局分值, 由于PageR2 ank计算在离线状态下预处理, 故该计算模型具有一定的效率优势, 但因其采用单一权重分值计算, 其不能有效解决针对不同的用户查询排序结果单一的问题。对此, 主题相关PageRank ( Top ic2S
ensitive PageRank, TS PR )得以提出, 其是标准PageRank的一个有效扩展, 针对不同的查
i = 1
i = 1 i i = 1
询 , TS PR 提供不同排序机制 [ 2 ]
。在 TSPR 模式下 , 每个页 面赋予一个计算分值 ( PageRank ) , 其分别对应某个主题
( To p ic ) 。基于用户访问一致性 , 本文提出与主题 t 相关的
定义 4 访问概率向量 (V isit Probability Vecto r ) , 用 户的访问概率向量定义为一个 n 元组 V = [ V ( 1 ) , , V
( n ) ] , n 为页面总数 , V ( i ) 指用户访问页面 p 的概
偏置随机跳转概率向量 Et = [ Et (1) , , Et ( n ) ] 为 :
率。V 被归一化为 ∑m V ( i ) = 1。
E t (p )
1 / n t , 如果页面 p 与 t 相
关
0, p 与 t 无关
(1)
引理 1 设用户 u 具有主题兴趣向量 T = [ T ( 1 ) ,
, T (m ) ] 和 概 率 访 问 向 量 V = [ V ( 1 ) ,
, V
( n ) ] , 在 TDRS M 模型下 , u 访问页面 p 的概率 V ( p )
其中 n t 指与 t 相关的页面总数 , 与 t 相关的页面集合
被引用为 t 的偏置集。
如果用户在冲浪的过程中 , 并非一直跟随页面的链接 进行跳转 , 其可能直接在 W eb 浏览器中输入某个感兴趣 的 URL 地址进行重新浏览 , 即用户在 W eb 上浏览时 , 其 跟随页面某个外出链接的概率为 d, 则 1 - d 表示其直接 跳转到某个新页面的概率 。从而与 t 相关的页面 p 的权重 分值 TSPR 计算式为 :
TSPR t (p ) = ( d × ∑ TSPR t (p 0 ) ) /
p 0∈L p
( l p 0 + ( 1 - d ) ×E t (p ) )
(2)张岱年
假设有 m 个主题 , 离线处理将有 m 个 TSPR 分值被计 算 , 在线查询处理过程中 , 对于给定查询 , 搜索引擎计算 出最合适的 TSPR 分值并用以排序页面 。
3 算法设计
本文所提出的算法主要包括两个部分 : 用户兴趣的学 习算法与个性化搜索排序算法 。其中用户兴趣学习算法主 要通过系统学习模型实现 ; 在学习到用户的兴趣向量的基 础上 , 通过优化的结果排序算法 , 为用户产生个性化的搜 索结果 。
为 :
m
V (p ) = ∑T ( i ) ×TS PR i (p )
( 3)
i = 1
在 TSPR 模型下 , 公式 ( 3 ) 显示了用户访问情况与 其主题兴趣向量间的关系 。在实际情况下 , 搜索引擎仅观 测用户对搜索结果的点击信息 , 而非用户的一般浏览行 为 , 即搜索引擎观测的点击信息并非基于主题驱动的随机 浏览模型 。为此 , 本文对主题驱动随机浏览模型进行扩展 为 :
定义 5 主题驱动搜索模型 ( Top ic 2D riven Searcher
Model, TD S M ) , 设某用户 u 具有 主 题 兴 趣 向 量 T, 在 TD S M 模型下 , u 将总是通过搜索引擎以两步过程浏览页
面 : 首先 , u 以概率 T ( t ) 选择一个兴趣主题 t, 然后 u 打开某搜索引擎发出一个关于 t 的查询 , 该搜索引擎返回 一个以 TSPR t (p ) 排序的页面结果集 , 最后 u 在该结果 集上进行点击 。
从参考文献 [ 3 ] 的研究结果得知 , 用户对某页面 p 的访问概率 V ( p ) 与 [ PR ( p ) ]
9 /4
成比例 , 由此得出 : 设
用户 u 具有主题兴趣向量 T 与访问概率向量 V, 则在
TD S M 模型下 , V (p ) 计算式为 :
m
311 用户兴趣学习算
法
V (p ) = ∑T ( i ) × [ TS PR i (p ) ] i = 1
9 /4
( 4)
定义 2 主题兴趣向量 ( Top ic Preference Vector ) , 某 个用户的主题兴趣向量定义为一个 m 元向量 : T = [ T
( 1) , T ( 2 ) ,
, T (m ) ] , m 指论域中的主题数 , T
对 [ TSPR i ( p )
(p ) ]9 /4 = 1。
]9 /4 进
行 归 一 化 为 ∑m
[ TSPR ( i ) 指用户对第 i 个主题的兴趣度 。向量 T 归一化为 ∑m
公式 ( 4) 描述了用户访问 、主题向量及主题相关页 面的 PageRank 值间的关系 , 其中 V (p ) 值可通过实验观 T ( i ) = 1。
定义 3 主题驱动随机浏览模型 ( Top ic 2D riven Ran 2
d om Surfer M odel, TDRS M ) , 设某个用户具有主题兴趣向 量 T, 在主题驱动随机浏览模型下 , 该用户将以两步来浏 览 W eb: 首先 , 用户选择一个兴趣主题 t, 并以概率 T
( t ) 开始一系列的随机 W eb 浏览 ; 接着其以等概率 ( 1 / n t ) 随机跳转到与主题 t 相关的某个页面 p t , 从该页面开
始 , 用户实施随机浏览 。在浏览的过程中 , 用户以概率 d 随机地选择 p t 的某个外出链接进行跳转 , 该过程中用户选 择某个新的主题 t ’ ( ∈T ) 重新进行跳转浏览的概率为 1
察用户 在 搜索 结 果 上 的 点 击 信 息 测 出 。公 式 ( 4 ) 中
TSPR i (p ) 的值可通过公式 ( 2 ) 计算得到 。公式 ( 4 ) 中
唯一未知的变量为 T 。由公式 ( 4 ) 求解 T 的方法有多 种 , 其中比较流行的有两种 : 线性回归法 (L inear Regres 2 sion ) 与 极 大 相 似 评 价 法 (Maxim u m 2likelihood Estim a 2 t o r ) [ 3 ] 。
由于线性回归法存在一个经典的 “数据稀疏问 题 ”[
4 ] ,
其将影响算法计算的精确性 , 故本文以性能较好 的极大相似评价法来计算用户的兴趣向量 T 。
假设用户已访问 k 个页面 , p i 指第 i 个访问页面 ,
则
m
- d, 以上过程一直重复直到用户结束本会话 。
V T (p ) = ∑T ( i ) ×TS PR i
i = 1
9 /4
为在 TD S M 下具有兴趣向
i = 1 i = 1 ∑ f k = 1 dk, q T
量 T 的用户访问页面 p 的概率 。再假设所有用户访问是彼 此独立的 , 则用户访问页面 p1, , p k 的概率为 ∏k
V (p i ) 。极大相似评价法求解 T 的计算模型为在公式 ( 5 ) 的最大值的约束下求 T 的值 :
∝ Pr ( T ( i ) ) ×Pr ( q | T ( i ) ) ( 7)
这里 Pr ( T ( i ) ) 为用户对主题 i 的兴趣概率 , 按照 兴趣向量 T 的定义 , Pr ( T ( i ) ) = T ( i ) 。 Pr ( q | T
( i ) ) 指用户对主题 i 感兴趣的条件下发出查询 q 的概率 , T = arg max ∏k
V (p i ) (5)
设在 ODP ( http: / /www . d moz. or g ) 中主题 i 下所包含 算法 1 用户兴趣向量学习算法
输入 : 主题 t i ( i = 1, , m ) 输出 : 用户兴趣向量 T = [ T ( 1) , , T (m ) ]
过程 : 1) 系统初始化阶段 。通过查询预处理 , 计算链接到
页面 p j ( j = 1,
, n ) 的页面集合 Lp, Lp 中页面 p0 的
的页面总数为 N i, 索引词条总数为 M i, f dk, q 表示查询 q 在 页面 d k ( k = 1, , N i ) 中出现的次数 , 则 q 在所有有 关主题 i 的页面中出现的次数为 :
N i k = 1 dk, q
则 Pr ( q | T ( i ) ) 计算公式为
[ 5 ]
:
马锡五∑N i
外出链接集合 l p0用户跟随 l p0的概率 d, 计算与 t 相关的页
Pr ( q | T ( i ) ) =
k = 1 f dk, q
M i
( 8)
面集合 n t 。
2) 根据公式 ( 1) 计算页面 —主题关联矩阵 R p t (R p t
为一 m ×n 矩阵 ) , 其行元素即为与 t i ( i = 1, , m ) 相 关的页面偏置随机跳转概率向量 E ti ( p ) = [ E t ( 1 ) ,
, E t ( n ) ] 的各元素值 , 如下所示 :
p1 p2
pn
由公式 ( 6) ～ ( 8) , 具有兴趣向量 T 的用户发出查 询 q 的个性化搜索页面 p 的 PageRank 值计算公式为 :
m
PPR T (p ) = ∑T ( i ) ×Pr ( q | T ( i ) ) ×TS PR i (p )
( 9)
i = 1
算法 2 个性化搜索排序算法 输入 : 用户兴趣向量 T = [ T 1,
, Tm ] , 用户查询
t1 t2 R p t =
tm Et1 (p1) Et1 (p2) Et1 (pn ) Et2 (p1)
Et2 (p2) Et2 (pn )
Etm (p1)
Etm (p2)
E tm (pn )
q 。
输出 : 由 top 2k 页面构成的个性化搜索排序页面集 S p 。 过程 : ①系统初始化阶段 。计算 ODP 中主题 Ti ( i =
其中各元素的计算式为 :
l/ n t , 如果页面 p 与 t 相
关
E t (p )
0,
p 与 t 无关
这里 p = p1,
, pn, 代表 n 个不同页面 , t = t1,
, tm , 代表 m 个不同的主题 。
3) 由前两步的计算结果 , 根据公式 ( 2 ) 计算与主
题 t 相关的页面 p 的权重分值 TSPR t (p ) , 即 :
TSPR t (p ) = ( d × ∑ TSPR t (p0) ) / ( l p0 + ( 1 - p0∈L p
d ) ×E t (p ) )
1, , m ) 所包含的页面总数 N i 及其索引词条数 M i, 查
询 q 在页面 d k ( k = 1, , N i ) 中出现的次数 f dk, q , 进而 计算 q 在所有有关 Ti 的页面中出现的次数 ∑N i f 。 ② 由
①, 根据用户兴趣向量 T = [ T ( 1 ) , , T (m ) ] 及 用户发出的查询信息 q, 由公式 ( 8 ) 分别计算用户在不 同兴趣下发出查询 q 的概率 Pr ( q | T ( i ) ) ( i = 1, , m ) 。 ③重复算法 1 中 ①②, 根据公式 ( 2 ) 计算与 Ti ( i
eels= 1, , m ) 相关的页面 p 的权重分值 TSPR i ( p ) ( i = 1, , m ) 。 ④由 ②③, 根据公式 ( 9 ) 计算具有兴趣向
量 T 的用户发出查询 q 的个性化搜索页面 p 的 PageRank 4) 公式 ( 4) 、 ( 5 ) , 通过极大相似评价法计算出用
户兴趣向量 T = [ T ( 1) , , T (m ) ] , T 中各元素代
表
值 PPR T (p ) , 即 :
m
用户对 m 个不同主题的不同兴趣度 。
312 个性化搜索排序算法
设 PR ( T ( i ) | q ) 为给定查询 q 与某个主题 i 相关 的概率 , 页面 p 的 PageRank 计算公式为 :
m
PR i (p ) = ∑Pr ( T ( i ) | q ) ×TS PR i (p )
(6)
i = 1
根据贝叶斯 (Bayesian ) 计算原理 :
Pr ( T ( i ) | q ) = Pr ( q, T ( i) )
Pr ( q )
救国论坛=
Pr ( T ( i ) ) ×Pr ( q | T ( i ) )
Pr ( q )
PPR T (p ) = ∑T ( i ) ×Pr ( q | T ( i ) ) ×TS PR i (p )
i = 1
这里 p = p1, , pn, 代表 n 个搜索页 面 。 ⑤对 PPR T (p )
中 n 个评分值从大到小进行排序 , 取前 k 个值对应 的页面 , 构建一个基于用户兴趣向量 T 的个性化搜索排序 页面集 S p 。
4 实验及分析
411 实验设置
通过调查浙江工商职业技术学院 10 位人员 (包括学 生 ) , 收集了他们 6个月的搜索历史信息及其所点击的查
T
询结果页面 。同时对上述 10 位测试对象进行人工测验 : 首先从收集的查询历史库中抽取 10 个最频繁的查询 , 接 | ( i, j ) ∶i, j ∈S,σk ( i ) <σk ( j ) ,σ
′k ( i ) >σ′k ( j )
|
| S| ×| S - 1 |
( 11)
着对于每个查询 , 10位测试对象均被随机显示 10 个与该 查询匹配的页面 , 最后要求测试对象从这 10 个页面中选 出自己需要的页面 。实验结果显示 : 对于每个测试对象平 均只有 219个搜索结果与其查询相关 。另外 , 为了实验需 要 , 从 ODP 中选择了 10个第一级主题 , 通过链接结构抓 取了其中的 500万个页面 , 并分别计算了其标准 PageRank
值与主题相关 PageRank 值 [ 5 ] 。实验数据集统计情况如表
1所示 。
式中
σk 为基于本文方法计算得出的个性化排序等级 的 to p 2k 排序页面列表 , σ′k
为基于用户实际兴趣向量计 算得出的个性化排序等级的 top 2k 排序页面列表 , S 为
σk 与 σ′k 的并集 。Γ取值范围为 0 ≤Γ≤1。图 3 显示 k = 20 的实验结果 , 从图中可以看出通过本文学习方法可以
取得 较好的个性化排序性能 。
采用统计度量方法中的平均绝对偏差 MAE (Mean
Abso lute Error ) 对用户兴趣向量的学习精度进行度量 :
top 2k = 20, 采样页面集 L = 100
图 3 页面排序等级分值比较
倒立摆MAE ( Te ) = | Te - T |
| T |
( 10)
5 结束语
式中 T 指用户实际的兴趣向量 , Te 指基于用户点击 历史学习到的用户兴趣向量 。实验结果如图 2所示 。
个性化搜索目前被广泛应用于 W eb 信息检索 , 针对 当前个性化 W eb 搜索中存在的问题 , 本文提出一种基于 用户点击历史信息自动学习其兴趣的架构 , 基于主题相关
PageRank 技术 , 设计了基于用户点击历史自动学习用户
兴趣向量算法与个性化搜索页面排序算法 。实验结果显 示 , 本算法即使在小量点击历史数据的情况下仍能比较精 确地捕捉到用户的兴趣信息 , 从而提高了个性化 W eb 搜 索质量 。 □
采样页面集 L = 100
图 2 用户兴趣向量学习精度误差度量
参考文献
[ 1 ] Krove tz R, Crof t W B. Lexical ambiguity and inf ormation re 2
trieval [ J ]. I nf orma tion Syste m s, 1992, 10 ( 2) : 1152141
图 2中基线测试方法指的是用户对所有主题均取相同 [ 2 ] Haveliwal a T. Top ic 2Se nsitive PageRank [ C ] / / Proceedings of
the Eleventh I ntl. World W ide W eb Conf , 2002
的兴趣权重值的情形。从图 2 可以看出 , 当主题数 K 的 取值只有在一个较小范围时 ( 1≤K ≤10 ) , 本文提出的学 [ 3 ] Cho J, Roy S. Impact of W eb search engines on page populari 2
ty [ C ] / / Proc . of WWW ’04, 2004
习算法的绝对误差才明显小于基线测试算法的误差 , 这说 [ 4 ] Sun J, Zeng H, L iu H, et a l. CubeSVD: A novel app roach to
明当用户兴趣较分散时 , 实验需要收集更多的用户点击历
personalized web search [ C ] / / Proceedings of the
Fourteenth 史信息用以学习其兴趣向量 。
I ntl. World W ide W eb Conf . , 2005
413 个性化排序等级精度测试
[ 5 ] Chirita P, Nejdl W , Paiu R, et a l. U sing ODP metadata to per 2
采用 Kendall 距离公式来测试本文计算得出的页面个
dppe
sonalize search [ C ] / / Proceedings of A CM SIGIR ’05, 2005
性化排序等级与理想的排序等级之间的差距 , 即 :
Γ (σk , σ′k ) =
作者简介 : 陶剑文 , 男 , 1973年生 , 硕士 , 讲师 。 收稿日期 : 2007 - 01 - 23
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议