人の群衆のためのクラスタ分析

Question

私は多数のユーザ（数十万人）からの位置データを持っています。私は現在の位置といくつかの履歴データポイント（1時間後の分データ）を保存します。

誕生日パーティーなどの自然なイベントの周りに集まっている人を検出するにはどうすればいいですか？小規模の人でも（5人から始めると言わせてください）、検出されるはずです。 このアルゴリズムは、ほとんどの場合リアルタイムで（または少なくとも1分に1回）動作して、群衆が発生したときにそれを検出する必要があります。

私は多くのクラスタ分析アルゴリズムを検討しましたが、そのほとんどは悪い選択肢のようです。彼らはあまりにも長い（私はO（n^3）とO（2^n）を見た）か、あらかじめいくつのクラスターがあるかを知る必要があります。

誰かが私を助けることができますか？ありがとうございました！

Answer 1

各ユーザーを自分のクラスターにする。彼女が別のユーザーに距離Rになると、新しいクラスターを形成し、人が離れると再び分離する。人々の

• 数が
• T
よりも彼らはタイマー大きいため、同じ場所にある
Nよりも大きい当事者が（公共交通機関を示している可能性があります）に移動されていない：ときあなたはあなたのイベントを持っています それは、公共サービスの建物（病院、学校など）に位置していない
• （他の条件の良い数）

1分は、たくさんのです何十万という人々にさえもそれを達成するための時間です。素朴な実装では、それはO（n^2）ですが、各個人の位置を比較する際にはポイントがありません。近くにあるものだけが考えられます。最初の近似では、「世界」をセクターに分割することができます。これにより、タスクを並行しやすくすることが容易になります。より多くのユーザー？いくつかのノードを追加してダウンスケールしてください。

「質量」と重心に関して考えてみてください。まず第一に、何かをイベントとしてマークしないでください。 15台確かに、位置は不正確ですが、イベントの場合、イベントの中心を中心に平均する必要があります。あなたのクラスターが実質的な質量を増やすことなくどんな方向に成長しても、それは正しいとは限りません。 DBSCAN（密度ベースのクラスタリング）のようなメソッドを見て、良いインスピレーションは物理的なシステムからも取ることができます。イジングモデル（温度に関して考えると、

投稿者のコメントに記載されている「1連鎖問題」を回避するにはどうすればよいですか？一つのアイデアは、「質量」と重心の観点から考えることです。まず第一に、何かをイベントとしてマークしないでください。 15台確かに、位置は不正確ですが、イベントの場合、イベントの中心を中心に平均する必要があります。あなたのクラスターが実質的な質量を増やすことなくどんな方向に成長しても、それは正しいとは限りません。 DBSCAN（密度ベースのクラスタリング）のようなメソッドを見て、良いインスピレーションは物理的なシステムからも、イジングモデル（ここでは温度の面で考えると群衆に加わるために "フリップ"する）から取ることができます。それは新規な問題ではなく、それをカバーする論文（部分的に）があると確信しています。 Is There a Crowd? Experiences in Using Density-Based Clustering and Outlier Detection。

Answer 2

フルクラスタリングではほとんど使用されません。

ちょうど良いデータベースインデックスを使用しています。

現在の位置のデータベースを保持します。

新しい座標を取得するたびに、データベースに希望の半径、たとえば50メートルを照会します。 A 良いインデックスは、小さな半径に対してO（log n）でこれを行います。十分な結果が得られれば、これはイベント、または進行中のイベントに参加している人かもしれません。