东莞网站优化制作,做外贸学英语的网站,台州人才网,工厂展厅效果图第四章 图论和网络爬虫
4.1 构建网络爬虫工程重点 构建网络爬虫的重点 用BFS还是DFS 在不考虑时间的情况下#xff0c;这两种不同的搜索方法都可以在相同的时间下爬下整个静态的互联网内容#xff0c;但是在现实中肯定是需要考虑时间以及互联网动态变化的。所以重点应该是如…第四章 图论和网络爬虫
4.1 构建网络爬虫工程重点 构建网络爬虫的重点 用BFS还是DFS 在不考虑时间的情况下这两种不同的搜索方法都可以在相同的时间下爬下整个静态的互联网内容但是在现实中肯定是需要考虑时间以及互联网动态变化的。所以重点应该是如何在有限时间里最多的爬下最重要的网页类似BFS。 考虑爬虫的分布式结构一个大的网络爬虫可能有成千上万台服务器组成的分布式系统这些服务器下载完一个网站后再进入另一个网站而不是每个网络先下载5%在回头继续第二批这样可以避免握手下载服务器和网络服务器建立通信的过程次数过多类似DFS。 所以并不是单纯的BFS或者DFS而是有相对复杂的下载优先级排序方法调度系统。 页面分析和URL提取 当一个网站下载后需要提取url加入下载队列。 记录哪个网页已经下载过-URL表 在互联网上一个网页可能会被多个网页的超链接指向所以在遍历时可能被多次访问为了避免一个网页被下载多次可以使用哈希表记录那些网 页已经被下载过。采用哈希表的好处是判断url是否在表中平均只需一次或者略多查找。遇到未下载的网页除了下载该网页还要适当将这个网页的URL存入哈希表中。如果有成千上万服务器下载网页存储这个哈希表的服务器的通信就是整个爬虫系统的瓶颈了。 总结 因为在现实生活中图的规模都是在几千个节点以内比如公路图铁路图等图的遍历比较简单所以在图论出现后的很长时间内即使是计算机专业的学生也体会不到这个领域的研究有什么实际用处。但是随着互联网的出现图的遍历方法一下子有了用武之地很多数学方法如布尔代数布尔运算等都是这样 第五章 网络搜索
5.1 pagerank算法(度量网页质量) pagerank算法中心思想 如果一个网页被很多网页所连接说明它收到普遍的承认和信赖那么它的排名就高排名高的网页的链接更可靠需要区别对待给予更大的权重即网页排名高的网站贡献的链接权重大。 计算网页排名的过程中需要用到网页自己的排名布林假定所有网页排名相同使用二维矩阵想乘并迭代计算的方法。 假定向量 B ( b 1 , b 2 , ⋯ , b N ) ⊤ \boldsymbol{B}\left(b_1, b_2, \cdots, b_N\right)^{\top} B(b1,b2,⋯,bN)⊤ 为第一、第二……第 N N N 个网页的网页排名。知阵 A [ a 11 ⋯ a 1 n ⋯ a 1 M ⋯ ⋯ a m 1 ⋯ a m n ⋯ a m M ⋯ ⋯ a M 1 ⋯ a M n ⋯ a M M ] A\left[\begin{array}{ccccc} a_{11} \cdots a_{1 n} \cdots a_{1 M} \\ \cdots \cdots \\ a_{m 1} \cdots a_{m n} \cdots a_{m M} \\ \cdots \cdots \\ a_{M 1} \cdots a_{M n} \cdots a_{M M} \end{array}\right] A a11⋯am1⋯aM1⋯⋯⋯a1namnaMn⋯⋯⋯a1M⋯amM⋯aMM 为网页之间链接的数目. 其中 a m n a_{m n} amn 代表第 n n n 个网页指问第 m m m 个网页的链接数。 A A A 是已知的, B B B 是末知的, 是我们所要计算的。 初始假设所有网页的排名都是 1 / N 1 / N 1/N, 即 B 0 ( 1 N , 1 N , ⋯ , 1 N ) 。 \boldsymbol{B}_0\left(\frac{1}{N}, \frac{1}{N}, \cdots, \frac{1}{N}\right) \text { 。 } B0(N1,N1,⋯,N1) 。 假定 B i B_i Bi 是第 i i i 论连代的结果那么 B i A ⋅ B i − 1 \boldsymbol{B}_i\boldsymbol{A} \cdot \boldsymbol{B}_{i-1} BiA⋅Bi−1 显然通过公式简单 (但是计算量非常大) 的知阵运算, 可以得到 B 1 , B 2 , ⋯ ⋯ B_1, B_2, \cdots \cdots B1,B2,⋯⋯ 可以证明 B i \boldsymbol{B}_i Bi 最终会收敛, 即 B i B_i Bi 无限趋近于 B \boldsymbol{B} B, 此时: B B × A ± \boldsymbol{B}\boldsymbol{B} \times \boldsymbol{A}_{ \pm} BB×A±因此. 当两炏㑢代的结果 B i \boldsymbol{B}_i Bi 和 B i − 1 \boldsymbol{B}_{i-1} Bi−1 之间的差昇非常小, 接近于零时, 停止迭代运算, 算法结束。一般来进, 只要 10 次左右的造代基本上就收敛了。 由于网页之间链接的数量相比互联网的规模非常稀疏, 因此计算网页的网页排名也需要对零概率或者小概率事件进行平滑处理。网页的排名是个一维向量, 对它的平清处理只能利用一个小的常数 α D \alpha_{\mathrm{D}} αD 这时, 公式 (1 变成 B i [ α N ⋅ I ( 1 − α ) A ] ⋅ B i − 1 \boldsymbol{B}_i\left[\frac{\alpha}{N} \cdot I(1-\alpha) A\right] \cdot \boldsymbol{B}_{i-1} Bi[Nα⋅I(1−α)A]⋅Bi−1 其中 N N N 是互联网网页的数教, α \alpha α 是一个 (较小的) 常数, I I I 是单位矩阵。网页排名的计算主要是矩阵相乘, 这种计算很容易分解成许多小任务.在多台计算机上并行处理。 5.2 TF-IDF(度量网页与查询相关性)
5.2.1 影响搜索引擎的因素
可以归纳为四大类 完备的索引。俗话说巧姻难为无米之㰠, 如果一个网页不在索引中, 那么再好的算法也找不到。对网页质量的度量, 比如 PageRank。当然, 正如在前面一章中介绍的那样, 现在来看, PageRank 的作用比 10 年前已经小了很多今天对网页质量的衝量是全方位的, 比如对网页内容权威性的度量,一些八卦网站的 PageRank 可能很高, 但是它们的内容权威性很低。用户偏好。这一点也很容易理解因为不同用户的㔛好不同因此一个好的搜害引繁会针对不同用户, 对相同的搜索给出不同的排名。确定一个网页和某个查询的相关性的方法。
5.2.2 TF( Term Frequency单文本词频) 度量网页和某个查询的相关性有个简单的办法即直接使用各个关键词在网页中出现的总词频。 T F 关键词出现次数 网页总字数 TF\frac{\text{关键词出现次数}}{\text{网页总字数}} TF网页总字数关键词出现次数 如果一个查询包含N个关键词 w 1 , w 2 , ⋯ , w N w_1, w_2, \cdots, w_N w1,w2,⋯,wN, 它们在一个特定网页中的词频分别是: T F 1 , T F 2 , ⋯ , T F N T F_1, T F_2, \cdots, T F_{N} TF1,TF2,⋯,TFN。那么, 这个直询和该网页的相关性 (即相似度) 就是: T F 1 T F 2 . . . . . T F N TF_1TF_2.....TF_N TF1TF2.....TFN 如搜索“原子能的应用”假设网页总字数1000字“原子能”出现2次“的”出现35次“应用”出现5次则TF为 0.002 0.035 0.005 0.042 0.0020.0350.0050.042 0.0020.0350.0050.042 漏洞 停止词“的”对确定网页主题几乎无用但却占词频80%“原子能”是个很专业的词权重应该比“应用”更重要但是词频却小于应用 因此我们需要给汉语中的每个词设置一个权重每个词的权重应满足 一个词预测主题的能力越强, 权重越大, 反之, 权重越小。在网页中看到 “原子能” 这个词, 或多或少能了解网页的主题。而看到 “应用”一词, 则对主题基本上还是一无所知。因此, “原子能”的权重就应该比“应用”大。停止词的权重为零。 很容易发现, 如果一个关键词只在很少的网页中出现, 通过它就容易锁定搜索目标, 它的权重也就应该大。反之, 如果一个词在大量网页中出现看到它仍然不很清楚要找什么内容, 它的权重就应该小。 5.2.3 IDF(Inverse Document Frequency逆文本词频指数) 在信息检索中使用最多的权重就是IDF。嘉定一个关键词 W W W在 D W D_W DW个网页中出现过那么 D W D_W DW越大 W W W权重越小反之亦然 I D F log D D W IDF\log {\frac{D}{D_W}} IDFlogDWD 其中D为所有网页数。 所谓IDF的概念为在一个特定条件下关键词的概率分布的交叉熵。
5.2.4 TF-IDF TF-IDF 被公认为是信息检索中最重要的发明 T F − I D F T F 1 ⋅ I D F 1 T F 2 ⋅ I D F 2 . . . T F N ⋅ I D F N TF-IDF TF_1\cdot IDF_1 TF_2\cdot IDF_2 ...TF_N\cdot IDF_N TF−IDFTF1⋅IDF1TF2⋅IDF2...TFN⋅IDFN 如搜索“原子能的应用”假设网页总字数1000字“原子能”出现2次“的”出现35次“应用”出现5次则TF为 T F 原子能 0.002 T F 的 0.035 T F 应用 0.005 \begin{aligned} TF_{原子能}0.002\\ TF_{的}0.035\\ TF_{应用}0.005\\ \end{aligned} TF原子能0.002TF的0.035TF应用0.005 假定中文网页数是 D 10 D10 D10 亿, 停止词 “的”在所有的网页中都出现, 即 D w 10 D_w10 Dw10 亿, 那么它的 I D F 的 log ( 10 亿 / 10 亿 ) log ( 1 ) 0 IDF_{的}\log (10 亿 / 10亿 )\log (1)0 IDF的log(10亿/10亿)log(1)0 假如专用词 “原子能” 在 200 万个网页中出现, 即 D w 200 D_w200 Dw200 万, 则它的权重 I D F 原子能 log ( 500 ) 8.96 I D F_{原子能}\log (500)8.96 IDF原子能log(500)8.96 又假定通用词 “应用”出现在五亿个网页中, 它的权重 I D F 应用 log ( 2 ) 1 I D F_{应用}\log (2)1 IDF应用log(2)1 , 则只有 1 。也就是说, 在网页中找到一个 “原子能” 的命中率 (Hits) 相当于找到九个 “应用” 的命中率。利用 IDF, 上述相关性计算的公式就由词频的加权求和 T F − I D F T F 1 ⋅ I D F 1 T F 2 ⋅ I D F 2 . . . T F N ⋅ I D F N T F 原子能 ⋅ I D F 原子能 T F 的 ⋅ I D F 的 T F 应用 ⋅ I D F 应用 0.002 ⋅ 8.96 0.035 ⋅ 0 0.005 ⋅ 1 0.01798 0 0.005 0.02292 \begin{aligned} TF-IDF TF_1\cdot IDF_1 TF_2\cdot IDF_2 ...TF_N\cdot IDF_N\\ TF_{原子能}\cdot IDF_{原子能}TF_{的}\cdot IDF_{的}TF_{应用}\cdot IDF_{应用}\\ 0.002 \cdot 8.960.035\cdot 00.005\cdot1\\ 0.0179800.005\\ 0.02292 \end{aligned} TF−IDFTF1⋅IDF1TF2⋅IDF2...TFN⋅IDFNTF原子能⋅IDF原子能TF的⋅IDF的TF应用⋅IDF应用0.002⋅8.960.035⋅00.005⋅10.0179800.0050.02292 如果结合网页排名算法如PageRank,那么给定一个查询有关网页的综合排名大致由相关性和网页排名的乘积决定。 5.2.5 TF-IDF的信息论依据 后续使用 w w w为关键词N为整个语料库D为中文网页数 D w D_w Dw为 w w w出现的网页/文献个数 T F ( w ) 关键词w出现次数 当前网页 / 文献总字数 TF(w)\frac{\text{关键词w出现次数}}{当前网页/文献总字数} TF(w)当前网页/文献总字数关键词w出现次数 一个查询中每一个关键词 w w w 的权重应该反映这个词对查询来讲提供了多少信息。一个简单的办法就是用每个词的信息量作为它的权重, I ( w ) − P ( w ) log P ( w ) − T F ( w ) N log T F ( w ) N T F ( w ) N log N T F ( w ) ∵ N 为常数 ∴ T F ( w ) log N T F ( w ) \begin{aligned} I(w) -P(w) \log P(w) \\ -\frac{T F(w)}{N} \log \frac{T F(w)}{N}\\ \frac{T F(w)}{N} \log \frac{N}{T F(w)}\\ \because~~N为常数\\ \therefore~~T F(w) \log \frac{N}{T F(w)}\\ \end{aligned} I(w)∵ ∴ −P(w)logP(w)−NTF(w)logNTF(w)NTF(w)logTF(w)NN为常数TF(w)logTF(w)N 上述公式有一个缺陷两个词出现的频率 TF 相同, 一个是某篇特定文章中的常见词, 而另外一个词是分散在多篇文章中, 那么显然第一个词有更高的分辨率, 它的权重应该更大。显然, 更好的权重公式应该反映出关键词的分辨率。 如果做一些理想的假设, 每个文献大小基本相同, 均为 M M M 个词, 即 M N D ∑ w T F ( w ) D M\frac{N}{D}\frac{\sum_w T F(w)}{D} MDND∑wTF(w) 。一个关键词在文献一旦出现, 不论次数多少, 贡献都等同, 这样一个词要么在一个文献中出现 c ( w ) T F ( w ) D ( w ) c(w)\frac{T F(w)}{D(w)} c(w)D(w)TF(w) 次, 要么是零。注意, c ( w ) M c(w)M c(w)M ∵ N M D T F ( w ) c ( w ) ⋅ D ( w ) ∴ I ( w ) T F ( w ) log N T F ( w ) T F ( w ) log M D c ( w ) D ( w ) T F ( w ) log ( D D ( w ) M c ( w ) ) T F ( w ) log ( D D ( w ) ) − T F ( w ) log ( M c ( w ) ) ∵ I D F log D D W ∴ T F ( w ) ⋅ I D F ( W ) − T F ( w ) log ( M c ( w ) ) \begin{aligned} \because~~NMD\\ TF(w)c(w)\cdot D(w)\\ \therefore~~ I(w)T F(w) \log \frac{N}{T F(w)}\\ TF(w) \log \frac{M D}{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{aligned} ∵ ∴ I(w)∵ ∴ NMDTF(w)c(w)⋅D(w)TF(w)logTF(w)NTF(w)logc(w)D(w)MDTF(w)log(D(w)Dc(w)M)TF(w)log(D(w)D)−TF(w)log(c(w)M)IDFlogDWDTF(w)⋅IDF(W)−TF(w)log(c(w)M) 这样, 我们看到 TF-IDF 和信息量之间的差异就是公式 中的第二项。因为 c ( w ) M c(w)M c(w)M, 所以第二项大于零, 它是 c ( w ) c(w) c(w) 的递减函数。把上面的公式重写成 T F − I D F ( w ) I ( w ) − T F ( w ) log M c ( w ) T F-I D F(w)I(w)-T F(w) \log \frac{M}{c(w)} TF−IDF(w)I(w)−TF(w)logc(w)M 可以看到, 一个词的信息量 I ( w ) I(w) I(w) 越多, TF-IDF 值越大; 同时 w w w 命中的文献中 w w w 平均出现的次数越多, 第二项越小, TF-IDF 也越大。这些结论和信息论完全相符。 TF-IDF 是对搜索关键词的重要性的度量, 并且具备很强的理论根据。因此, 即使是对搜索不是很精通的人, 直接采用 TF-IDF, 效果也不会太差。现在各家搜索引擎对关键词重要性的度量, 都在 TF-IDF 的基础上做了一定的改进和微调。但是, 在原理上与 TF-IDF 相差不远。
