# Nearest Neighbours and Sparse Features¶

While trying to apply k-nearest neighbours classifier database, we might face a tricky issue. Let’s try to find out what it is, why it is happening and how to solve it.

from jyquickhelper import add_notebook_menu

c:python370_x64libsite-packagesipykernelparentpoller.py:116: UserWarning: Parent poll failed.  If the frontend dies,
the kernel may be left running.  Please let us know
ipython-dev@scipy.org
ipython-dev@scipy.org""")

## Get the data¶

We use the package mnist.

import mnist
train_images = mnist.train_images()
train_labels = mnist.train_labels()
test_images = mnist.test_images()
test_labels = mnist.test_labels()

train_images.shape, train_labels.shape

((60000, 28, 28), (60000,))

train_X = train_images.reshape((train_images.shape[0], train_images.shape[1] * train_images.shape[2]))
test_X = test_images.reshape((test_images.shape[0], test_images.shape[1] * test_images.shape[2]))

train_X.shape, train_labels.shape

((60000, 784), (60000,))

train_X[:2]

array([[0, 0, 0, ..., 0, 0, 0],
[0, 0, 0, ..., 0, 0, 0]], dtype=uint8)


## Train a classifier¶

from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(algorithm="kd_tree")
knn

KNeighborsClassifier(algorithm='kd_tree', leaf_size=30, metric='minkowski',
metric_params=None, n_jobs=1, n_neighbors=5, p=2,
weights='uniform')

knn.fit(train_X, train_labels)

KNeighborsClassifier(algorithm='kd_tree', leaf_size=30, metric='minkowski',
metric_params=None, n_jobs=1, n_neighbors=5, p=2,
weights='uniform')


The memory consumption is quite huge. The first hill is training, the second one is the beginning of testing.

from pyquickhelper.helpgen.utils_sphinx_config import NbImage
NbImage("images/train.png")


## Predict¶

# do not do it, it takes for ever.
# yest = knn.predict(test_X)

NbImage("images/test.png")


## Enigma¶

The process almost does not end. We chose a k-d tree to optimize the neighbours search. Why does it take so much memory and so much time? What would you do to optimize it?