Albrecht Zimmermann
email: albrecht.zimmermann@cs.kuleuven.

Objectively evaluating condensed representations and interestingness measures for frequent itemset mining

Objectively evaluating condensed representations and interestingness measures for frequent itemset mining

Introduction

Frequent itemset mining (FIM) was introduced almost twenty years ago [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF] and the framework has proven to be very successful. It not only spawned related approaches to mining patterns in sequentially, tree, and graph-structured data, but due to its relative simplicity it has been extended beyond the mining of supermarket baskets towards general correlation discovery between attribute value pairs, discovery of co-expressed genes, and classification rules, etc.

The original framework used frequency of itemsets in the data (support) as a significance criterion -often occurring itemsets are assumed not to be chance occurrences -and conditional probability of the right-hand side of association rules (confidence) as a correlation criterion. This framework has clear weaknesses and other interestingness measures have been proposed in the years since the seminal paper was published [START_REF] Wu | Re-examination of interestingness measures in pattern mining: a unified framework[END_REF], as well as several condensed representations [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF][START_REF] Boulicaut | Mining free itemsets under constraints[END_REF][START_REF] Gouda | Genmax: An efficient algorithm for mining maximal frequent itemsets[END_REF] that attempt to remove redundant information from the result set.

While each of these measures and condensed representations is well-motivated, there is as of yet no consensus about how effectively existing correlations are in fact discovered. A prime reason for this can be seen in the difficulty of evaluating the quality of data mining results. In classification or regression tasks, there is a clearly defined target value, often objectively measured or derived from expert labeling a priori to the mining/modeling process, that results can be compared to when assessing the goodness of fit. In clustering research, the problem is somewhat more pronounced but clusters can be evaluated w.r.t. intra-cluster similarity and inter-clusters dissimilarity, knowledge about predefined groups might be available, e.g. by equating them with underlying classes, and last but not least there exist generators for artificial data [START_REF] Pei | A synthetic data generator for clustering and outlier analysis[END_REF]. In FIM, in contrast, while the seminal paper introduced a data generator as well, that data generator has been used only for efficiency estimations and fell furthermore into some disregard after Zheng et al. showed that the data it generated had characteristics that were not in line with real-life data sets [START_REF] Zheng | Real world performance of association rule algorithms[END_REF]. The current, rather small collection of benchmark sets, hosted at the FIMI repository [START_REF]Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations[END_REF], consists of data sets whose underlying patterns are unknown. As an alternative, patterns mined using different measures have been shown to human "domain experts" who were asked to assess their interestingness [START_REF] Carvalho | Evaluating the correlation between objective rule interestingness measures and real human interest[END_REF]. Given humans' tendency to see patterns where none occur, insights gained from this approach might be limited.

Interestingly enough, however, the Quest generator proposed by Agrawal and Srikant already includes everything needed to perform such assessments: it generates data by embedding source itemsets, making it possible to check mining results against a gold standard of predefined patterns. Other data generation methods proposed since [START_REF] Ramesh | Distribution-based synthetic database generation techniques for itemset mining[END_REF][START_REF] Cooper | Realistic synthetic data for testing association rule mining algorithms for market basket databases[END_REF][START_REF] Vreeken | Preserving privacy through data generation[END_REF][START_REF] Bie | Maximum entropy models and subjective interestingness: an application to tiles in binary databases[END_REF] do not use clearly defined patterns and can therefore not be used for this kind of analysis. The contribution of this work is that we repurpose the Quest generator accordingly and address this open questions for the first time:

-How effective are different condensed representations and interestingness measures in recovering embedded source itemsets?

In the next section, we introduce the basics of the FIM setting, and discuss different interestingness measures. In Section 3, we describe the parameters of the Quest generator and its data generation process. Equipped with this information, we can discuss related work in Section 4, placing our contribution into context and motivating it further. Following this, we report on an experimental evaluation of pattern recovery in Section 5, before we conclude in Section 6.

The FIM setting

We employ the usual notations in that we assume a collection of items I = {i 1 , . . . , i N }, and call a set of items I ⊆ I an itemset, of size |I|. In the same manner, we refer to a transaction t ⊆ I of size |t|, and a data set T ⊆ 2 I of size |T |. An itemset I matches (or is supported by) a transaction t iff I ⊆ t, the support of I is sup(I, T ) = |{t ∈ T | I ⊆ t}|, and its relative support or frequency f req(I, T ) = sup(I,T )

|T | . An itemset I is frequent for a given threshold θ ∈ N, if sup(I, T ) ≥ θ. The confidence of an association rule X ⇒ Y , formed of two itemsets X, Y ⊂ I, X ∩ Y = ∅, is calculated as conf (X ⇒ Y, T ) = sup(X∪Y,T )
sup(X,T ) . When the context makes it clear which data set is referred to, we drop T from the notation.

Condensed representations

The set of all frequent itemsets can be summarized by so-called condensed representations, subsets that include enough information to enumerate all frequent itemsets or even to derive their support.

An itemset I is a closed itemset iff I is an itemset and ∀i ∈ I, i / ∈ I :

sup(I ∪ i, T ) < sup(I, T ). An itemset I is a maximal frequent itemset for given minimum support threshold θ ∈ N iff sup(I, T ) ≥ θ ∧ ∀I ′ ⊃ I : sup(I ′ , T ) < θ.

Interestingness measures

The support/confidence framework has at least one major drawback in that it ignores prior probabilities. Assume, for instance, two items i 1 , i 2 with f req(i 1 ) = 0.6, f req(i 2 ) = 0.8. While f req(i 1 , i 2 ) = 0.48 would often denote the itemset as a high-frequency itemset, it is in fact exactly what would be expected given independence of the two items. Similarly, conf (i 1 ⇒ i 2 ) = 0.8, while clearly a high confidence value, would also indicate independence when compared to the prior frequency of i 2 . Therefore, numerous other measures have been proposed to address these shortcoming [START_REF] Wu | Re-examination of interestingness measures in pattern mining: a unified framework[END_REF].

Most of them have been proposed for assessing the quality of association rules, meaning that they relate two binary variables. Generally speaking, it is possible to use such measures more generally to assess the quality of itemsets in the following way. Given an interestingness measure m : 2 I × 2 I → R, itemset I, we can take the minimal value over all possible association rules with a single item in the right-hand side (RHS): min i∈I {m(I \ i ⇒ i)}, if the measure is to be maximized, or the maximum value in the opposite case. Several studies [START_REF] Tan | Selecting the right interestingness measure for association patterns[END_REF][START_REF] Vaillant | A clustering of interestingness measures[END_REF][START_REF] Lenca | On selecting interestingness measures for association rules: User oriented description and multiple criteria decision aid[END_REF] have explored association rule measures w.r.t. their theoretical properties and empirical behavior and identified groups of measures that behave the same or at least very similar. Based on those groupings, we have selected the following measures:

1. Piatetsky-Shapiro (PS)

P S(X ⇒ Y ) = f req(X ∪ Y ) -f req(X)f req(Y ) 2. Confidence (Conf) See above 3. Least Contradiction (LC) LC(X ⇒ Y ) = sup(X ∪ Y ) -(sup(X) -sup(X ∪ Y )) sup(Y ) 4. Jaccard (J) J(X ⇒ Y ) = sup(X ∪ Y ) sup(X) + sup(Y ) -sup(X ∪ Y ) 5. J-Measure (JM) JM (X ⇒ Y ) = max sup(X∪Y ) |T | log 2 ( sup(X∪Y )|T | sup(X)sup(Y ) )+ sup(X)-sup(X∪Y ) |T | log 2 ( (sup(X)-sup(X∪Y ))|T | sup(X)(|T |-sup(Y )) ), sup(X∪Y ) |T | log 2 ( sup(X∪Y )|T | sup(X)sup(Y ) )+ sup(Y )-sup(X∪Y ) |T | log 2 ( (sup(Y )-sup(X∪Y ))|T | sup(Y )(|T |-sup(X)) ) 6. Goodman-Kruskal (GK) GK(X ⇒ Y ) = i∈X max i ′ ∈Y f req(i∪i ′ )+ i∈Y max i ′ ∈X f req(i∪i ′ ) -maxi∈X f req(i)-max i ′ ∈Y f req(i ′ ) 2-maxi∈X f req(i)-max i ′ ∈Y f req(i ′ )
Our primary aim, however, is to test the recovery of itemsets, the precursors to association rules, and we are therefore also interested in measures that have been proposed to mine interesting itemsets. To make it easier to discuss those more sophisticated measures, we associate each itemset with a function I : T → {0, 1}, with I(t) = 1 iff I ⊆ t, which allows us to define an equivalence relation based on a collection of itemsets {I 1 , . . . , I k }: Multi-way χ 2 Brin et al. proposed to use the χ 2 test to evaluate itemsets directly [START_REF] Brin | Beyond market baskets: Generalizing association rules to correlations[END_REF]. Each item i ∈ I is considered its own itemset and instead of a 2 × 2 contingency table, a multiway table with 2 |I| cells is populated by the cardinalities of the blocks derived from T / ∼ {i|i∈I} . The χ 2 -value is calculated as in the two-dimensional case. The degrees of freedom for such a table are df (I) = 2 |I| -1 -|I|, and if the χ 2 value exceeds a given p-value for that many df , the itemset is considered significant. Brin et al. also propose an interest measure for individuals cells:

∼ {I1,...,I k } = {(t 1 , t 2 ) ∈ T × T | ∀I i : I i (t 1 ) = I i (t 2 )}
interest(b v ) = |1 -Ov
Ev |, and propose to consider the combination of item presences and absences of the cell with the highest interest value the most relevant contribution of the found itemset.

Entropy Entropy effectively evaluates the "balance" of a partition induced by an itemset, i.e. the relative size or likelihood of the blocks:

H({i | i ∈ I}) = - b∈T /∼ {i|i∈I} |b| |T | log 2 ( |b| |T | )
The entropy is highest, equal to |I|, if all blocks are equally likely, and 0 if there is only one block. Heikinheimo et al. proposed mining low-entropy itemsets [START_REF] Heikinheimo | Finding low-entropy sets and trees from binary data[END_REF].

Maximum Entropy evaluation Not a measure per se, De Bie has proposed to use maximum entropy models to sample data sets conforming to certain constraints derived from T , e.g. row and column margins, i.e. support of individual items and sizes of transactions, in the expectation [START_REF] Bie | Maximum entropy models and subjective interestingness: an application to tiles in binary databases[END_REF]. Found patterns can be reevaluated on these databases and rejected if they occur in more than a certain proportion.

3 The Quest generator

The Quest generator was introduced in the paper that jump-started the area of frequent itemset mining (FIM), and arguably the entire pattern mining field [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]. The generative process is governed by a number of parameters:

-L -the number of potentially large itemsets (source itemsets) in the data.

-N -the number of items from which source itemsets can be assembled.

-|I| -the average size of source itemsets.

-|t| -the average size of transactions in the data.

-|T | -the cardinality of the data set.

c -the "correlation level" between successive itemsets.

The generator proceeds in two phases: it first generates all source itemsets, and in a second step assembles the transactions that make up the full data set from them. The authors, working in the shopping basket setting, aimed to model the phenomenon that certain items are typically bought together and several such groups of items would make up a transaction. This also means that the output of FIM operations can be compared to the source itemsets to get an impression of how well such mining operations recover the underlying patterns. We have reimplemented the generator and it can be downloaded at http://www.scientific-data-mining.org.

Source itemset generation

For each of the L source itemsets, the size is sampled from a Poisson distribution with mean |I|, which means that itemsets' sizes are not influenced by those of others. A fraction of the items used in the source itemset formed in iteration i is taken randomly from the itemset formed in iteration i -1. This fraction is sampled from an exponential distribution with mean c. This is the only step in which itemsets are influenced by others. The rest of the items are sampled uniformly from N . Each source itemset is assigned a weight, which will correspond to its probability of appearing in the data, sampled from an exponential distribution with unit mean, and a corruption level, i.e. a probability value that only the partial source itemset will be embedded into a transaction, sampled from a normal distribution with mean 0.5 and variance 0.1. Source itemsets' weights are normalized so that they sum to 1.0.

Transaction generation

For each of the |T | transactions, the size is sampled from a Poisson distribution with mean |t|. Source itemsets to be embedded into the transaction are chosen according to their weight, and their items embedded according to their corruption level. Importantly, this means that source itemsets are selected independently from each other. If the number of items to be embedded exceeds the remaining size of the transaction, half the time the items are embedded anyway, and the transaction made larger, in the other half the transaction is made smaller, and the items transferred for embedding into the succeeding transaction.

Related work

The seminal paper on FIM, which also introduced the Quest generator, was published almost twenty years ago [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]. The authors used the generator to systematically explore the effects of data characteristics on their proposed algorithm, using several different transaction and source itemset sizes, evaluating a number of values for |T | (9 values), N (5 values), and |t| (6 values) while keeping the other parameters fixed, respectively, specifically the number of source itemsets L. It is unclear whether more than one data set was mined for each setting, an important question given the probabilistic nature of the correlation, corruption, and source itemset weight effects. A similar kind of systematic evaluation can still be found in [START_REF] Zaki | Scalable algorithms for association mining[END_REF], although the authors did not evaluate different values for N (and also continue to keep L fixed throughout). The evaluation found in [START_REF] Han | Mining frequent patterns without candidate generation[END_REF], however, already limits itself to only two Quest-generated data sets. In line with this trend, the authors of [START_REF] Zaki | ChArm: An efficient algorithm for closed association rule mining[END_REF] used four Quest-generated data sets which they augmented by three UCI data sets [START_REF] Blake | UCI repository of machine learning databases[END_REF], and PUSMB data sets that act as stand-ins for "dense" data, i.e. sets with few items coupled with large transaction sizes. The evaluation reported in [START_REF] Pei | Closet: An efficient algorithm for mining frequent closed itemsets[END_REF] uses one artificial data set, one UCI data set, and the PUSMB data.

The systematic use of the Quest generator came to a virtual halt after Zheng et al. reported that one of the Quest-generated data sets shows different characteristics from real-life data and that algorithmic improvements reported in the literature did not transfer to real-life data [START_REF] Zheng | Real world performance of association rule algorithms[END_REF]. Notably, the authors pointed out that Closet [START_REF] Pei | Closet: An efficient algorithm for mining frequent closed itemsets[END_REF] scales worse than Charm [START_REF] Zaki | ChArm: An efficient algorithm for closed association rule mining[END_REF], a result that Zaki et al. verified in revisiting their work and comparing against Closet as well [START_REF] Zaki | Charm: An efficient algorithm for closed itemset mining[END_REF], and that runs contrary to the experimental evidence presented in [START_REF] Pei | Closet: An efficient algorithm for mining frequent closed itemsets[END_REF] by the authors of Closet, probably due to the difference in used data sets.

The typical evaluation of FIM related approaches afterwards consisted of using two Quest-generated data sets, a number of UCI data sets, and the reallife data sets made available to the community, e.g. in the Frequent Itemset Mining Implementation competitions [START_REF]Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations[END_REF]. This has led to the paradoxical situation that while techniques for FIM have proliferated, the amount of data sets on which they have been evaluated has shrunk, in addition to a lack of control over these data sets' characteristics. Also, all evaluations limited themselves to evaluating efficiency questions.

In the same period, data sets begun to be characterized by the distribution of the patterns mined from them, see e.g. [START_REF] Ramesh | Distribution-based synthetic database generation techniques for itemset mining[END_REF]. These analyses have given rise to techniques for "'inverse itemset mining" that, starting from FIM results, generate data leading to the same distribution of mined itemsets. While these data sets could be used for efficiency evaluations, they are dependent on the data from which patterns are mined in the first place, and the lack of clearly defined patterns prevents quality evaluations. In a similar vein falls the generator proposed in [START_REF] Vreeken | Preserving privacy through data generation[END_REF] which uses the MDL principle to generate data sets that will lead to similar itemsets mined, even though it serves a different purpose, namely to protect the anonymity of original data sources.

Finally, FIM research has spawned a large number of interestingness measures and literature discussing what desirable characteristics of such measures are and how similar their practical performance is [START_REF] Tan | Selecting the right interestingness measure for association patterns[END_REF][START_REF] Vaillant | A clustering of interestingness measures[END_REF][START_REF] Lenca | On selecting interestingness measures for association rules: User oriented description and multiple criteria decision aid[END_REF][START_REF] Wu | Re-examination of interestingness measures in pattern mining: a unified framework[END_REF]. Tan et al. [START_REF] Tan | Selecting the right interestingness measure for association patterns[END_REF] performed two types of analysis on 21 different interestingness measures: 1) they analyzed each measure in terms of the properties identified as desirable by Piatetsky-Shapiro [START_REF] Piatetsky-Shapiro | Discovery, analysis, and presentation of strong rules[END_REF] and additional properties they identified themselves, 2) they randomly generated contingency tables and compared the similarity of different measures' rankings. They identify five (non-disjunct) groups in this manner. Vaillant et al. [START_REF] Vaillant | A clustering of interestingness measures[END_REF] performed similar analyses, grouping twenty measures, only some of which had been considered by Tan et al., empirically on ten UCI data sets, and comparing their results with a grouping derived from several formal properties. They identify four groups and show that the empirical and theoretical groups do not fully agree. They reprised their work in [START_REF] Lenca | On selecting interestingness measures for association rules: User oriented description and multiple criteria decision aid[END_REF], slightly revising the set of measures, adding additional analyses and suggesting guidelines for selecting the appropriate interestingness measure. While this has made it possible to state whether some measures will have the same outcome, i.e. solution sets, it is at present unknown how those outcomes relate to the patterns underlying the data. The closest research has come to such evaluations are attempts to establish how well interestingness measures for association rules align with domain experts' interest [START_REF] Carvalho | Evaluating the correlation between objective rule interestingness measures and real human interest[END_REF].

Pattern recovery

The fact that the Quest generator assembles transactions in terms of source itemsets gives us the unique opportunity to compare the output of a frequent itemset mining operation to the original patterns. Note that this is different from the approach taken in [START_REF] Ramesh | Distribution-based synthetic database generation techniques for itemset mining[END_REF][START_REF] Vreeken | Preserving privacy through data generation[END_REF] -in those works databases were generated that would result in the itemsets (or at least of the same number of itemsets of certain sizes) being mined that informed the generating process. Contrary to this, we cannot be sure that the output of the frequent itemset mining operation has any relation to the source patterns from which the data is generated, although we of course expect that that would be the case. To the best of our knowledge, this is the first time that such an objective comparison of mined to source itemsets has been performed.

Experimental setup

For reasons of computational efficiency, we use only few (10, 100) source itemsets in our experiments. This allows us to mine with high support thresholds without having to expect missing (too many) source itemsets. We generate data with N = 2000, |t| = 10, |I| = 4, with corruption turned off. We generate 100 data sets for each setting and average the results over them. We used FPGrowth in Christian Borgelt's implementation with support threshold 100/L%, a generous threshold given that we can expect each transaction to consist on average of 10/4 = 2.5 itemsets. This corresponds to a relatively easy setting since the source itemsets have high support and apart from the correlation-induced overlap, items are unlikely to appear in several itemsets. Mined itemsets can be of different type, they can correspond:

one-to-one to source itemsets to unions of source itemsets to intersections of source itemsets to true subsets of source itemsets or be none of the above, in which case the itemset is considered spurious

We mine three kinds of patterns: frequent, closed, and maximal itemsets. While frequent itemsets will be guaranteed to include all source itemsets recoverable at the minimum support threshold, they will also include all of their subsets, and possibly additional combinations of items. Closed itemsets might miss some source itemsets if the probabilistic process of the Quest generator often groups two itemsets together while generating transactions, an effect that should not be very pronounced over 100 data sets, however. On the other hand can closed itemsets be expected to avoid finding subsets of frequent sets unless those are intersections of source itemsets, and to restrict supersets of source itemsets to unions of them. Maximal itemsets, finally, can be expected to consist of unions of source itemsets.

We also use this opportunity to assess the effect of data sizes on the output, e.g. whether more itemsets are mined or whether additional data helps remove spurious patterns. To this end, we generate data with 10, 000 (10K), 100, 000 (100K), and 1, 000, 000 (1M) transactions. For each pattern type, we filter using to the different measures afterwards: a) Piatetsky-Shapiro: 0.01 since independent LHS and RHS will have a PSscore of 0. b) Confidence: 0.5, which is a standard value used in the association rule mining literature. c) Least Contradictions: 0.01 since the numerator will be ≤ 0 if there are at least as many counter examples as supporting examples.

d) Jaccard: it is not straight-forward how to set a threshold for the Jaccard measure since even the value for independent LHS and RHS depends on the frequency of either one. Since negatively correlating ones would get a score of 0, 0.001 would at least filter those out. e) J-Measure: this measure measures the larger contribution to mutual entropy, which is the Shannon entropy decrease according to [START_REF] Blanchard | Using information-theoretic measures to assess association rule interestingness[END_REF]. This is another measure for which the threshold is not straight-forward but given that independent LHS and RHS will result in no decrease at all, we set a threshold of 0.1. f) Goodman-Kruskal: 0.01 for analogous reasons as in the case of PS. g) Multi-way χ 2 : no threshold is needed for this measure but a significance level, we choose 0.05. A high score does not always indicate that the itemset as a whole is relevant, however. To interpret selected itemsets, we use the block with the highest interest value. To give an example, if {i 1 , i 2 , i 3 } attains a high score but the block with highest interest is b 101 , we interpret {i 1 , i 3 } as the pattern, and i 2 as being negatively correlated with it, hence coming from a different source itemset. For this measure, we can therefore also assess how many negative correlations were identified, and how many of those correctly. h) Entropy: there is not clear way to set a maximal threshold. We require for the entropy of itemsets to be at most half of their size. i) Maximum entropy evaluation: we use an empirical p-value of 0.05 to reject the null hypothesis that the items in an itemset are independent from each other, i.e. an itemset must not be frequent on more than 5% of the sampled data sets. We sample 100 times from the maximum entropy model of each data set. We will therefore risk false negatives but evaluating patterns on 10000 data sets already taxes our computational resources.

These measures have different semantics, as explained in [START_REF] Tan | Selecting the right interestingness measure for association patterns[END_REF][START_REF] Vaillant | A clustering of interestingness measures[END_REF], and those works cautioned to consider the characteristics of the data mining task at hand in selecting one, or several of them. As we have explained at the beginning of Section 2.1, we apply all of them to a task that they are not necessarily wellsuited for, the identification of sets of co-occurring items, and evaluate their usefulness for this task. In doing so, we also explore the view that successful prediction of an item's presence can be seen as a surrogate for the rejection of independence.

We want to understand how the different pattern types and the different interestingness measures interact with the source patterns to produce an output set. Hence we show cumulative pattern counts, i.e. the top of the bar corresponds to the total amount of itemsets mined, and different colors show the proportion of different categories of itemsets. This could be incomplete information, however: a measure could for instance have a bias for short itemsets while selecting the same type of itemset as another measure. We therefore also show the length distribution of itemsets in the respective output sets. Finally, the score assigned to patterns can be used to rank them and give guidance to a user in terms of which ones to inspect/consider most relevant. We therefore select the top-50 scores for each measure, and evaluate the itemsets falling into this score interval in the same manner (types of patterns, and length distribution). If different itemsets have the same score, this set's cardinality can be larger than 50. Note that in the ideal case this should include only source itemsets for L = 100, while it necessarily will include other types for L = 10.

Data sets created without corruption of source itemsets

Due to the page limit and since the results for 10K, 100K, and 1M transactions to not differ from each other, we show only plots for 10K transactions. We also focus mainly on results for L = 100, since the trends for L = 10 remain the same, with only some changes in the composition of the output set. The full set of plots can be downloaded at http://www.scientific-data-mining.org.

Frequent itemsets As Figure 1 shows, for 100 source itemsets, the vast majority of the output will be composed by subsets of those itemsets. The first column also shows quite a few spurious itemsets. While some of the interestingness measures, such as PS or JM, manage to remove most of the spurious sets, although JM does so at the expense of actual source itemsets, they cannot filter out the subsets since these consist of legitimately co-occurring items. Except for the two mentioned measures, however, all of the other measures let significant amounts of spurious itemsets pass, some filtering better (Confidence, LC, GK), some worse (Jaccard, Entropy, Multiway-Chi, MaxEnt). Due to the large size of the output, the first figure has a log-scaled y-axis. To gain a better idea of the composition of the output, Figure 2 shows the output set with subsets and spurious sets removed.

As can be seen, the threshold is tight enough that no full unions of source itemsets appear, which unfortunately also means that quite a few source patterns are not recovered. It is interesting to see that most measures reduce the number of source itemset intersections, with the exception of entropy and the Multiway-Chi, which actually identifies intersections in combination with spurious items.

Figure 3 shows how itemset sizes are distributed. In particular it shows that GK has a tendency to select longer itemset, compared to the other measures.

As mentioned above (and as seen in Figure 1), using a single cut-off value still leaves too many itemsets in the output set. Figure 4 shows the effect of using the top-50 scores.

Both confidence and entropy include almost the entire set of itemsets in this score range, although confidence removes at least the spurious sets, while the others return far fewer itemsets. As the figure makes clear, in most cases it is the source itemsets that are removed in this way, with intersections and subsets being selected. Almost no spurious patterns remain, showing that highly scoring patterns indeed consist of co-occurring items.

Figure 5 shows the size distribution of itemsets within the top-50 scores (excluding confidence and entropy since their distributions would look as in Figure 3). The majority of itemsets is relatively short, supporting the impression gained from Figure 4, with the exception of Multiway-Chi and GM that identify longer patterns as interesting. Since the Multiway-Chi score increases with the number of cells, this was to be expected. At this point, we have to conclude tentatively that mining frequent itemsets overwhelms interestingness measures: in particular the large amount of subsets means that the result set would need quite a bit of post-processing to identify the actual patterns in the data.

Closed itemsets A straight-forward way of addressing this issue of too many subsets consists of mining closed itemsets instead, and indeed, as Figure 6 shows, the number of returned itemsets drops from almost ten thousand to a few hundred.

With many subsets removed, similar filtering trends hold as in the case of mining all frequent itemsets -in particular Jaccard and Multiway-Chi, but also Entropy and MaxEnt, are filtering spurious sets not really well. In the case of the latter three the problem seems to be that source itemsets or their subsets, when combined with spurious items, still show unexpected frequencies, appearing significant. The removal of subsets also affects the size distribution of itemsets (Figure 7).

Since there are no more subsets to overwhelm the interestingness measures, the set of itemsets having scores within the top-50 range is roughly of size 50, with the exception of entropy, as Figure 8 shows.

This plot contains the in our opinion first surprising result since the output set selected by confidence (consisting mainly of source itemsets and intersections) would actually be the most relevant. But also most of the other measures return a mix of itemsets that are related to the source itemsets, with the exception of GK, entropy, and Multiway-Chi. The latter loses its good performance, now that there are no more subsets that can be separated from spurious items with which they were combined. Combining closed frequent itemsets with interestingness measures proves to be much more effective for recovering source itemsets and itemsets that are related to them, vindicating the theoretical considerations that led to the proposal and adoption of closed itemset mining.

Maximal itemsets An alternative to closed itemset mining consist of mining maximal itemsets. Since those can also be expected to remove intersections of source itemsets, the result set should consist mainly of source itemsets and Figure 10 seems to bear this out. The size distribution of course reflects the focus of this approach on long itemsets (Figure 11). When selecting itemsets using the top-50 scores (Figure 12), finally, mining maximal itemsets looks like clear winner, at least if one does not use GK, Multiway-Chi, or entropy to select patterns.

The problem with this interpretation is that Figure 14, showing the result for mining maximal sets for L = 10, paints a different picture: while, similar to the case of L = 100, the full result set contains roughly the same amount of patterns as there are source itemsets, the majority of those are spurious.

The reason for this is to be found in that with 100 source patterns, 100 * 101 2 = 5050 possible pattern combinations are possible, making it relatively unlikely that many will show up as frequent. 10 source patterns will only combine into Since there are fewer than 50 patterns in total, using top scores will not help in this situation, and while the set is small enough to be examined by a user, maximal pattern do not carry enough information to help with determining the relevant ones.

The number of source patterns, its interplay with the minimum support threshold, the number of highest-scoring patterns chosen, and of course thresholds for interestingness measures, will therefore have a strong effect on what kind of patterns are returned, a problem that also the use of the top-scoring closed itemsets will not fully address, as Figure 15 shows. In this work, we have for the first time evaluated condensed representations and interestingness measures for frequent itemset mining objectively. Due to a lack of data whose underlying patterns are known and whose characteristics can be easily controlled, it had been unknown whether FIM approaches recover underlying patterns.

We have revisited the Almaden Quest data generator, and exploited the fact that it constructs data from explicit patterns. By generating data sets and performing frequent itemset mining on them, we could compare the mined patterns against the source itemsets used to construct the data. We found not only that mining frequent, closed, or maximal patterns leads to result sets that include many non-relevant patterns in addition to source itemsets but also that several interestingness measures that have been proposed in the literature are only partially effective in reducing the result set to the relevant patterns.

In particular, we have seen that results may vary quite a bit depending on the number of actual source patterns in the data. Since this is one piece of information that no user will know, guidelines should be developed regarding the relationship between mined and actual patterns, depending on the generative processes. Such information could be used to relate patterns to each other in post-processing steps such as pattern set mining. Also, the Quest generator implements a relatively simple setting since all items of a source itemset are embedded together, without conditionality effects, and without any noise in the data that is independent of patterns. We therefore recommend to view our results as a kind of upper bound on the performance of the evaluated interestingness measures: results in more complex, let alone real-world, settings are likely to be worse and any measure that did not perform well in the setting we evaluated here is not very likely to be useful in other settings.

For future work, we therefore intend to look into more complex ways of embedding itemsets, e.g. involving noise, in particular noise that gives the appearance of regularity. Similarly, we will develop approaches for embedding partial patterns conditionally, since this would be a setting that is better suited for evaluating the performance of quality measures for predictive rules. Additionally, there have been proposals put forward for generators that generate the source itemsets themselves in a more sophisticated way, for instance in [START_REF] Mampaey | Summarizing categorical data by clustering attributes[END_REF]. Such data can then be used to relate found patterns to generating processes, and we will use it to follow up on the results presented in this work, with the goal of getting closer to giving robust recommendations for the use of measures and pattern types in real-world settings.

  Using this equivalence relation, a given transaction t induces a block : [t] = {t ′ ∈ T | t ′ ∼ {I1,...,I k } t}. The set of all blocks is referred to as the partition or quotient set of T over {I 1 , . . . , I k }: T / ∼ {I1,...,I k } = {[t] | t ∈ T } In the succeeding discussion, we label each block b ∈ T / ∼ {I1,...,I k } with a subscript denoting what the different itemsets evaluate to. Assuming a set of itemset {I 1 , I 2 , I 3 , I 4 }, for instance, b 1010 contains all transactions for which itemsets I 1 , I 3 evaluate to 1, and itemsets I 2 , I 4 evaluate to 0.

Fig. 1 Fig. 2

 12 Fig. 1 Pattern types for mining all frequent itemsets for L = 100, no corruption

Fig. 3 Fig. 4

 34 Fig. 3 Pattern size distribution for mining all frequent itemsets for L = 100, no corruption

Fig. 5

 5 Fig. 5 Pattern size distribution for mining the top-50 scoring frequent itemsets for L = 100, no corruption, excluding Confidence and Entropy

Fig. 6 Fig. 7

 67 Fig. 6 Pattern types for mining all closed frequent itemsets for L = 100, no corruption

Fig. 8

 8 Fig. 8 Pattern types for mining the top-50 scoring closed frequent itemsets for L = 100, no corruption

Fig. 9 Fig. 10

 910 Fig. 9 Pattern size distribution for mining the top-50 scoring closed frequent itemsets for L = 100, no corruption

Fig. 11 Fig. 12

 1112 Fig. 11 Size distribution for mining all maximal frequent itemsets for L = 100, no corruption

Fig. 13 Fig. 14

 1314 Fig. 13 Size distribution for mining the top-50 scoring maximal frequent itemsets for L = 100, no corruption

Fig. 15

 15 Fig. 15 Pattern types for mining the top-50 scoring closed frequent itemsets for L = 10, no corruption

Acknowledgements

We are grateful to Christian Borgelt and Tijl De Bie for their support w.r.t. the FPGrowth implementation and the MaxEnt Database Generator, respectively, and to our colleagues Matthijs van Leeuwen and Tias Guns, and the participants of Qimie 2013 for helpful discussions. Finally, we thank the anonymous reviewers for their help in improving the manuscript. The author is supported by a post-doctoral grant by the Fonds Wetenschappelijk Onderzoek Vlanderen (FWO).


The Data Problem in Data Mining

Albrecht Zimmermann

INSA de Lyon albrecht.zimmermann@insa-lyon.fr Abstract. Computer science is essentially an applied or engineering science, creating tools. In Data Mining, those tools are supposed to help humans understand large amounts of data, and produce actionable insight. In this talk, I argue that for all the progress that has been made in Data Mining, in particular Pattern Mining, we are lacking understanding of key aspects of the performance and results of pattern mining algorithms. I will focus particularly on the difficulty of deriving actionable knowledge from patterns. I trace the lack of progress regarding those questions to a lack of data with varying, controlled properties, and argue that we will need to make a science of digital data generation, and use it to develop guidance to data practitioners.

Short-comings in evaluation

Data Mining, and in particular Pattern Mining, have been around for about two decades and the work in the field has led to a large number of techniques, which have been applied to pattern domains as diverse as itemsets, attribute-value data, sequences, trees, and graphs, and tasks ranging from finding associations to describing interesting subpopulations, to predicting unseen class labels.

In this talk, I will focus on the unsupervised pattern mining setting, i.e. finding unexpected, interesting and useful patterns that are not related to a variable of interest -nominal or otherwise. As I will argue, the qualitative evaluation of proposed techniques, i.e. how "good" the resulting patterns are, has been given short thrift in comparison to quantitative evaluation, i.e. how efficiently the output is found.

But also the latter has arguably not been given the attention it deserved. This case has been made convincingly early on by Zheng et al. [START_REF] Zheng | Real world performance of association rule algorithms[END_REF], who showed that the evaluations performed in itemset mining up to that point in time had led to an over-fitting on the artificially generated data used. The reported performance did not transfer to real-life data, which showed different characteristics than the artificially generated data. Remarkably enough, the situation has barely improved since then, with quantitative evaluations focused on a small number of data sets, of which typically only few are used in a given evaluation.

The situation is worse for qualitative evaluations, which are rarely performed in the first place. This is understandable since the lack of a target variable corresponds to missing ground truth in the data. But at the same time, it means that even if we knew how to set parameters appropriately 1 , we would not know how found patterns relate to the processes that generated the data. Since pattern mining is supposed to give us insight into those processes, and allow us to act based on found patterns, this is a serious short-coming.

Generating data (and understanding pattern mining)

When there is no ground truth available for real-life data (or when there is little real-life data available in the first place), generating artificial data is a promising alternative. This is not only the case in computer science, where, for instance, the SAT solving community has chosen this direction, but also in "hard sciences" like physics, see for instance [START_REF]Cern software development for experiments -Simulation[END_REF].

Data generation allows us to both break the bottleneck of too few data sets (or data sets with a too narrow range of characteristics), and to understand how found patterns relate to the processes that generated the data. As Zheng et al. showed, however, and others have demonstrated since, approaching this task without forethought and an understanding of the data we aim to generate will lead to unrealistic data sets. Furthermore, limiting ourselves to a narrow selection of generative processes, e.g. generating itemset mining data only by combining itemsets, will restrict the lessons to be learned from matching patterns to processes, and carries the risk of biasing qualitative evaluations.

Fortunately, we do not have to start from scratch. More-or-less successful attempts at data generation have been made, and some infrastructure exists to support this task. Additionally, some researchers have attempted to relate patterns to different processes to evaluate their quality, especially in recent years. Finally, researchers and practitioners in other fields have developed theories of their own that, while necessarily taken with a grain of salt, can be built on to simulate real-life processes. By combining and building on this existing knowledge, we can fill in the current data gaps and start to understand those aspects of pattern mining that escape us so far.

Another area in which there is too little guidance.


Yoann Blache
email: yoann.blache@univ-lyon1.fr

Raphaël Dumas

Arian Lundberg

Mickaël Begon

Blache Yoann

Main component of soft tissue artifact of the upper-limbs with respect to different functional, daily life and sports movements

Keywords: skin marker, geometrical transformation, cluster deformation, deformation energy, shoulder complex

Main component of soft tissue artifact of the upper-limbs with respect to different functional, daily

life and sports movements.

Introduction

The assessment of human body kinematics is essential in many research fields such as orthopedics, ergonomics and sport biomechanics. Accuracy of the skeleton pose estimate is dependent of the methods used to record body kinematics. Usually, trajectories of reflective markers stuck on the skin are recorded using stereophotogrammetry. Nevertheless, skin marker trajectories are affected by the soft tissue artifact (STA) defined as the relative movement between each skin marker and its underlying bone [START_REF] Leardini | Human movement analysis using stereophotogrammetry. Part 3. Soft tissue artifact assessment and compensation[END_REF][START_REF] Peters | Quantification of soft tissue artifact in lower limb human motion analysis: a systematic review[END_REF]. Since STA representations vary among literature, Dumas et al. (2014a) have proposed a generalized mathematical representation of the STA: individual marker displacements, marker-cluster geometrical transformations and skin envelope shape variations. Among these three representations, STA are more usually described either by individual marker displacements or marker-cluster geometrical transformations [START_REF] Alexander | Correcting for deformation in skin-based marker systems[END_REF][START_REF] Andriacchi | A point cluster method for in vivo motion analysis: applied to a study of knee kinematics[END_REF][START_REF] Benoit | Surface marker cluster translation, rotation, scaling and deformation: Their contribution to soft tissue artefact and impact on knee joint kinematics[END_REF][START_REF] Dumas | Soft tissue artifact compensation by linear 3D interpolation and approximation methods[END_REF].

The ultimate purpose of STA assessment is to implement methods in order to improve kinematics estimation. These methods can be used either to define mathematical models that can be embedded in optimal bone pose estimator [START_REF] Alexander | Correcting for deformation in skin-based marker systems[END_REF]Bonci et al., 2014;[START_REF] Camomilla | A model of soft tissue artefact rigid component[END_REF][START_REF] Camomilla | A hip joint kinematics driven model for the generation of realistic thigh soft tissue artefacts[END_REF], to implement functional algorithms for locating joint rotation center [START_REF] De Rosario | Propagation of soft tissue artifacts to the center of rotation: a model for the correction of functional calibration techniques[END_REF] or to assess the dynamic effects of the wobbling mass [START_REF] Bélaise | Effect of wobbling mass modeling on joint dynamics during human movements with impacts[END_REF][START_REF] Thouze | A chain kinematic model to assess the movement of lower-limb including wobbling masses[END_REF]. As STA may not be defined a priori because they are subject-, task-and segment-specific, a calibration (i.e. identification of the components that define the STA and of the parameters that model these components) is necessary for each studied movement. Consequently, some studies aimed at describing the components, among individual marker displacements or marker-cluster geometrical transformations that best describe STA. These studies have been performed exclusively concerning the lower-limb STA. Briefly, these investigations pointed out which skin markers located on the thigh and shank were the most subject to the STA [START_REF] Akbarshahi | Non-invasive assessment of soft-tissue artifact and its effect on knee joint kinematics during functional activity[END_REF]Dumas et al., 2014b;[START_REF] Kuo | Influence of soft tissue artifacts on the calculated kinematics and kinetics of total knee replacements during sit-to-stand[END_REF][START_REF] Tsai | Effects of soft tissue artifacts on the calculated kinematics and kinetics of the knee during stair-ascent[END_REF]. In addition, it was observed that STA of the lower limbs were mainly explained by rigid transformations (i.e. translations and rotations) and in a less manner by deformations (i.e. homotheties and stretches) of the markercluster [START_REF] Andersen | A linear soft tissue artefact model for human movement analysis: proof of concept using in vivo data[END_REF][START_REF] Barre | Soft tissue artifact distribution on lower limbs during treadmill gait: Influence of skin markers' location on cluster design[END_REF][START_REF] Barre | Soft tissue artifact assessment during treadmill walking in subjects with total knee arthroplasty[END_REF][START_REF] Benoit | Surface marker cluster translation, rotation, scaling and deformation: Their contribution to soft tissue artefact and impact on knee joint kinematics[END_REF][START_REF] Benoit | Effect of skin movement artifact on knee kinematics during gait and cutting motions measured in vivo[END_REF][START_REF] De Rosario | Kinematic description of soft tissue artifacts: quantifying rigid versus deformation components and their relation with bone motion[END_REF]Dumas et al., 2014b;[START_REF] Grimpampi | Metrics for describing soft-tissue artefact and its effect on pose, size, and shape of marker clusters[END_REF]. Although many studies give either qualitative or quantitative information about STA for the lower limbs, no data is available in the literature concerning the characterization of the STA for the upper-limb.

The objective of this study was to describe the main components that best represent the STA of the shoulder complex and arm during functional arm movements and daily-life or sports movements. Firstly, the description of the displacement of the individual skin markers was analyzed. Secondly, special consideration was given to the analysis of marker-cluster geometrical transformations. To that purpose, the trajectories of the skin markers relative to the bone were computed using reflective markers secured to intra-cortical pins. As STA has been shown to be task-specific, the analysis focused on movements with different amplitudes, degrees of freedom and velocities. To that aim, arm flexions and rotations as well as hair combing and hockey shooting were investigated. According the studies about the STA of the lower limb, it was hypothesized, that the STA energy was task-, location-segment-and subject-specific, while the rigid transformations of the marker-cluster explained the main part of the STA energy.

Methods

Participants

The raw data obtained by Dal Maso et al. (2014) have been used in this study. Four healthy male participants (age ranged between 27 and 41 years, mass ranged between 57 and 115 kg, height ranged between 1.65 and 1.82 m) volunteered to participate in this study. They signed an informed consent which was approved by the Karolinska Institute (Sweden) and the University of Montreal (Canada) ethics committees. None of the participants presented current or previous shoulder injuries.

Instrumentation

Four or five reflective markers secured to pins were respectively inserted into the first third of the scapula spine and the clavicle, and below the attachment of the medial deltoid on the humerus. The pin locations were chosen to avoid muscles such that the movement pattern remained unchanged. They were also oriented to avoid contacts between markers and head or neck during movements (see Dal [START_REF] Dal Maso | Coupling between 3D displacements and rotations at the glenohumeral joint during dynamic tasks in healthy participants[END_REF] for details about the surgical insertion).

In line with the kinematic shoulder model of [START_REF] Jackson | Improvements in measuring shoulder joint kinematics[END_REF], 16 skin markers were placed on the left clavicle (5), scapula (4), upper arm (7) (Fig. 1). Marker trajectories for each movement were measured with an 18-camera optoelectronic VICON TM system (T-40S and T-20S; Oxford Metrics Ltd., Oxford, UK) sampled at 300 Hz. The experiment was conducted under local anaesthesia that lasted two hours.

Insert Figure 1 near here

Procedures

Prior to the test, participants held for a few seconds an anatomical and then a rest static positions. Thereafter they performed functional movements, including arm flexion, rotation and circumduction. This procedure was used to determine joint centre of rotations and to define segment coordinate system for the STA description (see section 2.4.). The movements of interest were two kind of functional movements performed up to 11 repetitions; they consisted in arm flexions (i.e. elevation in the sagittal plane) and arm rotations with the arm at 0° and 90° of abduction (with maximal range of motion). For the arm flexion, participants had to keep a neutral internal/external arm rotation, and the elbow extended throughout the movements. Nevertheless because of the discomfort induced by the humeral pin, the second participant performed only two trials of arm flexion. Concerning the arm rotations, participants had to keep their elbow at 90° of flexion throughout the movement. In addition, the participants performed six trials of a daily-life activity (i.e. to mimic hair combing) and a sport movement (i.e. to mimic hockey shooting with a hockey stick). The participants performed their movements at their preferred speed.

Data Processing

Joint center of rotation locations were obtained from the functional symmetrical centre of rotation algorithm [START_REF] Ehrig | A survey of formal methods for determining the centre of rotation of ball joints[END_REF] implemented with pin markers. Skin markers and joint center of rotation locations obtained during the static position were used to define each segment coordinate system according to the ISB [START_REF] Wu | ISB recommendation on definitions of joint coordinate systems of various joints for the reporting of human joint motion--Part II: shoulder, elbow, wrist and hand[END_REF] and [START_REF] Jackson | Improvements in measuring shoulder joint kinematics[END_REF] recommendations. Joint angles were computed using a single-body kinematic optimization algorithm, consisting in minimizing the quadratic Euclidean distance between the experimental pin markers and virtual markers of the kinematic model. Finally, the skin marker displacements were expressed with respect to their underlying segment coordinate system.

Finally, the helical axis angle between the orientations of the pin-and skin-based local coordinate systems was calculated at the beginning of each trial in order to assess a possible rotation of the markers support on the pin or pin loosening. A drift of this angle for the scapula of two participants was identified after a few trials. Consequently the data concerning the scapula were removed for these two participants.

Soft tissue artifact

From pin and skin markers, the method developed by Dumas et al. (2014a) was implemented to describe STA relative to the scapula, clavicle and humerus. Briefly, STA fields were computed to represent the displacements that all skin markers associated with the segment undergoes relative to the segment coordinate system at each sampled instant of time from a reference position defined during the static posture. STA fields were then represented by a series of modes (l):

(1)

where corresponds to the amplitude of the projection of onto the basis vector and can be obtained as follow:

(2)

The definition of the basis vectors for both individual skin marker displacements and marker-cluster geometrical transformations (i.e. translations, rotations, homotheties and stretches) is detailed in Dumas et al. (2014a). Finally, the modes were ranked by computing the STA energy:

(3)

Note that the total STA energy is the sum of the above mentioned modal ones.

Analyzed variables

Firstly, the upper-limb STA were described by the analysis of the individual skin marker displacements, which corresponded to the modes in Eq.1. The percentage of the total STA energy explained by each individual marker displacement along its three dimensional axis was calculated. Then, to enable a global analysis, the STA energies of the three dimensional axis of a given skin marker were summed.

Secondly, the upper-limb STA have been defined as marker-cluster geometrical transformations, which corresponded to the modes in Eq.1 (i.e., translations, rotations, homotheties and stretches along the three dimensional axis). Similarly as for individual skin marker displacements, the STA energies of the three dimensional axis for a given geometrical transformation were summed.

Finally, the analyzed variables cited above have been calculated for each trial (up to 11) of each movement. Then the mean value of the trials for a given movement (arm flexion or rotation; hair combing; or hockey shooting) and a segment (clavicle, scapula and humerus)

were considered for the analysis. Due to the small number of subjects, no statistics was performed.

Results

First of all, as the pin inserted into the scapula rotated a few degrees for two participants, the data concerning the scapula were given for only two remaining participants. The joint angles of each movement computed with the pin markers were presented in figure 2. The durations of the movements were 3.63±1.16 s, 1.57±0.31 s, 1.34±0.45 s and 0.94±0.54 s for the arm flexion/extension, arm rotation, combing mimic and hockey shooting mimic respectively.

Individual skin marker displacements

The relative percentage of total STA energy explained by each marker varied among participants and motions. Nevertheless some similitude may be noticed. Concerning the clavicle, the markers CL1 and CL4 represented the greatest percentages of the total STA energy (31% on average for each marker), but for the hockey shooting. Indeed for the latter movement CL2 energy was significantly greater than the CL4 one (Fig. 3). Concerning the scapula, it appeared that each marker would have a similar contribution to the total STA energy for the rotation and hair-combing movements. By contrast SS1 and SS2 had the greatest percentages of total STA energy for the flexion and hockey-shooting movements (Fig. 3).

Concerning the humerus, during the flexion movement, the markers Tri2, Bic1 and Bic2 generally explained the greatest part of the total STA energy (23% on average for each marker), while EpM and EpL were the markers that presenting the less STA energy (5% on average for each marker) (Fig. 3). For the rotation and hair-combing movements, Tri2 and EpL explained most of the time the greatest part of total STA energy (25% on average for each marker) (Fig. 3). Finally, for the hockey-shooting similar percentage of STA energy was observed between each marker (Fig. 3).

Insert Figure 2 near here

Marker-cluster geometrical transformations

Concerning the clavicle, the translation of the marker-cluster explained the greatest percentage of the total STA energy in three participants (60% on average). Similar percentages were observed between the rotation and homothety, while the smallest percentage of the total STA energy was observed for the stretch (Fig. 4). Concerning the scapula, it seemed that the translation of the marker-cluster explained also the greatest percentage of total STA energy. For the humerus, during the arm flexion movement the translation of the marker-cluster represented the greatest percentage of the total STA energy (66% on average), followed by the arm rotation and stretch, while the homothety represented the smallest percentage (Fig. 4). Concerning the rotation and hair-combing movements, the total STA energy was explained in a descending order by rotation (53% on average), translation, homothety and stretch of the marker-cluster (Fig. 4). Finally, for the hockey-shooting, the rigid transformations (translation and rotation) represented a similar percentage of total STA energy (37% on average for each mode), that was greater than the homothety and stretch (Fig. 4).

Insert Figure 3 near here

When the rigid transformations were summed and compared to the sum of the non-rigid transformations, the sum of rigid transformations always explained the greatest part of the total STA energy (on average 85% of the total STA energy), regardless the segment and the movement and the participant.

Insert Figure 4 near here

Discussion

The purpose of this study was to describe the main components that best describe the STA of the shoulder complex and arm during functional arm movements and daily-life or sports movements. To that aim, the percentage of the total STA energy explained either by individual marker displacements or marker-cluster geometrical transformations was computed. Our hypotheses were confirmed since we firstly observed that the individual marker displacements were task-location-and subject-specific. Secondly, concerning the marker-cluster geometrical transformations, the rigid part systematically explained at least 85% of the total STA energy regardless the task and the segment. However, the proportion of translation and rotation was different with regards to the segment, task and participant.

Limits

Our results were observed on a small sample size, consequently further studies using fluoroscopy or intra cortical pins with more participants are needed to confirm our conclusions. Nevertheless, it can be noticed, that the statistical methods used, enabled to perform mixed-linear model analysis on small samples (Leys 2010) and showed excellent statistical power (superior to 0.9). The second limit was that the displacements of the skin marker located near to the pins may have been slightly reduced, since the skin may present less movement in this area. The third limit was that the subjects could only mimic daily-living and sport movements, especially because of the environmental context, which may not totally reflect movements with strong impacts. The fourth limit was that we used the definition given by Dumas et al. (2014a) to describe the geometrical transformations, while alternative definitions are also given in the literature [START_REF] Andersen | A linear soft tissue artefact model for human movement analysis: proof of concept using in vivo data[END_REF][START_REF] Barre | Soft tissue artifact assessment during treadmill walking in subjects with total knee arthroplasty[END_REF][START_REF] De Rosario | Kinematic description of soft tissue artifacts: quantifying rigid versus deformation components and their relation with bone motion[END_REF][START_REF] Grimpampi | Metrics for describing soft-tissue artefact and its effect on pose, size, and shape of marker clusters[END_REF]. Nevertheless the definition of Dumas et al.

(2014a) has been used in several studies investigating the STA of the lower limbs [START_REF] Camomilla | A model of soft tissue artefact rigid component[END_REF]Dumas et al., 2014b[START_REF] Dumas | What portion of the soft tissue artefact requires compensation when estimating joint kinematics[END_REF] which, showed similar results for the lower limb as studies using other definitions. Finally, the metric used to describe the main components of the STA was the percentage of total energy. This is not widely used in biomechanics, nevertheless this metrics has been used in study about the STA of the lower limbs [START_REF] Camomilla | A model of soft tissue artefact rigid component[END_REF]Dumas et al., 2014b) and is very similar in principle to the fraction of total STA magnitudes as proposed by [START_REF] Benoit | Surface marker cluster translation, rotation, scaling and deformation: Their contribution to soft tissue artefact and impact on knee joint kinematics[END_REF].

Individual skin marker displacements

The Individual skin marker displacement of the present study seemed to be subject-, task-and location-specific. These results generalize the findings observed for the humerus (Begon et al., 2015), the scapula [START_REF] Matsui | Deviation of skin marker from bone target during movement of the scapula[END_REF] and the lower limbs [START_REF] Akbarshahi | Non-invasive assessment of soft-tissue artifact and its effect on knee joint kinematics during functional activity[END_REF][START_REF] Andersen | A linear soft tissue artefact model for human movement analysis: proof of concept using in vivo data[END_REF] to the whole shoulder complex. Nevertheless, regardless the task and participant, some markers such as CL5 (lateral part of the clavicle) and EpM (medial epicondyle of the humerus) were always few affected by STA. Consequently as suggested by [START_REF] Begon | Can optimal marker weightings improve thoracohumeral kinematics accuracy[END_REF] these marker locations (lateral part of the clavicle and medial epicondyle of the humerus) may be relevant for a set using a limited number of markers or when the experimenter looks for a sensor location with small STA. Concerning the scapula, [START_REF] Matsui | Deviation of skin marker from bone target during movement of the scapula[END_REF] observed similar deviation for the two markers located near the acromion process, while the skin marker located on the inferior angle underwent the highest deviation. We studied only skin markers located near the acromion process, which may explain why none of our scapula markers presented more or less STA.

To summarize, when STA is assessed through individual skin marker displacements, even if some markers seemed to be almost STA free, for most of them, STA were subject-and taskspecific. In addition, almost no marker represented more than 50% of the total STA energy; by contrast lots of them explained a similar part of the total STA energy. Therefore, we may suggest that none of the skin markers used in this study should be specifically selected or removed when one want to estimate upper-limb kinematics with skin markers.

Marker-cluster geometrical transformations

As already observed for the lower limbs [START_REF] Andersen | A linear soft tissue artefact model for human movement analysis: proof of concept using in vivo data[END_REF][START_REF] Barre | Soft tissue artifact distribution on lower limbs during treadmill gait: Influence of skin markers' location on cluster design[END_REF][START_REF] Benoit | Surface marker cluster translation, rotation, scaling and deformation: Their contribution to soft tissue artefact and impact on knee joint kinematics[END_REF]Dumas et al., 2014b), the marker-cluster geometrical transformations of the upperlimb were task-, segment-and subject-specific. Nevertheless for the clavicle a similar ranking was observed among the four analyzed task namely, the greatest part of the total STA energy was often explained by the translation of the marker-cluster, followed by a similar contribution of the rotation and homothety. Similar results were observed for the scapula.

Concerning the humerus translation and rotation explained the greatest part of the total STA energy but for arm flexion task. Interestingly, the highest proportion of maker-cluster translation was specific of this flexion task.

However, although differences were observed among the segment and analyzed movements, the rigid transformations (translation + rotation) summed together always explained a greater part of the total STA energy than the non-rigid transformations (homothety + stretch). On average 85% of the total STA energy was explained by the rigid transformations. These results confirmed those observed on the lower-limbs when rigid and non-rigid transformations were compared during walking [START_REF] Andersen | A linear soft tissue artefact model for human movement analysis: proof of concept using in vivo data[END_REF][START_REF] Barre | Soft tissue artifact distribution on lower limbs during treadmill gait: Influence of skin markers' location on cluster design[END_REF][START_REF] Barre | Soft tissue artifact assessment during treadmill walking in subjects with total knee arthroplasty[END_REF][START_REF] Benoit | Surface marker cluster translation, rotation, scaling and deformation: Their contribution to soft tissue artefact and impact on knee joint kinematics[END_REF], running (Dumas et al., 2014b), cutting manoeuver and hopping [START_REF] Andersen | A linear soft tissue artefact model for human movement analysis: proof of concept using in vivo data[END_REF][START_REF] Benoit | Surface marker cluster translation, rotation, scaling and deformation: Their contribution to soft tissue artefact and impact on knee joint kinematics[END_REF]. The upper limb specificity appears in the proportion of marker-cluser rotation at the humerus for most of the movements analysed.

Nevertheless, as for the lower limb, least squares bone pose estimators, that compensate only for the non-rigid transformations of the marker cluster, can hardly improve the estimation of joint kinematics, in particular for the shoulder joint [START_REF] Begon | Can optimal marker weightings improve thoracohumeral kinematics accuracy[END_REF]. The large proportion of marker-cluster translation also suggests joint dislocation or inter-penetration if the joint displacements are computed from the skin markers.

Previous studies [START_REF] Camomilla | A model of soft tissue artefact rigid component[END_REF][START_REF] De Rosario | Propagation of soft tissue artifacts to the center of rotation: a model for the correction of functional calibration techniques[END_REF] investigating the STA of the lower limb have shown that the development of models composed of STA rigid components represents a potential solution for STA compensation. This solution could be extended for the STA compensation in the upper limb. Our study was the first step (i.e.

determine the main components that best describe the STA) necessary to implement STA models that may enable to reduce shoulder kinematics errors. The next step will be to consider these rigid transformations in the implementation of a STA model in order to reduce its effects on kinematics estimation. Meanwhile, using a redundant marker set with multibody kinematic optimisation algorithms may currently represent the best method for clinicians and researchers. The accuracy of this method relies on the definition of joint models.

Conclusion

Although some studies [START_REF] Begon | Can optimal marker weightings improve thoracohumeral kinematics accuracy[END_REF][START_REF] Hamming | The accuracy of measuring glenohumeral motion with a surface humeral cuff[END_REF] assessed the effect of STA on shoulder and upper limb kinematics, to our knowledge, our study was the first one to describe the STA of the shoulder complex (clavicle, scapula and humerus) and may be a benchmark of larger scale study. Our study was performed in a modelling perspective. STA was found task-, location-and subject-specific when analyzing the individual skin marker displacements. Consequently considering individual marker displacements for further development of STA models may be compromised. By contrast, although maker-cluster geometrical transformations were also task-, segment and subject-specific, the rigid transformations explained on average 85% of the total STA energy for all subjects, with a large proportion of maker-cluster translation except for the humerus. Therefore, as for the lower limb that was more widely studied, large joint dislocations and limited efficiency of least squares bone pose estimators can be expected for the computation of joint kinematics from skin markers. New compensation methods addressing the STA rigid component need to be further developed and evaluated.

Figure captions Figure 1 .

 captions1 Figure captions

Figure 2 .

 2 Figure 2. Shoulder kinematics of a representative participant with respect to the time for the flexion movement (A), rotation (B), hair combing (C) and hockey shooting (D). For the sternoclavicular joint the protraction(-)/retraction(+), elevation(+)/depression(-) and posterior(-)/anterior(+) rotation are represented by the solid black, dashed black and grey lines respectively. Concerning the acromioclavicular joint the internal(-)/external(+) rotation, upward(+)/downward(-) rotation and anterior(-)/posterior(+) tilt are represented by the solid black, dashed black and grey lines respectively. For the glenohumeral joint the plane of elevation, elevation and the internal(-)/external(+) axial rotation are represented by the black, dashed black and grey lines respectively.

Figure 3 .

 3 Figure 3. Percentage of total STA energy explained by each individual skin marker displacement according to each segment (left-right) and movement (up-down) for each participant (black: participant 1, dark grey: participant 2, light grey: participant 3, white: participant 4). Refer to figure 1 for the definition of the markers.

Figure 4 .

 4 Figure 4. Percentage of total STA energy explained by each type of rigid (translation [T] and rotation [R]) and non-rigid (homothety [H] and stretch [S]) transformation as a function of the segment (left-right) and movement (up-down) for each participant (black: participant 1, dark grey: participant 2, light grey: participant 3, white: participant 4).

Acknowledgement

This work was partially funded by the NSERC discovery (#RGPIN-2014-03912) grant. The first author is scholar of the Méditis program (NSERC, CREATE).

Conflict of interest statement

None of the authors are in conflict of interest with regards to this research.