Метрика расстояния, предложенная @ Anony-Mousse, является хорошей
и естественный, но я ставлю под сомнение использование dbscan. С помощью
предлагаемый
distance = length of shortest path, or infinity if there is none
Любые два узла, которые напрямую связаны, будут на расстоянии 1.
Если бы вы использовали dbscan с epsilon <1, все точки были бы шумом
точки. Так что вы захотите epsilon> 1. Из вашего примера это выглядит
например, если на расстоянии 1 есть хотя бы одна точка,
тот же компонент, так
похоже, вы хотите minNumPts = 2. Это даст
результат, что это две точки соединены путем любой длины
они будут в одном кластере. Это выглядит как
вы после не имеет ничего общего с плотностью и кластеризацией,
скорее, я думаю, что вы хотите, это связанные компоненты.
Если два узла соединены путем любой длины, они
в том же компоненте. Нахождение этого через dbscan или другую кластеризацию
метод может быть возможным, но это, вероятно,
неправильный способ думать об этом. У вас есть график и график
теоретическая проблема. Вы, вероятно, должны использовать методы из графа
теория.
Я проиллюстрирую, используя R и igraph. Есть и другие инструменты
если тебя это не волнует.
Большая часть работы заключается в том, чтобы просто решить вашу проблему.
library(igraph)
to = c("a1", "a2", "a3", "a0", "b1", "b2", "b3", "b0")
from = c("a0", "a1", "a2", "a3", "b0", "b1", "b2", "b3")
EL = data.frame(from, to)
Vert = c("a0", "a1", "a2", "a3", "b0", "b1", "b2", "b3", "c0", "d0")
Vdf = data.frame(Vert)
g = graph_from_data_frame(d = EL, vertices=Vdf)
LO = matrix(c(1.2,1,1,1.2, 2.2,2,2,2.2, 0, 3, 4,3,2,1,4,3,2,1,4,4),
ncol=2)
plot(g, layout=LO)
Теперь мы можем использовать однострочник, чтобы получить все, что нам нужно
о компонентах.
Comp = components(g, mode="weak")
Comp
$membership
a0 a1 a2 a3 b0 b1 b2 b3 c0 d0
1 1 1 1 2 2 2 2 3 4
$csize
[1] 4 4 1 1
$no
[1] 4
Это говорит нам о членстве компонентов в узлах,
количество узлов на компонент и количество
компоненты. Так как вы хотели вызвать один узел
Компоненты «шум» в стиле dbscan можно
убедитесь, что компоненты 3 и 4 имеют по одному узлу.
Они шум. Другие являются «настоящими» компонентами.
Чтобы показать, как использовать это и прийти к завершению с
красивая картинка, я построю график раскраски
компоненты и использовать светло-серый для «шума».
ColorMap = rainbow(Comp$no)
ColorMap[Comp$csize == 1] = "lightgray"
plot(g, layout=LO, vertex.color=ColorMap[Comp$membership])
Я призываю вас думать о проблеме графа как о графике.