Определение задачи отбора данных

Ведение.

В современном обществе все большие объемы информации сохраняются в электронном виде в базах данных. Источники таких больших потоков данных имеются во многих областях: банковское дело, розничная торговля, управление и диагностика, маркетинг и т.д. Общим для всех этих данных является то, что она содержит большое количество скрытых закономерностей, являющихся весьма важными для принятия стратегических решений. К сожалению, человеку не под силу извлечь эти закономерности просто из-за огромного размера баз данных. Таким образом, существует необходимость в компьютерных системах, способных анализировать подобного рода данные и представлять новые знания в удобной для восприятия человеком форме. Этот процесс называется извлечением данных (data mining) или, более точно, открытием знаний (knowledge discovery). Системы, решающие такие задачи имеют важное практическое значение и базируются на методах машинного обучения и обобщения знаний.

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

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

Базы данных постоянно обновляются. Информация добавляется, изменяется или удаляется. Следовательно, знания, извлеченные из базы данных ранее, уже не соответствуют содержащимся в ней данным. Очевидно, что обучающаяся система должна адаптироваться к подобным изменениям. Необходимо также учесть, что свежая информация более ценна, чем старая.

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

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

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

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

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

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

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

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

Ø масштабируемость;

Ø использование реляционного подхода отбора данных, а не выборочного;

Ø возможность выполнять множество запросов за один просмотр.

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

 

Определение задачи отбора данных

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

 

Ассоциации/сходство

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

 

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

 

Последовательности/временные шаблоны

Этот метод используется для того, чтобы выявить временную взаимосвязь, например:

в 80% случаев покупки портативного компьютера батарейки покупаются в течение следующих трех месяцев;

клиенты сотовой связи, делавшие в предыдущие три месяца на 25% меньше вызовов, с вероятностью 60% отказываются от услуг этой службы;

в течение месяца после землетрясения продажа огнетушителей вырастает на 400%.

Кластеризация

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

Ø покупателей, которые, по всей вероятности, будут покупать электронику для развлечений;

Ø магазины, которые, вероятно, будут продавать спутниковые антенны;

Ø клиентов сотовой телефонной связи с различными привычками пользования телефоном.

Классификация

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

 

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

 

Способы получения знаний

 

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

Под приобретением (acquisition) знаний понимают способ автоматизированного наполнения базы знаний посредством диалога эксперта и специальной программы.

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

Термином “ обнаружение знаний в базах данных ” (knowledge discovery in databases – KDD) сегодня обозначают процесс получения из “сырых” данных новой, потенциально полезной информации о предметной области. Этот процесс включает несколько этапов (рис. 1). Сюда относится накопление сырых данных, отбор, подготовка, преобразование данных, поиск закономерностей в данных, оценка, обобщение и структурирование найденных закономерностей.

Рисунок 1. Процесс обнаружения знаний в БД

Стратегия KDD все более выдвигается на первую роль. Это во многом обусловлено быстрым развитием разнообразных хранилищ данных (data warehouse) – собраний данных, отличающихся предметной ориентированностью, интегрированностью, поддержкой хронологии, неизменяемостью, и предназначенных для последующей аналитической обработки.

 

Специфика современных требований к обработке данных с целью обнаружения знаний следующая:

- Данные имеют неограниченный объем

- Данные являются разнородными (количественными, качественными, категориальными)

- Данные должны быть конкретны и понятны

- Инструменты для обработки “сырых” данных должны быть просты в использовании

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

Важное положение Data Mining – нетривиальность разыскиваемых паттернов. Это означает, что они должны отражать неочевидные, неожиданные (unexpected) регулярности в данных, составляющие так называемые скрытые знания (hidden knowledge). Многие специалисты осознали, что для выявления закономерностей в реальных жизненных явлениях нужен особенный аналитический инструментарий, соответствующий их системной сложности. В свою очередь, к обществу пришло понимание, что “сырые” данные содержат глубинный пласт знаний, при грамотной раскопке которого могут быть обнаружены настоящие самородки.

Системы Data Mining применяются по двум основным направлениям:

1) как массовый продукт для бизнес-приложений;

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

Сфера применения Data Mining ничем не ограничена - она везде, где имеются какие-либо данные. Но в первую очередь методы Data Mining сегодня, мягко говоря, заинтриговали коммерческие предприятия, развертывающие проекты на основе информационных хранилищ данных (Data Warehousing). Опыт многих таких предприятий показывает, что отдача от использования Data Mining может достигать 100%. Например, известны сообщения об экономическом эффекте, в 10-70 раз превысившем первоначальные затраты от 350 до 750 тыс. дол. Известны сведения о проекте в 20 млн. дол., который окупился всего за 4 месяца. Другой пример - годовая экономия 700 тыс. дол. за счет внедрения Data Mining в сети универсамов в Великобритании.

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

Некоторые бизнес - приложения Data Mining

Розничная торговля

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

 

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

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

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

 

Банковское дело

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

 

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

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

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

 

Телекоммуникации

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

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

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

Страхование

Страховые компании в течение ряда лет накапливают большие объемы данных. Здесь обширное поле деятельности для методов Data Mining:

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

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

 

Другие приложения в бизнесе

Data Mining может применяться во множестве других областей:

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

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

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

Специальные приложения

Медицина

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

 

Молекулярная генетика и генная инженерия

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

 

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

 

Прикладная химия

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

 

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

 

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

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

Например, методы традиционной математической статистики, составляющие основу статистических пакетов, полезны главным образом для проверки заранее сформулированных гипотез (verification-driven data mining) и для “грубого” разведочного анализа, составляющего основу оперативной аналитической обработки данных (online analytical processing, OLAP). Главная причина ограниченной эффективности большинства процедур для выявления взаимосвязей в данных, входящих в состав статистических пакетов, – концепция усреднения по выборке, приводящая к операциям над несуществующими величинами (например, средняя температура пациентов по больнице, средняя высота дома на улице, состоящей из дворцов и лачуг и т.п.). Так называемые “многомерные методы” типа дискриминантного, факторного и других подобных видов анализа приходят к конечному результату через операции над фиктивными векторами средних значений, а также ковариационными и корреляционными матрицами. Поэтому, их результаты нередко неточны, грешат подгонкой и отсутствием смысла.

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

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

Идея систем рассуждений на основе аналогичных случаев (case based reasoning – CBR) на первый взгляд крайне проста. Для того чтобы сделать прогноз на будущее или выбрать правильное решение, эти системы находят в прошлом близкие аналоги наличной ситуации и выбирают тот же ответ, который был для них правильным. Поэтому этот метод еще называют методом “ближайшего соседа” (nearest neighbour). В последнее время распространение получил также термин “memory based reasoning”, который акцентирует внимание, что решение принимается на основании всей информации, накопленной в памяти.

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

В наибольшей мере требованиям Data Mining удовлетворяют методы поиска логических закономерностей в данных. Их результаты, чаще всего выражаются в виде IF-THEN1 и WHEN-ALSO правил. С помощью таких правил решаются задачи прогнозирования, классификации, распознавания образов, сегментации БД, извлечения из данных “скрытых” знаний, интерпретации данных, установления ассоциаций в БД и др. Логические методы работают в условиях разнородной информации. Их результаты эффективны и прозрачны для восприятия.

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

Задачи

Задача 1 – “Умение решать простейшие задачи”

Для поиска логических закономерностей предлагается таблица данных, содержащая 100 объектов (строк) и 2 количественных признака (столбца) Х1, Х2. Таблица разделена ровно пополам на два класса объектов. Распределение объектов на плоскости двух признаков Х1 и Х2 приведено на рис. 2. Объекты 1-класса обозначены крестиком, а объекты второго класса – ноликом.

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

Решение представленной тестовой задачи очевидно. Каждый класс описывается двумя логическими правилами (всего 4 правила):

 

IF (X1 > 4) и (X2 < 5) THEN Класс 1 – крестики

 

IF (X1 < 5) и (X2 > 4) THEN Класс 1 – крестики

 

IF (X1 < 5) и (X2 < 5) THEN Класс 2 – нолики

 

IF (X1 > 4) и (X2 > 4) THEN Класс 2 – нолики

 

Как видно, этот простейший тест окажется “неподъемным” для многих известных коммерческих алгоритмов поиска логических закономерностей в данных.

Задача2 – “Умение находить наиболее полные и точные правила”

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

Матрица объект-признак размера N? p (N – число объектов, р – количество признаков) заполняется нулями и единицами (или любыми другими символами) со случайным равномерным распределением. В этой матрице выбираются участки строк различной длины (комбинации значений признаков), каждый из которых дублируется в матрице определенное число раз строго по вертикали. Тем самым создаются подгруппы объектов, для которых известно логическое правило, описывающее их полностью со 100 % точностью. Наборы подгрупп объединяются в классы, подлежащие распознаванию. Для большей чистоты эксперимента столбцы и строки общей матрицы переупорядочиваются случайным образом. Ставится задача найти в матрице данных введенные известные правила.

В конкретной задаче 2 таблица данных имеет следующие характеристики: количество объектов 400 (из них 100 объектов принадлежит 1 классу и 100 – второму, 200 объектов – случайным образом распределенные значения), 100 бинарных признаков, принимающих значения А или В. Требуется найти 4 известных логических правила, по 2 правила на каждый класс. Эти правила представляют собой комбинации от 7 до 15 элементарных логических событий. Фрагмент таблицы данных приведен на рис. 3.

Рисунок 3. Небольшой фрагмент бинарных тестовых данных

(выделены искомые комбинации значений признаков)

Задача2 далеко не самая трудная из встречающихся на практике. 100 бинарных признаков появляются в анализе, например, когда мы имеем дело всего с 10 исходными количественными признаками, которые при поиске логических закономерностей разбиваются на 10 интервалов каждый. Реальные задачи нередко содержат сотни и даже тысячи количественных, порядковых и категориальных признаков, а логические закономерности могут представлять собой комбинации из десятков и сотен элементарных событий. Если какая-либо система “не умеет” находить правила неограниченной сложности, покрывающие максимально возможные количества объектов собственного класса, то аналитик рискует утонуть в море “обрывков” логических правил.

 

Методы анализа данных

Интеллектуальные средства анализа данных используют следующие основные методы:

Ø нейронные сети;

Ø деревья решений;

Ø индукцию правил;

Кроме этих методов существуют еще несколько дополнительных:

Ø системы рассуждения на основе аналогичных случаев;

Ø нечеткая логика;

Ø генетические алгоритмы;

Ø алгоритмы определения ассоциаций и последовательностей;

Ø анализ с избирательным действием;

Ø логическая регрессия;

Ø эволюционное программирование;

Ø визуализация данных.

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

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

 

Д е р е в ь я р е ш е н и й

 

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

Деревья решений (decision trees) являются самым распространенным в настоящее время подходом к выявлению и изображению логических закономерностей в данных. Видные представители этого подхода – процедуры CHAID (chi square automatic interaction detection), CART (classification and regression trees) и ID3 (Interactive Dichotomizer – интерактивный дихотомайзер).

Первые идеи создания деревьев решений восходят к работам Ховленда (Hoveland) и Ханта(Hunt) конца 50-х годов XX века. Однако, основополагающей работой, давшей импульс для развития этого направления, явилась книга Ханта (Hunt, E.B.), Мэрина (Marin J.) и Стоуна (Stone, P.J) «Experiments in Induction», увидевшая свет в 1966г.

Деревья решения являются одним из наиболее популярных подходов к решению задач data mining. Они создают иерархическую структуру классифицирующих правил типа «ЕСЛИ... ТО...», имеющую вид дерева. Для того чтобы решить, к какому классу отнести некоторый объект или ситуацию, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Вопросы имеют вид «значение параметра A больше x». Если ответ положительный, осуществляется переход к правому узлу следующего уровня, если отрицательный – то к левому узлу; затем снова следует вопрос, связанный с соответствующим узлом.

Популярность подхода связана с наглядностью и понятностью. Но очень остро для деревьев решений стоит проблема значимости. Дело в том, что отдельным узлам на каждом новом построенном уровне дерева соответствует все меньшее и меньшее число записей данных – дерево дробит данные на большое количество частных случаев. Чем больше этих частных случаев, чем меньше обучающих примеров попадает в каждый такой частный случай, тем менее уверенной становится их классификация. Если построенное дерево слишком «кустистое» – состоит из неоправданно большого числа мелких веточек – оно не будет давать статистически обоснованных ответов. Как показывает практика, в большинстве систем, использующих деревья решений, эта проблема не находит удовлетворительного решения. Кроме того, общеизвестно, и это легко показать, что деревья решений дают полезные результаты только в случае независимых признаков. В противном случае они лишь создают иллюзию логического вывода.

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

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

 

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

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

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

 

Регрессионный анализ

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

Регрессия наиболее часто используется для построения прогнозных моделей.

К-ближайшие соседи

Аналогично деревьям решений, алгоритмы К-ближайших соседей лучше всего подходят для кластеризации и классификации. При выявлении кластеров алгоритм сначала представляет каждую запись как точку в многомерном пространстве. Затем он подбирает веса по каждой размерности так, чтобы точки, изображающие данные со сходными целевыми признаками, оказались в тесном соседстве. Предположим, например, что для банка целевая характеристика такова: "люди, обратившиеся за второй закладной". Если параметрами являются возраст, сумма первой закладной, задолженность и доход, то алгоритм последовательно перебирает различные веса для этих размерностей до тех пор, пока все точки, изображающие даные о лицах, обратившихся за второй закладной, не окажутся на графике рядом друг с другом, т. е. соседями. После того как К-ближайшие соседи использованы для кластеризации, они могут помочь произвести классификацию. Например, финансовая организация может очертить круг потенциальных покупок закладных, используя модель К-ближайших соседей. Если К-ближайшие соседи какого-то лица приобретут вторую закладную с некоторой вероятностью, то это лицо приобретет ее с той же самой вероятностью. Финансовая организация может решить предлагать вторые закладные только людям, для которых вероятность покупки составляет, скажем, 66% или выше.

Нейронные сети

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

 

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

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