Develop spectral clustering / embedding methods with dask arrays

[PeterDSteinberg]

The objective is to develop at least four spectral clustering / embedding methods using pysptools as an rough prototype, converting the numpy data structures in that library for medium sized datasets to Dask data structures for large data parallelism. These were the four we mentioned in the proposal (not necessarily limiting our scope here):

• Automatic Target Generation Process (ATGP)
• Fast Iterative Pixel Purity Index (FIPPI)
• N-FINDR
• Pixel Purity Index (PPI)

[PeterDSteinberg]

Hi @TomAugspurger - We have Phase II funding to develop large matrix spectral clustering / embedding models. Please take a look at the models below and the linked implementations for numpy in pysptools. We need to do the same kind of thing for dask. These four models are listed in the proposal, but feel free to spend some time looking around at other related models in pysptools to see level of effort involved in supporting those. The work can end up in Elm or dask-ml, whichever you feel makes the most sense (for specific NASA funded tasks like this one we should make an Elm issue and its fine if the Elm issue gets solved by changes in another repo, e.g. dask-ml or xarray).

Completing this issue:

• [ ] Implement each these with dask in place of numpy:
  • [ ] Automatic Target Generation Process (ATGP)
  • [ ] Fast Iterative Pixel Purity Index (FIPPI)
  • [ ] N-FINDR
  • [ ] Pixel Purity Index (PPI)
• [ ] Make a notebook demonstrating the different methods

[TomAugspurger]

@PeterDSteinberg Do you know what the interest in approximate algorithms is, relative to exact solutions? https://www.csie.ntu.edu.tw/~cjlin/papers/psc08.pdf suggests that "traditional" spectral clustering algorithms don't scale very well, O(N^3) apparently?

I'll keep reading around to see what others have done.

[PeterDSteinberg]

Hi @TomAugspurger - Great paper - thanks for sharing.

I think that "traditional" spectral clustering algos are O(N^3) because the similarity matrix is calculation assumed to be O(N^2) and then an O(N^1) operation on top of that. Same thing can be said if you solve K-Means exactly with a dense full distance matrix (O^3) rather than through iterative recalculation of cluster means as an approximation (O^1 k number of iterations, I think). Anything that requires an exact dense distance/similarity matrix is going to be at least O(N^2).

Here are some ideas for simplifying the similarity matrix and order of the algo:

• Let's start the large matrix spectral clustering algos by assuming we have a tall thin matrix. Many problems in satellite imagery / climate ML can be as small as 8 to 20 columns (e.g. clustering with multispectral imagery or larger input matrices that we run through a dimensionality reduction transform first). Of course it would be nice to support up to the 100s of columns for hyperspectral problems / climate reanalysis, but let's do our initial testing on the tens of columns size.
• Note in that paper you linked, @TomAugspurger, the similarity matrix uses a exponential decay and divisor scaling parameter. Can we set the scaling parameter in a way that makes the problem effectively sparse? (Same idea as doing Euclidean distance while rounding off to zero any distances that are smaller than a threshold).
• Assume number of clusters in spectral clustering is around 5 to 20, if that helps. I'm still thinking through how number of clusters affects order of runtime.

The specs above relate to the usage of spectral clustering in climate / satellite imagery analysis - not sure about how these algos are used in other disciplines.

[RichardScottOZ]

Did anyone invent anything here:- re: pysptools?

[jbednar]

This was implemented in dask-ml; see example at https://examples.pyviz.org/landsat_clustering/landuse_clustering.html

[RichardScottOZ]

This was implemented in dask-ml; see example at https://examples.pyviz.org/landsat_clustering/landuse_clustering.html

Thanks! Trick now being the endmember part.