### Install Dependencies

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Installs all necessary Python packages for building the documentation. This should be run before building.

```bash
pip install -r requirements.txt
```

--------------------------------

### Install EVoC from Source

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/installation.md

Clone the repository and install the latest development version of EVoC using pip in editable mode.

```bash
git clone https://github.com/TutteInstitute/evoc.git
cd evoc
pip install -e .
```

--------------------------------

### Install EVōC using pip

Source: https://github.com/tutteinstitute/evoc/blob/main/README.rst

Installs the EVōC library from the Python Package Index (PyPI). This is the recommended method for most users.

```bash
pip install evoc
```

--------------------------------

### Install EVōC from Source

Source: https://github.com/tutteinstitute/evoc/blob/main/README.rst

Installs the latest version of EVōC directly from its GitHub repository. Use this if you need the most recent features or want to contribute.

```bash
pip install git+https://github.com/TutteInstitute/evoc.git
```

--------------------------------

### Development Installation of EVoC

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/installation.md

Install EVoC from source with additional dependencies required for development, documentation, and testing.

```bash
git clone https://github.com/TutteInstitute/evoc.git
cd evoc
pip install -e ".[dev,docs,test]"
```

--------------------------------

### Benchmark setup and execution loop

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Sets up a list of algorithms to benchmark, defines the scaling parameters, and iterates through dataset sizes and runs to collect timing and ARI results. Be aware that this loop can take a significant amount of time to complete.

```python
algorithms = [
    ("UMAP + HDBSCAN",    lambda X: umap_hdbscan(X)),
    ("Sklearn KMeans",          lambda X: kmeans(X, n_clusters=n_clusters, kmeans_algorithm="elkan")),
    ("FAISS KMeans",    lambda X: faiss_kmeans(X, n_clusters=n_clusters)),
    ("Sklearn Minibatch KMeans",lambda X: minibatch_kmeans(X, n_clusters=n_clusters)),
    ("EVoC",            lambda X: EVoC(X)),
]

scaling_results = {"size": [], "time": [], "algorithm": [], "ari": []}
n_runs = 4

for size in np.logspace(4, 6.5, num=8):
    for n in range(n_runs):
        n_clusters = int(2 * np.sqrt(size))
        blobs, labels = make_blobs(n_samples=int(size), n_features=1024, centers=n_clusters, cluster_std=3.0)
    
        for name, fn in algorithms:
            start_time = time.time()
            clusters = fn(blobs)
            scaling_results["size"].append(size)
            scaling_results["algorithm"].append(name)
            scaling_results["time"].append(time.time() - start_time)
            scaling_results["ari"].append(sklearn.metrics.adjusted_rand_score(labels, clusters))

scaling_df = pd.DataFrame(scaling_results)
```

--------------------------------

### Install EVoC in Development Mode

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Installs the EVoC package in editable mode, which is required for the documentation build process to correctly reference the package.

```bash
pip install -e ../..
```

--------------------------------

### Build HTML Documentation

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Manually builds the HTML version of the documentation using Sphinx. This command should be run after installing dependencies and the package.

```bash
make html
```

--------------------------------

### Quick Start: Initialize and Fit EVoC

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/index.md

Demonstrates basic usage of the EVoC class for clustering high-dimensional embedding vectors. Requires numpy for data generation.

```python
from evoc import EVoC
import numpy as np

# Generate sample data
X = np.random.rand(1000, 512)  # 1000 samples, 512-dimensional embeddings

# Initialize and fit the clusterer
clusterer = EVoC()
labels = clusterer.fit_predict(X)

# Access cluster layers and membership strengths
print(f"Number of clusters: {len(np.unique(labels[labels >= 0]))}")
print(f"Number of cluster layers: {len(clusterer.cluster_layers_)}")
```

--------------------------------

### Verify EVoC Installation

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/installation.md

Run this Python script to check if EVoC is installed correctly and to perform a basic clustering test. Note that Numba JIT compilation may cause a delay on the first run.

```python
import evoc
print(evoc.__version__)

# Run a quick test
from evoc import EVoC
import numpy as np

X = np.random.rand(100, 10)
clusterer = EVoC()
labels = clusterer.fit_predict(X)
print(f"Clustering completed successfully! Found {len(np.unique(labels[labels >= 0]))} clusters.")
```

--------------------------------

### Run Documentation Doctests

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Executes any embedded doctests within the documentation source files. This helps verify that code examples in the documentation are correct.

```bash
make doctest
```

--------------------------------

### EVoC with Quantized Embeddings (int8)

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/quickstart.md

This example shows how to prepare and use int8 quantized embeddings with EVoC, which utilizes quantized cosine distance.

```python
from sklearn.preprocessing import normalize, StandardScaler
import numpy as np

# Example embedding data (assuming blob_data is available and normalized)
# embeddings = normalize(blob_data)

# For quantized embeddings (int8)
X_quantized = (StandardScaler().fit_transform(embeddings) * 127).astype(np.int8)
labels_quantized = EVoC().fit_predict(X_quantized)
```

--------------------------------

### Load CIFAR-100 Dataset

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Loads the CIFAR-100 dataset embeddings and targets from Huggingface datasets. Ensure the 'datasets' library is installed.

```python
from datasets import load_dataset
```

--------------------------------

### EVoC with Binary Embeddings (uint8)

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/quickstart.md

This example demonstrates using packed uint8 binary embeddings with EVoC, which employs bitwise Jaccard distance.

```python
from sklearn.preprocessing import normalize, StandardScaler
import numpy as np

# Example embedding data (assuming blob_data is available and normalized)
# embeddings = normalize(blob_data)

# For binary embeddings (packed uint8)
X_binary = np.packbits(embeddings > 0.0, axis=1)
labels_binary = EVoC().fit_predict(X_binary)
```

--------------------------------

### Clustering CLIP Embeddings

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/examples.md

Example of generating embeddings using CLIP and then clustering them with EVoC. Requires PyTorch and CLIP libraries. Adjust EVoC parameters for optimal clustering.

```python
import torch
import clip
from evoc import EVoC

# Load CLIP model
device = "cuda" if torch.cuda.is_available() else "cpu"
model, preprocess = clip.load("ViT-B/32", device=device)

# Generate embeddings for images
# (assuming you have a list of PIL images)
embeddings = []
with torch.no_grad():
    for image in images:
        image_input = preprocess(image).unsqueeze(0).to(device)
        embedding = model.encode_image(image_input)
        embeddings.append(embedding.cpu().numpy())

X = np.vstack(embeddings)

# Cluster the embeddings
clusterer = EVoC(
    n_neighbors=20,
    noise_level=0.6,
    base_min_cluster_size=3
)
labels = clusterer.fit_predict(X)
```

--------------------------------

### EVoC with Float Embeddings (Cosine Distance)

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/quickstart.md

This example demonstrates how to use EVoC with standard float32/float64 embeddings, which defaults to using cosine distance for clustering.

```python
from sklearn.preprocessing import normalize, StandardScaler
import numpy as np

# Example embedding data (assuming blob_data is available and normalized)
# embeddings = normalize(blob_data)

# For standard embeddings (float)
X_float = embeddings.astype(np.float32)
labels_cosine = EVoC().fit_predict(X_float)
```

--------------------------------

### Build Documentation (Windows)

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Execute this batch file to build the documentation on Windows. Ensure you are in the 'doc' directory.

```cmd
cd doc
build_docs.bat
```

--------------------------------

### Build Documentation (Unix/macOS)

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Execute this script to build the documentation on Unix-like systems. Ensure you are in the 'doc' directory.

```bash
cd doc
./build_docs.sh
```

--------------------------------

### Live Reload Documentation Build

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Sets up a live-reloading server for the documentation during development. Changes to source files will automatically trigger a rebuild and browser refresh.

```bash
pip install sphinx-autobuild
make livehtml
```

--------------------------------

### bfs_from_hierarchy

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/evoc.cluster_trees.md

Performs a Breadth-First Search (BFS) starting from a hierarchy.

```APIDOC
## evoc.cluster_trees.bfs_from_hierarchy(hierarchy, bfs_root, num_points)

### Description
Performs a Breadth-First Search (BFS) starting from a hierarchy.

### Parameters
- **hierarchy** (object) - The hierarchy structure.
- **bfs_root** (object) - The root node for the BFS.
- **num_points** (int) - The total number of points.
```

--------------------------------

### get_cluster_labelling_at_cut

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/evoc.cluster_trees.md

Gets the cluster labelling at a specific cut in a linkage tree.

```APIDOC
## evoc.cluster_trees.get_cluster_labelling_at_cut(linkage_tree, cut, min_cluster_size)

### Description
Gets the cluster labelling at a specific cut in a linkage tree.

### Parameters
- **linkage_tree** (object) - The linkage tree.
- **cut** (float) - The cut value.
- **min_cluster_size** (int) - The minimum cluster size.
```

--------------------------------

### Basic EVoC Clustering

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/examples.md

Demonstrates the basic usage of EVoC for clustering with random data. Initializes the clusterer and predicts cluster labels.

```python
from evoc import EVoC
import numpy as np

# Simple example with random data
X = np.random.rand(500, 128)
clusterer = EVoC()
labels = clusterer.fit_predict(X)

print(f"Found {len(np.unique(labels[labels >= 0]))} clusters")
```

--------------------------------

### Basic EVōC Clustering

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/quickstart.md

Import EVoC, generate sample embedding data using make_blobs, create an EVoC instance with default parameters, and call fit_predict to obtain cluster labels. Analyze the results by counting unique clusters and noise points.

```python
from evoc import EVoC
from sklearn.datasets import make_blobs
import numpy as np

# Generate sample embedding data
blob_data, blob_labels = make_blobs(n_samples=10_000, n_features=512, centers=256)

# Create and fit the clusterer
clusterer = EVoC()
labels = clusterer.fit_predict(blob_data)

# Analyze results
n_clusters = len(np.unique(labels[labels >= 0]))
n_noise = np.sum(labels == -1)

print(f"Found {n_clusters} clusters")
print(f"Noise points: {n_noise}")
```

--------------------------------

### EVoC Initialization

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/generated/evoc.EVoC.md

Initializes the EVoC clustering model with various parameters to control the clustering process.

```APIDOC
## EVoC Constructor

### Description
Initializes the EVoC clustering model.

### Parameters
- **noise_level** (float, optional) - Default: 0.5. Controls the sensitivity to noise.
- **base_min_cluster_size** (int, optional) - Default: 5. The minimum size of clusters at the base layer.
- **base_n_clusters** (int | None, optional) - Default: None. The number of clusters at the base layer.
- **approx_n_clusters** (int | None, optional) - Default: None. Approximate number of clusters.
- **n_neighbors** (int, optional) - Default: 15. The number of neighbors to consider for graph construction.
- **min_samples** (int, optional) - Default: 5. The minimum number of samples in a neighborhood for a point to be considered a core point.
- **n_epochs** (int, optional) - Default: 50. Number of epochs for training node embeddings.
- **node_embedding_init** (str | None, optional) - Default: 'label_prop'. Method for initializing node embeddings.
- **symmetrize_graph** (bool, optional) - Default: True. Whether to symmetrize the graph.
- **node_embedding_dim** (int | None, optional) - Default: None. Dimension of the node embeddings.
- **neighbor_scale** (float, optional) - Default: 1.0. Scaling factor for neighbor distances.
- **random_state** (int | None, optional) - Default: None. Seed for random number generation.
- **min_similarity_threshold** (float, optional) - Default: 0.2. Minimum similarity threshold for forming clusters.
- **max_layers** (int, optional) - Default: 10. Maximum number of layers in the clustering hierarchy.
- **n_label_prop_iter** (int, optional) - Default: 20. Number of iterations for label propagation.
```

--------------------------------

### Basic EVōC Clustering

Source: https://github.com/tutteinstitute/evoc/blob/main/README.rst

Demonstrates the fundamental usage of the EVoC clusterer, similar to scikit-learn's API. Use this for standard clustering tasks on embedding vectors.

```python
import evoc
from sklearn.datasets import make_blobs

data, _ = make_blobs(n_samples=100_000, n_features=1024, centers=100)

clusterer = evoc.EVoC()
cluster_labels = clusterer.fit_predict(data)
```

--------------------------------

### EVoC Class Initialization and Parameters

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/evoc.clustering.md

This snippet details the initialization of the EVoC class and its various parameters, which control the clustering process, graph construction, and embedding generation.

```APIDOC
## class evoc.clustering.EVoC

Bases: `BaseEstimator`, `ClusterMixin`

Embedding Vector Oriented Clustering for efficient clustering of high-dimensional embedding vectors such as CLIP-vectors, sentence-transformers output, etc. The clustering uses a combination of a node embedding of a nearest neighbour graph, related to UMAP, and a density based clustering approach related to HDBSCAN, improving upon those approaches in efficiency and quality for the specific case of high-dimensional embedding vectors.

### Parameters

* **noise_level** (*float*, *default=0.5*) – The level of noise to consider when clustering.
* **base_min_cluster_size** (*int*, *default=5*) – The minimum size of clusters to consider.
* **base_n_clusters** (*int* or *None*, *default=None*) – The base number of clusters to aim for. If None, it will be estimated.
* **approx_n_clusters** (*int* or *None*, *default=None*) – An approximation of the number of clusters to expect. Used to guide the clustering process.
* **n_neighbors** (*int*, *default=15*) – The number of neighbors to use in the nearest neighbor graph construction.
* **min_samples** (*int*, *default=5*) – The minimum number of samples to use in the density estimation when performing density based clustering on the node embedding.
* **n_epochs** (*int*, *default=50*) – The number of epochs to use when training the node embedding.
* **node_embedding_init** (*str* or *None*, *default='label_prop'*) – The method to use to initialize the node embedding. If None, no initialization will be used. If ‘label_prop’, the label propagation method will be used.
* **symmetrize_graph** (*bool*, *default=True*) – Whether to symmetrize the nearest neighbor graph before using it to construct the node embedding.
* **node_embedding_dim** (*int* or *None*, *default=None*) – The number of dimensions to use in the node embedding. If None, a default value of min(max(n_neighbors // 4, 4), 15) will be used.
* **neighbor_scale** (*float*, *default=1.0*) – The scale factor to use when constructing the nearest neighbor graph. This multiplies the effective number of neighbors used in graph construction (neighbor_scale * n_neighbors). Values > 1.0 create denser graphs with more connectivity, potentially capturing more global structure but at increased computational cost. Values < 1.0 create sparser graphs focused on local structure.
* **random_state** (*np.random.RandomState* or *None*, *default=None*) – The random state to use for the random number generator. If None, the random number generator will not be seeded and will use the system time as the seed.
* **reproducible_flag** (*bool*, *default=True*) – Whether to ensure reproducible results by using deterministic algorithms where possible. When True, the clustering results should be consistent across runs with the same random_state.
* **min_similarity_threshold** (*float*, *default=0.2*) – The minimum similarity threshold for cluster layer selection. Peaks that result in clusterings with Jaccard similarity above this threshold will be filtered out to ensure diverse cluster layers.
* **max_layers** (*int*, *default=10*) – The maximum number of cluster layers to return. The algorithm will select up to this many diverse peaks based on persistence and similarity criteria.
* **n_label_prop_iter** (*int*, *default=20*) – The number of iterations to use in the label propagation algorithm when initializing the node embedding.

### Returns:

* **cluster_layers** (*list of array-like of shape (n_samples,)*) – The clustering of the data at each layer of the clustering. Each layer is a clustering of the data into a different number of clusters.
* **membership_strengths** (*list of array-like of shape (n_samples,)*) – The membership strengths of each point in the clustering at each layer. This gives a measure of how strongly each point belongs to each cluster.
* **nn_inds** (*array-like of shape (n_samples, n_neighbors)*) – Indices of nearest neighbors for each sample.
* **nn_dists** (*array-like of shape (n_samples, n_neighbors)*) – Distance from each sample to each nearest neighbor indexed by nn_inds
* **duplicates** (*set of tuple of int*) – Only returned in `return_duplicates` is True. A set of pairs of indices of potential duplicate points in the data.
```

--------------------------------

### EVoC Clustering with Specified Cluster Count

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/examples.md

Shows how to specify the desired number of clusters when initializing the EVoC clusterer.

```python
# When you know the desired number of clusters
clusterer = EVoC(approx_n_clusters=5)
labels = clusterer.fit_predict(X)
```

--------------------------------

### Parameter Optimization using Grid Search

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/examples.md

Illustrates how to perform a grid search over key EVoC parameters like `n_neighbors` and `noise_level` to find optimal settings using silhouette scores. Requires scikit-learn for evaluation.

```python
from sklearn.metrics import silhouette_score

# Grid search over parameters
best_score = -1
best_params = None

for n_neighbors in [10, 15, 20]:
    for noise_level in [0.3, 0.5, 0.7]:
        clusterer = EVoC(
            n_neighbors=n_neighbors,
            noise_level=noise_level,
            random_state=42
        )
        labels = clusterer.fit_predict(X)

        if len(np.unique(labels[labels >= 0])) > 1:
            score = silhouette_score(X, labels)
            if score > best_score:
                best_score = score
                best_params = {
                    'n_neighbors': n_neighbors,
                    'noise_level': noise_level
                }

print(f"Best parameters: {best_params}")
print(f"Best silhouette score: {best_score:.3f}")
```

--------------------------------

### Hierarchical Analysis with EVoC

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/examples.md

Demonstrates how to obtain and analyze multiple clustering granularities from the EVoC model. Access the full hierarchical structure for detailed insights.

```python
# Get multiple clustering granularities
clusterer = EVoC(max_layers=5)
clusterer.fit(X)

# Analyze each layer
for i, layer in enumerate(clusterer.cluster_layers_):
    n_clusters = len(np.unique(layer[layer >= 0]))
    persistence = clusterer.persistence_scores_[i]

    print(f"Layer {i}: {n_clusters} clusters, "
          f"persistence: {persistence:.3f}")

# Access the hierarchical structure
tree = clusterer.cluster_tree_
print(f"Hierarchical structure: {tree}")
```

--------------------------------

### evoc.EVoC Constructor

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/generated/evoc.EVoC.md

Initializes the EVoC clustering model with various parameters to control the clustering process.

```APIDOC
## evoc.EVoC(noise_level: float = 0.5, base_min_cluster_size: int = 5, base_n_clusters: int | None = None, approx_n_clusters: int | None = None, n_neighbors: int = 15, min_samples: int = 5, n_epochs: int = 50, node_embedding_init: str | None = 'label_prop', symmetrize_graph: bool = True, node_embedding_dim: int | None = None, neighbor_scale: float = 1.0, random_state: int | None = None, min_similarity_threshold: float = 0.2, max_layers: int = 10, n_label_prop_iter=20)

### Description
Embedding Vector Oriented Clustering for efficient clustering of high-dimensional embedding vectors such as CLIP-vectors, sentence-transformers output, etc. The clustering uses a combination of a node embedding of a nearest neighbour graph, related to UMAP, and a density based clustering approach related to HDBSCAN, improving upon those approaches in efficiency and quality for the specific case of high-dimensional embedding vectors.

### Parameters
- **noise_level** (float) - Optional - Controls the sensitivity to noise in the data. Defaults to 0.5.
- **base_min_cluster_size** (int) - Optional - The minimum size of clusters to be considered. Defaults to 5.
- **base_n_clusters** (int | None) - Optional - The exact number of clusters to find. If None, the algorithm will try to determine the number of clusters.
- **approx_n_clusters** (int | None) - Optional - An approximation for the number of clusters, used for optimization.
- **n_neighbors** (int) - Optional - The number of neighbors to consider when building the nearest neighbor graph. Defaults to 15.
- **min_samples** (int) - Optional - The minimum number of samples in a neighborhood for a point to be considered as a core point in density-based clustering. Defaults to 5.
- **n_epochs** (int) - Optional - The number of training epochs for the node embeddings. Defaults to 50.
- **node_embedding_init** (str | None) - Optional - Method for initializing node embeddings. Options include 'label_prop'. Defaults to 'label_prop'.
- **symmetrize_graph** (bool) - Optional - Whether to symmetrize the nearest neighbor graph. Defaults to True.
- **node_embedding_dim** (int | None) - Optional - The dimension of the node embeddings. If None, it's determined automatically.
- **neighbor_scale** (float) - Optional - Scaling factor for neighbor distances. Defaults to 1.0.
- **random_state** (int | None) - Optional - Seed for random number generation for reproducibility.
- **min_similarity_threshold** (float) - Optional - Minimum similarity threshold for merging clusters. Defaults to 0.2.
- **max_layers** (int) - Optional - Maximum number of layers to consider in the clustering process. Defaults to 10.
- **n_label_prop_iter** (int) - Optional - Number of iterations for label propagation. Defaults to 20.
```

--------------------------------

### Initialize EVoC with Custom Parameters

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/quickstart.md

Use this snippet to initialize the EVoC clusterer with specific parameters like n_neighbors, base_min_cluster_size, and max_layers for custom graph construction and clustering.

```python
clusterer = EVoC(
    n_neighbors=25,          # More neighbors for denser graphs
    base_min_cluster_size=10, # Larger minimum clusters
    max_layers=5             # Limit hierarchy depth
)

labels = clusterer.fit_predict(blob_data)
```

--------------------------------

### Clean and Build HTML Documentation

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Performs a clean build of the HTML documentation, removing old build artifacts before generating new ones. Useful for ensuring a fresh build.

```bash
make clean html
```

--------------------------------

### evoc.numba_kdtree.build_kdtree

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/index.md

Builds a KD-tree from the given data using Numba for acceleration.

```APIDOC
## evoc.numba_kdtree.build_kdtree(data, leaf_size=40)

### Description
Builds a KD-tree from the given data using Numba for acceleration.

### Parameters
- **data**: The input data array or list.
- **leaf_size** (int, optional): The maximum number of samples in a leaf node. Defaults to 40.
```

--------------------------------

### evoc.label_propagation.label_propagation_init

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/generated/evoc.label_propagation.label_propagation_init.md

Initializes a node embedding using label propagation on a sparse graph.

```APIDOC
## evoc.label_propagation.label_propagation_init

### Description
Initialize a node embedding using label propagation on a sparse graph.

This function provides a high-quality initialization for node embeddings by
combining graph-based label propagation with hierarchical partitioning. For
large graphs, it recursively partitions the data and upscales the results.
For small graphs, it uses direct methods (PCA, spectral embedding, or random).

### Parameters
#### Path Parameters
- **graph** (scipy.sparse matrix) - Required - A sparse adjacency or weighted graph matrix representing connectivity.
- **n_label_prop_iter** (int) - Optional - Number of label propagation iterations to perform on the graph. (default: 20)
- **n_embedding_epochs** (int) - Optional - Number of epochs when using node embedding for upscaling. (default: 50)
- **approx_n_parts** (int) - Optional - Approximate number of partitions to create for recursive partitioning
of large graphs. Useful for controlling memory and computation. (default: 512)
- **n_components** (int) - Optional - The number of dimensions in the output embedding. (default: 2)
- **scaling** (float) - Optional - Scaling factor applied to label propagation distances. (default: 0.1)
- **random_scale** (float) - Optional - Scaling factor for random noise in the initialization. (default: 1.0)
- **noise_level** (float) - Optional - The noise level parameter passed to node embedding algorithms. (default: 0.5)
- **random_state** (RandomState instance or None) - Optional - Controls the randomness of the algorithm. If None, uses system randomness. (default: None)
- **data** (array-like of shape (n_samples, n_features) or None) - Optional - The original data array. Required if base_init=’pca’. Used for direct
initialization methods on small graphs. (default: None)
- **recursive_init** (bool) - Optional - If True, uses recursive partitioning for large graphs. If False, applies
the base initialization method directly. (default: True)
- **base_init** ({'pca', 'random', 'spectral', 'mds'}) - Optional - The initialization method to use for small graphs (when graph size is below
base_init_threshold). ‘pca’ requires the data parameter. (default: 'pca')
- **base_init_threshold** (int) - Optional - The size threshold below which the base_init method is used directly.
Graphs larger than this use recursive partitioning. (default: 64)
- **upscaling** ({'partition_expander', 'node_embedding'}) - Optional - The method to use when upscaling partitions back to the full graph.
‘partition_expander’ uses a fast expansion method, ‘node_embedding’ uses
full node embedding (slower but potentially better quality). (default: 'partition_expander')

### Returns
**embedding** - The initialized node embedding based on label propagation and graph structure.

### Return type
array-like of shape (n_vertices, n_components)
```

--------------------------------

### Import necessary libraries

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Imports the required libraries for data generation and FAISS.

```python
from sklearn.datasets import make_blobs
import faiss
```

--------------------------------

### Explore Hierarchical Clustering Layers in EVoC

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/user_guide.md

Instantiate EVoC, fit it to data, and iterate through cluster layers to analyze cluster counts, noise points, and persistence scores. Useful for understanding different granularities of clustering.

```python
clusterer = EVoC(max_layers=5)
clusterer.fit(X)

# Explore different granularities
for i, layer in enumerate(clusterer.cluster_layers_):
    n_clusters = len(np.unique(layer[layer >= 0]))
    n_noise = np.sum(layer == -1)
    persistence = clusterer.persistence_scores_[i]

    print(f"Layer {i}: {n_clusters} clusters, {n_noise} noise points, "
          f"persistence: {persistence:.3f}")

# Use cluster tree for hierarchical analysis
tree = clusterer.cluster_tree_
# ... analyze hierarchical structure ...
```

--------------------------------

### Import Libraries for Benchmarking

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Imports all necessary libraries for running benchmarks, comparisons, and visualizing results, including numpy, matplotlib, seaborn, time, evoc, umap, hdbscan, pandas, and sklearn modules. It also suppresses warnings.

```python
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import time
import evoc
import umap
import hdbscan
import pandas as pd
import sklearn.cluster
import sklearn.metrics
import warnings
warnings.filterwarnings("ignore")
```

--------------------------------

### Run Dataset Benchmarks

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Executes benchmark tests for clustering algorithms on the prepared dataset, configuring KMeans and UMAP+HDBSCAN with specific parameters.

```python
bird_results = run_dataset_benchmarks(
    birdclef2023_data, 
    birdclef2023_target, 
    n_runs=16, 
    kmeans_kwargs={"n_clusters":130}, 
    umap_hdbscan_kwargs={
        "min_samples":5,
        "min_cluster_size":100,
        "metric":"cosine",
        "cluster_selection_method":"leaf"
    }
)
```

--------------------------------

### Run Dataset Benchmarks

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Executes benchmark tests for clustering algorithms on CIFAR-100 data. Configures KMeans with 125 clusters and UMAP+HDBSCAN with specific parameters for optimal performance.

```python
cifar_results = run_dataset_benchmarks(
    cifar_data, 
    cifar_target, 
    n_runs=16, 
    kmeans_kwargs={\"n_clusters\":125},
    umap_hdbscan_kwargs={
        "min_samples":5,
        "min_cluster_size":120, 
        "metric":"cosine", 
        "cluster_selection_method":"leaf"
    }
)
```

--------------------------------

### Load and Prepare MNIST Data

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Loads the MNIST dataset and prepares the data and target arrays for clustering. Ensures data is in float32 format and C-contiguous order.

```python
mnist_ds = fetch_openml('mnist_784')
mnist_data = mnist_ds.data.values.astype(np.float32, order="C")
mnist_target = mnist_ds.target.values.astype(np.uint8)
```

--------------------------------

### Load 20-Newsgroups Dataset

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Loads the 20-newsgroups dataset and extracts pre-computed text embeddings and target labels. This is the initial step for running benchmarks on text data.

```python
ds_news = load_dataset("lmcinnes/evoc_bench_20newsgroups")
news_data = np.asarray(ds_news["train"]["embedding"])
news_target = np.asarray(ds_news["train"]["target"])
```

--------------------------------

### Check Documentation Links

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/README.md

Runs Sphinx's link checking functionality to identify any broken internal or external links within the documentation.

```bash
make linkcheck
```

--------------------------------

### Fetch MNIST Dataset

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Imports the necessary function to fetch the MNIST dataset from OpenML.

```python
from sklearn.datasets import fetch_openml
```

--------------------------------

### MiniBatchKMeans wrapper function

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

A wrapper function for scikit-learn's MiniBatchKMeans to facilitate its use in benchmarking. It configures the number of clusters and batch size.

```python
def minibatch_kmeans(data, n_clusters=10):
    return sklearn.cluster.MiniBatchKMeans(
        n_clusters=n_clusters, 
        n_init="auto", 
        batch_size=4*n_clusters
    ).fit_predict(
        data
    )
```

--------------------------------

### Advanced EVōC Features: Layers, Hierarchy, and Duplicates

Source: https://github.com/tutteinstitute/evoc/blob/main/README.rst

Illustrates how to access advanced features of EVoC, including multiple cluster layers, the cluster hierarchy, and potential duplicate vectors. These are useful for layered topic modeling and data exploration.

```python
import evoc
from sklearn.datasets import make_blobs

data, _ = make_blobs(n_samples=100_000, n_features=1024, centers=100)

clusterer = evoc.EVoC()
cluster_labels = clusterer.fit_predict(data)
cluster_layers = clusterer.cluster_layers_
hierarchy = clusterer.cluster_tree_
potential_duplicates = clusterer.duplicates_
```

--------------------------------

### evoc.clustering_utilities.build_cluster_tree

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/evoc.clustering_utilities.md

Constructs a cluster tree from a set of labels.

```APIDOC
## evoc.clustering_utilities.build_cluster_tree(labels)

### Description
Constructs a cluster tree from a set of labels.

### Method
N/A (Python function)

### Parameters
#### Path Parameters
N/A

#### Query Parameters
N/A

#### Request Body
N/A

### Request Example
N/A

### Response
N/A
```

--------------------------------

### EVoC Clustering Parameters and Outputs

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/generated/evoc.EVoC.md

The EVoC algorithm offers a comprehensive set of parameters to fine-tune the clustering process, from noise tolerance to embedding dimensions. It outputs cluster labels and membership strengths for each data sample.

```APIDOC
## EVoC Clustering

### Description
Performs hierarchical clustering using an evolutionary approach, generating multiple layers of clusters with varying granularity and noise filtering.

### Parameters

#### Noise and Granularity Control
* **noise_level** (*float*, *default=0.5*) – Controls the trade-off between clustering more data and cluster accuracy. Higher values discard more data as noise for more accurate clusters.
* **base_min_cluster_size** (*int*, *default=5*) – The minimum number of points required for a cluster in the base layer.
* **base_n_clusters** (*int* or *None*, *default=None*) – Attempts to find a base clustering with exactly this many clusters. If None, the algorithm determines the number of clusters.
* **approx_n_clusters** (*int*, *default=None*) – If set, produces a single-layer clustering with approximately this many clusters, bypassing hierarchical layers.

#### Graph and Embedding Parameters
* **n_neighbors** (*int*, *default=15*) – The number of neighbors to consider when constructing the nearest neighbor graph.
* **min_samples** (*int*, *default=5*) – The minimum number of samples used for density estimation in node embedding.
* **n_epochs** (*int*, *default=50*) – The number of training epochs for the node embedding.
* **node_embedding_init** (*str* or *None*, *default='label_prop'*) – Method for initializing node embeddings. Options include 'label_prop' or None for no initialization.
* **symmetrize_graph** (*bool*, *default=True*) – Whether to symmetrize the nearest neighbor graph before embedding.
* **node_embedding_dim** (*int* or *None*, *default=None*) – The desired dimensionality for the node embeddings. If None, a default is calculated.
* **neighbor_scale** (*float*, *default=1.0*) – A scaling factor for `n_neighbors`, influencing graph density and structure capture.
* **n_label_prop_iter** (*int*, *default=20*) – Number of iterations for the label propagation algorithm during embedding initialization.

#### Layer Selection and Filtering
* **min_similarity_threshold** (*float*, *default=0.2*) – Minimum Jaccard similarity for cluster layers to be considered diverse and kept.
* **max_layers** (*int*, *default=10*) – The maximum number of hierarchical cluster layers to return.

#### General Parameters
* **random_state** (*int* or *None*, *default=None*) – Seed for the random number generator for reproducible results.

### Outputs

#### labels_
* **Type:** array-like of shape (n_samples,)
* **Description:** An array of integer labels for each data sample. A value of -1 indicates a noise point.

#### membership_strengths_
* **Type:** array-like of shape (n_samples,)
* **Description:** An array of floating-point values (0 to 1) indicating the strength of each sample's membership in its assigned cluster.
```

--------------------------------

### Evoc Clustering

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/evoc.clustering.md

Performs clustering on the input data using the Evoc algorithm. It allows for fine-grained control over various aspects of the clustering process, including noise handling, cluster granularity, graph construction, and node embedding initialization. The output includes cluster labels and membership strengths for each data sample.

```APIDOC
## Evoc Clustering

### Description
Performs clustering on the input data using the Evoc algorithm. This method offers a comprehensive set of parameters to customize the clustering process, from noise tolerance to the number of layers in the hierarchical output. It is suitable for scenarios requiring detailed control over cluster formation and analysis.

### Parameters
#### Noise and Granularity
* **noise_level** (*float*, *default=0.5*) – Controls the trade-off between including more data and cluster accuracy. Higher values discard more data for more accurate clusters.
* **base_min_cluster_size** (*int*, *default=5*) – Sets the minimum number of points for clusters in the base layer, defining the finest granularity.
* **base_n_clusters** (*int* or *None*, *default=None*) – Attempts to find a clustering granularity yielding exactly this many clusters in the bottom-most layer. Affects base layer computation for hierarchical layers.
* **approx_n_clusters** (*int*, *default=None*) – Attempts to find a clustering granularity yielding exactly this many clusters as the final output. Results in a single layer of clustering.

#### Graph and Embedding
* **n_neighbors** (*int*, *default=15*) – The number of neighbors used in nearest neighbor graph construction.
* **min_samples** (*int*, *default=5*) – Minimum samples for density estimation in node embedding.
* **n_epochs** (*int*, *default=50*) – Number of epochs for training the node embedding.
* **node_embedding_init** (*str* or *None*, *default='label_prop'*) – Method for initializing node embedding. Options include 'label_prop' or None.
* **symmetrize_graph** (*bool*, *default=True*) – Whether to symmetrize the nearest neighbor graph before node embedding.
* **node_embedding_dim** (*int* or *None*, *default=None*) – Dimensions for node embedding. Defaults to min(max(n_neighbors // 4, 4), 15) if None.
* **neighbor_scale** (*float*, *default=1.0*) – Scale factor for nearest neighbor graph construction. Affects graph density and structure capture.
* **n_label_prop_iter** (*int*, *default=20*) – Iterations for label propagation in node embedding initialization.

#### Layer Selection
* **min_similarity_threshold** (*float*, *default=0.2*) – Minimum Jaccard similarity for filtering cluster layers to ensure diversity.
* **max_layers** (*int*, *default=10*) – Maximum number of diverse cluster layers to return.

#### General
* **random_state** (*int* or *None*, *default=None*) – Seed for the random number generator for reproducible results.

### Outputs
#### labels_
* **Type:** array-like of shape (n_samples,)
* **Description:** An array of integer labels for each data sample. A value of -1 indicates noise.

#### membership_strengths_
* **Type:** array-like of shape (n_samples,)
* **Description:** An array of floating point values (0-1) indicating how strongly each sample belongs to its assigned cluster.
```

--------------------------------

### Run Dataset Benchmarks on MNIST

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Executes benchmark runs on the MNIST dataset using EVoC and other algorithms. Configures parameters for KMeans and UMAP+HDBSCAN.

```python
mnist_results = run_dataset_benchmarks(
    mnist_data, 
    mnist_target, 
    n_runs=16, 
    kmeans_kwargs={"n_clusters":10},
    umap_hdbscan_kwargs={
        "min_samples":5,
        "min_cluster_size":1200, 
        "metric":"cosine", 
        "cluster_selection_method":"leaf"
    }
)
```

--------------------------------

### FAISS KMeans wrapper function

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

A wrapper function for FAISS's KMeans implementation. It initializes FAISS KMeans, trains it on the data, and returns the cluster labels.

```python
def faiss_kmeans(data, n_clusters=10):
    kmeans = faiss.Kmeans(data.shape[1], n_clusters, niter=50, nredo=1, gpu=False)
    X = np.ascontiguousarray(data, dtype=np.float32)
    kmeans.train(X)
    _, labels = kmeans.index.search(X, 1)
    return labels.ravel()
```

--------------------------------

### Clustering Sentence Embeddings

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/examples.md

Demonstrates clustering text data by first generating sentence embeddings using Sentence Transformers and then applying EVoC. Groups texts by their assigned cluster.

```python
from sentence_transformers import SentenceTransformer
from evoc import EVoC

# Load sentence transformer model
model = SentenceTransformer('all-MiniLM-L6-v2')

# Your text data
texts = [
    "The cat sat on the mat",
    "Dogs are great pets",
    "Machine learning is fascinating",
    # ... more texts
]

# Generate embeddings
embeddings = model.encode(texts)

# Cluster similar texts
clusterer = EVoC(
    n_neighbors=15,
    noise_level=0.4,
    base_min_cluster_size=2
)
labels = clusterer.fit_predict(embeddings)

# Group texts by cluster
clusters = {}
for i, label in enumerate(labels):
    if label >= 0:  # Ignore noise points
        if label not in clusters:
            clusters[label] = []
        clusters[label].append(texts[i])
```

--------------------------------

### Evoc Clustering Parameters and Returns

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/api/index.md

This snippet details the configurable parameters for the Evoc clustering algorithm and the structure of its returned values.

```APIDOC
## Evoc Clustering

### Parameters

* **neighbor_scale** (*float*, *default=1.0*) – The scale factor to use when constructing the nearest neighbor graph. This multiplies the effective number of neighbors used in graph construction (neighbor_scale * n_neighbors). Values > 1.0 create denser graphs with more connectivity, potentially capturing more global structure but at increased computational cost. Values < 1.0 create sparser graphs focused on local structure.
* **random_state** (*np.random.RandomState* or *None*, *default=None*) – The random state to use for the random number generator. If None, the random number generator will not be seeded and will use the system time as the seed.
* **reproducible_flag** (*bool*, *default=True*) – Whether to ensure reproducible results by using deterministic algorithms where possible. When True, the clustering results should be consistent across runs with the same random_state.
* **min_similarity_threshold** (*float*, *default=0.2*) – The minimum similarity threshold for cluster layer selection. Peaks that result in clusterings with Jaccard similarity above this threshold will be filtered out to ensure diverse cluster layers.
* **max_layers** (*int*, *default=10*) – The maximum number of cluster layers to return. The algorithm will select up to this many diverse peaks based on persistence and similarity criteria.
* **n_label_prop_iter** (*int*, *default=20*) – The number of iterations to use in the label propagation algorithm when initializing the node embedding.

### Returns:

* **cluster_layers** (*list of array-like of shape (n_samples,)*) – The clustering of the data at each layer of the clustering. Each layer is a clustering of the data into a different number of clusters.
* **membership_strengths** (*list of array-like of shape (n_samples,)*) – The membership strengths of each point in the clustering at each layer. This gives a measure of how strongly each point belongs to each cluster.
* **nn_inds** (*array-like of shape (n_samples, n_neighbors)*) – Indices of nearest neighbors for each sample.
* **nn_dists** (*array-like of shape (n_samples, n_neighbors)*) – Distance from each sample to each nearest neighbor indexed by nn_inds
* **duplicates** (*set of tuple of int*) – Only returned in `return_duplicates` is True. A set of pairs of indices of potential duplicate points in the data.
```

--------------------------------

### Run Dataset Benchmarks for Text Data

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Executes benchmark tests on the 20-newsgroups text data using EVoC, KMeans, and UMAP+HDBSCAN. It configures specific parameters for each algorithm to optimize performance and clustering quality.

```python
news_results = run_dataset_benchmarks(
    news_data, 
    news_target, 
    n_runs=32, 
    kmeans_kwargs={"n_clusters":25},
    umap_hdbscan_kwargs={
        "min_samples":5,
        "min_cluster_size":180,
        "metric":"cosine",
        "cluster_selection_method":"leaf"
    }
)
```

--------------------------------

### Load and Preprocess BirdCLEF 2023 Dataset

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Loads the BirdCLEF 2023 dataset embeddings and targets, then filters out species with fewer than 100 recordings to simplify clustering.

```python
ds_birdclef = load_dataset("Syoy/birdclef_2023_train")
birdclef2023_data = np.asarray(ds_birdclef["train"]["embeddings"])
birdclef2023_target = np.asarray(ds_birdclef["train"]["primary_label"])
# Only use bird species with at least 100 samples -- this is still very challenging
mask = np.isin(
    birdclef2023_target,
    np.where(np.bincount(birdclef2023_target) > 100)[0],
)
birdclef2023_data = birdclef2023_data[mask]
birdclef2023_target = birdclef2023_target[mask]
```

--------------------------------

### Plotting runtime scaling

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/benchmarks.ipynb

Generates a scatter plot with a regression line to visualize how the runtime of each algorithm scales with increasing dataset size.

```python
sns.lmplot(data=scaling_df, x="size", y="time", hue="algorithm", order=2, height=10)
```

--------------------------------

### Understanding EVōC Output Attributes

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/quickstart.md

Access and print information about the clustering results, including the number of available cluster layers, the average membership strength, and the hierarchical cluster structure. This demonstrates how to interpret the detailed outputs provided by EVōC.

```python
# Access different clustering layers
print(f"Available layers: {len(clusterer.cluster_layers_)}")

# Get membership strengths
strengths = clusterer.membership_strengths_
print(f"Average membership strength: {np.mean(strengths):.3f}")

# Access the cluster hierarchy
tree = clusterer.cluster_tree_
print(f"Hierarchical structure: {tree}")
```

--------------------------------

### Optimize EVoC for Faster Clustering on Large Datasets

Source: https://github.com/tutteinstitute/evoc/blob/main/doc/source/user_guide.md

Reduce n_neighbors and n_epochs, and limit max_layers for faster clustering on large datasets, trading off some accuracy for speed. Not setting a random seed can improve performance.

```python
clusterer = EVoC(
    n_neighbors=10,         # Balance between quality and speed
    n_epochs=30,           # Fewer epochs for faster embedding
    max_layers=3,          # Limit hierarchy depth
)
```