论文部分内容阅读
相似科技文献检索在学术研究中占有十分重要的比重。随着科技文献数据的指数级增长，传统的基于文本内容的相似度检索方法在实际应用中遇到了精度与速度的瓶颈。近年来，研究焦点越来越多地转移到依据文献间关系的相似度检索，特别是基于图结构的相似文献检索。当前，一种有效的相似度检索方法就是首先构建以单篇文档为节点的文档网络图，然后利用网络节点相似度评价指标进行进一步分析研判。SimRank则为目前应用较广泛的网络节点相似度评价指标之一。本文研究了的SimRank算法的优化问题，并探索了SimRank的优化算法在科技文献检索中的应用。 SimRank的基本思想可以概括为两个节点的邻居越相似，这两个节点越相似；即两个节点的相似度由其邻居节点的相似度决定。然而，目前SimRank的计算方式时间和空间开销巨大，在实际应用中表现并不出色。目前主流的算法主要是基于SimRank的矩阵迭代形式，该方法以整个文档网络为输入进行迭代，每次迭代需要更新全局网络的所有点对。一方面，其时空开销巨大，可扩展性不好，实际应用效果不理想；另一方面，实际应用仅关心相似度较高的文献对，而其计算结果为整个网络所有文献对的相似度，结果利用率十分低。针对此问题，本文依据SimRank的随机游走模型设计了一种Top-kSimRank算法框架，旨在及时排除相似度较低的点对，快速和精确地计算出相似度较高的点对，并使用实际数据测试其应用效果。 首先，本文依据SimRank的随机游走模型，设计了SimRank的增量算法。增量算法的依据是SimRank与从点对出发的两条随机路径随机游走的首次相遇概率的等价关系。增量算法的优点在于其每次迭代过程不需要重新计算，仅在上次迭代结果上继续增加此次迭代相似度值，使得结果非递减，十分适合阈值与非候选点的判定。其次，本文根据增量算法，设计了SimRank的迭代删点框架，该框架可快速识别非候选点并删除，以节约时空开销。在该框架下，本文定义了“超点”的概念，并设计了与基于超点的上界作为删点的依据。与已有的基于等比数列求和的上界相对比，本文设计的基于超点的上界考虑了点在网络中的临接关系，能够提供精度更高的上界，而且计算时空开销很小。本文还在迭代删点框架下设计了基于超点的上界的使用方法，可以在不必完全算出基于超点上界的情况下提早删除部分非候选点，更有效地节约了时间成本，且进一步压缩了空间开销。最后，考虑到现实中海量数据的问题，本文综合了基于等比数列求和的上界与基于超点的上界设计了针对大网络的算法优化策略。 为了进一步评价所提技术的实际效用和意义，本文利用真实数据开展了应用研究。对于已有的文献数据，以单篇文档为节点，文档间引用关系为边建立文档网络图。利用本文所提技术进行文档相似度检索，实验结果表明本文所提技术时间和空间开销均较小，符合实际应用需求。