Предварительные знания
 Скачать 3.17 Mb.
|
|
PARTITION алгоритм (A. Savasere, E. Omiecinski and S. Navathe, 1995 год). Этот алгоритм разбиения (разделения) заключается в сканировании транзакционной базы данных путем разделения ее на непересекающиеся разделы, каждый из которых может уместиться в оперативной памяти [65]. На первом шаге в каждом из разделов при помощи алгоритма Apriori определяются "локальные" часто встречающиеся наборы данных. На втором подсчитывается поддержка каждого такого набора относительно всей базы данных. Таким образом, на втором этапе определяется множество всех потенциально встречающихся наборов данных. 177 Алгоритм DIC, Dynamic Itemset Counting (S. Brin R. Motwani, J. Ullman and S. Tsur, 1997 год). Алгоритм разбивает базу данных на несколько блоков, каждый из которых отмечается так называемыми "начальными точками" (start point), и затем циклически сканирует базу данных [64]. Пример решения задачи поиска ассоциативных правил Дана транзакционная база данных, необходимо найти наиболее часто встречающиеся наборы товаров и набор ассоциативных правил с определенными границами значений поддержки и доверия. Рассмотрим процесс построения ассоциативных правил в аналитическом пакете Deductor. Транзакционная база данных, которая содержит в каждой записи номер чека и товар, приобретенный по этому чеку, имеет формат MS Excel. Для начала импортируем данные из файла MS Excel в среду Deductor, этот процесс аналогичен тому, что был рассмотрен в лекции о нейронных сетях. Единственное отличие - в назначении столбцов. Для номера транзакции (обычно в базе данных - это поле "номер чека") указываем тип "идентификатор транзакции (ID)", а для наименований товара - тип "элемент". Результат импорта базы данных из файла MS Excel в среду Deductor видим на рис. 15.2 . На рисунке приведен фрагмент базы данных, которая содержит более 140 записей. Рис. 15.2. Транзакционная база данных, импортированная в Deductor из файла MS Excel 178 Далее вызываем мастер обработки и выбираем метод "Ассоциативные правила". На втором шаге мастера проверяем назначения исходных столбцов данных, они должны иметь тип "ID" и "элемент". На третьем шаге, проиллюстрированном на рис. 15.3 , необходимо настроить параметры поиска правил, т.е. установить минимальные и максимальные характеристики поддержки и достоверности. Это наиболее "ответственный" момент формирования набора правил, о важности выбора границ значений поддержки и достоверности уже говорилось в начале лекции. Выбор можно сделать на основе каких-либо соображений, имеющегося опыта анализа подобных данных, интуиции или же определить в ходе экспериментов. Рис. 15.3. Настройка параметров построения ассоциативных правил Мы установим такие границы для параметров поиска: минимальный и максимальный уровень поддержки равны 20% и 60% соответственно, минимальный и максимальный уровень значения достоверности равны 40% и 90% соответственно. Эти значения были выявлены в ходе проведения нескольких экспериментов, и оказалось, что именно при таких значениях формируется требуемый набор правил. При указании некоторых значений, например, уровня поддержки от 30% до 50%, набор правил не формируется, поскольку ни одно правило по параметрам поддержки не входит в этот интервал. На следующем шаге мастера запускается процесс поиска ассоциативных правил. В результате видим информацию о количестве множеств и найденных правил в виде гистограммы распределения часто встречающихся множеств по их мощности. Данный процесс проиллюстрирован на рис. 15.4 179 Рис. 15.4. Процесс построения ассоциативных правил Здесь мы видим, что количество сформированных множеств равно тринадцати - это популярные наборы, количество сформированных правил - пятнадцать. На следующем шаге для просмотра полученных результатов предлагается выбрать визуализаторы из списка; мы выберем такие: "Популярные наборы", "Правила", "Дерево правил", "Что-если". Рассмотрим, что они из себя представляют. Визуализатор "Популярные наборы". Популярные наборы или часто встречающиеся наборы - это наборы, состоящие из одного или нескольких товаров, которые в транзакциях наиболее часто встречаются одновременно. Характеристикой, насколько часто набор встречается в анализируемом наборе данных, является поддержка. Популярные наборы нашего набора данных, найденные при заданных параметрах, приведены в таблице 15.3 . Есть возможность отсортировать данную таблицу по разным ее характеристикам. Для определения наиболее популярных товаров и их наборов удобно отсортировать ее по уровню поддержки. Таким образом, мы видим, что наибольшей популярностью пользуются такие товары: хлеб и булки, масло, соки. N Множество Поддержка % Кол-во 6 ХЛЕБ И БУЛКИ 54,55 24 180 3 МАСЛО 52,27 23 5 СОКИ 50,00 22 10 МАСЛО И ХЛЕБ И БУЛКИ 45,45 20 4 МОЛОКО 43,18 19 2 КЕФИР 31,82 14 1 ЙОГУРТЫ 31,82 14 12 СОКИ И ХЛЕБ И БУЛКИ 22,73 10 11 МОЛОКО И ХЛЕБ И БУЛКИ 22,73 10 8 МАСЛО И МОЛОКО 22,73 10 7 ЙОГУРТЫ И КЕФИР 22,73 10 13 МАСЛО И МОЛОКО И ХЛЕБ И БУЛКИ 20,45 9 9 МАСЛО И СОКИ 20,45 9 Визуализатор "Правила" Правила в данном визуализаторе размещены в виде списка. Каждое правило, представленное как "условие-следствие", характеризуется значением поддержки в абсолютном и процентном выражении, а также достоверностью. Таким образом, аналитик видит поведение покупателей, описанное в виде набора правил. Набор правил для решаемой нами задачи приведен в таблице 15.4 . Например, первое правило говорит о том, что если покупатель купил йогурт, то с достоверностью или вероятностью 71% он купит также кефир. Эта информация полезна с различных точек зрения. Она, например, помогает решить задачу расположения товаров в магазине. N Условие Следствие Поддержка % Кол-во Достоверность, % 1 ЙОГУРТЫ КЕФИР 22,73 10 71,43 2 КЕФИР ЙОГУРТЫ 22,73 10 71,43 3 МАСЛО МОЛОКО 22,73 10 43,48 4 МОЛОКО МАСЛО 22,73 10 52,63 5 СОКИ МАСЛО 20,45 9 40,91 181 6 МАСЛО ХЛЕБ И БУЛКИ 45,45 20 86,96 7 ХЛЕБ И БУЛКИ МАСЛО 45,45 20 83,33 8 МОЛОКО ХЛЕБ И БУЛКИ 22,73 10 52,63 9 ХЛЕБ И БУЛКИ МОЛОКО 22,73 10 41,67 10 СОКИ ХЛЕБ И БУЛКИ 22,73 10 45,45 11 ХЛЕБ И БУЛКИ СОКИ 22,73 10 41,67 12 МАСЛО И МОЛОКО ХЛЕБ И БУЛКИ 20,45 9 90,00 13 МАСЛО И ХЛЕБ И БУЛКИ МОЛОКО 20,45 9 45,00 14 МОЛОКО И ХЛЕБ И БУЛКИ МАСЛО 20,45 9 90,00 15 МОЛОКО МАСЛО И ХЛЕБ И БУЛКИ 20,45 9 47,37 При большом количестве найденных правил и широком ассортименте товаров анализировать полученные правила достаточно сложно. Для удобства анализа таких наборов правил предлагаются визуализаторы "Дерево правил" и "Что-если". Визуализатор "Дерево правил" представляет собой двухуровневое дерево, которое может быть построено по двум критериям: по условию и по следствию. Если дерево построено по условию, то вверху списка отображается условие правила, а список, прилагающийся к данному условию, состоит из его следствий. При выборе определенного условия, в правой части визуализатора отображаются следствия условия, уровень поддержки и достоверности. В случае построения дерева по следствию, вверху списка отображается следствие правила, а список состоит из его условий. При выборе определенного следствия, в правой части визуализатора мы видим условия этого правила с указанием уровня поддержки и достоверности. Визуализатор "что-если" удобен, если нам необходимо ответить на вопрос, какие следствия могут получиться из данного условия. Например, выбрав условие "МОЛОКО", в левой части экрана получаем три следствия "МАСЛО", "ХЛЕБ И БУЛКИ", "МАСЛО И ХЛЕБ И БУЛКИ", для которых указаны уровень поддержки и достоверности. Этот визуализатор представлен на рис. 15.5 182 Рис. 15.5. Визуализатор "Что-если" Рассмотренный пример поиска ассоциативных правил является типичной иллюстрацией задачи анализа покупательской корзины. В результате ее решения определяются часто встречающиеся наборы товаров, а также наборы товаров, совместно приобретаемые покупателями. Найденные правила могут быть использованы для решения различных задач, в частности для размещения товаров на прилавках магазинов, предоставления скидок на пары товаров для повышения объема продаж и, следовательно, прибыли и других задач. 183 Способы визуального представления данных. Методы визуализации "Говорят, один рисунок стоит тысячи слов, и это действительно так, но при условии, что рисунок хороший." Боумена [65] С возрастанием количества накапливаемых данных, даже при использовании сколь угодно мощных и разносторонних алгоритмов Data Mining, становится все сложнее "переваривать" и интерпретировать полученные результаты. А, как известно, одно из положений Data Mining - поиск практически полезных закономерностей. Закономерность может стать практически полезной, только если ее можно осмыслить и понять. В 1987 году по инициативе ACM SIGGRAPH IEEE Computer Society Technical Committee of Computer Graphics, в связи с необходимостью использования новых методов, средств и технологий данных, были сформулированы соответствующие задачи направления визуализации. К способам визуального или графического представления данных относят графики, диаграммы, таблицы, отчеты, списки, структурные схемы, карты и т.д. Визуализация традиционно рассматривалась как вспомогательное средство при анализе данных, однако сейчас все больше исследований говорит о ее самостоятельной роли. Традиционные методы визуализации могут находить следующее применение: • представлять пользователю информацию в наглядном виде; • компактно описывать закономерности, присущие исходному набору данных; • снижать размерность или сжимать информацию; • восстанавливать пробелы в наборе данных; • находить шумы и выбросы в наборе данных. Визуализация инструментов Data Mining Каждый из алгоритмов Data Mining использует определенный подход к визуализации. В предыдущих лекциях мы рассмотрели ряд методов Data Mining. В ходе использования каждого из методов, а точнее, его программной реализации, мы получали некие визуализаторы, при помощи которых нам удавалось интерпретировать результаты, полученные в результате работы соответствующих методов и алгоритмов. • Для деревьев решений это визуализатор дерева решений, список правил, таблица сопряженности. • Для нейронных сетей в зависимости от инструмента это может быть топология сети, график изменения величины ошибки, демонстрирующий процесс обучения. • Для карт Кохонена: карты входов, выходов, другие специфические карты. • Для линейной регрессии в качестве визуализатора выступает линия регрессии. • Для кластеризации: дендрограммы, диаграммы рассеивания. Диаграммы и графики рассеивания часто используются для оценки качества работы того или иного метода. 184 Все эти способы визуального представления или отображения данных могут выполнять одну из функций: • являются иллюстрацией построения модели (например, представление структуры (графа) нейронной сети); • помогают интерпретировать полученный результат; • являются средством оценки качества построенной модели; • сочетают перечисленные выше функции (дерево решений, дендрограмма). Визуализация Data Mining моделей Первая функция (иллюстрация построения модели), по сути, является визуализацией Data Mining модели. Существует много различных способов представления моделей, но графическое ее представление дает пользователю максимальную "ценность". Пользователь, в большинстве случаев, не является специалистом в моделировании, чаще всего он эксперт в своей предметной области. Поэтому модель Data Mining должна быть представлена на наиболее естественном для него языке или, хотя бы, содержать минимальное количество различных математических и технических элементов. Таким образом, доступность является одной из основных характеристик модели Data Mining. Несмотря на это, существует и такой распространенный и наиболее простой способ представления модели, как "черный ящик". В этом случае пользователь не понимает поведения той модели, которой пользуется. Однако, несмотря на непонимание, он получает результат - выявленные закономерности. Классическим примером такой модели является модель нейронной сети. Другой способ представления модели - представление ее в интуитивном, понятном виде. В этом случае пользователь действительно может понимать то, что происходит "внутри" модели. Таким образом, можно обеспечить его непосредственное участие в процессе. Такие модели обеспечивают пользователю возможность обсуждать ее логику с коллегами, клиентами и другими пользователями, или объяснять ее. Понимание модели ведет к пониманию ее содержания. В результате понимания возрастает доверие к модели. Классическим примером является дерево решений. Построенное дерево решений действительно улучшает понимание модели, т.е. используемого инструмента Data Mining. Кроме понимания, такие модели обеспечивают пользователя возможностью взаимодействовать с моделью, задавать ей вопросы и получать ответы. Примером такого взаимодействия является средство "что, если". При помощи диалога "система- пользователь" пользователь может получить понимание модели. Теперь перейдем к функциям, которые помогают интерпретировать и оценить результаты построения Data Mining моделей. Это всевозможные графики, диаграммы, таблицы, списки и т.д. Примерами средств визуализации, при помощи которых можно оценить качество модели, являются диаграмма рассеивания, таблица сопряженности, график изменения величины ошибки. 185 Диаграмма рассеивания представляет собой график отклонения значений, прогнозируемых при помощи модели, от реальных. Эти диаграммы используют для непрерывных величин. Визуальная оценка качества построенной модели возможна только по окончанию процесса построения модели. Таблица сопряженности используется для оценки результатов классификации. Такие таблицы применяются для различных методов классификации. Они уже использовались нами в предыдущих лекциях. Оценка качества построенной модели возможно только по окончанию процесса построения модели. График изменения величины ошибки. График демонстрирует изменение величины ошибки в процессе работы модели. Например, в процессе работы нейронных сетей пользователь может наблюдать за изменением ошибки на обучающем и тестовом множествах и остановить обучение для недопущения "переобучения" сети. Здесь оценка качества модели и его изменения может оцениваться непосредственно в процессе построения модели. Примерами средств визуализации, которые помогают интерпретировать результат, являются: линия тренда в линейной регрессии, карты Кохонена, диаграмма рассеивания в кластерном анализе. Методы визуализации Методы визуализации, в зависимости от количества используемых измерений, принято классифицировать на две группы [22]: • представление данных в одном, двух и трех измерениях; • представление данных в четырех и более измерениях. Представление данных в одном, двух и трех измерениях К этой группе методов относятся хорошо известные способы отображения информации, которые доступны для восприятия человеческим воображением. Практически любой современный инструмент Data Mining включает способы визуального представления из этой группы. В соответствии с количеством измерений представления это могут быть следующие способы: • одномерное (univariate) измерение, или 1-D; • двумерное (bivariate) измерение, или 2-D; • трехмерное или проекционное (projection) измерение, или 3-D. Следует заметить, что наиболее естественно человеческий глаз воспринимает двухмерные представления информации. При использовании двух- и трехмерного представления информации пользователь имеет возможность увидеть закономерности набора данных: • его кластерную структуру и распределение объектов на классы (например, на диаграмме рассеивания); 186 • топологические особенности; • наличие трендов; • информацию о взаимном расположении данных; • существование других зависимостей, присущих исследуемому набору данных. Если набор данных имеет более трех измерений, то возможны такие варианты: • использование многомерных методов представления информации (они рассмотрены ниже); • снижение размерности до одно-, двух- или трехмерного представления. Существуют различные способы снижения размерности, один из них - факторный анализ - был рассмотрен в одной из предыдущих лекций. Для снижения размерности и одновременного визуального представления информации на двумерной карте используются самоорганизующиеся карты Кохонена. Представление данных в 4 + измерениях Представления информации в четырехмерном и более измерениях недоступны для человеческого восприятия. Однако разработаны специальные методы для возможности отображения и восприятия человеком такой информации. Наиболее известные способы многомерного представления информации: • параллельные координаты; • "лица Чернова"; • лепестковые диаграммы. Параллельные координаты В параллельных координатах переменные кодируются по горизонтали, вертикальная линия определяет значение переменной. Пример набора данных, представленного в декартовых координатах и параллельных координатах, дан на рис. 16.1 [22]. Этот метод представления многомерных данных был изобретен Альфредом Инселбергом (Alfred Inselberg ) в 1985 году. 187 Рис. 16.1. Набор данных в декартовых координатах и в параллельных координатах "Лица Чернова" Основная идея представления информации в "лицах Чернова" состоит в кодировании значений различных переменных в характеристиках или чертах человеческого лица [66]. Пример такого "лица" приведен на рис.16.2 Рис. 16.2. "Лицо Чернова" Для каждого наблюдения рисуется отдельное "лицо". На каждом "лице" относительные значения переменных представлены как формы и размеры отдельных черт лица (например, длина и ширина носа, размер глаз, размер зрачка, угол между бровями). Анализ информации при помощи такого способа отображения основан на способности человека интуитивно находить сходства и различия в чертах лица. 188 |