Методичка. Распознование образов

5. Метод k-ближайших соседей

Теоретические основы

При использовании статистических алгоритмов распознавания предполагается, что объекты обучающей выборки и распознаваемые объекты принадлежат к одной и той же генеральной совокупности [1]. Считается, что объективно существует совместное вероятностное распределение элементов данной генеральной совокупности по классам и в признаковом пространстве. В случаях, когда такое распределение известно, существует простое оптимальное решение задачи распознавания принадлежности объектов классам K1,...,Kl . Предположим, что нам необходимо

классифицировать объект S , признаковое описание которого представлено вектором x(S) . Для каждого из классов

K1,...,Kl вычисляется условная вероятность принадлежно-

сти P(Ki |x). Объект S относится к тому классу, для ко-

торого условная вероятность принадлежности максимальна. Данное решающее правило минимизирует вероятность ошибочной классификации. В литературе его принято называть байесовским решающим правилом или оптимальным байесовским классификатором (см. раздел 2.). На практике бывает, что байесовское решающее правило не может быть реализовано из-за того, что вероятностное распределение неизвестно.

Простым, но достаточно эффективным подходом здесь является метод k -ближайших соседей [1]. Оценка условных вероятностей P(Ki |x) в методе k -ближайших сосе-

дей ведется по ближайшей окрестности Vk точки x(S) в

32

признаковом пространстве, содержащей по крайней мере k признаковых описаний объектов обучающей выборки.

В качестве оценки P(Ki |x) выступает отношение		ki	, где
		k
ki - число объектов из класса	Ki в окрестности Vk . Есте-
ственно, что поиск ближайшей	окрестности должен осно-

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

Однако мы можем попытаться оценить условные вероятности принадлежности P(Ki |x), используя информа-

цию, содержащуюся в обучающей выборке.

Пример решения задачи атрибуции

В рассматриваемом методе расстояния между классами определяются наименьшим расстоянием между любыми двумя объектами в различных классах (т.е. "наиболее ближними соседями").

Представив документы векторами, рассчитывается расстояние от проверяемого текста контрольной выборки

33

до каждого документа текущего класса. Выбирая манхэттенское расстояние, используем формулу:

n

R(x, y) | xi yi |

i 1

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

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

В учебном пособии [2] можно найти листинг программы для среды MatLab, реализующий данный метод.

Задания для индивидуальной работы

Реализовать задания 3 – 7 параграфа 1 при помощи метода k-ближайших соседей и метода взвешенных ближайших соседей, сравнить полученные результаты между собой, а также с результатами, полученными при помощи других методов.

Литература
1. Журавлев Ю. И.,	Рязанов В. В., Сенько	О.
В. «Распознавание».	Математические методы.	Про-

34

граммная система. Практические применения. — М.:

Фазис, 2006.

2.Дьяконов, A. Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab (практикум на ЭВМ кафедры математических методов прогнозирования). — МАКСПресс, 2010.

— 278 с.

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

ных: http://www.machinelearning.ru.

4.Р.Дуда, П.Харт. Распознавание образов и анализ сцен. -

М.: Мир, 1976. – 511 с.

5.Лепский А.Е., Броневич А.Г. Математические методы распознавания образов: Курс лекций. – Таганрог: Изд-

во ТТИ ЮФУ, 2009. – 155 с.

35

6. Метод Парзеновского окна

Теоретические основы

Метод Парзеновского окна принадлежит к непараметрическим методам классификации, которые основаны на локальном оценивании плотностей распределения классов в окрестности классифицируемого объекта [1, 2, 3, 4]. В основе метода лежит идея о том, что плотность выше в тех точках, рядом с которыми находится большое количество объектов выборки.

Изложим данный метод согласно источнику [3], там же можно найти листинги программ, реализующих данный метод. В этом методе вводится понятие “Окно” – это сферическая окрестность объекта u радиуса h, при по-

падании в которую обучающего объекта xi объект u

“притягивается” к классу yi .

Пусть на X задана функция расстояния (x,xi ), во-

обще говоря, не обязательно метрика. Парзеновская оценка плотности для каждого класса y Y имеет вид:

		1	l		(x,x )
pˆy,h	(x)		yi	y K	i
					h
		ly V(h) i 1

где h – ширина окна;

К(r) – ядерная функция, невозрастающая на интер-

вале [0; ];

V(h) – некоторая функция от ширины окна - нормирующий множитель;

36

l – количество элементов во всей выборке; ly – количество элементов в классе y.

Ядерную функцию K(r) можно выбрать из следующих достаточно распространенных функций:

Классифицирующее правило имеет вид:

.

Если метрика ρ фиксирована, то обучение Парзеновского классификатора сводится к подбору ширины окна h и вида ядра K.

Ширина окна существенно влияет на качество восстановления плотности и, как следствие, классификации. При слишком малом окне мы получаем тот же эффект, что и при использовании гистограммы значений: плотность концентрируется вблизи обучающих объектов, и функция pˆh (x) претерпевает резкие скачки. При слишком большом

окне плотность вырождается в константу.

Варианты нахождения оптимальной ширины окна и способы решения проблемы локальных сгущений, в ситуации, если распределение объектов в пространстве X сильно неравномерно, можно найти в [3].

37

Задания для индивидуальной работы

Реализовать задания 3 – 7 параграфа 1 при помощи метода Парзеновского окна с разными ядерными функциями, сравнить полученные результаты между собой, а также с результатами, полученными при помощи других методов.

Литература

1.Лепский А.Е., Броневич А.Г. Математические методы распознавания образов: Курс лекций. – Таганрог: Изд-

во ТТИ ЮФУ, 2009. – 155 с.

2.Р.Дуда, П.Харт. Распознавание образов и анализ сцен. -

М.: Мир, 1976. – 511 с.

3.Воронцов К.В. Курс лекций «Математические методы обучения по прецедентам» // http://www.machinelearning.ru/wiki/images/6/6d/Voron- ML-1.pdf

4.Лекции Д.П. Ветрова и Д.А. Кропотова «Байесовские методы машинного обучения» // http://www.machinelearning.ru/wiki/images/e/e1/BayesM L-2007-textbook-1.pdf

38

7. Метод опорных векторов

Описание метода

Метод опорных векторов (Support vector machines - SVM) был описан в работе В. Н. Вапника [2]. SVM – это математический метод получения функции, решающей задачу классификации. При помощи данного метода изначально решались задачи бинарной классификации, т.е. этот алгоритм мог отличать только объекты двух классов. В 90-х гг. прошлого века метод SVM был усовершенствован: разработаны эффективные алгоритмы поиска оптимальной плоскости, найдены способы обобщения на нелинейные случаи и ситуации с числом классов, большим двух [1].

В основе метода лежит понятие плоскостей решений. Плоскость (plane) решения разделяет объекты с разной классовой принадлежностью [12].

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

Изначально идея метода возникла из геометрической интерпретации задачи классификации. Ниже, опираясь на работу [10], изложим эту самую идею, лежащую в основе метода опорных векторов. Допустим, есть множество точек на плоскости, и каждая из точек принадлежит только одному из двух классов. Необходимо найти прямую, которая однозначно разделит эти точки на два класса. Если удастся найти такую прямую, то классифицировать каждую новую точку можно будет следующим образом: если точка лежит выше прямой, то она относится к классу А, если ниже – к классу В (см. рис.1).

39

А

В

b

Рисунок 1. Разделяющая прямая

Формально это можно сформулировать следующим образом: необходимо найти вектор w такой, что для некоторого граничного значения b и новой точки xi выполня-

ется:

w xi b yi 1 w xi b yi 1.

Уравнение w xi b описывает прямую, разделяю-

щую классы на плоскости. Назовем прямую b разделяю-

щей прямой.

Это означает, что если скалярное произведение вектора w на xi больше допускающего значения b, то новая

точка принадлежит одному классу – А, если меньше, то другому классу - В.

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

40

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

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

Пример разделяющей полосы, заданной условием1 w xi b 1, приведен на рисунке 2:

41