It is a forest of random projection trees

Overview

rpforest

rpforest

CircleCI

rpforest is a Python library for approximate nearest neighbours search: finding points in a high-dimensional space that are close to a given query point in a fast but approximate manner.

rpforest differs from alternative ANN packages such as annoy by not requiring the storage of all the vectors indexed in the model. Used in this way, rpforest serves to produce a list of candidate ANNs for use by a further service where point vectors are stored (for example, a relational database).

How it works

It works by building a forest of N binary random projection trees.

In each tree, the set of training points is recursively partitioned into smaller and smaller subsets until a leaf node of at most M points is reached. Each parition is based on the cosine of the angle the points make with a randomly drawn hyperplane: points whose angle is smaller than the median angle fall in the left partition, and the remaining points fall in the right partition.

The resulting tree has predictable leaf size (no larger than M) and is approximately balanced because of median splits, leading to consistent tree traversal times.

Querying the model is accomplished by traversing each tree to the query point's leaf node to retrieve ANN candidates from that tree, then merging them and sorting by distance to the query point.

Installation

  1. Install numpy first.
  2. Install rpforest using pip: pip install rpforest

Usage

Fitting

Model fitting is straightforward:

from rpforest import RPForest

model = RPForest(leaf_size=50, no_trees=10)
model.fit(X)

The speed-precision tradeoff is governed by the leaf_size and no_trees parameters. Increasing leaf_size leads the model to produce shallower trees with larger leaf nodes; increasing no_trees fits more trees.

In-memory queries

Where the entire set of points can be kept in memory, rpforest supports in-memory ANN queries. After fitting, ANNs can be obtained by calling:

nns = model.query(x_query, 10)

Return nearest neighbours for vector x by first retrieving candidate NNs from x's leaf nodes, then merging them and sorting by cosine similarity with x. At most no_trees * leaf_size NNs will can be returned.

Candidate queries

rpforest can support indexing and candidate ANN queries on datasets larger than would fit in available memory. This is accomplished by first fitting the model on a subset of the data, then indexing a larger set of data into the fitted model:

from rpforest import RPForest

model = RPForest(leaf_size=50, no_trees=10)
model.fit(X_train)

model.clear()  # Deletes X_train vectors

for point_id, x in get_x_vectors():
     model.index(point_id, x)

nns = model.get_candidates(x_query, 10)

Model persistence

Model persistence is achieved simply by pickling and unpickling.

model = pickle.loads(pickle.dumps(model))

Performance

Erik Bernhardsson, the author of annoy, maintains an ANN performance shootout repository, comparing a number of Python ANN packages.

On the GloVe cosine distance benchmark, rpforest is not as fast as highly optimised C and C++ packages like FLANN and annoy. However, it far outerpforms scikit-learn's LSHForest and panns.

Performance

Development

Pull requests are welcome. To install for development:

  1. Clone the rpforest repository: git clone [email protected]:lyst/rpforest.git
  2. Install it for development using pip: cd rpforest && pip install -e .
  3. You can run tests by running python setupy.py test.

When making changes to the .pyx extension files, you'll need to run python setup.py cythonize in order to produce the extension .cpp files before running pip install -e ..

Comments
  • Is rpforest supports custom similarity/distance function

    Is rpforest supports custom similarity/distance function

    hi, @maciejkula , According to your paper titled "Metadata Embeddings for User and Item Cold-start Recommendations", lyst generate recommendation using lightfm and some kind of ANN algorithm. So I came to rpforest in lyst's repository and I think maybe that's exactly the ANN. Now Suppose that we have trained a lightfm model, include embeddings and bias. It seems that it is still hard to rapidly generate top-k recommendation using rpforest, Since as Readme said, rpforest is based on cosine similarity, however, the score for a user-item pair in lightfm is the sum of a dot product of two embeddings and two bias. So my question is:

    Is rpforest supports custom similarity/distance function, or some other way can achieve top-k recommendation?

    thanks jianyi

    opened by hiyijian 10
  • Compile error when installing rpforest

    Compile error when installing rpforest

    In file included from rpforest/rpforest_fast.cpp:271:
    
    In file included from /usr/local/lib/python2.7/site-packages/numpy/core/include/numpy/arrayobject.h:4:
    
    In file included from /usr/local/lib/python2.7/site-packages/numpy/core/include/numpy/ndarrayobject.h:17:
    
    In file included from /usr/local/lib/python2.7/site-packages/numpy/core/include/numpy/ndarraytypes.h:1804:
    
    /usr/local/lib/python2.7/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: "Using deprecated NumPy API, disable it by "          "#defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-W#warnings]
    
    #warning "Using deprecated NumPy API, disable it by " \
    
     ^
    
    rpforest/rpforest_fast.cpp:5727:28: error: no member named 'shrink_to_fit' in 'std::vector<int, std::allocator<int> >'
    
        __pyx_v_node->indices->shrink_to_fit();
    
        ~~~~~~~~~~~~~~~~~~~~~  ^
    
    rpforest/rpforest_fast.cpp:5940:28: error: no member named 'shrink_to_fit' in 'std::vector<int, std::allocator<int> >'
    
        __pyx_v_node->indices->shrink_to_fit();
    
        ~~~~~~~~~~~~~~~~~~~~~  ^
    
    1 warning and 2 errors generated.
    
    error: command 'gcc' failed with exit status 1
    
    opened by delip 10
  • Does windows support the libs

    Does windows support the libs

    In win7 environment, when i install rpforest ,i met the problem. i use vs2015. the complie error informatios: C:\Users\juine\AppData\Local\Programs\Common\Microsoft\Visual C++ for Python \9.0\VC\Bin\cl.exe /c logo /Ox /MD /W3 /GS- /DNDEBUG -ID:\Python27\lib\site-p ackages\numpy\core\include -ID:\Python27\include -ID:\Python27\PC /Tprpforest/rp forest_fast.cpp /Fobuild\temp.win32-2.7\Release\rpforest/rpforest_fast.obj -ffas t-math cl : Command line warning D9002 : ignoring unknown option '-ffast-math' rpforest_fast.cpp d:\python27\lib\site-packages\numpy\core\include\numpy\npy_1_7_deprecated_ap i.h(12) : Warning Msg: Using deprecated NumPy API, disable it by #defining NPY_N O_DEPRECATED_API NPY_1_7_API_VERSION rpforest/rpforest_fast.cpp(271) : fatal error C1083: Cannot open include fil e: 'stdint.h': No such file or directory error: command 'C:\Users\juine\AppData\Local\Programs\Common\Microsof t\Visual C++ for Python\9.0\VC\Bin\cl.exe' failed with exit status 2

    opened by juine 4
  • C++ error with python 3.5

    C++ error with python 3.5

    Hello, I'm trying to fir an rpforet module on a big matrix (3000000 x 300) in python 3.5 on OS X 10.11 and I get the following error:

    Traceback (most recent call last):
      File "rpforest_test.py", line 29, in <module>
        index.fit(model.syn0)
      File "/usr/local/lib/python3.5/site-packages/rpforest/rpforest.py", line 81, in fit
        tree.make_tree(self._X)
      File "rpforest/rpforest_fast.pyx", line 237, in rpforest.rpforest_fast.Tree.make_tree (rpforest/rpforest_fast.cpp:3896)
    ValueError: Buffer dtype mismatch, expected 'double' but got 'float'
    
    opened by w4nderlust 2
  • Errors installing rpforest in conda environment on Mac OS X

    Errors installing rpforest in conda environment on Mac OS X

    OS/compiler details:

    OS X version: 10.11.2 (El Capitan)

    $ clang --version
    Apple LLVM version 7.0.2 (clang-700.1.81)
    Target: x86_64-apple-darwin15.2.0
    Thread model: posix
    

    gcc is an alias for clang.

    Installing rpforest in a fresh virtualenv environment works fine:

    $ mkvirtualenv rpfenv
    ... python 3.4 env built ...
    (rpfenv)$ pip install numpy
    ... numpy 1.10.2 installed ...
    (rpfenv)$ pip install rpforest
    ... rpforest 1.1 installed ...
    

    rpforest_fast was compiled successfully with:

    clang -Wno-unused-result -fno-common -dynamic -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -I/Users/dsc/.virtualenvs/rpfenv/lib/python3.4/site-packages/numpy/core/include -I/usr/local/Cellar/python3/3.4.3_2/Frameworks/Python.framework/Versions/3.4/include/python3.4m -c rpforest/rpforest_fast.cpp -o build/temp.macosx-10.10-x86_64-3.4/rpforest/rpforest_fast.o -std=c++11
    

    Trying to do the same in a conda environment results in compilation errors however:

    $ conda create -n rpfenv2 python=3.4
    ... python 3.4 env built ...
    $ source activate rpfenv2
    (rpfenv2)$ pip install numpy
    ... numpy 1.10.2 installed ...
    (rpfenv2)$ pip install rpforest
    

    rpforest 1.1 is downloaded, but compilation fails. Compilation command:

    clang -fno-strict-aliasing -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -I/Users/dsc/miniconda3/envs/rpfenv2/include -arch x86_64 -I/Users/dsc/miniconda3/envs/rpfenv2/lib/python3.4/site-packages/numpy/core/include -I/Users/dsc/miniconda3/envs/rpfenv2/include/python3.4m -c rpforest/rpforest_fast.cpp -o build/temp.macosx-10.5-x86_64-3.4/rpforest/rpforest_fast.o -std=c++11
    

    Compiler errors:

      In file included from rpforest/rpforest_fast.cpp:271:
      In file included from /Users/dsc/miniconda3/envs/rpfenv2/lib/python3.4/site-packages/numpy/core/include/numpy/arrayobject.h:4:
      In file included from /Users/dsc/miniconda3/envs/rpfenv2/lib/python3.4/site-packages/numpy/core/include/numpy/ndarrayobject.h:18:
      In file included from /Users/dsc/miniconda3/envs/rpfenv2/lib/python3.4/site-packages/numpy/core/include/numpy/ndarraytypes.h:1781:
      /Users/dsc/miniconda3/envs/rpfenv2/lib/python3.4/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: "Using deprecated NumPy API, disable it by "          "#defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-W#warnings]
      #warning "Using deprecated NumPy API, disable it by " \
       ^
      rpforest/rpforest_fast.cpp:5727:28: error: no member named 'shrink_to_fit' in 'std::vector<int, std::allocator<int> >'
          __pyx_v_node->indices->shrink_to_fit();
          ~~~~~~~~~~~~~~~~~~~~~  ^
      rpforest/rpforest_fast.cpp:5940:28: error: no member named 'shrink_to_fit' in 'std::vector<int, std::allocator<int> >'
          __pyx_v_node->indices->shrink_to_fit();
          ~~~~~~~~~~~~~~~~~~~~~  ^
      1 warning and 2 errors generated.
      error: command 'clang' failed with exit status 1
    
    opened by davechallis 1
  • label points that are being fit()

    label points that are being fit()

    I'm not sure if the implementation already supports this, but is it possible assign a label with every point with fit(), so when there is a query, I can identify the neighbors by the labels?

    opened by delip 1
  • CircleCI 2.0, tox, py35+ tests and support

    CircleCI 2.0, tox, py35+ tests and support

    Decided to use tox, so that you can:

    • run tests locally in multiple python versions
    • have a consistent testing platform across CI and local environment

    Also:

    • updated readme
    • refactored setup.py ... made it not a fatal exception if python setup.py is run without an installed numpy
    • fixed flake8 issues
    • black-ified code
    • fixed tests code to support py35+
    • updated cpp library with the latest cython 0.29.14 (previously 0.23.4)
    opened by iserko 0
  • Reuse hyperplanes

    Reuse hyperplanes

    This PR makes all interior nodes of a tree at a given depth now use the same projection hyperplane. This drastically reduces the memory footprint of the tree without affecting the guarantees of the data structure (which relies on the hyperplanes being independently drawn _ between_ the trees in the forest).

    opened by maciejkula 0
  • Raising error when tree already exists

    Raising error when tree already exists

    Referencing https://github.com/lyst/rpforest/blob/master/rpforest/rpforest.py#L59

    The tree already exists, so is there a way to handle this gracefully instead of raising an error?

    opened by RitwikGupta 0
Owner
Lyst
Your World of Fashion
Lyst
Laporan Proyek Machine Learning - Azhar Rizki Zulma

Laporan Proyek Machine Learning - Azhar Rizki Zulma Project Overview Domain proyek yang dipilih dalam proyek machine learning ini adalah mengenai hibu

Azhar Rizki Zulma 6 Mar 12, 2022
Optimal Randomized Canonical Correlation Analysis

ORCCA Optimal Randomized Canonical Correlation Analysis This project is for the python version of ORCCA algorithm. It depends on Numpy for matrix calc

Yinsong Wang 1 Nov 21, 2021
scikit-multimodallearn is a Python package implementing algorithms multimodal data.

scikit-multimodallearn is a Python package implementing algorithms multimodal data. It is compatible with scikit-learn, a popul

12 Jun 29, 2022
A classification model capable of accurately predicting the price of secondhand cars

The purpose of this project is create a classification model capable of accurately predicting the price of secondhand cars. The data used for model building is open source and has been added to this

Akarsh Singh 2 Sep 13, 2022
Course files for "Ocean/Atmosphere Time Series Analysis"

time-series This package contains all necessary files for the course Ocean/Atmosphere Time Series Analysis, an introduction to data and time series an

Jonathan Lilly 107 Nov 29, 2022
A simple python program which predicts the success of a movie based on it's type, actor, actress and director

Movie-Success-Prediction A simple python program which predicts the success of a movie based on it's type, actor, actress and director. The program us

Mahalinga Prasad R N 1 Dec 17, 2021
This jupyter notebook project was completed by me and my friend using the dataset from Kaggle

ARM This jupyter notebook project was completed by me and my friend using the dataset from Kaggle. The world Happiness 2017, which ranks 155 countries

1 Jan 23, 2022
Tools for Optuna, MLflow and the integration of both.

HPOflow - Sphinx DOC Tools for Optuna, MLflow and the integration of both. Detailed documentation with examples can be found here: Sphinx DOC Table of

Telekom Open Source Software 17 Nov 20, 2022
About Solve CTF offline disconnection problem - based on python3's small crawler

About Solve CTF offline disconnection problem - based on python3's small crawler, support keyword search and local map bed establishment, currently support Jianshu, xianzhi,anquanke,freebuf,seebug

天河 32 Oct 25, 2022
An open source framework that provides a simple, universal API for building distributed applications. Ray is packaged with RLlib, a scalable reinforcement learning library, and Tune, a scalable hyperparameter tuning library.

Ray provides a simple, universal API for building distributed applications. Ray is packaged with the following libraries for accelerating machine lear

23.3k Dec 31, 2022
LinearRegression2 Tvads and CarSales

LinearRegression2_Tvads_and_CarSales This project infers the insight that how the TV ads for cars and car Sales are being linked with each other. It i

Ashish Kumar Yadav 1 Dec 29, 2021
A collection of interactive machine-learning experiments: 🏋️models training + 🎨models demo

🤖 Interactive Machine Learning experiments: 🏋️models training + 🎨models demo

Oleksii Trekhleb 1.4k Jan 06, 2023
PyHarmonize: Adding harmony lines to recorded melodies in Python

PyHarmonize: Adding harmony lines to recorded melodies in Python About To use this module, the user provides a wav file containing a melody, the key i

Julian Kappler 2 May 20, 2022
Toolkit for building machine learning models that generalize to unseen domains and are robust to privacy and other attacks.

Toolkit for Building Robust ML models that generalize to unseen domains (RobustDG) Divyat Mahajan, Shruti Tople, Amit Sharma Privacy & Causal Learning

Microsoft 149 Jan 06, 2023
Dieses Projekt ermöglicht es den Smartmeter der EVN (Netz Niederösterreich) über die Kundenschnittstelle auszulesen.

SmartMeterEVN Dieses Projekt ermöglicht es den Smartmeter der EVN (Netz Niederösterreich) über die Kundenschnittstelle auszulesen. Smart Meter werden

greenMike 43 Dec 04, 2022
Summer: compartmental disease modelling in Python

Summer: compartmental disease modelling in Python Summer is a Python-based framework for the creation and execution of compartmental (or "state-based"

6 May 13, 2022
YouTube Spam Detection with python

YouTube Spam Detection This code deletes spam comment on youtube videos based on two characteristics (currently) If the author of the comment has a se

MohamadReza Taalebi 5 Sep 27, 2022
mlpack: a scalable C++ machine learning library --

a fast, flexible machine learning library Home | Documentation | Doxygen | Community | Help | IRC Chat Download: current stable version (3.4.2) mlpack

mlpack 4.2k Jan 01, 2023
Practical Time-Series Analysis, published by Packt

Practical Time-Series Analysis This is the code repository for Practical Time-Series Analysis, published by Packt. It contains all the supporting proj

Packt 325 Dec 23, 2022
healthy and lesion models for learning based on the joint estimation of stochasticity and volatility

health-lesion-stovol healthy and lesion models for learning based on the joint estimation of stochasticity and volatility Reference please cite this p

5 Nov 01, 2022