Supervised Learning(Part-6)

 K-nearest Neighbor


K Nearest Neighbors - Classification

K nearest neighbors is a simple algorithm that stores all available cases and classifies new cases based
on a similarity measure (e.g., distance functions). KNN has been used in statistical estimation and
pattern recognition already in the beginning of 1970’s as a non-parametric technique. 
 
Algorithm
A case is classified by a majority vote of its neighbors, with the case being assigned to the class most
common amongst its K nearest neighbors measured by a distance function. If K = 1, then the case is
simply assigned to the class of its nearest neighbor. 

It should also be noted that all three distance measures are only valid for continuous variables. In
the instance of categorical variables the Hamming distance must be used. It also brings up the issue of standardization of the numerical variables between 0 and 1 when there is a mixture of numerical
and categorical variables in the dataset.

Choosing the optimal value for K is best done by first inspecting the data. In general, a large K value
is more precise as it reduces the overall noise but there is no guarantee. Cross-validation is another
way to retrospectively determine a good K value by using an independent dataset to validate
the K value. Historically, the optimal K for most datasets has been between 3-10. That produces
much better results than 1NN.
 
Example:
Consider the following data concerning credit default. Age and Loan are two numerical variables
(predictors) and Default is the target.

We can now use the training set to classify an unknown case (Age=48 and Loan=$142,000) using
Euclidean distance. If K=1 then the nearest neighbor is the last case in the training set with Default=Y.
 

D = Sqrt[(48-33)^2 + (142000-150000)^2] = 8000.01  >> Default=Y

  

With K=3, there are two Default=Y and one Default=N out of three closest neighbors. The prediction
for the unknown case is again Default=Y.
 
Standardized Distance
One major drawback in calculating distance measures directly from the training set is in the case
where variables have different measurement scales or there is a mixture of numerical and categorical
variables. For example, if one variable is based on annual income in dollars, and the other is based
on age in years then income will have a much higher influence on the distance calculated.
One solution is to standardize the training set as shown below.
 

Using the standardized distance on the same training set, the unknown case returned a different
neighbor which is not a good sign of robustness. 

Comments

Post a Comment

Popular posts from this blog

Supervised Learning(Part-5)

Image
  Decision Trees (Continued) Attribute Selection Measures If the dataset consists of N attributes then deciding which attribute to place at the root or at different levels of the tree as internal nodes is a complicated step. By just randomly selecting any node to be the root can’t solve the issue. If we follow a random approach, it may give us bad results with low accuracy. For solving this attribute selection problem, researchers worked and devised some solutions. They suggested using some criteria like : Entropy, Information gain, Gini index, Gain Ratio, Reduction in Variance Chi-Square These criteria will calculate values for every attribute. The values are sorted, and attributes are placed in the tree by following the order i.e, the attribute with a high value(in case of information gain) is placed at the root. While using Information Gain as a criterion, we assume attributes to be categorical, and for the Gini index, attributes are assumed to be continuous. Entropy Entropy is a me
Read more

Supervised Learning(Part-2)

Image
  Support Vector Machine A Support Vector Machine (SVM) is a discriminative classifier formally defined by a separating hyperplane. In other words, given labeled training data, the algorithm outputs an optimal hyperplane which categorizes new examples.  In two dimensional space this hyperplane is a line dividing a plane in two parts where in each class lay in either side. Suppose given plot of two label classes on graph as shown in image. You might have come up with something similar to following image (image B). It fairly separates the two classes. Any point that is left of line falls into black circle class and on right falls into blue square   In real world application, finding perfect class for millions of training data set takes lot of time. This is called regularization parameter.  Two terms regularization parameter and gamma are tuning parameters in SVM classifier. Varying those we can achieve considerable non linear classification line with more accuracy in reasonable amount of
Read more

Text Analysis (Part - 4)

Image
  The article covers a very important concepts of Text Analysis from Bayesian's i.e the  Latent Dirichlet Allocation  which is the part of topic modelling . What is Topic Modelling? Topic modelling is a type of statistical modelling for discovering the abstract “topics” that occur in a collection of documents. This can be useful for search engines, customer service automation, and any other instance where knowing the topics of documents is important . Thus, Topic Models , in a nutshell, are a type of statistical language models used for uncovering hidden structure in a collection of texts. There are multiple methods of for topic modelling and one of them includes Latent Dirichlet Allocation (LDA) . Latent Dirichlet Allocation Latent Dirichlet Allocation (LDA) is an example of topic model and is used to classify text in a document to a particular topic. It builds a topic per document model and words per topic model, modelled as Dirichlet distributions. Basic Idea LDA is a  genera
Read more