2
$\begingroup$

I need to use a customized linkage function for my project. For this function, on every step I should calculate the objective containing

  • similarity (distance) between subclusters to be merged
  • distances between leaves and roots in terms of edges in the forest of subclusters.

Currently I'm using scikit-learn AgglomerativeClustering. I looked through a question related to mine.

I found that the merging operation for max link and average link happens in the script.

However, I cannot find where the the distances between all the subclusters are calculated and how to derive a number of edges between leaves and roots in subclusters.

How can this be done?

UPD: I am trying to implement Chakrabarti algorithms for smooth clustering over time. For agglomerative clustering, a choice for next clusters to be merged depends on two components: similarity between subclusters at current time stamp and a historical cost related to the previous time stamp. The latter has several variations. For example, one includes merge distance (not only that): if we would merge two subclusters S1 and S2, what would be the average distance (in terms of edges) between all leaves in S1 and S2.

There are a couple of questions about sklearn AgglomerativeClustering:

  1. What lines in the code implement a choice of clusters to be merged at the current step?

  2. Is it possible to extract a distance between a leaf and a root of a subcluster at each merging step? I noticed there is an attribute 'children_' in AgglomerativeClustering which I could use to create the resulting tree and find distances between any nodes. How to extract such an information for every merging step?

$\endgroup$
1
$\begingroup$

Most implementations will begin with a distance matrix (and not a data matrix) as input, as the algorithms are O(n²) anyway.

For the second question, I don't understand how that is defined. If your linkage is not a Lance Williams update, you may need to reimplement hierarchical clustering completely, to make sure you have all the information you need. Lance Williams are much more elegant to compute.

$\endgroup$
  • $\begingroup$ Thank you, @Anony-Mousse! I updated my questions with deeper explanations. $\endgroup$ – Mirit Dec 19 '17 at 10:30
  • $\begingroup$ For this use case, I strongly suggest to implement it yourself, rather than hacking around the existing code limitations. $\endgroup$ – Has QUIT--Anony-Mousse Dec 19 '17 at 16:44
  • $\begingroup$ Thank you! Seems this is the best way for me to proceed. $\endgroup$ – Mirit Dec 21 '17 at 8:51

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.