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
Turning images into '9-pan' palettes using KMeans clustering from sklearn.

img2palette Turning images into '9-pan' palettes using KMeans clustering from sklearn. Requirements We require: Pillow, for opening and processing ima

Samuel Vidovich 2 Jan 01, 2022
XAI - An eXplainability toolbox for machine learning

XAI - An eXplainability toolbox for machine learning XAI is a Machine Learning library that is designed with AI explainability in its core. XAI contai

The Institute for Ethical Machine Learning 875 Dec 27, 2022
PyPOTS - A Python Toolbox for Data Mining on Partially-Observed Time Series

A python toolbox/library for data mining on partially-observed time series, supporting tasks of forecasting/imputation/classification/clustering on incomplete multivariate time series with missing va

Wenjie Du 179 Dec 31, 2022
MLR - Machine Learning Research

Machine Learning Research 1. Project Topic 1.1. Exsiting research Benmark: https://paperswithcode.com/sota ACL anthology for NLP papers: http://www.ac

Charles 69 Oct 20, 2022
This handbook accompanies the course: Machine Learning with Hung-Yi Lee

This handbook accompanies the course: Machine Learning with Hung-Yi Lee

RenChu Wang 472 Dec 31, 2022
Open-Source CI/CD platform for ML teams. Deliver ML products, better & faster. ⚡️🧑‍🔧

Deliver ML products, better & faster Giskard is an Open-Source CI/CD platform for ML teams. Inspect ML models visually from your Python notebook 📗 Re

Giskard 335 Jan 04, 2023
A library of sklearn compatible categorical variable encoders

Categorical Encoding Methods A set of scikit-learn-style transformers for encoding categorical variables into numeric by means of different techniques

2.1k Jan 07, 2023
A naive Bayes model for cancer classification using a set of documents

Naivebayes text classifcation model for cancer and noncancer documents Author: Alex King Purpose Requirements/files included How to use 1. Purpose The

Alex W King 1 Nov 24, 2021
Accelerating model creation and evaluation.

EmeraldML A machine learning library for streamlining the process of (1) cleaning and splitting data, (2) training, optimizing, and testing various mo

Yusuf 0 Dec 06, 2021
ClearML - Auto-Magical Suite of tools to streamline your ML workflow. Experiment Manager, MLOps and Data-Management

ClearML - Auto-Magical Suite of tools to streamline your ML workflow Experiment Manager, MLOps and Data-Management ClearML Formerly known as Allegro T

ClearML 4k Jan 09, 2023
QML: A Python Toolkit for Quantum Machine Learning

QML is a Python2/3-compatible toolkit for representation learning of properties of molecules and solids.

176 Dec 09, 2022
A Python library for choreographing your machine learning research.

A Python library for choreographing your machine learning research.

AI2 270 Jan 06, 2023
Projeto: Machine Learning: Linguagens de Programacao 2004-2001

Projeto: Machine Learning: Linguagens de Programacao 2004-2001 Projeto de Data Science e Machine Learning de análise de linguagens de programação de 2

Victor Hugo Negrisoli 0 Jun 29, 2021
Convoys is a simple library that fits a few statistical model useful for modeling time-lagged conversions.

Convoys is a simple library that fits a few statistical model useful for modeling time-lagged conversions. There is a lot more info if you head over to the documentation. You can also take a look at

Better 240 Dec 26, 2022
Microsoft 5.6k Jan 07, 2023
Xeasy-ml is a packaged machine learning framework.

xeasy-ml 1. What is xeasy-ml Xeasy-ml is a packaged machine learning framework. It allows a beginner to quickly build a machine learning model and use

9 Mar 14, 2022
A machine learning web application for binary classification using streamlit

Machine Learning web App This is a machine learning web application for binary classification using streamlit options this application contains 3 clas

abdelhak mokri 1 Dec 20, 2021
Land Cover Classification Random Forest

You can perform Land Cover Classification on Satellite Images using Random Forest and visualize the result using Earthpy package. Make sure to install the required packages and such as

Dr. Sander Ali Khowaja 1 Jan 21, 2022
Turns your machine learning code into microservices with web API, interactive GUI, and more.

Turns your machine learning code into microservices with web API, interactive GUI, and more.

Machine Learning Tooling 2.8k Jan 02, 2023
A single Python file with some tools for visualizing machine learning in the terminal.

Machine Learning Visualization Tools A single Python file with some tools for visualizing machine learning in the terminal. This demo is composed of t

Bram Wasti 35 Dec 29, 2022