xmoonlight
@xmoonlight
https://sitecoder.blogspot.com

Как разделить «веса» на кластеры КОРРЕКТНО?

Есть значения «весов» слов:
1, 3, 5, 6, 8, 8.7, 9.5, 10, 12.
И вот, как поделить их на кластеры КОРРЕКТНО?
  • Вопрос задан
  • 159 просмотров
Решения вопроса 2
@dmshar
В алгоритмах кластеризации использующих центроиды (да и вообще - построенные на метрических мерах) как правило требуется задание количества кластеров, на которые вы желаете разбить свой набор данных в качестве входного параметра. Измените приведенный выше вами пример на такой - 1,2,4,11,12,18,19,20. И вот уже непонятно, тут три или четыре кластера? Просто в одномерном случае мы можем построить рисуночек и ответить на вопрос визуально. В многомерном так не получается, и определение "корректного" количества кластеров выливается в отдельную и весьма не простую задачу. И точног, абсолютно обоснованного решения, кстати, может и не иметь. Можете поискать "метод колена при кластеризации". Только зачем себе жизнь усложнять?

Если же исходить из того, что данные к вам поступают, например, потоком и их надо бить на некоторые кластеры, то я бы вообще - в одномерном случае!!! - задал правило и не мучился бы. Например, в один кластер попадают точки, отстающие от ближайшей точки кластера не далее чем на 1. Или на 2, или на 3 или вообще на 100 - но это как раз и будет тем семантически зависимым параметром вашего алгоритма. При этом надо признать, что количество кластеров может изменяться. Причем и увеличиваться и уменьшаться. Например, в потоке 8,5,4,1,6,7 - у вас последовательно будет 1,2,2,3,3,2 кластера. Но это более менее согласуется с нашим интуитивным представлением. И главное, опровергнуть корректность именно такого количества кластеров - при заданном правиле - не удастся.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Сначала вам нужно определиться, нужно ли вам фиксированное количество кластеров, или переменное. Затем вам нужно придумать метрику, которая говорила бы, какая кластеризация лучше другой.

Варианты метрик:

- Для каждого кластера считается наибольшее расстояние между двумя элементами, и это суммируется по всем кластерам. Можно суммировать квадраты этих расстояний, тогда будут наказываться кластеризации с очень большими кластерами.
- отношение максимального расстояния между соседними точками в любом кластере и минимального расстояния между кластерами.
- Это может быть и качественная метрика. Любая кластеризация, где расстояние между соседними точками в кластере меньше расстояния между кластерами считается хорошей. Это частный случай предыдущей метрики, но вам достаточно искать не минимум, а любое значение <1.

Некоторые метрики имеют смысл только при фиксированном количестве кластеров, как первая.

Разные метрики дают разные кластеризации и все они в каком-то смысле хорошие. Что именно подходит вам в вашей задаче - можете судить только вы эмпирически.

На линии можно довольно быстро это оптимизировать. Например, третья метрика вообще решается жадностью - сортируем все отрезки между соседними точками по длине и жадно сливаем кластера пока их не будет требуемое количество.

Многие метрики, если они аддитивны как первая, можно считать динамическим программированием: f(i,k) - значение метрики если мы разбили первые i точек на k кластеров.

Для других, как для второй придется смешивать дихотомию по ответу и динамическое программирование (бинарный поиск по ответу, далее проверяем, а есть ли разбиение с такой или лучшей метрикой. Внутри динамика - минимально достижимое значение максимума между соседними точками в классе среди первых i при разбиении на k кластеров. При переборе последнего кластера нужно смотреть, чтобы расстояние между ним и соседними не превышало ответа динамики деленного на перебираемый коэффициент).

Еще можно применять стандартные методы без оптимизаций опирающихся на то, что у нас одномерное пространство - тупо применяйте метод k ближайших соседей, например.

Вам придется попробовать разные методы на ваших реальных данных и выбрать то, что лучше всего работает.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы