DP-means is a Bayesian nonparametric extension of K-means for clustering unlabeled data. It assigns each point to the nearest existing centroid, but creates a new cluster when the smallest squared Euclidean distance exceeds the threshold λ. Its K-means-like objective penalizes the number of clusters, allowing that number to grow with the data. section 8.1 section 8.5
The core procedure is:
- Initialize cluster centers and a distance threshold λ. section 8.1
- For each data point, compare its squared Euclidean distance with every current centroid. section 8.1
- Assign the point to the closest centroid unless the distance exceeds λ; in that case, start a new cluster. section 8.1
- Evaluate cluster assignments with normalized mutual information, variation of information, or adjusted Rand index when ground-truth labels are available. section 8.1
Customer segmentation and iris clustering
Customer purchase history, interests, and geographical location provide a motivating segmentation setting. A Python implementation initializes centroids with k-means++, applies DP-means to the iris dataset, and records the objective and iteration time for up to 100 iterations. section 8.1 section 8.1
Figure 8.1 DP-means algorithm pseudo-code
Use the DP-means pseudo-code to inspect the reassignment and new-cluster creation loop. section 8.1
