<jupyter_start><jupyter_text>BanditPAM: Almost Linear-Time k-Medoids Clustering This repo contains a high-performance implementation of BanditPAM from https://arxiv.org/abs/2006.06856. The code can be called directly from Python or C++.If you use this software, please cite:<NAME>, <NAME>, <NAME>, <NAME>, <NAME>, <NAME>. "Bandit-PAM: Almost Linear Time k-medoids Clustering via Multi-Armed Bandits" Neural Information Processing Systems (NeurIPS) 2020.<jupyter_code>@inproceedings{BanditPAM,
  title={Bandit-PAM: Almost Linear Time k-medoids Clustering via Multi-Armed Bandits},
  author={<NAME>, <NAME> and <NAME>, <NAME>, <NAME>, Ilan},
  booktitle={Advances in Neural Information Processing Systems},
  pages={368--374}, #TODO: Fix this
  year={2020}
}<jupyter_output><empty_output><jupyter_text>Python Quickstart  Install the repo and its dependencies:<jupyter_code>/BanditPAM/: pip install -r requirements.txt
/BanditPAM/: sudo pip install .<jupyter_output><empty_output><jupyter_text>Example 1: Synthetic data from a Gaussian Mixture Model<jupyter_code>from BanditPAM import KMedoids
import numpy as np
import matplotlib.pyplot as plt

# Generate data from a Gaussian Mixture Model with the given means:
np.random.seed(0)
n_per_cluster = 40
means = np.array([[0,0], [-5,5], [5,5]])
X = np.vstack([np.random.randn(n_per_cluster, 2) + mu for mu in means])

# Fit the data with BanditPAM:
kmed = KMedoids(n_medoids = 3, algorithm = "BanditPAM")
kmed.fit(X, 'L2')

# Visualize the data and the medoids:
for p_idx, point in enumerate(X):
    if p_idx in map(int, kmed.final_medoids):
        plt.scatter(X[p_idx, 0], X[p_idx, 1], color='red', s = 40)
    else:
        plt.scatter(X[p_idx, 0], X[p_idx, 1], color='blue', s = 10)
plt.show()<jupyter_output><empty_output><jupyter_text>Example 2: MNIST and its medoids visualized via t-SNE<jupyter_code>from BanditPAM import KMedoids
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.manifold import TSNE

# Load the 1000-point subset of MNIST and calculate its t-SNE embeddings for visualization:
X = pd.read_csv('data/MNIST-1k.csv', sep=' ', header=None).to_numpy()
X_tsne = TSNE(n_components = 2).fit_transform(X)

# Fit the data with BanditPAM:
kmed = KMedoids(n_medoids = 10, algorithm = "BanditPAM")
kmed.fit(X, 'L2')

# Visualize the data and the medoids via t-SNE:
for p_idx, point in enumerate(X):
    if p_idx in map(int, kmed.final_medoids):
        plt.scatter(X_tsne[p_idx, 0], X_tsne[p_idx, 1], color='red', s = 40)
    else:
        plt.scatter(X_tsne[p_idx, 0], X_tsne[p_idx, 1], color='blue', s = 5)
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12575757575757576, 'fraction_numerical': 0.023106060606060606, 'mean_word_length': 5.22877358490566, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 28, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '652814', 'license': 'MIT', 'n_tokens_mistral': 1029, 'n_tokens_neox': 952, 'n_words': 277, 'path': 'README.ipynb', 'repo_name': 'dhaval737/BanditPAM', 'size': '2744'}