在R矩阵中检测相似的相邻值

Question

我有一个10x10的矩阵，其中包含0和1，1通常会成簇出现。 我正在尝试将这些1的集群提取到它们自己的矩阵列表中。下面是我的起始矩阵：

field <- matrix(0,10,10)
field[3:4,3:4]<-1
field[6:7,7]<-1
field[7:8,8]<-1
field[8,6]<-1
field
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
[1,]    0    0    0    0    0    0    0    0    0     0
[2,]    0    0    0    0    0    0    0    0    0     0
[3,]    0    0    1    1    0    0    0    0    0     0
[4,]    0    0    1    1    0    0    0    0    0     0
[5,]    0    0    0    0    0    0    0    0    0     0
[6,]    0    0    0    0    0    0    1    0    0     0
[7,]    0    0    0    0    0    0    1    1    0     0
[8,]    0    0    0    0    0    1    0    1    0     0
[9,]    0    0    0    0    0    0    0    0    0     0
[10,]   0    0    0    0    0    0    0    0    0     0

我希望最终得到一个类似于下面列表的矩阵列表（用0的边框来形成矩形）：

list(
    field[2:5,2:5],
    field[5:9,5:9]
  )

[[1]]
[,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    0    1    1    0
[3,]    0    1    1    0
[4,]    0    0    0    0

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

我甚至不知道这个概念的实现方式。是否有一些相关的软件包存在，或者有人能够提供做这件事情的帮助和解释？还是说这是不可能的？感谢您的帮助！

- bkauder

---

相关链接：http://math.stackexchange.com/questions/507742/distance-similarity-between-two-matrices 一旦你定义了相似度（或距离）度量，你就可以遍历所有可能的子矩阵并找到最佳匹配。 - nico

我会尝试迭代解决方案：取第一个“1”，然后增加周围的边框大小，直到它只包含零。提取子矩阵，将所有值设置为“0”，重复此过程。 - tonytonov

一个簇的条件是什么？一组由对角线、垂直或水平相邻完全连接的1，并且没有与任何其他1相邻的1。 - Spacedman

是的，Spacedman，那正是我所指的。 - bkauder

我有一个可能的解决方案，涉及使用 igraph 创建带有对角连接的格点图，丢弃与 field==1 相对应的图节点，然后循环遍历子图。抱歉这不是一个完整的解决方案，但可能会让您有所启发。 - Spacedman

Answer 1

首先，您需要定义相似度的计量方式。这里有一个关于此问题的 Math SE的讨论。

一种简单的方法是计算 余弦相似度。

因此，例如：

# Generate the matrix
field <- matrix(0,10,10)
field[3:4,3:4]<-1
field[6:7,7]<-1
field[7:8,8]<-1
field[8,6]<-1

# Our similarity function, adapt as needed    
simil <- function(m1, m2)
  {
  # Check dimensions are the same
  if (any(dim(m1) != dim(m2)))
    stop(paste("ERROR: matrices are not the same size: ",
               nrow(m1), "x", ncol(m1), "vs", 
               nrow(m2), "x", ncol(m2)))

  # Linearize the matrices
  m1 <- as.vector(m1)
  m2 <- as.vector(m2)

  # Cosine similarity
  similarity <- (m1%*%m2)/sqrt((m1%*%m1) * (m2%*%m2))

  return(similarity)
  }

现在，在三个可能的领域进行测试，似乎运行得相当不错

m1 <- field[2:5, 2:5]
m2 <- field[6:9, 6:9]
m3 <- field[4:7, 7:10]

> simil(m1, m2)
          [,1]
[1,] 0.6708204

> simil(m1, m3)
     [,1]
[1,]    0

> simil(m2, m3)
          [,1]
[1,] 0.2581989

而且，正如预期的那样：

> simil(m1,m1)
     [,1]
[1,]    1
> simil(m1,!m1)
     [,1]
[1,]    0

我们现在生成所有可能的矩阵，我已经使用两个嵌套的for循环完成了这项工作，虽然这种方法通常效率较低，但对于小型矩阵来说并不重要。

field.len <- 4

subfields <- list()
i <- 1
for (col in (1:(ncol(field)-field.len+1)))
  {
  for (row in (1:(nrow(field)-field.len+1)))
      {
      submatrix <- field[row:(row+field.len-1),col:(col+field.len-1)] 

      # Discard zero matrices
      if (sum(submatrix) > 0)
        {
        subfields[[i]] <- submatrix
        i <- i+1
        }
      }
  }

最后，找到相似矩阵。

simil.matrix <- sapply(subfields, function(sf1)
  {
  res <- sapply(subfields, function(sf2)
    {
    res <- simil(sf1, sf2)

    res
    })

  res
  })

例如：

例如：

> simil.matrix[1,24]
[1] 0.8660254
> subfields[[1]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    0    0    0    0
[3,]    0    0    1    1
[4,]    0    0    1    1
> subfields[[24]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    0    0    0    0
[3,]    0    0    1    0
[4,]    0    0    1    1

两个不太相似的矩阵

> simil.matrix[10,5]
[1] 0.25
> subfields[[10]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    1    0    0
[3,]    1    1    0    0
[4,]    0    0    0    0
> subfields[[5]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    0    0    0    0
[3,]    0    1    1    0
[4,]    0    1    1    0

和两个不同的

> simil.matrix[4,5]
[1] 0
> subfields[[4]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    1    1
[2,]    0    0    0    0
[3,]    0    0    0    0
[4,]    0    0    0    0
> subfields[[5]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    0    0    0    0
[3,]    0    1    1    0
[4,]    0    1    1    0

可能有更好的方法，但这似乎是一个不错的开始。

- nico