Identifier des «clusters» ou «groupes» dans une matrice

J'ai une matrice qui est remplie d'éléments discrets et je dois les regrouper (en utilisant R) en groupes intacts. Alors, par exemple, prenez cette matrice:

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

Il y aurait deux clusters distincts pour A, deux clusters distincts pour C et un cluster pour B.

La sortie que je recherche attribuerait idéalement un ID unique à chaque cluster, quelque chose comme ceci:

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

À l'heure actuelle, j'ai écrit un code qui le fait de manière récursive en vérifiant simplement de manière itérative le plus proche voisin, mais il déborde rapidement lorsque la matrice devient grande (c'est-à-dire 100x100).

Y a-t-il une fonction intégrée dans R qui peut le faire? J'ai étudié le raster et le traitement d'image, mais pas de chance. Je suis convaincu que ce doit être là-bas.

Selon vous, quelle est la mesure de distance dans votre cas?

Je suppose qu'il y a trois dimensions ici:

• RowN (numéro de ligne)
• ColN (numéro de colonne)
• Value (valeur: A, B ou C)

Cela signifie que les données que vous obtenez de la 4x5matrice ressemblent à:

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 valuemis à l'échelle? En d'autres termes, est-ce A < B < C?

Si oui, alors

• vous pouvez remplacer {A, B, C}par {0, 1, 2}(ou peut-être {10, 11, 12}, si vous voulez que cette différence soit moins importante que les attributs RowN et ColN)
• normaliser vos données
• utiliser, par exemple, l'algorithme de clustering K-Means ( http://stat.ethz.ch/R-manual/R-patched/library/stats/html/kmeans.html ) du statspackage R

Dans ce cas, la distance entre deux sera:

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

Si valuen'est pas mis à l'échelle (variable catégorielle régulière), utilisez certaines modifications des K-Means qui fonctionnent avec des données catégorielles .

Donc, dans le cas d'une matrice 100x100, vous avez 10000 observations et trois variables, ce qui est une taille d'échantillon assez banale.

Je ne sais pas si votre question est classée comme un problème de clustering. Dans le clustering, vous essayez de découvrir des clusters d'exemples similaires à l'aide de données non étiquetées. Ici, il semble que vous souhaitiez énumérer les "clusters" existants de nœuds voisins.

Pour être honnête, je n'ai aucune idée d'une telle fonction dans R. Mais, en ce qui concerne l'algorithme, je crois que ce que vous recherchez est l' étiquetage des composants connectés . Une sorte de remplissage de seau, pour les matrices.

L'article de wikipedia est lié ci-dessus. L'un des algorithmes présentés ici, appelé algorithme à passage unique, est le suivant:

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

Je suppose qu'il serait facile de rouler le vôtre en utilisant ce qui précède.