Identificando "Clusters" ou "Grupos" em uma Matriz

Eu tenho uma matriz que é preenchida com elementos discretos e preciso agrupá-los (usando R) em grupos intactos. Então, por exemplo, considere esta matriz:

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

Haveria dois clusters separados para A, dois clusters separados para C e um cluster para B.

A saída que estou procurando seria idealmente atribuir um ID exclusivo para cada cluster, algo como isto:

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

No momento, escrevi um código que faz isso de forma recursiva, apenas verificando iterativamente o vizinho mais próximo, mas ele transborda rapidamente quando a matriz fica grande (ou seja, 100x100).

Existe uma função integrada no R que possa fazer isso? Eu olhei para o raster e processamento de imagem, mas sem sorte. Estou convencido de que deve estar lá fora.

O que você acha que é a medida da distância no seu caso?

Suponho que há três dimensões aqui:

• RowN (número da linha)
• ColN (número da coluna)
• Value (valor: A, B ou C)

Isso significa que os dados obtidos da 4x5matriz se parecem com:

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

Está valueescalado? Em outras palavras, é A < B < C?

Se sim, então

• você pode substituir {A, B, C}por {0, 1, 2}(ou pode ser {10, 11, 12}, se você quiser que essa diferença seja menos importante que os atributos RowN e ColN)
• normalize seus dados
• use, por exemplo, o algoritmo de clustering K-Means ( http://stat.ethz.ch/R-manual/R-patched/library/stats/html/kmeans.html ) do statspacote R

Nesse caso, a distância entre dois será:

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

Se valuenão estiver dimensionado (variável categórica regular), use algumas modificações do K-Means que funcionem com dados categóricos .

Portanto, no caso da matriz 100x100, você tem 10000 observações e três variáveis, o que é um tamanho de amostra bastante trivial.

Não tenho certeza se sua pergunta é classificada como um problema de cluster. No armazenamento em cluster, você está tentando descobrir grupos de exemplos semelhantes usando dados não rotulados. Aqui, parece que você deseja enumerar "agrupamentos" existentes de nós próximos.

Para ser sincero, não tenho idéia de tal função em R. Mas, no que diz respeito ao algoritmo, acredito que o que você está procurando é a etiquetagem de componentes conectados . Tipo de preenchimento de balde, para matrizes.

O artigo da Wikipedia está relacionado acima. Um dos algoritmos apresentados aqui, denominado algoritmo de passagem única, é o seguinte:

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

Eu acho que seria fácil criar o seu próprio usando o acima.