Зайцев И.М., Федяев О.И.
Донецкий национальный технический университет
Стремительное развитие информационных технологий способствовал появлению различных методов сбора, хранения и обработки огромных массивов данных. Для эффективного использования собранной информации появился новый класс алгоритмов, направленный на интеллектуальный анализ данных с целью извлечения знаний для управления деятельностью предприятий.
Деревья решений – один из таких методов автоматического анализа данных. Для автоматического анализа данных применяется новая технология Data Mining [1]. Data Mining переводится как «добыча» или «раскопка данных»[1]. Синонимами Data Mining являются также термины «обнаружение знаний в базах данных» (knowledge discovery in databases) и «интеллектуальный анализ данных».
Знания, извлечённые алгоритмами Data Mining, описывают причинно-следственные связи между свойствами, позволяют предсказывать значения одних признаков на основе других и т. д. . Знания должны быть в удобном для использования виде, чаще всего в форме продукции «if … then …». Выявленные знания могут быть применимы и для анализа новых данных с некоторой степенью достоверности.
Алгоритмы, используемые в Data Mining, требуют большого объёма вычислений. Раньше это являлось сдерживающим фактором широкого практического применения технологии Data Mining. Однако сегодняшний рост производительности современных процессоров снял остроту этой проблемы. Теперь за приемлемое время можно провести качественный анализ сотен тысяч и миллионов записей.
На сегодняшний день существует значительное число алгоритмов, реализующих деревья решений ID3, CART, C4.5, NewId, ITrule, CHAID, CN2. На основе этих алгоритмов построено много систем извлечения знаний: BrainMaker, CART, DMSK, DTREG, Estard Data Miner [1].
Большинство из известных алгоритмов являются «жадными алгоритмами». Если один раз был выбран атрибут, и по нему было произведено разбиение на подмножества, то алгоритм не может вернуться назад и выбрать другой атрибут, который дал бы лучшее разбиение. По этой причине на этапе построения нельзя сказать даст ли выбранный атрибут, в конечном итоге, оптимальное разбиение. Для улучшения качества выявленных знаний используется аппарат теории информации.
Решаемая задача заключается в исследовании зависимости результирующих деревьев решений, полученных с помощью применения алгоритма ID3, от выбора различных методов оценки информативности атрибутов. При анализе было выяснено, что при построении деревьев решений наиболее популярны следующие оценки информативности атрибутов: information gain, gain ratio и индекс Гини [1]. Для каждой оценки определены положительные и отрицательные стороны и сделан вывод, какой из этих методов является наиболее предпочтительным для использовании в реальных программных системах.
Для нахождения каждой из этих оценок используется понятие информационной энтропии. Для множества A из n элементов, m из которых обладают некоторым свойством S, энтропия множества A по отношению к свойству S рассчитывается, как
Для множества A элементов, из которых некоторые обладают свойством S (A классифицировано посредством атрибута Q, имеющего q разных значений) прирост информации рассчитывается по формуле:
где Ai – множество элементов A, на которых Q имеет значение i.
На каждом шаге алгоритм выбирает атрибут, для которого прирост информации максимален.
При выборе атрибута, основываясь на приросте информации, существует проблема: критерий будет показывать наибольший прирост для атрибутов, имеющих наибольшее число значений.
Другой критерий Gain Ratio учитывает не только количество информации, требуемое для записи результата, но и количество информации для разделения по текущему атрибуту.
Вводится поправка:
Сам критерий определяется максимизацией величины
Ещё один часто используемый критерий – так называемый индекс Гини. Для набора тестов A и свойства S, имеющего s значений, этот индекс вычисляется так:
Соответственно, для набора тестов A, атрибута Q, имеющего q значений, и целевого свойства S, имеющего s значений, индекс вычисляется следующим образом:
Индекс Гини отчасти компенсирует уклон критерия прироста информации в сторону выбора самых «развесистых» атрибутов. Однако в остальном они очень похожи (индекс Гини и критерий прироста информации не согласуются только на приблизительно 2% возможных случаев).
1. Люгер Д. Ф. Искусственный интеллект: стратегии и методы решения сложных проблемм, 4-е издание. : Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 864c.