Mining Multidimensional
Association Rules
From Relational Databases and Data
Warehouses
Lecture Based on Han & Kamber (2006), Section 6.4
Introduction
• Association rule mining finds relationships among data items.
• Traditionally focused on single-dimensional transactional data.
• Multidimensional association rules mine across attributes
like age, income, location, product.
• Applicable to relational databases and data warehouses
where multiple attributes exist.
• Definition: Association rules involving more than one dimension.
• Format: (Dimension1 = value1) ^ (Dimension2 = value2) =>
(Dimension3 = value3)
Key Definitions
Term Meaning
Multidimensional Rule Involves ≥2 predicates (e.g., age, buys)
Inter-dimension Rule Distinct predicates appear only once
Hybrid-dimension Rule Repeated predicates (e.g., multiple buys)
Discrete values, finite values
Categorical Attribute
(e.g., color, occupation)
Numeric values, continuous values
Quantitative Attribute
(e.g., age, income)
age(X, "19–24") ∧ occupation(X, "student") →
buys(X, "laptop")
Three Approaches to Handling
Quantitative Attributes
Approach Description
Predefined concept hierarchies
Static Discretization
used
Quantitative Association Rules Dynamic binning during mining
Distance-Based Association Clustering based on value
Rules proximity
1. Static
Discretization of
Quantitative
Attributes
• Replace numeric values with
predefined ranges
• Uses concept hierarchies (e.g.,
income: 20K–30K → “Low”)
• Discretized attributes treated like
categorical ones
• Can use Apriori-like algorithms
or data cubes
Data Cubes for Efficient Mining
• Store aggregate values for dimensions like age, income,
buys
• Cuboids represent combinations; base cuboid = full
granularity
• Efficient support/confidence computation
2. Quantitative Association
Rules
• Discretization occurs during mining
• Focused on confidence/compactness optimization
• Example:
age(X, "30–34") ∧ income(X, "42K–48K") → buys(X, "high-res TV")
Uses grid-based clustering,
e.g., ARCS algorithm
ARCS in Data Mining - Key
Concepts
• ARCS stands for Association Rule Clustering System,
which is used to organize and interpret large sets of
association rules.
• Association Rules: Patterns like “If A and B, then C”
found in transactional data.
• Clustering: Grouping similar rules to reduce
redundancy and improve interpretability.
• Binning: Quantitative attributes are partitioned into
intervals (bins) to simplify rule generation.
ARCS Workflow
• Equal-width binning:
User-defined bin sizes for numeric attributes.
• 2D Grid Construction:
Each cell represents a bin combination with class distributions.
• Rule Generation:
Frequent predicate sets are extracted based on support and confidence.
• Clustering:
Rectangular clusters of rules are formed for better visualization and analysis.
Rule Clustering Concept
• Find close rules and merge to simplify
Cluster rules:
• age=34, income=30K–40K → buys high-res TV
• age=35, income=40K–50K → buys high-res TV
→ Combine into:
age=34–35 ∧ income=30K–50K → buys high-res TV
3. Distance-Based Association
Rules
• Use clustering algorithms to define intervals
• Based on proximity rather than exact intervals
• Measures closeness between numeric values or
multidimensional tuples.
• Rule example: If two customers are
similar in age and spending, they likely
buy similar products.
• Replace support/confidence with:
• Density Threshold
• Degree of Association
(distance-based)
Cluster-Based Rule Mining (Two-
Phase)
Phase 1:
• Apply clustering on attribute tuples
• Use diameter/density metrics
Phase 2:
• Mine rules of the form:
Cluster_A(Milk) → Cluster_B(Snacks)
Summary
• Multidimensional rules reveal rich, cross-attribute
insights
• Techniques vary by attribute type & data representation
• Data cubes and concept hierarchies boost performance
• Clustering empowers approximate and dynamic rule
discovery