第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 词是人类智慧的结晶，并在搜索查询和微博等网络
Ｕ ２ ） １７ 第 １２ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．５ ２０１７ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１７０６０９６ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７１０２１．１３４９．００４．ｈｔｍｌ 基于用户查询日志的网络搜索主题分析 张森１ ， 张晨１，２ ， 林培光１ ， 张春云１ ，郭玉超１ ， 任威龙１ ，任可２ （１．山东财经大学 计算机科学与技术学院，山东 济南 ２５００１４；２． 香港科技大学 计算机科学及工程学系，香港 ９９９０７７） 摘 要：网络搜索分析在优化搜索引擎方面具有举足轻重的作用，而且对用户个人搜索特性进行分析能够提高搜索 引擎的精准度。 目前，大多数已有模型（比如点击图模型及其变体），注重研究用户群体的共同特点。 然而，关于如 何做到既可以获取用户群体共同特点又可以获取用户个人特点方面的研究却非常少。 本文研究了基于个人用户网 络搜索分析新问题，即通过研究用户搜索的突发性现象，获取个人用户搜索查询的主题分布情况。 提出了两个搜索 主题模型，即搜索突发性模型（ＳＢＭ）和耦合敏感搜索突发性模型（ＣＳ－ＳＢＭ）。 ＳＢＭ 假设查询词和 ＵＲＬ 主题是无关 的，ＣＳ－ＳＢＭ 假设查询词和 ＵＲＬ 之间是有主题关联的，得到的主题分布信息存储在偏 Ｄｉｒｉｃｈｌｅｔ 先验中，采用 Ｂｅｔａ 分 布刻画用户搜索的时间特性。 实验结果表明，每一个用户的网络搜索轨迹都有多种基于用户的独有特点。 同时，在 使用大量真实用户查询日志数据情况下，与 ＬＤＡ、ＤＣＭＬＤＡ、ＴＯＴ 相比，本文提出的模型具有明显的泛化性能优势，并 且有效地描绘了用户搜索查询主题在时间上的变化过程。 关键词：网络搜索；搜索引擎；自然语言处理；主题模型；文本挖掘；突发性；时间分析；参数估计 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０５－０６６８－１０ 中文引用格式：张森， 张晨， 林培光，等．基于用户查询日志的网络搜索主题分析［Ｊ］． 智能系统学报， ２０１７， １２（５）： ６６８－６７７． 英文引用格式：ＺＨＡＮＧ Ｓｅｎ， ＺＨＡＮＧ Ｃｈｅｎ， ＬＩＮ Ｐｅｉｇｕａｎｇ， ｅｔ ａｌ． Ｗｅｂ ｓｅａｒｃｈ ｔｏｐｉｃ ａｎａｌｙｓｉｓ ｂａｓｅｄ ｏｎ ｕｓｅｒ ｓｅａｒｃｈ ｑｕｅｒｙ ｌｏｇｓ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（５）： ６６８－６７７． Ｗｅｂ ｓｅａｒｃｈ ｔｏｐｉｃ ａｎａｌｙｓｉｓ ｂａｓｅｄ ｏｎ ｕｓｅｒ ｓｅａｒｃｈ ｑｕｅｒｙ ｌｏｇｓ ＺＨＡＮＧ Ｓｅｎ １ ， ＺＨＡＮＧ Ｃｈｅｎ １，２ ， ＬＩＮ Ｐｅｉｇｕａｎｇ １ ， ＺＨＡＮＧ Ｃｈｕｎｙｕｎ １ ， ＧＵＯ Ｙｕｃｈａｏ １ ， ＲＥＮ Ｗｅｉｌｏｎｇ １ ， ＲＥＮ Ｋｅ ２ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ， Ｓｈａｎｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｆｉｎａｎｃｅ ＆ Ｅｃｏｎｏｍｉｃｓ， Ｊｉｎａｎ ２５００１４， Ｃｈｉｎａ； ２．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ＆ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｈｏｎｇ Ｋｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｈｏｎｇ Ｋｏｎｇ ９９９０７７， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｅｂ ｓｅａｒｃｈ ａｎａｌｙｓｉｓ ｐｌａｙｓ ａ ｃｒｉｔｉｃａｌ ｒｏｌｅ ｉｎ ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｃｏｎｔｅｍｐｏｒａｒｙ ｓｅａｒｃｈ ｅｎｇｉｎｅｓ． Ｉｎ ａｄｄｉｔｉｏｎ， ｓｅａｒｃｈ ｅｎｇｉｎｅ ａｃｃｕｒａｃｙ ｃａｎ ｂｅ ｉｍｐｒｏｖｅｄ ｂｙ ａｎａｌｙｚｉｎｇ ｔｈｅ ｉｎｄｉｖｉｄｕａｌ ｓｅａｒｃｈ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｕｓｅｒｓ． Ｍｏｓｔ ｅｘｉｓｔｉｎｇ ｍｏｄｅｌｓ， ｓｕｃｈ ａｓ ｔｈｅ ｃｌｉｃｋ ｇｒａｐｈ ａｎｄ ｉｔｓ ｖａｒｉａｎｔｓ， ｆｏｃｕｓ ｏｎ ｔｈｅ ｃｏｍｍｏｎ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｇｒｏｕｐ． Ｈｏｗｅｖｅｒ， ａｓ ｙｅｔ， ｔｈｅｒｅ ｈａｓ ｂｅｅｎ ｌｉｔｔｌｅ ｉｎｖｅｓｔｉｇａｔｉｏｎ ｏｆ ａ ｍｏｄｅｌ ｔｈａｔ ｗｏｕｌｄ ｏｂｔａｉｎ ｂｏｔｈ ｔｈｅ ｃｏｌｌｅｃｔｉｖｅ ｇｒｏｕｐ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ａｎｄ ｔｈｅ ｕｎｉｑｕｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｉｎｄｉｖｉｄｕａｌ ｕｓｅｒｓ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｉｎｖｅｓｔｉｇａｔｅ ｕｓｅｒ－ｓｐｅｃｉｆｉｃ ｗｅｂ ｓｅａｒｃｈ ａｎａｌｙｓｉｓ， ｗｈｅｒｅｂｙ ｗｅ ｏｂｔａｉｎ ｔｈｅ ｔｏｐｉｃ ｄｉｓｔｒｉｂｕｔｉｏｎｓ ｏｆ ｔｈｅ ｓｅａｒｃｈ ｑｕｅｒｉｅｓ ｏｆ ｉｎｄｉｖｉｄｕａｌ ｕｓｅｒｓ ｂｙ ｄｅｔｅｒｍｉｎｉｎｇ ｔｈｅ ｂｕｒｓｔｉｎｅｓｓ ｏｆ ｕｓｅｒ ｓｅａｒｃｈｅｓ． Ｗｅ ｐｒｏｐｏｓｅ ｔｗｏ ｔｏｐｉｃ ｍｏｄｅｌｓ， ｉ．ｅ．， ｔｈｅ ｓｅａｒｃｈ ｂｕｒｓｔｉｎｅｓｓ ｍｏｄｅｌ （ＳＢＭ） ａｎｄ ｔｈｅ ｃｏｕｐｌｉｎｇ⁃ｓｅｎｓｉｔｉｖｅ ｓｅａｒｃｈ ｂｕｒｓｔｉｎｅｓｓ ｍｏｄｅｌ （ＣＳ⁃ＳＢＭ）． Ｔｈｅ ＳＢＭ ａｄｏｐｔｓ ｔｈｅ ａｓｓｕｍｐｔｉｏｎ ｔｈａｔ ｔｈｅ ｑｕｅｒｙ ｗｏｒｄｓ ａｎｄ ＵＲＬ ａｒｅ ｔｏｐｉｃａｌｌｙ ｉｎｄｅｐｅｎｄｅｎｔ， Ｔｈｅ ＣＳ⁃ＳＢＭ ｓｕｐｐｏｓｅｓ ｔｈａｔ ｔｈｅ ｑｕｅｒｙ ｗｏｒｄｓ ａｎｄ ＵＲＬ ａｒｅ ｔｏｐｉｃａｌｌｙ ｒｅｌｅｖａｎｔ． Ｔｈｅ ｏｂｔａｉｎｅｄ ｔｏｐｉｃ ｄｉｓｔｒｉｂｕｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｉｓ ｓｔｏｒｅｄ ｉｎ ｓｋｅｗｅｄ Ｄｉｒｉｃｈｌｅｔ ｐｒｉｏｒｓ ａｎｄ ａ ｂｅｔａ ｄｉｓｔｒｉｂｕｔｉｏｎ ｉｓ ｕｓｅｄ ｔｏ ｃａｐｔｕｒｅ ｔｈｅ ｔｅｍｐｏｒａｌ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｔｈｅ ｕｓｅｒ ｓｅａｒｃｈｅｓ． Ｏｕｒ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｅａｃｈ ｕｓｅｒ’ ｓ ｗｅｂ ｓｅａｒｃｈ ｔｒａｉｌ ｈａｓ ｕｎｉｑｕｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ， ａｎｄ ｔｈａｔ ｉｎ ｔｈｅ ｃａｓｅ ｏｆ ｔｈｅｒｅ ｂｅｉｎｇ ａ ｌａｒｇｅ ａｍｏｕｎｔ ｏｆ ｒｅａｌ ｑｕｅｒｙ ｌｏｇ ｄａｔａ， ｉｎ ｃｏｍｐａｒｉｓｏｎ ｔｏ ｔｈｅ ｌａｔｅｎｔ Ｄｉｒｉｃｈｌｅｔ ａｌｌｏｃａｔｉｏｎ （ＬＤＡ） ａｎｄ ｔｏｐｉｃ ｏｖｅｒ ｔｉｍｅ （ ＴＯＴ） ｍｏｄｅｌｓ， ｏｕｒ ｐｒｏｐｏｓｅｄ ｍｏｄｅｌｓ ｈａｖｅ ａｄｖａｎｔａｇｅｓ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｇｅｎｅｒａｌｉｚｅｄ ｐｅｒｆｏｒｍａｎｃｅ ａｎｄ ｅｆｆｅｃｔｉｖｅｌｙ ｄｅｓｃｒｉｂｅｓ ｔｈｅ ｔｅｍｐｏｒａｌ ｃｈａｎｇｅ ｐｒｏｃｅｓｓ ｏｆ ｕｓｅｒ ｓｅａｒｃｈ ｑｕｅｒｉｅｓ． Ｋｅｙｗｏｒｄｓ：ｗｅｂ ｓｅａｒｃｈ； ｓｅａｒｃｈ ｅｎｇｉｎｅ； ｎａｔｕｒａｌ ｌａｎｇｕａｇｅ ｐｒｏｃｅｓｓｉｎｇ； ｔｏｐｉｃ ｍｏｄｅｌ； ｄａｔａ ｍｉｎｉｎｇ； ｂｕｒｓｔｉｎｅｓｓ； ｔｅｍｐｏｒａｌ ａｎａｌｙｓｉｓ； ｐａｒａｍｅｔｅｒ ｅｓｔｉｍａｔｅ 收稿日期：２０１７－０７－０１． 网络出版日期：２０ －１０－２１． 基金项目：国家自然科学基金重点项目（ １ ０１２５８ １９３１ 年，Ｚｉｐｆ ［１］发现在自然语言中，词的频率与 它在词汇表中的排名成反 通信作者：张晨． Ｅ⁃ｍａｉｌ： ｚｈａｎｇｃｈｅｎ．ｓｄｕｆｅ＠ ｇｍａｉｌ．ｃｏｍ． 比，服从幂律分布，他把 这种现象称为上下文语言模型中词的突发性。 后 来发现，在金融、基因表达、计算机视觉等方面的数 据也存在这种突发现象。 网络搜索已成为人们日 常生活中必不可少的一部分，用户提交的搜索查询 词是人类智慧的结晶，并在搜索查询和微博等网络 教育部人文社会科学研 究项目（１５ＹＪＡＺＨ０４２）．
第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模 提出的模型应具备以下条件：
信息中显现出与传统的自然语言不同的特点，网络 搜索中每一个用户的搜索条目都包括查询词和 ＵＲＬ 两 项。 已 经 提 出 的 Ｄｉｒｉｃｈｌｅｔ Ｃｏｍｐｏｕｎｄ Ｍｕｌｔｉｎｏｍｉａｌ （ ＤＣＭ） 模 型［２］ 和 Ｄｉｒｉｃｈｌｅｔ Ｃｏｍｐｏｕｎｄ Ｍｕｌｔｉｎｏｍｉａｌ Ｌａｔｅｎｔ Ｄｉｒｉｃｈｌｅｔ Ａｌｌｏｃａｔｉｏｎ （ＤＣＭＬＤＡ）模 型［３］可以对文章中词的突发性现象建模，但如果直 接应用于网络搜索建模却不是很理想。 虽然大多 数的点击图模型［４］及其变体［５－６］可以对网络搜索建 模，但都是针对用户群体进行研究而忽略了用户个 人特点。 本文通过分析用户查询日志来获取网络搜索 突发 现 象， 并 提 出 了 两 个 模 型： ＳＢＭ （ ｓｅａｒｃｈ ｂｕｒｓｔｉｎｅｓｓ ｍｏｄｅｌ ） 和 ＣＳ⁃ＳＢＭ （ ｃｏｕｐｌｉｎｇ⁃ｓｅｎｓｉｔｉｖｅ ｓｅａｒｃｈ ｂｕｒｓｔｉｎｅｓｓ ｍｏｄｅｌ）。 ＳＢＭ 是一个单极模型，假 设查询词和 ＵＲＬ 之间主题独立，突发性的相关信息 存储在偏 Ｄｉｒｉｃｈｌｅｔ 先验里。 ＣＳ⁃ＳＢＭ 充分考虑查询 词和 ＵＲＬ 之间的关联。 本文还用 Ｂｅｔａ 分布刻画了 用户搜索的时间特性，使前面提出的模型能够用来 捕获时间上的突发性。 １ 相关工作 Ｍａｄｓｅｎ 指出，多项分布经常用于文本建模。 然 而，多项分布能获取到文档中词汇的突发性现象， 即一个词如果出现过一次，那么它很有可能再次出 现［７］ 。 因 此 Ｍａｄｓｅｎ 提 出 了 Ｄｉｒｉｃｈｌｅｔ 多 项 分 布 （ＤＣＭ）来代替传统的多项分布。 ＤＣＭ 拥有一级自 由度，能获取到词的突发性，但是没有涉及文档中 词汇的主题。 文献［２］ 将 ＤＣＭ 模型扩展成为了混 合 ＤＣＭ 分布，该模型能够训练表示一组文档，其中 每一个文档都来自不同的高级主题。 但是，该模型 还是不能建模一个文档包含多个主题单词的情景。 上述工作中，之所以不能很好地刻画文档主 题，其主要原因是 ＤＣＭ 更关注突发性现象而非获取 文档主题。 ２００３ 年 Ｂｌｅｉ ［８］ 提出的 Ｌａｔｅｎｔ Ｄｉｒｉｃｈｌｅｔ Ａｌｌｏｃａｔｉｏｎ （ＬＤＡ） 是非监督的贝叶斯生成模型，它 可以将文档集中每篇文档的主题按照概率分布的 形式给出。 ＬＤＡ 包括词汇、主题和文档 ３ 层。 ＬＤＡ 引入了 Ｄｉｒｉｃｈｌｅｔ 先验分布，成为了一个完备的贝叶 斯模型。 ＬＤＡ 文档生成过程为，从 Ｄｉｒｉｃｈｌｅｔ 分布中 采样文档与主题、主题与词汇分布，再重复从文档－ 主题多项式分布中采样主题以及由主题－词汇多项 式分布生成词汇的过程，逐步生成整个文档。 ＬＤＡ 已经在学术和工业界得到广泛应用。 但是，ＬＤＡ 模 型并不能预测词汇突发性出现的趋势。 为了能够在获取主题的同时预测词汇突发性 现象，Ｇ．Ｄｏｙｌｅ ［３］提出了 ＤＣＭＬＤＡ 主题模型，该模型 结合了 ＤＣＭ 和 ＬＤＡ 的优势，直接将 ＤＣＭ 扩展合并 到主题模型里面形成了一个比 ＬＤＡ 更加复杂的模 型。 在 ＤＣＭＬＤＡ 中对于每个主题 ｋ 和每个文档 ｄ 服从新的多项式分布 θｋｄ ，每个主题 ｋ 都有不同的、 非均匀的 βｋ 向量。 对于每一个文档 ｄ， φｋｄ 根据 Ｄｉｒｉｃｈｌｅｔ（βｋ ）的变化而变化，因此每个主题实例在 文档之间是相互联系的。 文档中的主题实例允许 在同一主题不同文档中每一个词汇的概率不同，这 也就是突发现象。 随着带有时间标记的文本集合（例如，数字化 的报纸、杂志、博客等） 数量和体积的增加，如何有 效地搜索这些数据变得更加重要。 上述模型都难 以发现主题的演化趋势。 在这个背景下，文献［９］ 等提出了 Ｔｏｐｉｃ Ｏｖｅｒ Ｔｉｍｅ（ＴＯＴ）模型。 ＴＯＴ 将文档 的时间信息作为服从 Ｂｅｔａ 分布的变量，将每个主题 通过 Ｂｅｔａ 分布与时间信息相关联。 ＴＯＴ 假设每个 生成的词汇对应的时间信息也是通过它所属主题 相关的 Ｂｅｔａ 分布采样生成，这样主题与时间信息也 有关系。 ＴＯＴ 不依赖马尔可夫假说，这样能够避免 在离散化过程中遇到时间粒度选取的问题。 另外，文献［１０］系统地总结了自然语言处理中 主题模型的发展，对 ＬＤＡ 模型进行了详细的分析，并 对主题模型的发展趋势进行了预测。 根据微博的特 殊形式，在 ＬＤＡ 的基础上进行了改进，分别提出了 （ＭｉｃｒｏＢｌｏｇｓ⁃ＬＤＡ） ＭＢ⁃ＬＤＡ 模 型［１１］ 和 （ ＭｉｃｒｏＢｌｏｇｓ⁃ ＨＤＰ）ＭＢ⁃ＨＤＰ 模型［１２］ ，同时证明了提出模型能够很 好地对微博进行主题挖掘。 以前的工作都是集中在对自然语言文本中的 同质项目进行分析，即对一个文档中的同质词汇进 行建模。 然而在网络搜索分析中，文档是由查询词 和 ＵＲＬ 两个异构项目组成，并且带有时间信息。 因 此，本文结合网络搜索查询的文本特点，提出并研 究了将主题模型运用到网络搜索分析中，对查询词 和 ＵＲＬ 这两个异构项目和它们之间的关系进行 建模。 ２ 以用户为中心的概率主题模型 本节主要介绍了 ＳＢＭ 和 ＣＳ⁃ＳＢＭ 主题模型，以 及获取主题时间突发性的策略。 提出的模型应具备以下条件： 第 ５ 期 张森，等：基于用户查询日志的网络搜索主题分析 ·６６９·
·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是提交查询词给搜索引擎后
１）查询词和 ＵＲＬ 的突发性现象研究要分开 建模［１３］ 。 ２）建模时，网络搜索特点，包括查询词、ＵＲＬ 和 ｓｅｓｓｉｏｎ ３ 个维度都要考虑在内［１４－１５］ 。 ｓｅｓｓｉｏｎ 是指在短时间内提交的满足相同信息 需求的一系列查询。 为了避免同一会话中包含不 相干的查询而导致的性能降低，本文优先考虑同一 会话中查询词之间的语义一致性。 通过对比分析， 本文采用文献［１６］ 提出的一系列规则来划分搜索 ｓｅｓｓｉｏｎ。 这些规则用于评估查询之间的词汇相似 性，并在检测相关搜索查询时表现出很高精度。 ２．１ 查询词和 ＵＲＬ 独立的主题模型（ＳＢＭ） ＳＢＭ 的生成过程是基于查询词和 ＵＲＬ 相互独 立的假设。 与 ＬＤＡ 和 ＤＣＭＬＤＡ 等传统主题模型不 同，ＳＢＭ 中的文档有查询词、被点击 ＵＲＬ 和查询时 间三项。 图 １ 是 ＳＢＭ 的搜索主题模型概率图。 首 先，从超参数为 α 的 Ｄｉｒｉｃｈｌｅｔ 分布中抽样生成文档 与主题之间的关系矩阵 θ，θ 是一个 Ｄ×Ｋ 的矩阵，其 中 Ｄ 代表文档数量，Ｋ 代表主题数。 对于每一个主 题 ｋ，从超参为 βｋ 和 δｋ 的 Ｄｉｒｉｃｈｌｅｔ 分布中分别取样 生成查询词与主题之间的关系矩阵 θ 和 ＵＲＬ 与主 题之间的关系矩阵 Ω。 θ 和 Ω 是 Ｄ×Ｋ×Ｖ 的三维矩 阵，Ｖ 代表训练语料库中出现的所有词的词表。 对 于文档中的每一个 ｓｅｓｓｉｏｎ，从参数为 θｄ 的多项分布 中选择一个主题 ｚ，从参数为 φｚｄ的查询词的多项分 布中，采样生成查询词 ｗ。 然后，生成点击事件的二 项分布，如果 ＵＲＬ 被点击了，从参数为 Ωｚｄ的 ＵＲＬ 的多项分布中，采样生成 ＵＲＬ ｕ。 变量 θ 和 δ 是基 于单个特定文档的，因此 ＳＢＭ 可以为每一个用户查 询词和 ＵＲＬ 的突发性建模。 图 １ ＳＢＭ 网络搜索分析主题模型 Ｆｉｇ．１ ＳＢＭ ｗｅｂ ｓｅａｒｃｈ ａｎａｌｙｓｉｓ ｔｏｐｉｃ ｍｏｄｅｌ ＳＢＭ 中 的 Ｇｉｂｂｓ 采 样 方 法 借 鉴 了 ＬＤＡ 和 ＤＣＭＬＤＡ 中 Ｇｉｂｂｓ 采样的方法，并进行了推导。 模 型的完全似然函数为 Ｐ（ｗ，ｕ，ｚ α，β，δ） ＝ Ｐ（ｕ ｚ，δ）Ｐ（ｗ ｚ，β）Ｐ（ｚ α） 展开上式中的多项分布和 Ｄｉｒｉｃｈｌｅｔ 分布，利用多项 分布和 Ｄｉｒｉｃｈｌｅｔ 分布的共轭性质，分别积分掉参数 θ 和 φ 以后，通过借鉴 ＬＤＡ 和 ＤＣＭＬＤＡ 中 Ｇｉｂｂｓ 采 样的方法，在 ＳＢＭ 中概率 Ｐ（ｚ α）为 Ｐ（ｚ α） ＝ Γ（∑ Ｋ ｚ ＝ １ αｚ） ∏ Ｋ ｚ ＝ １ Γ（αｚ） æ è ç ç ç ö ø ÷ ÷ ÷ Ｄ ∏ Ｄ ｄ ＝ １ ∏ Ｔ ｚ ＝ １ Γ（ｎｄｚ ＋ αｚ） Γ（∑ Ｚ ｚ ＝ １ （ｎｄｚ ＋ αｚ）） 式中 ｎｄｚ为第 ｄ 个文档中主题 ｚ 的数量。 概率 Ｐ（ｗ｜ｚ，β）为 Ｐ（ｗ ｚ，β） ＝ ∏ Ｄ ｄ ＝ １ ∏ Ｋ ｋ ＝ １ Γ（∑ Ｗ ｗ ＝ １ βｋｗ） ∏ Ｗ ｗ ＝ １ Γ（βｋｗ） ∏ Ｗ ｗ ＝ １ Γ（ｎｄｋｗ ＋ βｋｗ） Γ（∑ Ｗ ｗ ＝ １ （ｎｄｋｗ ＋ βｋｗ）） æ è ç ç ç ö ø ÷ ÷ ÷ 式中 ｎｄｋｗ为第 ｄ 个文档中第 ｋ 个主题下查询词 ｗ 的 个数。 当该 ｓｅｓｓｉｏｎ 中没有 ＵＲＬ 被点击时的条件概 率为 Ｐ（ｚｉ ＝ ｋ Ｘｉ ＝ ０，ｚ －ｉ，ｗ，ｕ，α，β，δ） ∝ Ｃ ＤＫ ｄｋ ＋ αｋ ∑ Ｋ ｋ′ ＝ １ （Ｃ ＤＫ ｄｋ′ ＋ αｋ ′） · Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ）） Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ）） ∏ Ｗ ｗ ＝ １ Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ） Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗ） 式中：Ｃ ＤＫ ｄｋ 表示文档 ｄ 中分配主题为 ｋ 的 ｓｅｓｓｉｏｎ 的 数量，Ｃ ＫＷＤ ｋｗｄ 表示文档 ｄ 中查询词 ｗ 被分配主题 ｋ 的 次数，Ｎｉｗ表示第 ｉ 个 ｓｅｓｓｉｏｎ 中查询词 ｗ 的个数。 当一个 ｓｅｓｓｉｏｎ 中有 ＵＲＬ 被点击时的条件概 率为 Ｐ（ｚｉ ＝ ｋ ｜ Ｘｉ ＝ １，ｚ －ｉ，ｗ，ｕ，α，β，δ） ∝ Ｃ ＤＫ ｄｋ ＋ αｋ ∑ Ｋ ｋ′ ＝ １ （Ｃ ＤＫ ｄｋ′ ＋ αｋ ′） · Γ（∑ Ｗ ｗ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ）） Γ（∑ Ｗ ｗ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗ ＋ Ｎｉｗ）） ∏ Ｗ ｗ ＝ １ Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ） Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ） · Γ（∑ Ｕ ｕ ＝ １ （Ｃ ＫＵＤ ｋｕｄ ＋ δｕｋ）） Γ（∑ Ｕ ｕ ＝ １ （Ｃ ＫＵＤ ｋｕｄ ＋ δｕｋ ＋ Ｎｉｕ）） ∏ Ｕ ｕ ＝ １ Γ（Ｃ ＫＵＤ ｋｕｄ ＋ δｕｋ ＋ Ｎｉｕ） Γ（Ｃ ＫＵＤ ｋｕｄ ＋ δｕｋ） 式中，Ｃ ＫＵＤ ｋｕｄ 表示文档 ｄ 中 ＵＲＬ ｕ 被分配主题 ｋ 的次 数，Ｎｉｕ表示第 ｉ 个 ｓｅｓｓｉｏｎ 中 ＵＲＬ ｕ 的数量。 ２．２ 查询词和 ＵＲＬ 相关联的主题模型（ＣＳ⁃ＳＢＭ） 查询词和 ＵＲＬ 通过搜索引擎紧密地结合在一 起，这使得本文研究的问题变得更加复杂。 被点击 的 ＵＲＬ 是由对应的查询词经过搜索得出的。 在网 络搜索的情境中，ＵＲＬ 是提交查询词给搜索引擎后 ·６７０· 智 能 系 统 学 报 第 １２ 卷
第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();
返回的结果。 因此，ＵＲＬ 和查询词是相关的。 为了 获取它们两者之间的关系，这里引入变量 Δｑｋｕ 来 代表“查询词－ＵＲＬ”的多项分布，其先验由 δ 表示。 “查询词－ＵＲＬ”多项式通过目前已经被广泛采用的 点击图来获得，点击图由搜索查询和被点击的 ＵＲＬ 两部分组成。 用于表示全局部分的 ＣＳ⁃ＳＢＭ 定义为 ＣＳ⁃ＳＢＭ⁃Ｇ。 因为本文重点研究以单个用户为核心 的信息能否增强主题模型的表现，所以基于单个用 户 “查询词－ＵＲＬ”多项分布的 ＣＳ⁃ＳＢＭ 定义为 ＣＳ⁃ ＳＢＭ⁃Ｕ。 图 ２ 给出了 ＣＳ⁃ＳＢＭ 的生成过程。 与 ＳＢＭ 相 比，查询词的生成过程不变，两者最主要的区别在 于，ＣＳ⁃ＳＢＭ 在 ＵＲＬ 生成的时候要考虑查询词的影 响，对于 ｓｅｓｓｉｏｎ 中每一个查询项 ｑ，首先生成点击事 件的二项分布，如果 ＵＲＬ 被点击了，则从参数为 Ωｑｚ 的 ＵＲＬ 多项分布中采样生成 ＵＲＬ ｕ。 图 ２ ＣＳ⁃ＳＢＭ 网络搜索分析主题模型 Ｆｉｇ．２ ＣＳ⁃ＳＢＭ ｗｅｂ ｓｅａｒｃｈ ａｎａｌｙｓｉｓ ｔｏｐｉｃ ｍｏｄｅｌ 模型的完全似然函数为 Ｐ（ｗ，ｕ，ｚ α，β，δ） ＝ Ｐ（ｕ ｚ，ｗ，δ）Ｐ（ｗ ｚ，β）Ｐ（ｚ α） 在 ＣＳ⁃ＳＢＭ 中， 同 样 采 用 了 与 ＬＤＡ 类 似 的 Ｇｉｂｂｓ 采样方法。 Ｐ（ｚ｜ α）和 Ｐ（ｗ ｚ，β）都与 ＳＢＭ 中 的相同。 两者主要的区别就是给定的主题中的 ｗ 和 ｕ 不再相互独立。 ｕ 的生成过程可能受到主题 ｚ 和相关搜索查询 ｑ 的影响。 Ｐ（ｕ ｜ ｚ，ｗ，δ） ＝ ∫∏ Ｄ ｄ ＝ １ ∏ Ｎｄ ｉ ＝ １ Ｐ（ｕｄｉ ｜ Δｑｄｉ ｚｄｉ ）∏ Ｑ ｑ ＝ １ ∏ Ｋ ｚ ＝ １ ｐ（Δｑｚ ｜ δ）ｄΔ ＝ ∫∏ Ｋ ｚ ＝ １ ∏ Ｑ ｑ ＝ １ ∏ Ｕ ｕ ＝ １ Δ ｎｑｚｕ ｑｚｕ ∏ Ｑ ｑ ＝ １ ∏ Ｋ ｚ ＝ １ （ Γ（∑ Ｕ ｕ ＝ １ δｑｕ ） ∏ Ｕ ｕ ＝ １ Γ（δｑｕ ） ∏ Ｕ ｕ ＝ １ Δ δｑｕ －１ ｑｚｕ ）ｄΔ ＝ ∏ Ｑ ｑ ＝ １ （ Γ（∑ Ｕ ｕ ＝ １ δｑｕ ） Ｋ ∏ Ｕ ｕ ＝ １ Γ（δｑｕ ） ） × ∏ Ｋ ｚ ＝ １ ∏ Ｑ ｑ ＝ １ ∏ Ｕ ｕ ＝ １ Γ（ｎｑｚｕ ＋ δｑｕ ） Γ（∑ Ｕ ｕ ＝ １ （ｎｑｚｕ ＋ δｑｕ ）） 式中，ｎｑｚｕ是第 ｚ 个主题的第 ｑ 个查询中的 ＵＲＬ ｕ 的 数量。 当 ｓｅｓｓｉｏｎ 中没有 ＵＲＬ 被点击时的条件概率为 Ｐ（ｚｉ ＝ ｋ Ｘｉ ＝ ０，ｚ －ｉ，ｗ，ｕ，α，β，δ，Ψ） ∝ Ｃ ＤＫ ｄｋ ＋ αｋ ∑ Ｋ ｋ′ ＝ １ （Ｃ ＤＫ ｄｋ′ ＋ αｋ ′） · Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ）） Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ ）） · ∏ Ｗ ｗ ＝ １ Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ ） Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗ ） 当 ｓｅｓｓｉｏｎ 中有 ＵＲＬ 被点击时的条件概率为 Ｐ（ｚｉ ＝ ｋ ｜ Ｘｉ ＝ １，ｚ －ｉ，ｗ，ｔ，ｕ，α，β，δ，Ψ） ∝ Ｃ ＤＫ ｄｋ ＋ αｋ ∑ Ｋ ｋ′ ＝ １ （Ｃ ＤＫ ｄｋ′ ＋ αｋ ′） · Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ）） Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ ）） · ∏ Ｗ ｗ ＝ １ Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ） Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗ） ∏ｑ∈ｓ ｉ Γ（∑ Ｕ ｕ ＝ １ （Ｃ ＱＺＵ ｑｚｕ ＋ δｑｕ）） Γ（∑ Ｕ ｕ ＝ １ （Ｃ ＱＺＵ ｑｚｕ ＋ δｑｕ ＋ Ｎｉｕ）） · ∏ｕ←ｑ Γ（Ｃ ＱＺＵ ｑｚｕ ＋ δｑｕ ＋ Ｎｉｕ ） Γ（Ｃ ＱＺＵ ｑｚｕ ＋ δｕ ） 式中： Ｃ ＱＺＵ ｑｚｕ 表示在一个 ｓｅｓｓｉｏｎ 里查询项 ｑ 中的 ＵＲＬ ｕ被分配主题为 ｚ 的次数；Ｎｉｗ表示 ｓｅｓｓｉｏｎ ｉ 中 ＵＲＬ 的数量。 ２．３ 主题在时间上的突发性 网络搜索中另一个常见现象就是时间上的突 发性。 一个用户更倾向于在一个很短的时间内集 中查询一些内容。 因此，本文假设每一个用户的查 询轨迹都有一个时间上的突发性，这种突发性由与 查询相关的时间戳来体现。 因为时间粒度是很难 设定的，所以本文采用 ＴＯＴ 中提出的方法，使用连 续的 Ｂｅｔａ 分布来捕获主题时间上的突发性。 通过 引入 Ｂｅｔａ 分布，使一个主题能够更容易在一个短的 时间周期内出现。 在这种情况下，本文从整个语料 库级别（定义为 Ｘ－ＴＧ）和基于单一用户级别（定义 为 Ｘ － ＴＵ） 出发，刻画一个主题在时间上的变化 趋势。 因为主题－周期的多项分布是固定的（对每一 个用户而言），所以主题中存在的时间周期将会证 明突发性。 每天或者每小时都可以观察到突发性 现象，这表明去离散化是更合适的。 下面是 ＳＢＭ 和 ＣＳ⁃ＳＢＭ 在添加了时间信息以 后的模型算法。 ｔｈｅ ｓａｍｅ ａｓ ｔｈｅ ｏｒｉｇｉｎａｌ ｍｏｄｅｌ ｆｏｒ ｅａｃｈ ｓｅｓｓｉｏｎ ｓ ｉｎ ｄ ｄｏ ｃｈｏｏｓｅ ａ ｔｏｐｉｃ ｚ：Ｍｕｌｔｉｎｏｍｉａｌ（θｄ ）； 第 ５ 期 张森，等：基于用户查询日志的网络搜索主题分析 ·６７１·
·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))
ｇｅｎｅｒａｔｅ ｔｉｍｅｓｔａｍｐｓ ｔ～ Ｂｅｔａ（τｚ）（Ｘ－ＴＧ） ｏｒ ｔ：Ｂｅｔａ（τｚｄ ） （Ｘ－ＴＵ）； ｔｈｅ ｓａｍｅ ａｓ ｔｈｅ ｏｒｉｇｉｎａｌ ｍｏｄｅｌ ｅｎｄ ｆｏｒ 它主要的变化在于，对文档中的每一个 ｓｅｓｓｉｏｎ， 从参数为 θｄ 的多项分布中采样一个主题 ｚ，然后根 据数据集的不同，从 Ｂｅｔａ 分布 Ｂｅｔａ（τｚ）和 Ｂｅｔａ（τｚｄ ） 分别生成基于全局的时间戳和基于特定用户的时 间戳。 ＴＳ⁃ＳＢＭ 的 Ｇｉｂｂｓ 采样与 ＬＤＡ 方法类似。 本文 给出了一些简单的推导。 首先，模型的完全似然函 数为 Ｐ（ｗ，ｕ，ｔ，ｚ｜ α，β，δ，τ）＝ Ｐ（ｔ ｜ｚ，τ）Ｐ（ｕ ｜ｚ，δ）· Ｐ（ｗ｜ｚ，β）Ｐ（ｚ｜ α） 如果 ｓｅｓｓｉｏｎ 中没有 ＵＲＬ 被点击，那么此时的条件 概率是： Ｐ（ｚｉ ＝ ｋ ｜ Ｘｉ ＝ ０，ｚ －ｉ，ｗ，ｕ，α，β，δ，τ） ∝ ∏ Ｔ ｊ ＝ １ （１ － ｔ ｊ） τ ｄｋ１ －１ ｔ τ ｄｋ２ －１ ｊ Ｂ（τｄｋ１ ，τｄｋ２ ） Ｃ ＤＫ ｄｋ ＋ αｋ ∑ Ｋ ｋ′ ＝ １ （Ｃ ＤＫ ｄｋ′ ＋ αｋ′） · Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ）） Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ）） ∏ Ｗ ｗ ＝ １ Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ） Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗ） 式中：τｄｋ１和 τｄｋ２是 Ｂｅｔａ 分布的超参数。 对于 ＳＢＭ 模型，如果 ｓｅｓｓｉｏｎ 中有 ＵＲＬ 被点击， 此时的条件概率为 Ｐ（ｚｉ ＝ ｋ ｜ Ｘｉ ＝ １，ｚ －ｉ，ｗ，ｕ，α，β，δ） ∝ ∏ Ｔ ｊ ＝ １ （１ － ｔ ｊ） τ ｄｋ１ －１ ｔ τ ｄｋ２ －１ ｊ Ｂ（τｄｋ１ ，τｄｋ２ ） Ｃ ＤＫ ｄｋ ＋ αｋ ∑ Ｋ ｋ′ ＝ １ （Ｃ ＤＫ ｄｋ′ ＋ αｋ′） · Γ（∑ Ｗ ｗ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ）） Γ（∑ Ｗ ｗ ＝ １ （Ｃ ＫＷ ｋｗ ＋ βｗ ＋ Ｎｉｗ ）） ∏ Ｗ ｗ ＝ １ Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ ） Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ） · Γ（∑ Ｕ ｕ ＝ １ （Ｃ ＫＵＤ ｋｕｄ ＋ δｕｋ）） Γ（∑ Ｕ ｕ ＝ １ （Ｃ ＫＵＤ ｋｕｄ ＋ δｕｋ ＋ Ｎｉｕ ）） ∏ Ｕ ｕ ＝ １ Γ（Ｃ ＫＵＤ ｋｕｄ ＋ δｕｋ ＋ Ｎｉｕ ） Γ（Ｃ ＫＵＤ ｋｕｄ ＋ δｕｋ） 对于 ＣＳ⁃ＳＢＭ 模型，当 ｓｅｓｓｉｏｎ 中有 ＵＲＬ 被点击时的 条件概率为 Ｐ（ｚｉ ＝ ｋ ｜ Ｘｉ ＝ １，ｚ －ｉ，ｗ，ｔ，ｕ，α，β，δ，Ψ） ∝ ∏ Ｔ ｊ ＝ １ （１ － ｔ ｊ） τ ｄｋ１ －１ ｔ τ ｄｋ２ －１ ｊ Ｂ（τｄｋ１ ，τｄｋ２ ） Ｃ ＤＫ ｄｋ ＋ αｋ ∑ Ｋ ｋ′ ＝ １ （Ｃ ＤＫ ｄｋ′ ＋ αｋ′） · Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ）） Γ（∑ Ｗ ｔ ＝ １ （Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ）） ∏ Ｗ ｗ ＝ １ Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗｋ ＋ Ｎｉｗ） Γ（Ｃ ＫＷＤ ｋｗｄ ＋ βｗ） · ∏ｑ∈ｓ ｉ Γ（∑ Ｕ ｕ ＝ １ （Ｃ ＱＺＵ ｑｚｕ ＋ δｑｕ ）） Γ（∑ Ｕ ｕ ＝ １ （Ｃ ＱＺＵ ｑｚｕ ＋ δｑｕ ＋ Ｎｉｕ ）） ∏ｕ←ｑ Γ（Ｃ ＱＺＵ ｑｚｕ ＋ δｑｕ ＋ Ｎｉｕ ） Γ（Ｃ ＱＺＵ ｑｚｕ ＋ δｕ ） 时间的参数按照如下方法更新： τｋｄ１ ＝ ｔ ｋｄ ［ ｔ ｋｄ （１ － ｔ ｋｄ ） ｓ ２ ｋｄ － １］ τｋｄ２ ＝ （１ － ｔ ｋｄ ）［ ｔ ｋｄ （１ － ｔ ｋｄ ） ｓ ２ ｋｄ － １］ 式中，ｔ ｋｄ和 ｓ ２ ｋｄ表示每一个文档中主题 ｚ 时间上的样 本均值和样本偏方差。 ３ 参数估计 关于超参数 α 和 β 设置问题，一些 ＬＤＡ 应用采 用默认相同值的方法获得了成功，例如由 Ｇｒｉｆｆｉｔｈｓ 和 Ｓｔｅｙｅｒｓ ［１７］提出的 α＝ ５０ ／ ｋ，β ＝ ０．０１，Ｋ 是主题的数 量。 因此，在 ＬＤＡ 中没有必要去研究超参数。 然 而，在本文提出的模型中，超参数的设置是至关重 要的。 因为 ＬＤＡ 中的 φ 和 Ω 值，也被包括在 ＳＢＭ 和 ＣＳ⁃ＳＢＭ 的 β 和 δ 中。 ＳＢＭ 完全似然 Ｐ（ｗ，ｕ，ｚ ｜ α，β，δ） 的计算如下 所示： Ｐ（ｗ，ｕ，ｚ ｜ α，β，δ） ＝ ∏ｄ （ Γ（∑ Ｋ ｋ ＝ １ αｋ） ∏ Ｋ ｋ ＝ １ Γ（αｋ） ） ∏ Ｔ ｋ ＝ １ Γ（ｍｄｋ ＋ αｋ） Γ（∑ Ｋ ｋ ＝ １ （ｍｄｋ ＋ αｋ）） · ∏ｄ，ｋ （（ Γ（∑ Ｗ ｗ ＝ １ βｗｋ） ∏ Ｗ ｗ ＝ １ Γ（βｗｋ） ） ∏ Ｗ ｗ ＝ １ Γ（ｎｋｗｄ ＋ βｗｋ） Γ（∑ Ｗ ｗ ＝ １ （ｎｋｗｄ ＋ βｗｋ）） ）· （ Γ（∑ Ｕ ｕ ＝ １ δｕｋ） ∏ Ｕ ｕ ＝ １ Γ（δｕｋ） ） ∏ Ｕ ｕ ＝ １ Γ（ｎｋｕｄ ＋ δｕｋ） Γ（∑ Ｕ ｕ ＝ １ （ｎｋｕｄ ＋ δｕｋ）） ） ＣＳ⁃ＳＢＭ 完全似然 Ｐ（ｗ，ｕ，ｚ ｜ α，β，δ）的计算如 下所示： Ｐ（ｗ，ｕ，ｚ ｜ α，β，δ） ＝ ∏ｄ （ Γ（∑ Ｋ ｋ ＝ １ αｋ） ∏ Ｋ ｋ ＝ １ Γ（αｋ） ） ∏ Ｔ ｋ ＝ １ Γ（ｍｄｋ ＋ αｋ） Γ（∑ Ｋ ｋ ＝ １ （ｍｄｋ ＋ αｋ）） · ·６７２· 智 能 系 统 学 报 第 １２ 卷