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

張 偉

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 遼寧 沈陽110819)

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

張 偉

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 遼寧 沈陽110819)

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

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

0 引 言

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

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

圖1所示的是一個簡單的不確定圖，其中第一條邊線上的括號(1∶0.5)表示節(jié)點(diǎn)A到節(jié)點(diǎn)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點(diǎn)最近的兩個節(jié)點(diǎn)，則有多種可能的答案：(1)按照文獻(xiàn)[1]所定義的以實(shí)際距離(路徑權(quán)值)占主導(dǎo)考慮因素的距離定義，答案是{B，C}，因?yàn)锽和C距A較近；(2)按照文獻(xiàn)[2]所定義的最大可靠性距離定義(某些文獻(xiàn)稱之為概率可達(dá)性)，答案是{B，D}，其中節(jié)點(diǎn)A和B連通的概率是0.5，節(jié)點(diǎn)A和D連通的概率是0.5×(0.7+(0.3×0.8)-0.7×(0.3×0.8))=0.386，即A和B連通并且B和D至少有一條路徑連通的概率。而節(jié)點(diǎn)A和C連通的概率則是0.5×0.3=0.15，故不選擇C。注意，在最大可靠性距離中沒有考慮路徑的權(quán)值(長度)[6-8]。

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

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

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

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

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

1 不確定圖模型

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

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

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

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

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

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

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

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

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

2.1 樸素的k-NN查詢算法

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

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

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

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

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

begin

置T :=?;

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

d := 0; /* d為以源點(diǎn)s為中心的搜索范圍半徑，初始時(shí)為0 */

While (|T|

begin

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

/* 調(diào)用Dijkstra求取G’中離開源點(diǎn)s最短距離小于等于d的所有節(jié)點(diǎn)，放入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é)點(diǎn)，要選取概率最大的幾個留在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*算法，當(dāng)同一個節(jié)點(diǎn)t離開源點(diǎn)s有多條最短路徑時(shí)，Dijkstra*算法要記錄所有這些最短路徑。子算法ComputPL(s, t)計(jì)算源點(diǎn)s到節(jié)點(diǎn)t的最短路徑概率，其算法描述如下：

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

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

begin

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

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

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

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

for Pg中的每個圖例g’ do

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

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

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

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

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

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

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

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

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

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

begin

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

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

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

(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)成的 隨機(jī)向量X = (X1,X2,…,Xm)；隨機(jī)向量X有2m種取值，代表所有可能圖例；若X的當(dāng)前取值代表的圖例使(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)計(jì)數(shù)變量M*/

(8) } /* end of while */

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

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

end /* Sub-Algorithm */

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

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

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

那么有：

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

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

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

那么有：

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

有：

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

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

3 實(shí)驗(yàn)結(jié)果與性能比較

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

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 實(shí)驗(yàn)1

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

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

圖2 樸素k-NN查詢算法的時(shí)間復(fù)雜度隨k值變化的過程

3.3 實(shí)驗(yàn)2

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

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

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

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

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

3.4 實(shí)驗(yàn)3

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

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

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

4 結(jié) 語

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

[1] 張旭，何向南，金澈請，等. 面向不確定圖的k最近鄰查詢 [J]. 計(jì)算機(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] 華斌，楊超．主成分分析在復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的應(yīng)用[J]．計(jì)算機(jī)應(yīng)用與軟件，2015，32(9)：261-263.

[4] 張碩,高宏,李建中,等.不確定圖數(shù)據(jù)庫中高效查詢處理[J].計(jì)算機(jī)學(xué)報(bào), 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] 張偉,俞瑞釗,何志均. 可采納搜索算法最壞復(fù)雜度的下確界[J].計(jì)算機(jī)學(xué)報(bào)，1990，13(6)：449-455.

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

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

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

[10] 袁野，王國仁. 面向不確定圖的概率可達(dá)查詢[J].計(jì)算機(jī)學(xué)報(bào), 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].計(jì)算機(jī)學(xué)報(bào)，2010，33(8)：1359-1368.

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

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

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

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

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

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

[19] 亞森·艾則孜，李衛(wèi)平，郭文強(qiáng)．復(fù)雜網(wǎng)絡(luò)中基于WCC的并行可擴(kuò)展社團(tuán)挖掘算法[J]．計(jì)算機(jī)應(yīng)用與軟件，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。國家科技支撐計(jì)劃項(xiàng)目(2014BAI17B01)；軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室開放課題(SKLSDE-2012KF-02)。張偉，教授，主研領(lǐng)域：人工智能，機(jī)器學(xué)習(xí)。

TP311.13 TP392

A

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