The Apriori Algorithm

# Apriori, run in full on the same 20 baskets: every candidate set, every count,
# the pruning step doing its work, the rules generated afterwards, and the cost
# against counting every possible itemset.
from itertools import combinations

BASKETS = [
    ("notebook", "pen", "tea"),
    ("notebook", "pen", "tea", "highlighter"),
    ("notebook", "pen", "tea"),
    ("notebook", "pen", "highlighter", "tea"),
    ("notebook", "pen", "tea"),
    ("notebook", "tea"),
    ("pen", "tea"),
    ("pen", "tea", "samosa"),
    ("tea", "samosa"),
    ("tea", "samosa"),
    ("tea", "samosa", "photocopy"),
    ("tea", "photocopy"),
    ("photocopy", "stapler", "tea"),
    ("photocopy", "stapler"),
    ("photocopy", "stapler", "tea"),
    ("notebook", "pen", "highlighter"),
    ("notebook", "highlighter", "tea"),
    ("tea",),
    ("tea", "samosa"),
    ("notebook", "pen", "tea", "samosa"),
]
SETS = [set(b) for b in BASKETS]
ITEMS = sorted({i for b in BASKETS for i in b})
n = len(BASKETS)
MINSUP = 0.15          # 3 baskets in 20
MINCONF = 0.70

counted = 0            # how many itemsets were counted against the database
passes = 0             # how many times the database was read

def count(itemset):
    global counted
    counted += 1
    s = set(itemset)
    return sum(1 for b in SETS if s <= b)

def support(itemset):
    return count(itemset) / n

print("THE PROBLEM. %d items means %d non-empty itemsets to consider:"
      % (len(ITEMS), 2 ** len(ITEMS) - 1))
print("   %s" % ", ".join(ITEMS))
print("   counting all %d against %d baskets is possible here and is not possible"
      % (2 ** len(ITEMS) - 1, n))
print("   at all in a shop with 10000 items, where the number is 2**10000.")
print()
print("THE ONE PROPERTY THAT SAVES IT: DOWNWARD CLOSURE, also called the apriori")
print("property or anti-monotonicity.")
print("   IF AN ITEMSET IS FREQUENT, EVERY SUBSET OF IT IS FREQUENT.")
print("   equivalently: if any subset is INFREQUENT, the set cannot be frequent.")
print("   the reason is one line: every basket containing the whole set contains")
print("   each of its subsets, so a subset's count is at least the set's count.")
print()
print("   checked on this data, for every frequent pair and triple:")
ok = bad = 0
for size in (2, 3):
    for c in combinations(ITEMS, size):
        s = set(c)
        cnt = sum(1 for b in SETS if s <= b)
        if cnt / n >= MINSUP:
            for k in range(1, size):
                for sub in combinations(c, k):
                    ss = set(sub)
                    subcnt = sum(1 for b in SETS if ss <= b)
                    if subcnt >= cnt:
                        ok += 1
                    else:
                        bad += 1
print("      %d subset comparisons, %d of them consistent, %d violations."
      % (ok + bad, ok, bad))
print()
print("MINIMUM SUPPORT %.2f, which is %d baskets of %d. MINIMUM CONFIDENCE %.2f."
      % (MINSUP, round(MINSUP * n), n, MINCONF))
print()

def apriori():
    global passes
    frequent = {}
    # ---- level 1: every single item -----------------------------------------
    passes += 1
    level = []
    print("LEVEL 1. count every item.")
    print("   itemset               | baskets | support | kept")
    for it in ITEMS:
        c = count([it])
        keep = c / n >= MINSUP
        print("   %-21s | %7d | %7.4f | %s" % (it, c, c / n, "yes" if keep else "NO"))
        if keep:
            level.append((it,))
            frequent[(it,)] = c
    print("   L1 has %d itemsets." % len(level))
    print()
    k = 2
    while level:
        # ---- JOIN: two frequent (k-1)-sets sharing their first k-2 items ----
        cands = []
        for i in range(len(level)):
            for j in range(i + 1, len(level)):
                a, b = level[i], level[j]
                if a[:k - 2] == b[:k - 2]:
                    cands.append(tuple(sorted(set(a) | set(b))))
        cands = sorted(set(c for c in cands if len(c) == k))
        print("LEVEL %d. JOIN gives %d candidate%s."
              % (k, len(cands), "" if len(cands) == 1 else "s"))
        # ---- PRUNE: drop any candidate with an infrequent (k-1)-subset ------
        kept, pruned = [], []
        for c in cands:
            subs = [tuple(s) for s in combinations(c, k - 1)]
            if all(s in frequent for s in subs):
                kept.append(c)
            else:
                missing = [s for s in subs if s not in frequent]
                pruned.append((c, missing[0]))
        if pruned:
            print("   PRUNE removes %d of them WITHOUT COUNTING ANYTHING:" % len(pruned))
            for c, miss in pruned:
                print("      %-30s because %s is not frequent"
                      % ("+".join(c), "+".join(miss)))
        else:
            print("   PRUNE removes none.")
        if not kept:
            print("   nothing left to count. the algorithm stops.")
            print()
            break
        passes += 1
        print("   COUNT the %d survivor%s:" % (len(kept), "" if len(kept) == 1 else "s"))
        print("   itemset                    | baskets | support | kept")
        level = []
        for c in kept:
            cnt = count(c)
            keep = cnt / n >= MINSUP
            print("   %-26s | %7d | %7.4f | %s"
                  % ("+".join(c), cnt, cnt / n, "yes" if keep else "NO"))
            if keep:
                level.append(c)
                frequent[c] = cnt
        print("   L%d has %d itemset%s." % (k, len(level), "" if len(level) == 1 else "s"))
        print()
        k += 1
    return frequent

frequent = apriori()
print("THE FREQUENT ITEMSETS, all of them:")
for size in sorted({len(k) for k in frequent}):
    rows = sorted(k for k in frequent if len(k) == size)
    print("   size %d: %s" % (size, ";  ".join("+".join(r) for r in rows)))
print()
print("THE COST, MEASURED.")
print("   itemsets counted against the database : %d" % counted)
print("   every possible non-empty itemset      : %d" % (2 ** len(ITEMS) - 1))
print("   passes over the database              : %d" % passes)
print("   apriori counted %.0f per cent of the itemsets a brute force would."
      % (100.0 * counted / (2 ** len(ITEMS) - 1)))
print("   the saving here is modest because %d items is a toy. the saving is the"
      % len(ITEMS))
print("   difference between possible and impossible on a real catalogue, and it")
print("   comes entirely from the prune step, which rejects candidates WITHOUT")
print("   LOOKING AT THE DATA AT ALL.")
print()

print("GENERATING THE RULES. for each frequent itemset of 2 or more items, every")
print("way of splitting it into a non-empty antecedent and a non-empty")
print("consequent is a candidate rule; keep those above the confidence threshold.")
print("   rule                                    | support | conf   |   lift")
rules = []
for iset, cnt in frequent.items():
    if len(iset) < 2:
        continue
    for r in range(1, len(iset)):
        for a in combinations(iset, r):
            b = tuple(x for x in iset if x not in a)
            conf = cnt / frequent[tuple(sorted(a))]
            lift = conf / (frequent[tuple(sorted(b))] / n
                           if tuple(sorted(b)) in frequent
                           else sum(1 for bk in SETS if set(b) <= bk) / n)
            rules.append((conf, lift, a, b, cnt / n))
for conf, lift, a, b, sup in sorted(rules, reverse=True):
    if conf >= MINCONF:
        print("   %-39s | %7.4f | %6.4f | %6.4f"
              % ("if " + "+".join(a) + " then " + "+".join(b), sup, conf, lift))
print()
print("   %d of the %d candidate rules pass the confidence threshold."
      % (sum(1 for c, _, _, _, _ in rules if c >= MINCONF), len(rules)))
print("   NOTE THE LIFT COLUMN. several rules above %.2f confidence have a lift"
      % MINCONF)
print("   near 1, and they are the tea rules again: high confidence because tea")
print("   is everywhere. apriori CANNOT filter these out, because it never looks")
print("   at lift. the filtering is the analyst's job and it is not optional.")
print()

print("THE THRESHOLD DECIDES EVERYTHING. the same data at four minimum supports:")
print("   minsup | baskets | frequent itemsets | largest itemset | rules above %.2f"
      % MINCONF)
for ms in (0.05, 0.10, 0.15, 0.25, 0.50):
    freq = {}
    for size in range(1, len(ITEMS) + 1):
        for c in combinations(ITEMS, size):
            s = set(c)
            cnt = sum(1 for b in SETS if s <= b)
            if cnt / n >= ms:
                freq[c] = cnt
    biggest = max((len(k) for k in freq), default=0)
    nrules = 0
    for iset, cnt in freq.items():
        if len(iset) < 2:
            continue
        for r in range(1, len(iset)):
            for a in combinations(iset, r):
                if cnt / freq[tuple(sorted(a))] >= MINCONF:
                    nrules += 1
    print("   %6.2f | %7d | %17d | %15d | %d"
          % (ms, round(ms * n), len(freq), biggest, nrules))
print("   at %.2f a 'finding' can rest on a single basket; at %.2f only tea"
      % (0.05, 0.50))
print("   itself survives and there are no rules at all.")
print("   THERE IS NO CORRECT VALUE. the threshold is a decision about how much")
print("   of the data a finding must cover before it is worth reading, and it is")
print("   made by the person, not by the algorithm.")