張 偉

(東北大學計算機科學與工程學院 遼寧 沈陽110819)

基于抽樣的不確定圖k最近鄰搜索算法

張 偉

(東北大學計算機科學與工程學院 遼寧 沈陽110819)

在諸如生物網(wǎng)絡(luò)或社交網(wǎng)絡(luò)等各種由不確定數(shù)據(jù)組成的網(wǎng)絡(luò)中，不確定圖是一種十分重要和普遍使用的數(shù)學模型。由于不確定圖中計算兩點連通概率問題是#P完全問題，其k最近鄰查詢問題要比確定圖復雜得多，并且與“距離”的定義相關(guān)。采用“最短距離”作為距離定義，討論了在不確定圖是加權(quán)圖的情況下，求解k最近鄰搜索問題(k-NN問題)。為了克服計算兩點連通概率帶來的時間指數(shù)爆炸問題，提出了一個基于Dijkstra算法的抽樣k-NN查詢算法，研究了其收斂性和收斂速度，同時通過實驗驗證了所提出的方法效率優(yōu)于kMinDist方法并且具有很高的查全率。

人工智能 不確定圖 概率圖 生物網(wǎng)絡(luò) k-NN 抽樣技術(shù)

0 引 言

隨著云計算和大數(shù)據(jù)時代的到來，由于數(shù)據(jù)獲取存在噪聲、網(wǎng)絡(luò)傳送存在誤差、數(shù)據(jù)使用顆粒度差異等各種原因，使得我們面臨大量不確定數(shù)據(jù)的處理問題。在各種不確定數(shù)據(jù)組成的網(wǎng)絡(luò)(諸如生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò))中，不確定圖(或稱概率圖)是一種十分重要和普遍使用的數(shù)學模型，對不確定圖的搜索問題，也成為當前大數(shù)據(jù)研究當中的一個研究熱點[1-3]。

在實際應用中，不確定圖搜索問題十分常見。例如，在社交網(wǎng)絡(luò)中，用節(jié)點表示用戶，用邊表示好友關(guān)系，則好友之間的影響程度就可由邊上的概率來表示，從而構(gòu)成一個不確定圖；在城市的路網(wǎng)中，用節(jié)點表示地點，用邊表示街道，則街道是否擁堵就可由邊上的概率來表示，亦構(gòu)成不確定圖。不確定圖的搜索問題，通常是“在社交網(wǎng)絡(luò)中，與張三關(guān)系最密切的三個人是誰？”、“在城市路網(wǎng)中，從地點A到地點B最通暢的三條路徑是哪些路徑？”。這些問題(實質(zhì)是k-NN問題)在確定圖中是容易解決的，但是對不確定圖而言它們就變得十分復雜[4-5]。

圖1所示的是一個簡單的不確定圖，其中第一條邊線上的括號(1∶0.5)表示節(jié)點A到節(jié)點B的長度是1，該邊的存在概率是0.5，其他邊也使用類似的表示。在可能世界模型下，圖1的一個可能世界，亦稱可能圖例，如圖1(b)所示，該可能世界的概率是0.5×0.3×0.7×0.8×(1-0.4)×(1-0.6)=0.02。

圖1 一個簡單的不確定圖

對于圖1(a)，距離A點最近的兩個節(jié)點，則有多種可能的答案：(1)按照文獻[1]所定義的以實際距離(路徑權(quán)值)占主導考慮因素的距離定義，答案是{B，C}，因為B和C距A較近；(2)按照文獻[2]所定義的最大可靠性距離定義(某些文獻稱之為概率可達性)，答案是{B，D}，其中節(jié)點A和B連通的概率是0.5，節(jié)點A和D連通的概率是0.5×(0.7+(0.3×0.8)-0.7×(0.3×0.8))=0.386，即A和B連通并且B和D至少有一條路徑連通的概率。而節(jié)點A和C連通的概率則是0.5×0.3=0.15，故不選擇C。注意，在最大可靠性距離中沒有考慮路徑的權(quán)值(長度)[6-8]。

由此可見，不確定圖的近鄰查詢問題，比確定圖復雜得多，并且與“距離”的定義相關(guān)。目前被研究者采納比較多的“距離”定義主要有五種：(1)中位距離，其含義是：對于兩個節(jié)點s和t，中位距離是一個最大的數(shù)字D，使得s到t的最短距離小于等于D的所有可能圖例的概率之和不超過50%；(2)多數(shù)距離，其含義是：對于兩個節(jié)點s和t，多數(shù)距離是一個數(shù)字d，使得s到t的最短距離恰好等于d的所有可能圖例的概率之和最大；(3)期望可信距離，其含義是：兩個節(jié)點s和t在所有可能圖例中最短路徑的期望長度；(4)最短距離，其含義是：兩個節(jié)點s和t在所有可能圖例中最短路徑(即，在所有可能圖例中的最短路徑當中長度最小者)的長度，注意，該距離定義優(yōu)先考慮路徑的權(quán)值，路徑的概率起輔助作用(詳見下小節(jié)k-NN問題)；(5)概率可達性距離，其含義是：兩個節(jié)點s和t連通的概率[8-9]。

文獻[10]以生物信息學中的蛋白質(zhì)交互網(wǎng)和作者合作網(wǎng)絡(luò)為背景，提出了適用于中位距離、多數(shù)距離和期望可信距離的k-NN查詢算法。該算法使用了抽樣和剪枝技術(shù)，實現(xiàn)了較好的搜索效率[10-11]。文獻[10]提出了一個基于隨機抽樣的、可快速估計兩點連通概率的算法，該算法也是面向最大可靠性距離的，如進行一定延展，可以擴展到不確定圖的k-NN查詢問題中。

文獻[12]介紹了在一個有障礙物體的空間內(nèi)查詢一個特定點可見概率最大的k-NN近鄰的算法。該算法是面向最大可靠性距離的，使用了剪枝技術(shù)和近似采樣技術(shù)來提高搜索效率[12-13]。

然而，在很多不確定數(shù)據(jù)組成的網(wǎng)絡(luò)應用中，上述的第4種距離定義(即“最短距離”)是最適合的距離定義。例如，在社交網(wǎng)絡(luò)中有一類很常用的問題是好友推薦問題：當一個社交網(wǎng)絡(luò)用戶A向系統(tǒng)提出好友推薦要求時，怎么給他推薦好友呢？一個經(jīng)常的做法是，考察A的好友B、C有沒有共同的好友；如果B、C有共同的好友D、E，那么D、E很可能也是A感興趣的人，就可以推薦給A。當D、E距A相等且只能給A推薦一個好友時，優(yōu)先選擇D、E中與A連通概率大的節(jié)點。這里使用的“距離”定義就是以路徑長度為主導以概率為輔助的最短距離定義。文獻[1]根據(jù)社交網(wǎng)絡(luò)的這種特點，提出了最短距離的定義，并給出了一個k-NN查詢算法。由于該算法是基于可能世界模型的樸素路徑概率計算思想的，故效率受到一定限制。雖然文獻[1]對其算法做了“公用邊”優(yōu)化，在一定程度上推遲了時間復雜度拐點的出現(xiàn)時間，但不能避免時間復雜度指數(shù)爆炸。

因為最短距離在社交網(wǎng)絡(luò)中好友推薦類問題及相似的問題中有較好的應用意義，并且可以得到精確的計算結(jié)果，本文采用這個距離定義，并討論在不確定圖是加權(quán)圖的情況下，求解k最近鄰的查詢問題。提出了一個基于Dijkstra算法的抽樣k-NN算法，同時通過實驗驗證了本文所提出的方法效率優(yōu)于文獻[1]的kMinDist方法。

1 不確定圖模型

雖然人們根據(jù)所探討的具體問題提出過很多與不確定圖相關(guān)的問題定義，但是以下概念是核心的、共同的[14-16]。

定義1(不確定圖) 一個不確定圖可由四元組G=(V，E，P，W)表示，其中V和E分別表示G含有的節(jié)點集和邊集，變量P表示邊上的概率集合，即P(e)表示邊e∈E的存在概率，變量W表示邊上的權(quán)值集合，即W(e)表示邊e∈E的權(quán)值，我們約定W的值均為正整數(shù)。

定義2(可能世界模型) 對于一個不確定圖G，我們按照概率P對G的邊集合E進行一次采樣得到邊子集E’?E，則稱由E’及V、W構(gòu)成的確定圖G’=(V,E’,W)為不確定圖G的一個可能世界。

定義3 (最短距離) 對于一個不確定圖G=(V，E，P，W)中的任意兩個節(jié)點s和t，我們稱s和t的最短距離是在所有可能圖例中最短路徑(即在所有可能圖例的所有連通s和t的最短路徑當中長度最小者)的長度[1]，記為dL(s,t)。本定義采用了文獻[1]的最短距離定義。

對于圖1(a)而言，dL(A,D)=3。

與文獻[1]相同，我們定義k-NN查詢(即kMinDist查詢)為：對一個源點s，找到它的k個最近鄰節(jié)點，當其中長度最大的節(jié)點多于查詢所需時，用路徑概率PL(s,t)決定取舍(PL(s,t)路徑概率是含有該(最短)路徑的所有圖例的概率之和)。這個k-NN定義意味著k-NN查詢中距離不是最大的節(jié)點應直接進入查詢結(jié)果集中，其他則須用概率決定取舍。

2 基于Dijkstra算法的k-NN查詢算法

按照上述的距離定義，我們提出了一個基于Dijkstra算法并采用抽樣技術(shù)估計連通概率的k-NN查詢算法。首先，給出一個基礎(chǔ)的k-NN算法，它采用兩點連通概率的定義精確計算路徑概率PL(s,t)；當然基礎(chǔ)算法存在指數(shù)爆炸的缺點。其次，我們給出了一個對基礎(chǔ)算法的改進算法：它采用抽樣技術(shù)來估計概率PL(s,t)，進而解決k-NN查詢?？梢宰C明，該方法不僅克服了指數(shù)爆炸具有高效率，而且也具有很高的k-NN查全率和查準率。

我們首先討論第一種方法，即基礎(chǔ)的k-NN查詢算法(亦稱樸素k-NN算法)。

2.1 樸素的k-NN查詢算法

查詢一個不確定圖的給定源點s的k個最近鄰節(jié)點，可采用以下簡捷的方法：

將不確定圖G看成確定圖，采用Dijkstra算法從源點s出發(fā)，找到距離s節(jié)點最短距離(≤d)的所有節(jié)點集T(這里d為記錄當前離開s的距離閾值變量，初始時d=0)，當|T|k)在T中距離s最遠的幾個節(jié)點(它們與s的距離相等)中選取若干最短路徑概率較大的節(jié)點保留在T中使|T|=k，而從T中刪除其他概率小的節(jié)點。

上述求解k-NN方法可用算法語言形式描述如下：

算法1 Minimum Distance k-NN(G,s,k)

/* G是一個不確定圖，s是源點，k是需要查詢的節(jié)點個數(shù) */

begin

置T :=?;

令G’ = (V，E，W)，其中V，E，W 與不確定圖G=(V，E，P，W)中的相同；/* 此操作將不確定圖G當作確定圖G’來處理 */

d := 0; /* d為以源點s為中心的搜索范圍半徑，初始時為0 */

While (|T|

begin

Dijkstra (G’, s, d, T);

/* 調(diào)用Dijkstra求取G’中離開源點s最短距離小于等于d的所有節(jié)點，放入T */

d := d+1; /* 遞增d */

end; /* while */

If |T|=k then return(T);

else /* |T|>k */

{ for (tn1,…,tnj∈T with the largest dL(s,tni)) do

{ /* tn1,…,tnj是T中具有相等的最大dL(s,tni)的節(jié)點，要選取概率最大的幾個留在T中*/

shortest-path-length = dL;

ComputPL(G,s, tni, shortest-path-length);

按照PL(s, tni)(1≤i≤j)的從大到小順序排列{ tn1,…,tnj}，取前m個留在T中使|T|=k；

Return (T);

} /* for */

} /* else*/

end /* of the algorithm */

這里Dijkstra算法是稍做修改的Dijkstra*算法，當同一個節(jié)點t離開源點s有多條最短路徑時，Dijkstra*算法要記錄所有這些最短路徑。子算法ComputPL(s, t)計算源點s到節(jié)點t的最短路徑概率，其算法描述如下：

子算法1 ComputPL(G,s,t,shortest-path-length)

/* 這里G是不確定圖，s是源點，t是當前節(jié)點，shortest-path-length是s到t的最短路徑長度 */

begin

PL(s, t) :=0; /* 初始化 */

計算G中所有連通(s,t)的最短路徑長度為shortest path-length的路徑集合，記之為shortest-paths;

依shortest-paths刪節(jié)G得到g，使g是G的子圖且僅含shortest-paths中的邊和節(jié)點，則g由源點s到節(jié)點t的長度為dL(s,t) 的所有最短路徑組成；

生成g的所有可能圖例集Pg;

for Pg中的每個圖例g’ do

{ If g’包含shortest-paths中的任一最短路徑，

then { 計算g’的概率Pr(g’)：

累加Pr(g’)到PL(s, t)中：

PL(s, t) := PL(s, t) + Pr(g’);

} /* end of if */

} /end of for */

return(PL(s, t));

end /* Sub-Algorithm */

該算法根據(jù)定義3的距離定義，求取k-NN查詢時找到距離源節(jié)點s最近的k個節(jié)點集T，并在解決最后競爭時(離開s具有相同距離的多個節(jié)點全加入T使|T|多于k)將最短路徑概率大者保留在T中。由于需精確計算最短路徑概率，故其不能避免可能世界圖例的指數(shù)爆炸。為了解決這個問題，我們提出了一個基于抽樣技術(shù)的k-NN算法。

2.2 采用抽樣技術(shù)的k-NN查詢算法

理論和實驗都表明，當k變大時，計算圖中兩點的最短路徑概率是影響算法kMinDist[1]和本文的樸素k-NN查詢算法(Minimum Distance k-NN算法)效率的關(guān)鍵因素。為了徹底避開可能圖例的指數(shù)爆炸問題，我們對樸素Minimum Distance k-NN算法做以下改進，主要想法是放棄樸素k-NN查詢算法查詢最優(yōu)k-NN的目標，轉(zhuǎn)而求取近似最優(yōu)k-NN來保持k-NN算法的高效率。

注意到本文的樸素算法Minimum Distance k-NN算法僅在計算(s,t)以最短路徑連通的概率PL(s,t)時，才引發(fā)可能圖例數(shù)量的指數(shù)爆炸。在下面的對該樸素算法的改進算法Approximate Minimum Distance k-NN中，對T中距離s最遠的若干節(jié)點tn1,tn2,…,tnj(它們與s的距離相等)中，在計算PL(s,tni) (1≤i≤j)時，不再按照子算法ComputPL(s,tni)去逐一枚舉連通(s,tni)的所有可能圖例來計算源點s到節(jié)點tni的精確最短路徑概率，而是抽取所有可能圖例的一部分樣本來估計PL(s,tni)的近似值。抽取可能圖例的方法是：按照連通(s,tni)的子圖中每個邊的存在概率來決定該邊出現(xiàn)與否，并組成圖例。根據(jù)Chernoff引理，只要圖例抽樣個數(shù)N達到足夠大，就可以保證估計的精確度，而N不是k-NN查詢之k的一個指數(shù)函數(shù)，從而避免了指數(shù)爆炸。

改進算法按照上述最遠點最短路徑概率(估計值)較大原則，選取若干最短路徑概率較大的節(jié)點保留在T中使|T|=k，而從T中刪除其他最遠節(jié)點。我們實現(xiàn)了這個算法Approximate Minimum Distance k-NN，并分析和驗證了其不僅效率大大高于文獻[1]的kMinDist算法，而且其給出的k-NN的查詢結(jié)果具有令人滿意的查全率(平均≥97%)。

算法Approximate Minimum Distance k-NN的偽代碼形式描述與上節(jié)的算法Minimum Distance k-NN只有一條語句不同：即使用計算最短路徑概率近似值的Approx-ComputPL′(G,s,tni,shortest-path-length)語句替代了前算法的計算最短路徑概率之精確值的ComputPL(G,s,tni,shortest-path-length)語句。對應的子程序也相應改變：

子算法Approx-ComputPL′(s,t)采用抽樣法計算源點s到節(jié)點t的最短路徑概率的近似值，其算法描述如下：

子算法2 Approx-Comput PL′(G, s, t, shortest-path-length)

/* 這里G是不確定圖，s是源點，t是當前節(jié)點，shortest-path-length是s到t的最短路徑長度 */

begin

(1) N=0，M = 0; /* N表示需要抽取圖例總數(shù)，其計算法見Chernoff定理；M為循環(huán)記數(shù)器*/

(2) number-of-I = 0; /*N個圖例中使(s,t)以最短路徑連通的圖例個數(shù)*/

(3) 計算s到t的所有的最短路徑集shortest-paths，根據(jù)該最短路徑集組成一個子圖g，使g是G的子圖且僅含shortest-paths中的邊和節(jié)點；

(4) 子圖g =(V，E)的所有的邊組成一個向量(e1,e2…em)；

(5) while (M≤N) { /*循環(huán)N次*/

對每邊ei依該條邊上的概率P(ei)選取“1”作為Xi的值(未能取1則取0)，得到由{0，1}構(gòu)成的 隨機向量X = (X1,X2,…,Xm)；隨機向量X有2m種取值，代表所有可能圖例；若X的當前取值代表的圖例使(s,t)以最短路徑連通，我們記I(X) =1，否則記I(X) =0；

(6) if (I(X)==1)

number-of-I = number-of-I + 1；

(7) M=M+1; /* 遞增循環(huán)計數(shù)變量M*/

(8) } /* end of while */

(9) return (number-of-I/N)；

/* number-of-I/N =PL′(s, t)就是節(jié)點s與節(jié)點t抽樣算法得到的概率近似值*/

end /* Sub-Algorithm */

該算法按照最遠節(jié)點概率較大原則選取若干最短路徑概率較大的最外層節(jié)點保留在T中仍可保證給出的k-NN的查詢結(jié)果是最優(yōu)k-NN查詢的很好近似的原因有兩個：(1)根據(jù)我們采用的文獻[1]的最短距離dL(s,t)定義，所有非最外層節(jié)點應落入最優(yōu)k-NN查詢結(jié)果T中，該近似算法首先將所有非最外層節(jié)點選入k-NN查詢結(jié)果T中；(2)對于最外層節(jié)點(它們與源點s的距離相等)tn1,tn2,…,tnj，要選取近似概率PL′(s,tni)最大的幾個tni留在T中，使得|T|=k。我們通過大量的實驗，證明了這種近似算法的有效性，它不僅效率大大高于樸素k-NN查詢算法，而且其給出的k-NN的查詢結(jié)果具有令人滿意的查全率。

關(guān)于子算法Approx-ComputPL′(s,t)采用抽樣法計算連通概率近似值PL′(s,t)時的取樣容量N，我們有以下Chernoff定理[2]給出的取樣容量N與估計概率值(與精確概率值)的誤差關(guān)系作理論保障。

定理1 (Chernoff定理) 令X1,X2,…,XN是獨立同分布的隨機變量且它們有相同的期望值μ=E(Xi)。當N滿足

那么有：

我們稱N個樣本(的平均值)給出了μ的一個(ε，δ)精度的近似，其中0≤ε≤1、0≤δ≤1分別是誤差精度和置信度。

上述Chernoff定理在概率圖k-NN查詢問題中的一個直接應用[2]就是以下定理2。

定理2 令g是s到t的所有的最短路徑組成一個子圖、向量Xi=(e1,e2，…，em)是對g中所有邊ek按照其存在概率抽樣得到的一個圖例，當Xi使(s,t)以最短距離連通時令I(lǐng)(Xi)=1，否則I(Xi)=0。顯然I(X1),I(X2),…,I(XN)是獨立同分布的隨機變量且它們有相同的期望值E(Ii)=PL(s,t)。當N滿足：

那么有：

在定理2的實際應用中，為了計算N，我們引進一個連通概率閾值ρ(通常為某個很小的常數(shù)，如ρ=0.001)，當節(jié)點對(s,t)的(最短路徑)連通概率PL(s,t)小于ρ時，認為k-NN查詢可以忽略t，也即這樣的t是我們不感興趣的節(jié)點。于是定理2變?yōu)椋寒擭滿足：

有：

其中0≤ε≤1、0≤δ≤1分別是誤差精度和置信度，ρ是預先給定的一個很小的常數(shù)。

定理2的最后形式既給出了抽樣容量N與近似連通概率誤差的關(guān)系，也為我們計算N提供了理論公式。下一節(jié)的實驗驗證了該公式的準確性。

3 實驗結(jié)果與性能比較

為了驗證上述算法的有效性，我們在美國Enron公司的郵件網(wǎng)絡(luò)數(shù)據(jù)[1，10]上進行了k-NN查詢實驗。該郵件網(wǎng)絡(luò)把每個郵件帳戶看作一個網(wǎng)絡(luò)節(jié)點，如果帳戶i曾經(jīng)向帳戶j發(fā)送過一個郵件，就認為節(jié)點i與節(jié)點j之間存在一條無向邊。這個網(wǎng)絡(luò)有36 692個節(jié)點、183 818條邊。我們對數(shù)據(jù)進行了預處理：為每條邊附加了一個隨機產(chǎn)生的概率值，使之成為不確定圖，每條邊的權(quán)值為1。于是，每條邊附加的信息為：(1：p),其中1為權(quán)值、p∈[0,1]為概率值[10，17-19]。

3.1 實驗環(huán)境

我們實驗的硬件為主頻率為2.6 GHz的雙核CPU、4 GB內(nèi)存、硬盤500 GB的PC臺式計算機，操作系統(tǒng)為Windows XP,編程環(huán)境為VS2010集成開發(fā)平臺，編程語言為C++語言。

3.2 實驗1

本實驗主要顯示本文的樸素k-NN查詢算法(Minimum Distance k-NN)的效率。我們對美國Enron公司的郵件網(wǎng)絡(luò)數(shù)據(jù)進行了抽取以減小其圖數(shù)據(jù)的分枝系數(shù)(即，出邊數(shù))，使每個節(jié)點連接的邊不超過7條，抽取到的不確定圖數(shù)據(jù)Data1的節(jié)點個數(shù)N=200，邊數(shù)為665條；Data2的節(jié)點個數(shù)為663節(jié)點，邊的條數(shù)為1 785；Data3的節(jié)點個數(shù)為3 480節(jié)點，邊的條數(shù)為6 815。本實驗中我們采用數(shù)據(jù)集Data3 ，觀察k-NN查詢的k由50至730不斷增長時，算法為了得到查詢結(jié)果所需要的時間(時間單位為毫秒ms)。

圖2所示的是本文給出的樸素k-NN查詢算法(Minimum Distance k-NN)所耗費時間隨k變化的情況。我們知道，求取最短路徑的概率要枚舉含有最短路徑的子圖上的可能世界模型的所有圖例，是最耗費時間的計算步驟，也是決定k-NN算法效率的關(guān)鍵因素。上述實驗表明，樸素k-NN算法的時間復雜度會發(fā)生急速上升(指數(shù)爆炸)，拐點是在k=690處。這個實驗表明，在k較大時，即使求取一次兩節(jié)點連通概率都可能引發(fā)指數(shù)爆炸。

圖2 樸素k-NN查詢算法的時間復雜度隨k值變化的過程

3.3 實驗2

實驗2主要比較本文提出的樸素k-NN查詢算法(Minimum Distance k-NN)與抽樣k-NN查詢算法(Approximate Minimum Distance k-NN)的效率及查全率(recall ratio)。我們采用的不確定圖數(shù)據(jù)Data3是從Enron郵件數(shù)據(jù)中抽取的：節(jié)點個數(shù)為3 480節(jié)點，邊的條數(shù)為6 815時，觀察k-NN查詢的k由10至750不斷增長時，樸素k-NN查詢算法、抽樣k-NN查詢算法為了得到查詢結(jié)果所需要的時間(時間單位為毫秒ms)，同時考察兩算法的查全率變化情況。抽樣算法的參數(shù)為ε=0.1,δ=0.1,ρ=0.01。

從圖3中我們可以看到，抽樣k-NN查詢算法效率比樸素k-NN查詢算法高得多，因為它只對實際可能世界中的N個圖例(N是常數(shù))計算路徑的概率，減少了一個指數(shù)級復雜度的計算。樸素k-NN查詢算法在k大于690后時間復雜度開始急劇上升，而抽樣k-NN查詢算法則一直沒有驟然上升的情況。同時，從查全率和查準率來看(這里查全率指：抽樣k-NN查詢所得的k個節(jié)點與標準定義的k-NN查詢所得的k個節(jié)點的交集的勢除以k所得的比例[20]。顯然針對本文的k-NN定義，查準率等于查全率)，樸素k-NN查詢算法的查全率和查準率(當然)是100%；而抽樣k-NN算法也保持了很高的查全率和查準率(平均≥97%)，在實際應用中表現(xiàn)很好(如圖4所示)。

圖3 樸素k-NN查詢算法與抽樣k-NN查詢算法的時間比較

圖4 樸素k-NN查詢算法與抽樣k-NN查詢算法的查全率比較

我們也將本文的抽樣k-NN查詢算法與文獻[1]提出的“共用邊”優(yōu)化kMinDist算法的效率進行了比較。實驗表明(見圖3所示)，該優(yōu)化算法較之樸素k-NN只是推遲了指數(shù)爆炸而不能避免它，而抽樣k-NN算法則避免了指數(shù)爆炸。

3.4 實驗3

我們對抽樣法近似計算連通概率近似值PL(s,t)的收斂速度(相對于抽樣容量N)進行了研究。針對不確定圖數(shù)據(jù)Data1、 Data2和Data3，我們以樸素k-NN查詢算法(可以)計算出的節(jié)點間連通概率為基礎(chǔ)真實概率數(shù)據(jù)，考察抽樣算法計算的相應節(jié)點間近似連通概率的誤差的絕對值隨著抽樣量N的變化趨勢。我們做了k取不同值時的k-NN實驗，并記錄了在對應的k個節(jié)點上的近似連通概率與真實連通概率誤差的平均值(這里‘對應的k個節(jié)點’是指用抽樣算法近似計算出的k-NN節(jié)點集與真實k-NN節(jié)點集交集節(jié)點上的概率誤差)。在圖5中，以抽樣算法計算近似概率的抽樣容量N為橫軸，以近似概率誤差為縱軸，畫出了絕對概率誤差的平均值隨著抽樣量N的變化曲線。

可以看出，概率誤差隨著N的增加而迅速收斂。通?？稍贜≥2 000的范圍內(nèi)收斂到誤差不超過10%。這是相當好的結(jié)果，它為抽樣算法既保持較高的查詢搜索速度又保證高查全率提供了抽樣容量N的經(jīng)驗數(shù)據(jù)。

圖5 抽樣估計節(jié)點間連通概率之誤差隨抽樣量N的增加而變小

4 結(jié) 語

在各種不確定數(shù)據(jù)組成的網(wǎng)絡(luò)(諸如生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò))中，不確定圖(或稱概率圖)是一種十分重要和普遍使用的數(shù)學模型，對不確定圖的搜索問題，也成為當前大數(shù)據(jù)研究當中的一個研究熱點。依據(jù)參考文獻[1]，本文采用最短距離作為不確定圖的節(jié)點間距離定義，并討論在不確定圖是加權(quán)圖的情況下，求解最近k近鄰的查詢問題(k-NN問題)。本文提出了一個基于Dijkstra算法的抽樣k-NN算法，同時通過實驗驗證了本文所提出的方法效率優(yōu)于以前的方法。

[1] 張旭，何向南，金澈請，等. 面向不確定圖的k最近鄰查詢 [J]. 計算機研究與發(fā)展, 2011，48(10)：1871-1878.

[2] Potamias M，Bonchi F, Gionis A, et al. K-nearest neighbors in uncertain graphs[J].The VLDB Journal, 2010,3(1):997-1008.

[3] 華斌，楊超．主成分分析在復雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的應用[J]．計算機應用與軟件，2015，32(9)：261-263.

[4] 張碩,高宏,李建中,等.不確定圖數(shù)據(jù)庫中高效查詢處理[J].計算機學報, 2009,32(10):2066-2079.

[5] Beskales G, Soliman M A, Ilyas I F. Efficient search for the top-k probable nearest neighbors in uncertain databases[J]. Proceedings of the Vldb Endowment Vldb Endowment Hompage, 2008, 1(1):326-339.

[6] 張偉,俞瑞釗,何志均. 可采納搜索算法最壞復雜度的下確界[J].計算機學報，1990，13(6)：449-455.

[7] 梁聰，唐振華．一種基于DCT域局部能量的多聚焦圖像融合算法[J]．計算機應用與軟件，2016，33(5)：235-238．

[8] 信俊昌,王國仁,公丕臻,等. 不確定數(shù)據(jù)庫中的閾值輪廓查詢處理[J]. 計算機研究與發(fā)展,2009, 46(5):126-132.

[9] 黃冬梅，鄧斌，趙丹楓．帶權(quán)不確定圖的K最近鄰查詢算法[J]．計算機應用與軟件，2016，33(2)：212-216．

[10] 袁野，王國仁. 面向不確定圖的概率可達查詢[J].計算機學報, 2010，33(8)：1378-1386.

[11] Aggarwal C C. Managing and mining uncertain data: advances in database systems[M].New York: Springer,2009:77-107.

[12] 李傳文,谷峪,李芳芳,等.一種障礙空間中不確定對象的連續(xù)最近鄰查詢方法[J].計算機學報，2010，33(8)：1359-1368.

[13] 王艷秋, 徐傳飛, 于戈,等. 一種面向不確定對象的可見k近鄰查詢算法[J]. 計算機學報, 2010, 33(10):1943-1952.

[14] 梁美麗，牛之賢．改進的綜合顏色紋理特征圖像檢索[J]．計算機應用與軟件，2014，31(6)：228-231．

[15] 于戈,谷峪,鮑玉斌,等.云計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)：挑戰(zhàn)與進展 [J]. 計算機學報，2011,34(10):1753-1767.

[16] 張偉,洪聲貴. 基于GAG的Horn邏輯分布式推導模型[J]. 遼寧大學學報，2012,39(4):1-6.

[17] 周林,晏立,沈項軍．基于邊密度的復雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分方法[J]．計算機應用與軟件，2013，30(12)：8-11．

[18] 唐德權(quán),吳紹兵,凌志剛．一種新的圖聚類算法研究[J]．計算機應用與軟件，2014，31(6)：18-20.

[19] 亞森·艾則孜，李衛(wèi)平，郭文強．復雜網(wǎng)絡(luò)中基于WCC的并行可擴展社團挖掘算法[J]．計算機應用與軟件，2016，33(6)：37-39．

[20] Jiang L, Cai Z, Wang D. Bayesian citation-knn with distance weighting[J].International Journal of Machine Learning and Cybernetics,2014,5(2):193-199.

K-NEAREST NEIGHBOR SEARCH ALGORITHM FOR UNCERTAIN GRAPHS BASED ON SAMPLING

Zhang Wei

(CollegeofComputerScienceandEngineering,NortheasternUniversity,Shenyang110819,Liaoning,China)

Uncertain graphs are a very important and widely used mathematical model in networks composed of uncertain data such as biological networks or social networks. Since the two-point connectivity probability problem in the graph is a complete problem, the k nearest-neighbor query problem is much more complex than the normal graph and is related to the definition of "distance". Using the shortest distance as the definition of distance, we discuss the k-nearest neighbor search problem (k-NN) under the condition that the uncertain graph is a weighted graph. In order to overcome the problem of time exponential explosion caused by computing two-point connectivity probability, a sampling k-NN query algorithm based on Dijkstra algorithm is proposed. The convergence rate and convergence rate are studied. The proposed method is proved to be more efficient than kMinDist method and has high recall rate.

Artificial intelligence Uncertain graphs Probability graph Biological network k-NN Sampling technique

2016-07-07。國家科技支撐計劃項目(2014BAI17B01)；軟件開發(fā)環(huán)境國家重點實驗室開放課題(SKLSDE-2012KF-02)。張偉，教授，主研領(lǐng)域：人工智能，機器學習。

TP311.13 TP392

A

10.3969/j.issn.1000-386x.2017.06.033