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

I. ВВЕДЕНИЕ.

1. Основные понятия, методика исследования и постановка задачи.

1.1. Предварительные сведения .1Я

1.2. Постановка задачи

2. Классы алгоритмов

2.1. Разделяющие плоскости

2.2. Метод потенциальных функций

2.3. Алгоритм распознавания, основанный на вычислении оценок.

2.4. Алгоритм, основанный на формировании дере вьев.

2.5. Алгоритм распознавания именованных, номинальных признаков

3. Вамыкание классов алгоритмов

3.1. Общая схема построения замыкания

3.2. Построение замыканий алгоритмов

33. Вычисление параметров в замыкании

3.4. Описание алгоритма в общем виде

3.5. Переход к строгим неравенствам системы

3.6. Схема работы алгоритма решения системы строгих неравенств.

4. Применение алгоритмов распознавания к решению задач.

4.1. Построение алгоритма распознавания причин брака в сталеплавильном производстве •

4.2. Пример построения алгоритма распознавания типа голосования для решения задачи геологического прогнозирования

4.3. Применение комплексного алгоритма распознава ния к задачам социологии

В В Е Д Е Н И Е Математическая теория распознавания образов является одной из быстро развивающихся областей прикладной математики и кибер нетики. Эта теория, зародившись в рамках статистической теорий решений, последние два десятилетия приобрела самостоятельное значение, т.к. стала применяться в решении задач, в которых обучающий материал /исходная информация/ является, вообще говоря, ста тистическио не достоверным, В теории распознавания, не связанной прямо с математической статистикой, в настоящее время выделяются три уровня исследова НИИ. Первый уровень состоит в изобретении достаточно правдоподобных алгоритмов решения некоторой конкретной задачи, причем математическое Обоснование пр*швншост*4 таких алгоритмов не производится. Применимость выясняется экспериментальным путем так же, как в физйке, химии и т.д. Алгоритм используется для решения конкретных задач, выясняется его практическая эффективность,и, если она прввьш1ает некоторый заданный порог, алгоритм считается "достаточно хорошим" и применяется для решения прикладных задач.Проблемы, возникающие на первом уровне, связаны обычно с построением эф фективных вычислительных схем, реализующих такие эвристические, некорректные /I/ алгоритмы, и созданием удобных и эффективных программных комплексов. Второй уровень исследования составляют результаты по формированию и изучению отдельных моделей /2/ распознающих алгорит мов. Различные эвристические алгоритмы образуют несколько групп, таких, что алгоритмы, попавшие в одну группу, имеют примерно одинаковую структуру. Группы похожих друг на друга распознающих алгоритмов, удается описать кэк параметрические модели, т.е.такие совокупности объектов, которые допускают единое описание с точностью до теоретико-множественных и числовых параметров. Алгоритм выделяется из модели, если зафиксировать значения всех этих параметров, В связи с вышеизложенным ввникэют следующие задачи: описание совокупности структурно П О Х О Ж И Х алгоритмов как единой параметрической модели; выделение алгоритма,максимально эффективного для решения данной конкретной задачи. При решении задач второго уровня возникает необходимость исследования специальных экстремальных проблем, связанных с выбором оптимального по эффективности алгоритма. Обычно под эффективностью распознающего алгоритма, если заранее неизвестно строение множества распознаваемых объектов, понимается его точность при распознавании заранее заданного контрольного материала. Ищется алгоритм_,максимально точный на заданном контроле или, что то же самое, значение параметров, определяющих этот алгоритм. Возни кающая здесь проблематика в определенной степени повторяет проблематику, возникающую при решении обычных задач оптимизации.Учитывая то, что аначительная часть работ по теории распознавания относится именно ко второму уровню, теорию распознавания часто отождествляют с теорией решений или теорией оптимальных решений /3/. Последнее, по-видимому, справедливо, если ограничиться рассмотрением проблем выбора оптимального алгоритма в рамках фиксированной параметрической модели. Третий уровень исследования связан с тем, что для алгоритмов вводятся алгебраические или логические операции, повышающие их эффективность. Таким образом, появляются алгебраические или логические замыкания семейств распознающих алгоритмов. Выбор оптимальных алгоритмов в таких замыканиях в некоторых случаях сводитб. ся к решению задач второго уровня задач оптимизации/, э в других к прямому построению оптимальных алгоритмов с помощью методов алгебры или логики. Очевидно, что логические и алгебраические операции могут применяться как в наудачу выбранных эвристических алгоритмах, так и в алгоритмах, экстремальных в своих моделях. Предлагаемая диссертация является работой, в которой предложены некоторые новые эвристические алгоритмы, как, например, алгоритм, основанный на формировании структур. Этот алгоритм бази руется на правдоподобных предположениях /4/ и является достаточно эффективным при решении некоторых прикладных задач. В диссертации также исследована задача двух указанных направлений второго уровня. Для групп похожих алгоритмов например, алгоритмы с

1. Журавлев Ю.И. Экстремальные алгоритмы в математических моделях для задач распознавания.и классификации. Доклады .Академии наук СССР, 1976, том. 231, Л 3, с. 532-535.7. .Распознавание образцов. Вып. I/Под ред. Ростриги-на Л.А. Рига: Зинатис, 1974.

2. Себестьян. Г.О. Процессы принятия решений при распознавании образцов. -К.: Техника, 1965.

3. Алгоритмы обучения распознавания образцов. /Под ред. Вапник В.И. М.: Советское радио, 1973.

4. Фу К. Последовательные методы в распознавании образцов и обучении машин. М.: Наука, 1971. - 256 с.

5. Васильев В.И. Распознающие системы. -К.: Наукова думка, 1969. 292 с.

6. Аркадьев А.Т., Браверман Э.М. Обучение машины классификации объектов. -М.: Наука, 1971.

7. Загоруйко Н.Т. Методы распознавания и их применения. М.: Советское радио, 1972. - 204 с.

8. Айзершн М.А. и др. Методы потенциальных функций в теории, обучения машин. /М.А.Айзерман, Э.М.Браверман, Л.И.Ро-зеноэр, М.: Наука, 1970.

9. Горелик. АЛ. и др. Построение. систем распознавания. /Л.А.Горелик,- В.А.Сйсрыпкин. -.:.Советское радио, 1974, 224 с.

10. Дуда Р., Хорт П. Распознавание образцов и анализ сцен. Пер. с англ. - М.: Мир,.1976. - 511 с.19. ^Линейные неравенства и смежные вопросы. М.: йн. лит-ра, 1959. . .

11. Первозванский А.А. Поиск. -М.: Наука, 1970. 263 с.

12. Черников С.И. Линейные неравенства. М.: Наука, 1968.

13. Гейл Л. Теория линейных экономических моделей. -М.: Ин. литература, 1963.

14. Опыт применения методов теории распознавания к задаче оценки деловых качеств работника. /Ю.И.Журавлев, А.И.Зен-кин, Н.Б.Скоробогатов и др. В кн.: Вопросы радиоэлектроники. Вып. 3. М., 1974, с. 28-44.

15. Системный анализ определения брака по химическому составу листовой стали. /А.С.Ленович, В.Б.Судейко, Я.Л.Райхман, И.М.Хорошилов и др. В кн.: Производство стали. Вып.1.M., 1972, с. 31-32.

16. Ленович А.С. Алгоритмы распознавания влияния элементов химического состава на механические свойства стали. -Кибернетика, 1974, £ 3.

17. Ленович А.С., Ткачева Л.Р. Метод определения весов именованных признаков в алгоритмах на графах для задач с частично упорядоченными классами включен в ФАП 15 июня 1977 г.Л 000002.

18. Ленович А.С., Ткачева Л.Р. Метод нахождения решения системы строгих линейных однородных неравенств включен в ФАП 10 мая 1981 г. Ш Л 000003.

19. IEEE TMMAcr/Wsr ом cowpxrf/ts, 6-tz0. /2 Decesndf?,/?

20. IEEE TRANSACTIONS OF COMPUTERS VOL. C-22, Ho 12, December, 1973. An Algorithm for the Optimal Solution of Linear Inequalities and Its Application to Pattern Recognition.

21. Построение замыкания распознающих алгоритом. Ленович А.С. Рукопись деп. в УкрНИЙНТИ 18 октября 1983 г.,Л II58 Ук-Д-83.