ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 1595
Скачиваний: 34
156
б) Алгоритм Дж. Мак-Кина предложен в 1967 году. Он
отличается от метода Бола и Холла тем, что при просмотре
списка объектов пересчет центра масс класса происходит
после присоединения к нему каждого очередного объекта.
Этот алгоритм связан с функционалом качества разбиения
S
Q
1
- сумма внутриклассовых дисперсий.
2. Алгоритм «Форель». Первоначальное название этого
алгоритма было: ФОРЭЛ – ФОР малый ЭЛемент. Этот
алгоритм предложен в 1966 году Елкиной В.Н. и Загоруйко
Н.Г. Этот алгоритм выполняется следующим образом.
Случайный объект объявляется центром класса; все объекты,
находящиеся от него на расстоянии не большем R, входят в
первый класс. В нем определяется центр масс, который
объявляется новым центром класса и т.д. до стабилизации
центра. Затем все объекты, попавшие в первый класс,
изымаются, и процедура повторяется с новым случайным
центром.
После проведения классификации важно в удобной
форме представить ее результаты. Для этого необходимы
следующие характеристики классификации.
1.
Распределение номеров объектов по номерам
классов.
2.
Гистограмма межобъектных расстояний.
3.
Средние внутриклассовые расстояния.
4.
Матрица средних межклассовых расстояний.
5.
Визуальное представление данных на плоскости
двух
(в
пространстве
трех)
«наиболее
информативных» признаков.
6.
Дендрограмма для иерархических процедур.
7.
Средние значения и размахи во всех классах для
каждого признака.
Последний пункт очень важен, так как в большинстве
случаев описание классов происходит по средним значениям
признаков в них. Сопоставление средних значений для
заданного признака наиболее просто осуществляется, если
157
классы не имеют наложения проекций. Степень разделенности
классов по каждой оси можно охарактеризовать с помощью
коэффициента
i
j
R
L
/
,
где
R
i
– размах по заданному признаку
l
– го класса, а
,...
,
2
1
L
L
- длины наложений проекций классов на ось
признака. Если γ=1, то классы полностью разделены. Чем
ближе γ к 0, тем больше наложение проекций классов друг на
друга.
10.7. Алгоритм K – внутригрупповых средних
Рассмотрим компьютерную реализацию алгоритма K –
внутригрупповых средних. Этот алгоритм наиболее часто
используется в задачах классификации объектов. Он также
используется для организации входных данных для нейронных
сетей. Алгоритм, представленный ниже, минимизирует
показатель качества, определенный как сумма квадратов
расстояний всех точек, входящих в кластерную область, до
центра кластера. Эта процедура, которую часто называют
алгоритмом, основанным на вычислении К внутригрупповых
средних, состоит из следующих шагов.
Шаг 1
.
Выбираются К исходных центров кластеров
z
1
(1),
z
2
(1), . . .,z
k
(1).
Этот выбор производится произвольно, и обычно в
качестве исходных центров используются первые К результатов
выборки из заданного множества объектов.
Шаг 2.
На k-м шаге итерации заданное множество объектов
{
x
}
распределяется по К кластерам по правилу:
)
(
)
(
),
(
k
z
x
k
z
x
если
k
S
x
i
j
j
(10.12)
для всех
i
=
1, 2, …,K,
i≠j
, где
S
j
(k)
– множество объектов,
входящих в кластер с центром
z
j
(k).
В случае равенства в (10.12)
решение принимается произвольным образом.
Шаг 3.
На основе результатов шага 2 определяются новые
центры кластеров
z
j
(k+1), j=1, 2, …,К,
исходя из условия, что
сумма квадратов расстояний между всеми объектами,
158
принадлежащими множеству
S
j
(k),
и новым центром кластера
должна быть минимальной. Другими словами, новые центры
кластеров
z
j
(k+1)
выбираются таким образом, чтобы
минимизировать показатель качества
)
(
2
,...,
2
,
1
,
)
1
(
k
S
x
j
j
j
K
j
k
z
x
Q
. (10.13)
Центр
z
j
(k+1),
обеспечивающий минимизацию показателя
качества, является в сущности, выборочным средним,
определенным по множеству
S
j
(k).
Следовательно, новые центры
кластеров определяются как
,
,...,
2
,
1
,
)
(
1
)
1
(
K
j
k
j
S
x
x
j
N
k
j
z
(10.14)
где
N
j
– число выборочных объектов, входящих в множество
S
j
(k).
Очевидно, что название алгоритма «К внутригрупповых
средних»
определяется
способом,
принятым
для
последовательной коррекции назначения центров кластеров.
Шаг 4.
Равенство
z
j
(k+1)= z
j
(k) при j=1, 2, …, К
является
условием сходимости алгоритма, и при его достижении
выполнение алгоритма заканчивается. В противном случае
алгоритм повторяется от шага 2.
Качество работы алгоритмов, основанных на вычислении К
внутригрупповых средних, зависит от числа выбираемых
центров кластеров, от выбора исходных центров кластеров, от
последовательности осмотра объектов и от геометрических
особенностей данных. Хотя для этого алгоритма общее
доказательство сходимости не известно, получение приемлемых
результатов можно ожидать в тех случаях, когда данные
образуют характерные гроздья, отстоящие друг от друга
достаточно далеко. В большинстве случаев практическое
применение
этого
алгоритма
потребует
проведения
экспериментов, связанных с выбором различных значений
параметра К и исходного расположения центров кластеров.
159
Лабораторная работа № 8. Реализация алгоритма
K – внутригрупповых средних в пакете MATHCAD
Целью лабораторной работы является программная
реализация алгоритма K – внутригрупповых средних для
корректирования
центров
исходных
классов.
Классы
составляют случайные величины с различными законами
распределения.
Задачами лабораторной работы являются:
формирование случайных величин с нормальным,
равномерным
и
экспоненциальным
законом
распределения с использованием математического
пакета MATHCAD;
описание эталонных образов классов в виде векторов,
характеристиками которых являются: математическое
ожидание,
дисперсия,
среднеквадратическое
отклонение,
эксцесс
и
асимметрия
законов
распределения;
применение алгоритма К– внутригрупповых средних
для корректирования центров исходных классов
случайных величин с рассмотренными законами
распределения.
Пример выполнения задания
В качестве примера представлен графический интерфейс
программы, выполненной в среде Borland Delphi 7. Форма,
предназначенная
для
реализации
алгоритма
К
-
внутригрупповых средних, показана на рис. 10.4.
160
Рис. 10.4. Форма для алгоритма К– внутригрупповых средних
При запуске алгоритма выдается сообщение о том, что идет
обработка введенного вектора (рис. 10.5).
Рис. 10.5. Сообщения, выдаваемые при обработке вектора
После выполнения алгоритма в окне результатов будут
выведены скорректированные центры исходных классов (рис.
10.6).