Pandas DataFrame中使用Networkx计算联通组件

Question

操作 根据距离和标签使用连通组件对点进行聚类。

问题 在NetworkX节点属性存储和Pandas DataFrame之间不断切换导致的复杂性。

• 看起来过于复杂
• 查找节点时出现索引/键错误

尝试 使用不同的函数，如Scikit NearestNeighbours，但结果仍然需要不断地移动数据。

问题 是否有更简单的方法执行此连接组件操作？

示例

import numpy as np
import pandas as pd
import dask.dataframe as dd
import networkx as nx
from scipy import spatial

#generate example dataframe
pdf = pd.DataFrame({'x':[1.0,2.0,3.0,4.0,5.0],
                    'y':[1.0,2.0,3.0,4.0,5.0], 
                    'z':[1.0,2.0,3.0,4.0,5.0], 
                    'label':[1,2,1,2,1]}, 
                   index=[1, 2, 3, 4, 5])
df = dd.from_pandas(pdf, npartitions = 2)

object_id = 0
def cluster(df, object_id=object_id):
    # create kdtree
    tree = spatial.cKDTree(df[['x', 'y', 'z']])

    # get neighbours within distance for every point, store in dataframe as edges
    edges = pd.DataFrame({'src':[], 'tgt':[]}, dtype=int)
    for source, target in enumerate(tree.query_ball_tree(tree, r=2)):
        target.remove(source)
        if target:
            edges = edges.append(pd.DataFrame({'src':[source] * len(target), 'tgt':target}), ignore_index=True)

    # create graph for points using edges from Balltree query
    G = nx.from_pandas_dataframe(edges, 'src', 'tgt')

    for i in sorted(G.nodes()):
        G.node[i]['label'] = nodes.label[i]
        G.node[i]['x'] = nodes.x[i]
        G.node[i]['y'] = nodes.y[i]
        G.node[i]['z'] = nodes.z[i]

    # remove edges between points of different classes
    G.remove_edges_from([(u,v) for (u,v) in G.edges_iter() if G.node[u]['label'] != G.node[v]['label']])

    # find connected components, create dataframe and assign object id
    components = list(nx.connected_component_subgraphs(G))
    df_objects = pd.DataFrame()

    for c in components:
        df_object = pd.DataFrame([[i[0], i[1]['x'], i[1]['y'], i[1]['z'], i[1]['label']] for i in c.nodes(data=True)]
                                 , columns=['point_id', 'x', 'y', 'z', 'label']).set_index('point_id')
        df_object['object_id'] = object_id
        df_objects.append(df_object)
        object_id += 1

    return df_objects

meta = pd.DataFrame(np.empty(0, dtype=[('x',float),('y',float),('z',float), ('label',int), ('object_id', int)]))
df.apply(cluster, axis=1, meta=meta).head(10)

- Tom Hemmes

---

你好！很抱歉没有及时回答这个问题。如果你在此期间自己找到了一个好的解决方案，欢迎将其作为答案发布在自己的问题下，因为它可能会帮助未来遇到相同问题的其他人。 - Stef

感谢您的留言，很遗憾我并没有找到更有效的方法来解决这个问题，只能按照当时提供的示例解决方案进行工作。 - Tom Hemmes

当我尝试运行你的代码时，出现了“ValueError: data must be 2 dimensions”的错误。 - biqarboy

Answer 1

您可以使用 scikit-learn 中的 DBSCAN。 当 min_samples=1 时，它基本上会找到连接组件。 它可以使用不同的最近邻算法，并通过参数 algorithm 进行配置（其中之一是 kd-tree）。

我的另一个建议是针对不同的标签分别进行计算。这简化了实现，并允许并行化。

可以按以下方式实现这两个建议：

from sklearn.cluster import DBSCAN

def add_cluster(df, distance):
    db = DBSCAN(eps=distance, min_samples=1).fit(df[["x", "y", ...]])
    return df.assign(cluster=db.labels_)

df = df.groupby("label", group_keys=False).apply(add_cluster, distance)

它应该适用于Pandas和Dask数据框。注意，每个标签的群集ID从0开始，即一个群集由元组 (label, cluster) 唯一标识。

以下是一个使用人工数据的完整示例：

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import DBSCAN

plt.rc("figure", dpi=100)
plt.style.use("ggplot")

# create fake data
centers = [[1, 1], [-1, -1], [1, -1], [-1, 1]]
XY, labels = make_blobs(n_samples=100, centers=centers, cluster_std=0.2, random_state=0)
inp = (
    pd.DataFrame(XY, columns=["x", "y"])
    .assign(label=labels)
    .replace({"label": {2: 0, 3: 1}})
)

def add_cluster(df, distance):
    db = DBSCAN(eps=distance, min_samples=1).fit(df[["x", "y"]])
    return df.assign(cluster=db.labels_)

out = inp.groupby("label", group_keys=False).apply(add_cluster, 0.5)

# visualize
label_marker = ["o", "s"]
ax = plt.gca()
ax.set_aspect('equal')

for (label, cluster), group in out.groupby(["label", "cluster"]):
    plt.scatter(group.x, group.y, marker=label_marker[label])

生成的数据框如下所示： 聚类图如下所示。标签由标记形状指示，颜色表示聚类。

- Anton