第12卷第5期 智能系统学报 Vol.12 No.5 2017年10月 CAAI Transactions on Intelligent Systems 0ct.2017 D0I:10.11992/tis.201706096 网络出版地址:htp:/kns.cmki.net/kcms/detail/23.1538.TP.20171021.1349.004.html 基于用户查询日志的网络搜索主题分析 张森',张晨12,林培光1,张春云,郭玉超,任威龙,任可 (1.山东财经大学计算机科学与技术学院,山东济南250014:2.香港科技大学计算机科学及工程学系,香港 999077) 摘要:网络搜索分析在优化搜索引擎方面具有举足轻重的作用,而且对用户个人搜索特性进行分析能够提高搜索 引擎的精准度。目前,大多数已有模型(比如点击图模型及其变体),注重研究用户群体的共同特点。然而,关于如 何做到既可以获取用户群体共同特点又可以获取用户个人特点方面的研究却非常少。本文研究了基于个人用户网 络搜索分析新问题,即通过研究用户搜索的突发性现象,获取个人用户搜索查询的主题分布情况。提出了两个搜索 主题模型,即搜索突发性模型(SBM)和耦合敏感搜索突发性模型(CS-SBM)。SBM假设查询词和URL主题是无关 的,CS-SBM假设查询词和URL之间是有主题关联的,得到的主题分布信息存储在偏Dirichlet先验中,采用Beta分 布刻画用户搜索的时间特性。实验结果表明,每一个用户的网络搜索轨迹都有多种基于用户的独有特点。同时,在 使用大量真实用户查询日志数据情况下,与LDA,DCMLDA、TOT相比,本文提出的模型具有明显的泛化性能优势,并 且有效地描绘了用户搜索查询主题在时间上的变化过程。 关键词:网络搜索:搜索引擎:自然语言处理:主题模型:文本挖掘:突发性:时间分析:参数估计 中图分类号:TP391文献标志码:A文章编号:1673-4785(2017)05-0668-10 中文引用格式:张森,张晨,林培光,等.基于用户查询日志的网络搜索主题分析[J】.智能系统学报,2017,12(5):668-677. 英文引用格式:ZHANG Sen,ZHANG Chen,LIN Peiguang,etal.Web search topic analysis based on user search query logs[J]. CAAI transactions on intelligent systems,2017,12(5):668-677. Web search topic analysis based on user search query logs ZHANG Sen',ZHANG Chen'.2,LIN Peiguang',ZHANG Chunyun', GUO Yuchao',REN Weilong',REN Ke2 (1.School of Computer Science Technology,Shandong University of Finance Economics,Jinan 250014,China;2.Department of Computer Science Engineering,Hong Kong University of Science and Technology,Hong Kong 999077,China) Abstract:Web search analysis plays a critical role in improving the performance of contemporary search engines.In addition,search engine accuracy can be improved by analyzing the individual search properties of users.Most existing models,such as the click graph and its variants,focus on the common characteristics of the group. However,as yet,there has been little investigation of a model that would obtain both the collective group characteristics and the unique characteristics of individual users.In this paper,we investigate user-specific web search analysis,whereby we obtain the topic distributions of the search queries of individual users by determining the burstiness of user searches.We propose two topic models,i.e.,the search burstiness model (SBM)and the coupling-sensitive search burstiness model (CS-SBM).The SBM adopts the assumption that the query words and URL are topically independent,The CS-SBM supposes that the query words and URL are topically relevant.The obtained topic distribution information is stored in skewed Dirichlet priors and a beta distribution is used to capture the temporal properties of the user searches.Our experimental results show that each user's web search trail has unique characteristics,and that in the case of there being a large amount of real query log data,in comparison to the latent Dirichlet allocation (LDA)and topic over time (TOT)models,our proposed models have advantages with respect to generalized performance and effectively describes the temporal change process of user search queries. Keywords:web search;search engine;natural language processing;topic model;data mining;burstiness; temporal analysis;parameter estimate 1931年,Zipf)发现在自然语言中,词的频率与 这种现象称为上下文语言模型中词的突发性。后 它在词汇表中的排名成反比,服从幂律分布,他把 来发现,在金融、基因表达、计算机视觉等方面的数 据也存在这种突发现象。网络搜索已成为人们日 收稿日期:2017-07-01.网络出版日期:2017-10-21 基金项目:国家自然科学基金重点项目(U1201258)教育部人文社会科学研 常生活中必不可少的一部分,用户提交的搜索查询 究项目(15Y】AZ☑H042). 通信作者:张晨.E-mail:zhangchen..sdufe@gmail..com 词是人类智慧的结晶,并在搜索查询和微博等网络
U 2 ) 17 第 12 卷第 5 期 智 能 系 统 学 报 Vol.12 №.5 2017 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2017 DOI:10.11992 / tis.201706096 网络出版地址:http: / / kns.cnki.net / kcms/ detail / 23.1538.TP.20171021.1349.004.html 基于用户查询日志的网络搜索主题分析 张森1 , 张晨1,2 , 林培光1 , 张春云1 ,郭玉超1 , 任威龙1 ,任可2 (1.山东财经大学 计算机科学与技术学院,山东 济南 250014;2. 香港科技大学 计算机科学及工程学系,香港 999077) 摘 要:网络搜索分析在优化搜索引擎方面具有举足轻重的作用,而且对用户个人搜索特性进行分析能够提高搜索 引擎的精准度。 目前,大多数已有模型(比如点击图模型及其变体),注重研究用户群体的共同特点。 然而,关于如 何做到既可以获取用户群体共同特点又可以获取用户个人特点方面的研究却非常少。 本文研究了基于个人用户网 络搜索分析新问题,即通过研究用户搜索的突发性现象,获取个人用户搜索查询的主题分布情况。 提出了两个搜索 主题模型,即搜索突发性模型(SBM)和耦合敏感搜索突发性模型(CS-SBM)。 SBM 假设查询词和 URL 主题是无关 的,CS-SBM 假设查询词和 URL 之间是有主题关联的,得到的主题分布信息存储在偏 Dirichlet 先验中,采用 Beta 分 布刻画用户搜索的时间特性。 实验结果表明,每一个用户的网络搜索轨迹都有多种基于用户的独有特点。 同时,在 使用大量真实用户查询日志数据情况下,与 LDA、DCMLDA、TOT 相比,本文提出的模型具有明显的泛化性能优势,并 且有效地描绘了用户搜索查询主题在时间上的变化过程。 关键词:网络搜索;搜索引擎;自然语言处理;主题模型;文本挖掘;突发性;时间分析;参数估计 中图分类号:TP391 文献标志码:A 文章编号:1673-4785(2017)05-0668-10 中文引用格式:张森, 张晨, 林培光,等.基于用户查询日志的网络搜索主题分析[J]. 智能系统学报, 2017, 12(5): 668-677. 英文引用格式:ZHANG Sen, ZHANG Chen, LIN Peiguang, et al. Web search topic analysis based on user search query logs[ J]. CAAI transactions on intelligent systems, 2017, 12(5): 668-677. Web search topic analysis based on user search query logs ZHANG Sen 1 , ZHANG Chen 1,2 , LIN Peiguang 1 , ZHANG Chunyun 1 , GUO Yuchao 1 , REN Weilong 1 , REN Ke 2 (1. School of Computer Science & Technology, Shandong University of Finance & Economics, Jinan 250014, China; 2.Department of Computer Science & Engineering, Hong Kong University of Science and Technology, Hong Kong 999077, China) Abstract:Web search analysis plays a critical role in improving the performance of contemporary search engines. In addition, search engine accuracy can be improved by analyzing the individual search properties of users. Most existing models, such as the click graph and its variants, focus on the common characteristics of the group. However, as yet, there has been little investigation of a model that would obtain both the collective group characteristics and the unique characteristics of individual users. In this paper, we investigate user-specific web search analysis, whereby we obtain the topic distributions of the search queries of individual users by determining the burstiness of user searches. We propose two topic models, i.e., the search burstiness model (SBM) and the coupling⁃sensitive search burstiness model (CS⁃SBM). The SBM adopts the assumption that the query words and URL are topically independent, The CS⁃SBM supposes that the query words and URL are topically relevant. The obtained topic distribution information is stored in skewed Dirichlet priors and a beta distribution is used to capture the temporal properties of the user searches. Our experimental results show that each user’ s web search trail has unique characteristics, and that in the case of there being a large amount of real query log data, in comparison to the latent Dirichlet allocation (LDA) and topic over time ( TOT) models, our proposed models have advantages with respect to generalized performance and effectively describes the temporal change process of user search queries. Keywords:web search; search engine; natural language processing; topic model; data mining; burstiness; temporal analysis; parameter estimate 收稿日期:2017-07-01. 网络出版日期:20 -10-21. 基金项目:国家自然科学基金重点项目( 1 01258 1931 年,Zipf [1]发现在自然语言中,词的频率与 它在词汇表中的排名成反 通信作者:张晨. E⁃mail: zhangchen.sdufe@ gmail.com. 比,服从幂律分布,他把 这种现象称为上下文语言模型中词的突发性。 后 来发现,在金融、基因表达、计算机视觉等方面的数 据也存在这种突发现象。 网络搜索已成为人们日 常生活中必不可少的一部分,用户提交的搜索查询 词是人类智慧的结晶,并在搜索查询和微博等网络 教育部人文社会科学研 究项目(15YJAZH042).
第5期 张森,等:基于用户查询日志的网络搜索主题分析 ·669. 信息中显现出与传统的自然语言不同的特点,网络 型并不能预测词汇突发性出现的趋势。 搜索中每一个用户的搜索条目都包括查询词和 为了能够在获取主题的同时预测词汇突发性 URL两项。已经提出的Dirichlet Compound 现象,G.Doylets)提出了DCMLDA主题模型,该模型 Multinomial(DCM)模型[)和Dirichlet Compound 结合了DCM和LDA的优势,直接将DCM扩展合并 Multinomial Latent Dirichlet Allocation (DCMLDA) 到主题模型里面形成了一个比LDA更加复杂的模 型]可以对文章中词的突发性现象建模,但如果直 型。在DCMLDA中对于每个主题k和每个文档d 接应用于网络搜索建模却不是很理想。虽然大多 服从新的多项式分布Oa,每个主题k都有不同的 数的点击图模型)及其变体[s可以对网络搜索建 非均匀的B。向量。对于每一个文档d,Pu根据 模,但都是针对用户群体进行研究而忽略了用户个 Dirichlet(B,)的变化而变化,因此每个主题实例在 人特点。 文档之间是相互联系的。文档中的主题实例允许 本文通过分析用户查询日志来获取网络搜索 在同一主题不同文档中每一个词汇的概率不同,这 突发现象,并提出了两个模型:SBM(search 也就是突发现象。 burstiness model CS-SBM coupling-sensitive 随着带有时间标记的文本集合(例如,数字化 search burstiness model)。SBM是一个单极模型,假 的报纸、杂志、博客等)数量和体积的增加,如何有 设查询词和URL之间主题独立,突发性的相关信息 效地搜索这些数据变得更加重要。上述模型都难 存储在偏Dirichlet先验里。CS-SBM充分考虑查询 以发现主题的演化趋势。在这个背景下,文献[9] 词和URL之间的关联。本文还用Beta分布刻画了 等提出了Topic Over Time(TOT)模型。TOT将文档 用户搜索的时间特性,使前面提出的模型能够用来 的时间信息作为服从Bta分布的变量,将每个主题 捕获时间上的突发性。 通过Beta分布与时间信息相关联。TOT假设每个 生成的词汇对应的时间信息也是通过它所属主题 1 相关工作 相关的Beta分布采样生成,这样主题与时间信息也 Madsen指出,多项分布经常用于文本建模。然 有关系。T0T不依赖马尔可夫假说,这样能够避免 而,多项分布能获取到文档中词汇的突发性现象, 在离散化过程中遇到时间粒度选取的问题。 即一个词如果出现过一次,那么它很有可能再次出 另外,文献[10]系统地总结了自然语言处理中 现[)。因此Madsen提出了Dirichlet多项分布 主题模型的发展,对LDA模型进行了详细的分析,并 (DCM)来代替传统的多项分布。DCM拥有一级自 对主题模型的发展趋势进行了预测。根据微博的特 由度,能获取到词的突发性,但是没有涉及文档中 殊形式,在LDA的基础上进行了改进,分别提出了 词汇的主题。文献[2]将DCM模型扩展成为了混 (MicroBlogs--LDA)MB-LDA模型m和(MicroBlogs 合DCM分布,该模型能够训练表示一组文档,其中 HDP)MB-HDP模型2)],同时证明了提出模型能够很 每一个文档都来自不同的高级主题。但是,该模型 好地对微博进行主题挖掘。 还是不能建模一个文档包含多个主题单词的情景。 以前的工作都是集中在对自然语言文本中的 上述工作中,之所以不能很好地刻画文档主 同质项目进行分析,即对一个文档中的同质词汇进 题,其主要原因是DCM更关注突发性现象而非获取 行建模。然而在网络搜索分析中,文档是由查询词 文档主题。2003年Bleits]提出的Latent Dirichlet 和URL两个异构项目组成,并且带有时间信息。因 Allocation(LDA)是非监督的贝叶斯生成模型,它 此,本文结合网络搜索查询的文本特点,提出并研 可以将文档集中每篇文档的主题按照概率分布的 究了将主题模型运用到网络搜索分析中,对查询词 形式给出。LDA包括词汇、主题和文档3层。LDA 和URL这两个异构项目和它们之间的关系进行 引入了Dirichlet先验分布,成为了一个完备的贝叶 建模。 斯模型。LDA文档生成过程为,从Dirichlet分布中 2以用户为中心的概率主题模型 采样文档与主题、主题与词汇分布,再重复从文档 主题多项式分布中采样主题以及由主题-词汇多项 本节主要介绍了SBM和CS-SBM主题模型,以 式分布生成词汇的过程,逐步生成整个文档。LDA 及获取主题时间突发性的策略。 已经在学术和工业界得到广泛应用。但是,LDA模 提出的模型应具备以下条件:
信息中显现出与传统的自然语言不同的特点,网络 搜索中每一个用户的搜索条目都包括查询词和 URL 两 项。 已 经 提 出 的 Dirichlet Compound Multinomial ( DCM) 模 型[2] 和 Dirichlet Compound Multinomial Latent Dirichlet Allocation (DCMLDA)模 型[3]可以对文章中词的突发性现象建模,但如果直 接应用于网络搜索建模却不是很理想。 虽然大多 数的点击图模型[4]及其变体[5-6]可以对网络搜索建 模,但都是针对用户群体进行研究而忽略了用户个 人特点。 本文通过分析用户查询日志来获取网络搜索 突发 现 象, 并 提 出 了 两 个 模 型: SBM ( search burstiness model ) 和 CS⁃SBM ( coupling⁃sensitive search burstiness model)。 SBM 是一个单极模型,假 设查询词和 URL 之间主题独立,突发性的相关信息 存储在偏 Dirichlet 先验里。 CS⁃SBM 充分考虑查询 词和 URL 之间的关联。 本文还用 Beta 分布刻画了 用户搜索的时间特性,使前面提出的模型能够用来 捕获时间上的突发性。 1 相关工作 Madsen 指出,多项分布经常用于文本建模。 然 而,多项分布能获取到文档中词汇的突发性现象, 即一个词如果出现过一次,那么它很有可能再次出 现[7] 。 因 此 Madsen 提 出 了 Dirichlet 多 项 分 布 (DCM)来代替传统的多项分布。 DCM 拥有一级自 由度,能获取到词的突发性,但是没有涉及文档中 词汇的主题。 文献[2] 将 DCM 模型扩展成为了混 合 DCM 分布,该模型能够训练表示一组文档,其中 每一个文档都来自不同的高级主题。 但是,该模型 还是不能建模一个文档包含多个主题单词的情景。 上述工作中,之所以不能很好地刻画文档主 题,其主要原因是 DCM 更关注突发性现象而非获取 文档主题。 2003 年 Blei [8] 提出的 Latent Dirichlet Allocation (LDA) 是非监督的贝叶斯生成模型,它 可以将文档集中每篇文档的主题按照概率分布的 形式给出。 LDA 包括词汇、主题和文档 3 层。 LDA 引入了 Dirichlet 先验分布,成为了一个完备的贝叶 斯模型。 LDA 文档生成过程为,从 Dirichlet 分布中 采样文档与主题、主题与词汇分布,再重复从文档- 主题多项式分布中采样主题以及由主题-词汇多项 式分布生成词汇的过程,逐步生成整个文档。 LDA 已经在学术和工业界得到广泛应用。 但是,LDA 模 型并不能预测词汇突发性出现的趋势。 为了能够在获取主题的同时预测词汇突发性 现象,G.Doyle [3]提出了 DCMLDA 主题模型,该模型 结合了 DCM 和 LDA 的优势,直接将 DCM 扩展合并 到主题模型里面形成了一个比 LDA 更加复杂的模 型。 在 DCMLDA 中对于每个主题 k 和每个文档 d 服从新的多项式分布 θkd ,每个主题 k 都有不同的、 非均匀的 βk 向量。 对于每一个文档 d, φkd 根据 Dirichlet(βk )的变化而变化,因此每个主题实例在 文档之间是相互联系的。 文档中的主题实例允许 在同一主题不同文档中每一个词汇的概率不同,这 也就是突发现象。 随着带有时间标记的文本集合(例如,数字化 的报纸、杂志、博客等) 数量和体积的增加,如何有 效地搜索这些数据变得更加重要。 上述模型都难 以发现主题的演化趋势。 在这个背景下,文献[9] 等提出了 Topic Over Time(TOT)模型。 TOT 将文档 的时间信息作为服从 Beta 分布的变量,将每个主题 通过 Beta 分布与时间信息相关联。 TOT 假设每个 生成的词汇对应的时间信息也是通过它所属主题 相关的 Beta 分布采样生成,这样主题与时间信息也 有关系。 TOT 不依赖马尔可夫假说,这样能够避免 在离散化过程中遇到时间粒度选取的问题。 另外,文献[10]系统地总结了自然语言处理中 主题模型的发展,对 LDA 模型进行了详细的分析,并 对主题模型的发展趋势进行了预测。 根据微博的特 殊形式,在 LDA 的基础上进行了改进,分别提出了 (MicroBlogs⁃LDA) MB⁃LDA 模 型[11] 和 ( MicroBlogs⁃ HDP)MB⁃HDP 模型[12] ,同时证明了提出模型能够很 好地对微博进行主题挖掘。 以前的工作都是集中在对自然语言文本中的 同质项目进行分析,即对一个文档中的同质词汇进 行建模。 然而在网络搜索分析中,文档是由查询词 和 URL 两个异构项目组成,并且带有时间信息。 因 此,本文结合网络搜索查询的文本特点,提出并研 究了将主题模型运用到网络搜索分析中,对查询词 和 URL 这两个异构项目和它们之间的关系进行 建模。 2 以用户为中心的概率主题模型 本节主要介绍了 SBM 和 CS⁃SBM 主题模型,以 及获取主题时间突发性的策略。 提出的模型应具备以下条件: 第 5 期 张森,等:基于用户查询日志的网络搜索主题分析 ·669·
·670 智能系统学报 第12卷 1)查询词和URL的突发性现象研究要分开 O和p以后,通过借鉴LDA和DCMLDA中Gibbs采 建模。 样的方法,在SBM中概率P(za)为 2)建模时,网络搜索特点,包括查询词、URL和 session3个维度都要考虑在内[4-1]。 T(∑a, ΠT(n+) P(za)= session是指在短时间内提交的满足相同信息 Πr(a,) 需求的一系列查询。为了避免同一会话中包含不 a+a 相干的查询而导致的性能降低,本文优先考虑同一 式中n4为第d个文档中主题z的数量。 会话中查询词之间的语义一致性。通过对比分析, 概率P(wlz,B)为 本文采用文献[16]提出的一系列规则来划分搜索 IIr(na.+B) session。这些规则用于评估查询之间的词汇相似 =1 P(w zB) 性,并在检测相关搜索查询时表现出很高精度。 2.1查询词和URL独立的主题模型(SBM) 式中n.为第d个文档中第k个主题下查询词w的 SBM的生成过程是基于查询词和URL相互独 个数。 立的假设。与LDA和DCMLDA等传统主题模型不 当该session中没有URL被点击时的条件概 同,SBM中的文档有查询词、被点击URL和查询时 率为 间三项。图1是SBM的搜索主题模型概率图。首 C+a 先,从超参数为a的Dirichlet分布中抽样生成文档 P(z=k X:0,z,w,u,a,B,8) 与主题之间的关系矩阵0,0是一个D×K的矩阵,其 中D代表文档数量,K代表主题数。对于每一个主 题k,从超参为B,和δ的Dirichlet分布中分别取样 T(Σ(C+B) =1 I(cop +B.+N) 生成查询词与主题之间的关系矩阵0和URL与主 三(c+B+,) T(C四+B.) 题之间的关系矩阵2.0和2是DxK×V的三维矩 阵,V代表训练语料库中出现的所有词的词表。对 式中:C表示文档d中分配主题为k的session的 于文档中的每一个session,从参数为0,的多项分布 数量,C表示文档d中查询词w被分配主题k的 中选择一个主题:,从参数为P的查询词的多项分 次数,N表示第i个session中查询词0的个数。 布中,采样生成查询词心。然后,生成点击事件的二 当一个session中有URL被点击时的条件概 项分布,如果URL被点击了,从参数为2的URL 率为 的多项分布中,采样生成URLu。变量0和δ是基 CaK og P(a=k1X=1,2-,w,u,cB,8)x 于单个特定文档的,因此SBM可以为每一个用户查 乞(C+a) 询词和URL的突发性建模。 @ rΣ(c世+B》 w=1 T(C"+B4+N) 0 宫G+a+》 T(C四+BA) r宫+】 T(C+δ4+N) D Π 图1SBM网络搜索分析主题模型 T∑(C"+a4+N) T(C+δ4) = Fig.1 SBM web search analysis topic model 式中,C表示文档d中URLu被分配主题k的次 SBM中的Gibbs采样方法借鉴了LDA和 数,Wn表示第i个session中URLu的数量。 DCMLDA中Gibbs采样的方法,并进行了推导。模 2.2查询词和URL相关联的主题模型(CS-SBM) 型的完全似然函数为 查询词和URL通过搜索引擎紧密地结合在一 P(w,u,zla,B,6)=P(ulz,6)P(w|z,B)P(z|a) 起,这使得本文研究的问题变得更加复杂。被点击 展开上式中的多项分布和Dirichlet分布,利用多项 的URL是由对应的查询词经过搜索得出的。在网 分布和Dirichlet分布的共轭性质,分别积分掉参数 络搜索的情境中,URL是提交查询词给搜索引擎后
1)查询词和 URL 的突发性现象研究要分开 建模[13] 。 2)建模时,网络搜索特点,包括查询词、URL 和 session 3 个维度都要考虑在内[14-15] 。 session 是指在短时间内提交的满足相同信息 需求的一系列查询。 为了避免同一会话中包含不 相干的查询而导致的性能降低,本文优先考虑同一 会话中查询词之间的语义一致性。 通过对比分析, 本文采用文献[16] 提出的一系列规则来划分搜索 session。 这些规则用于评估查询之间的词汇相似 性,并在检测相关搜索查询时表现出很高精度。 2.1 查询词和 URL 独立的主题模型(SBM) SBM 的生成过程是基于查询词和 URL 相互独 立的假设。 与 LDA 和 DCMLDA 等传统主题模型不 同,SBM 中的文档有查询词、被点击 URL 和查询时 间三项。 图 1 是 SBM 的搜索主题模型概率图。 首 先,从超参数为 α 的 Dirichlet 分布中抽样生成文档 与主题之间的关系矩阵 θ,θ 是一个 D×K 的矩阵,其 中 D 代表文档数量,K 代表主题数。 对于每一个主 题 k,从超参为 βk 和 δk 的 Dirichlet 分布中分别取样 生成查询词与主题之间的关系矩阵 θ 和 URL 与主 题之间的关系矩阵 Ω。 θ 和 Ω 是 D×K×V 的三维矩 阵,V 代表训练语料库中出现的所有词的词表。 对 于文档中的每一个 session,从参数为 θd 的多项分布 中选择一个主题 z,从参数为 φzd的查询词的多项分 布中,采样生成查询词 w。 然后,生成点击事件的二 项分布,如果 URL 被点击了,从参数为 Ωzd的 URL 的多项分布中,采样生成 URL u。 变量 θ 和 δ 是基 于单个特定文档的,因此 SBM 可以为每一个用户查 询词和 URL 的突发性建模。 图 1 SBM 网络搜索分析主题模型 Fig.1 SBM web search analysis topic model SBM 中 的 Gibbs 采 样 方 法 借 鉴 了 LDA 和 DCMLDA 中 Gibbs 采样的方法,并进行了推导。 模 型的完全似然函数为 P(w,u,z α,β,δ) = P(u z,δ)P(w z,β)P(z α) 展开上式中的多项分布和 Dirichlet 分布,利用多项 分布和 Dirichlet 分布的共轭性质,分别积分掉参数 θ 和 φ 以后,通过借鉴 LDA 和 DCMLDA 中 Gibbs 采 样的方法,在 SBM 中概率 P(z α)为 P(z α) = Γ(∑ K z = 1 αz) ∏ K z = 1 Γ(αz) æ è ç ç ç ö ø ÷ ÷ ÷ D ∏ D d = 1 ∏ T z = 1 Γ(ndz + αz) Γ(∑ Z z = 1 (ndz + αz)) 式中 ndz为第 d 个文档中主题 z 的数量。 概率 P(w|z,β)为 P(w z,β) = ∏ D d = 1 ∏ K k = 1 Γ(∑ W w = 1 βkw) ∏ W w = 1 Γ(βkw) ∏ W w = 1 Γ(ndkw + βkw) Γ(∑ W w = 1 (ndkw + βkw)) æ è ç ç ç ö ø ÷ ÷ ÷ 式中 ndkw为第 d 个文档中第 k 个主题下查询词 w 的 个数。 当该 session 中没有 URL 被点击时的条件概 率为 P(zi = k Xi = 0,z -i,w,u,α,β,δ) ∝ C DK dk + αk ∑ K k′ = 1 (C DK dk′ + αk ′) · Γ(∑ W t = 1 (C KWD kwd + βwk)) Γ(∑ W t = 1 (C KWD kwd + βwk + Niw)) ∏ W w = 1 Γ(C KWD kwd + βwk + Niw) Γ(C KWD kwd + βw) 式中:C DK dk 表示文档 d 中分配主题为 k 的 session 的 数量,C KWD kwd 表示文档 d 中查询词 w 被分配主题 k 的 次数,Niw表示第 i 个 session 中查询词 w 的个数。 当一个 session 中有 URL 被点击时的条件概 率为 P(zi = k | Xi = 1,z -i,w,u,α,β,δ) ∝ C DK dk + αk ∑ K k′ = 1 (C DK dk′ + αk ′) · Γ(∑ W w = 1 (C KWD kwd + βwk)) Γ(∑ W w = 1 (C KWD kwd + βw + Niw)) ∏ W w = 1 Γ(C KWD kwd + βwk + Niw) Γ(C KWD kwd + βwk) · Γ(∑ U u = 1 (C KUD kud + δuk)) Γ(∑ U u = 1 (C KUD kud + δuk + Niu)) ∏ U u = 1 Γ(C KUD kud + δuk + Niu) Γ(C KUD kud + δuk) 式中,C KUD kud 表示文档 d 中 URL u 被分配主题 k 的次 数,Niu表示第 i 个 session 中 URL u 的数量。 2.2 查询词和 URL 相关联的主题模型(CS⁃SBM) 查询词和 URL 通过搜索引擎紧密地结合在一 起,这使得本文研究的问题变得更加复杂。 被点击 的 URL 是由对应的查询词经过搜索得出的。 在网 络搜索的情境中,URL 是提交查询词给搜索引擎后 ·670· 智 能 系 统 学 报 第 12 卷
第5期 张森,等:基于用户查询日志的网络搜索主题分析 .671 返回的结果。因此,URL和查询词是相关的。为了 数量。 获取它们两者之间的关系,这里引入变量△ku来 当session中没有URL被点击时的条件概率为 代表“查询词-URL”的多项分布,其先验由δ表示。 P(a:=k|X=0,z-,w,u,a,B,8,Ψ) “查询词-URL”多项式通过目前已经被广泛采用的 点击图来获得,点击图由搜索查询和被点击的URL T(∑(C+B) f=1 两部分组成。用于表示全局部分的CS-SBM定义为 CS-SBM-G。因为本文重点研究以单个用户为核心 名+ rΣ(C+R4+M) 1=1 的信息能否增强主题模型的表现,所以基于单个用 (CK+B+N) 户“查询词-URL”多项分布的CS-SBM定义为CS- Π I(CKu+B.) SBM-U。 当session中有URL被点击时的条件概率为 图2给出了CS-SBM的生成过程。与SBM相 P(z;=kI X:=1,z-,w,t,u,a,B,6,V) 比,查询词的生成过程不变,两者最主要的区别在 于,CS-SBM在URL生成的时候要考虑查询词的影 C+ag T(∑(C四+B) =1 响,对于session中每一个查询项q,首先生成点击事 件的二项分布,如果URL被点击了,则从参数为2 宫c赠·R.+》 的URL多项分布中采样生成URLu。 T∑(C+6) (a rC吧+Bs+N m=1 I(CID +B.) qesi (0 r(∑(C+i+N)) T(C+δ+Na) Π T(c4+δ.) 式中:C2表示在一个session里查询项g中的 ⑥ URLu被分配主题为z的次数;N.表示session i中 URL的数量。 D 2.3主题在时间上的突发性 图2CS-SBM网络搜索分析主题模型 网络搜索中另一个常见现象就是时间上的突 Fig.2 CS-SBM web search analysis topic model 发性。一个用户更倾向于在一个很短的时间内集 模型的完全似然函数为 中查询一些内容。因此,本文假设每一个用户的查 P(w,u,zla,B,6)=P(ulz,w,8)P(wz.B)P(zla) 询轨迹都有一个时间上的突发性,这种突发性由与 在CS-SBM中,同样采用了与LDA类似的 查询相关的时间戳来体现。因为时间粒度是很难 Gibbs采样方法。P(zla)和P(wlz,B)都与SBM中 设定的,所以本文采用TOT中提出的方法,使用连 的相同。两者主要的区别就是给定的主题中的 续的Beta分布来捕获主题时间上的突发性。通过 和u不再相互独立。“的生成过程可能受到主题z 引入Beta分布,使一个主题能够更容易在一个短的 和相关搜索查询g的影响。 时间周期内出现。在这种情况下,本文从整个语料 P(uI z.w6)= 库级别(定义为X-TG)和基于单一用户级别(定义 为X-TU)出发,刻画一个主题在时间上的变化 iipus14aii(a.1)w= 趋势。 因为主题-周期的多项分布是固定的(对每一 i114-1i 个用户而言),所以主题中存在的时间周期将会证 明突发性。每天或者每小时都可以观察到突发性 Πr() 现象,这表明去离散化是更合适的。 m=1 下面是SBM和CS-SBM在添加了时间信息以 ⅡT(ne+) 后的模型算法。 M- the same as the original model 1r(6) T(∑(ne+i) for each session s in d do 式中,nm是第z个主题的第q个查询中的URLu的 choose a topic z:Multinomial();
返回的结果。 因此,URL 和查询词是相关的。 为了 获取它们两者之间的关系,这里引入变量 Δqku 来 代表“查询词-URL”的多项分布,其先验由 δ 表示。 “查询词-URL”多项式通过目前已经被广泛采用的 点击图来获得,点击图由搜索查询和被点击的 URL 两部分组成。 用于表示全局部分的 CS⁃SBM 定义为 CS⁃SBM⁃G。 因为本文重点研究以单个用户为核心 的信息能否增强主题模型的表现,所以基于单个用 户 “查询词-URL”多项分布的 CS⁃SBM 定义为 CS⁃ SBM⁃U。 图 2 给出了 CS⁃SBM 的生成过程。 与 SBM 相 比,查询词的生成过程不变,两者最主要的区别在 于,CS⁃SBM 在 URL 生成的时候要考虑查询词的影 响,对于 session 中每一个查询项 q,首先生成点击事 件的二项分布,如果 URL 被点击了,则从参数为 Ωqz 的 URL 多项分布中采样生成 URL u。 图 2 CS⁃SBM 网络搜索分析主题模型 Fig.2 CS⁃SBM web search analysis topic model 模型的完全似然函数为 P(w,u,z α,β,δ) = P(u z,w,δ)P(w z,β)P(z α) 在 CS⁃SBM 中, 同 样 采 用 了 与 LDA 类 似 的 Gibbs 采样方法。 P(z| α)和 P(w z,β)都与 SBM 中 的相同。 两者主要的区别就是给定的主题中的 w 和 u 不再相互独立。 u 的生成过程可能受到主题 z 和相关搜索查询 q 的影响。 P(u | z,w,δ) = ∫∏ D d = 1 ∏ Nd i = 1 P(udi | Δqdi zdi )∏ Q q = 1 ∏ K z = 1 p(Δqz | δ)dΔ = ∫∏ K z = 1 ∏ Q q = 1 ∏ U u = 1 Δ nqzu qzu ∏ Q q = 1 ∏ K z = 1 ( Γ(∑ U u = 1 δqu ) ∏ U u = 1 Γ(δqu ) ∏ U u = 1 Δ δqu -1 qzu )dΔ = ∏ Q q = 1 ( Γ(∑ U u = 1 δqu ) K ∏ U u = 1 Γ(δqu ) ) × ∏ K z = 1 ∏ Q q = 1 ∏ U u = 1 Γ(nqzu + δqu ) Γ(∑ U u = 1 (nqzu + δqu )) 式中,nqzu是第 z 个主题的第 q 个查询中的 URL u 的 数量。 当 session 中没有 URL 被点击时的条件概率为 P(zi = k Xi = 0,z -i,w,u,α,β,δ,Ψ) ∝ C DK dk + αk ∑ K k′ = 1 (C DK dk′ + αk ′) · Γ(∑ W t = 1 (C KWD kwd + βwk)) Γ(∑ W t = 1 (C KWD kwd + βwk + Niw )) · ∏ W w = 1 Γ(C KWD kwd + βwk + Niw ) Γ(C KWD kwd + βw ) 当 session 中有 URL 被点击时的条件概率为 P(zi = k | Xi = 1,z -i,w,t,u,α,β,δ,Ψ) ∝ C DK dk + αk ∑ K k′ = 1 (C DK dk′ + αk ′) · Γ(∑ W t = 1 (C KWD kwd + βwk)) Γ(∑ W t = 1 (C KWD kwd + βwk + Niw )) · ∏ W w = 1 Γ(C KWD kwd + βwk + Niw) Γ(C KWD kwd + βw) ∏q∈s i Γ(∑ U u = 1 (C QZU qzu + δqu)) Γ(∑ U u = 1 (C QZU qzu + δqu + Niu)) · ∏u←q Γ(C QZU qzu + δqu + Niu ) Γ(C QZU qzu + δu ) 式中: C QZU qzu 表示在一个 session 里查询项 q 中的 URL u被分配主题为 z 的次数;Niw表示 session i 中 URL 的数量。 2.3 主题在时间上的突发性 网络搜索中另一个常见现象就是时间上的突 发性。 一个用户更倾向于在一个很短的时间内集 中查询一些内容。 因此,本文假设每一个用户的查 询轨迹都有一个时间上的突发性,这种突发性由与 查询相关的时间戳来体现。 因为时间粒度是很难 设定的,所以本文采用 TOT 中提出的方法,使用连 续的 Beta 分布来捕获主题时间上的突发性。 通过 引入 Beta 分布,使一个主题能够更容易在一个短的 时间周期内出现。 在这种情况下,本文从整个语料 库级别(定义为 X-TG)和基于单一用户级别(定义 为 X - TU) 出发,刻画一个主题在时间上的变化 趋势。 因为主题-周期的多项分布是固定的(对每一 个用户而言),所以主题中存在的时间周期将会证 明突发性。 每天或者每小时都可以观察到突发性 现象,这表明去离散化是更合适的。 下面是 SBM 和 CS⁃SBM 在添加了时间信息以 后的模型算法。 the same as the original model for each session s in d do choose a topic z:Multinomial(θd ); 第 5 期 张森,等:基于用户查询日志的网络搜索主题分析 ·671·
·672 智能系统学报 第12卷 generate timestamps t~Beta(T:)(X-TG)or t:Beta(T)(X-TU) I(CK+B.+N.) the same as the original model 宫(+R+》 I(CKMP+B.) end for 它主要的变化在于,对文档中的每一个session, T(∑(c+6) 从参数为日,的多项分布中采样一个主题z,然后根 Π w=I Π I(coc +5+N) 据数据集的不同,从Beta分布Beta(T,)和Beta(Ta) T(∑(C%+6+N.) T(c+6) 分别生成基于全局的时间戳和基于特定用户的时 时间的参数按照如下方法更新: 间戳。 TS-SBM的Gibbs采样与LDA方法类似。本文 w元a1- -1] SLA 给出了一些简单的推导。首先,模型的完全似然函 数为 7a=a-1-)-1 P(w,u,t,zla,B,δ,r)=P(tlz,r)P(ulz,8) 式中,和s表示每一个文档中主题z时间上的样 P(wlz,B)P(zla) 本均值和样本偏方差。 如果session中没有URL被点击,那么此时的条件 概率是: 3 参数估计 P(z=kI X:=0,z-i,w,u,a,B,6,T)c 关于超参数a和B设置问题,一些LDA应用采 (1-t))'atae 用默认相同值的方法获得了成功,例如由Griffiths B(T1,T2) 和Steyers提出的a=50/k,B=0.01,K是主题的数 量。因此,在LDA中没有必要去研究超参数。然 () 而,在本文提出的模型中,超参数的设置是至关重 f=1 I(Cko?+B+N) 要的。因为LDA中的p和2值,也被包括在SBM (∑(C+Bk+N.) I(CKu+B.) 和CS-SBM的B和8中。 式中:T1和T2是Beta分布的超参数。 SBM完全似然P(w,u,zIa,B,8)的计算如下 对于SBM模型,如果session中有URL被点击, 所示: 此时的条件概率为 P(w,u,z1,B,8)= T P(a:=k|X=1,2i,w,u,a,B,8)c ΠT(m+a4) k=1 k= (1-专)a1ta C+ B(T1,T2) 县(c+) ΠT(a) ( (m+a)) k= k=1 T(立(c"+B) r(Ba) IIr(n+B.) I(Chm+B+N) r宫R I(C +B.) ΠT(B) (nid +B)) r2(c-+ia》 T(∑6) ΠT(nd+δk) =1 u=1 T(C+δk+N) T(∑(c+64+N) (CkuP+8) IIr(8.) 空u+i》 联三1 CS-SBM完全似然P(w,u,zla,B,δ)的计算如 对于CS-SBM模型,当session中有URL被点击时的 下所示: 条件概率为 P(w,u,z1a,B,8)= P(z=kI X:=1,z-i,w,t,u,a,B,6,) (1-)at52- CK+ T(m+a) k=1 B(T,T2) + r) (m+a))
generate timestamps t~ Beta(τz)(X-TG) or t:Beta(τzd ) (X-TU); the same as the original model end for 它主要的变化在于,对文档中的每一个 session, 从参数为 θd 的多项分布中采样一个主题 z,然后根 据数据集的不同,从 Beta 分布 Beta(τz)和 Beta(τzd ) 分别生成基于全局的时间戳和基于特定用户的时 间戳。 TS⁃SBM 的 Gibbs 采样与 LDA 方法类似。 本文 给出了一些简单的推导。 首先,模型的完全似然函 数为 P(w,u,t,z| α,β,δ,τ)= P(t |z,τ)P(u |z,δ)· P(w|z,β)P(z| α) 如果 session 中没有 URL 被点击,那么此时的条件 概率是: P(zi = k | Xi = 0,z -i,w,u,α,β,δ,τ) ∝ ∏ T j = 1 (1 - t j) τ dk1 -1 t τ dk2 -1 j B(τdk1 ,τdk2 ) C DK dk + αk ∑ K k′ = 1 (C DK dk′ + αk′) · Γ(∑ W t = 1 (C KWD kwd + βwk)) Γ(∑ W t = 1 (C KWD kwd + βwk + Niw)) ∏ W w = 1 Γ(C KWD kwd + βwk + Niw) Γ(C KWD kwd + βw) 式中:τdk1和 τdk2是 Beta 分布的超参数。 对于 SBM 模型,如果 session 中有 URL 被点击, 此时的条件概率为 P(zi = k | Xi = 1,z -i,w,u,α,β,δ) ∝ ∏ T j = 1 (1 - t j) τ dk1 -1 t τ dk2 -1 j B(τdk1 ,τdk2 ) C DK dk + αk ∑ K k′ = 1 (C DK dk′ + αk′) · Γ(∑ W w = 1 (C KWD kwd + βwk)) Γ(∑ W w = 1 (C KW kw + βw + Niw )) ∏ W w = 1 Γ(C KWD kwd + βwk + Niw ) Γ(C KWD kwd + βwk) · Γ(∑ U u = 1 (C KUD kud + δuk)) Γ(∑ U u = 1 (C KUD kud + δuk + Niu )) ∏ U u = 1 Γ(C KUD kud + δuk + Niu ) Γ(C KUD kud + δuk) 对于 CS⁃SBM 模型,当 session 中有 URL 被点击时的 条件概率为 P(zi = k | Xi = 1,z -i,w,t,u,α,β,δ,Ψ) ∝ ∏ T j = 1 (1 - t j) τ dk1 -1 t τ dk2 -1 j B(τdk1 ,τdk2 ) C DK dk + αk ∑ K k′ = 1 (C DK dk′ + αk′) · Γ(∑ W t = 1 (C KWD kwd + βwk)) Γ(∑ W t = 1 (C KWD kwd + βwk + Niw)) ∏ W w = 1 Γ(C KWD kwd + βwk + Niw) Γ(C KWD kwd + βw) · ∏q∈s i Γ(∑ U u = 1 (C QZU qzu + δqu )) Γ(∑ U u = 1 (C QZU qzu + δqu + Niu )) ∏u←q Γ(C QZU qzu + δqu + Niu ) Γ(C QZU qzu + δu ) 时间的参数按照如下方法更新: τkd1 = t kd [ t kd (1 - t kd ) s 2 kd - 1] τkd2 = (1 - t kd )[ t kd (1 - t kd ) s 2 kd - 1] 式中,t kd和 s 2 kd表示每一个文档中主题 z 时间上的样 本均值和样本偏方差。 3 参数估计 关于超参数 α 和 β 设置问题,一些 LDA 应用采 用默认相同值的方法获得了成功,例如由 Griffiths 和 Steyers [17]提出的 α= 50 / k,β = 0.01,K 是主题的数 量。 因此,在 LDA 中没有必要去研究超参数。 然 而,在本文提出的模型中,超参数的设置是至关重 要的。 因为 LDA 中的 φ 和 Ω 值,也被包括在 SBM 和 CS⁃SBM 的 β 和 δ 中。 SBM 完全似然 P(w,u,z | α,β,δ) 的计算如下 所示: P(w,u,z | α,β,δ) = ∏d ( Γ(∑ K k = 1 αk) ∏ K k = 1 Γ(αk) ) ∏ T k = 1 Γ(mdk + αk) Γ(∑ K k = 1 (mdk + αk)) · ∏d,k (( Γ(∑ W w = 1 βwk) ∏ W w = 1 Γ(βwk) ) ∏ W w = 1 Γ(nkwd + βwk) Γ(∑ W w = 1 (nkwd + βwk)) )· ( Γ(∑ U u = 1 δuk) ∏ U u = 1 Γ(δuk) ) ∏ U u = 1 Γ(nkud + δuk) Γ(∑ U u = 1 (nkud + δuk)) ) CS⁃SBM 完全似然 P(w,u,z | α,β,δ)的计算如 下所示: P(w,u,z | α,β,δ) = ∏d ( Γ(∑ K k = 1 αk) ∏ K k = 1 Γ(αk) ) ∏ T k = 1 Γ(mdk + αk) Γ(∑ K k = 1 (mdk + αk)) · ·672· 智 能 系 统 学 报 第 12 卷
第5期 张森,等:基于用户查询日志的网络搜索主题分析 ·673· ira+R) 对于SBM: M- ak'=∑(lnT(na+d陆)-lnr(δu)+ .k. IIr(B.) (nid +B)) ∑hr(∑)-hr(Σw+i.:) ΠT(nh+δn) 对于CS-SBM: u= i,'=∑(lnT(nh+in)-ln「(δ))+ g,k ΠT(δ) Σar(Σa.)-lhr(Σ+.) SBM-T完全似然P(w,u,za,B,8)的计算如下 上面的每一个公式无论a'B.k'还是6.k'、8., 所示: 都定义了一个向量。本文采用文献[18]中提出的 P(w,u,zla,B,6)= 有限空间的BFGS方法使它最大化。运行Gibbs采 ΠT(m4+a4) 样,然后选择B和6使P(w,u,za,B,δ,r)完全 k= 似然最大化,直到达到稳定状态。重复上述过程, Πr(a) (ma +ag)) 直到aB和6收敛。 =1 T(∑B) 4实验结果分析 ΠT(n+Bt) 三 4.1数据集 本文选择的实验数据是搜狗搜索发布的匿名 查询日志。它是搜狗在网上公开发布的用户查询 日志。该日志包括了用户2008年6月整月的网络 Ip(ta:I Ta.) 查询记录。日志主要包括5部分,即用户匿名D Ir(.) 查询词、查询时间、点击的URL的排名、点击的 CS-SBM-T完全似然P(w,u,za,B,8,T)的计 URL。这些数据是按照匿名用户的D顺序依次排 算如下所示: 列的。本文选取了在一个月内查询日志条目大于 500条的用户进行建模。首先,将同一用户的搜索 P(w,u,zla,B,8,r)= 查询日志放到一个文档中。然后,用文献[16]提出 ( ΠT(m+a) 的方法将搜索查询日志切分成了647164个session, k= 用于下一步搜索主题的发现。接下来,根据文献 Πr(a) [16]提出的停用词列表过滤掉那些没有意义的查 r(∑BA) 询词。同时,例如www.sougou.com、www.baid.com iT(na+Bt) 等主要的搜索引擎和门户网站也要过滤掉),因为 n=1 =1 它们没有提供有用信息。每一个文档的时间戳是 ΠT(B) (nd +B)) 由搜索日志上提供的查询时间决定的,并且根据文 r+- 献[20]提出的SSTM模型中用到的方法,将时间按 照先后顺序归一化到(0,1)。实验数据中,每一个 W= 文档都包括了一些session,每一个session都包括一 1r(6) 些查询词、URL(如果有点击事件)和时间戳。 I(a) 本文选用了两个衡量标准。第1个衡量标准是 用部分Held-Out数据评估模型预测未知数据的能 进行对数似然转换: 力。第2个衡量标准,本文参照了文献[21]提出的 a.((a)-In(a)) 方法,即在观察部分用户搜索记录以后,预测剩余 ∑(nr(∑a)-lnr(∑mu+a) 查询项的能力。两个衡量标准都选择了困惑度作 为评估模型泛化能力的衡量指标。一般而言,模型 B'=Σfnu+B)-nr(B.)+ 的困惑度越低,表明泛化能力越强,对模型的拟合 Σ(nf(∑Ba)-lhr(∑nw+B) 程度越高。由于很少有概率模型做有关获取网络 搜索查询突发性和时间上的主题突发性研究,很难
∏d,k (( Γ(∑ W w = 1 βwk) ∏ W w = 1 Γ(βwk) ) ∏ W w = 1 Γ(nkwd + βwk) Γ(∑ W w = 1 (nkwd + βwk)) )· ∏ K k = 1 ∏ Q q = 1h (( Γ(∑ U u = 1 δqu ) ∏ U u = 1 Γ(δqu ) ) ∏ U u = 1 Γ(nqku + δqu ) Γ(∑ U u = 1 (nqku + δqu )) ) SBM⁃T 完全似然 P(w,u,z α,β,δ)的计算如下 所示: P(w,u,z α,β,δ) = ∏d ( Γ(∑ K k = 1 αk) ∏ K k = 1 Γ(αk) ) ∏ T k = 1 Γ(mdk + αk) Γ(∑ K k = 1 (mdk + αk)) · ∏d,k ( Γ(∑ W w = 1 βwk) ∏ W w = 1 Γ(βwk) ) ∏ W w = 1 Γ(nkwd + βwk) Γ(∑ W w = 1 (nkwd + βwk)) · æ è ç ç ç ( Γ(∑ U u = 1 δuk) ∏ U u = 1 Γ(δuk) ) ∏ U u = 1 Γ(nkud + δuk) Γ(∑ U u = 1 (nkud + δuk)) ö ø ÷ ÷ ÷ ∏d,s,i p(t dsi | τdks ) CS⁃SBM⁃T 完全似然 P(w,u,z α,β,δ,τ) 的计 算如下所示: P(w,u,z α,β,δ,τ) = ∏d ( Γ(∑ K k = 1 αk) ∏ K k = 1 Γ(αk) ) ∏ T k = 1 Γ(mdk + αk) Γ(∑ K k = 1 (mdk + αk)) · ∏d,k (( Γ(∑ W w = 1 βwk) ∏ W w = 1 Γ(βwk) ) ∏ W w = 1 Γ(nkwd + βwk) Γ(∑ W w = 1 (nkwd + βwk)) )· ∏ K z = 1 ∏ Q q = 1 (( Γ(∑ U u = 1 δqu ) ∏ U u = 1 Γ(δqu ) ) ∏ U u = 1 Γ(nqku + δqu ) Γ(∑ U u = 1 (nqku + δqu )) )· ∏d,s,i p(t dsi | τdks ) 进行对数似然转换: α.′ = ∑d,k (lnΓ(n. kd + αk) - lnΓ(αk)) + ∑d (lnΓ(∑k αk) - lnΓ(∑k n. kd + αk)) β. k ′ = ∑d,k,w (lnΓ(nwkd + βwk) - lnΓ(βwk)) + ∑d,k (lnΓ(∑w βwk) - lnΓ(∑w nwkd + βwk)) 对于 SBM: δ. k ′ = ∑d,k,u (lnΓ(nukd + δuk) - lnΓ(δuk)) + ∑d,k (lnΓ(∑u δuk) - lnΓ(∑u nukd + δuk)) 对于 CS⁃SBM: δ. q ′ = ∑q,k,u (ln Γ(nqku + δqu ) - lnΓ(δqu )) + ∑q,k (lnΓ(∑u δqu ) - lnΓ(∑u nqku + δqu )) 上面的每一个公式无论 α.′、β. k ′还是 δ. k ′、δ. q ′ 都定义了一个向量。 本文采用文献[18] 中提出的 有限空间的 BFGS 方法使它最大化。 运行 Gibbs 采 样,然后选择 α、β 和 δ 使 P(w,u,z| α,β,δ,τ)完全 似然最大化,直到达到稳定状态。 重复上述过程, 直到 α、β 和 δ 收敛。 4 实验结果分析 4.1 数据集 本文选择的实验数据是搜狗搜索发布的匿名 查询日志。 它是搜狗在网上公开发布的用户查询 日志。 该日志包括了用户 2008 年 6 月整月的网络 查询记录。 日志主要包括 5 部分,即用户匿名 ID、 查询词、 查询时间、 点击的 URL 的排名、 点击的 URL。 这些数据是按照匿名用户的 ID 顺序依次排 列的。 本文选取了在一个月内查询日志条目大于 500 条的用户进行建模。 首先,将同一用户的搜索 查询日志放到一个文档中。 然后,用文献[16]提出 的方法将搜索查询日志切分成了647 164个 session, 用于下一步搜索主题的发现。 接下来,根据文献 [16]提出的停用词列表过滤掉那些没有意义的查 询词。 同时,例如 www.sougou. com、www. baidu. com 等主要的搜索引擎和门户网站也要过滤掉[19] ,因为 它们没有提供有用信息。 每一个文档的时间戳是 由搜索日志上提供的查询时间决定的,并且根据文 献[20]提出的 SSTM 模型中用到的方法,将时间按 照先后顺序归一化到(0,1)。 实验数据中,每一个 文档都包括了一些 session,每一个 session 都包括一 些查询词、URL(如果有点击事件)和时间戳。 本文选用了两个衡量标准。 第 1 个衡量标准是 用部分 Held⁃Out 数据评估模型预测未知数据的能 力。 第 2 个衡量标准,本文参照了文献[21]提出的 方法,即在观察部分用户搜索记录以后,预测剩余 查询项的能力。 两个衡量标准都选择了困惑度作 为评估模型泛化能力的衡量指标。 一般而言,模型 的困惑度越低,表明泛化能力越强,对模型的拟合 程度越高。 由于很少有概率模型做有关获取网络 搜索查询突发性和时间上的主题突发性研究,很难 第 5 期 张森,等:基于用户查询日志的网络搜索主题分析 ·673·
674 智能系统学报 第12卷 找到提出模型的直接竞争对手。所以本文选取了3 671.09、561.26。本文中提出的模型再次取得了显 个常用的主题模型作为比较基线,即LDA、DCMLDA 著的优势,其中SBM的困惑度是206.76,而CS-SBM 和T0T。 达到了204.87。实验结果表明,SBM和CS-SBM有 4.2模型困惑度分析 着更好的预测剩余查询项的能力。 对于第一个衡量标准,困惑度义如下: 1.6×10 LDA 1.4 Perplexity)(()) ++DCMLDA 1.2 +TOT d=1i=1 SBM 式中,M是模型通过训练过程学习到的,N,是指第 1.0 -·CS-SBM d个文档中词汇数量。图3展示了困惑度的比较结 果,从中可以发现这两个提出的模型与3个基线模 0.4 型相比表现出了更好的预测未知数据的能力。因 0.2 此,把搜索主题数设置为1O00时,SBM、CS-SBM、 t.... LDA、DCMLDA、TOT的困惑度分别为430.347 20 406080100 训练数据占总数据的百分比/% 400.16、1080.41、995.76、830.23。SBM和CS-SBM 自身的困惑度低,并且随着主题数增加困惑度还会 图4 Observed数据的困惑度 进一步降低。实验结果表明,SBM和CS-SBM更适 Fig.4 Perplexity of observed data 合于从给予的用户搜索历史中预测用户未来网络 4.3搜索主题发现及分析 搜索查询。 发现搜索主题的合理性是判断模型是否成功 ×10 的一个重要指标。本文中的实验结果证明了提出 3.0 →LDA 的模型在发现搜索主题方面表现突出,同时还准确 2.5 ◆◆DCMLDA ..TOT 地预测了查询主题在时间上的演化趋势。 20 -SBM 实验中设置主题的数目为K=50。搜索主题是 CS-SBM ☒1. 从Gibbs采样的1O00次迭代中单次采样提取的。 1.0 在表1~4中,展示了4个由SBM和CS-SBM分别 在语料库级上和单个用户级上发现的搜索主题,并 0.5 列出了各主题概率值最大的前5个词汇及其概率。 0 2004006008001000 主题名称是根据该主题下词汇具体的语义信息定 检索的主题个数/个 义的。图5~8中,直方图显示了主题在时间轴上的 图3Held-out数据的困惑度 概率分布,光滑曲线为拟合Beta分布的概率密度函 Fig.3 Perplexity of held-out data 数曲线。下面将选取图中的两个搜索主题进行具 第2种衡量标准的困惑度为 体分析。 Perplexity(M)= 表1~2中的第一个主题是“地震”,通过图5~6 可以发现,本文提出的SBM模型在语料库级上和单 三(w (II II p(,IM.w.)) 个用户级上都成功获取了主题时间上的突发性。 d=li=P+I 根据其时间分布来看,由于刚刚发生过汶川地震, 第2种衡量标准可以评估提出的模型在观察一 因此在6月份的前半个月,人们对地震的搜索比较 部分用户搜索历史记录以后,预测剩余查询项的能 频繁,但随着时间的推移,搜索数量逐渐减少。从 力。例如,从用户的查询日志中得到已经观察的查 语料库级的分析结果看,“汶川、地震、救灾”等高频 询词心1,P,那么剩余查询项的预测分布为 词汇都与地震相关。对于单个用户,本文从实验结 P(wW:P)。测试数据的困惑度是根据上面的困惑 果中选择了一位有大量查询日志并且有地震主题 度公式进行计算。举例来说,选择数据集中前80% 的用户做具体分析描述。结果发现,在这个主题下 的搜索查询词作为观察训练数据,剩余的20%作为 的词,例如地震、汶川、唐山、四川等词汇出现的概 测试数据。图4呈现了部分观察数据的预测困惑 率较高。总体来看,汶川地震引起了人们广泛的关 度,LDA、DCMLDA、TOT的困惑度分别是684.83、 注,对于全局来说,用户更关注地震救援工作:对于
找到提出模型的直接竞争对手。 所以本文选取了 3 个常用的主题模型作为比较基线,即 LDA、DCMLDA 和 TOT。 4.2 模型困惑度分析 对于第一个衡量标准,困惑度义如下: Perplexityheld-out(M) = (∏ D d = 1 ∏ Nd i = 1 p(wi M)) -1 ∑ D d = 1 (Nd ) 式中,M 是模型通过训练过程学习到的,Nd 是指第 d 个文档中词汇数量。 图 3 展示了困惑度的比较结 果,从中可以发现这两个提出的模型与 3 个基线模 型相比表现出了更好的预测未知数据的能力。 因 此,把搜索主题数设置为 1 000 时,SBM、CS⁃SBM、 LDA、 DCMLDA、 TOT 的 困 惑 度 分 别 为 430. 347、 400.16、1 080. 41、995. 76、830. 23。 SBM 和 CS⁃SBM 自身的困惑度低,并且随着主题数增加困惑度还会 进一步降低。 实验结果表明,SBM 和 CS⁃SBM 更适 合于从给予的用户搜索历史中预测用户未来网络 搜索查询。 图 3 Held⁃out 数据的困惑度 Fig.3 Perplexity of held⁃out data 第 2 种衡量标准的困惑度为 Perplexityportion(M) = (∏ D d = 1 ∏ Nd i = P+1 p(wi M,Wa:P )) -1 ∑ D d = 1 (Nd ) 第 2 种衡量标准可以评估提出的模型在观察一 部分用户搜索历史记录以后,预测剩余查询项的能 力。 例如,从用户的查询日志中得到已经观察的查 询 词 w1:P , 那 么 剩 余 查 询 项 的 预 测 分 布 为 P w | W1:P ( ) 。 测试数据的困惑度是根据上面的困惑 度公式进行计算。 举例来说,选择数据集中前 80% 的搜索查询词作为观察训练数据,剩余的 20%作为 测试数据。 图 4 呈现了部分观察数据的预测困惑 度,LDA、DCMLDA、TOT 的困惑度分别是 684. 83、 671.09、561.26。 本文中提出的模型再次取得了显 著的优势,其中 SBM 的困惑度是 206.76,而 CS⁃SBM 达到了 204.87。 实验结果表明,SBM 和 CS⁃SBM 有 着更好的预测剩余查询项的能力。 图 4 Observed 数据的困惑度 Fig.4 Perplexity of observed data 4.3 搜索主题发现及分析 发现搜索主题的合理性是判断模型是否成功 的一个重要指标。 本文中的实验结果证明了提出 的模型在发现搜索主题方面表现突出,同时还准确 地预测了查询主题在时间上的演化趋势。 实验中设置主题的数目为 K = 50。 搜索主题是 从 Gibbs 采样的 1000 次迭代中单次采样提取的。 在表 1 ~ 4 中,展示了 4 个由 SBM 和 CS-SBM 分别 在语料库级上和单个用户级上发现的搜索主题,并 列出了各主题概率值最大的前 5 个词汇及其概率。 主题名称是根据该主题下词汇具体的语义信息定 义的。 图 5~8 中,直方图显示了主题在时间轴上的 概率分布,光滑曲线为拟合 Beta 分布的概率密度函 数曲线。 下面将选取图中的两个搜索主题进行具 体分析。 表 1~2 中的第一个主题是“地震”,通过图 5~6 可以发现,本文提出的 SBM 模型在语料库级上和单 个用户级上都成功获取了主题时间上的突发性。 根据其时间分布来看,由于刚刚发生过汶川地震, 因此在 6 月份的前半个月,人们对地震的搜索比较 频繁,但随着时间的推移,搜索数量逐渐减少。 从 语料库级的分析结果看,“汶川、地震、救灾”等高频 词汇都与地震相关。 对于单个用户,本文从实验结 果中选择了一位有大量查询日志并且有地震主题 的用户做具体分析描述。 结果发现,在这个主题下 的词,例如地震、汶川、唐山、四川等词汇出现的概 率较高。 总体来看,汶川地震引起了人们广泛的关 注,对于全局来说,用户更关注地震救援工作;对于 ·674· 智 能 系 统 学 报 第 12 卷
第5期 张森,等:基于用户查询日志的网络搜索主题分析 ·675. 表2中的个人用户来说,他们只是关注地震本身,而 250 没有救援相关的查询。 200 200 表3~4中,最后一个主题是“欧洲杯”,图7一8 100 100 中,CS-SBM的实验结果显示关于“欧洲杯”这个话 50 题的查询从第十天到第三十天越来越多,这也符合 0 1015202530 51015202530 随着欧洲杯的进行人们关注的热情越来越高的现 时间/天 时间/天 象。从整个语料库得到的结果来看,搜索主题“欧 (a)主题“电子产品”随着 (b)主题“欧洲杯”随着 洲杯”主要包括欧洲杯、瑞士、奥地利等词。其中 时间的变化趋势 时间的变化趋势 “瑞士”和“奥地利”是本届欧洲杯的举办地,这些词 图8 CS-SBM-TU发现的搜索主题在时间上的演化趋势 汇都与欧洲杯的主题紧密相关。而对于表4中的个 Fig.8 Latent evolutions of CS-SBM-TU discovered search topics 人用户,我们仍然从实验结果中选取了与“欧洲杯” 主题相关的用户进行分析说明。它包括欧洲杯、西 表1SBM-TG发现的搜索主题分布情况 班牙、冠军等关键词,这证明了该用户更关注于欧 Table 1 SBM-TG discovered search topics distribution 洲杯的冠军归属问题。 主题1 主题2 总体而言,发现的搜索主题与实际的情况大体 地震 NBA 相吻合,而且能较好地反应主题变化的趋势。 搜索词 概率 搜索词 概率 ×10 ×10 汶川 0.03628 NBA 0.03128 2.5 1.0 地震 0.03342 季后赛 0.02883 2.0 0.5 救灾 0.03217 西部 0.02832 1.0 05 武警 0.02774 湖人 0.02336 0 51015202530 51015202530 哄抢 0.02774 冠军 0.02092 时间/天 时间/天 (a)主题“地震”随着时间 (b)主题“NBA”随着时间 表2 SBM-TU发现的搜索主题分布情况 的变化趋势 的变化趋势 Table 2 SBM-TU discovered search topics distribution 图5CS-SBM网络搜索分析主题模型 主题1 主题2 Fig.5 Iatent evolutions of SBM-TG discovered search tonics 地震 NBA 750r 600 ← 600 500 搜索词 概率 搜索词 概率 450 400 300 300 地震 0.04762 总决赛 0.04293 200 150 100 汶川 0.04358 NBA 0.03912 0 5 1015202530 51015202530 唐山 0.04302 湖人 0.03641 时间/天 时间/天 (a)主题“地震”随着时间 (b)主题“NBA”随着时间 四川 0.03275 凯尔特人 0.03379 的变化趋势 的变化趋势 地壳 0.03028 斯台普斯 0.02311 图6SBM-TU发现的搜索主题在时间上的演化趋势 表3 CS-SBM-TG发现的搜索主题分布情况 Fig.6 Iatent evolutions of SBM-TI discovered search tonics ×10 ×10 Table 3 CS-SBM-TG discovered search topics distribution 35 2.5 主题3 3.0 电子产品 2.0 1.5 主题4 欧洲杯 1.0 搜索词 概率 搜索词 概率 0.5 0 51015202530 51015202530 手机 0.05004 欧洲杯 0.03487 时间/天 时间/天 内存卡 0.04818 瑞士 0.02983 (a)主题“电子产品”随着 (b)主题“欧洲杯”随着 耳机 0.04557 奥地利 0.02649 时间的变化趋势 时间的变化趋势 图7CS-SBM-TG发现的搜索主题在时间上的演化趋势 笔记本 0.04365 足球 0.02537 Fig.7 Latent evolutions of CS-SBM-TG discovered MP3 0.03876 决赛 0.02430 search topics
表 2 中的个人用户来说,他们只是关注地震本身,而 没有救援相关的查询。 表 3~4 中,最后一个主题是“欧洲杯”,图 7 ~ 8 中,CS-SBM 的实验结果显示关于“欧洲杯”这个话 题的查询从第十天到第三十天越来越多,这也符合 随着欧洲杯的进行人们关注的热情越来越高的现 象。 从整个语料库得到的结果来看,搜索主题“欧 洲杯” 主要包括欧洲杯、瑞士、奥地利等词。 其中 “瑞士”和“奥地利”是本届欧洲杯的举办地,这些词 汇都与欧洲杯的主题紧密相关。 而对于表 4 中的个 人用户,我们仍然从实验结果中选取了与“欧洲杯” 主题相关的用户进行分析说明。 它包括欧洲杯、西 班牙、冠军等关键词,这证明了该用户更关注于欧 洲杯的冠军归属问题。 总体而言,发现的搜索主题与实际的情况大体 相吻合,而且能较好地反应主题变化的趋势。 (a)主题“地震”随着时间 (b)主题“NBA”随着时间 的变化趋势 的变化趋势 图 5 CS⁃SBM 网络搜索分析主题模型 Fig.5 Latent evolutions of SBM⁃TG discovered search topics (a)主题“地震”随着时间 (b)主题“NBA”随着时间 的变化趋势 的变化趋势 图 6 SBM⁃TU 发现的搜索主题在时间上的演化趋势 Fig.6 Latent evolutions of SBM⁃TU discovered search topics (a)主题“电子产品”随着 (b)主题“欧洲杯”随着 时间的变化趋势 时间的变化趋势 图 7 CS⁃SBM⁃TG 发现的搜索主题在时间上的演化趋势 Fig. 7 Latent evolutions of CS⁃SBM⁃TG discovered search topics (a)主题“电子产品”随着 (b)主题“欧洲杯”随着 时间的变化趋势 时间的变化趋势 图 8 CS⁃SBM⁃TU 发现的搜索主题在时间上的演化趋势 Fig. 8 Latent evolutions of CS⁃SBM⁃TU discovered search topics 表 1 SBM⁃TG 发现的搜索主题分布情况 Table 1 SBM⁃TG discovered search topics distribution 主题 1 地震 主题 2 NBA 搜索词 概率 搜索词 概率 汶川 0.036 28 NBA 0.031 28 地震 0.033 42 季后赛 0.028 83 救灾 0.032 17 西部 0.028 32 武警 0.027 74 湖人 0.023 36 哄抢 0.027 74 冠军 0.020 92 表 2 SBM⁃TU 发现的搜索主题分布情况 Table 2 SBM⁃TU discovered search topics distribution 主题 1 地震 主题 2 NBA 搜索词 概率 搜索词 概率 地震 0.047 62 总决赛 0.042 93 汶川 0.043 58 NBA 0.039 12 唐山 0.043 02 湖人 0.036 41 四川 0.032 75 凯尔特人 0.033 79 地壳 0.030 28 斯台普斯 0.023 11 表 3 CS⁃SBM⁃TG 发现的搜索主题分布情况 Table 3 CS⁃SBM⁃TG discovered search topics distribution 主题 3 主题 4 电子产品 欧洲杯 搜索词 概率 搜索词 概率 手机 0.050 04 欧洲杯 0.034 87 内存卡 0.048 18 瑞士 0.029 83 耳机 0.045 57 奥地利 0.026 49 笔记本 0.043 65 足球 0.025 37 MP3 0.038 76 决赛 0.024 30 第 5 期 张森,等:基于用户查询日志的网络搜索主题分析 ·675·
·676 智能系统学报 第12卷 表4CS-SBM-TG发现的搜索主题分布情况 118-126 Table 4 CS-SBM-TG discovered search topics distribution [5]GUO F,LIU C,WANG Y M.Efficient multiple-click 主题3 电子产品 models in web search[C]//Proceedings of the Second ACM International Conference on Web Search and Data Mining. 主题4 欧洲杯 Barcelona,Spain,2009:124-131. 搜索词 概率 搜索词 概率 [6]张宇,宋巍,刘挺,等.基于URL主题的查询分类方法 诺基亚 0.03882 欧洲杯 0.03203 [J】.计算机研究与发展,2012,49(6):1298-1305 手机 0.03912 ZHANG Yu,SONG Wei,LIU Ting,et al.Query 西班牙 0.03064 classification based on url topic[J].Journal of computer 内存 0.03641 德国 0.02991 research and development,2012,49(6):1298-1305. 相机 0.03379 冠军 0.02901 [7]MADSEN R E,KAUCHAK D,ELKAN C.Modeling word HTC 0.02311 瑞士 0.02506 burstiness using the dirichlet distribution[C]//Proceedings of the 22nd international conference on Machine iearning. 5 结束语 Bonn,Germany,2005:545-552. [8]BLEI D M,NG A Y,JORDAN M I.Latent dirichlet 本文提出了两个主题模型SBM和CS-SBM,从 allocation[J].Journal of machine learning research,2003, 全局和基于特定用户来建模网络搜索分析。SBM 3(1):993-1022. 主要是用于获取网络查询的突发现象。CS-SBM主 [9]WANG X,MCCALLUM A.Topics over time:a non-Markov 要添加了查询词和URL之间的关系,获取了主题突 continuous-time model of topical trends[Cl//Proceedings of 发性。为了使SBM和CS-SBM可以获取时间上的 the 12th ACM SIGKDD international conference on Knowledge discovery and data mining.Philadelphia,USA, 突发性,本文采用Beta分布拟合主题在时间上的变 2006:424-433. 化的策略。本文还设计了一系列的实验验证了提 「10]徐戈,王厚峰.自然语言处理中主题模型的发展[J] 出模型拥有较好的泛化能力、主题发现能力和反应 计算机学报,2011.34(8):1423-1436. 主题时间上突发性的能力。本文的贡献主要有三 XU Ge,WANG Houfeng.The development of topic model 个方面:第一,研究了搜索引擎用户行为分析中突 in natural language processing [J].Chinese journal of 发性现象:第二,提出了两种新型的模型用来捕获 computers,2011,34(8):1423-1436. 网络搜索中各个方面的突发性:第三,通过大量的 [11]张晨逸,孙建伶,丁轶群.基于MB-LDA模型的微博 实验验证了模型的有效性。下一步工作中,将把这 主题挖掘[J].计算机研究与发展,2011,48(10): 1795-1802 些模型运用到团购广告投放。通过发现用户的搜 ZHANG Chenyi,SUN Jianling,DING Yiqun.Topic 索主题,然后将同一主题下的用户按照社团发现的 mining for microblog based on mb-lda model[].Journal of 规则进行分类,并进行广告投放。 computer research and development,2011,48(10): 参考文献: 1795-1802. [12]刘少鹏,印鉴,欧阳佳,等.基于MB-HDP模型的微博 [1]SUNEHAG P.Using two-stage conditional word frequency 主题挖掘[J].计算机学报,2015,38(7):1408-1419. models to model word burstiness and motivating TF-IDF[J]. LIU Shaopeng,YIN Jian,OUYANG Jia,et al.Topic Journal of machine learning reasearch,2017,2:8. mining from microblogs based on MB-HDP model[J]. [2]ELKAN C.Clustering documents with an exponential-family Chinese Journal of Computers,2015,38(7):1408-1419. approximation of the Dirichlet compound multinomial 13 JIANG D,TONG Y,SONG Y.Cross-lingual topic distribution [C]//Proceedings of the 23rd International discovery from multilingual search engine query log[J]. Conference on Machine Learning,Pittsburgh.Pennsylvania, ACM transactions on information systems(TOIS),2016, USA,2006:289-296. 35(2):9. [3]DOYLE G,ELKAN C.Accounting for burstiness in topic [14]JIANG D,LEUNG K W T,NG W.Query intent mining models[C]//Proceedings of the 26th Annual International with multiple dimensions of web search data[J].World Conference on Machine Learning Montreal.QC,Canada, wide web,2016,19(3):475. 2009:281-288. [15]JIANG D,YANG L.Query intent inference via search [4]XUE G R,ZENG H J,CHEN Z,et al.Optimizing web engine log [J].Knowledge and information systems, search using web click-through data[C]//Proceedings of 2016.49(2):661-685. the thirteenth ACM international conference on Information [16]HUANG J,EFTHIMIADIS E N.Analyzing and evaluating and Knowledge Management.Washington,USA,2004: query reformulation strategies in web search logs [C]/
表 4 CS⁃SBM⁃TG 发现的搜索主题分布情况 Table 4 CS⁃SBM⁃TG discovered search topics distribution 主题 3 主题 4 电子产品 欧洲杯 搜索词 概率 搜索词 概率 诺基亚 0.038 82 欧洲杯 0.032 03 手机 0.039 12 西班牙 0.030 64 内存 0.036 41 德国 0.029 91 相机 0.033 79 冠军 0.029 01 HTC 0.023 11 瑞士 0.025 06 5 结束语 本文提出了两个主题模型 SBM 和 CS⁃SBM,从 全局和基于特定用户来建模网络搜索分析。 SBM 主要是用于获取网络查询的突发现象。 CS⁃SBM 主 要添加了查询词和 URL 之间的关系,获取了主题突 发性。 为了使 SBM 和 CS⁃SBM 可以获取时间上的 突发性,本文采用 Beta 分布拟合主题在时间上的变 化的策略。 本文还设计了一系列的实验验证了提 出模型拥有较好的泛化能力、主题发现能力和反应 主题时间上突发性的能力。 本文的贡献主要有三 个方面:第一,研究了搜索引擎用户行为分析中突 发性现象;第二,提出了两种新型的模型用来捕获 网络搜索中各个方面的突发性;第三,通过大量的 实验验证了模型的有效性。 下一步工作中,将把这 些模型运用到团购广告投放。 通过发现用户的搜 索主题,然后将同一主题下的用户按照社团发现的 规则进行分类,并进行广告投放。 参考文献: [1] SUNEHAG P. Using two⁃stage conditional word frequency models to model word burstiness and motivating TF⁃IDF[J]. Journal of machine learning reasearch, 2017, 2: 8. [2]ELKAN C. Clustering documents with an exponential⁃family approximation of the Dirichlet compound multinomial distribution [ C ] / / Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh. Pennsylvania, USA, 2006: 289-296. [3] DOYLE G, ELKAN C. Accounting for burstiness in topic models[C] / / Proceedings of the 26th Annual International Conference on Machine Learning Montreal. QC, Canada, 2009: 281-288. [4]XUE G R, ZENG H J, CHEN Z, et al. Optimizing web search using web click⁃through data [ C] / / Proceedings of the thirteenth ACM international conference on Information and Knowledge Management. Washington, USA, 2004: 118-126. [5] GUO F, LIU C, WANG Y M. Efficient multiple - click models in web search[C] / / Proceedings of the Second ACM International Conference on Web Search and Data Mining. Barcelona, Spain, 2009: 124-131. [6]张宇, 宋巍, 刘挺, 等. 基于 URL 主题的查询分类方法 [J]. 计算机研究与发展, 2012, 49(6): 1298-1305. ZHANG Yu, SONG Wei, LIU Ting, et al. Query classification based on url topic [ J]. Journal of computer research and development, 2012, 49(6): 1298-1305. [7]MADSEN R E, KAUCHAK D, ELKAN C. Modeling word burstiness using the dirichlet distribution[C] / / Proceedings of the 22nd international conference on Machine iearning. Bonn, Germany, 2005: 545-552. [8] BLEI D M, NG A Y, JORDAN M I. Latent dirichlet allocation[J]. Journal of machine learning research, 2003, 3(1): 993-1022. [9]WANG X, MCCALLUM A. Topics over time: a non⁃Markov continuous⁃time model of topical trends[C] / / Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. Philadelphia, USA, 2006: 424-433. [10]徐戈, 王厚峰. 自然语言处理中主题模型的发展[ J]. 计算机学报, 2011, 34(8): 1423-1436. XU Ge, WANG Houfeng. The development of topic model in natural language processing [ J ]. Chinese journal of computers, 2011, 34(8): 1423-1436. [11]张晨逸, 孙建伶, 丁轶群. 基于 MB-LDA 模型的微博 主题挖掘[ J]. 计算机研究与发展, 2011, 48 ( 10): 1795-1802. ZHANG Chenyi, SUN Jianling, DING Yiqun. Topic mining for microblog based on mb⁃lda model[J]. Journal of computer research and development, 2011, 48 ( 10 ): 1795-1802. [12]刘少鹏, 印鉴, 欧阳佳, 等. 基于 MB⁃HDP 模型的微博 主题挖掘[J]. 计算机学报, 2015, 38(7): 1408-1419. LIU Shaopeng, YIN Jian, OUYANG Jia, et al. Topic mining from microblogs based on MB - HDP model [ J]. Chinese Journal of Computers, 2015, 38(7): 1408-1419. [ 13 ] JIANG D, TONG Y, SONG Y. Cross⁃lingual topic discovery from multilingual search engine query log[ J]. ACM transactions on information systems (TOIS), 2016, 35(2): 9. [14] JIANG D, LEUNG K W T, NG W. Query intent mining with multiple dimensions of web search data[ J]. World wide web, 2016, 19(3): 475. [15] JIANG D, YANG L. Query intent inference via search engine log [ J ]. Knowledge and information systems, 2016, 49(2): 661-685. [16]HUANG J, EFTHIMIADIS E N. Analyzing and evaluating query reformulation strategies in web search logs [ C] / / ·676· 智 能 系 统 学 报 第 12 卷
第5期 张森,等:基于用户查询日志的网络搜索主题分析 .677. Proceedings of the 18th ACM Conference on Information 作者简介: and Knowledge Management.Hong Kong,China,2009: 张森,男,1992年生,硕士研究生, 77-86. 主要研究方向为信息检索、自然语言 [17]GRIFFITHS T L,STEYVERS M.Finding scientifie topics 处理。 []Proceedings of the national academy of sciences, 2004,101(1):5228-5235. [18]ZHU C.BYRD R H,LU P,et al.Algorithm 778:L- BFGS-B:Fortran subroutines for large-scale bound- constrained optimization [J].ACM transactions on 张晨,男,1988年生,副教授,博士, mathematical software TOMS),1997,23 (4): 主要研究方向为众包、数据分析与数据 550-560. 挖掘、机器学习。在TKD、VLDB、 [19 MANNING C D,RAGHAVAN P.SCHUTZE H. SIGMOD、ICDE等国内外重要期刊和顶 Introduction to information retrieval [M].Cambridge: 级学术会议上发表论文10余篇。 Cambridge University Press,2008:1-16. [20]JIANG D,NG W.Mining web search topics with diverse spatiotemporal patterns [C]//Proceedings of the 36th 林培光,男.1978年生,副教授,博 International ACM SIGIR Conference on Research and 士,主要研究方向为信息检索、海量数 Development in Information Retrieval.Dublin,Ireland, 据处理和集成。主持教育部课题2项、 2013:881-884 山东省自然科学基金项目1项,济南市 [21 LI W,MCCALLUM A.Pachinko allocation:DAG- 科技局自主创新计划1项和青年科技 structured mixture models of topic correlations [C]/ 明星计划1项,另外参与国家自然科学 Proceedings of the 23rd International Conference on 基金以及省部级课题多项。发表学术论文30余篇,被SCI Machine Learning.Pittsburgh,USA,2006:577-584. 检索3篇,E1检索30余篇
Proceedings of the 18th ACM Conference on Information and Knowledge Management. Hong Kong, China, 2009: 77-86. [17]GRIFFITHS T L, STEYVERS M. Finding scientific topics [J]. Proceedings of the national academy of sciences, 2004, 101(1): 5228-5235. [18] ZHU C, BYRD R H, LU P, et al. Algorithm 778: L⁃ BFGS⁃B: Fortran subroutines for large⁃scale bound⁃ constrained optimization [ J ]. ACM transactions on mathematical software ( TOMS ), 1997, 23 ( 4 ): 550-560. [ 19 ] MANNING C D, RAGHAVAN P, SCHÜTZE H. Introduction to information retrieval [ M]. Cambridge: Cambridge University Press, 2008: 1-16. [20] JIANG D, NG W. Mining web search topics with diverse spatiotemporal patterns [ C] / / Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval. Dublin, Ireland, 2013: 881-884. [ 21 ] LI W, MCCALLUM A. Pachinko allocation: DAG⁃ structured mixture models of topic correlations [ C] / / Proceedings of the 23rd International Conference on Machine Learning. Pittsburgh, USA, 2006: 577-584. 作者简介: 张森,男,1992 年生,硕士研究生, 主要研究方向为信息检索、自然语言 处理。 张晨,男,1988 年生,副教授,博士, 主要研究方向为众包、数据分析与数据 挖 掘、 机 器 学 习。 在 TKD、 VLDB、 SIGMOD、 ICDE 等国内外重要期刊和顶 级学术会议上发表论文 10 余篇。 林培光,男,1978 年生,副教授,博 士,主要研究方向为信息检索、海量数 据处理和集成。 主持教育部课题 2 项、 山东省自然科学基金项目 1 项、济南市 科技局自主创新计划 1 项和青年科技 明星计划 1 项,另外参与国家自然科学 基金以及省部级课题多项。 发表学术论文 30 余篇,被 SCI 检索 3 篇,EI 检索 30 余篇。 第 5 期 张森,等:基于用户查询日志的网络搜索主题分析 ·677·