第四、五章图论和网络爬虫+网络搜索

第四章 图论和网络爬虫

4.1 构建网络爬虫工程重点

• 构建网络爬虫的重点

  1. 用BFS还是DFS

     在不考虑时间的情况下，这两种不同的搜索方法都可以在相同的时间下爬下整个静态的互联网内容，但是在现实中肯定是需要考虑时间以及互联网动态变化的。所以重点应该是如何在有限时间里最多的爬下最重要的网页，类似BFS。

     考虑爬虫的分布式结构，一个大的网络爬虫可能有成千上万台服务器组成的分布式系统，这些服务器下载完一个网站后再进入另一个网站，而不是每个网络先下载5%，在回头继续第二批，这样可以避免握手（下载服务器和网络服务器建立通信的过程）次数过多，类似DFS。

     所以并不是单纯的BFS或者DFS，而是有相对复杂的下载优先级排序方法（调度系统）。

  2. 页面分析和URL提取

     当一个网站下载后，需要提取url，加入下载队列。

  3. 记录哪个网页已经下载过-URL表

     在互联网上一个网页可能会被多个网页的超链接指向，所以在遍历时可能被多次访问，为了避免一个网页被下载多次，可以使用哈希表记录那些网

     页已经被下载过。采用哈希表的好处是，判断url是否在表中，平均只需一次（或者略多）查找。遇到未下载的网页，除了下载该网页，还要适当将这个网页的URL存入哈希表中。如果有成千上万服务器下载网页，存储这个哈希表的服务器的通信就是整个爬虫系统的瓶颈了。

• 总结：

  因为在现实生活中图的规模都是在几千个节点以内，比如公路图，铁路图等，图的遍历比较简单，所以在图论出现后的很长时间内，即使是计算机专业的学生也体会不到这个领域的研究有什么实际用处。但是随着互联网的出现，图的遍历方法一下子有了用武之地，很多数学方法如布尔代数，布尔运算等都是这样

---

第五章 网络搜索

5.1 pagerank算法(度量网页质量)

• pagerank算法中心思想

  如果一个网页被很多网页所连接，说明它收到普遍的承认和信赖，那么它的排名就高；排名高的网页的链接更可靠，需要区别对待，给予更大的权重，即网页排名高的网站贡献的链接权重大。

• 计算网页排名的过程中需要用到网页自己的排名，布林假定所有网页排名相同，使用二维矩阵想乘并迭代计算的方法。

• 假定向量
  $$\mathbf{B}={\left(b_1,b_2,\cdots ,b_N\right)}^{\top }$$

  为第一、第二……第 $N$ 个网页的网页排名。知阵
  $$A=\left[\begin{array}{ccccc}{a}_{11}& \cdots & a_{1n}& \cdots & a_{1M}\\ \cdots & & & & \cdots \\ a_{m1}& \cdots & a_{mn}& \cdots & a_{mM}\\ \cdots & & & & \cdots \\ a_{M1}& \cdots & a_{Mn}& \cdots & a_{MM}\end{array}\right]$$

  为网页之间链接的数目. 其中 $a_{mn}$ 代表第 $n$ 个网页指问第 $m$ 个网页的链接数。 $A$ 是已知的, $B$ 是末知的, 是我们所要计算的。

  初始假设：所有网页的排名都是 $1/N$, 即
  $${\mathbf{B}}_0=\left(\frac{1}{N},\frac{1}{N},\cdots ,\frac{1}{N}\right)\text{ 。 }$$
  假定 $B_i$ 是第 $i$ 论连代的结果，那么
  $${\mathbf{B}}_i=\mathbf{A}\cdot {\mathbf{B}}_{i-1}$$

• 显然通过公式简单 (但是计算量非常大) 的知阵运算, 可以得到 $B_1,B_2,\cdots \cdots$ 可以证明 ${\mathbf{B}}_i$ 最终会收敛, 即 $B_i$ 无限趋近于 $\mathbf{B}$, 此时: $\mathbf{B}=\mathbf{B}\times {\mathbf{A}}_{\pm }$因此. 当两炏㑢代的结果 ${\mathbf{B}}_i$ 和 ${\mathbf{B}}_{i-1}$ 之间的差昇非常小, 接近于零时, 停止迭代运算, 算法结束。一般来进, 只要 10 次左右的造代基本上就收敛了。

  由于网页之间链接的数量相比互联网的规模非常稀疏, 因此计算网页的网页排名也需要对零概率或者小概率事件进行平滑处理。网页的排名是个一维向量, 对它的平清处理只能利用一个小的常数 ${\alpha }_{\mathrm{D}}$ 这时, 公式 (1 变成
  $${\mathbf{B}}_i=\left[\frac{\alpha }{N}\cdot I+(1-\alpha )A\right]\cdot {\mathbf{B}}_{i-1}$$

  其中 $N$ 是互联网网页的数教, $\alpha$ 是一个 (较小的) 常数, $I$ 是单位矩阵。网页排名的计算主要是矩阵相乘, 这种计算很容易分解成许多小任务.在多台计算机上并行处理。

---

5.2 TF-IDF(度量网页与查询相关性)

5.2.1 影响搜索引擎的因素

• 可以归纳为四大类
  1. 完备的索引。俗话说巧姻难为无米之㰠, 如果一个网页不在索引中, 那么再好的算法也找不到。
  2. 对网页质量的度量, 比如 PageRank。当然, 正如在前面一章中介绍的那样, 现在来看, PageRank 的作用比 10 年前已经小了很多，今天对网页质量的衝量是全方位的, 比如对网页内容权威性的度量,一些八卦网站的 PageRank 可能很高, 但是它们的内容权威性很低。
  3. 用户偏好。这一点也很容易理解，因为不同用户的㔛好不同，因此一个好的搜害引繁会针对不同用户, 对相同的搜索给出不同的排名。
  4. 确定一个网页和某个查询的相关性的方法。

5.2.2 TF( Term Frequency：单文本词频)

• 度量网页和某个查询的相关性有个简单的办法，即直接使用各个关键词在网页中出现的总词频。
  $$TF=\frac{\text{关键词出现次数}}{\text{网页总字数}}$$

  如果一个查询包含N个关键词 $w_1,w_2,\cdots ,w_N$, 它们在一个特定网页中的词频分别是: $T{F}_1,T{F}_2,\cdots ,T{F}_N$。那么, 这个直询和该网页的相关性 (即相似度) 就是:
  $$T{F}_1+T{F}_2+.....+T{F}_N$$
  如搜索“原子能的应用”，假设网页总字数1000字，“原子能”出现2次，“的”出现35次，“应用”出现5次，则TF为
  $$0.002+0.035+0.005=0.042$$

  漏洞：

  1. 停止词“的”，对确定网页主题几乎无用，但却占词频80%
  2. “原子能”是个很专业的词，权重应该比“应用”更重要，但是词频却小于应用

• 因此我们需要给汉语中的每个词设置一个权重，每个词的权重应满足

  1. 一个词预测主题的能力越强, 权重越大, 反之, 权重越小。在网页中看到 “原子能” 这个词, 或多或少能了解网页的主题。而看到 “应用”一词, 则对主题基本上还是一无所知。因此, “原子能”的权重就应该比“应用”大。
  2. 停止词的权重为零。

  很容易发现, 如果一个关键词只在很少的网页中出现, 通过它就容易锁定搜索目标, 它的权重也就应该大。反之, 如果一个词在大量网页中出现，看到它仍然不很清楚要找什么内容, 它的权重就应该小。

---

5.2.3 IDF(Inverse Document Frequency：逆文本词频指数)

• 在信息检索中，使用最多的权重就是IDF。嘉定一个关键词$W$在$D_W$个网页中出现过，那么$D_W$越大，$W$权重越小，反之亦然
  $$IDF=\log \frac{D}{D_W}$$
  其中D为所有网页数。

• 所谓IDF的概念为在一个特定条件下关键词的概率分布的交叉熵。

5.2.4 TF-IDF

• TF-IDF 被公认为是信息检索中最重要的发明
  $$TF-IDF=T{F}_1\cdot ID{F}_1+T{F}_2\cdot ID{F}_2+...+T{F}_N\cdot ID{F}_N$$

• 如搜索“原子能的应用”，假设网页总字数1000字，“原子能”出现2次，“的”出现35次，“应用”出现5次，则TF为
  $$\begin{array}{rl}& T{F}_{原子能}=0.002\\ & T{F}_{的}=0.035\\ & T{F}_{应用}=0.005\end{array}$$

  假定中文网页数是 $D=10$ 亿, 停止词 “的”在所有的网页中都出现, 即 $D_w=10$ 亿, 那么它的
  $$ID{F}_{的}=\log (10亿/10亿)=\log (1)=0$$
  假如专用词 “原子能” 在 200 万个网页中出现, 即 $D_w=200$ 万, 则它的权重
  $$ID{F}_{原子能}=\log (500)=8.96$$
  又假定通用词 “应用”出现在五亿个网页中, 它的权重
  $$ID{F}_{应用}=\log (2)=1$$
  , 则只有 1 。也就是说, 在网页中找到一个 “原子能” 的命中率 (Hits) 相当于找到九个 “应用” 的命中率。利用 IDF, 上述相关性计算的公式就由词频的加权求和
  $$\begin{array}{rl}TF-IDF& =T{F}_1\cdot ID{F}_1+T{F}_2\cdot ID{F}_2+...+T{F}_N\cdot ID{F}_N\\ & =T{F}_{原子能}\cdot ID{F}_{原子能}+T{F}_{的}\cdot ID{F}_{的}+T{F}_{应用}\cdot ID{F}_{应用}\\ & =0.002\cdot 8.96+0.035\cdot 0+0.005\cdot 1\\ & =0.01798+0+0.005\\ & =0.02292\end{array}$$
  如果结合网页排名算法如PageRank,那么给定一个查询，有关网页的综合排名大致由相关性和网页排名的乘积决定。

---

5.2.5 TF-IDF的信息论依据

• 后续使用：$w$为关键词，N为整个语料库，D为中文网页数，$D_w$为$w$出现的网页/文献个数，
  $$TF(w)=\frac{\text{关键词w出现次数}}{当前网页/文献总字数}$$

• 一个查询中每一个关键词 $w$ 的权重应该反映这个词对查询来讲提供了多少信息。一个简单的办法就是用每个词的信息量作为它的权重,
  $$\begin{array}{rl}I(w)& =-P(w)\log P(w)\\ & =-\frac{TF(w)}{N}\log \frac{TF(w)}{N}\\ & =\frac{TF(w)}{N}\log \frac{N}{TF(w)}\\ \because & N为常数\\ \therefore & =TF(w)\log \frac{N}{TF(w)}\end{array}$$

  上述公式有一个缺陷：两个词出现的频率 TF 相同, 一个是某篇特定文章中的常见词, 而另外一个词是分散在多篇文章中, 那么显然第一个词有更高的分辨率, 它的权重应该更大。显然, 更好的权重公式应该反映出关键词的分辨率。

  如果做一些理想的假设,

  1. 每个文献大小基本相同, 均为 $M$ 个词, 即 $M=\frac{N}{D}=\frac{{\sum }_{w}TF(w)}{D}$ 。
  2. 一个关键词在文献一旦出现, 不论次数多少, 贡献都等同, 这样一个词要么在一个文献中出现 $c(w)=\frac{TF(w)}{D(w)}$ 次, 要么是零。注意, $c(w)<M$

  $$\begin{array}{rl}\because & N=MD\\ & TF(w)=c(w)\cdot D(w)\\ \therefore I(w)& =TF(w)\log \frac{N}{TF(w)}\\ & =TF(w)\log \frac{MD}{c(w)D(w)}\\ & =TF(w)\log \left(\frac{D}{D(w)}\frac{M}{c(w)}\right)\\ & =TF(w)\log \left(\frac{D}{D(w)}\right)-TF(w)\log \left(\frac{M}{c(w)}\right)\\ \because & IDF=\log \frac{D}{D_W}\\ \therefore & =TF(w)\cdot IDF(W)-TF(w)\log \left(\frac{M}{c(w)}\right)\end{array}$$

  这样, 我们看到 TF-IDF 和信息量之间的差异就是公式 中的第二项。因为 $c(w)<M$, 所以第二项大于零, 它是 $c(w)$ 的递减函数。把上面的公式重写成
  $$TF-IDF(w)=I(w)-TF(w)\log \frac{M}{c(w)}$$

  可以看到, 一个词的信息量 $I(w)$ 越多, TF-IDF 值越大; 同时 $w$ 命中的文献中 $w$ 平均出现的次数越多, 第二项越小, TF-IDF 也越大。这些结论和信息论完全相符。

• TF-IDF 是对搜索关键词的重要性的度量, 并且具备很强的理论根据。因此, 即使是对搜索不是很精通的人, 直接采用 TF-IDF, 效果也不会太差。现在各家搜索引擎对关键词重要性的度量, 都在 TF-IDF 的基础上做了一定的改进和微调。但是, 在原理上与 TF-IDF 相差不远。