K-Nearest Neighbor

K-Nearest Neighbor

The K-Nearest Neighbors algorithm is a powerful supervised machine learning algorithm typically used for classification. However, it can also perform regression. 

K-Nearest Neighbors (KNN) is a classification algorithm. The central idea is that data points with similar attributes tend to fall into similar categories. 

K-Nearest Neighbors :from sklearn.neighbors import KNeighborsClassifier

Three steps of the K-Nearest Neighbor Algorithm:
  1. Normalize the data
  2. Find the k nearest neighbors
  3. Classify the new point based on those neighbors

Euclidean Distance

To find the Euclidean distance between two points, we first calculate the squared distance between each dimension. If we add up all of these squared differences and take the square root, we’ve computed the Euclidean distance. 

The image below shows a visual of Euclidean distance being calculated:

The Euclidean distance between two points. 

Manhattan Distance

Manhattan Distance is extremely similar to Euclidean distance. Rather than summing the squared difference between each dimension, we instead sum the absolute value of the difference between each dimension. 

The equation is shown below:


∣a1−b1∣+∣a2−b2∣+…+∣an−bn∣\mid a_1 - b_1 \mid + \mid a_2 - b_2 \mid + \ldots + \mid a_n - b_n \mid

Note that Manhattan distance will always be greater than or equal to Euclidean distance. Take a look at the image below visualizing Manhattan Distance:

The Manhattan distance between two points.

Hamming Distance

Hamming Distance is another slightly different variation on the distance formula. Instead of finding the difference of each dimension, Hamming distance only cares about whether the dimensions are exactly equal. When finding the Hamming distance between two points, add one for every dimension that has different values.
Hamming distance is used in spell checking algorithms. For example, the Hamming distance between the word “there” and the typo “thete” is one. Each letter is a dimension, and each dimension has the same value except for one.


SciPy Distances

Python’s SciPy library:

  • Euclidean Distance .euclidean()
  • Manhattan Distance .cityblock()
  • Hamming Distance .hamming()

 




Comments

Post a Comment

Popular posts from this blog

Support Vector Machines

Image
Support Vector Machines A Support Vector Machine (SVM) is a powerful supervised machine learning model used for classification. An SVM makes classifications by defining a decision boundary and then seeing what side of the boundary an unclassified point falls on. Decision boundaries get defined,  by using a training set of classified points.     Decision boundaries exist even when your data has more than two features. If there are three features, the decision boundary is now a plane rather than a line.   As the number of dimensions grows past 3, it becomes very difficult to visualize these points in space. Nonetheless, SVMs can still find a decision boundary. However, rather than being a separating line, or a separating plane, the decision boundary is called a separating hyperplane . Optimal Decision Boundaries In general, we want our decision boundary to be as far away from training points as possible. Maximizing the dis...
Read more

ACCURACY, RECALL, PRECISION, F1 SCORE

ACCURACY, RECALL, PRECISION, F1 SCORE Classifying a single point can result in a true positive ( truth = 1 , guess = 1 ), a true negative ( truth = 0 , guess = 0 ), a false positive ( truth = 0 , guess = 1 ), or a false negative ( truth = 1 , guess = 0 ). Accuracy measures how many classifications your algorithm got correct out of every classification it made. Recall measures the percentage of the relevant items your classifier was able to successfully find. Precision measures the percentage of items your classifier found that were actually relevant. Precision and recall are tied to each other. As one goes up, the other will go down. F1 score is a combination of precision and recall. F1 score will be low if either precision or recall is low. The decision to use precision, recall, or F1 score ultimately comes down to the context of your classification. Maybe you don’t care if your classifier has a lot of false positives. If that’s the case, precision doesn’t matter as m...
Read more

Random Forest

RANDOM FOREST A random forest is an ensemble machine learning model. It makes a classification by aggregating the classifications of many decision trees. Random forests are used to avoid overfitting. By aggregating the classification of multiple trees, having overfitted trees in a random forest is less impactful. Every decision tree in a random forest is created by using a different subset of data points from the training set. Those data points are chosen at random with replacement , which means a single data point can be chosen more than once. This process is known as bagging . When creating a tree in a random forest, a randomly selected subset of features are considered as candidates for the best splitting feature. If your dataset has n features, it is common practice to randomly select the square root of n features. Boosting Steps : Draw a random subset of training samples d1 without replacement from the training set D to train a weak learner C1 ...
Read more