Ускоренный поиск огромного массива matlab

Question

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

[ 0 1 2 3 4 5 NaN NaN; 
    4 6 7 8 NaN NaN NaN NaN; 
...] 

Только размер этой вещи - это размер (данные) = [90810 30]. Теперь я хочу найти частые пункты в этой базе данных (без слишком большого использования панелей инструментов). Я обеспечу toyexample здесь:

toyset = [ 
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9; 
    5, 6, 7,NaN,NaN,NaN,NaN,NaN,NaN,NaN; 
    5, 6, 7,NaN,NaN,NaN,NaN,NaN,NaN,NaN; 
    1, 6, 7, 9, 10, 11,NaN,NaN,NaN,NaN; 
    2, 4, 8, 11, 12,NaN,NaN,NaN,NaN,NaN]; 

Это будет генерировать следующие наборы элементов при применении минимальной поддержки 0,5 [поддержки = (occurences_of_set)/(all_sets)]:

frequent_itemsets = [ 
    7,NaN,NaN; 
    6,NaN,NaN; 
    5,NaN,NaN; 
    6, 7,NaN; 
    5, 7,NaN; 
    5, 6,NaN; 
    5, 6, 7]; 

Моя проблема сейчас нахождение частого набора элементов в наборе данных. В настоящее время я использую следующий алгоритм (который работает прекрасно кстати):

function list = preprocess(subjectArray, combinations, progressBar) 
% ========================================================================= 
% 
% Creates a list which indicates how often an article-combination given by 
% combinations is present in the array of Customers 
% 
% ========================================================================= 
% 
% preprocesses the array; Finds the frequency of articles 
% subjectArray - Array that contains customer data 
% combinations - The article combinations to be found 
% progressBar  - The progress bar to indicate the progress of the 
%      algorithm 
% 
% ========================================================================= 

    [countCustomers,maxSizeCustomers] = size(subjectArray); 
    [countCombinations,sizeCombinations] = size(combinations); 
    list=zeros(1,countCombinations); 

    for i = 1:countCustomers 
     waitbar(i/countCustomers,progressBar,sprintf('Preprocess: %.0f/%.0f\nSet size:%.0f',i,countCustomers,sizeCombinations)); 
     for k = 1 : countCombinations 
      helpArray = zeros(1,maxSizeCustomers); 
      help2Array = zeros(1,sizeCombinations); 
      for j = 1:sizeCombinations 
       helpArray = helpArray + (subjectArray(i,:) == combinations(k,j)); 
       help2Array(j) = any(helpArray); 
      end 
      list(k) = list(k) + all(help2Array); 
     end 
    end 
end 

Моя единственная проблема это то, что берет возрасты !!! Буквально!! Есть ли какая-то простая возможность (за исключением наборов длины 1, я знаю, что можно сделать быстрее простым подсчетом), чтобы сделать это быстрее?

Я думаю, что это:

helpArray = helpArray + (subjectArray(i,j) == combinations(k,:)); 

является узким местом? Но я не уверен, так как не знаю, как быстро Matlab выполняет определенные операции.

Спасибо за глядя в него, mind_

То, что я закончил с делать:

function list = preprocess(subjectArray, combinations) 
% ========================================================================= 
% 
% Creates a list which indicates how often an article-combination given by 
% combinations is present in the array of Customers 
% 
% ========================================================================= 
% 
% preprocesses the array; Finds the frequency of articles 
% subjectArray - Array that contains customer data 
% combinations - The article combinations to be found 
% 
% ========================================================================= 

    [countCustomers,maxSizeCustomers] = size(subjectArray); 
    [countCombinations,sizeCombinations] = size(combinations); 
    list=zeros(1,countCombinations); 


    if sizeCombinations == 1 
     for i = 1 : countCustomers 
      for j = 1 : maxSizeCustomers 
       x = subjectArray(i,j) + 1; 
       if isnan(x), break; end 
       list(x+1) = list(x+1) + 1; 
      end 
     end 
    else 
     for i = 1:countCombinations 
      logical = zeros(size(subjectArray)); 
      for j = 1:sizeCombinations 
       logical = logical + (subjectArray == combinations(i,j)); 
      end 
      list(i) = sum(sum(logical,2) == sizeCombinations); 
     end 
    end 
end 

Спасибо за поддержку!

Answer 1

Три предложения, которые я вижу сразу же:

Во-первых, ваш waitbar добавляет еще три с половиной минуты для поиска. Согласно этой теме: http://www.mathworks.com/matlabcentral/newsreader/view_thread/261380 он берет код, проходящий через 240 000 предметов, дополнительно 550 секунд, чтобы выполнить, если вы включите панель ожидания, масштабируйте ее до 90 000, и у вас все еще есть 3 с половиной минуты дополнительного времени.

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

logical7=subjectArray==7; 
numOf7s=sum(sum(logical7)); 

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

Чтобы сделать этот код лучше, вы можете сделать что-то вроде

предварительно выделить логический мат, с каждым 3d срезом, представляющим числом (шестой фрагмент представляет частоту. = 5, 7 среза представляет частоту. = 6)

logMat=zeros([size(subjectArray) maxPossibleVal+1])% Макс. Возможный вес - 9 в коробке для игрушек ex.

затем заполнить каждый кусочек с логическими #

матриц,

for i=0:maxPossibleVal 
    logMat(:,:,i+1) = subjectArray==i; 
end 

Еще раз, вы можете получить суммы от каждого логического среза и те, которые меньше определенного порогового значения, вы можете удалить из журнала. mat (я бы также использовал логическую индексацию для удаления срезов, которые не соответствуют порогу)

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

logM7=logMat(:,:,8) 
logM8=logMat(:,:,9) 

combo7and8=logical(double(logM7)+double(logM8))

% Вы могли бы заменить это возможно, с | чтобы сделать это проще/быстрее

freq7and8=sum(sum(combo7and8')==2) 

% суммы по умолчанию находит сумму столбцов, превратить наши строки в столбцы, а затем выяснить, какие строки равны 2, добавить все логические 1 вместе, и у вас есть частота , из 7 и 8 в каждом наборе данных.

Весь этот пост можно резюмировать двумя вещами:

Взлет waitbar

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

Answer 2

Извините, но я не могу комментировать (моя репутация слишком низкая, я полагаю) Частая добыча полезных ископаемых довольно сложна. Если у вас огромный набор данных, и вы выбираете низкий порог для того, чтобы элемент (набор) был частым, с вашим подходом (apriori?), Вы должны быть готовы долго ждать :) Обычно, когда вы имеете дело с вложенными для петли с matlab, вы также испытываете низкую производительность. Какой порог вы выбрали? насколько велик ваш набор данных?