Dendrogram, add colors to groups

[LunaKet]

This issue repeats the the Julia discourse page, to better track it on here. Thank @kescobo for taking an interest in this issue.
https://discourse.julialang.org/t/statsplots-dendrogram-how-to-have-clustered-coloring/50768

The idea is that it would be really great to have "group" functionality inside the dendrogram function, where sections of the dendrogram are different colors. This can be seen in R packages. I'm not clear on how to implement it, but I imagine it would use already-present functionality to identify grouped dendrogram lines. cutree, for instance, could be used.

Ideally, passing a boolean true argument to group would use a "best" number and passing an integer argument would declare how many clusters the user wants. A third argument could also be a manual listing of all the groups (array of arrays.)

[kescobo]

Always takes me a while to find it, because we went in some circles to get this recipe in, but the dendrogram was put into StatsPlots in #152

The Hclust "merge" object is what holds the relevant information for the positioning. It took me a while to understand this (you can see this epic PR thread for more info). The merges are a vector of 2ples, each of which codes for 1 connection. Negative numbers refer to indices of the initial object (leaves), positive numbers refer to dendrogram groups (nodes). So for example, if I have 5 things being clustered

merges = [
    (-1, -3) # this links leaf1 to leaf3, with leaf1 on the left. This is node1
    (-4, 1) # this links leaf4 to the left of node1. This is node2
    (-5, -2) # this links leaf5 to the left of leaf2. This is node3
    (2, 3) # this links node2 to node3. This is node4
]

Hclust also stores an order vector. In this case, it would be [4, 1, 3, 5, 2]

The way the recipe works is based on this function, to draw one merge at a time. The order vector gives the x positions of the leaves, and then the merges are drawn, storing the x and y positions of nodes as they're created. If useheights=true in the recipe, then that information is taken from the heights object, but let's ignore that for a moment, and just assume that the height is always 1:

1. We draw the line for node1, using the following 4 points ((x,y): [(2, 0), (2, 1), (3, 1), (3, 0)]
2. We store 1 as the ypos for node1, and 2.5 (half way between 2 and 3) as the xpos
3. We draw the line for node2, which connect leaf4 to node1: [(1, 0), (1, 2), (2.5, 2), (2.5, 1)]
4. We store 2 as the ypos for node2, and 1.75 as the xpos

etc.

So, to add colors using the groups keyword, which I agree would be the best user experience, we'd have to somehow track which leaves are connected through which merges, and then maybe throw an error if the groupings don't work. For example, in this case, let's say leaves [1, 3, 4] are in the blue group, and [5, 2] are in red group. We'd want to note that nodes [1, 2] are blue, node [3] is red, and node [4] is black.

But the plotting will often not be ordered by groups. If instead we had

merges = [(-1, -3), (-5, -2), (-4, 1), (3, 2)]
order = [4, 1, 3, 5, 2]

Then we'd have to plot a blue line, then a red line, then another blue line, then the black line. In addition, if someone claims that one group contains [1, 3, 5] and the other contains [2, 4], this would break the scheme.

@alailink unfortunately, I don't think I have time to work on an implementation, but I'd be happy to help shepherd a PR from you (or anyone else interested) if you want to try to tackle it. Hopefully, this explanation is enough to get you started. @mkborregaard we may need your help too, as I remember getting pretty twisted up trying to understand exactly how grouping works. IIRC, it may not even be possible to use that without an overhaul of the recipe, since it expects all members of a group to be plotted at the same time, right?

[LunaKet]

This is a really incredible description of how merges in general works. I thought I understood it, but this makes it much clearer what is being stored.

I would like to tackle this! I also have limited time (like us all) so it might take me weeks/months to get something workable, if you can keep track of it that long. I've never collaborated on something at this scale, though. So a few questions:

1. Using git terms, are the first few steps pulling the appropriate libraries and making my own branch? And once I have something workable push it back?

2. if I understand multiple dispatch correctly, if the group command doesn't do what I want, I can create a different call by passing in a different datatype, in this case something related to our hclust merges. Thus, if I can't get the native group function to work, I can dispatch to another functionality (which I will have to write). But maybe that's what you meant by 'overhaul'.

3a) The way that you describe merge makes me think that maybe the solution really is to edit the group command so that it doesn't graph everything together, but in the same order as the merges. This also presupposes that a clustering algorithm has already been used to appropriately group them. So I might also need to develop a clever way to check for compatible input.

3b) Another possible route is to reorder the merge data so that it is pregrouped before plotting. I still feel like it would require me to rewrite functionality for the group command, though.

[kescobo]

I would like to tackle this

Great! I'm happy to help however I can.

Using git terms, are the first few steps pulling the appropriate libraries and making my own branch? And once I have something workable push it back?

Typically, the first thing you do is "fork". This is a GitHub term rather than a git one, but it essentially means you clone the repo to your own account. This way you can push stuff with abandon without getting write permissions to the main one.
You should then "clone" the repo from your account to your local machine. There are now 3 repositories that concern you

1. Your local repo: this is where you'll be editing files.
2. The "remote" linked with your account, conventionally called "origin."
3. This repo, which is another "remote," conventionally called "upstream."

You can now check out a new branch on your local and start committing changes. No need to wait until you have something workable - as soon as you've made a commit, do git push -u origin ${branchname}.

Then, when you come back to GitHub, you'll see a helpful little banner asking you if you want to make a pull request. Go ahead and do it, giving it a title like "[WIP] group colors for hclust Plots" (WIP means work in progress), tag me and this issue, and you're off to the races! You keep pushing to your remote / branch, but it will be tracked on a PR here. Then I and others can review the code and answer questions as they arise.

if I understand multiple dispatch correctly, if the group command doesn't do what I want, I can create a different call by passing in a different datatype, in this case something related to our hclust merges. Thus, if I can't get the native group function to work, I can dispatch to another functionality (which I will have to write). But maybe that's what you meant by 'overhaul'.

It's a bit more complicated in this case, for a number of reasons I'm not totally competent to explain. But basically, what we're doing here is writing a recipe, which composes a bunch of stuff, and then passes that data the a separate plotting function that takes all of that info. In this case, the Hclust object passed as the first argument is already dispatching to a separate method. In principle, we could add other types to dispatch on (though keyword types aren't used in dispatch), but this doesn't actually help us unless we want to re-write the underlying plot function. I really don't think we do, as that has enormous and ecosystem-wide consequences.

The way that you describe merge makes me think that maybe the solution really is to edit the group command so that it doesn't graph everything together, but in the same order as the merges.

I think this is close - I don't think we should edit the group command, but we should alter the order that the lines are stored, so that group can work as expected.. At the moment, the individual lines are ordered as I described above, but as there isn't any overlap, changing that order after the fact shouldn't cause problems.

So effectively, I think you'll just need to change treepositions to take a group keyword that alters the order of the resulting matrix if passed.

Get a PR started, poke around at some things, and we can continue the discussion there. Good luck! This will be great fun.

it might take me weeks/months to get something workable, if you can keep track of it that long

This is totally understandable - and I might not be able to keep track of it that long (I have a toddler at home 👶 ), but it's perfectly reasonable to ping me every week or two if I fall off the map. I will do my best to stay on top of it though.