In this paper, we give a novel on-line ϵ-approximation algorithm for mining the set of strongly closed itemsets in a transaction stream, and also study its acceleration technique with several pruning methods such as look-ahead success detection for strongly closed itemsets. We also show some experimental results for evaluating the proposed algorithms.

Essentially, any negative association rules are constructed over infrequent underling itemsets, thus the number of valid negative rules is always quite huge, and effective extraction of negative rules is quite difficult. In this paper, we study an efficient mining algorithm of negative rules over minimal generators, where a set of negative rules can be effectively compressed by using minimal generators, especially for dense data. We first propose new two concepts, so called consistency and non-redundancy, for a set consisting of both positive and negative association rules. Next, we prove some a fundamental but important property for minimal generators, which enables us to construct a suffix tree over minimal generators. We show a new top-down algorithm for mining a consistent and non-redundant set of negative association rules. The top-down search uses the suffix tree in order to restrict some negative rules to be right-minimal, which also suppress the burst of negative rules. Finally, we show preliminary results of experimental evaluation for the proposed negative rule mining method.

Abstract Here, we present a novel algorithm for frequent itemset mining in streaming data (FIM-SD). For the past decade, various FIM-SD methods in one-pass approximation settings that allow to approximate the support of each itemset have been proposed. They can be categorized into two approximation types: parameter-constrained (PC) mining and resource-constrained (RC) mining. PC methods control the maximum error that can be included in the approximate support based on a pre-defined parameter. In contrast, RC methods limit the maximum memory consumption based on resource constraints. However, the existing PC methods can exponentially increase the memory consumption, while the existing RC methods can rapidly increase the maximum error. In this study, we address this problem by introducing a hybrid approach of PC-RC approximations, called PARASOL. For any streaming data, PARASOL ensures to provide a condensed representation, called a Δ-covered set, which is regarded as an extension of the closedness compression; when Δ = 0, the solution corresponds to the ordinary closed itemsets. PARASOL searches for such approximate closed itemsets that can restore the frequent itemsets and their supports while the maximum error is bounded by an integer, Δ. Then, we empirically demonstrate that the proposed algorithm significantly outperforms the state-of-the-art PC and RC methods for FIM-SD.

In this paper, we study acceleration methods for on-line stream mining of all frequent closed itemsets under a minimal-size restriction. The algorithm LC-K-CloStream [3] can perform an 6-approximation on-line mining based on incremental intersection of transactions. We first integrate LC-K-CloStream with an extended FP-tree with skipping in order to effectively compress a huge number of mined closed itemsets. Next, we introduce novel pruning methods for rejecting a hopeless intersection computation by using look-ahead maximal-size estimation. We show, through experimental evaluations, that the proposed methods have a great performance for mining a large set of closed itemsets in dense data sets.

We propose a new on-line e-approximation algorithm for mining closed itemsets from a transactional data stream, which is also based on the incremental/cumulative intersection principle. The proposed algorithm, called LC-CloStream, is constructed by integrating CloStream algorithm and Lossy Counting algorithm. We investigate some behaviors of the LC-CloStream algorithm. Firstly we show the incompleteness and the semi-completeness for mining all frequent closed itemsets in a stream. Next, we give the completeness of eapproximation for extracting frequent itemsets.

This paper studies one-scan approximation algorithms for streaming data mining (SDM). Despite of the importance of pattern discovery in streaming data, this issue has not sufficiently addressed yet in the big data community. In this context, we briefly review the previously proposed SDM methods. There is a recent work to improve their limitation using the tecnique of online compression. It is based on the notion of Δ-cover. We then introduce them and show the experimental results obtained from high dimensional streaming transactions, each of which consists of about 10 thousand items. Consequently, the results demonstrate that we can drastically improve the scalability of SDM on the dimension number.

This study considers approximation techniques for frequent itemset mining from data streams (FIM-DS) under resource constraints. In FIM-DS, a challenging problem is handling a huge combinatorial number of entries (i.e., itemsets) to be generated from each streaming transaction and stored in memory. Various types of approximation methods have been proposed for FIM-DS. However, these methods require almost O(2L) space for the maximal length L of transactions. If some transaction contains sudden and intensive bursty events for a short span, they cannot work since memory consumption exponentially increases as L becomes larger. Thus, we present resource-oriented approximation algorithms that fix an upper bound for memory consumption to tolerate bursty transactions. The proposed algorithm requires only O(k) space for a resource-specified constant k and processes every transaction in O(kL) time. Consequently, the proposed algorithm can treat any transaction without memory overflow nor fatal response delay, while the output can be guaranteed to be no false negative under some conditions. Moreover, any (even if false negative) output is bounded within the approximation error which is dynamically determined in a resource-oriented manner. From an empirical viewpoint, it is necessary to maintain the error as low as possible. We tackle this problem by dynamically reducing the original stream. Through experimental results, we show that the resource-oriented approach can break the space limitation of previously proposed FIM-DS methods.

In this paper, we propose two kinds of semi-automatic training-example generation algorithms for rapidly synthesizing a domain-specific Web search engine. We use the keyword spice model, as a basic framework, which is an excellent approach for building a domain-specific search engine with high precision and high recall. The keyword spice model, however, requires a huge amount of training examples which should be classified by hand. For overcoming this problem, we propose two kinds of refinement algorithms based on semi-automatic training-example generation: (i) the sample decision tree based approach, and (ii) the similarity based approach. These approaches make it possible to build a highly accurate domain-specific search engine with a little time and effort. The experimental results show that our approaches are very effective and practical for the personalization of a general-purpose search engine

In this paper, we study frequent subsequence extraction from a single very-long data-sequence. First we propose a novel frequency measure, called the total frequency, for counting multiple occurrences of a sequential pattern in a single data sequence. The total frequency is anti-monotonic, and makes it possible to count up pattern occurrences without duplication. Moreover the total frequency has a good property for implementation based on the dynamic programming strategy. Second we give a simple on-line algorithm for a specialized subsequence extraction problem, i.e., a problem with the infinite window-length. This specialized problem is considered to be a relaxation of the general-case problem, thus this fast on-line algorithm is important from the view of practical applications.