"""
# Welcome to the Fashion-MNIST Challenge!

Website reference: https://github.com/zalandoresearch/fashion-mnist

**Author:** Gabriele Carbone

**Date:** 05/06/2021
"""
##################################################
# Imports
##################################################

import numpy as np
import cv2
import os
import pandas as pd
import matplotlib.pyplot as plt
import time
from sklearn.preprocessing import MinMaxScaler
from sklearn.neighbors import KNeighborsClassifier
from scipy.stats import entropy

##################################################
# Params
##################################################

DATA_BASE_FOLDER = '/kaggle/input/image-classification-fashion-mnist'

# Set seed
np.random.seed(0)

# Adjust the font type of the plots with the one in the document
plt.rcParams["font.family"] = "serif"
"""
# Dataset

The dataset contains 50k train + 10k validation images of 10 different categories ('T-shirt/top', 'Trouser', 'Pullover', 'Dress', 'Coat', 'Sandal', 'Shirt', 'Sneaker', 'Bag', 'Ankle boot').

Each image is a 28x28 grayscale, and for simplicity here is flattened into a 784 dimensional vector.
"""
##################################################
# Load dataset
##################################################

x_train = np.load(os.path.join(DATA_BASE_FOLDER, 'train.npy'))
x_valid = np.load(os.path.join(DATA_BASE_FOLDER, 'validation.npy'))
x_test = np.load(os.path.join(DATA_BASE_FOLDER, 'test.npy'))
y_train = pd.read_csv(os.path.join(DATA_BASE_FOLDER, 'train.csv'))['class'].values
y_valid = pd.read_csv(os.path.join(DATA_BASE_FOLDER, 'validation.csv'))['class'].values
y_labels = ['T-shirt/top', 'Trouser', 'Pullover', 'Dress', 'Coat', 'Sandal', 'Shirt', 'Sneaker', 'Bag', 'Ankle boot']

# Plot random images of different classes
plt.figure(figsize=(25, 5))
for idx in range(20):
    plt.subplot(1, 20, idx + 1)
    img = x_train[idx].reshape(28, 28)
    plt.title(f'{y_labels[y_train[idx]]}')
    plt.imshow(img, cmap='gray')
    plt.axis('off')
plt.show()
"""
# Processing Data

We transform the datasets into pandas DataFrame because it's easier to work with them
"""
x_train_df = pd.DataFrame(x_train)
x_valid_df = pd.DataFrame(x_valid)
x_test_df = pd.DataFrame(x_test)
"""
### Check for NA values

There are no observations with NA values
"""
print(x_train_df.isna().sum().sum())
"""
### Print Shapes

Print the shapes of the **3 dataset** (x_train_df, x_valid_df, x_test) and **2 target vectors** (y_train, y_valid)
"""
print(x_train_df.shape, 
      x_valid_df.shape, 
      x_test.shape, 
      y_train.shape, 
      y_valid.shape)
"""
### Classes' Frequency
The classes are very balanced, each of the classes has around the same portion of dataset (10%)
"""
unique, counts = np.unique(y_train, return_counts=True) # Count the unique values

y_class_fr = pd.DataFrame(counts, index = y_labels)
y_class_fr = y_class_fr.rename(columns={0: "Count"})   # Rename the columns

display(y_class_fr.transpose())                     # Display the count

y_class_fr.plot.bar(legend = False)     # Create a barplot
"""
### Feature Selection - Entropy Method

We have a **huge number of features** in the dataset (over 700), so we need to give a priority to them

We use the metric *entropy* to understand what features might carry more information (alias, we look for the pixel that are more important in the classification process)
"""
entropy = pd.Series(entropy(x_train))              #compute entropy for each parameter

entropy = entropy.reset_index()                    #reset the index

entropy = entropy.sort_values(ascending = False, by = 0)    #sort the values from the biggest to the smallest

entropy = entropy.rename(columns={0: "Entropy", "index": "Index"})   #rename the columns
"""
### Feature Scaling and Final Elaborations

In this notebook, we will fully test the K Nearest Neighbor model which is very sensible to the scale of the single features

Now, *all the values in the dataset are between 0 and 255*, so  - in theory - we should obtain good results even without scaling, but for good practice we will use a **standard MinMaxScaler** anyway
"""
#Scale the features
Scaler = MinMaxScaler()

x_train_scaled = Scaler.fit_transform(x_train_df)
x_valid_scaled = Scaler.fit_transform(x_valid_df)
x_test_scaled = Scaler.fit_transform(x_test_df)
"""
# kNN Model

The Fashion-MNIST Challenge is a **classification problem**, so using a kNN (aka k-Nearest Neighbors) can be a smart approach

kNN is a **non-parametric model** (meaning that doesn't use weights or parameters learning) that, intuitively, given a certain input searches for the most similar k observation and assign a class to the input based on the most popular one among them

From a mathematical point of view, the "similarity" is often computed using the l1-norm or the l2-norm (also called "euclidean distance")

The main advantage of kNN is the **almost non-existent time to train** (limited to the storing time) BUT **the prediction phase may take a while** because the algorithm needs to compare the input to all the observation in the dataset (for each input!)

## How does it works?

kNN takes as input the parameter values of the observation then computes the distances between the instance's value for a feature and the training set's value for the same feature, for each feature. Then the model process, depending on the norm used, these distances and output a number that represent the general "distance" of the the observation from that data point.

These results are ranked from the smallest (most similar observation of the training set) to the greatest (the least similar one).

Finally, the first k observation (called **"neighbors"**) are taken and given the "right" to vote for the class of a given instance.
"""
"""
![knn.PNG](attachment:18b3ba5a-7cfc-4bca-8eba-19eed2b9a33b.PNG)

*Source: https://hal.archives-ouvertes.fr/hal-01657491/document*

As you can see from the image, with 1 and 3 neighbors we assign the new data point (the black one) to the blue class, while with 5 and 7 neighbors we assign the new data point to the grey class.

**There is no optimal number of neighbors**, it depends on the specific context and dataset.
"""
"""
![](https://robocrop.realpython.net/?url=https%3A//files.realpython.com/media/knn_01_MLgeneral_wide.74e5e2dc1094.png&w=1512&sig=492d6c64473418b06336cebadf7eb78bb7662e12)

*Source: https://realpython.com/knn-python/*

From a mathematical point of view, in 2D we can imagine the kNN as **a model to create "dominance" maps** (also called "Voronoi Diagram Visualizations") were, *if an instance fall inside one of these intervals, then it's assigned to the dominant class.*

From the image above, you can see  a very simple case: for example, given that the majority of the data points in the top left side of the graph are stars then we will assign an hypotetichal new data point to "star" if it falls in that interval.

kNN is very powerful because it can create **extremely complex boundaries with simple math.**
For example, in the image below you can see the complexity of a real case study and how it changes based on the number of neighbors: usually, *if we have fewer neighbors the boundaries are more complex because they are more sensible* (it takes just a single data point to change the class!)
"""
"""
![knn - Copia.PNG](attachment:96789107-19c7-4f41-9f62-3382da19147c.PNG)

*Source: https://hal.archives-ouvertes.fr/hal-01657491/document*
"""
# This is the final optimized model, we will use this from the start in order to speed up the computing time

model = KNeighborsClassifier(n_neighbors = 4, 
                             weights = 'distance',
                             algorithm = 'brute', 
                             p = 2)
"""
### Testing the HyperParameters
For both accuracy (as the primary KPI) and speed (the secondary KPI)
"""
# Compute the accuracy of the model

def accuracy(y_pred, y_true):
    '''
    input y_pred: ndarray of shape (N,)
    input y_true: ndarray of shape (N,)
    '''
    return (1.0 * (y_pred == y_true)).mean()
# Evaluate the model and append the accuracy and speed to the given lists
# N is the number of observations
# D is the number of parameters
# V is the number of values tried

def execute_model_evaluation (model, x_train, y_train, x_valid, accuracy_list, speed_list):
    '''
    input model: sklearn kNN model
    input x_train: pd.DataFrame of shape (N, D)
    input y_train: ndarray of shape (N,)
    input x_valid: pd.DataFrame of shape (N, D)
    input accuracy_list: list of length (V)
    input speed_list: list of legnth (V)
    '''

    # Start the time keeping
    starting_time = time.process_time()                               
    
    # Fit the model with the training dataset
    model.fit(x_train, y_train)                                       
        
    # Predict the new values with the model
    y_pred = model.predict(x_valid)                                   

    # End the time keeping
    finishing_time = time.process_time()                              
    
    # Compute the time
    iteration_speed = round(finishing_time - starting_time, 3)        
    
    # Append the time to the speed list
    speed_list.append(iteration_speed)                                
    
    # Compute the accuracy
    iteration_accuracy = round(accuracy(y_pred, y_valid) * 100, 2)    
    
    # Append the accuracy to the accuracy list
    accuracy_list.append(iteration_accuracy)                          
# Create a line plot of accuracy and speed
# V is the number of values tried for the model

def accuracy_speed_plot(x_axis, accuracy_list, speed_list):
    '''
    input x_axis: ndarray of shape (V,)
    input accuracy_list: list of length (V)
    input speed_list: list of length (V)
    '''
    fig, (ax1, ax2) = plt.subplots(2,                           # Create two subplots
                                   sharex = True,               # Remove the common inside x-axis
                                   figsize=(12,8))              # Adjust the figure size

    fig.suptitle('Accuracy in % (Top) and Speed in s (Down)', fontsize=24, fontfamily = "serif")   # Add the plot title

    ax1.plot(x_axis, accuracy_list, linewidth = 2)   # Plot the accuracy list

    ax2.plot(x_axis, speed_list, linewidth = 2)      # Plot the speed list
    
    ax1.tick_params(axis='y', labelsize=14)          # Adjust the y label font size
    ax2.tick_params(axis='y', labelsize=14)          # Adjust the y label font size
    ax2.tick_params(axis='x', labelsize=16)          # Adjust the x label font size
# Create a bar plot of accuracy and speed
# V is the number of values tried for the model

def accuracy_speed_barplot(x_axis, accuracy_list, speed_list):
    '''
    input x_axis: ndarray of shape (V,)
    input accuracy_list: list of length (V)
    input speed_list: list of length (V)
    '''
    fig, (ax1, ax2) = plt.subplots(2,                          # Create two subplots
                                   sharex = True,              # Remove the common inside x-axis
                                   figsize=(12,8))             # Adjust the figure size

    fig.suptitle('Accuracy in % (Top) and Speed in s (Down)', fontsize=24, fontfamily = "serif")  # Add the plot title

    ax1.bar(x_axis, accuracy_list)                             # Plot the accuracy list

    ax2.bar(x_axis, speed_list)                                # Plot the speed list

    ax1.tick_params(axis='y', labelsize=14)                    # Adjust the y label font size
    ax2.tick_params(axis='y', labelsize=14)                    # Adjust the y label font size
    ax2.tick_params(axis='x', labelsize=16)                    # Adjust the x label font size
# Create a cool table with the accuracy and the speed for each try
# V is the number of values tried for the model

def cool_table (values, values_name, accuracy_list, speed_list):
    '''
    input values: ndarray of shape (V,)
    input values_name: string
    input accuracy_list: list of length (V)
    input speed_list: list of length (V)
    output tbl: pd.DataFrame of shape(V, 3)
    '''
    
    # Create a dataframe with the value tested, the accuracy and the speed
    tbl = pd.DataFrame({'Accuracy': accuracy_list,
                         'Time': speed_list},
                      index= values)
    
    tbl.index.name = values_name                    # Rename the index
    
    return tbl
"""
### Tuning the Number of Features
Selecting the most important features (alias the pixels) is the first step in our tuning process

In general, more features means more information and, as a consequence, more accuracy (at least in the training set...)

But, to use all features involves to major side effects:
- **risk of overfitting the model**: as in all situations with a very high number of parameters
- **a general decrease in speed**: expecially in a model as kNN the number of features is of the utmost importance, given that the time required increase linearly with the dataset used 
"""
# Inizialize the two kpi lists
accuracy_features, speed_features = [], []         

#Select the desired number of features we want to test
features_numbers = np.array([1, 2, 4, 8, 16, 32, 64, 128, 256, 512, x_train_scaled.shape[1]])

for features_number in features_numbers:
    
    # Select the number of features
    parameters_list = entropy.head(features_number).Index                 
    
    # Create a new training df with only that features
    x_train_param = pd.DataFrame(x_train_scaled)[parameters_list]         
    
    # Create a new validation df with only that features
    x_valid_param = pd.DataFrame(x_valid_scaled)[parameters_list]         
    
    execute_model_evaluation(model, 
                             x_train_param, y_train, 
                             x_valid_param, 
                             accuracy_features, speed_features)
    

features_table = cool_table(features_numbers, '# of Features', 
                            accuracy_features, speed_features)
display('Time to run the cell: ' + str(round(sum(speed_features), 2)) + ' s')
display(features_table)

accuracy_speed_plot (features_numbers, 
                     accuracy_features, speed_features)
"""
The first thing we can notice is that **the accuracy increase (although not linearly) with every feature**, so we can say that - in general - all of the pixel are important. But, as we said before, we cannot use the full dataset.

We select for the final model the 512 features option, because we want a model with at least 80% accuracy, but it can't be too slow

Furthermore, *we can see that the increase in accuracy is very small while the increase in the running time is linearly dependent on the size of the dataset*

For the sake of speed, during the rest of the tuning, we will use the 128 option
"""
# Select the 128 features with the highest entropy
parameters_list = entropy.head(128).Index                  

# Filter the features selected from the training set
x_train = pd.DataFrame(x_train_scaled)[parameters_list]    

# Filter the features selected from the validation set
x_valid = pd.DataFrame(x_valid_scaled)[parameters_list]    
"""
### Tuning the number of neighbors
The number of neighbors computed is the "k" in the kNN model. *Having more neighbors means that the model will take in account more observation similar to the input.* So, if we set k = 5 the 5 most similar observations will have a right to "vote" and influencing the class assignment to the input, if we set k = 15 the 15 most similar observations have the right to "vote" and so on.

Exploring this hyperparameter is very important in order to **understand the optimal level of bias-variance trade-off.**

Usually, if we set k too small we will have underfitting, while if we set k too large we will have overfitting.

We set the search space between 1 and 16 neighbors, and if that is not enough, we will expand the search
"""
accuracy_neighbors, speed_neighbors = [], []

neighbors_fitted = [1, 2, 3, 4, 5, 6, 7, 10, 13, 16]

for neighbors_trial in neighbors_fitted:
    
    model = KNeighborsClassifier(n_neighbors = neighbors_trial,
                                 weights = 'distance', 
                                 algorithm = 'brute', 
                                 p = 2)
    
    execute_model_evaluation(model, 
                             x_train, y_train, 
                             x_valid, 
                             accuracy_neighbors, speed_neighbors)

    
neighbors_table = cool_table(neighbors_fitted, '# of Neighbors', 
                             accuracy_neighbors, speed_neighbors)

display('Time to run the cell: ' + str(round(sum(speed_neighbors), 2)) + ' s')
display(neighbors_table)

accuracy_speed_plot (neighbors_fitted, 
                     accuracy_neighbors, speed_neighbors)
"""
We note that **the accuracy goes up until 3 neighbors then starts to drop.** This means that if we go over 4 neighbor we start overfitting the model.

Also, note that the speed is affected only up to the fourth neighbor, after that is constant

Considered that, we will use 3 neighbors in the next models
"""
"""
### Tuning the type of weight
kNN is a non-parametric model, so to see the word "weight" must be somewhat confusing

There are two types of weights in kNN:
- *'uniform'*: this means, substantially, that there are no weights and all the distances in the features are considered with the same importance
- *'distance'*: this means that the features will be assigned a weight based on their distance from the input. So, the more distant a feature values is the smaller the weight assigned will be the mless important the feature will be

With the 'distance' option, a feature that have values usually far from the input will have less importance 

**Feature scaling is extremely important for this hyperparameter!**
"""
accuracy_weights, speed_weights = [], []

weights_fitted = ['uniform', 'distance']

for weight_trial in weights_fitted:
    
    model = KNeighborsClassifier(n_neighbors = 3, 
                                 weights = weight_trial,
                                 algorithm = 'brute', 
                                 p = 2)
    
    execute_model_evaluation(model, 
                             x_train, y_train, 
                             x_valid, 
                             accuracy_weights, speed_weights)
    

weight_table = cool_table(weights_fitted, 'Types of Weight', 
                          accuracy_weights, speed_weights)

display('Time to run the cell: ' + str(round(sum(speed_weights), 2)) + ' s')
display(weight_table)

accuracy_speed_barplot(weights_fitted, 
                       accuracy_weights, speed_weights)
"""
In our case, **this hyperparameter doesn't seem to have a strong impact**

The accuracy is more or less the same, while *the speed is slightly increased with the 'distance' option.*

Considered that, we will use the 'distance' option in the next models
"""
"""
### Tuning the type of algorithm
The type of algorithm is, essentially, **the "engine" that the model use** to process the input.

There are four option for this hyperparameter:
- *'auto'*: the function will automatically pick the best of the other three options based on the input
- *'ball_tree'*: will use the ball_tree algorithm. It's an algorithm that uses a binary tree to partition the data. Usually, performs well when the number of dimensions is high but, initially, require a lot of time to create the binary tree. It uses the 'triangle inequality' to create bounds and speed up the process. Complexity: O[DNlog(N)]
- *'kd_tree'*: will use the kd_tree algorithm. Like the ball_tree, uses binary trees to recursively partition the data into smaller groups. The construction of a kd_tree is very fast because it's done by using only along the data axes. But, kd_tree becomes very slow for higher dimensionality spaces because it suffer from the 'curse of dimensionality'. Complexity: O[DNlog(N)], for larger samples O[DN]
- *'brute'*: will use a brute force approach. Complexity: O[DN]

The main difference between the kd_tree and the ball_tree is that *kd_tree partition data along the axes, while the ball_tree partition data in a series of hyper-spheres* (in 2d they would be circles, in 3d they would be sphere, and so on)
"""
accuracy_algorithm, speed_algorithm = [], []

algorithms_fitted = ['auto', 'ball_tree', 'kd_tree', 'brute']

for algorithm_trial in algorithms_fitted:
    
    model = KNeighborsClassifier(n_neighbors = 3, 
                                 weights = 'distance', 
                                 algorithm = algorithm_trial,
                                 p = 2,
                                 leaf_size = 2)
    
    execute_model_evaluation(model, 
                             x_train, y_train, 
                             x_valid, 
                             accuracy_algorithm, speed_algorithm)
    
algorithm_table = cool_table(algorithms_fitted, 'Types of Algorithms', 
                             accuracy_algorithm, speed_algorithm)

display('Time to run the cell: ' + str(round(sum(speed_algorithm), 2)) + ' s')
display(algorithm_table)
    
accuracy_speed_barplot(algorithms_fitted, 
                       accuracy_algorithm, speed_algorithm)
"""
We can see that the 'auto' option probably selected the 'kd_tree' option for this dataset, thus the similar results.

The ball_tree algorithm is almost twice as fast as the kd_tree, while the brute force algorithm is almost 6 times faster than the kd_tree (and 3x faster than the ball_tree). **The brute force algorithm is faster due to the fact that doesn't need to build a binary tree like the other two.**

Given the obvious disparity in performances, we will use the brute force in the final model
"""
"""
### Tuning the leaf size

The leaf size hyperparameter influences the use of the binary trees with theBallTree algorithm or the KDTree algorithm options active

With the brute force method applied, this shouldn't affect the performances whatsoever
"""
accuracy_leaf_size, speed_leaf_size = [], []

leaf_size_fitted = [1, 2, 4, 8, 16, 32, 64]

for leaf_size_trial in leaf_size_fitted:
    
    model = KNeighborsClassifier(n_neighbors = 3, 
                                 weights = 'distance',
                                 algorithm = 'brute',
                                 leaf_size = leaf_size_trial,
                                 p = 2)
    
    execute_model_evaluation(model, 
                             x_train, y_train, 
                             x_valid, 
                             accuracy_leaf_size, speed_leaf_size)
    
leaf_table = cool_table(leaf_size_fitted, 'Leaf Size', 
                        accuracy_leaf_size, speed_leaf_size)

display('Time to run the cell: ' + str(round(sum(speed_leaf_size), 2)) + ' s')
display(leaf_table)
    
accuracy_speed_plot(leaf_size_fitted, 
                    accuracy_leaf_size, speed_leaf_size)
"""
We can see that **the accuracy is exactly the same for all the trials,** while the speed change less than 3% between the smallest and the largest trial.

This proves the indifference that the brute force method has regarding the leaf size (simply because doesn't use trees at all)

In the final model we will drop entirely this hyperparameter because it's not important to us and we want to improve readibility
"""
"""
### Tuning the p parameter
The p-parameter indicates the way in which the kNN should compute the distances between observations and input

We will test the two main methods for computing inputs:
- *p = 1*: also called l1-norm or manatthan distance. Compute the distance, in absolute values, between the input value and the observations.
- *p = 2*: also called l2-norm or euclidean distance. Compute the distance by taking the root of the sum of all the squared distances between the input value and the observations
"""
accuracy_p, speed_p = [], []

p_fitted = [1, 2]

for p_trial in p_fitted:
    
    model = KNeighborsClassifier(n_neighbors = 3, 
                                 weights = 'distance', 
                                 algorithm = 'brute', 
                                 p = p_trial)
    
    execute_model_evaluation(model, 
                             x_train, y_train, 
                             x_valid, 
                             accuracy_p, speed_p)
    
p_table = cool_table(p_fitted, 'Types of Norm', 
                     accuracy_p, speed_p)

display('Time to run the cell: ' + str(round(sum(speed_p), 2)) + ' s')
display(p_table)
    
accuracy_speed_barplot(p_fitted, 
                       accuracy_p, speed_p)
"""
We can see that **the model, using the l2-norm, is almost 6x faster than using the l1-norm**

This is probably due to the fact that computing absolute values is more computationally expensive compared to squaring and rooting numbers if the problem can't be solved using an LP reformulation that lead to linear equations 

While the accuracy is sligthly higher with the l1-norm, we will use the l2-norm in the final model
"""
"""
# Evaluation
"""
### We report the final model with all the best features

# We select the 512 parameters with the highest entropy
parameters_list = entropy.head(512).Index                            

x_train_final = pd.DataFrame(x_train_scaled)[parameters_list]

x_valid_final = pd.DataFrame(x_valid_scaled)[parameters_list]

model = KNeighborsClassifier(n_neighbors = 3, 
                             weights = 'distance',
                             algorithm = 'brute', 
                             p = 2)

starting_time = time.process_time()                    # Start the time keeping

model.fit(x_train_final, y_train)                      # Fit the model with the training dataset

y_pred = model.predict(x_valid_final)                  # Predict the new values with the model

finishing_time = time.process_time()                   # End the time keeping

iteration_speed = finishing_time - starting_time       # Compute the time

iteration_accuracy = accuracy(y_pred, y_valid) * 100   # Compute the accuracy

print ('The model has an accuracy of ' + 
       str(round(iteration_accuracy, 2)) + 
       '% and a computing speed of ' + 
       str(round(iteration_speed, 2)) + 
       ' seconds')

print('The model is capable of predicting one instance in ' + 
      str(round(iteration_speed/y_pred.shape[0], 4)) + 
      ' seconds')
"""
# Author's Notes

I've tried to optimize not only the model per se, but also the notebook in general:
- Each new piece of code is commented the first time that it's used
- The lines have an addition space between them
    - But, if the lines are somehow connected, then you'll find them together
- Each function's argument is broke into single lines
    - But, if the arguments are few or simple I've left them on a single line
- Through the notebook, I've used similar variable names, only changing the minimum possible to ease the connection between each section of the hyperparameters tuning
- I've used the easiest plots to read (lineplots or barplots) , this is because I've favoured readibility over complexity. I feel like the informations that I wanted to share were delivered pretty well even with simple plots and I didn't want to add complexity where it wasn't necessary
- I've added little sections of theoretical stuff to help you understand the notebook even with minimal background
- I've tried to explain, for each hyperparameter, how it impacts the results and why

That's all. Let me know if you appreciated it!
"""
"""
# Sending the submission for the challenge
"""
##################################################
# Save your test prediction in y_test_pred
##################################################

x_test_final = pd.DataFrame(x_test_scaled)[parameters_list]

y_test_pred = model.predict(x_test_final)

# Create submission
submission = pd.read_csv(os.path.join(DATA_BASE_FOLDER, 'sample_submission.csv'))
if y_test_pred is not None:
    submission['class'] = y_test_pred
submission.to_csv('my_submission.csv', index=False)