我有一个来自世界特定地区地理数据的 X 和 Y 坐标列表。我想根据每个坐标在图中的位置分配一个权重。
例如:如果一个点位于周围有很多其他节点的地方,则它位于高密度区域,因此具有更高的权重。
我能想到的最直接的方法是在每个点周围绘制单位半径的圆,然后计算其他点是否位于其中,然后使用函数为该点分配权重。但这似乎很原始。
我看过 pySAL 和 NetworkX,但看起来它们可以处理图表。我在图中没有任何边,只有节点。
我有一个来自世界特定地区地理数据的 X 和 Y 坐标列表。我想根据每个坐标在图中的位置分配一个权重。
例如:如果一个点位于周围有很多其他节点的地方,则它位于高密度区域,因此具有更高的权重。
我能想到的最直接的方法是在每个点周围绘制单位半径的圆,然后计算其他点是否位于其中,然后使用函数为该点分配权重。但这似乎很原始。
我看过 pySAL 和 NetworkX,但看起来它们可以处理图表。我在图中没有任何边,只有节点。
标准解决方案是使用 KDE(核密度估计)。
在网上搜索:“KDE Estimation”你会发现大量的链接。在 Google 中输入:KDE Estimation ext:pdf
另外,Scipy 有 KDE,请按照http://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.gaussian_kde.html 操作。那里有工作示例代码;)
如果您有很多点,您可以使用KDTree更有效地计算最近邻:
import numpy as np
import scipy.spatial as spatial
points = np.array([(1, 2), (3, 4), (4, 5), (100,100)])
tree = spatial.KDTree(np.array(points))
radius = 3.0
neighbors = tree.query_ball_tree(tree, radius)
print(neighbors)
# [[0, 1], [0, 1, 2], [1, 2], [3]]
tree.query_ball_tree返回points
最近邻居的索引(的)。例如,[0,1]
(在索引 0 处)表示points[0]
并且points[1]
在radius
距离之内points[0]
。[0,1,2]
(在索引 1 处)表示points[0]
,points[1]
并且points[2]
在radius
距离内points[1]
。
frequency = np.array(map(len, neighbors))
print(frequency)
# [2 3 2 1]
density = frequency/radius**2
print(density)
# [ 0.22222222 0.33333333 0.22222222 0.11111111]
是的,你确实有边,它们是节点之间的距离。在您的情况下,您有一个带有加权边的完整图。
只需导出从每个节点到其他节点的距离(这会为您O(N^2)
提供时间复杂度),然后使用节点和边作为您找到的这些方法之一的输入。
尽管您的问题似乎是一个分析问题而不是其他任何问题;您应该尝试对您的数据运行一些聚类算法,例如K-means
,根据距离函数对节点进行聚类,您可以在其中简单地使用欧几里得距离。
该算法的结果正是您所需要的,因为您将拥有紧密元素的集群,您将知道为每个组分配了哪些元素以及分配了多少元素,并且您将能够根据这些值,生成要分配给每个节点的系数。
这里值得指出的唯一问题是您必须确定要创建多少个clusters
-- 。k-means, k-clusters
您最初倾向于在每个点周围画一个圆并计算该圆中其他点的数量是一个很好的选择,正如 unutbu 所提到的,KDTree 将是解决此问题的一种快速方法。
这可以通过 PySAL 轻松完成,它在后台使用 scipy 的 kdtree。
import pysal
import numpy
pts = numpy.random.random((100,2)) #generate some random points
radius = 0.2 #pick an arbitrary radius
#Build a Spatial Weights Matrix
W = pysal.threshold_continuousW_from_array(pts, threshold=radius)
# Note: if your points are in Latitude and Longitude you can increase the accuracy by
# passing the radius of earth to this function and it will use arc distances.
# W = pysal.threshold_continuousW_from_array(pts, threshold=radius, radius=pysal.cg.RADIUS_EARTH_KM)
print W.cardinalities
#{0: 10, 1: 15, ..... }
如果您的数据在 Shapefile 中,只需将 threshold_continuousW_from_array 替换为 threshold_continuousW_from_shapefile,有关详细信息,请参阅文档。