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

第七章用户行为特征及缓存的应用 张宇计算机科学与技术学院 研究用户行为特征的目的 搜索引擎用户输入的查询词语和查询过程中所点击到的网页URL均表现出明显的局部性可以用来指导查询缓存的设计 主要内容 用户查询与点击日志用户行为特征的统计分析查询缓存的使用用户行为与Web信息的分布特征 主要内容 用户查询与点击日志用户行为特征的统计分析查询缓存的使用用户行为与Web信息的分布特征 用户查询与点击日志 搜索引擎所维护的信息种类搜集到的Web网页相关的信息网页经过分析处理后得到的信息 摘要 关键词 元信息 URL超链信息这些都是提供给用户看的信息在服务过程中收集到的用户行为信息用户的查询项 查询时间 用户的IP地址 用户点击的感兴趣的页面的URL 用户查询与点击日志 天网日志文件用户查询日志用户提交查询请求时记录的用户提交的关键词 提交时间 用户的IP 页号 是否在缓存中命中用户点击日志在用户浏览查询结果时点击页面时记录的用户点击页面的时间 点击页面的URL 用户IP 点击页面的序号 该点击对应的查询词等 FriMar2100 00 022003 提交时间218 24 100 77 用户IPDatabase 是否在缓存中命中老歌 查询词3 页号 FriMar2100 00 022003 点击时间202 206 102 169 用户IP虫儿飞 查询词 用户查询与点击日志 统计分析了如下用户行为的分布特征用户查询词的分布情况雷同查询词的衰减统计相邻N项查询项的偏差分析用户点击URL的分布情况用户在输出结果中的翻页情况 主要内容 用户查询与点击日志用户行为特征的统计分析查询缓存的使用用户行为与Web信息的分布特征 用户行为特征的统计分析 用户查询词的分布情况天网1999年4月15日到1999年6月10日期间的日志记录为分析对象假设用户的查询词序列为其中 n个查询中共有m个不同的查询词按查询次数降序排列 得到 用户行为特征的统计分析 与S2对应的查询次数序列S2中前某个百分比的查询词对应的查询次数占总查询次数的比率Y 用户行为特征的统计分析 查询词的分布情况 X轴 用户查询词占查询词总数的百分比Y轴 查询词的查询次数占总的查询次数的百分比 查询词分布函数及其拟合函数 原函数 拟合函数 拟合函数 y 0 04103 1 01689x 0 1346 用户行为特征的统计分析 雷同查询词的衰减统计将序列S1进行分组 用户的查询词序列 每1000个一组T1表示A1中不同的查询项组成的集合 然后计算后面各组的查询项中有多少个查询项出现在T1中 用户行为特征的统计分析 雷同查询词的衰减 用户行为特征的统计分析 相邻N项查询的偏差分析将用户查询每1000项分为一组对于相邻的两组A和B假设A组中出现的不同的用户查询是其中 前k项是A组和B组共有的 后n项是A中但B中没有的同理 B组中出现的不同的用户查询是 用户行为特征的统计分析 A和B中的这些不同的查询项构成一个向量空间假设 为某查询词qi在A中出现的次数 则可得到A组的特征向量同样 可得到B组的特征向量 用户行为特征的统计分析 计算上两种特征向量的差平方和 相邻1000项查询词的频率的差的平方和 用户行为特征的统计分析 用户在输出结果中的翻页情况统计表统计相同页号的页面点击次数占总点击此书的百分比假设系统能够提供n个显示页面实际系统中 n 2000 每页包括10个网页信息显示页面 P1 Pn 对应的点击数 C1 Cn 用户行为特征的统计分析 计算其点击次数占总点击此书的百分比 用户在前5页的翻页情况统计 用户行为特征的统计分析 用户翻页情况统计 用户行为特征的统计分析 用户点击URL的分布情况假设用户点击的URL序列为其中 这n个点击中有m个是不同的 按其被点击次数进行降序排列 得到序列与S2对应的点击次数序列 用户行为特征的统计分析 计算S2中前某个百分比的URL其对应点击次数占总点击次数的比率Y 用户点击URL的分布情况 横坐标 所选URL的数目占用户点击的URL总数的比率纵坐标 所选URL的被点击数目占用户点击总数的比率 用户行为特征的统计分析 主要内容 用户查询与点击日志用户行为特征的统计分析查询缓存的使用用户行为与Web信息的分布特征 查询缓存的使用 基于用户行为的启示用户查询分布的统计分析表明用户查询词是非常集中的表明在查询中使用缓存的可行性用户经常查询的词其实很少把这些查询次数较高的词的查询结果放在缓存中 可以用较小的空间取得较大的缓存命中率 假设缓存中命中一个用户查询需要的延迟是Tm磁盘文件中查找一个用户查询需要的时间是Td缓存命中率是p引入缓存后 用户查询的平均响应时间变为未使用缓存的 倍访问一次硬盘的时间大约是访问一次内存的几十倍 1 p 查询缓存的使用 用户雷同查询项的统计分析表明用户查询有一定的稳定性放在缓存中的查询信息及其结果不仅在很短的时间内才有效 可能经过一段时间后还被用户查询 查询缓存的使用 相邻N项查询项的统计分析表明相邻N项查询项的查询频率偏差很小而且非常稳定缓存替换过程不会因为用户查询短期内的变化而产生颠簸现象 查询缓存的使用 对用户在输出结果中翻页情况的统计分析表明用户通常只浏览前几页的内容 说明了对输出结果进行排序的重要性一个URL被很多用户点击 表明该URL相对重要 提高其权值不是在硬盘中修改的使用热点击缓存 将用户点击过的URL放在里面 若再次被点击 在内存中进行修改 查询缓存的使用 缓存替换策略的研究FIFO firstinfirstout LRU leastrecentlyused 替换最近最少使用的对象LFU leastfrequentlyused 替换缓存中最少被引用的对象 查询缓存的使用 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 C1000000URL目录深度 D1 D2 D1000000 用户行为与Web信息的分布特