Home / Curated / Algorithms / Nearest-neighbor-chain clustering

Nearest-neighbor-chain clustering

Algorithms AIMech:NearestNeighborChainClustering DRAFT

Aliases: Nearest neighbor chain algorithm, NN-chain clustering

An agglomerative clustering algorithm that follows a chain of nearest clusters until its last pair are reciprocal nearest neighbors, merges that pair, and reuses the remaining chain; for suitable distance updates, sorting and relabeling the recorded merges produces a valid stepwise hierarchy.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 651 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 21, 0, 0 lines. All distinct match contents were read, including generated index rows repeating the fully read Ward record. Recovery hits concern Ward implementation context, its saved review or pending discovery/source notes; none identifies an existing standalone chain record. Both other checkouts returned no matches including ignored and hidden files. Semantic matching covered 26 AIO and 168 native definitions, all read; unchanged definitions were byte-compared with the preceding full assessment. 9 full annotated AIO node/edge/generated contexts and 4 full native records were inspected. The chain is an agglomerative merge-search procedure parameterized by linkage. It differs from the Ward ESS criterion, centroid reassignment in k-means, CURE representatives, BIRCH compression, nearest-neighbor label voting and batch reciprocal-neighbor passes. Retain the conditional stepwise-output identity rather than treating all nearest-neighbor algorithms or all fastcluster entrypoints as aliases.

Claims & Grounded Evidence

6 Claims

Mechanism #reciprocal-chain

Begin with a current cluster and repeatedly find a nearest distinct cluster. Prefer the preceding chain member when it is tied for nearest, so a reciprocal pair terminates the chain. Merge that pair, update distances and cluster sizes, and continue from the retained prefix or restart when it is exhausted. The chain avoids restarting a full global pair search after every merge.

supports Source: Construction d’une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques · Locator: Sections2.2–2.5 and3, printed pp.211–218 / PDF pp.4–11
supports Source: Programme de classification hiérarchique par l’algorithme de la recherche en chaîne des voisins réciproques · Locator: Sections1–2, printed pp.219–220 / PDF pp.2–3; CADENA listing, printed pp.223–224 / PDF pp.6–7
supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section3.2 and Figure 4, PDF pp.11–16

Scope #update-law-conditions

The cited sufficient conditions require reducibility and invariance of the distance between two disjoint merged pairs to their merge order. Reducibility means d(A,B)≤min(d(A,C),d(B,C)) implies min(d(A,C),d(B,C))≤d(A∪B,C). Reducibility alone is insufficient for arbitrary history-dependent updates. The paper establishes the conditions for single, complete, average, weighted and Ward linkage; centroid and median updates are outside this guarantee.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section3.2, Equation1, Theorem 1, Proposition2 and footnote1, PDF pp.12–16

Mechanism #stepwise-output-and-ties

A reciprocal pair need not be the globally closest current pair, so discovery-order merge heights can be unsorted. To obtain the stated stepwise dendrogram, stably sort the recorded merges by height and relabel their cluster representatives while preserving the dependency order of tied merges. Under the stated conditions, this yields a valid greedy stepwise hierarchy; it need not reproduce one particular arbitrary global tie convention or a unique tree.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section2.2 and Section3.2, Figures4–5, PDF pp.4–5,11–16
supports Source: fastcluster src/fastcluster_python.cpp · Locator: generate_SciPy_dendrogram, src/fastcluster_python.cpp lines108–145 at the pinned commit
supports Source: fastcluster src/fastcluster.cpp · Locator: node comparator, lines225–232; union_find, lines366–403 at the pinned commit

Scope #matrix-complexity

In the stored-dissimilarity setting with constant-time scalar distance updates, the chain algorithm takes quadratic time in the number of observations and linear auxiliary space beyond the writable quadratic-size distance matrix. This is not a linear-total-memory claim or a guarantee for arbitrary high-dimensional distance evaluation; vector implementations require a separate analysis.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Section4.1, PDF p.20
supports Source: Construction d’une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques · Locator: Section2.5, printed p.214 / PDF p.7

Scope #procedure-versus-linkage

The chain specifies how merge candidates are found; the chosen linkage defines cluster dissimilarity. It can implement the Ward ESS criterion but is not identical to Ward clustering, a nearest-neighbor classifier, or the earlier procedure that repeatedly finds and merges batches of reciprocal pairs. The cited correctness result establishes valid stepwise output; it does not assert globally optimal fixed-count partitions.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Sections2 and3.2, PDF pp.3–8,11–16
supports Source: Construction d’une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques · Locator: Section1, printed pp.209–210 / PDF pp.2–3
supports Source: La classification hiérarchique ascendante selon la méthode des voisins réciproques · Locator: Introduction and Sections3.2 and4.2, printed pp.135–136,140–142 / PDF pp.2–3,7–9

Limitation #implementation-boundaries

Both Figure 4 of the 2011 paper and the later pinned fastcluster matrix implementation restart at a chain length or tip count of at most three. The pinned code retains premerge cluster sizes, uses explicit root handling and stable output sorting, and its Ward matrix wrapper squares inputs and square-roots output heights. These inspected details clarify the implemented conventions without certifying every printed listing or floating-point variant. The same repository uses a generic algorithm for vector Ward input and documents removal of its earlier vector chain implementation.

supports Source: Modern hierarchical, agglomerative clustering algorithms · Locator: Figure4, NN-CHAIN-CORE line6, PDFp13: length(chain) ≤3
supports Source: fastcluster src/fastcluster.cpp · Locator: NN_chain_core lines574–778; f_ward lines530–545; union_find lines366–403
supports Source: fastcluster src/fastcluster_python.cpp · Locator: Matrix dispatch/preprocessing/postprocessing lines290–353; vector dispatch lines1164–1193; dendrogram output lines108–145
supports Source: fastcluster NEWS.txt · Locator: Version1.1.2 entry dated 11 October 2011

⚠️ Curated Limitations & Negative Results

Scope is finite symmetric nonnegative dissimilarities and appropriate linkage updates. General dissimilarity matrices need not be metric, while Ward’s Euclidean ESS interpretation requires its geometry and distance-scale conventions. No automatic cluster-count selection or class-label prediction is implied.
Theorem 1 supplies sufficient update-law conditions; this record does not claim they are necessary or certify every proof. A five-point sum-of-three-distances update satisfies reducibility but fails the disjoint-merge condition and yields a different invalid stepwise result.
Figure 4 prints length(chain) ≤3, consistent with the pinned implementation; its three-entry restart does not access chain[-4]. An earlier curator reading incorrectly substituted <3 and is explicitly rejected in the discovery correction. Separate Figure 5 root/union notation and Figure 2 Ward/centroid/median scaling still require care. No claim is made that the printed pseudocode was executed unchanged.
The original French batch and chain sources have different output and tie conventions. De Rham’s displayed equality of nearest-distance minima is not itself a sufficient definition of reciprocity, and its all-pairs batch instruction needs tie handling. These are retained as source boundaries, not adopted as chain instructions.
All 29 pages of Müllner 2011 v1, 11 of Benzécri 1982, 8 of Juan 1982 and 11 of de Rham 1980 were visually read. Only named ranges of the pinned C++ files and the complete README, NEWS and license were statically inspected. No author program, package or historical benchmark was executed.
Finite curator calculations check 11,664 four-object matrix/start/linkage cases and 324 one-dimensional Ward/start cases, predecessor tie handling, discovery-order sorting, the published reducibility counterexample and the actual ≤3 restart guard and safe longer-chain indexing. They are not a universal proof, floating-point audit or benchmark replication.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:HierarchicalClustering` Hierarchical Clustering	related_match	The procedure builds an agglomerative hierarchy. The pinned target denotes a clustering task; this algorithm is related without asserting task/algorithm equivalence or subclass membership.
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	The selected setting groups unlabeled objects using dissimilarities. The AIO task does not specify reciprocal chains, admissible update laws or stepwise output.

Evidence Sources & Primary Literature

7 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`mullner2011`	Modern hierarchical, agglomerative clustering algorithms Daniel Müllner	primary paper full_text	ID: arXiv:1109.2378v1 sha256:3d8ea802c328…
`benzecri1982`	Construction d’une classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques J.-P. Benzécri	primary paper full_text	sha256:2569b4b21a2e…
`juan1982`	Programme de classification hiérarchique par l’algorithme de la recherche en chaîne des voisins réciproques J. Juan	primary paper full_text	sha256:3710466686c4…
`derham1980`	La classification hiérarchique ascendante selon la méthode des voisins réciproques C. de Rham	primary paper full_text	sha256:c62314df59e7…
`fastcluster-core`	fastcluster src/fastcluster.cpp Daniel Müllner, fastcluster contributors	official documentation documentation	ID: 9d0e48609283edaae90593a6967d3f2217786d2d sha256:9ba52420e373…
`fastcluster-wrapper`	fastcluster src/fastcluster_python.cpp Daniel Müllner, fastcluster contributors	official documentation documentation	ID: 9d0e48609283edaae90593a6967d3f2217786d2d sha256:b7fc7d732572…
`fastcluster-news`	fastcluster NEWS.txt Daniel Müllner, fastcluster contributors	official documentation documentation	ID: 9d0e48609283edaae90593a6967d3f2217786d2d sha256:087eb9c9afab…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-13T21:17:01Z

Updated: 2026-10-13T21:24:56Z

Source File: data/curated/NearestNeighborChainClustering.yaml