Session 3 | Syntax Lab

This session (PDF)MCSL-223 Section 2 (ZIP)MCSL-223 (ZIP)Semester 2 (ZIP)

Apriori needs nominal attributes, so discretisation comes first. This session runs Apriori across several datasets with different support and confidence settings and studies the rules produced.

Objectives

Do not copy. Read for understanding and the viva

Complete questions 7 to 8 of the manual: unsupervised filters and apriori
Prepare the deliverable before the lab and finish it during the session
Be ready to explain every step in the viva

Questions Covered

Do not copy. Read for understanding and the viva

Question	Requirement	Status
Q7	Perform the following	Complete
Q8	Implement the Apriori Algorithm to find the association rules in contactlenses.arff…	Complete

Preparation

Do not copy. Read for understanding and the viva

Apriori parameters in WEKA: lowerBoundMinSupport, upperBoundMinSupport, delta, minMetric (confidence), numRules. Know what each does before changing it.
Discretize with equal-width and equal-frequency bins and compare the rules; note that bin boundaries appear in the rules.
For question 8, implement Apriori by hand or in Python on the 24-row contact-lenses data: candidate generation, support counting, pruning, then rule generation with confidence.

Question 7

Problem Statement

Write in lab record

Perform the following:

Explore various options available in WEKA for preprocessing data and apply unsupervised filters like Discretization, Resample-filter etc. on various datasets.
Load weather, nominal, Iris, Glass datasets into WEKA and run Apriori algorithms with different support and confidence values.
Study the rules generated.
Apply different discretization filters on numerical attributes and run the Apriori association rule algorithm. Study the rules generated.
Derive interesting insights and observe the effect of discretization in the rule generation process.

Solution

Write in lab record

Steps

Unsupervised filters live under Filter, Choose, weka.filters.unsupervised. The ones used in this session:

Filter	Menu path	Options that matter
Discretize	attribute, Discretize	`attributeIndices` (default first-last, numeric only), `bins` (10), `useEqualFrequency` (False), `findNumBins` (False), `makeBinary` (False)
Resample	instance, Resample	`sampleSizePercent` (100), `noReplacement` (False), `randomSeed` (1)
Normalize	attribute, Normalize	`scale` 1.0, `translation` 0.0
Standardize	attribute, Standardize	none; gives mean 0, standard deviation 1
NominalToBinary	attribute, NominalToBinary	`transformAllValues`, `attributeIndices`
RemoveUseless	attribute, RemoveUseless	`maximumVariancePercentageAllowed` 99; drops constant attributes and identifiers
Randomize	instance, Randomize	`randomSeed`; shuffles row order

Apriori is at Associate tab, Choose, weka.associations.Apriori. Click the name to open the options:

Parameter	Default	Meaning
upperBoundMinSupport	1.0	support at which the search starts
delta	0.05	support is lowered by this each cycle
lowerBoundMinSupport	0.1	search stops here
metricType	Confidence	Confidence, Lift, Leverage or Conviction
minMetric	0.9	rules below this are dropped
numRules	10	stop lowering support once this many rules pass
outputItemSets	False	also print the large itemsets
car	False	mine class association rules only

weather.nominal, run 1: Open file weather.nominal.arff, Associate, Choose Apriori, keep defaults, Start.
weather.nominal, run 2: click the Apriori name, set lowerBoundMinSupport 0.3 and minMetric 0.7, OK, Start.
iris: Open file iris.arff, Preprocess, Discretize with bins 3 on first-last (the class is nominal and is skipped), Apply. Associate, Apriori defaults, Start. Then minMetric 0.7, numRules 8, Start.
iris again with the default 10 bins: Undo, Discretize with bins 10, Apply, Apriori defaults, Start. Compare with step 3.
glass: Open file glass.arff, Discretize bins 3, Apply, Apriori defaults, Start; then lowerBoundMinSupport 0.5, minMetric 0.95, Start.
Every output below that says computed was produced with apriori.py (Question 8) on the same data; the Python and WEKA output formats are the same, so compare line by line.

Output

weather.nominal, defaults (computed; identical to the block on page 57 of the manual):

Minimum support: 0.15 (2 instances)
Minimum metric <confidence>: 0.9
Number of cycles performed: 17

Generated sets of large itemsets:

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

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

Size of set of large itemsets L(3): 39

Size of set of large itemsets L(4): 6

Best rules found:

 1. outlook=overcast 4 ==> play=yes 4    <conf:(1)> lift:(1.56) lev:(0.1) [1] conv:(1.43)
 2. temperature=cool 4 ==> humidity=normal 4    <conf:(1)> lift:(2) lev:(0.14) [2] conv:(2)
 3. humidity=normal windy=FALSE 4 ==> play=yes 4    <conf:(1)> lift:(1.56) lev:(0.1) [1] conv:(1.43)
 4. outlook=sunny play=no 3 ==> humidity=high 3    <conf:(1)> lift:(2) lev:(0.11) [1] conv:(1.5)
 5. outlook=sunny humidity=high 3 ==> play=no 3    <conf:(1)> lift:(2.8) lev:(0.14) [1] conv:(1.93)
 6. outlook=rainy play=yes 3 ==> windy=FALSE 3    <conf:(1)> lift:(1.75) lev:(0.09) [1] conv:(1.29)
 7. outlook=rainy windy=FALSE 3 ==> play=yes 3    <conf:(1)> lift:(1.56) lev:(0.08) [1] conv:(1.07)
 8. temperature=cool play=yes 3 ==> humidity=normal 3    <conf:(1)> lift:(2) lev:(0.11) [1] conv:(1.5)
 9. outlook=sunny temperature=hot 2 ==> humidity=high 2    <conf:(1)> lift:(2) lev:(0.07) [1] conv:(1)
10. temperature=hot play=no 2 ==> outlook=sunny 2    <conf:(1)> lift:(2.8) lev:(0.09) [1] conv:(1.29)

weather.nominal, lowerBoundMinSupport 0.3 and minMetric 0.7 (computed):

Minimum support: 0.3 (4 instances)
Minimum metric <confidence>: 0.7
Number of cycles performed: 14

Generated sets of large itemsets:

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

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

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

Best rules found:

 1. outlook=overcast 4 ==> play=yes 4    <conf:(1)> lift:(1.56) lev:(0.1) [1] conv:(1.43)
 2. temperature=cool 4 ==> humidity=normal 4    <conf:(1)> lift:(2) lev:(0.14) [2] conv:(2)
 3. humidity=normal windy=FALSE 4 ==> play=yes 4    <conf:(1)> lift:(1.56) lev:(0.1) [1] conv:(1.43)
 4. humidity=normal 7 ==> play=yes 6    <conf:(0.86)> lift:(1.33) lev:(0.11) [1] conv:(1.25)
 5. play=no 5 ==> humidity=high 4    <conf:(0.8)> lift:(1.6) lev:(0.11) [1] conv:(1.25)
 6. windy=FALSE 8 ==> play=yes 6    <conf:(0.75)> lift:(1.17) lev:(0.06) [0] conv:(0.95)

Only 6 rules pass: at support 0.3 (4 instances) there are just 9 large 2-itemsets and one 3-itemset, and support cannot drop further because the lower bound was reached.

iris discretised into 3 equal-width bins, Apriori defaults. Computed on iris-sample.arff, the first 10 rows of each class (30 of the 150 rows), so the counts are 10 where WEKA prints 50 on the full file:

Minimum support: 0.3 (9 instances)
Minimum metric <confidence>: 0.9
Number of cycles performed: 14

Generated sets of large itemsets:

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

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

Size of set of large itemsets L(3): 6

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

Best rules found:

 1. petallength='(-inf-3.066667]' 10 ==> sepallength='(-inf-5.466667]' 10    <conf:(1)> lift:(2.31) lev:(0.19) [5] conv:(5.67)
 2. petalwidth='(-inf-0.9]' 10 ==> sepallength='(-inf-5.466667]' 10    <conf:(1)> lift:(2.31) lev:(0.19) [5] conv:(5.67)
 3. class=Iris-setosa 10 ==> sepallength='(-inf-5.466667]' 10    <conf:(1)> lift:(2.31) lev:(0.19) [5] conv:(5.67)
 4. petalwidth='(-inf-0.9]' 10 ==> petallength='(-inf-3.066667]' 10    <conf:(1)> lift:(3) lev:(0.22) [6] conv:(6.67)
 5. petallength='(-inf-3.066667]' 10 ==> petalwidth='(-inf-0.9]' 10    <conf:(1)> lift:(3) lev:(0.22) [6] conv:(6.67)
 6. class=Iris-setosa 10 ==> petallength='(-inf-3.066667]' 10    <conf:(1)> lift:(3) lev:(0.22) [6] conv:(6.67)
 7. petallength='(-inf-3.066667]' 10 ==> class=Iris-setosa 10    <conf:(1)> lift:(3) lev:(0.22) [6] conv:(6.67)
 8. petallength='(3.066667-4.833333]' 10 ==> petalwidth='(0.9-1.7]' 10    <conf:(1)> lift:(2.73) lev:(0.21) [6] conv:(6.33)
 9. class=Iris-setosa 10 ==> petalwidth='(-inf-0.9]' 10    <conf:(1)> lift:(3) lev:(0.22) [6] conv:(6.67)
10. petalwidth='(-inf-0.9]' 10 ==> class=Iris-setosa 10    <conf:(1)> lift:(3) lev:(0.22) [6] conv:(6.67)

With minMetric 0.7 and numRules 8 the same 8 rules come out first, because there are already more than 8 rules at confidence 1 and lowering the threshold only adds rules further down the list.

On the full 150-row file the bin labels are ’(-inf-2.966667]’ for petallength and ’(-inf-0.9]’ for petalwidth, and the top rules are the same pairs with count 50: petalwidth='(-inf-0.9]' 50 ==> class=Iris-setosa 50 conf:(1), petallength='(-inf-2.966667]' 50 ==> class=Iris-setosa 50 conf:(1), and both directions between the two petal bins. Every setosa has petal width at most 0.6, so the lowest bin is exactly the setosa class.

iris sample with the default 10 bins (computed):

Minimum support: 0.3 (9 instances)
Minimum metric <confidence>: 0.9
Number of cycles performed: 14

Generated sets of large itemsets:

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

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

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

Best rules found:

 1. class=Iris-setosa 10 ==> petallength='(-inf-1.83]' 10    <conf:(1)> lift:(3) lev:(0.22) [6] conv:(6.67)
 2. petallength='(-inf-1.83]' 10 ==> class=Iris-setosa 10    <conf:(1)> lift:(3) lev:(0.22) [6] conv:(6.67)
 3. petalwidth='(-inf-0.34]' 9 ==> petallength='(-inf-1.83]' 9    <conf:(1)> lift:(3) lev:(0.2) [6] conv:(6)
 4. petalwidth='(-inf-0.34]' 9 ==> class=Iris-setosa 9    <conf:(1)> lift:(3) lev:(0.2) [6] conv:(6)
 5. petalwidth='(-inf-0.34]' class=Iris-setosa 9 ==> petallength='(-inf-1.83]' 9    <conf:(1)> lift:(3) lev:(0.2) [6] conv:(6)
 6. petallength='(-inf-1.83]' petalwidth='(-inf-0.34]' 9 ==> class=Iris-setosa 9    <conf:(1)> lift:(3) lev:(0.2) [6] conv:(6)
 7. petalwidth='(-inf-0.34]' 9 ==> petallength='(-inf-1.83]' class=Iris-setosa 9    <conf:(1)> lift:(3) lev:(0.2) [6] conv:(6)
 8. petallength='(-inf-1.83]' 10 ==> petalwidth='(-inf-0.34]' 9    <conf:(0.9)> lift:(3) lev:(0.2) [6] conv:(3.5)
 9. class=Iris-setosa 10 ==> petalwidth='(-inf-0.34]' 9    <conf:(0.9)> lift:(3) lev:(0.2) [6] conv:(3.5)
10. petallength='(-inf-1.83]' class=Iris-setosa 10 ==> petalwidth='(-inf-0.34]' 9    <conf:(0.9)> lift:(3) lev:(0.2) [6] conv:(3.5)

glass (214 rows, 9 numeric attributes, Discretize bins 3, Apriori defaults; expected shape, not run here): Ba is 0 in 176 rows and Fe is 0 in 144 rows, so the lowest Ba and Fe bins are the most frequent items and the top rules connect them, for example Fe='(-inf-0.17]' ==> Ba='(-inf-1.05]' with confidence near 1 and support above 0.6. With lowerBoundMinSupport 0.5 and minMetric 0.95 only rules among Ba, Fe and K bins remain, and no rule mentions Type, because the largest class (build wind non-float, 76 rows) is only 36 percent of the data.

Explanation

Support and confidence pull in opposite directions. Lowering minMetric from 0.9 to 0.7 admits weaker rules such as windy=FALSE ==> play=yes (conf 0.75), whose lift 1.17 says it is barely better than guessing play=yes outright (9 of 14). Raising lowerBoundMinSupport to 0.3 removes every rule about temperature=hot or outlook=sunny with play=no, because those itemsets cover only 2 or 3 rows.

Discretisation decides what the rules can say. With 3 bins, the iris sample gives 12 large single items and 12 pairs, and the rules read as class descriptions (petallength small and petalwidth small mean setosa). With 10 bins each bin holds fewer rows, so only 5 items reach the 30 percent support and the rules describe the same setosa cluster with narrower intervals ((-inf-1.83], (-inf-0.34]) and lower confidence for the reverse direction (0.9 instead of 1). Finer bins give more precise but rarer items; coarser bins give frequent but vaguer items. Equal-frequency bins (useEqualFrequency True) make every item about equally frequent, which removes the tall-bin effect seen on glass.

Interesting rules are the ones with confidence near 1 and lift well above 1: temperature=cool ==> humidity=normal (lift 2) is a real dependency in the weather data; outlook=overcast ==> play=yes (lift 1.56) is the rule a decision tree also finds.

Question 8

Problem Statement

Write in lab record

Implement the Apriori Algorithm to find the association rules in contactlenses.arff dataset.

Solution

Write in lab record

Steps

Read the ARFF: the header gives the attribute names and the value list, each data row becomes a transaction whose items are the (attribute, value) pairs.
Level 1: count every item; keep those with count at least the minimum support count. For support 0.2 on 24 rows the count is $⌊ 0.2 \times 24 + 0.5 ⌋ = 5$ (WEKA rounds 4.8 to 5).
Level k: join two large (k-1)-itemsets that differ in one item, keep the candidate only if all its (k-1)-subsets are large (the Apriori pruning), then scan the transactions to count it.
Stop when a level is empty.
Rules: from every large itemset of size 2 or more, try each non-empty proper subset as the consequent; confidence is the itemset count divided by the premise count; keep the rule when confidence is at least 0.9.
Rank by confidence, then by support, print the top 10 in WEKA’s format.
Run: python3 apriori.py contact-lenses.arff -M 0.2 -U 0.2 fixes the support at 0.2 for one pass. python3 apriori.py contact-lenses.arff repeats WEKA’s default search from 1.0 downwards.

Program

Lab record: every tab is one file of the answer. Write all of them.

apriori.pypython

#!/usr/bin/env python3
"""Apriori association-rule miner that behaves like weka.associations.Apriori.

Standard library only. Reads an ARFF file with nominal attributes (numeric
attributes are discretised into equal-width bins first, like WEKA's
unsupervised Discretize filter) and prints the same blocks WEKA prints.

Usage:
  python3 apriori.py FILE.arff [-N rules] [-C minMetric] [-T 0|1] [-D delta]
                     [-U upperBoundMinSupport] [-M lowerBoundMinSupport]
                     [-B bins] [-R attr,attr] [-I]

  -T 0 ranks by confidence (default), -T 1 by lift.  -I prints the large
  itemsets.  -R removes attributes by 1-based index before mining (like the
  Remove filter).  -B is the number of bins for numeric attributes.

Examples:
  python3 apriori.py contact-lenses.arff                   # WEKA defaults
  python3 apriori.py contact-lenses.arff -M 0.2 -U 0.2 -I  # one pass at 0.2
  python3 apriori.py iris-sample.arff -B 3 -M 0.3
"""
import argparse
import itertools
import re
from collections import Counter
from decimal import ROUND_HALF_UP, Decimal


def read_arff(path):
    """Return (relation, [(name, values-or-None)], rows). '?' marks missing."""
    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(",")])
                continue
            low = line.lower()
            if low.startswith("@relation"):
                relation = line.split(None, 1)[1].strip("'\"")
            elif low.startswith("@attribute"):
                m = re.match(r"@attribute\s+('[^']*'|\"[^\"]*\"|\S+)\s+(.*)", line, re.I)
                name, typ = m.group(1).strip("'\""), m.group(2).strip()
                if typ.startswith("{"):
                    attrs.append((name, [v.strip().strip("'\"") for v in typ.strip("{}").split(",")]))
                else:
                    attrs.append((name, None))  # numeric / real / integer
            elif low.startswith("@data"):
                in_data = True
    return relation, attrs, rows


def fmt(x, places=6):
    """WEKA's Utils.doubleToString: rounds half up, trailing zeros trimmed."""
    s = str(Decimal(repr(x)).quantize(Decimal(1).scaleb(-places), ROUND_HALF_UP)).rstrip("0").rstrip(".")
    return s if s not in ("", "-0") else "0"


def discretize(attrs, rows, bins):
    """Equal-width bins with WEKA's labels: '(-inf-c1]', '(c1-c2]', '(cn-inf)'."""
    for j, (name, values) in enumerate(attrs):
        if values is not None:
            continue
        nums = [float(r[j]) for r in rows if r[j] != "?"]
        lo, hi = min(nums), max(nums)
        width = (hi - lo) / bins
        cuts = [lo + i * width for i in range(1, bins)]
        labels = ["'(-inf-%s]'" % fmt(cuts[0])]
        labels += ["'(%s-%s]'" % (fmt(a), fmt(b)) for a, b in zip(cuts, cuts[1:])]
        labels.append("'(%s-inf)'" % fmt(cuts[-1]))
        for r in rows:
            if r[j] == "?":
                continue
            v, k = float(r[j]), 0
            while k < len(cuts) and v > cuts[k]:
                k += 1
            r[j] = labels[k]
        attrs[j] = (name, labels)
    return attrs, rows


def large_itemsets(trans, min_count):
    """Level-wise Apriori. Returns [L1, L2, ...] as dicts itemset -> count."""
    counts = Counter(i for t in trans for i in t)
    levels = [{frozenset([i]): c for i, c in counts.items() if c >= min_count}]
    while levels[-1]:
        prev = levels[-1]
        cands = set()
        for a, b in itertools.combinations(sorted(prev, key=sorted), 2):
            u = a | b
            if len(u) == len(a) + 1 and all(frozenset(s) in prev for s in itertools.combinations(u, len(a))):
                cands.add(u)
        # ponytail: O(|L|^2) join, fine for lab-sized files; prefix join if it ever matters
        counts = {c: sum(1 for t in trans if c <= t) for c in cands}
        levels.append({c: n for c, n in counts.items() if n >= min_count})
    return levels[:-1]


def rules_from(levels, n, min_metric, metric_type):
    """All rules X ==> Y from every large itemset, kept when metric >= min_metric.
    Generation order matches WEKA: itemsets in attribute order, consequents of
    size 1 first, then size 2, ... (this fixes the tie order in the output)."""
    supp = {k: v for lev in levels for k, v in lev.items()}
    out = []
    for lev in levels[1:]:
        for iset in sorted(lev, key=sorted):
            items = sorted(iset)
            for size in range(1, len(items)):
                for cons in itertools.combinations(items, size):
                    cons = frozenset(cons)
                    prem = iset - cons
                    nxy, nx, ny = supp[iset], supp[prem], supp[cons]
                    conf = nxy / nx
                    lift = conf / (ny / n)
                    lev_ = nxy / n - (nx / n) * (ny / n)
                    conv = (nx * (n - ny) / n) / (nx - nxy + 1)  # WEKA adds 1 to the denominator
                    metric = conf if metric_type == 0 else lift
                    if metric >= min_metric - 1e-9:
                        out.append((prem, cons, nx, nxy, conf, lift, lev_, conv))
    return out


def item_str(attrs, item):
    j, vi = item
    return f"{attrs[j][0]}={attrs[j][1][vi]}"


def main():
    p = argparse.ArgumentParser()
    p.add_argument("file")
    p.add_argument("-N", type=int, default=10, help="numRules")
    p.add_argument("-C", type=float, default=0.9, help="minMetric")
    p.add_argument("-T", type=int, default=0, help="metricType 0=confidence 1=lift")
    p.add_argument("-D", type=float, default=0.05, help="delta")
    p.add_argument("-U", type=float, default=1.0, help="upperBoundMinSupport")
    p.add_argument("-M", type=float, default=0.1, help="lowerBoundMinSupport")
    p.add_argument("-B", type=int, default=10, help="bins for numeric attributes")
    p.add_argument("-R", default="", help="1-based attribute indices to remove")
    p.add_argument("-I", action="store_true", help="outputItemSets")
    a = p.parse_args()

    relation, attrs, rows = read_arff(a.file)
    if a.R:
        drop = {int(i) - 1 for i in a.R.split(",")}
        attrs = [x for j, x in enumerate(attrs) if j not in drop]
        rows = [[v for j, v in enumerate(r) if j not in drop] for r in rows]
    attrs, rows = discretize(attrs, rows, a.B)
    # items are (attribute index, value index) so ordering follows the ARFF declaration
    trans = [frozenset((j, attrs[j][1].index(v)) for j, v in enumerate(r) if v != "?") for r in rows]
    n = len(trans)

    metric_name = ["confidence", "lift"][a.T]
    print("=== Run information ===\n")
    print(f"Scheme:       weka.associations.Apriori -N {a.N} -T {a.T} -C {a.C} -D {a.D} -U {a.U} -M {a.M} -S -1.0 -c -1")
    print(f"Relation:     {relation}")
    print(f"Instances:    {n}")
    print(f"Attributes:   {len(attrs)}")
    for name, _ in attrs:
        print(f"              {name}")
    print("=== Associator model (full training set) ===\n\n\nApriori\n=======\n")

    # WEKA: start at upper - delta, lower the support each cycle until numRules
    # rules pass minMetric or the lower bound is reached.
    min_support, cycles = round(a.U - a.D, 10), 0
    if min_support < a.M:
        min_support = a.M
    while True:
        need = int(min_support * n + 0.5)
        levels = large_itemsets(trans, need)
        rules = rules_from(levels, n, a.C, a.T)
        cycles += 1
        nxt = round(min_support - a.D, 10)
        if len(rules) >= a.N or nxt < a.M - 1e-9 or nxt <= 0:
            break
        min_support = nxt

    print(f"Minimum support: {fmt(min_support, 2)} ({need} instances)")
    print(f"Minimum metric <{metric_name}>: {fmt(a.C, 2)}")
    print(f"Number of cycles performed: {cycles}\n")
    print("Generated sets of large itemsets:\n")
    for k, lev in enumerate(levels, 1):
        print(f"Size of set of large itemsets L({k}): {len(lev)}\n")
        if a.I:
            print(f"Large Itemsets L({k}):")
            for iset in sorted(lev, key=sorted):
                print(" ".join(item_str(attrs, i) for i in sorted(iset)), lev[iset])
            print()

    # rank: metric descending, then support descending, then generation order
    key = (lambda r: (-r[4], -r[3])) if a.T == 0 else (lambda r: (-r[5], -r[3]))
    rules.sort(key=key)
    print("Best rules found:\n")
    for i, (prem, cons, nx, nxy, conf, lift, lev_, conv) in enumerate(rules[: a.N], 1):
        lhs = " ".join(item_str(attrs, x) for x in sorted(prem))
        rhs = " ".join(item_str(attrs, x) for x in sorted(cons))
        m = [f"conf:({fmt(conf, 2)})", f"lift:({fmt(lift, 2)})",
             f"lev:({fmt(lev_, 2)}) [{int(round(lev_ * n, 6))}]", f"conv:({fmt(conv, 2)})"]
        m[a.T] = "<" + m[a.T] + ">"
        print(f"{i:2d}. {lhs} {nx} ==> {rhs} {nxy}    {' '.join(m)}")


if __name__ == "__main__":
    main()

contact-lenses.arfftext

% contact-lenses.arff - the 24-row dataset shipped in WEKA's data folder
@relation contact-lenses

@attribute age {young, pre-presbyopic, presbyopic}
@attribute spectacle-prescrip {myope, hypermetrope}
@attribute astigmatism {no, yes}
@attribute tear-prod-rate {reduced, normal}
@attribute contact-lenses {soft, hard, none}

@data
young,myope,no,reduced,none
young,myope,no,normal,soft
young,myope,yes,reduced,none
young,myope,yes,normal,hard
young,hypermetrope,no,reduced,none
young,hypermetrope,no,normal,soft
young,hypermetrope,yes,reduced,none
young,hypermetrope,yes,normal,hard
pre-presbyopic,myope,no,reduced,none
pre-presbyopic,myope,no,normal,soft
pre-presbyopic,myope,yes,reduced,none
pre-presbyopic,myope,yes,normal,hard
pre-presbyopic,hypermetrope,no,reduced,none
pre-presbyopic,hypermetrope,no,normal,soft
pre-presbyopic,hypermetrope,yes,reduced,none
pre-presbyopic,hypermetrope,yes,normal,none
presbyopic,myope,no,reduced,none
presbyopic,myope,no,normal,none
presbyopic,myope,yes,reduced,none
presbyopic,myope,yes,normal,hard
presbyopic,hypermetrope,no,reduced,none
presbyopic,hypermetrope,no,normal,soft
presbyopic,hypermetrope,yes,reduced,none
presbyopic,hypermetrope,yes,normal,none

Output

python3 apriori.py contact-lenses.arff -M 0.2 -U 0.2 (support 0.2, confidence 0.9, one pass):

Minimum support: 0.2 (5 instances)
Minimum metric <confidence>: 0.9
Number of cycles performed: 1

Generated sets of large itemsets:

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

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

Size of set of large itemsets L(3): 6

Best rules found:

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

Cross-check against WEKA. Explorer, Open file contact-lenses.arff, Associate, Apriori with defaults, Start prints:

Minimum support: 0.2 (5 instances)
Minimum metric <confidence>: 0.9
Number of cycles performed: 16

Generated sets of large itemsets:

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

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

Size of set of large itemsets L(3): 6

Best rules found:

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

Check	Python, one pass at 0.2	WEKA defaults
Minimum support	0.2 (5 instances)	0.2 (5 instances), reached after 16 cycles from 1.0
L(1), L(2), L(3)	11, 21, 6	11, 21, 6
Rules with confidence at least 0.9	10	10
Rule 1	tear-prod-rate=reduced 12 ==> contact-lenses=none 12	same
Rules 2 to 5	the four 2-item premises containing reduced, support 6	same four; WEKA may print them in a different order among themselves
Rules 6 to 10	the five soft rules with support 5	same

The only difference WEKA can show is the order of rules that tie on both confidence and support; the sets are identical.

Explanation

The program is the textbook algorithm. large_itemsets is the level-wise pass: Counter gives L1, itertools.combinations over the previous level joins pairs, the all(... in prev ...) test is the pruning step that throws away a candidate whose subset is not large, and one scan of the transactions counts what is left. Pruning matters even here: from 21 large pairs there are 210 possible joins, but only candidates whose three pairs are all large get counted, and only 6 survive. rules_from walks every large itemset and every consequent, and the confidence test $conf (X \Rightarrow Y) = \frac{| X \cup Y |}{| X |}$ is one division. The support-lowering loop in main reproduces WEKA’s search: start at upperBoundMinSupport minus delta, mine, and lower the support until numRules rules pass or lowerBoundMinSupport is hit; 16 steps of 0.05 from 0.95 land on 0.2, which is why WEKA prints 16 cycles.

Viva Questions

Do not copy. Read for understanding and the viva

Q: Why does WEKA report Minimum support 0.2 when the lower bound was 0.1? A: It starts at 1.0 and lowers by delta 0.05 each cycle; at 0.2 it already had 10 rules, so it stopped.

Q: What is the Apriori property? A: Every subset of a frequent itemset is frequent, so a candidate with an infrequent subset can be dropped without counting it.

Q: Why must numeric attributes be discretised before Apriori? A: An item is an attribute-value pair; a continuous value would be its own item with support 1 of N.

Q: What does the number after the arrow mean in tear-prod-rate=reduced 12 ==> contact-lenses=none 12? A: Twelve rows contain both sides; the 12 before the arrow is the premise count; confidence is 12 divided by 12.

Q: What does lift 4 on rule 10 tell you? A: The consequent (astigmatism=no and tear-prod-rate=normal) occurs in 6 of 24 rows, 25 percent; among soft-lens rows it occurs 100 percent, four times as often.

Q: How does the number of bins change the rules? A: More bins mean rarer, more precise items; fewer rules pass the support threshold and their intervals are narrower.

Q: Why does the equal-width Discretize label read ’(-inf-0.9]’ and not ‘[0.1-0.9]’? A: WEKA makes the first and last bins open so that unseen values outside the training range still fall into a bin.

Common Mistakes

Do not copy. Read for understanding and the viva

Running Apriori on iris or glass without Discretize; WEKA greys out Start because Apriori cannot handle numeric attributes.
Setting lowerBoundMinSupport above upperBoundMinSupport, which gives no cycles and no rules.
Reading conf:(1) as proof of a strong pattern when the support is 2 rows out of 14.
Confusing the item count in the rule (rows matched) with the support fraction; divide by the number of instances.
Forgetting that Discretize on first-last leaves the nominal class alone, then reporting that the class was not binned as an error.

Formula Sheet

Do not copy. Read for understanding and the viva

Association rules

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

support (X \Rightarrow Y) = \frac{| X \cup Y |}{N}, confidence (X \Rightarrow Y) = \frac{| X \cup Y |}{| X |}, lift (X \Rightarrow Y) = \frac{confidence (X \Rightarrow Y)}{support (Y)}

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}$ :

H (S) = - \sum_{i = 1}^{c} p_{i} \log_{2} p_{i}, Gain (S, A) = H (S) - \sum_{v \in values (A)} \frac{| S_{v} |}{| S |} H (S_{v}), Gini (S) = 1 - \sum_{i = 1}^{c} p_{i}^{2}

ID3 splits on the attribute with the highest gain; J48 (C4.5) uses the gain ratio $Gain (S, A) / SplitInfo (S, A)$ where $SplitInfo (S, A) = - \sum_{v} \frac{| S_{v} |}{| S |} \log_{2} \frac{| S_{v} |}{| S |}$ .

Classifier evaluation

From the confusion matrix with true positives $T P$ , false positives $F P$ , false negatives $F N$ , true negatives $T N$ :

Accuracy = \frac{T P + T N}{T P + T N + F P + F N}, Precision = \frac{T P}{T P + F P}, Recall = \frac{T P}{T P + F N}, F_{1} = \frac{2 \cdot Precision \cdot Recall}{Precision + Recall}

Kappa compares observed agreement $p_{o}$ (accuracy) with the agreement expected by chance $p_{e}$ :

κ = \frac{p_{o} - p_{e}}{1 - p_{e}}, p_{e} = \sum_{i} \frac{({row}_{i} total) ({column}_{i} total)}{N^{2}}

The ROC curve plots true positive rate $T P / (T P + F N)$ against false positive rate $F P / (F P + T N)$ ; the area under it (AUC) is 0.5 for guessing and 1.0 for a perfect classifier.

Naive Bayes and k-nearest neighbour

P (C | x_{1}, \dots, x_{n}) \propto P (C) \prod_{i = 1}^{n} P (x_{i} | C)

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

d (𝐚, 𝐛) = \sqrt{\sum_{i = 1}^{n} {(a_{i} - b_{i})}^{2}}

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

Linear regression

\hat{y} = β_{0} + β_{1} x, β_{1} = \frac{\sum (x_{i} - \overline{x}) (y_{i} - \overline{y})}{\sum {(x_{i} - \overline{x})}^{2}}, β_{0} = \overline{y} - β_{1} \overline{x}

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 $μ_{j}$ :

S S E = \sum_{j = 1}^{k} \sum_{𝐱 \in C_{j}} {‖ 𝐱 - μ_{j} ‖}^{2}, μ_{j} = \frac{1}{| C_{j} |} \sum_{𝐱 \in C_{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 $minPts$ points lie within radius $ε$ ; clusters grow from core points, and points reachable from none are noise.

Session Summary

Write in lab record

Question 7: unsupervised filters catalogued with menu paths; Apriori run on weather.nominal (defaults and 0.3 with 0.7), on iris with 3 and 10 bins and on glass; rules interpreted and the effect of bin count recorded
Question 8: apriori.py written and run on contact-lenses.arff at support 0.2 and confidence 0.9; L1, L2, L3 = 11, 21, 6 and all 10 rules match WEKA’s default output