Overfitting and cross-validation
A model overfits when it learns the noise and quirks of its training data instead of the underlying pattern. It then does very well on the data it has seen and worse on new data. The opposite problem, underfitting, is a model too simple to capture the pattern. The gap between training and validation performance is the main warning sign.
Python
xs = list(range(1, 13))
labels = [0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1]
def predict(train_x, train_y, x, k):
order = sorted(range(len(train_x)), key=lambda i: abs(train_x[i] - x))
votes = [train_y[i] for i in order[:k]]
return 1 if sum(votes) * 2 > len(votes) else 0
def train_accuracy(k):
return sum(predict(xs, labels, x, k) == y for x, y in zip(xs, labels)) / len(xs)
def leave_one_out_accuracy(k):
correct = 0
for i in range(len(xs)):
rest_x = xs[:i] + xs[i + 1:]
rest_y = labels[:i] + labels[i + 1:]
correct += predict(rest_x, rest_y, xs[i], k) == labels[i]
return correct / len(xs)
for k in (1, 3, 5):
print(k, round(train_accuracy(k), 3), round(leave_one_out_accuracy(k), 3))