Nearest-Centroid Assignment And Euclidean Distance

Assigning an Observation to a Centroid

In k-means clustering, a centroid represents the center of a cluster. Once a set of centroids is specified, assigning an observation means identifying which centroid is nearest to it. This is a geometric comparison: the observation is assigned to the centroid with the smallest Euclidean distance. The centroids are treated as fixed during this assignment step; updating them is a separate operation.

Suppose each observation has \(p\) numerical coordinates. Write observation \(i\) as \(\mathbf{x}_i=(x_{i1},\ldots,x_{ip})\), and centroid \(j\) as \(\mathbf{c}_j=(c_{j1},\ldots,c_{jp})\). The coordinates being compared must use the same feature representation. No probability distribution is required for this distance calculation.

Definition: The squared Euclidean distance from observation \(\mathbf{x}_i\) to centroid \(\mathbf{c}_j\) is the sum of the squared coordinate differences:

d_{ij}^{\,2}=\sum_{r=1}^{p}(x_{ir}-c_{jr})^2.

The Euclidean distance is \(d_{ij}=\sqrt{d_{ij}^{\,2}}\). Assign the observation to a centroid that minimizes \(d_{ij}\), or equivalently minimizes \(d_{ij}^{\,2}\). If two or more centroids attain the same minimum, the observation is tied; a specified tie-breaking rule can select one of them.

For example, with two coordinates, the squared distance from \((x_1,x_2)\) to \((c_1,c_2)\) is \((x_1-c_1)^2+(x_2-c_2)^2\). Each coordinate contributes a squared difference. The same process extends to any number of coordinates: include one squared difference for every feature, then add them.

Why Comparing Squared Distances Is Enough

The square root in Euclidean distance is unnecessary when the task is only to determine which centroid is nearest. Squaring is strictly increasing for nonnegative numbers: if \(a\) and \(b\) are nonnegative, then \(a<b\) exactly when \(a^2<b^2\). Since every Euclidean distance is nonnegative, the centroid with the smallest distance also has the smallest squared distance.

Justification: For any two candidate centroids \(j\) and \(k\), \(d_{ij}\) and \(d_{ik}\) are nonnegative. Therefore,

d_{ij}<d_{ik} \quad\Longleftrightarrow\quad d_{ij}^{\,2}<d_{ik}^{\,2}.

Thus square roots cannot change which centroid is nearest, and they can be omitted. Equality is preserved as well, so \(d_{ij}^{\,2}=d_{ik}^{\,2}\) identifies an exact tie.

This shortcut is especially useful when there are many candidate centroids or several coordinates. It avoids repeated square-root calculations while preserving the assignment. It does not mean that the coordinate differences themselves can be added without squaring.

Worked Example: Assigning Several Points in Two Dimensions

A hypothetical portfolio analysis uses three fixed centroids \(A=(1,1)\), \(B=(5,3)\), and \(C=(-1,4)\). Assign observations \(P=(2,2)\), \(Q=(4,2)\), \(R=(0,3)\), and \(T=(3,2)\) to their nearest centroid. Use squared Euclidean distances, and report any ties.

Method. For each observation, calculate the squared distance to all three centroids and select the smallest value.

For \(P=(2,2)\):

d_{PA}^{\,2}=(2-1)^2+(2-1)^2=1+1=2,

d_{PB}^{\,2}=(2-5)^2+(2-3)^2=9+1=10, \qquad d_{PC}^{\,2}=(2+1)^2+(2-4)^2=9+4=13.

The minimum is \(2\), so \(P\) is assigned to \(A\).

For \(Q=(4,2)\):

d_{QA}^{\,2}=(4-1)^2+(2-1)^2=9+1=10,

d_{QB}^{\,2}=(4-5)^2+(2-3)^2=1+1=2, \qquad d_{QC}^{\,2}=(4+1)^2+(2-4)^2=25+4=29.

The minimum is \(2\), so \(Q\) is assigned to \(B\).

For \(R=(0,3)\):

d_{RA}^{\,2}=(0-1)^2+(3-1)^2=1+4=5,

d_{RB}^{\,2}=(0-5)^2+(3-3)^2=25+0=25, \qquad d_{RC}^{\,2}=(0+1)^2+(3-4)^2=1+1=2.

The minimum is \(2\), so \(R\) is assigned to \(C\).

For \(T=(3,2)\):

d_{TA}^{\,2}=(3-1)^2+(2-1)^2=4+1=5,

d_{TB}^{\,2}=(3-5)^2+(2-3)^2=4+1=5, \qquad d_{TC}^{\,2}=(3+1)^2+(2-4)^2=16+4=20.

The minimum value, \(5\), is shared by \(A\) and \(B\). Thus \(T\) is exactly equidistant from \(A\) and \(B\); the distance calculation alone does not prefer either one. The assignments are \(P\to A\), \(Q\to B\), \(R\to C\), and \(T\to A\) or \(B\), depending on the tie rule. As a check, each reported assignment corresponds to the smallest calculated squared distance.

Common mistake avoided: Do not force a unique assignment for \(T\) just because the task uses the word “nearest.” Both centroids are nearest. A tie rule resolves how to record the assignment; it does not make one distance smaller.

Calculations in More Than Two Dimensions

The formula works the same way when observations have three or more features. A common error is to omit a coordinate, particularly when one of the differences is zero. Including the zero term is harmless, but omitting a nonzero coordinate can change which centroid is nearest. Keep the coordinate order consistent between each observation and each centroid.

Worked Example: Comparing Three-Coordinate Centroids

A hypothetical risk grouping uses observations with three recorded features. For observation \(X=(1,2,1)\), compare centroids \(U=(0,0,0)\), \(V=(2,2,1)\), and \(W=(-1,3,2)\). Assign \(X\) using squared Euclidean distance and show every coordinate contribution.

Method. Subtract each centroid coordinate from the matching observation coordinate, square each difference, and add the three results.

For centroid \(U\), the coordinate differences are \(1-0=1\), \(2-0=2\), and \(1-0=1\). Therefore,

d_{XU}^{\,2}=1^2+2^2+1^2=1+4+1=6.

For centroid \(V\), the differences are \(1-2=-1\), \(2-2=0\), and \(1-1=0\). Therefore,

d_{XV}^{\,2}=(-1)^2+0^2+0^2=1+0+0=1.

For centroid \(W\), the differences are \(1-(-1)=2\), \(2-3=-1\), and \(1-2=-1\). Therefore,

d_{XW}^{\,2}=2^2+(-1)^2+(-1)^2=4+1+1=6.

The smallest squared distance is \(1\), so \(X\) is assigned to \(V\). The calculation is checked by comparing all three totals: \(1<6\) and \(1<6\). The equal distances to \(U\) and \(W\) do not affect the assignment because neither is tied for the minimum.

Common mistake avoided: A tie between two candidate distances matters only if those distances are minimal. Here \(U\) and \(W\) tie with each other, but \(V\) is strictly closer.

Exact Ties and a Stated Tie Rule

An observation may be equally distant from two centroids. If a problem specifies a tie-breaking convention, apply it only after calculating and comparing the distances. For instance, a convention might assign a tied observation to the centroid with the smaller index. This convention makes the recorded assignment reproducible; it is not a claim that the selected centroid is geometrically closer.

A tie can occur even when an observation does not lie halfway between the centroids along the line joining them. In two dimensions, many points can have equal distances to the same pair of centers. The important test for an individual observation is direct: calculate both squared distances and check whether the values are equal.

Worked Example: An Equidistant Point and a Tie-Breaking Convention

Three hypothetical centroids are \(D=(2,0)\), \(E=(6,0)\), and \(F=(4,8)\). A point \(Z=(4,3)\) is assigned to the nearest centroid; if there is a tie for the minimum, assign to the centroid with the smaller index, where \(D\), \(E\), and \(F\) have indices 1, 2, and 3. Then repeat the assignment for \(Z'=(4.2,3)\).

For \(Z=(4,3)\): The squared distances are

d_{ZD}^{\,2}=(4-2)^2+(3-0)^2=4+9=13,

d_{ZE}^{\,2}=(4-6)^2+(3-0)^2=4+9=13,

d_{ZF}^{\,2}=(4-4)^2+(3-8)^2=0+25=25.

The minimum is \(13\), attained by \(D\) and \(E\). The point is equidistant from these two nearest centroids. The stated rule selects the smaller index, so \(Z\) is assigned to \(D\). Without that rule, the distance-based result is a tie between \(D\) and \(E\).

For \(Z'=(4.2,3)\): Calculate each squared distance without rounding intermediate values:

d_{Z'D}^{\,2}=(4.2-2)^2+(3-0)^2=2.2^2+3^2=4.84+9=13.84,

d_{Z'E}^{\,2}=(4.2-6)^2+(3-0)^2=(-1.8)^2+3^2=3.24+9=12.24,

d_{Z'F}^{\,2}=(4.2-4)^2+(3-8)^2=0.2^2+(-5)^2=0.04+25=25.04.

The minimum is \(12.24\), so \(Z'\) is assigned to \(E\). The small change in the first coordinate breaks the tie: its squared distance to \(E\) is now \(13.84-12.24=1.60\) less than its squared distance to \(D\). The calculations also confirm that \(F\) is not competitive for either point.

Common mistake avoided: Do not apply the tie rule to \(Z'\). Its distances are not tied; the minimum is strictly \(12.24\).

Common Metric Mistakes

Euclidean distance is not the same as Manhattan distance. Euclidean distance squares coordinate differences and takes a square root; Manhattan distance adds their absolute values. Substituting one metric for the other can change the nearest centroid. The following check illustrates why the specified metric matters.

Exam trap: From the origin, compare centroids \(G=(3,3)\) and \(H=(5,0)\). Using Manhattan distance gives \(6\) to \(G\) and \(5\) to \(H\), so it incorrectly selects \(H\) if the required metric is Euclidean. The correct squared Euclidean distances are

d_G^{\,2}=3^2+3^2=18, \qquad d_H^{\,2}=5^2+0^2=25.

Since \(18<25\), the Euclidean assignment is to \(G\). The error was changing the distance definition, not omitting a square root.

Another trap is comparing only one coordinate, such as the horizontal difference between a point and each center. Euclidean distance uses every coordinate in the stated feature space. Conversely, do not calculate ordinary distances and then compare rounded values when the squared-distance totals already establish the minimum. If exact totals tie, report the tie or use the rule given in the question.

Distance-based assignments depend on the coordinate representation and the metric specified. If features are recorded on very different scales, those scales can affect Euclidean distances; the assignment calculation itself does not adjust them automatically. Use the feature values as the problem directs, and do not introduce an unrequested transformation.

Key takeaway: For each observation-centroid pair, square every coordinate difference and add the results. Assign to a centroid with the smallest total; report an exact tie honestly, and apply a tie-breaking convention only when one is specified.

Check Your Understanding

For each problem, use squared Euclidean distance and show the coordinate contributions before selecting a centroid.

An observation \(A=(2,1)\) is compared with \(C_1=(0,0)\) and \(C_2=(4,2)\). Calculate both squared distances and state the assignment or tie. (Answer: \(d_{A,C_1}^{\,2}=5\), \(d_{A,C_2}^{\,2}=5\); tie.)
For \(B=(1,0,2)\), compare \(D_1=(0,0,0)\) and \(D_2=(2,1,2)\). Which centroid is nearest? (Answer: \(d_{B,D_1}^{\,2}=1+0+4=5\), \(d_{B,D_2}^{\,2}=1+1+0=2\); assign to \(D_2\).)
For \(C=(3,1)\), compare \(E_1=(1,2)\) and \(E_2=(5,0)\). Calculate both squared distances and report any tie. (Answer: \(d_{C,E_1}^{\,2}=4+1=5\), \(d_{C,E_2}^{\,2}=4+1=5\); tie.)
From the origin, compare \(F_1=(3,3)\) and \(F_2=(5,0)\). A candidate uses Manhattan distance and selects the nearest under that metric. What is the correct Euclidean assignment? (Answer: squared distances are \(18\) to \(F_1\) and \(25\) to \(F_2\); assign to \(F_1\).)
Centroids \(G_1=(2,0)\), \(G_2=(6,0)\), and \(G_3=(4,8)\) are compared with \(X=(4,3)\). If a tie for the minimum is assigned to the smallest index, where does \(X\) go? (Answer: squared distances are \(13,13,25\); tie for the minimum between \(G_1\) and \(G_2\), so assign to \(G_1\).)

What You'll Learn