基于LDA的問答網站話題抽取算法

戰學剛 王 曉

基于LDA的問答網站話題抽取算法

戰學剛 王 曉

(遼寧科技大學軟件學院 遼寧 鞍山 114051)

為了幫助用戶在使用問答網站時準確地描述所提問題的話題，對社會化問答網站問題及話題進行了建模，發現問題的潛在語義關系，提出一種基于潛在狄利克雷分布LDA(Latent Dirichlet Allocation)的話題抽取算法。該算法通過挖掘問題與問題之間的潛在語義信息，找到潛在語義相類似的問題，在語義層面上抽取出話題集合，找到最符合的話題列表。在真實網站中的數據進行試驗證實，應用該算法可以有效擴大話題抽取的準確率和召回率。

LDA 問答網站 協同過濾 話題模型

0 引 言

社會化問答網站是區別于傳統問答網站(如百度知道)或百科類網站(維基百科)的基于社會化關系的新型問答網站，它的價值在于給用戶提供一個可以流動的“知識庫”。其“社會化”的定義主要體現在問題、話題、用戶之間的關注關系上。在社會化問答網站中，通過一系列的關注關系來使問題及其答案進入用戶的視線中，例如用戶可以關注“社交網站”這一話題，那么日后在該用戶的首頁就能不斷地推送出關于該話題下的熱門問答內容，從而加快知識的傳播速度。社會化問答網站是互聯網領域的一個創新應用。社會化問答網站最初的實現是國外的Quora(www.quora.com)。近兩年，國內相繼涌現出一批類似的社會化問答網站，包括最初的知乎(www.zhihu.com)，以及后來的百度新知、六達網等。

和傳統的問答網站相比，社會化問答網站通過加入社交元素來體現“社會化”的概念。通過使用“話題”來組織問題的結構，一個問題可以有多個話題，一個話題下包含多個問題。用戶可以通過關注特定的話題來發現他們感興趣的內容，給一個問題添加正確的話題可以讓該問題更好的流通[1]。因此，如何能夠自動識別問題的話題是問答網站數據挖掘研究中亟需解決的問題。

傳統的問題自動識別話題的方法是通過搜索引擎匹配關鍵字，然而該方法存在很大的局限性。例如，對于問題“今年詹姆斯能不能帶領邁阿密熱火隊奪冠？”，如果通過搜索引擎來尋找話題，那么會匹配“勒布朗·詹姆斯”、“邁阿密熱火”、“奪冠”。而顯然奪冠是不符合該問題的，并且如果通過人來識別的話，該問題的標簽應該是“NBA”、“籃球”。

針對上面的問題，本文提出了一種新的基于LDA的問題抽取話題的方法。區別于已有的方法，該方法在抽取話題的時候，考慮了問題與問題之間的語義相關性，通過尋找問題在語義空間的相類似問題，找到問答網站內已有類似問題的話題，來識別該問題的話題。在尋找類似問題時，考慮了潛在語義特征。傳統的問題相似性匹配一般基于TFIDF[2]。本文通過TFIDF結合LDA來判定相似問題，對于相似問題的話題，抽取出共現概率最高的話題作為最終結果。其基本思想是：首先根據數據集中已有問題以及話題的組合，作為訓練數據來估計LDA模型的參數；然后根據LDA模型對所有問題進行推導，構成LDA主題空間，當有新的問題提出的時候，根據LDA模型進行推導，并在主題空間中尋找最相似的問題；最后通過抽取相似問題的話題，將最符合的話題取出以作為結果。

根據以上的理論研究，本文在取自目前國內最大的社會化問答網站“知乎”網站內的數據進行了實驗評測。實驗結果表明，本文提出的方法在準確率、召回率上均優于目前已知的算法。

1 相關定義及理論

1.1 基本定義

在問答網站中，信息的流動主要依靠問題和話題。

問題：一個問題是問答網站中最基本的單元，問題可以是中文或是英文的字符串。

話題：一個話題是對一個問題所屬領域的抽象描述，一個問題可以有多個話題，一個話題也可以分別屬于多個問題。話題通常為一個詞或者短語。

1.2 LDA主題模型

在自然語言處理中，可以將詞項的概率分布定義為“主題”的概念。一個文檔的產生過程可以被看成是以一定的概率選擇了某一個“主題”，再以一定的概率從“主題”中選擇一些詞項的過程。而主題模型就是對文檔的生成過程進行模擬。主題模型的起源是隱語義索引(LSI)，在LSI的基礎上，Hofmann提出了基于概率的隱語義索引(pLSI)[3]。

LDA主題模型是由Blei等人提出的[4]，LDA在pLSI的基礎上進行了擴展，將每一個文檔的主題分布定義成Dirichlet分布，得到了一個更為完全的概率模型。 LDA模型假設語料庫中的每一篇文檔是與每一個主題的一個多項分布相對應。每個主題又與詞匯表中的單詞的一個多項分布相對應。

該模型有兩個參數需要推斷：一個是“文檔—主題”分布，另一個是“主題—單詞”分布。通過學習到這兩個參數，我們可以對任意的文檔進行主題分布推斷。例如，對于問題“喬布斯的離去對蘋果產生哪些影響”，LDA可以推斷出句子中的詞“蘋果”與“蘋果公司”意思更接近，而不是與“水果”意思更接近，盡管“蘋果”這個詞有多重意義。通過大量的語料進行學習，結合文本的上下文，通過LDA模型可以知道文檔的潛在主題。在參數推斷方法上面，主要的方法有LDA模型的作者提出的變分—EM算法，還有現在常用的Gibbs抽樣法[5]。

2 LDA模型訓練

基于LDA的話題抽取算法包含離線模型建立部分和在線推薦兩部分。在離線計算部分，根據人工標注的語料進行模型的訓練，得到詞對應語義的特征向量，然后根據訓練出的模型對每個問題進行推斷，最終得到每個問題的潛在語義向量。

在線推薦部分，首先根據LDA進行推斷[5]，得到問題的特征向量；然后在模型空間中進行搜索，拿到搜索結果后對結果進行重新排序，引入潛在語義向量的相似度得分，相似度計算使用余弦相似度計算法方法；最終得到語義上最相近的問題集合，抽取問題集合中話題共現率最高的詞作為最終的返回結果。

2.1 利用LDA獲取問題語義特征向量模型

設每一篇訓練文檔為d，所有訓練文檔的集合為語料集合，表示為D，統計得出集合D的文檔數量，表示為M。統計每個文檔d的詞項數目，得到訓練語料的總詞項數目V。

在LDA 模型中，潛在主題的數目K是固定不變的，并且需要在模型訓練之前人工給定，在K給定的前提下，一個文檔d的產生可以表示為以下兩個過程：

1) 從Dirichlet分布P(θ|α)中隨機選擇一個K維的向量，表示文檔d中的主題混合比例；

2) 根據特定的主題比例對文檔d中的每個詞w進行反復抽樣,得到P(wn|θα,β)。

其中a是一個K維的Dirichlet參數：

LDA是一個三層式結構，圖模型表示如圖1所示。其結構表現在：α和β是 語料級，每個corpus抽樣一次；θ是文檔級，每個文檔抽樣一次；w和z是詞級，每個文本中每個詞抽樣一次。LDA的生成過程如下：

對主題進行采樣，φ～Dir(β)k∈[1,k]

對語料中的第m個文檔

得到主題概率分布，θm～Dir(α)m∈[1,M]

得到文檔長度Nm～Poiss(ε)

對于文檔中的每一個單詞n，重復以下過程：

選擇一個主題z～p(z|θ)

生成一個單詞w～p(w|z,β)

圖1 LDA模型圖

在本文中，訓練數據為從“知乎”問答網站中抽取出的問題數據。一個話題下的所有問題作為一個文檔的概念，視為d。所有問題的集合視為文檔集合D。在進行LDA分析之前需要確定主題數目K，Dirichlet的先驗α 及β。在K值的選取上，我們通過使用不同的K值進行實驗對比準確度，最終發現K定為1000效果比較理想，而α及β的取值一般根據經驗可以設定為α=5/K,β=0.01，起到平滑數據的作用[6]。在一些情況下，也可以對α及β進行貝葉斯分析以確定更加準確的值[7]。

有了詞—主題矩陣，就可以對所有問題進行推斷：對于一個問題Q來說，首先進行分詞，得到詞的集合{w1,w2,…,wn}。假設詞的個數為N，根據LDA分析得到的矩陣Ewt，生成一個文檔(這里的文檔就是指一個問題)的主題分布，再生成N個主題，進而得到這篇文檔的N個詞的概率，可表示為：

其中θ是文檔的主題分布向量，z是N維的主題向量，w是N個詞組成的向量。

對網站內已有的所有問題進行LDA推斷，得到問題Q在不同潛在話題下的概率矩陣Eqt，矩陣中每一行代表一個問題在主題上的分布概率，而每一行有K維，每一維代表一個潛在主題：

至此，我們得到了問題特征向量矩陣，可以作為模型進行后續的計算。

2.2 在線推薦

在線推薦部分，當用戶提出問題時，首先通過用戶輸入的問題進行歸一化處理，去除停用詞，對英文進行大小寫轉換等，得到歸一化的問題Q。然后根據LDA模型對問題Q進行推導，得到問題Q在各個潛在語義話題上的概率向量V。通過計算問題語義向量與訓練好的所有問題的向量間的相似度，找到所有相似度大于閾值的相似問題集合。

在計算相似度部分，我們使用余弦相似度算法來計算兩組特征向量的相似性[8]，假設矩陣的一列所代表的問題Q′的向量為V′，則問題Q與Q′的相似度為：

因為在線推薦部分對性能的要求較高(用戶一般希望在500毫秒以下的時間內返回結果)，而通過LDA訓練所獲得的特征向量矩陣的維度一般較大(視問答網站的規模而定)，不能使用順序查找方法。在實際應用中，我們通過將計算好的特征向量集合存入多棵KD-Tree中，提高查詢的性能。KD-Tree是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形結構[10]，可以極大地提高多維向量空間中相似向量的檢索效率。多棵KD-Tree可以分別部署到不同的服務器上，在查詢時分別返回各自的查詢結果，最終匯總成最后結果。

得到相似問題集合后，通過抽取相似問題的話題，計算話題的共現概率，將共現概率較高的詞作為結果返回。

2.3 基于LDA的話題抽取算法

基于主題模型的話題推薦算法偽代碼描述如下：

離線計算部分：

輸入：問題集合Q，話題集合L，問題與話題的綁定關系QL。

輸出：LDA modelEwt。

步驟：

1. D=Set

2. for 話題I in L：

3. 根據QL提取話題I下的問題集合Iq={q1,q2,…,qn}

4. W=Set

5. for 問題q in Iq：

6. 問題q進行分詞，得到詞集合W′=(w1,w2,…,wn)

7. W.union(W′)

8. end for

9. 將W作為一個文檔加入到D

10. end for

11. 根據D訓練LDA model得到模型矩陣Ewt

在線推薦部分：

輸入：用戶提出的問題q，網站已有問題集合Q。

輸出：推薦添加的話題集合L。

步驟：

1. 對問題q進行分詞，得到詞集合W′={w1,w2,…,wn}

2. 根據Ewt推導出問題q的特征向量Vq

3. 初始化相似問題集合Qs

4. for q′ in Q:

5. 根據Ewt推導出問題q的特征向量Vq′

6. 得到Vq與Vq′的潛在語義以及TFIDF得分

7. if 得分>閾值，加入到集合Qs中

8. end for

9. 計算Qs中出現最多的n個話題作為結果集合

3 實驗評估

3.1 數據獲取與基準模型選擇

本文主要處理帶有話題的文檔,選取了國內最大的社會化問答網站知乎(www.zhihu.com)下的5萬個話題，以及話題下的100萬個問題，作為訓練模型用的數據。

我們選取了5個領域下用戶新提出的1000個問題，作為測試用數據集合，如表1所示。

表1 測試問題領域分布

在實驗中,選擇了兩種基線模型與本文所提算法相對比。第一種是改進的基于TFIDF的協同過濾算法(記為TFIDF)[9]。該算法用改進的權重算法表示文本向量，使用改進后的文本向量作為特征向量。第二種是搜索引擎搜索關鍵詞返回的結果(記為SEARCH)。

對于測試問題集合中的1000個問題，本文提出的算法以及兩種對比算法均會給出建議添加的話題列表，通過準確率、召回率來評價每個算法的優劣程度。準確率體現了算法所給出的話題的正確程度，而召回率體現了算法給出的話題的多樣性。為了能夠準確評價哪些話題是正確的話題，我們邀請了各個領域的網站編輯來進行人工標注。選用網站編輯的數據而不使用普通用戶的操作數據是因為網站編輯一般對于所屬領域比較熟悉，能夠相對正確、客觀地給出問答網站內該領域的問題所對應的正確話題。

對于一個問題Q來說，設|Ls|代表算法對于問題Q給出的話題集合，|Lu|代表網站編輯對于問題Q給出的話題集合。則準確率(precision)和召回率(recall)分別定義為：

3.2 實驗結果及分析

表2和表3分別給出了使用基于LDA的話題抽取算法的召回率以及準確率，表4 給出了本文模型與基線模型結果列表比較的結果。通過實驗結果發現，本文所提出的基于LDA的話題抽取算法在召回率與準確率上均高于對比算法，并且相比于傳統算法，基于LDA的推薦算法能更好地推薦出反映用戶提問時問題的主題。

表2 召回率測試結果

領域召回率NBA83%建筑74%醫學91%音樂88%心理學76%

表3 準確率測試結果

領域準確率NBA74%建筑63%醫學65%音樂56%心理學34%

表4 對比基線模型結果

通過記錄每一次話題抽取的起始時間和結束時間，圖2給出了本文算法在這1000個問題上的性能表現。其中橫坐標為問題編號(question id)，縱坐標為相應時間，單位為毫秒(ms)。實驗環境為2.4 GHz Intel Core i5的CPU，4 GB的內存，256 GB硬盤的PC機2臺，操作系統為Linux。從圖中可以看到，本文算法的響應時間大部分集中在300 ms左右，在性能上完全滿足在線使用的需求。

圖2 測試問題話題抽取響應時間

4 結 語

本文參考了經典LDA主題模型的優點，對社會化問答網站的問題進行建模，將潛在語義信息融入了話題抽取算法中，彌補了傳統抽取算法在語義相關度不足的缺點，提高了話題推薦的準確性。通過實驗表明，該算法能夠顯著提高推薦話題的相關性，提高現有推薦算法的準確率以及召回率。目前該算法被應用到問答網站“知乎”(www.zhihu.com)的提問模塊中，如圖3所示。當用戶提出一個問題時，該模塊會自動推薦5個話題。圖3中，當用戶提出的問題是關于長城汽車的問題時，系統自動推薦了4個相關的話題：其中“汽車”，“車輛”，“長城(汽車品牌)”，是和問題具有很強語義相關性的，可以認為是正確的推薦。而“SUV”是長城這款車的所屬類型，也可以認為是正確推薦。

圖3 實際運行效果

從該算法的實際運行情況統計，用戶一般會采納系統推薦的話題中的3～4個，極大地拓展了問題的流通渠道。

[1] 劉高勇,鄧勝利.社交問答服務的演變與發展研究[J].圖書館論壇,2013(1):17-19.

[2] 施聰鶯,徐朝軍,楊曉江.TFIDF算法研究綜述[J].計算機應用,2009(S1):167-171.

[3] Hofmann T.Probabilistic latent semantic analysis[C]//Proceedings of the 22nd annual international ACM conference on Research and development in information retrieval,1999,15:50-57.

[4] Blei D,Ng A,Jordan M.Latent DirichletAllocation[J].Journal of Machine Learning Research,2003(3):993-1022.

[5] Griffiths T L,Steyvers M.Finding scientific topics[J].Proceedings of the National Acdademy of Sciencs,2004,101(S1):5228-5235.

[6] Liu Zhiyuan,Zhang Yuzhou,Edward Y Chang.PLDA+:Parallel Latent Dirichlet Allocation with data placement and pipeline processing[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):1-18.

[7] Steyvers M,Griffiths T.Probabilistic topic models:Latent Semantic Anlysis:A road to meaning[M].Laurence Erlbaum,2006.

[8] Xian Zhang,Yu Hao,Zhu Xiaoyan.Information distance from a question to an answer[C]//Proceedings of KDD ’07,2007:874-883.

[9] 鄭霖,徐德華.基于改進TFIDF算法的文本分類研究[J].計算機與現代化,2014(9):6-9.

[10] 李航.統計學習方法[M].北京:清華大學出版社,2012.

LDA-BASED Q & A WEBSITES QUESTION LABEL EXTRACTION ALGORITHM

Zhan Xuegang Wang Xiao

(SchoolofSoftwareEngineering,UniversityofScienceandTechnologyLiaoning,Anshan114051,Liaoning,China)

To help people accurately describe the topics of the question raised when using question and answer (Q & A) websites, we modelled the questions and topics in socialised Q&A websites, found the latent semantic relationship among questions, and proposed an LDA-based topic extraction algorithm. The algorithm finds the questions with latent semantics similarity by digging up latent semantic information between questions, extracts the topics set on semantic level, and finds the list of topics that matches the most. It has been proved by the test with the data in actual websites that the application of the algorithm can effectively improve the precision and recall rates of topic extraction.

Latent Dirichlet allocation (LDA) Q&A websites Collaborative filtering Topic model

2014-11-20。戰學剛，副教授，主研領域：自然語言處理，數據挖掘。王曉，碩士生。

TP391.1

A

10.3969/j.issn.1000-386x.2016.04.023