2

クラスターとは、リンクされた重なり合う円のグループを意味します。この画像は、おそらく私が見つけようとしているもののより良いアイデアを提供します：

ここに画像の説明を入力してください

私のデータでは、円は中心点の座標で表されています。オーバーラップを表すペアの中心点のリストを作成するために、すでに衝突検出を実行しました。

pts = [(-2,2), (-2,2), (0,0), (2,1), (6,2), (7,1)]

overlaps = [
    (pts[0], pts[1]),
    (pts[0], pts[2]),
    (pts[1], pts[2]),
    (pts[2], pts[3]),
    (pts[4], pts[5]),
]

これは期待される結果です：

expected_clusters = [
    ((-2,2), (-2,2), (0,0), (2,1)),
    ((6,2), (7,1))
]

実際には、私が使用するデータセットはほぼこのサイズになるので、おそらくスケールアップする必要はありません。しかし、それは私がより最適な解決策を好まないということではありません。

私は自分自身の素朴な解決策を考え出しました。それを答えとして投稿します。しかし、私は他の解決策を見たいと思います。

4

2 に答える 2

5

あなたがしているのは、実際にはクラスター分析ではなく、連結成分分析です。クラスター分析では、多数の個別のポイントを取得して、円を見つけようとします。ただし、初期の近隣にポイントを割り当てることと、重複する近隣を介したクラスタリングベースの到達可能性の組み合わせが、DBSCANのアイデアとその密度ベースのクラスタリングバリアントの中心であることに関心があるかもしれません。

いずれにせよ、円から始めているので、衝突検出を行うと、オーバーラップリストと呼んでいるのは隣接リストであり、クラスターと呼んでいるのは連結成分です。アルゴリズムはかなり単純です。

  1. Lすべてのノード のリストを作成します。
  2. 接続されたコンポーネントの空のリストを作成しますCs
  3. L空ではない 間：
    1. 任意のノードを選択しますN
    2. Cで初期化された連結成分リストを作成しますN
    3. 隣接リストを使用して幅優先または深さ優先のトラバーサルを実行し、遭遇した各ノードを追加します。C
    4. Cに追加Cs
    5. Cからすべてのノードを削除しますL
于 2013-01-30T15:45:24.203 に答える
1

acjohnson55のアルゴリズムを支持して元の応答を編集しました：

center_pts = [(-2,2), (-2,2), (0,0), (2,1), (6,2), (7,1)]

overlapping_circle_pts = [
    (center_pts[0], center_pts[1]),
    (center_pts[0], center_pts[2]),
    (center_pts[1], center_pts[2]),
    (center_pts[2], center_pts[3]),
    (center_pts[4], center_pts[5]),
]

expected_solution = [
    [(-2,2), (-2,2), (0,0), (2,1)],
    [(6,2), (7,1)]
]


def cluster_overlaps(nodes, adjacency_list):
    clusters = []
    nodes = list(nodes)  # make sure we're mutating a copy

    while len(nodes):
        node = nodes[0]
        path = dfs(node, adjacency_list, nodes)

        # append path to connected_nodes
        clusters.append(path)

        # remove all nodes from
        for pt in path:
            nodes.remove(pt)

    return clusters


def dfs(start, adjacency_list, nodes):
    """ref: http://code.activestate.com/recipes/576723/"""
    path = []
    q = [start]

    while q:
        node = q.pop(0)

        # cycle detection
        if path.count(node) >= nodes.count(node):
            continue

        path = path + [node]

        # get next nodes
        next_nodes = [p2 for p1,p2 in adjacency_list if p1 == node]
        q = next_nodes + q

    return path

print cluster_overlaps(center_pts, overlapping_circle_pts)
于 2013-01-30T15:18:17.503 に答える