Mahout
  1. Mahout
  2. MAHOUT-518

Implement Affinity Preprocessing for Eigencuts and Spectral KMeans

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Won't Fix
    • Affects Version/s: 0.4
    • Fix Version/s: 0.6
    • Component/s: Clustering
    • Labels:
      None

      Description

      The input format for these clustering algorithms is currently affinity tuples. It would be very nice to have this process automated. Marking for 0.5 as this will require some investigation.

        Activity

        Hide
        Sean Owen added a comment -

        After 14 months, and some related progress, I think this is as done as it will be.

        Show
        Sean Owen added a comment - After 14 months, and some related progress, I think this is as done as it will be.
        Hide
        Shannon Quinn added a comment -

        I could make a patch that processes a basic CSV file of m n-dimensional points, but I still wouldn't consider this issue closed, as the discussion regarding standardizing the input/output formats for Mahout still seems to be ongoing, and isn't something that will be resolved for 0.5. Once it is resolved, this will likely still have to be modified, so a future version would probably be best.

        Show
        Shannon Quinn added a comment - I could make a patch that processes a basic CSV file of m n-dimensional points, but I still wouldn't consider this issue closed, as the discussion regarding standardizing the input/output formats for Mahout still seems to be ongoing, and isn't something that will be resolved for 0.5. Once it is resolved, this will likely still have to be modified, so a future version would probably be best.
        Hide
        Sean Owen added a comment -

        Same, doesn't look like anything for 0.5 here, so marking for a future version?

        Show
        Sean Owen added a comment - Same, doesn't look like anything for 0.5 here, so marking for a future version?
        Hide
        Jeff Eastman added a comment -

        Sort of. The density estimators both use a set of representative points taken from the clustered points output after clustering. But using a threshold to force large distance measures to product zero affinities - instead of just small affinities - would make the A matrix sparse again and allow subsequent processing to scale better. Even with such a threshold; however, the need to compare each point with every other would make it tricky to do at scale. I can imagine some sort of mapper-side join in a custom InputFormat would be required as in DRM.

        Show
        Jeff Eastman added a comment - Sort of. The density estimators both use a set of representative points taken from the clustered points output after clustering. But using a threshold to force large distance measures to product zero affinities - instead of just small affinities - would make the A matrix sparse again and allow subsequent processing to scale better. Even with such a threshold; however, the need to compare each point with every other would make it tricky to do at scale. I can imagine some sort of mapper-side join in a custom InputFormat would be required as in DRM.
        Hide
        Shannon Quinn added a comment -

        Some of the examples I've seen of generalized spectral clustering use points in two-dimensional space and generate affinities between them. In theory there's no issue with this; the only problem is you can easily imagine situations where the data are non-symmetric (i.e. the KNN of one point has a member which does not contain the original point in its KNN), so yes the only way to guarantee symmetry is to compute the affinity of each point with every other point, and that clearly isn't scalable. A distance threshold would work much better - something more along the lines of density estimation?

        Show
        Shannon Quinn added a comment - Some of the examples I've seen of generalized spectral clustering use points in two-dimensional space and generate affinities between them. In theory there's no issue with this; the only problem is you can easily imagine situations where the data are non-symmetric (i.e. the KNN of one point has a member which does not contain the original point in its KNN), so yes the only way to guarantee symmetry is to compute the affinity of each point with every other point, and that clearly isn't scalable. A distance threshold would work much better - something more along the lines of density estimation?
        Hide
        Jeff Eastman added a comment -

        Mean Shift is used in image processing too, but has shown itself to work pretty well on other vector clustering applications. I wonder if spectral clustering can be also? I see that the affinity preprocessing of n, arbitrary vectors might produce a dense nxn matrix if we used a DistanceMeasure as the affinity measure and this would clearly not scale. There are also scalability problems with needing to compare each point with every other as in Mean Shift. But the addition of a distance threshold, similar to T1 & T2 for Canopy could allow a distance-measure-based preprocessor to produce affinity matrices that were both square and sparse. It might just be GIGO, but it would allow the spectral clustering jobs to consume arbitrary vectors like most of the other clustering jobs.

        Show
        Jeff Eastman added a comment - Mean Shift is used in image processing too, but has shown itself to work pretty well on other vector clustering applications. I wonder if spectral clustering can be also? I see that the affinity preprocessing of n, arbitrary vectors might produce a dense nxn matrix if we used a DistanceMeasure as the affinity measure and this would clearly not scale. There are also scalability problems with needing to compare each point with every other as in Mean Shift. But the addition of a distance threshold, similar to T1 & T2 for Canopy could allow a distance-measure-based preprocessor to produce affinity matrices that were both square and sparse. It might just be GIGO, but it would allow the spectral clustering jobs to consume arbitrary vectors like most of the other clustering jobs.
        Hide
        Shannon Quinn added a comment -

        That's a good point, and these images can always be converted to a friendly format for the example. However, if we want to support raw input we may still have to incorporate raw image preprocessing into Eigencuts, which will likely require JAI. Unless there's an intermediate format we could support instead? I'm totally open to ideas on this one.

        Show
        Shannon Quinn added a comment - That's a good point, and these images can always be converted to a friendly format for the example. However, if we want to support raw input we may still have to incorporate raw image preprocessing into Eigencuts, which will likely require JAI. Unless there's an intermediate format we could support instead? I'm totally open to ideas on this one.
        Hide
        Ted Dunning added a comment -

        Java Advanced Imaging can read PNM formatted images with includes PGM (and PBM and PPM) formatted images.

        See
        http://java.sun.com/products/java-media/jai/iio.html
        and
        http://java.sun.com/javase/technologies/desktop/media/jai/project/index.html
        and
        https://jai-imageio.dev.java.net/

        Sanselan also supports reading images in PGM format.

        I don't know how much we want to add a dependency just for a demo program for eigenCuts.

        Show
        Ted Dunning added a comment - Java Advanced Imaging can read PNM formatted images with includes PGM (and PBM and PPM) formatted images. See http://java.sun.com/products/java-media/jai/iio.html and http://java.sun.com/javase/technologies/desktop/media/jai/project/index.html and https://jai-imageio.dev.java.net/ Sanselan also supports reading images in PGM format. I don't know how much we want to add a dependency just for a demo program for eigenCuts.
        Hide
        Shannon Quinn added a comment -

        This is worth discussion: Eigencuts (and spectral clustering algorithms on a whole) is designed to work specifically on images, but in theory can be used for any general-purpose clustering if the data format is correct. The primary issue here, however, is that the input affinity matrix A currently must be symmetrical (and sparse, but that's the Mahout requirement). The symmetry is easy to do with images: the general rule of thumb is that for each pixel, the neighborhood of affinities consists of the 8 pixels around it, therefore making it both sparse and symmetric. Were these data points to be drawn from arbitrary distributions (say, a bunch of points in Euclidean space), you can picture instances where the neighborhoods of nearest data points aren't symmetric.

        There are optimizations that can be made to convert non-symmetric input data into lower-rank approximations that are fully symmetric, but that's probably something we should tackle later (there's a section on this problem specifically in Dr. Chennubhotla's thesis containing Eigencuts, that's probably a good place to start). My recommendation for this ticket is to allow the algorithm to process raw images; generalized input data (which is not necessarily symmetric) can come later.

        My only point regarding images is that for most academic purposes, this algorithm has used input images in PGM format; problem is, Java doesn't have a native PGM image processor, hence why I'm still tweaking the Eigencuts examples. If anyone knows of something that would help with this, please let me know.

        Show
        Shannon Quinn added a comment - This is worth discussion: Eigencuts (and spectral clustering algorithms on a whole) is designed to work specifically on images, but in theory can be used for any general-purpose clustering if the data format is correct. The primary issue here, however, is that the input affinity matrix A currently must be symmetrical (and sparse, but that's the Mahout requirement). The symmetry is easy to do with images: the general rule of thumb is that for each pixel, the neighborhood of affinities consists of the 8 pixels around it, therefore making it both sparse and symmetric. Were these data points to be drawn from arbitrary distributions (say, a bunch of points in Euclidean space), you can picture instances where the neighborhoods of nearest data points aren't symmetric. There are optimizations that can be made to convert non-symmetric input data into lower-rank approximations that are fully symmetric, but that's probably something we should tackle later (there's a section on this problem specifically in Dr. Chennubhotla's thesis containing Eigencuts, that's probably a good place to start). My recommendation for this ticket is to allow the algorithm to process raw images; generalized input data (which is not necessarily symmetric) can come later. My only point regarding images is that for most academic purposes, this algorithm has used input images in PGM format; problem is, Java doesn't have a native PGM image processor, hence why I'm still tweaking the Eigencuts examples. If anyone knows of something that would help with this, please let me know.

          People

          • Assignee:
            Shannon Quinn
            Reporter:
            Jeff Eastman
          • Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development