基于LDA的問答網(wǎng)站話題抽取算法

戰(zhàn)學(xué)剛 王 曉

基于LDA的問答網(wǎng)站話題抽取算法

戰(zhàn)學(xué)剛 王 曉

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

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

LDA 問答網(wǎng)站 協(xié)同過濾 話題模型

0 引 言

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

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

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

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

根據(jù)以上的理論研究，本文在取自目前國內(nèi)最大的社會化問答網(wǎng)站“知乎”網(wǎng)站內(nèi)的數(shù)據(jù)進行了實驗評測。實驗結(jié)果表明，本文提出的方法在準確率、召回率上均優(yōu)于目前已知的算法。

1 相關(guān)定義及理論

1.1 基本定義

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

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

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

1.2 LDA主題模型

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

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

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

2 LDA模型訓(xùn)練

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

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

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

設(shè)每一篇訓(xùn)練文檔為d，所有訓(xùn)練文檔的集合為語料集合，表示為D，統(tǒng)計得出集合D的文檔數(shù)量，表示為M。統(tǒng)計每個文檔d的詞項數(shù)目，得到訓(xùn)練語料的總詞項數(shù)目V。

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

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

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

其中a是一個K維的Dirichlet參數(shù)：

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

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

對語料中的第m個文檔

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

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

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

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

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

圖1 LDA模型圖

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

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

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

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

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

2.2 在線推薦

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

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

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

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

2.3 基于LDA的話題抽取算法

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

離線計算部分：

輸入：問題集合Q，話題集合L，問題與話題的綁定關(guān)系QL。

輸出：LDA modelEwt。

步驟：

1. D=Set

2. for 話題I in L：

3. 根據(jù)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. 根據(jù)D訓(xùn)練LDA model得到模型矩陣Ewt

在線推薦部分：

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

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

步驟：

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

2. 根據(jù)Ewt推導(dǎo)出問題q的特征向量Vq

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

4. for q′ in Q:

5. 根據(jù)Ewt推導(dǎo)出問題q的特征向量Vq′

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

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

8. end for

9. 計算Qs中出現(xiàn)最多的n個話題作為結(jié)果集合

3 實驗評估

3.1 數(shù)據(jù)獲取與基準模型選擇

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

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

表1 測試問題領(lǐng)域分布

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

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

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

3.2 實驗結(jié)果及分析

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

表2 召回率測試結(jié)果

領(lǐng)域召回率NBA83%建筑74%醫(yī)學(xué)91%音樂88%心理學(xué)76%

表3 準確率測試結(jié)果

領(lǐng)域準確率NBA74%建筑63%醫(yī)學(xué)65%音樂56%心理學(xué)34%

表4 對比基線模型結(jié)果

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

圖2 測試問題話題抽取響應(yīng)時間

4 結(jié) 語

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

圖3 實際運行效果

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

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

[2] 施聰鶯,徐朝軍,楊曉江.TFIDF算法研究綜述[J].計算機應(yīng)用,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].計算機與現(xiàn)代化,2014(9):6-9.

[10] 李航.統(tǒng)計學(xué)習(xí)方法[M].北京:清華大學(xué)出版社,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。戰(zhàn)學(xué)剛，副教授，主研領(lǐng)域：自然語言處理，數(shù)據(jù)挖掘。王曉，碩士生。

TP391.1

A

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