摘要：隨著信息技術(shù)的發(fā)展，對信息的檢索和利用越來越顯示出其重要的作用。在知識(shí)產(chǎn)權(quán)專家?guī)斓膽?yīng)用中，由于信息表達(dá)的差異化和碎片化，信息檢索的準(zhǔn)確率和有效率都有待提高。將潛在語義檢索方法應(yīng)用于專家?guī)煜到y(tǒng)中，可以大大提高檢索的準(zhǔn)確率和有效率，并且可以避免數(shù)據(jù)庫以及外圍系統(tǒng)的重復(fù)更新，極大地節(jié)約了開發(fā)和維護(hù)的成本，具有十分重要的實(shí)際意義。該文結(jié)合RANSAC以及潛在語義檢索算法給出了一種適用于專家?guī)煨畔z索的搜索算法。實(shí)驗(yàn)結(jié)果表明，該方法在實(shí)踐中取得了預(yù)期的效果。

關(guān)鍵詞： RANSAC；潛在語義分析；奇異值分解；聚類分析

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）05- 1141-03

Expert Database Retrieval Based on RANSAC and LSA Algorithm

CAI Jia-cheng

（Suzhou Intellectual Property Rights Center， Suzhou 215104， China）

Abstract： With the development of information technology the retrieval and use of information becoming more and more important. In the case of experts in intellectual property library， because of the differentiation and fragmentation of information expression， accuracy and efficiency of information retrieval is not good enough for us. By applying LSA technology to Municipal Intellectual Property expert database retrieval system can improve the accuracy and efficiency of retrieval results. It can also avoid needless updating of database and retrieval system which greatly save the cost of development and maintenance of the retrieval system. In this paper we introduced an expert database retrieval method based on RANSAC and LSA. The experimental results show that this method gets the expected effectiveness.

Key words：RANSAC；latent semantic analysis （LSA）；singular value decomposition （SVD）；cluster analysis

1 概述

近年來，隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，信息化已經(jīng)滲透到企業(yè)與政府部門的各個(gè)重要環(huán)節(jié)。蘇州知識(shí)產(chǎn)權(quán)專家?guī)熳鳛閷＜倚畔⒌拇鎯?chǔ)與檢索平臺(tái)，為政府各部門進(jìn)行知識(shí)產(chǎn)權(quán)專家信息檢索，知識(shí)產(chǎn)權(quán)預(yù)警以及知識(shí)產(chǎn)權(quán)相關(guān)項(xiàng)目評審提供了統(tǒng)一化的信息搜集和過濾支持。在龐大的知識(shí)產(chǎn)權(quán)庫中，由于錄入人員、時(shí)間、方式的多樣化，特別是隨著時(shí)間的推移會(huì)出現(xiàn)一些新興的領(lǐng)域以及新興名詞，導(dǎo)致對專家所擅長的領(lǐng)域以及興趣方向描述方式不盡相同。而對于專家?guī)熹浫虢缑孢M(jìn)行規(guī)約化的做法會(huì)大量耗費(fèi)重復(fù)開發(fā)的人力物力，并且不能做到一勞永逸。而引入基于潛在語義的搜索方法，有助于對數(shù)據(jù)庫中各種專家信息進(jìn)行聚類和分析，并且提取統(tǒng)一化的關(guān)鍵詞作為出口。從而無需對以前的數(shù)據(jù)進(jìn)行重復(fù)的整理或者反復(fù)改變既有系統(tǒng)的錄入方式并調(diào)整數(shù)據(jù)庫結(jié)構(gòu)，從而大大節(jié)約了管理與維護(hù)成本。

本文，根據(jù)知識(shí)產(chǎn)權(quán)專家相關(guān)特征量大相似表述多，并且在實(shí)際應(yīng)用中對搜索精度和效率的特別要求設(shè)計(jì)了基于層次化特征潛在語義空間的聚類方案來增加搜索準(zhǔn)確度，通過使用RANSAC方法提高了搜索速度。從而實(shí)現(xiàn)了對專家信息檢索在精度和效率上的需求。

2 基于潛在語義的專家?guī)鞕z索算法

2.1 RANSAC算法

專家?guī)熘械臄?shù)據(jù)特征，具有數(shù)量龐大，但是特征方向性明顯，同時(shí)包含散亂噪聲的特點(diǎn)。為了提高精確度與后期計(jì)算速度，該文使用了RANSAC算法對數(shù)據(jù)進(jìn)行預(yù)處理。噪聲環(huán)境下的魯棒性估計(jì)算法，常用的有M-估計(jì)器、最小二乘和RANSAC（Random Sample Consensus）方法。而由Fishler和Bolles在1981年提出的RANSAC算法被認(rèn)為是最好、也是使用最廣泛的方法，它甚至能處理50%噪聲情況下的數(shù)據(jù) [1]。RANSAC算法利用一小部分?jǐn)?shù)據(jù)作為內(nèi)點(diǎn)得到初始值，然后根據(jù)初始值統(tǒng)計(jì)數(shù)據(jù)集中所有的內(nèi)點(diǎn)。這種估計(jì)方法使其能最大限度地減少噪聲及外點(diǎn)的影響。但這也使得算法精確性和收斂速度受初始參數(shù)值的影響很大。要提高RANSAC算法性能，必須建立一個(gè)良好的初始參數(shù)值估計(jì)方法。

2.2 潛在語義分析

潛在語義分析 （Latent Sereantic AnMysis，LSA）是一種用于自動(dòng)地實(shí)現(xiàn)知識(shí)提取和表示的理論和方法，它通過對大量的文本集進(jìn)行統(tǒng)計(jì)分析，從中提取出詞語的上下文使用含義，是一種通過建立概念空間的方式來獲得對詞語和文檔的語義理解和語義聯(lián)系[2]。它通過統(tǒng)計(jì)方法，提取并量化這些潛在的語義結(jié)構(gòu)，進(jìn)而消除同義詞、多義詞的影響，提高文本表示的準(zhǔn)確性。LSA思想最初應(yīng)用于文本信息檢索領(lǐng)域，有效地解決了同義詞和多義詞的問題，隨著應(yīng)用領(lǐng)域的不斷拓展，LSA在信息過濾、信息分類、聚類、交叉語言檢索、信息理解、判斷和預(yù)測等眾多領(lǐng)域中得到了廣泛的應(yīng)用[3，4]。

2.3 算法基本思想

基于RANSAC的潛在語義搜索算法的主要思想是，在原始的文檔矩陣基礎(chǔ)上，對數(shù)據(jù)先進(jìn)行RANSAC處理，得到新的數(shù)據(jù)矩陣。在此基礎(chǔ)上使用SVD提取特征向量，最后通過詞頻信息對特征進(jìn)行層次化分類。具體算法流程如下：

1）生成詞-文檔矩陣X。從專家?guī)?，專家特長字段抽取原始文本并按照既定的自然語言分割標(biāo)記如：標(biāo)點(diǎn)空格斜杠等自動(dòng)篩選出關(guān)鍵詞，并將抽取的關(guān)鍵詞生成關(guān)鍵詞矩陣X。

2） 使用RANSAC算法對原始矩陣X進(jìn)行處理獲得精簡數(shù)據(jù)集R。對高維度海量的關(guān)鍵詞矩陣進(jìn)行預(yù)處理，運(yùn)用RANSAC算法對原始數(shù)據(jù)矩陣進(jìn)行精簡，排除關(guān)鍵詞矩陣中孤立的、低效益的特征點(diǎn)。此算法不管是在數(shù)據(jù)量，還是在空間維度上，都能對原始數(shù)據(jù)進(jìn)行精簡，同時(shí)還能有效排除孤立的噪聲數(shù)據(jù)。

3） 對新數(shù)據(jù)集進(jìn)行SVD分解提取主成分得到特征矩陣T。RANSAC簡化、降維處理，大大減少了提取主成分的時(shí)間，同時(shí)也使得矩陣特征矩陣T中的特征區(qū)分度更高、更為明顯。

矩陣的奇異值分解：這里，R為初始矩陣，設(shè)r為m*n實(shí)矩陣，且n階方陣[RTR]的非0特征值的算術(shù)平方根為矩陣X的奇異值。則：

[R=T×S×TD] （1）

其中，[Tm×r=（t1，t2，…，tr）]為正交矩陣，其中[t1，t2，…，tr]為R的左奇異向量，并且是[RRT]的特征向量；

[Sr×r=diag（σ1，σ2，…，σr）] （2）

[Sr×r]為對角矩陣，[σ1，σ2，…，σr]為X的所有奇異值，并滿足以下關(guān)系：[σ1≥σ2≥…≥σr>0]； [Dn×r=（d1，d2，…，dr）]為正交矩陣，其中[d1，d2，…，dr]為R的右奇異向量，并且是[RTR]的特征向量。

設(shè)定k值，保留[σ1，σ2，…，σk]，同時(shí)只保留T和D的前k列，得到原矩陣的近似矩陣R。

[R=T×S×DT] （3）

4）對各個(gè)特征向量進(jìn)行相似度分析，并使用詞頻信息對其進(jìn)行分類。根據(jù)專家?guī)炀唧w應(yīng)用的特點(diǎn)與需求，使用詞匯與詞匯的關(guān)進(jìn)進(jìn)行相似度分析，并進(jìn)行聚類，生成相似度聚類矩陣E。最后使用詞頻權(quán)重算法對其進(jìn)行加權(quán)變換形成最終特征空間。

對上一步得到的近似矩陣R進(jìn)行正向乘法。[R^' R'T=T'S'D'T?D'S'T T'T]，這里，[S'=S'T，D'D'T）=I]，因此：

[R' R'T=T' S' I?S'T'T）=T'S'2 T'T] （4）

其中，矩陣[R' R'T]的第i行第j列表明了詞匯i和詞匯j的相似程度。

求解（4）所得到的特征矩陣可稱之為相似度聚類矩陣E。矩陣E所描述的相似關(guān)聯(lián)度，僅與原始文檔數(shù)據(jù)中關(guān)鍵詞關(guān)聯(lián)信息相關(guān)。而在實(shí)際專家?guī)鞕z索應(yīng)用中，各關(guān)鍵詞存在不同的重要級(jí)別。如：與物聯(lián)網(wǎng)關(guān)聯(lián)更多的，應(yīng)該是傳感器與嵌入式技術(shù)，而與軟件技術(shù)或者工業(yè)設(shè)計(jì)關(guān)聯(lián)度較弱。每一個(gè)特征詞匯對文檔的貢獻(xiàn)度不盡相同。故本文使用詞頻權(quán)重對相似度特征矩陣進(jìn)行權(quán)重賦值。這里采用了直接而簡單的詞頻權(quán)重：

[ajk=fjk] （5）

由于專家?guī)斓膽?yīng)用需求，該文中的權(quán)重由兩部分構(gòu)成：局部權(quán)重和和全局權(quán)重。局部權(quán)重記作LW（i，j），全局權(quán)重記作GWT（i，j）。經(jīng)過權(quán)重分配后的相似度聚類矩陣可表示為[f?E]。

5） 最后，根據(jù)原有矩陣的截?cái)嗥娈愔颠M(jìn)行近似計(jì)算，即計(jì)算矩陣[RK|A]的奇異值分解，其中：[RK=TK SK DTK]為原矩陣的截?cái)嗥娈愔稻仃嚕珹為新增數(shù)據(jù)集。并通過SVD-Updating算法更新數(shù)據(jù)庫。

3 實(shí)驗(yàn)及分析

本文方法在市知識(shí)產(chǎn)權(quán)據(jù)專家數(shù)據(jù)庫上進(jìn)行了一系列測試，其命中率和查準(zhǔn)率如表1所示：

表1 搜索對比表

[特征值＼&測試用例＼&本文方法＼&傳統(tǒng)檢索＼&感興趣數(shù)據(jù)＼&本文方法＼&傳統(tǒng)檢索＼&檢索結(jié)果＼&命中結(jié)果＼&檢索結(jié)果＼&命中結(jié)果＼&命中率＼&查準(zhǔn)率＼&命中率＼&查準(zhǔn)率＼&單關(guān)鍵詞＼&地理信息＼&62＼&58＼&58＼&58＼&62＼&94%＼&93%＼&100%＼&93%＼&計(jì)算機(jī)科學(xué)＼&105＼&100＼&65＼&62＼&100＼&95%＼&100%＼&95%＼&88%＼&GIS＼&62＼&62＼&20＼&20＼&62＼&100%＼&100%＼&100%＼&32%＼&多關(guān)鍵詞＼&計(jì)算機(jī)科學(xué)，GIS＼&167＼&160＼&85＼&85＼&170＼&95%＼&94%＼&100%＼&50%＼&語義表述＼&地理信息，計(jì)算機(jī)技術(shù)專家＼&52＼&50＼&0＼&0＼&60＼&100%＼&83%＼&0＼&0＼&計(jì)算機(jī)資深

專家＼&54＼&52＼&0＼&0＼&57＼&100%＼&91%＼&0＼&0＼&]

從以上實(shí)驗(yàn)數(shù)據(jù)分析可以得到如下結(jié)論：

1）對于單關(guān)鍵詞的中文檢索，在精確含義詞匯檢索中本文方法與傳統(tǒng)方法差異不大，而在廣義或者模糊含義詞匯的檢索中，該文方法能夠檢索出更多有價(jià)值的信息，查準(zhǔn)率更高；

2）對于單關(guān)鍵詞的英文檢索，只能檢索到包含相同英文字母的信息，不能獲得其真實(shí)本意不能查到相關(guān)中文信息，其命中率和查準(zhǔn)率都比較低，而本文方法則能夠取得較為滿意的結(jié)果；

3）對于多特征中英文混合檢索，僅僅靠關(guān)鍵詞匹配的傳統(tǒng)檢索搜索出的結(jié)果不能令人滿意，而本文方法同樣達(dá)到了比較高的準(zhǔn)確率，結(jié)果令人滿意；

4）對于語義方式表述的特征樣本，該文方法能夠檢索出有價(jià)值的數(shù)據(jù)，并且查準(zhǔn)率較高，而相反在傳統(tǒng)檢索方法中，由于沒有出現(xiàn)直接關(guān)鍵詞，故無法獲得檢索結(jié)果。

參考文獻(xiàn)：

[1] Bartoli Adrien， A Random Sampling StrategyFor Piecewise Planar Scene Segmentation[J]. Computer Vision and Image Understanding， 2007， 105（1）： 42-59.

[2] 葉昭輝，楊高峰，楊岳湘.一種基于潛在語義分析的中文網(wǎng)頁自動(dòng)摘要方法[J].廣西大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，37（2）：342-345.

[3] 蔡嘉誠.潛在語義索引技術(shù)在知識(shí)產(chǎn)權(quán)專家?guī)熘械难芯颗c應(yīng)用[D].蘇州大學(xué)碩士論文，2010.04.

[4] 楊文清.基于Web文檔庫的中文全文檢索技術(shù)與實(shí)現(xiàn)[D].南京大學(xué)計(jì)算機(jī)科學(xué)與工程系碩士論文，1998.

[5] Ishii，Murai，Yamada.Text Classification by combining Grouping[J]，LSA and KNN，Computer and Information Science，July 2006：148-154.

[6] Sudarsun.S，Venkatesh Prabhu.G Sathish Kumar.V.Role of weighting on TDM in Improvising PerformanceofLSA on TbXt Data[C]，Annual India Conference，2006，Sept.2006：1-6.

[7] 余正濤，樊孝忠，郭劍毅，等.基于潛在語義分析的漢語問答系統(tǒng)答案提取[J].計(jì)算機(jī)學(xué)報(bào)，2006，29（10）：1889-1893.

[8] 蓋杰，王怡，武港山.基于潛在語義分析的信息檢索[J].計(jì)算機(jī)工程，2004（30）.

[9] 戚涌，徐永紅，劉鳳玉.基于潛在語義標(biāo)引的Web文檔自動(dòng)分類[J].計(jì)算機(jī)工程與應(yīng)用，2004（22）：28-31.