Petra Hofstedt
email: hofstedt@b-tu.de

Ke Liu
email: liuke@b-tu.de

Sven Löffler
email: sven.loeffler@b-tu.de

Solving the Talent Scheduling Problem by Parallel Constraint Programming

Keywords: Scheduling, Constraint programming, Parallel constraint solving, The Talent scheduling problem

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The talent scheduling problem (TS) is a NP-hard problem originally presented in [START_REF] Cheng | Optimal scheduling in film production to minimize talent hold cost[END_REF], and it is problem No.039 in CSPLib [START_REF] Smith | CSPLib problem 039: The rehearsal problem[END_REF]. The problem can be described as follows: the process of making a film is partitioned into n individual pieces, each of which may require a different subset of the resources such as actors, props and costumes, etc., which can be viewed as a set whose members are m independent resources. Besides, the duration of pieces varies according to the requirement of the film shoot; the cost of different resources is paid at different rates. For a given piece, the cost incurred by one resource is equal to the product of the duration of the piece and the cost of the resource. A feasible solution of a TS problem can be represented as a table (cf. Table 1), in which each column stands for a fixed set of resources required by a piece, while each row represents the demand for the resource for all the pieces of the film. One feasible solution of the TS problem differs from another only because of their different permutations of pieces (columns). By contrast, the order of resources (rows) can always be fixed. A cell of a feasible solution is assigned to one if the resource is required by the piece, otherwise zero. For example, in Table 1, piece 4 requires resource 1 and does not require resource 2; hence, the corresponding cells are 1 and 0 respectively.

The cost of a resource only depends on the interval between the first piece in which it is involved and the last piece in which it is involved, which implies that the idle times of the resource in the interval also need to be paid. In the Piece 4 1 11 10 13 12 3 2 6 8 7 9 5 20 15 14 17 18 16 19 Cost/100 resource 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 10 resource 2 0 1 0 1 1 0 1 1 0 1 1 0 0 1 1 1 1 0 0 0 4 resource 3 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 0 5 resource 4 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 resource 5 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 5 resource 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 40 resource 7 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 4 resource 8 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 20 Duration 1 2 1 2 2 1 1 1 3 1 1 1 1 1 2 1 1 2 1 1 Table 1. A feasible solution for a given TS in [START_REF] Smith | Constraint programming in practice: Scheduling a rehearsal[END_REF]. The Cost and Duration in the last column and the last row stands for the cost per time unit and the duration of the pieces, respectively. The overall cost of this solution is 14,600.

presented paper, if a resource lies idle in such an interval, we call it idle resource. For instance, resource 1 required from piece 4 to piece 8 lies idle for pieces 13 and 12 in the feasible solution shown in Table 1. In this case, resource 1 still needs to be paid due to pieces 13 and 12. Thus, the additional expense incurred by resource 1 is calculated by 10 * 2 + 10 * 1, where 10 is the cost of resource 1, and 2 and 1 are the durations of pieces 13 and 12 respectively. The objective of the TS problem is to find a feasible solution that has the lowest cost incurred by all the idle resources of the feasible solution. Given the above, the TS problem is a typical constraint optimization problem (CSOP).

Consider the making process of a film composed of n pieces and m kinds of resources, d j (j ∈ {1..n}) denotes the duration for piece j, while c i (i ∈ {1..m}) denotes the costs of resource i. Besides, we define a function τ (i, j) as follows:

τ (i, j) = 1 -T (i, j) (1)
where T (i, j) denotes the value in row i and column j of the given feasible solution, and the domain of j is over the interval between the first occurrence of one (f i ) and the last occurrence of one (l i ) in row i. Therefore, the total cost function for all the idle resources in a feasible solution t is:

cost(t) = m i=1 li j=fi τ (i, j) • d j • c i (2)
where t determines f i , l i , and τ (i, j). Therefore, the objective of the TS problem can be stated as finding a feasible solution which has the minimum value of the cost function, which is given by:

M inimize t∈T cost(t) (3)
where T is the total solution space of the given TS problem.

The remaining part of the paper is structured as follows: In Section 2, we introduce the basic notions used in this paper. Then, in Section 3, we gradually describe the modeling approach for the problem in detail. Next, in Section 4, we present an approach to solve the problem in parallel, experimental results are given in Section 5. Finally, we conclude in Section 6.

Preliminaries

Constraint programming (CP) is one of the most powerful techniques to tackle combinatorial problems, generally NP-complete or NP-hard. It employs constraint propagation interleaved with backtrack search. The problem to be solved is expressed through a formal model by using constraints from a rich set of modeling primitives. A constraint network R or constraint satisfaction problem (CSP) is a triple X, D, C , which consists of:

-a finite set of variables X = {x 1 , . . . , x k }, where k is the number of variables in R, -a set of respective finite domains D = {D(x 1 ), . . . , D(x k )}, where D(x i ) is the domain of the variable x i , and -a set of constraints C = {c 1 , ..., c t }, where a constraint c j is a relation defined on the domains of a subset S j of X, c j ⊆ x∈Sj D(X).

A Constraint Satisfaction Optimization Problem X, D, C, f (CSOP) is defined as a CSP with an optimization function f that maps each solution to a numerical value [START_REF] Tsang | Foundations of Constraint Satisfaction[END_REF][START_REF] Rossi | Handbook of constraint programming[END_REF]. Generally, a solution t of a CSOP is a solution of the corresponding CSP, where f (t) is maximal or minimal.

A CSP Model

We are now going to introduce our model in detail. Any feasible solution for the TS problem is a permutation of {1, 2, ...n}, where n is the number of pieces involved in film shooting. Hence, the problem can be viewed as to assign n values to n slots. We define the decision variables as X = {x 1 , x 2 , ..., x n }, each of which has domain {1, 2, ...n}, where x i = j if slot i is assigned to piece j in the sequence. Therefore, the basic constraint of the model can be described as:

∀i, j, x i = x j (4)
where 1 ≤ i < j ≤ n. Constraint 4 can be realized by the allDifferent constraint [START_REF] Lauriere | A language and a program for stating and solving combinatorial problems[END_REF], which is implemented in almost all constraint solvers. Though a TS problem can simply be solved by the allDifferent constraint1 , the search space would be immense even for an small number of pieces in practice, and consequently the problem cannot be solved in a reasonable time frame. For example, the problem with 20 pieces, shown in Table 1, has 20! permutations on the sequence {1..20}, which leads to the fact that to iterate over all the possible permutations is impossible in a reasonable execution time. Therefore, the subsequent constraints we are going to present are used to reduce the search space.

Both a feasible solution and the solution in its reverse order have the same cost function value because the expenses incurred by the idle resources in both solutions are the same. Thus, it is unnecessary to re-explore such search regions for the resolution process. The static symmetry breaking constraint in our model is relatively simple and can be stated as:

x 1 < x n (5)
Obviously, the arithm constraint can be used to express Constraint 5. By imposing Constraint 5, the overall search space is halved. We can also take advantage of the intrinsic characteristics of the data to shrink the search space further. Specifically, if there is a fixed pattern which an optimal solution must contain, a set of optimality constraints can restrict the search space to the solutions containing such fixed pattern. An optimal solution remains unchanged if we exchange two pieces which require the same set of resources. However, as we can see from Table 1, there are some pairs of pieces in which two pieces request almost the same set of resources except for one difference. For example, piece 1 and piece 3 require almost the same resources apart from resource 3. As a result, only resource 3 has an effect on the positional relation among pieces 1, 3 and other pieces in an optimal solution since piece 1 would be treated as the same as piece 3 if they require the same resources. Moreover, piece 3 must be closer to the pieces (e.g., piece 13) requiring resource 3 in an optimal solution, compared to piece 1 because this arrangement of pieces is bound to incur a lower overall cost.

Based on this observation, we can first find all pairs of pieces requiring the same resources but one, and then, find a benchmark resource containing that difference resource, which can be stated as:

| idx i -idx bm | < | idx j -idx bm | (6)
where idx i , idx j , and idx bm are set to the index of the value (piece) i, j, and bm. the set of all idx i , idx j , and idx bm is:

{(i, j, bm) | i = j = bm, |R i ∪R j |-|R i ∩R j |= 1, (R i ∪R j )\(R i ∩R j ) ∈ R bm } (7)
Herein R i , R j , and R bm represent the set of resources required by pieces i, j, and bm (e.g., R 1 = {1, 2}, R 3 = {1, 2, 3}, R 13 = {2, 3, 4}). We denote idx i and idx j as the indices of piece i and piece j, where resources required by them only have one difference, given by

|R i ∪ R j |-|R i ∩ R j |= 1.
The index of bm (idx bm ) is the benchmark for the indices i and j, in which piece bm entails the different resource between resources required by piece i and piece j, which can be expressed as

(R i ∪ R j ) \ (R i ∩ R j ) ∈ R bm .
In other words, the criterion for a benchmark is to select the piece requiring the only different resource between resources required by piece i and piece j.

Take the example mentioned above, piece 13 is the benchmark of pieces 3 and 1, and piece 3 must be closer to the benchmark than piece 1 is. We have the following constraint: | idx 3 -idx 13 |<| idx 1 -idx 13 |. Please note that piece 13 is not the only choice of the benchmark. All the pieces requiring resource 3 (e.g., pieces 2, 8 etc.) can be the benchmark between piece 3 and piece 1.

Constraint 6 can be realized by the inverseChanneling, the distance constraint, and the arithm constraint. For a specific example of Constraint 6, we first use the inverseChanneling constraint to record the indices of the decision variables X by introducing new auxiliary variables IDX, given by:

X[i] = j ⇔ IDX[j] = i (8)
where i, j ∈ {1..n}. Having auxiliary variables IDX, we can control the distance between given values in a output of a sequence easily. For a given value i, j, and bm, Constraint 6 can be converted to:

distance | IDX[i] -IDX[bm] |< distance | IDX[j] -IDX[bm] | (9)
If one implements this model in the Choco solver, two extra auxiliary variables must be introduced in order to store the resulting variables of Constraints 10 and 11 for the distance constraints. Therefore, both sides of the less than sign (<) of the Constaint 9 can be replaced by:

distance | IDX[i] -IDX[bm] |= aux 1 (10) distance | IDX[j] -IDX[bm] |= aux 2 (11)
Then, the arithm constraint can be used to restrict the relation between the two auxiliary variables, given by:

arithm(aux 1 < aux 2 ) (12)
Apparently, one instance of Constraint 6 might reduce more than half of the entire search space because the solutions satisfying | idx i -idx bm |≥| idx jidx bm | are ruled out. In the concrete implementation steps , we first find all the pairs of pieces that only have one different resource, then impose the instances of Constraint 6 for these pairs on the model. Local search (LS), an incomplete search method for finding an optimal solution, is often the method of choice to solve CSOPs. Several ways to combine CP and local search have been proposed in the literature [START_REF] Focacci | Local search and constraint programming[END_REF][START_REF] Pesant | A constraint programming approach to the traveling tournament problem with predefined venues[END_REF]. One way to utilize LS for CP is to freeze a fragment of the variables specified with fixed values and to solve the subproblem defined by the uninstantiated variables. Hence, we should carefully decide which variables should be frozen. For the data shown in Table 1, resources 6 and 8 cost much more than other resources and there is no intersection between pieces requiring resources 6 and the pieces requiring resources 8; therefore, we assume that pieces involving with resource 6 or resource 8 are more likely to arrange together within an optimal solution. Please note that this method does not guarantee that no optimal solution will be ruled out, but the experimental result shows that the best solution we obtained is the same as that one provided in [START_REF] Smith | Constraint programming in practice: Scheduling a rehearsal[END_REF]. In our implementation, we treat piece 6, 7, 8, and 9 as an entirety, say piece 21; and also treat piece 14, 15, 16, 17, and 18 as another entirety, say piece 22. Consequently, the entire search space is reduced from 20! to 13! •5! •4! by this means. Though, the more freezing variables are, the more search space reduction is, there is a trade-off between search space reduction and the optimal solutions possibly contained in the reduced search space. In general, to apply LS to solve TS problem, we should consider to freeze the pieces entailing the highest cost of the resource, the second highest cost of the resources, etc. in turn, and then treat these pieces as entireties. Meanwhile, we also take into account the trade-off we mentioned above. Based on the above analysis, selecting variables for LS are automated:

1. Sort resource based on their cost in descending order. 2. Freeze pieces requiring the current highest cost resource. 3. If the number of frozen pieces can lead the computation ends in predefined execution time (e.g., 20 mins), then the selection procedure stops. Otherwise, we set the next resource in the sorted resources as the current resource and then repeat step 2.

In summary, Constraints 4 and 5, together with constraints entailed by Constraint 6 with LS form the model used to tackle the TS problem.

Solving the TS in Parallel

We would like to briefly introduce Embarrassingly Parallel Search (EPS) [START_REF] Régin | Embarrassingly parallel search[END_REF] in constraint programming. EPS indicates no communication requirement during the solving process. An embarrassingly parallel workload distribution also implies that the independent worker works on distinct data. EPS is well suited for solving the TS problem in parallel since disjoint partial solutions can be easily obtained before the solving process and then mapped to workers. Hence, we use EPS with static decomposition to accelerate the solving process of TS problem.

First, a subset of the decision variables of the model is selected. One viable way is to select the pieces that do not belong to any entirety. In other words, pieces frozen by LS are excluded. For the data in Table 1, we chose a set of pieces P S = {1, 2, 3, 4, 5, 10, 11, 12, 13, 19, 20} to generate partial solutions.

Then, the model presented in Section 3 is applied to the decision variables whose domain is P S and the number of the decision variables is equivalent to the cardinality of the set P S. The model used to generate the partial solutions includes Constraints 4, 5, and constraints entailed by Constraint 6. Please recall that all the pairs of pieces that only have one different resource are found, and then we impose the instances of Constraint 6 for these pairs on the model in sequential version. In the parallel version, the instances of Constraint 6 would not be entailed by the pieces not contained in P S when generating the partial solutions. In doing so, there are two advantages: First, the partial solutions can be generated in a reasonable time for the next step; second, solutions that cannot be extended to an optimal solution wouldn't be generated.

After generating the partial solutions, each worker receives the same number of partial solutions and works on its own independent partial solutions in parallel. Embarrassingly parallel execution works as follows on each worker:

1. The entireties are inserted into all possible positions of a partial solution so that all possible permutations with entireties for all pieces are generated. 2. The cost function (Equation 2) is evaluated for each permutation. The branch-and-bound algorithm is used here to avoid visiting the nodes that are impossible to be extended as an optimal solution.

It is worth noting that P S doesn't include all the pairs of pieces that only have one different resource. Thus, in order to shrink the search space for each worker, the instances of Constraints 6 are entailed by the remaining part of such pairs of pieces. Also note that there is no communication between workers, which means no communication cost; on the other hand, a new lower bound discovered by a worker cannot be used by other workers for improving their current resolution. Obviously, there is a trade-off between sharing lower bounds and communication. We decided not to use communication, because, for the sake of scalability of the parallel algorithm, more workers and smaller sub-problems might lead to more expensive communication cost and the uselessness of sharing lower bound since the resolution time of the sub-problems may be short.

The final step is to obtain the permutation with the smallest value of the cost function.

Numerical Results

In order to confirm our theoretical discussion, we implemented the model as described in Section 3 and Section 4 and its parallel version in the Choco Solver 4.0.6 [START_REF] Prud'homme | Choco Documentation[END_REF] with JDK version 9.0.1. All experiments were performed on a computer with an Intel i7-3720QM CPU, 2.60GHz with 4 physical and 8 logical cores, and 8 GB DDR3 memory running Ubuntu 17.10.

All tricks of solving TS problem in a reasonable execution time is essentially to reduce search space. The constraints regarding search space reduction allowed us only to evaluate 1,027,403,520 out of 20! feasible solutions, reducing approximately 99.99% of the total search space. The following experiment was carried out to test the effectiveness of the search space reduction sequentially and its parallel version.

As can be seen from Table 2, the efficiency dropped rapidly as the number of workers increased from 4 to 8. Theoretically, we would not have expected this result since no communication is required. Thus, in order to eliminate the factors such as the limit number of physical cores and the limited size of the cache, we halved the partial solutions, and executed the first part of the partial solutions and the second part of partial solution by using 4 workers in turn. As a result, the speedup of 8 workers can be 5.42 ( 7.528 1.389 ), and its efficiency is 0.68.

The execution time of the sequential part for generating the partial solutions was 25 seconds in the parallel version; therefore, by using Amdahl's law [START_REF] Amdahl | Validity of the single processor approach to achieving large scale computing capabilities[END_REF] we can calculate that the theoretical speedup of our approach is around 18.1 for the given data. Additionally, one benefit of parallel solving for the TS is that we may obtain different optimal solutions in a shorter time. For the problem shown in Table 1, we obtained the following optimal solutions: 4. Optimal solutions in order of pieces with cost 14,600

Conclusion

We have presented the model for TS problem, as well as utilizing data-level parallelism to speedup the execution. Besides, our approach also employs the local search to reduce the search space. The experimental results indicate that embarrassingly parallel search can be an appropriate choice to solve such constraint optimization problems.

Nevertheless, we believe there is still a potential to improve the performance of our approach. Although it has performed well, Constraint 6 and the dual variables could be replaced by a tailored constraint that can realize the functional requirements of Constraint 6 and use only one constraint instead of the distance, the arithm constraint, and the ifThen constraint for the dual variables. Besides, the theoretical speedup can still be improved for larger instances though

Table 2 .

 2 Solving the TS on a multi-core computer

	Number of Workers	1	2	4	8
	Execution time (s) 451.68 250.56 137.64 119.82
	Speedup	1	1.8	3.28	3.77
	Efficiency	1	0.9	0.82	0.47125
	Four Workers		First Part Second Part
	Execution time (s)	83.34	81.42

Table 3 .

 3 Use 4 workers to calculate the first part and second part in turn.

The names of the constraints used in this paper are consistent with the names of constraints used in the Choco Solver[START_REF] Prud'homme | Choco Documentation[END_REF].

it is limited for the given data. Finally, we would like to explore the use of our parallel approach to accelerate the resolution of other CSPs and CSOPs in the future.


Andres Ovidio

Restrepo Rodriguez
email: aorestrepor@correo.udistrital.edu.co

Daniel Esteban Casas Mateus

Paulo Alonso Gaona-García

Adriana Gomez Acosta

Carlos Enrique

Montenegro Marin

Daniel Esteban Casas
email: decasasm@correo.udistrital.edu.co

Paulo Alonso Gaona
email: pagaonag@udistrital.edu.co

Adriana Gomez
email: acgomez@funsanmateo.edu.co

Carlos Enrique Montenegro
email: cemontenegrom@udistrital.edu.co

Segmentation Methods for Image Classification Using a Convolutional Neural Network on AR-Sandbox

Keywords: Canny Edge Detector, Color-space, Convolutional Neural Networks, Image processing, Segmentation, Threshold, Vowels

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The AR-Sandbox is an augmented reality device, which, through the projection of digital topographic maps, allows to close the gap between 2D and 3D visualization, improving the thought and spatial modeling skills. This device has a large field of action, providing support and revolutionizing the traditional paradigm of education in early childhood and in medicine such as rehabilitation through motor therapy [START_REF] Woods | Pilot Study Using the Augmented Reality Sandbox to Teach Topographic Maps and Surficial Processes in Introductory Geology Labs[END_REF], for this, it is important that the AR-Sandbox provide feedback of the activity carried out.

The image recognition on the AR-Sandbox presents a high degree of difficulty, since when capturing the image from this device a high level of noise is presented, due to the multiple pigmentations according to the level of the sand, exposed by the nature of this augmented reality tool. The AR-Sandbox makes use of a Kinect and a projector to make colorful representations in 3D on a sandbox [START_REF] Giorgis | Instructor-Led Approach to Integrating an Augmented Reality Sandbox into a Large-Enrollment Introductory Geoscience Course for Nonmajors Produces No Gains[END_REF]. This article presents preliminary results for model implementation results of a convolution neural network (CNN), as an image recognition technique on the AR-Sandbox, evaluating the application of three segmentation methods to the training dataset and the test dataset, for the training and prediction phase, in order to determine which segmentation method best fits the characteristics of the AR-Sandbox.

Background

Previous image processing besides image recognition through convolutional neural networks have had a large number of applications, which its goal is to optimize pattern recognition [START_REF] Hijazi | Using Convolutional Neural Networks for Image Recognition[END_REF]. From different computer vision techniques, convolutional neural networks have been in a continuous growth since their creation [START_REF] Neha | An Analysis of Convolutional Neural Networks For Image Classification[END_REF].

Image segmentation methods are used to optimize the analysis and interpretation of images through a process depending on the segments of each image, there are a variety of algorithms and methods with advantages and disadvantages depending on the features of the image, these methods are classified depending on pixel intensity value, color, texture, etc. [START_REF] Kaur | Various Image Segmentation Techniques: A Review[END_REF]. Authors like [START_REF] Raj | Hardware realization of canny edge detection algorithm for underwater image segmentation using field programmable gate arrays[END_REF] use image segmentation in order to get information for underwater images, which are difficult to get and analyze due to environmental conditions, for these reasons, canny edge detector algorithm is used because it gave localization and response with extreme accuracy and it has a superior capability under noise conditions. Finally, in previous studies, [START_REF] Restrepo Rodriguez | Hyperparameter Optimization for Image Recognition over an AR-Sandbox Based on Convolutional Neural Networks Applying a Previous Phase of Segmentation by Color-Space[END_REF] where the purpose of this research was to establish a model of a CNN for the classification of geometric figures by optimizing hyperparameters using random search, evaluating the impact of the implementation of a previous phase of colorspace segmentation to a set of tests captured from the AR-Sandbox, authors find that using the proposed method, an average decrease of 39.45% to a function of loss and an increase of 14.83% on average in the percentage of correct answers is presented.

Based on this panorama, the present study intends to carry out the recognition of images by the means of deep learning techniques, such as convolutional neural networks and image processing by three segmentation methods, with the purpose of determining the performance variation of a convolutional neural network, applying these segmentation methods the test and training datasets. In the next section, the selected study scenario is presented.

General approach

Figure 1, presents the general approach of this study, which has as its starting point a base model of a convolutional neural network. The study starts from previous results of [START_REF] Restrepo Rodriguez | Hyperparameter Optimization for Image Recognition over an AR-Sandbox Based on Convolutional Neural Networks Applying a Previous Phase of Segmentation by Color-Space[END_REF] that had the purpose of creating contributions towards image recognition based on immersive techniques, through deep learning using CNN, hyperparameters optimization and image processing. From this base model, CNN is trained, using a training dataset composed of a series of vowels (A, E, I, O, U), which will be previously put through image processing, trough Python and OpenCV, using three segmentation methods, Canny Edge Detector [START_REF] Raj | Hardware realization of canny edge detection algorithm for underwater image segmentation using field programmable gate arrays[END_REF], color-space segmentation [START_REF] Restrepo Rodriguez | Hyperparameter Optimization for Image Recognition over an AR-Sandbox Based on Convolutional Neural Networks Applying a Previous Phase of Segmentation by Color-Space[END_REF] and Threshold [START_REF] Rui | Threshold segmentation algorithm for automatic extraction of cerebral vessels from brain magnetic resonance angiography images[END_REF]. When obtaining the trained model, we proceed to make the model evaluation, making use of a test dataset, which was acquired in its entirety through the AR-Sandbox. The same segmentation method applied in the training phase is applied previously to the test dataset, for the evaluation phase of the model the following evaluation items are defined: Confusion Matrix, and the ROC Curves.

CNN base model

In order to carry out the recognition and classification of vowels from the AR-Sandbox, a model of a convolutional neural network was selected [START_REF] Restrepo Rodriguez | Hyperparameter Optimization for Image Recognition over an AR-Sandbox Based on Convolutional Neural Networks Applying a Previous Phase of Segmentation by Color-Space[END_REF], where the definition of a base model of a CNN was carried out, in order to perform the hyperparameters optimization by random search, defining a dictionary of hyperparameters. The model selected was for the recognition of geometric figures acquired from the AR-Sandbox. The selected model is presented in figure 2.

Figure 2. CNN model

As a first step, the acquisition of images was done through the AR-Sandbox, which aims to support early education and rehabilitation in motor therapy, in order to change the traditional paradigm of exercises. Next, the segmentation methods and their process are presented.

Canny Edge Detector

As a first step, we proceed to select the original image, later the image has to be resized, in order to apply Gaussian filter and sobel procedure, finally, Non maximum suppression and hysteresis are applied to image [START_REF] Opencv | Canny Edge Detector[END_REF]. Figure 3 presents the process.

Color-space

As a first instance, the target color and a range of close colors are selected, in order to separate the colors in the image, therefore, the values within these parameters are painted of white color and the rest of a black color, this is called mask, which provides a contrast in the image. The white part of the mask will take the green color while the rest of the image is still black. Figure 4 presents the process.

Threshold

As a first step, the original selected image must be passed to grayscale, later you have to apply the threshold function using Otsu binarization [START_REF] Mordvintsev | Image Segmentation with Watershed Algorithm[END_REF]. Figure 5 presents the process.

Similarity Indexes

In order to obtain the probability of similarity between the original image and the segmented image using the methods mentioned above, we proceed to calculate the coefficients of Jaccard and Sørensen-Dice, making use of Matlab, where the individual coefficient of each image is obtained in order to obtain the average value of each of the coefficients for each segmentation method. The obtained coefficients are presented in Table 1.

Results

In this section the results are shown, in the first part the results show the ROC curves of the used test dataset and finally the models are compared by success rate obtained from the confusion matrices of each segmentation method.

To acquire the images and make the test dataset of images which are made in the AR-Sandbox, it was necessary to convene a group of ten people who made a total of 15 images each, which are 3 for each class.

ROC curves

Figure 6A shows the ROC curves for the dataset with color-space, in Figure 6B the ROC curve for the dataset with Canny Edge Detector is presented, in Figure 6C the curve for the dataset with Threshold and Figure 6D the curve without a segmentation method. Each of these figures has seven curves which are areas under the curve of the micro and macro level of the ROC curve, in addition the curves corresponding to each vowel represented by a number from 1 to 5 in alphabetical order.

Confusion matrix

With the help of the Python sk-learn library an algorithm is implemented for the creation of confusion matrices that will show the success rate of each method with respect to the test dataset. Table 2, shows the percentage of success rate of each segmentation method.

Analysis of results

Regarding the confusion matrix, the highlighted segmentation method is color-space with 92.67% having a difference of 5.34% with Canny Edge Detector, 34.67% with Threshold and 57.33% without segmentation method.

As evidenced in figure 6, the model that stands out with respect to the AUC, making the average between micro average and macro average, is the Color-space model with a 0.99 performance, followed by Canny Edge Detector with a 0, 97, Threshold with 0.835 and finally the model without segmentation method with 0.73. In addition, it can be seen that the model with color-space segmentation increases the precision value by 0.26. Table 3 presents a detailed analysis by vowel.

Conclusions

From the analysis presented and taking as criteria the ROC curve and confusion matrix, it was determined that the segmentation method with the highest performance for the recognition of vowels on CNN is Color-space, given the multiple pigmentation characteristics of the AR-Sandbox, the choice of a target color represents a greater percentage of correct answers in its prediction phase. By applying the same segmentation method in the training and prediction phase, positive contribution is made in the identification and extraction of characteristics for the classification of images, as mentioned by the authors in [START_REF] Restrepo Rodriguez | Hyperparameter Optimization for Image Recognition over an AR-Sandbox Based on Convolutional Neural Networks Applying a Previous Phase of Segmentation by Color-Space[END_REF].

On the other hand, it is determined that the similarity indexes are not decisive for the choice of a segmentation method for the recognition of images by CNN in an AR-Sandbox, since as can be seen the Canny Edge Detector method presents the lowest coefficients of similarity contradicting the results of confusion matrices and ROC curves that show a high performance of the CNN trained with this segmentation method.

From a model with a high level of precision for objects identification from AR-Sandbox, one can begin to expand the spectrum of functionality and use this augmented reality device in early education and rehabilitation.

According to the above, the combination of multimedia, deep learning together with image processing provides an opportunity to perform a multidisciplinary work in parallel with traditional paradigms in the fields of education and medicine.

Figure 1 .

 1 Figure 1. General approach

Figure 3 .

 3 Figure 3. Canny Edge Detector segmentation

Figure 4 .

 4 Figure 4. Color-space segmentation

Figure 5 .

 5 Figure 5. Threshold segmentation

Figure 6 .

 6 Figure 6. ROC curves.

Table 1 .

 1 Similarity indexes

	Method	Jaccard	Index Sorensen-Dice
	Canny	0.3239	0.4356
	Color-space	0.7143	0.7801
	Threshold	0.4869	0.6244

Table 2 .

 2 Success Rate segmentation methods

		Method
	Without Segmentation Canny Color-space Threshold
	Success Rate 57.33%	87.33% 92.67%	58.00%

Table 3 .

 3 Specific analysis: ROC curve

	Method		A	E	Vowel I	O	U
	Canny		0,95 0,99 0,96 0,98 0,99
	Color-Space Threshold	AUC	0,98 1,00 0,98 0,99 0,99 0,89 0,99 0,92 0,59 0,84
	Without segmentation		0.87 0.71 0.92 0.72 0.82


Ιοannis Schoinas

Christos Tjortjis

MuSIF: A Product Recommendation System Based on Multi-source Implicit Feedback

Keywords: Implicit Feedback (IF), Collaborative Filtering (CF), Recommendation Systems (RS), Matrix Factorization (MF), Association Rule Mining (ARM), Artificial Intelligence Applications

Collaborative Filtering (CF) is a well-established method in Recommendation Systems. Recent research focuses on extracting recommendations also based on implicitly gathered information. Implicit Feedback (IF) systems present several new challenges that need to be addressed. This paper reports on MuSIF, a product recommendation system based solely on IF. MuSIF incorporates CF with Matrix Factorization and Association Rule Mining. It implements a hybrid recommendation algorithm in a way that different methods can be used to increase accuracy. In addition, it is equipped with a new method to increase the accuracy of matrix factorization algorithms via initialization of factor vectors, which, as far as we know, is tested for the first time in an implicit modelbased CF approach. Moreover, it includes methods for addressing data sparsity, a major issue for many recommendation engines. Evaluation shows that the proposed methodology is promising and can benefit customers and e-shop owners with personalization in real world scenarios

Introduction

Content Based Filtering (CBF) systems create customer profiles based on their preferences for various product characteristics or their past behavior [START_REF] Pazzani | Content-Based Recommendation Systems[END_REF] [START_REF] Gerogiannis | Personalised Fuzzy Recommendation for High Involvement Products[END_REF]. They aim in matching the customer to the items with characteristics closer to their preferences [START_REF] Ricci | Recommender Systems Handbook[END_REF].

Collaborative Filtering (CF) systems on the other hand, exploit user ratings to create communities of users or items with similar characteristics, since users with similar tastes tend to prefer the same items [START_REF] Sivapalan | Recommender Systems in E-Commerce[END_REF] [5] [START_REF] Linden | Amazon. com recommendations: Item-to-item collaborative filtering[END_REF] [7] [START_REF] Pathan | Product Recommendations System Survey[END_REF]. In both cases user input is required. In CBF customers need to create their profiles and explicitly state which attributes they prefer. CF algorithms require user ratings to extract communities. However, customers often do not create profiles or rate items they preferred or liked.

In other cases, system designers might aim to offer a simpler experience to customers, where rating system and preference profiling burdens and makes the process more complex. For such cases explicitly provided information is not available and research has focused in gathering valuable knowledge from Implicit Feedback (IF) [START_REF] Jawaheer | Comparison of implicit and explicit feedback from an online music recommendation service[END_REF]. IF is provided by monitoring user behaviour with extensive search and focus is given to purchase history. Though using solely purchase history to create recommendations limits the number of users and items available for recommendations, which can be created just for users who have previously bought any items and only for items that also have been previously bought by someone. This reduces the coverage of a RS, which is an important criterion regarding such systems' performance.

In addition to customer purchases, there are other sources that depict user preferences. Viewing, searching or other domain specific inter-actions can be used to infer customer interests. Purchase history and other implicit sources depict different levels of interest. The act of purchasing shows that the customer was interested enough to purchase this item, though it does not mean that he or she was happy with this choice. In addition, repeated viewing of a specific item shows a definite interest, but not as strong as actually buying it. Thus, different sources should be considered.

Our aim is to adequately infer users' preferences from their behavior. We propose here MuSIF, a Product Recommendation System Based on Multi-source IF. In contrast to most research on IF systems, we utilize different sources of information in addition to purchase history and try to construct an estimate of user preference towards an item [START_REF] Hu | Collaborative Filtering for Implicit Feedback Datasets[END_REF], [START_REF] Johnson | Logistic Matrix Factorization for Implicit Feedback Data[END_REF], [START_REF] Choi | A hybrid online-product recommendation system: Combining implicit rating-based collaborative filtering and sequential pattern analysis[END_REF], [START_REF] Baltrunas | Towards Time-Dependant Recommendation based on Implicit Feedback[END_REF], [START_REF] Bahrainian | Implementation of an Intelligent Product Recommender System in an e-Store[END_REF] [15], [START_REF] Delporte | Socially Enabled Preference Learning from Implicit Feedback Data[END_REF].The ultimate goal would be to construct an equation that includes a vast number of implicit sources and accurately models user preference. Research exists for systems that use a combination of implicit and explicit feedback [START_REF] Gábor | Applications of the Conjugate Gradient Method for Implicit Feedback Collaborative Filtering[END_REF] [18] [START_REF] Pilászy | Fast ALS-based matrix factorization for explicit and implicit feedback datasets[END_REF] or even knowledge derived from users social network [START_REF] Delporte | Socially Enabled Preference Learning from Implicit Feedback Data[END_REF], though we focus on a purely implicit approach with knowledge derived from user item interactions. Another issue present in many RS is data sparsity, especially for systems using explicit feedback or systems with a large volume of customers and items. In these cases, customers rate and interact with a small number of items, hindering the performance of recommender systems. Especially in CF systems, it is difficult to recommend items with low to no user interaction; like-wise, is difficult to produce recommendations for customers with very few rates or little interaction history. In our methodology we create a denser user item matrix by enhancing it with the help of Association Rule Mining (ARM). Association Rules (AR) are extracted based on purchase history and fill in missing values where needed. Aiming to further increase the accuracy of the algorithm, we proceed to apply another optimization technique. The main CF algorithm used is a Matrix Factorization (MF) technique, where we find the latent factor matrices of the user item matrix via optimization. For increasing the performance of our method, we initialize the latent factors prior to using the main algorithm by decomposing the user item matrix with the Singular Value Decomposition (SVD) algorithm. The remaining of the paper discusses related work in section 2, The proposed method and its key components are detailed in section 3. Section 4 presents results and evaluation. Finally, section 5 concludes the paper with directions for further work.

Related Work

Research regarding IF is not as popular as explicit recommenders. However, there are a lot of cases where algorithms use IF exclusively or in combination with other types of sources [START_REF] Dutta | Offering A Product Recommendation System in Ecommerce[END_REF]. CF for IF Datasets, which is the backbone of our research, presents an algorithm based solely in IF [10] [11]. The methodology is categorized as CF, and more specifically as MF. The idea is to construct a user item matrix, similar to explicitly created matrix of user-item ratings. Though in this case the matrix consists of estimates of preference induced by the customers views instead of ratings. Preference is set to 1 for each show the user has watched. Notating users with u, items with i, preference with p and the observed times a user watched a show as r, the preference is given by:

𝑝 = 1 𝑟 > 0 0 𝑟 = 0 (1)
The number of times a viewer watched a show depicts their interest towards that show. To model this behaviour confidence is constructed using a predefined constant that sets the increase rate for each view. Notating confidence with c and the predefined constant with a, confidence is given by:

𝑐 = 1 + 𝑎 𝑟 (2)
Factors are extracted minimizing the following cost function:

𝑚𝑖𝑛 , = ∑ 𝑐 (𝑝 -𝑥 𝑦 ) + 𝜆(∑ ‖𝑥 ‖ + ∑ ‖𝑦 ‖ ) , (3)
In addition, Alternating the Least Squares (ALS) method is used for optimization [START_REF] Koren | Matrix Factorization Techniques for Recommender Systems[END_REF]. The idea is to keep one vector static in each iteration and re-compute the other, lowering the value of the cost function while in the next iteration to alternate the static and re-computed vectors. After computing the user and item vectors, xu and yi respectively, the predicted user preference for a specific item is given by the dot product of their factor vectors.

𝑝̂ = 𝑥 𝑦

The proposed implementation performs well and sets the ground rules for dealing with IF recommenders. Viewing a show in the specific context is the same as purchasing a product. Repeated purchase of a specific product is a very strong indication of preference. Thus, it is less prone to misinterpretation and more accurate. Though, in the proposed algorithm only a single source of IF is used, which limits recommendations to items that have actually been viewed. A transformation of the described methodology is presented in [START_REF] Gerogiannis | Personalised Fuzzy Recommendation for High Involvement Products[END_REF]. This paper demonstrates different ways for MF and adopts a probabilistic approach. Like the approach in [START_REF] Breese | Empirical Analysis of Predictive Algorithms for Collaborative Filtering[END_REF], it is concerned with an implicit user item matrix that shows preference between user-item pairs. In this case, the latent factor matrices are calculated using a different cost function and the aim is to maximize it with alternating gradient ascent procedure.

𝑝(𝑙 |𝑥 , 𝑦 , 𝛽 , 𝛽 ) = (5)
The research in [START_REF] Choi | A hybrid online-product recommendation system: Combining implicit rating-based collaborative filtering and sequential pattern analysis[END_REF] is another example of IF CF which is also based only on transaction info. Though in this case sequence pattern analysis is included during the construction of the user item matrix, which will be used for the recommendations. The algorithm calculates a preference score derived from transactions, and a preference score derived from sequence pattern analysis on transactions. The aggregation of both scores forms the final preference score of the user item pairs. The preference score using transactions is calculated with the following equations:

𝐴𝑃 = ln + 1 (6) 𝑅𝑃 = ∈ ( ) (7)
𝐼𝑅 = 𝑟𝑜𝑢𝑛𝑑 (5 𝑅𝑃 ) (8)
Then the system proceeds with the prediction of the user preference using ratings from the k most similar users. The prediction is computed with:

𝐶𝐹𝑃𝑃 = 𝑅 + ∑ | ( , ) | ∑ 𝑠𝑖𝑚(𝑎, 𝑏)(𝑅 -𝑅 ) (9)
For the sequential pattern analysis, the algorithm creates sequences based on the transaction of all the other customers. Then it proceeds with comparing the derived sequences with the transaction's subsequences of the target customer. Finally, the score derived from the analysis is found from the equation:

𝑆𝑃𝐴𝑃𝑃 = ∑ 𝑆𝑢𝑝𝑝𝑜𝑟𝑡 ∈ (10)
In this equation, the set of the user's subsequences is denoted as SUB, and the support of the item in the specific subsequence as Support s. The final preference score FPP for the user item pair is calculated using the normalized CFPP and SPAPP and the constant a as weight in the following manner:

𝐹𝑃𝑃 = 𝑎 𝑁𝐶𝐹𝑃𝑃 + (1 -𝑎)𝑁𝑆𝑃𝐴𝑃𝑃 (11)
During evaluation the algorithm was tested against CF and sequential pattern analysis with regards to precision, recall and F1. The results show that the use of implicit rating is an acceptable solution to insufficient explicit feedback. In this example there is a combination of IF CF algorithm with sequential pattern analysis. Sequential pattern and market basket analysis are well established research topics in data mining regarding transactions. Since IF datasets contain information regarding transactions, they make such techniques important tools for increasing accuracy and performance. Another interesting approach aiming at increasing the performance of MF techniques is via initialization of factor matrices. In CF with initialized factor matrices [START_REF] Guo | Resolving Data Sparsity by Multitype Auxiliary Implicit Feedback for Recommender Systems[END_REF] offers a methodology to improve approaches such as the one used in our implementation and those in papers [START_REF] Hu | Collaborative Filtering for Implicit Feedback Datasets[END_REF], [START_REF] Johnson | Logistic Matrix Factorization for Implicit Feedback Data[END_REF] where they randomly initialize the user item factor matrices and implement a repeated optimization method on these matrices. In these cases, random initialization is not the optimal method. In the first phase of the methodology, latent user and item factor matrices are extracted from the user-item matrix. The initialization method consists of the following steps. First additional values are being filled in the original user-item matrices, where the rating is unknown. This is accomplished by using a method such as averaging the known user ratings for the specific item. Eight approaches regarding filling the unknown rating values prior to SVD have been tested. These include using the median rating of user, the median rating of item, the total median of items, the average of user and item median, the average ratings of the user, the average ratings of the item, total average of all ratings and the average from user and item averages.

For evaluation the proposed approach was tested against a randomly initialized matrices MF algorithm with the same optimization method. Results show that the method improved the system, while requiring less iterations to find the matrices with the least error. This led to increased execution time, even double time in some cases. The approach describes a method of increasing accuracy and overall performance for discovering latent factor models. What should be noted though is that taking average of ratings for filling the user-item matrix before SVD requires further examination and testing over other possible alternatives that could further increase performance.

Method

Our methodology is a combination of three main approaches. The main algorithm we use is a variation of the IF CF using ALS. In a similar fashion, we construct a user item matrix of inferred preference induced by monitoring customer behavior. Though in our case we utilize three different sources of implicit feedback. In addition, we combine the algorithm with ARM to address the data sparsity issue present in our dataset. In the third part we aim at further increasing performance by initializing user and item factor vectors

Implicit Matrix Factorization (MF)

The main algorithm of our system is an implementation based on the work of CF for IF dataset [START_REF] Breese | Empirical Analysis of Predictive Algorithms for Collaborative Filtering[END_REF][START_REF] Baltrunas | Towards Time-Dependant Recommendation based on Implicit Feedback[END_REF]. For the implementation of the algorithm, the raw data need to be transformed in a user-item matrix with values representing the implicit rating associated with the pair. Our dataset provides observations over different visitors' behavior. Thus, the first stage of the algorithm involves preprocessing raw data to transform them in a user-item matrix.

In CF for IF Datasets a user's interest towards a show is inferred by the number of times they viewed the show. In our case instead of a single implicit source we consider three. Thus, interaction score includes three different observations and is given by:

𝑟 = 𝑣 + 𝑏 + 𝑡 (12)
The number of times the visitor viewed the item is notated as v, the number of times the visitor added the item to their cart is notated as b, and the number of times the visitor bought the item as t.

During the purchase process the visitor usually navigates through several items before deciding. While viewing products, it is possible that one sees products that they will then exclude for several reasons; one being that they did not like them. Viewing items, even though being an indication that the visitor wanted to learn more about them, does not always mean that the customer prefers it. On the other hand, "add to cart" and transaction are stronger indications of preference, since the visitor did decide to purchase them. Thus, the three observations have different weight regarding visitor's preference over an item. Taking into consideration the above weighting of the observations is required, thus the interaction score is transformed into:

𝑟 = 𝑣 + 𝑏 * 𝑏 + 𝑡 * 𝑡 (13)
As tweight we denote the transaction weight and as bweight the "add to cart" weight. After cross validation we defined transaction weight to be equal to 100, while "add to cart" to be 50. We considered not giving additional weight to "add to cart" since the customer is required to proceed to it if he wants to buy it, and this intent is captured by the "transaction" interaction. Finally, "add to cart" was included because there might be cases where the customer added the item to the cart, but did not complete the transaction. This is also a strong indication of preference, though not as strong as actually buying it.

In the proposed algorithm, preference is a binary variable which takes the value of 1 for the cases where a user interacted with an item and 0 for the rest. With rui we notate the interaction score for a user u with an item i.

𝑝 = 1 𝑟 > 0 0 𝑟 = 0 (14)
Also, in our case, it is needed to consider differences in preference level and so a confidence level is defined. Similarly, repetition of interaction is considered as a strong indication of preference. Confidence of each user item pair is given by:

𝑐 = 1 + 𝑎( 𝑟 ) (15)
A predefined constant used as scale regulator is notated as a. 40 was found after validation to perform well in our model. After creating the user item matrix, the next phase of the algorithm is to calculate the user item factor vectors. The system proceeds with calculating the vectors by minimizing the cost function proposed in [START_REF] Breese | Empirical Analysis of Predictive Algorithms for Collaborative Filtering[END_REF]:

min , ∑ 𝑐 (𝑝 -𝑥 𝑦 ) + 𝜆 (∑ ‖𝑥 ‖ + ∑ ‖𝑦 ‖ ) , (16)
As x is denoted the user factor vector and as y the item factor vector. The 𝜆 (∑ ‖𝑥 ‖ + ∑ ‖𝑦 ‖ )is used to prevent overfitting. After having calculated the factor vectors, we can get a prediction for the user-item pair by calculating the dot product of their factor vectors.

𝑟𝑒𝑐 = 𝑥 . 𝑦 recui ( 17
)
is the predicted preference score for a specific user towards a specific item. The system proceeds with ranking all products for a user, and a list ordered by preference can be extracted and used as recommendations.

Association Rule Mining (ARM)

AR in our system are used for enhancing the CF algorithm and addressing the data sparsity problem. The main algorithm calculates the user item factor vectors based on the user item matrix. The denser the matrix is the more accurate the results become.

Similarly to [START_REF] Schafer | Collaborative Filtering Recommender Systems[END_REF] ARM is used in order to make the user-item preference matrix denser by extracting rules and filling missing values accordingly. We used AR extracted by Apriori considering all the transactions for each user [START_REF] Agarwal | Fast algorithms for mining association rules[END_REF]. The rules provide us with information about items that tend to be bought together.

The system fills the matrix with specific user items, where the user has bought the base item, but not the appended item. The score assigned to the previously unassigned user item value takes is derived from the score of the base item. In this way we can also model cases where the user bought the base item more than once. In addition, since confidence provides information about the correlation between base and appended items, this should also be considered in calculating missing values. Thus, the score is equal to that of base item times the confidence of the rule. Notating user with u, items with i, ia are the appended items and ib are the base items and nr is a newly assigned rating score that was previously absent for the specific user item pair.

𝑛𝑟 = 𝑟 * 𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒 (18)

After enhancing the user-item score the system proceeds by discovering the user item factor vectors of the enhanced matrix and the remaining phases of the recommendation system.

Initializing user item factor vectors

In the last phase of our approach, we aim at further increasing the performance of the system by initializing the factor vector prior to ALS optimization. The methodology presented in [START_REF] Hu | Collaborative Filtering for Implicit Feedback Datasets[END_REF], [START_REF] Johnson | Logistic Matrix Factorization for Implicit Feedback Data[END_REF] uses random values for initialization of the vectors. Following the research in [START_REF] Guo | Resolving Data Sparsity by Multitype Auxiliary Implicit Feedback for Recommender Systems[END_REF] we proceed by decomposing the initial user item matrix using the SVD algorithm. In contrast to this method, we did not proceed by filling the missing values with averages. Average filling technique is a stochastic approach and further research is required to discover a more suitable technique. A flowchart for our approach is shown in Fig. 1.

Evaluation

For the evaluation of the system we tested the algorithm on various transformations of the user-item matrix. Since negative feedback for the recommended items was not in the scope of our work, accuracy metrics are not suitable for the evaluation of the system. Thus, the metric we used for evaluating the quality of the proposed methodology is the Mean Percentile Ranking (MPR).

The first thing that needs to be evaluated is if the algorithm performs better considering all event types or considering only transaction events. Thus, two user item matrices are constructed using the proposed methodology, one constructed based solely on transactions and one including all three interactions. We refer to the user-item matrix that includes all interactions as multi-type MT matrix, and to the one that contains only transactions as single-source matrix ST. Furthermore, the algorithm was evaluated on how well it performs when applying methods for increased accuracy. Thus, the tests on each of the previous user-item matrices implement four different methods: i) the standard method, ii) enhanced by use of ARM, iii) by initializing the user item factor vectors method and iv) by enhancing the matrix as well as initializing the factor vectors method. With 4 different methods on two user item matrices, we calculated the mean percentile ranking for eight different cases.

For AR enhancing the user level category, extracted rules were used as described section 3.2. In total 23 rules have been extracted using minimum confidence of 0.5. Implementing changes where it was necessary lead to 44 changes in the initial user-item matrix. For initialization of the factor vectors the SVD decomposed the initial user-item matrix without any prior filling of missing values.

In addition, on both matrices, information about visitors who have viewed less than 5 items was deemed as unusable and was removed from the training set, since the it is insufficient to produce meaningful recommendations. In addition, this serves the purpose of reducing the total size of the evaluated training set and reducing its sparsity.

Even though this hinders the system's recommendation coverage, addressing the cold start issue was out of scope of this work [START_REF] Nalmpantis | The 50/50 Recommender: a Method Incorporating Personality into Movie Recommender Systems[END_REF].

The dataset used for evaluation is the Retailrocket recommender system dataset [START_REF]Retailrocket recommender system data[END_REF].

Retail Rocket is a company that develops personalization technologies for their customers. The dataset consists of three different files each of which is associated with a different aspect of an e-commerce system.

4.1

Single-source evaluation with transaction events In this case the standard methodology provides the best results. Unexpectedly, all the methods applied aiming at increasing system accuracy turned out to greatly hindered it instead. The assumption is that in this case, the user-item matrix uses a small number of users and items and is dense enough for the algorithm to perform well, in which case any attempt to add values or initialize the factor vectors adds noise to the matrix.

4.2

Multi-source evaluation with transactions, views and addtocart events In this case all the applied methods for increased accuracy actually did increase it. Notably AR enhancing introduced the largest improvement of 3.13%. Following AR initialization of the factor vectors improved the standard methodology by 1.94%. Though it was assumed that implementing both enhancement and initialization would improve performance even further, though that is not the case. Combination of both improvement methodologies improved the algorithm by a mere 0.67%.

Single-source vs multi-source comparison

By comparing the results considering single-source and multi-source matrices, it is notable that single-source user-item matrix performs a lot better than any other type of matrix evaluated. Specifically, compared to the best performing case of multi-source matrices, the AR enhanced multi-source matrix, still performed 5.18% better.

The reason that the single-source performs better is not exclusively because it is a better model. The main difference in the two user-item matrices is data sparsity. Sparsity greatly affects MF techniques. In both matrices, users with only a few interactions have been eliminated. This resulted in a denser single-source matrix. More specifically, the multi-source matrix has a sparsity degree of 0.01%, which means that only the 0.01% of user-item pairs have ratings. On the other hand, single-source matrix has a sparsity degree of 1%, which means that only 1% of all possible user-item ratings are filled. Even though single-source matrix is also too sparse, it is ten times denser than the multi-source matrix.

Fig. 2. Comparison of single-source and multi-source algorithms on all methods

Coverage

In contrast to accuracy, a quality measure often required in RS is coverage. In terms of coverage, the single-source matrix can create recommendations for 1056 users on 106 different items. In contrast, the multi-source matrix can recommend 16022 different items to 43827 users. In terms of coverage the multi-source matrix is more suitable for creating recommendations.

S T A N D A R D M E T H O D O L O G Y A S S O C I A T I O N R U L E S E N H A N C E M E N T I N I T I A L I Z E D F A C T O R V E C T O R S E N H A N C E D & I N I T I A L I Z E D ST MT
or single-source of implicit information used, the AR extract-ed, the method to enhance the user-item matrix with AR, and the method to initialize factor vectors.

Regarding the use of different types of implicit information, results show that a lot of noise is added hindering accuracy. Though predictions are far from random, thus, considering also the difference in coverage between single-source and multi-source (14966 more users and 15916 more items in multi-source) deems multi-source a promising approach. The multi-source approach requires further research for discovering a more suitable method to include this information.

Regarding ARM, even though the number of extracted rules is very small for adequately addressing data sparsity on their own, results indicate that they benefit matrices with data noise, such as multi-source matrices. Initialization of the factor vectors, like AR enhancement, benefits matrices with noise and can improve their accuracy. Though further research is required regarding the decomposition of the matrix as to discovering the best approach for filling the user-item matrix from which the initial vectors will be extracted. Future research should examine different ways of including different implicit information in the user-item matrix and best performing models. The literature for predicting future transactions proposes treating other implicit information as auxiliary data and implements a regression model for discovering the impact they pose in the final transaction [START_REF] Guo | Resolving Data Sparsity by Multitype Auxiliary Implicit Feedback for Recommender Systems[END_REF]. Implicit datasets that offer transaction history provide opportunities for sequence analysis and rule-based recommenders in general. In this paper we considered only AR and let sequential pattern analysis as one of the best next steps for improving the method.

Factor vectors initialization should be further researched for accuracy improvement. Specifically, an adequate way of filling the initial matrix prior to decomposition should be discovered. The literature proposes averages [START_REF] Guo | Resolving Data Sparsity by Multitype Auxiliary Implicit Feedback for Recommender Systems[END_REF] which improved accuracy. In addition, other ways for singular value decomposition should also be examined. The data sparsity issue should also be examined further. ARM alone did not manage to increase the matrices significantly. One possible way could be via product similarity based on item properties and using Content-based filtering methods. Lastly, a lot of products are suitable only for specific time periods such as seasons or a specific age. Thus, time should also be considered in product recommendation research. Time depended recommenders are focused ον by some researchers [START_REF] Jiang | Life-stage Prediction for Product Recommendation in E-commerce[END_REF].

Fig. 1 .

 1 Fig. 1. MuSIF's Flowchart

Table 1 .

 1 Single source methods notation

	Method	Notation	Score
	single -source	ST	30
	enhanced single -source	EST	38
	initialized single -source	IST	39
	enhanced & initialized single -source EIST	39

Table 2 .

 2 Multi source methods notation

	Method	Notation	Score
	multi-source	MT	38.31
	enhanced multi-source	EMT	35.18
	initialized multi-source	IMT	36.37
	enhanced & initialized multi-source EIMT	37.64

  In this paper we proposed MuSIF, a Product Recommendation System based on Multi-source Implicit Feedback. MuSIF utilises a variation of the IF CF by means of ALS. It constructs a user item matrix of inferred preference induced by monitoring customer behavior and uses three different sources of IF. We proposed to treat each source in accordance with the level of interest it implies. In addition, it incorporates ARM to address the data sparsity issue and further increases performance by initializing user and item factor vectors. Conclusions can be categorized regarding the multi

		30	38,31	38	35,18	39	36,37	39	37,64
	5	Conclusions and Future Work


Corinne G Allaart
email: corinne.allaart@stud.ki.se

Lena Mondrejevski

Panagiotis Papapetrou
email: panagiotis@dsv.su.se

FISUL: A Framework for Detecting Adverse Drug Events from Heterogeneous Medical Sources using Feature Importance

Keywords: adverse drug events, feature importance, predictive models, clustering

Adverse drug events (ADEs) are considered to be highly important and critical conditions, while accounting for around 3.7% of hospital admissions all over the world. Several studies have applied predictive models for ADE detection; nonetheless, only a restricted number and type of features has been used. In the paper, we propose a framework for identifying ADEs in medical records, by first applying the Boruta feature importance criterion, and then using the top-ranked features for building a predictive model as well as for clustering. We provide an experimental evaluation on the MIMIC-III database by considering 7 types of ADEs illustrating the benefit of the Boruta criterion for the task of ADE detection.

Introduction

Adverse drug events (ADEs) refer to diagnoses corresponding to injuries that result from the use of a drug, including harm caused by the normal use of a drug, drug overdose, and use-related harms, such as from drug dose reductions and discontinuations of drugs administration [START_REF] Nebeker | Clarifying adverse drug events: a clinician's guide to terminology, documentation, and reporting[END_REF]. ADEs possess high clinical relevance being that they account for approximately 3.7% of hospital admissions around the world [START_REF] Howard | Which drugs cause preventable admissions to hospital? a systematic review[END_REF]. Unfortunately, many ADEs are currently not being identified as such, due to limited knowledge about the effects of medical treatments, e.g., drugs being tested only in limited clinical trials under controlled conditions. An alternative approach is to resort to machine learning and the exploitation of the constantly growing amounts of information stored in electronic healthcare records (EHRs), so as to extract knowledge from past observations and learn how to identify new patient cases with a high risk of leading to an ADE.

With the adoption of EHRs, the amount of healthcare documentation is larger than ever, and there are several efforts underway to involve patients in their healthcare process through the use of patient generated data. Traditionally, data management and machine models have been developed by utilizing information from structured data fields [START_REF] Hielscher | Mining longitudinal epidemiological data to understand a reversible disorder[END_REF][START_REF] Bagattini | A classification framework for exploiting sparse multi-variate temporal features with application to adverse drug event detection in medical records[END_REF] as well as clinical text [START_REF] Henriksson | Modeling heterogeneous clinical sequence data in semantic space for adverse drug event detection[END_REF], little attention has been devoted to combining different data sources for the creation of richer overall models [START_REF] Zhao | Predictive modeling of structured electronic health records for adverse drug event detection[END_REF]. More importantly, these data sources are naturally characterized by high degree of sparsity and missing values. Consider for example a drug prescription variable (e.g., beta-blockers), which is typically administered to patients suffering from heart-related disorders. We should expect that this variable will be substantially empty for patients not suffering from any heart disease.

The problem of missing values in EHRs has been identified by several earlier studies [START_REF] Beaulieu-Jones | Characterizing and managing missing structured data in electronic health records: Data analysis[END_REF][START_REF] Bagattini | A classification framework for exploiting sparse multi-variate temporal features with application to adverse drug event detection in medical records[END_REF]. More recently, Bagattini et al. [START_REF] Bagattini | A classification framework for exploiting sparse multi-variate temporal features with application to adverse drug event detection in medical records[END_REF] propose three simple approaches for handling sparse features in EHRs for the task of ADE detection. Nonetheless, only one type of EHR features was used, corresponding to blood test measurements before the occurrence of an ADE; while diagnoses codes and drug prescriptions were excluded from the study. Moreover, the goal of that paper was to define simple temporal abstractions that take into account such temporal features with high degrees of sparsity. The objective of our study in this paper is to take a different research angle and approach the problem using feature importance to assess the statistical significance of multiple, heterogeneous EHR features in terms of their predictive performance. Moreover, we aim to define a more general approach to the problem of ADE detection in EHRs that can handle disparate feature types and, in the presence of sparse and noisy features, identify the subset of most significant class-distinctive features, that can then be used for both classification and clustering of ADEs in EHRs.

The main contributions of the paper include: (1) the formulation of a framework for identifying and assessing the importance of medical features in terms of their predictive performance, as well as their descriptive power for the problem of ADE detection; (2) the proposed framework employs the Boruta feature importance criterion as a first step, and then subsequently pipelines the selected features to building a predictive model for ADE prediction, as well as identifying clusters of patients under different ADE classes; (3) an extensive experimental evaluation on patient records obtained from the MIMIC database1 including patients with 7 ADE types, and assessing (a) the predictive performance of four classification models using sets of features extracted by the Boruta criterion, as well as (b) the descriptive performance of clusters obtained using the highest scoring features in terms of the Boruta criterion under K-medoids.

Related work

The wide usage of EHRs in medical research has recently increased the interest in the use of clinical data sources by medical practitioners as well as researchers from various fields [START_REF] Hersh | Adding value to the electronic health record through secondary use of data for quality assurance, research, and surveillance[END_REF][START_REF] Weiskopf | Defining and measuring completeness of electronic health records for secondary use[END_REF]. Numerous research directions arise for the problem of ADE identification, which is the key focus of this study [START_REF] Hersh | Adding value to the electronic health record through secondary use of data for quality assurance, research, and surveillance[END_REF]. Compared to traditional data sources, such as spontaneous reports [START_REF] Van Puijenbroek | A comparison of measures of disproportionality for signal detection in spontaneous reporting systems for adverse drug reactions[END_REF], as well as other popular resources, such as social media data [START_REF] Sarker | Utilizing social media data for pharmacovigilance: a review[END_REF], EHRs contain data types and information that allow for incidence estimation and provide class labels for supervised machine learning. Research on mining both structured and unstructured EHR data for ADE detection is nascent, see e.g. [START_REF] Harpaz | Mining electronic health records for adverse drug effects using regression based methods[END_REF][START_REF] Henriksson | Identifying adverse drug event information in clinical notes with distributional semantic representations of context[END_REF][START_REF] Park | A novel algorithm for detection of adverse drug reaction signals using a hospital electronic medical record database[END_REF][START_REF] Schuemie | Using electronic health care records for drug safety signal detection: a comparative evaluation of statistical methods[END_REF][START_REF] Zhao | Predictive modeling of structured electronic health records for adverse drug event detection[END_REF].

The traditional approach for ADE identification is performed before the deployment of a drug. This is achieved by several rounds of clinical trials, which however are hampered by the fact that only a limited sample of patients is usually employed and monitored for a short or limited time period. Consequently, the phenomenon of ADE under-reporting arises as several serious ADEs are not detected during clinical trials but rather after the market deployment of a new drug. This typically results in having several drugs withdrawn. These limitations can be overcome by defining and employing rules for ADE detection [START_REF] Freeman | Advances in electronic surveillance for healthcare-associated infections in the 21st century: a systematic review[END_REF][START_REF] Cao | Handling temporality of clinical events for drug safety surveillance[END_REF].

Machine learning is an alternative to ADE detection by the exploitation of rich data features in EHRs, such as for example blood tests [START_REF] Ouchi | Machine learning to predict, detect, and intervene older adults vulnerable for adverse drug events in the emergency department[END_REF]. More importantly, the development and application of machine learning models, both supervised and unsupervised, in a clinical setting can facilitate substantial improvements in terms of ADE detection while maintaining low hospitalization and treatment costs. We can identify four major lines of research on learning from EHRs [START_REF] Jensen | Mining electronic health records: towards better research applications and clinical care[END_REF]: [START_REF] Bagattini | A classification framework for exploiting sparse multi-variate temporal features with application to adverse drug event detection in medical records[END_REF] detection and analysis of comorbidities, (2) clustering patients with similar characteristics, (3) supervised learning, and (4) cohort querying and analysis. Examples of the above four categories are itemset mining, association rule extraction, and disproportionality analysis, prediction of critical healthcare and patient conditions, such as, for instance, smoking status quantification for a patient [START_REF] Uzuner | Identifying patient smoking status from medical discharge records[END_REF], patient safety and automated surveillance of ADEs [START_REF] Honigman | Using computerized data to identify adverse drug events in outpatients[END_REF], comorbidity and disease networks [START_REF] Cao | Handling temporality of clinical events for drug safety surveillance[END_REF], processing of clinical text [START_REF] Henriksson | Identifying adverse drug event information in clinical notes with distributional semantic representations of context[END_REF], identification of suitable individuals for clinical trials [START_REF] Pakhomov | Prospective recruitment of patients with congestive heart failure using an ad-hoc binary classifier[END_REF], as well as identification of temporal associations between medical events and first prescriptions of medicines for signaling the presence of an ADE [START_REF] Norén | Empirical performance of the calibrated self-controlled cohort analysis within temporal pattern discovery: Lessons for developing a risk identification and analysis system[END_REF].

The FISUL framework

We present Feature Importance for Supervised and Unsupervised Learning (FISUL), a framework for predictive and descriptive modeling of ADEs from EHRs. FISUL has three phases: (1) feature importance, (2) predictive modeling, and (3) clustering. In Figure 1 we provide an outline of the proposed framework. Next, we describe each phase in more detail.

Phase I: Boruta feature importance

We employ the Boruta method [START_REF] Kursa | Boruta -a system for feature selection[END_REF] as a feature importance criterion for reducing the number of data features. Boruta is a variable importance method that is defined for the random forest classifier, by mainly measuring the total decrease in impurity from performing a feature split over all nodes of a tree, averaged over all trees in the random forest. The Boruta method was selected for its ability to provide unbiased and stable selection of all relevant features [START_REF] Kursa | Feature selection with the boruta package[END_REF] The main idea is to create randomized copies of the existing features, merge the copies with the original data features, build a final classifier using all features, including the randomized ones, and iteratively identify the most important features for the classification task at hand. More concretely, let D be the original dataset and let F denote the original feature space. The key objective of Boruta is to define a mapping process, T , such that T : F -→ F. where F is a set of randomized features originating from F. More concretely, the following steps are performed:

-Randomization: a replica, called shadow feature, fi ∈ F is created for each feature f i ∈ F, by random permutation of its values; as a result, possible correlations that may exist between the original features and the class attribute are diminished. -Model building: a random forest R is built using the union of the features F F. This procedure is repeated n times, i.e., for n iterations.

-Importance score: for each f i ∈ F and fi ∈ F, we define an importance score, called Z -score, over all trees in R, where each feature appears. The mean and standard deviation of the accuracy loss are defined as µ fi , µ fi and σ fi , σ fi , respectively, using the out-of-bag samples. Finally, the Z-score of each feature f i and each shadow feature fi is defined as

Z fi = µ fi σ fi and Z fi = µ fi σ fi ,
respectively. Intuitively, the Z-score reflects the degree of fluctuation of the mean accuracy loss among the trees in R. -Statistical significance: for each original f i ∈ F, we compute a statistical significance score using a two-tailed binomial test. More specifically, let Z j max be maximum Z-score of all shadow features in iteration j, i.e.,

Z j max = max fi∈ F Z fi . (1)
We use a vector, called hit vector H, to store for each f i ∈ F in how many iterations it achieved a Z-score higher than Z j max , i.e.,

H i = n j=1 |1 1 {fi:Z f i ≥Z j max } (f i )| , (2)
where 1 1 is the indicator function, i.e.,

1 1 A (x) = 1 if x ∈ A 0 if x / ∈ A (3)
If feature f i performs significantly better than expected compared to its shadow features in terms of Z-score, it is marked as "important". Note that under the binomial distribution assumptions, the expected number of times H i that f i may outperform its shadow replicas is simply

E(f i , n) = n 2 , with a standard deviation σ(f i , n) = √ 0.25n, assuming that H i ∼ B(n, 0.5). Conversely, f i is considered "important", if H i is significantly higher than E(f i , n).
Finally, the features that survive the test constitute the set of Boruta features F .

Phase II: Predictive modeling

The set of Boruta features F extracted from Phase I are next passed to Phase II for building a predictive model using the new feature space. The main objective is to learn a classification function τ : o → y, that assigns a given data object o with a class label from a set C of predefined class labels, such that y ∈ C. More specifically, we can couple τ with a set of features θ selected and employed during the training phase. In our case, the set of class labels corresponds to a selected set of ADEs. More information about the selected class labels can be found in Section 4. The training phase of a predictive model is more formally defined as τ = L(θ, T ), where L is the learning function corresponding to a chosen predictive model and T is the training set. Finally, the label of a newly seen data example o is obtained by applying τ , configured with the same chosen feature set θ, i.e., y = τ (o; θ). In our framework, we choose the top-k most important Boruta features, i.e., θ = F k .

Phase III: Clustering

An alternative approach for exploiting F is clustering. The main objective is to define a partitioning G = {g 1 , . . . , g K } of K groups, such that inter-group similarity is maximized and intra-group similarity is minimized.

Since in our case the data objects contain features that are not necessarily numerical, we employ K-medoids using the Gower distance. This distance function computes the average dissimilarity across the data objects. Let o i , o j be two data objects in our dataset and |θ| be the size of our feature space. The Gower distance is computed as follows:

G dist (o i , o j ) = 1 |θ| |θ| i=1 d f i,j , (4)
where d f i,j is a function computing the dissimilarity of feature f between objects o i and o j , depending on the feature type, after standardizing each feature. For example, in the case of numerical features, d f i,j is defined as follows:

d f i,j = |o f i -o f j | Z f , (5)
where Z f is the maximum distance range across all data objects and o f i , o f j denote the values of feature f for objects o i , o j , respectively. In the case of categorical features, d f i,j = 0, if o f i = o f j and 1, otherwise. The clustering is obtained by running K-medoids under the Gower distance given by Eq. 4, and tuning K using the Silhouette coefficient [START_REF] Rousseeuw | Silhouettes: A graphical aid to the interpretation and validation of cluster analysis[END_REF] and selecting the one with the highest Silhouette value [START_REF] Rousseeuw | Silhouettes: A graphical aid to the interpretation and validation of cluster analysis[END_REF].

Experimental evaluation

We outline the experimental setup by first our dataset, the benchmarked methods, the undersampling procedure we used to tackle the high class imbalance, and finally the presentation of our findings.

Dataset. We used the Medical Information Mark for Intensive Care III (MIMIC-III) database [START_REF] Scott | Accessing the public mimic-ii intensive care relational database for clinical research[END_REF], a freely available medical database for intensive care (ICU) research, released in 2006 and comprising over 40,000 patients. Several studies have been conducted on this dataset using predictive models, such as prediction of hospital stay [START_REF] Gentimis | Predicting hospital length of stay using neural networks on mimic iii data[END_REF] or mortality rate [START_REF] Desautels | Using transfer learning for improved mortality prediction in a data-scarce hospital setting[END_REF]. However, little attention has been given to prediction of ADEs, yet they are common in ICU patients [START_REF] Bates | for the ADE Prevention Study Group: Patient Risk Factors for Adverse Drug Events in Hospitalized Patients[END_REF]. In MIMIC-III the ADEs are coded as ICD-9 diagnosis codes and for this study we explored the 7 of the most commonly occurring codes depicting ADEs; grouped as caused by one of four specific drugs: (1) antibiotics, (2) anticoagulants, (3) antineoplastic and immunosuppressive drugs, or (4) corticosteroids. We hence considered five datasets, one being the whole dataset including all ADEs, while each of the remaining four corresponded to each of the four specific drugs. All hospital admissions where one of these drugs were prescribed, were considered in the preprocessing, with a positive class label signifying at least one of the selected ADEs during hospital stay. A summary of the used datasets is given in Table 1.

Four different types of features were selected from MIMIC-III, either based on previous relevance to ADE prediction or as they had been identified clinically as risk factors or indications of ADEs in critical care. These features were: admission characteristics, undergone procedures, laboratory tests, and prescribed drugs. For the last three, one-hot encoding was applied based on clinically relevant groupings of their coding systems. The NDC drug codes extracted from MIMIC-III were converted to ATC codes [START_REF] Kury | Desiderata for drug classification systems for their use in analyzing large drug prescription datasets[END_REF], as the ATC grouping system has more clinical relevance. The full set of selected features is described in Table 2. The drug specific datasets excluded the drug feature group the ADE was caused by, for example the dataset with ADEs caused by corticosteroids excluded the corticosteroid drug group as a feature. Setup. We benchmarked six predictive modeling techniques having demonstrated competitive predictive performance in earlier works on ADE detection [START_REF] Bagattini | A classification framework for exploiting sparse multi-variate temporal features with application to adverse drug event detection in medical records[END_REF][START_REF] Zhao | Predictive modeling of structured electronic health records for adverse drug event detection[END_REF]: (1) Random Forests (RF100) with 100 trees, (2) simple Feed-Forward Neural Networks (NNet), (3) eXtreme gradient boosting (XGBoost), ( 4) SVM with a radial basis kernel (SVMRadial), ( 5) SVM with a polynomial kernel with degree 3 (SVMPolynomial), and (6) SVM with a linear kernel (SVMLinear). Due to the high class imbalance in all datasets, we performed under-sampling of the majority class for each dataset. All models used 3 feature sets: all features, the relevant features as selected by Boruta, and Boruta's top 10 (after under-sampling). The performance metrics were AUC and AUPRC, under 10fold cross-validation. For clustering we used the original imbalanced datasets. We applied K-medoids for different values of K, using the Gower distance on the top-10 Boruta selected features.

Results. Next, we present our experimental findings for each of the three phases of the FISUL framework.

-Boruta feature importance. When applied to the whole dataset, the Boruta criterion rejected 56 features, mainly those that were extremely sparse (<1% occurrence). Many of the top ranking significant features are laboratory tests, while the vast majority of the remaining significant features are drug prescriptions with very few admission characteristics and procedures, which is comparable to the antibiotics dataset (Fig 2). The anticoagulants dataset paints a similar picture, with the only difference that age and the platelets lab test are the top 2 features (Fig 4). For the immunosuppressives dataset, the top-3 features were again laboratory tests, while the majority of the remaining significant features were drugs, with very few features corresponding to procedures. On the other hand, we observe that for corticosteroids (Figure 3 (left)) the vast majority of significant features are drugs, with laboratory tests being less significant. We also note that for the latter dataset, no other feature types where deemed significant. -Predictive modeling. Our experimental findings in terms of predictive performance are shown in Tables 3,4, and 5. We observe that both RF100 and XGBoost consistently outperform the other classifiers for the whole dataset classification in all feature sets. For the four individual datasets, RF100 is still a winner in most of the cases, alongside with XGBoost, especially on the complete unfiltered feature set, where the other benchmarked classifiers are not competitive. However, note that when the Boruta feature selection is applied first and either only all relevant or top-10 features are included, the performances of the other benchmarked classifiers are not substantially lower than the two winners. Clustering. For all 5 datasets, the Silhouette coefficient suggested two clusters. For all cases, the two clusters mostly contained non-ADE examples, while cluster purity was above 96% for the whole dataset as well as for corticosteroids, 98% for antibiotics and anticoagulants, and 91% for immunosuppressives. Due to the inherent extreme class imbalance of the dataset the top-10 Boruta features did not manage to capture any strong cluster structure that can distinguish ADE from non-ADE cases.

Fig. 2: Histograms of the Boruta importance for all feature types for the whole dataset (left) and the antibiotics dataset (right). We observe that the features with the highest importance are Laboratory tests and drugs for both cases.

Discussion. Our overall framework and our benchmark on six predictive models, illustrates the medical importance of the selected features. The most important features of all the datasets mainly included values clinically known to be indicative of ADEs, such as laboratory tests and certain drugs groups. The procedures seemed to be the least influential features for ADE detection. There were differences between the 4 drug-specific datasets, which could be clinically explained. For example, the top 2 features in the anticoagulants dataset were age and platelet lab tests, which are also considered the two major risk factors in anticoagulants caused ADEs [START_REF] Fitzmaurice | Bleeding risks of antithrombotic therapy[END_REF]. Moreover, the corticosteroid dataset showed mainly drugs important features. Corticosteroids are a known factor in many Fig. 3: Histograms of the Boruta importance for all feature types for the corticosteroids dataset (left) and the immunosuppresive dataset (right). We observe that the features with the highest importance for immunosuppresives are the drugs, while for corticosteroids some laboratory tests precede in the ranking. drug-drug interactions [START_REF] Daveluy | Drug interactions between inhaled corticosteroids and enzymatic inhibitors[END_REF], which are often at the base of ADEs, which could explain the importance of other drug groups for corticosteroid-induced ADEs.

With regards to the classifiers, it is evident that the random forest and extreme gradient boosting outperformed the other classifiers. However, when the full framework including the feature selection is applied, the other classifiers become competitive, while the two winners to not decrease in predictive performance. Also, the addition of the feature selection speeds up the model building phase substantially, without decreasing the performance. Moreover, due to the high values of purity obtained in the clustering, our results still suggest that the Boruta criterion can be seen as a promising feature importance measure for identifying strong cluster substructures.

Conclusions

We presented a framework for studying ADEs in EHRs using heterogeneous feature types. We illustrated the importance of the Boruta feature importance criterion for the tasks of classification and clustering ADEs. Our findings suggest that integrating different feature types along with a strong feature importance criterion (such as Boruta) can provide substantially better predictive performance compared to only using drugs or clinical tests. Directions for future work include the integration of features from non-structured data types (e.g., clinical text and notes) and the exploration of alternative feature importance measures.

Fig. 1 :

 1 Fig. 1: An outline of the FISUL framework.

Fig. 4 :

 4 Fig. 4: Histogram of the Boruta importance for the anticoagulant dataset. We observe that laboratory tests and the patient's age are the most important features.

Table 1 :

 1 The table provides information about the whole dataset used for our experimental evaluation, and the four subset datasets of ADEs. For each dataset we indicate the number of total examples, the number of positive and negative class labels, the gender ratio of the patients (in terms % of female patients), and their average age.

		Whole	Anti-	Immuno-Cortico-Antbiotics
		Dataset coagulants suppresive steroids
	Total # of Examples	47506	42449	2389	12198	37145
	# of Class Labels (positive) 2078	600	223	511	469
	# of Class Labels (negative) 4,4	1,4	9,3	4,2	1,3
	% of Female Patients	43.9	43.9	42.8	49.3	44.2
	Average Age	58.8	61.9	57.2	61.2	58.4

Table 2 :

 2 The table provides information on the features of the datasets used in our experimental evaluation. Per feature type, the total number of features for the whole dataset is indicated, as well as the type of grouping used for their one-hot encoding.

		# of Features	Type of grouping
	Admission Characteristics	5	-
	Procedures	18	ICD-9 2 procedure groups
	Laboratory Test	10	LOINC 3 (parent) groups
	Prescribed Drugs	94	ATC 4 level 2

Table 3 :

 3 The performance the six chosen classifiers for the five datasets in terms of AUC and AUPRC for all data features without applying the Boruta criterion.

		Whole Dataset Anticoagulants Immunosupp. Corticosteroids Antibiotics
		AUC AUPRC AUC AUPRC AUC AUPRC AUC AUPRC AUC AUPRC
	RF100	0,81	0,79	0,73	0,69	0,78	0,75	0,72	0,70	0,80 0,78
	NNet	0,57	0,38	0,54	0,43	0,65	0,45	0,58	0,40	0,58 0,45
	XGBoost	0,81	0,79	0,73	0,69	0,78	0,75	0,71	0,68	0,81 0,78
	SVMRadial	0,50	0,49	0,56	0,56	0,52	0,51	0,48	0,50	0,49 0,49
	SVMPolynomial 0,74	0,76	0,67	0,63	0,76	0,74	0,67	0,69	0,74 0,72
	SVMLinear	0,71	0,72	0,58	0,61	0,71	0,75	0,57	0,65	0,61 0,72

Table 4 :

 4 The performance the six chosen classifiers for the five datasets in terms of AUC and AUPRC for all data features considered significant by the Boruta criterion.

		Whole Dataset Anticoagulants Immunosupp. Corticosteroids Antibiotics
		AUC AUPRC AUC AUPRC AUC AUPRC AUC AUPRC AUC AUPRC
	RF100	0,81	0,79	0,74	0,69	0,80	0,77	0,72	0,71	0,81 0,78
	NNet	0,78	0,66	0,69	0,59	0,74	0,61	0,66	0,62	0,71 0,60
	XGBoost	0,81	0,79	0,74	0,69	0,79	0,74	0,71	0,69	0,81 0,78
	SVMRadial	0,80	0,77	0,73	0,69	0,76	0,74	0,69	0,68	0,79 0,75
	SVMPolynomial 0,80	0,79	0,70	0,66	0,80	0,76	0,71	0,68	0,80 0,76
	SVMLinear	0,80	0,78	0,70	0,66	0,76	0,73	0,70	0,67	0,79 0,75

Table 5 :

 5 The performance the six chosen classifiers for the five datasets in terms of AUC and AUPRC for the top-10 significant data features based on the Boruta criterion.

		Whole Dataset Anticoagulants Immunosupp. Corticosteroids Antibiotics
		AUC AUPRC AUC AUPRC AUC AUPRC AUC AUPRC AUC AUPRC
	RF100	0,78	0,77	0,71	0,66	0,77	0,75	0,70	0,67	0,79 0,77
	NNet	0,78	0,76	0,69	0,63	0,76	0,69	0,70	0,66	0,78 0,75
	XGBoost	0,78	0,77	0,72	0,67	0,78	0,74	0,71	0,67	0,80 0,77
	SVMRadial	0,76	0,71	0,70	0,64	0,78	0,75	0,70	0,68	0,76 0,73
	SVMPolynomial 0,77	0,76	0,69	0,64	0,80	0,77	0,70	0,67	0,78 0,76
	SVMLinear	0,77	0,76	0,68	0,63	0,77	0,74	0,70	0,66	0,78 0,75

https://mimic.physionet.org.

http://icd9.chrisendres.com/index.php?action=contents

https://loinc.org/groups/

https://www.whocc.no

Acknowledgments

This work was partly supported by the VR-2016-03372 Swedish Research Council Starting Grant.