Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 17:48, 31 October 2016

Revision as of 17:49, 31 October 2016

Line 152:

If <math>d(A,B)</math> is the smallest of the three distances on the right hand side (as would necessarily be true if <math>A</math> and <math>B</math> are mutual nearest-neighbors) then the negative contribution from its term is cancelled by the <math>n_C</math> coefficient of one of the two other terms, leaving a positive value added to the weighted average of the other two distances. Therefore, the combined distance is always at least as large as the minimum of <math>d(A,C)</math> and <math>d(B,C)</math>, meeting the definition of reducibility.

ThereforeBecause Ward's distance is reducible, the nearest-neighbor chain algorithm using Ward's distance calculates exactly the same clustering as the standard greedy algorithm. For {{mvar|n}} points in a [[Euclidean space]] of constant dimension, it takes time {{math|''O''(''n''²)}} and space {{math|''O''(''n'')}}.<ref name="murtagh-hmds"/>

===Complete linkage and average distance===