Robustness of ML Model in question While trying to emulate a ML model similar to the one described in this paper, I seemed to eventually get good clustering results on some sample data after a bit of tweaking. By "good" results, I mean that


Each observation was put in a cluster with high probability (as opposed to having being 50/50 between two clusters or something similar)
A high proportion of the observations were put in the correct cluster, indicating that the model actually did work.


For example, if we had observation $a$ that belonged to cluster $A$, and observation $b$ belonging to cluster $B$, then the model might output (0.99, 0.01) for observation $a$ (where the 0.99 indicates a high probability for $a$ belonging to $A$ and 0.01 represents a low probability of belonging to $B$) and (0.02, 0.98) for observation $b$. (These specific numbers are chose randomly, but generally the good results give probabilities close to 0 and 1.) However, every few times I train the model, I get a weird result; one that seems to still 'cluster' the data in a sense, but is technically wrong. A bad result would give something of the nature (0.99, 0.01) for observation $a$ (which is good), but then give something like (0.65, 0.35) for observation $b$ . In this way, when I look at the data I can tell that it has been "clustered" as the observations that belong to $A$ give different cluster probability distributions than the observations of $B$, but the model has not accomplished either of the two goals above when actually assigning clusters. 

I would like to make my model more robust so that I get "good" results more often, but I don't know what I could do to do this. One thing that would definitely work to help avoid this problem would be to do the cluster training many times and take the average result; the problem with this is that each training takes somewhere on the order of hours, meaning that doing it multiple times might take on the order of days, which I want to avoid. 

If there are any (hopefully quick) fixes I can do to avoid getting these odd results, I would love to hear any advice on the topic. I should also be able to answer questions if you need more information, but the paper I linked should have most of the pertinent info.
Clustering is an unsupervised approach wherein unlike supervised learning its devoid of not knowing the class label or the response or dependent variable. In clustering, the idea is to determine patterns in data such that it can be grouped into cohesive clusters. Such groups will have data points that are similar to each other whilst dissimilar to other data points in other groups. Now, clustering algorithms can broadly be classified into two types, namely, partitional and hierarchical. Some well-known partitional clustering algorithms in the literature are k-means (that works for numerical data only), k-modes (that works for categorical data only), and the k-prototypes (that can work for mixed data (i.e. both numerical and categorical data)).
A fundamental problem associated with partition-based clustering algorithms is not knowing the initial number of groups. And as such researchers using this class of algorithms often fall into this trap by failing to address this fundamental issue. Thus their results are not reproducible.
In literature, there exist several approaches to have proposed to solve this issue of Estimating the possible number of clusters. A well-known approach is the Elbow method proposed by researchers (Kaufman &amp; Rousseeuw, 2009). I fact a group of researchers developed an R package called NbClust that can be used to estimate the number of clusters using the elbow method. This package contains ~30 algorithms for determining the number of clusters.
Recommendation when building a partition-based clustering model
I would recommend the following steps for result reproducibility

setting a random seed value
choose a method to determine the number of clusters
run the experiment at least 5 to 10 times, note the result for each run, and then average the values. Report the averaged value as the final result.

Reference
Kaufman, L., &amp; Rousseeuw, P. J. (2009). Finding groups in data: an introduction to cluster
analysis (Vol. 344): John Wiley &amp; Sons