Алгоритм кластеризации / разделения номеров

Question

У меня есть упорядоченный 1-D массив чисел.И длина массива, и значения чисел в массиве являются произвольными.Я хочу разделить массив на k разделов в соответствии с числовыми значениями, например, скажем, я хочу 4 раздела, распределенных как 30% / 30% / 20% / 20%, то есть верхние 30% -ые значения сначала, следующие 30%потом и т.д. я выбираю k и проценты распределения.Кроме того, если один и тот же номер появляется в массиве более одного раза, он не должен содержаться в двух разных разделах.Это означает, что приведенные выше проценты распределения являются не строгими, а скорее "целями" или "отправными точками", если хотите.

Например, допустим, мой массив равен ar = [1, 5, 5, 6, 7, 8, 8, 8, 8, 8].

Я выбираю k = 4 и числа должны быть распределены по разделам A, B, C и D с процентами pA = pB = pC = pD = 25%.

Учитывая ограничения, которые я дал выше, результирующие разделы должны быть:

A = [1] B = [5, 5] C = [6, 7] D = [8, 8, 8, 8, 8]

с результирующими (достигнутыми / исправленными) процентами pcA = 10%, pcB = 20%, pcC = 20%, pcD = 50%

Мне кажется, что мне нужен модифицированный алгоритм k-средних, потому что стандартный алгоритм не гарантирует соблюдениемои проценты и / или требование, чтобы одно и то же значение не могло быть в более чем одном кластере / разделе.

Итак, есть ли алгоритм для такого рода кластеризации?

Answer 1

Алгоритмы кластеризации используются на многомерных данных.Для одномерных данных вы должны просто использовать алгоритм сортировки.

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

Answer 2

Вот решение для динамического программирования, которое находит раздел, который минимизирует сумму квадратов ошибок в размерах частей.Итак, в вашем примере [1, 5, 5, 6, 7, 8, 8, 8, 8, 8] вам нужны части размера (2.5, 2.5, 2.5, 2.5), а результат, полученный этим кодом, равен (9,0 (1, 2, 2, 5)).Это означает, что выбранные разделы были размером 1, 2, 2 и 5, и общая ошибка составляет 9 = (2,5-1) ^ 2 + (2,5-2) ^ 2 + (2,5-2) ^ 2 + (2,5-5) ^ 2.

def partitions(a, i, sizes, cache):
    """Find a least-cost partition of a[i:].

    The ideal sizes of the partitions are stored in the tuple 'sizes'
    and cache is used to memoize previously calculated results.
    """
    key = (i, sizes)
    if key in cache: return cache[key]
    if len(sizes) == 1:
        segment = len(a) - i
        result = (segment - sizes[0]) ** 2, (segment,)
        cache[key] = result
        return result
    best_cost, best_partition = None, None
    for j in xrange(len(a) - i + 1):
        if 0 < j < len(a) - i and a[i + j - 1] == a[i + j]:
            # Avoid breaking a run of one number.
            continue
        bc, bp = partitions(a, i + j, sizes[1:], cache)
        c = (j - sizes[0]) ** 2 + bc
        if best_cost is None or c < best_cost:
            best_cost = c
            best_partition = (j,) + bp
    cache[key] = (best_cost, best_partition)
    return cache[key]


ar = [1, 5, 5, 6, 7, 8, 8, 8, 8, 8]
sizes = (len(ar) * 0.25,) * 4
print partitions(ar, 0, (2.5, 2.5, 2.5, 2.5), {})

Answer 3

Наивный подход будет выглядеть так:

Скажите, p1 ... pk - проценты для ваших разделов (p1 + ... + pk = 1)

Скажем, у вас есть N элементов в массиве

Начальные границы (их k + 1, включая конец массива, поскольку у вас есть k разделов): 0, p1 * N, (p1 + p2) * N, ..., N (будет какое-то округление).

Для перемещения границ вы смотрите на два элемента массива с каждой стороны границы (для границ k-1, которые вы можете перемещать). Если два элемента равны, вам нужно перейти к границе, либо слева направо, по крайней мере, пока не будет выполнено ограничение. Наивным подходом было бы начинать слева и делать минимальные корректировки (просто отрегулируйте ограничение в сторону, которая вызывает наименьшее движение, и не перемещайте границу дальше).

Этот алгоритм не охватывает все пространство разделов. Это просто дает вам одно решение. Чтобы найти лучшее решение, вам нужно выполнить поиск методом «грубой силы» по всему пространству разделов с некоторой обрезкой (например, динамическое программирование, где вы помните лучшее разделение для подмассива исходного массива).