基于改進(jìn)BIRCH聚類算法的評價對象挖掘

王夢遙 王曉曄 洪睿琪

摘? 要： 本文對于意見挖掘領(lǐng)域中的評價對象的修剪和聚類問題，提出使用K-means聚類算法和BIRCH聚類算法相結(jié)合的方式來進(jìn)行評價對象的修剪和聚類。利用BIRCH算法類別聚類的功能對評價對象進(jìn)行聚類，并刪除包含較少數(shù)據(jù)的簇來實現(xiàn)修剪評價對象;再通過對于剩下的簇使用K-means聚類算法來獲得最優(yōu)評價對象。這種修剪聚類方法與以往的基于PMI算法修剪然后基于K-means聚類算法相比，減少了評價對象修剪時對語料庫的依賴，最終聚類的結(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)站的評論信息來對商品有更加全面的了解。但同一產(chǎn)品在網(wǎng)絡(luò)中的評論可能會達(dá)到成千上萬條，給用戶全部逐條查看帶來了極大的麻煩，這基本是不可能實現(xiàn)的。而且評價信息數(shù)據(jù)量雖然極大，但信息量稀疏，也就是說不是所有的句子都是有用的，這又使得用戶評論的參考價值大大降低。因此，挖掘用戶評論提取出有用信息供給用戶查看就顯得十分必要了。

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

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

1? 主題詞的抽取

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

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

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

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

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

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

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

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

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

2? 主題詞的修剪及聚類

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

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

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

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

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

2.2? BIRCH聚類算法

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

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

BIRCH算法步驟如表1所示。

3? 實驗分析

3.1? BIRCH算法與PMI算法修剪評價對象實驗對比分析

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

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

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

3.2? BIRCH聚類算法實驗分析

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

首先是映射集方法，實驗建立的映射集部分如表2。

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

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