Что такое метрический классификатор

Метрический классификатор

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

Для формализации понятия сходства вводится функция расстояния между объектами . Как правило, жёсткого требования, чтобы эта функция была метрикой не предъявляется; в частности , неравенство треугольника вполне может и нарушаться.

Разновидности метрических алгоритмов

К метрическим алгоритмам классификации относятся:

• Метод ближайших соседей
• Метод потенциальных функций
• Метод радиальных базисных функций
• Метод парзеновского окна
• Метод дробящихся эталонов
• Алгоритм вычисления оценок

Кроме метрических классификаторов, в машинном обучении имеется широкий класс методов, также использующих информацию о сходстве объектов, но для решения других задач:

• Кластеризация
• Непараметрическая регрессия
• Многомерное шкалирование
• Визуализация, в частности, Карта сходства и Карта Кохонена

Гипотеза компактности

Метрические классификаторы опираются на гипотезу компактности, которая предполагает, что схожие объекты чаще лежат в одном классе, чем в разных. Это означает, что граница между классами имеет достаточно простую форму, и классы образуют компактно локализованные области в пространстве объектов. Заметим, что в математическом анализе компактными называются ограниченные замкнутые множества. Гипотеза компактности не имеет ничего общего с этим понятием, и пониматься скорее в «бытовом» смысле слова.

Беспризнаковое распознавание

В метрических алгоритмах классифицируемый объект может описываться не набором признаков, а непосредственно вектором расстояний до остальных объектов обучающей выборки. В таких случаях говорят также о беспризнаковом распознавании.

Например, сходство текстов, химических формул, аминокислотных последовательностей, и т.п. гораздо проще измерять непосредственно, чем переходя к признаковым описаниям.

Проблема выбора метрики

В практических задачах классификации редко встречаются такие «идеальные случаи», когда заранее известна хорошая функция расстояния. Если объекты описываются числовыми векторами, часто берут евклидову метрику. Этот выбор, как правило, ничем не обоснован — просто это первое, что приходит в голову. При этом необходимо помнить, что все признаки должны быть измерены «в одном масштабе», лучше всего — отнормированы. В противном случае признак с наибольшими числовыми значениями будет доминировать в метрике, остальные признаки, фактически, учитываться не будут.

Однако и нормировка является весьма сомнительной эвристикой, так как остаётся вопрос: «неужели все признаки одинаково значимы и должны учитываться примерно с одинаковым весом?»

Если признаков слишком много, а расстояние вычисляется как сумма отклонений по отдельным признакам, то возникает проблема проклятия размерности. Суммы большого числа отклонений с большой вероятностью имеют очень близкие значения (согласно закону больших чисел). Получается, что в пространстве высокой размерности все объекты примерно одинаково далеки друг от друга; в частности , выбор ближайших соседей становится практически случайным.

Проблема решается путём отбора относительно небольшого числа информативных признаков (features selection). В алгоритмах вычисления оценок строится множество различных наборов признаков (т.н. опорных множеств), для каждого строится своя функция близости, затем по всем функциям близости производится голосование.

Рассуждения на основе прецедентов

Парадигма CBR, case based-reasoning, возникла как одно из направлений искусственного интеллекта. В экспертных системах важно не только классифицировать объекты, но и выдавать пользователю объяснение предлагаемой классификации. В методе ближайшего соседа такие объяснения выглядят весьма разумно: «Объект отнесён к классу потому, что к этому же классу относился близкий объект обучающей выборки ». Такая «прецедентная» логика хорошо понятна экспертам во многих предметных областях (медицине, геологии, юриспруденции).

Литература

1. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
2. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
3. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
4. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.

Ссылки

• Машинное обучение (курс лекций, К.В.Воронцов). МФТИ (2004), ВМиК МГУ (2007).

ОБОБЩЁННЫЙ МЕТРИЧЕСКИЙ КЛАССИФИКАТОР

Описанные выше алгоритмы классификации являются частными случаями одной общей формулы.

Пусть задана весовая функция w(i, u), которая оценивает степень важности i-го соседа для классификации объекта u. Естественно полагать, что эта функция неотрицательна и не возрастает по i. Согласно гипотезе компактности чем меньше i, тем ближе объекты u и x_i,u, тем выше шансы, что они принадлежат одному классу.

Метрическим алгоритмом классификации с обучающей выборкой X? будем называть отображение вида

Алгоритм a относит объект u к тому классу, для которого суммарный вес ближайших обучающих объектов Г_y(u) ? Г_y(u, X ? ) максимален.

Выбирая весовую функцию w(i, u), можно получать различные типы метрических алгоритмов классификации: w(i, u) = [i = 1] — ближайший сосед;

w(i, u) = [i ? k] — k ближайших соседей;

w(i, u) = [i ? k] q i — k взвешенных ближайших соседей;

w(i, u) = K(p(u,x_i,u)/h) — парзеновское окно фиксированной ширины h;w(i, u) = K() — парзеновское окно переменной ширины.

Обучающая выборка X ? играет роль параметра алгоритма a. Настройка сводится к запоминанию выборки, и, возможно, оптимизации ещё каких-то параметров, однако сами объекты не подвергаются обработке и сохраняются «как есть». По этой причине метрические алгоритмы относятся к методам вывода на основе прецедентов (case-based reasoning, CBR). Здесь действительно можно говорить о «выводе», так как на вопрос «почему объект u был отнесён к классу y» алгоритм может дать понятный эксперту ответ: «потому, что имеются прецеденты — схожие с ним объекты, принадлежащие классу y», и предъявить список этих прецедентов.

Понятие отступа объекта

Общая формула позволяет ввести характеристику объектов, показывающую, насколько глубоко объект погружён в свой класс.

Отступом (margin) объекта xi ? X? относительно алгоритма вида

Понятие «отступ» можно трактовать как «расстояние от объекта до поверхности, отделяющей свой класс от всех остальных». Величина отступа показывает степень граничности объекта.

Отступ M(x_i) отрицателен тогда и только тогда, когда алгоритм допускает ошибку: a(x_i) y_i. Большой отрицательный отступ свидетельствует о том, что объект xi окружён объектами чужих классов — такие объекты называют шумовыми или выбросами. Большой положительный отступ означает, что объект окружён объектами своего класса — это наиболее типичные, эталонные представители классов. Отступ, близкий к нулю, означает, что объект xi является пограничным — на таких объектах классификация неустойчива в том смысле, что малые изменения в составе обучающей выборки могут приводить к ошибочной классификации объекта x_i. В выборках избыточно большого объёма выделяется масса объектов с большим положительным отступом — это неинформативные объекты, которые правильно классифицируются по ближайшим к ним эталонам и фактически не несут никакой новой информации. Таким образом, распределение отступов позволяет выделить четыре категории объектов: шумовые, пограничные, неинформативные и эталонные. Из них шумовые и неинформативные целесообразно удалять из выборки.

Распределение значений отступов в выборке даёт полезную дополнительную информацию не только об отдельных объектах, но и о выборке в целом. Если основная масса объектов имеет положительные отступы, то разделение выборки произошло успешно. Если же значения отступов концентрируются вблизи нуля, значит, почти все объекты являются граничными, и гипотеза компактности не выполняется. Это означает, что в данной задаче при выбранной метрике применять алгоритмы типа kNN бесполезно.

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

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

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

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

Метод [math]k[/math] ближайших соседей (англ. kNN — [math]k[/math] Nearest Neighbours) — Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей — [math]k[/math] ближайших к нему объектов обучающей выборки [math]x_i[/math] . В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.

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

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

Пусть задана обучающая выборка пар «объект-ответ» [math]X^m = \.[/math]

Пусть на множестве объектов задана функция расстояния [math]\rho(x,x’)[/math] . Эта функция должна быть достаточно адекватной моделью сходства объектов. Чем больше значение этой функции, тем менее схожими являются два объекта [math]x, x'[/math] .

Для произвольного объекта [math]u[/math] расположим объекты обучающей выборки [math]x_i[/math] в порядке возрастания расстояний до [math]u[/math] :

[math]\rho(u,x_) \leq \rho(u,x_) \leq \cdots \leq \rho(u,x_)[/math] , где через [math]x_[/math] обозначается тот объект обучающей выборки, который является [math]i[/math] -м соседом объекта [math]u[/math] . Аналогичное обозначение введём и для ответа на [math]i[/math] -м соседе: [math]y_[/math] . Таким образом, произвольный объект [math]u[/math] порождает свою перенумерацию выборки. В наиболее общем виде алгоритм ближайших соседей есть: [math]a(u) = \mathrm\max_ \sum_^m \bigl[ y_=y \bigr] w(i,u)[/math] ,

где [math]w(i,u)[/math] — заданная весовая функция, которая оценивает степень важности [math]i[/math] -го соседа для классификации объекта [math]u[/math] . Естественно полагать, что эта функция не отрицательна и не возрастает по [math]i[/math] (поскольку чем дальше объект, тем меньший вклад он должен вносить в пользу своего класса).

По-разному задавая весовую функцию, можно получать различные варианты метода ближайших соседей.

[math]w(i,u) = [i=1][/math] — простейший метод ближайшего соседа;

[math]w(i,u) = [i\leq k][/math] — метод [math]k[/math] ближайших соседей;

[math]w(i,u) = [i\leq k] q^i[/math] — метод [math]k[/math] экспоненциально взвешенных ближайших соседей, где предполагается константа [math]q \lt 1[/math] ;

Пример классификации, методом 5 ближайших соседей

Использование ядер сглаживания

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

Будем обозначать функцию ядра [math]K(r)[/math] .

Примеры ядер

Метод парзеновского окна

Алгоритм [math]k[/math] ближайших соседей можно обобщить с помощью функции ядра. Рассмотрим два способа, которыми это можно сделать.

[math]w(i,u) = K\biggl(\frac<\rho(u,x_)>\biggr)[/math] — метод парзеновского окна фиксированной ширины [math]h[/math] ;

[math]w(i,u) = K\biggl(\frac<\rho(u,x_)><\rho(u,x_)>\biggr)[/math] — метод парзеновского окна переменной ширины;

Сравним два этих метода. Сперва запишем классификаторы, полученные при использовании этих методов, в явном виде:

Фиксированной ширины: [math]a_h = a(u, X^m, \boldsymbol, K) = \mathrm\max_ \sum_^m \bigl[ y_=y \bigr] K\biggl(\frac<\rho(u,x_)>\biggr)[/math] ,

Переменной ширины: [math]a_k = a(u, X^m, \boldsymbol, K) = \mathrm\max_ \sum_^m \bigl[ y_=y \bigr] K\biggl(\frac<\rho(u,x_)><\rho(u,x_)>\biggr)[/math] .

[math]a_h[/math] не будет учитывать соседей на расстояние больше чем [math]h[/math] , а всех остальных учтет в соответствии с функций ядра [math]K[/math] . [math]a_k[/math] является аналогом метода [math]k[/math] ближайших соседей (т.к. для всех [math]k+i[/math] -ых соседей функция [math]K[/math] вернет 0), но при этом чем ближе [math]k-i[/math] -ый сосед, тем больший вклад в сторону своего класса он даст.

Часто используют окно переменной ширины т.е. классификатор [math]a_k[/math] , по следующим причинам:

1. Удобнее оптимизировать целочисленный параметр [math]k[/math] , чем вещественный параметр [math]h[/math] по некоторой сетке;

1. Существует большое количество задач, где точки разбросаны неравномерно. В них могут существовать области, где достаточно брать небольшую [math]h[/math] и области, где в окно ширины [math]h[/math] попадает только одна точка. Тогда для классификатора [math]a_h[/math] будут существовать области в которых не будет ни одного объекта (кроме того, который нужно классифицировать). Для таких областей не понятно как классифицировать объекты.

Пример классификации, методом с постоянной шириной окна, и неравномерным разбросом точек

Использование различных метрик расстояния

Очень редко известна хорошая функция расстояния [math]\rho(x,x’)[/math] . В качестве нее обычно использую следующие функции:

Примеры метрик

Пусть [math]x[/math] , [math]y[/math] — объекты, а [math](x_1, x_2. x_n)[/math] , [math](y_1, y_2. y_n)[/math] их признаковые описания.

Евклидова метрика: [math]\rho(x,y) = \sqrt ^(x_-y_)^>[/math] ,

Расстояние Чебышёва: [math]\rho(x,y)=\max _|x_-y_|[/math] ,

Манхэттенское Расстояние: [math]\rho(x,y)=\sum _^|x_-y_|[/math] .

При их использовании важно нормировать значения признаков, иначе один признак с максимальным значением может стать преобладающим, а признаки с маленькими значениями не будут учитываться при классификации. Чтобы отсеять лишние признаки (т.е. не влияющие на класс объекта) можно использовать feature selection.

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

Рассмотрим использование алгоритма [math]kNN[/math] на примере реального набора данных. Предположим, что мы загрузили [math]wdbc.data[/math] и сохранили как [math]tr.csv[/math] с заголовком — описанием признаков.

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

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

Теперь [math]X[/math] , [math]y[/math] — нормированные значения признаков и соответствующие им классы.

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

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: 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

libraryDependencies += "com.github.haifengl" %% "smile-scala" % "1.5.2"

Пример классификации датасета и вычисления F1 меры [1] используя smile.classification.knn [2] :

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)

Пример на языке Java

Пример классификации датасета с применением weka.classifiers.lazy.IBk [3]

 nz.ac.waikato.cms.weka weka-stable 3.8.0  

import weka.classifiers.Evaluation; import weka.classifiers.lazy.IBk; import weka.core.converters.ConverterUtils;

// read dataset and build knn-classifier var source = new ConverterUtils.DataSource("iris.csv"); var dataset = source.getDataSet(); var ibk = new IBk(); ibk.buildClassifier(dataset); // test the model var eTest = new Evaluation(dataset); eTest.evaluateModel(ibk, dataset); // print results summary var strSummary = eTest.toSummaryString(); System.out.println(strSummary);

См. также

• Обзор библиотек для машинного обучения на Python
• Общие понятия
• Уменьшение размерности

Примечания

Источники информации

• machinelearning.ru — Метрический классификатор
• machinelearning.ru — Метод ближайших соседей (kNN)
• Лекция «Метрические методы классификации» К.В. Воронцов, курс «Машинное обучение» 2014
• Wikipedia — Kernel (statistics)
• Документация по scikit-learn
• Пример по работе с датасетом с kaggle

Глава 3. Метрические методы классификации

Во многих прикладных задачах измерять степень сходства объектов существенно проще, чем формировать признаковые описания. Например, такие сложные объекты, как фотографии лиц, подписи, временные ряды или первичные структуры белков естественнее сравнивать непосредственно друг с другом путём некоторого «наложения с выравниванием», чем изобретать какие-то признаки и сравнивать признаковые описания. Если мера сходства объектов введена достаточно удачно, то, как правило, оказывается, что схожим объектам очень часто соответствуют схожие ответы. В задачах классификации это означает, что классы образуют компактно локализованные подмножества. Это предположение принято называть гипотезой компактности . Для формализации понятия «сходства» вводится функция расстояния в пространстве объектов Х. Методы обучения, основанные на анализе сходства объектов, будем называть метрическими, даже если функция расстояния не удовлетворяет всем аксиомам метрики (в частности, аксиоме треугольника). В англоязычной литера- туре употребляются термины similarity based learning или distance-based learning.

3.1. Метод ближайшего соседа и его обобщения

Пусть на множестве объектов X задана функция расстояния

p : X × X → [0, ∞ ).			Существует целевая зависимость			y * : X → Y , значения кото-
рой	известны		только	на	объектах	обучающей	выборки
X t	= ( x , y ) l	, y	= y * ( x ). Множество классов Y конечно. Требуется построить
i i i = 1	i	i

алгоритм классификации a : X → Y , аппроксимирующий целевую зависимость y * ( x ) на всём множестве X .

3.1.1. Обобщённый метрический классификатор

Для произвольного объекта u X расположим элементы обучающей выборки x 1 . x l в порядке возрастания расстояний до и:

p ( u , x (1) ) ≤ p ( u , x (2) ) ≤ . ≤ p ( u , x ( l ) ),
u	u	u
где через x (i) обозначается i-й сосед объекта u. Соответственно ответ на					i-м
u	x (i) = y * ( x (i) )
соседе объекта u есть			. Таким образом, любой объект u X		по-
u	u
рождает свою перенумерацию выборки.
Определение. 3.1.	Метрический		алгоритм	классификации с обучающей

выборкой X l относит объект u к тому классу y X , для которого суммарный вес ближайших обучающих объектов Γ y ( u , X l ) максимален: 54

l	l	( i )	(3.1)
Г y ( u , X	) = ∑	y		u	= y ω ( i , u ),
i =1

где весовая функция ω ( i , u ) оценивает степень важности i -го соседа для кла с- сификации объекта u . Функция Γ y ( u , X l ) называется оценкой близости объек- та u к классу y . Метрический классификатор определён с точностью до весовой функции ω ( i , u ) . Обычно она выбирается неотрицательной, не возрастающей по i. Это соответствует гипотезе компактности, согласно которой чем ближе объекты u и x u (i) , тем выше шансы, что они принадлежат одному классу. Обучающая выборка X играет роль параметра алгоритма a . Настройка сводится к запоминанию выборки, и, возможно, оптимизации каких-то параметров весовой функции, однако сами объекты не подвергаются обработке и сохраняются «как есть». Алгоритм a ( u , X l ) строит локальную аппроксимацию выборки X , причём вычисления откладываются до момента, пока не станет известен объект u. По этой причине метрические алгоритмы относятся к методам ленивого обучения (lazylearning), в отличие от усердного обучения (eagerlearning), когда на этапе обучения строится функция, аппроксимирующая выборку. Метрические алгоритмы классификации относятся также к методам рас- суждения по прецедентам (case-basedreasoning, CBR). Здесь действительно можно говорить о «рассуждении», так как на вопрос «почему объект u был отнесён к классу у?» алгоритм может дать понятное экспертам объяснение: «потому, что имеются схожие с ним прецеденты класса y», и предъявить список этих прецедентов. Выбирая весовую функцию W ( i , u ) , можно получать различ- ные метрические классификаторы, которые подробно рассматриваются ниже.

3.1.2. Метод ближайших соседей

Алгоритм ближайшего соседа (nearestneighbor, NN) относит классифицируе- мый объект u X к тому классу, которому принадлежит ближайший обучающий объект:

ω ( i , u ) =	[	i = 1 ;	a ( u ; X l ) = y (1) .
]		u

Этот алгоритм является, по всей видимости, самым простым классифика- тором. Обучение NN сводится к запоминанию выборки X . Единственное достоинство этого алгоритма — простота реализации. Недостатков гораздо больше: • Неустойчивость к погрешностям. Если среди обучающих объектов есть выброс — объект, находящийся в окружении объектов чужого класса, то не только он сам будет классифицирован неверно, но и те окружающие его объекты, для которых он окажется ближайшим. 55
• Отсутствие параметров, которые можно было бы настраивать по выборке. Алгоритм полностью зависит от того, насколько удачно выбрана метрика ρ. • В результате — низкое качество классификации. Алгоритм k ближайших соседей (k nearest neighbors, kNN). Чтобы сгладить

влияние выбросов, будем относить объект u к тому классу, элементов которого
окажется больше среди k ближайших соседей x ( i ) , i = 1. k :
u
ω ( u , i ) = [ i ≤ k ] ; a ( u ; X	l	k	( i )	= y
	, k ) = argmax ∑	y u	.
y Y i = 1

При k = 1 этот алгоритм совпадает с предыдущим, следовательно, неустойчив к шуму. При k = , наоборот, он чрезмерно устойчив и вырождается в константу.Таким образом, крайние значения k нежелательны. На практике оптимальное значение параметра k определяют по критерию скользящего контроля с исключением объектов по одному(leave-one-out, LOO). Для каждого объекта x i X l проверяется, правильно ли он классифицируется по своим k ближайшим соседям

LOO( k , X ) =	l	a ( x ; X l \ < x , >, k ) ≠ y				→ min .
∑	i	i	i
=	k
i 1
Заметим, что если классифицируемый объект x i					не исключать из обучаю-
щей выборки, то ближайшим соседом x i				всегда будет сам x i , и минимальное

(нулевое) значение функционала LOO ( k ) будет достигаться при k = 1 . Существует и альтернативный вариант метода k NN: в каждом классе выбирается k ближайших к u объектов, и объект u относится к тому классу, для которого среднее расстояние до k ближайших соседей минимально. Алгоритм k взвешенных ближайших соседей. Недостаток k NN в том, что максимум может достигаться сразу на нескольких классах. В задачах с двумя классами этого можно избежать, если взять нечётное k. Более общая тактика, которая годится и для случая многих классов — ввести строго убывающую последовательность вещественных весов ω i , задающих вклад i-го соседа в клас- сификацию:

ω ( u , i ) = [ i ≤ k ] ω i ; a ( u ; X	l	k	( i )	= y
	, k ) = argmax ∑	y u	ω i .
y Y i = 1

Выбор последовательности ω i является эвристикой. Если взять линейно убывающие веса ω i = k + 1 − i , то неоднозначности также могут возникать, хотя k 56

и реже (пример: классов два; первый и четвёртый сосед голосуют за класс 1, второй и третий — за класс 2; суммы голосов совпадают). Неоднозначность устраняется окончательно, если взять нелинейно убывающую последователь- ность, скажем, геометрическую прогрессию: ω i = q i , где знаменатель прогрессии q (0,1) является параметром алгоритма. Его можно подбирать по критерию LOO, аналогично числу соседей k. Недостатки простейших метрических алгоритмов типа kNN: • Приходится хранить обучающую выборку целиком. Это приводит к неэффективному расходу памяти и чрезмерному усложнению решающего правила. При наличии погрешностей (как в исходных данных, так и в модели сходства p) это может приводить к понижению точности классификации вблизи границы классов. Имеет смысл отбирать минимальное подмножество эталонных объектов, действительно необходимых для классификации. • Поиск ближайшего соседа предполагает сравнение классифицируемого объекта со всеми объектами выборки за O ( l ) операций. Для задач с боль- шими выборками или высокой частотой запросов это может оказаться накладно. Проблема решается с помощью эффективных алгоритмов поиска ближайших соседей, требующих в среднем O (ln l ) операций. • В простейших случаях метрические алгоритмы имеют крайне бедный набор параметров, что исключает возможность настройки алгоритма по данным.

3.1.3. Метод парзеновского окна

Ещё один способ задать веса соседям — определить ω i как функцию от расстояния p ( u , x u ( i ) ), а не от ранга соседа i . Введём функцию ядра K(z), невоз-

растающую на [0,			∞ ). Положив ω (i,u) = K (					1 p ( u , x ( i ) ))			в общей формуле (3.1),
h	u
	получим алгоритм
k				p ( u , x u ( i ) )
	l	( i )
a ( u ; X	, h ) = arg max ∑		y u	= y	K (	h	).	(3.2)
y Y i = 1

Параметр h называется шириной окна и играет примерно ту же роль, что и число соседей k . «Окно» — это сферическая окрестность объекта u радиуса h , при попадании в которую обучающий объект x i «голосует» за отнесение объек- та uк классу y i . Мы пришли к этому алгоритму чисто эвристическим путём, однако он имеет более строгое обоснование в байесовской теории классификации, и, фактически, совпадает с методом парзеновского окна. Параметр h мож- 57