论文作者:Doug Beeferman 本文将解读此篇论文,此论文利用搜索日志中的<query,url>类型点击日志,实现忽略目标url内容,基于搜索词条用户的点击数据,聚合相关搜索和连接的算法。(本解读文章个人辛苦之作,请勿随意转载 文章链接 https://www.cnblogs.com/jiaomaster/p/16271663.html)
随着互联网规模的扩大和普及,现在有超过10亿个静态网页(作者所写的年份),一些商业搜索引擎每天处理数以千万计的查询对组织这些数据的自动方法的迫切需求已经发展。为大规模的非结构化数据集带来一定程度的秩序的一种策略是将相似的项分组在一起。本文介绍了一种技术,用于通过Internet搜索从用户事务集合中找到相关查询和相关url的集群。作者列举了一些常用的文档的聚类计算方法,如HAC,k-means,但是这些都基于文档内容,但作者提出了一种基于用户点击数据日志的方法。
http协议允许商业搜索引擎记录关于用户的大量信息——发送请求的机器的名称和IP地址、机器上运行的web浏览器的类型、机器的屏幕分辨率,等等。这里,我们只对包含用户提交的查询的字符序列和用户从搜索引擎提供的选项中选择的URL感兴趣。表1列出了来自最近Lycos日志的点击记录(查询,URL)的一小段摘录。
表1:2000年2月某一天Lycos点击记录(用户查询和所选url)的一小段摘录。
1.构造二部图 点击转跳二部图介绍
首先我们约定,用户查询词query为Q,Url则为U,构造出的图为G,二部图的query顶点W(白节点),Url顶点为B(黑节点),日志的数据集为C(数据集格式<query,url>)
2.节点间的相似度
为了对二部图进行聚合,需要计算每个顶点之间的相似度,引入公式
公式中σ(x,y)表示x和y顶点(黑和黑,白和白),N(x)代表顶点x和另一边顶点的总边数,N(y)代表顶点y和另一边顶点的总边数,所以公式的意思就是,两顶点重合的边和总共的边的比代表相似度
3.对二部图进行聚合
此为我本人项目用的思路,得到聚合数据以后,可根据用户搜索时返回的链接,在聚合数据中匹配,将匹配到的聚合数据的query数据就是相关搜索的推荐内容
在阅读其它文章,我发现有以下两个缺点
1.没有考虑噪声数据,即用户错误点击
对此问题 W ing Shun Chan 在论文《Query Log Containing Noisy Clickthroughs 》中,给出了优化的相似度计算公式
2.没有给出算法明确停止边界
如果计算的最大相似度度太低,会导致不相关的也被强行聚合,所以,我们通过设置一个阈值来解决
[ 1] Doug Beeferman, Adam Berger. Agglomerative Clustering of a Search Engine Query Log[C], Proceedings of the sixth ACM S IGKDD interna2 tional con ference on knowledge discovery and data m ining, pp. 407 416, August 20~23, 2000, Boston, M assachusetts, United States.
[2] W ing Shun Chan, W ai Ting Leung, D ik Lun Lee. Clustering Search En2 gine Query Log Containing Noisy Clickthroughs [C], Proceedings ofthe 2004 International Symposium on App lications and the Internet( SAINTT04).