如何为地图数据使用tSNE聚类

编译：yxy

出品：ATYUN订阅号

在本文中，我会展示如何在经纬度坐标对上使用tSNE来创建地图数据的一维表示。这种表示有助于开发新的地图搜索算法。这对于诸如“这个经纬度坐标是新泽西或者纽约的吗？”或“离我最近的披萨位置在哪里？”这样的查询非常有用。更快的地图搜索对于Uber，Google Maps和Directions，Yelp等公司来说非常有价值。

在这篇文章中，我们将首先看看如何在真值表逻辑数据集上使用tSNE维度映射，然后我们将使用相同的概念将经纬度坐标映射到一维空间。在我们获得一维表示之后，我们可以实现算法以使用集合关系（set membership）操作等方式进行恒定时间搜索。

tSNE（t-distributed stochastic neighbor embedding）是一种聚类技术，其最终结果与PAC(principal component analysis)相似。PCA使用线性代数概念来构造一个新的正交向量的维空间，而tSNE使用容易理解的，排斥或吸引的方法将点从高维空间映射到低维空间。许多聚类算法的核心是以这样的方式识别高维数据集中的相似性，从而可以降低维度。tSNE算法用于保持较高空间中的线性空间关系，而一些聚类算法例如，径向基函数网络中使用的算法是试图增强空间关系，使得新空间可线性分离(例如XOR逻辑问题的解决方案。

要在python中使用tSNE，比较简单方法是使用sklearn：

from sklearn.manifoldimport TSNE

# sample data set

X= np.array([[0,0],[0,1],[1,0],[1,1]])

X_embedded= TSNE(n_components=1).fit_transform(X)

注：在Python中，可以使用以下方法创建一维线形图：将y轴固定在一个常量上，例如:plt.scatter(X_embedded,y=[1,1,1,1])

现在，我们已经看到tSNE如何将逻辑真值表映射到1维空间中，让我们传入一个映射数据集例子：波士顿，迈阿密和旧金山经纬度组成的映射数据集。

Boston: [42.3601,-71.0589],

Miami: [25.7617,-80.1918],

SF: [37.7749,-122.4194]

# This is done with the following code

from sklearn.manifoldimport 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)

现在，我们已将这些经纬度对转换到1维空间

Boston: [42.3601,-71.0589] ->14,473.32

Miami:  [25.7617,-80.1918] ->3299.8037

SF:     [37.7749,-122.4194]->-7838.6094

拥有低维空间表示有很多优势，如保持空间信息在同一的坐标空间（高维空间的采样）。具有较低维空间表示同时在与采样的高维空间相同的坐标空间中保留空间信息具有许多优点。我们可以对来自基本数据结构的这些数据使用所有1维排序和搜索算法。此外，将经纬度维数降低到1维会减少进行距离计算所需计算量的一半。我们可以只取新的1维表示的差，而不取经度和维度值之间的差。

如果对更快的地图搜索算法感兴趣，可以访问下方链接：

https://towardsdatascience.com/kmeans-hash-search-map-search-in-o-n%C2%B2lgn-33743ece434f