An algorithm similar to (or based on) K-means that do not require the 'k' number of clusters These days I'm using a lot (and discovering) nice ways to use k-means' clustering. For example, clustering word embeddings (word2vec vectors) to find synonyms or clustering doc vectors (doc2vec) to classify topics. 
But for these tasks I always need to specify the number of clusteres (the 'k'). Is there some unsupervised algorithm that estimates a good number of clusteres and (but not must do) do the clustering task?
 A: Yet another approach is to use the Mean Shift algorithm. You must specify a radius around points to explore, but it determines the number of clusters.
A: The NASA Autoclass employs Bayesian approach to inferring not only the cluster centers but also the most likely number of clusters. A similar tool, NBCTK, uses more modern inference algorithms (e.g. Variational Bayes).
Some of the nice features include:


*

*Support for mixed data types (e.g. discrete and real-valued features)

*Handles missing values


It works fairly well on relatively small datasets (on my datasets). Some basic understanding how the algorithm works under the hood helps to use the tool to its best potential. Expect time to process even moderate size datasets to be significant.
Note: The most likely number clusters are found under the assumptions made by the model. One must not interpret the results as absolute truth.
A: If you mean clustering without specifying number of clusters up front, you have a couple of approaches


*

*estimate $k$ - use elbow method or x-means. Also, bisecting kmeans doesn't need $k$ specified.

*use different clustering scheme altogether


If you choose 2 then you have further types of methods


*

*use hierarchical clustering 

*use density-based clustering algorithms like DBSCAN, or its newer cousin, HDBSCAN


Both hierarchical methods and density-based methods require some kind of distance parameter to be specified - the clusters are formed by grouping the points based on that distance.
A: DBSCN, Affinity Propagation are clustering algorithms that don't require that you specify k. 
Alternatively, you can iterate through multiple values of k and see which one gives you the best results using some similarity measure. 
A 3rd approach is ask a domain expert in whichever domain you are working in to give you a rough estimate of how many clusters you should be expecting. 
A: Density clustering methods (MeanShift, DBScan....) don't require to specify the number of clusters, you specify something like the order of magnitude of the distance of points considered as "connected". The parameter is (very) roughly speaking the expected radius of a cluster, and then it finds the best number of clusters.
Density algorithms tend to fail in large dimension because the space is almost empty everywhere (or alternatively the distances gather around a certain value in a way that is extremely difficult to compensate). Density algorithms thus often require dimension reduction first, unlike k-means. With word2vec you usually start with dimension 300, which might be a problem (to experiment). If the density algorithms fail, then you can reduce the dimension first, possibly drastically.
