Welcome to Data Analytics Foundations for Accountancy II! I'm excited to have you in the class and look forward to your contributions to the learning community. To begin, I recommend taking a few minutes to explore the course site. Review the material we’ll cover each week, and preview the assignments you’ll need to complete to pass the course. Click Discussions to see forums where you can discuss the course material with fellow students taking the class. If you have questions about course content, please post them in the forums to get help from others in the course community. For technical problems with the Coursera platform, visit the Learner Help Center. Good luck as you get started, and I hope you enjoy the course!
Introduction to k-nn
Loading...
From the course by University of Illinois at Urbana-Champaign
Data Analytics Foundations for Accountancy II
3 ratings
From the lesson
Module 1: Introduction to Machine Learning
This module provides the basis for the rest of the course by introducing the basic concepts behind machine learning, and, specifically, how to perform machine learning by using Python and the scikit learn machine learning module. First, you will learn how machine learning and artificial intelligence are disrupting businesses. Next, you will learn about the basic types of machine learning and how to leverage these algorithms in a Python script. Third, you will learn how linear regression can be considered a machine learning problem with parameters that must be determined computationally by minimizing a cost function. Finally, you will learn about neighbor-based algorithms, including the k-nearest neighbor algorithm, which can be used for both classification and regression tasks.
Meet the Instructors
Robert BrunnerProfessor
Accountancy
Hello. This lesson we're going to introduce one of
the first machine learning algorithms that we'll be discussing in more detail.
In particular, it's the k-nearest neighbors or k-nn algorithm.
This algorithm is important for a couple of reasons.
First of all, it's a very simple algorithm to understand.
And second of all, it's known as a lazy evaluator or non-parametric technique
that simply uses the properties of
the training data to make predictions about new test data.
The key aspect here is that we don't actually build a model with this algorithm.
Instead, it uses the training data during
the prediction phase to quantify or make predictions about that new data.
So, by the end of this lesson,
you should be able to articulate what's going on with the k-nearest neighbor algorithm.
You should also be able to apply a k-nearest neighbor algorithm for
classification or regression tasks by using the Scikit-learn Library.
And you should know where you can apply this algorithm
successfully and where you probably need to use a different algorithm.
Now, the entirety of this lesson is
contained in the introduction to k-nearest neighbors notebook.
So what is this notebook going to do?
Well, we're going to talk about this algorithm,
and we're going to move on to other ideas that are
applicable to other algorithms as well because
the k-nn provides a nice demonstration of some of these.
So, what is this k-nn algorithm?
If you think about the way where data comes from,
you can understand that often,
data points that are near each other are related.
I like to use the example of people.
If you think about people who are similar to you,
you typically live near people that are similar to you either because of income,
educational level or religious or political beliefs.
Thus, if you take a census and you look at people that live in the same neighborhood,
there's often a lot of similarities between those people.
Thus if somebody new moves into that neighborhood,
and you want to understand what are they probably like,
the easiest thing to do is to average over their neighbors.
Now, as you add more neighbors,
you can sometimes get a more accurate prediction.
But on the other hand if you start going too far away,
you may start getting other neighborhoods that
have other properties and you may lose accuracy,
so that number of neighbors or distance that you expose
your algorithm to making predictions can be important.
So, what are some things that we have to understand?
First, we have to understand how to compute distances,
and there's actually different ways to compute distances,
that will be important in trying to find the nearest neighbors.
We'll also have to look at something known as the curse of dimensionality.
And the reason we talk about that is because usually
you would think as you add more and more features or dimensions to your data,
you'll be able to make bigger predictions.
But, sometimes that can actually slow down
the computations because it becomes harder and harder to, in this case,
find nearest neighbors or alternatively,
you have to get more and more training data to adequately
sample the space that your data actually can occupy.
So, we'll do this by talking about some of those basic concepts.
We will introduce the idea of Helper code,
and I put these in a separate file that you can open.
But we're not going to go into too much detail,
they basically do things like load data,
do some of that pre-processing,
maybe they make visualization plots.
Then we'll look at k-nearest neighbors for classification.
For that, we're going to talk about some performance metrics,
we're going to talk about some of the hyper-parameters that might be important.
And then we're going to go on and look at regression.
So we start with our standard import,
and then we move into the actual formalism of this method.
So what I'm doing here is I'm actually generating some data,
and I'm transforming it into a different space and making a plot.
So here, I have our data and I say show me the five nearest neighbor.
So here's my green point.
That's my special point.
Might say this, blue are all the training data and green is now a test data point,
and I say find me the five nearest neighbors.
And you can see here's the five nearest neighbors.
If I had only said four,
then perhaps this point would have been picked.
And if I had said six,
probably this point would have been picked.
And as you see, as the number of neighbors changes,
the radius of a circle centered on
our test point will get bigger and include more and more points.
And we'll be averaging over a greater area.
That can be both good and bad,
and that's one of the reasons the number of
neighbors is a hyper-parameter that we have to tune.
Next step is what are distance measurements?
Typically, you might just say we'll use a Pythagorean theorem: x squared minus x1,
x2 minus x1 quantity square plus y2 minus y1 quantity squared square root.
You've seen that for years,
but that's really only applicable for data that followed the Euclidean Distance Metric.
And so if you've plotted points on a Cartesian plot,
that would be a good example of where you would do that.
But you might want to do something different for other types of data.
If it's currency data or even categorical or text data,
what kind of distances would you use?
For this, we define the idea of a metric
which is how do you measure distance for a particular type of data.
And there's a number of different metrics.
One is the Euclidean that we saw,
that's the, what we know as the L2-norm.
Another is Manhattan, and this is where you restrict distances to be on grid lines.
So if you think about it the idea this came from
taxicab distance on the island of Manhattan where the streets are all laid out in a grid,
one block square, and you had to stay on the streets.
You couldn't drive through buildings and so
the idea of this then is known as the L1-norm.
There's also some other ones I mentioned a few here, the haversine.
This is for distances traveled on the surface of a sphere.
If you've ever seen the the path of
an airline will take traveling on a flat map, it looks curved.
The reason for that is because it's actually
traveling across the surface of a sphere of the earth.
So when you flatten that out,
it actually the shortest distance between New York and
Los Angeles or San Francisco and Beijing,
is actually a curved path,
and we use the haversine metric for that.
Then there's some other ones, the Chebyshev and the Minkowski, as well as others.
And so we demonstrate calculating these in this particular code cell and you
should get a little familiar with this because it may be a little different for you.
So for instance, Euclidean distance, you should understand that.
The Manhattan distance, you're just summing up
the block travel times or travel distances,
the Chebyshev, the Minkowski.
I mentioned briefly here with the Curse of Dimensionality,
as the number of dimensions grows,
the number of points we have to have to maintain the
same sampling density jumps very fast.
And that of course is a problem.
So we can look at this in terms of a visualization and say well,
what's the relative density if we keep the number of points the
same as the number of dimensions increases what's our relative density?
And you can see that it very quickly drops.
So, really if you have a very high dimensional dataset,
you need a lot of training data to sufficiently span
that space to be able to make accurate predictions for new unseen data.
We talk a little bit about the Helper Code,
you can read about this and understand it.
There's a few functions I've created that load
the data and do some pre-processing for it or make plots.
We demonstrate one of them here.
We're importing from our Helper code and calling a function on it here to get the data.
This loads the data and splits it into training and testing,
and makes this plot.
So you can see here's the class 0,1,2,
that's the setosa, versicolor and virginica.
We also have some test data to show
data where the test data comes from and we can analyze this.
So the next thing is k-nearest neighbors again. How do we use this?
We import our module,
we create our estimator,
we get our testing and training data,
and then we fit our model to this training data,
and then we can make predictions on our test data.
So here we go. This is it.
Right? We saw this in
the first lesson notebook where we did the introduction to Machine Learning,
demonstrated classification with k-nearest neighbor classifier.
We specified one hyper-parameter,
the number of neighbors,
we fit the model and we score the model.
That's very simple. We can also try changing a few things.
We can look at the Confusion matrix.
So here we are going to explicitly make predictions for our test data,
and we're going to then see how well do we do on a per class basis.
And this is called a Confusion Matrix.
So each row is a different predicted class,
each column is the actual class.
I've made a convenience function called confusion,
which will plot this.
So it's a little easier to see but it was the same data.
So here you can have the predicted label and
the true label and you can see the relationship between them.
We can also measure other metrics such as precision and recall or F1 score.
And this talks about that these can be generated and displayed on
a per class basis with something called the classification report.
And that's demonstrated here,
where we see how well do our model
perform for the different classes as well as an average score.
The support is the number of test data points in each class,
and you can see those are all roughly the same.
The last thing I want to show you here about
classification is the idea of decision surfaces,
and how they can be used to understand the impact of hyper-parameters.
For the nearest neighbor algorithm,
we typically vary the neighbor hyper-parameter which might be two, three, four, five.
So this code here simply makes different plots of a decision surface.
And here's an example of that.
We've restricted ourselves to two dimensions,
Sepal width and Petal width.
Here's the data that we actually are predicting on.
Underneath it is a grid of points and you can see the colors change as we move around.
This is known as a Decision Surface because it
tells us if we put a desk data point right here,
a test data point, what would it be classified as.
And in this case, you can see it's going to be blue.
If it was over here it would be green and if it's over here it was brown.
So it shows you how these this algorithm is splitting up this underlying space.
Now, this was for three nearest neighbors.
If I change it to five nearest neighbors,
you'd notice that changes dramatically.
Right? Look up here, this is very different than what we had up here.
And it changes a little bit over here as well.
The idea of the decision surface is it shows you the impact of
a hyper parameter on making predictions in the general space that you're looking at.
So it's a good way to try to figure out what's a good value
for a hyper parameter if you don't want to resort to just scoring.
And then here we've increased it to nine,
and again it's changed things just slightly.
Notice now we have these two values here that are predicted right.
There's other things you can look at.
One of them is called weights.
This says for instance you may want to say if a data points close to me,
I want to give it a higher weight.
Data points that are farther away are going to be less so.
So we can do the same thing.
Here we're going to change weighing scheme from
uniform where all data has the same weight.
Alternatively, we could say we're going to weigh points by how far away they are from us.
So if they're farther away they have a lower weight.
And so we can look at the decision surface in this case,
here is uniform weighting.
This is the same plot we saw before for three nearest neighbors,
and then we can look at distance weighting and you could see how it changes.
Notice that this point is now correctly classified, and this one is as well.
This is the only one that's not.
That's interesting in how that all works,
and probably gives you a bit of a feel for why decision surfaces are important.
So the next thing is regression,
k-nearest neighbor for regression,
very similar to classification.
We simply change our estimator, we get our data.
In this case we're just going to make a plot of the values,
and then we're going to show how the regression works.
So here's some data points.
Here's the k-nearest neighbor regressor for five with a uniform weighting,
and here's five with a uniform distance,
just to give you an introduction to regression here in this particular case.
So with that I'm going to go ahead and stop.
If you have any questions let us know.
K-nearest neighbor, very simple algorithm,
should give you a pretty good feel for how things work.
If you have any questions, let us know. And good luck.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
