K-means clustering is unsupervised, and the closest unsupervised technique which uses EM is model-based clustering (Gaussian mixture models, GMM). An annoying problem with GMM model-based clustering occurs when many of the features are correlated, which causes near-singularity in the feature-based covariance(correlation) matrix. In this situation, the likelihood function becomes unstable, with condition indexes reaching infinity, causing
GMM to break down completely.
Thus, drop the idea of EM and kNN -- since it's based on covariance (correlation) matrices for unsupervised analysis. Your inquiry on optimization closely resembles Sammon mapping, and classical metric and non-metric multidimensional scaling (MDS). Sammon mapping is derivative-iterative based, while various forms of MDS are commonly iterative or one-step eigendecompositions, which can nevertheless optimize during a one-step matrix operation.
Looking again back at your request: the answer is: it's already been done in Sammon mapping.