胡欣杰, 龔 波, 蘇俊杰, 王 琳

(裝備學(xué)院信息裝備系,北京101416)

裝備采辦知識搜索引擎關(guān)鍵技術(shù)研究

胡欣杰, 龔 波, 蘇俊杰, 王 琳

(裝備學(xué)院信息裝備系,北京101416)

研究并設(shè)計(jì)了裝備采辦知識搜索引擎系統(tǒng)結(jié)構(gòu),包括搜索模塊、索引模塊、檢索模塊、查詢擴(kuò)展模塊和結(jié)果聚類模塊。就裝備采辦知識管理搜索關(guān)鍵技術(shù)查詢擴(kuò)展模塊和結(jié)果聚類模塊,提出了相似性度量的漸進(jìn)直推式支持向量機(jī)(similarity measurement progressive tranductive support vector machine,SMPTSVM)查詢擴(kuò)展模型,以及基于人工免疫算法的搜索引擎結(jié)果聚類算法。實(shí)驗(yàn)結(jié)果表明,該模型和算法提高了搜索結(jié)果的查全率、查準(zhǔn)率及搜索結(jié)果的平均聚類精度。

裝備采辦;查詢擴(kuò)展;支持向量機(jī);聚類

1 問題的提出

隨著裝備采辦知識管理系統(tǒng)內(nèi)部知識的爆炸式增長,采辦工作人員勢必會淹沒在知識海洋中,如何幫助裝備采辦人員快速、準(zhǔn)確地從浩瀚的知識資源中尋找真正所需的信息,成為裝備采辦知識管理系統(tǒng)建設(shè)的主要目標(biāo)之一,對裝備采辦實(shí)施知識管理已成為我軍提高采辦效益的必然選擇。裝備采辦知識管理系統(tǒng)能夠?qū)崿F(xiàn)對知識的有效組織、管理和應(yīng)用,而知識搜索引擎作為知識管理系統(tǒng)中的核心組成,是采辦人員獲取知識、學(xué)習(xí)知識的重要工具,有效提高了知識的使用效率。因此研究具有良好知識搜索性能的裝備采辦知識管理系統(tǒng)具有較大的軍事意義和實(shí)際應(yīng)用價(jià)值[1]。

搜索引擎作為一種信息檢索技術(shù),能夠以一定的策略在信息資源中搜集、發(fā)現(xiàn)信息,對信息進(jìn)行理解、提取、組織和處理,并為用戶提供檢索服務(wù),從而起到信息導(dǎo)航的作用。一個高效的裝備采辦知識搜索引擎能夠促進(jìn)系統(tǒng)內(nèi)部知識的流轉(zhuǎn),加快裝備采辦人員查找信息的速度,對提高裝備采辦工作效率具有重要意義。

2 裝備采辦知識搜索引擎系統(tǒng)結(jié)構(gòu)

裝備采辦知識搜索引擎為知識匯聚、知識發(fā)現(xiàn)、知識聚類、知識門戶的構(gòu)建等提供支持,通過搜索引擎技術(shù)完成知識管理。知識搜索引擎建立在明確的知識來源基礎(chǔ)之上,根據(jù)用戶的身份與請求,回饋?zhàn)顪?zhǔn)確恰當(dāng)?shù)闹R,為特定用戶提供搜索服務(wù)[2-3]。裝備采辦知識搜索引擎系統(tǒng)主要由搜索模塊、索引模塊、檢索模塊、查詢擴(kuò)展模塊和結(jié)果聚類模塊組成,系統(tǒng)框架結(jié)構(gòu)如圖1所示。

圖1 裝備采辦知識搜索引擎系統(tǒng)結(jié)構(gòu)

搜索模塊搜集系統(tǒng)內(nèi)部的網(wǎng)頁資源和知識庫中的內(nèi)容,并將獲取的網(wǎng)頁資源存儲在文件數(shù)據(jù)庫中;索引模塊是對收集的文件進(jìn)行分析,提取其中的重要信息,并針對這些信息建立索引數(shù)據(jù)庫;檢索模塊提供了用戶與系統(tǒng)進(jìn)行交互的接口,通過接口,用戶提交查詢請求,檢索模塊對該請求進(jìn)行解析處理,將處理后的查詢請求提供給索引子系統(tǒng),在索引數(shù)據(jù)庫中查找相關(guān)信息,并根據(jù)一定的相關(guān)度算法對查詢到的結(jié)果進(jìn)行相關(guān)度排序,返回搜索結(jié)果;查詢擴(kuò)展模塊根據(jù)初次檢索返回的結(jié)果進(jìn)行查詢重構(gòu),解決用戶“詞不匹配”問題,提高搜索結(jié)果的查全率和查準(zhǔn)率;結(jié)果聚類模塊根據(jù)返回結(jié)果之間的相似性進(jìn)行劃分,將內(nèi)容相近的結(jié)果劃分為一類并用標(biāo)簽標(biāo)志,用戶根據(jù)標(biāo)簽在相應(yīng)類別中查找,縮短了信息查找時(shí)間。

查詢擴(kuò)展模塊和結(jié)果聚類模塊是本系統(tǒng)關(guān)鍵技術(shù),幫助用戶快速定位所需信息,提高搜索引擎性能。本系統(tǒng)所實(shí)現(xiàn)的查詢擴(kuò)展模塊,提出了相似性度量的漸進(jìn)直推式支持向量機(jī)(SMPTSVM)查詢擴(kuò)展模型,結(jié)果聚類模塊提出基于人工免疫算法的搜索引擎結(jié)果聚類算法,實(shí)驗(yàn)和仿真結(jié)果表明提高了搜索結(jié)果的查全率、查準(zhǔn)率及搜索結(jié)果的平均聚類精度。

3 關(guān)鍵技術(shù)研究

3.1 SMPTSVM查詢擴(kuò)展模型

裝備采辦知識搜索查詢擴(kuò)展模塊是根據(jù)初次檢索返回的結(jié)果重新構(gòu)建查詢,實(shí)現(xiàn)詞匹配,提高搜索結(jié)果的查全率和查準(zhǔn)率。在本系統(tǒng)的查詢擴(kuò)展模塊中,提出了SMPTSVM查詢擴(kuò)展模型,并通過實(shí)驗(yàn)驗(yàn)證了其有效性。SMPTSVM查詢擴(kuò)展模型擴(kuò)展了相似性度量的PTSVM(progressive tranductive support vector machine)模型,引入了漸進(jìn)直推式支持向量機(jī)的概念。

基于支持向量機(jī)的查詢擴(kuò)展模型將信息檢索中的查詢擴(kuò)展看作1個分類問題,采用分類模型將候選詞項(xiàng)分為“相關(guān)”和“不相關(guān)”2類,將標(biāo)記為“相關(guān)”的詞項(xiàng)加入到原始查詢中,以解決詞的不匹配問題。然而查詢擴(kuò)展與普通的分類問題相比又有其特殊性,不能夠用普通的SVM(support vector machine)模型來解決查詢擴(kuò)展問題。根據(jù)查詢擴(kuò)展具體應(yīng)用背景,基于SMPTSVM的查詢擴(kuò)展模型應(yīng)主要解決以下2個問題：樣本的向量表示和目標(biāo)函數(shù)的定義。

3.1.1 SMPTSVM查詢擴(kuò)展模型算法[4-7]

SMPTSVM算法在標(biāo)記無標(biāo)簽樣本時(shí)綜合了周圍樣本和通過分類模型計(jì)算的標(biāo)簽值對其的影響,使標(biāo)簽值的確定更加準(zhǔn)確,減少了標(biāo)簽的重置率。基于SMPTSVM的查詢擴(kuò)展方法如下。

步驟1 由多次搜索結(jié)果的特征值構(gòu)建(query,word)特征向量;

步驟2 隨機(jī)選取n個(query,word)樣本進(jìn)行人工標(biāo)記,將相關(guān)的樣本標(biāo)記+1,不相關(guān)的樣本標(biāo)記-1,并選擇m個未標(biāo)記樣本(m?n);

步驟3 按上述描述的方法對SMPTSVM分類模型進(jìn)行訓(xùn)練,得到分類效果較優(yōu)的分類函數(shù)f;

步驟4 在索引庫中,按查詢query進(jìn)行初次檢索,以返回的前K篇文檔為擴(kuò)展詞項(xiàng)來源;

步驟5 對返回結(jié)果i進(jìn)行去噪、分詞處理,過濾掉不符合條件的詞項(xiàng),對剩余詞項(xiàng)構(gòu)建(query,word)形式的表示向量;

步驟6 利用步驟3訓(xùn)練所得的分類函數(shù)f計(jì)算每個(query,word)向量的標(biāo)簽值label,并將label=+1的結(jié)果存入結(jié)果推薦矩陣;

步驟7 若i＜K,返回步驟5繼續(xù)執(zhí)行,否則跳到步驟8;

步驟8 根據(jù)結(jié)果推薦矩陣中total的值,將total值最大的前j個詞項(xiàng)加入到原始查詢中構(gòu)成新的查詢newquery。

3.1.2 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

裝備采辦知識搜索引擎是基于裝備采辦知識管理系統(tǒng)的信息檢索系統(tǒng),原型系統(tǒng)設(shè)計(jì)了3個查詢集進(jìn)行測試,每個查詢集合包括10個查詢, 3個查詢集合如表1所示。

表1 查詢集合

其中Query1包含1個關(guān)鍵詞,Query2包含2個關(guān)鍵詞,Query3中包含3個關(guān)鍵詞。

實(shí)驗(yàn)采用查全率和查準(zhǔn)率作為評價(jià)標(biāo)準(zhǔn)。將本文提出的SMPTSVM與標(biāo)準(zhǔn)的SVM方法、局部上下文分析的查詢擴(kuò)展方法進(jìn)行了比較。選擇初始檢索后返回的前10篇文檔作為相關(guān)文檔集,然后根據(jù)各種算法的選擇策略來評估相關(guān)文檔集中的關(guān)鍵詞,選出得分最高且沒有在初始查詢中出現(xiàn)的20個關(guān)鍵詞來重構(gòu)查詢,并進(jìn)行二次檢索。由于在返回結(jié)果中,人們往往更關(guān)注排名靠前的結(jié)果,因此實(shí)驗(yàn)選取每次查詢返回的前50篇文檔,采用人工評判的方式分別統(tǒng)計(jì)3種方法在各查詢集合上的查全率和查準(zhǔn)率,3種方法的查詢性能量化對比結(jié)果如表2所示。

表2 查詢性能對比

從3種方法在不同查詢集合上的對比可以看出,本文提出的基于SVM的查詢擴(kuò)展模型與其他2種方法相比查全率和查準(zhǔn)率都有了明顯的提高,具有更優(yōu)的檢索性能。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)查詢擴(kuò)展方法相比,搜索結(jié)果的查全率提高了6.67%,查準(zhǔn)率提高了6.81%。

3.2 基于人工免疫算法的搜索引擎結(jié)果聚類算法

裝備采辦知識管理搜索引擎的搜索結(jié)果聚類模塊,針對現(xiàn)有算法自適應(yīng)差的缺點(diǎn),將人工免疫思想引入搜索結(jié)果聚類過程,構(gòu)造了基于人工免疫算法的搜索結(jié)果聚類方法,采用自生長、自組織的進(jìn)化策略得到樹狀拓?fù)浣Y(jié)構(gòu)的抗體種群,通過該種群獲得的聚類中心能夠較好地?cái)M合搜索結(jié)果在向量空間中的分布形狀,提高了算法的聚類精度及運(yùn)行效率。

目前常用的聚類算法有：劃分聚類方法、層次聚類方法、基于密度的聚類方法、基于網(wǎng)格的聚類方法、基于模型的聚類方法、K-Means算法等。與K-Means算法原理相同,本文利用人工免疫思想改進(jìn)的聚類算法也是基于K-Nearest準(zhǔn)則的聚類,該算法主要分為2個步驟：構(gòu)造樹狀拓?fù)浣Y(jié)構(gòu)的抗體種群;選取記憶抗體作為整個抗原種群的碼書(codebook),然后采用K-Nearest準(zhǔn)則對搜索結(jié)果進(jìn)行聚類。具體方法為,首先從搜索引擎結(jié)果中提取出有效的特征向量,并采用樹狀種群拓?fù)浣Y(jié)構(gòu),采用自生長、自組織的種群進(jìn)化策略對特征向量進(jìn)行有效聚類。通過自適應(yīng)的進(jìn)化迭代,抗體由單一個體逐漸進(jìn)化為一定規(guī)模的種群,其中的個體可以通過對種群拓?fù)浣Y(jié)構(gòu)的解析劃分到不同的聚類。

基于人工免疫算法的搜索引擎結(jié)果聚類過程如下。

步驟1 根據(jù)迭代結(jié)束后生產(chǎn)的抗體種群,通過上述代碼得到每個類別的初始聚類中心。

步驟2 用值在(0,1)之間的隨機(jī)數(shù)初始化隸屬度矩陣U,使其滿足如下約束條件。

步驟3 判斷停止條件,若滿足則輸出聚類結(jié)果,將搜索結(jié)果根據(jù)隸屬度矩陣劃分到相應(yīng)的類別中;否則轉(zhuǎn)至步驟4。

步驟4 根據(jù)式(1)更新隸屬矩陣U。

其中：m為可調(diào)節(jié)參數(shù),用來控制算法柔性。

步驟5 根據(jù)式(2)計(jì)算新的聚類中心,返回步驟3。

在搜索結(jié)果聚類過程中,由高效的人工免疫算法生成的初始聚類中心能夠很好擬合結(jié)果向量在空間中的分布形狀,可以減少聚類過程的迭代次數(shù),聚類效果明顯優(yōu)于K-Means這類隨機(jī)初始化聚類中心的方法。

1)實(shí)驗(yàn)設(shè)計(jì)。設(shè)計(jì)8個獨(dú)立的查詢詞{query1=“合同”,query2=“項(xiàng)目管理”,query3=“裝備”,query4=“采辦”,query5=“維修保障”,query6=“研制”,query7=“信息化”,query8=“裝備科研”}進(jìn)行實(shí)驗(yàn)。對于每個查詢詞,選取返回結(jié)果的前100項(xiàng)作為實(shí)驗(yàn)數(shù)據(jù),搜索返回結(jié)果經(jīng)過預(yù)處理后建立向量空間模型,分別采用本文提出的人工免疫聚類算法以及K-Means算法進(jìn)行對比實(shí)驗(yàn)。人工免疫算法的參數(shù)如表3所示。

表3 實(shí)驗(yàn)采用的參數(shù)值列表

對于每個參與實(shí)驗(yàn)的算法,比較該算法生成的聚類結(jié)果與人工分類得到的聚類結(jié)果的相似度,采用平均聚類精度Jacp作為衡量算法準(zhǔn)確度的指標(biāo),Jacp計(jì)算公式如下[5,8-9]：

式中：k是算法生成的聚類個數(shù);Pj是第j個聚類的準(zhǔn)確率,即在該聚類中與采用人工方式判斷一致的結(jié)果數(shù)占人工分類總數(shù)目的比重。對比結(jié)果如圖2所示。

圖2 2種算法在8個獨(dú)立查詢詞上的平均查準(zhǔn)率對比

2)結(jié)果分析。從圖2對比結(jié)果可以看出,與K-Means聚類算法相比,基于人工免疫的聚類算法在8個查詢詞上的平均聚類精度得到明顯的提高,前100項(xiàng)返回結(jié)果的平均聚類精度達(dá)到72%左右。特別是在query3、query4、query5和query6上,本文算法體現(xiàn)出明顯的優(yōu)越性。而KMeans聚類算法在query7上也有較高的平均聚類精度,但在query6上平均聚類精度僅有50%左右,這是由于K-Means選取的聚類中心具有隨機(jī)性,有時(shí)候并不能很好的體現(xiàn)數(shù)據(jù)的真實(shí)分布情況,導(dǎo)致了聚類性能的不穩(wěn)定。人工免疫聚類算法通過多次抗原刺激構(gòu)造的抗體種群,能夠較好地?cái)M合搜索結(jié)果在真實(shí)數(shù)據(jù)空間的分布形狀,從而保證了下一步聚類的有效性,因此聚類效果較為穩(wěn)定。

4 結(jié)束語

本文以裝備采辦信息化訓(xùn)練與研究平臺為背景,主要圍繞裝備采辦知識管理系統(tǒng)和知識搜索引擎相關(guān)技術(shù)進(jìn)行研究。知識搜索引擎作為裝備采辦知識管理系統(tǒng)的一種基礎(chǔ)服務(wù),對加速系統(tǒng)內(nèi)知識的流轉(zhuǎn)、共享和創(chuàng)新具有重要的作用,可以有效提高裝備采辦工作效率。

References)

[1]戰(zhàn)竹杰,白鳳凱.裝備采辦知識管理研究[J].裝備指揮技術(shù)學(xué)院學(xué)報(bào),2010,21(1)：35-38.

[2]U.S.Department of Defense.Quadrennial defense review report[R/OL].[2011-02-10].http：//defense.com/products/ w/win-t-pop.ht.

[3]王沙聘,高學(xué)東,趙澄謀.新軍事變革：武器裝備采辦中的知識意識[J].現(xiàn)代情報(bào),2007(3)：209-211.

[4]彭新俊,王翼飛.雙模糊漸進(jìn)直推式支持向量機(jī)算法[J].模式識別與人工智能,2009,22(4)：560-566.

[5]張選平,蔣宇,袁明軒.一種基于概念的信息檢索查詢擴(kuò)展[J].微電子學(xué)計(jì)算機(jī),2006,23(4)：110-114.

[6]沈新宇.基于直推式向量機(jī)的圖像分類算法研究與應(yīng)用[D].北京：北京交通大學(xué),2007：33-36.

[7]李盼池,許少華.支持向量機(jī)在模式識別中的核函數(shù)特性分析[J].計(jì)算機(jī)工程與設(shè)計(jì),2005,26(2)：302-304.

[8]DASGUPTA D.Advances in artificial immune systems[J]. IEEE Computational Intelligence Magazine,2006,1(4)：40-49.

[9]馮棟梁.基于人工免疫原理的聚類問題研究[D].哈爾濱：哈爾濱工程大學(xué),2008：50-53.

(編輯：李江濤)

Research on the Key Technology of Equipment Procurement Knowledge Searching Engine

HU Xinjie, GONG Bo, SU Junjie, WANG Lin

(Department of Information Equipment,Equipment Academy,Beijing 101416,China)

This paper researches and designs the equipment procurement knowledge searching engine system structure.The system structure has five modules,including scouting module,indexing module,searching module,inquiring extension module and clustering module.About extend module and clustering module,it proposes similarity measurement progressive tranductive support vector machine(SMPTSVM)inquiring extension model and search engine results clustering algorithm based on artificial immune algorithm.The experimental results show that this method can improve the recall ratio,precision and the average clustering precision of the search results.

equipment procurement;inquiring extension;support vector machine;clustering

TP 393

2095-3828(2014)02-0090-04

ADOI10.3783/j.issn.2095-3828.2014.02.021

2013-05-08

部委級資助項(xiàng)目

胡欣杰(1963-),女,教授.主要研究方向：裝備信息系統(tǒng).