如何在python中使用spotify的annoy库？

Question

我想知道 annoy 库是如何工作的。我从 github 得到了这个测试代码，但我是编码新手，所以我很难理解 .

from annoy import AnnoyIndex
import random
f = 40

t = AnnoyIndex(f, 'angular')  #Length of item vector that will be indexed
for i in range(1000):
    v = [random.gauss(0, 1) for z in range(f)]
    t.add_item(i, v)

t.build(10) # 10 trees
t.save('test.ann')

u = AnnoyIndex(f, 'angular')
u.load('test.ann') # super fast, will just mmap the file
print(u.get_nns_by_item(0, 1000)) # will find the 1000 nearest neighbors

Answer 1

annoy 库主要用于解决欧几里德距离、曼哈顿距离、余弦距离、汉明距离或点（内）积距离的最近邻搜索（NNS）问题。使用 Annoy，您将在一个维度空间中构建一个由点或向量组成的网络，然后要求它为您提供这个给定网络的不同属性。使用这个库的优点之一是它在内存存储方面特别高效。你可以用它做很多事情，它会变得像你想要的那样复杂，但这里有一个简单的例子可能会有所帮助。

a = AnnoyIndex(3, 'euclidean')
b = AnnoyIndex(3 ,'angular')

在这里，您首先创建 Annoy 包将在其上运行的对象。第一种情况是具有欧氏距离的三维空间。第二个有一个有角的。

a.add_item(0,[1,0,0])
a.add_item(1,[0,1,0])
a.add_item(2,[2,0,0])
a.add_item(3,[2.5,0,0])
a.add_item(4,[1,0,0.5])

b.add_item(0,[1,0,0]) 
b.add_item(1,[0,1,0])
b.add_item(2,[2,0,0])
b.add_item(3,[2.5,0,0])
b.add_item(4,[1,0,0.5])

a.build(1)
b.build(1)

在这里，我分别在对象 a 和 b 的相同位置添加相同的五个项目，然后使用 a/b.build(n) 构建网络，其中 n 是使用的“树”的数量。树越多，网络在执行操作时就越精确、越快。在这种情况下，我们使用 n=1，因为网络非常简单。

    print(a.get_nns_by_item(0, 4))
    print(b.get_nns_by_item(0, 4))

现在我要求网络给我所有在 0 和 4 之间的网络中的所有元素，从距离项目 0 的近到远列出，使用它们各自的距离，获得 0,4,1,2,3 和 0,2，分别为 3、4、1。现在让我们看看为什么我们会得到这样的结果。在以下几行中，我计算了项目 0 与其他项目之间的距离，然后将它们从小到大排序。

对象 a ，使用欧氏距离的距离 (d((x,y,z),(x',y',z')) = sqrt{( x-x')^2 + (y-y')^2 + (z-z')^2}) ：

'''
    d0-0 = 0 
    d0-1 = sqrt{5/4} 
    d0-2= 1.5 
    d0-3 = 2 
    d0-4 = 1/sqrt{2} 
'''

从小到大排序：d0-0,d0-4,d0-1,d0-2,d0-3（或{0,4,1,2,3}）

对象 b ，使用角距离（两个向量之间的角度，以度为单位）的距离：

'''
    angle0-0 = 0
    angle0-1 = 90
    angle0-2  = 0
    angle0-3 = 0
    angle0-4 = 45
'''

在这种情况下，如果两个元素的角度相同，则排序优先考虑较小的项目：{0,2,3,4,1}

到现在为止还挺好。现在让我们看看你的一段代码。

    from annoy import AnnoyIndex
    import random
    f = 40

    t = AnnoyIndex(f, 'angular')  #Length of item vector that will be indexed
    for i in range(1000):
        v = [random.gauss(0, 1) for z in range(f)]
        t.add_item(i, v)

    t.build(10) # 10 trees
    t.save('test.ann')
    

在第一部分中，我们将网络空间的维数设置为 40，并选择使用角距离。然后，在下一步中，我们创建一千个项目，每个项目都有对应的四十维向量，也可以理解为 40 维空间中的一个点。然后，每个维度的值由 random.gauss(0,1) 设置，它随机返回由 e^{{x}^2/2}/sqrt{2\pi} 给出的高斯分布内的一个点。然后我们使用 10 棵树构建相应的网络并将其保存为“test.ann”。

u = AnnoyIndex(f, 'angular')
u.load('test.ann') # super fast, will just mmap the file
    
    

现在我们可以下载它并用于我们想要的任何目的，它的优点是已经建立了网络，因此速度更快。

print(u.get_nns_by_item(0, 1000)) 

现在我们想要得到按其相对于第 0 项的角距离排序的千个元素。请注意，如果我们输入较小的数字而不是 1000，则大于该数字的项目将自动丢弃。

有关最近邻搜索的更多信息：

https://en.wikipedia.org/wiki/Nearest_neighbor_search

Github 烦人包

https://github.com/spotify/annoy