Identificación de "grupos" o "grupos" en una matriz

Tengo una matriz que se rellena con elementos discretos, y necesito agruparlos (usando R) en grupos intactos. Entonces, por ejemplo, tome esta matriz:

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

Habría dos grupos separados para A, dos grupos separados para C y un grupo para B.

La salida que estoy buscando idealmente asignaría una ID única a cada clúster, algo como esto:

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

En este momento, escribí un código que hace esto de forma recursiva al verificar iterativamente el vecino más cercano, pero se desborda rápidamente cuando la matriz se hace grande (es decir, 100x100).

¿Hay una función incorporada en R que pueda hacer esto? Miré en el procesamiento de imágenes y trama, pero no tuve suerte. Estoy convencido de que debe estar ahí afuera.

¿Cuál crees que es la medida de distancia en tu caso?

Supongo que hay tres dimensiones aquí:

• RowN (numero de fila)
• ColN (número de columna)
• Value (valor: A, B o C)

Eso significa que los datos que obtiene de la 4x5matriz se ven así:

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

¿Es valueescalado? En otras palabras, es A < B < C?

Si es así, entonces

• puede reemplazar {A, B, C}con {0, 1, 2}(o puede ser {10, 11, 12}, si desea que esta diferencia sea menos importante que los atributos RowN y ColN)
• normaliza tus datos
• utilice, por ejemplo, el algoritmo de agrupación K-Means ( http://stat.ethz.ch/R-manual/R-patched/library/stats/html/kmeans.html ) del statspaquete R

En ese caso, la distancia entre dos será:

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

Si valueno está escalado (variable categórica regular), use algunas modificaciones de K-Means que funcionen con datos categóricos .

Entonces, en el caso de una matriz de 100x100, tiene 10000 observaciones y tres variables, que es un tamaño de muestra bastante trivial.

No estoy seguro de si su pregunta se clasifica como un problema de agrupamiento. Al agrupar, está tratando de descubrir grupos de ejemplos similares utilizando datos no etiquetados. Aquí, parece que desea enumerar los "grupos" existentes de nodos cercanos.

Para ser honesto, no tengo idea de tal función en R. Pero, en lo que respecta al algoritmo, creo que lo que está buscando es el etiquetado de componentes conectados . Una especie de relleno de cubo, para matrices.

El artículo de wikipedia está vinculado anteriormente. Uno de los algoritmos presentados allí, denominado algoritmo de un solo paso, es el siguiente:

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

Supongo que sería fácil rodar el tuyo usando lo anterior.