Методические указания к выполнению ЛР8 - Разработка (анализ) данных (1033965), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Алгоритм дерева принятия решений (Майкрософт) поддерживает использование языка разметки прогнозирующих моделей (PMML) для создания моделей интеллектуального анализа данных.

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

Структура дерева решений

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

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

Дерево для каждого прогнозируемого атрибута содержит сведения, описывающие, как выбранные входные столбцы влияют на выходные данные этого прогнозируемого атрибута. Вверху каждого дерева находится узел (NODE_TYPE = 9), содержащий прогнозируемый атрибут, а затем следует ряд узлов (NODE_TYPE = 10), которые представляют входные атрибуты. Атрибут соответствует столбцу уровня вариантов или значениям столбцов вложенной таблицы, которые обычно находятся в столбце Key вложенной таблицы.

Внутренние и конечные узлы представляют условия разбиения. Дерево может разбиваться несколько раз по одному атрибуту. Например, модель TM_DecisionTree может разбиваться по атрибутам [Yearly Income] и [Number of Children], а на следующем участке дерева вновь разбиваться по атрибуту [Yearly Income].

Алгоритм дерева принятия решений (Майкрософт) также может содержать линейные регрессии во всем дереве или в его части. Если моделируемый атрибут имеет непрерывный числовой тип данных, модель может создать узел дерева регрессии (NODE_TYPE = 25) там, где связь между атрибутами может моделироваться линейно. В этом случае узел содержит формулу регрессии.

Однако если прогнозируемый атрибут имеет дискретные значения, а также если его числовые значения сегментированы или дискретизированы, то модель всегда создает дерево классификации (NODE_TYPE =2). Дерево классификации может иметь несколько ветвей или внутренних узлов дерева (NODE_TYPE =3) для каждого значения атрибута, однако не для каждого значения атрибута выполняется разбиение.

Алгоритм дерева принятия решений (Майкрософт) не допускает входные данные непрерывных типов. Поэтому, если какие-либо столбцы имеют непрерывный числовой тип данных, их значения дискретизируются. Для всех непрерывных атрибутов алгоритм самостоятельно выполняет дискретизацию в момент разбиения.

Ассоциативные правила

Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила, служит утверждение, что покупатель, приобретающий 'Хлеб', приобретет и 'Молоко' с вероятностью 72%. Первый алгоритм поиска ассоциативных правил, называвшийся AIS был разработан в 1993 году сотрудниками исследовательского центра IBM Almaden. С этой работы возрос интерес к ассоциативным правилам; на середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появлялось по несколько алгоритмов.

Впервые эта задача была предложена для поиска ассоциативных правил для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).

Анализ рыночной корзины

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

Пусть I = {i₁, i₂, i₃, …i_n} – множество (набор) товаров, называемых элементами. Пусть D – множество транзакций, где каждая транзакция T – это набор элементов из I, T I. Каждая транзакция представляет собой бинарный вектор, где t[k]=1, если i_k элемент присутствует в транзакции, иначе t[k]=0. Мы говорим, что транзакция T содержит X, некоторый набор элементов из I, если X T. Ассоциативным правилом называется импликация X Y, где X I, Y I и X Y = . Правило X Y имеет поддержку s (support), если s% транзакций из D, содержат X Y, supp(X Y) = supp (X Y). Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X Y справедливо с достоверностью (confidence) c, если c% транзакций из D, содержащих X, также содержат Y, conf(X Y) = supp(X Y)/supp(X ).

Покажем на конкретном примере: '75% транзакций, содержащих хлеб, также содержат молоко. 3% от общего числа всех транзакций содержат оба товара'. 75% – это достоверность (confidence) правила, 3% это поддержка (support), или 'Хлеб' 'Молоко' с вероятностью 75%. Другими словами, целью анализа является установление следующих зависимостей: если в транзакции встретился некоторый набор элементов X, то на основании этого можно сделать вывод о том, что другой набор элементов Y также должен появиться в этой транзакции. Установление таких зависимостей дает нам возможность находить очень простые и интуитивно понятные правила.

Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил X Y, причем поддержка и достоверность этих правил должны быть выше некоторых наперед определенных порогов, называемых соответственно минимальной поддержкой (minsupport) и минимальной достоверностью (minconfidence).

Задача нахождения ассоциативных правил разбивается на две подзадачи:

1. Нахождение всех наборов элементов, которые удовлетворяют порогу minsupport. Такие наборы элементов называются часто встречающимися.

2. Генерация правил из наборов элементов, найденных согласно п.1. с достоверностью, удовлетворяющей порогу minconfidence.

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

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

Свойство анти-монотонности

Выявление часто встречающихся наборов элементов – операция, требующая много вычислительных ресурсов и, соответственно, времени. Примитивный подход к решению данной задачи – простой перебор всех возможных наборов элементов. Это потребует O(2^|I|) операций, где |I| – количество элементов. Поэтому используют одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора {Хлеб, Масло, Молоко} будет всегда меньше или равна поддержке 2-элементных наборов {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}. Дело в том, что любая транзакция, содержащая {Хлеб, Масло, Молоко}, также должна содержать {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}, причем обратное не верно. Это свойство носит название анти-монотонности и служит для снижения размерности пространства поиска.

Свойству анти-монотонности можно дать и другую формулировку: с ростом размера набора элементов поддержка уменьшается, либо остается такой же. Из всего вышесказанного следует, что любой k-элементный набор будет часто встречающимся тогда и только тогда, когда все его (k-1)-элементные подмножества будут часто встречающимися. Все возможные наборы элементов из I можно представить в виде решетки, начинающейся с пустого множества, затем на 1 уровне 1-элементные наборы, на 2-м – 2-элементные и т.д. На k уровне представлены k-элементные наборы, связанные со всеми своими (k-1)-элементными подмножествами. Рассмотрим Рис.1, иллюстрирующий набор элементов I – {A, B, C, D}. Предположим, что набор из элементов {A, B} имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с {A, B}, отмечена желтым фоном. Использование этой эвристики позволяет существенно сократить пространство поиска.

Характеристики

Список файлов лабораторной работы