close

Вход

Забыли?

вход по аккаунту

?

7009.Интеллектуальные системы и технологии.

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ
Пальмов С. В.
Интеллектуальные системы и технологии
Методические указания к лабораторным работам
Самара - 2014
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Федеральное агентство связи
Федеральное государственное образовательное бюджетное
учреждение высшего профессионального образования
Поволжский государственный университет
телекоммуникаций и информатики
Кафедра «Информационные системы и технологии»
Пальмов С.В.
ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
И ТЕХНОЛОГИИ
методические указания
к лабораторным работам по дисциплине
для студентов очной формы обучения направления
«Информационные системы и технологии»
Самара, ИУНЛ ПГУТИ, 2014
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пальмов С.В. Методические указания к лабораторным работам по дисциплине «Интеллектуальные системы и технологии» для студентов очной формы
обучения направления «Информационные системы и технологии».– Самара:
ПГУТИ, 2014. – 119 с., ил.
Методические указания предназначены для студентов очного отделения направления09.03.02 (Информационные системы и технологии) по дисциплине
«Интеллектуальные системы и технологии». Лабораторный цикл включает в
себя двенадцать лабораторных работ, выполнение которых поможет студентам
изучить основные возможности интеллектуальных информационных систем.
Методические указания подготовлены на кафедре «Информационные системы и технологии».
Методические указания рекомендованы к изданию
методическим Советом ПГУТИ (заседание № 12 от
11.11.2014)
© ФГОБУ ВПО ПГУТИ
© ПАЛЬМОВ С.В. 2014
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Оглавление
ЛАБОРАТОРНАЯ РАБОТА №1. ЗНАКОМСТВО С СИСТЕМОЙ
WIZWHY …………………………………………………………………………..5
ЛАБОРАТОРНАЯ РАБОТА №2. ПРОВЕРКА АНАЛИТИЧЕСКИХ
ВОЗМОЖНОСТЕЙ СИСТЕМЫ WIZWHY…………………………………..25
ЛАБОРАТОРНАЯ РАБОТА №3. ДЕРЕВЬЯ РЕШЕНИЙ…………………..29
ЛАБОРАТОРНАЯ РАБОТА №4. АССОЦИАТИВНЫЕ ПРАВИЛА ………34
ЛАБОРАТОРНАЯ РАБОТА №5. КЛАСТЕРИЗАЦИЯ
(САМООРГАНИЗУЮЩАЯСЯ КАРТА КОХОНЕНА)………………….. 37
ЛАБОРАТОРНАЯ РАБОТА №6. НЕЙРОННЫЕ СЕТИ………………… 41
ЛАБОРАТОРНАЯ РАБОТА №7. АВТОКОРРЕЛЯЦИЯ. КОРРЕЛЯЦИЯ.
ФАКТОРНЫЙ АНАЛИЗ………………………………………………………..45
ЛАБОРАТОРНАЯ РАБОТА №8. ДУБЛИКАТЫ И ПРОТИВОРЕЧИЯ.
ТРАНСФОРМАЦИЯ ДАННЫХ……..………………………………………..56
ЛАБОРАТОРНАЯ РАБОТА №9. ВЫРАБОТКА РЕКОМЕНДАЦИЙ….. 60
ЛАБОРАТОРНАЯ РАБОТА №10. ГЕНЕТИЧЕСКОЕ
ПРОГРАММИРОВАНИЕ……………………………………………………….70
ЛАБОРАТОРНАЯ РАБОТА №11. ИГРА «ЖИЗНЬ»
………………….93
ЛАБОРАТОРНАЯ РАБОТА №12. ПОСТРОЕНИЕ ГРАФА ЭКСПЕРТНОЙ
СИСТЕМЫ……………………………………………………………………….96
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лабораторная работа №1. Знакомство с системой WizWhy
Цель работы: Ознакомиться с аналитической системой WizWhy
Введение
Среди систем анализа данных, относящих себя к области Data Mining, видное место занимают системы для поиска if-then правил. С помощью таких систем решаются задачи прогнозирования, классификации, распознавания образов,
сегментации БД, извлечения из данных "скрытых" знаний, интерпретации данных, установления ассоциаций в БД и др. Методы поиска if-then правил предъявляют минимальные требования к типу данных и применимы для обработки
разнородной информации. Их результаты прозрачны для восприятия.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи ПО WizWhy.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
Изучить по лекциям особенности работы алгоритмов поиска ассоциативных
правил.
Порядок выполнения лабораторной работы
Задание №1. Обзор системы WizWhy
Загрузка и управление данными.
Первое, что нужно сделать при работе с WizWhy, это загрузить анализируемый файл данных. Здесь имеется несколько возможностей:
- Вы можете подготавливать и читать файлы ASCII.
- Вы можете напрямую работать с файлами dBase(*.dbf), MSAccess
(*.mdb), Oracle и таблицами MSSQL.
- Вы можете воспринимать наборы данных посредством ODBC (Open Database Connectivity).
Для начала работы с процедурой загрузки следует, прежде всего, обратиться
к закладке «Basic Data» в окне диалога с именем текущего проекта (рис.1).
Здесь в поле «Open Data of Type» нужно указать тип загружаемых данных.
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис.1. Начало работы с системой WizWhy
Для примера возьмѐм таблицу с данными по ультразвуковой диагностике
почек в текстовом формате ASCII (разделителями колонок является знак табуляции, в первой строке таблицы данных записаны имена переменных). Укажем
требуемый тип данных и в появившемся окне диалога выберем файл USR.txt –
на экране выдаѐтся окно диалога системы WizWhy для редактирования и преобразования текстовых файлов (рис.2).
В поле Record Type (тип записи) устанавливаем переключатель в положение
Delimited (данные с разделителем) и ставим флажок в позиции First record for
fields names, говорящий о том, что имена переменных располагаются в первой
строке таблицы данных. В поле Field Delimiters (разделитель) ставим флажок в
позиции Tab (знак табуляции).
Нажимаем кнопку Parse, после чего система производит автоматический
грамматический разбор данных. Просматриваем результаты этого разбора и
при необходимости вносим коррективы – в поле Column (field) предоставляются возможности для изменения имѐн и типов переменных, а также отказа от
импорта каких-либо колонок. Нажимаем ОК. Система импортирует данные для
дальнейшей обработки, что отражается в диалоговом окне для управления данными Basic Data (рис.3).
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис.2. Диалоговое окно для чтения данных в текстовом формате
В поле Data Source указываются местоположение и имя файла, из которого
были импортированы данные. Кнопка View Data предназначена для вызова окна для просмотра загруженных данных (в нѐм демонстрируются 100 первых
строк таблицы) данных. В поле Field Grid отображаются имена и типы введѐнных переменных и предоставляются возможности проведения следующих операций:
- Назначение целевой, или так называемой зависимой (dependent) переменной. Это переменная, значения которой будут связываться с помощью ifthen-правил со значениями так называемых независимых (independent) переменных. В нашем случае такой целевой переменной является Diagnosis –
выставляем флажок в соответствующей позиции колонки Dependent Variable.
- Модификация переменных. В колонке Field Name можно редактировать
имена переменных. Для этого нужно щѐлкнуть на соответствующей позиции и ввести новое имя. Кроме этого, в позициях колонки Field Type можно
изменять тип переменной. Например, заменить тип Category (категориальный) на Number (количественный) или Date (дата) в формате День-МесяцГод (Год-Месяц-День) и т.п. Здесь заметим, что в зависимости от выбранного типа данных в дальнейшем к переменной применяются различные процедуры обработки.
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 3. Окно диалога для управления данными
В поле Data Source указываются местоположение и имя файла, из которого
были импортированы данные. Кнопка View Data предназначена для вызова окна для просмотра загруженных данных (в нѐм демонстрируются 100 первых
строк таблицы) данных. В поле Field Grid отображаются имена и типы введѐнных переменных и предоставляются возможности проведения следующих операций:
- Назначение целевой, или так называемой зависимой (dependent) переменной. Это переменная, значения которой будут связываться с помощью ifthen-правил со значениями так называемых независимых (independent) переменных. В нашем случае такой целевой переменной является Diagnosis –
выставляем флажок в соответствующей позиции колонки Dependent Variable.
- Модификация переменных. В колонке Field Name можно редактировать
имена переменных. Для этого нужно щѐлкнуть на соответствующей позиции и ввести новое имя. Кроме этого, в позициях колонки Field Type можно
изменять тип переменной. Например, заменить тип Category (категориальный) на Number (количественный) или Date (дата) в формате День-МесяцГод (Год-Месяц-День) и т.п. Здесь заметим, что в зависимости от выбранного типа данных в дальнейшем к переменной применяются различные процедуры обработки.
В системе WizWhy предусмотрен также случай, когда пропуски в таблице
данных (пустые ячейки) представляют собой самостоятельные информативные
события. Для учѐта подобных пропусков в значениях какой-либо переменной
ставится флажок против неѐ в колонке Analyze if Empty. В свою очередь, если
имеется необходимость исключить переменную из анализа, нужно выставить
флажок в колонке Ignore Field.
В нашем примере две переменные имеют категориальный (Category) формат
– целевой признак Diagnosis, признак Sex (пол пациента) и признак LR (левая
или правая почка.) Остальные переменные (Age (возраст), Length (длина поч8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ки), Width (ширина почки), Thickness (толщина почки), Thickpar (толщина паренхемы), Speed (средняя скорость кровотока), Index (индекс резистентности) и
Accel (ускорение артериального потока в систолу)) - количественные (Number).
Задание параметров процедуры поиска правил
В системе WizWhy целевой признак разделяет всѐ множество объектов на
две части. Это делается следующим образом.
Если целевая переменная является категориальной, WizWhy просматривает
все объекты (записи) и отбирает те из них, для которых целевая переменная
имеет выбранное значение. Отобранные таким образом объекты составляют
первую группу. Правила, характерные для данной группы, называются if-thenправила. Оставшиеся объекты составляют вторую группу, и для этой группы
характерные правила обозначаются как if-they-NOT-правила.
Если целевой признак является количественным, пользователь должен указать область значений этого признака. Правила if-then будут определяться для
этой указанной области. В свою очередь, if-they-NOT-правила будут описывать
объекты, не попавшие в выделенную область.
В рассматриваемом нами практическом примере целевой признак категориальный. Он принимает три значения: 1 – в классе «здоровая почка», 2 – в классе
«множественные кисты» и 3 – в классе «гидронефроз». Будем искать в данных
if-then-правила для объектов с диагнозом «множественные кисты». Для этого с
помощью закладки Rule Parameters (параметры правил) войдѐм в соответствующее окно диалога и в поле Predicted Value выставим значение «2».
Примечание: Если при попытке выполните вышеуказанный пункт задания
программа WizWhy «вылетает», то следует сменить тип переменной «Diagnosis» с категориального на количественный и установить следующие
значения полей «More than» и «Less or equal than» (см. рис. 4).
Последующие действия выполняются вне зависимости от того, «вылетала»
программа или нет.
После задания области значений целевой переменной или, как в нашем случае, еѐ одного значения система WizWhy читает данные и вычисляет простые
статистики, которые могут быть использованы в дальнейшем анализе. Так, например, справа от поля Predicted Value система выводит значение частоты, с
которой в анализируемых данных встречается значение Diagnosis = 2. Как указывают авторы, чтение больших наборов, данных способно занимать много
времени. Пользователь может прекратить процесс чтения, нажав кнопку Cancel
на специальной панели. В этом случае дальнейшему исследованию подвергается только та информация, которая успела прочитаться. Но при желании процесс
поиска данных можно повторить.
Следующим шагом является задание собственно параметров правил, которые будут искаться в прочитанных данных. Сюда, прежде всего, относят Mini9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
mum probability of if-then rules (минимальная вероятность if-then-правил) и Minimum probability of if-then-NOT rules (минимальная вероятность if-then-NOTправил). Эти параметры есть ни что иное, как точность правила. Поставим в
соответствующих полях окна диалога одинаковые значения указанных вероятностей 80% процентов. Это означает, что системеWizWhy формулируется требование обнаружить правила, которые будут ошибаться не более чем в 20%
случаев (имеются в виду ошибки на анализируемой выборке).
В принципе, можно задавать любые значения минимальных вероятностей от
0 до 100%. Но следует хорошо представлять, что, задав слишком низкий уровень точности, мы получим большое количество правил, среди которых будет
много малоинформативных компонентов. В свою очередь, выставив требование
100%, мы, скорее всего, не получим вообще ничего.
Рис. 4.
Ещѐ одним важным параметром служит Maximum number of conditions in a
rule (максимальное число условий в правиле). Это максимальное количество
элементарных логических событий в одном правиле. Хотя авторы ничего не говорят о предельном значении данного параметра, установлено, что оно равно 6.
Следующим параметром, который необходимо задать для работы процедуры поиска правил, является Minimum number of cases in a rule (минимальное
число объектов в правиле). Выставим здесь значение 10, обозначив тем самым
наше желание обнаружить в данных правила, которые распространяются не
менее чем на 10 объектов. Нижний предел составляет 4 объекта.
Окно Rule Report
Настройки этого окна (см. рис.5) касаются способов выдачи результатов.
Во-первых, нужно ввести параметр Maximum number of rules to be displayed
(максимальное количество отображаемых правил). Этот параметр не влияет на
работу процедуры поиска правил. Он предназначен только для ограничения количества правил, выдаваемых в отчѐт (Rule Report). Далее следует указать способ сортировки правил в отчѐте (по уровню значимости – Significance level, по
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
точности – Probability, по количеству объектов – Number of cases). В поле
Present examples where (представить примеры) можно выразить желание посмотреть примеры работы выявляемых правил. Если поставить флажок в позиции Rule in effect, то система будет формировать в отчѐте для каждого правила
список номеров объектов, для которых правило не ошибается. Длина списка
ограничивается заданным числом. Соответственно, флажок в позиции Rule in
not effect запрашивает у системы выдачу списка номеров объектов, на которых
какое-либо правило работает с ошибкой.
Рис.5
Работа с другими окнами диалога
Окно диалога Data Format предназначено для задания и корректировки
формата информации, с которой работает WizWhy (рис. 6). Прежде всего, сюда
относится формат данных. В поле number and Currency Format имеется возможность задавать количество цифр и виды разделителей в числовых и денежных
данных, а в поле Data Format выбирать формат для записи дат.
Кроме того, в нижней части окна диалога предусмотрены параметры, выбор
которых определяет место выдачи отчѐта о результатах работы системы (на
принтер, на экран, в текстовый файл и т.д.). В поле Subheading заносится подзаголовок отчѐта. Нажатием кнопки Font в правом нижнем углу вызывается окно
диалога для выбора используемых шрифтов.
Крайнее диалоговое окно – Prediction Input – предназначено для ввода, просмотра и коррекции внешних данных, на которых требуется проверить действие найденных правил. Оно изображено на рис.7. Работа с этим окном аналогична работе с уже рассмотренным диалоговым окном Basic Data.
В окне Error Costs (стоимость ошибок) требуется ввести соответствующие
значения по отдельности для двух видов ошибок: пропуска объектов (Cost of
miss) и ложной тревоги (Cost of false alarm) (рис. 8).
По умолчанию эти значения равны «1». Учѐт различной стоимости указанных ошибок может оказаться весьма ценным при решении практических задач.
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 6
Результаты работы системы
После внесения необходимой информации в рассмотренные выше окна
диалога можно приступить к поиску правил в загруженных данных. Для этого
нужно нажать кнопку Issue Rules (выдача правил) – система WizWhy выдаѐт
три отчѐта:
- Отчѐт о правилах (Rule report), в котором перечисляются обнаруженные
правила с указанием их характеристик.
- Отчѐт о трендах (Trend report), в котором представлены результаты сегментации отдельных признаков.
- Отчѐт о неожиданных правилах.
Рассмотрим указанные отчѐты более подробно.
Рис. 7
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 8
Отчѐт о правилах
Отчѐт о правилах размещѐн в трѐх окнах (рис. 9):
- Левое окно – список правил (Rule List).
- Правое верхнее окно – содержание записи в деталях (Record Details Grid).
- Правое нижнее окно – индекс признака (Field Index).
Рис. 9
Список правил
Список правил предваряется информацией о заданных параметрах поиска.
Здесь на примере данных по ультразвуковой диагностике почек, как видим, говорится, что общее число обработанных записей (объектов) составляет 74, минимальная вероятность правил if-then и if-then-NOT равны по 0.8, минимальное
количество объектов для правил – 10. Затем подтверждается, что правила находятся для переменной Diagnosis, конкретно для значения этой переменной, равного 2 (если в пункте 2 программа у вас «вылетала», то в строке Predicted Value
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
будет указано: between 1,00 and 2,00). Также указывается, что стоимость ошибок в виде пропусков и ложных тревог составляет 1, а средняя вероятность (априорная вероятность) прогнозируемого значения переменной равна 0.5
Далее система выдаѐт следующий блок общей информации об обнаруженных правилах:
ANALYSIS OF THE RULES EXPLANATORY POWER
Decision point: Predict between 1,00 and 2,00 when conclusive probability is more
than 0,572
Number of misses: 3
Number of false alarms: 4
Total number of errors: 7
Total cost of errors: 7
Success rate when predicting between 1,00 and 2,00 : 0,889
Success rate when predicting NOT between 1,00 and 2,00 : 0,903
Number of records with no relevant rules : 7
Average cost (per record): 0,104
Expected average cost (per record) : 0,500
Improvement Factor: 4,786
Из приведѐнного блока можно почерпнуть сведения о значениях некоторых
служебных параметров - Decision point (точка решения), Average cost (средние
потери (на запись)), Expected average cost (ожидаемые средние потери) и Improvement Factor (выигрыш), представляющий собой отношение ожидаемых
средних потерь к реальным потерям на запись.
Точка решения – когда WizWhy формирует прогноз, то вычисляется вероятность того, что значение зависимой переменной в анализируемой записи
равно «1» (допустим «1» – это спрогнозированное значение зависимой переменной). Эта вероятность называется итоговой (conclusive). Если значение
итоговой вероятности больше значения точки решения, то прогнозируемое
значении = 1, а если меньше, то не равно 1.
Средние потери на запись – общая сумма ошибок, поделѐнная на количество записей в исследуемом массиве данных.
Ожидаемые средние потери есть результат формирования прогноза только на основании частоты появления прогнозируемого значения, стоимости
пропуска объекта, стоимости ложной тревоги. Другими словами – это ожидаемые средние потери при условии, что неизвестно ни одного правила. Например, пусть частота появления прогнозируемого значения = 15%, стоимость пропуска объекта = 2, а стоимость ложной тревоги = 1. В этом случае, если в анализируемых записях не найдено ни одного правила, то WizWhy
формирует следующий прогноз: «прогнозируемое значение зависимой переменной не встречается ни в одной записи из исследуемого набора». В таком случае
(для прогноза такого вида) средние потери на запись называются ожидаемы14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ми средними потерями. Для данного примера они будут равны 0.3 (15% (или,
другим словами, 0.15) умножить на 2 и умножить на 1 = 0.3).
Кроме того, в блоке содержатся сведения о прогнозирующей способности
все совокупности обнаруженных правил – количество пропусков при прогнозировании (Number of misses), число ложных тревог (Number of false alarms), общее количество ошибок (Total number of errors), общие потери (Total cost of errors), вероятность успешного прогнозирования для класса 2 (Success rate when
predicting 2), вероятность успешного прогнозирования альтернативного класса
(Success rate when predicting NOT 2) и количество объектов, не охваченных выделенными правилами (Number of records with no relevant rules).
Список правил состоит из правил, упорядоченных по заданному критерию.
В данных по ультразвуковой диагностике почек при установленных параметрах
система WizWhy обнаружила 19 правил. Рассмотрим (для примера) правило №
5:
5)
IfLRisR
andSpeedis16,30 ... 41,50 (average = 25,44 )
andIndex is 0,70 ... 0,80 (average = 0,72 )
Then
Diagnosis is not between1,00 and 2,00
Rule's probability: 1,000
The rule exists in 10 records.
Significance Level: Error probability < 0,001
Positive Examples (records' serial numbers):
3, 61, 63, 64, 65, 66, 67, 72, 73, 74
Это правило представляет собой конъюнкцию трѐх элементарных высказываний. Первое - LR is R - говорит о том, что правило относится только к правой почке. Второе - Speed is 16,30 ... 41,50 – определяет диапазон значений для
средней скорости кровотока, и третье - Index is 0,70 ... 0,80 – описывает интервал значений индекса резистентности. Высказывание Diagnosis is not
between1,00and2,00 (или Diagnosis is not 2 – если у вас программа не «вылетала») означает, что правило характерно для объектов, не имеющих диагноз
«множественные кисты».
Запись Rule's probability: 1,000 означает, что точность правила в данном
случае равна 1. Следующая запись - The rule exists in 10 records– характеризует
объѐм множества объектов, для которых справедливо рассматриваемое правило, а другая запись - Significance Level: Error probability <
0,001 – касается
статистической оценки уровня значимости полученного правила (как видим,
доверие к правилу превышает 90%). Последняя запись - Positive Examples
(records' serial numbers) – означает «положительные» примеры, которые затем
представлены как номера записей (объектов) в наборе данных.
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Система WizWhy предоставляет возможность визуализации полученного
правила. Для этого нужно щѐлкнуть на правиле левой кнопкой мыши и затем с
помощью правой кнопки вызвать контекстное меню, в котором выбрать диаграмму правила Rule Chart (рис. 10).
Рис.10. Диаграмма выделенного правила № 5
Эта диаграмма иллюстрирует отдельные компоненты правила и даѐт графическое отображение совокупного взаимодействия переменных.
Содержание записи в деталях
Окно «Содержание записи в деталях» позволяет просмотреть значение признаков для каждого объекта. Для этого требуется ввести номер объекта в поле
Record и нажать клавишу Enter. Пример для объекта № 25 приведѐн на рис. 11.
Другая возможность состоит в том, что если дважды щѐлкнуть левой кнопкой мыши на номере объекта в списке правил, который там приведѐн в качестве
положительного или отрицательного примера, соответствующие значения признаков отобразятся в рассматриваемом окне. При этом целевая переменная будет отмечена специальным значком красного цвета, а все остальные – значками
зелѐного цвета. Кроме того, на значках, расположенных сразу слева от названия
признаков, указываются типы данных признаков.
Рис. 11
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Индекс признака
В окне «Индекс признака», расположенным в правом нижнем углу, отображаются порядковые номера правил, в которых появляются те или иные признаки (рис. 12).
Рис. 12.
Можно просмотреть всѐ окно, используя прокрутку. Также в системе предусмотрена другая возможность – если в списке правил дважды щѐлкнуть на каком-либо признаке в любом из правил, то этот признак будет автоматически
выделен в окне «Индекс признака». По представляемой информации удобно
выносить суждения о полезности признаков (о коэффициенте использования
признаков) для классификации данных и прогнозирования. В свою очередь, если дважды щѐлкнуть в окне «Индекс признака» по любому номеру правила, то
это правило моментально будет выделено в списке правил.
Распечатка и экспорт правил
Для распечатки правил или их экспорта в другой файл требуется нажать соответствующую кнопку печати на главном окне WizWhy – на экране появится
специальное диалоговое окно Print Rules (рис. 13).
Рис. 13
В поле Print to указывается адрес, по которому направляется результирующая информация. В поле Print/Export range указывается диапазон порядковых
номеров правил, которые должны быть распечатаны или экспортированы. В
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
нижней части окна диалога проставляются по необходимости флажки для распечатки или экспорта введения к списку правил Print Introduction и содержимого окна «Индекс признака». Кроме того, в поле Heading моно ввести заголовок
для результирующей информации.
Отчѐт о трендах
Отчѐт о трендах представляет результаты сегментации отдельных признаков. Окно данного отчѐта разделено на три области (рис. 14).
В области, расположенной в левом верхнем углу, мы задаѐм анализируемый
признак (Field to be analyzed). Здесь можно не только выбирать требуемый признак, но и сортировать признаки по какому-либо критерию (в алфавитном порядке, по номеру поля, по информативности).
Другие две области предназначены для отражения отношений между значениями признака и зависимой переменной. В верхней правой области окна отчѐта приводятся статистические характеристики сегментов выделенного признака. В нижней области отчѐта приводится графическая иллюстрация информативности каждого сегмента. На графике по горизонтальной оси располагаются
сегменты, на которые выбранный признак автоматически разбивается системой
WizWhy. По вертикальной оси откладывается отношение количества объектов
класса if-then к общему количеству объектов, попадающих в сегмент. Таким
образом, высота столбиков на графике отражает информативность сегментов.
Если столбик выше синей горизонтальной черты, значит, в данный сегмент чаще попадают объекты класса if-then, а если ниже горизонтальной черты – класса if-then-NOT. В свою очередь, ширина столбиков пропорциональна количеству объектов, относящихся к данному сегменту.
Отчѐт о неожиданных правилах
В системе WixWhy введено представление о так называемых неожиданных
правилах (unexpected rules). Под неожиданными понимаются правила в виде
конъюнкции двух и более простых высказываний, комбинация которых даѐт
точность и полноту прогноза выше, чем это можно было бы ожидать при независимости простых высказываний. Это представление, по-видимому, имеет
цель дополнительно заинтриговать конечного пользователя возможностью открывать в данных нетривиальные закономерности.
В нашем случае система не обнаружила таких неожиданных правил. Однако
можно попытаться это сделать, если мы изменим задание на поиск правил. Например, уменьшим минимальную вероятность if-then- и if-then-NOT-правил с
80 до 70% в окне Rule Parameters. Проделайте указанную операцию и нажмите
кнопку Issue Rules – теперь система обнаружит в данных по ультразвуковой диагностике 38 правил, и среди них окажется 4 неожиданных, отчѐт о которых
выдаѐтся в специальном окне (рис. 15). Окно отчѐта о неожиданных правилах
разделено на три секции. В левой верхней секции отображается в стандартной
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
форме найденное неожиданное правило. Правая верхняя секция содержит информацию об элементах, из которых составлено неожиданное правило. И наконец, нижняя секция предназначена для сортировки неожиданных правил и графического представления результатов.
Рис. 14
Так, в нашем случае первое неожиданное правило, изображѐнное на рис. 15,
расшифровывается следующим образом: если (пол женский) и (ширина почки в
интервале от 61 до 75) и (ускорение кровотока от 148 до 275), то диагноз (множественные кисты). Данное правило вместе с рассчитанными характеристиками приведено ниже. Здесь по сравнению с ранее рассмотренными характеристиками выдаются две новые – уровень неожиданности (Level of Unlikelihood) и
ожидавшаяся вероятность правила (Expected rule probability) Как видно, за счѐт
взаимосвязи элементов правила точность целого правила составила 0,999 и оказалась значительно выше ожидавшейся (0,81).
Рис. 15
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Unexpected Rule # 1 (out of 4)
Level of Unlikelihood :0,999
1)
If Sex is F
and Width is 61,00 ... 77,00 (average = 67,30 )
and Accel is 148,00 ... 275,00 (average = 216,10 )
Then
Diagnosis is between1,00 and 2,00
Rule's probability: 1,000
The rule exists in 10 records.
Significance Level: Error probability < 0,001
Expected rule probability :0,810
Actual minus Expected probability: 0,190
В правой верхней секции приводится статистический разбор компонентов,
из которых состоит неожиданное правило. Оно состоит из двух частей (табл. 1)
Базисные правила (Basic Rules) представляют собой комбинации простых
событий, входящих в неожиданное правило.
Табл.1
Basic Rules
1)If Width is 59,00 ... 101,00 (average =
69,00 )
and Accel is 148,00 ...
279,00 (average = 214,11 )
Then
Diagnosis is between 1,00 and
2,00
Rule's probability: 0,778
The rule exists in 14 records.
Significance Level: Error probability < 0,01
5)
Basic Trends
If Sex is F
Then
Diagnosis is between 1,00 and
2,00
Trend's probability : 0,595
The trend exists in 25 records.
6)
If Width is 59,00 ... 101,00
Then
Diagnosis is between 1,00 and
2,00
2)If Sex is Fand Accel is 148,00 ...
275,00 (average = 222,14 )
Then
Diagnosis is between 1,00 and
2,00
Rule's probability: 0,810
The rule exists in 17 records.
Significance Level: Error probability < 0,001
3)
Trend's probability : 0,556
The trend exists in 20 records.
If Sex is F
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
and Width is 60,00 ... 85,00 (average = 68,29 )
Then
Diagnosis is between 1,00 and
2,00
Rule's probability: 0,706
The rule exists in 12 records.
Significance Level: Error probability <
0,1
4) If Accel is 148,00 ... 279,00 (average
= 217,18 )
Then
Diagnosis is between 1,00 and
2,00
Rule's probability: 0,706
The rule exists in 24 records.
Significance Level: Error
probability < 0,01
Базисные тренды (Basic Trends) – это статистический разбор сегментов анализируемых переменных, составляющих собственно логические события.
Как видим из таблицы, все компоненты неожиданного правила по отдельности имеют точность существенно ниже 1 – самое высокое значение точности
наблюдается у базисного правила №2.
Нижняя секция отчѐта о неожиданных правилах разделена на две части. В
левой части располагаются элементы управления для сортировки этих правил.
По умолчанию правила проранжированы по величине разности между реальной
и ожидаемой точностями правил. Если установить переключатель в поле Field и
выбрать из списка какой-либо признак, то будут отображаться только те неожиданные правила, в которых встречается указанный признак. В свою очередь, в поле Type можно выбрать один из трѐх типов фильтров правил: All (все
правила), if-then-правила и if-then-NOT.
В правой части нижней секции отчѐта о неожиданных правилах даѐтся графическое представление характеристик правил и их составляющих. Первый
слева столбик относится к найденному неожиданному правилу – его высота
равна точности, а ширина пропорциональна количеству покрываемых объектов.
Следующий столбик отображает ожидавшиеся характеристики правила, а остальные столбики соответствуют описанным выше базисным правилам и трендам. Если щѐлкнуть левой кнопкой мыши по какому-либо столбику, то система
WizWhy автоматически изменит содержание верхних окон отчѐта о неожиданных правилах. Можно также щѐлкнуть правой кнопкой мыши – появляется
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
контекстное меню, в котором можно выбрать иллюстрацию в виде диаграммы
правила (Rule chart).
Прогнозирование на основе полученных правил
В системе WizWhy предусмотрены две возможности использования обнаруженных правил для предсказания значений целевого показателя на новом материале.
Первая возможность заключается в ручном вводе значений признаков и обработке нового одиночного объекта (записи). Она реализуется следующим образом.
Нажмите кнопку Predict online – на экран выдаѐтся диалоговое окно для
ручного ввода значений признаков (рис. 16).
Рис. 16
После заполнения окошек предложенной таблицы (здесь возможны пропуски) нажмите кнопку Issue Report – система создаѐт отчѐт, в котором подробно
описывает как конечный результат предсказания, так и характеристики каждого
отдельного правила, использованных для получения прогноза. Пример отчѐта
представлен ниже:
WIZWHY PREDICTION REPORT
File Name: G:\WIZWHY 3.01 DEMO\USR.txt
Condition Fields:
Age =50,00
Width =60,00
Speed =15,00
Index =1,00
Accel =1,00
Dependent Variable: Diagnosis
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Subject for Prediction: Diagnosis is between1,00 and 2,00
Prediction's significance level: Error probability = 0,000
Primary Prediction's probability: 0,500
Conclusive Prediction's probability: 0,884
Prediction: between 1,00 and 2,00
Relevant rules:
1)
If Age is 46,00 ... 70,00 (average = 62,00 )
and Speed is 2,30 ... 15,40 (average = 13,17 )
Then
Diagnosis is between1,00 and 2,00
Rule's probability: 0,909
The rule exists in 10 records.
Significance Level: Error probability < 0,01
2)
If Width is 54,00 ... 87,00 (average = 64,82 )
and Speed is 2,30 ... 15,40 (average = 13,28 )
Then
Diagnosis is between1,00 and 2,00
Rule's probability: 0,909
The rule exists in 10 records.
Significance Level: Error probability < 0,01
3)
If Speed is 2,30 ... 15,40 (average = 13,28 )
Then
Diagnosis is between1,00 and 2,00
Rule's probability: 0,833
The rule exists in 10 records.
Significance Level: Error probability <
0,1
Как видим, в данном случае система выдала предсказание, что рассматриваемый объект относится к классу 2. Это решение система приняла на основании трѐх правил.
Вторая возможность использования множества правил заключается в обработке сразу большого массива новой информации. Для этого перейдите к закладке PredictionInput в окне диалога для ввода данных и в ней укажите файл, в
котором записана новая информация. Пусть это будет тот же самый файл с
обучающей выборкой USR.txt. Затем требуется задать имя файла, в который
будут записываться результаты прогнозирования. Данная операция осуществляется с помощью кнопки Print result to… И наконец, нажимается кнопка Predict to file – система производит необходимые расчѐт и сообщает, что результаты успешно записаны в указанный файл.
Итогом выполнения первого задания работы должны быть:
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Прогноз, полученный при помощи опции Predict online (ручной ввод) для
произвольной
записи.
Результаты
скопируйте
в
файл:
WizWhy_1_Фамилия.doc.
2. Прогноз, полученный при помощи опции Predict online (для большого массива файлов); используйте файл USR.txt.
Задание №2
В качестве источника данных выберите файл Stock (таблица Companies1) (в
папке «WizWhy»). Зависимая переменная – «Industry» - может принимать следующие значения:
1. 036 - Software & Programming
2. 0727 - Regional Banks
3. 1018 - Computer Services
4. 0803 - Biotechnology & Drugs
5. 0909 - Business Services
6. 0730 - S&Ls/Savings Banks
7. 0812 - Medical Equipment & Supplies
8. 0915 - Communications Services
9. 1024 - Electronic Instruments & Controls
10.0721 - Misc. Financial Services
11.1003 - Communications Equipment
12.0933 - Real Estate Operations
13.1030 - Scientific & Technical Instruments
14.0609 - Oil & Gas Operations
15.0218 - Misc. Capital Goods
16.The others.
Выберите согласно вашему варианту из вышеприведѐнного списка значение зависимой переменной. Установите следующие значения параметров:
Рис. 17
Выполните процедуру поиска правил. После этого, при помощи опции Predict online выполните прогнозирование на основе полученных правил (в качестве анализируемого набор данных выберите таблицу Companies2 из файла
Stock).
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание отчѐта (часть 2): Аналогично части 1.
Содержание отчѐта (в отдельных файлах):
1. Прогноз, полученный при помощи опции Predict online (ручной ввод) для
произвольной
записи.
Результаты
скопируйте
в
файл:
WizWhy_1_Фамилия.doc; используйте файл USR.txt.
2. Прогноз, полученный при помощи опции Predict online (для большого
массива файлов); используйте файл USR.txt.
3. Прогноз, полученный при помощи опции Predict online (ручной ввод) для
произвольной
записи.
Результаты
скопируйте
в
файл:
WizWhy_1_Фамилия.doc; используйте файл Stock.
4. Прогноз, полученный при помощи опции Predict online (для большого
массива файлов); используйте файл Stock.
Контрольные вопросы
1. Назовите форматы файлов, с которыми может работать WizWhy.
2. Дайте понятие зависимой и независимой переменной. Приведите примеры.
3. Опишите процесс задания параметров поиска правил.
4. Поясните содержимое окна Error Costs.
5. Каково максимальное число элементарных логических событий, которое
может обнаружить WizWhy в данных?
6. Поясните состав блока общей информации об обнаруженных правилах.
7. Поясните структуру правила, обнаруживаемого при помощи WizWhy.
8. Как функционирует опция Predict online?
Список литературы
1. Сайт компании WizSoft[Электронный ресурс]: руководство пользователя.
– Режим доступа:http://www.wizsoft.com/index.php/support/download-usermanuals
Лабораторная работа №2. Проверка аналитических возможностей системы
WizWhy
Цель работы: Проверить прогностические возможности аналитической системы WizWhy.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи ПО WizWhy.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Изучить по лекциям особенности работы алгоритмов поиска ассоциативных правил.
Порядок выполнения лабораторной работы
1. Создать базу данных (предметная область – любая, кроме автомобилей),
содержащую скрытые закономерности (15 шт.).
2. Попытаться выявить скрытые закономерности при помощи WizWhy.
3. Сделать выводы.
Пояснения к лабораторной работе
1. Создать базу данных, содержащую ассоциативные правила (скрытые закономерности).
ВНИМАНИЕ! При создании базы весь текст (названия полей, значения) –
на латинице. Формат - .txt.
Создание базы начинается с выбора предметной области. Допустим, Вы выбрали «Автомагазин». После этого необходимо создать для базы 15 скрытых
закономерностей (правил), которые Вы попытаетесь обнаружить при помощи
WizWhy. Закономерности представляются в формате «Если»… «то». Например,
закономерность может выглядеть так: «Если цвет машины = красный то цена =
$20000».
Итак, вы создали первую закономерность (правило). Каким же образом поместить закономерность в базу данных? Для этого информацию из созданного
правила необходимо добавить в базу данных. Делается это следующим образом. Создаѐм пустую базу данных. Вы (для примера) выбрали автомобили:
Табл. 2
Цвет
Марка
С
пробегом
Тип Приобретение Тип дви- Цена
кузова
в кредит
гателя
Заносим в неѐ информацию из правила:
Табл.3
Цвет
красный
Марка С пробе- Тип Приобретение Тип двигом
кузова
в кредит
гателя
Цена
20000
Заполняем оставшиеся ячейки произвольной информацией. Например:
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Табл.4
Цвет
Марка С пробе- Тип Приобретение Тип дви- Цена
гом
кузова
в кредит
гателя
красный Форд
Да
Седан
Да
бензин 20000
Как было сказано выше, все надписи должны быть на латинице. Поэтому:
Табл.5
Cvet
Marka
krasny
Ford
S probegom
Da
Tip
V
Dvigatel Cena
kuzova kredit
Sedan
Da
benzin 20000
Т.о., у Вас получилась база данных состоящая (пока) из одной записи, в которой содержится скрытая закономерность «Если цвет машины = красный то
цена = $20000».
В Вашей базе 7 атрибутов (полей). Это сделано специально. Программа
WizWhy имеет следующее ограничение: она может находить закономерности
(правила), в условной части которых содержится не более шести условий, т.е.
правило вида: «Если условие1=a и условие2=b и… и условие6=f то следствие
= z» будет самым сложным, которое сможет найти система. Поэтому в Вашей
базе (ОБЯЗАТЕЛЬНОЕ УСЛОВИЕ!!!) должно быть 6 условий (или независимых переменных) и одно следствие (зависимая или целевая переменная). В
данном примере первые 6 атрибутов (полей) – независимые переменные, а последняя – зависимая.
Табл. 6
Cvet
Marka
krasny
Ford
S probegom
Da
Tip
V
Dvigatel Cena
kuzova kredit
Sedan
Da
benzin 20000
Продолжаем создавать закономерности и заполнять базу. Необходимо создать ещѐ четыре закономерности с одним условием в условной части (т.е., в
сумме будет 5). Принцип их создания аналогичен рассмотренному выше: создаѐм (и записываем) закономерность – переносим информацию из неѐ в базу данных – заполняем оставшиеся поля - создаѐм (и записываем) закономерность –
переносим информацию из неѐ в базу данных-… .
Далее, создаѐм закономерность с тремя условиями в условной части (их тоже должно быть пять штук) и с шестью условиями в условной части (пять
штук).
Таким образом, Вы создали 15 закономерностей, каждая из которых содержится в соответствующей записи базы данных. Ваша база содержит 15 уникальных записей, но этого мало. Почему? А потому, что WizWhy имеет ещѐ одно ограничение: эта система находит только те закономерности, которые встре27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
чаются в базе данных хотя бы четыре раза. Поэтому, чтобы точно выполнить
это условие скопируйте Ваши 15 записей три раза. Получим базу из 60 записей.
Ваша база готова.
Замечания
- Целевая переменная – всегда одна и та же. Выбрали целевой переменной атрибут «цена», значит для всех 15 закономерностей он и будет целевым (значения целевого атрибута, естественно, могут быть разными в разных закономерностях; например, цена = 10000, цена = 20000 и т.д.).
- Если создаѐте базу в формате .txt – отделяйте значения в одном столбце о другого табуляцией.
2. Проверить возможности системы WizWhy по обнаружению скрытых закономерностей.
Загружаем базу в WizWhy (см. лр №1). И начинаем проверять правила. Для
этого выполняем следующий набор действий:
a) Выбираем первое правило: Если цвет машины = красный то цена = $20000.
b) Настраиваем параметры поиска правил (см. лр №1). При этом задаѐм: цена =
$20000, minimum number of cases in a rule = 4, maximum number of condition in a
rule = 6.
c) Запускаем процесс поиска правил (см. практическую работу).
d) После завершения процесса поиска правил, получаем набор правил (модель), которую
можно использовать для поиска закономерностей.
e) При помощи опции predict online (см. практическую работу) пытаемся обнаружить
первую закономерность: Если цвет машины = красный то цена = $20000. Вводим значение условия и запускаем процесс поиска.
f) В результате система формирует отчѐт, содержащий различную информацию. Вас интересует строка, которая начинает со слова Prediction. Это результат поиска. Например,
для данного случая: Prediction = 20000 – закономерность обнаружена; Prediction
= No
20000 – не обнаружена.
g) Скопируйте отчѐт в отчѐт по контрольной работе.
h) Повторите пп. a – g для оставшихся закономерностей.
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Напоминаю: цель работы состоит в проверке возможностей системы. Если
какие-то из закономерностей не удалось обнаружить, то это не значит, что Вы
ошиблись. Это значит, что программа не смогла найти эту закономерность, и
вы смело копируете результаты еѐ работы в отчѐт.
Содержание отчѐта
1.
2.
3.
4.
5.
6.
Титульный лист
Цель работы
15 закономерностей в формате если… то.
15 уникальных записей из БД (скриншот).
15 отчѐтов из predict online.
Выводы по работе (сколько правил найдено, сколько нет).
Лабораторная работа №3. Деревья решений
Цель работы: Научиться использовать деревья решений для анализа данных
Введение
Определение
Деревья решений – это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный
узел, дающий решение.
Правило – логическая конструкция вида «Если… то…».
Рис.18 Фрагмент дерева решений
Области применения деревьев решений


Описание данных: позволяют хранить точное описание объектов в компактной форме.
Классификация: деревья решений хорошо справляются с задачами классификации (отнесения объектов к одному из заранее известных классов);
целевая переменная должна быть дискретной.
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Регрессия: если целевая переменная имеет непрерывные значения, деревья решений позволяют установить зависимость целевой переменной от
независимых (входных) переменных.
Общие принципы построения деревьев решений
Пусть задано некоторое обучающее множество T, содержащее объекты
(примеры), каждый из которых характеризуется m атрибутами, причѐм один из
них указывает на принадлежность объекта к определѐнному классу.
Пусть через {C1, C2, ... Ck} обозначены классы (значения метки класса), тогда существуют 3 ситуации:
1. множество T содержит один или более примеров, относящихся к одному
классу Ck. Тогда дерево решений для Т – это лист, определяющий класс
Ck;
2. множество T не содержит ни одного примера, т.е. пустое множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из
другого множества отличного от T, скажем, из множества, ассоциированного с родителем;
3. множество T содержит примеры, относящиеся к разным классам. В этом
случае следует разбить множество T на некоторые подмножества. Для
этого выбирается один из признаков, имеющий два и более отличных
друг от друга значений O1, O2, ... On. T разбивается на подмножества T1,
T2, ... Tn, где каждое подмножество Ti содержит все примеры, имеющие
значение Oi для выбранного признака. Это процедура будет рекурсивно
продолжаться до тех пор, пока конечное множество не будет состоять из
примеров, относящихся к одному и тому же классу.
Вышеописанная процедура лежит в основе многих современных алгоритмов
построения деревьев решений, этот метод известен ещѐ под названием разделения и захвата (divide and conquer). Очевидно, что при использовании данной
методики, построение дерева решений будет происходит сверху вниз.
Поскольку все объекты были заранее отнесены к известным нам классам,
такой процесс построения дерева решений называется обучением с учителем
(supervised learning). Процесс обучения также называют индуктивным обучением или индукцией деревьев (tree induction).
На сегодняшний день существует значительное число алгоритмов, реализующих деревья решений CART, C4.5, NewId, ITrule, CHAID, CN2 и т.д. Но
наибольшее распространение и популярность получили следующие два:

CART (Classification and Regression Tree) – это алгоритм построения бинарного дерева решений. Каждый узел дерева при разбиении имеет только двух потомков. Как видно из названия алгоритма, решает задачи классификации и регрессии.
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

C4.5 – алгоритм построения дерева решений, количество потомков у узла
не ограничено. Не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации.
Большинство из известных алгоритмов являются "жадными алгоритмами".
Если один раз был выбран атрибут, и по нему было произведено разбиение на
подмножества, то алгоритм не может вернуться назад и выбрать другой атрибут, который дал бы лучшее разбиение. И поэтому на этапе построения нельзя
сказать даст ли выбранный атрибут, в конечном итоге, оптимальное разбиение.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи ПО Deductor
Academic 5.3.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
Изучить по лекциям и учебной литературе особенности построения деревьев решений и работы в ПО Deductor Academic 5.3.
Порядок выполнения лабораторной работы
Задание№1
1. Запустите Deductor.
2. Импортируйте набор данных из текстового файла «Голосование конгресса.txt» (выберите «Сценарии», нажмите «F6», выберите пункт «Text», выберите путь к файлу, остальные поля оставляйте без изменений).
3. Запустите мастер обработки (выберите в разделе «Сценарии» пункт «Текстовый файл…» и нажмите «F7»).
4. В открывшемся окне выберите пункт «Дерево решений». Нажмите «Далее».
5. В открывшемся окне обозначьте поле «Класс» как выходное, а остальные
– как входные. Нажмите «Далее».
6. На следующем этапе производится разбиение исходного множества на
обучающее и тестовое. Настройки не изменяйте. Нажмите «Далее».
7. На следующем этапе производится настройка параметров обучения дерева. Настройки не изменяйте. Нажмите «Далее».
8. На следующем этапе производится настройка способа обучения дерева.
Настройки не изменяйте. Нажмите «Далее».
9. На следующем этапе нажмите «Пуск». Когда процесс будет завершѐн,
нажмите «Далее».
10.На следующем этапе необходимо определить способы отображения полученных результатов. Отметьте пункты «Дерево решений», «Правила»,
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
«Значимость атрибутов». «Таблица сопряжѐнности» и «Что-если». Нажмите «Далее», а затем «Готово».
11.Сохраните полученные результаты.
12.Сделайте выводы об эффективности построенного дерева.
Задание №2
1. Запустите Deductor.
2. Импортируйте набор данных из текстового файла, который вы создали в
лабораторной работе №2. Убедитесь, что в файле содержится не менее
300 записей. Если записей меньше, то сдублируйте имеющиеся столько
раз, сколько нужно для выполнения вышеуказанного требования.
3. Запустите мастер обработки.
4. В открывшемся окне выберите пункт «Дерево решений». Нажмите «Далее».
5. В открывшемся окне обозначьте поле, которое у Вас было целевым в лабораторной работе №2, как выходное, а остальные – как входные. Нажмите «Далее».
6. На следующем этапе производится разбиение исходного множества на
обучающее и тестовое. Настройки не изменяйте. Нажмите «Далее».
7. На следующем этапе производится настройка параметров обучения дерева. Настройки не изменяйте. Нажмите «Далее».
8. На следующем этапе производится настройка способа обучения дерева.
Настройки не изменяйте. Нажмите «Далее».
9. На следующем этапе нажмите «Пуск». Когда процесс будет завершѐн,
нажмите «Далее».
10.На следующем этапе необходимо определить способы отображения полученных результатов. Отметьте пункты «Дерево решений», «Правила»,
«Значимость атрибутов». «Таблица сопряжѐнности» и «Что-если». Нажмите «Далее», а затем «Готово».
11.Сохраните полученные результаты.
12.При помощи опции «Что-если» попытайтесь найти скрытые закономерности, введѐнные в БД в лабораторной работе №2. Для удаления введѐнных значений входных параметров используйте функцию «Очистить значения входных полей»(см. рис. 2). Результаты поиска (скриншоты) сохраните в текстовый файл.
13.Сделайте выводы об эффективности построенного дерева и результатах
поиска.
Задание №3
1. Запустите Deductor.
2. Импортируйте набор данных из текстового файла, который вы создали в
лабораторной работе №2. Убедитесь, что в файле содержится не менее
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
300 записей. Если записей меньше, то сдублируйте имеющиеся столько
раз, сколько нужно для выполнения вышеуказанного требования.
3. Запустите мастер обработки.
4. В открывшемся окне выберите пункт «Дерево решений». Нажмите «Далее».
5. В открывшемся окне обозначьте поле, которое у Вас было целевым в лабораторной работе №2, как выходное, а остальные – как входные. Нажмите «Далее».
6. На следующем этапе производится разбиение исходного множества на
обучающее и тестовое. Настройки не изменяйте. Нажмите «Далее».
7. На следующем этапе производится настройка параметров обучения дерева. Настройки не изменяйте. Нажмите «Далее».
8. На следующем этапе производится настройка способа обучения дерева.
Выберите «Интерактивное построение».
9. На следующем этапе необходимо определить способы отображения полученных результатов. Отметьте пункты «Дерево решений», «Правила»,
«Значимость атрибутов». «Таблица сопряжѐнности» и «Что-если». Нажмите «Далее», а затем «Готово».
10.При помощи опции «Разбить текущий узел на подузлы» (см. рис.3) постройте дерево решений, ориентируясь на значение параметра GainRatio.
Внимание: при GainRatio= 0, использовать атрибут для разбиения не
нужно! Проводите разбиение узлов до тех пор, пока для всех переменных
GainRatio не станет равным нулю.
11.Сохраните полученные результаты.
12.При помощи опции «Что-если» попытайтесь найти скрытые закономерности, введѐнные в БД в лабораторной работе №2. Для удаления введѐнных значений входных параметров используйте функцию «Очистить значения входных полей» (см. рис. 2). Результаты поиска (скриншоты) сохраните в текстовый файл.
13.Сделайте выводы об эффективности построенного дерева, сравнив его с
деревом из задания №2. Сделайте выводы о результатах поиска скрытых
закономерностей.
Рис.19.Функция «Очистить значения входных полей»
Рис.20. Опция «Разбить текущий узел на подузлы»
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание отчѐта
Титульный лист.
Цель лабораторной работы.
Предметную область Вашей базы данных.
15 уникальных записей из Вашей базы данных.
Результаты выполнения задания №1 (дерево решений, правила,
мость атрибутов (привести только значимые атрибуты!), таблица
жѐнности, выводы).
6. Результаты выполнения задания №2 (дерево решений, правила,
мость атрибутов (привести только значимые атрибуты!), таблица
жѐнности, выводы).
7. Результаты выполнения задания №3 (дерево решений, правила,
мость атрибутов (привести только значимые атрибуты!), таблица
жѐнности, выводы).
1.
2.
3.
4.
5.
значисопрязначисопрязначисопря-
Контрольные вопросы
1. Что такое дерево решений?
2. Как построить дерево решений в Deductor?
3. Поясните содержимое вкладок «Дерево решений», «Правила», «Значимость атрибутов». «Таблица сопряжѐнности» и «Что-если»?
4. Что такое «жадный алгоритм»?
5. Области применения деревьев решений?
Лабораторная работа №4. Ассоциативные правила
Цель работы: Научиться использовать ассоциативные правила для анализа
данных
Введение
Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила, служит утверждение, что покупатель, приобретающий "Хлеб", приобретѐт и "Молоко" с вероятностью 75%.
Первая практическая задача, для решения которой были использованы ассоциативные правила, - нахождение типичных шаблонов покупок, совершаемых в супермаркете (анализ рыночной корзины, market basket analysis).
Он производится путѐм анализа баз данных транзакций с целью определения комбинаций товаров, связанных между собой. То есть, выполняется обнаружение товаров, наличие которых в транзакции влияет на вероятность появления других товаров или их комбинаций.
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Результаты, полученные с помощью анализа рыночной корзины, позволяют
оптимизировать ассортимент товаров и запасы, размещение их в торговых залах, увеличивать объѐмы продаж за счѐт предложения клиентам сопутствующих товаров. Например, если в результате анализа будет установлено, что совместная покупка макарон и кетчупа является типичным шаблоном, то разместив эти товары на одной и той же витрине можно «спровоцировать» покупателя
на их совместное приобретение.
Для решения задачи анализа рыночной корзины используются ассоциативные правила вида «если… то...». Например, «если клиент купил пиво, то он купит и чипсы». Каждая покупка именуется «транзакцией», на основании большего набора таких транзакций и строят исследования поведения клиента.
Для характеристики правила используются следующие метрики
Правило X→Y имеет поддержку s (support), если s транзакций из D, содержат пересечение множеств X и Y. Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X→Y справедливо с достоверностью c (confidence), если c транзакций из D, содержащих X, также содержат Y,
conf(X→Y) = supp(X→Y)/supp(X).
Например, «75% транзакций, содержащих хлеб, также содержат молоко.
3% от общего числа всех транзакций содержат оба товара». 75% – это достоверность (confidence) правила, 3% - это поддержка (support), или
«Хлеб»→«Молоко» с вероятностью 75% и поддержкой 3%.
В основном, очевидные правила имеют высокую поддержку и достоверность (60% и больше), но не являются знаниями де-факто. Основное внимание
необходимо уделять правилам, имеющим поддержку 5-10%, именно они могут
стать источником идеи промоакции или услуги.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи ПО Deductor
Academic 5.3.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
Изучить по лекциям и учебной литературе особенности обнаружение ассоциативных правил и работы в ПО Deductor Academic 5.3.
Порядок выполнения лабораторной работы
Задание №1
Произвести анализ совместно покупаемых товаров (бытовая химия).
1. Запустите Deductor.
2. Импортируйте набор данных из текстового файла «Чеки.txt».
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Запустите мастер обработки.
4. В открывшемся окне выберите пункт «Ассоциативные правила». Нажмите «Далее».
5. Убедитесь, что «ID» - это идентификатор транзакции, а «ITEM» - элемент
транзакции.
6. Дальнейшие настройки оставьте без изменений. Запустите процесс поиска правил.
7. После завершения процесса поиска правил необходимо определить способы отображения полученных результатов. Отметьте пункты «Правила»,
«Популярные наборы», «Дерево правил», «Что-если», «Таблица».
Правила - в визуализаторе выводятся полученные ассоциативные правила и их
основные расчѐтные характеристики; Популярные наборы - отображается
множество найденных популярных предметных наборов; Дерево правил - отображение множества ассоциативных правил в виде двухуровневого дерева построенного по условию или по следствию; Что-если - позволяет ответить на
вопрос, что будет в качестве следствия, если изменяться данные условия.
8. Сохраните полученные результаты.
9. Сделайте выводы о полученных правилах (достоверность, поддержка)
Задание №2
1. Внесите изменения в Вашу БД из лабораторной работы №2, чтобы она
стала пригодна для анализа средствами Deductor на предмет поиска ассоциативных правил. Убедитесь, что в файле содержится не менее 300 записей. Если записей меньше, то сдублируйте имеющиеся столько раз,
сколько нужно для выполнения вышеуказанного требования.
Замечание: если Вы до этой работы использовали в своей базе цифровую кодировку значений параметров – уберите еѐ!
2. Запустите Deductor.
3. Сгенерируйте набор правил и, при помощи опции «Что-если», попытайтесь выявить скрытые закономерности в Вашей БД (15 штук). Результаты
поместите в отчѐт. Сделайте выводы.
Содержание отчѐта
1.
2.
3.
4.
5.
6.
Титульный лист.
Цель лабораторной работы.
Предметная область Вашей базы данных.
15 уникальных записей из Вашей базы данных.
Перечень правил и выводы (задание №1).
Скриншоты результатов поиска скрытых закономерностей и выводы (задание №2).
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Контрольные вопросы
1.
2.
3.
4.
5.
Для чего могут быть использованы ассоциативные правила?
Какова структура ассоциативного правила? Приведите примеры правил.
Какие характеристики ассоциативных правил Вы знаете?
Опишите процесс поиска ассоциативных правил в Deductor.
Опишите процесс поиска ассоциативных правил.
Лабораторная работа №5. Кластеризация (самоорганизующаяся карта Кохонена)
Цель работы: Научиться использовать самоорганизующиеся карты Кохонена
для кластеризации данных
Введение
Приведѐм несколько определений кластеризации.
Кластеризация - это группировка объектов (наблюдений, событий) на основе данных, описывающих свойства объектов. Объекты внутри кластера должны
быть похожими друг на друга и отличаться от прочих, которые вошли в другие
кластеры.
Кластеризация - группировка объектов на основе близости их свойств; каждый кластер состоит из схожих объектов. а объекты разных кластеров существенно отличаются.
Кластеризация – процедура, которая любому объекту
ставит в соответствие метку кластера
.
Кластеризацию используют, когда отсутствуют априорные сведения относительно классов, к которым можно отнести объекты исследуемого набора данных, либо, когда число объектов велико, что затрудняет их ручной анализ.
Постановка задачи кластеризации сложна и неоднозначна, так как:
оптимальное количество кластеров в общем случае неизвестно;
выбор меры «похожести или близости свойств объектов между собой, как
и критерия качества кластеризации, часто носит субъективный характер.
Самоорганизующаяся карта Кохонена (self organizing шар, SOM) позволяет
представлять результаты кластеризации в виде двумерных карт, где расстояния
между объектами соответствуют расстояниям между их векторами в многомерном пространстве, а сами значения признаков отображаются различными цветами и оттенками, Можно провести аналогию между SOM и обычной географической картой, где размещение объектов и расстояния между ними соответствуют их расположению на земной поверхности, Однако, кроме горизонтальных координат, необходимо показать и рельеф - высоту гор, холмов, а также
глубину водоѐмов. Для этого используется специальная цветовая гамма. Так,
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
высота местности отображается с помощью оттенков коричневого, глубина морей и океанов - синего: чем выше или глубже объект, тем более тѐмным цветом
он окрашивается. Таким образом, двумерная карта позволяет представлять
трѐхмерные данные.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи ПО Deductor
Academic 5.3.
Домашнее задание студентам для подготовки к выполнению лабораторной
работы
Изучить по лекциям и учебной литературе особенности карт Кохонена и работы в ПО Deductor Academic 5.3.
Порядок выполнения лабораторной работы
Задание №1
Выполните сегментацию абонентов телекоммуникационной компании.
1. Запустите Deductor.
2. Импортируйте набор данных из текстового файла «Абоненты.txt».
3. На третьем шаге импорта убедитесь, что «Разделители целой и дробной
части числа» - точка, а не запятая!
4. На шестом шаге импорта настройте тип данных для полей: «Среднемесячный расход», «Средняя продолжительность разговора», «Доля звонков
на стационарные телефоны» - вещественный; для всех остальных - целый.
5. Запустите мастер обработки и выберите пункт «карта Кохонена».
6. На первом шаге установите назначение полей. Полю «Код» присвойте назначение – «Информационное», всем остальным – «Входное».
7. На следующем шаге задайте способ разбиения исходного набора данных
на обучающее и тестовое. Для решения текущей задачи тестовое множество не нужно, поэтому укажите для обучающего множества - 100%.
8. На следующем шаге задайте размеры карты. По X - 24, по Y - 18.
9. Остальные настройки оставьте без изменений. Запустите процесс построения. Выполнение операции займѐт некоторое время (длительность –
500 эпох).
10.В качестве способа отображения отметьте пункт «Карта Кохонена».
11.На следующем шаге отметьте все входные столбцы, а также пункты
«Кластеры» и «Матрица ошибок квантования». Нажмите «Далее».
12.Кластеры выделились не очень чѐтко. Попробуйте улучшить результат.
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
13.Постройте дополнительную карту Кохонена, в которой максимальной
значимостью будут обладать поля: «Возраст» и «Среднемесячный расход». Скопируйте узел «Самоорганизующаяся карта [24; 18]» (ПКМ по
узлу и выберите из контекстного меню требуемый пункт) и сделайте его
перенастройку (выделите скопированный узел и нажмите Alt+Enter).
14.На первом шаге нажмите «Настройка нормализации». Для всех полей,
кроме «Возраст» и «Среднемесячный расход», установите значимость
равную 30%. Все остальные настройки оставьте без изменений.
15.Запустите построение карты.
16.После завершения построения, дополнительно активируйте следующие
визуализаторы: «Матрица сравнения», «Профили кластеров», «Связи кластеров».
17.Хотя количество кластеров увеличилось до 11 (было 10), но, качество
разбиения несколько улучшилось (значения коэффициентов в матрице
ошибок квантования уменьшились).
18.Проанализируйте кластеры, ответив на следующие вопросы (ответы – в
отчѐт):
- какие кластеры обладают наименьшим разбросом значений параметров?
- какие кластеры обладают наибольшим разбросом значений параметров?
19.Выявите наиболее заметные особенности каждого кластера (например,
наибольшее количество SMS за месяц среди всех кластеров) и, исходя из
этого, присвойте каждому кластеру новое имя (например, «Бизнесмены»).
Причину выбора имени для каждого кластера опишите в отчѐте.
20.Сохраните полученные результаты.
Матрица ошибок квантования – отображает среднее расстояние от расположения примеров до центра ячейки. Пример находится в многомерном пространстве, где количество измерений равно числу входных полей. Центр ячейки – точка пространства с координатами, равными весам нейрона. Матрица
ошибок квантования показывает, насколько хорошо обучена нейросеть.
Чем меньше среднее расстояние до центра ячейки, тем ближе к ней расположены примеры, и тем лучше построена модель.
Визуализатор Профили кластеров позволяет наглядно оценить результаты
кластеризации и исследовать статистические характеристики кластеров. Он
доступен для обработчиков, реализующих алгоритмы кластеризации и даѐт
возможность наглядно оценить сегментацию исходного набора данных, а
также влияние на формирование кластеров входных факторов.
Задание №2
1. Импортируйте набор данных из текстового файла, который вы создали в
лабораторной работе №2. Убедитесь, что в файле содержится не менее
300 записей. Если записей меньше, то сдублируйте имеющиеся столько
раз, сколько нужно для выполнения вышеуказанного требования.
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Запустите Deductor.
3. Разбейте данные на кластеры и, при помощи опции «Что-если», попытайтесь выявить скрытые закономерности в Вашей БД (15 штук). Результаты
поместите в отчѐт. Сделайте выводы.
Содержание отчѐта
Титульный лист.
Цель лабораторной работы.
Предметная область Вашей базы данных.
15 уникальных записей из Вашей базы данных.
Скриншоты кластеров, матриц ошибок квантования для двух сценариев и
результаты выполнения пп. 18 и 19 (задание №1).
6. Скриншоты результатов поиска скрытых закономерностей и выводы (задание №2).
1.
2.
3.
4.
5.
Контрольные вопросы
1.
2.
3.
4.
5.
Что такое кластеризация?
Что такое карта Кохонена?
Для решения каких задач применяется карта Кохонена?
Кратко опишите процесс кластеризации (Кохонен).
Опишите процесс кластеризации (Кохонен) в Deductor.
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лабораторная работа №6. Нейронные сети
Цель работы: Научиться использовать нейронные сети для анализа данных
Введение
Нейронные сети(НС) представляют собой вычислительные структуры, моделирующие простые биологические процессы, аналогичные процессам, происходящим в человеческом мозге.
НС– это распределѐнные и параллельные системы, способные к адаптивному обучению путѐм реакции на положительные и отрицательные воздействия.
В основе построения сети лежит элементарный преобразователь, называемый
искусственным нейроном или просто нейроном по аналогии с его биологическим прототипом.
Структуру НС можно описать следующим образом. НС состоит из нескольких слоѐв: входной, внутренние (скрытые) и выходной слои. Входной слой реализует связь с входными данными, выходной – с выходными. Внутренних слоѐв может быть от одного и больше.
В каждом слое содержится несколько нейронов.
Между нейронами есть связи, называемые весами.
В Deductor в основе обработчика«Нейросеть» лежит многослойный персептрон с двумя алгоритмами обучения.
Рис. 21. Структура нейрона
Рис. 22. Пример нейросети
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
НС способна имитировать какой-либо процесс. Любое изменение входов
НС ведѐт
к изменению еѐ выходов. Причѐм выходы НС однозначно зависят от еѐ входов.
Перед тем как использовать НС, еѐ необходимо обучить. Задача обучения
здесь равносильна задаче аппроксимации функции, то есть восстановление
функции по отдельно взятым еѐ точкам – таблично заданной функции. Таким
образом, для обучения нужно подготовить таблицу с входными значениями и
соответствующими им выходными значениями.
По такой таблице НС сама находит зависимости выходных полей от входных. Далее эти зависимости можно использовать, подавая на вход НС некоторые значения. На выходе будут восстановлены зависимые от них значения.
Причѐм на вход можно подавать значения, на которых НС не обучалась.
Важно следующее. Обучающая выборка не должна содержать противоречий, так как НС однозначно сопоставляет выходные значения входным. После
обучения на вход НС необходимо подавать значения из диапазона, на котором
она обучалась. Например, если при обучении НС на один из еѐ входов подавались значения от 0 до100, то в дальнейшем следует на этот вход подавать значения из диапазона от 0 до100.
НС работают по принципу «чѐрного ящика», однако, в отличие от статистических регрессионных моделей (используются для исследования влияния одной
или нескольких независимых переменных на зависимую переменную), менее
чувствительны к выбросам, шумам, мультиколлинеарности (наличие линейной
зависимости между независимыми переменными регрессионной модели) во
входных признаках.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи ПО Deductor
Academic 5.3.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
Изучить по лекциям и учебной литературе особенности нейронных сетей и
работы в ПО Deductor Academic 5.3.
Порядок выполнения лабораторной работы
Задание №1. Оценка стоимости недвижимости
Особенностью процесса оценки стоимости объекта имущества является его
рыночный характер. Это означает, что процесс оценки объекта не ограничива42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ется учѐтом одних только затрат на создание или приобретение оцениваемого
объекта собственности - необходим учѐт совокупности рыночных факторов,
экономических особенностей оцениваемого объекта, а также макроэкономического и микроэкономического окружения. Кроме того, рынок недвижимости
очень динамичный, поэтому требуется периодическая переоценка объектов
собственности.
НС как универсальные аппроксиматоры позволяют строить сложные нелинейные регрессионные модели типа "чѐрный ящик". Создание моделей для
оценки стоимости недвижимости могут существенно повысить эффективность
работы организаций, занимающихся риэлтерской деятельностью.
Целевой признак – стоимость квартиры.
1.
2.
3.
4.
5.
Запустите Deductor.
Импортируйте набор данных из файла «Недвижимость.ddf».
Щѐлкните левой кнопкой мыши по появившемуся пункту сценария.
Нажмите F7.
Выберите пункт «Качество данных». Все настройки мастера обработки
оставьте по умолчанию. В результате откроется визуализатор «Оценка
качества данных».
Аудит данных обнаружил несколько выбросов (выходящих за границы 3сигма) и экстремальных значений (выходящих за границы 5-сигма). В частности, детализация показывает, что для поля «Общая площадь» есть три экстремальных значения 133 и 134 м2. Можно также предположить наличие линейной
корреляции между общей и жилой площадью.
Вообще, нейросетевые модели достаточно устойчивы к шумам, выбросам и
мультиколлинеарности, поэтому предпринимать особых усилий по подготовке
выборки для них обычно не требуется. Тем не менее, экстремальные значения
лучше всѐ-таки удалить. Они точно не улучшат качество модели.
3-сигма - вероятность того, что случайная величина отклонится от своего математического ожидания на большую величину, чем утроенное среднее
квадратичное отклонение, практически равна нулю. Правило справедливо
только для случайных величин, распределѐнных по нормальному закону.
Например, пусть имеется выборка наблюдений за ежедневными продажами в магазине. Значения их распределены по нормальному закону с математическим ожиданием 150000 руб. и среднеквадратическим отклонением 20000
руб. Тогда в соответствии с правилом 3-х сигм продажи ниже, чем 150 000 20 000 x 3 = 90 000, и выше, чем 150 000 + 20 000 х 3 = 210 000, являются
практически невозможными событиями. Фактически это означает, что рассматривать данные объѐмы продаж как потенциально возможные не имеет
смысла.
6. По умолчанию предлагается ограничить найденные выбросы и экстремальные значения. Переопределите это действие:
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
для выбросов выберете пункт «Оставить без изменения»;
для экстремальных значений – «Удалять».
7. Для того чтобы эти действия были произведены, после узла «Качество
данных» добавьте узел «Редактирование выбросов», оставив включѐнным
флаг «Использовать информацию узла оценки качества данных».
8. Откройте мастер обработки и запустите нейросеть. Убедитесь, что
«Стоимость» - выходное поле. Остальные настройки – без изменений. На
последнем шаге («Определение способов отображения») должны быть
отмечены первые три пункта.
9. При помощи построенной нейросети (визуализатора «Что-Если») выполните прогнозирование стоимости квартиры со следующими характеристиками:
количество комнат – 3;
район – Орджоникидзевский;
планировка – Свердловский вариант;
этаж – 7;
площадь – 63;
жилая – 41;
кухня – 8;
состояние – 4;
наличие агентства – нет.
Задание №2
1. Импортируйте набор данных из текстового файла, который вы создали в
лабораторной работе №2. Убедитесь, что в файле содержится не менее
300 записей. Если записей меньше, то сдублируйте имеющиеся столько
раз, сколько нужно для выполнения вышеуказанного требования.
2. Запустите Deductor.
3. Постройте нейросеть и, при помощи опции «Что-если», попытайтесь выявить скрытые закономерности в Вашей БД (15 штук). Результаты поместите в отчѐт. Сделайте выводы.
Содержание отчѐта
1.
2.
3.
4.
5.
Титульный лист.
Цель лабораторной работы.
Предметная область Вашей базы данных.
Скриншоты графа нейросети, диаграммы рассеяния (п.8) и что-если (п.9).
15 уникальных записей из Вашей базы данных.
44
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6. Скриншоты результатов поиска скрытых закономерностей и выводы (задание №2).
Контрольные вопросы
1.
2.
3.
4.
5.
Что такое нейронная сеть?
Какова структура нейросети?
Что такое 3-сигма?
Какова структура искусственного нейрона?
Опишите процесс построения нейросети в Deductor.
Лабораторная работа №7. Автокорреляция. Корреляция. Факторный анализ
Цель работы: Научиться использовать автокорреляцию, корреляцию и факторный анализ для исследования данных
Введение
Целью автокорреляционного анализа является выяснение степени статистической зависимости между различными значениями (отсчѐтами) случайной последовательности, которую образует поле выборки данных. В процессе автокорреляционного анализа рассчитываются коэффициенты корреляции (мера
взаимной зависимости) для двух значений выборки, отстоящих друг от друга на
определѐнное количество отсчѐтов, называемые также лагом. Совокупность коэффициентов корреляции по всем лагам представляет собой автокорреляционную функцию ряда (АКФ):
R(k)= corr(X(t), X(t+k)), где k > 0 – целое число (лаг)
По поведению АКФ можно судить о характере анализируемой последовательности и наличии периодичности (например, сезонной).
Очевидно, что при k = 0, автокорреляционная функция будет максимальной
и равной 1, т.е. значение последовательности полностью коррелировано само с
собой, степень статистической взаимозависимости максимальна. Действительно, если факт появления данного значения имел место, то и соответствующая
вероятность равна 1. По мере увеличения числа лагов, т.е. увеличения расстояния между двумя значениями, для которых вычисляется коэффициент корреляции, значения АКФ будут убывать из-за уменьшения статистической взаимозависимости между этими значениями (вероятность появления одного из них все
меньше влияет на вероятность появления другого). При этом чем быстрее убывает АКФ, тем быстрее изменяется анализируемая последовательность. И наоборот, если АКФ убывает медленно, то и соответствующий процесс является
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
относительно гладким. Если в исходной выборке имеет место тренд (плавное
увеличение или уменьшение значений ряда), то плавное изменение АКФ также
будет иметь место. При наличии сезонных колебаний в исходном наборе данных, АКФ также будет иметь периодические всплески.
Для применения алгоритма автокорреляции в Deductor необходимо выбрать
поле, для которого вычисляется АКФ. В поле «Количество отсчѐтов» требуется
указать количество отсчѐтов, для которых будут рассчитаны значения АКФ.
Корреляционный анализ применяется для оценки зависимости выходных
полей, данных от входных факторов и устранения незначащих факторов. Принцип корреляционного анализа состоит в поиске таких значений, которые в наименьшей степени коррелированны (взаимосвязаны) с выходным результатом.
Такие факторы могут быть исключены из результирующего набора данных
практически без потери полезной информации. Критерием принятия решения
об исключении является порог значимости. Если модуль корреляции (степень
взаимозависимости) между входным и выходным факторами меньше порога
значимости, то соответствующий фактор отбрасывается как незначащий.
Факторный анализ – это математический инструмент для понижения размерности пространства признаков, широко применяется в экономике, социологии, психологии.
Информативность многомерного описания объекта возрастает с увеличением количества используемых признаков. Однако очень трудно сразу выбрать и
существенные, и независимые друг от друга характеристики. Как правило, аналитик начинает с заведомо избыточного количества признаков, и в процессе
работы сталкивается с необходимостью адекватной интерпретации большого
объѐма полученных данных и их компактной визуализации. Возникает вопрос в
том, что многие признаки, вероятно, в некоторой степени дублируют друг друга, а вся полученная информация в целом избыточна. За связанными друг с другом (коррелирующими) переменными, по-видимому, стоит влияние некоторой
скрытой переменной (фактора), с помощью которой можно объяснить наблюдаемое сходство полученных оценок. Выделение факторов, как переменных более общего, более высокого порядка, позволяет по-новому взглянуть на полученные данные, заметить те связи между переменными, которые ранее небыли
очевидны.
В узле «Факторный анализ» для факторизации корреляционной матрицы
используется метод главных компонент. Он сводится к выбору новой ортогональной системы координат в пространстве наблюдений. В качестве первой
главной компоненты избирают направление, вдоль которого массив данных
имеет наибольший разброс. Выбор каждой главной последующей компоненты
происходит так, чтобы разброс данных вдоль неѐ был максимальным, и чтобы
эта главная компонента была ортогональна другим главным компонентам, выбранным прежде. В результате получаем несколько главных компонент, каждая
следующая из которых несѐт все меньше информации из исходного набора.
Следующим шагом является выбор наиболее информативных главных компонент, которые будут использоваться в дальнейшем анализе.
46
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Посмотрим на следующий рисунок. На нѐм изображено двумерное пространство наблюдений в осях Х и Y, соответствующих двум измеряемым параметрам.
Рис. 23
Как видно, разброс данных велик по обоим направлениям. Теперь повернѐм
систему координат так, чтобы направление наибольшего разброса массива данных, то есть перейдѐм в систему координат оси Y соответствовало X’ – Y’. Теперь по оси X‘ дисперсия данных невелика, и появляется возможность отбросить это направление, перейдя к одномерному пространству.
Рис. 24
В этом случае потери некоторой части информации могут компенсироваться удобством работы с данными меньшей размерности. Аналогичные действия
выполняются в многомерном случае: система координат последовательно вращается таким образом, чтобы каждый следующий поворот минимизировал остаточный разброс массива данных.
Таким образом, факторный анализ решает две главные задачи:
1. Понижение размерности числа используемых переменных за счѐт их объяснения меньшим числом факторов.
2. Группировка и структурирование полученных данных.
Математическая модель факторного анализа имеет вид:
где p – количество переменных, vi – значение i-й переменной. Коэффициенты
wj,i называются нагрузкой i-й переменной на j-й фактор или нагрузкой j-го фактора на i-ю переменную. Таким образом, нагрузка – это корреляция между исходной переменной и фактором.
Аналогичным образом:
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
где xi – значение i-й переменной, которое выражено в виде линейной комбинации m главных факторов, количество которых меньше числа исходных признаков, и остаточным членом ui, характерным только для переменной xi; ai,j – регрессионные коэффициенты, показывающие вклад каждого из k факторов в данную переменную.
Факторы имеют две характеристики: долю объясняемой дисперсии и нагрузки. Результат процедуры факторизации заключается в формировании матрицы факторных нагрузок.
Табл.7
xi
f1
w11
x1
w21
x2
w31
x3
…
…
wp1
xp
…
…
fm
w1m
w2m
w3m
…
wpm
На практике аналитикам чаще всего интересен факторный анализ с ортогональным вращением осей, когда при повороте осей координат угол между факторами остаѐтся прямым. Цель исследователя заключается в поиске простой
структуры или попытке объяснить большее число переменных меньшим числом факторов. «Простота» хорошего факторного решения заключается в том,
что каждая переменная имеет наиболее простое факторное объяснение, т.е. характеризуется преобладающим влиянием некоторого одного фактора, и в
меньшей степени связана с другими факторами. И наоборот: один фактор должен быть специфическим образом связан с одной группой переменных и не
связан с другими переменными.
В узле реализовано два метода вращения: варимакс и квартимакс.
Варимакс – наиболее часто используемый на практике метод, цель которого
– минимизировать количество переменных, имеющих высокие нагрузки на
данных фактор, что способствует упрощению описания фактора за счѐт группировки вокруг него только тех переменных, которые с ним связаны в большей
степени, чем с остальными.
Квартимакс противоположен варимаксу, поскольку минимизирует количество факторов, необходимых для объяснения данной переменной. Квартимаксвращение приводит к выделению одного из общих факторов с достаточно высокими нагрузками на большинство переменных.
После расчѐта факторных нагрузок для каждой переменной доступны два
показателя: собственное значение и объѐм объясняемой дисперсии в %, а также
суммарный процент дисперсии. Пример такого расчѐта приведѐн в таблице ниже.
Собственное значение фактора – это его вклад в дисперсию переменных,
объясняемую влиянием общих факторов. Считается, что те факторы, у которых
48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
этот показатель меньше 1,0, не вносят значительного вклада в объяснение результата.
Второй расчѐтный показатель – процент объясняемой дисперсии переменных. Принято считать, что при хорошем факторном решении выбирают столько
факторов, чтобы они в сумме объясняли не менее 70-75%. В отдельных случаях
этот показатель может достигать 85-90%.
Факторный анализ широко используется в следующей ситуации. В очень
большом исходном наборе данных есть много полей, некоторые из которых
взаимозависимы. На этом наборе данных требуется, к примеру, обучить нейронную сеть. Для того чтобы снизить время, требуемое на обучение сети, и
требования к объѐму обучающей выборки, с помощью факторного анализа
осуществляют переход в новое пространство факторов меньшей размерности.
Так как большая часть информативности исходных данных сохраняется в выбранных главных компонентах, то качество модели ухудшается незначительно,
зато намного сокращается время обучения сети. Главной проблемой факторного анализа является выделение и интерпретация главных факторов.
Табл. 8
Фактор Собственное
% объясСуммарный
значение
няемой
%
дисперсии объясняемой
дисперсии
5,14
51,4
51,4
1
1,72
17,2
68,6
2
1,03
10,3
78,9
3
0,76
7,7
86,6
4
0,38
3,9
90,5
5
0,33
3,3
93,7
6
0,28
2,8
96,6
7
0,21
2,1
98,7
8
0,08
0,8
99,5
9
0,05
0,5
100,0
10
Настройки в Deductor
В узле «Факторный анализ» помимо вида метода (варимакс, квартимакс, без
вращения) следует выбрать число выделяемых факторов.
Можно задать непосредственно число факторов в диапазоне от 1 до общего
числа переменных, или задать долю дисперсии, описанной выделяемыми факторами по отношению к общей дисперсии.
После расчѐта факторных нагрузок количество выявленных факторов можно изменить, уточняя порог значимости или количество факторов.
Пример
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рассмотрим пример из области анализа клиентской базы телекоммуникационной компании. В подобных задачах обычно в распоряжении исследователя
оказываются десятки и сотни переменных, описывающих поведенческий профиль клиента – агрегированная структура потребления клиентом продуктов/услуг компании за определѐнный временной период, как в количественном,
так и в стоимостном выражении.
Многие из таких переменных сильно коррелируют друг с другом, например,
число звонков и стоимость звонков. Аналитику можно отобрать только часть
таких переменных, опираясь на опыт и интуицию, а лучше воспользоваться
факторным анализом для получения сжатого описания всех переменных в виде
нескольких главных факторов.
Пусть даны признаки, описывающие структуру потребления услуг мобильной связи (в среднем за год) в разных аспектах: тип вызова (исходящий входящий), время звонка, направление связи (фиксированная, мобильная, сообщение)
и другие, всего 21 непрерывная переменная.
Рис. 25
.
Рис. 26
Поставим задачу компактно описать каждого клиента, т.е. минимизировать
число переменных.
Воспользуемся узлом «Факторный анализ» и зададим: метод вращения – варимакс, число факторов – 5.
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 27
На следующем шаге мастера убедимся, что пять фактов обеспечили почти
70% вклада в результат. Откроем визуализатор «Факторный анализ» и установим для отображения в матрице факторных нагрузок порог значимости 0,45
(остальные значения будут скрыты). Все нагрузки становятся либо большими,
либо маленькими, что упрощает интерпретацию.
Рис. 28
Видно, что вращение помогло объединить наши переменные в логические
группы:
Фактор 1 – высокие нагрузки на поведенческие характеристики клиента,
отвечающие за gsm-звонки.
Фактор 2 – фактор, отвечающий за обычные sms-сообщения.
Фактор 3 – фактор, отвечающий за активность в международном направлении, включая звонки и sms.
Фактор 4 – фактор, отвечающий за активность в использовании платных
sms-сервисов.
Фактор 5 – фактор, отвечающий за звонки на фиксированные средства
связи.
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В результате после обработчика нам доступен набор данных, где каждому
клиенту соответствуют значения пяти главных факторов. Такой набор данных
можно использовать для построения какой-нибудь модели, классификации или
регрессии.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи ПО Deductor
Academic 5.3.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
Изучить по лекциям и учебной литературе особенности проведения корреляционного и факторного анализа.
Задание №1. Автокорреляционный анализ (продажа товара)
Есть таблица (табл. 9) продаж некоторого товара за два с небольшим года.
Определим наличие сезонных зависимостей продаж этого товара.
1. Скопируйте таблицу в txt-файл. Сохраните файл.
2. Запустите автокорреляцию. Одно из полей будет отмечено как недоступное. Просто нажмите «Далее». Вычислите автокорреляционную функцию
для поля «Объѐм продаж». Для оценки сезонности выберите количество
отсчѐтов = 24 (два года).
Табл. 9
Дата
01.01.2012
01.02.2012
01.03.2012
01.04.2012
01.05.2012
01.06.2012
01.07.2012
01.08.2012
01.09.2012
01.10.2012
01.11.2012
01.12.2012
01.01.2013
01.02.2013
01.03.2013
01.04.2013
Объѐм продаж
4795
5772
8259
8418
8064
5462
4142
3910
3450
6994
1999
7286
7355
7108
1876
2976
52
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
01.05.2013
01.06.2013
01.07.2013
01.08.2013
01.09.2013
01.10.2013
01.11.2013
01.12.2013
01.01.2014
01.02.2014
01.03.2014
01.04.2014
01.05.2014
01.06.2014
01.07.2014
01.08.2014
01.09.2014
6365
1806
4774
3391
7824
3118
9404
8451
7820
6319
2954
5819
8815
2915
3575
7488
3183
3. Постройте диаграмму автокорреляции.
4. На диаграмме АКФ выглядит следующим образом (рис. 29). Как видно из
рисунка, в этом наборе данных автокорреляция слабая. Это обусловлено
тем, что данные, использованные в работе, были сгенерированы случайным образом.
5. Создайте свой набор данных и проделайте для него пп. 1 – 5.
Рис. 29
Задание №2. Корреляционный анализ
Пусть есть временные ряды (табл. 10) продаж товаров. Определите корреляцию «Товара 1» с остальными.
1. Скопируйте таблицу в txt-файл.
53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.
3.
4.
5.
6.
7.
Сохраните файл.
Импортируйте информацию из файла в Deductor.
Нажмите «F7» и выберите узел «Корреляционный анализ».
Отметьте «Товар 1» как входное поле. Остальные – выходные.
Прочие настройки оставьте без изменений.
В качестве визуализатора выберите «Матрица корреляции».
Как видно из рис. 30, ряд продаж для «Товар 2» имеет очень большую положительную, а «Товар 3» – отрицательную корреляцию. Из этого можно сделать вывод, что «Товар 2», возможно, является сопутствующим товаром, а «Товар 3» – заместителем «Товар 1». Корреляция с продажами «Товар 4» с «Товар
1» является отрицательной, но при этом абсолютное значение корреляции невелико, и, следовательно, можно говорить об отсутствии взаимосвязи между продажами «Товар 1» и продажами «Товар 4».
Табл. 10
Товар 1
10
12
14
13
14
14
12
10
16
13
17
Товар
2
20
22
25
24
25
25
21
18
24
21
25
Товар
3
15
12
9
10
9
9
12
14
9
9
7
Товар 4
25
26
26
25
24
23
24
23
22
23
25
Рис. 30
Выберите из табл. 11 (согласно варианта) нужный файл.
8. Переведите выбранный файл в формат txt.
9. Импортируйте информацию из него в Deductor.
10.Проведите корреляционный анализ. В качестве выходного поля выберите
Result. Остальные поля – входные. Некоторые поля изначально будут отмечены как непригодные. С ними никаких действий предпринимать не
нужно.
11.Сделайте выводы.
54
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Табл.11
Номер в списке группы
1 или 9 или 17 или 25
2 или 10 или 18 или 26
3 или 11 или 19 или 27
4 или 12 или 20 или 28
5 или 13 или 21 или 29
6 или 14 или 22 или 30
7 или 15 или 23 или 31
8 или 16 или 24 или 32
Название файла
AusOpen-men-2013.csv
AusOpen-women-2013.csv
FrenchOpen-men-2013.csv
FrenchOpen-women-2013.csv
USOpen-men-2013.csv
USOpen-women-2013.csv
Wimbledon-men-2013.csv
Wimbledon-women-2013.csv
Задание №3. Факторный анализ
1. Выполните факторный анализ данных из файла, выбранного в предыдущем задании.
2. Задайте следующие настройки: а) варимакс и 5 факторов; б) квартимакс и
5 факторов; в) без вращения и 5 факторов.
3. Задайте следующие настройки: а) варимакс и 10 факторов; б) квартимакс
и 10 факторов; в) без вращения и 10 факторов.
4. Задайте следующие настройки: а) варимакс и 15 факторов; б) квартимакс
и 15 факторов; в) без вращения и 15 факторов.
5. Сделайте выводы об эффективности работы факторного анализа при различных настройках.
Содержание отчѐта:
1.
2.
3.
4.
5.
6.
Титульный лист.
Цель лабораторной работы.
Номер варианта.
Задание №1: Результаты выполнения пунктов 6 и 7.
Задание №2: Результаты выполнения пунктов 7 – 12.
Задание №3: Результаты выполнения пунктов 2 – 5.
Контрольные вопросы
1.
2.
3.
4.
5.
6.
7.
Что такое автокорреляционный анализ?
Что такое АКФ?
Что такое корреляционный анализ?
Что такое факторный анализ?
Какие задачи решает факторный анализ?
Что такое варимакс и квартимакс?
Какова главная проблема факторного анализа?
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лабораторная работа №8. Дубликаты и противоречия. Трансформация
данных
Цель работы: Научиться выявлять дубликаты и противоречия
Введение
Дубликаты и противоречия
При построении модели регрессии или классификации в анализируемых
таблицах нужно определить входные и выходные поля, зависимости между которыми и исследуются. Предполагается, что значения входных полей полностью определяют значения выходных.
При подобной постановке задачи возможно возникновение противоречий,
то есть присутствие групп записей, значения в ключевых (входных) полях которых полностью совпадают, а в целевых (выходных) – различаются. Например, если значения в ключевых полях – это коды товаров, а в целевых – цены
этих товаров, то присутствие двух записей с одинаковым кодом, но с разной
ценой как раз и создаѐт противоречие. Обычно бывает так, что только одна запись из группы противоречивых является правильной, а остальные – ошибочными. Очевидно, что присутствие ошибочных данных искажает результаты
анализа, поэтому противоречивые данные чаще всего лучше вообще исключить
из исходной выборки. Однако следует заметить, что искусственное введение
противоречий в исходные данные может быть полезным, например, если нужно
ввести некоторую неопределѐнность в данные, кроме того противоречия могут
отражать особенности поведения анализируемого объекта.
Также в данных могут встречаться записи с одинаковыми входными факторами и одинаковыми выходными, т.е. дубликаты. Эти данные чаще всего избыточны, хотя присутствие дубликатов в анализируемых данных можно рассматривать как способ повышения «значимости» дублирующийся информации. В
некоторых случаях такой приѐм может быть полезен, например, если при обучении нейросети нужно особо выделить и усилить влияние некоторых наборов
значений. Однако в других случаях дублирование может указывать на ошибки
при подготовке исходных данных. Дубликаты могут искажать результаты некоторых методов анализа, например, статистического.
Так или иначе, в процессе анализа иногда возникает проблема выявления
дубликатов и противоречий в данных. В Deductor для автоматизации этого процесса есть соответствующий инструмент – обработчик «Дубликаты и противоречия».
Дубликаты – записи в таблице, все входные и выходные поля которых
одинаковые.
Противоречия – записи в таблице, у которых все входные поля одинаковые, но отличаются хотя бы по одному выходному полю.
56
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Суть обработки состоит в том, что определяются входные и выходные поля.
Алгоритм ищет во всем наборе записи, для которых одинаковым входным полям соответствуют одинаковые (дубликаты) или разные (противоречия) выходные поля. На основании этой информации создаются два дополнительных логических поля – «Дубликат» и «Противоречие», принимающие значения «истина» или «ложь», и дополнительные числовые поля «Группа дубликатов» и
«Группа противоречий», в которые записываются номер группы дубликатов и
группы противоречий, содержащих данную запись. Если запись не является
дубликатом или противоречием, то соответствующие поля будут пустыми.
Настройка выявления дубликатов и противоречий заключается в выборе назначений полей исходной выборки данных, то есть в выборе, какие поля входные, а какие – выходные.
Трансформация данных
Анализируемая информация, представленная в виде набора данных, имеет
определѐнный формат. Под форматом данных подразумевается отнесение их к
определѐнному типу (целочисленные, строковые, даты), задание вида (дискретные или непрерывные) и т. п. Для анализа различных аспектов информации
может потребоваться преобразование еѐ формата или трансформация. Кроме
преобразования форматов трансформация включает в себя изменение представления данных и другие операции, связанные с преобразованиями входного набора данных.
Настройка набора данных
Обработчик «Настройка набора данных» предназначен для изменения имени, метки, типа, вида и назначения полей текущей выборки данных и кэширования выходного набора.
У каждого поля можно изменить метку столбца, которая будет использоваться для дальнейшей работы в программе. Если в текущей выборке данных
поле имеет имя «Name», ему можно задать метку «Наименование», что гораздо
удобнее при дальнейшем отображении этого поля в таблицах или диаграммах.
Изменение имени поля удобно в тех случаях, когда имена столбцов могут
измениться в источнике данных или при перенастройке узлов верхних уровней.
В этом случае в узле «Настройка набора данных» имя исходного столбца заменяется другим, на которое и настраиваются все дочерние узлы. После такой
операции изменение имѐн полей на верхних уровнях не потребует перенастройки всех дочерних узлов в дереве сценариев.
У каждого поля можно изменить вид, тип данных, назначение.
Сортировка
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
С помощью сортировки можно изменять порядок следования записей в исходной выборке данных в соответствии с заданным пользователем алгоритмом
сортировки. Результатом выполнения сортировки будет новая выборка данных,
записи в которой будут следовать в соответствии с заданными параметрами
сортировки.
Дата и время
Преобразование даты служит для анализа всевозможных показателей за определѐнный период (год, квартал, месяц, неделя, день, час, минута, секунда).
Суть преобразования заключается в том, что на основе столбца с информацией
о дате/времени формируются один или несколько столбцов, в которых указывается, к какому заданному интервалу времени принадлежит строка данных. Тип
интервала задаѐтся аналитиком, исходя из того, что он хочет выделить из даты.
Такая операция требуется потому, что очень часто интересным для анализа
является не сама дата, а еѐ производная. Например, для анализа посещаемости
магазина интересен день недели, а для оценки загруженности касс – час.
Замена данных
В результате выполнения этой операции производится замена значений по
таблице подстановки, которая содержит пары, состоящие из исходного значения и выходного значения. Например, 0 – «красный», 1 – «зелѐный», 2 – «синий». Или «зима» – «январь», «весна» – «апрель», «лето» – «июль», «осень» «октябрь». Для каждого значения исходного набора данных ищется соответствие среди исходных значений таблицы подстановки. Если соответствие найдено, то значение меняется на соответствующее выходное значение из таблицы
подстановки. Если значение не найдено в таблице, оно может быть либо заменено значением, указанным для замены «по умолчанию», либо оставлено без
изменений (если такое значение не указано). Кроме того, можно указать значения, которые нужно вставить вместо пустых ячеек.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи ПО Deductor
Academic 5.3.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
Изучить по лекциям и учебной литературе особенности выявления дубликатов и противоречий.
Задание №1. Выявление дубликатов и противоречий
58
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пусть есть следующая таблица
Табл.12
Поле 1
01.01.2014
21.05.2014
21.05.2014
21.05.2014
01.09.2014
01.09.2014
Поле
2
2
3
3
3
4
4
Поле 3
Поле 4
1000
1000
700
700
1200
1200
1500
1500
1500
1500
1700
1700
1. Скопируйте еѐ в txt-файл.
2. Импортируйте данные из файла в Deductor.
3. При помощи обработчика «Настройка набора данных», измените названия полей на более информативные (проявите фантазию). Измените тип
«Поля 2» на строковый.
4. Отсортируйте данные по убыванию (первый столбец).
5. Выполните преобразование даты. Добавьте столбец «Дата (Год+Месяц)»
в строковом формате.
6. Замените значения второго столбца на какие-либо другие при помощи
обработчика «Замена данных».
7. Проведите поиск дубликатов и противоречий.
8. Сделайте скриншот полученных результатов.
Содержание отчѐта:
1. Титульный лист.
2. Цель лабораторной работы.
3. Задание №1: Результаты выполнения пунктов 3-8.
Контрольные вопросы
1.
2.
3.
4.
5.
Для чего используется настройка набора данных?
Для чего используется сортировка?
Для чего используется обработчик «Дата и время»?
Для чего используется замена данных?
Что такое дубликаты и противоречия?
59
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Лабораторная работа №9. Выработка рекомендаций
Цель работы: Ознакомиться с методами искусственного интеллекта, используемыми для формирования рекомендаций
Введение
Формирование рекомендаций на основе предпочтений других людей используется в различных ситуациях: рекомендование товаров на сайте электронной торговли, указание интересных сайтов или помощь в поиске нужной музыки и фильмов.
Информацию о предпочтениях можно собирать по-разному. Иногда данными являются купленные посетителем товары, а мнения об этих товарах представляются в виде голосования «да/нет» или оценки по пятибалльной шкале.
Коллаборативная фильтрация
С нетехнологичным способом получить рекомендацию о товаре, фильме
или развлекательном сайте вы знакомы. Достаточно спросить у друзей. Знаете
вы и о том, что у некоторых ваших друзей вкус лучше, чем у других; вы имели
возможность убедиться в этом, поскольку не раз оказывалось, что им нравится
то же, что и вам. Но по мере увеличения количества предложений становится
все менее практично основывать решение на опросе небольшой группы людей,
поскольку они могут просто не знать обо всех имеющихся вариантах. Тут-то и
приходит на помощь то, что принято называть коллаборативной фильтрацией.
Обычно алгоритм коллаборативной фильтрации работает следующим образом: просматривает большую группу людей и отыскивает в ней меньшую группу с такими же вкусами, как у вас. Он смотрит, какие ещѐ вещи им нравятся,
объединяет предпочтения и создаѐт ранжированный список предложений. Есть
несколько способов решить, какие люди похожи, и объединить их предпочтения в список.
Сначала нужно представить информацию о предпочтениях людей. В данной
работе для этого будет использоваться вложенный словарь. Он удобен для экспериментов с алгоритмами и иллюстрации их возможностей. Большой объѐм
информации, конечно, удобнее хранить в базе данных.
Собрав данные о том, что нравится людям, нужно определить схожесть их
вкусов. Для этого каждый человек сравнивается со всеми другими и вычисляется коэффициент (или оценка) правдоподобия. Для этого можно использовать
разные способы. В данной лабораторной работе речь пойдѐт о двух из них: евклидовом расстоянии и коэффициенте корреляции Пирсона.
Один из самых простых способов вычисления оценки подобия – это евклидово расстояние. В этом случае предметы, которые люди оценивали сообща,
представляются в виде координатных осей. Теперь в этой системе координат
60
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
можно расположить точки, соответствующие людям, и посмотреть, насколько
они оказались близки (рис)
На этом рисунке показаны люди, представленные точками в пространстве
предпочтений. Toby имеет координату 4,5 по оси Snakes и координату 1,0 по
оси Dupree. Чем ближе два человека в пространстве предпочтений, тем более
схожи их предпочтения. Поскольку эта диаграмма двумерная, то одновременно
можно смотреть только на два показателя, но принцип остаѐтся тем же самым и
для большего числа показателей.
Рис.31. Люди в пространстве предпочтений
Коэффициент корреляции Пирсона
Чуть более сложный способ определить степень схожести интересов людей
даѐт коэффициент корреляции Пирсона. Коэффициент корреляции – это мера
того, насколько хорошо два набора данных ложатся на прямую. Формула сложнее, чем для вычисления евклидова расстояния, но она даѐт лучшие результаты,
когда данные плохо нормализованы, например, если некоторый критик устойчиво выставляет фильмам более низкие оценки, чем в среднем.
Для визуализации этого метода можно нанести на диаграмму оценки, выставленные двумя критиками, как показано на рис. . Mick LaSalle оценил фильм
«Superman» на 3, а Gene Seymour – на 5, поэтому мы наносим точку (3,5).
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 32. Сравнение двух кинокритиков на точечной диаграмме
На диаграмме также изображена прямая линия. Она называется линией наилучшего приближения, поскольку проходит настолько близко ко всем точкам
на диаграмме, насколько возможно. Если бы оба критика выставили всем
фильмам одинаковые оценки, то эта линия оказалась бы диагональной и прошла бы через все точки. В этом случае получилась бы идеальная корреляция с
коэффициентом 1. Но в нашем случае критики разошлись в оценках, поэтому
коэффициент корреляции равен 0,4. На рис. показан пример с гораздо более
высоким коэффициентом корреляции 0,75.
Рис. 33. Два критика с высоким коэффициентом корреляции
У коэффициента корреляции Пирсона есть одно интересное свойство, которое можно наблюдать на рисунке – он корректирует обесценивание оценок.
Видно, что Jack Matthews систематически выставляет более высокие оценки, чем Lisa Rose, но линия всѐ равно проходит близко к точкам, поскольку их
предпочтения схожи. Если один критик склонен выставлять более высокие
оценки, чем другой, то идеальная корреляция всѐ равно возможна при условии,
62
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
что разница в оценках постоянна. Метод евклидова расстояния в этом случае
выдал бы результат, что критики не похожи, поскольку один всегда оказывается строже другого, несмотря на то, что их вкусы, по существу, очень сходны. В
зависимости от конкретного приложения такое поведение может вас устраивать
или нет.
Программа для вычисления коэффициента корреляции Пирсона сначала находит фильмы, оценѐнные обоими критиками, и вычисляет сумму и сумму
квадратов выставленных ими оценок, а также сумму произведений оценок. На
последнем этапе (строки 65 – 69) найденные значения используются для вычисления коэффициента корреляции. В отличие от евклидовой метрики, эта
формула интуитивно не так очевидна.
Эта функция возвращает значение от -1 до 1. Значение 1 означает, что два
человека выставили каждому предмету в точности одинаковые оценки. В отличие от евклидовой метрики, масштабировать возвращѐнное значение для приведения к нужному диапазону не требуется.
Описание программного обеспечения
Данная лабораторная работа должна выполняться при помощи Python 2.7.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
Изучить по учебной литературе особенности работы с Python.
Задание №1. Использование оценки по евклидову расстоянию для определения подобия между парами критиков.
1. Скопируйте файл recommendations.py в какую-нибудь новую папку.
2. Откройте его в Notepad++. Изучите его структуру (до строки 39).
Структура файла recommendations.py (до строки 39):
Строки 3–19 – вложенный словарь. Он содержит имена критиков и перечень
оценок, которые они выставили соответствующим фильмам.
Строки 22-38 – функция оценки подобия по евклидову расстоянию.
3. Найти оценку подобия между следующими парами критиков: Lisa Rose и
Gene Seymour, Michael Phillips и Claudia Puig, Mick LaSalle и Jack
Matthews, Lisa Rose и Jack Matthews, Michael Phillips и Mick LaSalle.
Нахождение оценки подобия:
А) ЗапуститеIDLE (Python GUI). Откройтевнѐм recommendations.py (File ->
Open)
63
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Б) Откроется новое окно с текстом программного кода. Запустите файл на выполнение (Run->RunModule или нажмите F5).
В) В появившемся окне введите:
import recommendations
нажмите «Enter»
recommendations.sim_distance(recommendations.critics,'X','Y'), где X – имяпервогокритика, а Y – второго.Нажмите «Enter». Скопируйте в отчѐт полученное
значение оценки. Повторите процедуру необходимое количество раз.
4. Сделайте выводы относительно полученных результатов.
Задание №2. Использование оценки по евклидову расстоянию для определения подобия между парами критиков (другие данные).
1. Сделайтекопиюфайла recommendations.py. Назовитееѐ recommendations1.py.
2. Откройте его в Notepad++. Удалите строки 3-19. Создайте свой вложенный словарь (по образу словаря из задания 1). В качестве критиков
могут выступать, например, Ваши друзья. Фильмы – на Ваше усмотрение. Формат оценок – как в recommendations.py. Язык – английский
(транслит).
3. Найдите оценку подобия между 5 парами критиков.
4. Сделайте выводы относительно полученных результатов.
Задание №3. Определите степень схожести интересов людей при помощи
коэффициента корреляции Пирсона (для файла recommendations.py)
Описание структуры файла recommendations.py.
Строки 41 – 71 – возвращает коэффициент корреляции Пирсона:
# Возвращает коэффициент корреляции Пирсона между p1 и p2
def sim_pearson(prefs,p1,p2):
# Получить список предметов, оценѐнных обоими
si={}
for item in prefs[p1]:
if item in prefs[p2]: si[item]=1
# Найти число элементов
n=len(si)
# Если нет ни одной общей оценки, вернуть 0
64
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
if n==0: return 0
# Вычислить сумму всех предпочтений
sum1=sum([prefs[p1][it] for it in si])
sum2=sum([prefs[p2][it] for it in si])
# Вычислитьсуммуквадратов
sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
sum2Sq=sum([pow(prefs[p2][it],2) for it in si])
# Вычислитьсуммупроизведений
pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
# ВычислитькоэффициентПирсона
num=pSum-(sum1*sum2/n)
den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
if den==0: return 0
r=num/den
return r
1. Определите степень схожести интересов пар критиков (взять из задания
№1).
2. Запустите IDLE (Python GUI). Откройтевнѐм recommendations.py (File ->
Open).
3. Откроется новое окно с текстом программного кода. Запустите файл на
выполнение (Run->RunModule или нажмите F5).
4. В появившемся окне введите:
import recommendations
нажмите «Enter»
print
recommendations.sim_pearson(recommendations.critics,
'Lisa
Rose','Gene Seymour').
5. Повторите процедуру необходимое количество раз.
6. Сделайте выводы.
Задание №4. Определите степень схожести интересов людей при помощи
коэффициента корреляции Пирсона (другие данные)
Определите степень схожести интересов людей при помощи коэффициента
корреляции Пирсона (для файла recommendations1.py).
1. Определите степень схожести для Ваших данных (аналогично заданию
№3).
2. Сделайте выводы.
65
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задание №5. Ранжирование критиков
Имея функции для сравнения двух людей, можно написать функцию, которая будет вычислять оценку подобия всех имеющихся людей с данным человеком и искать наилучшее соответствие. Допустим, нас интересуют кинокритики
с таким же вкусом, как у Lisa Rose. За реализацию этой возможности в
recommendations.py отвечает следующий фрагмент программного кода:
# Возвращает список наилучших соответствий для человека из словаря prefs.
# Количество результатов в списке и функция подобия – необязательные
# параметры.
def topMatches(prefs,person,n=5,similarity=sim_pearson):
scores=[(similarity(prefs,person,other),other)
for other in prefs if other!=person]
# Отсортировать список по убыванию оценок
scores.sort( )
scores.reverse( )
return scores[0:n]
Эта функция сравнивает выбранного критика со всеми остальными хранящимися в словаре пользователями с помощью одной из ранее определѐнных
метрик, применяя для этого трансформацию списка (list comprehension). И возвращает первые n элементов отсортированного списка результатов.
Если вызвать еѐ, передав соответствующее имя, то она вернѐт список кинокритиков и оценку подобия выбранного человека для каждого из них.
1. Выполните ранжирование критиков (для всех, имеющихся в словаре).
2. Запустите IDLE (Python GUI). Откройтевнѐм recommendations.py (File ->
Open).
3. Откроется новое окно с текстом программного кода. Запустите файл на
выполнение (Run->RunModule или нажмите F5).
4. В появившемся окне введите:
import recommendations
нажмите «Enter»
recommendations.topMatches(recommendations.critics,'X',n=3), гдеХ – имякритика.
5. Скопируйте результаты в отчѐт.
6. Выполните вышеуказанную процедуру необходимое количество раз.
7. Сделайте выводы.
Задание №6. Ранжирование критиков (другие данные)
66
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Выполните ранжирование критиков для Ваших данных (аналогично заданию №5).
2. Сделайте выводы.
Задание №7. Рекомендование предметов
Найти подходящего критика – это, конечно, неплохо, но в действительности-то хочется получить рекомендацию, какой фильм посмотреть. И прямо сейчас. Можно было бы посмотреть, какие фильмы понравились человеку с похожими вкусами, и выбрать из них те, что ещѐ не просмотрены.
Но при таком подходе можно было бы случайно наткнуться на критиков,
ничего не писавших о фильмах, которые могли бы мне понравиться. Можно
также отобрать критика, которому почему-то понравился фильм, получивший
отрицательные отзывы от всех остальных критиков, вошедших в список
topMatches.
Чтобы разрешить эти проблемы, необходимо ранжировать сами фильмы,
вычислив взвешенную сумму оценок критиков. Для примера возьмѐм критика
Toby. Берѐм каждого из отобранных критиков и умножаем его оценку подобия
с Toby на оценку, которую он выставил каждому фильму. В табл. показан результат вычислений.
В этой таблице приведены коэффициенты корреляции для каждого критика
и оценки, поставленные ими трѐм фильмам («The Night Listener», «Lady in the
Water» и «Jus tMy Luck»), которые Toby не оценивал. В столбцах «П.x» находится произведение коэффициента подобия на оценку, выставленную критиком. Смысл в том, чтобы мнение критика с похожими на Toby вкусами вносило
больший вклад в общую оценку, чем мнение критика, не похожего него. В
строке «Итого» приведены суммы, вычисленных таким образом величин. Можно было бы использовать для ранжирования сами эти суммы, но тогда фильм,
который просмотрело больше людей, получил бы преимущество. Чтобы исправить эту несправедливость, необходимо разделить полученную величину на
сумму коэффициентов подобия для всех критиков, которые рецензировали
фильм (строка «S подоб» в таблице).
Табл.13
Критик
Подобие Night П.х
Night
0.99
3.0
2.97
Rose
3.0
1.14
Seymour 0.38
0.89
4.5
4.02
Puig
0.92
3.0
2.77
LaSalle
3.0
1.99
Matthews 0.66
12.89
Итого
3.84
S подоб
3.35
Итого /
S подоб.
Lady П.х Luck П.х
Lady
Luck
2.5
2.48 3.0
2.97
3.0
1.14 1.5
0.57
3.0
2.68
3.0
2.77 2.0
1.85
3.0
1.99
8.38
8.07
2.95
3.18
2.83
2.53
67
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Поскольку фильм «The Night Listener» рецензировали все, величина «Итого» для него делится на сумму всех коэффициентов подобия. Напротив, фильм
«Lady in the Water» критик Puig не рецензировал, следовательно, в этом случае
величина «Итого» делится на сумму коэффициентов подобия всех критиков,
кроме Puig. В последней строке показано частное от деления.
Всѐ вышеперечисленное реализуется добавлением следующего кода:
# Получить рекомендации для заданного человека, пользуясь взвешенным средним
# оценок, данных всеми остальными пользователями
def getRecommendations(prefs,person,similarity=sim_pearson):
totals={}
simSums={}
for other in prefs:
# сравнивать заданного человека (Toby, в данном случае) с собой же не нужно
if other==person: continue
sim=similarity(prefs,person,other)
# игнорировать нулевые и отрицательные оценки
ifsim<=0: continue
for item in prefs[other]:
# оценивать только фильмы, которые заданный человек ещѐ не смотрел
if item not in prefs[person] or prefs[person][item]==0:
# Коэффициент подобия * Оценка
totals.setdefault(item,0)
totals[item]+=prefs[other][item]*sim
# Сумма коэффициентов подобия
simSums.setdefault(item,0)
simSums[item]+=sim
# Создать нормализованный список
rankings=[(total/simSums[item],item) for item,total in totals.items( )]
# Вернуть отсортированный список
rankings.sort( )
rankings.reverse( )
returnrankings
68
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Код, реализующий этот алгоритм, абсолютно прямолинеен и может работать как с евклидовым расстоянием, так и с коэффициентом корреляции Пирсона.
В цикле осуществляется обход всех людей, присутствующих в словаре
prefs.
Для каждого вычисляется коэффициент подобия с заданным человеком
person. Далее обходятся все фильмы, которым текущий критик выставил оценку. В строке, выделенной полужирным шрифтом, вычисляется окончательная
оценка фильма – оценка, данная каждым критиком, умножается на коэффициент подобия этого критика и произведения суммируются. В самом конце оценки нормализуются путѐм деления на сумму коэффициентов подобия и возвращается отсортированный список результатов.
1. Запустите IDLE (Python GUI). Откройте в нѐм recommendations.py (File ->
Open).
2. Откроется новое окно с текстом программного кода. Запустите файл на
выполнение (Run->RunModule или нажмите F5).
3. В появившемся окне введите:
import recommendations
нажмите «Enter»
recommendations.getRecommendations(recommendations.critics,'Toby')
скопируйте результат в отчѐт
введите (многоточие при вводе удалите):
recommendations.getRecommendations(recommendations.critics,'Toby',
... similarity=recommendations.sim_distance)
скопируйтерезультатвотчѐт
В результате выполнения этого задания, мы получили не только ранжированный список фильмов, но и прогноз оценок, которые заданный пользователь
поставит каждому из них. Имея такую информацию, можно решить, стоит ли
вообще смотреть фильм. В зависимости от приложения вы можете вообще не
давать рекомендаций, если не нашлось ничего, отвечающего стандартам данного пользователя. Поэкспериментировав, вы обнаружите, что выбор метрики подобия влияет на результаты очень слабо.
4. Проделайте вышеуказанную процедуру для все критиков из списка.
5. Сделайте выводы
Задание №8. Рекомендование предметов (другие данные)
1. Выполните рекомендование предметов для Ваших данных (аналогично
заданию №7).
2. Сделайте выводы.
69
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание отчѐта:
5. Титульный лист.
6. Цель лабораторной работы.
7. Задание №1 и №2: Результаты выполнения пунктов 3-4.
8. Задание №3: Результаты выполнения пунктов 4-6.
9. Задание №4: Результаты выполнения пунктов 1-2.
10.Задание №5: Результаты выполнения пунктов 4-7.
11.Задание №6: Результаты выполнения пунктов 1-2.
12.Задание №7: Результаты выполнения пунктов 3-5.
13.Задание №8: Результаты выполнения пунктов 1-2.
Контрольные вопросы
1. Как работает алгоритм коллаборативной фильтрации?
2. Как вычислить оценку подобия при помощи евклидова расстояния?
3. Как вычислить оценку подобия при помощи коэффициента корреляции
Пирсона?
4. Поясните, как выполняется ранжирование критиков?
5. Поясните, как выполняется рекомендование предметов?
Лабораторная работа №10. Генетическое программирование
Введение
Генетическое программирование – это методика машинного обучения, прототипом которой является биологическая эволюция. В общем случае, мы начинаем с большого набора программ (популяция), сгенерированных случайным
образом или написанных вручную, о которых известно, что это достаточно хорошие решения. Затем эти программы конкурируют между собой в попытке
решить некоторую поставленную пользователем задачу. Это может быть игра, в
которой программы соревнуются между собой напрямую, или специальный
тест, призванный определить, какая программа лучше. По завершении состязания составляется ранжированный список программ – от наилучшей к наихудшей.
Затем – здесь в дело вступает эволюция – лучшие программы копируются и
модифицируются одним из двух способов. Самый простой называется мутацией. В этом случае некоторые части программы случайным образом и очень незначительно изменяются в надежде, что от этого решение станет лучше. Другой
способ называется скрещиванием (или кроссовером) – часть одной из отобранных программ перемещается в другую. В результате процедуры копирования и
модификации создаѐтся много новых программ, которые основаны на наилучших особях предыдущей популяции, но не совпадают с ними.
70
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
На каждом этапе качество программ вычисляется с помощью функции выживаемости (fitness function). Так как размер популяции не изменяется, программы, оказавшиеся плохими, удаляются из популяции, освобождая место для
новых. Создаѐтся новая популяция, которая называется «следующим поколением», и весь процесс повторяется. Поскольку сохраняются и изменяются самые
лучшие программы, то есть надежда, что с каждым поколением они будут совершенствоваться, как дети, которые могут превзойти своих родителей.
Новые поколения создаются до тех пор, пока не будет выполнено условие
завершения, которое в зависимости от задачи может формулироваться одним из
следующих способов:
Найдено идеальное решение.
Найдено достаточно хорошее решение.
Решение не удаѐтся улучшить на протяжении нескольких поколений.
Количество поколений достигло заданного предела.
Для некоторых задач, например, определения математической функции,
отображающей один набор значений на другой, можно найти идеальное решение. Для других, например, когда речь идѐт о настольной игре, найденное решение может быть не идеальным, поскольку его качество зависит от стратегии
противника.
Генетический алгоритм – это метод оптимизации, в основе которого лежит
идея естественного отбора как средства достижения наилучшего результата.
При любом способе оптимизации изначально имеется некоторая метрика или
алгоритм, и мы просто пытаемся подобрать для него наилучшие параметры.
Как и в случае оптимизации, для генетического программирования необходим способ измерения качества решения. Но, в отличие от оптимизации, решением является не просто набор параметров заданного алгоритма. Путѐм естественного отбора автоматически проектируется сам алгоритм со всеми своими параметрами.
Для создания программ, которые можно тестировать, подвергать мутации
и скрещиванию, необходимо как-то представлять их в виде кода на языке
Python и запускать. Представление должно допускать простую модификацию и,
что более существенно, быть настоящей исполняемой программой. Поэтому
просто генерировать случайные строки и пытаться трактовать их как Pythonпрограмму не получится. Было предложено несколько способов представления
программ для генетического программирования, но самым распространѐнным
является древовидное представление.
Каждый узел представляет либо операцию над дочерними узлами, либо
является листовым, например, параметром или константой.
Может показаться, что подобные деревья годятся только для построения
совсем простых функций. Но следует отметить две вещи. Во-первых, узлы,
входящие в дерево, могут представлять очень сложные компоненты. Во71
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
вторых, дерево может быть рекурсивным, если допускаются ссылки на узлы,
расположенные выше. С помощью таких деревьев можно организовывать циклы и более сложные управляющие структуры.
Задание №1. Представление деревьев на языке Python. Построение и вычисление деревьев
Прежде, чем переходить к выполнению задания, ознакомьтесь с той частью
файла gp.py, которая понадобится Вам для этого.
from random import random,randint,choice
from copy import deepcopy
from math import log
class fwrapper:
def __init__(self,function,childcount,name):
self.function=function
self.childcount=childcount
self.name=name
class node:
def __init__(self,fw,children):
self.function=fw.function
self.name=fw.name
self.children=children
def evaluate(self,inp):
results=[n.evaluate(inp) for n in self.children]
return self.function(results)
class paramnode:
def __init__(self,idx):
self.idx=idx
def evaluate(self,inp):
return inp[self.idx]
class constnode:
def __init__(self,v):
self.v=v
def evaluate(self,inp):
returnself.v
В этом фрагменте программного кода присутствуют 4 класса:
fwrapper
Обѐртка для функций, которые будут находиться в узлах, представляющих
функции. Его члены – имя функции, сама функция и количество принимаемых
параметров.
72
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
node
Класс функциональных узлов (имеющих потомков). Инициализируется экземпляром класса fwrapper. Метод evaluate вычисляет значения дочерних узлов и
передаѐт их представленной данным узлом функции в качестве параметров.
paramnode
Класс узлов, которые просто возвращают один из переданных программе параметров. Его метод evaluate возвращает параметр, соответствующий значению
idx.
constnode
Узлы, возвращающие константы. Метод evaluate просто возвращает то значение, которым экземпляр был инициализирован.
Кроме классов в вышеуказанном файле присутствует ряд функций, которые
будут вызываться при посещении узлов.
addw=fwrapper(lambda l:l[0]+l[1],2,'add')
subw=fwrapper(lambda l:l[0]-l[1],2,'subtract')
mulw=fwrapper(lambda l:l[0]*l[1],2,'multiply')
def iffunc(l):
if l[0]>0: return l[1]
else: return l[2]
ifw=fwrapper(iffunc,3,'if')
def isgreater(l):
if l[0]>l[1]: return 1
else: return 0
gtw=fwrapper(isgreater,2,'isgreater')
flist=[addw,mulw,ifw,gtw,subw]
С помощью класса node строим дерево программы:
def exampletree( ):
return node(ifw,[
node(gtw,[paramnode(0),constnode(3)]),
node(addw,[paramnode(1),constnode(5)]),
node(subw,[paramnode(1),constnode(2)]),
]
)
1.
2.
3.
4.
Запустите графическую оболочку.
Из-под неѐ откройте файл gp.py.
Запустите его на выполнение.
Введите следующие строки:
import gp
exampletree=gp.exampletree( )
exampletree.evaluate([2,3])
73
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5.
6.
7.
8.
Нажмите «Enter».
Введите следующую информацию: exampletree.evaluate([5,3])
Нажмите «Enter».
На экране будут отображены результаты работы программы.
Пока не очень понятно? Однако в этом задании был построен миниязык для
представления древовидных программ и написан интерпретатор для него. Последующие задания внесут ясность в вопрос, рассматриваемый в данной лабораторной работе.
Задание №2. Визуализация программы
Древовидные программы будут создаваться автоматически, об их структуре
Вы заранее ничего знать не будете. Поэтому необходим способ визуализации
программы, так чтобы еѐ было легко интерпретировать. При проектировании
класса node было предусмотрено, что в каждом узле будет храниться имя представляемой им функции в виде строки, поэтому функция вывода должна просто
вернуть эту строку и отображаемые строки от своих дочерних узлов. Чтобы
программу было проще читать, строки дочерних узлов нужно печатать с отступом, тогда будут сразу видны отношения родитель–потомок, существующие в
дереве.
Для реализации вышеуказанного:
в классе node присутствует метод display, который выводит представление дерева в виде строки:
def display(self,indent=0):
print (' '*indent)+self.name
for c in self.children:
c.display(indent+1)
в классе paramnode присутствует метод display, который печатает индекс
возвращаемого параметра:
def display(self,indent=0):
print '%sp%d' % (' '*indent,self.idx)
классе constnode также присутствует метод display:
def display(self,indent=0):
print '%s%d' % (' '*indent,self.v)
1.
2.
3.
4.
Запустите графическую оболочку.
Из-под неѐ откройте файл gp.py.
Запустите его на выполнение.
Введите следующие строки, чтобы распечатать:
exampletree=gp.exampletree( )
exampletree.display( )
5. На экране должен появиться такой результат:
74
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
if
isgreater
p0
3
add
p1
5
subtract
p1
2
Так выглядит дерево, построенное при помощи класса node. Код для него
приведѐн в предыдущем задании (если p0>3, то p1+5 иначе p1-2).
Задание №3. Создание начальной популяции
Хотя программы для генетического программирования можно создавать и
вручную, но обычно начальная популяция состоит из случайно сгенерированных программ. Это упрощает запуск процесса, поскольку отпадает необходимость проектировать несколько программ, которые почти решают задачу. Кроме того, таким образом в начальную популяцию вносится разнообразие, тогда
как разные программы для решения одной задачи, написанные одним программистом, скорее всего, были бы похожи и, хотя давали бы почти правильный ответ, идеальное решение могло бы выглядеть совершенно иначе.
Для построения случайной программы нужно создать узел, поместив в него
случайно выбранную функцию, а затем – необходимое количество дочерних
узлов, каждый из которых может иметь свои дочерние узлы и т. д. Как обычно
при работе с деревьями, проще всего сделать это рекурсивно.
В файле gp.py это реализовано при помощи функции makerandomtree:
def makerandomtree(pc,maxdepth=4,fpr=0.5,ppr=0.6):
if random( )<fpr and maxdepth>0:
f=choice(flist)
children=[makerandomtree(pc,maxdepth-1,fpr,ppr)
for i in range(f.childcount)]
return node(f,children)
elif random( )<ppr:
return paramnode(randint(0,pc-1))
else:
return constnode(randint(0,10))
Эта функция создаѐт узел, содержащий случайно выбранную функцию, и
проверяет, сколько у этой функции должно быть параметров. Для каждого дочернего узла функция вызывает себя рекурсивно, чтобы создать новый узел.
Так конструируется все дерево, причѐм процесс построения ветвей завершается
75
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
в тот момент, когда у очередного узла нет дочерних (то есть он представляет
либо константу, либо переменную-параметр). Параметр pc равен числу параметров, принимаемых деревом на входе. Параметр fpr задаѐт вероятность того,
что вновь создаваемый узел будет соответствовать функции, а ppr – вероятность того, что узел, не являющийся функцией, будет иметь тип paramnode.
1.
2.
3.
4.
Запустите графическую оболочку.
Из-под неѐ откройте файл gp.py.
Запустите его на выполнение.
Введите следующие строки:
random1=gp.makerandomtree(2)
random1.evaluate([7,1])
На экране появится некоторое число (у меня это было «7»).
5. Введите следующую строку:
random1.evaluate([2,4])
На экране появится некоторое число (у меня это было «2»).
6. Введите следующие строки:
random2=gp.makerandomtree(2)
random2.evaluate([5,3])
На экране появится некоторое число (у меня это было «480»).
7. Введите следующую строку:
random2.evaluate([5,20])
На экране появится некоторое число (у меня это было «18500»).
Если все листовые узлы оказываются константами, то программа вообще не
принимает параметров, поэтому результат еѐ работы не зависит от того, что Вы
подадите на вход. С помощью функции, использованной ранее, можно распечатать случайно сгенерированные деревья.
8. Введите следующую строку: random1.display( ), а после вывода результата на экран: random2.display( ).
У меня получилось два таких дерева: p0 и
if
p1
multiply
add
multiply
9
p1
p0
multiply
76
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
p0
p1
add
add
multiply
6
p1
p0
p0
В этом задании программа построила два дерева, которые сгенерировала
случайным образом (исходя из заданных настроек).
Некоторые деревья оказываются довольно глубокими, поскольку каждая
ветвь продолжает расти, пока не встретится узел без потомков. Поэтому так
важно ограничивать максимальную глубину, иначе растущее дерево может переполнить стек.
Задание №4. Проверка решения
В данном задании будут рассмотрены способы проверки правильности получаемых решений.
Простой математический тест
Один из самых простых тестов, применяемых в генетическом программировании, – реконструкция простой математической функции. Предположим, что
задана таблица входных и выходных данных.
Табл.14
X
Y
Результат
26
35
829
8
24
141
20
1
467
33
11
1215
37
16
1517
Существует некая функция, отображающая заданные пары (X, Y) на результаты, но что это за функция, - неизвестно. Статистик мог бы попытаться применить к этой задаче регрессионный анализ, но для этого нужно знать структуру формулы. Другой вариант – построить прогностическую модель с помощью
метода k-ближайших соседей, но для этого требуется хранить все данные. В некоторых случаях нужна лишь формула, быть может, для встраивания в другую,
77
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
гораздо более простую программу или чтобы объяснить человеку, что происходит.
Для генерации этих данных использовалась следующая функция:
2
x 2 y 3x 5 . В файле gp.py эта функция представлена в следующем виде:
def hiddenfunction(x,y):
return x**2+2*y+3*x+5
Воспользуемся этой функцией для построения набора данных, на котором
будем проверять сгенерированные программы. Функция для создания набора
данных buildhiddenset:
def buildhiddenset( ):
rows=[]
for i in range(200):
x=randint(0,40)
y=randint(0,40)
rows.append([x,y,hiddenfunction(x,y)])
return rows
Измерение успеха
Необходимо научиться измерять качество найденного решения. В данном
случае мы сравниваем результаты работы программы с известными числами,
поэтому для проверки нужно посмотреть, насколько мало оказалось расхождение.
def scorefunction(tree,s):
dif=0
for data in s:
v=tree.evaluate([data[0],data[1]])
dif+=abs(v-data[2])
return dif
Эта функция перебирает все строки набора данных, вычисляет функцию от
указанных в ней аргументов и сравнивает с результатом. Абсолютные значения
разностей суммируются. Чем меньше сумма, тем лучше программа, а значение
0 говорит о том, что все результаты в точности совпали. Проверим, насколько
хороши оказались сгенерированные ранее программы. Проделайте:
>>> import gp
>>>hiddenset=gp.buildhiddenset()
>>> random1=gp.makerandomtree(2)
78
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
>>> random2=gp.makerandomtree(2)
>>>gp.scorefunction(random2,hiddenset)
117926
>>>gp.scorefunction(random1,hiddenset
115744
Поскольку мы сгенерировали лишь две программы, причѐм совершено случайные, шансы на отыскание правильной функции ничтожно малы. Однако теперь у нас есть способ проверить, насколько хорошо программа даѐт прогноз
математической функции.
Мутация программ
Отобранные наилучшие программы копируются и модифицируются для
включения в следующее поколение. Выше уже отмечалось, что мутация заключается в небольшом изменении одной программы. Изменить древовидную программу можно разными способами, например, изменив функцию в каком-то узле или одну из ветвей. Если для новой функции требуется другое количество
дочерних узлов, то либо какие-то ветви удаляются, либо добавляются новые
(см. рис. 34)
Другой способ мутации – замена какого-то поддерева целиком, как показано на рис. 35.
Рис. 34
Мутации должны быть незначительными. Не следует, к примеру, заменять
бОльшую часть узлов дерева. Вместо этого нужно задать относительно малую
вероятность того, что какой-либо узел будет изменѐн.
79
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Далее вы начинаете обход дерева от корня, и если случайно выбранное число оказалось меньше пороговой вероятности, то узел мутирует одним из описанных выше способов. В противном случае проверяются дочерние узлы.
Ради простоты, в данной работе будет рассмотрен только второй способ.
Рис. 35
Функция mutate начинает с корня дерева и решает, следует ли изменить
узел.
def mutate(t,pc,probchange=0.1):
if random( )<probchange:
return makerandomtree(pc)
else:
result=deepcopy(t)
if isinstance(t,node):
result.children=[mutate(c,pc,probchange) for c in t.children]
return result
Если нет, она рекурсивно вызывает mutate для дочерних узлов. Может случиться, что мутации подвергнутся все узлы, а иногда дерево вообще не изменится.
Запустите несколько раз функцию mutate для случайно сгенерированных
программ и посмотрите, как она модифицирует деревья:
import gp
random1=gp.makerandomtree(2)
random1.display( )
Будет выведено дерево
80
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
muttree=gp.mutate(random1,2)
muttree.display( )
Будет выведено изменѐнное дерево
gp.scorefunction(random1,hiddenset)
105357 – результат
gp.scorefunction(muttree,hiddenset)
105688 – изменѐнный результат
Напомним, что мутации случайны, они необязательно должны вести к
улучшению решения. Мы лишь надеемся, что в каких-то случаях результат станет лучше. Изменение будет продолжаться, и после смены нескольких поколений мы все-таки найдѐм (если повезѐт) наилучшее решение.
Скрещивание
Другой вид модификации программ – это скрещивание. Для этого две успешные программы комбинируются с целью получения новой. Обычно это делается путѐм замены какой-то ветви одной программы ветвью другой. На рис.
36 приведѐн соответствующий пример
Рис. 36
81
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Функции, выполняющей скрещивание, передаются два дерева, и она обходит оба. Если случайно выбранное число не превышает пороговой вероятности,
то функция возвращает копию первого дерева, в которой одна из ветвей заменена какой-то ветвью, взятой из второго дерева. Поскольку обход выполняется
параллельно, то скрещивание произойдѐт примерно на одном уровне каждого
дерева.
Это реализуется функцией crossover:
def crossover(t1,t2,probswap=0.7,top=1):
if random( )<probswap and not top:
return deepcopy(t2)
else:
result=deepcopy(t1)
if isinstance(t1,node) and isinstance(t2,node):
result.children=[crossover(c,choice(t2.children),probswap,0)
for c in t1.children]
return result
Попробуйте применить эту функцию:
random1=gp.makerandomtree(2)
random1.display( )
На экране будет отображено дерево
random2=gp.makerandomtree(2)
random2.display( )
На экране будет отображено дерево
cross=gp.crossover(random1,random2)
cross.display( )
На экране будет отображено дерево, полученное в результате скрещивания
Вероятно, вы заметили, что перестановка ветвей может радикально изменить поведение программы. Кроме того, результат работы каждой программы
может оказаться близок к правильному по совершенно различным причинам,
поэтому скрещенная программа может давать результаты, совершенно не похожие ни на одного из родителей. Как и раньше, мы надеемся, что в результате
некоторых скрещиваний решение удастся улучшить, и оно перейдѐт в следующее поколение.
Задание №5. Построение окружающей среды
82
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вооружившись средством для измерения успеха и двумя методами модификации наилучших программ, мы можем перейти к созданию конкурентной среды, в которой программы будут эволюционировать. Необходимые шаги представлены блок-схемой на рис. 37. Смысл в том, чтобы создать набор случайных
программ, отобрать из них наилучшие для копирования и модификации и повторять процесс, пока не будет выполнено некое условие останова.
Функция evolve реализует эту процедуру:
def evolve(pc,popsize,rankfunction,maxgen=500,
mutationrate=0.1,breedingrate=0.4,pexp=0.7,pnew=0.05):
# Возвращает случайное число, отдавая предпочтение более маленьким числам
# Чем меньше значение pexp, тем больше будет доля маленьких чисел
def selectindex( ):
return int(log(random( ))/log(pexp))
# Создаем случайную исходную популяцию
population=[makerandomtree(pc) for i in range(popsize)]
for i in range(maxgen):
scores=rankfunction(population)
print scores[0][0]
if scores[0][0]==0: break
# Две наилучшие особи отбираются всегда
newpop=[scores[0][1],scores[1][1]]
# Строим следующее поколение
while len(newpop)<popsize:
if random( )>pnew:
newpop.append(mutate(
crossover(scores[selectindex( )][1],
scores[selectindex( )][1],
probswap=breedingrate),
pc,probchange=mutationrate))
else:
# Добавляем случайный узел для внесения неопределѐнности
newpop.append(makerandomtree(pc))
population=newpop
scores[0][1].display( )
return scores[0][1]
83
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 37
Эта функция создаѐт случайную исходную популяцию. Затем она выполняет не более maxgen итераций цикла, вызывая каждый раз функцию
rankfunctionдля ранжирования программ от наилучшей до наихудшей. Наилучшая программа автоматически попадает в следующее поколение без изменения.
Иногда эту стратегию называют элитизмом. Все остальные особи в следующем
поколении конструируются путѐм случайного выбора программ, расположенных близко к началу списка, и применения к ним операций мутации и скрещивания. Процесс повторяется, пока не будет получено идеальное совпадение
(расхождение с известным результатом равно 0) или не исчерпаются все итерации.
У функции есть несколько параметров, управляющих различными аспектами окружающей среды:
rankfunction - функция, применяемая для ранжирования списка программ от
наилучшей к наихудшей.
mutationrate - вероятность мутации, передаваемая функции mutate.
breedingrate - вероятность скрещивания, передаваемая функции crossover.
popsize - размер исходной популяции.
probexp - скорость убывания вероятности выбора программ с низким рангом; чем выше значение, тем более суров процесс естественного отбора, то есть
производить потомство разрешается только программам с наивысшим рангом.
probnew - вероятность включения в новую популяцию совершенно новой
случайно сгенерированной программы. Смысл параметров probexp и probnew
будет пояснѐн далее.
Функция getrankfunction возвращает функцию ранжирования для имеющегося набора данных:
def getrankfunction(dataset):
84
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
def rankfunction(population):
scores=[(scorefunction(t,dataset),t) for t in population]
scores.sort( )
return scores
return rankfunction
Итак, переходим к автоматическому созданию программы, которая будет
искать математическую формулу, соответствующую набору данных:
import gp
rf=gp.getrankfunction(gp.buildhiddenset( ))
gp.evolve(2,500,rf,mutationrate=0.2,breedingrate=0.1,pexp=0.7,pnew=0.1)
У меня получилось следующее:
18680
8048
4018
3615
2666
2478
2478
2438
2438
2420
2420
2340
2340
2215
2002
2002
2002
1309
1309
1309
1264
1264
1190
1190
1190
1190
400
200
200
85
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
200
200
200
200
200
200
200
200
200
200
200
200
200
0
subtract
multiply
p0
add
p0
6
subtract
p0
subtract
subtract
add
add
6
if
multiply
p0
0
isgreater
multiply
multiply
p1
p0
1
multiply
add
5
5
add
p0
p1
86
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
subtract
if
add
3
4
8
isgreater
p0
7
p0
if
2
p1
add
add
if
multiply
isgreater
p1
p1
if
9
4
p1
p0
isgreater
p0
p0
10
4
subtract
9
p1
p0
Числа изменяются медленно, но должны убывать, пока не достигнут 0. Интересно, что найденная функция правильна, но выглядит сложнее той, с помощью которой набор был сгенерирован (p0 – это Х, p1 – Y).
В этом задании продемонстрирована важная особенность генетического
программирования: найденные решения могут быть правильными или очень
хорошими, но из-за способа построения часто оказываются гораздо сложнее,
чем то, что мог бы придумать человек. Нередко в программе обнаруживаются
крупные участки, которые вообще не выполняют ничего полезного или вычисляют по сложной формуле одно и то же значение.
87
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Можно заставить алгоритм строить простые программы, но во многих случаях это лишь затруднит поиск хорошего решения. Гораздо лучше позволить
программам свободно эволюционировать, а потом упростить найденное хорошее решение, исключив лишние участки дерева. Иногда это можно сделать
вручную, а иногда – автоматически с помощью алгоритма отсечения ветвей.
Важность разнообразия
Функция evolve среди прочего ранжирует программы от лучших к худшим,
поэтому возникает искушение просто взять две-три программы, оказавшиеся в
начале списка, и модифицировать их для включения в новую популяцию. В
конце концов, зачем отказываться от лучшего?
Но проблема в том, что, выбирая всякий раз два лучших решения, мы быстро приходим к чрезмерно однородной популяции (если хотите, назовите это
вырождением). Все решения в ней достаточно хороши, но мало изменяются,
так как операции скрещивания порождают практически то же, что было раньше. Таким образом, мы выходим на локальный максимум – хорошее, но не идеальное состояние, в котором малые изменения не приводят к улучшению результата.
Как выясняется, комбинирование самых лучших решений с большим количеством умеренно хороших даѐт более качественные результаты. Поэтому у
функции evolve есть два дополнительных параметра, которые позволяют внести
разнообразие в процесс селекции. Уменьшая значение probexp, вы позволяете
более слабым решениям принять участие в формировании результата, так что
процесс описывается уже не фразой «выживают сильнейшие», а фразой «выживают сильнейшие и самые удачливые». Увеличивая значение probnew, вы позволяете иногда включать совершенно новые программы. Оба параметра повышают степень разнообразия эволюционного процесса, но не вмешиваются в
него чрезмерно, так как худшие программы в конечном итоге всѐ равно «вымирают».
Задание №5. Простая игра
Более интересной задачей для генетического программирования является
создание искусственного интеллекта для игры. Программы можно заставить
эволюционировать, принудив их состязаться между собой или с людьми, причѐм победителям предоставляются более высокие шансы перейти в следующее
поколение. В этом задании вы познакомитесь с симулятором для очень простой
игры «Погоня» (см. рис).
Два игрока по очереди делают ходы на небольшой расчерченной на клеточки доске. Можно перейти на любую из четырѐх соседних клеток, но размеры
доски ограничены, поэтому игрок, пытающийся выйти за еѐ пределы, пропускает ход. Цель игры – взять соперника в плен, перейдя в свой ход на ту же
клетку, где он сейчас стоит. Налагается лишь одно ограничение – нельзя два
88
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
раза подряд ходить в одном и том же направлении, иначе будет засчитано поражение. Игра очень простая, но, поскольку в ней сталкиваются интересы двух
участников, на еѐ примере можно изучить конкурентные аспекты эволюции.
Рис. 38
Функция gridgame имитирует игру двух участников. Она попеременно передаѐт каждой программе текущее положение ходящего игрока и его противника, а также последний сделанный ходящим игроком ход и возвращает в качестве результата новый ход.
Ход представляется числом от 0 до 3, обозначающим одно из четырѐх возможных направлений. Но так как случайные программы могут вернуть любое
целое число, функция должна как-то привести результат к допустимому диапазону. Для этого она возвращает остаток от деления полученного числа на 4.
Случайная программа может также создать игрока, который будет ходить по
кругу, поэтому число ходов ограничивается – после 50 ходов объявляется ничья.
defgridgame(p):
# Размер доски
max=(3,3)
# Запоминаем последний ход каждого игрока
lastmove=[-1,-1]
# Запоминаем положения игроков
location=[[randint(0,max[0]),randint(0,max[1])]]
# Располагаем второго игрока на достаточном удалении от первого
location.append([(location[0][0]+2)%4,(location[0][1]+2)%4])
# Не более 50 ходов до объявления ничьей
for o in range(50):
# Для каждого игрока
for i in range(2):
locs=location[i][:]+location[1-i][:]
locs.append(lastmove[i])
move=p[i].evaluate(locs)%4
# Если игрок два раза подряд ходит в одном направлении, ему
# засчитывается проигрыш
if lastmove[i]==move: return 1-i
lastmove[i]=move
if move==0:
89
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
location[i][0]-=1
# Доскаограничена
if location[i][0]<0: location[i][0]=0
if move==1:
location[i][0]+=1
if location[i][0]>max[0]: location[i][0]=max[0]
if move==2:
location[i][1]-=1
if location[i][1]<0: location[i][1]=0
if move==3:
location[i][1]+=1
if location[i][1]>max[1]: location[i][1]=max[1]
# Если противник захвачен в плен, вы выиграли
if location[i]==location[1-i]: return i
return -1
Программа возвращает 0, если выиграл первый игрок, 1 – если второй, и –1
– в случае ничьей. Попробуйте создать две случайные программы и заставить
их сыграть между собой:
import gp
p1=gp.makerandomtree(5)
p2=gp.makerandomtree(5)
gp.gridgame([p1,p2])
Программы ещѐ не подвергались эволюции, поэтому, скорее всего, они будут проигрывать, делая два хода подряд в одном направлении. В идеале эволюционировавшая программа должна понять, что так делать нельзя.
Круговой турнир
Следуя идеологии коллективного разума, надо было бы проверять пригодность программ в игре против людей и соответственно проводить эволюцию.
Было бы замечательно учесть при разработке «умной» программы поведение
тысяч людей. Но при большой популяции и многих поколениях пришлось бы
сыграть десятки тысяч игр, в большинстве своѐм с очень слабыми противниками. На практике это нереализуемо, поэтому сначала мы разовьѐм программы,
заставив их состязаться друг с другом на турнире.
Функция tournament принимает на входе список игроков и организует игру
каждого из них со всеми другими, отслеживая, сколько раз каждая программа
проиграла. За проигрыш программе начисляется два очка, за ничью – одно.
def tournament(pl):
# Массив для подсчета проигрышей
90
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
losses=[0 forpinpl]
# Каждый игрок встречается со всеми другими
for i in range(len(pl)):
for j in range(len(pl)):
if i==j: continue
# Ктовыиграл?
winner=gridgame([pl[i],pl[j]])
# Два очка за поражение, одно за ничью
if winner==0:
losses[j]+=2
elif winner==1:
losses[i]+=2
elif winner==-1:
losses[i]+=1
losses[i]+=1
pass
# Отсортировать и вернуть результаты
z=zip(losses,pl)
z.sort( )
return z
В конце функция сортирует результаты и возвращает их вместе с программами, которые потерпели меньше всего поражений. Именно эта информация
необходима функции evolve, чтобы организовать эволюцию, поэтому функция
tournament может использоваться в качестве аргумента evolve, следовательно, у
вас всѐ готово для выбора программы-победителя. Выполните в интерактивном
сеансе следующие команды (на это может уйти заметное время):
import gp
winner=gp.evolve(5,100,gp.tournament,maxgen=50)
Игра с человеком
Вы получили в ходе эволюции программу, которая победила всех своих кибернетических соперников. Теперь самое время сыграть с ней самому.
Класс humanplayer:
classhumanplayer:
defevaluate(self,board):
# Получить мою позицию и позиции других игроков
me=tuple(board[0:2])
others=[tuple(board[x:x+2]) for x in range(2,len(board)-1,2)]
# Нарисоватьдоску
for i in range(4):
91
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
for j in range(4):
if (i,j)==me:
print 'O',
elif (i,j) in others:
print 'X',
else:
print '.',
print
# Показать ходы, для справки
print 'Ваш последний ход %d' % board[len(board)-1]
print ' 0'
print '2 3'
print ' 1'
print 'Введитеход: ',
# Вернуть введенное пользователем число
move=int(raw_input( ))
return move
Начинайте игру в интерактивном сеансе:
import gp
gp.gridgame([winner,gp.humanplayer( )])
.O..
....
....
...X
Ваш последний ход -1
0
23
1
Введите ход:
Если программа хорошо эволюционировала, то победить еѐ будет довольно
трудно. Ваша программа почти наверняка научилась не ходить два раза подряд
в одном направлении, поскольку это влечѐт немедленную гибель, но то, в какой
мере она освоила другие стратегии, зависит от конкретного прогона evolve.
Содержание отчѐта:
1. Титульный лист.
2. Цель лабораторной работы.
3. Скриншоты результатов работы программы
Контрольные вопросы
1. Что такое генетическое программирование?
92
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Что такое генетический алгоритм?
3. Что такое мутация?
4. Что такое скрещивание?
Лабораторная работа №11. Игра «Жизнь»
Цель работы: Ознакомиться с игрой «Жизнь»
Введение
Игра "Жизнь", придуманная американским математиком Дж. Конуэем, уже
несколько десятков лет привлекает к себе пристальное внимание. Созданы десятки программ, реализующих эту игру чуть ли не на всех типах компьютеров,
написаны тысячи статей, десятки сайтов в Интернете посвящены этой игре.
Для игры "Жизнь" вам не понадобится партнѐр - в неѐ можно играть и одному. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колоний живых организмов. По этой причине "Жизнь" можно отнести к быстро развивающейся категории так называемых "моделирующих игр" - игр, которые в той или иной
степени имитируют процессы, происходящие в реальной жизни.
Основная идея игры состоит в том, чтобы, начав с какого-нибудь простого
расположения фишек (организмов), расставленных по различным клеткам доски, проследить за эволюцией исходной позиции под действием "генетических
законов" Конуэя, которые управляют рождением, гибелью и выживанием фишек. Конуэй тщательно подбирал свои правила и долго проверял их "на практике", добиваясь, чтобы они по возможности удовлетворяли трѐм условиям:
1. не должно быть ни одной исходной конфигурации, для которой существовало бы простое доказательство возможности неограниченного роста
популяции;
2. в то же время должны существовать такие начальные конфигурации, которые заведомо обладают способностью беспредельно развиваться;
3. должны существовать простые начальные конфигурации, которые в течение значительного промежутка времени растут, претерпевают разнообразные изменения и заканчивают свою эволюцию одним из следующих
трѐх способов: полностью исчезают (либо из-за перенаселѐнности, т. е.
слишком большой плотности фишек, либо, наоборот, из-за разрежѐнности фишек, образующих конфигурацию); переходят в устойчивую конфигурацию и перестают изменяться вообще или же, наконец, выходят на колебательный режим, при котором они совершают некий бесконечный
цикл превращений с определѐнным периодом.
Короче говоря, правила игры должны быть такими, чтобы поведение популяции было достаточно интересным, а главное, непредсказуемым.
93
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Генетические законы Конуэя удивительно просты. Прежде чем мы их
сформулируем, обратим внимание на то, что каждую клетку доски (которая,
вообще говоря, считается бесконечной) окружают восемь соседних клеток: четыре имеют с ней общие стороны, а четыре другие - общие вершины. Правила
игры (генетические законы) сводятся к следующему:
1. выживание. Каждая фишка, у которой имеются две или три соседние
фишки, выживает и переходит в следующее поколение;
2. гибель. Каждая фишка, у которой оказывается больше трѐх соседей, погибает, т. е. снимается с доски, из-за перенаселѐнности. Каждая фишка, вокруг которой свободны все соседние клетки или же занята только одна
клетка, погибает от одиночества;
3. рождение. Если число фишек, с которыми граничит какая-нибудь пустая
клетка, в точности равно трѐм (не больше и не меньше), то на этой клетке
происходит рождение нового "организма", т. е. следующим ходом на неѐ
ставится одна фишка.
Важно понять, что гибель и рождение всех "организмов" происходят одновременно. Вместе взятые, они образуют одно поколение или, как мы будем говорить, один "ход" в эволюции начальной конфигурации.
Начав игру, вы сразу заметите, что популяция непрестанно претерпевает
необычные, нередко очень красивые и всегда неожиданные изменения. Иногда
первоначальная колония организмов постепенно вымирает, т. е. все фишки исчезают, однако произойти это может не сразу, а лишь после того, как сменится
очень много поколений. В большинстве своѐм исходные конфигурации либо
переходят в устойчивые (последние Конуэй называет "любителями спокойной
жизни") и перестают изменяться, либо навсегда переходят в колебательный режим. При этом конфигурации, не обладавшие в начале игры симметрией, обнаруживают тенденцию к переходу в симметричные формы. Обретѐнные свойства симметрии в процессе дальнейшей эволюции не утрачиваются, а симметрия
конфигурации может лишь обогащаться.
Конуэй высказал гипотезу, согласно которой не существует ни одной начальной конфигурации, способной беспредельно расти. Иначе говоря, любая
конфигурация, состоящая из конечного числа фишек, не может перейти в конфигурацию, у которой число фишек превосходило бы некий конечный верхний
предел. Это, наверное, наиболее глубокая и самая сложная задача, возникающая в игре "Жизнь". В своѐ время Конуэй предлагал премию в 50 долларов тому, кто до конца 1970 г. первым докажет или опровергнет его гипотезу. Опровергнуть предположение Конуэя можно было бы, например, построив конфигурацию, к которой, следуя правилам игры, всѐ время приходилось бы добавлять
новые фишки. К ним можно отнести, в частности, "ружьѐ" (конфигурацию, которая через определѐнное число ходов "выстреливает" движущиеся фигуры
вроде "глайдера") или "паровоз, пускающий дым из трубы" (движущаяся конфигурация, оставляющая за собой "клубы дыма").
94
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задание
1) Нарисовать указанные на рис. 1 конфигурации. Описать их поведение
(например, записать шаг, на котором конфигурация переходит в устойчивое состояние, исчезает, возвращается в исходное состояние и т.д.). Описание сопроводить скриншотом.
Рис. 39
2) Нарисовать линию из 5 горизонтальных клеток. Описать их поведение
(например, записать шаг, на котором конфигурация переходит в устойчивое состояние, исчезает, возвращается в исходное состояние и т.д.). Описание сопроводить скриншотом.
3) Проделать п.2 для линий, состоящих из 6, 7, … 20 клеток.
4) Нарисовать конфигурацию, изображѐнную на рис.2. Сделать скриншот
финальной конфигурации.
Рис. 40
5) Поэкспериментируйте с разными конфигурациями.
Содержание отчѐта:
1. Титульный лист.
2. Цель лабораторной работы.
3. Скриншоты результатов работы программы
Контрольные вопросы:
1. Что такое игра «Жизнь»?
95
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Условия, которым должны удовлетворять правила Конуэя
3. Правила игры (генетические законы) игры.
Лабораторная работа №12. Построение графа экспертной системы
Цель работы: Научиться строить графы экспертной системы
Введение
Назначение экспертных систем заключается в решении достаточно трудных
для экспертов задач на основе накапливаемой базы знаний, отражающей опыт
работы экспертов в рассматриваемой проблемной области. Достоинство применения экспертных систем заключается в возможности принятия решений в уникальных ситуациях, для которых алгоритм заранее не известен и формируется
по исходным данным в виде цепочки рассуждений (правил принятия решений)
из базы знаний. Причѐм решение задач предполагается осуществлять в условиях неполноты, недостоверности, многозначности исходной информации и качественных оценок процессов.
Экспертная система является инструментом, усиливающим интеллектуальные способности эксперта, и может выполнять следующие роли:
консультанта для неопытных или непрофессиональных пользователей;
ассистента в связи с необходимостью анализа экспертом различных вариантов принятия решений;
партнѐра эксперта по вопросам, относящимся к источникам знаний из
смежных областей деятельности.
Экспертные системы используются во многих областях, среди которых лидирует сегмент приложений в бизнесе.
Домашнее задание студентам для подготовки к выполнения лабораторной
работы
Изучить по лекциям и учебной литературе особенности построения графов
экспертных систем.
Порядок выполнения лабораторной работы
Задание
Построить граф работы экспертной системы для выбранной предметной области (предметную область «Автосервис» использовать нельзя). Использовать
связи «И» и «ИЛИ». В графе должно содержаться минимум 15 правил различной сложности. Правил с одним условием в условной части – не более 5.
96
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание отчѐта
1.
2.
3.
4.
Титульный лист.
Цель лабораторной работы.
Граф работы экспертной системы.
Перечень правил в формате «Если… то…».
Контрольные вопросы
1. Что такое экспертная система?
2. Какие виды экспертных систем Вы знаете? Их основные особенности?
3. Назовите области применения экспертных систем.
Список литературы
1. Лутц, М. Изучаем Python, 4-е изд. [Текст]. –/ Лутц, М.; пер. с англ. – СПб:
Символ- Плюс, 2011. – 1280 с., ил.
2. Сегаран,Т. Программируем коллективный разум [Текст]. – Сегаран,Т. ;
пер. с англ. – СПб: Символ-Плюс, 2008. – 368 с., ил.
3. Сайт компании BaseGroup Labs[Электронный ресурс]: статьи. – Режим
доступа:http://basegroup.ru/library/
97
Документ
Категория
Без категории
Просмотров
266
Размер файла
1 528 Кб
Теги
интеллектуальной, технология, система, 7009
1/--страниц
Пожаловаться на содержимое документа