CURE clustering
Algorithms AIMech:CUREClustering DRAFT
Aliases: CURE, Clustering Using REpresentatives
An agglomerative clustering procedure that represents each cluster by several scattered points shrunk toward its mean and merges the pair with the smallest distance between their representative points.
Identity Notes & Concept Scope
CURE uses a set of representative locations, unlike centroid-only k-means or graph-cut normalization in CHAMELEON. This record describes the original vector-data clustering rule and explicitly qualifies the faster representative-reuse and sampled-data enhancements. Recomputing representatives from all merged observations and selecting from old representatives need not give identical merges. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 223 preceding native IDs/names/aliases. Word-delimited fixed-string searches of both full checkouts, including ignored and hidden files, returned 2 worktree lines in discovery context and 6 main-checkout lines including four unrelated ignored dependency matches. Six neighboring native records and nine exact AIO nodes with scoped synonyms and outgoing edges were inspected.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Start with singleton clusters. Represent a cluster C by up to c selected points, with c a positive integer: choose the first farthest from its mean, then choose each next point to maximize its minimum distance to already selected points. Shrink every selected p to p+alpha(mean(C)−p), for a chosen shrink fraction in [0,1]. Define cluster distance as the minimum distance between a representative from each cluster, repeatedly merge the closest pair and stop at the requested count. In the original merge procedure recompute the mean with observation-count weights and select scattered points from the merged observations. The improved merge considers the at-most-2c old scattered points, recovered from their shrunken representatives when unshrinking is defined, and then shrinks new selections toward the merged mean. Large-data enhancements cluster a random sample, optionally partially cluster sample partitions before merging their partial clusters, and label remaining observations by the nearest selected final representative.
⚠️ Curated Limitations & Negative Results
- The mean-and-shrink description assumes a vector representation with a meaningful distance and arithmetic mean. The source’s mention of nonmetric similarities does not make the same operations defined for arbitrary categorical objects.
- The improved representative-reuse step restricts the candidate set and can alter the selected representatives and later merges. Unshrinking from locations alone is undefined at alpha=1; it requires alpha<1 or retained original scattered points.
- Sampling and partial partition clustering may miss rare groups or irreversibly combine points before the final pass. The paper’s two-stage small-cluster outlier removal is heuristic and can remove genuine small clusters.
- Representative count, shrink fraction, sampling, partitioning, distance, outlier rules and target count matter. The method does not guarantee recovery of arbitrary true shapes or universal outlier robustness, and its indexing/runtime claims are dimension-dependent. No implementation or benchmark was reproduced.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | CURE groups unlabeled observations using a specified agglomerative procedure. The AIO target is a task; this association does not assert algorithm/task equivalence or subclass membership. |
AIO:HierarchicalClustering
Hierarchical Clustering
|
related_match | CURE repeatedly merges clusters to construct a hierarchy, while the target does not specify its linkage, initialization or stopping rule. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Sudipto Guha, Rajeev Rastogi, Kyuseok Shim
|
primary paper
full_text
|
ID: https://doi.org/10.1145/276305.276312
sha256:4207acc2deb7…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T09:45:04Z
Updated: 2026-10-11T09:45:04Z
Source File:
data/curated/CUREClustering.yaml