Thanks for the PR.
Do we want to / can we guess whether we want to go sparse? It seems like the number of non-zeros or the shape of the matrix might be a good heuristic?

btw, what kind of clustering do you use to get 100k clusters and how many data points do you have? This seems like a rather borderline use-case ^^

We could probably catch a MemoryError in contingency_matrix and call it again with sparse=True ? And generate a warning saying this is happening?
Clustering 10s of millions of proteins (using external tools). Validating clustering using sklearn.

I think catching a memory error is not great, because numpy might segfault instead of throwing a memory error (sometimes?)

Also you might fill the ram, bringing other applications down. So if the contingency_matrix is large and sparse, maybe we don't want to call toarray on it. Then we might be able to keep the interface much simpler.

I think this is the right way to go, and was just about to suggest an issue for it. Unfortunately, in the meantime max_n_classes has been introduced, which I think is the wrong solution; this PR needs a rebase as a result. If I give this PR a review, will you be able to work on it to completion, @stuppie?

@amueller you can get many clusters in something like cross-document coreference resolution; perhaps not 100k, but only an order of magnitude off for current manually annotated datasets.

@jnothman Sorry for the long delay. Yes, I can I can. Are you saying I should remove the max_n_classes code, rebase, and re-submit the pull request?

You don't need to resubmit the pull request, just git push -f your branch back to github.

I'm not sure I'm doing this right. I have merge conflicts in sklearn/metrics/cluster/supervised.py. Do I need to (manually) merge the sparse and max_n_classes changes?

You've somehow reset your branch to master!

Yes, you'll have to manually merge the changes. First you'll have to go back and find your changes!