微博中基于增强型倒排索引的特定文档影响力估计算法

2014-09-15司宏伟

计算机工程与科学 2014年3期

关键词：语料库文档影响力

司宏伟

(国防科学技术大学计算机学院，湖南长沙 410073)

微博中基于增强型倒排索引的特定文档影响力估计算法

司宏伟

(国防科学技术大学计算机学院，湖南长沙 410073)

微博搜索系统中，将微博帖子根据搜索相关性和重要性进行排序，并通过列表的方式返回结果，是目前信息内容的主要展示手段。基于向量空间模型的打分函数被广泛地应用于该类系统中。事实上，微博系统中的帖子重要性打分函数实际取值并不为用户所见，文档的影响力通过排名的方式表现出来。对于一个检索外的文档，如何衡量其在信息检索系统文库中的影响力？一般搜索引擎或信息检索系统并不能很好地回答该问题。在微博短文本的基础上引入了社交影响力这一概念，并通过在文本倒排索引基础上设置反向位置标记，给出了一种全新的影响力度量指标，有效地回答了前述问题。理论分析和数据实验验证了算法的有效性和效率。

信息获取;倒排索引;TFIDF指标;索引标记

1 引言

随着信息技术的快速发展和互联网应用的普及，社会各行业对信息化需求不断增加，产生了大量的信息内容，极大促进了信息检索系统的发展。特别是近年来，以微博为代表的社交网络获得了快速的发展，受社交网络的推动，信息传播模式快速朝着去中心化的方向发展，人类使用互联网的方式产生了深刻变革：由简单信息搜索和网页浏览转向网上社会关系的构建与维护、基于社会关系的信息创造、交流和共享。

对于一个特定的信息内容，如何快速度量其在微博上的影响力呢？微博中，社会个体通过各种连接关系在社交网络上构成“关系结构”，基于社交网络的关系结构，大量网络个体围绕着话题内容而聚合，相互影响、作用、依赖，形成具有共同行为特征的“网络群体”；各类“网络信息”得以快速发布并传播扩散形成社会化媒体，反馈到现实社会，从而使得社交网络与现实社会间形成互动，并对现实世界产生影响。正是因为这个原因，以微博为代表的社交网络中，信息内容的影响力度量方法应该兼顾信息内容本身的影响力和社交网络对其的放大作用。

传统信息检索应用中，用户通过输入一组关键词，文档检索系统返回一组文档列表，其中列表中的文档根据与查询(关键词)的相关程度进行排名。向量空间模型作为一种用于衡量文档间相关度的模型，被广泛地应用于该类系统中[1,2]。在该模型中，文档和针对文档的查询都被模型化为由关键词组成的多维向量空间，而文档与查询间的相关程度可以由文档向量与关键字向量的夹角来进行衡量，从而作为信息检索系统排列文档的依据。作为一种信息检索系统中的打分函数，向量空间模型有多种变种。公式(1)展示了一种基于余弦相似度的向量空间模型的例子。

relevance(d,q)=cosθ=(d·q)/(|d||q|)

(1)

其中，d表示文档向量，而q表示关键词向量。余弦为零表示检索词向量垂直于文档向量，即没有符合，也就是说该文档不含此检索词。目前这种基于向量空间模型的方法被广泛应用在了各类微博搜索引擎中。具体来说，文档向量模型表现了微博帖子(文档，本文用d表示)和查询关键词(本文用q表示)之间的关联关系，关联越紧，打分函数取值越大，对应内容排名也就越高，这种排名反映出了文档的影响力。

在微博中，文档是通过社交网络中节点间的通道进行传播的，因此节点间的结构特性极大地影响着内容的传播能力。而在社交网络中，文档通过社交网络中的信息通道传播，直接将上述模型应用到社交网络中，并不能体现文档的影响能力。针对这一问题，部分微博类社交网络应用，例如新浪微博，常利用微博文档所特有的“转发数”来衡量文档重要与否，即一个文档获得转发越多，这个文档越重要，其检索系统将文档向量模型与转发数结合，综合计算文档重要性指标。随着基于社交网络和微博营销等业务的快速发展，微博水军等快速发展，使用“转发量”或“点击率”的文档重要性衡量方法的客观性逐渐获得质疑。针对这一问题，本文给出了一种改进的解决方案，我们创新性地将文档向量模型和基于链接的节点权威性度量方法，通过一种多准则约束的排序策略，有机地结合在一起。此外，本文提出的方法还在广告收益估计、新闻舆论影响评估等领域具有重要的作用和广阔的前景。

本文的主要思想是在充分预处理数据全集的前提下，通过对索引设置“相关度反向排名标记”，使微博的检索系统具有快速估计新文档在不同查询下排名的能力。基于向量空间模型和倒排索引，设计中实现了一种新型的索引结构，并结合海量文本管理中数据规模庞大、数据更新快等特点，结合分布式集群化的特点，设计了一种高速的、可扩展的索引更新策略。

2 问题定义

通常意义上讲，衡量一篇特定文档在一个文档集合中的影响力往往要考虑多种因素，例如文档的时效性、文档所表述的观点态度、文档发表的时机和场合、社交网络对信息的放大效果等。而且对于特定读者，文档影响力的衡量具有强烈的主观性，即每个读者都会站在自己的角度上，对影响力的认识也有着不同的理解。例如，体育类的新闻往往对财经类读者缺乏吸引力。因此，文档影响力的衡量是一个复杂的过程，且方法并不具有唯一性。

本文考虑在社交网络环境下，一个特定文档的影响力应至少由两部分组成，即信息内容本身的影响力和社交网络中作者的权威性。

定义1 社交影响力模型：用A(d)表示文档的影响力度量指标，它由两个要素组成，即A(d)=αr(d)+βsi(d)，其中r(d)表示文档d和查询关键词的相关程度，si(d)表示文档d在社交网络中所处的位置节点的固有影响力，α和β表示加权因子。

r(d)表示信息内容和用户查询的关联程度。其意义表示在一般信息检索系统中，信息内容在特定用户查询下的打分函数取值。r(d)的实现并不唯一，本文使用上一节介绍的向量空间模型实现。si(d)表示文档d在社交网络中的位置权威性，通过其作者在社交网络中的节点权威性进行度量。在社交网络中，基于链接的节点权威性度量函数是一种常见的度量节点社会地位的方法。本文采用了一种类PageRank的节点权威性度量函数。

si(d)=A(u)=

其中，A(u)表示帖子d的博主u的权威性指标，M(u)表示u的邻居集合，表示阻尼因子,L(v)表示贴子的数量。上述公式表示了一种权威性传递的思想。本文认为一个节点在社交网络中的权威性指标取决于其周围的邻居，体现了一种信息传递和社交的思想。

社交影响力模型使用了文档向量空间模型和基于链接的作者权威性度量函数取值两部分的线性组合作为衡量一个文档影响力的方法。本文中公式(1)的文档向量空间模型中，cosθ的取值在0～1，由于si是一种概率模型，其取值也在0～1，因此可以简单推算出，由于A(d)=αr(d)+βsi(d)，如果文档库中文档数量大于1，且社交网络中节点数量大于1，则必然有0

定义2 基于排名的文档影响力：给定一个关键字集合K={k1,…,kn}和语料库C={d1,…,dn}，其中，di=〈km,…,kj〉∈D代表一个由关键字序列组成的文档；给定一个关键词，在关键词上的的排名估计查询函数表示为RankD:D×K→N，Rank(d,k)=r表示在语料库C中，有且仅有r-1个d′≠d，使relevance(d′,k)>relevance(d,k)，即文档d在关键字k查询下在C中的排名。

排名估计查询返回一个文档在特定查询下的排名，需要注意的是，排名是一个全局概念，要获得文档d在特定查询k下的排名，需要通过比较所有其他文档和k的相关程度才能获得结果；而对海量文本系统，其值可能达到千万甚至上亿的规模，这样规模的比较操作显然无法满足大规模系统的需要。信息检索系统通常使用倒排索引(Inverted Index)，对于内容待定的文档，我们可以将文档插入语料库，更新索引，并执行查询来获得文档的排名；由于倒排索引可以将相似度比较次数限定在包含有k的文档集中，可以有效减少比较次数。然而，这种操作会对索引产生不必要的更新开销，特别是对于内容待定的文档，内容往往需要多次修改，频繁更新索引会带来大量索引碎片，从而影响全系统效率。

如何在不对文档索引进行更新的前提下，估计文档在特定查询下的排名，依然是一个具有挑战性及实际应用价值的问题。

3 相关工作

3.1 社交网络的影响力估计方法

一般来说，国内外对社交网络信息传播学影响的研究主要有经济学方法、传播学方法和概率论方法等。1992年，纽约大学的Shenoy P P等人[1]利用经济学方法，提出了基于效用评价的信息传播影响力求解方法，利用一种可替换公式，基于效用评价系统对信息传播影响力问题进行表示和求解。1999年，丹麦奥尔堡大学的Madsen A L等人[2]提出了一种基于熵的网络信息传播的影响力评估函数方法，通过在强连接树中进行传播信息的影响力推理估算。2006年，加拿大西蒙菲莎大学的McCandless L C等人[3]利用概率论，提出了基于蒙特卡罗的信息传播计算方法，但是这种类型的影响力分析方法不能有效揭示非线性关系。同时，研究者还探讨了概率结构模型的影响力分析方法，如美国匹斯堡大学的Wang H等人[4]研究发现，贝叶斯网络对于参数概率的变化非常敏感，并论证了敏感度分析对贝叶斯网络参数分析非常有效，但这些贝叶斯网络敏感度分析方法还仅涉及到单个参数；荷兰乌特勒支大学的Renooij S等人[5]将贝叶斯网络灵敏性分析延伸到多个参数，利用动态概率结构模型进行影响力的敏感度分析等。2006年，法国巴黎大学的Maes S等人[6]基于多Agent因果概率图模型给出了一种利用部分信息的影响力分析方法。

本文的目标是在已知节点影响力计算方法的前提下，快速估计未知文档(新文档)在文档库中的影响力指标。上述方法更侧重通过量化分析社交网络中节点的传播特性来分析节点的影响力，与本文的需求和定义有较大的差异。

3.2 倒排索引与TFIDF函数

TFIDF(Term Frequency Inverse Document Frequency)是一种常见的向量空间模型的实现，是一种统计学模型，用于衡量一个词对于语料库中文档的重要性，其值与词在特定文档中的频率成正比，与该词在其他文档中的频率呈反比。TFIDF[7～9]函数由两部分组成，其中，tf表示词的词频，指的是某一个给定的词在文档中出现的频率；idf表示反向文档频率，表示一个词在一个特定文档中的重要性，是一个词在语料库中普遍重要性的度量，由总文档数目除以包含该词语的文档的数目，再对得到的商取对数。在系统实现中，人们通常结合TFIDF，使用倒排索引组织文档索引。倒排索引也常被称为反向索引、置入档案或反向档案。文档的倒排索引由形如〈t,posting〉的结构组成，每个元组由一个词语t引导，posting中存储包含这个词语的文档列表，即Score(d，t)>0的文档。为了提高查询效率，posting中的文档通常根据文档与t的相关度Score(d,t)进行排序。

本文结合倒排索引中相关度排序的这个特点，提出了一种增强型的倒排索引方法。

4 基于位置标记的索引

倒排索引的建立过程通常包含几个步骤：(1)文档解析。将不同的文档存储格式转换为统一的字符串形式。(2)关键词提取。这个步骤主要完成包括中文分词、去除停用词、大小写转换、时态还原等操作。(3)建立、存储倒排索引。将关键词、文章号、关键词的出现位置加入到前面所述的倒排索引数据结构中，将倒排索引数据结构存储到数据库或文件等持久化设备中。假设综合分析文档d的全局影响力，需要对任意一个可能获取到d的查询，都要进行排名。对于已经建立了倒排索引的语料库，本文给出了一种直观算法。

4.1 简单算法

对于任意ti∈d，首先计算tfi；之后对于其他文档dj∈{d|ti∈d}，计算tfi,j，并对TF值进行排序，从而获得文档d在ti下的排名(单关键词查询无需计算IDF)。

算法1 简单算法

输入:文档dm，语料库C;

输出:影响力向量ri。

变量tfi向量：dm中词语的TF值向量

1. 预操作建立倒排索引

2. FOR eachti∈dm

3.tfi=ni,m/∑knk,m;

4. FOR eachdj∈{d|ti∈d}

5.tfi,j=ni,j/∑knk,j;

6. END FOR

7. 计算tfi在tfi,j中的位置

8. 输出ri

9. END FOR

10.结束

算法1描述了简单算法的全过程。要估计文档d中在其所包含的所有词语{t|t∈d}上的影响力，该算法需要执行∑t:t∈d|{dj|t∈dj}|次tfi,j运算操作，并对每个t∈d，都要进行一次规模为|{dj|ti∈dj}|的排序并插入。对于长文档在大规模语料库中的影响力估计，开销很大。通常搜索引擎或文档检索系统会预先计算并使用矩阵存储每个文档的值，这样可以达到使用存储空间换取效率的目的，并在对倒排索引的posting列表进行降序排列时，使用阈值TA(Threshold Algorithms)算法降低排序开销。即使在这样的条件下，对文档在大规模语料库中的影响力分析，尤其是对流行词语的分析，仍然面临着超长posting列表的问题，依然具有相当的挑战，仍然需要占用大量的空间来存储矩阵，也对索引的有效组织带来了困难。

4.2 带有反向位置标记的扩展索引

本文在一般倒排索引的基础上，通过添加反向位置标记实现了扩展索引结构，系统体系结构如图1所示。该扩展索引结构具有自更新和自调整的能力，当新文档到来的时候，扩展索引随倒排索引自动更新，并透明地进行自调整优化。当用户进行一般关键字查询，即keyword-posting查询时，系统通过原倒排索引完成结果返回；当用户执行影响力评估操作时，查询首先通过扩展索引进行结果预估，之后通过倒排索引进行结果精化。

Figure 1 System architecture图1 系统体系结构

图2是本文设计的扩展索引结构。为了使传统的倒排索引具有能够快速计算特定文档序的功能，本文对一般倒排索引进行了如下改进：(1)对倒排索引的每个反向链表，均按照对应词语的TF值进行降序排列；(2)对于降序排列的0,k,2k,…,nk位置,记录其对应文档的tfi值mi,n、代表词语ti的nk位置的tfi值。

Figure 2 Extent inverted index structure(k=3)图2 k=3的扩展倒排索引结构

在实际实现中，我们称这些位置为反向位置标记(Milestone)，在本节描述的索引结构中，该值采用外部分离存储的方式，无需修改原倒排索引结构。当收到新的排名估计查询d后，对于任意ti∈d,首先计算tfi，并比较与对应链表中反向位置标记mi,n的大小，初步定位。k值的选择通常与搜索引擎或文本检索系统中每页显示文档数量相当。这样仅通过上一步操作，即可直接定位目标文档d在查询ti下所处的目标页数，对反向位置标记使用二分插入方法[7](对于n个元素，二分插入方法的平均比较次数是logn)，比较次数仅为∑ti:ti∈dlog(|{dj|ti∈dj}|/k)。以k=20，posting平均长度|{dj|ti∈dj}|=1000为例，如仅需定位文档在检索系统中出现的页码数，比较次数仅为原来的5%。

算法2 使用扩展索引的算法

输入:文档dm,语料库C;

输出:影响力向量ri。

变量tfi向量：dm中词语的TF值向量

1. 预操作建立倒排索引建立扩展索引

2. FOR eachti∈dm

3.tfi=ni,m/∑knk,m//n定义参考2.1节;

4. FOR eachmi,n(0≤n≤|{dj|ti∈dj}|/k)

5. IFtfi

6. 计算并输出ri，Continue;

7. END IF

8. END FOR

9. END FOR

10.结束

4.3 索引更新策略

当语料库文档改变时，需要对索引进行更新。对于任意一个新文档dm的插入，会影响到索引中|{t|t∈dm}|个反向链表。对于快速更新的语料库，如何防止频繁更新带来的索引碎片和性能下降，也是一个具有挑战性的问题。在本节中，我们设计了一个兼顾更新效率与索引维护效率的索引更新策略。

更新扩展索引策略反向位置标记间维持(k-1)～2(k-1)个元素，当新元素到来时，且反向位置标记间元素数量达到2(k-1)时，创建一个新的标记；当元素被删除，且反向位置标记间元素数量少于(k-1)时，则删除一个标记。

图3所示，当一个新的文档d到来时，需要更新tn引导的反向链表且mn,1

Figure 3 Update policy(k=3)图3 k=3的更新策略

当文档列表进行更新时，事实上上述排名估计方法存在一定的误差。通过计算可以看出，两个相邻的位置标记之间存在(k-1)～2(k-1)个元素，因此误差范围与k相关，也与文档的排名相关。也就是说，一个文档排名越靠后，其可能的误差范围也就越大。

5 实验

我们基于Apache软件基金会的非结构化信息管理结构UIMA(Unstructured Information Management Architecture)平台，开发了银河博思舆情系统，并在其中实现了本文描述的算法。本实验使用的详细配置如表1所示，实验环境使用Java语言实现，运行于基于Linux内核的CentOS平台上。

Table 1 Running environment of system development

在数据集的选择上，我们挑选了微博文本数据集。Weibo2012是我们通过采集新浪微博上的博文构造的文本数据集。数据集的统计资料如表2所示。由于中文文本特殊的语法结构，我们使用了中国科学院计算技术研究所发布的中文分词器ICTCLAS。

Table 2 Corpus configuration

在实验中，测试了不同k值对扩展索引生成和执行影响力查询操作的运行时间。由于三个数据集在数据规模上有较大的差异，在建立索引实验时，使用了兆字节/秒(MB/s)作为标准单位，出于公平原则，对于中文文档，在运行时间上没有计算对中文文本进行分词的时间。通过索引建立时间可以看出，k的取值对索引建立并没有太大的影响，建立倒排索引的开销依然支配着运行时间。

Figure 4 Running time图4 运行时间(k=0表示没有设置反向标记)

对于查询效率，采用随机生成查询文档的方式，为了公平起见，以1 KB个长度为200词的随机文档作为一个查询的计时单位测试处理时间。通过图4可以看出，设立反向位置标记的索引相对于原始的倒排索引，在影响力估计查询效果方面效率良好，反向位置标记效果明显。

为了验证文中影响力估计方法的正确性，我们随机挑选了300个“查询-文档”对，测试了k=10(假设搜索引擎每页显示10条信息)时的误差率。在对相关的数据进行连续插入更新操作后，计算算法估计排名和实际排名之间的差值。图5中，横坐标表示“查询-文档”，纵坐标表示对应查询的误差率，通过结果可以看出，本文所提方法的误差率很低，绝大部分查询的误差率在5%左右。

Figure 5 Accuracy analysis图5 正确率分析

6 结束语

本文给出了一种全新的基于全局排名的影响力指标，并通过在传统的倒排索引基础上设置反向

位置标记，使一般信息检索系统具有快速估计新文档影响力的能力。本文创新性地将文档向量模型和基于链接的节点权威性度量方法，通过一种排序策略有机地结合在一起。本文提出的方法还在广告收益估计、新闻舆论影响评估等领域具有重要的作用和广阔的前景。

本文提出的模型当前仅针对单个关键字查询，今后还可以在此基础上设计开发多关键字的文档影响力估计模型，并结合恶意排名、垃圾信息检测等工作开展进一步的研究。

[1] Shenoy P P. Valuation_based systems for Bayesian decision analysis[J]. Operations Research, 1992,40(3):63-84.

[2] Madsen A L. Lazy propagation:A junction tree inference algorithm based on lazy evaluation[J].Artificial Intelligence, 1999, 113(1-2):203-245.

[3] McCandless L C, Gustafson P, Levy A. Bayesian sensitivity analysis for unmeasured confounding in observational studies[J]. Statistics in Medicine, 2006, 26(11):2331-2347.

[4] Wang H. Building Bayesian networks: Elicitation, evaluation, and learning[M]. Pittsburgh:University of Pittsburgh, 2004.

[5] Renooij S. Efficient sensitivity analysis in hidden Markov models[C]∥Proc of the 5th European Workshop on Probabilistic Graphical Modelsm, 2010:1.

[6] Maes S, Philippe L. Multi-agent causal models for dependability analysis[C]∥Proc of the 1st International Conference on Availability, Reliability and Security, 2006:794-798.

[7] Salton G, McGill M J. Introduction to modern information retrieval[M]. NY:McGraw-Hill, 1983.

[8] Salton G, Fox E A, Wu H. Extended boolean information retrieval[J]. Communicaton of ACM,1983,26(11):1022-1036.

[9] Salton G,Buckley C.Term-weighting approaches in automatic text retrieval[J]. Information Processing & Management, 1988,24(5):513-523.

SI Hong-wei,born in 1982,MS,his research interest includes computer network security.

Estimating the influence of documents:An enhanced inverted index based approach

SI Hong-wei
(College of Computer,National University of Defense Technology,Changsha 410073,China)

Ranking the documents in a list has been extensively used in a lot of search engine systems. In these systems, vector space based ranking models are adopted. Actually, the ranking score of a given document is invisible to search engine users, and the rank position can be regarded as a measure of the influence of a given document. However, for a document outside corpus, how can we measure the influence of it? The question cannot be answered by using ordinary search engines. Social influence is introduced on a real micro-blogging system. Moreover, a large number of milestones are added into inverted indices for the sake of estimating the influence scores. Therefore, above questions can be well answered. The experiments on real data sets verify the effectiveness and efficiency.

information retrieval;inverted index;TFIDF;milestone

2012-07-14;

2012-10-12

国家863计划资助项目(2011AA010702，2012AA01A402)；国家自然科学基金资助项目(91124002)；科技支撑计划课题(2012BAH38B06) 通讯地址：410073 湖南省长沙市国防科学技术大学计算机学院

1007-130X(2014)03-0545-06

TP391

10.3969/j.issn.1007-130X.2014.03.030