CLASSIFICATION OF DISSIMILARITY MEASURES BETWEEN DATA CLUSTERS ACCORDING TO THE METRIC STRUCTURE OF THE APPLICATION SAMPLE SPACE

01 · What is compared, and what does “near” mean?

A classification of dissimilarity measures starts by identifying the objects being compared. An observation may be represented by a feature vector x; a cluster by a set of observations; a distribution by a probability measure; and a function by a trajectory or profile. These objects call for different constructions. Producing a number is not sufficient for an expression to define a metric distance.

Throughout, 𝒳 denotes the domain of objects, N the number of observations, and p the number of variables. The Minkowski exponent is written q to distinguish it from dimension. The symbol d is used for distances with an explicitly stated structure, δ for more general dissimilarities, and s for similarities. Smaller dissimilarities express greater proximity, whereas larger similarities usually express greater proximity.

Strictly, the sample space Ω is the set of possible outcomes of a random experiment. The feature space 𝒳 contains the representations used in the analysis. The observed sample is a finite subset, or an indexed collection, of those representations. A data matrix does not automatically identify these three notions.

02 · Metrics, completeness, and topology

A metric is a finite, nonnegative function that separates points, is symmetric, and satisfies the triangle inequality:

Identity requires both implications: a point is at zero distance from itself, and two points at zero distance must be the same point. The triangle inequality holds for every triple, including repeated points. It is not a generalization of the Pythagorean theorem, which states a particular equality in Euclidean geometry.

Completeness is an additional property of the pair (𝒳,d). A sequence is Cauchy when its terms eventually become arbitrarily close to one another:

The space is complete if every Cauchy sequence converges to an element of 𝒳. For example, ℝ with its usual distance is complete; ℚ with the inherited distance is not, since rational sequences may approach √2. A finite set of distinct points with a metric is complete: its smallest positive distance prevents a Cauchy sequence from continuing to jump between different points. Completeness is therefore not the main difficulty when clustering a finite sample.

A metric generates open sets through balls. Nevertheless, topology does not determine distance values: d and 2d generate the same open sets. Completeness of a particular metric is not a topological invariant either: ℝ and (0,1) are homeomorphic, although their usual Euclidean metrics have different completeness properties. A homeomorphism preserves topological structure; an isometry preserves distances. These are elementary checks, not assumptions about an algorithm.

03 · A classification by axioms

¹ The convention follows Stojmirović (2005): separation is required jointly in both directions. Other sources reserve “quasi-metric” for a stronger separation condition. A metric is also a quasi-metric under the inclusive convention: not requiring symmetry does not prohibit it.

² Here “semimetric” means a symmetric, nonnegative, point-separating function without a required triangle inequality. The term has several uses. McAuley (1956, p. 315, footnote 1) requires symmetry and compatibility with a topology through limit points; his definition must not be replaced by “asymmetric distance.” A function lacking the triangle inequality does not automatically support the same open-ball theory as a metric.

³ For the clustering examples, dissimilarities are finite, nonnegative, and zero on the diagonal; symmetric ones may be stored in a symmetric matrix. These conditions alone do not impose separation or the triangle inequality. The table lists requirements, not mutually exclusive classes.

04 · Minkowski, scaling, and squared distance

On ℝᵖ, the Minkowski family consists of metrics induced by norms:

The cases q=1, q=2, and q→∞ give Manhattan, Euclidean, and maximum distance. For q≥1, Minkowski’s inequality ‖u+v‖_q≤‖u‖_q+‖v‖_q guarantees the triangle inequality. For 0<q<1, the same expression with the 1/q power is not a norm and may violate it. This differs from the sum without that outer power: ∑|xⱼ−yⱼ|^q is a metric in that interval.

For x=(1,2) and y=(4,6), the absolute coordinate differences are 3 and 4: Manhattan gives 7; Euclidean gives √(9+16)=5; maximum gives 4. All three answers are consistent with different geometric rules.

The expression δ(x,y)=‖x−y‖₂² is squared Euclidean distance. It is symmetric and separates points, but it is not generally a metric. With x=0, y=1, and z=2, δ(x,z)=4 while δ(x,y)+δ(y,z)=2:

Units matter. Measuring one variable in colones and another in thousands of colones changes their relative contributions. Standardizing columns by their standard deviations is one possible decision, not a universal requirement; it needs nonzero scales and a defensible interpretation. With strictly positive weights, d(x,y)=√∑wⱼ(xⱼ−yⱼ)² remains a metric. Zero weights can produce a pseudometric; negative weights no longer guarantee a real, nonnegative distance.

The dist() implementation is documented by R Core Team (n.d.-b); its argument named p corresponds to the exponent q used in this article.

05 · Pearson, Spearman, and Kendall: from association to dissimilarity

Correlations measure association, not metric separation of original observations. They may be negative and equal 1, rather than 0, for a nonconstant profile compared with itself. They must be identified before being transformed.

Pearson

Both profiles must vary. For x=(1,2,3) and y=(2,4,6), r=1 even though x≠y and their Euclidean distance is √14. Thus 1−r ignores level and positive scale differences. This can be desirable when comparing shapes, but not when absolute magnitude matters.

Spearman

The first equality defines Spearman correlation as Pearson correlation of ranks. The second is a simplification valid without ties. With ties, assign average ranks and use the first expression. Pearson’s numerator must sum paired products, rather than multiply two centered sums that would each be zero.

Kendall

For each pair of elements i<j, C counts concordances and D discordances. T_x and T_y count pairs tied only in x or only in y; pairs tied in both are excluded from those terms. Without ties, C+D=p(p−1)/2 and τ_a=(C−D)/(C+D). A tie does not mean that two judges assign the same rank to one person: it means equality within at least one ranking for a pair of people.

Revisiting the original document’s twelve candidates: X=(1,2,…,12) and Y=(1,2,4,3,6,5,8,7,10,9,12,11). There are 66 pairs, five discordant and 61 concordant; hence τ=56/66≈0.848485. Squared rank differences sum to 10, so ρ_s=1−60/1716≈0.965035. These are different coefficients for the same comparison.

A transformation does not guarantee a metric

Consider centered profiles x=(1,−1,0), y=(1,0,−1), and z=(0,1,−1). Direct calculation gives r(x,y)=r(y,z)=1/2 and r(x,z)=−1/2. The dissimilarity 1−r gives 1/2, 1/2, and 3/2, violating the triangle inequality. Chordal distance is justified by normalization:

The identity proves that d_ch is Euclidean between normalized vectors. On the original profiles it is generally a pseudometric: profiles related by y=a·x+b·1 with a>0 have zero distance. It becomes a metric on the corresponding equivalence classes. Spearman admits the same construction after ranking and normalizing. This proof must not be extended automatically to every Kendall-based formula.

R Core Team (n.d.-a) documents rank correlation and ties; Kendall (1938, 1945) distinguishes the original coefficient and its adjustment. The calculations and counterexample above are worked out explicitly here.

06 · Pseudometrics: what information is lost

A pseudometric retains nonnegativity, symmetry, and the triangle inequality while allowing distinct objects to have zero distance. If φ:𝒳→𝒴 and d_𝒴 is a metric, then dφ(x,y)=d_𝒴(φ(x),φ(y)) is a pseudometric; it is a metric when φ is injective. The triangle inequality is inherited directly from 𝒴.

Under π(x₁,x₂)=x₁, points P=(2,3) and Q=(2,5) have zero pseudodistance because the second coordinate was discarded. This is not a mathematical contradiction: it states precisely which information the representation has removed.

Further retained examples are d(f,g)=|f(t₀)−g(t₀)| for real functions on a domain containing t₀; d(x,y)=s(x−y) when s is a seminorm; and the trivial pseudometric d≡0. Each illustrates a different source of indistinguishability.

The relation ∼ is an equivalence relation: transitivity follows from the triangle inequality. Distance between classes is well defined because replacing a representative by another at zero distance does not change the result. The quotient 𝒳/∼ is a metric space. In data analysis, this distinguishes duplicate representations from substantively identical objects.

07 · Quasi-metrics and directional comparisons

A quasi-metric allows the cost of moving from x to y to differ from the cost of returning. Under the convention used here, q(x,x)=0, the directed triangle inequality holds, and q(x,y)=q(y,x)=0 implies x=y. Nonnegativity is part of the definition.

For example, q(2,5)=3 but q(5,2)=0. One direction measures a required increase; the other has no increase to penalize. The triangle inequality follows from (a+b)₊≤a₊+b₊. The conjugate reverses direction, and the maximum of the two recovers a metric. For any quasi-metric with this joint separation condition, both max{q,q*} and q+q* are metrics.

Directed balls depend on whether q(x,y) or q(y,x) is used; the associated topology must specify that choice. Quasi-metrics can model asymmetric transformation costs, but not every asymmetric cost satisfies the triangle inequality. The discrete metric, equal to 0 for identical points and 1 otherwise, is symmetric: it belongs to the broad quasi-metric class but does not illustrate asymmetry.

08 · Set distances and linkage criteria

Let A and B be nonempty finite clusters, and d a metric between their observations. Single linkage uses the nearest pair; complete linkage the farthest; and average linkage all pairs. Hausdorff compares the largest nearest-neighbor distance in both directions:

Hausdorff is a metric on the nonempty finite subsets of a metric space, and extends to nonempty compact subsets. Separation follows because zero distance forces each point of either set to belong to the other; the triangle inequality follows by chaining nearest-neighbor approximations through the intermediate set.

Linkage criteria are not automatically metrics on sets. Single linkage can be zero for different intersecting sets. Complete and average linkage may give D(A,A)>0. Centroid distance can be zero for different sets sharing the same center. These properties are separate from the usefulness of these rules for constructing a hierarchy.

A complete example on ℝ: A={0,2}, B={5,9}. The four cross-distances are 5,9,3,7; the centroids are 1 and 7. From A, the largest nearest-neighbor distance to B is 5; from B to A it is 7. The results are:

Ward selects the merger that minimizes the increase in within-cluster sum of squares. Decomposing deviations around the merged center yields:

In this example, W(A)=2 and W(B)=8; the merged center is 4 and W(A∪B)=46, so ΔW=46−10=36. This increase is not the same quantity as centroid distance. Under the usual Euclidean Ward.D2 parameterization, height corresponds to √(2ΔW), rather than ΔW itself; the example would give √72≈8.4853.

09 · Choosing a compatible measure and algorithm

Euclidean embeddability is stronger than the metric axioms. For a finite symmetric nonnegative matrix D with zero diagonal, it can be diagnosed through B=−½JD²J, where J=I−11ᵀ/N and D² denotes elementwise squaring. An exact Euclidean representation exists when B is positive semidefinite; substantial negative eigenvalues rule it out. A numerical tolerance only addresses rounding.

Pearson correlation computed over a common set of coordinates allows chordal distance to be used as Euclidean input between normalized profiles. For Ward.D2, supply √[2(1−r)] without squaring it beforehand. This preserves the normalized geometry, not original magnitudes.

Categorical and mixed variables require constructions that respect their scales. Coding nominal categories as 1,2,3 and using Euclidean distance imposes an order and separations that may be meaningless. Hamming, Jaccard, or Gower may be considered depending on the domain, with explicit rules for absences, weighting, and missing data. Such extensions still require checking the axioms of the specific variant.

The minimum-variance criterion originates with Ward (1963); implementation differences are discussed by Murtagh and Legendre (2014) and R Core Team (n.d.-c).

10 · A reproducible experiment with six observations

This illustrative dataset is designed so that every calculation can be reconstructed; it is not an empirical sample from a population. Both variables are treated as comparable coordinates and are not standardized in this example:

The first Euclidean merger joins A and B at √1.04≈1.019804. The final single-linkage height depends on a bridge between groups; complete linkage depends on the farthest pair. Manhattan distance changes coordinate contributions. Ward generates a sequence based on increases in dispersion. Agreement of a partition at one number of groups does not imply agreement of the entire hierarchy or its heights.

At three clusters, Euclidean complete linkage gives {A,B,C}, {D,E}, {F}; Manhattan complete linkage gives {A,B,C}, {D,F}, {E}. The rest of the procedure is unchanged: changing the measure changes a merger decision. Numeric cluster labels are arbitrary.

11 · Functions, manifolds, and tensors: necessary distinctions

The word “metric” appears in related but distinct settings. Minkowski distance between vectors is induced by a norm. For function spaces and 1≤q<∞, define:

For functions considered pointwise, two functions differing only on a measure-zero set may have zero distance. Lᵠ spaces identify functions equal almost everywhere; on those equivalence classes the expression is a norm. Lᵠ spaces are complete for q≥1, but their definition requires a specified measure and integration domain.

A smooth n-dimensional manifold is locally modeled on open subsets of ℝⁿ through compatible charts. The tangent space TₐM at a point a does not require the manifold to be compact. A Riemannian metric tensor smoothly assigns a positive-definite inner product to each tangent space:

Symmetry exchanges tangent vectors, not points of the manifold. Nondegeneracy means that gₐ(u,v)=0 for every v forces u=0; in coordinates, the component matrix is invertible. Positive definiteness is an additional requirement. On a connected Riemannian manifold, integrating √g(γ̇,γ̇) along curves and taking the infimum defines intrinsic distance between points.

A pseudo-Riemannian metric allows indefinite signature. For example, g(v,v)=−v₀²+v₁²+⋯+vₙ² can be positive, negative, or zero with v≠0. Such a form does not automatically yield a nonnegative dissimilarity suitable for the preceding algorithms. Minkowski spacetime geometry must be distinguished from the Minkowski norm family.

Finally, tensor order and dimension are different concepts: an order-two tensor can have an n×n component matrix. Tensorial status requires a transformation law. For a covariant order-two tensor:

In Cartesian Euclidean coordinates, g̃ₐᵦ=δₐᵦ, giving the special case gᵢⱼ=∑ₐ(∂ξᵃ/∂xⁱ)(∂ξᵃ/∂xʲ). A data matrix can represent different mathematical objects; rectangular arrangement alone does not identify it as a metric tensor. These distinctions preserve the connection to geometry without assigning a differential structure to a clustering problem before that structure has been constructed.

The algebraic definitions of nondegeneracy and signature can be checked in SageMath Developers (n.d.). Distinguishing these structures from clustering criteria is part of this revision’s argument.

12 · R code and checks

The following program uses only packages included with R. It downloads no data and installs no dependencies. It rejects nonfinite inputs to maintain a common domain and produces tables, diagnostics, and a PDF containing four dendrograms. The audit_distance function checks all sample triples and explicitly has cubic cost.

# Dissimilarity measures: verifiable examples using base R.
# Run: Rscript dissimilarity_reproducible_examples.R [output_directory]
# Columns are comparable coordinates; they are not standardized in this example.
args <- commandArgs(trailingOnly = TRUE)
out_dir <- if (length(args)) args[1L] else "disimilaridad_resultados"
dir.create(out_dir, recursive = TRUE, showWarnings = FALSE)

audit_distance <- function(D, tol = 1e-10) {
  # Exhaustive finite-matrix audit: O(N^3) time.
  D <- as.matrix(D)
  if (!is.numeric(D) || nrow(D) != ncol(D) || nrow(D) < 1L ||
      any(!is.finite(D)) || length(tol) != 1L || !is.finite(tol) || tol <= 0) {
    stop("A finite square numeric matrix and tol > 0 are required.")
  }
  n <- nrow(D)
  eps <- tol * max(1, abs(D))
  diagonal_zero <- max(abs(diag(D))) <= eps
  nonnegative <- min(D) >= -eps
  symmetric <- max(abs(D - t(D))) <= eps
  separated <- if (n == 1L) TRUE else all(D[row(D) != col(D)] > eps)
  max_violation <- -Inf
  for (k in seq_len(n)) {
    max_violation <- max(max_violation, D - outer(D[, k], D[k, ], "+"))
  }
  triangle <- max_violation <= eps
  euclidean <- NA
  min_eigenvalue <- NA_real_
  if (nonnegative && diagonal_zero && symmetric) {
    J <- diag(n) - matrix(1 / n, n, n)
    B <- -0.5 * J %*% (D^2) %*% J
    eigenvalues <- eigen((B + t(B)) / 2, symmetric = TRUE,
                         only.values = TRUE)$values
    min_eigenvalue <- min(eigenvalues)
    euclidean <- min_eigenvalue >= -tol * max(1, abs(eigenvalues))
  }
  c(diagonal_zero = diagonal_zero, nonnegative = nonnegative,
    symmetric = symmetric, separated = separated, triangle = triangle,
    metric = diagonal_zero && nonnegative && symmetric && separated && triangle,
    max_triangle_violation = max(0, max_violation),
    euclidean = euclidean, min_gram_eigenvalue = min_eigenvalue)
}

X <- rbind(A = c(0, 0), B = c(1, 0.2), C = c(0.3, 2.4),
           D = c(3.5, 3.1), E = c(5.2, 1.3), F = c(5.9, 4.0))
colnames(X) <- c("x1", "x2")
stopifnot(all(is.finite(X)))
D_e <- as.matrix(dist(X, method = "euclidean"))
D_m <- as.matrix(dist(X, method = "manhattan"))
D_i <- as.matrix(dist(X, method = "maximum"))
stopifnot(isTRUE(all.equal(dist(X, method = "minkowski", p = 2),
                         dist(X), check.attributes = FALSE)))
write.csv(X, file.path(out_dir, "observaciones.csv"))
write.csv(D_e, file.path(out_dir, "distancias_euclidianas.csv"))

# Counterexample 1: squaring can break the triangle inequality.
D_line <- as.matrix(dist(matrix(0:2, ncol = 1)))
check_squared <- audit_distance(D_line^2)
stopifnot(check_squared["triangle"] == 0,
          abs(check_squared["max_triangle_violation"] - 2) < 1e-10)

# Counterexample 2: 1-r can break the triangle inequality.
profiles <- rbind(x = c(1, -1, 0), y = c(1, 0, -1), z = c(0, 1, -1))
stopifnot(all(apply(profiles, 1, sd) > 0))
R <- cor(t(profiles), use = "all.obs", method = "pearson")
D_corr <- 1 - R
D_chord <- sqrt(pmax(2 * D_corr, 0))
dimnames(D_chord) <- dimnames(R)
U <- profiles - rowMeans(profiles)
U <- U / sqrt(rowSums(U^2))
stopifnot(isTRUE(all.equal(unname(D_chord), unname(as.matrix(dist(U))),
                         tolerance = 1e-10)))
stopifnot(audit_distance(D_corr)["triangle"] == 0,
          audit_distance(D_chord)["metric"] == 1)

# Same normalized profile: distinct original objects, zero distance.
x <- c(1, 2, 3)
y <- c(2, 4, 6)
stopifnot(abs(cor(x, y) - 1) < 1e-12,
          abs(sqrt(sum((x - y)^2)) - sqrt(14)) < 1e-12)

# Pseudometric and quasi-metric: both directions are retained.
P <- rbind(P = c(2, 3), Q = c(2, 5), S = c(4, 1))
D_projection <- abs(outer(P[, 1], P[, 1], "-"))
v <- c(2, 5, 8)
Q <- outer(v, v, function(a, b) pmax(b - a, 0))
Q_s <- pmax(Q, t(Q))
stopifnot(audit_distance(D_projection)["separated"] == 0,
          Q[1, 2] == 3, Q[2, 1] == 0,
          audit_distance(Q)["triangle"] == 1,
          audit_distance(Q_s)["metric"] == 1)

# Twelve candidates: five adjacent inversions, no ties.
rank_x <- 1:12
rank_y <- c(1, 2, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11)
pairs <- combn(12L, 2L)
signs <- apply(pairs, 2, function(ij) {
  sign((rank_x[ij[1]] - rank_x[ij[2]]) *
         (rank_y[ij[1]] - rank_y[ij[2]]))
})
concordant <- sum(signs > 0)
discordant <- sum(signs < 0)
rho_s <- cor(rank_x, rank_y, method = "spearman")
tau <- cor(rank_x, rank_y, method = "kendall")
stopifnot(concordant == 61, discordant == 5,
          abs(tau - 56 / 66) < 1e-12,
          abs(rho_s - (1 - 60 / 1716)) < 1e-12)

# With ties, Spearman is Pearson correlation of average ranks.
tie_x <- c(1, 1, 3, 4)
tie_y <- c(2, 3, 3, 5)
stopifnot(isTRUE(all.equal(cor(tie_x, tie_y, method = "spearman"),
                          cor(rank(tie_x), rank(tie_y)))))

# Clusters A={0,2}, B={5,9}: one-dimensional comparisons.
cluster_A <- c(0, 2)
cluster_B <- c(5, 9)
cross <- abs(outer(cluster_A, cluster_B, "-"))
hausdorff <- max(apply(cross, 1, min), apply(cross, 2, min))
delta_W <- length(cluster_A) * length(cluster_B) /
  (length(cluster_A) + length(cluster_B)) *
  (mean(cluster_A) - mean(cluster_B))^2
cluster_results <- c(single = min(cross), complete = max(cross),
                     average = mean(cross), centroid = abs(mean(cluster_A) -
                     mean(cluster_B)), Hausdorff = hausdorff, Ward_deltaW = delta_W)
stopifnot(isTRUE(all.equal(unname(cluster_results), c(3, 9, 6, 6, 7, 36))))

fits <- list(
  euclidean_complete = hclust(as.dist(D_e), method = "complete"),
  euclidean_single = hclust(as.dist(D_e), method = "single"),
  manhattan_complete = hclust(as.dist(D_m), method = "complete"),
  euclidean_wardD2 = hclust(as.dist(D_e), method = "ward.D2")
)

# Check every Ward.D2 height against the actual increase in W.
hc <- fits$euclidean_wardD2
groups <- vector("list", nrow(hc$merge))
ward_check <- numeric(nrow(hc$merge))
for (i in seq_len(nrow(hc$merge))) {
  get_group <- function(j) if (j < 0) -j else groups[[j]]
  a <- get_group(hc$merge[i, 1])
  b <- get_group(hc$merge[i, 2])
  delta <- length(a) * length(b) / (length(a) + length(b)) *
    sum((colMeans(X[a, , drop = FALSE]) - colMeans(X[b, , drop = FALSE]))^2)
  ward_check[i] <- sqrt(2 * delta)
  groups[[i]] <- c(a, b)
}
stopifnot(isTRUE(all.equal(hc$height, ward_check, tolerance = 1e-10)))

diagnostics <- rbind(
  euclidean = audit_distance(D_e), manhattan = audit_distance(D_m),
  maximum = audit_distance(D_i), squared_line = check_squared,
  one_minus_r = audit_distance(D_corr), chordal = audit_distance(D_chord),
  projection = audit_distance(D_projection), directed = audit_distance(Q),
  symmetrized = audit_distance(Q_s)
)
write.csv(diagnostics, file.path(out_dir, "diagnosticos.csv"))
write.csv(as.data.frame(cluster_results), file.path(out_dir, "criterios_conglomerados.csv"))
write.csv(data.frame(concordant, discordant, rho_s, tau),
          file.path(out_dir, "rangos.csv"), row.names = FALSE)
heights <- do.call(cbind, lapply(fits, function(h) h$height))
colnames(heights) <- names(fits)
write.csv(heights, file.path(out_dir, "alturas.csv"), row.names = FALSE)
partitions <- do.call(cbind, lapply(fits, cutree, k = 3))
write.csv(partitions, file.path(out_dir, "particiones_k3.csv"))
for (name in names(fits)) {
  h <- fits[[name]]
  write.csv(data.frame(left = h$merge[, 1], right = h$merge[, 2], height = h$height),
            file.path(out_dir, paste0("fusiones_", name, ".csv")), row.names = FALSE)
}

pdf(file.path(out_dir, "dendrogramas.pdf"), width = 9, height = 7,
    bg = "#fffdf7", family = "serif", useDingbats = FALSE)
par(mfrow = c(2, 2), mar = c(3, 4, 3, 1), col = "#2c2418",
    col.axis = "#2c2418", col.lab = "#2c2418", col.main = "#8b4513")
titles <- c("Euclidean / complete", "Euclidean / single",
            "Manhattan / complete", "Euclidean / Ward.D2")
for (i in seq_along(fits)) {
  plot(fits[[i]], main = titles[i], sub = "", xlab = "", ylab = "Height", hang = -1)
}
invisible(dev.off())
capture.output(sessionInfo(), file = file.path(out_dir, "sessionInfo.txt"))
print(round(diagnostics, 8))
print(cluster_results)
print(data.frame(concordant, discordant, rho_s, tau))
print(round(heights, 8))
print(partitions)
cat("Checks completed. Results in:", normalizePath(out_dir), "\n")

13 · References and scope of the revision

The short proofs, counterexamples, and A–F dataset are instructional developments of this revision. References ground conventions and allow implementation checks; synthetic examples are not attributed to those authors.

Additional R documentation: cor() · hclust().