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

Метрический классификатор (англ. 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];

Пример классификации, методом 5 ближайших соседей

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

При использовании линейной функции в качестве [math]w(i, u)[/math] возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило, используют функцию Ядра^{[на 28.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]k[/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] не будет учитывать соседей на расстояние больше чем [math]h[/math], а всех остальных учтет в соответствии с функций ядра [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] по некоторой сетке;

1. Существует большое количество задач, где точки разбросаны неравномерно. В них могут существовать области, где достаточно брать небольшую [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]kNN[/math] на примере реального набора данных. Предположим, что мы загрузили [math]wdbc.data[/math] и сохранили как [math]tr.csv[/math] с заголовком — описанием признаков.

• Загружаем данные

 import pandas as pd    
 from sklearn.preprocessing import StandardScaler    

 def load_data(data_path):
     ds = pd.read_csv(data_path, names=["id", "diagnosis", "radius_mean", "texture_mean", "perimeter_mean", "area_mean",
                                      "smoothness_mean", "compactness_mean", "concavity_mean", "concave points_mean",
                                      "symmetry_mean", "fractal_dimension_mean", "radius_se", "texture_se",
                                      "perimeter_se", "area_se", "smoothness_se", "compactness_se", "concavity_se",
                                      "concave points_se", "symmetry_se", "fractal_dimension_se", "radius_worst",
                                      "texture_worst", "perimeter_worst", "area_worst", "smoothness_worst",
                                      "compactness_worst", "concavity_worst", "concave points_worst", "symmetry_worst",
                                      "fractal_dimension_worst"])
     y = ds['diagnosis']
     X = ds.drop('diagnosis', axis=1)
     X = X.drop('id', axis=1)
     i = len(X.columns)
     X = X.drop(X.columns[i - 1], axis=1)
     y.replace(('M', 'B'), (1, 0), inplace=True)
     sc = StandardScaler()
     sc.fit(X)
     X_ans = sc.transform(X)
     return X_ans, y

 X, y = load_data("tr.csv")

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

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

from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=1234)

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

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

model_params = best_model.get_params()
tuned_params = {}
for k, v in model_params.items():
    tuned_params[k] = [v]
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)
best_model.fit(X_train, y_train)
predicted = best_model.predict(X_test)

• Выводим результат:

print('Used params:', best_params)
print('Evaluation:\n', metrics.classification_report(y_test, predicted))

> Used params: {'metric_params': None, 'metric': 'euclidean', 'weights': 'distance', 'n_neighbors': 9, 'leaf_size': 30, 'n_jobs': 4, 'p': 2, 'algorithm': 'auto'}
  Evaluation:
                  precision    recall  f1-score   support
              0       0.90      1.00      0.95        69
              1       1.00      0.82      0.90        45
      micro avg       0.93      0.93      0.93       114
      macro avg       0.95      0.91      0.92       114
   weighted avg       0.94      0.93      0.93       114

Пример на языке Scala

SBT зависимость:

 libraryDependencies += "com.github.haifengl" %% "smile-scala" % "1.5.2"

Пример классификации датасета и вычисления F1 меры используя smile.classification.knn:

 import smile.classification._
 import smile.data._
 import smile.plot._
 import smile.read
 import smile.validation.FMeasure

 val toy: AttributeDataset = read.table("iris.csv", delimiter = ",", response = Some((new NumericAttribute("class"), 2)))
 val x: Array[Array[Double]] = toy.x()
 val y: Array[Int] = toy.y().map(_.toInt)
 val KNN: KNN[Array[Double]] = knn(x, y, 3)
 val predictions: Array[Int] = x.map(KNN.predict)
 val f1Score = new FMeasure().measure(predictions, y)
 plot(x, y, KNN)

См. также

• Обзор библиотек для машинного обучения на Python
• Общие понятия
• Уменьшение размерности

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

• machinelearning.ru — Метрический классификатор
• machinelearning.ru — Метод ближайших соседей (kNN)
• Лекция "Метрические методы классификации" К.В. Воронцов, курс "Машинное обучение" 2014
• Wikipedia — Kernel (statistics)
• Документация по scikit-learn
• Пример по работе с датасетом с kaggle