Визуализация многомерных данных очень полезна для выявления их важных закономерностей и свойств. Для этой цели используются алгоритмы снижения размерности. Среди наиболее распространенных алгоритмов можно отметить метод главных компонент (англ. principal component analysis, PCA) и стохастическое вложение соседей с t-распределением (англ. t-distributed Stochastic Neighbor Embedding, t-SNE). Оба этих алгоритма обладают высокой временной сложностью: $inline$O(n^3)$inline$ у PCA, $inline$O(n^2)$inline$ у t-SNE, где $inline$n$inline$ — количество объектов. К тому же у t-SNE есть по меньшей мере 3 гиперпараметра, к подбору которых он очень чувствителен. Я хочу вам рассказать о новом алгоритме полигональной системы координат (англ. polygonal coordinate system, PCS). Это алгоритм без гиперпараметров и со сложностью $inline$O(n)$inline$ от числа объектов.
Описание алгоритма
Полигональная система координат (PCS) — это способ представить входные вектора размерности $inline$S$inline$ на двумерной плоскости. Для этой цели в $inline$S$inline$-мерном пространстве признаков
$$display$$mathcal{X} = {x_i, x_i in mathbb{R}^S, 1 leqslant i leqslant N}$$display$$
$inline$N$inline$ вещественные точки представляются в виде правильных многоугольников с $inline$S$inline$ сторонами длины $inline$u$inline$ на плоскости, обозначается как $inline$Smbox{-}P_u$inline$. Его также называют межпространством, промежуточной стадией между большой размерностью и двумерной плоскостью. Многоугольники со сторонами 1 называются унитарными и обозначаются как $inline$Smbox{-}P_1$inline$ или просто $inline$Smbox{-}P$inline$.
Результирующее двумерное пространство задается двумя осями — горизонтальная $inline$w$inline$ и вертикальная $inline$h$inline$. Каждая сторона многоугольника $inline$vec{mathcal{X}_j}$inline$ представляет собой одну координату изначального $inline$S$inline$-мерного пространства. На рисунке выше представлены два многоугольника для (a) 3-мерного пространства признаков и (b) 6-мерного пространства. На рисунке $inline$vec{mathcal{X}_j}$inline$ — это метавектор, то есть задает множество векторов в одном направлении, но различной длины. Он обозначает проекцию $inline$j$inline$-й координаты точки на $inline$j$inline$-ю сторону многоугольника.
Алгоритм PCS состоит из трех шагов:
1) Нормализация данных
2) Проекция данных в межпространство
3) Проекция на плоскость.
Шаг 1. Нормализация данных
Это самый простой шаг и заключается в min-max нормализации признаков:
$$display$$z_j=frac{mathcal{X}_j-min(mathcal{X}_j)}{max(mathcal{X}_j)-min(mathcal{X}_j)}$$display$$
Эта нормализация нужна, чтобы результирующий многоугольник был унитарным и правильным.
Шаг 2. Проекция данных в межпространство
Рассмотрим угол $inline$theta_j$inline$ на рисунке выше. $inline$theta_j$inline$ — это угол от оси $inline$w$inline$ до $inline$vec{mathcal{X}_j}$inline$ в положительном направлении. Он равен (a) $inline$60^{circ}$inline$ и (b) $inline$150^{circ}$inline$. При этом каждый вектор $inline$vec{mathcal{X}_j}$inline$ будет образовывать такой угол $inline$theta_j$inline$, отсюда получаем последовательность из $inline$S$inline$ углов, считая по часовой стрелке. Первый угол в последовательности $inline$gamma$inline$ будет наибольшим и выражается как функция от внутреннего угла многоугольника $inline$alpha=frac{180(S-2)}{S}$inline$ как $inline$gamma=alpha + frac{180(1+(S;mod;2))}{S}$inline$. Так как позиция угла в последовательности важна, то нумерацию сторон многоугольника осуществим по правилу: начинать снизу многоугольника со второго квадранта и двигаться по часовой стрелке:
Тогда последовательность углов определяется так:
$$display$$theta_j=(gamma+alpha (j−1)$$display$$
Автор: nikitarykov
