Блог

У меня есть матрица, которая заполнена дискретными элементами, и мне нужно объединить их в неповрежденные группы. Итак, например, возьмем эту матрицу:

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

Для A было бы два отдельных кластера, два отдельных кластера для C и один кластер для B.

Результат, который я ищу, в идеале назначил бы уникальный идентификатор каждому кластеру, что-то вроде этого:

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

Прямо сейчас у меня есть R-код, который делает это рекурсивно, просто итеративно проверяя ближайшего соседа, но он быстро переполняется, когда матрица становится большой (т. Е. 100×100).

Есть ли встроенная функция в R, которая может это сделать? Я изучил растровую обработку и обработку изображений, но безуспешно. Я убежден, что это должно быть там.

Спасибо!

Вы могли бы подойти к этому, построив граф решетки, представляющий вашу матрицу, где ребра сохраняются только в том случае, если вершины имеют одинаковый тип:

 # Build initial matrix and lattice graph
library(igraph)
mat <- matrix(c(1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 3, 1, 1, 1, 3, 1), nrow=4)
labels <- as.vector(mat)
g <- graph.lattice(dim(mat))
lyt <- layout.auto(g)

# Remove edges between elements of different types
edgelist <- get.edgelist(g)
retain <- labels[edgelist[,1]] == labels[edgelist[,2]]
g <- delete.edges(g, E(g)[!retain])

# Take a look at what we have
plot(g, layout=lyt)
 

Вершины нумеруются по столбцам вниз. Легко видеть, что все, что нам нужно сделать, это захватить компоненты этого графика:

 matrix(clusters(g)$membership, nrow=nrow(mat))
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    1    2    2    3    4
# [2,]    1    1    2    4    4
# [3,]    1    2    2    5    5
# [4,]    1    1    1    1    1
 

Если вы хотите включить диагонали в решетку, вы можете начать с решетки с размером окрестности 2, а затем ограничить элементы, которые находятся на расстоянии не более одной строки или одного столбца. Рассмотрим следующую матрицу:

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

Вот код, который будет захватывать 4 группы, а не 6, из-за включения диагональных ссылок:

 # Build initial matrix and lattice graph (neighborhood size 2)
mat <- matrix(c(1, 2, 2, 1, 3, 1, 2, 1), nrow=2)
labels <- as.vector(mat)
rows <- (seq(length(labels)) - 1) %% nrow(mat)
cols <- ceiling(seq(length(labels)) / nrow(mat))
g <- graph.lattice(dim(mat), nei=2)

# Remove edges between elements of different types or that aren't diagonal
edgelist <- get.edgelist(g)
retain <- labels[edgelist[,1]] == labels[edgelist[,2]] amp;
  abs(rows[edgelist[,1]] - rows[edgelist[,2]]) <= 1 amp;
  abs(cols[edgelist[,1]] - cols[edgelist[,2]]) <= 1
g <- delete.edges(g, E(g)[!retain])

# Cluster to obtain final groups
matrix(clusters(g)$membership, nrow=nrow(mat))
#      [,1] [,2] [,3] [,4]
# [1,]    1    2    3    4
# [2,]    2    1    1    1
 

Я не совсем уверен, отвечает ли это на ту же проблему, но недавно я написал некоторый код, который группирует сегменты стены в лабиринте таким же образом, т. Е. Ближайший сосед. Мой является итеративным и использует функцию dist() . Вот часть кода, который я использовал.

Я начинаю с матрицы N * 4, содержащей все сегменты стены (сгенерированные с использованием дерева Alg Прима); столбцы (x0, y0, x1, y1) определяют конечные точки данного сегмента. Все сегменты начинаются и заканчиваются целочисленными точками сетки и имеют длину 1. Каждый элемент treelist содержит все кластеризованные сегменты. Для опубликованного вопроса это должно быть немного проще, потому что каждый элемент имеет только одну координату (строку, столбец), а не две.

 treelist<-list()
 treecnt<-1
 #kill edge walls, i.e. wall segments on the border of the maze.
 #  edges<- which(dowalls[,1]==dowalls[,3] | dowalls[,2]==dowalls[,4])
 vedges <- which( (dowalls[,1]==dowalls[,3]) amp; (dowalls[,1]==1 | dowalls[,1]==dimx 1) )
 hedges <- which( (dowalls[,2]==dowalls[,4]) amp; (dowalls[,2]==1 | dowalls[,1]==dimy 1) )
 dowalls<-dowalls[-c(vedges,hedges),,drop=FALSE]
 # now sort into trees 
 while(nrow(dowalls)>0 ) {
     tree <- matrix(dowalls[1,],nr=1) #force dimensions 
     dowalls<-dowalls[-1,,drop=FALSE]
     treerow <- 1 #current row of tree we're looking at
     while ( treerow <= nrow(tree) ) {
         #only examine the first 'column' of the dist() matrix 'cause those are the
         # distances from the tree[] endpoints
         touch <- c( which(dist(rbind(tree[treerow,1:2],dowalls[,1:2]) )[1:nrow(dowalls)]==0),  which(dist(rbind(tree[treerow,1:2],dowalls[,3:4]) )[1:nrow(dowalls)]==0), which(dist(rbind(tree[treerow,3:4],dowalls[,1:2]) )[1:nrow(dowalls)]==0), which(dist(rbind(tree[treerow,3:4],dowalls[,3:4]) )[1:nrow(dowalls)]==0) )
         if(length(touch) ) {
            tree <- rbind(tree,dowalls[c(touch),])
            dowalls <- dowalls[-c(touch),,drop=FALSE] 
            }
    # now be careful: want to track the row of tree[] we're working with AND
    # track how many rows there currently are in tree[]
        treerow <- treerow   1 
    } #end of while treerow <= nrow 
    treelist[[treecnt]]<-tree
    treecnt <- treecnt   1 
} #end ; all walls have been classified