很大程度上依赖于要分组的所有相邻元素仅形成矩形/线/点的事实,我们看到矩阵的元素可以根据它们的值进行聚合[row, col]
通过关系对矩阵进行索引(abs(row1 - row2) + abs(col1 - col2)) < 2
.
所以,从[row, col]
指数:
sm = as.matrix(summary(m))
我们计算它们的距离,正如 GiuGe 所指出的,这实际上是“曼哈顿”方法:
d = dist(sm, "manhattan")
单链接在其最近邻居上聚类元素的属性在这里很有用。此外,我们还可以通过以下方式对元素进行分组cutree
计算“h = 1”(其中索引距离为“
gr = cutree(hclust(d, "single"), h = 1)
最后,我们可以将上面的内容包装在一个新的稀疏矩阵中:
sparseMatrix(i = sm[, "i"], j = sm[, "j"], x = gr)
#8 x 8 sparse Matrix of class "dgCMatrix"
#
#[1,] 1 1 1 . . . . .
#[2,] 1 1 1 . 4 4 . .
#[3,] 1 1 1 . 4 4 . .
#[4,] . . . . 4 4 . .
#[5,] . . 3 3 . . 7 7
#[6,] 2 . 3 3 . . 7 7
#[7,] 2 . . . 5 . . .
#[8,] 2 . . . . 6 6 6
使用的“m”是:
library(Matrix)
m = new("ngCMatrix"
, i = c(0L, 1L, 2L, 5L, 6L, 7L, 0L, 1L, 2L, 0L, 1L, 2L, 4L, 5L, 4L,
5L, 1L, 2L, 3L, 6L, 1L, 2L, 3L, 7L, 4L, 5L, 7L, 4L, 5L, 7L)
, p = c(0L, 6L, 9L, 14L, 16L, 20L, 24L, 27L, 30L)
, Dim = c(8L, 8L)
, Dimnames = list(NULL, NULL)
, factors = list()
)
EDIT 2017 年 2 月 10 日
另一个想法(再次考虑到相邻元素仅形成矩形/线/点的事实)是在升序列中迭代[row, col]
索引,并在每一步中找到当前列和行中其最近邻居的每个元素的距离。如果发现“
ff = function(x)
{
sm = as.matrix(summary(x))
gr = integer(nrow(sm)); ngr = 0L ; gr[1] = ngr
lastSeenRow = integer(nrow(x))
lastSeenCol = integer(ncol(x))
for(k in 1:nrow(sm)) {
kr = sm[k, 1]; kc = sm[k, 2]
i = lastSeenRow[kr]
j = lastSeenCol[kc]
if(i && (abs(kc - sm[i, 2]) == 1)) gr[k] = gr[i]
else if(j && (abs(kr - sm[j, 1]) == 1)) gr[k] = gr[j]
else { ngr = ngr + 1L; gr[k] = ngr }
lastSeenRow[kr] = k
lastSeenCol[kc] = k
}
sparseMatrix(i = sm[, "i"], j = sm[, "j"], x = gr)
}
并应用于“m”:
ff(m)
#8 x 8 sparse Matrix of class "dgCMatrix"
#
#[1,] 1 1 1 . . . . .
#[2,] 1 1 1 . 4 4 . .
#[3,] 1 1 1 . 4 4 . .
#[4,] . . . . 4 4 . .
#[5,] . . 3 3 . . 7 7
#[6,] 2 . 3 3 . . 7 7
#[7,] 2 . . . 5 . . .
#[8,] 2 . . . . 6 6 6
此外,两个函数以相同的顺序返回组也很方便,我们可以检查一下:
identical(mySolution(m), ff(m))
#[1] TRUE
举一个看似更复杂的例子:
mm = new("ngCMatrix"
, i = c(25L, 26L, 27L, 25L, 29L, 25L, 25L, 17L, 18L, 26L, 3L, 4L, 5L,
14L, 17L, 18L, 25L, 27L, 3L, 4L, 5L, 17L, 18L, 23L, 26L, 3L,
4L, 5L, 10L, 17L, 18L, 9L, 11L, 17L, 18L, 10L, 17L, 18L, 3L,
17L, 18L, 21L, 17L, 18L, 17L, 18L, 1L, 2L, 3L, 4L, 16L, 8L, 17L,
18L, 19L, 20L, 21L, 22L, 23L, 24L, 25L, 7L, 9L, 10L, 11L, 26L,
8L, 27L, 1L, 2L, 28L, 1L, 2L, 15L, 27L, 1L, 2L, 21L, 22L, 1L,
2L, 7L, 21L, 22L, 1L, 2L, 6L, 24L, 1L, 2L, 5L, 11L, 16L, 25L,
26L, 27L, 4L, 15L, 17L, 19L, 25L, 26L, 27L, 3L, 16L, 25L, 26L,
27L, 2L, 28L, 1L)
, p = c(0L, 0L, 3L, 3L, 5L, 6L, 7L, 7L, 10L, 18L, 25L, 31L, 35L, 38L,
42L, 44L, 46L, 51L, 61L, 66L, 68L, 71L, 75L, 79L, 84L, 88L, 96L,
103L, 108L, 110L, 111L)
, Dim = c(30L, 30L)
, Dimnames = list(NULL, NULL)
, factors = list()
)
identical(mySolution(mm), ff(mm))
#[1] TRUE
以及更大矩阵上的简单基准:
times = 30 # times `dim(mm)`
MM2 = do.call(cbind, rep_len(list(do.call(rbind, rep_len(list(mm), times))), times))
dim(MM2)
#[1] 900 900
system.time({ ans1 = mySolution(MM2) })
# user system elapsed
# 449.50 0.53 463.26
system.time({ ans2 = ff(MM2) })
# user system elapsed
# 0.51 0.00 0.52
identical(ans1, ans2)
#[1] TRUE