Выделить скопления в общей массе точек в многомерном пространстве, найти отдельные, найти границы, различия
На примере двумерного думать проще — скопления точек видны взгляду, надо придумать как их сможет видеть алгоритм
А потом экстраполировать алгоритм на многомерное.
Если пространство анизатропно, можно выровнять всю массу по осям. Если нет — надо понять занимаемый диапазон по каждой оси. Дальнейшие расчеты можно вести не в исходных значениях, а в процентах от занимаемого диапазона.
Интересно, как оно будет по оси со всего четырьмя значениями?.. По ним сразу кластеризуется? Или такие оси стоит просто исключать из рассмотрения? Наверное, как-то зависит от задачи.
Глаз в двумерном поле зрения легко выхватывает скопления и промежутки при обзоре всего скопления. Чтоб промежутки были заметны, они должны быть вдоль каждой оси больше -среднего- какого-то расстояния между ближайшими точками по этой оси. Или больше нескольких процентов общего размера массы точек по оси. Найти размер промежутков — тоже интересная задача. Возможно, нужно искать пики количества соседей на том или ином расстоянии, и выбирать промежутки между пиками.
Более тонкие промежутки либо не интересны, либо интересны в рамках деления отдельных скоплений на скопления внутри них. Скопления вообще могут быть иерархично устроены.
Чтоб ближайшие искать не полным перебором, можно построить индексы по каждой оси, и в них видеть ближайших соседей.
Перебирать соседей по индексам можно не в один заход, постепенно увеличивая радиус осмотра для сбора статистики расстояний или ограничиваясь радиусом для сбора соседей.
Имея понимание о размере промежутков, можно начать с произвольной точки, наречь её членом нового скопления, и помечать относящимся к нему же всех соседей, взятых из индексов в диапазоне до промежутка. Если согласиться на квадрат вместо круга (если размер промежутка позволяет), то можно лишь проверять присутствие точки одновременно во всех индексах, не считая расстояние (корень суммы квадратов). Если столкнулись с точкой другого скопления, записать что эти два скопления на самом деле одно. Потом можно слить.
Возможны скопления большие, продолговатые, гнутые, извилистые. Возможны в границах щели (фьёрды), и эти особенности тоже могут быть интересны. Вообще, выделить границы задача интересная.
Nashev
commented
6 years ago
Выделить скопления в общей массе точек в многомерном пространстве, найти отдельные, найти границы, различия
На примере двумерного думать проще — скопления точек видны взгляду, надо придумать как их сможет видеть алгоритм
А потом экстраполировать алгоритм на многомерное.
Если пространство анизатропно, можно выровнять всю массу по осям. Если нет — надо понять занимаемый диапазон по каждой оси. Дальнейшие расчеты можно вести не в исходных значениях, а в процентах от занимаемого диапазона.
Интересно, как оно будет по оси со всего четырьмя значениями?.. По ним сразу кластеризуется? Или такие оси стоит просто исключать из рассмотрения? Наверное, как-то зависит от задачи.
Глаз в двумерном поле зрения легко выхватывает скопления и промежутки при обзоре всего скопления. Чтоб промежутки были заметны, они должны быть вдоль каждой оси больше -среднего- какого-то расстояния между ближайшими точками по этой оси. Или больше нескольких процентов общего размера массы точек по оси. Найти размер промежутков — тоже интересная задача. Возможно, нужно искать пики количества соседей на том или ином расстоянии, и выбирать промежутки между пиками.
Более тонкие промежутки либо не интересны, либо интересны в рамках деления отдельных скоплений на скопления внутри них. Скопления вообще могут быть иерархично устроены.
Чтоб ближайшие искать не полным перебором, можно построить индексы по каждой оси, и в них видеть ближайших соседей.
Перебирать соседей по индексам можно не в один заход, постепенно увеличивая радиус осмотра для сбора статистики расстояний или ограничиваясь радиусом для сбора соседей.
Имея понимание о размере промежутков, можно начать с произвольной точки, наречь её членом нового скопления, и помечать относящимся к нему же всех соседей, взятых из индексов в диапазоне до промежутка. Если согласиться на квадрат вместо круга (если размер промежутка позволяет), то можно лишь проверять присутствие точки одновременно во всех индексах, не считая расстояние (корень суммы квадратов). Если столкнулись с точкой другого скопления, записать что эти два скопления на самом деле одно. Потом можно слить.
Возможны скопления большие, продолговатые, гнутые, извилистые. Возможны в границах щели (фьёрды), и эти особенности тоже могут быть интересны. Вообще, выделить границы задача интересная.