NearPy是一個Python框架，用于使用不同的局部敏感散列方法在高維向量空間中進行快速（近似）最近鄰搜索。
你可以使用NearPy去進行試驗和評估新的（研究）方法，但也可以直接用于實際應用。NearPy配有一個redis存儲適配器。
要安裝它，只需執行 pip install NearPy。它還將安裝scipy，numpy和redis。
現在支持密集和稀疏（scipy.sparse）向量。
點擊此處了解更多信息：http://pixelogik.github.io/NearPy/

(文中向量和矢量是同一個意思，都翻譯于vector)

原理

為了找到查詢向量的近似最近鄰居，首先索引要存儲的向量。對于應該被索引（’存儲’）的每個向量，生成散列，即字符串值。該散列用作存儲向量的后備數據單元的鍵。在大多數情況下，后備數據單元只是一個系列的向量，后備數據單元是在這種應用下使用的術語。
這樣生成的后備數據單元（bucket）的鍵（即向量散列值）對于查找查詢向量的最近鄰居沒有任何用處。因此，NearPy實現近似最近鄰算法的機制的“秘密”是使用所謂的一些局部敏感哈希函數—LSH。這些局部敏感哈希函數考慮了空間性，因此它們傾向于為近似向量生成相同的散列值（后備數據的鍵）。這使得在給定查詢向量的情況下獲得接近向量的速度非常快。因為這是一種非常粗略的方法，所以它被稱為近似最近鄰搜索，因為您可能無法獲得真正的最近鄰居。在許多應用程序中這是很好的一種折中方式，因為你只想得到20個“足夠相等”的向量。

Engine — 發動機

使用NearPy時，您將主要通過配置和使用Engine對象來完成此操作。Engines是可配置的管道，用于使用局部敏感哈希（LSH）進行近似最近鄰搜索（ANNS）。

使用構造函數配置Engine，該構造函數接受管道中的不同組件：

def __init__（self，dim，lshashes = [RandomBinaryProjections（' default '，10）]，distance = CosineDistance（），vector_filters = [NearestFilter（10）]，storage = MemoryStorage（））：

ANNS管道配置為特征空間的固定維度，可以使用構造函數的dim參數設置。dim必須是正整數值。
Engine可以使用多個局部敏感哈希函數LSH，可以通過lshashes參數中設置，該參數必須是LSHash對象的數組。
根據查詢期間使用的過濾器類型，可以指定距離度量。只有在使用需要距離的過濾器（如 NearestFilter 或 DistanceThresholdFilter）時才需要指定距離度量。
在查詢最近鄰居期間，過濾器用于最后一步。現有的實現是NearestFilter，DistanceThresholdFilter和UniqueFilter。
fetch_vector_filters是Engine構造函數的另一個參數，它是在從后備數據單元(Buckets)中提取候選矢量(vector)之后和使用距離或矢量濾波器之前執行的。默認情況下，該參數是一個UniqueFilter，并且該參數應該始終是UniqueFilter。將這個參數作為保留，萬一以后有特殊的用途。
Engine 支持多種索引向量（和后備數據單元）的存儲方式。當前的存儲實現是MemoryStorage和RedisStorage。
引擎有兩種主要方法：

store_vector（self，v，data = None） neighbours（self，v）

store_vector() 使用所有已配置的LSH對向量v進行哈希處理，并將其(向量v)存儲在哈希結果相匹配的后備數據單元（Bucket）中 (每個哈希結果對應一個后備數據單元Bucket?)。可選的data參數必須是JSON可序列化的。它與向量一起存儲，并將在搜索結果中返回。最佳做法是僅將數據庫ID用作附加的“data”，并將實際數據存儲在數據庫中。
neighbors() 使用所有配置的局部敏感哈希函數對向量v進行哈希計算，利用哈希的結果從后備數據單元中取出所有匹配的候選向量，應用距離函數（可選）和過濾函數（可選）構造返回的列表（向量，數據，距離） ）元組或（向量，數據）元組。
要從引擎中刪除索引向量及其數據，可以使用以下兩種方法：

clean_all_buckets（self） clean_buckets（self，hash_name）

Hashed — 哈希

NearPy中的所有LSH實現都是繼承于nearpy.hashes.LSHash，除了構造函數和重置方法之外，它還有一個主要方法。

hash_vector（self，v）

hash_vector（） 函數計算指定的向量的哈希并返回包含一個或多個條目的后備數據庫鍵。
LSH RandomBinaryProjections將特定向量投影到特征空間中的n個隨機歸一化向量，并返回由’0’和’1’組成的字符串。如果向量v位于第n個法向量的正側，則字符串中的第n個字符為’1’，如果v位于其負側，則字符串中的第n個字符為’0 ”。這樣，LSH將特征空間（“輸入空間”）的每個可能向量投影到許多可能的后備數據單元中。
LSH RandomDiscretizedProjections幾乎與RandomBinaryProjections完全相同。唯一的區別是，即將投影值除以bin寬度，并使用每個隨機投影中的bin索引作為bucket key（后備存儲單元）的一部分。給定與RandomBinaryProjections相同的隨機投影向量計數，這會在給定相同向量集的情況下產生更多Bucket(后備存儲單元)。Bucket的密度可以由bin寬度控制，bin寬度是構造器的一部分。
使用構造函數指定的向量訓練集訓練LSH PCABinaryProjections。構造函數執行PCA（主成分分析）以找到訓練集中最高方差的方向。然后，它使用前n個主成分作為投影向量（或投影到子空間的維度）。這個想法是，這使得在桶之間獲得良好的向量分布更加安全。我對此沒有任何測試，也不知道這是否有意義。
LSH PCADiscretizedProjections是RandomDiscretizedProjections的pca版本，不使用隨機向量，而是訓練集的前n個主成分，就像PCABinaryProjections的做法一樣。

Hash configurations — 哈希配置

要在Redis中保存索引并在索引過程完成后重新使用它，您應該保持哈希配置 ，以便之后可以重新創建相同的引擎以進行更多索引或查詢。
示例代碼如下：

# Create redis storage adapter redis_object = Redis(host='localhost', port=6379, db=0) redis_storage = RedisStorage(redis_object)# Get hash config from redis config = redis_storage.load_hash_configuration('MyHash')if config is None:# Config is not existing, create hash from scratch, with 10 projectionslshash = RandomBinaryProjections('MyHash', 10) else:# Config is existing, create hash with None parameterslshash = RandomBinaryProjections(None, None)# Apply configuration loaded from redislshash.apply_config(config)# Create engine for feature space of 100 dimensions and use our hash. # This will set the dimension of the lshash only the first time, not when # using the configuration loaded from redis. Use redis storage to store # buckets. engine = Engine(100, lshashes=[lshash], storage=redis_storage)# Do some stuff like indexing or querying with the engine...# Finally store hash configuration in redis for later use redis_storage.store_hash_configuration(lshash)

===========
Example usage:

from nearpy import Engine from nearpy.hashes import RandomBinaryProjections# Dimension of our vector space dimension = 500# Create a random binary hash with 10 bits rbp = RandomBinaryProjections('rbp', 10)# Create engine with pipeline configuration engine = Engine(dimension, lshashes=[rbp])# Index 1000000 random vectors (set their data to a unique string) for index in range(100000):v = numpy.random.randn(dimension)engine.store_vector(v, 'data_%d' % index)# Create random query vector query = numpy.random.randn(dimension)# Get nearest neighbours N = engine.neighbours(query)

============

本文翻譯自NearPy的 README.md，翻譯 By ysg
如果翻譯的有不當的地方，請評論區指出，共同進步。

總結

以上是生活随笔為你收集整理的了解NearPy，进行快速最近邻搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。