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

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

?

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

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

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

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

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

0 引言

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

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

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

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的一個待測短文本的特征，Y={y1,y2,…,ys}，根據(jù)CRF的基本理論，觀察序列X對應(yīng)參數(shù)集合λ={λ1，λ2，…，λt}的指定狀態(tài)Y的條件概率：

(2)

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

(3)

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

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

(4)

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

1.3.1 算法原理

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

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

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

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

1.3.2 算法步驟

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

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

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

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

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

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

step4WhileST_Fv≠?

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

step4-2 對于給定閾值θ，設(shè)min{v1,v2,…,vk,…}對應(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,…}所對應(yīng)的短文本歸并到最大概率所對應(yīng)的話題中

step5EndW

step6 輸出T_S

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

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

2.1 評價參數(shù)

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

(5)

(6)

(7)

2.2 決策樹方法與CRF方法比較

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

圖3 決策樹和CRF話題提取實驗結(jié)果比較

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

3 結(jié)論

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

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

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

[3] 張磊,李亞男,王斌,等.網(wǎng)頁搜索引擎查詢?nèi)罩镜腟ession劃分研究[J].中文信息學(xué)報,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] 劉金嶺.基于降維的短信文本語義分類及主題提取[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é)社會科學(xué)研究項目(2015SJD702)；淮陰工學(xué)院科研基金項目(HGC1422)。

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

TP391.1

A

1009-7961(2016)05-0006-04