不確定隨機(jī)網(wǎng)絡(luò)Top-k最近節(jié)點(diǎn)查詢算法

連春月，李孝忠，牛浩浩

(天津科技大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，天津 300457)

實(shí)際生活中，會遇到許多非確定的現(xiàn)象．為了研究這類非確定的現(xiàn)象，17世紀(jì)誕生了概率論．概率論基于大量的歷史數(shù)據(jù)，有效解決了很多統(tǒng)計(jì)問題．但是，有時(shí)因?yàn)楦鞣N原因無法獲得足夠多的數(shù)據(jù)，這時(shí)使用概率論解決問題就很難辦到．為了解決這類問題，Liu B于2007年提出了不確定理論[1]，并于2010年對不確定理論進(jìn)行重新定義[2]，為小樣本數(shù)據(jù)、甚至是無樣本數(shù)據(jù)的統(tǒng)計(jì)提供了新的理論基礎(chǔ)．

經(jīng)過多年研究與實(shí)踐，不確定理論得到了充分的發(fā)展與廣泛的應(yīng)用．2013年，高原[3]詳細(xì)研究了不確定網(wǎng)絡(luò)的最短路徑問題；2014年，Zhou等[4]研究了不確定網(wǎng)絡(luò)的最短路徑的逆不確定分布問題；2015年，Zhou等[5]給出了不確定網(wǎng)絡(luò)的最小生成樹的路徑最優(yōu)條件．

對于一個(gè)復(fù)雜網(wǎng)絡(luò)，某些弧的權(quán)重可以通過對歷史數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析得到，而某些弧由于沒有歷史數(shù)據(jù)或者歷史數(shù)據(jù)無效，導(dǎo)致其權(quán)重不能通過概率統(tǒng)計(jì)得到，只能利用專家的經(jīng)驗(yàn)數(shù)據(jù)，得到不確定弧的權(quán)重的不確定分布函數(shù)．

2013年，為了解決這類既有非確定因素，又有不確定因素的現(xiàn)象，Liu Y[6]開創(chuàng)了機(jī)會理論．2014年，Liu B[7]首次將機(jī)會理論引入不確定網(wǎng)絡(luò)，提出不確定隨機(jī)網(wǎng)絡(luò)的概念．2015年，盛玉紅[8]對不確定隨機(jī)網(wǎng)絡(luò)的最短路徑問題、最小生成樹問題和最大流問題進(jìn)行研究，提出理想機(jī)會分布函數(shù)的概念并利用其求解了上述問題．

關(guān)于非確定性數(shù)據(jù)的Top-k查詢問題，學(xué)者們提出了各種計(jì)算方法，包括U-topK[9]、U-kRanks[10]，PT-k[11]，Global-topK[12]等．Li 等[13]提出了基于權(quán)值參數(shù)的排名函數(shù)，實(shí)現(xiàn)了排名分值與概率平衡．2016年，郭長友等[14]首次將不確定理論應(yīng)用到不確定數(shù)據(jù)的Top-k查詢計(jì)算中．

非確定數(shù)據(jù)的 Top-k查詢在 P2P系統(tǒng)、電纜鋪設(shè)等方面已經(jīng)有了實(shí)際應(yīng)用，但不確定數(shù)據(jù)和隨機(jī)數(shù)據(jù)同時(shí)存在的Top-k查詢方面的研究并不多．本文基于現(xiàn)有研究成果，將包含不確定數(shù)據(jù)和隨機(jī)數(shù)據(jù)的問題轉(zhuǎn)化為不確定隨機(jī)網(wǎng)絡(luò)，并在深度優(yōu)先遍歷的算法上，提出在一定機(jī)會測度的情況下，尋找距離某個(gè)節(jié)點(diǎn)最近的k個(gè)節(jié)點(diǎn)的算法，能有效解決在經(jīng)驗(yàn)數(shù)據(jù)和小樣本數(shù)據(jù)混雜情況下的節(jié)點(diǎn)查詢問題．

1 相關(guān)概念

1.1 不確定理論[1]

定義1設(shè)Γ為非空集合，L是Γ上的σ-代數(shù)，任意的Λ∈L稱為一個(gè)事件．如果從L到實(shí)數(shù)集R的集函數(shù)M滿足以下條件：

公理 1(規(guī)范性) 對于全集Γ，有M{Γ}=1；

公理 2(對偶性) 對于任意的事件Λ∈L，有M{Λ}+M{Λc}=1；

公理 3(次可列可加性) 對于可數(shù)的事件序列M{Λ}，有

則稱集函數(shù) M 為Γ上的不確定測度，三元組(Γ,L, M)稱為一個(gè)不確定空間．

為了研究乘積空間上的不確定測度，Liu B提出了乘積公理[1]：

公理 4設(shè)(Γi,Li,Mi)為一列不確定空間，則乘積不確定測度M為

不確定變量的定義是由抽象的不確定空間和Borel集描述的．如果僅從定義出發(fā)，在理解和應(yīng)用不確定變量時(shí)都會遇到困難，為了更好地理解不確定變量，給出如下不確定分布的概念．

定義 4若不確定變量ξ具有不確定分布

其中 a和 b為常數(shù)，則ξ為線性的不確定變量，記為L( a, b)．

定義 5若對于任意的 α∈ (0,1)，不確定變量ξ的不確定分布Φ(x)的反函數(shù) Φ-1(α)存在且唯一，則稱Φ(x)為正則分布，稱ξ為正則不確定變量．

定義 6若不確定變量ξ具有正則分布Φ(x)，則其反函數(shù)Φ-1(α)稱為ξ的逆不確定分布．

例 1根據(jù)定義 4—定義 6，線性不確定變量L( a, b)的逆不確定分布為

1.2 機(jī)會理論[6]

定義 7設(shè)(Γ,L,M)× (Ω,A, Pr)是一個(gè)機(jī)會空間，Θ是L×A的一個(gè)事件，那么事件Θ的機(jī)會測度為

定義 8從機(jī)會空間(Γ ,L ,M )× (Ω,A, Pr)到實(shí)數(shù)集 R的可測函數(shù)ξ稱為不確定隨機(jī)變量，即對于任意的Borel實(shí)數(shù)集Β，集合

是L×A中的一個(gè)事件．定義 9設(shè) f:Rn→R是一個(gè)可測函數(shù)，ξ1,ξ2,…,ξn是機(jī)會空間(Γ,L,M)×(Ω,A, Pr)上的一列不確定隨機(jī)變量，那么對任意的(γ,ω)∈?！力?，ξ=f(ξ1,ξ2,…,ξn)是由

所確定的一個(gè)不確定隨機(jī)變量．

定義10η1,η2,…,ηm是一系列獨(dú)立的隨機(jī)變量，概率分布分別為Ψ1,Ψ2,…,Ψm，τ1,τ2,…,τn是一列不確定變量，不確定分布分別為?1,?2,… ,?n，那么不確定隨機(jī)變量

有一個(gè)機(jī)會分布

其中，對任意的實(shí)數(shù)y1, y2,…,ym，F(xiàn)(x, y1,y2,…,ym)是不確定變量f(η1,η2,…,ηm,τ1,τ2,…τn)的不確定分布，它可由其反函數(shù)F-1(α;y, y,…,y)=f(y,y,…,12m12y,?-1(α) ,?-1(α),…,?-1(α))決定，條件是f為對于m12nτ1,τ2,…,τn的單增函數(shù)．

例 2設(shè)η是一個(gè)隨機(jī)變量，其概率分布為Ψ，τ是一個(gè)不確定變量，其不確定分布為?．那么，ξ= η+ τ是一個(gè)不確定隨機(jī)變量，ξ的機(jī)會分布為

其中，y是隨機(jī)變量η的任一實(shí)現(xiàn)．

2 不確定隨機(jī)網(wǎng)絡(luò)下的Top-k查詢算法

2.1 不確定隨機(jī)網(wǎng)絡(luò)

N是節(jié)點(diǎn)集合，U是不確定弧的集合，R是隨機(jī)弧的集合，W 是不確定權(quán)重和隨機(jī)權(quán)重的集合，那么四元組(N，U，R，W)被稱為一個(gè)不確定隨機(jī)網(wǎng)絡(luò)．

例3圖1是有4個(gè)節(jié)點(diǎn)的不確定隨機(jī)網(wǎng)絡(luò)．其中，隨機(jī)權(quán)重ηAB、ηCD的概率分布分別為ΨAB、ΨCD．不確定權(quán)重τBC具有正則的不確定分布?BC．各邊的權(quán)重的分布函數(shù)見表1．

圖1 4節(jié)點(diǎn)不確定隨機(jī)網(wǎng)絡(luò)Fig. 1 Uncertain random network with 4 nodes

表1 圖1網(wǎng)絡(luò)中各邊的權(quán)重的分布函數(shù)Tab. 1 Distribution function of the edge’s weight of figure 1

ΨAB，ΨCD的概率分布函數(shù)分別為

?BC的不確定分布為

則權(quán)重的機(jī)會分布函數(shù)為

計(jì)算可得

假設(shè)機(jī)會測度Φ (x) =0.95，計(jì)算得權(quán)重x=25.7．

2.2 Top-k最近節(jié)點(diǎn)查詢算法

給定不確定隨機(jī)網(wǎng)絡(luò)G，節(jié)點(diǎn)間的權(quán)重的機(jī)會分布函數(shù)為Φ，則節(jié)點(diǎn)間的路徑長度機(jī)會分布函數(shù)D＝Φ，即將節(jié)點(diǎn)間的權(quán)重建模為節(jié)點(diǎn)間的路徑長度．基于節(jié)點(diǎn)間的路徑長度，提出以下的不確定隨機(jī)網(wǎng)絡(luò)Top-k最近節(jié)點(diǎn)查詢算法．

輸入：不確定隨機(jī)網(wǎng)絡(luò) G＝(N，U，R，W)，選擇的最近節(jié)點(diǎn)個(gè)數(shù)k，初始節(jié)點(diǎn)p，機(jī)會測度α．

輸出：當(dāng)機(jī)會測度為α?xí)r，與 p最近的k個(gè)節(jié)點(diǎn)，以及對應(yīng)路徑．

具體算法如下：

(1)計(jì)算所有節(jié)點(diǎn)間 i，j間的路徑，初始節(jié)點(diǎn)為：i＝1，j＝2，并將 i標(biāo)記為已訪問；

(2)從N中取出非i節(jié)點(diǎn)k，若兩點(diǎn)間有路徑，將k標(biāo)記為已訪問；

(3)若k＝j(luò)，將所有已訪問節(jié)點(diǎn)組成的路徑放入路徑集合D中，回溯至上一個(gè)已訪問節(jié)點(diǎn)，重復(fù)步驟(2)；否則，重復(fù)步驟(2)；

(4)若 k≥n，j++，重復(fù)步驟(1)—(3)，直至 j＝n；

(5)若 j＞n，j- -，i++，重復(fù)步驟(1)—(4)，直至 i＝n；

(6)計(jì)算D中所有路徑的機(jī)會分布函數(shù)；

(7)計(jì)算當(dāng)機(jī)會測度為α?xí)r，點(diǎn) p到所有節(jié)點(diǎn)的路徑長度；

(8)找到距離點(diǎn) p最近的k個(gè)點(diǎn)及對應(yīng)路徑，算法結(jié)束．

算法中步驟(2)—(3)部分的代碼如下：

function FindPath(matrix，startNode，endNode){

result[nPos]＝startNode.key；//將當(dāng)前節(jié)點(diǎn)放入結(jié)果集

Mark[startNode.key]＝true；//標(biāo)記為已訪問nPos++；

while(nPos !＝0){

var tempVal＝result[nPos-1]；//獲取結(jié)果集最后

一個(gè)元素

if(tempVal＝＝endNode.key){//如果當(dāng)前節(jié)點(diǎn)為

結(jié)束節(jié)點(diǎn)，將結(jié)果集中的節(jié)點(diǎn)放入路徑結(jié)果集中

for(let j＝0；j＜nPos；j++){

resultPath[pathNum][j]＝result[j]；

}

nPos- -；//回溯至目標(biāo)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)

result[nPos]＝0；

pathNum++；//新增路徑數(shù)目

Mark[endNode.key]＝false；

break；

}；

while(startNode.flag＜matrix.length){

if(matrix[tempVal][startNode.flag]＝＝1){

if(Mark[startNode.flag]＝＝false){

var tempNode＝new Node()；

tempNode.key＝startNode.flag；

tempNode.flag＝0；

FindPath(matrix，tempNode，endNode)；

}

}

startNode.flag++；

}

if(startNode.flag＝＝matrix.length){

nPos- -；

startNode.flag＝0；

Mark[startNode.key]＝false；

break；

}

}

為了更好地理解算法，用例4進(jìn)行簡要說明．

例 4有 5個(gè)節(jié)點(diǎn)的不確定隨機(jī)網(wǎng)絡(luò)，如圖 2所示．其中τAB、τBD、τDE是不確定權(quán)重，且分別具有正則的不確定分布?AB、?BD、?DE；ηAE、ηBC、ηCD是隨機(jī)權(quán)重，分別具有概率分布ΨAE、ΨBC、ΨCD，網(wǎng)絡(luò)中各邊的權(quán)重的分布函數(shù)見表 2．求距離節(jié)點(diǎn) A最近的3個(gè)節(jié)點(diǎn)．

圖2 5節(jié)點(diǎn)不確定隨機(jī)網(wǎng)絡(luò)Fig. 2 Uncertain random network with 5 nodes

表2 圖2網(wǎng)絡(luò)中各邊的權(quán)重的分布函數(shù)Tab. 2 Distribution function of the edge’s weight of figure 2

能夠得到任意兩點(diǎn)間的路徑長度機(jī)會分布函數(shù)

其中F( x,yij,(i,j)∈R)由它的逆不確定分布確定：

當(dāng)機(jī)會測度α＝0.9時(shí)，計(jì)算出任意兩點(diǎn)間的最小路徑長度，計(jì)算結(jié)果見表3．

表3 α＝0.9時(shí)節(jié)點(diǎn)間路徑長度Tab. 3 Path length between nodes when α＝0.9

當(dāng)機(jī)會測度α＝0.8時(shí)，計(jì)算出任意兩點(diǎn)間的最小路徑長度，計(jì)算結(jié)果見表4．

表4 α＝0.8時(shí)節(jié)點(diǎn)間路徑長度Tab. 4 Path length between nodes when α＝0.8

所以，當(dāng)機(jī)會測度α＝0.9，k＝3時(shí)，距離節(jié)點(diǎn)A最近的 3個(gè)點(diǎn)分別為 E、B、C．當(dāng)機(jī)會測度α＝0.8，k＝3時(shí)，距離節(jié)點(diǎn)A最近的3個(gè)點(diǎn)分別為E、B、D．

當(dāng)機(jī)會測度變化時(shí)，查詢到的最短路徑節(jié)點(diǎn)也可能發(fā)生變化，所以需要根據(jù)現(xiàn)實(shí)需求來指定機(jī)會測度，以得到預(yù)期結(jié)果．

3 結(jié) 語

本文提出了不確定隨機(jī)網(wǎng)絡(luò)的 Top-k最近節(jié)點(diǎn)查詢問題，并使用機(jī)會理論求解該問題，設(shè)計(jì)不確定隨機(jī)網(wǎng)絡(luò)在一定機(jī)會測度條件下的 Top-k查詢算法．此算法能正確求解不確定隨機(jī)網(wǎng)絡(luò)的Top-k查詢問題，在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目較小、不確定隨機(jī)分布較簡單時(shí)的效率較高；一旦網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目眾多、網(wǎng)絡(luò)非常復(fù)雜時(shí)，則計(jì)算的時(shí)間復(fù)雜度會較高．如何對算法進(jìn)行改進(jìn)，以提高算法的計(jì)算效率是下一步的研究方向．