0
$\begingroup$

I found a C library for clustering and I was reading about the distance matrix here: it says:

The first step in clustering problems is usually to calculate the distance matrix. This matrix contains all the distances between the items that are being clustered.

If I have a cloud of data (I'm studying web traffic and I'm trying to classify it not with known ports or payload inspection, but with some kind of pattern recognition of collected data such as total number of packets, mean packet size, mean payload size excluding headers, number of bytes transfered), how should the distance matrix be set?

The quote says

This matrix contains all the distances between the items that are being clustered

so some kind of clustering has already been done? I think I'm missing something...

$\endgroup$
  • $\begingroup$ The very word "cluster" connotes a set of things that are mutually "close." It is up to you to determine what you mean by "close"--but that determination does not imply any clustering has yet been done. $\endgroup$ – whuber Jan 19 '16 at 14:01
0
$\begingroup$

Whatever source that is, it is wrong, and probably not of high quality.

The first step in clustering problems is usually to calculate the distance matrix.

I disagree that this "usually" is the first step. There are plenty of examples (e.g. k-means, DBSCAN, SLINK, EM/Gaussian Mixture modeling, ...) that do not need a distance matrix at all.

In fact, for large data, computing a full distance matrix will kill you - any algorithm that requires a distance matrix is not scalable to large data.

But you also stopped reading after the first step. At this point, no clustering has been done yet. But if you use an algorithm that does use a distance matrix (say, the naive $O(n^3)$ algorithm for hierarchical clustering) then you have already done a substantial amount of computation. While this part is only $O(n^2)$, it is already very expensive.

$\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.