Benjamin Gras
email: benjamin.gras@loria.fr

Armelle Brun
email: armelle.brun@loria.fr

Anne Boyer
email: anne.boyer@loria.fr

Can Matrix Factorization Improve the Accuracy of Recommendations Provided to Grey Sheep Users?

Keywords: Recommender Systems, Grey Sheep Users, Matrix Factorization

Matrix Factorization (MF)-based recommender systems provide on average accurate recommendations, they do consistently fail on some users. The literature has shown that this can be explained by the characteristics of the preferences of these users, who only partially agree with others. These users are referred to as Grey Sheep Users (GSU). This paper studies if it is possible to design a MF-based recommender that improves the accuracy of the recommendations provided to GSU. We introduce three MF-based models that have the characteristic to focus on original ways to exploit the ratings of GSU during the training phase (by selecting, weighting, etc.). The experiments conducted on a state-of-the-art dataset show that it is actually possible to design a MF-based model that significantly improves the accuracy of the recommendations, for most of GSU.

Introduction

Being different is a property shared by each person since everyone is unique. Current information systems exploit what data share, as well as their closeness, as a bond between them. They do not manage their differences. Although unique, most people share or are close on several characteristics. But what if a person does not share enough characteristics with others? What if a person is too different? In the frame of recommender systems [START_REF] Goldberg | Using collaborative filtering to weave an information tapestry[END_REF] that manage users' preferences, it results in the Grey Sheep Users (GSU) problem [START_REF] Claypool | Combining content-based and collaborative filters in an online newspaper[END_REF][START_REF] Ghazanfar | Fulfilling the needs of gray-sheep users in recommender systems, a clustering solution[END_REF].

RS suggest users of a system some resources, within a huge set of resources, with the aim to increase their satisfaction. The popularity of RS is continuously increasing and they are becoming an everyday part of our lives. They are used in many application domains, including e-commerce [START_REF] Huang | Designing utility-based recommender systems for e-commerce: Evaluation of preference-elicitation methods[END_REF]), e-learning [START_REF] Verbert | Context-aware recommender systems for learning: A survey and future challenges[END_REF], tourism [START_REF] Zanker | Information and communication technologies in tourism, chapter Evaluating recommender systems in tourism a case study from austria[END_REF], etc. RS have been extensively studied these last twenty years, the most prevalent approach is collaborative filtering (CF). CF relies on the information collected about users, most of the time preferences, and assumes that users' preferences are consistent among users. So, to infer the preferences of a user, the active user, CF relies on the preferences of a community of users [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF]; the resources with the highest estimated preferences are suggested to the active user.

CF-based recommender systems now provide on average highly accurate recommendations [START_REF] Castagnos | When diversity is needed... but not expected![END_REF]. Providing users with accurate recommendations is essential, as it is one of the key to success of the service on which the recommender system runs. In e-commerce, accurate recommendations increase customer retention; in e-learning they improve learners' learning process; etc. However, some users still get inaccurate recommendations.

The literature has recently emphasized that the singular preferences of some users, in comparison to those of the others, may explain why they get inaccurate recommendations [START_REF] Ghazanfar | Fulfilling the needs of gray-sheep users in recommender systems, a clustering solution[END_REF]. These users, who only partially agree (or disagree) with any community of users, are referred to as Grey Sheep Users (GSU) and are often opposed to "normal" users [START_REF] Claypool | Combining content-based and collaborative filters in an online newspaper[END_REF]. The Matrix Factorization (MF) recommendation technique has proven to be highly accurate and is now the most commonly used CF technique. MF techniques use an optimization process to form a model that fits the training data. More specifically this process relies on the overall accuracy of the recommendations. Within the entire set of users, GSU not only have singular preferences, but are also outnumbered. As a consequence, GSU might be overlooked within the sheer amount of normal users, so standard MF techniques do not accurately model GSU and do not provide them with high quality recommendations [START_REF] Gras | Identifying Grey Sheep Users in Collaborative Filtering: a Distribution-Based Technique[END_REF].

We believe that providing GSU with accurate recommendations is one way to improve the global accuracy of the system. The question addressed in this paper is thus: "Can we improve the accuracy of the recommendations provided to grey sheep users through matrix factorization?". [START_REF] Griffith | Investigations into user rating information and predictive accuracy in a collaborative filtering domain[END_REF] has shown that it may be possible to improve the accuracy of the recommendations provided to each user by learning a specific model. Thus, we ask if GSU can benefit from a model dedicated to them.

Few works in the literature have been interested in providing accurate recommendations to GSU. These works either simply split the set of users into normal and abnormal users [START_REF] Del Prete | differs: A mobile recommender service[END_REF], and then learn a model dedicated to each set, or rely on clustering [START_REF] Ghazanfar | Leveraging clustering approaches to solve the gray-sheep users problem in recommender systems[END_REF], or design new similarity measures between users [START_REF] Bobadilla | A collaborative filtering similarity measure based on singularities[END_REF].

As GSU have singular preferences, we assume that a unique model cannot accurately model both normal users and GSU. So, we consider a recommender system that relies on two models: a standard MF-based model from the state-of-the-art, used to provide recommendations to normal users and a MF model dedicated to GSU. The design of this second model is the focus of this paper.

Section 2 presents an overview of Collaborative Filtering and GSU modeling techniques. Section 3 introduces the MF models we design to fit GSU preferences. Section 4 focuses on the experiments conducted to evaluate each model and highlights the benefits of each of them. Finally, we discuss and conclude our work.

RELATED WORKS

Collaborative Filtering and Matrix Factorization

Collaborative Filtering (CF) relies on the preferences of some users on resources (items) to provide the active user u with some personalized recommendations. Let U be the set of n users and I be the set of m resources. The set of preferences, generally ratings, is represented in the form of a matrix R, where r u,i denotes the preference of u on the item i.

Two main approaches are used in CF: memorybased and model-based.

Memory-based approaches [START_REF] Resnick | Grouplens: An open architecture for collaborative filtering of netnews[END_REF] exploit users' preferences, without pre-processing. A commonly used technique is the user-based KNN (K Nearest Neighbors) that computes the similarity of preferences between each pair of users, and estimates the missing preferences of u by exploiting the preferences of his/her K nearest neighbor users (the item-based KNN technique that exploits the K nearest neighbor items is also commonly used). This technique is accurate, easy to implement and it automatically takes into account each new preference in the recommendation process. However, it hardly scales due to the computation cost of the similarities [START_REF] Rashid | Web Mining and Web Usage Analysis, chapter Towards a Scalable kNN CF Algorithm: Exploring Effective Applications of Clustering[END_REF] and it suffers from the extreme sparsity of the preference dataset (the similarity between two users or resources may not be computable, or two similarity values may not be comparable) [START_REF] Grcar | Data quality issues in collaborative filtering[END_REF]Grcar et al., 2005a).

Model-based approaches learn a model of preferences. Among the various techniques we can find Matrix Factorization (MF), that has recently proved to be highly accurate [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF][START_REF] Takacs | Scalable collaborative filtering approaches for large recommender systems[END_REF]. It is now the most commonly used technique, especially due to its high scalability. The general idea of MF is modeling user-resource interactions (ratings) through factors that represent latent characteristics of the users and of the resources, such as preference classes of users or category classes of resources. In practice, MF computes two sub-matrices with k latent features: the matrix P (dimension n * k) represents user-factors, and the matrix Q (dimension m * k) represents resource-factors. The factorization aims at accurately approximating R through the product of P and Q: PQ T ≈ R. The accuracy of this approximation relies on the error on each rating r u,i in R, following equation (1):

e u,i = r u,i -P u Q T i , (1)
where P u is the k-dimensional representation of user u and Q i is the k-dimensional representation of item i. P and Q are obtained through an optimization process, by exploiting a loss function L. In recommender systems, loss functions are often based on the nonzero squared loss:

argmin P,Q L(R, P, Q) = argmin P,Q ∑ r u,i ∈R e 2 u,i (2)
Alternating least squares (ALS) and stochastic gradient descent (SGD) are two popular approaches to solve this optimization problem. ALS solves the problem iteratively. At each iteration, one of the matrices (P or Q) is fixed, while the other matrix is modified (using equation ( 2)). At each iteration, the matrix fixed changes. SGD learns the matrices by iteratively evaluating the error e u,i for each rating r u,i in R. Both matrices P and Q are updated by taking a step in the opposite direction to the gradient of the loss function (equation ( 2)), following equations (3) and (4). p u = p u + α(e u,i q i ),

(3) q i = q i + α(e u,i p u ), (4) where α is the learning rate. In both approaches, these steps are repeated until the loss function does not significantly decrease or until a predefined number of iterations is reached.

To avoid overfitting, a regularization constraint is commonly incorporated, through the use of a regularization term in the loss function (equation ( 5)).

argmin

P,Q L(R, P, Q) = argmin P,Q ∑ r u,i ∈R e 2
u,i + λ reg(P, Q)

(5) The two most commonly used terms for regularization are L 1 and L 2 norms. The L 1 regularization [START_REF] Zheng | Statistical debugging of sampled programs[END_REF] manages the absolute values in matrices P and Q, whereas L 2 manages the squares of the values [START_REF] Nigam | Using maximum entropy for text classification[END_REF] (see equation ( 6)). In practice, L 2 regularization shows better results on datasets with many instances and few features [START_REF] Yu | Parallel matrix factorization for recommender systems[END_REF], which corresponds to RS datasets.

regL 2 (P, Q) = ||P u || 2 + ||Q i || 2 (6)

Grey Sheep Users

Grey sheep users (GSU) is a term commonly used in recommender systems. GSU are also referred to as deviant users, abnormal users, atypical users, unusual users, etc. [START_REF] Del Prete | differs: A mobile recommender service[END_REF][START_REF] Ghazanfar | Fulfilling the needs of gray-sheep users in recommender systems, a clustering solution[END_REF]. They refer to these users whose opinions do only partially agree or disagree with any community of users [START_REF] Claypool | Combining content-based and collaborative filters in an online newspaper[END_REF]. Inconsistent users [START_REF] Bellogín | The magic barrier of recommender systems -no magic, just ratings[END_REF] may also be related to GSU. Inconsistency is defined as users' inherent noise when interacting (rating) with a recommender system. Notice that inconsistency exploits only information about a user, not in comparison to other users. Several techniques have been proposed to perform the identification of GSU in RS. Most of them exploit the properties of the ratings of the resources: Abnormality [START_REF] Del Prete | differs: A mobile recommender service[END_REF] evaluates to what extent the ratings of a user is distant from the average rating of the resources he/she rated, Abnormality-CRU [START_REF] Gras | Identifying users with atypical preferences to anticipate inaccurate recommendations[END_REF] includes the variance of the ratings for each resource, whereas DILikelihood [START_REF] Gras | Identifying Grey Sheep Users in Collaborative Filtering: a Distribution-Based Technique[END_REF] relies on the distribution of the ratings, etc.

Once GSU are identified, the question related to their management has to be addressed. [START_REF] Griffith | Investigations into user rating information and predictive accuracy in a collaborative filtering domain[END_REF] mentionned that it may be possible to learn a specific model for each user, whereas [START_REF] Penn | Mircotrends: the small forces behind tomorrow's big changes[END_REF] emphasizes that preferences of grey sheep users are difficult to understand and to guess. So, the management of their preferences, as well as the conception of a recommendation model that fits their profile, seems to be a challenge.

The literature highlights the fact that GSU get inaccurate recommendations as the correlation of their ratings with other users could be low. Although neighbor-based recommendation approaches rely heavily on finding close neighbors [START_REF] Manouselis | Exploratory study of multi-criteria recommendation algorithms over technology enhanced learning datasets[END_REF], all the works have focused on these approaches. (Del Prete and Capra, 2010) divide users into two distinct subsets: mass like-minded users (normal users) and individual users (GSU); two recommendation models are formed: each one is learnt on and dedicated to one subset of users. Authors propose an adapted similarity measure between individual users. It relies on the fact that it does not represent to which extent two users rate resources similarly, but to which extent they similarly differ from the entire community. The accuracy of the recommendations provided to individual users is slightly improved. [START_REF] Bellogín | The magic barrier of recommender systems -no magic, just ratings[END_REF] have studied the accuracy of the recommendations that inconsistent users receive. The entire set of users is also split into easy users (normal users) and difficult (inconsistent) users. The accuracy of the recommendations provided to difficult users is not improved when only difficult users are used in the training set. This conclusion is contradictory to the one presented in (Del Prete and Capra, 2010). [START_REF] Bobadilla | A collaborative filtering similarity measure based on singularities[END_REF] have proposed to take into account the singularity of preferences of users in the evaluation of the similarity between two users. Rating values are categorized and a rating is singular if it does not correspond to the predominant category on this resource. When computing the similarity between two users, the more a rating is singular, the greater its importance. Using this new similarity measure slightly improves the accuracy of recommendations provided to grey sheep users. Although this work is not directly dedicated to the management of GSU, it is a way to take into account the specific preferences of users in the way to compute recommendations.

To manage the preferences of GSU, [START_REF] Ghazanfar | Leveraging clustering approaches to solve the gray-sheep users problem in recommender systems[END_REF] propose to rely on a pure content-based approach. The experiments conducted show that such an approach is more adequate to model GSU, the resulting model is more accurate than with a CF approach. Nevertheless, as most of the current datasets do not include resources metadata, this approach may not always be applicable.

Managing cold-start users may be considered as closely related to managing GSU. Cold-start users are users who have not provided enough information to the system, to accurately model them. The problem of managing GSU is different. The GSU are not new users, they are users with preferences that do not align with those of other users.

DESIGNING MODELS OF GSU

Similarly to the works presented in the previous section, the recommendation system we focus on relies on two sub-models: one model is dedicated to normal users (a standard MF model), the other model is dedicated to GSU. The work here is dedicated to the design of the latter model.

The identification of GSU is made upstream training the model, and upstream any recommendation process. To compute recommendations to a user, his/her category is identified (normal user or GSU), then the adequate recommendation model is used. As the detection of GSU is not the focus of this paper, we propose to use a recent state-of-the-art detection technique, that relies on the DILikelihood measure [START_REF] Gras | Identifying Grey Sheep Users in Collaborative Filtering: a Distribution-Based Technique[END_REF].

Recall that the literature has mostly focused on the neighbor-based approaches to model GSU (see section 2.2). As MF has proved to be the most accurate CF technique the general case [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF], we propose to design a MF-based recommendation model dedicated to GSU. To the best of our knowledge, it is the first attempt to study MF with this goal.

We are convinced that the reason why GSU do not get accurate recommendations with MF models not only lies in their singular preferences, but also in their number. Indeed, by definition, GSU are rare instances, so there are considerably more normal users than GSU. As the criterion optimized by MF is the global recommendation accuracy (on the entire set of users), the accuracy on GSU does not, or slightly, impact the global accuracy; so the resulting model tends to accurately model normal users, whatever is the accuracy of this model on GSU. SGD and ALS are nowadays two popular methods to factorize matrices [START_REF] Yu | Parallel matrix factorization for recommender systems[END_REF]. The MF models we propose can be used on the frame of both methods. For the sake of concision, we present these models with one of these methods. We choose SGD.

We propose three MF models dedicated to GSU.

Algorithm 1 Standard SGD Algorithm

Input: R = {r u,i } -set of ratings of users u on items i, k -number of features of the model, α -learning rate of the factorization, λ -regularization parameter Output:

Latent factor matrices P and Q procedure SGD(R, k, α, λ)

initialize random factor matrices P and Q while no Stop do for each r u,i ∈ R do e u,i = (r u,ip u q T i ) // Error estimation q i ← q i + α * (e u,i .p uλ.q i ) p u ← p u + α * (e u,i .q iλ.p u ) return P and Q no Stop is a boolean that represents if the stop criterion is reached (number of iterations or convergence of the loss function).

The GSUOnly Model

The first model we introduce aims at evaluating to what extent a GSU can benefit from other GSU only. The model is trained on the ratings of the set of GSU, the ratings of normal users being dismissed. This model is referred to as the GSUOnly model.

For this model, no amendments of the standard SGD algorithm (Algorithm 1) will be made. The only difference lies in the set of ratings used in the training phase, which is reduced to the ratings of GSU. The running time required to learn this model is reduced compared to standard models as the dimension of the matrices (R, P and Q) is highly reduced (|GSU| << n).

Note that this model cannot be used to provide recommendations to users who do not belong to the set of GSU (normal users), as the resulting matrices P and Q do not contain any value for these users.

The WeightedGSU Model

The second model we introduce, called WeightedGSU, weights GSU during the learning process. In standard algorithms both GSU and normal users have the same weight.

We will consider W GSU as the weight of GSU and W normal as the weight of normal users. Equation ( 7) presents the relation between both weights.

W GSU +W normal = 1.0 (7)
We are convinced that the weight of GSU has to be more important than the one of normal users. In this way, the rating specificities of GSU will be better addressed, while still using ratings of normal users. The ratings of normal users represent additional information in the learning process and are a way to cope with the lack of data from the small set of GSU. We aim at finding the W GSU value that optimizes the accuracy of the recommendations GSU get.

WeightedGSU also relies on Algorithm 1, in which we introduce modifications to manage the various weights. More specifically, the error estimation step is modified, to fit equation ( 8):

e u,i = W u * (r u,i -p u q T i ), (8)
where W u is the weight of user u, with W u = W GSU if u is a GSU and W u = W normal if u is a normal user.

The SingleGSU Model

The last model forms one model for each GSU. It is designed to evaluate to what extent a model dedicated to a specific GSU improves the accuracy of the recommendations provided to this user. This model, named SingleGSU, is learnt on the ratings of one GSU (the user the model is dedicated to) as well as on the ratings of additional users. We choose to select the additional users within the set of normal users to thoroughly study the influence of normal users on the accuracy of the recommendations provided to GSU, and exclude the possible negative impact that the ratings of some GSU may have on other GSU. The number and the way these additional normal users are chosen has to be studied.

Notice that this model is more a proof of concept than a model that can be used on real datasets. Indeed, it is not acceptable to compute a model for each GSU, in the context where data is overwhelming. Nevertheless, it is a way to study in depth the ability of MF to accurately model GSU.

EXPERIMENTS

This section presents the experiments we conduct to study to what extent the Matrix Factorization models we propose can improve the accuracy of the recommendations provided to GSU.

Dataset

The experiments are conducted on the MovieLens 20M dataset1 , made up of 20 mil-lion ratings from 138,493 users on 27,278 movies (resources). The rating scale ranges from 0.5 to 5.0 stars, with half-star increments. This dataset was published in April 2015 and is the current standard dataset for the evaluation of CF recommenders.

To not bias the evaluation, we choose to discard users who may be associated with the coldstart problem: those with less than 20 ratings in the dataset [START_REF] Schickel-Zuber | Overcoming incomplete user models in recommendation systems via an ontology[END_REF]. The set of users is then reduced to 123,053 users (88.8% of the original set of users) and is made up of 19.6 million ratings (98% of the original set of ratings). In the resulting dataset, users have provided up to 8,400 ratings, with an average number of 159 ratings per user. The sparsity of this dataset is higher than 99%, which is extremely sparse.

Evaluation Setup

The models studied are evaluated in terms of recommendation accuracy. More precisely, we use the RMSE (Root Mean Squared Error) measure. RMSE evaluates the discrepancy between the rating a user assigned to a resource and the rating estimated by the recommender, computed by equation ( 9).

RMSE = ∑ u,i∈R (n u,i -n * u,i ) 2 ||R|| , (9)
where n * u,i is the estimated rating of user u on item i and R = {r u,i } is the set of user-item ratings.

The set of ratings of the dataset is split into two sets: Train that contains 80% of the ratings randomly chosen and that will be used to train the different models, and Test that contains the 20% remaining ratings and that will be used to evaluate the accuracy of the models. Each of these sets is in turn split into two subsets: the subset made up of the ratings of GSU (Train GSU and Test GSU ) and the subset made up of the ratings of normal users (Train normal and Test normal ).

The accuracy of the models proposed is compared to that of standard MF models. ALS and SGD factorization techniques are studied. As the optimization of the parameters of these techniques is not the focus of this work, we fix them to the state-of-the-art values, used on a comparable dataset [START_REF] Yu | Parallel matrix factorization for recommender systems[END_REF]. 20 features are used, with a learning rate of 0.001 and a regularization parameter set to 0.02. Matrices P and Q are initialized randomly. A dozen runs are executed to avoid the bias introduced by the random initialization. The stop criterion used in the algorithms is the convergence of the RMSE on GSU. These models will further be considered as baselines. The first two lines of Table 1 present the RMSE of the two standard MF models (trained on Train and evaluated on Test ) with ALS and SGD factorization techniques and the L 2 regularization. SGD slightly outperforms ALS (by 2.5% for the median), which is consistent with what is usually reported in the literature [START_REF] Yu | Parallel matrix factorization for recommender systems[END_REF].

The identification of GSU is performed with the DILikelihood measure, introduced in [START_REF] Gras | Identifying Grey Sheep Users in Collaborative Filtering: a Distribution-Based Technique[END_REF]. We experimentally defined the set of GSU as the 6% of users with the highest DILikelihood values. This set of GSU has an average number of ratings of 103 per user, which confirms they are not cold-start users. The third and fifth lines of Table 1 present the RMSE of normal users (Test normal ) and of GSU (Test GSU ) respectively, using a standard SGD model (the same as in the first line). With a median RMSE of 1.18 on GSU and a median RMSE of 0.78 on normal users, the RMSE on GSU is 51% higher than the RMSE on normal users. We can confirm that GSU do actually get less accurate recommendations than normal users. In addition, the third quartile of the RMSE of normal users is lower than the first quartile of the RMSE of GSU. Moreover, the median RMSE of the entire set of users (Test) is 0.80, which confirms that the number of GSU is so small that they have a limited impact on the RMSE of the entire set of users.

From the third and the fourth lines of Table 1, we can see that as on the Test set, SGD provides more accurate recommendations on the Test GSU than ALS. Furthermore, the difference on Test GSU is larger than on Test: SGD is 8% more accurate than ALS. SGD seems to be more adapted to model GSU.

We ask now if the L 1 regularization (see last line of Table 1) could be a better choice for the regularization term to model GSU, referring to [START_REF] Ng | Feature selection, l1 vs. l2 regularization, and rotational invariance[END_REF][START_REF] Yu | Parallel matrix factorization for recommender systems[END_REF]. The median RMSE with L 1 is 1.21, which is 3% higher than the one obtained with the L 2 regularization. We can conclude that modifying the regularization term on a model learnt on Train is not the adequate solution to better model GSU.

The following experiments will be conducted to study if the models proposed in Section 3 are a way to better model GSU than standard MF models.

The GSUOnly Model

This section is dedicated to the evaluation of the accuracy of the GSUOnly model, that is trained on the ratings of GSU: namely the Train GSU subset. Table 2 displays the resulting median RMSE.

Modeling GSU by relying only on the preferences of the set of GSU leads to a model less accurate than a model trained on the ratings of the entire set of users (the RMSE is increased by 8%). These conclusions are consistent with those reported in [START_REF] Bellogín | The magic barrier of recommender systems -no magic, just ratings[END_REF], that showed that with a neighbor-based approach, exploiting only inconsistent users to compute recommendations for inconsistent users does not lead to accurate recommendations.

We can conclude that GSU benefit from the presence of normal users in the learning process of the factorization technique. This is also the conclusion reported in [START_REF] Bellogín | The magic barrier of recommender systems -no magic, just ratings[END_REF]: "less coherent users need information from outside of their own cluster".

Using the L 1 regularization, the RMSE is comparable to the one obtained with L 2 regularization (L 2 outperforms L 1 by only 1%, which is not significant). Thus, L 1 seems to be more adapted to the GSUOnly model than to a standard one. However, it does not improve the L 2 regularization. So, we confirm that L 2 remains the most accurate regularization. For the following experiments, we will use L 2 as regularization term.

Model

The WeightedGSU Model

The previous experiments showed that, when training the model on the ratings of GSU (Train GSU ) only, GSU do get recommendations less accurate than when training the model on the ratings of the entire set of users. However, even in this latter model, GSU do not get accurate recommendations. We think that the weight of GSU in such a model is too small to accurately model them. So, in this section we further study to what extent allowing a higher weight to GSU is a way to better model them: the WeightedGSU model. Figure 1 presents the evolution of the median RMSE, according to the weight of GSU (W GSU ). W GSU ranges from 0.1 to 1.0, with respect to equation (7). Let us notice that the case where W GSU = 0.0 cannot be studied as it would come down to not consider GSU during training, so the matrix P would contain random values in the vectors that correspond to GSU. A weight equals to 1.0 represents the case where normal users are not taken into account at all (the GSUOnly model), the corresponding RMSE is 1.27. A weight equals to 0.5 is equivalent to a standard model (GSU and normal users have a similar weight); the RMSE is 1.18. The smaller the impact of GSU on the factorization process, the worse the accuracy of their recommendations, which was expected. In the case where W GSU > 0.5, the RMSE increases along with the weight of GSU. It varies from 1.17 to 1.27. Thus, the higher the impact of GSU in the factorization process, the worse the accuracy of their recommendations. The lowest RMSE value is reached when W GSU = 0.5, which is equivalent to the standard MF model.

The evolution of the RMSE in the case where W GSU > 0.5, is not intuitive, we expected that giving a larger weight to GSU in the factorization would increase the accuracy of the recommendations provided to them. We wonder if the presence of the ratings of the entire set of GSU interferes with GSU modeling.

The SingleGSU Model

In the next experiments we propose to study the SingleGSU model that forms one model per GSU. Each model is trained on the ratings of a single GSU as well as those of a subset of normal users. We choose to not exploit the ratings of other GSU to discard their possible negative influence. The question here is twofold: (i) how many normal users have to be used to learn the model? and (ii) how to select the normal users?

The first experiment we conduct exploits normal users that are the most similar to the single GSU, according to the Pearson Correlation Coefficient.

As we consider 6% of the complete set of users as GSU (more than 7K GSU), the number of MF processes to be run is too high. We propose to randomly select 300 GSU and learn one SingleGSU model for each of them. The DILikelihhood of these 300 GSU is equally distributed within the set of GSU. Figure 2 presents the median RMSE of GSU with respect to the number of similar users selected. This number varies from 100 to 1,500. Figure 2 also presents the baseline RMSE (the one obtained with a standard SGD model). When 100 similar normal users are selected, the average RMSE of the SingleGSU model is 1.21, which is higher than the RMSE of a standard model. The higher the number of normal users, the lower the RMSE. When about 250 normal users are selected, the RMSE is similar to the one of a standard model. The decrease of the RMSE seems to stagnate from 700 normal users (the RMSE equals to 1.09). When 1,500 normal users are selected the RMSE is equal to 1.06, which corresponds to an improvement of 9% of standard models (from 1.17 to 1.06). Obviously, the more normal users are used, the longer the computation time to learn the model. The best tradeoff between the running time and the accuracy of recommendations provided to GSU seems to be 700 normal users (7% improvement).

Those first results represent an average improvement of the RMSE. It implies a disparity in the improvement of the RMSE, among GSU. To go further, we study the individual distribution of those improvements. First of all, the SingleGSU model improves the RMSE of more than 72% of the 300 GSU selected. If we focus on a more significant improvement, 54% of the GSU have an improvement of their RMSE of more than 10%. So, the SingleGSU model, with normal users selected through their similarity with the single GSU, significantly improves the accuracy of the recommendations of more than half of the GSU. In addition, 32% of the GSU have an improvement of their RMSE of more than 20%. Furthermore, 20% of the selected GSU have a RMSE lower than the median RMSE of normal users (0.8), which is high.

What about the 46% of GSU who have either an improvement of their RMSE lower than 10% or have an increase in their RMSE? We propose to build SingleGSU models for these users, with a random selection of the normal users. For each user, several random selections are performed, until forming a set of normal users that significantly improves (by at least 10%) the accuracy of the recommendations of the single GSU, in the limit of 500 trials. Such an improvement is reached for 62% of these GSU. Several attempts have been conducted to characterize the sets of normal users that improve the recommendations provided to those GSU. For now, no clear link has emerged.

To summarize, the SingleGSU model is able to significantly improve (by more than 10%) the accuracy of the recommendations provided by a standard MF model, for more than 82% of the selected GSU. This indicates that it is possible to increase the accuracy of the recommendations provided to GSU through a MF technique. The experiments conducted tend to show that one reason why GSU do not receive accurate recommendations with standard MF models may lie in the users used in the factorization process.

Discussion and Conclusion

This work aimed at studying the possibility to design a MF-based model that improves the accuracy of the recommendations that standard MF-based models provide to grey sheep users (GSU).

To reach this goal, we relied on the idea that when training a model, the ratings of GSU have to be considered differently than those of normal users. We proposed three models that either exploit only the ratings of GSU (the GSUOnly model), or weight differently the ratings of GSU and those of normal users (the WeightedGSU model) or model each GSU independently (the SingleGSU model).

The SingleGSU model, that forms a model for each GSU independently, improves the accuracy of the recommendations provided to GSU. This model exploits the ratings of one GSU (the user the model is dedicated to) as well as those of a subset of normal users (no rating about other GSU are included). When normal users are selected according to their similarity to the GSU, 72% of GSU actually get more accurate recommendations, which is highly significant. Furthermore, 52% of GSU have an improvement larger than 10%. This rate even reaches 82% if an additional way to select normal users is used.

To summarize, we wondered if some MF-models could improve the accuracy of the recommendations provided to GSU. Actually, the MF-based SingleGSU model significantly improves this accuracy, even by more than 10% for most of GSU.

These results need to be extended to study to what extent this improvement can be even more improved. This may rely on a modification of the correlation measure used to select the normal users to be used in the SingleGSU model, or designing a completely new MF technique. In addition, as noticed in section 3, designing one model per GSU is not practicable, especially if the number of GSU reaches several thousands of users. So, we would like to study if some GSU could be grouped together to reduce the number of models to be developed.

So far, the experiments conducted did not allow to identify how to select the set of normal users to use, given one GSU. Some GSU benefit from the selection of the most similar users, others do not. Being able to identify which users benefit from these similar users will also be highly interesting.

Figure 1 :

 1 Figure 1: RMSE of GSU according to the weight of GSU during the factorization processTwo main trends are observed in Figure1. In the case where W GSU < 0.5, the RMSE increases along with the decrease of the weight of GSU (up to 1.3). The smaller the impact of GSU on the factorization process, the worse the accuracy of their recommendations, which was expected. In the case where W GSU > 0.5, the RMSE increases along with the weight of GSU. It varies from 1.17 to 1.27. Thus, the higher the impact of GSU in the factorization process, the worse the accuracy of their recommendations. The lowest RMSE value is reached when W GSU = 0.5, which is equivalent to the standard MF model.The evolution of the RMSE in the case where W GSU > 0.5, is not intuitive, we expected that giving a larger weight to GSU in the factorization would increase the accuracy of the recommendations provided to them. We wonder if the presence of the ratings of the entire set of GSU interferes with GSU modeling.

Figure 2 :

 2 Figure 2: Median RMSE of GSU w.r.t. the number of similar users selected

Table 1 :

 1 RMSE of standard models

	Model	Test	RMSE RMSE RMSE
		set	Q1	Median	Q3
	SGD	Test	0.66	0.80	0.97
	ALS	Test	0.66	0.82	1.00
	SGD	Test GSU	1.01	1.18	1.35
	ALS	Test GSU	1.12	1.28	1.45
	SGD	Test normal	0.65	0.78	0.95
	SGD-L1	Test GSU	1.04	1.21	1.39

Table 2 :

 2 RMSE of the GSUOnly model

http://grouplens.org/datasets/movielens/


Yacine Abboud

Anne Boyer

Armelle Brun

CCPM: A Scalable and Noise-Resistant Closed Contiguous Sequential Patterns Mining algorithm

Keywords: Data mining, sequential pattern mining, closed contiguous sequential pattern, scalable, noise resistant

Mining closed contiguous sequential patterns has been addressed in the literature only recently, through the CCSpan algorithm. CCSpan mines a set of patterns that contains the same information than traditional sets of closed sequential patterns, while being more compact due to the contiguity. Although CCSpan outperforms closed sequential pattern mining algorithms in the general case, it does not scale well on large datasets with long sequences. Moreover, in the context of noisy datasets, the contiguity constraint prevents from mining a relevant result set. Inspired by BIDE, that has proven to be one of the most efficient closed sequential pattern mining algorithm, we propose CCPM that mines closed contiguous sequential patterns, while being scalable. Furthermore, CCPM introduces usable wildcards that address the problem of mining noisy data. Experiments show that CCPM greatly outperforms CCSpan, especially on large datasets with long sequences. In addition, they show that the wildcards allows to efficiently tackle the problem of noisy data.

Introduction

Pattern mining [START_REF] Agrawal | Mining Association Rules Between Sets of Items in Large Databases[END_REF] is one of the most studied topic in the data mining literature. An ordered pattern is usually called a sequential pattern. Many applications rely on sequential patterns: pattern discovery in protein sequences [START_REF] Liao | DFSP: a Depth-First SPelling algorithm for sequential pattern mining of biological sequences[END_REF], [START_REF] Zhang | Mining Periodic Patterns with Gap Requirement from Sequences[END_REF], analysis of customer behavior in web logs [START_REF] Chen | Mining Contiguous Sequential Patterns from Web Logs[END_REF], sequence-based classification [START_REF] Aggarwal | Xproj: A Framework for Projected Structural Clustering of Xml Documents[END_REF], etc. Consequently, sequential pattern mining [START_REF] Agrawal | Mining Sequential Patterns[END_REF] has become a significant part of pattern mining studies. Many sequential pattern mining algorithms have been proposed to solve various issues, such as general sequential pattern mining [START_REF] Han | FreeSpan: Frequent Pattern-projected Sequential Pattern Mining[END_REF], [START_REF] Pei | PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth[END_REF], string mining [START_REF] Fischer | Optimal string mining under frequency constraints[END_REF], [START_REF] Matsui | A New Approach to String Pattern Mining with Approximate Match[END_REF], closed sequential pattern mining [START_REF] Wang | BIDE: Efficient Mining of Frequent Closed Sequences[END_REF][START_REF] Yan | Clospan: mining closed sequential patterns in large datasets[END_REF], constraint-based sequential pattern mining [START_REF] Garofalakis | MSPIRIT: Sequential Pattern Mining with Regular Expression Constraints[END_REF], [START_REF] Pei | Constraint-based Sequential Pattern Mining: The Pattern-growth Methods[END_REF], etc. A pattern is said closed if there is no super-pattern with the same support. Closed sequential mining has become popular as the set of closed patterns extracted contains the same information than the set of general sequential patterns, but with less redundancy [START_REF] Zhang | CCSpan: Mining closed contiguous sequential patterns[END_REF]. Many real-life tasks greatly benefit from patterns with contiguous items. For example in text mining [START_REF] Fürnkranz | A Study Using n-gram Features for Text Categorization[END_REF], contiguous patterns are used for statistical natural language processing or document classification. In Web log mining [START_REF] Chen | Mining Contiguous Sequential Patterns from Web Logs[END_REF][START_REF] Chen | Contiguous item sequential pattern mining using UpDown Tree[END_REF], they are used to predict navigation paths and thus to improve the design of web pages. The search of frequent contiguous sequential patterns in DNA and amino acid sequences is unavoidable to reveal common shared functions [START_REF] Kang | Mining Frequent Contiguous Sequence Patterns in Biological Sequences[END_REF][START_REF] Karim | An Efficient Approach to Mining Maximal Contiguous Frequent Patterns from Large DNA Sequence Databases[END_REF]. The contiguity constraint leads to the extraction of much fewer patterns with a shorter average length, while carrying the same information [START_REF] Zhang | CCSpan: Mining closed contiguous sequential patterns[END_REF]. That is why closed contiguous sequential patterns (CCSPs) are highly relevant to mine data. However, the added value provided by the contiguity constraint has its cost. In case of noisy data, the support of the mined contiguous patterns is underestimated, making some of these patterns not frequent. CCSpan is the only algorithm designed to mine CCSPs, its design stands on a snippet-growth scheme to generate candidate patterns. A snippet is a contiguous sub-pattern. CCSpan outperforms, in runtime and memory usage, all the closed sequential pattern mining algorithms in the literature [START_REF] Zhang | CCSpan: Mining closed contiguous sequential patterns[END_REF]. Nevertheless, it suffers from the same issue than other contiguous pattern mining algorithms: the lack of adaptability to noisy data. In addition, despite being the most efficient algorithm to extract sequential patterns, CCSpan does not scale well on large databases having long sequences. Two scientific questions thus arise: 1) How to improve contiguous sequential pattern mining algorithms to more accurately extract information from noisy data? 2) How to increase the efficiency of CCSP mining algorithms to scale with large databases and long sequences? In this paper, we introduce a new algorithm CCPM that overcomes those two issues. CCPM is based on Prefixspan [START_REF] Pei | PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth[END_REF] and on BIDE [START_REF] Wang | BIDE: Efficient Mining of Frequent Closed Sequences[END_REF], two of the most efficient sequential mining and closed sequential mining algorithms [START_REF] Li | Efficiently Mining Closed Subsequences with Gap Constraints[END_REF]. CCPM mines closed contiguous patterns with usable wildcards. A wildcard [START_REF] Li | Efficiently Mining Closed Subsequences with Gap Constraints[END_REF] is a joker of one item regarding the contiguity constraint. Let a, b, d, c be a pattern, it can be considered as the pattern a, b, c with one wildcard. Unlike other algorithms with wildcards of the literature, CCPM introduces a maximal number of wildcards that can be used per pattern. To the best of our knowledge, CCPM is the first noise-resistant CCSP mining algorithm due to the use of wildcards. CCPM also offers the possibility to mine patterns that start with a constrained item and thus gets a new set of patterns not included in the closed contiguous sequential patterns. Experiments show that CCPM greatly outperforms CCSpan, especially on large datasets with long sequences. Hence the main contributions of this paper are:

we introduce the second closed contiguous sequential pattern mining algorithm that significantly outperforms the first one, CCSpan; we use expendabled wildcards to make CCPM noise-resistant; we present experiments on standard datasets and on jobs offers datasets to show how CCPM performs on large and noisy data;

This paper is organized as follows. Section 2 introduces concepts and notations required by the formulation of CCSP problem. In Section 3 we explore properties of CCSP and present CCPM. Section 4 is dedicated to the experiments conducted, while Section 5 concludes.

Preliminaries and Related Work

2.1 Preliminaries.

In this section we introduce some definitions and notations used for CCSP mining.

Let I = {i 1 , i 2 , ..., i n } be a set of distinct items. A sequential pattern P is an ordered list denoted as P = e 1 , e 2 , ..., e m where e k ∈ I is an item for 1 ≤ k ≤ m. For brevity, a sequential pattern is also written e 1 e 2 ...e m . A sequential pattern P 1 = a 1 a 2 ...a n is contiguously contained in another sequential pattern (S α ). Similarly, the relative support of P α in SDB is the proportion of sequences in SDB that contain P α , denoted by sup SDB R (S α ). The universal contiguous support is the number of occurrences of P α in SDB, denoted by uni sup SDB (P α ). Given a threshold min sup, a contiguous sequential pattern P α is frequent in SDB if sup SDB A (P α ) ≥ min sup or sup SDB R (P α ) ≥ min sup. P α is a closed contiguous sequential pattern if there exists no contiguous sequential pattern P β such that: P α c P β , and sup SDB A (P α ) = sup SDB A (P β ). An item e is a starting item, denoted e, if it satisfies a chosen constraint. A pattern is a starting item pattern if its first item is a starting item. Aside from the above notations, we further present some definitions. The sequential pattern mining problem was first introduced by Agrawal and Srikant in [START_REF] Agrawal | Mining Sequential Patterns[END_REF] with the Apriori algorithm. Apriori is based on the monotonicity property "all nonempty subsets of a frequent itemset must also be frequent" [START_REF] Agrawal | Mining Association Rules Between Sets of Items in Large Databases[END_REF]. Since then, many sequential pattern mining algorithms have been proposed for performance improvements: Prefixspan [START_REF] Pei | PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth[END_REF], SPAM [START_REF] Ayres | Sequential Pattern Mining Using a Bitmap Representation[END_REF], etc. Prefixspan algorithm uses projected databases to mine frequent sequential patterns. Prefixspan recursively extends a prefix sequential pattern by adding a frequent item from the projected database of this prefix. This new representation of data, based on projected databases, allows a more efficient mining [START_REF] Ayres | Sequential Pattern Mining Using a Bitmap Representation[END_REF] and thus Prefixspan performs really well regarding execution time. As closed sequential patterns lead to a more compact set of patterns but also a better efficiency, several algorithms focus their mining on such patterns [START_REF] Pei | CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets[END_REF], [START_REF] Zaki | CHARM: An efficient algorithm for closed itemset mining[END_REF]. Clospan [START_REF] Yan | Clospan: mining closed sequential patterns in large datasets[END_REF] is one of them, it mines a candidate set of closed patterns based on Prefixspan algorithm, and keeps the candidate patterns set for post-pruning. The candidate set is expensive in term of memory usage. To cope with this issue, the BIDE algorithm [START_REF] Wang | BIDE: Efficient Mining of Frequent Closed Sequences[END_REF] does not memorize any candidate set of closed patterns. BIDE generates new patterns with the framework of Prefixspan and uses a BI-Directional closure checking scheme that does not use any set of candidates, hence improves greatly both runtime and memory usage. The philosophy of this scheme is to check if a frequent pattern can be extended to the left (backward extension) or to the right (forward extension) with at least one item. The pattern is closed if it can not be extended in each sequence. BIDE is known to be one of the most efficient closed sequential pattern mining algorithm [START_REF] Li | Efficiently Mining Closed Subsequences with Gap Constraints[END_REF]. One major issue in closed sequential pattern mining comes from large databases: the set of frequent closed sequential patterns becomes unmanageable. To solve this problem, CCSpan [START_REF] Zhang | CCSpan: Mining closed contiguous sequential patterns[END_REF] algorithm introduced closed contiguous sequential pattern (CCSP) mining. Frequent CC-SPs are far fewer and shorter than closed sequential patterns. CCSpan uses a snippet-growth scheme to generate candidate patterns. The original sequence is split into a set of snippets of the same length and their support is calculated to keep the frequent ones as candidate patterns. Then for each candidate pattern, two sub-patterns are considered, the one without the first item of the pattern and the one without the last item. The closure checking is performed recursively by comparing the support of the pattern and the support of both sub-patterns. Despite being more efficient than closed sequential pattern mining algorithms due to the contiguity constraint, CCSpan scales rather poorly on datasets with long sequences. Indeed, the framework that builds snippets becomes highly time consuming as sequences become longer. Furthermore, CCSpan suffers from a lack of adaptability of CCSPs to noisy data. In fact, the support of CCSPs on noisy data may not reflect the real support of those patterns in the data. Therefore, the CCSPs can not be used to accurately extract information from noisy data. The issues raised by the state-of-the art make us consider the following questions: (1) Can the highly efficient framework from Prefixspan that mines frequent sequential patterns, used as well in Clospan and BIDE, be used to get frequent CCSPs? (2) How to take inspiration from BIDE, one of the most efficient algorithm for closed sequential patterns mining, to mine CCSPs? (3) How to bypass CCSpan algorithm issues with noisy data and keep the added value of contiguity?

P 2 = b 1 b 2 ...b m , if n < m and there exist consecutive integers 1 ≤ j 1 < j 2 < ... < j n < m such that a 1 = b j1 , a 2 = b j2 , ...,

CCPM: Mining Closed Contiguous Sequential Patterns

In this section, we introduce the CCPM algorithm (Closed Contiguous sequential Patterns Mining), which shares the philosophy of both Prefixspan [START_REF] Pei | PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth[END_REF] and BIDE algorithms [START_REF] Wang | BIDE: Efficient Mining of Frequent Closed Sequences[END_REF]. The use of contiguous sequential patterns mining algorithm is only relevant in case of clean data but most of the time data still contains noise.

In order to overcome this issue of noisy data, we introduce a maximal number of wildcards per pattern. As the mined data is usually just a bit noisy, the number of wildcards allowed is often rather small. In addition, CCPM allows to mine patterns starting with an item that satisfies a given constraint: starting item patterns. Such patterns are interesting in many domains. In text mining, patterns starting with an action verb in order to identify competencies [START_REF] Abboud | Predict the emergence -Application to competencies in job offers[END_REF] or in marketing, purchase patterns starting by a given category of items to establish more targeted selling strategies, etc. As a contiguous sequential starting item pattern (CSSP) can only start with a starting item, a closed contiguous sequential starting item pattern (CCSSP) is necessarily equal or included in a closed contiguous sequential super-pattern. If it is included, the CCSSP will not appear in the set of mined CCSPs. Therefore, if one CCSSP is not equal to the closed contiguous sequential super-pattern then the set of CCSSPs is not included in the set of CCSPs. Therefore, CCPM uses a framework that enumerates frequent contiguous sequential starting item patterns with wildcards (CSSPWs), inspired by the framework of Prefixspan to enumerate frequent sequential patterns. CCPM uses a closure scheme and a pruning technique inspired by the BI-Directional closure scheme and the Backscan method of BIDE to mine closed patterns. CCPM relies on three steps listed here: First, a framework that mines frequent CSSPWs. Second, a BI-Directional checking scheme, adapted to CSSPWs, that forms closed contiguous sequential starting item patterns with wildcards (CCSSPWs). Third, a contiguous pruning techniques used to improve the efficiency of CCPM.

Framework to enumerate frequent CSSPWs.

Here we introduce some definitions about projected contiguous items and database in order to explain the framework.

Definition 1. Projected contiguous items of a prefix sequential pattern with wildcards: Given an input sequence S and a sequential pattern P with P c S, the projected contiguous items of P are all the adjacent items after each occurrence of P in S and P is called a prefix sequential pattern. For example, in the sequence ABBCA of Table Proof. Given two items e 1 and e 2 , a prefix sequential pattern P and a sequence database SDB. If e * 2 is always a projected contiguous item of P together with e 1 and if e 2 is never a projected contiguous item of P in SDB, it means that there exists a contiguous sequential pattern Q = P, e 1 , e 2 with uni sup SDB (Q) = uni sup SDB ( P, e 2 ). Thus, the sequential pattern P, e 2 is always included in Q and so is its expansions. Therefore, it is useless to expand it.

The complete search space of contiguous sequential patterns forms a sequential pattern tree [START_REF] Ayres | Sequential Pattern Mining Using a Bitmap Representation[END_REF]. The root node of the tree is at the top level and is labeled ∅. The framework of CCPM recursively extends a node (referred to as a prefix sequential pattern) at a certain level in the tree by adding a contiguous item, resulting in a child node at the next level. As CCPM mines starting item patterns, the framework only extends frequent items satisfying the constraint. Applying this constraint greatly reduces the search space, hence greatly improves its efficiency. It also improves the results by removing irrelevant patterns. When all frequent starting items are found, each one becomes a prefix sequential pattern to expand, they are at the first level of the tree. The framework then builds the projected contiguous database of each prefix. To know if a wildcard is avalaible, the count of wildcards used is memorized for each occurrence of the prefix sequential pattern. Then, only the frequent items in the projected contiguous database grow the prefix sequential pattern. Now we describe how to enumerate frequent closed contiguous sequential patterns with one wildcard on this example. The prefix sequential pattern A is the first studied, its projected contiguous database is: {A, B, C * ; B, C * ; B, C * ; B}. In this projected database, B has a support of 4 and C a support of 3. As their support exceed min sup, both of them can be extended. However, B always occurs together with C * in the projected contiguous database and C is never a projected contiguous item. According to Theorem 1, A can be extended with B, C can be removed. Then, given the prefix sequential pattern AB, the projected database is: {C; C, B * ; C; B, C * }. C has a support of 4 and B a support of 2, both of them can be extended. The projected database of ABC is: {∅; B; ∅; A} and the one of ABB is: {∅; C}. As no item have a support greater or equal to min sup = 2, the prefix sequential pattern A is now completely extended. The same procedure can be used with B and C. With those definitions in mind, the following theorem and lemma are straightforward. Theorem 2. A CSSPW P is closed, if and only if P has no backward extension and no forward extension items. Lemma 1. Given a CSSPW P in a sequence database SDB, if there is a backward space Q of P in SDB, with sup SDB A ( Q, P ) = sup SDB A (P ), then Q is a backward extension of P . Lemma 2. For a given CSSPW P, its complete set of forward extensions items is the set of items in its projected contiguous database that have a support equal to sup SDB A (P ). We introduce two stop conditions during the backward spaces scanning to improve the efficiency of the backward extension checking. The backward checking extension of a CSSPW is stopped as soon as: 1) a starting item cannot be found in the backward spaces of a sequence; 2) one of the two backward contiguous items (if a wildcard is available) or the backward contiguous item (no wildcard) of the prefix sequential pattern cannot be found in the backward spaces of a sequence.

The contiguous BackScan pruning.

To prune the useless parts of the search space, we propose to use the Backscan technique from BIDE, adapted to CCSSPW mining. The idea behind Backscan is to detect if the current prefix sequential pattern can be absorbed by a prefix sequential pattern that will be mined later. If it is the case, it is not expanded.

Theorem 3 (The Backscan pruning). Given a CSSPW P in SDB, if there exists a backward space Q with uni sup( Q, P ) = uni sup SDB (P ), P can be safely pruned.

Proof. Given a CSSPW P and a backward space Q with uni sup( Q, P ) = uni sup SDB (P ). Assume we extend P with a contiguous sequential pattern K to get a longer CSSPW R (R = P, K ), we can also construct another CSSPW R = Q, P, K . As uni sup SDB ( Q, P ) = uni sup SDB (P ), we have uni sup SDB (R) = uni sup SDB (R ). Hence, we can not use P as a prefix sequential pattern to generate any CCSSPW.

The CCPM algorithm.

CCPM (Algorithm 1), integrates the three previous steps: the framework that searches frequent CSSPWs, the BI-Directional closure checking and the BackScan pruning.

Algorithm 1 CCPM(SDB, min sup, W)

Input:a sequence database SDB, a minimum support threshold min sup, a maximal number of wildcards W Output:F, the complete set of frequent CCSSPWs 1: F = {∅} 2: F 1 = f requent starting items(SDB, min sup); 3: foreach f 1 in F 1 do 4: f 1 SDB = projected database(SDB, f 1, W ); 5:

if (!BackScan(f 1)) 6:

call pGrowth(f 1 SDB, f 1, min sup, F ); 7: return F ; Algorithm 2 pGrowth(P SDB, P , min sup, F ) Input: projected sequence database with the used wildcards P SDB, a prefix sequential pattern P , a minimum support threshold min sup Output:F, the current set of frequent CCSSPWs 1: F I = f requent items(P SDB, min sup); 2: BEI = Backward Check(P, P SDB, W ) 3: if (!BackScan(P ) 4:

F EI = z in F I | z.sup = sup SDB (P ) ; 5: if ({BEI ∩ F EI} == {∅}) 6: F = F {P }; 7:
foreach i in F I do 8: P i = P, i ; 9:

P i SDB =projected database(P SDB, P i , W ); 10:

call pGrowth(P i SDB, P i , min sup, F );

The input parameters of Algorithm 1 are a sequence database, a minimum support and a maximal number of wildcards per pattern. CCPM starts by scanning the database to find the set of frequent starting items: F 1 (line 2). The starting items constraint can be removed without any impact on CCPM. The projected database function (line 4) creates the projected database of each item in F 1 and specifies if a wildcard has been used or not for each occurrence of each item. BackScan (line 5) is applied to check if a frequent item can immediately be pruned. The subroutine pGrowth (Algorithm 2) is called for each frequent starting item with its projected database. pGrowth checks if the input pattern P is closed and recursively extends P with each frequent items in its projected database. pGrowth continuously updates the set of CCSSPWs. The function Backward Check (line 2) looks for backward extensions, with 2 stop conditions designed to improve the efficiency. Backscan (line 3) is used again to check if the prefix can be pruned, then if there are no forward and no backward extensions (line 4 and 5), the input pattern P is added to the set of frequent CCSSPW: F (line 6). Then the projected database of P is scanned to find the set of frequent contiguous items and specifies if a wildcard has been used or not for each item (line 9). Each frequent item extends P (line 8) and becomes the prefix sequential pattern to recall pGrowth until CCPM returns F , the complete set of frequent CCSSPW.

Experiments

We conduct a comprehensive performance study to evaluate CCPM. [START_REF] Zhang | CCSpan: Mining closed contiguous sequential patterns[END_REF] has shown how CCSpan outscales and outperforms closed sequential pattern mining algorithms such as Clospan and BIDE. Therefore, we only compare CCPM to our implemantation of CCSpan to evaluate its efficiency. First, CCPM is compared to CCSpan [START_REF] Zhang | CCSpan: Mining closed contiguous sequential patterns[END_REF] in terms of running time and memory usage. The parameters of CCPM are set so that CCSpan and CCPM correspond to the same configuration: CCSP mining. Second, CCPM with no constraints and CCPM with starting item patterns and wildcards are compared to evaluate the impact of these constraints.

Datasets and environnement.

The experiments are performed on a i7-4750HQ 2GHz, 8GB memory on Windows 10. In order to evaluate the performance of CCPM, we use five real datasets that cover a wide range of distribution characteristics. Two of them are reference datasets used to evaluate sequential pattern mining algorithms. BM S1 Gazelle [START_REF] Yan | Clospan: mining closed sequential patterns in large datasets[END_REF], [START_REF] Wang | BIDE: Efficient Mining of Frequent Closed Sequences[END_REF], [START_REF] Zhang | CCSpan: Mining closed contiguous sequential patterns[END_REF] used in the KDD-CUP 2000 competition and M ushroom, available online on the SPMF website 1 . The three other datasets are datasets we formed from online job offers, so made up of noisy textual data. The BM S1 Gazelle dataset contains clickstream and purchase data from Gazelle.com, a legwear and legcare web retailer. BM S1 Gazelle is sparse. The second dataset, M ushroom, is composed of characteristics of various species of mushrooms and was originally obtained from the UCI repository of machine learning databases. M ushroom is dense. The three job datasets (jobs900, jobs1000 and jobs60000) are composed of job offers collected on websites between January 2016 and June 2016. They reflect the kind of textual data that can be found on the web, they are noisy and very sparse. The characteristics of the five datasets are shown in Table 2. Some of these datasets share similarities on some attributes, so we can easily compare the influence of each attribute on CCPM. The datasets BM S1 Gazelle and jobs60000 as well as jobs900 and jobs1000 have approximately the same number of sequences with a very different average length, they will be compared to evaluate the impact of average length. The datasets jobs900 and M ushroom as well as jobs1000 and jobs60000 have the same average length, they will be compared to evaluate the impact of the number of sequences. The experiment will highlight the impact of both average length and number of sequences on the efficiency of CCSpan and CCPM. As CCPM can be set to mine CCSPs like CCSpan, we can conduct a series of experiments on the five datasets in terms of execution time and memory usage, with various relative support thresholds (Figure 2). Each line stops when the absolute support reaches the value of 1 for the corresponding dataset. First of all, Figure 2 shows that neither CCSpan nor CCPM are significantly impacted by the variation of the support. Indeed, both runtime and memory usage are never increased by more than 10 whereas the number of patterns is increased from 110 times on jobs1000 to 6,200 on jobs60000. The only exception is the runtime of CCSpan on the M ushroom dataset, which is increased by almost 100. The contiguity constraint seems to make CCSpan and CCPM almost independent on the support and on the number of patterns mined. As the variation of the support has little impact on runtime and memory usage, we choose to set the support value for the rest of the experiments, this value is set to min sup = 1%.

Average length We first evaluate the impact of the average length of sequences on the execution time of CCSpan and CCPM (Figure 2a). jobs900 and jobs1000 share a similar number of sequences (900 vs 1,000) with a very different average length (23 vs 76). Same with BM S1 Gazelle and jobs60000 (59,601 vs 60,000) that also differ in the average sequence length (2.4 vs 77). CCSpan runs 8 times faster on jobs900 than on jobs1000 whereas the average length of jobs900 is 3 times smaller (ratio of 2.7). Same reasoning between BM S1 Gazelle and jobs60000, CCSpan runs 6,800 faster on BM S1 Gazelle than on jobs60000 whereas the average length is 32 times smaller (ratio of 212). We can conclude that the average length of the sequences exponentially impacts the runtime of CCSpan. CCPM runs 3.5 times faster on jobs900 than on jobs1000 (ratio of 1.2) and 25 times faster on Gazelle than on jobs60000 (ratio of 0.8). We can conclude that, contrary to CCSpan, the runtime of CCPM is linearly impacted by the length of the sequences.

Number of sequences Now we focus on the impact of the number of sequences on the execution time of CCSpan and CCPM. jobs900 and M ushroom share a similar average length of sequences (26.6 vs 23), while having a different number of sequences (900 vs 8,416). The two datasets jobs1000 and jobs60000 also have a similar average length of sequences (76 vs 77), while having a very different number of sequences (1,000 vs 60,000). CCSpan runs 8 times faster on jobs900 than on M ushroom whereas the number of sequences of jobs900 is 9 times smaller (ratio of 0.9). CCSpan runs 915 times faster on jobs1000 than on jobs60000 whereas the number of sequences of jobs1000 is 60 times smaller (ratio 15). We can conclude that the number of sequences exponentially impact the runtime of CCSpan. This result has to be tempered due to specificity of the M ushroom dataset, indeed it is the only dataset that impacts the runtime of CCSpan, while having a support that varies. CCPM runs 18 times faster on jobs900 than on M ushroom (ratio of 2) and 83 times faster on jobs1000 than on jobs60000 (ratio of 1.4). We observe that, contrary to CCSpan, the number of sequences linearly impacts the runtime of CCPM.

Finally, we compare the runtime between CCSpan and CCPM on all datasets. CCPM always greatly outperforms CCSpan in execution time on all the datasets and no matter the support. The ratio is going from 15 on BM S1 Gazelle to 2,175 on jobs60000.

We can conlude that CCPM is only linearly impacted by the number of sequences and their average length and is always significantly faster than CCSPan.

Memory usage We now focus on the evaluation of the memory usage of CC-Span and CCPM (Figure 2b). CCSpan is always more efficient than CCPM in terms of memory usage, except on the M ushroom dataset. We observe that the ratio between CCSpan and CCPM, ranges from 1.25 on BM S1 Gazelle to 2.1 on jobs60000. The difference both algorithms remains rather small, CCSpan and CBIDE are in the same order of magnitude, regarding the memory usage.

CCSpan has an average increase of memory usage of 1.8 with the support variation through all datasets. CCPM has an average increase of memory usage of 1.2 with support variation on all datasets. We observe that both algorithms are really stable; we suppose that it is another added value of the contiguity constraint. This experiment has shown that when mining CCSPs the support variation has almost no impact on both runtime and memory usage, probably due to the contiguity constraint. In addition, the memory usage is extremely stable. CCPM is always significantly faster than CCSpan, regardless the dataset and the support, while having memory usage in the same order of magnitude. Moreover, the runtime of CCPM is linearly impacted by the number of sequences and their average length, contrary to CCSpan. We have thus answered the second scientific question: CCPM scales well on large databases having long sequences. In the previous experiment, CCPM was implemented with no constraint for the sake of comparison with CCSpan. In this section, we show how the wildcards and the starting item patterns impact CCPM. This experiment is conducted on the jobs60000 dataset with a relative support of 0.1% (in order to mine a significant amount of patterns and perform a relevant analysis). In the employment sector, activities are at the core of job offers. An activity is a coherent set of completed tasks organized toward a predefined objective with a result that can be measured. An activity is formalized by action verbs [START_REF] Abboud | Predict the emergence -Application to competencies in job offers[END_REF]. In this context, activities are patterns starting with a verb with a length greater or equal to 3. The starting item constraint is thus defined as the verb category. "Inform clients by explaining procedures", "Manage business by performing related duties" or "Start operations by entering commands" are examples of activities.

We study runtime and activities of CCPM with starting item (SI) and/or wildcards (WC) and compare them to those of CCPM with no constraint. Table 3 shows the results of this experiment. The memory usage (not shown in Table 3) remains stable (about 1000 MBs), whatever is the configuration, the memory used is thus independent of the configuration. CCPM with no constraint mines 14,574 patterns in 49 seconds. 2,947 of them have a length greater or equal to 3 and 882 of them start with a verb, thus CCPM with no constraint mines 882 activities. We observe that CCPM with the starting item (SI) constraint mines 3,828 patterns in 27 seconds and 1,365 of them have a length greater or equal to 3. Therefore, CCPM with starting item mines 3.8 less patterns but the the execution time is only divided by 2. In addition, the SI constraint allows to find 65% more activities. Those two results are the consequence of the backward checking with starting item patterns. Indeed, instead of looking for any item, the function is looking for the first starting item on the left of the pattern, thus taking more time to execute the backward extension checking. In addition, a starting item pattern can have a non starting item closed super-pattern. In this case, the list of patterns mined by a closed contiguous sequential mining algorithm does not contain the starting item pattern. This is the reason why the set of activities mined with the starting item constraint is larger than the set of activities mined without any constraint. Now we evaluate the impact of wildcards on CCPM with and without the starting item constraint. We observe that the use of one, two and three wildcards increases the number of activities mined by respectively 230%, 280% and 307% for CCPM with no starting item and of 260%, 400% and 535% with starting item. Those numbers show that the use of wildcards greatly impacts the number of activities found and confirm that jobs60000 is actually a noisy dataset. Logically, introducing the wildcard constraint also increases the runtime. Recall that the wildcard constraint does not impact the memory usage. Going from no wildcard to one, two and three wildcards, the median and the mode of the length of the activities mined are respectively: 4 & 3; 6 & 3; 11 & 3; 16 & 3. The median length increases with the number of wildcards, but the mode remains stable. An expert of the domain stated that an activity is averagely made up of 3 to 6 words [START_REF] Abboud | Predict the emergence -Application to competencies in job offers[END_REF]. With 2 wildcards, the median reaches 11, patterns are becoming too long. Therefore, the optimal number of wildcards to mine activities in this dataset seems to be 1. To conclude, this experiment shows that the starting item constraint enables to mine a new set of CCSSPs not included in the set of CCSPs. Additionally, this constraint greatly decreases the execution time of CCPM. This experiment also shows that jobs60000 is a noisy dataset and that the optimal configuration of CCPM exploits the starting items constraint and 1 wildcard. So, we answered the first scientific question raised in the introduction: CCPM is a way to more accurately mine patterns in noisy data.

Conclusion

In this paper, we proposed a novel algorithm for mining frequent closed contiguous sequential patterns: CCPM. CCPM can rely on usable wildcards to fit noisy data while preserving the added value of contiguity. The experiments showed that CCPM greatly outperforms CCSpan in execution time, while being competitive in memory usage. In addition, to the best of our knowledge, CCPM is the first algorithm able to efficiently mine closed contiguous sequential patterns in large datasets with long sequences. Hence, CCPM is a solution to the two scientific questions raised in the introduction: 1) How to improve the adaptability of contiguous sequential pattern mining algorithms to more accurately extract information from noisy data? 2) How to increase the efficiency of CCSP mining algorithms to scale with large databases and long sequences? The starting items constraint allows to mine a new set of patterns not included in the set of closed contiguous sequential patterns. In a future work, CCPM will be evaluated on several others datasets with various characteristics. We will also focus on the improvement of the memory usage of CCPM. We will also work on enriching the types of constraint (on multiple items or on a item not necessarily at the start of the pattern) without increasing the execution time.

3 . 2

 32 BI-Directional contiguous closure checking with wildcards. The previous framework mines frequent CSSPWs. To get the set of frequent CCSSPWs, a closure checking has to be used. CCPM closure checking scheme is based on the same BI-Directional design than BIDE. The definitions of backward and forward extensions of BIDE are adapted to CSSPWs with the same number of wilcards for all CSSPWs. Given two CSSPWs P 1 = b 1 b 2 ...b n and P 2 = a 1 ...a m b 1 b 2 ...b n in a sequence database SDB. If sup SDB A (P 1 ) = sup SDB A (P 2 ), a 1 ...a m is called a backward extension of P 1 . The specificity of CSSPW forces the backward extension to be a starting item pattern. Given a sequence S of SDB and a CSSPW P with P c S. For each occurrence of P in S, the backward space of P is the CSSPW Q such that Q = c 1 ...c j and Q, P c S where c 1 is the first starting item on the left of this occurrence of P in S. If there is no starting item on the left of P , P can not have a backward extension. Let P 3 = b 1 b 2 ...b n d 1 ...d k be a CSPW, if sup SDB A (P 1 ) = sup SDB A (P 3 ), we say d 1 ...d k is a forward extension item of P 1 .

  Proof. For each item e k in the projected contiguous database of P , a new CSSPW P k = P, e k can be created, if sup P SDB A (e k ) = sup SDB A (P ) thus sup SDB A (P k ) = sup SDB A (P ) then e k is a forward extension of P .

1Fig. 1 :

 1 Fig. 1: Runtime(a) and Memory(b) on Mushroom, Gazelle, Jobs900, Jobs1000 and Jobs60000 datasets

  a n = b jn . P 1 is called a contiguous sub-pattern or a snippet of P 2 and P 2 a contiguous superpattern of P 1 , denoted by P 1 c P 2 . The concatenation of P 1 and P 2 is a new contiguous sequential pattern, denoted as P 1 , P 2 .

An input sequence database SDB is a set of tuples (sid, S), where sid is a sequence id, and S an input sequence. Table

1

contains an example of a sequence database, made up of 4 tuples and the set of items I = {A, B, C}. The number of tuples in SDB is called the size of SDB and is denoted by |SDB|. The absolute support of a contiguous sequential pattern P α in a sequence database SDB is the number of tuples in SDB that contiguously contain P α , denoted by sup SDB A

Table 1 : An example of sequence database SDB

 1

	Sequence id Sequence
	1	CAABC
	2	ABCB
	3	CABC
	4	ABBCA
	Example 1. We present different sets of patterns from the sequence database
	SDB (shown in Table 1) when min sup = 2 with one wildcard. The complete
	set of frequent contiguous sequential patterns consists of 7 sequential patterns
	S f c = {A : 4, AB : 4, ABC : 3, B : 4, BC : 4, C : 4, CA : 3}. The set
	of frequent closed contiguous sequential patterns consists of only 4 sequential
	patterns S f cc = {AB : 4, ABC : 3, BC : 4, CA : 3}. The complete set

  1, the projected contiguous items of the prefix sequential pattern B are B and C. If a wildcard can be used, all the second adjacent items after P are projected items too. A wildcard is denoted by * on the item it corresponds to. On the previous example, the item A is a projected contiguous item of B with a wildcard, noted A*. A wildcard is not used if the first and the second adjacent items after P are the same. For example, with the prefix sequential pattern A, the projected contiguous items are B and B*, so we only keep B. To summarize, the projected contiguous items with a wildcard of the prefix sequential pattern B in ABBCA are {B, C, A

* }. Definition 2. Projected contiguous database of a prefix sequential pattern with wildcards: The complete set of projected contiguous items in SDB of a prefix sequential pattern P with wildcards is called the projected contiguous database of P with wildcards.

Theorem 1 (Projected database pruning). Given two items e 1 and e 2 , if e * 2 is always a projected contiguous item of P together with e 1 , and if e 2 is never a projected contiguous item, e * 2 can be safely removed from the projected contiguous database.

Table 2 :

 2 Datasets characteristics

	Dataset	#seq. #items avg.len.
	BM S1 Gazelle 59,601	497 2.4
	M ushroom	8,416	119 23.0
	jobs900	900 4,460 26.6
	jobs1000	1,000 8,813 76.0
	jobs60000	60,000 92,394 77.0

Table 3 :

 3

	runtime, patterns of CCPM with constraints
	conf. pattern runtime len>=3 activities
	no con. 14,574	49	2,947	882
	1WC	26,655 142	7,603	2,019
	2WC	29,508 164	10,473	2,489
	3WC	31,817 176	12,782	2,711
	SI	3,828	27	1,365	1,365
	SI&1WC 7,938	42	3,597	3,597
	SI&2WC 9,757	49	5,417	5,417
	SI&3WC 11,649	55	7,308	7,308
	4.3 CCSSPW evaluation.


Raúl García

Raúl García-Castro

Technical and social aspect of semantic interoperability in the IoT Technical and social aspects of semantic interoperability in the IoT

come

Technical and social aspects of semantic interoperability in the IoT


Jonas Olsson
email: jonas.olsson@smhi.se

Lars Gidhagen
email: lars.gidhagen@smhi.se

Akira Kawamura
email: akira.kawamura@tmu.ac.jp

Downscaling of Short-Term Precipitation Time Series for Climate Change Impact Assessment

Keywords: climate model, urban hydrology, SUDPLAN

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

Introduction

Precipitation is often accumulated in time to days, months or years, but in some cases the short-term rainfall is the most interesting. With short-term we mean rainfall observed with a very short time step, e.g. 1 minute or even finer. In contrast to longterm accumulations, which represent averages over long periods, short-term precipitation thus corresponds to the instantaneous intensity (and intensity changes) that we perceive during a storm event.

Short-term precipitation is of particular interest in urban hydrology. Because of the large fraction of impervious surface in the urban environment the runoff process is very fast. Storm water moves rapidly on the surface to a sewer system inlet after which the flow is concentrated in the sewer pipe network. To simulate the flow response to an actual storm in a computer model of the urban environment, a time step of 1 min or shorter is required to capture the variability of the runoff. Thus also the input, i.e. precipitation time series, needs to have a very high time resolution. Such observations are commonly obtained using a tipping bucket gauge that registers a time stamp every time a small amount of rainfall (e.g. 0.2 mm) has accumulated. Further, urban catchments are generally very small, on the order of 1 km², so typically observations from only one gauge is used as input.

Short-term precipitation intensities are expected to increase as a function of the global warming. Both theoretical considerations [START_REF] Trenberth | The changing character of precipitation[END_REF] and climate model projections [START_REF] Larsen | Potential future increase in extreme one-hour precipitation events over Europe due to climate change[END_REF][START_REF] Olsson | Applying climate model precipitation scenarios for urban hydrological assessment: A case study in Kalmar City, Sweden[END_REF] generally support this hypothesis. This implies an increased load on sewer systems with potential consequences in terms of increased overflow volumes and flood risks [START_REF] Semadeni-Davies | The impacts of climate change and urbanisation on drainage in Helsingborg, Sweden: Suburban stormwater[END_REF]. To estimate the consequences quantitatively, sewer model simulations with precipitation input representing the future climate are required. A key problem, however, is that the spatial (and, to a lesser degree, also the temporal) resolution of Regional Climate Models (RCMs) is too coarse for directly applying the precipitation results in sewer system models. Climate model results represent a mean precipitation over an area of typically 1000-2000 km² whereas sewer models, as mentioned above, needs precipitation observed in a single location. Thus, some form of downscaling from the climate model grid scale to the local grid scale is required [START_REF] Olsson | Applying climate model precipitation scenarios for urban hydrological assessment: A case study in Kalmar City, Sweden[END_REF][START_REF] Semadeni-Davies | The impacts of climate change and urbanisation on drainage in Helsingborg, Sweden: Suburban stormwater[END_REF].

In this paper, the method and system for short-term precipitation downscaling used within the project SUDPLAN (Sustainable Urban Development Planner for Climate Change Adaptation) is described. The downscaling is based on the Delta Change concept, i.e. a rescaling of historical observations in line with the expected future changes. The technical solution as well as result visualization is briefly described.

Downscaling Method: Delta Change

Precipitation time series downscaling is performed by Delta Change, which generally means that future changes of some climate variable (e.g. precipitation or temperature), as estimated from climate model data, are transferred to historical observations of the same variable [START_REF] Hay | A comparison of delta change and downscaled GCM scenarios for three mountainous basins in the United States[END_REF]. In the SUDPLAN application, future changes of the frequency distribution of 30-min precipitation intensities, which is the shortest time step available in climate model data, are transferred to historical short-term rainfall observations.

After the historical time series to be rescaled has been defined, the first step in the procedure is to extract 30-min precipitation time series from climate model projections. Data from two 30-year periods are used; one reference period centered over the historical time series and one selected future period. The frequency distribution of the precipitation intensities in each period is calculated, after which the ratio of each future percentiles to the same reference percentile is calculated. This ratio is called Delta Change Factor (DCF; >1 implies increase, and vice versa).

High intensities Low intensities

Fig. 1. Example of future changes of rainfall intensities as estimated from a Regional Climate Model. DCF=1 implies no change, DCF<1 a future decrease and DCF>1 a future increase. Fig. 1 shows an example of DCFs and illustrates how this approach makes it possible to handle rather complicated future changes, such as increased high intensities but decreased intermediate and low intensities (summer in Fig. 1). Fig. 1 also demonstrates the need for performing the downscaling on a seasonal basis, as future changes may be radically different for different seasons. It should be mentioned that the methodology requires an assumption that DCFs estimated from data on the RCM resolutions in time and space are valid also for the higher resolutions of the historical observations.

Finally, the calculated DCFs may be transferred to the historical observations. This is achieved by firstly aggregating the observations to a 30-min time step, to correspond with the climate model output. Secondly a frequency analysis is performed to identify each 30-min value's corresponding percentile and, in turn, DCF. In the last step, the volume of each registration is rescaled in line with the DCF of the corresponding 30-min value. For further details on the approach, see [START_REF] Olsson | Applying climate model precipitation scenarios for urban hydrological assessment: A case study in Kalmar City, Sweden[END_REF]. In SUDPLAN, the data flows and model executions involved in the downscaling are managed by a Scenario Management System (SMS) and a core of Common Services (CS), where the latter includes modules for downscaling of not only precipitation but also air quality and hydrology (Fig. 2). Two types of user specifications are needed to launch a model simulation. (1) CS receives from the SMS the coordinates for the station, the data from which are to be downscaled, together with some identification of the coordinate system and map projection. The user has also specified which climate scenario to use and which future 30-year time period to perform the downscaling for. (2) Short-term rainfall observations from a tipping-bucket gauge or equivalent on a specified format, time stamp (resolution: minute or higher) followed by a rainfall registration (mm).

Technical Solution

The model execution includes the following steps. ( 1) Extraction of 30-min rainfall time series from the CS Scenario Database, in five RCM grid boxes surrounding the station. ( 2) Conversion of historical time series to 30-min time resolution, to be compatible with scenario data. (3) Downscaling by Delta Change, including (i) estimation of future changes from the scenario data and (ii) transfer of the estimated changes to the historical time series. ( 4) Calculation of general rainfall changes from reference period to scenario period. ( 5) Conversion of both historical and downscaled time series to 1-day and 10-min time resolutions, for visualization.

Output and Visualization

The main output is a time series which differs from the uploaded one in two ways. [START_REF] Trenberth | The changing character of precipitation[END_REF] In each time stamp, the observation year has been replaced by a future target year. (2) Each rainfall registration has been re-scaled to account for future changes in the probability distribution of short-term rainfall intensities (Fig. 3).

The automated CS downscaling function has been developed and verified using short-term rainfall data from Kalmar, Sweden, that are well known to the developer and thus optimal for this purpose. Figure 3 shows the first part of the original and downscaled time series. In this data, the gauge resolution was 0.2 mm; thus all original registrations have this value. In the downscaling procedure, the gauge resolution is assumed variable and modified to account for the climate change impact. In this application, a target period 70 years ahead was used, which is reflected in the time stamps (Fig. 3). Fig. 3. Suggested approach for short-term rainfall time series visualization.

Besides the time series, the user will be provided with a table of percentage changes in different key rainfall properties (mean, maximum and frequency), separated into seasons. Further, visualization as outlined in Fig. 4 is suggested. The upper graph Fig. 4. Suggested approach for short-term rainfall time series visualization.

shows daily rainfall on an annual basis, where the year can be selected using a 'year graph slider' below the graph. In the annual graph, by a 'day graph slider' a particular day can be selected and in the lower left diagram, 10-min rainfall during the selected date is shown. If both a reference and a scenario time series are selected, the lower right table shows the general rainfall changes from the reference to the scenario.

Concluding Remarks and Future Prospects

The precipitation time series downscaling functionality in SUDPLAN makes it possible for e.g. sanitation engineers and urban planners to obtain data for climate local change impact assessment studies. The methodology based on Delta Change (DC) a straight-forward and not without limitations. One general limitation is that the downscaled data will be strongly influenced by the properties of the historical data, with respect to e.g. variability. Another limitation is that any change in precipitation frequency is not taken into account in DC-based downscaling. Despite these limitations, in our opinion a DC-based approach is the only practicable solution in an automated system like this.

Future work will include development of the DC-approach to also be able to handle frequency changes. Preliminary analyses indicate that future precipitation frequency changes are generally caused by a change in the number of precipitation events rather than changes in event durations. Thus it may be possible to either remove or multiply observed events, in a clever way, to simulate frequency changes. On a more general level, the spatial resolution of RCMs is rapidly increasing and already results at ~10×10 km and even higher are available. Thus the scale of simulated precipitation is approaching the point scale, conceivably reducing (and ultimately, hopefully, eliminating) the need for subsequent downscaling. Evaluating high-resolution RCM precipitation is thus an important area of future research.

Fig. 2 .

 2 Fig. 2. Components of and data flows between Scenario Management System (SMS) and Common Services (CS) for precipitation downscaling.

Acknowledgments. The study was mainly performed within the SUDPLAN project (EU FP7 ICT-2009-6.4). Additional funding was provided by Tokyo Metropolitan University and the Swedish Research Council Formas, the latter through project HYDROIMPACTS2.0.