Sihem Amer-Yahia

Eric Gaussier

Vincent Leroy

Julien Pilourdault

Ria Mae Borromeo

Motomichi Toyama
email: toyama@keio.jp

Task Composition in Crowdsourcing

Crowdsourcing has gained popularity in a variety of domains as an increasing number of jobs are "taskified" and completed independently by a set of workers. A central process in crowdsourcing is the mechanism through which workers find tasks. On popular platforms such as Amazon Mechanical Turk, tasks can be sorted by dimensions such as creation date or reward amount. Research efforts on task assignment have focused on adopting a requester-centric approach whereby tasks are proposed to workers in order to maximize overall task throughput, result quality and cost. In this paper, we advocate the need to complement that with a worker-centric approach to task assignment, and examine the problem of producing, for each worker, a personalized summary of tasks that preserves overall task throughput. We formalize task composition for workers as an optimization problem that finds a representative set of k valid and relevant Composite Tasks (CTs). Validity enforces that a composite task complies with the task arrival rate and satisfies the worker's expected wage. Relevance imposes that tasks match the worker's qualifications. We show empirically that workers' experience is greatly improved due to task homogeneity in each CT and to the adequation of CTs with workers' skills. As a result task throughput is improved.

I. INTRODUCTION

Crowdsourcing has gained popularity in a variety of domains as an increasing number of jobs are "taskified" and completed independently by a set of workers. Tasks range from simple requests such as transcribing a store receipt, to ones requiring the participation of skilled workers, such as text translation. A central process in crowdsourcing is task assignment, the mechanism through which workers find tasks. In this paper, we advocate the need to complement existing requestercentric and platform-centric task assignment strategies, with a worker-centric approach to task assignment. We examine the problem of producing, for each worker, a personalized summary of tasks that preserves overall task throughput. To the best of our knowledge, this is the first work that addresses worker-centric task assignment and shows the impact of such an approach on the effectiveness of crowdsourcing.

Today, task assignment is achieved by letting workers selfappoint themselves via an interface showing a list of tasks. For example, on Amazon Mechanical Turk (AMT), workers can rank tasks by creation date, reward amount, etc. In practice, workers look for tasks they can easily complete, i.e., that match their skills, and that provide a desired compensation. Indeed, a thorough examination of crowdsourcing forums such as TurkerNation, 1 reveals that workers spend non-negligible 1 http://turkernation.com/ amounts of time discussing how to best select tasks depending on one's goals, which requesters to ban, and which skills are required for the latest tasks on AMT. That calls for rethinking task assignment and developing an approach to find the tasks that best fit workers' preferences. Recent research on task assignment is wither requester-centric or platform-centric, whereby tasks are proposed to workers in order to maximize overall task throughput, result quality, and cost [START_REF] Mavridis | Using hierarchical skills for optimized task assignment in knowledge-intensive crowdsourcing[END_REF], [START_REF] Roy | Task assignment optimization in knowledge-intensive crowdsourcing[END_REF]. These approaches do not take into account workers' preferences. To combine the best of both worlds, we propose to help workers find relevant tasks and enforce the selection of tasks according to their arrival rate. Satisfying workers while keeping in mind the need to optimize task throughput is the challenge we are tackling in this work.

We conjecture that since not every worker is interested in every task, we need to provide a personalized summary of tasks to each worker. We propose to build for each worker, a set of Composite Tasks (CTs) where each CT is valid, i.e., contains tasks that reflect their arrival time and offering a total reward that satisfies the worker's desired compensation and is representative of the set of input tasks. Moreover, we conjecture that workers who come to a crowdsourcing platform with a target reward in mind, expect to see a set of tasks for which they are proficient. Hence, each CT must also be relevant, i.e., containing tasks that match the worker's skills.

The problem of building CTs is inspired from the problem of building composite items (CIs). CIs have been shown to be effective in solving complex information needs such as planning a city tour, selecting books for a reading club, and organizing a movie rating contest [START_REF] Amer-Yahia | Composite retrieval of diverse and complementary bundles[END_REF]- [START_REF] Xie | Breaking out of the box of recommendations: From items to packages[END_REF]. CTs are a form of personalized CIs due to the relevance component. The formulation in [START_REF] Leroy | Building representative composite items[END_REF] has recently been shown to outperform previous work in building valid and representative CIs. We propose to extend it with relevance and express a maximization problem involving similarity between worker and task skills. We find that it is most natural to produce possibly overlapping CTs where each CT constitutes an option for the worker. Therefore, similarly to [START_REF] Leroy | Building representative composite items[END_REF], we rely on fuzzy clustering to produce CTs. Each cluster of CTs is a CT and each task may belong to more than one cluster. Our algorithm differs from the one in [START_REF] Leroy | Building representative composite items[END_REF] in that it solves a 3-way optimization problem where one part aims at identifying task representatives (i.e., cluster centroids obtained through fuzzy clustering), another ensures that the representatives chosen are close to valid CTs, and a last part ensures that the returned CTs are relevant to the worker.

Our user study involving tasks and workers from AMT, demonstrates the superiority of CTs over ranking tasks by creation date or by reward. We study the impact of the level of relevance for workers. We show empirically that improving workers' experience in finding relevant and useful tasks also improves task throughput.

In summary, this paper makes the following contributions:

• We introduce the problem of producing personalized summaries of tasks for a given worker. Our problem is based on building a set of k valid CTs that maximize task representativity and task relevance to a worker. • We define validity that glues together tasks with different arrival rates into a single CT satisfying a worker's desired reward expressed using a summarization vector as follows:

2(tdy), 2(tdy -2), 1(tdy -3), $2

This summarization vector specifies that each CT must contain 2 tasks from today, 2 from 2 days ago and 1 task from 3 days ago, and the total reward for those tasks must be at least $2. Our clustering objective function captures representativity and relevance. Representativity aims at finding the k CTs that cover best the input set of tasks. Relevance is ensured by selecting tasks that match a worker's set of skills. • We design a constraint-based fuzzy clustering algorithm that seamlessly integrates validity, representativity and relevance.

• We run experiments with real workers on AMT and explore the quality of CTs we produce. In particular, we show that our CTs have high quality (validity), provide a good coverage of input tasks (representativity), and are appreciated by workers (relevance). Our experiments validate the conjecture that workers who come to a crowdsourcing platform with a reward in mind, are looking for tasks they are proficient in. Indeed, since each CT contains similar tasks, workers are more likely to quickly complete them than to quickly complete a set of heterogeneous tasks. We also run performance experiments demonstrating that our algorithm scales linearly with different parameters. This paper is organized as follows. Section II introduces our formalization and defines our task composition problem. Section III describes our algorithm. Experiments are provided in Section IV. Related work and conclusion are given in Sections V and VI respectively.

II. MODEL AND PROBLEM

We first define our model and then we formally introduce our problem statement.

A. Model

We are given a set of workers U and a set of microtasks

X = {x 1 , • • • x n } posted by a set of requesters Q = {q 1 , • • • q m }. Skills. S = {s 1 , • • • , s p }
is a set of p skills. A skill could represent a domain/topic of interest or expertise and refers to a required-by-task or acquired-by-worker skill. For example, a translation task requires language skills, a task that gathers school names in a city requires to be familiar with that city, and a task that verifies the presence of some items in an image does not require any particular skill.

Workers. Every worker u ∈ U is defined as:

u = id u , V u , o
where id u is a unique identifier, V u = s u 1 , • • • , s u p is a vector of skill weights for u and each s u j corresponds to u's proficiency in skill s j ∈ S, and o u is the opinion the worker u has regarding requesters and tasks.

Opinion. We adopt the definition in [START_REF] Liu | Automated rule selection for aspect extraction in opinion mining[END_REF] where an opinion o of a worker u is a tuple containing entries of the form (E, F ) where E is an entity and F is a vector of features. According to TurkerNation,2 workers often discuss the requesters they do not want to work with and the skills they do not possess. Hence, we propose to model the opinion o of a worker u as follows: o = (BannedRequesters,

q 1 , • • • ), (U nSkilled, s 1 , • • • )).
Tasks. Every micro-task x ∈ X is defined as follows:

x = id x , V x , d, q, r
where id x is a unique identifier, V x is defined in the same manner as V u , and represents a vector of minimum skill weights required by task x, d is the timestamp representing the creation date of task x, q ∈ Q is the requester who posted task x, and r is the reward of task x.

For example, on AMT, a task that identifies a relation between two named entities in a sentence pays $0.15 and a receipt classification task pays $0.02. Definition 1 (Summarization Vector): Given a set X of micro-tasks, we define our summarization vector as follows:

sv = #t 1 , • • • , #t l , R
where each #t j , 1 ≤ j ≤ l specifies the number of tasks in a given time interval t j and R is a total reward.

A summarization vector indicates which tasks should be made visible to a worker. It depends on the daily arrival rate of tasks and specifies a total reward R. For example, the summarization vector sv = 2(tdy), 1(tdy -1), 1(tdy -3), $2 represents 2 tasks with creation date of today, 1 task with a creation date of yesterday, and 1 task from 3 days ago, with a minimum total reward of $2.

The summarization vector is used to define valid Composite Tasks (CT s).

Definition 2 (Validity): Given a set of tasks X and a summarization vector

sv = #t 1 , • • • , #t l , R , a valid CT = {x 1 , • • • , x g ; x i ∈ X , 1 ≤ i ≤ g},
is a set of tasks such that their arrival date fits the time intervals (i) and the total reward of tasks forming the CT is at least as high as R (ii):

           (i) ∀#t j ∈ sv, g i=1 1(t j , x i .d) = #t j (ii) g i=1 x i .r ≥ R
where 1 is an indicator function which is equal to 1 if the arrival date of the task x i .d belongs to the summarization vector time interval t j and 0 otherwise. g is the number of tasks in the CT and g ≥ n, where n is the number of timestamp values considered. We refer to the set of all valid CTs as V CT .

As an example, assume that we have the summarization vector sv = 2(tdy), 1((tdy -3)&(tdy -2)), $2 and three tasks x 1 , x 2 and x 3 with arrival dates x 1 .d = 2015/06/09, x 2 .d = 2015/06/05, and x 3 .d = 2015/06/09. If today's date is tdy = 2015/06/05 then, 1(t j , x i .d) will assign 1 to tasks x 1 an x 3 and 0 to task x 2 .

Skill Similarity. Skill similarity is measured either between tasks or between tasks and workers. We use an abstract function termed sim() on on V x and V u , the vectors of skills describing tasks and workers, to represent either similarities. Several vector and set similarity functions could be used in practice. In our study, we propose to use Cosine Similarity that returns a value between 0 and 1.

B. Applicability of fuzzy clustering

Our goal is to produce a summary of tasks for each worker. A summary is formed by valid and relevant CTs, and is representative of the set of available tasks. The validity of a CT is expressed in terms of a summarization vector sv = #t 1 , . . . , #t n , R as presented in Definition 2. Its relevance is the adequation between the opinion of the worker and the tasks forming the CT, and is evaluated using sim().

This objective bears a resemblance to the problem of generating representative composite items to summarize heterogeneous item collections [START_REF] Leroy | Building representative composite items[END_REF]. KFC, the algorithm that solves that problem, relies on fuzzy clustering to position k centroids that "cover" the whole dataset. Composite items are then formed in the vicinity of these centroids, which ensures that they provide a good summary of the dataset. In the context of this work, we may want to see a given task in different CTs. Contrary to hard clustering, fuzzy clustering allows each data point to participate to each cluster [START_REF] Bezdek | FCM: The Fuzzy c-Means Clustering Algorithm[END_REF]. Thus, KFC also allows this flexibility.

With KFC, the summaries are valid, representative, and cohesive (e.g., items forming a cluster are geographically close). Our work builds on that and adds the notion of relevance to a worker. Hence, instead of simply providing a summary of the dataset, our goal is to account for the profile of the user to personalize the results. We now state our problem more precisely.

C. Our Problem

Given a worker u, a set of n micro-tasks X , and a summarization vector sv, we define a set of k composite tasks

S u = {CT 1 , CT 2 , • • • , CT k }
where each CT i ⊆ X is a valid composite task and S u optimizes the following objective:

argmax C,W α k j=1 |X | i=1 w m ij sim(x i , c j )+ k j=1 max CTj ∈V CT β x∈CTj sim(x, c j )+ γ x∈CTj sim(x, u) s.t. ∀i ∈ [1, |X |], k j=1 w ij = 1
where C is a set of k centroids, W is a weight matrix of size |X | × k which contains the w ij weights indicating which task belongs to which cluster. α, β, γ are worker-dependent parameters controlling the weight of the optimization objectives, and m ≤ 1 is the weighting exponent used in fuzzy clustering.

The first two components of the objective function are inherited from KFC [START_REF] Leroy | Building representative composite items[END_REF] and capture representativity by choosing tasks x i that are close to the centroid c j of each of the k clusters. Those components serve to identify cluster centroids c j that are representative of the complete dataset, while ensuring that the centroids obtained are close to some valid CT (CT j ). Maximizing the sum of the similarities of all tasks in a CT to its centroid additionally ensures the cohesion of the valid CT considered. It is the compromise between these two components that allows the identification of valid and representative CTs.

The last component, weighted with γ, captures relevance to the worker by comparing similarity between the skill vectors of a task x and the worker u, and provides personalization. Relevance is also enforced by taking into account the opinion of a worker u regarding requesters and skills as follows:

∀CT j ∈ V CT and ∀x ∈ CT j : 1) x.q / ∈ u.o(BannedRequesters) 2) x.V u / ∈ u.o(U nSkilled)
We ensure this property by initially filtering X to remove any task that violates this definition. This allows the algorithm to focus on producing CTs that are representative of tasks that matter to this specific worker, rather than all tasks. We will see in Section IV, how varying α, β, γ, affects the resulting CTs.

III. ALGORITHMIC SOLUTION Our approach to generating CTs builds on a fuzzy clustering algorithm similar to k-means. We first present the main loop of the algorithm, that iteratively updates centroid positions and CTs until convergence. Then we focus on the function that builds a CT around a centroid, and present our greedy approach to solving this problem.

A. Convergence loop

The problem of building composite tasks has similarities with building representative composite items. Thus, our algorithm for building CTs extends the KFC algorithm [START_REF] Leroy | Building representative composite items[END_REF] and adopts the structure of fuzzy clustering, as described in Algorithm 1. Fuzzy clustering starts by initializing C, the set of k centroids to random positions (line 2). W is the weights' matrix representing the participation of each task from X to each cluster. Fuzzy clustering iteratively updates weights (line 6) and centroid positions (line 8) until convergence (line 9) [START_REF] Bezdek | FCM: The Fuzzy c-Means Clustering Algorithm[END_REF]. Similarly to KFC, whenever centroids are updated, a CT is build around each centroid (line 7) in order to update S u , the set of k composite tasks built for the worker u. To select the tasks added to each CT, we rely on a selection function f , which is detailed in Section III-B. Parameter α, β and γ are gradually adjusted to their target values over η cycles (lines 4 and 10). Hence, the algorithm starts by executing a standard fuzzy clustering (α = 1, β = γ = 0), which ensures that centroids are well positioned, before gradually increasing the importance of cohesiveness and personalization in subsequent iterations (line 5).

The update rules for weights and centroids when using cosine similarity are given in [START_REF] Leroy | Building representative composite items[END_REF] (Equations 6 and 7). While our problem definition differs from the one of KFC, the worker personalization term does not involve the position of the centroids, so the update rules are the same. However, the function that builds the CT corresponding to a centroid, represented in Algorithm 1 by f , needs to be adapted to account for the specificities of our problem. We describe that adaptation next.

B. CT selection

We describe in detail the function f that builds the CT corresponding to a centroid position. Because the summarization vector sv considered here has two parts, related respectively to the daily rate and reward (see Definition 1), we rely on two scenarios associated to two different choices for f .

In the first scenario, we restrict ourselves to the daily rate constraint: sv = #t 1 , . . . , #t n , without any minimum reward constraint. In that particular case, it is possible to efficiently compute, for any c j , the CT CT j that maximizes the objective function max

CTj ∈V CT β x∈CTj sim(x, c j ) + γ x∈CTj sim(x, u)
through the following process: 1) Start with an empty CT: CT j ← ∅ 2) For each time interval i = 1 to l, add to CT j the #t i tasks of day type t i that maximize β sim(x, c j ) + γ sim(x, u)

α = α -1-λ η ; β = β + β η ; γ = γ + γ η 5: repeat 6:
Update cluster membership weights W 7:

Update S u by generating CT for each centroid in C using f (Algorithm 2) 8:

Update centroid positions C 9:

until convergence 10: until α = α ∧ β = β ∧ γ = γ 11: S u ← f (C, sv, u) (with the final f and C obtained) 12: return S u 3) Return CT j
The function f defined by the above algorithm has a complexity of O(|X |g) in the worst case, where g is the cardinality of the CT. Indeed, without a reward constraint, maximizing the objective function is akin to a top-g query in which the score of each task is pre-computed. Given a centroid c j , it returns the optimal CT according to the objective function.

In the second scenario, we consider the reward constraint in addition to the daily rate constraint, leading to the general summarization vector: sv = #t 1 , . . . , #t n , R . In that case, one cannot directly use the above approach, as it does not always respect the minimum reward constraint. In fact, finding the optimal CT is NP-hard. The existence of a valid solution however can be easily computed in O(|X |g), by selecting for each time interval the most rewarding task without considering the objective function. We developed an approximate algorithm, described in Algorithm 2, with a O(|X |g 2 ) worst-case complexity for building the CT corresponding to a centroid. Our approach, described in Algorithm 2, always returns a valid CT if it exists. It may not lead to an optimal solution in the sense of our objective function; it will nevertheless yield a valid CT (close to the centroid considered and similar to the worker's skill vector).

C. Our algorithm

Our greedy solution is detailed in Algorithm 2. We assume there exists a solution and that X only contains valid candidates, i.e. candidates from a time interval with a non-zero cardinality constraint. The CT is iteratively built as the set of tasks CT , initially empty (line 1 in Algorithm 2). The main loop of lines 4-15 is executed as long the cardinality constraints are not met. Each of its executions greedily adds a task x to CT . The set X contains the candidate tasks, and the algorithm selects the task x ∈ X that maximizes the expression of line 6, i.e. the task that contributes the most to the objective function. Once CT contains the desired number of tasks for a given time interval, all candidates from the same interval t x are eliminated (line 13), so CT cannot exceed the cardinality constraints. Combined with the termination condition of the loop (line 4), that ensures that CT does not violate the first validity property (Definition 2 (i)). The second validity property, i.e. the reward requirement, is enforced by the auxiliary function FILTER (lines [START_REF] Ambati | Collaborative workflow for crowdsourcing translation[END_REF][START_REF] Bernstein | Direct answers for search queries in the long tail[END_REF][START_REF] Kim | Crowdsourcing step-by-step information extraction to enhance existing how-to videos[END_REF][START_REF] Lasecki | Real-time captioning by groups of non-experts[END_REF][START_REF] Noronha | Platemate: crowdsourcing nutritional analysis from food photographs[END_REF][START_REF] Tuite | Photocity: training experts at large-scale image acquisition through a competitive game[END_REF][START_REF] Ipeirotis | Quality management on amazon mechanical turk[END_REF][START_REF] Kittur | Crowdforge: crowdsourcing complex work[END_REF][START_REF] Kulkarni | Collaboratively crowdsourcing workflows with turkomatic[END_REF][START_REF] Rahman | Task assignment optimization in collaborative crowdsourcing[END_REF][START_REF] Fan | icrowd: An adaptive crowdsourcing framework[END_REF][START_REF] Ho | Online task assignment in crowdsourcing markets[END_REF][START_REF] Karger | Budget-optimal task allocation for reliable crowdsourcing systems[END_REF][START_REF] Assadi | Online assignment of heterogeneous tasks in crowdsourcing markets[END_REF][START_REF] Goel | Mechanism design for crowdsourcing markets with heterogeneous tasks[END_REF][START_REF] Ho | Adaptive task assignment for crowdsourced classification[END_REF]. The goal of this function is to eliminate candidate tasks that, if added to CT , would make it impossible to reach the minimum reward due to the greedy approach. FILTER iterates over all time intervals in the loop of lines 18-30 in order to compute a minimum reward threshold m i for the tasks of this interval. Given a task of interval t i FILTER computes, in a second loop (lines 20-28), the highest reward that could be obtained by selecting the most rewarding tasks for all unallocated task slots in CT . This is done in line 26 by selecting X j , the top-#t j tasks of interval t j in terms of reward. If FILTER is currently evaluating t j (i = j), then only #t j -1 other tasks can be selected. In line 29, all tasks of t i that do not meet the minimum reward threshold m i are eliminated from the set of candidates X. The algorithm uses the FILTER function to update X in line 5 before each addition to CT . This ensures that, despite the greedy approach, CTs generated by this algorithm always meet the reward constraint (Definition 2 (ii)), in addition to the cardinality constraints discussed previously.

IV. EXPERIMENTS

We evaluate the benefits of building Composite Tasks through a study on Amazon Mechanical Turk. We first describe in Section IV-A the options evaluated in this study, with two ranked-lists and two CTs configurations. Then, we present the setup of this experiment in Section IV-B. We evaluate the impact of using CTs on workers in Section IV-C by measuring their likelihood to select tasks presented to them. Finally, we evaluate the impact of CTs on the crowdsourcing platform (Section IV-D) in terms of task throughput and overall execution time.

Summary of results. Overall, we find that building CTs significantly improves the experience of workers, at is gives them direct access to a set of tasks that allows them to meet their reward objective. Personalizing the CTs with respect to the skills of the workers further improves the likelihood that they select one of the tasks returned. This contributes to reducing the time workers spend looking for relevant tasks and allows them to complete more tasks overall. We also find that the use of a summarization vector that reflects arrival rate improves task throughput and reduces starvation problems. We demonstrate that the time required to build CTs increases linearly with the size of the dataset, but that the benefits for workers significantly outweigh the extra computational cost. CT ← CT ∪ {x} 10:

A. Task display options evaluated

X ← X \ {x} 11:

#t x ← #t x -1 12: if #t x = 0 then 13: X ← X \ {x i ∈ X,
m i ← minReward 20:
for all #t j ∈ sv do 21:

if i = j then return X 32: end procedure for which the workers do not have qualifications (unSkilled), and tasks from unwanted requesters (BannedRequesters). The default interface of AMT allows workers to browse tasks as a ranked list. Tasks can typically be sorted by creation date, to find the tasks most recently submitted, or by reward, to access the highest-paying tasks. We refer to those possibilities as CRL and RRL respectively. The ranked-list paradigm constitutes the baseline in our experiments, as it is representative of the system used in a standard crowdsourcing platform. This paper advocates for presenting tasks using CTs built specifically for workers. Tasks are no longer displayed as a flat list, but rather as groups of tasks meeting objectives defined in the summarization vector. These include both constraints on the creation dates of the tasks (platform objective), and on the total reward of tasks within a given CT (worker objective). Options SCT and PCT both build k composite tasks for workers using Algorithms 1 and 2. The difference between them lies in the choice of parameters α, β and γ used in our problem definition. For SCT, we assume that worker skill vectors are unavailable (e.g. a new worker joining the platform). Hence, CTs are valid, coherent and representative, but not personalized to match the skills of the worker receiving them (α = 1 2 , β = 1 2 , γ = 0). In the case of PCT however, we rely on the worker's skill vector to personalize the CTs and make them more appealing (α = 1 3 , β = 1 3 , γ = 1 3 ). Throughout our experiments, we set the number of CTs k to 6, and the fuzziness parameter m to 0.8. This corresponds to moderate fuzziness and significant differences between CTs.

m i ← m i -x ∈ X j x.

B. Setup a) Tasks dataset:

We gather a list of tasks available on AMT using a Web crawler. Every hour, we retrieve the 300 most recent tasks and add them to a database. In practice, this means that we obtain almost all tasks submitted during the crawling period. Over a period of 18 weeks, between July 24 and August 12 in 2015, we obtain a dataset of 25,644 hits from 11,563 distinct hit groups. This dataset is then used to generate different task displays for workers using the 4 different approaches described in Table I. For each task, we record its ID, creation date, title, description, keywords, requester name, reward, time allotted and qualifications. We use LDA [START_REF] Blei | Latent dirichlet allocation[END_REF] on the keywords of tasks in order to discover 15 different topics of tasks. We describe each topic as a bag of words, keeping the 5 most characterizing words. These topics are listed in Figure 1 (keywords selection part). We notice the presence in our datasets of tasks illustrating the typical variety of micro-tasks, with a prevalence of demographic surveys, image tagging tasks, and audio transcription for instance.

b) Worker recruitment: We submit on AMT a first task aimed at recruiting workers. For this user study, we recruited a total of 70 workers. Figure 1 presents a screenshot of this task as seen by the workers. The goal of this task is to build, for each worker participating to the user study, a profile as described in Section II. Each worker selects qualifications from a checkbox list containing 15 options, and indicates her desired reward, banned requesters and banned skills. Here are the 5 topics that are the most popular among workers recruited for this study:

• survey, demographics, psychology, research, study (95%) • easy, picture, cooler, ocmp, image (70%) • photographs, tagging, verbs, easy, tag (56%) Thus, social studies are very popular, and so is annotating videos and images. Conversely, topics related to audio transcription had a low selection rate (15%). This is likely because such tasks require a quiet environment and dedicated equipment to listen to audio files. On average, each worker selected 6.2 topics, with a median at 5.

On average, workers indicated that they expected to earn $1.23 each time they completed tasks on AMT. The standard deviation however is quite high, at $1.24. 50% of the workers indicated a value of $1, with a minimum of $0.10 and a maximum of $10. These very different values confirm that it is important to take each worker's personal objective into account when selecting sets of tasks to display.

After this recruitment phase, each worker is paid $0.10 and is given a unique token in order to move on to the next phase of the study. The reward for this first task is low in order to encourage workers to perform the full study. c) Task display options evaluation: For each worker, we build different task selections and displays according to the options described in Section IV-A. We first eliminate tasks the worker does not qualify for, and requesters the worker bans. Then, we rank tasks according to creation date and reward to produce CRL and RRL. In the case of CTs, we take into account the worker's target reward and skills are taken from the worker's profile gathered in the recruitment phase. The platform objective is the same for all workers, and is set to 2 tasks created in August 2015, and 6 tasks from September and November 2015. Hence, all CTs contain 8 tasks matching this interval distribution. Once these results are ready, we make them available on AMT through an evaluation task. The worker is identified by her unique token, and is presented the options generated from her profile.

We perform an independent evaluation of the task display options, in order to assess the relevance of the tasks they contain (Figure 2). We then compare pairs of display options to better understand the preferences of workers (Figure 3). We discuss the results of this user study in Section IV-C.

At the end of the evaluation, the worker is given a reward of $6.90, which makes the overall compensation for participating to the full study $7.

C. Worker impact 1) Independent evaluation: We first evaluate the 4 task display options independently. Workers are presented with tasks, either as lists (CRL and RRL), or as a set of k = 6 CTs (SCT and PCT) for each option. We ask them to select individual tasks that they would be interested in performing (Figure 2). The average and median task acceptance rates for each option are given in Table II.

CRL performs the worst, as listing tasks by creation date does not seem to bring any benefit to workers. They are willing to perform an average of 30% of tasks, but we note a very high variance. Indeed, some workers accept most tasks, and select many of them no matter the way they are displayed. However, selective workers, who constitute the majority of the workforce in this study, find few relevant tasks (median at 20%). Sorting tasks by reward RRL is an improvement, as it allows workers to reach their reward objective more easily by selecting tasks granting a high reward. With the SCT option, task acceptance rate is 38% on average, with low variance. Despite not being personalized, the CTs generated by SCT have multiple advantages. Each CT is homogeneous as it contains tasks that are similar to each other. This allows workers to quickly assess if they are interested in a whole set of tasks (i.e. the CT), rather than having to independently evaluate individual tasks. Workers also generally prefer performing several tasks of the same type in a row in order to be more efficient. Each CT is representative of a different types of tasks, which allows them to quickly get an overview the different type of tasks currently available on AMT. Workers are presented with sets of similar tasks that, taken simultaneously, let them achieve their reward objective. Hence, workers do not have to skim through long lists of tasks in order to find suitable ones. This finding validates our conjecture that workers who come to the platform with a reward in mind, do indeed look for similar tasks to be efficient. PCT outperforms SCT by 12% on average. This confirms that accounting for worker skills when building composite tasks further improves the relevance of the results presented to the workers, and thus their satisfaction.

2) Comparative evaluation: We then perform a comparative evaluation in which workers are shown simultaneously two task display options, and are asked which one they prefer (Figure 3). In this context, a display option is either the top-8 results of a ranked list (RRL and CRL), or one of the 6 CTs chosen at random (PCT and SCT). Hence, each display option presents 8 tasks to the worker. The pairwise comparison results are given in Table III.

We first compare the two list-based task display options. We notice that workers favor RRL over CRL 55% of the time. This result is consistent with the independent evaluation, which shows that workers are more likely to perform tasks displayed by RRL, as their reward is higher. CT-based display options (SCT and PCT) always significantly outperform listbased options (RRL and CRL). The ratio goes from 79% for PCT against CRL to 87% for PCT against RRL. While the independent evaluation placed SCT relatively close to RRL, that was not the case in the comparative evaluation, as SCT is selected 81% of the time. This experiment shows a clear preference of workers for CT-based display options. Indeed, CTs allow workers to browse coherent sets of similar tasks, grouped together to allow workers to achieve their personal reward goal. This facilitates the tedious operation of browsing and selecting tasks to perform. This experiment also confirms that accounting for the worker's skills when generating CTs is preferable, as PCT is selected over SCT 56% of the time.

D. Platform impact

1) Task throughput: Presenting tasks as ranked list has the drawback of limiting the exposure of some of the tasks to workers. For instance, with CRL, a task can easily be hidden by a batch of more recent tasks submitted by a requester. This causes starvation problems, as these tasks are increasingly less likely to be selected by workers as they become older. Consequently, requesters tend to cancel those tasks and submit identical ones to obtain more recent creation timestamps and increase their visibility. We propose to solve this problem using CTs by letting the platform target specific types of tasks using the CT summarization vector (Section II). In the context of this experiment, the platforms ensures that each CT contains 2 tasks created in August 2015 and 6 tasks from September and November 2015. This solves the problem of starvation by promoting older tasks in the options presented to workers, and can be leveraged by the platform to adapt to varying tasks arrival rate.

We rely on the independent evaluation experiment presented in Section IV-C to measure the throughput of tasks depending on their creation time. Each CT contains 8 tasks that are ranked from the oldest to the most recent. We present in Figure 4 the likelihood of a task of a CT to be selected by a worker with respect to its creation time rank. We observe that this likelihood is quite stable for SCT, and completely even in the case of PCT. This demonstrates that the incorporation of creation time interval constraints in the creation of CTs does not negatively affect the results, as old tasks are as likely to be selected as recent ones. This also indicates that promoting older tasks can be a solution to increasing their visibility and helping reduce the variation in the latency of a task execution. Due to limited information from AMT, we were not able to evaluate extreme cases in which workers are purposely avoiding some very old tasks, because of their low reward for instance. We conjecture that, as long as the pool of tasks in each time interval remains sufficient, these results are valid. To deal with extreme cases, the most unattractive tasks could be discarded from the CT creation step when they have been presented many times but not selected by workers.

2) Execution time: Currently, crowdsourcing platforms display the same ranked list of tasks to all workers. Hence, very few resources are used to maintain this list of tasks. In this paper, we propose to personalize the tasks displayed for each worker. The first step (CRL and RRL) is to eliminate some tasks that do not match worker constraints in terms of skills and requesters. This filtering is relatively low cost, as it only requires reading the top of the global list of tasks until the number of tasks matching the filtering criteria is sufficient. Maintaining CTs however is more costly. In this work, we present an algorithm derived from fuzzy clustering that builds CTs from scratch in a new dataset. In practice, the position of centroids can be used to speed up the execution when adding and removing a few tasks from the dataset. In this experiment, we show that even when building CTs from scratch for each user, the benefits of using CTs outweigh the extra computational cost for the crowdsourcing platform.

In Figure 5, we present the time required to build CTs for different configurations. The first configuration considers the case of 6 CTs of 8 tasks each built using PCT. Then, we double the number of tasks in each CT by altering the summarization vector to obtain 6 CTs of 16 tasks. Finally, we double the number of CTs to obtain 12 CTs of 8 tasks. This experiment is executed on an Intel i7-4870HQ CPU single threaded, and we vary the number of tasks selected initially in order to evaluate the scalability of the algorithm. We observe that the execution time increases linearly with the size of the dataset, which is consistent with the behavior of algorithms derived from k-means. We also observe a linear increase in the execution time with respect to the number of CTs. While the CT selection algorithm presented in Section III-C has a complexity that is quadratic in the number of tasks in a CT, the total execution time is dominated by the main loop of fuzzy clustering, so CT construction overall is not very sensitive to the number of tasks per CT. This execution time is negligible compared to the time it takes workers to perform tasks. This is particularly true as workers are more likely to select tasks contained in CTs. Hence, the platform CPU usage is acceptable.

V. RELATED WORK

To the best of our knowledge, this work is the first to study personalized summaries of micro-tasks for workers. This work is related to building composite items, task decomposition and task assignment in crowdsourcing. We hence summarize the related work in all three areas. a) Composite Items: Composite retrieval was studied with different semantics in recent work [START_REF] Amer-Yahia | Composite retrieval of diverse and complementary bundles[END_REF]- [START_REF] Choudhury | Automatic construction of travel itineraries using social breadcrumbs[END_REF], [START_REF] Xie | Breaking out of the box of recommendations: From items to packages[END_REF]. Most existing algorithms rely on a two-stage process that decouples constraint satisfaction (e.g., a CI must contain one museum and 2 restaurants) from the optimization goal (e.g., each CI is a set of close landmarks in a city). In [START_REF] Leroy | Building representative composite items[END_REF], it was shown that an integrated approach produces better representative CIs than a two-stage approach. We hence build on the approach presented in [START_REF] Leroy | Building representative composite items[END_REF] and extend it to consider our goal, namely, building valid, representative and relevant CTs.

Personalized CIs were proposed in [START_REF] Brilhante | Where shall we go today?: planning touristic tours with tripbuilder[END_REF] to build customized city tours. Tailored itineraries are extracted from Flickr using an objective function that combines POIs popularity with the actual user preferences over POI categories. This approach is not directly applicable to ours since the personalization is merely a filtering of extracted trajectories while in our case, it is the task composition itself that is personalized (using the expected reward). That makes our problem computationally more challenging.

b) Task Decomposition: Crowdsourcing marketplaces such as AMT3 are primarily designed for micro-tasks. Hence, complex tasks must be decomposed into easier sub-tasks [START_REF] Ambati | Collaborative workflow for crowdsourcing translation[END_REF]- [START_REF] Tuite | Photocity: training experts at large-scale image acquisition through a competitive game[END_REF]. For instance, in [START_REF] Kim | Crowdsourcing step-by-step information extraction to enhance existing how-to videos[END_REF], each video annotation task is decomposed into a sequence of sub-tasks, based on a 3stage workflow. To improve the quality of crowd work, the decomposition may also return collections of redundant subtasks [START_REF] Kim | Crowdsourcing step-by-step information extraction to enhance existing how-to videos[END_REF]- [START_REF] Noronha | Platemate: crowdsourcing nutritional analysis from food photographs[END_REF], [START_REF] Ipeirotis | Quality management on amazon mechanical turk[END_REF] and use voting to aggregate workers' responses. Previous work such as CrowdForge [START_REF] Kittur | Crowdforge: crowdsourcing complex work[END_REF] and Turkomatic [START_REF] Kulkarni | Collaboratively crowdsourcing workflows with turkomatic[END_REF], proposed frameworks to design crowdsourcing workflows. Task composition is hence not the reverse operation of task decomposition. The micro-tasks that form a composite task remain small, independent and simple, thus preserving the benefits of task decomposition. c) Task Assignment: While on AMT workers selfappoint themselves to tasks, some recent work studied the task assignment problem whereby tasks are assigned to workers so as to optimize some objective. Examples include the optimization of group design in collaborative crowdsourcing [START_REF] Rahman | Task assignment optimization in collaborative crowdsourcing[END_REF] or quality optimization in online settings [START_REF] Fan | icrowd: An adaptive crowdsourcing framework[END_REF]- [START_REF] Karger | Budget-optimal task allocation for reliable crowdsourcing systems[END_REF]. Other studies assign several tasks to each worker [START_REF] Assadi | Online assignment of heterogeneous tasks in crowdsourcing markets[END_REF]- [START_REF] Zheng | QASCA: A quality-aware task assignment system for crowdsourcing applications[END_REF]. For example, Roy et al. [START_REF] Roy | Task assignment optimization in knowledge-intensive crowdsourcing[END_REF] assign to each worker a number of tasks in a range [X min , X max ] while maximizing the expected quality of crowd work. Zheng et al. [START_REF] Zheng | QASCA: A quality-aware task assignment system for crowdsourcing applications[END_REF] assign to each worker a task featuring k questions picked among n questions posted by a requester. Goel et al. [START_REF] Goel | Mechanism design for crowdsourcing markets with heterogeneous tasks[END_REF] assign each worker a set of tasks in an online context where the objective is to maximize the utility of crowd work under budget constraints. None of the previous studies that assign tasks to a worker focus on defining valid, representative and relevant tasks. Only the optimization of some objective function measuring the quality of crowd work is considered.

VI. CONCLUSION

We presented and validated the first solution that combines requester and platform-centric crowdsourcing with workercentric crowdsourcing. Indeed, to the best of our knowledge, existing work in task assignment is focused on optimizing requester goals such as budget, or platform goals such as task throughput. A thorough examination of TurkerNation4 reveals that workers spend non-negligible amounts of time discussing how to best select tasks depending on one's goals, which requesters to ban, and which skills are required for the latest tasks on AMT. Therefore, we proposed to provide to workers homogeneous sets of tasks, termed Composite Tasks (CTs), that match their profiles and comply with their desired reward. Each CT also complies with task arrival rate as it contains a proportional number of tasks per time period.

We conducted a user study with AMT workers that compared four task display options: two ranked lists of workerrelevant tasks sorted by creation date or by reward, and two sets of CTs, one personalized using the worker's skills and one not. Our findings confirmed the superiority of personalized CTs in satisfying workers and improving task throughput.

We are currently exploring several avenues based on this work. The two short-term goals worth mentioning are: a classification of workers based on their reward and the time they spend completing tasks, and the use of that information to indicate whether CTs should be homogeneous or heterogeneous; the use of workers' feedback during task completion in order to refine their summarization vector. While existing work has focused on incentivizing workers for long-lasting tasks [35] [36] or entertaining workers during task completion [START_REF] Dai | And now for something completely different: Improving crowdsourcing workflows with micro-diversions[END_REF], we would like to focus on learning workers' preferences as they evolve during task completion, and adapt each worker's summarization vector accordingly. This approach would account for the diversity of workers on a crowdsourcing platform and also for the evolution of their expectations during task completion.

ACKNOWLEDGMENT

This work was partially funded by ANR-13-CORD-0020.

  |Xj |=nb,∀x∈Xj ,1(tj ,x.d) x∈Xj x.r 27:

  r

X

  ← X \ {x i ∈ X, 1(t x , x i .d), x.r < m i }

Fig. 1 .

 1 Fig. 1. Recruiting workers

Fig. 2 .

 2 Fig. 2. Independent evaluation task

Fig. 3 .

 3 Fig. 3. Comparative evaluation task

Fig. 4 .

 4 Fig. 4. Task throughput wrt. its creation time rank

Fig. 5 .

 5 Fig. 5. CTs creation time

  Algorithm 1 Algorithm for building CTs Input: set of tasks X , summarization vector sv, α, β, γ, number of iterations η, CT selection procedure f , worker u Output: Set S u of k CTs generated for worker u

1: S u ← ∅; α = 1; β = 0; γ = 0 2: Initialize (e.g. through random assignment) C 3: repeat 4:

  Table I summarizes the different task display options considered in our evaluation. In all cases, we eliminate tasks Algorithm 2 Composite Task selection Input: X , centroid c, worker u, summarization vector sv = #t 1 , . . . , #t n , R , β, γ Output: Set CT , the CT matching centroid c

	1: CT ← ∅
	2: totalReward ← 0
	3: X ← X
	4: while ∃#t i ∈ sv, #t i > 0 do
	5:	X ← FILTER(X, R -totalReward , sv)
	6:	argmax	β sim(x, c) + γ sim(x, u)
		x∈X
	7:	totalReward ← totalReward + x.r
	8:	t x ← t i ∈ sv|1(t i , x.d)

9:

  1(t x , x i .d)}

	14:	end if
	15: end while
	16: return CT
	17: procedure FILTER(X, minReward , sv)
	18:	for all #t i ∈ sv do
	19:

http://turkernation.com/

https://www.mturk.com/

http://turkernation.com/


Martin Kirchgessner

Vincent Leroy

Sihem Amer-Yahia

Shashwat Mishra

Testing Interestingness Measures in Practice: A Large-Scale Analysis of Buying Patterns

come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

Ever since databases have been able to store basket data, many techniques have been proposed to extract useful insights for analysts. One of the first, association rule mining [START_REF] Agrawal | Mining Association Rules between Sets of Items in Large Databases[END_REF], also remains one of the most intuitive. Association rules are often used to summarize consumer trends in a set of transactions or as input to a classifier [START_REF] Sun | Why Big Data Industrial Systems Need Rules and What We Can Do About It[END_REF]. The problem is the very high number of rules, typically in the order of millions. That is exacerbated by the lack of thorough studies of which of the many interestingness measures for ranking rules [START_REF] Geng | Interestingness Measures for Data Mining: A Survey[END_REF] is most appropriate for which application domain. We present CAPA, a framework to compare the rankings that result from applying different interestingness measures to association rules in the retail domain. CAPA relies on a flexible architecture and on jLCM [START_REF] Kirchgessner | jLCM[END_REF], our parallel and distributed pattern mining algorithm that runs on MapReduce. The use of real datasets and a close collaboration with experienced domain experts from Intermarché, one of the largest retailers in France, has led us to select the most relevant measures to rank association rules in the food retail domain.

Our dataset contains 290 million receipts from 1,884 stores in all of France, gathered over one year, 2013. Mining this data results in a huge number of rules. For example, using a minimum support of 1,000 jLCM mines 2,746,418 frequent rules of the form customer segment ! product category. Out of these, 15,063 have a confidence of 50% or higher. Table I shows a ranking of the top-10 rules according to 3 different interestingness measures proposed in [START_REF] Geng | Interestingness Measures for Data Mining: A Survey[END_REF]. If we denote rules as A ! B, confidence is akin to precision and is defined as the probability to observe B given that we observed A, i.e., P (B|A). Piatetsky-Shapiro [START_REF] Piatetsky-Shapiro | Knowledge Discovery in Databases[END_REF] combines how A and B occur together with how they would if they were independent, i.e., P (AB) P (A)P (B). Pearson's 2 , measures how unlikely observations of A and B are independent. This example shows that these measures result in different rule rankings.

The first question we ask ourselves is how different are the rule rankings produced by existing interestingness measures in the retail domain? We examine the rankings produced by 34 measures [START_REF] Geng | Interestingness Measures for Data Mining: A Survey[END_REF], [START_REF] Lenca | Association Rule Interestingness Measures: Experimental and Theoretical Studies[END_REF]. This effort was conducted for 3 mining scenarios designed by experienced analysts from the marketing studies department of Intermarché. In the first scenario, demo_assoc, the analyst provides a target product category and expects rules of the form customer segment ! category, i.e. customers who belong to the described segment purchase products in the target category. In the other two scenarios, the analyst provides a target product p and expects rules of the form set of products ! p. Such rules are either extracted based on a receipt-centric view, where products are grouped by receipt (prod_assoc_t), or based on a customer-centric view, where products are grouped by customer across several receipts (prod_assoc_c). Our first finding is that existing interestingness measures can be automatically grouped into 6 families of similar measures, regardless of the mining scenario.

We then conducted a user study with two experienced domain experts from Intermarché in order to address the following question: out of the 6 families of interestingness measures, which ones are meaningful? Our study lets analysts choose one of 3 mining scenarios along with target products or categories, as well as a (hidden) ranking measure. Their interactions with the resulting list of association rules were observed and their feedback recorded. Overall, ranking rules by decreasing confidence was preferred because of its intuitive nature. Moreover, analysts were willing to trade some confidence (akin to precision) for a significant gain in support (akin to recall). This is achieved by the Piatetsky-Shapiro's measure [START_REF] Piatetsky-Shapiro | Knowledge Discovery in Databases[END_REF]. However, this measure promotes rules containing very frequent products that are interpreted as noise by analysts. This drawback is alleviated by providing the ability to filter out rules containing uninteresting products.

CAPA is made possible with jLCM, our distributed pattern mining algorithm that is able to mine millions of patterns in a few minutes [START_REF] Kirchgessner | jLCM[END_REF]. jLCM can be constrained to focus on different customer demographics and product taxonomies. Thus, in addition to typical associations between products, it finds associations between customer segments and products and between products and categories.

In summary, this paper presents CAPA, a joint effort between researchers in Academia and business experts at Intermarché. The context and goals of the work are provided in Section II. The architecture of CAPA is overviewed in Section III. In Section IV, CAPA is deployed to perform an automatic grouping of measures into 6 groups based on similarities in the rakings they produce. These groups are then evaluated by retail experts in Section V leading to insightful findings. The related work is summarized in Section VI. Planned and possible evolutions are finally discussed in Section VII.

II. CONTEXT A. Dataset

We represent a dataset D as a set of records of the form ht, c, pi, where t is a unique receipt identifier, c is a customer, and p is a product purchased by c. When a customer purchases multiple products at the same time, several records with the same receipt identifier t are generated. The set of receipt identifiers is denoted as T . Each receipt identifier is associated with a unique customer, and multiple receipt identifiers can be associated with the same customer. We do not use product price or product cardinality in this work. The complete dataset contains over 290 million unique receipts, spanning 3.5 billion records, generated at a retail chain consisting of 1,884 stores over the whole year of 2013.

The set of customers, C, contains over 9 million customers. Each customer has demographic attributes. In this study, we focus on 3 attributes: age, gender and location. The attribute age takes values in {<35, 35-49, 50-65, >65} and the attribute location admits French departments as values. Each customer segment is described by a set of user attribute values that are interpreted in the usual conjunctive manner. For example, the segment {< 35 , Paris} refers to young Parisian customers.

We use demo(c) to refer to the set of attribute values of a customer c. For example, {35-49, female, Calvados} represents a 48 year old female from the Calvados department, whom we will refer to as Mary.

The set of products P contains over 200,000 entries, out of which 55,786 have been sold more than a thousand times. Products are organized in a taxonomy with 19,557 nodes over 4 levels. Products are leaf nodes, and belong to all their ancestor categories. The set of categories a product p belongs to is denoted as cat(p). For example, chocolate cream belongs to the categories Fresh food, Dairy, Ultra fresh and Desserts.

B. Mining Customer Receipts

1) Dataset Preparation: Our analysts are interested in studying two kinds of buying patterns: those representing associations between customer segments and a product category (young people in the north of France consume sodas), and those associating a set of products to a single product (people who purchase pork sausage and mustard also buy Riesling). In all cases the analyst specifies B, a set of rule targets.

In the first case, coined demo_assoc, B contains one or more categories. The analyst expects rules of the form customer segment ! category, i.e. customers who purchase products in the target category. The second case comes in two variants: prod_assoc_t, a receipt-centric view where products are found in the same receipt, and prod_assoc_c, a customer-centric view where products are purchased by the same customer over time. In these variants, B only contains products (as opposed to categories in the first scenario) and the analyst expects rules of the form set of products ! target product p 2 B. The dataset D is transformed into a collection of transactions T that is given as input to the mining process, as summarized in Table II. The set T is constructed differently for each scenario.

In demo_assoc, a transaction is a tuple built for each receipt ht, c, pi by associating demo(c) with cat(p). For Mary, the record h234567, Mary, chocolate creami is mapped to the transaction h 35-49, female, Calvados, chocolate cream, Fresh food, Dairy, Ultra fresh, Dessertsi. The number of transactions is equal to |D|, and each transaction contains the segments a customer belongs to, and the categories of the product purchased. In prod_assoc_t, T is built by grouping the records in D by receipt identifier, t. For each t, we generate a transaction as the set of products bought in a single visit to the store {p|ht, c, pi 2 D}. If Mary has a store receipt containing the products cream, yogurt, cola, a transaction containing the 3 products is generated. This leads to a total of |T | transactions, where each transaction is a subset of P. In prod_assoc_c, we generate the set of transactions T by grouping records in D by customer. For each customer " where support T (P ) is the number of transactions in T that contain all items in P . As indicated in Table II, we set the frequency threshold to different values in different scenarios because they differ in the cardinalities of their transactions. Moreover, because marketing actions are decided and applied nation-wide, they are expected to concern at least 1,000 customers, and preferably more than 10,000.

An itemset P is closed iff there exists no itemset P 0 P such that support T (P ) = support T (P 0

) [START_REF] Pasquier | Discovering Frequent Closed Itemsets for Association Rules[END_REF]. The number of closed itemsets can be orders of magnitude less important than the number of itemsets, while providing the same amount of information on T . Several algorithms, including ours, focus on extracting frequent closed itemsets, increasing performance and avoiding redundancy in results [START_REF] Pei | Closet: An Efficient Algorithm for Mining Frequent Closed Itemsets[END_REF], [START_REF] Uno | LCM ver. 2: Efficient Mining Algorithms for Frequent/Closed/Maximal Itemsets[END_REF].

We consider our mining scenarios described in Section II-B1. Each scenario leads to the construction of a collection of transactions T , where a transaction is a set of items. Given T , a frequency threshold ", we find all closed frequent itemsets, and use them to derive association rules [START_REF] Tan | Introduction to Data Mining[END_REF]. Each itemset P implies an association rule of the form A ! B where A, B is a partition of P . A is the antecedent of the rule, and B its consequent. In demo_assoc, A is a customer segment and B is a single product category. In prod_assoc_t and prod_assoc_c, A is a set of products (A ✓ P) and B is a single product. Analysts generally focus on particular products or product categories. This is why they specify the list of targets B in each scenario. Table II contains example association rules extracted from our dataset.

C. Interestingness Measures

Large datasets often contain millions of frequent closed itemsets, and each of them may lead to several association rules. The ability to identify valuable rules is therefore of the utmost importance to avoid drowning analysts in useless information. Association rules A ! B were originally selected using thresholds for support (support

T (A [ B)) and confidence ( support T (A[B)
support T (A) ) [START_REF] Agrawal | Mining Association Rules between Sets of Items in Large Databases[END_REF]. However using two separate values, and guessing the right threshold is not natural. Furthermore, support and confidence do not always coincide with the interest of analysts. Hence, a number of interestingness measures that serve different analyses were proposed in the literature [START_REF] Geng | Interestingness Measures for Data Mining: A Survey[END_REF], [START_REF] Minato | A Fast Method of Statistical Assessment for Combinatorial Hypotheses based on Frequent Itemset Enumeration[END_REF], [START_REF] Liu | Towards Exploratory Hypothesis Testing and Analysis[END_REF]. Table III summarizes the measures we use in this work. The first column contains the name of the measure, the second its expression. The last column will be referred to later.

D. Goal

Our goal is to help analysts test and compare the rankings produced by different interestingness measures on rules extracted from D. An analyst can specify one of 3 mining scenarios, demo_assoc, prod_assoc_t, and prod_assoc_c, and one or several targets (categories in the case of demo_assoc, products in the case of the other two), and CAPA generates as many rule rankings as the number of interestingness measures.

III. ARCHITECTURE

Figure 1 contains the main components of CAPA and their interactions. The first module is acquisition and storage. Sales records are produced locally at each store, and are loaded daily into a data center 1 . Records are stored in a sales table, and are augmented with customer segments coming from the customers table 2 . CAPA's curation module is used to build transactions. The analysts selects a mining scenario and a set of input targets 3 , which are used to generate the appropriate collection of transactions T 4 . CAPA's mining component relies on jLCM, an open-source pattern mining library that we developed [START_REF] Kirchgessner | jLCM[END_REF], to compute a set of association rules matching the input targets 5 . CAPA's exploitation component computes the quality of produced rules according to each interestingness measure 6 , and loads them into a database. Results are presented to the analyst through a web application 7 . We now describe the details of CAPA.

A. Acquisition and storage

Each of the 1,884 stores locally maintains a log of all customer transactions completed during the day. Whenever a customer checks out, a receipt is generated, indicating the list of products purchased, their price, as well as potential discounts. These receipts are logged under the form of hr, c, pi triples and stored in a write-ahead log. Once a day, during the store's closing time, this log is transmitted to the main data center that centralizes all sales records.

Measure Formula Group and description

One-Way Support P (B|A) ⇥ log2 P (AB)

P (A)P (B)
Relative Risk P (B|A)/P (B|¬A) Odd Multiplier (P (AB)P (¬B))/(P (B)P (A¬B)) Zhang Odds Ratio ⌃ (P (AB)P (¬A¬B))/(P (A¬B)P (B¬A)) Information Gain ⇤ log(P (AB)/(P (A)P (B)))

Highest confidence Lift ⇤ P (AB)/(P (A)P (B)) P (A)P (B)+P (¬A)P (¬B) ⇥ 1 P (A)P (B) P (¬A)P (¬B) 1 P (AB) P (¬B|¬A)

G1

G6

Highest recall Favors rare targets

We rely on YARN [START_REF] Vavilapalli | Apache Hadoop YARN: Yet Another Resource Negotiator[END_REF] to administer the cluster storing sales records. Data is stored in an HBase database [START_REF]The Apache Software Foundation[END_REF], and processed using the MapReduce framework [START_REF] Dean | Mapreduce: Simplified Data Processing on Large Clusters[END_REF]. Sales records are stored in the sales table. To avoid redundancy and ease data processing, records are grouped by receipt before being stored in sales. Thus, each receipt is a line in the table, and the content of the receipt is stored in the meta column family. We leverage HBase's flexibility on columns by recording each product identifier as a column qualifier, with information such as the cardinality and the unit-price as a value. The row key of each receipt is defined as storeId-day-customerId-receiptId. The sales table is configured to be sorted by row key. This allows operations such as selecting the sales records of a given store to be efficiently performed in a single scan, while selecting a specific time period can also be done by combining 1,884 ranges (one per store identifier). Given that customer purchases may vary between geographical areas [START_REF] Mishra | Discovering characterizing regions for consumer products[END_REF] and over time, these operations are frequently used by analysts. This data layout is optimized to perform these selections without incurring unnecessary reads. That enables storage of large amounts of data without increasing the cost of analyzing a fixed number of records. Sales logs transferred from the stores are first stored on the distributed file system HDFS, and then loaded into HBase using MapReduce, as a daily batch job.

Each customer constitutes an entry in the customers table, which records the segments she belongs to. After loading the sales records into the database, we enrich the sales table using another MapReduce job. For each new record, the receipt is augmented with the user segments by querying the customers table and copying these segments to the meta column family in sales. Hence, each sales record is assigned a snapshot of the user information at the time the receipt was generated.

B. Curation

As described in Section II-B1, mining customer receipts begins with the construction of a transactions dataset T following the requirements of the analyst. This operation is performed using MapReduce jobs executed on the sales table. In the case of demo_assoc, a single map operation is sufficient. The product taxonomy is loaded in memory by all mappers through the distributed cache, and, given a row, for each product registered in the products column family, a transaction containing its categories is generated. Customer segments are directly available in the meta column family thanks to the enrichment phase and are added to the transactions. As described in Section III-A, records are already grouped by receipt when stored in sales, thus no further processing is necessary for an analysis in prod_assoc_t. Each line of sales generates one transaction containing the set of products. In prod_assoc_c, the products bought by a given customer are grouped using a reduce operation with the customer identifier as a key to generate a transaction. In all cases, at the end of this phase the dataset T is stored on HDFS as a text file, with one line per transaction.

C. Mining 1) Extracting itemsets using jLCM: Generating association rules, presented in Section II-B2, firstly requires the extraction of frequent itemsets from T . We rely on jLCM, available as an open-source library [START_REF] Kirchgessner | jLCM[END_REF]. jLCM is integrated in a MapReduce job. The itemset extraction job scans the input T once in the map function, and builds for each target item b in B, a filtered dataset limited to transactions containing b:

T {b} = {E 2 T , b 2
E}.This is done using the target items from B as intermediate keys for the reduce function. For each target, reduce executes jLCM on its filtered dataset. jLCM is a recursive algorithm that enumerates itemsets and computes their frequency. Closed itemsets are returned along with their support, with the exception of singletons that cannot produce association rules. In demo_assoc, itemsets should contain a single category only, so all categories except the target one are removed from transactions.

This technique allows us quickly obtain itemsets that satisfy our constraint, i.e. all itemsets contain one of the targets from B. The job's run-time is dominated by the scan of T in the map phase, which can be accelerated by the addition of worker nodes. On average, each reduce task completes in 10 seconds.

2) Evaluating relevant association rules: Analysts aim at uncovering interesting association rules expressed as A ! B. Evaluating the interestingness of an association rule requires computing the support of itemsets A, B and A [ B in T . The standard method for mining association rules consists in finding all frequent itemsets in the dataset, and then generating the rules. Given that our analysts have specified a restricted set of targets B, this approach would be wasteful. This motivates our distribution of the itemsets extraction, presented in the previous sub-section. Our itemsets extraction job gives the support of B and A [ B for all association rules we are interested in (i.e. all B satisfy B = {e}, e 2 B). This job also materializes, as a prefix tree in a side-output file, the set A of all antecedent itemsets, whose support needs to be evaluated.

A second MapReduce job completes the evaluation of association rules. Each map operation reads a transaction of T and counts the support all association rules' antecedents. The reduce phase uses itemsets in A as intermediate keys and sums partial counts to obtain the total support. This two-step approach avoids the computation of many itemsets that never appear as a rule antecedent.

D. Exploitation

The quality measures selected require at most P (A), P (B) and P (A [ B) to be computed, because, given |T |, other probabilities like P (B|A) or P (A¬B) can be derived from them. Therefore, we denormalize the results of the mining phase in order to store those 3 probabilities with each A and B. The supports of all rules' antecedents (providing P (A)) are centralized and joined to the results of jLCM (which provides P (AB) and P (B)). After this denormalization, each row represents an association rule and has enough information to compute its score. This table is then augmented with 34 columns, one for each measure implemented in CAPA, and listed in Table III. Because large numbers are involved, for Fisher's exact test we actually use the logarithm of the binomial coefficients, which are computed as logarithms of the gamma function. This makes the calculation feasible, but requires long iterations so we do it in parallel again (this is easy to implement thanks to the denormalization). The complete table is stored in a relational database.

The final component of CAPA is a web application allowing the analyst to explore this augmented table. In any scenario, the analyst picks a measure and selects a target product or category, or a set of target products or categories. Association rules are then returned in a table and sorted according to the selected measure. A rule like yogurt ! cheese is displayed with 3 values: support (number of customers who bought both cheese and yogurt), confidence (fraction of yogurt buyers who also bought cheese), recall (fraction of cheese buyers who also bought yogurt). During the user study these figures help analysts quickly judge the volume of sales for each rule.

IV. EMPIRICAL EVALUATION

We present an empirical evaluation of the 34 measures for association rules introduced in Section II-C. Recall that our goal, stated in Section II-D, is to assist the analyst in selecting measures. Our evaluation consists in comparing rankings produced by these measures on retail data to discover which measures differ significantly in practice. We then use that similarity to classify ranking measures into groups. We annotate these groups based on the properties common to the group. We discuss key insights obtained from experimentation on each group. The goal of this evaluation is to automatically detect similarities between interestingness measures and reduce the number of candidate measures to present to analysts in the user study (Section V).

We first present in Section IV-A methods used to compare ranked list. Then, we compare the resulting rankings in Section IV-B). We conclude the empirical evaluation with the selection of representative measures in Section IV-C.

A. Ranking similarity measures

In this section, we discuss some methods for comparison of ranked lists. The first three methods are taken from the literature. We then introduce NDCC, a new parameter-free ranking similarity designed to emphasize differences at the top of the ranking.

We are given of a set of association rules R to rank. We interpret each measure, m, as a function that receives a rule and generates a score, m : R ! R. We use L m R to denote an ordered list composed of rules in R, sorted by decreasing score. Thus,

L m R =< r 1 , r 2 , . . . > s.t. 8i > i 0 m(r i ) < m(r i 0
). We generate multiple lists, one for each measure m, from the same set R. L m R denotes a ranked list of association rules according to measure m where the rank of rule r is given as

rank(r, L m R ) = |{r 0 |r 0 2 R, m(r 0 ) m(r)}|.
To assess the dissimilarity between two measures, m and m 0 , we compute the dissimilarity between their ranked lists, L m R and L m 0 R . We use r m as a shorthand notation for rank(r, L m R ). 1) Spearman's rank correlation coefficient: Given two ranked lists L m R and L m 0 R , Spearman's rank correlation [START_REF] Daniel | Applied Nonparametric Statistics[END_REF] computes a linear correlation coefficient that varies between 1 (identical lists) and 1 (opposite rankings) as shown below.

Spearman(L m R , L m 0 R ) = 1 6 P r2R (r m r m 0 ) 2 |R|(|R| 2
1) This coefficient depends only on the difference in ranks of the element (rule) in the two lists, and not on the ranks themselves. Hence, the penalization is the same for differences occurring at the beginning or at the end of the lists.

2) Kendall's ⌧ rank correlation coefficient: Kendall's ⌧ rank correlation coefficient [START_REF] Kendall | A New Measure of Rank Correlation[END_REF] is based on the idea of agreement among element (rule) pairs. A rule pair is said to be concordant if their order is the same in L m R and L m 0 R , and discordant otherwise. ⌧ computes the difference between the number of concordant and discordant pairs and divides by the total number of pairs as shown below.

⌧ (L m R , L m 0 R ) = |C| |D| 1 2 |R|(|R| 1) C = {(r i , r j )|r i , r j 2 R ^i < jŝ gn(r m i r m j ) = sgn(r m 0 i r m 0 j )} D = {(r i , r j )|r i , r j 2 R ^i < jŝ
gn(r m i r m j ) 6 = sgn(r m 0 i r m 0 j )} Similar to Spearman's, ⌧ varies between 1 and 1, and penalizes uniformly across all positions.

3) Overlap@k: Overlap@k is another method for ranked lists comparison widely used in Information Retrieval. It is based on the premise that in long ranked lists, the analyst is only expected to look at the top few results that are highly ranked. While Spearman and ⌧ account for all elements uniformly, Overlap@k compares two rankings by computing the overlap between their top-k elements only.

Overlap@k (L m R , L m 0 R ) = |{r 2 R | r m  k ^r m 0  k }| k 4) Normalized Discounted Correlation Coefficient:
Overlap@k, Spearman's and ⌧ sit at two different extremes. The former is conservative in that it takes into consideration only the top k elements of the list whereas the latter two take too liberal an approach by penalizing all parts of the lists uniformly. In practice, we aim for a good tradeoff between these extremes.

To bridge this gap, we propose a new ranking correlation measure coined Normalized Discounted Correlation Coefficient or NDCC. NDCC draws inspiration from NDCG, Normalized Discounted Cumulative Gain [START_REF] Järvelin | Cumulated Gain-based Evaluation of IR Techniques[END_REF], a ranking measure commonly used in Information Retrieval. The core idea in NDCG is to reward a ranked list L m R for placing an element r of relevance rel r by relr log r m . The logarithmic part acts as a smoothing discount rate representing the fact that as the rank increases, the analyst is less likely to observe r. In our setting, there is no ground truth to properly assess rel r . Instead, we use the ranking assigned by m 0 as a relevance measure for r, with an identical logarithmic discount. When summing over all of R, we obtain DCC , which presents the advantage of being a symmetric correlation measure between two rankings L m R and L m 0 R .

DCC (L m R , L m 0 R ) = X r2R 1 log (1 + r m 0 ) log (1 + r m )
We compute NDCC by normalizing DCC between 1 (identical rankings) and 1 (reversed rankings).

NDCC (L m R , L m 0 R ) = dcc avg max avg where dcc = DCC (L m R , L m 0 R ), max = DCC (L m 0 R , L m 0 R ) min = DCC (L⇤, L m 0 R ), L⇤ = rev (L m 0 R )
avg = (max + min)/2 5) Ranking comparison by example: We illustrate the difference between all ranking correlation measures with an example in Table IV. This shows correlation of a ranking L 1 with 3 others, according to each measure. NDCC does indeed penalize differences at higher ranks, and is more tolerant at lower ranks.

B. Rankings comparison

We perform a comparative analysis of ranking measures, on our 3 mining scenarios summarized in Table II. We generate association rules A ! B where B is a single product among a set of 64 previously studied by analysts. Overall we obtain 1,651,024 association rules, and we compute one rule ranking per product and per interestingness measure. Our first observation is that the results we obtain for all scenarios lead to the same conclusions. Therefore, we only report numbers for prod_assoc_c. While all measures are computed differently, we notice that some of them always return the same ranking for association rules of a given target. We identify them in Table III using symbols. Other notable similarities include Sebag-Schoenauer and lift (89% of rankings are equal), as well as Loevinger and lift (87%). This difference between the number of interestingness measures considered (34) and the number of different rankings obtained (25) can easily be explained analytically in the case of a fixed target. Indeed, for a given ranking, P (B) is constant, which eliminates some of the differences between interestingness measures. In addition, some measures only have subtle differences which only appear when selecting extreme values for P (A), P (B) and P (AB), which do not occur in practice in our retail dataset.

1) Comparative analysis: We now evaluate similarity between interestingness measures that do not return the same rankings. We compute a 34 ⇥ 34 correlation matrix of all rankings according to each correlation measure described in Section IV-A, and average them over the 64 target products. This gives us a ranking similarity between all pairs of measures. We then rely on hierarchical clustering with average linkage [START_REF] Sokal | A Statistical Method for Evaluating Systematic Relationships[END_REF] to obtain a dendrogram of interestingness measures and analyze their similarities. The dendrograms for NDCC and ⌧ are presented in Figure 2. For better readability, we merge sub-trees when correlation is above 0.9. To describe the results more easily, we partition interestingness measures into 6 groups, as indicated in the third column in Table III.

G

1 is by far the largest group: in addition to 4 measures that always generate the same rankings, 14 other measures output similar results. A second group, G 2 , comprising 2 measures, is quite similar to G 1 according to NDCC . ⌧ also discovers this similarity, but considers it lower, which shows that it is mostly caused by high ranks. Jaccard is as a slight outlier in G 3 according to NDCC . Indeed, when focusing on the first 20 elements (Overlap@20), only an average of 71% are shared between Jaccard and the rest of G 3 . This situation also occurs between Klosgen and the rest of G 5 . Interestingly, we observe that, according to NDCC , G 5 is closest to G 6 and is negatively correlated with the other groups. However, according to ⌧ , G 5 is very similar to G 4 and is negatively correlated with G 6 . This difference between ranking measures illustrates the importance of accounting for rank positions. When the top of the ranking is considered more important, some similarities emerge.

We illustrate this behavior in Figure 3 by displaying correlation between rankings obtained with different interestingness measures. This experiment clearly shows that overall, cosine (G 4 ) is closer to specificity (G 5 ) than Gini (G 3 ), as the rank difference observed in the results is overall smaller. However, when focusing on the top-10 results of cosine, Gini assigns closer ranks than specificity. This explains the difference in clustering between NDCC /overlap and ⌧ /Spearman.

2) Annotating groups: While using hierarchical clustering on interestingness measures allows the discovery of families of measures, and their relative similarity, it does not fully explain which types of results are favored by each of them. We propose to compare their outputs according to the two most basic and intuitive interestingness measures employed in data mining: recall and confidence. recall represents the proportion of target items that can be retrieved by a rule, that is, P (A|B). Its counterpart, confidence, represents how often the consequent is present when the antecedent is, that is, P (B|A). We present, in Figure 4, the average recall and confidence of the top-20 rules ranked according to each interestingness measure. G 1 contains confidence, so it is expected to score the highest on this dimension. G 2 is extremely close to G 1 , but obtains slightly lower confidence and recall. We then have, in order of increasing recall and decreasing confidence G 3 , G 4 and G 5 . Finally, G 6 , which contains recall, obtains the highest recall but the lowest confidence. Figure 4 also shows that executing a Euclidean distance-based clustering, such as k-means, with recall/confidence coordinates would lead to groups similar to the ones obtained with hierarchical clustering. Hence, this analysis is consistent with the hierarchical grouping and the correlation with NDCC .

While we believe that NDCC better reflects the interpretation of analysts browsing rules, it is important to note that the grouping of interestingness measures created through this evaluation is stable across all 4 correlation measures and for all 3 scenarios. Correlation between different families of measures may vary, but measures within a single family always have a high similarity. Thus, we conjecture that the obtained results are true in the general case of food retailers and we can rely on these groups to reduce the number of options presented to analysts.

C. Selecting representative measures

We summarize the findings of the comparative evaluation in the last column of Table III. We identify 6 families of measures that behave similarly. Each family offers a different trade-off in terms of confidence and recall, and thus ranks association rules differently. We select the quality measure that most represents each family of measures (i.e. with highest average similarity) in order to confront the results of this analysis with the opinion of domain experts in our user study. Taking a general data mining perspective leads us to considering G 3 and G 4 as the most promising families for finding interesting association rules. Indeed, it is important to achieve a good trade-off between recall and confidence in order to find reliable association rules that can be applied in a significant number of cases. Hence, F1 score, that combines recall and confidence, would prefer G 3 and G 4 to others. V. USER STUDY We now report the results of a user study with domain experts from Intermarché. The goal of this study is to assess the ability of interestingness measures to rank association rules according to the needs of an analyst. As explained in Section IV, we identified 6 families of measures, and selected a representative of each group for the user study (their names are in bold in Table III). We rely on the expertise of our industrial partner to determine, for each analysis scenario, which family produces the most interesting results. This experiment involved 2 experienced analysts from the marketing department of Intermarché. We setup CAPA and let analysts select targets multiple times in order to populate the web application's database with association rules (Section III-D). We let our analysts interact with CAPA without any time restriction, and collect their feedback in a free text form.

Each analyst firstly has to pick a mining scenario among demo_assoc, prod_assoc_t, or prod_assoc_c. Then she picks a target category or a target product in the taxonomy. In prod_assoc_t and prod_assoc_c, she also has the option to filter out rules whose antecedent products are not from the same category as the target. Finally, she chooses one of our 6 ranking measures to sort association rules. Neither the name of the measure nor its computed values for association rules are revealed, because we wanted analysts to evaluate rankings without knowing how they were produced.

Resulting association rules are ranked according to a selected measure. Each rule is displayed with its support, confidence and recall, such that analysts can evaluate it at a glance. For each scenario, our analysts are asked which representative measure highlights the most interesting results (as detailed below, in all cases a few of them were chosen).

A. Scrolling behavior

Once the analyst selects a target, all matching rules are returned. The initial motivation of this choice was to determine how many results are worth displaying and are actually examined by the analysts. According to the follow-up interview with the analysts, they carefully considered the first ten results, and screened up to a hundred more. Interestingly, analysts mentioned that they also scrolled down to the bottom of the list in order to see which customer segments are not akin to buying the selected category. For example, when browsing demographic association rules, they expected to find {50-64} ! pet food among top results, but also expected {<35, Paris} ! pet food among bottom results. This confirms that all rules should remain accessible. This also indicates that while interestingness measures favor strong associations, it could also be useful to highlight anti-rules.

B. Feedback on ranking measures

We let marketing experts explore all 3 scenarios and express their preference towards groups of measures.

In the demo_assoc case, G 1 and G 3 were both highly appreciated. G

1 favors rules such as {< 35, M, Oise} ! Flat and Carbonated drinks. These rules are very specific and thus have a very high confidence (31,58 % in this particular case). However, this comes at the cost of recall (0,08 %). Experts involved in this study value confidence much more than recall, as their priority is finding rules that they consider reliable. A low support is not necessarily an issue, and can lead to the discovery of surprising niche rules that can be exploited nonetheless. As discussed in Section IV-B2, G 3 offers a more balanced trade-off between confidence and recall, and prioritizes rules such as {< 35, *, *} ! Baby food (confidence 8,57 %, recall 37,61%). These rules are interesting because they capture a large fraction of the sales of a given category, but are less reliable and generally less surprising.

G

2 and G 4 were considered as less interesting than G 1 and G 3 respectively. Their results offer similar trade-offs, but with lower confidence each time. G 5 and G 6 were considered unusable because of their very low confidence.

When experimenting with prod_assoc, we observed a slightly different behavior. By default, the analysts favored G 1 and G 2 because of the confidence of their results. Then, we offered the analysts the possibility of filtering the rules to only keep the ones in which the antecedent contains products from the same category as the target. This led to analysts favoring G 3 and G 5 . This difference is caused by an important criterion: the ability of a measure to filter out very popular products. For example, the rule {van. cream, emmental}! choc. cream usually appears just above its shorter version {van. cream}! choc. cream, because the first one has a confidence of 32% and the second 31%. However, experts prefer the second one, because emmental (cheese) is among the heavy hitters in stores. Its addition to the rule is hence considered insignificant. This "noise" generally increases with recall. Hence, when no filtering is available, G 1 is selected, but analysts prefer the recall and confidence trade-off provided by G 3 and G 5 . Again, G 4 suffered from its proximity to G 3 with lower confidence, while G 6 's confidence was too low. In all cases, analysts mentioned G 6 as uninteresting because it selects rules of low confidence. In general, sorting by decreasing lift (which is close to sorting by decreasing confidence) is the preferred choice. Combined with the minimum support threshold used in the mining phase, this ranking promotes rules that are considered reliable. However, in the case where analysts are given the ability to filter out noisy products (very frequent ones), they prefer the ranking produced by Piatetsky-Shapiro's measure [START_REF] Piatetsky-Shapiro | Knowledge Discovery in Databases[END_REF]. That could be explained by the fact this measure provides a good compromise between confidence and support. The noisy products that this measure may introduce can be filtered out by analysts.

VI. RELATED WORK

To the best of our knowledge, CAPA targets datasets which are orders of magnitude bigger (and sparser) than those tested in existing work on ranking association rules. This paper is also the first to complement an algorithmic comparative analysis with a user study involving domain experts.

The definition of quality of association rules is a wellstudied topic in statistics and data mining. In their survey [START_REF] Geng | Interestingness Measures for Data Mining: A Survey[END_REF], Geng et al. review 38 measures for association and classification rules. They also discuss 4 sets of properties like symmetry or monotony, and how each of them highlights different meanings of "rule quality", such as novelty and generality. However, we observe no correlation between these properties and the groups of measures discovered using CAPA.

These 38 measures are compared in [START_REF] Le | Beyond Support and Confidence: Exploring Interestingness Measures for Rule-Based Specification Mining[END_REF]. Authors consider the case of extracting and ranking temporal rules (event A!event B) from the execution traces of programs. Each measure is evaluated in its ability to rank highly rules known from a ground truth (library specification). We observe that the measures scoring the highest are all from the groups identified in this work as G 1 and G 3 , which are also favored by our analysts. There are however some counterexamples, with measures from G 1 scoring poorly. The main difference between CAPA and [START_REF] Le | Beyond Support and Confidence: Exploring Interestingness Measures for Rule-Based Specification Mining[END_REF] is the absence of a ground truth of interesting rules for our dataset. Thus, our evaluation of measures is first comparative, with 4 correlations measures covering both the top of the ranking and the entire ranked list. The differences in the results obtained also highlight the importance of performing domain-specific studies, as properties of data and expectations of analysts vary significantly.

The closest work to ours is HERBS [START_REF] Lenca | Association Rule Interestingness Measures: Experimental and Theoretical Studies[END_REF]. HERBS relies on a different and smaller set of measures to cluster rule rankings. Authors perform an analysis of the properties of measures, in addition to an experimental study. The datasets used are from the health and astronomy domains. Each of them contains at most 1,728 transactions and leads to the extraction of 49 to 6,312 rules. Rankings are then compared between all pairs of measures using Kendall's ⌧ correlation measure averaged over all datasets. The largest group of measures identified, which includes confidence, is quite similar to G 1 . However, there are also significant differences. For instance, we find G 2 and G 6 to be very different, while [START_REF] Lenca | Association Rule Interestingness Measures: Experimental and Theoretical Studies[END_REF] considers the measures of this group similar. The authors observe a weak resemblance between the theoretical and experimental analysis of the measures. CAPA is entirely focused on retail data, which has different properties and contains millions of transactions and rules. We also consider more interestingness measures, and 4 different ranking correlation measures instead of 1.

Our use of the p-value (via Pearson's 2 test) in the evaluation of rule interestingness is borrowed from [START_REF] Liu | Towards Exploratory Hypothesis Testing and Analysis[END_REF]. A low p-value shows a correlation between a rule's antecedent and consequent. The use of Fisher's exact test on association rules is inspired by [START_REF] Minato | A Fast Method of Statistical Assessment for Combinatorial Hypotheses based on Frequent Itemset Enumeration[END_REF]. Both of these works aim at finding highly-correlated itemsets, which requires the analyst to set a threshold on the p-value. This is common practice in biology, but less meaningful in the retail industry. In [START_REF] Liu | Towards Exploratory Hypothesis Testing and Analysis[END_REF], Liu et al. also propose an exploration framework where rules are grouped by consequent, then traversed by progressively adding items to the antecedent. The framework provides hints to help guess how each additional item would make a difference. Such a framework is suitable to some of the scenarios we consider and could be integrated in a future version of CAPA.

VII. SUMMARY AND EVOLUTIONS

In this paper, we present CAPA, a framework for mining association rules from large-scale retail data. We defined 3 mining scenarios allowing analysts to extract associations between user segments and product categories, or products themselves. Given a scenario, CAPA builds a dataset of transactions and mines in parallel association rules containing target products chosen by analysts. Our main contribution is the study of 34 interestingness measures for ranking rules. We first performed an analytical and an empirical comparison between different rule rankings and grouped measures into 6 families. Resulting groups were then evaluated in a user study involving retail experts. We concluded that lift and Piatetsky-Shapiro best fit the needs of analysts, as they ensure high confidence. Our user study also led us to thinking about the extraction of negative results (anti-rules). We are currently studying how to add and rank negative rules.

ACKNOWLEDGMENT

This work was partially funded by the Datalyse PIA project.

P

  (AB) P (A)P (B) max(P (AB)P (¬B),P (B)P (A¬B))Yule's Q ⌃ P (AB)P (¬A¬B) P (A¬B)P (B¬A) P (AB)P (¬A¬B)+P (A¬B)P (B¬A)

3 Fig. 1 .

 31 Fig. 1. Overview of the architecture

Fig. 2 .

 2 Fig. 2. Hierarchical clustering of interestingness measures for a single target

Fig. 4 .

 4 Fig. 3. Rank correlations

TABLE I TOP

 I -5 DEMOGRAPHICS ASSOCIATION RULES, ACCORDING TO DIFFERENT INTERESTINGNESS MEASURES. RULES ARE DENOTED {AGE, GENDER, DEPARTMENT} ! product category. PRODUCT CATEGORIES WERE TRANSLATED TO ENGLISH, FRENCH DEPARTMENTS WERE LEFT UNCHANGED.

	by confidence {> 65, F, Aube} {> 65, F, Aveyron} {> 65, F, Val de Marne} {> 65, F, Seine S t Denis} {> 65, F, Haute Saone}	! Dairy ! Dairy ! Dairy ! Dairy ! Dairy	by Piatetsky-Shapiro [5] {⇤, ⇤, Nord} ! Liquids {⇤, ⇤, Nord} ! Soft drinks {⇤, ⇤, Nord} ! Beers {⇤, ⇤, Nord} ! Spreads {⇤, F, Nord} ! Soft drinks	by Pearson's 2 {⇤, ⇤, Somme} ! Cut cheese {⇤, F, Somme} ! Cut cheese {> 65, ⇤, Morbihan} ! Fresh milk {> 65, ⇤, Somme} ! Cut cheese {⇤, ⇤, F inistere} ! Canned pork

TABLE III INTERESTINGNESS

 III MEASURES OF A RULE A ! B. ⇤, . INDICATE MEASURES PRODUCING IDENTICAL RULE RANKINGS WHEN B IS FIXED. ⌃, †, , ⌦ INDICATE MEASURES THAT ALWAYS PRODUCE THE SAME RULE RANKING. |T | IS THE NUMBER OF TRANSACTIONS.

P (A) = support(A)/|T |.