Test for cluster existence based on dissimilarity matrix

Question

Context: I want to detect clusters in a dataset. This dataset is constituted of non-numerical objects, for which I am able to compute a dissimilarity matrix. I apply the $k$-medoids clustering method to partition the dataset using various values of $k$, based on this matrix.

However, I do not know a priori if there are any clusters in my dataset: there could be just a single one, or several.

Question: is there a statistical test (or measure) allowing to determine whether there are more than one cluster in such a dataset?

Note : All the measures I could find, either deal with $k \geq 2$ clusters (like the Silhouette for instance) or require numerical data (i.e. cannot work with only the dissimilarity matrix).

Edit 1: Here is one specific situation I met. Suppose that you use the Silhouette (or any other similar measure) to assess the partitions you detected for $k = 2,...,n$, and that the obtained values decrease as $k$ increases. One may wonder if there are any clusters at all, hence the need to test for this assumption.

Edit 2: I am considering studying the distribution of the dissimilarity values and check its modality. I assume that it should be bimodal only if there are several clusters (one mode for strongly similar pairs, the other for strongly dissimilar ones). This idea is so simple that either there must already be some reference describing it, or it is flawed and somebody already explained that. In any case, I would like any reference you may have.

Answer 1

Existence or validity of clusters is not very well defined. Largely because there is no single concept of clusters, either!

From a k-means point of view, there always exist k clusters.

Some of the common criteria for k-means do work for k=1, too. I just usually recommend to not rely on them too much, as they are just heuristics, and frequently give bad recommendations rather than the "true best" k.

So if you want any such test, you will have to narrow down the definition of clusters.

There are some attempts to define a "clustering tendency" but these will usually consider Gaussian data to be "clustered" and are essentially test for uniform distributions. You could try to protect them from distances to similarities, if you can generate "uniform" distribution. But as far as I can tell, they will likely not help you to decide whether there are 1, 2 or more clusters.