Categorical Encoding

The previous lesson used the region information as five ready-made binary columns and did not ask where those columns came from. The region is a text field. The input of a model is a number. The translation in between is a decision, and the decision has at least two costs: how many columns it produces and how much it moves the number on the held-out set.

This lesson compares three encodings on the same table. One-hot encoding opens a separate binary column for each category. Ordinal encoding gives the categories one integer each and settles for a single column. Target encoding replaces each category with the suspicious rate of that category in the training set; it produces a single column but puts the label inside the encoding. The measurement is made on two categorical fields: the region with five categories and the reading route code, whose cardinality is two hundred forty.

• PS17. The reading route code is a field of the raw record and is fictional: each subscriber is attached to one reading route, and routes were opened according to region and the expansion wave of the network. The Data Analytics curriculum did not use this field.
• PS18. The route code is not produced directly from the label. The information it carries comes from the region and from the wave of joining the network; the second is absent from the feature columns.
• PS19. The measurement set, the split and the baseline are the same as in the earlier lessons: 756/252/252 and 0.7579 on the test set.
• PS20. The model is fixed: a depth 6 decision tree. No scaling is applied, because the previous lesson showed that its contribution on the tree is exactly zero.
• PS21. The encoding is a fitted object. What is fitted is the category list in one-hot encoding, the category–integer mapping in ordinal encoding, and the category–rate table in target encoding. All three are extracted only from the training set.
• PS22. An unseen category is a code that appears in the held-out set and does not exist in the training set. Every encoding has to give it an answer, and the answer it gives is part of the encoding.
• PS23. Computing target encoding in-fold means this: the training set is divided into five folds, and the encoding value of each row is computed from the four folds that do not contain that row. This way no row’s own label enters its own encoding value.
• PS24. Cross-validation itself is not built in this lesson; the fold is used only as the split in which the encoding is computed.
• PS25. The test set is 252 subscribers, and one subscriber is worth 0.0040.

Three Encodings, Two Numbers

The setup regenerates the table and adds the route field.

# encoding.py — MODEL. The fictional subscriber table is regenerated with the same seed; the
# FICTIONAL reading route code from the raw record is added as a categorical column.
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, route_rng = [], rng(SEED + 41000)
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),
         "region": k["region"][0]}
    wave = min(7, int((k["id"] - 10001) / 1399 * 8))        # wave of joining the network
    x["route"] = "R%03d" % ([b[0] for b in REGION].index(k["region"][0]) * 48
                            + wave * 6 + int(route_rng() * 6) + 1)
    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:]
BASELINE = sum(x["suspicious"] == 0 for x in TEST) / len(TEST)
NUMERIC = ["mean_consumption", "volatility", "household", "satisfaction", "period", "zero_readings"]
TRAIN_ROUTES = {x["route"] for x in TRAIN}
ROUTE_SIZE = {}
for x in TRAIN:
    ROUTE_SIZE[x["route"]] = ROUTE_SIZE.get(x["route"], 0) + 1
print(f"route code: {len({x['route'] for x in DATA})} in the table, {len(TRAIN_ROUTES)} in train, "
      f"most crowded route {max(ROUTE_SIZE.values())} subscribers, average "
      f"{sum(ROUTE_SIZE.values()) / len(ROUTE_SIZE):.1f}")
print(f"unseen route codes in test {len({x['route'] for x in TEST} - TRAIN_ROUTES)}, "
      f"subscribers on these codes {sum(1 for x in TEST if x['route'] not in TRAIN_ROUTES)}")
print(f"region {len({x['region'] for x in TRAIN})} categories, baseline {BASELINE:.4f}")

route code: 240 in the table, 231 in train, most crowded route 9 subscribers, average 3.3
unseen route codes in test 6, subscribers on these codes 10
region 5 categories, baseline 0.7579

On average 3.3 subscribers fall on each route, and the most crowded route has nine subscribers. This number will be decisive in the second half of the lesson. Now the four encodings are applied in turn.

def gini(s):
    p = sum(x["suspicious"] for x in s) / len(s) if s else 0.0
    return 2 * p * (1 - p)


def tree(s, depth, fields, min_size=2):     # MODEL: decision tree, depth 6
    p = sum(x["suspicious"] for x in s) / len(s)
    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) - (len(left) * gini(left) + len(right) * gini(right)) / len(s)
                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 one_hot(column, train, test):           # FIT: the category list in the training set
    cats = sorted({x[column] for x in train})
    encode = (lambda s: [dict(x, **{column + "_" + k: int(x[column] == k) for k in cats})
                         for x in s])
    return [column + "_" + k for k in cats], encode(train), encode(test)


def ordinal(column, train, test, order=None):  # FIT: category -> integer mapping
    cats = order or {k: i for i, k in enumerate(sorted({x[column] for x in train}))}
    encode = lambda s: [dict(x, route_ordinal=cats.get(x[column], -1)) for x in s]
    return ["route_ordinal"], encode(train), encode(test)


def rate(rows):
    m = {}
    for x in rows:
        m.setdefault(x["route"], []).append(x["suspicious"])
    return {k: sum(v) / len(v) for k, v in m.items()}


def target(train, test):                    # FIT: suspicious rate per category
    g, t = sum(x["suspicious"] for x in train) / len(train), rate(train)
    encode = lambda s: [dict(x, route_target=t.get(x["route"], g)) for x in s]
    return ["route_target"], encode(train), encode(test)


def target_in_fold(train, test, folds=5):   # each row from outside its own fold
    g, t = sum(x["suspicious"] for x in train) / len(train), rate(train)
    tables = [rate([y for j, y in enumerate(train) if j % folds != i]) for i in range(folds)]
    e = [dict(x, route_target=tables[i % folds].get(x["route"], g)) for i, x in enumerate(train)]
    return ["route_target"], e, [dict(x, route_target=t.get(x["route"], g)) for x in test]


RESULT = {}


def measure(name, fields, e, s):
    m = tree(e, 6, fields)
    train_acc = sum(predict(m, x) == x["suspicious"] for x in e) / len(e)
    test_acc = sum(predict(m, x) == x["suspicious"] for x in s) / len(s)
    RESULT[name] = (len(fields), train_acc, test_acc)
    print(f"{name:<28} {len(fields):>7} {train_acc:>8.4f} {test_acc:>8.4f}")


print(f"{'encoding':<28} {'columns':>7} {'train':>8} {'test':>8}")
measure("no categorical column", NUMERIC, TRAIN, TEST)
region_cols, eb, sb = one_hot("region", TRAIN, TEST)
measure("region one-hot", NUMERIC + region_cols, eb, sb)
for name, fn in (("+ route one-hot", lambda: one_hot("route", eb, sb)),
                 ("+ route ordinal", lambda: ordinal("route", eb, sb)),
                 ("+ route target", lambda: target(eb, sb)),
                 ("+ route target, in-fold", lambda: target_in_fold(eb, sb))):
    a, e, s = fn()
    measure(name, NUMERIC + region_cols + a, e, s)

encoding                     columns    train     test
no categorical column              6   0.8492   0.7302
region one-hot                    11   0.8466   0.7778
+ route one-hot                  242   0.8452   0.7897
+ route ordinal                   12   0.8651   0.7897
+ route target                    12   0.9114   0.7421
+ route target, in-fold           12   0.8519   0.7540

The first two rows say what the encoding itself is worth. When no categorical field is used, the model reads 0.7302 and stays 0.0277 below the baseline. When the five-category region field is opened into five binary columns, the number rises to 0.7778: twelve subscribers. This is the largest single contribution of the course so far, and the decision itself is invisible, because turning the region into a number is usually done without discussion.

The Same Contribution, a Difference of Two Hundred Thirty-One Columns

When the three encodings of the route field stand side by side in the same table, the price paid becomes visible.

t = RESULT["region one-hot"]
print(f"{'encoding':<28} {'added columns':>14} {'train contribution':>19} {'test contribution':>18}")
for name in ("+ route one-hot", "+ route ordinal", "+ route target",
             "+ route target, in-fold"):
    v = RESULT[name]
    print(f"{name:<28} {v[0] - t[0]:>14} {v[1] - t[1]:>+19.4f} {v[2] - t[2]:>+18.4f}")

codes = sorted(TRAIN_ROUTES)
code_rng = rng(SEED + 43000)
perm = list(range(len(codes)))
for i in range(len(perm) - 1, 0, -1):
    j = int(code_rng() * (i + 1))
    perm[i], perm[j] = perm[j], perm[i]
a, e, s = ordinal("route", eb, sb, {k: perm[i] for i, k in enumerate(codes)})
m = tree(e, 6, NUMERIC + region_cols + a)
print(f"\nordinal encoding, code order shuffled: test "
      f"{sum(predict(m, x) == x['suspicious'] for x in s) / len(s):.4f}")

g = sum(x["suspicious"] for x in TRAIN) / len(TRAIN)
_, _, st = target(eb, sb)
unseen = [x for x in st if x["route"] not in TRAIN_ROUTES]
print(f"{len(unseen)} subscribers on unseen routes: in one-hot encoding all 231 columns are 0, "
      f"in ordinal encoding -1, in target encoding {g:.4f}")
print(f"inflation on train of the in-fold encoding "
      f"{RESULT['+ route target'][1] - RESULT['+ route target, in-fold'][1]:+.4f}, "
      f"recovered on test "
      f"{RESULT['+ route target, in-fold'][2] - RESULT['+ route target'][2]:+.4f}")

encoding                      added columns  train contribution  test contribution
+ route one-hot                         231             -0.0013            +0.0119
+ route ordinal                           1             +0.0185            +0.0119
+ route target                            1             +0.0648            -0.0357
+ route target, in-fold                   1             +0.0053            -0.0238

ordinal encoding, code order shuffled: test 0.7778
10 subscribers on unseen routes: in one-hot encoding all 231 columns are 0, in ordinal encoding -1, in target encoding 0.2222
inflation on train of the in-fold encoding +0.0595, recovered on test +0.0119

The first two rows give the same contribution at two different prices: one-hot encoding gives 0.0119 for 231 extra columns, ordinal encoding gives the same 0.0119 for a single column. A three-subscriber difference would not be read on its own; what is read is the price difference. The cost of one-hot encoding grows linearly with the cardinality, and on a training set of 756 rows, 231 columns means an average of three rows per column.

There is a reason ordinal encoding works in this table, and the shuffling test reveals it. The code numbers were not given at random; they were ordered first by region and then by the wave of joining the network, so saying “the route number is smaller” says something. When the mapping is shuffled, the test number drops to 0.7778, that is, to where it would be if the route field had not been used at all. The contribution of ordinal encoding comes not from the categories but from the order of the codes themselves; when the order is made up, the contribution is zero.

The third row is the real number of the lesson. Target encoding gains 0.0648 on the training set and loses 0.0357 on the test set. The opposite signs of the two numbers are no coincidence; they are the two faces of the same event. On average 3.3 subscribers fall on each route; the suspicious rate of a route with three subscribers is the mean of the labels of those three rows, and each row’s own label is one third of that mean. When the tree reads this column, it reads a copy of the row’s label. The 0.9114 on the training set is the result not of learning but of reading itself.

In-fold computation corrects this. When each row’s encoding value is derived from the four folds that do not contain that row, 0.0595 of the inflation on the training set disappears and the test number comes back by 0.0119. Even so, the remaining contribution is −0.0238: after the leak is pulled back, target encoding still stays below the baseline in this field. The measured result is this — removing the leak does not make the step good, it only makes the real contribution of the step visible.

The last line is the silent face of the encoding. In the test set, ten subscribers are attached to six routes never seen in the training set. One-hot encoding gives them a row of 231 zeros, ordinal encoding gives a −1 outside the training range, and target encoding gives the overall rate of the training set, 0.2222. All three are a decision and all three are part of the encoding; none of them is right by itself.

Summary

• When no categorical field is used, the model reads 0.7302 and stays below the baseline; when the five-category region field is one-hot encoded it rises to 0.7778, a contribution of +0.0476.
• The route field with a cardinality of 240 gives +0.0119 for 231 extra columns when one-hot encoded, and the same +0.0119 for a single column when ordinal encoded; the same contribution has two different prices.
• The contribution of ordinal encoding comes from the order of the codes themselves: when the category–integer mapping is shuffled, the test number drops to 0.7778, that is, to the level where the field is not used at all.
• Target encoding gives +0.0648 on train and −0.0357 on test; since 3.3 subscribers fall on each route, each row’s own label is inside its own encoding value.
• In-fold computation erases 0.0595 of the inflation on the training set and brings 0.0119 back on the test set, but the remaining contribution is −0.0238; removing the leak does not make the step good, it shows its real contribution.

Next Step

In this lesson the satisfaction column was assumed to be filled for every subscriber. In the raw record it is not so: satisfaction is a survey response, and there are subscribers who did not answer the survey. In all the lessons so far, that gap was silently filled with the median of the training set, and the filling itself was never measured. The next lesson puts the gap back and prints three options side by side: filling with the median, filling and adding a missingness indicator next to it, and dropping the missing rows from the training set. When the missingness carries information about the subscriber itself, the contribution of the indicator is measured, and why dropping rows cannot be applied on the held-out set is shown with numbers.