Nearest Neighbor

The Linear Models topic worked on a single form across five lessons: the model drew a line or a plane in the feature space. Polynomial features stretched this form, but the stretching still stayed inside an equation with fixed coefficients. The closing of the topic left a question open: what happens in a set where the boundary separating two classes is itself curved, and how many numbers does a family that finds that curve without writing it by hand cost.

This lesson starts with the answer that is furthest from the question: a model that builds no equation at all. An instance-based procedure computes nothing during training; it stores the training set as it is, and when classifying a subscriber it looks at the training rows nearest to that subscriber and gives the label of the majority. The decision boundary is not written here, it arises from the placement of the examples, and nothing extra is done to make it curved. It has a price, and the lesson measures that price with the course’s three numbers: the baseline, the family number and the number of candidates tried to find that number.

• NM1. The set is the fictional subscriber table coming from the Introduction to Machine Learning and Data Preparation and Feature Engineering courses: 1,260 subscribers, seed 20260218, split 756/252/252, baseline 0.7579 on the test set. The baseline is the procedure that says the most frequent class, that is, “not suspicious”.
• NM2. The feature set is taken as the Data Preparation and Feature Engineering course left it and is held fixed throughout the course: five numeric columns, the per-person consumption ratio, the zero-reading indicator and five region columns, twelve in total. Columns derived from text are left out because they are left to the Natural Language Processing and Computer Vision course. The only thing that changes is the model.
• NM3. The measure is accuracy and the test set is 252 subscribers; one subscriber is worth 0.0040.
• NM4. Scaling is applied in the form set up in the scaling lesson of the Data Preparation and Feature Engineering course: the standard score is learned from the training set alone and applied to the other two sets. In a procedure that sums distances, scale is a column weight; that course measured that the sign of this decision changes with the family, and those numbers are not repeated here.
• NM5. A hyperparameter is a number that the model does not learn from the data and that is given from outside. This family has two: the neighbor count and the distance metric.
• NM6. The choice is read from the validation set. The number on the test set is only reported; what would come out if the choice were made on the test set from the same table is printed separately.
• NM7. Neighbor counts are chosen odd so that no tie arises in the vote.
• NM8. The columns added in the curse of dimensionality measurement are fictional, come from the same generator and carry no relation to the label.

A Model Without Training

The setup reproduces the set, learns the scale from the training set and writes the procedure.

# neighbor.py — MODEL: the FICTIONAL subscriber table of the Introduction to Machine Learning course is rebuilt with the same seed;
# the feature set comes from the Data Preparation and Feature Engineering course and is fixed throughout the course.
import math
import statistics

SEED, RAW, 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, DATA = [], []
for i in range(RAW):
    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])
    rating = 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": rating})
for k in SUBSCRIBERS:
    r, v = rng(SEED + 7000 + k["id"]), []
    for n in range(pick(r(), [0.05, 0.12, 0.21, 0.62])):
        v.append(0.0 if r() < 0.038 else math.floor(
            k["region"][2] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - n * 0.05) * 100 + 0.5) / 100)
        r()
    if not v:
        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),
         "region_name": k["region"][0],
         "zero_readings": int(min(v) == 0.0), "suspicious": int(z > 1.35)}
    for b in REGION:
        x["area_" + b[0]] = int(k["region"][0] == b[0])
    x["per_person"] = round(x["mean_consumption"] / x["household"], 3)
    DATA.append(x)

NUMERIC = ["mean_consumption", "volatility", "household", "satisfaction", "period", "per_person"]
FIELDS = NUMERIC + ["zero_readings", "area_north", "area_south", "area_east", "area_west",
                    "area_central"]


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, VAL, TEST = K[:756], K[756:1008], K[1008:]
BASELINE_TEST = sum(x["suspicious"] == 0 for x in TEST) / len(TEST)
BASELINE_VAL = sum(x["suspicious"] == 0 for x in VAL) / len(VAL)
SCALE = {a: (statistics.fmean(x[a] for x in TRAIN),
             statistics.pstdev([x[a] for x in TRAIN])) for a in NUMERIC}


def scale_rows(s):
    return [dict(x, **{a: (x[a] - SCALE[a][0]) / SCALE[a][1] for a in SCALE}) for x in s]


def vectorize(s, fields=None):
    return [([x[a] for a in (fields or FIELDS)], x["suspicious"]) for x in s]


def abs_diff(a, b):
    return sum(abs(p - q) for p, q in zip(a, b))


def neighbor_accuracy(train, target, k, metric):   # MODEL: instance-based procedure
    hits = 0
    for v, y in target:
        u = sorted((metric(v, w), t) for w, t in train)
        hits += (sum(t for _, t in u[:k]) * 2 > k) == y
    return hits / len(target)


S_TRAIN, S_VAL, S_TEST = scale_rows(TRAIN), scale_rows(VAL), scale_rows(TEST)
V_TRAIN, V_VAL, V_TEST = vectorize(S_TRAIN), vectorize(S_VAL), vectorize(S_TEST)
print(f"train {len(TRAIN)}, validation {len(VAL)}, test {len(TEST)}, columns {len(FIELDS)}")
print(f"baseline: test {BASELINE_TEST:.4f}, validation {BASELINE_VAL:.4f}")
print(f"unscaled columns (absolute difference, k=31) test "
      f"{neighbor_accuracy(vectorize(TRAIN), vectorize(TEST), 31, abs_diff):.4f}")
print(f"scaled columns   (absolute difference, k=31) test "
      f"{neighbor_accuracy(V_TRAIN, V_TEST, 31, abs_diff):.4f}")

train 756, validation 252, test 252, columns 12
baseline: test 0.7579, validation 0.8135
unscaled columns (absolute difference, k=31) test 0.7778
scaled columns   (absolute difference, k=31) test 0.7937

The body of the neighbor_accuracy function has no model-building step. In the other families there is a stage that produces weights, coefficients or split thresholds; here that stage is empty and the model itself is the 756-row training set. One consequence shows on the prediction side: for every new subscriber, 756 distances are computed and sorted. The family hands the cost of training over to prediction.

The second observation is in the scaling lines. The same procedure reads 0.7778 with unscaled columns and 0.7937 with scaled columns. The reason is that distance is a sum: in the sum of twelve differences, the raw range of mean consumption is forty times wider than the range of a region column, so unscaled distance is quietly a weighting. The Data Preparation and Feature Engineering course measured this decision separately in three families and showed that its sign changes with the family; here scaling stands not as a correction but as the condition for the notion of distance to be comparable across columns.

One more number needs attention: the baseline is not the same on the two sets. It is 0.7579 on the test set and 0.8135 on the validation set. Two sets coming out of the same split have drifted apart by 0.0556 in the suspicious share. This means that a model’s validation number cannot be compared directly with its test number; each number is read against the baseline of its own set.

Twenty-Four Candidates

The family has two hyperparameters and neither is learned from the data. The neighbor count determines how many examples a decision rests on. The distance metric is the definition of the word “near”: squared distance, which sums the squares of the differences; absolute difference, which sums the absolute differences; and largest difference, which looks only at the single largest difference. The three do not give the same ordering on the same set.

def squared_distance(a, b):
    return sum((p - q) * (p - q) for p, q in zip(a, b))


def largest_difference(a, b):
    return max(abs(p - q) for p, q in zip(a, b))


NEIGHBOR_COUNTS = [1, 3, 5, 9, 15, 21, 31, 45]
METRICS = [("squared distance", squared_distance), ("absolute difference", abs_diff),
           ("largest difference", largest_difference)]


def neighbor_labels(train, target, metric):
    return [([t for _, t in sorted((metric(v, w), t) for w, t in train)][:max(NEIGHBOR_COUNTS)], y)
            for v, y in target]


CANDIDATES = {}
for name, metric in METRICS:
    lv, lt = neighbor_labels(V_TRAIN, V_VAL, metric), neighbor_labels(V_TRAIN, V_TEST, metric)
    for k in NEIGHBOR_COUNTS:
        CANDIDATES[(name, k)] = (sum((sum(t[:k]) * 2 > k) == y for t, y in lv) / len(lv),
                                 sum((sum(t[:k]) * 2 > k) == y for t, y in lt) / len(lt))

for i, split in enumerate(("validation", "test")):
    print(f"{split + ' k =':<20}" + "".join(f"{k:>8}" for k in NEIGHBOR_COUNTS))
    for name, _ in METRICS:
        print(f"{name:<20}" + "".join(f"{CANDIDATES[(name, k)][i]:>8.4f}" for k in NEIGHBOR_COUNTS))
cv = max(CANDIDATES, key=lambda a: (CANDIDATES[a][0], -a[1]))
ct = max(CANDIDATES, key=lambda a: (CANDIDATES[a][1], -a[1]))
print(f"\ncandidates tried {len(CANDIDATES)}")
print(f"chosen on validation: {cv[0]}, k={cv[1]} -> validation {CANDIDATES[cv][0]:.4f}, "
      f"test {CANDIDATES[cv][1]:.4f}")
print(f"chosen on test:       {ct[0]}, k={ct[1]} -> validation {CANDIDATES[ct][0]:.4f}, "
      f"test {CANDIDATES[ct][1]:.4f}")
print(f"validation - test on the chosen candidate {CANDIDATES[cv][0] - CANDIDATES[cv][1]:+.4f}; "
      f"family number {CANDIDATES[cv][1] - BASELINE_TEST:+.4f} above the baseline")
print(f"candidates above the validation baseline "
      f"{sum(1 for a in CANDIDATES if CANDIDATES[a][0] > BASELINE_VAL)}, "
      f"above the test baseline {sum(1 for a in CANDIDATES if CANDIDATES[a][1] > BASELINE_TEST)}")

validation k =             1       3       5       9      15      21      31      45
squared distance      0.7540  0.7738  0.7698  0.8214  0.8175  0.8254  0.8214  0.8254
absolute difference   0.7778  0.7738  0.7937  0.8254  0.8214  0.8214  0.8294  0.8254
largest difference    0.7500  0.7897  0.8056  0.8214  0.8056  0.8095  0.8056  0.8135
test k =                   1       3       5       9      15      21      31      45
squared distance      0.7262  0.7341  0.7341  0.7579  0.7619  0.7738  0.7778  0.7937
absolute difference   0.7063  0.7262  0.7302  0.7698  0.7698  0.7619  0.7937  0.7937
largest difference    0.7262  0.7460  0.7619  0.7817  0.7897  0.7738  0.7579  0.7778

candidates tried 24
chosen on validation: absolute difference, k=31 -> validation 0.8294, test 0.7937
chosen on test:       absolute difference, k=31 -> validation 0.8294, test 0.7937
validation - test on the chosen candidate +0.0357; family number +0.0357 above the baseline
candidates above the validation baseline 11, above the test baseline 14

The first column shows the best-known flaw of the family. The procedure that looks at a single neighbor is below the baseline on the test set under all three metrics: 0.7262, 0.7063 and 0.7262. One neighbor means copying the label of a single row in the training set; if that row sits on the wrong side, the decision sits on the wrong side too. As the neighbor count grows, each decision rests on more rows and the number rises.

The choice read from the validation set is absolute difference with 31 neighbors; that candidate’s validation number is 0.8294 and its test number is 0.7937. The family number is 0.7937, and it beats the baseline by 0.0357, that is, nine subscribers. If the choice were made on the test set from the same table, the chosen candidate would not change; this is luck, and it shows in the table, because 0.7937 appears on three different candidates at once on the test set. What would change is not the candidate but the reported number: had the 0.8294 on the set the choice was made on been reported, the family would have seemed to gain eighteen subscribers instead of nine. The validation set is a set spent on choosing, and the highest number read on it is not an estimate of generalization.

The number of candidates tried is 24, and this number cannot be read without standing next to the family number. Of the twenty-four candidates, 11 beat their own baseline on the validation set, one comes out exactly equal to the baseline, and the remaining twelve are worse than a procedure that says nothing. The sentence “the family beat the baseline by 0.0357” is not the same thing as the sentence “the best of twenty-four candidates beat the baseline by 0.0357”.

The Curse of Dimensionality

Distance stops being distinguishing as the column count grows. The mechanism is in the sum itself: every new column adds a term to the sum, and if the terms are independent of each other, the sum approaches a common mean as the column count grows. As a result the ratio between the farthest neighbor and the nearest neighbor falls to 1 and the word “nearest” loses its meaning. This is known as the curse of dimensionality, and it can be counted.

def noisy(s, d, seed):                 # FICTIONAL: columns that carry no information
    out = []
    for i, x in enumerate(s):
        r = rng(seed + i)
        out.append(([x[a] for a in FIELDS] + [(r() + r() + r() - 1.5) * 1.15
                                              for _ in range(d)], x["suspicious"]))
    return out


print(f"{'columns':>7} {'farthest / nearest':>19} {'test':>8} {'vs baseline':>12}")
for d in (0, 4, 12, 40, 120):
    NT, NE = noisy(S_TRAIN, d, SEED + 300000), noisy(S_TEST, d, SEED + 700000)
    ratio, correct = [], 0
    for v, y in NE:
        u = sorted((abs_diff(v, w), t) for w, t in NT)
        ratio.append(u[-1][0] / u[0][0])
        correct += (sum(t for _, t in u[:31]) * 2 > 31) == y
    print(f"{len(FIELDS) + d:>7} {statistics.fmean(ratio):>19.2f} "
          f"{correct / len(NE):>8.4f} {correct / len(NE) - BASELINE_TEST:>+12.4f}")

columns  farthest / nearest     test  vs baseline
     12               26.91   0.7937      +0.0357
     16                6.70   0.7817      +0.0238
     24                3.46   0.7738      +0.0159
     52                2.01   0.7698      +0.0119
    132                1.49   0.7579      +0.0000

The two columns are read together. At twelve columns the farthest training row is 26.91 times farther than the nearest one, and the word “neighbor” has a counterpart. When four noise columns are added the ratio falls to 6.70, and at forty columns to 2.01. At one hundred twenty noise columns the ratio is 1.49: less than half again separates the nearest training row from the farthest one, and the model settles exactly on the baseline, 0.7579. The family is no longer learning anything.

None of the added columns carries wrong information; they carry no information at all. The difference comes from the family’s inability to ignore these columns. A decision tree that picks a single column at each split can leave the uninformative column outside by not choosing it as a split candidate; a linear model that learns coefficients can shrink that column’s coefficient. The sum of distances has no such means, because distance is not learned, it is defined. Feature selection and dimensionality reduction are not an improvement for this family but the condition for it to work.

Summary

• The training stage of an instance-based procedure is empty; the model is the 756-row training set itself, and the cost is on the prediction side: 756 distances are computed for every subscriber.
• The candidate chosen on the validation set is absolute difference with 31 neighbors; the family number on the test set is 0.7937, 0.0357 above the baseline, and this number was found by trying 24 candidates.
• The same candidate’s number on the validation set is 0.8294; had the number read on the set the choice was made on been reported, the family would have seemed to gain eighteen subscribers instead of nine.
• The procedure that looks at a single neighbor falls below the baseline on the test set under all three distance metrics (0.7262, 0.7063 and 0.7262); thirteen of the twenty-four candidates fail to beat their own baseline on the validation set.
• When the column count rises from 12 to 132, the ratio of the farthest neighbor to the nearest falls from 26.91 to 1.49, and the family number settles exactly on the baseline, 0.7579.

Next Step

In this family, twelve columns melt into a single sum of distances: the region indicator and the mean consumption meet in the same sum, and which of them carries the decision is not visible. For a categorical field, “distance” is already a forced notion; after the region columns are opened into five binary columns, the difference between two different regions is always the same number. The next lesson takes a family that does not sum the columns but counts: it counts how many times each feature value is seen under each class and multiplies those counts. For the multiplication to be valid, the columns must be independent of each other given the class; in this set they are not. The lesson counts the two separate consequences of the broken assumption separately, the probability output going to the extremes and the ranking staying standing, and measures how smoothing solves the problem of a never-seen count silencing the model entirely.