Ezzeddine Fatnassi

An optimization based software tool for Individual automated Guideway Transit Systems

Keywords: Automated guideway transit, Ondemand Transportation systems, Optimization, Branch And Bound

Automated Guideway Transit is a form of public transportation tools where fully driverless vehicles operate in order to move passengers between specic locations. Automated Guideway Transit includes a large variety of systems including mass transit systems and limited people automated guideway transit systems. In this paper, we focus on a specic limited people mover system called personal rapid transit. We develop in this paper an optimization based software which could manage eciently the empty vehicles movements within the personal rapid transit system. Within this context, a branch and bound algorithm is proposed and its eciently is proved on a set of instances taken from the literature. Our algorithm is shown to get good quality results.

Introduction

Personal Rapid Transit(PRT) is a relatively new mode of specic transportation system. It falls under the automated guideway transit systems (AGT). In fact and as any classic AGT, PRT uses a set of automated vehicles which run on dedicated guideways. PRT is designed to move people in urban areas. PRT vehicles move people directly from origin station to destination station with a PRT'network of guideways without intermediate stops or transfers. The transportation service in PRT is done on-demand where one or a group of passengers ask for their transportation service. Typically, the main characteristics of PRT includes: i)Small electric driverless vehicles, ii) Direct origin-to-destination transportation service, iii) on demand transportation service and iv) Exclusive use of the PRT network by the PRT vehicles.

In summary, the main characteristics of PRT includes the oer of a taxilike transportation service by the use of driverless vehicles on a set of dedicated guideways.

As the PRT is a complex, intelligent transportation service, it consists mainly on several advances components such as electric/electronic hardware, guideways, automated vehicles, stations, power sources and software [START_REF] Furman | Automated transit networks (atn): A review of the state of the industry and prospects for the future[END_REF].

Typically, a software is one of the core component of any PRT system. It includes and supervises all the other PRT'components in order to deliver a high level of mobility for its users. Central control system for PRT manages the vehicles movements, the requested trips scheduling, the response of irregular operations such as intrusion, accidents and so on. Consequently, implementing ecient softwares for PRT is of a high importance for such an intelligent transportation system. In this paper, we focus on implementing an optimization based software for PRT in order to eectively manage the empty vehicles management of PRT while reducing its total energy consumption. In fact for a on-demand transportation service such as PRT, we could get up for a high number of empty vehicles moving to take passengers from dierent stations in the PRT'network which represents a high level of wasted transportation capacity. Therefore including optimization module within PRT'management software is of a high importance.

In the literature, several operational optimization related studies to PRT were published such as dynamic routing [START_REF] Chebbi | Modeling on-demand transit transportation system using an agent-based approach[END_REF], network design [START_REF] Zheng | Network design for personal rapid transit under transitoriented development[END_REF], simulation [5][11], optimized operational planning [START_REF] Chebbi | Reducing the wasted transportation capacity of personal rapid transit systems: An integrated model and multi-objective optimization approach[END_REF][9], energy minimization [START_REF] Mrad | Optimal consumed electric energy while sequencing vehicle trips in a personal rapid transit transportation system[END_REF], total traveled distance [10][12][8], eet size [START_REF] Chebbi | Optimal eet sizing of personal rapid transit system[END_REF] and so on.

In this paper, we focus on the optimization problem related to PRT studied by Mrad and Hidri [START_REF] Mrad | Optimal consumed electric energy while sequencing vehicle trips in a personal rapid transit transportation system[END_REF]. They proposed to study the routing electric vehicles with limited battery capacity in a static deterministic context. We propose a branch and bound resolution approach for that problem. We found that our branch and bound method outperforms the commercial solver Cplex' results for solving the PRT'optimization problem. An specic integration of our optimization approach within a PRT'software is also proposed.

The remainder of this paper is organized as follows: Section 2 presents the formal problem denition. Section 3 develops our branch and bound optimization approach. Section 4 describes the computational results as well as the integration of our optimization approach within a PRT'software. Finally, Section 5 concludes the paper.

Problem formulation

We present in this section the problem formulation as presented in the work made by Mrad and Hidri [START_REF] Mrad | Optimal consumed electric energy while sequencing vehicle trips in a personal rapid transit transportation system[END_REF]. The problem treated is based on the assumption that we have a predetermined list of trips to serve.

Let us suppose that we have a set of PRT stations S, a depot D, and a PRT network that makes it possible to journey between any pair of stations. Let us also suppose that we have an unlimited number of vehicles that are initially located in the depot and have battery capacity B.

Cost i,j is a cost matrix that denes the cost of traveling from station i to station j. The cost of moving between station i and station j in the PRT network will be the length of the shortest path calculated using a FloydWarshall algorithm.

Details about Cplex could be found in https://www-01.ibm.com/software/ commerce/optimization/cplex-optimizer/ Let us dene a list of trips T that has cardinality |T | = n. Each trip i (= 1, . . . , n) will have its particular origin and arrival stations (OS i , AS i ) and its particular departure and arrival times (OT i , AT i ). We also suppose that the vehicle should return to the depot to charge its battery when necessary. The PRT problem is dened on an asymmetric graph G = {V , E}, where V = {v 0 , v 1 , v 2 , ,v n } is a set of nodes for which v 0 denes the depot and v 1 , v 2 , ,v n denes the n dierent trips that the PRT system must cover. We dene

V * = V /v 0 . Moreover, E = {(v i , v j ); v i , v j ∈ V } is a set of arcs that is dened as follows: If v i , v j ∈ V * with AT i + Cost (ASi,OSj ) ≤ OT j ,
then the arc (i, j) exists and has cost c ij , which represents the energy consumed from the arrival station of trip i (AS i ) to the arrival station of trip j (AS j ). Hence, each edge will have a combined cost that includes the cost of the movement from one trip to another and the cost of a trip itself. For each node i ∈ V * we add an arc (0, i). The cost of this arc is c 0i and represents the energy used to reach the arrival station of trip i from the depot. For each node i ∈ V * we add an arc (i, 0). The cost of this arc is c i0 and represents the energy used to reach the depot from the arrival station of trip i.

We also dene

E ′ = {(v i , v j ); v i , v j ∈ V * }.
Note that G is a direct incomplete graph, because if the arc between node v i and node v j exists, the opposite arc does not exist. Our problem is a typical node routing problem that can be assimilated into the asymmetrical distanceconstrained vehicle routing problem (ADCVRP). The main purpose in our problem is to assign trips to vehicles with respect to the battery capacity of each vehicle in order to minimize the total consumption of electrical energy.

Flow-based mathematical formulation

In this section, we adapt and present a ow-based mathematical formulation of our problem. This formulation was presented in [START_REF] Kara | Two indexed polonomyal size formulationsfor vehicle routing problems[END_REF] for the asymmetrical distance-constrained vehicle routing problem. We rst introduce the following integer variables:

x ij = { 1 if node j is visited after node i , 0 otherwise, z ij =   
the shortest length traveled from the depot to customer j, as i is the predecessor of j 0 otherwise. Let c ij be the cost of the journey from node i to node j. Let δ + (i) is the set of edges that have v i as a root. Let δ -(i) is the set of edges that have v i as a sink.

PRT(1): Minimize

∑ (i,j)∈E c ij x ij (1) ∑ j∈δ + (i) x ij = 1 ∀i ∈ V * (2) ∑ j∈δ -(i) x ji = 1 ∀i ∈ V * (3) ∑ (i,j)∈E ′ z ij - ∑ (i,j)∈E ′ z ji - ∑ j∈V * c ij x ij = 0 ∀i ∈ V (4)
z ij ≤ (B -c j0 )x ij ∀(i, j) ∈ E ′ (5)
z ij ≥ (c ij + c 0i )x ij ∀i ̸ = 0, ∀(i, j) ∈ E ′ ( 6
)
z 0i = c 0i x 0i ∀i ∈ E ′ (7)
The objective ( 1) is to minimize the total charge used to make all the trips. Constraints ( 2) and (3) control the assignment of trips to routes. In fact, both constraints require that each node i ∈ V * be visited just once. Constraint (4) ensures that the distance from node v i to any node v j by road is equal to the distance between the depot and node v j plus the distance from node v j to node v i . Constraint [START_REF] Chebbi | Proceedings of the Second International Afro-European Conference for Industrial Advancement AECIA[END_REF] ensures that the dierent routes are generated with respect to the battery capacity. In fact, it guarantees that the amount of charge the vehicle consumes to reach node v j from the depot is less than its battery capacity minus the charge needed for returning to the depot. Moreover, in accordance with constraint [START_REF] Chebbi | Reducing the wasted transportation capacity of personal rapid transit systems: An integrated model and multi-objective optimization approach[END_REF], the total charge used to reach node v j from the depot is greater than or equal to the charge needed to follow the direct link between the depot and node v j . Finally, constraint [START_REF] Detienne | The two-machine owshop total completion time problem: Branch-and-bound algorithms based on network-ow formulation[END_REF] provides the initial value for z 0i , which should be equal to the distance from the depot to node v i .

The branch and bound normally starts from a feasible initial solution given by an upper-bounding procedure. However, if we do not have a heuristic approach, the initial upper bound is set to innity. Once some constraints are relaxed, we need to dene a search strategy that consists of the main rules for choosing the next node to branch o and treat. There are two well-known strategies for branching: the depth-rst search (DFS), which consists in solving the most recently generated nodes rst; and the best-rst search, which consist in solving the most promising node rst [START_REF] Germs | Lower tolerance-based branch and bound algorithms for the {ATSP}[END_REF]. Our B&B is presented in Algorithm 1. Based on Algorithm 1, there are several components that need to be dened such as the lower bounding procedure and the branching rules. In the next sections, we present details of the specic components of the B&B method. We should note that a solution S in Algorithm 1 represents a set of roads that cover each node in graph G exactly once.

Computation of lower bound for PRT problem

The lower bound is one of the most important issues for the branch-and-bound algorithm. In fact, the branch and bound has to apply a lower-bounding procedure at each node of the search tree. The lower bound also has the advantage of giving a performance measure for heuristics. In the branch and bound, the lower bounds can be found by relaxing the mathematical formulation. There is a multitude of ways to relax these models. In our B&B, we decided to use the following linear model in order to generate the lower bounds. We will rst introduce the following integer variables

x ij = { 1 if node of index j
is visited after node of index i 0 Otherwise c ij dene the cost of moving between nodes v i and v j in G.

PRT: Min

∑ (i,j)∈E c ij x ij (8) ∑ j∈δ + (i) x ij = 1∀i ∈ V * (9) ∑ j∈δ -(i)
x ji = 1∀i ∈ V * (10)

x ij ∈ {0, 1}∀ (i, j) ∈ E (11)
In fact to generate the lower bounds, we decided to remove the battery constraints from the mathematical model presented in [START_REF] Mrad | Optimal consumed electric energy while sequencing vehicle trips in a personal rapid transit transportation system[END_REF] for solving the PRT problem. The quality of this lower bound is not high, but with this lower-bounding scheme we obtain integer solutions. Solving the relaxed mathematical model, we obtained two types of cycles (routes):

A cycle that respects the battery capacity of the PRT vehicles. A cycle that does not respect the battery capacity of the PRT vehicles which must be eliminated in future resolution of the relaxed linear program. As mentioned in the previous section, solving of the lower bound can result in cycles that do not respect the battery capacity. Such a route is infeasible and thus should be eliminated (i.e., the cycle should not appear in any future relaxation of the problem). Accordingly, we take inspiration from previous work on solving either the asymmetric traveling salesman problem (ATSP) [START_REF] Germs | Lower tolerance-based branch and bound algorithms for the {ATSP}[END_REF] or the ADCVRP [START_REF] Almoustafa | New exact method for large asymmetric distance-constrained vehicle routing problem[END_REF]. Normally, to eliminate an infeasible route, one arc should be removed. In our branch-and-bound method, we assign a large value to the selected arc that should be removed and then solve the relaxed program again. Thus, in the future relaxations, the infeasible route will not reappear. The main disadvantage of this strategy is that the excluded edge may be present in the optimal solution, which can result in a failure of the method to nd the optimal solution.

There are several ways to choose an arc to exclude from the infeasible route:

The rst way is to exclude the arc with the greatest cost.

The second way is to exclude a random arc.

A third way is to use the concept of the tolerance of an arc. This type of sensitivity operator will choose only one infeasible route to work on and branch from each time. Hence, for each infeasible route, the method will compute the ratio between the total electric charge used along the route and the number of arcs in that route. We then choose to work on the infeasible route with the largest ratio. For this route, we solve the dierent relaxation problems while eliminating one arc of the chosen route each time. We add to the tree the nodes that correspond to these dierent relaxations.

In this paper, we choose to work with the third way as a branching rule for our branch-and-bound algorithm.

Example

In this example, we explain the proposed B&B with the sensitivity operator. Suppose that we have 10 trips to serve and we have a battery capacity that permits the vehicle to run for 30 min. For simplicity, we assume that we have no upper bound. Therefore, the initial value of the upper bound is set to ∞.

The route R2 has the larger ratio (ρ(R2) = 9). Hence, we choose arcs from route R2 for branching. We add three nodes to the search tree, where each corresponds to solving the relaxed linear problem while excluding one arc (see Figure 1). The node counter is increased by 3. The upper bound is not updated, since we did not nd a feasible solution.

We now have three subproblems on the tree, with costs 104, 107, and 105. We choose to branch from the node with the least cost (104). Solving the new

Hence, we decide to branch from route R1. We add additional node subproblems to the tree, where each corresponds to excluding one of the arcs (2, 4) (4, 6), and (6, 9) (see Figure 2).. The node counter is updated and increased by 3. The upper bound is not updated, since we again did not nd a feasible solution.

This process is repeated until the maximum number of nodes is reached, the optimal solution is found, or the maximum running time is reached.

Computational Results

We have generated randomly 190 instances using the instances generator of Mrad and Hidri [START_REF] Mrad | Optimal consumed electric energy while sequencing vehicle trips in a personal rapid transit transportation system[END_REF]. The size of the generated instances varies from 10 to 100 PRT'trips in steps of 5. For each trips'size, we generated 10 instances. Tests were made using a program coded in C++ and simulations are performed on a personal computer with Intel i5 2.3 GHZ processor and 6 GO of RAM(Windows 7). We measure the performance of the tested algorithm by the GAP metric which is computed as follows:

GAP = ( (SOL B&B -LB) LB ) * 100 (16)
SOL B&B represents the obtained solution for an instance using the B&B algorithm. The LB is the lower bound related to an instance of our problem. It is calculated based on the linear relaxation of the mathematical model given in [START_REF] Almoustafa | New exact method for large asymmetric distance-constrained vehicle routing problem[END_REF]. All the mathematical models in this paper were coded using Cplex12.1.

Results of our algorithm are proposed in Table 1.

The B&B method founds an average GAP of 0.920 % in 356.717 seconds which could be described as good results. In fact and in many instances, the lower-bound technique used in our B&B can nd integer solutions that are very close to the optimal solution. Also one could note from table 1 that the average computation time for B&B increases at a reasonably low rate.

We also compared the solutions obtained from B&B to those obtained by CPLEX for solving the valid mathematical model for the PRT problem [START_REF] Fatnassi | Comparison of two mathematical formulations for the oine routing of personal rapid transit system vehicles[END_REF].

Our B&B was able to nd better solutions than CPLEX in 30 instances, and the results were equal in 160 instances. We also performed more extensive statistical tests to evaluate the signicance of our results. In particular, we made a Wilcoxon matched-pairs signed-ranks test.

This test yielded a P-value less than 0.0001 and showed that B&B is superior to Cplex. Therefore, we can state that B&B outperforms CPLEX. 4: Use the B&B method to generate the optimal solution 5: The PRT control system uses the obtained data related to the dierent obtained roads from the B&B method to manage the PRT system.

Algorithm 2 includes several steps in order to manage eciently the PRT system. It starts by obtaining the related input such as the metric matrix related to the cost of moving between the dierent PRT stations and the information related to the static list of trips to serve. Next and based on these input data, the two matrix Cost and T ime are constructed. Then, the optimization phase of our PRT software starts by building rst the graph G. The optimization phase then ,and using the proposed B&B method, would solve the constructed problem using the obtained input data. The last step of our algorithm includes the transmission of the obtained roads representing the solution of the B&B method to the central PRT control system in order to route eciently the dierent vehicles available in the depot. [START_REF] Chebbi | Proceedings of the Second International Afro-European Conference for Industrial Advancement AECIA[END_REF]

Conclusion

In this paper, we proposed an optimization approach to minimizing the energy consumption for PRT. While focusing on a static problem related to PRT, a B&B resolution approach was proposed. This method adapted to the context of PRT was capable to solve various sized PRT test instances. In fact, our algorithm was shown to get a good quality results as it handles to nd an average gap of 0.920 in 356.717 seconds.

As future works, we could implement new lower bounding procedures based on dierent type of relaxation. A branch and cut algorithm could also be developed in order to speed up the performance of our algorithm. Also, one could note that the implementation of ecient new meta-heuristic and solution'representation seem to be very interesting in our context in order to enhance the solution quality. New implemented meta-heuristic could also be implemented within our PRT software to solve large instances'size.

  First, we solve the relaxed linear program. We obtain three routes R1 = (D, 0); (0, 3); (3, 7); (7, D), R2 = (D, 1); (1, 5); (5, 8); (8, 9); (9, D), and R3 = (D, 2); (2, 4); (4, 6); (6, D) of 28, 45, and 31 min, respectively. Therefore, we have two infeasible routes R2 and R3. For each of these two routes we calculate the associated ratio ρ as follows: ρ(R2) = 45(Cost of the route R1) 5(number of arcs) = 9 (12) ρ(R3) = 31(Cost of the route R2) 4(number of arcs) = 7.75

Fig. 1 :

 1 Fig. 1: First iteration of B&B

Fig. 2 :

 2 Fig. 2: Second iteration of B&B

Table 1 :

 1 Results of the B&B algorithm Get the information related to the PRT network and the List of Trips 2: Construct the matrix Cost and T ime.

		Number of trips Average Gap % Average Time (s)
		10	0	0.217
		15	0.565	76.056
		20	0.980	151.140
		25	0.980	151.140
		30	0.837	302.896
		35	1.893	480.634
		40	0.337	309.723
		45	0.867	362.849
		50	0.781	481.219
		55	0.976	541.620
		60	0.387	363.099
		65	0.638	439.567
		70	0.898	500.468
		75	2.237	423.149
		80	0.988	484.330
		85	1.112	492.855
		90	0.557	364.977
		95	1.051	305.209
		100	1.398	546.469
		Average	0.920	356.717
	4.1	Integration of the optimization module within a PRT software
	There is several ways to integrate optimization resolution techniques within in-
	telligent mobility softwares. In our PRT context and based on our problem,
	we propose a full integration procedure of our optimization technique which is
	presented in Algorithm 2.
	Algorithm 2 PRT software
	1:

3: Construct the graph G.

Branch-and-bound algorithm for static routing problem of personal rapid transit system For the general VRP, there exists a dierent method of solution that utilizes an exact algorithm. The reader is referred to[START_REF] Baldacci | Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints[END_REF] for a more extensive review of the exact method for the VRP. In this paper, we propose a branch-and-bound algorithm for solving the PRT problem. We present rst the general framework of our branch-and-bound procedure (B&B)[START_REF] Kadri | A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems[END_REF][17][START_REF] Detienne | The two-machine owshop total completion time problem: Branch-and-bound algorithms based on network-ow formulation[END_REF]. The branch-and-bound algorithm is an exact method of nding optimal solutions for various distinctive optimization problems. This method was rst introduced by Land and Doig in 1960. Its main idea consists in enumerating all possible solutions in a search tree. The branch and bound rst solves a general global problem at the root of the search tree. Then, for all the other nodes the branch and bound will solve subproblems in which some constraints are relaxed and some variables are xed.


Katarzyna Borowska
email: k.borowska@pb.edu.pl

Jaros Law Stepaniuk
email: j.stepaniuk@pb.edu.pl

Imbalanced data classification: a novel re-sampling approach combining Versatile Improved SMOTE and Rough Sets

Keywords: Data preprocessing, Class imbalance, Rough Sets, SMOTE, Oversampling, Undersampling

In recent years, the problem of learning from imbalanced data has emerged as important and challenging. The fact that one of the classes is underrepresented in the data set is not the only reason of difficulties. The complex distribution of data, especially small disjuncts, noise and class overlapping, contributes to the significant depletion of classifier's performance. Hence, the numerous solutions were proposed. They are categorized into three groups: data-level techniques, algorithmlevel methods and cost-sensitive approaches. This paper presents a novel data-level method combining Versatile Improved SMOTE and rough sets. The algorithm was applied to the two-class problems, data sets were characterized by the nominal attributes. We evaluated the proposed technique in comparison with other preprocessing methods. The impact of the additional cleaning phase was specifically verified.

Introduction

Proper classification of imbalanced data is one of the most challenging problems in data mining. Since wide range of real-world domains suffers from this issue, it is crucial to find more and more effective techniques to deal with it. The fundamental reason of difficulties is the fact that one class (positive, minority) is underrepresented in the data set. Furthermore, the correct recognition of examples belonging to this particular class is a matter of major interest. Considering domains like medical diagnostic, anomaly detection, fault diagnosis, detection of oil spills, risk management and fraud detection [START_REF] Galar | A Review on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and Hybrid-Based Approaches[END_REF], [START_REF] Sun | Cost-sensitive Boosting for Classification of Imbalanced Data[END_REF] the misclassification cost of rare cases is obviously very high. The small subset of data describing disease cases is more meaningful than remaining majority of objects representing healthy population. Therefore, the dedicated algorithms should be applied to recognizing minority class instances in these areas.

Over the last years the researchers' growing interest in imbalanced data contributed to considerable advancements in this field. Numerous methods were proposed to address this problem. They are grouped into three main categories [START_REF] Galar | A Review on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and Hybrid-Based Approaches[END_REF], [START_REF] Sun | Cost-sensitive Boosting for Classification of Imbalanced Data[END_REF]:

data-level techniques: adding the preliminary step of data processing -assumes mainly undersampling and oversampling, algorithm-level approaches: modifications of existing algorithms, cost-sensitive methods: combining data-level and algorithm-level techniques to set different misclassification costs.

In this paper we focus on data-level approaches: generating new minority class samples (oversampling) and introducing additional cleaning step (undersampling). Creating new examples of the minority class requires careful analysis of the data distribution. Random replication of the positive instances may lead to overfitting [START_REF] Galar | A Review on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and Hybrid-Based Approaches[END_REF]. Furthermore, even applying methods like Synthetic Minority Oversampling Technique [START_REF] Chawla | SMOTE: synthetic minority over-sampling technique[END_REF] (creation of new samples by interpolating several minority class examples that lie together) may not be sufficient for variety of real-life domains. Indeed, the main reason of difficulties in learning from imbalanced data is the complex distribution: existence of class overlapping, noise or small disjuncts [START_REF] Galar | A Review on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and Hybrid-Based Approaches[END_REF], [START_REF] Japkowicz | Class imbalances versus small disjuncts[END_REF], [START_REF] He | Learning from Imbalanced Data[END_REF], [START_REF] Napiera La | Learning from imbalanced data in presence of noisy and borderline examples[END_REF].

The VIS algorithm [START_REF] Borowska | New Data Level Approach for Imbalanced Data Classification Improvement[END_REF], incorporated into the proposed approach, addresses listed problems by applying dedicated mechanism for each specific group of minority class examples. Assigning objects into categories is based on their local characteristics. Although this solution considers additional difficulties, in case of eminently complex problems it may contribute to creation of noisy objects. Hence, the clearing mechanism is introduced as the second step of preprocessing. On the other hand, new preliminary step deals with uncertainty by relabeling ambiguous majority data. All negative (majority) instances belonging to the boundary region defined by the rough sets theory [START_REF] Stepaniuk | Rough-Granular Computing in Knowledge Discovery and Data ing[END_REF], [START_REF] Pawlak | Rudiments of Rough Sets[END_REF] are relabeled to the positive class. Novel technique was developed to verify the impact of inconsistencies in data sets on the classifier performance. Only data sets described by nominal attributes were examined. However, discretization of attributes may allow applying proposed solutions to data including continuous values.

Although only the preprocessing techniques are discussed, we need to mention that there are numerous effective methods belonging to other categories, such as BRACID [START_REF] Napiera La | BRACID: a comprehensive approach to learning rules from imbalanced data[END_REF] (algorithm-level) or AdaC2 [START_REF] Sun | Cost-sensitive Boosting for Classification of Imbalanced Data[END_REF] (cost-sensitive).

Preprocessing algorithms overview

Since SMOTE algorithm [START_REF] Chawla | SMOTE: synthetic minority over-sampling technique[END_REF] is based on the k-NN method, it is not deprived of some drawbacks related to the k-NN performance. Primarily, the k-NN technique is extremely sensitive to data complexity [START_REF] Garca | On the k-NN performance in a challenging scenario of imbalance and overlapping[END_REF]. Especially class overlapping, noise or small disjuncts existing in imbalanced data negatively affects the performance of distance-based algorithms. Considering scenario of generating new minority examples by interpolating two minority instances that belong to different clusters (but were recognised as nearest neighbors), it is likely that new object will overlap with an example of majority class [START_REF] Stefanowski | Selective Pre-processing of Imbalanced Data for Improving Classification Performance[END_REF]. Hence, applying SMOTE to some domains may cause creating incorrect synthetic samples that fall into majority regions [START_REF] Barua | A novel synthetic minority oversampling technique for imbalanced data set learning[END_REF]. Methods like MSMOTE [START_REF] Hu | MSMOTE: Improving Classification Performance When Training Data is Imbalanced[END_REF], Bordeline-SMOTE [START_REF] Han | Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning[END_REF], VIS [START_REF] Borowska | New Data Level Approach for Imbalanced Data Classification Improvement[END_REF] were developed to address this problem. They assume that there are inconsistencies in data set and identify specific groups of minority class instances to select the most appropriate strategy of preprocessing.

On the other hand, there are numerous proposals of hybrid re-sampling methods. They combine oversampling with undersampling to ensure that improper newly-generated examples will be excluded before applying classifier. SMOTE-Tomek links and SMOTE-ENN [START_REF] Batista | A study of the behavior of several methods for balancing machine learning training data[END_REF] introduce the additional cleaning step to original SMOTE processing. The SMOTE-RSB * algorithm [START_REF] Ramentol | SMOTE-RSB * : a hybrid preprocessing approach based on oversampling and undersampling for high imbalanced data-sets using SMOTE and rough sets theory[END_REF] eliminates overfitting by application of the rough sets theory and lower approximation of a subset. Defining the lower approximation of the minority class enables to remove generated synthetic samples that are presumably noise.

The rough set theory was also the inspiration for developing techniques discussed below. They are dedicated to data sets described by nominal attributes.

Rough set based remove and relabel techniques

The method proposed in [START_REF] Stefanowski | Rough Sets for Handling Imbalanced Data: Combining Filtering and Rule-based Classifiers[END_REF] considers applying the rough sets theory to obtain the inconsistences in imbalanced data. The fundamental assumption of the rough set approach is that objects from a set U described by the same information are indiscernible. This main concept is source of the notion referred as indiscernibility relation

IN D ⊆ U × U , defined on the set U . Let [x] IN D = {y ∈ U : (x, y) ∈ IN
D} be an indiscernibility class, where x ∈ U . For any subset X of the set U it is possible to prepare the following characteristics [START_REF] Pawlak | Rudiments of Rough Sets[END_REF]:

the lower approximation of a set X: all examples that can be certainly classified as members of X with respect to IN D;

{x ∈ U : [x] IN D ⊆ X}, (1)
the boundary region of a set X: all instances that are possibly members of X set with respect to IN D;

{x ∈ U : [x] IN D ∩ X ̸ = ∅ &[x] IN D X}. (2)
In described method two filtering techniques based on the presented rough set concepts were developed. Both of them require calculation of boundary region of minority class. Next step depends on the chosen method. The first one removes majority class examples belonging to the minority class boundary region that contains inconsistent objects. The second technique relabels all majority objects that belong to the minority class boundary region.

The figure 1 illustrates results of applying two described methods on artificial data. It also demonstrates the boundary region (with 16 objects) of minority class in the original data set (dashed line).

Versatile Improved SMOTE and rough sets (VIS RST)

The main idea of this new approach is to apply two preprocessing methods: oversampling and undersampling in order to generate minority class instances and ensure that no additional inconsistencies will be introduced to the original data set. This hybrid technique combines modified Versatile Improved SMOTE algorithm with the rough sets theory. Although the VIS method is considered as effective and flexible, introducing the step of removing noise from created minority examples may guarantee better results in classifying data with very complex distribution. The algorithm discussed in this paper is dedicated to data sets described by nominal attributes, however, it can be easily adjusted to the continuous data problems.

At the beginning of algorithm relabel technique is applied (described in subsection 2.1). It is based on rough set theory. Since numerous real-world data sets are imprecise (have nonempty boundary region), the relevancy of this process should be emphasized. Majority class samples belonging to the boundary region of minority class are transformed into minority class examples (their class attribute is modified). In other words, all examples that can be certainly classified neither as negative nor as positive samples are imposed to be considered as minority class members. Thus, the complexity of the problem becomes lower (by reducing inconsistencies) as well as the imbalance ratio is decreased. Using calculations made at the beginning of algorithm, verify whether newly created synthetic object i belongs to the lower approximation of the minority class -if yes: add the example i to the resultDataSet. In the other case, remove generated sample i.

Algorithm VIS RST

30: end for

In the next step minority data is categorized into three groups. To obtain the proper group for each sample the k-NN technique is applied. In order to consider both numeric and symbolic attributes the HVDM metric [START_REF] Wilson | Improved heterogeneous distance functions[END_REF] was chosen to calculate distance between objects. The Heterogeneous Value Distance Metric is defined as:

HV DM (x, y) = m ∑ a=1 d a (v, v ′ ) 2 (3)
where x and y are the input vectors, m is the number of attributes, v and v ′ are the values of attribute a for object x and y respectively. The distance function for the attribute a is defined as:

d a (v, v ′ ) =      1, if v or v ′ is unknown normalized vdm a (v, v ′ ), if a is nominal normalized dif f a (v, v ′ ), if a is linear (4)
The distance function consists of two other functions conformed to different kinds of attributes. Hence, the following function is defined for nominal features:

normalized vdm a (v, v ′ ) = C ∑ c=1 N v,c N v - N v ′ ,c N v ′ 2 (5)
where N v is the number of instances in the training set that have value v for attribute a, N v,c is the number of instances that have value x for attribute a and output class c, C is the number of classes.

On the other hand, the function appropriate for linear attributes is defined as:

normalized dif f a (v, v ′ ) = |v -v ′ | 4σ a (6)
where σ a is the standard deviation of values of attribute a.

Definition 1. Depending on the class membership of the sample's k nearest neighbors, the following labels for the minority class are assigned: -NOISE, when all of the k nearest neighbors represent the majority class, -DANGER, if half or more than half of the k nearest neighbors belong to the majority class, -SAFE, when more than half of the k nearest neighbors represent the same class as the example under consideration (namely the minority class).

The mechanism of detecting within-class subconcepts enables to customize the oversampling strategy for each specific type of objects. Moreover, depending on the number of samples in mentioned groups two main modes of preprocessing minority data are proposed in modified VIS algorithm.

The first one, "HighComplexity", represents the case when the area surrounding class boundaries can be described as complex (at least 30% of the minority class instances are the borderline ones -DANGER label) [START_REF] Napiera La | Learning from imbalanced data in presence of noisy and borderline examples[END_REF]. Definition 2. Since generating most of the minority synthetic samples in this region may lead to the overlapping effect, the following rules of creating new objects are applied for particular kinds of nominal data:

-DANGER: only one new sample is generated by replicating features of the minority instance under consideration, -SAFE: as the SAFE objects are assumed to be the main representatives of the minority class, a plenty of new data is created in these homogeneous regions using majority vote of k nearest neighbors' features, -NOISE: no new instances created. The second mode, "LowComplexity", is appropriate for less complex problems.

Definition 3. When the number of minority samples labeled as DANGER does not exceed 30% of all minority class examples, the processing is performed according to the approach specified below:

-DANGER: many objects are created, because not sufficient number of minority class examples in this specific area may be dominated in the learning process by the majority class samples. Newly generated sample attributes' values are obtained by the majority vote of k nearest neighbors' features, -SAFE: one new object for each existing instance is created. Therefore, number of SAFE examples is doubled. New sample has the same values of attributes as the object under consideration, -NOISE: no new instances created.

There is also one special strategy, namely "noSAFE". It was developed to ensure that the required number of synthetic samples will be created, even as any of the minority class instances belongs to SAFE category. Absence of the SAFE examples indicates that the problem is very complex and most of the objects are labeled as DANGER. In standard way of processing the "HighComplexity" mode is chosen, hence majority of the new objects are generated in safe regions. However, there are no SAFE instances, thus the safe regions are not specified. In order to consider this case, "noSAFE" mode assumes creation of all new examples in the area surrounding class boundaries.

The overall number of the minority class samples to be generated is obtained automatically. The algorithm is designed to even the number of objects from both classes.

The final synthetic minority data set is obtained by eliminating samples considered as noise. The algorithm inspired by rough set notions is applied to indicate which newly created examples are similar to the majority objects. Since only nominal attributes are considered in this analysis, the boundary region of the minority class is calculated. All synthetic samples that belong to the boundary region are removed. This additional cleaning step ensures that the generated data set is deprived of inconsistent objects. It is essential to select only these samples that are certainly members of the minority class.

Experiments

Six data sets were selected to perform experiments. All of them (except didactic) originally came from the UCI repository [START_REF]UC Irvine Machine Learning Repository[END_REF], but after conversions like adjusting them to the two-class problem they were published in Keel-dataset repository [START_REF] Alcala-Fdez | KEEL Data-Mining Software Tool: Data Set Repository, Integration of Algorithms and Experimental Analysis Framework[END_REF]. Only data sets described by the nominal attributes were chosen. They are presented in Table 1 (IR indicates the imbalance ratio).

The aim of this experiment was to prepare comparison of four preprocessing methods. The classification without any re-sampling step was performed to establish a reference point for evaluation of algorithms. The following assumptions were made considering SMOTE and VIS RST techniques:

the number of nearest neighbors (k) was set to 5, the HVDM distance metric was applied, the imbalance ratio after generating new samples was 1.0. The results of classification were evaluated by five measures:

accuracy (Q) -the percentage of all correct predictions (both minority and majority class examples are considered), sensitivity (T P rate ) -the percentage of positive instances correctly classified, specificity (T N rate ) -the percentage of properly classified objects from the majority class. -F -measure -the average of sensitivity and precision. Precision is the number of correctly identified positive samples divided by the number of all instances classified as positive (both properly and erroneously), -AU C -area under the ROC curve. The Receiver Operating Characteristics (ROC) graphic depicts dependency between T P rate and F P rate . The F P rate means the percentage of negative examples misclassified.

The AdaBoost.M1 algorithm [START_REF] Freund | Experiments with a new boosting algorithm[END_REF] with decision trees C4.5 as weak learners was applied as the classifier. This technique represents the group of ensemble methods. The main purpose of combining decisions of multiple classifiers to obtain the aggregated prediction is improvement of generalization [START_REF] Sun | Cost-sensitive Boosting for Classification of Imbalanced Data[END_REF]. A fivefolds crossvalidation was performed. The final experiments' results (presented in Table 2) are the average values of results from five iterations of processing.

Results of these experiments show that the higher complexity of analysed data set is, the better outcomes from applying proposed technique are. VIS RST algorithm indicates that three real-world data sets are the most complex: flare-F, zoo-3 and car-good. One of these data sets, namely flare-F, has nonempty boundary region. Method proposed in this paper outperformed other techniques for this complex example. In all experiments both SMOTE and VIS RST achieve higher values of AUC measure than the classification without preprocessing step. Remove and Relabel filters perform better only in case of nonempty boundary region. Relabel technique may be considered as more effective. It is worth noting that all minority samples generated by the VIS RST method were in the lower approximation. Therefore, undersampling cleaning step was not needed.

Conclusions and future research

Firstly, the experiments revealed that the new VIS RST method is comparable to the SMOTE algorithm when applied to data sets described only by the nominal features. The AU C measure of VIS RST was higher for the flare-F data set. Proposed algorithm outperformed other techniques when evaluated data sets had nonempty boundary regions (flare-F and didactic). Secondly, the Relabel filtering technique performed better than the Remove approach for data set which has the nonempty boundary region (flare-F). In future research the performance of the proposed algorithm adjusted for the Big Data may be investigated. The application of the MapReduce paradigm [START_REF] Dean | MapReduce: Simplified Processing on Large Clusters[END_REF] seems to be promising solution for large imbalance data problem.

Fig. 1 .

 1 Fig. 1. Example of artificial data (60 objects, 15 indiscernibility classes, imbalance ratio IR = 2.75) described by two nominal attributes with three and five values. Data after filtering by the "Remove" technique (IR = 2.25). Data after applying "Relabel" technique (IR = 1.5).

Fig. 2 .

 2 Fig. 2. Example of VIS RSB preprocessing (relabel step is omitted): artificial data where minority objects are labeled as DANGER (orange), SAFE (green) and NOISE (red). The labels are assigned using k = 3 nearest neighbors and normalized vdm metric. Grey objects are new minority class samples generated in respect of the assigned labels.

  DataSet; Number of all instances S; Number of minority class samples M ; Number of nearest neighbors k OUTPUT: resultDataSet: minority and majority class instances after preprocessing 1: Calculate the boundary region. Modify the class attribute of the majority samples belonging to the boundary region -relabel to minority class. Add the number of relabeled instances to the overall number of minority class examples M . Calculate the total counts of objects belonging to each group and save these values in the following variables: saf e, danger, noise. Based on these counts, choose the strategy (mode) of processing: 14: if saf e == 0 then

	2: for i ← 1 to M do
	3:	Calculate the distance between minority class objects and all other examples
		using kN N method.
	4:	Calculate the number of nearest neighbors that belongs to the majority class
		and save this value in majorityClassN eighbors variable. Assign the positive
		instance i into one category (SAFE, DANGER or NOISE) considering the local
		characteristics (nearest neighbors):
	5:	if majorityClassN eighbors == k then
	6:	label[i] = N OISE
	7:	else if majorityClassN eighbors < k/2 then
	8:	label[i] = SAF E
	9:	else if majorityClassN eighbors k/2 then
	10:	label[i] = DAN GER
	11:	end if
	12: end for
	13: 15:	mode := noSAF E
	16: else if danger 30%M then
	17:	mode := HighComplexity
	18: else
	19:	mode := LowComplexity
	20: end if
	21: Calculate the required number of minority class examples to create. The result
		save in N variable.
	22: for i ← 1 to M do
	23:	if label ̸ = N OISE then
	24:	Calculate the distance between minority class objects using kN N method,
		indexes of k nearest neighbors save in nnarray array.
	25:	Create the synthetic examples following rules specified for the appropriate
		mode.
	26:	end if
	27: end for
	28: for i ← 1 to N do
	29:

INPUT:

Table 1 .

 1 Characteristics of evaluated data sets

	dataset	objects attributes IR boundary region
	dermatology-6	358	34	16.90	empty
	flare-F	1066	11	23.79	nonempty
	lymphography-normal-fibrosis 148	18	23.67	empty
	zoo-3	101	16	19.20	empty
	car good	1728	6	24.04	empty
	didactic (see Fig. 1)	60	2	2.75	nonempty

Table 2 .

 2 Classification results for the selected UCI datasets: Q -accuracy, T Praterate of true positives, T Nrate -rate of true negatives, F -F measure, AU C -area under the curve. noPRE 99.44 95.00 99.70 0.95 97.35 94.65 11.63 98.14 0.15 54.89 SMOTE 99.85 100.00 99.70 1.00 99.85 97.26 96.38 98.14 0.97 97.26 VIS RST 99.70 99.70 99.70 1.00 99.70 98.48 99.16 97.80 0.98 98.48 Remove 99.44 95.00 99.70 0.95 97.35 96.08 37.21 98.74 0.45 67.98 Relabel 99.44 95.00 99.70 0.95 97.35 97.09 87.61 98.22 0.86 92.91 lymphography-normal-fibrosis zoo-3 noPRE 97.97 50.00 100.00 0.67 75.00 94.06 40.00 96.88 0.40 68.44 SMOTE 98.94 97.89 100.00 0.99 98.94 97.40 96.88 97.92 0.97 97.40 VIS RST 98.24 97.89 98.59 0.98 98.24 97.40 97.92 96.88 0.97 97.40 Remove 97.97 50.00 100.00 0.67 75.00 94.06 40.00 96.88 0.40 68.44 Relabel 97.97 50.00 100.00 0.67 75.00 94.06 40.00 96.88 0.40 68.44 car good didactic noPRE 98.38 73.91 99.40 0.78 86.66 83.33 68.75 88.64 0.69 78.69 SMOTE 99.43 99.64 99.22 0.99 99.43 89.77 88.64 90.91 0.90 89.77 VIS RST 99.16 99.52 98.79 0.99 99.16 100.00 100.00 100.00 1.00 100.00 Remove 98.38 73.91 99.40 0.78 86.66 100.00 100.00 100.00 1.00 100.00 Relabel 98.38 73.91 99.40 0.78 86.66 100.00 100.00 100.00 1.00 100.00

	method	Q T Prate T Nrate F AU C	Q T Prate T Nrate F AU C
		dermatology-6	flare-F

Acknowledgements

The research is supported by the Polish National Science Centre under the grant 2012/07/B/ST6/01504.


Michail Makridis
email: michail.makridis@jrc.ec.europa.eu

Raúl Fidalgo-Merino
email: raul.fidalgo-merino@jrc.ec.europa.eu

Antonio Cotelo-Lema
email: antonio.cotelo@jrc.ec.europa.eu

Aris Tsois
email: aris.tsois@jrc.ec.europa.eu

Enrico Checchi
email: enrico.checchi@ec.europa.eu

A Quality Assessment Framework for Large Datasets of Container-Trips Information

Keywords: quality assessment, knowledge validation, qualitative indicators, supply chain

Customs worldwide are facing the challenge of supervising huge volumes of containerized trade arriving to their country with resources allowing them to inspect only a minimal fraction of it. Risk assessment procedures can support them on the selection of the containers to inspect. The Container-Trip information (CTI) is an important element for that evaluation, but is usually not available with the needed quality. Therefore, the quality of the computed CTI records from any data sources that may use (e.g. Container Status Messages), needs to be assessed. This paper presents a quality assessment framework that combines quantitative and qualitative domain specific metrics to evaluate the quality of large datasets of CTI records and to provide a more complete feedback on which aspects need to be revised to improve the quality of the output data. The experimental results show the robustness of the framework in highlighting the weak points on the datasets and in identifying efficiently cases of potentially wrong CTI records.

Introduction

The vast majority of non-bulk cargo worldwide is transported in containers. The World Shipping Council, estimates that more than 18 million containers were active in 2011 [5], transporting in 2014 more than 171 million TEU (Twentyfoot Equivalent Unit) of goods [START_REF]Review of the Maritime Transport 2015[END_REF]. Due to the high volumes of containerized trade, with big ports handling more than 80000 TEU a day [START_REF]Review of the Maritime Transport 2015[END_REF], authorities can physically check only a small fraction of it, limiting their capacity to detect illegal activities and security threats. To mitigate the risks, authorities focus on obtaining high quality information on the transported cargo to conduct effective risk assessments.

The 2015 WCO Safe Framework of Standards [START_REF]SAFE Framework of standards to secure and facilitate global trade[END_REF], defines as high-risk the cargo for which either there is inadequate information or reason to deem it as low risk, or is indicated as such by tactical intelligence or a risk-scoring assessment methodology based on security-related data elements. Customs administrations should ensure the interoperability of their IT systems by using the WCO Data Model. This data model identifies the key information elements for the Customs risk-scoring assessment methodologies and systems. Among them, WCO includes the container id, country of origin, place of loading, countries of routing, first port of arrival, place of discharge and date/time of arrival to the first port in Customs territory. The reason is that for goods shipped in containers, their route is equivalent to the container route since they are stuffed into the container (origin of the goods), until they are stripped out of the container (final destination of the goods). Unfortunately, poor quality information regarding the actual route followed by a container is quite common in Customs' declarations.

The logistics' industry and ocean carriers have been using for quite some time electronic records on the events and the whereabouts of the containers they handle. These records, called Container Status Messages (CSM) in WCO SAFE [START_REF]SAFE Framework of standards to secure and facilitate global trade[END_REF], are generated by different participants on the logistics chain (mainly container terminals) and are exchanged electronically to inform carriers, operators and final customers. Unfortunately, this information is often noisy, incomplete and non-standardized, requiring elaborated algorithms to remove the noise and improve the quality of the information. The works in [START_REF] Tsois | Using container status messages to improve targeting of high-risk cargo containers[END_REF][4] [3][2] focus on how CSM records can be processed in order to extract useful information on the routes of the goods and assist the Customs risk management processes. The key element proposed on them to describe the route of the goods is the Container-Trip Information (CTI) [18][4]. In [START_REF] Chahuara | Inferring itineraries of containerized cargo through the application of conditional random fields[END_REF] an algorithm is presented for the computation of CTI records from CSMs based on Conditional Random Fields. Other algorithms, including decision trees, can also be applied to compute the CTI records.

The value of CTI records for Customs risk management is indisputable but it heavily depends on their quality. They are used to detect anomalies in the flow of millions of containers, so the quality of the CTI records extracted can impact severely the effectiveness of the risk analysis. Therefore, it is very important to be able to evaluate the quality of the models used to extract those CTI records. The final aim is to reduce the number of wrongly computed CTI records and their impact on the quality of the risk assessment, allowing a more efficient usage of the resources dedicated to container inspections by the authorities.

This paper proposes a CTI Quality Assessment Framework (CTI-QAF) that contributes to the improvement of the CTI record computation models and facilitates their evaluation. Based on quantitative and qualitative metrics, it provides both a way to evaluate the quality of the CTI computation model output and a way to identify the potentially wrong CTI records. Moreover, the output of the CTI-QAF facilitates the user to identify the CTI properties which are not correctly computed by the model.

The paper is organized as follows. Section 2 describes the related work. Section 3 formalizes the CTI representation to be used and describes the proposed CTI-QAF framework. Section 4 shows how this framework has been applied to assess the quality of four different case studies. Finally, Section 5 concludes the paper and highlights the main future lines.

Related Work

In this work we propose a quality assessment framework for automatically calculated CTI records (CTI-QAF). CTI-QAF provides useful information to improve the assessed CTI computation model and aims at facilitating risk assessment procedures by highlighting potentially wrong computed CTI records.

To be able to apply proposals like [START_REF] Donati | Overview of the contraffic system[END_REF] and [START_REF] Villa | A description logic approach to discover suspicious itineraries from maritime container trajectories[END_REF] to use CTI in Route-based Risk Indicators (RRIs), there is the need to develop algorithms to obtain this information from commonly existing data sources. In [START_REF] Camossi | Detecting anomalous maritime container itineraries for anti-fraud and supply chain security[END_REF], CSMs were used to infer CTI records following a decision-tree like process. In [START_REF] Triepels | Uncovering document fraud in maritime freight transport based on probabilistic classification[END_REF] basic information on the container trip (origin, first port, last port and destination) is extracted from bill of lading documents [START_REF] Levi | International Finance[END_REF]. In [START_REF] Chahuara | Inferring itineraries of containerized cargo through the application of conditional random fields[END_REF] a more sophisticated approach is proposed, extracting information on the different stages of a container trip from CSM data using Conditional Random Fields (see also [START_REF] Lafferty | Conditional random fields: Probabilistic models for segmenting and labeling sequence data[END_REF] or [START_REF] Sutton | An introduction to conditional random fields[END_REF]).

The assessment of the results in the above-mentioned techniques is based on traditional metrics of performance that focus on the generic accuracy of the proposed algorithm. They are not focused on the particularities of the domain and they cannot detect individual problematic cases. In other domains, like in the Part-of-the-speech tagging problem [START_REF] Manning | Part-of-speech tagging from 97% to 100%: Is it time for some linguistics?[END_REF], one can find the usage of quality indicators. In this case, it is useful to know not only the precision of the algorithms when tagging words but also the decision (understood as the number of words non-ambiguously tagged [START_REF] Adda | The grace french part-of-speech tagging evaluation task[END_REF]) or simply the sentence accuracy. Other examples of quality indicators can be also found in the Information Retrieval domain, as it is important to measure the document rank in web searches [7] [10]. Such approaches are efficient in evaluating the overall quality of the information retrieval/extraction process, but they are not designed to evaluate the quality of the resulting data for outlier-detection environments.

In contrast, this paper proposes a new operational framework (CTI-QAF) that uses the CTI key element to formalize the goods route and proposes a set of quantitative (generic) and qualitative (domain specific) metrics to assess the overall quality of the model, the CTI properties and the individual CTI records.

CTI-Quality Assessment Framework

This section describes the proposed CTI-QAF, which is not only able to assess the quality of CTI datasets based on domain-specific metrics, but also capable to highlight potentially problematic CTI records. The outputs of the proposed CTI-QAF help the user to evaluate qualitatively the CTI computation model and to fine tune it by minimizing the number of wrongly computed CTI records.

CTI Formalization

A CTI record codifies the key route information regarding the transportation of goods in a container from an initial location where the goods were stuffed (inserted) into the container till the final destination where the goods were stripped (extracted) from the container. The CTI record splits the route in 5 phases:

-Stuffing phase, when and where got the goods stuffed in the container? -First-load phase, when and where started its maritime transport? -Transshipment phase, when and where was it transshipped (if any)? -Final-discharge phase, when and where ended its maritime transport? -Stripping phase, when and where got the goods stripped from it?

For each phase CTI encodes: a) the main location(s) involved, b) the time period covered by the phase and c) the vessel(s) involved (if any).

Each CTI can be described using the following representation:

cti = (containerId, stuf f ing, loading, transship[], discharging, stripping)
identifying the container and collecting the relevant data of each phase:

-containerID is the id that uniquely identifies a container box -stuffing=(startDate, endDate, location) -loading=(startDate, endDate, location, vessel) transship[] is a (possibly empty) list of records in the form:

transship i = (startDate, endDate, location, vesselIn, vesselOut), with i [1, n], n ≥ 1) -discharging=(startDate, endDate, location, vessel) -stripping=(startDate, endDate, location)
We consider that a CTI record is wrongly calculated if a domain expert based on the same information would not conclude the exact same CTI record, even if the difference is in a single field of the CTI record.

Finding the potentially wrong CTI records out of a huge CTI set is not a trivial task when the computation model has a high precision. Random sampling and manual evaluation by domain experts (ground-truth) is not efficient as one would need to evaluate a very large number of CTI records before identifying enough wrong cases. The framework proposed addresses this problem by using qualitative metrics to identify the set of potentially wrong CTI records and using quantitative metrics to validate the quality of the selected dataset.

The CTI-QAF

The quality assessment upon a large result-set of any model is usually performed by defining one or more ground-truth subsets, which are then compared with the corresponding elements from the large results-set using quantitative metrics. The overall performance of the model can be then approximated by extrapolation. This type of quality assessment can be adequate in cases where an overview of the model's precision is enough for evaluation purposes. However, in cases such as the one discussed in this paper, we must be able to evaluate the expected impact that those wrongly computed CTI records will have on the risk assessment process.

The proposed CTI-QAF framework provides an overall quality assessment based on domain specific qualitative metrics, and additionally provides insight on which aspects need fine-tuning on CTI record computation models.

The workflow, depicted in Figure 1, can be described as follows:

Input: A set of CTI records, CTIset, based on a specified computation model.

Stage A. Do a quantitative analysis on a small sample of CTIset.

A The next section describes the metrics used in the proposed CTI-QAF.

Quantitative and Qualitative Metrics

This section describes in detail the quantitative and qualitative metrics used in the framework in order to assess the input CTI dataset.

Quantitative Metrics. The metrics most commonly used to measure the performance of classification models are based on confusion tables by comparison of the classifiers' results with the ground-truth on a sample set [START_REF] Sokolova | A systematic analysis of performance measures for classification tasks[END_REF]. In CTI-QAF we use Precision, FDR, Recall and F1-Score:

-Precision is the success rate on those elements for which the model assigned a positive class and it is defined as: P recision = T P T P +F P -False discovery rate (FDR) is the opposite of precision: F DR = 1-P recision where: TP is the number of True Positive (the classifiers resulted class coincides with the ground-truth), FP is the amount of False Positives (the classifier does not coincide with the ground-truth) and FN stands for False Negatives (classifier's results that are not included in the ground-truth result set).

Qualitative Metrics

We propose to use several domain-specific metrics aimed to assess the quality of the CTI record computation model.

We split the proposed metrics into heuristic metrics and semantic indicators. The first are based on a set of threshold functions that aim to detect CTI records outliers based on deviations from typical container trip characteristics. The second target semantically incomplete or potentially wrong CTI records, i.e., container trips or trip-phases having semantically incoherent properties.

The heuristic metrics defined below are based on the duration of the different parts of the trip and the number of transshipments.

-Abnormally long trips: Trips with duration equal or greater than 120 days. The semantic indicators defined below assess the structure and quality of the CTI records through functions that highlight semantic inconsistencies.

-Trips with same location for load and discharge: Container trips having the same location as origin and destination.

T Location = (cti.stuf f ing.location == cti.discharging.location)

-Trips with at least one transshipment and having the same vessel at the loading and the discharging phases: During the container trip several transshipments may take place, i.e. the containers are being discharged from the vessel and re-loaded to a different vessel.

T ODV essel =((cti.loading.vessel == cti.discharging.vessel)∧ (|cti.transship| ≥ 1))

-Trips joined with SAD declarations having different origin: In the EU, the Single Administrative Document (SAD) [14] is used in the trade with third countries and for moving non-EU goods within the EU. The SAD declaration corresponding to the trip can be identified through the containerID and the acceptance date of the goods in the EU. Then, to calculate this indicator we are only interested in the field reporting the location of origin.

T SAD = (cti.stuf f ing.location = sad.location)

It is worth mentioning that the proposed framework is expandable and more metrics can be introduced according to the domain, the resources and the desired coverage that has to be achieved regarding the assessment of the model.

Experimental Results

This section presents four different studies derived by using two different CTI record computation models over two different data sources.

We have implemented two different CTI computation models: a rule-based logic deterministic model and a sequence-based probabilistic one. The rule-based model is defined by a complex set of deterministic rules manually induced by an expert (that we denoted as RULES). The second model is obtained by the application of the methodology described in [START_REF] Chahuara | Inferring itineraries of containerized cargo through the application of conditional random fields[END_REF] to construct a machine learning model based on Conditional Random Fields (that we denoted as CRF).

For the application of the proposed methodology two parameters of the CTI-QAF must be set up. For the cases presented in next subsections, we fix a maximum value of 20% for the threshold of quantitative metrics (FDRTh), while for the qualitative indicators' threshold (QLTh) it is set up to 10%.

CTI-QAF applied to RULES models

In this section, CTI-QAF is applied to the CTI records obtained from two CSM data collections (Carriers 1 and 2) by the RULES models. These collections are part of the database of CSMs available within the ConTraffic project [START_REF] Donati | Overview of the contraffic system[END_REF].

Case study 1: Analysis of the performance of the RULES model on Carrier 1. The input data to the CTI-QAF is the set CTIset computed by the RULES model. The number of containers processed for Carrier 1 by RULES was 692,233, corresponding to active containers during the period 2010-2015. The total amount of trips detected was 9,800,207.

The Stage A of the methodology measures quantitatively the performance of the CTIset using a random set of trips. With this aim, 72 CTI records (CTI-Xset) were randomly selected from CTIset. Then, an expert was asked to obtain the correct trips corresponding to those CTI records. A total of 70 ground-truth CTI records (CTI-GT-Xset) were extracted. Based on this, a False Discovery Rate (FDR) of 70.83% was obtained for the CTI-Xset (i.e., 51 wrong trips). As the FDR exceed the threshold for quantitative metrics (FDRth=20%), the CTI-QAF recommends to reconsider the model before continue.

We compute then the Precision, the Recall and the F1-Score metrics for each CTI record's phase. Table 1 compiles the values of these quantitative metrics, showing problems in the proper identification of the discharging and stripping phases. Thus, the methodology provides hints in order to improve the model (e.g., creating new rules to better identify the final phases of the trips).

Case study 2: Analysis of the performance of the RULES model on Carrier 2. In this scenario, we give as input to CTI-QAF the set of CTI records generated by RULES (CTIset) from Carrier 2 data. 404,571 containers were processed (for the period 2010-2015) and a total of 4,631,965 trips were detected. In Stage A, the quantitative validation of CTIset was performed. With this aim, 90 records (CTI-Xset) were randomly selected from CTIset and an expert computed their ground-truth, obtaining 92 CTI records (CTI-GT-Xset).

The FDR for the RULES model was 14.29% (12 wrong trips) and since it does not exceed the FDRth value we proceed to Stage B. The quantitative metrics computed for the different phases returned high values (all above 80%).

In Stage B, the calculation of the qualitative indicators is carried out on the CTIset. Table 2 shows the results for each indicator. As they are all below the QLTh(10% in our case), the assessment continues to the next Stage. In Stage C, the ranked list of potentially wrong CTI records was obtained (RListpwrongCTIset), and its first 90 trips were selected for quantitative evaluation (CTI-RXset). According to the expert, 92 ground-truth CTI records were found (CTI-GT-RXset). The FDR obtained was 96.65%, which means that the metrics for the selection of probably wrong trips have been effective.

Finally, the CTI-QAF can conclude that the model may have its most serious problems in the detection of the transshipment phase (based on the F1-Score obtained in the five phases, see Table 3).

CTI-QAF applied to CRF models

The CTI-QAF was applied to the CTI records obtained by CRF models as well, something that demonstrates its versatility. These models were assessed using Stage A of the CTI-QAF measures quantitatively the performance of the CTIset using a random set of trips. Thus, 69 CTI records (CTI-Xset) were randomly selected from CTIset and an expert computed their ground-truth obtaining 70 CTI records (CTI-GT-Xset). The FDR was 13.18% (i.e., 10 trips wrong), which is lower than the FDRth threshold (i.e., 20%) and hence the assessment of the model can continue.

In Stage B, the qualitative indicators ranged from 0.03% to 3.5%, so they passed the QLth threshold which is set to 10% for all metrics. The ranked list RListpwrongCTIset is then constructed, which can be analyzed by the user in order to further improve the CRF model.

Stage C allows the user to fine tuning the CTI construction model. To do this, the first 69 trips (CTI-RXset) from RListpwrongCTIset were selected and an expert calculated the ground-truth of this set, obtaining 70 CTI records (CTI-GT-RXset). Then, quantitative metrics for CTI records and phases are computed. The FDR was 95.92%. The quantitative metrics obtained for each phase show that the stuffing phase is often wrongly computed (F1-Score=34.88%).

Case study 4: Analysis of the performance of the CRF model on Carrier 2. The data set (CTIset) contained 3,327,561 CTI records, which were computed by CRF on the data from Carrier 2 (described in previous sections).

In Stage A, we obtained the CTI-Xset extracting randomly 93 trips from the CTIset. These CTI records were given to an expert, obtaining a ground-truth set of 92 CTI records (CTI-GT-Xset). The FDR computed was 10.99% (i.e., 12 wrong trips), which allows continuing with the Stage B.

Then, the calculation of the qualitative results was carried out, showing that in many cases the first two phases of the CTI records are not properly detected (T SDLong = 7.31%). However, as all the indicators are below the qualitative threshold, the set RListpwrongCTIset is obtained.

In Stage C, the first 93 trips from RListpwrongCTIset were selected for expert annotation. The quantitative metrics show a FDR of 97.13%. A deeper analysis revealed that the model had serious problems in the detection of the transshipment (F1-Score=16.53%) and stuffing phases (F1-score=23.00%).

Conclusions and Future Work

In this paper, a quality assessment framework for large datasets of Container-Trips Information (CTI) is proposed (CTI-QAF). The framework combines traditional quantitative metrics with domain specific qualitative indicators in order to achieve an overall assessment of the constructed CTI records dataset. The proposed CTI-QAF is able to assess the CTI records and also highlight the aspects of the CTI computation model with more improvement potential.

Incoherent CTI records can easily jeopardize the risk analysis on the goods route. The capacity of CTI-QAF to highlight potentially wrong records can be used to support the risk assessment procedure itself by providing information on the quality of each CTI record. Moreover, knowing the potentially wrong CTI records is useful for analyzing in deep the problems of the computation model.

Two different case studies were presented to demonstrate the application of the CTI-QAF. Two different CTI record computation models have been implemented; a sequence-based probabilistic model and a decision-tree based logic deterministic one. The experimental results involved data from more than 1.1 million containers for two operators (Carrier 1 and Carrier 2), which led to the assessment of more than 23 million trips constructed by the 2 models.

The experimental results shown the effectiveness of CTI-QAF to detect models with low performance at an early stage (see Case Study 1). It is also capable to identify problematic cases, helping to improve the model (see Case Study 4).

With regard to future research lines that would extend the result of this paper, a methodology should be defined to help the users to select the appropriate thresholds to be used in the framework. Moreover, the use of composite indicators could be useful to extend CTI-QAF in two directions. First, they could be used to provide a more effective measure of the quality of a CTI record, facilitating its integration on the risk assessment process. Second, a composite indicator could be developed to provide a quality measure that could be used to directly compare different computation models between them. Finally, it is worth mentioning that the proposed framework is expandable and more qualitative metrics can be introduced depending on the domain, the resources and the desired coverage that needs to be achieved regarding the model assessment.

Fig. 1 .

 1 Fig. 1. Workflow of the CTI-QAF

T--

  Long = (cti.stripping.endDate -cti.stuf f ing.startDate ≥ 120) -Abnormally short trips: Trips with duration equal or shorter than 5 days. T Short = (cti.stripping.endDate -cti.stuf f ing.startDate ≤ 5) -Trips with multiple transshipments: Trips more than 3 transshipments. T M ulti = (|cti.transship| > 3) Trips with prolonged initial phase: Trips having cumulative duration of stuffing and first-load phases equal or greater than 20 days. T SDLong = (cti.loading.endDate -cti.stuf f ing.startDate ≥ 20) Trips with prolonged final phase: Trips having cumulative duration of finaldischarge and stripping phase sequal or greater than 20 days. T ARLong = (cti.stripping.endDate -cti.discharging.startDate ≥ 20)

  .1 Select randomly a set of CTI records (we call that set CTI-Xset). A.2 Let experts create the ground-truth for CTI-Xset (CTI-GT-Xset). A.3 Perform quantitative analysis by computing FDR on the complete CTI records and Precision, Recall and F1-Score on CTI records' phases using CTI-Xset and CTI-GT-Xset (QT-Xresults). A.4 In case the FDR passes a predefined FDRth threshold, further improvement of the model is recommend. Stage B. Perform the qualitative analysis on the entire CTIset. B.1 Apply the qualitative metrics QLM to the CTIset and extract a set of potentially wrong CTI records, pwrongCTIset. B.2 Order decreasingly the pwrongCTIset based on how many metrics signaled each CTI record, producing RListpwrongCTIset. B.3 For each metric, calculate the percentage (QLM i ) of the CTI records evaluated with it that have been detected as suspicious. If for any indicator the percentage is higher than a predefined QLTh threshold, the further improvement of the model is recommend. Stage C. Do a quantitative analysis on a small sample of RListpwrongCTIset. C.1 Select the set of CTI records with highest risk according to the RListp-wrongCTIset and call that set CTI-RXset. C.2 Let experts create the ground-truth for CTI-RXset (CTI-GT-RXset). C.3 Perform quantitative analysis by computing FDR on the complete CTI

records and Precision, Recall and F1-Score on CTI records' phases using CTI-RXset and CTI-GT-RXset (QT-RXresults). The results can show: 1) if the qualitative metrics properly select the RListpwrongCTIset set and, 2) which are the weakness of the CTI computation model if any.

Table 1 .

 1 Quantitative results for stage A of the RULES model for Carrier 1

	RULES model Precision (%) Recall (%) F1-Score (%)
	Stuffing	100.00	88.24	93.75
	First-load	98.49	91.55	94.89
	Transshipment	94.12	94.12	94.12
	Final-discharge	100.00	13.76	24.14
	Stripping	61.11	28.21	28.60

Table 2 .

 2 Qualitative results on the trips obtained by the RULES model for Carrier 2

	RULES model Indicator value (%)
	TLong	0.36
	TShort	0.36
	TMulti	0.05
	TSDLong	0.73
	TARLong	4.78
	TLocation	0.21
	TODVessel	0.09
	TSAD	0.8

Table 3 .

 3 Quantitative results for stage C of the RULES model for Carrier 2Case study 3: Analysis of the performance of the CRF model on Carrier 1. In this case study, the CTIset was obtained after applying a CRF model to data from Carrier 1. 5,970,005 CTI records were computed by this model.

	RULES model Precision (%) Recall (%) F1-Score (%)
	Stuffing	50.59	94.44	65.89
	First-load	65.41	65.41	65.41
	Transshipment	22.22	3.95	6.70
	Final-discharge	66.67	47.69	55.61
	Stripping	50.00	42.86	46.15
	as input the same two different data sources than in previous case studies (see
	Section 4.1).