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

Question

У меня есть таблица предметов с [ID, ATTR1, ATTR2, ATTR3], Я хотел бы выбрать около половины элементов, но постараюсь получить случайный набор результатов, который НЕ кластеризован. Другими словами, существует довольно равномерный разброс значений ATTR1, ATTR2 и ATTR3. Это НЕ обязательно представляет данные как единое целое, другими словами, общая таблица может быть в основном сконцентрирована на определенных значениях атрибутов, но я бы хотел выбрать подмножество с большим разнообразием. Атрибуты не связаны между собой, поэтому между ATTR1 и ATTR2 на самом деле нет корреляции.

В качестве примера представим ATTR1 = "State". Мне бы хотелось, чтобы каждая позиция в моем подмножестве находилась в другом состоянии, даже если во всем наборе большая часть моих данных сконцентрирована в нескольких состояниях. И для того, чтобы это было одновременно верно и для других 2 атрибутов. (Я понимаю, что некоторые таблицы могут не сделать это возможным, но есть достаточно данных, которые вряд ли будут иметь решение)

Есть идеи для эффективного алгоритма? Спасибо! Я даже не знаю, как искать это:)

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

Answer 1

Интересная проблема. Так как вы хотите около половины списка, как об этом:-

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

: петля

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

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

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

Answer 2

По моему мнению

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')

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

Answer 3

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

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

10000 * |ATTR1| + 1000 * |ATTR2| + 100 * |ATTR3|

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

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

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

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" в качестве первого множителя, но пример был бы более грязным; и да, это явно наивный пример, и здесь есть много возможных оптимизаций, которые оставляют читателю в качестве упражнения

Answer 4

Предположим, что 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(количество атрибутов).

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

Answer 5

Идея № 2.

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

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

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

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

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

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

Answer 6

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

Answer 7

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

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

{ 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поэтому, возможно, было бы лучше сгруппировать некоторые связанные атрибуты вместе, хотя это, вероятно, увеличило бы количество сгенерированных предикатов.
• по соображениям эффективности, вы должны иметь таблицу по категориям предикатов, если вы хотите иметь эффективный выбор.

Answer 8

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