Search

Study of trajectory of care is attractive for predicting medical outcome. Models based on machine learning (ML) techniques have proven their efficiency for sequence prediction modeling compared to other models. Introducing pattern mining techniques contributed to reduce model complexity. In this respect, we explored methods for medical events’ prediction based on the extraction of sets of relevant event sequences of a national hospital discharge database. It is illustrated to predict the risk of in-hospital mortality in acute coronary syndrome (ACS). We mined sequential patterns from the French Hospital Discharge Database. We compared several predictive models using a text string distance to measure the similarity between patients’ patterns of care. We computed combinations of similarity measurements and ML models commonly used. A Support Vector Machine model coupled with edit-based distance appeared as the most effective model. Indeed discrimination ranged from 0.71 to 0.99, together with a good overall accuracy. Thus, sequential patterns mining appear motivating for event prediction in medical settings as described here for ACS.

International audience; Multiple time series are a set of multiple quantitative variables occurring at the same interval. They are present in many domains such as medicine, finance, and manufacturing for analytical purposes. In recent years, streamgraph visualization (evolved from ThemeRiver) has been widely used for representing temporal evolution patterns in multiple time series. However, streamgraph as well as ThemeRiver suffer from scalability problems when dealing with several time series. To solve this problem, multiple time series can be organized into a hierarchical structure where individual time series are grouped hierarchically according to their proximity. In this paper, we present a new streamgraph-based approach to convey the hierarchical structure of multiple time series to facilitate the exploration and comparisons of temporal evolution. Based on a focus+context technique, our method allows time series exploration at different granularities (e. g., from overview to details). To illustrate our approach, two usage examples are presented.

Unilateral Spatial Neglect is a cognitive impairment commonly observed in patients after right hemispheric lesions. A patient with this condition will show a lack of attention or response to visual stimuli presented to the left space.

International audience; Many real world data can be represented by a network with a set of nodes linked each other by multiple relations. Such a rich graph is called multilayer graph. In this demo, we present a tool for Visual Querying of Large Multilayer Graphs that allows to visually draw the query, retrieve result patterns and finally navigate and browse the results considering the original multilayer graph database. Our approach does not only provide a graphical user interface for the graph engine but the query processing is fully integrated.

International audience; Topic labeling aims at providing a sound, possibly multi-words, label that depicts a topic drawn from a topic model. This is of the utmost practical interest in order to quickly grasp a topic informa-tional content-the usual ranked list of words that maximizes a topic presents limitations for this task. In this paper, we introduce three new unsupervised n-gram topic labelers that achieve comparable results than the existing unsupervised topic labelers but following different assumptions. We demonstrate that combining topic labelers-even only two-makes it possible to target a 64% improvement with respect to single topic labeler approaches and therefore opens research in that direction. Finally, we introduce a fourth topic labeler that extracts representative sentences, using Dirichlet smoothing to add contextual information. This sentence-based labeler provides strong surrogate candidates when n-gram topic labelers fall short on providing relevant labels, leading up to 94% topic covering.

International audience; Sentiment analysis allows the semantic evaluation of pieces of text according to the expressed sentiments and opinions. While considerable attention has been given to the polarity (positive, negative) of English words, only few studies were interested in the conveyed emotions (joy, anger, surprise, sadness, etc.) especially in other languages. In this paper, we present the elaboration and the evaluation of a new French lexicon considering both polarity and emotion. The elaboration method is based on the semi-automatic translation and expansion to synonyms of the English NRC Word Emotion Association Lexicon (NRC-EmoLex). First, online translators have been automatically queried in order to create a first version of our new French Expanded Emotion Lexicon (FEEL). Then, a human professional translator manually validated the automatically obtained entries and the associated emotions. She agreed with more than 94 % of the pre-validated entries (those found by a majority of translators) and less than 18 % of the remaining entries (those found by very few translators). This result highlights that online tools can be used to get high quality resources with low cost. Annotating a subset of terms by three different annotators shows that the associated sentiments and emotions are consistent. Finally, extensive experiments have been conducted to compare the final version of FEEL with other existing French lexicons. Various French benchmarks for polarity and emotion classifications have been used in these evaluations. Experiments have shown that FEEL obtains competitive results for polarity, and significantly better results for basic emotions.

International audience; The problem of local community detection in graphs refers to the identification of a community that is specific to a query node and relies on limited information about the network structure. Existing approaches for this problem are defined to work in dynamic network scenarios, however they are not designed to deal with complex real-world networks, in which multiple types of connectivity might be considered. In this work, we fill this gap in the literature by introducing the first framework for local community detection in multilayer networks (ML-LCD). We formalize the ML-LCD optimization problem and provide three definitions of the associated objective function, which correspond to different ways to incorporate within-layer and across-layer topo-logical features. We also exploit our framework to generate multilayer global community structures. We conduct an extensive experimentation using seven real-world multilayer networks, which also includes comparison with state-of-the-art methods for single-layer local community detection and for multilayer global community detection. Results show the significance of our proposed methods in discovering local communities over multiple layers, and also highlight their ability in producing global community structures that are better in modularity than those produced by native global community detection approaches .

International audience; Enhancing the frequency of satellite acquisitions represents a key issue for Earth Observation community nowadays. Repeated observations are crucial for monitoring purposes, particularly when intra-annual process should be taken into account. Time series of images constitute a valuable source of information in these cases. The goal of this paper is to propose a new methodological framework to automatically detect and extract spatiotemporal information from satellite image time series (SITS).Existing methods dealing with such kind of data are usually classification-oriented and cannot provide information about evolutions and temporal behaviors. In this paper we propose a graph-based strategy that combines object-based image analysis (OBIA) with data mining techniques. Image objects computed at each individual timestamp are connected across the time series and generates a set of evolution graphs. Each evolution graph is associated to a particular area within the study site and stores information about its temporal evolution. Such information can be deeply explored at the evolution graph scale or used to compare the graphs and supply a general picture at the study site scale. We validated our framework on two study sites located in the South of France and involving different types of natural, semi-natural and agricultural areas. The results obtained from a Landsat SITS support the quality of the methodological approach and illustrate how the framework can be employed to extract and characterize spatiotemporal dynamics.

International audience; Many real world datasets can be represented by graphs with a set of nodes intercon- nected with each other by multiple relations (e.g., social network, RDF graph, biological data). Such a rich graph, called multigraph, is well suited to represent real world scenarios with com- plex interactions. However, performing subgraph query on multigraphs is still an open issue since, unfortunately, all the existing algorithms for subgraph query matching are not able to ad- equately leverage the multiple relationships that exist between the nodes. Motivated by the lack of approaches for sub-multigraph query and stimulated by the increasing number of datasets that can be modelled as multigraphs, in this paper we propose IMQA (Index based Multigraph Query Answering), a novel algorithm to extract all the embeddings of a sub-multigraph query from a single large multigraph. IMQA is composed of two main phases: Firstly, it implements a novel indexing schema for multiple edges, which will help to efficiently retrieve the vertices of the multigraph that match the query vertices. Secondly, it performs an efficient subgraph search to output the entire set of embeddings for the given query. Extensive experiments conducted on real datasets prove the time efficiency as well as the scalability of IMQA.; De nombreuses données réelles peuvent être représentées par un réseau avec un ensemble de nœuds interconnectés via différentes relations (i.e. les réseaux sociaux, les données biologiques, les graphes RDF). Ce type de graphe, appelé multigraphe, est tout à fait adapté à la représentation de scénarios réels contenant des interactions complexes. La recherche de sousmultigraphe dans des multigraphes est un domaine de recherche ouvert et malheureusement les algorithmes existants pour faire de la recherche de sous-graphe ne sont pas adaptés et ne peuvent pas prendre en compte les différentes relations qui peuvent exister entre les nœuds. Motivés par le manque d’approches existantes et par le nombre croissant d’applications qui peuvent être modélisées via des multigraphes, nous proposons dans cet article IMQA un nouvel algorithme pour extraire tous les sous-multigraphes inclus dans un grand multigraphe. IMQA comporte deux étapes principales. Tout d’abord il implémente une nouvelle structure d’indexation pour les relations multiples qui est utilisée pour rechercher efficacement les sommets du multigraphe qui correspondent aux sommets de la requête. Ensuite, il réalise une recherche efficace de Ingénierie des systèmes d’information – no 3/2016, 53-74 54 ISI. Volume 21 – no 3/2016 l’ensemble des sous-multigraphes correspondant à une requête donnée. Les nombreuses expérimentations menées sur des jeux de données réelles ont montré l’efficacité et le passage à l’échelle de IMQA.

International audience; Many real world datasets can be represented by a network with a set of nodes interconnected with each other by multiple relations. Such a rich graph is called a multigraph. Unfortunately, all the existing algorithms for subgraph query matching are not able to adequately leverage multiple relationships that exist between the nodes. In this paper we propose an efficient indexing schema for querying single large multi-graphs, where the indexing schema aptly captures the neighbourhood structure in the data graph. Our proposal SuMGra couples this novel indexing schema with a subgraph search algorithm to quickly traverse though the solution space to enumerate all the matchings. Extensive experiments conducted on real benchmarks prove the time efficiency as well as the scalability of SuMGra.

The web and social media have been growing exponentially in recent years. We now have access to documents bearing opinions expressed on a broad range of topics. This constitutes a rich resource for natural language processing tasks, particularly for sentiment analysis. Nevertheless, sentiment analysis is usually difficult because expressed sentiments are usually topic-oriented. In this paper, we propose to automatically construct a sentiment dictionary using relevant terms obtained from web pages for a specific domain. This dictionary is initially built by querying the web with a combination of opinion terms, as well as terms of the domain. In order to select only relevant terms we apply two measures \(\textit{AcroDef}_{\textit{MI}3}\) and TrueSkill. Experiments conducted on different domains highlight that our automatic approach performs better for specific cases.

International audience; Recent improvements in positioning technology have led to a much wider availability of massive moving object data. A crucial task is to find the moving objects that travel together. In common, these object sets are called object movement patterns. Due to the emergence of many different kinds of object movement patterns in recent years, different approaches have been proposed to extract them. However, each approach only focuses on mining a specific kind of patterns. It is costly and time consuming to mine and manage various number of patterns, since we have to execute a large number of different pattern mining algorithms. Moreover, we have to execute these algorithms again whenever new data are added to the existing database. To address these issues, we first redefine movement patterns in the itemset context. Second, we propose a unifying approach, named GeT_Move, which uses a frequent closed itemset-based object movement pattern-mining algorithm to mine and manage different patterns. GeT_Move is developed in two versions which are GeT_Move and Incremental GeT_Move. To optimize the efficiency and to free the parameters setting, we further propose a Parameter Free Incremental GeT_Move algorithm. Comprehensive experiments are performed on real and large synthetic datasets to demonstrate the effectiveness and efficiency of our approaches.

International audience; It is very common in todays’ social networks that several discussion threads around similar topics are opened at the same time in different distinct or overlapping communities. Being aware about these different threads may be difficult. Moreover, when new threads are created, it may be useful to provide the user with linked past tweets instead of generating new threads. Information linkage is the pro- cess by which different pieces of information are put together ac- cording to criteria and constraints to form a new information which is richer (i.e. increased) and which can be consumed by an user or automatically by another process.This linkage can: (i) ease the digestion of information, i.e. its perception by users, (ii) enable a better information management from the system perspective, and (iii) allow other third-party applications to draw more benefits from a social content which, in a disparate form, is useless. The problem we are tackling can be formulated as follows: Having a broad set of interactions between users of a social network with disparate messages and connections, how to link these interactions so that they are correlated consistently and significantly for either an end user or an automatic processor to navigate easier in this large content.We propose in this paper to handle the problem of overload in social interactions by grouping messages according to three important dimensions: (i) content (textual and hashtags), (ii) users, and (iii) time difference. This process will also allow to perform well other tasks, such as query recommendation, text understanding (i.e. summarization), and event detection. We evaluated our approach on a Twitter data set and we compared it to other existing approaches and the results are promising and encouraging.

International audience; In this letter, we propose a new active transductive learning (ATL) framework for object-based classification of satellite images. The framework couples graph-based label propagation with active learning (AL) to exploit positive aspects of the two learning settings. The transductive approach considers both labelled and unlabelled image objects to perform its classification as they are all available at training time while the AL strategy smartly guides the construction of the training set employed by the learner. The proposed framework was tested in the context of a land cover classification task using RapidEye optical imagery. A reference land cover map was elaborated over the whole study area in order to get reliable information about the performance of the ATL framework. The experimental evaluation under- lines that, with a reasonable amount of training data, our framework outperforms state of the art classification methods usually employed in the field of remote sensing.

International audience; Sequential pattern mining is the method that has received much attention in sequence data mining research and applications, however, a drawback is that it does not profit from prior knowledge of domains. In our previous work, we proposed a belief-driven method with fuzzy set theory for discovering the unexpected sequences that contradict existing knowledge of data, including occurrence constraints and semantic contradictions. In this paper, we present a new approach that discovers unexpected sequences with determining semantic contradictions by using concept hierarchies associated with the data. We evaluate the effectiveness of our approach with experiments on Web usage analysis.

Recently, the knowledge extraction community takes a closer look at new models where data arrive in timely manner like a fast and continuous flow, i.e. data streams. As only a part of the stream can be stored, mining data streams for sequential patterns and updating previously found frequent patterns need to cope with uncertainty. In this paper, we introduce a new statistical approach which biases the initial support for sequential patterns. This approach holds the advantage to maximize either the precision or the recall, as chosen by the user, and limit the degradation of the other criterion. Moreover, these statistical supports help building statistical borders which are the relevant sets of frequent patterns to use into an incremental mining process. From the statistical standpoint, theoretical results show that the technique is not far from the optimum. Experiments performed on sequential patterns demonstrate the interest of this approach and the potential of such techniques.

International audience; Gradual patterns highlight covariations of attributes of the form " The more/less X, the more/less Y ". Their usefulness in several applications has recently stimulated the synthesis of several algorithms for their automated discovery from large datasets. However, existing techniques require all the interesting data to be in a single database relation or table. This paper extends the notion of gradual pattern to the case in which the co-variations are possibly expressed between attributes of different database relations. The interestingness measure for this class of " relational gradual patterns " is defined on the basis of both Kendall's τ and gradual supports. Moreover, this paper proposes two algorithms, named τ RGP Miner and gRGP Miner, for the discovery of relational gradual rules. Three pruning strategies to reduce the search space are proposed. The efficiency of the algorithms is empirically validated, and the usefulness of relational gradual patterns is proved on some real-world databases.

International audience; With the development of new technologies more and more information is stored in log files. Analyzing such logs can be very useful for the decision maker. One of the probably best known example is the Web log file analysis where lots of efficient tools have been proposed to extract the top-k accessed pages, the best users or even the patterns describing the behaviors of users on a Web site. These tools take advantages of the well-formed structures of the data. Unfortunately, logs files from the industrial world have very heterogeneous complex structures (e.g., tables, lists, data blocks). For experts, analyzing logs to find messages helping to better understand causes of a failure, if a problem have already occurred in the past or even knowing the main consequences of a failure is a hard, tedious, time-consuming and error-prone task. There is thus a need for new tools helping the experts to easily recognize the appropriate part in logs. Passage retrieval methods have proved to be very useful for extracting relevant parts in documents. In this paper we propose a new approach for automatically split logs files into relevant segments based on their logical units. We characterize the complex logical units found in logs according to their syntactic characteristics. We also introduce the notion of generalized vs-grams which is used to automatically extract the syntactic characteristics of special structures found in log files. Conducted experiments are performed on real datasets from the industrial world to demonstrate the efficiency of our proposal on the recognition of complex logical units.

International audience; The main use of satellite imagery concerns the process of the spectral and spatial dimensions of the data. However, to extract useful information, the temporal dimension also has to be accounted for which increases the complexity of the problem. For this reason, there is a need for suitable data mining techniques for this source of data. In this work, we developed a data mining methodology to extract multidimensional sequential patterns to characterize temporal behaviors. We then used the extracted multidimensional sequences to build a classifier, and show how the patterns help to distinguish between the classes. We evaluated our technique using a real-world dataset containing information about land use in Mali (West Africa) to automatically recognize if an area is cultivated or not.

International audience; Mining frequent patterns on streaming data is a new challenging problem for the data mining community since data arrives sequentially in the form of continuous rapid streams. In this paper we propose a new approach for mining itemsets. Our approach has the following advantages: an efficient representation of items and a novel data structure to maintain frequent patterns coupled with a fast pruning strategy. At any time, users can issue requests for frequent itemsets over an arbitrary time interval. Furthermore our approach produces an approximate answer with an assurance that it will not bypass user-defined frequency and temporal thresholds. Finally the proposed method is analyzed by a series of experiments on different datasets.

International audience; In recent years the emergence of new real-world applications such as network traffic monitoring, intrusion detection systems, sensor network data analysis, click stream mining and dynamic tracing of financial transactions, calls for studying a new kind of model. Named data stream, this model is in fact a continuous and potentially infinite flow of information as opposed to finite and statically stored data sets. We study the problem of sequential pattern mining in data streams. This problem has been extensively studied for the conventional case of disk resident data sets. In the case of data streams, this problem becomes more challenging as the volume of data is usually too huge to be stored on permanent devices, main memory or to be scanned thoroughly more than once. In this case, it may be acceptable to generate approximable solutions for our mining problem. In this paper we introduce a new approach based on biased reservoir sampling to achieve a more efficient mining of sequential patterns. Furthermore, we theoretically prove that our biased reservoir size is always bounded whatever the size of the stream is. This property often allows us to keep the entire relevant reservoir in main memory. We also show a simple algorithm to build the biased reservoir for the special case of sequential pattern mining. Experimental evaluation supports the claim that sequential pattern mining based on biased reservoir sampling needs small memory requirements. Besides, we also propose an adapted approach to handle the case of mining sequential patterns in a sliding window model. The experiment show that the results are accurate.

International audience; Economic development based on industrialization, intensive agriculture expansion and population growth places greater pressure on water resources through increased water abstraction and water quality degradation [40]. River pollution is now a visible issue, with emblematic ecological disasters following industrial accidents such as the pollution of the Rhine river in 1986 [31]. River water quality is a pivotal public health and environmental issue that has prompted governments to plan initiatives for preserving or restoring aquatic ecosystems and water resources [56]. Water managers require operational tools to help interpret the complex range of information available on river water quality functioning. Tools based on statistical approaches often fail to resolve some tasks due to the sparse nature of the data. Here we describe HydroQual, a tool to facilitate visual analysis of river water quality. This tool combines spatiotem-poral data mining and visualization techniques to perform tasks defined by water experts. We illustrate the approach with a case study that illustrates how the tool helps experts analyze water quality. We also perform a qualitative evaluation with these experts.

International audience; More and more data come with contextual information describing the circumstances of their acquisition. While the frequent pattern mining literature offers a lot of approaches to handle and extract interesting patterns in data, little effort has been dedicated to relevantly handling such contextual information during the mining process. In this paper we propose a generic formulation of the contextual frequent pattern mining problem and provide the CFPM algorithm to mine frequent patterns that are representative of a context. This approach is generic w.r.t. the pattern language (e.g., itemsets, sequential patterns, subgraphs, etc.) and therefore is applicable in a wide variety of use cases. The CFPM method is experimented on real datasets with three different pattern languages to assess its performances and genericity.

National audience; Detecting change in evolving data streams is a central issue for accurate adaptive learning. In real world applications, data streams have categorical features, and changes induced in the data distribution of these categorical features have not been considered extensively so far. Previous work on change detection focused on detecting changes in the accuracy of the learners, but without considering changes in the data distribution. To cope with these issues, we propose a new unsupervised change detection method, called CDCStream (Change Detection in Categorical Data Streams), well suited for categorical data streams. The proposed method is able to detect changes in a batch incremental scenario. It is based on the two following characteristics: (i) a summarization strategy is proposed to compress the actual batch by extracting a descriptive summary and (ii) a new segmentation algorithm is proposed to highlight changes and issue warnings for a data stream. To evaluate our proposal we employ it in a learning task over real world data and we compare its results with state of the art methods. We also report qualitative evaluation in order to show the behavior of CDCStream.; Pour mieux analyser et extraire de la connaissance de flots de données, des approches spécifiques ont été proposées ces dernières années. L’un des challenges auquel elles doivent faire face est la détection de changement dans les données. Alors que de plus en plus de données qualitatives sont générées, peu de travaux de recherche se sont intéressés à la détection de changement dans ce contexte et les travaux existants se sont principalement focalisés sur la qualité d’un modèle appris plutôt qu’au réel changement dans les données. Dans cet article nous proposons une nouvelle méthode de détection de changement non supervisée, appelée CDCStream (Change Detection in Categorical Data Streams), adaptée aux flux de données qualitatives.

International audience; Online health fora are increasingly visited by patients to get help and information related to their health. However, these fora are not limited to patients: a significant number of health professionals actively participate in many discussions. As experts their posted information are very important since, they are able to well explain the problems, the symptoms, correct false affirmations and give useful advices, etc. For someone interested in trusty medical information , obtaining only these kinds of posts can be very useful and informative. Unfortunately, extracting such knowledge needs to navigate over the fora in order to evaluate the information. Navigation and selection are time consuming, tedious, difficult and error-prone activities when done manually. It is thus important to propose a new method for automatically categorize information proposed both by non-experts as well as by professionals in online health fora. In this paper, we propose to use a supervised approach to evaluate what are the most representative components of a post considering vocabularies, uncertainty markers, emotions, misspellings and interrogative forms to perform efficiently this categorization. Experiments have been conducted on two real fora and shown that our approach is efficient for extracting posts done by professionals.

With the growing popularity of the World Wide Web (Web), large volumes of data such as user address or URL requested are gathered automatically by Web servers and collected in access log files. Discovering relationships and global patterns that exist in such files can provide significant and useful information for performance enhancement, restructuring a Web site for increased effectiveness, and customer targeting in electronic commerce. In this paper, we propose an integrated system (WebTool) for applying data mining techniques such as association rules or sequential patterns on access log files. Once interesting patterns are discovered, we illustrate how they can be used to customize the server hypertext organization dynamically.

While significant work in data mining has been dedicated to the detection of single outliers in the data, less research has approached the problem of isolating a group of outliers, i.e. rare events representing micro-clusters of less – or significantly less – than 1% of the whole dataset. This research issue is critical for example in medical applications. The problem is difficult to handle as it lies at the frontier between outlier detection and clustering and distinguishes by a clear challenge to avoid missing true positives. We address this challenge and propose a novel two-stage framework, based on a backward approach, to isolate abnormal groups of events in large datasets. The key of our backward approach is to first identify the core of the dense regions and then gradually augments them based on a density-driven condition. The framework outputs a small subset of the dataset containing both rare events and outliers. We tested our framework on a biomedical application to find micro-clusters of pathological cells. The comparison against two common clustering (DBSCAN) and outlier detection (LOF) algorithms show that our approach is a very efficient alternative to the detection of rare events – generally a recall of 100% and a higher precision, positively correlated wih the size of the rare event – while also providing a \(\mathcal{O}(N)\) solution to the existing algorithms dominated by a \(\mathcal{O}(N^2)\) complexity.

International audience; Considering relational tables as the object of analysis, methods to summarize them can help the analyst to have a starting point to explore the data. Typically, table summarization aims at producing an informative data summary through the use of metadata supplied by attribute taxonomies. Nevertheless, such a hierarchical knowledge is not always available or may even be inadequate when existing. To overcome these limitations, we propose a new framework, named cTabSum, to automatically generate attribute value taxonomies and directly perform table summarization based on its own content. Our innovative approach considers a relational table as input and proceeds in a two-step way. First, a taxonomy for each attribute is extracted. Second, a new table summarization algorithm exploits the automatic generated taxonomies. An information theory measure is used to guide the summarization process. Associated with the new algorithm we also develop a prototype. Interestingly, our prototype incorporates some additional features to help the user familiarizing with the data: (i) the resulting summarized table produced by cTabSum can be used as recommended starting point to browse the data; (ii) some very easy-to-understand charts allow to visualize how taxonomies have been so built; (iii) finally, standard OLAP operators, i.e. drill-down and roll-up, have been implemented to easily navigate within the data set. In addition we also supply an objective evaluation of our table summarization strategy over real data.

International audience; Mining trajectories (or moving object patterns) from spatio-temporal data is an active research field. Most of the researches are devoted to extract trajectories that differ in their structure and characteristic in order to capture dif- ferent object behaviors. The first issue is constituted from the fact that all these methods extract thousand of patterns resulting in a huge amount of redundant knowledge that poses limit in their usefulness. The second issue is supplied from the nature of spatio-temporal database from which different types of patterns could be extracted. This means that using only a single type of patterns is not sufficient to supply an insightful picture of the whole database. Motivating by these issues, we develop a Minimum Description Length (MDL)-based approach that is able to compress spatio-temporal data combin- ing different kinds of moving object patterns. The proposed method results in a rank of the patterns involved in the summarization of the dataset. In order to validate the quality of our approach, we conduct an empirical study on real data to compare the proposed algorithms in terms of effectiveness, running time and compressibility.

International audience; Traditional sequential patterns do not take into account contextual infor- mation associated with sequential data. For instance, when studying purchases of customers in a shop, a sequential pattern could be "frequently, customers buy prod- ucts A and B at the same time, and then buy product C". Such a pattern does not con- sider the age, the gender or the socio-professional category of customers. However, by taking into account contextual information, a decision expert can adapt his/her strategy according to the type of customers. In this paper, we focus on the analysis of a given context (e.g., a category of customers) by extracting context-dependent sequential patterns within this context. For instance, given the context correspond- ing to young customers, we propose to mine patterns of the form "buying products A and B then product C is a general behavior in this population" or "buying products B and D is frequent for young customers only". We formally define such context- dependent sequential patterns and highlight relevant properties that lead to an effi- cient extraction algorithm. We conduct our experimental evaluation on real-world data and demonstrate performance issues.

International audience; Recent improvements in positioning technology have led to a much wider availability of massive moving object data. One of the objectives of spatio-temporal data mining is to analyze such datasets to exploit moving objects that travel together. Naturally, the moving objects in a cluster may actually diverge temporarily and congregate at certain timestamps. Thus, there are time gaps among moving object clusters. Existing approaches either put a strong constraint (i.e. no time gap) or completely relaxed (i.e. whatever the time gaps) in dealing with the gaps may result in the loss of interesting patterns or the extraction of huge amount of extraneous patterns. Thus it is difficult for analysts to understand the object movement behavior. Motivated by this issue, we propose the concept of fuzzy swarm which softens the time gap constraint. The goal of our paper is to find all non-redundant fuzzy swarms, namely fuzzy closed swarm. As a contribution, we propose fCS-Miner al- gorithm which enables us to efficiently extract all the fuzzy closed swarms. Con- ducted experiments on real and large synthetic datasets demonstrate the effectiveness, parameter sensitiveness and efficiency of our methods.

International audience; One of the objectives of spatio-temporal data mining is to analyze moving object datasets to exploit interesting pat- terns. Traditionally, existing methods only focus on an unchanged group of moving objects during a time period. Thus, they cannot capture object moving trends which can be very useful for better understanding the natural moving behavior in various real world applications. In this paper, we present a novel concept of "time relaxed gradual trajectory pattern", denoted real-Gpattern, which captures the object movement tendency. Additionally, we also propose an efficient algorithm, called ClusterGrowth, designed to extract the complete set of all interesting maximal real-Gpatterns. Conducted experiments on real and large synthetic datasets demonstrate the effectiveness, parameter sensitiveness and efficiency of our methods.

Sequential pattern mining is aimed at extracting correlations among temporal data. Many different methods were proposed to either enumerate sequences of set valued data (i.e., itemsets) or sequences containing multidimensional items. However, in real-world scenarios, data sequences are described as events of both multidimensional items and set valued information. These rich heterogeneous descriptions cannot be exploited by traditional approaches. For example, in healthcare domain, hospitalizations are defined as sequences of multi-dimensional attributes (e.g. Hospital or Diagnosis) associated with two sets, set of medical procedures (e.g. $ \lbrace $ Radiography, Appendectomy $\rbrace$) and set of medical drugs (e.g. $\lbrace $ Aspirin, Paracetamol $\rbrace$) . In this paper we propose a new approach called MMISP (Mining Multidimensional Itemset Sequential Patterns) to extract patterns from a complex sequences including both dimensional items and itemsets. The novelties of the proposal lies in: (i) the way in which the data can be efficiently compressed; (ii) the ability to reuse and adopt sequential pattern mining algorithms and (iii) the extraction of new kind of patterns. We introduce as a case-study, experimented on real data aggregated from a regional healthcare system and we point out the usefulness of the extracted patterns. Additional experiments on synthetic data highlights the efficiency and scalability of our approach.

International audience; In this paper, we study the mining of gradual patterns in the presence of numeric attributes belonging to data sets. The field of gradual pattern mining have been recently proposed to extract covariations of attributes, such as: {the higher the age, the higher the salary}. This gradual pattern denoted as {size≥salary≥} means that the age of people increases together with their salary. Actually, the analysis of such correlations is very memory consuming. When managing huge databases, issue is very challenging. In this context, we focus on the use of fuzzy orderings to take this into account and we propose techniques in order to optimize the computation. These techniques are based on a matrix representation of fuzzy concordance degrees C(i, j) and the Yale Sparse Matrix Format.

Recent improvements in positioning technology has led to a much wider availability of massive moving object data. A crucial task is to find the moving objects that travel together. Usually, these object sets are called spatio-temporal patterns. Due to the emergence of many different kinds of spatio-temporal patterns in recent years, different approaches have been proposed to extract them. However, each approach only focuses on mining a specific kind of pattern. In addition to being a painstaking task due to the large number of algorithms used to mine and manage patterns, it is also time consuming. Moreover, we have to execute these algorithms again whenever new data are added to the existing database. To address these issues, we first redefine spatio-temporal patterns in the itemset context. Secondly, we propose a unifying approach, named GeT_Move, which uses a frequent closed itemset-based spatio-temporal pattern-mining algorithm to mine and manage different spatio-temporal patterns. GeT_Move is implemented in two versions which are GeT_Move and Incremental GeT_Move. To optimize the efficiency and to free the parameters setting, we also propose a Parameter Free Incremental GeT_Move algorithm. Comprehensive experiments are performed on real datasets as well as large synthetic datasets to demonstrate the effectiveness and efficiency of our approaches., Comment: 17 pages, 24 figures, submitted to KDD, TKDD

International audience; Recent improvements in positioning technology has led to a much wider availability of massive moving object data. A crucial task is to find the moving objects that travel together. Usually, these object sets are called spatio-temporal patterns. Analyzing such data has been applied in many real world applications, e.g., in ecological study, vehi- cle control, mobile communication management, etc. However, few data mining tools are available for flexible and scalable analysis of massive scale moving object data. The main reason is that there is no a uni- fying approach to manage the patterns while many different kinds of spatio-temporal patterns have been proposed in recent years. Each ap- proach only focuses on mining a specific kind of pattern. Our system, GeT Move, is designed to extract and manage different spatio-temporal patterns concurrently. A user-friendly interface is provided to facilitate interactive exploration of mining results. Since GeT Move is tested on many kinds of real data sets, it will benefit users to carry out versatile analysis on these kinds of data by exhibiting different kinds of patterns at the same time.

International audience; In many domains (e.g., data mining, data management, data warehouse), a hierarchical organization of attribute values can help the data analysis process. Nevertheless, such hi- erarchical knowledge does not always available or even may be inadequate or useless when exists. Starting from this consideration, in this paper we tackle the problem of the automatic definition of data-driven taxonomies.To do this we combine techniques coming from information theory and clustering to obtain a structured representation of the at- tribute values: the Contextual Attribute-Value Taxonomy (CAVT). The two main advantages of our method are to be fully unsupervised (i.e., without any knowledge provided by an expert) and parameter-free. We experiments the bene- fit of use CAVTs in the two following tasks: (i) the mul- tilevel multidimensional sequential pattern mining problem in which hierarchies are involved to exploit abstraction over the data, (ii) the table summarization problem, in which the hierarchies are used to aggregate the data to supply a sketch of the original information to the user. To validate our approach we use real world datasets in which we obtain appreciable results regarding both quantitative and qualitative evaluation.

International audience; Data warehouses are nowadays extensively used to perform analyses on huge volume of data. This success is partly due to the capacity of considering data at several granularity levels thanks to the use of hierarchies. However, in previous work, we showed that the experts' knowledge were not much considered in the generalization process. To overcome this drawback, we introduced a new category of hierarchies, namely the contextual hierarchies. Unfortunately, in contrast to the complexity of expert knowledge that should be considered, the knowledge definition process was too rigid. In this paper, we extend these hierarchies and their related techniques to drastically increase their flexibility and expressivity. To this purpose, we adopt a fuzzy-based methodology which allows to express expert knowledge in a very convenient way. Experiment results obtained on synthetic datasets show that the contextual generalization process is very fast and can thus be used in practice.

Mining gradual patterns plays a crucial role in many real world applications where very large and complex numerical data must be handled, e.g., biological databases, survey databases, data streams or sensor readings. Gradual rules highlight complex order correlations of the form “The more/less X, then the more/less Y”. Such rules have been studied for a long time and recently scalable algorithm has been proposed to address the issue. However, mining gradual patterns remains challenging in mobile object applications. In the other hand, mining frequent moving objects patterns is also very useful in many applications such as traffic management, mobile commerce, animals tracking. Those two techniques are very efficient to discover interesting rules and patterns; however, in some aspect, each individual technique could not help us to fully understand and discover interesting items and patterns. In this paper, we present a novel concept in that gradual pattern and spatio-temporal pattern are combined together to extract gradual-spatio-temporal rules. We also propose a novel algorithm, named GSTD, to extract such rules. Conducted experiments on a real dataset show that new kinds of patterns can be extracted.

Research highlights? Data representation in train preventive maintenance data. ? Sequential pattern mining in sensor monitoring data. ? Anomaly detection based on sequential patterns. ? Considering contextual information for precise description of train monitoring data. Today, many industrial companies must face problems raised by maintenance. In particular, the anomaly detection problem is probably one of the most challenging. In this paper we focus on the railway maintenance task and propose to automatically detect anomalies in order to predict in advance potential failures. We first address the problem of characterizing normal behavior. In order to extract interesting patterns, we have developed a method to take into account the contextual criteria associated to railway data (itinerary, weather conditions, etc.). We then measure the compliance of new data, according to extracted knowledge, and provide information about the seriousness and the exact localization of a detected anomaly.

International audience; The system that monitors the events occurring in a computer system or a network and analyzes the events for sign of intrusions is known as Intrusion Detection System (IDS). The IDS need to be accurate, adaptive, and extensible. Although many established techniques and commercial products exist, their effectiveness leaves room for improvement. A great deal of research has been carried out on intrusion detec- tion in a distributed environment to palliate the drawbacks of centralized approaches. However, distributed IDS suffer from a number of drawbacks e.g., high rates of false positives, low efficiency, etc. In this paper, we propose a distributed IDS that integrates the desirable features provided by the multi-agent methodology with the high accuracy of data mining techniques. The proposed system relies on a set of intelligent agents that collect and analyze the network connections, and data mining techniques are shown to be useful to detect the intrusions. Carried out experiments showed superior performance of our distributed IDS compared to the centralized one.

International audience; Web usage mining has been much concentrated on the discovery of relevant user behaviours from Web access record data. In this paper, we present WebUser, an approach to discover unexpected usage in Web access log. We present a belief-driven method for extracting unexpected Web usage sequences, where the belief system consists of a temporal relation and semantics constrained sequence rules acquired with respect to prior knowledge. Our experiments show the effectiveness and usefulness of the proposed approach. Further, discovered rules of unexpected Web usage can be used for Web content personalisation and recommendation, site structure optimisation, and critical event prediction.

International audience; Gradual patterns refer to frequent patterns describing correlations between variables which evolution is linked. For instance, the gradual pattern the older, the higher means that the age and the salary increase/decrease simultaneously between two persons. This co-evolution can be found either as increasing together or evolving oppositely (e.g., the more cars, the less bus tickets). Several approaches were proposed to mine such patterns. These approaches differ depending on the way they count how frequent a pattern is, or depending on their efficiency both for memory and time consumption. The approaches can also differ depending on the way the attributes are treated, i.e. if they are considered as monotonically growing within the range of values or if they are considered as a fuzzy partition. For instance, the pattern the closer the age of an employee to 46, the higher his/her income is called to be a fuzzy gradual pattern. The challenge is then to retrieve the fuzzy sets (e.g. almost 46) that allow to mine the most relevant fuzzy gradual patterns. In this paper we focus on how genetic programming can be used in this context.

International audience; In mining gradual patterns the idea is to express co-variations of attributes, taking the direction of change of attribute values into account. These patterns are such as {the more A, the more B}, {the more A, the more B, the less C} or {the higher the speed, the higher the danger }. These patterns are denoted as {A≥B≥ }, { A≥B≥C≤}or { speed≥danger≥} respectively. Such patterns hold if the variation constraints simultaneously hold on the attributes. However, it is often hardly possible to compare attribute values, either because the values are taken from noisy data, or because it is difficult to consider that a small difference between two values is meaningful. In this context, we focus on the use of fuzzy orderings to take this into account abstract environment.

International audience; Traditional sequential patterns do not take into account additional contextual information since patterns extracted from data are usually general. By considering the fact that a pattern is associated with one specific context the decision expert can then adapt his strategy considering the type of customers. In this paper we propose to mine more precise patterns of the form "young users buy products A and B then product C, while old users do not follow this same behavior". By highlighting relevant properties of such contexts, we show how contextual sequential patterns can be extracted by mining the database in a concise manner. We conduct our experimental evaluation on real-world data and demonstrate performance issues.

International audience; Gradual Patterns allow to express frequent patterns like "the older an employee, the higher his/her income". After having been extensively used for fuzzy command (e.g., "the closer the wall, the harder the break"), they are currently grasping the attention of the data mining community, where the focus is put on the scalability of the methods when addressing very large databases (e.g. biology). However, it is often the case that the information is not contained at the upper and lower boundaries (min/max), but rather hidden in-between. For instance, the most interesting rule could be "the closer the age of an employee to 46, the higher his/her income". In this paper, we introduce several methods for automatically defining fuzzy modalities and we compare the results obtained when considering the various solutions.

Sales on the Internet have increased significantly during the last decade, and so, it is crucial for companies to retain customers on their web site. Among all strategies towards this goal, providing customers with a flexible search tool is a crucial issue. In this paper, we propose an approach, called TIGER, for handling such flexibility automatically. More precisely, if the search criteria of a given query to a relational table or a Web catalog are too restrictive, our approach computes a new query combining extensions of the criteria. This new query maximizes the quality of the answer, while being as close as possible to the original query. Experiments show that our approach improves the quality of queries, in the sense explained just above.

International audience; Gradual rules allow users to be provided with rules describing the ordering correlations among attributes. Such a rule is for instance given by the higher the salary and the lower the number of cars, the higher the number of tourist travels. Previously intensively used in fuzzy command systems, these rules were manually provided to the system. More recently, they have received attention from the data mining community and methods have been defined to automatically extract and maintain gradual rules from numerical databases. However, no method has been shown to be able to handle data streams, as no method is scalable enough to manage the high rate which stream data arrive at. In this paper, we thus propose an original approach to mine data streams for gradual rules. Our method is based on B-Trees and OWA (Ordered Weighted Aggregation) operator in order to speed up the process. B-Trees are used to store already-known gradual rules in order to maintain the knowledge over time, while OWA operators provide a fast way to discard non relevant data.

International audience; Hierarchies are crucial for analysis in data warehouses. But they can hardly be defined on measure attributes. In this paper, we tackle this issue and we show that measure generalizations often depend on a context. For instance, a given blood pressure can be either low, normal or high regarding not only the collected measure but also characteristics of the patient such as the age. The contribution of this paper is threefold. (1) Thanks to an external database storing the expert knowledge, we propose an effective solution for considering these hierarchies. (2) In order to efficiently manage this knowledge, a Rich Internet Application is developed. (3) Finally, in order to provide a flexible analysis, query rewriting module is proposed. Thus, it is possible to answer queries such as: "Who had a low blood pressure last night?''

International audience; The question answering systems are considered the next generation of search engines. This paper focuses on the first step of this process, which is to search for relevant passages containing answers. Passage Retrieval, can be difficult because of the complexity of data, log files in our case. Our contribution is based on the enrichment of queries by using a learning method and a novel term weighting function. This original term weighting function, used within the enrichment process, aims to assign a weight to terms according to their relatedness to the context of answers. Experiments conducted on real data show that our protocol of primitive query enrichment make it possible to retrieve relevant passages.