K-means, Gaussian mixtures, and soft assignments — Examples

For the data $x_1=0,x_2=1,x_3=2,x_4=3$ in $\mathbb{R}$ and $K=2$, use nearest-center initialization with smallest-index initialization ties, retain the current label on later ties, replace each nonempty center by its assigned-data mean, and leave empty centers unchanged. For clusters $C_1,C_2$ and centers $c_1,c_2$, define the cost by $J={\sum }_{k=1}^2{\sum }_{x_i\in C_k}(x_i-c_k{)}^2$. Initial centers $(0,11\mathrm{/}10)$ yield the fixed clusters $\{0\}$ and $\{1,2,3\}$ with centers $(0,2)$ and cost $2$. Initial centers $(3,19\mathrm{/}10)$ yield the fixed clusters $\{3\}$ and $\{0,1,2\}$ with centers $(3,1)$ and cost $2$. Initial centers $(1\mathrm{/}2,5\mathrm{/}2)$ yield the fixed clusters $\{0,1\}$ and $\{2,3\}$ with centers $(1\mathrm{/}2,5\mathrm{/}2)$ and cost $1$. In the first two runs, the boundary observation is tied between the two updated centers and stays in its current cluster by the retention rule; each output is a fixed point, while the third has lower cost.

Lloyd's k-means algorithm with explicit tie handling — initialization, tie retention, empty-center handling, and the stop condition requiring unchanged labels and centers.

K-means objective — the squared Euclidean within-cluster objective used for the reported values.

The horizontal coordinate is the observation value. Each row is one run; blue dots are assigned to cluster 1 and red dots to cluster 2. Dashed vertical ticks mark the updated centers, with labels above them. Vertical row placement has no numerical meaning. The diagram records the verified terminal assignments; the proof above establishes them without using the picture.

diagram failed to render:
\begin{tikzpicture}[x=1.15cm,y=0.95cm,every node/.style={font=\small}]
  \draw[->] (-0.35,0) -- (3.55,0) node[right] {$x$};
  \foreach \x in {0,1,2,3} {\draw (\x,0.06)--(\x,-0.06) node[below=3pt] {\x};}

\node[left] at (-0.4,3) {run 1}; \draw[blue,dashed] (0,2.68)--(0,3.32) node[above] {$c_1=0$}; \draw[red,dashed] (2,2.68)--(2,3.32) node[above] {$c_2=2$}; \foreach \x in {0} {\fill[blue] (\x,3) circle (2.5pt);} \foreach \x in {1,2,3} {\fill[red] (\x,3) circle (2.5pt);}

\node[left] at (-0.4,2) {run 2}; \draw[blue,dashed] (3,1.68)--(3,2.32) node[above] {$c_1=3$}; \draw[red,dashed] (1,1.68)--(1,2.32) node[above] {$c_2=1$}; \foreach \x in {3} {\fill[blue] (\x,2) circle (2.5pt);} \foreach \x in {0,1,2} {\fill[red] (\x,2) circle (2.5pt);}

  \node[left] at (-0.4,1) {run 3};
  \draw[blue,dashed] (0.5,0.68)--(0.5,1.32) node[above] {$c_1=1/2$};
  \draw[red,dashed] (2.5,0.68)--(2.5,1.32) node[above] {$c_2=5/2$};
  \foreach \x in {0,1} {\fill[blue] (\x,1) circle (2.5pt);}
  \foreach \x in {2,3} {\fill[red] (\x,1) circle (2.5pt);}
\end{tikzpicture}

Assume AC. Take one observation $x=0\in \mathbb{R}$, two Gaussian components with means ${\mu }_1=-1$ and ${\mu }_2=1$, common variance ${\sigma }^2>0$, and mixture weights ${\pi }_1=1\mathrm{/}3$ and ${\pi }_2=2\mathrm{/}3$. Their component density is ${\varphi }_1(x;\mu ,{\sigma }^2)=(2\pi {\sigma }^2{)}^{-1\mathrm{/}2}\exp (-(x-\mu {)}^2\mathrm{/}(2{\sigma }^2))$, and the responsibility of component $k$ is ${\gamma }_k={\pi }_k{\varphi }_1(0;{\mu }_k,{\sigma }^2)\mathrm{/}{\sum }_{j=1}^2{\pi }_j{\varphi }_1(0;{\mu }_j,{\sigma }^2)$. The two squared distances from the observation to the component means are both $1$. For every $\sigma >0$, the responsibility vector is exactly $(1\mathrm{/}3,2\mathrm{/}3)$; therefore as $\sigma \downarrow 0$ it remains fractional rather than converging to $(1,0)$ or $(0,1)$.

Finite Gaussian mixture with positive-definite component covariances — the positive-weight Gaussian component formula and responsibility definition.

Equal-spherical mixture assignments and objective converge to k-means — tied nearest centers receive limiting responsibilities proportional to their fixed mixture weights.

Positive-definite multivariate Gaussian density is normalized — each component formula is a normalized Gaussian density.

Assume AC. For the observations $x_1=0,x_2=1\in \mathbb{R}$, use two Gaussian components of weights $1\mathrm{/}2,1\mathrm{/}2$, both with mean $0$, with variances ${\epsilon }^2$ and $1$ for $\epsilon >0$. Write ${\varphi }_1(x;0,s^2)=(2\pi s^2{)}^{-1\mathrm{/}2}\exp (-x^2\mathrm{/}(2s^2))$, $f_{\epsilon }(x)=\frac{1}{2}{\varphi }_1(x;0,{\epsilon }^2)+\frac{1}{2}{\varphi }_1(x;0,1)$, and $L_{\epsilon }=f_{\epsilon }(0)f_{\epsilon }(1)$. Every parameter in this family has positive weights and positive-definite one-dimensional covariances. The likelihood $L_{\epsilon }$ is unbounded above as $\epsilon \downarrow 0$; hence its log likelihood is unbounded above as well.

Finite Gaussian mixture with positive-definite component covariances — the finite-mixture likelihood and Gaussian density formula.

Positive-definite multivariate Gaussian density is normalized — the component functions are normalized probability densities for every $\epsilon >0$.