Автор работы: Пользователь скрыл имя, 19 Декабря 2014 в 21:16, дипломная работа
Цель данной работы: на основе общей математической теории распознавания подробно изучить один из методов этой теории: метод ближайших соседей, и использовать его для задач: первая – классификации видов преступления и вторая – по экономическим данным определения географического региона в зависимости от ряда факторов.
В работе решаются следующие задачи: выявление особенности изучаемого метода в зависимости от выбора признаков обучающей выборки (дискретные и непрерывные); сбор данных для создания информационной базы данных (информация о преступлениях против личности и против порядка управления, данные по трудовой деятельности граждан, осуществляющих деятельность в Центральной и Восточной части России).
Введение.
Глава 1. Общая теория распознавания образов.
Глава 2. Алгоритм ближайшего соседа.
Глава3. Практическая реализация алгоритма ближайшего соседа.
Заключение.
Список литературы.
Приложения.
МЕТОД БЛИЖАЙШИХ СОСЕДЕЙ В ЗАДАЧЕ
КЛАССИФИКАЦИИ
Выпускная квалификационная работа
Оглавление
Человек, сталкиваясь с новой задачей, использует свой жизненный опыт, вспоминает аналогичные ситуации, которые когда-то с ним происходили. О свойствах нового объекта мы судим, полагаясь на похожие знакомые наблюдения.
Распознавание – это отнесение конкретного объекта (реализации), представленного значениями его свойств (признаков), к одному из фиксированного перечня образов (классов) по определённому решающему правилу в соответствии с поставленной целью.
В последние годы распознавание образов находит все большее применение. Распознавание речи, печатного и рукописного текста, различных изображений, отнесения произвольного объекта к конкретному классу, без дополнительных вычислений и наблюдений значительно упрощает взаимодействие человека с компьютером, создает предпосылки для применения различных систем искусственного интеллекта.
Способность восприятия внешнего мира в форме образов позволяет с определенной достоверностью узнавать бесконечное число объектов на основании ознакомления с конечным их числом, а объективный характер основного, уже известного свойства образов позволяет моделировать процесс их распознавания.
Цель данной работы: на основе общей математической теории распознавания подробно изучить один из методов этой теории: метод ближайших соседей, и использовать его для задач: первая – классификации видов преступления и вторая – по экономическим данным определения географического региона в зависимости от ряда факторов.
В работе решаются следующие задачи:
Теория распознавания образов - научное направление, связанное с разработкой принципов и построением систем, предназначенных для определения принадлежности данного объекта к одному из заранее выделенных классов объектов. Под объектами в распознавании образов понимают различные предметы, явления, процессы, ситуации, сигналы. Каждый объект описывается совокупностью основных характеристик (признаков, свойств) где -я координата вектора определяет значения -й характеристики, и дополнительной характеристикой , которая указывает на принадлежность объекта к некоторому классу (образу). Набор заранее расклассифицированных объектов, т. е. таких, у которых известны характеристики и , используется для обнаружения закономерных связей между значениями этих характеристик и поэтому называются обучающей выборкой. Те объекты, у которых характеристика неизвестна, образуют контрольную выборку. Отдельные объекты обучающей и контрольной выборок называются реализациями [1].
Одна из основных задач распознавания образов – выбор правила (решающей функции) , в соответствии с которым по значению контрольной реализации устанавливается её принадлежность к одному из образов, т. е. указываются "наиболее правдоподобные" значения характеристики для данного . Выбор решающей функции требуется произвести так, чтобы стоимость самого распознающего устройства, его эксплуатации и потерь, связанных с ошибками распознавания, была минимальной. Примером задачи распознавания образов этого типа может служить задача различения нефтеносных и водоносных пластов по косвенным геофизическим данным. По этим характеристикам сравнительно легко обнаружить пласты, насыщенные жидкостью. Значительно сложнее определить, наполнены они нефтью или водой. Требуется найти правило использования информации, содержащейся в геофизических характеристиках, для отнесения каждого насыщенного жидкостью пласта к одному из двух классов - водоносному или нефтеносному. При решении этой задачи в обучающую выборку включают геофизические данные вскрытых пластов.
Успех в решении задачи распознавания образов зависит в значительной мере от того, насколько удачно выбраны признаки . Исходный набор характеристик часто бывает очень большим. В то же время приемлемое правило должно быть основано на использовании небольшого числа признаков, наиболее важных для различения одного образа от другого. Так, в задачах медицинской диагностики важно определить, какие симптомы и их сочетания (синдромы) следует использовать при постановке диагноза данного заболевания. Поэтому проблема выбора информативных признаков - важная составная часть проблемы распознавания образов [2].
Проблема распознавания образов тесно связана с задачей предварительной классификации, или таксономией.
В основной задаче распознавания образов о построении решающих функций используются закономерные связи между характеристиками и обнаруживаемые на обучающей выборке, и некоторые дополнительные априорные предположения, например следующие гипотезы: характеристики для реализаций образов представляют собой случайные выборки из генеральных совокупностей с нормальным распределением, реализации одного образа расположены "компактно" (в некотором смысле), признаки в наборе независимы и т.д.
Распознавание образов — это отнесение исходных данных к определенному классу с помощью выделения существенных признаков, характеризующих эти данные, из общей массы несущественных данных.
Классическая постановка задачи распознавания образов:
Дано множество объектов. Относительно них необходимо провести классификацию. Множество представлено подмножествами, которые называются классами. Заданы: информация о классах, описание всего множества и описание информации об объекте, принадлежность которого к определенному классу неизвестна. Требуется установить – к какому классу относится этот объект [1].
Основная типология методов распознавания образов:
Примеры задач распознания образов:
где
Правило Байеса показывает, как наличие измеренной величины х позволяет из априорной вероятности получить апостериорную вероятность Если при наблюдении получено значение , для которого больше, чем , то естественно склониться к решению, что истинное состояние природы есть . Аналогично, если больше, чем , то естественно склониться к выбору . Для того, чтобы обосновать это, вычислим вероятность ошибки при принятии решения, когда наблюдалось определенное значение х:
Средняя вероятность ошибки определяется выражением
и если для каждого х вероятность достигает наименьшего значения, то и интеграл должен быть минимальным. Этим мы обосновали следующее байесовское решающее правило, обеспечивающее наименьшую вероятность ошибки:
Самим видом решающего правила подчеркивается роль апостериорных вероятностей. Используя уравнение (1), можно выразить это правило через условные и априорные вероятности. Заметим, что в уравнении (1) с точки зрения принятия решения роли не играет, являясь всего-навсего масштабным множителем, обеспечивающим равенство . Исключив его, получим следующее решающее правило, полностью эквивалентное прежнему:
Чтобы пояснить существо вопроса, рассмотрим крайние случаи. Пусть для некоторого получено, что , так что конкретное наблюдение не дает информации о состоянии объекта. В этом случае решение, которое мы примем, целиком зависит от априорных вероятностей. С другой стороны, если , то состояния объекта априорно равновозможны, и вопрос о принятии решения опирается исключительно на – правдоподобие при данном . В общем случае при выборе решения важны обе указанные величины, что и учитывается правилом Байеса, обеспечивающим наименьшую вероятность ошибки [3].
Метод k ближайших соседей для решения задач дискриминантного анализа был впервые предложен еще в 1952 году. Он заключается в следующем.
При классификации неизвестного объекта находится заданное число (k) геометрически ближайших к нему в пространстве признаков других объектов (ближайших соседей) с уже известной принадлежностью к распознаваемым классам. Решение об отнесении неизвестного объекта к тому или иному диагностическому классу принимается путем анализа информации об этой известной принадлежности его ближайших соседей, например, с помощью простого подсчета голосов.
Первоначально метод k ближайших соседей рассматривался как непараметрический метод оценивания отношения правдоподобия. Для этого метода получены теоретические оценки его эффективности в сравнении с оптимальным байесовским классификатором.
При использовании метода k ближайших соседей для распознавания образов исследователю приходится решать сложную проблему выбора метрики для определения близости диагностируемых объектов. Эта проблема в условиях высокой размерности пространства признаков чрезвычайно обостряется вследствие достаточной трудоемкости данного метода, которая становится значимой даже для высокопроизводительных компьютеров. Поэтому здесь необходимо решать творческую задачу анализа многомерной структуры экспериментальных данных для минимизации числа объектов, представляющих диагностические классы.
Сходство объектов лежит в основе алгоритма k-ближайших соседей (k-nearest neighbor algorithm, KNN). Алгоритм способен выделить среди всех наблюдений k известных объектов (k-ближайших соседей), похожих на новый неизвестный ранее объект. На основе классов ближайших соседей выносится решение относительно нового объекта. Важной задачей данного алгоритма является подбор коэффициента – количество записей, которые будут считаться похожими [4].
Метод ближайшего соседа является, пожалуй, самым простым алгоритмом классификации. Классифицируемый объект относится к тому классу , которому принадлежит ближайший объект обучающей выборки .
Пусть имеется n наблюдений, каждому из которых соответствует запись в таблице. Все записи принадлежат какому-либо классу. Необходимо определить класс для новой записи.
На первом шаге алгоритма следует задать число – количество ближайших соседей. Если принять , то алгоритм потеряет обобщающую способность (то есть способность выдавать правильный результат для данных, не встречавшихся ранее в алгоритме) так как новой записи будет присвоен класс самой близкой к ней. Если установить слишком большое значение, то многие локальные особенности не будут выявлены.
На втором шаге находятся записей с минимальным расстоянием до вектора признаков нового объекта (поиск соседей).
Для упорядоченных значений признаков находится Евклидово расстояние:
где – количество признаков.
Вначале, найдя число , мы узнали, сколько записей будет иметь право голоса при определении класса. Затем мы выявили эти записи, расстояние от которых до новой оказалось минимальным. Теперь можно приступить к ***стому невзвешенному голосованию.
Расстояние от каждой записи при голосовании здесь больше не играет роли. Все имеют равные права в определении класса. Запись отдает предпочтение тому классу, к которому она принадлежит, а тот, который наберет наибольшее количество голосов, присваивается новой записи.
Информация о работе Метод ближайших соседей в задаче классификации