点のグルーピング - Shinichi0713/AlgorithmChallenges GitHub Wiki

点群情報からグルーピング

点と点の座標情報を元にグルーピングを行う手法について確認する。

1. K-Means クラスタリング

K-Meansは、事前にクラスタの数を指定して、点をその数のクラスタに分けるアルゴリズムです。

手順：

クラスタの数 k を決める。
k 個のクラスタの中心（セントロイド）をランダムに初期化する。
各点を最も近いセントロイドに割り当てる。
各クラスタのセントロイドを再計算する。
収束するまで3と4を繰り返す。

import numpy as np
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

# サンプルデータ生成
points = np.random.rand(100, 2)

# K-Means クラスタリング
kmeans = KMeans(n_clusters=3)
kmeans.fit(points)
labels = kmeans.labels_

# 結果のプロット
plt.scatter(points[:, 0], points[:, 1], c=labels)
plt.show()

2. DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCANは、密度に基づくクラスタリングアルゴリズムで、クラスタの数を事前に指定する必要がありません。また、ノイズ点（クラスタに属さない点）も検出できます。

手順：

各点について、指定された半径内にある点の数を数える。
半径内の点が指定された閾値以上であれば、その点を「コア点」とする。
コア点から到達可能なすべての点を同じクラスタに割り当てる。
ノイズ点はどのクラスタにも属さない点とする。

import numpy as np
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt

# サンプルデータ生成
points = np.random.rand(100, 2)

# DBSCAN クラスタリング
dbscan = DBSCAN(eps=0.1, min_samples=5)
dbscan.fit(points)
labels = dbscan.labels_

# 結果のプロット
plt.scatter(points[:, 0], points[:, 1], c=labels)
plt.show()

3. Hierarchical Clustering（階層的クラスタリング）

階層的クラスタリングは、クラスタを階層的に分割する方法で、クラスタの数を事前に指定する必要がありません。

手順：

各点を個別のクラスタとして開始する。
最も近い2つのクラスタをマージする。
すべての点が1つのクラスタになるまで2を繰り返す。
デンドログラム（木構造）を用いて適切なクラスタ数を決定する。

import numpy as np
from sklearn.cluster import AgglomerativeClustering
import matplotlib.pyplot as plt

# サンプルデータ生成
points = np.random.rand(100, 2)

# 階層的クラスタリング
hierarchical = AgglomerativeClustering(n_clusters=3)
labels = hierarchical.fit_predict(points)

# 結果のプロット
plt.scatter(points[:, 0], points[:, 1], c=labels)
plt.show()

点情報の境界を多角形で取得するアルゴリズム

凸包（Convex Hull）: 凸包は、平面上の点集合を囲む最小の凸多角形を求めるもので、点情報の境界を取得するのに適しています。 ScipyやShapelyなどのライブラリを使用して簡単に凸包を計算できます。ここでは、Scipyを使用した例を示します。

凸包（Convex Hull）

凸包(convex hull)とは，与えられた点をすべて包含する最小の凸多角形（凸多面体）のこと.

凸包の特徴

点集合Sに含まれる点のうち、ある軸で最小値・最大値を持つ点は凸包に含まれる凸包では凸包内のいかなる二点同士を結んでその線上に点を決めてもそれは凸包の中にある点集合Sについて、凸包上の点を内部に含む３点が存在しない 2次元の凸包は上部凸包(upper hull)と下部凸包(lower hull)に分けることができる

凸包を見つけるアルゴリズムは凸包の点になる候補を見つけていくアルゴルズム

以下ではnは点数、hは凸包に含まれる点数.
・特定の三点を選んでその中に含まれている点を除去を繰り返す
O(n^4)となるシンプルで最も遅い方法.三角形の中に含まれる点は凸包の頂点の候補にはならないため、除去できます.
・ギフト包装法
シンプルで有名な方法.O(nh)で見つけられるが、最悪ケースではO(n^2).凸包の頂点を一つ見つけたら、次に結ぶ点の片方の側に点が存在しないように点の選択を繰り返す方法.
・Grahamの方法
点を円周方向にソートした後に、順に凸包に含まれるかどうかを判定していきます.ソートでO(n*log(n))で判定でO(n)のため、全体としてはO(nlog(n))になります.
・QuickHull
高次元でも使用することのできる凸包アルゴリズム.Quickソートのような動きをして、凸包を求めていく.O(n log(n))だが、最悪ケースではO(n^2)となる.
・分割統治法
小さい点群で凸包を求めてそれを統合していく方法.
・逐次構成法
一点ずつ点を加えていく方法
・Kirkpatrick-Seidelの方法
O(n log(h))な高速な手法. しかしやや複雑な動きをする.
・Chanのアルゴリズム
上記のKirkpatrick-Seidelと同様な方法だがかなりシンプルになっておりこちらもO(n log(h))

Monotone Chain アルゴリズムの概要

点のソート:

点集合を x座標（一次座標）で昇順にソートします。x座標が同じ場合は、y座標（二次座標）で昇順にソートします。

下部凸包の構築:

ソートされた点集合を左から右に走査し、下部凸包を構築します。各点を順に追加し、右回りのターンが発生する場合は、最後に追加した点を削除します。

上部凸包の構築:

ソートされた点集合を右から左に走査し、上部凸包を構築します。各点を順に追加し、右回りのターンが発生する場合は、最後に追加した点を削除します。

凸包の結合:

下部凸包と上部凸包を結合して完全な凸包を得ます。ただし、最初と最後の点は重複するため、片方を削除します。

def monotone_chain(points):
    # 点をx座標、y座標の順にソート
    points = sorted(points)

    # 下部凸包の構築
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    # 上部凸包の構築
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    # 下部凸包と上部凸包を結合（最初と最後の点を削除して重複を避ける）
    return lower[:-1] + upper[:-1]

def cross(o, a, b):
    # ベクトル OA と OB のクロス積を計算
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

# サンプルデータ
points = [(0, 0), (1, 1), (2, 2), (2, 0), (2, 1), (3, 3), (4, 2), (4, 4)]

# 凸包の計算
hull = monotone_chain(points)

# 結果の表示
print("Convex Hull:", hull)

グリッドベースの集約 (Grid-based Aggregation)

グリッドベースの集約は、空間をグリッドに分割し、各グリッド内の点群を集約する手法　　

import numpy as np
import matplotlib.pyplot as plt

# サンプルの点群データを生成
np.random.seed(0)
points = np.random.rand(100, 2)

# グリッドサイズを設定
grid_size = 0.1

# グリッド内の点を集約
grid_dict = {}
for point in points:
    grid_x = int(point[0] // grid_size)
    grid_y = int(point[1] // grid_size)
    grid_key = (grid_x, grid_y)
    if grid_key not in grid_dict:
        grid_dict[grid_key] = []
    grid_dict[grid_key].append(point)

# 各グリッドの中心点を計算
grid_centers = np.array([np.mean(grid_dict[key], axis=0) for key in grid_dict])

# 集約結果をプロット
plt.scatter(points[:, 0], points[:, 1], alpha=0.5)
plt.scatter(grid_centers[:, 0], grid_centers[:, 1], c='red')
plt.show()