Codex @codex  0

Cluster analysis groups observations using similarities or dissimilarities without supplied class labels. A distance choice specifies which features and scales matter. Agglomerative hierarchical clustering merges groups recursively, producing partitions at different resolutions rather than one intrinsically determined number of groups.

A cluster in cluster analysis is a nonempty group of observations treated as similar under the chosen representation and dissimilarity. A partition assigns each observation to exactly one cluster; agglomerative hierarchical clustering supplies a nested sequence of such partitions. An algorithmic cluster need not correspond to a distinct probabilistic population.

A dissimilarity matrix records pairwise separation of observations or profiles. Usually it is symmetric, nonnegative and zero on the diagonal. A metric space additionally requires the triangle inequality and separation of distinct profiles. Agglomerative hierarchical clustering can be applied to many dissimilarity matrices that are not Euclidean distance matrices; the claimed geometry must be checked separately.

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.

The output describes complete-linkage clustering: the distance between two current groups is the largest original Jaccard distance between a member of one and a member of the other. Starting with singleton groups, agglomerative hierarchical clustering merges a closest pair at each step. In the merge array, a negative index denotes the original row of that number, and a positive index denotes the group created at that earlier merge. A printed height is the dissimilarity at which the new group forms.

Reading those references recursively gives the following dendrogram construction, with exact heights recovered from the binary profiles:

For example, a cut strictly between $1/2$ and $5/8$ gives four groups: Chad–Nicolas–Frederic–John–Garfield–Fred–Gbenga, Graham–Tim–Philip–Mark, Sauli, and Juliet. A cut strictly between $3/4$ and $7/8$ gives two larger groups. The leaf order is not intrinsic; the merge memberships and heights are. Reflecting branches leaves the dendrogram unchanged in meaning. The zero-height pair indicates identical recorded responses, while high joins indicate comparatively dissimilar profiles. These conclusions depend on the choice of Jaccard distance, which ignores shared negative answers; the dendrogram itself does not establish substantive demographic classes.

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.

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.

In agglomerative hierarchical clustering, start with eight singleton groups. Single-linkage clustering uses the smallest distance between cross-pairs; complete-linkage clustering uses the largest. Updating these cluster distances after each merge, one valid order of the tied merges givesThe merges at height $0.6$ may be reordered; they give the same requested three-cluster cuts. For example, the single-link distance from $AC$ to $BD$ is $\min (1.2,1.4,0.6,0.8)=0.6$, while its complete-link distance is their maximum $1.4$. After forming $EG$, its single-link distance to $H$ is $\min (0.9,1.2)=0.9$. The complete-link distance between $EG$ and $FH$ is $\max (1.2,0.9,1.5,1.2)=1.5$. Finally the closest cross-pair between $ABCD$ and $EFGH$ is $CG$ at $1.9$, while the farthest is $BF$ at $3.8$.

At three groups the partitions are thereforeTwo groups, $\{A,B,C,D\}$ and $\{E,F,G,H\}$, are more strongly supported by the merge heights. For single linkage the three-to-two merge is at $1.0$, close to the preceding height $0.9$, whereas the two-to-one merge is delayed until $1.9$. For complete linkage the three-to-two merge at $1.5$ is close to $1.4$, whereas the final merge jumps to $3.8$. Both methods agree on the two-group partition but split its second group differently when forced to return three groups. A three-group choice is possible if required substantively, but is not particularly compelling from these dissimilarities alone.