Условная выборка двоичных векторов (?)

Ответ 1

Мое конкретное, практичное (если гарантия приближения сработает для вас) предложение было бы применить метод максимальной энтропии (в главе 7 книги Бойда и Ванденберге "Выпуклая оптимизация"; вы можете найти несколько реализаций с вашей любимой поисковой системой), чтобы найти максимальное распределение вероятности энтропии по индексам строк, такое, что (1) ни один индекс строки не является более вероятным, чем 1/500 (2) ожидаемое значение выбранного вектора строки составляет 1/500 от предварительно определенного распределения. Учитывая это распределение, выберите каждую строку независимо с вероятностью, в 500 раз превышающей вероятность ее распределения, что даст вам в среднем 500 строк. Если вам нужно ровно 500, повторяйте, пока не получите ровно 500 (не следует делать слишком много попыток из-за ограничений концентрации).

Ответ 2

Сначала я сделаю некоторые предположения относительно этой проблемы:

• Независимо от того, является ли сумма столбца выбранного решения над или под целевым значением, она весит одинаково.
• Сумма первого, второго и третьего столбца одинаково взвешивается в решении (т.е. если есть решение, в то время как сумма первого столбца не равна 1, а в другом, где сумма третьего столбца не равна 1, решение одинаково хорошо).

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

Однако обе эти проблемы являются NP-Complete. Это означает, что нет алгоритма полиномиального времени, который мог бы их решить, хотя это легко проверить.

Если бы я был вами, два наиболее эффективных решения этой проблемы - linear programming и machine learning.

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

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

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

Ответ 3

Это определенно может быть смоделировано как (целочисленная!) Линейная программа (многие проблемы могут). Получив его, вы можете использовать такую программу, как lpsolve, чтобы решить ее.

Мы моделируем vector i is selected как x_i, который может быть 0 или 1.

Тогда для каждого столбца c у нас есть ограничение:

sum of all (x_i * value of i in column c) = target for column c

Если взять ваш пример, в lp_solve это может выглядеть так:

min: ;
+x1 +x4 +x5 >= 2;
+x1 +x4 +x5 <= 2;
+x1 +x2 +x3 +x4 <= 1;
+x1 +x2 +x3 +x4 >= 1;
+x3 <= 0;
+x3 >= 0;
bin x1, x2, x3, x4, x5;

Ответ 4

Если вас устраивает эвристический подход к поиску, вот один.

Перейдите по списку и найдите минимальную квадратовую сумму разности между цифрами между каждой строкой битов и целью. Например, если мы ищем 2, 1, 0, и мы набираем 0, 1, 0, мы сделали бы это следующим образом:

Возьмите разницу в цифру: 2, 0, 1

Возведите в квадрат разумную разницу: 4, 0, 1

Сумма: 5

Как примечание, возведение в квадрат разницы при оценке является распространенным методом при эвристическом поиске. В вашем случае это имеет смысл, потому что битовые строки, в которых первая цифра равна 1, намного интереснее для нас. В вашем случае этот простой алгоритм выберет сначала 110, а затем 100, что будет лучшим решением.

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

Ответ 5

У вас есть заданный целевой двоичный вектор. Вы хотите выбрать векторы M из N, которые имеют ближайшую сумму к цели. Допустим, вы используете евклидово расстояние, чтобы измерить, лучше ли выбор, чем другой.

Если вы хотите получить точную сумму, взгляните на проблему k-суммы, которая является обобщением задачи 3SUM. Эта проблема сложнее, чем проблема суммы подмножеств, потому что вы хотите, чтобы точное число элементов было добавлено к целевому значению. есть решение в O(N^(M/2)). lg N), но это означает, что в вашем случае более 2000 ^ 250 * 7.6> 10 ^ 826 операций (в благоприятном случае, когда операции с векторами имеют стоимость 1).

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

Вот подход к альпинизму :

1. отсортировать векторы по количеству единиц: сначала 111..., затем 000...;
2. используйте алгоритм приближения полиномиального времени для суммы подмножества;
3. у вас есть приблизительное решение с элементами K. Из-за порядка элементов (большие идут первыми), K должно быть как можно меньше:
   • если K> = M, вы берете M первые векторы решения, и это, вероятно, почти лучшее, что вы можете сделать.
   • если K & lt; M, вы можете удалить первый вектор и попытаться заменить его двумя или более векторами из остальных векторов N, используя ту же технику, пока у вас не появятся векторы M. Подводя итог: разделите большие векторы на более мелкие, пока не достигнете правильного числа векторов.

Вот подтверждение концепции с числами в Python:

import random

def distance(x, y):
    return abs(x-y)

def show(ls):
    if len(ls) < 10:
        return str(ls)
    else:
        return ", ".join(map(str, ls[:5]+("...",)+ls[-5:]))

def find(is_xs, target):
    # see https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution
    S = [(0, ())] # we store indices along with values to get the path
    for i, x in is_xs:
        T = [(x + t, js + (i,)) for t, js in S]
        U = sorted(S + T)
        y, ks = U[0]
        S = [(y, ks)]

        for z, ls in U:
            if z == target: # use the euclidean distance here if you want an approximation
                return ls

            if z != y and z < target:
                y, ks = z, ls
                S.append((z, ls))

    ls = S[-1][1] # take the closest element to target
    return ls

N = 2000
M = 500
target = 1000

xs = [random.randint(0, 10) for _ in range(N)]
print ("Take {} numbers out of {} to make a sum of {}", M, xs, target)

xs = sorted(xs, reverse = True)
is_xs = list(enumerate(xs))

print ("Sorted numbers: {}".format(show(tuple(is_xs))))

ls = find(is_xs, target)
print("FIRST TRY: {} elements ({}) -> {}".format(len(ls), show(ls), sum(x for i, x in is_xs if i in ls)))

splits = 0
while len(ls) < M:
    first_x = xs[ls[0]]

    js_ys = [(i, x) for i, x in is_xs if i not in ls and x != first_x]
    replace = find(js_ys, first_x)
    splits += 1
    if len(replace) < 2 or len(replace) + len(ls) - 1 > M or sum(xs[i] for i in replace) != first_x:
        print("Give up: can't replace {}.\nAdd the lowest elements.")
        ls += tuple([i for i, x in is_xs if i not in ls][len(ls)-M:])
        break

    print ("Replace {} (={}) by {} (={})".format(ls[:1], first_x, replace, sum(xs[i] for i in replace)))
    ls = tuple(sorted(ls[1:] + replace)) # use a heap?
    print("{} elements ({}) -> {}".format(len(ls), show(ls), sum(x for i, x in is_xs if i in ls)))

print("AFTER {} splits, {} -> {}".format(splits, ls, sum(x for i, x in is_xs if i in ls)))

Результат явно не гарантирован, чтобы быть оптимальным.

Примечания:

• Сложность: find имеет полиномиальную временную сложность (см. страницу Википедии) и вызывается не более M^2 раз, поэтому сложность остается полиномиальной. На практике этот процесс достаточно быстрый (разделенные вызовы имеют небольшую цель).
• Векторы: чтобы обеспечить достижение цели с минимумом элементов, вы можете улучшить порядок элементов. Ваша цель - (t_1, ..., t_c): если вы сортируете t_j по максимуму и минимуму, сначала вы получаете столбцы с большим количеством импортеров. Вы можете отсортировать векторы: по номеру 1, а затем по наличию 1 в наиболее важных столбцах. Например. target = 4 8 6 => 1 1 1 > 0 1 1 > 1 1 0 > 1 0 1 > 0 1 0 > 0 0 1 > 1 0 0 > 0 0 0.
• find (Векторы), если текущая сумма превышает цель во всех столбцах, значит, вы не подключаетесь к цели (любой вектор, добавленный к текущей сумме, приведет вас дальше от цели): не добавляйте сумма в S (случай z >= target для чисел).

Ответ 6

Я предлагаю простой специальный алгоритм, который я не могу классифицировать, но который, по-видимому, работает относительно хорошо для входных векторов, которые имеют распределение 1 с, "похожее" на вектор целевой суммы, и, вероятно, также для всех "хороших" входные векторы, как определено в вашем комментарии. Решение не точное, но приближение кажется хорошим.

Расстояние между вектором суммы выходных векторов и целевым вектором считается евклидовым. Чтобы свести к минимуму это означает минимизацию суммы разностей квадратов от вектора суммы и целевого вектора (квадратный корень не нужен, потому что он монотонный). Алгоритм не гарантирует выдачу образца, который минимизирует расстояние от цели, но в любом случае делает серьезную попытку сделать это, всегда двигаясь в каком-то локально оптимальном направлении.

Алгоритм можно разбить на 3 части.

Прежде всего, первые M возможных выходных векторов из N входных векторов (например, N = 2000, M = 500) помещаются в список, а оставшиеся векторы помещаются в другой.

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

Затем, в качестве последней фазы, выполняются "оптимальные" перестановки, снова останавливаясь на отсутствии уменьшения расстояния или достижения максимального количества итераций. Оптимальные перестановки приводят к максимальному уменьшению расстояния, не требуя удаления первого вектора, который был бы оптимальным сам по себе. Чтобы найти оптимальный обмен, необходимо проверить все пары векторов. Эта фаза намного дороже, будучи O (M (N-M)), в то время как предыдущая "приблизительная" фаза - O (M+ (N-M)) = O (N). К счастью, при переходе на этот этап большая часть работы уже была выполнена на предыдущем этапе.

from typing import List, Tuple

def get_sample(vects: List[Tuple[int]], target: Tuple[int], n_out: int,
               max_approx_swaps: int = None, max_optimal_swaps: int = None,
               verbose: bool = False) -> List[Tuple[int]]:
    """
    Get a sample of the input vectors having a sum close to the target vector.

    Closeness is measured in Euclidean metrics. The output is not guaranteed to be
    optimal (minimum square distance from target), but a serious attempt is made.
    The max_* parameters can be used to avoid too long execution times,
    tune them to your needs by setting verbose to True, or leave them None (∞).
    :param vects: the list of vectors (tuples) with the same number of "columns"
    :param target: the target vector, with the same number of "columns"
    :param n_out: the requested sample size
    :param max_approx_swaps: the max number of approximately optimal vector swaps,
        None means unlimited (default: None)
    :param max_optimal_swaps: the max number of optimal vector swaps,
        None means unlimited (default: None)
    :param verbose: print some info if True (default: False)
    :return: the sample of n_out vectors having a sum close to the target vector
    """

    def square_distance(v1, v2):
        return sum((e1 - e2) ** 2 for e1, e2 in zip(v1, v2))

    n_vec = len(vects)
    assert n_vec > 0
    assert n_out > 0
    n_rem = n_vec - n_out
    assert n_rem > 0
    output = vects[:n_out]
    remain = vects[n_out:]
    n_col = len(vects[0])
    assert n_col == len(target) > 0
    sumvect = (0,) * n_col
    for outvect in output:
        sumvect = tuple(map(int.__add__, sumvect, outvect))
    sqdist = square_distance(sumvect, target)
    if verbose:
        print(f"sqdist = {sqdist:4} after"
              f" picking the first {n_out} vectors out of {n_vec}")

    if max_approx_swaps is None:
        max_approx_swaps = sqdist
    n_approx_swaps = 0
    while sqdist and n_approx_swaps < max_approx_swaps:
        # find the best vect to subtract (the square distance MAY increase)
        sqdist_0 = None
        index_0 = None
        sumvect_0 = None
        for index in range(n_out):
            tmp_sumvect = tuple(map(int.__sub__, sumvect, output[index]))
            tmp_sqdist = square_distance(tmp_sumvect, target)
            if sqdist_0 is None or sqdist_0 > tmp_sqdist:
                sqdist_0 = tmp_sqdist
                index_0 = index
                sumvect_0 = tmp_sumvect
        # find the best vect to add,
        # but only if there is a net decrease of the square distance
        sqdist_1 = sqdist
        index_1 = None
        sumvect_1 = None
        for index in range(n_rem):
            tmp_sumvect = tuple(map(int.__add__, sumvect_0, remain[index]))
            tmp_sqdist = square_distance(tmp_sumvect, target)
            if sqdist_1 > tmp_sqdist:
                sqdist_1 = tmp_sqdist
                index_1 = index
                sumvect_1 = tmp_sumvect
        if sumvect_1:
            tmp = output[index_0]
            output[index_0] = remain[index_1]
            remain[index_1] = tmp
            sqdist = sqdist_1
            sumvect = sumvect_1
            n_approx_swaps += 1
        else:
            break
    if verbose:
        print(f"sqdist = {sqdist:4} after {n_approx_swaps}"
              f" approximately optimal swap{'s'[n_approx_swaps == 1:]}")

    diffvect = tuple(map(int.__sub__, sumvect, target))
    if max_optimal_swaps is None:
        max_optimal_swaps = sqdist
    n_optimal_swaps = 0
    while sqdist and n_optimal_swaps < max_optimal_swaps:
        # find the best pair to swap,
        # but only if the square distance decreases
        best_sqdist = sqdist
        best_diffvect = diffvect
        best_pair = None
        for i0 in range(M):
            tmp_diffvect = tuple(map(int.__sub__, diffvect, output[i0]))
            for i1 in range(n_rem):
                new_diffvect = tuple(map(int.__add__, tmp_diffvect, remain[i1]))
                new_sqdist = sum(d * d for d in new_diffvect)
                if best_sqdist > new_sqdist:
                    best_sqdist = new_sqdist
                    best_diffvect = new_diffvect
                    best_pair = (i0, i1)
        if best_pair:
            tmp = output[best_pair[0]]
            output[best_pair[0]] = remain[best_pair[1]]
            remain[best_pair[1]] = tmp
            sqdist = best_sqdist
            diffvect = best_diffvect
            n_optimal_swaps += 1
        else:
            break
    if verbose:
        print(f"sqdist = {sqdist:4} after {n_optimal_swaps}"
              f" optimal swap{'s'[n_optimal_swaps == 1:]}")

    return output


from random import randrange

C = 30    # number of columns
N = 2000  # total number of vectors
M = 500   # number of output vectors
F = 0.9   # fill factor of the target sum vector
T = int(M * F)  # maximum value + 1 that can be appear in the target sum vector
A = 10000 # maximum number of approximately optimal swaps, may be None (∞)
B = 10    # maximum number of optimal swaps, may be None (unlimited)

target = tuple(randrange(T) for _ in range(C))
vects = [tuple(int(randrange(M) < t) for t in target) for _ in range(N)]
sample = get_sample(vects, target, M, A, B, True)

Типичный вывод:

sqdist = 2639 after picking the first 500 vectors out of 2000
sqdist =    9 after 27 approximately optimal swaps
sqdist =    1 after 4 optimal swaps

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

P.P.S.: Время выполнения с вашими данными, вероятно, приемлемо для стандартного CPython, но улучшается (например, за пару секунд, почти в 10 раз) с PyPy. Чтобы обрабатывать большие наборы данных, алгоритм должен быть переведен на C или другой язык, что не должно быть сложным.