MATLAB / General CS: выборка без замены из нескольких наборов (+ отслеживание случаев без выборки) - PullRequest
Новая
       10

MATLAB / General CS: выборка без замены из нескольких наборов (+ отслеживание случаев без выборки)

1 голос
/ 16 марта 2011

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

Ситуация следующая:

У меня есть конечное число наборов ( A , B , C ), каждый с конечным, но, возможно, различным количеством элементов ( a1 , a2 ... a8 , b1, b2 ... b10 , c1, c2 ... c25 ). У меня также есть вектор вероятностей для каждого набора, который перечисляет вероятность для каждого элемента в этом наборе (то есть для набора A , P_A = [p_a1 p_a2 ... p_a8] где sum (P_A) = 1) , Обычно я использую их для создания функции генерации вероятности для каждого набора, которому дано одинаковое число от 0 до 1, который может выплевывать один из элементов этого набора (то есть функция P_A (u), которая при u = 0,25, будет выберите a2 ).

Я ищу образец без замены из комплектов A, B, и C . Каждый «полный образец» представляет собой последовательность элементов из каждого из различных наборов, т.е. ( a1, b3, c2 ). Обратите внимание, что пространство полных выборок - это совокупность всех перестановок элементов в A, B, и C . В приведенном выше примере это пространство ( a1, a2 ... a8 ) x ( b1, b2 ... b10 ) x ( c1, c2 ... c25 ) и в моем пространстве 8 * 10 * 25 = 2000 уникальных "полных образцов".

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

Лучший метод в моем распоряжении прямо сейчас - отслеживать отобранные случаи. Это немного неэффективно, так как мой сэмплер вынужден отклонить любой случай, который был отобран ранее (так как я беру выборку без замены). Затем я выполняю оценку функции для несэмплированных случаев, просматривая каждую перестановку ( ax, by, cz ), используя вложенные циклы for, и выполняя оценку функции, только если эта комбинация ( ax, by , cz ) в выборочные случаи не входит. Опять же, это немного неэффективно, так как я должен «проверить», была ли каждая перестановка ( ax, by, cz ) уже выбрана.

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

Ответы [ 2 ]

2 голосов
/ 16 марта 2011

Вам действительно нужно отслеживать все несобранные случаи? Даже если бы у вас был вектор размером 1 на 10 10 , в котором хранилось логическое значение , равное true или false, указывающее, была ли выбрана эта перестановка или нет, для этого все равно потребуется около 10 ГБ. памяти, и MATLAB, скорее всего, либо выдаст ошибку «Недостаточно памяти» , либо приведёт к полной остановке всей машины, если вы попытаетесь создать переменную такого размера.

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

A = 1:8;
B = 1:10;
C = 1:25;
nA = numel(A);
nB = numel(B);
nC = numel(C);
beenSampled = sparse(1,nA*nB*nC);

Разреженная матрица размером 1 на 2000 beenSampled пуста для начала (т. Е. Содержит все нули), и мы добавим единицу с заданным индексом для каждой выборочной перестановки. Мы можем получить новую выборку перестановок, используя функцию RANDI , чтобы дать нам индексы в A, B и C для нового набора значений: 

indexA = randi(nA);
indexB = randi(nB);
indexC = randi(nC);

Затем мы можем преобразовать эти три индекса в один уникальный линейный индекс в beenSampled, используя функцию SUB2IND : 

index = sub2ind([nA nB nC],indexA,indexB,indexC);

Теперь мы можем проверить индексированный элемент в beenSampled, чтобы увидеть, имеет ли он значение 1 (т. Е. Мы уже взяли его) или 0 (т. Е. Это новый сэмпл). Если он уже был выбран, мы повторим процесс поиска нового набора индексов выше. Как только у нас есть перестановка, которую мы еще не взяли, мы можем ее обработать: 

while beenSampled(index)
  indexA = randi(nA);
  indexB = randi(nB);
  indexC = randi(nC);
  index = sub2ind([nA nB nC],indexA,indexB,indexC);
end
beenSampled(index) = 1;
newSample = [A(indexA) B(indexB) C(indexC)];
%# ...do your subsequent processing...

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

0 голосов
/ 16 марта 2011

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

current_values = [5 89 45];  % lets say this is your current sample set
used_values = [used_values; current_values];
% wash, rinse, repeat
...