蜜桃AV动漫,超碰另类欧美,蜜桃在线91区

本文首發(fā)于：http://xzyin.top/hnsw/
轉載請注明出處:http://xzyin.top/

關注微信公眾號：【charlie_mouse】進入技術交流群。

1. Small world vs. Random graph

在正式的介紹NSW和HNSW之前，先來了解一下小世界和隨機圖的概念方便后續(xù)理解為什么NSW能夠做近鄰查找。

1.1 Regular graph vs. Random graph

在圖論中對正則圖的定義如下:

正則圖是指每個頂點都有相同數(shù)目鄰居的圖，即每個頂點的度相同。若每個頂點的度均為 $k$ ，稱為 $k$ -正則圖。

正則圖

隨機圖是指在隨機過程的生成的圖，也就是節(jié)點和節(jié)點之間的連接是隨機建立的。

隨機圖和正則圖的對比

在正則圖中，當聚類系數(shù)接近飽和的時候，聚類系數(shù)比較高，平均路徑也比較短，但是此時節(jié)點的度比較高。

隨機圖節(jié)點的聚類系數(shù)比較低，并且節(jié)點的度也比較低。

1.2 Small world

在介紹完了隨機圖和正則圖，我們再來看一下小世界網(wǎng)絡。

在1967年Stanley Milgram從Kansas和Nebraska兩個州招募了一批志愿者，
請他們分別將一封信轉寄給一個住在Cambridge神學院學生的妻子和一個住在Boston郊區(qū)的股票經(jīng)紀人。
他給志愿者們這樣的要求：

雖然有寄信目標的相關信息，如果不是私人關系，不能把信直接寄給TA.
每次只能把信寄給最有可能知道這個人的熟人。
原始信封里有15張追蹤卡片，每次轉寄都要回寄一張給實驗者，其他的放在信封里寄給下一個人，這樣研究員可以隨時追蹤這些信函的路徑。

在到達的信函中，Stanley Milgram計算信函平均到達的節(jié)點為5個，也就是我們和一個陌生人建立連接只需要6步。

Stanley Milgram基于他的實驗提出了著名的六度分離理論，這個理論指出:

現(xiàn)實世界中的短路徑是普遍存在的。
人們可以有效地找到并且利用這些短路徑。

在小世界網(wǎng)絡中，可以把點與點之間的關系可以分為兩種：

同質性:同質性也就是相似的點會聚集到一起，相互連接具有鄰接邊。
弱連接:弱連接是指從每一個節(jié)點上，會有一些隨機的邊隨機連接到網(wǎng)絡中的節(jié)點上，這些節(jié)點是隨機均勻的。

1.3 三者之間的關系

有研究表明，小世界網(wǎng)絡介于正則圖和隨機圖之間，正則圖隨著隨機性的增加具有小世界的特性。

在這里插入圖片描述

我們可以這么理解：小世界在局部同類節(jié)點的連接呈現(xiàn)出規(guī)則，從全局來看不同類節(jié)點的連接呈現(xiàn)出隨機性。
這兩種性質也就是上面我們所說的同質性和弱連接。

2. Navigable Small World

可導航小世界的原理很簡單，其基本原理如下圖所示:

[圖片上傳失敗...(image-f07fbb-1602403656206)]

在NSW算法中通過構建一個小世界網(wǎng)絡，希望通過黑色相似的近鄰邊來檢索最近鄰節(jié)點，
通過紅色長邊(高速公路)來實現(xiàn)不同類節(jié)點之間的快速檢索。

這里我們不妨考慮一下，為什么regular graph不能做近鄰檢索? 為什么random graph不能做近鄰檢索，為什么small world
可以用來做近鄰檢索?

2.1 圖的檢索

在了解完NSW的基本思路之后，接下來我們看一下NSW當中，如何對整個圖中的節(jié)點查找K個最近鄰節(jié)點。

K 近鄰查找

在NSW中K近鄰檢索的過程如下:

隨機選擇1個元素，放入到candidates當中

從candidates中選取最近鄰節(jié)點c，將這些元素的鄰居節(jié)點放置到q當中

從candidates中移除最近鄰節(jié)點c

如果c的距離遠大于result中的第k個節(jié)點，跳出循環(huán)

否則，對于c的每個鄰居節(jié)點，遍歷其鄰居，如果沒有在visited set里面。

將e加入到visited set， candidates， tempRes

遍歷完成candidate中所有的節(jié)點后，把tempRes的結果傳入到result

重復執(zhí)行上述步驟m遍, 返回result中最優(yōu)的k個近鄰結果。

具體的偽代碼描述如下:

K-NNSearch(object q,integer:m,k)
1   TreeSet[object]tempRes, candidates, visitedSet, result
2   for(i<-0; i<m; i++) do:
3       put random entry point in candidates
4       tempRes<-null
5       repeat:
6           get element c closest from candidates to q
7           remove c from candidates
8           #checks to p condition:
9           if c is further than k-th element from result
10          than break repeat
11          #update list of candidates:
12          for every element e from friends of c do:
13              if e is not in visited Set than
14                  add e to visited Set, candidates, tempRes
15
16      end repeat
17      #aggregate the results:
18      add objects from tempRes to result
19  end for
20  return best k elements from result

2.2 圖的構建

基于NSW的原理，我們希望NSW的局部節(jié)點之間的在距離上具有同質性(也就是近鄰節(jié)點能夠相互連接)。從而使得當我們檢索
到一個近鄰節(jié)點時，其大部分近鄰節(jié)點都是近鄰節(jié)點。同時也希望保留一些隨機邊，能夠在不同區(qū)域之間快速跳轉。

那么我們需要怎么樣構建一個，具有同質性同時又具備隨機性的小世界網(wǎng)絡呢？

Delaunay 三角剖分

為了使得相鄰的點在空間距離上相近，我們引入Delaunay三角剖分，相關的定義如下

Delaunay 邊

在點集 $V$ 中存在兩點 $a$ 和 $b$ ，圈內不包含點集 $V$ 中的任何其他點。這個特質被稱為空圈特質個。
節(jié)點 $a$ 和節(jié)點 $b$ 連接起來的邊稱為Delaunay邊。

Delaunay 三角剖分

如果一個點集 $V$ 的三角剖分 $T$ 都只包含 Delaunay邊，那么該三角剖分稱為Delaunay剖分。

[圖片上傳失敗...(image-90a97d-1602403656206)]

NSW節(jié)點的插入

構建圖的時候，理論上來說我們對所有的點做Delaunay三角剖分，然后添加一些隨機的長邊構建快速檢索通道，
就構建了一個可導航的小世界網(wǎng)絡。

由于構建Delaunay三角剖分的復雜度太高實際的代碼實現(xiàn)過程中是通過節(jié)點隨機插入來引入隨機性，利用已有節(jié)點構建Delaunay邊來引入同質性。

NSW的網(wǎng)絡構建過程如下:

在候選節(jié)點 $V$ 里面隨機挑選一個節(jié)點 $v_i$
將節(jié)點 $v_i$ 插入到已經(jīng)構建好的圖中，并構建邊。
邊構建的規(guī)則：找到節(jié)點 $v_i$ 最近鄰的 $f$ 個鄰居，建立 $v_i$ 和這些鄰居的邊連接。

對應的偽代碼如下:

Nearest_Neighbor_Insert(object: new_object,integer:f, integer:w)
1 SET[object]:neighbors<-k-NNSearch (new_object, w, f);
2 for(i<-0; i<f; i++) do
3   neighbors[i].connect(new_object);
4   new_object.connect(neighbors[i]);

在構建NSW圖結構的時候，在局部通過尋找 $f$ 個最近鄰來建立類似于Delaunay三角剖分的結構，
在全局通過隨機順序插入，引入隨機邊從而使得所以具備可導航小世界的特性。

3. Hierarchical Navigable Small World

在NSW中，構建圖的階段通過節(jié)點的隨機插入來引入隨機性，構建出一個類似于小世界的網(wǎng)絡結構。在NSW中很明顯地會存在
幾個問題。

對于最先插入的節(jié)點，其連接的鄰居節(jié)點，基本都比較遠(弱連接屬性較強)
對于最后插入的節(jié)點，其連接的鄰居節(jié)點，基本都比較近(弱連接屬性較弱)
對于具有聚類效應的點，由于后續(xù)插入的點可能都和其建立連接，對應節(jié)點的度可能會比較高。

等等

如果繼承NSW基于long link快速檢索，short link具有聚類特性的思想。怎么樣能夠使得查找更為穩(wěn)定，
或者怎么樣能夠把long link的查找和short link查找有效區(qū)分。在此基礎上引入了分層圖的思想。

基于這些問題在NSW的基礎上我們來看一下HNSW。

在這里插入圖片描述

根據(jù)上圖可以直接看出HNSW在NSW基礎上所作的優(yōu)化。

在HNSW中，引入Layers的概念，總體思想如下:

在Layer = 0 層中，包含了連通圖中所有的點。
隨著層數(shù)的增加，每一層的點數(shù)逐漸減少并且遵循指數(shù)衰減定律
圖節(jié)點的最大層數(shù)，由隨機指數(shù)概率衰減函數(shù)決定。
從某個點所在的最高層往下的所有層中均存在該節(jié)點。
在對HNSW進行查詢的時候，從最高層開始檢索。

3.1 HNSW的查詢

在HNSW的查詢階段，包括以下幾個算法。

SEACHER-LAYER: 在指定層查詢K個最近鄰節(jié)點。
SELECT-NEIGHBORS-SIMPLE: 簡單的查找某一層最近的鄰居節(jié)點。
SELECT-NEIGHBORS-HEURISTIC: 探索式查找某一層最近的鄰居節(jié)點。
K-NN-SEARCH: 從所有候選結果中找出K個最近鄰結果。

接下來，我們來具體看一下這幾個算法和對應的具體查詢邏輯。

3.1.1 SEACHER-LAYER

算法偽代碼

在這里插入圖片描述

傳入?yún)?shù)

q:表示需要查找的節(jié)點

eq: 固定的起始節(jié)點，如果Layer是最頂層，有固定的入口節(jié)點。如果不是最頂層則是上一層查詢到的最近鄰。

ef: 查找的鄰居節(jié)點數(shù)目

lc: 查詢的層數(shù)

輸出 :

q元素最近鄰的ef個節(jié)點。

功能:

SEARCH LAYER算法的功能是在給定一個節(jié)點q和起始查詢節(jié)點eq、查詢的層lc的情況下，查找出
節(jié)點q在層lc下的ef個最近鄰。

查詢步驟：

首先根據(jù)ep 初始化visited set V, candidate set C, 以及動態(tài)最近鄰W

當 candidate set 不為空的時候執(zhí)行:

2.1) 從candidate set C中選取離q最近的點c,

2.2) 從動態(tài)最近鄰中選取最遠的點f,

2.3) 比較distance(c,q)和distance(f,q)

2.4) 如果distance(c,q) > distance(f,q)執(zhí)行步驟 3 否則繼續(xù)執(zhí)行 2.5

2.5) 對在lc層中c節(jié)點的每個鄰居e。如果e在visited中，重新執(zhí)行步驟 2, 否則繼續(xù)執(zhí)行 2.6

2.6) 將e節(jié)點加入visited set

2.7) 從W中獲取最遠的節(jié)點f

2.8) 如果distance(e,q) < distance(f,q) 或者 |W| < ef 將 e分別加入 candidate set C和動態(tài)最近鄰W

2.9) 如果 |W| > ef 移除最大元素。

返回集合W

3.1.2 SELECT-NEIGHBORS

在select neighbors主要分為兩個部分由SELECT-NEIGHBORS-SIMPLE以及SELECT-NEIGHBORS-HEURISTIC兩個算法組成。

SELECT-NEIGHBORS-SIMPLE和SELECT-NEIGHBORS-HEURISTIC兩個算法都是用在圖構建的過程中，而不用在KNN的近鄰
檢索，與SIMPLE不同HEURISTIC方法添加了更多的隨機性，從而同一層節(jié)點之間的連接隨機性更強。

SELECT-NEIGHBORS-SIMPLE

算法偽代碼

[圖片上傳失敗...(image-44c55a-1602403656206)]

參數(shù)輸入

q:表示需要查詢的節(jié)點。

C:表示查詢的候選節(jié)點集合。

M:表示返回最近鄰居的個數(shù)。

輸出

q在C中的M個最近鄰居

功能

選取出節(jié)點q在候選集C中的M個最近鄰居。

SELECT-NEIGHBORS-HEURISTIC

算法偽代碼

在這里插入圖片描述

參數(shù)輸入

q:表示我們需要查詢的節(jié)點

C:表示candidate 節(jié)點

M:表示返回的最近鄰節(jié)點的個數(shù)M

lc:表示返回的層的編號

extendCandidates:表示是否需要擴展candidate

keepPrunedConnection:表示是否需要把廢棄節(jié)點加入到返回結果中

返回結果

通過探索式查找返回最近鄰的M個結果。

3.1.3 K-NN-SEACHER

KNN查詢的邏輯很簡單，從固定的enter節(jié)點進入，在頂層開始檢索。
在每一層檢索到唯一一個最近鄰然后作為下一層入口節(jié)點。最后在底層檢索top K個最相似節(jié)點。

算法偽代碼

在這里插入圖片描述

3.2 HNSW的插入

在HNSW中，通過插入算法來構建整個圖結構并在此基礎上進行檢索。HNSW的插入算法如下。

算法偽代碼

在這里插入圖片描述

算法參數(shù)

hnsw: 節(jié)點所需要插入的目標圖結構
q: 需要插入的節(jié)點
M: 每個節(jié)點需要與其他節(jié)點建立的連接數(shù)，也就是節(jié)點的度。
efConstruction: 用來設置查詢網(wǎng)絡節(jié)點集合的動態(tài)大小
mL: 用來選擇節(jié)點q的層數(shù)的時候所需要用到的歸一化因子。

算法輸出

插入節(jié)點q后的hnsw網(wǎng)絡結構。

節(jié)點插入過程

在整個HNSW的insert的過程中包含以下幾個部分。

初始化當前最近鄰集合W，初始化固定節(jié)點ep，獲取頂層編號L，獲取新插入節(jié)點的層l

對于屬于L->l+1的每一層查找出q的最近鄰節(jié)點。

對于lc <- min(L,l)..0的每一層執(zhí)行以下步驟:

3.1) 每一層查找出最近的efConstruction個節(jié)點得到集合M。

3.2) 在每個節(jié)點中查找到最近的M個neighbors。(采用算法3,或者算法4)

3.2) 將在層lc中的所有neighbors和節(jié)點q建立連接。

3.3) 對于neighbors中的每個節(jié)點e重新判斷一下節(jié)點個數(shù)，然后減少e節(jié)點的鄰居節(jié)點重新建立連接。

如果 l > L，將q設置為hnsw的enter point

在上述偽代碼中對于每個新節(jié)點而言獲取器layer id的公式如下。

$l = \lfloor -ln(unif(0,1)) \cdot mL \rfloor$

HNSW通過一個隨機函數(shù)，將所有的點劃分到不同層次，越往上節(jié)點數(shù)越少，邊越少。這種情況下節(jié)點和節(jié)點之間尋找最近鄰居的
距離也就越遠。因此在從上到小檢索的過程中，先通過Long Link找到全局可能的最近節(jié)點，然后往下層以該節(jié)點為入口
進一步做局部檢索。

4 總結

在這篇文章中，主要介紹了NSW和HNSW的算法原理。NSW算法基于六度分離理論將小世界的特性用于近鄰檢索，
提出了基于圖結構的檢索方案。

在NSW的基礎上，HNSW利用多層的圖結構來完成圖的構建和檢索，使得通過將節(jié)點隨機劃分到不同的layer，
從上層圖到下層圖的檢索中，越往下層節(jié)點之間的距離越近, 隨機性也越差，聚類系數(shù)越高。
HNSW通過從上到下的檢索，完成了NSW中Long Link高速公路快速檢索的作用，通過最后底層的近鄰檢索，
完成局部最近鄰的查找。