r - 二进制矩阵中的 1 组群

Question

我希望在所有 1 周围创建集群s 和 0 s。类似于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通过向上、向下、向左、向右、对角线(任何方向)，继续增长“集群”。基于这些规则(每个点有 8 个连接点)，我可以发现四个具有孤立 1 的独特集群。 s。

您将如何编码以找到这些组？

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 .

我很确定这种方法对于大型矩阵也会非常快。