搜索引擎技术基础 主讲：于俊清
1 内容提要 搜索引擎的前世今生商用搜索引擎结构与组成搜索引擎质量评估搜索引擎排序策略 分布式搜索引擎
2 搜索引擎的排序策略 用户的浏览行为 F现象 排序策略 将用户最想要的网页放在前面 有哪些因素可以影响网页的排序？
3 搜索引擎的排序算法 文本信息检索模型 布尔模型向量空间模型概率模型语言模型
4 搜索引擎的排序算法 链接分析排序 HITS算法PageRank算法算法 其他提升网页排序的方法
5 文本信息检索模型 文档和查询词差异在于如何定义和计算文档与检索词之间的关 系
6 1 布尔模型 布尔模型 基于集合论和布尔代数早期搜索引擎使用的检索模型 三个主要逻辑运算符
A B
A B
A B 逻辑与 逻辑或 逻辑与、逻辑或、逻辑非示意图
7 逻辑非 布尔模型 google搜索引擎提供的布尔模型搜索
8 布尔模型 
布尔模型示例 查询词Q=(K1ANDK2)OR(K3NOTK4) 检索步骤 首先，分别检索含有关键词K1、K2、K3和K4的文档集 合，记为C1、C2、C3、C4 K1nDocsK2nDocsK3nDocsK4nDocs Doc1Doc1Doc1Doc1
9 Doc2Doc2Doc2 Doc3Doc3 Doc4 布尔模型 检索步骤（续） 然后通过集合的布尔运算C=(C1ANDC2)OR(C3NOTC4) 最终得到该检索词的返回文档集合
C，运算过程如下 布尔表达式C1ANDC2C3NOTC4(C1ANDC2)OR(C3NOTC4) 页面{Doc1,Doc2}{Doc2,Doc3}{Doc1,Doc2,Doc3} 最终返回文档集合{Doc1,Doc2,Doc3} 10 布尔模型 特点 是一种精确匹配的检索模型返回只有两种状态，难以排序用户使用门槛高 11 向量空间模型 提出 Salton CommunicationsoftheACM,1975 基本思想
B 事物由原子性基本单元构成 Doc 词项作为原子单元 ɑ Query
A C 向量空间模型示例 12
2 向量空间模型 网页文本表示为如下n维向量： D(w,w,,w) i i1i2 in wij表示该文档在第j个词项上的权重 包含d个页面的集合可以表示为一个矩阵： Term1Term2 Termn Doc1 w11 w12 w1n Doc2 Docd ww21 22  wwd1 d2 w2n wdn 13 向量空间模型 利用空间向量模型度量两个文本之间的相似度 两个文档分别表示为 D(w,w,,w)
1 1112 1n D2(w21,w22,,w2n) 内积相似度可表示为 n Sim(D1,D2)w1,k·w2,k k
1 问题：内积相似度度量更偏向于较长的文档——改进？ 比内积相似度更有效的相似度度量——余弦相似度 14 向量空间模型 余弦相似度Sim(D1,D2)cos w·wn1,k2,kk
1 (w)(w)n21,kk
1 n22,k k
1 与内积相似度的不同：它对内积相似度进行了归一化 通过归一化避免文档长度对相似度度量的影响 对于文档D和查询词
Q，其余弦相似度为： Sim(
D,Q) w·wn D,k Q,k k
1 (w)(w)n k
1 2D,k nk
1 2Q,k 15 向量空间模型 关键词与文档之间的相关度用关键词出现的次数（频率）度量——TF（TermFrequence） 频率越高越重要 某个词项k在文档Di中的TF值即该词项出现次数除以该文档的长度（所有词的个数）： TFiktcikcij j1 cik表示词项k在Di中的出现次数 16 向量空间模型 大量文档中，关键词出现的次数越少，其重要性越高，权值越大 IDF（Inversedocumentfrequence） 对于词项k中的IDF值计算如下 IDFklogNnk •nk：出现词项k的文档数 •N：集合中的文档数 17 向量空间模型 TF、IDF计算实例对于如下4个文档： d1清华大学是中国著名高等学府d2清华大学的前身是清华学堂d3清华大学面临前所未有的历史机遇d4清华大学跻身世界一流大学行列 18
3 向量空间模型 Term d1 d2 d3 d4 清华
1 2
1 1 TF、IDF计算实例（续）大学1112 中国
1 0
0 0 假设某个词项在文档中的权重是它出 著名
1 0
0 0 高等
1 0
0 0 学府
1 0
0 0 现的次数，则得如 前身
0 1
0 0 学堂
0 1
0 0 图矩阵： 面临
0 0
1 0 前所未有

0 0
1 0 历史
0 0
1 0 机遇
0 0
1 0 跻身
0 0
0 1 世界
0 0
0 1 一流
0 0
0 1 19
行列
0 0
0 1 向量空间模型 TF、IDF计算实例（续）词项“清华”在文档d2中的TF、IDF值： TF2,清华=2/(2+1+1+1)=0.4IDF清华=log(4/4) 词项“面临”在文档d3中的TF、IDF值为： TF3,面临=1/6IDF面临=log(4/1) 20 向量空间模型 TF、IDF应用 如输入搜索词“一流大学”，搜索范围为上述 四个文档d1、d2、d3、d4 将此项分解为“一流”、“大学” 词项“一流”在四个文档中的TF值： TF1,一流=0/6=0TF2,一流=0/4=0TF3,一流=0/6=0TF4,一流=1/7=0.143 21 向量空间模型 TF、IDF应用（续） 词项“大学”在四个文档中的TF值 TF1,大学=1/6=0.167TF2,大学=1/4=0.25TF3,大学=1/6=0.167TF4,大学=2/7=0.286 “一流”、“大学”在四个文档中的IDF值 IDF一流=log(4/0)，IDF大学=log(4/4)=0 22 向量空间模型 TF、IDF分析TF值表示某词项在某一文档中的重要程度，即TF值越大说明该词项越重要IDF值表示某词项在集合文档中的重要程度，一个词项出现的文档数越多，说明该词项的区分度越差，其在文档集合中的重要性就越低 23 向量空间模型 特点 简单，易于实现对网页质量要求较高空间映射问题词项不匹配——解决方案？ 24
4 向量空间模型 链接结构分析 向量空间模型问题解决 万维网链接结构图Graph 充分利用锚文本（anchortext）信息 节点A-H：网页
H •提高网页向量表示的精确性 有向边：网页之间的连接关系
A 根据语义对查询词进行扩展用户先验行为信息积累 BF •对用户整体搜索偏好和热点分析，提高检索实时性•对用户个体检索偏好分析，提高信息检索个性 CE GD 25 26 链接结构分析 万维网链接结构关系 用邻接矩阵M表示，其中某个元素mi,j的取值 满足： 1(i,j)Graph mi,j 0otherwise •注：n为链接结构图Graph的节点规模，则邻接矩 阵M为nn的矩阵 27 链接结构分析 链接结构图Graph的邻接矩阵表示： 01110101 10100000 11010010 M000010000000001000000010 00000001   00000000 28 链接结构分析 万维网的规模 很难给出准确的统计结果 •网页存在形式复杂——静态页面、动态页面（服务器端自动生成的超链接等） 通过实验性万维网语料库相关数据估算 •AltaVista：2.03亿网页，14.66亿链接•ClueWeb09：10.41亿节点，79.44亿链接•SogouT：1.39亿网页，33.4亿链接 节点集合规模在万亿以上 边集合规模约为节点集合规模的几到几十倍 29 链接结构分析 万维网链接图连通情况基本概念 •强连通子图（StronglyConnectedComponent,SCC）•弱连通子图（WeaklyConnectedComponent,WCC） 强、弱连通子图规模分布规律基本相同 •设连通子图的规模为Size，而具有规模Size的连通子图数目Number近似满足 logNumber2.54logSizeC 30
5 链接结构分析 万维网链接图连通情况 指数形式表示 NumberCSize2.54 语料库中词项出现频率与按频率排名的规律 PCi1i ——幂律分布 幂律分布广泛存在于自然科学与社会科学研究中 •地震规模大小的分布、月球表面月坑直径的分布•战争规模的分布、大多数国家姓氏的分布 31 链接结构分析 万维网链接结构图的面貌 “领结”形式的结构（bow-tiestructure）Core：规模最大的强连通子图SCC IN21.2% Core27.7% OUT21.2% Others29.9%32 链接结构分析 万维网链接图入度和出度 反映某节点（网页）被其他节点（网页）链接以及链接到其他节点（网页）的情况•入度为Indegree的网页数目N（Indegree） NIndegreeCIndegree •出度为Outdegree的网页数目N（Outdegree） NOutdegreeCOutdegree •ɑ、ß均为大于零的参数，C与C‘为常数 33 链接结构分析 万维网链接图入度和出度分布情况 (a)入度 (b)出度 34 链接结构分析 万维网链接图入度和出度分布情况（续） 由上图实验数据得：入度与出度分别服从指数为ɑ=2.09与ß=2.72的幂律分布•大部分网页入度出度值低，即高质量网页数目少•出度值小于10的网页数目分布未严格遵循幂律，因网页中均有难以删除的“刚性”超链接 35 链接结构分析 超链接结构分析基础——超链接的两个特性 特性1：内容推荐特性•链接文本检索算法，提高网络信息检索质量•如HITS算法和PageRank算法 特性2：主题相关特性•重复/冗余网页判定算法•如扩散（SpreadingActivity，SA）算法 36
6 链接结构分析 超链接的两个特性（续） 万维网节点间的超链接关系远比上述特性1、2描述的情况复杂的多，如：•导航栏链接：方便并协助用户访问•广告等商业内容传播链接•版权信息、注册信息超链接 37 HITS算法 HITS HITS：Hyperlink-InducedTopicSearch，针对特定主题文档进行链接分析计算 JonKleinberg（CornellUniversity）核心思想：页面质量从如下两方面进行评价 •内容权威度（AuthorityValue）•链接权威度（HubValue）举例•--什么是一篇“好”论文•--哪个城市“重要”38 HITS算法 实施方式 首先，文本搜索过程 选取网络信息检索结果集合
R，将R，R所指向以及指向
R 的网页构成的链接结构图称为
G 对G中每一个节点n，设定器内容权威度A
(0)(n)和链接权 威度H
(0)(n)初始值均为
1 迭代计算，Fork=1,2,
3,…,
N，对G中每一个节点n AHm• (k)n k1i--I操作 min •H(k)nAkmi--O操作 nmi 39 HITS算法 迭代过程 Hb1…SumHbk PageP Ap Hp Af1…SumAfm 迭代结束判断 结果向量A和H收敛，或 达到迭代次数上限
N ——结果向量一定收敛吗？ 40 HITS算法 收敛性说明 设G对应的邻接矩阵为
M，则有： AMHAnHm(k) k1 k imin
T k1 HMAH(k)nAkminmi k k 41 HITS算法 收敛性说明（续） 若代入初始条件HA(1,
1,,1)，假设z(1,
1,,1)，则 AMHMAMMHk  Tk1 TM k1  TM Tk2  MT 
M 
2  k2
A  (
M TM)k
1 1
A  (MTM)k1MT  0
H  (MTM)k1MTz HkMAkMMTHk1MMTMAk1 MMT2Hk2(MMT)k1H1 (MMT)k1MA1(MMT)kH0(MMT)kz 由此知HITS算法的收敛性，A和H分别收敛到对应矩阵 的主特征向量 算法收敛速度与矩阵各个特征值之间的大小关系相关 42
7 HITS算法 HITS算法的缺陷 内容检索算法并非总是格外有效•噪音影响：与主题不相关文档•主题偏移：与主题部分相关文档 运行效率•运算量比PageRank小•准确性高于PageRank算法但需实时进行•Connectivityserver可实现一定程度的在线实时计算，但计算代价过高，难应用于大规模的网页数据集 43 PageRank算法 SergeyBrin、LarryPage（Google）搜索引擎排序算法算法描述 把超链接关系作为一个“投票”动作获得较多投票的网页质量较高入链接个数：直接统计票数，各票等权重PageRank：质量较高的网页投票权重较高“不公平”的“民主决策”过程 44 PageRank算法 PageRank算法运行 定义“网页质量”•HITS：链接权威度与内容权威度•PageRank：用户随机浏览互联网时访问到某个页面的概率大小 估计用户访问某网页的概率•建立用户浏览模型——“随机游走”（randomwalk）模型•随机：浏览起始点及页内超链接选择的随机性 45 PageRank算法 随机浏览模型 网民小刚使用浏览器的收藏夹提供的“随便逛逛”功能进行万维网冲浪（注：该浏览器未设置“地址栏”及“后退”按钮）•小刚使用“随便逛逛”功能挑选一随机起点进行访问，浏览该页面后他可能点击页面上某链接继续访问他感兴趣的内容，也可能使用“随便逛逛”功能跳转到另一网页浏览•浏览中某网页被访问的概率称为该页面的PageRank 46 PageRank算法 网页A的PageRank估算 小刚使用“随便逛逛”跳转到页面
A，则A被访问概率 PA1N--N为互联网上的网页总数
1 浏览中通过其他网页超链接访问到
A，则通过Pi页面访问 到A的概率为：PageRank(P)P(PA) i i 注：P1，…，Pk为链接到A的所有网页PageRank(P)--访问Pi的概率 i P(PA)--访问Pi时点击页面A超链接的概率i PageRank(P)  通过Pi访问到A的概率为: i Outdegree(P) i 47 PageRank算法 网页A的PageRank估算（续） 通过P1，…，Pk这k个页面访问到A的概率 k  PageRank(Pi)或  PageRank(P)i i1Outdegree(P)PiAOutdegree(P) i i 综上：设小刚主动使用“随便逛逛”功能的概率为ɑ，则 页面A被访问的概率为 PageRank(A)
1 (1)  PageRank(P)i
N PiAOutdegree(P) i 48
8 PageRank算法 网页A的PR值计算实例 如/seo的PR=4，/seo只有1个链接，并且链接到
A，则PR(A)0.15(1-0.15)*(4/1)0.150.85*43.55 如/seo有2个链接，并且链接到
A，则 PR(A)0.151-0.15*(4/2)0.150.85*21.85 如果10个PR=0的网站链接到
A，则PR(A)0.15(10.15)*(0/N)(10.15)*(0/N)(10.15)*(0/N) 0.1500.15 49 PageRank算法 PageRank简化算法 取万维网链接结构图
G，G的规模为
N，即G中包含N个节点 对G中每个节点n，设其初始PageRank值为 PR(1,
1,,1)NNN Fork=1,
2,…,TN，对G中每个节点n PR(k)(n)1(1) PR(k1)(P)i
N PinOutdegree(P) i 当结果向量PR未收敛时，返回上一步继续循环；收敛时 算法结束，输出G中各节点的PageRank数值PR(n) 50 PageRank算法 PageRank简化算法示例 如右图示链接结构图初值：PR(1,1,1,1),0.2 4444第一次迭代： AB CD PR
(1)(A)0.21(10.2)(PR
(0)(D)Outdegree(D))0.050.810.25
4 4 PR
(1)(B)0.21(10.2)(PR
(0)(A)Outdegree(A))0.050.8110.15
4 42 PR
(1)(C)0.21(10.2)(PR
(0)(A)Outdegree(A))0.050.8110.15
4 42 PR
(1)(D)0.21(10.2)(PR
(0)(B)Outdegree(B))(PR
(0)(C)Outdegree(C))
4 0.050.8(11)0.454451 PageRank算法 PageRank简化算法示例（续） 第二次迭代： PR
(2)(A)0.21(10.2)(PR
(1)(D)Outdegree(D))0.050.80.450.414 PR
(2)(B)0.21(10.2)(PR
(1)(A)Outdegree(A))0.050.8110.15
4 42 PR
(2)(C)0.21(10.2)(PR
(1)(A)Outdegree(A))0.050.8110.15
4 42 PR
(2)(D)0.21(10.2)(PR
(1)(B)Outdegree(B))(PR
(1)(C)Outdegree(C))
4 0.050.8(11)0.4544 52 PageRank算法 详细迭代结果如下PR(A)PR(B)第1次迭代0.25000.2500第2次迭代0.25000.1500第3次迭代0.41000.1500第4次迭代0.28200.2140第5次迭代0.28200.1628…第10次迭代0.30680.1861…第20次迭代0.31440.1758…第30次迭代0.31580.1762…第100次迭代0.31560.1762 PR(C)0.25000.15000.15000.21400.1628 0.1861 0.1758 0.1762 0.176253 PR(D)0.25000.45000.29000.29000.3924 0.3210 0.3341 0.3319 0.3320 i1A,.B,0CP,D0R0(i0)1.00001.00001.00001.0000 1.0000 1.0000 1.0000 1.0000 PageRank算法 PageRank简化算法的问题 有些页面没有超链接•txt，doc，jpg，…•随机浏览进入死胡同•简化算法无法保证迭代过程中的PageRank值之和为
1，算法失效 对简化算法进行改进 54
9 PageRank算法 PageRank标准算法 取万维网链接结构图
G，G的规模为
N，即G中包含N个节点 对G中每个节点n，设其初始PageRank值为PR(1,
1,,1)， NNN 同时设定临时变量I(,,,) NNN Fork=1,
2,…,
M，对G中每个节点n •若Outdegree(n)>
0，则有 P,ifn
P,I(P)I(P)(1)PR(k1)(n) i i i i Outdegree(n) •若Outdegree(n)=
0，则有 P
G,I(P)I(P)(1)PR(k1)(n) i i i 55
N PageRank算法 PageRank标准算法（续）当结果向量PR未收敛时，返回上一步继续循环；收敛时 算法结束，输出G中各节点的PageRank数值PR(n) 算法效率低 每次遍历节点n时，若n的出度为
0，需对每一个链接图内的节点进行操作 相当于为“死胡同”网页和G中所有网页之间添加了一条虚拟的出链接 改进邻接矩阵56 PageRank算法 改进邻接矩阵 原始邻接矩阵M改进邻接矩阵
A 1(i,j)Graphmi,j 0otherwise 1aji,jai,j1n
0 (i,j)Gai,j0 j otherwise 57 PageRank算法 基于改进邻接矩阵的算法描述 依照上述改进邻接矩阵的定义，则标准PageRank算法的迭代过程可表示为（其中I(1,
1,,1)）: (k) PR  
1 (1)ATPR(k1)
N 存在问题•A为稀疏矩阵，传统矩阵运算空间消耗巨大•用稀疏矩阵加速算法来改善运算 58 PageRank算法 PageRank加速算法 输入：万维网链接结构图G（节点规模为N）的链接关系特征文件
D，参数ɑ，迭代次数M•D：只记录改进邻接矩阵中的非零元素 输出：G对应的各节点的PageRank数值PR临时变量：I（每个节点的PageRank值） S（无出链接节点的PageRank值之和） 59 PageRank算法 PageRank加速算法（续1） 
1.遍历文件
D，对于D记录的每条链接关系E(i,j): Outdegree(i)Outdegree(i)
1 
2.Forn=1,
2,…,
N，PR
(0)(n)
1,I(n)
N N •若Outdegree(n)=
0，则 S
(1)S
(1)PR
(0)(n) 60 10 PageRank算法 PageRank加速算法（续2） 
3.Fork=1,
2,…,
M •遍历文件
D，对于D中每一条链接关系E(i,j)： I(j)I(j)(1)PR(k1)(i)Outdegree(i) •Forn=1,
2,…,
N PR(k)(n)I(n)(1)S(k),I(n)
N n •若Outdegree(i)=
0，则有 S(k1)S(k1)PR(k)(i) 61 PageRank算法 PageRank加速算法（续） 需要进行的遍历次数 (M1)(NL) •M：迭代次数；N：节点规模；L：链接规模需存储的内容 •与N规模相关的PR•临时变量I 62 PageRank算法 PageRank局限性 在真实应用环境中未获巨大成功•Upstill：在链接分析方法使用较多的主页查找任务中，PageRank算法及其变形只比纯内容检索略好•Amento：小规模数据中PageRank/HITS均无法有效提高纯文本检索的效果•实验研究：PageRank在TREC大规模检索数据时失效 原因•网络数据的繁杂导致的数据规模、数据质量问题 63 PageRank算法 PageRank困境 网站域名 PageRank得分排名 1234567891064 给出的流量排名 1391655 21391062 1179 8342 PageRank算法 PageRank困境（续1） 根据SougoT语料库中PageRank得分最高的10个站点及其对应的Alexa流量排名情况，PageRank得分与受用户欢迎程度（以访问量衡量）的一致性比较：•部分网站用户访问量排名与其PageRank得分不符•部分网站在万维网链接结构中为了符合相关法律法规的要求或者为了网页读者浏览的便利而被推荐处于重要位置，却不为用户所关注，如网站：、、等 65 PageRank算法 PageRank困境（续2） •大量无意义、低质量乃至垃圾链接严重影响其页面质量评估的效果 使链接结构分析算法同样适合于真实万维网环境•使用用户浏览信息对万维网链接结构信息进行过滤和清理，使之真正反映用户的互联网访问情况 66 11 其他提升网页排序的方法 锚文本（AnchorText） 即链接文本可作为其所在页面内容的评估精确描述其所指向页面的内容收集一些搜索引擎不能索引的文件网页中合适的锚文本会增加所在网页和所指向网页的 重要程度 67 其他提升网页排序的方法 页面版式 包括标题、文字、标签等搜索引擎利用这些版式来识别搜索词与页面内容的相 关程度合理利用网页的页面版式，可提升网页在搜索结果页 的排序位置 68 其他提升网页排序的方法 收费排名 不属于排序技术搜索引擎的盈利模式——直接影响搜索引擎的排序给企业带来访问量——对于企业来说，是提升网站在 搜索引擎中排名的最直接和最简单的办法对访问者有一定好处，但更多的是不真实排序失去公正性，甚至带来大量垃圾 69 搜索引擎存在的问题 没有真正解决相关性问题 没有出现查询词的网页就不是用户需要的网页？ 搜索结果的单一化 检索结果的排序应该更加个性化：根据用户的不同产生不同的排序结果 70 课后作业 问题1：按照搜索引擎的排序策略，如何生成垃圾网页以提高排序时pr值？ 问题2：搜索引擎如何处理垃圾网页？ 71 12