梁睿博 王思遠(yuǎn) 李壯 劉亞松

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

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

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

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

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

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

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

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

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

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

3? 基于RAKEL算法的商品評(píng)論多標(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)的分類器。對(duì)于新實(shí)例的多標(biāo)簽分類，每個(gè)分類器為每個(gè)標(biāo)簽提供二元決策，隨后計(jì)算每個(gè)標(biāo)簽的平均決策，如果平均值大于用戶指定的閾值則輸出最終的肯定決策。RAKEL算法對(duì)于標(biāo)簽子集的擇是隨機(jī)的，沒有充分利用標(biāo)簽相關(guān)性，對(duì)最終的分類結(jié)果產(chǎn)生巨大影響。本文從這一角度展開，利用標(biāo)簽間的相關(guān)性來(lái)確定標(biāo)簽間的關(guān)系，提出了FI-RAKEL算法。

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

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

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

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

輸入：模型數(shù)目，頻繁項(xiàng)集最小支持度，子集大小，標(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? ?實(shí)驗(yàn)與結(jié)果分析（Experiment and analysis）

4.1? ?實(shí)驗(yàn)方法

4.1.1? ?實(shí)驗(yàn)數(shù)據(jù)集

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

4.1.2? ?評(píng)價(jià)指標(biāo)

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

①Subset-Accuracy

（1）

②Recall

（2）

③F-Measure

（3）

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

4.2? ?實(shí)驗(yàn)結(jié)果和分析

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

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

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

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

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

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

參考文獻(xiàn)（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] 張洛陽(yáng)，毛嘉莉，劉斌，等.基于貝葉斯模型的多標(biāo)簽分類算法[J].計(jì)算機(jī)應(yīng)用，2016（1）：52-56;71.

[5] 徐婧揚(yáng).多標(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] 金永賢，張微微，周恩波.一種改進(jìn)的RAKEL多標(biāo)簽分類算法[J].浙江師范大學(xué)學(xué)報(bào)（自然科學(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] 周恩波，葉榮華，張微微，等.一種基于成對(duì)標(biāo)簽的Rakel算法改進(jìn)[J].計(jì)算機(jī)與現(xiàn)代化，2016（3）：16-18;23.

[14] 呂小勇，石洪波.基于頻繁項(xiàng)集的多標(biāo)簽文本分類算法[J].計(jì)算機(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.