融合樸素貝葉斯與決策樹的用戶評(píng)論分類算法

賈曉帆，何利力

（浙江理工大學(xué) 信息學(xué)院，浙江杭州 310018）

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，為了滿足用戶需求，出現(xiàn)了網(wǎng)頁、軟件、手機(jī)應(yīng)用等互聯(lián)網(wǎng)產(chǎn)品，還包括建立在各類平臺(tái)上而開發(fā)出的產(chǎn)品，如微信小程序、公眾號(hào)等。用戶在互聯(lián)網(wǎng)中發(fā)表對(duì)產(chǎn)品的評(píng)價(jià)這一舉動(dòng)讓用戶從單一的信息接受者轉(zhuǎn)變?yōu)榛ヂ?lián)網(wǎng)中文本信息的發(fā)布者，文本信息量呈指數(shù)級(jí)增長，僅僅由人工進(jìn)行分析提取幾乎不大可能，如何有效管理并充分利用這些信息值得思考。

樸素貝葉斯是機(jī)器學(xué)習(xí)的一個(gè)常用分類模型，模型本身是建立在貝葉斯定理和特征條件獨(dú)立假設(shè)上的，有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，用概率統(tǒng)計(jì)知識(shí)對(duì)樣本數(shù)據(jù)集進(jìn)行分類。1990 年，Kononenko 等［1］證明了樸素貝葉斯的有效性。樸素貝葉斯的優(yōu)勢在于能夠很快地在訓(xùn)練集中建立起貝葉斯模型，但是在有些實(shí)際應(yīng)用中分類效果卻不盡如人意。因?yàn)樵谟秘惾~斯分類的前提下，必須假設(shè)屬性獨(dú)立，即屬性之間沒有關(guān)系，當(dāng)該假設(shè)不成立時(shí)，就會(huì)影響貝葉斯分類效果。為了解決該問題，學(xué)者們放松屬性之間相互獨(dú)立的條件假設(shè)，提出了貝葉斯網(wǎng)絡(luò)分類器［2］，其基本思想是考慮全部或者部分屬性之間的關(guān)聯(lián)性，以此滿足樸素貝葉斯模型相互獨(dú)立的條件假設(shè)。盡管這種思想能提高分類性能，但是在訓(xùn)練中需要測算所有屬性之間的相關(guān)性，導(dǎo)致算法復(fù)雜度劇增。1996 年，Sahami［3］提出K-依賴貝葉斯分類器，有效提升了分類性能；1997 年，F(xiàn)riedman 等［4］提出了一種樹擴(kuò)展的樸素貝葉斯分類器，簡稱TAN 模型，它在測算屬性之間相關(guān)性的基礎(chǔ)上，構(gòu)建樹形結(jié)構(gòu)圖；1999 年，Nurnberger 等［5］提出了基于神經(jīng)模糊的樸素貝葉斯分類器，簡稱BAN 模型，它是TAN 模型的升級(jí)版，相比TAN 模型，允許特征屬性之間形成有向結(jié)構(gòu)圖；2004 年，Wang 等［6］提出基于自適應(yīng)的Boosting 與樸素貝葉斯結(jié)合方法，可以有效地緩解噪聲提高分類性能；2008 年，徐光美等［7］通過基于互信息計(jì)算各屬性與各類別之間的相關(guān)性，選擇不相關(guān)的特征值代入樸素貝葉斯模型中；2011 年，Zheng 等［8］通過刪除一部分相關(guān)性強(qiáng)的特征屬性，將處理后的特征屬性應(yīng)用于樸素貝葉斯分類模型；2014 年，杜選［9］提出一種基于加權(quán)補(bǔ)集的樸素貝葉斯文本分類模型，這種模型可避免在訓(xùn)練集不平衡時(shí)，可能導(dǎo)致分類性能低的缺陷。

本文在研究樸素貝葉斯算法的基礎(chǔ)上提出一種與決策樹相融合的算法，使用本文算法可以有效填補(bǔ)數(shù)據(jù)集中的缺失屬性值。實(shí)驗(yàn)結(jié)果證明，本文算法的分類效果比傳統(tǒng)樸素貝葉斯分類效果更好。

1 理論基礎(chǔ)

1.1 Laplace 方法

Laplace 是最古老的平滑技術(shù)之一，所謂平滑技術(shù)是指為了產(chǎn)生更理想的概率以調(diào)整最大似然估計(jì)的技術(shù)［10-11］。計(jì)算公式如下：

其中，N 為訓(xùn)練實(shí)例總數(shù)量；T 為訓(xùn)練集實(shí)例種類數(shù)。在Laplace 估計(jì)中，先驗(yàn)概率P（Y）被定義如下：

其中,nc是滿足Y={yj} 的實(shí)例個(gè)數(shù)，N 是訓(xùn)練集個(gè)數(shù)，n是類的個(gè)數(shù)，并且k=1。

1.2 樸素貝葉斯

樸素貝葉斯分類（NBC）是一種假設(shè)特征與特征之間相互獨(dú)立的算法，它基于貝葉斯定理，算法邏輯穩(wěn)定且簡單，樸素貝葉斯的健壯性較好，其分類功能在數(shù)據(jù)展現(xiàn)出不同特點(diǎn)時(shí)，差別不大，也即在不同類型的數(shù)據(jù)集中不會(huì)表現(xiàn)出太大差異［12］。因此，當(dāng)數(shù)據(jù)集屬性之間的關(guān)系相對(duì)獨(dú)立時(shí)，樸素貝葉斯分類算法會(huì)有較好的效用。

（1）貝葉斯定理。根據(jù)條件概率可知，事件A 在事件B已發(fā)生的條件下發(fā)生概率為：

同樣地，在事件A 已發(fā)生條件下事件B 發(fā)生的概率為：

結(jié)合兩個(gè)方程式可以得到：

上式兩邊同除以P（A），若P（A）為非零，可以得到貝葉斯定理：

（2）樸素貝葉斯定理。設(shè)有樣本數(shù)據(jù)集D={d1,d2,…,dn}，對(duì)應(yīng)樣本數(shù)據(jù)的特征屬性集為X={x1,x2,…,xd}，有類別集合Y={y1,y2,…,ym}，即D可以分為ym類別。其中x1,x2,…,xd相互獨(dú)立且隨機(jī)，則Y的先驗(yàn)概率P=P(Y)，Y的后驗(yàn)概率P=P(Y|X)，由樸素貝葉斯算法可得后驗(yàn)概率為：

樸素貝葉斯基于各特征之間相互獨(dú)立，在給定類別為y的情況下，式（6）可以進(jìn)一步表示為：

由式（7）可計(jì)算出后驗(yàn)概率為：

由于P(X)的大小固定不變，因此在比較后驗(yàn)概率時(shí)，只比較式（8）的分子部分即可。因此，可以得到一個(gè)樣本數(shù)據(jù)屬于類別yi的樸素貝葉斯計(jì)算公式如下：

1.3 決策樹

決策樹是一種包含根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)、葉節(jié)點(diǎn)3 種節(jié)點(diǎn)的樹型結(jié)構(gòu)。當(dāng)文本分類算法為決策樹時(shí)，它由樹的內(nèi)部節(jié)點(diǎn)逐一標(biāo)注所構(gòu)成，葉節(jié)點(diǎn)表示對(duì)應(yīng)的類別標(biāo)簽，與葉節(jié)點(diǎn)相連的分支上標(biāo)注著其對(duì)應(yīng)的權(quán)重，樹的葉子節(jié)點(diǎn)表示文本分類目標(biāo)，當(dāng)從根開始遍歷查詢最終到達(dá)某一個(gè)葉子節(jié)點(diǎn)，這樣就完成了一次文本分類［13］，樹的高度就是時(shí)間復(fù)雜度，它是一個(gè)自頂向下、分而治之的總過程。決策樹的準(zhǔn)確率會(huì)因重復(fù)的屬性而受一定影響，因而用決策樹進(jìn)行分類是要對(duì)數(shù)據(jù)進(jìn)行特征選擇。決策樹在開始階段會(huì)浪費(fèi)時(shí)間，但只要模型建立起來，運(yùn)用階段非?？臁?/p>

決策樹算法是一種無監(jiān)督分類方法，決策樹的生成主要分為節(jié)點(diǎn)分裂和閾值確定，節(jié)點(diǎn)分裂指當(dāng)一個(gè)節(jié)點(diǎn)所代表的屬性無法判斷時(shí)，則選擇將一節(jié)點(diǎn)分為多個(gè)子節(jié)點(diǎn)，而選擇適當(dāng)?shù)拈撝悼梢允狗诸愬e(cuò)誤率最小。決策樹以樹的層次規(guī)則為特征，葉子節(jié)點(diǎn)為分類目標(biāo)，通過遍歷根節(jié)點(diǎn)到葉子節(jié)點(diǎn)完成一次分類操作。決策樹分類算法與其他決策支持工具相比較起來易于理解和解釋。然而，通過有限的數(shù)據(jù)集無法訓(xùn)練出可靠的類標(biāo)簽，并且對(duì)特征空間計(jì)算成本非常高，這對(duì)決策樹而言是一種限制［13］。決策樹算法作為一種常見分類算法，有很多變種，包括ID3、C4.5、C5.0、CART 等。其中，最常用的、最經(jīng)典的是C4.5 算法。

2 改進(jìn)思想

2.1 樸素貝葉斯概率優(yōu)化

樸素貝葉斯的概率估計(jì)會(huì)在訓(xùn)練樣本不足時(shí)出現(xiàn)零概率的問題，這會(huì)導(dǎo)致求出的類標(biāo)簽的后驗(yàn)概率值為零，使用連乘計(jì)算文本出現(xiàn)概率時(shí)也是零，傳統(tǒng)的樸素貝葉斯在這種情況下無法進(jìn)行分類，這一直以來都是樸素貝葉斯的難題。為了解決該問題，法國的數(shù)學(xué)家拉普拉斯（Lapla?cian）首次提出一種加法平滑方法，對(duì)每個(gè)詞的計(jì)數(shù)加1，該加法平滑也叫拉普拉斯平滑。該方法基于一定的數(shù)學(xué)理論基礎(chǔ)，在數(shù)據(jù)集較大的情況下，每一個(gè)詞出現(xiàn)的次數(shù)加1之后對(duì)概率估計(jì)結(jié)果的影響可完全忽略不計(jì)，但是卻可以有效地避免出現(xiàn)零概率問題。針對(duì)本實(shí)驗(yàn)所采取的樸素貝葉斯模型，采用詞頻估算每一個(gè)特征，其經(jīng)過拉普拉斯平滑方法處理后的表達(dá)式為：

2.2 樸素貝葉斯與決策樹融合

為了提高貝葉斯分類準(zhǔn)確性，在提出的貝葉斯與其他方法相結(jié)合的算法中，最為代表的是Kohavi［14］提出的NB?Tree 算法。對(duì)于大型數(shù)據(jù)分類，決策樹和樸素貝葉斯相比，前者在維度較大或者屬性之間的依賴關(guān)系明顯優(yōu)于后者，后者的分類結(jié)果準(zhǔn)確性優(yōu)于前者。而NBTree 算法剛好結(jié)合貝葉斯和決策樹各自的優(yōu)點(diǎn)，提升了算法效率。

C4.5 算法的優(yōu)點(diǎn)是產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高，C4.5 經(jīng)過樹生成和樹剪枝建立決策樹。在計(jì)算每個(gè)屬性的信息增益率（Information GainRatio）后，選出信息增益率最高的屬性對(duì)給定集合測試屬性，再采用遞歸算法根據(jù)測試屬性建立分支，初步得到?jīng)Q策樹。

在用決策樹對(duì)測試樣本數(shù)據(jù)進(jìn)行分類時(shí)可能會(huì)有某些屬性值缺失，傳統(tǒng)的決策樹算法在面對(duì)這些缺失的屬性值一般會(huì)采用拋棄缺失屬性值或者重新給定一個(gè)在訓(xùn)練樣本中該屬性常見的值［15］。而C4.5 算法會(huì)采用概率分布填充法處理缺失屬性值，具體執(zhí)行過程：首先為某個(gè)未知屬性每個(gè)可能的值賦予一個(gè)概率，再計(jì)算某節(jié)點(diǎn)上屬性不同值的出現(xiàn)頻率，這些概率可以被再次估計(jì)［16］。C4.5 算法相關(guān)計(jì)算公式如下所示［17］。

（1）期望信息（也稱信息熵）。設(shè)S是Si個(gè)數(shù)據(jù)樣本的集合，假定類標(biāo)號(hào)屬性有m個(gè)不同值，定義m個(gè)不同類Ti(i=1,…,m)。設(shè)Si是類Ti中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類所需的期望值為：

（2）信息增益。由屬性A劃分成子集的信息量為：

信息增益為原來的信息需求與新的需求之間的差。即：

（3）信息增益率。C4.5 算法中引入了信息增益率，屬性A 的信息增益率計(jì)算公式為：

在決策樹的剪枝階段，C4.5 算法采用后剪枝技術(shù)形成決策樹模型，根據(jù)建立好的模型生成一系列IF-THEN 規(guī)則，實(shí)現(xiàn)對(duì)訓(xùn)練集的分類。

C4.5 算法雖然在處理噪聲方面有很強(qiáng)的能力，但是在訓(xùn)練集缺失屬性值很高的狀態(tài)下，使用C4.5 算法構(gòu)建的決策樹模型會(huì)變復(fù)雜并出現(xiàn)更多的結(jié)點(diǎn)數(shù)，最終分類準(zhǔn)確率也會(huì)下降［18］。鑒于樸素貝葉斯分類具有堅(jiān)實(shí)的理論基礎(chǔ)、較小的出錯(cuò)率，本文提出一種基于樸素貝葉斯定理的方法［19］，以處理空缺屬性值。

假定一個(gè)樣本訓(xùn)練集D={d1,d2,…,dn}，每一個(gè)訓(xùn)練實(shí)例描述為di={di1,di2,…,dih}，對(duì)應(yīng)樣本訓(xùn)練的特征屬性集A={A1,A2,…,An}，每個(gè)屬性Ai的屬性值是{Ai1,Ai2,…,Aih} 。訓(xùn)練集包含的類別集合C={C1,C2,…,Cm}，即D可以分為Cm類別。與訓(xùn)練集D 有關(guān)系的決策樹有如下特點(diǎn)：①內(nèi)部節(jié)點(diǎn)由Ai表示；②子節(jié)點(diǎn)屬性與父節(jié)點(diǎn)屬性用枝干相連；③葉節(jié)點(diǎn)由Ci表示。樹被建立起來后對(duì)每個(gè)測試實(shí)例進(jìn)行分類，實(shí)例di的結(jié)果就是一個(gè)類別?；静襟E為：一是用訓(xùn)練集構(gòu)造一個(gè)決策樹；二是將概率優(yōu)化后的樸素貝葉斯運(yùn)用到測試集D 中。

對(duì)于訓(xùn)練集D，首先運(yùn)用決策樹分類器對(duì)每個(gè)di進(jìn)行分類。如果訓(xùn)練集中沒有空缺屬性，則將數(shù)據(jù)壓入D1 集合，如果有，則按空缺個(gè)數(shù)壓入D2 集合，數(shù)量越少越排前，到所有數(shù)據(jù)都檢測完則結(jié)束，最后形成了D1 和D2 兩個(gè)集合，其中D1 放入的是沒有空缺屬性值的數(shù)據(jù)集合，D2 放入的是包含空缺屬性值的數(shù)據(jù)集合；讀取D2 中的數(shù)據(jù)，用概率優(yōu)化后的樸素貝葉斯處理空缺屬性后放入D1 中，遞歸直到D2 集合中數(shù)據(jù)為0。處理完訓(xùn)練集D 中的空缺屬性值后，再用決策樹對(duì)更新后的訓(xùn)練集進(jìn)行分類。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)選取的是某互聯(lián)網(wǎng)營銷平臺(tái)微信公眾號(hào)中活動(dòng)的91 120 條中文用戶評(píng)論，通過考察用戶評(píng)論，將數(shù)據(jù)分為積極和消極兩類數(shù)據(jù)，并選用準(zhǔn)確率和召回率評(píng)價(jià)分類效果。部分?jǐn)?shù)據(jù)如表1 所示。

Table 1 Data of some user comments表1 部分用戶評(píng)論數(shù)據(jù)

3.2 數(shù)據(jù)預(yù)處理與文本特征抽取

數(shù)據(jù)預(yù)處理包括3 個(gè)部分，即：文本正則化、切分成詞和去掉停用詞。運(yùn)用TF-IDF 方法抽取數(shù)據(jù)特征，如表2 所示。

Table 2 Data preprocessing and text feature extraction表2 數(shù)據(jù)預(yù)處理與文本特征抽取

3.3 樸素貝葉斯與決策樹分類融合

采用融合樸素貝葉斯和決策樹的算法對(duì)用戶評(píng)論進(jìn)行分類，最終正確地將用戶評(píng)論分為積極和消極兩類，如表3 所示。

Table 3 Classification results表3 分類結(jié)果

本文實(shí)驗(yàn)結(jié)果采用準(zhǔn)確率和召回率兩個(gè)指標(biāo)，計(jì)算公式如下：

其中，TP 表示正確的標(biāo)記為正，F(xiàn)P 錯(cuò)誤的標(biāo)記為正，F(xiàn)N 錯(cuò)誤的標(biāo)記為負(fù)，TN 正確的標(biāo)記為負(fù)［20］，如表4 所示。

Table 4 Parameter meaning表4 參數(shù)含義

最終計(jì)算得到的分類準(zhǔn)確率和召回率如表5 所示。

Table 5 Analysis of experimental results表5 實(shí)驗(yàn)結(jié)果分析

由表5 可知，為了對(duì)比本文中提出的算法是否可行有效，通過對(duì)比樸素貝葉斯對(duì)用戶評(píng)論的分類，本文算法準(zhǔn)確率高出0.5 個(gè)百分點(diǎn)，召回率高出0.2 個(gè)百分點(diǎn)。由此可見，在用戶評(píng)論文本分類中，融合樸素貝葉斯和決策樹用戶評(píng)論分類效果取得了不錯(cuò)的結(jié)果。

4 結(jié)語

為了實(shí)現(xiàn)對(duì)用戶評(píng)論的商業(yè)研究價(jià)值提取，解決互聯(lián)網(wǎng)產(chǎn)品后續(xù)優(yōu)化和增進(jìn)服務(wù)問題，本文提出了一種融合樸素貝葉斯與決策樹的用戶評(píng)論分類算法。該研究首先對(duì)文本正則化、切分成詞并去掉停用詞，再融合樸素貝葉斯和決策樹算法，并將其應(yīng)用于微信公眾號(hào)互聯(lián)網(wǎng)營銷用戶評(píng)論分類中，最終可以正確地將用戶評(píng)論分為積極和消極兩類。其中，積極的用戶評(píng)論可以作為后續(xù)互聯(lián)網(wǎng)營銷活動(dòng)優(yōu)化，提升用戶體驗(yàn)的重要參考依據(jù)，消極的用戶評(píng)論可以增進(jìn)自己的服務(wù)。對(duì)分類結(jié)果的分析表明，改進(jìn)后的算法解決了樸素貝葉斯的零概率問題和決策樹因?qū)傩灾等笔矢邔?dǎo)致的分類準(zhǔn)確度下降問題，提高了分類準(zhǔn)確率。由于數(shù)據(jù)集不足以及中文語義復(fù)雜，會(huì)造成評(píng)論分類出現(xiàn)相反的情況，后續(xù)要在語義情感特征準(zhǔn)確性提取上作進(jìn)一步研究。