一種基于詞覆蓋的新聞事件脈絡(luò)鏈構(gòu)建方法

付佳兵 董守斌

?

一種基于詞覆蓋的新聞事件脈絡(luò)鏈構(gòu)建方法

付佳兵 董守斌?

華南理工大學(xué)廣東省計算機網(wǎng)絡(luò)重點實驗室, 廣州 510640; ?通信作者, E-mail: sbdong@scut.edu.cn

針對目前構(gòu)建新聞脈絡(luò)鏈只關(guān)注新聞脈絡(luò)鏈的主題相似性和文檔重要性, 而忽略新聞脈絡(luò)鏈邏輯連貫性和可解釋性的不足, 以及新聞數(shù)據(jù)集合指數(shù)級增長帶來的算法復(fù)雜度問題, 從詞覆蓋的角度提出一種新聞脈絡(luò)鏈構(gòu)建方法, 利用新聞的評論信息來定位新聞事件轉(zhuǎn)折點, 用主題相似與稀疏差異的思想以及RPCA方法對文檔進行邏輯建模, 利用隨機游走以及圖遍歷的方法, 量化并生成可解釋且具有很好邏輯連貫性的脈絡(luò)鏈。雙盲實驗表明, 與其他算法相比, 該方法取得較好的效果。

新聞脈絡(luò); 詞覆蓋; 可解釋; 健壯主成分分析; 隨機游走

面對大量信息, 讀者容易迷失在局部的信息中,逐漸喪失對信息的全局把控。因此, 構(gòu)建新聞脈絡(luò)鏈成為當(dāng)今迫切需要解決的問題。構(gòu)建新聞脈絡(luò)鏈?zhǔn)菍π侣勈录适掳l(fā)展脈絡(luò)結(jié)構(gòu)的捕捉, 因此新聞故事發(fā)展需要具備很好的邏輯發(fā)展特性和可解釋性機制?，F(xiàn)有脈絡(luò)鏈構(gòu)建研究存在以下三方面的問題: 1)脈絡(luò)陷入局部, 沒有全局觀; 2)脈絡(luò)關(guān)注主要集中在文檔重要性、相關(guān)性以及相似性等一維內(nèi)容層面, 忽視文檔之間的二維邏輯連貫語義層面; 3)脈絡(luò)構(gòu)建復(fù)雜度高, 多數(shù)研究為保證脈絡(luò)的全局特性而對整個數(shù)據(jù)集進行多次迭代, 缺乏對數(shù)據(jù)集大小進行有效降級。

基于以上問題, 本文提出一種新聞脈絡(luò)鏈構(gòu)建方法, 將脈絡(luò)構(gòu)建視為詞覆蓋問題, 在依賴新聞內(nèi)在邏輯性進行詞覆蓋的同時, 也完成了結(jié)構(gòu)化邏輯且可解釋的脈絡(luò)構(gòu)建。本文算法可根據(jù)讀者感興趣的新聞熱點事件, 自動生成該新聞事件的新聞脈絡(luò)鏈, 能夠幫助讀者把控新聞事件的全局發(fā)展脈絡(luò)。例如, 讀者對馬航(MH370)事件感興趣, 那么算法給出的可能輸出如圖1所示。

1 相關(guān)工作

信息過載使得研究人員開始尋找各種信息中隱含的故事發(fā)展脈絡(luò), 比如微博[1-4], 新聞[5-7], 論文[8-9]以及郵件[10]。故事生成[11-12]較早開始對故事脈絡(luò)進行定義和建模, 但只關(guān)注規(guī)則模版的設(shè)定及其推演。事件檢測[13-14]嘗試發(fā)現(xiàn)信息中隱含的新聞事件, 但并不嘗試將其連接起來形成完整的脈絡(luò)發(fā)展。文獻[2-3]嘗試解決脈絡(luò)的連接問題, 但基于局部貪心的思想缺乏全局觀。文獻[5]構(gòu)建的是全局脈絡(luò), 其代價是需對整個候選新聞集合進行迭代, 嚴(yán)重影響算法的可擴展性。事件追蹤[15]利用有監(jiān)督的機器學(xué)習(xí)算法, 將新聞劃分到大的新聞子類, 但是需要進行人工標(biāo)注, 難度大。事件追蹤與TDT[16](主題檢測和追蹤)的思想類似, 不同之處在于后者將事件追蹤抽象為主題追蹤。TDT致力于生成文本的故事鏈, 主要包括五大任務(wù): 故事分段、主題追蹤、主題檢測、起始故事檢測以及鏈接檢測。大部分TDT的研究主要關(guān)注文本相關(guān)性或者相似性, 在其基礎(chǔ)上進行文本分類和聚類, 并未考慮文本間的邏輯轉(zhuǎn)換關(guān)系[17]。文獻[18]通過考慮文本間相互作用構(gòu)建主題結(jié)構(gòu)圖, 基于結(jié)構(gòu)圖對主題變化趨勢進行追蹤。類似地, 文獻[13-19]通過發(fā)現(xiàn)新聞事件子類, 并利用其相互依賴關(guān)系構(gòu)建圖結(jié)構(gòu)(動態(tài)主題模型), 但是均未考慮圖結(jié)構(gòu)的連貫性問題。

MDS(多文本總結(jié))通過選取代表性的句子, 以時序的方式構(gòu)建時間軸, 完成對文檔集合的總結(jié), 為構(gòu)建脈絡(luò)提供了一個文本總結(jié)的新思路。句子的選擇標(biāo)準(zhǔn)方法有很多種, 基本上分為三大類: 一類是句子本身的屬性, 比如文獻[20]用句子的信息含量(通過最大化信息含量高的詞), 文獻[21-22]用句子的相關(guān)性、覆蓋性、連貫性以及多樣性, 文獻[23]用句子的不確定性, 文獻[24]用句子的代表性和差異性; 另一類是句子的結(jié)構(gòu)屬性, 文獻[19-25]通過構(gòu)建句子圖譜, 使用圖譜的中心化句子節(jié)點作為候選句子; 第三類是前兩類的綜合, 文獻[26-27]通過矩陣分解對句子進行潛在的語義分析。這三大類方法(包括第三類的潛在語義)以及TDT都無法給生成的脈絡(luò)結(jié)果提供可解釋性, 而缺乏可解釋機制會大大增加對脈絡(luò)鏈的理解難度。

2 算法總體設(shè)計

2.1 詞覆蓋方法

典型的搜索查詢?nèi)蝿?wù)流程如下: 給定查詢詞集合, 搜索引擎在數(shù)據(jù)庫中逐個掃描并返回覆蓋查詢詞的文檔集合。簡單歸納可知, 搜索引擎的工作實質(zhì)上是基于查詢詞的文檔覆蓋。新聞脈絡(luò)鏈, 其反映的是新聞事件的邏輯發(fā)展, 與搜索引擎有相同亦有不同: 相同之處是都可看成文檔覆蓋問題; 不同之處是文檔覆蓋的查詢詞不再是用戶輸入的新聞事件查詢詞, 取而代之的是能反映該查詢詞所對應(yīng)新聞事件新聞脈絡(luò)的詞集合。一旦結(jié)果文檔集合能覆蓋反映該新聞事件脈絡(luò)的詞集合, 那么文檔集合即是結(jié)果新聞脈絡(luò)。對比異同, 新聞脈絡(luò)鏈的構(gòu)建引擎實質(zhì)上是附加查詢詞擴展層的搜索引擎。

2.2 設(shè)計框架

基于查詢詞返回結(jié)果文檔的研究已經(jīng)很成熟, 因此構(gòu)建新聞脈絡(luò)圖的關(guān)鍵是快速定位詞集合, 即完成從新聞事件查詢詞到的擴展。很難通過的直接擴展得到, 因為在未徹底了解新聞事件前, 無法預(yù)先得知; 即便了解, 由于理解上的主觀性, 也無法確切得知。因此,只是概念化的詞集合, 無從獲知。若已知, 則新聞脈絡(luò)已知。由于無法“正面”得知, 本文則通過采用不斷縮小候選詞集合的方法, 不斷逼近真實的, 從而間接獲取。

2.3 算法描述

2.3.1 時間評論聚類算法

某段時間特別受關(guān)注的新聞很可能是新聞事件的轉(zhuǎn)折點, 即所需捕捉候選新聞文檔集合, 因此可利用新聞報道的用戶關(guān)注度來定位新聞事件轉(zhuǎn)折點。用戶關(guān)注行為有強弱兩種: 強用戶評論行為和弱用戶瀏覽行為, 一般瀏覽行為很難準(zhǔn)確獲取。文獻[28]表明用戶的評論和瀏覽行為存在強一致性, 即評論行為越多, 瀏覽行為也越多, 因此可通過度量評論行為來達到度量評論和瀏覽行為的目的。

K-means算法[29]是最簡單易行的聚類算法之一, 它能夠快速有效地處理大規(guī)模數(shù)據(jù), 運用十分廣泛。本文用二維元組<評論數(shù)量, 評論時間>表示樣本點x, 采用K-means對樣本集合{1,2, …,x}進行聚類, 剔除小于10個樣本的小型類別, 保留剩余類別所有樣本點。

2.3.2 文檔建模算法

主題模型pLSI[30]和LDA[31]廣泛用于文檔建模領(lǐng)域。給定一篇文檔, 形式化描述如下:

=+,

其中代表低秩主題部分,代表高斯噪音部分。

但這并不總符合現(xiàn)實情況。如圖3(a)所示, 文檔中常出現(xiàn)一些頻率異常高的詞, 因此詞頻分布誤差并不是主題模型所假設(shè)的噪音方差小且服從高斯分布, 而是高頻噪音誤差。高頻噪音誤差并非沒有價值, 相反地, 它恰恰最能反映文檔間的差異性。基于此, 如圖3(b)所示, 對文檔進行低秩主題部分-稀疏高頻部分建模, 形式化表示如下:

=+,

其中代表低秩主題部分,代表稀疏高頻部分。為便于后續(xù)描述, 將表述為主題部分,表述為稀疏部分。

文檔集合的分離過程是在盡可能用低秩主題模型擬合文檔集合的基礎(chǔ)上, 最小化中的非零項個數(shù)。只有在盡可能剝離共有主題部分之后,才能準(zhǔn)確描述文檔集合中文檔之間的差異性部分, 因此分離定義如下:

2.3.3 隨機游走算法

關(guān)系作用傳遞分為顯式和隱式: 顯式關(guān)系傳遞指兩篇文檔包含相同的詞; 隱式關(guān)系傳遞指兩篇文檔中的前一篇包含這個詞, 而后一篇文檔缺失這個詞。后者的隱式關(guān)系傳遞是指同一隱含語義, 在文檔中因作者、文章題材等影響而會采取不同表達。比如一篇文章包含律師, 另外一篇包含訴訟或者法庭, 即使后一篇文檔通篇不包含律師這個詞, 但兩篇文章本質(zhì)上仍隱含轉(zhuǎn)移關(guān)系。本文采用隨機游走模型來對文檔的顯式和隱式傳遞關(guān)系進行建模, 如圖4(a)所示, 分析1→4, 顯示關(guān)系傳遞為1→2→4, 隱式關(guān)系傳遞為1→1→3→4→4和1→1→3→3→4?？梢钥闯? 隨機游走模型能很好地融合顯式和隱式文檔關(guān)系。

文獻[5]定義Influence (d,d|) , 即兩篇文檔和基于詞的跳轉(zhuǎn)概率, 通過Influence將轉(zhuǎn)移依據(jù)在兩篇文檔轉(zhuǎn)移中的影響進行量化。為了計算Influence (d,d|), 文獻[5]的定義如下:

2.3.4 鏈生成算法

兩篇文檔發(fā)生邏輯轉(zhuǎn)移, 相似性是必要條件, 充分條件是文檔間必須有差異, 過于相似或者過于不相似都將導(dǎo)致文檔間相似和差異的比例不均衡, 直接影響文檔間轉(zhuǎn)移的質(zhì)量。過于相似文檔間發(fā)生轉(zhuǎn)移類似文本主題聚類, 而聚類并不能反映其邏輯意義。過于不相似文檔間發(fā)生轉(zhuǎn)移類似隨機選取文檔進行轉(zhuǎn)移, 得出的結(jié)果將因為噪音的影響而失真。因此本文將文檔的主題相似作為判定轉(zhuǎn)移的條件(降低噪音), 之后通過差異部分具體量化轉(zhuǎn)移。這種策略將大幅度提高轉(zhuǎn)移結(jié)果的準(zhǔn)確性。新聞脈絡(luò)鏈由多個邏輯轉(zhuǎn)移構(gòu)成, 因此本算法通過計算文檔間主題相似度, 在此基礎(chǔ)上建立時序有向圖。如圖5(a)所示, 節(jié)點代表文檔, 邊的粗細(xì)是定義在主題空間的節(jié)點間正弦距離, 定義如下:

給定起點文檔和重點文檔, 即可根據(jù)邏輯性指標(biāo), 在時序圖中遍歷找到最佳脈絡(luò)圖, 并附加可解釋的轉(zhuǎn)移依據(jù)。

3 實驗設(shè)計

3.1 數(shù)據(jù)集

本實驗使用的數(shù)據(jù)集來自新浪網(wǎng)新聞專題搜索引擎, 通過抓取基于關(guān)鍵字MH370搜索返回的結(jié)果, 得到與馬航相關(guān)的新聞事件文檔集合。對新聞去重后, 對文檔集合的評論信息進行分析抓取, 形成最終的原始文檔集合, 具體描述見表1。

表1 原始數(shù)據(jù)集描述

3.2 時間評論聚類算法有效性驗證

通過對新聞-用戶評論數(shù)據(jù)進行K-means聚類分析, 將得到的結(jié)果與參照的人工編輯脈絡(luò)鏈進行對比, 對假設(shè)“某新聞是新聞事件發(fā)展轉(zhuǎn)折點的可能性大小正比于用戶對該新聞的關(guān)注行為強度”做可行性假設(shè)。剔除評論數(shù)低于1500的樣本點, 對原始數(shù)據(jù)進行聚類并得到多個時間簇, 時間簇所包含的時間點(以天為單位)即預(yù)測的新聞核心事件發(fā)生日期。對比人工編輯新聞鏈中新聞文檔發(fā)表時間發(fā)現(xiàn), 聚類得到的新聞轉(zhuǎn)折點發(fā)生時間與人工編輯的基本上吻合, 如圖6所示。

從3月8日到12月24日, 共有291個日期, 人工編輯提供17個標(biāo)準(zhǔn)日期答案, 聚類算法提供58個預(yù)測日期并命中其中16個, 唯一未命中的是5月9日, 但算法提供非常接近的預(yù)測日期5月10日, 因此預(yù)測錯誤可能由新聞的延遲導(dǎo)致。為定量描述聚類算法有效性, 定義召回率和準(zhǔn)確率的指標(biāo)如下:

通過計算可知, 未做預(yù)測之前召回率為1, 準(zhǔn)確率為5.84%; 經(jīng)過利用用戶評論信息聚類預(yù)測后, 召回率為94.12%, 基本上接近1, 準(zhǔn)確率為27.59%, 數(shù)據(jù)集合數(shù)量由2895變?yōu)?94, 縮小至原來的1/5。在保證不丟失新聞脈絡(luò)信息的同時, 大大減少了候選新聞數(shù)據(jù)集合的大小, 數(shù)據(jù)集的數(shù)量級也有大幅度降低, 提升了算法的可擴展性。

3.3 文檔建模效果分析

本節(jié)實驗數(shù)據(jù)集合為時間聚類方法得到的候選新聞集合。過濾掉詞頻出現(xiàn)小于10的低頻詞, 將實驗數(shù)據(jù)集轉(zhuǎn)換成為∈494×1010, 通過RPCA得到矩陣和, 預(yù)處理新聞集合的具體描述見表2。

表2 候選數(shù)據(jù)集描述

圖7描述的是源文檔0: 《馬航機場員工推搡中國記者大聲罵人豎中指》。利用隨機游走模型計算文檔0到另兩篇文檔{1,2}轉(zhuǎn)移中轉(zhuǎn)移依據(jù)(比如推搡)的影響, 可以看出0→1基于每一個詞轉(zhuǎn)移的概率都接近0, 結(jié)果是合理的。0→2基于每個詞轉(zhuǎn)移的概率之間差別較大, 選取其中幾個影響較大的詞: 推搡、員工、中國、道歉、馬航, 可以看出結(jié)果詞能較好地解釋兩篇文章轉(zhuǎn)移依據(jù)(顯式和隱式)。至于“記者”沒有出現(xiàn)在轉(zhuǎn)移依據(jù)中, 是因為“記者”在新聞文檔中雖然出現(xiàn)頻次高但意義小, 比如“據(jù)新華社記者報道”和“記者某某報道”, 因此在分詞預(yù)處理階段, 連同詞“報道”同時被過濾掉, 不參與后續(xù)轉(zhuǎn)移。

3.4 鏈評價

實驗設(shè)定=0.5,=0.8, 得出候選結(jié)果鏈條Coherence指標(biāo)最高為0.01008646。限于篇幅, 只列出“本文算法_結(jié)果2”及其序號5→序號6文檔的轉(zhuǎn)移依據(jù)“疑似(7.0305495×10-4), 殘骸(6.433595×10-4), 祈禱(3.8924068×10-4), 并非(3.8924022×10-4), 海面(3.1231903×10-4)”, 詞后的數(shù)字代表該詞在文檔間轉(zhuǎn)移的量化影響, 具體結(jié)果如圖8所示。

新聞事件邏輯脈絡(luò)鏈具有很強主觀特性, 比如鏈的可讀性、邏輯性以及可解釋性等, 無法類比搜索引擎或者推薦引擎評價的標(biāo)準(zhǔn)和客觀。ROUGH系列評價指標(biāo)是多文本總結(jié)領(lǐng)域常用指標(biāo), 但它較主觀, 不能反映真實的效果。鑒于本文構(gòu)建脈絡(luò)鏈的高主觀特性(后續(xù)實驗已證實, 不同用戶對同一脈絡(luò)結(jié)果打分相差很大), 本文通過用戶調(diào)查對生成的鏈進行評價。

脈絡(luò)鏈構(gòu)建的工程性質(zhì)使得相關(guān)算法雖然多, 但基本上不公開源碼, 因此論文方法不可再現(xiàn)。為避免因個人工程實現(xiàn)原因?qū)е聦Ρ人惴ㄐЧ档? 多角度比較算法效果, 本文算法與3個經(jīng)典的算法進行比較, 三者分別代表隨機性、主題聚類特性以及相關(guān)性。

1)隨機選取算法: 代表隨機性的思想, 隨機選取固定數(shù)目的新聞文檔作為脈絡(luò)鏈的候選文檔。

2)K-means聚類算法: 代表主題聚類特性, 在話題追蹤領(lǐng)域廣泛應(yīng)用。通過將文檔利用主題分量進行描述, 并基于這個主題向量空間進行K-means聚類, 得出聚類簇, 然后選擇最靠近類簇中心的文檔作為脈絡(luò)鏈的候選文檔。

3)最短路徑算法: 通過文檔的主題余弦相似度構(gòu)建一個圖, 權(quán)重為相似度, 尋找權(quán)重最大的路徑, 這是一個局部算法。

4)本文算法: 設(shè)定鏈的長度為6, 生成候選鏈。

本文對20名大學(xué)生進行雙盲問卷調(diào)查, 為其提供5個待評價脈絡(luò)鏈(圖8及附錄), 受調(diào)查者需回答兩個問題: 一個是知識量, 即讀完能夠?qū)κ录}絡(luò)的了解程度; 另一個是邏輯連貫性, 即展示脈絡(luò)鏈的邏輯連貫程度。二者分?jǐn)?shù)都是1~5之間的整數(shù)。為保證問卷調(diào)查的公平和客觀, 本文給出兩個待評估的鏈(未將脈絡(luò)鏈的可解釋加上, 若加上, 效果會更好), 其余3個算法各給出一條脈絡(luò)鏈, 并提供人工編輯的脈絡(luò)鏈供參考, 結(jié)果見表3。

表3 基于雙盲用戶調(diào)查的4種算法評估結(jié)果

4 結(jié)語

基于現(xiàn)有脈絡(luò)圖存在的三方面不足, 本文從詞覆蓋角度考慮邏輯脈絡(luò)鏈生成問題。在保證新聞脈絡(luò)基本無損的情況下, 利用新聞評論信息對數(shù)據(jù)集進行5倍壓縮。通過對文檔進行RPCA建模, 利用主題相似與稀疏差異的思想對文檔進行邏輯建模并量化, 形成可解釋且具較好邏輯連貫性的脈絡(luò)鏈, 解決了貪心相似或者主題聚類的脈絡(luò)局部化問題。本文方法簡單, 最終結(jié)果脈絡(luò)鏈取決于用戶給定的起始和終點文檔, 無須每次對整個集合進行迭代。

本文構(gòu)建脈絡(luò)鏈的最終評價標(biāo)準(zhǔn)是邏輯連貫性, 而邏輯連貫性取決于具體轉(zhuǎn)移詞的累加。選取哪些詞以及累加轉(zhuǎn)移如何計算, 都可由用戶個性化指定。如用戶喜歡邏輯跳躍緩慢的鏈, 就返回相鄰邏輯轉(zhuǎn)移增長相對平緩的鏈, 反之亦然。與此同時, 用戶也可對詞轉(zhuǎn)移的影響進行人為指定。比如用戶喜歡某些特定詞, 即可人為調(diào)高相應(yīng)詞的轉(zhuǎn)移影響, 結(jié)果鏈包含用戶喜歡的事件的轉(zhuǎn)移幾率就會提高。在為用戶生成邏輯連貫且可解釋的脈絡(luò)鏈的同時, 利用鏈可解釋性的展示可獲取用戶的反饋, 因此研究如何為用戶提供個性化的邏輯脈絡(luò)鏈?zhǔn)窍乱徊揭龅墓ぷ鳌Ｄ壳敖Y(jié)果鏈?zhǔn)菃捂? 反映事件的某一個側(cè)面, 將來可考慮構(gòu)建成脈絡(luò)圖, 使之包含的信息更加全面。因此, 如何融合多條鏈, 也是將來要考慮的工作。

[1]Lin Chen, Lin Chun, Li Jingxuan, et al. Generating event storylines from microblogs // Proceedings of the 21st ACM International Conference on Information and Knowledge Management. New York, 2012: 175–184

[2]Sakaki T, Okazaki M, Matsuo Y. Earthquake shakes twitter users: real-time event detection by social sensors // Proceedings of WWW 2010. Raleigh, 2010: 851–860

[3]Shamma D A, Kennedy L, Churchill E F. Peaks and persistence: modeling the shape of microblog conversations // Proceedings of CSCW 2011. Hang-zhou, 2011: 355–358

[4]Shi J, Malik J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888–905

[5]Shahaf D, Guestrin C. Connecting the dots between news articles // Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, 2010: 623–632

[6]Shahaf D, Guestrin C, Horvitz E. Trains of thought: Generating information maps // Proceedings of the 21st International Conference on World Wide Web. New York, 2012: 899–908

[7]Shahaf D, Yang J, Suen C, et al. Information cartography: creating zoomable, large-scale maps of information // Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, 2013: 1097–1105

[8]Shahaf D, Guestrin C, Horvitz E. Metro maps of science // Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, 2012: 1122–1130

[9]El-Arini K, Guestrin C. Beyond keyword search: discovering relevant scientific literature // Procee-dings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, 2011: 439–447

[10]Lewis D D, Knowles K A. Threading electronic mail: a preliminary study. Information Processing and Management, 1997, 33(2): 209–217

[11]Turner S R. The creative process: a computer model of storytelling and creativity. Hillsdale: Lawrence Erlbaum Associates Inc, 1994

[12]Niehaus J, Young R M. A computational model of inferencing in narrative // AAAI Spring Sympo-sium’09. Stanford, 2009: 75–82

[13]Kleinberg J. Bursty and hierarchical structure in streams. Data Mining & Knowledge Discovery, 2003, 7(4): 373–397

[14]Yang Y, Ault T, Pierce T, et al. Improving text categorization methods for event tracking // SIGIR 2000. Athens, 2000: 65–72

[15]Masand B, Linoff G, Waltz D. Classifying news stories using memory based reasoning // SIGIR. Copenhagen,1992: 59–65

[16]Allan J. Introduction to topic detection and tracking // Topic Detection and Tracking. Norwell, MA, 2002: 1–16

[17]Lavrenko V, Allan J, DeGuzman E, et al. Relevance models for topic detection and tracking // Proceedings of HLT 2002. San Francisco, 2002: 115–121

[18]Morinaga S, Yamanishi K. Tracking dynamics of topic trends using a finite mixture model // Proceedings of SIGKDD 2004. Seattle, 2004: 811–816

[19]Kumar R, Mahadevan U, Sivakumar D. A graph-theoretic approach to extract storylines from search results // Proceedings of SIGKDD 2004. Seattle, 2004: 216–225

[20]Yih W, Goodman J, Vanderwende L, et al. Multi-document summarization by maximizing informative content-words // The 20th International Joint Con-ference on Artificial Intelligence. Hyderabad, 2007: 1776–1782

[21]Yan R, Wan X, Otterbacher J, et al. Evolutionary timeline summarization: a balanced optimization framework via iterative substitution // Proceedings of SIGIR. New York, 2011: 745–754

[22]Yan Rui, Jiang Han, Lapata M, et al. i, poet: automatic Chinese poetry composition through a generative summarization framework under cons-trained optimization // Proceedings of IJCAI 2013. Beijing, 2013: 2197–2203

[23]Wan Xiaojun, Zhang Jianmin. CTSUM: extracting more certain summaries for news articles // Procee-dings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval. New York, 2014: 787–796

[24]Wei F, Li W, Lu Q, et al. Query-sensitive mutual reinforcement chain and its application in query-oriented multi-document summarization // Procee-dings of SIGIR 2008. New York, 2008: 283–290

[25]Li J, Li L, Li T. MSSF: a multi-document summarization framework based on submodularity // Proceedings of SIGIR 2011. Beijing, 2011: 1247–1248

[26]Wang D, Li T, Zhu S, et al. Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization // Proceedings of SIGIR 2008. New York, 2008: 307–314

[27]Lee D, Seung H. Algorithms for non-negative matrix factorization // Advances in neural information processing systems, NIPS 2001. Vancouver, 2001: 556–562

[28]Mishne G, Glance N. Leave a reply: an analysis of weblog comments // Third Annual Workshop on the Weblogging Ecosystem. Edinburgh, 2006: 1–8

[29]Mcqueen J. Some methods for classification and analysis of multivariate observations // Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, 1967: 281–297

[30]Bai B, Weston J, Grangier D, et al. Supervised semantic indexing. Lecture Notes in Computer Science, 2009, 5478: 761–765

[31]Blei D M, Ng A Y, Jordan M I. Latent dirichlet allocation. J Mach Learn Res, 2003, 3: 993–1022

[32]Candès E J, Li X, Ma Y, et al. Robust principal component analysis?. Journal of the Acm, 2011, 58(3): 219–226

Constructing a News Story Chain from Word Coverage Perspective

FU Jiabing, DONG Shoubin?

Guangdong key Laboratory of Communications, South China University of Technology, Guangzhou 510640; ? Corresponding author, E-mail: sbdong@scut.edu.cn

Current studies merely focus on a story chain’s similarity of topic relationship and importance of documents, whilst almost ignoring its logical coherency and explainability. Along with algorithm complexity brought about by exponential growth in sets of news data, a story chain from word coverage perspective is constructed, taking advantage of the story comments to position the turning point of each event. The ideas of similarity of topic relationship and sparsity differences as well as RPCA approach are used to conduct logical modeling for the documents. Random walk and graph traversals are adopted to quantify and construct an explainable and logically coherent story chain. The double-blind experiment reveals that proposed method outperforms other algorithms.

story chain; word coverage; explainable; RPCA; random walk

10.13209/j.0479-8023.2016.018

TP391

2015-06-19;

2015-08-17; 網(wǎng)絡(luò)出版日期: 2015-09-30

廣東省前沿與關(guān)鍵技術(shù)創(chuàng)新專項(2014B010112006)和廣東省產(chǎn)學(xué)研省部合作專項資金(2013B090500087)資助