Somewhat surprisingly, the most important part of the k-means clustering algorithm is how the algorithm is initialized. The three most common k-means initialization algorithms are 1.) Forgy initialization, 2.) random initialization, and 3.) k-means++ initialization.
Even though there’s been decades of research on clustering algorithms, there’s no clear consensus opinion on which of the three initialization algorithms works best. First of all, it’s not clear what “best” means — it could mean fastest, easiest to implement, best results quickly, best results eventually, and so on. And the formal research results I’ve read have been ambiguous.
In my opinion, there is probably no single best initialization algorithm for k-means, and different initialization algorithms work differently on different datasets. Additionally, the difference in initialization algorithms rarely makes any practical difference.
I was coding around recently and compared Forgy initialization and random initialization. I used a super simple dummy dataset with just 20 items, each with just 2 elements. Forgy initialization is harder to implement and is stochastic in the sense that it could fail (even though the possibility of failure is extremely small). Random initialization is easier to implement and, if done in a particular way, cannot fail to successfully initialize.
In k-means initialization, you must initialize the cluster mapping and the cluster means. Suppose you have just 6 data items, each with just two elements, and you’ve set k = number of clusters = 3.
[0] 0.20 0.120 [1] 0.30 0.200 [2] 0.60 0.160 [3] 0.40 0.180 [4] 0.50 0.140 [5] 0.70 0.170
Random initialization begins by assigning each data item to cluster. My technique of choice is to begin by cycling through all values of k to get a mapping: (0, 1, 2, 0, 1, 2). This ensures that there are no empty clusters. Then I randomly shuffle the mapping, giving for example: (2, 0, 1, 1, 2, 0). So items [1] and [5] belong to cluster 0, items [2] and [3] belong to cluster 1, and items [0] and [4] belong to cluster 2.
Next, you compute the means of each cluster. The mean of cluster 0 is (0.30, 0.200) + (0.70, 0.170) / 2 = (0.50, 0.185). Similarly, the mean of cluster 1 is (0.60, 0.160) + (0.40, 0.180) / 2 = (0.50, 0.170). The mean of cluster 2 is (0.20, 0.120) + (0.50, 0.140) / 2 = (0.35, 0.130).
At this point the mapping and means have been initialized, and the mapping has no empty clusters. Now you can do the main clustering loop.
Forgy initialization begins by selecting k random data items and using their values for the initial means. Suppose you select (5, 0, 2). So the mean of cluster 0 = item [5] = (0.70, 0.170), the mean of cluster 1 = item [0] = (0.20, 0.120), and the mean of cluster 2 = item [2] = 0.60, 0.160):
cluster mean ---------------------- 0 (0.70, 0.170) 1 (0.20, 0.120) 2 (0.60, 0.160)
Next you use the initial means to assign each data item to a cluster. Item [0] is closest to mean 1 so it’s assigned to cluster 1. Item [1] is closest to mean 0 so it’s assigned to cluster 0. Item [2] is closest to mean 2 so it’s assigned to cluster 2, Item [3] is closest to mean 2 so it’s assigned to cluster 2. And so on.
Unfortunately, at this point in Forgy initialization the mapping might have an empty cluster, for example, something like (0, 2, 2, 2, 0, 2) which has no data items assigned to cluster 1. The main clustering loop would blow up. So for Forgy initialization you have to initialize with a loop:
loop maxCount times pick k distinct items initialize means to selected items use means to compute mapping if mapping has no empty clusters break end-loop
My implementation of Forgy initialization for k-means clustering.
I coded up a k-means clustering routine with an option for either random or Forgy initialization. I ran clustering with both initializations on a tiny dataset that is designed with 3 clear clusters. There are a ton of details but I ran each initialization type, setting k = 1 to 10 and computed the resulting within-cluster sum of squares (WCSS). Smaller values of WCSS are better.
k Forgy WCSS random WCSS -------------------------- 1 0.1111 0.1111 2 0.0317 0.0317 3 0.0072 0.0072 4 0.0058 0.0053 5 0.0046 0.0677 6 0.0026 0.0038 7 0.0020 0.0541 8 0.0017 0.0406 9 0.0016 0.0330 10 0.0015 0.0433
Forgy initialization was better than or the same as random, except for k=4. Clustering using random initialization was especially poor for k = 5, 7, 8, 9, 10. However, this one example doesn’t prove anything general about Forgy vs. random. As I mentioned, research results are mixed.
Three images from an Internet search for “initialization”. Left: I speculate this image of a man’s face is related to some sort of illustration tool initialization. Center: The t-shirt reads “ADULTPERSON.EXE Initialization Failed”. Right: The famous Lena photo used in image classification. She appeared in the November 1972 Playboy Magazine. Writing a breakthrough research paper isn’t the only way to become famous in ML.



.NET Test Automation Recipes
Software Testing
SciPy Programming Succinctly
Keras Succinctly
R Programming
Visual Studio Live
Microsoft MLADS Conference
DevIntersection Conference
Machine Learning Week
Ai4 Conference
G2E Conference
iSC West Conference
You must be logged in to post a comment.