<p>Vijaya, from what I know, there is only one public library that does order preserving hierarchical clustering (<a href="https://bitbucket.org/Bakkelund/ophac/wiki/Home" rel="nofollow noreferrer">ophac</a>), but that will only return a trivial hierarchy if your data is totally ordered (which is the case with the sections of a book).</p>
<p>There is a theory that may offer a theoretical reply to your answer, but no industry-strength algorithms currently exist: <a href="https://arxiv.org/abs/2109.04266" rel="nofollow noreferrer">https://arxiv.org/abs/2109.04266</a>. I have an implementation of this theory that can deal with up to 20 elements, so if this is interesting, give me a hint, and I will share the code.</p>
Order Preserving Hierarchical Agglomerative Clustering - Python
<p>Is there any Hierarchical Agglomerative Clustering implementation (in Python) available that preserves the order of data points? For example, I want the output something like this.</p>
<pre><code>(((seg1, seg2), (seg3, seg4)), seg5)
</code></pre>
<p>but not like this</p>
<pre><code>(((seg1, seg5), (seg2, seg3)), seg4)
</code></pre>
<p>E.g., <strong>Actual output</strong> with existing implementation
<a href="https://i.stack.imgur.com/gvVpO.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/gvVpO.png" alt="Actual Output with existing implementation" /></a></p>
<p><strong>Expected output</strong> (any implementation?)
<a href="https://i.stack.imgur.com/dE2so.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/dE2so.png" alt="enter image description here" /></a></p>