Identifying templates with parameters in text fragments I have a data set with text fragments having a fixed structure that can contain parameters.
Examples are:

 Temperature today is 20 centigrades
 Temperature today is 28 centigrades


or

 Her eyes are blue and hair black.
 Her eyes are green and hair brown.


The first example show a template with one numerical parameter. The second one is a template with two factor parameters.

The number of templates and the number of parameter is not know. 

The problem is to identify the templates and assign each text fragment to the corresponding template.

The obvious first idea is to use clustering. The distance measure is defined as a number of non matching words. I.e. the records in example one have distance 1, in example two distance is 2. The distance between the record in example one and two is 7.
This approach works fine, providing the number of clusters is know, which is not the case, so it is not useful.

I can imagine a programmatic approach scanning the distance matrix searching for records with lot of neighbors in distance 1 (or 2,3,..), but I'm curious if I can apply some unsupervised machine learning algorithm to solve the problem. R is preferred, but not required.
You might consider using word2vec to identify phrases in the corpus.  The presence of a phrase (instead of single tokens) is likely to indicate a 'template.'  

From here, the tokens most similar to your template phrase are likely to be the values for your parameters.