一种文档的检索方法和装置转让专利
申请号 : CN200910238289.X
文献号 : CN101706812B
文献日 : 2011-09-14
发明人 : 唐杰 , 杨子
申请人 : 清华大学
摘要 :
本发明公开了一种文档的检索装置和方法，针对现有话题模型无法自动识别话题的问题而发明。本发明的装置包括：话题识别模块、随机游走模块、检索模块。方法包括：使用概率话题模型从文档集中识别话题，并根据识别到的话题得到文档的话题分布；对每个文档计算其话题层次的随机游走排序得分；根据查询关键词及话题，计算文档相对于该查询关键词的相关性得分，将话题层次随机游走的排序重要性得分和相关性得分相结合得到检索结果。
权利要求 :
1.一种文档的检索装置，其特征在于，包括：
话题识别模块，所述话题识别模块利用概率话题模型从文档集中识别话题，并根据识别到的话题得到文档的话题分布，具体包括：参数计算子模块，所述参数计算子模块根据Gibbs采样方法计算话题z上的后验概率分布：
其中d为文档集D中的一个文档，z为文档d中的话题；为文档中的每个单词 对应的话题；di表示文档d中的第i个单词， 表示除di外的统计数值，然后根据后验概率分布计算θ和φ，其中θ为|D|个文档相关的文档-话题分布矩阵；φ为|T|个话题相关的话题-单词的分布矩阵，α和β分别为多项式分布θ和φ的Dirichlet先验；
识别话题子模块，所述识别话题子模块根据θ和φ，使用LDA话题模型从文档集中识别话题，其中文档集D的似然度为：其中θd为文档d在话题上的多项式分布，φz为话题z在单词上的多项式分布；ndz是将话题z关联到文档d的次数，nzv是单词wv由话题z生成的次数；V为互异单词的集合；
多项式分布子模块，所述多项式分布子模块根据所述话题识别模块识别的话题，生成文档的话题的多项式分布{p(z|d)}；其中P(z|d)是文档d生成话题z的概率；
随机游走模块，所述随机游走模块根据话题分布对每个文档计算随机游走排序得分，具体包括：随机游走排序得分计算子模块，以根据文档话题的多项式分布计算随机游走排序得分：其中，r[d，z]为文档d在话题z上的随机游走排序得分；D为所有文档的集合；T为所有话题的集合；z为文档d中的话题；λ为预设的随机跳跃参数，即游动者以等概率随机跳到文档集中的不同文档；γ为随机游走者点击一条链接访问相同话题的文档dl的概率，(1-γ)为随机游走者点击一条链接访问不同话题的文档dl的概率；
其中，P(dl|dk，zi)是从文档dk到dl在相同话题zi上的转移概率，表示为P(d|d′，zi)；
P(dl，zj|dk，zi)是从话题zi的文档dk到话题zj的文档dl的转移概率，表示为P(d，zi |d′，zj)；则检索模块，所述检索模块根据查询关键字计算文档对于该查询关键字的相关性得分，并根据随机游走排序得分与相关性得分结合得到检索结果，具体包括：概率计算子模块，所述概率计算模块计算由话题模型生成查询关键词q的概率PLDA(q|d)，其中θd为特定文档d在话题上的多项式分布；φz为特定的话题z在单词上的多项式分布；
并采用语言模型计算查询关键词q从文档d中生成概率PLM(q|d)；
查询关键词q与文档相关性得分P(q|d)＝PLM(q|d)×PLDA(q|d)；
将所述随机游走模块所得话题层次随机游走排序得分r[d，z]和相关性得分P(q|d)相结合得到检索结果。
2.根据权利要求1所述的文档的检索装置，其特征在于，还包括：关键字扩展模块，所述关键字扩展模块对查询关键字进行扩展，并对扩展的查询关键词q中的每个单词wqi，根据以下公式的概率采样话题z：其中nqz是查询关键词q按照多项式分布采样话题z的次数；αq是查询关键词q的相d关多项式LDA先验；n 表示在所述话题识别模块中的全部文档数目，α和β分别为多项式分布θ和φ的Dirichlet先验。
3.一种文档的检索方法，包括：
步骤1、使用概率话题模型从文档集中识别话题，并根据识别到的话题得到文档的话题分布，具体包括：步骤11、根据Gibbs采样方法计算话题z上的后验概率分布：其中d为文档集D中的一个文档，z为文档d中的话题；为文档中的每个单词 对应的话题；di表示文档d中的第i个单词， 表示除di外的统计数值；
步骤12、根据后验概率分布计算θ和φ，其中θ为|D|个文档相关的文档-话题分布矩阵；φ为|T|个话题相关的话题-单词的分布矩阵；
步骤13、使用LDA话题模型从文档集中识别话题，其中文档集D的似然度为：其中θd为文档d在话题上的多项式分布，φz为话题z在单词上的多项式分布；ndz是将话题z关联到文档d的次数，nzv是单词wv由话题z生成的次数；V为互异单词的集合；
步骤14、计算文档的话题的多项式分布{p(z|d)}；其中P(z|d)是文档d生成话题z的概率；
步骤2、利用话题分布对每个文档计算其话题层次的随机游走排序得分，具体包括：采用以下公式获得话题z的随机游走排序得分：
其中，r[d，z]为文档d在话题z上的排序得分；D为所有文档的集合；T为所有话题的集合；z为文档d中的话题；λ为预设的随机跳跃参数，即游动者以等概率随机跳到文档集中的不同文档；γ为随机游走者点击一条链接访问相同话题的文档dl的概率，(1-γ)为随机游走者点击一条链接访问不同话题的文档dl的概率；
其中，P(d|d′，zi)是从文档dk到dl在相同话题zi上的转移概率，表示为P(dl|dk，zi)；
P(d，zi|d′，zj)是从话题zi的文档dk到话题zj的文档dl的转移概率，表示为P(dl，zj|dk，zi)；则步骤3、根据查询关键词及话题，计算文档相对于该查询关键词的相关性得分，将话题层次随机游走排序得分和相关性得分相结合得到检索结果，具体包括：步骤31、计算由话题模型生成查询关键词q的概率PLDA(q|d)；
步骤32、采用语言模型计算查询关键词q从文档d中生成概率PLM(q|d)；
步骤33、关键词q与文档相关性得分P(q|d)＝PLM(q|d)×PLDA(q|d)；
步骤34、将步骤2所得话题层次随机游走排序得分r[d，z]和相关性得分P(q|d)相结合得到检索结果。
4.根据权利要求3所述的文档的检索方法，其特征在于，所述步骤2和步骤3之间还包括：步骤a、对查询关键词进行扩展，并对扩展的查询关键词q中的每个单词 根据以下公式的概率采样话题z：其中nqz是查询关键词q按照多项式分布采样话题z的次数；αq是查询关键词q的相d关多项式LDA先验；n 表示在步骤1全部文档数目。
说明书 :
一种文档的检索方法和装置
技术领域
[0001] 本发明涉及一种检索技术，特别是指可以应用于网页检索的文档的检索装置及方法。
背景技术
[0002] 随着计算机和网络的普及，极大的改变了人们获取资讯的方式。但是如何从浩如烟海的万维网资讯中快速获得使用者所需的资料成为重要的研究课题。在万维网上，每一个网页都可以视为一个文档，而万维网可以认为是一个由无数个超级链接组合在一起的文档的集合。因此对于文档的检索中，其中很重要的一种方式就是基于超链接关系的分析。
[0003] 在现有技术的超链接关系的分析技术中，广泛应用到了随机游走。随机游走是基于随机数学理论，形式化地表述了行进随机步数的轨迹。例如现有的PageRank算法，其使用了随机游走技术通过万维网中的链接分析得到了每个页面的相对重要性程度。从直观上讲，一个网页如果出现在其他重要页面的超链接中，那么这个网页很可能也是一个重要的网页。其他基于随机游走的方法也相继提出，例如HITS。
[0004] 现有的随机游走方法仅仅使用了单一数值表示一个页面或文档的重要性，而没有考虑到其所讲述的内容中包含的话题信息。而异构网络中包含了丰富的潜在话题信息。
[0005] 因此，如果使用传统的随机游走模型对文档重要性进行排序，那些集中讨论热门话题的文档将更容易占领“统治”地位。例如，一个有关产品介绍或者在线订购的页面可能被大量的包含该产品信息的广告页面指向，这将会导致搜索系统在进行排序时会将其放置在靠前的位置上。因此，理想的解决办法就是该系统可以考虑页面中包含的潜在话题信息，并且根据不同的话题对于页面进行排序。对于不同话题的查询关键词，该模型根据话题层次的排序得分，系统可以返回给用户不同话题下的排序列表。
[0006] 近些时期，沿着该研究思路，有一些研究工作已经展开。例如话题敏感随机游走试图通过为每个页面引入分值向量突破单一重要性得分的限制。具体来讲，该方法假设每个页面都有很多相关联的话题，并使用偏向因子表示特定话题上的重要性。Nie等人研究了万维网搜索中的话题链接分析问题，并提出了话题PageRank以及话题HITS模型。但是，在这些方法中存在着严重的不足：所有的话题都需要预先指定，因此这些排序模型不易于扩展到新的领域中。
发明内容
[0007] 针对现有技术中存在的缺陷和不足，本发明的目的是提供一种文档重要性的排序装置及方法，以及应用上述的排序装置和方法对网页和文档进行检索的检索装置及方法，有效地解决现有的检索中排序不能够很好的适用于异构学术网络的问题。
[0008] 为了达到上述目的，本发明还提出了一种文档的检索装置，其特征在于，包括：
[0009] 话题识别模块，所述话题识别模块利用概率话题模型从文档集中识别话题，并根据识别到的话题得到文档的话题分布；
[0010] 随机游走模块，所述随机游走模块根据话题分布对每个文档计算随机游走排序得分；
[0011] 检索模块，所述检索模块根据查询关键字计算文档对于该查询关键字的相关性得分，并根据随机游走排序得分与相关性得分结合得到检索结果。
[0012] 其中，所述话题识别模块包括：
[0013] 参数计算子模块，所述参数计算子模块根据Gibbs采样方法计算话题z上的后验概率分布：
[0014]
[0015] 其中d为文档集D中的一个文档，z为文档d中的话题；为文档中的每个单词对应的话题；di表示文档d中的第i个单词， 表示除di外的统计数值；
[0016] 然后根据后验概率分布计算θ和φ，其中θ为|D|个文档相关的文档-话题分布矩阵；φ为|T|个话题相关的话题-单词的分布矩阵；
[0017] 话题识别子模块，所述话题识别子模块根据θ和φ，使用LDA话题模型从文档集中识别话题，其中文档集D的似然度为：
[0018]
[0019] 其中θd为文档d在话题上的多项式分布，φz为话题z在单词上的多项式分布；ndz是将话题z关联到文档d的次数，nzv是单词wv由话题z生成的次数；V为互异单词的集合；
[0020] 多项式分布子模块，所述多项式分布子模块根据所述话题识别模块识别的话题，生成文档的话题的多项式分布{p(z|d)}；其中P(z|d)是文档d生成话题z的概率。
[0021] 其中，所述随机游走模块包括：
[0022] 随机游走排序得分计算子模块，以根据文档话题的多项式分布计算随机游走排序得分：
[0023]
[0024] 其中，r[d，z]为文档d在话题z上的排序得分；D为所有文档的集合；T为所有话题的集合；z为文档d中的话题；λ为预设的随机跳跃参数，即游动者以等概率随机跳到文档集中的不同文档；γ为随机游走者点击一条链接访问相同话题的文档dl的概率，(1-γ)为随机游走者点击一条链接访问不同话题的文档dl的概率；
[0025] 其中，P(dl|dk，zi)是从文档dk到dl在相同话题zi上的转移概率，表示为P(d|d′，zi)；P(di，zj|dk，zi)是从话题zi的文档dk到话题zj的文档dl的转移概率，表示为P(d，zi|d′，zj)；则
[0026]
[0027] 其中，所述检索模块包括：
[0028] 概率计算子模块，所述概率计算子模块计算由话题模型生成查询关键词q的概率PLDA(q|d)，
[0029]
[0030] 其中θd为特定文档d在话题上的多项式分布；φz为特定的话题z在单词上的多项式分布；
[0031] 并采用语言模型计算查询关键词q从文档d中生成概率PLM(q|d)；
[0032] 查询关键词q与文档相关性得分P(q d)＝PLM(q|d)×PLDA(q|d)；
[0033] 将随机游走模块所得话题层次随机游走排序得分r[d，z]和相关性得分P(q|d)相结合得到检索结果。
[0034] 其中，所述装置还包括：
[0035] 关键字扩展模块，所述关键字扩展模块对查询关键字进行扩展，并对扩展的查询关键词q中的每个单词 根据以下公式的概率采样话题z：
[0036]
[0037] 其中nqz是查询关键词q按照多项式分布采样话题z的次数；αq是查询关键词q的相关多项式LDA先验；nd表示在话题识别模块中的全部文档数目，α和β分别为多项式分布θ和φ的Dirichlet先验。
[0038] 同时，本发明还提出了一种文档的检索方法，包括：
[0039] 步骤1、使用概率话题模型从文档集中识别话题，并根据识别到的话题得到文档的话题分布；
[0040] 步骤2、利用话题分布对每个文档计算其话题层次的随机游走排序得分；
[0041] 步骤3、根据查询关键词及话题，计算文档相对于该查询关键词的相关性得分，将话题层次随机游走排序得分和相关性得分相结合得到检索结果。
[0042] 其中，所述步骤1具体为：
[0043] 步骤11、根据Gibbs采样方法计算话题z上的后验概率分布：
[0044]
[0045] 其中d为文档集D中的一个文档，z为文档d中的话题；为文档中的每个单词对应的话题；di表示文档d中的第i个单词， 表示除di外的统计数值；
[0046] 步骤12、根据后验概率分布计算θ和φ，其中θ为|D|个文档相关的文档-话题分布矩阵；φ为|T|个话题相关的话题-单词的分布矩阵；
[0047] 步骤13、使用LDA话题模型从文档集中识别话题，其中文档集D的似然度为：
[0048]
[0049] 其中θd为文档d在话题上的多项式分布，φz为话题z在单词上的多项式分布；ndz是将话题z关联到文档d的次数，nzv是单词wv由话题z生成的次数；V为互异单词的集合；
[0050] 步骤14、计算文档的话题的多项式分布{p(z|d)}；其中P(z|d)是文档d生成话题z的概率。
[0051] 其中，所述步骤2具体为：
[0052] 采用以下公式获得话题z的随机游走排序得分：
[0053]
[0054] 其中，r[d，z]为文档d在话题z上的随机游走排序得分；D为所有文档的集合；T为所有话题的集合；z为文档d中的话题；λ为预设的随机跳跃参数，即游动者以等概率随机跳到文档集中的不同文档；γ为随机游走者点击一条链接访问相同话题的文档dl的概率，(1-γ)为随机游走者点击一条链接访问不同话题的文档dl的概率；
[0055] 其中，P(d|d′，zi)是从文档dk到dl在相同话题zi上的转移概率，表示为P(dl|dk，zi)；P(d，zi|d′，zj)是从话题zi的文档dk到话题zj的文档dl的转移概率，表示为P(dl，zj|dk，zi)；则
[0056]
[0057] 其中，所述步骤3具体为：
[0058] 步骤31、计算由话题模型生成查询关键词q的概率PLDA(q|d)；
[0059]
[0060] 步骤32、采用语言模型计算查询关键词q从文档d中生成概率PLM(q|d)；
[0061] 步骤33、关键词q与文档相关性得分P(q|d)＝PLM(q|d)×PLDA(q|d)；
[0062] 步骤34、将步骤2所得话题层次随机游走排序得分r[d，z]和相关性得分P(q|d)相结合得到检索结果。
[0063] 其中，所述步骤2和步骤3之间还包括：
[0064] 步骤a、对查询关键词进行扩展，并对扩展的查询关键词q中的每个单词 根据以下公式的概率采样话题z：
[0065]
[0066] 其中nqz是查询关键词q按照多项式分布采样话题z的次数；αq是查询关键词qd的相关多项式LDA先验；n 表示在步骤1全部文档数目。
[0067] 上述技术方案具有如下优点：本发明提出了一种文档检索装置及方法，能够使用统计话题模型自动从文档集中抽取话题，并根据话题层次随机游走，基于抽取的话题将每个文档的话题相关重要性进行打分，并给定查询关键词。然后根据发现的话题，计算文档相对于该查询关键词的相关性得分，并根据话题层次随机游走的排序重要性得分和相关性得分相结合得到检索结果。因此本发明相比较现有技术能够自动抽取话题，并使能够根据话题随机游走得分与相关性得分结合得到更好的检索结果。
附图说明
[0068] 图1是本发明优选实施例流程示意图；
[0069] 图2是异构网络具体实例的结构示意图；
[0070] 图3是调整参数γ后搜索结果的变化示意图；
[0071] 图4是搜索论文的结果和搜索专家的结果示意图；
[0072] 图5是调整参数t后搜索结果的变化示意图。
具体实施方式
[0073] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。
[0074] 万维网中的网页或其他存在关联的实体网络可以用含有链接的文档的集合表示，即G＝(D，E)，其中D表示所有文档的集合，E表示所有超级链接的结合，有向边d1→d2∈E表示文档d1有指向d2的超级链接。
[0075] 实施例1
[0076] 本发明提出的文档重要性的排序方法，其优选实施例包括：
[0077] 步骤一：话题建模
[0078] 步骤一的目的是使用概率话题模型从文档集中发现话题。概率话题模型可以有效地在文档集中挖掘话题。在这些方法中，通常假设文档是从|T|个概率模型的混合中生成。潜在Dirichlet分配(LDA)是一种广泛使用的话题模型。在该模型中，文档集D的似然度定义为：
[0079]
[0080] 其中，ndz是将话题z关联到文档d的次数，nzv是单词wv由话题z生成的次数。
[0081] 直观上讲，该方法假设在文档集D中共讨论了|T|个不同的话题。每个文档有P(z|d)的概率讨论话题z。而有最大概率的那个话题在一定程度上揭示了文档d的语义内容。根据话题模型，每个文档根据如下随机过程生成：首先文档(如网页等)的作者会根据文档的话题分布P(z|d)决定撰写的话题z，之后根据该话题上单词的分布P(w|z)从话题z上采样得到单词。
[0082] 在话题模型中，推理的目的是为了估计LDA模型中的未知参数：(1)|D |个文档相关的文档-话题分布矩阵θ和|T|个话题相关的话题-单词分布矩阵φ；(2)文档d中的每个单词 对应的话题 该方法使用Gibbs采样方法估计参数。具体来讲，该方法不直接估计模型的参数，相反仅仅估计z上的后验概率分布，再用z推理θ和φ。后验分布定义为：
[0083]
[0084] 其中， 的上标 表示除当前实例(文档d中的第i个单词)的统计数值。
[0085] 步骤二：话题层次随机游走
[0086] 在文档集上使用话题模型后，该方法得到了每个文档的话题分布。形式化讲，对于每个文档，使用{p(z|d)}(等价的写为θdz)表示话题的多项式分布。之后定义话题层次的随机游走。
[0087] 对于每个文档d，在该方法中关联着一个排序得分向量{r[d，z]}z，[0088] 其中每一个元素对应一个话题z。随机游走既在同一个话题的范畴内，同时也跨越不同的话题，沿着文档之间的超级链接进行。
[0089] 对于包含指向文档dl的超级链接的文档dk，该方法定义两种类型的文档间转移概率：话题内转移概率和话题间转移概率，即：
[0090]
[0091] 其中，P(dl|dk，zi)是从文档dk到dl在相同话题zi上的转移概率；P(dl，zj|dk，zi)是从话题zi的文档dk到话题zj的文档dl的转移概率。
[0092] 接下来在该方法中引入参数γ表示对于话题内转移或者话题间转移的偏好。因此该转移图如下形式化地描述了一个随机游走者的行为：随机游走者有γ的概率点击某一条链接访问相同话题的文档dl，并且有(1-γ)的概率点击某一条连接访问不同话题的文档dl。
[0093] 和PageRank类似，为每个文档d定义随机游走排序得分的公式：
[0094]
[0095] 其中，P(z|d)是文档d生成话题z的概率；和PageRank类似，可以定义随机跳跃参数λ，它允许游动者以等概率随机跳到文档集中的不同文档。
[0096] 步骤三：查询关键词建模
[0097] 步骤三是为了找到和查询关键词相关的文档。尽管这一步并不是必须的，但是该步骤有助于发现查询关键词的语义信息。由于查询关键词的长度通常较短，可见为查询关键词建模并不容易。为了确保能够找到正确的话题描述用户的查询意图，该方法中使用信息检索中通常使用的方法，即进行查询关键词扩展。具体来讲，对于查询关键词q中的每一个单词w，该方法从文档集中抽取若干高频共现词，并将它们添加到查询关键词中。考虑单词w的窗口大小邻域中出现的单词作为共现词，也就是说w前后的单词。该应用中设置窗口大小为1。之后，该方法在扩展的查询关键词上应用话题模型找到查询关键词相关的话题。对于扩展查询关键词q中的每个单词 最后根据如下的概率采样话题z：
[0098]
[0099] 其中，nqz是查询关键词q按照多项式分布采样话题z的次数；αq是查询关键词相d关多项式的Dirichlet先验；有上标d的n 表示在步骤一的推理过程之后统计的全部文档数目。例如， 表示在所有文档中单词w被分配到话题z中的次数。
[0100] 特别重要的是，该方法为查询关键词q额外进行一次生成过程。该生成过程和步骤一中的类似，只是为了查询关键词建模，该方法结合了文档建模的结果。具体的讲，该方法从Dirichlet先验αq中为每一个查询关键词q采样得到一个多项式分布；之后，对于每一个查询关键词中的单词 从多项分布中采样得到话题 生成过程依赖于查询关键词和文档的相关性。该过程后，该方法得到查询关键词-对应话题的分布{p(z|q)}，它包含了查询词的语义信息。
[0101] 步骤四：用话题层次随机游走进行搜索
[0102] 在最后一步中，该方法使用话题层次随机游走进行搜索。具体来讲，对于每一个文档d，该方法结合查询关键词q和文档的相关性得分以及在话题层次随机游走中得到的文档d的重要性排序得分。相似性得分根据如下公式计算：
[0103]
[0104] 但是，由于根据话题模型学到的话题通常是通用的，并不针对某个具体的查询关键词，因此在搜索中仅仅使用话题模型会造成结果过于粗糙。之前进行的实验中也证实了在信息检索中仅仅使用话题模型会降低检索性能。因此，为了在通用和具体中间找到平衡，该方法得到LDA模型和基于单词的语言模型的组合形式。
[0105] P(q|d)＝PLM(q|d)×PLDA(q|d)(7)
[0106] 其中，PLM(q|d)是根据语言模型，计算查询关键词q从文档d中生成概率。而PLDA(q|d)是由话题模型生成查询关键词的概率。
[0107] 该方法首先考虑两种将相关性得分和随机游走重要性排序得分相结合的方法，即：
[0108]
[0109] 及
[0110]
[0111] 其中，P(z|d)表示文档d生成话题z的概率，r[d，z]表示文档d在话题z上的重要性得分。
[0112] 上述方法对于所有话题上的查询关键词的生成概率进行求和。同样可以考虑使用查询关键词建模的结果。组合得分如下定义：
[0113]
[0114] 其中，在采样过程中，zw为查询关键词q中的单词w所选择的话题。
[0115] 实施例2
[0116] 本发明提出的文档的检索装置，其优选实施例包括：
[0117] 话题识别模块，所述话题识别模块利用概率话题模型从文档集中识别话题，并根据识别到的话题得到文档的话题分布；
[0118] 随机游走模块，所述随机游走模块根据话题分布对每个文档计算随机游走排序得分；
[0119] 检索模块，所述检索模块根据查询关键字计算文档对于该查询关键字的相关性得分，并根据随机游走排序得分与相关性得分结合得到检索结果。
[0120] 其中，所述话题识别模块包括：
[0121] 参数计算子模块，所述参数计算子模块根据Gibbs采样方法计算话题z上的后验概率分布：
[0122]
[0123] 其中d为文档集D中的一个文档，z为文档d中的话题；为文档中的每个单词对应的话题；di表示文档d中的第i个单词， 表示除di外的统计数值；
[0124] 然后根据后验概率分布计算θ和φ，其中θ为|D|个文档相关的文档-话题分布矩阵；φ为|T|个话题相关的话题-单词的分布矩阵；
[0125] 识别话题子模块，所述识别话题子模块根据θ和φ，使用LDA话题模型从文档集中识别话题，其中文档集D的似然度为：
[0126]
[0127] 其中θd为文档d在话题上的多项式分布，φz为话题z在单词上的多项式分布；ndz是将话题z关联到文档d的次数，nzv是单词wv由话题z生成的次数；V为互异单词的集合；
[0128] 多项式分布子模块，所述多项式分布子模块根据所述话题识别模块识别的话题，生成文档的话题的多项式分布{p(z|d)}；其中P(z|d)是文档d生成话题z的概率。
[0129] 其中，所述随机游走模块包括：
[0130] 随机游走排序得分计算子模块，以根据文档话题的多项式分布计算随机游走排序得分：
[0131]
[0132] 其中，r[d，z]为文档d在话题z上的排序得分；D为所有文档的集合；T为所有话题的集合；z为文档d中的话题；λ为预设的随机跳跃参数，即游动者以等概率随机跳到文档集中的不同文档；γ为随机游走者点击一条链接访问相同话题的文档dl的概率，(1-γ)为随机游走者点击一条链接访问不同话题的文档dl的概率；
[0133] 其中，P(d|d′，zi)是从文档dk到dl在相同话题zi上的转移概率，表示为P(dl|dk，zi)；P(d，zi|d′，zj)是从话题zi的文档dk到话题zj的文档dl的转移概率，表示为P(dl，zj|dk，zi)；则
[0134]
[0135] 其中，所述检索模块包括：
[0136] 概率计算子模块，所述概率计算子模块计算由话题模型生成查询关键词q的概率PLDA(q|d)，
[0137]
[0138] 并采用语言模型计算查询关键词q从文档d中生成概率PLM(q|d)；
[0139] 关键词q与文档相关性得分P(qd)＝PLM(q|d)×PLDA(q|d)；
[0140] 将随机游走模块所得话题层次随机游走的排序得分r[d，z]和相关性得分P(q|d)相结合得到检索结果。
[0141] 其中，所述检索装置还包括：
[0142] 关键字扩展模块，所述关键字扩展模块对查询关键字进行扩展，并对扩展的查询关键词q中的每个单词 根据以下公式的概率采样话题z：
[0143]
[0144] 其中nqz是查询关键词q按照多项式分布采样话题z的次数；αq是查询关键词qd的相关多项式LDA先验；n 表示在话题识别模块中的全部文档数目。
[0145] 下面应用一个具体事例对本发明进行进一步说明。
[0146] (1)实验集
[0147] 本发明可以用于异构网络中多种类型结点的搜索。在实验评估环节，我们重点在学术网络中进行分析研究。学术网络中中包含多种类型的结点，例如论文、期刊会议、作者等，如图2所示。在图中，相同类型的结点之间存在着若干的关联，例如论文之间有向的引用关系，作者之间有无向的合作关系。不同类型的结点之间也存在着某些关系，如作者会发表论文，论文会发表在期刊会议中等等。这些结点和边组成了异构学术网络。我们在学术研究者社会网络搜索系统ArnetMiner的环境中进行评估。200个示例话题及其有代表性的研究者，论文可以参见示例话题页面(http://arnetminer.org/topicBrowser.do)。每篇论文用标题表示其文档内容，对于作者(专家)，用他的全部论文的标题串表示，当然也可以使用论文的摘要或者全文表示论文的文档内容。
[0148] 我们在ArnetMiner的一个子数据集(包含14，134个作者以及10，716篇论文)上进行实验。由于目前并没有一个标准答案的数据集，我们从ArnetMiner的日志中选择并列出了若干最频繁的查询词。处于评估的考虑，我们使用合并相关评估方法并结合人为判断。具体来讲，对于每个查询关键词，我们首先从三个相似的系统：Libra(http://libra.msra.cn/)、Rexa(http://rexa.info/)以及ArnetMiner(http://www.arnetminer.org)的前30个查询结果中合并结果。然后，两个计算机专业的教师和五个研究生对结果进行人工标注。
四个评价等级(3、2、1以及0)分别用来表示绝对权威、权威、临界权威以及不权威。我们通过该方法分别进行论文搜索和专家搜索，并在测试集上对于这两类应用的性能进行评测。
四个评价等级(3、2、1以及0)分别用来表示绝对权威、权威、临界权威以及不权威。我们通过该方法分别进行论文搜索和专家搜索，并在测试集上对于这两类应用的性能进行评测。
[0149] (2)评估方法
[0150] 在这些实验中，我们使用P@5、P@10、P@20、R-pre和均值平均查准率(MAP)进行评估。
[0151] 其中P@k表示系统对于查询关键词返回的前k个结果的查准率，定义为：
[0152]
[0153] R-pre表示检索出R篇文档时的准确率，其中R是在标准答案集中与查询关键词相关的文档的数目。
[0154] MAP表示每个查询关键词对应的准确率的平均值。具体来说，对于一个给定的查询关键词，根据前k个结果的查准率，首先计算平均查准率：
[0155]
[0156] 而MAP是在全部数据集上AP的平均值。
[0157] (3)基线方法
[0158] 我们使用基于单词的语言模型(LM)、BM25、LDA、PageRank(PR)作为基线方法。在基于单词的语言模型中，我们计算查询关键词短语和论文或者专家之间的相关性。在BM25中，我们计算查询关键词和论文或者专家的相似度，记为SBM25(d，q)。对于PageRankSPR(d)，我们使用Page介绍的方法计算论文或者专家的重要性。对于话题PageRank STPR，我们使用Nie描述的方法。
[0159] 同时考虑上述基线方法的若干组合形式，包括LM+LDA、LM*LDA、LM*PR、LM+PR、LM*LDA*PR以及BM25*PR。
[0160] SLM+LDA(d，q)＝(1-t)PLM(d|q)+tPLDA(d|q)
[0161] SLM*LDA(d，q)＝PLM(d|q)·PLDA(d|q)
[0162] SLM*PR(d，q)＝PLM(d|q)·PR(d) (11)
[0163] SLM+PR(d，q)＝(1-t)PLM(d|q)+tPR(d)
[0164] SLM*LDA*PR(d，q)＝PLM(d |q)·PLDA(d|q)·PR(d)
[0165] SBM25*PR(d，q)＝SBM25(d，q)·PR(d)
[0166] (4)实验结果
[0167] 实验中的参数如下设置：对于LDA模型，设置超参数α＝0.1以及β＝0.1，话题的数目设置为不同的值(分别为5、15以及80)。在话题层次随机游走中，设置随机跳转因子λ＝0.15，而将因子γ设置为以0.1为间隔从0取到1.0。公式11中LM和LDA的组合权重t分别在0、0.1、0.2、0.4、0.6、0.8和1.0取值上进行试验，调整这些参数，并报告最佳性能。
[0168] 表格1和表格2展示了使用发明的方法(TPR+、TPR*和TPRq)与基线方法的实验结果比较。从中可见该方法在大部分的评价指标中胜过基线方法。使用TPR+方法获得了最佳的性能。
[0169] 表1搜索论文的结果
[0170]模型 p@5 p@10 p@20 R-pre MAP MRR B-pre
LM 0.4286 0.4000 0.4000 0.1094 0.4876 0.6786 0.2732
LDA 0.0286 0.0429 0.0500 0.0221 0.1272 0.1180 0.0238
LM+LDA 0.4000 0.4714 0.4000 0.1561 0.5325 0.7659 0.2808
LM*LDA 0.4000 0.4714 0.4714 0.1605 0.5009 0.4728 0.3236
TPR 0.7143 0.5143 0.4857 0.2201 0.6311 0.8333 0.3687
BM25 0.4286 0.4571 0.4143 0.1196 0.4712 0.6000 0.2734
LM*PR 0.6571 0.6714 0.5214 0.1985 0.6541 0.7976 0.4055
LM+PR 0.4286 0.4286 0.4000 0.2100 0.4918 0.6905 0.3107
BM25*PR 0.6571 0.5429 0.4857 0.2094 0.6115 0.8571 0.3780
LM*LDA*PR 0.6571 0.6000 0.5071 0.2146 0.6404 0.7262 0.4091
TPR+ 0.7143 0.5714 0.5286 0.2065 0.7139 1.0000 0.4193
TPR* 0.7429 0.6000 0.5429 0.2255 0.6961 0.8333 0.4251
TPRq 0.6286 0.6286 0.4929 0.1838 0.6235 0.7262 0.3874[0171] 表2搜索专家的结果
LM 0.4286 0.4000 0.4000 0.1094 0.4876 0.6786 0.2732
LDA 0.0286 0.0429 0.0500 0.0221 0.1272 0.1180 0.0238
LM+LDA 0.4000 0.4714 0.4000 0.1561 0.5325 0.7659 0.2808
LM*LDA 0.4000 0.4714 0.4714 0.1605 0.5009 0.4728 0.3236
TPR 0.7143 0.5143 0.4857 0.2201 0.6311 0.8333 0.3687
BM25 0.4286 0.4571 0.4143 0.1196 0.4712 0.6000 0.2734
LM*PR 0.6571 0.6714 0.5214 0.1985 0.6541 0.7976 0.4055
LM+PR 0.4286 0.4286 0.4000 0.2100 0.4918 0.6905 0.3107
BM25*PR 0.6571 0.5429 0.4857 0.2094 0.6115 0.8571 0.3780
LM*LDA*PR 0.6571 0.6000 0.5071 0.2146 0.6404 0.7262 0.4091
TPR+ 0.7143 0.5714 0.5286 0.2065 0.7139 1.0000 0.4193
TPR* 0.7429 0.6000 0.5429 0.2255 0.6961 0.8333 0.4251
TPRq 0.6286 0.6286 0.4929 0.1838 0.6235 0.7262 0.3874[0171] 表2搜索专家的结果
[0172]模型 p@5 p@10 p@20 R-pre MAP MRR B-pre
LM 0.4000 0.2714 0.1500 0.3274 0.5744 0.8095 0.3118
LDA 0.0857 0.0571 0.0286 0.0595 0.2183 0.2063 0.0506
LM+LDA 0.6571 0.4429 0.2500 0.5881 0.7347 0.8929 0.6012
LM*LDA 0.5714 0.3714 0.2429 0.5107 0.6593 0.8929 0.4926
TPR 0.3714 0.2286 0.1500 0.2964 0.3991 0.4976 0.2267
BM25 0.4857 0.2857 0.1500 0.4214 0.6486 0.7857 0.3775
LM*PR 0.6857 0.5286 0.2786 0.6357 0.7864 0.9286 0.7183
LM+PR 0.6571 0.4429 0.2500 0.5881 0.7338 0.8929 0.6012
BM25*PR 0.6286 0.4857 0.2714 0.6179 0.7392 1.0000 0.6526
LM*LDA*PR 0.6571 0.4857 0.2571 0.6655 0.7661 0.9048 0.6831
TPR+ 0.7143 0.4857 0.2714 0.7179 0.8029 1.0000 0.7151
TPR* 0.7143 0.4857 0.2500 0.6512 0.7424 0.8571 0.6650
TPRq 0.6571 0.4571 0.2714 0.6179 0.7084 0.7857 0.6261[0173] (5)参数调整
LM 0.4000 0.2714 0.1500 0.3274 0.5744 0.8095 0.3118
LDA 0.0857 0.0571 0.0286 0.0595 0.2183 0.2063 0.0506
LM+LDA 0.6571 0.4429 0.2500 0.5881 0.7347 0.8929 0.6012
LM*LDA 0.5714 0.3714 0.2429 0.5107 0.6593 0.8929 0.4926
TPR 0.3714 0.2286 0.1500 0.2964 0.3991 0.4976 0.2267
BM25 0.4857 0.2857 0.1500 0.4214 0.6486 0.7857 0.3775
LM*PR 0.6857 0.5286 0.2786 0.6357 0.7864 0.9286 0.7183
LM+PR 0.6571 0.4429 0.2500 0.5881 0.7338 0.8929 0.6012
BM25*PR 0.6286 0.4857 0.2714 0.6179 0.7392 1.0000 0.6526
LM*LDA*PR 0.6571 0.4857 0.2571 0.6655 0.7661 0.9048 0.6831
TPR+ 0.7143 0.4857 0.2714 0.7179 0.8029 1.0000 0.7151
TPR* 0.7143 0.4857 0.2500 0.6512 0.7424 0.8571 0.6650
TPRq 0.6571 0.4571 0.2714 0.6179 0.7084 0.7857 0.6261[0173] (5)参数调整
[0174] (A)调整参数γ
[0175] 图3(a)通过MAP展示了使用TPR+和TPR*进行论文搜索的性能，其中将γ取0到1.0之间的某个固定值(选取间隔为0.1)，记为cons tantγ，在图中用坐标点表示。同时还将γ设为随话题和文档变化的动态的值P(z|d′)，并记为variableγ，在图中用一条虚线表示。对于搜索专家，如见图3(b)所示，使用同样的参数值设置调节该参数。可以看出对于不同的γ设置，搜索专家更为稳定，即对于γ的变化影响较小。
[0176] (B)调整参数|T|
[0177] 对于参数话题个数|T|，调整|T|分别为5、15和80。搜索论文的结果在图4(a)中展示，搜索专家的结果在图4(b)中展示。在论文搜索，当把|T|设置为15时，使用大部分方法都能得到最佳的结果。在专家搜索中，当把话题数目设置为5时，得到最佳的结果。这或许是因为相比于确定一篇论文的话题，更难准确判断一个专家所感兴趣的领域。
[0178] (C)调整参数t
[0179] 如图5所示，调整参数t从0变化到1.0，间隔为0.2。可以看出当t在0.2和0.8之间变化时结果较为稳定。
[0180] (6)实例分析
[0181] 为了进一步表明研究话题层次随机游走的动机，我们进行一个具体的案例研究。我们选择两个查询关键词分析他们的语义，查询关键词为“natural language processing”(自然语言处理)和“intelligent agents”(智能代理)。对于这两个查询关键词中的每一个单词，我们为其挑选最有代表性的若干话题，也就是说我们从15个话题中删除那些和这些单词关联性均较弱的话题(通常他们之间的生成概率仅仅是模型中的平滑系数)。我们得到单词在话题#4、#7、#10、#13上的分布，如表3所示。从中可见，查询关键词“naturallanguage processing”主要对应于话题#10，而“intelligent agents”主要对应话题#4和#7。
[0182] 表4展现了分别通过PageRank和话题层次随机游走(TPR+)计算得到的重要性得分。当使用TPR+用查询关键词“naturallanguage processing”搜索论文时，第一个文档VerifiableSemantics for Agent Communication Languages(代理通讯语言中验证语义)并没有被检索得到，这主要是因为该文档在话题#10上的重要性得分较低，而第二个文档Probabilistic Parsing Using LeftCorner Language Models(用左角落语言模型进行概率句法分析)被TPR+检索出。但是，当使用PagePank用“natural languageprocessing”搜索论文时，第一个文档由于其较高的PageRank得分被检索得到，而第二个文档没有被检索到。上述过论在一定程度上说明了我们的方法的合理性。当我们用查询关键词“intelligentagents”搜索论文时，第四个文档Agent-Based Business ProcessManagement(基于代理的商务流程管理)可以被我们的TPR+方法成功检索出来，但是PageRank并不能做到，而相反PageRank选择了没有被TPR+检索出的第三个文档The GRAIL concept modelinglanguage for medical terminology(医学术语的GRAIL概念建模语言)，这主要是由于该文档被大量的论文引用。
[0183] 表3查询关键词中单词的概率分布
[0184]单词 话题#4 话题#7 话题#10 话题#13
natural 0.000018 0.000018 0.018966 0.000022
language 0.000018 0.002946 0.043322 0.000022
processing 0.000018 0.000018 0.012652 0.000022
intelligent 0.002363 0.022158 0.000023 0.000022
agents 0.037541 0.034784 0.000023 0.000022
natural 0.000018 0.000018 0.018966 0.000022
language 0.000018 0.002946 0.043322 0.000022
processing 0.000018 0.000018 0.012652 0.000022
intelligent 0.002363 0.022158 0.000023 0.000022
agents 0.037541 0.034784 0.000023 0.000022
[0185] 表4用TPR+和PageRank搜索四篇文档的重要性得分
[0186]
[0187] 从实验结果可以看出，发明的方法在两个不同任务上的测试结果都优于基线方法。实验表明，我们提出的话题层次随机游走是切实有效的。
[0188] 以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和变型，这些改进和变型也应视为本发明的保护范围。