# The Soil Nutrient Spatial Interpolation Algorithm Based on KNN and IDW

Xin Xu, Hua Yu, Guang Zheng, Hao Zhang, Lei Xi

► To cite this version:

Xin Xu, Hua Yu, Guang Zheng, Hao Zhang, Lei Xi. The Soil Nutrient Spatial Interpolation Algorithm Based on KNN and IDW. 9th International Conference on Computer and Computing Technologies in Agriculture (CCTA), Sep 2015, Beijing, China. pp.412-424, 10.1007/978-3-319-48357-3_40. hal-01557849

HAL Id: hal-01557849

https://inria.hal.science/hal-01557849v1

Submitted on 6 Jul 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# The Soil Nutrient Spatial Interpolation Algorithm Based on KNN and IDW

Xin XU<sup>1,3</sup>, Hua YU<sup>1,3</sup>, guang ZHENG<sup>1,3</sup>, Hao ZHANG<sup>1,2,3</sup>, Lei XI<sup>1,2,3,*</sup>

<sup>1</sup>College of Information and Management Science, Henan Agricultural University, Zhengzhou 450002, China;

<sup>2</sup>Henan grain crops Collaborative Innovation Center, Zhengzhou 450002, China;

<sup>3</sup>Ministry of Agriculture Agricultural Information Technology Science Observation Station in Huanghuaihai district, Zhengzhou 450002, China

**Abstract.** For breaking the limitation of the GIS platform and realizing the soil nutrients spatial interpolation algorithm for any points in the monitoring area to transplant to the mobile platforms, this paper established the spatial index of the soil nutrient sampling points utilizing the K-D Tree as the space splitting algorithm of the soil nutrient sampling points. On this basis, the K nearest neighbor search of the soil nutrient sampling points was also implemented employing KNN algorithm. Finally, the soil nutrient spatial interpolation was realized based on KNN and IDW algorithm. Meanwhile, the accuracy of the algorithm and the influence to the different soil nutrient elements affected by the K value in KNN algorithm were also verified. The results show that the soil nutrient spatial interpolation algorithm was viable to predict the element contents of soil nutrient during the running time was less than 3s. To reach the best accuracy, the values of the proximal point K for predicting the PH, organic matter, rapid available phosphorus and rapid available potassium should be set as 85, 15, the largest sample space and 65 respectively. The optimal average absolute error of the pH, organic matter, rapid available phosphorus and rapid available potassium was 0.0405, 0.3870, 0.0015 respectively.

**Keywords:** IDW, KNN, KD-Tree, Soil Nutrient, Spatial Interpolation

## 1 Introduction

Due to the problems of the obtaining the sampling points data of the soil testing and formulated fertilization such as difficult sampling<sup>[1]</sup>, heavy workload<sup>[2]</sup>, high cost<sup>[3]</sup> and so on, the data points during the fertilizing decision stage in the process of testing soil for formulated fertilization was not enough to achieve the complete coverage for the field parcel in each region. Therefore, the sampling point soil nutrient data of the currently unknown spatial points were obtained on the basis of interpolation operation of the existing sampling point data frequently in real application. The utilizing of spatial interpolation technology was commonly used method. In the method, the statistical methods were applied to the nutrient data of some smaller density soil sample points to conduct interpolation operation to the data from the points that were not sampled to form the more dense point data distribution or the area data of
different areal unit. The soil nutrient values of the points which were not sampled
were predicted scientifically. Then, the precise fertilization could be implemented to
the whole area.

Following the rapid development of the mobile intelligent terminal and the distributed computing technology, the computing and data processing of more and more applications was transferred to client-side. Due to the frequent disconnection[5] and low reliability[6] of mobile GIS, most of space interpolation for mobile side had to rely on the service side in the using. It made the usage scenarios of the mobile-oriented space interpolation limited. Thus, making full advantage of modern computer technology could provide more configurable, extensible and customizable distributed applications and made traditional soil testing and formulated fertilization recommendation system running in embedded devices such as high performance and low cost mobile intelligent terminal possible. However, most of current soil testing and formulated fertilization system, and soil nutrient spatial interpolation technology, were based on the GIS platform and hard to be transplanted to mobile platform. Hence, to realize the soil nutrient inquiry to any land parcel and the fertilization information recommendation by the users through intelligent mobile terminals and the personalized recommendation of the soil testing and fertilizer recommendation technology by fully integrating mobile technology and soil testing formula technology, the researching of a type of soil nutrient spatial interpolation technology which was divorced from the limitation of the GIS platform was significant for the application and popularization of soil testing formula fertilization technology.

2 Material and Methods

2.1 Source of Material

The data in this paper came from the 238 soil nutrient sampling points in 10 thousand mu precision agriculture model production field of Changge city, Henan province in 2014. The sampling point data was consist of sampling number, numbering of land parcel, soil texture, preceding crop, PH values, organic matter, rapidly available phosphorus, rapidly available potassium, latitude and longitude information.

## 2.2 Research Method

2.2.1 Inverse Distance Weighted (IDW) Interpolation

At present, there were many kinds of methods for the soil nutrient interpolation. In which methods, the Inverse Distance Weighted interpolation (IDW) and Kriging interpolation were considered to be the most widely used two common interpolation methods. The Kriging interpolation was often influenced
by many factors in actual application错误!未找到引用源. 18错误!未找到引用源.. Considering the space complexity of Kriging interpolation algorithm, the Inverse Distance Weighted interpolation was adopted in this study to design the interpolation algorithm for the soil nutrient data.

The inverse distance weighted interpolation was based on the theory of “like similarity principle”. Through the calculating of the inverse distance weighted average of the discrete points of nearby area, the value in the cell was also calculated. According to the principle that the point with closer distance had the greater weighting values, the value of the estimate point was fitted employing the linear weighting of some neighboring points around.

This algorithm was a simple and effective data interpolation method with relatively fast computing speed. However, it also had the obvious flaws. For example, the method only considered the space distance between the estimation points and the interpolation points. Moreover, the weight calculation used in the algorithm lacked the exact physical basis错误!未找到引用源. 20].

### 2.2.2 K-Nearest Neighbor (KNN) Algorithm and Spatial Index of Soil Nutrient Sampling Points Based on K-D Tree

The soil nutrient content of the sampling point was not only affected by the change of the sample point distance, but also was affected by many other factors such as soil texture variation. Therefore, the K-Nearest Neighbor algorithm was also introduced in the process of the adjacent points selecting and searching during the process of the interpolation to the soil nutrient using inverse distance weighted interpolation to improve the IDW algorithm.

K-Nearest Neighbor (KNN) sorting algorithm was proposed by Cover and Hart in 1967错误!未找到引用源. It was a simple algorithm based on analogy and had become one of the most mature machine learning algorithms in theory at present. The idea of the algorithm was: if most of the k most similar (i.e., the adjacent) samples of a sample in the characteristic space belonged to a category, then the sample also belonged to this category. If the query point and the positive integer K were given, the k closest data to the query point were also found from the data set.

The realization of the KNN algorithm was based on the establishment of the spatial index for data. The commonly used algorithms for establishment of a spatial index in GIS interpolation algorithm has K-D tree, K-D-B tree, BSP tree, R tree series, quadtree, grid and many other spatial index[21]. K-D (K dimension search binary tree) was a main memory data structure to generalize binary tree to multidimensional data and a type of binary tree in K dimension space. It was also a type of dynamic index structure for the segmentation of data space and suited for the space point target indexing[22]. Therefore, this paper constructed the spatial index algorithm of the soil nutrient utilizing the K-D tree.

## 3 Design and Simulation of Algorithm
## 3.1 Workflow Design

The idea of the soil nutrient spatial interpolation algorithm based on KNN and IDW proposed in this paper was: Constructing the KD-Tree firstly to establish the index space of the soil nutrient data sampling points. After that, the sampling point data set was further screened. The specific method was: using the given soil nutrient training data set, the tree structure data index was constructed adopting the space partitioning tree KD tree to conduct the hierarchical division for the search space of soil sampling point. After that, the fast matching was conducted to the new input sampling point data to find the nearest neighboring K sampling points of the sampling point in the training data set. The K sampling point data would be used as the spatial interpolation data. The algorithm process was shown in Figure 1.
1. Reading the interpolation sampling point data

2. Pre-processing to the sampling point data

3. Establishing the spatial index

4. Conducting the space partition to the data

5. Screening data sets and forming the preparative interpolation data set

6. Judging whether accordant with the soil texture of the current sampling point

7. Selecting the final interpolation data set

8. Judging the number of the data in final data set "cout"

9. Calculating the weighted average of the data points

10. Calculating and outputting the interpolation results
<caption>Fig. 1. The process design of algorithm</caption>

(1) Reading the current sampling point data set and ready for operation;
(2) Conducting the data pre-processing to the sampling point data and removing critical value such as the outliers and the value beyond administrative boundary and so on to reduce the measuring error of the interpolation results;
(3) Constructing the KD tree and establishing the spatial index of the sampling point data;
(4) Conducting the space partition to the soil nutrient sampling point data using the KD tree;
(5) Conducting the screening to current data set utilizing the K-Nearest Neighbor algorithm to seek the nearest neighbor sampling point data of the current interpolation sampling point data to form the preparative interpolation data set;
(6) Traversing the current sample point data set, judging the data whether was accordant with the soil texture of the current sampling point. If the data was inconsonant with the soil texture of the current sampling point, the data would be discarded.
(7) Selecting the final interpolation data set based on the step 6;
(8) Judging whether the number of the data in final data set “cout” was less than 2, if “cout” was less than 2, this time interpolation was fail and returned the “false” information. Otherwise, the process continued.
(9) Looping through the data set and calculating the weighted average of the current unknown sample points with the current data points.
(10) Calculating and outputting the interpolation results based on inverse distance weighted interpolation.

3.2 Algorithm Implementation

Based on the above algorithm design, the process of the algorithm implementation consisted of the following three steps: 1. KD tree Constructing, 2. K neighboring searching, 3. the inverse distance weighted interpolation calculation.

1. KD tree Constructing

The KD tree data structure was established firstly in the algorithm. After that, the
KD tree was constructed based on KD tree data structure. The steps of the algorithm
were as follows:

(1) If the sampling point data sets “Dataset” was empty, the empty KD tree was returned. Otherwise, the node generation program would be executed.

(2) Determine the maximum variance dimension the “Split” domain. The maximum variances in each space dimension of all the sampling point data which prepared for interpolation were counted. The maximal dimension in their variance was elected as the space division dimension. The quantitative value was used as the value of the “Split” domain.

(3) The root Node “Node” was confirmed. The data of the selected space partition dimension was sorted. The sampling point data located in the middle was used as the data of the “Node” node.

(4) The left subspace “leftNodeData” and the right subspace “rightNodeData” of
the “Node” were determined. The data of the sampling points whose space dimension
was less than the "Node" node was used as the data of the left subspace of the "Node" node. The data of the sampling points whose space dimension was larger than the "Node" node was used as the data of the right subspace of the "Node" node.

(5) The above process was recursive to conduct the space division partition for the "leftNodeData" and the "rightNodeData" until the subspace had not data.

## 2. K-Nearest Neighbor Searching

The KD tree nearest neighbor search query algorithm was adopted in this study to construct the KD tree "Kd". Adopting the target point "target" as the input, employing the obtained K nearest neighboring "nearest" sets of the "target" as the output, the steps of the K search algorithm establishment were as follows:

(1) The leaf nodes containing the target point "target" were found from the KD tree. From the root node, the KD tree was recursively searched downward. If the coordinates of the current dimension of the target point "target" was less than the coordinate of the split points, the target point "target" was moved to the left child node space. Otherwise, it was moved to the right child node.

(2) The leaf node searched in step 1 was used as the current nearest point "currnearest".

(3) The other possible nearest points were backtracked recursively. If there was a node closer the target point "target" than the current nearest point "currnearest", the value of the current "currnearest" was updated.

(4) When the backtracking backed to the root node, the search ended. The last nearest point "currnearest" was the nearest neighboring point of the "target".

(5) The current nearest neighboring point was deposited in the "nearest" set and removed from the tree of Kd.

(6) The above process was repeated until the number of set elements in the "nearest" was equal to K. Stopped the search and returned back to the "nearest" set.

## 3. Inverse Distance Weighted Interpolation

Based on the KD tree generating algorithm, the spatial index tree of the current sample sampling points was constructed. On the basis of this, the K nearest-neighbor sampling points were searched out combining k-nearest neighbor algorithm to form the nearest-neighbor set "nearest". Employing the nearest-neighbor set "nearest" and the target point "target" as the input, the sampling points data of the current sampling points was conducted the spatial interpolation processing adopting the inverse distance weighted interpolation. The algorithm steps were as follows:

(1) Calculating the distance between the target point "target" and the sampling points in the nearest-neighbor set "nearest". Traversal the "nearest" set and calculating the distance from the "target" to each nearest-neighbor sampling point.

(2) Calculating the weight of each point. The weight of each sampling point in the nearest-neighbor set "nearest" was calculated to be used as the weight during the interpolation.

(3) Calculating the results of the weighted interpolation. Traversal the "nearest" neighboring set. The results was worked out based on the weight of each point and returned.
## 4 Design and Analysis of Experiments

Adopting the data from 238 soil nutrient sampling points in 10 thousand mu precision agriculture model production field of Changge city, Henan province in 2014 as the data source, the ARM CPU architecture as mobile hardware environment(1.6 GHz, 4 core), the above soil nutrient interpolation calculation method was realized based on the Android 4.4 mobile platform. As shown in figure 2, the pH, organic matter, rapid available phosphorus and rapid available potassium in the sample data were conducted the spatial interpolation processing and effect analysis during the algorithm implementation efficiency was less than 3s.

<figure><img src="image_2.png" /><figcaption>Fig. 2. Algorithm running results</figcaption></figure>

The Figure 2 showed the results page after interpolation to the 10 nearest-neighbor sampling point data. By the program, the nutrient content of the current point was predicted through the interpolation to the pH, organic matter, rapid available phosphorus and rapid available potassium of the current point and contrasted with the actual value.

The effect analysis of algorithm adopting the cross validation method: a small number of samples of the sampling data of nutrients were screened and reserved to be not involved in the interpolation. These reserved samples were conducted comparative evaluation with the interpolation results. That meant that the model established by the most of the sample was used to conduct the small sample prediction. Meanwhile, the error of prediction was also obtained. The mean absolute error, average relative error and root-mean-square error was used as the standard of measuring the interpolation precision.

错误!未找到引用源。错误!未找到引用源。

In this experiment, the randomly selected 50 sample points from the total samples were used as the data waiting for interpolation and need to be predicted. The rest of the sample points were used as the interpolation data. After many times of experiment,
the influence of the different number of the nearest-neighbor to the result data of the sampling point was tested under the same soil texture. The interpolation results analysis were shown in the tables below:

<table><caption>Table 1. Results Statistic of pH Values</caption><thead><tr><th rowspan="2">Nu<br>mber<br>of<br>adjacen<br>t points</th><th colspan="4">Absolute error</th><th colspan="2">Relative error</th><th rowspan="2">Root-<br>mean-<br>square<br>error</th></tr><tr><th>Ma<br>ximum<br>value</th><th>Mini<br>mum<br>value</th><th>Mean<br>value</th><th>Maximum<br>value</th><th>Minimum<br>value</th><th>Mean<br>value</th></tr></thead><tbody><tr><td>5</td><td>1.2</td><td>-1.75</td><td>0.0365</td><td>0.203725</td><td>0.004342</td><td>0.068</td><td>0.468</td></tr><tr><td>10</td><td>1.17</td><td>-1.72</td><td>0.0405</td><td>0.200233</td><td>0.004342</td><td>0.066</td><td>0.456</td></tr><tr><td>15</td><td>1.15</td><td>-1.7</td><td>0.0390</td><td>0.197905</td><td>0.004342</td><td>0.065</td><td>0.448</td></tr><tr><td>20</td><td>1.14</td><td>-1.7</td><td>0.0405</td><td>0.197905</td><td>0.004292</td><td>0.065</td><td>0.447</td></tr><tr><td>25</td><td>1.13</td><td>-1.7</td><td>0.0395</td><td>0.197905</td><td>0.002894</td><td>0.065</td><td>0.444</td></tr><tr><td>30</td><td>1.12</td><td>-1.7</td><td>0.0390</td><td>0.197905</td><td>0.002894</td><td>0.065</td><td>0.443</td></tr><tr><td>35</td><td>1.12</td><td>-1.7</td><td>0.0390</td><td>0.197905</td><td>0.002894</td><td>0.065</td><td>0.442</td></tr><tr><td>40</td><td>1.12</td><td>-1.7</td><td>0.0385</td><td>0.197905</td><td>0.002894</td><td>0.065</td><td>0.442</td></tr><tr><td>45</td><td>1.12</td><td>-1.7</td><td>0.0380</td><td>0.197905</td><td>0.002894</td><td>0.064</td><td>0.441</td></tr><tr><td>50</td><td>1.11</td><td>-1.69</td><td>0.0395</td><td>0.19674</td><td>0.002861</td><td>0.064</td><td>0.438</td></tr><tr><td>55</td><td>1.11</td><td>-1.69</td><td>0.0385</td><td>0.19674</td><td>0.002861</td><td>0.064</td><td>0.438</td></tr><tr><td>60</td><td>1.11</td><td>-1.69</td><td>0.0390</td><td>0.19674</td><td>0.002861</td><td>0.064</td><td>0.438</td></tr><tr><td>65</td><td>1.11</td><td>-1.69</td><td>0.0385</td><td>0.19674</td><td>0.002861</td><td>0.064</td><td>0.438</td></tr><tr><td>70</td><td>1.11</td><td>-1.69</td><td>0.0385</td><td>0.19674</td><td>0.002861</td><td>0.064</td><td>0.436</td></tr><tr><td>75</td><td>1.11</td><td>-1.68</td><td>0.0400</td><td>0.195576</td><td>0.002861</td><td>0.064</td><td>0.436</td></tr><tr><td>80</td><td>1.1</td><td>-1.68</td><td>0.0405</td><td>0.195576</td><td>0.002861</td><td>0.064</td><td>0.436</td></tr><tr><td>85</td><td>1.1</td><td>-1.68</td><td>0.0405</td><td>0.195576</td><td>0.002861</td><td>0.064</td><td>0.436</td></tr><tr><td>90</td><td>1.1</td><td>-1.68</td><td>0.0425</td><td>0.195576</td><td>0.002861</td><td>0.064</td><td>0.436</td></tr><tr><td>95</td><td>1.1</td><td>-1.68</td><td>0.0435</td><td>0.195576</td><td>0.001431</td><td>0.064</td><td>0.436</td></tr><tr><td>100</td><td>1.1</td><td>-1.68</td><td>0.0440</td><td>0.195576</td><td>0.001431</td><td>0.063</td><td>0.436</td></tr></tbody></table>

<table><caption>Table 2. Results Statistic of Organic Material</caption><thead><tr><th rowspan="2">Nu<br>mber<br>of<br>adjacen</th><th colspan="4">Absolute error</th><th colspan="2">Relative error</th><th rowspan="2">Root-<br>mean-<br>square<br>error</th></tr><tr><th>Maxi<br>mum</th><th>Mini<br>mum</th><th>Mean<br>value</th><th>Maximu<br>m value</th><th>Minimu<br>m value</th><th>Mean<br>value</th></tr></thead><tbody></tbody></table>
<table><caption>Table 3 Results Statistic of Rapidly Available Phosphorus</caption><thead><tr><th>t points</th><th>value</th><th>value</th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>5</td><td>11.76</td><td>-5.08</td><td>0.4455</td><td>1.4067</td><td>0.0089</td><td>0.1507</td><td>2.539</td></tr><tr><td>10</td><td>11.17</td><td>-5.21</td><td>0.4070</td><td>1.3361</td><td>0.0013</td><td>0.1415</td><td>2.426</td></tr><tr><td>15</td><td>11</td><td>-5.09</td><td>0.3870</td><td>1.3158</td><td>0.0009</td><td>0.1417</td><td>2.414</td></tr><tr><td>20</td><td>10.96</td><td>-4.98</td><td>0.4205</td><td>1.3110</td><td>0.0012</td><td>0.1389</td><td>2.422</td></tr><tr><td>25</td><td>10.92</td><td>-4.97</td><td>0.4415</td><td>1.3062</td><td>0.0029</td><td>0.1381</td><td>2.430</td></tr><tr><td>30</td><td>10.9</td><td>-4.96</td><td>0.4500</td><td>1.3038</td><td>0.0053</td><td>0.1380</td><td>2.430</td></tr><tr><td>35</td><td>10.89</td><td>-5</td><td>0.4565</td><td>1.3026</td><td>0.0059</td><td>0.1390</td><td>2.450</td></tr><tr><td>40</td><td>10.88</td><td>-5</td><td>0.4540</td><td>1.3014</td><td>0.0076</td><td>0.1389</td><td>2.450</td></tr><tr><td>45</td><td>10.87</td><td>-5</td><td>0.4525</td><td>1.3002</td><td>0.0082</td><td>0.1390</td><td>2.448</td></tr><tr><td>50</td><td>10.86</td><td>-5.02</td><td>0.4490</td><td>1.2990</td><td>0.0094</td><td>0.1395</td><td>2.451</td></tr><tr><td>55</td><td>10.88</td><td>-5.06</td><td>0.4440</td><td>1.3014</td><td>0.0099</td><td>0.1405</td><td>2.462</td></tr><tr><td>60</td><td>10.88</td><td>-5.09</td><td>0.4460</td><td>1.3014</td><td>0.0099</td><td>0.1409</td><td>2.464</td></tr><tr><td>65</td><td>10.89</td><td>-5.13</td><td>0.4495</td><td>1.3026</td><td>0.0099</td><td>0.1413</td><td>2.467</td></tr><tr><td>70</td><td>10.88</td><td>-5.15</td><td>0.4635</td><td>1.3014</td><td>0.0099</td><td>0.1416</td><td>2.467</td></tr><tr><td>75</td><td>10.89</td><td>-5.19</td><td>0.4640</td><td>1.3026</td><td>0.0099</td><td>0.1425</td><td>2.473</td></tr><tr><td>80</td><td>10.9</td><td>-5.21</td><td>0.4720</td><td>1.3038</td><td>0.0099</td><td>0.1429</td><td>2.478</td></tr><tr><td>85</td><td>10.91</td><td>-5.22</td><td>0.4780</td><td>1.3050</td><td>0.0094</td><td>0.1436</td><td>2.484</td></tr><tr><td>90</td><td>10.91</td><td>-5.21</td><td>0.4830</td><td>1.3050</td><td>0.0099</td><td>0.1442</td><td>2.488</td></tr><tr><td>95</td><td>10.91</td><td>-5.21</td><td>0.4835</td><td>1.3050</td><td>0.0103</td><td>0.1446</td><td>2.490</td></tr><tr><td>100</td><td>10.92</td><td>-5.2</td><td>0.4790</td><td>1.3062</td><td>0.0108</td><td>0.1448</td><td>2.493</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Nu<br>ber<br>of<br>adjace<br>nt<br>points</th><th colspan="4">Absolute error</th><th colspan="2">Relative error</th><th rowspan="2">Root-<br>mean-<br>square<br>error</th></tr><tr><th>Ma<br>ximum<br>value</th><th>Minim<br>um value</th><th>Mean<br>value</th><th>Maximu<br>m value</th><th>Minimu<br>m value</th><th>Mean<br>value</th></tr></thead><tbody><tr><td>5</td><td>8.16</td><td>-18.28</td><td>-1.7905</td><td>1.1209</td><td>0.0019</td><td>0.3219</td><td>6.9795</td></tr><tr><td>10</td><td>8.15</td><td>-17.75</td><td>-1.7320</td><td>1.1195</td><td>0.0102</td><td>0.3178</td><td>6.6646</td></tr></tbody></table>
<table><caption>Table 4 Results Statistic of Rapidly Available Potassium</caption><tr><td>15</td><td>8.06</td><td>-17.84</td><td>-1.7665</td><td>1.1071</td><td>0.0015</td><td>0.3166</td><td>6.5797</td></tr><tr><td>20</td><td>8.01</td><td>-17.76</td><td>-1.7455</td><td>1.1003</td><td>0.0029</td><td>0.3162</td><td>6.5122</td></tr><tr><td>25</td><td>7.99</td><td>-17.76</td><td>-1.7300</td><td>1.0975</td><td>0.0031</td><td>0.3169</td><td>6.4578</td></tr><tr><td>30</td><td>7.97</td><td>-17.79</td><td>-1.7420</td><td>1.0948</td><td>0.0051</td><td>0.3171</td><td>6.4259</td></tr><tr><td>35</td><td>7.95</td><td>-17.8</td><td>-1.7550</td><td>1.0920</td><td>0.0072</td><td>0.3177</td><td>6.4065</td></tr><tr><td>40</td><td>7.94</td><td>-17.77</td><td>-1.7735</td><td>1.0907</td><td>0.0072</td><td>0.3170</td><td>6.3900</td></tr><tr><td>45</td><td>7.93</td><td>-17.74</td><td>-1.7910</td><td>1.0893</td><td>0.0093</td><td>0.3179</td><td>6.3834</td></tr><tr><td>50</td><td>7.92</td><td>-17.7</td><td>-1.7915</td><td>1.0879</td><td>0.0103</td><td>0.3185</td><td>6.3733</td></tr><tr><td>55</td><td>7.92</td><td>-17.68</td><td>-1.7970</td><td>1.0879</td><td>0.0113</td><td>0.3181</td><td>6.3628</td></tr><tr><td>60</td><td>7.9</td><td>-17.68</td><td>-1.7950</td><td>1.0852</td><td>0.0144</td><td>0.3186</td><td>6.3545</td></tr><tr><td>65</td><td>7.9</td><td>-17.68</td><td>-1.7955</td><td>1.0852</td><td>0.0175</td><td>0.3184</td><td>6.3513</td></tr><tr><td>70</td><td>7.9</td><td>-17.68</td><td>-1.8010</td><td>1.0852</td><td>0.0175</td><td>0.3182</td><td>6.3490</td></tr><tr><td>75</td><td>7.9</td><td>-17.67</td><td>-1.8060</td><td>1.0852</td><td>0.0175</td><td>0.3179</td><td>6.3439</td></tr><tr><td>80</td><td>7.9</td><td>-17.67</td><td>-1.8145</td><td>1.0852</td><td>0.0163</td><td>0.3180</td><td>6.3433</td></tr><tr><td>85</td><td>7.89</td><td>-17.66</td><td>-1.8160</td><td>1.0838</td><td>0.0116</td><td>0.3181</td><td>6.3410</td></tr><tr><td>90</td><td>7.89</td><td>-17.67</td><td>-1.8160</td><td>1.0838</td><td>0.0088</td><td>0.3184</td><td>6.3395</td></tr><tr><td>95</td><td>7.89</td><td>-17.67</td><td>-1.8205</td><td>1.0838</td><td>0.0075</td><td>0.3185</td><td>6.3384</td></tr><tr><td>100</td><td>7.89</td><td>-17.67</td><td>-1.8285</td><td>1.0838</td><td>0.0034</td><td>0.3183</td><td>6.3368</td></tr></table>

<table><thead><tr><th rowspan="2">Nu<br>mber<br>of<br>adjace<br>nt<br>points</th><th rowspan="2">Ma<br>ximum<br>value</th><th colspan="3">Absolute error</th><th colspan="3">Relative error</th><th rowspan="2">Root-<br>mean-square<br>error</th></tr><tr><th>Minim<br>um value</th><th>Mean<br>value</th><th>Maximu<br>m value</th><th>Minimu<br>m value</th><th>Mean<br>value</th></tr></thead><tbody><tr><td rowspan="2">5</td><td>57.7</td><td></td><td></td><td></td><td></td><td></td><td>0.196</td><td></td></tr><tr><td>1</td><td>-47.5</td><td>0.0200</td><td>0.4809</td><td>0.0110</td><td>4</td><td>0.195</td><td>24.2538</td></tr><tr><td rowspan="2">10</td><td>57.1</td><td></td><td></td><td></td><td></td><td></td><td>0.195</td><td></td></tr><tr><td>6</td><td>-48.44</td><td>-0.4010</td><td>0.5057</td><td>0.0180</td><td>8</td><td>0.194</td><td>24.3808</td></tr><tr><td rowspan="2">15</td><td>56.7</td><td></td><td></td><td></td><td></td><td></td><td>0.194</td><td></td></tr><tr><td>4</td><td>-49.41</td><td>-0.2720</td><td>0.5072</td><td>0.0124</td><td>2</td><td>0.192</td><td>24.3740</td></tr><tr><td rowspan="2">20</td><td>56.5</td><td></td><td></td><td></td><td></td><td></td><td>0.192</td><td></td></tr><tr><td>2</td><td>-50.03</td><td>-0.3100</td><td>0.4966</td><td>0.0090</td><td>3</td><td>0.190</td><td>24.2862</td></tr><tr><td rowspan="2">25</td><td>56.2</td><td></td><td></td><td></td><td></td><td></td><td>0.190</td><td></td></tr><tr><td>5</td><td>-50.09</td><td>-0.2755</td><td>0.4954</td><td>0.0084</td><td>8</td><td>0.189</td><td>24.1878</td></tr><tr><td rowspan="2">30</td><td>55.9</td><td></td><td></td><td></td><td></td><td></td><td>0.189</td><td></td></tr><tr><td>5</td><td>-50.21</td><td>-0.2020</td><td>0.4999</td><td>0.0037</td><td>9</td><td>0.189</td><td>24.1507</td></tr><tr><td rowspan="2">35</td><td>55.7</td><td></td><td></td><td></td><td></td><td></td><td>0.189</td><td></td></tr><tr><td>3</td><td>-50.29</td><td>-0.0700</td><td>0.5020</td><td>0.0015</td><td>7</td><td>0.189</td><td>24.1325</td></tr><tr><td rowspan="2">40</td><td>55.5</td><td></td><td></td><td></td><td></td><td></td><td>0.189</td><td></td></tr><tr><td>7</td><td>-50.35</td><td>-0.0160</td><td>0.5028</td><td>0.0012</td><td>3</td><td>0.188</td><td>24.0965</td></tr><tr><td rowspan="2">45</td><td>55.4</td><td></td><td></td><td></td><td></td><td></td><td>0.188</td><td></td></tr><tr><td>1</td><td>-50.49</td><td>-0.0160</td><td>0.5035</td><td>0.0011</td><td>7</td><td>0.189</td><td>24.0536</td></tr><tr><td rowspan="2">50</td><td>55.2</td><td></td><td></td><td></td><td></td><td></td><td>0.189</td><td></td></tr><tr><td>8</td><td>-50.56</td><td>0.0645</td><td>0.5024</td><td>0.0023</td><td>1</td><td>0.189</td><td>24.0341</td></tr></tbody></table>
<table><tr><td>55</td><td>55.1</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td></td><td>5</td><td>-50.65</td><td>0.0175</td><td>0.5003</td><td>0.0019</td><td>8</td><td>23.9893</td></tr><tr><td>60</td><td>55.0</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td></td><td>3</td><td>-50.69</td><td>0.0065</td><td>0.4993</td><td>0.0023</td><td>8</td><td>23.9824</td></tr><tr><td>65</td><td>55</td><td>-50.74</td><td>0.0015</td><td>0.4980</td><td>0.0031</td><td>5</td><td>23.9818</td></tr><tr><td></td><td>54.9</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td>70</td><td>5</td><td>-50.84</td><td>-0.0190</td><td>0.4979</td><td>0.0035</td><td>5</td><td>23.9995</td></tr><tr><td></td><td>54.8</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td>75</td><td>8</td><td>-50.94</td><td>-0.0210</td><td>0.4967</td><td>0.0042</td><td>6</td><td>24.0169</td></tr><tr><td></td><td>54.8</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td>80</td><td>4</td><td>-50.97</td><td>-0.0220</td><td>0.4962</td><td>0.0043</td><td>5</td><td>24.0312</td></tr><tr><td></td><td>54.7</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td>85</td><td>9</td><td>-51.04</td><td>0.0215</td><td>0.4958</td><td>0.0044</td><td>5</td><td>24.0372</td></tr><tr><td></td><td>54.7</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td>90</td><td>5</td><td>-51.04</td><td>0.0115</td><td>0.4952</td><td>0.0044</td><td>2</td><td>24.0579</td></tr><tr><td></td><td>54.7</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td>95</td><td>1</td><td>-51.1</td><td>-0.0100</td><td>0.4942</td><td>0.0042</td><td>2</td><td>24.0725</td></tr><tr><td></td><td>54.6</td><td></td><td></td><td></td><td></td><td>0.188</td></tr><tr><td>100</td><td>8</td><td>-51.18</td><td>-0.0450</td><td>0.4933</td><td>0.0040</td><td>0</td><td>24.0808</td></tr></table>

Because the algorithms was designed based on mobile computing, it could not only guarantee the accuracy but also provide high efficiency. Through many times of experiment contrasting, when the execution efficiency was less than 3s, the variation situation of the soil nutrients interpolation error in the algorithm was examined in 100 neighboring set. The comparing results as follows:

(1) The prediction error of Ph decreased gradually with the increase of the neighbor point firstly. The prediction error reach minimum when the number of the neighbor point increased to 85. The mean absolute error, average relative error and root-mean-square error was 0.0405, 0.064052 and 0.4360 respectively. Then, the error increased gradually again.

(2) The prediction error of organic material decreased gradually with the increase of the neighbor point firstly. The prediction error reach minimum when the number of the neighbor point increased to 15. The mean absolute error, average relative error and root-mean-square error was 0.3870, 0.1417 and 2.4147 respectively. Then, the error increased gradually again.

(3) The prediction error of rapid available phosphorus decreased gradually with the increase of the neighbor point.

(4) The prediction error of rapid available potassium decreased gradually with the increase of the neighbor point. The prediction error reach minimum when the number of the neighbor point increased to 65. The mean absolute error, average relative error and root-mean-square error was 0.0015, 0.1885 and 23.9818 respectively. Then, the error increased gradually again.

## 5 Conclusions

The K-D Tree was used as the space division algorithm for the soil nutrient sampling point in this study. The spatial index of the soil nutrient sampling point was also
established. On this basis, the K-nearest neighbor search of the soil nutrient sampling
point was realized using KNN algorithm. Furthermore, combined with KNN and IDW
algorithm, the soil nutrients spatial interpolation algorithm was implemented and
broke away from the limitation of GIS platform.

(1) The experiment showed that the soil nutrient spatial interpolation algorithm based on KNN and IDW was effective and feasible for predicting the content values of the Ph, organic matter, rapid available phosphorus and rapidly available potassium in soil.

(2) This paper tested the influence to different soil nutrient elements affected by the K value in KNN algorithm. The result showed that the neighboring points for the prediction of Ph, organic matter, rapid available phosphorus and rapid available potassium of respectively take 85, 15, maximal sample space, 65 could achieve the best accuracy. Of which, the optimal average absolute errors of Ph, organic matter, rapidly available potassium were 0.0405, 0.3870, and 0.0015 respectively.

(3) Through the analysis of the error size, it was found that the interpolation precision to pH and organic matter of the algorithm is higher than the interpolation precision of the rapid available phosphorus and rapid available potassium. The error of the rapid available phosphorus and rapid available potassium was larger. This was largely relevant with their large spatial variability[24].

Following the rapid development of the mobile intelligent terminal and the distributed computing technology, more and more applications transferred the computing and the data processing to thin client. The soil nutrient spatial interpolation algorithm based on KNN and IDW enabled the traditional soil testing and formulated fertilization recommended system to run on embedded devices such as high performance and low cost mobile intelligent terminal. The advantages of the mobile technology and the soil testing formula technology could thus fully integrate to achieve the positioning and query to the soil nutrient and recommended fertilization information of any plot for the users through the intelligent mobile platform in the fields. It had an important significance for the accurate utilizing of the soil testing and formulated fertilization technology and the resolving of the problem of “the last kilometer” for the scientific fertilization information promotion.

## Acknowledgment

Funds for this research was provided by the Henan Province Scientific and Technological Achievements Transformation Plan(132201110025), the National 12th Five-year Science and Technology Support Plan (2014BAD10B06), the Colleges and Universities in Henan Province Key Scientific Research Project (15A520019).
References

1. Wu Jing-san, Cheng Gui-cheng. The Existing Problems and Countermeasures of Unit Soil Samples Collecting in Soil Testing and Formulated Fertilization[J]. Modern Agricultural Science and Technology, 2010, (1):274.

2.Tong Yue, Zhang Xiao-xu, Wang Ce et al. The Existing Problems and Countermeasures in Soil Testing and Formulated Fertilization Project[J]. Modern Agricultural Science and Technology, 2014, (13):262.

3.Feng Donghai. The Existing Problems and Countermeasures in Soil Testing and Formulated Fertilization [J]. Modern Agricultural Science and Technology, 2011, (18):298-299.

4. Wang Yue, Yue Wei-ning, Wang Heng, et al. Multi-Modal Interaction in Handheld Mobile Computing. Journal of Software, 2005,16(1): 29-30.

5. Yu Yisheng, Hu Fenggen. Processing model of mobile data in disconnecting computing environments[J].Computer Engineering and Design, 2006,27(14):2686-2687.

6. Yu Tao, Yu Lizhong, Wang Zheng.The Development and Application of GIS under Mobile Computing Environment[J].Bulletin of Surveying and Mapping, 2002,(2):40-41.

7. Zhang Li, Tian Yin-lei. PDA-based mobile query system for testing soil for wheat formulated fertilization[J]. Journal of Henan Agricultural University, 2010, 44(3),341-342.

8. Zhang Guo-feng, HE Li-yuan, Han Song, et al. Research and Development of Recommended Fertilization System Based on Mobile GIS[J]. Journal of Huazhong Agricultural University, 2011,30(4):484-486.

9. Xu Xin, Zhang Hao, Xi Lei, et al. Decision-making System for Wheat Precision Fertilization Based on WebGIS [J]. Transactions of The Chinese Society of Agricultural Engineering, 2011, 27(14): 95-97.. (in Chinese with English abstract)

10. Jiang Hai-yan, Mao Jin-hui, Xu Xiao-ming. Support System for Wheat Production Management Based on Service-oriented Architecture and WebGIS[J]. Transactions of The Chinese Society of Agricultural Engineering, 2012,28(8):160-165.

11. Zhao Qing-song, Xu Tao, Jiang Hai-yan, et al. Cropping System Design Service System Based on SOA and WebGIS[J]. Computers and Applied Chemistry, 2014,31(6):757-759.
12. Zhu Qiuan, Zhang Wanchang, Yu Junhui. The Spatial Interpolations in GIS[J]. Journal of Jiangxi Normal University(Natural Science), 2004,28(2):184-186.

13. Wang Xiu, Miao Xiao-ke. Meng Zhi-jun et al.Effect on Soil Nutrition Interpolation Result of Different Interpolation Styles[J].Chinese Journal of Soil Science, 2005,36(6):827-829. 14. Zu Juan. Researched and Developed a Soil Testing and Formulated Fertilization Application System Based on PDA-GIS[D]. Anhui Agricultural University,2012.

15. Xu Li-Hua. Comparisons among different Prediction Method on the Soil Nutrient-Taking Wangjiagou small Watershed of Three Gorges Reservoir Area as Researching Zone. Southwest University,2012.

16. Li Zeng-bing, Zhao Geng-xing, Zhao Qian-qian.Comparison of Spatial Interpolation Methods for Soil Nutrients in Cultivated Land Fertility Evaluation[J].Chinese Agricultural Science Bulletin,2012,28(20):231-236.

17. Jin Guo-dong, Liu Yan-cong, Niu Wen-jie.Comparison between Inverse Distance Weighting Method and Kriging[J].Journal of Changchun University of Technology, 2003,24(3):54-56.

18. Chen Guang, He Li-yuan, Zhan Xiang-wen. Comparison of Spatial Interpolation Technique of Soil Nutrient and Reasonable Sampling Density [J]. Chinese Journal of Soil Science, 2008, 39(5): 1008-1011.

19. Dung Minl.Study on Soil Property with GA-RBF-Neural-Network-Based Spatial Interpolation Method [D]. Sichuan Agricultural University, 2009.

20. Cover T M, Hart P E. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967, 13(1):21-27.
21. Zhang Zebao. Research of Spatial Indexes Optimization and Implementation[D]. Harbin Engineering University, 2005.

22. Yan Chaode, Zhao Xuesheng. The Review of Spatial Indexes in GIS[J]. Geograph and Geo - Information Science, 2004,20(4):23-26.

23. Shi Xiao-hua, Yang lian-an, Zang Lei. Comparison of Spatial Interpolation Methods for Soil Availability of Kalium[J]. Journal of Soil and Water Conservation, 20(2):70.

24. Wang Ke, Shen Zhangquan, John S. Bailey, et al. Spatial Variants and Sampling Strategies of Soil Properties for Precision Agriculture[J]. Transactions of The Chinese Society of Agricultural Engineering, 2001, (2):34-35.