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

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

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

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

Метод $k$ ближайших соседей (англ. kNN — $k$ Nearest Neighbours) — Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей — $k$ ближайших к нему объектов обучающей выборки $x_i$. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры ядер

Triangular: ${\displaystyle K(r)=(1-|r|)}$

Parabolic: ${\displaystyle K(r)={\frac {3}{4}}(1-r^{2})}$

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

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

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

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

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

Фиксированной ширины: $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)$

Переменной ширины: $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)$

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

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

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

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

Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек

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

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

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

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

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

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

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

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

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

Рассмотрим использование алгоритма $knn$ на примере реального набора данных. Предположим, что мы загрузили $wdbc.data$ и сохранили как $tr.csv$ с заголовком - описанием признаков.

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

 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")

Теперь $X$, $y$ - нормированные значения признаков и соответствующие им классы.

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

from sklearn.model_selection import train_test_split

X_train, X_validation, y_train, y_validation = 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_validation)

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

print('Used params:', best_params)
print('Evaluation:\n', metrics.classification_report(y_validation, 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^{[на 30.12.18 не создан]}
• Общие понятия^{[на 30.12.18 не создан]}

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

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