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

• Автор: Шайер, Азар
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Москва
• Количество страниц: 192 c. : ил

Вв едение
ГЛАВА I.

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

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

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

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

Глава II.

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

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

Глава III.

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

§ 2. Решение задачи распознавания на примере задачи из
геологии и социально-экономической области
Ли т е р а т ур а
ПРИЛОЖЕНИЕ - *'

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

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

Д о к а з а т ельство. Необходимость теоремы вытекает из определения сильной Н -разделимости множеств, поэтому проверим только ее достаточность. Пусть А/,<гг % и MJ &е, два непустых подмножества множеств
М< и соответственно. По условию теоремы, в частности, имеем
ŸJ I ÎL , .
Отметим, что М,,' ~ <{#ij .. V и
мл=и{1^10... (j{ïç,l
Применяя последовательно лемму, получим
Щ К*
Еще раз применяя последовательно лемму, получим окончательно:
н я Mi
Т. в. М, и И; слабо Н -разделимы при помощи М и Mi • Так как М] и были произвольными подмножествами, ТО ПО определению имеем ДЛЯ множеств М-l и МА сильную И -разделимость-. Теорема доказана.
Используя доказанную теорему, сильную Н -разделимость двух множеств М.| и Мд, можно охарактеризовать и в терминах конусов, связанных с этими подмножествами.
Пусть К — &>п.(М) , К - Со п. ( М) » где множества М И м определялись ПО М* И Ml выше, и К*
есть выпуклый конус, двойственный к