.. image:: doc/pynndescent_logo.png :width: 600 :align: center :alt: PyNNDescent 标志

.. image:: https://dev.azure.com/TutteInstitute/build-pipelines/_apis/build/status%2Flmcinnes.pynndescent?branchName=master :target: https://dev.azure.com/TutteInstitute/build-pipelines/_build?definitionId=17 :alt: Azure Pipelines 构建状态 .. image:: https://readthedocs.org/projects/pynndescent/badge/?version=latest :target: https://pynndescent.readthedocs.io/en/latest/?badge=latest :alt: 文档状态

=========== PyNNDescent

PyNNDescent 是一个用于近似最近邻搜索的 Python 最近邻下降算法。它提供了一个用于 k 近邻图构建和近似最近邻搜索的 Python 实现，基于以下论文：

Dong, Wei, Charikar Moses, and Kai Li. "Efficient k-nearest neighbor graph construction for generic similarity measures." Proceedings of the 20th international conference on World wide web. ACM, 2011.

该库通过使用随机投影树进行初始化来补充这种方法。这对于适合这种方法的度量（欧几里得、闵可夫斯基、角度、余弦等）特别有用。还会执行图多样化，剪除图中任何三角形的最长边。

目前，该库的目标是实现相对高精度（80%-100%准确率）的近似最近邻搜索。

为什么使用 PyNNDescent？

PyNNDescent 提供快速的近似最近邻查询。根据 ann-benchmarks <https://github.com/erikbern/ann-benchmarks>_ 系统的评测，它在顶级 ANN 库中表现出色：

SIFT-128 欧几里得距离

.. image:: https://pynndescent.readthedocs.io/en/latest/_images/sift.png :alt: SIFT 128 数据集的 ANN 基准性能

NYTimes-256 角度距离

.. image:: https://pynndescent.readthedocs.io/en/latest/_images/nytimes.png :alt: NYTimes 256 数据集的 ANN 基准性能

虽然 PyNNDescent 是最快的 ANN 库之一，但它也易于安装（可通过 pip 和 conda 安装），没有平台或编译问题，并且非常灵活，默认支持多种距离度量：

闵可夫斯基类型度量

欧几里得距离
曼哈顿距离
切比雪夫距离
闵可夫斯基距离

其他空间度量

堪培拉距离
布雷-柯蒂斯距离
半正矢距离

归一化空间度量

马哈拉诺比斯距离
加权闵可夫斯基距离
标准化欧几里得距离

角度和相关性度量

余弦距离
点积
相关系数
斯皮尔曼等级相关系数
TSSS
真实角度

概率度量

赫林格距离
瓦瑟斯坦距离

二进制数据度量

汉明距离
杰卡德距离
戴斯系数
拉塞尔-劳距离
库尔辛斯基系数
罗杰斯-塔尼莫托系数
索卡尔-米切纳系数
索卡尔-斯尼思系数
尤尔系数

同时还支持自定义距离度量，并保持良好的性能。

PyNNDescent 还与 Scikit-learn 集成良好，包括为使用最近邻计算的算法提供 KNeighborTransformer 的替代实现。

如何使用 PyNNDescent

PyNNDescent 旨在提供非常简单的接口。它类似于（但功能更有限）sklearn 中的 KDTree 和 BallTree。实际上只有两个操作 —— 索引构建和查询索引以获取最近邻。

要在训练数据 data 上构建新的搜索索引，可以这样做：

.. code:: python

from pynndescent import NNDescent
index = NNDescent(data)

然后，您可以使用该索引进行搜索（如果需要，可以将其序列化到磁盘）。要在 pynndescent 索引中搜索测试数据集 query_data 的 15 个最近邻，可以这样做：

.. code:: python

index.query(query_data, k=15)

这就是全部内容。您可以在 文档 <https://pynndescent.readthedocs.org>_ 中找到更多详细信息。

安装

PyNNDescent 设计为易于安装的纯 Python 模块，具有相对轻量级的依赖：

numpy
scipy
scikit-learn >= 0.22
numba >= 0.51

所有这些都可以通过 pip 或 conda 安装。最简单的安装方式应该是通过 conda：

.. code:: bash

conda install -c conda-forge pynndescent

或通过 pip：

.. code:: bash

pip install pynndescent

要手动安装此软件包：

.. code:: bash

wget https://github.com/lmcinnes/pynndescent/archive/master.zip
unzip master.zip
rm master.zip
cd pynndescent-master
python setup.py install

帮助和支持

这个项目仍然很年轻。文档仍在不断完善。同时，请 提出问题 <https://github.com/lmcinnes/pynndescent/issues/new>_，我会尽力提供帮助和指导。请同时查看代码中的文档字符串，其中提供了一些参数说明。

许可证

pynndescent 软件包使用 2-clause BSD 许可证。尽情使用吧。

贡献

欢迎贡献！这里有很多潜在的项目机会，所以如果您想提供帮助，请与我们联系。从代码到笔记本再到示例和文档，一切都同等重要，所以请不要觉得您无法做出贡献。要贡献，请 fork 项目 <https://github.com/lmcinnes/pynndescent/issues#fork-destination-box>_，进行修改并提交拉取请求。我们会尽最大努力解决任何问题，并将您的代码合并到主分支中。