Improve memory-efficiency of clustering algorithm in AttractorsViaFeaturizing

[KalelR]

Hey

The current way that the features in AttractorsViaFeaturizing are clustered can use a lot of memory. Just as a reminder, if we want to calculate 2d basins of attraction with side length L, we would

1. integrate the L^2 initial conditions on the grid
2. extract their features, leading to num_features = L^2 features
3. apply the dbscan clustering algorithm, which requires a pairwise distance matrix which is thus of size num_features^2 = L^4. As you see, this explodes even with relatively-course grids - I was already having trouble with L ~ 200. Clustering.jl offers another way to use dbscan which doesn't apparently use the full pairwise matrix, and so should use less memory. I've been trying this and getting some really weird and hard-to-debug memory errors, which I guess stem from an allocation of a large array somewhere.

It would be nice anyway in the future for us to try other clustering methods. But I need these basins quickly for a project, so I've done the following:

1. reduce (by a lot) the number of features to be clustered by doing a first, rough "clustering". This involves rounding the values in each feature to a certain decimal number, and then getting the unique (rounded) features. This is of course not perfect, as there will be repeated some features that differ slightly, but already reduces the dimensionality from L^2 to ~number of attractors.
2. apply dbscan to this reduced list of features, obtaining now the unique (clustered) features, that correspond to the attractors.
3. use these attractors as templates and map all the unrounded features to them using the nearest-neighbors algorithm. This gets us the labels of all the features.

function _cluster_features_into_labels_large(features, config, ϵ_optimal; par_weight::Real = 0, plength::Int = 1, spp::Int = 1)
    ufeats = unique(map(feature->round.(feature, sigdigits=2), features))
    distances = Attractors._distance_matrix(ufeats, config; par_weight, plength, spp)
    dbscanresult = Attractors.dbscan(distances, ϵ_optimal; min_neighbors=config.min_neighbors, metric=nothing)
    cluster_labels_reduced = Attractors.cluster_assignment(dbscanresult)
    ulabels = unique(cluster_labels_reduced)
    templates = ufeats[ulabels]

    templates_mat = reduce(hcat, templates)
    kdtree = Attractors.KDTree(templates_mat) #each pt is a column in the mat
    features_mat = reduce(hcat, features)
    cluster_labels, dists = Attractors.knn(kdtree, features_mat, 1)
    cluster_labels = [lab[1] for lab in cluster_labels]
    return cluster_labels
end

It has worked great in the example I tried here: firstly, it runs (haha), uses a lot less memory and is much faster (no need to compute L^4 distances!). I'm not sure how this would behave in general though. Happy to discuss this, and later do a pull request if you think it's a good idea.

PS: sorry for posting so many issues and not solving them, I'm quite busy with a few projects now. Will try to complete the other issues as soon as I can!

[Datseris]

This is a good idea. We should do this. We have the max_used_features but this is only for the optimal radius. I think your option is very nice and probably even better.