<jupyter_start><jupyter_text>Drawback of K-Means is that it uses distance based model but Gaussian distribution uses distribution based model.  Defination -Gaussian Mixture Models (GMMs) assume that there are a certain number of Gaussian distributions, and each of these distributions represent a cluster. Hence, a Gaussian Mixture Model tends to group the data points belonging to a single distribution together.  The Gaussian DistributionSome of us might have studied the Gaussian Distribution (or Normal Distribution). It has a bell-shaped curve, with the data points symmetrically distributed around the mean value.The below image has a few Gaussian distributions with a difference in mean &micro; and variance &sigma;2. Remember that the higher the σ value more would be the spread:![Gaussian Distribution](https://miro.medium.com/max/875/1*lTv7e4Cdlp738X_WFZyZHA.png)\Here, we can see that there are three Gaussian functions, hence K = 3. Each Gaussian explains the data contained in each of the three clusters available.Here the Gaussian function is given by:![Gaussian function](https://cdn.analyticsvidhya.com/wp-content/uploads/2019/10/pdf_var-1.png)\where &micro; is the mean and &sigma;2 is the variance.A 3D Bell Curve can be shown as:![Bell Curve 3D](https://cdn.analyticsvidhya.com/wp-content/uploads/2019/10/gaussians-3d.png)Here the probability density function would be:![pdf](https://cdn.analyticsvidhya.com/wp-content/uploads/2019/10/pdf_var-2.png)where x is the input vector, &micro; is the 2D mean vector, and &sum; is the 2×2 covariance matrix. The covariance would now define the shape of this curve. We can generalize the same for d-dimensions.> _Thus, this multivariate Gaussian model would have x and &micro; as vectors of length d, and &sum; would be a dxd covariance matrix._\These values are determined using a technique called Expectation-Maximization (EM).\ What is Expectation-Maximization?\> _The expectation-maximization algorithm is an approach for performing maximum likelihood estimation in the presence of latent (missing) variables._\**Since we do not have the values for the latent variables, Expectation-Maximization tries to use the existing data to determine the optimum values for these variables and then finds the model parameters.** Based on these model parameters, we go back and update the values for the latent variable, and so on.Broadly, the Expectation-Maximization algorithm has two steps:- **(Expectation)** Assign each data point to a cluster probabilistically. In this case, we compute the probability it came from the red cluster and the yellow cluster respectively.- **(Maximization)** Update the parameters for each cluster (weighted mean location and variance-covariance matrix) based on the points in the cluster (weighted by their probability assigned in the first step).Expectation-Maximization is the base of many algorithms, including Gaussian Mixture Models. Expectation-Maximization in Gaussian Mixture ModelsLet’s understand this using another example. I want you to visualize the idea in your mind as you read along. This will help you better understand what we’re talking about.We should follow the following steps for the solution:1. Start with an arbitrary initial choice of parameters.2. Apply Expectation3. Apply Maximization4. Repeat steps 2 and 3 to convergence.Let the parameters of our model be![](https://miro.medium.com/max/720/1*rVAJtuaMXEgcdklaSBRzQw.png)Let’s say we need to assign $k$ number of clusters. This means that there are k Gaussian distributions, with the mean and covariance values to be &micro;1, &micro;2, .. &micro;k and &sum;1, &sum;2, .. &sum;k . Additionally, there is another parameter for the distribution that defines the number of points for the distribution. Or in other words, the density of the distribution is represented with &Pi;i.**Step 1:**\Initialise θ accordingly. For instance, we can use the results obtained by a previous K-Means run as a good starting point for our algorithm.**Step 2 (Expectation step):**For each point xi, calculate the probability that it belongs to cluster/distribution c1, c2, … ck. This is done using the below formula:\![formula](https://cdn.analyticsvidhya.com/wp-content/uploads/2019/10/probab_gmm_1.png)\The result of this operation would be high when the point is assigned to the right cluster and lower otherwise.**Step 3 (Maximization step):**Here we go back and update the &Pi;, &micro; and &sum; values. These are updated in the following manner:1. The new density is defined by the ratio of the number of points in the cluster and the total number of points:      \      ![Pi update](https://cdn.analyticsvidhya.com/wp-content/uploads/2019/10/mean-formula-gmm.png)2. The mean and the covariance matrix are updated based on the values assigned to the distribution, in proportion with the probability values for the data point. Hence, a data point that has a higher probability of being a part of that distribution will contribute a larger portion:   \      ![Mu and Sigma Update](https://cdn.analyticsvidhya.com/wp-content/uploads/2019/10/formulas-gmm-e1571990956378-300x128.png)\ **Step 4 :**Now based on the updated values generated from this step , we calculate the probabilities for each data points and update the values iteratively. This is done in order to maximize the [log-likelihood function](https://en.wikipedia.org/wiki/Likelihood_function:~:text=Log%2Dlikelihood%20function%20is%20a,to%20maximizing%20the%20log%2Dlikelihood.).In other words, _k-means only considers the mean to update the centroid while GMM takes into account the mean as well as the variance of the data._> ![example of EM](https://miro.medium.com/max/450/0*kE-YHM1yJfxnbCLt.gif) \>   [Expectation Maximization for Old Faithful Eruption Data](https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm)\ Expectation Maximization in General1. We have some data X of whatever form.2. We posit there is also unobserved (latent) data Δ, again of whatever form.3. We have a model with parameters &theta;.4. We have the ability to compute the log-likelihood ℓ(θ; X, Δ). Specifically, the log of the probability of observing our data and specified assignments of the latent variables given the parameters.5. We also have the ability to use the model to compute the conditional distribution Δ|X given a set of parameters. We will denote this P(Δ|X; θ).6. Consequently we can compute the log-likelihood ℓ(θ; X). This is the log of the probability of observing our data given the parameters (without assuming an assignment for the latent variables).  In Depth: Gaussian Mixture Models The *k*-means clustering model explored in the previous section is simple and relatively easy to understand, but its simplicity leads to practical challenges in its application.In particular, the non-probabilistic nature of *k*-means and its use of simple distance-from-cluster-center to assign cluster membership leads to poor performance for many real-world situations.In this section we will take a look at Gaussian mixture models (GMMs), which can be viewed as an extension of the ideas behind *k*-means, but can also be a powerful tool for estimation beyond simple clustering.We begin with the standard imports:<jupyter_code>%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np<jupyter_output><empty_output><jupyter_text>Motivating GMM: Weaknesses of k-MeansLet's take a look at some of the weaknesses of *k*-means and think about how we might improve the cluster model.As we saw in the previous section, given simple, well-separated data, *k*-means finds suitable clustering results.For example, if we have simple blobs of data, the *k*-means algorithm can quickly label those clusters in a way that closely matches what we might do by eye:<jupyter_code># Generate some data
from sklearn.datasets.samples_generator import make_blobs
X, y_true = make_blobs(n_samples=400, centers=4,
                       cluster_std=0.60, random_state=0)
X = X[:, ::-1] # flip axes for better plotting
# Plot the data with K Means Labels
from sklearn.cluster import KMeans
kmeans = KMeans(4, random_state=0)
labels = kmeans.fit(X).predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=40, cmap='viridis');<jupyter_output><empty_output><jupyter_text>From an intuitive standpoint, we might expect that the clustering assignment for some points is more certain than others: for example, there appears to be a very slight overlap between the two middle clusters, such that we might not have complete confidence in the cluster assigment of points between them.Unfortunately, the *k*-means model has no intrinsic measure of probability or uncertainty of cluster assignments (although it may be possible to use a bootstrap approach to estimate this uncertainty).For this, we must think about generalizing the model.One way to think about the *k*-means model is that it places a circle (or, in higher dimensions, a hyper-sphere) at the center of each cluster, with a radius defined by the most distant point in the cluster.This radius acts as a hard cutoff for cluster assignment within the training set: any point outside this circle is not considered a member of the cluster.We can visualize this cluster model with the following function:<jupyter_code>from sklearn.cluster import KMeans
from scipy.spatial.distance import cdist

def plot_kmeans(kmeans, X, n_clusters=4, rseed=0, ax=None):
    labels = kmeans.fit_predict(X)

    # plot the input data
    ax = ax or plt.gca()
    ax.axis('equal')
    ax.scatter(X[:, 0], X[:, 1], c=labels, s=40, cmap='viridis', zorder=2)

    # plot the representation of the KMeans model
    centers = kmeans.cluster_centers_
    radii = [cdist(X[labels == i], [center]).max()
             for i, center in enumerate(centers)]
    for c, r in zip(centers, radii):
        ax.add_patch(plt.Circle(c, r, fc='#CCCCCC', lw=3, alpha=0.5, zorder=1))
kmeans = KMeans(n_clusters=4, random_state=0)
plot_kmeans(kmeans, X)<jupyter_output><empty_output><jupyter_text>An important observation for *k*-means is that these cluster models *must be circular*: *k*-means has no built-in way of accounting for oblong or elliptical clusters.So, for example, if we take the same data and transform it, the cluster assignments end up becoming muddled:<jupyter_code>rng = np.random.RandomState(13)
X_stretched = np.dot(X, rng.randn(2, 2))

kmeans = KMeans(n_clusters=4, random_state=0)
plot_kmeans(kmeans, X_stretched)<jupyter_output><empty_output><jupyter_text>By eye, we recognize that these transformed clusters are non-circular, and thus circular clusters would be a poor fit.Nevertheless, *k*-means is not flexible enough to account for this, and tries to force-fit the data into four circular clusters.This results in a mixing of cluster assignments where the resulting circles overlap: see especially the bottom-right of this plot.One might imagine addressing this particular situation by preprocessing the data with PCA (see [In Depth: Principal Component Analysis](05.09-Principal-Component-Analysis.ipynb)), but in practice there is no guarantee that such a global operation will circularize the individual data.These two disadvantages of *k*-means—its lack of flexibility in cluster shape and lack of probabilistic cluster assignment—mean that for many datasets (especially low-dimensional datasets) it may not perform as well as you might hope.You might imagine addressing these weaknesses by generalizing the *k*-means model: for example, you could measure uncertainty in cluster assignment by comparing the distances of each point to *all* cluster centers, rather than focusing on just the closest.You might also imagine allowing the cluster boundaries to be ellipses rather than circles, so as to account for non-circular clusters.It turns out these are two essential components of a different type of clustering model, Gaussian mixture models.  Generalizing E–M: Gaussian Mixture ModelsA Gaussian mixture model (GMM) attempts to find a mixture of multi-dimensional Gaussian probability distributions that best model any input dataset.In the simplest case, GMMs can be used for finding clusters in the same manner as *k*-means:<jupyter_code>from sklearn.mixture import GMM
gmm = GMM(n_components=4).fit(X)
labels = gmm.predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=40, cmap='viridis');<jupyter_output><empty_output><jupyter_text>But because GMM contains a probabilistic model under the hood, it is also possible to find probabilistic cluster assignments—in Scikit-Learn this is done using the ``predict_proba`` method.This returns a matrix of size ``[n_samples, n_clusters]`` which measures the probability that any point belongs to the given cluster:<jupyter_code>probs = gmm.predict_proba(X)
print(probs[:5].round(3))<jupyter_output>[[ 0.     0.     0.475  0.525]
 [ 0.     1.     0.     0.   ]
 [ 0.     1.     0.     0.   ]
 [ 0.     0.     0.     1.   ]
 [ 0.     1.     0.     0.   ]]<jupyter_text>We can visualize this uncertainty by, for example, making the size of each point proportional to the certainty of its prediction; looking at the following figure, we can see that it is precisely the points at the boundaries between clusters that reflect this uncertainty of cluster assignment:<jupyter_code>size = 50 * probs.max(1) ** 2  # square emphasizes differences
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=size);<jupyter_output><empty_output><jupyter_text>Under the hood, a Gaussian mixture model is very similar to *k*-means: it uses an expectation–maximization approach which qualitatively does the following:1. Choose starting guesses for the location and shape2. Repeat until converged:   1. *E-step*: for each point, find weights encoding the probability of membership in each cluster   2. *M-step*: for each cluster, update its location, normalization, and shape based on *all* data points, making use of the weightsThe result of this is that each cluster is associated not with a hard-edged sphere, but with a smooth Gaussian model.Just as in the *k*-means expectation–maximization approach, this algorithm can sometimes miss the globally optimal solution, and thus in practice multiple random initializations are used.Let's create a function that will help us visualize the locations and shapes of the GMM clusters by drawing ellipses based on the GMM output:<jupyter_code>from matplotlib.patches import Ellipse

def draw_ellipse(position, covariance, ax=None, **kwargs):
    """Draw an ellipse with a given position and covariance"""
    ax = ax or plt.gca()
    
    # Convert covariance to principal axes
    if covariance.shape == (2, 2):
        U, s, Vt = np.linalg.svd(covariance)
        angle = np.degrees(np.arctan2(U[1, 0], U[0, 0]))
        width, height = 2 * np.sqrt(s)
    else:
        angle = 0
        width, height = 2 * np.sqrt(covariance)
    
    # Draw the Ellipse
    for nsig in range(1, 4):
        ax.add_patch(Ellipse(position, nsig * width, nsig * height,
                             angle, **kwargs))
        
def plot_gmm(gmm, X, label=True, ax=None):
    ax = ax or plt.gca()
    labels = gmm.fit(X).predict(X)
    if label:
        ax.scatter(X[:, 0], X[:, 1], c=labels, s=40, cmap='viridis', zorder=2)
    else:
        ax.scatter(X[:, 0], X[:, 1], s=40, zorder=2)
    ax.axis('equal')
    
    w_factor = 0.2 / gmm.weights_.max()
    for pos, covar, w in zip(gmm.means_, gmm.covars_, gmm.weights_):
        draw_ellipse(pos, covar, alpha=w * w_factor)<jupyter_output><empty_output><jupyter_text>With this in place, we can take a look at what the four-component GMM gives us for our initial data:<jupyter_code>gmm = GMM(n_components=4, random_state=42)
plot_gmm(gmm, X)<jupyter_output><empty_output><jupyter_text>Similarly, we can use the GMM approach to fit our stretched dataset; allowing for a full covariance the model will fit even very oblong, stretched-out clusters:<jupyter_code>gmm = GMM(n_components=4, covariance_type='full', random_state=42)
plot_gmm(gmm, X_stretched)<jupyter_output><empty_output><jupyter_text>This makes clear that GMM addresses the two main practical issues with *k*-means encountered before.  Choosing the covariance typeIf you look at the details of the preceding fits, you will see that the ``covariance_type`` option was set differently within each.This hyperparameter controls the degrees of freedom in the shape of each cluster; it is essential to set this carefully for any given problem.The default is ``covariance_type="diag"``, which means that the size of the cluster along each dimension can be set independently, with the resulting ellipse constrained to align with the axes.A slightly simpler and faster model is ``covariance_type="spherical"``, which constrains the shape of the cluster such that all dimensions are equal. The resulting clustering will have similar characteristics to that of *k*-means, though it is not entirely equivalent.A more complicated and computationally expensive model (especially as the number of dimensions grows) is to use ``covariance_type="full"``, which allows each cluster to be modeled as an ellipse with arbitrary orientation.We can see a visual representation of these three choices for a single cluster within the following figure: ![(Covariance Type)](https://github.com/jakevdp/PythonDataScienceHandbook/blob/master/notebooks/figures/05.12-covariance-type.png?raw=1)[figure source in Appendix](06.00-Figure-Code.ipynbCovariance-Type)  GMM as *Density Estimation*Though GMM is often categorized as a clustering algorithm, fundamentally it is an algorithm for *density estimation*.That is to say, the result of a GMM fit to some data is technically not a clustering model, but a generative probabilistic model describing the distribution of the data.As an example, consider some data generated from Scikit-Learn's ``make_moons`` function, which we saw in [In Depth: K-Means Clustering](05.11-K-Means.ipynb):<jupyter_code>from sklearn.datasets import make_moons
Xmoon, ymoon = make_moons(200, noise=.05, random_state=0)
plt.scatter(Xmoon[:, 0], Xmoon[:, 1]);<jupyter_output><empty_output><jupyter_text>If we try to fit this with a two-component GMM viewed as a clustering model, the results are not particularly useful:<jupyter_code>gmm2 = GMM(n_components=2, covariance_type='full', random_state=0)
plot_gmm(gmm2, Xmoon)<jupyter_output><empty_output><jupyter_text>But if we instead use many more components and ignore the cluster labels, we find a fit that is much closer to the input data:<jupyter_code>gmm16 = GMM(n_components=16, covariance_type='full', random_state=0)
plot_gmm(gmm16, Xmoon, label=False)<jupyter_output><empty_output><jupyter_text>Here the mixture of 16 Gaussians serves not to find separated clusters of data, but rather to model the overall *distribution* of the input data.This is a generative model of the distribution, meaning that the GMM gives us the recipe to generate new random data distributed similarly to our input.For example, here are 400 new points drawn from this 16-component GMM fit to our original data:<jupyter_code>Xnew = gmm16.sample(400, random_state=42)
plt.scatter(Xnew[:, 0], Xnew[:, 1]);<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup