Параллельная обработка таблиц решения для задач распознавания

Размещено на http://www.allbest.ru/

Аннотация

Параллельная обработка таблиц решения для задач распознавания^** Работа выполнена при финансовой поддержке РФФИ (проекты №05-07-90232, №05-01-00818).

Н.Р. Акчурина 111250, Москва, ул. Красноказарменная 14, МЭИ, AkchurinaNR@yandex.ru., В.Н. Вагин 111250, Москва, ул. Красноказарменная 14, МЭИ, vagin@apmsun.mpei.ac.ru.

Предложен новый параллельный алгоритм для решения актуальной задачи машинного обучения [Akchurina et al., 2004, Vagin et al., 2004] совместной обработки качественных и количественных атрибутов с отсутствующими значениями. Тщательное тестирование на 55 на базах данных известного хранилища UC Irvine Repository, специально созданного из реальных баз данных разных областей для тестирования и сравнения алгоритмов обобщения [ML Repository], показало, что использование предложенного алгоритма увеличило точность классификации (главного критерия качества обучения) известных алгоритмов обобщения: ID3 [Quinlan, 1993], C4.5 [Quinlan, 1993], Naпve Bayes [Langley et al., 1992], Instance Based [Wettschereck, 1994] почти для всех случаев. Предложенный алгоритм при наличии ресурсов также позволяет существенно увеличить скорость предварительной обработки.

Введение

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

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

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

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

Также большинство алгоритмов обобщения не может непосредственно работать с таблицами с отсутствующими значениями.

Классификация методов дискретизации и группировки:

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

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

Было показано, что:

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

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

На основе данных наблюдений и теории приближенных множеств авторами была предложена параллельная версия алгоритма [Akchurina et al., 2004, Vagin et al., 2004], позволяющая одновременно обработать разнородные атрибуты (качественные и количественные) в том числе и с отсутствующими значениями.

1. Алгоритм параллельной предварительной обработки таблиц, основанный на теории приближенных множеств

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

,

где - атрибут решения. Элементы называются атрибутами условия.

С каждым множеством атрибутов ассоциировано отношение эквивалентности , называемое отношением - неразличимости:

.

Обозначим:

.

Через обозначим классы эквивалентности отношения .

Обобщенное решение в - это функция:

.

Таблица решений называется непротиворечивой (детерминированной), если для любого , иначе называется противоречивой (недетерминированной).

Представим формальное определение обобщенной задачи разбиения значений атрибутов [Akchurina et al., 2004, Vagin et al., 2004].

Пусть

- таблица решений, где

для . Любая функция называется разбиением . Ранг определяется как

.

Любое семейство разбиений

определяет из новую систему решений

,

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

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

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

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

Пусть

- система решений, где:

, и .

Тройка называется цепочкой, где для и .

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

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

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

- относительной матрицей различимости для цепочек будем называть симметричную матрицу с элементами:

.

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

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

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

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

Шаг 3. Для каждого процесса из

Формируем матрицу из -ого

столбца - относительной матрицы для цепочек.

Шаг 4. Находим наиболее часто встречающуюся цепочку в элементах .

Шаг 5. Цепочка добавляется к множеству цепочек .

Шаг 6. Все ячейки , содержащие заменяем пустыми множествами.

Шаг 7. Если все ячейки матрицы являются пустыми множествами, то переходим к шагу 4, иначе к шагу 8.

Шаг 8. Формируем множество цепочек из наиболее часто встречающихся цепочек в .

Шаг 9. Для каждого процесса из .

Проверяем, различает ли все объекты из различных классов решений при помощи матриц .

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

Шаг 10. определяет из

новую систему решений:

,

для любого объекта , .

Шаг 11. Разделяем числовые атрибуты на интервалы. Шкалированые качественные атрибуты на подмножества.

2. Анализ результатов

Предложенный алгоритм был реализован на Ассемблере и протестирован на базах данных известного хранилища UC Irvine Repository, специально созданного из реальных баз данных разных областей для тестирования и сравнения алгоритмов обобщения [ML Repository]. Таблица показывает увеличение точности классификации, известных алгоритмов обобщения: ID3 [Quinlan, 1993], C4.5 [Quinlan, 1993], Naпve Bayes [Langley et al., 1992], Instance Based [Wettschereck, 1994] на 35 таблицах этого хранилища (тестирование было проведено для 55 таблиц), предварительно обработанных при помощи предложенного алгоритма, и характеристики таблиц:

train/test - число объектов в обучающем/экзаменационном множестве;

С - отмечено, если соответствующая таблица содержит количественные атрибуты;

Q - отмечено, если соответствующая таблица содержит качественные атрибуты;

M - отмечено, если некоторые значения в таблице отсутствуют.

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

Предложенный алгоритм при наличии ресурсов также позволяет существенно увеличить скорость предварительной обработки по сравнению с последовательной версией [Akchurina et al., 2004, Vagin et al., 2004].

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

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

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

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

Заключение

Предложен новый параллельный алгоритм для решения актуальной задачи машинного обучения [Akchurina et al., 2004, Vagin et al., 2004] совместной обработки качественных и количественных атрибутов с отсутствующими значениями. Тщательное тестирование на 55 на базах данных известного хранилища UC Irvine Repository, специально созданного из реальных баз данных разных областей для тестирования и сравнения алгоритмов обобщения [ML Repository], показало, что использование предложенного алгоритма увеличило точность классификации (главного критерия качества обучения) известных алгоритмов обобщения: ID3, C4.5, Naпve Bayes, Instance Based почти для всех случаев. Предложенный алгоритм при наличии ресурсов также позволяет существенно увеличить скорость предварительной обработки по сравнению с последовательной версией.

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

1. [Akchurina et al., 2004] Akchurina N.R., Vagin V.N., Generalized Value Partition Problem: A Rough Set Approach / Journal of Computer and Systems Sciences International. Vol. 43, No. 2. 2004, pp. 223-238.

2. [Vagin et al., 2004] Vagin V.N., Akchurina N.R., New Techniques for Handling Missing Data and Feature Extraction for Knowledge Discovery / Knowledge-Based Software Engineering // Stefanuk V. and Kaijiri K. (eds.), IOS Press, 2004, pp. 169-176.

3. [ML Repository] http://www.ics.uci.edu/~mlearn/MLRepository.html.

4. [Quinlan, 1993] Quinlan J.R., C 4.5: Programs for Machine Learning, Morgan Kaufmann Publishers, Inc., Los Altos, California, 1993.

5. [Langley et al., 1992] Langley P., Iba W., Thompson K., An analysis of bayesian classifiers / Proceedings of the tenth national conference on artificial intelligence, AAAI Press and MIT Press, 1992, pp. 223-228.

6. [Wettschereck, 1994]Wettschereck D., A Study of Distance-Based Machine Learning Algorithms, PhD thesis, Oregon State University, 1994.

Размещено на Allbest.ru