Кластеризация по повторным данным

Question

Есть ли способ разбить набор данных, состоящий из пар трехмерных точек (или только их индексных номеров) на связанные кластеры? То есть две пары (a, b) и (c, d) должны находиться в одном кластере, если они имеют общую точку (т. Е. A = c, b = c, a = d или b = d) или если есть цепочка из одной или нескольких других пар, каждая из которых имеет общую точку с предыдущей, от одной пары к другой.

Например, список пар:

[[1,2],[2,3],[4,5],[6,7],[7,8],[9,4],[8,5]]

будет сгруппирован следующим образом:

[[1,2],[2,3]]

[[4,5],[6,7],[7,8],[9,4],[8,5]]

В первом кластере пары (1,2) и (2,3) имеют общую точку 2 и не имеют общих точек ни с какими парами вне кластера. Во втором кластере пара (4,5) имеет общие точки с (9,4) и (8,5), в то время как (8,5) имеет общую точку с (7,8), которая имеет общую точку с (6,7).

Данные изначально хранятся в массиве numpy, но формат вывода не слишком важен.

Мне нужно иметь доступ к данным, которые впоследствии составляют каждый отдельный кластер.

Answer 1

Использование networkx:

import networkx

edges = [[1, 2], [2, 3], [4, 5], [6, 7], [7, 8], [9, 4], [8, 5]]

graph = networkx.Graph(edges)
print(list(networkx.connected_components(graph)))

Выход:

[set([1, 2, 3]), set([4, 5, 6, 7, 8, 9])]