<p>Have you considered <a href="http://arxiv.org/abs/1112.2903" rel="nofollow">Correlation Clustering</a>?<br>
If you read carefully section 2.1 in that paper you'll see a probabilistic interpretation to the recovered number of clusters.</p>

<p>The only modification you need for your <code>M</code> matrix is to set a threshold deciding what distance is considered "same" and what distance is too large and should be considered as "not-same".</p>

<p>Section 7.2 in the aforementioned paper deals with a clustering of a full matrix where the recovering of the underlying number of clusters is an important part of the task at hand.</p>
Clustering given pairwise distances with unknown cluster number?
<p>I have a set of objects <code>{obj1, obj2, obj3, ..., objn}</code>. I have calculated the pairwise distances of all possible pairs. The distances are stored in a <code>n*n</code> matrix <code>M</code>, with <code>Mij</code> being the distance between <code>obji</code> and <code>objj</code>. Then it is natural to see <code>M</code> is a symmetric matrix.</p>

<p>Now I wish to perform unsupervised clustering to these objects. After some searching, I find <a href="http://en.wikipedia.org/wiki/Spectral_clustering" rel="noreferrer">Spectral Clustering</a> may be a good candidate, since it deals with such pairwise-distance cases.</p>

<p>However, after carefully reading its description, I find it unsuitable in my case, as <strong>it requires the number of clusters as the input</strong>. Before clustering, I don't know the number of clusters. It has to be figured out by the algorithm while performing the clustering, like DBSCAN.</p>

<p><strong>Considering these, please suggest me some clustering methods that fit my case</strong>, where</p>

<ol>
<li>The pairwise distances are all available.</li>
<li>The number of clusters is unknown.</li>
</ol>