# Data Quality Analysis and Improvement: A Case Study of a Bus Transportation System
## 4 Data-Cleaning Methods
### Cleaning Method for Noisy Data  
In GPS trajectory data, anomalous data are referred to as outliers or noisy points. These data usually present scattered, irregular characteristics and are difficult to detect in large volumes of trajectory data. Noise data may place a significant negative impact on trajectory data mining applications. To improve the accuracy of data analysis, these anomalous points in GPS trajectory data need to be cleaned. Generally, GPS anomalous points can be classified into the following two categories:  
1. Range anomalies: The longitude or latitude of a GPS point outside the specified range, i.e., longitude range between 0 and 180\({}^{\circ}\) and latitude range between 0 and 90\({}^{\circ}\). Note that these GPS points outside this area are also considered as anomalous outliers. 2. Jump anomalies: Both the longitude and latitude of a GPS point are within the normal range, but there is an extreme distance between a given point and its consecutive points. It means that the GPS point deviates significantly from the original trajectory, resulting in \"Jump points\" in the trajectory. To solve the above problem, this paper proposes a solution, which combines the heuristic-based GPS anomaly filtering and Fast Map Matching (FMM) [40] framework for correcting anomalous points in GPS trajectories. Key steps are as follows: Firstly, it applies a heuristic-based GPS anomaly filtering algorithm to the raw GPS trajectory dataset to remove all range anomalies and the obvious jump anomalies. Then, it takes the filtered dataset as input for the FMM algorithm, which incorporates Hidden Markov Models and pre-computation, to correct jump anomalies. This solution not only effectively removes the noises from the raw GPS trajectory dataset but also further improves GPS positioning accuracy. In the first step, Algorithm 1 is performed to conduct heuristic GPS anomaly filtering. The core idea of this algorithm is to calculate the distance and time difference between two adjacent points, to calculate the instantaneous speed of a bus, and to determine whether it is an anomalous point by a pre-defined speed threshold. During the detection process, we keep and store these weights of the anomalous points. Finally, the anomalies with high weight values are removed from the raw GPS trajectory dataset and the filtered GPS dataset is returned. In the second step, the FMM (as Algorithm 2 described) matches each trajectory of the filtered GPS dataset to the road network. The FMM algorithm takes a GPS trajectory and the road network as inputs, and outputs a matched GPS trajectory. In detail, it consists of two stages: precomputation and map matching. In the initial stage, the framework precomputes all pairs of shortest paths in the road network below a certain threshold and substitutes these repetitive queries in map matching using a hash table. This hash table is called an Upper Bound Origin Destination Table (UBODT). In the second stage, the framework integrates the Hidden Markov Model (HMM) with precomputation to deduce vehicle paths, taking into account GPS positioning errors and topological constraints. This stage consists of four sub-steps: candidate search (CS), optimal path inference (OPI), complete path construction (CPC), and geometric construction (GC). ```
Input: The original GPS trajectory: rawTR; The road network: network < V, E >; An upper bound origin destination table: ubodt. Output: A matched path: matchedPath. 1 HashMap < point_segment> psegKV = null/* save point and candidate segment */
2 RTree rtree = buildRTree(network)
3 for i = 0; i < rawTR.len; i ++ do
4 Point = rawTR[i]
5 proPoint = getProjectPoint(Point,rtree)
6 canSegments = getCandidateSegments(proPoint,rtree)
7 psegKV.put(proPoint,canSegments)
8 endfor
9 transitGraph = constructTransitGraph(rawTR,psegKV,rtree)
10 optimalPath = pathInference(transitGraph,ubodt)
11 return optimalPath
```  
**Algorithm 2** The fast map matching algorithm. The CS step searches the corresponding candidate edges for each point in the trajectory.