Рисование случайного ненулевого элемента из разреженной матрицы

Question

У меня есть разреженная логическая матрица, которая довольно велика.Я хотел бы нарисовать случайные ненулевые элементы из него, не сохраняя все его ненулевые элементы в отдельном векторе (например, с помощью команды find).Есть ли простой способ сделать это?

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

Answer 1

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

%# using find
idx = find(S);
%# draw 4 without replacement
fourRandomIdx = idx(randperm(length(idx),4));
%# draw 4 with replacement
fourRandomIdx = idx(randi(1,length(idx),4));
%# get row, column values
[row,col] = ind2sub(size(S),fourRandomIdx);



%# using rejection sampling
density = nnz(S)/prod(size(S));
%# estimate how many samples you need to get at least 4 hits
%# and multiply by 2 (or 3)
n = ceil( 1 / (1-(1-density)^4) ) * 2;
%# random indices w/ replacement
randIdx = randi(1,n,prod(size(S)));
%# identify the first four non-zero elements
[row,col] = find(S(randIdx),4,'first');

Answer 2

Матрица nxm с nnz ненулевыми элементами требует nnz + n + 1 целых чисел для хранения местоположений своих ненулевых записей.Для логической матрицы нет необходимости хранить значения ненулевых записей: все они истинны.Соответственно, вам лучше всего преобразовать свою логическую разреженную матрицу в список линейных индексов ее ненулевых элементов вместе с n и m, для чего требуется только nnz + 2 целых числа памяти.Из них (и ind2sub) вы можете легко восстановить индексы, соответствующие любой ненулевой записи, которую вы выбираете случайным образом, используя randi в диапазоне 1..nnz

Answer 3

Представляя записи в формате с 3 столбцами, или в виде списка координат (i, j, значение), вы можете просто выбрать элементы из списка.Чтобы получить это, вы можете либо использовать свой оригинальный метод для создания разреженной матрицы (то есть предшественника sparse()), либо использовать команду find, например: [i,j,s] = find(S);

Если вы этого не сделаетенужны записи, а кажется, что нет, вы можете просто извлечь i и j.

Если по какой-то причине ваша матрица массивна, а ограничения ОЗУ серьезны, вы можете просто разделить матрицу на регионы и позволить вероятности выбора данной подматрицы быть пропорциональной числуноль элементов (используя nnz) в этой подматрице.Вы можете пойти так далеко, что разделите матрицу на отдельные столбцы, а остальная часть вычисления будет тривиальной.Примечание: применив sum к матрице, вы можете получить количество столбцов (при условии, что ваши записи равны только 1 с).

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

Answer 4

find - это стандартный интерфейс для получения ненулевых элементов в разреженной матрице. Посмотрите здесь http://www.mathworks.se/help/techdoc/math/f6-9182.html#f6-13040

[i,j,s] = find(S)

find возвращает индексы строк ненулевых значений в векторе i, индексы столбцов в векторе j и сами ненулевые значения в векторе s.

Нет необходимости получать с. Просто выберите случайный индекс в i, j.