# Clustering of a matrix (homogeneity measurement)

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.

-
2x2 matrix's upper left corner is only one element... Can you reformulate the question? –  mbq Sep 30 '10 at 14:11
@mbq: I tried to reformulate, let me know if it's still unclear (high values and low values refer to block matrices inside the big matrix) –  Xodarap Sep 30 '10 at 14:17
Much better now, thanks. Still, the more details you'll put here (Are those clusters sharp or smooth? Is it all noisy? How large should be those clusters?) the more useful answer you get. –  mbq Sep 30 '10 at 14:27

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.

-
I knew of no freeware GWR implementation either until I came across this website recently, ecoevol.ufg.br/sam/#Graphics . I wouldn't be surprised if others exist though. –  Andy W Oct 24 '10 at 16:03
@Andy Thank you! That's a real find. This software looks like it reproduces GeoDa's capabilities with the addition of logistic regression and GWR. I look forward to exploring it. –  whuber Oct 24 '10 at 21:09

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;

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.

-
This looks very useful! Just to be clear (since I'm not fluent in R): this calculates spatial correlation, but weights more highly correlations between things that are closer together. Is that correct? –  Xodarap Oct 6 '10 at 19:44
Precisely. It uses the inverse distance between the pixels (as measured in pixels) to weight the measure of spatial autocorrelation. Note that I generated a grayscale image, but you could similarly apply this to a color image either treating the colors separately or taking some combined score. –  M. Tibbits Oct 6 '10 at 19:46

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 )

-