10-互联网有哪些信誉好的足球投注网站searching the web-1基本原理basic principles[精品].ppt

* * * * * * * * * * * * * 平稳，顾名思义，是指过程随时间变化特性没有发生变化，任意时刻开始观测该过程都是一样的；各态历经，任意时刻都可以取所有可能值，意思是说，任意观测一次的结果都是一样的。 各态历经过程是平稳随机过程中最为重要的一类。如果平稳随机过程中集合的平均值可以由样本的时间平均值来代替，也就是说，其中任意一条样本曲线基本上包含了该随机过程所具有的所有统计特性，这时就说它是各态历历经过程。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 帮助使用者 通过用户交互 检查拼写 查询优化 给出查询建议 理解用户上下文 * 上下文敏感的拼写检查 * 给出查询建议 * 引用分析: 科研论文上下文 引用频率 引用文献耦合频率 同时引用相同引文的文章相关 引用索引 给定一个作者，他/她都被谁引用了? (Garfield [Garf72]) * * * * 独立于查询的排序 第一代：用链接计数作为简单的网页声望值度量 两个基本的建议 无向声望值Undirected popularity 每个页面都有一个评分 = 入链接的数量+出链接的数量 (3+2=5) 有向声望值Directed popularity 网页的评分 = 入链接的数量 (3) * 查询处理 首先检出所有满足文本查询的页面 将检出的页面按链接声望度排序 无向声望度 入链接的数量+出链接的数量 有向声望度 入链接的数量 * 简单的声望值计算容易被恶意利用 Exercise: 在下面情况下你如何使用一些技巧使得页面有高的评分？ 每个页面的评分=入链接数+出链接数 每个页面的评分=入链接数 * 假设一个浏览者在网页间随机走动 从随机页面开始 每一步都从当前页面上的某个链接以相等概率游走 在系统达到稳态时，每个页面都有一个长期稳态到访率 – 用它作为页面的评分 Pagerank 排名计算方法 1/3 1/3 1/3 * 存在问题 Web到处是死角dead-ends 随机游走会在死角卡住 谈论长期稳态到达率没有意义 ?? * 解决方法：跳转 Teleporting 每一步以10%的概率跳转到一个随机页面 剩余概率 (90%), 从一个随机链接走出 如果没有出链接，停在原地不动 结果 不会在死角卡住 每个页面都有一个长期的稳态访问率 如何来计算这个访问率? * 马尔可夫链Markov chains 马尔可夫链包括n 个状态, 以及n?n 转移概率矩阵 P 每一步在一个状态里 For 1 ? i,j ? n, 矩阵的项 Pij 表明了当在状态i时，j成为下一个状态的概率 i j Pij Pij0 即可 显然,对所有i都有, 马尔可夫链是随机游走的一种数学抽象 * 遍历的马氏链 Ergodic Markov chains 对于遍历的(平稳随机过程中集合的平均值可以由样本的时间平均值来代替) 马尔科夫链，每个状态存在唯一的长期访问率 访问率的长期稳态分布 经历较长时间后，访问每个状态的概率正比于访问率 平稳随机过程并不关心从什么状态开始 * 概率向量 概率行向量 x = (x1, … xn) 表明在任何时间点随机游走在什么状态上 E.g., (000…1…000) 表示在状态 i i n 1 更一般化的讲, 向量 x = (x1, … xn) 表明游走在状态 i上概率为 xi * 概率向量的改变 如果在这一步的概率向量是 x = (x1, … xn) , 下一步应该是什么? 第i行的转移概率矩阵P告诉我们从第i个状态会转移到哪个状态 因此从状态x, 我们的下一个状态分布为 xP * 计算到访率 稳态概率是一个概率的向量 a = (a1, … an) ai 是在状态 i 的概率 1 2 3/4 1/4 3/4 1/4 For this example, a1=1/4 and a2=3/4. * 如何计算稳态到访率向量 令 a = (a1, … an) 代表稳态概率的行向量 如果当前状态是 a, 那下一个状态就是 aP 由于a是稳态, 因此有 a=aP 解此矩阵等式可得a a 是P的左特征向量 * 一种计算 a 的方法 由于无论从什么位置出发，最终都能够到达稳定状态 a，因此可以从任何分布开始计算 (例如 x=(10…0)) 一步以后，可得到 xP; 两步以后得到 xP2 , 然后是 xP3 如此下去. 最终当k取比较大的值的时候, xPk = a. 算法：将 x 与 P 的k次幂相乘，k不断变大直到相乘结果看上去达到稳定. * 一个稍微复杂的例子 Page ID Outlinks 1