Lecture Notes in Computer Science, 2005, Volume 3518/2005, 269-274, DOI: 10.1007/11430919_8

Extraction of Frequent Few-Overlapped Monotone DNF Formulas with Depth-First Pruning

Yoshikazu Shima, Kouichi Hirata and Masateru Harao

View Related Documents

Abstract

In this paper, first we introduce frequent few-overlapped monotone DNF formulas under the minimum supportσ, the minimum term support τ and the maximum overlap λ. We say that a monotone DNF formula is frequent if the support of it is greater than σ and the support of each term (or itemset) in it is greater than τ, and few-overlapped if the overlap of it is less than λ and λ < τ.Then, we design the algorithm ffo_dnf to extract them. The algorithm ffo_dnf first enumerates all of the maximal frequent itemsets under τ, and secondly connects the extracted itemsets by a disjunction ∨ until satisfying σ and λ. The first step of ffo_dnf, called a depth-first pruning, follows from the property that every pair of itemsets in a few-overlapped monotone DNF formula is incomparable under a subset relation. Furthermore, we show that the extracted formulas by ffo_dnf are representative.Finally, we apply the algorithm ffo_dnf to bacterial culture data.
This work is partially supported by Grand-in-Aid for Scientific Research 15700137 and 16016275 from the Ministry of Education, Culture, Sports, Science and Technology, Japan.

Fulltext Preview

Image of the first page of the fulltext document