基于改進特征提取及聚類的網絡評論挖掘研究

李昌兵+龐崇鵬 凌永亮+王強

〔摘要〕[目的/意義]針對信息過載條件下中文網絡產品評論中特征提取性能低以及特征聚類中初始中心點的選取問題。[方法/過程]本研究提出采用基于權重的改進Apriori算法產生候選產品特征集合，再根據獨立支持度、頻繁項名詞非特征規則及基于網絡搜索引擎的PMI算法對候選產品特征集合進行過濾。并以基于HowNet的語義相似度和特征觀點共現作為衡量產品特征之間關聯程度的特征，提出一種改進 K-means 聚類算法對產品特征進行聚類。[結果/結論]實驗結果表明，在特征提取階段，查準率為69%，查全率為9264%，綜合值達到7907%。在特征聚類階段，本文提出的改進K-means算法相對傳統算法具有更優的挖掘性能。

〔關鍵詞〕Apriori算法；特征提取；PMI算法；K-means算法；語義相似度

DOI：10.3969/j.issn.1008-0821.2018.02.011

〔中圖分類號〕TP393〔文獻標識碼〕A〔文章編號〕1008-0821（2018）02-0068-07

Research on Network Review Mining Based on Improved

Feature Extraction and Clustering

Li ChangbingPang Chongpeng*Ling YongliangWang Qiang

（School of Economics and Management，Chongqing University of Posts and Telecommunications，

Chongqing 400065，China）

〔Abstract〕[Purpose/Significance]Aiming at the problem that the feature extraction performance is low and the initial center point in the feature clustering is under the condition of information overload condition.[Method/Process]In this study，a new Apriori algorithm based on weight was proposed to generate candidate product feature sets，and then the candidate product feature sets were filtered according to independent support，frequent item term non-feature rules and PMI algorithm based on web search engine.Based on HowNets semantic similarity and feature view co - occurrence as a feature to measure the degree of correlation between product features，an improved K - means clustering algorithm was proposed to cluster the product characteristics.[Result/Conclusion]The experimental results showed that the precision is 69%，the recall rate was 9264%，and the comprehensive value was 7907%.In the stage of feature clustering，the improved K-means algorithm proposed in this paper had better mining performance than traditional algorithm.

〔Key words〕Apriori algorithm；feature extraction；PMI algorithm；K-means algorithm；semantic similarity

隨著互聯網的迅速發展，評論挖掘作為一種從數據中探索有用信息為目標的技術逐漸被研究者所關注。在許多電商領域，用戶在做出購買決策之前都會瀏覽產品的評論信息以此決定是否購買該產品。然而，在信息過載條件下，通常的分類目錄和搜索引擎需要用戶能準確描述自己的需求，而當用戶無法準確描述自己的需求時，前述方法就無能為力了。這時就需要借助以數據挖掘技術為基礎的推薦系統，從海量的網絡產品評論信息中獲取自己需要的信息、產品或服務。

產品特征提取是在海量的網絡產品評論信息中提取出用戶真正關心的產品特征。在這些產品特征里，往往會發現同一種特征在評論句子中可以有不同的短語或詞來描述，如評價手機的“功能”和“機能”實際上表示的是同一個產品特征。因此，對提取出的產品特征信息進行相應聚類也是非常有意義的。現如今，許多國內外研究者在這些方面都取得了不錯的成果。在特征提取方面，Zhuang L等[1]采用人工或半自動的方式對電影中文評論領域進行產品特征提取研究。Kobayash N等[2]提出利用產品、產品特征和觀點詞之間的共現模式的半自動化方法提取產品特征和觀點詞。婁德成等[3]利用半自動方式進行人工定義，從而抽取出產品評論信息。Hu M等[4]抽取出現頻率大的名詞及名詞短語作為候選產品特征，通過壓縮剪枝和冗余剪枝策略對提取的頻繁商品特征進行篩選，再使用關聯規則挖掘識別頻繁產品特征。此方法使得各性能指標有了較大提升。Popescu A M等[5]將產品特征看作是產品的一部分，使用候選產品特征和領域特征之間的共現來提取商品特征，并使用點互信息PMI（Pointwise Mutual Information）表示關聯程度，最終按關聯程度大小選擇商品特征。該方法提高了產品特征提取的準確率，但召回率有所下降。在特征聚類方面，Guo H等人提出了一種兩層監督算法mLSA，根據多層次潛在語義關聯技術實現對產品特征的聚類[6]。Zhai和Liu在EM算法的基礎上提出了一種約束的半監督的SC-EM學習方法歸納特征，主要采用兩條約束信息，選擇文本上下文信息作為特征，并對其中一條約束信息進行人工標注，進行分類器分類，通過實驗驗證此方法具有明顯的可行性[7]。楊源等提出一種權重標準化方法，然后結合Zhai提出的SC-EM方法，來計算被提取的產品特征之間的相似度，大大提高了聚類效果[8]。張姝等人第一次把經典K-means算法應用于對產品特征進行聚類[9]。Guo H等人提出了一種PLSA方法，利用產品特征詞和觀點詞往往同時出現的信息，對產品特征進行聚類，并取得比較好的聚類效果[6]。對于傳統的K-means算法來說，對初始類中心點的選擇并不理想，導致聚類效果不佳。

所以，針對上述存在的問題。傳統關聯規則Apriori算法運行效率低，以及其是根據特征項出現頻次來設置最低支持度，會導致頻次相對較低且更有價值的特征項未被提取出來。基于此，本文首次將基于權重的改進Apriori算法[10]引入到產品特征預抽取階段進行頻繁項挖掘，然后采用基于網絡搜索引擎的PMI算法[11]進行過濾提取最優產品特征集合。傳統的K-means算法在選擇初始類中心點的時候是隨機選擇的，而初始類中心點的選擇對聚類效果起著重要性作用，本文引入圖論中最小生成樹Prim算法[12]選擇初始類中心點，對聚類算法進行改進。實驗結果表明，挖掘性能指標均有顯著提高。

1中文網絡產品評論挖掘的框架流程

如圖1所示，具體步驟如下：

1）應用Python工具的Jieba分詞包對原始評論語料進行分詞和詞性標注。

2）根據Jieba分詞工具所使用的詞語標記符號，其中與名詞相關的子集標記符號有{/n，/nr，/ns，/nt，/nz，/nl，/ng}，再根據這些標記符號所代表的含義和語法特點，本文選取{/n}作為抽取規則。使用計算機程序對每一條評論中進行抽取。

3）采用基于權重的改進Apriori算法產生候選集合。

4）建立常見中文頻繁項名詞卻非產品特征的集合，并從中文語義及語法角度過濾候選特征集合，利用基于網絡搜索引擎的PMI算法進一步過濾形成產品特征集合。常見的頻繁項名詞卻非產品特征主要劃定為以下幾種情況：

①常見商品的品牌。例如“諾基亞”、“三星”、“西門子”等名詞。

②一些常見的口語化名詞。例如“機子”、“情況”、“方面”、“賣點”、“優缺點”等。

③與產品無關的稱呼類名詞，例如“朋友”、“同事”、“男子”等。

④計算機程序識別出來的少量錯誤名詞，例如“高端”、“聊天”、“海量”等。

⑤常見的集合類名詞，例如“群組”、“大家”等。

⑥單字詞，例如“功”、“卡”等。

5）利用改進語義相似度算法提取特征信息。

6）利用改進傳統K-means算法進行特征聚類形成特征聚類集合。

2具體改進算法

本文從兩個方面對中文網絡產品評論挖掘方法進行改進。首先首次將基于矩陣與權重的改進Apriori算法運用到特征預選擇階段，再利用基于網絡與搜索引擎的PMI算法進行最終過濾；然后，針對傳統K-means聚類算法隨機選擇初始類中心點的不足，提出用圖論中的Prim算法來確定選擇初始類中心點，從而實現較好的聚類效果。

21基于權重的改進Apriori算法

用評論語料和特征集合I0構建0～1矩陣M如下：

M=a11a12…a1n

a21a22…a2n

am1am2…amn

式中，aij=1，aij∈Ti

0，aijTi，Ti表示第i條評論，i=1，2，3，…，m，j=1，2，3，…，n，I={I1，I2，I3，…，In}表示N個特征

圖1中文網絡產品評論挖掘的框架流程

集合。Ij在事務數據庫中出現的概率為p（Ij），計算見式（1），IJ的權重記為w（Ij），與p（Ij）有關，w（Ij）的計算公式見（2）。

p（Ij）=l/m（1）

w（Ij）=1/p（Ij）（2）

式中，l表示Ij在事務集中出現的次數，即上述矩陣中第j列中1的個數，m是評論語料的總條數。

事務Tk指數據集中的第k條評論，它的權重指該評論中所包含的特征項的平均權重，記為wt（Tk），即對aij=1的所有w（Ij）求平均值，其中j=1，2，3，…，n，計算見式（3）。

wt（Tk）=∑Ij∈Tkj=1w（Ij）/Tk（3）

式中，Tk表示評論Tk中包含的特征項的個數。

項的權重支持度記為w sup port，權重支持度表示包含特征項的事務權重占所有事務權重的比例，計算見式（4）。

w sup port（S）=∑STkk=1wt（Tk）/∑mk=1wt（Tk）（4）

式中，S表示事務數據庫中的任意特征項。

基于權重的改進Apriori算法具體步驟如下：

1）掃描事務數據庫，構建0～1事務矩陣，并根據事務矩陣計算出每個特征項和事務的權重，即w（Ij），wt（Tk）。

2）根據事務矩陣得到候選1-項集C1，計算C1中每個特征項的權重支持度w sup port（S），找出滿足最小支持度k的頻繁-項集Lk。

基于權重的改進Apriori算法流程圖如圖2所示：

22基于語義相似度聚類算法

本文首先用向量空間模型把產品特征f用向量表示，如feature（f1，f2，…，fn，o1，o2，…，om），其中fi表示產品特征詞，oj表示產品特征對應的觀點詞，通過f和fi的字符串相似度及語義相似度來衡量fi的權重，同樣的用f和oj的PMI值來衡量oi的權重。

本文以HowNet的語義相似度和特征觀點共現作為衡量產品特征之間關聯程度的特征。具體公式如下：

sim（Si，Sj）=x*simA（Si，Sj）+（1-x）*simB（Si，Sj）（5）

其中，x為對應的參數閾值，simA（Si，Sj）為特征之間基于HowNet詞典中詞語語義之間的相似度。假設有兩個特征詞S1、S2，若S1中含有m個概念：S11，S12，…，S1m，同樣的S2中含有n個概念：S21，S22，…，S2n，對于S1和S2中對應的m和n個概念進行相應的組合，計算概念間的相似度，其中得到的相似度最大值作為兩個詞語S1和S2的相似度，相應的公式如（6）所示：

simA（S1，S2）=maxe=1…m，f=1…nsim（S1e，S2f）（6）

simB（Si，Sj）為基于特征和觀點信息共現的特征相似度。將特征f表示為{O1，O2，…，On}，其中Oi為特征f的觀點信息詞，wi（S）對應為Oi的權重值，也就是觀點詞與特征詞在詞匯集中同時出現的頻次，任意兩個特征f1和f2語義相似度定義如（7）所示：

simB（S1，S2）=∑nOi∈S1，Oj∈S2wi（S1）wj（S2）sim（Oi，Oj）∑Oi∈S1wi（S1）∑Oj∈S2wj（S2）（7）

其中式（7）中，sim（Oi，Oj）表示兩個特征詞對應的觀點詞基于HowNet得出的相似度。

K-means聚類算法中最開始的一步是對初始類中心點進行選擇，其選擇的結果對下一步的聚類效果有著重要作用，而傳統的聚類算法是隨機選擇初始類中心點，本文研究聚類算法就是對初始類中心點進行改進，并且采用產品特征之間的距離作為考核度量值，考慮將距離相近的兩個特征放在同一個簇中，簇內特征盡量緊湊，最終得到的結果是各個獨立的簇。

本文算法的基本思想是首先構建一個無向賦權圖G=（V，E）；其次對初始類中心點進行選擇，過程如下：首先利用圖論中Prim算法生成最小生成樹，最小生成樹中每個節點對應的是產品特征詞，根據權重值大小選擇權重最小的K-1條邊依次刪除，最后得到K個連通子圖；接著對K個連通子圖中所有對象計算均值，并依據這些均值作為K個初始類中心點的選擇然后進行相關聚類。改進的K-means聚類算法如圖3所示：

圖3改進后的K-means算法流程圖

K-means聚類算法中還需要事先給出聚類類別K，但是一般情況下，聚類前都是不知道類別K的，本文算法中利用連通子圖個數K來作為聚類類別K。本文研究的聚類算法中，每一個產品特征對應一個簇，通過計算該特征與其他簇中的產品特征的相似度都要超過設定的閾值來進行設定算法。

3算法性能評估

31評估指標

311特征抽取評估指標

本文采用查準率P、查全率R和綜合值F-score作為特征抽取性能評估指標，具體計算方法如下：

P=AA+B（8）

R=AA+C（9）

F-score=2RPR+P（10）

A、B、C含義見表1所示：

312特征聚類評估指標

本文研究聚類算法為了驗證算法的有效性，采用Rand Statistics來評價[13]。Rand Statistics評價的具體指標如下：若特征集合L得到一個聚類結果為R={R1，R2，…，Rk}，而且對應的特征集合的劃分為C={C1，C2，…，Cs}，通過比較R與C之間的相似程度來衡量聚類算法的有效性，對于任意一對特征（li，lj）計算以下特征：

SS：li，lj在C和R中都屬于同一個類。

SD：li，lj在C中屬于同一個類，在R中不屬于同一個類。

DS：li，lj在C中不屬于同一個類，在R中屬于同一個類。

DD：li，lj在C和R中都不屬于同一個類。

用a、b、c、d來表示SS、SD、DS、DD的數目。假設a、b、c、d 4個指標之和為n，其中n為特征集中所有特征的個數，對應n=N（N-1）/2，那么R與C之間的相似程度可用如下公式來衡量：Rand Statistics=（a+b）/n，Rand Statistics的取值范圍在0～1之間，越往1靠近，表示二者之間的相似度越高，聚類有效性也就越好。

由于研究算法中閾值的選取好壞直接影響到聚類效果，因此選擇恰當的閾值，對于提高聚類效果意義重大，本文研究把評論語料作為訓練集，通過不斷調整Rand Statistics，觀察聚類效果，當Rand Statistics值達到最大值時，聚類效果最好，也把此時的值作為閾值。

32實驗數據

本文利用數據堂提供的手機評論語料（http：//www.datatang.com/data/43824）。選取其中800條作為實驗數據，對語料進行手工標注得到手機產品特征204個，如表2所示：

通過前面對中文網絡產品評論進行產品特征提取、優化過濾后得到產品評論的特征集合。針對此集合，采用人工標注的方法對產品評論對象進行人工標注，得到產品特征集。

33實驗結果與分析

331特征提取結果分析

在用基于權重的改進Apriori算法進行頻繁項挖掘，在考慮噪聲的情況下，為使抽取出來的特征更加全面，本文多次對特征維度進行改變，得到的特征維度變化以及抽取出來的正確特征數（查全率）變化見表3：

根據表3可知，將特征維度選取為1900最佳。再根據中文產品特征規則進一步過濾特征集合，最后利用PMI算法進行最終過濾，提取出最優部分特征結果如表4所示：

對PMI設置不同的閾值，性能變化如圖4所示：

通過以上實驗結果可知，結合基于權重的改進Apriori算法與PMI算法進行特征提取時，當PMI值為-5時，挖掘結果綜合性能最優，查準率達到69%，查全率達到9264%，綜合值達到7907%。

332特征聚類結果分析

1）評估結果

首先對中文網絡產品進行產品特征提取并進行過濾優化后，利用公式（7）的點互信息公式計算特征之間的相似度，然后進行聚類算法，在算法中選擇Rand Statistics值最大時作為最后選擇閾值，選擇閾值如表6所示，從表中可以看出當閾值的值為045時，對應的Rand Statistics最高，為8675%，而此時對應的聚類效果也最好。針對于不同的閾值，對Rand Statistics變化情況如圖5所示。

3）對比分析

對于手機評論的產品特征挖掘，通過實驗分析，本文所提出的方法與K-means方法在性能指標上的比較結果如圖6所示。

4結語

用戶評論中蘊含了大量有價值的信息，識別出用戶關注的產品特征并將產品信息按照特征進行組織至關重要。

本文專注于解決用戶評論中產品特征的提取及聚類問題，首次采用基于矩陣與權重的改進Apriori算法進行頻繁項挖掘，然后利用基于網絡搜索引擎的PMI算法進行過濾形成最優特征集合。最后采用改進的聚類算法對所提取的產品特征進行聚類。通過使用本文的挖掘方法進行實驗，取得了較好的效果。可以滿足不同用戶的信息需求，幫助潛在的消費者做出購買決策，也可以為生產商的產品改進提供有價值的反饋信息，為其提供決策支持。今后也將結合更多機器學習算法對評論文本中的情感傾向性進行相關研究。

參考文獻

[1]Zhuang L，Jing F，Zhu X Y.Movie Review Mining and Summarization[C].In：Proceedings of the 15th ACM International Conference on Information and Knowledge Management （CIKM06），Arlington，Virginia，USA.New York：ACM，2006：43-50.

[2]Kobayashi N，Inui K，Matsumoto Y.Collecting Evaluative Expressions for Opinion Extraction[C].In：Proceedings of the 1st International Joint Conference on Natural Language Processing（IJCNLP04）.Berlin，Heidelberg：Springer-Verlag，2004：596-605.

[3]婁德成，姚天防.漢語句子語義極性分析和觀點抽取方法的研究[J].計算機應用，2006，26（11）：2622-2625.

[4]Hu M，Liu B.Mining Opinion Features in Customer Reviews[C].In AAAI，2004：755-760.

[5]Popescu A M，Etzioni O.Extracting Product Features and Opinions From Reviews[C].In Proceedings of HLT-EMNLP 2005，ACL，2005：339-346.

[6]Guo H，Zhu H，Guo Z，et al.Product Feature Categorization with Multilevel Latent Sentiment Association.In：Proceedings of CIKM，2009：1087-1096.

[7]Zhai Zhongwu，Liu Bing，Xu Hua，et al.Groupting Features Using Semi-Supervised Learning with Soft-Constrains.Proceeding of the 23rd International Conference on Computational Linguistics （COLING-2010），2010：1272-1280.

[8]楊源，馬云龍，林鴻飛.評論挖掘中產品屬性歸類問題研究[J].中文信息學報，2012，26（3）：104-108.

[9]扈中凱，鄭小林，吳亞峰，等.基于用戶評論挖掘的產品推薦算法[J].浙江大學學報：工學版，2013，47（8）：1475-1485.

[10]邊根慶，王月.一種基于矩陣和權重改進的Apriori算法[J].微電子學與計算機，2017，（1）：136-140.

[11]王永，張勤，楊曉潔.中文網絡評論中產品特征提取方法研究[J].現代圖書情報技術，2013，（12）：70-73.

[12]江波，張黎.基于Prim算法的最小生成樹優化研究[J].計算機工程與設計，2009，30（13）：3244-3247.

[13]Halkidi M，Batistakis Y，Vazirgiannis M.On Clustering Validation Techniques[J]. Journal of Intelligent Information Systems，2001，17（2-3）：107-145.

（實習編輯：陳媛）