Изменения

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

'''Метод <tex>k</tex> ближайших соседей''' (англ. knn kNN {{- --}} <tex>k</tex> nearest neighboursNearest 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>w(i,u)</tex> {{---}} заданная весовая функция, которая оценивает степень важности <tex>i</tex>-го соседа для классификации объекта <tex>u</tex>. Естественно полагать, что эта функция неотрицательна не отрицательна и не возрастает по <tex>i</tex> (поскольку чем дальше объект, тем меньший вклад он должен вносить в пользу своего класса).

При использовании линейной функции в качестве <tex>w(i, u)</tex> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило , используют функцию [[Ядра]]^{[на 1528.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>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>.

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].

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

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

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

* Делим данные на тренировочное и тестовое множество:

X_train, X_validationX_test, y_train, y_validation y_test = train_test_split(X, y, test_size=0.2, random_state=1234)

* Создаем классификатор:

* Обучаемся:

* Используем скользящий контроль для поиска лучших параметров (англ. cross validation):

* Оценка классификатора:

predicted = best_model.predict(X_validationX_test)

* Выводим результат:

print('Evaluation:\n', metrics.classification_report(y_validationy_test, predicted))

* [[Обзор библиотек для машинного обучения на Python]]^{[на 30.12.18 не создан]}* [[Общие понятия]]^{* [на 30.12.18 не создан[Уменьшение размерности]]}

# [http://www.machinelearning.ru/wiki/index.php?title=KNN knnkNN] - статья на machinelearning.ru про knnkNN# [https://www.youtube.com/watch?v=l1xGQMowWA4&t=0s&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=3 лекция про knnkNN] - Лекция из курса К.В. Воронцова