I want to compare the performances of two clustering algorithms that give me different numbers of clusters. I recently learned about the gap statistic. However, from what I have learned, this statistic is used to find the optimal number of clusters for one algorithm (On that page, for example, it is used to find the best number of clusters for k-means). Is it possible to use it to compare which algorithm clusters gives the best performances? (finds the clustering that minimises the distance in clusters and maximized the distance between them)
Logically, the answer should be yes: you may compare, by the same criterion, solutions different by the number of clusters and/or the clustering algorithm used. Majority of the many internal clustering criterions (one of them being Gap statistic) are not tied (in proprietary sense) to a specific clustering method: they are apt to assess the clusters whatever method used. They just do not "know" if the being compared solutions with various number of clusters have come from the same or from different clustering methods.
However the majority of criterions should be applied to the same clustered dataset, unless a criterion value is well-thought standardized (which is not an easy task).
P.S. In their reasonable answer @Anony-Mousse raised an aspect which I had decided to hush up above.
There exist no balanced or "universal" clustering criterions; any one of them bears some homology to the objective function of this and not that clustering algorithm, by virtue of which it tends to "prefer" one algorithm to another (and one shape of clusters to another, too). Gap statistic retains something of the K-means function, while Silhouette has clear trace of average linkage hierarchical method. They are not "orthogonal" to anything. A clustering criterion is itself an objective function of some clustering algorithm not invented exactly so, yet. An algorithm is good for us (in respect to cluster separability) if it wins when judged by the criterion we want. And it is unclear what else it might be that is the measure of
Note that some algorithms will try to optimize the gap, others won't.
By comparing different algorithms with a measure that correlates with some of the objective functions, you will be more likely measuring how similar the algorithm is to the gap statistic, but not how good it actually works.
A similar problem occurs with pretty much every measure.
For example, the "sum of squares" (SSQ) measure is internally used by k-means, and it improves with the number of clusters (up to 0, when k=number of objects). K-means is (approximately, as the common algorithms only find local minimas) optimal with respect to this measure. And the optimum k is the number of objects.
So obviously, any other algorithm will look bad compared to k-means, and yet the optimum result will be entirely useless.
Be careful when relying on such metrics. You measure a mathematical quantity that may not be capturing your needs.
Things such as using the gap statistic or silhouette with k-means sometimes work well, because they are actually "orthogonal" to the objective used by k-means. Instead of blindly searching for the best k-means result (which would yield a much too high k), you use this secondary measure to compare k-means results. It works, because even with different k, k-means still optimizes SSQ, and not the gap statistic.
Note that it already fails when you try different normalization before running k-means. It's trivial to reduce gaps just by scaling the data set down; the preprocessing has a strong effect on these statistics.
When you compare different algorithms, usually each optimizes different quantities; so the comparison will usually not be fair. Actually, in most cases the result will not be fair; the only situation where it works reasonably well is varying the cluster number of k-means, and keeping everything else as is.