<jupyter_start><jupyter_text>K-Nearest Neighbor* Lets now discuss a very simple, and very intuitive method for machine learning: K-Nearest Neighbor* The basic premise is to make a prediction using the closest known data points ![r_knn_concept.png](attachment:r_knn_concept.png) Implementation  KNN - 1 * Although the concept for K-Nearest Neighbor is simple, the implementation can be complex* 1 - nearest neighbor is simple, since we just need to keep track of the minimum distance ![knn%201.png](attachment:knn%201.png) KNN - Multiple neighbors* keeping track of an arbitrary number of closest distances is not trivial * For examples: > * say we have found 3 data points that are [1, 2 ,3] away, and k = 3  * and we see the next training point and it is at a distance of 1.5 away  * how do we check to see if it should go into the set of the 3 closest data points that we have so far?  * First, lets consider that if we have N training points, then we need to look through all of them for every prediction we want to make! This is **O(N)**  * If we take the Naive approach and look through each of the K closest points we have found so far, to see if we should remove the closest one, and add a closer point, thaat is **O(K)**  * this gives a total of **O(NK)**  * However, as you should know searching a list does not need to be **O(K)**  * In fact, if we are able to keep a sorted list, we can make the search **O(logK)**, which is a bit better  * There are even better ways to optimize this, such as athe Ball Tree and K-D Tree, but they are outside the scope of this course  * Once we have our k-nearest neighbors, the next step is to turn them into votes   * This should make us realize that not only do we need to store the closest distances, we need to store their corresponding classes as well  * This is like a dictionary, or a list of tuples, where the key is the distances, and the value is the class      * {dist1: class 1, dist2: class2,...} or [(dist1, class1),(dist2, class2),...]  * once we have collected the k nearest neighbors, all we need to do is create another dictionary, where the class is the key, and the number of times it appears is the value  * We finally just chose the class with the maximum number of votes      Breaking Ties      * one question that may arise is, what if we end up with a tie?       * in this case we have several options:      * the simplest case is to just take whatever the argmax(votes) gives us. We don't know how argmax() is implemented, so it is up to the implementation      * Another way is to just pick at random       * A final option is to weight each distance from the neighbor to the test point (more difficult)      * In our case we are going to loop through the dictionary manually and choose the first max      * therefore it depends on how keys of dictionaries are hashed in python  How is K chosen?* No easy answer* K is called a "hyperparameter"* going to want to use cross validation!  Lazy Classifier * KNN is an example of a lazy classifier * train(X,Y) doesn't do anything! It just store X and Y* predict(X') does all the work by looking through the stored X and Y  ---- KNN in code with MNIST* lets now take some time to implement KNN in code, and implement it on the MNIST data set* before getting into that though, lets just quickly look through the data set to get a feel for what it looks like![data.png](attachment:data.png)<jupyter_code>import pandas as pd
df = pd.read_csv('data/train.csv')
df.head()
df.shape<jupyter_output><empty_output><jupyter_text>We can see that this data is comprised of 42000 examples, and has 785 columns/input vectors. We should think about the problem in the following way:* Each image (42,000 total) is a single training point.* Each image (1 training point) is composed of 784 input features* these input features are intensity values from 0..255* the first column is the label associated with its image training point* 784 + 1 = 785, hence why we have 785 columns  Time to implement...* for this we are going to needs the `sortedcontainers` library* Quickly, lets look over the `getData` function* this uses pandas to make reading the csv input, just one line* we then use `asmatrix` to turn the data into a numpy array* we shuffle the data so that when we sample it later, it is in a random order* we normalize the data to 0-1* X is all the image data* Y is the first column, the labels<jupyter_code>import numpy as np
import pandas as pd

def get_data(limit=None):
    print("Reading in and transforming data...")
    df = pd.read_csv('data/train.csv')
    data = df.as_matrix()
    np.random.shuffle(data)
    X = data[:, 1:] / 255.0 # data is from 0..255
    Y = data[:, 0]
    if limit is not None:
        X, Y = X[:limit], Y[:limit]
    return X, Y
from sortedcontainers import SortedList
from datetime import datetime<jupyter_output><empty_output><jupyter_text>Create KNN class<jupyter_code>class KNN(object):
    def __init__(self, k):
        self.k = k
    
    # this is our train function
    # takes in X and y, which are the inputs and the targets
    # because this is a lazy classifer, all the fit method does is save X and y
    def fit(self, X, y):
        self.X = X
        self.y = y
        
    # this only takes in X
    def predict(self, X):
        
        # need a prediction for every input (42,000 in this case)
        y = np.zeros(len(X))
        
        # loop through every X row, so for each iteration (index i) x has a shape (784,1) since its a row vector
        # aka here we are just going through each training example (an image)
        # these are all of the inputs that we want to predict
        for i, x in enumerate(X):
            
            # now we create a sorted list - because this is meant to store our k nn, it must be size k
            sl = SortedList()
            
            # for each input test point we have to look through all of the training points to find the knn
            # Note: X is the data we wish to make predictions on, and self.X is the data that we are using 
            # to determine knn - they can be thought of the data we are using to help make our prediction
            # So, in other words what is happening here is that for each input image, we have to loop through all 
            # of the training points, to find the knn
            # so j is the index, xt is the training point (remember, that is a 784x1 row vector)
            for j, xt in enumerate(self.X):
                
                # this is a (784,1) - (784,1), and it will be done for every training image in comparison the 
                # current image we are trying to predict
                # diff is also (784, 1)
                diff = x - xt
                
                # here we use the squared distance, instead of euclidean distance -> results in a single scalar value
                d = diff.dot(diff)
                
                # make a comparison to see if there are k values in list
                if len(sl) < self.k:
                    sl.add((d, self.y[j]))
                
                # check to see if the current value (need to use [-1] to get last item, and [0] to get the 
                # distance. If it was [-1][1] then would have grabbed the last label, not distance value) 
                else: 
                    if d < sl[-1][0]:
                        del sl[-1]
                        sl.add((d, self.y[j]))


            # Now we need to collect all of the votes - so we create a dictionary called votes
            votes = {}
            
            # loop through the list of the knn. We don't care about the first element, only the second element
            # since that is the class. votes.get simply grabs the value of the hash for key v 
            for _, v in sl:
                votes[v] = votes.get(v, 0) + 1
            
            # now votes contains the class, and the count has the value
            max_votes = 0
            max_votes_class = -1
            
            # finally loop through all of our votes, and if this vote is greater than our current max vote, 
            # then we make our current max votes equal to the current votes
            for v, count in votes.items():
                if count > max_votes:
                    max_votes = count
                    max_votes_class = v
                    
            y[i] = max_votes_class
        return y
            
        
    # similar to scikit learn method, takes in X and y, makes a prediction on X, and returns accuracy
    def score(self, X, Y):
        P = self.predict(X)
        return np.mean(P == Y)            
if __name__ == '__main__':
    
    X, Y = get_data(2000)
    Ntrain = 1000
    Xtrain, Ytrain = X[:Ntrain], Y[:Ntrain]
    Xtest, Ytest = X[Ntrain:], Y[Ntrain:]
    
    # loop through multiple values of k 
    for k in (1,2,3,4,5):
        
        # create a model with k nearest neighbors
        knn = KNN(k)
        print('K: ', k )
        
        # set timer to see how long it takes knn to fit the training data
        t0 = datetime.now()
        knn.fit(Xtrain, Ytrain)
        print ("Training Time: ", (datetime.now() - t0))
        
        # now get training accuracy and time this as well
        t0 = datetime.now()
        print ("Train accuracy:", knn.score(Xtrain, Ytrain))
        print("Time to compute train accuracy:", (datetime.now() - t0), "Train size:", len(Ytrain))
        
        # now print test accuracy
        t0 = datetime.now()
        print ("Test accuracy:", knn.score(Xtest, Ytest))
        print("Time to compute test accuracy:", (datetime.now() - t0), "Test size:", len(Ytest))
        print('-----------------------------------------------------------------------')<jupyter_output>Reading in and transforming data...
K:  1
Training Time:  0:00:00.000012
Train accuracy: 1.0
Time to compute train accuracy: 0:00:20.694450 Train size: 1000
Test accuracy: 0.883
Time to compute test accuracy: 0:00:25.591816 Test size: 1000
-----------------------------------------------------------------------
K:  2
Training Time:  0:00:00.000005
Train accuracy: 1.0
Time to compute train accuracy: 0:00:20.438604 Train size: 1000
Test accuracy: 0.883
Time to compute test accuracy: 0:00:25.622225 Test size: 1000
-----------------------------------------------------------------------
K:  3
Training Time:  0:00:00.000007
Train accuracy: 0.95
Time to compute train accuracy: 0:00:20.718641 Train size: 1000
Test accuracy: 0.887
Time to compute test accuracy: 0:00:25.456866 Test size: 1000
-----------------------------------------------------------------------
K:  4
Training Time:  0:00:00.000005
Train accuracy: 0.952
Time to compute train accuracy: 0:00:20.475038 Train size: 1000
Test accurac[...]<jupyter_text>--- When K-Nearest Neighbors can fail* Lets now look at some data where KNN can fail* We want to do this so we can have a good understanding of the weakness of the model* Think of a grid of alternating dots* If we do 3 nearest neighbor, we are always going to get a 2 out of 3 vote for the other class* Why is that?* Well, assuming that we use all of the data as training data, then the closest point will be itself* However, the next two points will be the other class, since we have alternating classes. This means we will always vote against the true class* We could of course circumvent this by doing some kind of weighting metric, or doing 1 nearest neighbor, or weighting out each point by distance* Lets plot this out to make it a bit more clear!<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
def get_data_2():
    width = 8 
    height = 8
    N = width * height
    X = np.zeros((N,2))
    Y = np.zeros(N)
    n = 0
    start_t = 0
    for i in range(width):  # looping through each column
        t = start_t
        for j in range(height):  # looping through each row
            X[n] = (i, j)  # setting the specific point 
            Y[n] = t
            n += 1
            t = (t + 1) % 2
        start_t = (start_t + 1) % 2
    return X, Y
if __name__ == '__main__':

    X, Y = get_data_2()
    fig, ax = plt.subplots(figsize=(12,8))

    # X[:, 0] = x values, aka the columns, X[:, 1] = y values, aka the rows
    plt.scatter(X[:, 0], X[:, 1], s=100, c=Y, alpha=1, cmap='bwr')
    plt.show()
    
    model = KNN(3)
    model.fit(X, Y)
    print("Train Accuracy:", model.score(X,Y))<jupyter_output><empty_output><jupyter_text>As we can see, our final training accuracy was 0%! --- KNN for the XOR problem* we are not going to solve the XOR problem for only 4 inputs, as we did with logistic regression, since we know that KNN cannot solve that* But, we think of the grid above as an expanded XOR!* we will now treat anything above 0.5 and less than 1 as true, and anything below 0.5 and above 0 as false<jupyter_code>def get_xor():
    X = np.zeros((200, 2))
    X[:50] = np.random.random((50, 2)) / 2 + 0.5 # (0.5-1, 0.5-1)
    X[50:100] = np.random.random((50, 2)) / 2 # (0-0.5, 0-0.5)
    X[100:150] = np.random.random((50, 2)) / 2 + np.array([[0, 0.5]]) # (0-0.5, 0.5-1)
    X[150:] = np.random.random((50, 2)) / 2 + np.array([[0.5, 0]]) # (0.5-1, 0-0.5)
    Y = np.array([0]*100 + [1]*100)
    return X, Y
if __name__ == '__main__':
    X, Y = get_xor()
    
    fig, ax = plt.subplots(figsize=(12,8))
    plt.scatter(X[:, 0], X[:, 1], s=150, c=Y, alpha=0.5, cmap='bwr')
    plt.show()
    
    model = KNN(3)
    model.fit(X, Y)
    print("Train Accuracy:", model.score(X,Y))<jupyter_output><empty_output><jupyter_text>--- KNN for the DONUT problem * the donut problem is where we have one class inside of another class* we know that linear classifiers cannot solve this problem either, becuase there is not line that separates the two classes *<jupyter_code>def get_donut():
    N = 200
    R_inner = 5
    R_outer = 10

    # distance from origin is radius + random normal
    # angle theta is uniformly distributed between (0, 2pi)
    R1 = np.random.randn(N//2) + R_inner
    theta = 2*np.pi*np.random.random(N//2)
    X_inner = np.concatenate([[R1 * np.cos(theta)], [R1 * np.sin(theta)]]).T

    R2 = np.random.randn(N//2) + R_outer
    theta = 2*np.pi*np.random.random(N//2)
    X_outer = np.concatenate([[R2 * np.cos(theta)], [R2 * np.sin(theta)]]).T

    X = np.concatenate([ X_inner, X_outer ])
    Y = np.array([0]*(N//2) + [1]*(N//2))
    return X, Y
if __name__ == '__main__':
    X, Y = get_donut()
    
    fig, ax = plt.subplots(figsize=(12,8))
    plt.scatter(X[:, 0], X[:, 1], s=150, c=Y, alpha=0.5, cmap='bwr')
    plt.show()
    
    model = KNN(3)
    model.fit(X, Y)
    print("Train Accuracy:", model.score(X,Y))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10834125798125255, 'fraction_numerical': 0.030974052438527373, 'mean_word_length': 2.4183886696076153, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 27, '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': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '614177', 'license': 'MIT', 'n_tokens_mistral': 4642, 'n_tokens_neox': 4280, 'n_words': 2026, 'path': 'notebooks/Machine-Learning-Perspective/Supervised Machine Learning in Python/Section 2 - K Nearest Neighbor.ipynb', 'repo_name': 'NathanielDake/NathanielDake.github.io', 'size': '14722'}