于秀麗，王陽(yáng)，齊幸輝

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

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

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

于秀麗1，王陽(yáng)2，齊幸輝2

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

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

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

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

0 引言

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

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

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

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

1.1 CHI特征選擇法

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

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

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

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

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

1.2 樸素貝葉斯模型

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

對(duì)樸素貝葉斯算法定義如下：

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

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

③計(jì)算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)頁(yè)作為訓(xùn)練集和測(cè)試集，利用樸素貝葉斯方法構(gòu)建垂直搜索引擎分類器，對(duì)網(wǎng)頁(yè)進(jìn)行分類。

2.1 特征選取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 分類示例

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 實(shí)驗(yàn)結(jié)果

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)論

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

［13］李靜梅，孫麗華，張巧榮，等.一種文本處理中的樸素貝葉斯模型［J］.哈爾濱工程大學(xué)學(xué)報(bào)，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

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

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

2015-08-06

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