时间戳

首页 > 解决方案 > 二元矩阵中 1 的聚类组

r - 二元矩阵中 1 的聚类组

问题描述

我正在寻找围绕所有1s 和0s 创建集群。与Mindsweeper类似，我想基本上在所有s周围“画一个圆圈” ，并在s存在1的地方创建一个边框。0

我曾尝试使用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

我的规则如下：如果任何通过 UP、DOWN、LEFT、RIGHT、DIAGONAL（任何方向）1连接到任何1，则继续增长“集群”。基于这些规则（每个点有 8 个连接点），我可以发现四个具有孤立1s 的独特集群。

您将如何编写代码来查找这些组？

标签： rmatrixbinary

解决方案

我认为聚类在这里是正确的方法，但是您为该任务选择了一种较差的（计算量大的）方法。我会像这样去 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.

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

推荐阅读