王 春 梅

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

?

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

王 春 梅

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

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

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

0 引 言

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

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

1 文獻(xiàn)利用率影響因素分析

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

1.1 篩選機(jī)制對(duì)文獻(xiàn)利用率的影響

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

1.2 檢索習(xí)慣對(duì)文獻(xiàn)利用率的影響

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

2 Skyline算法研究

Skyline計(jì)算是一個(gè)典型的多目標(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ù)的查詢計(jì)算方面更具有十分重要的應(yīng)用前景[7-8]。Skyline查詢的主要目標(biāo)是從一個(gè)潛在的、海量的數(shù)據(jù)中找出用戶感興趣的、相對(duì)重要的點(diǎn)，過濾掉一些不需要的點(diǎn)，從而為進(jìn)一步的數(shù)據(jù)處理工作打下基礎(chǔ)，減少不必要的資源浪費(fèi)。

2.1 算法分析

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

SELECT...FROM...WHERE

GROUP BY...HAVING...

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

2.2 算法實(shí)例

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

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

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

2.3 Skyline文獻(xiàn)檢索排序模型

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

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

圖1 SP點(diǎn)集合示意圖

圖2 Skyline查詢模型

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

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

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

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

4 測(cè)試論證

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

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

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

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

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

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

5 結(jié) 論

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

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

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

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

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

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

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

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

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

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

國(guó)家自然科學(xué)基金項(xiàng)目(31172144)

王春梅(1974-)，女 ，吉林長(zhǎng)春人，碩士，館員,研究方向?yàn)樾畔⑾到y(tǒng)實(shí)踐研究。

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

TP 391.3

A

1006-7167(2016)09-0126-04