Annoy — 優(yōu)秀的”鄰近搜索”解決方案

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

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

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

開始之前，你要確保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

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

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

f = 40
t = AnnoyIndex(f, 'angular') # 用于存儲(chǔ)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 棵樹，查詢時(shí)，樹越多，精度越高。
t.save('test.ann')

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

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

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 個(gè) item 的n個(gè)最近鄰的item。在查詢期間，它將檢索多達(dá)search_k（默認(rèn)n_trees * n）個(gè)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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í)行，在建立之后無需保存）。

我們的文章到此就結(jié)束啦，如果你喜歡今天的Python 實(shí)戰(zhàn)教程，請持續(xù)關(guān)注Python實(shí)用寶典。

有任何問題，可以在公眾號后臺(tái)回復(fù)：加群，回答相應(yīng)紅字驗(yàn)證信息，進(jìn)入互助群詢問。

原創(chuàng)不易，希望你能在下面點(diǎn)個(gè)贊和在看支持我繼續(xù)創(chuàng)作，謝謝！

點(diǎn)擊下方閱讀原文可獲得更好的閱讀體驗(yàn)

Python實(shí)用寶典 (pythondict.com)
不只是一個(gè)寶典
歡迎關(guān)注公眾號：Python實(shí)用寶典