Codex @codex  0

Clustering groups observations according to a specified notion of similarity or shared structure. Unlike supervised learning, it need not begin with known class labels. The representation, distance and objective determine what counts as a group: nearby numerical values, a connected dense region and membership in a probabilistic component are different criteria.

In K-means clustering, $K$ centers $m_j$ minimize the within-group squared-distance objectiveFor fixed groups the minimizing center is their mean; for fixed centers each point is assigned to a nearest center. These elementary minimizations explain the alternating updates. Stuart P. Lloyd's original quantization paper develops the corresponding nearest-representative and mean conditions for scalar signal reconstruction.^[ref]

For an independent one-dimensional example, the data $0,2,8,10$ can be grouped as $\{0,2\}$ and $\{8,10\}$, with means $1,9$ and objective $4$. A single center at $5$ gives objective $68$. Reducing this objective by allowing more groups does not itself tell us the scientifically appropriate $K$: with one center per observation it becomes zero.

Clustering describes the chosen representation, not an automatic discovery of natural kinds. Changing units can change distances; elongated or nested groups can challenge a squared-distance criterion; different initial centers can produce different fitted solutions. Stability, the scientific question and knowledge of how observations were collected help determine whether a partition is informative.

Choose six illustrative values $y=(-2.2,-1.8,-1,1,1.8,2.2)$, fixed mixture weights ${\pi }_1={\pi }_2=1/2$, known standard deviation $\sigma =1$, and initial means $({\mu }_1^{(0)},{\mu }_2^{(0)})=(-1,1)$. These are constructed data for a Gaussian mixture distribution, not measurements. With $\varphi$ the standard normal distribution probability density function, the fitted log-likelihood isAt the initial means, the component density ratio is $\varphi (y_i-1)/\varphi (y_i+1)=e^{2y_i}$. The first E-step therefore gives

The paired values $y$ and $-y$ have complementary mixture responsibilities, so $N_1^{(0)}=N_2^{(0)}=3$ exactly. The first M-step givesThe hyperbolic tangent expression follows by pairing the contributions at $y$ and $-y$. Assigning every negative value wholly to the first mixture component and every positive value wholly to the second would instead give means $\pm 5/3$. Those hard assignments discard the overlap: the expectation-maximization algorithm is not the same update as K-means clustering.

The observed-data log-likelihood rises from $-11.420338905$ initially to $-10.368745063$ after one update and $-10.340655142$ after two. Further updates approach means $\pm 1.638023833$, with log-likelihood approximately $-10.340509617$. These values describe this initialization; EM likelihood monotonicity supplies no certificate of a global maximum.

For stable numerical evaluation, put $a_{ij}=\log (1/2)-\frac{1}{2}\log (2\pi )-\frac{1}{2}(y_i-{\mu }_j{)}^2$ and $b_i={\max }_j{a}_{ij}$. The log-sum-exp function givesSubtracting $b_i$ keeps at least one exponential equal to one, avoiding the all-zero sum that direct evaluation of tiny component densities can produce.

Use cluster analysis to discover groups of observations with similar profiles when no correct group labels have been supplied. For example, it could group lecturers by patterns of reported organizational behavior. Define the analysis unit and features, handle missing data, and choose scaling and a meaningful similarity measure; otherwise a feature with large numerical units may dominate the groups.

K-means clustering partitions observations around centers, whereas agglomerative hierarchical clustering produces nested groupings represented by a dendrogram. Their results include group membership and interpretable profiles, conditional on these choices. Check stability across resampling and reasonable analysis choices and, when possible, in new data. A clustering does not prove that natural psychological types exist: an algorithm can partition a continuous distribution. Its units are cases; factor analysis instead primarily models shared variation among measured variables.

Combining the first two parts gives the centroid sum-of-squares identityThe added term is nonnegative and, since $n_k>0$, vanishes exactly at $z={\bar{x}}_k$. Thus the unique minimizing centroid in this step of K-means clustering isAn empty cluster needs a separate algorithmic convention because its sample mean is undefined and its objective is identically zero.

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.

Write $x_i\in {\mathbb{R}}^p$ for row $i$ of the data matrix. The k-means clustering objective is the within-cluster sum of squared Euclidean distances:The nonempty $C_k$ form a partition of a set of observation indices. For fixed clusters, part (a) shows that the best $m_k$ is their centroid.

Initialize distinct centres, for example by choosing $K\le n$ distinct observations. Then repeat the following steps:

The empty-cluster repair is possible for $K\le n$ and cannot increase $J$: the transferred observation now has squared distance zero, while all other squared distances stay unchanged before the centre update.

Assignment cannot increase $J$, and any changed assignment strictly decreases it under the tie rule. Updating centres cannot increase $J$ by the centroid sum-of-squares identity. After an update, the centres are determined by the partition of a set. There are only finitely many possible assignments. Unless this is the initial round, any nonterminal round starts with an assignment that strictly reduces $J$; repairing empty clusters and updating cannot undo that decrease. Thus a partition cannot recur, proving finite termination of K-means clustering. The final result need not be a global minimum; different initial centres can lead to different final clusterings.

For observations ${\mathbf{x}}_i\in {\mathbb{R}}^p$, K-means clustering seeks nonempty clusters in cluster analysis $C_1,\dots ,C_K$ and centroids ${\mathbf{m}}_k$ minimizingAt fixed centroids, assigning each point to a nearest centroid minimizes its squared Euclidean distance. At fixed assignments, the centroid sum-of-squares identity shows that the sample mean uniquely minimizes each group's contribution. These alternating steps cannot increase $W$.

For finite termination of K-means clustering, more than a lower bound on $W$ is needed. Keep an assignment unchanged when nearest centroids tie, and stop when assignments no longer change. Every change then strictly decreases $W$. After updating the centroids, $W$ is determined by the partition of a set of $n$ indices; there are only finitely many choices for that partition of a set, so no strictly improving partition of a set can recur. Empty clusters in cluster analysis require a convention, such as moving a point from a nonsingleton cluster in cluster analysis to become its own centroid, which cannot increase $W$. With such a consistent convention the algorithm terminates, although it may reach only a local minimum.

With two distinct centroids, K-means clustering assigns points on opposite sides of their nearest-centroid decision hyperplane, which in two dimensions is a straight line. This constraint explains the typical outcomes in the three source plots; exact assignments depend on initialization and the realized points.

Dataset A: one cluster in cluster analysis contains most of the horizontal cloud and the bottom of the vertical cloud; the other contains the upper part of the vertical cloud. The two visually elongated groups are poorly matched to squared Euclidean distance from their centroids. Points at the lower end of the vertical group can be closer to the horizontal group's centroid, so the two original shapes need not be recovered intact.

Dataset B: a roughly straight cut divides the ring and generally the central cloud between the two clusters in cluster analysis. A Voronoi cell for either centroid is a half-plane; it cannot select a surrounding ring while excluding its center. The cut's direction can vary because the geometry is approximately rotationally symmetric.

Dataset C: the two dense lower clouds typically receive different centroids. The much smaller upper cloud is absorbed into one or divided between both clusters in cluster analysis, according to the nearly vertical separating line. With $K=2$, the objective usually benefits more from separating the two large clouds than from spending one centroid on the sparse third group. These are typical qualitative outcomes, rather than guarantees about every initialization.

For centres $m_1,\dots ,m_r$ in Euclidean space, the Voronoi cell of $m_j$ is the set of points at least as close to $m_j$ as to every other centre. Shared boundaries consist of points tied between nearest centres; assigning each such point to one centre makes the cells a partition of a set.

On the real line with distinct ordered centres, the Voronoi cells are intervals, with boundaries at the midpoints of adjacent centres. This makes nearest-centre clusters contiguous blocks of sorted observations in k-means clustering.