吳含前　 周立鳳　 謝　玨

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京211189)(2東南大學(xué)蒙納士大學(xué)蘇州聯(lián)合研究生院，蘇州215123)

二次剪枝算法在評論特征提取中的應(yīng)用

吳含前1周立鳳1謝玨2

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京211189)(2東南大學(xué)蒙納士大學(xué)蘇州聯(lián)合研究生院，蘇州215123)

摘要:針對序列模式挖掘(GSP)算法在中文產(chǎn)品評論特征提取中準(zhǔn)確率不夠高的問題,提出了一種二次剪枝算法,即利用GSP算法產(chǎn)生候選特征集，然后采用詞對共現(xiàn)度作為閾值對其進(jìn)行進(jìn)一步篩選，從而達(dá)到提高準(zhǔn)確率的目的.利用定制化的爬蟲工具從京東網(wǎng)站上抓取攝像頭產(chǎn)品的中文評論,選取其中1 000條作為試驗(yàn)數(shù)據(jù),采用分詞工具ICTCLAS對評論進(jìn)行分詞和數(shù)據(jù)預(yù)處理,并將所提算法與GSP算法、交叉語言模型(CLM)和似然比檢驗(yàn)(LRT)進(jìn)行對比試驗(yàn).結(jié)果表明,利用所提算法獲得的中文產(chǎn)品評論特征提取準(zhǔn)確率達(dá)到76.37%,較GSP算法、CLM和LRT的準(zhǔn)確率分別提高2.94%,5.77%和7.57%.

關(guān)鍵詞:特征提取;二次剪枝;詞對共現(xiàn)度;似然比檢驗(yàn);交叉語言模型

隨著互聯(lián)網(wǎng)應(yīng)用的不斷發(fā)展,網(wǎng)絡(luò)購物逐漸成為一種消費(fèi)時(shí)尚. 在線評論作為網(wǎng)絡(luò)購物平臺的重要組成部分,為網(wǎng)購用戶做出購買決策及制造商改善產(chǎn)品提供重要依據(jù). 在線評論是網(wǎng)購用戶對產(chǎn)品及產(chǎn)品屬性的主觀評價(jià),它包含了產(chǎn)品符合度(包括產(chǎn)品整體及部分的性能、外觀、手感、質(zhì)量優(yōu)劣情況等)、賣家服務(wù)態(tài)度、物流速度等豐富信息.如何從這些海量的評論中挖掘有價(jià)值的信息成為當(dāng)前學(xué)術(shù)界和工業(yè)界的一個研究熱點(diǎn).

產(chǎn)品特征的提取是在線評論挖掘研究工作中的重要組成部分[1]. 學(xué)術(shù)界通常將評論中出現(xiàn)的頻繁名詞或名詞短語作為產(chǎn)品特征[2-4].通過提取產(chǎn)品特征,可以幫助生產(chǎn)商、銷售商和網(wǎng)購用戶全面分析和了解產(chǎn)品的各個屬性,進(jìn)而為生產(chǎn)商改進(jìn)產(chǎn)品、銷售商推廣產(chǎn)品及網(wǎng)購用戶做出購買決策等提供重要參考信息.此外,產(chǎn)品特征的提取作為后續(xù)評論挖掘工作的研究基礎(chǔ),其結(jié)果的準(zhǔn)確率將直接影響到最終評論挖掘系統(tǒng)的可靠性.

國內(nèi)外學(xué)者已對產(chǎn)品特征的自動化提取展開了深入研究.Hu等[1]于2004年采用關(guān)聯(lián)規(guī)則算法進(jìn)行了特征提取;Popescu等[5]利用互信息去除不是屬性的高頻名詞;Li等[2]基于每個語句與結(jié)構(gòu)化的語義信息來構(gòu)建解析樹,從而自動化識別特征;Chen等[6]利用條件熵和通用算法來自動化提取特征;李實(shí)等[7]利用關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行中文產(chǎn)品特征識別;Javed等[8]利用最大熵模型進(jìn)行特征提取. 本文針對GSP算法[9]自動提取產(chǎn)品特征準(zhǔn)確率不高的問題,提出了一種二次剪枝算法(GSP-TPCW算法).該算法汲取了GSP獲取頻繁名詞和詞組的優(yōu)點(diǎn),利用概率統(tǒng)計(jì)方法來計(jì)算詞語與主題的相關(guān)性,通過設(shè)定相關(guān)度閾值來過濾噪聲數(shù)據(jù),從而提高中文產(chǎn)品評論特征提取的準(zhǔn)確率.將二次剪枝算法與GSP算法、交叉語言模型(CLM)算法[10]、似然比檢驗(yàn)(LRT)算法[11]進(jìn)行比較,以驗(yàn)證所提算法的有效性.

1二次剪枝算法

二次剪枝算法是在GSP算法的基礎(chǔ)上,利用概率統(tǒng)計(jì)的方法計(jì)算詞對共現(xiàn)度,以獲取詞語與主題的相關(guān)性,并通過設(shè)定詞語與主題相關(guān)度的閾值來實(shí)現(xiàn)噪聲數(shù)據(jù)的過濾,從而提高中文產(chǎn)品評論特征的提取準(zhǔn)確率.

1.1GSP算法原理

GSP算法采用冗余候選模式中的剪枝策略進(jìn)行剪枝,最初是為處理數(shù)據(jù)庫中形如〈客戶ID交易時(shí)間交易項(xiàng)〉的客戶交易記錄而提出的.GSP算法考慮了項(xiàng)與項(xiàng)之間的順序.例如,組合詞“性價(jià)比”通過ICTCLAS分詞工具處理之后顯示為“性價(jià)/n比/p”,“性價(jià)”與“比”之間有著嚴(yán)格的先后順序,而關(guān)聯(lián)規(guī)則挖掘算法并不適合提取此類特征,類似的組合詞還有“攝像頭”、“硅膠套”等.GSP算法中的相關(guān)概念如下[12]:

1) 序列模式

序列模式是由頻繁出現(xiàn)的數(shù)據(jù)項(xiàng)構(gòu)建的模式,即一個序列模式s表示一個排過序的項(xiàng)集列表〈α1,α2,…,αn〉.其中,αi(i=1,2,…,n)為序列模式s中的一個序列元素.同時(shí),αi又可表示為一組項(xiàng)目的集合{χ1,χ2,…,χm},其中,χj為一個項(xiàng)目元素.GSP算法的目標(biāo)是從序列模式集合中找出所有滿足用戶指定的最小支持度序列模式(頻繁序列)，可將序列模式集合中該序列模式的個數(shù)作為其支持度.

2) 詞對共現(xiàn)度

詞對共現(xiàn)度是用來度量詞語與主題之間關(guān)聯(lián)程度的指標(biāo),可以通過統(tǒng)計(jì)概率的方法計(jì)算得到[12],其計(jì)算公式為

式中,f(tij)表示詞tj在第i條評論中出現(xiàn)的次數(shù);f(tij∩tik)表示詞tj,tk在第i條評論中連續(xù)出現(xiàn)的次數(shù).w值越大,說明特征名詞與主題關(guān)系越緊密.

1.2GSP-TPCW算法步驟

令Fk表示滿足最小支持度且長度為k的頻繁序列集合,Ck表示所有長度為k的頻繁候選序列集合,則GSP-TPCW算法步驟如下:

① 將原始數(shù)據(jù)集合存入模式數(shù)據(jù)庫S中,形成候選集C1.

② 遍歷數(shù)據(jù)庫S,找出滿足最小支持度的序列模式并將其存入F1.

③ 將元素長度為k的Fk作為種子集,通過連接和剪枝操作,形成長度為k+1的候選集Ck+1并將其作為種子集.重復(fù)該步驟,直到?jīng)]有新的序列模式或候選序列模式產(chǎn)生為止.

④ 通過計(jì)算詞對共現(xiàn)度,對獲得的候選序列模式集合進(jìn)行二次剪枝.檢查序列模式集合中任意2個序列模式在分別去掉其第1個項(xiàng)目和最后1個項(xiàng)目后得到的序列是否相同,如果相同,則對這2個序列模式進(jìn)行連接處理;否則,不進(jìn)行連接處理.然后,計(jì)算每個候選序列模式的支持度,如果結(jié)果小于最小支持度,則將其從候選序列模式集合中刪除,否則保留該候選序列模式,直到最終獲得滿足要求的序列模式集合.

2交叉語言模型

Zhai等[10]提出了一種基于概率方法的交叉語言模型.該模型被廣泛用于語音識別和信息檢索領(lǐng)域.

假定一個文檔由一個目標(biāo)短語集合和一個資料庫短語集合構(gòu)成,即

θ=αθcorpus+βθquery

(1)

式中,θ表示從評論集合中獲取的名詞集合;θcorpus表示資料庫名詞集合;θquery表示與主題相關(guān)的名詞集合;α,β分別為θcorpus和θquery的噪聲干擾因子,且α+β=1.

Zhang等[4]提出了一種時(shí)間復(fù)雜度為O(nlog(n))的算法(n為數(shù)據(jù)規(guī)模),以獲取交叉語言模型中的θ.交叉語言模型可表述為

r=αp+βq

(2)

式中,r,p和q為多維向量.

假設(shè)fi和pi分別為r和p中第i個詞出現(xiàn)的頻率,構(gòu)造式(2)的對數(shù)似然函數(shù)為

對于所有滿足qi>0的qi,采用拉格朗日乘子方法,得到如下公式:

通過求解目標(biāo)函數(shù)的極大值可得

根據(jù)計(jì)算所得的qi值進(jìn)行排序,并設(shè)定一個閾值,選取大于該閾值的詞構(gòu)建最終的特征集合.

3似然比檢驗(yàn)

(3)

表1　詞頻統(tǒng)計(jì)

假設(shè)每個詞都服從貝努利分布b(p,k,n)=pk·(1-p)n-k,表1中的計(jì)數(shù)服從二項(xiàng)式分布,則式(3)中的似然比近似服從χ2分布,即

(4)

式中,

y=maxb(p1,C11,C11+C12)b(p2,C21,C21+C22)

式(4)可以轉(zhuǎn)換為

(5)

式中,

h=(C11+C21)log(r)+(C12+C22)log(1-r)-

C11log(r1)-C12log(1-r1)-

C21log(r2)-C22log(1-r2)

根據(jù)式(5)可以計(jì)算得到詞w的似然比.似然比越大,表示詞w與主題T之間的相關(guān)度也越大. 在實(shí)際應(yīng)用中,可以通過設(shè)定閾值來選取最終的特征集合.

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

4.1資料庫的建立

實(shí)現(xiàn)似然比檢驗(yàn)和交叉語言模型需要構(gòu)建主題相關(guān)資料庫和主題無關(guān)資料庫.為此,本文利用自定義爬蟲工具抓取了京東商城中的10個電子產(chǎn)品(包括電腦、耳機(jī)、音響、MP3、平板、電源等),共1×105條評論,8位研究生采用人工方式參與了對上述評論中名詞和名詞詞組的提取工作,剔除與電子產(chǎn)品無關(guān)的名詞和一些常用名詞(如東西、產(chǎn)品、東東等),構(gòu)建了主題相關(guān)資料庫.此外,采用同樣方法,通過抓取豆瓣網(wǎng)站的60部電影評論,構(gòu)建了主題無關(guān)資料庫.

4.2數(shù)據(jù)集的選取和處理

實(shí)驗(yàn)數(shù)據(jù)集選用了攝像頭的產(chǎn)品評論,經(jīng)過預(yù)處理后選擇1 000條評論作為測試數(shù)據(jù). 采用中國科學(xué)院的分詞工具ICTCLAS對上述測試數(shù)據(jù)進(jìn)行分詞,并提取其中的名詞.例如,對于評論“攝像頭不錯,性價(jià)比很高!”,經(jīng)過分詞后得到的名詞序列為“攝像、頭、性、價(jià)”,將該名詞序列作為一行記錄存入文本文件中,其中“攝像”、“頭”、“性”、“價(jià)”均為序列中的項(xiàng).

為了評估各種特征提取算法的有效性,將準(zhǔn)確率p、召回率r以及兩者的加權(quán)平均值f作為測試算法性能的評價(jià)指標(biāo),其中f的計(jì)算公式如下:

(6)

4.3結(jié)果比較及分析

根據(jù)實(shí)踐經(jīng)驗(yàn)并結(jié)合本文設(shè)計(jì)的實(shí)驗(yàn)環(huán)境,二次剪枝過程中詞對共現(xiàn)度的閾值設(shè)為0.68.GSP-TPCW算法與GSP算法的實(shí)驗(yàn)結(jié)果見表2.

表2GSP-TPCW算法與GSP算法的評價(jià)指標(biāo)

%

由表2可知,就準(zhǔn)確率、召回率以及兩者加權(quán)平均值這3個評價(jià)指標(biāo)而言,本文提出的GSP-TPCW算法明顯高于GSP算法,這是因?yàn)樗崴惴ㄍㄟ^設(shè)定的詞對共現(xiàn)度閾值有效過濾掉一些評論中不存在的名詞組合,從而提高了算法的性能.另外,GSP-TPCW算法的召回率相對偏低,這與實(shí)驗(yàn)中設(shè)置的候選序列模式最小支持度有關(guān),若最小支持度設(shè)置過低,則會產(chǎn)生較多噪聲數(shù)據(jù),導(dǎo)致準(zhǔn)確率不高;反之,若最小支持度設(shè)置過高,準(zhǔn)確率會提高,但召回率降低.本實(shí)驗(yàn)中,將最小支持度設(shè)置為3.

為了進(jìn)一步驗(yàn)證GSP-TPCW算法的有效性,將其與交叉語言模型和似然比檢驗(yàn)進(jìn)行對比. 實(shí)驗(yàn)過程中考慮了以下2種情況:① 保留單個漢字的名詞;② 刪除單個漢字的名詞.實(shí)驗(yàn)結(jié)果見表3.

表3　3種算法的評價(jià)指標(biāo)　%

由表3可知,GSP-TPCW算法的綜合性能較似然比檢驗(yàn)和交叉語言模型好,這與分詞工具的準(zhǔn)確性和中文評論資料庫的完善程度有關(guān).例如,ICTCLAS分詞工具將“性價(jià)比很高”分詞為 “性/n價(jià)/n比/p很/d高/a”,提取名詞為“性”與“價(jià)”;將“攝像頭不錯”分詞為“攝像/n頭/n不錯/a”,提取名詞為“攝像”與“頭”;顯然,“性價(jià)比”和“攝像頭”這些常用名詞不能通過似然比檢驗(yàn)和交叉語言模型準(zhǔn)確獲取,而GSP-TPCW算法則可通過獲取頻繁詞序列得到. 此外,刪除單個漢字名詞后的準(zhǔn)確率和加權(quán)平均值均比保留單個漢字名詞的準(zhǔn)確率與調(diào)和平均值高,這進(jìn)一步證明了GSP-TPCW算法的有效性.實(shí)驗(yàn)過程中,采用似然比檢驗(yàn)和交叉語言模型都需要構(gòu)建資料庫,且要求人工參與,而GSP-TPCW算法則不需要構(gòu)建資料庫,從而能夠?qū)崿F(xiàn)針對產(chǎn)品特征的高效提取.

綜上可知,利用GSP-TPCW算法獲得的中文產(chǎn)品評論特征提取準(zhǔn)確率達(dá)到76.37%,較GSP算法、CLM和LRT的準(zhǔn)確率分別提高2.94%,5.77%和7.57%.

基于本文實(shí)驗(yàn)采用的資料庫,采用GSP-TPCW算法、交叉語言模型和似然比檢驗(yàn)獲得的部分產(chǎn)品特征見表4.

表4　攝像頭特征自動獲取結(jié)果

5結(jié)語

本文針對網(wǎng)購平臺中文在線評論的產(chǎn)品特征提取,提出了一種二次剪枝算法.該算法在GSP算法的基礎(chǔ)上,采用詞對共現(xiàn)度作為閾值對候選特征集進(jìn)行進(jìn)一步篩選,從而提高準(zhǔn)確率. 采用1 000條攝像頭的中文評論作為測試數(shù)據(jù),并與GSP算法、交叉語言模型和似然比檢驗(yàn)進(jìn)行了比較.結(jié)果表明,利用所提算法進(jìn)行中文產(chǎn)品評論特征提取可獲得較高的準(zhǔn)確率.

參考文獻(xiàn) (References)

[1]HuM,LiuB.Miningopinionfeaturesincustomerreviews[C]//Proceedings of the 19th National Conference on Artifical Intelligence.Chicago,Illinois,USA, 2004:755-760.

[2]LiF,PanSJ,JinO,etal.Cross-domainco-extractionofsentimentandtopiclexicons[C]//Meeting of the Association for Computational Linguistics: Long Papers.Beijing,China, 2012:410-419.

[3]FeiG,LiuB,HsuM,etal.Adictionary-basedapproachtoidentifyingaspectsimpliedbyadjectivesforopinionmining[C]//24th International Conference on Computational Linguistics.Chicago,Illinois,USA,2012:309-318.

[4]ZhangY,XuW.Fastexactmaximumlikelihoodestimationformixtureoflanguagemodel[J]. Information Processing & Management, 2008, 44(3):1076-1085.DOI:10.1016/j.ipm.2007.12.003.

[5]PopescuA-M,EtzioniO.Extractingproductfeaturesandopinionsfromreviews[C]//Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing.Washington,DC,USA, 2005:32-33.

[6]ChenY,WangX.Textfeatureextractionbasedonjointconditionalentropy[C]//Proceedings of 2012 2nd International Conference on Computer Science and Network Technology.Changchun,China, 2012:2055-2058.

[7]李實(shí), 葉強(qiáng), 李一軍, 等. 挖掘中文網(wǎng)絡(luò)客戶評論的產(chǎn)品特征及情感傾向[J]. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(8):3016-3019.DOI:10.3969/j.issn.1001-3695.2010.08.054.

LiShi,YeQiang,LiYijun,etal.MiningproductfeaturesandsentimentorientationfromChinesecustomerreviews[J]. Application Research of Computers, 2010, 27(8):3016-3019.DOI:10.3969/j.issn.1001-3695.2010.08.054.(inChinese)

[8]JavedK,BabriHA,SaeedM.Featureselectionbasedonclass-dependentdensitiesforhigh-dimensionalbinarydata[J]. IEEE Trans Knowl Data Eng, 2012, 24(3):465-477.DOI:10.1109/tkde.2010.263.

[9]AgrawalR,SrikantR.Miningsequentialpatterns[C]//Proceedings of the Eleventh International Conference on Data Engineering.Taipei,China, 1995: 3-14.

[10]ZhaiC,LaffertyJ.Model-basedfeedbackinthelanguagemodelingapproachtoinformationretrieval[C]//Proceedings of the Tenth International Conference on Information and Knowledge Management.Pittsburgh,Pennsylvania,USA, 2001: 403-410.

[11]FerreiraL,JakobN,GurevychI.Acomparativestudyoffeatureextractionalgorithmsincustomerreviews[C]// 2008 IEEE International Conference on Semantic Computing.SantaClara,California,USA, 2008: 144-151.DOI:10.1109/icsc.2008.40.

[12]ZhengY,YeL,WuGF,etal.ExtractingproductfeaturesfromChinesecustomerreviews[C]//2008 3rd International Conference on Intelligent System and Knowledge Engineering.Xiamen,China, 2008: 285-290.DOI:10.1109/iske.2008.4730942.

Applicationofsecondarypruningalgorithmincommentaryfeatureextraction

WuHanqian1ZhouLifeng1XieJue2

(1SchoolofComputerScienceandEngineering,SoutheastUniversity,Nanjing211189,China) (2SoutheastUniversity-MonashUniversityJointGraduateSchool,Suzhou215123,China)

Abstract:Aiming at the low accuracy rate of the generalized sequence pattern (GSP) algorithm on product feature extraction from Chinese online reviews, a secondary pruning algorithm is proposed. In this algorithm, based on the candidate collection of the output of the GSP algorithm, the term pair co-occurrence weight (TPCW) is used as the threshold for further filtering to improve the accuracy rate.The customized tools are used to crawl the product Chinese reviews of cameras from Jingdong website. 1 000 reviews are selected as the experimental data and the segmentation tool ICTCLAS is used on the word segmentation and data preprocessing. The proposed algorithm is compared with the GSP algorithm, the cross language model (CLM), and the likelihood ratio test (LRT). The results show that the accuracy rate of the proposed algorithm on product feature extraction from Chinese online reviews is 76.37%, which is higher than those of the GSP algorithm, CLM and LRT by 2.94%, 5.77% and 7.57%, respectively.

Key words:feature extraction; secondary pruning; term pair co-occurrence weight; likelihood ratio test; cross language model

DOI:10.3969/j.issn.1001-0505.2016.03.010

收稿日期:2015-08-22.

作者簡介:吳含前(1972—)，男，博士，副教授， hanqian@seu.edu.cn.

基金項(xiàng)目:中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目、國家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃) 資助項(xiàng)目(2015AA015904).

中圖分類號:TP315.69

文獻(xiàn)標(biāo)志碼:A

文章編號:1001-0505(2016)03-0513-05

引用本文: 吳含前，周立鳳，謝玨.二次剪枝算法在評論特征提取中的應(yīng)用[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,46(3):513-517.DOI:10.3969/j.issn.1001-0505.2016.03.010.