support for new metrics is low priority. The idea of sum of squares as sufficient stats is designed for euclidean norm.

support for sparse matrices should be straightforward. I don't see why it would not work.

OVerall, I am impressed that you managed to put this together that fast.
This is great, and this is absolutely going in the right direction.
Congratulation!

Making it fast will probably require porting part of the code to Cython.
To probably calls for profiling before starting this endeavour.

Thanks. It is always nice to be appreciated.

As a general comment, before going low level to speed things up, I think that it would help having a high-level reflection on the structure of the code:

There are two classes. Can these 2 classes be collapsed into one? Less levels of indirection make it easier to profile and optimize. It also makes simpler Cython code.

What is the best way to store the data structures? We have here lists of objects, that have attributes that store the interesting information. Can we have lists / arrays of these interesting info? (unlikely, but worth thinking).

To think about that, I would make a diagram with all the data-structures layed out, and what they contribute to the algorithm.

1. Yes, partial_fit (or partial_fit_predict?) support would be wonderful, but I'm not sure that the current solution of storing labels for every training instance makes sense in a large-scale clustering approach. A fit-predict paradigm could make more sense, or could be provided as an option (and this means you don't need to track sample_indices_, but have an additional O(nlogn) predict time.
2. The paper describes a global clustering step in which an arbitrary clustering algorithm is applied to the identified subclusters. It seems this is not presently included. Is it possible to provide a meta-estimator or some other kind of data reduction transformation that allows subcluster centroids to then be clustered and those global-cluster labels returned from predict for the subcluster nearest each sample? (Note also that BIRCH is coming very close to some of the instance reduction techniques that have been mooted on the ML.)
3. Does adding __slots__ to every CFNode/CFSubcluster improve its profile?
4. I have thought about how to represent this, and it is not really very numpy friendly, in that I don't see a clean way for arrays to be used to represent the node space. Without tracking sample_indices_ (as above), it may be possible to have CFNode.subcluters_ as an array and hence vectorize the update step.

@jnothman @agramfort Thanks for all your comments. I shall give detailed response tomorrow.

I am responding to @jnothman 's major comment (and in a way to @GaelVaroquaux 's too) .

Yes, I did not include the global clustering step, in which the leaf sub-clusters are grouped back (according to an arbitrary clustering algorithm). In that way

1. In the fit method we can build the tree (and the global clusters) and in the predict method we can map the samples to the respective closest global clusters.
2. Do away with the tracking of sample_indices_ and collapse CFSubluster to 3 separate arrays
3. It also gives more sense to a partial_fit method.

However I am not sure how are we to accommodate this in the public API. Or do we just allow the user to give an option to set n_clustersand hardcode the final global clustering ourselves?

And I think, if we need to just euclidean metrics for now (according to @agramfort 's comment) , we can also do away with computing ss

EDIT:
It should not be too much work in any case, I can work that out once we come to a conclusion on how to handle the global clustering step.

@jnothman I have added the global clustering step, IRL me and @agramfort discussed about the global clustering step, right now we have hardcoded it and allowing the user to provide n_clusters. If n_clusters is None then we skip the global clustering step.
I have also put a partial_fit method to avoid the rebuilding of the CF Tree and inherited from Cluster Mixin for the fit_predict method.

it may be possible to have CFNode.subcluters_ as an array

I would like it to stay as it is because of the child_ param. IMO, it is now more readable.

Sounds good. I'll look through this later. Is it worth adding the option that n_clusters=arbitrary_clusterer?

We had thought about it, but then how do you account for the parameters of the arbitrary_clusterer?

Sounds good. I'll look through this later. Is it worth adding the option that
n_clusters=arbitrary_clusterer?

👍 good idea.

We had thought about it, but then how do you account for the parameters of the
arbitrary_clusterer?

You give an instance, not an object.

You give an instance, not an object.

I see, so I guess we are in the make it fast stage? ;)

I see, so I guess we are in the make it fast stage? ;)

No. This is good design (I meant a "not a class", by the way, in my
previous post).

Yes of course, I was asking if the next step would be to profile the code, after I make that change.

We need some work to speed it up, This example takes 1.24s with n_clusters=3 as compared to 0.02s with MiniBatchKMeans .

Though it is much faster than AgglomerativeClustering with the default parameters (which takes 6s) @GaelVaroquaux Is this expected?

yes. AgglomerativeClustering is quadratic in sample size (unless you use
connectivity)

@jnothman

Yes, the fact of setting threshold to zero initially, and then building a new tree based on the subclusters read from the leaves, and fitting a new tree using these subclusters as new samples (when a memory limit is set by the user), is interesting but I'm not sure how useful or practical this would be, but yes it might be worth a go later on.

Is there any literature on automatically setting the threshold?

Do you mean initially or when memory runs out. If you mean initially then we come back to Gael's comments about taking a small sample of the data, find the pairwise distances under a quantile percent. If you mean when the memory runs out, there are a number of heuristics in page 7 of the paper that sets a new threshold, based on seen data, radius of the subclusters in the tree and so on,

Sorry, it's a fairly full week

All right, thanks!

Once those minor things are addressed, I expect this will have my +1.

@jnothman I have addressed all your comments in the last commit, I have also added your name in the author's file, for your help in reviewing this

It was a problem with random_state, I moved the test to common_tests

@jnothman I can haz merge?

I think so! Well done!

Congrats !

@jnothman @agramfort Thanks for bearing with my impatience. Now is just the simple matter of rewriting it in Cython!

Now is just the simple matter of rewriting it in Cython!

Lol. No, the tricky part is writing as little of it as possible in Python
while keeping it clean and fast.

On 12 December 2014 at 09:11, Alexandre Gramfort notifications@github.com
wrote:

Congrats !

—
Reply to this email directly or view it on GitHub
#3802 (comment)
.

Congrats !

Hurray!