基于结构挖掘的论坛检索模型

杨小锐,林 磊,孙承杰,刘秉权

(哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001)

1 引言

论坛又名BBS,是英文Bulletin Board System(电子公告系统)的缩写,最初用来公布股市价格等信息,现在它变成了纯粹的讨论区[1]。BBS是用计算机及软件建立的一种电子数据库,可以让人们登录,并在上面留下各种各样的信息[2]。随着网络技术的蓬勃发展,论坛如雨后春笋般的出现,并迅速的发展壮大。目前,中国有上百万个论坛,每天发布大量信息,这些信息几乎涵盖了我们日常生活和工作的各个方面。国内比较著名的论坛有百度、腾讯、新浪等服务商提供的综合性论坛,也有例如CSDN、PHPChina等专注于程序设计的专业性论坛。

在论坛当中,用户发布的帖子是以线索进行分组的,一条线索代表一组用户针对一个起始话题的交流过程。线索包括一个由楼主发表的主题帖子,以及零个或多个回复帖子。经过数年的发展和累积,论坛中蕴涵着数量巨大且质量较好的知识资源,本文目的是探索和研究适合于论坛的检索方法,充分利用论坛平台累积的大量知识资源来满足用户从互联网上快速获取有用信息的需求。

目前来讲,互联网上论坛页面检索服务可以分为以下三类：

1)通用搜索引擎提供的论坛页面检索服务。通用的搜索引擎(百度,谷歌等)都会收录来自论坛的页面,但是它们只将论坛页面作为普通的网页对待,由于论坛页面与普通网页在结构上的显著差异导致通用搜索引擎无法提供令人满意的论坛页面检索服务。

2)论坛站点提供的站内检索服务。由于论坛站点往往是由一些网络爱好者建立,对所有人免费开放,没有财力物力支撑。一般只提供基于字符串匹配或是利用一些开源工具搭建的简单站内搜索,因此,检索结果往往更差。

3)专业搜索引擎提供的论坛页面检索服务。然而,这些论坛检索系统只是以来自论坛的网页作为数据集,更像是根据页面类别提供的分类检索服务,并没有考虑到论坛页面所具有的特点,得到的结果也难以让人满意。

目前,论坛检索直接相关的研究工作还比较少,但是论坛数据处理相关的工作正在不断开展,有关研究都主要集中在对论坛所蕴涵知识的抽取上,例如：寻找问答对[3]、利用条件随机域抽取问题的答案[4]。另外,一些学者采用不同方法对论坛中线索的结构或帖子之间的关系进行了挖掘[5-6]。在检索模型的研究方面,文献[7-8]讨论了使用上下文和结构的检索模型。

2 论坛线索结构特点

对于通用的搜索引擎来讲,他们没有考虑论坛具有的结构特点。论坛中每条线索是由网友围绕楼主发起的话题进行讨论交流而形成的,而人与人之间的对话会存在着一定的逻辑关系,我们的目的是找到这样的逻辑关系,进而利用挖掘得到的信息来构建适合论坛的检索模型。

为了能够明确的描述出上述的逻辑关系,我们分析下面这个例子。线索文本如图1所示,描述线索中帖子间逻辑关系的树如图2所示。由图1可见,楼主“xin87”首先发表自己遇到的问题,接下来网友“dosboring” 、“aliening” 、“witer666”分别针对楼主遇到的问题发表自己的解决方案或存在的困惑,当楼主“xin87”看到这些回复时,根据网友发布的内容,分别进行了解释(回复),此后,网友“遥远的期待”浏览到该线索,并针对楼主的问题提出了新的解决方案,楼主根据网友“遥远的期待”的提示成功地解决了自己遇到的问题。

图1 线索显示图

图2 线索树图

经过上面的分析发现,用户发布的帖子之间存在着对话关系,若帖子B是回复帖子A的,那么我们称A是B的父帖。显然,如果我们为线索中的每个帖子(第一个帖子除外)找到其父帖,那么我们就可以构造出一棵以楼主发布的主题帖为根的描述线索中帖子间逻辑关系的树。因此,我们接下来的工作就是如何挖掘出论坛中所蕴含的如上文所描述的结构信息。

3 基于排序支持向量机的论坛线索重构

3.1 排序支持向量机

排序支持向量机[9-11](Ranking Support Vector Machine,RSVM)是一种典型的解决排序学习问题算法。它把对目标数据点的排序问题转换为基于有序对数据的二值分类问题,进而利用支持向量机求解问题。

给定输入向量集合X={x1,x2,…,xm}⊆Rn和其对应的标号Y={y1,y2,…,ym},其中m为训练样本个数,n为输入向量维数。S=(X,Y)为按某一分布p(x,y)独立分布的样本集合。排序学习的目的是寻找一个能够精确预测数据 x的标号y的决策函数f：Rn→Y。基于有序对(x1,x2),其对应的标号分别为y1和y2,决策函数为 f,排序支持向量机为排序学习问题定义的损失函数lpref如公式(1)所示。

按照损失函数的如上定义,从分布 p(x1,x2,y1,y2)中抽样,排序算法的风险函数可以表示为公式(2),基于经验风险最小化原理的风险函数可以表示为公式(3)。

为了把最小化REMPpref(f)转化为二值分类问题,重新定义训练集合为S′=(X′,Y′)如下：其中,是一个有序对,分别代表第一个、第二个元素,对应标号分别为为一个指示函数,若取值为 1,若,取值为-1,否则为0;l为训练样本集S′的大小。由此,风险函数可以表示为公式(4),经验风险函数表示为公式(5),其中lclass为用于分类的0-1损失函数。以上两式即将排序学习问题转化为二值分类问题。

3.2 特征选择

3.1 节描述了排序支持向量机的基本原理,本节讨论如何利用排序支持向量机帮助我们解决第2节所描述的问题。

为了能够构建出描述线索中帖子间逻辑关系的树,我们的首要工作是为线索中的每个帖子(线索中第一个帖子除外)寻找父帖,即寻找其所回复的对象。这里,我们把寻找父帖的任务看作为一项排序任务。具体地,把当前回帖作为一个来自用户的查询输入,将在其之前发表的帖子作为待检索的文档,这些帖子即构成当前帖子的父帖的候选集合,同时,为了对应树结构,我们设定任意一个回帖有且仅有一个父帖,即为当前回帖在其父帖的候选集合当中选择一个最相关的帖子作为其父帖。进而,我们可以利用RSVM模型解决寻找父帖的工作。

接下来的工作是选择合适的特征。根据论坛的特点,我们主要选择了以下4个特征：

1)时间特征(t2-t1)/(t2-t0)：其中t0是线索中第一个帖子的发布时间;t1是一个候选父帖的发布时间;t2是当前帖子的发布时间。

2)引用特征：当前帖子中是否含有“引用”、“回复”等显式的论坛结构信息;当前帖子文本中是否含有“楼上” 、“*楼” 、“*L”、“ *l” 、“楼主”、“ 用户名字”等信息,其中*表示数字通配符。

3)同一用户特征：我们认为一般情况下用户不会与本身进行交流,所以引入了同一用户特征。

4)轮流发言特征：如果用户A和B曾进行过对话,A在前B在后,那么当A再发表帖子时,认为其更可能是对 B的回复,因此引入了轮流对话特征。

至此,我们可以利用RSVM模型为线索中的每个帖子寻找父帖,处理流程如图3所示。

图3 基于RSVM寻找父帖结构图

其中,帖子1直到帖子j构成了帖子j+1的父帖的候选集合,利用RSVM模型对这些候选的父帖进行评分并且排名,我们认为排名第一的帖子i是帖子j+1的父帖,这样就完成了为一个帖子寻找父帖的工作。

3.3 实验结果与分析

首先,我们手工标注来自PHPChina(http：//bbs.phpchina.com/)论坛的28条线索作为数据集。其次,利用 SVMLight工具包(http：//svmlight.joachims.org/)训练RSVM模型,我们采用4折交叉实验,每次实验选择21条线索作为训练集,剩余的7条线索作为测试集。实验结果如表1所示。

表1 寻找父帖实验结果

统计显示,每条线索平均包含约10个帖子,因此,一般情况下,对于一条线索来说,利用RSVM 模型,除一个帖子外,其余帖子都会得到正确的父帖标号。利用找到的父子关系可以建立一棵由用户交流关系而形成的线索树,从而把原来的线性结构重构成含义明确的树结构。

4 关键帖抽取与最佳对话链路发现

经过上一节的操作我们即可以为每条线索建立一棵如图2所示的描述其交流结构的树。由该图可见,根节点代表主题帖,即问题。根节点拥有三棵子树,恰好代表了围绕着楼主提出的问题的三种解决方案,我们最关心的是真正能够使问题得到解决的方案,对于图中所列线索来讲,由于8号帖子使得问题得到了解决,显然,1-4-7-8-9构成最佳解决方案,我们称1-4-7-8-9为最佳对话链路。显然,最佳对话链路对于线索来讲,是最有意义的部分,如果我们能够自动寻找到这条最佳链路并将其运用到检索系统当中,将有利于提高论坛检索系统的准确性。一般来讲,并不是所有线索中都一定蕴涵着能够使问题得到的方案,能够使问题得到解决的方案也不唯一,因此,为了简化我们的问题,本文只选择众多的解决方案当中最好的一个解决方案,称其为最佳对话链路。

4.1 关键帖抽取

论坛中的一些帖子没有现实的参考价值,即我们通常所说的水帖。例如：“顶楼主”、“期待答案”、“没有什么更好的办法了”等这样表达情感的交互用语。显然,如果像通用的搜索引擎一样简单的把这样的水帖作为文档的一部分,就会影响到检索的效果。因此,我们进行关键帖抽取,过滤掉水帖。

为了排除水帖对线索主要内容的干扰,抽取出能够代表线索主要内容的关键帖,我们采用了基于TF-IDF的方法进行关键帖抽取。传统的TF-IDF算法主要考虑特征项的频率信息TF以及反文档频率信息IDF[12]。在关键帖抽取过程中,我们把一条线索看成一个文档集合,当前线索中的每个帖子看成一篇文档,weight(Mjk)代表线索中第j个帖子的第k个词的TF-IDF权重。

向量空间模型(Vector Space Model)[13]被用来作为关键贴抽取的方法。在向量空间模型中,文本D表示为D(W1,W2,…,Wk)。其中Wk表示该向量模型中第k个词在当前文本中的权重。计算文档Dj和Dk的相似度的公式如公式(6)所示。

在关键帖抽取过程中,我们利用余弦向量夹角计算每个帖子与其所属线索的相似度,根据一定的阈值,把得分高于阈值的帖子作为当前线索的关键帖,进而,我们就可以用所得的关键贴集合代表当前线索。关键帖抽取流程如图4所示。其中线索j代表第j条线索,帖子ji代表第j条线索中的第i个帖子,d表示所选择的阈值。

4.2 寻找最佳对话链路

图4 关键帖抽取流程图

在4.1节中,我们曾经计算了每个帖子与所在线索的相似度值,这里,我们利用相似度值来衡量最佳对话链路。我们认为所有从根节点出发到叶子节点的路径当中相似度之和最大的路径为最佳对话链路。具体形式如图5所示。图中的数值代表相应的帖子与其所属线索的文本相似度,我们对相似度进行了归一化处理。图 5中节点1、2、6、7、8、10构成的路径相似度之和最大,因此称1-2-6-7-8-10为最佳对话链路。

图5 最佳对话链路

至此,我们可以通过RSVM模型寻找父帖并建立线索对应的树,进而利用相似度找到线索中的最佳对话链路。下一步的工作就是如何将所得到的最佳对话链路融合进论坛检索结果的排序方法中。

5 检索模型

根据上一节的工作,我们可以构建如下3个检索模型：

首先,对于通用的搜索引擎来讲,他们通常把论坛中的线索看作一篇普通文档对待,不会考虑水帖的干扰性以及论坛的结构特点,即相当于上文中阈值d取0的情况。为了能够对比不同算法的效果,我们把线索看作一篇普通文档建立检索模型LD。排序算法公式如公式(7)所示,其中T表示线索,Q表示用户查询。

其次,经过关键帖抽取,我们可以排除水帖的干扰,采用关键帖构成的集合来替代当前线索建立检索模型KP。对于线索 T,其关键帖集合记为 TKP,则TKP={Pi|Pi为线索T的关键帖}。排序算法公式如公式(8)所示。T、Q的意义与上文相同,d表示在关键帖抽取过程中采用的阈值,我们这里取d=EX-σ,EX代表数学期望,σ代表标准差。EX与σ计算方式如公式(9)和公式(10),其中n表示当前线索中帖子数目,Simi表示第i个帖子与其所属线索的相似度。

最后,经过对话链路挖掘,我们采用了基于论坛结构的排序算法,将对话链路上的帖子作为排序的部分依据,检索模型记为 Path,如公式(11)所示。其中,TPath表示位于线索T的最佳对话链路上的帖子构成的集合,π是调整权重的参数,实验中取其值经验值为0.5。

6 实验结果与分析

6.1 相关性文档集构建

为了对比各个检索模型的效果,我们构建了自己的论坛检索评价系统。首先是测试集合的准备。我们利用从CSDN、PHPChina等论坛上采集的21万条线索作为测试集,这样所有的检索系统就建立在共同的数据集合之上。

其次是查询集合的准备。根据程序设计论坛数据分布的特点,同时为了尽可能保证客观性,我们选择百度知道问答系统程序设计类别的一些问题的标题作为输入,同时由于需要人工进行相关性判断,考虑到人力资源的开销,我们选择了4个查询输入,如表2所示。

表2 查询列表

最后是对返回文档进行相关性判断。相关性本身是一个比较模糊的概念,具有很大的主观性,因此我们放弃了二分法(要么相关、要么不相关)的打分方式,将相关性设定为四个等级：0表示毫不相关,即没有出现相应的关键字;1表示稍有相关,即只是出现相应的关键字,没有对查询详细的介绍或解释;2表示比较相关,即不仅出现相应的关键字,同时有对查询的详细介绍或解释;3表示十分相关,即所返回的文档不仅有查询的详细介绍或解释,同时该介绍或解释是正确的或是权威的。为了尽可能的保证评价工作的专业性和客观性,我们邀请了5名计算机专业硕士研究生对返回文档进行相关性判断,并对返回文档的次序进行了打乱,即评价人员不知道当前等待评价的线索来自哪个模型,也不知道该线索在返回结果中的排名。对于一篇线索来讲,取这5个人的平均得分作为其最终得分,若得分不低于2,那么认为该文档与对应查询是相关的,反之,则不相关。

6.2 实验结果与分析

本文采用MAP指标作为论坛检索结果的评价指标。MAP是指相关文档被检索出之后所获得的平均准确率。第5节中描述的几个检索模型的MAP指标如表3所示。从表3中我们可以看出以下几点：首先,LD模型只是如同通用的搜索引擎一样把线索看作一般的文档来进行操作,没有考虑水帖的干扰以及论坛的结构特点,在3个检索模型当中表现最差;其次,KP模型进行了关键帖抽取,利用关键帖集合代替线索建立索引模型,考虑了水帖的干扰但是也忽略了论坛的结构特点,其结果要好于LD模型,其中MAP指标提高15个百分点,说明通过关键帖抽取可以较大幅度地提高检索系统的效果;最后,Path模型通过基于RSVM的方法抽取论坛结构并通过相似度寻找最佳对话链路,并将最佳对话链路融入到排序算法当中,Path模型取得了最好的效果,对比KP模型,其MAP指标提高了5个百分点,这说明通过论坛结构挖掘可以显著改善论坛检索系统的效果。综上所述,通过关键帖挖掘、论坛结构挖掘可以提高论坛检索系统的效果。

表3 实验结果

7 结论与展望

论坛数据自身的特点使得论坛检索系统很难直接采用通用搜索引擎的方法。本文针对论坛线索中存在大量水贴,且具有一定结构的特点,提出通过关键帖抽取、基于论坛结构挖掘的线索重构方法来提取论坛数据中最有价值的信息,从而减少垃圾数据对论坛检索的干扰。实验表明,利用本文提出的方法得到的论坛数据来构建论坛检索系统可以取得较好的效果。本文在基于排序支持向量机的论坛线索重构方法中没有引入文本特征,因此如何将文本特征引入将是今后工作中的任务之一;本文在寻找最佳对话链路过程中只考虑了相似度这一因素,以后可以通过情感分析进一步挖掘最佳对话链路。

[1]韩庆玲.网上论坛(BBS)的语体特点[J].修辞学习,2003,(4)：39-41.

[2]陈彤旭,邓理峰.议题的形成与衰变——对人民网强国论坛的个案研究[J].新闻与传播研究,2002,(1)：13-25.

[3]G.Cong,L.Wang,C.-Y.Lin,Y.-I.Song,and Y.Sun.Finding question-answer pairs from online forums[C]//Proceedings of SIGIR'08.New York,NY,USA：ACM,2008：467-474.

[4]S.Ding,G.Cong,C.Lin,and X.Zhu.Using conditional random fields to extract contexts and answers of questions from online forums[C]//Proceedings of ACL08.Columbus,Ohio,USA：ACL,2008：710-718.

[5]M.Elsner and E.Charniak.You talking to me?a corpus and algorithm for conversation disentanglement[C]//Proceedings ofACL-08：HLT.Columbus,Ohio,USA：ACL,2008：834-842.

[6]Y.-C.Wang,M.Joshi,W.W.Cohen,and C.Rose.Recovering implicit thread structure in newsgroup style conversations[C]//Proceedings of ICWSM II.Seattle,Washington,USA,2008：152-160.

[7]X.Liu and W.B.Croft.Cluster-based retrieval using language models[C]//Proceedings of SIGIR'04.New York,NY,USA ：ACM,2004：186-193.

[8]P.Ogilvie and J.Callan.Hierarchical language models for retrieval of XM L components[C]//Fuhr,Norbert.In Advances in XML Information Retrieval.Berlin Heidelberg：Springer,2005：224-237.

[9]R.Herbrich,T.Graepel,and K.Obermayer.Large margin rank boundaries for ordinal regression[C]//Advances in Large M argin Classifiers.Cambridge,MA ：M IT Press,2000：115-132.

[10]T.Joachims.Optimizing search engines using click through data[C]//Proceedings of the ACM Conference on Knowledge Discovery and Data Mining.New York,NY,USA：ACM,2002：133-142.

[11]高永梅,黄亚楼,倪维健.基于排序支持向量机的缩略词自动提取方[J].模式识别与人工智能,2008,21(2)：186-192.

[12]Sethian J A.Level Set Methods and Fast Marching Methods：Evolving Interface in Computational Geometry,Fluid Mechanics,Computer Vision,and Materials Science[M].New York：Cambridge University Press,1999：284-312.

[13]Natowicz R,Venturini G.Learning the behavior of a simulated moving robotusing genetic algorithms[C]//Proceedings of the third COGNITIVA symposium on at the crossroads of artificial intelligence,cognitivescience,and neuroscience.Amsterdam,The Netherlands：North-Holland PublishingCo.,1991：645-654.