王夢(mèng)遙 王曉曄 洪睿琪

摘? 要： 本文對(duì)于意見挖掘領(lǐng)域中的評(píng)價(jià)對(duì)象的修剪和聚類問題，提出使用K-means聚類算法和BIRCH聚類算法相結(jié)合的方式來進(jìn)行評(píng)價(jià)對(duì)象的修剪和聚類。利用BIRCH算法類別聚類的功能對(duì)評(píng)價(jià)對(duì)象進(jìn)行聚類，并刪除包含較少數(shù)據(jù)的簇來實(shí)現(xiàn)修剪評(píng)價(jià)對(duì)象;再通過對(duì)于剩下的簇使用K-means聚類算法來獲得最優(yōu)評(píng)價(jià)對(duì)象。這種修剪聚類方法與以往的基于PMI算法修剪然后基于K-means聚類算法相比，減少了評(píng)價(jià)對(duì)象修剪時(shí)對(duì)語料庫的依賴，最終聚類的結(jié)果更加精準(zhǔn)，而且BIRCH算法采用一次掃描數(shù)據(jù)庫的策略，可以有效提高速度。

關(guān)鍵詞： 名詞詞組模式;BIRCH聚類算法;K-means聚類算法;PMI算法

【Abstract】： For the pruning and clustering evaluation objects in opinion mining， this paper proposes a method that combines BIRCH clustering and K-means clustering algorithm to prune and cluster evaluation objects. Firstly， utilizing BIRCH algorithm of self-learning cluster category， after clustering by BIRCH algorithm， delete the clusters containing few data so that we can prune the evaluation objects. Then use K-means clustering algorithm to make global cluster for the remaining clusters. Compared with pruning using PMI algorithm and clustering using K-means clustering algorithm， our method eliminates the dependency on the corpus. And the cluster result is more accurate. Also BIRCH algorithm scans the database one time， so it can increase the speed greatly.

【Key words】： Noun phrase pattern; BIRCH clustering algorithm; K-means clustering algorithm; PMI algorithm

0? 引言

隨著電子商務(wù)行業(yè)的發(fā)展，網(wǎng)購在人們生活中起到越來越重要的作用，用戶通過查看購物網(wǎng)站的評(píng)論信息來對(duì)商品有更加全面的了解。但同一產(chǎn)品在網(wǎng)絡(luò)中的評(píng)論可能會(huì)達(dá)到成千上萬條，給用戶全部逐條查看帶來了極大的麻煩，這基本是不可能實(shí)現(xiàn)的。而且評(píng)價(jià)信息數(shù)據(jù)量雖然極大，但信息量稀疏，也就是說不是所有的句子都是有用的，這又使得用戶評(píng)論的參考價(jià)值大大降低。因此，挖掘用戶評(píng)論提取出有用信息供給用戶查看就顯得十分必要了。

評(píng)論信息的意見挖掘是從評(píng)論信息中提取主題詞的過程，主題詞包括評(píng)價(jià)對(duì)象，然后對(duì)評(píng)價(jià)對(duì)象進(jìn)行處理分析。目前對(duì)評(píng)價(jià)對(duì)象處理的方法有很多，比如，張俊飛[1]等人，通過改進(jìn)PMI算法實(shí)現(xiàn)特征值提取，利用TF-IDF函數(shù)實(shí)現(xiàn)特征值權(quán)重計(jì)算，實(shí)現(xiàn)基于PMI特征值TF-IDF加權(quán)樸素貝葉斯算法;陳海紅等人[2]，利用信息增益法進(jìn)行文本特征選取，運(yùn)用TF-IDF進(jìn)行特征權(quán)重設(shè)置，對(duì)支持向量機(jī)使用不同核函數(shù)，通過網(wǎng)格與交叉驗(yàn)證組合法優(yōu)化參數(shù)選擇，比較支持向量機(jī)在不同核函數(shù)下文本分類性能;為了減少數(shù)據(jù)集和訓(xùn)練方法對(duì)詞向量質(zhì)量的影響，王子牛、吳建華、高建瓴等人[3]提出了深度神經(jīng)網(wǎng)絡(luò)結(jié)合LSTM模型來實(shí)現(xiàn)情感分析;林欽、劉鋼[4]等人采用關(guān)聯(lián)算法挖掘商品特征的算法實(shí)現(xiàn)領(lǐng)域詞典的半自動(dòng)更新;孟鑫[5]等人在通用領(lǐng)域詞典的基礎(chǔ)上，增添領(lǐng)域情感詞及其情感強(qiáng)度值，通過計(jì)算詞語相似度，構(gòu)建專用領(lǐng)域情感詞典;李春婷[6]等人將模糊認(rèn)知圖理論應(yīng)用于詞語聚類，實(shí)際上屬于基于神經(jīng)網(wǎng)絡(luò)的聚類方法。

在前人研究的基礎(chǔ)上，本文采用名詞詞組模式來提取主題詞，然后使用BIRCH算法[7]與K-means聚類算法[8]相結(jié)合的方法對(duì)評(píng)價(jià)對(duì)象進(jìn)行修剪和聚類[9]。

1? 主題詞的抽取

主題詞抽取首先對(duì)評(píng)論信息進(jìn)行預(yù)先處理。處理工作主要分兩個(gè)部分：評(píng)論中經(jīng)常會(huì)包含明顯的無效信息，比如，QQ號(hào)、電話號(hào)碼或網(wǎng)址的句子有做廣告的嫌疑，重復(fù)出現(xiàn)的句子沒有意義，首先將這類評(píng)論刪除。之后是對(duì)句子進(jìn)行分詞和詞性標(biāo)注，由于我們主要依靠形容詞判斷句子情感，所以刪除不含有形容詞的評(píng)論。分詞采用中科院的分詞工具ICTCLAS2015[10]。

抽取主題詞[11]的關(guān)鍵在于評(píng)價(jià)詞和評(píng)價(jià)對(duì)象的抽取。對(duì)于評(píng)價(jià)對(duì)象的抽取，總結(jié)為對(duì)名詞、動(dòng)名詞、名詞短語的抽取，本文通過分析句式，構(gòu)建了以下四種名詞詞組形式：n和n和n、n和n、n的n、nn或n，進(jìn)而對(duì)句子進(jìn)行匹配并抽取主題詞。具體抽取步驟如下：

（1）使用上面幾種名詞詞組對(duì)于評(píng)論中的分句進(jìn)行匹配，根據(jù)此來確定評(píng)價(jià)對(duì)象，并同時(shí)匹配形容詞或其他詞性來抽取評(píng)論信息;

（2）若分句中只有評(píng)價(jià)詞而沒有評(píng)價(jià)對(duì)象，則將其前面分句中的評(píng)價(jià)對(duì)象作為該分句的評(píng)價(jià)對(duì)象;若前面分句也沒有評(píng)價(jià)對(duì)象，則該分句中的評(píng)價(jià)對(duì)象為隱式的，此時(shí)通過創(chuàng)建評(píng)價(jià)詞和評(píng)價(jià)對(duì)象的語義集的方法來確定隱式評(píng)價(jià)對(duì)象。

（3）若分句中只有評(píng)價(jià)對(duì)象沒有評(píng)價(jià)詞，則保存，如果后續(xù)沒有評(píng)價(jià)對(duì)象，則將其作為此分句中評(píng)價(jià)詞的評(píng)價(jià)對(duì)象;

（4）本文采取建立語義相關(guān)集的方法來抽取隱式評(píng)價(jià)對(duì)象，如下：

1）統(tǒng)計(jì)已抽取出的評(píng)價(jià)詞和評(píng)價(jià)對(duì)象在評(píng)論中出現(xiàn)的次數(shù)，選取出現(xiàn)次數(shù)最高的90個(gè)評(píng)價(jià)詞和45個(gè)評(píng)價(jià)對(duì)象;

2）統(tǒng)計(jì)每一對(duì)評(píng)價(jià)詞和評(píng)價(jià)對(duì)象共同出現(xiàn)的次數(shù);

3）對(duì)于每一個(gè)評(píng)價(jià)對(duì)象，選擇其對(duì)應(yīng)的出現(xiàn)次數(shù)最高的45個(gè)評(píng)價(jià)詞，以它們的組合詞對(duì)組成語義相關(guān)集，對(duì)應(yīng)的評(píng)價(jià)對(duì)象通過使用已抽取出的評(píng)價(jià)詞搜索語義相關(guān)集來確定。

2? 主題詞的修剪及聚類

有些抽取出的評(píng)價(jià)對(duì)象與商品無關(guān)，需要去掉。比如“淘寶網(wǎng)很棒”這句話，雖然評(píng)價(jià)詞“棒”被抽取出來，“淘寶網(wǎng)”也被作為評(píng)價(jià)對(duì)象提取，但這一分句并未對(duì)商品的屬性做出評(píng)價(jià)。所以需要去掉這些冗余數(shù)據(jù)后，再對(duì)剩下的數(shù)據(jù)聚類以得到最終評(píng)價(jià)對(duì)象。

2.1? BIRCH算法的預(yù)聚類

BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）利用層次方法的平衡迭代規(guī)約和聚類。它使用聚類特征（Clustering Feature， CF）和聚類特征樹（CF Tree）兩個(gè)概念，用于概述聚類。聚類特征樹概括了聚類的使用信息，并且占用空間較原來數(shù)據(jù)集小得多，可以存儲(chǔ)在內(nèi)存中，從而可以提高算法在大型數(shù)據(jù)集上的速度及伸縮性。關(guān)于BIRCH聚類算法，數(shù)據(jù)的插入順序?qū)垲愄卣鳂涞臉?gòu)建影響很大，所以本文通過對(duì)初始數(shù)據(jù)集進(jìn)行預(yù)聚類的方法，首先已知數(shù)據(jù)集合插入順序，再將數(shù)據(jù)按照順序插入來構(gòu)造聚類特征樹。在預(yù)聚類階段采用的算法是K-means算法，因?yàn)樵撍惴ㄐ矢?、?shí)規(guī)定現(xiàn)簡(jiǎn)單、復(fù)雜度較低，不會(huì)在初始階段增加BIRCH算法的復(fù)雜度。

為了將語言數(shù)學(xué)化，首先將所有評(píng)價(jià)對(duì)象轉(zhuǎn)化為詞向量，具體步驟如下：選取提取到的最高頻次的15個(gè)評(píng)價(jià)詞，該評(píng)價(jià)對(duì)象與這15個(gè)評(píng)價(jià)詞在評(píng)論中出現(xiàn)的次數(shù)即可用向量中的元素值來表示。比如，本文針對(duì)“手機(jī)”評(píng)論挑選的評(píng)價(jià)詞包括：“流暢”、“使用穩(wěn)定”、“操作方便”、“美觀”、“速度快”等共15個(gè)評(píng)價(jià)詞，而“攝像頭”這個(gè)評(píng)價(jià)對(duì)象表示成向量為[443， 227， 201， 145， 88， 129， 49， 55， 60， 41， 38， 42， 53， 44， 95]，向量中的元素代表“攝像頭”與評(píng)論中15個(gè)評(píng)價(jià)詞共同出現(xiàn)的次數(shù)。

對(duì)于K-means聚類算法的初始質(zhì)心如何選擇的問題，采用最大距離法[12]，保證各質(zhì)心不屬于同一類并且之間的距離盡量大。在計(jì)算各數(shù)據(jù)點(diǎn)之間的距離時(shí)，采用歐幾里得距離的方法。算法的具體細(xì)節(jié)見文獻(xiàn)[13]。

2.2? BIRCH聚類算法

關(guān)于BIRCH聚類算法中的幾個(gè)閾值[14，15]，直徑閾值T的確定如下：從數(shù)據(jù)集里選取N個(gè)數(shù)據(jù)，分別計(jì)算每?jī)蓚€(gè)數(shù)據(jù)之間的距離，計(jì)算這些距離的方差值DX和期望值EX，則閾值T = EX + 0.25 × DX。對(duì)于確定葉子節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)L以及非葉子結(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)B，通過抽取部分?jǐn)?shù)據(jù)作為測(cè)試集，反復(fù)實(shí)驗(yàn)，得到實(shí)驗(yàn)結(jié)果最好時(shí)的L和B值。

CF樹建完以后，每個(gè)葉節(jié)點(diǎn)包含的數(shù)據(jù)點(diǎn)就是一個(gè)簇，刪除所含節(jié)點(diǎn)數(shù)很少的簇，因?yàn)檫@些數(shù)據(jù)很可能是抽取出來的與商品無關(guān)的特征。由于BIRCH算法中閾值的限制，CF樹每個(gè)節(jié)點(diǎn)只能包含一定數(shù)量的子節(jié)點(diǎn)，最后得出來的簇可能和真實(shí)結(jié)果差別很大，所以需要對(duì)BIRCH聚類算法得出的聚類的結(jié)果進(jìn)行全局聚類。本文采用K-means聚類算法進(jìn)行全局聚類。

BIRCH算法步驟如表1所示。

3? 實(shí)驗(yàn)分析

3.1? BIRCH算法與PMI算法修剪評(píng)價(jià)對(duì)象實(shí)驗(yàn)對(duì)比分析

本文使用的實(shí)驗(yàn)數(shù)據(jù)是京東商城上手機(jī)的評(píng)論信息，共計(jì)1萬條數(shù)據(jù)。

為了驗(yàn)證BIRCH算法修整評(píng)價(jià)對(duì)象的效果，本文用它和常用的PMI算法修剪評(píng)價(jià)對(duì)象的結(jié)果進(jìn)行對(duì)比，通過分析兩種方法的準(zhǔn)確率、F值和召回率，進(jìn)而判定本文方法的效果。正確率就是對(duì)于操作出來的數(shù)據(jù)中正確操作的數(shù)據(jù)所占的比例，召回率是對(duì)于總樣本數(shù)據(jù)中正確操作的數(shù)據(jù)所占的比例，F(xiàn)值是二者的綜合指標(biāo)。

實(shí)驗(yàn)中BIRCH聚類算法中不是葉子結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)B為10，簇的直徑閾值T為3.9，葉子節(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)設(shè)定為15，將PMI算法中的修剪閾值設(shè)為0.3。將1萬條數(shù)據(jù)分為五個(gè)數(shù)據(jù)部分：2000條、4000條、6000條、8000條、10000條，上述兩種方法在不同數(shù)據(jù)段上的實(shí)驗(yàn)結(jié)果如表2和圖所示，使用BIRCH算法的修剪準(zhǔn)確率明顯高于PMI算法，因?yàn)镻MI算法對(duì)閾值和語料庫有非常大的依賴，需要綜合的語料庫作支撐，本實(shí)驗(yàn)選取的是微軟開發(fā)的必應(yīng)搜索引擎的語料庫，但如果同時(shí)增大語料庫，時(shí)間復(fù)雜度將會(huì)增加。

3.2? BIRCH聚類算法實(shí)驗(yàn)分析

以往對(duì)評(píng)價(jià)對(duì)象進(jìn)行聚類采用的方法主要是兩種：一種是通過創(chuàng)建商品屬性集合以及屬性常用的表達(dá)方式來組成映射集，然后對(duì)每個(gè)評(píng)價(jià)對(duì)象確定最終評(píng)價(jià)對(duì)象時(shí)，搜尋映射集來確定;另一種方法也是使用聚類算法，比如K均值聚類算法。本文為了驗(yàn)證將BIRCH聚類算法應(yīng)用于評(píng)價(jià)對(duì)象聚類方面的有效性，將其與上述兩種方法的正確率進(jìn)行實(shí)驗(yàn)對(duì)比分析。

首先是映射集方法，實(shí)驗(yàn)建立的映射集部分如表2。

使用K-means算法進(jìn)行屬性統(tǒng)一時(shí)，將評(píng)價(jià)對(duì)象聚為13類，然后選擇相對(duì)較集中的簇并且簇中數(shù)量較多的作為最終評(píng)價(jià)對(duì)象，結(jié)果為“手機(jī)”、“性價(jià)比”、“快遞速度”、“使用感受”、“散熱”、“聲音”、“外觀”、“服務(wù)”。

在對(duì)上節(jié)的BIRCH算法得出的每一簇，選擇出現(xiàn)頻率最高的數(shù)據(jù)來組成數(shù)據(jù)集，使用K-means算法進(jìn)行聚類，即完成了本文中方法的實(shí)驗(yàn)。最后，對(duì)這三種方法的結(jié)果進(jìn)行對(duì)比，圖1展示了三種方法在評(píng)論數(shù)據(jù)集分別在2000、4000、6000、8000和10000條時(shí)的正確率。