Сравнительный анализ алгоритмов решения задачи распознавания для систем обнаружения знаний в базах данных
Н.Р. Акчурина
(Москва, Московский энергетический институт (Технический университет), Россия)
В современном обществе все большие объемы информации
сохраняются в базах данных. Общим для этих данных является то, что они содержат
большое количество скрытых закономерностей, являющихся весьма важными для
принятия стратегических решений. Решить эту проблему были призваны системы
обнаружения знаний в базах данных. Одной из основных задач, решаемых данными
системами и возникающей в таких областях как маркетинг, розничная торговля,
банковское дело, телекоммуникации, страхование, медицина, молекулярная генетика
и генная инженерия, является задача распознавания (задача формирования
решающего правила, на основании которого объекты, принадлежащие классу, могут
быть отделены от остальных). Хотя ограничения модели
представления извлеченных знаний на основе решающих правил могут существенно
снизить точность аппроксимации, в пользу ее использования можно выдвинуть
следующие доводы: она легка для понимания; системы, основанные на решающих
правилах, по ряду критериев занимают лидирующие позиции [6]; даже простые
правила [5] позволяют добиться приемлемой точности классификации – главного
критерия качества обучения. Обнаружение знаний в базах данных – это
итеративный процесс, одной из основных стадий которого является предварительная
обработка таблиц, в процессе которой происходят: дискретизация числовых
значений полей, группировка качественных значений полей и обработка
отсутствующих значений. Необходимость дискретизации и группировки диктуется
следующими факторами [8]: многие алгоритмы обобщения могут работать только в
дискретном пространстве, использование дискретизации и группировки обычно
позволяет добиться существенного увеличения скорости работы и точности
классификации. Также большинство алгоритмов обобщения не может непосредственно
работать с таблицами с отсутствующими значениями [8]. Было замечено [8], что точность
классификации увеличивается при одновременной обработке нескольких однородных
(только качественных и только количественных) атрибутов. Предложенные автором
алгоритмы [1,9,10,11] позволяют одновременно обработать разнородные атрибуты
(качественные и количественные) в том числе и с отсутствующими значениями. И
хотя в последнее время разработке алгоритмов предварительной обработки
уделяется пристальное внимание, эта проблема, по-прежнему, актуальна,
поскольку, как отмечалось разными исследователями [3,4], создать универсальный
алгоритм невозможно, а следует уделить пристальное внимание созданию разных
алгоритмов и реализации программных систем, включающих разнообразные алгоритмы,
которые могут оказаться полезными для решения конкретной задачи.
В связи с этим, целью настоящей работы является создание
программного комплекса, который бы позволил использовать и оттестировать
разработанные автором алгоритмы предварительной обработки таблиц [1,9,10,11] в
сочетании с известными алгоритмами обобщения, а также представлял бы полученные
результаты в наглядной форме.
Было реализовано шесть
алгоритмов обобщения [2,12]:
ü
Baseline алгоритм –
алгоритм для определения базовой точности классификации;
ü
ID3 алгоритм;
ü
C4.5 алгоритм;
ü
Naïve Bayes алгоритм – алгоритм Байеса;
ü
Table Majority алгоритм – метод поиска
примера в обучающем множестве;
ü
Instance Based алгоритм – метод ближайшего
соседа для качественных атрибутов.
Разработанные автором алгоритмы предварительной обработки
таблиц [1,9,10,11] были реализованы на ассемблере.
Было реализовано два известных
современных способа представления полученных результатов: при помощи
перекрестных ссылок и логических диаграмм.
При помощи перекрестных ссылок
можно посмотреть благодаря какому правилу был проклассифицирован пример,
правильно ли он был проклассифицирован (определяется цветом) и какие объекты
были проклассифицированы благодаря данному правилу. Этот способ представления
предназначен только для алгоритмов обобщения, результатом работы которых
является система правил.
Способ представления,
использующий логические диаграммы, позволяет проследить как общие тенденции,
так и рассмотреть классификацию отдельных объектов (даже не принадлежащих
экзаменационной или обучающей выборки). Все пространство возможных объектов
представляется в виде прямоугольника, и раскрашивается в соответствие с
классификацией (полученной в результате алгоритма обобщения – каждому классу
соответствует свой цвет), после чего отображается экзаменационное множество.
Если объект был правильно проклассифицирован, то в соответствующем квадратике
ставится «+», неправильно - «-», если есть объекты в экзаменационной
выборке как соответствующие классификации, так и не соответствующие, то
ставится «+/-». Логические диаграммы не ограничены представлением результатов
работы лишь алгоритмов обобщения, основанных на правилах.
Было проведено тестирование реализованного программного
комплекса на 55 базах данных известного хранилища UC Irvine Repository [7],
специально созданного из реальных баз данных разных областей для тестирования и
сравнения алгоритмов обобщения. Проведен анализ полученных результатов,
показавший, что в подавляющем числе случаев точность классификации при
использовании разработанных автором алгоритмы предварительной обработки таблиц [1,9,10,11]
увеличилась или осталась неизменной для всех алгоритмов обобщения. Но как можно
заранее узнать принесет ли какие-нибудь положительные результаты использование
предложенных стратегий для конкретной задачи? Также как нет алгоритма
обобщения, который работал бы определенно лучше других алгоритмов обобщения для
всех задач, так и здесь нельзя заранее ответить. Еще раз подчеркнем, что лучшим
решением является реализация разнообразных алгоритмов, основанных на разных
подходах и разбиение модельного множества на три, а не, как раньше
предлагалось, на два множества: обучающее для обучения всех алгоритмов,
подтверждающее множество для выбора наилучшего и экзаменационное множество для
оценки точности при дальнейшей работе.
В данной работе был сделан вывод о необходимости обобщить задачу разбиения значений атрибутов для одновременной обработки чисто качественных, непрерывных числовых и дискретных числовых атрибутов и разработать алгоритм, решающего поставленную задачу в условиях отсутствия некоторых значений атрибутов, а также алгоритм обработки таблиц с отсутствующими значениями и создать программный комплекс, который бы позволил использовать и оттестировать разработанные алгоритмы в сочетании с известными алгоритмами обобщения, а также представлял бы полученные результаты в наглядной форме.
Разработанный программный комплекс был протестирован на 55 таблицах из UC Irvine Repository [7], специально созданного из реальных баз данных разных областей для тестирования и сравнения алгоритмов обобщения. Тестирование показало повышение точности классификации - главного критерия качества обучения при использовании предложенных в данной работе алгоритмов с известными алгоритмами обобщения.
ЛИТЕРАТУРА
1. 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. Berry M.J.A. Data Mining Techniques:
for Marketing, Sales, and Customer Relationship Management / Berry M.J.A.,
Linoff G.S. – 2nd ed. Wiley-Interscience, New York, NY, USA, 2004,
pages 643.
3.
Chen Z. Data Mining and Uncertain Reasoning: An
Integrated Approach. Wiley-Interscience, New York, NY, USA, 2001, pages 392.
4.
Fayyad U.M., Piatetsky-Shapiro G., Smyth P., Uturusamy
R. (eds.), Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press,
Cambridge, MA, 1996.
5.
Holte R.C. Very Simple Classification Rules Perform
Well on Most Commonly Used Datasets, Machine Learning, 11/1. 1993.
6.
http://kdnuggets.com/datasets/kddcup.html
7.
http:://www.ics.uci.edu/~mlearn/MLRepository.html
8.
Pyle D. Data Preparation for Data Mining. Morgan Kaufmann
Publishers, New York, NY, USA, 1999, pages 540.
9.
Vagin V.N., Akchurina N.R. New Techniques for Handling
Missing Data and Feature Extraction for Knowledge Discovery. Knowledge-Based
Software Engineering. Proceedings of the Sixth Joint Conference on Knowledge-Based
Software Engineering. V. Stefanuk and K. Kaijiri (Eds.). IOS Press, 2004, pp.
169-176.
10.Акчурина Н.Р., Вагин В.Н.
Обобщенная задача разбиения значений атрибутов на основе теории приближенных
множеств. ИЗВЕСТИЯ АКАДЕМИИ НАУК. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2004, №2, с.
69-85.
11.Акчурина Н.Р., Вагин В.Н., Алгоритм
обработки качественных и числовых атрибутов с отсутствующими значениями в
задачах индуктивного обобщения. Девятая Национальная конференция по
искусственному интеллекту с международным участием КИИ-2004 (28 сентября - 2
октября 2004 г., Тверь): Труды конференции. В 3-х т. Т.1. М.: Физматлит, 2004.
466 с. c. 202.
12.Вагин В.Н., Головина Е.Ю.,
Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в
интеллектуальных системах / Под ред. В.Н. Вагина, Д.А. Поспелова. – М.:
ФИЗМАТЛИТ, 2004. – 704 с.