# K-Nearest neighbors algorithm - the first step to Machine Learning?

Kamil Sopata
·Apr 16, 2019·

Machine Learning is like a magic word now - for sure you have heard something cool about it, a lot of developers tried to build some models using ready to use libraries like `scikit-learn`, but still some of us are affraid of it. But do you know that you can implement your first ML algorithm for your own. I read some time ago, not sure where, that k-Nearest neighbours is the first what you should try if you are interesting in ML.

## Let's try to do it!

You may think that the best option for this task will be Python (because most of popular ML tools are written in it). I've implemented kNN in Ruby because of a few reasons:

• I know Ruby pretty well
• Code and syntax are easy to understand for people who don't know Ruby
• Because why not? :)

Before we will start, let's try with simple example.

Let's say that we have recorded some unknown for us animal with sound frequency `20.9 Hz` and duration `2400 ms`. We know that it's a cat, but we don't know for sure if is it a domestic cat or cheetah.

According to these data, we can see that the purring of these cats is slightly different (different duration, cycles/phase, frequency). Let's try to use this data to create simple, test dataset:

``````unknown_cat = { label: "unknown cat", frequency: 20.9, duration: 2400 }

dataset = [
{ label: "domestic_cat", frequency: 22.6, duration: 575 },
{ label: "cheetah", frequency: 19.6, duration: 2770 },
{ label: "domestic_cat", frequency: 21.98, duration: 576 },
{ label: "cheetah", frequency: 20.87, duration: 3049 },
{ label: "domestic_cat", frequency: 23.24, duration: 573 },
{ label: "cheetah", frequency: 18.32, duration: 2491 }
]
``````

So, we have 6 examples in our dataset - 3 for domestic cats and 3 for cheetahs. We have also some unknown cat. Using these data, let's try to find out more about the unknown cat.

``````def cat_predictor(dataset, unknown_item)
max_similar_items = Math.sqrt(dataset.size).to_i
similar_items = {}

dataset.each do |dataset_el|
path = Math.sqrt(
(dataset_el[:frequency] - unknown_item[:frequency])**2 + (dataset_el[:duration] - unknown_item[:duration])**2
)

if similar_items.keys.size < max_similar_items || similar_items.keys.max > path
similar_items.delete(similar_items.keys.max) if similar_items.keys.size == max_similar_items
similar_items[path] = dataset_el
end
end

similar_items.map { |_path, item| item[:label] }.group_by(&:itself).transform_values(&:count).max_by(&:last)[0]
end

cat_predictor(dataset, unknown_cat)
# => cheetah
``````

Before I start with more complex examples, I will try to explain what happens there. First, look at the picture below:

source: datacamp.com

KNN is classification algorithm. Imagine that yellow point is our unknown cat, red points are domestic cat examples and green ones - cheetah examples. Like you can see we have to calculate "`path`" between each point from dataset and our unknown cat. To that we used a simple distance formula.

√(x1-x2)^2+(y1-y2)^2

The next important thing is the size of the set where we will be keeping the nearest examples (our "k") - I just calculated it by `Math.sqrt(dataset.size).to_i`, which means that "k" will have a square of dataset size. After that starts the core of our algorithm. We count the length of the path for each element and add them to `similar_items` hash if:

• there is a "free space" for new item
• or the new value is lower than the current highest

After all we just group results and choose group which has more items. Quite easy, isn't it?

## Movie rating prediction

The time has come for a more advanced example. I wanted to build model that can predict something, so I thought it would be cool if our example would be real-world example, so let's build a simple rating prediction system!

Let's say that we have some movie categories:

``````comedy_category  = OpenStruct.new(id: 1, name: 'Comedy')
action_category  = OpenStruct.new(id: 2, name: 'Action')
drama_category   = OpenStruct.new(id: 3, name: 'Drama')
horror_category  = OpenStruct.new(id: 4, name: 'Horror')
romance_category = OpenStruct.new(id: 5, name: 'Romance')
``````

And of course users which objects contains some statistics:

``````patrycja = OpenStruct.new(id: 1, name: 'Patrycja', watched_movies: {
comedy_category.id => 3,
action_category.id => 4,
drama_category.id => 4,
horror_category.id => 1,
romance_category.id => 4
})

justyna = OpenStruct.new(id: 2, name: 'Justyna', watched_movies: {
comedy_category.id => 4,
action_category.id => 3,
drama_category.id => 5,
horror_category.id => 1,
romance_category.id => 5
})

morfeusz = OpenStruct.new(id: 3, name: 'Morfeusz',  watched_movies: {
comedy_category.id => 2,
action_category.id => 5,
drama_category.id => 1,
horror_category.id => 3,
romance_category.id => 1
})

john = OpenStruct.new(id: 4, name: 'John',  watched_movies: {
comedy_category.id => 5,
action_category.id => 1,
drama_category.id => 1,
horror_category.id => 5,
romance_category.id => 1
})

simon = OpenStruct.new(id: 5, name: 'Simon',  watched_movies: {
comedy_category.id => 3,
action_category.id => 4,
drama_category.id => 3,
horror_category.id => 2,
romance_category.id => 4
})

angela = OpenStruct.new(id: 6, name: 'Angela',  watched_movies: {
comedy_category.id => 2,
action_category.id => 3,
drama_category.id => 2,
horror_category.id => 1,
romance_category.id => 4
})

hans = OpenStruct.new(id: 7, name: 'Hans',  watched_movies: {
comedy_category.id => 5,
action_category.id => 4,
drama_category.id => 4,
horror_category.id => 5,
romance_category.id => 5
})

users = [patrycja, justyna, morfeusz, john, simon, angela, hans]
``````

Last but not least, we need our movie:

``````movie = OpenStruct.new(id: 1, name: 'Matrix', ratings: {
justyna.id => 5,
morfeusz.id => 4,
john.id => 2,
simon.id => 4,
angela.id => 2,
hans.id => 5
})
``````

I've put them into OpenStruct objects, so we can treat them as for instance ActiveRecord objects.

Now we can start extend our previous algorithm to new requirements:

``````require 'ostruct'

class KnnModel
def initialize(dataset, new_item)
@dataset = dataset
@new_item = new_item
@neighbors_quantity = Math.sqrt(dataset.size).to_i
end

def build_model
shoritest_path = Float::INFINITY
nearest_neighbors = {}

(dataset - [new_item]).each do |dataset_el|
path = path_length(dataset_el)
if nearest_neighbors.keys.size < neighbors_quantity || nearest_neighbors.keys.max > path
nearest_neighbors.delete(nearest_neighbors.keys.max) if nearest_neighbors.keys.size == neighbors_quantity
nearest_neighbors[path] = dataset_el
end
end
Knn.new(nearest_neighbors)
end

private

def path_length(dataset_el)
dimension_results = 0
new_item.watched_movies.keys.each do |id|
next if dataset_el.watched_movies[id].nil?
dimension_results += (dataset_el.watched_movies[id] - new_item.watched_movies[id])**2
end
Math.sqrt(dimension_results)
end
end

class Knn

def initialize(nearest_neighbors)
@neighbors = nearest_neighbors
end

def predict_rating(movie)
neighbors_ratings = []
neighbors.values.each do |neighbor|
neighbors_ratings << movie.ratings[neighbor.id] if movie.ratings.keys.include?(neighbor.id)
end
return 'unpredictable average' if neighbors_ratings.empty?
count_avg_for_ratings(neighbors_ratings)
end

def find_user_who_like_similar_movies
neighbors[neighbors.keys.min].name
end

private

def count_avg_for_ratings(ratings)
ratings.instance_eval { reduce(:+) / size.to_f }
end
end
``````

And the results are:

``````knn_model = KnnModel.new(users, patrycja).build_model
puts 'nearest neighbors: '            + knn_model.neighbors.map{|el| el.last.name}.join(', ')
puts 'user who like similar movies: ' + knn_model.find_user_who_like_similar_movies
puts 'predicted rating for movie: '   + knn_model.predict_rating(movie).to_s
# =>
# nearest neighbors: Justyna, Simon
# user who like similar movies: Simon
# predicted rating for movie: 4.5
``````

As you can see, core of our code is similar to example with cats. First, we created kNN model in the same way as in previous example. Then we executed `predict_rating` method with `movie` as argument. This method is quite simple - it gets all ratings of nearest neighbors and counts their average.

## Bonus

I wanted to implement more efficient kNN algorithm some time ago. I didn't focus on design at all, my goal was to calculate the model as soon as possible. I chose GOlang for this task, you can find repository on GitHub. I added there some `content generator`, and package `lib` with config contant:

``````const (
MovieCategoriesNumber = 30
UsersNumber           = 50000
MaxPredictCategories  = 10
NearestNeighborsPart  = 1000
)
``````

I thought that it will be great if I can use multithreading (goroutines) for this task, so I added `NearestNeighborsPart` constant which determines the size of the batch. Before k-Nearest-Neighbors starts count the model - it splits whole model in a few batches and run them in separate threads. Then the results are joined into one model.

At the end I have some benchmarks:

• Benchmark with goroutines: 179.898931ms
• Benchmark without goroutines: 495.25129ms
• Benchmark with the same number of users and categories in Ruby: 1.586181sec

It's almost 10x faster than implementation in Ruby. Goroutines can give a kick for application performance, and at the same time are easy to implement, I recommend trying them out!