基于RANSAC潛在語義分析的專家?guī)鞕z索

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

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

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

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

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

2.1 RANSAC算法

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

2.2 潛在語義分析

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

2.3 算法基本思想

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

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

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

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

矩陣的奇異值分解：這里，R為初始矩陣，設(shè)r為m*n實矩陣，且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]，同時只保留T和D的前k列，得到原矩陣的近似矩陣R。

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

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

對上一步得到的近似矩陣R進行正向乘法。[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)。而在實際專家?guī)鞕z索應(yīng)用中，各關(guān)鍵詞存在不同的重要級別。如：與物聯(lián)網(wǎng)關(guān)聯(lián)更多的，應(yīng)該是傳感器與嵌入式技術(shù)，而與軟件技術(shù)或者工業(yè)設(shè)計關(guān)聯(lián)度較弱。每一個特征詞匯對文檔的貢獻度不盡相同。故本文使用詞頻權(quá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ù)原有矩陣的截斷奇異值進行近似計算，即計算矩陣[RK|A]的奇異值分解，其中：[RK=TK SK DTK]為原矩陣的截斷奇異值矩陣，A為新增數(shù)據(jù)集。并通過SVD-Updating算法更新數(shù)據(jù)庫。

3 實驗及分析

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

表1 搜索對比表

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

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

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

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

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

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

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

參考文獻：

[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)頁自動摘要方法[J].廣西大學學報：自然科學版，2012，37（2）：342-345.

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

[4] 楊文清.基于Web文檔庫的中文全文檢索技術(shù)與實現(xiàn)[D].南京大學計算機科學與工程系碩士論文，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].計算機學報，2006，29（10）：1889-1893.

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

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