賈曉帆,何利力
(浙江理工大學(xué) 信息學(xué)院,浙江杭州 310018)
隨著互聯(lián)網(wǎng)的飛速發(fā)展,為了滿(mǎn)足用戶(hù)需求,出現(xiàn)了網(wǎng)頁(yè)、軟件、手機(jī)應(yīng)用等互聯(lián)網(wǎng)產(chǎn)品,還包括建立在各類(lèi)平臺(tái)上而開(kāi)發(fā)出的產(chǎn)品,如微信小程序、公眾號(hào)等。用戶(hù)在互聯(lián)網(wǎng)中發(fā)表對(duì)產(chǎn)品的評(píng)價(jià)這一舉動(dòng)讓用戶(hù)從單一的信息接受者轉(zhuǎn)變?yōu)榛ヂ?lián)網(wǎng)中文本信息的發(fā)布者,文本信息量呈指數(shù)級(jí)增長(zhǎng),僅僅由人工進(jìn)行分析提取幾乎不大可能,如何有效管理并充分利用這些信息值得思考。
樸素貝葉斯是機(jī)器學(xué)習(xí)的一個(gè)常用分類(lèi)模型,模型本身是建立在貝葉斯定理和特征條件獨(dú)立假設(shè)上的,有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ),用概率統(tǒng)計(jì)知識(shí)對(duì)樣本數(shù)據(jù)集進(jìn)行分類(lèi)。1990 年,Kononenko 等[1]證明了樸素貝葉斯的有效性。樸素貝葉斯的優(yōu)勢(shì)在于能夠很快地在訓(xùn)練集中建立起貝葉斯模型,但是在有些實(shí)際應(yīng)用中分類(lèi)效果卻不盡如人意。因?yàn)樵谟秘惾~斯分類(lèi)的前提下,必須假設(shè)屬性獨(dú)立,即屬性之間沒(méi)有關(guān)系,當(dāng)該假設(shè)不成立時(shí),就會(huì)影響貝葉斯分類(lèi)效果。為了解決該問(wèn)題,學(xué)者們放松屬性之間相互獨(dú)立的條件假設(shè),提出了貝葉斯網(wǎng)絡(luò)分類(lèi)器[2],其基本思想是考慮全部或者部分屬性之間的關(guān)聯(lián)性,以此滿(mǎn)足樸素貝葉斯模型相互獨(dú)立的條件假設(shè)。盡管這種思想能提高分類(lèi)性能,但是在訓(xùn)練中需要測(cè)算所有屬性之間的相關(guān)性,導(dǎo)致算法復(fù)雜度劇增。1996 年,Sahami[3]提出K-依賴(lài)貝葉斯分類(lèi)器,有效提升了分類(lèi)性能;1997 年,F(xiàn)riedman 等[4]提出了一種樹(shù)擴(kuò)展的樸素貝葉斯分類(lèi)器,簡(jiǎn)稱(chēng)TAN 模型,它在測(cè)算屬性之間相關(guān)性的基礎(chǔ)上,構(gòu)建樹(shù)形結(jié)構(gòu)圖;1999 年,Nurnberger 等[5]提出了基于神經(jīng)模糊的樸素貝葉斯分類(lèi)器,簡(jiǎn)稱(chēng)BAN 模型,它是TAN 模型的升級(jí)版,相比TAN 模型,允許特征屬性之間形成有向結(jié)構(gòu)圖;2004 年,Wang 等[6]提出基于自適應(yīng)的Boosting 與樸素貝葉斯結(jié)合方法,可以有效地緩解噪聲提高分類(lèi)性能;2008 年,徐光美等[7]通過(guò)基于互信息計(jì)算各屬性與各類(lèi)別之間的相關(guān)性,選擇不相關(guān)的特征值代入樸素貝葉斯模型中;2011 年,Zheng 等[8]通過(guò)刪除一部分相關(guān)性強(qiáng)的特征屬性,將處理后的特征屬性應(yīng)用于樸素貝葉斯分類(lèi)模型;2014 年,杜選[9]提出一種基于加權(quán)補(bǔ)集的樸素貝葉斯文本分類(lèi)模型,這種模型可避免在訓(xùn)練集不平衡時(shí),可能導(dǎo)致分類(lèi)性能低的缺陷。
本文在研究樸素貝葉斯算法的基礎(chǔ)上提出一種與決策樹(shù)相融合的算法,使用本文算法可以有效填補(bǔ)數(shù)據(jù)集中的缺失屬性值。實(shí)驗(yàn)結(jié)果證明,本文算法的分類(lèi)效果比傳統(tǒng)樸素貝葉斯分類(lèi)效果更好。
Laplace 是最古老的平滑技術(shù)之一,所謂平滑技術(shù)是指為了產(chǎn)生更理想的概率以調(diào)整最大似然估計(jì)的技術(shù)[10-11]。計(jì)算公式如下:
其中,N 為訓(xùn)練實(shí)例總數(shù)量;T 為訓(xùn)練集實(shí)例種類(lèi)數(shù)。在Laplace 估計(jì)中,先驗(yàn)概率P(Y)被定義如下:
其中,nc是滿(mǎn)足Y={yj} 的實(shí)例個(gè)數(shù),N 是訓(xùn)練集個(gè)數(shù),n是類(lèi)的個(gè)數(shù),并且k=1。
樸素貝葉斯分類(lèi)(NBC)是一種假設(shè)特征與特征之間相互獨(dú)立的算法,它基于貝葉斯定理,算法邏輯穩(wěn)定且簡(jiǎn)單,樸素貝葉斯的健壯性較好,其分類(lèi)功能在數(shù)據(jù)展現(xiàn)出不同特點(diǎn)時(shí),差別不大,也即在不同類(lèi)型的數(shù)據(jù)集中不會(huì)表現(xiàn)出太大差異[12]。因此,當(dāng)數(shù)據(jù)集屬性之間的關(guān)系相對(duì)獨(dú)立時(shí),樸素貝葉斯分類(lèi)算法會(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},有類(lèi)別集合Y={y1,y2,…,ym},即D可以分為ym類(lèi)別。其中x1,x2,…,xd相互獨(dú)立且隨機(jī),則Y的先驗(yàn)概率P=P(Y),Y的后驗(yàn)概率P=P(Y|X),由樸素貝葉斯算法可得后驗(yàn)概率為:
樸素貝葉斯基于各特征之間相互獨(dú)立,在給定類(lèi)別為y的情況下,式(6)可以進(jìn)一步表示為:
由式(7)可計(jì)算出后驗(yàn)概率為:
由于P(X)的大小固定不變,因此在比較后驗(yàn)概率時(shí),只比較式(8)的分子部分即可。因此,可以得到一個(gè)樣本數(shù)據(jù)屬于類(lèi)別yi的樸素貝葉斯計(jì)算公式如下:
決策樹(shù)是一種包含根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)、葉節(jié)點(diǎn)3 種節(jié)點(diǎn)的樹(shù)型結(jié)構(gòu)。當(dāng)文本分類(lèi)算法為決策樹(shù)時(shí),它由樹(shù)的內(nèi)部節(jié)點(diǎn)逐一標(biāo)注所構(gòu)成,葉節(jié)點(diǎn)表示對(duì)應(yīng)的類(lèi)別標(biāo)簽,與葉節(jié)點(diǎn)相連的分支上標(biāo)注著其對(duì)應(yīng)的權(quán)重,樹(shù)的葉子節(jié)點(diǎn)表示文本分類(lèi)目標(biāo),當(dāng)從根開(kāi)始遍歷查詢(xún)最終到達(dá)某一個(gè)葉子節(jié)點(diǎn),這樣就完成了一次文本分類(lèi)[13],樹(shù)的高度就是時(shí)間復(fù)雜度,它是一個(gè)自頂向下、分而治之的總過(guò)程。決策樹(shù)的準(zhǔn)確率會(huì)因重復(fù)的屬性而受一定影響,因而用決策樹(shù)進(jìn)行分類(lèi)是要對(duì)數(shù)據(jù)進(jìn)行特征選擇。決策樹(shù)在開(kāi)始階段會(huì)浪費(fèi)時(shí)間,但只要模型建立起來(lái),運(yùn)用階段非???。
決策樹(shù)算法是一種無(wú)監(jiān)督分類(lèi)方法,決策樹(shù)的生成主要分為節(jié)點(diǎn)分裂和閾值確定,節(jié)點(diǎn)分裂指當(dāng)一個(gè)節(jié)點(diǎn)所代表的屬性無(wú)法判斷時(shí),則選擇將一節(jié)點(diǎn)分為多個(gè)子節(jié)點(diǎn),而選擇適當(dāng)?shù)拈撝悼梢允狗诸?lèi)錯(cuò)誤率最小。決策樹(shù)以樹(shù)的層次規(guī)則為特征,葉子節(jié)點(diǎn)為分類(lèi)目標(biāo),通過(guò)遍歷根節(jié)點(diǎn)到葉子節(jié)點(diǎn)完成一次分類(lèi)操作。決策樹(shù)分類(lèi)算法與其他決策支持工具相比較起來(lái)易于理解和解釋。然而,通過(guò)有限的數(shù)據(jù)集無(wú)法訓(xùn)練出可靠的類(lèi)標(biāo)簽,并且對(duì)特征空間計(jì)算成本非常高,這對(duì)決策樹(shù)而言是一種限制[13]。決策樹(shù)算法作為一種常見(jiàn)分類(lèi)算法,有很多變種,包括ID3、C4.5、C5.0、CART 等。其中,最常用的、最經(jīng)典的是C4.5 算法。
樸素貝葉斯的概率估計(jì)會(huì)在訓(xùn)練樣本不足時(shí)出現(xiàn)零概率的問(wèn)題,這會(huì)導(dǎo)致求出的類(lèi)標(biāo)簽的后驗(yàn)概率值為零,使用連乘計(jì)算文本出現(xiàn)概率時(shí)也是零,傳統(tǒng)的樸素貝葉斯在這種情況下無(wú)法進(jìn)行分類(lèi),這一直以來(lái)都是樸素貝葉斯的難題。為了解決該問(wèn)題,法國(guó)的數(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)零概率問(wèn)題。針對(duì)本實(shí)驗(yàn)所采取的樸素貝葉斯模型,采用詞頻估算每一個(gè)特征,其經(jīng)過(guò)拉普拉斯平滑方法處理后的表達(dá)式為:
為了提高貝葉斯分類(lèi)準(zhǔn)確性,在提出的貝葉斯與其他方法相結(jié)合的算法中,最為代表的是Kohavi[14]提出的NB?Tree 算法。對(duì)于大型數(shù)據(jù)分類(lèi),決策樹(shù)和樸素貝葉斯相比,前者在維度較大或者屬性之間的依賴(lài)關(guān)系明顯優(yōu)于后者,后者的分類(lèi)結(jié)果準(zhǔn)確性?xún)?yōu)于前者。而NBTree 算法剛好結(jié)合貝葉斯和決策樹(shù)各自的優(yōu)點(diǎn),提升了算法效率。
C4.5 算法的優(yōu)點(diǎn)是產(chǎn)生的分類(lèi)規(guī)則易于理解,準(zhǔn)確率較高,C4.5 經(jīng)過(guò)樹(shù)生成和樹(shù)剪枝建立決策樹(shù)。在計(jì)算每個(gè)屬性的信息增益率(Information GainRatio)后,選出信息增益率最高的屬性對(duì)給定集合測(cè)試屬性,再采用遞歸算法根據(jù)測(cè)試屬性建立分支,初步得到?jīng)Q策樹(shù)。
在用決策樹(shù)對(duì)測(cè)試樣本數(shù)據(jù)進(jìn)行分類(lèi)時(shí)可能會(huì)有某些屬性值缺失,傳統(tǒng)的決策樹(shù)算法在面對(duì)這些缺失的屬性值一般會(huì)采用拋棄缺失屬性值或者重新給定一個(gè)在訓(xùn)練樣本中該屬性常見(jiàn)的值[15]。而C4.5 算法會(huì)采用概率分布填充法處理缺失屬性值,具體執(zhí)行過(guò)程:首先為某個(gè)未知屬性每個(gè)可能的值賦予一個(gè)概率,再計(jì)算某節(jié)點(diǎn)上屬性不同值的出現(xiàn)頻率,這些概率可以被再次估計(jì)[16]。C4.5 算法相關(guān)計(jì)算公式如下所示[17]。
(1)期望信息(也稱(chēng)信息熵)。設(shè)S是Si個(gè)數(shù)據(jù)樣本的集合,假定類(lèi)標(biāo)號(hào)屬性有m個(gè)不同值,定義m個(gè)不同類(lèi)Ti(i=1,…,m)。設(shè)Si是類(lèi)Ti中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類(lèi)所需的期望值為:
(2)信息增益。由屬性A劃分成子集的信息量為:
信息增益為原來(lái)的信息需求與新的需求之間的差。即:
(3)信息增益率。C4.5 算法中引入了信息增益率,屬性A 的信息增益率計(jì)算公式為:
在決策樹(shù)的剪枝階段,C4.5 算法采用后剪枝技術(shù)形成決策樹(shù)模型,根據(jù)建立好的模型生成一系列IF-THEN 規(guī)則,實(shí)現(xiàn)對(duì)訓(xùn)練集的分類(lèi)。
C4.5 算法雖然在處理噪聲方面有很強(qiáng)的能力,但是在訓(xùn)練集缺失屬性值很高的狀態(tài)下,使用C4.5 算法構(gòu)建的決策樹(shù)模型會(huì)變復(fù)雜并出現(xiàn)更多的結(jié)點(diǎn)數(shù),最終分類(lèi)準(zhǔn)確率也會(huì)下降[18]。鑒于樸素貝葉斯分類(lèi)具有堅(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)練集包含的類(lèi)別集合C={C1,C2,…,Cm},即D可以分為Cm類(lèi)別。與訓(xùn)練集D 有關(guān)系的決策樹(shù)有如下特點(diǎn):①內(nèi)部節(jié)點(diǎn)由Ai表示;②子節(jié)點(diǎn)屬性與父節(jié)點(diǎn)屬性用枝干相連;③葉節(jié)點(diǎn)由Ci表示。樹(shù)被建立起來(lái)后對(duì)每個(gè)測(cè)試實(shí)例進(jìn)行分類(lèi),實(shí)例di的結(jié)果就是一個(gè)類(lèi)別。基本步驟為:一是用訓(xùn)練集構(gòu)造一個(gè)決策樹(shù);二是將概率優(yōu)化后的樸素貝葉斯運(yùn)用到測(cè)試集D 中。
對(duì)于訓(xùn)練集D,首先運(yùn)用決策樹(shù)分類(lèi)器對(duì)每個(gè)di進(jìn)行分類(lèi)。如果訓(xùn)練集中沒(méi)有空缺屬性,則將數(shù)據(jù)壓入D1 集合,如果有,則按空缺個(gè)數(shù)壓入D2 集合,數(shù)量越少越排前,到所有數(shù)據(jù)都檢測(cè)完則結(jié)束,最后形成了D1 和D2 兩個(gè)集合,其中D1 放入的是沒(méi)有空缺屬性值的數(shù)據(jù)集合,D2 放入的是包含空缺屬性值的數(shù)據(jù)集合;讀取D2 中的數(shù)據(jù),用概率優(yōu)化后的樸素貝葉斯處理空缺屬性后放入D1 中,遞歸直到D2 集合中數(shù)據(jù)為0。處理完訓(xùn)練集D 中的空缺屬性值后,再用決策樹(shù)對(duì)更新后的訓(xùn)練集進(jìn)行分類(lèi)。
本文實(shí)驗(yàn)選取的是某互聯(lián)網(wǎng)營(yíng)銷(xiāo)平臺(tái)微信公眾號(hào)中活動(dòng)的91 120 條中文用戶(hù)評(píng)論,通過(guò)考察用戶(hù)評(píng)論,將數(shù)據(jù)分為積極和消極兩類(lèi)數(shù)據(jù),并選用準(zhǔn)確率和召回率評(píng)價(jià)分類(lèi)效果。部分?jǐn)?shù)據(jù)如表1 所示。
Table 1 Data of some user comments表1 部分用戶(hù)評(píng)論數(shù)據(jù)
數(shù)據(jù)預(yù)處理包括3 個(gè)部分,即:文本正則化、切分成詞和去掉停用詞。運(yùn)用TF-IDF 方法抽取數(shù)據(jù)特征,如表2 所示。
Table 2 Data preprocessing and text feature extraction表2 數(shù)據(jù)預(yù)處理與文本特征抽取
采用融合樸素貝葉斯和決策樹(shù)的算法對(duì)用戶(hù)評(píng)論進(jìn)行分類(lèi),最終正確地將用戶(hù)評(píng)論分為積極和消極兩類(lèi),如表3 所示。
Table 3 Classification results表3 分類(lèi)結(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ì)算得到的分類(lèi)準(zhǔn)確率和召回率如表5 所示。
Table 5 Analysis of experimental results表5 實(shí)驗(yàn)結(jié)果分析
由表5 可知,為了對(duì)比本文中提出的算法是否可行有效,通過(guò)對(duì)比樸素貝葉斯對(duì)用戶(hù)評(píng)論的分類(lèi),本文算法準(zhǔn)確率高出0.5 個(gè)百分點(diǎn),召回率高出0.2 個(gè)百分點(diǎn)。由此可見(jiàn),在用戶(hù)評(píng)論文本分類(lèi)中,融合樸素貝葉斯和決策樹(shù)用戶(hù)評(píng)論分類(lèi)效果取得了不錯(cuò)的結(jié)果。
為了實(shí)現(xiàn)對(duì)用戶(hù)評(píng)論的商業(yè)研究?jī)r(jià)值提取,解決互聯(lián)網(wǎng)產(chǎn)品后續(xù)優(yōu)化和增進(jìn)服務(wù)問(wèn)題,本文提出了一種融合樸素貝葉斯與決策樹(shù)的用戶(hù)評(píng)論分類(lèi)算法。該研究首先對(duì)文本正則化、切分成詞并去掉停用詞,再融合樸素貝葉斯和決策樹(shù)算法,并將其應(yīng)用于微信公眾號(hào)互聯(lián)網(wǎng)營(yíng)銷(xiāo)用戶(hù)評(píng)論分類(lèi)中,最終可以正確地將用戶(hù)評(píng)論分為積極和消極兩類(lèi)。其中,積極的用戶(hù)評(píng)論可以作為后續(xù)互聯(lián)網(wǎng)營(yíng)銷(xiāo)活動(dòng)優(yōu)化,提升用戶(hù)體驗(yàn)的重要參考依據(jù),消極的用戶(hù)評(píng)論可以增進(jìn)自己的服務(wù)。對(duì)分類(lèi)結(jié)果的分析表明,改進(jìn)后的算法解決了樸素貝葉斯的零概率問(wèn)題和決策樹(shù)因?qū)傩灾等笔矢邔?dǎo)致的分類(lèi)準(zhǔn)確度下降問(wèn)題,提高了分類(lèi)準(zhǔn)確率。由于數(shù)據(jù)集不足以及中文語(yǔ)義復(fù)雜,會(huì)造成評(píng)論分類(lèi)出現(xiàn)相反的情況,后續(xù)要在語(yǔ)義情感特征準(zhǔn)確性提取上作進(jìn)一步研究。