MyGlobe エンジン

MyGlobe^{エンジンの概要}

MyGlobeエンジンは、iPhone GPSから各ユーザーの移動履歴を取得し分析し、建物

と道を強調し、行動領域を島として表現するユーザーの認知地図を生成するアルゴリズ ムを活用する。はじめに、MY GLOBE^{アプリケーションが、}iPhone^搭載のA-GPS^か ら取得した緯度、経度、精度、時刻の位置情報(^{高度は取得しない})^{をサーバーに送信し、}

蓄積する。

次にサーバーのデータベースに蓄積された位置情報を分析して、滞在時間と訪問回数 と行動領域を推定して、認知地図をレンダリングする。道は滞在の頻度が多い場所が連 続していた場合はそこがよく通る道だと判断してその頻度に応じて道を太くする。

建物はGPSデータを計測しなくなった場所と時間が推定して再び移動する時間までを 建物に滞在した時間として記録してその時間に比例して大きくするが、道と建物ともに 閾値が設定してあり一定の大きさ以上には大きくしない。そして、MyGlobeの認知地図 上の建物の種別は、Web APIとユーザーのつけたタグによって推定される。

行動領域は、ユーザーの全位置情報をK平均法によってクラスタにわけ、そのクラス タの重心からクラスタ内で一番離れているポイントを半径として、円を描き、それを各 重心で繰り返し描画することによって島として表現される。

このようにMyGlobeアプリケーションのアルゴリズムによって生成された認知地図 は、サーバーに保存され、移動履歴が増える毎に更新される。以下に詳細を述べる。

位置情報取得と位置情報の出現頻度の算出

iPhoneから送信された位置情報は、サーバーにインストールされたデータベースエン

ジンであるmysqlを用いて、データベースに蓄積される。この位置情報のうち、精度が 150m以上しか得られていない場合は、データベースには入力されない。このデータベー スに蓄積された位置情報履歴を分析して、地図の構成物である島と道と建物のレンダリ ングのためのデータを生成する。はじめに、この３つの構成物のための共通のデータで ある位置情報の出現頻度を計算する。位置情報の出現頻度とは、記録された各位置情報 の20メートル以内にある他の位置情報の個数である。この位置情報の出現頻度(^以下、

出現頻度)を各位置情報毎に算出する。

島のレンダリング

行動領域は、ユーザーの全位置情報をK平均法によってクラスタにわけ、そのクラス タの重心からクラスタ内で一番離れているポイントを半径として、円を描き、それを各 重心で繰り返し描画することによって島として表現される。ポイントは位置情報の場所 のことである。K平均法によるクラスタリングは、はじめにランダムにk^個の重心(^クラ スタの中心の点)を配置し、全てのポイントを最も近い重心のに割り当てる。なお、K^は 全ポイントを30で除算した数で設定する。この割り当ての後、重心はその重心に割り当 てられた全てのポイントの平均の位置に移動し、再度割り当てを行う。割り当てに変更 が生じなくなるまでこのプロセスを繰り返す。図4.11は、クラスタが２個でポイントが ６個の場合のプロセスを示している。

1. ２つの重心をランダムに配置する。

2. 各ポイントをもっとも近い重心に近づける。この図ではA、B、C、Eが左の重心 に割り当てられ、DとFが右の重心に割り当てられている。

3. それぞれの重心が重心に割り当てられたポイントの平均の位置に移動する。

4. 割り当てを再計算すると、Eは右側の重心に近づいたため、右側のクラスタに移動 している。

5. 再び、それぞれの重心が重心に割り当てられたポイントの平均の位置に移動する。

6. 割り当てに変更が生じなくなったら、クラスタ内の重心から一番遠いポイントを半 径として円を描く。左側のクラスタでは左の重心とCを半径として、右側のクラス タでは右の重心とEを半径として円を描いてる。

このステップを全ポイントで行って島の描画を行っている。尚、このクラスタリングの 方法は『集合知プログラミング』[31](46-48)を参考にした。島のレンダリングはGoogle

Map APIの図形を描画するクラスであるGPolygon^{を利用して実装した。}

図4.10 島のアルゴリズム

図4.11はインプットしたポイントに対する島のアウトプットのレンダリングである。

左図はインプットしたポイントで右図はアウトプットされた島の形である。

道のレンダリング

全位置情報の場所(以下、ポイント)毎に、そのポイント以外の全ポイントと取得時間 と離れている距離と出現頻度の比較を行い、以下の条件を互いに満たすポイントをユー

図4.11 島のレンダリング

ザーが通った道として推定して、そのポイント同士を直線によって繋ぐことによって道 のレンダリングを行う。

• 位置情報の取得時間が連続している。

• ^{離れている距離が}50メートル以内に存在する。

• 出現頻度が近似している。

繋ぐ線の太さは、繋がれた各ポイントの出現頻度の平均によって算出される。各直線 の太さは、出現頻度の平均に比例してレンダリングされる。出現頻度の平均が一定未満 の直線は表示されない。直線の太さには、閾値が設定されており、閾値を超える太さに なる直線は、一定の太さにおさえられる。

道のレンダリングはGoogle Map APIの線を描画するクラスであるGPolyline^を利用 して実装している。

図4.12の例では、円が各ポイントを、円内の数字が出現頻度を表している。左図では、

出現頻度が５で、距離的に近いポイントが直線で結ばれている。距離的に近くても、出 現頻度が違うポイントは直線で結ばれない。右図では、出現頻度に比例して、直線の太 さが太くなることを示している。

図4.13^は、Google Maps上に道を描画した例である。左上から時計まわりに、渋谷、

拡大表示した渋谷、日吉、拡大表示した日吉の地図である。

図 4.12 ^{道生成のアルゴリズム}

図 4.13 ^{道のレンダリングの例}

建物のレンダリング

建物は、滞在時間が一定以上の場所に配置され、その大きさはその滞在時間に比例す る。位置情報が取得されなくなり、再び取得されるまでの時間を、滞在時間とする。位 置情報の取得は、位置が変化しなくなると実行されなくなるように設定している。再び 位置が変化した場合に位置情報の再取得を実行する。滞在時間が３分以上である位置は、

ユーザーが滞在した建物であると推定される。

建物であると推定された位置には、建物アイコンが配置される。建物アイコンは、レス トラン、ファーストフード、居酒屋、コンビニエンスストア、ラーメン、カフェ、学校、

大学、駅、デパート、家、映画館、ホームセンター、書店、ホール、洋服、デパート、音 楽の18^{種類がある。}

配置されるアイコンの種類は、建物推定アルゴリズムによって決められる。建物推定ア ルゴリズムは、MyGlobeサービスのサーバー内部にある建物データベースとリクルート が提供するドコイク?API[29]とサーバーにある建物データベースを利用する。建物デー タベースに経度と緯度情報を問い合わせ、その位置に登録されている建物を検索し、該 当するものがあれば、その建物アイコンを配置する。該当するものがない場合は、ドコ イク?APIを利用する。ドコイク?APIとは、ドコイク?の持つ日本全国の店舗・スポット 情報が登録されいるデータベースを利用できるアプリケーション開発用のWebサービス である。ドコイク?APIに、建物であると推定された位置にある店舗情報を問い合わせ、

その位置に18種類のキーワードに該当する店舗がないかを検索する。このキーワードに 該当する店舗が存在した場合、このキーワードに関連する建物アイコンが、その位置に 配置される。さらに、キーワードに該当する店舗がなかった場合、暫定的にビルのアイ コンが配置される。そして、ユーザーが、違う建物のアイコンに修正する事で、正しい アイコンが配置され、その位置情報とともに建物データベースに新しく登録される。

この建物アイコンの大きさは、滞在時間に比例する。この建物アイコンには、大きさ の閾値が設定されており、一定以上の大きさにはならない。

建物のレンダリングはGoogle Map APIのアイコンを地図上にオーバーレイするクラ

スであるGMarkerを利用して実装した。

図 4.14 ^{建物推定のシステム}

第 5 章