Группировка упорядоченного набора данных в минимальное количество кластеров

Question

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

Есть ли алгоритм, который делает это, минимизируя общее количество кластеров и сохраняя их вес как можно более равномерным?

например. список [(a, 5), (b, 1), (c, 2), (d, 5)], N = 6 следует преобразовать в [([a], 5), ([b, c], 3), ([d], 5)]

Answer 1

Поскольку набор данных упорядочен, один из возможных подходов состоит в том, чтобы назначить оценку «плохости» каждому возможному кластеру и использовать динамическую программу, напоминающую перенос слов Кнута (http://en.wikipedia.org/wiki/Word_wrap), чтобы минимизировать сумму оценок плохости , Функция плохости позволит вам изучить компромиссы между минимизацией количества кластеров (больший постоянный член) и их балансировкой (больший штраф за отклонение от среднего количества предметов).

Answer 2

Ваша проблема недостаточно указана.

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

Например, рассмотрим: [(a, 1), (b, 1), (c, 1), (d, 1), (e, 1)], N = 2

Наиболее равномерное распределение: [([a], 1), ([b], 1), ([c], 1), ([d], 1), ([e], 1)]

Но наименьшее количество кластеров составляет [([a, b], 2), ([c, d], 2), ([e], 1)]

Как алгоритм должен знать, какой из них (или какую кластеризацию между ними) вы хотите? Вам нужно найти способ количественно определить компромисс, который вы готовы принять между числом кластеров и равномерностью распределения.

Вы можете создать пример со сколь угодно большим расхождением между двумя возможностями, создав любой набор с 2k + 1 элементами и присвоив им все значение N / 2. Это приведет к тому, что наименьшее количество кластеров будет k + 1 кластеров (k из 2 элементов и 1 из 1) с разницей в весе N / 2 между самым большим и самым маленьким кластерами. И тогда наиболее равномерное распределение для этого набора будет 2k + 1 кластеров по 1 элементу в каждом, без разницы в весе.

Редактировать: Кроме того, сама "равномерность" не является четко определенной идеей. Вы хотите минимизировать наибольшую абсолютную разницу в весах между кластерами, или среднюю разницу в весах, или срединную разницу в весах, или стандартное отклонение в весах?