Итерационные методы кластерного анализа. Кластерный анализ Проверка качества кластеризации

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

Методы КлА позволяют решать следующие задачи:

Проведение классификации объектов с учетом множества признаков;

Проверка выдвигаемых предположений о наличии некоторой структуры в изучаемой совокупности объектов, т.е. поиск существующей структуры;

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

Для записи формализованных алгоритмов КлА используются следующие условные обозначения:

– совокупность объектов наблюдения;

– i-е наблюдение в m-мерном пространстве признаков ();

– расстояние между -м и -м объектами;

– нормированные значения исходных переменных;

– матрица расстояний между объектами.

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

Для количественной оценки сходства вводится понятие метрики. Каждый объект описывается -признаками и представлен как точка в -мерном пространстве. Сходство или различие между классифицируемыми объектами устанавливается в зависимости от метрического расстояния между ними. Как правило, используются следующие меры расстояния между объектами:

Евклидово расстояние ;

Взвешенное евклидово расстояние ;

Расстояние city-block ;

Расстояние Махаланобиса ,

где – расстояние между -ым и -ым объектами;

, – значения -переменной и соответственно у -го и -го объектов;

, – векторы значений переменных у -го и -го объектов;

– общая ковариационная матрица;

– вес, приписываемый -й переменной.

Все методы КлА можно разделить на две группы: иерархические (агломеративные и дивизимные) и итеративные (метод -cpeдних, метод поиска сгущений).

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

Последовательность объединения может быть представлена в виде дендрограммы, представленной на рисунке 3.1. Дендрограмма показывает, что на первом шаге объединены в один кластер второй и третий объекты при расстоянии между ними 0,15. На втором шаге к ним присоединился первый объект. Расстояние от первого объекта до кластера, содержащего второй и третий объекты, 0,3 и т.д.

Множество методов иерархического кластерного анализа отличаются алгоритмами объединения (сходства), из которых наиболее распространенными являются: метод одиночной связи, метод полных связей, метод средней связи, метод Уорда.

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

б)

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

Рисунок 1.4. Объединение двух кластеров по методу средней связи:

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

Метод Уорда – на первом шаге каждый кластер состоит из одного объекта. Первоначально объединяются два ближайших кластера. Для них определяются средние значения каждого признака и рассчитывается сумма квадратов отклонений

, (1.1)

где – номер кластера, – номер объекта, – номер признака; – количество признаков, характеризующих каждый объект; – количество объектов в - мкластере.

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

Метод Уорда приводит к образованию кластеров приблизительно равных размеров с минимальной внутрикластерной вариацией.

Алгоритм иерархического кластерного анализа можно представить в виде последовательности процедур:

Нормирование исходных значений переменных;

Расчет матрицы расстояний или матрицы мер сходства;

Определение пары самых близких объектов (кластеров) и их объединение по выбранному алгоритму;

Повторение первых трех процедур до тех пор, пока все объекты не будут объединены в один кластер.

Мера сходства для объединения двух кластеров определяется следующими методами:

Метод «ближайшего соседа» – степень сходства между кластерами оценивается по степени сходства между наиболее схожими (ближайшими) объектами этих кластеров;

Метод «дальнего соседа» – степень сходства оценивается по степени сходства между наиболее отдаленными (несхожими) объектами кластеров;

Метод средней связи – степень сходства оценивается как средняя величина степеней сходства между объектами кластеров;

Метод медианной связи – расстояние между любым кластером S и новым кластером, который получился в результате объединения кластеров р и q, определяется как расстояние от центра кластера S до середины отрезка, соединяющего центры кластеров р и q.

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

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

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

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

Существуют несколько способов выбора радиуса сферы. Если – расстояние между -м и -м объектами, то в качестве нижней границы радиуса ()выбирают , а верхняя граница радиуса может быть определена как .

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

Пример 1. На основании приведенных данных таблицы 1.1 необходимо провести классификацию пяти предприятий при помощи иерархического агломеративного кластерного анализа.

Таблица 1.1

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

Решение. Перед тем как вычислять матрицу расстояний, нормируем исходные данные по формуле

Матрица значений нормированных переменных будет иметь вид

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

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

Как видно из матрицы , наиболее близкими являются объекты и . Объединим их в один кластер и присвоим ему номер . Пересчитаем расстояния всех оставшихся объектов (кластеров) до кластера получим новую матрицу расстояний

В матрице расстояния между кластерами определены по алгоритму «дальнего соседа». Тогда расстояние между объектом и кластером равно

В матрице опять находим самые близкие кластеры. Это будут и , . Следовательно, на этом шаге объединяем и кластеры; получим новый кластер, содержащий объекты , . Присвоим ему номер . Теперь имеем три кластера {1,3}, {2,5}, {4}.

Судя по матрице ,на следующем шаге объединяем кластеры и , в один кластер и присвоим ему номер . Теперь имеем только два кластера:

И, наконец, на последнем шаге объединим кластеры и на расстоянии 3,861.

Представим результаты классификации в виде дендрограммы (рисунок 1.5). Дендрограмма свидетельствует о том, что кластер более однороден по составу входящих объектов, так как в нем объединение происходило при меньших расстояниях, чем в кластере .

Рисунок 3.5.Дендрограмма кластеризации пяти объектов

Пример 2 . На основании данных, приведенных ниже, проведите классификацию магазинов по трем признакам: – площадь торгового зала, м 2 , – товарооборот на одного продавца, ден. ед., – уровень рентабельности, %.

Номер магазина				Номер магазина

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

Решение. 1. Рассчитаем расстояния между объектами по евклидовой метрике

где , – стандартизированные значения исходных переменных соответственно у -го и -го объектов; т – число признаков.

2. На основе матрицы Z рассчитаем квадратную симметричную матрицу расстояний между объектами ().

Анализ матрицы расстояний помогает определить положение первоначального центра сферы и выбрать радиус сферы.

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

3. Зададим радиус сферы . В этом случае в сферу попадают объекты, расстояние которых до первого объекта меньше 2.

Для шести точек (объекты 1, 2, 3, 6, 7, 8) определяем координаты центра тяжести: .

4. На следующем шаге алгоритма помещаем центр сферы в точку и определяем расстояние каждого объекта до нового центра.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Подобные документы

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

доклад , добавлен 02.11.2009

Характеристика строительной отрасли Краснодарского края. Прогноз развития жилищного строительства. Современные методы и инструментальные средства кластерного анализа. Многомерные статистические методы диагностики экономического состояния предприятия.

дипломная работа , добавлен 20.07.2015

Моделирование. Детерминизм. Задачи детерминированного факторного анализа. Способы измерения влияния факторов в детерминированном анализе. Расчёт детерминированных экономико-математических моделей и методов факторного анализа на примере РУП "ГЗЛиН".

курсовая работа , добавлен 12.05.2008

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

дипломная работа , добавлен 09.10.2013

Завдання та етапи кластерного аналізу, вимоги до інформації. Приклад класифікації економічних об"єктів за допомогою алгоритму кластерного аналізу, методи перевірки стійкості кластеризації, інтерпретація результатів аналізу та побудування дендрограми.

реферат , добавлен 15.07.2011

Основная терминология, понятие и методы факторного анализа. Основные этапы проведения факторного анализа и методика Чеботарева. Практическая значимость факторного анализа для управления предприятием. Метода Лагранжа в решении задач факторного анализа.

контрольная работа , добавлен 26.11.2008

Выполнение кластерного анализа предприятий с помощью программы Statgraphics Plus. Построение линейного уравнения регрессии. Расчет коэффициентов эластичности по регрессионным моделям. Оценка статистической значимости уравнения и коэффициента детерминации.

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

Методы КлА позволяют решать следующие задачи:

— проведение классификации объектов с учетом множества признаков;

— проверка выдвигаемых предположений о наличии некоторой структуры в изучаемой совокупности объектов, т.е. поиск существующей структуры;

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

Для записи формализованных алгоритмов КлА используются следующие условные обозначения:

– совокупность объектов наблюдения;

– i-е наблюдение в m-мерном пространстве признаков ();

– расстояние между -м и -м объектами;

– нормированные значения исходных переменных;

– матрица расстояний между объектами.

— евклидово расстояние ;

— взвешенное евклидово расстояние ;

— расстояние city-block ;

— расстояние Махаланобиса ,

где – расстояние между -ым и -ым объектами;

, – значения -переменной и соответственно у -го и -го объектов;

, – векторы значений переменных у -го и -го объектов;

– общая ковариационная матрица;

– вес, приписываемый -й переменной.

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

б)

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

Рисунок 1.4. Объединение двух кластеров по методу средней связи:

Метод Уорда – на первом шаге каждый кластер состоит из одного объекта. Первоначально объединяются два ближайших кластера. Для них определяются средние значения каждого признака и рассчитывается сумма квадратов отклонений

, (1.1)

Алгоритм иерархического кластерного анализа можно представить в виде последовательности процедур:

— нормирование исходных значений переменных;

— расчет матрицы расстояний или матрицы мер сходства;

— определение пары самых близких объектов (кластеров) и их объединение по выбранному алгоритму;

— повторение первых трех процедур до тех пор, пока все объекты не будут объединены в один кластер.

Мера сходства для объединения двух кластеров определяется следующими методами:

— метод «ближайшего соседа» – степень сходства между кластерами оценивается по степени сходства между наиболее схожими (ближайшими) объектами этих кластеров;

— метод «дальнего соседа» – степень сходства оценивается по степени сходства между наиболее отдаленными (несхожими) объектами кластеров;

— метод средней связи – степень сходства оценивается как средняя величина степеней сходства между объектами кластеров;

— метод медианной связи – расстояние между любым кластером S и новым кластером, который получился в результате объединения кластеров р и q, определяется как расстояние от центра кластера S до середины отрезка, соединяющего центры кластеров р и q.

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

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

Пример 1. На основании приведенных данных таблицы 1.1 необходимо провести классификацию пяти предприятий при помощи иерархического агломеративного кластерного анализа.

Таблица 1.1

Решение. Перед тем как вычислять матрицу расстояний, нормируем исходные данные по формуле

Матрица значений нормированных переменных будет иметь вид

И, наконец, на последнем шаге объединим кластеры и на расстоянии 3,861.

Рисунок 3.5.Дендрограмма кластеризации пяти объектов

Пример 2. На основании данных, приведенных ниже, проведите классификацию магазинов по трем признакам: – площадь торгового зала, м2 , – товарооборот на одного продавца, ден. ед., – уровень рентабельности, %.

Номермагазина				Номермагазина

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

Решение. 1. Рассчитаем расстояния между объектами по евклидовой метрике

2. На основе матрицы Z рассчитаем квадратную симметричную матрицу расстояний между объектами ().

Введение

Термин кластерный анализ, впервые введенный Трионом (Tryon) в 1939 году, включает в себя более 100 различных алгоритмов.

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

Кластерный анализ позволяет сокращать размерность данных, делать ее наглядной.

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

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

Задачи кластерного анализа можно объединить в следующие группы:

Разработка типологии или классификации.

Исследование полезных концептуальных схем группирования объектов.

Представление гипотез на основе исследования данных.

Проверка гипотез или исследований для определения, действительно ли типы (группы), выделенные тем или иным способом, присутствуют в имеющихся данных.

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

Цель занятия

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

Практическое задание

Разработать алгоритмы методов ближнего соседа и k -средних и реализовать их в виде компьютерных программ. С помощью ДСЧ сгенерировать 50 реализаций x = (x 1 , x 2) – случайной 2-мерной величины, координаты которой распределены равномерно в интервале (3,8). Распределить их с помощью разработанных программ на минимальное число кластеров, каждый из которых помещается в сфере радиуса 0,15.

Методические указания

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

Кластер имеет следующие математические характеристики:

дисперсия кластера;
среднеквадратическое отклонение.

Центр кластера – это среднее геометрическое место точек в пространстве переменных.

Радиус кластера – максимальное расстояние точек от центра кластера.

Дисперсия кластера – это мера рассеяния точек в пространстве относительно центра кластера.

Среднеквадратичное отклонение (СКО) объектов относительно центра кластера – квадратный корень из дисперсии кластера.

Методы кластерного анализа

Методы кластерного анализа можно разделить на две группы:

иерархические;

неиерархические.

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

Используя различные методы кластерного анализа, аналитик может получить различные решения на одних и тех же данных. Это считается нормальным явлением.

Иерархические методы кластерного анализа

Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.

Иерархические агломеративные методы (Agglomerative Nesting, AGNES)

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

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

Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)

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

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

Меры сходства

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

Евклидово расстояние является геометрическим расстоянием в многомерном пространстве и вычисляется по формуле (4.1).

Евклидово расстояние (и его квадрат) вычисляется по исходным, а не по стандартизованным данным.

Квадрат евклидова расстояния вычисляется по формуле (4.2).

(4.2)

Манхэттенское расстояние (расстояние городских кварталов), также называемое «хэмминговым» или «сити-блок» расстоянием, рассчитывается как среднее разностей по координатам. В большинстве случаев эта мера расстояния приводит к результатам, подобным расчетам евклидова расстояния. Однако, для этой меры влияние отдельных выбросов меньше, чем при использовании евклидова расстояния, поскольку здесь координаты не возводятся в квадрат. Манхэттенское расстояние вычисляется по формуле (4.3).

(4.3)

Расстояние Чебышева стоит использовать, когда необходимо определить два объекта как «различные», если они отличаются по какому-то одному измерению. Расстояние Чебышева вычисляется по формуле (4.4).

(4.4)

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

(4.5)

где r и p - параметры, определяемые пользователем. Параметр p отвечает за постепенное взвешивание разностей по отдельным координатам, параметр r за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра r и p равны двум, то это расстояние совпадает с расстоянием Евклида.

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

(4.6)

Методы объединения или связи

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

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

Полная связь (метод наиболее удаленных соседей) – расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т. е. «наиболее удаленными соседями»).

Невзвешенное попарное среднее– расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них.

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

Невзвешенный центроидный метод – расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.

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

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

Метод ближайшего соседа

Расстояние между двумя классами определяется как расстояние между ближайшими их представителями.

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

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

Итеративные методы.

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

Такая неиерархическая кластеризация состоит в разделении набора данных на определенное количество отдельных кластеров. Существует два подхода. Первый заключается в определении границ кластеров как наиболее плотных участков в многомерном пространстве исходных данных, т. е. определение кластера там, где имеется большое «сгущение точек». Второй подход заключается в минимизации меры различия объектов.

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

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

Алгоритм k-средних (k-means)

Среди итеративных методов наиболее популярным методом является метод k - средних Мак-Кина. В отличие от иерархических методов в большинстве реализаций этого метода сам пользователь должен задать искомое число конечных кластеров, которое обычно обозначается «k ». Алгоритм k- средних строит k кластеров, расположенных на возможно больших расстояниях друг от друга. Основное требование к типу задач, которые решает алгоритм k -средних, – наличие предположений (гипотез) относительно числа кластеров, при этом они должны быть различны настолько, насколько это возможно. Выбор числа k может базироваться на результатах предшествующих исследований, теоретических соображениях или интуиции.

Как и в иерархических методах кластеризации, пользователь при этом может выбрать тот или иной тип меры сходства. Разные алгоритмы метода k -средних отличаются и способом выбора начальных центров задаваемых кластеров. В некоторых вариантах метода сам пользователь может (или должен) задать такие начальные точки, либо выбрав их из реальных наблюдений, либо задав координаты этих точек по каждой из переменных. В других реализациях этого метода выбор заданного числа k начальных точек производится случайным образом, причем эти начальные точки (центры кластеров) могут в последующем уточняться в несколько этапов. Можно выделить 4 основных этапа таких методов:

выбираются или назначаются k наблюдений, которые будут первичными центрами кластеров;

при необходимости формируются промежуточные кластеры приписыванием каждого наблюдения к ближайшим заданным кластерным центрам;

после назначения всех наблюдений отдельным кластерам производится замена первичных кластерных центров на кластерные средние;

предыдущая итерация повторяется до тех пор, пока изменения координат кластерных центров не станут минимальными.

Общая идея алгоритма: заданное фиксированное число k кластеров наблюдения сопоставляются кластерам так, что средние в кластере (для всех переменных) максимально возможно отличаются друг от друга.

Описание алгоритма

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

Выбирается число k и k точек. На первом шаге эти точки считаются «центрами» кластеров. Каждому кластеру соответствует один центр. Выбор начальных центроидов может осуществляться следующим образом:

выбор k- наблюдений для максимизации начального расстояния;

случайный выбор k- наблюдений;

выбор первых k- наблюдений.

Затем каждый объект назначается определенному наиболее близкому кластеру.

Итеративный процесс.

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

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

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

Проверка качества кластеризации

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

Достоинства алгоритма k-средних :

простота использования;

быстрота использования;

понятность и прозрачность алгоритма.

Недостатки алгоритма k-средних :

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

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

Отчет должен содержать:

описание и блок-схемы алгоритмов;

исходные тексты программных модулей;

результаты работы алгоритмов в виде графиков.

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

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

Алгоритм k-средних (k-means)

Наиболее распространен среди неиерархических методов алгоритм k-средних , также называемый быстрым кластерным анализом . Полное описание алгоритма можно найти в работе Хартигана и Вонга (Hartigan and Wong, 1978). В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо иметь гипотезу о наиболее вероятном количестве кластеров.

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

Описание алгоритма

Первоначальное распределение объектов по кластерам.
Выбирается число k, и на первом шаге эти точки считаются "центрами" кластеров. Каждому кластеру соответствует один центр.

Выбор начальных центроидов может осуществляться следующим образом:
- выбор k-наблюдений для максимизации начального расстояния;
- случайный выбор k-наблюдений;
- выбор первых k-наблюдений.
В результате каждый объект назначен определенному кластеру.
Итеративный процесс.
Вычисляются центры кластеров , которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются.

Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий:
- кластерные центры стабилизировались, т.е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации;
- число итераций равно максимальному числу итераций.
На рис. 14.1 приведен пример работы алгоритма k-средних для k, равного двум.

Рис. 14.1.

Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты.

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