学习散列最大内积搜索
sitq的Python项目详细描述
SITQ是一种近似最大内积搜索的快速算法。 它能找到在次线性时间内对查询最大化内积的项目。
台阶标记
推荐是SITQ可以使用的领域之一。 实验使用movielens 100k数据集和movielens 20m数据集进行。
使用benfred/implicit中的als来学习项和用户的向量，其中（用户，项）对的得分通过这些向量的内积计算。 precision@10是针对测试数据集的正确建议的比率。 取数项是计算内积的项。 散列算法更可取，因为获取项的平均值和标准偏差较小。
ml-100k
| Name | Precision@10 | Fetched items. Avg | Fetched items. Std |
|---|---|---|---|
| SITQ | 0.202 | 105.2 | 76.6 |
| Simple-LSH | 0.182 | 496.2 | 441.2 |
| ITQ | 0.199 | 131.3 | 93.7 |
| LSH | 0.156 | 161.9 | 94.4 |
| brute force | 0.242 | (1680) |
毫升-20米
| Name | Precision@10 | Fetched items. Avg | Fetched items. Std |
|---|---|---|---|
| SITQ | 0.112 | 96.1 | 151.1 |
| Simple-LSH | 0.122 | 2158.2 | 5246.6 |
| ITQ | 0.090 | 111.0 | 332.9 |
| LSH | 0.069 | 531.3 | 912.2 |
| brute force | 0.151 | (26671) |
算法
sitq是一种简单的lsh[1]和itq[2]相结合的算法。
简单lsh利用了普通lsh的余弦相似性。 为了将lsh用于mips，它在计算其签名之前转换向量。
lsh通过固定的变换矩阵计算签名。 itq从项目向量中学习转换矩阵，以便更好地进行散列。
SITQ利用简单的LSH变换矢量，并通过ITQ学习变换矩阵。
示例
安装
pip install sitq
获得签名
importnumpyasnpfromsitqimportSitq# Create sample datasetitems=np.random.rand(10000,50)query=np.random.rand(50)sitq=Sitq(signature_size=8)# Learn transformation matrixsitq.fit(items)# Get signatures for itemsitem_sigs=sitq.get_item_signatures(items)# Get signature for queryquery_sig=sitq.get_query_signatures([query])[0]
检索项目
importnumpyasnpfromsitqimportMips# Create sample datasetitems=np.random.rand(10000,50)query=np.random.rand(50)mips=Mips(signature_size=8)# Learn lookup table and parameters for searchmips.fit(items)# Find items which are likely to maximize inner product against queryitem_indexes,scores=mips.search(query,limit=10,distance=1)
参考文献
| [1] | Neyshabur, Behnam, and Nathan Srebro. “On symmetric and asymmetric LSHs for inner product search.” arXiv preprint arXiv:1410.5518 (2014). |
| [2] | Gong, Yunchao, et al. “Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval.” IEEE Transactions on Pattern Analysis and Machine Intelligence 35.12 (2013): 2916-2929. |
欢迎加入QQ群-->： 979659372
