идеи для алгоритма? случайная сортировка списка с акцентом на разнообразие

Интересная проблема. Поскольку вам нужна примерно половина списка, как насчет этого: -

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

:петля

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

Если новый элемент увеличивает «энтропию» числа уникальных атрибутов в гистограммах, сохраните его и обновите гистограммы, чтобы отразить только что внесенное изменение.

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

Я не знаю (и надеюсь, что кто-нибудь ответит). Вот что приходит в голову: составьте распределение для MCMC, уделяя наибольшее внимание подмножествам с 'разнообразие'.

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

по моему мнению

Finding variety is difficult but generating it is easy.

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

Если таблица отсортирована, поиск также становится легким.

Пример кода на Python:

d = {}
d[('a',0,'A')]=0
d[('a',1,'A')]=1
d[('a',0,'A')]=2
d[('b',1,'B')]=3
d[('b',0,'C')]=4
d[('c',1,'C')]=5
d[('c',0,'D')]=6
d[('a',0,'A')]=7

print d

attr1 = ['a','b','c']
attr2 = [0,1]
attr3 = ['A','B','C','D']

# no of items in
# attr2 < attr1 < attr3

# ;) reason for strange nesting of loops

for z in attr3:
    for x in attr1:
        for y in attr2:
            k = (x,y,z)
            if d.has_key(k):
                print '%s->%s'%(k,d[k])
            else:
                print k

Вывод:

('a', 0, 'A')->7
('a', 1, 'A')->1
('b', 0, 'A')
('b', 1, 'A')
('c', 0, 'A')
('c', 1, 'A')
('a', 0, 'B')
('a', 1, 'B')
('b', 0, 'B')
('b', 1, 'B')->3
('c', 0, 'B')
('c', 1, 'B')
('a', 0, 'C')
('a', 1, 'C')
('b', 0, 'C')->4
('b', 1, 'C')
('c', 0, 'C')
('c', 1, 'C')->5
('a', 0, 'D')
('a', 1, 'D')
('b', 0, 'D')
('b', 1, 'D')
('c', 0, 'D')->6
('c', 1, 'D')

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

Предположим, что ATTR1, ATTR2 и ATTR3 являются независимыми случайными величинами (по однородному случайному элементу). (Если ATTR1, ATTR2 и ATTR3 независимы только приблизительно, тогда эта выборка должна быть приблизительно однородной по каждому атрибуту.) Чтобы выбрать один элемент (VAL1, VAL2, VAL3), атрибуты которого равномерно распределены, выберите VAL1 равномерно случайным образом из набора значений для ATTR1, выберите VAL2 равномерно случайным образом из набора значений для ATTR2 по элементам с ATTR1 = VAL1, выберите VAL3 равномерно случайным образом из набора значений для ATTR3 по элементам с ATTR1 = VAL1 и ATTR2 = VAL2.

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

ID    ATTR1 ATTR2 ATTR3
1     a     c     e
2     a     c     f
3     a     d     e
4     a     d     f
5     b     c     e
6     b     c     f
7     b     d     e
8     b     d     f
9     a     c     e

тогда дерево в нотации объекта JavaScript

{"a": {"c": {"e": [1, 9], "f": [2]},
       "d": {"e": [3], "f": [4]}},
 "b": {"c": {"e": [5], "f": [6]},
       "d": {"e": [7], "f": [8]}}}

Удаление выполняется рекурсивно. Если мы выбираем идентификатор 4, мы удаляем его из списка на уровне листьев. Этот список очищается, поэтому мы удаляем запись «f»: [] из дерева [«a»] [«d»]. Если мы теперь удаляем 3, то мы удаляем 3 из его списка, который очищается, поэтому мы удаляем запись «e»: [] из дерева [«a»] [«d»], которая очищает дерево [«a»] [ «d»], поэтому мы удаляем его по очереди. В хорошей реализации каждый элемент должен занимать время O (количество атрибутов).

РЕДАКТИРОВАТЬ: для повторного использования повторно вставьте элементы в дерево после сбора всего образца. Это не влияет на асимптотическое время работы.

Идея №2.

Вычислите гистограммы для каждого атрибута в исходной таблице.

Для каждого элемента вычислите его показатель уникальности = p (ATTR1) x p (ATTR2) x p (ATTR3) (умножьте вероятности для каждого атрибута, который он имеет).

Сортировать по уникальности.

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

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

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

Взяв ваш пример, присвойте каждому возможному «State» числовое значение (скажем, от 1 до 9). Сделайте то же самое для других атрибутов.

Теперь, предполагая, что у вас не более 10 возможных значений для каждого атрибута, умножьте значения ATTR3 на 100, ATTR2 на 1000, ATTR1 на 10000. Сложите результаты, и вы получите то, что может напоминать неопределенный хэш пункт. Что-то типа

10 000 * | ATTR1 | + 1000 * | ATTR2 | + 100 * | ATTR3 |

преимущество здесь в том, что вы знаете, что значения от 10000 до 19000 имеют одинаковое значение «Состояние»; другими словами, первая цифра представляет ATTR1. То же самое для ATTR2 и других атрибутов.

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

Пример: если ваши конечные значения

A: 15,700 = 10,000 * 1 + 1,000 * 5 + 100 * 7 B: 13,400 = 10,000 * 1 + 1,000 * 3 + 100 * 4 C: 13,200 = ... D: 12,300 E: 11,400 F: 10,900

вы знаете, что все ваши значения имеют одинаковый ATTR1; 2 имеют одинаковый ATTR2 (то есть B и C); и 2 имеют одинаковый ATTR3 (B, E).

Это, конечно, при условии, что я правильно понял, что вы хотите сделать. В конце концов, суббота, ночь.

ps: да, я мог бы использовать «10» в качестве первого множителя, но пример был бы более запутанным; и да, это явно наивный пример, и здесь есть много возможных оптимизаций, которые оставлены читателю в качестве упражнения.

Это очень интересная проблема, для которой я вижу ряд приложений. В частности, для тестирования программного обеспечения: вы получаете много транзакций «основного потока», но для проверки его работы требуется только одна, и при выборе вы бы предпочли получить чрезвычайно разнообразную выборку.

Я не думаю, что вам действительно нужна структура гистограммы или, по крайней мере, только двоичная (отсутствует / присутствует).

{ ATTR1: [val1, val2], ATTR2: [i,j,k], ATTR3: [1,2,3] }

Фактически это используется для создания списка предикатов:

Predicates = [ lambda x: x.attr1 == val1, lambda x: x.attr1 == val2,
               lambda x: x.attr2 == i, ...]

Этот список будет содержать, скажем, N элементов.

Теперь вы хотите выбрать K элемента из этого списка. Если K меньше N, это нормально, в противном случае мы продублируем список i раз, так что K <= N*i и с i минимальным, конечно, так i = ceil(K/N) (обратите внимание, что это работает, хотя если K <= N, с i == 1).

i = ceil(K/N)
Predz = Predicates * i # python's wonderful

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

Два замечания:

• если K > N вы можете захотеть выбрать i-1 раз каждый предикат, а затем случайным образом выбрать из списка предикатов только для завершения вашего выбора. Таким образом обеспечивается избыточное представительство даже наименее распространенных элементов.
• атрибуты полностью некоррелированы таким образом, вы можете выбрать шаблоны, поскольку вы никогда не сможете получить кортеж (1,2,3), выбрав третий элемент, равный 3, поэтому, возможно, усовершенствованием будет группировка некоторых связанных атрибутов вместе, хотя это, вероятно, увеличится количество сгенерированных предикатов
• по соображениям эффективности вы должны иметь таблицу по категории предикатов, если вы хотите иметь эффективный выбор.