Dempster, Laird & Rubin, Maximum Likelihood from Incomplete Data via the EM Algorithm, JRSS-B 1977
Three clusters in two dimensions. One is long and thin along a diagonal, one is tight and round, one is tilted the other way. k-means assumes clusters are spherical and equally sized, so it cuts the elongated one in half and scores about 0.52 on adjusted Rand index.
The generative view fixes this. Assume each point came from one of K Gaussians, with the component that produced it unobserved:
You cannot maximise that likelihood directly, because you do not know which component produced which point. EM alternates between filling in that missing information and re-fitting.
E-step. Given the current parameters, compute the posterior probability that point i came from component k:
M-step. Re-fit each component as a weighted average, with as the weights:
The paper's theorem is that the log-likelihood never decreases. That is a genuine test of your implementation, and this project grades it.
Establish the shape before assuming anything about it.
Implement explore_mixture(train_df) on columns x1 and x2, returning n_rows, n_dims, mean, std, covariance (a nested 2 by 2 list) and correlation, all floats to 5 places.
Use np.cov(X.T), which is the sample covariance with n−1 in the denominator. The off-diagonal term is what tells you the components are not axis-aligned, and therefore that no diagonal-covariance model, k-means included, is going to fit this well.
sklearn.cluster.KMeans for the baselinenp.random.default_rng(0)Evaluated server-side against a hidden test set.