## Exploring The Brute Force K-Nearest Neighbors Algorithm

By Murugan Yuvaraaj, Praxis Enterprise Schoo

Did you discover any distinction between the 2 graphs?

Each present the accuracy of a classification drawback for Ok values between 1 to 10.

Each of the graphs use the KNN classifier mannequin with ‘Brute-force’ algorithm and ‘Euclidean’ distance metric on identical dataset. Then why is there a distinction within the accuracy between the 2 graphs?

Earlier than answering that query, let me simply stroll you thru the KNN algorithm pseudo code.

I hope all are acquainted with k-nearest neighbour algorithm. If not, you’ll be able to learn the fundamentals about it at https://www.analyticsvidhya.com/blog/2018/03/introduction-k-neighbours-algorithm-clustering/.

We will implement a KNN mannequin by following the under steps:

2. Initialise the worth of ok
3. For getting the anticipated class, iterate from 1 to whole variety of coaching knowledge factors
4. Calculate the gap between take a look at knowledge and every row of coaching knowledge. Right here we’ll use Euclidean distance as our distance metric because it’s the preferred technique. A few of the different metrics that can be utilized are Chebyshev, cosine, and many others.
5. Type the calculated distances in ascending order primarily based on distance values
6. Get high ok rows from the sorted array
7. Get essentially the most frequent class of those rows
8. Return the anticipated class

For our evaluation, lets simply concentrate on step 7, getting essentially the most frequent class of those rows.

After getting the highest ok rows, we decide essentially the most frequent class (mode) from these rows. There’s a little drawback with that.

In case of an odd ok neighbours, there will probably be all the time a majority class within the record. Thus, there will probably be no drawback with odd ok neighbours.

However what about a fair ok neighbours quantity and if two or extra lessons get the identical majority?

The KNN algorithm may give excessive accuracy for a dataset for ok even neighbours. It’s not restricted to solely use odd ok neighbours to get the bulk class.

Take for instance:

If ok = Four and we’ve Class A = 2 and Class B = 2 in our record. In that case, the algorithm will take the category what falls within the first rows of the highest Ok rows as an alternative of trying on the distance metric.

To resolve this drawback, we used distance – mode – distance as our standards for even-numbered ok neighbours in our algorithm.

Our algorithm works the identical manner because the brute-force algorithm, however the distinction that it makes with even ok neighbours is nice.

What our algorithm does could be very easy. It takes the highest ok rows from the gap metric. Within the case of an odd ok worth, it takes the bulk. For a fair variety of ok rows, majority lessons are chosen. If it occurs to have two or extra lessons having a majority, these two or extra main class distances will go to the gap metric loop once more and examine which class has the bottom distance metric, and that class is chosen as the bulk class.

Let’s have a look at an instance of how this works.

For our evaluation we used the penguin dataset.

Brute-force Algorithm:

Right here we gave ok = 4.

Class ‘Chinstrap’ and ‘Adelie’ ended up with mode as 2. After arranging the Ok neighbours primarily based on mode, brute-force ended up choosing the primary class as an alternative of choosing the category which had least distance within the distance metric.

This impacts the accuracy for the brute-force algorithm when ok worth is even.

Our Mannequin:

Our mannequin is ready to improve the accuracy in case of even numbered neighbours.

Outcomes:

I’ve in contrast the accuracy of our mannequin with brute-force and under are the outcomes.

 Ok Brute Pressure Our Mannequin 1 0.805 0.805 2 0.746 0.805 3 0.761 0.761 4 0.746 0.791 5 0.776 0.776 6 0.716 0.791 7 0.746 0.746 8 0.686 0.746 9 0.746 0.746 10 0.701 0.776

I in contrast the outcomes with kd tree and ball tree algorithms additionally, and related outcomes had been obtained.