# $k$ Nearest Neighbors

## Illustration of Nearest Neighbors

Arguably one of the simplest classification algorithm is $k$ nearest neighbors (KNN). Below figure portrays the algorithm's simplicity. We see a training set of five red and five blue dots, representing some label 1 and 0, respectively. The two axes represent two features, e.g. income and credit card balance. If we now add a new test data point $x_0$ (green dot), KNN will label this test data according to its $k$ closest neighbors. In below figure we set $k=3$. The three closest neighbors are: one blue dot and two red dots, resulting in estimated probabilities of 2/3 for the red class and 1/3 for the blue class. Hence KNN will predict that the new data point will belong to the red class. More so, based on the training set the algorithm is able to draw a decision boundary. (Note: In a classification settings with $j$ classes a *decision boundary* is a hyperplane that partitions the underlying vector space into $j$ sets, one for each class.). This is shown with the jagged line that separates background colors cyan (blue label) and light blue (red label). Given any possible pair of feature values, KNN labels the response along the drawn decision boundary. With $k=1$ the boundary line is very jagged. Increasing the number of $k$ will smoothen the decision boundary. This tells us that small values of $k$ will produce large variance but low bias, meaning that each new added training point might change the decision boundary line significantly but the decision boundary separates the training set (almost) correctly. As $k$ increases, variance decreases but bias increases. This is a manifestation of the Bias-Variance Trade-Off as discussed in the script ([Fortmann-Roe (2012)](http://scott.fortmann-roe.com/docs/BiasVariance.html)) and highlights the importance of selecting an adequate value of $k$ - a topic we will pick up in a future chapter.



## Mathematical Description of KNN

Having introduced KNN illustratively, let us now define this in mathematical terms. Let our data set be $\{(x_1, y_1), (x_2, y_2), \ldots (x_n, y_n)\}$ with $x_i \in \mathbb{R}^p$ and $y_i \in \{0, 1\}\; \forall i \in \{1, 2, \ldots, n\}$. Based on the $k$ neighbors, KNN estimates the conditional probability for class $j$ as the fraction of points in $\mathcal{N}(k, x_0)$ (the set of the $k$ closest neighbors of $x_0$) whose response values equals $j$ (Russell and Norvig (2009)):

$$\begin{equation}
\Pr(Y = j | X = x_0) = \frac{1}{k} \sum_{i \in \mathcal{N}(k, x_0)} \mathbb{I}(y_i = j).
\end{equation}$$

Once the probability for each class $j$ is calculated, the  KNN classifier predicts a class label $\hat{y}_0$ for the new data point $x_0$ by maximizing the conditional probability (Batista and Silva (2009)).

$$\begin{equation}
\hat{y}_0 = \arg \max_{j} \frac{1}{k} \sum_{i \in \mathcal{N}(k,x_0)} \mathbb{I}(y_i = j)
\end{equation}$$

Selecting a new data point $x_0$'s nearest neighbors requires some notion of **distance measure**. Most researchers chose Minkowski's distance, which is often referred to as $L^m$ norm (Guggenbuehler (2015)). The distance between points $x_a$ and $x_b$ in $\mathbb{R}^p$ is then defined as follows (Russell and Norvig (2009)):

$$\begin{equation}
L^m (x_a, x_b) = \left(\sum_{i=1}^p |x_{a, i} - x_{b, i}|^m \right)^{1/m}
\end{equation}$$

Using $m=2$, above equation simplifies to the well known Euclidean distance and $m=1$ yields the Manhattten distance. Python's `sklearn` package, short for scikit-learn, offers [several other options](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.DistanceMetric.html) that we will not discuss. 

Beyond the pure distance measure, it is also possible to weight training data points relative to their distance from a certain point. In above figure distance is weighted uniformly. Alternatively one could weight points by the inverse of their distance (closer neighbors of a query point will have a greater influence than neighbors which are further away) or any other user-defined weighting function. For [further details check `sklearn`'s documentation](http://scikit-learn.org/stable/modules/neighbors.html\#classification} for details).

## Application: Predicting Share Price Movement

### Loading Data

The application of KNN is shown using simple stock market data. The idea is to predict a stock's movement based on simple features such as:
* `Lag1, Lag2`: log returns of the two previous trading days 
* `SMI`: SMI log return of the previous day

The response is a binary variable: if a stock closed above the previous day closing price it equals 1, and 0 if it fell. We start by loading the necessary packages and stock data from a csv - a procedure we are well acquainted with by now. Thus comments are held short.


```python
%matplotlib inline
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
plt.style.use('seaborn-whitegrid')
plt.rcParams['font.size'] = 14
```


```python
# Import daily shares prices and select window
shsPr = pd.read_csv('Data/SMIDataDaily.csv', sep=',',
                 parse_dates=['Date'], dayfirst=True,
                 index_col=['Date'])
shsPr = shsPr['2017-06-30':'2012-06-01']
shsPr.head()
```




<div>
<style>
    .dataframe thead tr:only-child th {
        text-align: right;
    }

    .dataframe thead th {
        text-align: left;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>ABBN</th>
      <th>ADEN</th>
      <th>BAER</th>
      <th>CFR</th>
      <th>CSGN</th>
      <th>GEBN</th>
      <th>GIVN</th>
      <th>LHN</th>
      <th>LONN</th>
      <th>NESN</th>
      <th>...</th>
      <th>ROG</th>
      <th>SCMN</th>
      <th>SGSN</th>
      <th>SLHN</th>
      <th>SREN</th>
      <th>UBSG</th>
      <th>UHR</th>
      <th>ZURN</th>
      <th>SIK</th>
      <th>SMI</th>
    </tr>
    <tr>
      <th>Date</th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
      <th></th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>2017-06-30</th>
      <td>23.68</td>
      <td>72.90</td>
      <td>50.45</td>
      <td>79.00</td>
      <td>13.86</td>
      <td>447.2</td>
      <td>1918.0</td>
      <td>54.90</td>
      <td>207.3</td>
      <td>83.45</td>
      <td>...</td>
      <td>244.2</td>
      <td>462.7</td>
      <td>2322.0</td>
      <td>323.6</td>
      <td>87.65</td>
      <td>16.24</td>
      <td>354.1</td>
      <td>279.1</td>
      <td>6160.0</td>
      <td>8906.89</td>
    </tr>
    <tr>
      <th>2017-06-29</th>
      <td>23.63</td>
      <td>72.85</td>
      <td>51.30</td>
      <td>78.60</td>
      <td>14.10</td>
      <td>446.0</td>
      <td>1913.0</td>
      <td>55.00</td>
      <td>204.7</td>
      <td>83.65</td>
      <td>...</td>
      <td>246.9</td>
      <td>463.9</td>
      <td>2310.0</td>
      <td>323.3</td>
      <td>87.80</td>
      <td>16.36</td>
      <td>353.4</td>
      <td>276.3</td>
      <td>6145.0</td>
      <td>8944.04</td>
    </tr>
    <tr>
      <th>2017-06-28</th>
      <td>24.07</td>
      <td>73.55</td>
      <td>51.65</td>
      <td>80.00</td>
      <td>13.82</td>
      <td>452.5</td>
      <td>1927.0</td>
      <td>56.35</td>
      <td>207.5</td>
      <td>85.40</td>
      <td>...</td>
      <td>251.2</td>
      <td>464.9</td>
      <td>2342.0</td>
      <td>325.3</td>
      <td>88.55</td>
      <td>16.29</td>
      <td>360.0</td>
      <td>278.0</td>
      <td>6195.0</td>
      <td>9076.73</td>
    </tr>
    <tr>
      <th>2017-06-27</th>
      <td>24.40</td>
      <td>73.70</td>
      <td>51.65</td>
      <td>80.20</td>
      <td>13.74</td>
      <td>453.8</td>
      <td>1931.0</td>
      <td>56.40</td>
      <td>207.6</td>
      <td>84.30</td>
      <td>...</td>
      <td>252.0</td>
      <td>465.0</td>
      <td>2355.0</td>
      <td>322.7</td>
      <td>88.80</td>
      <td>16.00</td>
      <td>362.0</td>
      <td>281.7</td>
      <td>6280.0</td>
      <td>9072.92</td>
    </tr>
    <tr>
      <th>2017-06-26</th>
      <td>24.63</td>
      <td>73.85</td>
      <td>51.35</td>
      <td>80.45</td>
      <td>13.49</td>
      <td>457.0</td>
      <td>1947.0</td>
      <td>56.25</td>
      <td>208.2</td>
      <td>85.65</td>
      <td>...</td>
      <td>251.7</td>
      <td>469.3</td>
      <td>2375.0</td>
      <td>323.9</td>
      <td>89.40</td>
      <td>15.71</td>
      <td>367.5</td>
      <td>284.4</td>
      <td>6310.0</td>
      <td>9121.22</td>
    </tr>
  </tbody>
</table>
<p>5 rows × 21 columns</p>
</div>



Having the data in a proper dataframe, we are now in a position to create the features and response values.


```python
# Calculate log-returns and label responses: 
# 'direction' equals 1 if stock closed above 
# previous day and 0 if it fell.
today = np.log(shsPr / shsPr.shift(-1))
direction = np.where(today >= 0, 1, 0)

# Convert 'direction' to dataframe
direction = pd.DataFrame(direction, index=today.index, columns=today.columns)

# Lag1, 2: t-1 and t-2 returns; excl. smi (in last column)
Lag1 = np.log(shsPr.iloc[:, :-1].shift(-1) / shsPr.iloc[:, :-1].shift(-2))
Lag2 = np.log(shsPr.iloc[:, :-1].shift(-2) / shsPr.iloc[:, :-1].shift(-3))

# Previous day return for SMI index
smi  = np.log(shsPr.iloc[:, -1].shift(-1) / shsPr.iloc[:, -1].shift(-2))
```

### KNN Algorithm Applied

Now comes the difficult part. What we want to achieve is to run the KNN algorithm for every stock and for different hyperparameter $k$ and see how it performs. For this we do the following steps:

1. Create a feature matrix `X` containing `Lag1`, `Lag2` and `SMI` data for share i
2. Create a response vector `y` with binary direction values
3. Split data to training (before 2016-06-30) and test set (after 2016-06-30)
4. Run KNN for different values of $k$ (loop)
5. Write test score for given $k$ to matrix `scr`
6. Once we've run through all $k$'s we proceed with step 1. with share i+1

This means we need two loops. The first corresponds to the share (e.g. ABB, Adecco, etc.), the second runs the KNN algorithm for different values of $k$. 

The reason for this approach is that we are interested in finding any pattern/structure that would provide a successful trading strategy. There is obviously no free lunch. Predicting share price direction is by no means an easy task and we must be well aware that we are in for a difficult job here. If it were simple, neither one of us would be sitting here but run his own fund. But nonetheless, let us see how KNN performs and how homogeneous (or heterogeneous) the results are.

Our first step is as usual to prepare the ground by loading the necessary package and defining some auxiliary variables. The KNN function we will be using is available through the `sklearn` (short for Scikit-learn) package. We only load the `neighbor` sublibrary which contains the needed KNN function called `KNeigborsClassifier()`. KNN is applied with the default distance metric: Euclidean distance (Minkowski's distance with $m=2$). If we would prefer another distance metric we would have to specify it ([see documentation](http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html)).


```python
# Import relevant functions
from sklearn import neighbors

# k = {1, 3, ..., 200}
k = np.arange(1, 200, 2)

# Array to store results in. Dimension is [k x m] 
# with m=20 for the 20 companies (excl. SMI)
scr = np.empty(shape=(len(k), len(shsPr.columns)-1))
```


```python
for i in range(len(shsPr.columns)-1):
    
    # 1) Create matrix with feature values of stock i
    X = pd.concat([Lag1.iloc[:, i], Lag2.iloc[:, i], smi], axis=1)
    X = X[:-3]  # Drop last three rows with NaN (due to lag)
    
    # 2) Remove last three rows of response dataframe
    #    to have equal no. of rows for features and response
    y = direction.iloc[:, i]
    y = y[:-3]
    
    # 3) Split data into training set...
    X_train = X['2016-06-30':]
    y_train = y['2016-06-30':]
    # ...and test set.
    X_test = X[:'2016-07-01']
    y_test = y[:'2016-07-01']
    
    # Convert responses to 1xN array
    y_train = y_train.values.ravel()
    y_test  = y_test.values.ravel()
    
    for j in range(len(k)):
        
        # 4) Run KNN
        # Instantiate KNN class
        knn = neighbors.KNeighborsClassifier(n_neighbors=k[j])
        # Fit KNN classifier using training set
        knn = knn.fit(X_train, y_train)
        
        # 5) Extract test score for k[j]
        scr[j, i] = knn.score(X_test, y_test)
```


```python
# Convert data to pandas dataframe
tickers = shsPr.columns
scr = pd.DataFrame(scr, index=k, columns=tickers[:-1])
```


```python
scr.head()
```




<div>
<style>
    .dataframe thead tr:only-child th {
        text-align: right;
    }

    .dataframe thead th {
        text-align: left;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>ABBN</th>
      <th>ADEN</th>
      <th>BAER</th>
      <th>CFR</th>
      <th>CSGN</th>
      <th>GEBN</th>
      <th>GIVN</th>
      <th>LHN</th>
      <th>LONN</th>
      <th>NESN</th>
      <th>NOVN</th>
      <th>ROG</th>
      <th>SCMN</th>
      <th>SGSN</th>
      <th>SLHN</th>
      <th>SREN</th>
      <th>UBSG</th>
      <th>UHR</th>
      <th>ZURN</th>
      <th>SIK</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>1</th>
      <td>0.462451</td>
      <td>0.533597</td>
      <td>0.521739</td>
      <td>0.513834</td>
      <td>0.509881</td>
      <td>0.533597</td>
      <td>0.498024</td>
      <td>0.498024</td>
      <td>0.505929</td>
      <td>0.411067</td>
      <td>0.549407</td>
      <td>0.553360</td>
      <td>0.513834</td>
      <td>0.521739</td>
      <td>0.509881</td>
      <td>0.470356</td>
      <td>0.490119</td>
      <td>0.549407</td>
      <td>0.498024</td>
      <td>0.529644</td>
    </tr>
    <tr>
      <th>3</th>
      <td>0.478261</td>
      <td>0.470356</td>
      <td>0.529644</td>
      <td>0.486166</td>
      <td>0.577075</td>
      <td>0.533597</td>
      <td>0.525692</td>
      <td>0.482213</td>
      <td>0.525692</td>
      <td>0.486166</td>
      <td>0.517787</td>
      <td>0.573123</td>
      <td>0.486166</td>
      <td>0.517787</td>
      <td>0.541502</td>
      <td>0.450593</td>
      <td>0.490119</td>
      <td>0.557312</td>
      <td>0.517787</td>
      <td>0.513834</td>
    </tr>
    <tr>
      <th>5</th>
      <td>0.498024</td>
      <td>0.494071</td>
      <td>0.537549</td>
      <td>0.494071</td>
      <td>0.525692</td>
      <td>0.573123</td>
      <td>0.537549</td>
      <td>0.474308</td>
      <td>0.501976</td>
      <td>0.486166</td>
      <td>0.525692</td>
      <td>0.513834</td>
      <td>0.466403</td>
      <td>0.501976</td>
      <td>0.521739</td>
      <td>0.482213</td>
      <td>0.494071</td>
      <td>0.553360</td>
      <td>0.533597</td>
      <td>0.509881</td>
    </tr>
    <tr>
      <th>7</th>
      <td>0.517787</td>
      <td>0.486166</td>
      <td>0.505929</td>
      <td>0.498024</td>
      <td>0.505929</td>
      <td>0.553360</td>
      <td>0.525692</td>
      <td>0.517787</td>
      <td>0.474308</td>
      <td>0.509881</td>
      <td>0.513834</td>
      <td>0.482213</td>
      <td>0.470356</td>
      <td>0.509881</td>
      <td>0.525692</td>
      <td>0.466403</td>
      <td>0.490119</td>
      <td>0.561265</td>
      <td>0.533597</td>
      <td>0.509881</td>
    </tr>
    <tr>
      <th>9</th>
      <td>0.553360</td>
      <td>0.478261</td>
      <td>0.505929</td>
      <td>0.470356</td>
      <td>0.486166</td>
      <td>0.533597</td>
      <td>0.505929</td>
      <td>0.513834</td>
      <td>0.458498</td>
      <td>0.462451</td>
      <td>0.545455</td>
      <td>0.486166</td>
      <td>0.462451</td>
      <td>0.501976</td>
      <td>0.501976</td>
      <td>0.470356</td>
      <td>0.490119</td>
      <td>0.517787</td>
      <td>0.482213</td>
      <td>0.470356</td>
    </tr>
  </tbody>
</table>
</div>



### Results & Analysis

Now let's see the results in an overview. 


```python
scr.describe()
```




<div>
<style>
    .dataframe thead tr:only-child th {
        text-align: right;
    }

    .dataframe thead th {
        text-align: left;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>ABBN</th>
      <th>ADEN</th>
      <th>BAER</th>
      <th>CFR</th>
      <th>CSGN</th>
      <th>GEBN</th>
      <th>GIVN</th>
      <th>LHN</th>
      <th>LONN</th>
      <th>NESN</th>
      <th>NOVN</th>
      <th>ROG</th>
      <th>SCMN</th>
      <th>SGSN</th>
      <th>SLHN</th>
      <th>SREN</th>
      <th>UBSG</th>
      <th>UHR</th>
      <th>ZURN</th>
      <th>SIK</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>count</th>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
      <td>100.000000</td>
    </tr>
    <tr>
      <th>mean</th>
      <td>0.553202</td>
      <td>0.506798</td>
      <td>0.515968</td>
      <td>0.508577</td>
      <td>0.517431</td>
      <td>0.499763</td>
      <td>0.533320</td>
      <td>0.492016</td>
      <td>0.537510</td>
      <td>0.519960</td>
      <td>0.546877</td>
      <td>0.513043</td>
      <td>0.479051</td>
      <td>0.516996</td>
      <td>0.490514</td>
      <td>0.520791</td>
      <td>0.489289</td>
      <td>0.507352</td>
      <td>0.553557</td>
      <td>0.530040</td>
    </tr>
    <tr>
      <th>std</th>
      <td>0.031183</td>
      <td>0.010579</td>
      <td>0.023187</td>
      <td>0.024694</td>
      <td>0.016666</td>
      <td>0.020266</td>
      <td>0.013498</td>
      <td>0.019546</td>
      <td>0.027272</td>
      <td>0.020842</td>
      <td>0.018939</td>
      <td>0.016882</td>
      <td>0.019902</td>
      <td>0.020634</td>
      <td>0.020150</td>
      <td>0.017837</td>
      <td>0.014962</td>
      <td>0.027736</td>
      <td>0.020282</td>
      <td>0.028188</td>
    </tr>
    <tr>
      <th>min</th>
      <td>0.462451</td>
      <td>0.470356</td>
      <td>0.462451</td>
      <td>0.454545</td>
      <td>0.446640</td>
      <td>0.458498</td>
      <td>0.498024</td>
      <td>0.450593</td>
      <td>0.458498</td>
      <td>0.411067</td>
      <td>0.505929</td>
      <td>0.474308</td>
      <td>0.446640</td>
      <td>0.474308</td>
      <td>0.450593</td>
      <td>0.450593</td>
      <td>0.438735</td>
      <td>0.454545</td>
      <td>0.482213</td>
      <td>0.466403</td>
    </tr>
    <tr>
      <th>25%</th>
      <td>0.529644</td>
      <td>0.500988</td>
      <td>0.501976</td>
      <td>0.493083</td>
      <td>0.509881</td>
      <td>0.486166</td>
      <td>0.525692</td>
      <td>0.477273</td>
      <td>0.529644</td>
      <td>0.509881</td>
      <td>0.533597</td>
      <td>0.501976</td>
      <td>0.462451</td>
      <td>0.501976</td>
      <td>0.474308</td>
      <td>0.516798</td>
      <td>0.482213</td>
      <td>0.486166</td>
      <td>0.545455</td>
      <td>0.512846</td>
    </tr>
    <tr>
      <th>50%</th>
      <td>0.557312</td>
      <td>0.505929</td>
      <td>0.517787</td>
      <td>0.509881</td>
      <td>0.517787</td>
      <td>0.498024</td>
      <td>0.533597</td>
      <td>0.490119</td>
      <td>0.547431</td>
      <td>0.525692</td>
      <td>0.545455</td>
      <td>0.513834</td>
      <td>0.476285</td>
      <td>0.521739</td>
      <td>0.494071</td>
      <td>0.525692</td>
      <td>0.490119</td>
      <td>0.501976</td>
      <td>0.557312</td>
      <td>0.525692</td>
    </tr>
    <tr>
      <th>75%</th>
      <td>0.581028</td>
      <td>0.513834</td>
      <td>0.533597</td>
      <td>0.525692</td>
      <td>0.525692</td>
      <td>0.513834</td>
      <td>0.537549</td>
      <td>0.505929</td>
      <td>0.553360</td>
      <td>0.533597</td>
      <td>0.561265</td>
      <td>0.525692</td>
      <td>0.490119</td>
      <td>0.533597</td>
      <td>0.501976</td>
      <td>0.533597</td>
      <td>0.498024</td>
      <td>0.525692</td>
      <td>0.569170</td>
      <td>0.546443</td>
    </tr>
    <tr>
      <th>max</th>
      <td>0.600791</td>
      <td>0.533597</td>
      <td>0.569170</td>
      <td>0.557312</td>
      <td>0.577075</td>
      <td>0.573123</td>
      <td>0.573123</td>
      <td>0.541502</td>
      <td>0.577075</td>
      <td>0.549407</td>
      <td>0.592885</td>
      <td>0.573123</td>
      <td>0.541502</td>
      <td>0.561265</td>
      <td>0.541502</td>
      <td>0.545455</td>
      <td>0.521739</td>
      <td>0.573123</td>
      <td>0.592885</td>
      <td>0.581028</td>
    </tr>
  </tbody>
</table>
</div>



Following finance theory, returns should be distributed symmetrically. Thus the simplest guess would be to expect a share price to increase on 50% of the days and to decrease on the remaining 50%. Similar to guessing a coin flip, if we would guess an 'up' movement for every day, we obviously would - in the long run - be correct 50% of the times. This would make for a score of 50%. 

Looking in that light at the above summary, we see some very interesting results. For 13 out of 20 stocks KNN produces test scores of > 50% for even the 0.25th percentile. Let's plot the ones with the highest test-scores (ABBN, NOVN, SIK and ZURN) to see at what value of $k$ the best test-score is achieved.


```python
nms = ['ABBN', 'NOVN', 'SIK', 'ZURN']

plt.figure(figsize=(12, 8))
for col in nms:
    scr[col].plot(legend=True)
plt.axhline(0.50, c='k', ls='--');
```

For ABB and Novartis the max. score is around $k=100$ while for Sika and Zurich it is between 177 - 185. Furthermore, it seems interesting that for ABB, Novartis and Zurich the test score was barely below 50%. If this is indeed a pattern we would have found a trading strategy, wouldn't we? 

To further assess our results we look into KNN's prediction of ABB stock movements. For this we rerun our KNN classifier algorithm for ABB as before.


```python
# 1) Create matrix with feature values of stock i
X = pd.concat([Lag1['ABBN'], Lag2['ABBN'], smi], axis=1)
X = X[:-3]  # Drop last three rows with NaN (due to lag)
```


```python
# 2) Remove last three rows of response dataframe
#    to have equal no. of rows for features and response
y = direction['ABBN']
y = y[:-3]
```


```python
# 3) Split data into training set...
X_train = X['2016-06-30':]
y_train = y['2016-06-30':]
# ...and test set.
X_test = X[:'2016-07-01']
y_test = y[:'2016-07-01']

# Covert responses to 1xN array
y_train = y_train.values.ravel()
y_test  = y_test.values.ravel()
```

For ABB the maximum score is reached where $k=119$. You can check this with the `scr['ABBN'].idxmax()` command, which provides the index of the maximum value of the selected column. In our case, the index is equivalent to the value of $k$. Thus we run KNN with $k=119$.


```python
# 4) Run KNN
# Instantiate KNN class for ABB with k=119
knn = neighbors.KNeighborsClassifier(n_neighbors=119)
# Fit KNN classifier using training set
knn = knn.fit(X_train, y_train)

# 5) Extract test score for ABB
scr_ABB = knn.score(X_test, y_test)
scr_ABB
```




    0.60079051383399207



The score of 60.08% is the very same as above. Nothing new so far. (Recall that the score is the total of correctly predicted outcomes.)

However, the alert reader should by now raise some questions regarding our assumption that 50% of the returns should have been positive. In the long run, this might be true. But our training sample contained only 1'018 records and of these 535 were positive. 


```python
# Percentage of 'up' days in training set
y_train.sum() / y_train.size
```




    0.52554027504911593



Therefore, if we would guess 'up' for every day of our test set and **given the distribution of classes in the test set is exactly as in our training set**, then we would predict the correct movement in 52.55% of the cases. So in that light, the predictive power of our KNN algorithm has to be put in perspective to the 52.55%.

In summary, our KNN algorithm has a score of 60.08%. Our best guess (based on the training set) would yield a score of 52.55%. This still displays that overall our KNN algorithm outperforms our best guess. Nonetheless, the margin is smaller than initially thought. 

### Confusion Matrix

There are more tools to assess the accuracy of an algorithm. We postpone the discussion of these tools to a later chapter and at this stage restrict ourselves to the discussion of a tool called "confusion matrix". 

A confusion matrix is a convenient way of displaying how our classifier performs. In binary classification (with e.g. response $y \in \{0, 1\}$) there are four prediction categories possible (Ting (2011)):

* **True positive**: True response value is 1, predicted value is 1 ("hit")
* **True negative**: True response value is 0, predicted value is 0 ("correct rejection")
* **False positive**: True response value is 0, predicted value is 1 ("False alarm", Type 1 error)
* **False negative**: True response value is 1, predicted value is 0 ("Miss", Type 2 error)

These information help us to understand how our (KNN) algorithm performed. There are different two ways of arranging confusion matrix. James et al. (2013) follow the convention that column labels indicate the true class label and rows the predicted response class. Others have it transposed, such that column labels indicate predicted classes and row labels show true values. We will use the latter approach.



To run this in Python, we first predict the response value for each data entry in our test matrix `X_test`. Then we arrange the data in a suitable manner.


```python
# Predict 'up' (=1) or 'down' (=0) for test set
pred = knn.predict(X_test)
```


```python
# Store data in DataFrame
cfm = pd.DataFrame({'True direction': y_test,
                    'Predicted direction': pred})
cfm.replace(to_replace={0:'Down', 1:'Up'}, inplace=True)

# Arrange data to confusion matrix
print(cfm.groupby(['Predicted direction','True direction']) \
      .size().unstack('Predicted direction'))
```

    Predicted direction  Down   Up
    True direction                
    Down                   31   83
    Up                     18  121


As mentioned before, rows represent the true outcome and columns show what class KNN predicted. In 31 cases, the test set's true response was 'down' (in our case represented by 0) and KNN correctly predicted 'down'. 121 times KNN was correct in predicting an 'up' (=1) movement. 18 returns in the test set were positive but KNN predicted a negative return. And in 83 out of 253 cases KNN predicted a 'up' movement whereas in reality the stock price decreased. The KNN score of 60.08% for ABB is the sum of true positive and negative (31 + 121) in relation to the total number of predictions (253 = 31 + 18 + 83 + 121). The error rate is 1 - score or (18 + 83)/253.

Class-specific performance is also helpful to better understand results. The related terms are **sensitivity** and **specifity**. In the above case, sensitivity is the percentage of true 'up' movements that are identified. A good 88.1% (= 121 / (18 + 121)). The specifity is the percentage of 'down' movements that are correctly identified, here a poor 27.2% (= 31 / (31 + 83)). More on this in the next chapter.

Because confusion matrices are important to analyze results, `Scikit-learn` has its own [command to generate it](http://scikit-learn.org/stable/modules/generated/sklearn.metrics.confusion_matrix.html). It is part of the `metrics` sublibrary. The difficulty is that in contrast to above (manually generated) table, the function's output provides no labels. Therefore one must be sure to know which value are where. Here's the code to generate the confusion matrix.


```python
from sklearn.metrics import confusion_matrix

# Confusion matrix
confusion_matrix(y_test, pred)
```




    array([[ 31,  83],
           [ 18, 121]], dtype=int64)



Often it is helpful to visualize results. `Sklearn` unfortunately doesn't have a specific plotting function for the confusion matrix. However, on the package's website a [function code is provided](http://scikit-learn.org/stable/auto_examples/model_selection/plot_confusion_matrix.html) that does exactly this. Below their code is applied to our KNN results on ABB's stock price movement. 


```python
import itertools
plt.style.use('default')

def plot_confusion_matrix(cm, classes,
                          normalize=False,
                          title='Confusion matrix',
                          cmap=plt.cm.Blues):
    """
    This function prints and plots the confusion matrix.
    Normalization can be applied by setting `normalize=True`.
    """
    if normalize:
        cm = cm.astype('float') / cm.sum(axis=1)[:, np.newaxis]
        print("Normalized confusion matrix")
    else:
        print('Confusion matrix, without normalization')

    print(cm)

    plt.imshow(cm, interpolation='nearest', cmap=cmap)
    plt.title(title)
    plt.colorbar()
    tick_marks = np.arange(len(classes))
    plt.xticks(tick_marks, classes, rotation=45)
    plt.yticks(tick_marks, classes)

    fmt = '.2f' if normalize else 'd'
    thresh = cm.max() / 2.
    for i, j in itertools.product(range(cm.shape[0]), range(cm.shape[1])):
        plt.text(j, i, format(cm[i, j], fmt),
                 horizontalalignment="center",
                 color="white" if cm[i, j] > thresh else "black")

    plt.tight_layout()
    plt.ylabel('True label')
    plt.xlabel('Predicted label')
```


```python
#plt.style.use('default')
# Compute confusion matrix
cfm_matrix = confusion_matrix(y_test, pred)
np.set_printoptions(precision=2)

# Plot non-normalized confusion matrix
plt.figure()
plot_confusion_matrix(cfm_matrix, classes=['Down', 'Up'],
                      title='Confusion matrix, without normalization');
```


```python
# Plot normalized confusion matrix
plt.figure()
plot_confusion_matrix(cfm_matrix, classes=['Down', 'Up'], normalize=True,
                      title='Normalized confusion matrix');
```

# Further Ressources


In writing this notebook, many ressources were consulted. For internet ressources the links are provided within the textflow above and will therefore not be listed again. Beyond these links, the following ressources were consulted and are recommended as further reading on the discussed topics:

* Batista, Gustavo, and Diego Furtado Silva, 2009, How k-nearest neighbor parameters affect its performance, in *Argentine Symposium on Artificial Intelligence*, 1–12, sn.
* Fortmann-Roe, Scott, 2012, Understanding the Bias-Variance Tradeoff from website, http://scott.fortmann-roe.com/docs/BiasVariance.html, 08/15/17.
* Guggenbuehler, Jan P., 2015, Predicting net new money using machine learning algorithms and newspaper articles, Technical report, University of Zurich, Zurich.
* James, Gareth, Daniela Witten, Trevor Hastie, and Robert Tibshirani, 2013, *An Introduction to Statistical Learning: With Applications in R* (Springer Science & Business Media, New York, NY).
* Müller, Andreas C., and Sarah Guido, 2017, *Introduction to Machine Learning with Python* (O’Reilly Media, Sebastopol, CA).
* Russell, Stuart, and Peter Norvig, 2009, *Artificial Intelligence: A Modern Approach* (Prentice Hall Press, Upper Saddle River, NJ).
* Ting, Kai Ming, 2011, Confusion matrix, in Claude Sammut, and Geoffrey I. Webb, eds., *Encyclopedia of Machine Learning* (Springer Science & Business Media, New York, NY).

ee4567a0059abee563396140b38b5c7e9c9e4b18
ipynb
Jupyter Notebook
0207_kNN.ipynb
mauriciocpereira/ML_in_Finance_UZH
d99fa0f56b92f4f81f9bbe024de317a7949f0d38
MIT
0207_kNN.ipynb
mauriciocpereira/ML_in_Finance_UZH
d99fa0f56b92f4f81f9bbe024de317a7949f0d38
MIT
0207_kNN.ipynb
mauriciocpereira/ML_in_Finance_UZH
d99fa0f56b92f4f81f9bbe024de317a7949f0d38
MIT
Qwen/Qwen-72B
1. YES
2. YES