Search

We propose a notion of deterministic association rules for ordered data. We prove that our proposed rules can be formally justified by a purely logical characterization, namely, a natural notion of empirical Horn approximation for ordered data which involves background Horn conditions; these ensure the consistency of the propositional theory obtained with the ordered context. The whole framework resorts to concept lattice models from of Formal Concept Analysis, but adapted to ordered contexts. We also discuss a general method to mine these rules that can be easily incorporated into any algorithm for mining closed sequences, of which there are already some in the literature., Postprint (published version)

In this paper we revisit the foundations of formal concept analysis for ordered contexts of [4]. From the theoretical point of view, the obtained lattice has proved to be a proper unifying framework for reasoning about different sequential mining tasks: from the discovery of partial orders to the clustering of input sequences. Here we will show how these results on sequences can be naturally extended to the mining of any partial order structure. We empirically validate the approach by testing it on real world data. Our experimental evaluation shows that this lattice-based method is an intuitive tool for analyzing acyclic structures., Postprint (published version)

We propose a general framework to describe formally the problem of capturing the intensity of implication for association rules through statistical metrics. In this framework we present properties that influence the interestingness of a rule, analyze the conditions that lead a measure to perform a perfect prune at a time, and define a final proper order to sort the surviving rules. We will discuss why none of the currently employed measures can capture objective interestingness, and just the combination of some of them, in a multi-step fashion, can be reliable. In contrast, we propose a new simple modification of the Pearson coefficient that will meet all the necessary requirements. We statistically infer the convenient cut-off threshold for this new metric by empirically describing its distribution function through simulation. Final experiments serve to show the ability of our proposal., Postprint (published version)

One basic goal in the analysis of time-series data is to find frequent interesting episodes, i.e, collections of events occurring frequently together in the input sequence. Most widely-known work decide the interestingness of an episode from a fixed user-specified window width or interval, that bounds the subsequent sequential association rules. We present in this paper, a more intuitive definition that allows, in turn, interesting episodes to grow during the mining without any user-specified help. A convenient algorithm to efficiently discover the proposed unbounded episodes is also implemented. Experimental results confirm that our approach results useful and advantageous., Postprint (published version)

The discovery of frequent sequential patterns in an ordered collection of data, such as sequential databases or time-series data, is an important issue in several contexts. In this paper, we employ formal concept analysis to develop the notion of closure for these sequential patterns and to characterize the concept lattice of the ordered contexts. The proposed concept lattice will serve as a model for the patterns extracted in the context of sequential databases by a recent algorithm (CloSpan, cite{Clospan}). Finally, we will show how we can also use our model to derive other kind of structured patterns, like the closed set of episodes in the context of time-series data cite{Toivonen}. So, the convenient transformation of the sequential patterns in the concepts of the lattice will give rise to the most representative set of parallel and serial closed episodes., Postprint (published version)

We describe efficient algorithmic proposals to approach three fundamental problems in data mining: association rules, episodes in sequences, and generalized association rules over hierarchical taxonomies. The association rule discovery problem aims at identifying frequent itemsets in a database and then forming conditional implication rules among them. For this association task, we will introduce a new algorithmic proposal to reduce substantially the number of processed transactions. The resulting algorithm, called Ready-and-Go, is used to discover frequent sets efficiently. Then, for the discovery of patterns in sequences of events in ordered collections of data, we propose to apply the appropriate variant of that algorithm, and additionally we introduce a new framework for the formalization of the concept of interesting episodes. Finally, we adapt our algorithm to the generalization of the frequent sets problem where data comes organized in taxonomic hierarchies, and here additionally we contribute with a new heuristic that, under certain natural conditions, improves the performance., Postprint (published version)