基于加權向量空間模型的網(wǎng)絡搜索
2007-01-01 00:00:00白曦呂曉楓孫吉貴
計算機應用研究 2007年2期
摘 要：為了高效地對從Internet上獲取的文檔進行訓練并歸類，給出了一種新的分類器模型。該模型在傳統(tǒng)的向量空間模型(VSM)中引入了關鍵詞語的加權因子，并在訓練文檔過程中對文檔類型特征向量進行動態(tài)優(yōu)化。這在一定程度上恢復了關鍵詞語實際應具有的權值，方便了閾值的選取，使分類更加準確和高效。實驗表明，該分類器分類合理、分類準確性有明顯的提高，并具有一定的學習功能。
關鍵詞：向量空間模型; 自動分類; 加權因子; 調節(jié)系數(shù); 閾值
中圖法分類號：TP391文獻標識碼：A
文章編號：1001—3695(2007)02—0051—03
1 引言
隨著信息時代的到來，人們已將Internet作為快速獲取、發(fā)布和傳遞信息的重要工具。網(wǎng)絡上的內容幾乎每時每刻都在更新，信息資源呈幾何級數(shù)增長。如今，人們獲取信息并加以利用的重點不是在于如何獲取資料，而是在于如何從海量的資料中去粗取精、去偽存真，以便獲得有價值的信息。面對紛繁復雜的信息，媒介從業(yè)者們不得不疲于應對篩選信息的艱巨任務[1]。采用人工瀏覽的方式去查找信息不但效率低而且很枯燥，于是搜索引擎技術應運而生[2]。目前比較流行的搜索引擎有Google，Yahoo，Baidu等。它們在很大程度上方便了人們進行網(wǎng)上沖浪，在政治、經(jīng)濟、生活等各個方面發(fā)揮著重要的作用。然而傳統(tǒng)的搜索引擎存在著很多缺點[2]：無法對信息的動態(tài)變化作出及時反應，不能對全新類型的文檔作出有效歸類；返回的搜索結果是基于關鍵字的，結果往往涉及到很多領域，用戶很難從眾多的結果中找到自己感興趣的信息等。此外，對文檔的分類大都基于向量空間模型(Vector Space Model，VSM)，而傳統(tǒng)的向量空間模型只是單純地將詞頻作為特征向量。有的文檔由于長度較短，或者由于關鍵詞在標題和正文開頭后出現(xiàn)，或者其他地方被代詞所替代，導致真正反映該文檔類型的關鍵詞總數(shù)較少。因此這種以詞頻作為特征向量的分類方法的效果并不令人滿意。
本文針對以上問題，在傳統(tǒng)的VSM基礎上，對其加以改進并應用到我們的分類器當中。我們根據(jù)詞語在文檔中出現(xiàn)的位置對關鍵詞語加權，并利用求平均值的方法對類型特征向量進行更新。
2 文檔表示模型
為了對文檔的類型進行判斷，我們需要從中提取出能表示該文檔內容的特征項（詞或短語等），然后在此基礎上設計某種模型來體現(xiàn)這些特征項。目前常用的文檔表示模型有向量空間模型、布爾邏輯模型以及概率模型等[3—5]。其中向量空間模型和概率模型應用比較廣泛，且效果較好。
2.1 向量空間模型
向量空間模型是由Salton在20世紀60年代提出的[3]，如今已被廣泛地應用在各大搜索引擎中，分類效果相當明顯。此模型將文檔內容的比較過程簡化為空間向量的計算，大大降低了分類過程的復雜性。
2.2 布爾邏輯模型
布爾模型是人們在向量空間模型的基礎上提出的[4]，該模型比較簡單，實際上是向量空間模型的簡化。它定義了一個二值映射函數(shù)f∶W→{0，1}，其中W表示詞。這樣，文檔就可以用一個由0和1構成的特征向量P表示：
從布爾邏輯模型的定義可以看出，它與向量空間模型的比較忽略了詞在文檔中出現(xiàn)的頻率，因此實現(xiàn)起來比較簡單，運行速度快。但是特征向量中的信息少，一些能反映文檔類別的關鍵性詞語可能被忽視。
2.3 概率模型
概率模型是由Belkin和Croft于1992年提出的[5]。它使用概率結構來表示特征項，通過貝葉斯公式計算詞頻。貝葉斯方法是效率較高的方法之一，但是它要求的獨立性條件往往不能被較好地滿足，因此人們常常通過放寬獨立性條件來得到若干改進的概率模型[6]。
3 加權文檔分類方法設計
本節(jié)建立了一個基于向量空間模型的加權文檔分類器模型。該模型用特征向量表示文檔，通過定量的運算來對文檔進行訓練和歸類。鑒于已知類別庫中的文檔是靜態(tài)的，而網(wǎng)上信息是動態(tài)變化的，我們令模型同時具有對已知類別特征向量進行更新的功能。在保證文檔被正確分類的前提下，提高了對后續(xù)文檔分類的精確度。
3.1 文檔分類模型的建立
傳統(tǒng)的VSM單純地將詞頻作為特征向量元素，它的分類效果并不理想。從第4節(jié)的試驗中也可以看到，原本經(jīng)人工分類應屬于同一類型的兩篇文檔，它們的相似度只有0.5左右，而不屬于同一類型的兩篇文檔，它們的相似度甚至超過了0.4，這將對閾值的選取造成相當大的困難。分析表明，造成這種同類和異類文檔相似度差別較小的主要原因是真正反映該文檔類型的關鍵詞出現(xiàn)的頻率較小所致。這可能是文檔長度較短導致詞的總數(shù)較少，也可能是由于關鍵詞在標題和正文開始后出現(xiàn)，其他地方被代詞所替代。針對此問題，我們可以利用網(wǎng)頁中含有的大量結構信息，包括該頁面的標題、子標題、加粗、加下劃線等重要標記，比如可將
以上改進在一定程度上恢復了關鍵性詞語在文檔中的實際權重，拉大了同類和異類文檔相似度的差別，便于我們選擇閾值并對文檔進行歸類。
3.2 文檔類型特征向量的實時更新
以上類型特征向量包含的詞語以及出現(xiàn)的頻率都是固定值。由于某類型所收錄的文檔數(shù)量的有限性，隨著新文檔的加入，類型特征向量將不能很好地反映文檔類別。因此，當判斷某文檔屬于某個文檔類型后，我們有必要對其進行實時更新。這樣做可使分類器具有學習功能，在其應用過程中通過不斷地對特征向量進行微調，使之更好地反映類別特征，為今后對其他文檔進行分類打下基礎。考慮到更新后的特征向量與舊的特征向量以及新加入文檔的特征向量有關，我們可以在此分類器中用對詞語的權重取平均值的方法對類型特征向量進行更新。但如果僅對以上兩個特征向量取平均值，新加入的文檔可能因為篇幅較短等原因導致更新后的特征向量波動較大。為避免上述情況的發(fā)生，我們可以為舊的特征向量增加一個調節(jié)系數(shù)，從而提高其影響力度。經(jīng)分析，我們把已收錄的文檔數(shù)作為調節(jié)系數(shù)。隨著某類型包含文檔數(shù)目的不斷增加，特征向量的更新將越來越有效。假設通過計算我們已經(jīng)得出3.1節(jié)中的sim′(C，P′)超過了事先設定的閾值μ，在此之前該類型已收錄k篇文檔，則更新后該類型的特征向量為
4 分類器測試與結果
我們在Internet上找了四篇文檔作為分類器的測試文檔，文檔標題和內容如下：
神舟六號發(fā)射全過程記錄
10月12日9時零分零秒，發(fā)射神六飛船的長征二號F型運載火箭點火。火箭在點火４秒鐘后升空，轟鳴聲回蕩在戈壁灘上空。這是長征火箭第８８次發(fā)射。點火第１２秒，火箭向東稍偏南的方向實施程序拐彎。此時，火箭距地面高度為２１１米。點火第１２０秒，火箭拋掉逃逸塔，這是火箭第一個分離動作。點火第１５９秒，火箭一二級分離成功，一級墜落。此時，火箭已經(jīng)飛過了平流層和中間層，正在接近大氣層邊緣。點火第２００秒，整流罩分離成功。飛行中，整流罩能保護飛船免受熱和氣流的作用。此時，第二級火箭已飛出稠密大氣層，飛船不再需要整流罩的保護了。指揮員宣布：飛船飛行正常。指揮員宣布，飛船遙測信號正常，雷達跟蹤正常。中國載人航天工程著陸場系統(tǒng)全面啟動。雷達發(fā)現(xiàn)飛船目標，雷達跟蹤正常。神舟六號飛船上升運行２６０秒后，位于酒泉附近的副著陸場承擔的飛船上升段應急返回搜救任務解除。船箭成功分離，此時距點火時間約５８３秒。第一次安裝在火箭上的攝像頭，拍下了從點火到船箭分離的全過程。點火５８３秒時，飛船與火箭在高度約２００公里處成功分離。北京航天飛行控制中心傳來航天員向地面報告“船箭分離”的聲音。此次載人航天工程著落系統(tǒng)的任務區(qū)包括：內蒙古中部的主著陸場，酒泉附近的副著陸場，銀川、榆林和邯鄲的陸上應急著陸區(qū)，３個海上應急搜救區(qū)，以及國外多個應急著陸點。神舟六號飛船正常上升運行４４９秒后，著陸場系統(tǒng)榆林搜救責任區(qū)任務解除。神舟六號飛船正常上升運行５４４秒后，著陸場系統(tǒng)邯鄲搜救責任區(qū)任務解除。航天員向北京飛控中心報告：“儀表顯示：帆板打開。感覺良好。”在神舟六號飛船順利進入軌道之后，著陸場系統(tǒng)承擔的飛船上升段應急返回搜救任務全部解除。胡錦濤等中央領導人在北京航天飛行控制中心興致勃勃地觀看神舟六號飛船升空實況。北京航天飛控中心報告“飛船工作正常”。北京航天飛控中心宣布：飛船正常入軌。溫家寶等中央領導同志在酒泉衛(wèi)星發(fā)射中心現(xiàn)場觀看飛船發(fā)射。
神州六號飛船發(fā)射場景
12:02[新華網(wǎng)報道]飛船升空，著陸場系統(tǒng)全面啟動，救援員登機待命。11:27[新華網(wǎng)報道]神舟六號載人航天飛行任務航天員乘組答記者問。11:16[新華網(wǎng)報道]航天員進餐完畢，調度指揮員要求一航天員休息。11:15[新華網(wǎng)報道]航天員正在第一次太空進餐，飛船工作情況正常。10:41[新華網(wǎng)報道]調度指揮員將通知航天員摘下手套解開束縛帶。10:41[新華網(wǎng)報道]神舟航天員報告飛船工作正常，解開束縛帶。10:40[新華網(wǎng)報道]我最西端的喀什測控站報告已發(fā)現(xiàn)神舟六號飛船。10:20[新華網(wǎng)報道]承擔海上救援任務的救助船舶在發(fā)射成功后返航。10:01[國際在線報道]楊立偉表示，作為航天員第一次走入太空來俯瞰我們美麗家園的時候，能感覺到人類的偉大、祖國的偉大、民族的偉大，同時也能感受到我們國家科技日新月異的發(fā)展。這次神舟六號發(fā)射，也是帶動我們科技全面的發(fā)展，也進一步凝聚了我們中華民族的凝聚力。09:59[國際在線報道]在現(xiàn)場觀摩神舟六號發(fā)射的航天員楊立偉說，作為航天員，在這么激動的時刻，心情不可能平靜，但是并不是緊張。這也充分體現(xiàn)了我們的航天員高素質和高技術這種水平。他們在上面完成得非常出色，無論他們從地面艙里面的準備還是在發(fā)射過程當中，表現(xiàn)得非常出色，而且也體現(xiàn)了非常好的、平穩(wěn)的心理。包括剛才入軌的一瞬間，都表現(xiàn)了非常良好的素質。現(xiàn)在這個階段也是他們剛剛入軌，正在調整的一個階段。09:50溫家寶、李長春、羅干等和現(xiàn)場工作人員握手，祝賀發(fā)射成功。09:49[國際在線報道]胡錦濤等中央領導同志與北京航天飛行控制中心工作人員親切握手，熱烈祝賀神舟六號發(fā)射成功。09:48[國際在線報道]９點４３分，溫家寶總理在酒泉衛(wèi)星發(fā)射中心發(fā)表重要講話，他代表黨中央、國務院、中央軍委講話，祝賀飛船發(fā)射成功，并向參加工程的全體科學技術人員、干部職工、人民解放軍指戰(zhàn)員表示衷心的祝賀和親切的慰問。09:46溫家寶向參加工程的全體人員祝賀并慰問。09:45溫家寶代表黨中央、國務院、中央軍委祝賀發(fā)射成功。
“神舟六號”發(fā)射過程報道實錄
新華網(wǎng)１０月１２日北京飛控中心專電 神六載人航天飛行發(fā)射階段，本網(wǎng)記者詳細記錄了我們新華社報道團的工作，這個時間表可以詳盡地展現(xiàn)整個神六載人航天飛行發(fā)射階段，那激動人心的六十多分鐘。８：３０分，酒泉發(fā)射中心，環(huán)抱船箭聯(lián)合體的火箭發(fā)射塔操作支架已經(jīng)完全打開。繼續(xù)搶發(fā)快訊，通報神六發(fā)射最新進展。８：４０分，直播口令下達。新華網(wǎng)神六載人航天飛行的發(fā)射階段視頻直播開始。我們和全國人民可以通過電視和網(wǎng)絡視頻直播，直接觀看到發(fā)射畫面。在另一套視頻信號系統(tǒng)里，現(xiàn)場記者可以清晰地聽到神六飛船內部兩位航天員正在接受指令。８：４５分，飛船發(fā)射進入十五分鐘準備階段！航天員回答：“明白！”，聲音清楚有力。記者們，正在寂靜中緊張工作，除了視頻信號里的聲音，現(xiàn)場只能聽到鍵盤的敲擊聲。神六飛船里，航天員與北京飛控中心的領導進行了通話。８：５０分，發(fā)射時間確定為９：００。８：５５分，飛船發(fā)射五分鐘準備。８：５９分，飛船發(fā)射一分鐘準備。飛船里，兩位航天員表情非常平靜。９：００：２０，由于信號傳輸?shù)难雍螅w船點火發(fā)射２０秒后，飛船內部的視頻信號中斷，我們看不到宇航員的情況了。９：００：２４，飛船內傳回的視頻信號恢復，兩位航天員向我們揮了揮手！這個情景通過即時的電視直播是看不到的。現(xiàn)場的記者很興奮，這無疑將成為我們一個美好的回憶。９：０８分，飛行正常，航天員的神情很輕松，他們又向鏡頭揮了揮手，我看到有些現(xiàn)場記者也情不自禁地向兩位航天員揮手，雖然他們看不到，無聲交流卻表達了我們記者衷心的祝愿。９：１０分，船箭分離。飛船內部的視頻信號暫時中斷。９：２５分，酒泉發(fā)射中心與北京航天飛行控制中心緊張交流各種技術數(shù)據(jù)。９：３０分，長江二號衛(wèi)星在預定軌道中發(fā)現(xiàn)神六飛船，飛船內部視頻畫面恢復！９：３３分，神六航天員與地面通話，接受指令打開航天服面窗。９：３４分，地面醫(yī)監(jiān)醫(yī)生與航天員通話。９：４０分，我國載人航天工程總指揮長陳炳德宣布神舟六號載人飛船發(fā)射成功。９：４２分，國家總理溫家寶發(fā)表講話。發(fā)射階段報道工作基本結束。但是我們現(xiàn)場記者的工作遠未結束。此時，新聞中心里專供電記者通信聯(lián)絡的電話鈴聲此起彼伏，而神六已經(jīng)遨游在預定軌道里了！
“長征”火箭發(fā)射成功率達100%
新華社太原電 據(jù)中國航天發(fā)射測控系統(tǒng)部有關負責人介紹，黨的十五大以來，我國航天發(fā)射綜合能力實現(xiàn)跨越式發(fā)展，已形成具有現(xiàn)代化水平的完整體系。酒泉、太原、西昌三大航天發(fā)射場經(jīng)過更新與改造，具備了發(fā)射高、中、低各種軌道航天器的能力。新建的載人飛船發(fā)射場于1998年正式投入使用，它綜合了當代世界先進科學技術，采用了具有國際先進水平的垂直總裝、垂直測試、垂直整體轉運的模式及遠距離發(fā)射測控技術，標志著我國航天發(fā)射實現(xiàn)了歷史性跨越。特別是“神舟”一、二、三號實驗飛船的成功發(fā)射，說明我國載人航天工程有了歷史性突破。目前，我國已建立陸海基為一體的現(xiàn)代化航天測控網(wǎng)，航天測控技術位居世界先進行列。新建的北京航天指揮控制中心，集指揮通信、信息處理、監(jiān)控顯示、飛行控制等系統(tǒng)于一體，具有世界一流水平。西安衛(wèi)星測控中心掌握和運用“中心遙控”模式，并建立起獨具特色的“一網(wǎng)管多星”模式，衛(wèi)星測控和管理達到世界先進水平。“遠望”號航天測量船隊可以同時在世界三大洋上布陣，進行精確的航天測量和控制。我國自行研制了12種型號的“長征”運載火箭，已形成完整系列，質量可靠，技術含量高，經(jīng)濟性能好，能夠滿足各種軌道、各種航天器的發(fā)射需要，具有較強的國際競爭能力。黨的十五大以來，“長征”火箭共進行了21次發(fā)射，把27顆衛(wèi)星和3艘飛船送入太空，發(fā)射成功率達100%，這標志著“長征”火箭總體技術性能已接近或達到國際先進水平。大批年輕科技工作者成為我國航天發(fā)射測控領域的中堅力量。如今，在發(fā)射測控關鍵崗位上，具有碩士以上學歷的中青年科技干部占大多數(shù)。承擔這次“中國資源二號”衛(wèi)星發(fā)射任務的太原衛(wèi)星發(fā)射中心，各專業(yè)崗位技術人員的平均年齡不到26歲。
由人工分類可得，前三篇文檔是屬于同類文檔。下面我們測試分類器對以上文檔的分類效果，該測試分三次進行。首先對文檔進行分詞并用傳統(tǒng)的VSM模型（向量不加權）統(tǒng)計出各篇的特征向量（令收錄詞數(shù)n=25）。分詞集合及對應的特征向量如下：
我們將相似度閾值設定為0.8并對以上三種情況分別計算兩兩文檔的相似度。在第二次試驗和第三次試驗中，文檔1和文檔3被判斷為同屬一類文檔。它們的特征向量經(jīng)式（6）更新后作為共有的特征向量。通過程序計算可得如表1所示的實驗結果（Ai表示第i篇文檔的特征向量）。
以上數(shù)據(jù)說明，按照傳統(tǒng)的向量空間模型計算同類型文檔和不同類型文檔的相似度數(shù)值比較接近，很難對閾值進行選擇。而加上權值之后，相同類型文檔的相似度被放大，不同類型文檔的相似度被縮小，同時特征向量被動態(tài)更新，隨著所收錄文檔數(shù)目的增多，它將越來越準確地反映類型特征。但是α取值太大會降低正文內容對相似度的影響，導致文檔的標題決定文檔類型，這是我們不希望看到的。實驗表明，當α=5時，令閾值μ=6.5，會得到比較滿意的分類效果。
我們又用小樣本測試集對該分類器進行了測試。從中文網(wǎng)站上選取了1 000篇文檔，其中航空技術、證券形勢、體育新聞、汽車文化方面的文檔各250篇。使用MySQL作為后臺數(shù)據(jù)庫以及MySQL-Front作為該數(shù)據(jù)庫前端瀏覽器，將待分類文檔存入數(shù)據(jù)庫后用分類器進行分類，所得結果用MySQL-Front顯示出來，如圖4所示。將列出的數(shù)據(jù)與原文檔進行對比，我們發(fā)現(xiàn)分到各個類型的文檔篇數(shù)均超過了文檔總數(shù)的94%。雖然也存在一些文檔無法被歸入這四個類型，但分類效果還是令人滿意的。
5 結束語
本文提出了一種基于向量空間模型的改進文本分類方法。主要根據(jù)關鍵詞在文檔中出現(xiàn)的位置對特征向量進行加權，同時在訓練文檔的過程中實時地對特征向量進行微調，從而使分類器具有了學習功能。文中對文檔特征向量的加權方法進行了試探性的研究，如果將HTML頁面上的其他一些結構信息(如子標題、加粗、加下劃線)中出現(xiàn)的詞語也加上合適的權值，將達到更好的分類效果。基于以上這種技術的分類器可以方便地對相似度閾值進行選擇，同類和異類文檔的界限將更加分明，分類過程中極少有模棱兩可的情況出現(xiàn)。該分類器將使目前大多數(shù)搜索引擎以人工分類為主的局面得以改觀，在一定程度上克服了人工分類效率低下、精確度不高的缺點。實驗表明，該分類器對文檔的分類比傳統(tǒng)的分類器要準確得多，令加權因子為5，閾值為0.65時，同類和異類文檔的相似度的最大差別可達0.571。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
