1
$\begingroup$

I am using scikit-learn's AgglomerativeClustering on a large data set.

I would like to modify the distance_threshold after the model has already been computed. Computing the model is slow (quadratic time), but it should easily be possible to re-compute the labels for a new distance_threshold in linear time because the model stores the children_ and distances_ arrays permanently. But how can the labels be re-computed for a different distance_threshold?

It can be assumed that distance_threshold was originally set to 0, i.e. the entire tree was computed.

$\endgroup$
0
+100
$\begingroup$

One option to speedup computation with different thresholds is caching the results using the memory option.

Something like this:

from sklearn.cluster import AgglomerativeClustering

clustering = AgglomerativeClustering(compute_full_tree=True,
                                     distance_threshold=1.0,
                                     memory='mycachedir', 
                                     n_clusters=None,)
$\endgroup$
2
  • $\begingroup$ Thank you. This certainly is a lot better than re-computing it entirely. But is there a way that does not require loading the entire input data into memory again? I intend to perform the initial computation on a supercomputer with a lot of RAM and then continue working on the data on a regular PC that doesn't have anywhere near enough RAM to store the input data. This way, I'd still have to keep the input data (along with the cache) on the supercomputer and then re-compute the labels there. $\endgroup$
    – UTF-8
    Mar 3 at 21:02
  • $\begingroup$ There are many ways to approach that problems. One way is to use Dask-ML to work with arrays that are larger than the current machine's memory. $\endgroup$ Mar 3 at 22:00
0
$\begingroup$

You may calculate the new label using children_ and distances_ recursively and following the below definition from scikit-learn document.

children_array-like of shape (n_samples-1, 2)
The children of each non-leaf node. Values less than n_samples correspond to leaves of the tree which are the original samples. A node i greater than or equal to n_samples is a non-leaf node and has children children_[i - n_samples]. Alternatively at the i-th iteration, children[i][0] and children[i][1] are merged to form node n_samples + I
distances_array-like of shape (n_nodes-1,)
Distances between nodes in the corresponding place in children_. Only computed if distance_threshold is used or compute_distances is set to True.

from sklearn.cluster import AgglomerativeClustering
from sklearn import datasets
iris = datasets.load_iris()
x, y = iris.data, iris.target

ac = AgglomerativeClustering(n_clusters=None, affinity='euclidean', linkage='complete', compute_full_tree=True, distance_threshold=0, )
labels = ac.fit_predict(x)

children = ac.children_
distances = ac.distances_
thres = 1.5
n_samples = 150

def get_branch(label):  # Return the "children" Index based on Node
    for idx,child in enumerate(children):
        if label in child:
            return idx

def new_label(label):

    branch = get_branch(label)
    distance = distances[branch]
    while distance < thres:
        parent = branch + n_samples   # As per doc, It's the Parent's Node
        branch = get_branch(parent)   # Get the Index of Parent
        distance = distances[branch]  # Get the Distance of the elements in the Index 

    return label if not parent else parent
    
new_label(100)
$\endgroup$
4
  • $\begingroup$ I'm not sure how to use this. I'd think that if I use the same threshold in the original model parameterization (line 6) as is used later on for variable thres, I'd get the same result as previously. However, if I choose 1.5 for both thresholds, print(ac.labels_[100]) prints 5 whereas print(new_label(100)) prints 284. I tried making sense of how to use this on a tiny sample size of 10 but can't understand it. What do I feed into new_label()? $\endgroup$
    – UTF-8
    Mar 9 at 13:47
  • $\begingroup$ The model is built on distance_threshold=0, so it will have a Cluster for each element. The new_label() will take the ClusterId/Prediction for any data and the new Threshold should be passed into thres variable. It will return the ParentNode collapsing it back till the new distance is less than the Threshold $\endgroup$
    – 10xAI
    Mar 9 at 14:52
  • $\begingroup$ I didn't realize that setting distance_threshold to 0 was integral. But even with it set to 0, I don't get results that look plausible. I still get 284 for print(new_label(100)), even with distance_threshold set to 0. I'd expect it to be 5, assuming they clusters are labeled the same way. But even if they are not, there are unexpected things happening: An error is thrown on new_label(0) or when choosing a low value for thres. $\endgroup$
    – UTF-8
    Mar 9 at 15:52
  • $\begingroup$ I tried running this on 10 samples (of my actual problem) that should have labels [2 0 0 0 0 1 1 1 1 0] for distance_threshold = 1. When I set distance_threshold = 0 and run your code, I get an error for 0, followed by: [16, 16, 16, 16, 15, 15, 15, 15, 16] Is there just an error for 0? Because then the results would be isomorphic (for 0 → 16, 1 → 15). $\endgroup$
    – UTF-8
    Mar 9 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.