Ludovic Tanguy

Assaf Urieli

Basilio Calderone

Nabil Hathout

Franck Sajous

A multitude of linguistically-rich features for authorship attribution

This paper reports on the procedure and learning models we adopted for the 'PAN 2011 Author Identification' challenge targetting real-world email messages. The novelty of our approach lies in a design which combines shallow characteristics of the emails (words and trigrams frequencies) with a large number of ad hoc linguistically-rich features addressing different language levels. For the author attribution tasks, all these features were used to train a maximum entropy model which gave very good results. For the single author verification tasks, a set of features exclusively based on the linguistic description of the emails' messages was considered as input for symbolic learning techniques (rules and decision trees), and gave weak results. This paper presents in detail the features extracted from the corpus, the learning models and the results obtained.

Introduction and motivations

Given a set of texts and the corresponding authors (in our case email messages), the basic idea underlying Authorship Attribution (AA) systems is that various calculable textual features may be relevant enough to capture statistically-based generalizations of the 'stylistic distinctiveness' of the writers, in order to distinguish texts written by different authors. These 'textual features' thus refer to the ability of representing a text by a set of attributes that capture a particular author's 'writing style' [START_REF] Zheng | A framework for authorship identification of online messages: Writing-style features and classification techniques[END_REF].

As members of the NLP team of a linguistics research laboratory, we decided to concentrate on calculating a large set of features, as we saw in this challenge an opportunity to take advantage of our experience in a wide variety of automated text annotation tasks. As will be presented in detail in § 2, we addressed both traditional features used for AA [START_REF] Juola | Authorship attribution[END_REF][START_REF] Stamatatos | A survey of modern authorship attribution methods[END_REF], and more innovative ones corresponding to the investigation of more focused textual phenomena.

Our definition and selection of these features was based on an approach that originates in the linguistic side of NLP and computational linguistics. More precisely, the first phase of our work was to carefully examine the data, and to use a combination of human intuition and computer-aided investigation tools, a common method used in areas such as corpus linguistics.

The next step was to design (in most cases, to recycle) specific processing methods to compute the selected features. Team work, available linguistic resources and the variety of our experiences in different areas of computational linguistics were crucial assets here. As described in the following sections, we were thus able to combine morphological, syntactic and semantic techniques, and also to design many data-specific features. If some of the features rely on well-known techniques, we also designed innovative approaches, such as the different measures used to assess syntactic complexity and semantic cohesion.

The last step was to feed all these features into a machine learning algorithm ( § 3). Given the sheer number of features (especially when word and trigrams frequencies are involved), our choice was to use a maximum entropy learner, which is able to cope with such quantities and with a variety of feature types (both quantitative and qualitative). However, we also wanted to have some kind of feedback of this procedure, and to identify which features were the most efficient for the task. This led us to apply other machine learning methods, namely tree-and rule-based algorithms whose main advantage is to give intelligible representations of the learned schemes. As far as the task results are concerned, this second choice was not a wise move, as we will discuss in the last section.

The PAN 2011 Authorship Attribution competition was based on real-world email messages (extracted from the Enron corpus) and consisted in two different sets of tasks. The first one (standard authorship attribution) required the participants to infer who was the author of each message from the test data (from all the authors present in the training data). Some of the test sets also contained emails written by unknown authors (absent from the training data): these subtasks' names are identified with a + sign. Training sets contained 3,000 messages from 26 authors (small data set) and 10,000 messages from 72 authors (large data set), while test sets ranged from 400 to 1,500 messages. The second set of tasks (authorship verification) focused on a single target author, requiring the participant to simply decide for each message in the test data if it was written by this particular author or not. Three different authors were targeted: for each author the training data contained about 50 messages, and test data about 100, with of course a totally unknown distribution.

The data itself was very challenging, especially when compared to other data sets used for this kind of task (mostly litterary texts). In addition to the (very) sloppy writing inherent to email messages, the data was very heterogeneous, as the authors used emails in very different contexts (personal as well as formal and informal professional communication). Some emails even contained non-english text, raw computer data and automatically generated content.

Linguistic features

In this section we give a detailed list of all the features used in this experiment. We chose to group them according to the linguistic units they address. We identified four such levels: sub-word (morphological units, character trigrams), word, sentence or phrase (syntax) and message.

Preprocessing

As many of the features used in this experiment required linguistic information from different language levels, our first step was to apply NLP tools to the raw text messages provided for this competition.

We chose Stanford CoreNLP [START_REF] Klein | Accurate unlexicalized parsing[END_REF] to do most of the work. This suite of tools is freely available and ready-to-run for English, and it addresses all the basic levels of natural language processing, mainly:

tokenization: identification of word and sentences boundaries, according to punctuation marks; -POS tagging: identification of each word's part-of-speech (POS) category (Noun, Verb, etc.), along with a number of inflectional features (number, tense, etc.); lemmatization: identification of each word's lemma, or citation form; syntactic parsing: identification of the syntactic relationships between words in a sentence.

The Stanford Parser is a dependency analyzer, and provides tagged pairwise links between syntactically related words (subject, object, determiner, etc.); named entity recognition: identification and classification of expressions that refer to a person, organization, date, quantity or location.

To avoid tweaking the main parameters of these programs, we applied a small number of modifications to the data. We replaced all <NAME/> XML tags (resulting from the anonymization process) with an arbitrary string, as CoreNLP could not cope with such input. We also detected (and replaced with a short arbitrary string) the message parts which contained raw (non-text) data, and would have led the most sophisticated processes (mostly the tagger and parser) to crash due to the lack of sentence delimiters. Finally, we limited the size of sentences to be processed to 50 words, discarding longer sentences which would have taken too long to parse and would probably not lead to interesting fine-grained linguistic features.

The features used for our experiment were computed on the output of these processes, with a few exceptions that are specifically indicated. The following sections give the complete list, according to the linguistic level to which they belong.

Sub-word-level features

The first level addresses linguistic characteristics that appear inside words themselves. Most of these do not need any kind of linguistic preprocessing and were in fact computed directly on the raw message text.

Character trigrams. Language models based on character n-grams have long been used for various text mining tasks, such as language identification [START_REF] Peng | Language independent authorship attribution using character level language models[END_REF]. Regarding authorship attribution, they offer many advantages: they have proven to be effective [START_REF] Cavnar | N-gram-based text categorization[END_REF] and additionally, they are language independent and do not require any preprocessing (not even tokenization). Merely using character n-grams may partly capture some of the features described below: suffixes, punctuation, case, contractions, smileys, function words such as prepositions, pronouns and conjunctions, as well as some cases of alternative spelling (e.g. American vs British English, such as -or /-our, -ise/-ize).

The character trigrams occurring in the larger train set were extracted and the 10,000 most frequent ones were retained as features.

Suffixes. Features related to the morphological properties of the words can be computed both at the sub-word-level and at the word-level. In both cases, we used the CELEX database [START_REF] Baayen | The CELEX lexical database (release 2). CD-ROM[END_REF], a resource which provides morphological analysis for a significant fragment of the English lexicon. The morphological features computed at the sub-word-level concerned the suffixes of derived words in the CELEX parses. These features were computed directly on the lemmas. For instance, one such feature is the number of words in the message whose lemmas end in -ion. We only considered suffixation because suffixed words are the most frequent derivatives and suffixes are better predictors of word formation than prefixes.

More precisely, we collected from CELEX the 149 suffixes which occur at the end of at least one suffixed word. Then, for each message and each suffix, we counted the number of words which end with this suffix. Two additional features were also computed for each message: the ratio of suffixed words to total words and their overall number.

Punctuation. The rate of each regular punctuation mark, multiple marks such as !! and ???, as well as space misuse in punctuation was computed. Indeed, some authors are more prone to neglect the use of punctuation marks in emails than in formal writings, or do not have an in-depth knowledge of typographic rules. Recurrent misuse of spaces may reveal a non-native speaker, e.g. a French author may repeatedly leave a blank before a colon when he writes in English. A list of 34 features corresponding to regular punctuation marks and misuse patterns was thus compiled.

Smileys.

A list of possible smileys was compiled and the 6 appearing in the Test sets were selected. For each of these specific smileys, a binary feature indicated the presence or absence of this smiley in a given message. The use of smileys was expected to be more effective in capturing types of messages (formal/informal) rather than authors' style. However, the fact that some authors use some specific smileys, or no smiley at all may be a hint of authorship.

Word-level features

These features deal with formal characteristics of word units. They take advantage of the tokenization performed by CoreNLP (and therefore inherit its errors). For most features, lemmatization and POS tagging results were used, and for some of them we had to build specific lists of words or patterns, which we made available at the following URL: http://redac.univ-tlse2.fr/projects/authorshipidentification/.

Word frequencies. According to the traditional approaches of text categorization, we computed the relative frequency of each wordform encountered in the messages. As it will be detailed in § 3, this set of features will be discarded in some parts of our experiments to focus on linguistically richer features.

Case. The proportion of all capitals tokens and tokens starting with an upper case was computed. Indeed, some authors tend to omit initial capital letters after sentence endings. Some writers have a tendency to "shout", i.e. write a whole sentence, or a part of it, in all caps. Two specific features were dedicated to the forms i /I, as some authors use the lower case in the emails instead of the regular upper case.

Morphologically complex words. Morphological features were also computed at the word level, once again with the CELEX database. We compiled the 30,693 morphologically complex words from CELEX, leaving out the ones formed by conversion (e.g. hand N → hand V ). These words include suffixed words (e.g. governable), prefixed words (e.g. anti-aircraft) and compounds (e.g. handbook ). Two features were computed for each message: the ratio of morphologically complex words to total words and their overall number.

Word length. Messages can also be characterized by the length of their words. For instance, the presence or absence of long words may indicate a message's technicality. Word length is also an approximate estimation of the morphological complexity of the words: longer words tend to be more complex. For each message, we counted the number of words of each length and we also computed the mean word length.

Inflections and stopwords. The inflection rate (ratio of inflected forms to lemmas) was computed and resulted in 3 features (for nouns, verbs and adjectives). The stop words rate was used as an additional feature.

Spelling errors. Spelling errors have long been identified as related to a particular author's writing specificities [START_REF] Koppel | Exploiting stylistic idiosyncrasies for authorship attribution[END_REF]. We compared each lowercase word in a message to a reference wordlist (from the wamerican Debian package), and applied a brute-force approach to check for specific spelling errors. More precisely we tested for the following errors (in order of priority): excess repeated letter, missing repeated letter, letter inversion, excess letter, missing letter, modified letter. In addition, and in cases when none of the previous tests led to a known word, we tested for word collision through automated querying of the Bing Web search engine (which, when given as input "officetoday" proposes to correct it in "office today").

The resulting features give the overall rate of misspelled words in a message, as well as specific rates for each kind of spotted error. While at first we considered letter-specific errors (e.g. repeated inversion of i and o), the lack of variety over the corpus led us to limit our features to broad categories.

Contractions and abbreviations.

A list of contractions and their corresponding full forms was compiled manually and resulted in about 200 features. These forms were then divided into the following classes: positive contraction with apostrophe (we're), negative contraction with apostrophe (isn't), positive full forms (we are), negative ones (is not), standard and nonstandard "collapsed" forms (cannot, gimme), "improper collapsed" forms (arent, thats) and a class of words used specifically in spoken language (gonna, kinda, nope, ya, . . . ). These classes resulted in 7 additional features.

A list of 450 abbreviations was compiled manually. It contained usual abbreviations such as ASAP or wrt, some taken from SMS language (e.g. 2L8 for too late) and some other originating from chat rooms (e.g. BBIAB for be back in a bit). Each abbreviation resulted in an individual feature.

US/UK variants. Two lists of roughly 550 American words and 550 British ones were manually compiled, using lexicons available from the web. These lists include alternative words (vacation/holiday, zip code/postcode), spellings (color /colour, vs./vs). The vast majority of the messages were expected to be written by American authors. However, for some authors, the use of American and British words may overlap (e.g. a message in the test set contains the British holiday and the American bill and gotten).

Binary features denote the presence/absence of the 70 British and 170 American forms taken from the aforementioned lists that occur in the Test sets. Two features account for the total number of forms (types) from both categories and two features represent the ratio of American (resp. British) forms to the number of tokens.

WordNet. A total of 12 features were based on WordNet. Four features represent the proportion of noun (resp. verb, adjective and adverb) lemmas occurring in the messages that are known from Princeton WordNet [START_REF]WordNet: An Electronic Lexical Database[END_REF]. Four additional features (one per part-of-speech) consist of the average number of synsets the words that are known from WordNet belong to. These features roughly represent the degree of polysemy of the words used by the authors. For each message, two features represent the average depth of the noun and verb synsets in WordNet's conceptual hierarchy. Two other features denote the average minimal depth for nouns and verbs. These depth-based features are indicative of semantic specificity [START_REF] Heylen | Modelling Word Similarity: an Evaluation of Automatic Synonymy Extraction Algorithms[END_REF]. Named entities. As presented above, the CoreNLP suite provides a named entity (NE) recognition and classification tool [START_REF] Finkel | Incorporating non-local information into information extraction systems by gibbs sampling[END_REF]. Therefore, we computed the relative frequency of each NE type in a message (date, location, money, number, ordinal, organization, percent, person and time).

Sentence-level features

The next set of features addresses the syntactic level. Syntax can be approached through crude techniques, or by taking advantage of the syntactic parsing provided by CoreNLP.

N-grams of part-of-speech tags. Bigrams and trigrams of part-of-speech tags (ignoring inflection indicators) were computed for all messages. The 732 bigrams and the 1,000 most frequent trigrams (from a total of 6,598) were retained. Part-of-speech trigrams have been used in [START_REF] Nerbonne | A measure of aggregate syntactic distance[END_REF] as an approximation of syntactic structures, in order to detect two groups of speakers including English and Finnish emigrants to Australia, and of adult and children among the Finnish immigrants. Part-of-speech n-grams are relevant here either because they reveal differences between native and non-native speakers, and differences in the syntactic patterns used by native speakers.

Syntactic depth and complexity. The general notion of syntactic complexity can be seen as an important feature of an author's style. In addition to the simple measure of sentence length (in number of words), we measured two different parameters for each sentence in a message.

The first is simply the depth of the syntactic tree resulting from the syntactic dependencies provided by the parser (after minor transformations). Sentences with deep trees have a large number of intermediary constituents, such as complex noun phrases, subordinates, etc. We measured both the maximal depth for each message and the average depth.

The second parameter is more directly related to the output of the parser. Following [START_REF] Mothe | Linguistic features to predict query difficulty[END_REF], we measured the average and maximal distance (expressed in number of words) covered by the identified dependency links. The resulting feature is not correlated to the tree depth, but can capture another dimension of syntactic complexity [START_REF] Tanguy | Sentence Complexity in French: a Corpus-Based Approach[END_REF]. As an example, a complex subject noun phrase (e.g. including a subordinate clause) results in an increased distance between the head noun and the verb. Syntactic dependencies. From the aforementioned syntactic parsing, a list of 2,439 types of syntactic dependencies was extracted. A dependency consists of the governor and dependent's parts-of-speech (leaving out inflection indicators), linked by a given relation. The 1,000 most frequent dependencies were retained and resulted in 1,000 corresponding features denoting the ratio between the occurrences of a given dependency in a message and the total number of dependencies. We added three more general features to represent the total number of dependencies in a message, this number divided by the number of tokens and divided by the number of sentences.

Message-level features

The fourth set of features deals with the message at a global level, and addresses a variety of linguistic issues. The following features tackle the message's typesetting, discourse structures and organization, as well as general semantic phenomena such as semantic cohesion.

Message length and general typesetting. The number of tokens, sentences, lines and the proportion of blank lines were computed for each message.

Openings and closings. The most frequent opening lines were extracted and manually selected as potentially relevant. This selection resulted in 22 features including: no opening line, proper name followed or not by a colon or a comma, greetings starting with hello/hey/hi/dear, etc.

Potential closing patterns were extracted from the messages and manually selected. First, a list of non anonymized signatures (lower case first names and family names, initials, etc.) resulted in 72 features. The presence/absence of some closing formulas (thanks/thanx/(all) the best/(best) regards/take care, etc) or of (anonymized) names resulted in 10 features. Finally, a feature was dedicated to the detection of 44 selected closing patterns, consisting of a combination of names, comma/dot, blank lines, closing formulas, etc. Distributional semantic cohesion. This last set of features was computed in order to estimate the "semantic cohesion" of an email message. The idea is to compute semantic similarity between words in a message, so that cohesive messages (dealing with a narrow topic, and thus containing many semantically related words) can be distinguished from the ones addressing multiple subjects (with many unrelated words). This kind of measure can also be seen as an attempt to capture some of the writing behaviors of authors.

Measures of semantic similarity between words can be obtained from manually-constructed resources such as WordNet or from the data produced by distributional semantic analysis. The distributional analysis assumption is that similar words can be identified according to their occurrence in similar contexts. Thus, through the syntactic processing of a very large quantity of texts, specific techniques can automatically quantify the semantic similarity between words.

We used Distributional Memory (DM) [START_REF] Baroni | Distributional memory: A general framework for corpus-based semantics[END_REF] which organizes the distributional information in a third-order tensor. It has been computed on a very large corpus of diversified texts. Specifically, we used the TypeDM model1 and its word-by-link-word matrix, which results from the tensor's matricization.

In particular, for each adjective, noun and verb in the matrix, we identified the 150 nearest semantic neighbors by calculating the cosine similarity. The features defining the semantic cohesion of the message were then obtained by counting the number of neighbors for each pair of lemmas found in the message. Different neighborhood sizes were considered: from 10 to 150 neighbors (in steps of 10).

Machine learning techniques and tools

The next step in our approach was to apply a machine-learning technique to this huge set of features. We used two different kinds of techniques, which are presented in this section.

Maximum entropy

For the author attribution tasks, we trained a single maximum entropy model [START_REF] Ratnaparkhi | Maximum entropy models for natural language ambiguity resolution[END_REF] using the OpenNLP2 MaxEnt library. While it is theoretically possible for a maximum entropy model to integrate thousands of heterogeneous features, both numeric and nominal, it is critical to normalize numeric features to avoid a bias in the model towards features with a larger numeric scale.

The features described above were collected as a set of CSV files. To simplify the task of normalizing, discretizing, training and evaluating based on features spread among dozens of files, we coded a software module, csvLearner 3 , distributed as open source, and specifically designed for collaborative machine learning projects.

Feature normalization. For the sake of simplicity, we initially tried to unify the features into a purely nominal space by applying Fayad and Irani MDL discretization [START_REF] Fayyad | Multi-interval discretization of continuous-valued attributes for classification learning[END_REF]. We then attempted two types of normalization: setting max value to 1.0, and setting the mean value to 0.5 (the latter to correctly normalize features with a handful of high outliers). Finally, we divided the features into several groups, each of which was normalized based on the max value of the entire group, while leftover features were normalized individually. By normalizing an entire group of interrelated features together (e.g. POS tag trigram counts), we avoided loss of information contained in their relative scale (e.g. relative count of each POS tag trigram for a given message).

Results for each of these normalization methods, when applied to SmallTrain using 10-fold cross validation, are shown in the table below. Since there is not a significant difference between max and mean normalization, we settled on max grouped normalization. Separating the wheat from the chaff. For tasks including unknown authors, the training sets were evaluated to find a criterion for separating known and unknown authorship. One of the main advantages of the maximum entropy machine learning algorithms is that it provides a probability for each possible outcome. Various parameters were thus considered, including p 1 (best guess probability), p 2 (second guess probability), p 1 -p 2 , z-score(p 1 ), z-score(p 2 ) and standard deviation of probabilities for all outcomes. Curiously, parameter spread for wrongly guessed messages and for messages by unknown authors was strikingly similar, and clearly differentiated from the spread for correctly guessed messages. We finally settled on p 1 alone as providing the cleanest and simplest criterion, and selected the p 1 threshold which maximized overall accuracy on SmallValid+ (p 1 < 0.66 results in 'unknown') and LargeValid+ (p 1 < 0.4). We also submitted another run which aimed at a better precision, with respective thresholds of 0.95 and 0.75.

Rule-based learning and decision trees

For the verification tasks (Verify1, Verify2 and Verify3, each dealing with a different single author), we applied a machine learning technique that allows us to get interpretable results, and thus to identify the linguistic profile of the target author. Another objective was to consider a decision scheme that does not rely on "knowledge-poor" features (mostly trigrams and word frequencies), but on linguistically-enriched features only. This decision was not motivated by the specificity of the verification subtask, but rather by the smaller size of its data and its more specific and strict aim.

We thus switched from the heavy-duty opaque maximum entropy learner to less sophisticated learning techniques. The specific algorithm for each set was simply chosen according to the compared performances on the training data.

For the Verify1 dataset, we adopted a decision tree (C4.5 algorithm [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF]) which splits the training dataset in different subsets according to the most 'informative' features, i.e. the features that maximize the information gain condition (the highest score of information gain for one feature if we use that feature to split the data). For the remaining Verify2 and Verify3 datasets, we exploited a rule-generating algorithm ('Repeated Incremental Pruning to Produce Error Reduction' or RIP-PER [START_REF] Cohen | Fast effective rule induction[END_REF]) that implements an incremental reduced-error pruning method to establish whether a rule should be pruned or not. Both classification algorithms were optimized, trained and applied in the WEKA software package4 [START_REF] Hall | The weka data mining software: An update[END_REF].

In both cases, the training data was constituted of the corresponding provided training sets, consisting of a few dozens messages by the target author, to which we added 1,500 messages written by a variety of different authors from the SmallTest training set.

Details. Figure 1 illustrates the decision tree adopted after training the Verify1 dataset. For better readability we do not indicate the exact thresholds for each decision node. The first node of the model corresponds to a specific typographic error (in this case, the absence of a blank after a question mark, see § 2.2). Other classificatory features are the amount of person named entities (see § 2.3), the distributional semantic neighbors extracted from the Distributional Memory (DM) (see § 2.5), the maximal depth of the syntactic tree (see § 2.4), the number of past participles as indicated by the POS parser (see § 2.3) and the apostrophe count for each message (see § 2.5).

Table 1 illustrates the rules resulting from the RIPPER model for the Verify2 and Verify3 tasks. In addition to some distributional semantic neighbors features, these datasets made use of This tree and these sets of rules gave us positive feedback concerning the usefulness of a variety of linguistic features. They can also tell us specific information about each target author. For example, author 1 tends to forget blanks after question marks, and uses a high number of people's names. However, the different semantic distribution scores seem to have the highest discriminative power, and yet are not very easy to interpret in terms of an author's general writing style.

Table 2 summarizes the scores obtained with the aforementioned models with respect to the three verification tasks. The scores concern the positive (target author) class, obtained on average over a 10-fold cross-validation. We initially were quite satisfied with these results, that seemed on a par with the ones obtained with the maximum entropy method, although on a very different task.

Results and discussion

The overall results of our different runs are the following: we apparently did very well for the attribution tasks, but failed for all three verification tasks. Detailed values are reported in Table 3. For the Large+ and Small+ tasks, it was indeed the low-threshold version that gave the best

Fig. 1 .

 1 Fig. 1. Decision tree model used for the Verify1 task (y = target author; n = other author)

http://clic.cimec.unitn.it/dm/#data

http://incubator.apache.org/opennlp

https://github.com/urieli/csvLearner

http://www.cs.waikato.ac.nz/ml/weka

Acknowledgements

As noted in the introduction, our success in this competitive task is the result of a team that extends far beyond the authors of this paper. Therefore we sincerely wish to thank for their insights, proposition of features and encouragements the following people (in alphabetical order): Clémentine Adam, Cécile Fabre, Bruno Gaume, Mai Ho-Dac, Anna Kupść, Marion Laignelet, Fanny Lalleman, François Morlane-Hondère, Marie-Paule Péry-Woodley and Nikola Tulechki.

results in terms of F-score: with higher probability thresholds, the precision gain was considerable but did not counterbalance the loss in recall. Many things can be learnt from these results. The first thing is that the good results we obtained for the attribution tasks may well be related to the linguistically-rich features we used in addition to more traditional word/trigram frequencies. During the training phase, we indeed observed that these features increased the estimated efficiency of the maximum entropy learner. However, we still have to investigate the amount of information added by individual features or feature sets. As noted above, this estimation is much more difficult for this kind of method than for symbolic learning, as the information about the model is accessible through a set of weights and require a detailed statistical analysis. However, we intend to test a larger number of features combinations in order to assess their exact contribution to the final results.

Another good point for our method is the apparent reliability of the probability score provided by the maximum entropy algorithm: this appears to be a good predictor that allowed our method to rank very high with the unknown author tasks. This estimation is, to our eyes, a clear advantage of this learning technique, that can have several positive implications in other tasks where maximum entropy has proven to be efficient (such as parsing).

The last issue raised is our failure in the verification tasks. It may be linked to some of the following causes: abandonment of the poorer features, switch from maximum entropy to rule-based techniques, and the fact that author verification is indeed a very different task from attribution. Each of these hypotheses will now require a specific investigation that should lead us to a better understanding of both the tasks, the applicability of the techniques and the relative advantage of our higher-level features.

As we have already noted, our main concern as computational linguists is to evaluate the effectiveness of more sophisticated language processing methods and features. In too many areas, linguistically-rich approaches have unfortunately not proven (yet) their efficiency when compared to heavy statistical methods. We hope that our work will contribute to a better understanding of how, when, and which linguistic knowledge has to be used.


Frédéric Blanchard
email: frederic.blanchard@univ-reims.fr

Michel Herbin
email: michel.herbin@univ-reims.fr

Relational Data Mining Through Extraction of Representative Exemplars

Keywords: relational data, data mining, representative, exemplar, clustering, network, Borda

With the growing interest on Network Analysis, Relational Data Mining is becoming an emphasized domain of Data Mining. This paper addresses the problem of extracting representative elements from a relational dataset. After defining the notion of degree of representativeness, computed using the Borda aggregation procedure, we present the extraction of exemplars which are the representative elements of the dataset. We use these concepts to build a network on the dataset. We expose the main properties of these notions and we propose two typical applications of our framework. The first application consists in resuming and structuring a set of binary images and the second in mining co-authoring relation in a research team.

Introduction

The data mining is interested in discovering knowledge from data. Nowadays finding interesting patterns or structures is a crucial task in the field of data analysis. Thus the paper addresses the problem of the extraction of representative elements from a dataset. This problem presents a significant interest when designing recommendation systems [START_REF] Pazzani | Content-Based Recommendation Systems The Adaptive Web[END_REF], selecting leaders or specimens [START_REF] Brun | Towards preference relations in recommender systems[END_REF], community detection [START_REF] Newman | Finding and evaluating community structure in networks[END_REF], customer Relationship analysis [START_REF] Tuzhilin | Customer relationship management and web mining: the next frontier[END_REF] or sub-sampling.

The classical ways to determine representative elements refer to the task of data clustering [START_REF] Alfred | Summarizing relational data using semi-supervised genetic algorithm-based clustering techniques[END_REF]. The goal is to partition of the dataset. Then the representative elements are the prototypes of the clusters. They can be chosen as the average elements of each cluster or selected after a random initialization step. For instance, when using k-means or k-centers algorithms (see [START_REF] Jain | Data clustering: a review[END_REF] for a review of clustering methods including k-means algorithm), the centers of the obtained clusters provide the prototypes of the dataset. The prototypes are first randomly selected and the algorithms iteratively refine the set of prototypes. The final elements are quite sensitive to the initial selection. Moreover k-means algorithm leads to average prototype which are not "real" elements of the initial dataset. this kind of methods is not satisfactory. The lacks of all the approaches based on clustering are multiple. Firstly the partition into clusters is predate to the extraction of representative elements and the clusters have to be validated and interpreted to justify the prototypes. Secondly the representative elements depend on the choice of clustering algorithms and the extraction of the prototypes depends on the implicit assumptions about the shape of clusters and data distributions. Moreover when one cluster contains more than one subpopulation, only one prototype is extracted. Finally, in the case of clustering algorithms like k-means, the centers are not elements of the original dataset. They are average computed elements. How make a mean-element meaningful ? Most of the time, providing a non-existing element (virtual element like a mean-element) does not make sense.

In this paper the approach we present consists in extracting elements we called exemplars directly from the whole dataset, without any a priori clustering step (in one pass unlike [START_REF] Frey | Clustering by passing messages between data points[END_REF]) . The exemplars summarize the dataset and are particular elements of the original dataset. Thus they are real data. These elements are as representative as possible of the whole set without any assumption on the shape or the density of data distribution (unlike in [START_REF] Lühr | Connectivity based stream clustering using localised density exemplars[END_REF]). To achieve the extraction of exemplar, we construct a degree of representativeness on the dataset. The exemplars are finally chosen as local maxima of the degree of representativeness. By fitting the locality parameter (in topological terms the scale factor ) we adapt the scale to determine the number of exemplars.

The paper is organized as follows. In the first section we introduce the context and expose our method. We present the formal definitions of scores between data, the notion of standard and the concept of exemplars in the dataset. Then we show how to build a network of exemplars to visualize these notions.

For each definition we present some interesting and remarkable properties (robustness, stability etc.) In Section 3, we provide two applications in very different context. Firstly we apply our method on a set of binary images. We compute scores and exemplars and we build the network to structure the dataset. The second application concerns the analysis of co-authoring in a research laboratory. We exhibit a coauthoring network that permits to visualize how researchers are really clustered and how they work together. Section 4 is a brief conclusion that outlines our main contributions and that expose our current and future works.

Method

Let Ω be a set of n elements in a multidimensional space. The n elements are qualitative, quantitative or mixed data. We assume that Ω is a relational data set without any underlying distribution. Let us describe the way we use to extract the exemplars of Ω structuring this set in a network. In this paper, the elements are called objects.

Pairwise Valued Relation

Ω is a relation dataset. Let us specify this relation. Let R be a pairwise valued relation on Ω. R is defined by :

R : Ω × Ω → R + (x, y) → R(x, y)
The use of a pairwise valued relation is very useful in data processing. A distance is a special case of this kind of relation. But a distance is frequently not available when processing qualitative data. Thus a relation is more widespread than a distance for pairwise comparisons of objects. In this paper, the value R(x, y) is also called the cost from x to y, indicating the generality of the relation. The relation must follow three trivial properties.

• The relation must be total. This means that each pair of objects of Ω is valued by R.

• The relation must be positive. The cost is a positive value for all pairs.

• The cost from x to x is null forall x (i.e. ∀x ∈ Ω, R(x, x) = 0) Unlike a distance, the relation does not necessarily respect the property of symmetry. R(x, y) may be different from R(y, x). For instance, if the cost from a point x to a point y is the time to go from x to y, then the cost from y to x could differ from the first one because of the slope, wind, flow, etc. Moreover, the relation does not respect the triangle inequality. A dissimilarity index gives a classical example of such a relation which does not respect the triangle inequality. x is dissimilar from y with R(x, y) and y is dissimilar from z with R(y, z) but x could be dissimilar from z with R(x, z) > R(x, y) + R(y, z). Such a relation can lead to a vote to designate exemplars within the dataset. Specifically, we can rank the objets of Ω taking into account the relation to set up votes between the objects themselves. The following subsection describes this procedure.

Score

In this paper, we select an exemplar object from Ω according to the Borda voting method [START_REF] De Borda | Mémoire sur les élections au scrutin[END_REF]. But firstly, we transform values of the relation into ranks [START_REF] Barnett | The ordering of multivariate data[END_REF][6] [START_REF] David | Order Statistics[END_REF]. Let x be an object of Ω. All objects can be sorted by the ascending order of their costs relative to x. Let us note Rk x (y) the rank of y relative to x. The rank is obtained when sorting the set {R(x, z)/z ∈ Ω}. Using Borda method [START_REF] De Borda | Mémoire sur les élections au scrutin[END_REF][21], the object x assigns a relative score to all objects of Ω. The score Sc x relative to x is defined by:

∀y ∈ Ω, Sc x (y) = n -Rk x (y)
where n is the number of objects of Ω. Thereby the relative score is an integer and it lies between 0 and n -1. The lower the cost from x to y, the higher the score of y relative to x. Computing all relative scores, each object x receives n relative scores corresponding to the votes of all objects of Ω (i.e. the n values Sc y (x) with y ∈ Ω). Then the relative scores are aggregated to choose the winner of the voting procedure. The aggregate score is defined by:

Sc : Ω → R + x → Sc(x) = 1 n y∈Ω Sc y (x)
In this paper, the aggregation function is the mean function.

Let us observe the aggregated scores in a relational dataset. Figure 1 displays an example of a dataset with 120 two dimensional random samples (A). Euclidean distance is used as the pairwise valued relation between samples. The respective aggregated scores (B) confirm that the score increases when the sample approaches the center of the dataset, i.e. in the midst of this one.

Standard

The object with the highest aggregated score is the standard we propose. Let us observe some properties of the standard. When resampling the dataset using the bootstrap technique [START_REF] Thomas | Use of the bootstrap in robust estimation of location[END_REF], the standard could change. If it does not change, the extraction of this standard is robust against the resampling. Using many bootstraps, the highest frequency of the extracted standards indicates the stability of the standard when resampling. Our experiments using simulated data and real data show that the standard depends very weakly in the resampling. Figure 3 displays the standards obtained when resampling the datasets (A), (B), and (C) of Figure 2. The initial datasets have 100 elements displayed with crosses. Stems with filled circles show the frequencies of the standards obtained with 200 bootstraps. The extracted standards remain in the center of respectively A, B, and C. The frequencies of the most frequent standards when resampling the 100 initial samples are respectively equal to 40%, 32%, 36%. These frequencies assess the stability of the standard with respect to the samples. Respectively 90%, 88%, and 90% of the dataset elements are never extracted as standards when resampling. Thus we assume that a standard gives a clue on the center of the dataset. Because the standard is a real element, it avoids the nonsense that the classical averages could produce with a virtual out-of-scope element outside of the data distribution. Note that the stability of the standard (i.e. the frequency of the most frequent standard) increases when the number of objects increases. Let us examine the stability of the standard when outliers are feared. We simulate outliers that we append to an initial dataset. We consider that the standard extraction is robust against outliers when the extracted standard remains one of three most frequent standards of the initial dataset. In this paper we describe the study of robustness (see [START_REF] Rousseeuw | Robust Regression and Outlier Detection[END_REF] for more details about the concept of robustness) using the datasets A, B and C of Figure 2. The outliers are random elements out of the range of the initial data domain. In this section, the domain is defined by elements of coordinates (x, y) where -10 ≤ x ≤ 40 and -15 ≤ y ≤ 15. Outliers are simulated in a larger domain defined by -10000 ≤ x ≤ 40000 and -15000 ≤ y ≤ 15000 (the initial limits are multiplied by 1000) excluding the elements that are too close from the initial domain by keeping the elements (x, y) where x ≤ -1000 or 4000 ≤ x and y ≤ -1500 or 1500 ≤ y (the limits of initial domain are multiplied by 100). We add such random outliers to an initial dataset until the extracted standards changes (i.e. until the extracted standard from the new dataset with outliers will not be one of the three most frequent standards of the initial dataset). When outliers are randomly generated in a such very large domain, the percentage of outliers could be higher than 200% without changing the initial standard. Then the standard is robust when the outliers are spread in a large domain. But the standard remains also robust when outliers are concentrated into only one duplicate object. When only one outlier is randomly generated in the very large domain, we could add up to 20% of out-of-range elements using this single outlier without changing the initial standard. Then we assume that the standard is particularly robust against outliers.

Exemplars and Networks

The standard is the only exemplar extracted from a dataset. But the dataset may be complex and it could require more than one exemplar to represent the whole set. This section describes how the dataset can be structured to retrieve these exemplars from the set. The first step consists in defining the neighborhood of each object within Ω. Let x be one of the n objects of Ω. Let k be a value between 0 and n. The k-nearest neighbors of x are defined using the ranks relative to x. Then the k-neighborhood of x in Ω is defined by:

∀x ∈ Ω, ∀k ∈ 1, n , N k (x) = {y ∈ Ω/Rk x (y) ≤ k} Thus N k (x) is the set of k nearest objects of x.
In a second step, each object x is associated with the neighbor having the highest aggregated score. Thus we define a link from x to its preferred neighbor. Each object x is linked to an object y. The links are defined by:

∀x ∈ Ω, x → y = argmax z∈N k (x)

Sc(z)

In this definition, x is linked to y and y is generally different from x when Sc(y) > Sc(x). If Sc(x) is maximal inside N k (x), then y = x and x is linked to x itself. These self-linked objects are simply called exemplars of Ω. Using the links, the dataset becomes a network where the nodes are the objects. The exemplars becomes the terminal nodes of this network (i.e. the roots of the trees forming the network). The exemplars depend on the value of k which influences the network configuration. In this paper, k is the size of the neighborhood we use. This parameter is called scale factor. Figure 4 displays four networks obtained from the simulated dataset of Figure 1 (A). The dataset has the 120 samples (n = 120). The four networks are configured using the scale factors 5, 10, 20, and 40. The exemplars are displayed with a filled circle, they are the terminal nodes of the networks. The numbers of extracted exemplars are respectively equal to 8, 4, 2 and 1. Distinctly the number of exemplars depends on the scale factor k. The following describes the influence of the scale factor.

Exemplars and Scale Factor

The higher the scale factor, the lower the number of exemplars. Moreover, when the scale factor increases from one to n, the number of exemplars decreases from n to one. Let us explain this property. When k = 1, N 1 (x) is the singleton equal to x. Therefore each object x is itself an exemplar of Ω (i.e. x is linked to x). Then the set of exemplars is Ω and the number of exemplars is equal to n. When k = n, N n (x) is equal to Ω. Each object x is linked to the standard which has the highest aggregated score within Ω. Then the number of exemplars is equal to 1 the network becomes only one tree and the standard is its root. At the scale k, an exemplar x has the highest aggregated score within the neighborhood N k (x) (i.e. within the k nearest neighbors of x).

If k 1 ≤ k 2 , then N k1 (x) ⊆ N k2 (x). If
x is an exemplar at the scale k 2 , then it is an exemplar at the scale k 1 . Therefore the number of exemplars necessarily decreases when the scale factor increases. Increasing the scale factor, some exemplars could disappear among those who were extracted. But an object never appears as an exemplar if it was not extracted at lower scale factor. Figure 5 displays the duration of each exemplar when increasing the scale factor. The exemplars are extracted from Figure 1 dataset (n = 120). When the scale factor is equal to 1, all the objects are exemplars. When the scale factor increases, some exemplars disappear and their duration is shortened. Only the standard is kept from scale 1 to the scale n. It has the longest duration equal to n. , Figure 5: Duration of exemplars increasing the scale factor: The Figure 1 dataset has 120 objects (n = 120). The scale factor increases from 1 to 120. When the scale factor is equal to 1, all the objects are exemplars. When the scale factor increases, some exemplars disappear. Only the standard is always extracted when increasing scale factor. Then its duration is equal to 120.

At the scale k, we assume that the numbers of exemplars is smaller than n -(k -1) where k is the scale factor and n is the number of objects of the dataset. At each scale k, we want to reduce the number of exemplars. When this number is equal to n -k + 1, we consider that the extraction of exemplars is suboptimal. This case is observed when k = 1 or k = n. In this paper, the scale factor becomes optimal when the difference between n -k + 1 and the number of extracted exemplars is maximum. Let k optimum be this optimal value of the scale factor we propose in this paper. Figure 7 displays the exemplars obtained with optimal scale factor from the datasets ((A), (B), and (C) on the Figure 2). The random datasets have 100 samples (n = 100). k optimum is respectively equal to 9, 7 and 10. The filled circles display the exemplars and a larger filled circle shows the standard.

Applications

This section presents applications of our method in two typical and very different contexts. The first application consists in extracting exemplars from a binary image database and building the graph of exemplars of this database. The second application present an analysis of the co-authoring in a research team by extracting exemplar authors and exhibiting the implicit structure.

Extraction of exemplars from a set of binary images

In this first application we consider a set of binary images contained in a database. The goal is to extract exemplar images from this database. The interest could be providing a set of resuming images or distinguishing subsets of images according to their content. The database is presented in the Table 1. In a first we construct the relation matrix by using the Asymetric Haussdorff Distance. Classical methods of clustering have to work with symmetric distance. They are inapplicable when distance from an image A to image B is not equal to distance from image B to image A. As we wrote at the beginning of this paper, the symmetry property is not required in our method. Table 1: Binary images sorted by decreasing score Firstly, we compute the score of each image of the database. The table 1 represents the images sorting by decreasing order of scores. Secondly we build the associated directed graph presented in Figure 8 and representing the exemplars network (with a scale factor of 4). This graph show how the dataset is structured. We can observe that the connected components of this graph are grouping image according to the object they represent. The three images of the Table 3.1 are the exemplars of this dataset and provide a good summary of the whole dataset.

Table 2: Exemplars extracted from the set of binary images of the Table 1 .

Figure 8: Network of the binary images where each image is connected to one exemplar. This directed graph exhibits three connected components forming three clusters coinciding with the content of images

Exploration of co-authoring network

The second application of our concept deals with publication data inside a laboratory, a research team or any other group of researchers. Co-authoring informations can be considered as relational data ( [START_REF] Mcgovern | Exploiting relational structure to understand publication patterns in high-energy physics[END_REF], [START_REF] Neville | Clustering relational data using attribute and link information[END_REF]). In this work, we consider that the value of the relation from a researcher named Alice to a researcher named Bob is computed as the sum for each common publication of the product of the number of coauthor on the publication and the number of publication of Alice. This relation is not symmetric. In fact, generally, Alice can be the "preferred" co-author of Bob, but Bob is not necessarily the "preferred" co-author of Alice. This valued relation characterizes the "quality" of links between the members and takes account of their publication activity.

The dataset we used is the set of publications of the CReSTIC Laboratory (University of Reims, France) [3]. This informations are extracted from the web site of the laboratory and have been anonymized.

The graph of the Figure 9 represents this dataset. Each node is a lab member and each edge between two members represents one common publication. Different colors are used to represents the different teams that compose the laboratory (but this information is not used in the computation of the exemplars). Therefore the scale factor is not used in this application because the size of the neighborhood is implicitly fixed in the dataset (according to the number of co-author of each member of the team).

After computing the scores, we built the exemplars graph represented on the Figure 10. The size of the node is proportional to its score. This graph is displayed using the same position for the nodes. In the Figure 11, the nodes are rearranged to propose a clearer visualization. Figure 10: Representative Network extracted from data of Figure 9. The higher is the score of one researcher, the higher is the diameter of its vertex in the graph. In this graph, each edge is the link of one researcher to its exemplar. The graphs presented in the Figures 9, 10 and 11 show several interests of our method. The first interests is the simplification of the graph of the Figure 9. When the numbers of vertices and edges are growing the graph becomes more unreadable. For big data, resuming and simplifying is a necessary task. The second interest is to exhibit such a sub-structure of the team (this task is called community detection in a network [START_REF] Papadopoulos | SkyGraph: an algorithm for important subgraph discovery in relational graphs[END_REF]). The Figures 10 and11 show how groups are connected, and which members are the most representative. The exemplars members are connecting the others and can be viewed as natural leaders (or natural mentors) according to their publications and their co-authors. It emphasizes the important (critical) position of some members in a research team. Incidentally, we can observe that the resulting clustering obtained by parti-tioning the graph in connected components is a little bit different of the real partitioning in sub-groups (represented by the different colors)

Conclusion

In the framework of data mining, this paper describes a new way for extracting exemplars from a relational dataset. The method we propose is based on a pairwise comparison assuming a coarse relation on the dataset. This approach is particularly adapted when no distance is available or meaningful in the data domain. Moreover the coarse relation between data does not need symmetry or transitivity properties. Thus the method is useful for any kinds of relational data. An aggregated score is defined from these pairwise comparisons. The paper defines the standard which is the sample with the highest score. Simulations show the robustness of the standard against outliers and the stability of the standard when resampling the dataset. Thus these results confirm the standard as a robust location estimator. Moreover the aggregated score is used to extract exemplars which are real objects. Then our approach of location estimator avoids the drawbacks of average objects which are meaningless when processing qualitative data. Using a score based on the pairwise comparison, we define the k nearest neighbors of each datum. This approach permits us to extract exemplars depending on this k value. We state that the number of local exemplars decreases from n to 1 (n is the number of data samples) when k value increases from 1 to n. Thus k is considered as a scale factor. The method we propose allows us to explore the dataset through different scales. We can adjust the k value for extracting a reduced number of exemplars. An automated approach is proposed to determine an optimal number of exemplars. On top of the extraction of exemplars, the method proposes to design a network. The paper shows that the network is reconfigured when the scale factor changes. The network eases the explanation of the exemplar roles in the dataset. When the scale factor increases, some exemplars could disappear keeping the most important ones (i.e. the exemplars which are important nodes for connecting some data).

In future works we propose to use the fuzzy set theory as in [START_REF] Blanchard | Data representativeness based on fuzzy set theory[END_REF] to generalize our framework in the case of fuzzy relation, when ranking data is not easy. The major way we would to explore is the area of Social Network Analysis. We are convinced that our concept of exemplar could be a significant tool for extracting leaders or mentors in social network and improve recommendation systems. Our concept of degree of representativeness should be compared to the different definitions of centrality in a network [START_REF] Pfeiffer | Probabilistic paths and centrality in time[END_REF].

Figure 1 :

 1 Figure 1: Example of a dataset with 120 random samples (A) and their respective aggregated scores (B). The score increases in the midst of the dataset

Figure 2

 2 displays three datasets A, B, and C. Each dataset has 100 random samples (n = 100). The aggregated scores are computed using Euclidean distance as pairwise valued relation. The maxima of aggregated score are respectively 68.75, 70.55, and 68.77 for A, B and C. Filled circles indicate the three respective standards with the highest aggregated scores. Figure 2 confirms that each standard lies in the midst of its dataset.

Figure 2 :

 2 Figure 2: Standard examples (filled circles) for respectively the datasets (A), (B), and (C). The datasets have 100 random samples. The aggregated scores of the standards are respectively 68.75, 70.55, and 68.77.

Figure 3 :

 3 Figure 3: Frequencies of the standards when resampling the datasets (A), (B), and (C) of Figure 2. The crosses show the 100 initial objects of the datasets. Stems with filled circles show the frequencies of the standards obtained when using 200 bootstraps. The most frequent standards appear in (A), (B), and (C) with respectively the frequencies of 40%, 32%, 36%.

Figure 4 :

 4 Figure 4: Networks obtained with scale factor k = 5, k = 10, k = 20, and k = 40. The networks are built between the 120 samples of Figure 1 (A). The exemplars are displayed with black filled circles.

Figure 6 Figure 6 :

 66 Figure 6: Number of Exemplars from Figure 1 (A) dataset and Scale Factor : The number of exemplar is smaller than 120 -(k -1) where k is the scale factor and 120 is the number of objects of the dataset. The difference between 120 -(k -1) (line) and the number of extracted exemplars (cross) is maximal when the scale factor is equal to 9 (filled circle).

Figure 7 :

 7 Figure 7: Optimal Scale Factor and Exemplars : The exemplars are extracted from the datasets (A), (B), and (C) of Figure 2. The optimal scale factors are respectively 9, 7 and 10. The numbers of exemplars (filled circles) are respectively 4, 3, and 3, larger filled circles show the standards.

Figure 9 :

 9 Figure 9: Digraph of the co-authoring in a laboratory. Each vertex is one researcher and each edge corresponds to one common publication.

Figure 11 :

 11 Figure 11: Network extracted from data of Figure 9 after rearranging the vertex positions (to increase the readability)


Nesrine Khabou
email: nesrine.khabou@gmail.com

Ismael Bouassida Rodriguez

Mohamed Jmaiel
email: mohamed.jmaiel@enis.rnu.tn

Context classification and context analysis approach for collaborative ubiquitous systems

Keywords: Ubiquitous computing, context awareness, adaptation, context analysis techniques, trend, peak, burst

Taking advantage of contextual information is very important for context aware applications especially in a mobile collaborative environment. This kind of applications adapt their behavior (self-adaptability property) according to the user needs, the available resources and the surrounding environment. This property is enforced by four phases; monitoring the application and its environment, analyzing context changes, planning adaptation actions and executing the planned actions to respond to context changes. In this paper, we focus and discuss the second phase. First, we propose a novel context classification which covers almost all of the context aspects. Then, we propose an analysis approach for collaborative ubiquitous systems. Our approach relies on different kinds of thresholds. Once relevant context changes occur, the context aware application will be notified to trigger its suitable process dynamically in order to deal with the changes.

I. INTRODUCTION AND RELATED WORK

With the great growth of mobile devices such as laptops, palm tops and smart phones and the evolution of the communication technologies, a new communication paradigm has been emerged. In this paradigm, the ubiquitous computing concept has been introduced by Mark Weiser in 1991 [START_REF] Weiser | The computer for the 21st century[END_REF]. The vision of ubiquitous computing adopts the idea of building smart environments where computing and communication are everywhere, being embedded in almost every surrounding object and can be accessed every time. In this paradigm, the behavior of the devices is unpredictable due to the environmental changes (temperature, pressure, noise, etc.), the execution context changes such as the network connection failure, the devices joining and leaving the network, etc. Hence, the need for sensing and detecting context changes to adapt the application behavior remains a challenge. This ability to sense and detect context changes is generally referred to as context awareness. Moreover, context awareness is central to ubiquitous computing and a key issue for making the devices aware of their situations. Therefore, the development of context aware applications requires the fulfillment of different phases. First, context monitoring which aims at collecting context information from different sources. In fact, some studies have addressed this issue by proposing monitoring techniques such as the work achieved in [START_REF] Ben Halima | Non-intrusive qos monitoring and analysis for self-healing web services[END_REF].

Because the diversity and the heterogeneity of these information, it is suggested to classify them in order to facilitate the context manipulation. Many researchers have proposed several classifications of context. Some studies classify the context into two categories like [START_REF] Mitchell | Supporting the development of mobile contextaware computing[END_REF], [START_REF] Schmidt | Ubiquitous computing -computing in context[END_REF], [START_REF] Prekop | Activities, context and ubiquitous computing[END_REF]. Schmidt et al. state two context classes such as physical environment and human factors. Mitchell [START_REF] Mitchell | Supporting the development of mobile contextaware computing[END_REF] divides the context into two classes. A personal environment formed by the user's interest, the user's location and an environmental context formed by the weather context. Other studies classify context to several categories like [START_REF] Rodden | Exploiting context in hci design for mobile systems[END_REF] and [START_REF] Schilit | Context-aware computing applications[END_REF]. Schilit et al. [START_REF] Schilit | Context-aware computing applications[END_REF] define the context as the constantly changing execution environment. In fact, the execution environment is the computing context formed by the available processors, the network capacity, and the connectivity; the user environment which contains the user's location, his social situation. Finally, the physical environment. In order to achieve a better understanding of the concept across a time span, Chen et al. [START_REF] Brown | Context-aware applications: from the laboratory to the marketplace[END_REF] add time context such as the time of the day, the week, the month and the season of the year.

Context classification is an important step to discover the possible context easily, simplify the context manipulation including context analysis. In fact, the context analysis's purpose is to analyze context information and identify context changes. In the context changes detection research direction, several techniques and models are proposed in order to reveal the context changes. In fact, in [START_REF] Cioara | A self-adapting algorithm for context aware systems[END_REF], Cioara et al propose to use the context entropy concept for detecting the context changes and determining the degree of fulfilling a predefined set of policies. Moreover, context situation entropy defines the level of the system's self and execution envionment disorder which is measured by evaluating the degree of respecting a set of policies. Hence, once the context entropy exceeds a fixed threshold, then the system is in a critical state and it must execute adaptation actions. Although this approach allows self adaptation following context changes, it does not consider many context parameters to study as it is restricted to external parameters such as temperature, humidity and light etc.

In other studies, context changes are picked up by comparing a context value saved in a repository with a new context value. In fact, in [START_REF] Zheng | Towards a context-aware middleware for deploying component-based applications in pervasive computing[END_REF], Zheng et al have addressed the issue of context change detection by proposing a contextaware middleware which conforms to the CORBA component model. The proposed middleware is composed of context aware services such as a context collector, a context interpreter, a context repository and a context analyzer. The latter is in charge of filtering and analyzing context information to determine relevant context changes and notifies the application afterwards. Furthermore, context filtering is based on a comparison of the context values saved in the context repository with the new context value in order to detect context changes.

The proposed middleware enables to save the scare resources. In fact, the component deployment is performed "just-in-time". However, this middleware does not specify context information to take into account. Another approach for dynamic context management is proposed in [START_REF] Taconet | Ca3m: A runtime model and a middleware for dynamic context management[END_REF]. Indeed, Taconet et al [START_REF] Taconet | Ca3m: A runtime model and a middleware for dynamic context management[END_REF] present CA3M, a context aware middleware, which enables applications to adapt their behavior by dynamically taking into account context changes.

They model the application by "entities", which represent a physical or logical phenomenon (person, concept, etc.) and "observable", which defines something to observe. For instance, a mobile device state is an example of an observable which may take a finite number of values (e.g low battery, almost low battery or normal battery). They consider that the change of an "observable" state or even the observation goes past a given threshold from the last notified value leads to a different application behavior.

In [START_REF] Rodriguez | A model-driven adaptive approach for collaborative ubiquitous systems[END_REF], Bouassida et al proposed a model driven approach for collaborative ubiquitous systems. In order to detect context changes, they specify predefined thresholds. Then, once context values remain below/under the threshold values, a notification is raised. Although this approach enables to detect instantly context changes, it may cause false detections as well as missing alarms by using fixed thresholds.

The rest of the paper is organized as follows. In section II, we introduce a case study named "Smart campus system". Its purpose is to provide suitable services to users according to the context changes. The proposed approach is presented in section III. Our approach defines a novel context parameter classification which takes into account the parameter evolution behavior. Then, we present the analysis approach that allows an application to analyze context and detect context changes using thresholds. In section VI, we motivate and illustrate the feasibility of our approach through an illustrative scenario. The last section concludes the paper and gives some directions for future work.

II. CASE STUDY: SMART CAMPUS

To motivate the use of our approach, we introduce in the following an example of a smart campus system illustrated in Figure 1. Smart campuses, with the ability to collect and analyze date are built in order to benefit the institution, the students and the teachers by providing services which facilitate interaction between the actors such as the teachers, the students and the technicians. For instance, every actor is equipped with a personal device (PDA, smart phone, PC, tablet, etc) and the smart campus system provides different services to actors based on their current situations. To maintain the collaboration among students and teachers, the actors' devices need to be aware of their environment, their execution context, etc . Consequently, smart campuses contain an infrastructure that allows devices and systems to be monitored and adapted automatically according to the changing context. Our work focuses on several parameters such as temperature, pressure, position and light which need to be monitored in response to the changing context. Furthermore, a multitude of resources such as the available memory, the energy, the CPU load and available bandwidth should be considered and supervised to assess both the devices and the communication state and react in a convenient way either by switching devices or improving the links quality.

An efficient smart campus relies on the cooperation of smart devices. Indeed, the campus architecture depicted in the Figure 1 involves different kinds of participants. On the one side, three controlling servers called Smart Campus Servers (SCS) namely SCS1, SCS2 and SCS3, which are Ethernet-connected and equipped with important storage and high computational capabilities. On the other side, fixed and mobile actors are equipped with sensors, accelerometers, thermometers, GPS, cameras, mics, etc. These mobile actors are usually resource constrained in terms of memory, bandwidth and energy for example. Hence, a periodic monitoring by the controlling servers is needed in order to check their state which changes according to context. Three gateways called Smart Campus Gateways (SCG), SCG1, SCG2 and SCG3 implementing software interfaces are used to connect devices to the corresponding controlling servers to exchange relevant information. The campus space is composed of separate buildings. Each one corresponds to a department such as physics department (Department2), biology department (Department3), computer science department (Department1), etc. In each department, there is a number of classrooms and offices. Each office and classroom is equipped with devices such as smart air-conditioner, a presence sensor and a luminosity sensor used to supervise the environment parameters of the department. Other devices (mobile phones, tablets, PDAs, etc.) are carried by mobile actors such as students and teachers.

III. THE PROPOSED APPROACH

Towards detecting context changes, we propose a novel analysis approach which aims at raising notifications if context changes occur. In order to achieve the mentioned goal, the application should perform a set of tasks. First, it should collect information, then analyze contextual information. Finally, the application should trigger the appropriate adaptation actions. Moreover, our approach depicted in Figure 2 involves two main components. A context provider responsible for providing context information. A second component namely a context manager is in charge of managing and handling context information. Furthermore, the activity of the context manager is divided into four modules.

• A context collector module: Responsible for managing sensors and collecting context information.

• A context interpreter module: It aims at processing contextual information and shielding off the information which is not useful to the application.

• A context database module: Filtered and processed contextual data are stored into the context database module for further retrieval.

• A context analyzer module: Responsible for analyzing stored contextual information and detecting context changes.

In our work, we focus on the context analyzer module. It retrieves context information from the context database module, analyzes it and identifies the context changes using thresholds. Afterwards, the context analyzer module notifies the application in order to execute the appropriate adaptation actions.

• For instance, all SCSs namely SCS1, SCS2 and SCS3 mentioned in section II (case study) are equipped by context databases and context analyzer modules. In fact, the SCSs need a set of context information parameters retrieved from the context database module in order to analyze them and generate appropriate notifications.

• The gateways SCG1, SCG2 and SCG3, when forwarding information from the devices to the SCS, filter the received data. For that reason, the gateways used in the smart campus application hold context interpreter modules. Then, only meaningful contextual information are stored in the context database modules.

• Each mobile device such as a tablet, a PDA, a smart phone is equipped with a context collector module that enable to capture context information such as light, temperature and forward the obtained data to the SCSs through the gateways.

For example, an actor equipped with its tablet holding a context collector (GPS for example) reports periodically the actor's position to the SCS1 through SCG1 as illustrated in Figure 1. The SCS1 receives the filtered data from SCG1, stores it in the context database module. Later, these information are analyzed and the SCS1 takes the appropriate decision. For instance, according to the position of the actor equipped with a tablet as depicted in Figure 1 , the SCS1 decides to switch off the lights in R14.

• Towards controlling their own state, mobile devices hold also a context analyzer module. In fact, each mobile device uses its context analyzer module to identify its resource context changes namely the battery level, the memory consumption, the CPU load, etc.

• Resource context related to the device

This class corresponds to the resources which characterize the device such as the available memory, the CPU frequency, the CPU load and the battery level.

• Resource context related to the network communication This class deals with the resources that identify the network communications such the loss rate, the network bandwidth, the network connectivity, the communication link load and the latency.

Despite the simplicity and the ease of the resource based classification, it remains specific to some context parameter types. In fact, this classification is restricted only to computing context described in section I. Since our work addresses a large amount of context parameters, our interest focuses on quantitative context parameters b) Quantitative centric classification: Since context parameters evolution is highly dynamic especially in ubiquitous environments, we propose to divide the quantitative context parameters into three families according to the context parameter evolution. Indeed, this classification covers almost all the context parameter types. Three classes are identified. Parameters whose behavior is characterized by a trend, parameters whose behavior is characterized by peaks and parameters whose behavior is characterized by bursts. Afterwards, we present each family separately.

1) Parameters whose behavior is characterized by a trend:

A trend is defined as the "long term" movement in a time series without irregular and abrupt effects. It is the underlying direction (an upward or downward trend) in a time series. This class deals with parameters whose behavior evolves in a constant way within time-That is the parameter model roughly coincides to a trendline as illustrated in Figure 3.

• For example, each mobile device such as PDA, mobile phone, etc. mentioned in section II periodically monitors its resource state. In fact, for each mobile device, the battery level, the memory consumption evolve in a relatively constant way. Besides, the latency defined as the time elapsed between the delivery of the message by the gateway and its reception by the controlling server can be modeled by a trend. 2) Parameters whose behavior is characterized by peaks: Peaks are defined as high values with sharp rise followed quickly by sharp fall implying a narrow period width [START_REF] Palshikar | Simple Algorithms for Peak Detection in Time-Series[END_REF]. Otherwise, we define a peak "P" by its amplitude "A p " and its period "T" as depicted in Figure 4. In fact, the peak is a very narrow period of high values-That is, its amplitude "A p " exceeds for n times the average amplitude "A av " of the time series formed by the parameter behavior. Hence, the parameters belonging to this class are those characterized by abrupt changes in their behavior as depicted in the Figure 4. Otherwise, a peak is defined by the following formulas:

A p = n × A av T ≤ m × T imeU nit
Where A p defines the peak's amplitude, A av defines the average amplitude of the parameter behavior, n and m are constants fixed by the application designers.

The SCSs receive the monitored data from the mobile devices in order to analyze them. For that reason, the SCSs CPU load can rise suddenly reaching high values after a high rate of clients requests. Hence, the CPU load especially of the SCSs is modeled by a peaked function. The link load as well as the available bandwidth belong also to this context family.

3) Parameters whose behavior is characterized by a burst:

A burst consists on a relatively wide contiguous region of values. Otherwise, a burst is defined as a large number of occurring events [START_REF] Klan | Towards burst detection for non-stationary stream data[END_REF]. As depicted in the Figure 5, we can model the wide region by an ON period and the other by an OFF behavior [START_REF] Yang | Designing traffic profiles for bursty internet traffic[END_REF]. The ON-period models a single flow such as the transfer of a single web page, and the OFF-period models the user's thinking time. Noting that the ON-period and the OFF-period are strictly alternating. The message number received during an ON-period can be modeled as a burst.

Since our interest focuses on context parameters evolution behavior, in the following we detail the threshold calculation for the quantitative centric classification which takes into account the parameter evolution behavior.

B. Threshold calculation

We have proposed a parameter context classification which takes into account the parameter evolution behavior. As we base our approach on thresholds for detecting context changes, we present threshold calculation for each parameter class.

For each class parameter, we propose to assign a number of thresholds. For each threshold, we attribute a notification or a signal. The latter is defined by an expert and it corresponds to an emergency degree or a need for adaptation that depends on the need of an expert or the application itself. The threshold values can be either predefined or adaptive ones.

Afterwards, we explain some element about threshold calculation for each parameter class detailed previously.

1) Threshold calculation for the parameters whose evolution behavior is characterized by a trend: For this class, the parameter evolution behavior is described by a trend. In order to avoid false detections as well as missing alarms, we need to define thresholds which are uncorrelated with the parameter behavior. A notification is raised when the parameter behavior crosses the threshold as depicted in Figure 6.

Different kinds of thresholds can be applied for this class, such as fixed thresholds, adaptive thresholds and step function thresholds.

For instance, fixed thresholds may be defined by the application designers according to the parameter characteristic. Then, a notification is raised once the parameter value crosses the threshold as depicted in the Figure 6(a).

For the adaptive threshold denoted in the Figure 6(b), mathematical methods can be applied in order to update threshold values at runtime such as the Exponential Weighted Moving Average technique used in [START_REF] Lahyani | Qos monitoring and analysis approach for publish/subscribe systems deployed on manet[END_REF]. However, for this kind of resource context characterized by a trend, adaptive threshold must be uncorrelated with the resource evolution behavior in order to avoid false detections and missing alarms. Finally, for the step function threshold described in the Figure 6(c), thresholds are defined per period and notifications are raised when the resource behavior crosses the thresholds.

• The memory consumption can be modeled by a trend as mentioned in part III-B. Each mobile device needs to monitor and analyze the memory consumption to evaluate its state. So each mobile device compares periodically its memory consumption state with the threshold. A signal or a notification is raised when there is an intersection between the threshold and the parameter behavior as illustrated in Figure 6. 2) Threshold calculation for the parameters whose evolution behavior is characterized by peaks: Identifying and detecting peaks in a given time series is important in order to react accordingly and to avoid undesirable effects. The key question is how to set the correct threshold so as to minimize false positives. In this class parameter, the idea consists in specifying adaptive thresholds that are correlated with the parameter evolution behavior. In fact, using fixed thresholds in this class could maximize false alarms. Furthermore, since peaks characterize sudden changes form a normal behavior to an abnormal one, adaptive threshold correlated with the parameter evolution behavior remains under the resource shape. So, a violation of the threshold indicates a context changes. • As mentioned in section II (case study), the servers receive periodically contextual information from the devices through the gateways. In case of a large amount of data, the CPU load of the servers could be overloaded.

This overload is identified when the CPU load oversteps the adaptive threshold for this parameter class. 3) Threshold calculation for the parameters whose evolution behavior is characterized by a burst: Burst is an unusually large number of events occurring within a certain ON-period of time T i . To the best of our knowledge, thresholds cannot be applied for this parameter class. So our idea consists on transforming a bursty model into a peaked model. So we propose to apply an aggregate function g in each ON-period. The aggregate function application is illustrated in Figure 8. As depicted in the Figure 8, the obtained model roughly coincides with a peaked function. Since we apply adaptive thresholds in this class parameter, a notification is raised when the parameter behavior crosses the threshold calculated in an ON-period.

For example, the gateway SCG1, is equipped with a context analyzer as described in section III. The maximum queue size for this device is set by the application designer. So that, if the traffic received by this gateway in a period T i exceeds a maximum, then a burst is identified in T i . Towards detecting bursty periods, applying the aggregate function g consists in calculating the slope of the scatter diagram obtained in each ON-period as depicted in the Figure 9(c). Second, in each ON-period, we compute the intensity of each slope formed in each ON-period. We obtain the figure 9(c). Consequently, if the slope intensity exceeds the threshold, then a burst is detected and appropriate reconfiguration actions are launched.

IV. ILLUSTRATIVE SCENARIO

In this section, we consider the case of a smart campus as shown in section II (case study). We focus in the interaction of the actors of the Department1 and SCS1 through SCG1. The Department1 is used by the unit researchers, the teachers, the students to achieve their work and to enhance collaboration between the different actors.

• For instance, at the beginning of each course session in R11, R12, R13 and R14, the presence sensor located in each room captures and localizes the mobile actors.

Their positions is then forwarded to SCS1. SCS1 holding a context analyzer module as illustrated in section -In case of a large amount of data received by the gateway SCG1 at a time t i , the load of SCG1 increases rapidly reaching a high value (i.e a peak) and exceeding the adaptive threshold. The analysis algorithm integrated in SCG1 raises a notification and the gateway decides to split its load with its neighboring gateway namely SCG2. -During the holidays, the SCS1 receives empty positions from the presence sensor (position=0) due to the non attendance of the teachers and the students. SCS1, by using the analysis algorithm based on thresholds finds that the threshold is always exceeding the context parameter (position). Consequently, the lights are switched off in R11, R12, R13 and R14 in order to reduce the power consumption.

• Each student participating to a course uses a tablet device to which the course will be dispatched through bluetooth. The tablet device holds the analysis algorithm described in section III in order to detect context changes. During the course, the students' tablet display appropriate slides and they follow their courses. Furthermore, the students can write annotations on their tablets and publish their comments to share knowledge between all the group members to enrich the course and enhance the collaboration. A student holding a tablet is participating to the course by exchanging information and slides. For each amount of data received, the tablet device retrieves the memory consumption from the operating system using probes. Then, it compares each value with the threshold which can be either predefined, adaptive or step function since memory consumption belongs to the trend context parameter class. The tablet detects that at a time t i , the memory consumption exceeds the threshold. So, the device displays a message preventing from receiving data. This scenario highlights the interaction of the campus application with context in such a way that it can detect context changes using the analysis approach in order to adapt its behavior accordingly.

V. CONCLUSION AND FUTURE WORK

The challenges for context aware applications design and implementation are to handle both context capture, context classification, context analysis and to react dynamically to every context changes. In this paper, we have proposed a novel context classification based on context parameter evolution behavior. Three classes have been identified. Context parameters whose behavior is modeled by a trend, context parameters whose behavior is modeled by peaks and context parameters whose behavior is modeled by bursts. Then, we have presented an analysis approach which aims at analyzing context and identifying context changes. The analysis approach is composed of a context provider and a context manager. The context provider is out of the scope of this paper. We focus on the context manager. It is divided into four modules namely a context collector module, a context interpreter module, a context database module and a context analyzer module. The context analyzer module is the main component of our analysis approach. It is responsible for retrieving context information from the context database module, analyzing stored context information, identifying context changes and notifying the context aware application. Towards detecting the changes, the context analyzer module relies on thresholds which can be either fixed, adaptive according to the context parameter class. As future work, we plan to stretch the context parameter classification. For further development, we intend to implement our analysis approach as a first step and to integrate it into the framework FACUS [START_REF] Sancho | Adaptation d'architectures logicielles collaboratives dans les environnements ubiquitaires. contribution l'interoprabilit par la smantique[END_REF]. The future work includes also ontology to support the context modeling because it makes context description more easier and rich of semantics.

Figure 1 .

 1 Figure 1. Case study: Smart campus

Figure 2 .

 2 Figure 2. The proposed approach

Figure 3 .

 3 Figure 3. Memory consumption evolution within time

Figure 4 .

 4 Figure 4. Link load evolution within time

Figure 5 .

 5 Figure 5. A bursty trafic model

Figure 6 .

 6 Figure 6. Threshold calculation for the resource whose evolution behavior is characterized by a trend

Figure 7 .

 7 Figure 7. Threshold calculation for the resources whose evolution behavior is characterized by a peak

Figure 8 .Figure 9 .

 89 Figure 8. Aggregate application

ACKNOWLEDGMENT

This research is supported by the ITEA2's A2NETS (Autonomic Services in M2M Networks) project 1 .