BaseMatcher
This a generic base class to be used by matchers. This class itself
does not implement a working matcher. Use a matcher such as
SimpleMatcher
, DistanceMatcher
, …
- class leuvenmapmatching.matcher.base.BaseMatcher(map_con, obs_noise=1, max_dist_init=None, max_dist=None, min_prob_norm=None, non_emitting_states=True, max_lattice_width=None, only_edges=True, obs_noise_ne=None, matching=<class 'leuvenmapmatching.matcher.base.BaseMatching'>, non_emitting_length_factor=0.75, **kwargs)[source]
Initialize a matcher for map matching.
This a generic base class to be used by matchers. This class itself does not implement a working matcher.
Distances are in meters when using latitude-longitude.
- Parameters:
map_con – Map object to connect to map database
obs_noise – Standard deviation of noise
obs_noise_ne – Standard deviation of noise for non-emitting states (is set to obs_noise if not give)
max_dist_init – Maximum distance from start location (if not given, uses max_dist)
max_dist – Maximum distance from path (this is a hard cut, min_prob_norm should be better)
min_prob_norm – Minimum normalized probability of observations (ema)
non_emitting_states – Allow non-emitting states. A non-emitting state is a state that is not associated with an observation. Here we assume it can be associated with a location in between two observations to allow for pruning. It is advised to set min_prob_norm and/or max_dist to avoid visiting all possible nodes in the graph.
max_lattice_width – Only continue from a limited number of states (thus locations) for a given observation. This possibly speeds up the matching by a lot. If there are more possible next states, the states with the best likelihood so far are selected. The other states are ‘delayed’. If the matching is continued later with a larger value using increase_max_lattice_width, the algorithms continuous from these delayed states.
only_edges – Do not include nodes as states, only edges. This is the typical setting for HMM methods.
matching – Matching type
non_emitting_length_factor – Reduce the probability of a sequence of non-emitting states the longer it is. This can be used to prefer shorter paths. This is separate from the transition probabilities because transition probabilities are averaged for non-emitting states and thus the length is also averaged out.
To define a custom transition and/or emission probability distribtion, overwrite the following functions:
- best_last_matches(k=1, nb_obs=3)[source]
Return the k best last matches.
- Parameters:
k – Number of best matches to keep for an observation
nb_obs – How many last matched observations to consider
- continue_with_distance(from_matches=None, k=2, nb_obs=2, max_dist=None)[source]
Continue the matcher but ignore edges and allow jumps to nearby edged.
- Parameters:
from_matches – Search in the neigborhood of these matches
k – If from_matches is not given, the k best matches are used in the last nb_obs observations since last early_stop_idx
max_dist – Add edges that are maximally max_dist away from the previous match. If none, self.max_dist * 3 is used.
- Praram nb_obs:
If from_matches is not given, the k best matches are used in the last nb_obs observations since last early_stop_idx
- copy_lastinterface(nb_interfaces=1)[source]
Copy the current matcher and keep the last interface as the start point.
This method allows you to perform incremental matching without keeping the entire lattice in memory.
You need to run
match_incremental()
on this object to continue from the existing (partial) lattice. Otherwise, if you usematch()
, it will be overwritten.Open question, if there is no need to keep track of older lattices, it will probably be more efficient to clear the older parts of the interface instead of copying the newer parts.
- Parameters:
nb_interfaces – Nb of interfaces (columns in lattice) to keep. Default is 1, the last one.
- Returns:
new Matcher object
- get_node_path(start_m, only_nodes=False)[source]
List of node/edge names that end in the given Matching object.
- get_path(only_nodes=True, allow_jumps=False, only_closest=True)[source]
A list with all the nodes (no edges) the matched path passes through.
- inspect_early_stopping()[source]
Analyze the lattice and try to find most plausible reason why the matching stopped early and print to stdout.
- lattice_dot(file=None, precision=None, render=False)[source]
Write the lattice as a Graphviz DOT file.
- Parameters:
file – File object to print to. Prints to stdout if None.
precision – Precision of (log) probabilities.
render – Try to render the generated Graphviz file.
- logprob_obs(dist, prev_m, new_edge_m, new_edge_o, is_ne=False)[source]
Emission probability.
- Note: In contrast with a regular HMM, this cannot be a probability density function, it needs
to be a proper probability (thus values between 0.0 and 1.0).
- Returns:
probability, properties that are passed to the matching object
- logprob_trans(prev_m: BaseMatcher, edge_m: BaseMatching, edge_o: Segment, is_prev_ne: Segment = False, is_next_ne: bool = False) Tuple[float, Dict[str, Any]] [source]
Transition probability.
- Note: In contrast with a regular HMM, this cannot be a probability density function, it needs
to be a proper probability (thus values between 0.0 and 1.0).
- Returns:
probability, properties that are passed to the matching object
- match(path, unique=False, tqdm=None, expand=False)[source]
Dynamic Programming based (HMM-like) map matcher.
If the matcher fails to match the entire path, the last matched index is returned. This index can be used to run the matcher again from that observation onwards.
- Parameters:
path – list[Union[tuple[lat, lon], tuple[lat, lon, time]]
unique – Only retain unique nodes in the sequence (avoid repetitions)
tqdm – Use a tqdm progress reporter (default is None)
expand – Expand the current lattice (delayed matches)
- Returns:
Tuple of (List of BaseMatching, index of last observation that was matched)
- node_path_to_only_nodes(path, allow_jumps=False)[source]
Path of nodes and edges to only nodes.
- Parameters:
path – List of node names or edges as (node name, node name)
allow_jumps – Allow a path over edges that are not connected. This occurs when matches are added without an edge, for example, when searching for edges in the distance neighborhood instead in the graph.
- Returns:
List of node names
- path_all_distances()[source]
Return a list of all distances between observed trace and map.
One entry for each point in the map and point in the trace that are mapped to each other. In case non-emitting nodes are used, extra entries can be present where a point in the trace or a point in the map is mapped to a segment.
- property path_pred
The matched path, both nodes and/or edges (depending on your settings).
- property path_pred_onlynodes
A list with all the nodes (no edges) the matched path passes through.
- property path_pred_onlynodes_withjumps
A list with all the nodes (no edges) the matched path passes through.