2

Vincent Zoonekind によって記述された 2 つの関数 (ここで見つけることができます) を使用して、次のグラフを作成しました (私のコードは記事の最後にあります)。

隣接する 3 つのポイントに接続されたポイント

その近傍グラフとそのパラメーター「k」が何であるかを説明できるようにするために、Isometric Feature Mappingが使用します。「k」は、各ポイントが直接接続されているポイントの数を指定します。それらの距離は、互いのユークリッド距離です。任意の点とその (k + 1) に最も近い点 (またはさらに離れた点) の間の距離は「測地線」と呼ばれ、そこに到達するために必要なすべてのエッジの長さの最小の合計です。これは、ユークリッド距離よりもはるかに長い場合があります。これは、私の図のポイント A と B の場合です。

ここで、点 A から点 B までの測地線距離を示す黒い線を追加したいと思います。線を追加するのにsegments()おそらく最適なコマンドについて知っています。 ) は Dijkstra のアルゴリズムであり、パッケージに実装されていることigraph。ただし、igraphグラフを解釈することも、渡す必要があるポイント (頂点) (およびその座標) を自分で見つけることもできません。

ところで、k = 18 の場合、つまりすべての点が最も近い 18 点に直接接続されている場合、A と B の間の測地線距離はちょうどユークリッド距離になります。

isomap.incidence.matrix <- function (d, eps=NA, k=NA) {
  stopifnot(xor( is.na(eps), is.na(k) ))
  d <- as.matrix(d)
  if(!is.na(eps)) {
    im <- d <= eps
  } else {
    im <- apply(d,1,rank) <= k+1
    diag(im) <- FALSE
  }
  im | t(im)
}

plot.graph <- function (im,x,y=NULL, ...) {
  if(is.null(y)) {
    y <- x[,2]
    x <- x[,1]
  }
  plot(x,y, ...)
  k <- which(  as.vector(im)  )
  i <- as.vector(col(im))[ k ]
  j <- as.vector(row(im))[ k ]
  segments( x[i], y[i], x[j], y[j], col = "grey")
}

z <- seq(1.1,3.7,length=140)*pi

set.seed(4)
zz <- rnorm(1:length(z))+z*sin(z)
zz <- cbind(zz,z*cos(z)*seq(3,1,length=length(z)))

dist.grafik <- dist(zz)

pca.grafik <- princomp(zz)

x11(8, 8)
par(mar=c(0,0,0,0))
plot.graph(isomap.incidence.matrix(dist.grafik, k=3), pca.grafik$scores[,1], pca.grafik$scores[,2],
           xaxt = "n", yaxt = "n", xlab = "", ylab = "", cex = 1.3)
legend("topright", inset = 0.02, legend = "k = 3", col = "grey", lty = 1, cex = 1.3) 
segments(x0 = -8.57, y0 = -1.11, x1 = -10.83, y1 = -5.6, col = "black", lwd = 2, lty = "dashed")
text(x = -8.2, y = -1.4, labels = "A", font = 2, cex = 1.2)
text(x = -11, y = -5.1, labels = "B", font = 2, cex = 1.2)
4

1 に答える 1

2

次のコードは、データを使用して、ノード間のユークリッド距離である重みを持つ igraph オブジェクトを作成するのに役立ちます。次に、によって返される加重最短パスを見つけますsp$vpath[[1]]。次の例では、ノード番号 5 と 66 の間の最短パスです。mattuからプロットするソリューションでコードを編集しました。

isomap.incidence.matrix <- function (d, eps=NA, k=NA) {
  stopifnot(xor( is.na(eps), is.na(k) ))
  d <- as.matrix(d)
  if(!is.na(eps)) {
    im <- d <= eps
  } else {
    im <- apply(d,1,rank) <= k+1
    diag(im) <- FALSE
  }
  im | t(im)
}

plot.graph <- function (im,x,y=NULL, ...) {
  if(is.null(y)) {
    y <- x[,2]
    x <- x[,1]
  }
  plot(x,y, ...)
  k <- which(  as.vector(im)  )
  i <- as.vector(col(im))[ k ]
  j <- as.vector(row(im))[ k ]
  segments( x[i], y[i], x[j], y[j], col = "grey")
}

z <- seq(1.1,3.7,length=100)*pi

set.seed(4)
zz <- rnorm(1:length(z))+z*sin(z)
zz <- cbind(zz,z*cos(z)*seq(3,1,length=length(z)))

dist.grafik <- as.matrix(dist(zz))
pca.grafik <- princomp(zz)

isomap.resul <-  function (d, eps=NA, k=NA) {
  a <- isomap.incidence.matrix(d, eps, k)
  b <- dist.grafik
  res <- a * b
  return(res)
}

a <- graph_from_adjacency_matrix(isomap.resul(dist.grafik, k=3), 
                                 mode = c("undirected"), weight = TRUE)
sp <- shortest_paths(a, 5, to = 66, mode = c("out", "all", "in"),
                     weights = NULL, output = c("vpath", "epath", "both"),
                     predecessors = FALSE, inbound.edges = FALSE)

path <- sp$vpath[[1]] 

x11(8, 8)
par(mar=c(0,0,0,0))
plot.graph(isomap.incidence.matrix(dist.grafik, k=3), pca.grafik$scores[,1], pca.grafik$scores[,2],
           xaxt = "n", yaxt = "n", xlab = "", ylab = "", cex = 1.3)
legend("topright", inset = 0.02, legend = "k = 3", col = "grey", lty = 1, cex = 1.3) 
segments(x0 = -8.57, y0 = -1.11, x1 = -10.83, y1 = -5.6, col = "black", lwd = 2, lty = "dashed")
text(x = -8.2, y = -1.4, labels = "A", font = 2, cex = 1.2)
text(x = -11, y = -5.1, labels = "B", font = 2, cex = 1.2)

for(i in 2:length(path)){
  aa <- pca.grafik$scores[path[i-1], 1]
  bb <- pca.grafik$scores[path[i-1], 2]
  cc <- pca.grafik$scores[path[i], 1]
  dd <- pca.grafik$scores[path[i], 2]
  segments(aa, bb, cc , dd, lwd = 2)
}

このスクリプトを実行するには、明らかにパッケージが必要ですigraph。

私には、測地線距離によると最短経路のようです。 ここに画像の説明を入力

それが役に立てば幸い。

于 2017-01-12T17:17:38.453 に答える