§1. Нормировка, расстояния и классы

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

Пример 1. Вес и рост

Студенты группы записывают свой вес $x$ и рост $y$. По этим данным на плоскости строится диаграмма рассеяния — «облако» точек $(x_i, y_i)$, $i = 1, \dots, n$. Масштабы по осям задаются произвольно.

На одном масштабе девушки (класс $A$) довольно чётко отделяются от юношей ($B$). Но если сжать шкалу на оси веса вдвое, более естественным становится уже деление на высоких юношей ($D$) и всех остальных ($C$).

Мораль: при классификации нельзя бездумно считать расстоянием между объектами евклидово расстояние между точками $(x_i, y_i)$. Признаки имеют разные единицы измерения, и сначала нужна нормировка, переводящая их в безразмерные величины.

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

Типы нормировки

Пусть $Z_1, \dots, Z_n$ — значения одного признака.

N1. $Z_i' = (Z_i - Z_{\min})/(Z_{\max} - Z_{\min})$ — всё загоняем в отрезок $[0, 1]$.

N2. $Z_i' = (Z_i - \bar Z)/S$, где $\bar Z = \frac1n\sum Z_i$ — среднее арифметическое, $S^2 = \frac1n\sum(Z_i - \bar Z)^2$ — выборочная дисперсия.

N3. $Z_i' = (Z_i - MED)/MAD$, где $MED$ — выборочная медиана (§2 главы 7), а $MAD$ — (нормированная) медиана абсолютных отклонений от $MED$:

Здесь $\Phi^{-1}$ — функция, обратная к функции распределения закона $\mathcal N(0, 1)$. Сокращение MAD — от английского Median of Absolute Deviations.

По кирпичикам: откуда множитель. Для $\mathcal N(\mu, \sigma^2)$ величина $|Z - \mu|$ имеет медиану $\sigma\,\Phi^{-1}(3/4) \approx 0{,}6745\,\sigma$: ровно половина нормальной массы лежит в $\mu \pm 0{,}6745\,\sigma$. Поэтому множитель $1/\Phi^{-1}(3/4) \approx 1{,}483$ обеспечивает сходимость $MAD \to \sigma$ при $n \to \infty$ (см. П5).

N3 меньше подвержена влиянию выделяющихся значений: один бешеный выброс сдвигает и среднее, и $S$, и тем более размах $Z_{\max} - Z_{\min}$, но почти не трогает медианы.

Посмотри: в N1 выброс сжал девять обычных весов в отрезок $[0;\ 0{,}32]$. В N3 они занимают примерно $[-1;\ 1]$, как и положено нормированным данным, а выброс стоит особняком: $5{,}3$.

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

Помимо типа нормировки, решающее влияние на результат оказывает выбор меры близости между $m$-мерными точками $\boldsymbol x_i = (x_{i1}, \dots, x_{im})$ и $\boldsymbol x_j = (x_{j1}, \dots, x_{jm})$.

D1. Метрика города (её также называют city-block или манхэттенской): $d_{ij} = \sum_{l=1}^m|x_{il} - x_{jl}|$. С ней хорошо выделяются классы вида «облака», вытянутого вдоль оси некоторого признака. Если координаты принимают только значения 0 и 1, это расстояние равно числу несовпадающих координат, то есть длине пути по рёбрам единичного $m$-мерного куба из одной вершины в другую — метрика Хемминга.

D2. Евклидова метрика: $d_{ij} = \bigl(\sum_{l=1}^m(x_{il} - x_{jl})^2\bigr)^{1/2}$.

D3. Метрика Чебышёва: $d_{ij} = \max_{1 \le l \le m}|x_{il} - x_{jl}|$.

Все три — частные случаи (при $p = 1$, $2$ и $\infty$) расстояния Минковского

При любом $p \ge 1$ для него выполняется неравенство треугольника $d_{ij} \le d_{ik} + d_{kj}$. Почему метрика Чебышёва отвечает именно $p = \infty$ — вопрос 1.

Единичные «шары» $B_p^m$ при $p = 1, 2, \infty$ — это ромб, круг и квадрат. Отношение объёмов $\rho_m = V(B_1^m)/V(B_\infty^m) = 1/m!$ при увеличении размерности быстро уменьшается: $\rho_2 = 1/2$, $\rho_5 = 1/120$, $\rho_{10} = 1/3\,628\,800 \approx 3\cdot10^{-7}$.

По кирпичикам: $B_\infty^m$ — куб $[-1, 1]^m$ объёма $2^m$; $B_1^m$ — «кросс-политоп» из $2^m$ одинаковых симплексов $\{x_l \ge 0,\ \sum x_l \le 1\}$ объёма $1/m!$ каждый. Отсюда $\rho_m = 2^m/m! \,/\, 2^m = 1/m!$.

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

Иногда матрица расстояний (мер близости) $d_{ij}$ задаётся непосредственно: например, как таблица экспертных оценок сходства объектов или матрица межотраслевых поставок. Тогда проблема выбора нормировки и расстояния снимается. Заметим, однако, что некоторым методам ниже нужны сами координаты объектов, а не только расстояния между ними.

Типы классов

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

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

C2. Кластер (сгущение в среднем). Среднее расстояние внутри класса меньше среднего расстояния от объектов класса до всех остальных.

C3. Класс типа ленты (слабое сгущение). Существует $\tau > 0$ такое, что для любого $\boldsymbol x_i$ из класса $S$ найдётся объект $\boldsymbol x_j \in S$ с $d_{ij} \le \tau$, а для всех $\boldsymbol x_k \notin S$ выполнено $d_{ik} > \tau$. Класс можно пройти «по кочкам» с шагом не больше $\tau$, и при этом не выпрыгнуть наружу.

C4. Класс с центром. Существуют порог $R > 0$ и точка $\boldsymbol x^*$ в пространстве (в частности, элемент класса) такие, что все объекты из $S$ и только они лежат в шаре радиуса $R$ с центром $\boldsymbol x^*$. Часто в качестве $\boldsymbol x^*$ выступает центр масс класса — средние значения признаков по объектам класса.

У Лагутина на рисунке 6 шесть пар множеств показывают, чем типы отличаются:

• $A$ и $B$ — две компактные далёкие кучки, это ядра (C1); остальные пары по C1 уже не разделяются;
• $C$ и $D$ ядрами не являются, но разделяются как кластеры (C2);
• у вытянутых $E$ и $G$ среднее внутреннее расстояние больше, чем среднее расстояние до соседей $F$ и $H$, так что кластерами они не являются; но как ленты (C3) разделяются;
• в смысле C3 разделяются все пары, кроме $I$ и $J$ и кроме $K$ и $L$;
• $I$ и $J$ — классы с центром (C4), а вытянутые $E$, $F$, $G$ — нет;
• налегающие множества $K$ и $L$ (разреженное облако и плотное пятно на нём) не разделяются ни одним из определений.

Тем не менее в примере 4 из §5 предлагается способ провести разделяющую границу и между перекрывающимися множествами — на основе статистической модели случайного выбора из одной из $k$ многомерных нормальных совокупностей.

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

Проверь себя