Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Прогнозный анализ данных методом ID3O

# 10, октябрь 2012
DOI: 10.7463/1012.0483286
Файл статьи: Кузовлёв_2_Р.pdf (330.59Кб)
авторы: Кузовлев В. И., Орлов А. О.

УДК 004.052.42

Россия, МГТУ им. Н.Э. Баумана

forewar@gmail.com

 

Введение

Прогнозный анализ данных применяется в системах поддержки принятия решений. Суть прогнозного анализа заключается в формировании суждений о будущих фактах на основе анализа некоторого набора исходных данных. Такой набор данных называется обучающим множеством, а процесс анализа исходных данных называется обучением с учителем. В процессе обучения строится прогнозная модель, которая далее используется для формирования прогнозов. В данной статье рассматривается модель решающего дерева (decisiontreemodel) [1-3]. Деревья решений организованы в виде иерархической структуры, состоящей из узлов принятия решений по оценке значений определенных переменных для прогнозирования результирующего значения. Любое дерево решений выводит прогнозируемое значение, полученное в результате оценки некоторых входных атрибутов. Каждый уровень в дереве может рассматриваться как одно из решений; узел принятия решений обеспечивает проверку условия, а каждое ребро обозначает один из возможных вариантов. Узлы принятия решений содержат критерии выбора, а ребра выражают взаимоисключающие результаты проверки соответствия этим критериям.

Существует достаточно много алгоритмов, реализующих принципы модели деревьев решений [1-3]: ID3, С4.5, ДРЕВ, ID5R, Reduce. Все эти алгоритмы построения дерева решений не предполагают возможности наличия искажений в данных. Отсутствующие или искаженные данные оказывают существенное влияние на конечный вид построенного дерева решений и, как следствие, на результат работы модели.

В реальных системах поддержки принятия решений формирование прогнозной модели подвержено влиянию искажений в данных, по которым строится прогнозная модель. В [4] обсуждаются такие типы искажений в данных, как «отсутствие значений» и «аномальные значения». Рассматривается влияние искажений этих типов на процесс формирования прогнозной модели при использовании различных алгоритмов построения дерева решений.

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

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

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

1.     Проблема наличия разнородных искажений в данных.

2.     Проблема выбора эффективной стратегии повышения качества данных.

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

Методика обработки шума в данных

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

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

Выбор стратегии повышения качества данных важен в реальных условиях ограниченности материальных ресурсов. Необходимо использовать такой механизм выбора стратегии повышения качества данных, который позволит максимизировать эффект от повышения качества данных в условиях ограниченности ресурсов. В [6-8] предлагаются критерии для оценки качества информационных элементов при ручной обработке данных. Появляется возможность обеспечить такую методику обработки, когда в первую очередь будут обрабатываться те объекты, значимость которых определены как наивысшая. Таким образом, обеспечивается интенсивность повышения качества данных в условиях параллельной эксплуатации системы [7].

При автоматической обработке значения атрибутов объектов, являющиеся шумом, должны быть скорректированы. Одним из наиболее эффективных и популярных методов коррекции таких данных является метод «ближайших соседей» [1]. Этот метод основан на предположении о том, что если объекты схожи по некоторому подмножеству их атрибутов, то эти же объекты, вероятно, будут схожи и по другому подмножеству атрибутов. Таким образом, для объекта, содержащего шум в значениях некоторого атрибута, находятся наиболее близкие объекты, которые не содержат шума в данном атрибуте. После этого шум корректируется на основании значений соответствующих атрибутов ближайших объектов. Для расчета близости объектов используется некоторая заданная заранее метрика. Обработка выбросов данных происходит в два этапа. На первом этапе выбросы в данных необходимо идентифицировать. Для идентификации аномалий применяется метод выявления аномалий, предложенный авторами в [4]. Этот метод основан на механизме LOF [5]. На втором этапе обнаруженные объекты подлежат обработке.

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

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

(1)

где  – количество атрибутов объектов,  – расстояние между значениями p-го атрибута объектов,  – вес соответствующего значения атрибута объекта,  в том случае, если значение атрибута  не помечено как аномальное, в противном случае .

Расстояние  для непрерывных признаков [6] равно

(2)

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

Если одно из значений непрерывного атрибута неизвестно (), то расстояние определяется по известному значению [6]формулой

(3)

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

Для дискретных атрибутов расстояние вычисляется при условии, что :

(4)

Если , тогда . Если одно из значений дискретных атрибутов неизвестно (), тогда расстояние равно

(5)

где – наиболее частое значение p-го атрибута, то есть , где k – количество различных значений атрибута . Если оба значения дискретных атрибутов неизвестны, тогда , что является округленным в большую сторону максимальным расстоянием.

Формула расчета  предложена и обоснована авторами в [4]:

(6)

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

(7)

Здесь  – количество наиболее близких объектов.

В случае качественного атрибута значение выбирается как наиболее часто встречающееся среди соответствующих значений атрибутов наиболее близких объектов.

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

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

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

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

Выход: множество объектов , не содержащих пустых значений атрибутов.

Начало алгоритма.

Шаг 1. Начало цикла по . Выбрать следующий объект .

Шаг 2. Если  не содержит пустых значений атрибутов, то добавить этот объект в выходное множество  и перейти к шагу 1. Иначе перейти к шагу 3.

Шаг 3. Сформировать множество  расстояний от объекта  до остальных объектов из .

Шаг 4. Из множества  выбрать  наиболее близких объектов к  и сформировать из них множество .

Шаг 5. Заполнить пустые значения атрибутов объекта  на основании значений атрибутов объектов из .

Шаг 6. Добавить объект в выходное множество .

Шаг 7. Конец цикла по .

Конец алгоритма.

 

Алгоритм ID3O

В [1] предлагается алгоритм IDTUV, использующий алгоритмы построения дерева решений ID3 и C4.5 совместно с алгоритмом ВОССТАНОВЛЕНИЕ, позволяющим восстанавливать пропущенные данные.

Для шума типа «аномальные значения» в [4] предлагается метод выявления аномалий в исходных данных.

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

На первом этапе происходит выбор стратегии повышения качества данных в соответствии с показателями, предложенными в [8]. На втором этапе происходит повышение качества данных по предложенному алгоритму заполнения отсутствующих атрибутов данных, а также по предложенному в [4] алгоритму выявления аномалий. Далее строится дерево решений по алгоритму IDTUV [1].

Рисунок 1. Алгоритм ID3O

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

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

(8)

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

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

1)              Данные задач Монахов [10].

2)              Данные для распознавания типов цветков Ириса. Одна из наиболее популярных выборок данных для проверки моделей классификации [9].

3)              Данные для распознавания флагов стран [8].

4)              Данные о сердечной недостаточности проекта Statlog [11].

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

В таблице 2 представлены данные экспериментов над тестовыми наборами данных, не содержащих шума. Алгоритмы IDTUV и ID3O выдают результат, аналогичный результатам алгоритмов ID3 и C4.5 в случаях, когда в наборе данных содержатся только категориальные или только числовые атрибуты соответственно. В среднем по всем наборам данных алгоритмы IDTUV и ID3O показали лучшую точность классификации по сравнению с ID3 и C4.5, что подтверждает результаты, полученные в [1].

Таблица 2. Точность классификации на данных без шума

 

ID3

C4.5

IDTUV

ID3O

Monks

94,4

90,3

94,4

94,4

Iris

0

92,7

92,7

92,7

Flags

47,8

73,9

69,6

69,6

StatlogHeart

0

77,3

83,3

83,3

Среднее

35,55%

83,5%

85%

85%

На втором этапе в наборы данных вносился шум типов «отсутствие значений атрибутов» и «аномальные значения атрибутов». На втором этапе сравнивались результаты работы алгоритмов IDTUV и ID3O, поскольку они обрабатывают и корректируют шум в данных. Результаты представлены в таблице 3.

Таблица 3. Точность классификации на данных с шумом

Шум 5%

 

IDTUV

ID3O

Monks

93,6

94,4

Iris

90,3

92,7

Flags

68,5

69,6

StatlogHeart

77,7

83,2

Среднее

82,53%

84,98%

 

Шум 10%

 

IDTUV

ID3O

Monks

92,8

94,1

Iris

88,8

92,6

Flags

66,3

69,1

StatlogHeart

76,3

81,8

Среднее

81,05%

84,4%

 

Шум 20%

 

IDTUV

ID3O

Monks

90,7

92,8

Iris

87,9

92,2

Flags

64,2

65,2

StatlogHeart

74,2

78,1

Среднее

79,25%

82,08%

 

Заключение

По итогам экспериментов стало ясно, что предложенный в данной работе алгоритм ID3O имеет высокую устойчивость к искажениям в данных благодаря механизмам поиска и устранения аномалий в данных, а также заполнения пропущенных значений атрибутов. Так, при уровне шума в 5 % средний результат по всем наборам данных всего на 0,02 % ниже результата при отсутствии шума. При шуме в 10 % и 20 % снижение точности классификации составило в среднем 0,6 % и 2,92 % соответственно, что существенно меньше, чем снижение точности классификации других рассмотренных алгоритмов при аналогичных уровнях шума.

Таким образом, предложенный алгоритм ID3O показал способность к эффективной работе с данными, содержащими шум.

Список литературы

 

1.     Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах / под ред. В.Н. Вагина, Д.А. Поспелова. 2-е изд., испр. и доп. М.: Физматлит, 2008. 712 с.

2.     Quinlan J.R. Induction of Decision Trees // Machine Learning. 1986. Vol. 1, no. 1. P. 81-106. DOI: 10.1023/A:1022643204877

3.     Utgoff P.E. Incremental induction on Decision Trees // Machine Learning. 1989. Vol. 4, no. 2. P. 161-186. DOI: 10.1023/A:1022699900025

4.     Кузовлев В.И., Орлов А.О. Метод выявления аномалий в исходных данных при построении прогнозной модели решающего дерева в системах поддержки принятия решений // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 9. DOI: http://dx.doi.org/10.7463/0912.0483269   

5.     Breunig M., Kriegel H.-P., T. Ng R., Sander J. LOF: Identifying Density-Based Local Outliers // Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press. P. 93-104.

6.     Кузовлев В.И., Липкин Д.И. Определение базовых показателей достоверности обработки информации проектных решений АСОИУ. М., 2001. 12 с. Деп. в ВИНИТИ № 1094-В2001.

7.     Кузовлев В.И., Орлов А.О. Учет взаимосвязей между объектами результатов профилирования // Наука и образование. МГТУ им. Н. Э. Баумана. Электрон. журн. 2012. № 08. Режим доступа: http://engbul.bmstu.ru/doc/482766.html (дата обращения 03.09.2012).

8.     Кузовлев В.И., Орлов А.О. Вероятностный подход к оценке показателя достоверности элементов результатов профилирования // Вестник МГТУ им. Н.Э. Баумана, 2012. Режим доступа: http://vestnik.bmstu.ru/catalog/it/hidden/115.html (дата обращения 21.11.2012).

9.     UCI Machine Learning Repository: Flags Data Set. Режим доступа: http://archive.ics.uci.edu/ml/datasets/Flags  (дата обращения 02.09.2012).

10.  UCI Machine Learning Repository: Iris Data Set. Режим доступа: http://archive.ics.uci.edu/ml/datasets/Iris  (дата обращения 02.09.2012).

11.  UCI Machine Learning Repository: Monk’s Problems Data Set. Режим доступа: http://archive.ics.uci.edu/ml/datasets/MONK%27s+Problems (дата обращения: 02.09.2012)

12.  UCI Machine Learning Repository: Statlog Heart Data Set. Режим доступа:. http://archive.ics.uci.edu/ml/datasets/Statlog+%28Heart%29 (дата обращения: 02.09.2012)

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2024 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)