Главная База знаний "Allbest" Экономико-математическое моделирование Выбор метрики расстояния для k-NN классификатора

Выбор метрики расстояния для k-NN классификатора

Характеристика различных видов метрик. Метод ближайших соседей и его обобщения. Алгоритм ближайшего соседа. Метод парзеновского окна. Обобщенный метрический классификатор. Проблема выбора метрики. Манхэттенское и эвклидово расстояние. Косинусная мера.

Рубрика	Экономико-математическое моделирование
Вид	курсовая работа
Язык	русский
Дата добавления	08.03.2015
Размер файла	319,2 K

посмотреть текст работы

скачать работу можно здесь

полная информация о работе

весь список подобных работ

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

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

Для формализации понятия «сходства» вводится функция расстояния или метрика с(x, x?) в пространстве объектов X. Алгоритмы, основанные на анализе сходства объектов, часто называют метрическими, даже в тех случаях, когда функция с не удовлетворяет всем аксиомам метрики (например, аксиоме треугольника).

Различные метрические алгоритмы классификации рассматриваются в.

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

1. ЦЕЛЬ РАБОТЫ

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

Так же продемонстрировать на примерах использование различных метрик.

2. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

Напомним основные обозначения и постановку задачи классификации.

Имеется пространство объектов X и конечное множество имён классов Y. На множестве X задана функция расстояния с: X ЧX > [0,?). Существует целевая зависимость y?: X > Y, значения которой известны только на объектах обучающей выборки X^? = (x_i, y_i)^?_i=1, y_i = y?(x_i). Требуется построить алгоритм классификации a: X > Y, аппроксимирующий целевую зависимость y?(x) на всём множестве X.

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

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

с(u, x₁,_u) ? с(u, x₂,_u) ? · · · ? с(u, x_?,_u)(2.1)

где через x_i,u обозначается i-й сосед объекта u. Аналогичное обозначение введём и для ответа на i-м соседе: y_i,u = y?(x_i,u). Каждый объект u ? X порождает свою перенумерацию выборки x_1,u,..., x_?,u.

2.2 Алгоритм ближайшего соседа

Nearest neighbor, NN является самым простым алгоритмом классификации. Он относит классифицируемый объект u ? X^? к тому классу, которому принадлежит ближайший обучающий объект:

a(u; X^?) = y_1,u(2.2)

Обучение NN сводится к элементарному запоминанию выборки X^?. Единственное достоинство этого алгоритма -- простота реализации. Недостатков гораздо больше:

a) неустойчивость к погрешностям. Если среди обучающих объектов есть выброс -- объект, находящийся в окружении объектов чужого класса, то не только он сам будет классифицирован неверно, но и окружающие его объекты, для которых он окажется ближайшим, также будут классифицированы неверно;

b) отсутствие параметров, которые можно было бы настраивать по выборке. Алгоритм полностью зависит от того, насколько удачно выбрана метрика с;

c) в результате -- низкое качество классификации.

2.3 Алгоритм k ближайших соседей

K nearest neighbors, kNN. Чтобы сгладить шумовое влияние выбросов, будем классифицировать объекты путём голосования по k ближайшим соседям. Каждый из соседей x_i,u, i = 1,..., k голосует за отнесение объекта u к своему классу y_i,u. Алгоритм относит объект u к тому классу, которыйнаберёт большее число голосов:

a(u; X^?, k) = arg (2.3)

При k = 1 этот алгоритм совпадает с предыдущим, следовательно, неустойчив к шуму. При k = ?, наоборот, он чрезмерно устойчив и вырождается в константу.

Таким образом, крайние значения k нежелательны. На практике оптимальное значение параметра k определяют по критерию скользящего контроля с исключением объектов по одному (leave-one-out, LOO). Для каждого объекта x_i? X_? проверяется, правильно ли он классифицируется по своим k ближайшим соседям.

LOO(k, X^?) =(2.4)

Если классифицируемый объект x_i не исключать из обучающей выборки, то ближайшим соседом xi всегда будет сам x_i, и минимальное (нулевое) значение функционала LOO(k) будет достигаться при k = 1. Как правило, функционал LOO(k) имеет чётко выраженный минимум.

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

a(u; X^?, k) = arg w_i(2.5)

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

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

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

a(u; X^?, h, K) = arg K() (2.6)

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

Параметр h можно задавать априори или определять по скользящему контролю. Зависимость LOO(h), как правило, имеет характерный минимум, поскольку слишком узкие окна приводят к неустойчивой классификации; а слишком широкие -- к вырождению алгоритма в константу.

Фиксация ширины окна h не подходит для тех задач, в которых обучающие объекты существенно неравномерно распределены по пространству X. В окрестности одних объектов может оказываться очень много соседей, а в окрестности других -- ни одного. В этих случаях применяется окно переменной ширины. Возьмём финитное ядро -- невозрастающую функцию K(z), положительную на отрезке [0, 1], и равную нулю вне его. Определим h как наибольшее число, при котором ровно k ближайших соседей объекта u получают ненулевые веса: h(u) = с(u, x_k+1,u). Тогда алгоритм принимает вид

a(u; X^?, h, K) = arg K()(2.7)

Выбор ядра K слабо влияет на качество классификации.

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

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

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

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

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

(3.1)

Алгоритм 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ⁱ -- 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», и предъявить список этих прецедентов.

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

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

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

a(u) = arg (3.2)

называется величина

M(x_i) = (x_i) - (x_i).(3.3)

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

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

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

3.2 Отбор эталонных объектов

Обычно объекты обучения не являются равноценными. Среди них могут находиться типичные представители классов -- эталоны. Если классифицируемый объект близок к эталону, то, скорее всего, он принадлежит тому же классу. Ещё одна категория объектов -- неинформативные или периферийные. Они плотно окружены другими объектами того же класса. Если их удалить из выборки, это практически не отразится на качестве классификации. Наконец, в выборку может попасть некоторое количество шумовых выбросов -- объектов, находящихся «в гуще» чужого класса.

Как правило, их удаление только улучшает качество классификации.

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

Идея отбора эталонов реализована в алгоритме STOLP [3]. Мы рассмотрим его обобщённый вариант с произвольной весовой функцией w(i, u). Будем строить метрический алгоритм a(u; ?) вида (1.3), где ? ? X? -- множество эталонов.

Обозначим через M(x_i, ?) отступ объекта x_i относительно алгоритма a(x_i;?). Большой отрицательный отступ свидетельствует о том, что объект x_i окружён объектами чужих классов, следовательно, является выбросом. Большой положительный отступ означает, что объект окружён объектами своего класса, то есть является либо эталонным, либо периферийным.

Вход:

X^? -- обучающая выборка;

д -- порог фильтрации выбросов;

?₀ -- допустимая доля ошибок;

Выход:

Множество опорных объектов ? ? X^?;

1: для всех x_i ? X^? проверить, является ли x_i выбросом:

2: если M(x_i, X^?) < д то

3: X^??1:= X^? \ {x_i}; ? := ? ? 1;

4: Инициализация: взять по одному эталону от каждого класса:

5: пока ? ?X^?;

6: Выделить множество объектов, на которых алгоритм a(u; ?) ошибается:

E := {x_i ? X^? \ ? : M(x_i, ?) < 0};

7: если |E| < ?₀ то

8: выход;

9: Присоединить к ? объект с наименьшим отступом:

Алгоритм начинает с отсева выбросов (шаги 1-3). Из выборки X^? исключаются все объекты x_i с отступом M(x_i, X^?), меньшим заданного порога д, например, можно положить д = 0. Как вариант, можно исключать заданную долю объектов с наименьшими значениями отступа.

Затем формируется начальное приближение -- в ? заносится по одному наиболее типичному представителю от каждого класса (шаг 4).

После этого начинается процесс последовательного «жадного» наращивания множества ?. На каждом шаге к ? присоединяется объект x_i, имеющий минимальное отрицательное значение отступа. Так продолжается до тех пор, пока число ошибок не окажется пренебрежимо малым. Если положить ?₀ = 0, то будет построен алгоритм a(u; ?), не допускающий ошибок на обучающих объектах, за исключением, разве что, объектов выбросов.

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

В описанном варианте алгоритм STOLP имеет относительно низкую эффективность. Для присоединения очередного эталона необходимо перебрать множество объектов X^? \ ?, и для каждого вычислить отступ относительно множества эталонов ?. Общее число операций составляет O(|?|²?). Для ускорения алгоритма можно добавлять сразу по несколько эталонов, не пересчитывая отступов. Если при этом выбирать добавляемые эталоны достаточно далеко друг от друга, то добавление одного из них практически не будет влиять на отступы остальных. Аналогично, на этапе отсева выбросов можно вычислить отступы только один раз, и потом отбросить все объекты с отступами ниже д. При программной реализации имеет смысл определить отдельную процедуру для обновления значений всех отступов M_i = M(x_i, ?) при текущем наборе эталонов ?. Тогда в самом алгоритме можно будет гибко принимать решение о том, в какие моменты вызывать эту процедуру. Реализация этих идей не показана в Алгоритме, чтобы не загромождать его техническими подробностями.

Результатом работы алгоритма STOLP является разбиение обучающих объектов на три категории: шумовые, эталонные и неинформативные. Если гипотеза компактности верна и выборка достаточно велика, то основная масса обучающих объектов окажется неинформативной и будет отброшена. Фактически, этот алгоритм выполняет сжатие исходных данных.

4. ПРОБЛЕМА ВЫБОРА МЕТРИКИ

Выбор метрики с(x, x?) в пространстве объектов X является серьёзной проблемой в задачах классификации, кластеризации и непараметрической регрессии. Метрика -- это математическая модель сходства объектов, и её выбор во многих случаях не однозначен. В то же время, в большинстве метрических алгоритмов предполагается, что метрика фиксирована. В последнее время всё чаще применяются методы, в которых метрика настраивается по обучающей выборке.

Если объекты описываются набором признаков f₁(x),..., f_n(x), первое, что приходит в голову -- применить евклидову метрику (именно её все проходили в школе):

(4.1)

Её обобщением является взвешенная метрика Минковского:

(4.2)

где c_j -- веса признаков, показатель степени p может принимать значения от 1 до ? включительно. При p = ? имеем взвешенную равномерную метрику:

(4.3)

Веса признаков часто задают из соображений нормировки: M_j = max _i=1,...?|fj(xi)|,c_j = M^?^p_j, однако такой способ не позволяет учитывать относительную важность (ценность, информативность) признаков, а в многомерных пространствах приводит к проблеме «проклятия размерности» (curse of dimensionality) -- чем выше размерность пространства n, тем более устойчивой становится сумма разностей . Этот факт аналогичен закону больших чисел в теории вероятностей. Увеличение размерности в пределе n > ? приводит к тому, что все точки выборки становятся почти одинаково далеки друг от друга. Становится невозможно выделить локальную окрестность объекта, теряется информация о структуре метрического пространства. Это существенно затрудняет решение задач классификации, кластеризации и непараметрической регрессии.

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

5. МАНХЭТТЕНСКОЕ РАССТОЯНИЕ

Расстояние городских кварталов -- метрика, введённая Германом Минковским. Согласно этой метрике, расстояние между двумя точками равно сумме модулей разностей их координат.

У этой метрики много имён. Расстояние городских кварталов также известно как манхэттенское расстояние, метрика прямоугольного города, метрика L1 или норма ?₁, метрика городского квартала, метрика такси, метрика Манхэттена, прямоугольная метрика, метрика прямого угла; на Z² её называют метрикой гриды и 4-метрикой[1][2][3].

Название «манхэттенское расстояние» связано с уличной планировкой Манхэттена[4].

Расстояние городских кварталов между двумя векторами в n-мерном вещественном векторном пространстве с заданной системой координат -- сумма длин проекций отрезка между точками на оси координат. Более формально,

(5.1)

и (5.2)

-- векторы.

Например, на плоскости расстояние городских кварталов между и равно

(5.3)

Рис. 5.1 Окружности в дискретной и непрерывной геометрии городских кварталов

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

6. КОСИНУСНАЯ МЕРА

Мера Охаи -- бинарная мера сходства, предложенная Акирой Охаи в 1957 году[1]. В дальнейшем была развита Дж. Баркманом[2]. Фамилия автора коэффициента в литературе переводилась как Очиаи, Отиаи и т. п.

Сам автор (Охаи) утверждает, что коэффициент был ранее предложен Отсукой (Otsuka) как отношение общего числа признаков двух объектов к среднему геометрическому двух объектов и поэтому правильным будет называть -- коэффициент Отсуки-Охаи[3].

Охаи ничего нового в этот коэффициент не внёс и, по сути, является его популяризатором, но в своей статье он не дал ссылку на статью первоначального автора.

Эта мера сходства встречается также под названием косинусный коэффициент (cosine similarity coefficient, geometric coefficient, en:Fowlkes-Mallows Index):

(6.1)

Для сравнивания объектов по встречаемости видов (вероятностная интерпретация), то есть учитываются вероятности встреч, то аналогом меры Охаи будет коэффициент совместимости событий:

(6.2)

7. ЭВКЛИДОВО РАССТОЯНИЕ

метрика манхэттенский эвклидовый расстояние

В математике Евклидова дистанция или Евклидова метрика -- геометрическое расстояние между двумя точками в многомерном пространстве, вычисляемое по теореме Пифагора.

(7.1)

где a и b - точки в n-мерном пространстве, i - порядковый номер признака, и - координаты точек a и b по признаку i.

Рассмотрим расчет евклидова расстояния между двумя точками в пространстве трех измерений Рис 4.1.

(7.2)

Рис 7.1 Эвклидово расстояние в трехмерном пространстве

7.1 Взвешенное эвклидово расстояние. Определение веса

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

Определим весовую функцию w(i, u) так, чтобы каждый объект x_i учитывался со своим весом г(x_i):

w(i, u) = г(x_i,u) w (i, u)(7.3)

где функция w(i, u) неотрицательна и не возрастает по i. В частности, можно положить w(i, u) = 1. Тогда вес w(i, u) будет зависеть только от самого соседа x_i,u, но ни от его ранга i, ни от расстояния с(u, x_i,u). Чтобы настроить значения параметров г(x_i) по обучающей выборке, выпишем условие корректности алгоритма на объектах обучения:

a(x_i) = y_i, i = 1,..., ?(7.4)

Исходя из общего представления метрического алгоритма, легко сделать вывод, что эта система из ? равенств равносильна системе из ?(|Y| - 1) линейных неравенств относительно весов г(x_i):

(7.5)

где суммирование начинается с 2, чтобы сам объект x_i не попадал в число своих ближайших соседей; множество T определяется как множество всех пар «номер объекта -- номер класса, которому он не принадлежит»:

T = {(i, y) | i = 1,..., ?; y ? Y \{y_i}}.

Очевидно,

|T| = ?(|Y| - 1)(7.6)

Запишем систему неравенств в матричном виде. Введём вектор-столбец весов г = (г(x₁),…, г(x_?))^T. Определим матрицу B = (b_(i,y)j) с |T| строками и j столбцами. Строки будем нумеровать парами (i, y) из T. Заполним матрицу B следующим образом. Для каждой тройки индексов (i, y, s), в которой (i, y) ? T, s = 2,..., ?, найдём объект x_j = x_s,xi, который является s-м соседом объекта x_i. Предположим

b_(i,y)j = (7.7)

Тогда в матричном представлении система неравенств относительно неизвестного неотрицательного вектора г приобретёт совсем простой вид:

Bг > 0; г ? 0(7.8)

В общем случае эта система несовместна. Нарушение неравенства, соответствующего паре индексов (i, y), означает, что алгоритм a(u) допускает ошибку на обучающем объекте x_i, выдавая ответ y вместо y_i. Минимизация числа ошибок на обучающей выборке сводится к задаче поиска максимальной совместной подсистемы в системе неравенств Bг>0 при обязательном выполнении ограничений г ? 0.

Таким образом, задача определения весов объектов в метрическом классификаторе сводится к построению линейного разделяющего правила. Фактически, это новая задача классификации, в которой объектами являются всевозможные пары (i, y) ? T, а признаковые описания задаются векторами

(b₍_i_,_y₎₁,..., b₍_i_,_y_)?)(7.9)

Для решения данной задачи применимы методы построения линейной разделяющей поверхности с неотрицательными коэффициентами, в частности, модификация метода опорных векторов Non-Negative SVM.

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

8. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

В качестве примера были использованы выборки Iris и Wine. Это выборки с числовыми данными. Для исследования был написан программный код на языке C#, функции метрик:

// функция считающая Эвклид расстояние

static double Evklid(double[] masLearn, double[] mas)

{

double rast = 0;

double sum = 0;

for (int i = 0; i < mas.Length; i++)

{

sum += (masLearn[i] - mas[i]) * (masLearn[i] - mas[i]);

}

rast = Math.Sqrt(sum);

return rast;

}

// функция считающая Манхэттенское расстояние

static double Manhattan(double[] masLearn, double[] mas)

{

double rast = 0;

for (int i = 0; i < mas.Length; i++)

{

rast += Math.Abs(masLearn[i] - mas[i]);

}

return rast;

}

// Косинусной меры

static double CosMetric(double[] masLearn, double[] mas)

{

double rast = 0;

double znamenat = 0;

double cheslit = 0;

cheslit = (masLearn[0] - mas[0]) * (masLearn[1] - mas[1]) + (masLearn[2] - mas[2]) * (masLearn[3] - mas[3]);

znamenat = Math.Sqrt((Math.Pow(masLearn[0] - mas[0], 2) * Math.Pow(masLearn[1] - mas[1], 2) + Math.Pow(masLearn[2] - mas[2], 2) * Math.Pow(masLearn[3] - mas[3], 2)));

rast = Math.Abs(cheslit) / znamenat;

return rast;

}

// функция считающая взыешенное Эвклид расстояние

static double VzveshEvklid(double[] masLearn, double[] mas)

{

double rast = 0;

double sum = 0;

sum = 0.1 * (masLearn[0] - mas[0]) * (masLearn[0] - mas[0]) + 0.1 * (masLearn[1] - mas[1]) * (masLearn[1] - mas[1]) + 100 * (masLearn[2] - mas[2]) * (masLearn[2] - mas[2]) + 100 * (masLearn[3] - mas[3]) * (masLearn[3] - mas[3]);

rast = Math.Sqrt(sum);

return rast;

}

Результат работы для выборки Iris при k=11

Рис. 8.1 Скрин программы для Iris

Экспериментным путем я определил, что для k<11 эвклидово, взвешенное эвклидово и манхэттенское расстоянии дают одинаковые результаты равные 97,7777777777778%, у косинусной меры показатели очень малы. Но при k11 результаты первых трех метрик различны, у взвешенного эвклидово и манхэттенского расстояний процент остается таким же высоким.

Результат работы для выборки Wine при k=5

Рис. 8.2 Скрин программы для Wine

У выборки Wine результаты первых трех выборок начали различаться для числа соседей k5. У косинусной меры показатели всё так же очень малы.

Таблица 8.1 результаты для Iris k=11

Название метрики	Точность
евклидово расстояние	95,5555555555556
взвешенное Евклидово расстояние	97,7777777777778
косинусная мера	31,1111111111111
манхэттенское расстояние	97,7777777777778

Таблица 8.2 результаты для Wine k=5

Название метрики	Точность
евклидово расстояние	95,5555555555556
взвешенное Евклидово расстояние	97,7777777777778
косинусная мера	93,3333333333333
манхэттенское расстояние	8,88888888888889

ВЫВОДЫ

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

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

Задача выбора метрики зависит от различных факторов, таких как специфика выборки, вес атрибутов и др.

Для наших выборок оптимальной метриками была евклидово расстояние, а наиболее не подходящей - косинусная мера.

СПИСОК ССЫЛОК

1. Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. -- М.: Наука, 1970. -- P. 320.

2. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О. Б. Лупанов. -- М.: Физматлит, 2004. -- Т. 13. -- С. 5-36.

http:// www.ccas.ru/frc/papers/voron04mpc.pdf.

3. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. -- Новосибирск: ИМ СО РАН, 1999.

4. Mullin M., Sukthankar R. Complete cross-validation for nearest neighbor classi?ers //Proceedings of International Conference on Machine Learning. -- 2000.

5. http:// citeseer.ist.psu.edu/309025.html.

Размещено на Allbest.ru

курсовая работа "Выбор метрики расстояния для k-NN классификатора" скачать

Подобные документы

Математические методы в экономике
Линейное программирование. Геометрическая интерпретация и графический метод решения ЗЛП. Симплексный метод решения ЗЛП. Метод искусственного базиса. Алгоритм метода минимального элемента. Алгоритм метода потенциалов. Метод Гомори. Алгоритм метода Фогеля.

реферат [109,3 K], добавлен 03.02.2009
Обобщенный метод наименьших квадратов
Эффективность линейной несмещенной оценки вектора для обобщенной регрессионной модели, теорема Айткена. Обобщенный метод наименьших квадратов. Преобразования Фурье, их применение; разложение временного ряда. Ряды Фурье, многомерные преобразования.

реферат [345,4 K], добавлен 09.05.2012
Предмет и метод эконометрики
Суть эконометрики как научной дисциплины, ее предмет и метод. Парная и множественная регрессия в экономических исследованиях. Регрессионные модели с переменной структурой. Обобщенный метод наименьших квадратов. Анализ систем экономических уравнений.

реферат [279,2 K], добавлен 11.09.2013
Метод Монте-Карло
Связь стохастических процессов и дифференциальных уравнений. Алгоритм Бюффона для определения числа Пи. Геометрический алгоритм Монте-Карло интегрирования. Применение метода Монте-Карло в логистике. Алгоритм Метрополиса, квантовый метод Монте-Карло.

курсовая работа [258,0 K], добавлен 26.12.2013
Разработка программы построения нечеткого классификатора на основе наблюдаемых данных
Треугольное нечеткое число с центром в точке. Наиболее важные нечеткие импликации. Поиск на множестве векторных оценок отношения эквивалентности, которое однозначно определяет искомое разбиение. Формирование базы правил для нечеткого классификатора.

курсовая работа [1,9 M], добавлен 11.04.2014
Нахождение критического пути табличным методом
Проблема автоматизации расчёта сетевого графика. Вычисление критического пути с помощью ЭВМ. Табличный метод решения проблемы, метод графов. Составление алгоритма, написание программы и решение задачи. графический интерфейс пользователя, ввод данных.

курсовая работа [39,7 K], добавлен 20.11.2008
Методи кластеризації: процедура Мак-Кіна, метод К-методів, сітчасті методи
Мета кластерного аналізу: поняття, алгоритм, завдання. Головні особливості процедури Мак-Кіна. Графік середніх значень за трьома кластерами. Метод К-методів, переваги та недоліки використання. Поняття про сіткові алгоритми кластеризації (grid-based).

реферат [238,3 K], добавлен 27.05.2013
Метод потенциалов для решения транспортной задачи в матричной форме. Задача оптимального распределения ресурсов
Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.

контрольная работа [158,7 K], добавлен 15.10.2010
Эконометрический метод и использование стохастических зависимостей в эконометрике
Анализ и описание различных подходов к определению вероятности. Примеры стохастических зависимостей в экономике, их особенности и теоретико-вероятностные способы их изучения. Классификация и характеристика основных этапов эконометрического исследования.

реферат [25,1 K], добавлен 16.04.2009
Симплексный метод
Очевидное начальное опорное решение. Симплексный метод с естественным базисом. Графический метод решения задач линейного программирования. Двойственная задача, ее оптимальное решение. Матрица коэффициентов затрат. Полная схема межотраслевого баланса.

контрольная работа [89,6 K], добавлен 30.04.2009

Другие документы, подобные "Выбор метрики расстояния для k-NN классификатора"

весь список подобных работ

скачать работу можно здесь

сколько стоит заказать работу?

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.