Classification
Dr. Ceni Babaoglu
Data Science Laboratory
Classification
• Classification is a “predictive” method
• Classification is a “supervised” learning method
2
Classification Algorithms
• Logistic regression
• Naïve Bayes classifier
• Decision trees
• k-Nearest Neighbours (k-NN)
3
k-Nearest Neighbours Algorithm
• Stores all available cases and classifies new
cases based on a similarity measure (e.g. distance functions)
• Used mostly in pattern recognition
4
k-Nearest Neighbours 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 neighbours by a distance
function
• If k = 1, then the case is simply assigned to the class of its
nearest neighbour
• Distance Functions: Euclidean, Manhattan, Minkowski
5
k-Nearest Neighbours Algorithm
• Compute the test point’s distance from each
training point
• Sort the distances in order
• Use the sorted distances to select the k nearest neighbours
• Use majority rule
6
k-Nearest Neighbours Algorithm
• k-NN is a method that classifies unlabeled
examples based on their similarity to examples in the
training set
• For a given unlabeled example x, we want to find k closest
labeled examples in the training data set and assign x to the
class that appears most frequently
7
k-Nearest Neighbours Algorithm
k-NN algorithm requires:
• An integer k
• A set of labeled examples (training data)
• A metric to measure closeness
8
Example
The green circle should be classified
If k = 3, it is assigned to red triangles
If k = 5, it is assigned to blue squares
9
References
Additional information and slide 9 image retrieved from
[Link]
10