5

I am using Silhouette width to compute the best value for k in k-means. As I am performing document clustering, I am calculating the values of a and b as follows in Python:

a = distance(data[index], centroids[clusters[index]], metric=metric, p=p)
b = min([distance(data[index], c) for i,c in enumerate(centroids) if i != currentindex])
score = float(b - a) / max(a, b) if max(a, b) > 0 else 0.0

The original formula from the Wikipedia page is the following:

enter image description here

I am using a cosine similarity measure to compute the distances and was wondering if this formula needs to be changed or it can be left as is. In the above snippet of code, the function distance computes the cosine similarity metric.

Legend
  • 4,232
  • 7
  • 37
  • 50
  • I'm not sure if it is appropriate to use a centroid-based method along with cosine distance. Centroids are obviously minimizers for L_p-norms, but I'm not sure about whether this holds for cosine distance. Anyone knows if the centroid also minimizes cosine? – Has QUIT--Anony-Mousse Feb 10 '12 at 20:35

2 Answers2

7

Silhouette statistic works on distances, not similarities. One should revert similarities into distances. The general pass to do it: 1) set diagonal as 0, 2) revert sign of elements, 3) find the smallest element and substract it from each element, 4) set diagonal as 0.

For cosine or correlation there is also a geometrically more correct way: distance = sqrt[2(1-similarity)]; it comes from trigonometric "cosine theorem".

BTW, if you use SPSS you can find a collection of macros on my web-page that compute a number of clustering criterions, including Silhouette.

Community
  • 1
ttnphns
  • 51,648
  • 40
  • 253
  • 462
  • +1 for your time. Thank You! Actually I am using python as I don't have SPSS. But thank you very much for your suggestion. Just to confirm, I just need to change the distance function to calculate what you suggested and I do not have to make any modifications to my original formula. Is that correct? – Legend Jul 12 '11 at 04:51
  • You see, I'm in difficulty to say if your computation of a(i) and b(i) terms is correct - because I hardly know Python. I said only that they are computed based on distances, not similarities. What is worth doing for you, anyway, is to google some articles on the Silhouette, not just Wikipedia, to make sure that you compute it right. – ttnphns Jul 12 '11 at 05:11
  • Thank you for your suggestions. I accepted your reply as an answer. What is more interesting is that the cosine distance calculation function I am using from scipy gives me values greater than 1 because of which the value under the square root is coming out to be negative. I guess I need to see what is wrong with the function. – Legend Jul 12 '11 at 05:11
1

You can calculate the silhouette for similarity matrix. The seminal paper, by P.J Rousseeuw about silhouette, explains about how to calculate silhouette from similarity matrix:

  1. calculation for Cohesion remains same.
  2. For computing Separation, take maximum instead of minimum.
  3. for calculating silhouete, the numerator changes as follows: cohesion-separation.

Refer to page 57 in the paper Silhouettes:a graphical aid to the interpretation and validation of cluster analysis, by Peter Rousseeuw

chl
  • 50,972
  • 18
  • 205
  • 364
user11158
  • 11
  • 1