于秀麗，王陽，齊幸輝

（1.天津科技大學，天津 300222；

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

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

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

（1.天津科技大學，天津 300222；

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

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

樸素貝葉斯；垂直搜索引擎；特征提??；文檔分類

0 引言

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

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

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

1 關鍵技術

1.1 CHI特征選擇法

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

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

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

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

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

1.2 樸素貝葉斯模型

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

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

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

②設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 垂直搜索引擎分類器的構建

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

2.1 特征選取

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

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

②去噪處理：將訓練數據集中的網頁進行去噪處理，即去除網頁中與內容無關的Html標簽和JavaScript代碼，獲取代表實質內容的中文段落。

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

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

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

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

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

2.2 根據分類特征進行分類

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

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

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

假設每個分類特征都是獨立的，即出現在網頁中的分詞都是隨機出現的。因此，

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

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

2.3 分類示例

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

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

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

表2 訓練集分類特征分布表

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

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

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

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

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

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

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

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

3 分類結果與結論

3.1 實驗結果

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

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

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

表3 統(tǒng)計結果

3.2 實驗結論

根據表數據，可得如下結論：

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

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

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

4 構建簡易垂直搜索引擎

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

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

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

③利用Luence搜索引擎開源包，為分好類的網頁建立索引，將其存儲至數據庫，并實現排序算法。

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

5 結束語

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

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

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

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

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

［5］羅 剛，王振東.自己動手寫網絡爬蟲［M］.北京：清華大學出版社，2012.

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

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

［8］WITTEN Ian H，FRANK Eibe.數據挖掘實用機器學習技術［M］.北京：機械工業(yè)出版社，2012.

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

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

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

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

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

［14］余 淼，楊 丹，趙俊芹.垂直搜索引擎的關鍵技術研究［J］.軟件導刊，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

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

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

2015-08-06

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