17
правок
Изменения
Базовая статья Метрический классификатор и метод ближайших соседей
'''Метрический классификатор''' (англ. similarity-based classifier) {{---}} алгоритм классификации, основанный на вычислении оценок сходства между объектами.
Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</tex>. Как правило, не требуется, чтобы были выполнены все три аксиомы метрики - неравенство треугольника может нарушаться.
'''Метод ближайших соседей''' {{---}} простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
'''Метод k ближайших соседей''' (англ. knn - k nearest neighbours) {{---}} Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей — k ближайших к нему объектов обучающей выборки x_i. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
'''Метод взвешенных ближайших соседей''' {{---}} в задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда i-му соседу приписывается вес w_i, как правило, убывающий с ростом ранга соседа i. Объект относится к тому классу, который набирает больший суммарный вес среди k ближайших соседей.
== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}.</tex>
Пусть на множестве объектов задана функция расстояния <tex>\rho(x,x')</tex>. Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта <tex>x, x'</tex>.
Для произвольного объекта <tex>u</tex> расположим объекты обучающей выборки <tex>x_i</tex> в порядке возрастания расстояний до <tex>u</tex>:
<tex>\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u})</tex>,
где через <tex>x_{i; u}</tex> обозначается тот объект обучающей выборки, который является <tex>i</tex>-м соседом объекта <tex>u</tex>. Аналогичное обозначение введём и для ответа на <tex>i</tex>-м соседе: <tex>y_{i; u}</tex>. Таким образом, произвольный объект <tex>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) = [i=1]</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)</tex> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию ядра.
'''Функция ядра (ядро сглаживания)''' {{---}} неотрицательная монотонно невозрастающая функция на <tex>[0,+\infty)</tex>
Будем обозначать функцию ядра <tex>K(r)</tex>
=== Примеры ядер ===
Triangular: <tex>{\displaystyle K(r)=(1-|r|)}</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>
=== Варианты метода ближайших соседей, использующие функцию ядра ===
<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})}{\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>\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>\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)=\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].
== Пример использования (через 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)))
== См. также ==
* [[Обзор библиотек для машинного обучения на Python]]<sup>[на 30.12.18 не создан]</sup>
* [[Общие понятия]]<sup>[на 30.12.18 не создан]</sup>
== Источники информации ==
# [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80 Метрический классификатор] - статья на machinelearning.ru про метрический классификатор
# [http://www.machinelearning.ru/wiki/index.php?title=KNN knn] - статья на machinelearning.ru про knn
# [https://www.youtube.com/watch?v=l1xGQMowWA4&t=0s&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=3 лекция про knn] - Лекция из курса К.В. Воронцова
# [https://en.wikipedia.org/wiki/Kernel_(statistics) Функции ядер] - примеры ядер с Википедии
# [https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html] - документация по scikit-learn
Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</tex>. Как правило, не требуется, чтобы были выполнены все три аксиомы метрики - неравенство треугольника может нарушаться.
'''Метод ближайших соседей''' {{---}} простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
'''Метод k ближайших соседей''' (англ. knn - k nearest neighbours) {{---}} Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей — k ближайших к нему объектов обучающей выборки x_i. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
'''Метод взвешенных ближайших соседей''' {{---}} в задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда i-му соседу приписывается вес w_i, как правило, убывающий с ростом ранга соседа i. Объект относится к тому классу, который набирает больший суммарный вес среди k ближайших соседей.
== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <tex>X^m = \{(x_1,y_1),\dots,(x_m,y_m)\}.</tex>
Пусть на множестве объектов задана функция расстояния <tex>\rho(x,x')</tex>. Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта <tex>x, x'</tex>.
Для произвольного объекта <tex>u</tex> расположим объекты обучающей выборки <tex>x_i</tex> в порядке возрастания расстояний до <tex>u</tex>:
<tex>\rho(u,x_{1; u}) \leq \rho(u,x_{2; u}) \leq \cdots \leq \rho(u,x_{m; u})</tex>,
где через <tex>x_{i; u}</tex> обозначается тот объект обучающей выборки, который является <tex>i</tex>-м соседом объекта <tex>u</tex>. Аналогичное обозначение введём и для ответа на <tex>i</tex>-м соседе: <tex>y_{i; u}</tex>. Таким образом, произвольный объект <tex>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) = [i=1]</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)</tex> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию ядра.
'''Функция ядра (ядро сглаживания)''' {{---}} неотрицательная монотонно невозрастающая функция на <tex>[0,+\infty)</tex>
Будем обозначать функцию ядра <tex>K(r)</tex>
=== Примеры ядер ===
Triangular: <tex>{\displaystyle K(r)=(1-|r|)}</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>
=== Варианты метода ближайших соседей, использующие функцию ядра ===
<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})}{\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>\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>\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)=\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].
== Пример использования (через 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)))
== См. также ==
* [[Обзор библиотек для машинного обучения на Python]]<sup>[на 30.12.18 не создан]</sup>
* [[Общие понятия]]<sup>[на 30.12.18 не создан]</sup>
== Источники информации ==
# [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80 Метрический классификатор] - статья на machinelearning.ru про метрический классификатор
# [http://www.machinelearning.ru/wiki/index.php?title=KNN knn] - статья на machinelearning.ru про knn
# [https://www.youtube.com/watch?v=l1xGQMowWA4&t=0s&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=3 лекция про knn] - Лекция из курса К.В. Воронцова
# [https://en.wikipedia.org/wiki/Kernel_(statistics) Функции ядер] - примеры ядер с Википедии
# [https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html] - документация по scikit-learn
