Викиконспекты - Вклад участника [ru]

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

2019-01-22T20:35:32Z

Kirant:

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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[ 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) = [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>;

[[Файл:SimpleKnnExample.png|frame|none|super|upright=1|Пример классификации, методом 5 ближайших соседей]]

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

Будем обозначать функцию ядра <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>k</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>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_h</tex> не будет учитывать соседей на расстояние больше чем <tex>h</tex>, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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) ==

Рассмотрим использование алгоритма <tex>kNN</tex> на примере [https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29 реального набора данных].
Предположим, что мы загрузили <tex>wdbc.data</tex> и сохранили как <tex>tr.csv</tex> с заголовком - описанием признаков.

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

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

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

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

* Создаем классификатор
'''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_test)

* Выводим результат
print('Used params:', best_params)
print('Evaluation:\n', metrics.classification_report(y_test, 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 меры<ref>[https://en.wikipedia.org/wiki/F1_score F1 мера]</ref> используя smile.classification.knn<ref>[https://haifengl.github.io/smile/classification.html#knn Smile, KNN]</ref>:
'''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]]
* [[Общие понятия]]
* [[Уменьшение размерности]]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn
# [https://www.kaggle.com/jeffbrown/knn-classifier/data kaggle example] - пример по работе с датасетом с kaggle

[[Категория: Машинное обучение]]
[[Категория: Метрический классификатор]]

Файл:SimpleKnnExample.png

2019-01-22T20:26:26Z

Kirant:

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

2019-01-22T10:47:29Z

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

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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[ 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) = [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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило, используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>k</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>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_h</tex> не будет учитывать соседей на расстояние больше чем <tex>h</tex>, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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) ==

Рассмотрим использование алгоритма <tex>kNN</tex> на примере [https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29 реального набора данных].
Предположим, что мы загрузили <tex>wdbc.data</tex> и сохранили как <tex>tr.csv</tex> с заголовком - описанием признаков.

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

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

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

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

* Создаем классификатор
'''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_test)

* Выводим результат
print('Used params:', best_params)
print('Evaluation:\n', metrics.classification_report(y_test, 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 меры<ref>[https://en.wikipedia.org/wiki/F1_score F1 мера]</ref> используя smile.classification.knn<ref>[https://haifengl.github.io/smile/classification.html#knn Smile, KNN]</ref>:
'''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 не создан]
* [[Уменьшение размерности]]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn
# [https://www.kaggle.com/jeffbrown/knn-classifier/data kaggle example] - пример по работе с датасетом с kaggle

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

2019-01-22T10:32:51Z

Kirant:

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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[ 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) = [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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило, используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>k</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>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_h</tex> не будет учитывать соседей на расстояние больше чем <tex>h</tex>, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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) ==

Рассмотрим использование алгоритма <tex>kNN</tex> на примере [https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29 реального набора данных].
Предположим, что мы загрузили <tex>wdbc.data</tex> и сохранили как <tex>tr.csv</tex> с заголовком - описанием признаков.

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

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

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

* Делим данные на тренировочное и тестовое множество
'''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 меры<ref>[https://en.wikipedia.org/wiki/F1_score F1 мера]</ref> используя smile.classification.knn<ref>[https://haifengl.github.io/smile/classification.html#knn Smile, KNN]</ref>:
'''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 не создан]
* [[Уменьшение размерности]]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn
# [https://www.kaggle.com/jeffbrown/knn-classifier/data kaggle example] - пример по работе с датасетом с kaggle

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

2019-01-18T20:44:29Z

Kirant:

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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[ 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) = [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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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_h</tex> не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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) ==

Рассмотрим использование алгоритма <tex>knn</tex> на примере [https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29 реального набора данных].
Предположим, что мы загрузили <tex>wdbc.data</tex> и сохранили как <tex>tr.csv</tex> с загаловком - описанием признаков.

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

'''import''' pandas '''as''' pd
'''from''' sklearn.preprocessing '''import''' StandardScaler

'''def''' load_data(data_path):
ds = pd.read_csv(data_path)
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")

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

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

== См. также ==
* [[Обзор библиотек для машинного обучения на Python]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn
# [https://www.kaggle.com/jeffbrown/knn-classifier/data kaggle example] - пример по работе с датасетом с kaggle

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

2019-01-18T20:41:46Z

Kirant:

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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[ 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) = [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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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_h</tex> не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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) ==

Рассмотрим использование алгоритма knn на примере [https://archive.ics.uci.edu/ml/datasets/Breast+Cancer+Wisconsin+%28Diagnostic%29 реального датасета].
Предположим, что мы загрузили ''wdbc.data'' и сохранили как ''tr.csv'' с загаловком - описанием признаков.

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

'''import''' pandas '''as''' pd
'''from''' sklearn.preprocessing '''import''' StandardScaler

'''def''' load_data(data_path):
ds = pd.read_csv(data_path)
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")

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

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

== См. также ==
* [[Обзор библиотек для машинного обучения на Python]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn
# [https://www.kaggle.com/jeffbrown/knn-classifier/data kaggle example] - пример по работе с датасетом с kaggle

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

2019-01-18T17:57:37Z

Kirant:

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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[ 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) = [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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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_h</tex> не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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) ==

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

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

* Выводим результат
print('Used params:', best_params)
print('Evaluation:\n', metrics.classification_report(y_validation, predicted))

> '''Used params: {'n_neighbors': 23}'''
'''Evaluation:'''
precision recall f1-score support

A 0.82 1.00 0.90 40
B 0.40 0.44 0.42 43
C 0.83 0.23 0.36 22
D 0.61 0.98 0.75 47
E 0.33 0.67 0.44 42
F 0.50 0.11 0.19 70
G 0.59 0.44 0.50 68

micro avg 0.53 0.53 0.53 332
macro avg 0.58 0.55 0.51 332
weighted avg 0.56 0.53 0.49 332

== См. также ==
* [[Обзор библиотек для машинного обучения на Python]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn

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

2019-01-18T16:37:05Z

Kirant:

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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[ 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) = [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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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_h</tex> не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|frame|none|super|upright=1|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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) ==

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

* Делим данные на тренировочное и тестовое множество
'''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]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn

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

2019-01-17T12:26:41Z

Kirant:

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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[ 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) = [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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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_h</tex> не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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) ==

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

* Делим данные на тренировочное и тестовое множество
'''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]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn

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

2019-01-17T12:18:24Z

Kirant:

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

Для формализации понятия сходства вводится функция расстояния между объектами <tex>\rho(x,x')</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> ближайших соседей.

== Описание алгоритма ==
Пусть задана обучающая выборка пар «объект-ответ» <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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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> является аналогом метода <tex>k</tex> ближайших соседей (т.к. для всех <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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn

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

2019-01-15T10:18:08Z

Kirant: /* Метод парзеновского окна */

'''Метрический классификатор''' (англ. 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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn

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

2019-01-15T10:17:20Z

Kirant:

'''Метрический классификатор''' (англ. 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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

[[Файл:KnnExample.png|Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек]]

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn

Файл:KnnExample.png

2019-01-15T10:08:03Z

Kirant:

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

2019-01-15T10:06:46Z

Kirant:

'''Метрический классификатор''' (англ. 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> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]][на 15.01.18 не создан].

Будем обозначать функцию ядра <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>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> будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

== Использование различных метрик расстояния ==
Очень редко известа хорошая функция расстояния <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]][на 30.12.18 не создан]
* [[Общие понятия]][на 30.12.18 не создан]

== Источники информации ==
# [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 sklearn] - документация по scikit-learn

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

2019-01-15T08:40:36Z

Kirant: /* Источники информации */

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

2018-12-30T17:22:42Z

Kirant: Небольшие поправки стиля и опечаток

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

2018-12-30T17:19:48Z

Kirant: Базовая статья Метрический классификатор и метод ближайших соседей