In this paper we propose CCCS, a new algorithm for classification based on association rule mining. The key innovation in CCCS is the use of a new measure, the "Complement Class Support (CCS)" whose application results in rules which are guaranteed to be positively correlated. Furthermore, the anti-monotonic property that CCS possesses has very different semantics vis-a-vis the traditional support measure. In particular, "good" rules have a low CCS value. This makes CCS an ideal measure to use in conjunction with a top-down algorithm. Finally, the nature of CCS allows the pruning of rules without the setting of any threshold parameter! To the best of our knowledge this is the first threshold-free algorithm in association rule mining for classification.

The mining of outliers (or anomaly detection) in large databases continues to remain an active area of research with many potential applications. Over the last several years many novel methods have been proposed to efficiently and accurately mine for outliers. In this paper we propose a unique approach to mine for sequential outliers using Probabilistic Suffix Trees (PST). The key insight that underpins our work is that we can distinguish outliers from non-outliers by only examining the nodes close to the root of the PST. Thus, if the goal is to just mine outliers, then we can drastically reduce the size of the PST and reduce its construction and query time. In our experiments, we show that on a real data set consisting of protein sequences, by retaining less than 5% of the original PST we can retrieve all the outliers that were reported by the full-sized PST. We also carry out a detailed comparison between two measures of sequence similarity: the normalized probability and the odds and show that while the current research literature in PST favours the odds, for outlier detection it is normalized probability which gives far superior results. We provide an information theoretic argument based on entropy to explain the success of the normalized probability measure. Finally, we describe a more efficient implementation of the PST algorithm, which dramatically reduces its construction time compared to the implementation of Bejerano [3].

We propose an efficient algorithm to mine positive and negative patterns in large spatial databases. The algorithm is based on exploiting a complementarity property for a certain support-like measure. This property guarantees that if a positive k-pattern is “frequent” then O(k) related negative patterns will be infrequent. For the traditional support measure this complementarity property holds true only when the minimum support is over fifty percent. We also confirm the correctness of our approach using Ripley's K-Function, a standard tool in spatial statistics for analyzing point patterns. Extensive experimentation on data extracted from the Sloan Digital Sky Survey (SDSS) database demonstrates the utility of our approach to large scale data exploration.