K-means groups data points into a chosen number of clusters. It assigns each point to its nearest cluster center, called a centroid, then moves each centroid to the mean of its assigned points. Repeating those steps reveals groupings that may not be obvious from looking at the data. section 6.2
A basic run follows this cycle:
- Normalize dimensions so differences in scale do not cause larger-valued dimensions to dominate. section 6.2
- Choose k, the number of clusters, and initialize their centroids randomly within the data’s range. section 6.2
- Assign each point to its nearest centroid, then recompute each centroid from the mean of its assigned points. section 6.2
- Repeat until centroids stop moving or a set iteration limit is reached. section 6.2
A Swift implementation can represent points through a shared interface that exposes their dimensions and distance. Normalization matters because otherwise a dimension with larger differences can dominate the clustering. section 6.1 section 6.2
Governors by age and longitude
With k set to 2, the algorithm groups state governors using longitude and age. One run finds a cluster of western states whose governors are relatively older. Random starting centroids can produce different results, and the pattern suggests correlation—not a conclusive explanation. section 6.3
Choosing k and useful starting centroids can take trial and error. Outliers may produce odd clusters, and the basic method can become impractical with many points and dimensions. Alternatives and extensions include k-means++, sampling, k-medians, and k-medoids. section 6.4
public func run(maxIterations: UInt = 100) -> [Cluster] {
for iteration in 0..<maxIterations {
clusters.forEach{ $0.points.removeAll() } // clear all clusters
assignClusters() // find clusters each is closest to - assign
let lastCentroids = centroids // record centroids
generateCentroids() // find new centroids
if lastCentroids == centroids { // have centroids moved?
print("Converged after \(iteration) iterations.")
return clusters // they haven't moved, so we've converged
}
}
return clusters
}
}
The Swift run loop clears assignments, recalculates centroids, and returns when they stop changing. section 6.2
