Глава 2.Разработка приложений
МИНИСТЕРСТВООБРАЗОВАНИЯИНАУКИ
РОССИЙСКОЙФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕГОСУДАРСТВЕННОЕАВТОНОМНОЕ
ОБРАЗОВАТЕЛЬНОЕУЧРЕЖДЕНИЕВЫСШЕГООБРАЗОВАНИЯ«ТЮМЕНСКИЙГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТ»
Институтматематикиикомпьютерныхнаук
Кафедрапрограммногообеспечения
Курсоваяработа
подисциплине«Структурыиалгоритмыкомпьютернойобработкиданных»
натему:«Исследованиекачестваосновныхалгоритмовмашинногообучениядлярешениязадачиклассификации»
Выполнил:
Студентгруппы164-1
ПоляковИгорьАндреевич
Проверил:
_______________________ ст.преподавателькафедрыпрограммногообеспечения
ПавловаЕленаАлександровна
Оглавление
Введение. 3
Глава 1.Теоретические сведения. 4
1.1.Упрощенный байесовский классификатор. 4
1.2. Нейронная сеть. 7
Глава 2. Разработка приложений. 12
2.1. Используемые классы и методы Байесовского классификатора. 13
2.1.1. Демонстрация работы приложения для классификации пола. 13
2.2. Используемые классы и методы Нейронной сети. 15
2.2.1. Демонстрация работы приложения для классификации цвета. 16
Список литературы.. 18
Приложение 1. 19
Приложение 2. 22
Введение
Вмашинномобучениизадачаклассификацииотноситсякразделуобучениясучителем.Разделмашинногообучения,посвященныйрешениюследующейзадачи.Имеетсямножествообъектов(ситуаций)имножествовозможныхответов(откликов,реакций).Существуетнекотораязависимостьмеждуответамииобъектами,ноонанеизвестна.Известнаконечнаясовокупностьпрецедентов—пар«объект,ответ»,называемаяобучающейвыборкой.Наосновеэтихданныхвосстанавливаетсязависимость,тоестьзадача в построенииалгоритма,способногодлялюбогообъектавыдатьточныйответ.Дляизмеренияточностиответовопределённымобразомвводитсяфункционалкачества.
|
|
|
Подучителемпонимаетсялибосамаобучающаявыборка,либотот,ктоуказалназаданныхобъектахправильныеответы.Существуеттакжеобучениебезучителя,в этом случаенаобъектахвыборкиответынезадаются.
Формулировказадачи
1. Изучитьосновныеалгоритмыклассификации.
2. Реализоватьдва основныхалгоритмовклассификации.
Цельработы
Целью даннойработыбылоизучениекачестваалгоритмовклассификацииипрограммнаяреализациянескольких изних.
Существуютнесколькоосновныхвидовалгоритмовклассификациисобучающейвыборкой:
· Упрощенныйбайесовскийклассификатор
· Нейронные сети.
Глава1.Теоретическиесведения
Упрощенныйбайесовскийклассификатор
ФормулаБайесапозволяетпоменятьместамипричинуиследствиевформулахсусловнымивероятностями[1]:
P(A|B)–апостериорнаявероятностьданногоклассаc(т.е.данногозначенияцелевойпеременной)приданномзначениипризнакаx.
|
|
|
P(A)–априорнаявероятностьданногокласса.
P(B|A)–правдоподобие,т.е.вероятностьданногозначенияпризнакаприданномклассе.
P(B)–априорнаявероятностьданногозначенияпризнака.
ПустьвкачествеAбудетрассматриватьсянекотороемножествоклассовC,которыммогутпринадлежатьобъекты;авкачествеB–наборпризнаков(векторпредикторов)X1,X2,…,Xn,X2,…,Xn,позначениямкоторымможноотнестилюбойобъекткодномуизклассов.ВэтихобозначенияхформулаБайесаперепишетсяследующимобразом:
Если,например,рассматриваютсятрикласса:«флет»,“трендвверх”,“трендвниз”,авкачествепредикторов(наблюдаемогонаборапризнаков)выступаетденьнеделиивчерашнеесостояниетренда,тоформулаБайесаприметвид (3):
гдеслучайнаявеличинаCможетприниматьтризначения0(флет),1(uptrend,трендвверх)и-1(downtrend,трендвниз);предикторX1принимаетзначенияMn,Tu,Wd,ThиFr(рабочиеднинеделиспонедельникадопятницы);предикторX2–тежезначения,чтоиC(флет,трендвверхилитрендвниз,ноимеетсяввидунаправлениерынкавтечениепредыдущегодня).
ВчислителеP(C)–этоаприорныевероятноститого,чтолюбойизрассматриваемыхобъектов(споканеизвестнымипризнаками)окажетсяпринадлежащимданномуклассу.Внашемпримеретритакихвероятности,дляфлетаидлятрендовобоихнаправлений:P0,P1,иP−1.
|
|
|
ЗнаменательвформулеБайесаP(X1,X2)–вероятноститого,чтонаугадвзятыйобъектбудетиметьзаданныйнаборзначенийпризнаков.Врассматриваемом примере15такихвероятностей:P(Mn,-1),P(Tu,-1),…,P(Mn,0),…,P(Fr,1).
P(X1,X2∣C)–этоусловныевероятноститого,чтообъект,принадлежащийданномуклассу,имеетзаданныйнаборпризнаков.Внашемпримере5⋅3⋅3=45такихвероятностей:
P(Mn,−1∣1),P(Tu,−1∣−1),…,P(Fr,1∣1).
Если,известнывсевероятности,стоящиевформулеБайесасправаотзнакаравенства,тогдаможнорассчитатьусловнуювероятностьслева.Тогдаполюбомунаборузначенийпризнаковможнонайтивероятностьотнестипредъявленныйобъектккаждомуизклассов.Какаявероятностьокажетсябольше,тотклассивыбирается.ВероятностьвзнаменателеформулыБайесаможнонерассматривать,посколькуонанезависитоттого,ккакомуклассупринадлежиттотилиинойобъект.Чтобывыбратьнаибольшеезначениеизвсехрассчитанных,намдостаточнознатьтольковероятности,стоящиевчислителе.
Байесовскийклассификатортребуетобучения: нужно получитьнаборобъектовсразличнымизначениямипризнаков(впримереэтоизмененияцензакакой-либоотрезокистории)исообщаем,ккакомуклассудолженбытьотнесёнкаждыйизэтихобъектов.Описанныйпроцессназываетсяобучениемсучителем(учитель–этотот,ктознает,ккакомуклассудолжныбытьотнесеныобъекты).Врезультатеобученияклассификатордолженнайтизначениявсехвероятностей,стоящихвформулеБайесасправаотзнакаравенствавчислителе.
|
|
|
Нозадачуможноупростить,еслипредположить,чтовсепризнакинезависимыдруготдруга.Тогдаможновероятностьсложногособытиязаписатьввидепроизведениявероятностейкаждогособытиявотдельности: 
Проще найти n одномерных функций, чем одну n-мернуюфункцию. Для нашего примера вместо 45-ти условных вероятностей P(X1,X2∣C)P(X1,X2∣C)надооценитьпоэкспериментальнымданнымизобучающейвыборкинезависимодруготдруга15значенийP(X1∣C)P(X1∣C)(5рабочихднейнеделина3состояниярынка)и9значенийP(X2∣C)P(X2∣C)(трисостояниярынкавчеранатрисостояниясегодня),т.е. всего 24 искомых параметров вместо 45. При увеличении размерности задачи (количества признаков) выигрыш ещё более заметен.[2]
Такимобразом,упрощенныйбайесовскийклассификатор—этопростойвероятностныйклассификатор,основанныйнапримененииТеоремыБайесас(наивными)предположениямионезависимостипредикторов:
[1]
Из основных преимуществ—простотареализацииинизкиевычислительныезатраты(О (N*M*C+N)), где N-количество признаков, M-длина множества признаков, C-количество классов классификации,приобучениииклассификации.Вслучаях,когдапризнакинезависимы(илипочтинезависимы),наивныйбайесовскийклассификаторпрост в создании математической модели.Основнойнедостаток—относительнонизкоекачествоклассификациивбольшинствереальныхзадач.Чащеониспользуетсяиликак«примитивный»эталондлясравненияразличныхмоделейалгоритмов,иликакэлементарный«строительныйблок»валгоритмическихкомпозициях подобных примеру на рис 1.[2]
| Начало |
| Генерация обучающей выборки |
| Получение входных данных в виде списка признаков объекта |
| Вычисление вероятности каждого из классов с учетом всех признаков |
| Вычисление полных вероятностей для каждого класса |
| Получение вероятности полных классов |
| Конец |
Рис 1. Блок-схема алгоритма наивной байесовской классификации.
Преимуществабайесовскогоподхода.
· Байесовскоерешающееправилопросто в понимании,выписываетсявявноманалитическомвиде,легкореализуетсяпрограммно.Наегоосновестроятсямногиеметодыклассификации.
· Приклассификацииобъектазаоднооцениваютсяаприорныевероятностиегопринадлежностикаждомуизклассов.Этаинформацияиспользуетсявомногихприложенияхдляоценкирисков.
· Байесовскоерешающееправилоудобноиспользоватьвкачествеэталонапритестированииалгоритмовклассификациинамодельныхданных.
Недостаткибайесовскогоподхода.
· Модельточналишьвслучае,когдавыполняетсяпредположениеонезависимости.Впротивномслучае,строгоговоря,вычисленныевероятностиуженеявляютсяточными(идажеболеетого,ихсуммаможетнеравнятьсяединице,из-зачеготребуетсянормироватьрезультат).Однаконапрактикенезначительныеотклоненияотнезависимостиприводятлишькнезначительномуснижениюточности,идажевслучаесущественнойзависимостимеждупеременнымирезультатработыклассификаторапродолжаеткоррелироватьсистиннойпринадлежностьюобразакклассам.
· Есливтестовомнабореданныхприсутствуетнекотороезначениекатегорийногопризнака,котороеневстречалосьвобучающемнабореданных,тогдамодельприсвоитнулевуювероятностьэтомузначениюинесможетсделатьпрогноз.Этоявлениеизвестноподназванием«нулеваячастота».Даннуюпроблемуможнорешитьспомощьюсглаживания.ОднимизсамыхпростыхметодовявляетсясглаживаниепоЛапласу.
Нейронная сеть
Искусственная нейронная сеть (ИНС) — математическая модель, а также её программное или аппаратное воплощение, построенная по принципу организации и функционирования биологических нейронных сетей — сетей нервных клеток живого организма. Это понятие возникло при изучении процессов, протекающих в мозге, и при попытке смоделировать эти процессы. Первой такой попыткой были нейронные сети У. Маккалока и У. Питтса. После разработки алгоритмов обучения получаемые модели стали использовать в практических целях: в задачах прогнозирования, для распознавания образов, в задачах управления и др.[7]
В качестве образов могут выступать различные по своей природе объекты: символы текста, изображения, образцы звуков и т. д. При обучении сети предлагаются различные образцы образов с указанием того, к какому классу они относятся. Образец, как правило, представляется как вектор значений признаков. При этом совокупность всех признаков должна однозначно определять класс, к которому относится образец. В случае, если признаков недостаточно, сеть может соотнести один и тот же образец с несколькими классами, что неверно. По окончании обучения сети ей можно предъявлять неизвестные ранее образы и получать ответ о принадлежности к определённому классу.
Топология такой сети характеризуется тем, что количество нейронов в выходном слое, как правило, равно количеству определяемых классов. При этом устанавливается соответствие между выходом нейронной сети и классом, который он представляет. Когда сети предъявляется некий образ, на одном из её выходов должен появиться признак того, что образ принадлежит этому классу. В то же время на других выходах должен быть признак того, что образ данному классу не принадлежит. Если на двух или более выходах есть признак принадлежности к классу, считается, что сеть «не уверена» в своём ответе [6].
В рассматриваемом примере используется архитектура персептрона с одним скрытым слоем, (рис.2) состоящая из трёх типов элементов, а именно: поступающие от датчиков сигналы передаются ассоциативным элементам,
а затем реагирующим элементам. Таким образом, персептроны позволяют создать набор «ассоциаций» между входными стимулами и необходимой реакцией на выходе
Рис. 2.Логическая схема персептрона с тремя выходами
Оптимизация методом роя частиц
Алгоритм ParticleSwarmOptimization (PSO) основывается на концепции социального взаимодействия при решении проблем, предполагает нахождение локального экстремума, изменение опыта частицы, находящейся в N-мерном пространстве для возможности передачи соседним сигнала изменения направления. В модели PSO каждая частица обладает вектором скорости и вектором позиции. При оптимизации N-мерной функции такие векторы имеют размерность N. Как и в биологической жизни, предполагается, что каждая частица регулирует свои векторы позиции и скорости в соответствии с собственным опытом (когнитивная составляющая), а также по информации, полученной от других членов социума (социальный опыт). Когнитивный опыт частицы понимается как ее знание о лучшей позиции, в которой она сама находилась, а социальное знание частицы – как знание о лучшей позиции, через которую прошла одна из частиц в одной группе с ней. В задаче оптимизации лучшая позиция частицы понимается как позиция, в которой минимизируется значение функции.
Таким образом, состояние каждой частицы роя характеризуется:
1. Тремя N-мерными векторами: Х – текущая позиция частицы в поисковом пространстве; G – лучшая позиция, найденная всем роем; v – скорость движения частицы.
2. Двумя скалярными значениями, описывающими качество решения задачи: P – фитнес-частицы (значение целевой функции в текущей позиции); G – фитнес-группы, в которую входит частица (значение целевой функции в лучшей позиции).
Изменение положения частицы задается добавлением v-вектора к X-вектору: Xi = Xi + vi. Изначально значение вектора скорости генерируется случайным образом в пределах [–vmax, vmax], где vmax – максимально допустимое значение. Скорость частицы модифицируется по формуле vi = vi + c1r1(G – Xi ) + c2r2(Pi – Xi ), где i – номер частицы; vi – вектор скорости; Xi – вектор позиции частицы; Pi – вектор лучшей позиции, которой достигала частица; G – вектор лучшей позиции, которой достигала группа из I частиц; с1, с2 – константы скорости обучения, управляющие соответственно социальной и познавательной компонентой; r1, r2 – случайные числа в диапазоне [0, 1], которые служат для поддержания разных траекторий частиц при поиске. Константы скорости обучения контролируют степень важности индивидуального познания и социального знания. Частица одновременно обновляет свою позицию относительно лучшей позиции группы и собственной лучшей позиции, которая была в прошлом. Если с2 имеет преобладающее значение, то частица будет обследовать узкую область поискового пространства, а если преобладает с1, то происходит поиск в большом пространстве. В формулу может вводиться фактор инерции W: vi = Wvi + c1r1(Pi – Xi ) + c2r2(G – Xi ). Вначале фактор инерции W = 1, а потом он постепенно уменьшается во времени по формуле W= Wmax – (Wmax – Wmin)n/N, где n – номер текущей итерации; N – заданное число итераций. При инициализации частицы распределяются случайным образом в поисковом пространстве, их скорость получает случайные значения в допустимом диапазоне. Таким образом, работу алгоритма оптимизации PSO можно описать Рис. 3[7]
Рис. 3.Алгоритм оптимизации роем частиц
| Начало |
| Генерация обучающей выборки |
| Создание тренировочных и тестовых матриц с разделением 80%-20% |
| Тренировка с использованием PSO |
| Нахождение и загрузка лучших весов |
| Анализ точности нейронной сети на тестовых данных |
| Конец |
Рис 4. Блок-схема алгоритма классификации нейронной сети.
Глава 2.Разработка приложений
Разработаны модули для исследования качестве алгоритмов на принципе коннектевизма и дискриминантного анализа. В примере байесовского классификатора рассматривается реализация,основанная на нереалистичном предположении о статистической независимости признаков. Нейронная сеть организована по принципу многослойного перцептрона Розенблатта, проверяется изменение точности при различном количестве скрытых слоев.
Дата добавления: 2018-05-01; просмотров: 146; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!