В этом коротком сообщении в блоге я покажу вам, как использовать tSNE для пар координат Lat / Lng для создания одномерного представления картографических данных. Это представление полезно для разработки новых алгоритмов поиска по карте. Они могут быть полезны для таких запросов, как «Эта пара координат широта / долгота находится в Нью-Джерси или Нью-Йорке?» или «Где от меня ближайшая пиццерия?». Более быстрый поиск по карте может быть очень полезен для таких вещей, как Uber, Google Maps and Directions, Yelp и многих других.

В этом посте мы сначала рассмотрим, как сопоставления размерности tSNE могут использоваться в наборе логических данных таблицы истинности, а затем мы перенесем те же концепции для сопоставления координат Lat / Lng в одномерном пространстве. После того, как у нас есть одномерное представление, мы можем реализовать алгоритмы, позволяющие выполнять поиск в постоянном времени с такими вещами, как операции с набором членства.

tSNE (t-распределенное стохастическое встраивание соседей) - это метод кластеризации, который имеет конечный результат, аналогичный PCA (анализ главных компонентов). В то время как PCA использует концепции линейной алгебры для построения нового размерного пространства ортогональных векторов, tSNE использует более простой для понимания подход «отталкивать / притягивать» для отображения точек из пространства высокой размерности в пространство меньшей размерности. Основное внимание многих алгоритмов кластеризации уделяется выявлению сходства в наборе данных большой размерности таким образом, чтобы можно было уменьшить размерность. Алгоритм tSNE работает, чтобы сохранить линейные пространственные отношения в верхнем пространстве, тогда как некоторые алгоритмы кластеризации, такие как то, что используется в сети радиальной базовой функции, пытаются увеличить пространственные отношения так, чтобы новое пространство было линейно отделимым, например, решение для проблема логики XOR.

Один простой способ использовать tSNE в python - использовать пакет sklearn:

from sklearn.manifold import TSNE
# sample data set
X = np.array([[0,0],[0,1],[1,0],[1,1]])
X_embedded = TSNE(n_components=1).fit_transform(X)

Теперь, когда мы увидели, как tSNE отображает логическую таблицу истинности в одномерное пространство, давайте подадим пример набора картографических данных, состоящего из пар широта / долгота для Бостона, Майами и Сан-Франциско.

Boston: [42.3601, -71.0589], 
Miami: [25.7617, -80.1918], 
SF: [37.7749, -122.4194]

# This is done with the following code
from sklearn.manifold import TSNE
X = np.array([[42.3601, -71.0589], [25.7617, -80.1918], [37.7749, -122.4194]])
X_embedded = TSNE(n_components=1).fit_transform(X)

Теперь мы преобразовали эти пары Lat / Lng в одномерное пространство.

Boston: [42.3601, -71.0589]  -> 14,473.32
Miami:  [25.7617, -80.1918]  -> 3299.8037
SF:     [37.7749, -122.4194] -> -7838.6094

Есть много преимуществ у пространственных представлений нижнего измерения при сохранении пространственной информации в том же координатном пространстве, что и у дискретизированного пространства высокого измерения. Мы можем использовать все одномерные алгоритмы сортировки и поиска по этим данным из элементарных структур данных. Кроме того, уменьшение размерности Lat / Lng до 1-D сокращает вдвое объем вычислений, необходимых для расчета расстояния. Вместо того, чтобы брать разницу между значениями lat и lng, мы можем просто взять разницу нового одномерного представления.

Если вас интересуют более быстрые алгоритмы поиска по карте, ознакомьтесь с этой статьей о том, как мы можем ускорить поиск, оставив координаты широты и долготы в двухмерном пространстве:



Поиск хэша kMeans по картографическим данным
Алгоритм кластеризации kMeans очень популярен благодаря своей классификации как« неконтролируемый искусственный интеллект … todatascience.com»



Спасибо за чтение! Пожалуйста, оставьте комментарий с любыми вопросами, идеями или вещами, которые, по вашему мнению, не так в этой статье.

CShorten

Коннор Шортен - студент факультета информатики Атлантического университета Флориды. Научные интересы в области науки о данных, глубокого обучения и разработки программного обеспечения. В основном кодирование на Python, JavaScript и C ++. Следите за дополнительными статьями по этим темам.