一種基于關聯度的Skyline多目標優化文獻檢索方法設計與測試

王 春 梅

(吉林農業大學, 吉林 長春 130000)

?

一種基于關聯度的Skyline多目標優化文獻檢索方法設計與測試

王 春 梅

(吉林農業大學, 吉林 長春 130000)

查詢與結果排序是文獻檢索系統的兩個重要指標，直接影響著用戶對文獻資源的利用率。針對目前文獻檢索排序策略上存在的不足， 從用戶檢索文獻的需求出發，在Skyline算法的基礎上提出一種基于Skyline關聯度的多目標優化文獻檢索排序方法，將文獻之間的關聯程度作為查詢算法的主要條件進行檢索和排序，從而將有價值的資源挖掘出來。最后， 基于CNKI數據庫平臺對相關文獻進行檢索，并應用所設計模型對檢索結果進行重新排序。結果表明，該方法可有效優化排序結果，將關聯度較高的文獻信息挖掘出來，滿足用戶對期望資源的檢索要求，提高了文獻的利用率，具有一定的參考價值。

文獻檢索; Skyline查詢; 關聯度; 優化

0 引 言

信息技術的發展，用戶可以足不出戶地通過互聯網查詢所需資料，尤其對數字圖書館電子文獻的需求，更是與日俱增。人們可以借助于文獻檢索工具，方便快捷地找到自己所需信息。而就目前的基于關鍵字的檢索現狀來看，常出現返回不相關的文獻信息、文獻不按規則排序、檢索結果關聯度不高等弊端[1-2]，隨著用戶對檢索需求的日益深化，暴露出的局限性也越來越明顯?；诖?，尋求一種高效的文獻檢索工具成為研究人員關注的重點。文獻[3]通過具有語義特征的本體概念對文獻集進行描述，提出一種根據上下文評價的文獻檢索方法，取得了很好的應用效果。文獻[4]在Lucenel的基礎上，設計了一種基于語義的文獻檢索系統，該查詢模塊與Lucene契合度高，檢索效果好。文獻[5]針對文獻檢索過程中的分類問題，定義了特征提取的概念，提出一種基于支持向量機的內嵌空間特征選擇查詢與排序方法。文獻[6]針對文獻檢索中存在的信息冗余或信息缺失等問題，采用統一數字化標度方法，構建了一種基于檢索項匹配的文獻檢索模型，使用戶直觀的了解文獻的等級分布以及文獻之間的相互聯系，縮短了檢索時間，提高了文獻利用效率。

在現有成果的基礎上，本文將文獻檢索后的排序策略作為主要的研究內容，設計了一種基于關聯度的Skyline多目標優化文獻檢索方法，將文獻之間的關聯度作為排序的重要衡量標準，從而使用戶得到一個更加滿意的查詢結果，目的是為了加快查詢速度，提高文獻的利用效率。

1 文獻利用率影響因素分析

衡量文獻檢索利用率的兩個重要指標是檢索速度和排序策略，有效的排序方式是保證檢索結果被用戶有效利用的前提。文獻利用率主要受篩選機制和用戶檢索習慣的影響。

1.1 篩選機制對文獻利用率的影響

信息源多，無用信息量大是目前文獻檢索存在的普遍問題。雖然搜索引擎功能日益強大，但由于信息資源急劇增加，導致用戶檢索結果數量龐大。譬如在中國學術期刊網絡出版總庫(CNKI)中以“檢索”為關鍵詞進行查詢，輸出的結果超過22萬條。各信息良莠不齊，如果沒有一個合理的篩選機制及有效的檢索結果處理手段，會使用戶面對大量的無用信息，無從下手，而最后無法找到自己真正想要的文獻，導致文獻利用率大打折扣。

1.2 檢索習慣對文獻利用率的影響

一般的數據庫查詢系統都包括初級檢索和高級檢索兩種途徑，但多數用戶都習慣于使用初級檢索方式，而很少使用高級檢索。這使檢索結果雖然包含了帶有某關鍵詞的所有數據，但不能真正按照用戶的意愿處理，這種情況下作者只能一頁一頁的去查看結果，浪費大量時間，也很難獲得滿意的信息。

2 Skyline算法研究

Skyline計算是一個典型的多目標優化的問題，作為數據挖掘技術的重要分支，Skyline算法在多標準決策、數據挖掘以及網絡作業調度等領域應用非常廣泛，尤其是在數據的查詢計算方面更具有十分重要的應用前景[7-8]。Skyline查詢的主要目標是從一個潛在的、海量的數據中找出用戶感興趣的、相對重要的點，過濾掉一些不需要的點，從而為進一步的數據處理工作打下基礎，減少不必要的資源浪費。

2.1 算法分析

設數據空間Y包含了n個數據集，表示為：Y=D1×D2×…×Dn。若數據集Di(1≤i≤n)又包含了j個數據，即(d1,d2, …,dj)∈Di,dj表示數據Di的第j維值，定義如下[9-10]：對于Di中任意兩個數據P和Q，若對象P在所有維度上的屬性值都不比對象Q差，并且至少在某一維上的屬性值優于對象Q，則稱P支配Q，記作：PQ。根據以上語義，實現Skyline查詢的嵌套SQL語句可表示為：

SELECT...FROM...WHERE

GROUP BY...HAVING...

SKYLINE OF [DISTINCT]d1[MIN|MAX|DIFF], …, dj[MIN|MAX|DIFF]

2.2 算法實例

Skyline算法實例[11]：要去海灘游玩，想找一個既便宜又靠近海灘的賓館。而實際上，這存在一個矛盾，距離海邊越近的酒店通常價錢越高，而價錢相對便宜的酒店一般距離海邊很遠，它們的關系如表1所示。

表1 賓館價格與距海邊距離關系

這時我們就希望有一個旅館集合，能為我們的選擇提供幫助，我們稱這個集合為Skyline，每個可以選擇的賓館為SP(Skyline Point)點。如圖1所示，對于旅游者來說，很明顯折線上p1，p2，p5三個SP點是比較偏好的選擇，其他非SP點可以不做考慮，因為總可以在折線上找到一個SP點，或者在價格，或者在距離上優于非SP點。

2.3 Skyline文獻檢索排序模型

通常用戶期望將最匹配的檢索結果排在最前面，可見文獻排序策略的優劣，直接影響用戶的檢索效率[12]。

Skyline查詢是一種典型的多目標優化查詢方法，根據其查詢原理，研究人員提出了基于Skyline的迭代排序模型：假設用戶對檢索結果集的期望具有多維性，期望維度大于等于1。對多維文獻集M進行Skyline查詢操作，得到Skyline文獻集S1，然后對剩余的子文獻集N=M-S1再進行Skyline查詢操作，得到Skyline文獻集S2，……，依此類推，不斷迭代，直到剩余文獻集為空，最后按檢索的先后順序將得到的文獻集排列，最后抒結果返回給用戶，其模型如圖2所示[13-15]。

圖1 SP點集合示意圖

圖2 Skyline查詢模型

與傳統的文獻排序方案相比，Skyline迭代排序方法可以從不同維度進行多目標優化查詢，并均衡各維度之間的關系進行合理排序。但是由于沒有考慮文獻之間的關聯作用，導致一些本來滿足作者要求的文獻被Skyline迭代算法排在很靠后的位置，從而被忽視。

3 基于關聯度的Skyline多目標優化文獻檢索模型設計

學者們撰寫論文或著作，一般會對已有的成果進行引用。同時，一個領域的成果在某些字段或內容上也有很多相似之處，從而使各個文獻之間建立起一種關聯，反映了文獻之間的相關性。根據文獻的關聯度往往可以進一步獲得更有參考價值的文獻資料。基于此，本文將文獻之間的關聯度作為文獻查詢時的衡量指標，設計了一種基于關聯度的Skyline查詢模型，如圖3所示。模型的主要功能如下：

首先在查詢模塊中通過關鍵字和不同參考維度進行檢索，過濾掉大部分不相關的文獻，以提高整體檢索效率；將查詢得到的文獻庫在排序模塊中進行Skyline查詢，得到Skyline文獻集和非Skyline文獻集，通過計算相關度將有價值的非Skyline文獻挖掘出來，并與Skyline文獻進一步排序，從而使用戶得到滿意的檢索結果。

4 測試論證

為驗證基于關聯度的Skyline文獻檢索與排序模型的有效性，采用該模型進行檢索論證，并與傳統文獻檢索排序方法進行對比。在中國知網(CNKI)期刊庫中以“Skyline查詢”為主題進行檢索，檢索時間從2009年1月1日～2013年12月31日，結果按被引頻次由高到低排序，共搜索到66條記錄，為使驗證更具操作性，僅以被引頻次和發表時間作為參考維度，部分檢索結果如表2表示。

圖3 基于關聯度的多目標優化文獻檢索排序模型

表2 部分檢索結果列表

從表中可以看出，個別文獻與用戶期望結果有一定出入，從而增加了用戶尋找目標文獻的時間。對文獻集合進行兩個維度Skyline查詢處理，得到Skyline初始文獻集M，根據各文獻之間的引用與關聯關系，計算每個非Skyline文獻的Skyline關聯度大小。以Skyline關聯度為排序依據，重新對文獻集M進行排序，當存在Skyline關聯度相同的文獻時，將按文獻被引頻次的大小排序，優化后的排序結果如表3所示。

表3 Skyline關聯度排序結果

結果表明，與優化之前相比，各文獻的排列順序發生了很大的變化，說明利用所設計模型能有效把原本排序位置靠后，但與用戶期望資源關聯度較高的文獻信息挖掘出來，同時過濾掉原本排名靠前但關聯度較低的文獻，符合用戶真正的檢索需求。

5 結 論

資源利用率是評價文獻檢索有效性的重要指標，隨著文獻數量的迅速增長，傳統關鍵字的檢索方法已經很難滿足用戶的檢索需求，因此尋求一種高效的文獻檢索與排序方法成為研究人員關注的重點。本研究從用戶檢索需求出發，在基于Skyline查詢方法的基礎上引入關聯度的概念，將各文獻之間的關聯度作為排序的衡量指標，從而使Skyline文獻集與非Skyline文獻集之間緊密聯系起來，以挖掘出滿足用戶需求且容易被忽視的文獻，從而提高了資源的利用效率。測試結果表明，該方法可有效優化排序結果，真正把用戶需要的文獻信息挖掘出來，提高了文獻的利用率和用戶工作效率，設計方案滿足實際需求，具有一定的實際應用價值。

[1] 蔣 濤, 張 彬, 余法紅,等. 排序的相互k-Skyband查詢算法[J]. 軟件學報, 2015, 26(9): 2297-2310.

[2] 孫圣力，戴東波，黃震華，等. 概率數據流上skyline查詢處理算法 [J].電子學報, 2009, 37(2): 285-293.

[3] Nattakarn, Ratprasartporn. Evaluating Different Ranking Functions for Context-Based Literature Search [N]. Data Engineering Workshop，2007.

[4] JIANG Y F, WANG H. Design and implementation of semantic search engine based on Lucerne [J]. Computer Engineering and Design，2008(20).

[5] 周綺鳳,楊小青，洪文財，等.內嵌空間排序支持向量機及其在文本檢索中的應用[J].信息與控制，2010,39(5):629-634.

[6] 孫笑明，崔文田.一種網絡展現文獻檢索結果的理論模型[J].情報學報,2011，30(2).

[7] 向劍平，鄭皎凌. Skylin計算在多維排序問題上的分析[J]. 太原師范學院學報(自然科學版)，2009，8(2): 82-84.

[8] 楊立龍，董一鴻，何賢芒. 分布式環境下的Skyline代表點查詢[J]. 計算機應用研究,2015(1):102-107.

[9] 瞿 亮,楊 貫.基于本體的專業文獻檢索[J].計算技術與自動化，2007，26(1).

[10] Lin Zhu, Yufei Tao， Shuigeng Zhou. Distributed Skyline Retrieval with Low Bandwidth Consumption [J]. IEEE Trans. Knowl. Data Eng., 2009, 21(3): 384-400.

[11] 黃子晴，劉東蘇.Skyline查詢處理在文獻檢索排序中的應用[J]. 情報理論與實踐,2011(10):104-108.

[12] 劉松濤. 基于引文排序的科技文獻檢索初探[J]. 制造業自動化，2010，32(10): 129-131.

[13] 王曉偉，黃九鳴，賈 焰. 分布式不確定數據上的概率Skyline計算[J]. 計算機科學與探索, 2010, 4(10): 951-961.

[14] 楊林青，李 湛，牟雁超，等. 面向大規模數據集的并行化Top-k Skyline查詢算法[J]. 計算機科學與探索，2015,9(8)：897-904.

[15] Wei Xiaojuan，Yang Jing，Li Cuiping，etal． Skyline query processing [J]. Journal of Software，2008， 19(6): 1386-1400.

Design and Experiment of a Skyline Multi-objective Optimization Literature Retrieval Method Based on Correlation Degree

WANGChun-mei

(Jilin Agricultural University, Changchun 130000, China)

The querying and sorting the results are two important indexes of literature retrieval system, they directly affect the utilization of literature resources. In view of the current literature retrieval sequencing strategy, this study started from the user retrieval information needs, and was based on Skyline algorithm to propose a multi-objective optimization literature retrieval ranking method. The degree of correlation of the literature was the main condition and used to retrieving and ranking information, so that it could have the value of resource mining. Based on the CNKI database, relevant literature was retrieved, and application design model of search results was established. Results showed that the method could effectively optimize the ranking results, and mine associative information with a higher degree of correlation to meet the user expectations of resource retrieval requirements. The method improved the utilization rate of literature, and had a certain reference value.

document retrieval; Skyline query; correlation degree; optimization

2016-01-13

國家自然科學基金項目(31172144)

王春梅(1974-)，女 ，吉林長春人，碩士，館員,研究方向為信息系統實踐研究。

Tel.：13194352337；E-mail: wcmwcm_1974@163.com

TP 391.3

A

1006-7167(2016)09-0126-04