K-Means Clustering With Natural Density Peaks for Discovering Arbitrary-Shaped Clusters

Area of Science:

• Data Science
• Machine Learning
• Clustering Algorithms

Background:

• K-means is a widely used clustering method known for its simplicity.
• However, K-means struggles with identifying arbitrary-shaped clusters and is sensitive to initial center selection.
• Existing K-means improvements often focus on speed or initial centers, neglecting the arbitrary-shaped cluster problem.

Purpose of the Study:

• To propose a novel K-means algorithm, NDP-Kmeans, capable of identifying arbitrary-shaped clusters.
• To address the limitations of traditional K-means in handling complex data structures.
• To improve clustering accuracy for manifold and non-spherical data distributions.

Main Methods:

• Selected representatives from local neighborhoods, termed natural density peaks (NDPs).
• Defined a neighbor-based distance metric for NDPs to compute graph distance (GD) efficiently.
• Employed an improved K-means algorithm utilizing high-quality initial centers and GD for clustering NDPs.

Main Results:

• NDP-Kmeans successfully identified both spherical and manifold clusters.
• The algorithm demonstrated superior performance in detecting arbitrary-shaped clusters compared to other methods.
• Efficient computation of GD was achieved by leveraging neighbor-based distances between NDPs.

Conclusions:

• NDP-Kmeans offers a significant advancement in clustering arbitrary-shaped data.
• The use of natural density peaks and neighbor-based graph distance computation enhances clustering quality.
• This approach provides a more robust and versatile clustering solution than traditional K-means variants.