Standard clustering algorithms like $K$-means rely on a fundamental assumption: a cluster can be adequately summarized by a single central point, such as a geometric centroid or a central medoid. This assumption works beautifully when data is neatly packed into spherical, convex blobs.
But what happens when a cluster snakes along a winding manifold, forms a crescent moon, or exists in a relational database where a "geometric mean" cannot even be computed? In these scenarios, a single central point often falls completely outside the actual data density, leading to misclassification and a failure to capture the true underlying structure.
To bridge this gap, a powerful paradigm has emerged: representing a single cluster using a set or distribution of multiple representative points. As noted in a comprehensive taxonomy by Jinzhen Ping et al., this multi-point approach balances the computational efficiency of centroid-based methods with the descriptive power required for complex geometries.
The Intuition of Well-Scattered Skeletons
How do we choose these multiple points without falling back into the computational trap of tracking every single data point? The foundational intuition is to find a small set of "well-scattered" points that trace the outer boundaries and internal density of the cluster, effectively forming a structural skeleton.
In the classic CURE algorithm, Kyuseok Shim et al. select a fixed number of well-scattered points and then shrink them toward the cluster centroid by a fraction $\alpha$. This shrinking mechanism serves a dual purpose: it mitigates the distorting impact of outliers while allowing the algorithm to adaptively conform to non-spherical shapes and varying cluster sizes.
Similarly, for evaluating the quality of a clustering layout, Maria Halkidi developed the CDbw validity index, which uses a furthest-first traversal to isolate well-scattered representatives. By evaluating density around multiple points rather than a single center, the index can accurately judge the compactness and separation of arbitrarily shaped clusters.
Single Centroid (Fails on Manifolds) Multi-Point Skeleton (Succeeds)
_______ _______
/ o \ / x x \
| (Mean) | | x x |
\_________/ \_________/
(Outside Density) (Traces Geometry)
When scaled to optimization frameworks, this skeletonization allows algorithms to trace complex data manifolds. For instance, Man Liu combines a minimum spanning tree with multiple local centroids within a particle swarm optimization framework. By calculating distances along the tree paths and breaking a complex cluster down into simpler sub-clusters, the algorithm effectively maps non-convex shapes that traditional Euclidean metrics would fail to partition.
Clustering Without Coordinates: Relational and Multi-View Spaces
The single-centroid model breaks down completely when data lacks a continuous geometric space. In relational databases or multi-view applications, calculating a mean vector is mathematically undefined.
Sarabjot Singh Anand addresses this by replacing the single central medoid with a set of maximally spread representative objects distributed throughout the cluster space. This allows relational clustering algorithms to capture complex, non-spherical relational structures without requiring explicit coordinates.
To make this representation more robust, frameworks can assign continuous weights to these representatives, turning a discrete set of points into a weighted committee. Kuang Zhou et al. introduced an evidential c-medoids clustering approach (wECMdd) that models clusters using multiple weighted medoids. Each object's weight reflects its degree of representativeness, providing a richer, more nuanced understanding of cluster composition and handling overlapping or uncertain data.
This concept is extended to multi-view data by Yangtao Wang et al., who model clusters as a weighted distribution across all objects. By optimizing a weighted committee of medoids across different data views, their approach flexibly handles complex or non-spherical geometries where different views might emphasize different dense regions.
Decompositions, Graphs, and Boundaries
The utility of multi-point representation extends beyond traditional clustering into matrix factorization, deep learning, and computer vision, where it solves analogous geometric bottlenecks.
In Non-Negative Matrix Factorization (NMF), standard models fail when data lies on intricate manifolds because they rely on a single global basis vector per cluster. Hongchang Gao et al. resolve this by introducing a local centroids structured NMF. By representing a single cluster using multiple local basis vectors, the model prevents misclassification near irregular cluster boundaries and accurately preserves the underlying manifold structure.
In high-dimensional, dynamic environments—such as incremental face clustering—Xuan Zhao et al. utilize Graph Convolutional Networks (GCNs) to aggregate multiple representative nodes into an "optimal summary" rather than a single mean vector. This multi-point summary allows the network to dynamically capture the arbitrary shapes formed by evolving face tracks in high-dimensional space.
Even in spatial and control applications, moving past a single origin unlocks new capabilities:
- Regions of Attraction: In estimating complex, non-convex regions of attraction for dynamical systems, Yue Shen et al. employ a multi-center representation composed of overlapping geometric primitives (like spheres or polyhedra), balancing shape flexibility with computational tractability.
- Instance Segmentation: In computer vision, Ke-Lei Wang et al. developed MP-PolarMask for instance segmentation. While traditional polar coordinate regression relies on a single center—failing on concave shapes—their model uses a primary center alongside four auxiliary centers distributed across quadrants, enabling precise boundary regression for highly complex geometries.
- Spatial Orientation: For spatial reasoning, Haowen Yan demonstrates that modeling the spatial orientation of sprawling or intertwined object groups requires treating direction as a weighted distribution of multiple angles rather than a single vector.
By shifting from a single-point summary to a multi-point committee, these diverse techniques share a core mechanism: they distribute the burden of representation across a localized collective, allowing algorithms to respect the true topography of complex data.
Key Foundational Work
Multi-type Relational Clustering Approaches: Current State-of-the-Art and New Directions (2008) — contributed 3 concept elements to this direction.
A density-based cluster validity approach using multi-representatives (2008) — contributed 2 concept elements to this direction.
Cure: An Efficient Clustering Algorithm for Large Databases (2001) — contributed 2 concept elements to this direction.