Skip to main content

BanditPAM: A state-of-the-art, high-performance k-medoids algorithm.

Project description

Quickstart

Run pip install banditpam and then check out the examples.

If you use this software, please cite: Mo Tiwari, Martin Jinye Zhang, James Mayclin, Sebastian Thrun, Chris Piech, Ilan Shomorony. “BanditPAM: Almost Linear Time k-medoids Clustering via Multi-Armed Bandits” Advances in Neural Information Processing Systems (NeurIPS) 2020.

Introduction

Clustering algorithms are ubiquitous in modern data science applications. Compared to the commonly used k-means clustering, k-medoids clustering requires the cluster centers to be actual datapoints and supports arbitrary dissimilarity functions in addition to standard distance metrics. This enables greater interpretability of the cluster centers and the clustering of structured objects. Despite these advantages, k-medoids clustering has been far less popular than k-means due to its computational cost. We present BanditPAM, a randomized algorithm inspired by techniques from multi-armed bandits, that scales almost linearly with dataset size and runs significantly faster than prior algorithms while still matching the best prior algorithms in clustering quality. Prior k-medoids algorithms such as PAM and FastPAM scale quadratically in the dataset size and are significantly slower than k-means, which scales linearly in dataset size. This algorithm, BanditPAM, almost matches k-means in complexity and is significantly faster than prior state-of-the-art with runtime O(nlogn).

Details

In this package, we provide a high-performance implementation of BanditPAM, a state-of-the-art k-medoids algorithm. BanditPAM:

  • matches the best prior work in clustering quality but scales as O(nlogn) instead of O(n^2) in each iteration, and

  • supports arbitrary dissimilarity functions between points – these functions need not even be proper metrics

This implementation is written in C++ for performance, but is callable from Python via Python bindings. The algorithm is empirically validated on several large, real-word datasets with a reduction in the number of distance evaluations of up to 200x while returning the same results as prior state-of-the-art.

Further Reading

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

banditpam-4.0.1.tar.gz (179.4 kB view hashes)

Uploaded Source

Built Distributions

banditpam-4.0.1-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.6 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-pp39-pypy39_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (3.5 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

banditpam-4.0.1-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.6 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-pp38-pypy38_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (3.5 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

banditpam-4.0.1-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (3.6 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-pp37-pypy37_pp73-manylinux_2_17_i686.manylinux2014_i686.whl (3.5 MB view hashes)

Uploaded PyPy manylinux: glibc 2.17+ i686

banditpam-4.0.1-cp311-cp311-musllinux_1_1_x86_64.whl (11.8 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

banditpam-4.0.1-cp311-cp311-musllinux_1_1_i686.whl (11.3 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ i686

banditpam-4.0.1-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (11.5 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-cp311-cp311-manylinux_2_17_i686.manylinux2014_i686.whl (11.3 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ i686

banditpam-4.0.1-cp311-cp311-macosx_11_0_arm64.whl (231.0 kB view hashes)

Uploaded CPython 3.11 macOS 11.0+ ARM64

banditpam-4.0.1-cp311-cp311-macosx_10_14_x86_64.whl (13.7 MB view hashes)

Uploaded CPython 3.11 macOS 10.14+ x86-64

banditpam-4.0.1-cp311-cp311-macosx_10_14_universal2.whl (13.9 MB view hashes)

Uploaded CPython 3.11 macOS 10.14+ universal2 (ARM64, x86-64)

banditpam-4.0.1-cp310-cp310-musllinux_1_1_x86_64.whl (11.7 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

banditpam-4.0.1-cp310-cp310-musllinux_1_1_i686.whl (11.3 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ i686

banditpam-4.0.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (11.5 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-cp310-cp310-manylinux_2_17_i686.manylinux2014_i686.whl (11.2 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ i686

banditpam-4.0.1-cp310-cp310-macosx_11_0_arm64.whl (230.9 kB view hashes)

Uploaded CPython 3.10 macOS 11.0+ ARM64

banditpam-4.0.1-cp310-cp310-macosx_10_14_x86_64.whl (13.7 MB view hashes)

Uploaded CPython 3.10 macOS 10.14+ x86-64

banditpam-4.0.1-cp310-cp310-macosx_10_14_universal2.whl (13.9 MB view hashes)

Uploaded CPython 3.10 macOS 10.14+ universal2 (ARM64, x86-64)

banditpam-4.0.1-cp39-cp39-musllinux_1_1_x86_64.whl (11.7 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

banditpam-4.0.1-cp39-cp39-musllinux_1_1_i686.whl (11.3 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ i686

banditpam-4.0.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (11.5 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-cp39-cp39-manylinux_2_17_i686.manylinux2014_i686.whl (11.2 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ i686

banditpam-4.0.1-cp39-cp39-macosx_11_0_arm64.whl (231.1 kB view hashes)

Uploaded CPython 3.9 macOS 11.0+ ARM64

banditpam-4.0.1-cp39-cp39-macosx_10_14_x86_64.whl (13.7 MB view hashes)

Uploaded CPython 3.9 macOS 10.14+ x86-64

banditpam-4.0.1-cp39-cp39-macosx_10_14_universal2.whl (13.9 MB view hashes)

Uploaded CPython 3.9 macOS 10.14+ universal2 (ARM64, x86-64)

banditpam-4.0.1-cp38-cp38-musllinux_1_1_x86_64.whl (11.7 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

banditpam-4.0.1-cp38-cp38-musllinux_1_1_i686.whl (11.3 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ i686

banditpam-4.0.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (11.5 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-cp38-cp38-manylinux_2_17_i686.manylinux2014_i686.whl (11.2 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ i686

banditpam-4.0.1-cp38-cp38-macosx_11_0_arm64.whl (230.7 kB view hashes)

Uploaded CPython 3.8 macOS 11.0+ ARM64

banditpam-4.0.1-cp38-cp38-macosx_10_14_x86_64.whl (13.7 MB view hashes)

Uploaded CPython 3.8 macOS 10.14+ x86-64

banditpam-4.0.1-cp38-cp38-macosx_10_14_universal2.whl (13.9 MB view hashes)

Uploaded CPython 3.8 macOS 10.14+ universal2 (ARM64, x86-64)

banditpam-4.0.1-cp37-cp37m-musllinux_1_1_x86_64.whl (12.0 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ x86-64

banditpam-4.0.1-cp37-cp37m-musllinux_1_1_i686.whl (11.5 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ i686

banditpam-4.0.1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (11.6 MB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-cp37-cp37m-manylinux_2_17_i686.manylinux2014_i686.whl (11.4 MB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ i686

banditpam-4.0.1-cp37-cp37m-macosx_10_14_x86_64.whl (13.7 MB view hashes)

Uploaded CPython 3.7m macOS 10.14+ x86-64

banditpam-4.0.1-cp36-cp36m-musllinux_1_1_x86_64.whl (11.7 MB view hashes)

Uploaded CPython 3.6m musllinux: musl 1.1+ x86-64

banditpam-4.0.1-cp36-cp36m-musllinux_1_1_i686.whl (11.2 MB view hashes)

Uploaded CPython 3.6m musllinux: musl 1.1+ i686

banditpam-4.0.1-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (11.3 MB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ x86-64

banditpam-4.0.1-cp36-cp36m-manylinux_2_17_i686.manylinux2014_i686.whl (11.1 MB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ i686

banditpam-4.0.1-cp36-cp36m-macosx_10_14_x86_64.whl (13.7 MB view hashes)

Uploaded CPython 3.6m macOS 10.14+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page