基于CRF模型的短文本信息流話題提取

王宗堯，劉金嶺，崔俊峰，王 敏

(1. 淮陰工學(xué)院 管理工程學(xué)院，江蘇 淮安 223003；2. 淮陰工學(xué)院 計(jì)算機(jī)與軟件學(xué)院， 江蘇 淮安 223003；3. 淮陰工學(xué)院 數(shù)理學(xué)院，江蘇 淮安 223003；4. 淮陰工學(xué)院 圖書(shū)館，江蘇 淮安 223003)

?

基于CRF模型的短文本信息流話題提取

王宗堯1，劉金嶺2，崔俊峰3，王 敏4

(1. 淮陰工學(xué)院 管理工程學(xué)院，江蘇 淮安 223003；2. 淮陰工學(xué)院 計(jì)算機(jī)與軟件學(xué)院， 江蘇 淮安 223003；3. 淮陰工學(xué)院 數(shù)理學(xué)院，江蘇 淮安 223003；4. 淮陰工學(xué)院 圖書(shū)館，江蘇 淮安 223003)

為更有效地在中文短文本信息流中進(jìn)行話題提取，給出了一種基于CRF模型的話題提取方法。根據(jù)短文本信息流的特點(diǎn)，定義了短文本信息流中關(guān)鍵詞語(yǔ)相似度。充分利用上下文信息對(duì)特征信息進(jìn)行全局歸一化的處理，進(jìn)一步得到全局的最優(yōu)值。在真實(shí)的短信文本信息集上將此方法與決策樹(shù)方法進(jìn)行比較，取得了較明顯的優(yōu)勢(shì)。

短文本；信息流；話題提取；CRF模型

0 引言

隨著通信技術(shù)的迅猛發(fā)展，短文本信息流以TB數(shù)據(jù)量級(jí)增長(zhǎng)，而短文本信息流中又富含一些人民群眾最關(guān)心的社會(huì)問(wèn)題，如教育中存在的問(wèn)題、股市和樓市問(wèn)題、醫(yī)療和社保問(wèn)題、勞動(dòng)就業(yè)問(wèn)題等等，熱點(diǎn)話題發(fā)現(xiàn)對(duì)及時(shí)了解社情民意、預(yù)防較大的社會(huì)群體性事件的發(fā)生、構(gòu)建和諧社會(huì)具有重要意義。

短文本信息流含有的話題可視為短文本的集合，在集合中的所有短文本都表達(dá)特定的主題，短文本信息流話題提取是根據(jù)話題以及信息間的對(duì)話關(guān)系，利用表達(dá)話題的關(guān)鍵詞集合將相關(guān)的短文本分撿到每一個(gè)話題中。本文針對(duì)短文本信息流的開(kāi)放性，形式變化的多樣性以及網(wǎng)絡(luò)用語(yǔ)、縮語(yǔ)、口語(yǔ)化等特點(diǎn)，利用CRF全新概率模型進(jìn)行話題提取，強(qiáng)化了話題提取中短文本長(zhǎng)距離依賴(lài)性和交疊性特征的能力，提高了話題提取算法的性能。

黃九鳴等[1]利用接收到短文本的時(shí)間距離某固定時(shí)間的毫秒數(shù)(稱(chēng)為時(shí)間點(diǎn))為橫軸，短文本信息條數(shù)為縱軸，實(shí)線為單位時(shí)間產(chǎn)生的信息條數(shù)(即信息產(chǎn)生的速率)，該方法是利用判斷一元函數(shù)極值點(diǎn)的性質(zhì)來(lái)確定話題邊界。問(wèn)題是假設(shè)數(shù)學(xué)模型條件都滿(mǎn)足，但根據(jù)短文本信息流的交錯(cuò)性特點(diǎn)，即使一個(gè)很短時(shí)間的短文本信息流中也可能包含多個(gè)話題，因此該方法檢測(cè)多話題并存的情況是困難的。程俊霞等[2]提出了一種基于SVM過(guò)濾的檢測(cè)方法，該方法在聚類(lèi)前將微博文本特征抽象成用于輸入向量機(jī)的向量，對(duì)微博文本進(jìn)行過(guò)濾，提高了計(jì)算效率，但該算法如果不考慮語(yǔ)句數(shù)特征，則降低了有效微博的準(zhǔn)確率和召回率。張磊等[3]利用決策樹(shù)方法來(lái)處理流量分類(lèi)問(wèn)題，該方法利用訓(xùn)練數(shù)據(jù)集中的信息熵來(lái)構(gòu)建提取模型，并通過(guò)對(duì)提取模型的簡(jiǎn)單查找來(lái)完成未知網(wǎng)絡(luò)流樣本的提取。目前，基于條件隨機(jī)場(chǎng)(Conditional Random Fields，CRF)較新概率模型，在中文分詞、序列分塊、命名實(shí)體識(shí)別等自然語(yǔ)言處理任務(wù)中都有很好的應(yīng)用[4]，其主要優(yōu)勢(shì)是可以對(duì)所有短文本集的特征信息進(jìn)行全局歸一化，進(jìn)一步可以得到全局的最優(yōu)值，它具有表達(dá)話題中短文本長(zhǎng)距離依賴(lài)性和交疊性特征的能力，能方便地在模型中包含領(lǐng)域知識(shí)。

1 基于CRF模型的短文本信息流提取方法

1.1 短文本信息流的向量集表示

假設(shè)短文本信息流ST_Fv的歷史數(shù)據(jù)都利用劉金嶺提出[5]的方法進(jìn)行了預(yù)處理，將ST_Fv表示成特征向量集的形式：

ST_FV={STi|wi1,hi1;wi2,hi2;…;win,hin}

(1)

其中：wik表示短文本STi的關(guān)鍵詞，,hik表示關(guān)鍵詞wik關(guān)于短文本STi的權(quán)重(k=1,2,…,n)

1.2 短文本信息流的CRF模型

假設(shè)X={x1,x2,…,xn}表示ST_FV的一個(gè)待測(cè)短文本的特征，Y={y1,y2,…,ys}，根據(jù)CRF的基本理論，觀察序列X對(duì)應(yīng)參數(shù)集合λ={λ1，λ2，…，λt}的指定狀態(tài)Y的條件概率：

(2)

其中：fj為特征函數(shù)，λj為特征函數(shù)的權(quán)值，可以通過(guò)訓(xùn)練得到；Z(X)為歸一化因子。

(3)

CRF模型通過(guò)特征函數(shù)的定義來(lái)描述觀察值與狀態(tài)值之間的對(duì)應(yīng)關(guān)系和狀態(tài)值之間的轉(zhuǎn)移關(guān)系，提取出它們的特征，特征函數(shù)定義得合適與否將直接影響CRF的標(biāo)注性能。

CRF模型計(jì)算ST_FV中具有最大概率的狀態(tài)參數(shù)序列λ作為結(jié)果。即對(duì)于短文本ST_FV，為了標(biāo)記其位于i和i-1位置時(shí)的參數(shù)值，以確定ST_FV是某一話題的結(jié)束還是某一話題的延續(xù)。對(duì)于(2)式定義的條件概率和參數(shù)序列λ，需要在參數(shù)估計(jì)中搜索到概率最大的最優(yōu)值Y*，使得：

(4)

1.3 短文本信息流的CRF模型話題提取算法

1.3.1 算法原理

采用L-BFGS算法，任取ST∈ST_FV作初始觀察序列，并將ST_FV-{ST}作為初始狀態(tài)序列，利用CRF模型得到話題初始輸出類(lèi)別，然后把剩余的ST_FV中待檢測(cè)文本作為觀察序列，通過(guò)CRF模型來(lái)計(jì)算觀察序列中的短文本和輸出類(lèi)別中短文本之間的概率值，并根據(jù)其方差值給出短文本與話題類(lèi)別的區(qū)分程度。其識(shí)別過(guò)程如圖1所示。

圖1 短文本信息流話題提取流程

利用CRF模型進(jìn)行短文本信息流話題提取時(shí)，先是對(duì)短文本信息流的短文本進(jìn)行預(yù)處理，然后將CRF預(yù)測(cè)序列標(biāo)注的特點(diǎn)應(yīng)用到短文本信息流的話題提取中，將短文本的每個(gè)關(guān)鍵詞、話題類(lèi)別和類(lèi)別概率的標(biāo)注分別作為第1列、第2列和第3列，如圖2所示。

圖2 短信文本話題初始標(biāo)注示例

1.3.2 算法步驟

假設(shè)短文本信息流向量集是按時(shí)間順序的短文本信息向量集，話題提取的CRF算法如下。

輸入 短文本信息流向量集ST_Fv，區(qū)分度閾值θ

輸出 話題集合T_S={C1,C2,C3,L}

step1 對(duì)任意ST∈ST_Fv，并假設(shè)是按時(shí)間順序排列的的短文本信息向量集。將ST和ST_FV-{ST}分別作為CRF模型的觀察序列和狀態(tài)序列來(lái)計(jì)算ST和ST_Fv-{ST}相關(guān)性概率值，得到概率序列{p1,p2,p3,…}。

step2 設(shè)C1={最大概率值所對(duì)應(yīng)的短文本}∪{輸入觀察序列中的短文本}，C2={最小概率值對(duì)應(yīng)的短文本}，C1,C2?C。

step3 將ST_Fv=ST_Fv-(C1∪C2)作為輸入觀察序列，利用CRF模型得到ST_Fv隸屬于C1的概率值和ST_Fv隸屬C2的概率值。

step4WhileST_Fv≠?

step4-1 對(duì)任意ST∈ST_Fv，ST=ST_Fv-{ST}，求出ST與輸出類(lèi)別序列的各個(gè)概率值，并求出相應(yīng)方差序列{v1,v2,…,vk,…}。

step4-2 對(duì)于給定閾值θ，設(shè)min{v1,v2,…,vk,…}對(duì)應(yīng)的短文本STmin的所有概率值集合P_min。

step4-2-1Whilemin(P_min)<θ

step4-2-2ifSTmin∈ST_Fv

step4-2-3 C3={STmin}andST=ST_Fv-C3

step4-2-4else

step4-2-5 考慮方差值第二小的那篇短文本

step4-2-6endif

step4-2-7EndW

step4-3 將max{v1,v2,…,vk,…}所對(duì)應(yīng)的短文本歸并到最大概率所對(duì)應(yīng)的話題中

step5EndW

step6 輸出T_S

2 實(shí)驗(yàn)結(jié)果及分析

區(qū)分度閾值越大，類(lèi)別間的區(qū)別越不明顯，實(shí)驗(yàn)取。為了驗(yàn)證相關(guān)結(jié)論，從江蘇某短信運(yùn)營(yíng)商截取2012年2月1日零點(diǎn)整到4月30日24點(diǎn)整這個(gè)時(shí)間段的近9萬(wàn)4千條手機(jī)短信文本集合進(jìn)行了人工標(biāo)注。抽取出了如載有化學(xué)品的船在江陰段沉船、江蘇沿江部分城市出現(xiàn)市民搶購(gòu)礦泉水、元宵節(jié)祝福等142個(gè)熱點(diǎn)話題。為了問(wèn)題的簡(jiǎn)化，實(shí)驗(yàn)前根據(jù)文獻(xiàn)[5]提前將樣本集通過(guò)分詞、特征提取和降維等預(yù)處理為短信文本向量集，得到18000條的短信文本向量集。實(shí)驗(yàn)編碼使用C#語(yǔ)言在VisualStutio2010 平臺(tái)上實(shí)現(xiàn)，分詞采用ICTCLAS，關(guān)鍵詞提取采用文檔頻率法，CRF方法采用CRF++結(jié)合快速L-BFGS訓(xùn)練方法。

2.1 評(píng)價(jià)參數(shù)

抽取出的話題j和人工標(biāo)注的真實(shí)會(huì)話i的準(zhǔn)確率P、召回率R和F度量值，其公式如下：

(5)

(6)

(7)

2.2 決策樹(shù)方法與CRF方法比較

為了比較CRF模型與決策樹(shù)方法的優(yōu)劣，將張磊等[3]給出的決策樹(shù)流量提取方法與CRF方法進(jìn)行比較。分別用決策樹(shù)和CRF方法進(jìn)行話題提取，并進(jìn)行準(zhǔn)確率、召回率和F度量值比較，結(jié)果如圖3所示。

圖3 決策樹(shù)和CRF話題提取實(shí)驗(yàn)結(jié)果比較

從圖3的實(shí)驗(yàn)結(jié)果可以看出，利用CRF進(jìn)行話題提取的整體性能要好于決策樹(shù)方法，這是因?yàn)闆Q策樹(shù)模型進(jìn)行話題提取僅考慮當(dāng)前短文本信息，不考慮前一個(gè)短文本所屬的類(lèi)別，同時(shí)決策樹(shù)算法也存在計(jì)算效率低下、多值偏向等很多不足之處，而CRF模型在標(biāo)注時(shí)考慮了短文本信息流的前一個(gè)短文本的標(biāo)注對(duì)后一個(gè)短文本的影響。

3 結(jié)論

短文本信息流的話題研究是目前研究的熱點(diǎn)之一?，F(xiàn)有的會(huì)話提取技術(shù)主要對(duì)基于文本相似度聚類(lèi)方法的改進(jìn)，不能很好地反應(yīng)短文本信息流特征的稀疏性、奇異性和動(dòng)態(tài)性。使用CRF建立短文本信息流抽取統(tǒng)計(jì)模型，再利用了CRF模型能夠結(jié)合多種特征融合能力比較強(qiáng)和避免標(biāo)記偏置等優(yōu)勢(shì)，其性能更好。但CRF模型的特征選擇和優(yōu)化是影響結(jié)果的關(guān)鍵因素，特征選擇問(wèn)題的好與壞，直接決定了系統(tǒng)性能的高低。通過(guò)與決策樹(shù)模型對(duì)短文本信息流的話題提取比較，CRF模型方法要好于決策樹(shù)方法。

[1] 黃九鳴,吳泉源,劉春陽(yáng),等.短文本信息流的無(wú)監(jiān)督會(huì)話抽取技術(shù)[J].軟件學(xué)報(bào),2012(4): 735-747.

[2] 程俊霞,李芝棠,鄒明光,等.基于SVM 過(guò)濾的微博新聞話題檢測(cè)方法[J].通信學(xué)報(bào),2013(Z2): 74-78.

[3] 張磊,李亞男,王斌,等.網(wǎng)頁(yè)搜索引擎查詢(xún)?nèi)罩镜腟ession劃分研究[J].中文信息學(xué)報(bào),2009(2):54-61.

[4] Charles Sutton, Andrew McCallum, Khashayar Rohanimanesh. Dynamic Conditional Random Fields: Factorized Probabilistic Models for Labeling and Segmenting Sequence Data[J].The Journal of Machine Learning Research,2007(8): 693-723.

[5] 劉金嶺.基于降維的短信文本語(yǔ)義分類(lèi)及主題提取[J].計(jì)算機(jī)工程與應(yīng)用,2010(23):159-161.

(責(zé)任編輯：孫文彬)

The Short Text Information Flow Topic Extraction Based on CRF Model

WANG Zong-yao1, LIU Jin-ling2, CUI Jun-feng3, WANG Min4

(1.Faculty of Management Engineering, Huaiyin Institute of Technology, Huai'an Jiangsu 223003, China; 2.Faculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huai'an Jiangsu 223003,China; 3.Faculty of Mathematics and Physics, Huaiyin Institute of Technology, Huai'an Jiangsu 223003, China; 4.Library, Huaiyin Institute of Technology, Huai'an Jiangsu 223003, China)

A topic extraction method based on CRF model is presented in order to extract topic from Chinese short text information flow more effectively. According to the characteristics of short text information flow, the similarity of key words in short text information flow is defined. Global normalization of the feature information is processed through context information, and then the global optimal value is obtained. CRF method provides significant benefits if to compare the CRF method with decision tree method based on the real short text information set.

short text; the flow of information; topic extraction; CRF model

2016-08-07

江蘇高校哲學(xué)社會(huì)科學(xué)研究項(xiàng)目(2015SJD702)；淮陰工學(xué)院科研基金項(xiàng)目(HGC1422)。

王宗堯(1980-)，男，江蘇淮安人，講師，碩士，主要從事信息管理與統(tǒng)計(jì)學(xué)研究。

TP391.1

A

1009-7961(2016)05-0006-04