Imbalanced Classes

The previous lesson recorded as a side effect that dropping the missing rows took more than half of the minority class. The size difference between the classes itself was never measured. In the training set 168 of 756 subscribers are suspicious, and in the test set 61 of 252. On this table accuracy is a misleading measure, and the size of the deception can be counted: the baseline that marks no one as suspicious reads 0.7579, and the number of suspicious subscribers it catches is zero.

This lesson measures three answers to imbalance: oversampling the minority, undersampling the majority and giving a class weight. Each answer is read with two numbers at once; the theory of measures is not the subject of this course. The share of correctly flagged minority is called precision, and the share of caught minority is called recall; their definitions, how they are read against each other and the choice of a threshold are left to the Supervised Learning course. Here only raw numbers are printed.

• PS34. The set, the split, the features and the model are the same as in the earlier lessons: 756/252/252, a depth 6 decision tree, eleven features.
• PS35. Two measures are printed: accuracy and the number of suspicious subscribers caught, that is, how many of the 61 suspicious subscribers in the test set were flagged as suspicious. Two more raw numbers are written next to them: the suspicious subscribers missed, and the subscribers flagged as suspicious who are not.
• PS36. The baseline does not change: telling every subscriber the most frequent class of the training set. This procedure gives 0.7579 in accuracy and 0 in caught.
• PS37. Oversampling rewrites the minority rows as they are; no new rows are generated.
• PS38. Undersampling reduces the majority rows at random and shrinks the training set; the discarded rows do not come back.
• PS39. The class weight makes the tree compute its split criterion with weights: the contribution of each row is multiplied by its own weight. In this lesson the model code is written so that it accepts weights.
• PS40. All three answers are applied only to the training set. The test set is never oversampled, undersampled or weighted in any case; the measure is read on the real distribution.

Two Numbers, One Baseline

The setup produces the set and prints the baseline in two measures at once.

# imbalanced.py — MODEL. The fictional subscriber table is regenerated with the same seed.
import math

SEED, CANDIDATES, M32 = 20260218, 1400, 0xFFFFFFFF
REGION = [("north", 0.28, 21, 0.00), ("south", 0.22, 17, -0.10),
          ("east", 0.18, 26, 0.30), ("west", 0.14, 14, -0.05),
          ("central", 0.18, 23, 0.05)]


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


def pick(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


SUBSCRIBERS, READINGS = [], {}
for i in range(CANDIDATES):
    r = rng(SEED + i)
    b = REGION[pick(r(), [x[1] for x in REGION])]
    household = 1 + pick(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    satisfaction = 1 + pick(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() >= 0.046:
        SUBSCRIBERS.append({"id": 10001 + i, "region": b, "household": household,
                            "satisfaction": satisfaction})
for k in SUBSCRIBERS:
    r = rng(SEED + 7000 + k["id"])
    for d in range(pick(r(), [0.05, 0.12, 0.21, 0.62])):
        READINGS.setdefault(k["id"], []).append(0.0 if r() < 0.038 else math.floor(
            k["region"][2] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - d * 0.05) * 100 + 0.5) / 100)
        r()

DATA = []
for k in SUBSCRIBERS:
    v = READINGS.get(k["id"])
    if v is None:
        continue
    mean, vol, r = sum(v) / len(v), max(v) - min(v), rng(SEED + 51000 + k["id"])
    z = (0.052 * (mean - 20) + 0.85 * (min(v) == 0.0) + 0.026 * vol
         + 0.24 * (k["household"] >= 5) - 0.20 * (k["satisfaction"] >= 4) + k["region"][3]
         + 0.9 * (k["id"] - 10001) / 1399 + (r() + r() + r() - 1.5) * 1.30)
    x = {"household": k["household"], "satisfaction": k["satisfaction"], "period": len(v),
         "mean_consumption": round(mean, 2), "volatility": round(vol, 2),
         "zero_readings": int(min(v) == 0.0), "suspicious": int(z > 1.35)}
    for b in REGION:
        x["b_" + b[0]] = int(k["region"][0] == b[0])
    DATA.append(x)


def shuffle(data, seed):
    r, s = rng(seed), list(range(len(data)))
    for i in range(len(s) - 1, 0, -1):
        j = int(r() * (i + 1))
        s[i], s[j] = s[j], s[i]
    return [data[i] for i in s]


K = shuffle(DATA, SEED + 90000)
TRAIN, TEST = K[:756], K[1008:]
FIELDS = ["mean_consumption", "volatility", "household", "satisfaction", "period", "zero_readings",
          "b_north", "b_south", "b_east", "b_west", "b_central"]
N_TRAIN, N_TEST = sum(x["suspicious"] for x in TRAIN), sum(x["suspicious"] for x in TEST)
print(f"train {len(TRAIN)} subscribers, suspicious {N_TRAIN} ({N_TRAIN / len(TRAIN):.4f}); "
      f"test {len(TEST)} subscribers, suspicious {N_TEST} ({N_TEST / len(TEST):.4f})")
print(f"majority / minority ratio in train {(len(TRAIN) - N_TRAIN) / N_TRAIN:.2f}")
print(f"baseline (most frequent class): accuracy "
      f"{sum(x['suspicious'] == 0 for x in TEST) / len(TEST):.4f}, "
      f"suspicious caught 0 / {N_TEST}, suspicious flagged 0")

train 756 subscribers, suspicious 168 (0.2222); test 252 subscribers, suspicious 61 (0.2421)
majority / minority ratio in train 3.50
baseline (most frequent class): accuracy 0.7579, suspicious caught 0 / 61, suspicious flagged 0

The last line shows the baseline of the course in a second measure, and the picture changes. 0.7579 in accuracy is a number that looks good; zero in the number of suspicious subscribers caught is an unusable result. The same procedure, the same set, two measures, two different verdicts. On an imbalanced set, not having chosen the measure is the same as not having chosen the baseline.

Three Answers

The code below writes the tree so that it accepts weights and measures the three answers in turn.

def gini(s):
    n = sum(x.get("w", 1.0) for x in s)
    if n <= 0:
        return 0.0
    p = sum(x.get("w", 1.0) * x["suspicious"] for x in s) / n
    return 2 * p * (1 - p)


def tree(s, depth, fields, min_size=2):     # MODEL: weighted decision tree
    n = sum(x.get("w", 1.0) for x in s)
    p = sum(x.get("w", 1.0) * x["suspicious"] for x in s) / n
    best = None
    if depth and len(s) >= 2 * min_size and 0.0 < p < 1.0:
        for a in fields:
            d = sorted({x[a] for x in s})
            for v in (d[1:] if len(d) < 10 else
                      [d[int(i * len(d) / 10)] for i in range(1, 10)]):
                left = [x for x in s if x[a] < v]
                right = [x for x in s if x[a] >= v]
                if min(len(left), len(right)) < min_size:
                    continue
                k = gini(s) - (sum(x.get("w", 1.0) for x in left) * gini(left)
                               + sum(x.get("w", 1.0) for x in right) * gini(right)) / n
                if best is None or k > best[0]:
                    best = (k, a, v, left, right)
    if best is None or best[0] <= 1e-9:
        return {"prediction": int(p > 0.5)}
    return {"field": best[1], "threshold": best[2],
            "left": tree(best[3], depth - 1, fields, min_size),
            "right": tree(best[4], depth - 1, fields, min_size)}


def predict(d, x):
    while "prediction" not in d:
        d = d["left"] if x[d["field"]] < d["threshold"] else d["right"]
    return d["prediction"]


def oversample(train, times):               # each minority row is written `times` times
    out = []
    for x in train:
        out += [x] * (times if x["suspicious"] else 1)
    return out


def undersample(train, seed):               # the majority is reduced to the minority size
    minority = [x for x in train if x["suspicious"]]
    majority = shuffle([x for x in train if not x["suspicious"]], seed)[:len(minority)]
    return shuffle(minority + majority, seed + 1)


def weighted(train, w):
    return [dict(x, w=(w if x["suspicious"] else 1.0)) for x in train]


RESULT = {}


def measure(name, train):
    m = tree(train, 6, FIELDS)
    t = [predict(m, x) for x in TEST]
    d = sum(t[i] == TEST[i]["suspicious"] for i in range(len(TEST))) / len(TEST)
    c = sum(1 for i, x in enumerate(TEST) if t[i] == 1 and x["suspicious"] == 1)
    RESULT[name] = (len(train), d, c, sum(t))
    print(f"{name:<36} {len(train):>7} {d:>9.4f} {c:>10} {sum(t):>10}")


print(f"{'procedure':<36} {'train':>7} {'accuracy':>9} {'caught':>10} "
      f"{'flagged':>10}")
print(f"{'baseline (most frequent class)':<36} {'-':>7} "
      f"{sum(x['suspicious'] == 0 for x in TEST) / len(TEST):>9.4f} {0:>10} {0:>10}")
measure("raw training set", TRAIN)
measure("oversampling, minority twice", oversample(TRAIN, 2))
measure("oversampling, minority three times", oversample(TRAIN, 3))
measure("undersampling, majority to minority", undersample(TRAIN, SEED + 22000))
measure("class weight 2.0", weighted(TRAIN, 2.0))
measure("class weight 3.5", weighted(TRAIN, 3.5))

procedure                              train  accuracy     caught    flagged
baseline (most frequent class)             -    0.7579          0          0
raw training set                         756    0.7778         21         37
oversampling, minority twice             924    0.7619         33         65
oversampling, minority three times      1092    0.7341         34         74
undersampling, majority to minority      336    0.7143         36         83
class weight 2.0                         756    0.7619         33         65
class weight 3.5                         756    0.6349         39        109

The two columns move in opposite directions. While accuracy falls from 0.7778 to 0.6349, the number of suspicious subscribers caught rises from 21 to 39. With the raw training set the model misses 40 of the 61 suspicious subscribers; with the harshest weight it misses 22 of them, but the number of subscribers it flags as suspicious rises from 37 to 109.

The flagged column says something on its own, too. There are 61 suspicious subscribers in the test set, while the model trained on the raw training set flags only 37 subscribers. The model flags the minority too little, and this is not a tuning mistake but the direct result of the split criterion: the criterion rewards saying the majority at a leaf, and as long as the minority share stays below fifty percent, a leaf saying minority pays off only when a very pure region is found. All three answers to imbalance break exactly this calculation: some by writing a row a second time, some by reducing the opposite class, some by changing the weight directly, they pull down the threshold at which leaves say minority. The Statistical Analysis and Exploratory Data Analysis course of the Data Analytics curriculum measured the traps of reading proportions in imbalanced sets; the difference here is that it is not the proportion but the decision that changes.

In Which Number the Contribution Is Measured

When the same decisions are read against the raw training set, the meaning of the table becomes clear.

h = RESULT["raw training set"]
print(f"{'procedure':<36} {'accuracy change':>15} {'caught +':>12} "
      f"{'missed':>10} {'false flags':>14}")
for name in ("oversampling, minority twice", "oversampling, minority three times",
             "undersampling, majority to minority", "class weight 2.0",
             "class weight 3.5"):
    v = RESULT[name]
    print(f"{name:<36} {v[1] - h[1]:>+15.4f} {v[2] - h[2]:>+12} "
          f"{N_TEST - v[2]:>10} {v[3] - v[2]:>14}")
a = tree(oversample(TRAIN, 2), 6, FIELDS)
b = tree(weighted(TRAIN, 2.0), 6, FIELDS)
print(f"\nsubscribers given the same prediction by oversampling twice and class weight 2.0 "
      f"{sum(predict(a, x) == predict(b, x) for x in TEST)} / {len(TEST)}")

procedure                            accuracy change     caught +     missed    false flags
oversampling, minority twice                 -0.0159          +12         28             32
oversampling, minority three times           -0.0437          +13         27             40
undersampling, majority to minority          -0.0635          +15         25             47
class weight 2.0                             -0.0159          +12         28             32
class weight 3.5                             -0.1429          +18         22             70

subscribers given the same prediction by oversampling twice and class weight 2.0 252 / 252

In the accuracy column all five rows are negative. If the rule of the course is applied to the letter, none of these five steps has a contribution and none of them should be taken. But the caught column rises by between twelve and eighteen subscribers, and each of those subscribers is a missed suspicion of illicit use or a fault. The contradiction is not in the procedures but in the choice of the measure. As long as accuracy is chosen, the contribution of every answer to imbalance is negative; when the measure changes, the sign changes too. Which number matters is not read from the data but from the job — how many wrong addresses an inspection team can go to is a question of resources.

The undersampling row also opens a question of stability. Had the same undersampling been done with another seed, which 168 majority rows remain would change, and the model would change with it; oversampling and weighting contain no random choice and produce the same tree on the same set in every run. Besides the contribution of a preparation step, how much that contribution moves from run to run should also be asked.

The cost side of the last two rows is clear. Class weight 3.5 catches eighteen more suspicious subscribers while raising the number of wrongly flagged subscribers from 16 to 70. Undersampling pays a different price: the training set falls from 756 rows to 336, and the information in the 420 discarded majority rows does not come back. On small sets this price is reflected directly in the stability of the model.

The last output shows that two procedures are the same thing. Oversampling the minority twice and giving the minority a class weight of 2.0 produce the same prediction for all 252 subscribers in the test set. The reason is in the split criterion of the tree: the criterion is computed with the weighted sum of the rows, and writing a row twice gives the same sum as making its weight two. The only place where the two part ways is the stopping condition that looks at the number of rows — with oversampling the set grows to 924 rows, with weighting it stays at 756 — and in this table that condition did not bind at any node. In memory and time weighting is cheap; oversampling produces the same result with a larger set.

Summary

• The baseline gives two separate numbers on an imbalanced set: 0.7579 in accuracy, zero out of 61 in the number of suspicious subscribers caught; accuracy alone is a misleading baseline.
• The model on the raw training set gives 0.7778 accuracy and catches 21 of the 61 suspicious subscribers, and misses 40.
• Oversampling, undersampling and class weight all give a negative contribution in accuracy (between −0.0159 and −0.1429) and a positive one of between twelve and eighteen subscribers in the number of suspicious subscribers caught; the sign turns with the measure.
• Undersampling takes the training set from 756 rows to 336, and the information in the 420 discarded majority rows does not come back; oversampling and weighting discard no rows.
• Oversampling the minority twice and giving a class weight of 2.0 produce the same prediction for all 252 subscribers in the test set, because the split criterion of the tree is computed with the weighted sum.

Next Step

In this lesson the number of suspicious subscribers was a problem because of its scarcity; in the next lesson a few subscribers will be a problem because of their value. In the mean consumption column there are subscribers outside the fence computed from the interquartile range of the training set; some of them are real extremes, and some are recording errors produced by stuck meters. The two look the same in the table. The next lesson measures a single clipping decision in two model families, shows that the same decision gives a positive contribution in the slope-based procedure and a negative one in the tree-based procedure, and puts forward with numbers that an outlier can be managed without deleting any row.