Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Принцип применения метода дисперсионного анализа



Сначала формулируется нулевая гипотеза, то есть предполагается, что исследуемые факторы не оказывают никакого влияния на значения результативного признака и полученные различия случайны.

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

Если эта вероятность мала*, то мы отвергаем нулевую гипотезу и заключаем, что результаты исследования статистически значимы. Это еще не означает, что доказано действие именно изучаемых факторов (это вопрос, прежде всего, планирования исследования), но все же маловероятно, что результат обусловлен случайностью.
__________________________________
* Максимальную приемлемую вероятность отвергнуть верную нулевую гипотезу называют уровнем значимости и обозначают α = 0,05.

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

Doбщ. = Dфакт + D ост.,

Doбщ. - общая дисперсия наблюдаемых значений (вариант), характеризуется разбросом вариант от общего среднего. Измеряет вариацию признака во всей совокупности под влиянием всех факторов, обусловивших эту вариацию. Общее разнообразие складывается из межгруппового и внутригруппового;

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

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

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

Классический дисперсионный анализ проводится по следующим этапам:

Построение дисперсионного комплекса.



Вычисление средних квадратов отклонений.

Вычисление дисперсии.

Сравнение факторной и остаточной дисперсий.

Оценка результатов с помощью теоретических значений распределения Фишера-Снедекора (приложение N 1).

 

8. Основная цель

Термин кластерный анализ (впервые ввел Tryon, 1939) в действительности включает в себя набор различных алгоритмов классификации. Общий вопрос, задаваемый исследователями во многих областях, состоит в том, как организовать наблюдаемые данные в наглядные структуры, т.е. развернуть таксономии. Например, биологи ставят цель разбить животных на различные виды, чтобы содержательно описать различия между ними. В соответствии с современной системой, принятой в биологии, человек принадлежит к приматам, млекопитающим, амниотам, позвоночным и животным. Заметьте, что в этой классификации, чем выше уровень агрегации, тем меньше сходства между членами в соответствующем классе. Человек имеет больше сходства с другими приматами (т.е. с обезьянами), чем с "отдаленными" членами семейства млекопитающих (например, собаками) и т.д. В последующих разделах будут рассмотрены общие методы кластерного анализа, см. Объединение (древовидная кластеризация), Двувходовое объединение и Метод K средних.

Проверка статистической значимости

Заметим, что предыдущие рассуждения ссылаются на алгоритмы кластеризации, но ничего не упоминают о проверке статистической значимости. Фактически, кластерный анализ является не столько обычным статистическим методом, сколько "набором" различных алгоритмов "распределения объектов по кластерам". Существует точка зрения, что в отличие от многих других статистических процедур, методы кластерного анализа используются в большинстве случаев тогда, когда вы не имеете каких-либо априорных гипотез относительно классов, но все еще находитесь в описательной стадии исследования. Следует понимать, что кластерный анализ определяет "наиболее возможно значимое решение". Поэтому проверка статистической значимости в действительности здесь неприменима, даже в случаях, когда известны p-уровни (как, например, в методе K средних).



Области применения

Техника кластеризации применяется в самых разнообразных областях. Хартиган (Hartigan, 1975) дал прекрасный обзор многих опубликованных исследований, содержащих результаты, полученные методами кластерного анализа. Например, в области медицины кластеризация заболеваний, лечения заболеваний или симптомов заболеваний приводит к широко используемым таксономиям. В области психиатрии правильная диагностика кластеров симптомов, таких как паранойя, шизофрения и т.д., является решающей для успешной терапии. В археологии с помощью кластерного анализа исследователи пытаются установить таксономии каменных орудий, похоронных объектов и т.д. Известны широкие применения кластерного анализа в маркетинговых исследованиях. В общем, всякий раз, когда необходимо классифицировать "горы" информации к пригодным для дальнейшей обработки группам, кластерный анализ оказывается весьма полезным и эффективным.

В начало

 

Объединение (древовидная кластеризация)

Иерархическое дерево

Меры расстояния

Правила объединения или связи

Общая логика

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

Иерархическое дерево

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

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

Меры расстояния

Объединение или метод древовидной кластеризации используется при формировании кластеров несходства или расстояния между объектами. Эти расстояния могут определяться в одномерном или многомерном пространстве. Например, если вы должны кластеризовать типы еды в кафе, то можете принять во внимание количество содержащихся в ней калорий, цену, субъективную оценку вкуса и т.д. Наиболее прямой путь вычисления расстояний между объектами в многомерном пространстве состоит в вычислении евклидовых расстояний. Если вы имеете двух- или трёхмерное пространство, то эта мера является реальным геометрическим расстоянием между объектами в пространстве (как будто расстояния между объектами измерены рулеткой). Однако алгоритм объединения не "заботится" о том, являются ли "предоставленные" для этого расстояния настоящими или некоторыми другими производными мерами расстояния, что более значимо для исследователя; и задачей исследователей является подобрать правильный метод для специфических применений.

Евклидово расстояние.Это, по-видимому, наиболее общий тип расстояния. Оно попросту является геометрическим расстоянием в многомерном пространстве и вычисляется следующим образом:

расстояние(x,y) = { i (xi - yi)2 }1/2

Заметим, что евклидово расстояние (и его квадрат) вычисляется по исходным, а не по стандартизованным данным. Это обычный способ его вычисления, который имеет определенные преимущества (например, расстояние между двумя объектами не изменяется при введении в анализ нового объекта, который может оказаться выбросом). Тем не менее, на расстояния могут сильно влиять различия между осями, по координатам которых вычисляются эти расстояния. К примеру, если одна из осей измерена в сантиметрах, а вы потом переведете ее в миллиметры (умножая значения на 10), то окончательное евклидово расстояние (или квадрат евклидова расстояния), вычисляемое по координатам, сильно изменится, и, как следствие, результаты кластерного анализа могут сильно отличаться от предыдущих.

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

расстояние(x,y) = i (xi - yi)2

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

расстояние(x,y) = i |xi - yi|

Расстояние Чебышева.Это расстояние может оказаться полезным, когда желают определить два объекта как "различные", если они различаются по какой-либо одной координате (каким-либо одним измерением). Расстояние Чебышева вычисляется по формуле:

расстояние(x,y) = Максимум|xi - yi|

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

расстояние(x,y) = ( i |xi - yi|p)1/r

где r и p - параметры, определяемые пользователем. Несколько примеров вычислений могут показать, как "работает" эта мера. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра - r и p, равны двум, то это расстояние совпадает с расстоянием Евклида.

Процент несогласия.Эта мера используется в тех случаях, когда данные являются категориальными. Это расстояние вычисляется по формуле:

расстояние(x,y) = (Количество xi yi)/ i

Правила объединения или связи

На первом шаге, когда каждый объект представляет собой отдельный кластер, расстояния между этими объектами определяются выбранной мерой. Однако когда связываются вместе несколько объектов, возникает вопрос, как следует определить расстояния между кластерами? Другими словами, необходимо правило объединения или связи для двух кластеров. Здесь имеются различные возможности: например, вы можете связать два кластера вместе, когда любые два объекта в двух кластерах ближе друг к другу, чем соответствующее расстояние связи. Другими словами, вы используете "правило ближайшего соседа" для определения расстояния между кластерами; этот метод называется методом одиночной связи. Это правило строит "волокнистые" кластеры, т.е. кластеры, "сцепленные вместе" только отдельными элементами, случайно оказавшимися ближе остальных друг к другу. Как альтернативу вы можете использовать соседей в кластерах, которые находятся дальше всех остальных пар объектов друг от друга. Этот метод называется метод полной связи. Существует также множество других методов объединения кластеров, подобных тем, что были рассмотрены.

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

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

Невзвешенное попарное среднее.В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты в действительности формируют различные "рощи", однако он работает одинаково хорошо и в случаях протяженных ("цепочного" типа) кластеров. Отметим, что в своей книге Снит и Сокэл (Sneath, Sokal, 1973) вводят аббревиатуру UPGMA для ссылки на этот метод, как на метод невзвешенного попарного арифметического среднего - unweighted pair-group method using arithmetic averages.

Взвешенное попарное среднее.Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому предлагаемый метод должен быть использован (скорее даже, чем предыдущий), когда предполагаются неравные размеры кластеров. В книге Снита и Сокэла (Sneath, Sokal, 1973) вводится аббревиатура WPGMA для ссылки на этот метод, как на метод взвешенного попарного арифметического среднего - weighted pair-group method using arithmetic averages.

Невзвешенный центроидный метод.В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести. Снит и Сокэл (Sneath and Sokal (1973)) используют аббревиатуру UPGMC для ссылки на этот метод, как на метод невзвешенного попарного центроидного усреднения - unweighted pair-group method using the centroid average.

Взвешенный центроидный метод (медиана).тот метод идентичен предыдущему, за исключением того, что при вычислениях используются веса для учёта разницы между размерами кластеров (т.е. числами объектов в них). Поэтому, если имеются (или подозреваются) значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего. Снит и Сокэл (Sneath, Sokal 1973) использовали аббревиатуру WPGMC для ссылок на него, как на метод невзвешенного попарного центроидного усреднения - weighted pair-group method using the centroid average.

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

 

9. МНОГОМЕРНАЯ МОДЕЛЬ ДАННЫХ

 

"Многомерный взгляд на данные наиболее характерен для пользователя, занимающегося анализом данных" - это утверждение сегодня стало уже почти аксиомой. Однако, у, впервые прочитавшего это утверждение, возникают вопросы: что такое многомерное представление? откуда появляется многомерность в трехмерном мире? чем многомерность отличается и чем она лучше ставшего уже привычным реляционного представления? откуда могут появиться люди, мыслящие в четырех и более измерениях, и как это им удается? Однако, пользователь, занимающийся анализом, сам не замечая того, действительно имеет многомерность мышления. Весь вопрос в том, что понимать под измерением. Достаточно очевидно, что даже при небольших объемах данных отчет, представленный в виде двухмерной таблицы (Модели компьютеров по оси Y и Время по оси X), нагляднее и информативнее отчета с реляционной построчной формой организации.
Реляционная модель представления данных Многомерная модель представления данных
Модель Месяц Объем   Июнь Июль Август
Celeron Июнь "Celeron"
Celeron Июль "Pentium" -
Celeron Август "Athlon" - -
Pentium Июнь        
Pentium Июль        
Athlon Июль        

Но в любом магазине имеется не три модели товара, а значительно больше (например, 30), и анализ проводится не за три, а за 12 месяцев. В случае построчного (реляционного) представления будет получен отчет в 360 строк (30х12), который займет не менее 5-6 страниц. В случае же многомерного (в данном случае двухмерного) представления будет получена достаточно компактная таблица 12 на 30, которая уместится на одной странице и которую, даже при таком объеме данных, можно реально оценивать и анализировать.

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

При многомерном представление и описании структур данных основными понятиями, с которыми оперирует пользователь и проектировщик в многомерной модели данных, являются:

Измерение (Dimension)

Это множество однотипных данных, образующих одну из граней гиперкуба. Измерения играют роль индексов, используемых для идентификации конкретных значений (Показателей), находящихся в ячейках гиперкуба. Наиболее часто используемые в анализе измерения:

временные -Дни, Месяцы, Кварталы, Годы;

географических- Города, Районы, Регионы, Страны и т.д. В многомерной модели данных

Ячейка (Cell)

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

Разреженность (Sparse)

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

Показатель (Measure)

Иногда вместо термина "Ячейка" используется термин показатель (Measure) - это поле (обычно числовое), значения которого однозначно определяются фиксированным набором измерений.

10.OLAP (от англ. OnLine Analytical Processing — оперативная аналитическая обработка данных, также: аналитическая обработка данных в реальном времени, интерактивная аналитическая обработка данных) — подход к аналитической обработке данных, базирующийся на их многомерномиерархическом представлении, являющийся частью более широкой области информационных технологий — бизнес-аналитики (BI).

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

 

OLAP (англ. on-line analytical processing) – совокупность методов динамической обработки многомерных запросов в аналитических базах данных. Такие источники данных обычно имеют довольно большой объем, и в применяемых для их обработки средствах одним из наиболее важных требований является высокая скорость. В реляционных БД информация хранится в отдельных таблицах, которые хорошо нормализованы. Но сложные многотабличные запросы в них выполняются довольно медленно. Значительно лучшие показатели по скорости обработки в OLAP-системах достигаются за счет особенности структуры хранения данных. Вся информация четко организована, и применяются два типа хранилищ данных: измерения (содержат справочники, разделенные по категориям, например, точки продаж, клиенты, сотрудники, услуги и т.д.) и факты(характеризуют взаимодействие элементов различных измерений, например, 3 марта 2010 г. продавец A оказал услугу клиенту Б в магазине В на сумму Г денежных единиц). Для вычисления результатов в аналитическом кубе применяются меры. Меры представляют собой совокупности фактов, агрегированных по соответствующим выбранным измерениям и их элементам. Благодаря этим особенностям на сложные запросы с многомерными данными затрачивается гораздо меньшее время, чем в реляционных источниках.

Одним из основных вендоров OLAP-систем является корпорация Microsoft. Рассмотрим реализацию принципов OLAP на практических примерах создания аналитического куба в приложениях Microsoft SQL Server Business Intelligence Development Studio (BIDS) и Microsoft Office PerformancePoint Server Planning Business Modeler (PPS) и ознакомимся с возможностями визуального представления многомерных данных в виде графиков, диаграмм и таблиц.

Например, в BIDS необходимо создать OLAP-куб по данным о страховой компании, ее работниках, партнерах (клиентах) и точках продаж. Допустим предположение, что компания предоставляет один вид услуг, поэтому измерение услуг не понадобится.

Сначала определим измерения. С деятельности компании связаны следующие сущности (категории данных):

Точки продаж
- Сотрудники
- Партнеры


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

 

 

11. Data Mining (рус. добыча данных, интеллектуальный анализ данных, глубинный анализ данных) — собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Термин введён Григорием Пятецким-Шапиро в 1989 году[1][2][3].

Английское словосочетание «Data Mining» пока не имеет устоявшегося перевода на русский язык. При передаче на русском языке используются следующие словосочетания[4]:просев информации, добыча данных, извлечение данных, а, также, интеллектуальный анализ данных[5][6][7]. Более полным и точным является словосочетание «обнаружение знаний в базах данных» (англ. knowledge discovering in databases, KDD).

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

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

 

Исторический экскурс

Область Data Mining началась с семинара (англ. workshop), проведёного Григорием Пятецким-Шапиро в 1989 году.[1]

Ранее, работая в компании GTE Labs, Григорий Пятецкий-Шапиро заинтересовался вопросом: можно ли автоматически находить определённые правила, чтобы ускорить некоторые запросы к крупным базам данных. Тогда же было предложено два термина — Data Mining («добыча данных»[9]) и Knowledge Discovery In Data (который следует переводить как «открытие знаний в базах данных»).

В 1993 году вышла первая рассылка «Knowledge Discovery Nuggets», а в 1994 году был создан один из первых сайтов по Data Mining.

Постановка задачи

Первоначально задача ставится следующим образом:

имеется достаточно крупная база данных;

предполагается, что в базе данных находятся некие «скрытые знания».

Необходимо разработать методы обнаружения знаний, скрытых в больших объёмах исходных «сырых» данных.

Что означает «скрытые знания»? Это должны быть обязательно знания:

ранее не известные — то есть такие знания, которые должны быть новыми (а не подтверждающими какие-то ранее полученные сведения);

нетривиальные — то есть такие, которые нельзя просто так увидеть (при непосредственном визуальном анализе данных или при вычислении простых статистических характеристик);

практически полезные — то есть такие знания, которые представляют ценность для исследователя или потребителя;

доступные для интерпретации — то есть такие знания, которые легко представить в наглядной для пользователя форме и легко объяснить в терминах предметной области.

Эти требования во многом определяют суть методов Data mining и то, в каком виде и в каком соотношении в технологии Data mining используются системы управления базами данных, статистические методы анализа и методы искусственного интеллекта.

 

Data mining и базы данных

Методы Data mining имеет смысл применять только для достаточно больших баз данных. В каждой конкретной области исследований существует свой критерий «великости» базы данных.

Развитие технологий баз данных сначала привело к созданию специализированного языка — языка запросов к базам данных. Для реляционных баз данных — это язык SQL, который предоставил широкие возможности для создания, изменения и извлечения хранимых данных. Затем возникла необходимость в получении аналитической информации (например, информации о деятельности предприятия за определённый период), и тут оказалось, что традиционные реляционные базы данных, хорошо приспособленные, например, для ведения оперативного учёта (на предприятии), плохо приспособлены для проведения анализа. это привело, в свою очередь, к созданию т. н. «хранилищ данных», сама структура которых наилучшим способом соответствует проведению всестороннего математического анализа.

12.

 

13. Классификация и регрессия

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

Распознавание качественной (дискретной) характеристики объекта называется классификацией, число возможных значений q - числом классов, а множество объектов, для которых эта характеристика принимает j-е значение - j-м классом. Ответом распознавателя для каждого объекта лучше считать не номер класса, к которому распознаватель относит объект, а более полное знание, исходя из которого номер класса легко посчитать, - q-мерный вектор "уверенностей" ( confidence) в принадлежности объекта каждому из классов. Тем самым, классификация превращается в специальный случай регрессии2.

В теоретически удобных случаях, когда пространство всех возможных объектов разбито на классы и на нем определена вероятность, "уверенности" в кавычках можно заменить вероятностями без кавычек и для них выполнены вероятностные нормировки (каждая от 0 до 1, сумма всех равна 1). На практике задачу классификации иногда обобщают на случай классов, объединение которых не равно всему пространству, (такая задача сводится к "правильно поставленной" задаче введением дополнительного класса), и даже на случай пересекающихся классов. При этом "уверенности" могут не быть вероятностями в каком-либо строгом смысле. Например, при распознавании рукописных букв на вход распознавателя может попасть вообще не буква. Кроме того, некоторые написания букв `О' заглавное, `о' строчное и цифры `0' абсолютно неразличимы, но считать, что такая замечательно написанная буква `о' является буквой `о' с вероятностью всего лишь около [ 1/3] не всегда полезно для распознавания слова в целом.

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

Классы могут быть и неравноправны: объекты одного класса могут встречаться на несколько порядков реже, чем объекты другого класса. В этом случае распознавать, какому классу объект принадлежит с большей вероятностью, довольно бессмысленно: почти всегда ко второму. Осмысленно обучать распознаватель оценивать вероятность принадлежности первому (очень редкому) классу.

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

Классификация с любым числом классов может быть сведена, причем разными способами, к решению конечного числа задач двухклассовой классификации. Иногда оказывается, что обучить и скомбинировать несколько двухклассовых классификаторов легче, чем обучить один многоклассовый. А иногда - наоборот. См., например, [HL02].

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

 

14. Задача кластеризации заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m – целое) кластеров (подмножеств) Q1, Q2, …, Qm, так, чтобы каждый объект Gj принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время, как объекты, принадлежащие разным кластерам были разнородными.

Например, пусть G включает n стран, любая из которых характеризуется ВНП на душу населения (F1), числом М автомашин на 1 тысячу человек (F2), душевым потреблением электроэнергии (F3), душевым потреблением стали (F4) и т.д. Тогда Х1 (вектор измерений) представляет собой набор указанных характеристик для первой страны, Х2 - для второй, Х3 для третьей, и т.д. Задача заключается в том, чтобы разбить страны по уровню развития.

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

где xj - представляет собой измерения j-го объекта.

Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности.

Понятно то, что объекты i-ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Хi и Хj было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Хi и Хj из Ер, где Ер -р-мерное евклидово пространство. Неотрицательная функция d(Хi , Хj) называется функцией расстояния (метрикой), если:

а) d(Хi , Хj) ³ 0, для всех Хi и Хj из Ер

б) d(Хi, Хj) = 0, тогда и только тогда, когда Хi = Хj

в) d(Хi, Хj) = d(Хj, Хi)

г) d(Хi, Хj) £ d(Хi, Хk) + d(Хk, Хj), где Хj; Хi и Хk - любые три вектора из Ер.

Значение d(Хi, Хj) для Хi и Хj называется расстоянием между Хi и Хj и эквивалентно расстоянию между Gi и Gj соответственно выбранным характеристикам (F1, F2, F3, ..., Fр).

Наиболее часто употребляются следующие функции расстояний:

1. Евклидово расстояние d2i , Хj) =

2. l1 - норма d1i , Хj) =

3. Супремум - норма d¥ i , Хj) = sup

k = 1, 2, ..., р

4. lp - норма dрi , Хj) =

Евклидова метрика является наиболее популярной. Метрика l1 наиболее легкая для вычислений. Супремум-норма легко считается и включает в себя процедуру упорядочения, а lp - норма охватывает функции расстояний 1, 2, 3,.

Пусть n измерений Х1, Х2,..., Хn представлены в виде матрицы данных размером p´n:

 

Тогда расстояние между парами векторов d(Хi , Хj) могут быть представлены в виде симметричной матрицы расстояний:

Понятием, противоположным расстоянию, является понятие сходства между объектами Gi. и Gj. Неотрицательная вещественная функция S(Хi ; Хj) = Sij называется мерой сходства, если :

1) 0£ S(Хi , Хj)<1 для Хi ¹ Хj

2) S(Хi , Хi) = 1

3) S(Хi , Хj) = S(Хj , Хi)

Пары значений мер сходства можно объединить в матрицу сходства:

Величину Sij называют коэффициентом сходства.

Методы кластеризации

 

Сегодня существует достаточно много методов кластерного анализа. Остановимся на некоторых из них (ниже приводимые методы принято называть методами минимальной дисперсии).

Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., Хu) и квадрат евклидова расстояния между Хi и Хj определяется по формуле:

 

1) Метод полных связей.

Суть данного метода в том, что два объекта, принадлежащих одной и той же группе (кластеру), имеют коэффициент сходства, который меньше некоторого порогового значения S. В терминах евклидова расстояния d это означает, что расстояние между двумя точками (объектами) кластера не должно превышать некоторого порогового значения h. Таким образом, h определяет максимально допустимый диаметр подмножества, образующего кластер.

 

2) Метод максимального локального расстояния.

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

 

3) Метод Ворда.

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

 

4) Центроидный метод.

Расстояние между двумя кластерами определяется как евклидово расстояние между центрами (средними) этих кластеров:

d2 ij = (`X –`Y)Т(`X –`Y) Кластеризация идет поэтапно на каждом из n–1 шагов объединяют два кластера G и p, имеющие минимальное значение d2ij Если n1 много больше n2, то центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп.

 

 

15. ЗАДАЧА ПОИСКА АССОЦИАТИВНЫХ ПРАВИЛ

Ассоциация - это одна из задач Data Mining. Целью поиска ассоциативных правил (association rule) является нахождение закономерностей между связанными событиями в базах данных [10-16].

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

Часто встречающиеся приложения с применением ассоциативных правил:

а)розничная торговля: определение товаров, которые стоит продвигать совместно; выбор местоположения товара в магазине; анализ потребительской корзины; прогнозирование спроса;

б)перекрестные продажи: если есть информация о том, что клиенты приобрели продукты A, Б и В, то какие из них вероятнее всего купят продукт Г?

в)маркетинг: поиск рыночных сегментов, тенденций покупательского поведения;

г)сегментация клиентов: выявление общих характеристик клиентов компании, выявление групп покупателей;

д)оформление каталогов, анализ сбытовых кампаний фирмы, определение последовательностей покупок клиентов (какая покупка последует за покупкой товара А);

е)анализ Web-логов.

Простой пример ассоциативного правила: покупатель, приобретающий шампунь для волос, приобретет кондиционер для волос с вероятностью 50%.

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

Рыночная корзина ? это набор товаров, приобретенных покупателем в рамках одной отдельно взятой транзакции.

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

Транзакция ? это множество событий, которые произошли одновременно.

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

Полученные в результате анализа шаблоны включают перечень товаров и число транзакций, которые содержат данные наборы.

Транзакционная или операционная база данных (Transaction database) представляет собой двумерную таблицу, которая состоит из номера транзакции (TID) и перечня покупок, приобретенных во время этой транзакции.? уникальный идентификатор, определяющий каждую сделку или транзакцию.

Пример транзакционной базы данных, состоящей из покупательских транзакций, приведен в таблице 2.2. В таблице первая колонка (TID) определяет номер транзакции, во второй колонке таблицы приведены товары, приобретенные во время определенной транзакции [10-13].

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

 

Таблица 2.2 - Транзакционная база данных TID

TIDПриобретенные покупки1Пена для бритья, гель для душа, бальзам после бритья2Гель для душа, мыло3Гель для душа, пена для бритья, мыло, бальзам после бритья4Духи, мыло5Пена для бритья, гель для душа, бальзам после бритья, мыло6Крем для тела

 

16. Выявление и использование формализованных закономерностей, или дистилляция шаблонов. При технологии дистилляции шаблонов один образец (шаблон) информации извлекается из исходных данных и преобразуется в некие формальные конструкции, вид которых зависит от используемого метода Data Mining. Этот процесс выполняется на стадии

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

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

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

 

17. Вторая стадия Data Mining - прогностическое моделирование - использует результаты работы первой стадии. Здесь обнаруженные закономерности используются непосредственно для прогнозирования.

Прогностическое моделирование включает такие действия:

• предсказание неизвестных значений (outcome prediction);

• прогнозирование развития процессов (forecasting).

В процессе прогностического моделирования решаются задачи классификации и прогнозирования.

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

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

Продолжая рассмотренный пример первой стадии, можем сделать следующий вывод.

Зная, что соискатель ищет руководящую работу и его стаж > 15 лет, на 65 % можно быть уверенным в том, что возраст соискателя > 35 лет. Или же, если возраст соискателя > 35 лет и желаемый уровень вознаграждения > 1200 условных единиц, на 90% можно быть уверенным в том, что соискатель ищет руководящую работу.

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

Правило: "Если возраст соискателя < 20 лет и желаемый уровень вознаграждения > 700 условных единиц, то в 75% случаев соискатель ищет работу программиста"

На основании частного, т.е. информации о некоторых свойствах класса "возраст < 20 лет" и "желаемый уровень вознаграждения > 700 условных единиц", мы делаем вывод об общем, а именно: соискатели - программисты.

Прогностическое моделирование, напротив, дедуктивно. Закономерности, полученные на этой стадии, формируются от общего к частному и единичному.

Здесь мы получаем новое знание о некотором объекте или же группе объектов на основании:

• знания класса, к которому принадлежат исследуемые объекты;

• знание общего правила, действующего в пределах данного класса объектов.

Знаем, что соискатель ищет руководящую работу и его стаж > 15 лет, на 65% можно быть уверенным в том, что возраст соискателя > 35 лет.

На основании некоторых общих правил, а именно: цель соискателя - руководящая работа и его стаж > 15 лет, мы делаем вывод о единичном - возраст соискателя > 35 лет.

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

18. На третьей стадии Data Mining анализируются исключения или аномалии, выявленные в найденных закономерностях.

Действие, выполняемое на этой стадии, - выявление отклонений (deviation detection). Для выявления отклонений необходимо определить норму, которая рассчитывается на стадии свободного поиска.

Вернемся к одному из примеров, рассмотренному выше.

Найдено правило "Если возраст > 35 лет и желаемый уровень вознаграждения > 1200 условных единиц, то в 90 % случаев соискатель ищет руководящую работу". Возникает вопрос - к чему отнести оставшиеся 10 % случаев?

Здесь возможно два варианта. Первый из них - существует некоторое логическое объяснение, которое также может быть оформлено в виде правила. Второй вариант для оставшихся 10% - это ошибки исходных данных. В этом случае стадия анализа исключений может быть использована в качестве очистки данных [12].

Далее мы рассмотрим несколько известных классификаций методов Data Mining по различным признакам.

Классификация технологических методов Data Mining

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

1. Непосредственное использование данных, или сохранение данных.

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

Методы этой группы: кластерный анализ, метод ближайшего соседа, метод k-ближайшего соседа, рассуждение по аналогии.

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

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

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

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

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

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

 

19. Методы классификации и прогнозирования. Деревья решений

Метод деревьев решений (decision trees) является одним из наиболее популярных методов

решения задач классификации и прогнозирования. Иногда этот метод Data Mining также

называют деревьями решающих правил, деревьями классификации и регрессии.

Как видно из последнего названия, при помощи данного метода решаются задачи

классификации и прогнозирования.

Если зависимая, т.е. целевая переменная принимает дискретные значения, при помощи

метода дерева решений решается задача классификации.

Если же зависимая переменная принимает непрерывные значения, то дерево решений

устанавливает зависимость этой переменной от независимых переменных, т.е. решает

задачу численного прогнозирования.

Впервые деревья решений были предложены Ховилендом и Хантом (Hoveland, Hunt) в

конце 50-х годов прошлого века. Самая ранняя и известная работа Ханта и др., в которой

излагается суть деревьев решений - "Эксперименты в индукции" ("Experiments in

Induction") - была опубликована в 1966 году.

В наиболее простом виде дерево решений - это способ представления правил в

иерархической, последовательной структуре. Основа такой структуры - ответы "Да" или

"Нет" на ряд вопросов.

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

существует возможность только двух ответов на поставленный вопрос ("да" и "нет").

Бинарные деревья являются самым простым, частным случаем деревьев решений. В

остальных случаях, ответов и, соответственно, ветвей дерева, выходящих из его

внутреннего узла, может быть больше двух.

Рассмотрим более сложный пример. База данных, на основе которой должно

осуществляться прогнозирование, содержит следующие ретроспективные данные о

клиентах банка, являющиеся ее атрибутами: возраст, наличие недвижимости, образование,

среднемесячный доход, вернул ли клиент вовремя кредит. Задача состоит в том, чтобы на

основании перечисленных выше данных (кроме последнего атрибута) определить, стоит

ли выдавать кредит новому клиенту.

Как мы уже рассматривали в лекции, посвященной задаче классификации, такая задача

решается в два этапа: построение классификационной модели и ее использование.

На этапе построения модели, собственно, и строится дерево классификации или создается

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

корня к одной из вершин, являющийся набором правил для конкретного клиента,

используется для ответа на поставленный вопрос "Выдавать ли кредит?"

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

На рис. 9.2. приведен пример дерева классификации, с помощью которого решается

задача "Выдавать ли кредит клиенту?". Она является типичной задачей классификации, и

при помощи деревьев решений получают достаточно хорошие варианты ее решения.

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

Как мы видим, внутренние узлы дерева (возраст, наличие недвижимости, доход и

образование) являются атрибутами описанной выше базы данных. Эти атрибуты

99называют прогнозирующими, или атрибутами расщепления (splitting attribute). Конечные

узлы дерева, или листы, именуются метками класса, являющимися значениями зависимой

категориальной переменной "выдавать" или "не выдавать" кредит.

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

Последний может относиться лишь к одному атрибуту расщепления данного узла.

Характерная особенность предикатов расщепления: каждая запись использует

уникальный путь от корня дерева только к одному узлу-решению. Объединенная

информация об атрибутах расщепления и предикатах расщепления в узле называется

критерием расщепления (splitting criterion) [33].

На рис. 9.2. изображено одно из возможных деревьев решений для рассматриваемой базы

данных. Например, критерий расщепления "Какое образование?", мог бы иметь два

предиката расщепления и выглядеть иначе: образование "высшее" и "не высшее". Тогда

дерево решений имело бы другой вид.

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

множество деревьев решений различного качества, с различной прогнозирующей

точностью.

Качество построенного дерева решения весьма зависит от правильного выбора критерия

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

исследователи.

Метод деревьев решений часто называют "наивным" подходом [34]. Но благодаря целому

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

задач классификации.

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

Интуитивность деревьев решений. Классификационная модель, представленная в виде

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

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

от нейронных сетей, представляющих собой "черные ящики", легко интерпретируется

пользователем. Это свойство деревьев решений не только важно при отнесении к

определенному классу нового объекта, но и полезно при интерпретации модели

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

конкретный объект относится к тому или иному классу.

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

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

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

аналитику достаточно сложно формализовать знания.

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

входных атрибутов (независимых переменных). На вход алгоритма можно подавать все

существующие атрибуты, алгоритм сам выберет наиболее значимые среди них, и только

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

сетями, это значительно облегчает пользователю работу, поскольку в нейронных сетях

выбор количества входных атрибутов существенно влияет на время обучения.

100Точность моделей, созданных при помощи деревьев решений, сопоставима с другими

методами построения классификационных моделей (статистические методы, нейронные

сети).

Разработан ряд масштабируемых алгоритмов, которые могут быть использованы для

построения деревьев решения на сверхбольших базах данных; масштабируемость здесь

означает, что с ростом числа примеров или записей базы данных время, затрачиваемое на

обучение, т.е. построение деревьев решений, растет линейно. Примеры таких алгоритмов:

SLIQ, SPRINT.

Быстрый процесс обучения. На построение классификационных моделей при помощи

алгоритмов конструирования деревьев решений требуется значительно меньше времени,

чем, например, на обучение нейронных сетей.

Большинство алгоритмов конструирования деревьев решений имеют возможность

специальной обработки пропущенных значений.

Многие классические статистические методы, при помощи которых решаются задачи

классификации, могут работать только с числовыми данными, в то время как деревья

решений работают и с числовыми, и с категориальными типами данных.

Многие статистические методы являются параметрическими, и пользователь должен

заранее владеть определенной информацией, например, знать вид модели, иметь гипотезу

о виде зависимости между переменными, предполагать, какой вид распределения имеют

данные. Деревья решений, в отличие от таких методов, строят непараметрические модели.

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

отсутствует априорная информация о виде зависимости между исследуемыми данными.

 

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

Напомним, что рассматриваемая нами задача классификации относится к стратегии

обучения с учителем, иногда называемого индуктивным обучением. В этих случаях все

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

классов.

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

"создание" дерева (tree building) и "сокращение" дерева (tree pruning). В ходе создания

дерева решаются вопросы выбора критерия расщепления и остановки обучения (если это

предусмотрено


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!