文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.181392
中文引用格式: 康衛(wèi),邱紅哲,焦冬冬,等. 基于搜索的短文本分類算法研究[J].電子技術(shù)應(yīng)用,2018,44(11):121-123,128.
英文引用格式: Kang Wei,Qiu Hongzhe,Jiao Dongdong,et al. Search-based short-text classification[J]. Application of Electronic Technique,2018,44(11):121-123,128.
0 引言
文本分類(Text Classification)是指在給定的分類體系下,由計算機通過某種分類算法將未知類別的文本進行自動歸類的過程。最近十幾年,文本分類得到了迅速的發(fā)展,并且被廣泛應(yīng)用到許多領(lǐng)域,包括:數(shù)字圖書館、網(wǎng)頁分類、垃圾電子郵件過濾等。到目前為止,已經(jīng)有許多基于統(tǒng)計學理論和機器學習的文本分類方法,如決策樹(Decision Tree)、貝葉斯方法、KNN、神經(jīng)網(wǎng)絡(luò)、支持向量機(SVM)等[1]。然而,這些分類方法的研究和應(yīng)用都是基于長文本的,而目前短文本在網(wǎng)絡(luò)上使用越來越普遍。最近新興起的微博客的最大的特點就是“微”,一般發(fā)布的消息只能是只言片語。著名流量統(tǒng)計網(wǎng)站ALEXA的數(shù)據(jù)顯示,Twitter日均訪問量已近2 000萬人次,在美國、英國、加拿大等地的網(wǎng)站排名中均列前15位。在專業(yè)或者垂直搜索領(lǐng)域,由于資源限制,無法對全文進行處理,轉(zhuǎn)而根據(jù)文章標題或文章摘要進行分類。這些應(yīng)用場合都需要短文本分類技術(shù)。針對實際的需求以及傳統(tǒng)方法的不足,本文提出了一種新的分類方法,利用搜索實現(xiàn)基于類似NaiveBayes的文本分類方法。對比實驗表明,在短文本的分類上,此方法比傳統(tǒng)的分類方法提高了準確率和分類速度。
1 相關(guān)工作介紹
在過去的四十多年中,許多關(guān)于文本分類的研究工作都是圍繞著Salton提出的向量空間模型(VSM)展開的,向量空間模型的基本思想是以向量來表示文本:(W1,W2,…,Wn),首先將文本進行分詞,由這些詞作為向量的維數(shù),用詞頻來表示特征項對應(yīng)的向量分量,詞頻計算方法主要運用TF-IDF公式。對于向量空間法的研究工作主要集中在特征選取和特征權(quán)重的調(diào)整上來提高分類的性能,如陸玉昌先生在特征選取中利用評估函數(shù)代替TF-IDF公式進行權(quán)值調(diào)整[2]。
神經(jīng)網(wǎng)絡(luò)學習算法在文本分類中的研究和應(yīng)用也非常廣泛,其中最流行的神經(jīng)網(wǎng)絡(luò)算法是1986年由RUMELHARD D E和MCCLELLAND J L提出的后向傳播算法(簡稱BP算法)[3]。由于BP算法存在收斂速度慢、容易陷入局部極小值等問題,后人對BP算法進行了多方面的改進,如李曉峰提出了BP神經(jīng)網(wǎng)絡(luò)動態(tài)全參數(shù)自動調(diào)整學習算法[4]。神經(jīng)網(wǎng)絡(luò)擁有很好的對噪音數(shù)據(jù)的承受能力和文本分類能力,但是需要大量的參數(shù),這些通常主要靠經(jīng)驗確定。另外神經(jīng)網(wǎng)絡(luò)需要很長的訓練時間,因此它適用于有足夠長訓練時間的應(yīng)用。
王建會等提出了基于互依賴和等效半徑、簡單但高效的分類算法SECTILE[5],該方法提出互依賴(Mutual Dependence,MD)模型,并將其與N-gram結(jié)合起來進行特征屬性選擇,提高了屬性選擇的準確性,實現(xiàn)了有效地降維。引入等效半徑(Equivalent Radius,ER)的概念,用基于等效半徑的相對距離代替?zhèn)鹘y(tǒng)的歐氏距離,提高了分類精度。SECTILE分類算法計算復雜度低,分類模型容易更新,適用于大規(guī)模信息樣本分類場合。
石志偉等提出了向量空間法和k近鄰的組合分類方法[6],該方法將整個實例空間劃分為正實例、負實例和混合實例三部分,根據(jù)查詢實例落入不同的區(qū)域調(diào)用不同的分類算法。該方法充分利用了向量空間法分類速度快和k近鄰方法分類精度高的優(yōu)勢。
以上提到的各種分類方法都適用于長文本的分類,由于短文本相對于長文本要短得多,文本中的特征數(shù)很少,并且文本之間很少含有相同的特征,因此傳統(tǒng)的文本分類方法并不適合短文本分類。目前專門研究短文本分類的工作還較少,大致分為兩種研究方向:一種是通過外部資源來增加文本之間共享的特征,豐富文本的上下文,例如Wikipedia被作為外部資源引入短文本分類中[7],從而可以使用傳統(tǒng)的文本分類方法;另一種是充分利用這些稀疏的特征,對短文本進行預處理。下面介紹一些針對短文本分類的研究工作。
蒲強等提出基于獨立分量分析(Independent Component Analysis,ICA)和潛在語義分析(Latent Semantic Analysis,LSA)的短文本分類方法[8],該方法首先通過LSA對文本進行預處理,然后對處理結(jié)果再進行獨立分量分析。LSA利用奇異值分解(Singular Value Decomposition,SVD)降秩方法實現(xiàn)信息抽取和噪聲去除,將文檔的高維表示投影在低維的潛在語義空間中,從而呈現(xiàn)出潛在的語義結(jié)構(gòu)。然而對原始詞——文檔矩陣進行SVD,選取最大的一些奇異值對應(yīng)的特征作為潛在語義空間,目前沒有理論證明奇異值最大的那些特征具有最好的分類能力,所以在該潛在語義空間上進行文本分類,分類效果并沒有得到改善。
滕少華等提出基于條件隨機場(Conditional Random Fields,CRFs)的短文本分類方法[9],該方法認為短文本通常集中于一個主題,從而文本中的特征也具有很強的相關(guān)性。根據(jù)這種性質(zhì),該方法利用中文分詞中的字標注方法,將短文本分類問題轉(zhuǎn)化成序列標注問題,從而可以使用CRFs來解決短文本分類問題。然而CRFs依賴于高置信度特征,高置信度特征也可以引入干擾,這樣就很容易導致分詞錯誤,這種困難很難依靠CRFs自身來解決。雖然可以通過對基于CRFs的分詞結(jié)果進行后處理來解決該問題,但是這種方法有它的局限性,只能使用基于CRFs的中文分詞。
綜上所述,目前的短文本分類方法不能有效地選擇那些分類能力好的特征,分類準確度低,分類速度慢;或者依賴于中文分詞系統(tǒng),擴展性差。本文提出的基于搜索的Na?觙veBayes文本分類方法在這些方面進行了改進。
2 基于搜索的樸素貝葉斯分類算法
基于搜索的樸素貝葉斯文本分類是將搜索技術(shù)應(yīng)用到文本分類中,并對樸素貝葉斯分類算法進行改進,從而實現(xiàn)的一種適合短文本分類的分類方法。分類算法如下:
令C={c1,c2,…,cm}是預定義的類別集,D={d1,d2,…,dn}是待分類的文檔集,d={w1,w2,…,wn}是一個文檔的特征向量,文檔di屬于類別cj的概率可以由條件概率P(cj|di)表示。根據(jù)貝葉斯公式:
式(2)、式(4)中,|c|為文本的類別數(shù),分子上的1是為了防止出現(xiàn)概率為零的情況進行的加權(quán)處理。
為了計算簡便,不妨在選取訓練數(shù)據(jù)時規(guī)定各類別中的文本數(shù)一樣多。這樣,對于每一個文本類別來說,先驗概率是相等的,計算P(cj)的過程也可以忽略不計。計算貝葉斯概率也就簡化成了計算文檔di屬于類別cj的后驗概率:
在式(5)中,對于每一類別來說,分母部分N(cj)+|c|是相等的,即不影響屬于每一類別的概率大小比較,這樣就直接計算:
而為了防止出現(xiàn)負無窮和零的情況,只需要知道每一個屬性(詞)在指定類別中出現(xiàn)的文檔個數(shù),即N(wi|cj)。
結(jié)合上面的公式推導,可以將基于搜索的NaiveBayes文本分類算法描述如下:
(1)假定有m個類別C1,C2,…,Cm。分別對每一類別中的數(shù)據(jù)樣本進行中文分詞,建立索引CIndex1,CIndex2,…,CIndexm;
(2)給定一個沒有類標號的數(shù)據(jù)樣本X,對其進行中文分詞(分詞系統(tǒng)要和步驟(1)用到的分詞系統(tǒng)保持一致),每個詞對應(yīng)一個屬性,分別為W1,W2,…,Wn;
(3)求將數(shù)據(jù)樣本X分配給類別Cj的概率,即:
換言之,X被分配到使P(w|ci)最大的類別Ci。
注意:步驟(1)也可以看作是建立分類模型,此步不影響分類的速度,因為建立分類模型是在進行文本分類之前做的?;谒阉鞯腘aiveBayes分類器模型是對已知類標號的訓練數(shù)據(jù)集建立的索引,并且各個類別的訓練數(shù)據(jù)文本數(shù)是相等的。這也是基于搜索的NaiveBayes分類器和其他分類器的不同之處。為了提高速度,本文使用了Lucene.Net搜索技術(shù)。Lucene.Net中自帶的StandardAnalyzer分詞器是以字為單位索引的,對于中文文本分類來說,按單字分詞會影響分類的精度,所以本文使用了KTDictSeg分詞系統(tǒng),KTDictSeg是由KaiToo搜索開發(fā)的一款基于字典的開源的中英文分詞系統(tǒng)。KTDictSeg可以識別中文人名,還有對Lucene.net 的支持,提供KTDictSegAnalyzer 分析器給Lucene.net。
分類器效率的評估結(jié)果可以有多種,比如分類的準確率、速度、可規(guī)模性等。而評估的方法也有多種,最簡單的是保持(Holdout)方法,即使用類標號已知的數(shù)據(jù)來測試分類器。在認為分類器的準確率可以接受時,就可以利用此分類器對類標號未知的數(shù)據(jù)進行分類預測。
3 實驗及結(jié)果分析
對于中文文本分類而言,目前還沒有標準的語料庫可供使用。因此,本文使用搜狗實驗室整理的語料庫(SogouC.reduced.20061127),此語料庫包含了九個類別,分別是財經(jīng)、IT、健康、體育、旅游、教育、招聘、文化、軍事,每一類包含1 990篇文章。對此語料庫做一下簡單整理,從每一類中隨機選出160篇文章作為測試數(shù)據(jù),用剩余的1 830篇文章作為訓練數(shù)據(jù)建立分類模型。用準備好的測試數(shù)據(jù)對基于搜索的NaiveBayes文本分類器和weka的NaiveBayes文本分類器進行測試,測試結(jié)果如表1所示。
從表1可以看出,基于搜索的NaiveBayes分類器和weka的NaiveBayes分類器不相上下。但是,為了體現(xiàn)基于搜索的NaiveBayes分類器對于短文本分類的優(yōu)越性,對這1 440篇測試數(shù)據(jù)做一下簡單處理后再次進行測試,即每一類中包含50字以內(nèi)的文本50篇、50~200字的文本50篇、200~1 000字的文本50篇和1 000字以上的文本50篇。這樣測試數(shù)據(jù)就按照文本字數(shù)的多少分為了不同的等級,并且測試數(shù)據(jù)文本數(shù)也增加到了1 800篇。然后用整理后的測試數(shù)據(jù)對兩種分類器進行測試,測試結(jié)果如表2所示。
根據(jù)表2的數(shù)據(jù)繪制出分類準確率的曲線圖,如圖1所示。
通過圖1可以清楚地看到,對于100字以內(nèi)的短文本的分類,基于搜索的NaiveBayes分類器在分類精度方面表現(xiàn)出了優(yōu)越的性能。通過表2和表1的比較也不難發(fā)現(xiàn),對于1 440篇長文本的分類,基于搜索的NaiveBayes分類器耗時12.587 5 s;而對于加入了短文本的1 800篇文本的分類,基于搜索的NaiveBayes分類器耗時13.006 2 s。從數(shù)字上可以看出,對于短文本的分類,基于搜索的NaiveBayes分類器在分類速度上也明顯提高。
這說明基于搜索的NaiveBayes分類方法對短文本的處理得到了很好的分類效果,并且并沒有因為選取全部的文本特征而降低分類速度,相反,由于搜索技術(shù)的引入,從某種程度上還提高了文本分類的速度。
4 結(jié)論
本文針對傳統(tǒng)的文本分類方法對短文本分類的不足,提出了基于搜索的NaiveBayes文本分類方法。該方法與傳統(tǒng)的文本分類方法的不同之處在于,它將搜索引擎技術(shù)應(yīng)用到了文本分類中,并對樸素貝葉斯分類算法進行了改進。實驗結(jié)果表明,對于短本文的分類,基于搜索的NaiveBayes分類方法不僅大大提高了分類的準確度,同時降低了時間復雜度。另外,在文本特征提取和中文文本停詞的處理方面,針對不同的應(yīng)用背景還需要做進一步的研究。實驗用的語料庫不是標準的語料庫,僅僅有17 910篇文章,因此,實驗的規(guī)模有待進一步擴大。在應(yīng)用前景方面,隨著通信技術(shù)和互聯(lián)網(wǎng)的發(fā)展,電子郵件、短信、微博信息等各種短文本信息迅速增加,基于搜索的NaiveBayes文本分類器必將會得到廣泛的應(yīng)用。
參考文獻
[1] Wu Xindong,KUMAR V,QUINLAN J R,et al.Top 10 algorithms in data mining[J].Knowl.Inf.Syst.,2008(14):24-27.
[2] 陸玉昌,魯明羽,李凡,等.向量空間法中單詞權(quán)重函數(shù)的分析和構(gòu)造[J].計算機研究與發(fā)展,2002,39(10):1205-1210.
[3] RUMELHART D E,MCCLELLAND J L.Parallel distributed processing:explorations in microstructure of cognition,Vol.1:Foundations[M].Cambridge:MIT Press,1986:318-364.
[4] 李曉峰.動態(tài)全參數(shù)自調(diào)整BP神經(jīng)網(wǎng)絡(luò)預測模型的建立[J].預測,2001,20(3):69-71.
[5] 王建會,王洪偉,申展,等.一種實用高效的文本分類算法[J].計算機研究與發(fā)展,2005,42(1):85-93.
[6] 石志偉,劉濤,吳功宜.一種快速高效的文本分類方法[J].計算機工程與應(yīng)用,2005,41(29):180-183.
[7] SCHONHOFEN P.Identifying document topics using the Wikipedia category network[C].Proc.the IEEE/WIC/ACM International Conference on Web Intelligence,2006:456-462.
[8] Pu Qiang,Yang Guowei.Short-text classification based on ICA and LSA[C].Berlin:Springer-Verlag Berlin/Heidelberg,2006:265-270.
[9] 滕少華.基于CRFs的中文分詞和短文本分類技術(shù)[D].北京:清華大學,2009.
作者信息:
康 衛(wèi)1,邱紅哲2,焦冬冬1,房志奇1,于寅虎1
(1.華北計算機系統(tǒng)工程研究所,北京100083;2.北京航天飛行控制中心,北京100094)