ROCK clustering
Algorithms AIMech:ROCKClustering DRAFT
Aliases: ROCK, Robust Clustering using linKs
An agglomerative clustering procedure that merges clusters using shared-neighbor link counts divided by a cluster-size normalization derived from a neighborhood model.
Identity Notes & Concept Scope
ROCK is Guha et al.’s RObust Clustering using linKs procedure, designed for categorical or other similarity-based data. Links count common neighbors rather than direct similarities or graph cut weights. The normalized goodness is a heuristic and is not simply maximum shared-neighbor count. The record follows the 1999 conference article, not an uninspected expanded journal version. 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
On the clustering sample choose a symmetric similarity in [0,1] and threshold theta. Define N(i)={j!=i:sim(i,j)>=theta} and link(i,j)=|N(i) intersect N(j)|; excluding each point from its own neighbor list reproduces the paper’s worked link counts. For clusters A,B set Link(A,B)=sum_(i in A,j in B)link(i,j). Starting from singletons, merge the pair maximizing g(A,B)=Link(A,B)/[(|A|+|B|)^(1+2f)−|A|^(1+2f)−|B|^(1+2f)]. The paper’s experimental configuration uses f(theta)=(1−theta)/(1+theta); use 0<=theta<1 so f>0 and the denominator is positive. Update cross-cluster links additively after a merge. Stop at the requested cluster count or when every remaining cross-cluster link count is zero. The optional large-data procedure clusters a random sample and labels other observations using representative subsets L_i, choosing the cluster maximizing its threshold-neighbor count divided by (|L_i|+1)^f.
⚠️ Curated Limitations & Negative Results
- The paper introduces a neighborhood-size model and chooses f(theta) for its experiments; the normalization is not a universal theorem for every supplied similarity or data distribution. theta=1 makes the displayed experimental-normalization denominator zero.
- The graph and shared-neighbor counts depend on the supplied sample, similarity and threshold. Categorical attribute-value encoding with Jaccard similarity is one stated construction; shared-neighbor links do not guarantee semantic clustering.
- The source’s prose explicitly allows termination above the requested count when all cross-links vanish. Forcing arbitrary zero-link merges changes that stopping convention.
- Sampling and outlier details omitted from the conference article are deferred to its cited full report. This record does not invent those procedures or claim a benchmark/runtime advantage. No clustering implementation was executed.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | ROCK 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 | ROCK 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.1109/ICDE.1999.754967
sha256:735b0e5275f2…
|
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/ROCKClustering.yaml