MINISTRY OF NATIONAL EDUCATION, REPUBLIC OF MALI

HIGHER EDUCATION AND RESEARCH

***********
SCIENTIFIC
One people - One goal - One faith
*****************
NATIONAL SCHOOL OF ENGINEERS
ABDERHAMANE BABA TOURE (ENI-ABT)

ExposE

Theme

K-NEAREST NEIGHBORS ALGORITHM

K-NEAREST NEIGHBORS

Presented and supported by:Souleymane Kodjo

Abdrahamane Idrissa Doumbia
Ouzairou Djiré

Responsable pédagogique : Dr A. SIDIBE

 Summary
Chapter 1: Introduction........................................................................................................ 4
1.1Use case and applications................................................................. 4
Chapter 2: K Nearest Neighbors Algorithm5
2.1 Classification What class?» . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Regression How much?» ......................................................................................... 6
Chapter 3Principle of the algorithm..................................................................................... 7
3.1 Select the number k of neighbor............................................................................ 7
3.2 On calculate the distances between the data u and each data belonging to E
the help of the functiond ........................................................................................................... 7
3.2.1 Distance Euclidean............................................................................................ 7
3.2.2 Distance Manthattan
3.3 On retain the k data points from the dataset E that are closest to u..................... 8
3.4 On assign to u the class that is most frequent among the k nearest data points
close8
3.5 Writing algorithmice ................................................................................................. 8
Chapter 4Study of an Example......................................................................................... 10
4.1 Games of data....................................................................................................... 10
4.2 The software used............................................................Error! Bookmark not defined.
Anaconda navigator.............................................................................................................. 10
Jupyter notebook .................................................................................................................. 10
Chromiume .10
4.3 Libraries Used Python................................................................................ 10
4.3.1 Pandas 10
4.3.2 NumPy 11
4.3.3 Matpotlib ............................................................................................................ 11
4.3.4 Sklearn 11
4.4 Importation libraries
4.5 Importation the datas ............................................................................................ 11
4.6 Formatting .................................................................................................................. 11
4.7 First data visualization
4.8 Sample to predict.................................................................................................. 13
4.9 Visualization from the sample to predict in the graph............................................... 13
 4.10 Separation of the dataset into training set and testing set.................................... 14
4.11 KNN algorithm for K=2 .............................................................................. 14
4.12 Error rate optimization.............................................................................. 15
• In Graphical Form.................................................................................................. 15
4.13 Creation of a python function result that returns the predictionn ....................... 16
4.14 Final visualization and prediction
5 Conclusion........................................................................................................................ 18
Chapter 1: Introduction
Machine Learning can be defined as a
branch of artificial intelligence encompassing many methods for creation
Automatically models from data. These methods are actually algorithms.

A traditional computer program performs a task by following precise instructions.

and therefore systematically in the same way. On the contrary, a machine learning system does not
not instructions, but to give the ability to computers to learn from
data, that is to say to improve their performance in solving tasks without being explicitly
programmée pour chacun .En conséquent ces performances’améliore au fils de son
Training in terms of algorithms is exposed to more data.

1.1 Use Cases and Applications

Machine Learning powers many popular modern services for
product recommendation. Notable examples include: Netflix, YouTube, Amazon ...
The same goes for web search engines like Google or Baidu and voice assistants.
such as Siri and Alexa.

It is also used in price prediction, spam detection...

Chapter 2: K-Nearest Neighbors Algorithm
The k-nearest neighbors algorithm, also called KNN from the English K-Nearest
Neighbors belongs to the family of machine learning algorithms.
Learning). The idea of machine learning is not new, since the term Machine
Learning was first used by the American computer scientist Arthur Samuel in
1959. The k-nearest neighbors algorithm is a supervised learning algorithm.
In supervised learning, an algorithm receives a dataset that is
labeled with corresponding output values on which it will be able to train
and define a prediction model. This algorithm can subsequently be used on
new data to predict their corresponding output values.

The supervised learning algorithm addresses two problems:

2.1 Classification "Which class?"

The classification algorithm is initially fed a finite number of cataloged examples.
which he uses for his learning. This learning allows him to select a
"hypothesis", or rule supposed to make few classification errors on these examples
futures
The result is a membership class. An input object is classified according to the result.
majority of the class membership statistics of its k nearest neighbors.
2.2 Regression 'How Many?'
The regression algorithm is fed from the target variable or the explanatory variable.
(Y), the model aims to make a prediction using so-called explanatory variables (X) or
predictive
The result is the value for this Object. This value is the average of the values of the k most
close.
KNN is a non-parametric method in which the model memorizes the observations of
the training set for the classification of the test set data

Indeed, this algorithm is classified as lazy, because it learns nothing during the phase.
training. To predict the class of a new input data, it will look for its K
nearest neighbors (using Euclidean distance, or others) and will choose the class
majority neighbors.
Chapter 3: Principle of the algorithm
The k-nearest neighbors algorithm does not require a proper learning phase.
To speak, you just need to store the training dataset. Let E be a set containing n
labeled data: = (y , x⃗ i )} with i ranging between 1 and n, where corresponds to the class
(the label) of the data i and where the vector of dimension p( =( 1i, x2 ,..., )) represents
the predictive variables of the data i. Let there be a data u that does not belong to E and that does not
does not have a label (u is characterized only by a vector of dimension p). Let
of a function that returns the distance between the data u and any data belonging to
Let E be an integer k less than or equal to n. Here is the principle of the k-nearest neighbors algorithm.
neighbors:

3.1 Select the number k of neighbors

We fix the number of k neighbors, We detect the k nearest neighbors of the new ones.
data the entry we want to classify
3.2 We calculate the distances between the data u and each data belonging to
And with the function d
It is possible to use different types of distance: Euclidean, Manhattan, ...

3.2.1 Euclidean Distance

• On a graduated line:

The distance between A and B is: d(A,B) = |abscissa of B – abscissa of A|

the largest x-coordinate - the smallest x-coordinate
We can therefore write a distance function, in Python, that takes two input arguments.
coordinates x1 and x2 and returns the value of the distance between the two points of coordinates
x1 and x2
• In a plan:

We assume that the plane is equipped with an orthonormal frame (O;I;J).

Let A ( ; ) and B ( ; For two points in the plane, the Euclidean distance between A and B is:

( , )= = √( − )² + ( − )²
3.2.2 Manhattan Distance
The Manhattan distance was used in a regression analysis in 1757 by Roger.
Joseph Boscovich. The geometric interpretation dates back to the end of the 19th century and to
development of non-Euclidean geometries, notably by Hermann Minkowski and his
Minkowski inequality, of which this geometry constitutes a particular case, especially
used in number geometry (Minkowski 1910).
The Manhattan distance is also called taxi distance, it is the distance between two points.
Traversed by a taxi when moving in a city where the streets are arranged according to a
network or grid. A taxi path is the route taken by a taxi when it moves from a node
from one network to another using horizontal and vertical movements of the network.

Between two points A and B, with coordinates respectively ( , ) and ( , )

La distance de Manhattan est définie par :

( , )= | − | + | − |.

3.3 We keep the k data points from the dataset E that are closest to u.
3.4 We assign to u the class that is the most frequent among the k data
the closest
Depending on whether we reason in one, two, or three dimensions, the calculation of the distance between two
points is more or less simple.
To apply this principle, it will be necessary to:

✓ Evaluate the distance that separates the new element from each of the other points.
The set E. Each point of the set is characterized by its index i.
✓ Store these distance values d in a list of the type: [[d,i],[ ...],...], where d is the
distance that separates the new element from the index point i.
✓ Sort the list according to the values of the distances d.
✓ Select the first k points from the sorted list, which are the k-nearest neighbors.
✓ Assign a class to the new element based on the majority of classes
represented among the k-nearest neighbors.
We will need three functions:

✓a functiondistance to calculate the distance between two points with coordinates

known.
✓ A function that determines the k-nearest neighbors of a new element.
✓ A function predict_class that determines the majority result of the classes
of the k-nearest neighbors' belonging and assigns the class of the new element to this
majority class.
3.5 Algorithmic writing
We can illustrate the functioning of K-NN by writing it in the following pseudocode:
Start Algorithm
Input data:

▪ A dataset D.
▪ A function defining distance d.
▪ An integer K
For a new observation X for which we want to predict its output variable y Do:

1. Calculate all the distances of this observation X with the other observations
of the dataset
2. Retain the K observations from the dataset D that are closest to X using the
distance calculation function d
3. Take the values of y from the K selected observations:
1. If we perform a regression, calculate the mean (or the median)
and withholdings
2. If we perform a classification, calculate the mode of the retained y.
4. Return the calculated value from step 3 as the value that has been
predicted by K-NN for observation X.
End Algorithm
Chapter 4: Study of an Example
4.1 Datasets
We have chosen here to base ourselves on the "Fisher's iris dataset."

Photo 2 IRIS

Photo 1 IRIS

This dataset consists of 50 entries, for each entry we have:

▷ the length of the sepals (in cm)
▷ the width of the sepals (in cm)
▷ the length of the petals (in cm)
▷ the width of the petals (in cm)
▷ the species of iris: Iris setosa
Iris virginica
Iris versicolor
4.2 The software used
Anaconda navigator
Jupyter notebook
Chrome
4.3 Python libraries used
4.3.1 Pandas
Pandas is an excellent library for importing your Excel tables (and other formats) into
Python in order to extract statistics and load your Dataset into Sklearn.
4.3.2 NumPy
Numpy is the library that allows you to create and manipulate matrices or arrays easily.
with efficiency. Thus matrix calculation represents the essence of Machine Learning. It is
It is important to understand it, but the functions in Numpy perform matrix calculations.
in our place... Magical!
4.3.3 Matpotlib
Matplotlib is the library that allows us to visualize our datasets, our functions, our results in
shapes of graphs, curves, and scatter plots
4.3.4 Sklearn
Sklearn is the library that contains all the state-of-the-art functions of Machine Learning.
It contains the most important algorithms as well as various pre-processing functions.
4.4 Importing Libraries

4.5 Data Importation

4.6 Formatting
Here we will replace
Iris-setosa by 0
Iris-virginica by 1
Iris-versicolor by 2
4.7 First data visualization
Once the csv file is modified, it is possible to write a program to visualize
the data in graphical form (x-axis: 'petal_length', y-axis: 'petal_width')

Graph:
4.8 Sample to predict

4.9 Visualization of Sample to Predict in the Graph

Graph
4.10 Separation of the data into training set and testing set

4.11 KNN Algorithm for K=2

Use of KNN algorithm for K=2 and the prediction error rate
4.12 Error Rate Optimization

• In Graphical Form
4.13 Creation of a python function result that returns the prediction
It is the class to which the sample belongs.

4.14 Final visualization and prediction

Visualization in
Graph: The prediction result on the graph
5 Conclusion
In this report, you have discovered the k-NN algorithm which is one of the algorithms for
supervised machine learning is simple and easy to implement. it has none
hypothesis about data (linear, affine...) in addition to that, it is versatile. It can be
used for classification, regression.
You have also learned that:
oK-NN stores the entire dataset to make a prediction,
oK-NN does not calculate any predictive model and falls within the framework of Lazy Learning.