基于聚类/分类和时间的簇页面排名设备和方法

摘要

提供了基于聚类/分类和时间的簇页面排名设备和方法。该簇页面排名设备包括：搜索器，被配置以根据给定查询语句从数据集中搜索相关文档并计算所搜索的文档的文档相关值，从而得到排序的相关文档集；簇生成器，被配置以对所述相关文档集进行聚类或分类从而得到簇；基于时间的簇页面排名计算器，被配置以基于簇计算基于时间的簇页面排名值(TCP值)，其是所述簇中所有文档的基于时间的文档链接值的组合，并作为所述簇中所有文档的基于时间的页面排名值、基于时间的作者排名值和基于时间的文档库排名值的组合；簇趋势生成器，被配置根据TCP值计算簇的未来的TCP值；和簇趋势排名器，被配置以对所述未来的TCP值进行排序从而得到趋势。

说明书

技术领域

本发明涉及趋势分析及文档排名优化，更具体地说，本发明涉及能够找到一特定领域的子领域并分析和发现这些子领域的趋势的基于聚类/分类和时间的簇页面排名设备和方法。

背景技术

在趋势分析和文档排名优化的领域中，参考文件1(US20050234877A1，“System and method for searching using a temporal dimension”)公开了对查询结果进行时间上排序，排序时考虑每个结果文档的作者权威和出版社权威。其中，基于时间的排名使用了基于文档出版时间和现在的时间差的老化函数以及一个会使得发表时间越久文档值降低越快的比率。但是，该方案只是计算单文档的基于时间的页面排名值并预测其趋势，并用于预测单文档趋势。

参考文件2(US20080071763A1，“Dynamic updating of display and ranking for search results”，EMC CORP)公开了重新对搜索排序，其采用了页面排名值来对搜索结果的第一部分进行排序，用聚类方法往第一部分结果中插入搜索结果的第二部分。

参考文件3(US20070143300A1，“System and method for monitoring evolution over time of temporal content”，ASK JEEVES INC)公开了根据用户输入的查询语句，收到和存储基于时间的内容，分析实体出现以确定基于时间的内容趋势。

参考文件4(US20060089924A1，“Document categorisation system”)公开了一个文档分类系统，包括一个聚类器和一个过滤模块。系统包括一个用于确定文档分类随时间的变化趋势和确定新簇的趋势分析器，此系统可用于电子数据表应用的嵌入模块。

另外，在参考文件5(Hassan Sayyadi，Lise Getoory；“FutureRank：Ranking Scientific Articles by Predicting their Future PageRank”，Society for Industrial and Applied Mathematics(SIAM)Data Mining Conference(SDM 2009))中，其方法将引用，作者和出版时间结合在一起有效地对科学文章进行排序并预测文章的未来趋势，但是此方法不涉及分类和聚类方法，对搜索结果的页面排名值上增加与时间相关的值，并且仅用于预测单文档趋势。

另外，现有技术中还存在以下的一些系统，其中CiteSpace是一个将趋势可视化系统。但此系统只考虑了作者间的合作关系，并没有对未来趋势进行预测。

ThemeRiver是一个趋势、模式判别系统。但它没考虑网络的上下文，也没对未来数据进行预测，只有对历史数据的统计。

而Google trend分析Google网页搜索用于计算用户使用词的次数。因为没考虑用户的权威性，所以使用词的次数多并不代表它就是权威的。

综上所述，在现有方法中，用户首先根据给定领域搜索相关文档，然后只是简单计算已知子领域的文档数目或人工总结文档内容、分析时间并预测趋势。计算文档数目不能揭示文档的内容关系，而人工分析方法又耗时又不客观。

发明内容

因此，本发明的目的是解决上述现有技术中的缺点，从而对于一给定领域，找到正出现的子领域并预测这些子领域的趋势。

为了解决现有技术中的问题，本专利提出了基于聚类/分类的时间的簇页面排名设备和方法。其能够自动发现子领域并采用基于时间的链接关系来客观地计算子领域的相对重要性，即趋势。

根据本发明的一个方面，提供了一种基于聚类/分类和时间的簇页面排名设备，包括：搜索器，被配置以接收用户给定的查询语句，根据所述查询语句从数据集中搜索相关文档并计算所搜索文档的文档相关值，从而得到排序的相关文档集，并将所述相关文档集输出；簇生成器，被配置以接收从所述搜索器输出的相关文档集，对所述相关文档集进行聚类或分类从而得到簇，并将所述簇输出；基于时间的簇页面排名计算器，被配置以从所述簇生成器接收所输出的簇，基于簇计算基于时间的簇页面排名值，并输出所述基于时间的簇页面排名值，所述基于时间的簇页面排名值是所述簇中所有文档的基于时间的文档链接值的组合，并作为所述簇中所有文档的基于时间的页面排名值、基于时间的作者排名值和基于时间的文档库排名值的组合；簇趋势生成器，被配置以从所述基于时间的簇页面排名计算器接收所述基于时间的簇页面排名值，并根据所述基于时间的簇页面排名值计算簇的未来的基于时间的簇页面排名值，并输出所述未来的基于时间的簇页面排名值；和簇趋势排名器，被配置以从簇趋势生成器接收所述未来的基于时间的簇页面排名值，并对所述未来的基于时间的簇页面排名值进行排序从而得到趋势。

在本发明中，所述基于时间的簇页面排名计算器进一步包括：页面排名值计算单元，被配置以计算簇中文档的基于时间的页面排名值；作者排名值计算单元，被配置以计算簇中文档的基于时间的作者排名值；文档库排名值计算单元，被配置以计算簇中文档的基于时间的文档库排名值；和加权单元，通过计算来自所述页面排名值计算单元的基于时间的页面排名值、来自所述作者排名值计算单元的基于时间的作者排名值和来自所述文档库排名值计算单元的基于时间的文档库排名值的加权和，并累积簇中所有文档的加权和来产生所述基于时间的簇页面排名值。

在本发明中，所述页面排名值计算单元通过在所有时间T_i的文档的基于时间的页面排名变化值的加权和来计算该文档在时间T_n的基于时间的页面排名值，其中i＝1，...，n，T_i≤T_n，且所述在所有时间T_i的文档的基于时间的页面排名变化值的权重是时间T_i到T_n的时间差的老化函数，并且在时间T_i的文档的基于时间的页面排名变化值是所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，且所述所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与所述搜索器得到的文档相关值成正比。

在本发明中，所述作者排名值计算单元所计算的文档的基于时间的作者排名值是此文档所有作者的基于时间的作者排名值之和，其中，通过在所有时间T_i的作者的基于时间的作者排名变化值的加权和来计算该作者在时间T_n的基于时间的作者排名值，其中i＝1，...，n，T_i≤T_n，且所述在所有时间T_i的作者的基于时间的作者排名变化值的权重是时间T_i到T_n的时间差的老化函数，并且在时间T_i的作者的基于时间的作者排名值为该作者所写的所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，所述作者所写的所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与所述搜索器得到的文档相关值成正比。

在本发明中，所述文档库排名值计算单元所计算的文档基于时间的文档库排名值为该文档所在文档库的基于时间的文档库排名值，并且文档库在时间T_n时的基于时间的文档库排名值是在所有时间T_i的文档库的基于时间的文档库排名变化值之和，其中i＝1，...，n，T_i≤T_n，，并且在时间T_i的文档库的基于时间的文档库排名变化值为该文档库中所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，所述文档库中所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与所述搜索器得到的文档相关值成正比。

在本发明中，所述簇趋势生成器根据基于时间的簇页面排名值的变化值或基于时间的簇页面排名值的变化率来计算簇的未来的基于时间的簇页面排名值。

在本发明中，所述簇趋势排名器根据簇的未来的基于时间的簇页面排名值与当前的基于时间的簇页面排名值之间的差对簇进行排序，其中，所述差值越大，排名越高。

根据本发明的另一方面，提供了一种基于聚类/分类和时间的簇页面排名方法，包括：搜索步骤，其根据由用户给定的查询语句从数据集中搜索相关文档并计算所搜索的文档的文档相关值，从而得到排序的相关文档集；簇生成步骤，其对所述相关文档集进行聚类或分类从而得到簇；基于时间的簇页面排名计算步骤，其基于所述簇生成步骤中得到的簇计算基于时间的簇页面排名值，所述基于时间的簇页面排名值是所述簇中所有文档的基于时间的文档链接值的组合，并作为所述簇中所有文档的基于时间的页面排名值、基于时间的作者排名值和基于时间的文档库排名值的组合；簇趋势生成步骤，其根据所述基于时间的簇页面排名值计算簇的未来的基于时间的簇页面排名值；和簇趋势排名步骤，其对所述未来的基于时间的簇页面排名值进行排序从而得到趋势。

在本发明中，所述基于时间的簇页面排名计算步骤进一步包括：页面排名值计算步骤，计算簇中文档的基于时间的页面排名值；作者排名值计算步骤，计算簇中文档的基于时间的作者排名值；文档库排名值计算步骤，计算簇中文档的基于时间的文档库排名值；和加权步骤，通过计算来自所述页面排名值计算单元的基于时间的页面排名值、来自所述作者排名值计算单元的基于时间的作者排名值和来自所述文档库排名值计算单元的基于时间的文档库排名值的加权和，并累积簇中所有文档的加权和来产生所述基于时间的簇页面排名值。

在本发明中，通过在所有时间T_i的文档的基于时间的页面排名变化值的加权和来计算该文档在时间T_n的基于时间的页面排名值，其中i＝1，...，n，T_i≤T_n，且所述在所有时间T_i的文档的基于时间的页面排名变化值的权重是时间T_i到T_n的时间差的老化函数，并且在时间T_i的文档的基于时间的页面排名变化值是所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，且所述所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与所述搜索步骤中得到的文档相关值成正比。

在本发明中，所述文档的基于时间的作者排名值是此文档所有作者的基于时间的作者排名值之和，其中，通过在所有时间T_i的作者的基于时间的作者排名变化值的加权和来计算该作者在时间T_n的基于时间的作者排名值，其中i＝1，...，n，T_i≤T_n，且所述在所有时间T_i的作者的基于时间的作者排名变化值的权重是时间T_i到T_n的时间差的老化函数，并且在时间T_i的作者的基于时间的作者排名值为该作者所写的所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，所述作者所写的所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与所述搜索步骤中得到的文档相关值成正比。

在本发明中，所述文档库排名值计算单元所计算的文档基于时间的文档库排名值为该文档所在文档库的基于时间的文档库排名值，并且文档库在时间T_n时的基于时间的文档库排名值是在所有时间T_i的文档库的基于时间的文档库排名变化值之和，其中i＝1，...，n-1，T_i≤T_n，，并且在时间T_i的文档库的基于时间的文档库排名变化值为该文档库中所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，所述文档库中所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与所述搜索步骤中得到的文档相关值成正比。

在本发明中，根据基于时间的簇页面排名值的变化值或基于时间的簇页面排名值的变化率来计算簇的未来的基于时间的簇页面排名值。

在本发明中，根据簇的未来的基于时间的簇页面排名值与当前的基于时间的簇页面排名值之间的差对簇进行排序，其中，所述差值越大，排名越高。

通过本申请的基于聚类/分类和时间的簇页面排名设备和方法，可以自动发现子领域并可以自动预测子领域趋势，发现未来热门子领域。并且，由于采用基于页面排名来分析趋势，可以客观地计算和分析趋势，避免了采用引用方法时由于过去被大量的引用，越老文档排名会越高，而由于较少引用的新文档会排名很低的问题，从而改进了趋势分析的精确性。

附图说明

图1是示出根据本发明的基于聚类/分类和时间的簇页面排名设备的总体配置的框图；

图2是示出根据本发明的基于聚类/分类和时间的簇页面排名设备中的基于时间的簇页面排名计算器的配置的框图；

图3是示出根据本发明的基于聚类/分类和时间的簇页面排名方法的流程图；

图4是示出根据本发明的基于聚类/分类和时间的簇页面排名方法中计算基于时间的簇页面排名值步骤的流程图。

具体实施方式

下面将结合附图来详细描述本发明的具体实施例。

图1是示出根据本发明的基于聚类/分类和时间的簇页面排名设备的总体配置的框图。如图1所述，本发明的基于聚类/分类和时间的簇页面排名设备100包括搜索器101、簇生成器102、基于时间的簇页面排名计算器103、簇趋势生成器104和簇趋势排名器105。下面，将对基于聚类/分类和时间的簇页面排名设备100的各个组件做详细说明如下。

在所述基于聚类/分类和时间的簇页面排名设备100中，搜索器101接收用户给定的查询语句，根据所述查询语句搜索全文索引，从数据集中搜索相关文档并计算所搜索的文档的相关文档值，从而通过对该相关文档值进行排序而得到排序的相关文档集，并将相关文档集输出。这里，搜索器101的采用的方法可以包括统计方法或基于链接分析的方法或它们的组合。

例如，搜索器101可以采用BM25算法(参见Ed Greengras，“Information Retrieval：A Survey”，30November 2000)来计算给定查询语句和文档库中文档的相关性得分，从而得到相应的搜索排名。这里，给定一文档集，用户输入查询语句Q，即一个领域描述，例如“办公室打印自动化”，则文档d的相关性得分score(d，Q)由如下公式计算得到：

$>\mathrm{score}(d,Q)=\underset{t\in Q}{\Sigma }\frac{\mathrm{tf}}{K+\mathrm{tf}}\frac{\mathrm{qtf}}{\mathrm{qtf}+k_3}\log (k_2\frac{N}{N_t}+1.0)$>公式1

其中，t是查询Q中的单词，tf是t在文档d中出现的次数，qtf是t在查询Q中出现的次数，N是文档库中的文档数，N_t是文档库中包含单词t的文档数，k₂和k₃是参数，例如k₂＝0.5，k₃＝1000，K定义如下

$>K=k_1((1-b)+b\frac{l}{\mathrm{avg}\_l})$>公式2

其中1是文档d的长度，含义为文档中单词的总数，avg_l是文档库的平均文档长度，即所有文档长度之和除以文档个数，k₁和b是参数，例如k₁＝1.2，b＝0.75。

其中，score(d，Q)的数值越高，表示该文档d与查询语句的相关度越高。

这样，搜索器101得到文档d与查询语句的相关度，即，相关文档值，并且根据相关度对于文档集进行排序从而得到排序的相关文档集。

簇生成器102接收从搜索器101输出的相关文档集，并对其进行聚类或分类。在簇生成器102中，聚类的方法可以是K-均值法聚类算法、模糊c-均值法聚类算法、及图论方法中的任意一个或多个的组合，并且分类的方法为基于监督的文档分类方法，非监督的文档分类方法，半监督的文档分类方法中的任意一个或多个的组合。

例如，簇生成器102将一次查询的结果中排名靠前的一定数目N的文档的子集进行聚类，以形成不同的簇，每个簇中的文档数据属于同一个特征或主题。当簇生成器102采用K-均值法聚类算法(参见Lloyd，S.P.(1957)，“Lastsquare quantization in PCM”，Bell Telephone Laboratories Paper Published in journal much later：Lloyd.，S.P.(1982))，用来对排名最靠前的N个搜索结果文档聚类生成簇时，该算法步骤包括：

(1)选择聚类参数k，其中k可以定义为k＝(N/2)1/2；

(2)随机选择k个文档作为k个初始类；

(3)对每个类，将其出现次数最多的10个词(t1，...，t10)确定为其聚类中心；

(4)分别计算每个文档和每个类之间的距离

公式3

其中s1，s2，...，s10分别是类c的10个中心词t1，...，t10出现的次数，l1，l2，...，l10分别是文档d中10个中心词t1，...，t10出现的次数，文档d将属于距离最近的类；

(5)循环步骤(3)和(4)直到每个聚类不再发生变化为止。

这样，簇生成器102通过对搜索器101排序的相关文档集进行聚类和分类，得到簇，即子主题。

基于时间的簇页面排名计算器103从簇生成器102获得簇，从而基于簇计算基于时间的簇页面排名值。将在下文中结合图2详细描述本发明的基于时间的簇页面排名计算器103的配置。

簇趋势生成器104根据基于时间的簇页面排名计算器103所计算的基于时间的簇页面排名(TCP)值，来计算簇的未来的基于时间的簇页面排名值，从而计算出每个簇的趋势。所述簇趋势生成器104采用的方法可以包括基于TCP变化值的预测方法和基于TCP变化率的预测方法。

例如，用TCP变化值来计算未来趋势时，

ΔTCP_Tn(c)＝TCP_Tn(c)-TCP_Tn-1(c)          公式4

ΔTCP_Tn-1(c)＝TCP_Tn-1(c)-TCP_Tn-2(c)      公式5

ΔTCP_Tn+1(c)＝2*ΔTCP_Tn(c)-ΔTCP_Tn-1(c)  公式6

这里，ΔTCP_Tn(c)是簇c在时间T_i的TCP值增量。(i＝n-2，n-1，n，n+1)

最后，簇趋势排名器105根据簇趋势生成器104计算簇的簇趋势值，也就是簇趋势生成器104计算出的TCP值增量对簇进行排序，其中，TCP值增量越大，排名越高。这里，所述TCP值增量是簇的未来的TCP值与簇的当前的TCP值之间的差值。这里，排名高的簇是即将出现的热门子领域。

下面，将参考图2对于本发明的基于时间的簇页面排名计算器103做进一步的详细描述如下。

如图2所示，本发明的基于时间的簇页面排名计算器103包括：页面排名值计算单元201，用于计算簇中文档的基于时间的页面排名值；作者排名值计算单元202，用于计算簇中文档的基于时间的作者排名值；文档库排名值计算单元203，用于计算簇中文档的基于时间的文档库排名值；和加权单元204，通过计算来自所述页面排名值计算单元201的基于时间的页面排名值、来自所述作者排名值计算单元202的基于时间的作者排名值和来自所述文档库排名值计算单元203的基于时间的文档库排名值的加权和来产生所述基于时间的簇页面排名值。下面，将对基于时间的簇页面排名计算器103的各个组件做详细说明如下。

根据本发明，基于时间的簇页面排名计算器103所计算的基于时间的页面排名值是簇中所有文档的基于时间的文档链接值的组合。而文档的基于时间的文档链接值则是文档的基于时间的页面排名值，文档的基于时间的作者排名值和文档的基于时间的文档库排名值的组合。因此，在本申请的基于时间的簇页面排名计算器103中，通过文档的基于时间的页面排名值，文档的基于时间的作者排名值和文档的基于时间的文档库排名值的加权和来计算基于时间的簇页面排名值，即TCP值。

在本发明中，页面排名值计算单元201通过在所有时间T_i的文档的基于时间的页面排名变化值的加权和来计算该文档在时间T_n的基于时间的页面排名值，其中i＝0，1，...，n-1，T_i＜T_n，且所述在所有时间T_i的文档的基于时间的页面排名变化值的权重是时间T_i到T_n的时间差的老化函数，并且在时间T_i的文档的基于时间的页面排名变化值是所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，且所述所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与搜索器101得到的文档相关值成正比。

例如，令PR_Tn(A)为文档A在时间T_n时的基于时间的页面排名值，则

$>{\mathrm{PR}}_{\mathrm{Tn}}\left(A\right)=(1-d)+d*(w_{T_1}*\Delta {\mathrm{PR}}_{T_i}\left(A\right)+...+w_{T_n}*\Delta {\mathrm{PR}}_{T_n}\left(A\right))$>

公式7

其中，d是一个常数且0＜d＜1，例如，d＝0.5，并且ΔPR_Ti(A)为时间T_i(0＜i≤n)时文档A的页面排名值变化量(即，基于时间的页面排名变化值)。

对于ΔPR_Ti(A)的权重，满足

$>w_{T_i}={\alpha }^{(T_n-\mathrm{Ti})/12}$>公式8

其中α是一常数并且0＜α＜1，例如，α＝0.5。

对于时间T_i(0＜i≤n)时文档A的页面排名值变化量，

$>\Delta {\mathrm{PR}}_{\mathrm{Ti}}\left(A\right)=S_{p1*}\frac{\Delta {\mathrm{PR}}_{T_i}\left(p_1\right)}{C\left(p_1\right)}+...+S_{\mathrm{pk}*}\frac{\Delta {\mathrm{PR}}_{T_i}\left(p_k\right)}{C\left(p_k\right)}$>公式9

其中是从T_i-1到T_i指向文档A的文档P_j的页面排名变化值，这里0＜j≤k，并且k是从T_i-1到T_i指向文档A的所有文档的个数，S_pk是由搜索器101进行归一化的搜索后得到的文档相关值，且C(p_j)是文档P_j的出度。

此外，除去本发明的上述方法外，还可以使用如US20050234877A1中公开的方法，或如FutureRank：Ranking Scientific Articles by Predicting their Future PageRank一文中所公开的方法计算簇中单文档的页面排名值。

作者排名值计算单元202所计算的文档的基于时间的作者排名值是此文档所有作者的基于时间的作者排名值之和，其中，通过在所有时间T_i的作者的基于时间的作者排名变化值的加权和来计算该作者在时间T_n的基于时间的作者排名值，其中i＝1，...，n-，T_i≤T_n，且所述在所有时间T_i的作者的基于时间的作者排名变化值的权重是时间T_i到T_n的时间差的老化函数，并且在时间T_i的作者的基于时间的作者排名值为该作者所写的所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，所述作者所写的所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与搜索器101得到的文档相关值成正比。

例如，令a₁，...，a_m是文档A的作者。为文档A在时间T_n时的基于时间的作者排名值，为文档A在时间T_n时作者a₁的排名值(其中，0＜1≤m，且m是文档A的作者的数目)，则有

$>{\mathrm{AP}}_{T_n}\left(A\right)={\mathrm{AP}}_{T_n}\left(a_1\right)+...+{\mathrm{AP}}_{T_n}\left(a_m\right),$>公式10

并且，对于文档A在时间T_n时作者a₁的排名值

$>{\mathrm{AP}}_{\mathrm{Tn}}\left(\mathrm{ai}\right)={w^{\prime }}_{T_1}*\Delta {\mathrm{AP}}_{T_i}\left(\mathrm{ai}\right)+...+{w^{\prime }}_{T_n}*\Delta {\mathrm{AP}}_{T_n}\left(\mathrm{ai}\right)$>公式11

其中，是作者a₁在时间T_i时的排名增量(即，文档的基于时间的作者排名变化值)，其中，0＜i≤n。

对于的权重，满足

$>{w^{\prime }}_{T_i}={\beta }^{(T_n-\mathrm{Ti})/12}$>公式12

其中，β是一常数并且0＜β＜1，例如β＝0.5。

而对于作者a_k在时间T_i时的排名增量，满足

$>\Delta {\mathrm{AP}}_{\mathrm{Ti}}\left(\mathrm{ai}\right)=\frac{S_{p1}*\Delta {\mathrm{PR}}_{T_i}\left(p_1\right)+...+S_{\mathrm{pk}}*\Delta {\mathrm{PR}}_{T_i}\left(p_k\right)}{k}$>公式13

其中，是从T_i-1到T_i指向文档A的文档P_j的页面排名变化值，这里0＜j≤k，并且k是从T_i-1到T_i指向文档A的作者a₁发表的所有文档的个数，S_pk是归一化的搜索后得到的文档相关值。这里p₁，...，p_k是作者a₁发表的文档。

此外，如页面排名值计算单元201计算的文档基于时间的页面排名值，除去本发明的上述方法外，还可以使用如US20050234877A1中公开的方法，或如FutureRank：Ranking Scientific Articles by Predicting their Future PageRank 一文中所公开的方法计算簇中单文档的作者排名值。

文档库排名值计算单元203所计算的文档基于时间的文档库排名值为该文档所在文档库的基于时间的文档库排名值，并且文档库在时间T_n时的基于时间的文档库排名值是在所有时间T_i的文档库的基于时间的文档库排名变化值之和，其中i＝1，...，n，T_i≤T_n，，并且在时间T_i的文档库的基于时间的文档库排名变化值为该文档库中所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，所述文档库中所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与所述搜索器得到的文档相关值成正比。

例如，令p是文档A的文档库，是文档A所在文档库的排名值，且p)是在时间Tn时文档库p的排名值，则

$>{\mathrm{JP}}_{T_n}\left(A\right)={\mathrm{JP}}_{T_n}\left(p\right)$>公式14

对于在时间Tn时文档库p的排名值

$>{\mathrm{JP}}_{\mathrm{Tn}}\left(p\right)=\Delta {\mathrm{JP}}_{T_1}\left(p\right)+...+\Delta {\mathrm{JP}}_{T_n}\left(p\right)$>公式15

这里是时间Ti时文档库p的排名值增量(即，文档库排名变化值)，其中0＜i≤n，由下式表示

$>\Delta {\mathrm{JP}}_{\mathrm{Ti}}\left(p_j\right)=\frac{S_{p1}*\Delta {\mathrm{PR}}_{T_i}\left(p_1\right)+...+S_{\mathrm{pk}}*\Delta {\mathrm{PR}}_{T_i}\left(p_k\right)}{k}$>公式16

其中是从T_i-1到T_i指向文档A的文档P_j的页面排名变化值，这里0＜j≤k，并且k是从T_i-1到T_i指向文档A的文档库P中的所有文档的个数，S_pk是归一化的搜索后得到的文档相关值，p₁，...，p_k是文档库P中的文档。

并且，如页面排名值计算单元201计算的文档基于时间的页面排名值和作者排名值计算单元202计算的文档基于时间的作者排名值，除去本发明的上述方法外，还可以使用如US20050234877A1中公开的方法，或如FutureRank：Ranking Scientific Articles by Predicting their Future PageRank一文中所公开的方法计算簇中单文档的文档库排名值。

加权单元204基于时间T_n时的文档的基于时间的页面排名值、基于时间的作者排名值和基于时间的文档库排名值A)，来计算基于时间的簇文档排名值。

例如，另是簇c在时间Tn时的页面排名值，则

$>\mathrm{TC}{P}_{T_n}\left(c\right)=\underset{A\in c}{\Sigma }(k_1*{\mathrm{PR}}_{T_n}\left(A\right)+k_2*{\mathrm{AP}}_{T_n}\left(A\right)+k_3*J{P}_{T_n}\left(A\right))$>公式17

其中k₁，k₂，k₃是大于零的常量参数，例如，k₁＝0.5，k₂＝0.3且k₃＝0.2。

这样，通过上述本发明的基于时间的簇页面排名计算器103的加权单元204计算页面排名值计算单元201所计算的基于时间的页面排名值、作者排名值计算单元202所计算的基于时间的作者排名值和文档库排名值计算单元203所计算的基于时间的文档库排名值的加权和，并对于簇中的所有文档累积所述加权和，从而得到基于时间的簇页面排名值。

此外，本领域技术人员也可以理解，当使用如US20050234877A1中公开的方法，或如FutureRank：Ranking Scientific Articles by Predicting their Future PageRank一文中所公开的方法时，通过累积所计算的簇中单文档的页面排名值、簇中单文档的作者排名值和簇中单文档的文档库排名值来获得文档的基于时间的文档链接值，并对簇中所有文档累积所述文档链接值，也可以得到所述基于时间的簇页面排名值。

图3是示出根据本发明的基于聚类/分类和时间的簇页面排名方法的流程图。如图3所示，本发明的基于聚类/分类和时间的簇页面排名方法包括步骤：

搜索步骤S101，在该步骤中，接收用户给定的查询语句，根据所述查询语句搜索全文索引，从数据集中搜索相关文档并计算所搜索的文档的相关文档值，从而通过对该相关文档值进行排序而得到排序的相关文档集，并将相关文档集输出。这里，所述搜索步骤采用的方法可以包括统计方法或基于链接分析的方法或它们的组合，在上文关于搜索器101的描述中已对此进行了描述，因此，在此将不再赘述。

簇生成步骤S102，在该步骤中，接收在搜索步骤S101中产生的相关文档集，并对其进行聚类或分类。在簇生成步骤S102中采用的聚类的方法可以是K-均值法聚类算法、模糊c-均值法聚类算法、及图论方法中的任意一个或多个的组合，并且采用的分类的方法为基于监督的文档分类方法，非监督的文档分类方法，半监督的文档分类方法中的任意一个或多个的组合，在上文关于簇生成器102的描述中已对此进行了描述，因此，在此将不再赘述。

基于时间的簇页面排名计算步骤S103，在该步骤中，基于在簇生成步骤S102获得的簇来计算基于时间的簇页面排名值。将在下文中结合图4详细描述本发明的基于时间的簇页面排名计算步骤的处理流程。

簇趋势生成步骤S104，在该步骤中，根据基于时间的簇页面排名计算步骤S103所计算的基于时间的簇页面排名(TCP)值，来计算簇的未来的基于时间的簇页面排名值，从而计算出每个簇的趋势。所述簇趋势生成步骤104采用的方法可以包括基于TCP变化值的预测方法和基于TCP变化率的预测方法，在上文关于簇趋势生成器104的描述中已对此进行了描述，因此，在此将不再赘述。

簇趋势排名步骤S105，在该步骤中，根据在簇趋势生成步骤S104计算的簇的簇趋势值(即簇趋势生成步骤S104计算出的TCP值增量)对簇进行排序，其中，TCP值增量越大，排名越高。这里，所述TCP值增量是簇的未来的TCP值与簇的当前的TCP值之间的差值。并且，排名高的簇是即将出现的热门子领域。

下面，将参考图4详细描述基于时间的簇页面排名计算步骤S103的处理流程。其中，图4是示出根据本发明的基于聚类/分类和时间的簇页面排名方法中计算基于时间的簇页面排名值步骤的流程图。

如图4所示，所述计算基于时间的簇页面排名值的步骤包括：页面排名值计算步骤S201，其用于计算簇中文档的基于时间的页面排名值；作者排名值计算步骤S202，用于计算簇中文档的基于时间的作者排名值；文档库排名值计算步骤S203，用于计算簇中文档的基于时间的文档库排名值；和加权步骤S204，通过计算在所述页面排名值计算步骤S201计算的基于时间的页面排名值、在所述作者排名值计算步骤S202计算的基于时间的作者排名值和在所述文档库排名值计算步骤S203计算的基于时间的文档库排名值的加权和，并对于簇中的所有文档累积所述加权和来产生所述基于时间的簇页面排名值。下面，将对以上各个步骤做进一步说明如下。

在本发明中，页面排名值计算步骤S201通过在所有时间T_i的文档的基于时间的页面排名变化值的加权和来计算该文档在时间T_n的基于时间的页面排名值，其中i＝1，...，n，T_i≤T_n，且所述在所有时间T_i的文档的基于时间的页面排名变化值的权重是时间T_i到T_n的时间差的老化函数，并且在时间T_i的文档的基于时间的页面排名变化值是所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，且所述所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与在搜索步骤S101得到的文档相关值成正比。在上述关于页面排名值计算单元201的描述中已给出了计算簇中文档的基于时间的页面排名值的实例，因此在此不再赘述。

此外，除去本发明上述方法外，还可以使用如US20050234877A1中公开的方法，或如FutureRank：Ranking Scientific Articles by Predicting their Future PageRank一文中所公开的方法计算簇中单文档的页面排名值。

作者排名值计算步骤S202所计算的文档的基于时间的作者排名值是此文档所有作者的基于时间的作者排名值之和，其中，通过在所有时间T_i的作者的基于时间的作者排名变化值的加权和来计算该作者在时间T_n的基于时间的作者排名值，其中i＝1，...，n，T_i≤T_n，且所述在所有时间T_i的作者的基于时间的作者排名变化值的权重是时间T_i到T_n的时间差的老化函数，并且在时间T_i的作者的基于时间的作者排名值为该作者所写的所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，所述作者所写的所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与在搜索步骤S101得到的文档相关值成正比。在上述关于作者排名值计算单元202的描述中已给出了计算簇中文档的基于时间的作者排名值的实例，因此在此不再赘述。

此外，如在页面排名值计算步骤S201中计算的文档基于时间的页面排名值，除去本发明的上述方法外，还可以使用如US20050234877A1中公开的方法，或如FutureRank：Ranking Scientific Articles by Predicting their Future PageRank一文中所公开的方法计算簇中单文档的作者排名值。

文档库排名值计算步骤S203所计算的文档基于时间的文档库排名值为该文档所在文档库的基于时间的文档库排名值，并且文档库在时间T_n时的基于时间的文档库排名值是在所有时间T_i的文档库的基于时间的文档库排名变化值之和，其中i＝1，...，n，T_i≤T_n，，并且在时间T_i的文档库的基于时间的文档库排名变化值为该文档库中所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的加权和，所述文档库中所有指向该文档的文档在时间T_i的基于时间的页面排名变化值的权重与搜索步骤S101得到的文档相关值成正比。在上述关于文档库排名值计算单元203的描述中已给出了计算簇中文档的基于时间的文档库排名值的实例，因此在此不再赘述。

并且，如页面排名值计算步骤S201计算的文档基于时间的页面排名值和作者排名值计算单元S202计算的文档基于时间的作者排名值，除去本发明的上述方法外，还可以使用如US20050234877A1中公开的方法，或如FutureRank：Ranking Scientific Articles by Predicting their Future PageRank一文中所公开的方法计算簇中单文档的文档库排名值。

随后，在加权步骤S204，计算页面排名值计算步骤S201所计算的基于时间的页面排名值、作者排名值计算步骤S202所计算的基于时间的作者排名值和文档库排名值计算步骤S203所计算的基于时间的文档库排名值的加权和，并对于簇中的所有文档累积所述加权和，从而得到基于时间的簇页面排名值。在上述关于加权单元204的描述中已给出了通过加权和来计算基于时间的簇页面排名值的实例，因此在此不再赘述。

此外，本领域技术人员也可以理解，当使用如US20050234877A1中公开的方法，或如FutureRank：Ranking Scientific Articles by Predicting their Future PageRank一文中所公开的方法时，通过累积所计算的簇中单文档的页面排名值、作者排名值和文档库排名值，可以得到所述文档的基于时间的文档链接值，并且，通过累积簇中所有文档的文档链接值，也可以得到簇页面排名值。

综上所述，通过本发明的基于聚类/分类和时间的簇页面排名设备和方法，可以自动发现子领域并可以自动预测子领域趋势，发现未来热门子领域。并且，由于采用基于页面排名来分析趋势，可以客观地计算和分析趋势，避免了采用引用方法时由于过去被大量的引用，越老文档排名会越高，而由于较少引用的新文档会排名很低的问题，从而改进了趋势分析的精确性。

在说明书中说明的一系列操作能够通过硬件、软件、或者硬件与软件的组合来执行。当由软件执行该一系列操作时，可以把其中的计算机程序安装到内置于专用硬件的计算机中的存储器中，使得计算机执行该计算机程序。或者，可以把计算机程序安装到能够执行各种类型的处理的通用计算机中，使得计算机执行该计算机程序。

例如，可以把计算机程序预先存储到作为记录介质的硬盘或者ROM(只读存储器)中。或者，可以临时或者永久地存储(记录)计算机程序到可移动记录介质中，诸如软盘、CD-ROM(光盘只读存储器)、MO(磁光)盘、DVD(数字多功能盘)、磁盘、或半导体存储器。可以把这样的可移动记录介质作为封装软件提供。

本发明已经参考具体实施例进行了详细说明。然而，很明显，在不背离本发明的精神的情况下，本领域技术人员能够对实施例执行更改和替换。换句话说，本发明用说明的形式公开，而不是被限制地解释。要判断本发明的要旨，应该考虑所附的权利要求。