Constraint-Based Association Mining

1. Motivation

Apriori/FP-growth on a large, dense database produces an enormous number of rules, most of which are uninteresting or irrelevant to the analyst. Rather than post-filtering, constraint-based mining pushes the user's constraints into the mining process so that only the relevant patterns are searched for — much faster and more useful.

Examples of user constraints

"Find rules whose antecedent contains age and occupation."
"Find rules with items from {milk, bread} only."
"Find rules with support between 2% and 8% and sum of prices > ₹500."
"Find rules excluding item item_5."

2. Constraint Categories (taxonomy)

Type of constraint	Expression	Example
Anti-monotone	If an itemset violates $C$ , all its supersets also violate; if $S$ satisfies $C$ , all its subsets satisfy $C$	$sum(S.price) \le 100$ ; $S \subseteq I_{small}$ ; $support(S) \ge 2\%$ — used for pruning
Monotone	If $S$ satisfies $C$ , all supersets satisfy $C$ ; monotone constraints help grow	$sum(S.price) \ge 100$ ; $min(S.price) \le 5$ ; $S \supseteq$ a given set
Succinct	The set of satisfying itemsets can be enumerated precisely without support counting (via the data itself)	"suffix/prefix of a given item set", `S.itemset >= 5`, item membership in a set
Convertible	Not anti-monotone/monotone by itself, but becomes one after reordering the items (e.g. by value)	$avg(S.price) \le v$ after sorting items ascending by price
Inconvertible	No ordering makes it monotone/anti-monotone	$sum(S) \ge v_1 \wedge sum(S)\le v_2$ formed by items
SQL-style	Constraints expressible in SQL-like syntax	`WHERE count(*) <= 20 GROUP BY items HAVING sum(price) < 100`

3. Characterisation of Anti-monotonicity

Let $S$ be an itemset and $C$ a constraint:

C \text{ is anti-monotone} \iff \forall\, S \subseteq S' : \ C(S') \Rightarrow C(S)

 Anti-monotone (used for pruning) : if a candidate fails, drop it and all supersets
 Monotone (used for growing)      : if a set passes, all supersets pass, so keep growing
 Succinct + monotone              : efficient = generate only the satisfying set
 Convertible                      : order items e.g. by price, then it is anti/monotone
 Inconvertible                    : needs another pruning strategy (e.g. dual pruning)

4. Constraint Pushing into the Algorithm

Key idea: test the constraint inside candidate generation/pruning, at every level, instead of at the end.

Apriori-with-constraints:
   C1 = candidates(1-itemsets satisfying C)          // constraint at level 1
   L1 = {c in C1 | support >= min_sup}
   for k = 2,3... while L(k-1) != empty:
       Ck = apriori_gen(L(k-1))
       Ck = { c in Ck | c satisfies the anti-monotone / monotone constraints }   <-- push here
       count support of Ck;  Lk = frequent c in Ck
       // "constraint at each level" - if C is anti-monotone, an itemset violating it
       //   would only be extended into more violators, so pruning it is safe

Satisfiability / "characteristic set" approach: for a monotone constraint, the set of satisfying itemsets has a characteristic set (its minimal elements); for anti-monotone, the constraint only needs the satisfying set.

5. Constraint-Based Mining is Not Always Pushed Down — the `sum < 100` Example

Constraint sum(price) ≤ 100 is anti-monotone, so it can be used to prune: this simplifies the problem and can be applied early. Monitoring the most expensive item can also help if we know the minimum possible price.

However some constraints on data items, e.g. S.avg(price) = 200, are inconvertible, but here in "constraint pushing": the problem is that if an itemset is infeasible then its supersets also infeasible → this holds only for anti-monotone. For monotone/inconvertible constraints we must use the "equivalence of a constraint" with the itemset average value as the key, or the maximum/minimum itemset bound method, since the frequency of a superset does not in itself indicate the constraint value.

6. Constraint-Based Mining in Multi-dimensional Cubes

Mining is performed per cell of a data cube using iceberg cubes: only cuboids/cells that satisfy $count \ge min\_sup$ (iceberg condition) are retained. Constraints on dimensions (e.g. region = 'North') then restrict the search space.

   Cuboid (item, city) with iceberg condition count >= 2
        city=Delhi  city=Mumbai  ...
 milk      4            3        ...
 bread     5            1  (dropped: below iceberg condition)

7. A "constraint-checking" Ordering Efficient Strategy (The "C" Property)

Constraint	Category	Push-down technique
$S \subseteq \{a,b,c\}$	Anti-monotone	Prune any candidate containing an item outside the set
$support(S)\ge 3$	Anti-monotone	Apriori pruning
$\min(S.price)\le 5$	Monotone	grow supersets, prune only when exceeded?
$avg(S.price)=200$	Inconvertible	use average-based prefix pruning after sorting by price, or store per-itemset aggregates
$sum(S.price)\ge 100$	Monotone	grow; do not prune on failure
$sum(S.price)\le 100$	Anti-monotone	prune on failure
$S \cap {x}
e\phi $\| Monotone \| require$ x$
$S \cap \{k\}=\phi$	Anti-monotone	ban item $k$ entirely

8. The "Algorithm vs Constraint" Trade-Off (Implementation Strategies)

Strategy	Description	Efficiency
Post-pruning	Mine everything, filter at the end	Simple, but very wasteful
Loose/partial push-down	Apply easy constraints early, hard ones late	Good
Full push-down	All constraints checked inside the candidate generation loop	Best for pushable (anti-monotone/monotone/succinct) constraints
Rewriting the data	Put only relevant dimensions/items in the mining view (data cube)	Reduces the problem size dramatically

9. Exam Points

Define constraint-based mining and give five example constraints — 5 marks.
Explain anti-monotone, monotone, succinct, convertible and inconvertible constraints with examples — 10 marks (very frequent).
Show how an anti-monotone constraint prunes the candidate search (with a small example) — 5-7 marks.
Explain iceberg cubes / constraint-based mining on cubes — 5 marks.
Compare post-processing vs constraint pushing — 3 marks.

Constraint-Based Association Mining