Hey, everyone.

Welcome back.

In this episode, we're going to do something special,

and that's write our own classifier from scratch.

If you're new to machine learning,

this is a big milestone.

Because if you can follow along and do this on your own,

it means you understand an important piece of the puzzle.

The classifier we're going to write today

is a scrappy version of k-Nearest Neighbors.

That's one of the simplest classifiers around.

First, here's a quick outline of what we'll do in this episode.

We'll start with our code from Episode 4, Let's

Write a Pipeline.

Recall in that episode we did a simple experiment.

We imported a data set and split it into train and test.

We used train to train a classifier,

and test to see how accurate it was.

Writing the classifier is the part

we're going to focus on today.

Previously we imported the classifier

from a library using these two lines.

Here we'll comment them out and write our own.

The rest of the pipeline will stay exactly the same.

I'll pop in and out of the screencast to explain things

as we go along.

To start, let's run our pipeline to remind ourselves

what the accuracy was.

As you can see, it's over 90%.

And that's the goal for the classifier

we'll write ourselves.

Now let's comment out that import.

Right off the bat, this breaks our code.

So the first thing we need to do is fix our pipeline.

And to do that, we'll implement a class for our classifier.

I'll call it ScrappyKNN.

And by scrappy, I mean bare bones.

Just enough to get it working.

Next, I'll change our pipeline to use it.

Now let's see what methods we need to implement.

Looking at the interface for a classifier,

we see there are two we care about-- fit,

which does the training, and predict,

which does the prediction.

First we'll declare our fit method.

Remember this takes the features and labels for the training set

as input, so we'll add parameters for those.

Now let's move on to our predict method.

As input, this receives the features for our testing data.

And as output, it returns predictions for the labels.

Our first goal is to get the pipeline working,

and to understand what these methods do.

So before we write our real classifier,

we'll start with something simpler.

We'll write a random classifier.

And by random, I mean we'll just guess the label.

To start, we'll add some code to the fit and predict methods.

In fit, I'll store the training data in this class.

You can think of this as just memorizing it.

And you'll see why we do that later on.

Inside the predict method, remember

that we'll need to return a list of predictions.

That's because the parameter, X_test, is actually

a 2D array, or list of lists.

Each row contains the features for one testing example.

To make a prediction for each row,

I'll just randomly pick a label from the training data

and append that to our predictions.

At this point, our pipeline is working again.

So let's run it and see how well it does.

Recall there are three different types of flowers

in the iris dataset, so accuracy should be about 33%.

Now we know the interface for a classifier.

But when we started this exercise,

our accuracy was above 90%.

So let's see if we can do better.

To do that, we'll implement our classifier,

which is based on k-Nearest Neighbors.

Here's the intuition for how that algorithm works.

Let's return to our drawings of green dots and red dots

from the last episode.

Imagine the dots we see on the screen

are the training data we memorized in the fit method,

say for a toy dataset.

Now imagine we're asked to make a prediction for this testing

point that I'll draw here in gray.

How can we do that?

Well in a nearest neighbor classifier,

it works exactly like it sounds.

We'll find the training point that's

closest to the testing point.

This point is the nearest neighbor.

Then we'll predict that the testing

point has the same label.

For example, we'll guess that this testing dot is green,

because that's the color of its nearest neighbor.

As another example, if we had a testing dot over here,

we'd guess that it's red.

Now what about this one right in the middle?

Imagine that this dot is equidistant to the nearest

green dot and the nearest red one.

There's a tie, so how could we classify it?

Well one way is we could randomly break the tie.

But there's another way, and that's where k comes in.

K is the number of neighbors we consider

when making our prediction.

If k was 1, we'd just look at the closest training point.

But if k was 3, we'd look at the three closest.

In this case, two of those are green and one is red.

To predict, we could vote and predict the majority class.

Now there's more detail to this algorithm,

but that's enough to get us started.

To code this up, first we'll need a way

to find the nearest neighbor.

And to do that, we'll measure the straight line

distance between two points, just like you do with a ruler.

There's a formula for that called the Euclidean Distance,

and here's what the formula looks like.

It measures the distance between two points,

and it works a bit like the Pythagorean Theorem.

A squared plus B squared equals C squared.

You can think of this term as A, or the difference

between the first two features.

Likewise, you can think of this term as B,

or the difference between the second pair of features.

And the distance we compute is the length of the hypotenuse.

Now here's something cool.

Right now we're computing distance

in two-dimensional space, because we have just two

features in our toy dataset.

But what if we had three features or three dimensions?

Well then we'd be in a cube.

We can still visualize how to measure distance

in the space with a ruler.

But what if we had four features or four dimensions,

like we do in iris?

Well, now we're in a hypercube, and we

can't visualize this very easy.

The good news is the Euclidean Distance

works the same way regardless of the number of dimensions.

With more features, we can just add more terms to the equation.

You can find more details about this online.

Now let's code up Euclidean distance.

There are plenty of ways to do that,

but we'll use a library called scipy that's

already installed by Anaconda.

Here, A and B are lists of numeric features.

Say A is a point from our training data,

and B is a point from our testing data.

This function returns the distance between them.

That's all the math we need, so now

let's take a look at the algorithm for a classifier.

To make a prediction for a test point,

we'll calculate the distance to all the training points.

Then we'll predict the testing point has the same label

as the closest one.

I'll delete the random prediction we made,

and replace it with a method that finds the closest training

point to the test point.

For this video hard, I'll hard-code k to 1,

so we're writing a nearest neighbor classifier.

The k variable won't appear in our code,

since we'll always just find the closest point.

Inside this method, we'll loop over all the training points

and keep track of the closest one so far.

Remember that we memorized the training data in our fit

function, and X_train contains the features.

To start, I'll calculate the distance from the test point

to the first training point.

I'll use this variable to keep track of the shortest

distance we've found so far.

And I'll use this variable to keep

track of the index of the training point that's closest.

We'll need this later to retrieve its label.

Now we'll iterate over all the other training points.

And every time we find a closer one,

we'll update our variables.

Finally, we'll use the index to return

the label for the closest training example.

At this point, we have a working nearest neighbor classifier,

so let's run it and see what the accuracy is.

As you can see, it's over 90%.

And we did it.

When you run this on your own, the accuracy

might be a bit different because of randomness in the train test

split.

Now if you can code this up and understand it,

that's a big accomplishment because it

means you can write a simple classifier from scratch.

Now, there are a number of pros and cons

to this algorithm, many of which you can find online.

The basic pro is that it's relatively easy to understand,

and works reasonably well for some problems.

And the basic cons are that it's slow,

because it has to iterate over every training point

to make a prediction.

And importantly, as we saw in Episode 3,

some features are more informative than others.

But there's not an easy way to represent

that in k-Nearest Neighbors.

In the long run, we want a classifier

that learns more complex relationships between features

and the label we're trying to predict.

A decision tree is a good example of that.

And a neural network like we saw in TensorFlow Playground

is even better.

OK, hope that was helpful.

Thanks as always for watching.

You can follow me on Twitter for updates and, of course,

Google Developers.

And I'll see you guys next time.

[MUSIC PLAYING]