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

Question

[xmoonlight]

Есть значения «весов» слов:
1, 3, 5, 6, 8, 8.7, 9.5, 10, 12.
И вот, как поделить их на кластеры КОРРЕКТНО?

Comments

[Wataru]

Вообще странный вопрос. Корректен любой способ, хоть всех в один кластер, хоть каждое слово - сам себе кластер.

С какой целью кластеризуете? Что это за значения? Что будете с кластерами делать потом?

[xmoonlight]

Илья Николаевский, Ну смотри.
Есть ряд 1,2,3,11,12,18,19,20. Тут сразу понятно, что 3 кластера (средний: 11,12).
Почему именно так - понятно?

[Wataru]

xmoonlight, Нет, непонятно. Может эти числа - это числовое обозначение цвета тома словаря, в котором это слово описывается. То, что зеленый выпал на 11, а красный на 12, и они как бы рядом - просто повезло.

Или вы делаете фильтр мата и эти числа - это какая-то мера матерности слова. В этом случае вам нужно именно 2 кластера.

Еще раз - без физического смысла величины и цели кластеризации - вопросы о корректности и оптимальности кластеризации не имеют смысла.

[xmoonlight]

Илья Николаевский, Относительная плотность в одномерном пространстве.
Центроиды в двумерном, знаешь же.
Вот это те же центроиды, но в одномерном.
Т.е. задача: найти границы этих центроидов на прямой.

[Wataru]

xmoonlight, Если ты уже знаешь ответ, то зачем задаешь вопрос?

[xmoonlight]

Илья Николаевский, Блин, да-я не знаю ответ!) В этом и есть ПРИКОЛ!

Answer 1

[Wataru]

Сначала вам нужно определиться, нужно ли вам фиксированное количество кластеров, или переменное. Затем вам нужно придумать метрику, которая говорила бы, какая кластеризация лучше другой.

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

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

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

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

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

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

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

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

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

Comments

[xmoonlight]

отношение максимального расстояния между соседними точками в любом кластере и минимального расстояния между кластерами.

минимального - это какого именно (как вычисленного) и между какими кластерами? (минимального расстояния между всеми уже полученными?...)

На приведённых данных: 1, 3, 5, 6, 8, 8.7, 9.5, 10, 12
можешь объяснить?

[Wataru]

xmoonlight, минимального между всеми парами.

Например в {1, 3, 5, 6, 8, 8.7, 9.5, 10, 12}, если разбить на {1, 3, 5, 6}, {8, 8.7, 9.5, 10}, {12}, то максимальное расстояние в кластере между соседними будет 2 (5-3), а расстояние между кластерами - тоже 2 (8-6 или 12-10). Итого метрика - 2/2=1.

Если разбить {1}, {3}, {5, 6}, {8, 8.7, 9.5, 10}, {12}, то максимальное расстояние между соседними будет 1 (это для каждой точки берем минимум по всем в том же кластере, а потом из этого всего берем максимум). А минимальное расстояние между кластерами будет 2 (тупо минимум по всем парам из разных кластеров). Итого метрика 1/2 лучше. Но тут если количество кластеров не ограничено, то можно вообще каждую точку отдельным кластером сделать и будет 0.

[xmoonlight]

Илья Николаевский, Не совсем тут понял: {8, 8.7, 9.5, 10} как тут получилось, что

максимальное расстояние между соседними будет 1

?

Например, мне нужно, чтобы в каждом "хорошем" кластере было бы по-возможности минимум 2 элемента. Одиночные элементы (=один кластер) допускаются, но не рассматриваются в метрике: т.е. "мусорные" точечные значения.
Количество кластеров и количество элементов в кластерах - неограничено.

Как сделать разбивку в этом случае и какой будет алгоритм разбивки?

[Wataru]

xmoonlight, максимальное расстояние между соседними берется по всем кластерам. Да, в {8, 8.7, 9.5, 10} расстояние 0.8, но есть же еще {5, 6}. Идея в этой метрике - мы смотрим как близко точки бывают в одном кластере и как близко бывают точке вне кластеров. Эти 2 множества должны быть хорошо разделены - в кластрерах точки рядышком, а сами кластеры далеко друг от друга.

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

[xmoonlight]

Илья Николаевский, как именно добиться такой разбивки {1}, {3}, {5, 6}, {8, 8.7, 9.5, 10}, {12} ?
Есть формула на это или брутом?

[Wataru]

xmoonlight, Можно жадно - не надо даже дихотомии и динамики. Отсортируйте все соседние расстояния и сливайте эти 2 соседних числа в один кластер, считая метрику.

В вашем примере сначала объединим 9.5 и 10 (разность 0.5), потом 8 и 8.7 (0.7), потом 8.7 и 9.5 (0.8), потом 5 и 6 (1). При слиянии смотрите отношение текущего расстояния и следующего и минимум его тут 1/2.

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

[xmoonlight]

Илья Николаевский, Ага! Приблизительно понял оба варианта. Буду кодить.
Спасибо большое!

[Wataru]

xmoonlight, Особенность этого варинта в безразмерности. Т.е. если вы растянете все числа так, что любое расстояние между соседними больше года или сожмете все точки в одну микросекунду, разбиение на кластеры будет точно таким же.

Если в вашей задаче это не вяжется, можно вместо просто после сортировки отсечь по какой-то выбранной вами константе.

[xmoonlight]

Илья Николаевский,

Особенность этого варинта в безразмерности. Т.е. если вы растянете все числа так, что любое расстояние между соседними больше года или сожмете все точки в одну микросекунду, разбиение на кластеры будет точно таким же.

Именно это и нужно!

Answer 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 кластера. Но это более менее согласуется с нашим интуитивным представлением. И главное, опровергнуть корректность именно такого количества кластеров - при заданном правиле - не удастся.

Comments

[xmoonlight]

Много слов, ответа - не увидел.
Косвенно упомянул ты:

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

Интересно: визуально - можем ответить, а математически - нет?!)

Вот, я писал выше:

Т.е. задача: найти границы этих центроидов на прямой.

[dmshar]

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

P.S. Кстати - кластеризация - это разбиение на несколько подмножеств ни количество которых, ни их описание заранее неизвестны. А классификация (построение классификатора) - это построение границ между заданными классами для последующего отнесения вновь поступившего объекта к определенному классу. Так что задачи как бы разные изначально.

[xmoonlight]

dmshar, я имел ввиду скопления вокруг центроидов, это понятно...

И вообще, решение задачи кластеризации вне семантики - очень сомнительная затея.

Ну, а толку? Ок, пишу.
Есть временная шкала и события во времени на ней.
Нужно поделить события на группы (или на временные отрезки) с наибольшей активностью событий.
Что поменялось?)

[xmoonlight]

dmshar,

P.S. Кстати - кластеризация - это разбиение на несколько подмножеств ни количество которых, ни их описание заранее неизвестны.

Интересует именно кластеризация.

[dmshar]

xmoonlight, Если этот временная шкала, а значения - это метки времени (например, номер секунды) их наступления, то это вообще другая - вполне известная - схема решения. Вот это и поменялось.
Речь идет об интенсивности. А интенсивность обычно измеряется количеством событий за ЗАДАННЫЙ ПРОМЕЖУТОК ВРЕМЕНИ. Т.е. тут первый семантический параметр - длинна вот этого самого промежутка. Таким образом вы переходите к новой шкале, по которой откладываются номер интервала, а значения - количество событий в нем случившихся. Граница кластера разумеется при таком подходе может быть проведена исключительно по границе интервала, а сам интервал является начальным элементом нового кластера, если интенсивность изменилась более, чем на заданную величину (и это второй семантический параметр).

То, что это именно семантические параметры и не могут быть иначе заданы при указанной постановке задачи становится понятным, если сравнить их значения - например - для потока событий прибытия кораблей в порт, и потока поступления пакетов по коммуникационной сети.

P.S. Задача относиться к теме "Теория потока однородных событий".

[xmoonlight]

dmshar,

А интенсивность обычно измеряется количеством событий за ЗАДАННЫЙ ПРОМЕЖУТОК ВРЕМЕНИ.

вот это самое и неизвестно.
Есть шкала 1,2,3,4,......11, 12
Есть на ней события (1 значение = 1 событие): 1, 3, 5, 6, 8, 8.7, 9.5, 10, 12
Не зная никаких промежутков времени нужно поделить на группы активности событий.

Интервала тут нет фиксирванного. Это "плавающий" параметр, который необходимо определить для того, чтобы корректно поделить.

[dmshar]

Пытаюсь понять.
У вас

Есть шкала 1,2,3,4,......11, 12
Есть на ней события (1 значение = 1 событие): 1, 3, 5, 6, 8, 8.7, 9.5, 10, 12

Другими словами, у вас таблица вида
1-1
2-3
3-5
4-6
5-8
6-8.7
7-9.5
8-10
9-12
Я правильно понял то, что вы написали?? Первый столбец - номер "секунды", на которой произошло количество событий указанных во втором столбце? И это самое "количество событий" может только возрастать?
Т.е так, как на картинке:


Или опять что-то не так?

[xmoonlight]

dmshar, нет.
Есть значения: 1, 3, 5, 6, 8, 8.7, 9.5, 10, 12 - это 9 событий на тайм-шкале.
Одно значение - это одно событие.
Нужно кластеризовать скопления событий на тайм-шкале.

[xmoonlight]

dmshar, Если будет иное решение, отличное от решения Илья Николаевский, готов также рассмотреть...

[dmshar]

xmoonlight,
"Отсортируйте все соседние расстояния и сливайте эти 2 соседних числа в один кластер, считая метрику.
...... Потом все точки, с расстоянием меньше этого числа - объединить в один кластер за еще один проход."
да нет, отличное решение. Про него я вам и писал по сути (с небольшими вариациями) в своих первых попытках ответа. Но я искренне рад, что Илье удалось донести эту мысль лучше и четче, чем мне.

[xmoonlight]

dmshar, Ок. Я просто не понял видимо... Спасибо!