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

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

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

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

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

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

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

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

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

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

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

Худший ответ: В алгоритмах кластеризации использующих центроиды (да и вообще -  построенные на метрических мерах) как правило требуется задание количества кластеров, на которые вы желаете разбить свой набор данных в качестве входного параметра.   Измените приведенный выше вами  пример на такой - 1,2,4,11,12,18,19,20. И вот уже непонятно, тут три или четыре кластера?  Просто в одномерном случае мы можем  построить рисуночек и ответить на вопрос визуально. В многомерном так не получается, и определение "корректного" количества кластеров выливается в отдельную и весьма не простую задачу.  И точног, абсолютно обоснованного решения, кстати, может и не иметь. Можете поискать "метод колена при кластеризации".  Только зачем себе жизнь усложнять?

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