Annoy：用于搜索空間中給定查詢點(diǎn)的近鄰點(diǎn)

Annoy 是由 spotify 開源的一個Python第三方模塊，它能用于搜索空間中給定查詢點(diǎn)的近鄰點(diǎn)。

此外，眾所周知，Python由于GIL的存在，它的多線程最多只能用上一個CPU核的性能。如果你想要做性能優(yōu)化，就必須用上多進(jìn)程。

但是多進(jìn)程存在一個問題，就是所有進(jìn)程的變量都是獨(dú)立的，B進(jìn)程訪問不到A進(jìn)程的變量，因此Annoy為了解決這個問題，增加了一個靜態(tài)索引保存功能，你可以在A進(jìn)程中保存Annoy變量，在B進(jìn)程中通過文件的形式訪問這個變量。

1.準(zhǔn)備

開始之前，你要確保Python和pip已經(jīng)成功安裝在電腦上，如果沒有，可以訪問這篇文章：超詳細(xì)Python安裝指南 進(jìn)行安裝。

**(可選1) **如果你用Python的目的是數(shù)據(jù)分析，可以直接安裝Anaconda：Python數(shù)據(jù)分析與挖掘好幫手—Anaconda，它內(nèi)置了Python和pip.

**(可選2) **此外，推薦大家用VSCode編輯器，它有許多的優(yōu)點(diǎn)：Python 編程的最好搭檔—VSCode 詳細(xì)指南。

請選擇以下任一種方式輸入命令安裝依賴 ：

1. Windows 環(huán)境 打開 Cmd (開始-運(yùn)行-CMD)。
2. MacOS 環(huán)境 打開 Terminal (command+空格輸入Terminal)。
3. 如果你用的是 VSCode編輯器 或 Pycharm，可以直接使用界面下方的Terminal.

pip install annoy

2.基本使用

Annoy使用起來非常簡單，學(xué)習(xí)成本極低。比如我們隨意生成1000個0,1之間的高斯分布點(diǎn)，將其加入到Annoy的索引，并保存為文件:

# 公眾號：Python 實(shí)用寶典
from annoy import AnnoyIndex
import random

f = 40
t = AnnoyIndex(f, 'angular') # 用于存儲f維度向量
for i in range(1000):
    v = [random.gauss(0, 1) for z in range(f)]
    t.add_item(i, v)

t.build(10) # 10 棵樹，查詢時，樹越多，精度越高。
t.save('test.ann')

這樣，我們就完成了索引的創(chuàng)建及落地。Annoy 支持4種距離計(jì)算方式：
"angular"，"euclidean"，"manhattan"，"hamming"，或"dot"，即余弦距離、歐幾里得距離、曼哈頓距離、漢明距離及點(diǎn)乘距離。

接下來我們可以新建一個進(jìn)程訪問這個索引：

from annoy import AnnoyIndex

f = 40
u = AnnoyIndex(f, 'angular')
u.load('test.ann')
print(u.get_nns_by_item(1, 5))
# [1, 607, 672, 780, 625]

其中，**u.get_nns_by_item(i, n, search_k=-1, include_distances=False) **返回第 i 個 item 的n個最近鄰的item。在查詢期間，它將檢索多達(dá)search_k（默認(rèn)n_trees * n）個點(diǎn)。

如果設(shè)置include_distances為True，它將返回一個包含兩個列表的元組，第二個列表中包含所有對應(yīng)的距離。

3.算法原理

構(gòu)建索引 ：在數(shù)據(jù)集中隨機(jī)選擇兩個點(diǎn)，用它們的中垂線來切分整個數(shù)據(jù)集。再隨機(jī)從兩個平面中各選出一個頂點(diǎn)，再用中垂線進(jìn)行切分，于是兩個平面變成了四個平面。以此類推形成一顆二叉樹。當(dāng)我們設(shè)定樹的數(shù)量時，這個數(shù)量指的就是這樣隨機(jī)生成的二叉樹的數(shù)量。所以每顆二叉樹都是隨機(jī)切分的。

查詢方法 ：

1. 將每一顆樹的根節(jié)點(diǎn)插入優(yōu)先隊(duì)列；
2. 搜索優(yōu)先隊(duì)列中的每一顆二叉樹，每一顆二叉樹都可以得到最多 Top K 的候選集；
3. 刪除重復(fù)的候選集；
4. 計(jì)算候選集與查詢點(diǎn)的相似度或者距離；
5. 返回 Top K 的集合。

4.附錄

下面是Annoy的所有函數(shù)方法：

1.** AnnoyIndex(f, metric) **返回可讀寫的新索引，用于存儲f維度向量。metric 可以是 "angular"，"euclidean"，"manhattan"，"hamming"，或"dot"。2. a.add_item(i, v) 用于給索引添加向量v，i 是指第 i 個向量。

3.** a.build(n_trees) ** 用于構(gòu)建 n_trees 的森林。查詢時，樹越多，精度越高。在調(diào)用build后，無法再添加任何向量。

4.** a.save(fn, prefault=False) **將索引保存到磁盤。保存后，不能再添加任何向量。

5.** a.load(fn, prefault=False) ** 從磁盤加載索引。如果prefault設(shè)置為True，它將把整個文件預(yù)讀到內(nèi)存中。默認(rèn)值為False。

6.** a.unload() **釋放索引。

7.** a.get_nns_by_item(i, n, search_k=-1, include_distances=False) **返回第 i 個item的 n 個最近鄰的item。

8.** a.get_nns_by_vector(v, n, search_k=-1, include_distances=False) **與上面的相同，但按向量v查詢。

9. **a.get_item_vector(i) **返回第i個向量。

10.** a.get_distance(i, j) ** 返回向量i和向量j之間的距離。

11.** a.get_n_items() **返回索引中的向量數(shù)。

12.** a.get_n_trees() **返回索引中的樹的數(shù)量。

13.** a.on_disk_build(fn) **用以在指定文件而不是RAM中建立索引（在添加向量之前執(zhí)行，在建立之后無需保存）。