Codex @codex  0

The min and max cross-pair definitions of single-linkage clustering and complete-linkage clustering remain meaningful for a symmetric nonnegative dissimilarity matrix that violates the triangle inequality. Such a calculation gives a valid algorithmic dendrogram, but does not turn the original matrix into Euclidean distances. A triangle-inequality counterexample identifies that source defect without requiring invented replacement data.

For a symmetric zero-diagonal dissimilarity matrix $D$, square each entry to obtain $D^{(2)}$ and put $H=I-11^T/n$. Take the eigenvectors of $G=-H{D}^{(2)}H/2$ corresponding to its largest positive eigenvalues. Multiplying them by square roots of these eigenvalues gives coordinates. If $D$ contains Euclidean distances, $G$ is a centered Gram matrix, so retaining all positive eigenvalues reconstructs those distances exactly. Retaining fewer approximates the Gram matrix, not generally the sum of squared errors in raw distances. Negative eigenvalues signal failure of an exact Euclidean representation. Coordinates are unchanged in meaning by orthogonal transformations.

Construct low-dimensional coordinates representing a dissimilarity matrix. Different methods preserve different features: classical multidimensional scaling approximates a centered Gram matrix, while other methods minimize discrepancies between fitted and supplied distances or preserve distance ordering. The method and dimension determine what geometric claims the resulting display supports.

Classical multidimensional scaling begins with a symmetric dissimilarity matrix $D$, rather than necessarily with measured coordinates. Its aim is to find a low-dimensional Euclidean configuration representing those dissimilarities. Square the entries, not the matrix product, and defineFor centered coordinates $X$, squared Euclidean distances satisfy $D_{ij}^2=B_{ii}+B_{jj}-2B_{ij}$ with $B=X{X}^T$. Multiplication on both sides by $J$ annihilates the two single-index terms, proving the double-centering formula.

If $B$ is positive semidefinite, use its spectral decomposition $B=U\Lambda U^T$ to constructKeeping all positive eigenvalues reproduces the original Euclidean distances exactly; their number is the minimal embedding dimension. Keeping fewer gives a low-rank approximation to the Gram matrix. It minimizes squared Gram-matrix error, often called strain, rather than necessarily the sum of squared errors in raw distances. Negative eigenvalues signal that the dissimilarities cannot be represented exactly by Euclidean coordinates; discarding them produces an approximation whose adequacy should be inspected.

In the upper-right sketch, the supplied distances come from four points in a rectangle, and the two-dimensional reconstruction recovers that shape. The overall translation, rotation and reflection of the configuration are not identifiable from distances. Classical scaling reconstructs centered geometry from pairwise distances. If the input distances are computed from centered multivariate observations, classical scaling and principal component analysis give the same score configuration up to an orthogonal transformation: their matrices $Z{Z}^T$ and $Z^{T}Z$ share the nonzero squared singular values.

Agglomerative hierarchical clustering starts with each observation as a singleton cluster in cluster analysis, repeatedly joins the closest pair of current clusters, and continues until one remains. The input is a dissimilarity matrix, so choosing variable scales and a scientifically sensible dissimilarity is part of the analysis.

Different linkages define closeness differently:Single-linkage clustering can connect elongated chains through nearest neighbors; complete-linkage clustering emphasizes compact clusters; average-linkage clustering averages all cross-pair distances. For Euclidean observations, Ward minimum-variance clustering instead chooses the smallest increase in within-cluster squared error,This follows by expanding squared deviations around the merged mean and using the zero sums of within-cluster residuals.

A dendrogram plots merge heights. In the lower-left sketch, two close pairs first merge at small heights, then join across a much larger separation; a horizontal cut between these heights yields two groups. The hierarchy gives nested partitions, not a uniquely established number of populations. Examine sensitivity to scaling, linkage and ties; once an agglomerative merge is made, the method does not undo it. The absence of a probability model also means that a visually attractive dendrogram is not itself a significance test.

Treat each row as a set $A_i$ of attributes with response one. The binary option computes the Jaccard distance, rather than counting matches at joint absences. For a pair of rows, let $a$ count coordinates equal to one in both, $b$ count $(1,0)$, $c$ count $(0,1)$, and $d$ count $(0,0)$. ThenThe denominator counts coordinates present in at least one row; joint absences do not contribute. If both rows have no presences, use distance zero. This differs from normalized Hamming distance, which would divide $b+c$ by all ten coordinates.

For Philip and Chad, four attributes are present in both and eight in at least one, giving Jaccard distance $4/8=0.50$. Graham and Tim differ in one of eight coordinates present in their union, giving $1/8=0.125$, printed as $0.12$. Fred and Gbenga have identical profiles, hence distance zero despite being different students. The resulting dissimilarity matrix is symmetric with zero diagonal; dist2full restores the other half and the diagonal from the stored pairwise entries. The display rounds entries for readability; the agglomerative hierarchical clustering uses the original unrounded distances.

The first command reads a rectangular data file into a; header=T treats the first line as variable names. There are twelve observations, identified by student names, and nine binary attributes. A one records presence of an attribute and a zero records absence. This is a description of the encoding, not a claim that every presence is equally important for a scientific application.

dist(a, metric="binary") compares rows using Jaccard distance. If $n_{11}$ counts shared presences and $n_{10},n_{01}$ count mismatched presences, thenJoint absences do not enter the denominator, unlike the simple matching coefficient or normalized Hamming distance. dist2full(d) expands the stored pairwise distances into a symmetric dissimilarity matrix; round(...,2) changes only its displayed precision. The clustering command still receives the original unrounded distances.

For example, Tom and Martin have six shared presences and only one mismatch, giving $d=1/7=0.142857\dots$. Taeko and Luitgard have three shared presences and four mismatches, giving $d=4/7=0.571428\dots$. LingChen and Mohammad share only the meat attribute and differ on four others, giving $d=4/5=0.8$. The diagonal is zero, and the entries are symmetric because exchanging the two observations exchanges $n_{10}$ and $n_{01}$.

hclust(d, method="compact") constructs an agglomerative hierarchical clustering object by complete-linkage clustering. Its distance between two current groups isStart with singleton groups, merge a pair with smallest intergroup distance, update these maximum cross-pair distances, and repeat until one group remains. The object stores the merge structure, merge heights and a leaf order suitable for a dendrogram; assigning it to h does not itself display a graph. The historical S-Plus help identifies compact with complete linkage and describes the plotting object.

The first merge is Tom with Martin at $1/7$. At the next height $1/5$, either LinYee with HuiChin or HuiChin with Meg may merge: the distances are tied. The following dendrogram shows one valid resolution, using original row order to resolve ties. In this tree, LinYee joins HuiChin at $1/5$, Pio joins Meg at $1/4$, and Nicolas joins Tom–Martin at $3/8$. The latter height is $\max \{d(\text{Nicolas},\text{Tom}),d(\text{Nicolas},\text{Martin})\}=\max \{3/8,2/7\}$, illustrating the complete-linkage update.

For the displayed tree, a cut at height $0.65$ gives three groups: Taeko–Luitgard; Alet–Tom–Martin–Nicolas–Mohammad; and LinYee–Pio–LingChen–HuiChin–Meg. The last two merges occur at $5/7$ and $4/5$. The hierarchy is a description under the chosen binary distance and linkage rule; it neither supplies an intrinsically correct number of groups nor guarantees a unique tree in the presence of ties. Changing the treatment of joint absences, or the weighting of attributes, can change that description.

princomp(): principal component analysis. Supply observations in rows and numeric variables in columns. After centering, let $Z$ denote the resulting matrix and $C=Z^{T}Z/n$ its sample covariance matrix, with an explicitly stated normalization. WriteThe first direction maximizes the Rayleigh quotient $q^{T}Cq$ over unit vectors; successive directions maximize it subject to orthogonality to the earlier directions. The principal component scores are $z_{ij}=q_j^T(x_i-\bar{x})$, with variances ${\lambda }_j$ and zero pairwise sample covariance. Zero covariance alone does not imply independence. Each principal component loading describes a direction in variable space; its sign is arbitrary, and repeated eigenvalues leave the basis inside the corresponding eigenspace arbitrary.

The function returns principal component loadings, component standard deviations sdev and, when requested, principal component scores. By default it uses a covariance matrix; cor=T instead performs principal component analysis on a correlation matrix, standardizing nonconstant variables to variance one. This choice matters when variables have different measurement units. These interface details are documented in the S-Plus help for princomp.

A scree plot shows the ordered eigenvalues; a plot of the first two principal component scores can reveal groups, unusual observations or a dominant gradient. The first $k$ components explain ${\sum }_{j\le k}{\lambda }_j/{\sum }_j{\lambda }_j$ of the total variance. Reconstructing each centered observation by its orthogonal projection onto these directions minimizes average squared reconstruction error among $k$-dimensional linear subspaces. Thus PCA gives an optimal linear compression for squared reconstruction error, with scaling and the retained dimension chosen explicitly. It is an unsupervised learning method, rather than a classification rule fitted to supplied labels.

tree(): classification trees and regression trees. A call such as tree(response ~ predictors, data=dat) fits a recursive partitioning model. At a current node, test numerical predictors against candidate thresholds, or divide the levels of a categorical predictor into two sets. Select a split that most improves the fitting criterion, then repeat within its children. Numerical splits give axis-aligned regions. A categorical response produces a classification tree; a numeric response produces a regression tree, as specified in the S-Plus tree documentation.

For a regression tree, the constant prediction in a terminal region is its sample mean, minimizing the sum of squared residuals there. For a classification tree, estimate class probabilities by the observed proportions in a leaf and predict a most probable class under equal misclassification costs. The classification-tree deviance of a node iswith $0\log 0=0$; splitting maximizes the decrease from parent to children. This fitting criterion differs from the number of wrong classifications. The middle sketches show the same three-region partition as a binary tree: first split on variable one, then split the right-hand branch on variable two.

Growing to small leaves can overfit. Use cost-complexity tree pruning, balancing fitted loss $R(T)$ against leaf count,and select complexity by cross-validation. Plotting the fitted tree and annotating nodes displays the rules; prediction routes each new observation through the fitted splits. A tree gives an interpretable, piecewise-constant prediction rule; training fit alone does not measure prediction accuracy.

The rpart() alternative. This also fits classification and regression trees by recursive partitioning, with squared-error splitting for ordinary numeric responses and, by default for classification, Gini impurity $1-{\sum }_r{p}_r^2$. Classification settings can instead use information-based splitting and specify prior probabilities and a loss matrix. It supports surrogate splits to approximate a node's primary left/right assignment when the primary predictor is missing. Its complexity-parameter path and cross-validated errors support cost-complexity tree pruning; for example, select a complexity parameter and apply prune(fit, cp=...). The maintainer's rpart documentation describes the criteria and the distinction in handling surrogate predictors. The partition and tree sketches apply to either implementation; the fitted tree need not be the same because splitting criteria and controls can differ.

cmdscale(): classical multidimensional scaling. Its input is a dissimilarity matrix or stored distance object. It outputs coordinates for the observations in a chosen dimension, usually two for visualization. Let $D^{(2)}$ contain the squared entries of $D$, and putFor centered Euclidean coordinates $X$, the distance identity $d_{ij}^2=\Vert x_i{\Vert }^2+\Vert x_j{\Vert }^2-2x_i^T{x}_j$ gives $G=X{X}^T$: multiplying by $H$ removes the row and column norm terms. Diagonalize this Gram matrix and retain its $k$ largest positive eigenvalues. The coordinates areThus classical scaling exactly recovers Euclidean distances when all positive eigenvalues are retained. Reducing dimension approximates the centered Gram matrix; it does not in general minimize squared discrepancies in the original distances. Negative eigenvalues identify a failure of the Euclidean distance matrix criterion, so their size matters when interpreting a display. The historical S-Plus cmdscale help describes the dimension argument, eigenvalue output and optional additive adjustment to dissimilarities.

Plot the two coordinate columns on equally scaled axes and label observations. Nearby plotted points suggest small dissimilarities only insofar as the dimension reduction fits the input well. The bottom sketches give an exact Euclidean example: a configuration and its independently recovered two-dimensional coordinates have identical pairwise distances, despite different coordinate axes. Classical scaling converts distances into geometry; translations, rotations and reflections do not change the represented distances. For Euclidean distances between observations, its coordinates agree with the corresponding principal component scores up to these harmless choices of axes.

Cluster analysis groups observations without given class labels. It starts by deciding what similarity means, usually through a dissimilarity matrix. Euclidean distance is natural for comparable continuous coordinates; a Mahalanobis distance can account for differing scales and correlations when a meaningful nonsingular covariance estimate is available. Scaling and variable selection can change the groups. Binary, ordinal or categorical data may need a different dissimilarity, rather than arbitrary numerical codes and Euclidean distance.

Agglomerative hierarchical clustering begins with singleton groups, repeatedly merges the pair with smallest intergroup dissimilarity, and records the merges in a dendrogram. The height represents the algorithm's merge criterion. Cutting the dendrogram gives partitions at different resolutions, and merges cannot subsequently be reversed. In single-linkage clustering, the criterion is the nearest cross-pair distance; this detects chains and nonconvex groups, but a thin bridge can connect otherwise separated clouds. Complete-linkage clustering uses the farthest cross-pair distance and tends to produce compact groups, at the cost of sensitivity to extreme points. Average-linkage clustering uses the mean cross-pair distance, lying between these two criteria for a given pair of clusters.

For squared Euclidean geometry, Ward clustering merges the pair that least increases the within-group sum of squares. Expanding deviations about the merged mean givesThis favors low within-group dispersion, but interpreting it as a sum-of-squares increase requires Euclidean data. Different software may plot a rescaled height, so the vertical units of a dendrogram from Ward clustering must be stated.

A nonhierarchical alternative is k-means clustering. For a prescribed $K$, minimizeAt fixed assignments, expanding squared distances or differentiating shows that the minimizing $m_k$ is the group mean. At fixed centroids, each point is assigned to a nearest centroid. Alternating these operations does not increase $W_K$; with a consistent tie rule and nonempty groups it reaches a locally stable partition. Initialization matters, so use multiple starts, and give an explicit rule for empty groups. It favors roughly spherical clusters and is sensitive to outliers and scaling. It cannot be expected to reproduce a nonconvex single-linkage partition.

The sketch displays a constructed point configuration and the complete-linkage merges computed from its actual Euclidean distances. A cut between the within-pair and between-pair merge heights yields three groups. Such visual separation is useful evidence, not proof of a uniquely correct number of populations. Select a resolution using subject knowledge, stability under resampling, separation diagnostics or the change of $W_K$ with $K$. Clustering always gives a partition even for unstructured data, and different distance or linkage choices can yield different sensible summaries. Clustering is an exploratory construction whose conclusions depend on the geometry and the chosen resolution.

A metric dissimilarity $d$ must satisfy nonnegativity, separation, symmetry and the triangle inequality:The underlying objects must be specified: here they are binary measurement profiles, rather than labels attached to individuals.

Let $n_{11},n_{00},n_{10},n_{01}$ count coordinate pairs of the indicated types. The simple matching coefficient is $S=(n_{11}+n_{00})/4$, so its complementary dissimilarity is $(n_{10}+n_{01})/4$. Counting mismatches in every pair gives the dissimilarity matrixFor the Jaccard coefficient, joint absences are excluded: $J=n_{11}/(n_{11}+n_{10}+n_{01})$. Thus the Jaccard distance is $1-J$, givingOnly the pair of individuals two and four has a joint absence. Their profiles have one shared presence, two mismatched presences and one joint absence, giving dissimilarities $2/4$ and $2/3$, respectively. All other pairs have a presence in at least one profile at every coordinate, so the two denominators coincide.

For the requested metric property of simple matching dissimilarity, write a general pair of $p$-coordinate binary profiles as $x,y$. Thenwhich is the normalized Hamming distance. It is nonnegative and symmetric, and equals zero exactly when all coordinates match. For each coordinate, a mismatch between $x_j$ and $z_j$ forces a mismatch between $x_j,y_j$ or between $y_j,z_j$. ThereforeSumming and dividing by $p$ proves the triangle inequality, establishing all four metric properties. Simple matching dissimilarity is a metric on binary profiles. If two separately labelled individuals have identical profiles, it gives zero distance between them, so on those labels it is only a pseudometric. The four profiles here are distinct, so this distinction does not prevent $D_S$ from defining a metric on the given sample.

There is a defect in the stated geometric interpretation of the data. The supplied numbers cannot be Euclidean distances, becauseThey violate the triangle inequality; independently, $d(C,D)=10.3>5.9+1.2$. Nevertheless, both clustering algorithms are defined for this symmetric dissimilarity matrix. The calculations below retain the supplied numbers and use agglomerative clustering of nonmetric dissimilarities, rather than silently inventing Euclidean replacement data.

In single-linkage clustering, the intercluster dissimilarity isThe closest pair is $A,D$, merging at $1.2$. Among the remaining clusters the next closest pair is $B,E$, merging at $2.6$. The three intercluster dissimilarities are nowConsequently $AD$ merges with $BE$ at $4.2$, using the cross-pair $A,B$. The remaining point $C$ joins at $\min (5.9,7.6,10.3,5.4)=5.4$, using $C,E$. The dendrogram thus hasThe close pairs $AD$ and $BE$ are the clearest early groupings. A cut between $2.6$ and $4.2$ produces these two pairs and the singleton $C$; a cut between $4.2$ and $5.4$ produces $ADBE$ and $C$. Single-linkage clustering builds chains through close cross-pairs, so the merge at $4.2$ does not mean every pair in $ADBE$ is that close: $d(D,E)=7.8$. The data alone do not prescribe a unique number of clusters.

For complete-linkage clustering, replace the minimum by the maximum:The first two merges remain $AD$ at $1.2$ and $BE$ at $2.6$. SubsequentlyThus $C$ joins $BE$ at $7.6$. The final maximum between $AD$ and $BCE$ is $d(D,C)=10.3$, givingBoth the topology and the later heights of the dendrogram change: complete-linkage clustering attaches $C$ to $BE$ before joining that group to $AD$, rather than merging the two pairs first. Its control of the largest within-cluster separation makes it less susceptible to the chaining seen with single-linkage clustering.