EVoC: Embedding Vector Oriented Clustering

EVoC provides several advantages for clustering dense vector representations:

• Optimized for High-Dimensional Embeddings: Specifically designed for modern embedding vectors.
• Multi-Layer Clustering: Provides hierarchical clustering with multiple granularity levels.
• Performance Optimized: Uses Numba for high-performance computation.
• Flexible Parameters: Extensive parameter set for fine-tuning clustering behavior.
• Scikit-learn Compatible: Follows standard scikit-learn API conventions.

EVoC (Embedding Vector Oriented Clustering) is a two-part algorithm designed specifically for clustering high-dimensional embedding vectors. It combines:

1. Graph Embedding: Constructs a k-nearest neighbor (k-NN) graph and learns a lower-dimensional embedding (similar to UMAP).
2. Density Clustering: Applies hierarchical density-based clustering to the resulting embedding (similar to HDBSCAN and PLSCAN).

This approach is optimized for performance and quality when handling dense, high-dimensional data, providing multiple clustering granularities through hierarchical layers and robust handling of noise and outliers.

EVoC supports hierarchical analysis by allowing you to inspect multiple layers of clustering. By setting max_layers in the constructor, you can access:

• cluster_layers_: An array containing the cluster assignments for each layer.
• persistence_scores_: The persistence score for each layer.
• cluster_tree_: The hierarchical tree structure representing the relationships between clusters.

# 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}")

When processing large datasets, you can improve memory efficiency by:

1. Reducing graph density with a lower n_neighbors.
2. Lowering the node_embedding_dim.
3. Reducing the number of training epochs with n_epochs.
4. Limiting hierarchy depth with max_layers.
5. Processing data in chunks (though note that fit_predict on chunks will return labels for those specific chunks).

# For large datasets, use smaller parameters
clusterer = EVoC(
    n_neighbors=10,        # Reduce graph density
    node_embedding_dim=8,  # Lower embedding dimension  
    n_epochs=30,          # Fewer training epochs
    max_layers=3          # Limit hierarchy depth
)

# Process in chunks if needed
chunk_size = 10000
all_labels = []

for i in range(0, len(X), chunk_size):
    chunk = X[i:i+chunk_size]
    chunk_labels = clusterer.fit_predict(chunk)
    all_labels.extend(chunk_labels)

To install the latest development version of EVōC directly from the GitHub repository, use the following command:

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

EVoC (Embedding Vector Oriented Clustering) is designed for high-dimensional embedding vectors (e.g., CLIP, sentence-transformers). It follows the scikit-learn API convention, allowing you to initialize a clusterer and use fit_predict to obtain cluster labels. The algorithm provides multi-layer clustering, which can be inspected via the cluster_layers_ attribute.

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_)}")

You can build the documentation using automated scripts or manual Sphinx commands.

Quick Build

For a fast build using the provided scripts:

• Unix/macOS: Run ./build_docs.sh from the doc/ directory.
• Windows: Run build_docs.bat from the doc/ directory.

Manual Build

To build manually using make:

1. Install dependencies: pip install -r requirements.txt
2. Install EVoC in development mode: pip install -e ../..
3. Build the HTML: make html
4. View the result in build/html/index.html.

# Unix/macOS Quick Build
cd doc
./build_docs.sh

# Windows Quick Build
cd doc
build_docs.bat

# Manual Build
pip install -r requirements.txt
pip install -e ../..
make html

To add new content to the documentation:

1. Create new .rst (reStructuredText) files in the source/ directory.
2. Register the new files by adding them to the toctree (Table of Contents tree) in source/index.rst.
3. Rebuild the documentation to see the changes.

You can install the stable version of EVōC from PyPI using pip. EVōC requires numpy, scikit-learn, numba, tqdm, and tbb as dependencies.

pip install evoc

The documentation uses Nbsphinx to integrate Jupyter notebooks. To include a notebook:

1. Place your .ipynb files in source/notebooks/.
2. Add the notebook files to source/notebooks/index.rst.
3. During the build process, notebooks are automatically converted to documentation.

Note on execution: By default, notebooks are NOT executed during the build (nbsphinx_execute = 'never'). To force execution of all cells during the build, change this setting to always in conf.py.