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

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

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

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

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

В главе 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, стр. 917 936.

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

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

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

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

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