UUtah Fall 2026 | Data Mining | L9 - k-Means and friends

Overview

The lecture formalizes assignment-based clustering through representative sites, then compares k-means, k-median, k-medoids, and k-center objectives. It explains Gonzalez’s 2-approximation for metric k-center and Lloyd’s algorithm for squared-Euclidean k-means, including its convergence to local optima and the k-means++ initialization method that improves the odds of finding a strong solution.

Key takeaways

K-means minimizes average squared Euclidean distance, and for fixed cluster assignments the coordinate-wise mean is the site that minimizes the cluster’s sum of squared errors.
K-median reduces the influence of distant outliers by using unsquared distances, while k-medoids additionally requires each representative to be an observed data point.
Gonzalez’s farthest-first algorithm gives a 2-approximation for k-center in metric spaces and applies to distances such as Jaccard without requiring Euclidean coordinates.
Lloyd’s assignment and mean-update steps each do not increase k-means cost, but stabilization only establishes a local optimum, not the globally best clustering.
K-means++ chooses later initial centers with probability proportional to squared distance from the nearest selected center, improving coverage before Lloyd’s optimization begins.

Chapters

0:00 Course Updates: Homework, Project Data, and Campus Events

Similarity homework is due at the end of the day; late submissions within one or two days can receive partial credit.
The one-page-per-group data collection report is due in a week and asks groups to consider how they would simulate data resembling their project dataset.
The School of Computing career fair is Thursday from 10 a.m. to 2 p.m.; the Data Science Club’s data discovery hunt is Monday from 9 a.m. to 4 p.m.

6:09 Assignment-Based Clustering Represents Clusters with Sites

The input is a dataset X in a space such as R^d, a distance function, and a target cluster count K.
Instead of storing only cluster subsets, assignment-based methods represent clusters using sites s1 through sK.
Each point is assigned to a site, which implicitly defines the corresponding cluster.

10:00 Nearest-Site Assignments Create Voronoi Clusters

The assignment function maps each point x to the site minimizing its distance: arg min over sites s_j of d(x, s_j).
Nearest-site assignments partition the space into Voronoi regions; restricting those regions to X gives the data clusters.
The site set can be a subset of the data points, but methods such as k-means can also use sites outside the observed dataset.

16:00 K-Means Minimizes Average Squared Euclidean Distance

The k-means objective averages each data point’s squared distance to its assigned site.
The standard formulation uses squared Euclidean distance in R^d and optimizes the locations of K sites.
The objective makes clustering an explicit optimization problem, unlike procedures whose output is defined only by a sequence of merges or density rules.

21:50 K-Median and K-Medoids Change Robustness and Site Constraints

K-median minimizes the sum of distances rather than squared distances, so a very distant outlier has less influence than under k-means.
K-medoids adds the constraint that every representative site must be an observed data point, avoiding the need to construct an average object.
Medoids are useful for non-Euclidean data such as documents compared with Jaccard distance, and their observed examples can make cluster representatives easier to interpret.

33:50 K-Center Minimizes the Worst Assignment Distance

The k-center objective minimizes the maximum distance from any data point to its assigned site.
Because the objective is governed by the worst-served point, k-center tends to select sites that cover outliers and extreme points.
The formulation applies in general metric spaces rather than requiring Euclidean coordinates.

35:00 Gonzalez’s Algorithm Greedily Selects Farthest Sites

Gonzalez’s algorithm starts with an arbitrary data point and repeatedly adds the point farthest from its nearest already-selected site.
At each iteration, the next site addresses the point currently contributing the largest k-center cost.
The procedure selects K sites in K passes over the data and requires the distance function to satisfy the metric triangle inequality.

44:05 Lloyd’s Algorithm Alternates Assignment and Mean Updates

Lloyd’s algorithm initializes K sites, assigns every point to its nearest site, and replaces each site with the mean of its assigned points.
It repeats nearest-site assignment and centroid updates until the sites stop changing or a limit such as 20 iterations is reached.
The mean update depends on Euclidean coordinates and the squared-distance k-means objective.

49:10 Voronoi Boundaries and Centroid Updates Refine Assignments

An initial set of five sites can induce Voronoi regions that split natural groups across cluster boundaries.
After assignments are computed, each site moves to the average of the points in its region, often shifting toward a more coherent group center.
Recomputing the Voronoi diagram after centroid updates can change assignments; once assignments and sites remain stable, the iteration stops.

53:30 The Mean Minimizes a Cluster’s Sum of Squared Errors

For a fixed cluster X_j, its optimal Euclidean site minimizes the sum of squared distances to the points in X_j.
That minimizer is the coordinate-wise mean, which justifies Lloyd’s centroid update.
The mean does not generally minimize the sum of unsquared distances, so the same update is not the correct k-median optimization step.

58:00 Lloyd’s Updates Decrease Cost but May Take Many Iterations

Nearest-site assignment cannot increase the objective because each point moves to a site no farther away.
Replacing each site with its cluster mean cannot increase squared-error cost because the mean minimizes that cluster’s sum of squared distances.
The objective decreases until the algorithm stabilizes, but the finite number of assignments does not rule out exponentially many iterations in the worst case.

1:00:30 Lloyd’s Algorithm Can Converge to a Local Optimum

A poor initial placement can split two sites across one natural group while leaving another group poorly represented.
Lloyd’s assignment and mean-update steps can then stabilize even though a different arrangement of K sites has lower cost.
In high-dimensional data, a two-dimensional projection or cluster variance may suggest problems, but neither necessarily reveals whether the solution is globally optimal.

1:07:00 Random and Gonzalez Seeding Help but Do Not Eliminate Bad Starts

Choosing K observed points uniformly at random and rerunning Lloyd’s algorithm can help; the lowest-cost run can be retained.
Gonzalez’s farthest-first sites give a structured initialization that tends to spread centers across the dataset.
Neither random seeding nor Gonzalez seeding guarantees a good k-means solution in every case.

1:10:00 K-Means++ Uses Distance-Weighted Random Initialization

K-means++ chooses its first center from the data and selects each subsequent center randomly with probability proportional to its squared distance from the nearest selected center.
Squaring the distance makes points far from existing centers much more likely to be selected, encouraging coverage of distinct groups.
After initialization, Lloyd’s algorithm refines the centers; repeated runs and selection of the best-cost result can further improve reliability.

1:13:00 Why Squared-Distance Sampling Favors Uncovered Clusters

After one center is chosen, points in its vicinity have small squared-distance weights, while distant groups receive much larger weights.
Once a second center covers a distant group, the remaining uncovered group becomes more likely to supply the next center.
The method combines randomized selection with distance-based coverage rather than choosing all centers uniformly.

1:16:30 Weighted Sampling with Cumulative Sums and the Alias Method

For nonnegative weights w_i, normalize by their sum so each item has probability w_i divided by the total weight.
Cumulative weight intervals let a uniform random number in [0, 1] select an item in proportion to its weight; a binary tree can support selection in logarithmic time.
The alias method can support constant-time weighted draws, and k-means++ uses this kind of sampling to initialize Lloyd’s algorithm.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, UofU Data Science.