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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 7: Строка 7:
 
'''Метод <tex>k</tex> ближайших соседей''' (англ. kNN {{---}} <tex>k</tex> Nearest Neighbours) {{---}} Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей {{---}} <tex>k</tex> ближайших к нему объектов обучающей выборки <tex>x_i</tex>. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
 
'''Метод <tex>k</tex> ближайших соседей''' (англ. kNN {{---}} <tex>k</tex> Nearest Neighbours) {{---}} Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей {{---}} <tex>k</tex> ближайших к нему объектов обучающей выборки <tex>x_i</tex>. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
  
'''Метод взвешенных ближайших соседей''' {{---}} в задачах с числом классов 3 и более нечётность уже не помогает и ситуации неоднозначности всё равно могут возникать. Тогда <tex>i</tex>-му соседу приписывается вес <tex>w_i</tex>, как правило, убывающий с ростом ранга соседа <tex>i</tex>. Объект относится к тому классу, который набирает больший суммарный вес среди <tex>k</tex> ближайших соседей.
+
'''Метод взвешенных ближайших соседей''' {{---}} в задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда <tex>i</tex>-му соседу приписывается вес <tex>w_i</tex>, как правило, убывающий с ростом ранга соседа <tex>i</tex>. Объект относится к тому классу, который набирает больший суммарный вес среди <tex>k</tex> ближайших соседей.
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
Пусть задана обучающая выборка пар "объект-ответ" <tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}.</tex>
+
Пусть задана обучающая выборка пар «объект-ответ» <tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}.</tex>
  
 
Пусть на множестве объектов задана функция расстояния <tex>\rho(x,x')</tex>. Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта <tex>x, x'</tex>.
 
Пусть на множестве объектов задана функция расстояния <tex>\rho(x,x')</tex>. Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта <tex>x, x'</tex>.
Строка 20: Строка 20:
 
<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ y_{i; u}=y \bigr] w(i,u)</tex>,
 
<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ y_{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> (поскольку чем дальше объект, тем меньший вклад он должен вносить в пользу своего класса).
  
 
По-разному задавая весовую функцию, можно получать различные варианты метода ближайших соседей.
 
По-разному задавая весовую функцию, можно получать различные варианты метода ближайших соседей.
Строка 39: Строка 39:
 
=== Примеры ядер ===
 
=== Примеры ядер ===
  
Triangular: <tex>{\displaystyle K(r)=(1-|r|)}</tex>,
+
Triangular: <tex>{\displaystyle K(r)=(1-|r|)}</tex>
  
Parabolic: <tex>{\displaystyle K(r)={\frac {3}{4}}(1-r^{2})}</tex>,
+
Parabolic: <tex>{\displaystyle K(r)={\frac {3}{4}}(1-r^{2})}</tex>
  
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>
  
 
=== Метод парзеновского окна ===
 
=== Метод парзеновского окна ===
Строка 55: Строка 55:
 
Сравним два этих метода. Сперва запишем классификаторы, полученные при использовании этих методов, в явном виде:
 
Сравним два этих метода. Сперва запишем классификаторы, полученные при использовании этих методов, в явном виде:
  
Фиксированной ширины: <tex>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)</tex>,
+
Фиксированной ширины: <tex>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)</tex>
  
Переменной ширины: <tex>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)</tex>.
+
Переменной ширины: <tex>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)</tex>
  
 
<tex>a_h</tex> не будет учитывать соседей на расстояние больше чем <tex>h</tex>, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.  
 
<tex>a_h</tex> не будет учитывать соседей на расстояние больше чем <tex>h</tex>, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.  
Строка 64: Строка 64:
 
Часто используют окно переменной ширины т.е. классификатор <tex>a_k</tex>, по следующим причинам:
 
Часто используют окно переменной ширины т.е. классификатор <tex>a_k</tex>, по следующим причинам:
  
# Удобнее оптимизировать целочисленный параметр <tex>k</tex>, чем вещественный параметр <tex>h</tex> по некоторой сетке;
+
1) Удобнее оптимизировать целочисленный параметр <tex>k</tex>, чем вещественный параметр <tex>h</tex> по некоторой сетке.
  
# Существует большое количество задач, где точки разбросаны неравномерно. В них могут существовать области, где достаточно брать небольшую <tex>h</tex> и области, где в окно ширины <tex>h</tex> попадает только одна точка. Тогда для классификатора <tex>a_h</tex> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.  
+
2) Существует большое количество задач, где точки разбросаны неравномерно. В них могут существовать области, где достаточно брать небольшую <tex>h</tex> и области, где в окно ширины <tex>h</tex> попадает только одна точка. Тогда для классификатора <tex>a_h</tex> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.  
  
 
[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]
 
[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]
  
 
== Использование различных метрик расстояния ==
 
== Использование различных метрик расстояния ==
Очень редко известна хорошая функция расстояния <tex>\rho(x,x')</tex>. В качестве нее обычно использую следующие функции:
+
Очень редко известа хорошая функция расстояния <tex>\rho(x,x')</tex>. В качестве нее обычно использую следующие функции:
  
 
=== Примеры метрик ===
 
=== Примеры метрик ===
 
Пусть <tex>x</tex>, <tex>y</tex> {{---}} объекты, а <tex>(x_1, x_2,..., x_n)</tex>, <tex>(y_1, y_2,..., y_n)</tex> их признаковые описания.
 
Пусть <tex>x</tex>, <tex>y</tex> {{---}} объекты, а <tex>(x_1, x_2,..., x_n)</tex>, <tex>(y_1, y_2,..., y_n)</tex> их признаковые описания.
  
Евклидова метрика: <tex>\rho(x,y) = \sqrt {\sum _{i=1}^{n}(x_{i}-y_{i})^{2}}</tex>,
+
Евклидова метрика: <tex>\rho(x,y) = \sqrt {\sum _{i=1}^{n}(x_{i}-y_{i})^{2}}</tex>
  
Расстояние Чебышёва: <tex>\rho(x,y)=\max _{i=1,\dots ,n}|x_{i}-y_{i}|</tex>,
+
Расстояние Чебышёва: <tex>\rho(x,y)=\max _{i=1,\dots ,n}|x_{i}-y_{i}|</tex>
  
Манхэттенское Расстояние: <tex>\rho(x,y)=\sum _{i=1}^{n}|x_{i}-y_{i}|</tex>.
+
Манхэттенское Расстояние: <tex>\rho(x,y)=\sum _{i=1}^{n}|x_{i}-y_{i}|</tex>
  
  
При их использовании важно нормировать значения признаков, иначе один признак с максимальным значением может стать преобладающим, а признаки с маленькими значениями не будут учитываться при классификации. Чтобы отсеять лишние признаки (т.е. не влияющие на класс объекта) можно использовать [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8 feature selection].
+
При их использовании важно нормировать значения признаков, иначе один признак с максимальным значением может стать приобладающим, а признаки с маленькими значениями не будут учитываться при классификации. Чтобы отсеить лишние признаки (т.е. не влияющие на класс объекта) можно использовать [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A3%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8 feature selection].
  
 
== Пример использования (через scikit-learn) ==
 
== Пример использования (через scikit-learn) ==
  
 
Рассмотрим использование алгоритма <tex>kNN</tex> на примере [https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29 реального набора данных].
 
Рассмотрим использование алгоритма <tex>kNN</tex> на примере [https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29 реального набора данных].
Предположим, что мы загрузили <tex>wdbc.data</tex> и сохранили как <tex>tr.csv</tex> с заголовком {{---}} описанием признаков.
+
Предположим, что мы загрузили <tex>wdbc.data</tex> и сохранили как <tex>tr.csv</tex> с заголовком - описанием признаков.
  
 
* Загружаем данные
 
* Загружаем данные
Строка 118: Строка 118:
  
 
   
 
   
Теперь <tex>X</tex>, <tex>y</tex> {{---}} нормированные значения признаков и соответствующие им классы.
+
Теперь <tex>X</tex>, <tex>y</tex> - нормированные значения признаков и соответствующие им классы.
  
* Делим данные на тренировочное и тестовое множество:
+
* Делим данные на тренировочное и тестовое множество
 
  '''from''' sklearn.model_selection '''import''' train_test_split
 
  '''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)
 
  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
 
  '''from''' sklearn.neighbors '''import''' KNeighborsClassifier
  
Строка 138: Строка 138:
 
  )
 
  )
  
* Обучаемся:
+
* Обучаемся
  
 
  best_model.fit(X_train, y_train)
 
  best_model.fit(X_train, y_train)
 
   
 
   
  
* Используем скользящий контроль для поиска лучших параметров (англ. cross validation):
+
* Используем скользящий контроль для поиска лучших параметров (англ. cross validation)
 
  '''from''' sklearn.model_selection '''import''' GridSearchCV
 
  '''from''' sklearn.model_selection '''import''' GridSearchCV
  
Строка 155: Строка 155:
 
  best_params = clf.best_params_
 
  best_params = clf.best_params_
  
* Оценка классификатора:
+
* Оценка классификатора
 
  '''from''' sklearn '''import''' metrics
 
  '''from''' sklearn '''import''' metrics
  
Строка 162: Строка 162:
 
  predicted = best_model.predict(X_test)
 
  predicted = best_model.predict(X_test)
  
* Выводим результат:
+
* Выводим результат
 
  print('Used params:', best_params)
 
  print('Used params:', best_params)
 
  print('Evaluation:\n', metrics.classification_report(y_test, predicted))
 
  print('Evaluation:\n', metrics.classification_report(y_test, predicted))

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: