Нов.ПМС-2

12 5 6 2 10 12 2 2,24 ,

а между первым и третьим объектами

13 5 5 2 10 13 2 3.

Очевидно, что 11 0 .

Аналогично находим расстояние между шестью объектами и строим матрицу расстояний

объекты наиболее близки 4,5 1,00 и поэтому объединяются

в один кластер. После объединения объектов имеем пять кластеров:

Расстояние между кластерами определим по принципу «ближайшего соседа», воспользовавшись формулой пересчета (10.11). Расстояние между объектом S1 и кластером S(4,5) будет

12 5.10 6.08 12 5.10 6.08 5.10.

151

Таким образом, расстояние 1,(4.5) равно расстоянию от объекта 1 до ближайшего к нему объекта, входящего в кластер

Объединим второй и третий объекты, имеющие наименьшее расстояние 2,3 1.41. После объединения объектов имеем четыре кластера:

S(1) ; S(2,3) ; S(4,5) ; S(6) .

Вновь найдем матрицу расстояний. Для того чтобы рассчитать расстояние до кластера S(2,3) воспользуемся матрицей расстояний R2. Например, расстояние между кластерами S(4,5) и S(2,3) равно

получим три кластера

S(1) ; S(2,3) и S(4,5,6) .

152

Матрица расстояний будет иметь вид:

Объединим теперь кластеры S(1) и S(2,3) , расстояние между

принципу «ближайшего соседа», будет (1,2,3)( 4,5,6) 5 .

Результаты иерархической классификации объектов представлены на рис. 10.2 в виде дендрограммы: по горизонтали откладываются номера объектов, а по вертикали – значения мер близости, при которых происходили соединения классов.

Рис. 10.2. Дендрограмма

На рис. 10.2 приводятся расстояния между кластерами, которые объединяются на одном этапе. В этом примере предпочтение следует отдать предпоследнему этапу

153

классификации, когда все объекты объединены в два кластера

S(1,2,3) и S(4,5,6).

10.6. Эвристические методы и алгоритмы

Подавляющая часть классификаций на практике производится эвристическими методами. Это объясняется относительной простотой и содержательной ясностью таких алгоритмов. Эти алгоритмы допускают вмешательство в их работу путем изменения одного или нескольких параметров, кроме того, они обладают невысокой трудоемкостью. Наиболее распространенные эвристические алгоритмы используют для своей реализации различные типы классов. Разделение классов на типы впервые осуществил советский ученый Миркин Б.Г. Какие множества называются группами однородных объектов или классов можно уточнить на основе заданного расстояния между объектами. Выделим некоторые типы классов.

1.Класс типа ядра. Такой класс называется сгущением. Все расстояния между объектами внутри класса меньше любого из расстояний между объектами класса и остальной частью множества объектов. На рис. 10.3 сгущениями являются А и В. Остальные пары множеств не разделяются с помощью этого определения.

2.Кластер (сгущение в среднем). Среднее расстояние внутри класса меньше среднего расстояния от объектов класса до всех остальных. Множества С и Д теперь разделяются, но у Е(G) среднее внутреннее расстояние больше, чем среднее расстояние между Е и F (G и H).

3.Класс типа ленты (слабое сгущение). Существует

определения на рис. 10.3 разделяются все пары множеств кроме I и J, K и L.

4. Класс с центром. Существует порог R>0 и некоторая точка x* в пространстве, занимаемом объектами класса S, такие, что все объекты из S и только они содержатся в шаре радиуса R с центром в x*. Часто в качестве x* выступает центр масс класса S, т.е. координаты центра определяются как средние значения признаков у объектов класса. Множества I и J являются классами с центром, а E, F и G – нет.

Рис. 10.3. Типы классов

Рассмотрим наиболее часто используемые эвристические алгоритмы.

1. Метод К-средних предназначен для выделения и распознавания классов типа 4 («класс с центром»). Приведем два варианта.

а) Алгоритм Г. Бола и Д. Холла был предложен в 1965 году. Суть алгоритма состоит в следующем. Случайно выбираются К объектов (эталонов). Каждый объект присоединяется к ближайшему эталону (тем самым образуются К классов), в качестве новых эталонов принимаются центры масс классов. Считается, что каждому объекту приписана масса 1. После пересчета объекты снова распределяются по ближайшим эталонам и т.д. Критерием окончания алгоритма служит стабилизация центров масс всех классов.

155

б) Алгоритм Дж. Мак-Кина предложен в 1967 году. Он отличается от метода Бола и Холла тем, что при просмотре списка объектов пересчет центра масс класса происходит после присоединения к нему каждого очередного объекта. Этот алгоритм связан с функционалом качества разбиения

Q1 S - сумма внутриклассовых дисперсий.

2. Алгоритм «Форель». Первоначальное название этого алгоритма было: ФОРЭЛ – ФОР малый ЭЛемент. Этот алгоритм предложен в 1966 году Елкиной В.Н. и Загоруйко Н.Г. Этот алгоритм выполняется следующим образом. Случайный объект объявляется центром класса; все объекты, находящиеся от него на расстоянии не большем R, входят в первый класс. В нем определяется центр масс, который объявляется новым центром класса и т.д. до стабилизации центра. Затем все объекты, попавшие в первый класс, изымаются, и процедура повторяется с новым случайным центром.

После проведения классификации важно в удобной форме представить ее результаты. Для этого необходимы следующие характеристики классификации.

1.Распределение номеров объектов по номерам классов.

2.Гистограмма межобъектных расстояний.

3.Средние внутриклассовые расстояния.

4.Матрица средних межклассовых расстояний.

5.Визуальное представление данных на плоскости двух (в пространстве трех) «наиболее информативных» признаков.

6.Дендрограмма для иерархических процедур.

7.Средние значения и размахи во всех классах для каждого признака.

Последний пункт очень важен, так как в большинстве случаев описание классов происходит по средним значениям признаков в них. Сопоставление средних значений для заданного признака наиболее просто осуществляется, если

156

классы не имеют наложения проекций. Степень разделенности классов по каждой оси можно охарактеризовать с помощью коэффициента

Lj / Ri ,

где Ri – размах по заданному признаку l – го класса, а

L1 , L2 ,... - длины наложений проекций классов на ось

признака. Если γ=1, то классы полностью разделены. Чем ближе γ к 0, тем больше наложение проекций классов друг на друга.

10.7. Алгоритм K – внутригрупповых средних

Рассмотрим компьютерную реализацию алгоритма K – внутригрупповых средних. Этот алгоритм наиболее часто используется в задачах классификации объектов. Он также используется для организации входных данных для нейронных сетей. Алгоритм, представленный ниже, минимизирует показатель качества, определенный как сумма квадратов расстояний всех точек, входящих в кластерную область, до центра кластера. Эта процедура, которую часто называют алгоритмом, основанным на вычислении К внутригрупповых средних, состоит из следующих шагов.

Шаг 1. Выбираются К исходных центров кластеров z1(1), z2(1), . . .,zk(1). Этот выбор производится произвольно, и обычно в качестве исходных центров используются первые К результатов выборки из заданного множества объектов.

Шаг 2. На k-м шаге итерации заданное множество объектов {x} распределяется по К кластерам по правилу:

для всех i=1, 2, …,K, i≠j, где Sj(k) – множество объектов, входящих в кластер с центром zj(k). В случае равенства в (10.12) решение принимается произвольным образом.

Шаг 3. На основе результатов шага 2 определяются новые центры кластеров zj(k+1), j=1, 2, …,К, исходя из условия, что сумма квадратов расстояний между всеми объектами,

157

принадлежащими множеству Sj(k), и новым центром кластера должна быть минимальной. Другими словами, новые центры кластеров zj(k+1) выбираются таким образом, чтобы минимизировать показатель качества

Центр zj(k+1), обеспечивающий минимизацию показателя качества, является в сущности, выборочным средним, определенным по множеству Sj(k). Следовательно, новые центры кластеров определяются как

где Nj – число выборочных объектов, входящих в множество Sj(k). Очевидно, что название алгоритма «К внутригрупповых средних» определяется способом, принятым для последовательной коррекции назначения центров кластеров.

Шаг 4. Равенство zj(k+1)= zj(k) при j=1, 2, …, К является условием сходимости алгоритма, и при его достижении выполнение алгоритма заканчивается. В противном случае алгоритм повторяется от шага 2.

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

158

Лабораторная работа № 8. Реализация алгоритма K – внутригрупповых средних в пакете MATHCAD

Целью лабораторной работы является программная реализация алгоритма K – внутригрупповых средних для корректирования центров исходных классов. Классы составляют случайные величины с различными законами распределения.

Задачами лабораторной работы являются:

формирование случайных величин с нормальным, равномерным и экспоненциальным законом распределения с использованием математического пакета MATHCAD;

описание эталонных образов классов в виде векторов, характеристиками которых являются: математическое ожидание, дисперсия, среднеквадратическое отклонение, эксцесс и асимметрия законов распределения;

применение алгоритма К– внутригрупповых средних для корректирования центров исходных классов случайных величин с рассмотренными законами распределения.

Пример выполнения задания

В качестве примера представлен графический интерфейс программы, выполненной в среде Borland Delphi 7. Форма, предназначенная для реализации алгоритма К - внутригрупповых средних, показана на рис. 10.4.

159

Рис. 10.4. Форма для алгоритма К– внутригрупповых средних При запуске алгоритма выдается сообщение о том, что идет обработка введенного вектора (рис. 10.5).

Рис. 10.5. Сообщения, выдаваемые при обработке вектора После выполнения алгоритма в окне результатов будут выведены скорректированные центры исходных классов (рис.

10.6).

160