next up previous
Next: Bibliography Up: 3 Algorithms Implemented Previous: 3.4 TB (-MEDOIDS)

3.5 ECH (Delaunay variant of TB)

The ECH clustering algorithm implements the variant of the TB heuristic, which is described in [1]. It uses the Delaunay triangulation of the dataset to find an efficient approximation to the quantity which TB minimizes.

It runs in \( O(n\log n) \) time, and gives clusterings of approximately the same quality as the TB heuristic. Further, it does not need to be given any value for \( k\) -- it will ignore any value which is given on the command line, and instead find the most appropriate value of \( k\) from the data itself.

Unfortunately, due to the complicated nature of the algorithm, time constraints have prevented our implementation of the ECH algorithm from being completed. Whilst it has been fully implemented, when its output is viewed it is clear that it is flawed in some way.

Kevin Pulo