— added later todo

The classifier is trained on the training set \(\Tset\):¹¹The features enter the trees after light preprocessing: categorical features (highway type, surface, \ldots) are turned into integers by an ordinal encoder, with missing values represented by an explicit missing category; numeric features are passed unchanged. the edges labelled 0 for lying on a good path, and 1 for being bad. In the training process, we must be careful about class imbalance. In the full map the great majority of edges count as bad under our rules, whereas the curated good edges are comparatively rare, on the order of a few percent. A classifier trained on a set with these proportions could reach a high accuracy by the trivial strategy of calling almost every edge bad. To prevent this, we do not train on the full map but on a sample with a much milder imbalance: three bad edges for every good one.

— end added later

In the earlier sections we discussed random forests and probability calibration as techniques to assign a cost to edges. These costs can then be used to make routes. Here we give the details of the pipeline we set up to compute pleasant walking routes.

Obtaining the edge features is the first step. We download the road network for the Netherlands from OpenStreetMap, as packaged by Geofabrik, and import the relevant data into a PostgreSQL database.

PostgreSQL is used for the heavy geospatial preprocessing stage. The tool osm2pgsql imports OSM into PostgreSQL tables, and the PostGIS extension for PostgreSQL offers functionality to deal with geographic information. It can happen that a few edges are not reachable, we therefore keep the largest component of the road graph.

After this preprocessing step we export the graph to SQLite. SQLite is a simple file database, but fast enough for our goals. We store edge features, scores and costs in this database.

Each OSM way becomes one or more directed edges in a graph \((\Nset, \Eset)\). An edge \(e \in \Eset\) connects two nodes and carries its geometry and OSM tag metadata.

Each edge has an id and is described by a feature vector \(f(e)\). The features used by the Wandelvogel code are as follows.

The categorical OSM tags are open-ended: the model uses the raw value present in the map data, and rare spelling mistakes or unusual tag values are simply treated as additional categories. Missing tags are also represented as a separate category. 1 therefore gives representative values, not a full data dump.

To train a classifier we use a set of published walking tracks, such as the Pieterpad and the Drenthepad: every edge that appears in one of those tracks receives label \(0\).

Edges that were not marked good are then labeled bad by a few simple rules:

• edges in industrial, commercial, or residential landuse zones,
• cycleways (which are often shared with pedestrians) within 50 m of a primary, secondary, or tertiary road,
• edges longer than 200 meters, since people dislike long stretches with the same features.

Finally, any edge that is tagged as a primary, secondary, or tertiary road is relabelled bad, even when it appears in one of the curated tracks.

Training the random forest is the second conceptual step. We use an ordinal encoder for categorical features. For a linear model this would be wrong; in that case we should use one-hot encoding to avoid saying that surface \(5\) is 5 times ``larger’’ than code \(1\) in the sense in which 50 m is larger than 10 m. For trees, however, one-hot encoding is not needed and can even be harmful. It makes the feature vector much wider and sparser, and it spreads one informative feature, such as highway type, over many separate columns. A tree may need several splits to recover a simple rule about a group of highway types. Worse yet, in a random forest the feature subset that is chosen randomly at a split will typically not contain all the columns that one-hot encoding uses for one feature. Thus, for random forests it is best to use ordinal encoding for categorical features. Missing categorical values are represented by an explicit category unknown. Binary features are stored as \(0/1\) indicators, so that a tree can separate the two cases with the split \(x \leq 0.5\). Finally, numeric features are passed as numbers. As numerical values are never missing, we don’t have to replace data by a special value.

To train the random forest, we sample 150 000 bad and 50 000 good edges from the graph of the entire Netherlands. As the good edges form 25% of this training sample, the simple strategy of scoring all edges as bad will not work well. We train 300 trees with a minimum leaf size of \(5\). These values appear to be sensible, but we chose them somewhat intuitively. If we had a good loss function, we could tune these hyperparameters. However, at present we do not have a representative loss function.

With isotonic regression we compute the calibration function \(g\) that converts the raw random-forest score \(u(e)\) into a calibrated bad-edge probability \(g(u(e))\). The calibration set \(\Hset\) is a stratified 20% hold-out from the labeled sample, in the sense of Chapter 3, and is not used to fit the forest. Thus, with the sample sizes above, the forest is fitted on 160 000 edges and calibration uses 40 000 edges, with the same good/bad proportions in both parts. The split is shuffled and uses a fixed random seed, so the example is reproducible.

For routing, we use the calibrated bad-edge probability as the model cost: \[ c_{\mathrm{model}}(e)=g(u(e)). \] Later hand-written penalties modify this model cost. For instance, if \(c_{\mathrm{model}}(e_1)=0.2\) and \(c_{\mathrm{model}}(e_2)=0.3\), and both edges are 200 m long, the cost difference corresponds to a willingness to walk \((0.3-0.2)\cdot 200=20\) m extra to enjoy the features of edge \(e_1\). But this extra distance may not reflect sufficiently strongly the difference we experience between the two edges. The multiplier \(\lambda\) scales this willingness to \(\lambda \cdot 20\) m; with \(\lambda = 5\), one of the values we use below, this becomes \(100\) m.

Edge-level losses such as the Brier score can tell us whether the classifier probabilities are calibrated, but they do not by themselves tell us whether the routes produced from those probabilities are pleasant. The harder tuning problem is therefore at route-level: ideally we would have an objective that captures the tradeoff between distance, scenery, and avoidance of busy roads. The problem is that this is somewhat arbitrary and, worse, hard to quantify.²²A similar problem occurs when debating whether a table is beautiful or not. Because of this, we did not use cross validation or other tools to obtain the most reliable edge score or calibration function: edge quality is just a proxy for total route quality, and we should not give edge quality an overly important interpretation. As a consequence, after training the random forest, we froze it,³³Freezing means that scikit-learn does not clone and refit forests as part of its internal calibration procedure. The forest remains fixed, and only isotonic regression fits a calibration function. and then applied a simple calibration step. Moreover, since we have already chosen the calibration set \(\Hset\), we do not create new cross-validation folds, but calibrate the frozen forest directly on \(\Hset\).

The routing environment uses the edge cost for the computation of the cheapest route from \(A\) to \(B\). Open Source Routing Machine (OSRM) is the engine of choice as it computes country-sized routes in a few milliseconds and scales to graphs with hundreds of millions of edges.

The random forest writes calibrated costs to rf_cost, while another model, such as gradient boosting, can write costs to a different column in the database such as gb_cost. Call this the model cost \(c_{\mathrm{model}}(e)\). We still need to apply a few hand-written adjustments to this cost.

MTB route classes impose a minimum cost \(c_{\mathrm{mtb}}(e)\).⁴⁴Mountain bike trails are mostly unsuitable for normal walking even though their OSM tags make them attractive. An edge gets MTB class \(0\) if it is not part of an MTB route. If it is part of a relation tagged type=route and route=mtb, it receives class \(1\), unless the tags suggest a stronger restriction. Edges with bicycle=designated and no explicit foot permission get class \(2\), and edges with foot=no get class \(3\). These classes impose minimum costs \(0\), \(0.2\), \(0.4\), and \(1.0\), respectively.

The road penalty \(c_\text{road}(e)\) is another hand-written correction. If an edge \(e\) is a tunnel or bridge, we set the penalty to zero, because such edges often cannot be avoided. Further, proximity to a motorway or trunk road adds a linear penalty within 200 m: the penalty is \(0.01\) times the remaining distance to that 200 m radius. In addition, being within 30 m of a primary or secondary road adds a penalty \(2\).

The final edge cost is

As a last remark, OSRM finds the path that minimizes total travel time, not total cost. We therefore convert the edge cost into a speed:

where \(s_0 = 6\) km/h is a base speed and \(\lambda\) is a weight. We use \(\lambda \in \{0, 5, 20\}\): \(\lambda=0\) results in the shortest route, \(\lambda=20\) offers the most scenic (perhaps) by avoiding bad edges most aggressively.

We visualize the route by means of website called De wandelvogel. The implementation is simple: a Python HTTP server based on the standard-library http.server module serves a single Leaflet page. In the browser, the user chooses a start point and an end point on the map, after which OSRM snaps the input points to the road network and returns the cheapest path to the Python server. The server sends the route back to the browser, and the browser uses Leaflet to draw the route on the map.

The server uses Nominatim to turn the coordinates of the selected points into a place or road label. The route statistics are computed in a second step by looking up the edge properties in the SQLite database.