互联网搜索引擎

admin管理员组

文章数量:1578036

说明：文章内容来源于课程视频和课程ppt。我只学习了课程没有做习题。文章不是翻译，是我对课程的理解。

1 挑战

　互联网搜索引擎与一般搜索引擎的区别主要在以下问题。
　第一是数据量(scalability)。互联网搜索需要处理的数据量大，如何保证能有效地处理这些数据，保证搜索的完整性，同时搜索速度也要在可接受范围内。解决策略：索引时候并行处理，搜索时候分布式处理。
　第二个是如何衡量数据质量，过滤垃圾数据？解决策略是垃圾检测。　
　第三个是互联网的动态性。要处理的数据会有新增和更新，怎么处理？解决策略是链接分析。
　VSM是一种普适算法，可以用在一般或者互联网搜索引擎中。这是它的优点。但它的问题是不能有效的利用网页或者文档的一些特性（例如：网页链接、发布日期、超链接文本等）

2 组成部分

　
　
　web searchEngine = Crawler+Indexer+(Inverted) Index + Retriever
　爬虫、索引操作、倒排索引、搜索操作

2.1 爬虫

　实验室级别爬虫：
　　

1. 种子页面放入优先队列；
2. 页面抓取；
3. 解析页面，提取链接，再添加到优先队列；

4. 从优先队列获得地址，回到2。

   真正在生产环境下的爬虫需要处理：
   　

5. 健壮性。当服务器不响应时候怎么处理；碰到爬虫陷阱（网站动态生成了一堆没用的地址）怎么处理；不能对被抓取的网站造成伤害（宕机），遵守Robot协议；处理不同类型的数据，例如网页、文件、图片等；还有ajax生成的页面怎么处理，用户登陆的页面怎么处理；冗余页面识别；隐藏链接发现。
6. 抓取策略。一般来说是广度优先（breadth-first）。
7. 分布式爬虫。
8. 特定主题的爬虫。只抓取某一类页面的爬虫。
9. 新页面/新站点发现，特别是与旧的页面没有链接的新页面怎么发现。
10. 新增页面抓取和更新页面抓取。这些需要处理怎么使用最少的资源实现目的。对新页面要抓取，旧的页面如果更新了，也要抓取更新到搜索引擎。对于旧页面的更新可以考虑一下因素：a、在抓取过程中总结、发现页面的更新频率，有些页面网址更新频率低，那抓取频率也降低。如果是体育新闻类页面，更新频率高，抓取频率也应提高。b、用户访问频率。用户访问频率高的页面，一般是最有用的页面，需要保证这些页面是尽可能最新。

2.2 索引操作、倒排索引

　创建互联网级别的索引，挑战在两方面：存储和效率。
　这些多数据怎么存储：分布式文件系统GFS、HDFS。
　这么多数据怎么有效地检索：MapReduce—-Hadoop

2.3 搜索-1 链接分析 Link Analysis

2.3.1 链接分析-1

　分析链接关系，提高搜索引擎搜索结果（怎么评估搜索结果，请参考文本搜索系统的评估）。
　标准的信息检索模型(IR)可以应用在互联网搜索(WR)中，但不够高效。原因如下。
　1 IR中人们主要查找图书资源，查找文献资源（literature Information）。WR人们需要查找一个页面，WR是具有导航性质的，一般称为导航搜索。所以分析链接关系可能有所帮助。
　2 网页一般还有其他信息可以作为搜索的线索。例如：布局、标题、链接信息。
　3 网页搜索可能还有其他因素，影响搜索结果。
　综上所述，我们可以通过链接分析、点击次数提高搜索结果。一般来讲会使用机器学习算法，把各个因素综合考虑。

　页面间引用关系，首先注意到的是锚点（anchor text）。锚点一般来说描述了所指向页面的主要内容或者特点。例如上面提交的“文本搜索系统的评估”，所指向的页面就是关系文本检索系统评估方面的内容。
　链接关系的第二个就是入链和出链。出链就像是一个路由器（hub）指向不同页面。入链是一个authority的页面：别人都在证明这个页面可能更有用。这有点像文献中的引用和被引用关系。成熟的解决方案是PageRank，考虑入链的个数以及质量。要注意处理没有入链的页面。
　

2.3.2 PageRank

　简要描述PageRank算法。
　PageRank 是一个随机访问模型。参数 α= $\alpha=$ 跳出本页面到其他页面（在浏览器中输入一个地址）的概率； 1−α= $1-\alpha =$ 在页面上随机选择一个连接进行下去。
　如果一个页面有很多的入链(inlinke)，也就是说入链数量高，那这个页面就更可能被访问到。因为有更多的可能从一个页面链接到这个页面。
　如果某个页面L1的某个入链L4有很多的入链，这些链接和L1形成一个间接链接关系。因为L4有很多的入链，L4的访问概率增加，那从L4到L1的概率也会增加。从这个角度看，算法也捕捉到了间接链接的关系。
　PageRank计算：转移矩阵、访问到某个页面的概率。
　
　
　

　

　PageRank的计算可以从线性代数的角度理解，也可以理解为是图的传播。
　PageRank可以用于计算某个主题相关页面的PageRank，也可以用于社交网络或者图的情形。

2.3.3 HITS

　直觉假设：被广泛引用的页面是一个好的Authority页面；引用了很多连接的页面是一个好的Hub页面。
　这是一个相互增强的思想。
　

2.4 搜索-2 排序 Ranking

　这是web搜索的最后一部分了。这里主要用机器学习的方法考虑各个因素，提高排序质量。
　现在我们有检索模型(BM25)可以计算查询语句与文档的相似度，我们也知道锚点、链接分值(PageRank)可以影响排序。问题是如何把这些因素结合起来，获得一个好的排序函数？用机器学习模型。
　假设： p(R=1|Q,D)=s(X1(Q,D),...Xn(Q,D),λ) $p(R=1|Q,D)=s(X_1(Q,D),...X_n(Q,D),\lambda)$， λ $\lambda$是参数，是一个向量。
　训练数据：为了获得参数，我们首先要获得训练数据。训练数据要包含每个文档对每个查询的相关度，形成一个（文档、查询、相关度）的数据。这些信息可以是很准确的用户处理的数据，也可以是基于点击量估计的（假设被点击的文档比跳过的文档更相关）。
　举例：逻辑回归模型(logistic regression)。最简单的模型。假设影响因素之间的关系是线性的。 Xi(Q,D) $X_i(Q,D)$是一个特征， β $\beta$是参数，模型如下：
　 logP(R=1|Q,D)1−P(R=1|Q,D)=β0+∑ni=1βiXi $log\dfrac{P(R=1|Q,D)}{1-P(R=1|Q,D)}=\beta_0+\sum_{i=1}^{n}\beta_iX_i$
　 P(R=1|Q,D)=11+exp(−β0−∑ni=1βiXi) $P(R=1|Q,D)=\dfrac{1}{1+exp(-\beta_0-\sum_{i=1}^{n}\beta_iX_i)}$
　 β0+∑ni=1βiXi $\beta_0+\sum_{i=1}^{n}\beta_iX_i$值越大， P(R=1|Q,D) $P(R=1|Q,D)$值也就越大，越相关(这与视频中讲的矛盾了，之后求证一下)。
　举例子。图中选择的是最大似然求解，此外还有最小二乘法。当然这里就涉及到乘法和加法的区别了。 β $\beta$参数学习到之后就可以用于文档排序了。
　
　

　还有更多选择的算法用来直接提高搜索结果(MAP,nDCG)。可以阅读参考文献
　•Tie-Yan Liu. Learning to Rank for Information Retrieval. Foundations and Trends in Information Retrieval 3, 3 (2009): 225-331.
　•Hang Li. A Short Introduction to Learning to Rank, IEICE Trans. Inf. & Syst. E94-D, 10 (Oct. 2011): n.p.
　

3 互联网搜索引擎的未来发展

3.1 趋势

　说的是趋势，其实很多已经实现了。
　下一代搜索引擎被认为更定制化，形成垂直搜索引擎。垂直搜索引擎被认为更好的原因是 1 针对特定的一个群体，他们拥有共同的基本概念。2 可以更个性化(personalization)。
　搜索引擎将会不断自动学习。
　搜索、推荐、导航集一体的搜索引擎。
　不再只是搜索，而是完成特定任务。例如购物。

3.2 新功能设想

　　
　　
　　
　　
　　从用户、数据、服务三个角度组合形成不同的产品。

3.3 更智能化的途径

　

　

本文标签： 互联网搜索引擎