WEB挖掘算法介绍.

Presentation on theme: "WEB挖掘算法介绍."— Presentation transcript:

1 WEB挖掘算法介绍

2 内容提要 WEB结构挖掘： 独立于查询的算法-PageRank 查询相关算法-HITS …...

3 PageRank算法 背景介绍 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank的计算

4 背景介绍 Web上超链接结构是个非常丰富和重要的资源，如果能够充分利用的话， 可以极大的提高检索结果的质量。
Sergey Brin(谢尔盖·布林 )和Lawrence Page(拉里·佩奇)在1998年提出 了PageRank算法，同年J. Kleinberg（J·克莱因伯格）提出了HITS算法 Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998, 为了更高效地计算 PageRank,以下是改良以后的一篇论文。Taher H. Haveliwala, ‘Efficient Computation of PageRank’, Stanford Technical Report, 1999,

5 Pagerank 创始人：拉里 佩奇(Larry Page ) 应 用：Google是用来衡量一个网站 好坏的唯一标准。
谢尔盖·布林(Sergey Brin) 应 用：Google是用来衡量一个网站 好坏的唯一标准。

6 PageRank的提出 Google的创始人之一Larry Page于1998年提出了 PageRank，并应用在Google搜索引擎的检索结果排序 上，该技术也是Google早期的核心技术之一 Larry Page是Google的创始首席执行官，2001年4月转 任现职产品总裁。他目前仍与Eric Schmidt和Sergey Brin一起共同负责 Google的日常运作。他在斯坦福大 学攻读计算机科学博士学位期间，遇到了Sergey Brin， 他们于1998年合伙创立Google。 PageRank(TM) 是美国 Google 公司的登记注册商标。 基于以上的一些朴素的想法，Google的创始人Page提出了PageRank，并应用 在Google搜索引擎的检索结果排序上，作为早期Google的核心技术之一 6

7 Google查询过程 Google 查询的全过程通常 不超过半秒时间，但在这 短短的时间内需要完成多 个步骤，然后才能将搜索 结果交付给搜索信息的用 户。 PageRank?

8 PageRank算法 背景介绍 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank的计算

9 Google的网页排序 在Google中搜索“体育新闻” 9

10 Google的网页排序 在Google中搜索“体育新闻” 搜索引擎工作的简要过程如下 针对查询词“体育新闻”进行分词——“体育”、“新闻”
查询词和文档的相关性 在Google中搜索“体育新闻” 搜索引擎工作的简要过程如下 针对查询词“体育新闻”进行分词——“体育”、“新闻” 根据建立的倒排索引，将同时包含“体育”和“新闻”的文档返回，并根据相关性进行排序 这里的相关性主要是基于内容的相关性 但是会有一些垃圾网页，虽然也包含大量的查询词，但却并 非满足用户需要的文档，一个网页中虽然出现了四次“体育 新闻”但却不是用户所需要的 因此，页面本身的重要性在网页排序中也起着很重要的作用 基于内容的相关性，简单地说是指，比如某篇文档出现了多次“体育新闻”， 就比只出现一次“体育新闻”的文档与query的相关性高，目前的相关性排序， 已经不再是简单地基于词匹配，还会根据topic，比如大量出现“足球”、“乒 乓球”等词语的文档同样相当于大量出现了“体育” 10

11 Google的网页排序 在Google中搜索“体育新闻” 11

12 Google的网页排序 如何度量网页本身的重要性呢？ 互联网上的每一篇html文档除了包含文本、图片、视频等信息外，还包含了大量的链接关系，利用这些链接关系，能够发现某些重要的网页 直观地看，某网页A链向网页B，则可以认为网页A觉得网 页B有链接价值，是比较重要的网页。 某网页被指向的次数越多，则它的重要性越高；越是重要 的网页，所链接的网页的重要性也越高。 网页是节点，网页 间的链接关系是边 A B 因此，除了基于相关性的排序外，还有一种基于重要性的排序，也被引入了搜 索引擎中 12

13 Google的网页排序 如何度量网页本身的重要性呢？
比如，新华网体育在其首页中对新浪体育做了链接， 人民网体育同样在其首页中对新浪体育做了链接 可见，新浪体育被链接的次数较多；同时，人民网体 育和新华网体育也都是比较“重要”的网页，因此新 浪体育也应该是比较“重要”的网页。 人民网体育 新华网体育 网页A的重要性，应该等于所有链向A的网页的重要性除以该网页的链接数之后 再求和 13

14 Google的网页排序 一个更加形象的图 链向网页E的链接远 远多于链向网页C的 链接，但是网页C的 重要性却大于网页 E。这是因为因为网 页C被网页B所链接， 而网页B有很高的重 要性。 一个更加形象的图 14

15 Http网页链接示意图

16 PageRank算法 背景介绍 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank的计算

17 什么是PageRank PageRank是一种在搜索引擎中根据网页之间相互的链 接关系计算网页排名的技术。
PageRank是Google用来标识网页的等级或重要性的一 种方法。其级别从1到10级，PR值越高说明该网页越受欢 迎（越重要）。 PageRank近似于一个用户，是指在Internet上随机地 单击链接将会到达特定网页的可能性。通常，能够从更多 地方到达的网页更为重要，因此具有更高的PageRank。 虽然今天的搜索引擎的排名系统远远要比这个算法复杂。 域名数据，内容质量，用户数据，建站时间等都可能被考 虑进去，但是page rank算法仍然是核心的技术之一。

18 Pagerank算法原理：

19 PageRank 的核心思想 PageRank 是基于「从许多优质的网页链接过来的网页，必定还是优质网页」的
回归关系，来判定所有网页的重要性。 因此，如果从类似于 Yahoo! 那样的 PageRank 非常高的站点被链接的话，仅此网页的 PageRank 也会一下子上升；相反地，无论有多少链入链接数，如果全都是从那些没有多大意义的页面链接过来的话，PageRank 也不会轻易上升。 链入链接数 (单纯的意义上的受欢迎度指标) 链入链接是否来自推荐度高的页面 (有根据的受欢迎指标) 链入链接源页面的链接数 (被选中的几率指标)

20 PageRank简单计算： 假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面 都链向A，那么A的PR（PageRank）值将是B，C及D的和。 继续假设B也有链接到C，并且D也有链接到包括A的3个页面。一个 页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的 票只有三分之一算到了A的PageRank上。 换句话说，根据链出总数平分一个页面的PR值。

21 PageRank的简单计算过程

22 PageRank的简化模型 可以把互联网上的各网页之间的链接关系看成一个有向 图。假设冲浪者浏览的下一个网页链接来自于当前网页。 建立简化模型：对于任意网页Pi，它的PageRank值可表 示为如下：其中Bi为所有链接到网页i的网页集合，Lj为 网页j的对外链接数（出度）。

23 简化模型面临的缺陷 实际的网络超链接环境没有这么理想化， PageRank会面临两个问题： Rank leak（遗漏）
Rank sink（汇点） 在google的搜索结果中，PR值越高的网页排在越前面。网页权重的算法有很多种，而page rank是Google搜索引擎采用的搜索结果排名算法之核心，且它把整个互联网当做一个整体来对待且最终依靠经典的数学模型精准地得到web上网页的权重。

24 Rank Leak Rank leak：一个独立的网页如果没有外出的链接就产生等级泄漏 解决办法：
PR(A) PR(B) PR(C) PR(D) 初始 0.25 一次迭代 0.125 二次迭代 三次迭代 … n次迭代 Rank leak：一个独立的网页如果没有外出的链接就产生等级泄漏 解决办法： 1.将无出度的节点递归地从图中去掉，待其他节点计算完毕后再加上 2.对无出度的节点添加一条边，指向那些指向它的顶点

25 Rank Sink Rank sink：整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生Rank sink。 PR(A)
PR(B) PR(C) PR(D) 初始 0.25 一次迭代 0.375 二次迭代 三次迭代 四次迭代 五次迭代 … Rank sink：整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生Rank sink。

26 PageRank算法 背景介绍 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank的计算

27 PageRank的随机浏览模型 假定随机地从一个网页开始浏览，上网者不断点击 当前网页的链接开始下一次浏览。但是，上网者最终厌 倦了，开始了一个随机的网页。随机上网者用以上方式 访问一个新网页的概率就等于这个网页PageRank值。 ① 这种随机模型更加接近于用户的浏览行为； ② 一定程度上解决了rank leak和rank sink的问题； ③ 保证pagerank具有唯一值。

28 随机浏览模型的图表示 设定任意两个顶点之间都有直接通路，在每个顶点处以概率d按原来蓝色方向转移，以概率1-d按红色方向转移。

29 随机浏览模型的邻接表表示 由于网页数目巨大，网页之间的连接关系的邻接矩阵是一个很 大的稀疏矩阵,采用邻接表来表示网页之间的连接关系.随机浏览模 型的PageRank公式： N: 网络中网页总数 d: 阻尼因子，通常设为0.85,d即按照超链接进行浏览的概率； 1-d：随机跳转一个新网页的概率 PR(pj):网页pj的PR值 L(pj)：网页pj的链出网页数 一个页面的PageRank是由其他页面的PageRank计算到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），由于等式PR=A*PR满足马尔可夫链的性质，如果马尔可夫链收敛，则PR存在唯一解.通过迭代计算得到所有节点的PageRank值。那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。

30 马尔可夫链收敛定理

31 改进 Larry Page和Sergey Brin 两人从理论上证明了 不论初始值如何选取，这种算法都保证了网页排名的估 计值能收敛到他们的真实值。 由于互联网上网页的数量是巨大的，上面提到的二 维矩阵从理论上讲有网页数目平方之多个元素。如果我 们假定有十亿个网页，那么这个矩阵就有一百亿亿个元 素。这样大的矩阵相乘，计算量是非常大的。Larry Page和Sergey Brin两人利用稀疏矩阵计算的技巧，大 大的简化了计算量。

32 PageRank算法 背景介绍 Google的网页排序 PageRank简化模型 PageRank随机浏览模型 PageRank的计算

33 PageRank的计算 互联网是一个有向图 每一个网页是图的一个顶点 网页间的每一个超链接是图的一个有向边
用邻接矩阵来表示图，即：定义邻接矩阵为G，若网页j到网页i有超链接，则 ；反之 。 显然，如果网页有N 个，则矩阵为N×N 的0、1方阵。

34 多个网页相互链接的图对应的邻接矩阵（这里将0,1值用二值图像显示，黑色代表0，白色代表1）

35 PageRank的计算 定义邻接矩阵为G，若网页j到网页i有超链接，则 ；反之， 。 记矩阵G的列和、行和分别是

36 PageRank的计算 假设我们在上网的时侯浏览页面并选择下一个页面，这个过程与过去浏览过哪些页面无关，而仅依赖于当前所在的页面，那么这一选择过程可以认为是一个有限状态、离散时间的随机过程，其状态转移规律用Markov链描述。 定义转移概率矩阵

37 PageRank的计算 根据Markov链的基本性质，对于正则Markov链，存在平稳分布 ，满足 求矩阵A的特征值1对应的特征向量
表示在极限状态（转移次数趋于无限）下各网页被访问的概率分布。 定义为网页的PageRank向量， 表示第i个网页的PageRank值 求矩阵A的特征值1对应的特征向量

38 某7个网页之间的链接关系图

39 网页链接图的邻接矩阵 G =

40 PageRank的计算 状态转移概率矩阵A 0 1 1/2 0 1/4 1/2 0 1/5 0 1/2 1/3 0 0 0
/ /4 1/2 0 1/5 0 1/2 1/ 1/ /3 1/ 1/ / 1/ / /2 1 / 1/ A =

41 PageRank的计算 求矩阵A特征值1对应的特征向量 0.699456533837389 0.303514376996805
归一化

42 7个网页的PageRank值

43 PageRank结果的评价 将 PageRank 的评价按顺序排列(PageRank 小数点3位四舍五入):

44 页面之间相互关系及状态转移图

45 PageRank结果的评价 ID=1 的页面的PageRank 是0.304，占据全体的三分之一，成为 了第1位。
特别需要说明的是，起到相当大效果的是从排在第3位的 ID=2 页面中得到了所有的PageRank (0.166) 数。ID=2页面有从3个 地方过来的链入链接，而只有面向 ID=1页面的一个链接，因此 (面向ID=1页面的)链接就得到ID=2的所有的PageRank数。 因为ID=1页面是链出链接和链入链接最多的页面，也可以理解 它是最受欢迎的页面。

46 PageRank结果的评价 反过来，最后一名的 ID=6 页面只有 ID=1 的15％的 微弱评价。

47 PageRank数值计算难点（一） 计算机容量限制
假设 N 是 104 的 order。通常，数值计算 程序内部行列和矢量是用双精度记录的，N 次正方行列 A 的记忆领域为 sizeof(double)* N * N =8 *104 * 104＝ 800MB。N 如果变成 105 或106 的话，就变成 80GB, 8TB。这样的话不用说内存就连硬盘也 已经很困难了。目前，Google处理着80亿以 上的页面，很显然，已知的这种做法已经完 全不适用了。

48 PageRank数值计算难点（二） 收敛问题
然而，常用的迭代求解方法会导致收敛速度很慢。

49 PageRank算法的应用 学术论文的重要性排序 学术论文的作者的重要性排序 网络爬虫(Web Crawler)
某作者引用了其它作者的文献，则该作者认为其它作 者是“重要”的。 网络爬虫(Web Crawler) 可以利用PR值，决定某个URL，所需要抓取的网页数量 和深度 重要性高的网页抓取的页面数量相对多一些，反之， 则少一些 关键词与句子的抽取（节点与边） 关于引用分析的研究要比链接分析早得多 49

50 PageRank PageRank的大小取决于三个因素： 链入网页数 链入网页的质量 链入网页的链出网页数

51 PageRank 2.5 2.5 2.5 2.5 给定初始PageRank值： (5, 0, 0) 1.25 1.25 1 1.25
B A B A B 2.5 2.5 C C 2.5 C 给定初始PageRank值： (5, 0, 0) 第1次迭代，PageRank值： (0, 2.5, 2.5) 第2次迭代，PageRank值： (2.5, 0, 2.5) 1.25 A B A 1.25 B A 1 B 1.25 1.25 1.25 1 1 2.5 C 1.25 C 2 C 第3次迭代，PageRank值： (2.5, 1.25, 1.25) 第4次迭代，PageRank值： (1.25, 1.25, 2.5) 第30次迭代，PageRank值： (2, 1, 2)

52 PageRank 经过30次迭代后，PageRank值趋向稳定， 经过归一化处理，得到最终结果（0.4, 0.2, 0.4） 0.2 0.2
B 0.2 0.2 0.4 C 第30次迭代，PageRank值： (0.4, 0.2, 0.4)

53 PageRank 的问题 PageRank算法中对于向外链接的权值贡献 是平均的，不考虑不同链接的重要性。
1.有些链接具有注释性，也有些链接是起导航或广告 作用。有注释性的链接才用于权威判断。 2.基于商业或竞争因素考虑，很少有WEB网页指向其 竞争领域的权威网页。 3.权威网页很少具有显式的描述，比如Google主页 不会明确给出WEB搜索引擎之类的描述信息. 53

54 pagerank小结 优点： 是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获 得；有效减少在线查询时的计算量，极大降低了查询响应时间。 PageRank的缺点 过分相信链接关系 一些权威网页往往是相互不链接的，比如新浪、搜狐、网易以及腾讯 这些大的门户之间，基本是不相互链接的，学术领域也是这样。 1）人们的查询具有主题特征，PageRank忽略了主题相关性，导致结 果的相关性和主题性降低 2）旧的页面等级会比新页面高。因为即使是非常好的新页面也不会 有很多上游链接，除非它是某个站点的子站点。 排序技术是搜索引擎的绝密 Google目前所使用的排序技术，已经不再是简单的PageRank

55 页面重要性的评价方法 在设计搜索引擎等服务时，对Web页面的链接结构进行挖掘以得出有用的知识是提高检索效率的重要手段。Web页面的链接类似学术上的引用，因此一个重要的页面可能会有很多页面的链接指向它。 定义7-3 设u为一个Web页，Fu为所有u指向的页面的集合，Bu为所有指向u的页面的集合。设Nu= |Fu|为从u发出的链接的个数，c（<1）为一个归一化的因子（因此所有页面的总的PageRank为一个常数），那么u页面的PageRank被定义为： 一个页面对应的PageRank值被分配到所有它所指向的页面中；每一个页面求和所有指向它的链接所带来的PageRank以得到它的新的PageRank。在计算时可以从任何一个页面开始，通过上面的公式反复计算直到其收敛。

56 页面等级 一般地说，页面的页面等级值是通过指向这个页面的数量来计算的，即通过指向向后连接数来计算的。向后连接是指向这个页面的连接减去它指向外面的连接。计算量不是简单地向后连接的数量加合，而是要考虑向后连接的页面的重要性。 给定一个页面p，我们使用Bp作为指向一系列指向P的页面，并且用Fp作为一系列由外部指向P的连接，则 这里的Nq=|Fq|。常量c是一个介于0，1之间的数，用于标准化。 这里有一个循环分级的问题。当计算一个页面的页面等级时，如果发生循环则产生这个错误（页面A指向页面B，页面B同时指向页面A），此时页面等级值随这些页面增加。可以通过另一个公式解决： 其中c是最大值，E(v)是一个矢量来增加一个人工连接。它是模拟一个用户不随着连接访问其他页面，而是随机跳到一个新的页面。E(v)增加一对结点中间可能的连接。

57 权威页面和中心页面 所谓权威页面是指包含需求信息的最佳资源页面。所谓中心页面是一 个包含权威页面连接的页面。
HITS（Hyperlink-Induced Topic Search）是遵照寻找权威页面和中 心页面的典型方法。HITS技术由两部分组成： 基于一组给定的关键字，可以找到相关的页面。 权威和中心页面与上述页面有关，返回具有最高权重的页面。 算法7-3 HITS 输入： （把www 看作）一个引导图W；查询请求q；支持s。 输出：权威页面的集合A；中心页面的集合H。 （1）BEGIN （2） R=SE(W, q)；//利用q得到页面的根集合R （3） B= R  {指向R的连接}{来自R的连接}； （4） G(B, L)= 由B导出的W的子图； （5） G(B, L1)=删除G中相同站点的连接； （6） xp=∑q Yq；// <q,p>∈L1，得到权威页面的权重； （7） yp=∑q Xq；// < q,p >∈L1 ，得到中心页面的权重； （8） A={p|p为具有最高xp值的页面}； （9） H={p|p为具有最高yp值的页面}； （10）END

58 Web访问信息的一些概念(一) W3C国际组织已经为Web访问信息定义了一些基本概念：
定义7-4 用户（User）：用户被定义为一个通过浏览器访问一个或者多个 Web服务器的访问者。一个用户可以通过几台PC机或者使用多个浏览器 来访问，因此识别用户是任务之一。 定义7-5 页面文件（Page File）：一个页面文件是通过HTTP请求发给用 户的文件。页面文件有静态和动态，动态页面文件由Web服务器动态生 成响应用户的请求。 定义7-6 页面视图（Page View）：一个页面视图由一个集合的页面文件 组成，页面视图通常与一个用户的行为相关（如一次鼠标点击）。由框 架（frame）、图片、和script等组成。 定义7-7 客户端浏览器（Client Browser）：是指具有一个独立IP地址的 ，用户通过其访问Web服务器的浏览器软件。客户端包括代理服务器软 件。 定义7-8 Web服务器（Web Server）：是指运行在互联网服务提供方主 机上的WWW服务软件，目的是响应客户端发来的HTTP请求。

59 Web访问信息的一些概念（二 ） 定义7-9 点击流（Click Stream）：亦称连续HTTP请求序列。
定义7-10 一次访问用户（One User at a Time）：是指某一个通 过一个客户端浏览器发出连续HTTP请求序列的对一个Web服务器 进行访问的访问者。如果一个真实的用户每隔一段较长的时间对 一个Web服务器发出一个连续HTTP请求序列，那么对该Web服务 器而言就有多个一次访问用户进行了访问。 定义7-11 用户访问会话（User Session）：是指由一个用户发出 的对Web世界的一次连续HTTP请求序列。 定义7-12 服务器用户访问会话（Server Session）：简称用户访 问事务（User Transaction）是指一次访问用户的对一个Web服务 器的一次访问。由该一次访问用户所请求的页面序列顺序组成。 定义7-13 访问片断（Episode）：任何有意义的用户访问会话或 用户访问事务的子集，被称为访问片断。

60 Web站点的结构的对象描述 一个Web站点的拓扑结构M ： 其中P为所有页面视图Page_View的集合：
一个页面视图Page_View由一组框架Frame组成： 每个框架由一个页面文件组成： LpageLink为所有页面的链接的集合： LpageViewLink为全部页面视图之间超链关系的集合：

61 Web站点结构的预处理 通过相应的搜索算法对Web网站进行遍历以找到PageLink， PageViewSet，PageViewLink的集合。 算法7-4：生成PageViewSet和PageViewLink算法 算法7-4 GPVS（Generating Page View Set） 输入： index.htm。 输出： PageViewSet， PageViewLinkSet。 （1）PageViewSet← GetFirstPageVeiw(/index.htm)； （2）PageViewLinkSet←NULL； （3）FOR each pageview  PageViewSet DO BEIGIN （4） PageSet← GetAllPage(pageview)； （5） FOR each p  PageSet DO BEIGIN//每个pageview由一些页面组成 （6） LinkSet← GetAllHyperLink(p)； （7） FOR each lLinkSet DO BEIGIN //l必须为站点内的地址 （8） newpageview← Substitute(pageview， l)；//根据超链得到一个新的pageview （9） PageViewSet← PageViewSet  {newpageview}； （10） PageViewLinkSet←PageViewLinkSet{<pageview，newpageview>}； （11） END （12） END （13）END. // PageViewSet 集合增量递增，每次从PageViewSet集合中变量pageview只取新的值

62 HITS算法 权威页面(Authority)是指那些与给定查询的上下文最为相关 并且具有权威性的页面。 中心页面(Hub)是指那些本身的内容未必具有权威性，但却 包含了多个指向权威网页的超链接结构: Good hub: page that points to many good authorities. Good authority: page pointed to by many good hubs. Given Keyword Query, assign a hub and an authoritative value to each page. Pages with high authority are results of query 62

63 HITS算法 HITS算法的求解过程如下： v w1 u1 w2 A H u2 ... ... wk uk 1、得出根集页面．
3、根据公式计算新一轮的H和A的值。 4、规范化结果 5、重复3、4, 直到结果收敛。 v w1 u1 w2 A H u2 ... ... wk uk 63

64 Hubs & Authorities Calculation
Iterative algorithm on Base Set: authority weights a(p), and hub weights h(p). Set authority weights a(p) = 1, and hub weights h(p) = 1 for all p. Repeat following two operations (and then re-normalize a and h to have unit norm): a(v1) h(v1) v1 v1 h(v2) v2 p p v2 a(v2) h(v3) v3 v3 a(v3) 64

65 HITS算法的问题 计算量比PageRank算法大。
有些时候，一主机A上的很多文档可能指向另外 一台主机B上的某个文档，这就增加了A上文档的Hub值和 B上文档的Authority，相反的情况也如此。HITS是假定 某一文档的权威值是由不同的单个组织或者个人决定的， 上述情况影响了A和B上文档的Hub和Authority。 网页中一些无关的链接影响A，H值的计算。 HITS算法最大的弱点是处理不好主题漂移问 题（topic drift），也就是紧密链接（TKC, Tightly- Knit Community Effect）现象。如果在基础集合T中有 少数与查询主题无关的网页，但是他们是紧密链接的， HITS算法的结果可能就偏离了原来的查询主题。 65