Метрический классификатор и метод ближайших соседей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метод парзеновского окна)
Строка 5: Строка 5:
 
'''Метод ближайших соседей''' {{---}} простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
 
'''Метод ближайших соседей''' {{---}} простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
  
'''Метод k ближайших соседей''' (англ. knn - k nearest neighbours) {{---}} Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей {{---}} k ближайших к нему объектов обучающей выборки x_i. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
+
'''Метод <tex>k</tex> ближайших соседей''' (англ. knn - <tex>k</tex> nearest neighbours) {{---}} Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей {{---}} <tex>k</tex> ближайших к нему объектов обучающей выборки <tex>x_i</tex>. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
  
'''Метод взвешенных ближайших соседей''' {{---}} в задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда i-му соседу приписывается вес w_i, как правило, убывающий с ростом ранга соседа i. Объект относится к тому классу, который набирает больший суммарный вес среди k ближайших соседей.
+
'''Метод взвешенных ближайших соседей''' {{---}} в задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда <tex>i</tex>-му соседу приписывается вес <tex>w_i</tex>, как правило, убывающий с ростом ранга соседа <tex>i</tex>. Объект относится к тому классу, который набирает больший суммарный вес среди <tex>k</tex> ближайших соседей.
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
Строка 20: Строка 20:
 
<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u)</tex>,
 
<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u)</tex>,
  
где <tex>w(i,u)</tex> {{---}} заданная весовая функция, которая оценивает степень важности <tex>i</tex>-го соседа для классификации объекта <tex>u</tex>. Естественно полагать, что эта функция неотрицательна и не возрастает по <tex>i</tex>.
+
где <tex>w(i,u)</tex> {{---}} заданная весовая функция, которая оценивает степень важности <tex>i</tex>-го соседа для классификации объекта <tex>u</tex>. Естественно полагать, что эта функция неотрицательна и не возрастает по <tex>i</tex> (поскольку чем дальше объект, тем меньший вклад он должен вносить в пользу своего класса).
  
 
По-разному задавая весовую функцию, можно получать различные варианты метода ближайших соседей.
 
По-разному задавая весовую функцию, можно получать различные варианты метода ближайших соседей.
Строка 28: Строка 28:
 
<tex>w(i,u) = [i\leq k]</tex> {{---}} метод <tex>k</tex> ближайших соседей;
 
<tex>w(i,u) = [i\leq k]</tex> {{---}} метод <tex>k</tex> ближайших соседей;
  
<tex>w(i,u) = [i\leq k] q^i</tex> {{---}} метод <tex>k</tex> экспоненциально взвешенных ближайших соседей, где предполагается <tex>q < 1</tex>;
+
<tex>w(i,u) = [i\leq k] q^i</tex> {{---}} метод <tex>k</tex> экспоненциально взвешенных ближайших соседей, где предполагается константа <tex>q < 1</tex>;
  
 
== Использование ядер сглаживания ==
 
== Использование ядер сглаживания ==
При использовании ленейной функции в качестве <tex>w(i, u)</tex> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]]<sup>[на 15.01.18 не создан]</sup>.
+
При использовании линейной функции в качестве <tex>w(i, u)</tex> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]]<sup>[на 15.01.18 не создан]</sup>.
  
 
Будем обозначать функцию ядра <tex>K(r)</tex>
 
Будем обозначать функцию ядра <tex>K(r)</tex>
Строка 56: Строка 56:
  
 
<tex>a_h</tex> не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.  
 
<tex>a_h</tex> не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.  
<tex>a_k</tex> является аналогом метода k ближайших соседей (т.к. для всех <tex>k+i</tex>-ых соседей функция <tex>K</tex> вернет 0), но при этом чем ближе <tex>k-i</tex>-ый сосед, тем больший вклад в сторону своего класса он даст.
+
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <tex>k+i</tex>-ых соседей функция <tex>K</tex> вернет 0), но при этом чем ближе <tex>k-i</tex>-ый сосед, тем больший вклад в сторону своего класса он даст.
  
 
Часто используют окно переменной ширины т.е. классификатор <tex>a_k</tex>, по следующим причинам:
 
Часто используют окно переменной ширины т.е. классификатор <tex>a_k</tex>, по следующим причинам:

Версия 15:18, 17 января 2019

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

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

  • Делим данные на тренировочное и тестовое множество
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)))


См. также

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

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