Clustering Small Text Descriptions Im presented with a unique text classification problem.

Im given a list of descriptions each containing 3-8 words. I know that there are some descriptions that are nearly the same, but the majority of them are significantly different from each other. My objective is to group the descriptions that are roughly the same and to consider the rest of the descriptions as unique. This data set can be considered too long to manually label for supervised learning.

My thought process so far:


TF-IDF will come in handy as the frequency of words that match is extremely low (therefore any match is highly valuable).
Unsupervised clustering techniques like K Means might be useful, but there is an inherit, "K" selection issue with K Means in this space. For example, if we have 1,000 descriptions and only 10 descriptions (5 clusters of 2 descriptions) are supposed to be clustered with one another (leaving 9,990 unique descriptions), we would need 9,995 clusters to represent the structure accurately (9,990 clusters with 1 item and 5 clusters with 2 items each). This issue would lead to an extremely difficult model building phase as the number of clusters would be so high (perhaps this isn't an issue and this theory should be tested).


I am very new to the space of unsupervised learning being used with NLP. I have a few more thoughts that I could elaborate on, but I really need some advice on how others deal with clustering text in this way. I dont need to use K Means or any other specific idea if better alternatives fit the problem space better.



Edit: 

I am starting to think that DBSCAN will be a much better clustering model. This documentation explains that each point can be clustered and outliers are not taken into consideration more so than real groups (under specific configuration). In more technical terms, I believe setting a low eps score with a minpts values of 2 will be a good theory to test. This essentially assumes that most data belongs to its own cluster (most of the data is unique), but some data (under a weak minimum points configuration) should indeed be grouped into a cluster. DBSCAN avoids the pitfalls of K Means by dealing with outliers in an algorithmic way. K Means would be heavily dependent on a genius guess of a "K" value.
On the top of my head:


with regular clustering techniques you could try to use text-specific distance/similarity measures instead of only considering distinct words as elements. There are hybrid string similarity measures such as SoftTFIDF which take into account character-based and word-based similarity.
use lemmas instead of words in order to facilitate matching of the same concept
for more specific NLP methods you could look at topic modeling and/or word sense induction techniques. The two follow similar ideas in different ways: the former is closer semantically to your case, the latter is meant to work with small context windows similar to your short descriptions size. I'm not sure what is the state of the art nowadays but Latent Semantic Analysis was the standard not so long ago. Afaik these techniques are meant for a quite high amount of data, but they might be worth trying.