<jupyter_start><jupyter_text>Learning ObjectivesWe learn about KNN, our first real ML algorithm today and we show how it fits into the parts of an ML algorithm that we described earlier.<jupyter_code>from sklearn.datasets import load_iris

iris_data = load_iris()
print iris_data['DESCR']
print iris_data['data'].shape
print iris_data['target'].shape
print iris_data['feature_names']
print iris_data['target_names']<jupyter_output>(150, 4)
(150,)
['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']
['setosa' 'versicolor' 'virginica']<jupyter_text>KNNK-Nearest Neighbors is the first fully fledged machine learning algorithm that we will be studying in class. KNN is a non-parametric model, it has no parameters, it can be simply described as a strategy:For each point X we will find its K nearest neighbors in the training set, and return their average y value as our prediction.Thus KNN.In order to fully understand KNN and any ML algorithm we can go back to the drawing board. Let's return to our assumptions and check to see what a machine learning algorithm entails:<jupyter_code>import networkx as nx
from nxpd import draw
from nxpd import nxpdParams
nxpdParams['show'] = 'ipynb'

c0 = 'Unknown target function, f(X) = y'
c1 = 'Inputs, (x_1, y_1), ..., (x_n, y_n)'
c2 = 'Learning Algorithm'
c3 = 'Hypothesis set, H'
c4 = 'Final Hypothesis, g(X) = y'
c5 = 'IID samples from a r.v. X'

G = nx.DiGraph()
G.add_node(c0)
G.add_node(c1)
G.add_edge(c0, c1)
G.add_node(c2)
G.add_edge(c1, c2)
G.add_node(c3)
G.add_edge(c3, c2)
G.add_node(c4)
G.add_edge(c2, c4)
G.add_node(c5)
G.add_edge(c5, c1)
draw(G)<jupyter_output><empty_output><jupyter_text>To do that we can refer back to our assumptions. So the machine learning algorithm is composed of three parts of the above diagram:0. Inputs1. Hypothesis Set2. Learning Algorithm3. Final HypothesisOf course the unknown target function is instrumental in the success of the algorithm in general. Specifically we would like if the unknown target function is in the hypothesis set, that way there is a chance we can find the real target function, but we would be happy if there is one 'close enough' in the hypothesis set.   Inputs and OutputsThis might seem odd that we include the inputs as a description of machine learning algorthm but this is very important. The first point to mention is that each machine learning algorithm is for a specific type of output: quantitative or qualitative. Certain machine learning algorithms are specifically for qualitative outputs and some for quantitative (and some for both). KNN can be both a classifier and a regressor, we will be focusing on the classification today.The second concern is about the inputs. Some models need very specific inputs. So for example, or KNN can only take quantitative features, so we need to make sure to convert all the values to quantitative ones before the regression. The second point that needs to be made is whether the data needs to be standardized. KNN is very particular about standardization. Remember the first part of the algorithm in KNN, we select the closest K points to our new datapoint. But that is very dependent the dimensions of your data.So for example you could have two factors: Wealth and Age. If wealth is always in the 1000s and age is always less and a hundred, the nearest other data points will be nearest in terms of wealth and KNN will pretty much ignore age. What is generally better is to standardize them both: subtract the mean and divide by the variance. This will put all points on a similar scale.That being said, subject matter experts might have a better way to standardize the data points (espicially if certain factors are more important than others). In summary two points:1. KNN can be both a classifier and a regressor2. KNN inputs need to be standardized  Hypothesis SetThis is the first time that we have seen a real machine learning algorithm, so the hypothesis set is harder to decipher. The previous algorithms we have seen have had just a set of hypotheses (you could count and point at them). This is a bit harder to understand.What is hard to understand about this is that in this algorithm we rely on the data. Once we have the data we will in fact only have one hypothesis, so you may be tempted to say that our set of hypotheses is one: just the KNN algorithm. But in fact we need to consider the set of hypotheses before we see the data. How many different hypotheses could we have?Well let's consider the simplest case, where k is 1 and we have a single data point. In this case we would classify every new point as our previous point. So how many possible hypotheses could we have, well the point could be anything, so infinite hypotheses. Wow!This infinity grows as the number of data points increases, and we get a power set of infinities. Ultimately what you need to know is that the KNN hypothesis set is very very big.   Learning AlgorithmThe learning algorithm for KNN, the way that KNN selects its final hypothesis, is that it looks at an memorizes the data. It is very quick but not so memory efficient. The best hypothesis is embedded in the algorithm itself.  Final HypothesisThe final hypothesis is gotten by memorizing the dataset and then for each new point looking for the nearest points in the data set. Unlike many other algorithms it takes longer to use the KNN final hypothesis than it does to find it. This is a defining part of KNN and non-parametric models in general and is one of the points to remember  ConclusionThere are three important things to know about KNN:1. You will need to standardize the data2. KNN has a very large hypothesis set, which as we will see later on leads to overfitting3. KNN is quick to train and slow to evaluate  Bonus factNow this will generally encapsulate all of the relevant information for an algorithm, but sometimes there is an extra bit of material that you should know before you use it. The extra bit of information is that KNN does not perform well as we increase the dimensionality of the data.This is called the curse of dimensionality. The intuitive explination of this is that as the dimensionality increases it becomes harder to find a truely similar data point. Think about it, if you needed to find a match for every gene that you have, you would need to look through a lot of other people, but if we are just matching blood type, it becomes easier.The non-intuitive explanation is that as we increase K the hypotheses set increases dramatically leading to more intense overfitting and worse out of sample performance.  SklearnOkay so with no further ado let's use this bad boy in practice. Let's start off with a sklearn KNN classification:<jupyter_code>from sklearn.neighbors import KNeighborsClassifier
# and then we can do nearly the same thing

# we make our classifier here
cls = KNeighborsClassifier(n_neighbors=3, weights='uniform')
cls.fit(iris_data['data'], iris_data['target'])
cls.predict(iris_data['data'][4, None])
cls.score(iris_data['data'], iris_data['target'])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.04687941259531206, 'fraction_numerical': 0.006636543349336345, 'mean_word_length': 4.777324632952691, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '487915', 'license': 'MIT', 'n_tokens_mistral': 1883, 'n_tokens_neox': 1808, 'n_words': 1114, 'path': 'practicals/10.KNN.ipynb', 'repo_name': 'marxcerqueira/ds-foundations', 'size': '7082'}