Геометрия такси

редактировать
Тип геометрии с использованием метрики Manhattan или L1 Taxicab геометрия в сравнении с евклидовым расстоянием: в геометрии такси красный, желтый и синий пути имеют одинаковую длину кратчайшего пути, равную 12. В евклидовой геометрии зеленая линия имеет длину 6 2 ≈ 8,49 {\ displaystyle 6 {\ sqrt {2}} \ приблизительно 8,49}6 {\ sqrt {2}} \ приблизительно 8,49 и является уникальным кратчайшим путем.

A геометрия такси - это форма геометрии, в которой обычная функция расстояния или метрика из евклидовой геометрии заменяется новой метрикой, в которой расстояние между двумя точками является суммой абсолютных разностей их Декартовы координаты. Показатель такси также известен как прямолинейное расстояние, L1расстояние, L расстояние или ℓ 1 {\ displaystyle \ ell _ { 1}}\ ell _ {1} norm (см. L пробел ), snake distance, городской квартал, Манхэттенское расстояние или Манхэттенская длина, с соответствующими вариациями названия геометрии. Последние названия ссылаются на сетку большинства улиц на острове Манхэттен, которая определяет кратчайший путь, по которому машина может проехать между двумя перекрестками в районе иметь длину, равную расстоянию перекрестков в геометрии такси.

Геометрия использовалась в регрессионном анализе с 18 века, и сегодня ее часто называют LASSO. Геометрическая интерпретация относится к неевклидовой геометрии 19 века и принадлежит Герману Минковскому.

Содержание

  • 1 Формальное определение
  • 2 Свойства
    • 2.1 Круги
  • 3 Приложения
    • 3.1 Измерение расстояний в шахматах
    • 3.2 Сжатое зондирование
    • 3.3 Различия в частотных распределениях
  • 4 История
  • 5 См. Также
  • 6 Примечания
  • 7 Ссылки
  • 8 Внешние ссылки

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

Расстояние такси, d 1 {\ displaystyle d_ {1}}d_ {1} , между двумя векторами p, q {\ displaystyle \ mathbf {p}, \ mathbf {q}}\ mathbf {p}, \ mathbf {q} в n-мерном вещественном векторном пространстве с фиксированной декартовой системой координат, - это сумма длин проекций отрезка отрезка между точками на оси координат . Более формально

d 1 (p, q) = ‖ p - q ‖ 1 = ∑ i = 1 n | p i - q i |, {\ displaystyle d_ {1} (\ mathbf {p}, \ mathbf {q}) = \ | \ mathbf {p} - \ mathbf {q} \ | _ {1} = \ sum _ {i = 1} ^ {n} | p_ {i} -q_ {i} |,}d_ {1} (\ mathbf {p}, \ mathbf {q}) = \ | \ mathbf {p} - \ mathbf {q} \ | _ {1} = \ sum _ {i = 1} ^ {n} | p_ {i} -q_ {i} |,

где (p, q) {\ displaystyle (\ mathbf {p}, \ mathbf {q})}(\ mathbf {p}, \ mathbf {q}) - это векторы

p = (p 1, p 2,…, pn) и q = (q 1, q 2,…, qn) {\ displaystyle \ mathbf {p} = (p_ {1 }, p_ {2}, \ dots, p_ {n}) {\ text {and}} \ mathbf {q} = (q_ {1}, q_ {2}, \ dots, q_ {n}) \,}\ mathbf {p} = (p_ {1}, p_ {2}, \ dots, p_ {n}) {\ text {and}} \ mathbf {q} = (q_ {1}, q_ {2}, \ dots, q_ {n }) \,

Например, в плоскости расстояние такси между (p 1, p 2) {\ displaystyle (p_ {1}, p_ {2})}(p_ {1}, p_ {2}) и (q 1, q 2) {\ displaystyle (q_ {1}, q_ {2})}(q_ {1}, q_ {2}) равно | p 1 - q 1 | + | p 2 - q 2 |. {\ displaystyle | p_ {1} -q_ {1} | + | p_ {2} -q_ {2} |.}| p_ {1} -q_ {1} | + | p_ {2} -q_ {2} |.

Свойства

Расстояние такси зависит от поворота системы координат, но не зависит от его отражения относительно координатной оси или его смещения. Геометрия такси удовлетворяет всем аксиомам Гильберта (формализация евклидовой геометрии ) за исключением аксиомы стороны-угла-стороны, как два треугольника с одинаковой «длиной» две стороны и одинаковый угол между ними обычно не конгруэнтны, если только упомянутые стороны не параллельны.

Круги

Круги в дискретной и непрерывной геометрии такси

A круг - это набор точек с фиксированным расстоянием, называемым радиусом, от точки, называемой центром. В геометрии такси расстояние определяется другой метрикой, чем в евклидовой геометрии, и форма кругов также изменяется. Круги такси - это квадраты со сторонами, ориентированными под углом 45 ° к осям координат. На изображении справа показано, почему это так, красным цветом показаны все точки с фиксированным расстоянием от центра, показанные синим цветом. По мере уменьшения размеров городских кварталов количество точек становится больше и они превращаются в повернутый квадрат в непрерывной геометрии такси. Каждая сторона будет иметь длину 2 r {\ displaystyle {\ sqrt {2}} r}\ sqrt {2} r с использованием евклидовой метрики, где r - радиус круга, его длина в геометрия такси 2кг. Таким образом, длина окружности равна 8р. Таким образом, значение геометрического аналога π {\ displaystyle \ pi}\ pi равно 4 в этой геометрии. Формула единичного круга в геометрии такси: | х | + | y | = 1 {\ displaystyle | x | + | y ​​| = 1}| x | + | y ​​| = 1 в декартовых координатах и

r = 1 | грех ⁡ θ | + | cos ⁡ θ | {\ displaystyle r = {\ frac {1} {| \ sin \ theta | + | \ cos \ theta |}}}r = {\ frac {1} {| \ sin \ theta | + | \ cos \ theta |}}

в полярных координатах.

круг радиуса 1 (с использованием этого расстояния) это окрестность фон Неймана его центра.

Окружность радиуса r для расстояния Чебышева (L∞метрика ) на плоскости также является квадратом со стороной 2r, параллельной осям координат, поэтому можно увидеть плоское расстояние Чебышева как эквивалент вращением и масштабированием до планарного расстояния такси. Однако эта эквивалентность между показателями L 1 и L ∞ не распространяется на более высокие измерения.

Всякий раз, когда каждая пара в наборе этих кругов имеет непустое пересечение, существует точка пересечения для всего набора; следовательно, манхэттенское расстояние образует инъективное метрическое пространство .

Приложения

Меры расстояний в шахматах

В chess расстояние между квадратами на шахматная доска для ладей измеряется расстоянием такси; короли и королевы используют расстояние Чебышева, а слоны используют расстояние такси (между квадратами одного цвета) на шахматной доске, повернутой на 45 градусов, т.е. с его диагоналями в качестве координатных осей. Чтобы добраться от одной клетки до другой, только королям требуется количество ходов, равное их соответствующему расстоянию; для ладей, ферзей и слонов требуется один или два хода (на пустой доске и при условии, что этот ход вообще возможен в случае слона).

Сжатое измерение

При решении недоопределенной системы линейных уравнений, член регуляризации для вектора параметров выражается в терминах ℓ 1 {\ displaystyle \ ell _ {1}}\ ell _ {1} -норма (геометрия такси) вектора. Этот подход появляется в структуре восстановления сигнала под названием сжатое зондирование.

Различия частотных распределений

Геометрия такси может использоваться для оценки различий в дискретных частотных распределениях. Например, в сплайсинге РНК позиционные распределения гексамеров, которые отображают вероятность появления каждого гексамера на каждом заданном нуклеотиде рядом с сайтом сплайсинга, можно сравнить с L1-расстояние. Каждое распределение положений может быть представлено в виде вектора, где каждая запись представляет вероятность того, что гексамер начинается с определенного нуклеотида. Большое расстояние L1 между двумя векторами указывает на значительную разницу в характере распределений, в то время как небольшое расстояние означает распределения схожей формы. Это эквивалентно измерению площади между двумя кривыми распределения, поскольку площадь каждого сегмента представляет собой абсолютную разницу между вероятностями двух кривых в этой точке. При суммировании для всех сегментов он дает ту же меру, что и расстояние L1.

История

Метрика L использовалась в регрессионном анализе в 1757 г. Роджер Джозеф Боскович. Геометрическая интерпретация датируется концом 19 века и развитием неевклидовой геометрии, в частности, Германом Минковским и его неравенством Минковского, из которых эта геометрия является особый случай, особенно используемый в геометрии чисел, (Minkowski 1910). Формализация L пробелов приписывается (Riesz 1910).

См. Также

Примечания

Ссылки

Внешние ссылки

Последняя правка сделана 2021-06-09 11:09:57
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте