Identifying “clusters” or “groups” in a matrix

Question

I have a matrix that is populated with discrete elements, and I need to cluster them (using R) into intact groups. So, for example, take this matrix:

[A B B C A]  
[A A B A A]  
[A B B C C]  
[A A A A A]  

There would be two separate clusters for A, two separate clusters for C, and one cluster for B.

The output I'm looking for would ideally assign a unique ID to each cluster, something like this:

[1 2 2 3 4]  
[1 1 2 4 4]  
[1 2 2 5 5]  
[1 1 1 1 1]

Right now I wrote a code that does this recursively by just iteratively checking nearest neighbor, but it quickly overflows when the matrix gets large (i.e., 100x100).

Is there a built in function in R that can do this? I looked into raster and image processing, but no luck. I'm convinced it must be out there.

Answer 1

What do you think is distance measure in your case?

I assume there are three dimensions here:

• RowN (row number)
• ColN (column number)
• Value (value: A, B or C)

That means data you get from 4x5 matrix looks like:

Sample1 -> (1, 1, A)
Sample2 -> (1, 2, B)
...
Sample5 -> (1, 5, A)
Sample6 -> (2, 1, A)
...
Sample15 -> (3, 5, C)
...
Sample20 -> (4, 5, A)

Is value scaled? In other words, is A < B < C?

If yes, then

• you can replace {A, B, C} with {0, 1, 2} (or may be {10, 11, 12}, if you want this difference be less important than RowN and ColN attributes)
• normalize your data
• use, for example, K-Means clustering algorithm (http://stat.ethz.ch/R-manual/R-patched/library/stats/html/kmeans.html) from stats R package

In that case the distance between two will be:

Sqrt( (RowN1-RowN2)^2 + (ColN1-ColN2)^2 + (Value1-Value2)^2 )

If value is not scaled (regular categorical variable), use some modifications of K-Means that work with categorical data.

So in case of 100x100 matrix you have 10000 observations and three variables, which is pretty trivial sample size.

Answer 2

I'm not sure if your question classifies as a clustering problem. In clustering you are trying to discover clusters of similar examples using unlabelled data. Here, it seems you wish to enumerate existing "clusters" of nearby nodes.

To be honest, I have no idea of such a function in R. But, as far as the algorithm is concerned, I believe what you are looking for is Connected-Component Labeling. Kind of a bucket fill, for matrices.

The wikipedia article is linked above. One of the algorithms presented there, termed as single-pass algorithm, is as follows:

One-Pass(Image)
        [M, N]=size(Image);
        Connected = zeros(M,N);
        Mark = Value;
        Difference = Increment;
        Offsets = [-1; M; 1; -M];
        Index = [];
        No_of_Objects = 0; 

   for i: 1:M :
       for j: 1:N:
            if(Image(i,j)==1)            
                 No_of_Objects = No_of_Objects +1;            
                 Index = [((j-1)*M + i)];           
                 Connected(Index)=Mark;            
                 while ~isempty(Index)                
                      Image(Index)=0;                
                      Neighbors = bsxfun(@plus, Index, Offsets');
                      Neighbors = unique(Neighbors(:));                
                      Index = Neighbors(find(Image(Neighbors)));                                
                      Connected(Index)=Mark;
                 end            
                 Mark = Mark + Difference;
            end
      end
  end

I guess it'd be easy to roll your own using the above.