Алгоритмы алгебраической и логической коррекции, и их применения
Скачать 0.51 Mb.
|
Таблица 5 n = 3n =5Набор корректируемых эвристик2,5,72,4,72,4,62,3,4,5,72,4,5,6,7Точность лучшей эвристики0,700,740,740,740,74Средняя точность эвристик набора0,680,700,690,680,67Логический корректор0,770,810,770,800,81В условиях эксперимента, дальнейшее наращивание корректируемых наборов приводит к появлению в них алгоритмов с более высокими значениями коэффициентов попарной корреляции. Таблица 6 N = 3n =5n = 7Набор корректируемых эвристик2,4,61,5,83,9,101,2,4,5,61,3,9,10,112,3,4,5,6,9,10Точность лучшей эвристики0,740,670,700,740,740,74Средняя точность эвристик набора0,700,610,660,670,680,67Логический корректор0,740,670,710,740,750,74По результатам проведенных экспериментов можно сделать вывод, что формирование набора из алгоритмов с сильной корреляцией редко приводит к повышению точности распознавания по отношению к лучшему из алгоритмов. Однако и в этом случае применение обучаемых корректоров может быть оправдано. Точность их работы выше средней точности алгоритмов набора, что соответствует точности алгоритма случайно выбираемого из набора. На практике часто нельзя гарантировать независимость работы тех или иных алгоритмов или же точно определить степень их зависимости. В результате этого корректируемые наборы могут содержать алгоритмы с различной степенью статистической близости. В табл. 7 приведены результаты некоторых экспериментов с такими наборами на примере задачи 1. Таблица 7 n = 3n =5n = 7Набор корректируемых эвристик1,3,44,5,61,4,51.4,5,6,71,2,3,6,71,2,3,4,5,6,7Точность лучшей эвристики0,700,670,670,700,740,74Средняя точность эвристик набора0,680,640,650,660,690,68Логический корректор0,720,690,700,730,810,84Анализ данных показывает, что с увеличением точность корректирования растет. В работе получены экспериментальные данные по корреляции результатов распознавания между алгоритмами на реальных задачах. Подобные результаты получены впервые. Хотя по ограниченному объему экспериментов нельзя сделать обоснованных выводов, однако эти результаты представляют широкий интерес, так как корреляция выступает здесь в качестве естественной меры статистической близости между алгоритмами. При решении прикладных задач необходимо, как правило, обеспечить возможность проведения в автоматизированном режиме следующих работ:
Данные проблемы решены в рамках программного комплекса, который можно рассматривать как полигон алгоритмов распознавания с управляющей системой /17/. Его архитектура состоит из следующих основных частей: управляющие подсистемы, пользовательские программы, система управления базами данных (СУБД). Управляющая подсистема выполняет функций по организации работы комплекса и контроля функционирования его компонентов. Пользовательские программы реализуют конкретные алгоритмы распознавания (библиотека алгоритмов) и выполняют пред- и постобработку информации. База данных состоит из наборов данных файла объектов, индексатора и файла подзадач. Программный комплекс данной архитектуры использовался для организации и проведения эксперимента по изучению свойств алгоритмов распознавания, построенных на основе двухуровневой схемы. Проведение подобного рода эксперимента требует значительных затрат, связанных с подготовкой, хранением и манипуляцией различных данных. Функциональные возможности и состав программной технологии позволяют автоматизировать многие рутинные процессы и повысить эффективность его проведения.
Вопрос сравнения различных алгоритмов распознавания и выбор наиболее перспективных для распознавания новых объектов всегда являлся центральным, но не имеющим однозначного ответа. Различные подходы имеют свои предпочтения и ограничения, связанные с длиной обучающей выборки, числом классов и признаков, представительностью описаний каждого класса, типом признаков, «компактностью классов», коррелированностью признаков, «конфигурацией классов», и т.п. Метод, являющийся наилучшим для некоторой прикладной задачи, может оказаться посредственным при решении другой. Естественным сравнительным критерием здесь может быть оценка числа практических задач, на которых некоторый метод занимал лидирующие позиции. Ниже в таблице 8 приводятся подобные сравнения. Для расчетов использовалась программная система «РАСПОЗНАВАНИЕ», в которую интегрированы указанные ниже методы. Строка таблицы соответствует методу распознавания (коррекции), столбец (кроме столбца «N»)– прикладной задаче: ТТ – «алгоритм голосования по тупиковым тестам» /1/, ЛЗ – «алгоритм голосования по системам логических закономерностей» /18/, БД – «бинарные решающие деревья» /19/, ФИШЕР – «линейный дискриминант Фишера» /20/, ЛМ – «линейная машина» /20/, СВМ – «метод опорных векторов» /21/, НейрС – «многослойный персептрон» /22/, Голос – «коллективное решение, как голосование по большинству» /8/, ЛогК – «логический корректор» (раздел 6), АлгК - «алгебраический корректор второй степени» (раздел 4), ОбК – «обобщенный алгебраический корректор» (раздел 5), «Abalone» – задача «распознавание возраста ракушек», l=3, q=2079 , n=8 (автор данных Sam Waugh (Sam.Waugh@cs.utas.edu.au), Department of Computer Science, University of Tasmania, GPO Box 252C, Hobart, Tasmania 7001, Australia), «Eco» - задача «место локализации протеина» l=8 , q=179 , n= 7 /23/, «Breast» - задача «диагностики рака груди» l=2 , q=355 , n=9 /24/, «Credit» - задача «Подтверждение кредитных карточек», l=2 , q=348 , n= 15 /25/, «Home» - задача «оценка стоимости жилья» l=5 , q=264, n=13 /26/, «Image» - задача «распознавание стандартных изображений», l=7 , q=2100, n= 16 /25/, «Ion» - задача «распознавание радиосигналов», l=2 , q=182 , n=34 /27/, «Pnevmo» - задача «Оценка степени тяжести пневмонии», l=4 , q=57, n=41, «Year» - задача «Protein Localization Sites», l=10 , q=747, n= 8 /23/. В столбцах 2-10 представлены оценки точности распознавания различных методов (процент правильно распознанных объектов некоторой выборки) на различных задачах. Для каждой задачи приведены значения числа классов, числа распознаваемых объектов и число признаков. Следует отметить, что параметры алгоритмов использовались «по умолчанию» (задавались автоматически), а не подбирались по данным обучения (например, с помощью минимизации числа ошибок на данных обучения в режиме скользящего контроля). Жирным шрифтом в каждом столбце выделены четыре наилучших результата – «призовые места». В столбце «N» для каждого метода отмечено, сколько раз соответствующий метод занимал призовое место. Таблица 8 Метод \задачаAbalone Eco Breast Credit Home Image Ion Pnevmo YearN ТТ60.663.192.485.363.386.587.961.444.32 ЛЗ56.861.596.182.871.690.890.159.613.91 БД56.773.292.185.167.490.287.457.945.21 Фишер62.477.194.484.876.589.483.554.453.82 ЛМ65.579.394.985.961.792.786.854.432.05 СВМ66.581.694.683.377.791.894.063.265.56 НейрС64.780.495.582.873.592.087.957.959.73 Коллек-тивные Голос63.579.394.982.276.593.993.457.948.34 ЛогК65.476.595.284.878.894.090.768.458.87 АлгК65.081.695.281.076.992.391.261.460.67 ОбК63.580.494.982.878.094.394.066.761.27 Таблица 9 Результаты тестирования метода «АВО-полином» приведены в таблице 9: TaskAVO-polynomAbalone62.3Breast canser96.1Ionosphere98.7Echocardiogram77.4Hepatitis88.0Image89.4Credit86.2Расшифровка задач приведена в /25/ и, частично, в /8/.
В настоящей статье приведены некоторые практические методы логической и алгебраической коррекции эвристических алгоритмов распознавания, а также некоторые результаты их сравнения. Хотя число практических задач было небольшим, полученные результаты являются хорошей наглядной иллюстрацией целесообразности использования корректирующих алгоритмов для повышения надежности результатов распознавания. Особое значение это имеет при использовании программ распознавания неквалифицированным пользователем в автоматическом режиме. Работа выполнена при поддержке проекта НАН Республики Беларусь и Российского фонда фундаментальных исследований №08-01-90016 «Методы построения эффективных признаковых пространств для задач мониторинга и распознавания сложных объектов в составе изображений и сцен». Литература 1. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. Проблемы кибернетики. М.: Наука, 1978. Вып.33. С.5-68. 2. Журавлев Ю.И. Корректные алгебры над множествами не корректных (эвристических) алгоритмов. I. // Кибернетика. 1977. N4. С. 5-17. , II. Кибернетика, N6, 1977, III. // Кибернетика. 1978. N2. С. 35-43. 3. Зуев Ю.А. Метод повышения надежности классификации при наличии нескольких классификаторов, основанный на принципе монотонности// ЖВМиМФ. 1981. Т.21. № 1. С.157-167. 4. Вешторт А.М., Зуев Ю.А., Краснопрошин В.В. Двухуровневая система распознавания с логическим корректором // Распознавание, классификация, прогноз. Математические методы и их применение. Ежегодник. - М.: Наука, 1989. - вып.2. - с.73-98. 5. L.A. Aslanyan, L.F. Mingo, J.B. Castellanos, F.B. Chelnokov, A.A. Dokukin, V.V.Ryazanov// On Logical Correction of Neural Network Algorithms for Pattern Recognition, Proceedings of 4-th international conference “INFORMATION RESEARCH & APPLICATIONS”, Foi-commerce, SOFIA, 2006 6. Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: минимальная степень корректного алгоритма// Журнал вычислительной математики и математической физики, 2005, Т. 45, №6. С.1134-1145. 7. Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: нормировка по отрезку // Журнал вычислительной математики и математической физики, 2009, Т. 49, №1. С.200-208. 8. Ю.И.Журавлев, В.В.Рязанов, О.В.Сенько, РАСПОЗНАВАНИЕ. Математические методы. Программная система. Практические применения. Изд.во «ФАЗИС», Москва, 2006, 168 стр. 9. Журавлёв Ю.И., Исаев И.В. Построение алгоритмов распознавания, корректных для заданной контрольной выборки // Ж. вычисл. матем. и матем. физ., 1979, т. 19, №3, стр. 726-738. 10. Докукин А.А. Об одном методе построения оптимального алгоритма вычисления оценок // Ж. вычисл. матем. и матем. физ., 2006, т. 46, №4, стр. 754-760. 11. Докукин А.А. О построении выборок для тестирования приближённых методов оптимизации алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ., 2006, т. 46, №5, стр. 978-983. 12. Краснопрошин В.В., Образцов В.А. Проблема принятия решений по прецедентности: разрешимость и выбор алгоритмов // Выбраныя навуковыя працы Беларускага Дзяржаунага унiверсiтэта, том 6, матэматыка, 2001, - стр.285-312. 13. Романов М.Ю. Об одном методе построения распознающего алгоритма в алгебре над множеством вычисления оценок // Ж. вычисл. матем. и матем. физ. —2007. — Т. 47, №8. —С. 1426–1430. 14. Романов М.Ю. Реализация одного метода построения распознающего алгоритма в алгебре над множеством алгоритмов вычисления оценок // Ж. вычисл. матем. и матем. физ. —2008. — Т. 48, №9. 15. Вешторт А.М., Кашкевич С.И., Костюкевич С.Б., Краснопрошин В.В., Синякович С.Г. Принципы построения информационной автоматизированной системы данных аэрокосмического спектрометрирования для целей физико-географического районирования // Известия АН СССР, сер. географ. - М, 1988. - с.89-94. 16. ГлушенковВ.С., Ковалев А.А., Коновалов О.Л., Костюкевич С.Б., Краснопрошин В.В., Юхименко Б.А. Система отображения и редактирования цифровых тематических радиационных и экологических карт на основе ПЭВМ // Весцi АНБ, сер. фiз.-мат.-навук - Мiнск, 1992. - Т5-6. - с.102-107. 17. Гафуров С.В., Краснопрошин В.В. Программная технология построения систем для решения задач распознавания со сложной структурой// Искусственный интеллект. 2008, №1, -с.30-37. 18. Рязанов В.В. Логические закономерности в задачах распознавания (параметрический подход) // Журнал вычислительной математики и математической физики, Т.47, №10, 2007, с.1793-1808. 19. Донской В.И. , Башта А.И. Дискретные модели принятия решений при неполной информации. –Смферополь: Таврия, 1992. – 166 с. 20. Дуда Р., Харт П., Распознавание образов и анализ сцен. Издательство "Мир", Москва, 1976, 511 с. 21. Christopher J.C. Burges. A Tutorial. on Support Vector Machines for Pattern Recognition, Appeared in: Data Mining and Knowledge Discovery 2, 121-167, 1998. 22. Уоссермен Ф., Нейрокомпьютерная техника, М.,Мир, 1992. 23. Horton Paul, Nakai Kenta //"A Probablistic Classification System for Predicting the Cellular Localization Sites of Proteins",Intelligent Systems in Molecular Biology, 109-115. St. Louis, USA 1996.
26. Harrison, D. and Rubinfeld, D.L. Hedonic prices and the demand for clean air, J. Environ. Economics & Management, vol.5, 81-102, 1978. 27. Sigillito, V. G., Wing, S. P., Hutton, L. V., \& Baker, K. B. (1989). Classification of radar returns from the ionosphere using neural networks. Johns Hopkins APL Technical Digest, 10, 262-266 1 Работа выполнена при поддержке проекта НАН Республики Беларусь, грантов Российского фонда фундаментальных исследований №№ 08-01-90016, 08-01-00636-а, 09-01-00409-а, гранта Президента РФ НШ-5294.2008.1, программ поддержки фундаментальных исследований Президиума РАН (П-2) и Отделения математических наук РАН. 2 Учреждение Российской Академии наук Вычислительный центр им. А.А. Дородницына РАН; 119333, Москва, Вавилова 40; тел. +7 499 1352489; факс. +7 499 1356159. 3 Белорусский государственный университет; Белоруссия, 220030, Минск, пр. Независимости, 4; тел./факс. +375 17 2095203. |
Похожие:
 | Рассматриваются алгоритмы комбинирования нескольких методов распознавания, оптимизированные к различным деформациям образов символов.... | | На «Программу тренинговых занятий по коррекции агрессивного поведения у учащихся начальной школы» |
 | Цель мастер-класса: повысить мотивацию коллег к овладению приёмами коррекции импульсивного поведения учащихся, создать условия для... | | Составители: ГильмановаЕ. Д.,старший методист бу «Центр психолого-педагогической реабилитации и коррекции» |
| Для достижения целей обучения, воспитания и коррекции речевого развития детей необходимо активное взаимодействие всех субъектов коррекционно... | | Открытого акционерного общества «северо-западный центр конактной коррекции зрения «контакор» за 2016 год |
| Константы, переменные, выражения, функции в языке Fortran. Линейные алгоритмы. Управляющие конструкции языка Fortran. Простые циклы... | | Программа определяет содержание логопедической коррекции обучающихся 1 4 классов специальной (коррекционной) образовательной школы... |
| ... | | ... |