3
$\begingroup$

I have to analyse a data set with weka clustering, using 3 clustering algorithms and I need to provide a comparison between them about their performance and suitability. The comparison may include a description about how to adjust parameter values of the clustering algorithms to make them perform better. The three algorithms are SimpleKmeans, DBSCAN and HierarchicalClusterer.

So, my questions are: What kind of variables do I need to look at when measuring performance and suitability? The one that I managed to find so far is Within cluster sum of squared errors. And also, which parameter values do I need to adjust in order to make the algorithms perform better?

$\endgroup$
2
$\begingroup$

this is a partial answer.

First of all you may find a similar question here : https://mathoverflow.net/questions/22081/how-to-compare-two-cluster-solutions

Now I do not know much about weka but what you could do is comparing clustering methods using silhouette coefficient, inertia or gap_statistic (Tibshirani 2001, may cost a bit to compute, can find the article on google). These coefficients have the advantage not to require the knowledge of the ground truth classes (contrary to adjusted rand-index for example).

For kmeans and hierarchical clustering, you can choose the number of cluster k by looking at the maximum of silhouette coefficient, an elbow in inertia plot vs number of cluster or the maximum gap statistic. I do not know what to do for DBSCAN, maybe silhouette is still relevant ? Inertia and gap statistic will not be relevant because they assume kind of "round" clusters.

In a way, to compare DBSCAN and the two others, you have to get a sense of your data distributions. Kmeans and hierarchical will perform well if the underlying clusters are convex whereas dbscan can find clusters of any shape.

Hope this is useful.

$\endgroup$
1
$\begingroup$

Measures such as WCSS (aka SSQ, variance), Silhouette etc. must only be used to compare results of multiple runs of the same algorithm. Comparing different algorithms with such an internal measure is misleading. The issue here is that you are more likely to measure which algorithm is more closely related to the concept of evaluation, not necessary which produces the better clustering result!

This is best seen by trying to compare $k$-means performance for different $k$. You'll notice that when increasing $k$, the WCSS values only get better and better. But in practise, the result doesn't really improve anymore, but it degenerates to the trivial solution "every object is its own cluster" (which has WCSS 0, and is "optimal" for this measure!)

Which is why Silhouette comes into play. It's an orthogonal measure, that $k$-means doesn't optimize. Since different $k$-means runs don't use this measure, and it doesn't just trivially improve with $k$, none will have an unfair advantage, and you can reasonably use Silhouette to compare different $k$-means even with different $k$. But next, you'll have someone make an "improved $k$-means algorithm" that always returns the result with the best silhouette, and thus appear to always outperform $k$-means; but not so much because the results are of higher quality, but because they know how you measure "quality".

Try different normalization, and their effect on your results and scores. You will be surprised how sensitive both internal evaluation and algorithms are wrt. normalization. Are you sure that none of the algorithms performs implicit normalization? Some k-means implementation will first perform PCA to "whiten" your data set (rescale and rotate your data to have unit variance and no covariances)

Furhtermore, DBSCAN for example has the concept of noise. In many implementations, this means it produces a "cluster" (which isn't actually a cluster) containing all the elements DBSCAN considers to be "outliers". Using a measure such as WCSS, Silhouette etc. on the noise "cluster" is just plain wrong. Of course this cluster will have a massive variance, because it has all the outliers! An alternate "interpretation" is to make each element in this cluster its own one-element-cluster for evaluation. But then you have hundreds or thousands of clusters, and a really low WCSS socre; but this also does not reflect reality.

Cluster evaluation is an art, and I would strongly advise against trusting a single mathematical number to capture this. Instead, you should evaluate whether the result is useful in practise.

In particular, make sure that:

  • The measures you use are appropriate for the algorithm (neither WCSS nor Silhouette are appropriate for DBSCAN, for example, and at least WCSS is also a bad idea to use with hierarchical clustering)
  • They can capture all formal concepts of the algorithms (for example "noise" as returned by DBSCAN, or soft assignments as produced by EM and Fuzzy C-means)
  • The measures are not related to the algorithms. $k$-means optimizes WCSS, so you must not use WCSS to compare other algorithms to $k$-means (or compare different $k$). $k$-means by definition must win (algorithms may get stuck in a local minimum; but the $k$-means problem is defined as finding the best WCSS partitioning). Don't use a measure to evaluate DBSCAN which does not have explicit "noise" treatment. Don't assume "noise" is a cluster; it's not, even when many implementations return a noise partition (often the first or last "cluster" is the noise). Similarly, for EM and fuzzy c-means, use an evaluation procedure which allows "fuzzy" aka "soft" assignments (partial cluster membership).
  • Try different normalizations; and make sure the algorithms you evaluate don't perform an automatic normalization which makes it unfairly harder for them to find anything. For example, some algorithms rescale the data to $[0;1]$. Putting a single far-away outlier will make this normalization to behave really badly, removing the outlier will substantially improve results.

You may want to read the Wikipedia article, which has a section on Evaluation.

P.S. instead of Weka, you may want to use ELKI which is much more powerful for clustering. If you have labeled data, it will automatically produce a number of common evaluation measures (but you'll mostly see that there are too many measures). It currently does not seem to include internal measures such as WCSS or Silhouette.

$\endgroup$
1
$\begingroup$

For a concise mathematical comparison you must use some kind of metric (as pointed by Scratch's post).

You might compare just the best clustering found for each method, but clearly you spend a lot of time finding good parameters, the method is not too good and this aspect would be lost by just looking at best results.

Hierarchical clustering techniques (like Single/average linkage) allow for easy visualization without parameter tuning. For k-means you could visualize without bothering too much about choosing the number of clusters k using Graphgrams (see the WEKA graphgram package - best obtained by the package manager or here! For DBScan you have two parameters, you could go for OPTICS that allows to visualize the result. You would get 3 different kinds of plots, which makes interpretation not trivial (in particular, compared to a single number given by a metric), but the information you get, once you understand the plots is a lot more than even several metrics can provide.

$\endgroup$

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.