(57)【特許請求の範囲】
【請求項１】
通信端末の経路を導出する情報処理装置であって、
複数の通信端末の時系列に沿った位置情報に基づき、当該複数の通信端末それぞれの移動経路を導出する経路導出手段と、
複数の通信端末の位置情報の相違度に基づいて、同一クラスタに分類する複数の通信端末の位置情報を抽出する抽出手段と、
前記抽出手段によって抽出された前記同一クラスタ内の全ての通信端末の位置情報に基づいて、当該クラスタを代表する代表経路を導出する代表導出手段と、を備え、
前記抽出手段は、前記経路導出手段により導出された各移動経路間の前記位置情報の相違度に基づいて、同一クラスタに分類する複数の通信端末の移動経路を抽出し、
前記代表導出手段は、前記抽出手段によって抽出された前記同一クラスタ内の全ての移動経路の平均経路を、前記代表経路として導出する、情報処理装置。
【請求項２】
前記抽出手段は、前記複数の通信端末それぞれの複数の位置情報を抽出する、請求項１記載の情報処理装置。
【請求項３】
前記代表導出手段は、前記同一クラスタに含まれる各移動経路のうち、他の移動経路それぞれとの相違度の合計が最も小さい移動経路を、前記代表経路として導出する、請求項１又は２記載の情報処理装置。
【請求項４】
前記代表導出手段は、前記代表経路を導出した同一クラスタ内の全ての移動経路それぞれに係る通信端末が、前記代表経路を通過したとみなす、請求項１〜３のいずれか一項記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信端末の移動経路を導出する情報処理装置に関する。
【背景技術】
【０００２】
従来、通信端末を所持した多数のユーザの行動履歴から、各ユーザの移動経路を抽出する装置が知られている。例えば特許文献１の装置では、通信端末の通信開始基地局及び通信終了基地局の位置情報に基づき、ユーザの移動経路を導出している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１５−０８４１９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述したようなユーザの移動経路に関する情報は、例えば観光客の行動パターンの統計を把握する上で有効な情報となる。また、様々な行動パターンを把握する観点から、少数のユーザのみが訪れた場所に関する位置情報を考慮した情報についても知りたいとの要望がある。しかし、少数のユーザのみが訪れた場所に関する位置情報については、当該場所を訪れた個人が特定されるおそれがあるので、移動経路の導出に用いていない。
【０００５】
本発明は上記実情に鑑みてなされたものであり、秘匿性を担保しながら少数のユーザのみが訪れた場所に関する位置情報を考慮した情報を導出することができる情報処理装置に関する。
【課題を解決するための手段】
【０００６】
本発明の一態様に係る情報処理装置は、通信端末の経路を導出する情報処理装置であって、複数の通信端末の位置情報の相違度に基づいて、同一クラスタに分類する複数の通信端末の位置情報を抽出する抽出手段と、抽出手段によって抽出された同一クラスタ内の全ての通信端末の位置情報に基づいて、当該クラスタを代表する代表経路を導出する代表導出手段と、を備える。
【０００７】
この情報処理装置では、位置情報の相違度に基づいて同一クラスタに分類される複数の通信端末の位置情報が抽出され、同一クラスタ内の全ての位置情報に基づき代表経路が導出されている。このように、位置情報の相違度に基づいてクラスタリングが行われることにより、例えば類似する位置情報が同一クラスタに分類される。そして、当該クラスタに含まれる全ての通信端末の位置情報に基づき代表経路が導出されることにより、少数のユーザのみが訪れた場所に関する位置情報も加味された上で代表経路が導出される。このことにより、少数のユーザのみが訪れた場所に関する位置情報をも考慮して代表経路を決定することができる。また、クラスタを代表する代表経路が導出されるので、少数のユーザのみが訪れた場所に関する位置情報が少数のユーザの位置情報としてそのまま出力されることを回避することができ、少数派の位置情報の秘匿性を担保することができる。以上より、本発明によれば、秘匿性を担保しながら、少数のユーザのみが訪れた場所に関する位置情報を考慮した行動パターンを導出することができる。
【０００８】
また、抽出手段は、複数の通信端末それぞれの複数の位置情報を抽出してもよい。同一クラスタに分類する位置情報として複数の通信端末それぞれの複数の位置情報が抽出されることにより、同一クラスタに含まれる位置情報として、互いに関連性の高い位置情報を含めることができる。
【０００９】
また、複数の通信端末の時系列に沿った位置情報に基づき、当該複数の通信端末それぞれの移動経路を導出する経路導出手段を更に備え、抽出手段は、経路導出手段により導出された各移動経路間の位置情報の相違度に基づいて、同一クラスタに分類する複数の通信端末の移動経路を抽出し、代表導出手段は、抽出手段によって抽出された同一クラスタ内の全ての移動経路に基づいて、当該クラスタを代表する代表経路を導出してもよい。このように、同一クラスタ内の各通信端末の移動経路から代表経路が導出されることにより、少数のユーザのみが通過した移動経路を考慮して代表経路を決定することができる。単に位置情報だけでなく、一ユーザの移動経路が考慮されることによって、少数派のユーザの行動パターンを、より好適に導出することができる。
【００１０】
また、代表導出手段は、同一クラスタに含まれる各移動経路のうち、他の移動経路それぞれとの相違度の合計が最も小さい移動経路を、代表経路として導出してもよい。これにより、同一クラスタ内の他の移動経路と最も近似する移動経路が代表経路として導出される。このことで、少数派の移動経路の情報も含めた各移動経路の情報を考慮しながら、代表経路とならなかった移動経路との乖離度合いが最も小さい移動経路を代表経路とすることができる。また、既に導出されている一の移動経路を代表経路とするため、例えば各移動経路の平均経路を代表経路として導出するような場合と比較して導出負荷を小さくすることができる。
【００１１】
また、代表導出手段は、代表経路を導出した同一クラスタ内の全ての移動経路それぞれに係る通信端末が、代表経路を通過したとみなしてもよい。これにより、例えば少数派の移動経路が代表経路とされた場合において、同一クラスタ内の全ての移動経路それぞれに係る通信端末が、当該少数派の移動経路を通過したとみなされることとなる。このことで、当該経路が少数派の経路であることを秘匿することができ、確実に秘匿性を担保することができる。
【発明の効果】
【００１２】
本発明によれば秘匿性を担保しながら少数のユーザのみが訪れた場所に関する位置情報を考慮した情報を導出することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態に係るシーケンス導出装置の機能ブロックを示す図である。
【図２】図１のシーケンス導出装置のハードウェア構成を示す図である。
【図３】事前分類処理の一例を説明するための図である。
【図４】相違度表作成処理の一例を説明するための図である。
【図５】相違度表を示す図である。
【図６】相違度表作成処理の一例を説明するための図である。
【図７】正規化された相違度表を示す図である。
【図８】階層型クラスタリングを説明するための図である。
【図９】正規化された相違度表を示す図である。
【図１０】ヘッドシーケンス導出を説明するための図である。
【図１１】図１のシーケンス導出装置の処理を示すフローチャートである。
【図１２】シーケンス導出処理を示すフローチャートである。
【図１３】事前分類処理を示すフローチャートである。
【図１４】相違度表作成処理を示すフローチャートである。
【図１５】クラスタ作成処理を示すフローチャートである。
【図１６】ヘッドシーケンス作成処理を示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照しながら本発明の実施形態を詳細に説明する。図面の説明において、同一又は同等の要素には同一符号を用い、重複する説明を省略する。
【００１５】
本発明の実施形態に係る情報処理装置は、外国人来訪者等の観光客の行動パターンを調べる際に用いる、各ユーザの移動経路を導出する装置である。以下では、各ユーザが外国人来訪者である例で説明する。
【００１６】
図１は、本発明の実施形態に係るシーケンス導出装置１の機能ブロックを示す図である。シーケンス導出装置１は、通信端末１０の移動経路を導出する情報処理装置である。以下では、通信端末１０の移動経路を「シーケンス」として説明する場合がある。通信端末１０は、ユーザにより用いられ、無線通信によって移動体通信システムに接続し、移動体通信を行う。具体的には、通信端末１０は、携帯電話機等に相当する。通信端末１０は、例えば、通信端末１０のユーザが移動体通信システムの通信事業者と契約することによって移動体通信を行うことが可能になる。図１に示されるように、シーケンス導出装置１は、経路導出部１１と、分類部１２と、代表導出部１３と、を備えている。
【００１７】
図２は、図１のシーケンス導出装置１のハードウェア構成を示す図である。シーケンス導出装置１は、図２に示されるハードウェアによって構成される。図２に示されるように、シーケンス導出装置１は、物理的には、１又は複数のＣＰＵ１１１、主記憶装置であるＲＡＭ１１２及びＲＯＭ１１３、入力デバイスであるキーボード及びマウス等の入力装置１１４、ディスプレイ等の出力装置１１５、ネットワークカード等のデータ送受信デバイスである通信モジュール１１６、半導体メモリ等の補助記憶装置１１７などを含むコンピュータシステムとして構成されている。シーケンス導出装置１の各機能は、図２に示すＣＰＵ１１１、ＲＡＭ１１２等のハードウェア上に１又は複数の所定のコンピュータソフトウェアを読み込ませることにより、ＣＰＵ１１１の制御のもとで入力装置１１４、出力装置１１５、通信モジュール１１６を動作させるとともに、ＲＡＭ１１２や補助記憶装置１１７におけるデータの読み出し及び書き込みを行うことで実現される。
【００１８】
経路導出部１１は、複数の通信端末１０の時系列に沿った位置情報に基づき、複数の通信端末１０それぞれのシーケンスを導出する経路導出手段である。具体的には、経路導出部１１は、位置情報読み込み処理、ユーザ毎分類処理、及び時間毎ソート処理を行うことにより、複数の通信端末１０それぞれのシーケンスを導出している。
【００１９】
位置情報読み込み処理では、経路導出部１１は、複数の通信端末１０から受信した位置情報を読み込む。経路導出部１１は、所定の間隔で位置情報を読み込んでもよいし、オペレータからの指示があった際に位置情報を読み込んでもよい。経路導出部１１は、位置情報に加えて、少なくとも、各位置情報が取得された時刻を示す情報と、位置情報を取得した通信端末１０を示すユーザＩＤと、当該通信端末１０が契約する通信事業者が存する国を示す国コードとを読み込む。経路導出部１１は、位置情報が取得された時刻を示す情報を、位置情報とともに通信端末１０から受信し、読み込む。また、経路導出部１１は、通信端末１０の加入者情報を記録・管理するレジスタ（例えばＶＬＲ（Visitor Location Register）から、ユーザＩＤ及び国コードを読み込む。通信端末１０が外国からの観光客のものである場合においては、当該通信端末１０が日本において最初に位置登録した際に、上述したユーザＩＤ及び国コードを含んだ情報である加入者プロファイルが、ローミング元の国のユーザ情報を管理するレジスタ（例えばＨＬＲ（Home Location Register）からＶＬＲにダウンロードされている。なお、国コードとは具体的には、加入者プロファイルの情報のうち、ＭＳＩＳＤＮのＣＣ（Country Code）から特定される情報である。また、ユーザＩＤとは具体的には、加入者プロファイルの情報のうち加入者情報から特定される情報である。なお、ユーザＩＤは、一方向性関数などを用いて加工されたデータであってもよい。位置情報とは、例えば各通信端末１０において取得されたスポット情報である。スポット情報とは、ある位置を示す情報と対応付けて設定されたスポットを示す情報であり、例えば駅や商業施設、スポーツ会場等を示す情報である。各通信端末１０は、例えば、基地局測位やＧＰＳ（Global Positioning System）測位によって、所定の間隔で位置を示す情報を取得し、当該位置を示す情報から上記スポット情報を導出する。また、経路導出部１１は、通信端末１０以外のスポット情報導出サーバから、通信端末のスポット情報を取得してもよい。スポット情報は、例えば、位置を示す情報と予め対応付けて設定されている。また、スポット情報は、例えば、基地局測位及びＧＰＳ測位等により測位が多くなされた位置を示す情報と自動的に対応付けられて設定されるものであってもよい。この場合には、スポット情報は、上述したスポット情報導出サーバによって自動的に生成される。経路導出部１１は、位置情報読み込み処理において読み込んだ各情報を、互いに紐づけて位置情報ＤＢ（図示せず）に記憶する。
【００２０】
ユーザ毎分類処理では、経路導出部１１は、位置情報読み込み処理において読み込んだ位置情報を、ユーザ毎（通信端末１０毎）に分類する。経路導出部１１は、ユーザＩＤに基づき、位置情報をユーザ毎に分類する。
【００２１】
時間毎ソート処理では、経路導出部１１は、ユーザ毎分類処理によってユーザ毎に分類した位置情報を、更に、時系列に沿ってソート（並び替え）する。経路導出部１１は、当該時間毎ソート処理を行った後に、時間的に連続する各位置情報同士をつなげて、通信端末１０の移動経路であるシーケンスを導出する。経路導出部１１は、導出した各ユーザのシーケンスを、分類部１２に出力する。
【００２２】
分類部１２は、経路導出部１１により導出された各シーケンス間の位置情報の相違度に基づいて、同一クラスタに分類する複数のシーケンスを抽出する。すなわち、分類部１２は、複数の通信端末１０の位置情報の相違度に基づいて、同一クラスタに分類する複数の通信端末１０の位置情報を抽出する抽出手段であり、より詳細には、複数の通信端末１０それぞれの複数の位置情報を抽出する。具体的には、分類部１２は、経路導出部１１により導出された複数のシーケンスのうち、位置情報の相違度が互いに小さいシーケンスを同一クラスタに分類する。相違度が互いに小さいとはすなわち、互いに近似していることを示している。分類部１２は、事前分類処理、相違度表作成処理、及びクラスタ作成処理を行うことにより、複数のシーケンスをクラスタに分類している。
【００２３】
事前分類処理では、分類部１２は、複数のシーケンスをクラスタに分類する前処理として、各シーケンスを同一クラスタに分類され得るシーケンス群に分類する。このため、相違度に基づくクラスタ分類は、同一のシーケンス群内でのみ行われる。分類部１２は、例えば国コード及び入国回数に応じて、各シーケンスをシーケンス群に分類する。当該国コード及び入国回数は、経路導出部１１によって読み込まれた情報から取得される。例えば、入国回数は、上述した位置情報ＤＢ（図示せず）が参照され、同一ユーザについて所定期間（例えば１か月）以上の間隔を空けて記憶された位置情報の数から推定される。
【００２４】
図３は、事前分類処理の一例を説明するための図である。図３においては、実線で示した２本のシーケンスが国コード：米国のユーザに係るシーケンスであり、点線で示した２本のシーケンスが国コード：韓国のユーザに係るシーケンスである。分類部１２は、事前分類処理において、図３（ａ）のように国コード：米国のユーザのシーケンスと、国コード：韓国のユーザのシーケンスとが混在している状態から、図３（ｂ）のように、国コード：米国のユーザのシーケンス群と国コード：韓国のユーザのシーケンス群とに分類する。また、分類部１２は、事前分類処理において、国コード及び入国回数毎のシーケンス群に分類してもよい。ここで、各シーケンス群には、一定数以上のシーケンスが属していることが好ましい。つまり、後述するクラスタ作成処理において、同一シーケンス群のシーケンスのうち相違度が互いに小さいものが同一クラスタに分類されるが、一のシーケンス群に含まれるシーケンスの数が著しく少ない場合には、同一のシーケンス群に相違度が小さいシーケンスが含まれないおそれがあるので、各シーケンス群には一定数以上のシーケンスが属していることが好ましい。例えば、分類部１２は、来訪者数が少ない国コード：ネパール、及び国コード：ウガンダのシーケンスを、同一シーケンス群としてもよい。また、来訪者数が少ない、入国回数２回以上のシーケンスを、同一シーケンス群としてもよい。
【００２５】
相違度表作成処理では、分類部１２は、事前分類処理後のシーケンス群毎に、複数のシーケンスの相違度を導出する。当該相違度は、同一シーケンス群に含まれる全てのシーケンスの組合せ毎に導出される。分類部１２は、各シーケンスの組合せ毎の相違度を、相違度表で管理する。
【００２６】
図４〜図６は、相違度表作成処理の一例を説明するための図である。図４及び図５には２つのシーケンスの相違度を導出する例を示している。図４（ａ）のシーケンスＬ２０は、東京から名古屋、京都を経て大阪に到達するシーケンスを示している。図４（ａ）のシーケンスＬ２１は、東京から岐阜、京都を経て大阪に到達するシーケンスを示している。図４（ｂ）の上段はシーケンスＬ２０を、下段はシーケンスＬ２１を、それぞれ示している。なお、シーケンスＬ２０，Ｌ２１は、それぞれ、１ユーザ（一つの通信端末１０）のシーケンスを示すものであってもよいし、複数ユーザ（複数の通信端末１０）のシーケンスを示すものであってもよい。複数ユーザのシーケンスが同一のシーケンス（例えばシーケンスＬ２０）で示されるとは、シーケンスに含まれる全ての位置情報が一致する通信端末１０が複数存在していることを意味している。分類部１２は、各シーケンスに含まれる各位置情報の相違度を導出することにより、シーケンス全体としての相違度を導出する。位置情報に基づく相違度の導出は、例えばＤＰマッチングにより行うことができる。図４（ｂ）に示す例では、上下段のシーケンスＬ２０，Ｌ２１において、東京、京都、及び大阪が共通している。一方で、上段のシーケンスＬ２０では名古屋を経由しているのに対し、下段のシーケンスＬ２１では岐阜を経由している点で異なる。よって、当該名古屋と岐阜との距離に応じて、Ｌ２０及びＬ２１の相違度が決定している。なお、図４に示す例では、図４（ｂ）下段のシーケンスＬ２１について京都の位置情報が２回あるため上下段のシーケンスで位置情報の数が異なっているが、位置情報の数にかかわらず、各シーケンスの近接する位置情報同士（「京都」同士）が比較される。図５は、シーケンスＬ２０及びシーケンスＬ２１の相違度を示した相違度表ＤＴ１である。相違度表ＤＴ１では、シーケンスＬ２０同士の相違度が「８」であること、シーケンスＬ２１同士の相違度が「１０」であること、並びに、シーケンスＬ２０及びシーケンスＬ２１の相違度が「２８８０１」であることが示されている。当該相違度は、例えば対比した位置情報の距離（ｍ）の差の合計とされる。ただし、対比した際に位置情報が一致する場合であっても、「２」が加算される。このように所定の値を加算することにより、経路の長さ（すなわち位置情報の数）を考慮した、正規化処理（詳細は後述）を円滑に行うことができる。すなわち、シーケンスＬ２０同士の相違度は、シーケンスＬ２０の東京、名古屋、京都、及び大阪が互いに対比され、４箇所全ての位置情報が一致するので、４×２＝「８」とされる。同様に、シーケンスＬ２１同士の相違度は、シーケンスＬ２１の東京、岐阜、京都、京都、及び大阪が互いに対比され、５箇所全ての位置情報が一致するので、５×２＝「１０」とされる。このため、通常、経路の長さが長く位置情報の数が多いシーケンスほど他のシーケンスとの相違度が大きくなり易い。なお、対比した際に位置情報が一致する場合に、例えば「２」が減算されるものであってもよい。この場合には、経路の長さが短く位置情報の数が少ないシーケンスほど他のシーケンスとの相違度が大きくなり易い。また、シーケンスＬ２０及びシーケ��スＬ２１の相違度は、シーケンスＬ２０の東京、名古屋、京都、大阪と、シーケンスＬ２１東京、岐阜、京都、京都、大阪とが対比され、名古屋及び岐阜の距離の差（約２８ｋｍ：２８７９３）と、位置情報が一致する４箇所に応じた値（４×２＝「８」との合計である「２８８０１」とされる。なお、相違度は必ずしも全ての位置情報を対比して導出されなくてもよく、例えばシーケンスにおける任意の数地点を対比して導出されるものであってもよい。
【００２７】
図６には６つのシーケンスの相違度を導出する例を示している。図６（ａ）におけるシーケンスＬ５０〜Ｌ５５それぞれの相違度を示した相違度表ＤＴ５が、図６（ｂ）に示されている。相違度表ＤＴ５からは、シーケンスＬ５０とシーケンスＬ５１とが最も相違度が小さく、シーケンスＬ５２とシーケンスＬ５４とが最も相違度が大きいことがわかる。なお、シーケンスＬ５０〜Ｌ５５は、それぞれ、１ユーザ（一つの通信端末１０）のシーケンスを示すものであってもよいし、複数ユーザ（複数の通信端末１０）のシーケンスを示すものであってもよい。
【００２８】
分類部１２は、相違度表作成処理の一部として、正規化処理を行う。正規化処理とは、シーケンスの長短に関らずシーケンスの相違度を適切に導出するために行う処理である。上述したように、シーケンスの相違度は、シーケンスに含まれる各位置情報の距離の差の合計に応じて決まる。そして、シーケンスを対比した際に位置情報が一致する場合であっても所定値（例えば「２」）が加算されて、シーケンスの相違度が決まる。そのため、通常、経路の長さが長く位置情報の数が多いシーケンスほど他のシーケンスとの相違度が大きくなり易く、反対に、経路の長さが短く位置情報が少ないシーケンスほどいずれのシーケンスとも相違度が小さくなり易い。そこで、分類部１２は、正規化処理として各シーケンスの経路の長さを共通化した上で、各シーケンスの相違度を導出する。シーケンスの経路の長さを共通化するとはすなわち、同一のシーケンス同士を比較した際の相違度の値を、各シーケンス間で共通化することをいう。具体的には、分類部１２は、例えば図６（ｂ）に示された相違度表Ｄ５について正規化処理を行う場合には、まず、各シーケンスのうち、同一のシーケンス同士を比較した際の相違度の値（基準相違度）が最も大きいシーケンスを、基準シーケンスとして特定する。相違度表Ｄ５の例では、シーケンスＬ５２が基準シーケンスとして特定される。つづいて、シーケンスＬ５０，Ｌ５１，Ｌ５３，Ｌ５４，Ｌ５５における他のシーケンスとの相違度の値に、所定の係数が乗算され、正規化処理後の相違度の値が導出される。当該所定の係数は、基準シーケンス（シーケンスＬ５２）の基準相違度を、他の一のシーケンスＬ５０，Ｌ５１，Ｌ５３，Ｌ５４，Ｌ５５の基準相違度により除算した値である。すなわち、例えば、シーケンスＬ５３についての正規化処理後の相違度の値は、他のシーケンスとの相違度の値に、シーケンスＬ５２の基準相違度（１２）をシーケンスＬ５３の基準相違度（６）により除算した値（２）が乗算されることにより導出される。図７は、図６に示す相違度表Ｄ５を正規化処理した相違度表を示している。例えば、図６に示すシーケンスＬ５３とシーケンスＬ５０との相違度の値（２０１９３４）に、所定の係数である２が乗算されて、図７に示すシーケンスＬ５３とシーケンスＬ５０との相違度の値（４０３８６８）が導出されている。
【００２９】
クラスタ作成処理では、分類部１２は、相違度表作成処理で作成された相違度表の各相違度に基づいて、相違度が互いに小さいシーケンスを同一クラスタに分類（クラスタリング）する。クラスタリング手法としては、ウォード法などの階層型クラスタリングや、ｋ−ｍｅａｎｓ法などの非階層型クラスタリング等を用いることができる。階層型クラスタリングは、計算量が多くなるがクラスタ毎の数を決めやすいというメリットがある。一方で、非階層型クラスタリングは、クラスタ毎の数の調整が難しいが計算量が比較的少なくなるというメリットがある。同一のクラスタに分類されるシーケンスの数（Ｋ）は予め定められており、例えばＫ＝３とする。本実施形態では、階層型クラスタリングであるウォード法の計算結果を用いる。
【００３０】
図８は、ウォード法による階層型クラスタリングを説明するための図である。図８において、横軸は図６に示した６つのシーケンスを示しており、縦軸は図７に示した正規化後の各シーケンスの相違度を示している。当該Ｋの値は、様々な行動パターンを導出する観点からは極力小さくされることが好ましい。一方で、秘匿性を担保する観点から、一定値よりも小さくすることができない。このように、種々の行動パターンを導出することと秘匿性とのバランスを考慮し、例えば国が刊行する統計などでは上述したようにＫ＝３とされている。Ｋの値は、例えば５であってもよいし、それより大きな値であってもよい。分類部１２は、クラスタ作成処理として、階層型クラスタリング処理と、Ｋ値ごとのグルーピング処理とを行う。階層型クラスタリング処理では、分類部１２は、シーケンス間の相違度の平方和が最小になるように、各シーケンスを関連付ける。図８において、縦軸の低い位置で関連付けられているシーケンスほど、互いに相違度が小さいことを示している。グルーピング処理では、分類部１２は、Ｋ＝３となるように、関連付けを適宜解消していく。つまり、図８の例では、分類部１２は、シーケンスＬ５３，Ｌ５４，Ｌ５５とシーケンスＬ５０，Ｌ５１，Ｌ５２との関連付けを解消し、それぞれ、別のクラスタとして分類する。分類部１２は、図９に示されるように、同一クラスタ毎に相違度表ＤＴ１００，ＤＴ２００を作成し、当該相違度表ＤＴ１００，ＤＴ２００を代表導出部１３に出力する。なお、図８に示した例では、シーケンス数が６、Ｋ＝３であったため、２つのクラスタにそれぞれＫの値の数（３つ）分だけシーケンスがクラスタリングされたが、例えばシーケンス数が７、Ｋ＝３である場合には、シーケンス数をＫの値で割り切ることができないため、２つのクラスタに３つずつシーケンスをクラスタリングすると１つのシーケンスが余ってしまう。このため、シーケンス数をＫの値で割り切ることができない場合には、いずれかのクラスタにＫの値に＋１した数分だけシーケンスが含まれるようにしてもよい。すなわち、シーケンス数が７、Ｋ＝３である場合には、一方のクラスタに３つのシーケンスをクラスタリングし、他方のクラスタに４つのシーケンスをクラスタリングしてもよい。この場合、上記４つのシーケンスとしては、全てのシーケンスの中で互いの相違度が最も小さい４つのシーケンスを選ぶことが好ましい。これにより、含まれるシーケンスの数を多くしたクラスタにおいても、ヘッドシーケンスとそれ以外のシーケンスとの乖離（誤差）を小さくすることができる。
【００３１】
代表導出部１３は、分類部１２によって分類された同一クラスタに含まれる全てのシーケンスに基づき、当該クラスタを代表するシーケンスであるヘッドシーケンスを導出する。すなわち、代表導出部１３は、分類部１２によって抽出された同一クラスタ内の全ての通信端末１０の位置情報に基づいて、ヘッドシーケンスを導出する代表導出手段である。具体的には、代表導出部１３は、ヘッドシーケンス決定処理と、シーケンス合成処理とを行う。
【００３２】
ヘッドシーケンス決定処理では、代表導出部１３は、同一クラスタに含まれる各シーケンスのうち、同一クラスタに含まれる自身以外の他のシーケンスそれぞれとの相違度の合計が最も小さいシーケンスを、ヘッドシーケンスとして導出する。例えば、図９に示される相違度表ＤＴ１００，ＤＴ２００が、分類部１２から入力されている場合を考える。相違度表においては、同一列の値を合計すると、当該列のシーケンスについて、他のシーケンスそれぞれとの相違度の合計を導出することができる。代表導出部１３は、相違度表ＤＴ１００において、各列のうちシーケンスＬ５０の列の合計値が最も小さくなるため、シーケンスＬ５０をヘッドシーケンスとして導出する。また、代表導出部１３は、相違度表ＤＴ２００において、各列のうちシーケンスＬ５３の列の合計値が最も小さくなるため、シーケンスＬ５３をヘッドシーケンスとして導出する。
【００３３】
シーケンス合成処理では、代表導出部１３は、あるクラスタに含まれる全てのシーケンスそれぞれに係る（それぞれを通過した）通信端末１０が、当該クラスタのヘッドシーケンスとして導出されたシーケンスを通過したとみなし、各シーケンスの合成を行う。各シーケンスの合成を行うとは、各シーケンスを全てヘッドシーケンスに変更することをいう。代表導出部１３は、図６（ａ）に示されたシーケンスＬ５０，Ｌ５１，Ｌ５２を含んだクラスタについてヘッドシーケンスをシーケンスＬ５０と決定すると、図１０に示されるように、シーケンスＬ５０，Ｌ５１，Ｌ５２を全てシーケンスＬ５０とする。同様に、代表導出部１３は、図６（ａ）に示されたシーケンスＬ５３，Ｌ５４，Ｌ５５を含んだクラスタについてヘッドシーケンスをシーケンスＬ５３と決定すると、図１０に示されるように、シーケンスＬ５３，Ｌ５４，Ｌ５５を全てシーケンスＬ５３とする。つまり、例えば各シーケンスＬ５０〜Ｌ５５に係る通信端末１０が１台である場合であれば、代表導出部１３からの出力結果としては、シーケンスＬ５０を通過した通信端末１０が３台、シーケンスＬ５３を通過した通信端末１０が３台とされる。当該代表導出部１３からの出力結果に基づき、ユーザの行動パターンが導出される。
【００３４】
次に、シーケンス導出装置１の処理について、図１１を参照して説明する。図１１は、図１のシーケンス導出装置１の処理を示すフローチャートである。
【００３５】
シーケンス導出装置１では、まず、経路導出部１１により、シーケンス導出処理が行われる（ステップＳ１）。つづいて、分類部１２により、事前分類処理（ステップＳ２）、相違度表作成処理（ステップＳ３）、及びクラスタ作成処理（ステップＳ４）が順次行われる。最後に、代表導出部１３により、ヘッドシーケンス作成処理が行われる（ステップＳ５）。
【００３６】
次に、上述した各処理の詳細について、図１２〜１６を参照して説明する。図１２は、シーケンス導出処理を示すフローチャートである。図１３は、事前分類処理を示すフローチャートである。図１４は、相違度表作成処理を示すフローチャートである。図１５は、クラスタ作成処理を示すフローチャートである。図１６は、ヘッドシーケンス作成処理を示すフローチャートである。
【００３７】
図１２に示されるように、シーケンス導出処理では最初に、経路導出部１１により位置情報読込処理が行われる（ステップＳ１１）。経路導出部１１は、複数の通信端末１０から受信した位置情報を読み込む。つづいて、経路導出部１１によりユーザ毎分類処理が行われる（ステップＳ１２）。経路導出部１１は、位置情報読み込み処理において読み込んだ位置情報を、ユーザ毎（通信端末１０毎）に分類する。最後に、経路導出部１１により時間毎ソート処理が行われる（ステップＳ１３）。経路導出部１１は、ユーザ毎分類処理によってユーザ毎に分類した位置情報を、更に、時系列に沿ってソート（並び替え）する。経路導出部１１は、当該時間毎ソート処理を行った後に、時間的に連続する各位置情報同士をつなげて、通信端末１０の移動経路であるシーケンスを導出する。
【００３８】
図１３に示されるように、事前分類処理では、分類部１２により、指定属性別の分類処理が行われる（ステップＳ２１）。分類部１２は、指定属性（例えば国コード及び入国回数）に応じて、各シーケンスをシーケンス群に分類する。
【００３９】
図１４に示されるように、相違度表作成処理では最初に、分類部１２により作成処理が行われる（ステップＳ３１）。分類部１２は、事前分類処理後のシーケンス群毎に、複数のシーケンスの互いに異なっている度合い（相違度）を導出する。当該相違度は、同一シーケンス群に含まれる全てのシーケンスの組合せ毎に導出される。つづいて、分類部１２により正規化処理が行われる（ステップＳ３２）。分類部１２は、正規化処理として各シーケンスの経路の長さを共通化した上で、各シーケンスの相違度を導出する。
【００４０】
図１５に示されるように、クラスタ作成処理では最初に、分類部１２により階層型クラスタリング処理が行われる（ステップＳ４１）。分類部１２は、シーケンス間の相違度の平方和が最小になるように、各シーケンスを関連付ける。つづいて、分類部１２によりＫ値ごとのグルーピング処理が行われる（ステップＳ４２）。
【００４１】
図１６に示されるように、ヘッドシーケンス作成処理では最初に、代表導出部１３によりヘッドシーケンス決定処理が行われる（ステップＳ５１）。代表導出部１３は、同一クラスタに含まれる各シーケンスのうち、同一クラスタに含まれる自身以外の他のシーケンスそれぞれとの相違度の合計が最も小さいシーケンスを、ヘッドシーケンスとして導出する。つづいて、代表導出部１３によりシーケンス合成処理が行われる（ステップＳ５２）。代表導出部１３は、あるクラスタに含まれる全てシーケンスそれぞれに係る通信端末１０が、当該クラスタのヘッドシーケンスを通過したとみなし、各シーケンスの合成を行う。
【００４２】
上述したシーケンス導出装置１では、時系列に沿った位置情報から複数の通信端末１０のシーケンスが導出され、位置情報の相違度に基づいて同一クラスタに分類される複数のシーケンスが抽出され、同一クラスタ内の全てのシーケンスに基づきクラスタを代表するヘッドシーケンス（代表経路）が導出されている。このように、位置情報の相違度に基づいてクラスタリングが行われることにより、例えば位置情報が類似するシーケンスが同一クラスタに分類される。そして、当該クラスタに含まれる全てのシーケンスに基づきヘッドシーケンスが導出されることにより、例えば少数のユーザのみが訪れた場所に関するシーケンスの情報も加味された上でヘッドシーケンスが導出される。このことにより、少数のユーザのみが訪れた場所に関するシーケンスの情報をも考慮してヘッドシーケンスを決定することができる。具体例について、図６及び図１０を参照して説明する。図６に示したシーケンスＬ５０〜Ｌ５２のヘッドシーケンスとしては、例えば図１０に示されるようにシーケンスＬ５０が選ばれている。ここで、上述したように、シーケンスＬ５０〜Ｌ５２は、それぞれ、１ユーザ（一つの通信端末１０）のシーケンスを示すものであってもよいし、複数ユーザ（複数の通信端末１０）のシーケンスを示すものであってもよい。例えば、Ｌ５０が１ユーザのシーケンスを示しており、シーケンスＬ５１，Ｌ５２が複数ユーザ（例えば１００人）のシーケンスを示している場合が考えられる。シーケンス導出装置１では、同一クラスタに含まれる全てのシーケンスすなわちシーケンスＬ５０〜Ｌ５２に基づきヘッドシーケンスが導出されるので、１ユーザのみが訪れた場所に関するシーケンスであるシーケンスＬ５０も考慮されてヘッドシーケンスが導出される。そして、例えば他のシーケンスそれぞれとの相違度の合計が最も小さいシーケンスがヘッドシーケンスとして選ばれるような場合には、図６に示されるように、シーケンスＬ５１とシーケンスＬ５２とに挟まれるように延びる経路であるシーケンスＬ５０がヘッドシーケンスとして導出される。このように、１ユーザのみが訪れた場所に関するシーケンスであるシーケンスＬ５０がヘッドシーケンスとして導出される可能性があることからも明らかなように、シーケンス導出装置１では、少数のユーザのみが訪れた場所に関するシーケンスの情報をも考慮してヘッドシーケンスを決定することができる。このため、秘匿性の観点から少数のユーザのみが訪れた場所に関する位置情報を用いていなかった従来の方法と比べて、様々な行動パターンを導出することができる。また、複数のシーケンスを代表するヘッドシーケンスとして導出されるので、少数派のシーケンス（少数のユーザのみが訪れた場所に関するシーケンス）が少数派のシーケンスとしてそのまま出力されることを回避することができ、少数派のシーケンスの秘匿性を担保することができる。このようにして導出されたヘッドシーケンスを用いることにより、秘匿性を担保しながら、少数派の移動経路を考慮した行動パターンを導出することができる。
【００４３】
また、分類部１２は、複数の通信端末１０それぞれの複数の位置情報を抽出する。同一クラスタに分類する位置情報として複数の通信端末１０それぞれの複数の位置情報が抽出されることにより、同一クラスタに含まれる位置情報として、互いに関連性の高い位置情報を含めることができる。
【００４４】
また、複数の通信端末１０の時系列に沿った位置情報に基づき、当該複数の通信端末１０それぞれのシーケンスを導出する経路導出部１１を更に備え、分類部１２は、経路導出部１１により導出された各シーケンス間の位置情報の相違度に基づいて、同一クラスタに分類する複数の通信端末１０のシーケンスを抽出し、代表導出部１３は、分類部１２によって抽出された同一クラスタ内の全てのシーケンスに基づいて、当該クラスタを代表するヘッドシーケンスを導出する。このように、同一クラスタ内の各通信端末１０のシーケンスからヘッドシーケンスが導出されることにより、少数のユーザのみが通過したシーケンスを考慮してヘッドシーケンスを決定することができる。単に位置情報だけでなく、一ユーザのシーケンスが考慮されることによって、少数派のユーザの行動パターンを、より好適に導出することができる。
【００４５】
また、代表導出部１３は、同一クラスタに含まれる各シーケンスのうち、他のシーケンスそれぞれとの相違度の合計が最も小さいシーケンスを、ヘッドシーケンスとして導出する。これにより、同一クラスタ内の他のシーケンスと最も近似するシーケンスがヘッドシーケンスとして導出される。このことで、少数派のシーケンスの情報も含めた各シーケンスの情報を考慮しながら、ヘッドシーケンスとならなかったシーケンスとの乖離度合いが最も小さいシーケンスをヘッドシーケンスとすることができる。また、ヘッドシーケンスを導出するに際して、既に導出されている一のシーケンスの中からヘッドシーケンスを選択するため、例えば各シーケンスの平均経路をヘッドシーケンスとするような場合と比較して導出負荷を小さくすることができる。
【００４６】
また、代表導出部１３は、同一クラスタ内の全てのシーケンスそれぞれに係る通信端末１０が、ヘッドシーケンスを通過したとみなす。これにより、例えば少数派のシーケンスがヘッドシーケンスとされたような場合において、同一クラスタ内の全てのシーケンスそれぞれに係る通信端末１０がヘッドシーケンスとして導出された少数派のシーケンスを通過したとみなされることとなる。このことで、当該シーケンスが少数派のシーケンスであることを秘匿することができ、確実に秘匿性を担保することができる。なお、代表導出部１３は、同一クラスタ内の全てのシーケンスそれぞれに係る通信端末１０の数に所定のランダム値（ノイズ値）を加えた数の通信端末１０が、ヘッドシーケンスを通過したとみなしてもよい。当該所定のランダム値は、正の数であってもよいし負の数であってもよい。このようにランダム値を加えることによって、秘匿性をより担保することができる。
【００４７】
以上、本発明の好適な実施形態について説明したが、本発明は上記実施形態に限定されない。例えば、代表導出部１３は、同一クラスタに含まれる各シーケンスのうち、同一クラスタに含まれる自身以外の他のシーケンスそれぞれとの相違度の合計が最も小さいシーケンスを、ヘッドシーケンスとして導出するとして説明したがこれに限定されず、例えば、同一クラスタに含まれる各シーケンスの中からランダムに、ヘッドシーケンスを導出してもよい。この場合には、ヘッドシーケンスの導出負荷をより軽減することができる。また、代表導出部１３は、同一クラスタに含まれるシーケンスの中からヘッドシーケンスを選択するのではなく、例えば各シーケンスの平均経路をヘッドシーケンスとしてもよい。
【００４８】
また、経路導出部１１により複数の通信端末１０それぞれのシーケンスが導出され、代表導出部１３により、同一クラスタ内の全てのシーケンスに基づいて、当該クラスタを代表するヘッドシーケンスが導出されるとして説明したがこれに限定されず、例えば、複数の通信端末１０のシーケンスは導出されずに、単に、複数の通信端末１０の位置情報からヘッドシーケンスが導出されてもよい。
【符号の説明】
【００４９】
１…シーケンス導出装置、１０…通信端末、１１…経路導出部、１２…分類部、１３…代表導出部。
【図１】
0006570869.tif 000002
【図２】
0006570869.tif 000003
【図３】
0006570869.tif 000004
【図４】
0006570869.tif 000005
【図５】
0006570869.tif 000006
【図６】
0006570869.tif 000007
【図７】
0006570869.tif 000008
【図８】
0006570869.tif 000009
【図９】
0006570869.tif 000010
【図１０】
0006570869.tif 000011
【図１１】
0006570869.tif 000012
【図１２】
0006570869.tif 000013
【図１３】
0006570869.tif 000014
【図１４】
0006570869.tif 000015
【図１５】
0006570869.tif 000016
【図１６】
0006570869.tif 000017