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

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

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

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

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

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

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

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

– 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. На следующем шаге алгоритма помещаем центр сферы в точку и определяем расстояние каждого объекта до нового центра.

10.1.1 Основные понятия.

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

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

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

,

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

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

Переводится понятие кластер (cluster) как "скопление", "гроздь". Синонимами термина " кластеризация " являются "автоматическая классификация ", "обучение без учителя" и "таксономия".

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

Характеристиками кластера можно назвать два признака:

внутренняя однородность;

внешняя изолированность.

Кластеры могут быть непересекающимися, или эксклюзивными (non-overlapping, exclusive), и пересекающимися (overlapping). Схематическое изображение непересекающихся и пересекающихся кластеров дано на рис. 10.1.

Рис. 10.1 Непересекающиеся и пересекающиеся кластеры

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

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

10.1.2 Характеристики кластера

Кластер имеет следующие математические характеристики: центр, радиус, среднеквадратическое отклонение, размер кластера.

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

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

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

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

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

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

Кластерный анализ: проблемы в использовании

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

Иерархический кластерный анализ

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

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

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

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

Для оценки результатов кластеризации применяют следующие критерии:

• индекс четкости;
• коэффициент разбиения;
• обычная, нормализованная и модифицированная энтропия;
• второй и третий функционал Рубенса.

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

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

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

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

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

Некоторые методы кластерного анализа особенно чувствительны к шумам или выбросам, другие - менее.

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

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

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

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

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

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

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

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

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

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

Сущность этих методов при помощи дендрограммы иллюстрирована рис. 10.4.

Рис. 10.4 Дендрограмма агломеративных и дивизимных методов

Программная реализация алгоритмов кластерного анализа широко представлена в различных инструментах Data Mining, которые позволяют решать задачи достаточно большой размерности. Например, агломеративные методы реализованы в пакете SPSS, дивизимные методы - в пакете Statgraf.

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

Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron - "дерево"), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.

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

Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально. Пример горизонтальной дендрограммы приведен на рис. 10.4, вертикальной дендрограммы - на рис. 10.5.

Рис. 10.5. Вертикальная дендрограмма

На рис 10.5 на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8, 9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.

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

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

Энциклопедичный YouTube

• 1 / 5

  Кластерный анализ выполняет следующие основные задачи:

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

  Независимо от предмета изучения применение кластерного анализа предполагает следующие этапы:

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

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

  Типология задач кластеризации

  Типы входных данных

  В современной науке применяется несколько алгоритмов обработки входных данных. Анализ путём сравнения объектов, исходя из признаков, (наиболее распространённый в биологических науках) называется Q -типом анализа, а в случае сравнения признаков, на основе объектов - R -типом анализа. Существуют попытки использования гибридных типов анализа (например, RQ -анализ), но данная методология ещё должным образом не разработана.

  Цели кластеризации

  • Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй »).
  • Сжатие данных . Если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.
  • Обнаружение новизны (англ. novelty detection ). Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров.

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

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

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

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

  1. Вероятностный подход . Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).
  2. Подходы на основе систем искусственного интеллекта: весьма условная группа, так как методов очень много и методически они весьма различны.
  3. Логический подход. Построение дендрограммы осуществляется с помощью дерева решений.
  4. Теоретико-графовый подход.
  5. Иерархический подход. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы в свою очередь подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации.
     • Иерархическая дивизивная кластеризация или таксономия. Задачи кластеризации рассматриваются в количественной таксономии .
  6. Другие методы. Не вошедшие в предыдущие группы.
     • Статистические алгоритмы кластеризации
     • Ансамбль кластеризаторов
     • Алгоритмы семейства KRAB
     • Алгоритм, основанный на методе просеивания

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

  Формальная постановка задачи кластеризации

  Пусть X {\displaystyle X} - множество объектов, Y {\displaystyle Y} - множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами ρ (x , x ′) {\displaystyle \rho (x,x")} . Имеется конечная обучающая выборка объектов X m = { x 1 , … , x m } ⊂ X {\displaystyle X^{m}=\{x_{1},\dots ,x_{m}\}\subset X} . Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами , так, чтобы каждый кластер состоял из объектов, близких по метрике ρ {\displaystyle \rho } , а объекты разных кластеров существенно отличались. При этом каждому объекту x i ∈ X m {\displaystyle x_{i}\in X^{m}} приписывается номер кластера y i {\displaystyle y_{i}} .

  Алгоритм кластеризации - это функция a: X → Y {\displaystyle a\colon X\to Y} , которая любому объекту x ∈ X {\displaystyle x\in X} ставит в соответствие номер кластера y ∈ Y {\displaystyle y\in Y} . Множество Y {\displaystyle Y} в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

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

  В социологии

  При анализе результатов социологических исследований рекомендуется осуществлять анализ методами иерархического агломеративного семейства, а именно методом Уорда, при котором внутри кластеров оптимизируется минимальная дисперсия, в итоге создаются кластеры приблизительно равных размеров. Метод Уорда наиболее удачен для анализа социологических данных. В качестве меры различия лучше квадратичное евклидово расстояние, которое способствует увеличению контрастности кластеров. Главным итогом иерархического кластерного анализа является дендрограмма или «сосульчатая диаграмма». При её интерпретации исследователи сталкиваются с проблемой того же рода, что и толкование результатов факторного анализа - отсутствием однозначных критериев выделения кластеров. В качестве главных рекомендуется использовать два способа - визуальный анализ дендрограммы и сравнение результатов кластеризации, выполненной различными методами.

  Визуальный анализ дендрограммы предполагает «обрезание» дерева на оптимальном уровне сходства элементов выборки. «Виноградную ветвь» (терминология Олдендерфера М. С. и Блэшфилда Р. К. ) целесообразно «обрезать» на отметке 5 шкалы Rescaled Distance Cluster Combine, таким образом будет достигнут 80 % уровень сходства. Если выделение кластеров по этой метке затруднено (на ней происходит слияние нескольких мелких кластеров в один крупный), то можно выбрать другую метку. Такая методика предлагается Олдендерфером и Блэшфилдом.

  Теперь возникает вопрос устойчивости принятого кластерного решения. По сути, проверка устойчивости кластеризации сводится к проверке её достоверности. Здесь существует эмпирическое правило - устойчивая типология сохраняется при изменении методов кластеризации. Результаты иерархического кластерного анализа можно проверять итеративным кластерным анализом по методу k-средних. Если сравниваемые классификации групп респондентов имеют долю совпадений более 70 % (более 2/3 совпадений), то кластерное решение принимается.

  Проверить адекватность решения, не прибегая к помощи другого вида анализа, нельзя. По крайней мере, в теоретическом плане эта проблема не решена. В классической работе Олдендерфера и Блэшфилда «Кластерный анализ» подробно рассматриваются и в итоге отвергаются дополнительные пять методов проверки устойчивости:

  1. кофенетическая корреляция - не рекомендуется и ограниченна в использовании;
  2. тесты значимости (дисперсионный анализ) - всегда дают значимый результат;
  3. методика повторных (случайных) выборок, что, тем не менее, не доказывает обоснованность решения;
  4. тесты значимости для внешних признаков пригодны только для повторных измерений;
  5. методы Монте-Карло очень сложны и доступны только опытным математикам [ (англ. edge detection ) или распознавания объектов .
  6. Интеллектуальный анализ данных (англ. data mining) - кластеризация в Data Mining приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию.