基于用户查询意图聚类的实时搜索建议可以用图1表示,对于图中涉及Web2．0的Ajax技术及其框架^{[ 9]},本文不作讨论。

图1

	Figure Option ViewDownloadNew Window
	图1 基于查询意图聚类的实时搜索建议流程

系统采用隐式跟踪方法,通过收集访问者的查询行为并测量其对数字资源类别的意图特征值,获取用户查询意图所在。结合用户专业背景,利用K-means算法对相似查询意图的用户聚类。当用户输入查询词时,通过相似度计算在目标用户所属聚类内搜索其最近邻居集,并从最近邻居评价信息中预测目标用户对未评分数字资源类别的兴趣程度,选择评分最高的前N个类别,实时显示在搜索框下方的“Suggest”列表中,供用户选择最匹配的查询主题后提交。

类别按主题内容标引。如果数字资源有两个以上的主题内容,可先对其中一个主题进行标引,再对另一个标引,以此类推。一个类别最多不超过3个主题词。比如期刊数据库中“零价铁还原土壤中邻硝基甲苯的实验研究”的类别为{环境化学,还原},“毛细管柱气相色谱法测定水中12种硝基苯类化合物” 的类别为{分析化学,环境化学,硝基苯类化合物}。

实时搜索建议的目标是降低搜索引擎的信息过载,使用户快速、准确定位自己所需内容的主题,缩小检索范围,因此取得用户查询意图是最终满足该目标至关重要的前提。在系统中,用户意图通过一些能反映其兴趣特征的评分数据表示。由于反馈评价需要较多的人力与时间,且大部分用户并不愿意主动提供评分信息,因此难以大规模展开。而用户查询行为蕴含了其对结果的相关性评价,因此本文根据图书馆数字资源特点采用隐式评分^{[ 10, 11]}。

服务器端日志文件数据量庞大且存在大量冗余数据、噪声信息,无法精确展示访问者在网上的实际行为,因此通过日志方法来追踪、分析用户的查询行为,难度较大,操作也比较繁琐。目前校园网普遍采用上网认证客户端,并且为了延伸服务空间,拓展馆藏资源利用率,大部分高校都建立了数字图书馆远程接入系统,使客户端数据技术有了应用基础。本文通过客户端收集用户的行为特征,解决了以往数据分析中用户识别方法的缺陷以及用户查询行为收集不便等问题。

数据分析中最能反映用户意图的行为有两类：

（1）用户对页面或文档的浏览时间,时间越长表示用户对该文档的关注度越高;

（2）用户复制、保存、下载、打印等操作行为,这类行为往往代表用户对该数字资源内容具有很高的兴趣度。

系统在跟踪用户过程中,首先赋予身份识别,记录其与服务器交互产生的请求,通过数据分析给予用户行为一个评分值,用于计算其兴趣偏好程度。

每个查询都具有可以被预测的类别,而数字资源类别在一定程度上可以反映用户的意图^{[ 12]}。如果用户对一些资源给予了高低不等的评分（隐式评分）,则可以根据这些已评分的数字资源对资源类别的隶属度,计算得到用户对不同资源类别的意图特征值来衡量其对某类资源的偏好程度。由于用户兴趣偏好具有随时间变化的特性,因此在对意图特征值的计算中加入了时间权重。

设DL是一个数字图书馆,C=C１,C２…,Cn为DL中所有数字资源类别的集合,∀c_j∈C,用c_j=cj１,cj２…,cjm表示j类别数字资源中所有资源的集合,则用户u对j类别资源的意图特征值C_u,j为：

C_u,j=∑i∈IuIu,i×γjxi∑i∈Iuγjxi×e^-t i＝１,２,…,n （1）

其中：I_u,i代表用户u对资源i的评分值;I_u代表用户u已评价的数字资源;γ_jxi代表资源i对类别j的隶属度;t代表行为特征发生时间与当前时间差值。

由式（1）计算形成一个用户-数字资源类别矩阵C如下：

C=Cu,jm×n u＝１,２…,n；j＝１,２…,m

其中,m是用户数,n是资源类别数。

对不同资源类别的意图特征值测量是为了获取用户意图所在,也是用户提交查询请求前,系统有针对性地给予其动态搜索建议的基础。

采用Pearson相关系数方法^{[ 13]}对用户意图特征值进行比较,获得用户间的相似度评价值。

设I_i、I_j分别表示用户i与用户j已评分的数字资源类别集合,评分值通过式（1）计算得到。I_i,j表示用户i与用户j有相同评分的资源类别集合,I_i,j=I_i∩I_j,则用户i和用户j之间的相似性simi,j如下：

simi,j=∑c∈Ii,jRi,c-R-iRj,c-R-j∑c∈Ii,jRi,c-R-i２∑c∈Ii,jRj,c-R-j２ （2）

R-i=∑c∈Ii,jRi,ck （3）

R-j=∑c∈Ii,jRj,ck （4）

其中：c属于I_i与I_j的交集,R_i,c、R_j,c分别表示用户i和j对数字资源类别c的评分;R-i和R-j由式（3）、式（4）计算得到,分别表示I_i,j中用户i和用户j的评分均值;k是I_i,j中元素的个数。

实时搜索建议关键在于其提示内容是否具有针对性。当目标用户输入查询词时,搜索引擎感知其查询意图的方法是通过相似系数的计算找到与他兴趣相似的用户,然后将这些用户感兴趣的内容通过搜索建议方式,动态推荐给目标用户,供其选择提交。在这一过程中,如果对全部数据集进行相似性计算,开销极大,且识别最近邻居算法的计算量也随着项目（图书馆数字资源）的增加成线性加大,计算复杂度最终成为系统性能的瓶颈,直接影响搜索建议的实时性。

基于查询意图聚类的算法提出一种解决方案。在整个用户空间,通过意图特征值相似性比较,把用户聚类为若干个不同数据对象集合^{[ 14]}。由于聚类可以离线进行,且查找目标对象最近邻居的范围缩小到与目标对象相似性程度最高的几个聚类,因此降低了实时计算压力,提高了搜索建议的动态响应速度。在相似性比较中,表示用户查询意图的意图特征值之间产生的相似交集远大于已评分的数字资源间产生的交集,解决了相同偏好特征用户可能有不相似的表面评分问题,保证搜索建议的准确度。

聚类采用K-means算法。本文参照文献[7]中k的取值方法,以评分（有效数据）最多的k个用户作为初始k个聚类中心,来消除孤立点对聚类结果产生的负面影响。

设数据集是由n个数据对象组成。k是K-means算法的输人参数,k≤n且每个聚类至少包含一个对象,每个对象属于且仅属于一个聚类。算法主要步骤描述如下：

输入：聚类数目k以及由式（1）计算形成的用户-数字资源类别矩阵C=Cu,jm×n

输出：k个意图特征值相似的用户聚类

主要步骤：

（1）从用户意图特征值数据库中检索所有n个数字资源类别,记为集合I=i１,i２,…,in;以及检索所有m个用户,记为集合U=u１,u２,…,um;

（2）从m个用户中选择评分最多的k个用户作为种子节点,将k个用户对资源类别的意图特征值数据作为初始聚类中心,记为集合CC=cc１,cc２,…,cck;将k个聚类初始化为空,记为集合C=c１,c２,…,ck;

（3）对剩余用户u_i∈U,由式（2）计算其与k个聚类中心cc_j∈CC的相似性simui,ccj;

（4）将每个用户分配到相似性最高的聚类中,simui,ccj=maxsimui,cc１,…,simui,cck,聚类c_m=c_m∪u_i,且c_m∈C;

（5）聚类生成后,计算类中对象的平均值,作为新的初始聚类中心;

（6）重复步骤（3）至步骤（5）,直到聚类结果基本不发生变化、准则函数收敛。准则函数采用平方误差准则,公式如下：

E=∑i＝１k∑p∈cip-mi２ （5）

其中：E是所有对象的平方误差总和,p表示给定的数据对象,m_i是聚类c_i的重心（平均值）。

实时搜索建议产生是在聚类结果的基础上,由式（2）计算得到最近邻居集合,完成从最近邻居评价信息中获得目标用户对未评分数字资源类别的兴趣程度预测。

设最近邻居查询个数为n,目标用户u的最近邻居集合M_i=m１,m２,…,mn,其相似度{sim（u,m₁）,sim（u,m₂）,…,sim（u,m_n）}按从大到小的顺序排列。用户m∈M_i。用户u对数字资源类别i的预测评分P_u,i可以通过计算得到,公式如下^{[ 15]}：

P_u,i=R-u+∑m∈MiRm,i-R-m×simu,m∑m∈Misimu,m （6）

其中：R-u、R-m分别为用户u与m对数字资源类别的平均评分,R_m,i为用户m对数字资源类别i的评分, 评分值由式（1）计算得到;simu,m为用户u和m的相似度,由式（2）计算得到。

目标用户u完成对所有未评分数字资源类别的兴趣程度预测后,选择预测评分最高的前N个类别（Top-N）^{[ 16]},实时给予用户搜索建议,供其选择最匹配的查询主题后提交。

实验在CPU为Intel Core2 Duo E8200、主频为2．66GHz、内存为2GB DDR2 800的机器上运行,在Microsoft Windows XP Professional+MyEclipse平台上使用Java语言开发。

实验数据来自Minnesota大学GroupLens项目组开发并公布的三个MovieLens数据集中的“100k Ratings Data Set”^{[ 17]}。该数据集包含了943位用户对1 682部影片的100 000条评分数据,评分采用5分制且每个用户至少对20部影片进行了评分,其中评分数值越大,表明用户对该电影的偏爱程度越高。

本文对19个大类的全部影片,根据MovieLens数据集提供的u．item中的影片描述信息,按主题内容标引为219个类别。比如把Movie ID为802的影片《Hard Target》标引为{Action,Crime,Thriller};把Movie ID为1065的影片《Koyaanisqatsi》标引为{Documentary,History,War}。219个类别分别用0到218表示。

实验选取MovieLens数据集提供的u．data中的全部原始评分数据。为了有效降低数据集对实验结果的影响,实验采用5折交叉验证法。将实验数据集平均分成5个互不相交的子集,每份数据子集包含20％的评分数据。每次实验选择其中一个数据子集作为测试集,其余4个合为一个训练集（包含80％的评分数据）,把训练集中的记录作为基本用户,对测试集中的目标用户进行推荐测试,循环5次,取5组实验数据的平均值作为最终结果。

（1）搜索建议的实时性实验

以不同的聚类数目k,完成给予目标用户N个主题的搜索提示所耗费的时间来衡量搜索建议的实时性效果。聚类离线计算,k值以评分量最多的45个用户作为取值范围,从5增加到45,间隔为5。采用Top-5（实时给予5个主题的搜索提示）,最近邻居查询个数为15。实验结果如图2所示：

图2

	Figure Option ViewDownloadNew Window
	图2 实时搜索建议所需时间

图2中,实时搜索建议所需时间随聚类数目增大而减少。当聚类数目k大于25时,完成搜索建议所需时间t小于300ms,实时性效果较好。

（2）搜索建议精度对比实验

通过与传统协同过滤算法对照实验,来验证基于查询意图聚类的实时搜索建议效果。评价指标采用平均绝对偏差MAE方法。

设预测的用户评分集合表示为p１,p２,…,pn,对应的实际用户评分集合为q１,q２,…,qn,则平均绝对偏差MAE为：

MAE=∑i＝１Npi-qiN （7）

实验中,初始聚类数目k值取30,目标用户的最近邻居个数从10增加到40,间隔为5,分别计算本文提出的方法与传统的协同过滤算法的MAE。对照实验均采用式（2）计算相似性,式（6）预测用户评分,式（7）作为评价指标。实验结果如图3所示：

图3

	Figure Option ViewDownloadNew Window
	图3 基于查询意图聚类与传统协同过滤算法的实验结果对比

从图3可以看出,当最近邻居查询个数小于30时,基于查询意图聚类方法的评分预测偏差明显小于传统协同过滤算法。当最近邻居查询个数超过30时,二者的MAE值开始接近,但基于查询意图聚类的预测评分与实际用户评分之间的偏差还是小于传统协同过滤。

实验结果表明,基于查询意图聚类的实时搜索建议比传统协同过滤算法具有较小的MAE值,推荐精度也有所改善。

通过用户u在传统向量空间模型（TF-IDF算法）与本文方法中查询Q_u,i的比较,验证基于查询意图聚类的实时搜索建议的检索性能。评测指标采用平均查全率与平均查准率,计算公式如下：

R_u,q（i）=∑i＝１nq（Qu,i）ni×100％ i＝１,２,…,m （8）

p_u,q（i）=∑i＝１nq（Qu,i）Ni×100％ i＝１,２,…,m （9）

其中：Q_u为仅属于用户u使用的查询词集合,Q_u=Qu,１,Qu,２…,Qu,m,∀Q_u,i∈Q_u;R_u,q（i）、P_u,q（i）分别为用户u查询Q_u,i的平均查全率与查准率;N、n分别为查询Q_u,i检索出的文献（影片）总量和用户u的实际评分集合中的相关影片总量;n_q（Q_u,i）为N与n的交集;i为被分别检索的查询词个数。

检索性能由检出相关信息的能力与信息准确度来衡量。但目前在评估算法性能的实验中,被检索出的相关信息量和系统中的相关信息总量并不来自于用户认为最符合其查询意向的文档,而是根据查询结果、查询词与测试集中文档的相关性匹配,是基于一种信息相关程度的“假设”且存在各种主观因素的影响,没有考虑用户信息需求存在的个性差异,因此不能保证评价数据的真实性。本文采用与查询用户实际评分集的文档匹配方法,获取最符合用户查询意图的文档数。

实验以u．item作为测试集。同时对u．data进行处理,去除其中评分小于3的44 625条数据,保证数据能反映用户真实的兴趣。之后,在余留的55 375条数据中按用户分类,组成943个评分集,并抽取评分量最多且评分对象差别较大的10位用户进行查询测试,用户信息描述如表1所示：

表1

表1

表1 查询测试用户信息 用户名 用户ID 总评分数量 总评分类别 数量 查询集中查 询词数量 User1 7 274 110 16 User2 59 280 103 17 User3 130 257 119 17 User4 276 274 106 18 User5 308 257 110 12 User6 416 322 131 18 User7 450 378 115 18 User8 474 257 102 11 User9 592 257 103 13 User10 846 260 117 17

表1 查询测试用户信息

在测试集u．item中,根据用户所属评分集中的评分影片类别描述,提取查询词并组成仅属于该用户的查询集Q_u,查询采用短查询式。实验中只对前50个查询结果进行统计,其余忽略。i取值为10,即在每个用户的查询集Q_u中随机抽取10个查询词用于查询测试。

在使用本文方法进行查询测试时,初始聚类数目k值取30,最近邻居查询个数为15。采用Top-5（给予目标用户5个主题的搜索提示）,并取其中查全率最高的一个搜索提示作为该用户的查询,与传统向量空间模型对比。实验结果如表2所示。

从表2可以看出,与传统向量空间模型相比,使用本文方法查询Q_u,i的查全率平均提高14．70％,查准率平均提高27．55％。实验结果表明,基于查询意图聚类的实时搜索建议能够较好地提高检索性能。

表2

表2

表2 检索性能对比实验结果 用户名 基于用户查询意图聚类 的实时搜索建议 传统向量空间模型检索 算法（TF-IDF） 平均查全率（％） 平均查准率（％） 平均查准率（％） 平均查准率（％） User1 69．94 35．91 55．13 24．75 User2 66．29 31．76 59．28 23．51 User3 72．67 37．62 64．66 29．38 User4 70．13 36．48 56．42 25．33 User5 83．10 42．30 78．49 32．68 User6 75．37 38．84 61．68 27．74 User7 87．00 39．05 81．46 37．86 User8 59．27 32．61 44．50 22．43 User9 62．74 29．21 62．22 31．56 User10 73．25 34．30 63．67 25．52 平均 71．98 35．81 62．75 28．08

表2 检索性能对比实验结果

值得注意的是实验中不管采用哪种查询方法,得到的查准率都相对较低,原因在于n为用户u评分集合中的相关影片数量,其值远小于整个数据集中所有相关影片的总量,以至于N与n的交集n_q（Q_u,i）变小,造成式（9）查准率较低的假象。此外,User9的查全率与查准率分别接近、小于传统向量空间模型,通过分析此用户评分集后,发现是由于其兴趣频繁改变所致,个别现象并不影响实时搜索建议的整体检索性能。