Исследование свойств линейных метрических алгоритмов распознавания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Вв едение .стр.

ГЛШ I.

§ I. Основные понятия и определения. Алгоритм Н.Z Ч

§ 2. О решающем правиле алгоритма Н.3.

§ 3. Сильная и слабая Н - разделимость.43.

§ 4. О погрешности распознавания алгоритма Н.53.

ГЛАВА П.

§ I. Линейные метрические алгоритмы распознавания.^

§ 2. Сокращение признакового пространства.Я

ГЛАВА Ш.

§ I. Реализация алгоритма классификации .НО

§ 2. Решение задачи распознавания на примере задачи из геологии и социально-экономической области.

Ли т е р а т ур а.12&

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

Одним из наиболее простых и естественных уточнений понятия "близости" является уточнение, основанное на метрике в пространстве признаков. Такое уточнение приводит к классу метрических алгоритмов распознавания, внутри которого выделяется важный подкласс - класс линейных метрических алгоритмов распознавания, одним из стандартных представителей которого является алгоритм Н, основанный на метрике Хемминга в пространстве бинарных признаков.

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

Диссертация состоит из оглавления, введения, трех глав, приложения и списка литературы.

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

В главе П на основе проведенного в главе I изучения свойств алгоритма Н , вводится дяя описания алгоритмов распознавания (классификации) модель метрических алгоритмов распознавания, важным подклассом которых является класс линейных метрических алгоритмов. Показывается, во-первых, что линейные метрические алгоритмы и (с некоторым дополнительным ограничением) только они в качестве разделяющей гиперповерхности строят гиперплоскость, а кроме того, что алгоритм Н является стандартным представителем этого класса, откуда следует справедливость результатов, полученных в главе I для алгоритма Н , применительно к произвольному линейному метрическому алгоритму распознавания. Далее в этой главе в теоретическом аспекте исследуется вопрос о возможности сокращения множества признаков. Доказывается, что поставленная задача является

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

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

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

В приложении приводится ФОРТРАН-программа алгоритма.

Перейдем к определениям и точным формулировкам полученных результатов.

1. Константинов P.M., Королева З.Е., Кудрявцев В.Б,О комбинаторно-логическом подходе к задачам прогноза рудоносности. Сб. "Проблемы кибернетики", вып. 31, М., "Наука", 1976, с. 5-33.

2. Журавлев Ю.И. Алгебраический подход к задачам распоз-нования. В сб. "Проблемы кибернетики", вып. 33, М.: Наука, 1978, с. 5-68.

3. Переяславский В.И, Об одном линейном методе распознавания образов. В сб. "Комбинаторно-алгебраические методы в прикладной математике", Горький, изд-вр ГГУ, 1982, с. 89-121.

4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике, М#: Наука, 1977, стр. 367.

5. Никольский С.М. Курс математического анализа, том I. М.: Наука, 1983, стр. 464.

6. Гэри М., Джонсон Д. Вычислительные машины и трудыоре-шаемые задачи. М.: Мир, 1982, стр. 416.

7. Карп P.M. Сводимость комбинаторных задач. Кибернетический сборник. М.: Мир, 1975, с. 16-38.

8. Ахо А., Хопкрофт Дж«, Ульман Дж. Построение и анализ вычислительных алгоритмов. М.; Мир, 1979.

9. Кук С,А. Сложность процедур вывода теорем. Кибернетический сборник, нов. сер., вып. 12. М.: Мир, 1975, с. 5-15.

10. Райзер Дж.Г. Комбинаторная математика. М.: Мир, 1966, стр. 152.

11. Александров А.Д. Внутренняя геометрия выпуклых поверхностей. Гостехиздат, 1948, стр. 386.

12. Айзерман М.А., Браверман Э.М. и Розоноер Л. Теоретические основы метода потенциальных функций в задаче об обучении автоматов разделению входных ситуаций на классы.Автоматика и телемеханика, 1964, том 25, №6, стр. 917936.

13. Сиротинская G.B. Метод вариационных рядов и его применение к исследованию некоторых геологических особенностей оловянно-вольфрамовых месторождений. В сб. Логико-информационные решения геологических задач. -M.s Наука, 1975, с. 5-82.

14. Кудрявцев Вит.Б., Чижова Й.А. Дифференированая оценка рекреационных территорий. В сб. Математические методы в биологии. М.: МГУ, 1985.

15. Шайеб А. Об одном алгоритме распознавания типа голосования. В сб. Дискретная математика и ее приложения. M.S МГУ, 1985.

16. Шайеб А., Болотов А.А. О линейных метрических алгоритмах распознавания. Тезисы ■УХВсесоюзной конференции по математической кибернетике, Саратов, 1983.

17. Шайеб А. К задаче сокращения признакового пространства в алгоритмах распознавания. В сб. Дискретная математика и ее приложения. М.: МГУ, 1985.