User Guide#

This guide provides a detailed overview of the DenMune algorithm, its implementation details, and practical usage tips.

Motivation for this Implementation#

This version of DenMune was developed as a clean-room rewrite to provide a robust, performant, and scikit-learn compatible estimator. The previous implementation available on PyPI had several architectural issues that hindered its practical use, including:

  • Lack of Scikit-learn Compatibility: The legacy class did not inherit from BaseEstimator, preventing its use in standard scikit-learn tools like Pipeline and GridSearchCV. Our implementation, DenMune, is a proper scikit-learn estimator.

  • Algorithmic Flaws: The previous version improperly mixed training and testing data, leading to data leakage and invalid evaluation metrics. This implementation adheres to the standard fit/predict paradigm.

  • Performance Bottlenecks: Core logic relied on slow Python loops. This implementation uses a vectorized, sparse-graph approach for significant speed-up.

How DenMune Works#

DenMune is a density-based algorithm that identifies clusters by finding density peaks and expanding from them based on mutual nearest neighbors. It operates in two main phases after an initial density estimation.

1. Density Estimation

For each point p, the algorithm computes two key sets based on its k_nearest neighbors: - The Refer-To List (`KNN_p->`): The k points closest to p. - The Reference-List (`KNN_p<-`): The set of points that consider p to be one of their k nearest neighbors.

The size of the Reference-List, |KNN_p<-|, serves as the density score for point p.

2. Phase I: Cluster Skeleton Construction

Points are classified based on their density: - Strong Points: Points where |KNN_p<-| >= k_nearest. These are density peaks and serve as the initial seeds for clusters. - Weak Points: Points where |KNN_p<-| < k_nearest. These are boundary points or noise. - Noise Points: Points with few or no mutual neighbors.

The algorithm iterates through the strong points in descending order of density. Each strong point forms a new cluster or is merged with an existing cluster skeleton using a Union-Find data structure for efficiency. Merging is decided by a majority vote among its already-classified mutual neighbors.

3. Phase II: Weak Point Assignment

After the skeletons are formed, the algorithm iteratively attempts to assign the remaining weak points. A weak point is assigned to the cluster that has the majority representation among its mutual neighbors. Points that cannot be assigned are labeled as noise (-1).

Practical Usage and Parameters#

Choosing `k_nearest`

The k_nearest parameter is the most important hyperparameter. It controls the granularity of the density estimation. - A small `k` may cause dense clusters to be fragmented. - A large `k` may cause distinct but close clusters to be merged. The paper suggests the algorithm is stable over a wide range of k. You can investigate this for your dataset as shown in our Analyzing DenMune’s Sensitivity to the k_nearest Parameter example.

Dimensionality Reduction

The algorithm’s density estimation is most effective in low-dimensional space. For high-dimensional data (n_features > 50 is a common heuristic), it is highly recommended to use dimensionality reduction. - `reduce_dims=True` (default): Will reduce data to target_dims. - `dim_reducer`: Can be set to 'tsne', 'pca', or a custom estimator instance like UMAP. See the sphx_glr_auto_examples_plot_custom_reducer.py example for how to use a custom reducer.