行（移動経路）クラスタリング機械学習アルゴリズム

Question

私は一連の行データを持っています（2-3の接続点）。 行をその類似点に分類するために使用できる最適な機械学習アルゴリズムは何ですか？ （下の画像）

好ましくは、SciKit-LearnなどのPythonライブラリ。

編集： 私はDBSCANを試してみましたが、2行がある場合、私が直面した問題でした互いに交差し、時にはDBSCAN彼らは別の方向に完全にされているにもかかわらず、一つのグループにそれらを考慮。ここで

は、私がこれまでに見つかったソリューションです：

GeoPathクラスタリングアルゴリズム

ここでの考え方はグループに互いに非常に類似した旅行地理パスをクラスタ化することです。

ステップ：ステップ1からの各クラスタ内の傾き

-2-に基づい

1-クラスタ線、線のcentriodを見つけ、小さなグループ

にK平均 アルゴリズムクラスタにそれらを使用することにより

3-ステップ2の各グループ内で、定義された長さのしきい値内で各行とグループ行の長さを計算します。

結果は類似した勾配を持つ小さなグループのグループになります。同様の移動距離である。

視覚化のスクリーンショットは次のとおりです。 黄色の線はすべて線であり、赤色は一緒に移動するパスのクラスタです。

Answer 1

あなたが解決しようとしている問題は、クラスタリングと呼ばれています。 sklearnのクラスタリングアルゴリズムの概要は、http://scikit-learn.org/stable/modules/clustering.html#clusteringを参照してください。

編集2：あなたの投稿を最初に見たときにKMeansが頭に浮かんだのはKMeansでしたが、コメントからのフィードバックに基づいて、適切ではないようです。代わりにsklearnのDBSCANを試してみてください。

潜在的な変換または追加機能を追加するには、各点のセットに直線を当てて、（スロープ、インターセプト）ペアを使用します。また、各行の重心を使用することもできます。

Answer 2

私は現在のものが不完全だと思うので答えを投げます...そして、私はまた、 "単純なヒューリスティック"のコメントは早すぎると思います。あなたがポイントを集めれば、あなたのダイアグラムが描いているものとは異なる結果になると思います。クラスターは終点近くにあり、あなたは素敵な楕円を得られません。

したがって、データが本当に表示される方法と同様に動作する場合は、私は2/3ポイントの各セットを、基本的にラインをトレースするポイントの長いリストに変えて刺すようにします。 （高密度で実験する必要があります）

結果にHDBSCANを実行して、ビデオ（https://www.youtube.com/watch?v=AgPQ76RIi6A）を参照してクラスタを取得してください。私は "pip install hdbscan"がそれをインストールすると信じています。

新しいサンプルをテストするときは、まずそれを多くの（N）点に分解し、hdbscanモデルに合わせてください。あなたがNポイントで過半数投票のアプローチをとると、 "ライン"が属する最高の全体的なクラスターを得ることができると私は思う。

「シンプルヒューリスティック」のコメントに同意していますが、全体を自動化したい場合はあまり簡単ではありません。 HDBSCANは密度ベースのアルゴリズムのためにこの問題に適していると確信することができます（各サンプルから多くのポイントを作成することに決めた場合）。

これまで私が行っていたライン交差モデルがあると確信しています。そして、その仕事を行うことができるヒューリスティックとルールがあります。おそらく、それらは計算上より経済的です。私の答えはあなたが要求したようにSklearnを使用して有機的なものです...私はそれをテストしていない！私があなたの靴の中にいたならば、私が進んでいく方法です。

編集

私の周りつつい

とライン類似度のカップルは、あなたはおそらくそこに試すことができます。フレッシュとハウスドルフ距離測定。

Frechet：http://arxiv.org/pdf/1307.6628.pdf Hausdorff：distance matrix of curves in python pythonの例です。

すべてのペアワイズ類似点を生成し、それらを類似度および/またはNビンに基づいてグループ化すると、それらのビンを「クラスタ」と呼ぶことができます（ただし、kmeansクラスタではありません）。新しい行ごとに、すべての類似点を生成し、それがどのbinに属しているかを確認します。私はおそらく計算的に集中力の低い私の元のコメントを修正する...あなたはあなたのラインは2または3ポイントしか持っていない運が良いです！