Алгоритм k взвешенных ближайших соседей

Недостаток kNN в том, что максимум может достигаться сразу на нескольких классах. В задачах с двумя классами этого можно избежать, если взять нечётное k. Более общая тактика, которая годится и для случая многих классов — ввести строго убывающую последовательность вещественных весов wi, задающих вклад i-го соседа в классификацию:

Выбор последовательности wi является эвристикой. Если взять линейно убывающие веса , то неоднозначности также могут возникать, хотя и реже (пример: классов два; первый и четвёртый сосед голосуют за класс 1, второй и третий — за класс 2; суммы голосов совпадают). Неоднозначность устраняется окончательно, если взять нелинейно убывающую последовательность, скажем, геометрическую прогрессию: wi = qⁱ, где знаменатель прогрессии q ∈ (0,1) является параметром алгоритма. Его можно подбирать по критерию LOO, аналогично числу соседей k.

Недостатки простейших метрических алгоритмов типа kNN.

• Приходится хранить обучающую выборку целиком. Это приводит к неэффективному расходу памяти и чрезмерному усложнению решающего правила. При наличии погрешностей (как в исходных данных, так и в модели сходства ρ) это может приводить к понижению точности классификации вблизи границы классов. Имеет смысл отбирать минимальное подмножество эталонных объектов, действительно необходимых для классификации.

• Поиск ближайшего соседа предполагает сравнение классифицируемого объекта со всеми объектами выборки за O(ℓ) операций. Для задач с большими выборками или высокой частотой запросов это может оказаться накладно. Проблема решается с помощью эффективных алгоритмов поиска ближайших соседей, требующих в среднем O(lnℓ) операций.

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

 

Некоторые метрики

Скалярное умножение векторов:

где p - размерность признакового пространства.

Абсолютное значение вектора (норма):

Направляющие косинусы:

Расстояние Танимото:

Содержание отчета

Отчет должен содержать:

1. Постановку задачи.

2. Таблицу 1 с обучающей и контрольной выборкой, графическое отображение выборок и эталонных значений.

3. Таблицу с результатами классификации реализованными алгоритмами (эталона и kNN) с использованием всех метрик обучающей и контрольной выборок и для различных k. Результаты классификации также отобразить графически.

4. Оценки обобщающей и распознающей способностей классификаторов.

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

6. Листинг программы.

 

 

Лабораторная робота №2

Тема: исследование классификатора на основе опорных векторов. Выбор ядра.

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

 

Порядок выполнения работы

1. Скачать библиотеку LIBSVM со страницы http://www.csie.ntu. edu.tw/~cjlin/libsvm.

2. Разработать программу, реализующую SVM-классификацию с возможностью выбора ядра (одного из стандартных, предоставляемых библиотекой LIBSVM). Предусмотреть визуализацию обучающих данных и классификации по двум признакам.

3. Обучите SVM-классификатор, используя различные ядра и отобразите сгруппированные данные.

4. Протестировать и отладить работу программы на различных обучающих данных. Для чего необходимо выполнить следующее:

a. загрузите данные со страницы http://archive.ics.uci.edu/ml/datasets/Iris для классической задачи классификации ирисов Фишера (БД содержит 150 примеров с 5 признаками);

b. создайте двумерный массив, в котором в первом столбце хранятся измерения sepal length, во втором – sepal width для 150 ирисов;

c. Из вектора species, создайте новый вектор-столбец groups, чтобы классифицировать данные в две группы: Setosa и non-Setosa;

d. Наугад выберите обучающее и тестовое множества.

5. Оформить отчет по лабораторной работе.