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

Энциклопедичный 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 приобретает ценность тогда, когда она выступает одним из этапов анализа данных, построения законченного аналитического решения. Аналитику часто легче выделить группы схожих объектов, изучить их особенности и построить для каждой группы отдельную модель, чем создавать одну общую модель для всех данных. Таким приемом постоянно пользуются в маркетинге, выделяя группы клиентов, покупателей, товаров и разрабатывая для каждой из них отдельную стратегию.

  Мы знаем, что Земля – это одна из 8 планет, которые вращаются вокруг Солнца. Солнце – это всего лишь звезда среди порядка 200 миллиардов звезд в галактике Млечный Путь. Очень тяжело осознать это число. Зная это, можно сделать предположение о количестве звезд во вселенной – приблизительно 4X10^22. Мы можем видеть около миллиона звезд на небе, хотя это всего лишь малая часть от всего фактического количества звезд. Итак, у нас появилось два вопроса:

  1. Что такое галактика?
  2. И какая связь между галактиками и темой статьи (кластерный анализ)

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

  Как мы будем обсуждать в следующем разделе, есть много общего между галактиками и кластерным анализом. Галактики существуют в трехмерном пространстве, кластерный анализ – это многомерный анализ, проводимый в n-мерном пространстве.

  Заметка: Черная дыра – это центр галактики. Мы будем использовать похожую идею в отношении центроидов для кластерного анализа.

  Кластерный анализ

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

  

  Для лучшего восприятия нарисуем график, где по оси x будет откладываться средняя продолжительность международных разговоров, а по оси y - средняя продолжительность локальных разговоров. Ниже график:

  

  Заметка: Это похоже на анализ расположения звезд на ночном небе (здесь звезды заменены потребителями). В дополнение, вместо трехмерного пространства у нас двумерное, заданное продолжительностью локальных и международных разговоров, в качестве осей x и y.
  Сейчас, разговаривая в терминах галактик, задача формулируется так – найти положение черных дыр; в кластерном анализе они называются центроидами. Для обнаружения центроидов мы начнем с того, что возьмем произвольные точки в качестве положения центроидов.

  Евклидово расстояние для нахождения Центроидов для Кластеров

  В нашем случае два центроида (C1 и C2) мы произвольным образом поместим в точки с координатами (1, 1) и (3, 4). Почему мы выбрали именно эти два центроида? Визуальное отображение точек на графике показывает нам, что есть два кластера, которые мы будем анализировать. Однако, впоследствии мы увидим, что ответ на этот вопрос будет не таким уж простым для большого набора данных.
  Далее, мы измерим расстояние между центроидами (C1 и C2) и всеми точками на графике использую формулу Евклида для нахождения расстояния между двумя точками.

  Примечание: Расстояние может быть вычислено и по другим формулам, например,

  1. квадрат евклидова расстояния – для придания веса более отдаленным друг от друга объектам
  2. манхэттенское расстояние – для уменьшения влияния выбросов
  3. степенное расстояние – для увеличения/уменьшения влияния по конкретным координатам
  4. процент несогласия – для категориальных данных
  5. и др.
  Колонка 3 и 4 (Distance from C1 and C2) и есть расстояние, вычисленное по этой формуле. Например, для первого потребителя

  Принадлежность к центроидам (последняя колонка) вычисляется по принципу близости к центроидам (C1 и C2). Первый потребитель ближе к центроиду №1 (1.41 по сравнению с 2.24) следовательно, принадлежит к кластеру с центроидом C1.

  

  Ниже график, иллюстрирующий центроиды C1 и C2 (изображенные в виде голубого и оранжевого ромбика). Потребители изображены цветом соответствующего центроида, к кластеру которого они были отнесены.

  

  Так как мы произвольным образом выбрали центроиды, вторым шагом мы сделать этот выбор итеративным. Новая позиция центроидов выбирается как средняя для точек соответствующего кластера. Так, например, для первого центроида (это потребители 1, 2 и 3). Следовательно, новая координата x для центроида C1 э то средняя координат x этих потребителей (2+1+1)/3 = 1.33. Мы получим новые координаты для C1 (1.33, 2.33) и C2 (4.4, 4.2).Новый график ниже:

  

  В конце концов, мы поместим центроиды в центр соответствующего кластера. График ниже:

  

  Позиции наших черных дыр (центров кластеров) в нашем примере C1 (1.75, 2.25) и C2(4.75, 4.75). Два кластера выше подобны двум галактикам, разделенным в пространстве друг от друга.

  Итак, рассмотрим примеры дальше. Пусть перед нами стоит задача по сегментации потребителей по двум параметрам: возраст и доход. Предположим, что у нас есть 2 потребителя с возрастом 37 и 44 лет и доходом в $90,000 и $62,000 соответственно. Если мы хотим измерить Евклидово расстояние между точками (37, 90000) и (44, 62000), мы увидим, что в данном случае переменная доход «доминирует» над переменной возраст и ее изменение сильно сказывается на расстоянии. Нам необходима какая-нибудь стратегия для решения данной проблемы, иначе наш анализ даст неверный результат. Решение данной проблемы это приведение наших значений к сравнимым шкалам. Нормализация – вот решение нашей проблемы.

  Нормализация данных

  Существует много подходов для нормализации данных. Например, нормализация минимума-максимума. Для данной нормализации используется следующая формула
  
  в данном случае X* - это нормализованное значение, min и max – минимальная и максимальная координата по всему множеству X
  (Примечание, данная формула располагает все координаты на отрезке )
  Рассмотрим наш пример, пусть максимальный доход $130000, а минимальный - $45000. Нормализованное значение дохода для потребителя A равно

  

  Мы сделаем это упражнение для всех точек для каждых переменных (координат). Доход для второго потребителя (62000) станет 0.2 после процедуры нормализации. Дополнительно, пусть минимальный и максимальный возрасты 23 и 58 соответственно. После нормализации возрасты двух наших потребителей составит 0.4 и 0.6.

  Легко увидеть, что теперь все наши данные расположены между значениями 0 и 1. Следовательно, у нас теперь есть нормализованные наборы данных в сравнимых шкалах.

  Запомните, перед процедурой кластерного анализа необходимо произвести нормализацию.

  Приветствую!

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

  Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.

  Понятие кластеризации

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

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

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

  Меры расстояний

  Итак, как же определять «похожесть» объектов? Для начала нужно составить вектор характеристик для каждого объекта - как правило, это набор числовых значений, например, рост-вес человека. Однако существуют также алгоритмы, работающие с качественными (т.н. категорийными) характеристиками.

  После того, как мы определили вектор характеристик, можно провести нормализацию, чтобы все компоненты давали одинаковый вклад при расчете «расстояния». В процессе нормализации все значения приводятся к некоторому диапазону, например, [-1, -1] или .

  Наконец, для каждой пары объектов измеряется «расстояние» между ними - степень похожести. Существует множество метрик, вот лишь основные из них:

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

  Классификация алгоритмов

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

  Объединение кластеров

  В случае использования иерархических алгоритмов встает вопрос, как объединять между собой кластера, как вычислять «расстояния» между ними. Существует несколько метрик:
  1. Одиночная связь (расстояния ближайшего соседа)
     В этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Результирующие кластеры имеют тенденцию объединяться в цепочки.
  2. Полная связь (расстояние наиболее удаленных соседей)
     В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. наиболее удаленными соседями). Этот метод обычно работает очень хорошо, когда объекты происходят из отдельных групп. Если же кластеры имеют удлиненную форму или их естественный тип является «цепочечным», то этот метод непригоден.
  3. Невзвешенное попарное среднее
     В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты формируют различные группы, однако он работает одинаково хорошо и в случаях протяженных («цепочечного» типа) кластеров.
  4. Взвешенное попарное среднее
     Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому данный метод должен быть использован, когда предполагаются неравные размеры кластеров.
  5. Невзвешенный центроидный метод
     В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.
  6. Взвешенный центроидный метод (медиана)
     Этот метод идентичен предыдущему, за исключением того, что при вычислениях используются веса для учета разницы между размерами кластеров. Поэтому, если имеются или подозреваются значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего.

  Обзор алгоритмов

  Алгоритмы иерархической кластеризации

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

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

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

  Алгоритмы квадратичной ошибки

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

  

  Где c j - «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).

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

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

  К недостаткам данного алгоритма можно отнести необходимость задавать количество кластеров для разбиения.

  Нечеткие алгоритмы

  Наиболее популярным алгоритмом нечеткой кластеризации является алгоритм c-средних (c-means). Он представляет собой модификацию метода k-средних. Шаги работы алгоритма:
  
  Этот алгоритм может не подойти, если заранее неизвестно число кластеров, либо необходимо однозначно отнести каждый объект к одному кластеру.

  Алгоритмы, основанные на теории графов

  Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E) , вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.

  Алгоритм выделения связных компонент

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

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

  Алгоритм минимального покрывающего дерева

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

  

  Путём удаления связи, помеченной CD, с длиной равной 6 единицам (ребро с максимальным расстоянием), получаем два кластера: {A, B, C} и {D, E, F, G, H, I}. Второй кластер в дальнейшем может быть разделён ещё на два кластера путём удаления ребра EF, которое имеет длину, равную 4,5 единицам.

  Послойная кластеризация

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

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

  ,

  Где G t = (V, E t) - граф на уровне с t ,
  ,
  с t – t-ый порог расстояния,
  m – количество уровней иерархии,
  G 0 = (V, o) , o – пустое множество ребер графа, получаемое при t 0 = 1,
  G m = G , то есть граф объектов без ограничений на расстояние (длину ребер графа), поскольку t m = 1.

  Посредством изменения порогов расстояния {с 0 , …, с m }, где 0 = с 0 < с 1 < …< с m = 1, возможно контролировать глубину иерархии получаемых кластеров. Таким образом, алгоритм послойной кластеризации способен создавать как плоское разбиение данных, так и иерархическое.

  Сравнение алгоритмов

  Вычислительная сложность алгоритмов
  
  Сравнительная таблица алгоритмов
  

  Алгоритм кластеризации	Форма кластеров	Входные данные	Результаты
  Иерархический	Произвольная	Число кластеров или порог расстояния для усечения иерархии	Бинарное дерево кластеров
  k-средних	Гиперсфера	Число кластеров	Центры кластеров
  c-средних	Гиперсфера	Число кластеров, степень нечеткости	Центры кластеров, матрица принадлежности
  Выделение связных компонент	Произвольная	Порог расстояния R
  Минимальное покрывающее дерево	Произвольная	Число кластеров или порог расстояния для удаления ребер	Древовидная структура кластеров
  Послойная кластеризация	Произвольная	Последовательность порогов расстояния	Древовидная структура кластеров с разными уровнями иерархии

  Немного о применении

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

  В отличие от полносвязного графа, в ориентированном дереве не все вершины соединены ребрами, при этом общее количество ребер равно n–1, где n – число вершин. Т.е. применительно к узлам дерева, работа алгоритма выделения связных компонент упростится, поскольку удаление любого количества ребер «развалит» дерево на связные компоненты (отдельные деревья). Алгоритм минимального покрывающего дерева в данном случае будет совпадать с алгоритмом выделения связных компонент – путем удаления самых длинных ребер исходное дерево разбивается на несколько деревьев. При этом очевидно, что фаза построения самого минимального покрывающего дерева пропускается.

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

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