一種基于關(guān)聯(lián)度的Skyline多目標(biāo)優(yōu)化文獻檢索方法設(shè)計與測試

王 春 梅

(吉林農(nóng)業(yè)大學(xué), 吉林 長春 130000)

?

一種基于關(guān)聯(lián)度的Skyline多目標(biāo)優(yōu)化文獻檢索方法設(shè)計與測試

王 春 梅

(吉林農(nóng)業(yè)大學(xué), 吉林 長春 130000)

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

文獻檢索; Skyline查詢; 關(guān)聯(lián)度; 優(yōu)化

0 引 言

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

在現(xiàn)有成果的基礎(chǔ)上，本文將文獻檢索后的排序策略作為主要的研究內(nèi)容，設(shè)計了一種基于關(guān)聯(lián)度的Skyline多目標(biāo)優(yōu)化文獻檢索方法，將文獻之間的關(guān)聯(lián)度作為排序的重要衡量標(biāo)準(zhǔn)，從而使用戶得到一個更加滿意的查詢結(jié)果，目的是為了加快查詢速度，提高文獻的利用效率。

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

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

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

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

1.2 檢索習(xí)慣對文獻利用率的影響

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

2 Skyline算法研究

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

2.1 算法分析

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

SELECT...FROM...WHERE

GROUP BY...HAVING...

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

2.2 算法實例

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

表1 賓館價格與距海邊距離關(guān)系

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

2.3 Skyline文獻檢索排序模型

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

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

圖1 SP點集合示意圖

圖2 Skyline查詢模型

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

3 基于關(guān)聯(lián)度的Skyline多目標(biāo)優(yōu)化文獻檢索模型設(shè)計

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

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

4 測試論證

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

圖3 基于關(guān)聯(lián)度的多目標(biāo)優(yōu)化文獻檢索排序模型

表2 部分檢索結(jié)果列表

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

表3 Skyline關(guān)聯(lián)度排序結(jié)果

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

5 結(jié) 論

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

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

[2] 孫圣力，戴東波，黃震華，等. 概率數(shù)據(jù)流上skyline查詢處理算法 [J].電子學(xué)報, 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] 周綺鳳,楊小青，洪文財，等.內(nèi)嵌空間排序支持向量機及其在文本檢索中的應(yīng)用[J].信息與控制，2010,39(5):629-634.

[6] 孫笑明，崔文田.一種網(wǎng)絡(luò)展現(xiàn)文獻檢索結(jié)果的理論模型[J].情報學(xué)報,2011，30(2).

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

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

[9] 瞿 亮,楊 貫.基于本體的專業(yè)文獻檢索[J].計算技術(shù)與自動化，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查詢處理在文獻檢索排序中的應(yīng)用[J]. 情報理論與實踐,2011(10):104-108.

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

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

[14] 楊林青，李 湛，牟雁超，等. 面向大規(guī)模數(shù)據(jù)集的并行化Top-k Skyline查詢算法[J]. 計算機科學(xué)與探索，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

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

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

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

TP 391.3

A

1006-7167(2016)09-0126-04