0
$\begingroup$

I've been investigating, reading and testing about hierarchical clustering, more specifically the single linkage approach. To which I understand that the naive approach of going through the entire distance matrix created before-hand, obtaining the minimum distance to merge two clusters and then updating said matrix by deleting the corresponding rows and columns of the merged points/clusters to then create a new one that represents said new cluster is what makes the complexity $O(n^3)$.

I found the SLINK algorithm proposed by R. Sibson that claims to lower the complexity to $O(n^2)$ with the use of the following pointer representations of a dendrogram:

$\pi(N) = N \;\;\; \lambda(N)=\infty$
$\pi(i) > i \;\;\; \lambda(\pi(i))>\lambda(i) \;\;\; for\;i<N$

$\lambda(i) = \inf\left \{ h:\exists j > i \;\; with \; (i,j)\in c(h) \right \}$
$\pi(i) = \max\left \{ j:(i,j) \in c(\lambda(i)) \right \}$

Using the pointer representation defined above, the algorithm is derived from the following recursive equations:

For given $n$ we define $\mu_{n}(i)$ recursively on $i$:

$\mu_{n}(i) = \min\left \{ d(i,n+1), \underset{\pi_{n}(j)=i}{\min} \max \left \{ \mu_{n}(j), \lambda_{n}(i) \right \} \right \}$

Thus $\mu_{n}(i)$ is defined for $i = 1, ..., n$ and since

$\mu_{n}(i) \leqslant d(i,n+1)$

and $d$ is a (finite) DC, $\mu_{n}(i)$ is finite for all $i$. We then define $\pi, \lambda$, which we shall prove to be the pointer representation of $C_{n+1}$, that is, $\pi_{n+1}, \lambda_{n+1}$, as follows.

$\pi(n+1) = n + 1$
$\lambda(n+1) = \infty$

$\lambda(i) = \min\left \{ \mu_{n}(i), \lambda_{n}(i) \right \}$ for $i < n + 1$

$\pi(i) = \pi_{n}(i)$ except that if $\mu_{n}(i) \leqslant \lambda_{n}(i)$ or
$\mu_{n}(\pi_{n}(i)) \leqslant \lambda_{n}(i) \: \: then \: \: \pi(i) = n + 1$, again for $i < n + 1$

The problem I face is that even though I feel like I understand the main gist of the algorithm thanks to the implementation done based on the pseudocode, as well as its connection to the mathematical equations, I don't fully understand the reasoning/intuition behind the equations themselves as they're derived above.

I've also found a summary of the article done by Veronika Strnadova-Neeley that takes a slightly different approach from the original SLINK by Sibson, while still being $O(n^2)$ albeit quite a bit slower as the number of data points increase.

I'm looking for an explanation similar to the summary provided by Veronika which is a lot easier to digest but seems different to the original concept from the article by Sibson, I'd appreciate if anybody's got insight on how to understand these mathematical equations that define the algorithm.

$\endgroup$

1 Answer 1

1
$\begingroup$

In essence, it's Prim's algorithm.

The only difference is the data storage. The format used by SLINK is more memory efficient than the usual format you would use with Prim's.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer! Checking Prim's algorithm and its visual presentation has indeed help me understand SLINK better, that's very helpful, but the whole mathematical definition still manages to avoid my understanding. $\endgroup$
    – Rodrigo R.
    Apr 6, 2018 at 16:01
  • $\begingroup$ The definitions don't capture the algorithm logic. They capture the output data structure. $\endgroup$ Apr 6, 2018 at 17:20

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.