Конструктивизация в классификации образов


ВЕСТНИК УДМУРТСКОГО УНИВЕРСИТЕТА

КОМПЬЮТЕРНЫЕ НАУКИ



2008. Вып.2

УДК 519.712 : 510.25 : 510.67

© Н. И. Калядин




                КОНСТРУКТИВИЗАЦИЯ В КЛАССИФИКАЦИИ ОБРАЗОВ




Изучаются проблемы разрешимости и вычислимости, предопределяющие концепцию конструктивизации в задачах классификации образов.
Ключевые слова: разрешимость, вычислимость, классификация образов, конструктивизация .




                Введение




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




                §1.0 проблемах в классификации образов




                                 k
   Рассматривается множество M = |J Mi классифицируемых (распо-i =1
знаваемых) образов (конечных объектов) x произвольной природы.
   Первым шагом при конструктивизации является формализация исходного описания образа x Е M для перехода от физической или семантической модели к математической.
   Для этого с помощью подходящей редукции р : M ^ N—{0,1, 2,...} осуществляется переход (кодирование) к натуральным числам. Дальнейшая формализация выполняется на единой алгоритмической основе — теории рекурсивных функций [4].
   Пусть р : M ^ Ф, где Ф — семейство всех конечных подмножеств множества натуральных чисел N; (M, р) — множество конструктивных объектов; O—{X1, Х₂,• • •, Xт} — обучающая выборка известных реализаций (описаний) Xi, i Е Iт—{1, 2,... ,m} образа x; X — неизвестная реализация образа x; S—{N1, N₂,• • •, Nt} — разбиение обучающей выборки