1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ It is difficult to define exactly what a cluster is, indeed. I was expecting a few propositions, in order to pick the one looking the most meaningful to me. I've added a specific case description to my question, maybe does this helps narrowing down the applicable tools? $\endgroup$
    – Vincent Labatut
    Sep 7, 2018 at 5:04
  • $\begingroup$ I've also added to my question some idea I had regarding the distribution of the similarity values, which is related to the last part of your answer. $\endgroup$
    – Vincent Labatut
    Sep 7, 2018 at 5:11
  • $\begingroup$ Well, k-means ist one, Silhouette another, DB index, c index, ... $\endgroup$
    – Has QUIT--Anony-Mousse
    Sep 7, 2018 at 11:03
  • $\begingroup$ If I'm not wrong: $k$-means is not a measure or statistic but a partioning method; the Silhouette, DB index and C index are not defined for $k=1$; and the DB index requires the raw numerical data (cannot use the dissimilarity matrix). (and If you meant $k$-means objective function, it also requires the raw data). $\endgroup$
    – Vincent Labatut
    Sep 8, 2018 at 12:06
  • $\begingroup$ The KMeans statistic is called "sum of squares". And yes, most are not that useful for checking the existence of clusters. They are all just heuristic, and each defines a different definition of what is a good cluster. Pick one of the 20+ that people have proposed. For example AIC or BIC may be able to decide whether your k=2 clustering did the data better than a k=1 clustering. $\endgroup$
    – Has QUIT--Anony-Mousse
    Sep 8, 2018 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.