scikit-learn/scikit-learn — pull request #1185 by magsol (2012-09-27 18:38:09+00:00)
Title: Fergus semi-supervised label propagation

This is a new semi-supervised algorithm based on Fergus et al 2009 [1].

Strengths:
* Closed-form solution, no need for iterations or convergence threshold
* Similar accuracy as other sklearn semi-supervised algorithms with moons data, much better accuracy than other algorithms with concentric circles
* In addition to 'knn' and 'rbf' modes, has an 'img' mode for segmenting images

Weaknesses:
* Full order of magnitude slower than other sklearn algorithms, likely due to eigh() on the graph laplacian (somewhat mitigated by use of sparse data structures)
* Eigen-decomposition precludes full integration with existing semi-supervised class structure
* Method for computing image affinities (img_rbf_kernel) is inefficient and could use some optimization

I would love to add this algorithm to scikit-learn's semi-supervised package. I'm definitely open to suggestions for improving it and bringing it up to par with scikit-learn's coding standards and algorithm performance.

[1] Rob Fergus et al. Semi-supervised learning in gigantic image collections, 2009.