training loss that we already encountered in thusthe unconstrained maximization of the log-likelihood function is an ill-posed problemirrespective of the choice of the optimization algorithmtwo possible solutions to this "overfittingproblem are restrict the parameter set th in such way that degenerate clusters (sometimes called spurious clustersare not allowed run the given algorithm and if the solution is degeneratediscard it and run the algorithm afresh keep restarting the algorithm until non-degenerate solution is obtained the first approach is usually applied to multiextremal optimization algorithms and the second is used for the em algorithm clustering via vector quantization in the previous section we introduced clustering via mixture modelsas form of parametric density estimation (as opposed to the nonparametric density estimation in section the clusters were modeled in natural way via the latent variables and the em algorithm provided convenient way to assign the cluster members in this section we consider more heuristic approach to clustering by ignoring the distributional properties of the data the resulting algorithms tend to scale better with the number of samples and the dimensionality in mathematical termswe consider the following clustering (also called data segmentationproblem given collection { xn of data points in some -dimensional space xdivide this data set into clusters (groupssuch that some loss function is minimized convenient way to determine these clusters is to first divide up the entire space xusing some distance function dist(**on this space standard choice is the euclidean (or distancev (xi xi ) dist(xx kx = manhattan distance other commonly used distance measures on rd include the manhattan distanced = maximum distance and the maximum distance|xi xi max |xi xi = , hamming distance on the set of strings of length dan often-used distance measure is the hamming distanced = {xi xi }that isthe number of mismatched characters for examplethe hamming distance between and is