论文部分内容阅读
摘 要： 提出一种基于用户浏览网页时间的搜索引擎新排名算法time-Rank。该算法根据用户浏览时间的信息，更加准确地计算网页的排名得分，提高搜索引擎排名的准确性。算法基于浏览任意两个网页之间的时间差，对用户浏览网页时间进行计算，该算法能够更加准确地模拟用户浏览网页的时间长短。由于浏览时间不同，用户对网页的喜爱程度也就不同，直接体现该页面针对不同用户的重要程度。
关键词： time-Rank；PageRank；Hits；搜索引擎；排序
中图分类号：TP391 文献标识码：A 文章编号：1671-7597（2012）1110013-02
0 引言
由于互联网的出现和迅速发展，搜索检索的环境发生了重大变化。而基于互联网的搜索引擎的排名算法，直接关系到用户获取相关信息的准确性。网页链接结构是搜索引擎排名算法的基础，其中有两种算法很流行：PageRank[4]算法和Hits[3]
算法，这两种算法国内外有许多学者和研究机构都进行了研究。但是，在传统的PageRank算法中，PageRank得分表示的是用户浏览某篇网页的概率。但此得分的计算过程有一个前提，那就是用户浏览网页的过程是绝对随机，并且是盲目的。于是，所有的出链都被赋予相同的权值，每篇被链到的页面都得到这个权值，完全没有考虑用户对两个网页的重视程度，这显然是不合理的。用户点击下一网页不是盲目的，用户是根据自己感兴趣的内容点击下以网页，PageRank和HITS算法都没有考虑这些，从而不能体现该网页对用户的重要程度，而timeRank 算法解决了这个问题。
1 PageRank算法
PageRank[4]算法是斯坦福大学的Larry Page和Sergey Brin在1996年提出的。
其基本概念是：每个网站都有外部链接和内部链接，其中数量和质量关系该网站的价值，如果网页v有其它网页进行链接，这样说明网页v对于其它网页比较重要，这相当每个页面对网页v进行了一次投票。链接越多，被其他网页的投票也就越多，每个网页都有重要性得分值，假设网页A它的重要性为：PageRank值PR（A）和A的出链（从A链出的链接）数C（A）的比值，具体公式为PR（A）/C（A）。
假设有T1…Tn个网页指向A，参数d为阻尼系数，是0到1之间的值，通常假设为0.85。C（A）是一个从网页A的链出的网页数。A的PageRank值由以下公式计算：
假设用户当前在浏览某一网页Ti，下一步它要么以概率
以概率1-d在Web中均匀地选择任一页面进行浏览。Web中存在的大量独立网页，用公式（1）计算的PageRank值为0.15，太高，于是Google又给出了公式：
2 time-Rank算法
2.1 算法
网页的重要性对于用户来说是不同的，即使它们的链接结构是一样的，因此怎样把网页内容和链接结构关系到一起？如果用户对网页感兴趣，那么用户浏览的时间比那些用户不感兴趣的网页浏览时间要长，这意味着网页的内容更可能是用户想搜索到的，如果我们把浏览时间加入到排序算法中，我们更能准确的计算网页排序的分数，因此，怎样估算浏览网页的时间是当前算法的关键。
为了估计出用户浏览网页的时间，我们做出一个合理的假设，假设用户点击的网页是来自搜索解析的网页集合中的网页，意思是说，用户在搜索引擎中输入关键字，得到相关的网页结合，假设用户每次只点击一个网页，一直到浏览完该网页才去点击另一网页，换句话说，每次用户点击不超过两个网页，直到浏览完一个网页再去浏览另一个，如果用户在这种方式下浏览网页，它存在一个浏览序列。
假设P为序列，向量P={p1，p2….，pn}，n代表用户输入的关键字，所解析返回的网页数量，基于这个序列，我们能计算出浏览网页的时间TJ代表用户点击网页Pj的时间，Tj+1代表用户点击网页Pj+1的时间，因此用户浏览网页Pj的时间是Tj+1-Tj，用户浏览浏览网页的时间为：TM={t1，t2….，tn}。
我们添加时间因素进入算法，是因为如果用户感兴趣该网页，有可能是和用户搜索的主题相关，这样用户就会浏览更长的时间，否则用户很快就离开该网页，浏览很短的时间。因此计算过程如下：
基于超链接的排名，每个网页有n个时间分数，n代表主题的数量。首先，运用web图算法并计算每个离线下网页的等级，这个计算过程是基于[1]。
其次，计算关键字和超链接的相似度，用户提交关键字给搜索引擎后，搜索引擎必须确保关键字和超链接想匹配，根据贝叶斯理论[2]，解析q和超链接j之间的关系有可能是：
H（j）代表j的每个页面的超链接，PR（H（j））代表在相关网页集中所占的比例，PR（q|H（j））代表在超链接j中包含q所占的比例，计算这个的目的是怎样把时间加入到超链接中。
最后，把时间加入进去 ，每个网页有初始的浏览时间向量TS={t（1），t（2），….t（n）}，t（j）代表用户关于连接j的页面的总的浏览时间，为了避免0的出现，初始t（j）=1，这样搜索引擎运行几次后，我们能计算出浏览每个网页的时间向量，这个向量来源于用户浏览时间序列TM，因此每个页面的排名是：
2.2 算法描述
为了把时间加入到排名算法中，我们首先建立“基于时间浏览模式”，在这种模式下我们能测量每个网页的浏览时间。在运行了原始算法和改进的网页算法后知道用户对不同网页的重视程度，这个算法利用时间因素增加了网页排名的准确性。
在这个算法中，意味着有较长的网页浏览时间，将获得更高的分数，无论两个网页的链接结构是相同的还是不同的。增加了时间到网页排名分数的计算中后，我们不仅能得到网页更准确的排名分数，而且避免了垃圾网页获得较高的分数，这是本论文的贡献。
2.3 處理
为了从服务器日志中得到用户浏览网页的时间，我们首先必须处理服务器日志，查询词，IP地址，以及浏览时间都记录在服务器上，由于在日志中存在噪声，首先我们应该先区分噪声，并且按照互联网协议地址安排事件。如果源IP地址在一小时是一样的，我们可以用web代理来处理它，我们可以把web代理看作是一个用户的点击序列，假如两个相邻的点击事件之间的时间间隔大于一个小时，我们就抛弃后一个点击事件，根据这个规则，我们能得到网页的访问的时间，并且可以计算时间通过公式（4）。
3 结束语
本文提出了基于时间技术的搜索排名算法timeRank，并且给出了完整和详细的数学表示，经过完整的算法表达与应用，充分根据网页对用户的重要性信息，能够获得更加准确的排序结果，克服PageRank等一些算法和查询关键字无关的缺陷，从而让排序算法更加准确地模拟了用户浏览页面的习惯。在此之前，所有搜索引擎排名算法都有很多不足之处，无法区分网页中的超链接是不是和网页有相关性，还是不相关，这样很容易出现主题漂移的问题，即和主题不相关的网页排名很靠前。但是，一个好的搜索引擎应该能够根据用户的兴趣，关注其兴趣或期望来获取相关的信息，本文已经开始利用用户的兴趣爱好，这些问题需要作出进一步的努力和改进。
参考文献：
[1]L. Page，S.Brin， R. Motwani and T. Winograd， The pagerank citation ranking： Bringing order to the web，Technical report， Stanford Digital Library Technologies Project.1998.
[2]Dimitri，P. Betsekas and John N. Tsitsiklis， Introduction to Probability. Athena Scientific， 2002.
[3]Jon Kleinberg， “Authoritative Sources in a Hyperlinked Environment”，In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms， 1998.
[4]BRIN S，PAGE L. The Anatomy of a LargeSca1e Hypertextual Web Search Engine[A].Pro. of the 7th international World Wide Web Conference[c].1998，Vo1.7.
关键词： time-Rank；PageRank；Hits；搜索引擎；排序
中图分类号：TP391 文献标识码：A 文章编号：1671-7597（2012）1110013-02
0 引言
由于互联网的出现和迅速发展，搜索检索的环境发生了重大变化。而基于互联网的搜索引擎的排名算法，直接关系到用户获取相关信息的准确性。网页链接结构是搜索引擎排名算法的基础，其中有两种算法很流行：PageRank[4]算法和Hits[3]
算法，这两种算法国内外有许多学者和研究机构都进行了研究。但是，在传统的PageRank算法中，PageRank得分表示的是用户浏览某篇网页的概率。但此得分的计算过程有一个前提，那就是用户浏览网页的过程是绝对随机，并且是盲目的。于是，所有的出链都被赋予相同的权值，每篇被链到的页面都得到这个权值，完全没有考虑用户对两个网页的重视程度，这显然是不合理的。用户点击下一网页不是盲目的，用户是根据自己感兴趣的内容点击下以网页，PageRank和HITS算法都没有考虑这些，从而不能体现该网页对用户的重要程度，而timeRank 算法解决了这个问题。
1 PageRank算法
PageRank[4]算法是斯坦福大学的Larry Page和Sergey Brin在1996年提出的。
其基本概念是：每个网站都有外部链接和内部链接，其中数量和质量关系该网站的价值，如果网页v有其它网页进行链接，这样说明网页v对于其它网页比较重要，这相当每个页面对网页v进行了一次投票。链接越多，被其他网页的投票也就越多，每个网页都有重要性得分值，假设网页A它的重要性为：PageRank值PR（A）和A的出链（从A链出的链接）数C（A）的比值，具体公式为PR（A）/C（A）。
假设有T1…Tn个网页指向A，参数d为阻尼系数，是0到1之间的值，通常假设为0.85。C（A）是一个从网页A的链出的网页数。A的PageRank值由以下公式计算：
假设用户当前在浏览某一网页Ti，下一步它要么以概率
以概率1-d在Web中均匀地选择任一页面进行浏览。Web中存在的大量独立网页，用公式（1）计算的PageRank值为0.15，太高，于是Google又给出了公式：
2 time-Rank算法
2.1 算法
网页的重要性对于用户来说是不同的，即使它们的链接结构是一样的，因此怎样把网页内容和链接结构关系到一起？如果用户对网页感兴趣，那么用户浏览的时间比那些用户不感兴趣的网页浏览时间要长，这意味着网页的内容更可能是用户想搜索到的，如果我们把浏览时间加入到排序算法中，我们更能准确的计算网页排序的分数，因此，怎样估算浏览网页的时间是当前算法的关键。
为了估计出用户浏览网页的时间，我们做出一个合理的假设，假设用户点击的网页是来自搜索解析的网页集合中的网页，意思是说，用户在搜索引擎中输入关键字，得到相关的网页结合，假设用户每次只点击一个网页，一直到浏览完该网页才去点击另一网页，换句话说，每次用户点击不超过两个网页，直到浏览完一个网页再去浏览另一个，如果用户在这种方式下浏览网页，它存在一个浏览序列。
假设P为序列，向量P={p1，p2….，pn}，n代表用户输入的关键字，所解析返回的网页数量，基于这个序列，我们能计算出浏览网页的时间TJ代表用户点击网页Pj的时间，Tj+1代表用户点击网页Pj+1的时间，因此用户浏览网页Pj的时间是Tj+1-Tj，用户浏览浏览网页的时间为：TM={t1，t2….，tn}。
我们添加时间因素进入算法，是因为如果用户感兴趣该网页，有可能是和用户搜索的主题相关，这样用户就会浏览更长的时间，否则用户很快就离开该网页，浏览很短的时间。因此计算过程如下：
基于超链接的排名，每个网页有n个时间分数，n代表主题的数量。首先，运用web图算法并计算每个离线下网页的等级，这个计算过程是基于[1]。
其次，计算关键字和超链接的相似度，用户提交关键字给搜索引擎后，搜索引擎必须确保关键字和超链接想匹配，根据贝叶斯理论[2]，解析q和超链接j之间的关系有可能是：
H（j）代表j的每个页面的超链接，PR（H（j））代表在相关网页集中所占的比例，PR（q|H（j））代表在超链接j中包含q所占的比例，计算这个的目的是怎样把时间加入到超链接中。
最后，把时间加入进去 ，每个网页有初始的浏览时间向量TS={t（1），t（2），….t（n）}，t（j）代表用户关于连接j的页面的总的浏览时间，为了避免0的出现，初始t（j）=1，这样搜索引擎运行几次后，我们能计算出浏览每个网页的时间向量，这个向量来源于用户浏览时间序列TM，因此每个页面的排名是：
2.2 算法描述
为了把时间加入到排名算法中，我们首先建立“基于时间浏览模式”，在这种模式下我们能测量每个网页的浏览时间。在运行了原始算法和改进的网页算法后知道用户对不同网页的重视程度，这个算法利用时间因素增加了网页排名的准确性。
在这个算法中，意味着有较长的网页浏览时间，将获得更高的分数，无论两个网页的链接结构是相同的还是不同的。增加了时间到网页排名分数的计算中后，我们不仅能得到网页更准确的排名分数，而且避免了垃圾网页获得较高的分数，这是本论文的贡献。
2.3 處理
为了从服务器日志中得到用户浏览网页的时间，我们首先必须处理服务器日志，查询词，IP地址，以及浏览时间都记录在服务器上，由于在日志中存在噪声，首先我们应该先区分噪声，并且按照互联网协议地址安排事件。如果源IP地址在一小时是一样的，我们可以用web代理来处理它，我们可以把web代理看作是一个用户的点击序列，假如两个相邻的点击事件之间的时间间隔大于一个小时，我们就抛弃后一个点击事件，根据这个规则，我们能得到网页的访问的时间，并且可以计算时间通过公式（4）。
3 结束语
本文提出了基于时间技术的搜索排名算法timeRank，并且给出了完整和详细的数学表示，经过完整的算法表达与应用，充分根据网页对用户的重要性信息，能够获得更加准确的排序结果，克服PageRank等一些算法和查询关键字无关的缺陷，从而让排序算法更加准确地模拟了用户浏览页面的习惯。在此之前，所有搜索引擎排名算法都有很多不足之处，无法区分网页中的超链接是不是和网页有相关性，还是不相关，这样很容易出现主题漂移的问题，即和主题不相关的网页排名很靠前。但是，一个好的搜索引擎应该能够根据用户的兴趣，关注其兴趣或期望来获取相关的信息，本文已经开始利用用户的兴趣爱好，这些问题需要作出进一步的努力和改进。
参考文献：
[1]L. Page，S.Brin， R. Motwani and T. Winograd， The pagerank citation ranking： Bringing order to the web，Technical report， Stanford Digital Library Technologies Project.1998.
[2]Dimitri，P. Betsekas and John N. Tsitsiklis， Introduction to Probability. Athena Scientific， 2002.
[3]Jon Kleinberg， “Authoritative Sources in a Hyperlinked Environment”，In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms， 1998.
[4]BRIN S，PAGE L. The Anatomy of a LargeSca1e Hypertextual Web Search Engine[A].Pro. of the 7th international World Wide Web Conference[c].1998，Vo1.7.