林鴻飛,王 健,熊大平,劉曉鳴
(大連理工大學 計算機科學與技術學院,遼寧 大連116024)
在社區問答系統中的用戶形形色色,良莠不齊,通常把行為活躍且具有一定數量的回答被提問者或系統評定為最佳答案的用戶稱為專家用戶。如果能在龐大的用戶群中辨別出專家用戶,提出者可以把新提出的問題推薦給專家用戶從而能及時地得到準確專業的答復,同時使外部搜索的信息量能有效地得到擴充。于是,專家發現成為社區問答中一個新的重要的研究熱點。
對于社區問答中的專家發現,學者們提出了很多不同的技術和方法。主要方法有建立用戶模型[1,2]、基于語義主題分析方法[3-5]和鏈接分析算法[6,7]?;谟脩裟P偷姆椒?,Chen等人[1]提出了一種基于用戶聲譽的結構分析模型來對用戶的專家得分進行評級排名。Kao等人[2]進一步綜合了用戶的知識領域、用戶聲望和鏈接分析來評定專家用戶?;谡Z義主題分析的方法,Riahi等人[3]使用分段主題模型來研究專家用戶發現問題,效果比LDA模型要好一些。Qu等人[4]提出了一種基于概率潛在語義分析 (PLSA)的模型來進行專家發現,進而將新問題推薦給專家。Liu等人[5]綜合考慮用戶的歷史回答信息、用戶權威度和用戶活躍度,提出了一種混合語言模型和LDA模型的方法來向專家用戶推薦新問題?;阪溄臃治龅姆椒?,Jurczyk等人[6]將用戶看作節點并利用HITS算法尋找權威用戶。Jie等人[7]則HITS算法進行了改進,使用帶權重的HITS算法計算用戶的權威值。此外,Liu等人[8]就將體育比賽中的競爭機制應用于專家發現的研究中,對用戶進行兩兩比較,計算用戶的權威值。
專家用戶與普通用戶之間存在很大的區別,部分學者通過觀察專家用戶的習慣,如專家用戶的初期活動規律[9]和偏好選擇規律[10],來構建模型以更好地發現專家用戶。本文通過觀察得知大部分專家用戶的擅長領域是相近的,根據用戶不同類別的參與度不同,提出了一種基于用戶類別參與度的社區問答專家發現方法,除了考慮所屬類別回答者的回答質量外,還考慮了相近類別中回答者的回答質量,綜合考慮來分辨出專家用戶。
PageRank算法在1998年由Sergey Brin和Larry Page提出,是一種靜態的網頁評級算法,可用于提高搜索引擎對網頁排序的準確度[11]。主要思想是:
(1)網頁i指向網頁j的超鏈接表示對網頁j權威的隱含認可,即網頁j的權威度與其鏈入超鏈接數量成正比關系;
(2)指向網頁j的網頁i自身權威值對網頁j的權威度會產生影響。若高權威值網頁i1和低權威值網頁i2都指向網頁j,則網頁i1對網頁j權威度的貢獻要比網頁i2要大些。即一個被其它重要網頁所指向的網頁也很重要。
將PageRank算法運用于本文的專家發現時,網頁代指用戶。對于一個社區問答網絡,從一個用戶出發,鏈接出去的其它用戶的概率為(1-λ);則給定一用戶i,其Page-Rank值定義公式如下
式中:Oj——用戶j的出鏈數。初始值設為:P(i)=1/N,i=1,……,N;λ取值為0.15。故P(i)∈ [0,1]。
HITS算法在1998年由Jon Kleinberg提出,對網頁的評級指標為權威等級 (authority)和中心等級 (hub)。其關鍵思想是:權威網頁和中心網頁之間的關系相互影響并促進。即權威等級高的網頁會被很多中心等級高的網頁所指向,同理中心等級高的網頁會被很多權威等級高的網頁所指向。
將HITS算法運用于本文的專家發現時,網頁代指用戶。對于一個社區問答網絡,每個用戶i的權威分值表示為a(i),中心分值表示為h(i),則兩種分值的相互增益關系可表示成公式如下
初始值設為:a(i)=h(i)=1,i=1,……,N。每次迭代后,都進行歸一化處理∈ [0,1],h(i)∈ [0,1]。
LDA主題模型是一種包含詞、主題和文檔三層結構的產生式概率模型,其概率圖模型如圖1所示。LDA生成文檔中詞的過程是一個概率抽樣過程,由參數 (α,β)來確定文檔集合中的三層結構,其中參數α控制了文檔中不同主題的相對出現概率,參數β調節所有主題中不同詞的出現概率分布,其生成文檔的具體過程如下:
(1)由參數α確定的Dirichlet(a)分布得到文檔d上的主題多項式分布函數θd。
(2)由參數β確定的Dirichlet(β)分布得到主題t上的詞多項式分布函數(t)。
(3)循環抽樣得到每個文檔中的每個單詞wdi:
1)從文檔d對應的θd中,抽樣得到主題t。
2)從主題t對應的(t)中,抽樣得到一個單詞作為wdi。
圖1 LDA的概率圖模型
將LDA主題模型運用于本文的專家發現時,對于類別的主題分布,一篇文檔對應為某一類別中所有的問題答案集;對于用戶的主題分布,一篇文檔對應為某一用戶參與的所有的問題和答案。
通過觀察百度知道的用戶信息,可以從中得出一個結論:大部分專家用戶的擅長領域是相近的。圖2是從百度知道中截取的兩位有代表性的專家用戶的信息。第一位專家用戶的擅長領域是 “文化教育”,第二位專家用戶的擅長領域是 “運動娛樂”。由圖2可見,對某一類別領域進行專家發現時,用戶u在其它相近的類別參與度,有助于提高在該類別領域的專家得分,故本文提出了一種基于用戶類別參與度的社區問答專家發現方法。
圖2 百度知道專家用戶信息
基于用戶類別參與度的專家發現系統的基本流程如圖3所示,具體分為以下過程:
(1)根據用戶之間提出問題、回答問題的關系,對每一個類別,將社區問答中的用戶構建成一個有向圖網。
(2)對每一個類別用鏈接分析算法PageRank和HITS得到用戶的初步專家得分。
(3)將每一個類別看成一個文檔,利用LDA主題模型來進行訓練,得到每一個類別的主題分布,利用KL距離來計算類別之間的相似度。
(4)把用戶看成文檔,用LDA模型進行推斷,得到每一個用戶的主題分布,利用KL距離來計算用戶對每一個類別的參與度。
(5)根據類別間相似度和用戶類別參與度,得到本類別對應的其它相近類別參與度得分。
(6)最后,綜合用戶在本類別的初步專家得分和其它相近類別的參與度得分,即為最終的本類別專家得分。
圖3 基于類別參與度的專家發現系統框架
在社區問答系統中,用戶j回答用戶i提出的問題q,則用戶i和用戶j之間存在著鏈接關系,如圖4(a)所示。用戶3回答了用戶1的問題,則轉化為用戶1指向用戶3的有向邊,如圖4(b)所示。于是,對每一個類別,根據用戶之間提出問題、回答問題,答案對應問題的關系,可以構建成一個用戶有向圖網。
圖4 社區問答用戶鏈接有向圖
設類別集合為 C = {c1,c2,...,cn},用戶集合為U ={u1,u2,...,um},則給定類別c,可將類別c中的用戶網絡看作是一個有向圖Gc= (Vc,Ec),其中,Vc= {ui}是類別c中所有用戶的集合,Ec={eij}是類別c中用戶間的有向邊集合,eij指用戶uj回答了用戶ui提出的問題。
每一位專家用戶都有自己感興趣,并擅長的領域,在社區問答中,會經常參與到對應的類別中為他人提供專業標準的答案。于是,每一個用戶在不同的類別中具有不同的初步專家得分。
對每一個類別,先構建一個用戶有向圖網,再利用鏈接分析算法,得到初步專家得分。給定類別cj,用戶ui,可如下得到用戶的初步專家得分。
(1)PageRank算法:PageRank值體現了用戶的權威等級,故初步專家得分為對應的PageRank值,即為scorePageRank(ui,cj)=P(i)∈ [0,1]。
(2)HITS算法:權威分值 (Authority)體現了回答者的重要性,中心分值 (Hub)體現了提問者的重要性,故把權威分值作為初步專家得分,即scoreHITS(ui,cj)=a(i)∈ [0,1]。
對某一類別領域進行專家發現時,用戶u在其它相近類別的參與度,有助于提高在該類別領域的專家得分,故需要得到兩兩類別間的相似度。
將所有類別的問題答案集看成一個語料集D,每一個類別看成一個文檔d,文檔的內容為該類別中所有的問題和答案。利用LDA模型,進行訓練,可以得到每一個類別對應的K維主題分布p(z|c),K為主題個數。
利用KL距離[12]來計算類別之間的相似度,則類別ci和類別cj的相似度計算公式如下
用戶類別參與度是指在某一類別領域進行專家發現時,用戶在其它相近類別的參與度。由上面得到的類別間相似度,可以得到該類別的相近類別;參與度為用戶主題分布和類別主題分布之間的相似性。
先得到用戶的主題分布。將所有用戶參與的問題和答案作為一個語料集,語料集中的文檔個數為用戶數量,文檔內容為用戶的屬性,即用戶參與的所有的問題和答案。利用LDA模型,進行推斷,可以得到每一個用戶對應的K維主題分布p(z|u),K為主題個數。
利用KL距離[12]來計算用戶對類別的參與度,則用戶ui在類別cj中的參與度計算公式如下
除了考慮所屬類別回答者的回答質量外,還考慮了相關類別中回答者的回答質量,綜合考慮來分辨出專家用戶。本文采用線性結合的方法,綜合用戶在本類別的專家得分和其它相近類別的參與度得分,作為最終的本類別專家得分。
對于用PageRank算法,其綜合得分如式 (5)所示
其中,Sim(cj,ck)>λ,λ為判斷相近類別的閾值。
同理,用HITS算法時,其綜合得分如式 (6)所示
其中,Sim(cj,ck)>λ,λ為判斷相近類別的閾值。
由于 Par(ui,cj)∈ (0,1],score(ui,ck)∈ [0,1],故為類別總數。score(ui,cj)值越大,則用戶ui在類別cj中稱為專家的可能性也越大。
本文采用的實驗語料來自Yahoo!Answers網站上抽取的真實標注數據集。去掉匿名用戶和匿名者給出的答案,實驗語料集共有94596個問題和587354個對應的答案,詳細的信息見表1。
本文對比了5種不同的專家發現方法來進行評價本文所提出方法的性能,其中 (2)為文獻 [7]中的方法。
(1)HITS:分別對每一個類別,使用HITS算法
表1 語料集的統計信息情況
(2)WeightHITS[7]:在方法 (1)的基礎上,使用帶權重的HITS算法
(3)BoostHITS:在方法 (1)的基礎上,使用基于類別參與度的HITS算法
(4)PageRank:分別對每一個類別使用PageRank算法
(5)BoostPageRank:在方法 (4)的基礎上,使用基于類別參與度的PageRank算法
本文采用AP@10和MAP兩種指標來進行結果的評價,得分越高,對應的性能越好。本文的方法與對比實驗的方法在評價指標AP@10上的結果如表2所示,在評價指標MAP上的結果如圖5所示。
表2 5種方法的AP@10值
圖5 5種方法的MAP值
本文采用了AP@10指標和MAP指標來評價方法的效果,結果評價數據如表2和圖5所示,并對實驗結果進行如下分析。
(1)對于常規的PageRank算法和 HITS算法而言,PageRank算法的結果要明顯好于HITS算法。這是因為HITS算法有權威分值 (authority)和中心分值 (hub)兩個評級,權威分值體現了回答者的重要性,中心分值體現了提問者的重要性,兩者是相互關聯、耦合的。故一些提問比較多的用戶會影響回答者的權威分值。
(2)帶權重的HITS算法比常規的HITS算法略好一些,說明用戶之間邊的連線具有差異性。用戶i回答了用戶j提出的問題,根據答案是否被選為正確答案,用戶j指向用戶i的邊權重應設為不同,選為正確答案的,邊權重應大些。
(3)基于類別參與度的HITS算法比前兩個效果又要好一些,說明對某一類別領域進行專家發現,用戶u在其它相近的類別參與度,有助于提高在該類別領域的專家得分。進一步證明了本文提出的方法。
(4)基于類別參與度的PageRank算法的效果是最好的,比BoostHITS算法要好很多。這與常規的PageRank算法比HITS算法好很多是相一致的。由于用戶有向圖的拓撲結構的微小的改動能夠明顯改變HITS算法得到的權威分值和中心分值,而對于PageRank算法來說幾乎沒有影響。因此由語料得到的網絡圖可能會存在影響。
(5)本文進一步采用了MAP指標來進行評價,如圖5所示,其結果趨勢與AP@10指標的結果趨勢是相一致的。每一個類別返回前20個用戶,故MAP值也比較高。
結果分析部分是通過實驗得到的數據,來定量地分析本文方法的有效性。為了更直觀地分析,利用網絡分析工具UCINET來可視化用戶網絡圖,圖6為社區問答系統中用戶有向網絡圖。
圖6 (a)為類別 “Homework Help”中與15個專家用戶有關聯的用戶構成的有向網絡圖,圖6(b)為所有類別中與15個專家用戶有關聯的用戶構成的有向網絡圖,圖中的小圓點為一般用戶,大圓點為專家用戶,帶箭頭的邊為用戶間的關系,箭頭的指向為提問者用戶指向回答者用戶(意義與圖4(b)一致),而且兩圖中專家用戶的位置是一一對應的。從圖6中可以看出,加入其它參與類別的信息后,專家用戶的入度數更多了,更容易成為一個小網絡的中心,即權威性也有所提高,從而更有效地進行專家發現。
表3 為圖6中用戶的入度數??芍?,加入其它參與類別的用戶后,15個專家用戶的平均入度數增加了一倍多,而且整個網絡用戶的平均入度數也有所增加。說明專家用戶在其它類別的參與度也是非常多的,因此,利用用戶在其它類別的參與度信息可以有效地提高本類別的專家發現水平。
圖6 社區問答系統中用戶有向網絡
表3 社區問答系統中用戶入度數
本文提出了一種基于用戶類別參與度的方法,來幫助辨別社區問答中的專家用戶。首先利用鏈接分析方法Page-Rank和HITS分別計算用戶在每一個參與類別的專家得分,然后由LDA模型得到類別和用戶的主題分布,再利用KL距離函數得到類別間的相似度和用戶對每一個參與類別的參與度得分,最后線性綜合用戶在本類別的專家得分與其它相近類別的參與度得分即為用戶在該類別的最終得分。如實驗部分所述,本文所述的專家發現方法顯示出了良好的性能。該方法能夠很好地挖掘出興趣、愛好和擅長領域相近的專家用戶,但對于擅長領域差異比較大的、或是沒有交集的專家用戶,本方法還有待于改進,這也是今后需要進一步研究的方向。
[1]Chen Lin,Nayak R.Expertise analysis in a question answer portal for author ranking [C]//Washington,USA:Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology,2008:134-140.
[2]Kao Weichen,Liu Duenren,Wang Shiuwen.Expert finding in question-answering websites:A novel hybrid Approach [C]//Sierre,Switzerland:Proceedings of the ACM Symposium on Applied Computing,2010:867-871.
[3]Riahi F,Zolaktaf Z,Shafiei M,et al.Finding expert users in community question answering [C]//Lyon,France:Proceedings of the 21st International Conference Companion on World Wide Web,2012:791-798.
[4]Qu Mingcheng,Qiu Guang,He Xiaofei,et al.Probabilistic question recommendation for question answering communities[C]//CM:Proceedings of the 18th International Conference on World Wide Web,2009:1229-1230.
[5]LIU Mingrong,LIU Yicen,YANG Qing.Predicting best answerers for new questions in community question answering[M].Web-Age Information Management.Springer Berlin Heidelberg,2010:127-138.
[6]Jurczyk P,Agichtein E.Discovering authorities in question answer communities by using link analysis[C]//Lisboa,Portugal:Proceedings of the 16th ACM Conference on Conference on Information and Knowledge Management,2007:919-922.
[7]Jie Shen,Wen Shen,Xin Fan.Recommending experts in Q & A communities by weighted HITS algorithm [C]//Chengdu,China:International Forum on Information Technology and Applications,2009:151-154.
[8]Liu Jing,Song Y I,Lin C Y.Competition-based user exper-tise score estimation [C]//Beijing,China:Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval,2011:425-434.
[9]Aditya P,Rosta F,Joseph A K,et al.Early detection of potential experts in question answering communities [C]//Girona,Spain:Proceedings of the 19th of User Modeling,Adaptation and Personalization,2011:231-242.
[10]Aditya P,Joseph A K.Expert identification in community question answering:Exploring question selection bias[C]//Toronto,Canada:Proceedings of the 19th ACM International Conference on Information and Knowledge Management,2010:1505-1508.
[11]GUO Qingbao,JIA Daiping.Improved PageRank algorithm of merging feedback information and topical relationship [J].Computer Engineering and Design,2011,32 (12):4071-4074(in Chinese).[郭慶寶,賈代平.融合反饋信息與內容相關度的PageRank改進算法 [J].計算機工程與設計,2011,32 (12):4071-4074.]
[12]Celikyilmaz A,Tur D H,Tur G.LDA based similarity modeling for question answering [C]//Stroudsburg,PA,USA:Proceedings of the NAACL HLT Workshop on Semantic Search,2010:1-9.