一種基于語(yǔ)義相似度的P2P數(shù)據(jù)查詢方法

林 曉（南京航空航天大學(xué)，210000）

一種基于語(yǔ)義相似度的P2P數(shù)據(jù)查詢方法

林 曉
（南京航空航天大學(xué)，210000）

目前P2P網(wǎng)絡(luò)中數(shù)據(jù)查詢?cè)谡Z(yǔ)義方面的研究較少，而基于DHT的數(shù)據(jù)檢索只支持準(zhǔn)確查詢，導(dǎo)致查詢準(zhǔn)確率不高，但是好的索引項(xiàng)的建立會(huì)給查詢帶來(lái)很大的方便。本文結(jié)合了RDF和WordNet在語(yǔ)義方面的特點(diǎn)提出了一種新的簡(jiǎn)易R(shí)DF概念列表來(lái)表示文檔，并通過(guò)計(jì)算語(yǔ)義相似度來(lái)決定輸出結(jié)果的P2P數(shù)據(jù)查詢方法。仿真實(shí)驗(yàn)證明本文方法可以較好的提高查詢成功率。

P2P網(wǎng)絡(luò)；簡(jiǎn)易R(shí)DF概念列表；語(yǔ)義相似度；數(shù)據(jù)查詢

0 引言

在是P2P網(wǎng)絡(luò)應(yīng)用中，數(shù)據(jù)查詢是經(jīng)常需要使用到一個(gè)基本功能，如何在大數(shù)據(jù)、大應(yīng)用的P2P系統(tǒng)中快速準(zhǔn)確地找到滿足給定條件的數(shù)據(jù)，是P2P網(wǎng)站能夠順利運(yùn)行關(guān)鍵環(huán)節(jié)。但是當(dāng)前許多研究都只是單純地考慮節(jié)點(diǎn)或文檔間的距離因素而忽略了語(yǔ)義對(duì)查詢結(jié)果的影響，而基于分布式哈希表DHT(Distributed Hash Table)的方法也只支持精確查詢，對(duì)文檔的搜索返回不相關(guān)的內(nèi)容經(jīng)常會(huì)對(duì)搜索準(zhǔn)確率產(chǎn)生影響，再者由于索引不當(dāng)，搜索不到有關(guān)文檔還會(huì)影響到搜索的召回率。為此，本文提出一種新的簡(jiǎn)易R(shí)DF概念列表表示法來(lái)表示文檔，并通過(guò)基于語(yǔ)義相似度的計(jì)算來(lái)進(jìn)行數(shù)據(jù)查詢的P2P搜索方法。使用簡(jiǎn)易R(shí)DF概念列表來(lái)表示文檔，提高索引方面的能力，并通過(guò)計(jì)算查詢消息和表示文檔的概念列表之間的語(yǔ)義相似度來(lái)決定二者的匹配程度，從而提高查詢準(zhǔn)確率。

1 文檔表示方法

1.1 現(xiàn)有文檔表示方法

節(jié)點(diǎn)上的文檔如何表示對(duì)P2P系統(tǒng)中的數(shù)據(jù)查詢尤為重要，因?yàn)樗鼪Q定著整個(gè)查詢的索引效率。一個(gè)好的索引項(xiàng)的建立對(duì)于整個(gè)系統(tǒng)的查詢效率的提高起著舉足輕重的作用。目前大多數(shù)文檔表示方法是基于向量空間模型的，以單一向量表示一篇文檔，每個(gè)向量的元素作為文檔中單詞的出現(xiàn)頻率和權(quán)重。另外，文獻(xiàn)提出的方法未考慮單詞出現(xiàn)頻率對(duì)語(yǔ)義相似度的影響，而只是單純將名詞列表作為文檔的搜索形式。

1.2 簡(jiǎn)易R(shí)DF概念列表表示法

本文采用簡(jiǎn)易R(shí)DF概念列表表示法對(duì)文檔進(jìn)行表示。RDF(Resource Description Framework)是一個(gè)應(yīng)用程序框架，允許將資源描述為結(jié)構(gòu)化的數(shù)據(jù)并在不同的應(yīng)用程序之間交換和重用這些資源。它可以提供結(jié)構(gòu)化的元數(shù)據(jù)來(lái)標(biāo)記資源，資源擁有的屬性可以被定義為一個(gè)擁有相應(yīng)屬性值的屬性類。例如我們可以把文檔所屬的類別作為文檔的一個(gè)屬性來(lái)描述，關(guān)于體育方面的文檔我們將其類別屬性標(biāo)識(shí)為sports,娛樂(lè)方面的文檔我們將其類別屬性標(biāo)識(shí)為entertainment等等。根據(jù)RDF的這個(gè)特殊性能，我們提出的簡(jiǎn)易R(shí)DF概念列表把文檔表示為單詞和詞頻組成的二元組列表的形式：

2 語(yǔ)義相似度的計(jì)算

在WordNet對(duì)語(yǔ)義相似度計(jì)算的研究中，一個(gè)最顯著的特征是以單詞的含義來(lái)代替原有的拼寫(xiě)形式來(lái)組織詞匯信息，單詞間的三種主要語(yǔ)義關(guān)系分別為：整體部分關(guān)系（meronymy）、遺傳關(guān)系（inheritance）、以及反義關(guān)系（antonymy），這些關(guān)系將對(duì)我們計(jì)算語(yǔ)義相似度提供很大幫助。

2.1 單詞間語(yǔ)義相似度的計(jì)算

文獻(xiàn)[4]給出了兩個(gè)單詞間的語(yǔ)義距離的定義

當(dāng)單詞有多個(gè)含義時(shí)，單詞間的語(yǔ)義距離是兩個(gè)單詞中任意兩個(gè)含義間語(yǔ)義距離的最小值，即

2.2 查詢相似度的計(jì)算

本文中查詢相似度定義如下：

由于事先已有簡(jiǎn)易R(shí)DF概念列表中的一項(xiàng)作為屬性來(lái)標(biāo)識(shí)文檔主題，不屬于同一主題的文檔我們認(rèn)為其相似度為0，如兩篇分別類屬于entertainment和sports的文檔，可以認(rèn)為二者沒(méi)有相似性。在兩個(gè)文檔屬于同一主題的情況下比較二者的語(yǔ)義相似度可以避免更多的計(jì)算來(lái)提高查詢效率。

3 數(shù)據(jù)查詢過(guò)程

我們用圖1給出的圖形簡(jiǎn)單的表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，圖中字母標(biāo)識(shí)的圓圈用來(lái)表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，各圓圈之間的連線表示節(jié)點(diǎn)之間的連接關(guān)系，有連線的表示節(jié)點(diǎn)為鄰居關(guān)系，可以相互通信。把這種機(jī)制應(yīng)用到P2P網(wǎng)絡(luò)中，可以增強(qiáng)節(jié)點(diǎn)之間的聯(lián)通性，因?yàn)楣?jié)點(diǎn)不僅可以查詢到自己的鄰居節(jié)點(diǎn)信息，還可以查詢鄰居的鄰居甚至更多，將會(huì)提高查全率從而更好地提高查準(zhǔn)率。

圖1 拓?fù)浣Y(jié)構(gòu)圖

3.1 相關(guān)工作

單個(gè)節(jié)點(diǎn)的數(shù)據(jù)表為：（1）節(jié)點(diǎn)自身建立的本地資源索引表LRIT(Local Resource Indexed Table)，用來(lái)記錄本地文檔列表。節(jié)點(diǎn)A的LRIT如下表1所示：（2）與該節(jié)點(diǎn)相關(guān)聯(lián)的鄰居節(jié)點(diǎn)資源索引表NRIT(Neighbor Resource Indexed Table)，用來(lái)保存鄰居節(jié)點(diǎn)所包含的文檔列表。節(jié)點(diǎn)A的NRIT如下表2所示：

表1 節(jié)點(diǎn)A的LRIT

表2 節(jié)點(diǎn)A的NRIT

3.2 查詢過(guò)程

第一步：對(duì)LRIT進(jìn)行檢查，若無(wú)合適選項(xiàng)，則跳入步驟四；

第五步：若查詢無(wú)返回標(biāo)志，則輸入NULL。

這里使用生存值TTL(Time To Live)來(lái)防止消息的無(wú)限轉(zhuǎn)發(fā)帶來(lái)的網(wǎng)絡(luò)堵塞問(wèn)題。由查詢過(guò)程可以看出最后的返回結(jié)果可能不能包含所有用戶給出的關(guān)鍵詞，這也是區(qū)別于精確查詢的地方。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文提出的基于語(yǔ)義相似度的P2P查詢方法的有效性，通過(guò)仿真實(shí)驗(yàn)針對(duì)不同查詢次數(shù)下的查詢成功率與Gnutella方法做了對(duì)比，結(jié)果證明本文方法查詢成功率較高。

5 結(jié)束語(yǔ)

本文通過(guò)結(jié)合RDF和WordNet在語(yǔ)義方面的特征提出一種新的文檔表示方法——簡(jiǎn)易R(shí)DF概念列表法，并通過(guò)計(jì)算查詢和文檔之間的語(yǔ)義相似度來(lái)確定查詢結(jié)果。仿真實(shí)驗(yàn)證明本文方法可以很好的提高查詢成功率，但是下一步的工作還要對(duì)其在帶寬利用率和查詢路徑方面的高效性做深一步的研究，以便進(jìn)一步證明該方法的實(shí)用性和科學(xué)性。

[1] John Rission，Tim Moors.Survey of research towards robust peer-to-peer networks:Search methods [J] Computer Networks 50(2006)3485-3521.

圖2 查詢成功率比較(查詢次數(shù)數(shù)量級(jí)為104)

[2] Pandya A,Bhattacharyya P.Text similarity measurement using concept representation of texts[C]//Proceedings of First International Conference on Pattern Recognition and MachineIntelligence.Berlin,Germany:Springer,2005:678-689.

[3] Roy R ,Mili H ,Blettner M .Development andapplication of a metric on semantic nets[J]. IEEE Transaction of a metric on System,Man and Cybernetics,1989,19(1):17-30

[4] Song Shaoxu,,Li Chunping.TCUAP: a novel approach of text clustering using asymmetric proximity[C]// Proceedings of the 2nd Indian International Conference on Artificial Intelligence.India: IICAI 2005:604-613

[5] 顏偉,荀恩東.基于WordNet的英語(yǔ)詞語(yǔ)相似度計(jì)算[A].第二屆全國(guó)學(xué)生計(jì)算語(yǔ)言學(xué)研討會(huì)[C],2004.

[6] Sai Ho Kwok.P2P Searching trends:2002-2004. Information Processing and Management 42(2006):237-247

[7] 孫爽，章勇.一種基于語(yǔ)義相似度的文本聚類算法[J].南京航空航天大學(xué)學(xué)報(bào)，2006，389(6):712-716.

Research of P2P Data Query Based on Semantic Similarity

Lin Xiao
（Nanjing University of Aeronautics & Astronautics，210000）

There is less research on data query of P2P network based on semantic,and data query based on DHT can only support precise query ,so the precision is not high.But a good query index can play an important role and help enhance the success ratio.This paper introduced a new data query approach,which integrated RDF with WordNet based on their semantic feature and use a new description method to describe document ,which is called simple RDF concept list.The query result is decided by the semantic similarity computed by our new formula.It is approved that the new method is advanced in improving the query success ratio.

P2P network;simple RDF concept list;semantic similarity;data quer

林曉（1979-），女，浙江溫州人，南京航空航天大學(xué)黨政辦公室對(duì)外聯(lián)絡(luò)辦公室主任，碩士，助理研究員，研究方向?yàn)楦叩冉逃芾怼?/p>

中央高校基本業(yè)務(wù)費(fèi)項(xiàng)目（NR2014024，NR2014059）