scoreliner.blogg.se - Basic algorithms for interviews

a maximization (M) step, which computes parameters maximizing the expected log-likelihood found on the E step.an expectation (E) step, which creates a function for the expectation of the log-likelihood evaluated using the current estimate for the parameters.The iteration alternates between performing:

It’s useful when the model depends on unobserved latent variables and equations can’t be solved directly. 8.1.1.3 EM (expectation-maximization) algorithmĮM algorithm is an iterative method to find maximum likelihood (MLE) or maximum a posteriori (MAP) estimates of parameters. After obtaining clusters using k-means clustering, we can classify new data into those clusters by applying the 1-nearest neighbor classifier to the cluster centers.Īpplications: Vector quantization for signal processing (where k-means clustering was originally developed), cluster analysis, feature learning, topic modeling. The algorithm has a loose relationship to the k-nearest neighbor classifier. The problem is computationally difficult (NP-hard) however, efficient heuristic algorithms converge quickly to a local optimum. As the algorithm is usually fast, it is common to run it multiple times with different starting conditions. The result may depend on the initial clusters. The algorithm doesn’t guarantee convergence to the global optimum. k-means minimizes within-cluster variances (squared Euclidean distances), but not regular Euclidean distances.

K-means clustering aims to partition observations into k clusters in which each observation belongs to the cluster with the nearest mean.

In k-NN regression, each object’s value is calculated as the average of the values of its k nearest neighbors.Īpplications: anomaly detection, search, recommender system 8.1.1.2 k-means clustering.

In k-NN classification, each object is classified into the class most common among its k nearest neighbors.

Given an object, the algorithm’s output is computed from its k closest training examples in the feature space. K-NN is a non-parametric method used for classification and regression. 8.1.1 Overview: Basic algorithms 8.1.1.1 k-nearest neighbor (k-NN)