梁睿博 王思遠 李壯 劉亞松

摘? 要：商品通常包含多個屬性維度，準(zhǔn)確找到商品評論中涉及的屬性維度是文本挖掘工作的基礎(chǔ)。RAKEL算法是多標(biāo)簽分類中問題轉(zhuǎn)換思路的一種實現(xiàn)。在以往的工作中，由于子標(biāo)簽集合的隨機性，沒有充分發(fā)現(xiàn)和考慮標(biāo)簽之間的相關(guān)性，導(dǎo)致分類精度不高。為此，提出了改進的FI-RAKEL算法。首先通過FP-Growth算法得到標(biāo)簽的頻繁項集，再從頻繁項集和原始標(biāo)簽集合中選擇標(biāo)簽構(gòu)成新的標(biāo)簽子集，以此充分利用標(biāo)簽相關(guān)性訓(xùn)練基分類器。實驗證明，改進的FI-RAKEL算法具有更好的評論文本多標(biāo)簽分類性能。

關(guān)鍵詞：多標(biāo)簽分類;RAKEL;頻繁項集;標(biāo)簽相關(guān)性

中圖分類號：TP391? ? ?文獻標(biāo)識碼：A

Research and Implementation of RAKEL Algorithm Based Multi-Label

Classification for Online Commodity Reviews

LIANG Ruibo，WANG Siyuan，LI Zhuang，LIU Yasong

（School of Computer Science and Engineering，Northeastern University，Shenyang 110819，China）

Abstract：Generally，there are multiple attribute-dimensions to describe a commodity.It is the foundation of text mining to accurately find the attribute-dimensions involved in commodity reviews.The Random K-Labelsets （RAKEL） is an accomplishment of problem transformation in multi-label classification.However，due to the randomness of sub-labelset and the lack of investigating into the relationship among labels，the classification accuracy of RAKEL is not high.Hence，an improved RAKEL algorithm （FI-RAKEL） is proposed.Firstly，the item-frequency sets of labels are obtained through the FP-Growth algorithm.Then，labels are selected from the item-frequency sets and the original label set respectively to generate a new k-labelset and it is used to train the corresponding classifier based on correlation among labels.The experiment result shows that the proposed FI-RAKEL algorithm brings higher classification accuracy for multiple-labeled reviews.

Keywords：multi-label classification;RAKEL;item-frequency set;label correlation

1? ?引言（Introduction）

近些年，網(wǎng)購成為了人們?nèi)粘ＯM的主要方式。由此，各大電商平臺上積累了海量的用戶購物評論數(shù)據(jù)，其中蘊藏著巨大的商業(yè)價值。一方面，用戶評論是企業(yè)和商家了解市場反饋的重要渠道;同時，對于消費者而言，參考其他人發(fā)表的評論也有助于快速地選擇理想的商品。通常，一種商品會包含多個屬性維度，用戶針對某個商品發(fā)表的評論也會涉及商品的多個方面。因此，對商品評論進行文本挖掘時，準(zhǔn)確找到評論中涉及的屬性維度是整個文本挖掘工作的基礎(chǔ)。針對商品評論數(shù)據(jù)集，多標(biāo)簽分類算法是首要考慮的問題。

多標(biāo)簽分類算法主要研究當(dāng)樣本同時具有多個類別標(biāo)記時，如何構(gòu)建分類器，準(zhǔn)確預(yù)測未知樣本的標(biāo)簽集合[1]。本文首先從京東商城等電商平臺按品類獲取了商品評論，并對這些評論進行人工標(biāo)注。按照標(biāo)簽對商品評論文本進行統(tǒng)計后發(fā)現(xiàn)，一些標(biāo)簽之間具有較高的相關(guān)性，例如，表1列舉的洗發(fā)水商品的評論R1-R6。從表1中可以看出，“快遞”和“購物渠道”這兩個標(biāo)簽在同一條用戶發(fā)表的評論文本中共現(xiàn)（被同時提及）的比例較高，我們可以認為這兩個標(biāo)簽具有一定的相關(guān)性。導(dǎo)致這一現(xiàn)象的原因是，當(dāng)“購物渠道”為電商平臺時，用戶必然會接受快遞服務(wù)，因此兩者的共現(xiàn)概率較高。而在實際應(yīng)用中，標(biāo)簽之間是存在一定聯(lián)系的。本文以標(biāo)簽相關(guān)性為基礎(chǔ)，參考近年來基于標(biāo)簽相關(guān)性的多標(biāo)簽分類算法，提出了基于頻繁項集的改進RAKEL算法FI-RAKEL。首先，通過頻繁項集挖掘標(biāo)簽之間的關(guān)聯(lián)關(guān)系，選取頻繁項集的元素作為RAKEL算法的標(biāo)簽子集，從而利用標(biāo)簽間的相關(guān)性提高預(yù)測分類的精確度和整體性能。

2? ?相關(guān)工作（Related work）

多標(biāo)簽學(xué)習(xí)的研究，起源于2000年的Schapire等提出的基于boost方法的文本多分類，著名的學(xué)者Tsoumakas、Jesse Read等從事過相關(guān)研究。解決多標(biāo)簽分類問題主要有兩種思路：算法適應(yīng)和問題轉(zhuǎn)換[2-4]。問題轉(zhuǎn)換法通過對樣本集合進行分解，達到把多標(biāo)簽學(xué)習(xí)問題轉(zhuǎn)換為多個單標(biāo)簽學(xué)習(xí)問題的目的。該方法具有簡化性，并且在大多數(shù)據(jù)集上應(yīng)用良好[5]，也是本文主要采用的方法。

問題轉(zhuǎn)換算法中經(jīng)典的方法有BR（Binary Relevance）、CC（Classifier Chains）和LP（Label Powset）等。其中BR算法是一階方法，將多標(biāo)簽學(xué)習(xí)問題分解為多個獨立的二元分類問題，該方法完全忽略了標(biāo)簽之間的潛在相關(guān)性。在BR的基礎(chǔ)上，Jesse Read等[6]人提出了Classifier Chains算法，將多標(biāo)簽學(xué)習(xí)問題轉(zhuǎn)化為二元分類問題鏈，鏈中的后續(xù)二元分類器基于前面的分類器進行預(yù)測[7]。分類器鏈具有開發(fā)標(biāo)簽相關(guān)性的優(yōu)點，但由于其鏈接屬性而無法實現(xiàn)并行。研究者還根據(jù)BR、CC等思想提出了Ensemble的框架[8]，提出了EBR、ECC等算法，這些算法也表現(xiàn)出了很好的性能。

另一種常見的問題轉(zhuǎn)換思路是創(chuàng)建新標(biāo)記，其中LP算法是將每個多標(biāo)簽實例的所屬標(biāo)簽聯(lián)合起來創(chuàng)建新的標(biāo)簽，但是這樣做會大大增加標(biāo)簽數(shù)量，增加計算開銷。后來的研究者們在LP思想的基礎(chǔ)上提出了Pruned Problem Transformation（PPT）算法[9]和Random k-labelsets（RAKEL）算法，以及一些RAKEL改進算法[10-13]。RAKEL的基本思想是將多標(biāo)簽學(xué)習(xí)問題轉(zhuǎn)化為多類分類問題的集合，從標(biāo)簽集合中隨機選出小部分標(biāo)簽子集，在這個子集的多分類分類器上引入Label Powerset（LP）技術(shù)。RAKEL是一個高階方法，其中標(biāo)簽相關(guān)度由k-labelsets的大小來控制，避免了LP的缺陷。但是正因為標(biāo)簽子集的隨機選擇，對標(biāo)簽之間的相互聯(lián)系考慮不足，從而導(dǎo)致分類的精確度不高。對此，研究者分別做出了不同的改進。文獻[10]提出的RAKEL改進算法LC-RAKEL，核心思想是通過聚類來選取標(biāo)簽子集。對隨機選擇的k個標(biāo)簽進行聚類，從每個聚類的標(biāo)簽簇中選取一個標(biāo)簽形成標(biāo)簽子集，通過訓(xùn)練可以得到分類精度較高的子分類器。但當(dāng)標(biāo)簽數(shù)目較少并且相關(guān)度較高時，聚類效果不理想。文獻[13]提出一種基于成對標(biāo)簽的RAKEL改進算法PwRAKEL。該方法考察任兩個標(biāo)簽的共現(xiàn)性，利用生成的共現(xiàn)矩陣選擇共現(xiàn)度高的成對標(biāo)簽加入標(biāo)簽子集，提高標(biāo)簽之間的相關(guān)關(guān)系來提升子分類器的模型預(yù)測精度。這種方法只考慮了每兩個標(biāo)簽間的相關(guān)關(guān)系，沒有將更多標(biāo)簽相互關(guān)聯(lián)的情形充分利用。

還有一些學(xué)者進行了基于頻繁項集的多標(biāo)簽分類算法改進[14，15]。文獻[15]提出了一種基于頻繁項集的多標(biāo)簽文本分類算法MLFI，利用FP-growth算法挖掘類別之間的頻繁項集，同時為每個類計算類標(biāo)準(zhǔn)向量和相似度閾值，如果文本與類標(biāo)準(zhǔn)向量的相似度大于相應(yīng)閾值則歸到相應(yīng)的類別，在分類結(jié)束后利用挖掘到的類別之間的關(guān)聯(lián)規(guī)則對分類結(jié)果進行校驗。該方法主要針對文檔進行類別劃分，不適用于商品評論的短文本多標(biāo)簽分類問題。

基于以上的相關(guān)工作，本文針對商品評論提出一種改進的多標(biāo)簽分類方法FI-RAKEL。首先對標(biāo)簽之間相關(guān)性進行頻繁模式挖掘，選取頻繁項集作為RAKEL算法的標(biāo)簽子集，充分利用標(biāo)簽相關(guān)性來訓(xùn)練子分類器，提升分類器的預(yù)測分類精度，實現(xiàn)RAKEL算法的改進。

3? 基于RAKEL算法的商品評論多標(biāo)簽分類算法

（Algorithm of RAKEL algorithm based multi-label

classification for online commodity reviews）

Tsoumakas等提出的Random k-Labelsets將集成學(xué)習(xí)與LP結(jié)合，將原始大標(biāo)簽集分成小標(biāo)簽集，使用LP技術(shù)訓(xùn)練相應(yīng)的分類器。對于新實例的多標(biāo)簽分類，每個分類器為每個標(biāo)簽提供二元決策，隨后計算每個標(biāo)簽的平均決策，如果平均值大于用戶指定的閾值則輸出最終的肯定決策。RAKEL算法對于標(biāo)簽子集的擇是隨機的，沒有充分利用標(biāo)簽相關(guān)性，對最終的分類結(jié)果產(chǎn)生巨大影響。本文從這一角度展開，利用標(biāo)簽間的相關(guān)性來確定標(biāo)簽間的關(guān)系，提出了FI-RAKEL算法。

首先采用FP-Growth算法實現(xiàn)標(biāo)簽間的關(guān)聯(lián)關(guān)系的挖掘，得到標(biāo)簽的頻繁項集。FP-Growth算法對數(shù)據(jù)集進行掃描，得到標(biāo)簽的頻繁項列表并對頻繁項進行支持度遞減的排序，我們設(shè)定最小支持度，認為小于值的項為非頻繁項，從而去除其中的非頻繁項;第二次掃描構(gòu)造一棵FP-Tree[15]，F(xiàn)P-Tree是從上至下發(fā)散的層次樹，越是上層的點表示出現(xiàn)越頻繁。從FP-Tree中提取頻繁項，得到標(biāo)簽的頻繁項集。不同下頻繁項集輸出結(jié)果如表2所示，在FI-RAKEL算法中頻繁項集的項數(shù)n的取值范圍是?；诘玫降念l繁項集構(gòu)造RAKEL算法的標(biāo)簽子集，從頻繁項集中選取一個頻繁項和原始標(biāo)簽集合中的部分標(biāo)簽作為標(biāo)簽子集來訓(xùn)練分類器，最后實現(xiàn)預(yù)測分類。

為了更好地描述算法，首先引入一些相關(guān)定義：令代表多標(biāo)簽分類域中的標(biāo)簽集合，大小為。集合并且，則稱為。在此，使用表示上所有不同的集合，為訓(xùn)練數(shù)據(jù)集。

首先在數(shù)據(jù)集上通過FP-Growth算法生成標(biāo)簽的頻繁項集，然后迭代構(gòu)造個LP分類器的集合。在每次迭代中即，分別從頻繁項集中拿出第個頻繁項和中隨機選擇（）個不重復(fù)的標(biāo)簽構(gòu)成標(biāo)簽子集，訓(xùn)練子分類器。對于新實例，每個模型為相應(yīng)k標(biāo)簽集中的每個標(biāo)簽提供二元決策，每個標(biāo)簽的平均決策，如果平均值大于用戶指定的閾值，則輸出最終的肯定決策。FI-RAKEL算法模型訓(xùn)練過程如算法1。

算法1 FI-RAKEL模型訓(xùn)練算法

輸入：模型數(shù)目，頻繁項集最小支持度，子集大小，標(biāo)簽集合，訓(xùn)練集，空集

輸出：LP分類器，相應(yīng)的

i-th frequent item? of labels selected from + （） labels randomly selected from? not in

else

endif

else

repeat 3 to 12

endif

endfor

4? ?實驗與結(jié)果分析（Experiment and analysis）

4.1? ?實驗方法

4.1.1? ?實驗數(shù)據(jù)集

本文以京東商城和天貓商城作為數(shù)據(jù)源，獲取其中洗發(fā)水商品評論。選取50萬條洗發(fā)水商品評論，進行人工屬性維度的標(biāo)注，以領(lǐng)域?qū)＜抑付ǖ?0個商品維度作為標(biāo)簽，包括“質(zhì)量”“產(chǎn)品功效”“香味”“質(zhì)地”“包裝”“性價比”“品牌”“購物渠道”“快遞”和“方便性”，以此作為實驗的訓(xùn)練集和測試集。在計算測試集相對訓(xùn)練集占比時，從數(shù)據(jù)集中隨機抽取數(shù)據(jù)作為測試集，其余作為訓(xùn)練集，得到測試集大小與訓(xùn)練集大小比例。

4.1.2? ?評價指標(biāo)

根據(jù)文獻[2]，本文從幾個方面對多標(biāo)簽分類算法進行評估分析：Subset-Accuracy、Recall和F-Measure，定義如式（1）—式（3）。

①Subset-Accuracy

（1）

②Recall

（2）

③F-Measure

（3）

其中，表示實驗的測試集大小，式（1）中的取值分別為和，Subset-Accuracy評估正確分類例子的分?jǐn)?shù)，即預(yù)測標(biāo)簽集合與實況標(biāo)簽集合的相同程度。式（3）中F-Measure是衡量算法整體性能的基本指標(biāo)。

4.2? ?實驗結(jié)果和分析

基于4.1.1中的商品評論數(shù)據(jù)集，本文對FI-RAKEL算法進行驗證并與其他RAKEL改進算法進行對比實驗，參考4.1.2中的評價指標(biāo)。

首先針對本文提出的FI-RAKEL算法進行實驗，F(xiàn)I-RAKEL算法采用的基分類器為LP分類器，LP的基分類器選擇SVM分類算法，標(biāo)簽子集大小為，模型個數(shù)，預(yù)測分類中閾值。我們選取不同的頻繁項集最小支持度進行對比實驗，其中訓(xùn)練集相對數(shù)據(jù)集的占比為0.8，使用Subset-Accuracy作為評價指標(biāo)。同時，我們在所有實驗過程中選擇三次交叉驗證，即測試集相對訓(xùn)練集占比一定時，進行三次測試集的隨機抽取，得到多個結(jié)果的平均值。實驗結(jié)果如圖1所示。

從圖1我們可以看出當(dāng)取值范圍在時，F(xiàn)I-RAKEL算法分類精度最高。我們又以0.01為間距進行實驗，發(fā)現(xiàn)時算法取得最好的分類精確度。隨后我們選擇REKAL算法和文獻[13]提出的PwRAKEL與本文算法進行對比實驗，基分類器為LP分類器，LP的基分類器同樣使用SVM分類算法，算法取標(biāo)簽子集大小為，模型個數(shù)，預(yù)測分類中閾值。對FI-RAKEL算法最小支持度取值為。實驗結(jié)果如圖2所示。

通過分析實驗結(jié)果我們發(fā)現(xiàn)，當(dāng)測試集相對訓(xùn)練集占比增加時算法性能趨優(yōu)。如圖2所示，當(dāng)測試集與訓(xùn)練集比例為0.9時，F(xiàn)I-RAKEL算法在分類準(zhǔn)確率、召回率和F值等評價指標(biāo)上有非常明顯的優(yōu)勢。相較于RAKEL算法，F(xiàn)I-RAKEL有更高的分類準(zhǔn)確率召回率和F1值，這說明本文提出的基于頻繁項集構(gòu)建標(biāo)簽子集的思想能夠有效利用標(biāo)簽相關(guān)性提升子分類器的訓(xùn)練和預(yù)測分類精度。

5? ?結(jié)論（Conclusion）

在多標(biāo)簽分類問題上，RAKEL算法由于標(biāo)簽子集選擇的隨機性，沒有充分利用標(biāo)簽間的相關(guān)性來改善算法的性能。針對商品評論文本挖掘這一領(lǐng)域，本文提出了一種基于頻繁項集的RAKEL改進算法FI-RAKEL，并與RAKEL算法和PwRAKEL算法進行對比，實驗結(jié)果表明FI-RAKEL算法性能更好，具有更高的分類準(zhǔn)確性、召回率和F值。雖然本文算法在性能上有些優(yōu)勢，但在實現(xiàn)本文過程中發(fā)現(xiàn)生成了大量新標(biāo)簽組合，其中有些標(biāo)簽組合在結(jié)果中出現(xiàn)頻率較低造成了資源浪費，因此如何更合理利用標(biāo)簽相關(guān)性，過濾低頻率標(biāo)簽組合并找到隱藏相關(guān)標(biāo)簽，減少資源浪費和運行時間是下一步值得思考的。

參考文獻（References）

[1] G.Tsoumakas，I.Katakis，and I.Vlahavas，Random k-labelsets for multi-label classification，IEEE Trans.Knowl.Data Eng.，2011，23（7）：1079-1089.

[2] Padmanabhan Divya，Bhat Satyanath，Shevade Shirish，Narahari Y.Topic Model Based Multi-Label Classification.2016 IEEE 28th International Conference on Tools with Artificial Intelligence，Nov 2016：996-1003.

[3] Huang Jun，Li Guorong，Huang Qingming，et al.Learning Label Specific Features for Multi-label Classification.2015 IEEE International Conference on Data Mining，2015（11）：181-190.

[4] 張洛陽，毛嘉莉，劉斌，等.基于貝葉斯模型的多標(biāo)簽分類算法[J].計算機應(yīng)用，2016（1）：52-56;71.

[5] 徐婧揚.多標(biāo)簽分類算法研究及其應(yīng)用[D].山東大學(xué)，2017.

[6] Read Jesse，Martino Luca，Luengo.Efficient monte carlo methods for multi-dimensional learning with classifier chains.Pattern Recognition，March 2014，47（3）：1535-1546.

[7] Yu Zhilou，Hao Hong，Zhang Weipin.A Classifier Chain Algorithm with K-means for Multi-label Classification on Clouds.Journal of Signal Processing Systems，2017，86（2）：337-346.

[8] Rokach Lior，Schclar Alon，Itach Ehud.Ensemble methods for multi-label classification.Expert Systems With Applications，November 2014（41）：7507-7523.

[9] Read J.A pruned problem transformation method for multi-label classification[C].Proceeding of New Zealand Computer Science Research Student Conference.Christchurch：Canterbury University，2008：143-150.

[10] 金永賢，張微微，周恩波.一種改進的RAKEL多標(biāo)簽分類算法[J].浙江師范大學(xué)學(xué)報（自然科學(xué)版），2016，39（4）：386-391.

[11] Wu Yu-Ping，Lin Hsuan-Tien.Progressive random k-labelsets for cost-sensitive multi-label classification.Machine Learning，2017，106（5）：671-694.

[12] Osojnik，Alja?，Panov.Multi-label classification via multi-target regression on data streams.Machine Learning，2017，106（6）：745-770.

[13] 周恩波，葉榮華，張微微，等.一種基于成對標(biāo)簽的Rakel算法改進[J].計算機與現(xiàn)代化，2016（3）：16-18;23.

[14] 呂小勇，石洪波.基于頻繁項集的多標(biāo)簽文本分類算法[J].計算機工程，2010（15）：83-85.

[15] Jiawei Han，Jian Pei，Yiwen Yin.Mining Frequent Patterns without Candidate Generation：A Frequent-Pattern Tree Approach[J].Data Mining and Knowledge Discovery，2004（8）：53-87.