劉建波

(山東財(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］。通過(guò)網(wǎng)絡(luò)短文本信息，人們記錄自己的日常生活及事務(wù)，抒發(fā)感情、釋放情緒。如今的網(wǎng)絡(luò)已成為史上最大的情感倉(cāng)庫(kù)。利用這個(gè)情感倉(cāng)庫(kù)，并從中挖掘有價(jià)值的信息，識(shí)別出群體的輿情趨向及演化規(guī)律，可以更好地分析人們的情感以及社會(huì)輿情熱點(diǎn)，具有較大的研究和應(yīng)用價(jià)值，對(duì)情感話題的檢測(cè)與跟蹤、網(wǎng)絡(luò)用戶群體極端行為方向的挖掘與思想異常檢測(cè)等方面有重要的價(jià)值。

1 相關(guān)研究

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

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

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

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

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

(2)改進(jìn)FP-樹(shù)的節(jié)點(diǎn)用項(xiàng)的序號(hào)標(biāo)記其支持?jǐn)?shù)，項(xiàng)的序號(hào)按支持度由大到小排序確定。每個(gè)節(jié)點(diǎn)包含 4個(gè)域:item、count、ahead和 next，其中item為結(jié)點(diǎn)名稱(chēng)，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-樹(shù)最大頻繁模式挖掘算法如下:

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

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

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

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

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

表1 短文本事物集

圖1 頻繁模式FP-樹(shù)

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

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

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

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

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

3.2 有效處理噪音

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

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

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

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

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

3.4 局部性度量算法

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

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

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

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

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

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

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

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

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

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

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

在我校學(xué)生論壇系統(tǒng)中，帖子以文本文件格式存放，其格式與短文本的特點(diǎn)一致。因此，選取某一段時(shí)間數(shù)據(jù)做實(shí)證分析。通過(guò)Visual C++實(shí)現(xiàn)以上算法，求出頻次大于180的重復(fù)串，λ的取值從0變化到1，步長(zhǎng)為0.05，對(duì)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ù)量超過(guò)800時(shí)，λ的最佳取值為0.5。

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

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

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

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

5 結(jié)論

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

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

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

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

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

［5］柴春梅.互聯(lián)網(wǎng)短文本信息分類(lèi)關(guān)鍵技術(shù)研究［D］.上海:上海交通大學(xué)圖書(shū)館，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-樹(shù)的頻繁模式挖掘算法［J］.廣西師范大學(xué)學(xué)報(bào)，2009，25(4):254-255.

［9］秦亮曦，史忠植.SFP-Max:基于排序FP-樹(shù)的最大頻繁模式挖掘算法［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.