Wyjaśnienie pytania wskazuje, że chciałbyś, aby klastrowanie opierało się na rzeczywistych segmentach linii , w tym sensie, że dowolne dwie pary początek-miejsce docelowe (OD) powinny być uważane za „zamknięte”, gdy oba początki są bliskie, a oba miejsca docelowe są bliskie , niezależnie od tego, który punkt uważa się za początek lub cel podróży .
Ta formuła sugeruje, że masz już wyczucie odległości d między dwoma punktami: może to być odległość podczas lotu samolotu, odległość na mapie, czas podróży w obie strony lub jakikolwiek inny parametr, który nie zmienia się, gdy O i D są zamieniono. Jedyną komplikacją jest to, że segmenty nie mają unikalnych reprezentacji: odpowiadają one nieuporządkowanym parom {O, D}, ale muszą być reprezentowane jako pary uporządkowane , (O, D) lub (D, O). Możemy zatem przyjąć odległość między dwiema uporządkowanymi parami (O1, D1) i (O2, D2), aby być jakąś symetryczną kombinacją odległości d (O1, O2) id (D1, D2), takich jak ich suma lub kwadrat pierwiastek z sumy ich kwadratów. Napiszmy tę kombinację jako
distance((O1,D1), (O2,D2)) = f(d(O1,O2), d(D1,D2)).
Wystarczy zdefiniować odległość między nieuporządkowanymi parami, aby była mniejsza z dwóch możliwych odległości:
distance({O1,D1}, {O2,D2}) = min(f(d(O1,O2)), d(D1,D2)), f(d(O1,D2), d(D1,O2))).
W tym momencie możesz zastosować dowolną technikę grupowania opartą na macierzy odległości.
Jako przykład obliczyłem wszystkie 190 odległości punkt-punkt na mapie dla 20 najbardziej zaludnionych amerykańskich miast i poprosiłem o osiem klastrów przy użyciu metody hierarchicznej. (Dla uproszczenia użyłem euklidesowych obliczeń odległości i zastosowałem domyślne metody w używanym przeze mnie oprogramowaniu: w praktyce będziesz chciał wybrać odpowiednie odległości i metody grupowania dla swojego problemu). Oto rozwiązanie z klastrami oznaczonymi kolorem każdego segmentu linii. (Kolory zostały losowo przypisane do klastrów).
Oto Rkod, który wytworzył ten przykład. Jego dane wejściowe to plik tekstowy z polami „Długość geograficzna” i „Szerokość geograficzna” dla miast. (Aby oznaczyć miasta na rysunku, zawiera również pole „Klucz”).
#
# Obtain an array of point pairs.
#
X <- read.csv("F:/Research/R/Projects/US_cities.txt", stringsAsFactors=FALSE)
pts <- cbind(X$Longitude, X$Latitude)
# -- This emulates arbitrary choices of origin and destination in each pair
XX <- t(combn(nrow(X), 2, function(i) c(pts[i[1],], pts[i[2],])))
k <- runif(nrow(XX)) < 1/2
XX <- rbind(XX[k, ], XX[!k, c(3,4,1,2)])
#
# Construct 4-D points for clustering.
# This is the combined array of O-D and D-O pairs, one per row.
#
Pairs <- rbind(XX, XX[, c(3,4,1,2)])
#
# Compute a distance matrix for the combined array.
#
D <- dist(Pairs)
#
# Select the smaller of each pair of possible distances and construct a new
# distance matrix for the original {O,D} pairs.
#
m <- attr(D, "Size")
delta <- matrix(NA, m, m)
delta[lower.tri(delta)] <- D
f <- matrix(NA, m/2, m/2)
block <- 1:(m/2)
f <- pmin(delta[block, block], delta[block+m/2, block])
D <- structure(f[lower.tri(f)], Size=nrow(f), Diag=FALSE, Upper=FALSE,
method="Euclidean", call=attr(D, "call"), class="dist")
#
# Cluster according to these distances.
#
H <- hclust(D)
n.groups <- 8
members <- cutree(H, k=2*n.groups)
#
# Display the clusters with colors.
#
plot(c(-131, -66), c(28, 44), xlab="Longitude", ylab="Latitude", type="n")
g <- max(members)
colors <- hsv(seq(1/6, 5/6, length.out=g), seq(1, 0.25, length.out=g), 0.6, 0.45)
colors <- colors[sample.int(g)]
invisible(sapply(1:nrow(Pairs), function(i)
lines(Pairs[i, c(1,3)], Pairs[i, c(2,4)], col=colors[members[i]], lwd=1))
)
#
# Show the points for reference
#
positions <- round(apply(t(pts) - colMeans(pts), 2,
function(x) atan2(x[2], x[1])) / (pi/2)) %% 4
positions <- c(4, 3, 2, 1)[positions+1]
points(pts, pch=19, col="Gray", xlab="X", ylab="Y")
text(pts, labels=X$Key, pos=positions, cex=0.6)
(Autor: Cassiopeia sweet z japońskiej Wikipedii GFDL lub CC-BY-SA-3.0 , za pośrednictwem Wikimedia Commons)