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?
 A: 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!
A: 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.
A: 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.
A: 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.
