Categorical data; sequential, sub-graph patterns

Issues related to categorical (non-binary) data

Association analysis was designed for asymmetric binary items. Categorical and continuous attributes, such as {Gender = Male, Education = Graduate, State = Bagmati}, must first be converted:

• Binarisation: each (attribute, value) pair becomes an item; continuous attributes are discretised.
• Issues: (1) too many items from attributes with many values; (2) attribute values with low frequency make rules infrequent, and skewed values (e.g. 95% "No") produce spurious patterns; (3) redundant rules because of concept hierarchies and relations between attributes; (4) loss of information in discretisation; (5) items from the same attribute must not appear together in one rule.
• Solutions: group rare values into "Other", use concept hierarchies (multilevel association), and use a lower support for rarer items.

Sequential patterns

A sequence is an ordered list of itemsets (events), e.g. ⟨{Laptop}, {Mouse, Bag}⟩. A sequential pattern is a subsequence that appears in at least min_sup data sequences (customers). Example: customers who buy a camera later buy a memory card within a month. Support is the fraction of sequences containing the pattern; timing constraints (maxgap, mingap, window) can be added. Algorithms: GSP, SPADE, PrefixSpan.

Sub-graph patterns

Data such as chemical compounds, web links or social networks are graphs. A frequent sub-graph is a subgraph that appears in at least min_sup graphs of the data set. Candidate subgraphs are generated by adding a vertex or an edge (Apriori-like FSG, or pattern-growth gSpan), with checks for graph isomorphism. Uses: finding common substructures of molecules, web communities.

Infrequent patterns

An infrequent pattern is an itemset whose support is below minsup; most are uninteresting, but some are still important.

• Negative patterns: itemsets that involve the absence of items (negated items), e.g. {Coffee, ¬Tea}: customers who buy coffee but not tea.
• Negatively correlated patterns: itemsets whose support is much lower than expected if the items were independent: s(X ∪ Y) < s(X)·s(Y), e.g. coffee and tea are rarely bought together.
• Use: finding rare but important events such as fraud, system faults and rare diseases. Mining uses a very low support or methods based on expected support.