k-означает, что в Matlab недостаточно памяти в зависимости от функции расстояния? - PullRequest
Новая
       41

k-означает, что в Matlab недостаточно памяти в зависимости от функции расстояния?

4 голосов
/ 03 августа 2011

Я использую k-means с matlab на большой и разреженной матрице ~ (1000000x1000). Теперь вот проблема - используя косинусное сходство в качестве функции расстояния, я получаю сообщение «Недостаточно памяти. Введите HELP MEMORY for your options» в течение нескольких минут. Однако, если я использую евклидово расстояние, оно проходит отлично (та же матрица).

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

Косинус прекрасно работает при использовании k-средних на меньшей матрице (1000x1000, хотя и не так редко).

Технические данные: Машина 64-битная с 8 ГБ оперативной памяти. Если вы хотите попробовать: матрицу можно найти здесь (она находится в пространстве отправки, поэтому она будет доступна в течение нескольких недель).

Файл имеет разреженный формат: [строка] \ t [столбец] \ t [значение] \ n

код Matlab: 

f=load(filename);
v=spconvert(f);
c=kmeans(v,9);
c=kmeans(v,9,'distance','cosine');

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

  2. Есть идеи, как приблизиться к нему и использовать косинус на большой матрице?

Спасибо!

1 Ответ

6 голосов
/ 25 августа 2011

Если вы проверяете функцию kmeans.m, то код косинусного расстояния сводится к двум критическим разделам, которые могут вызвать ошибки нехватки памяти.Сначала позвольте мне представить основные переменные:

  • X: строки - векторы наблюдений, столбцы - измерения (данные)
  • C: строкиявляются центроидами, столбцы - измерениями (центроиды кластеров)

1)

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

[n,p] = size(X);              %# in your case, X is a matrix of size 1000000x1000

Xnorm = sqrt(sum(X.^2, 2));   %# norm of each instance vector
X = X ./ Xnorm(:,ones(1,p));  %# normalize to unit length

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

>> whos X Xnorm
  Name             Size                 Bytes  Class     Attributes

  X          1017564x1000            83056640  double    sparse    
  Xnorm      1017564x1               12210776  double    sparse

Таким образом, Xnorm(:,ones(1,p)) попытается выделить временную матрицу размером 12210776*1000 bytes = 11.3722 GB, которая явно вызывает ошибку нехватки памяти....

(Для тех, кому интересно, матрица с двойной разреженностью X внутренне нуждается в 12*nnz(X) + 4*size(X,2) bytes для хранения, тогда как полное представление занимает prod(size(X))*8 bytes. В вашем случае это около 80 МБ против 11,5Требуется ГБ памяти!)

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

X = bsxfun(@rdivide, X, Xnorm);

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

2)

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

n = size(X,1);
nclusts = size(C,1);

D = zeros(n,nclusts);
for i = 1:nclusts
    D(:,i) = max(1 - X*C(i,:)', 0);
end

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

for i = 1:nclusts
    for j = 1:n
        D(j,i) = max(1 - dot(X(j,:),C(i,:)), 0);
    end
end

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

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

for i = 1:nclusts
    D(:,i) = (X(:,1) - C(i,1)).^2;
    for j = 2:p
        D(:,i) = D(:,i) + (X(:,j) - C(i,j)).^2;
    end
    % D(:,i) = sum((X - C(repmat(i,n,1),:)).^2, 2);    %# <--- commented code
end

Тем не менее, я удивлен, что BSXFUN снова не использовался вместо: 

for i=1:nclusts
    D(:,i) = sum(bsxfun(@minus, X, C(i,:)).^2, 2);
end

Обратите внимание, что у меня нетне пытался кластеризовать все данные до завершения.Я работаю на 32-разрядной машине с 4 ГБ (из которых MATLAB может получить доступ только к 3 ГБ из-за ограничений архитектуры), поэтому, пожалуйста, сообщите, действительно ли предлагаемые изменения имеют значение для вашего 64-разрядного / 8 ГБ оборудования;)

...