The Basic Idea  Say you are given a data set where each observed
example has a set of features, but has no labels. Labels are an
essential ingredient to a supervised algorithm like Support
Vector Machines, which learns a hypothesis function to predict
labels given features. So we can't run supervised learning. What
can we do?  One of the most straightforward tasks we can perform
on a data set without labels is to find groups of data in our
dataset which are similar to one another -- what we call
clusters.  K-Means is one of the most popular "clustering"
algorithms. K-means stores $k$ centroids that it uses to define
clusters. A point is considered to be in a particular cluster if
it is closer to that cluster's centroid than any other centroid.
K-Means finds the best centroids by alternating between (1)
assigning data points to clusters based on the current centroids
(2) chosing centroids (points which are the center of a cluster)
based on the current assignment of data points to clusters.
Figure 1: K-means