какой-нибудь простой способ кластеризации списка

otlichnica

Возник такой вопрос: у меня есть список в котором порядка 10000 элементов; каждый элемент ссылается на 5-20 других элементов; и есть подозрение, что все это может более-менее явно разделиться на несколько кластеров.
Можно ли это как-нибуть проверить машинными методами? Если с визуализацией, то вообще замечательно.

Damrad

найди мосты в своем графе. алгоритм известен
а вообще дай определение, что такое для тебя кластер?

otlichnica

если бы я мог построить граф и найти в нем мосты, я не спрашивал бы здесь, как это сделать
у меня сложно с определениями; например, если из этих десяти тысяч элементов каждая тысяча ссылается на элементы из самой себя (предположим, кроме 50 ссылок на элементы из остальных девяти тысяч это я назвал бы десятью кластерами. не знаю, как это формализовать

Aleks150284

) Построить квадратную матрицу 10000 на 10000
2) Наличие ссылки от объекта А до объекта Б закодировать как 1, отсутствие ссылки как 0.
...
5) Profit!

Damrad

) взять массив 1*10 000 и записать в него ссылки на элементы, пройдясь один раз по списку
2) Profit!

Aleks150284

ты получишь наборы односторонних ссылок от объекта А до Б,В,Г.
А собсна нужно еще установить, что связь двусторонняя, А ссылается на Б, Б ссылается на А - тогда буит кластер. + добавить сюда все односторонние ссылки от элементов кластера на всё остальное.

Vlad128

все эти шаги входят в "?"

Damrad

я написал только как построить граф. хотя даже этого вроде можно было бы и не делать
>ты получишь наборы односторонних ссылок от объекта А до Б,В,Г.
да. именно это и есть граф, заданные списками связных вершин
а определение кластера тут так и не прозвучало

Aleks150284

можно начать с такого определения: набор объектов, связанных попарно двусторонними связями. пример: А ссылается на Б и В;
Б ссылается на А и В; В ссылается на А и Б => имеем кластер А+Б+В.
Предположим, А,Б,В ссылаются также на Г, если при этом Г ссылается на А, Б, но не ссылается на В - то Г в кластер не попадает.

Vlad128

ну это ты написал определение клики в орграфе. Для поиска клик есть алгоритмы, да.
Но тут более автору надо высказаться. вот есть еще понятие "сильной связности" и можно разделить граф на сильно связные компоненты (есть эффективные алгоритмы). Тут уже надо знать специфику реальной задачи.

Vlad128

причем это еще такая халява (про клику): типа оставляем только тупо неориентированный граф, где дуга есть тогда и только тогда, когда в исходном были дуги в обоих направлениях и дальше алгоритм непомнюкого, но могу спросить, коллега недавно сталкивался.
Оставить комментарий
Имя или ник:
Комментарий: