Внутреннее измерение
Количество переменных, необходимых для минимального представления многомерных данных

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

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

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

Пример

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

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

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

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

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

Для N -переменной функции f набор переменных можно представить в виде N -мерного вектора x : . ф = ф ( х )  где  х = ( х 1 , … , х Н ) {\textstyle f=f\left(\mathbf {x} \right){\text{ где }}\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 , заданных как и , где B — невырожденная матрица M × M , поскольку . г ′ ( у ) = г ( Б у ) {\ textstyle g' \ left (\ mathbf {y} \ right) = g \ left (\ mathbf {By} \ right)} А ′ = Б − 1 А {\textstyle \mathbf {A'} =\mathbf {B} ^{-1}\mathbf {A} } ф ( х ) = г ′ ( А ′ х ) = г ( Б А ′ х ) = г ( А х ) {\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. Это означает, что существует нормализованный вектор и функция одной переменной g, такие, что для всех . Если F — преобразование Фурье f (обе функции двух переменных), то должно быть так, что . н ∈ Р 2 {\textstyle \mathbf {n} \in \mathbb {R} ^{2}} ф ( х ) = г ( н Т х ) {\textstyle f(\mathbf {x} )=g(\mathbf {n} ^{\operatorname {T} }\mathbf {x} )} х ∈ Р 2 {\textstyle \mathbf {x} \in \mathbb {R} ^{2}} Ф ( ты ) = Г ( н Т ты ) ⋅ δ ( м Т ты ) {\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 — нормализованный вектор, перпендикулярный n . Это означает, что F обращается в нуль всюду, кроме линии , проходящей через начало координат частотной области и параллельной m . Вдоль этой линии F изменяется в соответствии с G. Р 2 {\textstyle \mathbb {R} ^{2}}

Общий случай

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

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

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

Обобщения

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

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

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

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

f ( y 1 + y 2 2 , y 1 − y 2 2 ) = g ( y 1 ) {\displaystyle 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 ( x 1 2 + x 2 2 ) {\displaystyle f(x_{1},x_{2})=g\left({\sqrt {x_{1}^{2}+x_{2}^{2}}}\right)} , f является i1D и постоянна вдоль любой окружности с центром в начале координат
  • f ( x 1 , x 2 ) = g ( arctan ⁡ ( x 2 x 1 ) ) {\displaystyle f(x_{1},x_{2})=g\left(\arctan \left({\frac {x_{2}}{x_{1}}}\right)\right)} , f является i1D и постоянна вдоль всех лучей из начала координат

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

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

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

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

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

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

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

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

Измерьте для многих точек расстояния до двух ближайших соседей точки. μ = r 2 / r 1 {\displaystyle \mu =r_{2}/r_{1}} r 1 , r 2 {\displaystyle r_{1},r_{2}}

Подобрать эмпирическую функцию распределения к . μ {\displaystyle \mu } 1 − μ − d {\displaystyle 1-\mu ^{-d}}

Возвращаться . d {\displaystyle d}

История

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

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

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

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

Приложения

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

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

Смотрите также

Ссылки

  1. ^ Амсалег, Лоран; Челли, Усама; Фурон, Тедди; Жирар, Стефан; Хоуль, Майкл Э.; Каварабаяши, Кен-ичи; Нетт, Майкл (2015-08-10). "Оценка локальной внутренней размерности". Труды 21-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . KDD '15. Сидней, Новый Южный Уэльс, Австралия: Ассоциация вычислительной техники. стр.  29–38 . doi :10.1145/2783258.2783405. ISBN 978-1-4503-3664-2. S2CID  16058196.
  2. ^ Хоул, ME; Кашима, H.; Нетт, M. (2012). «Обобщенное измерение расширения». IEEE 12-я международная конференция по интеллектуальному анализу данных , семинары 2012 г. стр.  587–594 . doi :10.1109/ICDMW.2012.94. ISBN 978-1-4673-5164-5. S2CID  8336466.
  3. ^ Thordsen, Erik; Schubert, Erich (2020). «ABID: внутренняя размерность на основе угла». В Satoh, Shin'ichi; Vadicamo, Lucia; Zimek, Arthur; Carrara, Fabio; Bartolini, Ilaria; Aumüller, Martin; Jónsson, Björn Þór; Pagh, Rasmus (ред.). Поиск по сходству и его применение . Конспект лекций по информатике. Том 12440. Cham: Springer International Publishing. стр.  218–232 . arXiv : 2006.12880 . doi :10.1007/978-3-030-60936-8_17. ISBN 978-3-030-60936-8. S2CID  219980390.
  4. ^ Камастра, Франческо; Стайано, Антонино (2016-01-20). «Оценка внутренней размерности: достижения и открытые проблемы». Информационные науки . 328 : 26–41 . doi :10.1016/j.ins.2015.08.029. ISSN  0020-0255.
  5. ^ Факко, Елена; д'Эррико, Мария; Родригес, Алекс; Лайо, Алессандро (2017-09-22). "Оценка внутренней размерности наборов данных по минимальной информации о соседстве". Scientific Reports . 7 (1): 12140. arXiv : 1803.06992 . Bibcode :2017NatSR...712140F. doi : 10.1038/s41598-017-11873-y . ISSN  2045-2322. PMC 5610237 . PMID  28939866. 
  6. ^ Торгерсон, Уоррен С. (1978) [1958]. Теория и методы масштабирования . Wiley. ISBN 0471879452. OCLC  256008416.
  7. ^ Шепард, Роджер Н. (1962). «Анализ близости: многомерное шкалирование с неизвестной функцией расстояния. I». Психометрика . 27 (2): 125–140 . doi :10.1007/BF02289630. S2CID  186222646.
  8. ^ Шепард, Роджер Н. (1974). «Представление структуры в данных о сходстве: проблемы и перспективы». Психометрика . 39 (4): 373–421 . doi :10.1007/BF02291665. S2CID  121704645.
  9. ^ Беннет, Роберт С. (июнь 1965 г.). «Представление и анализ сигналов — Часть XXI: Внутренняя размерность наборов сигналов». Rep. 163. Балтимор, Мэриленд: Университет Джонса Хопкинса.
  10. ^ Роберт С. Беннетт (1965). Представление и анализ сигналов Часть XXI. Внутренняя размерность наборов сигналов (PDF) (PhD). Энн-Арбор, Мичиган: Университет Джонса Хопкинса. Архивировано из оригинала (PDF) 27 декабря 2019 г.
  11. ^ Беннетт, Роберт С. (сентябрь 1969 г.). «Внутренняя размерность наборов сигналов». Труды IEEE по теории информации . 15 (5): 517– 525. doi :10.1109/TIT.1969.1054365.
  12. ^ Фукунага, К.; Олсен, Д. Р. (1971). «Алгоритм нахождения внутренней размерности данных». IEEE Transactions on Computers . 20 (2): 176– 183. doi :10.1109/TC.1971.223208. S2CID  30206700.
  13. ^ Pettis, KW; Bailey, Thomas A.; Jain, Anil K.; Dubes, Richard C. (1979). «Оценка внутренней размерности на основе информации о близком соседе». IEEE Transactions on Pattern Analysis and Machine Intelligence . 1 (1): 25–37 . doi :10.1109/TPAMI.1979.4766873. PMID  21868828. S2CID  2196461.
  14. ^ Транк, Г. В. (1976). «Статистическая оценка внутренней размерности набора зашумленных сигналов». IEEE Transactions on Computers . 100 (2): 165– 171. doi :10.1109/TC.1976.5009231. S2CID  1181023.
  15. ^ Grassberger, P.; Procaccia, I. (1983). «Измерение странности странных аттракторов». Physica D: Nonlinear Phenomena . 9 ( 1– 2): 189– 208. Bibcode :1983PhyD....9..189G. doi :10.1016/0167-2789(83)90298-1.
  16. ^ Takens, F. (1984). "О численном определении размерности аттрактора". В Tong, Howell (ред.). Dynamical Systems and Bifurcations, Proceedings of a Workshop Held in Groningen, The Netherlands, April 16-20, 1984. Lecture Notes in Mathematics. Vol. 1125. Springer-Verlag. pp.  99– 106. doi :10.1007/BFb0075637. ISBN 3540394117.
  17. ^ Катлер, CD (1993). "Обзор теории и оценки фрактальной размерности". Оценка размерности и модели . Нелинейные временные ряды и хаос. Том 1. World Scientific. С.  1– 107. ISBN 9810213530.
  18. ^ Харт, Д. (2001). Мультифракталы — теория и приложения . Chapman and Hall/CRC. ISBN 9781584881544.
  19. ^ Чавес, Э. (2001). «Поиск в метрических пространствах». ACM Computing Surveys . 33 (3): 273– 321. doi : 10.1145/502807.502808. hdl : 10533/172863 . S2CID  3201604.
  20. ^ Пестов, В. (2008). «Аксиоматический подход к внутренней размерности набора данных». Нейронные сети . 21 ( 2– 3): 204– 213. arXiv : 0712.2063 . doi :10.1016/j.neunet.2007.12.030. PMID  18234471. S2CID  2309396.
  21. ^ Кнутссон, Ганс (1982). Фильтрация и реконструкция в обработке изображений (PDF) . Исследования Линчёпинга в области науки и технологий. Том 88. Университет Линчёпинга. ISBN 91-7372-595-1. oai:DiVA.org:liu-54890.
  22. ^ Бигун, Йозеф; Гранлунд, Гёста Х. (1987). «Оптимальное определение ориентации линейной симметрии» (PDF) . Труды Международной конференции по компьютерному зрению . С.  433–438 .
  23. ^ Гранлунд, Гёста Х.; Кнутссон, Ганс (1995). Обработка сигналов в компьютерном зрении. Клювер Академик. ISBN 978-1-4757-2377-9.
  • Майкл Фельсберг; Синан Калкан; Норберт Крюгер (2009). «Характеристика непрерывной размерности структур изображений». Image and Vision Computing . 27 (6): 628– 636. doi :10.1016/j.imavis.2008.06.018. hdl : 11511/36631 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Intrinsic_dimension&oldid=1258161882"