Hello everyone, A quick question: why not use Nystrom instead?
The effects of thresholding the kernel matrix is not very well understood and makes you lose the positive-definiteness (i.e. it's not a kernel matrix anymore). It's ok for spectral clustering as the Laplacian is always positive semi-definite and this is used for Ncut image segmentation. But for most other kernel-based methods (e.g. SVM) working with indefinite "kernel" matrices is a risky business... So, if I correctly understood what this thread is about, my remark is the following: 1) either you have one particular use case in mind, image segmentation with spectral clustering, in which case a simple solution exists: compute the kernel values only for neighboring pixels 2) or you want something more generic: Nystrom As the discussion on this topic is active and the solutions proposed seemed to require a little bit of effort, maybe it's worth dedicating it to implementing Nystrom instead? It is fairly easy and could be of general interest, imho. If you decide to go that way, I might even be able to provide some help as I already implemented this myself (based on Jitendra Malik's PAMI paper [1]). Cheers, Adrien [1] Spectral grouping using the Nystrom method, Fowlkes, C. and Belongie, S. and Chung, F. and Malik, J. PAMI 2004 Le 23/01/2012 10:20, Mathieu Blondel a écrit : > On Mon, Jan 23, 2012 at 6:06 PM, Andreas<[email protected]> wrote: > >> It might be as easy as that. >> I guess I should try to see if this speeds up things. > If you use algorithm="brute", there should be no speed-up (it computes > all the distances and find those within the given radius...). If you > use ball-tree, it should improve on low-dimensional data, make things > worse otherwise. > Question: can the triangle inequality tricks frequently used in > K-means be used for this kind of radius search too? One could sample a > few training points from the datasets and use them as "pivots". > > Mathieu > > ------------------------------------------------------------------------------ > Try before you buy = See our experts in action! > The most comprehensive online learning library for Microsoft developers > is just $99.99! Visual Studio, SharePoint, SQL - plus HTML5, CSS3, MVC3, > Metro Style Apps, more. Free future releases when you subscribe now! > http://p.sf.net/sfu/learndevnow-dev2 > _______________________________________________ > Scikit-learn-general mailing list > [email protected] > https://lists.sourceforge.net/lists/listinfo/scikit-learn-general ------------------------------------------------------------------------------ Try before you buy = See our experts in action! The most comprehensive online learning library for Microsoft developers is just $99.99! Visual Studio, SharePoint, SQL - plus HTML5, CSS3, MVC3, Metro Style Apps, more. Free future releases when you subscribe now! http://p.sf.net/sfu/learndevnow-dev2 _______________________________________________ Scikit-learn-general mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
