将相邻细胞及其相同类型的邻居聚集成具有 python 的簇
Agglomerate adjecent cells and their neighbours of the same type to clusters with python
我试图通过将具有相同类型（从 1 到 10 的整数）的相邻单元格（及其邻居）聚集到新的集群中，方法是将它们分配给集群 ID。
一些集群如图所示：
目前，我使用广度优先搜索的缩写来遍历所有邻居及其邻居，然后为所有找到的相同类型的邻居分配一个 cluster-id。由于我的数据集相当大（<300 万个网格单元），此操作在当前形式下需要几天时间。
我 运行 在一个循环中偶然选择单元格直到所有单元格都被分配了一个集群 ID 的函数：
def bfs(df, grid_id):
visited = []
queue = []
visited.append(grid_id)
queue.append(grid_id)
base_pred = df.loc[grid_id, "class"]
while queue:
_ = queue.pop(0)
n, e = get_n_e_index(grid_id)
neighbours = get_same_neighbours(base_pred, n, e, agglo_df)
for neighbour in neighbours:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
queue = queue + get_same_neighbours(base_pred, n, e, agglo_df)
return visited
visited用于分配相同的cluster_id
get_same_neighbours 仅 returns 个具有相同类型的给定单元格的邻居
在我最终验证该方法之前，我得出的结论是它最终会变慢，并且想知道是否有人知道一种足够快的算法来解决这个问题。在线搜索解决方案没有帮助。
编辑: 花了这么长时间不是算法的问题，但我忘了将可能的起始单元格减少到以前没有接触过的单元格.
编辑2:
get_n_e_index 只是将字符串 ID 转换为 North East Integers
def get_same_neighbours(base_class, north, east, df):
neighbours = []
grid_ids = df["ids"].values
for i in [-1, 1, 0]:
for j in [-1, 1, 0]:
n = int(north + i)
e = int(east + j)
grid_id = get_grid_id(n, e)
invalid = [(-1, 1), (1, 1), (0, 0), (1, -1), (-1, -1)] # invalid combinations
if grid_id in grid_ids and (j, i) not in invalid and base_class == df.loc[grid_id, "class"]:
neighbours.append(grid_id)
return neighbours
get_grid_id 将北 (n) 和东 (e) 整数转换为网格单元格的字符串 id。
你犯了几个错误。请注意，对于大约 300 万个单元格，这应该会在大约一秒钟内完成。
正如评论中指出的那样，visited 应该是 O(1) 查找的集合。
其次，如果队列变得很长，queue = queue + get_same_neighbours(base_pred, n, e, agglo_df) 会变得很慢，因为它会创建队列的副本。相反，只需 append 新项目。
最后，你的queue实际上不是一个队列，而是一个列表。因此，弹出第一个元素需要 O(n) 时间。相反，您可以使用队列（python 中的 deque），或者您可以弹出最后一个元素，这会将广度优先搜索转换为深度优先搜索，这应该同样有效。
除此之外，我认为唯一剩下的问题是 graph/grid 表示。将其存储为数据框似乎通常需要解析整个数据框以找到单元格。如果将其存储为多维数组（lists 或 numpy arrays）甚至 dict，您可以在 O(1) 时间内找到任何单元格。因此，我建议首先将数据帧中的数据预处理到另一个易于访问的数据结构中。
我试图通过将具有相同类型（从 1 到 10 的整数）的相邻单元格（及其邻居）聚集到新的集群中，方法是将它们分配给集群 ID。
一些集群如图所示：
目前，我使用广度优先搜索的缩写来遍历所有邻居及其邻居，然后为所有找到的相同类型的邻居分配一个 cluster-id。由于我的数据集相当大（<300 万个网格单元），此操作在当前形式下需要几天时间。
我 运行 在一个循环中偶然选择单元格直到所有单元格都被分配了一个集群 ID 的函数：
def bfs(df, grid_id):
visited = []
queue = []
visited.append(grid_id)
queue.append(grid_id)
base_pred = df.loc[grid_id, "class"]
while queue:
_ = queue.pop(0)
n, e = get_n_e_index(grid_id)
neighbours = get_same_neighbours(base_pred, n, e, agglo_df)
for neighbour in neighbours:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
queue = queue + get_same_neighbours(base_pred, n, e, agglo_df)
return visited
visited用于分配相同的cluster_id
get_same_neighbours 仅 returns 个具有相同类型的给定单元格的邻居
在我最终验证该方法之前，我得出的结论是它最终会变慢，并且想知道是否有人知道一种足够快的算法来解决这个问题。在线搜索解决方案没有帮助。
编辑: 花了这么长时间不是算法的问题，但我忘了将可能的起始单元格减少到以前没有接触过的单元格.
编辑2:
get_n_e_index 只是将字符串 ID 转换为 North East Integers
def get_same_neighbours(base_class, north, east, df):
neighbours = []
grid_ids = df["ids"].values
for i in [-1, 1, 0]:
for j in [-1, 1, 0]:
n = int(north + i)
e = int(east + j)
grid_id = get_grid_id(n, e)
invalid = [(-1, 1), (1, 1), (0, 0), (1, -1), (-1, -1)] # invalid combinations
if grid_id in grid_ids and (j, i) not in invalid and base_class == df.loc[grid_id, "class"]:
neighbours.append(grid_id)
return neighbours
get_grid_id 将北 (n) 和东 (e) 整数转换为网格单元格的字符串 id。
你犯了几个错误。请注意，对于大约 300 万个单元格，这应该会在大约一秒钟内完成。
正如评论中指出的那样，visited 应该是 O(1) 查找的集合。
其次，如果队列变得很长，queue = queue + get_same_neighbours(base_pred, n, e, agglo_df) 会变得很慢，因为它会创建队列的副本。相反，只需 append 新项目。
最后，你的queue实际上不是一个队列，而是一个列表。因此，弹出第一个元素需要 O(n) 时间。相反，您可以使用队列（python 中的 deque），或者您可以弹出最后一个元素，这会将广度优先搜索转换为深度优先搜索，这应该同样有效。
除此之外，我认为唯一剩下的问题是 graph/grid 表示。将其存储为数据框似乎通常需要解析整个数据框以找到单元格。如果将其存储为多维数组（lists 或 numpy arrays）甚至 dict，您可以在 O(1) 时间内找到任何单元格。因此，我建议首先将数据帧中的数据预处理到另一个易于访问的数据结构中。