Clustering of a matrix (homogeneity measurement)

Question

I have a 2 dim matrix, and I want to know e.g. all the higher values are in the upper left corner. I can't just project it into R^3 and use a standard clustering algorithm because I don't want to consider the value as a dimension by itself.

Is there an algorithm I can use for this?

EDIT:

To reformulate it, suppose it was like

| High values ... low values |
| ...
| Low values ...  ...        |
| ...
| High values .. low values  |

I'd want to know that there's a "cluster" of high values in the upper left and lower left.

EDIT 2:

The matrix represents an image. The values of each cell represent the concentration of a substance at that coordinate. I want to know how homogeneous the image is (i.e. how well "mixed together" the substance is). Additionally, I would like to know where the non-homogeneity (if any) is coming from.

Answer 1

This question is about spatial correlation. Many methods exist to characterize and quantify this. What they all have in common is comparing values at one location to those at nearby locations. Usually, the reference distribution is some kind of spatial stochastic process where data are generated independently from point to point ("complete spatial randomness"). Some methods only characterize average behavior while others provide more detailed exploratory tools to identify clusters of extreme values.

For three different approaches, check out (1) the literature on geostatistics/kriging/variography; (2) other measures of spatial correlation such as Ripley's K and L functions or the Getis-Ord $G_i$ statistics ; and (3) geographically weighted regression. Accessible, non-technical, and sort of correct explanations of all these can be found on ESRI.com . The Wikipedia articles are scanty and of variable quality, unfortunately.

The first two approaches are well supported with R packages such as spatstat and geoRglm. There is also free software for (2), of which some of the best known is Geoda and CrimeStat . I know of no free implementation of GWR (#3), but there are good resources maintained by its inventors.

Answer 2

You could also consider Moran's I which is available in the R package "ape". And then simply use a weighting based on distance:

nRows <- 30;
nCols <- 15;

nPixels <- nRows * nCols;

# Create a Random Image
image = matrix(0, nrow=nRows, ncol=nCols);

for ( I in 1:nRows )
  {
    for ( J in 1:nCols )
      {
        image[I,J] <- sample.int(256,1) - 1;
      } 
  }

# 1D to 2D Index Function
reverseIndex <- function ( vectorIdx, nRows, nCols )
  {
    # If you're using row major for some odd reason, you'll
    # need to flip these.

    J <- floor((vectorIdx-1) / nCols);
    I <- (vectorIdx-1) - nCols*J;

    return (c(I+1,J+1));
  } 

# Distance Function
distFunc <- function(I,J)
  {
    idx1 <- reverseIndex(I, nRows, nCols);
    idx2 <- reverseIndex(J, nRows, nCols);

    return (sqrt((idx1 - idx2) %*% (idx1 - idx2)));
  }

# Create Distance Matrix
dist = matrix(0, nrow=nPixels, ncol=nPixels);

for ( J in 1:nPixels )
  {
    dist[,J] <- sapply(1:nPixels, distFunc, J);
  }

# Invert Distance for Moran's I
invDist = 1.0 / dist;
diag(invDist) = 0.0;

# Load Library
library(ape);

# Compute Moran's I:
Moran.I(as.vector(image), dist);

R guru's feel free to weigh in on my code - I'm sure there are better / faster implementations. I know that for loops are insanely slow in R. Note that this will simply provide a measure & test of association, it will not identify where that association is in your matrix.

Answer 3

Good question. A trivial way to find "cluster of high values in the upper left" (as opposed to correlations) is to split the image into tiles and look at tile means. For example,

means of 100 x 100 tiles:
[[ 82  78  80  94  99 100]
 [ 80  53  66  62  80 100]
 [ 82  61  65  64  72  98]
 [ 87  83  99  81  80 100]
 [100 100 100 100 100 100]]

means of 50 x 50 tiles:
[[100  85  84 100  70  96 100 100 100 100 100]
 [ 83  59  57  71  67  88  89  86  98 100 100]
 [ 87  58  54  49  71  74  71  61  61 100 100]
 [100  76  58  52  59  61  55  59  65  95 100]
 [100  62  59  60  57  63  60  60  59  97 100]
 [100  68  65  59  59  82  76  61  61  70  95]
 [ 83  64  76  66  96 100  96  61  80  67 100]
 [100 100  97  92 100 100  84  82  83  88 100]
 [100 100 100 100 100 100 100 100 100 100 100]]

(a plot with average height / colour in each tile would be 10x better).

(If you're looking for features in images, what's a "feature" ? E.g. a red stop sign, as in Histograms for feature representation )

Answer 4

The goal is just to find out a measure that will tell us how mixed up all the pixels are. Given 2 matrices of data with the exact same distribution of values, if the first one's values are ordered or clumped together in spatial groups and the 2nd one's values are well-dispersed (high points and not near other high points, low points not near other lows), what is the method of evaluating this dispersion/ clumpyness? The matrices will have the exact same variance or standard deviation, so that is not a good method. One idea is using the 2D Fourier Transform, because a more clumpy image intuitively has a lower frequency, but I'm not sure if that is actually a common or useful practice for this type of evaluation.