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

• Содержание
• Введение
• 1. Анализ и формализация поставленной задачи
• 1.1 Анализ задачи
• 1.2 Обоснование выбора средств реализации
• 2. Разработка структуры обучающей системы
• 3. Разработка программного обеспечения
• 3.1 Поиск в пространстве версий
• 3.1.1 Краткое описание задачи
• 3.1.2 Описание реализации алгоритма поиска от частного к общему
• 3.1.3 Описание реализации алгоритма поиска от общего к частному
• 3.1.4 Описание реализации алгоритма исключения кандидата
• 3.2 Индуктивный алгоритм построения дерева решений ID3
• 3.2.1 Краткое описание задачи
• 3.2.2 Описание реализации алгоритма построения дерева решений ID3
• 3.3 Системы классификации
• 3.3.1 Теоретические сведения
• 3.3.2 Описание программной реализации
• 3.4 Игра «Искусственная жизнь»
• 3.4.1 Теоретические сведения
• 3.4.2 Описание программной реализации
• 4. Руководство пользователя
• 4.1 Системные требования
• 4.2 Руководство по инсталляции обучающей системы
• 5. Экономическое обоснование
• 5.1 Краткая характеристика работы и её назначение.
• 5.2 Определение затрат на создание программного продукта
• 5.2.1 Расходы на оплату труда разработчиков программы
• 5.2.2 Расчет стоимости оборудования
• 5.2.3 Расчет стоимость программного обеспечения
• 5.2.4 Расчет затрат на электроэнергию
• 5.2.5 Расчет стоимости арендной платы
• 5.2.6 Расчет затрат на отопление помещения
• 5.2.7 Общая стоимость разработки продукта
• 5.3 Оценка издержек
• 5.3.1 Постоянные издержки
• 5.3.2 Переменные издержки
• 5.4 Определение себестоимости продукции. Точка безубыточности
• 5.5 Экономический эффект у пользователя
• 6. Охрана труда
• 6.1 Анализ системы «человек-машина-среда»
• 6.1.1 Особенности работы пользователя с ПК
• 6.1.2 Неблагоприятные факторы воздействия при работе с ПК
• 6.1.3 Меры по организации и оборудованию рабочих мест
• 6.2 Технические и организационные меры по устранению вредных производственных факторов
• 6.3 Техника безопасности при работе с ПК
• Введение

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

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

– отсутствие ограничений по времени - изучение материала может быть не связано с временными рамками, такими как расписание аудиторных занятий;

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

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

– наличие гиперссылок - возможность более быстрого перехода от одного участка учебника к другому;

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

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

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

1. Анализ и формализация поставленной задачи

1.1 Анализ задачи

В традиционном обучении преобладают вербальные средства при изучении нового материала. В связи с этим применение аудио фрагментов в электронном учебнике позволяет не только приблизить его к привычным способам предъявления информации, но и улучшить восприятие нового материала, при этом активизирует не только зрительные, но и слуховые центры головного мозга. По данным ЮНЕСКО при аудиовосприятии усваивается только 12% информации, при визуальном - около 25%, а при аудиовизуальном - до 65% воспринимаемой информации.

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

К содержимому материала теоретической части предъявляется ряд требований:

– учебный материал должен быть разбит на блоки;

– наличие гиперссылок - возможность более быстрого перехода от одного участка учебника к другому;

каждый фрагмент, наряду с текстом, должен представлять информацию в формате аудио;

каждый блок должен быть снабжен иллюстрациями;

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

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

1.2 Обоснование выбора средств реализации

Исходя из поставленных задач следует выбрать средства для разработки учебника. Теоретический материал учебника представляет собой текст, сопровождаемый иллюстрациями. Большинство аналогичных известных продуктов реализовано в виде систем помощи в формате СHM. Это дает возможность удобной навигации по содержимому учебника, а также возможность легкого доступа по сети. CHM - это расширение файла в формате Compressed HTML Help, скомпилированный набор HTML страниц, данный формат был разработан Microsoft для гипертекстовых справочных систем. Для просмотра CHM файлов достаточно наличия в системе Internet Explorer. У CHM файлов, как правило, есть Содержание - отдельная панель со списком статей для упрощения навигации. В наличии содержания, пожалуй и заключается главное отличие CHM файлов от использовавшихся ранее HLP файлов справки Windows. На сегодняшнее время существует большое количество программ, которые позволяют создать такую справочную систему. Рассмотрим наиболее популярные из них: HTML Help Workshop и HelpScribble.

HTML Help Workshop - инструмент для авторской разработки справочных файлов(.chm), имеющий легкий для использования графический интерфейс, с помощью которого можно создавать проекты, гипертекстовые разделы, файлы содержания, индексные файлы, а также прочие элементы, которые вам могут понадобиться для последующего объединения справочной системы или сетевого сайта. Она состоит из следующих компонентов: HTML Help Workshop, Контроль управления HTML Help ActiveX, Программа просмотра HTML Help, Редактор изображений Microsoft HTML Help, Java-апплет HTML Help, Выполняемая программа HTML Help, Компилятор HTML Help.

HelpScribble - программа для создания систем помощи WinHelp (.hlp) и HTML Help (.chm) со всеми присущими HTML Help Workshop функциями. Кроме создания систем помощи, возможна разработка веб-документации, а также экспорт созданной системы помощи в RFT-файл. Программа может интерферироваться в Delphi и C++ Builder, так же имеется поддержка макросов. К одним из существенных недостатков относятся: для генерации CHM-файлов требуется установка Microsoft HTML Help Workshop и распространяется бесплатно, но срок ее функционирования ограничен, как правило, тридцатью дням, после чего необходимо приобрести лицензию.

Таким образом, для создания электронного учебника будем использовать программу HTML Help Workshop, так как по функциональности она не уступает HelpScribble и при этом не надо тратить деньги на приобретение лицензии, что играет не маловажную роль на сегодняшний день.

Для реализации практических примеров использовался язык программирования Visual С# с использованием интегрированной среды MS Visual Studio .NET 2008.

Использование Microsoft Visual Studio .Net 2008 обеспечит быстрое выполнение трудоемких задач, вывод на экран графической информации, приложение, разработанное в данной среде, будут работать на всех системах семейства Windows, так же дает возможность адаптации программ для переноса на другие платформы. Это, в свою очередь, дает возможность легкого распространения приложения. Так же мы решаем проблемы программного обеспечения. Для нормальной работы системы необходимо установка только Microsoft Framework, установка всего пакета Microsoft Visual Studio не требуется.

Visual C#-- это язык программирования, предназначенный для разработки самых разнообразных приложений, предназначенных для выполнения в среде .NET Framework. Язык Visual C# прост, строго типизирован и объектно-ориентирован. Благодаря множеству нововведений Visual C# обеспечивает возможность быстрой разработки приложений и его код является в высшей степени переносимым. При соответствующей доработке с использованием технологии ASP.Net этот учебник может стать общедоступным посредством ресурсов Internet.

2. Разработка структуры обучающей системы

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

Рисунок 2.1 - Экранная форма обучающей системы

Содержание учебника разбито на четыре раздела, в которых дается подробный теоретический материал. Первый раздел, составленный по материалам [1, глава 3], посвящен алгоритмам поиска в пространстве состояний. Во втором разделе рассматривается материала из [1, глава 8] рассуждения в условиях неопределенности. Третий раздел основан на материалах из [1, глава 8] и [1, глава 11] и в нем представлена информация о машинном обучение: основанному на символьном представлении информации и на основе социальных и эмерджентных принципов. Раздел «Библиография» содержит список источников, ссылки на которые приводятся в учебнике. Список использованных источников взят из [1].

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

Рисунок 2.2 Панель аудиовоспроизведения

После изучения теоретического материала пользователь имеет возможность увидеть работу изученного алгоритма на примере. Для этого по тексту учебника после описания алгоритмов включены ссылки в виде командных кнопок как на рисунке 2.3.

Рисунок 2.3 Кнопка «Запуск примера»

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

3. Разработка программного обеспечения

3.1 Поиск в пространстве версий

3.1.1 Краткое описание задачи

Поиск в пространстве версий (version space search) иллюстрирует индуктивное обучение как реализацию поиска в пространстве понятий. Поиск в пространстве версий основан на том, что операция обобщения упорядочивает понятия в пространстве поиска. Затем этот порядок используется для выбора направления поиска.

Обобщение и специализация - самые типичные операции при определении пространства понятий. К основным операциям обобщения, применяющимся в машинном обучении, относятся следующие:

Замена конкретных значений переменными. Например,

color(ball, red)

приводится к виду

color(X, red).

Исключение условий из конъюнктивных выражений. Так,

shape(X, round) size(X, small) color(X, red)

сводится к выражению

shape(X, round) color(X, red).

Добавление в выражение операции дизъюнкции. Например,

shape(X, round) size(X, small) color(X, red)

приводится к

shape(X, round) size(X, small) (color(X, red) color(X, blue)).

Замена свойства родительским объектом согласно иерархии классов. Если объект primary_color является суперклассом для свойства red, то

color(X, red)

заменяется на

color(X, primary_color).

Рассмотрим множество объектов со следующими свойствами

Sizes = {large, small}

Colors = {{red, white, blue}

Shapes = {ball, brick, cube}

Эти объекты можно представить с помощью предиката

obj(Sizes, Colors, Shapes).

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

Представлены три алгоритма поиска в пространстве версий (version space), представляющем собой множество всех описаний понятия, согласующихся с обучающими примерами. Эти алгоритмы работают за счет сужения пространства версий с появлением новых примеров. Первые два алгоритма обеспечивают сужение пространства версий в направлении от частного к общему и от общего к частному соответственно (рисунки 3.3, 3.4). Третий алгоритм, называемый алгоритмом исключения кандидата (candidate elimination), объединяет оба подхода и реализует двунаправленный поиск (рисунок 3.5).

Эти алгоритмы основаны на данных. Обобщение выполняется на основе обнаруженных в обучающих данных закономерностей. Кроме того, поскольку в этих алгоритмах используются классифицированные обучающие данные, они считаются разновидностью обучения с учителем (supervised learning).

Алгоритмы поиска в пространстве версий используют и положительные, и отрицательные примеры целевого понятия. Хотя операцию обобщения можно реализовать только на положительных примерах, отрицательные примеры позволяют предотвратить излишнее обобщение. Изученное понятие должно быть не только общим, чтобы соответствовать всем положительным примерам, но и частным, чтобы исключить все отрицательные. В пространстве, представленном на рисунке 3.1, все множество положительных экземпляров покрывается понятием obj(X, Y, Z).

Рисунок 3.1 - Пространство понятий

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

Рисунок 3.2 - Роль отрицательных примеров

Рисунок 3.3 - Поиск от частного к общему

Рисунок 3.4 - Поиск от общего к частному

Рисунок 3.5 -Алгоритм исключения кандидата

3.1.2 Описание реализации алгоритма поиска от частного к общему

В программе «Поиск от частного к общему» алгоритм поиска реализован на примере, подобном описанному в [1, 9.2.2].

1. Класс exemplar. Она используется для описания гипотез и обучающих примеров.

Членами (полями) класса являются:

1) color типа string - цвет объекта;

2) size типа string - размер объекта;

3) shape типа string - форма объекта;

2. s_list типа ArrayList - список существующих гипотез;

3. n_list типа ArrayList - список для хранения отрицательных примеров;

4. p_list типа ArrayList - список для хранения положительных примеров;

goal типа string - цель обучения;

Работа программы разделена на два этапа. Сначала пользователь должен обучить систему новому понятию. Для этого предусмотрен режим обучения. Затем он может проверить качество обучения в режиме тестирования. До начала обучения пользователь должен сообщить программе изучаемое понятие.

Алгоритм поиска реализован с помощью двух процедур:

1. PartToGenSearch (с входным параметром positive тип bool - отображающий к какому виду примеров он относится) для осуществления по шагового отображения выполнения алгоритма;

2. PartToGenSearch_Auto для реализации автоматического режима выполнения алгоритма.

Замена гипотезы минимальным более общим понятием при обработке положительного примера происходит следующим образом. Последовательно просматриваются все поля гипотезы (цвет, размер, форма). Если в поле гипотезы стоит переменная (X, Y или Z), то это поле пропускается. Если же в поле гипотезы записана константа (например, красный), то это поле сравнивается с соответствующим полем заданного примера, и если они не равны, то в гипотезу записывается переменная. Если это поле характеризует цвет, то записывается X, если размер, то Y, а если форму, то Z.

Затем согласно алгоритму из множества гипотез удаляются все гипотезы, более общие, чем некоторые другие. Просматривая список гипотез, ищем гипотезу с двумя переменными. Если нашли такую гипотезу, то начинаем искать гипотезу с одной переменной, т.к. только такая гипотеза может быть более частной. Если найдена такая гипотеза. То проверяем, не является ли она более частной, чем ранее найденная гипотеза. Для этого берем гипотезу с двумя переменными и сравниваем ее поле, значение которого является константой с соответствующим полем гипотезы с одной переменной. Если эти поля равны, то это означает, что гипотеза с одной переменной является более частной. Тогда гипотеза с двумя переменными удаляется из списка.

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

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

3.1.3 Описание реализации алгоритма поиска от общего к частному

В программе «Поиск от общего к частному» алгоритм поиска реализован на примере, подобном описанному в [1, 9.2.2] и [2].

Основные данные программы представлены следующим образом:

1. Класс exemplar. Она используется для описания гипотез и обучающих примеров.

Членами (полями) класса являются:

4) color типа string - цвет объекта;

5) size типа string - размер объекта;

6) shape типа string - форма объекта;

2. g_list типа ArrayList - список максимально конкретных значений;

3. n_list типа ArrayList - список для хранения отрицательных примеров;

4. p_list типа ArrayList - список для хранения положительных примеров;

5. goal типа string - цель обучения;

6. color_arr - массив элементов типа string, в котором хранятся возможные значения цветов объекта;

7. size_arr - массив элементов типа string, в котором хранятся возможные значения размеров;

8. shape_arr - массив элементов типа string, в котором хранятся возможные значения формы;

Последние три массива используются при операции замены элемента множества G его наиболее общей специализацией.

Алгоритм поиска реализован с помощью двух процедур:

3. GenToPartSearch (с входным параметром positive тип bool - отображающий к какому виду примеров он относится) для осуществления по шагового отображения выполнения алгоритма;

4. GenTopartSearch_Auto для реализации автоматического режима выполнения алгоритма.

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

При задании пользователем положительного примера из списка g_list удаляются все гипотезы, не удовлетворяющие этому примеру. Просматривая список гипотез, программа проверяет ее соответствие положительному примеру. Если в поле гипотезы записана переменная или его значение равно значению соответствующего поля примера, то это означает, что гипотеза удовлетворяет примеру по данной позиции. Если по какой-либо позиции гипотеза не удовлетворяет примеру, то она удаляется. Рассмотренный пример добавляется в список p_list.

Работа с отрицательным примером происходит следующим образом. Просматривается список гипотез с целью нахождения гипотезы удовлетворяющей отрицательному примеру. Если такая гипотеза найдена, то сначала запоминается ее позиция в списке, а затем начинается замена гипотезы ее наиболее общей специализацией, не удовлетворяющей отрицательному примеру. Поочередно просматриваются все поля гипотезы. Если в поле гипотезы записана переменная, то в список гипотез добавляется множество гипотез, таких чтобы значение этого поля в них отличалось от значения поля в отрицательном примере. Предположим, мы рассматриваем поле color и в нем записана переменная X, а в обучающем примере в этом поле записано red. Тогда в список g_list добавляется множество всех возможных гипотез, в которых значение color не равно red (например, blue, white и т.д.). При этом остальные поля записываются с теми же значениями, что и в рассматриваемой гипотезе. После просмотра всех гипотез, помеченные на удаление удаляются из списка g_list.

Затем из списка гипотез удаляются все гипотезы, более частные, чем некоторые другие, а также гипотезы, не удовлетворяющие примерам из p_list. Аналогичные процедуры описаны в разделе, поэтому здесь их описание опускается.

3.1.4 Описание реализации алгоритма исключения кандидата

Алгоритм исключения кандидата объединяет описанные выше алгоритмы. В программе используются те же типы данных, только здесь одновременно поддерживаются два списка гипотез: g_list - множество максимально общих понятий-кандидатов (G) и s_list - множество максимально конкретных (S). Большинство этапов работы алгоритма повторяют работу алгоритмов описанных выше, поэтому здесь их описание опускается.

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

На каждом шаге работы алгоритма проверяется равенство множеств g_list и s_list. Если они равны и оба содержат по одному элементу, то программа выдает сообщение о том, что найдено единственное понятие, удовлетворяющее всем данным.

Затем проверяется второе условие. Если множества g_list и s_list пусты, то программа выдает сообщение о том, что не существует понятия, покрывающего все положительные примеры и не удовлетворяющего отрицательным.

3.2 Индуктивный алгоритм построения дерева решений ID3

3.2.1Краткое описание задачи

Алгоритм ID3 подобно методу исключения кандидата обеспечивает изучение понятий на примерах. Особый интерес представляют способ хранения полученных знаний, подход к управлению сложностью, эвристика для выбора понятий-кандидатов и возможности обработки зашумленных данных. В алгоритме ID3 понятия представляются в виде дерева решений (decision tree) [1], [3].Такое представление позволяет классифицировать объект путем проверки значения определенных свойств.

Рассмотрим задачу оценки кредитного риска на основе кредитной истории, текущего долга, наличия поручительства и дохода. В таблице 3.1 представлены примеры с известным кредитным риском. Дерево решений на рисунке 3.6 содержит приведенные в таблице 3.1 данные и позволяет корректно классифицировать все объекты в таблице. Каждый внутренний узел дерева решений представляет некоторое свойство, например, кредитную историю или доход. Каждому возможному значению этого свойства соответствует ветвь дерева. Узлы-листья отражают результаты классификации, в частности, низкий, высокий или средний риск.

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

Процесс завершается при достижении конечного узла, определяющего класс объекта.

Таблица 3.1 - Данные о кредитной истории

№	Риск	Кредитная история	Долг	Поручительство	Доход, $
1	Высокий	Плохая	Высокий	Нет	От 0 до 15
2	Высокий	Неизвестна	Высокий	Нет	От 15 до 35
3	Средний	Неизвестна	Низкий	Нет	От 15 до 35
4	Высокий	Неизвестна	Низкий	Нет	От 0 до 15
5	Низкий	Неизвестна	Низкий	Нет	Свыше 35
6	Низкий	Неизвестна	Высокий	Адекватное	Свыше 35
7	Высокий	Плохая	Низкий	Нет	От 0 до 15
8	Средний	Плохая	Низкий	Адекватное	Свыше 35
9	Низкий	Хорошая	Низкий	Нет	Свыше 35
10	Низкий	Хорошая	Высокий	Адекватное	Свыше 35
11	Высокий	Хорошая	Высокий	Нет	От 0 до 15
12	Средний	Хорошая	Высокий	Нет	От 15 до 35
13	Низкий	Хорошая	Высокий	Нет	Свыше 35
14	Высокий	Плохая	Высокий	Нет	От 15 до 35

По алгоритму ID3 каждый узел дерева представляет некоторое свойство, на основании которого выполняется разделение набора примеров. Таким образом, алгоритм рекурсивно строит поддерево для каждого раздела. Эта процедура длится до тех пор, пока все элементы раздела не будут отнесены к одному и тому же классу. Этот класс становится конечным узлом дерева.

Шеннон определил количество информации в сообщении как функцию от вероятности р передачи каждого возможного сообщения, а именно -log₂p. Имея пространство сообщений M={m₁, m₂, … m_n} и зная вероятности p(m_i) для каждого сообщения, информативность этих сообщений можно вычислить по формуле

I[M] = = E[-log₂p(m_i)] . (3.1)

Количество информации в сообщении измеряется в битах.

Рисунок 3.6 - Дерево решений для оценки кредитного риска

Информативность дерева вычисляется на основе вероятностей различных типов классификации. Если предположить, что все примеры в таблице 4.1 появляются с одинаковой вероятностью, то

р (высокий риск) = 6/14, р (средний риск) = 3/14 и р (низкий риск) = 5/14.

Следовательно, информативность распределения D₁ , описанного в таблице 3.1, а значит, и любого дерева, покрывающего эти примеры, составляет

I[D_4.1] = - 6/14 log₂(6/14) - 3/14 log₂(3/14) - 5/14 log₂(5/14) =

= - 6/14 * (-1,222) - 3/14 * (-2,222) - 5/14 * (-1,485) = 1,531 бит

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

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

Если корнем текущего дерева является свойство Р, которое может принимать n значений, то множество обучающих примеров С будет разделено на подмножества {C₁, C₂,…, C_n}. Информация, необходимая для завершения построения дерева при выборе Р, составляет

E[P] = . (3.2)

где С_i - подмножество.

Выигрыш от использования свойства Р вычисляется как разность общей информативности дерева и объема информации, необходимого для завершения построения дерева:

gain(P) = I[C] - E[P] (3.3)

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

В алгоритме ID3 предполагается, что минимальное дерево, корректно классифицирующее все обучающие примеры, вероятнее всего, будет корректно классифицировать и последующие обучающие примеры.

3.2.2 Описание реализации алгоритма построения дерева решений ID3

При разработке демонстрационного примера использовался объектно-ориентированный подход. Для того чтобы упростить создание приложения были разработан класс ID3class: для ввода входных значений, реализации алгоритма построения дерева решения и тестирования правильности решения. Класс ID3class является основным классом, так же существует два дополнительных класса, которые необходимы для организации главного класса: node - класс для описания узла в разложении дерева; DataPoint - класс для описания для предоставления точки данных представляющих набор значений атрибутов, т.е. обучающих примеров.

Последний класс содержит единственное поле attributes массив типа int, значения каждого из атрибутов для данного примера хранятся в этом массиве. Такое представление делает сопоставления значений атрибутов проще, он включает в себя только целое сравнения и нет сравнения строк.

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

Таблица 3.1 - Список полей класса node

Поле	Тип	Описание
entropy	double	энтропии точек данных
data	ArrayList	набор данных
decompositionAttribute	int	атрибут, который используется для разделения данных
decompositionValue	int	значение атрибута
children	массив типа node	ссылки на дочерние узлы
parent	node	ссылка на родительский узел

Основной класс ID3class содержит методы (таблица 3.3), которые реализуют работу самого алгоритма, исходя из входных данных, которые представлены полями класса (таблица 3.2).

Таблица 3.2 - Список полей класса ID3class

Поле	Тип	Описание
numAttributes	int	количество атрибутов
attributeNames	массив string	список атрибутов
domains	массив ArrayList	список содержащий значения атрибутов
find_ex	класс DataPoint	пример для которого ищется решение
root	класс node	начальный узел с которого очуществляется построения дерева решения

Таблица 3.3 - Список методов класса ID3class

Метод	Описание
int getSymbolValue (int attribute, String symbol)	Осуществляет поиск числовому значению атрибута. Если число не существует в списке значений, символ добавляется в список значений атрибута
int[] getAllValues (ArrayList data, int attribute)	Выполняет поиск всех значений заданого атрибута.
ArrayList getSubset (ArrayList data, int attribute, int value)	Выполняет разделение набора данных на подмножества с одинаковыми значениями атрибута.
double calculateEntropy(ArrayList data)	Вычисляет значение атрибута для выходного атрибута
bool alreadyUsedToDecompose(node a_node, int attribute)	Определяет возможно ли использовать данный атрибут для дальнейшей декомпозиции набора данных
void decomposeNode(node a_node)	Выполняет рекурсивно разложение указанного узла в соответствии с алгоритмом ID3 до тех пор пока это возможно.
void PrinTree(node a_node, TreeNode tr)	Наглядно отображает построенное дерево решения.
string Testing(node a_node)	Выполняет поиск решения для тестового примера.

Основной метод класса - это процедура decomposeNode рекурсивного построения дерева решений, поэтому уделим ей особое внимание. Представление данных атрибутов организовано, так что атрибут, относительно которого выполняется поиск, стоит последним в массиве attributeNames это необходимо для того чтобы не увеличавать число входных параметров метода. В первую очередь необходимо найти энтропию (формула 3.2) для ключевого свойства, далее ищем атрибут с максимальной информативностью (вычисляем по формуле 3.3). После того как определен параметр относительно которого будет выполняться разложения набора данных на подмножества, в поле decompositionAttribute вносим номер этого свойства. Информацию о дочерних узлах добавляем во множество children, для текущего узла, а для его потомков в поле parent вносим ссылку на текущи узел, и decompositionValue присваиваем значение свойства. Далее продолжаем выполнять данную процедуру до тех пор пока это предоставлется возможным осуществлять дальнейщее разделение.

Для иллюстрирации построения дерева решений на форме используются компоненты Windows Forms (таблица 3.4), а для не посредственного потроения самого дерева используется класс .Net TreeView, метод PrinTree как раз и выполняет эту функцию. Процедура рекурсивно выводит в компонент TreeView начиная с корневого узла все элементы дерева. Условием выхода из процедуры является отстствие дочерних узлов.

Таблица 3.4 - Основные используемые компоненты

Компонент	Используемые события	Описание
TextBox: textBox_propt, textBox_value		Поля для ввод атрибутов и их значений.
Button: btn_induce_tree, btn_apl, btn_set_prop, btn_set_val	Click	Кнопки для добавления кандидата, атрибутов и значений атрибутов, так же для выполнения построения дерева решения.
ComboBox: comboBox_value, comboBox_key_prop	SelectedIndexChanged	Выбор и установка значения атрибута.
DataGridView: dt_list_kand		Отображение списка обучающих примеров
ListBox: list_prop	SelectedIndexChanged	Отображение списка свойств.

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

Листинг поцедуры построения дерева решения decomposeNode представлен в приложении 1.

3.3 Системы классификации

3.3.1 Теоретические сведения

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

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

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

Взаимодействие этих компонентов системы классификации можно продемонстрировать на простом примере. Предположим, набор подлежащих классификации объектов определяется шестью атрибутами (условиями с1, с2, …, с6). Допустим также, что каждый из этих атрибутов может принимать 5 различных значений. И хотя каждый атрибут имеет свой физический смысл (например, параметр с3 описывает цвет, а с5 - погоду), без потери общности допустимые значения всех атрибутов можно описать целыми числами {1, 2, …, 5}. Предположим, согласно правилам вывода объекты разбиваются на 4 класса: А1, А2, А3, А4.

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

(с1, с2, с3, с4, с5, с6)Аi, где I=1, 2, 3, 4,

где каждое из условий сi принимает значение из диапазона {1. 2. …. 5} соответствующего атрибута. Обычно условию может соответствовать и произвольное значение # каждого атрибута. В правой части соотношения выражение Ai обозначает один из классов А1, А2, А3 или А4. В таблице 3.1 приводится набор классификаторов. Обратите внимание на то, что несколько различных условных шаблонов могут соответствовать одному классу, как в правилах 1 и 2, либо два одинаковых шаблона могут соответствовать различным классам.

Чтобы упростить изложение, будем рассматривать обучение системы только для класса А1. Не принимая во внимание другие классы, присвоим шаблонам условий значение 1 или 0 в зависимости от соответствия классу А1. Заметим, что это упрощение не ограничивает общности рассуждения, поскольку эти выкладки можно распространить на случай обучения для нескольких классов. Для этого достаточно ввести вектор, соответствующий конкретному условному шаблону. Например, классификатор из таблицы 3.5 можно описать в виде

Таблица 3.5 - Наборы условий для различных классов

Условие (атрибуты)	Действие (класс)	Номер правила
(1###1#)	A1	1
(2##3##)	A1	2
(##43##)	A2	3
(1#####)	A2	4
(##43##)	A3	5

(1###1#)(1000),

(2##3##)(1000),

(1#####)(0100),

(##43##)(0110).

Последняя строка в этом примере соответствует правилам классификации для классов А2 и А3, но не А1 или А4. Заменяя 0 или 1 подобными векторными представлениями классов, можно оценить эффективность правила для классификации на несколько классов.

Для определения корректности классификации будем использовать правила из таблицы 3.1. А именно, будем рассматривать их в качестве учителя для оценки качества правил в системе классификации. Как в большинстве генетических систем обучения, выберем случайным образом исходную популяцию правил. Каждому шаблону условий сопоставим параметр качества (fitness) или силы (strength) (вещественное число из диапазона от 0,0 до 1,0). Этот параметр силы s будем вычислять на основе качества каждого родительского правила с учетом предыстории.

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

(###21#)1 s=0,6,

(##3##5)0 s=0,5,

(21####)1 s=0,4,

(#4###2)0 s=0,23.

Допустим, из среды поступило новое входное сообщение (1 4 3 2 1 5), и учитель (на основе первого правила из таблицы 3.1) классифицировал этот вектор как положительный пример для класса А1. Посмотрим, что происходит при передаче этого образа в рабочую память при попытке его классификации с помощью 4 правил-кандидатов. Этот образ соответствует правилам 1 и 2. Разрешение конфликта между подходящими правилами выполняется на основе конкуренции. В нашем примере степень соответствия каждого правила вычисляется как сумма произведений степеней соответствия каждого из атрибутов и меры качества данного правила. Неопределенному атрибуту # соответствует значение 0,5, а при точном соответствии атрибута ему присваивается степень 1,0. Для нормировки полученное значение делится на длину входного вектора. Поскольку первый классификатор для данного входного вектора дает два точных соответствия и 4 неопределенных атрибута, общая степень его соответствия входному вектору составляет ((4*0,5+2*1)*0,6)=0,4. Для второго классификатора тоже имеется 2 точных соответствия и 4 неопределенных атрибута, поэтому его степень соответствия составляет 0,33. В нашем примере по принципу конкуренции побеждает классификатор с максимальной степенью соответствия, но в более сложных задачах желательно учитывать некоторый порог.

Таким образом, победило первое правило, в соответствии с которым предъявленный образ относится к классу А1. Поскольку это действие корректно, мера качества первого правила увеличивается и принимает новое значение, приближенное к 1. Если бы результат выполнения этого правила оказался некорректным, его мера качества была бы уменьшена.

После вычисления меры качества правил-кандидатов в алгоритме обучения применяются генетические операторы для создания следующего поколения правил.

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

(###21#) 1 s=0,6,

(##3##5) 0 s=0,5,

получим потомки

(##3#1#) 0 s=0,53,

(###2#5) 1 s=0,57.

Мера качества каждого потомка - это взвешенная функция показателей качества их родителей. Весовые коэффициенты определяются местоположением точки скрещивания. Первый потомок получил 1/3 информации от классификатора с мерой качества 0,6 и 2/3 - от классификатора с мерой качества 0,5. Поэтому его мера качества составляет (1/3*0,6)+(2/3*0,5)=0,53. С помощью аналогичных рассуждений выясним, что мера качества второго потомка равна 0,57. Результат выполнения правила (значение 0 или 1) определяется соответствием большинства атрибутов. В типичных системах классификации эти два новых правила, наряду с их родителями, входят в набор классификаторов, с которыми работает система на следующем этапе.

Рассмотренный пример достаточно прост и призван лишь проиллюстрировать работу основных компонентов системы классификации.

3.3.2 Описание программной реализации

Программа «Система классификации» демонстрирует работу системы вывода подобной системе, описанной в разделе 3.2.1. Интерфейс программы позволяет задавать правила для четырех классов. Для каждого класса может быть задано несколько правил. Объект описывается шестью атрибутами, каждый из которых может принимать значение от 1 до 5 или произвольное.

Основные данные программы представлены следующим образом:

1 структура rule, для хранения правила из набора правил для обучения. Членами структуры являются:

1) num типа byte - номер правила;

2) class_label типа byte- класс, к которму относится правило;

3) rule_cond_arr - массив элементов типа byte для хранения условия (атрибутов) правила.

2 rule_list типа ArrayList - список правил-учителей;

3 структура kandidat для хранения кандидата-классификатора, членами которой являются:

1) kand_cond_arr - массив элементов типа byte для хранения условий (атрибутов) классификатора;

2) class_vector - массив элементов типа byte, в котором хранится вектор классов, которым соответствует данный кандидат;

4 kandidat_list типа ArrayList - список кандидатов-классификаторов;

5 rating_arr - массив элементо типа double для хранения рейтингов кандидатов;

6 quality_of_conform - массив элементов типа double для хранения степени соответствия кандидатов;

7 cros_pos типа int - позиция скрещивания;

8 test_vector - массив элементов типа byte - вектор для классификации входного сообщения.

В начале работы с программой пользователь должен задать набор правил, которые будут выступать в роли учителей при обучении системы классификации, правило записывается в список rule_list. При этом введенная пользователем строка преобразуется в массив типа byte. Если символ строки представляет цифру от 1 до 5, то это атрибут правила, а цифра 7 используется для представления атрибута правила, который может иметь произвольное значение. Полученный массив записывается в поле rule_cond_arr структуры rule.

После задания правил нужно произвести инициализацию, используя метод Next класса Random, каждому кандидату присваивается рейтинг 0.1. Затем сгенерированный кандидат проверяется на соответствие какому-либо обучающему правилу. Порядок определения соответствия описан ниже. За каждое найденное соответствие рейтинг кандидата увеличивается на 0.025. Сгенерированная исходная популяция кандидатов выводится в поле вывода результатов работы программы.

Затем пользователь начинает ввод сообщений для обучения системы классификации. После ввода пользователем сообщения и нажатия на кнопку «Ввод» полученное сообщение преобразуется в массив message_arr типа byte.

Полученное сообщение классифицируется по таблице правил. При этом сравниваются соответствующие позиции поля rule_cond_arr очередного правила и массива message_arr. Если по всем позициям обнаружено соответствие, то в позицию массива test_vector, соответствующую классу, который представляет очередное правило, записывается единица. Иначе туда записывается ноль.

Затем все кандидаты проверяются на соответствие входному сообщению. При этом сравниваются соответствующие позиции поля kand_cond_arr очередного кандидата и массива message_arr. Если очередной кандидат соответствует входному сообщению, то вычисляется степень его соответствия.

Для кандидатов, для которых установлено соответствие входному сообщению, проверяется корректность их действия. При этом сравниваются соответствующие позиции поля class_vector кандидата и массива test_vector. Если действие правила-кандидата корректно, то его рейтинг увеличивается на величину равную разности между единицей и рейтингом кандидата, умноженной на 0.1. В противном случае рейтинг кандидата уменьшается на эту величину.

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

3.4 Игра «Искусственная жизнь»

3.4.1 Теоретические сведения

Игра «Жизнь», которую можно эффективно визуализировать на компьютере, имеет очень простое описание. Впервые она была предложена математиком Джоном Хортоном Конвеем (John Horton Conway) и получила широкую популярность благодаря ее описанию в журнале Scientific American в 1970-1971 годах. Игра «Жизнь» - это простой пример модели вычислений, получившей название клеточных автоматов (cellular automata). Клеточный автомат - это семейство простых конечных автоматов, демонстрирующее интересное эмерджентное поведение при взаимодействии элементов популяции.

Понятие конечного автомата включает следующие элементы:

1 Множество I, называемое входным алфавитом;

2 Множество S возможных состояний автомата;

3 Известное начальное состояние s0;

4 Функция N: SxIS, определяющая следующее состояние для каждой упорядоченной пары состояние-вход.

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

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

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

...