# Clustering not producing even clusters

I'm using k-means clustering to processes running on machines.

Dataset sample :

machine name, process
m1,java
m2,tomcat
m1,word
m3,excel


Build a matrix of associated counts :

   java,tomcat,word,excel
m1,1,0,1,0
m2,0,1,0,0
m3,0,0,0,1


I then run k-means against this dataset (have tried Euclidean and Manhattan distance functions) The dataset is extremely sparse which I think is causing the generated clusters to not make much sense as many machines get grouped into the same cluster(as they are very similar)

How to achieve clusters where each cluster contains approx equal number of points ? Or perhaps this is not possible due to the sparseness of the data and instead I should try to cluster on a different attributes of dataset ?

• Why do you expect that clusters, based on similarities among cases, should end up having similar numbers of members? If I have 20 blue balls and 2 red balls and cluster them according to color, I will end up with a 10/1 ratio of cluster sizes.
– EdM
Mar 27, 2015 at 14:25
• @EdM I don't which is why I suggested using a different dataset. Perhaps I should have been explicit about this Mar 27, 2015 at 14:28
• Whether your analysis is correct or not in its roots (main issues here may be your using of k-means with something based on Manhatten (non-euclidean) distance and, moreover, based on counts; notion of "sparsiness" instantly makes usage of k-means very questionnable), the wish to get approximately same-sized clusters is itself an exacting requirement. It implies imposing constraints on an algorithm. You should seek for specific procedures which algorithms allow for such constraining. Mar 27, 2015 at 15:33
• 1. Given that you have a very sparse data set of very similar machines, why do you expect any method to work? 2. What is your goal here? Are you expecting to find patterns that are not discernible without statistics? Jun 13, 2015 at 11:27
• @Peter Flom goal is to find machines that are similar based on what processes they run. That's it really. But analysis has proved that machines I'm analysing are quite similar and for that reason are not producing discernable patterns which is fine. Jun 13, 2015 at 12:20

Most clustering algorithms prefer minimizing spread over cluster element count. I.e. they try to find clusters of small extent to cover everything, not clusters of even size.

I'm pretty sure there must be more algorithms, but the only one I have recently come across that tries to keep cluster sizes the same is this Tutorial:

http://elki.dbs.ifi.lmu.de/wiki/Tutorial/SameSizeKMeans

In your case, I guess hierarchical clustering would be better than k-means. But in hierarchical clustering, ensuring same-sized clusters seems quite hard. At some point, you will have to do some really bad cluster assignment if you want to fix cluster sizes.

This is most obvious if you have a data set with extremely well separated clusters, but different size. Say you have 100 instances that are $N(0;1)$ distributed, and 1000 instances that are $N(10;1)$ distributed. If you enforce the clusters to have the same size, the result will be really, really bad by any measure.

• I may make this a separate question, but if anyone is aware of algorithms that try to keep similar cluster sizes, that would be appreciated. It would be ideal if there was a metric for how "bad" it would be to keep the clusters with the same size so that if it's too "bad" then you can change the size. (Edit: I found the question: stackoverflow.com/questions/5452576/…) Nov 27, 2018 at 22:01
• Well, quality of clusterings isn't that easy either. You can quantify the loss in SSQ if you run both regular k-means and a balanced version. But is that quantity actually measuring quakity? - probably not. None of the quality measures convinces me. They are okay for a first guess at least for k-means; but not much more. Nov 28, 2018 at 21:25

It would help to have counts of the total number of possible machines and processes. The second matrix looks to be kind of misleading since it consists entirely of zeros and ones. I've assumed in my answer that a fully realized matrix might contain some zero values but also have many cells with values greater than one representing the frequencies of occurrence of these machines across the processes. To be clear, I'm assuming that, e.g., m1 has more than one occurrence in your data, or alternatively, that there is more than one machine named m1. If the resulting matrix is, indeed, all zeros and ones with only one occurrence for each machine-process combination, then the question seems kind of silly.

I know you seem to want to fix the resulting cluster sizes, but aside from asking the obvious question why you want to do this ("I don't" above?), especially given the likely wide asymmetries in machine use of these processes. Some algorithms naturally tend to generate roughly equal sized partitions, e.g., Ward's Method but none of the algorithms that I'm aware of allow you to "fix" their sizes to be equal. This doesn't mean they don't exist, but having been a student of clustering and multidimensional scaling routines (a technique strongly related to clustering, moderators) for years, I'm not aware of any. That said, it would be possible, post-hoc, to adjust the resulting cell sizes to symmetry based on optimizing some multivariate distance function. Of course, you would destroy the properties inherent in your algorithmic solution in doing so. Again, why is this a needed restriction? Please clarify your motivation for this as a requirement or clearly eliminate it as a spec to the answer (moderators go off when posted answers don't specifically address a question, whatever that means).

That said, there are lots of ways to rescale the resulting data matrix for use in the plethora of possible clustering, multidimensional scaling and unfolding routines: these are definitely not limited to just k-means or hierarchical algorithm(s). Canonical discriminant analysis is one approach that would readily capture the two-mode nature of the information in your second matrix (machine by process frequencies). Other, even older approaches were developed at Bell Labs, Rutgers and U North Carolina's Thurstone Lab beginning back in the 50s and 60s by people including Kruskal, Carroll, Young, and Arabie, to name a few. Their algorithms include ALSCAL -- alternating least squares which dates back to Young but still sees wide use today in, e.g., machine learning approaches to collaborative filtering; KYST -- link to its manual here: http://www.netlib.org/mds/kyst2a_manual.txt; and IDIOSCAL -- individual differences scaling: http://www.netlib.no/netlib/mds/idioscal.f.

The key things across all of them are, first, the algorithm and its assumptions and, second, the scaling of the input matrices into the algorithm(s). For instance, you can use one big matrix representing the similarities (differences) in frequency of process occurrence between machines. This kind of matrix could be used, e.g., in a canonical discriminant analysis. If you have any additional information, e.g., the locations for these machines, timing of the adoption of different processes or, perhaps, some underlying adoption diffusion curve, this would change the shape of the matrix. Again, depending on the type of ancillary information available, it could be that you could expand the information for each machine by several more levels based on machine-specific replications over time and create an individual differences type of matrix that would be appropriate for an IDIOSCAL type routine. One caveat to the use of some of these algorithms is that they all rely on some type of dimension reduction in arriving at their solution: ALSCAL, in particular, is vulnerable to flipping dimensions over the differing inputs.

At the end of the day, there is no single, ideal, best, much less true answer to your question. You will need to play around a bit with the various options and find one which gives you a reasonable answer. Reasonable being subjectively defined and determined since none of us can tell you what this means.