K-Means Clustering Forgy Initialization vs. Random Initialization

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.

This entry was posted in Machine Learning. Bookmark the permalink.