(57)【要約】【課題】移動体データから、場所および軌跡の両方にフォーカスした分析結果を取得する。【解決手段】クラスタリング装置１０は、所定の区域を、複数のパターンで複数の区域に分割し、複数のパターンごとに複数の区域のそれぞれについて、データ点の移動方向間の角度を基に、区域を、密集エリア区域と共通移動軌跡区域に分類する。そして、クラスタリング装置１０は、区域ごとに、データ点の位置間の距離およびデータ点の移動方向間の角度の両方に基づく尺度を用いてクラスタリングを行う。そして、クラスタリング装置１０は、クラスタリングの結果に基づいて、各パターンのコストを計算し、最もコストが小さいパターンを選択する。【選択図】図１
2018028823.tif 000002
【特許請求の範囲】
【請求項１】
所定の区域を、複数のパターンで、複数の区域に分割する分割部と、
前記複数のパターンごとに、前記複数の区域のそれぞれについて、区域内におけるデータ点の移動方向間の角度を基に、区域内のデータ点が交差する傾向の大きさを示す値を計算し、前記複数の区域のうち前記値が所定値以上である区域を第１の区域に分類し、前記複数の区域のうち前記値が所定値以上でない区域を第２の区域に分類する分類部と、
前記第１の区域に分類された区域ごとに、前記データ点の位置間の距離および前記データ点の移動方向間の角度の両方に基づく第１の尺度を用いて、区域内のデータ点のクラスタリングを行い、前記第２の区域に分類された区域ごとに、前記データ点の位置間の距離および前記データ点の移動方向間の角度の両方に基づく第２の尺度を用いて、区域内のデータ点のクラスタリングを行うクラスタリング部と、
前記複数のパターンごとに、前記クラスタリング部によるクラスタリングの結果に基づいて、区域の数、区域の大きさ、区域内のデータ点の数、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第１のコストを計算する計算部と、
前記複数のパターンのうち、前記第１のコストが最も小さいパターンを最適解として選択する選択部と、
を有することを特徴とするクラスタリング装置。
【請求項２】
前記計算部は、前記選択部によって最適解として選択されたパターンである前回最適パターンに含まれる区域ごとに、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第２のコストを比較し、
前記分割部は、前記第２のコストが最も大きい区域を、複数のパターンで、複数の区域にさらに分割し、
前記選択部は、前記複数のパターンのうち前記第１のコストが最も小さいパターンである今回最適パターンと前記前回最適パターンとから、前記第１のコストが小さい方のパターンを最適解として選択し、前記今回最適パターンを最適解として選択した場合、前記分割部に前記今回最適パターンを与え、さらに処理を実行させることを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
前記分類部は、移動方向間の角度とπ／２との差が所定値以下であるデータ点の組み合わせの数の、移動方向間の角度とπ／２との差が前記所定値より大きいデータ点の組み合わせの数に対する比が１以上である場合、前記区域を前記第１の区域に分類し、前記比が１より小さい場合、前記区域を前記第２の区域に分類し、
前記クラスタリング部は、２つのデータ点の位置間の距離の短さ、および移動方向間の角度の正弦値に比例する尺度を前記第１の尺度とし、２つのデータ点の位置間の距離の短さ、および移動方向間の角度の余弦値に比例する尺度を前記第２の尺度としてクラスタリングを行うことを特徴とする請求項１または２に記載のクラスタリング装置。
【請求項４】
クラスタリング装置で実行されるクラスタリング方法であって、
所定の区域を、複数のパターンで、複数の区域に分割する分割工程と、
前記複数のパターンごとに、前記複数の区域のそれぞれについて、区域内におけるデータ点の移動方向間の角度を基に、区域内のデータ点が交差する傾向の大きさを示す値を計算し、前記複数の区域のうち前記値が所定値以上である区域を第１の区域に分類し、前記複数の区域のうち前記値が所定値以上でない区域を第２の区域に分類する分類工程と、
前記第１の区域に分類された区域ごとに、前記データ点の位置間の距離および前記データ点の移動方向間の角度の両方に基づく第１の尺度を用いて、区域内のデータ点のクラスタリングを行い、前記第２の区域に分類された区域ごとに、前記データ点の位置間の距離および前記データ点の移動方向間の角度の両方に基づく第２の尺度を用いて、区域内のデータ点のクラスタリングを行うクラスタリング工程と、
前記複数のパターンごとに、前記クラスタリング工程によるクラスタリングの結果に基づいて、区域の数、区域の大きさ、区域内のデータ点の数、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第１のコストを計算する計算工程と、
前記複数のパターンのうち、前記第１のコストが最も小さいパターンを最適解として選択する選択工程と、
を含んだことを特徴とするクラスタリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置およびクラスタリング方法に関する。
【背景技術】
【０００２】
従来、移動体データを対象とした分析技術が知られている。従来の分析技術は、例えば、個々の移動体にフォーカスした技術と複数の移動体全体にフォーカスした技術とに分類される。また、従来の分析技術は、移動体が移動する場所にフォーカスした技術と移動体の詳細な軌跡にフォーカスした技術とに分類される。
【０００３】
個々の移動体および場所にフォーカスした技術として、例えば、移動体の各通過点での滞留時間とＰＯＩ（Point  of  interest）情報を用いて滞留場所を推定する技術が知られている。また、移動体全体および場所にフォーカスした技術として、例えば、複数の移動体が通過した密度の高い場所を求める技術が知られている。
【０００４】
また、個々の移動体および軌跡にフォーカスした技術として、例えば、マップをメッシュに分け、詳細軌跡に基づくメッシュ間の遷移確率から目的地を予測する技術が知られている。また、移動体全体および軌跡にフォーカスした技術として、例えば、移動体の軌跡を重回帰混合正規分布モデルに当てはめ、同じモデルに含まれる軌跡を共通移動ルートとして検出する技術が知られている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Martin  Ester,  Hans-Peter  Kriegel,  Jorg  Sander,  and  Xiaowei  Xu:  “A  density-based  algorithm  for  discovering  clusters  in  large  spatial  databases  with  noise,”  KDD,  pp.226-231,  1996.
【非特許文献２】熊谷  雄介、  今井  良太、  松林  達史:  “非負値複合テンソル因子分解を用いた訪日外国人観光客の回遊行動分析,”  IBISML,  2015.
【非特許文献３】Scott  Gaffney,  and  Padhraic  Smyth:  “Trajectory  Clustering  with  Mixtures  of  Regression  Models,”  KDD,  pp.63-72,  1999.
【非特許文献４】Jae-Gil  Lee,  Jiawei  Han,  Kyu-Young  Whang:  “Trajectory  clustering:  a  partition-and-group  framework,”  SIGMOD,  pp.593-604,  2007.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来の技術には、移動体データから、場所および軌跡の両方にフォーカスした分析結果を取得することができない場合があるという問題があった。例えば、点の密度が高い場所を求める技術では、軌跡にフォーカスした分析結果を取得することができない場合があった。また、例えば、同じ重回帰混合正規分布モデルに含まれる軌跡を共通移動ルートとして検出する技術では、場所にフォーカスした分析結果を取得することができない場合があった。
【課題を解決するための手段】
【０００７】
本発明のクラスタリング装置は、所定の区域を、複数のパターンで、複数の区域に分割する分割部と、前記複数のパターンごとに、前記複数の区域のそれぞれについて、区域内におけるデータ点の移動方向間の角度を基に、区域内のデータ点が交差する傾向の大きさを示す値を計算し、前記複数の区域のうち前記値が所定値以上である区域を第１の区域に分類し、前記複数の区域のうち前記値が所定値以上でない区域を第２の区域に分類する分類部と、前記第１の区域に分類された区域ごとに、前記データ点の位置間の距離および前記データ点の移動方向間の角度の両方に基づく第１の尺度を用いて、区域内のデータ点のクラスタリングを行い、前記第２の区域に分類された区域ごとに、前記データ点の位置間の距離および前記データ点の移動方向間の角度の両方に基づく第２の尺度を用いて、区域内のデータ点のクラスタリングを行うクラスタリング部と、前記複数のパターンごとに、前記クラスタリング部によるクラスタリングの結果に基づいて、区域の数、区域の大きさ、区域内のデータ点の数、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第１のコストを計算する計算部と、前記複数のパターンのうち、前記第１のコストが最も小さいパターンを最適解として選択する選択部と、を有することを特徴とする。
【０００８】
本発明のクラスタリング方法は、クラスタリング装置で実行されるクラスタリング方法であって、所定の区域を、複数のパターンで、複数の区域に分割する分割工程と、前記複数のパターンごとに、前記複数の区域のそれぞれについて、区域内におけるデータ点の移動方向間の角度を基に、区域内のデータ点が交差する傾向の大きさを示す値を計算し、前記複数の区域のうち前記値が所定値以上である区域を第１の区域に分類し、前記複数の区域のうち前記値が所定値以上でない区域を第２の区域に分類する分類工程と、前記第１の区域に分類された区域ごとに、前記データ点の位置間の距離および前記データ点の移動方向間の角度の両方に基づく第１の尺度を用いて、区域内のデータ点のクラスタリングを行い、前記第２の区域に分類された区域ごとに、前記データ点の位置間の距離および前記データ点の移動方向間の角度の両方に基づく第２の尺度を用いて、区域内のデータ点のクラスタリングを行うクラスタリング工程と、前記複数のパターンごとに、前記クラスタリング工程によるクラスタリングの結果に基づいて、区域の数、区域の大きさ、区域内のデータ点の数、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第１のコストを計算する計算工程と、前記複数のパターンのうち、前記第１のコストが最も小さいパターンを最適解として選択する選択工程と、を含んだことを特徴とする。
【発明の効果】
【０００９】
本発明によれば、移動体データから、場所および軌跡の両方にフォーカスした分析結果を取得することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、第１の実施形態に係るクラスタリング装置の構成の一例を示す図である。
【図２】図２は、クラスタリング装置に入力される移動体データの一例を示す図である。
【図３】図３は、方向の算出方法を説明するための図である。
【図４】図４は、変換後の移動体データの一例を示す図である。
【図５】図５は、移動体データを基に作成される図の一例である。
【図６】図６は、クラスタリング装置の処理について説明するための図である。
【図７】図７は、分割のパターンの一例を示す図である。
【図８】図８は、密集エリアクラスタの傾向を説明するための図である。
【図９】図９は、共通移動軌跡クラスタの傾向を説明するための図である。
【図１０】図１０は、クラスタリング結果の一例を示す図である。
【図１１】図１１は、第１の実施形態に係るクラスタリング装置の処理の流れを示すフローチャートである。
【図１２】図１２は、プログラムが実行されることによりクラスタリング装置が実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１１】
［第１の実施形態の構成］
以下に、本願に係るクラスタリング装置およびクラスタリング方法の実施形態を図面に基づいて詳細に説明する。なお、この実施形態により本発明が限定されるものではない。まず、図１を用いて、第１の実施形態に係るクラスタリング装置の構成について説明する。図１は、第１の実施形態に係るクラスタリング装置の構成の一例を示す図である。図１に示すように、クラスタリング装置１０は、入力部１１、出力部１２、制御部１３および記憶部１４を有する。
【００１２】
入力部１１は、例えば、移動体データの入力を受け付ける。入力部１１は、例えば、マウスやキーボード等の入力装置である。出力部１２は、画面の表示等により、データを出力する。出力部１２は、例えば、クラスタリングの結果を表示するディスプレイ等の表示装置である。
【００１３】
制御部１３は、クラスタリング装置１０全体を制御する。制御部１３は、例えば、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等の電子回路や、ＡＳＩＣ（Application  Specific  Integrated  Circuit）、ＦＰＧＡ（Field  Programmable  Gate  Array）等の集積回路である。また、制御部１３は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部１３は、各種のプログラムが動作することにより各種の処理部として機能する。例えば、制御部１３は、変換部１３１、分割部１３２、分類部１３３、クラスタリング部１３４、計算部１３５および選択部１３６を有する。
【００１４】
記憶部１４は、ＨＤＤ（Hard  Disk  Drive）、ＳＳＤ（Solid  State  Drive）、光ディスク等の記憶装置である。なお、記憶部１４は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ、ＮＶＳＲＡＭ（Non  Volatile  Static  Random  Access  Memory）等のデータを書き換え可能な半導体メモリであってもよい。記憶部１４は、クラスタリング装置１０で実行されるＯＳ（Operating  System）や各種プログラムを記憶する。さらに、記憶部１４は、プログラムの実行で用いられる各種情報を記憶する。
【００１５】
図２を用いて、移動体データについて説明する。図２は、クラスタリング装置に入力される移動体データの一例を示す図である。移動体データは、移動体の位置および移動方向に関する情報を含んだデータである。なお、図２に示す移動体データは、東京大学の人の流れプロジェクトの人流データ（参考ＵＲＬ：http://bdm.change-jp.com/?p=1705）の一部である。人流データは、国や地方自治体等で実施するパーソントリップ調査データから推定した各都市圏周辺の人の流れデータである。人流データには、日別に、各時刻における各ユーザの位置の経度、緯度等の属性が含まれる。また、この場合、ユーザが移動体である。
【００１６】
例えば、図２の１行目のデータは、ユーザＩＤが１であるユーザが、２０１３／７／１  ９：４５：００に、緯度が３５．６８３８４５１３、経度が１３９．８９９１３３７である位置にいたことを示している。なお、ユーザＩＤはユーザを識別するＩＤである。
【００１７】
変換部１３１は、クラスタリング装置１０に入力された移動体データを、所定の形式のデータに変換する。例えば、図３に示すように、変換部１３１は、入力された移動体データを、ユーザごとに時系列に並べ、緯度および経度の変化に基づいて方向を算出する。図３は、方向の算出方法を説明するための図である。
【００１８】
ここで、点ｉｄは、ユーザの各時刻における位置を識別するＩＤである。例えば、点ｉｄが１であるデータ点の位置の緯度は３５．６８３８４５１３、経度は１３９．８９９１３３７である。また、例えば、点ｉｄが２であるデータ点の位置の緯度は３５．６８２４３２８７、経度は１３９．７７３５７２８である。また、位置が同じであっても、ユーザが異なる場合は、異なる点ｉｄが設定されるようにしてもよい。
【００１９】
例えば、変換部１３１は、図３の１行目および２行目のデータを用いて、ユーザＩＤが１であるユーザの、点ｉｄが１であるデータ点の位置における方向を算出する。また、図３の３行目のデータには、後に続く位置のデータが存在しないため、変換部１３１は、図３の３行目のデータを削除し、ユーザＩＤが１であるユーザの、点ｉｄが３であるデータ点の位置における方向を算出しない。
【００２０】
図４は、変換後の移動体データの一例を示す図である。図４に示すように変換後の移動体データには、点ｉｄ、緯度、経度および方向が含まれる。また、例えば、図４に示すように、方向は角度で表される。例えば、点ｉｄが１であるデータ点の位置の緯度は３５．６８３８４５１３、経度は１３９．８９９１３３７、方向はπ／３である。
【００２１】
図５は、移動体データを基に作成される図の一例である。図５は、図４に示す変換後の移動体データに含まれる各点ｉｄに対応したデータを、地図上にプロットしたものである。図５に示すように、移動体の各点ｉｄに対応したデータは、矢印で表される。図５の矢印の根本の位置は各データの緯度および経度に対応し、矢印の向きは各データの方向に対応している。
【００２２】
なお、移動体データの変換は、クラスタリング装置１０以外の装置によって行われるようにしてもよい。また、クラスタリング装置１０によるクラスタリングに適合されるデータが入力される場合、変換部１３１による変換処理は行われなくてもよい。
【００２３】
以降の処理を、図６を用いて説明する。図６は、クラスタリング装置の処理について説明するための図である。クラスタリング装置１０は、イテレーションによって処理を行う。まず、初回のイテレーションの処理について説明し、その後、２回目以降の処理について説明する。なお、クラスタリング装置１０は、初回の処理のみを行うこととしてもよい。
【００２４】
［初回の処理］
まず、図６の（１−１）に示すように、分割部１３２は、移動体データの対象である領域のうち全領域を分析対象の領域として選択する。以降、分割部１３２が選択した領域を区域とよぶ。次に、図６の（１−２）に示すように、分割部１３２は、区域を、複数のパターンで、複数の区域に分割する。分割部１３２は、例えば、図７に示すように、全領域を所定のサイズのセルに分割しメッシュ化したうえで、所定の緯度を縦線、所定の経度を横線として区域を分割する。図７は、分割のパターンの一例を示す図である。図７に示すように、分割部１３２は、例えば、３×３のセルからなる区域を、４つのパターンで分割する。
【００２５】
ところで、密集エリアは、例えば、駅やショッピングモール等の多くの人が集まる施設が存在するエリアである。一方、共通移動軌跡は、例えば、幹線道路等の、多くの人が利用するルートである。
【００２６】
従来、密集エリアは、例えば移動体の各通過点での密度に基づいて決定されていた。また、従来、共通移動軌跡は、移動体の移動方向等を考慮した軌跡の類似度に基づいて決定されていた。このように、密集エリアおよび共通移動軌跡は、密度や方向といった、それぞれ異なる尺度で決定されていた。第１の実施形態では、クラスタリング装置１０は、密集エリアおよび共通移動軌跡をクラスタとして捉え、同一の尺度を用いて、区域内に密集エリアクラスタまたは共通移動軌跡クラスタを生成する。
【００２７】
図８に示すように、密集エリアクラスタでは、データ点が交差する傾向、すなわち、データ点間の距離が近く、データ点の移動方向が様々である傾向が大きい。図８は、密集エリアクラスタの傾向を説明するための図である。また、共通移動軌跡クラスタでは、データ点が交差する傾向が小さい。つまり、図９に示すように、共通移動軌跡クラスタでは、データ点が一定の方向に移動する傾向が大きい。図９は、共通移動軌跡クラスタの傾向を説明するための図である。なお、データ点とは、移動体の位置および移動方向が定義されたデータである。データ点の詳細については後述する。
【００２８】
これより、データ点間の距離およびデータ点の移動方向は、密集エリアクラスタおよび共通移動軌跡クラスタの両方に共通した尺度であることがいえる。また、移動方向傾向の違いにより、密集エリアおよび共通移動軌跡クラスタを区別できることがいえる。そこで、分類部１３３は、データ点の移動方向を基に、分割部１３２による分割のパターンごとに区域を分類する。具体的には、分類部１３３は、複数のパターンごとに、複数の区域のそれぞれについて、区域内におけるデータ点の移動方向間の角度を基に、区域内のデータ点が交差する傾向の大きさを示す値を計算し、複数の区域のうち値が所定値以上である区域を第１の区域に分類し、複数の区域のうち値が所定値以上でない区域を第２の区域に分類する。ここで、第１の区域は、密集エリア区域である。また、第２の区域は、共通移動軌跡区域である。
【００２９】
ここで、移動体データのうち、あるユーザについての移動体データを、それぞれの要素が緯度と経度とで表される位置座標、および角度で表される移動方向を持つ系列｛ｐ１，ｐ２，…，ｐｎ｝で表す。ここで、データ点は、当該系列の各要素である。また、データ点ｐｉの移動方向は、ｐｉ→ｐｉ＋１と表す。データ点は点ｉｄで識別されるので、図４の点ｉｄが１であるデータ点をｐ１とすると、ｐ１の位置座標は（３５．６８３８４５１３，１３９．８９９１３３７）であり、ｐ１の移動方向ｐ１→ｐ２はπ／３である。
【００３０】
分類部１３３は、区域内の全てのデータ点のペアについて、移動方向によって生成される角度θを算出する。θの範囲は０≦θ≦πとする。例えば、分類部１３３は、ｐｉとｐｊの移動方向によって生成される角度θを、ｐｉ→ｐｉ＋１とｐｊ→ｐｊ＋１との差を０≦θ≦πの範囲で表したものとすることができる。例えば、ｐｉ→ｐｉ＋１−ｐｊ→ｐｊ＋１＝π／２である場合、分類部１３３はθ＝π／２とする。また、例えば、ｐｉ→ｐｉ＋１−ｐｊ→ｐｊ＋１＝３π／２である場合、分類部１３３はθ＝π／２とする。また、例えば、ｐｉ→ｐｉ＋１−ｐｊ→ｐｊ＋１＝−π／３である場合、分類部１３３はθ＝π／３とする。
【００３１】
そして、分類部１３３は、算出したθのうち、π／４≦θ≦３π／４となるθの数が、０≦θ＜π／４∨３π／４＜θ≦πとなるθの数より多い区域を第１の区域、すなわち密集エリア区域に分類する。また、分類部１３３は、算出したθのうち、０≦θ＜π／４∨３π／４＜θ≦πとなるθの数が、π／４≦θ≦３π／４となるθの数以上である区域を第２の区域、すなわち共通移動軌跡区域に分類する。
【００３２】
つまり、分類部１３３は、θとπ／２との差が４／π以下であるペアの数の、θとπ／２との差が４／πより大きいデータ点の組み合わせの数に対する比が１以上である場合、区域を密集エリア区域に分類し、比が１より小さい場合、区域を共通移動軌跡区域に分類する。
【００３３】
このように、分類部１３３は、π／４≦θ≦３π／４となるθの数と０≦θ＜π／４∨３π／４＜θ≦πとなるθの数との比を、区域内のデータ点が交差する傾向の大きさを示す値としている。つまり、密集エリア区域、すなわちπ／４≦θ≦３π／４となるθの数が多い区域には、交差するデータ点が多いことになる。
【００３４】
一方、共通移動軌跡区域、すなわち０≦θ＜π／４∨３π／４＜θ≦πとなるθの数が多い区域には、交差するデータ点が少なく、移動方向が一致するデータ点、または移動方向が正反対であるデータ点が多いことになる。このような場合、当該区域には、上り方面と下り方面を有するルートが存在することが考えられる。
【００３５】
クラスタリング部１３４は、第１の区域に分類された区域ごとに、データ点の位置間の距離およびデータ点の移動方向間の角度の両方に基づく第１の尺度を用いて、区域内のデータ点のクラスタリングを行い、第２の区域に分類された区域ごとに、データ点の位置間の距離およびデータ点の移動方向間の角度の両方に基づく第２の尺度を用いて、区域内のデータ点のクラスタリングを行う。
【００３６】
クラスタリング部１３４は、第１の区域、すなわち密集エリア区域に分類された区域について、式（１）によってデータ点ｐｉとデータ点ｐｊとの関係を表す第１の尺度ｄｉｓｔＤを算出し、ｄｉｓｔＤに基づいて区域内の各データ点のクラスタリングを行う。以降、第１の尺度ｄｉｓｔＤを密集エリア距離とよぶ。ただし、δをスケール因子、θをｐｉ→ｐｉ＋１とｐｊ→ｐｊ＋１によって生成される角度、ＥＤ（ｐｉ，ｐｊ）をデータ点ｐｉとデータ点ｐｊの位置座標間のユークリッド距離とし、θの範囲を０≦θ≦πとする。
【００３７】
【数１】
2018028823.tif 000003
【００３８】
また、クラスタリング部１３４は、第２の区域、すなわち共通移動軌跡区域に分類された区域について、式（２）によってデータ点ｐｉとデータ点ｐｊとの関係を表す第２の尺度ｄｉｓｔＴを算出し、ｄｉｓｔＴに基づいて区域内の各データ点のクラスタリングを行う。以降、第２の尺度ｄｉｓｔＴを共通移動軌跡距離とよぶ。ただし、式（１）と同様に、δをスケール因子、θをｐｉ→ｐｉ＋１とｐｊ→ｐｊ＋１によって生成される角度、ＥＤ（ｐｉ，ｐｊ）をデータ点ｐｉとデータ点ｐｊの位置座標間のユークリッド距離とする。また、式（２）ではθの範囲を０≦θ≦π／２とする。
【００３９】
【数２】
2018028823.tif 000004
【００４０】
式（１）より、２点の位置座標のユークリッド距離が０に近いほど、また、移動方向によって生成される角度がπ／２に近いほど、密集エリア距離の値は最大値である１に近くなる。つまり、密集エリア距離は、２つのデータ点の位置間の距離の短さ、および移動方向間の角度の正弦値に比例する尺度である。
【００４１】
一方、式（２）より、２点の位置座標のユークリッド距離が０に近いほど、また、移動方向によって生成される角度が０に近いほど、共通移動軌跡距離の値は最大値である１に近くなる。つまり、共通移動軌跡距離は、２つのデータ点の位置間の距離の短さ、および移動方向間の角度の余弦値に比例する尺度である。
【００４２】
例えば、クラスタリング部１３４は、最小距離の閾値Ｍｉｎｄｉｓｔ、および最小密度の閾値Ｍｉｎｄｅｎｓｉｔｙが与えられるとき、密集エリア区域については密集エリア距離を用いて、共通移動軌跡区域については共通移動軌跡距離を用いて、非特許文献１に記載された密度ベースのクラスタリング手法によってクラスタリングを行うことができる。なお、クラスタリング部１３４のクラスタリングの手法は、上記手法に限られず、データ点の位置間の距離およびデータ点の移動方向間の角度の両方に基づく尺度を用いた任意のクラスタリング手法とすることができる。また、クラスタリング部１３４によるクラスタリングの結果は、各データ点がどのクラスタに含まれるかによって表される。このとき、いずれのクラスタにも含まれないデータ点が存在する場合があり、そのようなデータ点をノイズとよぶ。
【００４３】
図６の（１−３）は、クラスタリング部１３４による分割のパターンごとのクラスタリング結果を表している。図６の（１−３）の曲線で囲まれた領域は、密集エリア区域のクラスタを示している。また、図６の（１−３）の矢印は、共通移動軌跡区域のクラスタを示している。つまり、図６の（１−３）の各分割のパターンにおける太線で囲まれた区域内の、曲線で囲まれたデータ点の塊は、密集エリアクラスタである。また、図６の（１−３）の各分割のパターンにおける太線で囲まれた区域内の、矢印で囲まれたデータ点の塊は、共通移動軌跡クラスタである。
【００４４】
計算部１３５は、複数のパターンごとに、クラスタリング部１３４によるクラスタリングの結果に基づいて、区域の数、区域の大きさ、区域内のデータ点の数、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第１のコストを計算する。
【００４５】
計算部１３５は、各分割のパターンについて、第１のコストとしてＭＤＬコストを計算する。ＭＤＬコストとは、モデル選択基準であるＭＤＬ（minimum  description  length）を基にした方法によって計算される。また、ＭＤＬコストは、各分割のパターンのクラスタリング結果を評価するスコアである。なお、ＭＤＬは、式（３）に示すように、２つのコスト関数の組み合わせにより表現される。
【００４６】
【数３】
2018028823.tif 000005
【００４７】
例えば、データの圧縮モデルを選択する際の基準としてＭＤＬが用いられる場合、Ｃｏｓｔ（Ｈ）は圧縮モデルＨを表現するコストである。このとき、圧縮モデルがシンプルであるほど、Ｃｏｓｔ（Ｈ）は小さくなる。一方、Ｃｏｓｔ（Ｄ│Ｈ）は圧縮の質、すなわちモデルＨによりデータＤを表現するためのコストである。つまり、データと、データに割り当てられたモデルとの適合度が大きいほど、Ｃｏｓｔ（Ｄ│Ｈ）は小さくなる。ＭＤＬでは、この二つのコストの総計が一番小さなものを選び、少ない符号でデータを表現する最適なデータ圧縮を達成する。
【００４８】
まず、計算部１３５による計算に用いられるＣｏｓｔ（Ｈ）に含まれる値は、下記の通り定義される。
生成された区域の個数ｎ：ｌｏｇ＊（ｎ）  ビット
各区域  ni  におけるセルの数ｎｃ：Σｎｉ＝１ｌｏｇ＊（ｎｃ）  ビット
各区域  ni  におけるデータ点の数ｎｐ：Σｎｉ＝１ｌｏｇ＊（ｎｐ）  ビット
ここで、ｌｏｇ＊（ｘ）はユニバーサル符号長であり、ｌｏｇ＊（ｘ）＝ｌｏｇ２（２．８６５）＋ｌｏｇ２（ｘ）＋ｌｏｇ２ｌｏｇ２（ｘ）＋…と表すことができる。
【００４９】
クラスタリング部１３４によるクラスタリングによって、各区域に、クラスタの集合Ｃ＝｛ｃ１，ｃ２，…ｃｍ｝とＫ個のノイズとが生成されるとして、まず、計算部１３５は、式（４）に示すようにエントロピー符号を計算する。
【００５０】
【数４】
2018028823.tif 000006
【００５１】
ここで、式（４）のｑｉは、事象ｉの生起確率を表す。データ集合に表した事象の数が多いほど、また、各事象の生起確率が均等であるほど、データを表現するための最低限の符号が長くなり、エントロピー符号が大きくなる。一方、データ集合に表した事象の数が少ないほど、また、各事象の生起確率に偏りがあるほど、データを表現するための最低限の符号が短くなり、エントロピー符号が小さくなる。
【００５２】
そこで、計算部１３５は、生成される同種類のクラスタと個々のノイズを単独の事象とみなし、各区域内のデータ点ｐｉを表現するための最低限の符号長コストを式（５）により計算する。
【００５３】
【数５】
2018028823.tif 000007
【００５４】
ここで、｜ｃｉ｜はクラスタｃｉに含まれるデータ点の数、ｍはクラスタの数、ｋはノイズの数とする。区域内に生成されるクラスタの数やノイズとして判断されるデータ点の数が少ないほど、Ｅｐｉの値は小さくなる。このことは、各区域に含まれるデータ点をノイズの少ない１個のクラスタで表すことに寄与する。
【００５５】
そして、計算部１３５は、区域内の全てのデータ点を表現する符号長コストＥｎｉを、Ｅｎｉ＝ｎｐ・Ｅｐｉ、分割された区域の個数をｎとして、データ領域における全てのデータ点を表現するためのコストＣｏｓｔ（Ｄ｜Ｈ）を、Ｃｏｓｔ（Ｄ｜Ｈ）＝Σｎｉ＝１Ｅｎｉとして計算する。
【００５６】
各区域内の全てのデータ点を表現するコストＥｎｉは、その区域に対する再分割の必要性を示している。Ｅｎｉが大きい区域は、推定した種類のクラスタによって、区域における全てのデータ点を表現するのは適切ではないことを意味し、区域の再分割と細分された区域におけるデータ点に対する種類の再推定を行うことによって、より質の高いクラスタリング結果を得ることができる。
【００５７】
以上より、計算部１３５は、候補解Ｚ＝｛｛Ｃ，ｋ｝｜｛ｎ，｛ｎｃ｝，｛ｎｐ｝｝が与えられたときの符号長コストＣｏｓｔ（Ｄ，Ｈ）を式（６）のように計算する。
【００５８】
【数６】
2018028823.tif 000008
【００５９】
選択部１３６は、複数のパターンのうち、第１のコストが最も小さいパターンを最適解として選択する。すなわち、図６の（１−４）に示すように、Ｃｏｓｔｔ−１（Ｄ，Ｈ）を、第１のコストが最も小さい分割のパターンのコストとする。図６の（１−４）の破線で囲まれたパターンは、Ｃｏｓｔｔ−１（Ｄ，Ｈ）決定の一例である。なお、ｔ−１は何回目のイテレーションであるかを示している。ここで説明しているのは初回のイテレーション処理なので、ｔ−１は、例えば１とすることができる。
【００６０】
［２回目以降の処理］
ここまで、イテレーションの初回の処理について説明した。ここで、２回目以降のイテレーションの処理について説明する。計算部１３５は、選択部１３６によって最適解として選択されたパターンである前回最適パターンに含まれる区域ごとに、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第２のコストを比較する。第２のコストは、前述のＥｎｉである。例えば、２回目のイテレーションの処理では、計算部１３５は、初回の処理で選択されたパターンの区域ごとに、Ｅｎｉを比較する。
【００６１】
分割部１３２は、第２のコストが最も大きい区域を、複数のパターンで、複数の区域にさらに分割する。例えば、２回目のイテレーションの処理では、図６の（２−２）に示すように、分割部１３２は、Ｅｎｉが最も大きかった区域、すなわち、図６の（２−１）の左側の区域をさらに分割する。
【００６２】
また、例えば、イテレーションの２回目の処理では、図６の（２−３）に示すように、クラスタリング部１３４はさらにクラスタリングを行う。そして、計算部１３５は、さらにＣｏｓｔ（Ｄ，Ｈ）を計算する。
【００６３】
選択部１３６は、複数のパターンのうち第１のコストが最も小さいパターンである今回最適パターンと前回最適パターンとから、第１のコストが小さい方のパターンを最適解として選択し、今回最適パターンを最適解として選択した場合、分割部１３２に今回最適パターンを与え、さらに処理を実行させる。以降、各イテレーションにおける最適解をローカル最適解とよぶ。例えば、イテレーションの２回目の処理では、選択部１３６は、図６の（２−４）に示すように、Ｃｏｓｔｔ（Ｄ，Ｈ）が、ｔ回目のローカル最適解の第１のコストとする。図６の（２−４）の破線で囲まれたパターンは、Ｃｏｓｔｔ（Ｄ，Ｈ）決定の一例である。
【００６４】
そして、Ｃｏｓｔｔ（Ｄ，Ｈ）がＣｏｓｔｔ−１（Ｄ，Ｈ）より大きい場合、選択部１３６は、ｔ−１回目のローカル最適解を選択する。そして、クラスタリング装置１０は、選択部１３６によって選択されたパターンを、最終的な最適解として、出力部１２に出力させる。
【００６５】
一方、Ｃｏｓｔｔ（Ｄ，Ｈ）がＣｏｓｔｔ−１（Ｄ，Ｈ）より小さい場合、選択部１３６は、ｔ回目のローカル最適解を選択する。そして、選択部１３６は、分割部１３２に選択したパターンを与え、さらに処理を実行させる。
【００６６】
初回および２回目を例に挙げて説明した上記処理は、ｔ−１回目とｔ回目に拡張することができる。つまり、クラスタリング装置１０は、ｔ回目のイテレーションとｔ−１回目のイテレーションで選ばれたローカル最適解のＭＤＬコストを比較する。そして、ｔ回目のイテレーションのコストがｔ−１回目のイテレーションのコストより小さい場合、クラスタリング装置１０は、ｔ回目のイテレーションの結果を保留し、ｔ＋１回目のイテレーションを実行する。
【００６７】
一方、ｔ回目のイテレーションのコストがｔ−１回目のイテレーションのコストより大きい場合、クラスタリング装置１０は、ｔ−１回目のイテレーションの結果を最終的な最適解とする。
【００６８】
図１０を用いて、クラスタリング装置１０によるクラスタリング結果について説明する。図１０は、クラスタリング結果の一例を示す図である。図１０の例では、前述の人流データを用い、セルサイズを２００ｍ×２００ｍ、最小距離の閾値Ｍｉｎｄｉｓｔを、区域内全てのデータ点のうち自身との距離が上位２５個であるデータ点との距離の平均値の平均、最小密度の閾値Ｍｉｎｄｅｎｓｉｔｙを、区域内全てのデータ点の密度の平均に設定しクラスタリングを行った際のクラスタリング結果である。
【００６９】
図１０の四角形で囲まれた領域は、分割部１３２によって分割された区域である。また、曲線で囲まれたデータ点の塊は、密集エリアクラスタである。破線の四角形で囲まれた区域は、密集エリア区域である。また、白抜きの矢印で囲まれたデータ点の塊は、共通移動軌跡クラスタである。実線の四角形で囲まれた区域は、共通移動軌跡区域である。また、灰色の矢印はノイズである。
【００７０】
図１０に示すように、密集エリアクラスタはランドマーク（東京ドーム、飯田橋駅）とマッチしていた。また、共通移動軌跡クラスタは道路（国道等）とマッチしていた。図１０のように出力を行うことで、所定の日時に所定の領域にいた人々が、どこに集まっているか、どこから集まっているか、といったことを確認することができる。
【００７１】
［第１の実施形態の処理］
図１１を用いて、クラスタリング装置１０の処理の流れについて説明する。図１１は、第１の実施形態に係るクラスタリング装置の処理の流れを示すフローチャートである。図１１に示すように、分割部１３２は、セルサイズを決定し、データ領域をメッシュ化する（ステップＳ１０１）。
【００７２】
次に、分割部１３２は、分析対象である区域を選択し、複数のパターンで区域の分割を行う（ステップＳ１０２）。分類部１３３は、データ点の移動方向の角度を基に、区域を密集エリア区域と共通移動軌跡区域とに分類する（ステップＳ１０３）。クラスタリング部１３４は、密集エリア区域および共通移動軌跡区域のいずれにおいても、データ点の位置間の距離およびデータ点間の移動方向の角度を基に、データ点に対するクラスタリングを行う（ステップＳ１０４）。
【００７３】
計算部１３５は、クラスタリング部１３４によるクラスタリングの結果を基にＭＤＬコストを計算し、ローカル最適解のコストＣｏｓｔｔ（Ｄ，Ｈ）を決定する（ステップＳ１０５）。ここで、Ｃｏｓｔｔ（Ｄ，Ｈ）≦Ｃｏｓｔｔ−１（Ｄ，Ｈ）である場合（ステップＳ１０６、Ｙｅｓ）、クラスタリング装置１０は、ステップＳ１０２に処理を戻し、さらに処理を繰り返す。また、Ｃｏｓｔｔ（Ｄ，Ｈ）≦Ｃｏｓｔｔ−１（Ｄ，Ｈ）でない場合（ステップＳ１０６、Ｎｏ）、クラスタリング装置１０は、クラスタリング結果を出力し（ステップＳ１０７）、処理を終了する。
【００７４】
［第１の実施形態の効果］
分割部１３２は、所定の区域を、複数のパターンで、複数の区域に分割する。分類部１３３は、複数のパターンごとに、複数の区域のそれぞれについて、区域内におけるデータ点の移動方向間の角度を基に、区域内のデータ点が交差する傾向の大きさを示す値を計算し、複数の区域のうち値が所定値以上である区域を第１の区域に分類し、複数の区域のうち値が所定値以上でない区域を第２の区域に分類する。また、クラスタリング部１３４は、第１の区域に分類された区域ごとに、データ点の位置間の距離およびデータ点の移動方向間の角度の両方に基づく第１の尺度を用いて、区域内のデータ点のクラスタリングを行い、第２の区域に分類された区域ごとに、データ点の位置間の距離およびデータ点の移動方向間の角度の両方に基づく第２の尺度を用いて、区域内のデータ点のクラスタリングを行う。また、計算部１３５は、複数のパターンごとに、クラスタリング部１３４によるクラスタリングの結果に基づいて、区域の数、区域の大きさ、区域内のデータ点の数、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第１のコストを計算する。また、選択部１３６は、複数のパターンのうち、第１のコストが最も小さいパターンを最適解として選択する。
【００７５】
このように、第１の実施形態では、密集エリア区域および共通移動軌跡区域を、データ点の位置間の距離およびデータ点の移動方向間の角度という同一の尺度を用いて評価しているため、密集エリアクラスタおよび共通移動軌跡クラスタの同時検出が可能となり、移動体データから、場所および軌跡の両方にフォーカスした分析結果を取得することができるようになる。
【００７６】
計算部１３５は、選択部１３６によって今回のローカル最適解として選択されたパターンに含まれる区域ごとに、クラスタの数およびいずれのクラスタにも含まれなかったデータ点の数に比例する第２のコストを比較する。分割部１３２は、第２のコストが最も大きい区域を、複数のパターンで、複数の区域にさらに分割する。選択部１３６は、今回のローカル最適解と前回のローカル最適解とから、第１のコストが小さい方のパターンを最適解として選択し、今回のローカル最適解を最適解として選択した場合、分割部１３２に今回のローカル最適解与え、さらに処理を実行させる。このように、最適解が見つかるまで処理を繰り返すことで、より精度の高い分析結果を得ることが可能になる。
【００７７】
分類部１３３は、移動方向間の角度とπ／２との差が所定値以下であるデータ点の組み合わせの数の、移動方向間の角度とπ／２との差が所定値より大きいデータ点の組み合わせの数に対する比が１以上である場合、区域を第１の区域に分類し、比が１より小さい場合、区域を第２の区域に分類する。これにより、密集エリア区域と共通移動軌跡区域におけるデータ点の移動傾向の違いをクラスタリングに反映させることができる。
【００７８】
クラスタリング部１３４は、２つのデータ点の位置間の距離の短さ、および移動方向間の角度の正弦値に比例する尺度を第１の尺度とし、２つのデータ点の位置間の距離の短さ、および移動方向間の角度の余弦値に比例する尺度を第２の尺度としてクラスタリングを行う。これにより、データ点の位置間の距離およびデータ点の移動方向の角度という同一の尺度を用いつつ、密集エリア区域および共通移動軌跡区域のそれぞれに属するデータ点に適合した方法でクラスタリングを行うことが可能となる。
【００７９】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００８０】
また、本実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８１】
［プログラム］
一実施形態として、クラスタリング装置１０は、パッケージソフトウェアやオンラインソフトウェアとして上記のクラスタリングを実行するクラスタリングプログラムを所望のコンピュータにインストールさせることによって実装できる。例えば、上記のクラスタリングプログラムを情報処理装置に実行させることにより、情報処理装置をクラスタリング装置１０として機能させることができる。ここで言う情報処理装置には、デスクトップ型またはノート型のパーソナルコンピュータが含まれる。また、その他にも、情報処理装置にはスマートフォン、携帯電話機やＰＨＳ（Personal  Handyphone  System）等の移動体通信端末、さらには、ＰＤＡ（Personal  Digital  Assistant）等のスレート端末等がその範疇に含まれる。
【００８２】
また、クラスタリング装置１０は、ユーザが使用する端末装置をクライアントとし、当該クライアントに上記のクラスタリングに関するサービスを提供するクラスタリングサーバ装置として実装することもできる。例えば、クラスタリングサーバ装置は、移動体データを入力とし、クラスタリング結果を出力とするクラスタリングサービスを提供するサーバ装置として実装される。この場合、クラスタリングサーバ装置は、Ｗｅｂサーバとして実装することとしてもよいし、アウトソーシングによって上記のクラスタリングに関するサービスを提供するクラウドとして実装することとしてもかまわない。
【００８３】
図１２は、プログラムが実行されることによりクラスタリング装置が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【００８４】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【００８５】
ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、クラスタリング装置１０の各処理を規定するプログラムは、コンピュータにより実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、クラスタリング装置１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤにより代替されてもよい。
【００８６】
また、上述した実施形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【００８７】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００８８】
１０  クラスタリング装置
１１  入力部
１２  出力部
１３  制御部
１４  記憶部
１３１  変換部
１３２  分割部
１３３  分類部
１３４  クラスタリング部
１３５  計算部
１３６  選択部
【図１】
2018028823.tif 000009
【図２】
2018028823.tif 000010
【図３】
2018028823.tif 000011
【図４】
2018028823.tif 000012
【図５】
2018028823.tif 000013
【図６】
2018028823.tif 000014
【図７】
2018028823.tif 000015
【図８】
2018028823.tif 000016
【図９】
2018028823.tif 000017
【図１０】
2018028823.tif 000018
【図１１】
2018028823.tif 000019
【図１２】
2018028823.tif 000020