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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации)
Строка 31: Строка 31:
  
 
== Использование ядер сглаживания ==
 
== Использование ядер сглаживания ==
При использовании ленейной функции в качестве <tex>w(i, u)</tex> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию ядра.
+
При использовании ленейной функции в качестве <tex>w(i, u)</tex> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]]<sup>[на 15.01.18 не создан]</sup>.
 
 
'''Функция ядра (ядро сглаживания)''' {{---}} неотрицательная монотонно невозрастающая функция на <tex>[0,+\infty)</tex>
 
  
 
Будем обозначать функцию ядра <tex>K(r)</tex>
 
Будем обозначать функцию ядра <tex>K(r)</tex>
Строка 45: Строка 43:
 
Tricube: <tex>{\displaystyle K(r)={\frac {70}{81}}(1-{\left|r\right|}^{3})^{3}}</tex>
 
Tricube: <tex>{\displaystyle K(r)={\frac {70}{81}}(1-{\left|r\right|}^{3})^{3}}</tex>
  
=== Варианты метода ближайших соседей, использующие функцию ядра ===
+
=== Метод парзеновского окна ===
  
 
<tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h}\biggr)</tex> {{---}} метод парзеновского окна фиксированной ширины <tex>h</tex>;
 
<tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h}\biggr)</tex> {{---}} метод парзеновского окна фиксированной ширины <tex>h</tex>;
Строка 51: Строка 49:
 
<tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{\rho(u,x_{k+1; u})}\biggr)</tex> {{---}} метод парзеновского окна переменной ширины;
 
<tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{\rho(u,x_{k+1; u})}\biggr)</tex> {{---}} метод парзеновского окна переменной ширины;
  
<tex>w(i,u) = K\biggl(\frac{\rho(u,x_{i; u})}{h(x_{i; u})}\biggr)</tex> {{---}} метод потенциальных функций, в котором ширина окна <tex>h(x_i)</tex> зависит не от классифицируемого объекта, а от обучающего объекта <tex>x_i</tex>.
+
Сравним два этих метода. Сперва запишем классификаторы, полученные при использовании этих методов, в явном виде:
 +
 
 +
Фиксированной ширины: <tex>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)</tex>
 +
 
 +
Переменной ширины: <tex>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))</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>, по следующим причинам:
 +
 
 +
1) Удобнее оптимизировать целочисленный параметр <tex>k</tex>, чем вещественный параметр <tex>h</tex> по некоторой сетке.
 +
 
 +
2) Существует большое количество задач, где точки разбросаны не равномерно. В них могут существовать области, где достаточно брать небольшую <tex>h</tex> и области, где в окно ширины <tex>h</tex> попадает только одна точка. Тогда для классификатора <tex>a_h</tex> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.  
 +
 
  
 
== Использование различных метрик расстояния ==
 
== Использование различных метрик расстояния ==

Версия 13:06, 15 января 2019

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

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

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

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

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

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

Пусть задана обучающая выборка пар «объект-ответ» [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] является аналогом метода k ближайших соседей (т.к. для всех [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