CN101408897A - 一种基于协作过滤的个性化查询扩展方法 - Google Patents

Abstract

一种基于协作过滤的个性化查询扩展方法，属于个性化服务领域，其特征是利用用户群组对搜索结果的种种行为作为对词与词之间关系分析的依据，而不是依据文档中词语的相关性。根据同一个用户聚类内所有用户提交过的查询词以及用户对Web搜索引擎给出的结果的隐式反馈信息而进行查询扩展。该算法不需要用户人为地填写或修改个人兴趣，而是基于用户以往对搜索结果的种种动作，保证了用户兴趣的持久更新。

Description

一种基于协作过滤的个性化查询扩展方法

技术领域

本发明属于个性化服务领域，具体涉及一种基于协作过滤的个性化查询扩展方法。

背景技术

Web信息的日益增长，使人们不得不花费大量的时间搜索和浏览自己需要的信息。传统的搜索引擎比如：AltaVista(www.altavista.com)、Yahoo！(www.yahoo.com)和新一代的搜索引擎比如：Google(www.google.com)满足了人们一定的需要，但由于其通用的性质，仍不能满足不同背景、不同目的和不同时期的个性化查询需求。另外，电子商务应用的日益普及，越来越多的商品可供人们从因特网上挑选和购买。尽管人们可以更加轻松地买到自己需要的物品，但网上琳琅满目，千差万别的商品使消费者很难选择自己中意的产品。通常，人们很想了解别人的看法，并希望有人向他们进行推荐。另外，随着互联网上的资源的日益增多，如何对自己感兴趣的资源进行管理也成为人们越来越关心的问题。很多方面都涉及到个性化服务的需求，由于本发明的着重点在个性化搜索，这里以个性化搜索作为主要背景技术描述。

用户希望从搜索引擎中获得最贴近自己需要的信息，即对于同一查询，不同用户能够获得不同的搜索结果。例如，同样的查询“苹果”，有的用户希望“苹果”作为一种水果，获得它的相关信息；而另外的用户可能希望“苹果”作为一种计算机品牌，获取相关信息。有研究表明：网络用户用于搜索的查询85％是短查询，该类查询一般包括3个或更少数目的查询单词。因此，用户提交的查询通常不能充分表达出搜索相关文档所需的信息。目前，Web搜索引擎广泛采用自动查询扩展方法来解决这个问题，并获得了成功。即在原来查询的基础上，加入与用户用词相关联的词组成新查询，这在一定程度上弥补了用户查询信息的不足。对用户提交的查询进行扩展可以提高查询的准确性，但由于搜索引擎作为通用查询工具，很难做到用户间差异性，也就是说很难实现深入的个性化搜索。

发明内容

本发明的目的是提供一种基于协作过滤的个性化查询扩展方法来解决查询个性化问题。

本发明的特征在于，所述方法是在计算机中依次按以下步骤进行的：

步骤(1)初始化

在所述计算机中设定以下模块：用户兴趣学习模块、用户聚类模块、查询词相似度计算模块以及基于协作过滤的个性化查询扩展模块，其中：

用户兴趣学习模块：

设定：用户动作以及该用户动作对应的兴趣值的映射表：

a.用于下载文档的兴趣值为0.8，

b.用于为文档评分的兴趣值为：评分值/满分值，评分值由用户设定，用户根据对文档内容的兴趣度以及文档外观的怎样打分，满分值为5分，

c.用于为文档添加书签的兴趣值为1，

d.用于为文档删除的书签的兴趣值为-1，

e.在文档级别上，用户u浏览文档d的兴趣度为，w_u，d＝P(spd(u，d)≤spd(u，d’|d’∈D_u))，其中spd(u，d)为用户u阅读文档d的速度，spd(u，d)＝L_d/T_d，L_d为文档d的长度，T_d为用户u阅读文档d的时长，D_u为用户u浏览过的所有文档的集合，用户u阅读速度最慢的文档是最感兴趣的文档，用1表示；

所述在文档级别上的兴趣度按下式计算：w_u，d＝spd(u，d)/spd(u，d’)，其中d’表示用户u阅读速度最快的文章，

用户提交过多次查询后，对同一篇文档d有多种动作，其综合兴趣度用w′_u，d表示： $w_{u,d}^j=\max \left(w_{u,d}^j\right)+a,$ j＝1，…，λ，j为用户动作序号，w_u，d ^j为序号为j的用户动作的兴趣值，α在[0.1，0.3]中取值，

e.在领域级别上用户u浏览文档d的兴趣度为P_ut，公式如下：

$P_{\mathrm{ut}}=P\left(c_t\right|u)=\frac{\underset{d\∈D_u,d\∈c_t}{\mathrm{\Σ}}{w}_{u,d}^{\′}p\left(c_t\right|d)}{\mathrm{size}\left(D_u\right)}$

其中，c_t为序号为t的领域类型，所述领域类型的集合C＝{c₁，c₂，…，c_T}，T为该领域类型C的大小，P(c_t|d)为文档d属于领域c_t的条件概率，D_u为用户u浏览过的所有文档集合，size(D_u)为用户反馈的文档数；

用户聚类模块，用下述KMeans聚类对所以阅读过文档的用户分类，其步骤为：

第一步：随机选择K个用户，其中每个用户k初始代表一个簇中心o_p，p＝1，…，K，

第二步：计算剩余的每个用户u_c各自与各个簇中心o_p的欧氏距离 $d(u_c,O_p)=\sqrt{\underset{t=1}{\overset{K}{\mathrm{\Σ}}}{(p_{u_{c}t}-p_{\mathrm{ot}})}^2},$ 其中，

表示剩余用户u_c对领域的c_t兴趣值，P_ot表示属于簇o_p的用户对所述领域类型c_t的平均兴趣值， $p_{\mathrm{ot}}=\frac{1}{\left|O_p\right|}\underset{u\∈O_p}{\mathrm{\Σ}}{p}_{\mathrm{ut}},$ o_p为所述簇中心的大小，

第三步：根据所述剩余的每个用户u_c与各个簇中的o_p的距离，把u_c给最近的簇中心，

第四步：重新计算每个簇中心对领域类型c_t的平均兴趣值，

第五步：重复上述第一到第四步，直至 $P_{u_{c}t}-P_{\mathrm{ot}}<\mathrm{\&epsiv;},$ 阈值ε取10^-5；

查询相似度计算模块，用于计算与各个用户聚类o_p内所有用户各自的第i次提交的查询词q_i相似的由用户隐式反馈的查询词q′_i组成的列表simList＝{q′₁，q′₂，…，q′_t}，

所述相似查询词q_i满足以下条件：

由用户提交的查询词q_i查询得到的由搜索引擎给出的一组链接集合 ${\mathrm{res}}_{q_i}=\{d_1,d_2,...,d_n\},$ 以及由用户隐式反馈链接集合

来计算两个查询词q_i，q′_i之间的相似度，其公式为：

$\mathrm{similarity}(q_i,q_i^{\&prime;})=\frac{\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{w}_k^i*w_k^{i^{\&prime;}}}{\sqrt{\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{\left(w_k^i\right)}^2*\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{\left(w_k^{i^{\&prime;}}\right)}^2}}$

当计算得到的相似值similarity(q_i，q′_i)大于给定阈值δ，δ取值区间为(0，1)，则将q′_i添加到所述simList表中，否则舍去；

基于协作过滤的个性化查询扩展模块；

第一步，构造属于用户聚类o_p的原始查询词和扩展查询词的组合，用

表示，q_i∈simList，λ_i为-1或1，

第二步，把所述原始查询词和扩展词的组合提交所述搜索引擎，得到扩展查询词，

第三步，当用户属于不同聚类中时，重复上述第一步和第二步；

步骤(2)，用户输入查询词q，得到res_q＝{d₁，d₂，…，d_n}，并依次通过步骤(1)中所述各模块，得到多个个性化扩展查询词以及这些扩展查询词与查询词q之间的相似度排序结果。

本发明的优点在于：(1)体现用户的个性化查询需求，同一查询，不同用户能够获得不同的搜索结果；(2)查询扩展不是依据文档中词语的相关性，而是依据同一个用户聚类内所有用户提交过的查询词以及用户对Web搜索引擎给出的结果的隐式反馈信息。

附图说明

图1是基于协作过滤的个性化查询扩展的体系结构；

图2是个性化查询扩展的处理流程；

图3是查询词相似度(查询词以collaborative filtering为例)，其中：①查询词：协作过滤，②查询扩展词：推荐，③查询扩展词：聚类，④查询扩展词：信息过滤，⑤查询扩展词：计算机，⑥查询扩展词：推荐系统。

具体实施方式

本发明提出了一种基于协作过滤的个性化查询扩展方法，结合协作过滤，利用用户群组对搜索结果的种种行为体现用户的个性化查询以及对用户查询进行扩展，如图1所示，个性化查询扩展包括下述几个步骤：(1)用户兴趣学习，(2)用户聚类，(3)查询词处理，主要涉及查询词相似度的计算，(4)基于协作过滤的个性化查询扩展。

用户兴趣学习

为了实现个性化搜索必须了解用户的搜索意图，要建立一种长期的且能动态更新的方式来学习用户的兴趣.对用户兴趣的捕捉基于用户对以往搜索结果的种种动作。这里设定的资源对象为Web文档。

用户提交一项查询q，搜索引擎相应地给出一组页面链接集合res_q＝{d₁，d₂，…，d_n}。用户对于集合res_q中的页面链接，有些进一步打开浏览，有些下载，这些用户动作体现了用户兴趣。不同的用户动作在用户兴趣中具有的意义不同。如表1所示用户对搜索结果的一些主要动作，其中UID为用户标识，DID为文档标识，如果一篇文档实际存放在多个位置，则这个文档具有多个DID。

表1用户访问行为

其中，对于用户浏览文档来说，判断其对该文档的兴趣度比较复杂，本文根据用户浏览文档的时间长短来衡量，直观的，用户u阅读文档d时间越长，说明u对d的关注程度越高。设u阅读文档d的时间为T_d，文档d的长度为L_d，则u阅读d的速度为：

spd(u，d)＝L_d/T_d

根据上述公式计算用户u对文档d的兴趣度为：

w_u，d＝P(spd(u，d)≤spd(u，d’|d’∈D_u))

其中D_u表示用户u浏览过所有文档集合。上式表明，在用户浏览过的文档中，阅读速度最慢的可以看作是该用户最感兴趣的文档。用户对文档的其他动作对应的兴趣度值见表2。

表2用户动作的兴趣值

对于用户的一次查询q，设定用户u对集合res_q中的每项d具有一定的感兴趣度w_u，d，w_u，d值的大小介于[0，1]，则用户的兴趣表示为：

u＝(<d₁，w_u[1]>，<d₂，w_u[2]>，……，<d_n，w_u[n]>)。

用户兴趣学习(文档级别)

a.将查询q传到搜索引擎S(例如Google)，

b.res_q＝搜索引擎S返回的URL组成的向量，

c.对于res_q的每个URL，w_u[i]＝Interestingness(resq[i]，action[i])，action[i]为用户对resq[i]的动作，

d.利用w_u对res_q进行排序，

用户u提交过多次查询后，若对同一篇文档d有多种动作，其动作值为w_u，d ^j，j＝1，…，λ。则u对d的感兴趣度为多个动作值的综合，即 $w_{u,d}=\max \left(w_{u,d}^j\right)+a$

其中，max(w_u，d ^j)为取w_u，d ^j中最大值，α为常数，且满足 $0\&le;\max \left(w_{u,d}^j\right)+a\&le;1.$ 一般地，α的取值区间为[0.1，0.3]。

由于文档数目巨大，相对地，用户反馈过的文档数目过少，造成用户的兴趣表示非常稀疏。稀疏的数据会影响用户相似度计算和查询扩展的质量。考虑新的表示方式来改进数据稀疏状况。

假定所有文档具有特定的领域类型。领域类型集合为C＝{c₁，c₂，…，c_T}，其中T为集合的大小，c_t表示第t个领域，则文档d表示为一个条件概率的矢量：d＝<p(c₁|d)，p(c₂|d)，…，p(c_T|d)>，其中p(c_t|d)看作文档d属于类c_t的概率。用户u对某一领域c_t的兴趣表示为条件概率p_ut＝p(c_t|u)，则用户在一次查询后对领域的兴趣表示为u_c＝(<c₁，p_u1>，<c₂，p_u2>，…，<c_T，p_uT>)，相对于文档数目来说，领域类型的数目是非常有限的。

设D_u为用户u浏览过的文档集，则u对类别c_t感兴趣的概率可表示为D_u中所有文档属于c_t概率的加权平均：

其中size(D_u)表示用户反馈的文档总数，w_u，d是用户u对文档d的兴趣度。

用户兴趣学习(领域级别)

a.将查询q传到搜索引擎S(例如Google)，

b.res_q＝搜索引擎S返回的URL的向量，

c.用户从res_q选择D_u，

d.对于D_u中的每一篇文档d，如果d属于c_t，则有

f.利用P_ut对c_t(t＝1，…，T)进行排序。

用户聚类

根据基于领域的用户兴趣表示方法对用户的聚类。一般认为：同一个聚类内的用户是相似的；处于不同聚类的用户是相异的。聚类算法有多种，KMeans聚类算法是最常用的基于划分的方法。它以k为参数，把n个用户分为K个簇，以使簇内具有较高的相似度，而簇间的相似度最低。相似度的计算根据一个簇中所有用户的平均值(被看作簇的重心)来进行。首先，随机地选择K个用户，每个用户初始地代表了一个簇中心。对剩余的每个用户u_c，根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。

计算每个用户对象u_c与簇中心o_p(p＝1，…，K)之间的距离(即u_c与o_p的相异度)，最常用的度量方法是欧氏距离，公式为：

$d(u_c,O_p)=\sqrt{\underset{t=1}{\overset{K}{\mathrm{\&Sigma;}}}{(p_{u_{c}t}-p_{\mathrm{ot}})}^2},$ 其中表示剩余用户u_c对领域c_t的兴趣值，

P_ot的值是所有属于簇o_p的用户对领域类型C_t的兴趣值的平均值，即 $p_{\mathrm{ot}}=\frac{1}{\left|O_p\right|}\underset{u\&Element;O_p}{\mathrm{\&Sigma;}}{p}_{\mathrm{ut}}.$ 利用KMeans聚类算法对用户聚类计算步骤如下：

a.任意选择K个用户作为初始的簇中心，

b.根据与每个中心的距离，将每个用户对象赋给“最近”的簇，

c.重新计算每个簇中心对领域类型C_t的平均兴趣值，

d.重复上述三个步骤直至 $P_{u_{c}t}-P_{\mathrm{ot}}<\mathrm{\&epsiv;}$ (一般阈值ε取10^-5)。

查询相似度计算

用于计算与各个用户聚类o_p内所有用户各自的第i次提交的查询词q_i相似的由用户隐式反馈的查询词q′_i组成的列表simList＝{q′₁，q′₂，…，q′_t}，可按照以下步骤进行：

a.由用户提交的查询词q_i查询得到的由搜索引擎给出的一组链接集合 ${\mathrm{res}}_{q_i}=\{d_1,d_2,...,d_n\},$

b.利用

以及由用户隐式反馈链接集合

计算查询词q_i和q′_i之间的相似度值 $\mathrm{similarity}(q_i,q_i^{\&prime;})=\frac{\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{w}_k^i*w_k^{i^{\&prime;}}}{\sqrt{\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{\left(w_k^i\right)}^2*\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{\left(w_k^{i^{\&prime;}}\right)}^2}},$ 如果similarity(q_i，q′_i)大于阈值δ，δ的取值区间为(0，1)，则把q′_i添加到查询词列表simList，δ的取值需要根据该算法实施到的实际系统调整。

基于协作过滤的个性化查询扩展

对于目标用户u，针对其提交的查询q，对该查询进行扩展的基本流程是：

a.构造属于用户聚类o_p的原始查询词和扩展查询词的组合，用

表示，q_i∈simList，λ_i为-1或1，

b.把所述原始查询词和扩展词的组合提交所述搜索引擎，得到扩展查询词，

c.当用户属于不同聚类中时，重复上述第一步和第二步，

步骤二，用户输入查询词q，得到res_q＝{d₁，d₂，…，d_n}，并依次通过步骤一中所述各模块，得到个性化扩展查询词。

如图1所示是个性化查询扩展的处理流程。

我们开发了一个关于学术资源的个性化服务平台，新用户登录到该系统，输入查询词，系统返回搜索结果，用户对搜索结果进行浏览、下载、打分、收藏等操作。当用户再次登录到该系统，输入查询词时，系统将提示有一组词语可以作为当前查询的扩展词，辅助用户查询。系统收集了从2006年6月到2007年4月之间计算机系30位学生老师的搜索记录，对个性化查询扩展算法的测试利用了两个数据集进行测试。其中数据集1下载自Citeseer系统的1700篇文档，17个类，每个类别包含100篇；数据集2包含2312篇论文，属于6个类别：Agents，Artificial Intelligence(AI)，Database(DB)，InformationRetrieval(IR)，Machine Learning(ML)，Human Computer Interaction(HCI)，每个类别的文档数目大致相等。

用户提交查询关键词collaborative filtering，系统计算得到和查询词collaborativefiltering最相似的五个短语recommendation、clustering、information filtering、computer、recommender system，它们与collaborative filtering之间的相似度分别为0.83、0.43、0.35、0.52、0.80，如图3所示，按相似度从大到小排序得到扩展组合collaborative filtering和recommendation、collaborative filtering和recommendersystem、collaborative filtering和clustering、collaborative filtering和computer、collaborative filtering和information filtering，提交给系统进行扩展查询。

Claims (1)

1.一种基于协作过滤的个性化查询扩展方法，其特征在于，所述方法是在计算机中依次按以下步骤进行的：

步骤(1)初始化

在所述计算机中设定以下模块：用户兴趣学习模块、用户聚类模块、查询词相似度计算模块以及基于协作过滤的个性化查询扩展模块，其中：

用户兴趣学习模块：

设定：用户动作以及该用户动作对应的兴趣值的映射表：

a.用于下载文档的兴趣值为0.8，

b.用于为文档评分的兴趣值为：评分值/满分值，评分值由用户设定，用户根据对文档内容的兴趣度以及文档外观的怎样打分，满分值为5分，

c.用于为文档添加书签的兴趣值为1，

d.用于为文档删除的书签的兴趣值为-1，

e.在文档级别上，用户u浏览文档d的兴趣度为，w_u，d＝P(spd(u，d)≤spd(u，d’|d’∈D_u))，其中spd(u，d)为用户u阅读文档d的速度，spd(u，d)＝L_d/T_d，L_d为文档d的长度，T_d为用户u阅读文档d的时长，D_u为用户u浏览过的所有文档的集合，用户u阅读速度最慢的文档是最感兴趣的文档，用1表示；

所述在文档级别上的兴趣度按下式计算：w_u，d＝spd(u，d)/spd(u，d’)，其中d’表示用户u阅读速度最快的文章，

用户提交过多次查询后，对同一篇文档d有多种动作，其综合兴趣度用w′_u，d表示： $w_{u,d}^j=\max \left(w_{u,d}^j\right)+\mathrm{\&alpha;},$ j＝1，…，λ，j为用户动作序号，w_u，d ^j为序号为j的用户动作的兴趣值，α在[0.1，0.3]中取值，

g.在领域级别上用户u浏览文档d的兴趣度为P_ut，公式如下：

$P_{\mathrm{ut}}=P\left(c_t\right|u)=\frac{\underset{d\&Element;D_u,d\&Element;c_t}{\mathrm{\&Sigma;}}{w}_{u,d}^{\&prime;}p\left(c_t\right|d)}{\mathrm{size}\left(D_u\right)}$

其中，c_t为序号为t的领域类型，所述领域类型的集合C＝{c₁，c₂，...，c_T}，T为该领域类型C的大小，P(c_t|d)为文档d属于领域c_t的条件概率，D_u为用户u浏览过的所有文档集合，size(D_u)为用户反馈的文档数；

用户聚类模块，用下述KMeans聚类对所以阅读过文档的用户分类，其步骤为：第一步：随机选择K个用户，其中每个用户k初始代表一个簇中心o_p，p＝1，...，K，第二步：计算剩余的每个用户u_c各自与各个簇中心o_p的欧氏距离 $d(u_c,O_p)=\sqrt{\underset{t=1}{\overset{K}{\mathrm{\&Sigma;}}}{(p_{u_{c}t}-p_{\mathrm{ot}})}^2},$ 其中，

表示剩余用户u_c对领域的c_t兴趣值，P_ot表示属于簇o_p的用户对所述领域类型c_t的平均兴趣值， $p_{\mathrm{ot}}=\frac{1}{\left|O_p\right|}\underset{u\&Element;O_p}{\mathrm{\&Sigma;}}{p}_{\mathrm{ut}},$ o_p为所述簇中心的大小，

第三步：根据所述剩余的每个用户u_c与各个簇中的o_p的距离，把u_c给最近的簇中心，

第四步：重新计算每个簇中心对领域类型c_t的平均兴趣值，

第五步：重复上述第一到第四步，直至 $P_{u_{c}t}-P_{\mathrm{ot}}<\mathrm{\&epsiv;},$ 阈值ε取10^-5；

查询相似度计算模块，用于计算与各个用户聚类o_p内所有用户各自的第i次提交的查询词q_i相似的由用户隐式反馈的查询词q′_i组成的列表simList＝{q′₁，q′₂，...，q′_t}，

所述相似查询词q_i满足以下条件：

由用户提交的查询词q_i查询得到的由搜索引擎给出的一组链接集合 ${\mathrm{res}}_{q_i}=\{d_1,d_2,...,d_n\},$ 以及由用户隐式反馈链接集合resq′_i来计算两个查询词q_i，q′_i之间的相似度，其公式为：

$\mathrm{similarity}(q_i,q_i^{\&prime;})=\frac{\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{w}_k^i*w_k^{i^{\&prime;}}}{\sqrt{\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{\left(w_k^i\right)}^2*\underset{k=1}{\overset{m}{\mathrm{\&Sigma;}}}{\left(w_k^{i^{\&prime;}}\right)}^2}}$

当计算得到的相似值similarity(q_i，q′_i)大于给定阈值δ，δ取值区间为(0，1]，则将q′_i添加到所述simList表中，否则舍去；

基于协作过滤的个性化查询扩展模块；

第一步，构造属于用户聚类o_p的原始查询词和扩展查询词的组合，用

表示，q_i∈simList，λ_i为-1或1，

第二步，把所述原始查询词和扩展词的组合提交所述搜索引擎，得到扩展查询词，

第三步，当用户属于不同聚类中时，重复上述第一步和第二步；

步骤(2)，用户输入查询词q，得到res_q＝{d₁，d₂，...，d_n}，并依次通过步骤(1)中所述各模块，得到多个个性化扩展查询词以及这些扩展查询词与查询词q之间的相似度排序结果。

Images