Deterministic clustering approaches

I need a deterministic [in the sense - robust to the ways of initial input / initial seeds] clustering method to group values in distributions that could be either random, normal or log-normal. Google mostly turns up k-means, which isn't deterministic. Fixing the stochastic inputs (e.g. R's set.seed) is less desirable than methods that always return identical results for a particular set, so I can begin to understand and predict their behaviour. Does such a clustering method exist?

• It is unclear what is your data and what do you want your "deterministic" algorithm to do? Also, each of the methods that uses random numbers is deterministic given the seed. Many of the algorithms will let you use your own starting values (instead of random ones), but in many cases using different, random starting values lets you to prevent the algorithm of returning bogus results... – Tim Apr 6 '16 at 14:34
• Thanks Tim, I think your points are already covered in my question. – geotheory Apr 6 '16 at 14:54
• I don't know enough about the topic to really give a formal answer, but I do know there is research being done in convex clustering that should be an answer to your question: by making the objective function convex, you insure a global minimum with no other local minimum. But that's just about all I know at this time. – Cliff AB Apr 6 '16 at 15:18
• Agreed with @CliffAB here. Convex clustering is the way to go. It was developed exactly for this case -- that as long as you use the same value of the tuning parameter, you return the EXACT same clusters. I believe this is what you were referring to when you say "deterministic" (which would be more appropriately called reproducible). You should check out this R package: CVXcluster and references therein. – user23658 Apr 6 '16 at 17:10
• Also, is this for a fixed set of training/testing data? Because even with completely deterministic algorithms, if your training data varies between attempts, then the clusters likely will too. If the training data is fixed, then what's the problem with using a fixed random seed? – naught101 Mar 30 '17 at 0:13

I can point you to an algorithm and a family of algorithms:

• The algorithm is called IGMM (Incremental Gaussian Mixture Model). It is robust (but not insensitive) to order. But when data arrives in the same order, it always gives the same result.
• A family of clustering algorithms which satisfies your conditions is Spectral Clustering. They are batch algorithms and will give you the same results for the same datasets, even with different order.

EDIT: also, there are some methods for deterministic initialization of K-Means clusters, such as this one.

Hierarchical Agglomerative Clustering is deterministic except for tied distances when not using single-linkage.

DBSCAN is deterministic, except for permutation of the data set in rare cases.

k-means is deterministic except for initialization. You can initialize with the first k objects, then it is deterministic, too.

PAM like k-means.

... but there is probably 100 more clustering algorithms!

• Could you please elaborate more on your answer? In my understanding, The basic k-means clustering is based on a non-deterministic algorithm. This means that running the algorithm several times on the same data could give different results. – anu Dec 31 '18 at 20:11
• Except for initialization, as I wrote above, it is deterministic. Check again. – Anony-Mousse Dec 31 '18 at 20:55
• yes, but the whole algorithm is non-deterministic! The initialization is part of the k-means algorithm! so it should be a non-deterministic in nature! – anu Dec 31 '18 at 21:50
• There is not "the" k-means. MacQueen's algorithm (who coined the name k-means) is fully deterministic, as it uses the first k points as seeds. – Anony-Mousse Dec 31 '18 at 22:56

All the algorithms, by definition, are deterministic given their inputs. Any algorithm that uses pseudo-random numbers is deterministic given the seed.

K-means, that you used as example, starts with randomly chosen cluster centroids so to find optimal ones. Besides the initialization, the algorithm is totally deterministic, as you can make sure looking at it's pseudocode:

Nothing prohibits you from starting with non-random centroids. We use random centroids so to make sure that badly chosen starting points would not lead us to poor results. The same with other "random" algorithms: you can use them in "deterministic" fashion, but in most cases this is not a wise thing to do.

In case of k-means the algorithm deterministically minimizes the within-cluster sum of squares to find the optimal clustering solution. Unfortunately, it is sensitive to how the algorithm was initialized. Clustering problems in most cases do not have clear-cut solutions, because of that we often want to use randomized procedures to robustify them.

Imagine that you used some deterministic hierarchical clustering algorithm. Imagine that it goes through your data sequentially, starting from the first observation. What would happen if the first case was an outlier? On the other hand, if you initialized it several times at random points, the procedure would be less prone to problems with data.

Moreover, if you run non-"deterministic" algorithm multiple times and then use majority vote to choose for each case the class that appeared most commonly among the results, then the final output will also by highly deterministic.

• While this is a true statement, it doesn't appear to answer the OP's question: they are interested in cluster methods that are robust to initial values (within reason, of course). Also note that algorithms that definitively are not considered "deterministic" (i.e. MCMC) would give identical answers if the seed was set before running. – Cliff AB Apr 6 '16 at 15:25
• @geotheory: I can't see any reason why using a method that is robust to initial values would help this issue? The seems like an orthogonal issue. – Cliff AB Apr 6 '16 at 15:54
• @geotheory how would you imagine deterministic algorithm to help in such case? I see no reason why should it change anything. – Tim Apr 6 '16 at 16:14
• @geotheory results obtained using the same seeds should always be the same. You must have some kind of bug in your code if they are not. – Tim Apr 6 '16 at 16:51
• @geotheory in many cases, if there is no bug in the code, big variability of results would suggest that algorithm had problems in converging to the truthfully optimal solution. But "deterministic" algorithm is not a cure in here: is algorithm that would return the same wrong solution each time something better than the one that each time returns different wrong solutions (or that returns valid one with some probability)? This is exactly the case where randomisation helps to diagnose and prevent problems... – Tim Apr 6 '16 at 17:03

If I were to reinterpret your description of "deterministic," it sounds more like a longitudinal, "confirmatory" cluster analysis to me -- with the important exception that you haven't explicitly integrated time series considerations into your model. Confirmatory clustering methods are deployed once it is felt that the "space" they are meant to describe has been sufficiently well understood as to obviate the need for exploratory approaches. Speciation-based cladistics is one example of this.

Longitudinal cluster solutions are finally getting the attention they deserve in the literature. To the best of my knowledge, the earliest work dates back to the 80s with Pieter Kroonenberg's three-mode algorithms. But there is lots of interesting recent research that involves hidden markov chains, e.g., Steve Scott's papers or Oded Netzer's dissertation article both using HMMs, hierarchical, non-moment based information theoretic approaches such as permutation distribution clustering from Andreas Brandmaier as well as the chapters devoted to longitudinal clustering algorithms in Aggarwal and Reddy's book Data Clustering.

The key thing to keep in mind with all of these approaches borrows from Kroonenborg's conceptualization of a multi-mode matrix insofar as you can't have all of the modes moving at the same time. This means that the last thing you want to do is reinitialize the algorithm with each new dataset. Rather, you want to "fix," e.g., two out of three of the modes, allowing the third mode to vary in a kind of experimental "design." In this way, you can more carefully study how the dynamics of change impact a given niche in your data.

This approach is recommended regardless of the algorithm employed.

* EDIT * Actually, I'm wrong about Kroonenberg's work being the earliest on 3-mode analysis. Ledyard Tucker probably wrote the original article in 1966, Some mathematical notes on three-mode factor analysis.