<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Interpolation to a structured grid from a cloud of points
First of all, we have a cloud of XYZ points and we want to predict a vertice of a 2D structured grid based on this cloud of points (I will abreviate that as CP and the structured grid as SG).
It's important to note that, the CP has 3 values which describes each point
Step1:  Loading the points and creating the structured grid
Step2:  Structured Grid
Step3:  Cloud of Points
Step4:  Applying KNN
Step5:  Calculating the radius which the nearest point has to be located
| Symbol  | Meaning | 
|
Step6:  Selecting the points which the distance are equal or less than the radius
Step7:  It is interesting to normalize the distance and subtract the value from 1.  That will be the weight of each distance.
Using the l2 normalization which can be represented by
Step8:  Formula to calculate the value for each vertice of the strcutured grid
$$ P = \frac{\sum_{i=1}^{n} (w_{i}\times Z_i)}{\sum_{j=1}^{n} w_{j}} $$
In Python
Step9:  Example - Map desired
Step10:  Map reconstructed using the algorithm described
Step11:  Error
I'm going to calculate the error of the map reconstructed.
<ASSISTANT_TASK:>
Python Code:
# Imports
import math
import seaborn
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib import cm
from sklearn.neighbors import NearestNeighbors
from sklearn.preprocessing import normalize
Explanation: Interpolation to a structured grid from a cloud of points
First of all, we have a cloud of XYZ points and we want to predict a vertice of a 2D structured grid based on this cloud of points (I will abreviate that as CP and the structured grid as SG).
It's important to note that, the CP has 3 values which describes each point:
* the X value which represents the value in the X axis;
* the Y value which represents the value in the Y axis;
* The Z value which describes a property value (like temperature, or depth, or pressure, etc).
So, I'm going to use KNN (K-Nearest Neighbors) strategy to search for the nearest points of each vertice of the SG and I must predict the property value of that vertice. 
However if the nearest point of the vertice is too far away I will assume that point has to be blank (or in this case I will just put a zero value). I'm going to explain in the next sections how to apply this interpolation.
Obs: For more information about KNN algorithm please visit: 
* http://scikit-learn.org/stable/modules/neighbors.html
* https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm
Imports
End of explanation
# Loading xyz map
correct_map = pd.read_csv('correct_map.xyz', sep=' ', dtype='d', header=None, names=['x', 'y', 'z'])
scattered_data_10000 = pd.read_csv('scattered_data_10000.xyz', sep=' ', dtype='d', header=None, names=['x', 'y', 'z'])
NI = 100
NJ = 100
number_neighbors = 5
# Creating grid points
x_grid = np.linspace(1, 10, NI)
y_grid = np.linspace(1, 10, NJ)
grid_points = pd.DataFrame()
grid_points['x'] = np.tile(x_grid, NJ)
grid_points['y'] = y_grid.repeat(NI)
grid_points['z'] = np.zeros(NI*NJ)
Explanation: Loading the points and creating the structured grid
End of explanation
import matplotlib as mpl
%matplotlib inline
mpl.rcParams['savefig.dpi'] = 250
mpl.rcParams['figure.dpi'] = 250
grid_points.plot(kind='scatter', x='x', y='y', marker='.', s=5)
plt.show()
Explanation: Structured Grid:
End of explanation
scattered_data_10000.plot(kind='scatter', x='x', y='y', marker='.', s=5)
plt.show()
Explanation: Cloud of Points:
End of explanation
# Applying KNN
neighbors = NearestNeighbors(n_neighbors=number_neighbors, algorithm='ball_tree').fit(scattered_data_10000.loc[:, ['x', 'y']])
# Distance and index of each point from each vertice of the grid
distances, indexes = neighbors.kneighbors(grid_points.loc[:, ['x', 'y']])
Explanation: Applying KNN
End of explanation
# Maximum and minimum values in X axis
max_x = grid_points.loc[:, 'x'].max()
min_x = grid_points.loc[:, 'x'].min()
# Maximum and minimum values in Y axis
max_y = grid_points.loc[:, 'y'].max()
min_y = grid_points.loc[:, 'y'].min()
# Step X and Step Y
step_x = (max_x - min_x) / NI
step_y = (max_y - min_y) / NJ
# Radius
radius = 2 * math.sqrt((step_x ** 2) + (step_y ** 2))
Explanation: Calculating the radius which the nearest point has to be located
| Symbol  | Meaning | 
|:------: |:-------:|
|$$ S_x $$| Step in X axis|
|$$ x_{max} $$| Maximum value of X in grid|
|$$ x_{max} $$| Minimum value of X in grid|
|$$ N_i $$ | Number of vertices in X axis|
|$$ S_y $$| Step in Y axis|
|$$ y_{max} $$| Maximum value of Y in grid|
|$$ y_{max} $$| Minimum value of Y in grid|
|$$ N_j $$ | Number of vertices in Y axis|
|$$ R $$ | Radius |
|$$ d_{norm} $$| Distance normalized|
|$$ n $$ | Number of neighbors|
|$$ w $$ | One minus the normalization, represent the weight of each distance |
|$$ P $$ | Result of the scalar points |
|$$ Z $$ | Represents the property value |
Formula to calculate each axis step
$$ S_x = \frac{x_{max} - x_{min}}{N_i} $$
$$ S_y = \frac{y_{max} - y_{min}}{N_j} $$
Formula to calculate the radius which will be the maximum distance which the first nearest point needs to be located
$$ R = 2\sqrt{S_x^2 + S_y^2} $$
In Python:
End of explanation
less_radius = distances[:, 0] <= radius
distances = distances[less_radius, :]
indexes = indexes[less_radius, :]
Explanation: Selecting the points which the distance are equal or less than the radius:
End of explanation
# Using the scikit-learn library
weight_norm = 1 - normalize(distances, axis=1)
Explanation: It is interesting to normalize the distance and subtract the value from 1.  That will be the weight of each distance.
Using the l2 normalization which can be represented by:
$$ d_{norm} = \frac{d}{\sqrt{\sum_{i=1}^{n} d_i}}  $$
The weight of each distance will be:
$$ w = 1 - d_{norm} $$
In python:
End of explanation
prod = weight_norm * scattered_data_10000.values[indexes, 2]
scalars = np.full(NI * NJ, 0.0)
grid_points.loc[less_radius, 'z'] = prod.sum(axis=1) / (weight_norm.sum(axis=1))
Explanation: Formula to calculate the value for each vertice of the strcutured grid
$$ P = \frac{\sum_{i=1}^{n} (w_{i}\times Z_i)}{\sum_{j=1}^{n} w_{j}} $$
In Python:
End of explanation
plt.pcolor(correct_map.values[:, 0].reshape(NI, NJ), correct_map.values[:, 1].reshape(NI, NJ), correct_map.values[:, 2].reshape(NI, NJ), cmap=cm.jet)
Explanation: Example - Map desired
End of explanation
plt.pcolor(grid_points.values[:, 0].reshape(NI, NJ), grid_points.values[:, 1].reshape(NI, NJ), grid_points.values[:, 2].reshape(NI, NJ), cmap=cm.jet)
Explanation: Map reconstructed using the algorithm described
End of explanation
dif_map = correct_map.z - grid_points.z
dif_map.describe()
error = (grid_points.z / correct_map.z) - 1
plt.hist(error)
error[error < 0] *= -1
error.describe()
Explanation: Error
I'm going to calculate the error of the map reconstructed.
End of explanation
<END_TASK>