Sergey Rodionov

Alexey Potapov

Hugo Latapie
email: hlatapie@cisco.com

Enzo Fenoglio
email: efenogli@cisco.com

Maxim Peterson
email: maxim.peterson@gmail.com

Improving Deep Models of Person Re-identification for Cross-Dataset Usage

Keywords: person re-id, deep learning, metric embedding, triplet loss, crossdataset evaluation

Person re-identification (Re-ID) is the task of matching humans across cameras with non-overlapping views that has important applications in visual surveillance. Like other computer vision tasks, this task has gained much with the utilization of deep learning methods. However, existing solutions based on deep learning are usually trained and tested on samples taken from same datasets, while in practice one need to deploy Re-ID systems for new sets of cameras for which labeled data is unavailable. Here, we mitigate this problem for one state-of-the-art model, namely, metric embedding trained with the use of the triplet loss function, although our results can be extended to other models. The contribution of our work consists in developing a method of training the model on multiple datasets, and a method for its online practically unsupervised fine-tuning. These methods yield up to 19.1% improvement in Rank-1 score in the cross-dataset evaluation.

Introduction

Person tracking is one of the most typical tasks in visual surveillance. A great deal of methods for tracking within one camera has been developed. However, it is usually necessary to track a person using multiple cameras with non-overlapping fields of view. Here, traditional tracking techniques cannot be used, and the task of person reidentification (Re-ID) should be stated. This task is challenging because of high variations in background, illumination, viewpoint, human poses, etc., and absence of tight space-time constraints on candidate IDs like in tracking. Although some constraints do exist, and they should be used in a practical system.

Many attempts to solve this task exist [START_REF] Bedagkar-Gala | A survey of approaches and trends in person reidentification[END_REF], but it is far from being completely solved yet. Currently, deep convolutional neural networks (CNNs) are replacing traditional hand-crafted methods [START_REF] Zheng | Person Re-identification: Past, Present and Future[END_REF] that became possible due to both the progress in deep learning and the availability of larger public datasets like Market-1501 [START_REF] Zheng | Scalable person reidentification: A benchmark[END_REF] and MARS [START_REF] Zheng | MARS: A video benchmark for large-scale person re-identification[END_REF], CUHK03 [START_REF] Li | DeepreID: Deep filter pairing neural network for person re-identification[END_REF], DukeMTMC-reID [START_REF] Zheng | Unlabeled samples generated by GAN improve the person re-identification baseline in vitro[END_REF], and others. Different deep learning models have been developed to solve the person Re-ID task including classification CNNs used for feature learning as in [START_REF] Fan | Unsupervised Person Re-identification: Clustering and Finetuning[END_REF], Siamese CNNs that use image pairs [START_REF] Varior | Gated Siamese Convolutional Neural Network Architecture for Human Re-Identification[END_REF], metric embedding CNNs trained with the triplet loss [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF].

However, most of the existing deep learning models for Re-ID that show state-ofthe-art results on different benchmarks are trained and tested on each of these benchmarks separately (e.g. [START_REF] Varior | Gated Siamese Convolutional Neural Network Architecture for Human Re-Identification[END_REF][START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF]). At the same time, in practice, it is usually necessary to deploy a person Re-ID system to a new camera set, for which a large labeled training set is expensive or impossible to acquire, so pre-trained models should be used. Unfortunately, as it is shown in [START_REF] Fan | Unsupervised Person Re-identification: Clustering and Finetuning[END_REF], if a model is trained on one dataset and tested on another dataset, its performance drops significantly (seemingly below the level of hand-crafted features), because changes between datasets are rather large (see Figure 1 [START_REF] Li | DeepreID: Deep filter pairing neural network for person re-identification[END_REF], Duke [START_REF] Zheng | Unlabeled samples generated by GAN improve the person re-identification baseline in vitro[END_REF], Viper [START_REF] Gray | Viewpoint Invariant Pedestrian Recognition with an Ensemble of Localized Features[END_REF], WARD [START_REF] Martinel | Re-identify people in wide area camera network[END_REF] Few works address the problem of unsupervised fine-tuning of pre-trained models on new datasets, and even less of them report improvements achieved by unsupervised fine-tuning in comparison with corresponding pre-trained models, not just the final performance that depends both on the base model and unsupervised finetuning algorithm. One such recent work is [START_REF] Fan | Unsupervised Person Re-identification: Clustering and Finetuning[END_REF], in which improvements in Rank-1 accuracy from 1.2% for the model trained on Duke and tested on CUHK03 to 11.9% for the model trained on CUHK03 and tested on Market-1501 are reported. While this can be useful in practice, the achieved accuracy is still far below supervised learning results. Also, the Progressive Unsupervised Learning (PUL) algorithm proposed in [START_REF] Fan | Unsupervised Person Re-identification: Clustering and Finetuning[END_REF] assumes the known number of IDs in new dataset, which is usually unknown in practice. So, further progress in this task is needed.

In our work, we use one of the state-of-the-art models, namely, metric embedding network trained with the use of the triplet loss function [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF] as the base model. The contribution of our paper is two-fold:

1) We develop the novel method to train the metric embedding network using the triplet loss function on multiple datasets resulting in the increased invariance (and corresponding cross-dataset scores) of the embedding w.r.t. cameras. 2) We develop a novel fine-tuning method for the person re-id task, which relies on easily accessible information to collect negative samples, so we call it practically unsupervised. It yields up to 10% improvement in Rank-1 score.

Metric Embedding Learning for Person Re-ID

Loss Function

In the task of person Re-ID, it is usually assumed that bounding boxes (BBs) around humans are already extracted. These BBs are usually resized to a certain fixed size. Each resized BB yields a pattern (image) in an initial space of raw features (color values in resized BBs) xR F . BBs containing certain IDs can also be tracked within each camera forming the socalled tracklets, and in practice it is better to compare not separate BBs, but tracklets. But since it is usually enough to simply average over features calculated for BBs in a tracklet, and compare these averaged features, usage of tracklets doesn't influence on the rest functionality of a Re-ID system.

Each image x corresponds to a certain ID y, and the task is to identify which images from different cameras have same IDs. These IDs can be considered as classes, but it should be noted that the number of such classes is large and unknown while the number of images in each class is small. Thus, it is inefficient to cast the Re-ID task as the traditional pattern recognition problem.

One way to solve the task is to train a model (e.g. a Siamese Network) that accepts two images as input and infers if they correspond to same ID or not. The problem with this approach is that it requires running the model for one query image with each gallery image that is computationally expensive, especially in the case of deep neural networks.

Another possibility is to train a classification model (e.g. based on CNNs) for a fixed set of IDs known for a training set, and then to cut off the classification layer and compare images using high-level convolutional features, which were useful for classification. Similarity between images can be calculated directly as distance between these latent features, and the performance of such approach is acceptable in practice. However, images with the same ID will not be necessarily closer to each other than images with different IDs in the space of features useful for classification. Thus, additional step of metric learning is added to improve the overall performance.

In fact, what we want to learn is a metric embedding, i.e. a mapping f (x|):R N R M that transforms semantically similar images onto metrically close points in R M (and semantically dissimilar images onto metrically distant points). That is, D i,j =D(f (x i |), f (x j |)) is small if y i =y j and large otherwise, where D is some distance measure (e.g. Euclidean). One can try to learn this mapping directly without learning surrogate classification model, if an appropriate loss function is specified.

The following triplet loss function can be used [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF] 

      n p a y y y n p a n a p a tri D D m L , , , , ] [ ) (θ , ( 1
)
where m is some margin by which positive and negative examples should be separated. That is, different triplets of images are consideredone is anchor image with index a, another one is a positive example y p =y a with index p, and the last one is a negative example y n ≠y a with index n, and we want distance D a,p be smaller than distance D a,n by m. Softplus ln(1+exp(x)) is proposed to be used in place of the hidge function [m+] + in [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF], since in Re-ID we want to pull images with the same ID further even after the margin m is reached.

However, distances to similarly looking positives are easy to minimize and distances to arbitrary negatives are easy to maximize. Since triplets in (1) are mostly weak examples and all of them are also computationally demanding to use, hard positive samples and hard negative samples should be somehow selected to make embedding learning with the triplet loss successful. Computationally efficient selection of such hard samples can be done with the use of Batch Hard loss function [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF]. The idea is to form batches using P randomly selected classes (IDs) with randomly sampled K images per class, and to select the hardest positive and negative samples within the batch to form the triplets for the loss function (see details in [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF]).

Here, we also use soft margin and batch hard loss.

Model

We implemented the same network architecture as in [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF] with few differences. Instead of ResNet-50, we used MobileNet [START_REF] Howard | MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications[END_REF], since we found that performance is very similar while MobileNet is much faster. We also discarded the last classification layer and added two fully connected layers to map high-level convolutional features to the embedding space. Similar to [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF], we used the first dense layer with 1024 units with ReLU activation function [START_REF] Glorot | Deep Sparse Rectifier Neural Networks[END_REF], while the second (output) layer had 128 units corresponding to the embedding dimension. We also used batch normalization [START_REF] Ioffe | Batch normalization: Accelerating deep network training by reducing internal covariate shift[END_REF] between layers. Additionally we used dropout [START_REF] Hinton | Improving neural networks by preventing co-adaptation of feature detectors[END_REF] after batch normalization, but in one experiment we found it beneficial to switch it off.

For the usual training, we used ADAM optimizer with default parameters (beta 1 =0.9, beta 2 =0.999). The learning rate was set to 10 -4 during first 100 epochs. During next 300 epochs we exponentially decay the learning rate till 10 -7 . The number of steps per epoch was somewhat arbitrarily defined as N total /N batch , where N total is total the number of images in all used datasets, and N batch =KP is the batch size. We used K=4 and P=18 in all experiments.

In our online fine-tuning method (described below), we used RMSProp optimizer with default parameters. The initial learning rate was set to 10 -5 , and the final learning rate after decay was 10 -6 . The number of steps per epoch was defined as N pos /K, where N pos is total number of images in all positive samples. Since fine-tuning it was applied to the pre-trained model MARS is much larger, the number of epochs was taken smaller (20 epochs for Market-1501, and 2 epochs for MARS).

Improvements

Embedding Learning on Multiple Datasets

Usually the difference between different Re-ID datasets (for example between Duke and CUHK03) is quite significant. This is the source of the problem with using on one dataset a model trained on another dataset. The obvious idea is to train a model on several datasets simultaneously to force it to learn dataset-invariant embedding, which will be better transferrable to new datasets.

However, large difference between datasets means that it would be quite easy for the model to distinguish images from different sources. One can argue that it will prevent the model from learning invariant features. Instead, the model will focus on pushing different datasets apart in the embedding space, and on learning features more specific for individual datasets, which will be less useful in general setting.

In the case when we use the batch hard triplet loss, we can try to prevent this problem. Our approach is to train an embedding in such a way that network never "sees" images from different datasets simultaneously. We do it by forming each batch with images from only one dataset and we continuously switch between them during training. As we expect, this should prevent the model from simply pushing images from different datasets apart. Instead this should force it to search for invariant features, which, as we hope, will be useful for other datasets. We call this algorithm BH-switch. We will compare this algorithm with straightforward approach for training on multiple datasets where we just simply merge datasets together. We call this straightforward algorithm BH-merge.

Practically Unsupervised Fine-tuning

We can hope that the model trained on multiple datasets will be more datasetinvariant, and thus easier transferrable to new cameras. However, the model still needs to be tuned to achieve higher performance on new data distributions. This tuning should be done unsupervisingly. To apply the triplet loss directly, one should somehow guess positive and negative samples, i.e. which pairs of images correspond to same ID, and which correspond to different IDs.

Extracting Positive Samples

We propose the following method for extracting positive samples from unlabeled set of images (or tracklets) from two cameras. We can assume that we have a pre-trained model, which has a reasonable Re-ID performance for these two cameras. Using this model we calculate features for all images in our unlabeled training set. Then, the distance in the feature space is calculated between each possible pair of images from different cameras. We can except that pairs with minimal distance will be, with high probability, positive samples. We select first N p pairs with minimal distance and we will use them as presumable positive samples, where N p is a parameter.

Appropriate choice of N p can be important. If it is too small, there will be not enough training data to tune the model. If it is too high, the fraction of false positives among selected N p pairs will higher, and the model drift will take place. It is clear that N p should be proportional to the number of available images, but the coefficient of proportionality depends on two unknown factors, namely, on how well the pre-trained model suits these new data, and on the fraction of images (or tracklets) which belong to IDs which presented on both cameras (some IDs can be presented only on one camera). For example, the latter varies considerably for different pairs of cameras in MARS (from 0.24 to 0.92).

Our experiments showed that the dataset-dependent choice of N p influences the performance of fine-tuning. However, if we simply use N p = min(N 1 , N 2 ), where N 1,2 are the numbers of images (or tracklets) from two cameras, and  is a constant (we used =0.1), then the final performance drops no more than by 0.5%. Thus, we used this simple method without assuming the availability of additional information.

Extracting Negative Samples

Now we turn to the extraction of negative samples since we need them in the triplet loss. When the positive samples are defined, the negative sample can be extracted in a practically unsupervised manner. The simplest way is to take images, which were observed together with one of presumably positive images at the same time on the same camera. Even more negative samples can be gathered if two cameras have strictly non-overlapping field of view. In this case, we can use all images observed simultaneously on both cameras as negatives for each other. Thus, in the following experiments we will assume that we can obtain e.g. 10 negative samples for each positive pair.

Batch Hard Modification

Previously described Batch Hard loss should be adapted to the usage with our method for selecting positive and negative samples, since we don't have complete information about positive and negatives samples for each image in the batch.

We also form PK batches, but each of them contains K mutually positive samples (corresponding to one ID) and (P-1)K images of other IDs, which are negative samples for first K samples (but we don't know, what images have same IDs among these (P-1)K images). While the original Batch Hard averages over all PK images in the batch, here we average over first K images, for each of which the hardest positive and negative samples are found. Consequently, this modified loss will be much noisier. In the following experiments with unsupervised fine-tuning, RMSProp optimizer (instead of ADAM which we used in Multiple datasets training) and a smaller learning rate appeared to be more efficient, since this modified loss is more difficult to optimize.

Experiments

Multiple Datasets

Let us start with testing the embedding training on multiple datasets with the following details. All the scores were computed without test-time data augmentation on MARS dataset. From the Duke dataset, we removed IDs, which belong to images only from a single camera. We found that such IDs only decrease the cross-camera Re-ID performance.

We underline that the models were trained on datasets which do not include MARS or Market-1501, but all scores are given for MARS dataset. So, we are focusing on the cross-base performance here. Table 1 shows Rank-1 and mAP scores for BHmerge and BH-switch. As can be seen, training the embedding on multiple datasets without fine-tuning results in better performance even in the case of BH-merge. Even if the embedding shows an inferior performance on some dataset (e.g. CUHK03 in comparison to Duke), adding this dataset to the united training set improves the cross-base performance. Adding VIPER [START_REF] Gray | Viewpoint Invariant Pedestrian Recognition with an Ensemble of Localized Features[END_REF] and WARD [START_REF] Martinel | Re-identify people in wide area camera network[END_REF] datasets also improved the performance. One can also see, that our BH-switch method is better then BH-merge (by almost 4%).

Unsupervised Fine-Tuning

We used the model trained on CUHK03+DUKE+WARD+VIPER as the pre-trained model for further fine-tuning. Its performance before fine-tuning was 0.483 / 0.296 (Rank-1 / mAP). The tests were conducted on MARS dataset, which contains tracklets from 6 cameras. We extracted presumably positive samples for each combination of cameras (15 possible combinations in total). Each of our "presumably positive" sample is a pair of tracklets from different cameras. We expect that most of our "presumably positive" pairs are indeed belong to the same ID, but of course we will have some fraction of errors. For each positive sample we choose 10 negative samples (random tracklets from the selected pair of cameras, which do not belongs to the ID of the first tracklet from our "positive" pair), which are easily available in practical situations. One should note that if a "presumably positive" pair is identified mistakenly, there is some possibility that negative samples will also contain errors (some negative samples can belong to ID of the second tracklet from the "presumably positive" pair).

First of all, we checked the fraction of real positive samples among selected "presumably positive" samples. This fraction varies from 0.6 to 0.99 for different pairs of cameras. For most of them, it is larger than 0.8, and the average value is 0.83.

The Rank-1 / mAP scores after fine-tuning with our method appeared to be 0.566 / 0.355 meaning +8.3% improvement in Rank-1 over the model pre-trained on multiple datasets and +16.5% improvement over the best embedding model pre-trained on a single dataset. These results were obtained using the training set of MARS for finetuning. Since the goal is online unsupervised fine-tuning, both training and test sets are acceptable to use. So, we performed an additional step: we took the model finetuned on the training set and additionally fine-tuned it on the test set. The final scores increased to 0.592 / 0.380, so the overall improvement in Rank-1 is +19.1%.

Although our method is developed for real situations, in which tracklets are usually available, in many datasets they are absent, so we compare our results with [START_REF] Fan | Unsupervised Person Re-identification: Clustering and Finetuning[END_REF] on Market-1501 dataset without tracklets. We also note that we didn't use dropout in our model here, because it leads to slightly worse results (unlike on MARS, because MARS contains incorrect labels). Here, we also used test-time data augmentation (see [START_REF] Hermans | Defense of the Triplet Loss for Person Re-Identification[END_REF] for details). The comparison results are shown in Table 2. It should be noted that the baseline model for PUL was pre-trained on Duke+CUHK03 in the case of "multiple datasets". The authors [START_REF] Fan | Unsupervised Person Re-identification: Clustering and Finetuning[END_REF] point out "we find that initialization using more labeled datasets does not noticeably improve re-ID accuracy. Sometimes, multi-dataset initialization yields even worse results than single dataset initialization". Thus, we consider the pre-training of our model on more datasets as an improvement.

It should also be noted that we performed fine-tuning of our model on a united test and training sets of Market-1501, because no labels are used, and in a real situation one is interested in the online fine-tuning. If we use only the training set for finetuning, the scores are somewhat lower 0.586 (0.333).

Since we and [START_REF] Fan | Unsupervised Person Re-identification: Clustering and Finetuning[END_REF] use different baseline models, not the absolute scores, but improvements are of interest. From Table 2 it can be seen that the embedding baseline model is better (and thus actually more difficult for improvements), but also relative increase in scores are higher in our method both for multiple dataset pre-training, and for online fine-tuning. Indeed, PUL gains only +0.8% in Rank-1 due to the use of more datasets (in addition to Duke) during pre-training, and +5.5% due to fine-tuning on several datasets (with overall +9.4% in Rank-1 when switching from Dukebaseline to Multiple datasets-PUL). Our fine-tuned model gains +9.9% thanks to the pre-training on several datasets and +9.0% due to fine-tuning on several datasets (with overall +19.1% in Rank-1), which is considerably larger improvement in comparison to PUL (although PUL has superior improvement in the case of CUHK03 only).

Conclusion

In this paper, we have proposed two practical techniques, which help to improve performance of Re-ID systems in real situations, in which these systems should be applied to unlabeled images taken by new cameras placed at new locations. We model this situation by the cross-dataset testing using different public datasets, and take the metric embedding learning with the triplet loss function as a baseline model.

The first technique consists in a special formation of batches using images from several datasets. The main idea is not to feed images from different datasets to the embedding network simultaneously, so the model will learn to distinguish different IDs from the same dataset, but not to distinguish datasets. As a result, we achieved +8.2% increase in Rank-1 score on MARS dataset due to the training on 4 datasets (Duke, CUHK03, WARD, VIPER) instead of using one best dataset (Duke). At the same time, simple merging of datasets yields only +4.3%.

The second technique consists in selecting presumably positive and negative samples to perform fine-tuning from the target unlabeled dataset, for which the Re-ID system should be applied. The main idea is to supplement best positive samples guessed by the model with samples, which appear with presumably positive pairs simultaneously in the video frames and which thus should be negative samples. Our fine-tuning algorithm results in +9% improvement in Rank-1 score on MARS and Market datasets (with the assumption that we can obtain 10 negative examples for each presumably positive pair).

The overall improvement in Rank-1 on MARS and Market-1501 achieved by switching from the baseline embedding model trained on Duke to the fine-tuned model pre-trained on several datasets was +19.1%, which is much higher than +9.4% achieved by PUL [START_REF] Fan | Unsupervised Person Re-identification: Clustering and Finetuning[END_REF].

  ). For example, Rank-1 score can decrease from 0.762 to 0.361 on the Market-1501 test set if the training was performed on the Duke training set instead of the Market-1501 training set.

Fig. 1 .

 1 Fig. 1. Pairs of images of same IDs from different cameras from different datasets: Market-1501 [3], CUHK03[START_REF] Li | DeepreID: Deep filter pairing neural network for person re-identification[END_REF], Duke[START_REF] Zheng | Unlabeled samples generated by GAN improve the person re-identification baseline in vitro[END_REF], Viper[START_REF] Gray | Viewpoint Invariant Pedestrian Recognition with an Ensemble of Localized Features[END_REF], WARD[START_REF] Martinel | Re-identify people in wide area camera network[END_REF]

Table 1 .

 1 Rank-1 (mAP) scores on MARS for the embedding trained on different datasets

	Method	BH-merge	BH-switch
	Training sets
	Duke	0.401 (0.204)
	CUHK03	0.358 (0.189)
	Duke + CUHK03	0.427 (0.243) 0.455 (0.266)
	Duke + CUHK + WARD	0.437 (0.247) 0.468 (0.269)
	Duke + CUHK + WARD + VIPER	0.444 (0.252) 0.483 (0.296)

Table 2 .

 2 Rank-1 (mAP) scores on Market-1501 for the embedding and PUL trained on different datasets

	Method	PUL (no	PUL	Our (no	Our
	Training sets	fine-tuning)		fine-tuning)
	CUHK03	0.300	0.419	0.337	0.397
		(0.115)	(0.180)	(0.143)	(0.183)
	Duke	0.361	0.447	0.417	0.509
		(0.142)	(0.201)	(0.175)	(0.238)
	Multiple	0.400	0.455	0.518	0.608
	datasets	(0.170)	(0.205)	(0.208)	(0.350)


Daniel Stamate
email: d.stamate@gold.ac.uk.

Wajdi Alghamdi

Daniel Stahl

Doina Logofatu

Alexander Zamyatin

PIDT: A Novel Decision Tree Algorithm Based on Parameterised Impurities and Statistical Pruning Approaches

Keywords: Machine Learning, Decision trees, Parameterised impurity measures, Concave functions, Optimisation, Preventing overfitting, Statistical pruning, Permutation test, Significance level

In the process of constructing a decision tree, the criteria for selecting the splitting attributes influence the performance of the model produced by the decision tree algorithm. The most well-known criteria such as Shannon entropy and Gini index, suffer from the lack of adaptability to the datasets. This paper presents novel splitting attribute selection criteria based on some families of parameterised impurities that we proposed here to be used in the construction of optimal decision trees. These criteria rely on families of strict concave functions that define the new generalised parameterised impurity measures which we applied in devising and implementing our PIDT novel decision tree algorithm. This paper proposes also the S-condition based on statistical permutation tests, whose purpose is to ensure that the reduction in impurity, or gain, for the selected attribute is statistically significant. We implemented the S-pruning procedure based on the S-condition, to prevent model overfitting. These methods were evaluated on a number of simulated and benchmark datasets. Experimental results suggest that by tuning the parameters of the impurity measures and by using our S-pruning method, we obtain better decision tree classifiers with the PIDT algorithm.

Introduction

The decision tree algorithm is a highly efficient algorithm used in machine learning and data mining; the model the algorithm produces is easy to understand and interpret, and the algorithm offers accurate results in abbreviated time. Different versions of the decision tree algorithm have been introduced in the last few decades, and it remains an attractive research domain within the field of machine learning. Such algorithms are useful in numerous contexts within pattern recognition and machine learning applications. In the medical field, for instance, decision trees have been employed to diagnose heart disease patients [START_REF] Shouman | Using decision tree for diagnosing heart disease patients[END_REF] and to predict patients who may suffer from psychosis [START_REF] Alghamdi | A Prediction Modelling and Pattern Detection Approach for the First-Episode Psychosis Associated to Cannabis Use[END_REF].

A decision tree algorithm simulates a tree assembly [START_REF] Han | Data Mining Concepts and Techniques[END_REF]. A decision tree consists of nodes that are connected via branches. The decision tree begins with a single root node and ends with a number of leaf / decision nodes; the nodes in between are the internal nodes.

In classification trees, each leaf node is labelled with a particular class. Each node that is not a leaf node applies a test on a certain attribute, and each branch represents a result of the test. The nodes are selected from the top level based on the attribute-selection measure [START_REF] Witten | Data mining: Practical Machine Learning Tools and Techniques[END_REF]. For example, ID3 algorithm [START_REF] Quinlan | Induction of decision trees[END_REF] and its extended version C4.5 [START_REF] Witten | Data mining: Practical Machine Learning Tools and Techniques[END_REF] use information gain (which is based on Shannon entropy) to construct the decision tree; the element with the highest gain is taken as the root node, and the dataset is divided based on the root element values. Again, the information gain is calculated for all the internal nodes separately, and the process is repeated until leaf nodes are reached.

Unlike most machine learning algorithms, decision trees perform local feature selection on different sets of features. The selected feature should be the feature that reduces the uncertainty at the node the most [START_REF] Tan | Introduction to Data Mining[END_REF]. The dataset may then be partitioned accordingly into sub-nodes. This procedure is applied recursively until it meets any stopping criterion, such as the minimum number of instances or the maximum tree depth. Choosing the splitting and stopping criteria are two open problems in decision tree algorithms.

To address the first issue, many decision tree algorithms have proposed different impurity measures as a splitting criterion. Most decision tree algorithms are based on the information gain function for choosing the best attribute for splitting the data at each node that is not a leaf node. For instance, the ID3 and C4.5 algorithms are based on Shannon entropy [START_REF] Tan | Introduction to Data Mining[END_REF], while the classification and regression tree CART algorithm is based on the Gini index [START_REF] Breiman | Classification and regression trees, Machine Learning[END_REF]. However, one drawback in this kind of approach is that these types of impurity measures are only based on one fixed concave function for assessing the impurity in the datasets' class distributions, which means they suffer from a lack of adaptability to various datasets.

Many studies have investigated the importance of the split criterion [START_REF] Buntine | A further comparison of splitting rules for decision-tree induction[END_REF], [START_REF] Liu | The importance of attribute selection measures in decision tree induction[END_REF]. These studies have concluded that the choice of impurity measure does have some influence on the decision tree's efficacy. Inspired by these studies, we have proposed several novel splitting criteria based on parameterised families of strict concave functions that may be used as impurity measures. As such, we propose new parameterised impurities including parameterised entropy (PE), parameterised Gini (PG), parameterised Tsallis (PT), parameterised Renyi (PR), as well as parameterised AlphaBeta impurity (ABI) and parameterised GiniEntropy (GE) impurity. Their purpose will consist of being mostly reduced in a node after a split, which will dictate the choice of the most suitable attribute in that node. These methods indeed provide an innovative approach to improved decision tree performance, as this work shows.

As for the second problem, most practical decision tree implementations use a 'greedy' approach to grow the tree. Such algorithms would usually suffer from overfitting the dataset [START_REF] Han | Data Mining Concepts and Techniques[END_REF], and additional mechanisms are needed to be put in place to prevent this. Several stopping criteria have been introduced to overcome this issue, such as setting the minimum value of the information gain to grow the tree with a C4.5 algorithm for instance [START_REF] Witten | Data mining: Practical Machine Learning Tools and Techniques[END_REF]. A number of recent papers have used permutation tests for different machine learning problems, such as studying the classifier performance [START_REF] Ojala | Permutation tests for studying classifier performance[END_REF], or in the feature selection process [START_REF] Good | Permutation tests: a practical guide to resampling methods for testing hypotheses[END_REF]. With the model overfitting problem in mind, we proposed in this paper the S-condition based on statistical permutation tests, whose purpose is to ensure that the reduction in impurity, or gain, for the selected attribute in a node of the decision tree is statistically significant, and that the observed gain is unlikely to be at least that high just by chance. Moreover, we implemented the S-pruning procedure based on the S-condition, to prevent model overfitting.

We integrate the use of our novel families of parameterised impurities for the attribute selection, with the S-pruning procedure, and with the optimisation of the parameters of the impurity via cross-validation according to the accuracy performance, in a new decision tree algorithm that we call PIDT, whose name stands for Parameterised Impurity Decision Tree.

The rest of this paper is organised as follows. Section 2 introduces the mathematical formulations and the general requirements for the impurity measures, as well as the novel parameterised impurity measures that we propose to be used in selecting the splitting attributes in our PIDT algorithm. Section 3 introduces our S-condition and S-pruning procedure based on permutation tests, which enhance the PIDT algorithm to prevent model overfitting. Section 4 experimentally investigates the proposed parameterised impurity measures and compares them with conventional impurity functions, based on the performances obtained by the PIDT and conventional decision tree algorithms on a number of benchmarks and generated datasets. Finally, section 5 presents conclusions and offers directions for future work.

Impurity measures

As mentioned above, a decision tree algorithm splits the dataset sample (at each node that is not a leaf node) into two or more sets based on the attribute that scores the highest gain (i.e. reduction in impurity) [START_REF] Maszczyk | Comparison of Shannon, renyi and tsallis entropy used in decision trees[END_REF]. In the previous section, we mentioned two conventional impurities mostly used in decision tree algorithms, namely Shannon entropy and Gini index. But there are also other impurities which are presented in the literature such as Tsallis [START_REF] Raileanu | Theoretical comparison between the gini index and information gain criteria[END_REF], and Renyi [START_REF] Maszczyk | Comparison of Shannon, renyi and tsallis entropy used in decision trees[END_REF]. A different work proposed also a generalisation of the conditional entropy [START_REF] Tsallis | The role of constraints within generalised non-extensive statistics[END_REF]. Considering these different studies based on various impurity measures suggests that the choice of the impurity measure influences the decision tree's effectiveness. In the following sub-sections, we provide the mathematical formulations of and the criteria for functions defined on discrete probabilistic distributions, to be impurity measures.

Mathematical formulations

Let X be an n × m data matrix. We denote the r-th row vector of X by Xr, and the cth column vector of X by X c . Rows are also called records or data points, while columns are also called attributes or features. Since we do not restrict the data domain of X, the scale of this domain's features can be categorical or numerical. For each data point Xr, we have a class label yr. We assume a set of known class labels Y, so yr ∈ Y. Let D be the set of labelled data 𝐷 = {(𝑋 𝑟 , 𝑦 𝑟 )} 𝑟=1 𝑛 . During the classification task, the goal is to predict the labels of new data points by training a classifier on D. Now, let k be the total number of data entries in a node, and ki be the number of data entries classified as class i. Then 𝑝 𝑖 = 𝑘 𝑖 𝑘 ⁄ is the ratio of instances classified as i and estimates the probability of class i in the dataset in that node. The primary purpose of the impurity measures is to express the degree of mixture of various classes in a dataset and then to help to define how well the classes are separated via a split in a node. As such, in general, an impurity measure should satisfy specific requirements. Breiman [START_REF] Buntine | A further comparison of splitting rules for decision-tree induction[END_REF] suggested that an impurity measure is a function Imp whose argument is a vector of probabilities from a discrete probability distribution (given by the class proportions in a dataset), which satisfies the following properties:

Property A: Strict concavity 𝐼𝑚𝑝′′ < 0. Property B: Maximality 𝐼𝑚𝑝′ = 0 𝑓𝑜𝑟 (𝑝 𝑖 = 1 𝑘 ⁄ ) 𝑓𝑜𝑟 𝑖 = 1, . . . , 𝑘.
Property C:

Minimality 𝐼𝑚𝑝 = 0 ↔ ∃𝑖 |𝑝𝑖 = 1.
These properties state that the impurity function should be a strictly concave function; they also express what the maximum and minimum points of the function are. Both Shannon entropy and Gini index, which are defined below, meet the impuritybased criteria:

Entropy (D) = E(D) = -∑ p i k i=1 * log(p i ) (1)
Gini (D) = G(D) = 1 -∑ p i 2 k i=1 (2)
Several authors compared the behaviour of Gini index and Shannon entropy to determine which performs better; they concluded that it is not possible to decide which one leads to higher accuracies of the produced decision trees since the two measures have only about 2% disagreement in most cases [START_REF] Liu | The importance of attribute selection measures in decision tree induction[END_REF]. Note that both Gini index and Shannon entropy are based on one strict concave function each, and as such they might not have the flexibility in adapting to various datasets. We have also considered Renyi entropy and Tsallis entropy, both of which generalising Shannon entropy. They are described by the following formulas, respectively:

Renyi (D) = R(D) = 1 1-γ * log (∑ p i γ k i=1 )
where γ > 0 and γ ≠ 1 (3)

Tsallis (D) = T(D) = 1-∑ p i γ k i=1 1-γ
where γ > 0 and γ ≠ 1 (4)

In the next subsection, we propose several families of generalised parameterised impurity measures based on the requirements suggested by Breiman [START_REF] Buntine | A further comparison of splitting rules for decision-tree induction[END_REF] and outlined above, and we introduce our new PIDT algorithm employing these impurities.

Parameterised impurity measures

As mentioned, the novel parameterised impurity measures that we propose in what follows, are used to select the attribute that mostly reduces the impurity by splitting the dataset in a node of the decision tree.

Our first proposed family of parameterised impurities is the parameterised entropy PE, which is formulated below, and is illustrated in Figure 1 for the case of the 2 class problems (the x-axis represents the probability of one class).

PE (D) = E(D) α

where α ∈ 1] (5) The interval of variation for the parameter α, i.e. (0,1], was chosen to allow, on the one hand, a large diversity of shapes of the graph of the impurity PE, and on the other hand, to mathematically ensure the concavity of the impurity (proof not included here due to lack of space). The other requirements inspired by Breiman's work [START_REF] Buntine | A further comparison of splitting rules for decision-tree induction[END_REF], to which we referred in the previous subsection, are also met.

Figure 1 illustrates the impact of α on the shape of the PE curve. In particular, α =1 corresponds to the conventional Shannon entropy, while smaller positive values for α have an effect of diminishing the curvature of the PE curve around its middle (the second derivative's absolute value tends to decrease in that area), and of gradually transforming the curve and make it tends to a plateau for small values of the parameter (for illustration see the curve for α = 0.1 in Figure 1). Intuitively, these changes in the shape of the PE curve suggest potential changes in choosing attributes in a split node of the decision tree, and this was confirmed experimentally when we implemented our framework. This situation happens because the process may give preference to different class probability distributions in the data subsets that are issued from the split. Parameter α clearly influences which splits will be created in the decision tree, and as such it influences the model learnt from the data and allowed it to have more flexibility in adapting to the data than in the case of a fixed impurity such as the conventional Shannon entropy.

In the same manner, parameterised Gini, parameterised Renyi, and parameterised Tsallis are defined by using the following formulas:

PG (D) = G(D) α
where α ∈ (0, 1]

PR (D) = R(D) α where α ∈ (0, 1] (6)
PT (D) = T(D) α where α ∈ (0, 1] (7)
Note that since the concave functions that define the conventional Shannon entropy and Gini index are generalised by the proposed families of parameterised impurities PE and PG respectively, the use of these families of impurities is expected, roughly speaking, to produce comparable or better decision trees in most cases than those based on the conventional entropy and Gini index.

We now define two more families of parameterised impurities based on two parameters α and β this time.

GE (D) = G(D) α + E(D) β

where α and β ∈ (0, 1]

ABI (D) = ∑ p i ∝ k i=1 * (1 -p i ) β (9)
where α and β ∈ (0, 1]

Note that GE combines arbitrary positive and not larger than 1 powers of the Gini index and of the conventional Shannon entropy, generalising these impurities, and offering further flexibility by using two parameters. By the use of the two parameters, ABI family generalises the Gini index and also offers further flexibility in expressing various shapes of impurity. Note also that both GE and ABI fulfil, mathematically speaking, the requirements of impurity inspired by Breiman [START_REF] Buntine | A further comparison of splitting rules for decision-tree induction[END_REF] (proof omitted here due to lack of space).

Figure 2 illustrates, for the case of 2 class problems, the parameterised families of impurities PE and PG for various values of parameter α (see the top half), and the parameterised family of impurities GE for various values of parameters α and β (see the bottom half).

The above parameterised impurity families are used in our novel decision tree algorithm which we call PIDT, whose name stands for Parameterised Impurity Decision Trees. In particular, the impurities define the criterion for selecting the best attributes in the nodes of the decision tree, based on the largest decrease in impurity from the dataset in the parent node to the datasets in the child nodes. This difference is the socalled gain, and will be precisely defined in the next section when the statistical Scondition will be introduced. The PIDT algorithm uses one single selected family of parameterised impurities for a tree induction, and optimises the parameters of the impurity in a cross-validation fashion with respect to the accuracy performance. In the next section, we develop an enhancement of the process of growing the decision tree with the PIDT algorithm, based on a novel statistical pruning procedure Spruning that we introduce here as a useful tool to prevent overfitting problems.

S-pruning

Roughly speaking, the novel S-pruning procedure we describe here terminates some of the branches of the decision tree based on the outcome of a statistical test. In particular, this pruning method only allows the attributes that have a significant predictive power to split the node and grow the tree. Stopping the development of a branch is based on a certain condition, named here the S-condition.

S-condition:

Let X c be the attribute with the highest gain G in a node N. Roughly speaking, G is expressed by the reduction in impurity after the split with attribute X c in the node N. More precisely, the gain is defined in the same way as the information gain for the conventional Shannon entropy in C4.5 algorithm [START_REF] Witten | Data mining: Practical Machine Learning Tools and Techniques[END_REF]. The impurity is measured in the dataset before the split, and in the resulting data subsets for each child after the split.

The impurities in all these data subsets are averaged with weights derived as the fractions represented by the data subsets out of the dataset before the split. The impurity weighted average is then subtracted from the impurity of the dataset before the split, and the result defines the gain G mentioned above. The gain is non-negative for all attributes due to the concavity property of the impurity. Moreover, a higher gain may indicate a higher predictive power for an attribute. However, we want to ensure that a higher gain does not occur by chance. The S-condition defined here is a statistical mechanism to check this.

Let D be the dataset in node N. Shuffle (i.e. randomly permute) the labels in dataset D and measure again the gain for X c . Do this t times so that a vector V of t gain values is built. The S-condition is satisfied if and only if G is smaller than the q quantile of vector V. When the S-condition is satisfied, the branch in node N stops growing and N becomes a terminal node. This defines the S-pruning procedures.

Overall, the logic behind the S-condition is that if the gain G is smaller than the q quantile (for instance for a value q such as 0.95 or 0.9) of a vector V of t gain values (for instance t = 1000) obtained for X c using random labels (since they are shuffled or randomly permuted), then X c is not considered to have predictive power according to the data D in that node N. The values of t and s = 1-q must be specified by the user, where t is the number of label permutations (and thus equal to the number of gain values collected), and the value of s is the significance level (such as in the statistical tests). A smaller s will encourage more pruning. Intuitively, s indicates how likely the gain of the selected attribute X c would have been acceptably high just by chance. Another relevant quantity here is the p-value, defined experimentally as the fraction of cases in which the gain obtained with the random labels was higher than or equal to the gain obtained with the original labels of the records in D. Therefore, if the p-value is small enough (e.g. the p-value is smaller than or equal to the significance level s = 0.1 or 0.05), then we can say that the gain of the selected attribute in the original data is indeed significantly better and, in consequence, that the gain is too high to have occurred just by chance. That is, the null hypothesis of the permutation test is rejected in this case. As such the attribute X c is considered to have significant predictive power, and the split takes place. Note that the S-condition does not hold in this case.

On the other hand, if the p-value is larger than the significance level s, or in other words the S-condition holds, this means that the gain for the selected attribute is not large enough to indicate predictive power, so the development of that branch is stopped.

Note also that higher q (or equivalently smaller s) results in oversimplified trees, whereas the opposite results in reduced pruning and larger trees. As a result of using the S-pruning procedure, fewer nodes are expanded during the building phase, and thus constructing the decision tree is simplified. In addition, the decision tree has the advantage of avoiding overfitting while it is being built.

Comparison of decision tree classifiers with various impurity measures

We now compare several impurity measures with respect to their impact on the decision tree induction, including the conventional impurities such as Shannon entropy and Gini index, and also the new parameterised families of impurities introduced here. We argue that the conventional impurities mentioned above have their flexibility limitations when used with various datasets. We also argue that, due to their flexibility, the parameterised families of impurities are better suited for the purpose of class separation. We also test our novel S-pruning procedure introduced in the previous section. Finally, we demonstrate empirically that the proposed PIDT algorithm indeed produces better decision trees than the algorithms that use simply the conventional entropy and Gini index impurity measures. This section also investigates the performance of decision trees as a result of parameter optimisation. In order to investigate the usefulness of the novel parameterised impurity functions, we tested them on different datasets and compared them with the conventional impurities mentioned above. In order to optimise the parameters of an impurity family, a grid search over a parameter space with 5-fold cross-validation, were used to select the best parameters' values.

Experimental analysis

We chose the open-source library Weka (Waikato Environment for Knowledge Analysis) [START_REF] Frank | The WEKA Workbench, Online Appendix for Data Mining: Practical Machine Learning Tools and Techniques[END_REF] as a starting point in implementing our PIDT algorithm with the S-pruning method option, and parameter optimisation for the families of parameterised impurities above. In particular, the tree builder code was modified and extended to support the conventional impurities Shannon entropy, Gini index, as well as Tsallis, and Renyi, and of course we implemented also the new families of parameterised impurity measures introduced in this paper. The S-pruning method was also added. The PIDT software allows users to specify the family of impurities and values for their relevant parameters, or choose the optimisation of these parameters. It also allows specifying the significance level s and the number of permutations t when the S-pruning method is enabled.

Each experiment used 5-fold cross-validation and was performed with and without the S-pruning method. Finally, the minimum number of nodes was set to 7 in all experiments. Each of the techniques was applied to 7 datasets, of which 5 were real datasets and 2 were simulated datasets with different characteristics.

The real datasets from the University of California-Irvine (UCI) machine learning repository [START_REF]UCI machine learning repository: Datasets[END_REF] that were provided to illustrate the performance of different impurity measures, included the diagnostic Wisconsin breast cancer dataset, the diabetes dataset, the glass identification dataset, and a medical dataset for hepatitis and primary tumours [START_REF] Guyon | Competitive baseline methods set new standards for the nips 2003 feature selection benchmark[END_REF]. Two datasets were also generated using simulation techniques, in particular based on Guyon's proposed approach employed in various researches [START_REF] Guyon | Competitive baseline methods set new standards for the nips 2003 feature selection benchmark[END_REF][START_REF] Guyon | Design of experiments of the nips 2003 variable selection benchmark[END_REF][START_REF] Guyon | Result analysis of the nips 2003 feature selection challenge[END_REF][START_REF] Guyon | A: An introduction to feature extraction, Feature extraction[END_REF]. The simulated datasets contain a few thousand samples and different numbers of classes.

The PIDT algorithm was run for different impurity measures and values for α, β, γ parameters (whichever apply), and significance level s. The parameter space for α and β was 0.05, 0.1, ..., 0.95, 1.0; for γ the values were 0.1, 0.2, … ,0.9,1.5, 2.0, …, 5.0; and the considered significance level s values were 0.01, 0.05, and 0.1. Finally, the bestperforming models with their parameters were chosen for the final comparison on the separate test datasets. Table 2 shows a summary of the models built with the chosen optimised parameters, while Table 1 provides the summary of the models built by using conventional impurities. Bold fonts in Table 2 show the best results scored regarding the chosen dataset. The results demonstrate that the parameterised entropy (PE) could be used to construct more efficient decision trees compared with the conventional entropy impurity and Gini index impurity. In particular, PE led to better results when it was applied with the S-pruning method on most datasets. By looking at Table 1 and Table 2, we observe that the accuracy generally improved, and the number of nodes decreased for the models produced by the PDIT algorithm.

In particular, it is interesting to observe that the accuracy tended to improve depending on the dataset, thus confirming that this performance could be affected by the method used for selecting attributes during the tree construction. In terms of tree size, this was diminished for most datasets. The best reduction was achieved for the Pima diabetes database, where the size of the tree was reduced ten times compared to the standard tree algorithm -which used entropy (as shown in Table 1) -and was comparable to the tree size discussed in [START_REF] Tsallis | The role of constraints within generalised non-extensive statistics[END_REF]. We also note that our results for the hepatitis dataset produced more accurate and smaller tree compared to the results presented in [START_REF] Tsallis | The role of constraints within generalised non-extensive statistics[END_REF]. Overall, PE and PR impurities, in conjunction with activating the S-pruning procedure, produce more accurate results and yield much smaller trees for most of the datasets.

Conclusion and directions for future work

This paper proposed and tested an approach to building optimised classification trees using novel parameterised impurity measures which generalise conventional impurities such as Shannon entropy and Gini index. The experiments were conducted on five real datasets as well as on two simulated datasets. The results show that by building decision trees using parameterised impurity measures with optimal values for their parameters, the predictive models primarily led to better performance in terms of accuracy, than those built with traditional entropy impurity and Gini impurity.

A novel S-pruning method based on permutation tests was also introduced here to overcome the overfitting problem and to produce smaller decision trees. The proposed impurity measures gained significance and produced much smaller trees when they were applied with the S-pruning procedure enabled. However, if the significance level s for S-pruning is set too small, it may result in oversimplified trees.

One direction of extending this work is related to investigating novel impurity measures with flexibility capabilities in adapting to and working well with class-unbalanced problems. This direction is currently under investigation.

Fig. 1 :

 1 Fig. 1: Parameterised entropy (PE) with different values for α.

Fig. 2 :

 2 Fig. 2: Novel parametrised impurity measures PE, PG (top), and GE (bottom)

Table 1 :

 1 Assessing decision trees built with conventional impurity performances

		Decision tree with entropy	Decision tree with Gini
	Dataset	Accuracy	No. nodes	Accuracy	No. nodes
	Breast cancer	0.654	67	0.654	76
	Pima diabetes	0.736	119	0.724	135
	Hepatitis	0.807	21	0.794	25
	Primary tumour	0.434	60	0.363	57
	Glass	0.626	39	0.556	55
	Simulated data 1	0.721	33	0.668	67
	Simulated data 2	0.612	188	0.601	157

Table 2 :

 2 Assessing decision trees built with the PIDT algorithm with parameter optimisation, and with and without S-pruning procedure activated. "-" means values do not apply.

					PIDT
	Dataset	Accuracy	No. nodes		Parameters
				Impurity α β γ S-pruning s Permutations
	Breast cancer	0.731 0.720	91 29	PG PR	0.5 --1 -0.5	no yes	-0.05	-1000
	Pima diabetes	0.734	11	PE	0.5 --	yes	0.05	1000
	Hepatitis	0.839 0.807	23 7	PE PE	0.3 --0.3 --	no yes	-0.05	-1000
	Primary tumour	0.434	60	PE	1 --	no	-	-
	Glass	0.636	27	PE	0.6 --	no	-	-
	Simulated data 1	0.721	7	PE	0.8 0 0	yes	0.05	1000
	Simulated data 2	0.693	157	GE	1 0.4 -	no	-	-


Ilias Kalamaras
email: kalamar@iti.gr

Anastasios Drosou
email: drosou@iti.gr

Konstantinos Votis
email: kvotis@iti.gr

Dionysios Kehagias

Dimitrios Tzovaras
email: tzovaras@iti.gr

A multi-objective data mining approach for road traffic prediction

Keywords: Data Mining, Multi-objective Optimization, Pareto-optimal Solutions, Clustering, Graph-based Representation

Road traffic prediction for the efficient traffic control has lately been in the focus of the research community, as it can solve significant urban issues, such as city evacuation plans, increased concentration of CO2 emissions and delays caused by extended traffic jams. The current paper proposes a novel approach for multi-variate data mining from past traffic data (i.e. average speed values per road), so as to dynamically detect all significant correlations between the road network components (i.e. the segments of the roads) by mapping the latter onto a low dimensional embedding. Multiple traffic-related features (e.g. speed correlation, spatial proximity, phase difference, etc.) are utilized in a multi-objective optimization framework, producing all Pareto-optimal embeddings, each one corresponding to a different trade-off between the objectives. The operator is provided with the option to interactively select among these Paretooptimal solutions, so as to explore the most descriptive sets of road influences. The proposed method has been evaluated on real traffic data, while the evaluation of the forecasting performance of the multi-objective approach exhibited accuracy improvement with respect single-objective approaches.

Introduction

Traffic conditions on road networks have grown to affect several aspects such as the amount of productivity and the lifestyle of the citizens in big urban centers. The optimization of transport, in terms of both individuals and/or fleets, has a serious socioeconomic and environmental impact. The study towards the development of intelligent transportation systems (ITS) is constantly gaining attention by the research community. Although common traffic detectors could help alleviate certain traffic problems, the fact that traffic is a dynamic, constantly altering variable, poses new challenges in its confrontation. Consequently, the problem of forecasting traffic within short time intervals ahead of time has arisen as a crucial task, the satisfactory analysis of which is believed to result in more efficient and dynamic routing solutions.

Traffic may be interpreted in various ways through traffic descriptors, such as travel time and instantaneous vehicle speed, observed using GPS sensors. Traffic prediction techniques use this information, taking also into account the fact that the traffic in one region can affect the traffic in another. However, most techniques utilize a single notion of influence between roads, e.g. the correlation between their traffic time series. However, such influences are usually multi-dimensional, depending on more than one parameters, e.g. phase similarity of the corresponding time series, geographical proximity of the roads, etc.

In this paper, an approach for traffic prediction is proposed, which takes into account multiple types of influence among roads. The proposed method considers multiple notions of dissimilarity between roads, based on correlation, phase, geographical distance, etc. The dissimilarity measures are used in a multi-objective Multidimensional Scaling framework, for computing the influence between roads and using it for prediction. The multi-objective nature of the framework allows the selection of tradeoffs among the dissimilarity measures, allowing data exploration by operators.

Related Work

Existing approaches used for traffic prediction are divided into parametric and nonparametric methods. Parametric methods are based on specific pre-determined models that are trained in order to deduce their parameters. Common parametric methods include the Auto-Regressive Integrated Moving Average (ARIMA) model [START_REF] Box | Time Series Analysis, Forecasting and Control[END_REF], and its variations, such as the Auto-Regressive Moving Average (ARMA) model [START_REF] Brockwell | Introduction to Time Series and Forecasting[END_REF]. In contrast with the univariate analysis of the ARIMA model, its multivariate counterpart, the Space-Time ARIMA (STARIMA), first introduced in [START_REF] Pfeifer | A three-stage iterative procedure for space-time modeling[END_REF], takes into account several time series that are related to each other, introducing new parameters to account for spatial and temporal lags. A quite different line of parametric methods is the widely used Kalman Filters [4] [START_REF] Okutani | Dynamic prediction of traffic volume through Kalman filtering theory[END_REF], which are based on updating a state variable upon receiving each new measurement.

In non-parametric methods, the model is not known a-priori. Non-parametric methods can be categorized to memory-based ones, which retain historical samples in order to perform prediction, and model-based ones, which only need the extracted model, discarding historical data upon the training phase. The most typical example of a memory-based model is the k-Nearest Neighbor (kNN) method. Although simple in nature, kNN seems to produce satisfactory results [START_REF] Shen | Traffic velocity prediction using GPS data[END_REF], suggesting that performance lies mainly in the proper representation of the dataset features rather than the blind application of a robust algorithm. Model-based methods construct a model using training data. Typical examples include Random Forests (RFs) [START_REF] Breiman | Random forests[END_REF], Artificial Neural Networks (ANNs), such as Multi-Layered Perceptrons (MLPs) [START_REF] Vlahogianni | Optimized and metaoptimized neural networks for short-term traffic flow prediction: A genetic approach[END_REF][9], and Support Vector Machines (SVMs) [START_REF] Vapnik | The nature of statistical learning theory[END_REF] [START_REF] Wu | Travel-time prediction with support vector regression[END_REF].

Multi-objective optimization deals with problems having many conflicting objectives [START_REF] Ehrgott | Multicriteria optimization[END_REF] [START_REF] Coello | Evolutionary algorithms for solving multi-objective problems[END_REF]. Such problems arise frequently, especially in engineering and economics, for instance maximizing speed while minimizing fuel consumption or maximizing profit while minimizing cost. A solution that is optimal for one objective is subopti-mal for the other. One way to deal with this conflict is by scalarizing the objective functions, i.e. combining them in a single objective, which is then minimized with traditional optimization methods. Scalarization methods include using a weighted sum of the objectives [START_REF] Ehrgott | Multicriteria optimization[END_REF], the ε-constraint method, where only one of the objectives is minimized, with the others used as constraints [START_REF] Ehrgott | Multicriteria optimization[END_REF], or achievement function-based methods, that measure the distance of a solution from a reference one [START_REF] Wierzbicki | On the completeness and constructiveness of parametric characterizations to vector optimization problems[END_REF]. Scalarizing the objectives involves setting preferences for the multiple objectives, (e.g. the weights of a sum, or the reference point for achievement functions), which is not a trivial task. Another class of multi-objective optimization methods produce a set of solutions [START_REF] Ehrgott | Multicriteria optimization[END_REF] instead of a single one, namely the Pareto front, containing different trade-offs among the objectives. Such an approach can often discover solutions that scalarization approaches cannot, e.g. solutions lying in concave parts of the Pareto front. The Pareto front is commonly calculated using genetic algorithms, since the fact that they maintain a population of solutions, instead of a single one, suits the goal of calculating multiple solutions [START_REF] Coello | Evolutionary algorithms for solving multi-objective problems[END_REF] [START_REF] Zitzler | A tutorial on evolutionary multiobjective optimization[END_REF]. For the determination of the fitness function of the genetic process, different approaches have been followed [START_REF] Zitzler | A tutorial on evolutionary multiobjective optimization[END_REF], including weighted sums of the objectives with varying weights [START_REF] Hajela | Genetic search strategies in multicriterion optimal design[END_REF], alternating among the objectives [START_REF] Zitzler | A tutorial on evolutionary multiobjective optimization[END_REF] and using dominance relations [START_REF] Zitzler | SPEA2: Improving the strength Pareto evolutionary algorithm[END_REF].

Most of the existing methods for traffic prediction usually deal with one trafficrelated characteristic (i.e. modality), e.g. speed velocity at a given time instant, travel time required to traverse a road, etc. However, traffic prediction is a multivariate problem and such approaches pose some information loss, since they restrict the cognitive understanding of the traffic to one dimension. In this respect, the current paper proposes a framework that is able to merge multiple variables on a common space via the utilization of Multi-Dimensional Scaling and multi-objective optimization, overcoming thus the so-called "curse of dimensionality", while a set of Pareto-optimal cases is provided to the traffic operator as possible choices for traffic prediction.

Motivation and contribution

Existing research has shown that the choice of the data mining approach to use for traffic prediction can affect the capability traffic modeling. The work of [START_REF] Kamarianakis | Space-time modeling of traffic flow[END_REF] shows that just considering the flow of a road at previous times without considering the flow of neighboring roads discards information that is essential for producing more representative traffic models. Extending this further, the utilization of only a single notion of influence between roads, e.g. graph neighborhoods, may discard other types of influence that may lead to more accurate models. Influences among roads usually depend on more than one parameters, such as correlation between their traffic flow, flow phase similarity, geographical proximity, etc. When multiple types of information are available, multi-modal processing techniques have proven useful in combining all available information, in order to produce outcomes that are more accurate than using each type of information separately. Combining multiple modalities has been especially useful in the field of multimedia analysis [START_REF] Atrey | Multimodal fusion for multimedia analysis: a survey[END_REF]. Multi-objective optimization has shown promising results in this field, for managing multiple modalities [START_REF] Kalamaras | Multi-objective optimization for multimodal visualization[END_REF], as a generalization of other multimodal techniques, able to discover more solutions and to present the operator with a set of limited optimal trade-offs. Adapting this approach for combining multiple traffic-related characteristics seems promising for improving traffic prediction and allowing parameter exploration by the operator.

The contribution of this paper is the combination of multiple traffic-related features, using multi-objective optimization techniques, in order to measure the influence of one road to other roads of the network, and thus define different notions of "neighborhood", based on Multi-Dimensional Scaling, to be used in STARIMA traffic models. The proposed framework seems to produce promising results, and is adaptive to more traffic features and further notions of road similarity, providing space for further experimentation and research. From an application point of view, the operators are presented with a set of trade-offs among the multiple traffic features, allowing them to select the most important ones for prediction. Such interactivity facilitates the operator of an ITS in exploring the available data and making decisions.

Proposed approach

The proposed approach proceeds as follows. Initially, traffic-related features (vehicle speed, etc.) are extracted for each road in order to compute pairwise distance matrices, using multiple notions of road distance. The distance matrices are used to construct objective functions, whose minimization leads to an embedding of the roads as points on the 2D plane. Multidimensional Scaling (MDS) is used to formulate these objectives, while multi-objective optimization techniques are used to compute a set of Pareto-optimal placement solutions. This way, a set of alternative placements of the roads are provided, that can be used to define neighborhoods of influence, for use in STARIMA [START_REF] Pfeifer | A three-stage iterative procedure for space-time modeling[END_REF] traffic prediction. The placement solutions can be interactively selected by the operators, with reference to the indicated current state of the selected road segment, while traffic prediction is visually annotated in real time on the map.

Problem formulation

A set 𝑂 = {𝑅 1 , 𝑅 2 , … , 𝑅 𝑁 } of N road segments is considered. A road segment is the part of a road between two subsequent intersections. If there are two opposite lanes in the same road between two intersections, two separate road segments are considered, one for each lane. Without loss of generality, the road segments are hereby considered to be straight lines. For a particular day, each road segment 𝑅 𝑖 , 𝑖 = 1 … 𝑁, is modeled as a set of certain attributes:

𝑅 𝑖 = {𝒔 𝑖 , 𝒆 𝑖 , 𝒗 𝑖 } ∈ 𝑃, (1)
where 𝒔 𝑖 ∈ 𝑹 2 is the starting point of the segment, in map coordinates (latitude and longitude), 𝒆 𝑖 ∈ 𝑹 2 is similarly the ending point of the segment and 𝒗 𝑖 ∈ 𝑹 𝑀 is a vector whose j-th element, 𝑗 = 1 … 𝑀, is the average speed of the vehicles traveling on the road segment at the j-th time interval, where the day has been split into M time intervals. The road segments 𝑅 𝑖 are considered to belong in the space 𝑃 of all sets of these attributes.

The problem addressed hereby is, given the road segments and the vehicle speeds for a specific day, to discover which road segments are related to a selected road segment, in order to predict which segments will be influenced by a change in the vehicles' speed, e.g. denoting congestion, at the selected segment, on the same day another week.

Road segment distance measures

The proposed approach is based on defining notions of distance among the road segments, which encode different types of influence among them. The following distance measures are used, covering various spatiotemporal characteristics, although others can be incorporated as needed. The distance measures are used to construct distance matrices among the data, containing the distances among each pair of road segments.

Cross Correlation similarities. This metric stands for the cross correlation value between the sequences of speeds of two road segments. Given two road segments 𝑅 𝑖 and 𝑅 𝑗 , 𝑖, 𝑗 ∈ 1 … 𝑁, with their corresponding speed vectors 𝒗 𝑖 and 𝒗 𝑗 , the correlation distance 𝑑 cor is defined as follows:

𝑑 cor (𝑅 i , 𝑅 j ) = max 𝑘=-𝑀…𝑀 | 𝐸[(𝑣 𝑖,𝑡 -𝜇 𝑖 )(𝑣 𝑗,𝑡+𝑘 -𝜇 𝑗 )] 𝜎 𝑖 𝜎 𝑗 |, (2)
whereby 𝑣 𝑖,𝑡 is the t-th element of vector 𝒗 𝑖 , 𝜇 𝑖 is the mean value of vector 𝒗 𝑖 , 𝜎 𝑖 is the standard deviation of 𝒗 𝑖 and 𝐸[⋅] stands for the mean value of the enclosed values, for all values of t. The correlation value derives from the absolute value of the Pearson Product-Moment Correlation Coefficient (PPMCC), with the modification of considering a phase parameter k, in order to take all the possible alignments of the two time series, as in [START_REF] Diamantopoulos | Investigating the effect of global metrics in travel time forecasting[END_REF], since one of them may be delayed with respect to another due to time needed for traffic to pass from one segment to another.

Phase similarities. The correlation value above considers the maximum value of the correlation coefficient for all possible alignments of the two time series. The phase similarity 𝑑 phase between two time series is hereby defined as the amount of sliding needed in order to achieve this maximum coefficient value. It is therefore defined as:

𝑑 phase (𝑅 𝑖 , 𝑅 𝑗 ) = |arg max 𝑘=-𝑀…𝑀 | 𝐸[(𝑣 𝑖,𝑡 -𝜇 𝑖 )(𝑣 𝑗,𝑡+𝑘 -𝜇 𝑗 )] 𝜎 𝑖 𝜎 𝑗 || (3)
Only the absolute value of the delay k is used, in order for the distance measure to be symmetric. However, the sign of the delay, i.e. whether the second segment precedes or follows the first, can be used in applications, in order to demonstrate which road segments will be influenced in the future.

Geographical proximity.

The geographical distance 𝑑 geo between two road segments is defined as the Euclidean distance between their midpoints:

𝑑 geo (𝑅 𝑖 , 𝑅 𝑗 ) = ||𝐦 i -𝐦 j ||, (4)
where 𝐦 i = 1 2 (𝐬 i + 𝐞 i ) and || ⋅ || denotes the Euclidean norm.

Dynamic Time Warping difference. Provided the strong dependence on temporal relations of the fluctuations in the recorded velocities during the day, another metric that has been utilized for the estimation of the intra-distances between the roads is the Dynamic Time Warping (DTW) algorithm [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF] that sufficiently manages to capture the spatiotemporal characteristics of these signals. The DTW algorithm has been widely used in a series of matching problems, varying from speech processing [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF] to biometric recognition applications. Its main advantages are its simple implementation and its satisfactory performance given the required processing time.

Multi-objective multidimensional scaling

The hereby proposed approach is, using the distance measures described in Section 4.2, to embed the road segments into a low dimensional space, where nearest neighbors can be calculated, given a selected segment. Formally, the goal is to find an embedding 𝐩 1 , 𝐩 2 , … , 𝐩 N , 𝐩 i ∈ ℝ 𝐿 , for the N road segments 𝑅 1 , 𝑅 2 , … , 𝑅 𝑁 , so that the distances among the points 𝐩 i in the low dimensional space ℝ 𝐿 correspond to all the notions of distance between road segments which are defined in Section 4.2.

Multidimensional Scaling (MDS) [START_REF] Cox | Multidimensional scaling[END_REF] is a common technique used to find an embedding of a set of points, when only the distances among them are known. Let the known target distances be 𝛿 𝑖𝑗 , 𝑖, 𝑗 ∈ 1 … 𝑁. The desired embedding 𝑃 = (𝐩 1 , 𝐩 2 , … , 𝐩 N ) ∈ 𝒫 of the objects is one in which the target distances among points are best preserved in the embedding. Let 𝐽: 𝒫 → ℝ ≥0 be a cost function (objective function), evaluating the capability of an embedding 𝑝 ∈ 𝒫 for preserving the target distances among the data. ℝ ≥0 is the set of non-negative real numbers. A commonly used objective function for MDS is the following:

𝐽(𝐩 1 , 𝐩 2 , … , 𝐩 N ) = ∑ (||𝐩 𝑖 -𝐩 𝑗 || -𝛿 𝑖𝑗 ) 2 𝑁 𝑖,𝑗 (5)
Since there are multiple notions of distance between two data points (Section 4.2), multiple objective functions for MDS can be defined, one for each distance measure used. This is handled as a multi-objective optimization problem [START_REF] Ehrgott | Multicriteria optimization[END_REF], using genetic algorithms [START_REF] Zitzler | SPEA2: Improving the strength Pareto evolutionary algorithm[END_REF], resulting in a Pareto front of optimal trade-offs among the objectives. The genetic algorithms proceed by examining different placements of the N points on the 2D plane, so that there are 2N variables. Crossover strategies can combine two placements by randomly keeping, for each object, the corresponding point from either parent as the child's point. Mutation operates by adding random noise on the child's position. The initial population size can be chosen as multiple of the solutions that are kept to represent the final Pareto front, which can be in the order of 10 -20, so that they are not overwhelming to the operator. The focus of this paper is more on the assessment of how the combination of multiple traffic characteristics can benefit prediction than on finding the optimal crossover/mutation functions and population size. Further work can use different optimization techniques, in order to achieve more representative Pareto fronts faster.

An example Pareto front for a problem of two objectives is illustrated in Fig. 1(a). The Pareto diagram depicts the Pareto optimal solutions as points, having the values of the objective functions as coordinates. The gray-shaded area represents the set of all feasible solutions, while the bold border in the lower left of the feasible area is the Pareto front. Point 𝑃 2 dominates 𝑃 1 , as well as the whole hatched area, since both objectives have smaller values at 𝑃 2 . On the other hand, points 𝑃 2 and 𝑃 3 are incomparable, since decreasing one objective leads to increasing the other one.

The selection of a Pareto-optimal embedding to use for detecting roads with similar characteristics and making predictions is performed by a human user. The solutions of the Pareto set are presented to the user in the form of a Pareto diagram, such as the one in Fig. 1(a)Error! Reference source not found.. By selecting among different trade-offs, the operator can focus on different aspects of traffic flow and be assisted in predicting future states. After the selection of a Pareto-optimal embedding, the road segments are represented by points in the 2D space (see Fig. 1(b)). Nearby points represent roads that are similar with respect to the distance measures used and the Pareto trade-off that has been selected. When an operator selects a road segment on the map, wishing to view the segments which are influenced by it, the nearest roads segments to the selected one in the embedding are found and presented on the map. The amount of closeness of a road segment can be depicted graphically on a map by e.g. controlling its color or opacity.

5

Evaluation of the proposed approach

Dataset Description

The proposed method has been tested on the so-called Berlin dataset, which was recorded from 18/03/2012 to 31/03/2012, using the open TomTom API [START_REF]TomTom open maps API[END_REF]. The data contain real vehicle speed measurements from Berlin, collected from several road points using GPS locators. Each measurement contains the instantaneous speed at a specific road point, measured in millisecond intervals, and is accompanied by the map coordinates of the road location. However, due to the absence of speed values in many time moments, a preprocessing of the original data was performed, as described in [START_REF] Diamantopoulos | Investigating the effect of global metrics in travel time forecasting[END_REF]. The preprocessing procedure, for a day of measurements is as follows.

First, the measurement points were grouped in road segments, i.e. parts of a road between two subsequent intersections, resulting in about 7000 road segments, each associated with the speeds obtained for the road points inside it. Since each road segment may contain a different number of speed measurements, the raw measurements were grouped in five-minute intervals, considering the harmonic mean of the speed values at each interval. The size of the resulting speed vector assigned to a road segment was at most 288, the number of five-minute intervals in a day. This significantly reduced the size of the dataset and compensated for many missing values. However, there were still many intervals within a day with no measurements, so we kept a time period of 15 hours that had a small overall number of missing values throughout the whole dataset. This truncated the speed vectors to 180 values. The remaining missing values were filled using cubic spline interpolation. Finally, in order to limit the experiments to busy, and thus interesting, roads, the road segments were further filtered by keeping only those within a radius of approximately 5km from the city center. The final dataset consists of about 1300 road segments for each day of the week, each associated with a 180-dimensional speed vector (of average speed value 33.5 km/hour).

Experimental Results

The proposed method has been employed for the task of predicting the speed of a road segment at a future time interval. For evaluation purposes, it has been compared to the performance of methods which use a single objective to determine which road segments are influenced by the traffic of a selected segment. The model used for prediction is a simplified form of the STARIMA model, such as the ones used in [START_REF] Diamantopoulos | Investigating the effect of global metrics in travel time forecasting[END_REF]. For a selected road segment, the model is described by the following equation:

𝑧 𝑡+1 = 𝜙 0 𝑧 𝑡 + 𝜙 1 𝑧 𝑡-1 + 𝜙 2 𝑧 𝑡-2 + 𝜓 0 𝑢 𝑡 + 𝜓 1 𝑢 𝑡-1 (6)
Hereby, 𝑧 𝑡+1 is the predicted value of the speed of the road segment at time interval 𝑡 + 1. This value is calculated as a weighted combination of the speed values of the same road at previous time intervals, as well as of roads that are influenced by the selected road segment. The values 𝑧 𝑡 , 𝑧 𝑡-1 and 𝑧 𝑡-2 in Eq. ( 6) are the speeds of the road segments at the current time interval, t, and at the two previous time intervals, 𝑡 -1 and 𝑡 -2, respectively. The parameters 𝜙 0 , 𝜙 1 and 𝜙 2 are used as weights to denote the importance of each previous speed value for the determination of the predicted one. The last two factors of Eq. ( 6) are related to the speeds of the road segments which are most influenced by the selected road segment. The parameter 𝑢 𝑡 is defined as:

𝑢 𝑡 = 1 𝑘 ∑ 𝑣 𝑡 𝑅={𝒔,𝒆,𝒗}∈𝒩 𝑘 (7)
The set 𝒩 𝑘 is the set of the k segments which are most influenced by the selected segment. The value of 𝑢 𝑡 is thus the mean value of the speeds at time interval t of the road segments which belong to the set 𝒩 𝑘 . The determination of the most influenced road segments is hereby performed by selecting, in the 2-dimensional embedding, the k closest points to the point corresponding to the selected road segment. The most influenced road segments are thus determined by considering all notions of distance (Section 4.2) in a multi-objective manner, instead of using a single influence measure, as e.g. in the lag-based STARIMA model of [START_REF] Diamantopoulos | Investigating the effect of global metrics in travel time forecasting[END_REF].

In order to demonstrate the effectiveness of using multiple objectives, a comparison has been performed between two Pareto-optimal solutions. The first corresponds to a combination of the 𝑑 cor and 𝑑 tim distances measures, i.e. it is similar to the lagbased STARIMA method of [START_REF] Diamantopoulos | Investigating the effect of global metrics in travel time forecasting[END_REF], which uses correlation to find the roads that are most influenced, but also exploits time lags. The second Pareto point corresponds to a combination of the 𝑑 cor , the 𝑑 tim and the 𝑑 geo measures, i.e. it also includes geographical information. For each solution, the model of Eq. ( 6) is trained with data from a specific day of the week. The unknown model parameters 𝜙 0 , 𝜙 1 , 𝜙 2 , 𝜓 0 and 𝜓 1 are learned using a least-square error estimate. In order to test the model, predictions are made for the same day at another week. Given the current speed for a specific road segment, along with the previous speeds of the same segment and of the most influenced ones, the speed at the next time interval is calculated using Eq. ( 6).

Fig. 2(a) illustrates the Root Mean Square Error (RMSE) between the predicted and the real values, for different time intervals. For each interval, the RMSE for the prediction of the next interval is depicted. The RMSE is defined as the square root of the mean of the squared error between the predicted and the real values, where the mean is taken over all road segments. The combination of the three measures results in generally smaller prediction errors than the combination of just two of them, especially at the beginning of the day by an improvement of 0.0301 in the RMSE. Fig. 2(b) depicts similar results for another pair of sub-cases. Hereby, the first Pareto solution considers only the geographical distances among the roads, while the second solution considers a combination of the 𝑑 DTW , the 𝑑 tim and the 𝑑 geo measures of Section 4.2. Again the combination of three objectives outperforms the use of only one. The average improvements in the RMSE between the two curves is 0.0717.

The capabilities of the proposed approach have also been exhibited via a visualization application. Let us consider that, after the low-dimensional embedding has been performed and one of the Pareto-optimal solutions has been selected, an operator selects a specific road segment (blue line in Fig. 3(a) -Fig. 3(d)). The point in the 2D embedding that corresponds to the selected road segment is found and the road segments corresponding to nearby points in the embedding are colored on the map. The operator can thus have an overview of which roads are influenced by the traffic conditions of the selected road segment.

In Fig. 3(a) -Fig. 3(d), examples of different segment selections are depicted. When the operator selects a different segment, different roads are colored, denoting those which are mostly influenced by the selected segment. The color of the road segments is an indication of the direction of traffic. The faint red color corresponds to segments whose speed series precede the speed series of the selected segment, in terms of correlation, while segments with bright red color have speed series which follow the ones of the selected segment. As an example, in Fig. 3(d), the colors of the roads indicate that the general direction of traffic is towards the center of the city. The brightest the red colored lines, the biggest is their phase difference in the future. (d) It can be noted that the traffic congestion in the next minutes will be moving towards the center of the city.

Conclusions and next steps

In this study, the problem of forecasting traffic speeds was addressed, using a multiobjective framework that supports the combination of several traffic-related modalities via Multidimensional Scaling. The proposed approach facilitates increased flexibility and efficient human interaction, while exhibiting improved traffic prediction results when the broadly utilized STARIMA algorithm is applied. Furthermore, the proposed framework can form the basis for useful interactive applications, via suggesting only the (Pareto-)optimal solutions to the operator. The potential for further improvement in the prediction accuracy of the proposed approach should be highlighted, since it supports the integration of an unlimited amount of additional traffic-related modalities. Apart from speed measurements, traffic volume measurements can also be exploited as additional modalities in the future. Traffic volume adds additional information, which, combined with traffic speed can lead to more accurate traffic prediction. The utilized distance measures can be extended by using geodesic distance measures, which exploit the graph-like structure of the road network, and may be more informative than actual geographic proximity. The graph-based structure can also be used to improve the distance measures already used, by adjusting the distance matrices, based on their geodesic proximity of the graph. Such improvements are the objectives of future extensions of the current work, with the goal of achieving more accurate traffic prediction.

Fig. 1 .

 1 Fig. 1. (a) Example Pareto diagram. (b) Low-dimensional embeddings solely based on the (i) geographical proximity (ii) temporal proximity (iii) cross-correlation (iv) DTW-based modality.

Fig. 2 .

 2 Fig. 2. Comparison of RMSE for predictions performed using: (a) a combination of 𝑑 cor and 𝑑 tim (blue curve) and a combination of 𝑑 cor , 𝑑 tim and 𝑑 geo (red curve), (b) only 𝑑 geo (blue curve) and a combination of 𝑑 DTW , 𝑑 tim and 𝑑 geo (red curve).

Fig. 3 .

 3 Fig.3. Examples of the neighboring roads, in terms of "merged", low dimensionality distance. The brightest the red colored lines, the biggest is their phase difference in the future. (d) It can be noted that the traffic congestion in the next minutes will be moving towards the center of the city.

Acknowledgments

This work was supported by the EU-funded projects RESOLUTE (H2020-DRS-2014, grant agreement no. 653460) and My-TRAC (H2020-S2RJU-OC-2017, grant agreement no. 777640).