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

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



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} — разбиение обучающей выборки

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

189

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

2008. Вып.2

на классы (эталоны) Nj, j G 1₁—{1, 2,... ,t}; f : Im ^ It — классифицирующая функция, закрепляющая номера i G Iₘ элементов обучающей выборки Xi G O за номерами эталонов-классов Nj G S, j G 1₁.
   Тогда известные [1] в теории распознавания (классификации) задачи конструктивизируются на языке расширенного исчисления предикатов следующим образом [2, с. 8].
   1. Распознавание:


           (Ух G M)[х G X] = | ¹, “ G X „      _
                            ( 0, в противном случае.


   2. Идентификация:

           (Ух G O)[X = Xi

   3. Классификация:

           (Ух G O)[X G Nj


( 1, если X = Xi, i G Iₘ;
[ 0, в противном случае.

Г 1, если X G Nj, j G 11; [ 0, в противном случае.

   Без потери общности ограничимся рассмотрением проблем разреши

мости и вычислимости задач классификации.

   Проблема разрешимости: существует ли алгоритм, определяющий при

надлежности неизвестной реализации X образа х одному из классов разбиения Nj, то есть вычисляющий предикат P(х = (хi,х2,...,хп)), где х = (х 1, х2,..., хп) — набор признаков в описании образа.

   Проблема вычислимости — установление эффективной процедуры вы

числений разрешимых предикатов классификации P (х).
   Проблемы вычислимости и разрешимости тесно связаны [3, с. 30]: предикат P(х) разрешим, еели функция cₚ(х) вычислима; предикат P(х) неразрешим, если функция cₚ(х) невычислима, где P(х = (х 1, х2,..., хп)) n -местный предикат на натуральных числах; cp(х) — характеристическая


функция:

ср ⁽х⁾ = |

1,
0,

если P(х) истинно, если P(х) ложно.


   Определения разрешимости и вычислимости, рассматриваемые в данной работе, применимы к функциям и предикатам от натуральных чисел. Но это не является существенным ограничением, поскольку операции, включающие другие виды объектов, могут быть закодированы как операции с натуральными числами [3, с. 31].