Implement hierarchical clustering

[Mec-iS]

Motivation: why do we need hierarchical when we have already kmeans?

Vocabulary:

• divisive clustering: ...
• agglomerative clustering: average, weighted, median, centroid, Ward

Sub-tasks:

• pick one or a minimal set of metrics-distances
• pick one or a minimal set of linkage strategies
• pick one or more algorithms (SLINK for single-linkage and CLINK for complete-linkage clustering)

Visualisations: (?)

Other implementations:

• hierarchical clustering in SciPy
• hierarchical clustering in sklearn

[VolodymyrOrlov]

@Mec-iS Take a look at this paper that describes a FastPair algorithm. This algorithm helps to speedup cluster merge operation. Also I suggest to take a look at fastcluster implementation of the HC described in this paper. Figures at the bottom of this page show very well the difference between fastcluster and other implementations. Unfortunately it is written in C++.

[Mec-iS]

Notes

FastPair

• a Python implementation for FastPair
• Closest neighbour on Rosetta Stone, see the usage of complex numbers (for 2D points) to reduce distance to absolute value of difference (d = abs(P1-P2))
• Closest neighbout using randomness: Rabin’s Algorithm

fastcluster:

• Direct link to download the Paper with extensive explanation of the procedure
• Python interface for version 1.1.11 (from 2013), current version is 1.1.26 (December 2019) with a C++ and a CPython version

Alternatives:

1. translate from the Python interface in Rust, then hunt for changes/improvements in the C++ version
2. FFI to call C++ from Rust, in particular using rustcxx

Background questions:

• are we going for a 100% Rust native implementation?
• are we supposed to allow or not usages of unsafe blocks?

[VolodymyrOrlov]

Background questions:

• are we going for a 100% Rust native implementation?
• are we supposed to allow or not usages of unsafe blocks?

Yes, calling C++ library from SmartCore is not an option for multiple reasons. We'll have to ship fastcluster with SmartCore somehow and it diminishes usefulness of our library.

Do you know C++ by any chance? 😄 If not, feel free to go with any implementation, even if it is not the fastest out there. Another option would be to try to implement the algorithm (it is described here) yourself. It would be super awesome if you can implement fastcluster in Rust, because in this case we will be the only library in Rust that has it.

[Mec-iS]

what role you had in mind for FastPair?

[VolodymyrOrlov]

what role you had in mind for FastPair?

As an alternative to fastcluster

[Mec-iS]

FastPair is implemented #142

We can move on to implement clustering; starting with AgglomerativeClustering

Tasks:

1. do parameters parsing as in _fit()(we need only some of the required parameters)
2. implement ward_tree
3. return _labels

Basic linkage is Ward (that needs euclidean distance).