2

次の簡単な問題があります。いくつかのノードの距離行列があり、各サブセット内で 2 つのノードごとに最小距離 dmin になるように、このノードのサブセットのリストを取得したいと考えています。つまり、最初は、2 つのノードのそれぞれが、関連付けられた値を持つエッジによって接続されます。値が 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

4 つのノード (a、b、c、d) があります。その行列 (実際には 1 - 距離行列) としきい値 dmin が与えられた関数またはパッケージを検索します。たとえばdmin <- 0.5、 と の 2 つのセットが生成{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"
4

1 に答える 1

2

類似度行列 から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"
于 2013-08-07T13:48:58.250 に答える