Association Rules

The previous lesson asked whether a row stands alone and looked for the answer in five numeric columns. Subscriber records have one more side that is not a number: which events occur together in that subscriber within the period. The question keeps its form: is the joint occurrence of two events a finding, or can it already be explained by how frequent the two are separately.

Association rules answer this question with three measures, and one of them misleads when taken alone. The number of the lesson is how many of the rules chosen by confidence come only from a frequent item; its baseline is the support that comes out when the items are matched to each other at random.

• DR36. The set is the fictional subscriber table of the Introduction to Machine Learning, Data Preparation and Feature Engineering, and Supervised Learning courses, seed 20260218, 1,329 subscribers. Each subscriber is read as an itemset: the service records that occur in that subscriber within the period.
• DR37. The dependencies are deliberately placed in the generator, and which of them is real is known only for measurement; no measure sees this information.
• DR38. Three measures: support, the share of the baskets that contain the itemset; confidence, the share of the baskets containing the antecedent that also contain the consequent; lift, the confidence divided by the support of the consequent. Lift is read as a departure from 1; 1 is the absence of association.
• DR39. The baseline is the support that random matching produces: the column of each item is shuffled separately across the baskets, the frequencies are kept, and the bond of occurring together is broken.
• DR40. This lesson builds only the measures of extracting rules; which rule will be shown to whom is left to the Reinforcement Learning and Recommender Systems course.

Baskets and Item Supports

# COMMON — FICTIONAL. The subscriber table of the Introduction to Machine Learning, Data Preparation and Feature Engineering, and Supervised Learning courses is rebuilt with the same seed; this time the
# service records of each subscriber within the period are kept as an ITEMSET.
# The dependencies are PLACED in the generator ON PURPOSE and are known only for measurement.
SEED, RAW, M32 = 20260218, 1400, 0xFFFFFFFF


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


SUBSCRIBERS = []
for i in range(RAW):
    r = rng(SEED + i)
    r(), r(), r()          # region, household and satisfaction are not read in this lesson
    if r() >= 0.046:
        SUBSCRIBERS.append(10001 + i)

# (item, condition item, probability when the condition holds, probability when it does not)
TABLE = [("mobile_notification", None, 0.91, 0.91),        # independent, very frequent
         ("outage_notification", None, 0.55, 0.55),        # independent, very frequent
         ("delay", None, 0.22, 0.22),
         ("installment_plan", "delay", 0.58, 0.04),        # placed dependency
         ("auto_payment", "delay", 0.13, 0.47),            # placed inverse dependency
         ("objection", None, 0.16, 0.16),
         ("call_center", "objection", 0.90, 0.58),         # weak dependency, frequent item
         ("address_change", None, 0.08, 0.08),
         ("meter_replacement", "address_change", 0.36, 0.09),
         ("field_visit", "meter_replacement", 0.86, 0.19),
         ("tariff_change", None, 0.12, 0.12),
         ("illicit_use_report", None, 0.05, 0.05)]
ITEMS = [t[0] for t in TABLE]

BASKETS = []
for id in SUBSCRIBERS:
    r, s = rng(SEED + 37000 + id), set()
    for item, cond, p1, p0 in TABLE:
        if r() < (p1 if cond is None or cond in s else p0):
            s.add(item)
    BASKETS.append(s)

N = len(BASKETS)
D1 = {o: sum(1 for s in BASKETS if o in s) / N for o in ITEMS}
print(f"fictional: {N} subscriber baskets, {len(ITEMS)} items; "
      f"mean {sum(len(s) for s in BASKETS) / N:.2f} items per basket")
for o in sorted(ITEMS, key=lambda x: -D1[x]):
    print(f"  {o:<20} support {D1[o]:.4f}")

fictional: 1329 subscriber baskets, 12 items; mean 3.68 items per basket
  mobile_notification  support 0.9120
  call_center          support 0.6388
  outage_notification  support 0.5403
  auto_payment         support 0.3973
  field_visit          support 0.2671
  delay                support 0.2220
  installment_plan     support 0.1670
  objection            support 0.1497
  meter_replacement    support 0.1332
  tariff_change        support 0.1151
  address_change       support 0.0835
  illicit_use_report   support 0.0512

The supports are spread over a wide range: the most frequent item is in 0.9120 of the baskets, the rarest in 0.0512. This distribution sets the trap of the next section.

Confidence Alone

# Extracting rules: one or two items in the antecedent, one item in the consequent. The support floor
# is a decision and is fixed before measuring.
from itertools import combinations

SUPPORT_FLOOR, CONFIDENCE_FLOOR = 0.05, 0.50


def support(itemset):
    return sum(1 for s in BASKETS if itemset <= s) / N


RULES = []
antecedents = [frozenset([o]) for o in ITEMS] + \
              [frozenset(c) for c in combinations(ITEMS, 2)]
for X in antecedents:
    dx = support(X)
    if dx < SUPPORT_FLOOR:
        continue
    for y in ITEMS:
        if y in X:
            continue
        d = support(X | {y})
        if d < SUPPORT_FLOOR:
            continue
        g = d / dx
        RULES.append({"X": X, "y": y, "support": d, "confidence": g,
                      "lift": g / D1[y]})

SINGLE = sum(1 for k in RULES if len(k["X"]) == 1)
near = [k for k in RULES if abs(k["lift"] - 1) <= 0.05]
print(f"support floor {SUPPORT_FLOOR:.2f} and above: {len(RULES)} rules "
      f"({SINGLE} single-item antecedents, {len(RULES) - SINGLE} two-item)")
print(f"rules with lift within 0.05 of 1: {len(near)} "
      f"({len(near) / len(RULES):.4f})\n")


def show(title, ranked, count=8):
    print(title)
    print(f"  {'rule':<46} {'support':>7} {'confidence':>10} {'lift':>9}")
    for k in ranked[:count]:
        name = " + ".join(sorted(k["X"])) + " -> " + k["y"]
        print(f"  {name:<46} {k['support']:>7.4f} {k['confidence']:>10.4f} "
              f"{k['lift']:>9.4f}")


by_confidence = sorted(RULES, key=lambda k: (-k["confidence"], sorted(k["X"]), k["y"]))
show("top six rules by confidence", by_confidence, 6)
top = [k for k in by_confidence if k["confidence"] >= CONFIDENCE_FLOOR]
frequent = sum(1 for k in top if abs(k["lift"] - 1) <= 0.05)
print(f"\nthere are {len(top)} rules with confidence {CONFIDENCE_FLOOR:.2f} and above; "
      f"{frequent} of them have a lift within 0.05 of 1 ({frequent / len(top):.4f})")
last = {}
for k in top:
    last[k["y"]] = last.get(k["y"], 0) + 1
print("  by consequent item: " + ", ".join(
    f"{o} {last[o]} (support {D1[o]:.4f})" for o in sorted(last, key=lambda x: -last[x])))

single = [k for k in RULES if len(k["X"]) == 1]
show("\ntop four rules by lift (single-item antecedent)",
     sorted(single, key=lambda k: (-k["lift"], sorted(k["X"]), k["y"])), 4)
lowest = min(single, key=lambda k: (k["lift"], k["confidence"], sorted(k["X"]), k["y"]))
print(f"  lowest-lift rule: {' + '.join(sorted(lowest['X']))} -> "
      f"{lowest['y']}, support {lowest['support']:.4f}, "
      f"confidence {lowest['confidence']:.4f}, lift {lowest['lift']:.4f}")

support floor 0.05 and above: 166 rules (64 single-item antecedents, 102 two-item)
rules with lift within 0.05 of 1: 115 (0.6928)

top six rules by confidence
  rule                                           support confidence      lift
  outage_notification + tariff_change -> mobile_notification  0.0662     0.9565    1.0489
  tariff_change -> mobile_notification            0.1076     0.9346    1.0249
  auto_payment + objection -> mobile_notification  0.0602     0.9302    1.0200
  call_center + tariff_change -> mobile_notification  0.0700     0.9300    1.0198
  address_change -> mobile_notification           0.0775     0.9279    1.0175
  objection -> mobile_notification                0.1384     0.9246    1.0139

there are 97 rules with confidence 0.50 and above; 75 of them have a lift within 0.05 of 1 (0.7732)
  by consequent item: mobile_notification 32 (support 0.9120), call_center 28 (support 0.6388), outage_notification 25 (support 0.5403), field_visit 4 (support 0.2671), delay 4 (support 0.2220), installment_plan 4 (support 0.1670)

top four rules by lift (single-item antecedent)
  rule                                           support confidence      lift
  installment_plan -> delay                       0.1279     0.7658    3.4498
  delay -> installment_plan                       0.1279     0.5763    3.4498
  field_visit -> meter_replacement                0.1159     0.4338    3.2572
  meter_replacement -> field_visit                0.1159     0.8701    3.2572
  lowest-lift rule: outage_notification -> field_visit, support 0.1362, confidence 0.2521, lift 0.9437

All six of the top six rules by confidence have the same item as the consequent: the record that occurs in 0.9120 of the baskets. Their confidences are 0.9246–0.9565 and their antecedents have nothing to do with each other. Whichever antecedent is chosen, the confidence settles around 0.91; the lift column says this, between 1.0139 and 1.0489.

There are 97 rules with confidence above 0.50 and 75 of them have a lift closer to 1 than 0.05: 0.7732. By consequent item, 32, 28 and 25 rules point to the three most frequent items — 85 of the 97. Raising the threshold does not fix this; as the threshold rises, only frequent items can pass it.

Sorting by lift gives another list: two pairs in the top four, each pair in both directions — installment plan and delay 3.4498, meter replacement and field visit 3.2572. In the same rows confidence is read as asymmetric and lift as symmetric: the confidence from delay to installment plan is 0.5763, in the opposite direction 0.7658, and the lift is the same in both. The lowest lift is 0.9437; a lift that falls below 1 says that occurring together is rarer than chance.

The Random Matching Baseline

# BASELINE: the support that random matching produces. The column of each item is
# shuffled separately across the baskets; item frequencies are kept exactly,
# the bond of occurring together is broken. Lift is the closed form of this baseline.
BIT = {o: 1 << b for b, o in enumerate(ITEMS)}
COLUMNS = [[1 if o in s else 0 for s in BASKETS] for o in ITEMS]
REPEATS = 60


def superset_sums(masks):
    # For each pattern, the number of baskets that cover it: a single 12-bit pass.
    h = [0] * (1 << len(ITEMS))
    for m in masks:
        h[m] += 1
    for b in range(len(ITEMS)):
        for m in range(len(h)):
            if not m & (1 << b):
                h[m] += h[m | (1 << b)]
    return h


def shuffled(seed):
    rr, new = rng(seed), [0] * N
    for b, col in enumerate(COLUMNS):
        c = list(col)
        for i in range(N - 1, 0, -1):
            j = int(rr() * (i + 1))
            c[i], c[j] = c[j], c[i]
        for i in range(N):
            if c[i]:
                new[i] |= 1 << b
    return new


RANDOM_RUNS = [superset_sums(shuffled(SEED + 41000 + t)) for t in range(REPEATS)]
EXAMPLES = (("delay", "installment_plan"), ("meter_replacement", "field_visit"),
            ("tariff_change", "mobile_notification"), ("objection", "mobile_notification"))
pattern = lambda k: sum(BIT[o] for o in k["X"]) | BIT[k["y"]]
random_support = lambda k: [R[pattern(k)] / N for R in RANDOM_RUNS]

print(f"{REPEATS} shuffles: the support random matching produces\n")
print(f"  {'rule':<38} {'real':>7} {'random':>9} {'highest':>7} {'lift':>9}")
for k in sorted((k for k in RULES if len(k["X"]) == 1
                 and (sorted(k["X"])[0], k["y"]) in EXAMPLES),
                key=lambda k: -k["lift"]):
    r = random_support(k)
    print(f"  {sorted(k['X'])[0] + ' -> ' + k['y']:<38} {k['support']:>7.4f} "
          f"{sum(r) / len(r):>9.4f} {max(r):>7.4f} {k['lift']:>9.4f}")

OUTSIDE = {i: k["support"] > max(random_support(k)) or k["support"] < min(random_support(k))
           for i, k in enumerate(RULES)}
print(f"\n{len(RULES)} rules separated by two criteria at once")
print(f"  {'':<22} {'inside range':>14} {'outside range':>15}")
for name, cond in (("lift near 1", True), ("lift far from 1", False)):
    g = [i for i, k in enumerate(RULES) if (abs(k["lift"] - 1) <= 0.05) == cond]
    inside = sum(1 for i in g if not OUTSIDE[i])
    print(f"  {name:<22} {inside:>14} {len(g) - inside:>15}")

dt = support(frozenset(["delay", "auto_payment"]))
print(f"\na dependency that stays under the support floor: delay + auto_payment "
      f"support {dt:.4f}, lift {dt / (D1['delay'] * D1['auto_payment']):.4f}; "
      f"since the floor is {SUPPORT_FLOOR:.2f} it never enters the rule list")

60 shuffles: the support random matching produces

  rule                                      real    random highest      lift
  delay -> installment_plan               0.1279    0.0362  0.0467    3.4498
  meter_replacement -> field_visit        0.1159    0.0354  0.0451    3.2572
  tariff_change -> mobile_notification    0.1076    0.1043  0.1099    1.0249
  objection -> mobile_notification        0.1384    0.1363  0.1407    1.0139

166 rules separated by two criteria at once
                           inside range   outside range
  lift near 1                       107               8
  lift far from 1                    26              25

a dependency that stays under the support floor: delay + auto_payment support 0.0316, lift 0.3584; since the floor is 0.05 it never enters the rule list

The baseline is in the first two rows. Delay and installment plan occur together in 0.1279 of the baskets; when the columns are shuffled, the same pair falls to a mean of 0.0362 and the highest of sixty shuffles is 0.0467. The difference is 0.0917 and it comes from the data.

The last two rows show the opposite. The rule with a confidence of 0.9246 has a support of 0.1384; random matching carries the same pair to a mean of 0.1363 and a highest of 0.1407. The real support is inside the random range; the rule takes its high confidence entirely from the frequency of the consequent itself. Lift is the closed form of this baseline: dividing by the product of the supports is dividing by what shuffling produces on average.

When the two criteria are crossed, the 166 rules are spread over four cells: of the 115 rules with a lift near 1, 107 are inside the random range, and of the 51 rules with a lift far from 1, 26 are as well. In total 133 rules cannot be told apart from what random matching produces. The 8 rows in the opposite direction are meaningful too: as the support grows the range narrows, and even a lift of 1.04 falls outside. A departure of the lift is not enough; how often the departure is produced by chance is needed as well.

The last row opens another face. The fictional dependency between delay and auto payment has a lift of 0.3584, farther from 1 than anything in the list; but since the two occur together in only 0.0316 of the baskets, it stays under the support floor and never enters the list. If the floor were 0.03, this rule would be at the top of the list.

Summary

• All six of the top six rules by confidence have as the consequent the same item that occurs in 0.9120 of the baskets; their lifts are 1.0139–1.0489.
• Of the 97 rules with confidence above 0.50, 75 have a lift closer to 1 than 0.05, and 85 have one of the three most frequent items as the consequent.
• The baseline is the support that random matching produces: the support of 0.1279 for delay and installment plan does not exceed 0.0467 in any of sixty shuffles, but the support of the rule with a confidence of 0.9246 stays inside the random range.
• 133 of the 166 rules cannot be told apart from what random matching produces.
• The support floor is a decision: a real dependency with a lift of 0.3584 stays under the floor of 0.05 because its support is 0.0316, and never enters the list.

Course Wrap-Up

The account of eleven lessons is in a single table, and each number was read from its own lesson. The triple is the same in every row, but the rows do not carry a common unit: when there are no labels, each lesson chooses its own metric. The last column writes this — in the distance and error rows the smaller is better, in the rate and score rows the larger. The difference is the number of the method minus the baseline.

Lesson	Baseline	Method’s number	Difference	Metric
Clustering 01	random assignment 5.9790	3.8910	−2.0880	within-cluster distance
Clustering 02	random assignment 5.9181	2.2570	−3.6611	within-cluster distance
Clustering 03	random assignment 6.2340	4.5419	−1.6922	within-cluster distance
Clustering 04	random flagging 1.0200	1.7551	+0.7351	neighbor distance
Clustering 05	random assignment −4.2424	−3.7755	+0.4669	fit score
Clustering 06	single cluster 0.6539	0.5235	−0.1304	agreement index
Dimensionality reduction 01	column mean 3.3411	2.7762	−0.5650	reconstruction error
Dimensionality reduction 02	column mean 3.3411	2.7464	−0.5947	reconstruction error
Dimensionality reduction 03	random layout 0.0390	0.5032	+0.4642	neighborhood preservation rate
Dimensionality reduction 04	random flagging 0.0488	0.6190	+0.5702	precision
Dimensionality reduction 05	random matching 0.0362	0.1279	+0.0917	support of the rule

The second column was produced in each lesson by a separate procedure: random assignment, single cluster, random flagging, reconstruction with the column mean, random layout, random matching. In the supervised course the baseline was ready — saying the most frequent label — here each lesson built its baseline itself. This is the rule of the course: an unlabeled result exists only as much as it departs from a random result; a clustering whose baseline is not built counts as unmeasured. Three rows cannot be read without a footnote: in Clustering 06 the 0.5235 is below its baseline, the +0.7351 of Clustering 04 comes not from the data but from the metric, the 0.5032 of Dimensionality reduction 03 is the best of six candidates and the honest range is 0.3940–0.5032.

The second claim of the course is read from the same table: in an unsupervised result there is no right answer, the choice of metric determines the answer. The number of lessons in which the answer changed when the metric was changed is ten — three definitions of similarity gave three partitions, three linkage criteria chose 3, 37 and 56 clusters at the same height, three internal validity metrics chose 3, 6 and 10; in clustering 04 two metrics gave opposite rankings, in dimensionality reduction 03 what one preserved the other threw away, and here confidence and lift produced two separate lists.

In twenty-one lessons — eleven of them unlabeled — every method worked on the assumption that the features were given. Scaling, encoding, generating and reducing were always decided by hand, and the cost of each decision was measured separately. What a procedure that also learns these decisions from the data itself gains, and what it makes invisible, was never asked. The next course, Deep Learning, opens with this question.