劉建波

(山東財(cái)政學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)中心，山東 濟(jì)南 250014)

Web 2.0概念的出現(xiàn)使互聯(lián)網(wǎng)新媒體的發(fā)展進(jìn)入了新階段，互聯(lián)網(wǎng)上出現(xiàn)了大量帶有情感色彩的主觀性短文本，呈現(xiàn)的形式也多樣化［1-2］。通過網(wǎng)絡(luò)短文本信息，人們記錄自己的日常生活及事務(wù)，抒發(fā)感情、釋放情緒。如今的網(wǎng)絡(luò)已成為史上最大的情感倉庫。利用這個(gè)情感倉庫，并從中挖掘有價(jià)值的信息，識別出群體的輿情趨向及演化規(guī)律，可以更好地分析人們的情感以及社會輿情熱點(diǎn)，具有較大的研究和應(yīng)用價(jià)值，對情感話題的檢測與跟蹤、網(wǎng)絡(luò)用戶群體極端行為方向的挖掘與思想異常檢測等方面有重要的價(jià)值。

1 相關(guān)研究

當(dāng)前有關(guān)情感分析的研究成果主要集中在英文語種，由于中文語言在詞法和句法表達(dá)上有別于其他語言，使得許多已有方法并不能直接用于中文處理，因此基于漢語情感詞組挖掘算法值得深入研究［3-5］。

TURNEY等提出的基于語義方法的情感分類研究已經(jīng)具有了初步的應(yīng)用價(jià)值［6］;WIEBE等專注于識別文本中能夠表達(dá)主觀情感的特征，為客戶情感分析研究提供了方法;除此之外，還有一些學(xué)者采用由普林斯頓大學(xué)開發(fā)的英文詞網(wǎng)(WordNet)進(jìn)行英文語義方法的情感分析，也取得了較好的分析結(jié)果。國內(nèi)相關(guān)研究也取得了一定的成果，復(fù)旦大學(xué)金峰等人提出的基于傾向性文本過濾系統(tǒng)，能夠?qū)哂嘘P(guān)于某個(gè)主題的特定傾向的文本進(jìn)行過濾;FEI等提出基于短語模式的分類方法，利用機(jī)器學(xué)習(xí)方法，針對sport.yahoo.com英文體育評論開展了情感分析研究［7］。筆者提出一種面向情感分析的網(wǎng)絡(luò)短文本意義串算法，基于改進(jìn)FP-樹最大頻繁模式發(fā)現(xiàn)算法得到關(guān)鍵詞匯集合后，結(jié)合詞語局部性原理對詞匯集合進(jìn)一步進(jìn)行有意義字串挖掘，最后針對挖掘的意義串進(jìn)行情感分析［8-11］。

2 基于改進(jìn)FP－樹最大頻繁模式挖掘算法

針對網(wǎng)絡(luò)中文短文本的特點(diǎn)，筆者提出一種基于改進(jìn)的FP-樹結(jié)構(gòu)來完成頻繁模式的挖掘，改進(jìn)后的FP-樹與傳統(tǒng)FP-樹相比主要有以下特點(diǎn):

(1)傳統(tǒng)FP-樹是雙向的，而改進(jìn)的FP-樹是單向的，不存在從樹根到樹葉的路徑，改進(jìn)的FP-樹包含較少的指針，節(jié)省大量的存儲空間。

(2)改進(jìn)FP-樹的節(jié)點(diǎn)用項(xiàng)的序號標(biāo)記其支持?jǐn)?shù)，項(xiàng)的序號按支持度由大到小排序確定。每個(gè)節(jié)點(diǎn)包含 4個(gè)域:item、count、ahead和 next，其中item為結(jié)點(diǎn)名稱，count為項(xiàng)目計(jì)數(shù)，ahead為指向最左子女節(jié)點(diǎn)或父節(jié)點(diǎn)的指針，next為指向兄弟節(jié)點(diǎn)或節(jié)點(diǎn)鏈中下一節(jié)點(diǎn)的指針。

2.1 算法概述

基于改進(jìn)FP-樹最大頻繁模式挖掘算法如下:

輸入FP-樹、最小支持度閾值Min_sup;輸出最大頻繁模式集合MFS;其操作步驟為:

2.2 算法實(shí)現(xiàn)

結(jié)合以上提出的基于改進(jìn)FP-樹，對表1中的事物集進(jìn)行最大頻繁模式挖掘。

表1中出現(xiàn)頻次大于3的各個(gè)詞語按照支持度計(jì)數(shù)分別為 5、5、4、4、4、4;根據(jù)支持度降序排列可以得到其對應(yīng)的序號分別為 1、2、3、4、5、6，基于以上內(nèi)容可以構(gòu)造改進(jìn)的FP-樹，如圖1所示。

基于改進(jìn)FP-樹最大頻繁模式挖掘算法過程如下:

表1 短文本事物集

圖1 頻繁模式FP-樹

最后根據(jù)序號轉(zhuǎn)換表可得到最大頻繁項(xiàng)目集為 MFS={{山東，濟(jì)南}，{山東，東}，{綠色，動車，大，濟(jì)南，東}}。從得到的頻繁模式可以看出，按照以上算法得到的短文本最大化重復(fù)串在漢語語法中不一定是有意義字串，如“東”和“綠色，動車，大，濟(jì)南，東”，而“山東濟(jì)南”才有實(shí)際意義。因此，還要基于短文本的最大化重復(fù)串挖掘有意義字串。

3 基于局部性原理進(jìn)行有意義串挖掘

由于中文語法與西文語法不同，挖掘出來的詞有一定的局部性。所謂詞語局部性，有兩層含義:時(shí)間局部性和空間局部性。時(shí)間局部性是指不同的時(shí)間段出現(xiàn)的有意義詞語不同，如新聞熱點(diǎn)出現(xiàn)后不一定在短時(shí)間內(nèi)成為人們談?wù)摰慕裹c(diǎn);空間局部性是指在不同領(lǐng)域的文檔中出現(xiàn)的有意義詞語可能不同，如大學(xué)校園BBS與財(cái)經(jīng)專業(yè)BBS中挖掘出來的有參考價(jià)值的詞語不同。因此，筆者結(jié)合局部性度量策略的約束條件從以下幾方面對重復(fù)串進(jìn)行處理:多中心點(diǎn)分簇、抗噪音處理和頻次歸一化約束。

3.1 對文本庫分簇，形成多中心點(diǎn)

字符串在短文本庫各出現(xiàn)位置按照一定的策略劃分為若干簇，對每個(gè)簇分別計(jì)算中心點(diǎn)，度量字符串在該簇內(nèi)分布的局部性，得出字符串在整個(gè)文本庫中總局部性度量。

3.2 有效處理噪音

在文本中，某個(gè)詞如果在圖1所示的3個(gè)部分出現(xiàn)，第2和第3處出現(xiàn)的頻次遠(yuǎn)高于第1處，因此可以將第1處稱作孤立點(diǎn)或噪音。噪音對于文本的分簇影響較大，計(jì)算方差過程中帶有噪音的方差較大，偏離實(shí)際。因此在算法中要有效處理噪音。

3.3 詞語出現(xiàn)頻次歸一化約束

中文詞語的局部性與其出現(xiàn)的頻次(密度)有關(guān)系，密度越大，其局部性越高，但是也不能單一比較詞語在文本中的某個(gè)位置的密度或頻次，如在圖2和圖3中，字符串A在3位置的密度高于字符串B在2的位置，不能說明字符串A的局部性高于B，要對沒有噪音的短文本中所有出現(xiàn)重復(fù)串的密度作歸一化處理，計(jì)算其平均局部性，即各個(gè)區(qū)域局部性的平均值，保證詞語局部性的計(jì)算不局限于某個(gè)特定的區(qū)域，而是各區(qū)域局部性的綜合。

圖2 字符串A出現(xiàn)位置

圖3 字符串B出現(xiàn)位置

3.4 局部性度量算法

若字符串S在短文本中出現(xiàn)n次，各出現(xiàn)位置分別為 P1，P2，…，Pn，字符串的局部性度量算法主要通過以下幾個(gè)過程完成。

(1)計(jì)算參考距離。用參考距離Distance確定位置點(diǎn)的簇類，使用字符串在文本中各相鄰位置之間距離的平均值作為位置點(diǎn)聚類的參考距離，則字符串S的參考距離可由式(1)計(jì)算:

(2)位置點(diǎn)聚類。對于重復(fù)串出現(xiàn)的所有位置點(diǎn)按照參考距離進(jìn)行聚類，基本算法如下:

初始化當(dāng)前聚類C={P1};

對于1＜i＜n+1，循環(huán)計(jì)算 Pi-Pi-1，如果Pi-Pi-1＞Distance，將 C加入 R，清空 C;否則將Pi加入C。

通過以上算法，結(jié)合式(1)求出的參考距離，對所有最大化重復(fù)串位置點(diǎn)分簇，使得同一簇內(nèi)距離較小，而不同簇間的距離較大，從而得到較好的歸一化結(jié)果。

(3)字符串的整體局部性。字符串的整體局部性可以通過字符串在各簇局部性的平均值來度量，若根據(jù)各字符串出現(xiàn)的位置點(diǎn)最終劃分為k個(gè)簇{C1，C2，…，Ck}，字符串在每個(gè)簇 Ci的位置方差為Vi，其局部性的平均值為:

(4)字符串意義指數(shù)度量。通過后綴數(shù)組的頻繁模式發(fā)現(xiàn)算法得到最大重復(fù)串集合R={S1，S2，…，Sn}，并分別計(jì)算字符串在整個(gè)短文本中的局部性，利用式(3)度量各個(gè)字符串的有意義指數(shù):

其中，λ為指數(shù)影響因子，其設(shè)置為了影響MI的計(jì)算數(shù)值，可以通過實(shí)驗(yàn)數(shù)據(jù)來分析其取值變化對指數(shù)計(jì)算的影響，最后確定針對不同詞語密度的最佳數(shù)值，提高短文本聚類分析的數(shù)據(jù)結(jié)果的準(zhǔn)確率。

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

4.1 指數(shù)影響因子的確定

在我校學(xué)生論壇系統(tǒng)中，帖子以文本文件格式存放，其格式與短文本的特點(diǎn)一致。因此，選取某一段時(shí)間數(shù)據(jù)做實(shí)證分析。通過Visual C++實(shí)現(xiàn)以上算法，求出頻次大于180的重復(fù)串，λ的取值從0變化到1，步長為0.05，對0～1的每一個(gè)λ值，按照式(3)計(jì)算各字符串的MI值并排序，分別選取排序靠前的200個(gè)、400個(gè)、800個(gè)候選有意義串，統(tǒng)計(jì)其準(zhǔn)確率如圖4所示。

從圖4可以看出，λ的最佳取值隨著候選有意義串的數(shù)量增大而增大。當(dāng)候選有意義串?dāng)?shù)量為200時(shí)，λ的最佳取值為0.3;當(dāng)候選有意義串?dāng)?shù)量為400時(shí)，λ的最佳取值為0.4;當(dāng)候選有意義串的數(shù)量超過800時(shí)，λ的最佳取值為0.5。

圖4 影響因子閾值及其精確度

4.2 基于有意義串挖掘結(jié)果的情感分析

確定不同數(shù)量字符串對應(yīng)最佳影響因子閾值之后，可以對論壇中的短文本數(shù)據(jù)重新進(jìn)行聚類分析?？s小時(shí)間范圍，試驗(yàn)中得到2010年上半年論壇文本數(shù)據(jù)的挖掘結(jié)果，如表2所示，在表2中列出了出現(xiàn)頻次排名比較靠前的有意義字串，如“山東財(cái)經(jīng)大學(xué)”排在第一，說明學(xué)校用戶對我校整合其他院校以及更改校名事件比較敏感，以及合校之前新校長的上任比較關(guān)心;“非誠勿擾”單身交友節(jié)目是適齡大學(xué)生們的情感聚集;“酒后駕車”、“富二代”是社會的關(guān)注熱點(diǎn)。

表2 字符串聚類結(jié)果

5 結(jié)論

通過以上的分析，筆者提出的面向情感分析的短文本意義串發(fā)現(xiàn)及分析算法，實(shí)現(xiàn)簡潔，執(zhí)行效率高。但是，相比傳統(tǒng)的英文文本分類，中文文本情感分析有先天的困難和挑戰(zhàn)，主要表現(xiàn)在漢語語言表達(dá)方式的多樣化，算法需要考慮更多的影響因子以及對應(yīng)的閾值，以便提高其有效性。

［1］周立柱，賀宇凱.情感分析研究綜述［J］.計(jì)算機(jī)應(yīng)用研究，2008，28(11):2726-2727.

［2］胡佳妮，郭軍，鄧偉洪.基于短文本的獨(dú)立語義特征抽取算法［J］.通信學(xué)報(bào)，2007，28(12):121-122.

［3］蔡月紅，朱倩，孫萍.基于屬性選擇的半監(jiān)督短文本分類算法［J］.計(jì)算機(jī)應(yīng)用，2010，30(4):1015-1017.

［4］龔才春.短文本語言計(jì)算的關(guān)鍵技術(shù)研究［D］.北京:中國科學(xué)院計(jì)算技術(shù)研究所，2008.

［5］柴春梅.互聯(lián)網(wǎng)短文本信息分類關(guān)鍵技術(shù)研究［D］.上海:上海交通大學(xué)圖書館，2009.

［6］TURNEY P D.Thumbs up or thumbs down?semantic orientation applied to unsupervised classification of reviews［C］//Proceeding of Association for Computational Linguistics 40th Anniversary Meeting.［S.l.］:［s.n.］，2002:417-424.

［7］FEI Z C ，LIU J，WU G F.Sentiment classification using phrase patterns［C］//Proceedings of the Fourth International Conference on Computer and Information Technology(CIT'04).［S.l.］:［s.n.］，2004:2-5.

［8］林森媚，謝伙生，白清源.基于合并FP-樹的頻繁模式挖掘算法［J］.廣西師范大學(xué)學(xué)報(bào)，2009，25(4):254-255.

［9］秦亮曦，史忠植.SFP-Max:基于排序FP-樹的最大頻繁模式挖掘算法［J］.計(jì)算機(jī)研究與發(fā)展，2005，42(2):217-223.

［10］楊君銳，趙群禮.基于FP-Tree的最大頻繁項(xiàng)目集更新挖掘算法［J］.華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2004，32(11):88-90.

［11］GEORGE A M.WordNet:a lexical database for English［J］.Communications of the ACM，1995，38(11):39-41.