Skip to content

Latest commit

 

History

History
103 lines (57 loc) · 7.7 KB

how-to-choose-the-best-nearest-neighbors-algorithm-8d75d42b16ab.md

File metadata and controls

103 lines (57 loc) · 7.7 KB
Raw

如何选择最佳最近邻算法

原文：https://pub.towardsai.net/how-to-choose-the-best-nearest-neighbors-algorithm-8d75d42b16ab?source=collection_archive---------1-----------------------

机器学习，意见

一种数据驱动的方法，用于在您的自定义数据集上选择最快、最准确的人工神经网络算法

最快最准确的。来源

ANN 背景

在我之前的帖子里，KNN 死了！】，我比较了一个名为HNSW的人工神经网络算法和sklearn's KNN，证明了 HNSW 具有非常优越的性能，速度提高了 380 倍，同时提供了 99.3%的相同结果。

为了让事情更有趣，有几个人工神经网络算法，如

  1. Spotify 的惹恼了
  2. 谷歌的 ScaNN
  3. 脸书的失败
  4. 我个人最喜欢的:层次可导航小世界图 HNSW
  5. 还有更多

作为一名数据科学家，我非常支持做出数据驱动的决策，正如我在如何选择最佳的 Keras 预训练模型中提到的。因此，在这篇文章中，我将展示一种数据驱动的方法，通过使用优秀的[ann-benchmarks](https://github.com/erikbern/ann-benchmarks) GitHub 库来决定哪种人工神经网络算法是定制数据集的最佳选择。

人工神经网络基准

[ann-benchmarks](https://github.com/erikbern/ann-benchmarks)代码通过绘制每个算法的Recall与Queries per second.来比较多个人工神经网络算法。这样，您可以直观地选择最快(每秒查询数)的算法，同时提供最小的期望召回。我们选择 Recall 作为感兴趣的度量，因为我们想知道 ANN [ 精度和 Recall ]检索到的真实最近邻的百分比。

来源:维基百科上的沃尔伯

下图是使用angular距离度量在glove-100数据集上运行 ANN-Benchmarks 得到的图表。在这个数据集上，scann算法在任何给定的Recall都有最高的Queries per second，因此是这个数据集上最好的算法。

使用角距离度量在 glove-100 数据集上的 ANN 基准。来源

设置

这些是在自定义数据集上运行 ann-benchmarks 代码所涉及的步骤。

  1. 在 python 3.6 环境中安装 ann 基准。
  2. 将您的自定义嵌入数据帧上传到ann-benchmarks/data目录。
  3. 更新ann-benchmarks/ann-benchmarks/dataset.py以读取和分割新的定制嵌入数据帧。
  4. 运行基准测试代码。
  5. 绘制结果，瞧！最佳算法会出现在你面前。

1.在 python 3.6 环境中安装人工神经网络基准

这个步骤的代码需要在您的Terminal中执行。我使用 anaconda 进行环境设置。这将需要几分钟才能完成。您可以通过使用— proc参数增加并发进程的数量来加快速度。我故意在安装完成后才升级pandas and scipy。

重要！截至本文撰写之时，Ann-benchmarks 仅支持 Python 3.6。

潜在问题:

  1. gcc未安装:使用sudo apt-get install gcc安装 GCC。
  2. Docker未安装:根据此链接的说明安装 Docker。请记住选择正确的发行版。
  3. 权限问题:如果您在运行python install.py时遇到任何权限问题，只需使用sudo /opt/conda/envs/ann/bin/python install.py运行即可。当您使用sudo时，记得在您的ann环境中提供 anaconda python 的完整路径。

2.上传您的自定义嵌入数据框架

在此步骤中，您可以将自定义数据框文件粘贴到ann-benchmarks/data目录中。对于这篇文章，我的数据框架是相同的[ 亚马逊产品数据集 ]，具有我在上一篇文章中使用的 FastText 句子嵌入:KNN(K-Nearest Neighbors)死了！ 但我只是随机抽取了 50K 行，以确保基准测试在合理的时间内运行。下面是将嵌入数据框保存为 pickle 文件custom-euclidean.pkl的代码，该文件位于正确的目录中，同时也是数据框前 5 行的摘录。

自定义数据集的前 5 行。来源

3.更新datasets.py来处理您的自定义数据帧

我们需要更新 ANN 基准代码，以了解如何处理我们的新数据框架。我们通过在ann-benchmarks/ann-benchmarks/datasets.py文件的末尾添加一个新的函数和字典元素来做到这一点。距离参数允许的选项是"euclidean", "angular", "hamming" or "jaccard"。距离度量的选择取决于您的问题。对于我的情况，我发现“欧几里得”提供了良好的最近邻。

4.运行基准代码

如果到目前为止一切顺利，我们现在可以简单地通过从您的Terminal调用下面的行来运行基准测试。将parallelism的值更改为您想要使用的 CPU 内核数。我使用的是 16 核 CPU，所以我选择parallelism=14为其他任务保留 2 核。这将需要一些时间来完成。我的 50K 行数据框架在 20%测试集下运行了大约 7 个小时。

5.标绘结果

一旦运行完成，我们可以通过运行plot.py来绘制结果。我们还可以启用 y 轴以log比例绘图。注意这里我使用了sudo和我的 Anaconda Python 的完整路径，因为我在正常运行 plot.py 时遇到了权限问题:python plot.py --dataset=custom-euclidean --y-log。你可以用任何适合你的。

结果图作为 png 文件保存在results目录中。对于我在本文中使用的 50K 行亚马逊数据集，结果如下。

在我们的自定义数据集上，多个人工神经网络算法的每秒召回数与查询数。来源

从这个图中，我们看到一些算法，如NGT-onng, hnsw(nmslib), n2, hnswlib, SW-graph(nmslib)明显比其他算法好，在任何给定的召回中每秒提供更高的查询。因此，我们可以在亚马逊产品数据集上进一步探索这些算法。

结论

总之，通过使用ann-benchmarks，并组合一些额外的代码，我们可以在我们自己的定制数据集上测试大量的人工神经网络算法，以缩小几个人工神经网络算法的范围，供进一步研究。这篇文章的所有代码都可以在我的 Github 库中找到。感谢您的阅读！

下一步是什么？如果你想在“大数据”上部署 HNSW ANN，你可以在 Docker 容器中使用 Elasticsearch

[## 基于 Docker 弹性搜索的近似最近邻

将人工神经网络扩展到上亿

medium.com](https://medium.com/towards-artificial-intelligence/approximate-nearest-neighbors-on-elastic-search-with-docker-15342153f22a)

编辑 1:将代码片段转换成 GitHub gists