シミュレーションプログラムを開発しています。動物 (ヌー) の群れがあり、その群れの中で、群れから離れている 1 匹の動物を見つけることができる必要があります。
下の写真では、緑の点が群れから離れています。早く見つけたいのはこういうところです。
もちろん、その問題を解決するための簡単なアルゴリズムがあります。各ポイントの近傍にあるドットの数を数え、その近傍が空 (0 ポイント) の場合、このポイントが群れから離れていることがわかります。
問題は、このアルゴリズムがまったく効率的でないことです。私は 100 万点を持っていますが、このアルゴリズムを 100 万点のそれぞれに適用すると非常に時間がかかります。
もっと速くなるものはありますか？多分木を使う？
@amit の編集: そのようなケースは避けたいと思います。左隅にある緑色の点のグループが選択されますが、群れから離れているのは 1 匹の動物ではなく、動物のグループであるため、選択すべきではありません。群れから離れた 1 匹の動物のみを探しています (グループではありません)。
最近傍クエリでは、kd ツリーがよく使用されます。これにより、O(n log n) クエリが発生します (1 つのクエリは log(n) x n クエリであり、kd ツリーの構築自体は O(n log n) です)。何百万ものポイントがあり、すでにかなり効率的なライブラリもあります (たとえば、ANN )。
さらに、ANN は「Approximatenearestneighbors」の略で、正確な距離が必要ない場合はさらに高速になります。あなたの場合、最初の最近傍距離が大きいか小さいかだけを検出したいので、かなり高いしきい値を設定すると、さらに高速になります。
そこから、すべての最近傍までの距離分布を決定し、外れ値を見つけることができます。外れ値を決定するためにこれらすべての距離を並べ替えると、O(n log n) になります。
異常検出アルゴリズム(教師なし機械学習の問題)を探していると思います。
アイデアは、残りのインスタンスと比較して異常な「動作」をするインスタンスを見つけることです。
このビデオ (Coursera のオンライン機械学習コースから)で始まる一連のビデオでは、問題と、それに適切に取り組む方法について説明しています。
編集:
より簡単な代替手段は、すべてのポイント (動物) の平均を見つけ、そこから最も遠い動物 (または、あるしきい値からの距離が大きいすべてのポイント
) を「選択」することです。k
複数のグループがある場合は、最初にグループ化することをお勧めします。これを行う 1 つの方法は、k-means クラスタリングを使用し、各グループ (クラスター) に上記のアプローチのいずれかを適用することです。
孤独な動物を探しているので、O(N log N + ab*) O(N log N) に 2 つの凸層を使用できます。ここで、a は最初の船体のサイズで、b は 2 番目の船体のサイズです。船体。
外側 (最初) の船体の動物は、最も近い隣人が十分に離れている場合、「孤立」しています。最近隣は、内側と外側のハル内のそのポイント (同じポイントではない) に最も近いポイントです。アウターハルの場合は、検討しているポイントの左右のポイントまでの距離を確認するだけで済むでしょう。したがって、a(a+b) ではなく、大きな O の a*b
群れの「内側」の動物の 1 つが孤立していると見なされる場合が予想される場合 (この場合、内側とは、外側の船体を構成していない動物を指します)、上記の方法はおそらく機能しません。その場合は、より洗練されたアプローチを使用する必要があります。
また、a + b が N に近い場合は、基本的に O(N^2) になるため、おそらく非効率的です。ただし、その場合、動物が非常に孤立しているとは考えにくいです。
編集：ポイントを追加および削除するだけでポイントが移動する凸包を維持するために使用できる動的な凸包構造があることも指摘する必要があります。それはおそらくリアルタイムの更新に役立つでしょう。
*これは実際には O(N) であり、回転キャリパーを使用しています。
ここに簡単なアイデアがあります。（クラスタリングアプローチ）
x、y 値に基づいて動物をグリッドに配置します。誤って検出された外れ値が必要ない場合は、2 つのグリッドを使用できます。この例では、黒と青の線で示された 2 つのグリッド コンテナーを使用します。
外れ値は次のように定義されます。an animals which is alone in both it's blue and black grid.
グリッド インデックスとグリッドに含まれる動物の間の参照を保持します。
動物を反復し、x、y 値を使用してグリッドに配置します。次に、黒いグリッドを繰り返します。グリッド コンテンツが 1 の場合、黒いグリッド内にある動物を介して青いグリッド参照を見つけます。青いグリッドの内容を確認します。1 の場合、その動物は外れ値です。
実行時間はかなり速いはずです。
n: number of animals
b: size of black grid
動物をグリッドに配置するのはO(n). 黒いグリッドを繰り返すのはO(b)
これによりO(n) + O(b)、情報を構築し、外れ値を特定することができます。
外れ値の特定には時間がかかりO(b)ます。グリッドが十分に小さい場合、これにより非常に高速な実行時間が保証されます。
上の画像は、2 つの外れ値を示しているはずです。
実装は比較的簡単です。グリッド ベースの戦略のバリエーションを試したり、グリッドの異なるレイアウトを使用したり、より多くのグリッド コンテナーを使用したりできます。
編集: このアプローチは、この論文で説明されている距離計算なしのセル法に多少関連しています。http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-r-186.pdf この方法では、すべてのケースで誤って検出された外れ値が除外されるわけではありません。より完全な解決策 (マップ上の動物の考えられるすべての位置) については、セル内で検出された 1 匹の動物から隣接するセルのコンテンツまでの距離計算を追加する必要があります。詳細については、こちらをご覧ください。
三角測量に基づくクラスタリング アプローチを試すことができます。
データセットのDelaunay 三角形分割を形成します。これを行うには、パフォーマンスを提供するCGALやTriangleなどの効率的なアルゴリズムがありますO(|V|*log(|V|))。
セット内の頂点ごとに、接続されたエッジのリストをスキャンして「長さ測定値」を計算し、各頂点の最小エッジ長を記録します。これはする必要がありますO(|V|+|E|)。(平方根を取らないように、辺の長さの 2 乗を使用することもできます!)
上記で計算された「長さ測定値」に基づいて頂点を選択します。これを行う方法は、群れから「遠く離れた」ものをどのように分類するかによって異なります。いくつかの可能性:
簡単なアプローチは、静的な長さの許容値を使用することです。これにより、長さの測定値がこの値を超える場合、頂点は「離れている」と分類されます。これはO(|V|)テストになります。
三角形分割のすべてのエッジの平均エッジ長の係数に基づいて長さの許容値を設定するなど、より複雑なアプローチも可能です。これにより、群れの平均分布で許容値がスケーリングされます。これはO(|V|+|E|)テストになります。
このアプローチの利点は、メインクラスターの外側に小さな「サブグループ」を持つ群れに対して堅牢であることです(2番目の例のように)。
このようなクエリを高速化するには、空間インデックス構造を使用します。
kd-trees、quadtrees、R-trees、grids はオプションのほんの一部です。
このようなインデックス構造では、最近傍をすばやく見つけることができます。最も近い (2 番目に近い、3 番目に近い) 隣人が他の牛よりもはるかに離れている牛は、おそらくあなたが探している外れ値です。
その場合、どのインデックス構造を選択するかがおそらく最大の課題です。シミュレーションを行うので、効率的に更新できるものが最適でしょう。kd-trees はうまく更新できませんが、時々再構築する必要があります (ただし、うまく実装すれば、再構築はかなり高速になるはずです)。R* ツリーはおそらく再構築用に最適化されていますが、実際にはハードディスクに格納することを意図しています。
インメモリ シミュレーションで最高のパフォーマンスを発揮するのは単純にgridだと思います。さまざまなグリッド サイズを試して、最適なものを選択してください。さらに、いくつかの非常に優れた最適化が可能です。牛がいるグリッド セルではn、n-1 個の最も近い牛までの距離は最大で です。sqrt(w*w+h*h)ここで、wとhはグリッド距離です。したがって、「十分な」数の牛がいるセルを実際に見る必要はないかもしれません。nあなたにとっては3まで低いかもしれません。現在、牛が 1 頭だけのグリッド セルでは、外れ値である必要はありません。かなりいっぱいになっている隣接セルの端にある可能性があります。しかし、そのような細胞は多くないはずです。これらの牛は簡単に確認できます。
これはどう：
両方のリスト (X と Y) の候補は確実に分離されています。1 つのリストにのみ存在する候補についてもほぼ確実です。
複雑さは、ソートでは O(n log n)、スキャンでは O(n) です。データ構造を明らかにせずにそれを改善できるとは思えません。
ステップ1は、O（n）の複雑さを持つバケットまたは基数ソートを使用して解決することもできます
これら 2 つの並べ替えられたリストを維持できる場合は、各動物にプロパティ「lonley」を追加します。動物を絶えず反復処理しているため、並べ替えられた X/Y 配列内の現在の位置の左右の要素までの距離を確認することで、'lonley' ステータスを更新するだけです。
以下は単純な線形時間の手順です。
任意の時点で群れが 1 つだけであると仮定すると、動物の位置は 2 変量 (正規?) 分布からのサンプルと考えてください。母集団の平均偏差と標準偏差を線形時間で計算します。平均と各動物の間のマハラノビス距離を線形時間で計算します。t@amitによっても示唆されているように、ある閾値よりも遠い動物は群れではありません。そのしきい値を設定するのはあなた次第です。考えられるオプションの 1 つは、いくつかの例を手作りし、それらを使用して値を微調整することです。これは、マハラノビス距離がスケール不変であるため簡単です。私の直感では、3 が適切な出発点であるということです。平均から 3 標準偏差を超えるものは異常値です。