kNN для геоданных
В одном из последних постов упомянула, что классический knn не оч хорош для геоданных, полетели вопросы в лс) Поэтому решила сделать отдельный пост!

📍ПРОБЛЕМЫ

1. Масштабирование признаков
Геоданные обычно представлены в виде координат (широта, долгота), которые могут иметь разный масштаб (например, градусы vs. метры). Если не нормализовать данные, расстояние между точками будет искажаться.
Пример:
- В градусах: lat ∈ [-90, 90], lon ∈ [-180, 180] → долгота влияет сильнее.
- В метрах: 1° широты ≈ 111 км, 1° долготы ≈ 111 км × cos(lat) → зависимость от широты.

2. Расстояние на сфере (Земля не плоская)
Евклидово расстояние (sqrt(Δlat² + Δlon²)) плохо работает на больших дистанциях, так как искажает реальные расстояния на сфере.
Пример:
- Вблизи экватора 1° ≈ 111 км, но ближе к полюсам 1° долготы → 0 км.

3. Неравномерная плотность данных
В городах точек может быть много, а в сельской местности — мало. Это приводит к:
- Смещению предсказаний (kNN будет давать больше веса густонаселённым регионам).
- Проблемам с выбором k (в плотных районах нужно маленькое k, в разреженных — большое).

4. Вычислительная сложность
kNN требует хранения всех данных и вычисления расстояний для каждого нового объекта → O(N) на запрос. Для больших геодатасетов (миллионы точек) это неэффективно.

5. Категориальные признаки
Если в данных есть категории (например, тип местности), их сложно учесть в стандартной метрике расстояния.

📍КАК УЛУЧШИТЬ kNN ДЛЯ ГЕОДАННЫХ?

1. Использовать метрики, которые учитывают кривизну Земли.
- самая популярная Haversine distance

  from sklearn.metrics.pairwise import haversine_distances
  distances = haversine_distances([[lat1, lon1], [lat2, lon2]])
  

- Vincenty distance более точный, но более медленный

2. Нормализация и масштабирование
- Если используете евклидово расстояние, приведите координаты к метрам (например, через pyproj).
- Можно применить StandardScaler или MinMaxScaler.
Спойлер: в конце будет про UTM

3. Учет пространственной автокорреляции
- Взвешенный kNN – давать больше веса ближайшим соседям (например, weight = 1 / distance).
- KD-деревья или Ball Trees – ускоряют поиск соседей в пространственных данных (sklearn.neighbors.BallTree)
*** кстати соседей в своей работе в Яндексе я ищу через роутеры по улично-дорожной сети, т.к. в моих задачах мне важна транспортная доступность

4. Оптимизация выбора k
- Использовать кросс-валидацию с учетом пространственного разделения (например, sklearn.model_selection.KFold с учетом координат).
- Методы вроде LOOCV (Leave-One-Out Cross-Validation) для маленьких датасетов.

📍А КАК ЖЕ UTM???
UTM действительно помогают работать с геоданными в локальных координатах, но у них есть свои нюансы. За этими проекции следуюдет признать:
✅ Евклидово расстояние работает лучше – в метрах, а не в градусах.
✅ Меньше искажений на небольших территориях (город, область).
✅ Быстрые вычисления – не нужно считать Haversine.

Но есть ограничения...

1. Границы зон
Точки из разных зон UTM нельзя сравнивать напрямую (easting повторяется), нужно разбивать данные по зонам или использовать Haversine.
2. Большие расстояния
UTM искажает расстояния за пределами зоны (~1000 км), для континентальных данных лучше подходит Haversine/Vincenty.
3. Высота не учитывается
UTM работает только с 2D-координатами. Если нужен рельеф, нужно добавлять altitude в метрику расстояния.
4. Неравномерная плотность
В городах точек больше, чем в сельской местности, тут нужен адаптивный k или взвешенный kNN.

P.S. как быстро определить зону UTM

  import math
  utm_zone = math.floor((lon+180)/6)+1

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

@urban_mash