Кластерные группы 1 с в двоичной матрице

Question

Я хочу создать кластеры вокруг всех 1 с и 0 с. Как и в Mindsweeper, я хочу «нарисовать круг» вокруг всех 1 s и создать границу, в которой существует 0 s.

Я попытался использовать hclust() и создать матрицу расстояний, но фактическая таблица, с которой я работаю, очень велика, и у меня возникли проблемы со временем выполнения.

test_matrix  <- matrix(c( 1,1,0,0,0,0,1,     
                          1,1,1,0,0,1,0,
                          0,1,0,0,0,1,0,
                          0,0,0,1,1,1,0,
                          0,0,0,1,1,1,1),nrow=5)

Результат выглядит так:

     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    0    0    1    0    1    0
[2,]    1    1    0    0    0    1    1
[3,]    0    1    1    0    0    0    1
[4,]    0    1    0    0    0    0    1
[5,]    0    1    0    1    1    0    1

Мои правила следующие: если какой-либо 1 подключен к любому 1 через UP, DOWN, LEFT, RIGHT, DIAGONAL (любое направление), продолжайте увеличивать «кластер». Основываясь на этих правилах (8 точек подключения для каждой точки), я могу выделить четыре уникальных кластера с изолированными 1 с.

Как бы вы написали код, чтобы найти эти группы?

Answer 1

Я думаю, что кластеризация - правильный подход, но вы выбираете плохой (вычислительно дорогой) метод для этой задачи.Я бы выбрал DBSCAN так:

library(dbscan)

## slightly altered test matrix to include a "cluster" with a single 1
test_matrix  <- matrix(c( 1,1,0,0,0,0,1,     
                          1,1,1,0,0,1,0,
                          0,1,0,0,0,1,0,
                          0,0,0,1,1,1,0,
                          1,0,0,1,1,1,1),
                          nrow=5, byrow = TRUE)

## find rows and columns of 1s
ones_pos <- which(test_matrix > 0,arr.ind=TRUE)


## perform DBSCAN clustering
## setting eps = sqrt(2) + .1 corresponds to your neighbourhood definition
## setting minPts = 2 will mark clusters of one point as noise
clust <- dbscan(ones_pos, eps = sqrt(2), minPts = 2)

## find the indices of noise elements
singular_ones <- ones_pos[clust$cluster == 0, ]

singular_ones
#> row col 
#>  5   1 

Чтобы найти все кластеры (включая те, которые состоят только из 1), просто установите minPts в 1. В этом случае не может быть шума.Членство в кластере хранится в clust$cluster.

Я вполне уверен, что этот подход также будет довольно быстрым с большими матрицами.