写真Artem Svetlov
もっともらしいコルク画像を作成するために、 Mail.Ru Mapsプロジェクトは、交通参加者のGPS追跡に関する大量の情報を処理します。 多くの場合、安全上の理由を含めて、トラックのソースについてほとんど知られていない。 しかし、道路の真の状況を判断するために、私は常にもっと知りたいと思っていました。 少なくとも、ソースマシンの速度が残りのストリームの速度にどの程度対応しているかを理解するため。 この記事では、生のGPSデータストリームから路線車両（バス、トロリーバス、ミニバス、トラム）を抽出する方法に焦点を当てます。
なぜこれが重要なのか
ルート車両は、ほとんどの場合、残りのストリームの速度で移動しません。 もちろん、それらは輸送状況の指標になる可能性がありますが、いくつかの詳細があります：- バスとトロリーバスは、原則として、ルート上に多数の停留所がある独自のスケジュールを持っています。 これは、無料の道路では、バスがストリームよりも意図的に遅く移動し、多くの場合短時間停止することを意味します。 ラッシュアワーでは、バスが7〜10分間隔で運行しているため、バス停のエリアでの流量の減少に関する十分な情報を送信できます。
- 割り当てられたレーンのおかげで、バスは交通の流れよりも速く進むことができます。
- ミニバスドライバーは、多くの場合、規則に反して運転します。
それとは別に、私はほとんど常に、交通量の多い道路の近くまたは中心を通る割り当てられた車線に沿って進む路面電車について説明したいと思います。 したがって、路面電車のトラックは実際には車のトラックと見分けがつきません。
ソースデータ
この記事の目的は、どちらの衛星ナビゲーションシステムが優れているかを比較することではないことを事前に予約します。 現在、ほとんどすべてのクライアントデバイスには、使用可能なすべてのシステムからデータを受信し、一般化された座標を提供するチップが搭載されています。 スペースを節約するために、以降、衛星ナビゲーションシステムを使用して取得したトラック、GPSトラックを呼び出します。はじめに、GPSトラックとは何かを定義しましょう。 GPSトラックは、時間の経過に伴うデバイスの位置の一連の座標です。 残念ながら、トラックを送信する各デバイスについて私たちが知っている唯一のことは、一意の識別番号です。 これらは厳格なプライバシー要件です。
すべてのトラックは性質が異なり、さまざまなサプライヤーからのものです。 この記事では、デバイスが車両に固定されており、定期的にデータを送信する場合を考えます。 この単純化により、トラックを録音しているデバイスが誰かの手にある場合、この誰かがバスに乗って数回停車した場合の状況を考慮できなくなります。
分析の目的は、トラックの一般的なリストから、同じ道路シーケンス（ルート）に沿ってほとんどの時間を移動するトラックを分離することです。
解決方法
まず、最初の連続したトラックを単一のトリップに分割する必要があります。これを相互に比較します。 前述のように、物理的にはマシン上に、数秒ごとに座標を送信するGPSトラッカーがあります。 ほとんどの場合、トラッカーは車のイグニッションがオンになっているときに機能しますが、24時間機能するデバイスがあります。 したがって、トリップセパレーターは、速度が常に0であるか、デバイスがデータを送信しなかった場合に長い時間がかかります。
トラックを旅行に分割する例
これで、各車両について、一定の期間にわたって作成した一連の旅行トラックができました。 その中には、実際の旅行と、座標の決定エラー、企業の閉鎖ゾーン内での移動、「リパーク」などのゴミに起因する疎結合トラックの両方があります。 計算リソースを無駄にしないために、バウンディングボックスの長さが400メートル未満、ポイント数が10未満、地理的広がりが200メートル未満のすべてのトラックをフィルタリングします。 これにより、GPS受信機の大きなランダムエラーにより形成されるアスタリスクトラックが回避されます。
特徴的なアスタリスクトラック
次のタスクは、これらのトラックを相互に比較し、それらが同じルートに沿っているかどうかを判断することです。 これを行うには、最初にすべてのGPSトラックを単一の形式で持ち込み、それらを道路グラフにリンクします。 最後の投稿でバインダーの仕事について書きました。 それ以来、彼はいくつかの変更を受けましたが、基本的な原則は同じままです。 バインディングの出口で、ペアのチェーン（グラフのエッジのID、方向（前方または後方））の形でトラックを取得します。 この段階で、道路グラフに該当しないトラックを除外できます。 これらは、飛行機/ヘリコプター、海中のコンテナ、コンバインのトラックです。 または単に、何らかの理由で道路グラフがない場所に運転した車から。 ここでは、道路グラフとまったく一致しないトラックのみがフィルタリングされることに注意してください。 車が道路グラフを持たない駐車場を離れた後、道路に沿って長時間運転し、道路グラフに接続され、道路の終わりに駐車場に入った場合（再び道路グラフがない場合）、そのようなトラックがカウントされます。
結果のチェーンは、互いに比較するのがはるかに簡単です。 さまざまな比較指標を見て、最終的にレーベンシュタイン指標に焦点を合わせました 。 この場合のアルファベットは、考えられるすべてのエッジと方向のペアのセットです。 したがって、1つのルートから別のルートを取得するために、ルートのエッジの編集数（エッジの追加/削除/置換）としてトラックの「類似性」を数値的に決定する機会を得ました。
次のステップは、ルート上のトラックをグループ化することです。 この問題は、データクラスタリングアルゴリズムによって解決されます。 トラックの「類似性」の1次元メトリックがすでにあるため、最も単純な階層データクラスタリングアルゴリズムである樹状図を使用しました 。 ツリーは、レーベンシュタインの最小距離に基づいて構築され、その後、その枝が壊れ、nを超えるエッジが異なります。 16に等しい最適なnを計算することが不可欠でした。
その結果、同様のルートを格納するクラスターのセットを取得します。 この情報があれば、車両が所定のルートに沿って走行しているかどうかを結論付けることができます。 ルート内のエッジの数に応じて異なるnを使用するアイデアがありましたが、この改善によって検索の品質が向上することはなく、固定のnのままにすることにしました。
当初、ほとんどの車両には両方向に2つのルート（最終から最終）があると考えられていました。 しかし、実際に示されているように、ルートは円形である場合もあれば、複数の部分で構成される場合もあります。
ルート車両は常にルートに沿って移動するとは限りません。 ガレージ、ガソリンスタンドなどへの旅行があります。
ルートから追跡します。 ビューを閉じる
したがって、ほとんどの車両には、トリップが蓄積されるクラスターが少なくとも1つと、複数のサービスクラスターがあります。1回以上のまれなルート（ガレージ、ガソリンスタンドなど）。 得られたデータに基づいて、もう1つの仮説を確認できます。車両ルートとルート比較メトリックがあるため、同じルートで運行している車両を区別できます。 これを行うには、異なる車両の個別のクラスターを取得し、それらを相互に比較する必要があります（さらに、クラスター比較機能は既に階層ツリー実装にあります）。
同じルートに沿って走行する2つの異なるバス
したがって、ルートを改良し、公園内の車両をグループ化できます。