# Improving a Street-Based Geocoding Algorithm Using Machine Learning Techniques
## 3 Geocoding Algorithm Using Machine Learning Techniques
### Address Matching Using Machine Learning  
The parsed city, district, and road names undergo the address matching using machine learning, resulting in a set of road segments through the matching process. The address matching process helps to select a set of road segments to be sent to the address locating process. The city, district, and road names are matched one or two times in the matching process to find the records in the Alias DB for geocoding correctly (Algorithm 2 and in the middle of Figure 2). ```
1:Input: City, District, Road, Traindata
2:Output: MatchedName
3:Algorithm
4: Initialize the parameters of the \(S=0\), SearchName, Result, SearchResult, Test, OfficialName, and
5:Probs
6:MLT = MachineLearningTrain(Traindata)
7:while (\(S<2\))
8:if\(S=0\)
9:SearchName = City, District, or Road
10:elseif\(S=1\)
11:SearchName = input(\"Input city, dictrict, or road name once again\")
12:Result = MatchOfficialName(SearchName)
13:if length(Result) > 0
14:SearchResult = Result
15:\(S=2\)
16:else
17:for\(i=0\) to number of official names
18:Test[\(i\)] = GenerateSimMetrics(SearchName, OfficialName[\(i\)])
19:\(\mathit{Probs}[i]\) = MLT.PredictProbability(Test[\(i\)])
20:if there is a matched official name having the highest probability in \(\mathit{Probs}\)
21:SearchResult = the matched official name
22:else
23:SearchResult =\"
24:if the matched result is correct
25:\(S=2\)
26:else
27:\(S=1\)
28:endwhile
```  
**Algorithm 2** Address matching process  
In the first matching, the city, district, and road names undergo simple matching with their official names. If there is no identical official name found for the city, district, or road name, the second matching is subsequently involved using machine learning to supplement the first simple matching. Before matching using machine learning, we generate training data from the Alias DB, and select the best machine learning model through the evaluation of 17 text similarity metrics (Table 1) and three machine learning models. Each record of Alias DB has an official name and the aliases, while the training data consist of matching pairs and non-matching pairs. The matching pairs refer to the pairs of one official name and one alias of the official name. On the other hand, the non-matching pairs ae defined by the aliases and other unmatched official names in the Alias DB. In this study, we tested different combinations of matching and non-matching pairs for the training data since the accuracy of matching results may vary depending on the ratio of matching and non-matching pairs consisting of training data. For matching and non-matching pairs, we used variables calculated using 17 text similarity metrics to train machine learning models. Previous studies have widely used similarity metrics for word matching [16; 18; 33; 34]. This methodology uses edit-based and token-based similarity metrics. Edit-based similarity is more applicable for short phrases and compares only the characters. Hence, it is simple, yet it is inefficient for long phrases and computationally expensive. On the other hand, token-based similarity explores text as a set of tokens (words) and is more applicable for long texts. Three different kinds of machine learning methods--support vector machine (SVM), random forest (RF), extreme gradient boosting (XGB)--were tested to find the best method. SVM is a supervised machine learning method. The goal of SVM is to find a hyperplane in an N-dimensional space that best separates data points. A hyperplane that has the maximum margin between data points is selected as the best decision boundary to classify the data points. Given some training data D:  
\[\text{D}=\left\{(x_{i},y_{i})\Big{|}x_{i}\in R^{m},\ y_{i}\in\{-1,1\}\right\}_{i= 1}^{n} \tag{1}\]  
where \(x_{i}\) is an m-dimensional real vector, \(y_{i}\) is either 1 or \(-1\), indicating the class of input vector \(x_{i}\). Two parallel hyperplanes (Figure 3) are defined such that \(w^{T}x+b=1\) and \(w^{T}x+b=-1\). Maximizing the distance between these two hyperplanes defines the maximum-margin hyperplane.