基于社區發現的專利查詢擴展方法*

陳高榮 徐 建

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

專利文件是重要的知識財富，可以幫助保護個人，組織和公司的利益。專利文件具有巨大的研究價值，對工業，商業，法律和政策制定團體都是有益的。如果仔細分析專利文件，可以揭示重要的技術細節和關系，可以說明領先的技術趨勢，可以啟發新穎的技術解決方案，從而可以做出至關重要的投資決策［1］。

現有專利檢索技術中的挑戰如下：1）高召回率。專利檢索是一項面向召回的任務，其目標是在現有的專利庫中找到所有相關文檔［2］，檢索的目的是保證創新理念與任何先前授予的專利之間不存在侵權。2）長查詢。與查詢非常短的Ad hoc查詢和網絡搜索不同，專利查詢輸入通常很長，甚至包括整個專利申請。3）用詞含糊不清。申請人頻繁使用了同義詞和別名，常常使用不常見的非標準技術術語表達常見的語義，以保持專利權利要求的唯一性［3～4］，這導致專利術語不匹配問題，使專利檢索變得困難。因此，有效的專利檢索仍然是一項具有挑戰性和困難的檢索任務。

查詢拓展能很好地解決專利查詢中術語不匹配的問題。現有的擴展方法大多是針對普通文檔，如果直接將傳統的信息檢索方法用于專利檢索的任務中，很難取得較好的結果。不同于普通文檔查詢擴展，專利本身是一種包含大量技術術語的半結構文檔，并且包含大量復雜術語表達以及創造詞。由于專利的特性和專利檢索高召回率的要求，傳統的查詢擴展方法在專利檢索任務中難以獲取用戶完整的查詢意圖。另外，在專利查詢擴展過程中會不可避免地引入噪聲詞，出現主題漂移現象，導致查詢召回率降低。

因此本文提出一種基于社區發現的專利查詢擴展方法CD-PQE（Community Discovery Based Patent Query Expansion），該方法從專利文檔集中提取專利詞表，并構造對應的詞網絡，充分地利用了專利文檔集中的專業術語和創造詞之間的相關性，又通過社區發現算法構造稠密子圖獲得最終得擴展詞集，豐富并拓展了查詢詞集，減少了噪聲詞的加入，防止主題漂移。通過實驗驗證本文方法與一些經典的方法相比在準確率和召回率有著的更優的效果。

2 相關工作

專利文件的表達往往比其他文件更加模糊和專業，在同一技術上使用不同的術語表示，這使得搜索相關專利變得更加困難。早期的工作中［7］，采用的是基于主題的查詢重構方法，但該方法不能很好的利用創造詞導致結果準確率并不高。此外通過分類提高詞與領域的耦合度的方法也被用于專利檢索中，Wang和Qian等［6］，提出一種新穎的復合域視角模型，該模型將查詢專利的技術特征轉換為特定的復合分類域并生成方面查詢，加強了技術特征和技術領域之間的相關性。但原始的查詢詞對于用戶查詢的表達往往沒那么全面。通過查詢擴展可以有效地完善查詢意圖，以達到提高專利檢索的效果。現有查詢擴展的主要研究方法包括基于反饋的方法、基于詞典的方法和基于語義的方法。

PRE模型是一種常見的基于反饋的查詢擴展方法通過從初始搜索中排名靠前的偽相關結果中富集擴展詞條來擴展查詢詞［8～9］。Martins等［10］將最新索引與帶有外部語料庫的PRF結合使用，可以檢索更多相關文檔并提高排名。但檢索多針對某一專利領域，在不同專利領域域的信息差異較大，PRE未能很好地解決這個難題，而且PRE模型中常常存在著主題漂移現象。

基于詞典的方法使用額外的詞典作為拓展源進行詞拓展，往往基于WordNet、Wikipedia等外部資源構建查詢擴展［11～12］。許侃等［16］利用谷歌搜索引擎來替代詞典將外部信息源作用于專利檢索，雖然在檢索準確率上有一定成效，但依然沒有解決專利名詞的特殊性的問題。但是對于某些特定的主題查詢，這些方法的性能并不穩定，但仍無法滿足專利檢索的需求。

基于語義的方法在最大程度上保留查詢中查詢詞相關的語義信息，通過語義關系選擇與查詢詞語義相近的擴展詞。El Ghali等［13］基于上下文提取了一種潛在語義索引方法；徐博等［14］提出了一種融合語義資源的生物醫學查詢，該模型分為兩部分，首先通過偽相關反饋進行查詢拓展，然后基于拓展詞共現和MeSH詞表兩種方式加權對拓展詞進行綜合選擇，最終完成拓展。這些方法能提高拓展詞的有效性從而提高檢索的召回率，但現有的基于語義的拓展查詢中直接通過計算查詢與擴展詞的相似度來判斷拓展詞的有效性，忽視了擴展詞的在擴展資源中的重要性，這個過程會引入噪聲詞出現在擴展詞集中，影響檢索結果。

3 專利自動查詢擴展算法

專利檢索中專利文本多以非結構化的形式存儲在信息系統中，高召回率和準確率的檢索入口可以更好地幫助用戶獲得完整且準確的檢索結果。本文提出了基于社區發現的專利自動查詢擴展方法模型。該模型主要分為兩個模塊：建立具有權重的專利詞網絡及基于稠密子圖的社區發現算法。

3.1 建立具有權重的專利詞網絡

專利詞網絡是專利知識的一種圖解表示，用節點表示關鍵詞和概念，弧線表示關鍵詞間的聯系，本文首先從專利數據庫中提取專利中的關鍵詞，專利數據庫中有文檔D={d1，d2，d3，…，dk}，對于每個文檔通過TF-IDF獲得每個文檔的關鍵詞Wi={wi1，wi2，wi3，…，win}將所得排名靠前的關鍵詞匯總匯得關鍵詞候選集W={w11，w12，…，win}，再通過word2vec訓練獲得最終關鍵詞向量矩陣H用于專利詞網絡中相似度權重的構建。

根據詞向量表，構建一個基于關鍵詞的無向圖G=(V，E，W)來表示詞與詞之間的關系，其中節點集V={v1，v2，…，vn}，n=|V|，表示由關鍵詞構成的節點集；邊集E中每條邊ei，j對應V中一對頂點(vi，vj)之間的連接關系，m=|E|；W是G的權重矩陣，表示V中一對頂點(vi，vj)之間的相似度為邊的權重。將所有專利文本中的關鍵詞通過網絡的方式聯系起來更有利于詞之間關系的發現與計算。

本文通過計算兩個詞向量的余弦值來判定兩個詞的相關度，計算方式如下所示：

其中hi={x1，x2，…，xn}，hj={y1，y2，…，yn}分別是關鍵詞vi，vj的向量表示形式。

基于詞向量相似度構建關鍵詞網絡算法如下：

3.2 基于稠密子圖的社區發現算法

社區發現算法是指從復雜網絡中發現并識別出這些網路中高度相關的對象組，這些組別被稱為社區［18］。在本文首先構造關鍵詞網絡，根據邊權重與詞的網絡拓撲結構相結合，作為社區發現算法的依據，發現識別與查詢關鍵詞高度相關的詞，將這些詞構成了擴展詞集，其中這些擴展詞集符合社區的概念。

本文提出了一種基于稠密子圖的社區發現算法。首先將查詢關鍵詞Q={q1，q2，…，qn}作為種子節點為初始點，根據種子節點qi對子圖的適應度函數將種子節點擴展為局部稠密子圖；當所有的局部稠密子圖構造結束后將子圖進行合并獲得最終關鍵詞擴展集。

為了方便說明本文對局部稠密子圖做了如下定義：局部稠密子圖集為S={s1，s2，…，sn}，其中si=(Vs，Es，Ws)，si表示查詢關鍵詞qi作為種子節點獲得的稠密子圖，并且Vs?V，Es?E，Ws?W。

適應度函數是評價稠密子圖稠密程度。假設s為圖G的一個連通子圖，Vs表示該連通子圖的頂點集，Es表示其邊集，其中ns=|Vs|，ms=|Es|；為獲得一個完全圖，需要在連通子圖s中添加條邊，將原關鍵詞網絡圖G中邊權重的平均值作為新添加的邊的權重。通過原連通子圖s和新添加的邊的權重的差異作為評價s稠密度的評估函數f(s)。

其中W(VS)為原連通子圖的權重值，是新添加邊的權重值，Vs為稠密子圖的點集，w(vi，vj)為點vi，vj之間邊的權重，E和V分別為關鍵詞網絡圖G的點集和邊集。顯然如果函數f(s)越大，則子圖s越稠密。根據定義若|Vs|=1，即s中只有一個節點f(s)=0。

對于節點v?Vs，定義v對s的適應度函數：

對于一個節點如果稠密度的適應度函數的值越高，說明這個節點與這個子圖的關聯性就越強，將滿足σ(v，s＞a)（平均稠密度閾值）的節點擴展到子圖s中。

隨著以查詢關鍵詞為種子節點的圖集S={s1，s2，…，sn}，并將其合并，去除子圖中重疊的部分獲得包含擴展詞的子圖DS。但隨著詞節點的加入可能存在距離查詢關鍵詞Q中某一種子節w*點較遠的節點w也會加入到子圖中，這個過程會導致噪聲詞的出現在子圖S中。因此同時還設置了距離函數D(w)，對節點與種子節點的距離進行限制。

其中d(w，w*)表示節點w到w*的最短距離，其中|NQ|為查詢詞集的數量，|V|為關鍵詞網絡中關鍵詞的數量。當D(w)≤d時（d表示距離閾值）可以有效地避免噪聲詞的干擾。

算法2基于稠密子圖的社區發現算法

如圖1所示為部分查詢關鍵詞網絡子圖的示例，假設初始查詢詞集為Q={w3，w7，w10}，所以需要找到包含節點w3，w7，w10的稠密子圖。以q1=w3的例首先初始化其擴展子圖s1此時Vs1={w3}，在關鍵詞網絡G中依次找到節點w2，w4，w5，w6，并計算對s1的適應度函數σ(v，s1)，并判斷σ(v，s1)＞a，如果滿足則加入圖s1中，最后計算得Vs1={w1，w2，w3，w4，w5，w6}，分別得到w7，w10對應的擴展子圖s2，s3，其中Vs2={w6，w7，w8}，Vs3={w9，w10，w11}，將子圖s1，s2，s3合并獲得圖DS，最后判斷DS中得節點與查詢詞集Q中得節點的距離將D(w)＞d的節點刪除，減少擴展詞集中得噪聲詞。

圖1 部分查詢關鍵詞網絡子圖

4 實驗

4.1 數據集

專利數據集：在本文研究中使用的數據集是CLEP-IP 2010專利數據集。CLEP-IP 2010包含1985年至2001年之間發布的260萬份不同的專利文件，并具有標題，摘要，描述和權利要求。在本文的實驗中，使用了CLEP-IP 2010的英文小節，共計2000條查詢。

4.2 實驗評價指標

為了進行評估，本文使用召回率（Recall），平均精度（Mean Average Precision，MAP），專利檢索評估得分（Patent Search Evaluation Score，PRES）量化實驗結果。

召回率：檢索到相關專利與所有相關專利的比率。

T(q，Z)表示查詢q檢索結果中排名前Z的相關文檔的數量，z是指專利庫中相關文檔的數量。

平均精度（MAP）：它是所有測試專利的平均精度的平均值。

其中Rjk是從檢索到排名前k個的檢索結果的集合，如果檢索列表中未出現相關文檔，則精度值為0。

專利檢索評估得分（PRES）［19］：是基于召回的專利檢索的另一種有效評估指標，可以綜合測量召回率和排名質量。

其中ri為檢索第i個相關文檔的等級，N表示集合大小，n為相關文檔的數量，R為召回文檔中相關檢索文檔的數量。

4.3 參數選擇

本節主要對實驗中的一些參數的設置和選擇過程進行討論，本文方法參數包括構造專利詞網絡的相似度閾值s、稠密子圖的平均稠密度閾值a和距離閾值d。本節在參數評估指標選擇召回率和PRES。

圖2給出的是構造專利詞網絡的相似度閾值s對檢索性能的影響，在相似度閾值s=0.5的時候PRES達到最優解，當s=0.7時召回率最優，根據性能變化將相似度閾值設置為0.5。

圖2 相似度閾值s對檢索性能的影響

圖3給出的是稠密子圖的平均稠密度閾值a對檢索性能的影響。從實驗結果可看出在召回率和PRES值上，當a取0.6時檢索性能最佳。

圖3 平均稠密度閾值a對檢索性能的影響

圖4給出的是稠密子圖的距離閾值d對檢索性能的影響。距離閾值與最終的擴展詞集的數量有著強聯系。從實驗結果可以看出當d取值為0.35時在兩種評估指標上取得均衡值。因此最終將距離閾值設置為0.35，從圖5可查此時平均擴展查詢詞為70個，檢索性能達到最優。

圖4 距離閾值d對檢索性能的影響

圖5 距離閾值與最終平均擴展詞數量關系

4.4 基于社區發現的專利查詢擴展方法效果

本節基于CLEP-IP 2010大型專利數據集進行實驗，實驗中對比方法有：語言模型檢索（Language Model，LM），詞依賴模型檢索［15］（Term Dependency，TD），相關模型查詢擴展（Relevance Model，RM）以及基于聚類的查詢擴展模型（Cluster-base Model，CM）。本文選用的相關模型查詢擴展是偽相關反饋，基于聚類的查詢擴展方法則是通過K-means聚類選擇擴展詞。實驗結果如表1所示。

表1 基于CLEP-IP 2010數據集檢索結果

從表中實驗結果可以看出在召回率和PRES方面CD-PQ取得最優值；而在MAP方面未能取得最優值，是由于專利名詞存在特殊性，擴展一些與查詢專利描述相近但未用于專利中的相關術語，從而降低大多數相關專利的排名。上述的結果說明，CD-PQ能有效的改善并提升現有檢索的性能，特別是在召回率和PRES上表現良好，這是因為本文通過社區網絡中圖發現的方式判斷詞節點是否屬于同一類別，能夠更大程度地覆蓋高質量的擴展詞，減少噪聲詞加入到擴展詞集中；其次該方法是在專利數據集上構建的專利詞網絡，這能很好地解決專利中出現的創造詞無法用于檢索中的問題，使得檢索更具針對性。

5 結語

本文探索了基于社區發現的專利自動查詢擴展方法，以幫助分析人員盡可能多地找到所有可能相關的文檔。本文首先從專利數據庫中獲得專利領域關鍵字詞庫，然后通過詞庫構造關鍵詞網絡，然后通過社區發現算法獲得擴展詞集。通過對專利文件集合的評估證實了本文方法的有效性，能夠有效地提高專利檢索的準確率和召回率。未來工作方面會在本文的基礎上對文本相似度比較進行優化，進一步探索出提高專利檢索性能的綜合方法。