我有以下简单问题。我有多个节点的距离矩阵,我想获得该节点的子集列表,以便在每个子集中,每两个节点的最小距离为 dmin 。也就是说,最初每两个节点都通过具有关联值的边连接。我想删除值小于 dmin 的每一条边,并列出所有生成的断开连接图。
本质上,我想获得彼此非常接近的数据点集群,不是使用聚类算法,而是使用距离阈值。
我的问题自然是如何在 R 中完成它。考虑以下矩阵 m:
a b c d
a 1.0 0.9 0.2 0.3
b 0.9 1.0 0.4 0.1
c 0.2 0.4 1.0 0.7
d 0.3 0.1 0.7 1.0
有四个节点(a、b、c、d)。我搜索给定该矩阵(实际上是 1 - 距离矩阵)和阈值 dmin 的函数或包,例如 dmin <- 0.5
,会产生两组:{a,b}
和{c,d}
。实现它的一种非常低效的方法如下:
clusters <- list()
nodes <- colnames( m )
dmin <- 0.5
# loop over nodes
for( n in nodes ) {
found <- FALSE
# check whether a node can be associated to one of the existing
# clusters
for( c in names( clusters ) ) {
if( any( m[ n, clusters[[c]] ] > 0.5 ) ) {
clusters[[c]] <- c( clusters[[c]], n )
found <- TRUE
next
}
}
# no luck? create a new cluster for that node
if( ! found )
clusters[[n]] <- c( n )
}
结果是
> clusters
$a
[1] "a" "b"
$c
[1] "c" "d"
最佳答案
根据您的相似度矩阵m
,
您可以将邻接矩阵构建为 m > .5
,
构造相应的图
使用 igraph
包
并提取其连通分量。
m <- matrix(c(10,9,2,3, 9,10,4,1, 2,4,10,7, 3,1,7,10), 4, 4)/10
colnames(m) <- rownames(m) <- letters[1:4]
library(igraph)
g <- graph.adjacency( m > .5 )
plot(g)
clusters(g)$membership
# [1] 1 1 2 2
tapply(colnames(m), clusters(g)$membership, c)
# $`1`
# [1] "a" "b"
# $`2`
# [1] "c" "d"
关于r - 在 R 中切割图形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18103824/