Метрический классификатор и метод ближайших соседей

Метрический классификатор (англ. similarity-based classifier) — алгоритм классификации, основанный на вычислении оценок сходства между объектами.

Для формализации понятия сходства вводится функция расстояния между объектами [math]\rho(x,x')[/math]. Как правило, не требуется, чтобы были выполнены все три аксиомы метрики - неравенство треугольника может нарушаться.

Метод ближайших соседей — простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.

Метод [math]k[/math] ближайших соседей (англ. knn - [math]k[/math] nearest neighbours) — Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей — [math]k[/math] ближайших к нему объектов обучающей выборки [math]x_i[/math]. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.

Метод взвешенных ближайших соседей — в задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда [math]i[/math]-му соседу приписывается вес [math]w_i[/math], как правило, убывающий с ростом ранга соседа [math]i[/math]. Объект относится к тому классу, который набирает больший суммарный вес среди [math]k[/math] ближайших соседей.

Описание алгоритма

Пусть задана обучающая выборка пар «объект-ответ» [math]X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}.[/math]

Пусть на множестве объектов задана функция расстояния [math]\rho(x,x')[/math]. Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта [math]x, x'[/math].

Для произвольного объекта [math]u[/math] расположим объекты обучающей выборки [math]x_i[/math] в порядке возрастания расстояний до [math]u[/math]:

[math]\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u})[/math], где через [math]x_{i; u}[/math] обозначается тот объект обучающей выборки, который является [math]i[/math]-м соседом объекта [math]u[/math]. Аналогичное обозначение введём и для ответа на [math]i[/math]-м соседе: [math]y_{i; u}[/math]. Таким образом, произвольный объект [math]u[/math] порождает свою перенумерацию выборки. В наиболее общем виде алгоритм ближайших соседей есть: [math]a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ y_{i; u}=y \bigr] w(i,u)[/math],

где [math]w(i,u)[/math] — заданная весовая функция, которая оценивает степень важности [math]i[/math]-го соседа для классификации объекта [math]u[/math]. Естественно полагать, что эта функция неотрицательна и не возрастает по [math]i[/math] (поскольку чем дальше объект, тем меньший вклад он должен вносить в пользу своего класса).

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

[math]w(i,u) = [i=1][/math] — простейший метод ближайшего соседа;

[math]w(i,u) = [i\leq k][/math] — метод [math]k[/math] ближайших соседей;

[math]w(i,u) = [i\leq k] q^i[/math] — метод [math]k[/math] экспоненциально взвешенных ближайших соседей, где предполагается константа [math]q \lt 1[/math];

Использование ядер сглаживания

При использовании линейной функции в качестве [math]w(i, u)[/math] возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию Ядра^{[на 15.01.18 не создан]}.

Будем обозначать функцию ядра [math]K(r)[/math]

Примеры ядер

Triangular: [math]{\displaystyle K(r)=(1-|r|)}[/math]

Parabolic: [math]{\displaystyle K(r)={\frac {3}{4}}(1-r^{2})}[/math]

Tricube: [math]{\displaystyle K(r)={\frac {70}{81}}(1-{\left|r\right|}^{3})^{3}}[/math]

Метод парзеновского окна

[math]w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h}\biggr)[/math] — метод парзеновского окна фиксированной ширины [math]h[/math];

[math]w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{\rho(u,x_{k+1; u})}\biggr)[/math] — метод парзеновского окна переменной ширины;

Сравним два этих метода. Сперва запишем классификаторы, полученные при использовании этих методов, в явном виде:

Фиксированной ширины: [math]a_h = a(u, X^m, \boldsymbol{h}, K) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ y_{i; u}=y \bigr] K\biggl(\frac{\rho(u,x_{i; u})}{h}\biggr)[/math]

Переменной ширины: [math]a_k = a(u, X^m, \boldsymbol{k}, K) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ y_{i; u}=y \bigr] K\biggl(\frac{\rho(u,x_{i; u})}{\rho(u,x_{k+1; u})}\biggr)[/math]

[math]a_h[/math] не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра [math]K[/math]. [math]a_k[/math] является аналогом метода [math]k[/math] ближайших соседей (т.к. для всех [math]k+i[/math]-ых соседей функция [math]K[/math] вернет 0), но при этом чем ближе [math]k-i[/math]-ый сосед, тем больший вклад в сторону своего класса он даст.

Часто используют окно переменной ширины т.е. классификатор [math]a_k[/math], по следующим причинам:

1) Удобнее оптимизировать целочисленный параметр [math]k[/math], чем вещественный параметр [math]h[/math] по некоторой сетке.

2) Существует большое количество задач, где точки разбросаны неравномерно. В них могут существовать области, где достаточно брать небольшую [math]h[/math] и области, где в окно ширины [math]h[/math] попадает только одна точка. Тогда для классификатора [math]a_h[/math] будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

Использование различных метрик расстояния

Очень редко известа хорошая функция расстояния [math]\rho(x,x')[/math]. В качестве нее обычно использую следующие функции:

Примеры метрик

Пусть [math]x[/math], [math]y[/math] - объекты, а [math](x_1, x_2,..., x_n)[/math], [math](y_1, y_2,..., y_n)[/math] их признаковые описания.

Евклидова метрика: [math]\rho(x,y) = \sqrt {\sum _{i=1}^{n}(x_{i}-y_{i})^{2}}[/math]

Расстояние Чебышёва: [math]\rho(x,y)=\max _{i=1,\dots ,n}|x_{i}-y_{i}|[/math]

Манхэттенское Расстояние: [math]\rho(x,y)=\sum _{i=1}^{n}|x_{i}-y_{i}|[/math]

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

Пример использования (через scikit-learn)

Пусть [math]X[/math], [math]y[/math] - нормированные значения признаков и соответствуйющие им классы.

• Делим данные на тренировочное и тестовое множество

from sklearn.model_selection import train_test_split

X_train, X_validation, y_train, y_validation = train_test_split(X, y, train_size=0.1, random_state=1234)
print(X_train.shape, X_validation.shape)

• Создаем классификатор

from sklearn.neighbors import KNeighborsClassifier

best_model = KNeighborsClassifier(
   n_neighbors=10, 
   weights=’distance’,
   algorithm=’auto’,
   leaf_size=30,
   metric=’euclidean’,
   metric_params=None,
   n_jobs=4
)

• Обучаемся

best_model.fit(X_train, y_train)

• Используем скользящий контроль для поиска лучших параметров (англ. cross validation)

from sklearn.model_selection import GridSearchCV

tuned_params = best_model.get_params()
tuned_params['n_neighbors'] = range(1, 30)
clf = GridSearchCV(KNeighborsClassifier(), tuned_params, cv=10, n_jobs=-1)
clf.fit(X_train, y_train)
best_params = clf.best_params_

• Оценка классификатора

from sklearn import metrics

best_model = KNeighborsClassifier(**best_params)
predicted = best_model.predict(X_validation)
logging.info('Used params: {0}'.format(params))
logging.info('Evaluation:\n{0}'.format(metrics.classification_report(expected, predicted)))

См. также

• Обзор библиотек для машинного обучения на Python^{[на 30.12.18 не создан]}
• Общие понятия^{[на 30.12.18 не создан]}

Источники информации

1. Метрический классификатор - статья на machinelearning.ru про метрический классификатор
2. knn - статья на machinelearning.ru про knn
3. лекция про knn - Лекция из курса К.В. Воронцова
4. Функции ядер - примеры ядер с Википедии
5. sklearn - документация по scikit-learn