4867

41

yi ), i = 1.. .10, без указания их классификации. Количество наблюдаемых классов не известно.

Координаты точек t>i указаны в табл. 4.1. Таблица 4.1

Условимся для обозначения конкретной точки ^ из множества данных использовать ее порядковый номер i согласно табл. 4.1.

3. Нанесем точки на координатную плоскость x0y, как показано на рис.

4.1.

4. Определим расстояния dij между всеми возможными парами точек i = 1.10, j = 1.10:

Результаты расчетов представлены в табл. 4.2.

Рис. 4.1. Изображение исходных данных

5.Полученные значения расстояний dij можно рассматривать как N (N = 45 - объем выборки) независимых значений одной случайной величины d.

Упорядочим расстояния dij по возрастанию. Результаты сортировки представим в виде табл. 4.3, где к - количество пар точек, расстояние между которыми равно d.

Чтобы упростить статистическую обработку данных, выберем в качестве середин разрядов ряда распределения d повторяющиеся результаты расчетов

42

расстояний du (i = 1...13 - номер разряда) (см. табл. 4.3).

Для более наглядного представления о величинах расстояний между точками выборочного множества построим полигон распределения расстояний. Полигон (рис. 4.2) - это ломаная линия, соединяющая точки с абсциссами di (середины разрядов) и ординатами ri(относительными частотами). Относительной частотой (иначе эмпирической вероятностью) называется число наблюдений в i-м

разряде к, отнесенное к объему выборки N:

r = k i / N .

Таблица 4.2

Таблица 4.3

43

Рис. 4.2. Полигон распределения расстояний междУ парами точек

1.Проведем предварительный анализ меры рассеяния dj выборочного множества. Наиболее удалены друг от друга точки (1) и (10), предполагаем, что

они относятся к различным классам а1 и а2. Пусть для определенности (1) е а1, (10) е а2.

В качестве начальной точки алгоритмов иерархической группировки возьмем (1).

2.Выполним группировку данных по алгоритму ближайшего соседа. Последовательность шагов алгоритма:

- найдем точку, ближайшую к точке (1). Для этого в строке № 1 табл. 4.2

найдем минимальный элемент d1j ; это d13 = 1.414;

- объединяем точки (1) и (3) в одну группу (класс а1) и переходим к следующей точке группы - (3);

- находим минимальный элемент d3j в строке № 3; min{d3j} = d35 = 1.000; считаем, что (5) е а1, и переходим на строку № 5;

- в строке № 5 min{d5j} = d57 = 1.414, относим точку (7) к классу а1 и переходим на строку № 7;

-в строке № 7 min{d7j} = d79 = 1.414, (9) е а1;

-в строке № 9 находится единственный элемент - d910, и мы не можем от-

нести точку (10) к группе точек {1, 3, 5, 7, 9}, поскольку изначально предполагали, что точки (1) и (10) относятся к разным классам. Следовательно, обрываем цепочку последовательных объединений точек в одну группу.

- переходим к одной из точек, не вошедших в первую группу (класс а1), и повторяем шаги алгоритма.

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

класс а1: {1, 3, 5, 7, 9}, класс а2: {2, 4, 6, 8, 10}.

3. Определим статистические характеристики рассеяния внутри каждого класса:

-класс а1: минимальное расстояние d35 = 1.00, максимальное - d19 =

44

4.12, среднее - da1 = 2.24;

-класс а2: минимальное расстояние d24 = d68 = 1.00, максимальное - d2,10 = 4.47, среднее - da2 = 2.28.

4.Для визуализации результатов группировки соединим линиями пары точек, принадлежащих одному и тому же классу (рис. 4.3, а).

5. Выполним группировку данных по алгоритму дальнего соседа. Считаем, что количество классов объектов не менее двух (K > 2) и гра-

ничные точки (1) и (10) принадлежат разным классам: (1) е а\, (10) е а2. Для работы алгоритма необходимо оценить диаметр группы - наибольшее расстояние между точками одной группы. На рис. 4.2 визуально выделяются четыре моды рассеяния точек:

-мода dl = 1.414 соответствует в основном несвязанным между собой парам точек: (1-3), (4-6), (8-10), т.е. указанные ребра не имеют общих вершин;

-мода d = 2.236 - это расстояние между связанными парами: {(4-5), (4-7), (4-8)}, {(6-2), (6-7), (6-10)}, {(7-3), (7-4), (7-6)}; точки (4), (6) и (7) являются центрами рассеяния с мерой d .

Сравним расстояния от центров рассеяния (4), (6), (7) до граничных точек

(1) и (10) (см. табл. 4.1):

d14 < d17 < d16 (3.16 < 3.61 < 4.47); d10,6 < d10,7 < d10,4 (2.24 < 3.16 < 3.61);

в качестве критерия разброса внутри класса dmax примем d14;

-мода d = 3.126 - расстояние между точками {(8-2), (8-5), (8-9)}; центр рассеяния - точка (8). Ближайшая к (8) граничная точка - точка (10) - находится

на расстоянии d8,10 = 1.414 < dmax = 3.162, поэтому точки (10) и (8) относим к одному классу (а2);

-мода d = 4.472 характеризует разброс между точками из разных классов; это означает, что пары (2)-(9), (2)-(10) и (5)-(10) образуют группы {2, 5} и {9,

10}.

Сгруппируем данные по такому правилу: расстояние от граничной точки до любой другой точки группы не должно превышать dmax = 3.162.

Упорядочим расстояния d1i, d10i (i = 1...10) (табл. 4.4).

Как видно из таблицы, по критерию dmax выделяются две группы: {1, 2, 3, 4, 5} е а1 и {6, 7, 8, 10} е а2 и отдельная точка (9). Ближайшая к точке (9) - точка

(7)и d9,10 = 4.00 < d91 = 4.123, поэтому отнесем точку (9) к классу а2.

Таблица 4.4

45

Таким образом, по алгоритму дальнего соседа получаем: класс а1: {1, 2, 3,

4, 5}, класс a2: {6, 7, 8, 9, 10}.

а- алгоритм ближайшего соседа; б - алгоритм дальнего соседа

Ввыводах по лабораторной работе необходимо проанализировать влияние выбора алгоритма на результаты группировки данных.

46

Библиографический список

Основная литература

1. Ерош И.Л., Сергеев М.Б., Соловьев Н.В. Обработка и распознавание изображений в системах превентивной безопасности: Учебное пособие. - СПб.: ГУАП, 2006. – 153 с. // ЭБС Единое окно доступа к образовательным ресурсам.

– Режим доступа: http://window.edu.ru/resource/964/44964.

Дополнительная литература

2.Макаренко С.И. Интеллектуальные информационные системы: Учебное пособие. - Ставрополь: СФ МГГУ им. М.А. Шолохова, 2009. – 206 с. // ЭБС Единое окно доступа к образовательным ресурсам. – Режим доступа: http://window.edu.ru/resource/462/79462.

3.Лепский А.Е., Броневич А.Г. Математические методы распознавания образов: Курс лекций. - Таганрог: Изд-во ТТИ ЮФУ, 2009. – 155 с. // ЭБС Единое окно доступа к образовательным ресурсам. – Режим доступа: http://window.edu.ru/resource/800/73800.

Грибанов Андрей Анатольевич

Интеллектуальные системы распознавания

Методические указания к лабораторным работам для студентов магистратуры направления подготовки 15.04.04 – «Автоматизация технологических процессов и производств» для очной формы обучения

Редактор С.Ю. Крохотина

ФГБОУ ВО «Воронежский государственный лесотехнический университет имени Г.Ф. Морозова»