Всё для Учёбы — студенческий файлообменник
1 монета
docx

Студенческий документ № 058213 из НИУ МЭИ

Лекция 1. Введение в Data Mining

Термин Data Mining получил свое название из двух понятий: поиска ценной информации в большой базе данных (data) и добычи горной руды (mining). Оба процесса требуют или просеивания огромного количества сырого материала, или разумного исследования и поиска искомых ценностей.

Термин Data Mining часто переводится как добыча данных, извлечение информации, раскопка данных, интеллектуальный анализ данных, средства поиска закономерностей, извлечение знаний, анализ шаблонов, "извлечение зерен знаний из гор данных ", раскопка знаний в базах данных (БД), "промывание" данных. Понятие "обнаружение знаний в БД " (Knowledge Discovery in Databases, KDD) можно считать синонимом Data Mining.

Понятие Data Mining появилось в 1978 году и приобрело популярность с первой половины 1990-х годов. До этого обработка и анализ данных осуществлялись в рамках прикладной статистики, в основном решались задачи обработки небольших баз данных.

Data Mining - мультидисциплинарная область, возникшая и развивающаяся на базе наук: прикладная статистика, распознавание образов, искусственный интеллект, алгоритмизация, теория баз данных и др.

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

Суть и цель технологии Data Mining: предназначена для поиска в больших объемах данных неочевидных, объективных и полезных на практике закономерностей.

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

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

Традиционные методы анализа данных (статистические методы) и OLAP в основном ориентированы на проверку заранее сформулированных гипотез и на "грубый" разведочный анализ, составляющий основу оперативной аналитической обработки данных (OnLine Analytical Processing, OLAP), в то время как одно из основных положений Data Mining - поиск неочевидных закономерностей. Инструменты Data Mining могут находить такие закономерности самостоятельно и также самостоятельно строить гипотезы о взаимосвязях. Поскольку именно формулировка гипотезы относительно зависимостей является самой сложной задачей, преимущество Data Mining по сравнению с другими методами анализа является очевидным.

Основные понятия.

Родовое и видовое понятия - делимое понятие - это родовое, а его члены деления - это виды данного рода, несовместимые между собой, т.е. не пересекающиеся по своему объему (не имеющие общих элементов). Примеры деления понятий: В зависимости от источника энергии электростанции(род) делят на (виды) гидроэлектростанции, гелиоэлектростанции, геотермальные, ветровые и тепловые (к разновидностям тепловых относят АЭС).

Данные - это необработанный материал, предоставляемый поставщиками данных и используемый потребителями для формирования информации на основе данных.

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

Атрибут - свойство, характеризующее объект. Например: цвет глаз человека, температура воды и т.д. Атрибут также называют переменной, полем таблицы, измерением, характеристикой.

Генеральная совокупность (population) - вся совокупность изучаемых объектов, интересующая исследователя.

Выборка (sample) - часть генеральной совокупности, определенным способом отобранная с целью исследования и получения выводов о свойствах и характеристиках генеральной совокупности.

Параметры - числовые характеристики генеральной совокупности.

Статистики - числовые характеристики выборки.

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

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

Измерение - процесс присвоения чисел характеристикам изучаемых объектов согласно определенному правилу.

В процессе подготовки данных измеряется не сам объект, а его характеристики.

Шкала - правило, в соответствии с которым объектам присваиваются числа. Существует пять типов шкал измерений: номинальная, порядковая, интервальная, относительная и дихотомическая.

* Номинальная шкала (nominal scale) - шкала, содержащая только категории; данные в ней не могут упорядочиваться, с ними не могут быть произведены никакие арифметические действия. Номинальная шкала состоит из названий, категорий, имен для классификации и сортировки объектов или наблюдений по некоторому признаку. Пример такой шкалы: профессии, город проживания, семейное положение. Для этой шкалы применимы только такие операции: равно (=), не равно ().

* Порядковая шкала (ordinal scale) - шкала, в которой числа присваивают объектам для обозначения относительной позиции объектов, но не величины различий между ними.Шкала измерений дает возможность ранжировать значения переменных. Измерения же в порядковой шкале содержат информацию только о порядке следования величин, но не позволяют сказать "насколько одна величина больше другой", или "насколько она меньше другой".Пример такой шкалы: место (1, 2, 3-е), которое команда получила на соревнованиях, номер студента в рейтинге успеваемости (1-й, 23-й, и т.д.), при этом неизвестно, насколько один студент успешней другого, известен лишь его номер в рейтинге. Для этой шкалы применимы только такие операции: равно (=), не равно (), больше (>), меньше (), меньше (), меньше ( 2.

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

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

Правилом является логическая конструкция, представленная в виде "если : то :".

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

Рис. 4.2. Дерево решений "Выдавать ли кредит?"

Как видно, внутренние узлы дерева (возраст, наличие недвижимости, доход и образование) являются атрибутами описанной БД. Эти атрибуты называют прогнозирующими, или атрибутами расщепления (splitting attribute). Конечные узлы дерева (листы или метки класса) являются значениями зависимой категориальной переменной "выдавать" или "не выдавать" кредит.

Каждая ветвь дерева, идущая от внутреннего узла, отмечена предикатом расщепления. Последний может относиться лишь к одному атрибуту расщепления данного узла. Характерная особенность предикатов расщепления: каждая запись использует уникальный путь от корня дерева только к одному узлу-решению. Объединенная информация об атрибутах расщепления и предикатах расщепления в узле называется критерием расщепления (splitting criterion).

На рис.4.2. изображено одно из возможных деревьев решений для рассматриваемой БД. Например, критерий расщепления "Какое образование?", мог бы иметь два предиката расщепления и выглядеть иначе: образование "высшее" и "не высшее". Тогда дерево решений имело бы другой вид.

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

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

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

Преимущества деревьев решений:

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

Дерево решений позволяет понять и объяснить, почему конкретный объект относится к тому или иному классу.

Деревья решений дают возможность извлекать правила из БД на естественном языке.

Пример правила: Если Возраст > 35 и Доход > 200, то выдать кредит.

2) Генерация правил в областях, где эксперту трудно формализовать свои знания.

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

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

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

4) Масштабируемость - разработан ряд масштабируемых алгоритмов (SLIQ, SPRINT) для построения деревьев решения на сверхбольших БД. Масштабируемость здесь означает, что с ростом числа примеров или записей БД время, затрачиваемое на обучение, т.е. построение деревьев решений, растет линейно.

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

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

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

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

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

Процесс конструирования дерева решений

Задача классификации относится к стратегии обучения с учителем - индуктивного обучения. Все объекты тренировочного набора данных заранее отнесены к одному из определенных классов.

Алгоритмы конструирования деревьев решений состоят из этапов:

- "построение" или " создание " дерева (tree building) - решаются вопросы выбора критерия расщепления и остановки обучения (если это предусмотрено алгоритмом);

- " сокращение " дерева (tree pruning) - решается вопрос отсечения некоторых его ветвей.

Методика "Разделяй и властвуй" - основана на рекурсивном разбиении множества объектов из обучающей выборки на подмножества, содержащие объекты, относящиеся к одинаковым классам. Сначала выбирается независимая переменная, которая помещается в корень дерева. Из вершины строятся ветви, соответствующие всем возможным значениям выбранной независимой переменной. Множество объектов из обучающей выборки разбивается на несколько подмножеств в соответствии со значением выбранной независимой переменной. Таким образом, в каждом подмножестве будут находиться объекты, у которых значение выбранной независимой переменной будет одно и то же.

Критерий расщепления

Построение дерева решений происходит сверху вниз, т.е. является нисходящим.

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

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

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

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

Другой критерий расщепления, предложенный Брейманом и др., реализован в алгоритме CART и называется индексом Gini. При помощи этого индекса атрибут выбирается на основании расстояний между распределениями классов.

Если дано множество T, включающее примеры из n классов, индекс Gini, т.е. gini(T), определяется по формуле:

где T - текущий узел, pj - вероятность класса j в узле T, n - количество классов.

Большинство алгоритмов, которые используют данню методику, являются "жадными алгоритмами". Это значит, что если один раз переменная была выбрана и по ней было произведено разбиение, то алгоритм не может вернуться назад и выбрать другую переменную, которая дала бы лучшее разбиение. Вопрос в том, какую зависимую переменную выбрать для начального разбиения. От этого зависит качество получившегося дерева.

Другой проблемой при построении дерева является проблема остановки его разбиения - такой момент в процессе построения дерева, когда следует прекратить дальнейшие ветвления.

Методы решения:

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

2. Ограничение глубины дерева. Построение заканчивается, если достигнута заданная глубина.

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

Большое дерево не означает, что оно "подходящее"

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

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

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

Существует две возможные стратегии:

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

2 - использование набора процедур, определяющих "подходящий размер" дерева.

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

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

Сокращение дерева или отсечение ветвей

Решением проблемы слишком ветвистого дерева является его сокращение путем отсечения (pruning) некоторых ветвей.

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

Точность распознавания - отношение правильно классифицированных объектов при обучении к общему количеству объектов из обучающего множества.

Ошибка - отношение неправильно классифицированных объектов при обучении к общему количеству объектов из обучающего множества.

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

Алгоритмы

Существует большое число алгоритмов, реализующих деревья решений: CART, ID3, C4.5, CHAID, CN2, NewId, ITrule и другие. Рассмотрим некоторые из них.

Алгоритм CART

Алгоритм CART (Classification and Regression Tree, 1974-84г.) - решает задачи классификации и регрессии. Атрибуты набора данных могут иметь дискретное и числовое значение. Предназначен для построения бинарных (двоичных) деревьев решений.

Основные характеристики алгоритма CART: бинарное расщепление, критерий расщепления - индекс Gini, перекрестная проверка, принцип "вырастить дерево, а затем сократить", высокая скорость построения, обработка пропущенных значений.

Другие особенности алгоритма CART:

* функция оценки качества разбиения;

* механизм отсечения дерева;

* алгоритм обработки пропущенных значений;

* построение деревьев регрессии.

Каждый узел бинарного дерева при разбиении имеет только двух потомков, называемых дочерними ветвями. Дальнейшее разделение ветви зависит от того, много ли исходных данных описывает данная ветвь. На каждом шаге построения дерева правило, формируемое в узле, делит заданное множество примеров на две части. Правая его часть (ветвь right) - это та часть множества, в которой правило выполняется; левая (ветвь left) - та, для которой правило не выполняется.

Алгоритм ID3

Рассмотрим критерий выбора независимой переменной, от которой будет строиться дерево.

Полный набор вариантов разбиения |X| - количество независимых переменных. Рассмотрим проверку

переменой xh, которая принимает m значений ch1,ch2,...,chm. Тогда разбиение множества всех объектов обучающей выборки N по проверке переменной xh даст подмножества T1,T2,...,Tm.

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

При разделении исходного множества на более мелкие подмножества, неопределённость

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

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

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

Критерий для выбора атрибута (зависимой переменной) - Gain.

Критерий Gain рассчитывается для всех независимых переменных, затем выбирается переменная с максимальным значением Gain. Необходимо выбрать такую переменную, чтобы при разбиении по ней один из классов имел наибольшую вероятность появления. Это возможно в том случае, когда критерий Gain(X) достигает своего максимума.

Рис. 4.3. Варианты разбиения дерева

Критерий Gain рассчитывается для всех независимых переменных, затем выбирается переменная с максимальным значением Gain. Необходимо выбрать такую переменную, чтобы при разбиении по ней один из классов имел наибольшую вероятность появления. Это возможно в том случае, когда критерий Gain(X) достигает своего максимума.

В примере значение Gain для независимой переменной "Наблюдение" (перспектива) будет равно:

Gain (перспектива) = Info(I) - Info(перспектива) = 0,94-0,693=0,247 бит.

Аналогичные расчеты можно провести для других независимых переменных. В результате получаем:

Gain (наблюдение) =0,247 бит.

Gain (температура) =0,029 бит.

Gain (влажность) =0,152 бит.

Gain (ветер) =0,048 бит.

Таким образом, для первоначального разбиения лучше всего выбрать независимую переменную "Наблюдение". Далее требуется выбрать следующую переменную для разбиения. Варианты разбиения представлены на рисунке 4.4.

Аналогичным образом можно посчитать значение Gain для каждого разбиения:

Gain (температура) =0,571 бит.

Gain (влажность) =0,971 бит.

Gain (ветер) =0,02 бит.

Видно, что следующей переменной, по которой будет разбиваться подмножество T (солнечно) будет "Влажность". Дальнейшее разбиение этой ветви уже не потребуется, т.к. в получившихся подмножествах все объекты относятся только к одному классу.

Рис.4.4. Варианты 2 разбиения дерева

Если в процессе работы алгоритма получен узел, ассоциированный с пустым множеством (ни один объект не попал в данный узел), то он помечается как лист, и в качестве решения листа выбирается наиболее часто встречающийся класс у непосредственного предка данного листа.

Алгоритм C4.5 - усовершенствованный вариант алгоритма ID3.

Улучшения:

* возможность работать с числовыми атрибутами;

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

Недостаток алгоритма ID3 - он некорректно работает с атрибутами, имеющими уникальные значения для всех объектов из обучающей выборки. Алгоритм C4.5 решает эту проблему путём введения нормализации. Оценивается не количество объектов того или иного класса после разбиения, а число подмножеств и их мощность (число элементов).

Алгоритм покрытия - заключается в построении отдельной ветки дерева решений для каждого класса. Задача построения полного дерева при помощи этого алгоритма обычно не решается. На каждом этапе генерируется проверка узла дерева, который покрывает несколько объектов обучающей выборки. На каждом шаге алгоритма выбирается значение переменной, которое разделяет множество на два подмножества. Разделение должно выполняться так, чтобы все объекты класса, для которого строится дерево, принадлежали одному подмножеству. Такое разбиение производится до тех пор, пока не будет построено подмножество, содержащее только объекты одного класса. Таким же образом строятся деревья для других классов.

Разработка новых масштабируемых алгоритмов. Наиболее серьезное требование, которое предъявляется к алгоритмам конструирования деревьев решений - это масштабируемость, т.е. алгоритм должен обладать масштабируемым методом доступа к данным. Разработан ряд новых масштабируемых алгоритмов, один из них - алгоритм Sprint - масштабируемый вариант алгоритма CART, предъявляет минимальные требования к объему оперативной памяти.

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

Области применения деревьев решений

Деревья решений - отличный инструмент в системах поддержки принятия решений, интеллектуального анализа данных (data mining). В состав многих пакетов, предназначенных для интеллектуального анализа данных, уже включены методы построения деревьев решений.

Деревья решений успешно применяются для решения практических задач в областях:

* Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.

* Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например, проверка качества сварки) и т.д.

* Медицина. Диагностика различных заболеваний.

* Молекулярная биология. Анализ строения аминокислот.

Показать полностью…
170 Кб, 26 апреля 2017 в 12:10 - Россия, Москва, НИУ МЭИ, 2017 г., docx
Рекомендуемые документы в приложении