量子遺傳算法優化加權樸素貝葉斯復合語言文本分類

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

(1.玉林師范學院 計算機科學與工程學院，廣西 玉林 537000；2.桂林理工大學 廣西嵌入式技術與智能系統重點實驗室，廣西 桂林 541004；3.東華理工大學 測繪工程學院，江西 南昌 330013)

隨著互聯網的發展，大規模網絡數據分析成為研究熱點。語言文本分類作為數據挖掘的一種方式，在網絡服務平臺上得到了廣泛應用[1]，比如通過對社交或者電商平臺大規模用戶評論數據抓取，然后通過文本分類，可以獲得大量用戶的精準評價分類。隨著網絡服務平臺的全球開放與互融，多種語言文本分類需求應運而生，迫切需要一種能夠實現多種混合語言文本分類的分類算法，從而解決復合本文數據挖掘的問題。由于各國語言規則差異及文字語義組合機制相差較大[2]，相比于單語言文本分類，能夠同時實現多種語言文本分類的難度明顯提升，因此給互聯網中數據檢索及挖掘提出了新的挑戰。

不同于單一語言文本的分類研究，關于復合語言文本分類的研究較少。Pavlinek等[3]采用自訓練和線性判別分析主題模型對多種語言文本中所表現的情感因素進行分類，能夠出色完成對一般情感類別分類；但自訓練需要借助于來自未標記數據的信息來擴大小的初始標記集，因此分類效率有待提高。Liu等[4]采用AdaBoost機器學習進行了半監督的文本分類，較好地解決了AdaBoost的訓練誤差受歸一化因子乘積的限制問題，但同樣存在分類效率不理想的問題。

樸素貝葉斯分類作為機器學習領域的經典數據挖掘算法，具有建模簡單、執行效率高等特點，因此，Gao等[5]嘗試將分布式樸素貝葉斯算法在文本分類中進行應用，使用互信息方法檢查特征選擇后生成的特征集相關性來彌補傳統樸素貝葉斯文本分類方法的不足，但是相關運算的計算時間較長。Jiang等[6]采用樸素貝葉斯的特征加權對文本情感數據進行分類，通過計算訓練數據的特征加權頻率來估計樸素貝葉斯的條件概率，大幅提高了分類效率，但是簡單加權的樸素貝葉斯會降低模型的質量，導致分類精度降低。此外，上述2種基于樸素貝葉斯的文本分類均未涉及到復合語言文本分類。

本文中提出量子遺傳算法(QGA)優化加權樸素貝葉斯算法(WNBA)用于復合語言文本分類，嘗試引入遺傳算法對加權樸素貝葉斯算法的權重參數進行優化，在保證分類效率的同時提高分類精度。遺傳算法優化過程借鑒量子比特方法，提升加權樸素貝葉斯算法在復合語言文本分類中的適應度，從而獲得較高的文本分類準確率。

1 加權樸素貝葉斯算法

1.1 貝葉斯定理

設事件A、B發生的概率為P(A)、P(B)，事件A、B的聯合概率為P(A∩B)=P(B∩A)，當事件B發生時，事件A的概率P(A|B)為

(1)

同理，根據聯合概率公式，

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)

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

(5)

(6)

1.2 WNBA算法

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

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

(7)

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

由式(7)得

(8)

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

(9)

(10)

(11)

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

(12)

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

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

(13)

2 QGA優化WNBA算法

2.1 算法基本原理

為了改善加權樸素貝葉斯算法在復合語音文本分類的性能，利用遺傳算法(GA)來優化權重w，以提高復合語言文本分類性能。

首先設C(x)為適應度函數f，其中個體i被選擇進化的概率Pi[9]為

(14)

式中fi為個體適應度值。

(15)

式中α為隨機復數。

個體xk變異得到

(16)

式中β為取值為[0,1]中的隨機復數。

設交叉和變異概率分別為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。設全部個體適應度均值為favg，個體適應度最大值、最小值分別為fmax、fmin, 交叉與變異的適應度分別為f′和f[11]，則有

(17)

(18)

不斷進化迭代，直到復合語言文本分類精度達到要求或者達到最大迭代次數，算法停止，獲得經過優化后的加權樸素貝葉斯算法的最佳權重和閾值。

2.2 QA進化的量子比特表示

為了進一步提高GA對屬性權重的優化效率，引入量子比特表示。量子運算基本方法[12]為

(19)

(20)

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

(21)

式中θ為量子比特中的另一個實數。α和β可以采用量子方法計算。

最后得到QGA優化WNBA復合語言文本分類模型。

2.3 QGA優化WNBA復合語言文本分類流程

QGA優化WNBA復合語言文本分類流程如圖1所示。在復合語言文本分類過程中，首先構建加權樸素貝葉斯分類模型，然后求解不同權重條件下的遺傳個體適應度值，隨后進行GA權重優化，在交叉等計算過程中，結合量子比特計算，最后獲得最優權重個體。通過復合語言文本分類精度及迭代次數上限值來確定最終的分類模型。

圖1 量子遺傳算法(QGA)優化加權樸素貝葉斯復合語言文本分類流程

3 實例仿真

為了驗證QGA優化WNBA復合語言文本分類性能，首先對WNBA算法和QGA優化WNBA算法分別進行性能仿真，驗證QGA的優化性能；其次采用常見語言文本分類算法和本文中提出的QGA優化WNBA算法分別進行仿真，驗證不同分類算法的語言文本分類性能。分類性能指標為準確率、召回率和精確率與召回率的調和平均值F1。

復合語言文本仿真的數據來源為某知名跨境電商平臺，通過對5種熱銷產品的用戶評論數據進行分類，統計用戶評價結果。用戶評論語言包括中、英、法、韓、日等語種。根據5種產品構成5個數據集，樣本數量及需要分類的類別數分別如表1所示。

3.1 QGA的優化性能

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

表1 復合語言文本集

表2 量子遺傳算法(QGA)的優化性能對比

不同算法的分類時間性能如圖2所示。由圖可以看出，3種算法對數據集4的分類耗時最少，對數據集3的分類耗時最長，原因是復合語言文本的分類時間主要取決于樣本量和類別數，數據集3待分類樣本量最大且待分類的類別數最多，而數據集4正好相反。對比發現，NBA的復合語言文本分類耗時最短，而WNBA和QGA優化WNBA的分類時間相差很小，這是因為NBA沒有權重參數的求解過程，所以更省時，而WNBA和QGA優化WNBA均需要權重求解，但是通過實驗發現，QGA優化并未增加時間消耗，原因是通過QGA優化后求解最優屬性權重的時間變短。

NBA—樸素貝葉斯算法；WNBA—加權樸素貝葉斯算法；QGA—量子遺傳算法。

3.2 不同算法的復合語言文本分類性能

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

(a)數據集1

對4種算法在復合語言文本的分類穩定性進行仿真，驗證4種算法的準確率均方根誤差(RMSE)性能，結果見表3。從表中可以看出，對于5個數據集，QGA優化WNBA的分類準確率RMSE值最優，SVM表現最差。其中，4種算法在數據集4的RMSE性能表現最優，在數據集3的RMSE性能最差，這可能是因為數據集1待分類的類別數最少，而數據集3需要分類的類別數最多，在高維復合語言文本分類時，類別過多造成了分類準確率值在多次分類中波動較大，這也說明分類準確率RMSE值對分類類別數較為敏感，在對多類別進行分類時，需要采取合理措施來控制分類準確率波動。

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

4 結語

本文中提出將QGA優化WNBA應用于復合語言文本分類，充分利用QGA的權重優化優勢，提高了WNBA在多語言文本分類中的適用度，相比于常用復合語言文本分類算法，本文中提出的算法在分類準確率及RMSE性能方面優勢明顯。后續研究將進一步優化QGA求解，以優化分類時間性能，為大規模復合語言文本的分類研究提供參考。