title: Understanding DynamicTreeCut algorithm for cutting a dendrogram
body: <p>A dendrogram is a data structure used with hierarchical clustering algorithms that groups clusters at different "heights" of a tree - where the heights correspond to distance measures between clusters.</p>
  
  <p>After a dendrogram is created from some input data set, it's often a further challenge to figure out where to "cut" the dendrogram, meaning selecting a height such that only clusters below that height are considered meaningful. </p>
  
  <p>It's not always clear at what height to cut a dendrogram, but some algorithms exist, such as the <strong><a href="https://labs.genetics.ucla.edu/horvath/htdocs/CoexpressionNetwork/BranchCutting/Supplement.pdf" rel="nofollow noreferrer">DynamicTreeCut</a></strong> algorithm, that attempt to programatically select meaningful clusters from the dendrogram.</p>
  
  <p>See:</p>
  
  <p><a href="https://stats.stackexchange.com/questions/3685/where-to-cut-a-dendrogram">https://stats.stackexchange.com/questions/3685/where-to-cut-a-dendrogram</a></p>
  
  <p><a href="https://stackoverflow.com/questions/22317813/cutting-dendrogram-at-highest-level-of-purity">Cutting dendrogram at highest level of purity</a></p>
  
  <p>So I've been reading over the <strong><a href="https://labs.genetics.ucla.edu/horvath/htdocs/CoexpressionNetwork/BranchCutting/Supplement.pdf" rel="nofollow noreferrer">DynamicTreeCut</a></strong> algorithm, as well as a <a href="http://www.bioinformatics.org/cgi-bin/viewvc.cgi/catch/branches/CATCH%203/trunk/CATCH%203/controllers/treeCut/DynamicTreeCut.java?revision=485&amp;view=markup&amp;pathrev=485" rel="nofollow noreferrer"><strong>Java implementation</strong></a> of the algorithm.  I understand how the algorithm works and what it's doing, in terms of a step by step breakdown of what's going on. However, I am failing to understand <em>how</em> this algorithm is doing anything meaningful.  I think I am missing some key concept here.</p>
  
  <p>In general, the algorithm iterates over a "height sequence" from a dendrogram.  I'm not certain, but I assume that a "height sequence" just means the values along the Y axis of a dendrogram, i.e. the various heights at which cluster joins occur.  If that's the case, we can assume that a "height sequence" is sorted in <em>ascending order</em>.</p>
  
  <p>Then the algorithm calls for taking a "reference height", <code>l</code>, and subtracting it from each height in the input "height sequence".  This gives you a vector of differences (<code>D</code>) between each height <code>h[i]</code> in the height sequence and the reference height <code>l</code>. </p>
  
  <p>Then the algorithm attempts to find "transition points" - which are points in the differences vector where <code>D[i] &gt; 0</code> and <code>D[i+1] &lt; 0</code>.  In other words, points in the differences vector where the difference value transitioned from being positive to being negative.</p>
  
  <p>And right here I am totally lost.  I don't understand how these transition points can ever be meaningful.  Firstly, it's my understanding that the input height sequence <code>H</code> is just the values on the Y axis of the dendrogram.  So therefore the height sequence <code>H</code> should be in <em>ascending order</em>.  Therefore, how can there ever be a point in the differences vector where we transition from <em>positive</em> to <em>negative</em>?</p>
  
  <p><strong>For example:</strong></p>
  
  <p>Suppose our input height sequence H is <code>{1, 1.5, 2, 2.5, 3, 7, 9}</code> and our reference value <code>l</code> is the average height (which would be <code>3.7</code>).  So if we create a difference vector <code>D</code> by subtracting <code>l</code> from each height in <code>H</code>, we'd get <code>{-2.7, -2.2, -1.7, -1.2, -0.7, 3.3, 5.3}</code>.  So clearly there is no transition point here, nor could there ever be, because there are no points in the difference vector where <code>D[i] &gt; 0</code> and <code>D[i+1] &lt; 0</code>, since the height sequence <code>H</code> is in <em>ascending order</em>.</p>
  
  <p>So clearly I am totally misunderstanding something fundamental about this algorithm.  Perhaps I am not understanding what is meant by the "height sequence".  I am assuming it is simply the values on the Y-axis from the dendrogram, but clearly that doesn't make any sense with regard to what the algorithm is actually doing.  Unfortunately, the authors don't really explain what is meant by a "dendrogram height sequence", nor does it appear to be some kind of standard terminology in use by the data science community.</p>
  
  <p>So can something explain what the DynamicTreeCut algorithm is trying to achieve here, and where my understanding is going wrong?</p>