基于内容和用户行为的查询聚类

程舒杨，熊锦华，公 帅，程学旗

(中国科学院 计算技术研究所，北京 100190)

基于内容和用户行为的查询聚类

程舒杨，熊锦华，公 帅，程学旗

(中国科学院 计算技术研究所，北京 100190)

现有方法没有有效利用查询文本特征、点击行为和session信息来挖掘用户的搜索意图，获取的查询特征对于多意图查询在不同意图下的区分度不足，对于多意图查询的相关查询聚类效果不佳。针对以上问题，该文提出了基于查询图信息的GPLSI模型，并利用该模型学习所得的查询特征进行查询聚类。基于查询图信息的GPLSI模型利用查询的词语、点击和session共现现象，从查询的文本特征、点击行为和session信息等多个方面来模拟查询意图的产生和表现，学习查询在不同搜索意图上的概率分布。最后，实验结果验证了基于查询图信息的PLSI模型用于查询相似度计算和多意图查询聚类中的有效性。

查询聚类；多意图查询；搜索意图

1 引言

正确理解查询的搜索意图可以提供更加准确、个性化的搜索服务，提高搜索结果的质量，改善用户的搜索体验。传统的方法通过查询的聚类或分类来分析、归类用户的需求，并利用这些需求分析结果为用户提供更加细致的查询优化、查询推荐等服务。

由于多数查询的长度较短[1]，用户在查询中所表达的搜索意图往往是具有多义性或多需求性的。传统的方法进行多意图查询不同意图下的相关查询聚类时，不能很好地区分各种意图。查询的文本特征、点击行为和session信息从不同的方面表达了用户的搜索意图，传统方法简单的将词语的频率、点击链接或session信息作为查询的特征或利用这些信息进行查询相似度的计算，没有充分地挖掘包含在这些特征中的搜索意图。在没有考虑搜索意图的情况下，传统的查询特征和相似度计算方法会导致聚类结果的偏差。为了解决这一问题，Guo等人利用LapPLSI模型获取查询意图的概率分布作为查询特征[2]。然而，该模型没有考虑到查询在session中的共现所提供的信息，此外由LapPLSI模型的原理决定了该模型仅把查询点击共现作为一个修正数据，而非模型构建过程中EM算法的基础数据，不一定能达到全局最优解。针对以上问题，本文提出了基于查询图信息的PLSI模型(简称GPLSI模型)，并利用该模型学习所得的查询特征进行查询聚类。GPLSI模型利用查询的词语、点击和session共现现象，从查询的文本特征、点击行为和session信息等多个方面来模拟查询意图的产生和表现，学习查询在不同搜索意图上的概率分布。最后，我们利用实验结果验证了GPLSI模型用于查询相似度计算和多意图查询聚类中的优越性和有效性。

文章的其他部分组织结构如下，第二部分介绍相关工作；第三部分介绍GPLSI模型、模型的拟合以及聚类算法；第四部分对实验过程及结果进行说明；最后是总结和展望。

2 相关工作

查询的意图可以基于查询目的、查询语义分类或查询需求等多个维度进行划分。查询分类是根据已经标注好的查询及其类别训练分类模型，并根据未归类的查询特征将其归类到已经设定好的类别中[3-6]。查询聚类是对查询或查询相关的网页之间的相似度进行计算，采用聚类算法将相似度较高的查询或网页聚为一类，并将聚类的结果群簇作为不同搜索意图的体现，主要分为基于内容的聚类[7-12]、基于点击行为和session信息的聚类[13-17]、综合内容和行为信息的聚类[2，18-20]。

在基于内容聚类的相关研究中，多将词频、tfidf 值作为检索结果的特征，并进行聚类。Hearst等人采用Scatter/Gather聚类方法对检索结果URL页面进行文本层次的聚类[7]。Zamir等人采用STC算法对Web文档的摘要进行聚类[9]。这种类型的聚类方法忽略了点击、session所提供的信息，不能很好的区分文本相似查询的不同搜索意图。

基于点击行为和session信息的查询聚类一般利用搜索日志中的查询点击和session信息来构建查询关系图，利用点击次数、点击共现、session共现等来进行计算点与点之间的相似度或转移概率，并在此基础上进行聚类。Beeferman等人利用查询与其点击的URL构建二部图，将二部图中点与点之间的相似度定义为其邻居节点集合之间的相似度，对二部图中的查询节点和URL节点交替的进行聚合[13]。Craswell等人在查询和文档之间构建了点击图，并利用随机游走算法对图中的点进行聚类[17]。这种类型的聚类方法忽略了查询的文本摘要信息，仅采用用户行为这一单方面的信息来进行分析查询之间的关系。

综合内容和行为信息的聚类中，部分相关工作将内容、点击和session特征进行简单的加权作为查询特征，或将内容、点击和session相似度进行简单的加权作为查询之间的相似度。Wen等人在对查询进行聚类时，利用内容相似度和点击行为相似度的加权作为查询之间的相似度[19]。Hu等人在聚类中利用查询的点击和词语特性挖掘多意图查询的子主题，在相似度计算过程中对点击、内容和URL链接字符串相似度进行加权[18]。但是对于多意图的查询，不同意图的信息混合在内容、行为信息中，不能得到很好的区分。针对这一点，Guo等人利用查询之间的点击共现信息正则化PLSI模型，学习查询意图的概率分布，将这些概率分布作为查询的特征，并在此基础上进行聚类[2]。

3 方法综述

3.1 GPLSI模型

传统的PLSI模型是基于隐语义的统计模型，该模型利用隐含变量来解释数据的共现，例如文档和词的共现[21]。假设现有一组文档D={d1,d2,...,dN}，文档中包含的词的集合为W={w1,w2,...,wM}，该组文档和词的集合共享一组话题Z={z1,z2,...,zK}。根据似然原理，对于观察到的文档-单词对，我们可以获得似然函数如式(1)所示。

(1)

如果将PLSI模型中的文档看作查询及其文本摘要，主题看作用户的搜索意图，我们就可以获得查询在各搜索意图上的概率分布。查询的文本特征、点击信息和session信息从三个不同方面表现了用户的搜索意图，传统的PLSI模型利用隐含变量解释了文档-单词的共现，文献[2]中采用的LapPLSI模型利用查询的点击共现对PLSI模型进行正则化，然而以上模型没有考虑到查询-查询之间的共现信息。查询-查询之间的共现信息，在此指的是不同查询具有相同的点击链接和不同查询出现在同一session中的现象。现有的相关工作中，有许多文献[13-16]、文献[18-19]利用点击共现或session共现来进行查询相似度的计算。由于点击行为和session共现都是用户搜索意图的一种具体表现，故而我们认为不同查询的点击共现和session共现表明了用户在搜索不同查询时具有相同的搜索意图，也正是这些相同的搜索意图触发了相同的点击或驱动用户在同一session内搜索了不同的查询。

在这一假设的基础上，我们构建了GPLSI模型。假定有一包含N个查询的集合Q={q1,...,qN}，该集合中的查询共享一组相同的K个搜索意图S={s1,...,sK}，并且该集合查询的文本摘要中包含的词条集合为W={w1,...,wM}。与传统的PLSI模型类似(如图1(a)所示)，我们可以获得似然函数如式(2)所示。

(2)

在文献[22]中AspectModel的基础上，我们考虑到查询-查询之间共现过程如下(如图1(b)所示)。

1. 以P(sk)的概率选择用户的查询意图；

2. 在查询意图sk下，用户A1以P(qi|sk)的概率搜索了查询qi；

3. 在查询意图sk下，用户A2以P(qj|sk)的概率搜索了查询qj。

图1 GPLSI模型图解

那么(qi,qj)具有相同意图的概率可以计算如式(3)所示。

(3)

我们将qi,qj具有相同的点击链接及其出现在同一session的情况看作(qi,qj)同意图共现的一种表现，也就是说假设c(qi,qj)为查询qi,qj之间相同点击的次数，s(qi,qj)为查询qi,qj出现在同一session中的次数(当i=j时，c(qi,qj)、s(qi,qj)均为0)，那么查询(qi,qj)的共现次数如式(4)所示。

(4)

其中，λs和λc分别为session共现次数和点击共现次数的权重参数。

根据似然原理，对于观察到的查询(qi,qj)共现对，我们可以获得似然函数如式(5)所示。

(5)

综合查询-单词共现似然函数(式(2))、查询-查询共现似然函数(式(5))，我们可到GPLSI模型如式(6)所示。

(6)

3.2 模型拟合

由于GPLSI模型(式(7))由两个部分构成，在每次E步和M步的更新都需要保证两个部分构成的总和不断地增大，并最终收敛，具体如下。

E步，对隐含变量s的后验概率进行计算：

(7)

(8)

3.3 聚类算法

聚类过程中，采用基于查询意图概率分布的cosine相似度进行查询相似度计算，如式(9)所示。

(9)

我们实现了k-means聚类算法和complete-link聚类算法[15]用于查询聚类。

4 实验验证

为了验证GPLSI模型学习所得的查询特征能够有效提高查询相似度计算的准确率，我们将该模型学习所得的概率特征用于相似度计算的效果，与PLSI模型、LapPLSI模型[23]进行对比，并且将基于词频特征的cosine相似度和基于图的相似度计算方法中的random-walk算法[15]作为评估基准。此外，我们将GPLSI模型学习所得的查询意图概率分布信息用于k-means聚类和complete-link聚类中，与PLSI模型、LapPLSI模型进行了对比。

4.1 实验设定

实验中，我们采用了某商业搜索引擎为期一个月的搜索日志，从中随机抽取了9 938条查询作为模型训练的基础数据。为了比较各模型在查询相似度计算方法上的效果，我们挑选了206个多意图的查询作为种子查询，获取搜索日志中与其有共同点击的查询，并对这些查询基于搜索意图进行人工分类，对于每个种子查询的不同搜索意图挑选出三个查询，由此获得了1 581个标注查询。为了比较各模型在查询聚类上的效果，采用同样的方法，我们获得了由91个群簇组成的433个标注数据。最终用于模型构建和学习的数据为12 175条查询及其文本摘要、点击数据和session信息，包含58 665个单词、66 493条URL链接和371 621个session。其中，查询文本信息是通过抽取查询在Google上的搜索结果页面的标题和摘要而得的，点击信息和session信息都是从搜索日志上获得的。通过获取查询与查询之间的点击链接交集和session交集，我们可以获得其点击共现次数和session共现次数。

根据经验，我们设定GPLSI模型中的参数λs为0.1，λc为4.6；设定LapPLSI模型中，Newton-Raphson步长参数为0.1，正则化参数λ为10；并且将PLSI模型、LapPLSI模型、GPLSI模型中的隐含变量个数均设为500。在聚类算法中，我们将聚类的群簇个数设为91。

4.2 评估方法

• 相似度评估指标

假定给予一个种子查询q及其各搜索意图S={s1,s2,...,sK}上的标注查询，可采用文献[24]中的两种指标对不同的相似度计算方法进行评估，如式(10)、式(11)所示。

(10)

(11)

其中，IntraSim(S)指同一搜索意图内不同查询的相似度，而InterSim(S)指不同搜索意图下查询的相似度。我们将采用下面这个指标综合评价查询相似度计算结果的优劣如式(12)所示。

(12)

• 聚类结果评估指标

本文中，我们将采用纯度指标和NMI指标[25]对查询聚类结果进行评估。

用Q,...,}表示人工标注的查询簇的集合，其中∈Q为标注的包含同一意图查询的群簇，N代表集合Q中所有群簇包含的查询数量。假定聚类结果为,...,}，其中∈QΩ为聚类结果中的一个群簇。纯度指标和NMI指标的取值范围在0到1之间，聚类结果质量越高则纯度值和NMI值越高，其计算公式如式(13)、式(14)所示。

(13)

(14)

4.3 实验结果

• 查询相似度实验结果

如图2所示，其中cos-word代表基于文本特征的cosine相似度计算方法，random-walk代表random-walk算法，prob-PLSIprob-LapPLSIprob-GPLSI分别为采用PLSI、LapPLSI与GPLSI模型学习获得的查询意图概率分布{P(sk|qi)}进行相似度计算所得的结果。

图2 查询相似度计算实验结果

• 查询聚类实验结果

如图3所示，采用GPLSI模型学习所得的查询意图概率分布信息用于k-means聚类和complete-link聚类时，其聚类结果的纯度值和NMI值均高于PLSI模型和LapPLSI模型。从结果中可知，采用complete-link聚类方法得到的聚类结果优于k-means方法，而且采用这两种聚类方法对查询进行聚类时，实验结果中纯度越高的聚类结果，其NMI值也越高。实验结果中，GPLSI模型在聚类结果的纯度值和NMI值上较LapPLSI模型的提高较少，主要是由于实验数据中查询之间session共现现象较为稀疏，提供的信息不足所导致的。

5 总结与展望

针对现有方法在多意图查询聚类中的问题，本文提出了GPLSI模型，利用该模型学习所得的查询特征进行查询聚类，并利用实验验证了该模型用于查询相似度计算和多意图查询聚类中的优越性和有效性。在下一步的工作中，我们将研究不同的方式计算查询-查询共现对GPLSI模型拟合效果的影响，并对LDA模型用于查询意图概率计算的效果进行研究。

图3 k-means和complete-link聚类结果

[1]BJJansen,ASprink,TSaracevic.Reallife,realusers,andrealneeds:astudyandanalysisofuserqueriesontheweb[J].InformProcessManage, 2000, 36(2):207-227.

[2]JGuo,XCheng,GXu,etal.Intent-awarequerysimilarity[C]//ProceedingsofCIKM2011.NewYork,NY,USA:ACM, 2011：259-268.

[3]AZBroder,MFontoura,EGabrilovich,etal.Robustclassificationofrarequeriesusingwebknowledge[C]//ProceedingsofSIGIR2007.NewYork,NY,USA:ACM, 2007： 231-238.

[4]XLi,YWang,AAcero.Learningqueryintentfromregularizedclickgraphs[C]//ProceedingsofSIGIR2008.NewYork,NY,USA:ACM, 2008： 339-346.

[5]YLiu,XNi,JSun,etal.Unsupervisedtransactionalqueryclassificationbasedonwebpageformunderstanding[C]//ProceedingsofCIKM2011.NewYork,NY,USA:ACM, 2011： 57-66.

[6]XLi,YWang,DShen,etal.Learningwithclickgraphforqueryintentclassification[J].ACMTransactionsonInformationSystems, 2010, 28(3):Article12.

[7]MAHearst,JOPedersen.Reexaminingtheclusterhypothesis:scatter/gatheronretrievalresults[C]//ProceedingsofSIGIR1996.NewYork,NY,USA:ACM, 1996： 76-84.

[8]XWang,CZhai.Learnfromwebsearchlogstoorganizesearchresults[C]//ProceedingsofSIGIR2007.NewYork,NY,USA:ACM, 2007： 87-94.

[9]OZamir,OEtzioni.Webdocumentclustering:afeasibilitydemonstration[C]//ProceedingsofSIGIR1998.NewYork,NY,USA:ACM, 1998： 46-54.

[10]HJZeng,QHe,ZChen,etal.Learningtoclusterwebsearchresults[C]//ProceedingsofSIGIR2004.NewYork,NY,USA:ACM, 2004： 210-217.

[11]JCKCheung,XLi.Sequenceclusteringandlabelingforunsupervisedqueryintentdiscovery[C]//ProceedingsofWSDM2012.NewYork,NY,USA:ACM, 2012： 383-392.

[12]SVadrevu,CHTeo,SRajan,etal.Scalableclusteringofnewssearchresults[C]//ProceedingsofWSDM2011.NewYork,NY,USA:ACM, 2011： 675-684.

[13]DBeeferman,ABerger.Agglomerativeclusteringofasearchenginequerylog[C]//ProceedingsofKDD2000.NewYork,NY,USA:ACM, 2000： 407-416.

[14]HCao,DJiang,JPei,etal.Context-awarequerysuggestionbyminingclick-throughandsessiondata[C]//ProceedingsofKDD2008.NewYork,NY,USA:ACM, 2008： 875-883.

[15]ESadikov,JMadhavan,LWang,etal.Clusteringqueryrefinementsbyuserintent[C]//ProceedingsofWWW2010.NewYork,NY,USA:ACM, 2010： 841-850.

[16]TYamamoto,TSakai,MIwata,etal.Thewisdomofadvertisers:miningsubgoalsviaqueryclustering[C]//ProceedingsofCIKM2012.NewYork,NY,USA:ACM, 2012： 505-514.

[17]NCraswell,MSzummer.Randomwalksontheclickgraph[C]//ProceedingsofSIGIR2007.NewYork,NY,USA:ACM, 2007： 239-246.

[18]YHu,YQian,HLi,etal.Miningquerysubtopicsfromsearchlogdata[C]//ProceedingsofSIGIR2012.NewYork,NY,USA:ACM: 2012: 305-314.

[19]JWen,JNie,HZhang.Clusteringuserqueriesofasearchengine[C]//ProceedingsofWWW2001.NewYork,NY,USA:ACM, 2001: 162-186.

[20]LMAiello,DDonato,UOzertem,etal.Behavior-drivenclusteringofqueriesintotopics[C]//ProceedingsofCIKM2011.NewYork,NY,USA:ACM, 2011: 1373-1382.

[21]THofmann.Probabilisticlatentsemanticindexing[C]//ProceedingsofSIGIR1999.NewYork,NY,USA:ACM, 1999: 50-57.

[22]THofmann,JPuzicha.UnsupervisedLearningfromDyadicData[C]//Proceedingsofthe1998NeuralInformationProcessingSystems.Cambridge,MA,USA:TheMITPress, 1999, 11: 466-472.

[23]DCai,QMei,JHan,etal.Modelinghiddentopicsondocumentmanifold[C]//ProceedingsofCIKM2008.NewYork,NY,USA:ACM, 2008: 911-920.

[24]IBordino,CCastillo,DDonato,etal.Querysimilaritybyprojectingthequery-flowgraph[C]//ProceedingsofSIGIR2010.NewYork,NY,USA:ACM, 2010: 515-522.

[25]CDManning,PRaghavan,HSchütze. 信息检索导论(第一版)[M].王斌译.北京:人民邮电出版社,2010.

Query Clustering Based on Content and User Behavior

CHENG Shuyang, XIONG Jinhua, GONG Shuai, CHENG Xueqi

(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China)

This paper proposes a probabilistic latent semantic indexing model based on query graph (GPLSI) to learn query features for query clustering in this paper. GPLSI for query-word co-occurrence and query-query co-occurrence simulates the generation of query intent and its representation based on query text, click and session information, and learns the probability distribution of query on different intents. Experimental results illustrate GPLSI’s effectiveness in query similarity measurement and multi-intent query clustering.

query clustering; multi-intent query; query intent

程舒杨(1988—)，硕士，主要研究领域为信息检索。E⁃mail：shuyangcheng@gmail．com公帅(1984—)，博士，主要研究领域为信息检索、机器学习。E⁃mail：gongdonghui@gmail．com熊锦华(1972—)，博士，副研究员，主要研究领域为互联网搜索与挖掘，大规模数据处理，分布式计算。E⁃mail：xjh@ict．ac．cn

1003-0077(2016)02-0121-07

2013-06-08 定稿日期： 2013-10-09

国家重点基础研究发展规划(973计划)项目(2014CB340406，2012CB316303，2013CB329602)；国家自然科学基金(61173064)；国家科技支撑计划项目(2015BAK20B03)；国家科技支撑计划课题(2011BAH11B02,2012BAH39B04)；国家242专项(2012F86)

TP391

A