Nearest Neighbours and Sparse Features

Links: notebook, html, PDF, python, slides, GitHub

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
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
                about your system (bitness, Python, etc.) at
                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?