Понимание концепции гауссовых моделей смесей

Question

Я пытаюсь понять GMM, читая источники, доступные онлайн. Я добился кластеризации с помощью K-Means и увидел, как GMM будет сравниваться с K-means.

Вот что я понял, пожалуйста, дайте мне знать, если моя концепция неверна:

GMM похож на KNN в том смысле, что кластеризация достигается в обоих случаях. Но в GMM каждый кластер имеет свое независимое среднее значение и ковариацию. Кроме того, k-means выполняет жесткое присвоение точек данных кластерам, тогда как в GMM мы получаем коллекцию независимых гауссовых распределений, и для каждой точки данных мы имеем вероятность того, что она принадлежит одному из распределений.

Чтобы лучше это понять, я использовал MatLab для его кодирования и достижения желаемой кластеризации. Я использовал функции SIFT для извлечения функций. И использовали кластеризацию k-средних для инициализации значений. (Это из документации VLFeat)

%images is a 459 x 1 cell array where each cell contains the training image
[locations, all_feats] = vl_dsift(single(images{1}), 'fast', 'step', 50); %all_feats will be 128 x no. of keypoints detected
for i=2:(size(images,1))
    [locations, feats] = vl_dsift(single(images{i}), 'fast', 'step', 50);
    all_feats = cat(2, all_feats, feats); %cat column wise all features
end

numClusters = 50; %Just a random selection.
% Run KMeans to pre-cluster the data
[initMeans, assignments] = vl_kmeans(single(all_feats), numClusters, ...
    'Algorithm','Lloyd', ...
    'MaxNumIterations',5);

initMeans = double(initMeans); %GMM needs it to be double

% Find the initial means, covariances and priors
for i=1:numClusters
    data_k = all_feats(:,assignments==i);
    initPriors(i) = size(data_k,2) / numClusters;

    if size(data_k,1) == 0 || size(data_k,2) == 0
        initCovariances(:,i) = diag(cov(data'));
    else
        initCovariances(:,i) = double(diag(cov(double((data_k')))));
    end
end

% Run EM starting from the given parameters
[means,covariances,priors,ll,posteriors] = vl_gmm(double(all_feats), numClusters, ...
    'initialization','custom', ...
    'InitMeans',initMeans, ...
    'InitCovariances',initCovariances, ...
    'InitPriors',initPriors);

На основании изложенного у меня means, covariances а также priors, Мой главный вопрос: что теперь? Я сейчас немного потерян.

Так же means, covariances векторы каждого размера 128 x 50, Я ожидал, что они будут 1 x 50 Поскольку каждый столбец является кластером, не будет ли у каждого кластера только одно среднее значение и ковариация? (Я знаю, что 128 - это функция SIFT, но я ожидал средств и ковариаций).

В k-средних я использовал команду MatLab knnsearch(X,Y) который в основном находит ближайшего соседа в X для каждой точки в Y.

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

Спасибо

Answer 1

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

Начнем со случая смеси двух одномерных нормальных распределений. Каждый гауссиан представлен парой среднего значения и дисперсии. Смеси присваивают вес каждому компоненту (предварительно).

Например, давайте смешаем два нормальных распределения с равными весами (p = [0.5; 0.5]) первый с центром в 0 и второй в 5 (mu = [0; 5]), а дисперсии равны 1 и 2 соответственно для первого и второго распределений (sigma = cat(3, 1, 2)).

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

% create GMM
mu = [0; 5];
sigma = cat(3, 1, 2);
p = [0.5; 0.5];
gmm = gmdistribution(mu, sigma, p);

% view PDF
ezplot(@(x) pdf(gmm,x));

Идея EM кластеризации заключается в том, что каждый дистрибутив представляет кластер. Таким образом, в приведенном выше примере с одномерными данными, если вам дали экземпляр x = 0.5мы бы присвоили ему принадлежность к первому кластеру / режиму с вероятностью 99,5%

>> x = 0.5;
>> posterior(gmm, x)
ans =
    0.9950    0.0050    % probability x came from each component

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

>> x = 2.2
>> posterior(gmm, 2.2)
ans =
    0.4717    0.5283

---

Те же понятия распространяются на более высокие измерения с многомерными нормальными распределениями. В более чем одном измерении ковариационная матрица является обобщением дисперсии, чтобы учесть взаимозависимости между объектами.

Вот снова пример со смесью двух распределений MVN в двух измерениях:

% first distribution is centered at (0,0), second at (-1,3)
mu = [0 0; 3 3];

% covariance of first is identity matrix, second diagonal
sigma = cat(3, eye(2), [5 0; 0 1]);

% again I'm using equal priors
p = [0.5; 0.5];

% build GMM
gmm = gmdistribution(mu, sigma, p);

% 2D projection
ezcontourf(@(x,y) pdf(gmm,[x y]));

% view PDF surface
ezsurfc(@(x,y) pdf(gmm,[x y]));

Существует некоторая интуиция о том, как ковариационная матрица влияет на форму функции плотности соединения. Например, в 2D, если матрица диагональна, это означает, что два измерения не изменяются. В этом случае PDF будет выглядеть как выровненный по оси эллипс, вытянутый либо горизонтально, либо вертикально, в зависимости от того, какое измерение имеет большую дисперсию. Если они равны, то форма представляет собой идеальный круг (распределение распространяется в обоих измерениях с одинаковой скоростью). Наконец, если ковариационная матрица является произвольной (недиагональной, но все же симметричной по определению), то она, вероятно, будет выглядеть как вытянутый эллипс, повернутый на некоторый угол.

Таким образом, на предыдущем рисунке вы должны быть в состоянии отличить два "выступа" и то, какое отдельное распределение они представляют. Когда вы переходите в 3D и более высокие измерения, думайте о нем как о представлении (гипер) эллипсоидов в N-диммах.

---

Теперь, когда вы выполняете кластеризацию с использованием GMM, цель состоит в том, чтобы найти параметры модели (среднее значение и ковариацию каждого распределения, а также априоры), чтобы полученная модель наилучшим образом соответствовала данным. Оценка наилучшего соответствия приводит к максимизации вероятности получения данных с учетом модели GMM (то есть вы выбираете модель, которая максимизирует Pr(data|model)).

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

К сожалению, алгоритм EM очень чувствителен к инициализации модели, поэтому может потребоваться много времени, чтобы сойтись, если вы установили плохие начальные значения или даже застряли в локальных оптимумах. Лучшим способом инициализации параметров GMM является использование K-средних в качестве первого шага (как вы показали в своем коде) и использование среднего значения /cov этих кластеров для инициализации EM.

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

EM-кластеризация страдает от того факта, что для этого требуется множество параметров, и обычно для получения хороших результатов требуется много данных и много итераций. Неограниченная модель с M-смесями и D-мерными данными включает в себя подгонку D*D*M + D*M + M параметры (M ковариационных матриц, каждая из которых имеет размер DxD, плюс M означают векторы длины D, плюс вектор априоров длины M). Это может быть проблемой для наборов данных с большим количеством измерений. Поэтому принято налагать ограничения и допущения для упрощения проблемы (своего рода регуляризация, чтобы избежать переобучения проблем). Например, вы можете установить ковариационную матрицу, чтобы она была только диагональной, или даже иметь ковариационные матрицы, общие для всех гауссианов.

Наконец, после того, как вы подобрали модель смешивания, вы можете исследовать кластеры, вычисляя апостериорную вероятность экземпляров данных, используя каждый компонент смеси (как я показал на примере 1D). GMM назначает каждый экземпляр кластеру в соответствии с этой вероятностью "членства".

---

Вот более полный пример кластеризации данных с использованием моделей гауссовой смеси:

% load Fisher Iris dataset
load fisheriris

% project it down to 2 dimensions for the sake of visualization
[~,data] = pca(meas,'NumComponents',2);
mn = min(data); mx = max(data);
D = size(data,2);    % data dimension    

% inital kmeans step used to initialize EM
K = 3;               % number of mixtures/clusters
cInd = kmeans(data, K, 'EmptyAction','singleton');

% fit a GMM model
gmm = fitgmdist(data, K, 'Options',statset('MaxIter',1000), ...
    'CovType','full', 'SharedCov',false, 'Regularize',0.01, 'Start',cInd);

% means, covariances, and mixing-weights
mu = gmm.mu;
sigma = gmm.Sigma;
p = gmm.PComponents;

% cluster and posterior probablity of each instance
% note that: [~,clustIdx] = max(p,[],2)
[clustInd,~,p] = cluster(gmm, data);
tabulate(clustInd)

% plot data, clustering of the entire domain, and the GMM contours
clrLite = [1 0.6 0.6 ; 0.6 1 0.6 ; 0.6 0.6 1];
clrDark = [0.7 0 0 ; 0 0.7 0 ; 0 0 0.7];
[X,Y] = meshgrid(linspace(mn(1),mx(1),50), linspace(mn(2),mx(2),50));
C = cluster(gmm, [X(:) Y(:)]);
image(X(:), Y(:), reshape(C,size(X))), hold on
gscatter(data(:,1), data(:,2), species, clrDark)
h = ezcontour(@(x,y)pdf(gmm,[x y]), [mn(1) mx(1) mn(2) mx(2)]);
set(h, 'LineColor','k', 'LineStyle',':')
hold off, axis xy, colormap(clrLite)
title('2D data and fitted GMM'), xlabel('PC1'), ylabel('PC2')

Answer 2

Вы правы, то же самое относится к кластеризации с K-Means или GMM. Но, как вы упомянули, гауссовые смеси учитывают ковариации данных. Чтобы найти параметры максимального правдоподобия (или максимальный апостериорный MAP) статистической модели GMM, вам необходимо использовать итерационный процесс, называемый EM-алгоритмом. Каждая итерация состоит из E-шага (ожидание) и M-шага (максимизация) и повторяется до сходимости. После конвергенции вы можете легко оценить вероятности членства каждого вектора данных для каждой кластерной модели.

Answer 3

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

Однако GMM также страдает от слабости K-Means, что вы должны выбрать параметр K, который является количеством кластеров. Это требует хорошего понимания мультимодальности ваших данных.