量子遺傳算法優(yōu)化加權(quán)樸素貝葉斯復(fù)合語(yǔ)言文本分類

隆 峻，神顯豪，丁小軍，郭先春

(1.玉林師范學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 玉林 537000；2.桂林理工大學(xué) 廣西嵌入式技術(shù)與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004；3.東華理工大學(xué) 測(cè)繪工程學(xué)院，江西 南昌 330013)

隨著互聯(lián)網(wǎng)的發(fā)展，大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)分析成為研究熱點(diǎn)。語(yǔ)言文本分類作為數(shù)據(jù)挖掘的一種方式，在網(wǎng)絡(luò)服務(wù)平臺(tái)上得到了廣泛應(yīng)用[1]，比如通過(guò)對(duì)社交或者電商平臺(tái)大規(guī)模用戶評(píng)論數(shù)據(jù)抓取，然后通過(guò)文本分類，可以獲得大量用戶的精準(zhǔn)評(píng)價(jià)分類。隨著網(wǎng)絡(luò)服務(wù)平臺(tái)的全球開(kāi)放與互融，多種語(yǔ)言文本分類需求應(yīng)運(yùn)而生，迫切需要一種能夠?qū)崿F(xiàn)多種混合語(yǔ)言文本分類的分類算法，從而解決復(fù)合本文數(shù)據(jù)挖掘的問(wèn)題。由于各國(guó)語(yǔ)言規(guī)則差異及文字語(yǔ)義組合機(jī)制相差較大[2]，相比于單語(yǔ)言文本分類，能夠同時(shí)實(shí)現(xiàn)多種語(yǔ)言文本分類的難度明顯提升，因此給互聯(lián)網(wǎng)中數(shù)據(jù)檢索及挖掘提出了新的挑戰(zhàn)。

不同于單一語(yǔ)言文本的分類研究，關(guān)于復(fù)合語(yǔ)言文本分類的研究較少。Pavlinek等[3]采用自訓(xùn)練和線性判別分析主題模型對(duì)多種語(yǔ)言文本中所表現(xiàn)的情感因素進(jìn)行分類，能夠出色完成對(duì)一般情感類別分類；但自訓(xùn)練需要借助于來(lái)自未標(biāo)記數(shù)據(jù)的信息來(lái)擴(kuò)大小的初始標(biāo)記集，因此分類效率有待提高。Liu等[4]采用AdaBoost機(jī)器學(xué)習(xí)進(jìn)行了半監(jiān)督的文本分類，較好地解決了AdaBoost的訓(xùn)練誤差受歸一化因子乘積的限制問(wèn)題，但同樣存在分類效率不理想的問(wèn)題。

樸素貝葉斯分類作為機(jī)器學(xué)習(xí)領(lǐng)域的經(jīng)典數(shù)據(jù)挖掘算法，具有建模簡(jiǎn)單、執(zhí)行效率高等特點(diǎn)，因此，Gao等[5]嘗試將分布式樸素貝葉斯算法在文本分類中進(jìn)行應(yīng)用，使用互信息方法檢查特征選擇后生成的特征集相關(guān)性來(lái)彌補(bǔ)傳統(tǒng)樸素貝葉斯文本分類方法的不足，但是相關(guān)運(yùn)算的計(jì)算時(shí)間較長(zhǎng)。Jiang等[6]采用樸素貝葉斯的特征加權(quán)對(duì)文本情感數(shù)據(jù)進(jìn)行分類，通過(guò)計(jì)算訓(xùn)練數(shù)據(jù)的特征加權(quán)頻率來(lái)估計(jì)樸素貝葉斯的條件概率，大幅提高了分類效率，但是簡(jiǎn)單加權(quán)的樸素貝葉斯會(huì)降低模型的質(zhì)量，導(dǎo)致分類精度降低。此外，上述2種基于樸素貝葉斯的文本分類均未涉及到復(fù)合語(yǔ)言文本分類。

本文中提出量子遺傳算法(QGA)優(yōu)化加權(quán)樸素貝葉斯算法(WNBA)用于復(fù)合語(yǔ)言文本分類，嘗試引入遺傳算法對(duì)加權(quán)樸素貝葉斯算法的權(quán)重參數(shù)進(jìn)行優(yōu)化，在保證分類效率的同時(shí)提高分類精度。遺傳算法優(yōu)化過(guò)程借鑒量子比特方法，提升加權(quán)樸素貝葉斯算法在復(fù)合語(yǔ)言文本分類中的適應(yīng)度，從而獲得較高的文本分類準(zhǔn)確率。

1 加權(quán)樸素貝葉斯算法

1.1 貝葉斯定理

設(shè)事件A、B發(fā)生的概率為P(A)、P(B)，事件A、B的聯(lián)合概率為P(A∩B)=P(B∩A)，當(dāng)事件B發(fā)生時(shí)，事件A的概率P(A|B)為

(1)

同理，根據(jù)聯(lián)合概率公式，

P(A∩B)=P(A|B)P(B)，

(2)

P(B∩A)=P(B|A)P(A)，

(3)

P(A|B)P(B)=P(B|A)P(A)。

(4)

根據(jù)式(1)、(3)得樸素貝葉斯(naive Bayes)公式[6]為

(5)

(6)

1.2 WNBA算法

設(shè)樣本x包含n個(gè)維度，表示方法為x=(x1,x2,…,xn)，樣本共有m個(gè)類別，表示為C={C1,C2,…,Cm}，由N個(gè)樣本組成的樣本集X=(x1,x2,…,xN)T，其中X屬于各類Ci(i=1,2,…,m)的概率為

P(Ci|X)=maxP(Cj|X), 1≤j≤m，

(7)

式中P(Ci|X)表示最大后驗(yàn)概率[7]。

由式(7)得

(8)

式中：P(X)表示全概率[7]；

(9)

(10)

(11)

式中：N(Ci)為屬于Ci類的樣本個(gè)數(shù)；

(12)

其中N(Ci,xi)為Ci類中存在屬性的樣本個(gè)數(shù)。

在實(shí)際情況中，很多屬性對(duì)于類別的影響權(quán)重是不一樣的，因此引入屬性權(quán)重w，構(gòu)成WNBA(weight naive Bayes algorithm)[8]，即

(13)

2 QGA優(yōu)化WNBA算法

2.1 算法基本原理

為了改善加權(quán)樸素貝葉斯算法在復(fù)合語(yǔ)音文本分類的性能，利用遺傳算法(GA)來(lái)優(yōu)化權(quán)重w，以提高復(fù)合語(yǔ)言文本分類性能。

首先設(shè)C(x)為適應(yīng)度函數(shù)f，其中個(gè)體i被選擇進(jìn)化的概率Pi[9]為

(14)

式中fi為個(gè)體適應(yīng)度值。

(15)

式中α為隨機(jī)復(fù)數(shù)。

個(gè)體xk變異得到

(16)

式中β為取值為[0,1]中的隨機(jī)復(fù)數(shù)。

設(shè)交叉和變異概率分別為Pc和Pm，限制范圍為[Pc,min,Pc,max]和[Pm,min,Pm,max]，其中Pc,min=0，Pc,max=0.9，Pm,min=0.01，Pm,max=0.1。設(shè)全部個(gè)體適應(yīng)度均值為favg，個(gè)體適應(yīng)度最大值、最小值分別為fmax、fmin, 交叉與變異的適應(yīng)度分別為f′和f[11]，則有

(17)

(18)

不斷進(jìn)化迭代，直到復(fù)合語(yǔ)言文本分類精度達(dá)到要求或者達(dá)到最大迭代次數(shù)，算法停止，獲得經(jīng)過(guò)優(yōu)化后的加權(quán)樸素貝葉斯算法的最佳權(quán)重和閾值。

2.2 QA進(jìn)化的量子比特表示

為了進(jìn)一步提高GA對(duì)屬性權(quán)重的優(yōu)化效率，引入量子比特表示。量子運(yùn)算基本方法[12]為

(19)

(20)

式(19)、(20)中的α和β可以表示為α=cosθ，β=sinθ[13]，則有

(21)

式中θ為量子比特中的另一個(gè)實(shí)數(shù)。α和β可以采用量子方法計(jì)算。

最后得到QGA優(yōu)化WNBA復(fù)合語(yǔ)言文本分類模型。

2.3 QGA優(yōu)化WNBA復(fù)合語(yǔ)言文本分類流程

QGA優(yōu)化WNBA復(fù)合語(yǔ)言文本分類流程如圖1所示。在復(fù)合語(yǔ)言文本分類過(guò)程中，首先構(gòu)建加權(quán)樸素貝葉斯分類模型，然后求解不同權(quán)重條件下的遺傳個(gè)體適應(yīng)度值，隨后進(jìn)行GA權(quán)重優(yōu)化，在交叉等計(jì)算過(guò)程中，結(jié)合量子比特計(jì)算，最后獲得最優(yōu)權(quán)重個(gè)體。通過(guò)復(fù)合語(yǔ)言文本分類精度及迭代次數(shù)上限值來(lái)確定最終的分類模型。

圖1 量子遺傳算法(QGA)優(yōu)化加權(quán)樸素貝葉斯復(fù)合語(yǔ)言文本分類流程

3 實(shí)例仿真

為了驗(yàn)證QGA優(yōu)化WNBA復(fù)合語(yǔ)言文本分類性能，首先對(duì)WNBA算法和QGA優(yōu)化WNBA算法分別進(jìn)行性能仿真，驗(yàn)證QGA的優(yōu)化性能；其次采用常見(jiàn)語(yǔ)言文本分類算法和本文中提出的QGA優(yōu)化WNBA算法分別進(jìn)行仿真，驗(yàn)證不同分類算法的語(yǔ)言文本分類性能。分類性能指標(biāo)為準(zhǔn)確率、召回率和精確率與召回率的調(diào)和平均值F1。

復(fù)合語(yǔ)言文本仿真的數(shù)據(jù)來(lái)源為某知名跨境電商平臺(tái)，通過(guò)對(duì)5種熱銷產(chǎn)品的用戶評(píng)論數(shù)據(jù)進(jìn)行分類，統(tǒng)計(jì)用戶評(píng)價(jià)結(jié)果。用戶評(píng)論語(yǔ)言包括中、英、法、韓、日等語(yǔ)種。根據(jù)5種產(chǎn)品構(gòu)成5個(gè)數(shù)據(jù)集，樣本數(shù)量及需要分類的類別數(shù)分別如表1所示。

3.1 QGA的優(yōu)化性能

為了驗(yàn)證QGA對(duì)樸素貝葉斯復(fù)合語(yǔ)言文本分類的影響，分別采用樸素貝葉斯算法(NBA)、WNBA和QGA優(yōu)化WNBA對(duì)表1中的5個(gè)數(shù)據(jù)集進(jìn)行仿真，結(jié)果見(jiàn)表2。從表中可以看出，在跨境電商的商品評(píng)論5個(gè)數(shù)據(jù)集的復(fù)合語(yǔ)言文本分類中，經(jīng)過(guò)了QGA優(yōu)化的NBA表現(xiàn)出了更優(yōu)的性能。QGA優(yōu)化WNBA 3個(gè)指標(biāo)均超過(guò)了0.9，而NBA分類的3個(gè)指標(biāo)值均維持在0.8左右。QGA優(yōu)化WNBA的最大分類準(zhǔn)確率為93.83%，而NBA最大分類準(zhǔn)確率為82.99%，兩者差距較大，普通NBA在復(fù)合語(yǔ)言文本的效果并不理想，但通過(guò)QGA優(yōu)化后，分類性能提升明顯，主要原因是經(jīng)過(guò)QGA的權(quán)重優(yōu)化后，獲得了更準(zhǔn)確的屬性權(quán)重值，找到了影響分類準(zhǔn)確率最關(guān)鍵的屬性。下面將繼續(xù)對(duì)2種算法的分類效率進(jìn)行對(duì)比。

表1 復(fù)合語(yǔ)言文本集

表2 量子遺傳算法(QGA)的優(yōu)化性能對(duì)比

不同算法的分類時(shí)間性能如圖2所示。由圖可以看出，3種算法對(duì)數(shù)據(jù)集4的分類耗時(shí)最少，對(duì)數(shù)據(jù)集3的分類耗時(shí)最長(zhǎng)，原因是復(fù)合語(yǔ)言文本的分類時(shí)間主要取決于樣本量和類別數(shù)，數(shù)據(jù)集3待分類樣本量最大且待分類的類別數(shù)最多，而數(shù)據(jù)集4正好相反。對(duì)比發(fā)現(xiàn)，NBA的復(fù)合語(yǔ)言文本分類耗時(shí)最短，而WNBA和QGA優(yōu)化WNBA的分類時(shí)間相差很小，這是因?yàn)镹BA沒(méi)有權(quán)重參數(shù)的求解過(guò)程，所以更省時(shí)，而WNBA和QGA優(yōu)化WNBA均需要權(quán)重求解，但是通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，QGA優(yōu)化并未增加時(shí)間消耗，原因是通過(guò)QGA優(yōu)化后求解最優(yōu)屬性權(quán)重的時(shí)間變短。

NBA—樸素貝葉斯算法；WNBA—加權(quán)樸素貝葉斯算法；QGA—量子遺傳算法。

3.2 不同算法的復(fù)合語(yǔ)言文本分類性能

為了進(jìn)一步驗(yàn)證不同算法在復(fù)合語(yǔ)言文本分類中的性能，采用常用語(yǔ)言文本分類算法支持向量機(jī)(SVM)[14]、反向傳播神經(jīng)網(wǎng)絡(luò)(BPNN)[15]、卷積神經(jīng)網(wǎng)絡(luò)(CNN)[16]和QGA優(yōu)化WNBA算法分別對(duì)表1中的5個(gè)數(shù)據(jù)集進(jìn)行仿真。由于篇幅限制，因此暫只截取數(shù)據(jù)集1、3、5的分類性能，如圖3所示。從圖中可以看出，QGA優(yōu)化WNBA和CNN算法的復(fù)合語(yǔ)言文本分類準(zhǔn)確率最高，穩(wěn)定時(shí)兩者的分類準(zhǔn)確率非常接近，且均超過(guò)了0.9，SVM的分類準(zhǔn)確率最差，均小于0.8。從分類時(shí)間方面來(lái)看：對(duì)于數(shù)據(jù)集1，CNN算法消耗時(shí)間最長(zhǎng)，約為275 s，SVM分類時(shí)間最短，約為180 s，QGA優(yōu)化WNBA分類時(shí)間約為210 s；對(duì)于數(shù)據(jù)集3，CNN算法分類時(shí)間長(zhǎng)達(dá)440 s，QGA優(yōu)化WNBA的約為350 s；對(duì)于數(shù)據(jù)集5，QGA優(yōu)化WNBA比CNN算法節(jié)省了約40 s，因此在相同準(zhǔn)確率的情況下，本文中提出的算法相比于CNN算法分類時(shí)間性能優(yōu)勢(shì)明顯。

(a)數(shù)據(jù)集1

對(duì)4種算法在復(fù)合語(yǔ)言文本的分類穩(wěn)定性進(jìn)行仿真，驗(yàn)證4種算法的準(zhǔn)確率均方根誤差(RMSE)性能，結(jié)果見(jiàn)表3。從表中可以看出，對(duì)于5個(gè)數(shù)據(jù)集，QGA優(yōu)化WNBA的分類準(zhǔn)確率RMSE值最優(yōu)，SVM表現(xiàn)最差。其中，4種算法在數(shù)據(jù)集4的RMSE性能表現(xiàn)最優(yōu)，在數(shù)據(jù)集3的RMSE性能最差，這可能是因?yàn)閿?shù)據(jù)集1待分類的類別數(shù)最少，而數(shù)據(jù)集3需要分類的類別數(shù)最多，在高維復(fù)合語(yǔ)言文本分類時(shí)，類別過(guò)多造成了分類準(zhǔn)確率值在多次分類中波動(dòng)較大，這也說(shuō)明分類準(zhǔn)確率RMSE值對(duì)分類類別數(shù)較為敏感，在對(duì)多類別進(jìn)行分類時(shí)，需要采取合理措施來(lái)控制分類準(zhǔn)確率波動(dòng)。

表3 不同算法的準(zhǔn)確率均方根誤差(RMSE)

4 結(jié)語(yǔ)

本文中提出將QGA優(yōu)化WNBA應(yīng)用于復(fù)合語(yǔ)言文本分類，充分利用QGA的權(quán)重優(yōu)化優(yōu)勢(shì)，提高了WNBA在多語(yǔ)言文本分類中的適用度，相比于常用復(fù)合語(yǔ)言文本分類算法，本文中提出的算法在分類準(zhǔn)確率及RMSE性能方面優(yōu)勢(shì)明顯。后續(xù)研究將進(jìn)一步優(yōu)化QGA求解，以優(yōu)化分類時(shí)間性能，為大規(guī)模復(fù)合語(yǔ)言文本的分類研究提供參考。