# Improving a Street-Based Geocoding Algorithm Using Machine Learning Techniques
## 3 Geocoding Algorithm Using Machine Learning Techniques
### Address Matching Using Machine Learning
RF is also a supervised machine learning method and built upon decision trees on data points (Figure 4). It makes predictions from each of the trees with different features and selects the best solution with majority voting. By majority voting, RF can reduce the over-fitting. XGB, as a supervised machine learning method, is an implementation of gradient boosted decision trees for more efficient computation and the increase of performance. In the gradient boosted trees, each tree in boosting is a weak learner and tries to minimize the errors of the previous tree to make a strong learner. \begin{table}
\begin{tabular}{c c} \hline \hline
**Edit-Based Similarity Metric** & **Token-Based Similarity Metric** \\ \hline [PERSON] [35] & [PERSON] [36] \\ [PERSON] [37] & [PERSON] [38] \\ [PERSON] Reversed [29] & [PERSON] [34] \\ Jaro-Winkler Sorted [28] & [PERSON] [39] \\ [PERSON] [40] & [PERSON] [41] \\ [PERSON] [42] & [PERSON]\_[PERSON] [43] \\ [PERSON] [37] & [PERSON]\_[PERSON] [33] \\ [PERSON] [44] & \\ [PERSON] [45] & \\ [PERSON]\_[PERSON] [46] & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Seventeene kinds of similarity metrics. Figure 3: Support vector machine algorithm. We performed a 10-fold cross-validation to evaluate the performance of the matching process. This method splits the entire data set into 10 sets with equal size, and selects one single set as a test set. Remaining sets become training sets, and the cross-validation is repeated 10 times by using each test set only once. The performance of three machine learning models was compared with each similarity metric to see whether the machine learning models outperform conventional methods. To understand the minimum number of similarity metrics needed and choose the best model, we tested different numbers of similarity metrics. To do this, first, different similarity metrics were arranged in descending order by their accuracy and grouped into 2-17 based on the order. Second, the least number of similarity metrics showing higher accuracy of machine learning models than all the 17 similarity metrics was determined (Figure 10). Last, we chose the best model with the minimum number of similarity metrics that shows the highest accuracy among the three machine learning models. We measured accuracy for each similarity metric and the three different machine learning models. Especially, for each similarity metric, a threshold value needs to be set, determining whether a given pair of texts matches or not. Therefore, to find the optimal threshold, different thresholds need to be tested (Algorithm 3). This methodology tests different threshold values ranging from 0.00 to 1.00 by the increment 0.05 for each similarity metric and sets the optimal threshold that has the highest accuracy. ```
1:Input:_Trainedata, Threshold_
2:Output:_OptimalThreshold_
3:Algorithm
4: Initialize the parameters of the Predicted, Label, Acc, Alpha, and OptimalThreshold
5:for\(j=0\) to number of similarity metrics
6:for\(k=0\) to length(Threshold)
7:for\(i=0\) to length(Traindata)
8:if\(Taindata[i][j]>=Threshold[k]\)
9:\(Predicted[i]=1\)
10:else
11:\(Predicted[i]=0\)
12:\(Acc[k]=\) AccuracyScore(Label, Predict)
13:\(Alpha[k]=\)\(Threshold[k]\)
14:\(MaxIndex=\)\(\mathrm{Argmax}(Acc)\)
15:\(OptimalThreshold[j]=\)\(\mathrm{Alpha}[MaxIndex]\)
```  
**Algorithm 3** Choosing optimal thresholds for similarity metrics  
Figure 4: Random forest algorithm. When the first and second matching do not find a matched official name, the city, district, or road name is input manually and then the matching is undertaken once again. A set of road segments results from the end of the address matching process. As a result of the matching, candidates of road segments are selected and sent to the locating process with the parsed building number. The combination of road segments and the building number can help to narrow down to a final road segment necessary in locating.