# A Spatial-Temporal-Semantic Neural Network Algorithm for Location Prediction on Moving Objects
## 4 Experiments
### Experimental Preparation
#### 4.1.3 Selection of Compared Algorithms  
Feature extraction methods. Partitioning trajectories into self-defined cells or grids is commonly used [8; 17; 18; 21]. However, cell-based methods are easily affected by the granularity of the grid and it is difficult to draw a grid in the global area. Geohash is a geocoding system invented by [PERSON] [32]. It is a hierarchical spatial data structure that subdivides space into buckets of grid shape and is used as indexing algorithm by many geospatial databases, such as Elasticsearch and MongoDB. For example, a part of trajectory ((\(-25.383\), \(-49.266\)), (\(-25.427\), \(-49.315\))) can be transferred to (\(6\)gkzwgjz, \(6\)gkzmg1w) by Geohash. Similar to cell-based methods, Geohash extracts the geographic feature of trajectory but may suffer from granularity problems. Prediction Models. After feature selection, the location sequences are put into different models. Among all of the models described in Table 1, supervised learning models are suitable to fit the location sequences generated by the feature extraction method. The current locations are set to be features and the next location is the label. The location prediction can be regarded as classification problem. The hidden Markov model (HMM) is widely used in location prediction [16; 17; 18] and gain better prediction results. Moreover, XGBoost [33] is a popular classification and regression model. In many machine learning problems and data science challenges, XGBoost always surpasses other traditional classification models. Recently, the recurrent neural network (RNN) has been employed for mining location sequences [23] and provided a promising future. Therefore, HMM, XGBoost, and RNN are used to compare the proposed method. Brief introductions of HMM and XGBoost are provided below. Details of RNN has been introduced in Section 3.2.1. The HMM assumes the sequences are generated by a Markov process with unobserved states [34]. Each state has a probability distribution over the possible locations to be visited. It also has a probability distribution over the possible transitions of the states that will be predicted. The probability distribution of the hidden variable at time \(t\) depends only on the value of the hidden variable at time \(t-1\) \begin{table}
\begin{tabular}{c c c} \hline \hline \multirow{2}{*}{**True Condition**} & \multicolumn{2}{c}{**Predicted Condition**} \\ \cline{2-3}  & **Positive** & **Negative** \\ \hline Positive & True Positives (TP) & True Negatives (FN) \\ Negative & False Positives (FP) & False Negatives (TN) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Four categories of classification problems. This is called the Markov property. The prediction task is to compute the probability of a particular output sequence being observed. The probability of observing a particular sequence in the form \(Y=~{}<y(1),~{}y(2),~{}\ldots,y(L)>\), where \(y(t)\) is the location visited at time \(t\), is given by  
\[P(Y)=\sum_{X}P(Y|X)P(X). \tag{17}\]  
In Equation (17), the sum runs over all possible hidden-node sequences \(X=~{}<x(1),~{}x(2),~{}\ldots,x(L)>\), where \(x(t)\) is the hidden state at time \(t\). This problem can be solved by the Baum-Welch algorithm. For more information about the derivation of the parameters in HMM, please refer to the tutorial by [PERSON] [34]. XGBoost [33] is an ensemble model based on a gradient boosting decision tree (GBDT) [35] and is designed to be highly efficient, flexible, and portable. XGBoost is used for supervised learning problems, where training data with multiple features \(x_{i}\) (current location sequence) are used to predict a target variable \(y_{i}\) (the next location). For tree ensemble learning, the model is defined as Equation (18), where \(K\) is the number of trees, \(f\) is a function in the functional space \(F\), and \(F\) is the set of all possible CARTs.