楊小銳,林 磊,孫承杰,劉秉權(quán)
(哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱150001)
論壇又名BBS,是英文Bulletin Board System(電子公告系統(tǒng))的縮寫,最初用來公布股市價格等信息,現(xiàn)在它變成了純粹的討論區(qū)[1]。BBS是用計算機及軟件建立的一種電子數(shù)據(jù)庫,可以讓人們登錄,并在上面留下各種各樣的信息[2]。隨著網(wǎng)絡(luò)技術(shù)的蓬勃發(fā)展,論壇如雨后春筍般的出現(xiàn),并迅速的發(fā)展壯大。目前,中國有上百萬個論壇,每天發(fā)布大量信息,這些信息幾乎涵蓋了我們?nèi)粘I詈凸ぷ鞯母鱾€方面。國內(nèi)比較著名的論壇有百度、騰訊、新浪等服務(wù)商提供的綜合性論壇,也有例如CSDN、PHPChina等專注于程序設(shè)計的專業(yè)性論壇。
在論壇當中,用戶發(fā)布的帖子是以線索進行分組的,一條線索代表一組用戶針對一個起始話題的交流過程。線索包括一個由樓主發(fā)表的主題帖子,以及零個或多個回復(fù)帖子。經(jīng)過數(shù)年的發(fā)展和累積,論壇中蘊涵著數(shù)量巨大且質(zhì)量較好的知識資源,本文目的是探索和研究適合于論壇的檢索方法,充分利用論壇平臺累積的大量知識資源來滿足用戶從互聯(lián)網(wǎng)上快速獲取有用信息的需求。
目前來講,互聯(lián)網(wǎng)上論壇頁面檢索服務(wù)可以分為以下三類:
1)通用搜索引擎提供的論壇頁面檢索服務(wù)。通用的搜索引擎(百度,谷歌等)都會收錄來自論壇的頁面,但是它們只將論壇頁面作為普通的網(wǎng)頁對待,由于論壇頁面與普通網(wǎng)頁在結(jié)構(gòu)上的顯著差異導(dǎo)致通用搜索引擎無法提供令人滿意的論壇頁面檢索服務(wù)。
2)論壇站點提供的站內(nèi)檢索服務(wù)。由于論壇站點往往是由一些網(wǎng)絡(luò)愛好者建立,對所有人免費開放,沒有財力物力支撐。一般只提供基于字符串匹配或是利用一些開源工具搭建的簡單站內(nèi)搜索,因此,檢索結(jié)果往往更差。
3)專業(yè)搜索引擎提供的論壇頁面檢索服務(wù)。然而,這些論壇檢索系統(tǒng)只是以來自論壇的網(wǎng)頁作為數(shù)據(jù)集,更像是根據(jù)頁面類別提供的分類檢索服務(wù),并沒有考慮到論壇頁面所具有的特點,得到的結(jié)果也難以讓人滿意。
目前,論壇檢索直接相關(guān)的研究工作還比較少,但是論壇數(shù)據(jù)處理相關(guān)的工作正在不斷開展,有關(guān)研究都主要集中在對論壇所蘊涵知識的抽取上,例如:尋找問答對[3]、利用條件隨機域抽取問題的答案[4]。另外,一些學(xué)者采用不同方法對論壇中線索的結(jié)構(gòu)或帖子之間的關(guān)系進行了挖掘[5-6]。在檢索模型的研究方面,文獻[7-8]討論了使用上下文和結(jié)構(gòu)的檢索模型。
對于通用的搜索引擎來講,他們沒有考慮論壇具有的結(jié)構(gòu)特點。論壇中每條線索是由網(wǎng)友圍繞樓主發(fā)起的話題進行討論交流而形成的,而人與人之間的對話會存在著一定的邏輯關(guān)系,我們的目的是找到這樣的邏輯關(guān)系,進而利用挖掘得到的信息來構(gòu)建適合論壇的檢索模型。
為了能夠明確的描述出上述的邏輯關(guān)系,我們分析下面這個例子。線索文本如圖1所示,描述線索中帖子間邏輯關(guān)系的樹如圖2所示。由圖1可見,樓主“xin87”首先發(fā)表自己遇到的問題,接下來網(wǎng)友“dosboring” 、“aliening” 、“witer666”分別針對樓主遇到的問題發(fā)表自己的解決方案或存在的困惑,當樓主“xin87”看到這些回復(fù)時,根據(jù)網(wǎng)友發(fā)布的內(nèi)容,分別進行了解釋(回復(fù)),此后,網(wǎng)友“遙遠的期待”瀏覽到該線索,并針對樓主的問題提出了新的解決方案,樓主根據(jù)網(wǎng)友“遙遠的期待”的提示成功地解決了自己遇到的問題。
圖1 線索顯示圖
圖2 線索樹圖
經(jīng)過上面的分析發(fā)現(xiàn),用戶發(fā)布的帖子之間存在著對話關(guān)系,若帖子B是回復(fù)帖子A的,那么我們稱A是B的父帖。顯然,如果我們?yōu)榫€索中的每個帖子(第一個帖子除外)找到其父帖,那么我們就可以構(gòu)造出一棵以樓主發(fā)布的主題帖為根的描述線索中帖子間邏輯關(guān)系的樹。因此,我們接下來的工作就是如何挖掘出論壇中所蘊含的如上文所描述的結(jié)構(gòu)信息。
排序支持向量機[9-11](Ranking Support Vector Machine,RSVM)是一種典型的解決排序?qū)W習(xí)問題算法。它把對目標數(shù)據(jù)點的排序問題轉(zhuǎn)換為基于有序?qū)?shù)據(jù)的二值分類問題,進而利用支持向量機求解問題。
給定輸入向量集合X={x1,x2,…,xm}?Rn和其對應(yīng)的標號Y={y1,y2,…,ym},其中m為訓(xùn)練樣本個數(shù),n為輸入向量維數(shù)。S=(X,Y)為按某一分布p(x,y)獨立分布的樣本集合。排序?qū)W習(xí)的目的是尋找一個能夠精確預(yù)測數(shù)據(jù) x的標號y的決策函數(shù)f:Rn→Y?;谟行?qū)?x1,x2),其對應(yīng)的標號分別為y1和y2,決策函數(shù)為 f,排序支持向量機為排序?qū)W習(xí)問題定義的損失函數(shù)lpref如公式(1)所示。
按照損失函數(shù)的如上定義,從分布 p(x1,x2,y1,y2)中抽樣,排序算法的風(fēng)險函數(shù)可以表示為公式(2),基于經(jīng)驗風(fēng)險最小化原理的風(fēng)險函數(shù)可以表示為公式(3)。
為了把最小化REMPpref(f)轉(zhuǎn)化為二值分類問題,重新定義訓(xùn)練集合為S′=(X′,Y′)如下:其中,是一個有序?qū)?分別代表第一個、第二個元素,對應(yīng)標號分別為為一個指示函數(shù),若取值為 1,若,取值為-1,否則為0;l為訓(xùn)練樣本集S′的大小。由此,風(fēng)險函數(shù)可以表示為公式(4),經(jīng)驗風(fēng)險函數(shù)表示為公式(5),其中l(wèi)class為用于分類的0-1損失函數(shù)。以上兩式即將排序?qū)W習(xí)問題轉(zhuǎn)化為二值分類問題。
3.1 節(jié)描述了排序支持向量機的基本原理,本節(jié)討論如何利用排序支持向量機幫助我們解決第2節(jié)所描述的問題。
為了能夠構(gòu)建出描述線索中帖子間邏輯關(guān)系的樹,我們的首要工作是為線索中的每個帖子(線索中第一個帖子除外)尋找父帖,即尋找其所回復(fù)的對象。這里,我們把尋找父帖的任務(wù)看作為一項排序任務(wù)。具體地,把當前回帖作為一個來自用戶的查詢輸入,將在其之前發(fā)表的帖子作為待檢索的文檔,這些帖子即構(gòu)成當前帖子的父帖的候選集合,同時,為了對應(yīng)樹結(jié)構(gòu),我們設(shè)定任意一個回帖有且僅有一個父帖,即為當前回帖在其父帖的候選集合當中選擇一個最相關(guān)的帖子作為其父帖。進而,我們可以利用RSVM模型解決尋找父帖的工作。
接下來的工作是選擇合適的特征。根據(jù)論壇的特點,我們主要選擇了以下4個特征:
1)時間特征(t2-t1)/(t2-t0):其中t0是線索中第一個帖子的發(fā)布時間;t1是一個候選父帖的發(fā)布時間;t2是當前帖子的發(fā)布時間。
2)引用特征:當前帖子中是否含有“引用”、“回復(fù)”等顯式的論壇結(jié)構(gòu)信息;當前帖子文本中是否含有“樓上” 、“*樓” 、“*L”、“ *l” 、“樓主”、“ 用戶名字”等信息,其中*表示數(shù)字通配符。
3)同一用戶特征:我們認為一般情況下用戶不會與本身進行交流,所以引入了同一用戶特征。
4)輪流發(fā)言特征:如果用戶A和B曾進行過對話,A在前B在后,那么當A再發(fā)表帖子時,認為其更可能是對 B的回復(fù),因此引入了輪流對話特征。
至此,我們可以利用RSVM模型為線索中的每個帖子尋找父帖,處理流程如圖3所示。
圖3 基于RSVM尋找父帖結(jié)構(gòu)圖
其中,帖子1直到帖子j構(gòu)成了帖子j+1的父帖的候選集合,利用RSVM模型對這些候選的父帖進行評分并且排名,我們認為排名第一的帖子i是帖子j+1的父帖,這樣就完成了為一個帖子尋找父帖的工作。
首先,我們手工標注來自PHPChina(http://bbs.phpchina.com/)論壇的28條線索作為數(shù)據(jù)集。其次,利用 SVMLight工具包(http://svmlight.joachims.org/)訓(xùn)練RSVM模型,我們采用4折交叉實驗,每次實驗選擇21條線索作為訓(xùn)練集,剩余的7條線索作為測試集。實驗結(jié)果如表1所示。
表1 尋找父帖實驗結(jié)果
統(tǒng)計顯示,每條線索平均包含約10個帖子,因此,一般情況下,對于一條線索來說,利用RSVM 模型,除一個帖子外,其余帖子都會得到正確的父帖標號。利用找到的父子關(guān)系可以建立一棵由用戶交流關(guān)系而形成的線索樹,從而把原來的線性結(jié)構(gòu)重構(gòu)成含義明確的樹結(jié)構(gòu)。
經(jīng)過上一節(jié)的操作我們即可以為每條線索建立一棵如圖2所示的描述其交流結(jié)構(gòu)的樹。由該圖可見,根節(jié)點代表主題帖,即問題。根節(jié)點擁有三棵子樹,恰好代表了圍繞著樓主提出的問題的三種解決方案,我們最關(guān)心的是真正能夠使問題得到解決的方案,對于圖中所列線索來講,由于8號帖子使得問題得到了解決,顯然,1-4-7-8-9構(gòu)成最佳解決方案,我們稱1-4-7-8-9為最佳對話鏈路。顯然,最佳對話鏈路對于線索來講,是最有意義的部分,如果我們能夠自動尋找到這條最佳鏈路并將其運用到檢索系統(tǒng)當中,將有利于提高論壇檢索系統(tǒng)的準確性。一般來講,并不是所有線索中都一定蘊涵著能夠使問題得到的方案,能夠使問題得到解決的方案也不唯一,因此,為了簡化我們的問題,本文只選擇眾多的解決方案當中最好的一個解決方案,稱其為最佳對話鏈路。
論壇中的一些帖子沒有現(xiàn)實的參考價值,即我們通常所說的水帖。例如:“頂樓主”、“期待答案”、“沒有什么更好的辦法了”等這樣表達情感的交互用語。顯然,如果像通用的搜索引擎一樣簡單的把這樣的水帖作為文檔的一部分,就會影響到檢索的效果。因此,我們進行關(guān)鍵帖抽取,過濾掉水帖。
為了排除水帖對線索主要內(nèi)容的干擾,抽取出能夠代表線索主要內(nèi)容的關(guān)鍵帖,我們采用了基于TF-IDF的方法進行關(guān)鍵帖抽取。傳統(tǒng)的TF-IDF算法主要考慮特征項的頻率信息TF以及反文檔頻率信息IDF[12]。在關(guān)鍵帖抽取過程中,我們把一條線索看成一個文檔集合,當前線索中的每個帖子看成一篇文檔,weight(Mjk)代表線索中第j個帖子的第k個詞的TF-IDF權(quán)重。
向量空間模型(Vector Space Model)[13]被用來作為關(guān)鍵貼抽取的方法。在向量空間模型中,文本D表示為D(W1,W2,…,Wk)。其中Wk表示該向量模型中第k個詞在當前文本中的權(quán)重。計算文檔Dj和Dk的相似度的公式如公式(6)所示。
在關(guān)鍵帖抽取過程中,我們利用余弦向量夾角計算每個帖子與其所屬線索的相似度,根據(jù)一定的閾值,把得分高于閾值的帖子作為當前線索的關(guān)鍵帖,進而,我們就可以用所得的關(guān)鍵貼集合代表當前線索。關(guān)鍵帖抽取流程如圖4所示。其中線索j代表第j條線索,帖子ji代表第j條線索中的第i個帖子,d表示所選擇的閾值。
圖4 關(guān)鍵帖抽取流程圖
在4.1節(jié)中,我們曾經(jīng)計算了每個帖子與所在線索的相似度值,這里,我們利用相似度值來衡量最佳對話鏈路。我們認為所有從根節(jié)點出發(fā)到葉子節(jié)點的路徑當中相似度之和最大的路徑為最佳對話鏈路。具體形式如圖5所示。圖中的數(shù)值代表相應(yīng)的帖子與其所屬線索的文本相似度,我們對相似度進行了歸一化處理。圖 5中節(jié)點1、2、6、7、8、10構(gòu)成的路徑相似度之和最大,因此稱1-2-6-7-8-10為最佳對話鏈路。
圖5 最佳對話鏈路
至此,我們可以通過RSVM模型尋找父帖并建立線索對應(yīng)的樹,進而利用相似度找到線索中的最佳對話鏈路。下一步的工作就是如何將所得到的最佳對話鏈路融合進論壇檢索結(jié)果的排序方法中。
根據(jù)上一節(jié)的工作,我們可以構(gòu)建如下3個檢索模型:
首先,對于通用的搜索引擎來講,他們通常把論壇中的線索看作一篇普通文檔對待,不會考慮水帖的干擾性以及論壇的結(jié)構(gòu)特點,即相當于上文中閾值d取0的情況。為了能夠?qū)Ρ炔煌惴ǖ男Ч?我們把線索看作一篇普通文檔建立檢索模型LD。排序算法公式如公式(7)所示,其中T表示線索,Q表示用戶查詢。
其次,經(jīng)過關(guān)鍵帖抽取,我們可以排除水帖的干擾,采用關(guān)鍵帖構(gòu)成的集合來替代當前線索建立檢索模型KP。對于線索 T,其關(guān)鍵帖集合記為 TKP,則TKP={Pi|Pi為線索T的關(guān)鍵帖}。排序算法公式如公式(8)所示。T、Q的意義與上文相同,d表示在關(guān)鍵帖抽取過程中采用的閾值,我們這里取d=EX-σ,EX代表數(shù)學(xué)期望,σ代表標準差。EX與σ計算方式如公式(9)和公式(10),其中n表示當前線索中帖子數(shù)目,Simi表示第i個帖子與其所屬線索的相似度。
最后,經(jīng)過對話鏈路挖掘,我們采用了基于論壇結(jié)構(gòu)的排序算法,將對話鏈路上的帖子作為排序的部分依據(jù),檢索模型記為 Path,如公式(11)所示。其中,TPath表示位于線索T的最佳對話鏈路上的帖子構(gòu)成的集合,π是調(diào)整權(quán)重的參數(shù),實驗中取其值經(jīng)驗值為0.5。
為了對比各個檢索模型的效果,我們構(gòu)建了自己的論壇檢索評價系統(tǒng)。首先是測試集合的準備。我們利用從CSDN、PHPChina等論壇上采集的21萬條線索作為測試集,這樣所有的檢索系統(tǒng)就建立在共同的數(shù)據(jù)集合之上。
其次是查詢集合的準備。根據(jù)程序設(shè)計論壇數(shù)據(jù)分布的特點,同時為了盡可能保證客觀性,我們選擇百度知道問答系統(tǒng)程序設(shè)計類別的一些問題的標題作為輸入,同時由于需要人工進行相關(guān)性判斷,考慮到人力資源的開銷,我們選擇了4個查詢輸入,如表2所示。
表2 查詢列表
最后是對返回文檔進行相關(guān)性判斷。相關(guān)性本身是一個比較模糊的概念,具有很大的主觀性,因此我們放棄了二分法(要么相關(guān)、要么不相關(guān))的打分方式,將相關(guān)性設(shè)定為四個等級:0表示毫不相關(guān),即沒有出現(xiàn)相應(yīng)的關(guān)鍵字;1表示稍有相關(guān),即只是出現(xiàn)相應(yīng)的關(guān)鍵字,沒有對查詢詳細的介紹或解釋;2表示比較相關(guān),即不僅出現(xiàn)相應(yīng)的關(guān)鍵字,同時有對查詢的詳細介紹或解釋;3表示十分相關(guān),即所返回的文檔不僅有查詢的詳細介紹或解釋,同時該介紹或解釋是正確的或是權(quán)威的。為了盡可能的保證評價工作的專業(yè)性和客觀性,我們邀請了5名計算機專業(yè)碩士研究生對返回文檔進行相關(guān)性判斷,并對返回文檔的次序進行了打亂,即評價人員不知道當前等待評價的線索來自哪個模型,也不知道該線索在返回結(jié)果中的排名。對于一篇線索來講,取這5個人的平均得分作為其最終得分,若得分不低于2,那么認為該文檔與對應(yīng)查詢是相關(guān)的,反之,則不相關(guān)。
本文采用MAP指標作為論壇檢索結(jié)果的評價指標。MAP是指相關(guān)文檔被檢索出之后所獲得的平均準確率。第5節(jié)中描述的幾個檢索模型的MAP指標如表3所示。從表3中我們可以看出以下幾點:首先,LD模型只是如同通用的搜索引擎一樣把線索看作一般的文檔來進行操作,沒有考慮水帖的干擾以及論壇的結(jié)構(gòu)特點,在3個檢索模型當中表現(xiàn)最差;其次,KP模型進行了關(guān)鍵帖抽取,利用關(guān)鍵帖集合代替線索建立索引模型,考慮了水帖的干擾但是也忽略了論壇的結(jié)構(gòu)特點,其結(jié)果要好于LD模型,其中MAP指標提高15個百分點,說明通過關(guān)鍵帖抽取可以較大幅度地提高檢索系統(tǒng)的效果;最后,Path模型通過基于RSVM的方法抽取論壇結(jié)構(gòu)并通過相似度尋找最佳對話鏈路,并將最佳對話鏈路融入到排序算法當中,Path模型取得了最好的效果,對比KP模型,其MAP指標提高了5個百分點,這說明通過論壇結(jié)構(gòu)挖掘可以顯著改善論壇檢索系統(tǒng)的效果。綜上所述,通過關(guān)鍵帖挖掘、論壇結(jié)構(gòu)挖掘可以提高論壇檢索系統(tǒng)的效果。
表3 實驗結(jié)果
論壇數(shù)據(jù)自身的特點使得論壇檢索系統(tǒng)很難直接采用通用搜索引擎的方法。本文針對論壇線索中存在大量水貼,且具有一定結(jié)構(gòu)的特點,提出通過關(guān)鍵帖抽取、基于論壇結(jié)構(gòu)挖掘的線索重構(gòu)方法來提取論壇數(shù)據(jù)中最有價值的信息,從而減少垃圾數(shù)據(jù)對論壇檢索的干擾。實驗表明,利用本文提出的方法得到的論壇數(shù)據(jù)來構(gòu)建論壇檢索系統(tǒng)可以取得較好的效果。本文在基于排序支持向量機的論壇線索重構(gòu)方法中沒有引入文本特征,因此如何將文本特征引入將是今后工作中的任務(wù)之一;本文在尋找最佳對話鏈路過程中只考慮了相似度這一因素,以后可以通過情感分析進一步挖掘最佳對話鏈路。
[1]韓慶玲.網(wǎng)上論壇(BBS)的語體特點[J].修辭學(xué)習(xí),2003,(4):39-41.
[2]陳彤旭,鄧理峰.議題的形成與衰變——對人民網(wǎng)強國論壇的個案研究[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.