基于樸素貝葉斯的垂直搜索引擎分類器設(shè)計

于秀麗，王陽，齊幸輝

（1.天津科技大學(xué)，天津 300222；

2.河北遠東通信系統(tǒng)工程有限公司，河北 石家莊 050200）

基于樸素貝葉斯的垂直搜索引擎分類器設(shè)計

于秀麗1，王陽2，齊幸輝2

（1.天津科技大學(xué)，天津 300222；

2.河北遠東通信系統(tǒng)工程有限公司，河北 石家莊 050200）

隨著互聯(lián)網(wǎng)的網(wǎng)頁數(shù)量呈現(xiàn)爆炸式增長，傳統(tǒng)的通用搜索引擎越來越遭人詬病，查詢不準、深度不夠等問題，使用戶倍感煩惱。因此，針對特定行業(yè)的垂直搜索引擎逐漸興起，與之相關(guān)的研究也日益受到重視。網(wǎng)頁分類是垂直搜索引擎的基礎(chǔ)和難點，分類器的好壞直接決定了一個垂直搜索引擎系統(tǒng)的性能?；跇闼刎惾~斯的垂直搜索引擎分類器通過CHI方法進行特征提取，利用樸素貝葉斯模型對從互聯(lián)網(wǎng)爬取的網(wǎng)頁按內(nèi)容類別進行分類。實驗結(jié)果表明，該分類器對網(wǎng)頁分類有著良好的表現(xiàn)，為構(gòu)建大型專業(yè)的垂直搜索引擎系統(tǒng)奠定了一定的理論基礎(chǔ)。

樸素貝葉斯；垂直搜索引擎；特征提?。晃臋n分類

0 引言

所謂垂直搜索引擎，是針對某一個行業(yè)或類別的專業(yè)搜索引擎，其特點是“專、精、深”，且具有行業(yè)色彩，相比傳統(tǒng)通用搜索引擎的海量信息無序化，垂直搜索引擎則更加專注、具體和深入［1］。

2006年以來，國內(nèi)垂直搜索引擎與相關(guān)行業(yè)相結(jié)合，在IT信息、房地產(chǎn)、招聘、購物和醫(yī)療等方面發(fā)展迅速。但與國外相比，無論是在技術(shù)層面還是在行業(yè)經(jīng)驗上都還有很大差距，這大大限制了垂直搜索引擎的發(fā)展，使得專業(yè)化搜索服務(wù)還無法在社會的各個領(lǐng)域得到廣泛發(fā)展［2］。因此，加大對垂直搜索引擎的研究有著重大的現(xiàn)實意義。

而網(wǎng)頁分類是垂直搜索引擎的基礎(chǔ)和難點，分類器的好壞直接決定了一個垂直搜索引擎系統(tǒng)的性能［3］，進而決定了所占市場的比例。本文利用CHI算法進行特征提取，以樸素貝葉斯算法為基礎(chǔ)，構(gòu)建了一個以網(wǎng)頁分類為目標的垂直搜索引擎分類器，并對其準確率和招回率進行了詳細的研究和分析。結(jié)果證明基于樸素貝葉斯算法的分類器對網(wǎng)頁文類有著良好的表現(xiàn)。最后，利用Java、JS等Web開發(fā)語言和開源的Luence搜索引擎工具包［4］，構(gòu)建簡易的基于BS架構(gòu)的垂直搜索引擎系統(tǒng)。

1 關(guān)鍵技術(shù)

1.1 CHI特征選擇法

利用CHI方法選擇文本的特征是基于如下假設(shè)：在指定類別文本中出現(xiàn)頻率高的詞條與在其他類別文本中出現(xiàn)頻率高的詞條，對判定文檔是否屬于該類別是有幫助的［5］。

單詞term與類別class依賴關(guān)系的CHI統(tǒng)計公示如下：

CHI統(tǒng)計變量定義表如表1所示。

表1 CHI統(tǒng)計變量定義

類別class越依賴于單詞term，則CHI統(tǒng)計值越大。如果term和class是相互獨立的，則該值接近于0。

1.2 樸素貝葉斯模型

在人工智能領(lǐng)域，貝葉斯方法是一種非常具有代表性的不確定性知識表示和推理方法。簡單地說，貝葉斯定理是基于假設(shè)的先驗概率、給定假設(shè)下觀察到不同數(shù)據(jù)的概率，提供了一種計算后驗概率的方法［6］。

對樸素貝葉斯算法定義如下：

①設(shè)X＝[a1，a2，…an]為一個待分類項，每個ai都為X的一個特征屬性，而且每個特征屬性都是相互獨立的；

②設(shè)C＝[y1，y2，…yn]為一個類別集合；

③計算P(y1｜X)，P(y2｜X)，P(y3｜X)，…P(yn｜X)。

④P(yk｜X)＝max｛P(y1｜X)，P(y2｜X)，P(y3｜X)，…P(yn｜X)｝，則X∈yk。

2 垂直搜索引擎分類器的構(gòu)建

本文以從搜狐網(wǎng)爬取的IT、招聘、體育和軍事類網(wǎng)頁作為訓(xùn)練集和測試集，利用樸素貝葉斯方法構(gòu)建垂直搜索引擎分類器，對網(wǎng)頁進行分類。

2.1 特征選取

首選通過CHI特征提取法獲取每種類別的網(wǎng)頁所具有的文本特征。設(shè)C、M、S和W分別代表IT類、招聘類、體育類和軍事類。以體育類為例，特征選取流程如下：

①構(gòu)建訓(xùn)練數(shù)據(jù)集：從網(wǎng)上爬取此種類別的網(wǎng)頁N篇作為訓(xùn)練數(shù)據(jù)集。此處的N應(yīng)盡量大，使其能夠充分挖掘該類別的內(nèi)容特征［7］。選取權(quán)威網(wǎng)站上IT、招聘、體育和軍事行業(yè)網(wǎng)頁各100篇，作為網(wǎng)頁的原始訓(xùn)練數(shù)據(jù)集。

②去噪處理：將訓(xùn)練數(shù)據(jù)集中的網(wǎng)頁進行去噪處理，即去除網(wǎng)頁中與內(nèi)容無關(guān)的Html標簽和JavaScript代碼，獲取代表實質(zhì)內(nèi)容的中文段落。

③分詞處理：將獲取的中文段落劃分成一個個分詞，并且將其中無意義、明顯不能作為特征的詞去掉，如“的”，“是”，“或者”等等。

經(jīng)過以上處理，數(shù)據(jù)集中包含大量文字的網(wǎng)頁已經(jīng)被用一個中文分詞集合表示，如某體育類網(wǎng)頁可以表示成Si＝［體育、NBA、比賽、騎士、凱爾特人、詹皇、速貸球館……詹姆斯、季后賽、首發(fā)、投籃］。

將所有表示體育類網(wǎng)頁的中文分詞集合做合并運算，即SA＝S1∪S2∪S3∪…Sn，則SA便是體育類網(wǎng)頁的中文分詞庫。同理可以得到IT類、招聘類和軍事類的中文分詞庫CA、MA和WA。設(shè)TA＝SA∪CA∪MA∪WA，則TA為候選分類特征集合。接下來通過CHI統(tǒng)計公式獲得類別的真正分類特征。

④設(shè)TA＝[t1，t2，t3，…tn]，依次計算TA中每個候選特征與體育類別S的依賴關(guān)系值chi＿dependency(ti，S)，取使chi＿dependency數(shù)值最大的n項候選特征詞匯組成數(shù)組SR，即SR＝［sm1，sm2，sm3…，smn］，則SR即為體育類的真正分類特征集合。

通過以上方法，可以依次獲取IT、招聘、體育和軍事類網(wǎng)頁的真正分類特征集合，分別設(shè)為CR、MR、SR和WR。

2.2 根據(jù)分類特征進行分類

根據(jù)前文介紹的樸素貝葉斯分類器分類原理，需計算P(yi｜X)，以此來判斷樣本屬于哪一個類別。由于X＝[a1，a2，…an]，每個ai都為X的一個特征屬性，因此需計算每個特征屬性對于該類的影響力。

通過前文的特征選取方法已經(jīng)得到的體育類的特征集合為SR＝［sm1，sm2，sm3…，smn］。由于篇幅的限制，在這里選取n＝20即選取與類別最具有依賴關(guān)系的前20個中文分詞作為類別的分類特征。通過計算，CR＝［IT、互聯(lián)網(wǎng)、網(wǎng)絡(luò)、andoid、電商、虛擬、阿里巴巴、云計算、支付、…］，MR＝［招聘、簡歷、職位、薪資、企業(yè)、經(jīng)驗、崗位、行業(yè)、技術(shù)、…］，SR＝［體育、比賽、NBA、CBA、中超、亞冠、賽季、對手、歐冠、勝、…］，WR＝［軍事、美國、武器、軍方、導(dǎo)彈、戰(zhàn)略、南海、解放軍、擊敗、…］。設(shè)CMSWR＝CR∪MR∪SR∪CWR，CMSWR中的每個分類特征將作為文檔屬性參與到分類過程中。

以之前的100篇體育類文檔作為訓(xùn)練集，來計算SR中每個分類特征對類別的影響力。以“體育”為例，訓(xùn)練集中的100篇體育類文檔中有89篇均包含“體育”，則包含“體育”的網(wǎng)頁屬于體育類的概率為89／100；

假設(shè)每個分類特征都是獨立的，即出現(xiàn)在網(wǎng)頁中的分詞都是隨機出現(xiàn)的。因此，

P（yi｜X）＝P（a1｜yi）P（a2｜yi）…P（an｜yi）。

即假設(shè)有待測文本X＝[a1，a2，…an]，屬于yi的概率為訓(xùn)練數(shù)據(jù)中各屬性值出現(xiàn)的概率之積［8］。

2.3 分類示例

根據(jù)樸素貝葉斯算法定義，假設(shè)有類別C＝[y1，y2，…yn]，待測文本屬于哪個類別的概率最高，就將該文本劃分為那一類。

假設(shè)有網(wǎng)頁文本TXT＝“馬云和王健林關(guān)于O2O又展開了一輪對掐，因為涉及電商核心價值，我認為兩人在價值的判斷上，是真掐，特別是馬云，刀刀見肉。特別值得傳統(tǒng)企業(yè)借鑒。阿里巴巴馬云表示，互聯(lián)網(wǎng)經(jīng)濟不是虛擬經(jīng)濟，互聯(lián)網(wǎng)經(jīng)濟是實體經(jīng)濟與虛擬經(jīng)濟的結(jié)合體。互聯(lián)網(wǎng)企業(yè)要活得好，就要提供普惠性技術(shù)?！?/p>

經(jīng)統(tǒng)計，訓(xùn)練集與分類特征是否包含的數(shù)量關(guān)系如表2所示。

表2 訓(xùn)練集分類特征分布表

其中C、M、S、W分別代表IT類，招聘類、體育類和軍事類。Ctermi、Mtermi、Stermi、Wtermi代表CMSWR中屬于C、M、S、W的第i個分類特征。如第2行第2列的數(shù)字41代表IT類的第1個分類特征，即“IT”這個分詞在100篇IT類網(wǎng)頁中的其中41篇都出現(xiàn)了。

下面根據(jù)樸素貝葉斯算法依次計算網(wǎng)頁文本TXT屬于C、M、S、W的概率。

將文本TXT表示成一個向量TXT＿V，長度為集合CMSWR的大小。向量中的項代表TXT中是否包含CMSWR的分類特征。以IT類為例，由于TXT中包含了“互聯(lián)網(wǎng)”、“電商”、“虛擬”、“阿里巴巴”4個IT類的分類特征詞匯，所以TXT＿V＝（互聯(lián)網(wǎng)：1，電商：1，虛擬：1，阿里巴巴：1，網(wǎng)絡(luò)：0，…，招聘：0；簡歷：0；公司：1；…體育：0；比賽：0；…軍事：0；美國：0；…）。

將TXT＿V中的每一項Ti作為文檔的一個特征屬性，指定一個類別，針對每一個特征屬性Ti的屬性值計算待測樣本屬于這個類別的概率Pi。Pi的計算方法為［9］：

設(shè)T的長度為len，則TXT屬于某類別的概率為：

說明：之所以在計算Pi時分子加1／n，是為了防止某個屬性值的概率出現(xiàn)0的情況。因為在計算belong（TXT，C）的時候，其他的概率將與這個0相乘，因此不管其他屬性的概率有多大，最終的結(jié)果都是0，因此根據(jù)頻率來計算概率的方法，進行一些小的調(diào)整，這種方法被成為拉普拉斯估算器［10］。

根據(jù)以上公式，分別計算文檔TXT屬于IT類、招聘類、體育類和軍事類的概率，屬于哪個類別的概率最高，就將TXT歸為哪個類別。為了便于計算，將計算結(jié)果取對數(shù)得：

由以上計算結(jié)果看出，TXT屬于類別C的概率最大，因此將文本TXT歸為IT類。

3 分類結(jié)果與結(jié)論

3.1 實驗結(jié)果

以不同于訓(xùn)練集的IT類、招聘類、體育類和軍事類各100篇作為測試集，來驗證樸素貝葉斯模型的分類效果。

經(jīng)分析可得，分類特征作為判定是否屬于某個類別的主要依據(jù)，分類特征的選取對于網(wǎng)頁分類的效果有著至關(guān)重要的影響［11］。與類別最具有依賴關(guān)系的前20個中文分詞未必能夠代表該類別的內(nèi)容特征，因此在測試過程中，分別選取n＝20、n＝30和n＝50，來驗證分類效果。

通過正確率和召回率來量化實驗結(jié)果［12］，具體數(shù)據(jù)如表3所示。

表3 統(tǒng)計結(jié)果

3.2 實驗結(jié)論

根據(jù)表數(shù)據(jù)，可得如下結(jié)論：

①當n＝50時，統(tǒng)計結(jié)果的準確率和召回率都在90%以上，足以說明利用樸素貝葉斯模型進行網(wǎng)頁分類是可行的。

②當n＝20時，IT類統(tǒng)計結(jié)果的正確率只有66.7%，且返回樣本數(shù)高達132，可知其他類別中往往包含IT類的特征詞匯。選出的分類特征區(qū)分度不夠。

③分類特征的選取對于統(tǒng)計結(jié)果有著至關(guān)重要的影響［10］，n越大，分類特征越能代表整個類別的特征，統(tǒng)計結(jié)果越準確。

4 構(gòu)建簡易垂直搜索引擎

有了以上的算法基礎(chǔ)，便可以利用Java和JS等Web開發(fā)語言和開源的Luence搜索引擎工具包構(gòu)建一個基于BS架構(gòu)的簡易垂直搜索引擎系統(tǒng)，過程如下：

①用Java編程語言編寫網(wǎng)絡(luò)爬蟲，從互聯(lián)網(wǎng)上抓取有效網(wǎng)頁，并進行去重、去噪等處理。

②利用前文基于樸素貝葉斯算法的分類器對抓取到的網(wǎng)頁按類別分類。

③利用Luence搜索引擎開源包，為分好類的網(wǎng)頁建立索引，將其存儲至數(shù)據(jù)庫，并實現(xiàn)排序算法。

④Tomcat服務(wù)器搭建B／S環(huán)境，利用js和HTML語言編寫客戶端界面，根據(jù)用戶輸入的類別和關(guān)鍵字展示搜索結(jié)果。

5 結(jié)束語

介紹了基于樸素貝葉斯模型的垂直搜索引擎分類器的實現(xiàn)算法，實驗表明在根據(jù)類別進行網(wǎng)頁分類的過程中有著良好的表現(xiàn)［13］，為構(gòu)建大型專業(yè)的垂直搜索引擎奠定了一定的理論基礎(chǔ)。垂直搜索引擎是傳統(tǒng)搜索引擎的升級和延伸，是對網(wǎng)頁庫中某類信息的又一次整合。相信在不久的將來，越來越多的科技工作者會投入到垂直搜索引擎的研究中來。而采用更多數(shù)據(jù)挖掘的方法，對互聯(lián)網(wǎng)網(wǎng)頁進行有效處理，提高分類的準確度和速度，則是垂直搜索引擎研究的方向［14］。

［1］胡永鋒.淺談垂直搜索引擎的工作原理［J］.科學(xué)大眾（科學(xué)教育），2011（6）：171.

［2］王文鈞，李 巍.垂直搜索引擎的現(xiàn)狀與發(fā)展研究［J］.情報科學(xué)，2010，28（3）：477－450.

［3］張紅斌，曹義親.混合多層分類和樸素貝葉斯模型的垂直搜索引擎分類器設(shè)計［J］.現(xiàn)代圖書情報技術(shù)，2011（3）：73－79.

［4］任曉娜.基于Lucene的全文搜索引擎的研究與實現(xiàn)［J］.湖北廣播電視大學(xué)學(xué)報，2010，30（5）：158－159.

［5］羅 剛，王振東.自己動手寫網(wǎng)絡(luò)爬蟲［M］.北京：清華大學(xué)出版社，2012.

［6］HAN Jiawei，KAMBER Micheline，PEI Jian.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京：機械工業(yè)出版社，2012.

［7］石志偉，吳功宜.改善樸素貝葉斯在文本分類中的穩(wěn)定性［C］∥NCIRCS2004第一屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會議論文集，中國上海，2004：143－152.

［8］WITTEN Ian H，F(xiàn)RANK Eibe.數(shù)據(jù)挖掘?qū)嵱脵C器學(xué)習(xí)技術(shù)［M］.北京：機械工業(yè)出版社，2012.

［9］王樹文，鄭闊實，陳靜博.面向教育主題的垂直搜索引擎的設(shè)計與實現(xiàn)［J］.長春師范學(xué)院學(xué)報（自然科學(xué)版），2013（2）：40－43.

［10］余 芳，姜云飛.一種基于樸素貝葉斯分類的特征選擇方法［J］.中山大學(xué)學(xué)報（自然科學(xué)版），2004，43（5）：118－120.

［11］菅小燕，崔彩霞.基于樸素貝葉斯的文本分類［J］.電腦開發(fā)與應(yīng)用，2013（12）：58－59.

［12］盧 葦，彭 雅.幾種常用文本分類算法性能比較與分析［J］.湖南大學(xué)學(xué)報（自然科學(xué)版），2007（6）：72－74.

［13］李靜梅，孫麗華，張巧榮，等.一種文本處理中的樸素貝葉斯模型［J］.哈爾濱工程大學(xué)學(xué)報，2003，24（1）：71－74.

［14］余 淼，楊 丹，趙俊芹.垂直搜索引擎的關(guān)鍵技術(shù)研究［J］.軟件導(dǎo)刊，2007（23）：31－33.

Design of Vertical Search Engine Classifier Based on Naive Bayes

YU Xiu-li1，WANG Yang2，QI Xing-hui2
（1．Tianjin University of Science and Technology，Tianjin 300222，China；2．Hebei Far East Communication System Engineering Co．，Ltd．，Shijiazhuang Hebei 050200，China）

Along with the explosive growth of Internet pages，traditional universal search engines are more and more complained for problems such as inaccurate search and insufficient depth.Therefore，vertical search engine for special industries gradually emerges，and the associated researches attract more and more attention.Internet page classification is the basis and difficult point of vertical search engine.The quality of the classifier directly determines the performance of a vertical search engine system.The vertical search engine classifier based on naive Bayes extracts the features through CHI method，and then by using the naive Bayes model，it classifies the pages crawled from the Internet according to the contents.The experimental result shows that such classifier has good performance in classifyingInternet pages，which provides certain theoretical foundation for the construction of large-scale vertical search engine system.

naive Bayes classifier；vertical search engine；featureextraction；document classification

TP391

A

1003－3106（2015）11－0013－04

10.3969／j.issn.1003－3106.2015.11.04

于秀麗，王 陽，齊幸輝.基于樸素貝葉斯的垂直搜索引擎分類器設(shè)計［J］.無線電工程，2015，45（11）：13－16，25.

于秀麗女，（1976—），講師。主要研究方向：計算機智能計算。

2015-08-06

齊幸輝男，（1977—），高級工程師。主要研究方向：信息通信技術(shù)。