Кластеризация: структура без ответов

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

Мир как сто сорок две точки

Возьмём портрет мира 2007 года из набора Gapminder — открытой сводки шведского фонда Ханса Рослинга, собранной из статистики ООН и Всемирного банка: 142 страны, для каждой — ВВП на душу населения в долларах и ожидаемая продолжительность жизни в годах. Копия лежит в репозитории курса: scripts/data/gapminder.csv. Ни меток, ни «правильных ответов» в таблице нет; есть только положение каждой страны в пространстве двух чисел.

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

Задача не экзотическая, а вездесущая. Магазин делит покупателей на сегменты для рассылок; врач-исследователь ищет подтипы болезни среди пациентов с похожими анализами; биолог группирует гены по профилям активности; редактор — новости по темам, которых заранее никто не перечислял. Всюду одна механика: объекты, признаки, расстояние — и надежда, что геометрия проявит структуру, для которой пока нет названий. Страны мы выбрали за то, что каждый пункт этой механики на них виден невооружённым глазом и каждую находку можно проверить здравым смыслом.

Расстояние — это решение, а не данность

Кластеризация начинается со слова «похожие», а похожесть измеряется расстоянием. Для пары стран $u$ и $v$ с координатами «ВВП, жизнь» естественно взять евклидово расстояние из урока о режимах:

$$\rho(u,v) =\sqrt{(u_{\text{ВВП}}-v_{\text{ВВП}})^{2} +(u_{\text{жизнь}}-v_{\text{жизнь}})^{2}} .$$

Формула выглядит нейтрально, но посмотрите на единицы. ВВП измеряется тысячами долларов: разброс по странам — от 278 до 49 357. Жизнь — годами: от 39,6 до 82,6. Внутри одной суммы квадратов доллары и годы встретились без перевода, и слагаемое ВВП в тысячи раз больше слагаемого жизни. Расстояние почти целиком определяется доходом; продолжительность жизни превратилась в шёпот, которого метрика не слышит.

Запустим k-средние из урока 06 на этих сырых числах с $K=3$ и посмотрим на результат. Кластеры получаются такие: 103 страны «бедных», 20 «богатых» и 19 «очень богатых». Разрез прошёл строго по доходу: у «бедного» кластера продолжительность жизни гуляет от 39,6 до 78,8 лет — Япония бедного мира и Свазиленд оказались бы соседями, если бы у них совпал ВВП. Алгоритм не сломан; он честно оптимизировал то, что мы ему дали, а дали мы ему метрику, в которой год жизни стоит один доллар.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Лекарство называется стандартизацией: перевести каждый признак в безразмерные «сигмы», вычтя среднее и поделив на стандартное отклонение из урока о статистике:

$$\tilde x =\frac{x-\bar x}{s_x} ,$$

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

$$\tilde x=\ln x \quad\Longrightarrow\quad \tilde u-\tilde v=\ln\frac{u}{v} ,$$

тогда расстояние сравнивает отношения, а не разности: путь от 1000 к 2000 долларов равен пути от 20 000 к 40 000. Для величин, растущих в разы — доходов, населений, цен, — логарифм часто честнее сигм; мы уже видели его в этой роли в метрике RMSLE. Каждая нормировка — маленькая теория о том, что значит «похожие страны», и запускать кластеризацию раньше, чем эта теория произнесена вслух, значит доверить её случайности единиц.

Как работают k-средние

Пора раскрыть сам алгоритм, которым мы пользуемся с урока 06. Цель k-средних — расставить $K$ центров так, чтобы суммарный квадрат расстояний от точек до ближайших центров был минимален:

$$J =\sum_{i=1}^{n} \min_{1\le k\le K} \bigl\lVert x_i-\mu_k\bigr\rVert^{2} \;\longrightarrow\;\min_{\mu_1,\ldots,\mu_K} .$$

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

$$c(i)=\arg\min_{k}\bigl\lVert x_i-\mu_k\bigr\rVert .$$

Пересчёт: каждый центр переезжает в среднее своих точек,

$$\mu_k=\frac{1}{|C_k|}\sum_{i\in C_k} x_i .$$

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

А почему вообще нужен хитрый алгоритм — нельзя ли перебрать все разбиения и выбрать лучшее? Оценим объём работы. Каждая из 142 стран независимо выбирает один из трёх кластеров:

$$\frac{3^{142}}{3!} \approx 10^{67}$$

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

Сходится — но куда? В ближайшую «яму» функции $J$, которая зависит от случайной расстановки стартовых центров. Разные запуски могут дать разные разбиения, и это не дефект реализации, а свойство задачи. Отсюда обязательный ритуал: запускать k-средние несколько раз с разных стартов и брать лучший по $J$ результат — а заодно смотреть, насколько запуски согласны между собой. Несогласие запусков — важнейший диагностический сигнал, и через два раздела мы сделаем его измерительным прибором.

Умный старт: k-средние++

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

$$\Pr(x)\;\propto\;D(x)^{2}, \qquad D(x)=\min_{\mu\ \text{выбр.}}\lVert x-\mu\rVert .$$

Случайность остаётся — иначе один выброс всегда становился бы центром, — но взвешенная: далёкие сгустки почти наверняка получат своего представителя. У приёма есть и теоретическая гарантия: ожидаемое $J$ старта не хуже оптимума более чем в $O(\ln K)$ раз, и на практике k-средние++ давно стандарт по умолчанию. Заметьте архитектуру решения: неустранимую случайность не прячут, а направляют — тот же ход, каким $\varepsilon$-жадность из урока о режимах направляла разведку.

Среднее, медиана и медоид: кто стоит в центре

Почему в пересчёте Ллойда центр переезжает именно в среднее? Потому что целевая функция $J$ сложена из квадратов, а теорема прошлого урока говорит: сумму квадратов минимизирует среднее. Замените в $J$ квадраты на модули — и оптимальным центром станет покоординатная медиана, а алгоритм превратится в k-медианы, устойчивые к выбросам ровно так же, как медиана устойчива против среднего. Один богатейший Катар оттягивает центр своего кластера по оси дохода заметно сильнее, чем сместил бы медиану.

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

$$m_k =\arg\min_{x\in C_k} \sum_{y\in C_k} \rho(x,y) ,$$

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

Сколько кластеров: локоть и силуэт

В уроке 06 мы выбирали $K$ по локтю кривой $J(K)$. Добавим второй, более тонкий прибор. Для точки $i$ сравним её среднюю близость к своим и к лучшим из чужих:

$$s_i=\frac{b_i-a_i}{\max(a_i,\,b_i)} ,$$

где $a_i$ — среднее расстояние до точек своего кластера, а $b_i$ — наименьшее среди средних расстояний до каждого из чужих. Величина $s_i$ живёт в $[-1,1]$: около единицы — точка глубоко среди своих; около нуля — сидит на границе двух групп; отрицательная — прописана не туда. Средний по всем точкам силуэт оценивает разбиение целиком.

Почему вообще нельзя выбирать $K$ по самой функции $J$? Потому что $J$ убывает при любом росте $K$ автоматически: добавьте центр — и каждая точка либо останется при своём, либо найдёт более близкий; хуже не станет никому. В пределе $K=n$ каждый объект получает личный центр и $J=0$ — идеальный счёт и полная бессмыслица. Критерий, который монотонно улучшается от усложнения модели, не может это усложнение ограничивать; нам ещё не раз встретится этот принцип, и в уроке о переобучении он станет главным сюжетом. Локоть — попытка выжать из $J$ хоть что-то, глядя на скорость убывания; силуэт — критерий другой породы, который умеет становиться хуже.

Посчитаем силуэт стран для $K$ от 2 до 6 на стандартизированных осях: $0{,}536$, $0{,}594$, $0{,}524$, $0{,}526$, $0{,}517$. Максимум — при $K=3$: мир 2007 года охотнее всего делится на три группы. Заметьте, насколько это честнее локтя: силуэт не просто дешевеет с ростом $K$, он умеет и падать, когда лишний центр разрезает плотное облако по живому.

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

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Устойчивость: главный тест на настоящесть

Локоть и силуэт молчат о самом неприятном сценарии: что если найденные группы — артефакт конкретного запуска или конкретной выборки? Проверка проста и безжалостна. Запустим k-средние пять раз с разными случайными стартами и для каждой пары стран спросим: оказались ли они вместе в одном запуске и врозь в другом? Доля согласных пар измеряет устойчивость разбиения.

Формально: для разбиений $A$ и $B$ переберём все пары точек и посчитаем долю пар с совпавшим вердиктом,

$$\mathrm{agree}(A,B) =\frac{\#\{(i,j):\, [A(i)=A(j)]=[B(i)=B(j)]\}} {\binom{n}{2}} ,$$

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

Числа для наших стран красноречивы. При $K=3$ все пять запусков совпадают до последней страны: согласие 100%. При $K=4$ и $K=5$ — 92–93%: границы дрожат. А при $K=2$ согласие проваливается до 74%, и причина поучительна: двойке есть два почти равноценных способа разрезать мир — по доходу или по здоровью, и разные старты выбирают разные разрезы. Неустойчивость указала на содержательный факт: «двухполюсный мир» — не свойство данных, а произвол разреза. Рослинг говорил то же самое словами.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Второй вариант той же проверки — устойчивость к данным: убрать случайную десятую часть стран и посмотреть, сохранились ли группы. Настоящая структура переживает и смену старта, и потерю десятой части точек; артефакт рассыпается от любого чиха. Мы уже пользовались этой логикой, когда проверяли перенос кластеров дней с 2011 на 2012 год в уроке 06.

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

Лаборатория: мир под вашим ножом

Порядок опытов. Начните с сырых единиц и $K=3$: убедитесь глазами, что границы вертикальны и ось жизни мертва. Переключите нормировку на сигмы и увидьте, как мир перестраивается. Затем крутите $K$ при включённом силуэте: тройка держит максимум, а на $K=2$ нажмите «перезапустить» несколько раз — разрез будет прыгать между «богатые против бедных» и «здоровые против больных», это та самая неустойчивость двойки. В конце включите лог-ВВП и проверьте, гнётся ли тройка под другой честной нормировкой: устойчивость к разумным вариантам метрики — самый строгий из наших тестов.

Имя кластеру даёт человек

Алгоритм вернул три множества точек и ни слова об их смысле. Посмотрим, кто внутри. Первый кластер: Западная Европа, Северная Америка, Япония, Австралия — высокий доход, долгая жизнь; назовём его «богатый долгоживущий мир». Второй: почти вся Латинская Америка, Китай, Турция, Ближний Восток — средние доходы, жизнь 65–78. Третий: почти вся Африка южнее Сахары и беднейшие страны Азии — низкий доход, короткая жизнь. Имена дали мы, глядя на состав; у алгоритма их не было.

Насколько наши геометрические группы совпадают с привычной географией? В таблице есть колонка continent, которую алгоритм не видел, — чем не внешняя проверка. Совпадение заметное, но неполное: «богатый долгоживущий мир» собрал Европу с Японией и Австралией поперёк континентов, Африка расщепилась между «бедным» и «средним» кластерами. Кластеры по доходу и жизни — не континенты, и это правильный итог: геометрия отвечает на вопрос про деньги и годы, а не про положение на глобусе, и навязывать ей чужую рубрикацию — значит проверять ответ по чужому вопросу.

Самое ценное в разбиении — не аккуратные группы, а страны, которые сопротивляются именам. Ботсвана и Экваториальная Гвинея по доходу — крепкие середняки (12–13 тысяч долларов), а по жизни — 51 год, дно таблицы: сырьевые доходы не конвертировались в здоровье, по Ботсване ударила эпидемия ВИЧ. Куба и Коста-Рика — зеркальный случай: доход скромный, а живут по 78 лет, как богатый мир. Такие точки-диссиденты и есть главная добыча кластеризации: они показывают, где двумерная карта «доход-жизнь» рвётся, и заставляют искать третью переменную — устройство медицины, распределение доходов, историю эпидемий. Кластер — это не ответ; это хорошо сформулированный вопрос.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Кластеры из ничего

Осталась последняя и самая коварная проверка. Возьмём 142 точки, рассыпанные по квадрату равномерным случаем — по построению никаких групп, — и запустим на них весь наш конвейер: k-средние, $K=3$, силуэт. Алгоритм послушно вернёт три «кластера», а силуэт составит около 0,39. Повторим двадцать раз: шумовые силуэты лягут между 0,36 и 0,43. Ни один запуск не откажется работать, ни один не скажет «здесь ничего нет». Кластеризация всегда что-то находит — таково её устройство: минимизируя $J$, она обязана вернуть разбиение, есть в данных структура или нет.

Спасает сравнение с шумом, знакомое по духу из урока о статистике: наши страны дали силуэт 0,594 — далеко за пределами всего, что двадцать шумовых миров сумели изобразить. Значит, «три мира» — не подарок алгоритма, а свойство данных. Такой нулевой эксперимент занимает десять строк кода и обязан сопровождать любой отчёт о кластерах; без него фраза «мы нашли пять сегментов клиентов» означает ровно то же, что «мы попросили пять сегментов и нам их выдали».

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Иерархия вместо ножа

K-средние требуют выбрать $K$ до работы. Агломеративная кластеризация обходится без этого: она начинает со 142 кластеров-одиночек и на каждом шаге сливает два ближайших, пока не останется один. Слово «ближайших» для групп требует уточнения — расстоянием между кластерами $A$ и $B$ назначают, например, среднее попарное:

$$\rho(A,B) =\frac{1}{|A|\,|B|} \sum_{a\in A}\sum_{b\in B} \rho(a,b) ,$$

и варианты (минимум, максимум, среднее) дают разные характеры слияний. История слияний рисуется деревом-дендрограммой: листья — страны, высота развилки — расстояние, на котором группы согласились слиться. Дерево показывает структуру сразу на всех масштабах: горизонтальный разрез на любой высоте даёт разбиение, и выбор $K$ превращается из слепого параметра в осознанный разрез видимой картины.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Цена удобства — жадность: слияние, однажды сделанное, не пересматривается, и дерево может закрепить раннюю ошибку. На больших данных иерархия ещё и дорога: попарных расстояний квадратично много. Поэтому в практике оба инструмента живут рядом: дендрограмма — чтобы увидеть масштабы и выбрать $K$, k-средние — чтобы быстро и воспроизводимо разрезать миллионы точек.

За пределами двух колонок

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

$$\rho(u,v)=\sqrt{\sum_{j=1}^{d}(u_j-v_j)^{2}} ,$$

и k-средние, силуэт и устойчивость определены при любом числе координат $d$ — профили дней из урока 06 жили в $d=24$, и никто не жаловался. Меняются две вещи. Во-первых, нормировка становится ещё важнее: в двадцати колонках сырых единиц какофония масштабов гарантирована. Во-вторых, пропадает главная проверка — глаз: в двадцати измерениях не взглянешь на скаттер, и диагностика держится целиком на числах — силуэте, устойчивости, переносе. Как честно сплющить многомерное облако до двумерной картинки, расскажет урок о PCA; как кластеризуют то, у чего вообще нет координат — тексты, товары, гены, — покажет урок об эмбеддингах.

И одно предупреждение на вырост. K-средние ищут круглые сгустки: их устраивает мир, где кластер — это ком вокруг центра. Кольца, полосы, спирали и группы очень разных размеров они режут неправильно — не потому что плохи, а потому что их функция $J$ описывает другой мир. Проверка формы облака до выбора алгоритма — такая же обязанность, как проверка масштаба осей до выбора метрики.

Полвека спустя: кластеры двигаются

Кластеры — снимок, а мир — кино. Повторим стандартизированную кластеризацию на срезе 1957 года и сравним членство стран в трёх группах, упорядоченных по продолжительности жизни. Из 140 стран, присутствующих в обоих срезах, относительную группу сменили 66 — почти половина мира. Сорок поднялись: Южная Корея прошла весь путь из нижней группы в верхнюю — редчайший маршрут длиной в два кластера; Китай, Бразилия, Бангладеш перешли из нижней в среднюю. Двадцать шесть опустились, и среди них Аргентина, Чили и почти вся Восточная Европа — из верхней группы в среднюю.

Слово «опустились» требует немедленной оговорки, без которой сравнение лжёт. Нормировка выполнялась внутри каждого года отдельно, поэтому кластер измеряет положение относительно современников, а не абсолютный уровень: продолжительность жизни в Аргентине выросла с 64 до 75 лет — страна не падала, просто мир вокруг бежал быстрее. Это то же коварство относительных шкал, что у рейтингов и процентилей в школе: место в классе может падать при растущих знаниях. Абсолютную и относительную динамику всегда разводят явно; перепутать их — самый быстрый способ превратить честную таблицу в ложный заголовок.

Сборка: протокол честной кластеризации

Соберём урок в рабочий протокол. Сначала метрика: назвать единицы, выбрать и обосновать нормировку — этот шаг решает больше, чем алгоритм. Затем $K$: локоть и силуэт как советчики, задача как судья. Затем устойчивость: перезапуски и подвыборки; дрожащие границы — сообщение, а не помеха. Затем интерпретация: имена группам, отдельный список диссидентов, и запрет на причинные истории без внешних данных. И финальная проверка из урока 06: перенос — держится ли структура на новых данных, которых алгоритм не видел. Кластеризация без этого протокола выдаёт красивые группы всегда, даже на чистом шуме; с протоколом она становится тем, чем и должна быть, — прибором для поиска структуры, у которого есть показания и есть погрешность.

Задачи