Calculating similarity and clustering question

I have a dataset of about a million companies containing their names, total employees and annual sales. I want to come up with a function that when given the company returns the 5 most similar companies in terms of their distance in total employees and annual sales.

I thought of doing k-means clustering on the dataset and find clusters. Then return all the companies in that cluster. The problem with this approach is that I don't know the number of clusters I should form beforehand.

Also, on a separate note, if I were to obtain a list of specialties (e.g. marketing, software, etc.) for each of the companies - how can I transform this qualitative value in to a number which can later help me calculate similarity.

• Maybe I am missing something, but if all you want is the 5 most similar companies, couldn't you do a hierarchical clustering and then find the first group that had 5 companies? Or is that too computer intensive? Oct 31, 2012 at 11:12
• @PeterFlom Hierarchical clustering is incredibly expensive and slow. Oct 31, 2012 at 11:37
• OK, thanks. I've never done clustering on really large data sets. Oct 31, 2012 at 11:50

1) Regarding total employees and annual sales features, as both are quantitative you may just use euclidean distance for them. Only don't forget to z-standardize both variables first, as soon as they are of different measure units. Upon the standardizing you indeed may try K-means clustering. This method of cluster analysis is implicitly based on euclidean distances between the objects (the companies); you don't have to compute the pairwise distances, especially as you have million of companies!

2) You think you can't decide on the number of clusters beforehand, but you could always do it afterwards. Do properly K-means a number of times, specifying different number of clusters each time, say, from 20 to 2, and save the results (cluster membership variable) each time. Then compare the quality of these 19 solutions by some internal clustering criteria (I'd recommend Calinski–Harabasz or Davies–Bouldin, both based on ANOVA ideology). I'm not R user and cannot recommend a tested package, but use something like NBClust. There are also other ways to determine the "right" number of clusters with K-means, for example "cross-validation" by subsamples. Carefully read something on this topic before you apply.

3) Regarding nominal variables such as marketing, software.

• One way is to recode the variables into series of dummy (1 vs 0) variables and perform still K-means clustering on those as if it were quantitative variables. This approach is not valid geometrically and logically, but heuristically it can be used, and indeed is being used by many. The proper way with dummies would be to compute Dice similarity measure (other similarity measures for binary features are permissible, too) and do clustering by some appropriate method (not K-means); however the problem in your case is that you have too many objects. It is impossible to create at once such a huge similarity matrix.
• In SPSS, there is two-step clustering procedure which can cluster huge number of objects and also allows nominal variables as well as quantitative. I believe that method to be a good choice for you. The method is just slightly modified BIRCH clustering method. I don't know if "two-step clustering" is implemented in R, but BIRCH should be implemented, I believe. I don't know if BIRCH can take nominal variables.
• (+1) About R packages and other way to assess cluster stability, I provided some information on this thread: How to tell if data is “clustered” enough for clustering algorithms to produce meaningful results?. And there are some BIRCH implementation available. I haven't check if this still works, though.
– chl
Oct 31, 2012 at 10:36
• If the goal is to just find the 5 most similar companies, why is a clustering procedure required? Why not calculate euclidean distances between the target company and all other companies (as @ttnphns describes) and then rank the distances, and return the top 5? Nov 1, 2012 at 11:15

For similarity search, why do you want to do clustering at all?

Why don't you just use an multi-dimensional index structure such as the R*-tree, kd-tree etc.

When you want to add the categorical attribute, k-means becomes a really bad choice, because it only works well with Euclidean distance. But you might want to use a much more complicated similarity measure!