Занятие 6

Введение в sklearn. KNN

Общая схема решения задачи машинного обучения

Вспомнить из лекции:

  • Что такое задача машинного обучения? Что дано и что необходимо найти?
  • Какие бывают типы признаков в машинном обучении?
  • Какие бывают виды задач в машинном обучении?
  • Что такое функционал качества? Для чего он нужен?

Вспомним общую схему решения задачи машинного обучения:

Из исходной базы данных после предобработки мы получаем обучающую выборку $X, Y$. Матрица объекты-признаки $X$ имеет размер (число объектов) $\times$ (число признаков). Одна строка этой матрицы соответствует одному объекту обучающей выборки, заданному как вектор длины (число признаков). Признаки - числовые характеристики объекта. Вектор правильных ответов $Y$ имеет длину (число объектов).

На этапе обучения на основе обучающей выборки $X, Y$ строится (обучается) алгоритм $a(x)$. Это некая функция, которая берет на вход признаки объекта и возвращает предсказание для этого объекта: $y \approx a(x)$. Алгоритм $a$ может делать предсказания для любых допустимых объектов; его можно применять как к обучающим объектам, так и к тем, которых алгоритм никогда не видел. В этом и состоит цель машинного обучения: выявить такие закономерности в обучающей выборке, которые позволят делать качественные (довольно точные) предсказания на новых объектах $x$.

Тому, как обучать такие алгоритмы $a(x)$ по обучающей выборке, во многом ипосвящен наш курс.

Интерфейс Scikit-Learn

Scikit-Learn, или коротко Sklearn - библиотека, в которой реализованы практически все используемые сегодня алгоритмы машинного обучения. Нам необходимо познакомиться с интерфейсом библиотеки, чтобы понимать, как ее можно использовать на практике. Далее в курсе мы будем не только использовать готовые реализации из sklearn, но иногда и сами реализовывать алгоритмы в том же духе, в котором это сделано в этой библиотеке (с тем же интерфейсом).

Для реализации алгоритмов машинного обучения в sklearn всегда используется один интерфейс - класс с функциями fit(X, Y) для обучения модели по обучающей выборке $X, Y$ и predict(X) для возвращения предсказаний на выборке $X$. При создании класса можно указывать дополнительные параметры, влияющие на работу алгоритма машинного обучения.

Например, такова будет логика работы класса линейной регрессии, которую мы подробно изучим на следующих семинарах:

  • При создании класса нужно запомнить коэффициент регуляризации;
  • Задача функции fit - по выборке X и Y найти веса w и сохранить их внутри класса в self.w;
  • Задача функции predict - по весам self.w и X вернуть предсказания $Y$.
In [ ]:
import numpy as np
import pandas as pd
In [ ]:
class LinearRegressor:
    def __init__(self, reg_coef: float = None) -> None:
        self.lambda_ = reg_coef
    
    def fit(self, X_train: np.array, y_train: np.array) -> None:
        self.w =  # формула для вычисления весов, X, y и self.lambda_
    
    def predict(self, X_test: np.array) -> np.array:
        y_pred =  # функция от X и self.w
        
        return y_pred

Если бы не использовали класс, нам пришлось бы передавать веса w в функцию predict каждый раз, когда мы захотели бы сделать предсказания, это неудобно (особенно если таких вспомогательных переменных много). А так веса хранятся внутри класса, и мы можем даже не догадываться об их существовании (если класс писали не мы).

Пример импорта классификатора из sklearn:

In [ ]:
from sklearn.dummy import DummyClassifier

Помимо алгоритмов обучения и предсказания для разных методов, в sklearn реализовано много вспомогательного функционала для предобработки данных, визуализации данных, вычисления метрик качества и т. д. В ходе следующих семинаров мы постепенно познакомимся с этим функционалом библиотеки.

Сегодня мы познакомимся с методами предобработки данных и их реализацией в sklearn.

Предобработка данных

Для демонстраций загрузим набор данных Automobile Data Set. В данных присутствуют категориальные, целочисленные и вещественнозначные признаки.

In [ ]:
X_raw = pd.read_csv(
    "http://archive.ics.uci.edu/ml/machine-learning-databases/autos/imports-85.data", 
    header=None, 
    na_values=["?"]
)
X_raw.head()

Разделим признаки и целевую переменную:

In [ ]:
y = X_raw[25]
X_raw = X_raw.drop(25, axis=1)

Заполнение пропусков

В матрице объекты-признаки могут быть пропущенные значения, и это вызовет исключение при попытке передать такую матрицу в функцию обучения модели или даже предобработки. Если пропусков немного, можно удалить объекты с пропусками из обучающей выборки. Заполнить пропуски можно разными способами:

  • заполнить средними (mean, median);
  • предсказывать пропущенные значения по непропущенным.

Последний вариант сложный и применяется редко. Для заполнения константами можно использовать метод датафрейма fillna, для замены средними - класс impute.SimpleImputer.

In [ ]:
from sklearn.impute import SimpleImputer
In [ ]:
# для удобства работы с нашим датасетом создаем маску, указывающую на столбцы с категориальными признаками
# категориальные признаки имеют тип "object"
cat_features_mask = (X_raw.dtypes == "object").values

# для вещественнозначных признаков заполним пропуски средними
X_real = X_raw[X_raw.columns[~cat_features_mask]]
mis_replacer = SimpleImputer(strategy="mean")
X_no_mis_real = pd.DataFrame(data=mis_replacer.fit_transform(X_real), columns=X_real.columns)

# для категориальных - пустыми строками
X_cat = X_raw[X_raw.columns[cat_features_mask]].fillna("")
X_no_mis = pd.concat([X_no_mis_real, X_cat], axis=1)

X_no_mis.head()

Всегда нужно анализировать, случайны ли пропуски в каком-то признаке. Иногда факт отсутствия информации о значении признака может сам быть важным признаком, который необходимо добавить к другим признакам.

Пример: предсказание возраста пользователя по данным с его телефона. Поскольку люди старшего возраста чаще пользуются простыми телефонами, факт отсутствия каких-то данных (например, истории посещенных интернет-страниц), скорее всего, будет хорошим признаком.

Для категориальных признаков рекомендуется создавать отдельную категорию, соответствующую пропущенному значению. В наши данных пропусков в категориальных признаках нет.

Преобразование нечисловых признаков

Практически все методы машинного обучения требуют, чтобы на вход функции обучения подавалась вещественная матрица. В процессе обучения используются свойства вещественных чисел, в частности, возможность сравнения и применения арифметических операций. Поэтому, даже если формально в матрице объекты-признаки записаны числовые значения, нужно всегда анализировать, можно ли относиться к ним как к числам.

Пример: некоторые признаки могут задаваться целочисленными хешами или id (например, id пользователя соц. сети), однако нельзя сложить двух пользователей и получить третьего, исходя из их id (как это может сделать линейная модель).

Это пример категориального признака, принимающего значения из неупорядоченного конечного множества $K$. К таким признакам обычно применяют one-hot encoding (вместо одного признака создают $K$ бинарных признаков - по одному на каждое возможное значение исходного признака). В sklearn это можно сделать с помощью классов LabelEncoder + OneHotEncoding, но проще использовать функцию pd.get_dummies.

Следует заметить, что в новой матрице будет очень много нулевых значений. Чтобы не хранить их в памяти, можно задать параметр OneHotEncoder(sparse = True) или .get_dummies(sparse=True), и метод вернет разреженную матрицу, в которой хранятся только ненулевые значения. Выполнение некоторых операций с такой матрицей может быть неэффективным, однако большинство методов sklearn умеют работать с разреженными матрицами.

In [ ]:
print(f"Shape before encoding: {X_no_mis.shape}")
X_dum = pd.get_dummies(X_no_mis, drop_first=True)
X_dum

Помимо категориальных, преобразования требуют, например, строковые признаки. Их можно превращать в матрицу частот слов CountVectorizer, матрицу частот буквосочетаний фиксированной длины, можно извлекать другие признаки (например, длина строки).

Масштабирование признаков

При начале работы с данными всегда рекомендуется приводить все признаки к одному масштабу. Это важно для численной устойчивости при работе с матрицей объекты-признаки (рядом с нулем чисел с плавающей точкой больше, чем с области больших чисел). Кроме того, у каждого метода машинного обучения есть свои особенности, требующие масштабирования признаков. Например, для линейных моделей - это ускорение обучения и повышение интерпретируемости модели.

Первый популярный способ масштабирования - нормализация: вычитание среднего из каждого признака и деление на стандартное отклонение (StandardScaler в sklearn). Второй популярный способ: вычитание минимума из каждого признака, а затем деление на разницу максимального и минимального значения (MinMaxScaler в sklearn).

In [ ]:
from sklearn import preprocessing

normalizer = preprocessing.MinMaxScaler()
X_real_norm_np = normalizer.fit_transform(X_dum)
X = pd.DataFrame(data=X_real_norm_np)
X.head()

Пример реализации

Реализуем класс для нормализации данных по аналогии с интерфейсом sklearn для нормализации.

Предобработка данных в sklearn реализована по похожему шаблону, что и обучение моделей: функция .fit(X) запоминает внутренние переменные, а функция .transform(X) выполняет преобразование выборки. y здесь не нужен, потому что в нормализации целевые переменные не участвуют (как и почти во всей предобработке данных).

Параметров у класса нет, так что функцию __init__ мы пропускаем. Функция .fit() считает статистики - среднееи стандартное отклонение каждого признака (по обучающей выборке), а функция .tranform() вычитает среднее и делит на стандартное отклонение. Для вычисления статистик используем numpy.

In [ ]:
class Normalizer:
    def fit(self, X: np.array) -> None:
        self.mu = X.mean(axis=0)
        self.sigma = X.std(axis=0)
        
    def transform(self, X: np.array) -> np.array:
        return (X - self.mu[np.newaxis, :]) / self.sigma[np.newaxis, :]

Создаем случайные данные X и y для тестирования нашего класса:

In [ ]:
num_obj_train = 20
num_obj_te = 10
num_feat = 4
X_train = np.random.randint(-5, 5, size=(num_obj_train, num_feat))
X_train.shape
In [ ]:
X_test = np.random.randint(-5, 5, size=(num_obj_te, num_feat))
X_test.shape
In [ ]:
X_train

Создаем объект класса и трансформируем выборку:

In [ ]:
normalizer = Normalizer()
normalizer.fit(X_train)
X_train_transformed = normalizer.transform(X_train)
X_test_transformed = normalizer.transform(X_test)

Fit нужно вызывать именно на обучающих данных, чтобы ничего не подсмотреть в контрольной выборке. А transform можно вызывать много раз для любых выборок (с уже посчитанным статистиками, которые хранятся внутри класса).

In [ ]:
X_train_transformed

Метрические методы. k Nearest Neighbours

Теоретическая часть

Вспомнить из лекции:

  • Как в методе k ближайших соседей выполняются предсказания в задаче классификаци и регрессии?
  • Что такое гипотеза компактности?
  • Какие функции расстояния можно использовать для вещественных признаков, категориальных признаков, строковых признаков, множественнозначных признаков?

Задача 1.

Предположим, мы решаем задачу классификации на три класса по двум признакам и используем метод k ближайших соседей с k=3 и манхэттанской метрикой. Мы имеем следующую обучающую выборку:

Признак 1 Признак 2 Класс
1 -1 1
2 2 1
3 2 2
1 0 3
2 -2 3

Каковы будут предсказания для объекта $x=(2, -1)$?

Решение.

Алгоритм предсказания kNN для задачи классификации:

  1. Вычислить расстояние от каждого объекта обучающей выборки до тестового объекта.
  2. Найти k объектов обучающей выборки (соседей) с наименьшим расстоянием до тестового объекта.
  3. Вернуть наиболее встречающийся класс среди k соседей.

Вычислим расстояния. Расстояние от первого объекта в обучении до тестового объекта $x$ (манхэттэнская метрика):

$$|1-2| + |-1-(-1)| = 1.$$

Аналогично для 2-5 объектов: получатся расстояния 3, 4, 2, 1.

Находим 3 ближайших объекта: это объекты с номерами 1, 4, 5 (расстояния 1, 2, 1 соответственно). Эти три объекта относятся к классам 1, 3, 3. Чаще всего встречается класс 3, поэтому предсказываем 3.

Задача 2.

Визуализируйте разделяющую поверхность между классами для следующей выборки:

Признак 1 Признак 2 Класс
2 2 1
3 2 1
2 0 2
1 -1 3
1 1 3

Используйте k=1 и евклидово расстояние.

Решение.

В задачах классификации с двумя признаками мы можем изобразить признаковое пространство на плоскости и раскрасить его в разные цвета в соответствии с классом каждой точки плоскости. В этом и состоит сейчас наша задача.

Для начала отобразим на плоскости обучающую выборку - пять точек - в соответствии с их координатами.

При $k=1$ каждая точка плоскости будет относиться к тому же классу, что и ближайший к ней объект обучающей выборки. Если нам даны две точки разных классов, то чтобы провести между ними границу классов, нужно построить серединный перпендикудяр. Для случая с несколькими точками нужно построить несколько серединных перпендикуляров, найти их точки пересечения и определить, какие области к каким классам относятся. Более строго такая конструкция задается с помощью Диаграммы Вороного, но мы не будем вдаваться в ее детали.

Задача 3.

Предположим, мы решаем задачу регрессии по двум признакам и используем метод k ближайших соседей с k=3 и манхэттанской метрикой. Мы имеем следующую обучающую выборку:

Признак 1 Признак 2 Ответ
1 -1 3.5
2 2 2.3
3 2 1.7
1 0 -0.4
2 -2 0.1

Каковы будут предсказания для объекта $x=(2, -1)$?

Решение. Предсказания kNN для регрессии отличаются от предсказаний для классификации только финальным шагом: вместо поиска наиболее часто встречающегося класса нужно усреднить ответы на соседях. Признаки в этой задаче те же, что в задаче 1, поэтому соседей мы уже знаем: это объекты с номерами 1, 4, 5. На них мы имеем ответы 3.5, -0.3, 0.1. Усредним их: (3.5-0.4+0.1)/3 = 1.1. Предсказываем 1.1.

Вопрос: каковы параметры и гиперпараметры метода kNN?

Ответ:

Параметры - это величины, которые мы настраиваем в процессе обучения по обучающей выборке. В методе kNN нет как такового обучения - это очень простой эвристический алгоритм. Под параметрами в kNN можно понимать обучающую выборку. В другой трактовке у метода нет параметров.

Гиперпараметры - это величины, которые мы должны установить до начала обучения модели. Гиперпараметры не настраиваются по обучающей выборке в процессе обучения модели. Два самых важных гиперпараметры метода kNN - это число соседей k и метрика. Используя разные комбинации этих гиперпараметров, можно получать совершенно разное качество работы алгоритма. Гиперпараметры обычно настраивают по валидационной выборке или используя кросс-валидацию.

Какова динамика качества работы kNN при увеличении k?

Ответ:

При $k=1$ вокруг каждого объекта обучающей выборки создается область его класса. Если, к примеру, в "большую" область одного класса случайно попал один шумовой объект другого класса, вокруг этого шумового объекта будет "остров" предсказания другого класса. Это нелогично и говорит о переобучении.

При $k$, равном числу объектов в выборке, для всех объектов будет предсказываться одно и то же, что вновь говорит о низком качестве работы классификатора. Получается, что качество kNN при увеличении $k$ должно сначала расти, а потом падать, и оптимум будем где-то посередине.

Рассмотрим синтетический пример: на рисунке визуализирована обучающая выборка ("настоящая" разделяющая поверхность - прямая) и разделяющая поверхность kNN по аналогии с задачей 2, и на разных графиках используется разное число соседей $k$:

При использовании малых $k$ разделяющая поверхность слишком сложная, на нее оказывают сильное воздействие шумовые объекты. Далее поверхность становится все ровнее и ровнее и при $k=50$ выглядит наиболее разумно. При большем k разделяющая поверхность уходит от линейной, и оранжевый класс "захватывает" синий.

Почему при использовании kNN важно нормировать данные?

Ответ:

Рассмотрим для примера манхэттэнскую метрику. Если один признак будет иметь масштаб около 1000, а другой - около 1, то когда мы будем складывать модули разностей для этих двух признаков, второй признак практически не будет иметь влияния на ответ. Если же признаки отнормировать, но они все будут в одной шкале.

Практическая часть

In [ ]:
import numpy as np
import pandas as pd
import sklearn

# изображения цифр
from sklearn.datasets import load_digits
# классификатор
from sklearn.neighbors import KNeighborsClassifier
# шаффлер данных
from sklearn.utils import shuffle
In [ ]:
clf = KNeighborsClassifier(n_neighbors=3)

data = load_digits()
X = data.images
y = data.target

X.shape
In [ ]:
# вытягиваем квадратное изображение в вектор, чтобы получить матрицу объекты-признаки
X = X.reshape(X.shape[0], -1)

# перемешиваем данные
X, y = shuffle(X, y)
print(f"Features shape: {X.shape},\nTarget shape: {y.shape}")
print(f"Target samples: {y[:10]}")
In [ ]:
X_train, y_train = X[:700, :], y[:700]
X_val, y_val = X[700:1300, :], y[700:1300]
X_test, y_test = X[1300:, :], y[1300:]
In [ ]:
# Обучаем классификатор и делаем предсказания
clf.fit(X_train, y_train)
y_predicted = clf.predict(X_test)
In [ ]:
# Вычисляем простейшую метрику качества алгоритма - долю правильных ответов
print("Accuracy is: ", np.mean(y_test==y_predicted))

Учитывая, что у нас 10 классов, то вероятность угадать правильный ответ много раз очень мала. Поэтому полученное значение accuracy - очень хороший результат!

Попробуем использовать разные значения гиперпараметра k. Сравнивать разные значения k по обучающей выборке бесполезно: каждый объект является ближайшим сам к себе и оптимальное k будет равно 1. Будем сравнивать разные k по качеству на валидационной выборке:

In [ ]:
# Подбор k на валидационной выборке:
k_best = -1
best_accuracy = 0

for k in range(1, 20):
    y_predicted = KNeighborsClassifier(n_neighbors=k).fit(X_train, y_train).predict(X_val)

    val_accuracy = np.mean(y_predicted==y_val)                      
    print(f"k = {k}; accuracy = {val_accuracy:.3f}")
                           
    if val_accuracy > best_accuracy:
        best_accuracy = val_accuracy
        k_best = k

k_best

Сравним accuracy на обучении, валидации и тесте для найденного лучшего значения k:

In [ ]:
clf = KNeighborsClassifier(n_neighbors=k_best)
clf.fit(X_train, y_train)

for X_data, y_data in zip([X_train, X_val, X_test], [y_train, y_val, y_test]):
    y_predicted = clf.predict(X_data)
    print(f"Accuracy: {np.mean(y_predicted==y_data):.3f}")

Качество на обучающей выборке самое лучшее, но оно обманчиво, ведь алгоритм уже знает эти объекты. На валидационной выборке мы тоже использовали ответы - уже для подбора гиперпараметра k, так что этот показатель тоже не совсем честный. И действительно, качество на тестовой выборке (ответы для которой мы нигде не подсматривали) может оказаться хуже, чем на валидационной выборке.

Вывод: оценивать качество алгоритма нужно на отложенной выборке, которая не используется нигде в обучении и не используется в подборе гиперпараметров.