Как получить косинусное сходство сложности в Matlab?

Я реализовал косинусное сходство в Matlab следующим образом. На самом деле у меня есть двумерная матрица 50 на 50. Чтобы получить косинус, я должен сравнивать элементы в построчной форме.

for j = 1:50
    x = dat(j,:);
    for i = j+1:50
        y = dat(i,:);
        c = dot(x,y);
        sim = c/(norm(x,2)*norm(y,2));
    end
end

Это правильно? и вопрос в следующем: какова сложность или O (n) в этом состоянии?


matlab cosine-similarity similarity
person sima412    schedule 13.08.2013    source источник
comment
... в построчной форме. Вы имеете в виду по строкам или по столбцам?   -  person horchler    schedule 14.08.2013
comment
извините, я имею в виду построчно. Между двумя рядами   -  person sima412    schedule 14.08.2013
comment
является ли проблема: а) найти сложность выбранного вами алгоритма (независимого от MATLAB), б) иметь эффективный алгоритм для вычисления попарного косинусного подобия (опять же независимого от MATLAB) или в) иметь эффективную/быструю реализацию MATLAB? пожалуйста, постарайтесь быть кратким в том, что спрашивают.   -  person gevang    schedule 15.08.2013

Ответы (2)


arrow_upward
1
arrow_downward

Лучше заканчивай на 49. Может тебе тоже индекс добавить в сим?

for j = 1:49
  x = dat(j,:);
  for i = j+1:50
      y = dat(i,:);
      c = dot(x,y);
      sim(j) = c/(norm(x,2)*norm(y,2));
  end
end

Сложность должна быть примерно как o(n^2), не так ли? Возможно, вам следует взглянуть на функции корреляции ... Я не понимаю, что именно вы хотите написать, но похоже, что вы хотите сделать что-то подобное. В Matlab есть встроенные корреляционные функции.

person Melanchtron    schedule 14.08.2013
comment
спасибо Мелахтрон. я хочу получить косинусное сходство сложности. но еще один вопрос. Я хочу сравнить косинусное сходство и расстояние Хэмминга, но (1-расстояние Хэмминга для получения сходства между двумя векторами). Знаете ли вы, что такое расстояние Хэмминга сложности, но расстояние Хэмминга 1? а треска в матлабе? - person sima412; 14.08.2013
comment
см. mathworks.de/de/help/stats/pdist.html. для расстояния Хэмминга - вы можете использовать встроенную команду Matlab, если хотите запрограммировать ее самостоятельно, пожалуйста, посмотрите ответ gevang - person Melanchtron; 15.08.2013
comment
вам нужен двойной индекс для sim, то есть sim(j, i), иначе каждый запуск внутреннего цикла i будет перезаписывать предыдущий (таким образом, в sim(j) будет храниться только последний вызов i=j+50). По сути, вам нужно будет хранить n(n-1)/2 значений сходства в одномерном или двумерном массиве. Последнее может быть удобнее. - person gevang; 19.08.2013

arrow_upward
1
arrow_downward

Просто заметка об эффективной реализации того же самого с использованием векторных и матричных операций (которые оптимизированы в MATLAB). Это может иметь огромную экономию времени для больших матриц:

dat = randn(50, 50);

Реализация OP (двойного за):

sim = zeros(size(dat));
nRow = size(dat,1);
for j = 1:nRow
    x = dat(j, :);
    for i = j+1:nRow
        y = dat(i, :);
        c = dot(x, y);
        sim(j, i) = c/(norm(x,2)*norm(y,2));
    end
end

Векторизированная реализация:

normDat = sqrt(sum(dat.^2, 2));           % L2 norm of each row 
datNorm = bsxfun(@rdivide, dat, normDat); % normalize each row 
dotProd = datNorm*datNorm';               % dot-product vectorized (redundant!) 
sim2 = triu(dotProd, 1);                  % keep unique upper triangular part

Сравнения для матрицы 1000 x 1000: (MATLAB 2013a, x64, Intel Core i7 960 @ 3,20 ГГц)

Elapsed time is 34.103095 seconds.
Elapsed time is 0.075208 seconds.
sum(sum(sim-sim2))
ans =
    -1.224314766369880e-14
person gevang    schedule 14.08.2013
comment
Большое спасибо за примечание. Это правда для расстояния Хэмминга? и какие меры подобия? - person sima412; 15.08.2013
comment
@ sima412 изучите pdist2 для реализации различных мер подобия (включая hamming' and cosine'), определенных для попарных наблюдений. - person gevang; 15.08.2013
comment
хорошо, спасибо, gevang. но я использую друг к другу тип расстояния hammin. я хочу использовать 1-haming. - person sima412; 15.08.2013
comment
Возможно ли, чтобы вы подсказали мне, что векторизованное внедрение (1-hammin) ؟ - person sima412; 15.08.2013