Внутреннее измерение

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

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

Внутреннее измерение можно использовать как нижнюю границу того, в какое измерение можно сжать набор данных посредством уменьшения размерности, но его также можно использовать как меру сложности набора данных или сигнала. Для набора данных или сигнала N переменных его внутренняя размерность M удовлетворяет 0 ≤ M ≤ N , хотя средства оценки могут давать более высокие значения.

Пример

Позволять ${\textstyle f(x_{1},x_{2})}$ быть функцией двух переменных (или сигналом ), которая имеет форму ${\textstyle f(x_{1},x_{2})=g(x_{1})}$для некоторой функции одной переменной g , которая не является постоянной . Это означает, что f меняется в соответствии с g по первой переменной или по первой координате . С другой стороны, f постоянна по отношению ко второй переменной или по второй координате. Для определения значения f необходимо знать только значение одной, а именно первой переменной . Следовательно, это функция двух переменных, но ее внутренняя размерность равна единице.

Немного более сложный пример: ${\textstyle f(x_{1},x_{2})=g(x_{1}+x_{2})}$. f по-прежнему является одномерным, в чем можно убедиться, выполнив преобразование переменных ${\textstyle y_{1}=x_{1}+x_{2}}$ и ${\textstyle y_{2}=x_{1}-x_{2}}$что дает ${\textstyle f\left({\frac {y_{1}+y_{2}}{2}},{\frac {y_{1}-y_{2}}{2}}\right)=g\left(y_{1}\right)}$.Поскольку изменение f может быть описано единственной переменной y _1, ее внутренняя размерность равна единице.

В случае, когда f является постоянным, его внутренняя размерность равна нулю, поскольку для описания вариации не требуется никакой переменной. В общем случае, когда внутренняя размерность функции двух переменных f не равна ни нулю, ни единице, она равна двум.

В литературе функции, имеющие внутреннюю размерность ноль, единицу или два, иногда называют i0D , i1D или i2D соответственно.

Формальное определение сигналов

Для с N функции f -переменными набор переменных можно представить как N -мерный вектор x : ${\textstyle f=f\left(\mathbf {x} \right){\text{ where }}\mathbf {x} =\left(x_{1},\dots ,x_{N}\right)}$.

Если для некоторой с M функции g -переменной и размера M × N, матрицы A то верно ли, что

• для всех х ; ${\textstyle f(\mathbf {x} )=g(\mathbf {Ax} ),}$
• M указанное выше соотношение между f и g , — наименьшее число, для которого можно найти

тогда внутренняя размерность f равна M .

Внутреннее измерение — это характеристика f , но не однозначная характеристика ни g ни A. , То есть, если вышеуказанное соотношение удовлетворяется для некоторых f , g и A , оно также должно удовлетворяться для тех же f , g' и A', заданных формулами ${\textstyle g'\left(\mathbf {y} \right)=g\left(\mathbf {By} \right)}$и ${\textstyle \mathbf {A'} =\mathbf {B} ^{-1}\mathbf {A} }$где B — неособая матрица размера M × M , поскольку ${\textstyle f\left(\mathbf {x} \right)=g'\left(\mathbf {A'x} \right)=g\left(\mathbf {BA'x} \right)=g\left(\mathbf {Ax} \right)}$.

Преобразование Фурье сигналов малой внутренней размерности

Функция переменной N , имеющая внутреннюю размерность M < N, имеет характеристическое преобразование Фурье . Интуитивно понятно, что, поскольку этот тип функции является постоянным в одном или нескольких измерениях, ее преобразование Фурье должно выглядеть как импульс ( преобразование Фурье константы) в том же измерении в частотной области .

Простой пример

Пусть f — функция двух переменных, равная i1D. Это означает, что существует нормированный вектор ${\textstyle \mathbf {n} \in \mathbb {R} ^{2}}$ и функция одной переменной g такая, что ${\textstyle f(\mathbf {x} )=g(\mathbf {n} ^{\operatorname {T} }\mathbf {x} )}$для всех ${\textstyle \mathbf {x} \in \mathbb {R} ^{2}}$. Если F является преобразованием Фурье f (обе функции двух переменных), то это должно быть так, что ${\textstyle F\left(\mathbf {u} \right)=G\left(\mathbf {n} ^{\mathrm {T} }\mathbf {u} \right)\cdot \delta \left(\mathbf {m} ^{\mathrm {T} }\mathbf {u} \right)}$.

Здесь G — преобразование Фурье g (обе функции с одной переменной), δ — импульсная функция Дирака , а m — нормированный вектор в ${\textstyle \mathbb {R} ^{2}}$ перпендикулярно н . Это означает, что F исчезает везде, кроме линии, которая проходит через начало частотной области и параллельна m . линии F меняется в зависимости от G. Вдоль этой

Общий случай

Пусть f — функция с N -переменной, имеющая внутреннюю размерность M , то есть существует с M функция g -переменной и размера M × N матрица A такая, что ${\textstyle f(\mathbf {x} )=g(\mathbf {Ax} )\quad \forall \mathbf {x} }$.

Тогда его преобразование Фурье F можно описать следующим образом:

• F исчезает везде, кроме подпространства размерности M
• Подпространство M натянуто строками матрицы A
• В подпространстве F меняется в зависимости от g Фурье преобразования

Обобщения

Описанный выше тип внутренней размерности предполагает, что применяется линейное преобразование к координатам с N -переменной функции f для создания M переменных, которые необходимы для представления каждого значения f . Это означает, что постоянна вдоль линий, плоскостей или гиперплоскостей, в зависимости от N и M. f

В общем случае f имеет внутреннюю размерность M, если существуют M функций a ₁ , a ₂ , ..., a _M и с M функция g -переменной такие, что

• ${\textstyle f(\mathbf {x} )=g\left(a_{1}(\mathbf {x} ),a_{2}(\mathbf {x} ),\dots ,a_{M}(\mathbf {x} )\right)}$для всех х
• M — наименьшее количество функций, допускающее указанное выше преобразование.

Простой пример — преобразование функции с двумя переменными f в полярные координаты:

$$f\left({\frac {y_{1}+y_{2}}{2}},{\frac {y_{1}-y_{2}}{2}}\right)=g\left(y_{1}\right)$$

• $f(x_{1},x_{2})=g\left({\sqrt {x_{1}^{2}+x_{2}^{2}}}\right)$, f равно i1D и является постоянным вдоль любой окружности с центром в начале координат.
• $f(x_{1},x_{2})=g\left(\arctan \left({\frac {x_{2}}{x_{1}}}\right)\right)$, f есть i1D и постоянна вдоль всех лучей из начала координат

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

Локальная внутренняя размерность

Локальная внутренняя размерность (LID) относится к наблюдению, что часто данные распределяются по многообразию меньшей размерности, когда рассматривается только близлежащее подмножество данных. Например, функция $f(x,y)=x+\max\{0,|y|-1\}$ можно считать одномерным, когда y близко к 0 (с одной переменной x ), двумерным, когда y близко к 1, и снова одномерным, когда y положительное и намного больше 1 (с переменной x+y ). .

Локальная внутренняя размерность часто используется по отношению к данным. Затем он обычно оценивается на основе k ближайших соседей точки данных: часто основано на концепции, связанной с удвоением измерения в математике. Поскольку объем d -сферы растет экспоненциально по d , скорость, с которой обнаруживаются новые соседи по мере увеличения радиуса поиска, может использоваться для оценки локальной внутренней размерности (например, оценка GED ). Однако были предложены альтернативные подходы к оценке, например, оценка на основе угла.

Оценка внутреннего размера

Внутреннюю размерность многообразия данных можно оценить многими методами, в зависимости от предположений о многообразии данных. Обзор 2016 года.

Метод двух ближайших соседей (TwoNN) — это метод оценки внутренней размерности погруженного риманова многообразия . Алгоритм следующий:

Разбросайте несколько точек на многообразии.

Мера $\mu =r_{2}/r_{1}$ для многих точек, где $r_{1},r_{2}$ — расстояния до двух ближайших соседей точки.

Соответствуйте CDF эмпирическому $\mu$ к $1-\mu ^{-d}$.

Возвращаться $d$.

История

были разработаны так называемые методы «масштабирования» В 1950-х годах в социальных науках для исследования и обобщения многомерных наборов данных. После того, как Шепард в 1962 году представил неметрическое многомерное масштабирование. Одной из основных областей исследований в рамках многомерного масштабирования (MDS) была оценка внутренней размерности. Эта тема также изучалась в теории информации , впервые предложенной Беннетом в 1965 году, который ввел термин «внутреннее измерение» и написал компьютерную программу для его оценки.

В 1970-е годы были построены методы оценки внутренней размерности, которые не зависели от уменьшения размерности, такие как MDS: на основе локальных собственных значений. на основе распределения расстояний, и на основе других геометрических свойств, зависящих от размера.

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

В 2000-х годах «проклятие размерности» использовалось для оценки внутренней размерности.

Приложения

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

Например, концепция, которая здесь называется окрестностью изображения внутренней размерности 1 или окрестностью i1D, называет одномерной . Кнутссон (1982) линейная симметричная работа Бигюн и Гранлунд (1987) и простой район в Granlund & Knutsson (1995).

См. также

• Измерение
• Фрактальное измерение
• Размерность Хаусдорфа
• Топологическое измерение

Ссылки

• Майкл Фельсберг; Синан Калкан; Норберт Крюгер (2009). «Характеристика непрерывной размерности структур изображений» . Вычисление изображений и зрительных образов . 27 (6): 628–636. дои : 10.1016/j.imavis.2008.06.018 . hdl : 11511/36631 .