李 慧

(南京郵電大學(xué)圖書館，江蘇 南京210046)

搜索引擎最重要的任務(wù)是搜集網(wǎng)絡(luò)信息，提供給用戶與其檢索詞最匹配的結(jié)果，并返回相關(guān)鏈接。搜索引擎在網(wǎng)絡(luò)上抓取足夠的網(wǎng)頁(yè)已不再是困難，困難在于如何將這些網(wǎng)頁(yè)整理出來(lái)，選擇合適的排序算法，把這些結(jié)果集返回給用戶。語(yǔ)義網(wǎng)技術(shù)的出現(xiàn)，更加加劇了這種困境。語(yǔ)義網(wǎng)的宏觀結(jié)構(gòu)來(lái)源于RDF 模型所定義的數(shù)據(jù)之間的鏈接，隨著RDF 數(shù)據(jù)大量涌入，傳統(tǒng)搜索引擎更加凸顯出局限性，因此語(yǔ)義搜索引擎應(yīng)運(yùn)而生。由于語(yǔ)義檢索的對(duì)象不再僅限于文檔和網(wǎng)頁(yè)，同時(shí)也包括了實(shí)體和關(guān)系等，所以在一定程度上對(duì)排序算法的要求變得更高。對(duì)于語(yǔ)義搜索引擎來(lái)說(shuō)，一個(gè)合理的排序算法不僅可以幫助用戶提高搜索效率，更是邁向可信語(yǔ)義網(wǎng)的至關(guān)重要的一步。從對(duì)現(xiàn)有研究與調(diào)研的基礎(chǔ)上可以看出，目前針對(duì)本體文檔的排序研究較多，已經(jīng)形成了較為系統(tǒng)的分類排序算法體系，但針對(duì)實(shí)體和關(guān)系的排序的研究還在發(fā)展中。本文按照排序的階段將語(yǔ)義檢索排序分為實(shí)體排序、關(guān)系排序和文檔排序，并詳細(xì)闡述了每種排序算法的研究進(jìn)展，供今后研究人員參考。

1 傳統(tǒng)排序算法概述

傳統(tǒng)搜索引擎的排序算法主要可以分為兩類，分別是基于鏈接分析的方法和基于用戶行為分析的方法，以及在此基礎(chǔ)上進(jìn)行改進(jìn)的排序模型。其中基于鏈接分析的方法又可以分為PageRank［1］算法、HITS 算法［2］、SALSA［3］算法等;基于用戶行為分析的方法可以分為BrownseRank［4］和Direct Hit［5］算法等;一些在此基礎(chǔ)上改進(jìn)的排序算法包括基于節(jié)點(diǎn)和邊屬性的排序算法［6-8］、基于監(jiān)督學(xué)習(xí)的排序算法［9-10］等。隨著語(yǔ)義網(wǎng)的發(fā)展，本體數(shù)量與日俱增，本體模型在語(yǔ)義網(wǎng)上被廣泛地應(yīng)用，傳統(tǒng)的基于關(guān)鍵詞的檢索方法不能對(duì)本體中的語(yǔ)義關(guān)系進(jìn)行很好的推理，而僅僅基于表述邏輯(description logics)對(duì)本體進(jìn)行檢索，因而用戶滿意度并不高，也無(wú)法取得很好的排序結(jié)果。與此同時(shí)，一些研究將傳統(tǒng)的排序算法應(yīng)用于語(yǔ)義檢索中，取得了一定的成果，但是由于本體結(jié)構(gòu)的特殊性，目前相關(guān)研究仍在探索更加優(yōu)化的排序算法，下文將詳細(xì)介紹當(dāng)前的研究現(xiàn)狀和進(jìn)展。

2 語(yǔ)義檢索排序方法

當(dāng)前按照排序的階段可以將語(yǔ)義檢索排序分為實(shí)體排序、關(guān)系排序和本體文檔排序，但是這些排序方法之間是有很大交集的，并無(wú)嚴(yán)格的界限。

2.1 實(shí)體排序

語(yǔ)義網(wǎng)中的定義/概念是為了描述現(xiàn)實(shí)中的實(shí)體數(shù)據(jù)，這些實(shí)體數(shù)據(jù)都將服務(wù)于資源的請(qǐng)求者，比如利用FOAF撰寫的個(gè)人檔案就是目前最常用的實(shí)體數(shù)據(jù)。語(yǔ)義網(wǎng)最初發(fā)展時(shí)，由于實(shí)體數(shù)據(jù)相對(duì)匱乏，因而并未引起足夠的重視，近年來(lái)隨著語(yǔ)義網(wǎng)的迅猛發(fā)展，大量類似于FOAF、RSS 等實(shí)體數(shù)據(jù)的出現(xiàn)，加上實(shí)體排序本身就有著巨大的研究?jī)r(jià)值和商業(yè)價(jià)值，使得這個(gè)問題越來(lái)越受到研究者的關(guān)注，而且從實(shí)際的角度來(lái)講，對(duì)于大多數(shù)一般用戶而言，實(shí)體數(shù)據(jù)的檢索需求更為普遍。實(shí)體排序問題的實(shí)質(zhì)是對(duì)實(shí)體之間異質(zhì)關(guān)聯(lián)的分析方法，其排序的目的是從知識(shí)庫(kù)中發(fā)現(xiàn)和檢索與用戶需求最匹配的實(shí)體對(duì)象，這種最匹配的實(shí)體對(duì)象一般稱為種子實(shí)體(seed entity)，排序的困難之處在于實(shí)體之間的關(guān)聯(lián)異常的復(fù)雜，一些隱式關(guān)聯(lián)很難被發(fā)現(xiàn)，推理過(guò)程不僅牽扯到描述邏輯(Description Logic)的推理規(guī)則，還需要使用語(yǔ)義網(wǎng)規(guī)則描述語(yǔ)言(SWRL)定義的規(guī)則，因此在對(duì)實(shí)體數(shù)據(jù)進(jìn)行排序的過(guò)程中，如果想得到全面準(zhǔn)確的排序結(jié)果，那么推理所起到的作用是不可忽略的。

W.Wei 等人［11］提出了針對(duì)特定領(lǐng)域的實(shí)體排序算法RareRank，其指出傳統(tǒng)的信息檢索模型主要依靠?jī)?nèi)容和鏈接分析評(píng)分來(lái)確定排序結(jié)果，即相關(guān)性分?jǐn)?shù)(relevance)和質(zhì)量分?jǐn)?shù)(quality)。作者將這兩種評(píng)分相結(jié)合，并在此基礎(chǔ)上分配相應(yīng)的參數(shù)來(lái)進(jìn)行優(yōu)化，并引入了合理搜索模型(Rational Research Model)。其首先將一個(gè)領(lǐng)域的知識(shí)利用有向圖來(lái)表示，然后將領(lǐng)域本體引入到有向圖中，因此該模型的排序分?jǐn)?shù)整合了領(lǐng)域本體的相關(guān)性分?jǐn)?shù)和鏈接分析的質(zhì)量分?jǐn)?shù)。這個(gè)方法實(shí)質(zhì)是應(yīng)用了鏈接分析來(lái)對(duì)實(shí)體進(jìn)行排序，實(shí)證結(jié)果證明效果確實(shí)有一定改善，但是該模型的參數(shù)設(shè)置較為簡(jiǎn)單，將來(lái)還需要大量的數(shù)據(jù)集進(jìn)行測(cè)試。L.Dali 等人［12］提出了Learning to Rank 算法，其主要是采用查詢?cè)~本身進(jìn)行實(shí)體的優(yōu)化排序，首先利用PageRank作為參考模型，并將其應(yīng)用到RDF 圖中，并結(jié)合這些詞的變化特點(diǎn)，進(jìn)而獲得更高的資源關(guān)聯(lián)，最后計(jì)算出更好的排序結(jié)果。這種方法的本質(zhì)是利用查詢?cè)~自身特點(diǎn)的RDF圖。相比一般的文本排序，該方法會(huì)產(chǎn)生較大的非連續(xù)性，尤其是在關(guān)聯(lián)數(shù)據(jù)集(LOD)參與的情況下，很難具有較好的效果;X.Ning 等［13］提出了語(yǔ)義搜索排序框架RSS，這種算法一方面利用關(guān)系(relations)的異質(zhì)性來(lái)確定實(shí)體的重要性，同時(shí)利用一種擴(kuò)展激活算法(Extended spread activation)來(lái)檢索與查詢?cè)~最相關(guān)的實(shí)體，因此可以邊搜索邊推理，并提供合適的實(shí)體排序結(jié)果。實(shí)驗(yàn)結(jié)果也顯示出這種算法的效果。作者最后也指出，這種算法也具有一些不足，比如目前在模式圖中分配邊權(quán)重時(shí)無(wú)法采用機(jī)器自動(dòng)分配以及跨平臺(tái)可移植性效果不佳等;A.Harth 等［14］提出了語(yǔ)義搜索引擎SWSE，其是一種專門用來(lái)搜索實(shí)體及其相關(guān)知識(shí)的搜索引擎。SWSE 的排序算法叫做ReCon-Rank，該算法由3 個(gè)階段的實(shí)體計(jì)算構(gòu)成:①ResourceRank;②ContextRank;③ReConRank。這3 個(gè)階段的計(jì)算過(guò)程都是在RDF 資源圖中利用改進(jìn)的PageRank 算法來(lái)進(jìn)行的。具體來(lái)說(shuō)，首先從web 上抓取RDF 數(shù)據(jù)，之后傳遞到有向圖中，并利用ResourceRank 算法計(jì)算排序分?jǐn)?shù);然后使用RDF 數(shù)據(jù)源流信息的上下文情景語(yǔ)義圖進(jìn)一步計(jì)算ContextRank 分?jǐn)?shù);最終，利用預(yù)定義規(guī)則衍生出的整合后的資源語(yǔ)義圖進(jìn)一步生成ReConRank 分?jǐn)?shù)，這種排序算法考慮了實(shí)體及其上下文的重要性，并具有一定的可擴(kuò)展性;H.Hwang 等［15］提出了專門針對(duì)關(guān)系數(shù)據(jù)庫(kù)中的排序算法ObjectRank，其主要是基于PageRank 啟發(fā)原則來(lái)排序?qū)嶓w對(duì)象，并提出了一系列指標(biāo)和參數(shù)來(lái)改善結(jié)果的相關(guān)性。其中最重要的兩個(gè)參數(shù)是特定指標(biāo)(specificity metric)和質(zhì)量指標(biāo)(quality metric)。特定指標(biāo)是專門用來(lái)衡量與檢索詞最相關(guān)的實(shí)體對(duì)象;質(zhì)量指標(biāo)(quality metric)是用來(lái)衡量返回的實(shí)體本身的重要性的。此外還提出了兩個(gè)參數(shù)，分別是“結(jié)果集中的相關(guān)實(shí)體的數(shù)量”和“查詢?cè)~的權(quán)重”。作者也探索了將領(lǐng)域本體整合到ObjectRank 算法中，來(lái)優(yōu)化查詢結(jié)果;C.Rocha 等［16］提出了一種混合排序算法，在傳統(tǒng)關(guān)鍵詞檢索的基礎(chǔ)上，結(jié)合擴(kuò)展激活算法，通過(guò)圖遍歷進(jìn)一步擴(kuò)展檢索與初始結(jié)果相關(guān)的更多實(shí)體，這是一種依賴特定領(lǐng)域來(lái)達(dá)到相關(guān)結(jié)果排序的方法。此外，該方法是通過(guò)上下文情景來(lái)描述實(shí)體之間關(guān)系的重要性的，并分配相應(yīng)的權(quán)重。顯而易見，這種實(shí)體排序算法對(duì)跨領(lǐng)域的排序并不能起到良好的效果;N.Stojanovic［17］等提出一種利用本體中語(yǔ)義的排序算法。該方法結(jié)合推理過(guò)程的特點(diǎn)和資源內(nèi)容本身，相結(jié)合來(lái)確定搜索結(jié)果的相關(guān)性和排序。其把實(shí)體間的語(yǔ)義關(guān)系分配兩個(gè)權(quán)重，分別是“普遍性”和“用戶自定義”，不僅考慮了上下文的情景，也考慮了其他的一些參數(shù)，諸如路徑長(zhǎng)度和關(guān)系的特定性等。也就是說(shuō)，實(shí)體的關(guān)系特定性越高，該實(shí)體出現(xiàn)在其他關(guān)系中的可能性就越低。作者利用這種方法在樣本數(shù)據(jù)集中進(jìn)行測(cè)試，結(jié)果顯示用戶的滿意度有所提高;R.McCreadie［18］等利用一種擴(kuò)展的投票模型來(lái)進(jìn)行實(shí)體的排序，通過(guò)考慮查詢?cè)~和實(shí)體在上下文的共現(xiàn)程度作為投票的標(biāo)準(zhǔn)，為投票模型建立一種語(yǔ)義關(guān)系支持。另外在投票模型之上，開發(fā)了一種基于圖的技術(shù)來(lái)更進(jìn)一步的增強(qiáng)初始投票評(píng)估效果。為了獲取實(shí)體，他們利用了DBPedia建立了一個(gè)詞典庫(kù)，通過(guò)基于詞典的方式來(lái)識(shí)別實(shí)體。他們的實(shí)驗(yàn)表明擴(kuò)展的投票模型可以有效的處理實(shí)體排序問題;Z.wang［19］提出了一個(gè)實(shí)體排序方法，該方法先以文檔中心模型(DCM)為基礎(chǔ)，然后計(jì)算查詢術(shù)語(yǔ)與候選實(shí)體的距離得分。查詢術(shù)語(yǔ)和候選實(shí)體的距離是指，在候選實(shí)體的所有相關(guān)文檔中查詢?cè)~和候選實(shí)體名稱之間的最短距離。最后把文檔中心模型得分和距離得分做線性累加。

2.2 關(guān)系排序

目前語(yǔ)義搜索引擎的研究重點(diǎn)集中在如何更好地發(fā)現(xiàn)語(yǔ)義實(shí)體上，事實(shí)上語(yǔ)義網(wǎng)強(qiáng)調(diào)的是實(shí)體之間的關(guān)聯(lián)關(guān)系，實(shí)體之間是通過(guò)關(guān)聯(lián)關(guān)系結(jié)合在一起，孤立的實(shí)體本身并不包含任何語(yǔ)義信息。所以說(shuō)，實(shí)體之間的關(guān)聯(lián)關(guān)系相比實(shí)體本身更加具有研究?jī)r(jià)值，比如可以挖掘出隱藏在實(shí)體之間有價(jià)值的某種事實(shí)等。隨著語(yǔ)義網(wǎng)資源的大量增長(zhǎng)，實(shí)體之間的關(guān)聯(lián)關(guān)系的個(gè)數(shù)必然會(huì)超過(guò)實(shí)體本身，因此，在這種多領(lǐng)域融合的語(yǔ)義搜索中，對(duì)關(guān)聯(lián)關(guān)系搜索結(jié)果進(jìn)行排序，將用戶最為感興趣的關(guān)聯(lián)關(guān)系優(yōu)先返回給用戶，是當(dāng)前急需解決的難點(diǎn)之一。

關(guān)聯(lián)關(guān)系排序的困難之處在于，實(shí)體之間的鏈接異常復(fù)雜，某些隱式關(guān)聯(lián)很難被發(fā)現(xiàn)，而且實(shí)體之間的關(guān)聯(lián)反映在圖模型中往往體現(xiàn)為一條路徑，所以傳統(tǒng)排序中鏈接分析無(wú)法適用。關(guān)聯(lián)關(guān)系排序的實(shí)質(zhì)就是對(duì)實(shí)體圖中連接兩個(gè)實(shí)體之間的路徑進(jìn)行排序。與實(shí)體排序和本體文檔排序不同，語(yǔ)義關(guān)聯(lián)關(guān)系排序是近幾年才逐漸被人們關(guān)注的，相關(guān)研究還在快速發(fā)展中。

K.Anyanwu 等［20］提出了SemRank 算法，這是一種語(yǔ)義關(guān)聯(lián)關(guān)系搜索排序方法，這種方法利用“改進(jìn)排序模型”(Modulative Ranking Model)來(lái)識(shí)別與用戶查詢?cè)~相關(guān)的上下文情景，然后推斷用戶興趣，綜合了各種語(yǔ)義信息和啟發(fā)式信息。用戶還可以改變檢索的模式來(lái)得到涵蓋某種特定情景的搜索排序結(jié)果;Y.Li 等［21］提出了以關(guān)聯(lián)關(guān)系為基礎(chǔ)的搜索引擎OntoLook，其首先進(jìn)行網(wǎng)頁(yè)的語(yǔ)義標(biāo)注，利用概念和關(guān)系分別作為點(diǎn)和邊進(jìn)行建模，然后在圖中刪除一系列不相關(guān)的概念。利用這種方法，可以生成候選關(guān)系詞集(CRKS)，進(jìn)而返回給標(biāo)注數(shù)據(jù)庫(kù)，最大限度上減少了無(wú)關(guān)網(wǎng)頁(yè)的數(shù)量，優(yōu)化了排序結(jié)果。這種方法主要靠個(gè)人經(jīng)驗(yàn)和知識(shí)來(lái)識(shí)別概念關(guān)系，排除不相關(guān)概念，重構(gòu)用戶檢索需求;B.Aleman［22］等在利用復(fù)雜關(guān)系語(yǔ)義進(jìn)行關(guān)系排序中進(jìn)行了有益的嘗試，并提出了一個(gè)以用戶為中心的排序標(biāo)準(zhǔn)。作者提出了一些語(yǔ)義標(biāo)準(zhǔn)，比如“信任”、“包含”、“稀有度”、“關(guān)聯(lián)長(zhǎng)度”等，并利用這些標(biāo)準(zhǔn)對(duì)兩個(gè)實(shí)體進(jìn)行了語(yǔ)義關(guān)聯(lián)的排序。由于這種排序方法包含了較多的參數(shù)，所以在計(jì)算排序分?jǐn)?shù)權(quán)重時(shí)需要個(gè)人經(jīng)驗(yàn)或領(lǐng)域?qū)＜业膮⑴c，所以并不適用于一般的用戶;值得欣喜的是，國(guó)內(nèi)對(duì)關(guān)聯(lián)關(guān)系排序也有一定的探索研究，文坤梅［23］提出了一種關(guān)聯(lián)關(guān)系排序方法，其針對(duì)實(shí)體之間普遍存在的關(guān)聯(lián)關(guān)系，以統(tǒng)計(jì)學(xué)、鏈接分析、社會(huì)網(wǎng)絡(luò)等相關(guān)技術(shù)為基礎(chǔ)，抽取3 種影響排序的關(guān)鍵因素，分別是領(lǐng)域相關(guān)度，關(guān)聯(lián)關(guān)系長(zhǎng)度以及關(guān)聯(lián)關(guān)系頻度，并提出了這3種關(guān)鍵影響因子的計(jì)算方法，該方法綜合考慮了3 種因素的影響，能優(yōu)先返回用戶需要查詢的關(guān)聯(lián)關(guān)系。試驗(yàn)結(jié)果表明該方法能較好地將用戶感興趣的語(yǔ)義關(guān)聯(lián)關(guān)系優(yōu)先返回，并能挖掘出實(shí)體對(duì)象之間有價(jià)值的關(guān)聯(lián)關(guān)系。

2.3 語(yǔ)義/本體文檔排序

語(yǔ)義/本體文檔檢索的目的是為了找到含有特定類或?qū)傩缘谋倔w文檔。傳統(tǒng)的搜索引擎無(wú)法識(shí)別本體的語(yǔ)義標(biāo)注信息，所以在檢索結(jié)果集中無(wú)法將真正符合用戶需求的文檔檢索出來(lái)。就語(yǔ)義文檔檢索而言，結(jié)果集中應(yīng)該返回的是包含與查詢?cè)~最相關(guān)的實(shí)體及其關(guān)系的文檔。當(dāng)前用于本體文檔排序的相關(guān)方法大致可以分為:基于鏈接分析的方法、基于結(jié)構(gòu)分析的方法、基于內(nèi)容分析的方法、基于概念結(jié)構(gòu)分析的排序方法以及一些其他排序方法。目前本體文檔排序雖然形成了較為系統(tǒng)的排序方法，但是還沒有統(tǒng)一的標(biāo)準(zhǔn)，缺乏一致的衡量標(biāo)準(zhǔn)，在計(jì)算排序時(shí)要從本體鏈接關(guān)系、本體的模式和重要性、概念匹配的特征甚至是實(shí)體等角度進(jìn)行綜合考慮，同時(shí)也要結(jié)合用戶的個(gè)性化需求，才能夠獲得需求導(dǎo)向的最佳的排序效果。

2.3.1 基于鏈接分析的排序方法

L.Ding［24］等提出了語(yǔ)義搜索引擎Swoogle，其使用類似于PageRank 的鏈接分析法，作者提出了語(yǔ)義Web 中的3種基本元素:語(yǔ)義Web 文檔 (SWD)、語(yǔ)義Web 本體(SwO)以及語(yǔ)義Web 術(shù)語(yǔ)(SWT)，針對(duì)不同的元素，分別給出了不同的排序算法。其中針對(duì)語(yǔ)義Web 文檔(SWD)的排序算法叫做OntoRank［25］，在這種算法中，作者引入了3 種不同的隱式鏈接關(guān)系，分別是引用(TM/IN)、擴(kuò)展(EX)以及導(dǎo)入(IM)。引用表示一個(gè)本體文檔引用了另一個(gè)本體文檔中定義的術(shù)語(yǔ);擴(kuò)展表示一個(gè)本體擴(kuò)展了另外一個(gè)本體;導(dǎo)入表示一個(gè)本體導(dǎo)入另外一個(gè)本體，基于這些鏈接關(guān)系，OntoRank 采用隨機(jī)沖浪模型來(lái)計(jì)算本體的重要性。本體間的連接關(guān)系不同于網(wǎng)頁(yè)的鏈接，OntoRank 算法引入了更加合理的模型，為實(shí)體的關(guān)系賦予不同的權(quán)重。這種算法可以檢索出大量相關(guān)本體，但本體的主題對(duì)于排序結(jié)果的影響被忽略了，也就是說(shuō)OntoRank只能以靜態(tài)的方式評(píng)價(jià)本體的重要性，不能將用戶的查詢?cè)~作為影響排序結(jié)果的因素。類似于這種改進(jìn)的PageRank的算法還有ontokhoj［26］算法，在該算法中，本體間的鏈接關(guān)系被定義為兩個(gè)本體中概念之間的引用關(guān)系，同時(shí)這種鏈接關(guān)系被認(rèn)為是有向的而且可以傳遞，鏈接的強(qiáng)度隨著鏈接距離的增加而減弱，在確定了本體的鏈接關(guān)系后，再采用隨機(jī)沖浪模型計(jì)算每個(gè)本體的排序值即可。這種改進(jìn)的PageRank 算法將本體看成與網(wǎng)頁(yè)類似的無(wú)結(jié)構(gòu)數(shù)據(jù)，但本體具有其特殊性，從而導(dǎo)致排序結(jié)果準(zhǔn)確度不高。

使用鏈接分析或其他在此基礎(chǔ)上改進(jìn)后的算法，用來(lái)計(jì)算本體文檔排序的主要困難在于，本體與網(wǎng)頁(yè)不同，本體之間缺乏顯式的鏈接，所以采用鏈接分析的方法就必須要挖掘出本體之間的隱式關(guān)聯(lián)。這種以O(shè)ntoRank 為代表的鏈接分析方法，由于本體主題對(duì)排序結(jié)果的影響被忽略，所以不能將其作為結(jié)果排序的因素。

2.3.2 基于結(jié)構(gòu)分析的方法

H.Alani［27］等提出了AKTiveRank 算法，該方法從另一個(gè)角度考慮了用戶的查詢，尤其是多個(gè)關(guān)鍵字查詢對(duì)排序的影響。該算法利用了4 個(gè)標(biāo)準(zhǔn)對(duì)本體的重要性進(jìn)行評(píng)分，分別是類匹配標(biāo)準(zhǔn) (Class Mateh Measure)、密度標(biāo)準(zhǔn)(Density Measuxe)、語(yǔ)義相似度標(biāo)準(zhǔn)(Semantie Similarity Measue)和中間性標(biāo)準(zhǔn)(Betweenness Measure)，用戶在查詢時(shí)，本體文檔的排序分?jǐn)?shù)由這4 種標(biāo)準(zhǔn)加權(quán)來(lái)計(jì)算。實(shí)證結(jié)果顯示，在考慮查詢的情境下，AKTiveRank 算法排序結(jié)果比單一的OntoRank 更加貼近實(shí)際標(biāo)準(zhǔn)。此外，一些研究［28-31］側(cè)重將Swoogle 鏈接分析方法和AKTiveRank 方法結(jié)合起來(lái)探索本體排序結(jié)果，比較有代表性的比如張志強(qiáng)［32］等的研究，其將AKTiveRank 中的類匹配度量、語(yǔ)義相似性度量以及密度度量等保留，并結(jié)合匹配類的子類及其屬性，設(shè)置相應(yīng)的權(quán)重，迭代計(jì)算類的重要性，最后在Swoogle鏈接分析的基礎(chǔ)上計(jì)算本體的重要性的分?jǐn)?shù)。相比基于鏈接分析方法，基于結(jié)構(gòu)分析的方法考慮到了本體自身的結(jié)構(gòu)特性，同時(shí)也考慮到了用戶查詢?cè)~對(duì)結(jié)果集的影響，但是這種方法的時(shí)間成本較大。

S.Tartir［33-34］等提出了OntoQA 算法，首次把實(shí)體數(shù)據(jù)的考察引入到本體評(píng)價(jià)中。該算法的創(chuàng)新之處在于不僅考慮本體模式的評(píng)分，同時(shí)也考慮了本體知識(shí)庫(kù)的評(píng)分。該算法是對(duì)搜索到的本體文檔根據(jù)其結(jié)構(gòu)特征，再與用戶查詢?cè)~相對(duì)比，進(jìn)行多方面的度量，對(duì)各個(gè)度量值進(jìn)行加權(quán)計(jì)算，從而得到本體的最終排序值。這種算法對(duì)本體文檔重要性的評(píng)分可以分為兩個(gè)方面，分別是本體模式和本體實(shí)體。嚴(yán)格說(shuō)來(lái)，這是一種基于模式和實(shí)體分析的排序方法。

2.3.3 基于內(nèi)容分析的排序方法

M.Jones［35］等提出了一種基于內(nèi)容分析的本體排序算法，這種算法不僅考慮了類標(biāo)簽，同時(shí)考慮了本體圖以外的評(píng)論等內(nèi)容。其認(rèn)為在結(jié)果集中本體的重要性不僅與查詢?cè)~有關(guān)，與其相關(guān)概念的匹配程度也有關(guān)，匹配越多的查詢?cè)~，本體就越重要，排序時(shí)就應(yīng)該排在前面。在實(shí)驗(yàn)中，作者利用wordnet 獲得查詢?cè)~的上位詞、下位詞以及同義詞，再根據(jù)結(jié)果集中與本體中類的匹配程度來(lái)計(jì)算本體的類匹配值和文本匹配值，通過(guò)兩者加權(quán)進(jìn)行本體文檔的排序。

2.3.4 基于概念結(jié)構(gòu)分析的排序方法

A.Harith［36］在研究中考慮了匹配概念在本體結(jié)構(gòu)中的重要程度，充分注重了本體中匹配概念間的結(jié)構(gòu)和關(guān)系，通過(guò)查詢匹配，找到用戶所關(guān)注的概念在本體中的位置，然后分析其結(jié)構(gòu)的特征。這種算法考察了4 種衡量因素:分別是類匹配度量(CMM)，中心性度量(BEM)，密度度量(DEM)，語(yǔ)義相似性度量(SSM)，通過(guò)對(duì)上述4 種因素的加權(quán)平均得到每個(gè)本體文檔的分?jǐn)?shù)，然后進(jìn)行排序。

2.3.5 其他排序方法

OntoFetcher［37］從概念覆蓋CCW、關(guān)系覆蓋PRW、相關(guān)性度量RM、連通性度量CM、關(guān)系的豐富度RR 與Swoogle 鏈接分析計(jì)算出的本體的秩幾個(gè)方面進(jìn)行了本體重要度的考量，從而進(jìn)行排序設(shè)計(jì)，可以說(shuō)是一種基于內(nèi)容和鏈接分析相整合的排序方法;V.Sankar［38］等人提出了一種基于OWL 的本體文檔排序方法，OWL 中含有描述類、類公理、屬性定義與約束等內(nèi)部關(guān)系，可以通過(guò)對(duì)OWL 中類匹配進(jìn)行計(jì)算排序;徐德智［39］等針對(duì)傳統(tǒng)本體排序結(jié)果不準(zhǔn)確的情況下，提出一種新的內(nèi)容分析方法，首先通過(guò)構(gòu)造本體的概念模型提取本體的主題詞集合得到本體的主題相似度;然后通過(guò)對(duì)關(guān)鍵詞所在的本體上下文進(jìn)行分析，得到本體相對(duì)于關(guān)鍵詞的上下文相關(guān)度;最后對(duì)二者進(jìn)行加權(quán)平均得到本體文檔的排序分?jǐn)?shù)。實(shí)驗(yàn)結(jié)果表明，該方法可以有效地提高本體排序的準(zhǔn)確性;寇燕歌等［40-41］使用TF-IDF 方法計(jì)算查詢?cè)~與本體文檔中術(shù)語(yǔ)的權(quán)重，通過(guò)計(jì)算夾角弦值的方法衡量二者的相似度，據(jù)此進(jìn)行本體的排序;楊克特［42］等使用TF-IDF 方法計(jì)算匹配類的重要程度，再結(jié)合本體鏈接分析方法，提出一種面向特定領(lǐng)域的語(yǔ)義文檔排序算法;T.Ahmed［43］在分析本體鏈接的基礎(chǔ)上，提出了基于HITS 的本體排序方法;H.Lewen［44］探索了用戶對(duì)本體評(píng)論或用戶信任度等的本體反饋信息對(duì)排序的影響;還有一些研究［45］主要從方法的角度對(duì)本體排序因素進(jìn)行了探討，但是沒有闡述具體的量化計(jì)算方法。

以上是典型的語(yǔ)義/本體文檔排序算法，近年來(lái)一些研究開始逐步關(guān)注針對(duì)本體中某一片段甚至是個(gè)別詞匯的排序。在這種元素級(jí)或粒度層級(jí)上的排序目前還在快速發(fā)展中，代表性的算法有TermRank、CARRank 和TripleRank等。

TermRank［46］是swoogle 中用于術(shù)語(yǔ)排序的一種算法，該算法使用術(shù)語(yǔ)的流行度作為排序的標(biāo)準(zhǔn)，術(shù)語(yǔ)流行度由該術(shù)語(yǔ)被使用的次數(shù)、推廣的量、所在語(yǔ)義文檔上下文重要性等共同來(lái)確定;CARRank［47］是一種利用相互增強(qiáng)關(guān)系迭代計(jì)算本體中概念與關(guān)系的重要性的方法。這種算法根據(jù)本體構(gòu)建模型的特點(diǎn)進(jìn)行分析，從而得到本體模型的4個(gè)特征，最后根據(jù)這些基本特征利用本體中元素的中心值來(lái)表示本體中片段的重要性;TripleRank［48］是一種利用張量分解對(duì)語(yǔ)義網(wǎng)數(shù)據(jù)進(jìn)行排序的方法。該算法中使用統(tǒng)計(jì)學(xué)方法獲得外部語(yǔ)義來(lái)增強(qiáng)可用數(shù)據(jù)，并使用張力模型來(lái)模擬RDF 圖。最后使用平行因子法分析此模型，將該模型看成是可以使用HITS 算法進(jìn)行排序的模型。

3 總結(jié)與展望

語(yǔ)義檢索相比傳統(tǒng)檢索的優(yōu)勢(shì)在于可以實(shí)現(xiàn)基于語(yǔ)義的匹配和推理，是一種知識(shí)檢索，可以返回與查詢?cè)~更相關(guān)的內(nèi)容。本體在語(yǔ)義檢索中處于非常重要的位置，承擔(dān)著知識(shí)表達(dá)的核心任務(wù)，對(duì)語(yǔ)義檢索的推理也起著支撐性的作用。由于語(yǔ)義Web 對(duì)傳統(tǒng)互聯(lián)網(wǎng)進(jìn)行了革命性的變化，使其檢索和排序的對(duì)象不僅僅局限于文檔和網(wǎng)頁(yè)，更包括了實(shí)體和關(guān)系等，雖然可以通過(guò)模型變換和算法改進(jìn)來(lái)優(yōu)化傳統(tǒng)的排序算法，也帶來(lái)了一定的效果改善，但是由于語(yǔ)義Web 的特殊結(jié)構(gòu)，傳統(tǒng)排序算法的思路并不能完全移植到語(yǔ)義Web 中。本文在調(diào)研的基礎(chǔ)上，詳細(xì)闡述了當(dāng)前實(shí)體排序、關(guān)系排序和本體文檔排序的研究進(jìn)展，可以預(yù)見的是，在將來(lái)的語(yǔ)義排序算法發(fā)展中，語(yǔ)義網(wǎng)中信任和信譽(yù)度的研究將越來(lái)越受到重視，將用戶的社會(huì)網(wǎng)絡(luò)因素同已有的排序算法相結(jié)合，必將是未來(lái)重要的研究方向之一。

［1］ Page L，Brin S，Motwani R，et al. The PageRank citation ranking:Bringing order to the web ［J］. 1999.

［2］ 張書江. 基于超鏈接分析搜索引擎頁(yè)面排序算法的剖析［J］.安徽理工大學(xué)學(xué)報(bào):自然科學(xué)版，2008，28 (2):73 -77.

［3］ Lempel R，Moran S. SALSA:the stochastic approach for link -structure analysis ［J］. ACM Transactions on Information Systems(TOIS)，2001，19 (2):131 -160.

［4］ Liu Y，Gao B，Liu T Y，et al. BrowseRank:letting web users vote for page importance ［C］ ∥Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval. ACM，2008:451 -458.

［5］ 徐金雷，楊曉江. 專業(yè)搜索引擎的排序算法研究［J］. 現(xiàn)代圖書情報(bào)技術(shù)，2006，(7):20 -24.

［6］ Han Y，Zhou B，Pei J，et al. Understanding Importance of Collaborations in Co-authorship Networks:A Supportiveness Analysis Approach ［C］ ∥SDM，2009:1112 -1123.

［7］ Haveliwala T，Kamvar S，Jeh G. An analytical comparison of approaches to personalizing PageRank ［J］. 2003.

［8］ Haveliwala T H. Topic - sensitive pagerank ［C］ ∥Proceedings of the 11th international conference on World Wide Web. ACM，2002:517 -526.

［9］ Tsoi A C，Morini G，Scarselli F，et al. Adaptive ranking of web pages ［C］ ∥Proceedings of the 12th international conference on World Wide Web. ACM，2003:356 -365.

［10］ Agarwal A，Chakrabarti S，Aggarwal S. Learning to rank networked entities ［C］ ∥Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM，2006:14 -23.

［11］ Wei W，Barnaghi P，Bargiela A. Rational research model for ranking semantic entities ［J］. Information Sciences，2011，181(13):2823 -2840.

［12］ Dali L，F(xiàn)ortuna B. Learning to Rank for Semantic Search ［C］∥Proc. of fourth international Semantic Search workshop located at the 20th international World Wide Web Conference WWW2011，2011.

［13］ Ning X，Jin H，Wu H. RSS:A framework enabling ranked search on the semantic web ［J］. Information Processing ＆ Management，2008，44 (2):893 -909.

［14］ Harth A，Hogan A，Delbru R，et al. Swse:Answers before links!［J］. 2007，(3):18 -23.

［15］ Hwang H，Hristidis V，Papakonstantinou Y. Objectrank:a system for authority -based search on databases ［C］ ∥Proceedings of the 2006 ACM SIGMOD international conference on Management of data. ACM，2006:796 -798.

［16］ Rocha C，Schwabe D，Aragao M P. A hybrid approach for searching in the semantic web ［C］ ∥Proceedings of the 13th international conference on World Wide Web. ACM，2004:374 -383.

［17］ Stojanovic N，Studer R，Stojanovic L. An approach for the ranking of query results in the semantic web ［M］ ∥The Semantic Web-ISWC 2003. Springer Berlin Heidelberg，2003:500 -516.

［18］ McCreadie R，Macdonald C，Ounis I，et al. University of glasgow at trec 2009:Experiments with terrier ［R］. GLASGOW UNIV (UNITED KINGDOM)，2009.

［19］ Z. Wang，W. Lv，H. Li，et al. PRIS at TREC 2011 Entity Track:Related Entity Finding and Entity List Completion. Proceedings of the 20th Text REtrieval Conference (TREC2011)，Gaithersburg，MD:NIST Special Publication，2011.

［20］ Anyanwu K，Maduko A，Sheth A. SemRank:ranking complex relationship search results on the semantic web ［C］ ∥Proceedings of the 14th international conference on World Wide Web. ACM，2005:117 -127.

［21］ Li Y，Wang Y，Huang X. A relation - based search engine in semantic web ［J］. Knowledge and Data Engineering，IEEE Transactions on，2007，19 (2):273 -282.

［22］ Aleman - Meza B，Arpinar I B，Nural M V，et al. Ranking documents semantically using ontological relationships ［C］ ∥Semantic Computing (ICSC)，2010 IEEE Fourth International Conference on. IEEE，2010:299 -304.

［23］ 文坤梅. 基于本體知識(shí)庫(kù)推理的語(yǔ)義搜索研究［D］. 武漢:華中科技大學(xué)，2007.

［24］ Ding L，F(xiàn)inin T，Joshi A，et al. Swoogle:a search and metadata engine for the semantic web ［C］ ∥Proceedings of the thirteenth ACM international conference on Information and knowledge management. ACM，2004:652 -659.

［25］ Ding L，Pan R，F(xiàn)inin T，et al. Finding and ranking knowledge on the semantic web ［M］ ∥The Semantic Web - ISWC 2005.Springer Berlin Heidelberg，2005:156 -170.

［26］ Patel C，Supekar K，Lee Y，et al. OntoKhoj:a semantic web portal for ontology searching，ranking and classification ［C］ ∥Proceedings of the 5th ACM international workshop on Web information and data management. ACM，2003:58 -61.

［27］ Alani H，Brewster C，Shadbolt N. Ranking ontologies with AKTiveRank ［M］ ∥The Semantic Web - ISWC 2006. Springer Berlin Heidelberg，2006:1 -15.

［28］ Yu W，Chen J. Ranking ontology based on structure analysis［C］ ∥Knowledge Acquisition and Modeling，2009. KAM'09.Second International Symposium on. IEEE，2009， (2):119 -122.

［29］ Yu W，Chen J. Ontology ranking for the semantic web ［C］ ∥Proceedings of the 3rd international conference on Intelligent information technology application. IEEE Press，2009:573 -574.

［30］ Rajapaksha S K，Kodagoda N. Internal structure and semantic web link structure based ontology ranking ［C］ ∥Information and Automation for Sustainability，2008. ICIAFS 2008. 4th International Conference on. IEEE，2008:86 -90.

［31］ Ding Z，Duan Z. Improved ontology ranking algorithm based on semantic web ［C］ ∥2010 3rd IEEE International Conference on Ubi-Media Computing，2010:103 -107.

［32］ Zhiqiang Z，Weitao S，Xiaoqin X. An efficient ontology ranking algorithm- MIDSRank ［J］. Journal of Computer Research and Development，2011，48 (6):1077 -1088.

［33］ Tartir S，Budak Arpinar I. Ontology evaluation and ranking using OntoQA ［C］ ∥Semantic Computing，2007. ICSC 2007. International Conference on. IEEE，2007:185 -192.

［34］ Tartir S，Arpinar I B，Moore M，et al. OntoQA:Metric -based ontology quality analysis ［C］ ∥IEEE Workshop on Knowledge Acquisition from Distributed，Autonomous，Semantically Heterogeneous Data and Knowledge Sources，2005，(9).

［35］ Jones M，Alani H. Content - based ontology ranking ［J］.2006，(4):34 -36.

［36］ Alani H，Brewster C. Metrics for ranking ontologies ［J］.2006.

［37］ SHAH S A H，KHALID A，QADIR M A. OntoFecher:An approach for query generation to gather ontologies and ranking them by ensuring user's context ［C］ ∥Proeeedings of the 4th International Conference on Emerging Technologies. Islamabad: ［s. n. ］，2008:247 -252.

［38］ RaviSankar V，Damodaram A. Ranking ontologies based on OWLlanguage ［J］. Constructs Information Technology Journal，2010，9 (3):553 -560.

［39］ 徐德智，劉怡靜. 一種用于本體排序的內(nèi)容分析方法［J］.計(jì)算機(jī)應(yīng)用研究，2010，(6):2127 -2129.

［40］ Kou Y，Zhang W. Ranking algorithm based on ontology in semantic Web ［J］. Computer Engineering，2008，34 (9):22 -24.

［41］ Yu W，Cao J，Chen J. A novel approach for ranking ontologies on the semantic web ［C］ ∥Pervasive Computing and Applications，2006 1st International Symposium on. IEEE，2006:608-612.

［42］ Yang Ke - te，Chen Hua - jun. Special area oreented semantic searchresults ranking algorithm ［J］. Computer Applications and Software，2011，28 (12):172 -175.

［43］ Tolba A，Eladawi N，Elmogy M. An enhanced indexing and ranking technique on the semantic web ［J］. arXiv preprint arXiv:1111. 6713，2011.

［44］ Lewen H，d'Aquin M. Extending open rating systems for ontology ranking and reuse ［M］ ∥Knowledge Engineering and Management by the Masses. Springer Berlin Heidelberg，2010:441 -450.

［45］ Vrande cˇi c' D，Sure Y. How to design better ontology metrics［M］ ∥The Semantic Web:Research and Applications. Springer Berlin Heidelberg，2007:311 -325.

［46］ Finin T W，Sachs J，Parr C S. Finding Data，Knowledge，and Answers on the Semantic Web ［C］ ∥FLAIRS Conference，2007:2 -7.

［47］ 吳剛，張闊，李涓子，等. 利用相互增強(qiáng)關(guān)系迭代計(jì)算本體中概念與關(guān)系的重要性［J］. 計(jì)算機(jī)學(xué)報(bào)，2007，30 (9):1490 -1499.

［48］ Franz T，Schultz A，Sizov S，et al. Triplerank:Ranking semantic web data by tensor decomposition ［M］. Springer Berlin Heidelberg，2009.