Identifizieren von "Clustern" oder "Gruppen" in einer Matrix

Ich habe eine Matrix, die mit diskreten Elementen gefüllt ist, und ich muss sie (mit R) in intakte Gruppen gruppieren. Nehmen Sie zum Beispiel diese Matrix:

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

Es würde zwei separate Cluster für A, zwei separate Cluster für C und einen Cluster für B geben.

Die Ausgabe, nach der ich suche, würde idealerweise jedem Cluster eine eindeutige ID zuweisen, etwa so:

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

Im Moment habe ich einen Code geschrieben, der dies rekursiv tut, indem er nur den nächsten Nachbarn iterativ überprüft, der jedoch schnell überläuft, wenn die Matrix groß wird (dh 100 x 100).

Gibt es in R eine eingebaute Funktion, die dies kann? Ich habe mich mit Raster und Bildverarbeitung befasst, aber kein Glück. Ich bin überzeugt, dass es da draußen sein muss.

Was ist Ihrer Meinung nach das Entfernungsmaß in Ihrem Fall?

Ich gehe davon aus, dass es hier drei Dimensionen gibt:

• RowN (Zeilennummer)
• ColN (Spaltennummer)
• Value (Wert: A, B oder C)

Das bedeutet, dass Daten, die Sie aus der 4x5Matrix erhalten, folgendermaßen aussehen:

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

Ist valueskaliert? Mit anderen Worten, ist A < B < C?

Wenn ja, dann

• Sie können ersetzen {A, B, C}mit {0, 1, 2}(oder kann sein {10, 11, 12}, wenn Sie diese Differenz weniger wichtig sein wollen als Rown und ColN Attribute)
• Normalisieren Sie Ihre Daten
• Verwenden Sie beispielsweise den K-Means-Clustering-Algorithmus ( http://stat.ethz.ch/R-manual/R-patched/library/stats/html/kmeans.html ) aus dem statsR-Paket

In diesem Fall beträgt der Abstand zwischen zwei:

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

Wenn valuenicht skaliert (reguläre kategoriale Variable), verwenden Sie einige Modifikationen von K-Means, die mit kategorialen Daten funktionieren .

Im Fall einer 100x100-Matrix haben Sie also 10000 Beobachtungen und drei Variablen, was eine ziemlich triviale Stichprobengröße ist.

Ich bin nicht sicher, ob Ihre Frage als Clustering-Problem eingestuft wird. Beim Clustering versuchen Sie, Cluster ähnlicher Beispiele mithilfe unbeschrifteter Daten zu ermitteln. Hier möchten Sie anscheinend vorhandene "Cluster" benachbarter Knoten auflisten.

Um ehrlich zu sein, habe ich keine Ahnung von einer solchen Funktion in R. Aber was den Algorithmus betrifft, glaube ich, dass Sie nach der Kennzeichnung verbundener Komponenten suchen . Eine Art Eimerfüllung für Matrizen.

Der Wikipedia-Artikel ist oben verlinkt. Einer der dort vorgestellten Algorithmen, der als Single-Pass-Algorithmus bezeichnet wird, lautet wie folgt:

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

Ich denke, es wäre einfach, deine eigenen mit den oben genannten zu rollen.