1701008991
我和数学有约：趣味数学及算法解析 [:1701004241]
1701008992
我和数学有约：趣味数学及算法解析 7.5 Google是如何快速实现信息检索的
1701008993
1701008994
信息检索（Information Retrieval）是指信息按一定的方式组织起来，并根据信息用户的需要找出有关信息的过程和技术。狭义的信息检索就是信息检索过程的后半部分，即从信息集合中找出所需要的信息的过程，也就是我们常说的信息查寻（Information Search或Information Seek）。
1701008995
1701008996
信息检索起源于图书馆的参考咨询和文摘索引工作，从19世纪下半叶首先开始发展，至20世纪40年代，索引和检索已成为图书馆独立的工具和用户服务项目。随着1946年世界上第一台电子计算机问世，计算机技术逐步走进信息检索领域，并与信息检索理论紧密结合起来；脱机批量情报检索系统、联机实时情报检索系统文献信息检索相继研制成功并商业化。20世纪60年代到80年代，在信息处理技术、通讯技术、计算机和数据库技术的推动下，信息检索在教育、军事和商业等各领域高速发展，得到了广泛的应用。
1701008997
1701008998
Google是世界上最大的搜索引擎，占全球所有搜索引擎的40％（Alexa调查），Google网络搜索引擎排名是企业实力的象征。Google公司自身搜索流量在全球排名第三，在自身系统中大约有30亿网站，据统计，每天至少有10亿人在使用Google搜索引擎。Google排名生效后，国内众多搜索引擎都会免费收录你的网站，在全球各地都可以搜索到有关你网站的信息。如雅虎、百度、一搜、搜狐、新浪和网易等，并且会给你的网站相对靠前的排名，为你带来无限商机，因此，Google排名受到国内众多企业的日益青睐。
1701008999
1701009000
【问题】Google是如何快速实现信息检索的呢？
1701009001
1701009002
【分析】
1701009003
1701009004
Google公司利用PagePank系统完成对网页级别的评判，在计算一个网页的PagePank值时，除了要考虑此网页被多少网页链接，还要考虑这些网页本身的质量（即这些网页自身的PagePank值）。链入的网页质量越高，则此网页的得分也会越高，得分越高的网页相应的级别也就越高。总的看来，网页的PageRank值取决于链入网页数，链入网页的质量和链入网页的链出网页数。
1701009005
1701009006
为使读者能完全理解Google矩阵的定义，先引入两个概念。
1701009007
1701009008
1701009009
（1）Markov矩阵：如果n阶实矩阵（每行元素之和均为一的非负矩阵），就称A是一个Markov矩阵；
1701009010
1701009011
（2）随机矩阵：如果A和AT都是Markov矩阵，则称A是一个随机矩阵。
1701009012
1701009013
有了上述的两个概念之后，Google矩阵的定义如下。
1701009014
1701009015
1701009016
Google矩阵：如果n阶实矩阵满足：
1701009017
1701009018
1701009019
1701009020
1701009021
其中0≤c≤1，c的经验值为0.85≤c≤0.99；B是一个Markov矩阵，e是一个所有元素均为1的列向量，v是一个概率分布向量，即所有元素非负，且相加和为1，v被Google称作个性化向量，它的选取方案Google是不公开的；A是一个Google矩阵。
1701009022
1701009023
1701009024
1701009025
注意：Google矩阵的创始人Brin和Page在测试Google矩阵时，选取的是c=0.85和v的所有元素均为。
1701009026
1701009027
Google矩阵的解释：这里的B相当于网络页面的邻接矩阵，若页面i向页面j有链接，则bij=1；否则bij=0。再将每行除以它们的链接数，使得每行的行和为1（全概率）。而c的引入可以理解为：由于现实网络并不都是强连通的，故从每个页面出发，通过正向链接而到达新页面的概率是c，而通过键入新地址到达新页面的概率是1-c（c又被称作阻尼系数）。
1701009028
1701009029
由于Google矩阵的特殊性，它有许多特殊的性质：
1701009030
1701009031
（1）Google矩阵的特征值λ满足0≤｜λ｜≤1；
1701009032
1701009033
（2）Google矩阵的最大特征值λ1为1（当A为正矩阵时，最大特征值为单根）；
1701009034
1701009035
（3）设λ2为A的第二特征值，即λ2是A的第二大的特征值，则｜λ2｜≤c。
1701009036
1701009037
下面我们将证明Google矩阵的上述性质。
1701009038
1701009039
性质1：Google矩阵的特征值λ满足0≤｜λ｜≤1。
1701009040