# Speeding up findmin for a matrix for hierarchical clustering

**URL:** <https://discourse.julialang.org/t/speeding-up-findmin-for-a-matrix-for-hierarchical-clustering/41049>\
**Category:** Machine Learning\
**Created:** [June 9, 2020, 8:40am UTC](https://discourse.julialang.org/t/speeding-up-findmin-for-a-matrix-for-hierarchical-clustering/41049 "2020-06-09T08:40:09Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [June 9, 2020, 8:40am UTC](https://discourse.julialang.org/t/speeding-up-findmin-for-a-matrix-for-hierarchical-clustering/41049/1 "2020-06-09T08:40:09Z")

</div>

I’ve written a hierarchical clustering algorithm and I would like to speed it up if possible. It seems that my limiting step is `findmax(D)` where `D` is my dissimilarity matrix. This is a `LowerTriangular` matrix (since the order of the pairs doesn’t matter, i.e. `D[i,j] == D[j,i]`.

I was thinking it might help to convert this into a Vector, sort it and then do `findmax`. However, two issues:

1. How do I get back to my matrix from the vector?
2. I update `D` after each cluster merge. How can I insert the new dissimilarity values into the sorted vector representation of `D` in an efficient way?

Any thoughts would be very much welcome!

PS I know there is a clustering package for Julia, but I opted to write my own because I also need to implement a particular type of hierarchical clustering where you can only merge adjacent clusters. It seemed a bit too involved to do this by extending the clustering package.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [June 9, 2020, 10:31am UTC](https://discourse.julialang.org/t/speeding-up-findmin-for-a-matrix-for-hierarchical-clustering/41049/2 "2020-06-09T10:31:19Z")

</div>

> [@gobs](#):
>
> I was thinking it might help to convert this into a Vector, sort it and then do `findmax`

Sorting is O(n \log(n)) whereas `findmax` is O(n) , so I doubt that’ll be any faster.

You may want to have a look at [heaps](https://juliacollections.github.io/DataStructures.jl/latest/heaps/) if you want a datastructure that maintains easy access to an extreme value.

---

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [June 9, 2020, 12:15pm UTC](https://discourse.julialang.org/t/speeding-up-findmin-for-a-matrix-for-hierarchical-clustering/41049/3 "2020-06-09T12:15:46Z")

</div>

Hmmm, good point. I’ll try and rewrite my code with heaps in that case.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [June 10, 2020, 4:25pm UTC](https://discourse.julialang.org/t/speeding-up-findmin-for-a-matrix-for-hierarchical-clustering/41049/4 "2020-06-10T16:25:35Z")

</div>

> [@gobs](#):
>
> I know there is a clustering package for Julia, but I opted to write my own because I also need to implement a particular type of hierarchical clustering

There’s not just one, there now the awesome new parallel clustering package: [https://github.com/PyDataBlog/ParallelKMeans.jl/blob/master/docs/src/index.md](https://github.com/PyDataBlog/ParallelKMeans.jl/blob/master/docs/src/index.md) that I discovered in the (then latest, June now popped in) Julia newsletter (“‘orders of magnitude’ faster than Python’s scikit-learn, R and Clustering.jl”).

that you could use with hierarchical, but I found something with better time complexity. “Ultrametric [Baire space]” was new to me (and unknown to the professor teaching clustering/data mining; and also “generalized ultrametric [spaces]”).

> **[gfkl-190.pdf](https://www.cs.rhul.ac.uk/home/pedro/papers/gfkl-190.pdf)**
>
> 196.45 KB

> In this work a novel distance called the Baire distance is presented.  
> We show how this distance can be used to generate clusters in a way that is computationally inexpensive when compared with more traditional techniques. This approach therefore makes a good candidate for exploratory data analysis when data sets are very big or in cases where the dimensionality is large

What are you implementing? I see also recent from 2018: [https://arxiv.org/pdf/1806.03432.pdf](https://arxiv.org/pdf/1806.03432.pdf)

This in the package above seemed the best (almost all the algorithms there new to me):

[Yinyang K-Means](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/ding15.pdf)

and also interesting:  
Full Implementation of Triangle inequality based on [Elkan - 2003 Using the Triangle Inequality to Accelerate K-Means"](https://www.aaai.org/Papers/ICML/2003/ICML03-022.pdf).

---

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [June 11, 2020, 8:02am UTC](https://discourse.julialang.org/t/speeding-up-findmin-for-a-matrix-for-hierarchical-clustering/41049/5 "2020-06-11T08:02:25Z")

</div>

Cool! I’m basically implementing the two hierarchical clustering algorithms that you can find here:

[1] S. Pineda and J. M. Morales, “Chronological time-period clustering for optimal capacity expansion planning with storage,” IEEE Trans. Power Syst., vol. 33, no. 6, pp. 7162–7170, 2018.

I’m not sure I want to do anything fancier - the clustering is only a means to an end for me.