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

Есть ли способ разделить набор данных, состоящий из пар 3D-точек (или просто их порядковых номеров) на связанные кластеры? То есть две пары (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, но формат вывода не слишком важен.

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


python cluster-analysis grouping connected-components
person Ben Bird    schedule 19.10.2017    source источник
comment
Не могу понять логику группировки. Если [1,2],[2,3] находится в кластере, почему [6,7],[7,8] также не находится в этом или его собственном кластере? Что вы имеете в виду под повторяющимися точками?   -  person roganjosh    schedule 19.10.2017
comment
@roganjosh Я думаю, что проблема может быть выражена как поиск связанных компонентов графа, где заданные пары являются ребрами, а числа - узлами. ОП, посмотри networkx.   -  person Alex Hall    schedule 19.10.2017
comment
@AlexHall этому объяснению, к сожалению, не помогает случайное редактирование для добавления комментариев (не OP или вас) к вопросу. Но даже в этом случае, должен ли я интерпретировать требуемый вывод как идентифицирующий разрыв в графе соединений и сбрасывать остаток в другой список? [6,7],[7,8] все еще подключен, но он отображается вместе с остальными.   -  person roganjosh    schedule 19.10.2017
comment
@roganjosh Я предполагаю, что OP хочет список кластеров. В данном случае их всего два, потому что 4,5,6,7,8,9 косвенно связаны.   -  person Alex Hall    schedule 19.10.2017
comment
@AlexHall Я считаю, что мне следует отменить редактирование, что вы думаете? Это не объяснение ОП, и на самом деле оно ничего мне не проясняет, но, возможно, я что-то упускаю, и это помогло вам понять ход ваших мыслей.   -  person roganjosh    schedule 19.10.2017
comment
@AlexHall Хорошо, ваш последний комментарий отлично прояснил это для меня.   -  person roganjosh    schedule 19.10.2017
comment
Пожалуйста, не просто повторяйте вопрос, когда он был закрыт, а вместо этого отредактируйте и улучшите существующий вопрос, а затем попросите открыть его снова. Кажется, вы просите транзитивное замыкание отношения (и связанных компонентов), а не кластеризацию - довольно фундаментальное математическое понятие. Использование таких библиотек, как networkx, кажется мне излишним.   -  person Has QUIT--Anony-Mousse    schedule 20.10.2017
comment
@ Anony-Mousse: Учитывая, что вопрос, который вы закрыли как обман, теперь удален, а на этот вопрос есть принятый ответ, я думаю, что этот вопрос, вероятно, следует открыть повторно. Я попытался отредактировать его для ясности.   -  person Ilmari Karonen    schedule 29.10.2017
comment
@IlmariKaronen Я не могу снова открыть в мобильном приложении, извините. Кажется, это только браузер. И я в основном читаю SO на своем телефоне, когда езжу на работу.   -  person Has QUIT--Anony-Mousse    schedule 08.11.2017
comment
@ Anony-Mousse: Хорошо, хорошо, тогда я проголосовал за его повторное открытие. (Я бы сообщил об этой отсутствующей функции в мета, но мобильное приложение в любом случае в основном заброшено.) Хотя в мобильном приложении есть есть опция «Открыть в браузере» (скрытая за ... Больше, по крайней мере на Android), вы знаете.   -  person Ilmari Karonen    schedule 08.11.2017

Ответы (1)


arrow_upward
2
arrow_downward

Используя 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])]
person Alex Hall    schedule 19.10.2017
comment
Только что наткнулся на networkx сам. Большое спасибо за ваш рабочий пример. - person Ben Bird; 20.10.2017