matlab - mezcla - gaussian mixture model

Comprender el concepto de modelos de mezclas Gaussianas

Question

Intento entender GMM leyendo las fuentes disponibles en línea. He logrado agrupar usando K-Means y estaba viendo cómo GMM se compararía con K-means.

Esto es lo que he entendido, por favor avíseme si mi concepto es incorrecto:

GMM es como KNN, en el sentido de que la agrupación se logra en ambos casos. Pero en GMM cada clúster tiene su propia media y covarianza independientes. Además, k-means realiza asignaciones duras de puntos de datos a clusters, mientras que en GMM obtenemos una colección de distribuciones gaussianas independientes, y para cada punto de datos tenemos una probabilidad de que pertenezca a una de las distribuciones.

Para entenderlo mejor, he usado MatLab para codificarlo y lograr el clúster deseado. He utilizado las características de SIFT para extraer las características. Y usé el clúster k-means para inicializar los valores. (Esto es de la documentación de 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);

Basado en lo anterior, tengo means , covariances y priors . Mi pregunta principal es, ¿ahora qué? Estoy algo perdido ahora.

También los means , vectores de covariances son cada uno del tamaño 128 x 50 . Esperaba que fueran 1 x 50 ya que cada columna es un clúster, ¿no es que cada grupo tiene solo una media y covarianza? (Sé que 128 son las características SIFT, pero esperaba medias y covarianzas).

En k-means utilicé el comando MatLab knnsearch(X,Y) que básicamente encuentra el vecino más cercano en X para cada punto en Y.

Entonces, cómo lograr esto en GMM, sé ​​que es una colección de probabilidades, y por supuesto, el emparejamiento más cercano a esa probabilidad será nuestro clúster ganador. Y aquí es donde estoy confundido. Todos los tutoriales en línea han enseñado cómo lograr los valores means , las covariances , pero no dicen mucho sobre cómo usarlos realmente en términos de agrupamiento.

Gracias

Answer 1

Creo que ayudaría si primero GMM que representa un modelo GMM . Usaré functions de la Caja de herramientas de estadísticas , pero debería poder hacer lo mismo con VLFeat.

Comencemos con el caso de una mezcla de dos distribuciones normales en 1 dimensión. Cada gaussiano está representado por un par de mean y variance . La mezcla asigna un peso a cada componente (previo).

Por ejemplo, mezclemos dos distribuciones normales con pesos iguales ( p = [0.5; 0.5] ), la primera centrada en 0 y la segunda en 5 ( mu = [0; 5] ), y las varianzas son iguales a 1 y 2 respectivamente para la primera y la segunda distribución ( sigma = cat(3, 1, 2) ).

Como puede ver a continuación, la media efectivamente desplaza la distribución, mientras que la varianza determina qué tan ancha / estrecha y plana / puntiaguda es. El anterior establece las proporciones de mezcla para obtener el modelo combinado final.

% 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));

La idea de la agrupación EM es que cada distribución representa un clúster. Entonces, en el ejemplo anterior con datos unidimensionales, si le dieron una instancia x = 0.5 , la asignaríamos como perteneciente al primer clúster / modo con un 99.5% de probabilidad

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

puedes ver cómo la instancia cae bien debajo de la primera curva de campana. Mientras que si toma un punto en el medio, la respuesta sería más ambigua (punto asignado a clase = 2 pero con mucha menos certeza):

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

Los mismos conceptos se extienden a una dimensión más alta con distribuciones normales multivariables . En más de una dimensión, la matriz de covarianza es una generalización de la varianza, para tener en cuenta las interdependencias entre las características.

Aquí hay un ejemplo de nuevo con una mezcla de dos distribuciones de MVN en 2 dimensiones:

% 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]));

Existe cierta intuición detrás de cómo la matriz de covarianza afecta la forma de la función de densidad conjunta. Por ejemplo, en 2D, si la matriz es diagonal, implica que las dos dimensiones no varían conjuntamente. En ese caso, el PDF se vería como una elipse alineada al eje estirada horizontal o verticalmente según la dimensión que tenga la mayor varianza. Si son iguales, entonces la forma es un círculo perfecto (distribución distribuida en ambas dimensiones a la misma velocidad). Finalmente, si la matriz de covarianza es arbitraria (no diagonal pero aún simétrica por definición), entonces probablemente se verá como una elipse estirada rotada en algún ángulo.

Entonces, en la figura anterior, debería ser capaz de diferenciar los dos "baches" y qué distribución individual representa cada uno. Cuando vaya en 3D y dimensiones más altas, piense en ello como representando (hiper-) ellipsoids en N-dims.

Ahora cuando se realiza una clustering con GMM, el objetivo es encontrar los parámetros del modelo (media y covarianza de cada distribución, así como de los priores) para que el modelo resultante se ajuste mejor a los datos. La mejor estimación se traduce en la maximización de la probabilidad de los datos dados el modelo GMM (lo que significa que eliges un modelo que maximice Pr(data|model) ).

Como otros han explicado, esto se resuelve iterativamente usando el algoritmo EM ; EM comienza con una estimación inicial o conjetura de los parámetros del modelo de mezcla. Reanuda iterativamente las instancias de datos contra la densidad de mezcla producida por los parámetros. Las instancias recalculadas se usan luego para actualizar las estimaciones de los parámetros. Esto se repite hasta que el algoritmo converge.

Lamentablemente, el algoritmo EM es muy sensible a la inicialización del modelo, por lo que puede llevar mucho tiempo converger si establece valores iniciales deficientes o incluso se queda atascado en el óptimo local . Una mejor forma de inicializar los parámetros de GMM es usar K-means como primer paso (como lo ha demostrado en su código), y usar la media / co de esos clusters para inicializar EM.

Al igual que con otras técnicas de análisis de conglomerados, primero debemos decidir la cantidad de clústeres que se utilizarán. Cross-validation es una forma robusta de encontrar una buena estimación de la cantidad de clusters.

La agrupación de EM sufre del hecho de que hay muchos parámetros para ajustar, y generalmente requiere muchos datos y muchas iteraciones para obtener buenos resultados. Un modelo no restringido con mezclas M y datos D-dimensionales implica ajustar los parámetros D*D*M + D*M + M (matrices de covarianza M cada una de tamaño DxD, más vectores medios M de longitud D, más un vector de priores de longitud METRO). Eso podría ser un problema para conjuntos de datos con gran cantidad de dimensiones . Por lo tanto, es costumbre imponer restricciones y suposiciones para simplificar el problema (una especie de regularization para evitar problemas de overfitting ). Por ejemplo, puede corregir la matriz de covarianza para que sea solo diagonal o incluso tenga las matrices de covarianza shared en todos los gaussianos.

Finalmente, una vez que haya ajustado el modelo de mezcla, puede explorar los conglomerados calculando la probabilidad posterior de instancias de datos usando cada componente de mezcla (como he demostrado con el ejemplo de 1D). GMM asigna cada instancia a un clúster de acuerdo con esta probabilidad de "membresía".

Aquí hay un ejemplo más completo de agrupamiento de datos utilizando modelos de mezclas gaussianas:

% 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

La covarianza le dice cómo varían los datos en el espacio, si una distribución tiene una gran covarianza, eso significa que los datos están más dispersos y viceversa. Cuando tiene el PDF de una distribución gaussiana (parámetros de media y covarianza), puede verificar la confianza de pertenencia de un punto de prueba bajo esa distribución.

Sin embargo, GMM también sufre de la debilidad de K-Means, que debe elegir el parámetro K, que es el número de clusters. Esto requiere una buena comprensión de la multimodalidad de sus datos.

Answer 3

Tienes razón, existe la misma idea detrás del agrupamiento con K-Means o GMM. Pero como mencionas las Mezclas Gaussianas, ten en cuenta las covarianzas de datos. Para encontrar los parámetros de máxima verosimilitud (o MAP a posteriori máximo) del modelo estadístico GMM, debe usar un proceso iterativo llamado algoritmo EM . Cada iteración se compone de un E-step (Expectativa) y un M-step (Maximización) y repite hasta la convergencia. Después de la convergencia, puede estimar fácilmente las probabilidades de pertenencia de cada vector de datos para cada modelo de clúster.