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

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

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

Задача кластерного анализа — разбиение набора объектов на группы, при этом попутно определяется число этих групп. Группы, на которые разбивается выборка, называются кластеры.

13.1 Геометрическая интерпретация задачи кластеризации

Напомним себе, что

  • компьютер умеет работать только с числами
  • упорядоченое множество объектов одного типа есть вектор
  • каждый вектор мы [когда-то давно] договаривались начинать из начала координат, а значит, может описать его только координатами конца

Теперь посмотрим на данные. Как мы знаем,

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

Любой объект мы можем описать числовым вектором, где числа задают значение характеристик объектов. Если это количественные характеристики, то тут всё понятно — это сами числовые значения переменных. А если характеристики качественные? Никаких проблем — мы их перекодируем в числа! Если это бинарные переменные (например, пол или ступень обучения «бакалавр»/«магистр»), то одну категорию обозначим 0, другую — 1. Если категорий больше, то у нас просто будет больше чисел-индикаторов. Итого, каждое наблюдение описывается числовым вектором, а следовательно, и некоторой точкой в пространстве.

Каково это пространство? Оси — это переменные, то есть характеристики объектов. Измерений в этом признаковом пространстве столько, сколько переменных в нашем датасете.

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

Итого, summary геометрической задачи:

  • каждый из \(n\) рассматриваемых объектов — это точка в некотором \(p\)-мерном признаковом пространстве;
  • похожие объекты будут располагаться «близко» друг с другу;
  • различающиеся объекты будут располагаться «далеко» друг от друга;
  • скопления точек — это искомые кластеры.

13.2 Проблема кластеризации

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

Сколько здесь кластеров? Кто-то скажет, что их три:

Кто-то скажет, что их четыре:

Кто-то скажет, что их всё же три, но выглядят они по-другому:

Что мы здесь наблюдаем? Проблему. Разные методы кластеризации могут давать разные результаты. Какой из них верный? Неясно… так как истинная группировка данных нам неизвестна. Но мы будем пытаться как-то выживать в ситуаций такой неопределённости.

13.3 Расстояние между объектами

Обратим внимание на следующий важный момент. Мы оперируем терминами «близко» и «далеко» — но как мы определаем расстояние между объектами? Рассмотрим самые популярные и важные для нас варианты.

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

С одним из них мы знакомы ещё со школы — это евклидово расстояние между точками. По смыслу это длина отрезка, соединяющего две точки. Оно определяется как корень из суммы квадратов покоординатных разностей. Пусть у нас есть две точки — \((x_1, x_2, \dots, x_p)\) и \((y_1, y_2, \dots, y_p)\). Евклидово расстояние будет определяться по формуле:

\[ d_{\text{Eucl},XY} = \sqrt{\sum_{j=1}^p (x_j - y_j)^2} \]

Иногда также используется квадрат евклидова расстояния1.

13.3.2 Манхэттеновское расстояние

Оно же блок-расстояние, или расстояние таксиста, или Майкопское расстояние.

Славный российский город Майкоп — а именно его улицы — устроен так:

Какое расстояние проедет таксист из точки \(A\) в точку \(B\)?

Правильно, вот такое2:

Схожая логика может быть использована и при расчёте расстояния между точками3:

Математически это будет определено так:

\[ d_{\text{Manh},XY} = \sum^p_{j=1} |x_j - y_j| \]

13.3.3 Евклид vs Манхэттен

Когда какое расстояние выбирать? Здесь два важных момента.

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

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

13.3.4 Другие виды расстояний

Отметим, что есть и другие виды расстояний, когда мы работает не с числовыми объектами. Например, мы можем пытаться кластеризовать слова — задача непростая, но её можно пытаться решить. Например, с помощью расстояний Хэмминга или Левенштейна. Для более специфичных объектов могут понадобиться и более изощрённые метрики расстояний. Да и вообще «никакое время, потраченное на раздумья, какое расстояние выбрать, не будет потрачено зря»4.

13.4 Проблема операционализации расстояния

Но вообще нам надо здесь поговорить ещё вот о чём: как вообще мы определяем, что есть расстояние между объектами? То есть как мы его операционализируем?

Например, мы хотим кластеризовать наших испытуемых на «эффективных решателей задачи» и «неэффективных решателей задачи». По каким параметрам мы это будем делать? Как вариант — время решения и число ошибок в ходе решения. А как мы будем замерять эти переменные? Первую, видимо, в непрерывной шкале, вторую — в дискретной. Далее будем решать вопрос о выборе конкретной метрики расстояния.

Хорошо, а как нам кластеризовать менеджеров на «хороших», «плохих» и «средненьких продажников»? Можем использовать разные подходы: оценку 360, показатели KPI и т. д.

А как нам определять расстояние между сайтами? По каким показателям? Здесь вариантов ещё больше и всё зависит от конкретной аналитической задачи.

Это всё о чем? О том, что операционализировать расстояние не так-то просто и для разных задач расстояние между одними и теми же объектами может быть операционализировано по-разному.

13.5 Субъективность кластерного анализа

Мы плавно подъехали к ещё одной проблеме-особенности. Какова роль аналитика в кластерном анализе? Достаточно велика:

  • отбор переменных для анализа
  • какие переменные включать в анализ? все? или необходимо проводить отбор?
  • возможно наличие переменных, которые будут хорошо работать с точки зрения поиска схожих объектов, но это не то сходство, которое мы ищем
  • одни переменные могут быть косвенно заменены другими (уровень дохода — профессия, образование, стаж работы)
  • «ковариаты» могут быть важны при формировании кластеров (число учащихся и учителей в школах)
  • правильный выбор переменных крайне важен
  • критерием при отборе переменных выступает ясность интерпретации полученного результата и «интуиция исследователя»
  • метод стандартизации
    • качество кластеризации может зависит от выбранного метода стандартизации
  • выбор метрики для расстояния между объектами
  • выбор метрики для расстояния между кластерами
    • если кластеры выражены, то метрика не важна
    • если появляются кластеры сложной формы (например, ленточные), то всё становится сложнее
  • [иногда] определение числа кластеров
  • интерпретация результатов
    • результаты кластерного анализа нуждаются в интерпретации (если он не решает чисто техническую задачу сокращения размерности данных)
    • лучший результат кластеризации — это тот, который вы смогли понять и проинтерпретировать

13.6 Расстояние между кластерами

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

13.6.1 Среднее невзвешенное расстояние

Среднее невзвешенное рассрояние (Average linkage clustering) определяется так:

  • находим расстояния между всеми парами объектов двух кластеров
  • усредняем их

13.6.2 Центроидный метод

Ранее был самым популярным из-за вычислительной простоты. Определяется расстояние между центрами тяжести двух кластеров. В настоящее время используется крайне мало.

13.6.3 Метод дальнего соседа

Расстояние между кластерами определяется как расстояние между наиболее удалёнными объектами кластеров.

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

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

13.7 Иерархическая кластеризация

13.7.1 Алгоритм иерархического кластерного анализа

  1. Каждый объект объявляется кластером — из \(n\) наблюдений получается \(n\) кластеров.
  2. Выбираются два ближайших кластера — они объединяются.
  3. Выбираются два ближайших кластера — они объединяются [2].
  4. Выбираются два ближайших кластера — они объединяются [3].
  5. Так происходит до тех пор, пока не остается два кластера.
  6. Оставшиеся два кластера являются ближайшими друг с другу — поэтому объединяются в один.

Звучит, как какой-то сюр — начали с \(n\) кластеров по одному объекту, закончили один кластером, содержащим все объекты… Да, в таком исполнении, действительно, странная процедура. Однако если мы на каком-то этапе её прервём, то получим желаемый результат.

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

13.7.2 Дендрограмма

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

Принцип построения дендрограммы следующий:

  1. На прямой располагаются все наблюдения как отдельные кластеры.
  2. Каждому кластеру соответствует вертикальная линия.
  3. Каждому объединению кластеров соответствует горизонтальная линия.
  4. Высота, на которой кластеры соединяются, отражает расстояние между кластерами.

Разберемся с этим на примере.

  • У нас есть пять наблюдений. Первоначально мы объявляем все их кластерами — получаем пять кластеров. - - Договоримся, что расстояние между наблюдениями у нас манхэттеновское, а расстояние между кластерами — среднее невзвешенное, ибо так проще считать.
  • [Итерация 1]
    • Далее ищем два ближайших — это кластеры 1 и 2.
    • Объединяем их.
    • Отображаем это на дендрограмме — соединяем линии 1 и 2 между собой на высоте 1, так как расстояние между объединяемым кластерами равно единице.
    • Теперь у нас четыре кластера.
  • [Итерация 2]
    • Снова ищем два ближайших кластера — это 4 и 5.
    • Объединяем их на высоте 2, так как расстояние между ними равно двум.
    • Остаётся три кластера.
  • [Итерация 3]
    • Снова ищем два ближайщих кластера — на этот раз это 3 и 4-5.
    • Объединяем их на высоте 3, так как расстояние между ними равно трём.
  • [Итерация 4]
    • Остаётся только два кластера — соединяем их на каком-то большом расстоянии.

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

13.7.3 Каменистая осыпь

Ещё один способ определить число кластеров — это график «каменистая осыпь».

В данном случае по оси \(x\) располагаются шаги объединения, по оси \(y\) — расстояние между кластерами в момент объединения. Как именно нам помогает такой график?

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

13.7.4 Когда кластеризации нет?

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

13.7.5 Чем плох иерархический кластерный анализ?

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

13.8 Метод k-средних (k-means)

13.8.1 Алгоритм метода k-средних

Процедура кластерного анализа этим методом значительно отличается.

  1. Заранее определяется число кластеров \(k\). Хотя вообще-то это невозможно, однако уже найдены способы, чтобы обойти это ограничение.
  2. Для анализа выбирается \(k\) точек — центры кластеров.
  3. Объект приписывается к тому кластеру, чей центр ближайший.
  4. Центр кластера — центр тяжести объектов кластера.
  • центр тяжести множества точек с координатами \((x_{i1}, x_{i2}, \dots, x_{ip})\) — это точка с координатами \((\bar x_1, \bar x_2, \dots, \bar x_p)\).
  1. Повторяем поочерёдно пункты 3 и 4 до тех пор, пока центры кластеров не перестанут двигаться.

Визуализацию можно посмотреть тут.

13.8.2 Ограничения k-means

  • Необходимо заранее определить число кластеров
  • Используется только евклидово растояние
    • хотя этот недостаток исправляется в других модификациях метода
  • Результат зависит от начальных центров кластеров

13.8.3 Начальное положение кластеров

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

  1. Forgy — Случайным образом выбираются \(k\) наблюдений. Они объявляются начальными центрами кластеров.
  2. Случайное разбиение (Random Partition) — Каждое наблюдение случайным образом приписывается к одному из кластеров. Находятся центры тяжести кластеров. Они объявляются начальными центрами кластеров.

13.9 Метрики качества кластеризации

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

13.9.1 Внешние метрики

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

Но зачем нам проводить кластерный анализ, если нам уже известны кластеры? Ведь это тогда не кластеры, а классы! И мы можем строить классификатор. Так-то оно, конечно, так — и нам, аналитикам, эти метрики не очень интересны. Для разработчиков алгоритмов же они могут быть очень полезны.

Мы не будем на них останавливаться. Если хочется почитать и вникнуть, то вот.

13.9.2 Внутренние метрики

Эти метрики не используют внешний информации о датасете, а опираются только на результаты кластеризации.

13.9.2.1 Компактность кластеров (cluster cohesion)

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

\[ \text{WSS} = \sum_{j=1}^k \sum^{|C_j|}_{i=1} (x_{ij} − \bar x_j)^2, \]

где \(k\) — число кластеров, \(|C_j|\) — количество объектов в данном кластере.

Это самая популярная метрика качества кластеризации.

13.9.2.2 Отделимость кластеров (cluster separation)

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

\[ \text{BSS} = n \cdot \sum_{j=1}^k (\bar x_j - \bar x)^2, \]

где \(k\) — число кластеров.

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

13.10 Нечеткая кластеризация

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

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

Для решения задачи нечёткой кластеризации (fuzzy clustering) используется метод C-средних (C-means), который является усовершенствованием метода k-средних. Он позволяет разбить наблюдения на заданное число \(k\) нечетких кластеров. Нечеткость выражается как раз в том, что в ходе алгоритма рассчитывается степень принадлежности (membership value) наблюдения к каждому из кластеров.

Рассмотрим шаги алгоритма для простейшего случая. Пусть исходно имеются четыре наблюдения в двумерном признаковом пространстве с координатами \((1,3), (2,5), (6,8), (7,9)\). Эти наблюдения мы будем разбивать на два кластера.

  1. Каждому наблюдению присваивается случайное число, задающее его принадлежность к кластеру.
Кластер \((1,3)\) \((2,5)\) \((4,8)\) \((7,9)\)
1 0.8 0.7 0.2 0.1
2 0.2 0.3 0.8 0.9
  1. Вычисляются центры (центроиды) кластеров.

\[ V_{ij} = \frac{\sum_{k=1}^n \gamma_{ik}^m x^{(j)}_k}{\sum_{k=1}^n \gamma_{ik}^m}, \]

где \(\gamma\) — membership value, \(m\) — fuzziness parameter (степень нечеткости кластеров, стандартное значение — от 1.2 до 2), \(x^{(j)}_k\) — координата наблюдения, \(i\) — номер кластера, \(j\) — номера координаты.

Для представленной таблицы координаты центроидов будут таковы:

\[ \begin{split} \mathbf{V}_1 &= (V_{11}, V_{12}) = (1.568, 4.051) \\ \mathbf{V}_1 &= (V_{21}, V_{22}) = (5.350, 8.215) \end{split} \]

  1. Расчитываются расстояния от каждого наблюдения до центров (центроидов) кластеров.

Если использовать евклидово расстояние, то для рассматриваемого примера они будут такими:

Кластер \((1,3)\) \((2,5)\) \((4,8)\) \((7,9)\)
1 \(d_{11} = 1.2\) \(d_{21} = 1.04\) \(d_{31} = 4.63\) \(d_{41} = 7.34\)
2 \(d_{12} = 6.79\) \(d_{22} = 4.64\) \(d_{32} = 1.36\) \(d_{42} = 1.82\)
  1. Обновляются значения membership values для наблюдений по следующей формуле:

\[ \gamma_{pi} = \Bigg( \sum_{j=1}^J \Big( \frac{d_{pi}^2}{d_{pj}^2} \Big) ^{\frac{1}{m-1}} \Bigg)^{-1}, \]

где \(i\) — номер кластера, \(p\) — номер наблюдения, \(d\) — расстояние между наблюдением и центром кластера, \(J\) — количество кластеров, \(m\) — fuzziness parameter.

В рассматриваемом примере получатся такие значения:

Кластер \((1,3)\) \((2,5)\) \((4,8)\) \((7,9)\)
1 0.97 0.95 0.08 0.06
2 0.03 0.05 0.92 0.94
  1. Повторяются шаги 2–4 до тех пор, пока значения membership values не перестанут меняться.

По полученой таблице и определяется структура данных — или её отсутствие.

  1. Хотя математически эта метрика не является расстоянием, так как может нарушаться неравенство треугольника. Однако для задач кластерного анализа это не имеет большого значения.↩︎

  2. Заметьте, что в количестве кварталов все расстояния равны.↩︎

  3. Заметьте, что длина всех траекторий также будет одинакова.↩︎

  4. Вадим Аббакумов, лекция в Computer Science Center↩︎