第七章 用户行为特征及缓存的应用.ppt

1、第七章用户行为特征及缓存的应用,张宇 计算机科学与技术学院,研究用户行为特征的目的,搜索引擎用户输入的查询词语和查询过程中所点击到的网页URL均表现出明显的局部性 可以用来指导查询缓存的设计,主要内容,用户查询与点击日志 用户行为特征的统计分析 查询缓存的使用 用户行为与Web信息的分布特征,主要内容,用户查询与点击日志 用户行为特征的统计分析 查询缓存的使用 用户行为与Web信息的分布特征,用户查询与点击日志,搜索引擎所维护的信息种类 搜集到的Web网页相关的信息 网页经过分析处理后得到的信息：摘要、关键词、元信息、URL超链信息 这些都是提供给用户看的信息 在服务过程中收集到的用户行为信息

2、 用户的查询项、查询时间、用户的IP地址、用户点击的感兴趣的页面的URL,用户查询与点击日志,天网日志文件 用户查询日志 用户提交查询请求时记录的 用户提交的关键词、提交时间、用户的IP、页号、是否在缓存中命中 用户点击日志 在用户浏览查询结果时点击页面时记录的 用户点击页面的时间、点击页面的URL、用户IP、点击页面的序号、该点击对应的查询词等,Fri Mar 21 00:00:02 2003 /提交时间 218.24.100.77 /用户IP Database /是否在缓存中命中 老歌 /查询词 3 /页号,Fri Mar 21 00:00:02 2003 /点击时间 202.206.10

3、2.169 /用户IP 虫儿飞 /查询词 /点击的URL 16 /点击页面的排序,用户查询与点击日志,统计分析了如下用户行为的分布特征 用户查询词的分布情况 雷同查询词的衰减统计 相邻N项查询项的偏差分析 用户点击URL的分布情况 用户在输出结果中的翻页情况,主要内容,用户查询与点击日志 用户行为特征的统计分析 查询缓存的使用 用户行为与Web信息的分布特征,用户行为特征的统计分析,用户查询词的分布情况 天网1999年4月15日到1999年6月10日期间的日志记录为分析对象 假设用户的查询词序列为 其中，n个查询中共有m个不同的查询词 按查询次数降序排列，得到,用户行为特征的统计分析,与S2对

4、应的查询次数序列 S2中前某个百分比的查询词对应的查询次数占总查询次数的比率Y,用户行为特征的统计分析,查询词的分布情况,X轴：用户查询词占查询词总数的百分比 Y轴：查询词的查询次数占总的查询次数的百分比,查询词分布函数及其拟合函数,原函数,拟合函数,拟合函数：y=（-0.04103+1.01689x）0.1346,用户行为特征的统计分析,雷同查询词的衰减统计 将序列S1进行分组（用户的查询词序列） 每1000个一组 T1表示A1中不同的查询项组成的集合，然后计算后面各组的查询项中有多少个查询项出现在T1中,用户行为特征的统计分析,雷同查询词的衰减,用户行为特征的统计分析,相邻N项查询的偏差分

5、析 将用户查询每1000项分为一组 对于相邻的两组A和B 假设A组中出现的不同的用户查询是 其中，前k项是A组和B组共有的，后n项是A中但B中没有的 同理，B组中出现的不同的用户查询是,用户行为特征的统计分析,A和B中的这些不同的查询项构成一个向量空间 假设， 为某查询词qi在A中出现的次数，则可得到A组的特征向量 同样，可得到B组的特征向量,用户行为特征的统计分析,计算上两种特征向量的差平方和,相邻1000项查询词的频率的差的平方和,用户行为特征的统计分析,用户在输出结果中的翻页情况统计表 统计相同页号的页面点击次数占总点击此书的百分比 假设系统能够提供n个显示页面 实际系统中，n=2000

6、，每页包括10个网页信息 显示页面：P1,Pn 对应的点击数：C1,Cn,用户行为特征的统计分析,计算其点击次数占总点击此书的百分比,用户在前5页的翻页情况统计,用户行为特征的统计分析,用户翻页情况统计,用户行为特征的统计分析,用户点击URL的分布情况 假设用户点击的URL序列为 其中，这n个点击中有m个是不同的，按其被点击次数进行降序排列，得到序列 与S2对应的点击次数序列,用户行为特征的统计分析,计算S2中前某个百分比的URL其对应点击次数占总点击次数的比率Y,用户点击URL的分布情况,横坐标：所选URL的数目占用户点击的URL总数的比率 纵坐标：所选URL的被点击数目占用户点击总数的比率

7、,用户行为特征的统计分析,主要内容,用户查询与点击日志 用户行为特征的统计分析 查询缓存的使用 用户行为与Web信息的分布特征,查询缓存的使用,基于用户行为的启示 用户查询分布的统计分析表明 用户查询词是非常集中的 表明在查询中使用缓存的可行性 用户经常查询的词其实很少 把这些查询次数较高的词的查询结果放在缓存中，可以用较小的空间取得较大的缓存命中率,假设 缓存中命中一个用户查询需要的延迟是Tm 磁盘文件中查找一个用户查询需要的时间是Td 缓存命中率是p 引入缓存后，用户查询的平均响应时间变为未使用缓存的倍 访问一次硬盘的时间大约是访问一次内存的几十倍 1-p,查询缓存的使用,用户雷同查询项的

8、统计分析表明 用户查询有一定的稳定性 放在缓存中的查询信息及其结果不仅在很短的时间内才有效，可能经过一段时间后还被用户查询,查询缓存的使用,相邻N项查询项的统计分析表明 相邻N项查询项的查询频率偏差很小而且非常稳定 缓存替换过程不会因为用户查询短期内的变化而产生颠簸现象,查询缓存的使用,对用户在输出结果中翻页情况的统计分析表明 用户通常只浏览前几页的内容，说明了对输出结果进行排序的重要性 一个URL被很多用户点击，表明该URL相对重要，提高其权值 不是在硬盘中修改的 使用热点击缓存，将用户点击过的URL放在里面，若再次被点击，在内存中进行修改,查询缓存的使用,缓存替换策略的研究 FIFO（fi

9、rst in first out） LRU（least recently used） 替换最近最少使用的对象 LFU（least frequently used） 替换缓存中最少被引用的对象,查询缓存的使用,FIFO、LRU和LFU的缓存命中率比较,查询缓存的使用,3种替换策略的局部比较,查询缓存的使用,衰减因子 每次发生替换时，用某个衰减因子去衰减原来的查询次数并累加新的查询次数,调整后的LFU和LRU命中率的比较,查询缓存的使用,主要内容,用户查询与点击日志 用户行为特征的统计分析 查询缓存的使用 用户行为与Web信息的分布特征,用户行为与Web信息的分布特征,基本术语 网页重要度的度量 用户访问越多的网页越重要 网页P的入度H(P) 整个网络中指向网页P的超链接数目 网页P的镜像度C(P) 整个网络中网页P的镜像个数 域名深度：域名中包含子域的个数 目录深度D(P)：域名中包含目录的层数,海量Web信息的特征分析 URL序列：U1, U2, , U1000000 对应的用户点击次数为： V1, V2, , V1000000 对应的网页入度为： H1, H2, , H1000000 网页镜像度为： C1, C2, , C1000000 URL目录深度： D1, D2, , D1000000,用户行为与We