комплекс лабораторных работ. Методические указания по выполнению лабораторных работ по дисциплине Модели и алгоритмы распознавания и обработки данных
 Скачать 4.91 Mb.
|
|
1. Что такое «Редактор метаданных» в DeductorStudio? 2. Как создать новое пустое хранилище данных? 18 3. Как сделать иерархию измерений? 4. Какие типы данных могут быть у объектов хранилища? 5. Чем факт отличается от измерения? ЛАБОРАТОРНАЯ РАБОТА №3. Поиск ассициативных правил Цель работы. Изучить возможность поиска ассоциативных правил используя аналитическую платформу DEDUCTOR Теоретическая часть. В последнее время растет интерес к методам «обнаружения знаний в базах данных». Большие объемы современных баз данных вызsвают спрос на новые алгоритмы распознавания и обработки данных. Одним из распространенных аналитических методов обработки данных является аффинитивный анализ (англ: affinityanalysis), название произошедшее от английского слова affinity – близость, сходство. Метод определяет взаимные связи между событиями, происходящие совместно. Одним из применения аффинитивного анализа является анализ рыночной корзины (англ: marketbasketanalysis), цель которого – обнаружить ассоциации между различными данными, т.е. найти правила для количественного описания взаимной связи между двумя или более данными. Такие правила называются ассоциативными правилами (англ.: associationrules) и применяются в data mining. Примерами приложения ассоциативных правил могут быть следующие задачи: 1. Обнаружение наборов товаров, которые в супермаркетах часто покупаются вместе или никогда не покупаются вместе. 2. Определение доли клиентов, положительно относящихся к нововведениям в их обслуживании. 3. Определение профиля посетителя веб-ресурса. 4. Определение доли случаев, в которых новое лекарство показывает опасный побочный эффект. 19 Базовым понятием в теории ассоциативных правил является транзакция. Транзакция – некоторое множество событий, происходящих совместно. Типичной транзакцией является приобретение клиентом некоторого товара в супермаркете. В табл. 1 представлен простой пример набора транзакций. В каждой строке содержится комбинация продуктов, приобретенных за одну покупку. Таблица 1. Пример набора транзакций. № транзакции Товары 1 сливы, салат, помидоры 2 сельдерей, конфеты 3 конфеты 4 яблоки, морковь, помидоры, картофель, конфеты 5 яблоки, апельсины, салат.конфеты, помидоры 6 персики, апельсины, сельдерей, помидоры 7 фасоль, салат, помидоры 8 апельсины, салат.помидоры 9 яблоки, сливы, морковь, помидоры, лук, конфеты 10 яблоки, картофель На практике обрабатываются миллионы транзакций, в которых участвуют десятки и сотни различных продуктов. Данный пример ограничен 10 транзакциями, содержащими 13 видов продуктов, что достаточно для иллюстрации методики обнаружения ассоциативных правил. В большинстве случаев клиент приобретает не один товар, а некоторый набор товаров, называемых рыночной корзиной. Существует связь между спросом на товары, которую может обнаружить ассоциативное правило, утверждающее, что покупатель, купивший молоко, с вероятностью 75% купит и хлеб. Такие связи сущетвуют и в других областях, например в медицинской или технической диагностике, выборе профессий и т.д. 20 Анализ рыночной корзины – это анализ наборов данных для определения комбинаций товаров, связанных между собой. Иными словами, производится поиск товаров, присутствие которых в транзакции влияет на вероятность наличия других товаров или комбинаций товаров [4]. Современные кассовые аппараты в супермаркетах позволяют собирать информацию о покупках, которая может храниться в базе данных. Накопленные данные затем могут использоваться для построения систем поиска ассоциативных правил. Визуальный анализ примера (табл.1) показывает, что все четыре транзакции, в которых фигурирует салат, также включают и помидоры, и что четыре из семи транзакций, содержащих помидоры, также содержат и салат. Салат и помидоры в большинстве случаев покупаются вместе. Ассоциативные правила позволяют обнаруживать и количественно описывать такие совпадения. Ассоциативное правило состоит из двух наборов предметов, называемых условие (англ: antecedent) и следствие (англ: consequent), записываемых в виде X →Y, что читается «из X следует Y». Таким образом, ассоциативное правило формулируется в виде «Если условие, то следствие». Условие часто ограничивают содержанием только одного предмета. Правила обычно отображаются с помощью стрелок, направленных от условия к следствию, например, (помидоры) → (салат). Условие и следствие часто называются соответственно левосторонним (LHS – left-handside) и правосторонним (RHS – right-handside) компонентом ассоциативного правила. Ассоциативные правила описывают связь между наборами предметов, соответствующим условию и следствию. Эта связь характеризуется двумя показателями – поддержкой и достоверностью. Обозначим Dкак базу данных транзакций, а Nкак число транзакций в этой базе. Каждая транзакция Diпредставляет собой некоторый набор предметов. 21 Зададим, что S(англ.: support) – поддержка, C (англ.: confidence) – достоверность. Поддержка ассоциативного правила – это число транзакций, содержащих как условие, так и следствие. Например, для ассоциации A→Bможно записать: Достоверность ассоциативного правила- это мера точности правила, которая определяется как отношение количества транзакций, содержащих как условие, так и следствие, к количеству транзакций, содержащих только условие. Например, для ассоциации A→B можно записать: Если поддержка и достоверность достаточно высоки, то это позволяет с большой вероятностью утверждать, что любая будущая транзакция, которая включает условие, будет также содержать и следствие. Рассмотрим пример для вычисления поддержки и достоверности для ассоциаций из табл.1. Возьмем ассоциацию (салат) →(помидоры). Поскольку количество транзакций, содержащее как (салат), так и (помидоры), равно 4, а общее число транзакций 10, то поддержка данной ассоциации будет: S((салат)→ (помидоры)) = 4/10 = 0,4 . Поскольку Поскольку количество транзакций, содержащее только (салат) как условие, равно 4, то достоверность данной ассоциации будет: С((салат) →(помидоры)) = 4/4 = 1. Все наблюдения, содержащие салат, также содержат и помидоры, что позволяет сделать вывод о том, что данная ассоциация может рассматриваться как правило. С точки зрения интуитивного поведения такое правило вполне объяснимо, поскольку оба продукта широко используются для приготовления растительных блюд и часто покупаются вместе. 22 Рассмотрим ассоциацию (конфеты) →(помидоры), в которой содержатся, в общем-то, слабо совместимые в гастрономическом плане продукты (тот, кто планирует сделать растительное блюдо, вряд ли станет покупать конфеты, а покупатель, желающий приобрести что-нибудь к чаю, скорее всего, не станет покупать помидоры). Поддержка данной ассоциации S = 3/10 = 0,3 , а достоверностьС= 3/7 = 0,43. Таким образом, сравнительно невысокая достоверность данной ассоциации дает повод усомниться в том, что она является правилом. Аналитики могут отдавать предпочтение правилам, которые имеют только высокую поддержку или только высокую достоверность, либо, что является наиболее частым, оба эти показателя. Правила, для которых значения поддержки или достоверности превышают некоторый, заданный пользователем порог, называются сильными правилами (strongrules). Например, аналитика может интересовать, какие товары в супермаркете, покупаемые вместе, образуют ассоциации с минимальной поддержкой 20% и минимальной достоверностью 70 %. С другой стороны, при анализе с целью обнаружения мошенничеств, аналитику может потребоваться уменьшение поддержки до 1%, поскольку сравнительно небольшое число транзакций являются связанными с мошенничеством. Значимость ассоциативных правил Методики поиска ассоциативных правил обнаруживают все ассоциации, которые удовлетворяют ограничениям на поддержку и достоверность, наложенные пользователем. Это часто приводит к необходимости рассмотреть десятки и сотни тысяч ассоциаций, что делает невозможным «ручную» обработку такого большого количества данных. Очевидно, что желательно уменьшить число правил таким образом, чтобы проанализировать только наиболее значимые правила. Часто значимость связана с разностью между поддержкой правила в целом и произведением поддержки только условия и поддержки только следствия. 23 Выделяют объективные и субъективные меры значимости правил. Объективными являются такие меры, как поддержка и достоверность, которые могут применяться независимо от конкретного приложения. Субъективные меры связаны со специальной информацией, определяемой пользователем в контексте решаемой задачи. Такими субъективными мерами являются лифт (англ: lift) и левередж(от англ. leverage- плечо, рычаг). Лифт – это отношение частоты появления условия в транзакциях, которые также содержат и следствие, к частоте появления следствия в целом. Лифт (оригинальное название - интерес) определяется следующим образом: L(A→B) = C (A →B)/S(B). Значения лифта большие, чем единица показывают, что условие более часто появляется в транзакциях, содержащих и следствие, чем в остальных. Можно сказать, что лифт является обобщенной мерой связи двух предметных наборов: при значениях лифта >1 связь положительная, при 1 она отсутствует, а при значениях <1 -отрицательная. Другой мерой значимости правила является левередж(англ: leverage; предложена Г. Пятецким-Шапиро): Левередж – это разность между наблюдаемой частотой, с которой условие и следствие появляются совместно (т.е., поддержкой ассоциации), и произведением частот появления (поддержек) условия и следствия по отдельности. L(А→В) = S(A →В) - S(A)S(B). Такие меры, как лифт и левередж могут использоваться для последующего ограничения набора рассматриваемых ассоциаций путем установки порога значимости, ниже которого ассоциации отбрасываются. Генерация ассоциативных правил В DeductorStudio для решения задач ассоциации используется обработчик Ассоциативные правила. В нем реализован алгоритм apriori. Обработчик требует на входе два поля: идентификатор транзакции и элемент транзакции. 24 Например, идентификатор транзакции – это номер чека или код клиента. А элемент - это наименование товара в чеке или услуга, заказанная клиентом. Оба поля (идентификатор и элемент транзакции) должны быть дискретного вида. Пример решения конкретной задачи ассоциации из области розничной торговли: - предсказать то, какие товары покупатели могут выбрать в зависимости от того, что уже есть в их корзинах; - предложить рекламные акции типа «Каждому купившему товары A и B, товар C в подарок». Откройте программу DeductorStudio , используя ярлык на рабочем столе или через кнопку Пуск. Импортируйте данные из текстового файла transactions.txt в DeductorStudio. В файле данных имеются два столбцаТранзакция и Продукт, для которых нужно Тип поля нужно установить строковый. После импорта к данному загруженному файлу применим обработчик Ассоциативные правила. Столбец Транзакция сделаем идентификатором транзакции, а столбецПродукт – ее элементом: 25 На следующем шаге мастера настроим параметры построения ассоциативных правил, что, по сути, есть параметры алгоритма apriori: Здесь для изменения доступны следующие параметры. 26 Минимальная и максимальная поддержка в % – ограничивают пространство поиска часто встречающихся предметных наборов. Эти границы определяют множество популярных наборов, из которых и будут создаваться ассоциативные правила. Минимальная и максимальная достоверность в % – в результирующий набор попадут только те ассоциативные правила, которые удовлетворяют условиям минимальной и максимальной достоверности. Максимальная мощность искомых часто встречающихся множеств – параметр ограничивает длину k-предметного набора. Например, при установке значения 4 шаг генерации популярных наборов будет остановлен после получения множества 4-предметных наборов. В конечном итоге это позволяет избежать появления длинных ассоциативных правил, которые трудно интерпретируются. Нажмите на кнопку Пуск, что приведет к работе алгоритма поиска ассоциативных правил. По окончании его работы справа в полях появится следующая информация: Далее выбираем все доступные специализированные визуализаторы DataMining и визуализатор Таблица: 27 Все эти визуализаторы, кроме Что-если, отображают результаты работы алгоритма в различных формах. На вкладке Правила помимо самих ассоциативных правил приводятся их основные расчетные характеристики: поддержка, достоверность и лифт. 28 На вкладке Популярные наборы отображается множество найденных популярных предметных наборов в виде списка. Кнопка предлагает на выбор несколько вариантов сортировки списка, а кнопка * вызывает окно настройки фильтра множеств. Например, задав в фильтре минимальное значение поддержки 3% и отсортировав их по убыванию поддержки, получим 17 популярных наборов (на картинке изображено только 12): выявить наиболее популярные товарные наборы, состоящие из более, чем 1 предмета; На вкладке Дерево правил предлагается еще один удобный способ отображения множества ассоциативных правил, которое строится либо по условию, либо по следствию. При построении дерева правил по условию, на первом (верхнем) уровне находятся узлы с условиями, а на втором уровне – узлы со следствием. В дереве, построенном по следствию, наоборот, на первом уровне располагаются узлы со следствием. Справа от дерева расположен список правил, построенный по выбранному узлу дерева, например по правилу №5: предложить рекламные акции типа «Каждому купившему товары A и B, товар C в подарок». 29 Для каждого правила отображаются поддержка и достоверность и лифт. Если дерево построено по условию, то вверху списка отображается условие правила, а список состоит из его следствий. Тогда правила отвечают на вопрос, что будет при таком условии. Если же дерево построено по следствию, то вверху списка отображается следствие правила, а список состоит из его условий. Эти правила отвечают на вопросы, что нужно, чтобы было заданное следствие или какие товары нужно продать для того, чтобы продать товар из следствия. Сохраните сценарий под именем assosiation.ded. СОДЕРЖАНИЕ ОТЧЕТА 1. Цель работы. 2. Краткое описание хода работы. 3. Исходые данные 4. Выявленные ассоциативные правила 5. Ответы на вопросы. 6. Заключение. Вопросы: 1. Какой алгоритм генерации ассоциативных правил имеется в Deductor? 2. Какие входные поля набора данных необходимы для запуска обработчика Ассоциативные правила в Deductor? 3. Какие специализированные визуализаторы предлагаются к узлу- обработчику Ассоциативные правила? 30 Лабораторная работа №4. Распознавание образов данных (Сеть Хемминга) Цель работы. Изучение функционирования нейроподобных элементов в виде сети Хемминга. Разработка программы для разпознавания образов при преобразовании информации. Общие сведения В настоящее время дальнейшее повышение производительности компонентов связывает с системами, обладающими свойствами массового параллелизма. Одна из таких систем – это нейрокомпьютер, использующий искусственную нейросеть. Искусственная нейросеть (ИНС) – это параллельная структура, которая естественным образом реализует принцип потока данных. Обычно под ИНС понимается набор элементарных нейроподобных преобразователей информации – нейронов, соединенных друг с другом каналами обмена информацией для их совместной работы. Сформировались две ветви исследований. Первая, нейробиологическая, основывается на моделировании работы живого мозга, имея цель объяснить, каким образом в нем отображаются сложные объекты и связи между ними, как устанавливается соответствие между хранящейся и поступающей извне информацией, и другие вопросы, касающиеся функционирования мозга. Второе направление исследований направлено на решение с помощью ИНС задач переработки информации в различных областях знаний, особенно плохо формализованных, где существующие модели субъективны и неадекватны. Впечатляющие результаты использования ИНС достигнуты при распознавании образов, при построении ассоциативной памяти, при создании самообучающихся Экспертных систем, при решении оптимизационных задач большой размерности. Предложено и изучено большое количество моделей нейросетей. основными являются три типа сетей, которые соответствуют трем известным методам обучения: самоорганизации, последовательному подкреплению знаний, обучению с учителем. Теоретическая часть. Сеть Хемминга (СХ) представляет сеть с двухслойной топологией, прямой связью между слоями и с обучением с супервизором. Число нейронов N на входном слое равно размерности векторов памяти, а число нейронов в выходном слое равно числу M векторов памяти. Сеть состоит из двух слоев. Первый и второй слои имеют по m нейронов, где m – число образцов. Нейроны первого слоя имеют по n синапсов, соединенных со входами сети (образующими фиктивный нулевой слой). Нейроны второго слоя связаны между собой ингибиторными 31 (отрицательными обратными) синаптическими связями. Единственный синапс с положительной обратной связью для каждого нейрона соединен с его же аксоном. Работы сети заключается в нахождении расстояния Хэмминга от тестируемого образа до всех образцов. Расстоянием Хэмминга называется число отличающихся битов в двух бинарных векторах. Сеть должна выбрать образец с минимальным расстоянием Хэмминга до неизвестного входного сигнала, в результате чего будет активизирован только один выход сети, соответствующий этому образцу. На стадии инициализации весовым коэффициентам первого слоя и порогу активационной функции присваиваются следующие значения: , i=0...n-1, k=0...m-1 (5) T k = n / 2, k = 0...m-1 (6) Здесь x i k – i-ый элемент k-ого образца. Весовые коэффициенты тормозящих синапсов во втором слое берут равными некоторой величине 0 < < 1/m. Синапс нейрона, связанный с его же аксоном имеет вес +1. Рис.1 . Схема сети Хемминга Ход работы. Алгоритм функционирования сети Хэмминга следующий: 1. На входы сети подается неизвестный вектор X = {x i :i=0...n-1}, исходя из которого рассчитываются состояния нейронов первого слоя (верхний индекс в скобках указывает номер слоя): , j=0...m-1 (7) После этого полученными значениями инициализируются значения аксонов второго слоя: y j (2) = y j (1) , j = 0...m-1 2. Вычислить новые состояния нейронов второго слоя: 32 и значения их аксонов: Активационная функция f имеет вид порога (рис. 2б), причем величина F должна быть достаточно большой, чтобы любые возможные значения аргумента не приводили к насыщению. 3. Проверить, изменились ли выходы нейронов второго слоя за последнюю итерацию. Если да – перейди к шагу 2. Иначе – конец. Из оценки алгоритма видно, что роль первого слоя весьма условна: воспользовавшись один раз на шаге 1 значениями его весовых коэффициентов, сеть больше не обращается к нему, поэтому первый слой может быть вообще исключен из сети (заменен на матрицу весовых коэффициентов), поэтому так можно сделать в ее конкретной реализации, Сеть классифицирует произвольные бинарные или аналоговые образы ) ( 1 n x x x в один из M классов. При этом начальное значение ) 0 ( j y нейронов в выходном слое определяется двумя способами в зависимости от характера векторов памяти. Но в обоих случаях вектор стимула x с начало нормируется. Если векторы памяти являются бинарными, то ) 0 ( j y соответствует перекрытиям нормированного вектора стимула с нормированными векторами памяти. Если векторы памяти являются аналоговыми, то ) 0 ( j y выбирается в соответствии с величиной расстояния Хемминга между нормированными векторами памяти и стимула, с помощью пороговой функции F. После сформирования начальных значений нейронов выходного слоя (в этом слое все нейроны связаны между собой) выполняются итерации, про которых самодействие каждого нейрона является положительным, а вклад остальных нейронов этого слоя отрицателен. С помощью итераций выделяется тот нейрон, у которого значение ) 0 ( j y было максимальным, т. е. итерации прекращаются, когда только один из нейронов имеет ненулевое значение, а номер этого нейрона и определяет результат классификации. 4. Алгоритм программы 1. Инициализация весов (можно взять из файла “obraz.txt”). 2. Ввод распознаваемого образа. 3. Определение кодовое расстояние ] [ j d 4. Определение максимального сходство искомого образа с одним из исходных. ] [ ] [ j d porog j y 5. Вывод результата. 33 Пример результата работы сети Хемминга при разпознавании образоа цифры. 1. Введите образ: 1111 1111 0011 0011 0011 0011 Результат: 7 Введите образ: 1111 0011 1111 1111 1100 1111 2. Результат: 2 Содержание отчета 1. Цель работы. 2. Краткое описание хода работы. 3. Ответы на вопросы. 4. Листинг программы 5. Заключение. ВОПРОСЫ 1. Приведите примеры использовния сети Хемминга. |