Metadata-Version: 2.1
Name: cdc-cluster
Version: 0.1.1
Summary: A novel Clustering algorithm by measuring Direction Centrality (CDC) locally. It adopts a density-independent metric based on the distribution of K-nearest neighbors (KNNs) to distinguish between internal and boundary points. The boundary points generate enclosed cages to bind the connections of internal points.
Author-email: pdh <pengdh@whu.edu.cn>
Project-URL: Homepage, https://github.com/ZPGuiGroupWhu/CDC-pkg
Project-URL: Repository, https://github.com/ZPGuiGroupWhu/CDC-pkg.git
Project-URL: Bug Tracker, https://github.com/ZPGuiGroupWhu/CDC-pkg/issues
Keywords: clustering,centrality,boundary detection
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Requires-Python: >=3.8
Description-Content-Type: text/markdown
Requires-Dist: scikit-learn>=1.3.2

# Clustering by measuring local direction centrality for data with heterogeneous density and weak connectivity (CDC)


We propose a novel Clustering algorithm by measuring Direction Centrality (CDC) locally. It adopts a density-independent metric based on the distribution of K-nearest neighbors (KNNs) to distinguish between internal and boundary points. The boundary points generate enclosed cages to bind the connections of internal points, thereby preventing cross-cluster connections and separating weakly-connected clusters. We present an interactive ***Demo*** and a brief introduction to the algorithm at ***https://zpguigroupwhu.github.io/CDC-Introduction-Website/***, and develop a CDC toolkit at ***https://github.com/ZPGuiGroupWhu/ClusteringDirectionCentrality*** This paper has been published in ***Nature Communications***, and more details can be seen https://www.nature.com/articles/s41467-022-33136-9. 

![image](https://raw.githubusercontent.com/ZPGuiGroupWhu/CDC-pkg/refs/heads/main/image/cdc_algorithm.png)

# Installation
Supported `python` versions are `3.8` and above.

This project has been uploaded to [PyPI](https://pypi.org/project/cdc-cluster/), supporting direct download and installation from pypi

```
pip install cdc-cluster
```

## Manual Installation

```
git clone https://github.com/ZPGuiGroupWhu/CDC-pkg.git
cd CDC-pkg
pip install -e .
```

# How To Run
The CDC algorithm package provides the `cdc_cluster` function for clustering.

The description of the hyperparameters for user configuration are presented as follows 
```python
def cdc_cluster(X: np.ndarray, k_num: int, ratio: float) -> np.ndarray:
    """Clustering by measuring local Direction Centrality (CDC) algorithm.

    This function implements the CDC clustering algorithm, which is a connectivity-based
    clustering method that identifies boundary points using a directional centrality
    metric (DCM) and connects internal points to generate cluster labels. DCM is defined
    as angle variance in 2D space and simplex volume variance in higher dimensions.

    The algorithm works in several steps:
    1. For each point, find k-nearest neighbors
    2. For each point, calculate its DCM
    3. Identify boundary and internal points based on the DCM threshold
    4. Calculate reachable distances of the internal points
    5. Form clusters by connecting nearby internal points
    6. Assign boundary points to nearest clusters

    Args:
        X (np.ndarray): Input data matrix of shape (n_samples, n_features).
            Each row represents a data point and each column represents a feature.
        k_num (int): Number of nearest neighbors to consider. Must be greater than 0.
            This parameter controls the local neighborhood size.
        ratio (float): Ratio for determining the DCM threshold. Must be between 0 and 1.
            Lower values result in fewer internal points and more boundary points.

    Returns:
        np.ndarray: Cluster labels for each data point. Shape (n_samples,).
            Labels are integers starting from 1, where points with the same label
            belong to the same cluster.

    Raises:
        AssertionError: If k_num <= 0 or ratio is not in (0, 1).
        ValueError: If X is not a 2D array or has insufficient data points.

    Note:
        - For 2D data, the algorithm uses angle variance between k-nearest neighbors
        - For higher dimensional data, it uses convex hull simplex volume variance
        - The algorithm automatically handles edge cases and numerical instabilities
    """
```
After installing the CDC library, you can use this function as follows:
```python
from cdc import cdc_cluster
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import time
# DS1.txt link: https://github.com/ZPGuiGroupWhu/ClusteringDirectionCentrality/blob/master/Toolkit/Python/DS1.txt
raw_data = pd.read_table('DS1.txt', header=None)
X = np.array(raw_data)
[n, d] = X.shape
data = X[:, :d-1]
ref = X[:, d-1]
time_start = time.time()
res = cdc_cluster(X=data, k_num=30, ratio=0.72)
time_end = time.time()
print(time_end-time_start)

plt.scatter(data[:, 0], data[:, 1], c=res, s=10, cmap='hsv', marker='o')
plt.show()
```
# Citation Request:
Peng, D., Gui, Z.*, Wang, D. et al. Clustering by measuring local direction centrality for data with heterogeneous density and weak connectivity. Nat. Commun. 13, 5455 (2022).
https://www.nature.com/articles/s41467-022-33136-9

# License

This project is covered under the MIT License.
