Session 4

FP-Growth finds the same frequent itemsets as Apriori without generating candidates. The session compares the two and then runs Apriori with the exact parameter ranges the manual specifies.

Objectives

• Complete questions 9 to 11 of the manual: fp-growth and apriori parameter studies
• Prepare the deliverable before the lab and finish it during the session
• Be ready to explain every step in the viva

Questions Covered

Preparation

• FP-Growth in WEKA needs binary or nominal attributes; use NominalToBinary on other datasets first.
• Translate the manual’s wording into WEKA fields: upper bound 100 percent, lower bound 20 percent, delta 5 percent, minMetric 0.8, numRules 5 for question 10(a).
• Question 10(b) uses the lift metric: set metricType to Lift and minMetric to 1.5.

Question 9

Problem Statement

Find the frequent patterns using FP-Growth algorithm on contactlenses.arff and test.arff datasets.

Solution

Steps

1. Open file contact-lenses.arff. Filter, Choose, unsupervised, attribute, NominalToBinary; click the name and set transformAllValues True and binaryAttributesNominal True, OK, Apply. The 5 attributes become 12 binary ones named age=young, age=pre-presbyopic, …, contact-lenses=none, each with values 0 and 1. (FP-Growth also accepts the raw nominal file, but then for a two-valued attribute only its second value, positiveIndex 2, is an item, so tear-prod-rate=reduced would never appear in a rule.)
2. Associate, Choose, weka.associations.FPGrowth. Options: positiveIndex 2, numRulesToFind 10, metricType Confidence, minMetric 0.9, delta 0.05, lowerBoundMinSupport 0.1, upperBoundMinSupport 1.0, findAllRulesForSupportLevel False. Start.
3. test.arff is not a WEKA file; it is the 10-transaction market basket below, one binary attribute per item. Open file test.arff (already binary with values 0 and 1, so no filter). Same FPGrowth, lowerBoundMinSupport 0.3, minMetric 0.7, Start.
4. Compare with Apriori: on the same working relation choose Apriori with the same support and confidence and Start. The rules are the same; only the algorithm and the output format differ.
5. Run fpgrowth.py on both files to see the header table, the FP-tree and the full list of frequent patterns, which WEKA’s FPGrowth does not print.

Program

#!/usr/bin/env python3
"""FP-Growth frequent-pattern miner with WEKA-style rule output.

Standard library only. Builds the FP-tree (items ordered by frequency),
prints the header table and the tree, mines every frequent itemset by
recursive conditional pattern bases (no candidate generation), then derives
rules the way weka.associations.FPGrowth prints them.

Item rule (same as WEKA): if every attribute has exactly two values, only the
second value counts as 'present' (positiveIndex 2). Otherwise each
attribute=value pair is an item.

Usage: python3 fpgrowth.py FILE.arff [-M minSupport] [-C minConfidence] [-N rules]
"""
import argparse
import itertools
import re
from collections import Counter
from decimal import ROUND_HALF_UP, Decimal


def read_arff(path):
    relation, attrs, rows, in_data = "", [], [], False
    with open(path) as f:
        for line in f:
            line = line.strip()
            if not line or line.startswith("%"):
                continue
            if in_data:
                rows.append([v.strip().strip("'\"") for v in line.split(",")])
            elif line.lower().startswith("@relation"):
                relation = line.split(None, 1)[1].strip("'\"")
            elif line.lower().startswith("@attribute"):
                m = re.match(r"@attribute\s+('[^']*'|\"[^\"]*\"|\S+)\s+\{(.*)\}", line, re.I)
                attrs.append((m.group(1).strip("'\""), [v.strip() for v in m.group(2).split(",")]))
            elif line.lower().startswith("@data"):
                in_data = True
    return relation, attrs, rows


class Node:
    __slots__ = ("item", "count", "parent", "children")

    def __init__(self, item, parent):
        self.item, self.count, self.parent, self.children = item, 0, parent, {}


def build(trans, min_count):
    """trans: list of (frozenset of items, weight). Returns root, header, order, counts."""
    freq = Counter()
    for items, w in trans:
        for i in items:
            freq[i] += w
    freq = {i: c for i, c in freq.items() if c >= min_count}
    order = sorted(freq, key=lambda i: (-freq[i], i))
    root, header = Node(None, None), {i: [] for i in order}
    for items, w in trans:
        node = root
        for i in [x for x in order if x in items]:
            if i not in node.children:
                node.children[i] = Node(i, node)
                header[i].append(node.children[i])
            node = node.children[i]
            node.count += w
    return root, header, order, freq


def mine(trans, min_count, suffix, out):
    root, header, order, freq = build(trans, min_count)
    for item in reversed(order):  # least frequent item first
        pattern = suffix | {item}
        out[pattern] = freq[item]
        base = []  # conditional pattern base of `item`
        for node in header[item]:
            path, p = [], node.parent
            while p.item is not None:
                path.append(p.item)
                p = p.parent
            if path:
                base.append((frozenset(path), node.count))
        if base:
            mine(base, min_count, pattern, out)
    return root, header, order, freq


def show(node, depth=0):
    for child in node.children.values():
        print("  " * depth + f"{child.item}:{child.count}")
        show(child, depth + 1)


def fmt(x):
    """WEKA's Utils.doubleToString(x, 2): rounds half up, trailing zeros trimmed."""
    s = str(Decimal(repr(x)).quantize(Decimal("0.01"), ROUND_HALF_UP)).rstrip("0").rstrip(".")
    return s or "0"


def main():
    p = argparse.ArgumentParser()
    p.add_argument("file")
    p.add_argument("-M", type=float, default=0.2, help="minimum support (fraction)")
    p.add_argument("-C", type=float, default=0.9, help="minimum confidence")
    p.add_argument("-N", type=int, default=10, help="rules to display")
    a = p.parse_args()

    relation, attrs, rows = read_arff(a.file)
    binary = all(len(v) == 2 for _, v in attrs)
    trans = []
    for r in rows:
        items = set()
        for (name, values), v in zip(attrs, r):
            if v == "?" or (binary and v != values[1]):
                continue
            items.add(f"{name}={v}")
        trans.append((frozenset(items), 1))
    n = len(trans)
    min_count = int(a.M * n + 0.5)
    print(f"Relation: {relation}   Instances: {n}   Minimum support: {a.M} ({min_count} instances)")

    out = {}
    root, header, order, freq = mine(trans, min_count, frozenset(), out)
    print("\nHeader table (frequency-ordered items):")
    for i in order:
        print(f"  {i} {freq[i]}  ({len(header[i])} node(s))")
    print("\nFP-tree (item:count, indented by depth):")
    show(root)

    by_size = Counter(len(k) for k in out)
    print("\nFrequent itemsets by size:", dict(sorted(by_size.items())))
    for k in sorted(by_size):
        print(f"L({k}):")
        for iset in sorted((s for s in out if len(s) == k), key=sorted):
            print("  " + " ".join(sorted(iset)), out[iset])

    rules = []
    for iset, nxy in out.items():
        if len(iset) < 2:
            continue
        for size in range(1, len(iset)):
            for cons in itertools.combinations(sorted(iset), size):
                cons = frozenset(cons)
                prem = iset - cons
                nx, ny = out[prem], out[cons]
                conf = nxy / nx
                if conf >= a.C - 1e-9:
                    lift = conf / (ny / n)
                    lev = nxy / n - (nx / n) * (ny / n)
                    conv = (nx * (n - ny) / n) / (nx - nxy + 1)
                    rules.append((prem, cons, nx, nxy, conf, lift, lev, conv))
    rules.sort(key=lambda r: (-r[4], -r[3]))
    print(f"\nFPGrowth found {len(rules)} rules (displaying top {min(a.N, len(rules))})\n")
    for i, (prem, cons, nx, nxy, conf, lift, lev, conv) in enumerate(rules[: a.N], 1):
        print(f"{i:2d}. [{', '.join(sorted(prem))}]: {nx} ==> [{', '.join(sorted(cons))}]: {nxy}"
              f"   <conf:({fmt(conf)})> lift:({fmt(lift)}) lev:({fmt(lev)}) conv:({fmt(conv)})")


if __name__ == "__main__":
    main()

% test.arff - 10 market-basket transactions, one binary attribute per item.
% Value 1 (the second value, WEKA's positiveIndex 2) means the item was bought.
@relation test

@attribute bread {0, 1}
@attribute milk {0, 1}
@attribute butter {0, 1}
@attribute eggs {0, 1}
@attribute jam {0, 1}
@attribute beer {0, 1}

@data
1,1,1,0,0,0
1,1,0,1,0,0
1,0,1,0,1,0
0,1,0,1,0,1
1,1,1,1,0,0
1,0,1,0,1,0
0,1,0,0,0,1
1,1,1,0,1,0
1,1,0,1,0,0
1,1,1,0,0,0

Output

python3 fpgrowth.py contact-lenses.arff -M 0.2 -C 0.9 (computed):

Relation: contact-lenses   Instances: 24   Minimum support: 0.2 (5 instances)

Header table (frequency-ordered items):
  contact-lenses=none 15  (1 node(s))
  astigmatism=no 12  (2 node(s))
  astigmatism=yes 12  (2 node(s))
  spectacle-prescrip=hypermetrope 12  (4 node(s))
  spectacle-prescrip=myope 12  (4 node(s))
  tear-prod-rate=normal 12  (6 node(s))
  tear-prod-rate=reduced 12  (4 node(s))
  age=pre-presbyopic 8  (8 node(s))
  age=presbyopic 8  (8 node(s))
  age=young 8  (8 node(s))
  contact-lenses=soft 5  (5 node(s))

FP-tree (item:count, indented by depth):
contact-lenses=none:15
  astigmatism=no:7
    spectacle-prescrip=myope:4
      tear-prod-rate=reduced:3
        age=young:1
        age=pre-presbyopic:1
        age=presbyopic:1
      tear-prod-rate=normal:1
        age=presbyopic:1
    spectacle-prescrip=hypermetrope:3
      tear-prod-rate=reduced:3
        age=young:1
        age=pre-presbyopic:1
        age=presbyopic:1
  astigmatism=yes:8
    spectacle-prescrip=myope:3
      tear-prod-rate=reduced:3
        age=young:1
        age=pre-presbyopic:1
        age=presbyopic:1
    spectacle-prescrip=hypermetrope:5
      tear-prod-rate=reduced:3
        age=young:1
        age=pre-presbyopic:1
        age=presbyopic:1
      tear-prod-rate=normal:2
        age=pre-presbyopic:1
        age=presbyopic:1
astigmatism=no:5
  spectacle-prescrip=myope:2
    tear-prod-rate=normal:2
      age=young:1
        contact-lenses=soft:1
      age=pre-presbyopic:1
        contact-lenses=soft:1
  spectacle-prescrip=hypermetrope:3
    tear-prod-rate=normal:3
      age=young:1
        contact-lenses=soft:1
      age=pre-presbyopic:1
        contact-lenses=soft:1
      age=presbyopic:1
        contact-lenses=soft:1
astigmatism=yes:4
  spectacle-prescrip=myope:3
    tear-prod-rate=normal:3
      age=young:1
      age=pre-presbyopic:1
      age=presbyopic:1
  spectacle-prescrip=hypermetrope:1
    tear-prod-rate=normal:1
      age=young:1

Frequent itemsets by size: {1: 11, 2: 21, 3: 6}
(itemset listing omitted here; identical to the L(1), L(2), L(3) lists in Session 5)

FPGrowth found 10 rules (displaying top 10)

 1. [tear-prod-rate=reduced]: 12 ==> [contact-lenses=none]: 12   <conf:(1)> lift:(1.6) lev:(0.19) conv:(4.5)
 2. [spectacle-prescrip=myope, tear-prod-rate=reduced]: 6 ==> [contact-lenses=none]: 6   <conf:(1)> lift:(1.6) lev:(0.09) conv:(2.25)
 3. [spectacle-prescrip=hypermetrope, tear-prod-rate=reduced]: 6 ==> [contact-lenses=none]: 6   <conf:(1)> lift:(1.6) lev:(0.09) conv:(2.25)
 4. [astigmatism=yes, tear-prod-rate=reduced]: 6 ==> [contact-lenses=none]: 6   <conf:(1)> lift:(1.6) lev:(0.09) conv:(2.25)
 5. [astigmatism=no, tear-prod-rate=reduced]: 6 ==> [contact-lenses=none]: 6   <conf:(1)> lift:(1.6) lev:(0.09) conv:(2.25)
 6. [contact-lenses=soft]: 5 ==> [tear-prod-rate=normal]: 5   <conf:(1)> lift:(2) lev:(0.1) conv:(2.5)
 7. [contact-lenses=soft, tear-prod-rate=normal]: 5 ==> [astigmatism=no]: 5   <conf:(1)> lift:(2) lev:(0.1) conv:(2.5)
 8. [astigmatism=no, contact-lenses=soft]: 5 ==> [tear-prod-rate=normal]: 5   <conf:(1)> lift:(2) lev:(0.1) conv:(2.5)
 9. [contact-lenses=soft]: 5 ==> [astigmatism=no, tear-prod-rate=normal]: 5   <conf:(1)> lift:(4) lev:(0.16) conv:(3.75)
10. [contact-lenses=soft]: 5 ==> [astigmatism=no]: 5   <conf:(1)> lift:(2) lev:(0.1) conv:(2.5)

python3 fpgrowth.py test.arff -M 0.3 -C 0.7 (computed):

Relation: test   Instances: 10   Minimum support: 0.3 (3 instances)

Header table (frequency-ordered items):
  bread=1 8  (1 node(s))
  milk=1 8  (2 node(s))
  butter=1 6  (2 node(s))
  eggs=1 4  (3 node(s))
  jam=1 3  (2 node(s))

FP-tree (item:count, indented by depth):
bread=1:8
  milk=1:6
    butter=1:4
      eggs=1:1
      jam=1:1
    eggs=1:2
  butter=1:2
    jam=1:2
milk=1:2
  eggs=1:1

Frequent itemsets by size: {1: 5, 2: 7, 3: 3}
L(1):
  bread=1 8
  butter=1 6
  eggs=1 4
  jam=1 3
  milk=1 8
L(2):
  bread=1 butter=1 6
  bread=1 eggs=1 3
  bread=1 jam=1 3
  bread=1 milk=1 6
  butter=1 jam=1 3
  butter=1 milk=1 4
  eggs=1 milk=1 4
L(3):
  bread=1 butter=1 jam=1 3
  bread=1 butter=1 milk=1 4
  bread=1 eggs=1 milk=1 3

FPGrowth found 15 rules (displaying top 10)

 1. [butter=1]: 6 ==> [bread=1]: 6   <conf:(1)> lift:(1.25) lev:(0.12) conv:(1.2)
 2. [eggs=1]: 4 ==> [milk=1]: 4   <conf:(1)> lift:(1.25) lev:(0.08) conv:(0.8)
 3. [butter=1, milk=1]: 4 ==> [bread=1]: 4   <conf:(1)> lift:(1.25) lev:(0.08) conv:(0.8)
 4. [jam=1]: 3 ==> [butter=1]: 3   <conf:(1)> lift:(1.67) lev:(0.12) conv:(1.2)
 5. [butter=1, jam=1]: 3 ==> [bread=1]: 3   <conf:(1)> lift:(1.25) lev:(0.06) conv:(0.6)
 6. [bread=1, jam=1]: 3 ==> [butter=1]: 3   <conf:(1)> lift:(1.67) lev:(0.12) conv:(1.2)
 7. [jam=1]: 3 ==> [bread=1, butter=1]: 3   <conf:(1)> lift:(1.67) lev:(0.12) conv:(1.2)
 8. [jam=1]: 3 ==> [bread=1]: 3   <conf:(1)> lift:(1.25) lev:(0.06) conv:(0.6)
 9. [bread=1, eggs=1]: 3 ==> [milk=1]: 3   <conf:(1)> lift:(1.25) lev:(0.06) conv:(0.6)
10. [bread=1]: 8 ==> [butter=1]: 6   <conf:(0.75)> lift:(1.25) lev:(0.12) conv:(1.07)

What WEKA prints for contact-lenses after NominalToBinary (item names carry the binary value, otherwise the same ten rules as above):

Scheme:       weka.associations.FPGrowth -P 2 -I -1 -N 10 -T 0 -C 0.9 -D 0.05 -U 1.0 -M 0.1
Relation:     contact-lenses-weka.filters.unsupervised.attribute.NominalToBinary-N-A-Rfirst-last
Instances:    24    Attributes:   12

FPGrowth found 10 rules (displaying top 10)

 1. [tear-prod-rate=reduced=1]: 12 ==> [contact-lenses=none=1]: 12   <conf:(1)> lift:(1.6) lev:(0.19) conv:(4.5)
 2. [spectacle-prescrip=myope=1, tear-prod-rate=reduced=1]: 6 ==> [contact-lenses=none=1]: 6   <conf:(1)> lift:(1.6) lev:(0.09) conv:(2.25)
 ...
10. [contact-lenses=soft=1]: 5 ==> [astigmatism=no=1, tear-prod-rate=normal=1]: 5   <conf:(1)> lift:(4) lev:(0.16) conv:(3.75)

FP-Growth against Apriori on contact-lenses at support 0.2:

Explanation

FP-Growth compresses the transactions into a prefix tree. Items are sorted by frequency (contact-lenses=none 15 first, contact-lenses=soft 5 last; ties broken alphabetically here, WEKA’s tie order may differ) so that frequent items share tree prefixes: all 15 none rows hang under one node. The header table links every node of an item. Mining starts from the least frequent item: its conditional pattern base is the set of prefix paths above its nodes, a small conditional tree is built from them, and the recursion continues. No candidate is ever generated, so the 210 candidate pairs Apriori has to test on this file are never formed. Both algorithms find the identical frequent itemsets because the definition of frequent does not depend on the search; that is why the rule lists agree line for line. On test.arff the tree shows the pattern immediately: bread and milk head almost every path, jam only appears under butter, which gives the rule jam ==> butter with lift 1.67.

Question 10

Problem Statement

Generate association rules using Apriori algorithm with Bank.arff relation

1. Set minimum support range as 20% to 100%, incremental decrease factor as 5% and confidence factor as 80% and generate 5 rules.
2. Set minimum support as 10%, delta 5%, minimum lift as 150% and generate 4 rules.

Solution

Use bank-nominal.arff from Session 2 (bank-data with id removed, age and income in 3 bins, children nominal). Apriori refuses the raw file because age, income and children are numeric.

Steps

1. Open file bank-nominal.arff; confirm 600 instances, 11 attributes, all Nominal.
2. Associate, Choose Apriori, click the name and set, for part (a):

3. OK, Start. The Scheme line must read weka.associations.Apriori -N 5 -T 0 -C 0.8 -D 0.05 -U 1.0 -M 0.2 -S -1.0 -c -1.
4. For part (b) set:

5. OK, Start. Scheme line: weka.associations.Apriori -N 4 -T 1 -C 1.5 -D 0.05 -U 1.0 -M 0.1 -S -1.0 -c -1.
6. Tick outputItemSets and Start once more if you need the large itemset counts for the record.

Output

Expected shape (WEKA was not run here; bank-data is 600 rows and the counts depend on your bins, so copy the numbers from your own screen):

=== Run information ===

Scheme:       weka.associations.Apriori -N 5 -T 0 -C 0.8 -D 0.05 -U 1.0 -M 0.2 -S -1.0 -c -1
Relation:     bank-nominal
Instances:    600
Attributes:   11
=== Associator model (full training set) ===

Minimum support: 0.2 (120 instances)      <- or the first level at which 5 rules pass
Minimum metric <confidence>: 0.8
Number of cycles performed: 16

Best rules found:

 1. children=0 save_act=YES 190 ==> current_act=YES 158    <conf:(0.83)> lift:(1.1) ...
 2. ...

Part (b) prints Minimum metric <lift>: 1.5 and rules whose lift column is in angle brackets, for example income='(43758.136667-inf)' 120 ==> save_act=YES 110 conf:(0.92) <lift:(1.33)> ... would be rejected at 1.5 while a rule between mortgage=YES and pep=YES with lift above 1.5 would be kept.

Rules that this dataset is known to produce at high confidence involve current_act=YES (76 percent of customers) as a consequent, and at high lift involve income bins with save_act and children=0 with pep.

Explanation

Part (a) is a confidence search bounded by support: WEKA starts at support 0.95, lowers it by 0.05 a cycle, and stops at the first level where at least 5 rules have confidence 0.8 or better, or at 0.2. Because current_act=YES holds for three quarters of the rows, almost any premise predicts it with confidence above 0.8, so the top confidence rules are trivial. Part (b) fixes that by ranking on lift: $\text{lift}=\frac{\text{confidence}}{\text{support}(Y)}$ divides by how common the consequent is, so a rule predicting current_act=YES with confidence 0.83 gets lift 1.1 and fails the 1.5 threshold, while a rule that raises the chance of a rare consequent by half or more passes. The lower support bound of 0.1 (60 rows) lets rarer but stronger patterns through.

Question 11

Problem Statement

Generate association rule for the credit card promotion dataset using Apriori algorithm with the support range 40% to 100%, confidence as 10%, incremental decrease as 5% and generate 6 rules.

Solution

The credit card promotion database is the 15-row table from Roiger and Geatz: income-range, magazine-promotion, watch-promotion, life-insurance-promotion, credit-card-insurance, sex (all nominal) and age (numeric). It is small enough to compute for real.

Steps

1. Type the file below as credit-card-promotion.arff and Open file it.
2. Remove age (attribute 7): tick it and click Remove, because Apriori cannot use a numeric attribute. (Discretize would also work but the question does not ask for age rules.)
3. Associate, Choose Apriori, set lowerBoundMinSupport 0.4, upperBoundMinSupport 1.0, delta 0.05, metricType Confidence, minMetric 0.1, numRules 6, outputItemSets True. OK, Start.
4. Check the Scheme line: weka.associations.Apriori -N 6 -T 0 -C 0.1 -D 0.05 -U 1.0 -M 0.4 -S -1.0 -c -1.
5. Reproduce with python3 apriori.py credit-card-promotion.arff -R 7 -M 0.4 -C 0.1 -N 6 -I.

Program

% credit-card-promotion.arff - the 15-row credit card promotion database
% (Roiger and Geatz, Data Mining: A Tutorial-Based Primer, Table 2.3)
@relation credit-card-promotion

@attribute income-range {20-30K, 30-40K, 40-50K, 50-60K}
@attribute magazine-promotion {yes, no}
@attribute watch-promotion {yes, no}
@attribute life-insurance-promotion {yes, no}
@attribute credit-card-insurance {yes, no}
@attribute sex {male, female}
@attribute age numeric

@data
40-50K,yes,no,no,no,male,45
30-40K,yes,yes,yes,no,female,40
40-50K,no,no,no,no,male,42
30-40K,yes,yes,yes,yes,male,43
50-60K,yes,no,yes,no,female,38
20-30K,no,no,no,no,female,55
30-40K,yes,no,yes,yes,male,35
20-30K,no,yes,no,no,male,27
30-40K,yes,no,no,no,male,43
30-40K,yes,yes,yes,no,female,41
40-50K,no,yes,yes,no,female,43
20-30K,no,yes,yes,no,male,29
50-60K,yes,yes,yes,no,female,39
40-50K,no,yes,no,no,male,55
20-30K,no,no,yes,yes,female,19

Output

Computed with apriori.py (same format as WEKA’s Associate output; the Run information lists 15 instances and the 6 remaining attributes):

Minimum support: 0.4 (6 instances)
Minimum metric <confidence>: 0.1
Number of cycles performed: 12

Generated sets of large itemsets:

Size of set of large itemsets L(1): 9

Large Itemsets L(1):
magazine-promotion=yes 8
magazine-promotion=no 7
watch-promotion=yes 8
watch-promotion=no 7
life-insurance-promotion=yes 9
life-insurance-promotion=no 6
credit-card-insurance=no 12
sex=male 8
sex=female 7

Size of set of large itemsets L(2): 10

Large Itemsets L(2):
magazine-promotion=yes life-insurance-promotion=yes 6
magazine-promotion=yes credit-card-insurance=no 6
magazine-promotion=no credit-card-insurance=no 6
watch-promotion=yes life-insurance-promotion=yes 6
watch-promotion=yes credit-card-insurance=no 7
life-insurance-promotion=yes credit-card-insurance=no 6
life-insurance-promotion=yes sex=female 6
life-insurance-promotion=no credit-card-insurance=no 6
credit-card-insurance=no sex=male 6
credit-card-insurance=no sex=female 6

Best rules found:

 1. life-insurance-promotion=no 6 ==> credit-card-insurance=no 6    <conf:(1)> lift:(1.25) lev:(0.08) [1] conv:(1.2)
 2. watch-promotion=yes 8 ==> credit-card-insurance=no 7    <conf:(0.88)> lift:(1.09) lev:(0.04) [0] conv:(0.8)
 3. magazine-promotion=no 7 ==> credit-card-insurance=no 6    <conf:(0.86)> lift:(1.07) lev:(0.03) [0] conv:(0.7)
 4. sex=female 7 ==> life-insurance-promotion=yes 6    <conf:(0.86)> lift:(1.43) lev:(0.12) [1] conv:(1.4)
 5. sex=female 7 ==> credit-card-insurance=no 6    <conf:(0.86)> lift:(1.07) lev:(0.03) [0] conv:(0.7)
 6. magazine-promotion=yes 8 ==> life-insurance-promotion=yes 6    <conf:(0.75)> lift:(1.25) lev:(0.08) [1] conv:(1.07)

Explanation

With minMetric 0.1 the confidence filter is almost switched off, so the search is governed by support alone: WEKA lowers support from 0.95 until 6 rules exist, which happens at 0.4 (6 of 15 rows) after 12 cycles. At that level 9 single items and 10 pairs are large and no triple is, so every rule has one item on each side. The top rule, life-insurance-promotion=no ==> credit-card-insurance=no, has confidence $\frac{6}{6}=1$ but lift only $\frac{1}{12/15}=1.25$, because 12 of 15 customers have no credit card insurance anyway. The more useful rule is sex=female ==> life-insurance-promotion=yes (6 of 7, confidence 0.86, lift 1.43): women in this table took the life insurance promotion far more often than the base rate of 9 in 15. The exercise shows why a low confidence threshold is harmless when support is high, but the rules must be read with lift.

Viva Questions

Q: What does FP-Growth avoid that Apriori must do? A: Candidate generation and repeated scans; it builds a compressed tree in two scans and mines it recursively.

Q: What is a conditional pattern base? A: The set of prefix paths (with their counts) that lead to the nodes of one item in the FP-tree.

Q: Why sort items by frequency before inserting a transaction? A: So that common items sit near the root and many transactions share the same prefix, which keeps the tree small.

Q: In WEKA’s FPGrowth what does positiveIndex 2 mean? A: For a binary attribute, only its second value is treated as the item being present.

Q: Why did part (a) of the Bank question give trivial rules? A: Confidence rewards common consequents; current_act=YES is true for most rows so nearly any premise predicts it.

Q: How is “minimum lift 150%” entered in WEKA? A: metricType Lift and minMetric 1.5.

Q: In the credit card run, why did the support stop at 0.4 and not lower? A: lowerBoundMinSupport was 0.4 and six rules already passed there, so the loop ended.

Common Mistakes

• Running FPGrowth on a nominal file without NominalToBinary and then reporting that the first value of every two-valued attribute never appears in a rule.
• Entering 80 instead of 0.8 for minMetric, or 20 instead of 0.2 for the support bound; WEKA wants fractions.
• Leaving metricType on Confidence for the lift question and reading the lift: column by eye instead of letting WEKA rank by it.
• Forgetting to remove or discretise age in the credit card file, so Start stays disabled.

Formula Sheet

Association rules

For a rule $X\Rightarrow Y$ over $N$ transactions:

WEKA’s Apriori starts at the upper bound of minimum support and lowers it by the delta each pass until the requested number of rules is found or the lower bound is reached.

Entropy, information gain and Gini

For a set $S$ with class proportions $p_1,\dots ,p_c$:

ID3 splits on the attribute with the highest gain; J48 (C4.5) uses the gain ratio $\text{Gain}(S,A)/\text{SplitInfo}(S,A)$ where $\text{SplitInfo}(S,A)=-{\sum }_v\frac{|S_v|}{|S|}{\log }_2\frac{|S_v|}{|S|}$.

Classifier evaluation

From the confusion matrix with true positives $TP$, false positives $FP$, false negatives $FN$, true negatives $TN$:

Kappa compares observed agreement $p_o$ (accuracy) with the agreement expected by chance $p_e$:

The ROC curve plots true positive rate $TP/(TP+FN)$ against false positive rate $FP/(FP+TN)$; the area under it (AUC) is 0.5 for guessing and 1.0 for a perfect classifier.

Naive Bayes and k-nearest neighbour

k-NN assigns the majority class among the $k$ nearest training records under Euclidean distance

after normalising each attribute to $[0,1]$ with $x^{\prime }=(x-x_{\min })/(x_{\max }-x_{\min })$.

Linear regression

WEKA reports the correlation coefficient, mean absolute error and root mean squared error $\sqrt{\frac{1}{N}\sum {(y_i-{\hat{y}}_i)}^2}$.

Clustering

k-means minimises the within-cluster sum of squared errors over clusters $C_1,\dots ,C_k$ with centroids ${\mu }_j$:

Hierarchical (agglomerative) clustering merges the two closest clusters each step; linkage defines closeness: single $\min d(a,b)$, complete $\max d(a,b)$, average $\frac{1}{|A||B|}\sum d(a,b)$.

DBSCAN calls a point a core point when at least $\text{minPts}$ points lie within radius $\epsilon$; clusters grow from core points, and points reachable from none are noise.

Session Summary

• Question 9: fpgrowth.py written; FP-tree, header table and frequent patterns produced for contact-lenses.arff (11, 21, 6 itemsets, same 10 rules as Apriori) and for the hand-written test.arff; WEKA FPGrowth steps with NominalToBinary recorded
• Question 10: Bank.arff parameter table mapped to lowerBoundMinSupport, upperBoundMinSupport, delta, metricType, minMetric, numRules for both runs; Scheme lines and expected output shape recorded
• Question 11: credit-card-promotion.arff typed (15 rows), age removed, Apriori at support 0.4 to 1.0, delta 0.05, confidence 0.1, 6 rules computed and interpreted with lift