«

»

Окт 14

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

Е.С.Лепшова
Тверской государственный университет

Аннотация
Данная статья содержит 9 страниц, 1 рисунок, список литературы (8 используемых источников). Структура работы представлена введением, 5 разделами, выводами, списком используемой литературы. Областью исследования является алгоритм, основанный на деревьях решений и дальнейшее его использование для решения задач классификации и интеллектуального анализа данных с выявлением скрытых знаний. Целью работы является повышение эффективности, быстродействия и адаптивности метода формирования дерева решений, основанного на алгоритме C4-5. А так же рассмотрение возможности модификации алгоритма, используя распаралеливание в процессе построения дерева. Теоретическое исследование проводилось путем анализа литературы и нормативных источников.

Оглавление
Аннотация
Введение
Обоснование выбранного метода. Деревья решений
Алгоритм C4.5
Математическое обеспечение алгоритма
Оценка сложности алгоритма решения задачи. Параллелизм
Анализ полученных результатов распараллеливания
Выводы
Список использованной литературы

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

Введение
Стремительное развитие информационных технологий, в частности, прогресс в методах сбора, хранения и обработки данных позволил многим организациям собирать огромные массивы данных, которые необходимо анализировать. Объемы этих данных настолько велики, что возможностей экспертов уже не хватает.
На сегодняшний день интенсивно развивается направление, связанное с интеллектуализацией методов обработки и анализа данных. Интеллектуальные системы анализа данных (ИСАД) призваны минимизировать усилия лица, принимающего решения (ЛПР), в процессе анализа данных, а также в настройке алгоритмов анализа. Многие ИСАД позволяют не только решать классические задачи принятия решения, но и способны выявлять причинно-следственные связи, скрытые закономерности в системе, подвергаемой анализу. Точность результатов исследования прямо пропорционально объему тестовой выборки и обратно пропорциональна временным затратам. Суммарное время проведения исследований оказывается просто неприемлемым. Поэтому основной целью данной работы является актуальная научно-техническая задача реализации алгоритма и его распараллеливание. При этом необходимо проводить исследования на множестве задач, на каждой комбинации настроек алгоритма, с набором статистики.

Обоснование выбранного метода. Деревья решений
Впервые деревья решений были предложены Ховилендом и Хантом (Hoveland, Hunt) в конце 50-х годов прошлого века. Самая ранняя и известная работа Ханта и др., в которой излагается суть деревьев решений – “Эксперименты в индукции” (“Experiments in Induction”) – была опубликована в 1966 году.
Дерево решений – это способ представления правил в иерархической, последовательной структуре. Основа такой структуры – ответы “Да” или “Нет” в случае бинарных деревьев (алгоритм CART), или на ряд вопросов, определимых динамически в случае деревьев с произвольным числом потомков (алгоритм C4-5).
Чтобы решить задачу, т.е. принять решение требуется ответить на ряд вопросов, которые находятся в узлах дерева, начиная с его корня. При положительном ответе на вопрос осуществляется переход к левой части дерева, называемой левой ветвью, при отрицательном – к правой части дерева. Таким образом, внутренний узел дерева является узлом проверки определенного условия. Далее идет следующий вопрос и т.д., пока не будет достигнут конечный узел дерева, являющийся узлом решения, т.е. листом дерева. Для каждой конкретной задачи существуют свои типы конечного узла в количестве n+1.
Модель, представленная в виде дерева решений, является интуитивной и упрощает понимание решаемой задачи. Результат работы алгоритмов конструирования деревьев решений, в отличие, например, от нейронных сетей, представляющих собой “черные ящики”, легко интерпретируется пользователем. Это свойство деревьев решений не только важно при отнесении к определенному классу нового объекта, но и полезно при интерпретации модели классификации в целом. Дерево решений позволяет понять и объяснить, почему конкретный объект относится к тому или иному классу. Деревья решений дают возможность извлекать правила из базы данных на естественном языке.
Деревья решений позволяют создавать классификационные модели в тех областях, где аналитику достаточно сложно формализовать знания. Алгоритм конструирования дерева решений не требует от пользователя выбора входных атрибутов (независимых переменных). На вход алгоритма можно подавать все существующие атрибуты, алгоритм сам выберет наиболее значимые среди них, и только они будут использованы для построения дерева. В сравнении, например, с нейронными сетями, это значительно облегчает пользователю работу, поскольку в нейронных сетях выбор количества входных атрибутов существенно влияет на время обучения.
Точность моделей, созданных при помощи деревьев решений, сопоставима с другими методами построения классификационных моделей (статистические методы, нейронные сети). Разработан ряд масштабируемых алгоритмов, которые могут быть использованы для построения деревьев решения на сверхбольших базах данных; масштабируемость здесь означает, что с ростом числа примеров или записей базы данных время, затрачиваемое на обучение, т.е. построение деревьев решений, растет линейно.
На построение классификационных моделей при помощи алгоритмов конструирования деревьев решений требуется значительно меньше времени, чем, например, на обучение нейронных сетей. Большинство алгоритмов конструирования деревьев решений имеют возможность специальной обработки пропущенных значений.
Многие классические статистические методы, при помощи которых решаются задачи классификации, могут работать только с числовыми данными, в то время как деревья решений работают и с числовыми, и с категориальными типами данных.
Многие статистические методы являются параметрическими, и пользователь должен заранее владеть определенной информацией, например, знать вид модели, иметь гипотезу о виде зависимости между переменными, предполагать, какой вид распределения имеют данные. Деревья решений, в отличие от таких методов, строят непараметрические модели. Таким образом, деревья решений способны решать такие задачи Data Mining(раскопки данных), в которых отсутствует априорная информация о виде зависимости между исследуемыми данными.
На сегодняшний день существует большое число алгоритмов, реализующих деревья решений: CART, C4.5, CHAID, CN2, NewId, ITrule и другие. Деревья с произвольным числом потомков, как одна из разновидностей деревьев решений, благодаря своим свойствам являются более универсальным методом решения задач классификации. Именно такой алгоритм выбран в качестве области исследования.

Алгоритм C4.5
Алгоритм C4.5 моделирует дерево решений с неограниченным количеством ветвей у узла. Данный алгоритм может работать только с дискретным зависимым атрибутом и поэтому может решать только задачи классификации. C4.5 считается одним из самых известных и широко используемых алгоритмов построения деревьев классификации.
Для работы алгоритма C4.5 необходимо соблюдение следующих требований:
Каждая запись набора данных должна быть ассоциирована с одним из предопределенных классов, т.е. один из атрибутов набора данных должен являться меткой класса. Классы должны быть дискретными. Каждый пример должен однозначно относиться к одному из классов. Количество классов должно быть значительно меньше количества записей в исследуемом наборе данных. Алгоритм C4.5 медленно работает на сверхбольших и зашумленных наборах данных.
Псевдокод Algorithm C4-5
1. Input: database D
2. Tree = {}
3. If D is pure OR other stopping criteria Then
4. Terminate
5. End If
6. For all attribute a ϵ D do
7. Entropy for root
8. End For
9. abest = Best attribute entropy
10. Tree = Create a node then test a best in the root
11. Dv = sud_datasets from D
12. For all Dv do
13. Tree v= C4.5(Dv)
14. End for
15. Return Tree

Математическое обеспечение алгоритма
Исходными данными задачи классификации является множество примеров T, где каждый элемент этого множества описывается m атрибутами. Количество примеров во множестве T будем называть мощностью этого множества, и обозначаться |T|. Пусть метка класса принимает следующие значения C1, C2 … Ck.
Задача алгоритма заключается в построении иерархической классификационной модели в виде дерева из множества примеров T. Процесс построения дерева будет происходить сверху вниз. Сначала создается корень дерева, затем потомки корня и т.д.
На первом шаге дерево пустое (имеется только корень) и исходное множество T (ассоциированное с корнем). Требуется разбить исходное множество на подмножества. Для этого выбрать один из атрибутов в качестве проверки. Тогда в результате разбиения получаются n(по числу значений атрибута) подмножеств и, соответственно, создаются n потомков корня, каждому из которых поставлено в соответствие свое подмножество, полученное при разбиении множества T. Затем эта процедура рекурсивно применяется ко всем подмножествам (потомкам корня) и т.д.
Очевидно, что из m (по числу атрибутов) возможных вариантов, требуется выбрать самый подходящий. Некоторые алгоритмы исключают повторное использование атрибута при построении дерева. Любой из атрибутов можно использовать неограниченное количество раз при построении дерева.
Пусть мы имеем проверку X (в качестве проверки может быть выбран любой атрибут), которая принимает n значений A1, A2 … An. Тогда разбиение T по проверке X даст нам подмножества T1, T2 … Tn, при X равном соответственно A1, A2 … An. Единственная доступная информация – то, каким образом классы распределены во множестве T и его подмножествах, получаемых при разбиении по X. Именно это играет роль при определении критерия.
Пусть – количество примеров из некоторого множества S, относящихся к одному и тому же классу Cj. Тогда вероятность того, что случайно выбранный пример из множества S будет принадлежать к классу Cj

Согласно теории информации, количество содержащейся в сообщении информации, зависит от ее вероятности
(1)
Выражение дает оценку среднего количества информации, необходимого для определения класса примера из множества T. В терминологии теории информации выражение (2) называется энтропией множества T.
(2)
Ту же оценку, но только уже после разбиения множества T по X, дает следующее выражение:
(3)
Тогда критерием для выбора атрибута будет являться следующая формула:
(4)
Критерий (4) считается для всех атрибутов. Выбирается атрибут, максимизирующий данное выражение. Этот атрибут будет являться проверкой в текущем узле дерева, а затем по этому атрибуту производится дальнейшее построение дерева. Т.е. в узле будет проверяться значение по этому атрибуту и дальнейшее движение по дереву будет производиться в зависимости от полученного ответа.
Такие же рассуждения можно применить к полученным подмножествам T1, T2 … Tn и продолжить рекурсивно процесс построения дерева, до тех пор, пока в узле не окажутся примеры из одного класса.
Одно важное замечание: если в процессе работы алгоритма получен узел, ассоциированный с пустым множеством (т.е. ни один пример не попал в данный узел), то он помечается как лист, и в качестве решения листа выбирается наиболее часто встречающийся класс у непосредственного предка данного листа. Здесь следует пояснить, почему критерий (4) должен максимизироваться. Из свойств энтропии нам известно, что максимально возможное значение энтропии достигается в том случае, когда все его сообщения равновероятны. В данном случае, энтропия (3) достигает своего максимума, когда частота появления классов в примерах множества T равновероятна. В итоге необходимо выбрать такой атрибут, чтобы при разбиении по нему один из классов имел наибольшую вероятность появления. Это возможно в том случае, когда энтропия (3) будет иметь минимальное значение и, соответственно, критерий (4) достигнет своего максимума.
В случае с числовыми атрибутами следует выбрать порог, с которым должны сравниваться все значения атрибута. Пусть числовой атрибут имеет конечное число значений {v1, v2 … vn}, предварительно отсортированное. Тогда любое значение, лежащее между vi и vi+1, делит все примеры на два множества: те, которые лежат слева от этого значения {v1, v2 … vi}, и те, что справа {vi+1, vi+2 … vn}. В качестве порога можно выбрать среднее между значениями vi и vi+1

Таким образом, это позволит существенно упростить задачу нахождения порога, и привести к рассмотрению всего n-1 потенциальных пороговых значений TH1, TH2…THn-1. Формулы (2), (3) и (4) последовательно применяются ко всем потенциальным пороговым значениям, и среди них выбирается то, которое дает максимальное значение по критерию (4). Далее это значение сравнивается со значениями критерия (4), подсчитанными для остальных атрибутов. Если выяснится, что среди всех атрибутов данный числовой атрибут имеет максимальное значение по критерию (4), то в качестве проверки выбирается именно он.

Оценка сложности алгоритма решения задачи. Параллелизм
Алгоритм решающего дерева имеет сложность, линейную по длине выборки. Если множество предикатов настолько богато, что на шаге всегда нахо¬дится предикат, разбивающий выборку S на непустые подмножества S0 и S1,то алгоритм строит бинарное решающее дерево, безошибочно классифицирую¬щее выборку X. Параллелизм (Concurrency) — это свойство систем, при котором несколько вычислений выполняются одновременно, и при этом, возможно, взаимодействуют друг с другом. Вычисления могут выполняться на нескольких ядрах одного чипа с вытесняющим разделением времени потоков вычислений на одном процессоре, либо выполняться на физически отдельных процессорах.
Алгоритм деревьев решений построен на индукции, является примером поглощающего «жадного» алгоритма, и на сегодняшний день наиболее распространенной стратегией деревьев решений для данных, но это не только стратегия. Как отмечалось ранее, общая схема построения дерева принятия решений выглядит следующим образом:
Выбирается очередной атрибут, помещается в корень. Затем для всех его значений рекурсивно строится дерево в этом потомке. Начиная со второго шага, алгоритм может быть распараллелен.

График 1 Зависимость времени работы алгоритма от объема обучающей выборки (t, тик / size)
Метод 1 – Линейные вычисления (t, тик / size, количество строк шт. в базе)
Метод 2 – Распараллеливание в один поток (блокирование внешних потоков) (t, тик / size, количество строк шт. в базе)
Метод 3 – Полностью распараллеленный алгоритм на 2 потока (t, тик / size, количество строк шт. в базе)
Анализ полученных результатов распараллеливания
Из графика 1 видно, что распараллеливание алгоритма деревьев решений имеет смысл проводить только на больших объемах данных. Для случаев, где выборка данных меньше 50 элементов распараллеливание избыточно, линейный вариант алгоритма работает быстрее. Это связано с время затратой работы приложения на сам процесс создания и работы с потоками. Распараллеливание в 1 поток значительно проще реализуется, однако дает результат, превосходящий линейный алгоритм, а значит, так же является применимым для реализации данной задачи на практике. В результате, уже при объеме базы более ста строк алгоритм в распараллеленной версии позволяет экономить минуты. С увеличением базы этот результат будет подтверждаться, а разрыв во времени работы методов усиливаться.

Выводы
Деревья решений – иерархическое, гибкое средство предсказания принадлежности объектов к определенному классу или прогнозирования значений числовых переменных. Среди большого числа разнообразных алгоритмов классификации деревья решений отличаются тем, что позволяют проводить интеллектуальный анализ данных, т.е. представлять в явном и доступном для понимания и интерпретации экспертами причинно-следственные связи в процессе отнесения объекта классификации к тому или иному классу.
Задача формирования дерева решений представляет собой оптимизационную задачу. Качество работы рассмотренного метода деревьев решений зависит как от выбора алгоритма, так и от набора исследуемых данных. Несмотря на все преимущества данного метода, следует помнить, что для того, чтобы построить качественную модель, необходимо понимать природу взаимосвязи между зависимыми и независимыми переменными и подготовить достаточный набор данных.
В ходе работы был выполнен аналитический обзор существующих методов
классификации и оптимизации, установлена целесообразность использования деревьев решений, как метода для решения задач классификации и интеллектуального анализа данных, разработан метод формирования дерева решений с использованием выбранного алгоритма, рассмотрена возможность распараллеливания алгоритма, реализован разработанный алгоритм и апробирован его на реальных практических задачах
Таким образом, разработан и исследован на практических задачах классификации метод С4-5, основанный на деревьях решений. Преимуществом разработанного метода является формализованная процедура отбора стартовых правил с использованием априорной информации из обучающей выборки, существенно повышающая эффективность метода. Данная процедура позволяет сразу же генерировать работоспособное дерево из незначительного числа правил.
В ходе проведения апробации разработанной схемы формирования дерева решений были выявлены следующие особенности метода:
- существует определенный уровень ограничения на число используемых атрибутов, при котором достигается максимальная точность классификации; дальнейшее увеличение числа используемых в базе будет приводить к уменьшению точности классификации (эффект влияния правил);
- при выборе такого уровня ограничения будет наблюдаться увеличение эффективности классификации на каждом этапе формирования дерева;
- наблюдается статистическая устойчивость по точности классификации и повторяемости генерируемых деревьев решений при многократном запуске алгоритма;
Сравнение алгоритма C4-5 с другими методами показывает, что алгоритм деревьев решений превосходит по эффективности современные алгоритмы классификации. Кроме того, он – это также инструмент интеллектуального анализа данных для обнаружения скрытых знаний. В ходе апробации алгоритма на практических задачах классификации получены дерева решающих правил, представляющие интерес для специалистов в соответствующих проблемных областях.

Список использованной литературы:
1. Учебный курс И.А.Чубукова – Data Mining http://www.intuit.ru/department/database/datamining/
2. Основы программирования на С#, В. А. Биллиг, Бином. Лаборатория знаний, Интернет-университет информационных технологий. Серия: Основы информационных технологий, 2009. http://www.intuit.ru/department/se/prcsharp08/
3. Шилдт Г. Теория и практика C# / Г. Шилдт. – СПб.: BHV-Санкт-Петербург, 1996. – 312 с.
4. Барсегян, А.А. Методы и модели анализа данных: OLAP и Data Mining / А.А. Барсегян, М.С. Куприянов, В.В. Степаненко, И.И. Холод. – СПб.: «БХВ-Петербург», 2004. – 336 с.
5. Макленнен, Дж. Microsoft SQL Server 2008: Data Mining – интеллектуальный анализ данных / Дж. Макленнен, Ч. Танг, Б. Криват. – СПб.: «БХВ-Петербург», 2009. – 720 с.
6. Breiman, L., Friedman, J., Olshen, R., and Stone, C. (1984).
Classification and Regression Trees. Wadsworth International Group, Belmont, CA.
7. Joydeep Ghosh and Alexander Liu, K-Means, The Top Ten Algorithms in Data Mining
8. Dan Steinberg, CART: Classification and Regression Trees, The Top Ten Algorithms in Data Mining