2

∑Ф(x j , xp ),

У

Ф( А, А) =

(2.1)

N А (N А −1)

j, p; p> j

Т

где NA

– число объектов в классе, суммирование происходит

так, что j принимает все значения от 1 до n, а p – для каждого j

все значения, большие j, NA (NA – 1)/ 2 – (число сочетаний из NA

по 2) – количество членов суммы. Иными словами, Ф (А, А) про-

порционален сумме потенциалов, взаимно создаваемыхН

друг

й

на друге всеми точками класса. Очевидно, что Ф (А, А) тем

больше, чем теснее между собой расположеныБточки внутри

и

класса, чем компактнее класс.

Введем величину

kсреднегоi=1

«

собственного потенциала»

данной классификации

о

1

k

т

∑

F

=

Ф(А , А ),

(2.2)

и

1

i i

где k –

если

ч сло классов в классификации. По-видимому,

з

сравнивать между собой несколько разных классификаций, то

жно

величина F1 будет максимальной у той из них, в которой точ-

ки кажд го класса в среднем лежат наиболее тесно. Величину

п

принять за первый критерий оптимизации, а ее мак-

F1

м

симальн е значение будет соответствовать классификации,

о

тимальной с точки зрения этого критерия.

Р

Вторым критерием оптимизации должна быть величина,

характеризующая близость классов между собой. В качестве

еэтой величины примем

31

F2 =

2

∑k

Ф(Аi , Аj ),

(2.3)

k(k −1) i, j; j>i

где k – число классов в классификации, а Ф (Аi, Аj) – мера

близости между классами Аi

и Аj.Суммирование производится

У

так, что i принимает все значения от 1 до k, а значения j вы-

бираются для каждого i выбираются так,

чтобы они были

Т

больше i. Если сравнивать между собой несколько разных

классификаций, то величина F2 , очевидно, будет минимальна

у той из них, где классы в среднем расположены дальше друг

от друга. Величину F2 можно принять за второй критерий оп-

Б

тимизации, а ее минимальное значение будет соответствовать

классификации, оптимальной с точки зрения этого критерия.

Пpи отыскании наилучшей классификации на Носнове анализа

й

множества альтеpнативных ваpиантов необходимо пpинять pе-

шение по выбоpу оптимального ваp

, т. е. pешить задачу вы-

pаботки пpедпочтения

ианта

сpеди некотоpого множества альтеpн-

р

ативных классификаций. Ваp

ант класс фикации, выбpанный по

одному критерию, может оказаться неудовлетвоpительным с

о

точки зpения другого, не менее важного критерия. Для достиже-

ния нужного эффекта пpинятие окончательного pешения пpедла-

ции по воляет отнестиэту задачу к pазpяду многокpитеpиа-

гается осуществи ь на

сн ве сpавнения классификаций по зна-

чениямих

кри ериев.

Такая постановка задачи поиска оптимальной классифика-

го

льных.

П чти всеобоихматематические методы оптимизации пpедназ-

п

здля тыскания оптимального pешения одной функции –

начены

одн

кpитеpия. Поэтому одним из вариантов решения мно-

е

гокpитеpиальных задач является ее приведение к однокpите-

Р

pиальной с одним обобщенным критерием.

Пpи отыскании наилучшей классификации искомый обоб-

F = F1 – F2 .

(2.4)

Та классификация из нескольких альтернативных класси-

фикаций одной и той же совокупности объектов, для которой

критерий F принимает максимальное значение, очевидно, яв-

ляется в определенном смысле объективно оптимальной клас-

сификацией.

Н

У

Задание

Б

Т

1. Разработать программу классификации объектов, реали-

зующую алгоритм оптимальной классификации.

2.

Определить оптимальное число классов для объектов,

и

предложенных преподавателем.

3. Для защиты работы предъяв ть программу и получен-

р

ные результаты классификац

объектовй.

Л и т е

а т у р а

т

1. Zadeh L.A. Fuzzy Sets. Information and Control. – Vol. 8. –

1965.

и

о

з

2. Аркадьев А.Г., Браверман Э.М. Обучение машины клас-

сификации объектов. – М.: Наука, 1981.

о

3. Ай ерман М.А., Браверман Э.М., Розоноэр Л.И. Метод

тенциальных функций. – М.: Наука, 1987.

п

е

Р

33

У

Т

Н

Б

й

и

р

о

т

и

з

о

п

е

Р

СЕКУЩИХ ПЛОСКОСТЕЙ. . .

. . . . . .

. . . . . . . . . .

. . . .

3

Л а б о р а т о р н а я р а б о т а № 2. АЛГОРИТМ

У

ОПТИМАЛЬНОЙ ОБЪЕКТИВНОЙ

КЛАССИФИКАЦИИ.

. . . .

. . . .

. . . . . . .

. . . . . . . . . .

. . .

30

Т

Л и т е р а т у р а. . .

. . . .

. . . .

. . . .

. . . . . .

. . . . . . . . . .

. . .

33

Н

Б

й

и

р

о

т

и

з

о

п

е

Р

У

Т

Н

Б

й

и

р

о

т

и

з

о

п

е

Р

Учебное издание

Н

У

МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

Т

Б

Лабораторные работы

по дисциплине

«Алгоритмы

распознавания образов: алгоритм секущих

и

плоскостей и алгоритм оптимальной классификации»

для

студентов спец альности

р

1–40 01 02 «Информац онныейс стемы и технологии

( нап авлен ям)»

по

специализации 1–40 01 02-01 «Информационные системы

т

и технологии в пр ектировании и производстве»

ави

Сос

ель КОВАЛЕВА Ирина Львовна

з

Редактор Печать офсетная. Гарнитура Таймс.

А.М. Кондратович. Корректор М.П. Антонова

п

Компьютерная верстка А.Г. Гармазы

Подписано в печать 15.03.2004.

Р

Ф рмат 60 х 84 1/16. Бумага типографская № 2.

Усл.печ.л. 2,0. Уч.-изд.л. 1,5. Тираж 100. Заказ 478.

е

Издатель и полиграфическое исполнение:

Белорусский национальный технический университет.