4
$\begingroup$

I have a dataset of binary files. I can't do feature extraction on them. I just computed the distance between every pair of file in the dataset with a distance metric (NCD = Normalized Compression Distance). So I have a distance matrix.

My goal is to cluster these files. What is the best way to do that?

Improve this question
$\endgroup$
10
  • 4
    $\begingroup$ There are still a lot of clustering algorithms that will work, even if you only have a distance matrix & no longer have the raw data. Eg, if you are interested in hierarchical clustering, once you have a distance matrix you can do either single-linkage clustering or complete-linkage clustering w/o the original data. $\endgroup$
    – gung - Reinstate Monica
    Commented May 2, 2014 at 3:16
  • $\begingroup$ How can I analyze the clusters? $\endgroup$
    – Sina
    Commented May 2, 2014 at 3:18
  • $\begingroup$ What do you mean "analyze the clusters"? $\endgroup$
    – gung - Reinstate Monica
    Commented May 2, 2014 at 3:18
  • 2
    $\begingroup$ I'm not sure, I'm not familiar w/ NCD--I don't know what kind of distance it is. If you only have a distance matrix, you could do a multi-dimensional scaling to get points w/i an (arbitrary) space, & use that for plotting. The 1st 2 dimensions are analogous to the 1st 2 PCs in PCA. $\endgroup$
    – gung - Reinstate Monica
    Commented May 2, 2014 at 3:25
  • 2
    $\begingroup$ If you want visualisation, then the OPTICS landscape visualisation is quite nice. It is of course tied to the OPTICS method. As a side note, it is possible to visualise clusters produced by any type of algorithm onto the OPTICS landscape plot (but I don't know a general way of doing this), and your data is amenable to a wide range of clustering algorithms, including network-based algorithms. For the latter, you will need to work with similarities rather than distances. $\endgroup$
    – micans
    Commented May 2, 2014 at 10:43

2 Answers 2

Reset to default
2
$\begingroup$

Many, many algorithms are based on distances only:

  • hierarchical clustering, with most linkages (single-link etc.)
  • DBSCAN
  • OPTICS
  • PAM (Partitioning around Medoids, aka k-medoids)
  • Affinity propagation

Of course there are also a number of methods that need coordinates. In particular

  • Centroid-based methods such as k-means need coordinates to compute the centroid
  • Grid-based methods such as DENCLUE need coordinates to compute a grid
Improve this answer
$\endgroup$
1
$\begingroup$

so if you are able to do pair-wise distance calculation on your data, then you can certainly cluster your data with, for instance, k-means, which is based entirely on pair-wide distance calculation (though between each data point and a group of composite data point (aka centroids)

if you are not familiar with k-means, it works like so:

  • choose N, an integer value that represents the number of centroids, cluster centers (some refinements to the basic algorithm include a step to calculate the optimum number of centroids, eg, k-means plus)

  • select N data points at random; these are your centroids at t=0 (iteration 1)

  • for each remaining data point, calculate the pairwise distance from each of the N centroids; the centroid that give the smallest value (the centroid the point is closest to) is the centroid that data point is assigned to for iteration 1

  • now your data is partitioned into N groups; for each group of data points, calculate a single mean data point--these N points are the new centroids at iteration 2

  • repeat the step above until some stopping criteria is reached (eg, less than one percent mean diff between the centroids in two consecutive iterations)

Improve this answer
$\endgroup$
3
  • $\begingroup$ -1: k-means is not based on pairwise distances. On the contrary. It is based on sum of squared 1d deviations from centroids only. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented May 2, 2014 at 14:07
  • $\begingroup$ @Anony You might be a little too harsh here. If we read this answer just a little more generously and understand "based on ... distance" to include squared distances, then it is a mathematical fact that one-half the sum of pairwise squared distances within a cluster equals the sum of squared distances to the centroids. $\endgroup$
    – whuber ♦
    Commented May 2, 2014 at 15:13
  • 1
    $\begingroup$ @whuber The reason for the -1 is mostly that computing distances to centroids is exactly what is not possible here. He is clustering executable files (see his previous question), which he compares by compression distance. What is the centroid of a bunch of executables? $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented May 2, 2014 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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