目前关于个性化PageRank,其他的常见方法还有模型化PageRank(modular PageRank)和BlockRank等。这些方法在具体的计算方法上,主要的特点体现在从效率的角度上对算法进行了必要的优化。
关于加速PageRank算法的先前研究内容主要使用稀疏性图结构技术,比如Arasu等提出的观点,他们不仅仅单纯使用上次迭代循环产生值来计算本轮循环值,也使用本轮循环已经产生的值来加速本轮循环的计算。甚至提出了Web网络的蝴蝶结结构,并将其用于PageRank值的有效计算中。然而这些方法并不具有很大的实用性,主要原因在于算法要求对Web网络矩阵进行排序,这个操作需要按照深度搜索优先的原则进行网络遍历,这显然是一种代价极大的运算。最近Kamvar等也提出一些算法,使用连续中间循环来推断真实PageRank更好的估计值,但是仍然存在受PageRank算法初始参数影响的不足之处。
目前对于Web网络图结构的分析主要关注于研究图的属性,如节点的分布、网页链接的情况和Web网页图结构的建模等。然而,对于这些研究并没有强调如何有效利用这些属性来加快超链分析。
不少学者提出了一些改进做法,如Raghavan和Garcia-Molina等利用主机名称或者URL隐含的Web结构来代表Web图更为成功的做法也有很多,如Jeh和Widom通过有限修改网页的权值来表达的个性化网页权重,这个重要性权值可以反映用户指定的初始兴趣网页。由于对个性化视图的计算需要反复遍历整个Web图结构中的网页,这只有在运行期间才能实现,所以事先计算和存储所有的个性化视图并不现实。他们利用新的图论结果和技术构建出表达个性化视图的“偏好向量”(partial vector),它可以在不同用户的个性化视图中共享,同时关于它的计算和存储花费与视图数量的多少呈现出合理的比例。在计算中,还可以采用递增式计算,这就使得在查询期间利用偏好向量去构建个性化视图是可行的。这个偏好向量即为个性化PageRank向量(personalized PageRank vector,PPV),通俗地说,PPV是种Web网页的个性化视图。按照这个PPV来对网页结果进行排序可以有效地表达用户的偏好。
简单地看,每个PPV的长度都为咒,即Web的网页数量。但是由于从一个固定的角度循环计算PPV需要多次遍历Web网页图,这显然是不可能作为一种在线响应用户查询的方式。从另一个角度来看,所有PPV向量的总数量会达到2n(n为网页总数),这显然又过于巨大而无法实现离线存储。所以,必须将p集合中出现的网页限制为hub网页集合H的子集。H集合通常包含一些用户最为感兴趣的网页。在实践中,H集合可以是具有较高PageRank值的网页集合(重要网页)、在人工分类目录中的网页(如Yahoo和Open Directory)、特定企业或程序的重要网页等。H集合可以看成是计算个性化的基础。这种基于PPV的计算方式,不像传统的方式,能够和H集合大小成良好的比例缩放关系,并且这种技术也可以在更大的PPV集合上取得近似的效果,满足一些对于任意偏好网页集合的个性化计算要求。
除此以外,还有一些在计算效果上进行改进的算法。
如一种较为成功的做法是BlockRank方法,它主要是充分利用Web网页间链接结构呈现一种块状结构的特征来改进算法效率。关于Web网络块状结构的特征,已有很多学者进行了论证。例如,据Bharat等的分析,通过对比分析Web网络的链接结构,可以发现近80%左右的网页超链都是同一站点主机内部不同网页间形成的,而不同主机站点间网页的超链比重仅为20%左右。如果去除无用的死链接,这一比重表现得更加不平衡,近似于9:l。进一步将考察范围限定在域名级别后,上述的两个比重都有明显的增加,一为84:16,二为95:5,不平衡性明显加剧。一般在一个主机站点内,大部分的超链由于导航和站点安排,往往会在几个关键的网页上具有较多的内部链接。例如,高校站点内一般会对诸如图书馆、教务处和学生处等网页产生很高的链接比重。其实这种内部链接较高、外部链接较低的情况在不同级别的Web网页图结构中广泛存在,产生了明显的块化现象,而且大部分的块结构都远远小于整个Web的图结构。
这种Web网络所具有的块化结构有助于快速计算PageRank,同时为表达个性化PageRank提供了良好的基础。这个算法的思路大体描述如下:先对每个主机的网页计算本地化的PageRank值,得到在主机内部的相对重要权值。这些本地化的PageRank向量可以进一步按照不同Web网页块的相对重要程度加权形成全局PageRank值的近似值,然后将此PageRank向量作为标准PageRank算法的起始向量。不可否认,个性化PageRank虽然是个非常吸引人的主意,但是它需要对大规模的PageRank向量进行有效的迭代计算,而使用BlockRank算法和对冲浪者的随机冲浪行为做简单的限制就可以有效地减少个性化PageRank值的计算复杂度。这个限制就是当他厌倦时,他并不是从诸多网页中选择,而是从主机站点中进行选择。也就是说,此时无需考察冲浪者跳转的网页,而只考虑跳转的站点。这时构造的个性化向量具有的维度就是Web网络中主机的个数K,并且向量的元素值也反映冲浪者对不同主机的偏好程度。有了这个限制,本地化PageRank向量就无需针对不同的个性化用户而改变。事实上,本地化的PageRank向量也不会因为矩阵B结构的改变而改变,只有BlockRank向量6才会因为不同的个性化特征而改变,因此只需对每个基于块结构的个性化PageRank向量进行重新计算。
应该说,不论从理论上看,还是从实践上看,利用个性化PageRank来实现搜索引擎的个性化服务是个非常可行的选择,适应Web网络资源对信息检索提出的特点要求。它不仅在推荐结果内容上综合考虑网页客观性权重这个重要指标,而且该方法性能较高,主要计算工作都在离线阶段完成。然而,这些现有的个性化PageRank技术都需要用户登录并主动提交个性化信息,却忽略了用户对Web网页的理解,没有挖掘用户使用行为,收集用户个性化信息的方式不自然,这显然加重了用户的使用负担。所以,虽然说节省了用户挑选相关网页的时间,但是用户却需要花更多的时间去实现搜索个性化。由此可以看出,探讨获取用户个性化信息的其他有效形式将是提高此方法效果的关键所在,本书也主要对此进行研究,探寻更好的个性化信息收集和表达方法以适用于个性化PageRank算法中,该方法较为客观和全面。
个性化网页权重的常见形式就是个性化PageRank。现代搜索引擎对自然搜索引擎排名的排序依据除了使用传统的文本匹配技术以外,也广泛地使用网页权重值来进行。最为有名的例子就是Google的PageRank技术。
利用web结构的链接关系,PageRank可以计算每个网页的权重值,并据此对结果网页进行排序。因此,如果利用用户的偏好信息来修改PageRank权重值的计算,据此就产生表达特定用户个性化信息需求的搜索引擎排序结果。从效果上看,这种方法较PageRank更为实用,因为毕竟用户是不可能全部遍历获取的查询网页结果集合,所以把和用户需求联系最为密切的网页放于搜索结果前面,必然更易于用户访问。其实,Page等早已提出个性化PageRank的设想,只是他们并没有在此项研究上深人地开展下去基于个性化网页权重的个性化搜索引擎模型。
现在,人们提出的个性化PageRank方法有很多,主要分为两大类:一类是直接修改基于超链关系得到的网页权重值;另一类是在传统PageRank公式上添加修正参数来反映用户的个性化要求。
在原先的PageRank计算公式中,模型对每个网页的链接分配了相同的概率值,所以这种方法给不同链接和网页分配的权重是一样的,当前网页的权重值也会平均地影响链出网页,同时它还假设用户随机跳转到其他任何网页的概率都是一样的。所以,这种计算方法主要是依赖于网页结构图中的链接来进行分析。但是,这些链接却是由网站的网页设计者生成的,因此它只能反映设计者对Web中其他网页的理解。
另外,这种方法忽略了另外一个重要方面,那就是Web用户对Web网页的理解。也就是说,单纯使用网页之间的超链结构来表达网页权重值是不充分的。比较简单易行的修改网页权重做法就是利用Web日志挖掘信息来获取用户对Web网页的理解程度,以完善传统的PageRank计算方式。事实上,凭直觉可以判断出来,那些访问频率较高的超链应该比那些访问频率较低的超链更为重要,然而大部分的传统超链分析技术对这两者并不加以区分。
对于结合使用信息的超链分析技术最初是由Zhu等提出的,他们把相关公式称为PageRate,虽然他们也宣称自己的算法是PageRank的扩展,但是其实这种算法不具有任何PageRank的性质。这种算法对所有的链入不加区分,并不考虑高频访问和低频访问的区别。同时,他们也没有给出实验结论,对可能存在的问题也没有探讨,设计的公式还存在问题。
有些其他方面的研究也涉及使用信息分析。例如,使用一种增强学习方法来对搜索结果进行重排序和过滤,对于每个查询结果中的URL,系统都会记录不同用户的点击情况。在随后的查询中,上述信息就可以有效地提升高频访问的URL权值,而降低低频访问的URL权值这样的类似方法还应用于一些商业搜索引擎中,如有的学者就在多元搜索引擎中利用上述方法实现一种隐式的相关度反馈机制,它将用户点击产生的使用情况主要用于结果网页合并和网页重排序等操作中旧。用户使用信息还应用于基于模式的应用程序中,主要功能是及时学习用户的兴趣,并对搜索结果重排序以反映这种用户兴趣,如按照用户模式的特征改变不同主题词的相对重要程度。
比较好的方法是利用挖掘Web日志中的信息结合传统PageRank公式得出一种新的网页权重计算公式,即结合使用挖掘的PageRank,如特征敏感的PageRank(usage aware PageRank,UPR)。它结合了静态链接结构分析和用户使用分析两项技术:一方面仍然强调传统网页间的超链关系;另一方面,它通过分析日志,判断这些实际存在的网页超链中究竟哪些是经常被用户访问的,哪些不是经常被用户访问的,并以此来改进传统方法中由超链关系产生的网页权重值。
在UPR方法中,甚至还可以通过调整参数设置来控制静态链接结构分析技术和Web使用挖掘技术的作用力度,如果参数设置为O,公式就等价于传统的PageRank公式,如果参数设置为1,则重点就转移到使用挖掘分析算法上,介于两者之间则会兼顾,因此这种方式较传统方式更为概括。从效率上看,这种算法也有优势,只需通过一次额外的预处理步骤,其他的迭代处理和传统方式没有区别。
然而这种新的方法也存在不足之处。即使网站管理员可以得到自己站点用户的访问信息,并将其应用于UPR分析,但是这些信息显然没有包含全部的必要信息,如管理员不可能获得不属于自己站点访问内的链出网页使用情况。虽然可以通过爬虫程序遍历那些网页的超链结构,但是除了可以获得用户通过哪些网页的链出网页访问本地网页的使用信息,并不可能获得其他更为重要的使用信息。也就是说,从站点层次上看,全部的结构信息和使用信息是可以全部获取的,然而从整个Web网络层次上看,却是不完整的。
同时,对单一的应用技术而言,整个Web网络上的用户使用信息也是无法完整获取的。诸如Google搜索工具栏等客户端应用程序,虽然它们可以收集用户的使用信息,而且这些信息也确实是基于整个web范围而言的,然而这里所涉及的用户范围是相当小的,他们首先必须安装客户端应用程序,而且必须进行相关设置以同意公开这些属于个人隐私的Web访问信息。需要说明的是,诸如Google搜索工具栏之类的软件在默认情况下是尊重用户的个人隐私权的,除非用户自己允许,它并不主动收集任何用户访问的信息,当然也有其他一些客户端应用程序似乎并不遵守上述原则。
因此,这种结合使用挖掘的PageRank最适用于网站内部的网页搜索,搜索引擎工作的原理先获取该网站的结构信息,结合用户使用信息,可以得到传统PageRank方法的扩展模型。实验结果也能证明这种算法更能有效地提升高访问频率的网页权重值,相应地降低那些低访问频率的网页权重值。
随着搜索引擎技术慢慢走向成熟,越来越多的搜索引擎优化工作者以及很难从搜索引擎的表象去研究SEO。近一年时间以来,Google、百度等搜索引擎不断调整链接分析技术,加深SEO门槛。SEOER也必须随着搜索引擎的发展而发展。
以上的研究方法要求全面获取Web资源的使用情况,对于设计真正的Web搜索引擎而言,它是不可行的,所以只是适用于网站内部的信息检索系统中。
与此相反,对于Web搜索引擎,通过添加修正参数的个性化PageRank方法相对较为可行。该方法无需过多地在遍历网页结构时重新定义不同超链的权重分配关系,只需在得到全部网页的简单超链结构关系后,直接通过引入修正参数来体现用户的某种个性化信息。
通过添加修正参数引入个性化信息的网页权重算法在以Kleinberg等设计的HITS算法中就有体现,不像PageRank方法,这个算法对每个网页都分配两个权重值:一个为authority值;另一个为hub值。它们具有一种迭代的定义,即一个好的authority网页是被好的hub网页指向,一个好的hub网页也指向好的authority网页。这种算法主要应用于使用主题爬虫的网页排序方法,还有在受限条件下的Web社区分析等方面这个算法的最初版本没有像PageRank算法那样具有很好的缩放性,而且对于较多网页节点的处理还存在收敛的问题。
这种方法最早在PageRank算法中的用途主要是用于计算主题化PageRank,通过引人代表一定主题的参数向量就可以使PageRank产生主题化倾向。例如,Richardson等通过预处理方法,对不同主题所涉及的网页集合生成不同的PageRank向量,但查询包含上述的一个或者多个主题时,与那些主题有关的预处理PageRank值就可以直接用于运算另外,Haveliwala等使用了另外一种完全不同的方法,他提出了主题相关PageRank(topic-sensitive PageRank),这个方法先从Open Directory项目获取主题信息,然而对Open Directory项目的每个类别计算不同的PageRank值,这个PageRank值偏重于该类别内的相关网页。当用户发出查询时,通过识别查询的上下文,相关类别的PageRank值都用于计算结果网页的权重值口引。
本文作者: