Non-Derivable Item Set and Non-Derivable Literal Set Representations of Patterns Admitting Negation

摘要

The discovery of frequent patterns has attracted a lot of attention of the data mining community. While an extensive research has been carried out for discovering positive patterns, little has been offered for discovering patterns with negation. The main hindrance to the progress of such research is huge amount of frequent patterns with negation, which exceeds the number of frequent positive patterns by orders of magnitude. In this paper, we examine properties of derivable and non-derivable patterns, including those with negated items. In particular, we establish important relationships among patterns admitting negation that have the same canonical variant. By analogy to frequent non-derivable itemsets, which constitute a concise lossless representation NDR of frequent positive patterns, we introduce frequent non-derivable literal sets lossless representation NDRL of frequent positive patterns admitting negation. Then we use the derived properties of literal sets to offer a concise representation NDIR of frequent patterns admitting negation that is built only from positive non-derivable itemsets. The relationships between the three representations are identified. The transformation of the new representations into not less concise lossless closure representations is discussed.