﻿ Nearest Neighbor Interpolation
HOME Mathematics Computer Science Economics
Nearest Neighbor Interpolation
Prerequisites
Show All
Hide All
Interpolation
Show/Hide
﻿
Introduction
• If we are given a set of data points:  X 1 2 3 4 5 6 7 y 28 21 96 96 120 87 50
• We know the value of y when x is a whole number, i.e. 1, 2, 3
• But when x is 1.5 we do not have a corresponding value for y.
• Interpolation is the method of estimating the value of y for a given x when we don't have a data point for it.

Nearest Neighbor Interpolation
﻿
Introduction
• Nearest neighbor interpolation is the most simple type of interpolation.
• To find the value of a point which is not in the given set of points:
1. Find the closest point for which you do have a value.
2. Use its value.
Example
• If we are given a set of data points:  X 1 2 3 4 5 6 7 y 28 21 96 96 120 87 50
Find the value for y when x is 2.4
1. The point which has the closest x to 2.4 is (2, 21)
2. When x is 2.4, y is 21
Visualization
Code (using SciPy)
```from scipy import interpolate

dataPoints = [
[1, 28],
[2, 21],
[3, 96],
[4, 96],
[5, 120],
[6, 87],
[7, 50]
]

interpolator = interpolate.interp1d(
[dataPoint[0] for dataPoint in dataPoints],
[dataPoint[1] for dataPoint in dataPoints],
'nearest')

print(interpolator(2.4)) # prints 21
print(interpolator(2.6)) # prints 96
```
Code (using NumPy)
```import numpy as np

class NearestNeighborInterpolator:
# an array of x values, in order
_sortedDomain = []

# a dictionary of x, y values
_dataPointsDict = {}

def __init__(self, dataPoints):
for dataPoint in dataPoints:
self._dataPointsDict[dataPoint[0]] = dataPoint[1]

self._sortedDomain = [dataPoint[0] for dataPoint in dataPoints]
self._sortedDomain = np.sort(self._sortedDomain)

def interpolate(self, x):
# find the index of the smallest element larger than x
closest = np.searchsorted(self._sortedDomain, x)

# either 'closest' or 'closest - 1' will be closest to x
if abs(self._sortedDomain[closest - 1] - x) < abs(self._sortedDomain[closest] - x):
closest -= 1

# look up the corresponding y value for our value closest to x
y = self._dataPointsDict[self._sortedDomain[closest]]

return y

dataPoints = [
[1, 28],
[2, 21],
[3, 96],
[4, 96],
[5, 120],
[6, 87],
[7, 50]
]

interpolator = NearestNeighborInterpolator(dataPoints)

print(interpolator.interpolate(2.4)) # prints 21
print(interpolator.interpolate(2.6)) # prints 96
```