Association mining on varied data types

Categorical data

Convert each (attribute, value) pair into a binary item (continuous attributes are first discretized), then apply the usual Apriori or FP-growth. Example: (Gender = Male), (Age = 20-30), (Education = BE). Care is needed for attributes with many values (group rare values, use concept hierarchies for multilevel rules) and for skewed values; items from the same attribute should not be combined in one candidate.

Sequential data

Mine sequential patterns: a sequence is an ordered list of itemsets (e.g. a customer's purchases over time). A sequence is frequent if it is contained as a subsequence in at least min_sup data sequences. Apriori-like methods: GSP (generate candidate sequences level by level, using the property that every subsequence of a frequent sequence is frequent), SPADE, and pattern-growth PrefixSpan. Time constraints (min/max gap, window size) can be added.

Graph (graphical) data

Mine frequent sub-graphs: a sub-graph is frequent if it occurs in at least min_sup of the graphs. Candidates are grown by adding an edge or a vertex (Apriori-based FSG, or pattern-growth gSpan); subgraph isomorphism and canonical labelling are used to avoid duplicates. Example: common substructures in chemical compounds.

Data streams

Streams are continuous, fast and cannot be stored or scanned many times, so only one-pass, approximate algorithms are used:

• Lossy counting: keep counts with an allowed error ε; items with count below ε·N are dropped periodically.
• Sticky sampling and Misra-Gries/Space-saving keep only the most frequent items.
• Sliding window or time-decayed models give more weight to recent data.
• FP-stream, an FP-tree variant that keeps tilted time windows.

In all cases, the data is first converted to a form where itemsets, sequences or graphs can be counted, and the Apriori principle is used to prune.