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

Обычно анализ начинается с вопроса, на который отвечает заранее известный столбец: различается ли средний чек в двух филиалах, зависит ли от удовлетворённости готовность рекомендовать кафе. У кластеризации такого столбца нет. Она выясняет, не распадаются ли наблюдения на группы, которых никто не выделял (типы покупателей, характерные профили ответов), и ищет их только по сходству строк между собой. Идеи, на которых построен модуль кластерного анализа, разобраны ниже в том порядке, в каком они встречаются на его панели: что такое кластер и что можно кластеризовать; как измеряют расстояние между наблюдениями и зачем сначала приводить переменные к одной шкале; чем расстояние заменяют корреляция и коэффициент Гауэра; как устроены три алгоритма, как читать дерево и где его резать; как выбрать число кластеров и есть ли кластеры в данных вообще; что такое бикластер; как проверить решение на бутстрэп-выборках и изобразить на графике; наконец, что готовое решение утверждает, а чего нет. Модуль просит отметить в списке переменные для кластеризации и выбрать режим кластеризации: по наблюдениям, по переменным или сразу по тем и другим. Все числа получены на данных кафе после трёх исправлений. Участники программы лояльности кластеризуются по стандартизованным столбцам оценка, чек_после и визиты_после. Все три значения заполнены у 192 участников из 200. Шесть пунктов анкеты — вкус, свежесть, цена, приветливо, быстро и медленно — кластеризуются в режиме переменных, и они же образуют матрицу для бикластеризации. Остальные параметры везде оставлены по умолчанию, и любое число на странице можно воспроизвести.

Что делает кластеризация #

Кластеризация — это семейство методов, которые делят объекты на группы по одному только сходству: объекты внутри группы похожи друг на друга больше, чем на объекты из других групп. Здесь нет ни предсказываемого исхода, ни меток для обучения. Этим кластеризация отличается от классификации, которую сначала обучают на размеченных наблюдениях, а затем применяют к новым, и от сравнения, где группы заданы с самого начала. Методу дают строки, переменные, по которым их сравнивать, и способ измерить, насколько далеки две строки друг от друга. Всё остальное (сколько групп, кто в какую попал, что эти группы означают) берётся из данных и из того, как их истолкует аналитик. Сгруппируем 192 участника по оценке кафе, среднему чеку и числу визитов после смены меню. Метод k-средних с тремя кластерами выделяет 13 завсегдатаев (в среднем оценка 5.6, чек 10.3, визиты 23.5), 96 равнодушных с невысокими оценками и небольшим чеком (6.3, 7.5, 5.0) и 83 довольных, которые оставляют в кафе больше других (8.7, 12.2, 8.1). О таких сегментах касса ничего не знала.

Кластер — одна из таких групп, то есть набор наблюдений, которые алгоритм объединил. Кластеры нумеруются от 1 до k, но номера ничего не значат: кластер 1 одного запуска вполне может стать кластером 3 в следующем. Число кластеров k в методах k-средних и k-медоидов аналитик задаёт заранее, а в иерархической кластеризации его определяет высота, на которой разрезано дерево. Распределение всех наблюдений по кластерам, где каждое попадает ровно в один, называется разбиением. Чтобы понять кластер, смотрят на его профиль — средние переменных внутри кластера рядом со средними по всей выборке — и называют кластер по тому, что в профиле выделяется. Так и получили свои названия три сегмента кафе: по визитам, чеку и оценке.

Кластеризация наблюдений, переменных или тех и других — выбор того, что считать объектами. Кластеризация наблюдений группирует строки, а столбцы служат их описанием: каждого участника описывают оценка, чек и число визитов. Кластеризация переменных смотрит на таблицу по столбцам: объектом становится переменная, а её признаками — 192 ответа участников. Две переменные близки, если от участника к участнику они растут и падают вместе, а группы — это наборы переменных, которые ведут себя одинаково. Так без всякой факторной модели находятся подшкалы опросника. Бикластеризация работает сразу по обеим осям: она ищет блок (часть строк на части столбцов), внутри которого значения согласованы, а остальную таблицу не описывает. Этот режим нужен, когда структура затрагивает не все переменные: например, группа участников одинаково отвечает на несколько пунктов, а на остальные — как все.

Расстояние #

Расстояние — это одно число, которое показывает, насколько различаются два объекта по всем переменным сразу: у двух одинаковых строк оно равно нулю и тем больше, чем сильнее они расходятся. В кластеризации его чаще называют мерой различия, потому что не всякая такая мера — расстояние в геометрическом смысле. На нём построены все алгоритмы этой страницы, так что, выбирая меру, аналитик тем самым решает, что значит «похожи». Возьмём первых двух участников из файла кафе. Первый поставил кафе 8, его средний чек 6.37, визитов 6. Второй поставил 9, чек у него 7.83, визитов 2. В исходных единицах разности равны 1, 1.46 и 4, и каждая из пяти мер, описанных ниже, сводит эти три разности в одно число по-своему.

Евклидово расстояние — обычное расстояние по прямой между двумя точками, координатами которых служат переменные:

Разности сначала возводятся в квадрат и лишь потом складываются, поэтому одна большая разность весит больше, чем несколько малых с той же суммой. Для первых двух участников оно равно $\sqrt{1^2+{1.46}^2+4^2}$ = 4.37 в исходных единицах и 0.92 после того, как три переменные стандартизованы. Это расстояние выбрано по умолчанию, и только с ним работает метод k-средних: среднее кластера — именно та точка, для которой сумма квадратов евклидовых расстояний до наблюдений кластера минимальна.

Манхэттенское расстояние (его ещё называют расстоянием городских кварталов) складывает модули разностей, не возводя их в квадрат:

Для первых двух участников оно равно 1 + 1.46 + 4 = 6.46 в исходных единицах и 1.56 после стандартизации. Раз ничего не возводится в квадрат, одна большая разность влияет на него слабее, чем на евклидово расстояние. Поэтому манхэттенское расстояние надёжнее, когда у нескольких наблюдений есть по одному экстремальному значению.

Расстояние Чебышёва (в модуле оно называется Максимум) — наибольшая из разностей, ${\max }_j|x_j-y_j|$. Остальные разности не учитываются. Для первых двух участников оно равно 4 в исходных единицах (это разность в визитах) и 0.64 после стандартизации. Два наблюдения оказываются далеки настолько, насколько они расходятся по самой несхожей переменной. Такая мера уместна, когда решать должно одно крупное расхождение и остальные не должны его сглаживать.

Расстояние Канберра складывает разности, поделив каждую на сумму модулей двух значений:

Разность 1 между 1 и 2 весит столько же, сколько разность 50 между 50 и 100: значения сравниваются в пропорции, и малые из них не теряются. Это удобно для счётных и других неотрицательных переменных, измеренных в шкале отношений. Для первых двух участников в исходных единицах оно равно 0.66. Мера рассчитана на значения не меньше нуля. Стандартизованные переменные лежат по обе стороны от нуля, и пара, где один участник чуть выше среднего, а другой чуть ниже, получает различие почти в целую единицу, каким бы малым ни был настоящий разрыв. Поэтому с Канберрой стандартизацию лучше выключать.

Расстояние Минковского объединяет три предыдущих в одно семейство, а показатель p задаёт, насколько большая разность подавляет остальные:

При p = 1 это манхэттенское расстояние, при p = 2 — евклидово, а с ростом p оно стремится к расстоянию Чебышёва. Для первых двух участников после стандартизации оно равно 1.56 при p = 1, 0.92 при p = 2, 0.78 при p = 3 и дальше убывает к 0.64 — наибольшей из разностей. На практике берут p от 1 до 2: это компромисс между тем, чтобы учитывать каждую разность, и тем, чтобы решала самая большая.

Стандартизация перед кластеризацией приводит все переменные к одной шкале, обычно к z-оценкам: из каждого значения вычитают среднее переменной и делят на её стандартное отклонение. Иначе переменная с самыми крупными числами определяла бы расстояния в одиночку. Оценка измеряется в баллах, чек в деньгах, визиты в числе посещений, и стандартные отклонения у них 1.9, 3.7 и 6.3. Если возвести отклонения от среднего в квадрат и сложить по 192 участникам, на визиты придётся 69% всей вариации, на чек 25%, на оценку 6%, так что кластеризация по исходным числам — это по большей части кластеризация по визитам. Результат это подтверждает. Метод k-средних с тремя кластерами на нестандартизованных переменных даёт кластеры со средней оценкой 7.9, 6.9 и 7.0, то есть оценка их почти не различает, а после стандартизации средние оценки равны 5.6, 6.3 и 8.7. Стандартизация включена по умолчанию и нужна всякий раз, когда переменные измерены в разных шкалах. Выключают её, только если шкала у переменных общая и осмысленная, а разный разброс — часть того, что должна уловить кластеризация. К категориальной переменной стандартизация отношения не имеет: у неё нет шкалы.

Корреляция как мера различия превращает корреляцию r двух переменных в расстояние между ними. Величина 1 − r равна 0 для столбцов, которые меняются синхронно, 1 для несвязанных и 2 для строго противоположных. Величина 1 − |r| знак не учитывает, и переменная для неё неотличима от своего зеркального отражения. На стандартизованных столбцах это не новая геометрия, а всё та же евклидова: квадрат евклидова расстояния между двумя переменными в z-оценках равен $2(n-1)(1-r)$. Поэтому кластеризация переменных всегда работает со стандартизованными данными. Пункты анкеты быстро и медленно коррелируют на уровне −0.42. По мере 1 − r между ними 1.42, почти предельное расстояние для двух переменных, а по 1 − |r| всего 0.58, меньше, чем между вкус и быстро (0.78). У пунктов вкус и свежесть r = 0.51, и расстояние между ними 0.49 при обеих мерах. Если разрезать дерево шести пунктов на две группы, по 1 − |r| получатся {вкус, свежесть, цена} и {приветливо, быстро, медленно} — ровно те две подшкалы, из которых составлена анкета. По 1 − r пункт медленно остаётся в одиночестве против остальных пяти, потому что он сформулирован в обратную сторону. Для опросника с обратными пунктами подходит мера по модулю, а мера со знаком — для переменных, у которых направление входит в смысл.

Коэффициент Гауэра — мера различия для таблиц, где числа перемешаны с категориями. Каждая переменная оценивается по-своему, от 0 до 1: числовая — как модуль разности, делённый на размах переменной; порядковая — так же, но по рангам; категориальная — 0 при совпадении уровней и 1 при несовпадении. Различие двух наблюдений — среднее этих оценок по всем переменным. Сравним первых двух участников по оценке, чеку, визитам, филиал и рекомендует. Пять оценок равны 0.111 (разность 1 при размахе 9), 0.079, 0.093, 0 (оба ходят в «Набережную») и 1 (один рекомендует кафе, другой нет), а их среднее — 0.257. Последнее слагаемое показывает главную особенность коэффициента: несовпадение категорий сразу даёт 1, тогда как числовая разность — лишь долю размаха, поэтому в среднем категориальные переменные перевешивают. Метод k-медоидов с тремя группами по Гауэру на этих пяти переменных выделяет три группы: 84 посетителя «Набережной», рекомендующих кафе, 50 посетителей «Привокзальной», не рекомендующих его, и 58 посетителей «Привокзальной», рекомендующих. Разбиение по сути задают два категориальных столбца, а три числовых лишь добавляют оттенки. Коэффициент Гауэра нужен, когда категориальная переменная действительно должна участвовать в кластеризации. Если все переменные числовые, обычное расстояние ведёт себя лучше.

Алгоритмы #

Кластеризация методом k-средних выбирает k центров, относит каждое наблюдение к ближайшему, переносит каждый центр в среднее отнесённых к нему наблюдений и повторяет это, пока центры не перестанут сдвигаться. Результат минимизирует внутрикластерную сумму квадратов, то есть сложенные вместе квадраты евклидовых расстояний от наблюдений до центров их кластеров. Отсюда и форма кластеров: они округлые, примерно одинаковые по разбросу и разделены прямыми границами, а вытянутая или кольцеобразная группа распадается на куски. Процедура только улучшает решение и никогда не начинает заново, так что итог зависит от начальных центров. Поэтому её запускают многократно из случайных начальных точек и оставляют лучший результат. Методу нужны заранее заданное k и евклидово расстояние: среднее минимизирует сумму квадратов именно евклидовых расстояний, и никаких других. На стандартизованных оценке, чеке и визитах при k = 3 метод сходится за два прохода к тем самым 13, 96 и 83 участникам. Разбиение объясняет 249 из 573 единиц общей вариации (43.5%), остальное приходится на разброс внутри кластеров.

Медоид — наблюдение кластера, которое в среднем меньше всего отличается от остальных: самое центральное наблюдение, подобно тому как среднее — самая центральная точка. Метод k-медоидов использует медоиды в роли центров: каждое наблюдение относится к ближайшему медоиду, а медоид заменяется другим наблюдением своего кластера, если замена уменьшает суммарное различие, и так до тех пор, пока замены не перестанут помогать. Медоид — реальное наблюдение, а не вычисленная точка. Поэтому метод работает с любой мерой различия, в том числе с коэффициентом Гауэра и корреляциями, и далёкое наблюдение не может перетянуть центр к себе, как перетягивает среднее. На трёх стандартизованных переменных кафе при k = 3 метод k-медоидов даёт группы из 70, 48 и 74 участников. Их медоиды — участники 75, 83 и 48 из файла: (оценка 7, чек 6.58, 4 визита), (5, 10.86, 7) и (9, 11.78, 8). Так у каждого сегмента появляется живой представитель.

Иерархическая кластеризация начинает с того, что каждое наблюдение — отдельный кластер, и на каждом шаге сливает два самых близких кластера, пока все наблюдения не окажутся в одном. Для 192 участников это 191 слияние, и их последовательность образует дерево. Решение с k кластерами — это дерево, разрезанное там, где остаётся k ветвей. Ничего не задаётся заранее и ничего не выбирается случайно: одни и те же данные при одних и тех же настройках всегда дают одно и то же дерево. Дерево показывает сразу все вложенные решения, поэтому k можно выбрать по его строению, а не назначать произвольно. Что значит «ближайшие» для двух кластеров, а не для двух наблюдений, определяет метод связи, и на результат он влияет не меньше, чем расстояние. Метод Уорда на трёх переменных кафе при разрезе на три кластера даёт 119, 64 и 9 участников: первыми отделяются 9 самых частых гостей, у которых в среднем по 27 визитов.

Дендрограмма — изображение этого дерева. Внизу располагаются наблюдения, каждое слияние — горизонтальная перекладина, соединяющая две ветви, а высота перекладины равна различию, при котором произошло слияние. Низкие перекладины соединяют похожие наблюдения, высокие — группы, у которых мало общего. Горизонтальная линия поперёк дерева — это разрез, и пересечённые ею ветви — кластеры: разрез чуть ниже верхней перекладины даёт два кластера, ниже следующей — три. О числе кластеров судят по промежуткам между высотами соседних перекладин: большой скачок от одной перекладины к следующей означает, что слитые на этом шаге группы были далеки друг от друга. На дереве кафе по методу Уорда три последних слияния происходят на высотах 12.5, 12.8 и 16.2. К последнему слиянию высота резко подскакивает, а перед ним растёт едва заметно, так что две группы разделены отчётливо, а три — с трудом.

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

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

Метод полной связи (дальнего соседа) считает расстоянием между кластерами расстояние между двумя их самыми далёкими наблюдениями, так что две группы сливаются, только когда каждое наблюдение одной близко к каждому наблюдению другой. Кластеры получаются компактными и примерно одного диаметра, а одно далёкое наблюдение способно надолго задержать слияние, потому что именно оно задаёт самую дальнюю точку своего кластера. На переменных кафе при разрезе на три метод даёт 79, 111 и 2 участника. Эти двое — пара нетипичных участников, не примкнувших ни к одной группе.

Метод средней связи (UPGMA, невзвешенный метод попарного среднего) берёт среднее всех расстояний между наблюдениями двух кластеров. Это компромисс между ближайшей и самой далёкой парой: кластеры получаются умеренного размера и сбалансированные, а высоты дерева точнее, чем у других методов, воспроизводят исходные расстояния. Метод Мак-Квитти (WPGMA, взвешенный вариант) усредняет иначе: расстояние от только что слитого кластера до любого другого равно простому среднему расстояний от двух его частей, независимо от их размеров. Поэтому маленький кластер весит столько же, сколько большой, к которому он присоединился.

Метод Уорда на каждом шаге сливает ту пару кластеров, при объединении которой общая внутрикластерная сумма квадратов растёт меньше всего. Это та же величина, которую минимизирует метод k-средних, только здесь её уменьшают шаг за шагом, не пересматривая прежних слияний. Метод предпочитает компактные кластеры близкого размера и обычно служит выбором по умолчанию для иерархической кластеризации числовых данных. Его критерий — сумма квадратов евклидовых расстояний, так что метод предполагает именно это расстояние и с любым другим теряет обоснование. Вариант Уорда (D2) в модуле принимает на вход сами расстояния, а не их квадраты, и высоты его дерева измеряются в единицах расстояния.

Центроидный и медианный методы измеряют расстояние между кластерами как расстояние между их центрами. В центроидном методе центр — это центроид, среднее наблюдений кластера. В медианном методе центр нового кластера — середина между центрами двух слившихся кластеров, так что обе части входят в этот центр с равными весами независимо от размера. У обоих методов есть особенность, которой нет у остальных: центр нового кластера может оказаться к третьему кластеру ближе, чем была любая из его частей. Тогда следующее слияние происходит на меньшей высоте, чем предыдущее. Это называется инверсией, и на дендрограмме она выглядит как перекладина ниже тех двух, которые она соединяет. На трёх переменных кафе инверсиями оказываются 9 из 191 слияния центроидного метода, а разрез на три даёт 187, 3 и 2 участника. Инверсия — не ошибка, а свойство данных при таком методе, но читать и резать такое дерево трудно.

Выбор числа кластеров #

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

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

где $u_i$ — расстояния от случайных точек, а $w_i$ — от реальных наблюдений. Если данные рассеяны равномерно, расстояния обоих видов похожи и H близка к 0.5. Если наблюдения собраны в сгустки, они лежат близко друг к другу, случайные точки попадают в пустоты между сгустками, и H растёт к 1. Значения ниже 0.25 означают, что наблюдения расположены регулярнее, чем при случайном разбросе, как узлы сетки. Начиная с 0.75 данные считают кластеризованными. На трёх стандартизованных переменных кафе с 19 пробными точками (по одной на десять участников) H = 0.81. Участники распределены далеко не равномерно, и не в последнюю очередь потому, что распределение визитов сильно скошено и несколько самых частых гостей стоят особняком.

Критерий Дуды — Харта отвечает на более узкий вопрос: лучше ли описывают данные два кластера, чем один. Данные делятся на две части, и внутрикластерная сумма квадратов этого разбиения, Je(2), сравнивается с суммой квадратов отклонений от общего среднего, Je(1). Отношение всегда меньше 1, ведь разбиение может только уменьшить разброс. Критерий проверяет, меньше ли это отношение, чем при разбиении бесструктурных нормально распределённых данных. Значимое p означает, что два кластера лучше одного. На переменных кафе лучшее разбиение на два кластера оставляет 410.5 из 573 единиц вариации, отношение равно 0.716 при p = 0.078. Этого недостаточно, чтобы на уровне 0.05 отвергнуть гипотезу об одном кластере, хотя статистика Хопкинса показала, что точки распределены далеко не равномерно. Противоречия здесь нет: по статистике Хопкинса видно, что облако комковатое, а по критерию Дуды — Харта — что надвое оно не делится.

Внутрикластерный разброс обычно измеряют внутрикластерной суммой квадратов W: это квадраты расстояний от каждого наблюдения до среднего его кластера, сложенные по всем кластерам (это та самая величина, которую минимизирует метод k-средних). Объяснённая дисперсия — доля общей вариации, которая приходится на различия между кластерами: 1 − W ⁄ T, где T — общая сумма квадратов. Обе меры улучшаются с каждым новым кластером (если кластеров столько же, сколько наблюдений, W = 0), поэтому выбирать k по их лучшему значению нельзя. На переменных кафе W падает с 410.5 при k = 2 до 323.7 при k = 3 и до 128.5 при k = 10, а объяснённая дисперсия растёт с 28% до 44% и затем до 78%.

Метод локтя определяет k по форме этой убывающей кривой. На графике зависимости W от k кривая круто падает, пока каждый новый кластер отделяет настоящую группу, и выполаживается, когда новые кластеры лишь дробят уже найденные группы. Точка перелома между крутым и пологим участками, локоть, и есть кандидат. Модуль отмечает её как точку, наиболее удалённую от прямой через первую и последнюю точки кривой, и ничего не отмечает, если кривая почти прямая и изгиба у неё нет. У кривой кафе самый сильный изгиб приходится на k = 5. Это наглядный ориентир, а не статистический критерий: многие кривые изгибаются плавно, и локоть смещается вместе с проверяемым диапазоном.

Правило Хартигана выражает сравнение соседних k числом: для каждого k оно сопоставляет W при k с W при k + 1,

По эмпирическому правилу Хартигана значение больше 10 означает, что (k + 1)-й кластер ещё стоит добавить, а остановиться следует на первом k, при котором значение опускается до 10 или ниже. На данных кафе оно равно 50.7 при k = 2 и всё ещё 16.2 при k = 9, то есть превышает 10 при всех проверенных k. На этих переменных правило так и не срабатывает: внутрикластерная сумма квадратов убывает равномерно и не выходит на плато, которое указало бы естественное число кластеров.

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

Значение s лежит между −1 и +1. Около +1 наблюдение гораздо ближе к своему кластеру, чем к любому другому, а около 0 — на границе двух кластеров. Отрицательное значение означает, что наблюдение ближе к соседнему кластеру, чем к своему, и, скорее всего, отнесено не туда. Средняя ширина силуэта по всем наблюдениям оценивает разбиение целиком. По шкале Кауфмана и Руссеу структура сильная от 0.70, достаточная от 0.50, слабая от 0.25, а ниже существенной структуры нет. На переменных кафе средний силуэт максимален при k = 3 (0.303) и от 2 до 10 кластеров держится между 0.275 и 0.303. Все k попадают в полосу слабой структуры: три сегмента отражают реальные тенденции в данных, но чётко разделёнными группами не являются.

Индекс Калинского — Харабаша — отношение межкластерной вариации к внутрикластерной, причём каждая поделена на свои степени свободы,

где B — межкластерная, а W — внутрикластерная сумма квадратов. Чем больше индекс, тем лучше: он поощряет кластеры, одновременно плотные и далёкие друг от друга, а степени свободы не дают ему расти просто от увеличения k. Индекс предполагает компактные, примерно сферические кластеры. На данных кафе он лежит между 69.9 и 75.7 при всех k от 2 до 10 и максимален при k = 6. Профиль почти плоский, и явного предпочтения ни одному числу кластеров он не отдаёт.

Индекс Дэвиса — Болдина оценивает каждый кластер по его худшему соседу. Для каждой пары кластеров их разбросы (у каждого это среднее расстояние наблюдений до центра) складываются и делятся на расстояние между центрами. Для каждого кластера берётся наибольшее из этих отношений, и полученные значения усредняются по кластерам. Чем меньше индекс, тем лучше. Ноль соответствовал бы кластерам вовсе без разброса, а значение больше 1 означает, что расстояние от типичного кластера до ближайшего соседа меньше их суммарного разброса. На данных кафе индекс снижается с 1.37 при k = 2 до минимума 0.975 при k = 6.

Индекс Данна — наименьшее различие между наблюдениями из разных кластеров, делённое на наибольшее различие между наблюдениями одного кластера. Чем больше, тем лучше. Значение больше 1 означало бы, что любой кластер уже промежутка до соседнего. И числитель, и знаменатель определяются единственной крайней парой, поэтому одно выделяющееся наблюдение может сильно сдвинуть индекс: он строгий, но неустойчивый. На данных кафе индекс нигде не превышает 0.09 (кластеры соприкасаются, что видно и по силуэту), а лучшее значение, 0.085, снова приходится на k = 6.

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

так что большой разрыв означает, что настоящие кластеры гораздо плотнее случайных. Затем по правилу Тибширани, Уолтера и Хасти выбирается наименьшее k, чей разрыв не меньше разрыва при k + 1 за вычетом стандартной ошибки последнего, то есть наименьшее k, которое добавление кластеров явно не улучшает. Если это k = 1, данные кластеризованы не лучше эталона. На данных кафе разрыв держится около 1.0 при всех k от 2 до 10 и нигде заметно не растёт, так что правило возвращает k = 1. По сравнению с эталоном того же разброса в трёх переменных кафе нет кластерной структуры, которую статистика разрыва могла бы уловить.

Когда индексы расходятся, а на реальных данных так бывает почти всегда, причина в том, что каждый измеряет своё. Силуэт оценивает, как вписываются в кластеры отдельные наблюдения. Индексы Калинского — Харабаша и Дэвиса — Болдина измеряют компактность и разделённость округлых кластеров, индекс Данна определяется одной худшей парой кластеров, а статистика разрыва сравнивает данные с бесструктурным эталоном. У каждого есть и свой уклон: статистика разрыва тяготеет к малому числу кластеров, Калинский — Харабаш и Дэвис — Болдин предполагают сферические кластеры, индекс Данна чувствителен к выбросам. На трёх переменных кафе силуэт указывает на 3 кластера, локоть на 5, индексы Калинского — Харабаша, Дэвиса — Болдина и Данна на 6, статистика разрыва на 1. Правило Хартигана так и не срабатывает, а критерий Дуды — Харта не отвергает гипотезу об одном кластере. Этот разнобой и есть результат: участники различаются плавно, а не делятся на резко обособленные типы. Любое k из этого диапазона — лишь способ их описать, и выбирать его стоит по тому, какое решение лучше истолковывается и воспроизводится на новой выборке, а не по тому, какой индекс «победил».

Бикластеризация #

Бикластер — блок таблицы данных, то есть часть наблюдений на части переменных, внутри которого значения согласованы. Остальная таблица в описание не входит. Кластер — набор строк, похожих друг на друга по всем столбцам, а бикластер — набор строк, похожих лишь по некоторым столбцам и как угодно различающихся по остальным. Бикластеры могут перекрываться: наблюдение или переменная может входить в несколько из них или ни в один. Их число либо задаётся заранее, либо определяется алгоритмом. На шести пунктах анкеты алгоритм BiMax с тремя бикластерами при настройках по умолчанию выделяет 36 участников, оценивших пункты цена и приветливо выше медианы, ещё 36, оценивших выше медианы вкус и цена, и 11, поставивших выше медианы одновременно быстро и медленно. Эти одиннадцать согласились и с тем, что заказ принесли быстро, и с тем, что обслуживали медленно. Кластеризация по всем шести пунктам такое противоречие не выделила бы никогда.

Модель Plaid представляет таблицу как фон, на который наложены слои. Фон подгоняется первым по всей таблице: общее среднее плюс сдвиг для каждого наблюдения и каждой переменной. Слой — это блок наблюдений и переменных, внутри которого значения держатся на собственном уровне (константа блока плюс сдвиги для его наблюдений и переменных), и этот уровень добавляется к тому, что лежит под слоем. Слои снимаются по одному, и каждый подгоняется к тому, что осталось необъяснённым после предыдущих. Кандидат в слои сохраняется, только если объясняет больше, чем случайно размещённый блок того же размера. Когда таких кандидатов не остаётся, поиск прекращается. Так модель сама определяет число бикластеров. На шести пунктах анкеты она не находит ни одного слоя, стандартизованы пункты или нет. Структура этих пунктов — два широких фактора, затрагивающих всех участников, а не блоки участников, выделяющихся на нескольких пунктах, поэтому над фоном ничего не поднимается.

Бинаризация превращает каждое значение в 1 или 0: каждая переменная режется по выбранному квантилю её собственных значений, и выше порога ставится 1, на пороге и ниже — 0. Бинарная бикластеризация затем ищет блоки из одних единиц, то есть наблюдения с высокими значениями по набору переменных. Порог у каждой переменной свой, а не общий для всей таблицы, и именно это позволяет искать совместно переменные в разных шкалах. BiMax находит блоки, которые нельзя расширить ни строкой, ни столбцом, не захватив нуля, — максимальные по включению. Поэтому его бикластеры настолько велики, насколько позволяют единицы, а их число равно запрошенному. На пунктах анкеты, разрезанных по медианам, он находит три блока, описанных выше.

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

где $a_{iJ}$ и $a_{Ij}$ — средние по строке и по столбцу внутри блока, а $a_{IJ}$ — общее среднее блока. Если каждое наблюдение блока отличается от любого другого на постоянную величину, H = 0, какими бы ни были сами значения. У таблицы в целом H больше, и бикластер — это блок, остаток которого мал по сравнению с остатком всей таблицы. На шести стандартизованных пунктах анкеты у всей таблицы H = 0.74, а у первого бикластера Ченга — Чёрча (42 участника, все пункты, кроме медленно) H = 0.14, впятеро меньше. Порог, который блок не должен превышать, задаёт аналитик. Модуль выражает его как долю остатка самой таблицы, чтобы одна и та же настройка значила одно и то же на любых данных.

Корреляция внутри бикластера — другой способ оценить согласованность блока: средняя корреляция между всеми парами строк блока по его столбцам. Здесь важно лишь, растут и падают ли строки вместе, а не на сколько. Поэтому строки, повторяющие один рисунок с разной амплитудой (ответы одного участника колеблются вдвое шире, чем другого), получают высокую оценку по корреляции и низкую по среднему квадрату остатков: он предполагает между строками постоянный сдвиг. Чем выше, тем лучше, максимум 1. Строка с одним и тем же значением на всех столбцах блока ни с чем не коррелирует и в расчёт не входит. На шести пунктах анкеты у двух бикластеров BiMax при k = 2 средняя r = 0.49, а средний квадрат остатков 0.040. Блок, хороший по обеим мерам, согласован в самом строгом смысле, а большое расхождение между ними означает, что строки совпадают по форме, но не по масштабу.

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

Шахматная структура — картина, которую ищет спектральный алгоритм. Наблюдения делятся на несколько групп, переменные тоже, и таблица после перестановки строк и столбцов превращается в сетку блоков, каждый на своём уровне, — как шахматная доска с клетками разных оттенков. Обе группировки алгоритм получает из старших сингулярных векторов нормализованной таблицы, сочетает каждую группу наблюдений с каждой группой переменных и оставляет те пары, у которых блок достаточно велик, а значения достаточно близки друг к другу. Алгоритм рассчитан на таблицу, целиком состоящую из блоков: такой была бы таблица ответов респондентов из разных популяций на разные группы вопросов. Если же в таблице один-два блока на фоне сильного шума, лучше подходит модель Plaid.

Проверка решения и его визуализация #

Устойчивость кластеров — найдётся ли кластер, выделенный в этой выборке, снова в другой выборке из той же генеральной совокупности. Индексы из раздела о выборе числа кластеров оценивают разбиение на тех же наблюдениях, по которым оно построено, и потому не отличат настоящую группу от удачного разреза именно этих строк. Устойчивость проверяют на бутстрэп-выборках. Строки извлекаются заново с возвращением (это и есть бутстрэп-выборка того же объёма, где одни наблюдения повторяются, а других нет вовсе), она кластеризуется с теми же настройками, каждое наблюдение относится к ближайшему из новых кластеров, и для каждого исходного кластера находится самый похожий новый. Сходство измеряют коэффициентом Жаккара — числом общих элементов двух множеств, делённым на число элементов в их объединении. Кластер из 13 участников, вернувшийся как 12 своих плюс 3 чужих, получает 12 ⁄ 16 = 0.75. После ста повторов у каждого кластера есть средний коэффициент Жаккара и два счётчика: сколько раз кластер восстановился (0.75 и выше) и сколько раз распался (0.5 и ниже). По шкале Хеннига средний коэффициент от 0.85 означает очень высокую устойчивость, от 0.75 — устойчивость, от 0.60 — закономерность с сомнительным составом, а ниже кластеру доверять нельзя. При зерне бутстрэпа, равном 42, три сегмента k-средних получают 0.61 (13 завсегдатаев), 0.79 (96 равнодушных) и 0.78 (83 довольных). Два крупных сегмента возвращаются примерно в семи бутстрэп-выборках из десяти, а завсегдатаи распадаются в 38 из 100. Это горстка далёких наблюдений, и их группа зависит от того, какие из них попадут в бутстрэп-выборку. Кластер может быть хорошо выделен в этой выборке, с хорошим силуэтом, и всё же не повториться. Из всех диагностик только устойчивость отвечает на вопрос о следующей выборке.

Консенсусное разбиение — разбиение, построенное не по одной кластеризации данных, а по многим. Кластеризация каждой бутстрэп-выборки для любой пары наблюдений показывает, попали ли они в один кластер. Усреднение по бутстрэп-выборкам даёт коассоциацию пары: 1, если наблюдения каждый раз оказывались вместе, и 0, если ни разу. Затем кластеризуется сама таблица коассоциаций, и наблюдения, которые устойчиво держатся вместе, образуют консенсусный кластер. Сопоставив консенсусное разбиение с приведённым решением, можно увидеть, какие границы бутстрэп-выборки подтвердили. Для сопоставления есть две сводки: согласованность двух разбиений по скорректированному индексу Рэнда и доля неоднозначной кластеризации (PAC). PAC — доля пар с коассоциацией между 0.1 и 0.9, то есть пар, которые бутстрэп-выборки не держали надёжно ни вместе, ни порознь. Для группировки, которую данные задают однозначно, эта доля близка к 0. Для трёх сегментов k-средних при зерне 42 консенсусное разбиение оставляет всех 13 завсегдатаев и всех 96 равнодушных там же, где их поместило приведённое решение, и переносит к равнодушным 9 из 83 довольных. Скорректированный индекс Рэнда равен 0.83, согласие хорошее, и расходятся разбиения только на границе двух крупных сегментов. Однако PAC равен 0.52: половина всех пар в одних бутстрэп-выборках разделялась, а в других объединялась. Низкая согласованность или высокий PAC не означают, что прав консенсус, а приведённое разбиение ошибочно: оба — разрезы одних и тех же данных. Это знак, что данные не задают группировку однозначно, и повод сообщать решение с оговорками, а не заменять его другим.

Скорректированный индекс Рэнда показывает, насколько согласуются два разбиения одних и тех же наблюдений. Он перебирает все пары наблюдений и проверяет, одинаково ли с ними обходятся оба разбиения: либо оба помещают пару в один кластер, либо оба разводят её по разным. Долю таких пар затем поправляют на согласие, которого достигли бы два случайных разбиения с теми же размерами кластеров. Индекс равен 1 для совпадающих разбиений, как бы ни были пронумерованы кластеры, близок к 0, когда согласие не лучше случайного, и может быть отрицательным. По Стейнли 0.90 и выше — отличное согласие, от 0.80 — хорошее, от 0.65 — умеренное.

Кофенетическая корреляция показывает, насколько точно дерево воспроизводит различия, по которым оно построено. Любые два наблюдения соединяются на дендрограмме на некоторой высоте — высоте первого слияния, после которого они оказываются в одной ветви. Эта высота и есть различие между ними с точки зрения дерева, кофенетическое расстояние, а кофенетическая корреляция — обычная корреляция между кофенетическими и исходными различиями по всем парам наблюдений. При 1 высоты дерева в точности следуют исходным различиям. Дерево, хорошо представляющее данные, обычно даёт не меньше 0.75. Корреляция оценивает дерево целиком, а не его разрез, поэтому от k не зависит. На трёх стандартизованных переменных кафе дерево Уорда получает 0.50, а дерево средней связи — 0.79: метод средней связи для того и создан, чтобы точно передавать высоты, и с этим справляется. Однако дерево средней связи при разрезе на три даёт 187, 3 и 2 участника, а дерево Уорда — три осмысленных сегмента. Верное дерево и полезный разрез — разные достоинства, и кофенетическая корреляция оценивает только первое.

Многомерное шкалирование (МШ) располагает объекты на плоскости так, чтобы расстояния между точками воспроизводили различия между объектами настолько точно, насколько позволяют два измерения. По сути, это карта, восстановленная по таблице расстояний: так по таблице расстояний между городами из дорожного атласа можно было бы заново нарисовать карту. МШ относится к семейству методов ординации, и здесь оно нужно, чтобы показать, разделены ли кластеры в самих данных или только в таблице разбиения. Если точки, окрашенные по кластерам, образуют отдельные облака, кластеры разделяет сама мера различия. Если же облака перетекают одно в другое, алгоритм провёл границы там, где данные меняются непрерывно. Классическое (метрическое) шкалирование воспроизводит сами различия, а соответствие данным выражает долей их структуры, которую передают два измерения. На евклидовых расстояниях классическое шкалирование даёт ту же картину, что и первые две главные компоненты. Неметрическое шкалирование по Краскалу сохраняет только порядок различий: самая близкая пара должна быть самой близкой и на графике, следующая — следующей. Это подходит для меры различия, в которой ранги значат больше, чем величины. Несоответствие такого решения данным выражается стрессом: 0.025 и ниже — отлично, 0.05 — хорошо, 0.1 — удовлетворительно. На трёх стандартизованных переменных кафе два измерения классического шкалирования передают 75% структуры, а неметрическое шкалирование даёт стресс 0.15, хуже удовлетворительного. Четверть различий между участниками на график не попала, поэтому две точки, стоящие рядом, могут принадлежать участникам, которые различаются по оставшемуся за кадром измерению. Картинка всегда выглядит убедительно, а насколько ей верить, показывает соответствие, и смотреть на него нужно раньше, чем на картинку.

Биплот изображает наблюдения и переменные на одном графике: наблюдения — точками на плоскости первых двух главных компонент, как на графике классического МШ, а каждую переменную — стрелкой из центра в сторону её роста. Стрелка, направленная в ту часть графика, где лежит кластер, соответствует переменной, высокой в этом кластере. Так по биплоту видно, какие переменные создают разделение, существование которого график МШ лишь показывает. Угол между стрелками передаёт корреляцию: у переменных, меняющихся вместе, он острый, у несвязанных прямой, а стрелки переменных, тянущих в разные стороны, смотрят почти противоположно. Длина стрелки показывает, насколько хорошо переменную представляют две компоненты, поэтому направление короткой стрелки — самое ненадёжное, что есть на графике. На трёх стандартизованных переменных кафе первая компонента передаёт 46% вариации, вторая — 29%. Все три стрелки наклонены в одну сторону вдоль первой компоненты, поскольку оценка, чек и визиты слабо, но положительно коррелируют между собой (r от 0.13 до 0.24). Вторая компонента разводит оценку и визиты в противоположные стороны, а чек с самой короткой стрелкой оказывается между ними. Завсегдатаи вытянулись вдоль стрелки визитов, довольные тяготеют к стрелкам оценки и чека, равнодушные лежат по другую сторону от всех трёх, и профили трёх сегментов читаются по одной картинке. Чего две компоненты не передают (здесь это четверть вариации), того нет и на картинке, включая стрелки. Стрелки оценки и визитов на экране расходятся примерно на 100°, хотя сами переменные коррелируют на уровне 0.13: каждая изображена лишь отчасти.

Что можно утверждать по кластерному решению #

Кластерное решение — описание одной выборки при конкретных установках (этих переменных, этой мере различия, этом алгоритме и этом k), а не доказательство того, что группы существуют. Кластеры возвращает любой алгоритм: метод k-средних, которому велено найти три кластера, найдёт их и в равномерно рассеянных точках, а дерево можно разрезать на любой высоте. На трёх переменных кафе одно и то же k = 3 дало 13, 96 и 83 участника у метода k-средних; 70, 48 и 74 у k-медоидов; 119, 64 и 9 у метода Уорда; 190, 1 и 1 у метода одиночной связи. Каждое из четырёх разбиений верно отвечает на свой вопрос, просто вопросы поставлены по-разному. Утверждать решение может лишь то, что подтверждает диагностика. На втором шаге модуль сравнивает возможные значения k по индексам компактности и разделённости кластеров, а на третьем может проверить, повторяется ли каждый кластер на новой выборке. Кластер, распадающийся на бутстрэп-выборках, был особенностью этих 192 участников, а не генеральной совокупности, из которой они взяты. Вместе с результатом стоит указывать установки, кластеры — называть по профилям, а не по заранее сочинённой истории, а типами их можно считать только после того, как они повторятся на других данных.

Где это встречается в DataSuite #

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

Маркетолог: покупатели → наблюдения, показатели покупок → переменные кластеризации, сегменты → кластеры; эколог: участки отбора проб → наблюдения, численность видов → переменные кластеризации (расстояние Канберра); психометрист: пункты опросника → переменные, кластеризуемые в режиме переменных по 1 − |r|, группы → подшкалы.