in einer Matrix benachbarten Punkten Tagging

Question

I eine 8x8-Matrix haben:

1 1 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 1 0 0 
0 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 1 

-Code, es zu schaffen:

examplemat <- matrix(c(1, 1, rep(0, 6), 1, rep(0, 9), 1, 1, rep(0, 17), 1, rep(0, 7), 1, rep(0, 5), 1, rep(0, 11), 1), 8, 8, byrow=T) 

Die, die extrahiert wurden, als Koordinaten:

onecoords <- which(examplemat == 1, arr.ind=T) 

     row col 
[1,] 1 1 
[2,] 2 1 
[3,] 1 2 
[4,] 3 3 
[5,] 3 4 
[6,] 7 4 
[7,] 5 6 
[8,] 6 6 
[9,] 8 8 

I benötigen einen einfachen, vektorisierten Ansatz zum Gruppieren der Einsen in Gruppen benachbarter Koordinaten. (Für die Zwecke dieser Aufgabe würde ich 4-Wege-Up/Down/Links/Rechts-Nachbarschaft, aber Sie möchten möglicherweise auch die Option der 8-Wege-Nachbarschaft einschließlich der Diagonalen.)

In dem Beispiel würden wir am Ende mit 5 Cluster von Zellen:

 row col clus 
[1,] 1 1 A 
[2,] 2 1 A 
[3,] 1 2 A 
[4,] 3 3 B 
[5,] 3 4 B 
[6,] 7 4 C 
[7,] 5 6 D 
[8,] 6 6 D 
[9,] 8 8 E 

Das 4-Wege-adjacency Check ist ziemlich einfach: sum(abs(onecoords[1,] - onecoords[2,])) == 1 Aber ich bin zu kämpfen, wie man trainiert diese effizient vektorisieren.

Answer 1

Mit Dank an alexis_laz und Carl Witthoft für sehr hilfreiche Kommentare, die es mir ermöglichen, dies selbst zu beantworten.

Vierwege adjacency

Cluster adjacency basiert auf 4-Wege zu erhalten, verwenden hierarchische Clustering mit Single-Linkage auf Manhattan Distanz:

cbind(onecoords, clus = cutree(hclust(dist(onecoords, "manhattan"), "single"), h = 1)) 
     row col clus 
[1,] 1 1 1 
[2,] 2 1 1 
[3,] 1 2 1 
[4,] 3 3 2 
[5,] 3 4 2 
[6,] 7 4 3 
[7,] 5 6 4 
[8,] 6 6 4 
[9,] 8 8 5 

Acht-Wege-adjacency

Um Cluster basierend auf der 8-Wege-Adjazenz (einschließlich Diagonalen) zu erhalten, verwenden Sie hierarchisches Clustering mit einem einzelnen Link Alter auf maximale Entfernung:

cbind(onecoords, clus = cutree(hclust(dist(onecoords, "maximum"), "single"), h = 1)) 

Unterschied zwischen Manhattan und maximalen Entfernungen

Im Beispielfall dieser beide die gleichen Ergebnisse, aber wenn Sie die erste Zeile entfernen, zum Beispiel, sehen Sie, diese Manhattan-Entfernung produziert 6 Cluster, während die maximale Entfernung 5 Cluster erzeugt.

cbind(onecoords[2:9,], clus = cutree(hclust(dist(onecoords[2:9,], "manhattan"), "single"), h = 1)) 
    row col clus 
[1,] 2 1 1 
[2,] 1 2 2 
[3,] 3 3 3 
[4,] 3 4 3 
[5,] 7 4 4 
[6,] 5 6 5 
[7,] 6 6 5 
[8,] 8 8 6 
cbind(onecoords[2:9,], clus = cutree(hclust(dist(onecoords[2:9,], "maximum"), "single"), h = 1)) 
    row col clus 
[1,] 2 1 1 
[2,] 1 2 1 
[3,] 3 3 2 
[4,] 3 4 2 
[5,] 7 4 3 
[6,] 5 6 4 
[7,] 6 6 4 
[8,] 8 8 5