Алгоритмы кластеризации на службе Data Mining

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

Введение

Кластеризация – объединение в группы схожих объектов – является одной из фундаментальных задач в области анализа данных и Data Mining. Список прикладных областей, где она применяется, широк: сегментация изображений, маркетинг, борьба с мошенничеством, прогнозирование, анализ текстов и многие другие. На современном этапе кластеризация часто выступает первым шагом при анализе данных. После выделения схожих групп применяются другие методы, для каждой группы строится отдельная модель.

Задачу кластеризации в том или ином виде формулировали в таких научных направлениях, как статистика, распознавание образов, оптимизация, машинное обучение. Отсюда многообразие синонимов понятию кластер – класс, таксон, сгущение.

На сегодняшний момент число методов разбиения групп объектов на кластеры довольно велико – несколько десятков алгоритмов и еще больше их модификаций. Однако нас интересуют алгоритмы кластеризации с точки зрения их применения в Data Mining.

Кластеризация в Data Mining

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

Очень часто данные, с которыми сталкивается технология Data Mining, имеют следующие важные особенности:

высокая размерность (тысячи полей) и большой объем (сотни тысяч и миллионы записей) таблиц баз данных и хранилищ данных (сверхбольшие базы данных);
наборы данных содержат большое количество числовых и категорийных атрибутов.

Все атрибуты или признаки объектов делятся на числовые (numerical) и категорийные (categorical). Числовые атрибуты – это такие, которые могут быть упорядочены в пространстве, соответственно категорийные – которое не могут быть упорядочены. Например, атрибут «возраст» – числовой, а «цвет» – категорийный. Приписывание атрибутам значений происходит во время измерений выбранным типом шкалы, а это, вообще говоря, представляет собой отдельную задачу.

Большинство алгоритмов кластеризации предполагают сравнение объектов между собой на основе некоторой меры близости (сходства). Мерой близости называется величина, имеющая предел и возрастающая с увеличением близости объектов. Меры сходства «изобретаются» по специальным правилам, а выбор конкретных мер зависит от задачи, а также от шкалы измерений. В качестве меры близости для числовых атрибутов очень часто используется евклидово расстояние, вычисляемое по формуле:

Для категорийных атрибутов распространена мера сходства Чекановского-Серенсена и Жаккара ( \mid t_1 \cap t_2\mid/\mid t_1\cup t_2 \mid) .

Потребность в обработке больших массивов данных в Data Mining привела к формулированию требований, которым, по возможности, должен удовлетворять алгоритм кластеризации. Рассмотрим их:

Минимально возможное количество проходов по базе данных;
Работа в ограниченном объеме оперативной памяти компьютера;
Работу алгоритма можно прервать с сохранением промежуточных результатов, чтобы продолжить вычисления позже;
Алгоритм должен работать, когда объекты из базы данных могут извлекаться только в режиме однонаправленного курсора (т.е. в режиме навигации по записям).

Алгоритм, удовлетворяющий данным требованиям (особенно второму), будем называть масштабируемым (scalable). Масштабируемость – важнейшее свойство алгоритма, зависящее от его вычислительной сложности и программной реализации. Имеется и более емкое определение. Алгоритм называют масштабируемым, если при неизменной емкости оперативной памяти с увеличением числа записей в базе данных время его работы растет линейно.

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

Трудно соблюсти баланс между высоким качеством кластеризации и масштабируемостью. Поэтому в идеале в арсенале Data Mining должны присутствовать как эффективные алгоритмы кластеризации микромассивов (microarrays), так и масштабируемые для обработки сверхбольших баз данных (large databases).

Алгоритмы кластеризации: блеск и нищета

Итак, уже можно классифицировать кластерные алгоритмы на масштабируемые и немасштабируемые. Продолжим классификацию.

По способу разбиения на кластеры алгоритмы бывают двух типов: иерархические и неиерархические. Классические иерархические алгоритмы работают только с категорийными атрибутами, когда строится полное дерево вложенных кластеров. Здесь распространены агломеративные методы построения иерархий кластеров – в них производится последовательное объединение исходных объектов и соответствующее уменьшение числа кластеров. Иерархические алгоритмы обеспечивают сравнительно высокое качество кластеризации и не требуют предварительного задания количества кластеров. Большинство из них имеют сложность O(n^2) .

Неиерархические алгоритмы основаны на оптимизации некоторой целевой функции, определяющей оптимальное в определенном смысле разбиение множества объектов на кластеры. В этой группе популярны алгоритмы семейства k-средних (k-means, fuzzy c-means, Густафсон-Кесселя), которые в качестве целевой функции используют сумму квадратов взвешенных отклонений координат объектов от центров искомых кластеров.

Кластеры ищутся сферической либо эллипсоидной формы. В канонической реализации минимизация функции производится на основе метода множителей Лагранжа и позволяет найти только ближайший локальный минимум. Использование методов глобального поиска (генетические алгоритмы) значительно увеличит вычислительную сложность алгоритма.

Рисунок 1. Гистограммы двух разбиений

Среди неиерархических алгоритмов, не основанных на расстоянии, следует выделить EM-алгоритм (Expectation-Maximization). В нем вместо центров кластеров предполагается наличие функции плотности вероятности для каждого кластера с соответствующим значением математического ожидания и дисперсией. В смеси распределений (рис. 2) ведется поиск их параметров (средние и стандартные отклонения) по принципу максимума правдоподобия. Алгоритм EM и есть одна из реализаций такого поиска. Проблема заключается в том, что перед стартом алгоритма выдвигается гипотеза о виде распределений, которые оценить в общей совокупности данных сложно.

Рисунок 2. Распределения и их смесь

Еще одна проблема появляется тогда, когда атрибуты объекта смешанные – одна часть имеет числовой тип, а другая часть – категорийный. Например, пусть требуется вычислить расстояние между следующими объектами с атрибутами (Возраст, Пол, Образование):

Первый атрибут является числовым, остальные – категорийными. Если мы захотим воспользоваться классическим иерархическим алгоритмом с какой-либо мерой сходства, нам придется каким-то образом произвести дискредитацию атрибута «Возраст». Например, так:

При этом часть информации, мы, безусловно, потеряем. Если же мы будем определять расстояние в евклидовом пространстве, то возникнут вопросы с категорийными атрибутами. Понятно, что расстояние между «Пол муж» и «Пол жен» равно 0, т.к. значения этого признака находятся в шкале наименований. А атрибут «Образование» можно измерить как в шкале наименований, так и в шкале порядка, присвоив каждому значению определенные балл.

Какой вариант выбрать? А что делать, если категорийные атрибуты важнее числовых? Решение этих проблем ложится на плечи аналитика. Кроме того, при использовании алгоритма k-средних и ему подобных возникают трудности с пониманием центров кластеров у категорийных атрибутов, априорным заданием количества кластеров.

Алгоритм оптимизации целевой функции в неиерархических алгоритмах, основанных на расстояниях, носит итеративный характер, и на каждой итерации требуется рассчитывать матрицу расстояний между объектами. При большом числе объектов это неэффективно и требует серьезных вычислительных ресурсов. Вычислительная сложность 1-й итерации алгоритма k-means оценивается как O(kmn) , где k,m,n — количество кластеров, атрибутов и объектов соответственно. Но итераций может быть очень много! Придется делать много проходов по набору данных.

Имеет массу недостатков в k-means сам подход с идеей поиска кластеров сферической или эллипсоидной формы. Подход хорошо работает, когда данные в пространстве образуют компактные сгустки, хорошо отличимые друг от друга. А если данные имеют вложенную форму, то ни один из алгоритмов семейства k-means никогда не справится с такой задачей. Также алгоритм плохо работает в случае, когда один кластер значительно больше остальных, и они находятся близко друг от друга – возникает эффект «расщепления» большого кластера (рис. 3).

Рисунок 3. Эффект расщепления большого кластера

Впрочем, исследования в области совершенствования алгоритмов кластеризации идут постоянно. Разработаны интересные расширения алгоритма k-means для работы с категорийными атрибутами (k-modes) и смешанными атрибутами (k-prototypes). Например, в k-prototypes расчет расстояний между объектами осуществляется по-разному в зависимости от типа атрибута.

На рынке масштабируемых алгоритмов кластеризации борьба идет за снижение каждого «дополнительного» прохода по набору данных во время работы алгоритма. Разработаны масштабируемые аналоги k-means и EM (scalable k-means и scalable EM), масштабируемые агломеративные методы (CURE, CACTUS). Эти современные алгоритмы требуют всего несколько (от двух до десяти) сканирований базы данных до получения финальной кластеризации.

Получение масштабируемых алгоритмов основано на идее отказа от локальной функции оптимизации. Парное сравнение объектов между собой в алгоритме k-means есть не что иное, как локальная оптимизация, т.к. на каждой итерации необходимо рассчитывать расстояние от центра кластера до каждого объекта. Это ведет к большим вычислительным затратам.

При задании глобальной функции оптимизации добавление новой точки в кластер не требует больших вычислений: оно рассчитывается на основе старого значения, нового объекта и так называемых кластерных характеристик (clusters features). Конкретные кластерные характеристики зависят от того или иного алгоритма. Так появились алгоритмы BIRCH, LargeItem, CLOPE и многие другие.

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

Источник

Алгоритм максиминного расстояния

1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Нижегородский государственный университет им. Н.И. Лобачевского Т.И. Чачхиани М.Г. Серова Ю.А. Ванкова Алгоритм максиминного расстояния Практикум Рекомендовано методической комиссией факультета ВМК для студентов ННГУ, обучающихся по направлению подготовки «Фундаментальная информатика и информационные технологии» и «Прикладная математика и информатика» Нижний Новгород 2014

2 УДК ББК Ч-28 Чачхиани Т.И., Серова М.Г., Ванкова Ю.А. Алгоритм максиминного расстояния: практикум. Нижний Новгород: Нижегородский госуниверситет, с. Рецензент: к.ф.-м.н., доцент Золотых Н.Ю. Практикум входит в учебно-исследовательский программный комплекс для курса «Распознавание образов». В нем содержится описание алгоритма максиминного расстояния и дается описание работы программного модуля. Практикум предназначается для студентов ННГУ, обучающихся по направлениям подготовки «Фундаментальная информатика и информационные технологии» и «Прикладная математика и информатика». Ответственный за выпуск: заместитель председателя методической комиссии факультета ВМК ННГУ, к. т. н., доцент В.М. Сморкалова УДК ББК Нижегородский государственный университет им. Н.И. Лобачевского,

3 Введение Кластерный анализ это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп, как сгустков этих точек. Запишем в математических обозначениях: U= множество объектов в n-мерном пространстве u i x i =(x i1 x in )` (каждому объекту ставится в соответствии точка n- мерного пространства признаков с координатами x i1 x in ) Таким образом, множеству объектов U соответствует множество точек Х: U X =(x 1,, x N ), где N число точек в n-мерном пространстве признаков. Задача кластерного анализа: Дано множество объектов(точек) надо разбить его на некоторое число не пересекающихся подмножеств (кластеров) К i так, чтобы каждый объект принадлежал только одному кластеру, т.е. К i К j =Ø для всех i j и все точки были распределены по кластерам, то есть K = X. Объекты, принадлежащие к одному и тому же кластеру должны быть сходны между собой, в то время как объекты из разных кластеров должны быть различны. Эта задача является очень неопределенной, так как ее решение зависит от нескольких факторов — параметров кластеризации: 1) выбранного критерия сходства элементов Q; 2) от используемой метрики d (критерии сходства, как правило, зависят от выбранной метрики, измеряющей расстояние между векторами-образами); 3) от установленного (или оцениваемого) числа кластеров (оно может быть заданно априорно, или быть выходным параметром метода). Выбор параметров кластеризации, как правило, неоднозначен, зачастую субъективен, но этот выбор должен быть согласован с целями кластеризации. Среди основных целей кластеризации могут быть следующие: 1) кластеризация проводится для нахождения групп схожих элементов с целью дальнейшей независимой их обработки. В этом случае параметры кластеризации должны обеспечивать минимальность числа кластеров; 2) кластеризация осуществляется с целью получения новой небольшой выборки, состоящей из эталонных элементов — типичных представителей кластеров. Здесь важно, чтобы параметры кластеризации обеспечивали формирование кластеров с высокой степенью однородности входящих в них элементов; 3) кластеризация проводится с целью нахождения нетипичных элементов, т.е. элементов, не попадающих ни в один из кластеров, при этом сами кластеры должны быть небольшими; 3

4 4) кластеризация осуществляется с целью формирования иерархической структуры выборки (так называемая задача таксономии). В этом случае на каждом иерархическом уровне количество кластеров должно быть небольшим. Определим понятие меры сходства (различия). Любая мера сходства представляет собой некоторую функцию, ставящую в соответствие каждой паре точек (x i, x j ) некоторое число α(x i, x j ) характеризующее степень сходства объектов u и u. Такая мера имеет несколько свойств: 1) α(x i, x j ) 0; 2) α(x i, x j ) = α(x j, x i ); 3) α(x i, x i ) α(x i, x j ). В алгоритме в качестве меры сходства используется евклидово расстояние d(x i, x j ) = x i — x j. В этом случае свойство (3) изменяется: d(x i, x i ) d(x i, x j ). 1. Описание алгоритма максиминного расстояния Алгоритм производит разбиение на заранее не заданное число кластеров. При этом он выявляет наиболее удаленные друг от друга кластеры. Шаг 1. Первая точка становится центром кластера: z 1 = x 1 Находится наиболее удаленная от него точка и назначается центром второго кластера z = Arg min z x. Шаг 2. Вычисляются расстояния D 1i = z 1 — x и D 2i = z — x для всех оставшихся точек. Шаг 3. Из этих расстояний для каждой точки выбирают минимальное R i = min(d 1i, D 2i ). Шаг 4. Вычисляется максимальное из этих минимальных расстояний Q = max R. Шаг 5. Если это расстояние составляет значительную часть предыдущих максимальных расстояний между центрами кластеров, то соответствующий образ назначается центром нового кластера Q 1 2 z 1 — z 2, то z 3 = x minmax. Иначе переходим на последний шаг. Шаг 6. Вычисляем расстояния для оставшихся точек ото всех центров кластеров: D 1i, D 2i, D 3i Шаг 7. Повторяем шаги 3 и 4. Шаг 8. Если максимально-минимальное расстояние составляет значительную часть предыдущих максимальных расстояний между центрами 4

5 кластеров, то соответствующий образ назначается центром нового кластера. Хорошей мерой оценки предыдущих расстояний является их среднее значение. Если Q ½ (среднеарифметическое предыдущих максимальных расстояний), то образуется новый кластер и переходим на Шаг 6. Если иначе — переходим на последний шаг. Последний шаг. Распределяем оставшиеся точки по близости к центрам кластеров. Замечание: порядок просмотра точек может повлиять на результат кластеризации. 2. Пример работы алгоритма Сначала на рабочее поле наносятся точки и 1-я точка выбирается центром первого кластера (рис. 1). Рис. 1. Шаг первый Измеряется расстояния от этого центра кластера до всех других точек (рис. 2). 5

6 Рис. 2. Расстояния от центра кластера до остальных точек После того, как будет найдена наиболее удалённая точка, она назначается центром второго кластера (рис. 3). Рис. 3. Наиболее удалённая точка — центр нового кластера Измеряется расстояние от каждой точки до обоих центров и выбирается минимальное из них (рис. 4). 6

7 Рис. 4. Измерения расстояния от 2-х центров кластеров Из минимальных расстояний выбирается максимальное и, если оно составило значительную часть предыдущих максимальных расстояний, то соответствующая точка назначается центром третьего кластера (рис. 5). Рис. 5. Назначение 3-го центра 7

8 Снова вычисляются расстояния от точек, но уже до 3-х центров кластеров, и среди них выбирается минимальное (рис. 6). Рис. 6. Измерение расстояний от центров кластеров до точек В данном примере повторение процедуры приводит к образованию 5-ти кластеров (рис. 7). Рис. 7. Результат кластеризации 3. Описание работы программного модуля 8

9 Для демонстрации работы алгоритма создан программный модуль «Алгоритм максиминного расстояния». После запуска программы на экране появляется главное окно программы. В окне представлены: область пространства признаков Х и панель меню. Для начала работы необходимо с помощью мышки на рабочем поле выполнить ввод точек (рис. 8). Рис. 8. Точки нанесены Далее в меню выбирается пункт Запуск метода. Можно запустить работу в 3-х режимах: Автоматически, Пошагово и посмотреть Результат кластеризации сразу (рис. 9). Рис. 9. Запуск метода После выбора пошагового запуска внизу поля появится кнопка «вперед», при нажатии на которую программа будет выполнять каждый шаг, вместо мышки может использоваться клавиша Enter (рис. 10). 9

10 Рис. 10. Кнопка пошагового режима Рассмотрим пункты меню и возможности программы. В пункте «Файл» можно выбрать Очистить экран, перейти На начало примера (чтобы можно было проделать его с изменённым параметром) и сделать Выход из программы (рис. 11). Также можно сохранить либо загрузить пример. Рис. 11. Пункт меню «Файл» Пункт меню Параметр оценки позволяет сделать Изменение параметра (рис. 12 и рис. 13). Рис. 12. Параметр оценки 10

11 Рис. 13. Изменение и просмотр параметра оценки При выборе этого пункта появится окно «Значение параметра» (по умолчанию оно равно 0,5). Его можно изменить и нажать кнопку Изменить. Если параметр не был изменен, можно просто нажать Закрыть и продолжить работу с программой (рис. 12 и рис. 13). Пункт Демо позволяет посмотреть работу алгоритма на 3-х примерах (рис.14). Рис. 14. Демонстрационные примеры 11

12 ЛИТЕРАТУРА 1. Гонсалес Р., Ту Дж. Принципы распознавания образов. М.: Мир, с. 2. Мандель И.Д. Кластерный анализ. М.: Финансы и статистика с. 3. Диде Э. и др. Методы анализа данных. М.: Финансы и статистика с. 4. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, с. 5. Балабанов А.С., Стронгина Н.Р. Анализ данных в экономических приложениях: Учебное пособие. Н. Новгород: Изд-во ННГУ, с. 12

13 СОДЕРЖАНИЕ Введение Описание алгоритма максиминного расстояния Пример работы алгоритма Описание работы программного модуля.. 9 Литература

14 Татьяна Игоревна Чачхиани Марина Германовна Серова Юлия Алексеевна Ванкова АЛГОРИТМ МАКСИМИННОГО РАССТОЯНИЯ Практикум Федеральное государственное автономное образовательное учреждение высшего образования «Нижегородский государственный университет им. Н.И. Лобачевского» , Нижний Новгород, пр. Гагарина, 23. Подписано в печать. Формат /16. Бумага офсетная. Печать офсетная. Гарнитура Таймс. Усл. печ. л.. Уч. изд. л.. Заказ. Тираж экз. Отпечатано в типографии Нижегородского госуниверситета им. Н.И. Лобачевского , г. Нижний Новгород, ул. Большая Покровская,

Источник

Эвристический алгоритм максиминного расстояния

Алгоритм основан на принципе максиминного (максимально-минимального) расстояния. Алгоритм аналогичен схеме простого выявления кластеров, за исключением того, что в первую очередь он выявляет наиболее удаленные кластеры.

Пусть дана выборка из m n – мерных образов. Необходимо получить представление о количестве кластеров, выделяющихся в этих данных.

Алгоритм:

1)На первом шаге алгоритма один из объектов, например х₁, произвольным образом назначается центром первого кластера z₁

2)Затем отыскивается образ, отстоящий от образа х₁ на наибольшее расстояние, который и назначается центром кластера z₂

3)На k – ом шаге итерации для каждого из оставшихся образов выборки вычисляем расстояния до всех ранее полученных центров кластеров. В каждой паре этих расстояний выбираем минимальное. После этого находим среди всех полученных минимальных расстояний максимальное. Если последнее составляет значительную часть расстояния между полученными центрами кластеров (скажем, по меньшей мере половину этого расстояния), то соответствующий образ назначается центром следующего кластера. В противном случае выполнение алгоритма прекращается. В общем случае, процедура повторяется до тех пор, пока на каком – либо шаге не будет получено максимальное расстояние, для которого условие, определяющее выделение нового кластера не выполняется. При отнесении выборочных образов, не вошедших в кластерные центры, к одному из учрежденных кластеров, используется критерий, предусматривающий введение классифицируемого образа в тот кластер, центр которого для него ближайший.

Пример:

1. Назначаем центром кластера z₁ первое изображение объекта x₁.

2. Ищем изображение объекта, отстоящее от изображения x₁ на наибольшее расстояние. Наибольшим расстоянием является S(x1, x3). Назначаем центром второго кластера z2 – x6.

3.Для каждого из оставшихся образов вычисляем расстояния до всех ранее полученных центров кластеров. Из полученных наборов расстояний для каждого образа выбираем минимальное = min[(s(xi,z1)),(s(xi,z2))].

После этого находим среди всех полученных минимальных расстояний максимальное.

Максимальное расстояние Max= 3.

Расстояние S между центрами кластеров z1 и z2 = .

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

Источник

Материалы для PDF / Принятие решений / 66-71

расстояния оказываются больше порога Т, то учреждается новый центр кластера Z₃, с координатами Z₃=Х₃, в 6противном случае образ ω₃ зачисляется в тот кластер, чей центр к нему ближе. Подобным же образом расстояния от каждого нового образа до каждого известного центра кластера вычисляются и сравниваются с пороговой величиной — если все эти расстояния превосходят значения порога Т, учреждается новый центр кластера. В противном случае образ зачисляется в кластер с самым близким к нему центром. :

Результаты описанной процедуры определяются выбором первого центра кластера, порядком осмотра образов, значением пороговой величины Т и, конечно, геометрическими характеристиками данных. Это влияние проиллюстрировано на рис.4, на котором представлены три различных варианта выбора центров кластеров на одних и тех же данных, возникшие в результате изменения только значения пороговой величины Т и исходной точки кластеризации.

Рис.4. Иллюстрация влияния выбора величины порога и исходных точек в простой схеме кластеризации.

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

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

АЛГОРИТМ МАКСИМИННОГО РАССТОЯНИЯ

Алгоритм, основанный на принципе максиминного (максимально-минимального) расстояния, представляет собой еще одну простую эвристическую процедуру, использующую евклидово расстояние. Этот алгоритм в принципе аналогичен предыдущей схеме за исключением того обстоятельства, что в первую очередь он выявляет наиболее удаленные кластеры. Соответствующую процедуру удобнее всего рассмотреть на конкретном примере.

Возьмем выборку, состоящую из десяти двумерных образов (см. рис.5). Для того, чтобы получить представление о количестве кластеров, целесообразно воспользоваться алгоритмом, основанным на максиминном расстоянии. Описание алгоритма упрощают таблицы. Одна из них содержит выборочные образы, другая — список центров кластеров, установленных алгоритмом. До начала работы эта таблица пуста. На первом шаге алгоритма один из объектов, например, описываемый вектором Х₁ произвольным образом назначается центром первого кластера (на рисунке этот центр обозначен Z₁). Цифры, расположенные над стрелками, обозначают порядковый номер шага, на котором производится выделение соответствующего центра кластера.

Затем отыскивается образ, отстоящий от X₁ на наибольшем расстоянии; в данном случае — это образ, описываемый вектором Х₆, который и назначается центром второго кластера – Z₂. На третьем шаге алгоритма производится вычисление расстояний между всеми остальными объектами выборки и центрами кластеров Z₁ и Z₂. В каждой паре этих расстояний выделяется минимальное. После этого выделяется максимальное из этих расстояний. Если последнее составляет значительную часть расстояния между центрами кластеров Z₁ и Z₂ (скажем, по меньшей мере половину этого расстояния), соответствующий образ назначается центром кластера Z₃. В4 противном случае выполнение алгоритма

прекращается. Если воспользоваться таким критерием в приведенном примере, легко убедиться в том, что центром кластера Z₃ становится объект, описываемый вектором признаков Х₇.

На следующем шаге алгоритма вычисляется расстояние между тремя выделенными центрами кластеров и всеми остальными выборочными образами; в каждой группе этих из этих трех расстояний выбирается минимальное. После этого, как и на предыдущем шаге, находится максимальное из этих расстояний. Если последнее составляет значительную часть «типичных» предыдущих максимальных расстояний, то соответствующий образ назначается центром кластера Z₄. в противном случае выполнение алгоритма прекращается. Хорошей мерой для оценки типичных предыдущих расстояний является среднее значение. Если воспользоваться этим критерием в данном примере и потребовать, чтобы новое максимальное расстояние составляло по меньшей мере половину среднего, то из рис.5 следует, что очередное максимальное расстояние не удовлетворяет такому условию. Поэтому на данном шаге работа алгоритма прерывается. В общем случае описанная процедура повторяется до тех пор, пока на каком-либо шаге не будет получено максимальное расстояние, для которого условие, определяющее выделение нового кластера, не выполняется.

В этом простом примере были выделены три кластерных центра с координатами Х₁, Х₆ и Х₇. При отнесении остальных выборочных о6бразов к одному из учрежденных кластеров используется критерий, предусматривающий введение классифицируемого образа в тот кластер, центр которого для него ближайший. Таким образом, в нашем примере получены три кластера: <Х₁, Х₃, X₄>, <Х₂, Х₆>, <Х₅, Х₇, Х₈, Х₉, Х₁₀>. Можно более точно определить центры кластеров, вычислив для каждого набора выборочное среднее:

где S_j — множество образов, относящихся к j-му кластеру, N_j — количество образов, входящих во множество S_j. Эти средние можно считать новыми центрами кластеров.

АЛГОРИТМ К ВНУТРИГРУППОВЫХ СРЕДНИХ

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

Эта процедура, которую часто называют алгоритмом, основанным на вычислении К внутригрупповых средних, состоит из следующих шагов.

1. Выбираются К исходных центров кластеров Z₁(1), Z₂ (1), . Z_k (1).Этот выбор производится произвольно, и 4обычно в качестве исходных центров кластеров используются первые К результатов выборки из заданного множества объектов.

2. На n-ом шаге итерации заданное множество образов распределяется по К кластерам по следующему правилу:

для всех i=1, 2, . К, ij, где S_j(n) — множество образов, входящих в кластер с центром Z_j(п). В случае равенства в указанном уравнении решение принимается произвольным образом.

3. На основе результатов пункта 2 определяются новые центры кластеров Z_j(n+1 ), j=1, 2, . К, исходя из условия, что сумма квадратов расстояний между всеми образа6ми, принадлежащими множеству S_j(n), и новым центром кластера, должна быть минимальной. Другими словами, новые центры кластеров S_j(n+1) выбираются таким образом, чтобы минимизировать показатель качества

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

где N_i — число выборочных образов, входящих во множество S_j(n). Очевидно, что название алгоритма «К внутригрупповых средних» определяется способом, принятым для последовательной коррекции назначения центров кластеров.

4. Равенство S_j(n+1) = S_j(n) при j -1, 62, . К является условием сходимости алгоритма, и при его достижении выполнение алгоритма заканчивается. В противном случае алгоритм повторяется от пункта 2.

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

Хотя для этого алгоритма общее доказательство сходимости не известно, получение приемлемых результатов можно ожидать в тех случаях, когда данные образуют характерные «гроздья», отстоящие друг от друга достаточно далеко.

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

ОЦЕНКА РЕЗУЛЬТАТОВ ПРОЦЕССА КЛАСТЕРИЗАЦИИ

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

При интерпретации очень полезно использовать расстояние между центрами кластеров. Лучше всего информацию подобного рода представлять с помощью таблиц. Например:

является то обстоятельство, что центр кластера Z₅ существенно смещен относительно четырех других центров кластеров. Кроме того, расстояния между центрами кластеров Z₁ и Z₂ и Z₁ и Z₄ относительно одинаковы, если разделить только близко и далеко расположенные центры кластеров.

Таблица расстояний не является, естественно, достаточной основой для получения содержательных выводов. При интерпретации таблицы расстояний обычно используют в качестве вспомогательного средства количество образов классифицируемой выборки, вошедшее в каждый кластер. Например, из таблицы следует, что центр кластера Z₅ далеко отстоит от центров остальных кластеров. 8Если известно, что в этот кластер входит достаточно образов, то его следует принять в качестве элемента истинного описания данных. Если же, с другой стороны, в кластер входит только один или два образа, можно после соответствующего анализа устранить этот центр кластера, заключив, что данные образы являются шумом.

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

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

Источник