Frequent Patterns

What is Market Basket Analysis?

Market Basket Analysis is a data mining technique used to find associations between items
purchased together.​
It’s based on the idea: “If a customer buys Item A, they are likely to also buy Item B.”

Example:

●​ If someone buys bread, they are also likely to buy butter.​

●​ If someone buys laptop, they may also buy a mouse.​

How it Works
Market Basket Analysis uses Association Rule Mining (often with the Apriori algorithm,
FP-growth, etc.) to discover patterns.

An association rule looks like:

{Milk, Bread} → {Butter}

This means: Customers who buy Milk and Bread also tend to buy Butter.

Key Metrics
1.​ Support​

○​ Frequency of the itemset in the dataset.​

2.​ Confidence​

○​ Probability that Y is bought when X is bought.​

3.​ Lift​

○​ Strength of the association compared to random chance.​

 ○​ Lift > 1 → Positive correlation (X and Y appear together more often than random
chance).​

○​ Lift = 1 → No correlation.​

○​ Lift < 1 → Negative correlation.​

Steps in Market Basket Analysis

1.​ Collect transaction data (e.g., POS data from a supermarket).​

2.​ Create a transaction-item matrix (rows = transactions, columns = items).​

3.​ Apply Apriori / FP-growth algorithm to generate frequent itemsets.​

4.​ Generate association rules with support, confidence, lift.​

5.​ Interpret results and apply to business decisions.​

Applications
●​ Retail: Product placement, cross-selling (chips near cold drinks).​

●​ E-commerce: Recommendation systems (“Customers who bought this also bought…”).​

●​ Healthcare: Finding common drug prescriptions.​

●​ Banking: Detecting fraudulent transactions (unusual item associations).​

Example:

If in 1,000 supermarket transactions:

●​ 200 have {Milk, Bread, Butter}​

●​ 300 have {Milk, Bread}​

Then:
●​ Support = 200 / 1000 = 0.20 (20%)​

●​ Confidence (Milk, Bread → Butter) = 200 / 300 = 0.67 (67%)​

●​ If Butter appears in 250 transactions:​

○​ Support(Butter) = 0.25​

○​ Lift = 0.67 / 0.25 = 2.68 (strong positive association)

Example Dataset
Transaction ID Items Purchased

T1 Milk, Bread

T2 Milk, Bread, Butter

T3 Bread, Butter

T4 Milk, Bread, Butter, Eggs

T5 Milk, Eggs

Step 1: Create Transaction–Item Matrix

Transaction Milk Bread Butter Eggs

T1 1 1 0 0

T2 1 1 1 0

T3 0 1 1 0

T4 1 1 1 1

T5 1 0 0 1

🔹 Step 2: Frequent Itemsets

●​ Support is calculated as:​

●​ Single items:​

○​ Support(Milk) = 4/5 = 0.8​

○​ Support(Bread) = 4/5 = 0.8​

 ○​ Support(Butter) = 3/5 = 0.6​

○​ Support(Eggs) = 2/5 = 0.4​

●​ Two-item sets:​

○​ Support(Milk, Bread) = 3/5 = 0.6​

○​ Support(Milk, Butter) = 2/5 = 0.4​

○​ Support(Bread, Butter) = 3/5 = 0.6​

○​ Support(Milk, Eggs) = 2/5 = 0.4​

●​ Three-item sets:​

○​ Support(Milk, Bread, Butter) = 2/5 = 0.4​

○​ Support(Milk, Bread, Eggs) = 1/5 = 0.2​

○​ Support(Bread, Butter, Eggs) = 1/5 = 0.2​

Step 3: Generate Rules (Support, Confidence, Lift)

Example Rule 1:

{Milk, Bread} → {Butter}

●​ Support = 2/5 = 0.4​

●​ Confidence = Support(Milk, Bread, Butter) / Support(Milk, Bread)​

= (2/5) ÷ (3/5) = 0.67 (67%)​

●​ Lift = 0.67 ÷ Support(Butter)​

= 0.67 ÷ 0.6 = 1.12 (positive association)​

Example Rule 2:

{Butter} → {Bread}

●​ Support = 3/5 = 0.6​

 ●​ Confidence = Support(Bread, Butter) / Support(Butter)​
= (3/5) ÷ (3/5) = 1.0 (100%)​

●​ Lift = 1.0 ÷ Support(Bread)​

= 1.0 ÷ 0.8 = 1.25 (strong positive)​

Example Rule 3:

{Eggs} → {Milk}

●​ Support = 2/5 = 0.4​

●​ Confidence = Support(Milk, Eggs) / Support(Eggs)​

= (2/5) ÷ (2/5) = 1.0 (100%)​

●​ Lift = 1.0 ÷ Support(Milk)​

= 1.0 ÷ 0.8 = 1.25 (positive association)​

Insights from Analysis

●​ Customers who buy Butter almost always buy Bread.​

●​ Customers who buy Eggs also tend to buy Milk.​

●​ Milk + Bread → Butter is a good cross-sell opportunity.​

Frequent Itemset
●​ Definition: A set of items that occur together in transactions with frequency above a
minimum support threshold.​

Example (from dataset above):

●​ {Milk} appears in 4/5 = 80% transactions → Frequent​

●​ {Bread, Butter} appears in 3/5 = 60% transactions → Frequent​

●​ If min support = 40%, then {Milk}, {Bread}, {Butter}, {Milk, Bread}, {Bread, Butter}, {Milk,
Bread, Butter} are frequent itemsets.​

Closed Itemset
●​ A frequent itemset is closed if none of its supersets has the same support.​

●​ In other words, you can’t add another item without reducing its frequency.​

Example:

●​ {Milk, Bread} appears in 40 transactions.​

●​ {Milk, Bread, Butter} appears in 40 transactions too → {Milk, Bread} is not closed
(because adding Butter doesn’t reduce support).​

●​ {Milk, Bread, Butter} is closed (no superset has the same frequency).​

Closed itemsets reduce redundancy in results.

Association Rule
●​ A rule derived from frequent itemsets to show relationships.​

General form:​
​
X → Y

●​ Meaning: If X is bought, Y is likely bought too.​

●​ Metrics:​

○​ Support(X→Y) = Frequency of X and Y together.​

○​ Confidence(X→Y) = Probability of buying Y when X is bought.​

○​ Lift(X→Y) = How much more likely Y is bought with X compared to random

chance.​

Example:

{Milk, Bread} → {Butter}

Support = 40%
Confidence = 67%
Lift > 1 → Positive correlation

Frequent Pattern Matching

●​ The process of discovering recurring patterns in datasets.​

●​ Algorithms used:​

○​ Apriori → generates frequent itemsets level by level.​

○​ FP-Growth → faster, uses a compressed data structure called FP-tree.​

Example of a frequent pattern:

 ●​ Customers buying Laptop → Mouse → Bag​

●​ Appears repeatedly in purchase records.​

Comparison Table
Concept Definition Example

Frequent Itemset Itemset with support ≥ min threshold {Milk, Bread} appears 60%

Closed Itemset Frequent itemset with no superset {Milk, Bread, Butter}

having same support

Association Rule If-then relation between items, {Bread} → {Butter}

evaluated with support, confidence, lift

Frequent Pattern Process of mining repeating patterns Bread & Butter appear
Matching together in 3/5 transactions

Summary with Example:

●​ MBA finds relations in transactions.​

●​ Frequent Itemset = items bought together often.​

●​ Closed Itemset = non-redundant frequent itemset.​

●​ Association Rule = If {X}, then {Y}.​

●​ Frequent Pattern Matching = Mining recurring item combinations with Apriori /

FP-growth.
Apriori Algorithm
Definition
Apriori is a frequent itemset mining algorithm used in Market Basket Analysis.​
It discovers associations among items in transactional datasets.

It works on the principle:​

“If an itemset is frequent, all of its subsets must also be frequent.”​
“If an itemset is not frequent, none of its supersets can be frequent.”

This is called the Apriori Property (or downward closure property).

Steps in Apriori Algorithm

Step 1: Set Thresholds

●​ Minimum Support = how often an itemset must appear.​

●​ Minimum Confidence = how reliable the rule must be.​

Step 2: Find Frequent 1-itemsets (L1)

●​ Count how many transactions contain each item.​

●​ Keep items with support ≥ min support.​

Step 3: Generate Candidate k-itemsets (Ck)

●​ Join frequent (k–1)-itemsets to form k-itemsets.​

●​ Eliminate those with infrequent subsets (Apriori Property).​

Step 4: Find Frequent k-itemsets (Lk)

●​ Count support for each candidate k-itemset.​

●​ Keep those with support ≥ min support.​

Step 5: Repeat

●​ Keep generating larger itemsets until no more frequent itemsets can be found.​

Step 6: Generate Association Rules

From frequent itemsets, create rules:​
​
X → Y

●​
●​ Calculate Support, Confidence, Lift.​

●​ Keep rules that meet thresholds.​

Example Dataset
Transaction ID Items

T1 Milk, Bread

T2 Milk, Bread, Butter

T3 Bread, Butter

T4 Milk, Bread, Butter, Eggs

T5 Milk, Eggs

Let’s say:

●​ Min Support = 40% (0.4)​

●​ Min Confidence = 60% (0.6)

Example 2 ) Generate association rules using Apriori Algorithm with:

●​ Minimum Support = 50%​

●​ Minimum Confidence = 75%​

Let’s solve step by step.

Dataset
ID Items

1 Bread, Butter, Jam, Milk

2 Bread, Butter, Milk

3 Bread, Juice, Curd

4 Bread, Milk, Juice

5 Butter, Milk, Juice

Total Transactions = 5

Step 1: L1 (Frequent 1-itemsets)

We need support ≥ 50% → 0.5 × 5 = 2.5 ≈ 3 transactions

Item Count Support Frequent?

Bread 4 4/5=0.8 ✅
Butter 3 3/5=0.6 ✅
Jam 1 1/5=0.2 ❌
Milk 4 4/5=0.8 ✅
Juice 3 3/5=0.6 ✅
Curd 1 1/5=0.2 ❌
👉 Frequent 1-itemsets = {Bread, Butter, Milk, Juice}
Step 2: L2 (Frequent 2-itemsets)
Check all pairs from L1:

Itemset Count Support Frequent?

Bread, Butter 2 2/5=0.4 ❌

Bread, Milk 3 3/5=0.6 ✅
Bread, Juice 2 0.4 ❌
Butter, Milk 3 0.6 ✅
Butter, Juice 1 0.2 ❌
Milk, Juice 3 0.6 ✅
👉 Frequent 2-itemsets = {Bread, Milk}, {Butter, Milk}, {Milk, Juice}
Step 3: L3 (Frequent 3-itemsets)
Combine frequent pairs:

Itemset Count Support Frequent?

Bread, Butter, Milk 2 0.4 ❌

Bread, Milk, Juice 1 0.2 ❌
Butter, Milk, Juice 1 0.2 ❌
👉 No 3-itemset meets min support.​
So final frequent itemsets = {Bread, Milk}, {Butter, Milk}, {Milk, Juice}
 Step 4: Generate Association Rules
We now create rules from frequent 2-itemsets.​
Min Confidence = 75% = 0.75.

From {Bread, Milk}

●​ Rule: Bread → Milk​

○​ Support = 3/5 = 0.6​

○​ Confidence = 3/4 = 0.75 ✅​

●​ Rule: Milk → Bread​

○​ Confidence = 3/4 = 0.75 ✅​

✅ Both valid rules.
From {Butter, Milk}

●​ Rule: Butter → Milk​

○​ Support = 3/5 = 0.6​

○​ Confidence = 3/3 = 1.0 ✅​

●​ Rule: Milk → Butter​

○​ Confidence = 3/4 = 0.75 ✅​

✅ Both valid rules.

From {Milk, Juice}

●​ Rule: Milk → Juice​

○​ Support = 3/5 = 0.6​

 ○​ Confidence = 3/4 = 0.75 ✅​
●​ Rule: Juice → Milk​

○​ Confidence = 3/3 = 1.0 ✅​

✅ Both valid rules.
Final Strong Association Rules
1.​ Bread → Milk (Support=0.6, Confidence=0.75)​

2.​ Milk → Bread (0.6, 0.75)​

3.​ Butter → Milk (0.6, 1.0)​

4.​ Milk → Butter (0.6, 0.75)​

5.​ Milk → Juice (0.6, 0.75)​

6.​ Juice → Milk (0.6, 1.0)​

So using Apriori Algorithm, these 6 rules satisfy Support ≥ 50% and Confidence ≥ 75%.
FP-Growth Algorithm (Frequent Pattern
Growth)
FP-Growth is an improved algorithm for frequent pattern mining.​
It avoids generating candidate itemsets like Apriori, and instead uses a compact data
structure (FP-tree) to directly extract frequent itemsets.

Steps of FP-Growth Algorithm

1. Scan the Database

●​ Count frequency of each item.​

●​ Discard infrequent items (below min support).​

●​ Sort items in descending frequency.​

2. Build FP-Tree

●​ Start with a root (null).​

●​ Insert each transaction, arranging items in frequency order.​

●​ Common prefixes are shared (compressed tree).​

3. Generate Conditional FP-Trees

●​ For each frequent item, create its conditional pattern base (sub-transactions ending
with that item).​

●​ Construct conditional FP-tree recursively.​

4. Mine Frequent Itemsets

●​ From conditional FP-trees, extract frequent itemsets without generating candidates

explicitly.
Mining Frequent Itemsets using Vertical
Data Format (also called ECLAT approach) in detail.

1. What is Vertical Data Format?

●​ Instead of storing transactions row-wise (horizontal format), we store them column-wise
per item.​

●​ For each item, we store the TID-list (Transaction IDs where the item appears).​

●​ Mining is then done by intersecting TID-lists to compute support counts.​

This avoids repeated scanning of the database.

2. Example Dataset
TID Items

1 A, B, C

2 A, C

3 B, C

4 A, C, D

5 B, D

Min Support = 2 transactions (40%).

3. Convert to Vertical Format

●​ A → {1, 2, 4}​

●​ B → {1, 3, 5}​
 ●​ C → {1, 2, 3, 4}​

●​ D → {4, 5}​

4. Find Frequent Itemsets

Step 1: Frequent 1-itemsets

Check support (size of TID-list):

●​ A = 3, B = 3, C = 4, D = 2 → All are frequent ✅​

Step 2: Frequent 2-itemsets (by intersecting TID-lists)

●​ A ∩ B = {1} → support = 1 ❌​
●​ A ∩ C = {1, 2, 4} → support = 3 ✅​
●​ A ∩ D = {4} → support = 1 ❌​
●​ B ∩ C = {1, 3} → support = 2 ✅​

●​ B ∩ D = {5} → support = 1 ❌​

●​ C ∩ D = {4} → support = 1 ❌​

Frequent 2-itemsets = {A,C}, {B,C}

Step 3: Frequent 3-itemsets

●​ {A,C} ∩ {B} = A ∩ B ∩ C = {1} → support = 1 ❌​

No frequent 3-itemset.
 5. Final Frequent Itemsets
●​ 1-itemsets: {A}, {B}, {C}, {D}​

●​ 2-itemsets: {A,C}, {B,C}​

Key Points
●​ Uses TID-lists intersection instead of scanning database.​

●​ More efficient than Apriori for dense datasets.​

●​ Works well in memory if TID-lists are manageable.​

●​ Candidate generation still needed, but counting is faster.​

​
Apriori (Horizontal format) → Count support by scanning transactions.​
ECLAT (Vertical format) → Count support by intersecting TID-lists.
Mining Multilevel & Multidimensional
Association Rules
1. Multilevel Association Rules
Introduction:

●​ In real-life databases, items are often organized into hierarchies (taxonomies).​

●​ Example:​

○​ Level 1: Milk​

○​ Level 2: Toned Milk, Full Cream Milk​

○​ Level 3: Amul Toned Milk, Mother Dairy Toned Milk​

Multilevel Association Rules discover relations at different abstraction levels.

●​ Rules at higher level: broader but less actionable (e.g., Milk → Bread).​

●​ Rules at lower level: more specific and useful (e.g., Amul Toned Milk → Whole Wheat
Bread).​

Example:

●​ At Level 1: {Milk} → {Bread}​

●​ At Level 2: {Toned Milk} → {Brown Bread}​

●​ At Level 3: {Amul Toned Milk} → {Britannia Brown Bread}​

Advantages:

●​ Capture general-to-specific patterns.​

●​ Useful in retail, product categorization, web log mining.​

2. Multidimensional Association Rules

Introduction:

●​ Traditional association rules: involve one dimension (e.g., items bought).​

●​ Multidimensional rules involve more than one dimension/attribute.​

Dimensions may include:

●​ Items purchased​

●​ Customer age group​

●​ Location​

●​ Time of purchase​

●​ Payment mode​

Example:

●​ Single-dimensional rule: {Milk} → {Bread}​

●​ Multidimensional rule:​

○​ {Milk, Age=20-30} → {Bread}​

○​ {Location=City, Income=High} → {Smartphone}​

Advantages:

●​ Provide richer, context-aware insights.​

●​ Useful in target marketing, recommendation systems, customer segmentation.​

3. Comparison
Feature Multilevel Association Multidimensional Association Rules
Rules

Focus Hierarchies/levels of items Multiple attributes/dimensions

Example Amul Milk → Brown Bread Age=20-30 & Milk → Bread

Data type Hierarchical items Tabular attributes (categorical/numerical)

Application Product taxonomy, web Customer profiling, market basket

usage

●​ Multilevel rules → Patterns at different levels of abstraction (hierarchy).​

●​ Multidimensional rules → Patterns across multiple attributes/dimensions.​

Association Rule Mining vs. Correlation
Analysis
Association Rule Mining

●​ Finds frequent patterns (co-occurrence of items) from transactional data.​

●​ Metrics: Support & Confidence.​

●​ Example: {Milk} → {Bread} with confidence 80%.​

○​ Means: 80% of transactions with Milk also have Bread.​

Problem: Confidence can be misleading.

●​ If Bread is very popular overall, {Milk → Bread} may have high confidence even
without real correlation.​

Correlation Analysis

●​ Goes beyond co-occurrence.​

●​ Examines statistical dependency between items.​

●​ Tells us whether items are positively, negatively, or not correlated.​

This is where Lift (and related measures) are used.

Lift Measure

​
Interpretation:

●​ Lift > 1 → Positive correlation (X and Y occur together more than expected by chance).​

●​ Lift = 1 → No correlation (independent).​

●​ Lift < 1 → Negative correlation (X and Y occur together less than expected).​

Example
Suppose we have 100 transactions:

●​ Support(Milk) = 30%​

●​ Support(Bread) = 40%​

●​ Support(Milk ∪ Bread) = 20%​

Interpretation:

●​ Customers buying Milk are 1.68 times more likely to buy Bread compared to random
chance.​

●​ So there is a positive correlation.​

 Summary
●​ Association mining: discovers frequent co-occurrence patterns.​

●​ Correlation analysis: evaluates if patterns are statistically significant.​

●​ Lift: key measure that connects them by showing strength of correlation.​

Constraint-Based Association Mining

1. Introduction
●​ Traditional association rule mining (like Apriori, FP-Growth) may generate a huge
number of rules, many of which are not useful.​

●​ Example: In a supermarket database, you may discover thousands of rules like​

○​ “Milk → Bread”,​

○​ “Chips → Cold Drink”,​

○​ “Soap → Shampoo”, etc.​

But a business manager might only want rules involving high-profit items or rules related to
seasonal products.

Constraint-Based Association Mining solves this problem by allowing the user to specify
constraints that guide the mining process.

2. What are Constraints?

Constraints are conditions or restrictions applied during rule mining so that only interesting,
useful, or business-relevant rules are generated.

Types of constraints include:

1.​ Knowledge-type constraint – e.g., focus only on multi-level rules or multi-dimensional

rules.​
 2.​ Data constraint – e.g., only include transactions from last 3 months.​

3.​ Dimension/Item constraint – e.g., only rules involving Milk or Electronics.​

4.​ Rule constraint – e.g., rules must have confidence ≥ 70% and lift > 1.2.​

3. Example
Dataset (transactions):
T1: Milk, Bread, Butter
T2: Bread, Juice
T3: Milk, Bread
T4: Bread, Butter, Juice

If we apply no constraint, Apriori might generate rules like:

●​ Milk → Bread​

●​ Juice → Bread​

●​ Butter → Milk​

Now suppose we add a constraint:​

Only generate rules where “Milk” appears in the antecedent (LHS).

Then the result will be:

●​ Milk → Bread​

●​ Milk → Butter​

This reduces useless rules and focuses on business need.

4. Advantages
●​ Reduces search space (fewer rules).​

●​ Saves time and memory.​

 ●​ Produces more meaningful rules (business-driven).​

●​ Provides user control over mining.​

5. Applications
●​ Retail: Only mine rules for high-margin items.​

●​ Banking: Rules constrained to credit card transactions only.​

●​ Healthcare: Only consider drugs from a certain category.​

●​ E-commerce: Constrain rules to holiday sales period.​

Constraint-based association mining = Association mining guided by user-defined

conditions, making results more relevant and actionable.
Frequent Pattern Growth (FP-Growth)
Algorithm
1. Introduction
The FP-Growth (Frequent Pattern Growth) algorithm is an efficient method for mining
frequent itemsets without generating candidate sets as done in the Apriori algorithm.​
It uses a compact data structure called an FP-tree (Frequent Pattern Tree) to represent
transactions.

Unlike Apriori, FP-Growth scans the database only twice:

1.​ First scan – to calculate the frequency of each item.​

2.​ Second scan – to build the FP-Tree.​

The algorithm then mines the FP-tree using a divide-and-conquer approach to generate
frequent patterns.

2. Steps of FP-Growth Algorithm

1.​ Scan the database to find the frequency of each item.​

2.​ Remove infrequent items (items with frequency < minimum support).​

3.​ Sort the remaining items in descending order of frequency.​

4.​ Construct the FP-Tree by inserting ordered frequent items from each transaction.​

5.​ Create Conditional Pattern Bases (CPB) – paths in the FP-tree that contain a
particular item.​

6.​ Build Conditional FP-Trees from these bases.​

7.​ Extract Frequent Patterns from each Conditional FP-Tree.​

3. Example
Dataset:

Transaction ID Items

T1 {E, K, M, N, O, Y}

T2 {D, E, K, N, O, Y}

T3 {A, E, K, M}

T4 {C, K, M, U, Y}

T5 {C, E, I, K, O, O}

Minimum Support (min_sup) = 3

Step 1: Count Item Frequencies

Item Frequency

A 1

C 2

D 1

E 4

I 1

K 5

M 3

N 2

O 3

U 1

Y 3
Step 2: Select Frequent Items (≥ 3)

L = {K:5, E:4, M:3, O:3, Y:3}​

(Items are arranged in descending order of frequency)

Step 3: Create Ordered Transactions

Transaction ID Original Items Ordered Frequent Items

T1 {E, K, M, N, O, Y} {K, E, M, O, Y}

T2 {D, E, K, N, O, Y} {K, E, O, Y}

T3 {A, E, K, M} {K, E, M}

T4 {C, K, M, U, Y} {K, M, Y}

T5 {C, E, I, K, O, O} {K, E, O}

Step 4: Construct the FP-Tree

All transactions are inserted in the order of their frequent items.​

Step 5: Compute Conditional Pattern Bases (CPB)
Items Conditional Pattern Base

Y {K, E, M, O:1}, {K, E, O:1}, {K, M:1}

O {K, E, M:1}, {K, E:2}

M {K, E:2}, {K:1}

E {K:4}

K -

Step 6: Build Conditional FP-Tree & Generate Patterns

Items Conditional FP-Tree Frequent Patterns Generated

Y {K:3} {K,Y:3}

O {K:3}, {E,O:3}, {E,K,O:3} {K,O:3}, {E,O:3}, {E,K,O:3}

M {K:3} {K,M:3}

E {K:4} {E,K:3}

K - -

Step 7: Final Frequent Patterns

Pattern Support

{K, Y} 3

{K, O} 3

{E, O} 3

{E, K, O} 3

{K, M} 3

{E, K} 3
4. Advantages of FP-Growth
●​ No candidate generation (unlike Apriori).​

●​ Efficient for large datasets with many transactions.​

●​ Compact representation using FP-Tree.​

●​ Requires only two database scans.​

5. Disadvantages
●​ Slightly complex to implement compared to Apriori.​

●​ The FP-tree may become large if many items are frequent.​

●​ Recursion in building conditional trees can be memory-intensive.​

6. Applications
●​ Market Basket Analysis​

●​ Web Usage Mining​

●​ Recommendation Systems​

●​ Behavior Prediction and Decision Support​

Final Summary Table (for notes)

Itemset Conditional Pattern Base Conditional FP-tree Frequent Patterns
Generated
Y {(K, E, M, O):1}, {(K, E, O):1}, {K:3} {K,Y:3}
{(K, M):1}

O {(K, E, M):1}, {(K, E):2} {K:3}, {E,O:3}, {K,O:3}, {E,O:3},

{E,K,O:3} {E,K,O:3}

M {(K, E):2}, {(K):1} {K:3} {K,M:3}

E {(K):4} {K:4} {E,K:3}

K - - -