Data uncertainty is inherent in emerging applications such as location-based services, sensor monitoring systems, and data integration. To handle a large amount of imprecise information, uncertain databases have been recently developed. In this paper, we study how to efficiently discover frequent itemsets from large uncertain databases, interpreted under the Possible World Semantics. This is technically challenging, since an uncertain database induces an exponential number of possible worlds. To tackle this problem, we propose a novel methods to capture the itemset mining process as a probability distribution function taking two models into account: the Poisson distribution and the normal distribution. These model-based approaches extract frequent itemsets with a high degree of accuracy and support large databases. We apply our techniques to improve the performance of the algorithms for (1) finding itemsets whose frequentness probabilities are larger than some threshold and (2) mining itemsets with the $$k$$ highest frequentness probabilities. Our approaches support both tuple and attribute uncertainty models, which are commonly used to represent uncertain databases. Extensive evaluation on real and synthetic datasets shows that our methods are highly accurate and four orders of magnitudes faster than previous approaches. In further theoretical and experimental studies, we give an intuition which model-based approach fits best to different types of data sets.

Probabilistic frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied to standard "certain" transaction databases. The consideration of existential uncertainty of item(sets), indicating the probability that an item(set) occurs in a transaction, makes traditional techniques inapplicable. In this paper, we introduce new probabilistic formulations of frequent itemsets based on possible world semantics. In this probabilistic context, an itemset X is called frequent if the probability that X occurs in at least minSup transactions is above a given threshold τ. To the best of our knowledge, this is the first approach addressing this problem under possible worlds semantics. In consideration of the probabilistic formulations, we present a framework which is able to solve the Probabilistic Frequent Itemset Mining (PFIM) problem efficiently. An extensive experimental evaluation investigates the impact of our proposed techniques and shows that our approach is orders of magnitude faster than straight-forward approaches.

Mining sequential movement patterns describing group behaviour in potentially streaming spatio-temporal data sets is a challenging problem. Movements are typically noisy and often overlap each other. This makes a set of simple patterns difficult to interpret and sequences difficult to mine. Furthermore, group behaviour is complex. Objects in a group may behave similarly for a period of time (an interesting pattern sequence), then split up – either spatially, temporally or both; making a series of uninteresting movements before rejoining again. This behaviour must be captured in a single pattern for that group, rather than a number of unconnected pattern sequences. Secondly, it often occurs that individual objects only move along segments of a path, perhaps between intersections in a road or highway. However, the entire path is interesting when all such behaviours are taken together. Therefore, a pattern describing such behaviour should be found, rather than just a number of short sequences. This paper solves these challenges, among others, by mining sequences of Spatio-Temporal Association Rules. Theoretical results are exploited in order to develop an efficient algorithm, which is demonstrated to have linear run time in the number of interesting sequences discovered. A lattice for drill down and roll up exploratory analysis of the sequence patterns is proposed. Finally, verifiable and interesting patterns possessing the above characteristics are found in a real world animal tracking data set.

Finding interactions between variables is a fundamental concept in Data Mining. In this work, correlations between variables are considered using Pearson's product moment correlation coefficient. Of interest are complex, complete, and maximal sub-graphs which describe the correlation structure between variables. This paper considers both positive and negative correlations – complex interactions. It is proved that under a constraint on the minimum level of correlation desired, there are useful guarantees on the structure of the correlations. In particular, the sign of the correlation between variables can be mapped to the variables themselves (i.e. to the vertices). This means that the complete complex sub-graphs can be represented as a complex set, where each element – a variable with a positive or a negative sign – is highly positively correlated with every other. This makes the interaction much easier to understand. It is also exploited to develop an algorithm that runs in the same time as if complex interactions were not considered, resulting in significantly improved scalability. Mining maximal sets of variables characterized by the lack of correlations is also briefly considered. The approach is useful for examining complex correlation structures, as well as mining a representative subset of the entire data set. The latter idea is extended to the problem of feature subset selection in a way that gives guarantees on the minimum correlation required for features to be considered interchangeable (redundant), while guaranteeing that the selected features are not correlated with each other. Experiments show the approach performs well.

The application of association rule mining to classification has led to a new family of classifiers which are often referred to as "associative classifiers (ACs)". An advantage of ACs is that they are rule-based and thus lend themselves to an easier interpretation. Rule-based classifiers can play a very important role in applications such as medical diagnosis and fraud detection where "imbalanced data sets" are the norm and not the exception. The focus of this paper is to extend and modify ACs for classification on imbalanced data sets using only statistical techniques. We combine the use of statistically significant rules with a new measure, the Class Correlation Ratio (CCR), to build an AC which we call SPARCCC. Experiments show that in terms of classification quality, SPARCCC performs comparably on balanced datasets and outperforms other AC techniques on imbalanced data sets. It also has a significantly smaller rule base and is much more computationally efficient.

In our geometric view, an itemset is a vector (itemvector) in the space of transactions. Linear and potentially non-linear transformations can be applied to the itemvectors before mining patterns. Aggregation functions and interestingness measures can be applied to the transformed vectors and pushed inside the mining process. We show that interesting itemset mining can be carried out by instantiating four abstract functions: a transformation (g), an algebraic aggregation operator (o) and measures (f and F). For frequent itemset mining (FIM), g and F are identity transformations, o is intersection and f is the cardinality. Based on this geometric view we present a novel algorithm that uses space linear in the number of 1-itemsets to mine all interesting itemsets in a single pass over the data, with no candidate generation. It scales (roughly) linearly in running time with the number of interesting item- sets. FIM experiments show that it outperforms FP-growth on realistic datasets above a small support threshold (0.29% and 1.2% in our experiments).