(57)【特許請求の範囲】
【請求項１】
各時間ｔに個体が滞在した各場所ωを表す位置情報履歴から得られる観測値行列Ｙω，ｔに対して、非負値行列分解又は非負値テンソル分解を適用することにより、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔにおける各基底ｋの有効性を表すアクティベーションＵｋ，ｔとを出力するＮＭＦ適用部と、
前記基底ｋ毎の前記場所分布Ｈω，ｋと、各時間ｔの前記アクティベーションＵｋ，ｔとに基づいて、ＦＨＭＭを用いて推定される、各時間ｔに前記個体が滞在した各場所ωを表す推定値行列Ｘω，ｔと前記観測値行列Ｙω，ｔとの距離を表す予め求められた目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数１】
0006448506.tif 000048
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを繰り返す拡張ＦＨＭＭ適用部と、
前記更新された前記基底ｋ毎の各状態ｚｔｋにおける前記場所分布
【数２】
0006448506.tif 000049
と、各時間ｔの前記アクティベーションＵｋ，ｔとを出力する結果出力部と、
を含み、
前記目的関数は、前記観測値行列Ｙω，ｔの要素のうち、非ゼロの要素についての、推定値行列Ｘω，ｔと前記観測値行列Ｙω，ｔとの距離、及び前記観測値行列Ｙω，ｔの要素のうち、ゼロの要素についての、推定値行列Ｘω，ｔと更新前の前記推定値行列Ｘω，ｔとの距離を表すことを特徴とする
パターン抽出装置。
【請求項２】
前記拡張ＦＨＭＭ適用部は、周期性を考慮しない第１拡張ＦＨＭＭ適用部と、周期性を考慮した第２拡張ＦＨＭＭ適用部とからなり、
前記第１拡張ＦＨＭＭ適用部は、状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数３】
0006448506.tif 000050
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返し、
前記第２拡張ＦＨＭＭ適用部は、各時間ｔの前記アクティベーションＵｋ，ｔに基づいて、前記基底ｋ毎に周期を決定し、決定された前記基底ｋ毎の周期及び状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数４】
0006448506.tif 000051
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返す請求項１に記載のパターン抽出装置。
【請求項３】
前記第２拡張ＦＨＭＭ適用部は、決定された前記基底ｋ毎の周期に基づいて、前記周期の開始地点において状態遷移に制約を与えるように、前記基底ｋ毎の各状態ｚｔｋを推定する請求項２に記載のパターン抽出装置。
【請求項４】
前記第２拡張ＦＨＭＭ適用部は、初期周期決定部と、周期変更部とを含み、
前記初期周期決定部は、前記第１拡張ＦＨＭＭ適用部により更新された各時間ｔの前記アクティベーションＵｋ，ｔを用いて、前記基底ｋ毎に周期を決定し、
前記周期変更部は、前記第２拡張ＦＨＭＭ適用部により更新された各時間ｔの前記アクティベーションＵｋ，ｔを用いて、前記基底ｋ毎に周期を決定し、
前記第２拡張ＦＨＭＭ適用部は、前記初期周期決定部又は前記周期変更部によって決定された前記基底ｋ毎の周期及び状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数５】
0006448506.tif 000052
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新する請求項２又は請求項３に記載のパターン抽出装置。
【請求項５】
前記周期は、時間を基準とした時間周期、曜日を基準とした曜日周期、又は季節を基準とした季節周期である請求項２〜請求項４のいずれか１項に記載のパターン抽出装置。
【請求項６】
ＮＭＦ適用部が、各時間ｔに個体が滞在した各場所ωを表す位置情報履歴から得られる観測値行列Ｙω，ｔに対して、非負値行列分解又は非負値テンソル分解を適用することにより、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔにおける各基底ｋの有効性を表すアクティベーションＵｋ，ｔとを出力するステップと、
拡張ＦＨＭＭ適用部が、前記基底ｋ毎の前記場所分布Ｈω，ｋと、各時間ｔの前記アクティベーションＵｋ，ｔとに基づいて、ＦＨＭＭを用いて推定される、各時間ｔに前記個体が滞在した各場所ωを表す推定値行列Ｘω，ｔと前記観測値行列Ｙω，ｔとの距離を表す予め求められた目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数６】
0006448506.tif 000053
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを繰り返すステップと、
結果出力部が、前記更新された前記基底ｋ毎の各状態ｚｔｋにおける前記場所分布
【数７】
0006448506.tif 000054
と、各時間ｔの前記アクティベーションＵｋ，ｔとを出力するステップと、
を含み、
前記目的関数は、前記観測値行列Ｙω，ｔの要素のうち、非ゼロの要素についての、推定値行列Ｘω，ｔと前記観測値行列Ｙω，ｔとの距離、及び前記観測値行列Ｙω，ｔの要素のうち、ゼロの要素についての、推定値行列Ｘω，ｔと更新前の前記推定値行列Ｘω，ｔとの距離を表すことを特徴とする
パターン抽出方法。
【請求項７】
前記拡張ＦＨＭＭ適用部は、周期性を考慮しない第１拡張ＦＨＭＭ適用部と、周期性を考慮した第２拡張ＦＨＭＭ適用部とからなり、
前記第１拡張ＦＨＭＭ適用部が更新するステップは、状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数８】
0006448506.tif 000055
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返し、
前記第２拡張ＦＨＭＭ適用部が更新するステップは、各時間ｔの前記アクティベーションＵｋ，ｔに基づいて、前記基底ｋ毎に周期を決定し、決定された前記基底ｋ毎の周期及び状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数９】
0006448506.tif 000056
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返す請求項６に記載のパターン抽出方法。
【請求項８】
コンピュータを、請求項１〜請求項５のいずれか１項に記載のパターン抽出装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン抽出装置、方法、及びプログラムに係り、特に、位置情報履歴を活用したパターン抽出のためのパターン抽出装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、モバイルデバイスやソーシャルネットワーキングサービスの普及により、ユーザ毎の位置情報履歴の観察が可能になった。位置情報履歴から、定常的な訪問傾向を抽出する手法（非特許文献１参照）や、時間帯別の訪問傾向を抽出する手法（非特許文献２参照）、マルコフモデルにより連続する一部のログ間の遷移確率を抽出する方法（非特許文献３参照）などが提案されている。しかしながら、これらの手法は時系列情報を含む位置情報履歴全体の傾向を捉えるものであり、時間帯と共に連続して訪れる行動パターンを抽出できるまでには至っていない。
【０００３】
位置情報履歴に頻出する、例えば平日は朝自宅を出て会社に出勤し、昼には会社近くのいくつかの飲食店のうち１つで昼食を取り、夜になると会社を退社して自宅に帰る、といった連続行動パターン（以下パターンと称する）を抽出する取り組みは、情報配信、都市計画、又は人流制御による混雑緩和など多くの場面で有効であると考えられる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】T.Kurashima, T.Iwata, T.Hoshide, N.Takaya, and K.Fujimura. Geo Topic Model: Joint Modeling of User's Activity Area and Interests for Location Recommendation. In Proceedings of the sixth ACM international conference on Web Search and Data Mining, pages 375-384. ACM, 2013.
【非特許文献２】E.Malmi, T.M.T. Do, and D.Gatica-Perez. From Foursquare to My Square: Learning Check-in Behavior from Multiple Sources. ICWSM, 2013.
【非特許文献３】D.Ashbrook and T.Starner. Using GPS to learn significant locations and predict movement across multiple users. Personal and Ubiquitous Computing,7(5):275-286, 2003.
【非特許文献４】澤田宏. 非負値行列因子分解NMFの基礎とデータ/信号解析への応用. 信学誌, 95(9):829-833, 2012.
【非特許文献５】Z.Fan, X. Song, and R. Shibasaki. CitySpectrum: A Non-negative Tensor Factorization Approach. In Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing, pages 213-223. ACM,2014.
【非特許文献６】中野允裕, 北野佑, ルルージョナトン, 亀岡弘和, 小野順貴, 嵯峨山茂樹.可変基底NMFに基づく音楽音響信号の解析. 研究報告音楽情報科学(MUS),2010(10):1-6, 2010.
【非特許文献７】Y.Wang, Y.Zheng, and Y.Xue. Travel Time Estimation of a Path using Sparse Trajectories. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 25-34. ACM,2014.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記の従来手法においては以下に挙げる課題がある。
【０００６】
まず、位置情報履歴におけるパターン抽出における課題がある。時系列データから、パターンを抽出する方法として、非負値行列分解（Ｎｏｎ−ｎｅｇａｔｉｖｅ  Ｍａｔｒｉｘ  Ｆａｃｔｏｒｉｚａｔｉｏｎ，ＮＭＦ）の有効性が示されている（非特許文献４参照）。位置情報履歴におけるパターン抽出において、ＮＭＦを行列ではなくテンソルに拡張した非負値テンソル分解（Ｎｏｎｎｅｇａｔｉｖｅ  Ｔｅｎｓｏｒ  Ｆａｃｔｏｒｉｚａｔｉｏｎ，ＮＴＦ）の有効性が示されている（非特許文献５参照）。上記手法では、位置情報履歴をユーザ×場所×時間の３次元テンソルで表現した上で、そのテンソルを低次の行列（基底）の積の形で近似することにより、各時間の行動をいくつかの訪問傾向に分類し、行動パターンを抽出する。しかしながら、抽出する訪問傾向の種類数（基底数）は観察者により手動で設定され、その数が多すぎると、類似した訪問傾向がいくつもの基底で表現されてしまい、解釈が難しくなる。一方で、基底数が少ないと、異なる訪問傾向が１つの基底に混在してしまい、解釈が難しくなるといった課題がある。
【０００７】
また、Ｆａｃｔｏｒｉａｌ  Ｈｉｄｄｅｎ  Ｍａｒｋｏｖ  Ｍｏｄｅｌ（ＦＨＭＭ）における課題がある。ＮＭＦやＮＴＦにおいて、基底の分布を階層的に抽出するために、ＦＨＭＭの概念を導入した手法（非特許文献６参照）が提案されている。図１５に示すように、ＮＭＦにおける各基底の分布が状態変化するように表現されている。音響データの音源分離を目的としてＮＭＦにＦＨＭＭを適用することにより、各基底で音のピッチを分類した上で、さらに同じピッチの中で拍などに応じてアタック→サスタイン→ディケイ→リリースなどと微妙に変化する振幅スペクトルの状態遷移を表現し、性能の向上が示されているが、位置情報ログへの適用は未実現である。位置情報ログにおいてもＦＨＭＭが適用できれば、平日会社に行く際の行動パターンと休日習い事に行く際の行動パターンをそれぞれ別基底で抽出するなどの効果が期待される。
【０００８】
スパース性への対応において課題がある。ＦＨＭＭの有効性が示されている音響データなどに比べ、位置情報ログはスパース性が強い傾向がある。例えば、ある特定のユーザの訪問履歴を用いて場所×時間の行列Ｙω，ｔを作成する場合を考える。時刻ｔに場所ωを訪問すればＹω，ｔ＝１、訪問していなければＹω，ｔ＝０とする。ユーザは同時に複数の場所に存在することはできないという制約があるため、同じ時刻に訪問履歴がある場所は１箇所のみになり、他の場所には値０が入る。加えて、位置情報履歴の中でもチェックインサービスのログなど、ユーザによる能動的な作業により訪問履歴が残される形式のログでは、実際にどこかを訪問していても、その訪問が記録されない場合や、１箇所に数時間滞在していても、そこに到着した際にしかログが残っていない場合があり、よりデータのスパース性は高くなる。一方、ユーザの能動的な記録作業を必要としないＧＰＳ等の形式の移動軌跡ログにおいては、明示的に滞留点に対する訪問場所ＩＤなどが与えられないため、移動時等に場所数が膨大に増え、スパース性が高くなる。移動軌跡ログにおいて滞留点を検出するなどの前処理を行ったとしても、緯度経度の測定誤差や滞留点の検出精度などによりデータの欠損が容易に発生すると考えられる。データのスパース性が高いと、多くの時刻で状態が推定できなくなる（全ての場所への訪問確率が０となるパターンが大量に生成されてしまう）だけでなく、一度だけ訪問した場所などがパターン抽出に強く作用してしまう可能性がある。こうした位置情報ログのスパース性に対応する方法として、同一時間帯の同ユーザの訪問傾向や、他ユーザの同場所への訪問傾向を使ってデータを補間しながらＮＴＦを適用する手法が提案されている（非特許文献７参照）が、同一時間帯や同一場所の訪問傾向には必ず類似性があるという強い仮定が入っており、異なる時間帯に起こる類似した傾向等の考慮や、同一時間帯でも複数の傾向が混在するなどの状況にも対応した補間は実現できていない。
【０００９】
また、周期性への対応における課題がある。従来のＦＨＭＭでは、各基底における状態を推定する際に、データの絶対時間軸上の周期性を明示的に考慮することは行っておらず、例えば１週間周期、２４時間周期などの周期性の想定されるデータにおいても、その周期性と合致しないパターンが抽出されてしまい解釈が難しくなる可能性がある。
【００１０】
本発明は、上記問題点を解決するために成されたものであり、できるパターン抽出装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、第１の発明に係るパターン抽出装置は、各時間ｔに個体が滞在した各場所ωを表す位置情報履歴から得られる観測値行列Ｙω，ｔに対して、非負値行列分解又は非負値テンソル分解を適用することにより、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔにおける各基底ｋの有効性を表すアクティベーションＵｋ，ｔとを出力するＮＭＦ適用部と、前記基底ｋ毎の前記場所分布Ｈω，ｋと、各時間ｔの前記アクティベーションＵｋ，ｔとに基づいて、ＦＨＭＭを用いて推定される、各時間ｔに前記個体が滞在した各場所ωを表す推定値行列Ｘω，ｔと前記観測値行列Ｙω，ｔとの距離を表す予め求められた目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数１】
0006448506.tif 000002
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを繰り返す拡張ＦＨＭＭ適用部と、前記更新された前記基底ｋ毎の各状態ｚｔｋにおける前記場所分布
【数２】
0006448506.tif 000003
と、各時間ｔの前記アクティベーションＵｋ，ｔとを出力する結果出力部と、を含んで構成され、前記目的関数は、前記観測値行列Ｙω，ｔの要素のうち、非ゼロの要素についての、推定値行列Ｘω，ｔと前記観測値行列Ｙω，ｔとの距離、及び前記観測値行列Ｙω，ｔの要素のうち、ゼロの要素についての、推定値行列Ｘω，ｔと更新前の前記推定値行列Ｘω，ｔとの距離を表すことを特徴とする。
【００１２】
また、第１の発明に係るパターン抽出装置において、前記拡張ＦＨＭＭ適用部は、周期性を考慮しない第１拡張ＦＨＭＭ適用部と、周期性を考慮した第２拡張ＦＨＭＭ適用部とからなり、前記第１拡張ＦＨＭＭ適用部は、状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数３】
0006448506.tif 000004
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返し、前記第２拡張ＦＨＭＭ適用部は、各時間ｔの前記アクティベーションＵｋ，ｔに基づいて、前記基底ｋ毎に周期を決定し、決定された前記基底ｋ毎の周期及び状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数４】
0006448506.tif 000005
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返すようにしてもよい。
【００１３】
また、第１の発明に係るパターン抽出装置において、前記第２拡張ＦＨＭＭ適用部は、決定された前記基底ｋ毎の周期に基づいて、前記周期の開始地点において状態遷移に制約を与えるように、前記基底ｋ毎の各状態ｚｔｋを推定するようにしてもよい。
【００１４】
また、第１の発明に係るパターン抽出装置において、前記第２拡張ＦＨＭＭ適用部は、初期周期決定部と、周期更新部とを含み、前記初期周期決定部は、前記第１拡張ＦＨＭＭ適用部により更新された各時間ｔの前記アクティベーションＵｋ，ｔを用いて、前記基底ｋ毎に周期を決定し、前記周期変更部は、前記第２拡張ＦＨＭＭ適用部により更新された各時間ｔの前記アクティベーションＵｋ，ｔを用いて、前記基底ｋ毎に周期を決定し、前記第２拡張ＦＨＭＭ適用部は、前記初期周期決定部又は前記周期変更部によって決定された前記基底ｋ毎の周期及び状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数５】
0006448506.tif 000006
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新するようにしてもよい。
【００１５】
また、第１の発明に係るパターン抽出装置において、前記周期は、時間を基準とした時間周期、曜日を基準とした曜日周期、又は季節を基準とした季節周期であるようにしてもよい。
【００１６】
第２の発明に係るパターン抽出方法は、ＮＭＦ適用部が、各時間ｔに個体が滞在した各場所ωを表す位置情報履歴から得られる観測値行列Ｙω，ｔに対して、非負値行列分解又は非負値テンソル分解を適用することにより、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔにおける各基底ｋの有効性を表すアクティベーションＵｋ，ｔとを出力するステップと、拡張ＦＨＭＭ適用部が、前記基底ｋ毎の前記場所分布Ｈω，ｋと、各時間ｔの前記アクティベーションＵｋ，ｔとに基づいて、Ｆａｃｔｏｒｉａｌ  Ｈｉｄｄｅｎ  Ｍａｒｋｏｖ  Ｍｏｄｅｌ（ＦＨＭＭ）を用いて推定される、各時間ｔに前記個体が滞在した各場所ωを表す推定値行列Ｘω，ｔと前記観測値行列Ｙω，ｔとの距離を表す予め求められた目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数６】
0006448506.tif 000007
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを繰り返すステップと、結果出力部が、前記更新された前記基底ｋ毎の各状態ｚｔｋにおける前記場所分布
【数７】
0006448506.tif 000008
と、各時間ｔの前記アクティベーションＵｋ，ｔとを出力するステップと、を含んで実行することを特徴とし、前記目的関数は、前記観測値行列Ｙω，ｔの要素のうち、非ゼロの要素についての、推定値行列Ｘω，ｔと前記観測値行列Ｙω，ｔとの距離、及び前記観測値行列Ｙω，ｔの要素のうち、ゼロの要素についての、推定値行列Ｘω，ｔと更新前の前記推定値行列Ｘω，ｔとの距離を表すことを特徴とする。
【００１７】
また、第２の発明に係るパターン抽出方法において、前記拡張ＦＨＭＭ適用部は、周期性を考慮しない第１拡張ＦＨＭＭ適用部と、周期性を考慮した第２拡張ＦＨＭＭ適用部とからなり、前記第１拡張ＦＨＭＭ適用部が更新するステップは、状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数８】
0006448506.tif 000009
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返し、前記第２拡張ＦＨＭＭ適用部が更新するステップは、各時間ｔの前記アクティベーションＵｋ，ｔに基づいて、前記基底ｋ毎に周期を決定し、決定された前記基底ｋ毎の周期及び状態遷移確率に基づいて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋを推定し、推定された前記基底ｋ毎の各状態ｚｔｋを用いて、前記目的関数の値が最小となるように、前記基底ｋ毎の各状態ｚｔｋにおける場所分布
【数９】
0006448506.tif 000010
と、各時間ｔの前記アクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返すようにしてもよい。
【００１８】
第３の発明に係るプログラムは、コンピュータを、第１の発明に係るパターン抽出装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１９】
本発明のパターン抽出装置、方法、及びプログラムによれば、観測値行列に対して、非負値行列分解又は非負値テンソル分解を適用することにより、基底毎の場所分布と、各時間における各基底の有効性を表すアクティベーションとを出力し、基底毎の場所分布と、各時間のアクティベーションとに基づいて、ＦＨＭＭを用いて推定される、各時間に個体が滞在した各場所を表す推定値行列と観測値行列との距離を表す予め求められた目的関数の値が最小となるように、基底毎の各状態における場所分布と、各時間のアクティベーションとを更新することを繰り返し、更新された基底毎の各状態における場所分布と、各時間のアクティベーションとを出力し、目的関数は、観測値行列の要素のうち、非ゼロの要素についての、推定値行列と観測値行列との距離、及び観測値行列の要素のうち、ゼロの要素についての、推定値行列と更新前の推定値行列との距離を表すことにより、個体の位置情報履歴から、周期的に出現するパターンを抽出することができる、という効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】階層的な周期をもつパターン抽出のイメージを表した抽象図である。
【図２】位置情報履歴を表した抽象図である。
【図３】欠損補間のイメージを表した抽象図である。
【図４】アクティベーションのスパース化の一例を示すグラフ図である。
【図５】周期性の制約のイメージを表した抽象図である。
【図６】本発明の実施の形態に係るパターン抽出装置の構成を示すブロック図である。
【図７】本発明の実施の形態に係るパターン抽出装置におけるパターン抽出処理ルーチンを示すフローチャートである。
【図８】本発明の実施の形態に係るパターン抽出装置におけるＦＨＭＭ適用処理ルーチンを示すフローチャートである。
【図９】チェックインデータの一例を示す図である。
【図１０】観測値行列の一例を示す図である。
【図１１】初期のアクティベーションと、周期性の付与の検討例を示す図である。
【図１２】従来手法と拡張ＦＨＭＭのアクティベーションの出力を比較した一例を示す図である。
【図１３】アクティベーションのスパース化を行わなかった場合の一例を示す図である。
【図１４】ＮＭＦと拡張ＦＨＭＭの場所分布の出力を比較した一例を示す図である。
【図１５】ＮＭＦとＦＨＭＭの関係を示す抽象図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２２】
＜本発明の実施の形態に係る概要＞
【００２３】
まず、本発明の実施の形態における概要を説明する。
【００２４】
本発明の実施の形態では、位置情報履歴に対してＦＨＭＭを適用することにより、階層的な行動パターンの抽出を実現する際に生じる、データのスパース性という課題に対応するために、補間ステップを導入することによりＦＨＭＭを拡張する。また、１週間周期、２４時間周期などの周期性を外部情報として与えてＦＨＭＭにおける状態推定ステップに制約を与えることにより、様々な周期性を考慮しながら状態を推定できるようにＦＨＭＭを拡張する。図１に、本発明の実施の形態に係る手法による周期的パターンの抽出イメージを示す。ＨＭＭ１では時間周期、ＨＭＭ２では季節周期、ＨＭＭ３では曜日周期など様々な階層的周期性を持った訪問パターンが抽出できると期待される。ここで、状態は場所群への頻度分布を表す。例えば時間周期のＨＭＭ１の状態１は、会社（ビル）に行きやすい状態、状態２はカフェに行きやすい状態、状態３はカフェと寿司屋の両方に行きやすいが、ややカフェの方が確率が高い状態を示す。時間によって変化する状態の系列が、前述の連続行動パターンを形成すると想定する。
【００２５】
＜本発明の実施の形態に係る原理＞
【００２６】
次に、本発明の実施の形態における原理を説明する。
【００２７】
まず、位置情報ログに対してＦＨＭＭを適用する手法の原理について説明する。本実施の形態ではユーザＩＤ、年月日時刻、及び場所の情報を含む位置情報ログを想定する。以下、特定のユーザの位置情報履歴に対してＦＨＭＭを適用する場合について、技術の詳細を説明する。まず、場所ω×時刻ｔの行列を作成する。この際、時刻は日付単位、時間帯単位など任意の単位時間で区切る。位置情報履歴の表現方法の例を図２に示す。
【００２８】
ＦＨＭＭは以下（１）式のように表される。
【００２９】
【数１０】
0006448506.tif 000011
【００３０】
ＦＨＭＭの目的関数はＩダイバージェンス基準により以下（２）式のように記述できる。
【００３１】
【数１１】
0006448506.tif 000012
【００３２】
目的関数ＪＦＨＭＭに対しては、Ｊｅｎｓｅｎの不等式により、以下（３）式に示す上界関数を設定できる。
【００３３】
【数１２】
0006448506.tif 000013
【００３４】
上記（３）式の上界関数の等号成立条件を以下（４）式に示す。
【００３５】
【数１３】
0006448506.tif 000014
【００３６】
以上の（１）〜（４）式を用いて、場所ω×時刻ｔの訪問有無を格納したＹω，ｔに対して、以下の［１］〜［８］の手順でＦＨＭＭを適用することができる。
【００３７】
［１］ＮＭＦの結果得られたＨω，ｋ，Ｕｋ，ｔを用いて、
【００３８】
【数１４】
0006448506.tif 000015
【００３９】
に初期値を入れる。
【００４０】
［２］上記（４）式に従ってλω，ｋ，ｔの初期値を計算する。
【００４１】
［３］Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍに基づいて状態Ｚｔｋを更新する。
【００４２】
［４］上記（５）式に従って
【００４３】
【数１５】
0006448506.tif 000016
【００４４】
を更新し、上記（６）式に従ってＵｋ，ｔを更新する。
【００４５】
［５］収束するまで手順［３］、［４］を繰り返す。
【００４６】
［６］上記（４）式に従ってλω，ｋ，ｔの値を更新する。
【００４７】
［７］手順［３］から［６］を目的関数ＪＦＨＭＭの値が収束するまで繰り返す。
【００４８】
［８］目的関数ＪＦＨＭＭの値が十分に小さくなれば、各基底の状態数を順に増加していく。
【００４９】
上記、手順［４］の更新式は以下（５）式、及び（６）式の通りである。
【００５０】
【数１６】
0006448506.tif 000017
【００５１】
（５）式、及び（６）式は、上記（３）式をＨω，ｋ，ｊ、Ｕｋ，ｔについてそれぞれ偏微分した値を０と置いて、（５）式でＨω，ｋ，ｊを、（６）式でＵｋ，ｔを解くことにより得られる。ここで、１[]は、[]内の条件を満たす場合には１、そうでない場合には０をとる。
【００５２】
また、手順［１］の初期値を作成する際に、各基底内で類似した状態が設定されるようにするために、Ｈω，ｋ，１にはＨω，ｋの値を入れ、Ｈω，ｋ，ｓ（ｓは１≦ｓ≦Ｓｋを満たす整数）にはＨω，ｋをランダムに微小変化させた値を入れるなどの方法が考えられる。ここでＳｋは基底ｋの状態数を表し、Ｓｋの初期値は２とする。
【００５３】
上記手順の収束後、
【００５４】
【数１７】
0006448506.tif 000018
【００５５】
により、各基底ｋについて、各状態ｚｔｋにおける各場所ωに対する訪問確率分布が表現される。また、Ｕｋ，ｔにより、各時刻ｔ毎にどの基底（ｋ）がアクティベートされるか（有効になっているか）が表現される。
【００５６】
例えば、時刻ｔ＝３において、ｋ＝１のときＵ１，３が１で、ｋが他の値のときＵｋ，３が全て０になっていた場合、
【００５７】
【数１８】
0006448506.tif 000019
【００５８】
の分布は
【００５９】
【数１９】
0006448506.tif 000020
【００６０】
となる。
【００６１】
ここでｚ３１は時刻ｔ＝３における基底ｋ＝１の状態を示す。同一時刻において、各基底の状態は１つの状態に定まるものとする。
【００６２】
次に、スパース性を考慮するための拡張の原理について説明する。
【００６３】
位置情報ログの多くはスパース性が高く、特にチェックインデータなどユーザが能動的に訪問を記録する形式ではＹω，ｔにおける非ゼロ要素率は手元のデータで０．２７％などの小さい値を取る。スパース性が高いと、多くの時間帯において、状態がうまく推定できない、たまたま一度だけ訪問した場所が強くパターン抽出に作用してしまう、などの問題がある。そこで、ＦＨＭＭでパラメータの更新を繰り返していく際に、欠損箇所を補間していくステップを導入する。入力データにおいて０以外の値が入っている箇所の集合をΓとする。本実施の形態の提案手法では、以下（７）式のように、入力データで０以外の値が入っている箇所ではＹω，ｔとＸω，ｔが近づくように、欠損箇所（０が入っている箇所）ではＳω，ｔすなわち更新前のＸω，ｔの値と更新後のＸω，ｔが近づくように、最小化させる目的関数を変更する。
【００６４】
【数２０】
0006448506.tif 000021
【００６５】
図３に欠損値補間のイメージを示す。（７）式において、ｗｓは補間箇所におけるＩダイバージェンスをどれくらいの重みで考慮するかを示す定数である。補間された値にＸω，ｔが近づき過ぎないようにするために重みづけを行う。ｗｓの値として、例えば非ゼロ要素の割合（１−スパース率）を利用するなどが考えられる。
【００６６】
欠損箇所の補間を行うと、補間箇所に強い影響を受けて、各時刻ｔにおけるアクティベーションＵｋ，ｔが多くの基底ｋで類似した値になってしまう可能性がある。そこで、本発明の実施の形態では、複数の基底が同時にアクティベートされにくいように、Ｕｋ，ｔをスパース化させる処理を行う。ここでは、Ｕｋ，ｔの値が０に一定程度近づいたら強制的に０とするイメージで目的関数に｜Ｕｋ，ｔ｜Ｐを最小化させる項を加える。すなわち、目的関数は以下（８）式のように表現される。
【００６７】
【数２１】
0006448506.tif 000022
【００６８】
ここで、Ｐは０＜Ｐ＜２を満たす定数であり、０に近いほど強い制約となる。
【００６９】
また、ｗｐは全体の目的関数に対して、どの程度の重みでアクティベーションのスパース化を考慮するかを示す定数である。
【００７０】
上記（８）式からは解析的にＵｋ，ｔを更新することはできないため、関数Ｕｋ，ｔの上界関数として、図４に示すようなＵｋ，ｔに接する放物線を考える。この上界関数を用いて、目的関数は以下（９）式のように表現される。
【００７１】
【数２２】
0006448506.tif 000023
【００７２】
ここで￣Ｕｋ，ｔは、更新前のＵｋ，ｔの値を示す。
【００７３】
以上で示したように、本発明の実施の形態ではデータのスパース性に対応して欠損値を補間しながら値の更新を行っていくようにＦＨＭＭを拡張する。また、この際欠損部分の値に推定が強く影響されすぎないように、重み定数ｗｓ，ｗｐを導入した上で、アクティベーションＵｋ，ｔのスパース化を行う。目的関数が従来法の（３）式から、（９）式へと拡張されたことに応じ、ＦＨＭＭを適用する際の手順［４］の処理におけるＨω，ｋ，ｊ、Ｕｋ，ｔの更新式は以下（１０）式、及び（１１）式のように変更される。
【００７４】
【数２３】
0006448506.tif 000024
【００７５】
次に、周期性を考慮するための拡張の原理について説明する。
【００７６】
人間の行動を記録した位置情報ログにおいては、行動パターンに時間帯、曜日、月、季節などに応じた周期性が存在する可能性がある。従来のＦＨＭＭでも、ＮＭＦにおける各基底にｌｅｆｔ−ｔｏ−ｒｉｇｈｔのＨＭＭを仮定することにより、周期的パターンの抽出を試みた。しかしながら、各ＨＭＭに時間帯や曜日など外部情報から得られる絶対時間周期を考慮することは実現しておらず、ＦＨＭＭにより抽出される周期は絶対時間周期と対応付けて解釈できるものになるとは限らなかった。本発明では、人間の行動には複数の階層的な周期性があると捉え、行動を複数の階層的周期パターンの和として表現することにより、従来よりも解釈がしやすく、情報配信などへの応用にも効果的なパターンの抽出を試みる。
【００７７】
本発明の実施の形態における周期性を考慮した第２拡張ＦＨＭＭ適用部では、ＮＭＦで抽出された各基底に、それぞれ異なる絶対時間周期を仮定し、ＨＭＭにおける状態遷移に制約を与える。各基底に対する周期の初期値は、周期性考慮のための拡張を行わない第１拡張ＦＨＭＭ適用部適用時の各基底のアクティベーションの時間変化傾向を元に決定する。周期決定の際には、アクティベーションが季節、曜日、及び時間帯の何れの周期を持つ可能性が高いかどうかを判定する。例えば、毎日複数回アクティベーションが高くなる場合には、時間帯による周期を表現するための２４時間周期を与える。また、１日１回または特定の曜日にアクティベーションが高くなる場合には、曜日による周期を表現するための１週間周期を与える。同様にして、特定の季節のみでアクティベーションが高くなる場合には、季節による周期を表現するために、１年の周期を与える。
【００７８】
この時、全ての想定周期に対する集計値が不均一な場合には、周期性を与えない。季節、曜日、時間帯別にアクティベーションが一定以上になった回数を集計することにより、周期が決定される。
【００７９】
この周期は、拡張ＦＨＭＭを適用しながら、再度変更していくことが考えられる。決定した周期を用いて拡張ＦＨＭＭを適用した際に、特定の状態のみでしかアクティベーションが高くならない場合には、周期を１週間周期から２４時間周期など、より小さいものに変更していくことが考えられる。一方、アクティベーションが高くなった状態の偏りが少なくなった場合は、周期の変更を停止する。また、周期が最小となっても状態に偏りが生じた場合は、その基底への周期性付与は行わない。周期の最小値については、データ期間に応じて１時間周期、６時間周期などと決定することが考えられる。
【００８０】
本発明の実施の形態では、以上説明したように、各基底に仮定する絶対時間周期を決定した上で、ＨＭＭの状態推定時に、各周期の開始地点には特定の状態が推定されるよう制約を与える。周期性による制約のイメージを図５に示す。基底毎に異なる周期の周期性を仮定し、各周期の開始地点には状態ｉがｉ＝０に固定されるようにする。
【００８１】
基底ｋの時刻ｔにおける隠れ状態ｉを推定する際には、Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍを用いて以下（１２）式のような再帰計算を行う。
【００８２】
【数２４】
0006448506.tif 000025
【００８３】
ここで、ａｉｊはｉからｊへの遷移確率を示し、更新前に推定された状態系列内での遷移確率を元に決定する。｛ｂｅａｔｋ｝は基底ｋに与えた周期の開始地点のｔの値の集合を示す。ψｋ，ｔ，ｉを最後の時刻からたどれば、隠れ状態系列が得られる。なお、各周期の開始地点においては、状態遷移確率及び目的関数の値を参照せず、強制的に特定の状態ｉ（例えばｉ＝０）と決定する。
【００８４】
＜本発明の実施の形態に係るパターン抽出装置の構成＞
【００８５】
次に、本発明の実施の形態に係るパターン抽出装置の構成について説明する。図６に示すように、本発明の実施の形態に係るパターン抽出装置１００は、ＣＰＵと、ＲＡＭと、後述するパターン抽出処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このパターン抽出装置１００は、機能的には図６に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００８６】
入力部１０は、各時間ｔに特定のユーザが滞在した各場所ωを表す位置情報履歴を受け付け、位置情報ログ記憶部２８に記憶する。なお、複数のユーザの位置情報履歴を受け付け、ユーザごとにパターンを抽出するようにしてもよい。また、ユーザの位置情報履歴に限らず、識別可能な個体であればどのようなものの位置情報履歴でもよい。
【００８７】
演算部２０は、位置情報ログ記憶部２８と、ログ集計部３０と、ＮＭＦ適用部３２と、第１拡張ＦＨＭＭ適用部３４と、第２拡張ＦＨＭＭ適用部３６と、拡張ＦＨＭＭ結果出力部４４と、検出パターン描画部４６とを含んで構成されている。
【００８８】
位置情報ログ記憶部２８には、ユーザの位置情報履歴が記憶されている。
【００８９】
ログ集計部３０は、位置情報ログ記憶部２８に記憶されているユーザの位置情報履歴における時刻ｔの場所ω毎の訪問有無を集計し、観測値行列Ｙω，ｔを出力する。
【００９０】
ＮＭＦ適用部３２は、ログ集計部３０から出力された観測値行列Ｙω，ｔに対して非負値行列分解（ＮＭＦ）を適用し、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔにおける各基底ｋの有効性を表すアクティベーションＵｋ，ｔとを出力する。なお、本実施の形態ではＮＭＦを適用するが、これに限定されるものではなく、例えば非負値テンソル分解（ＮＴＦ）を適用するようにしてもよい。
【００９１】
以下に説明する第１拡張ＦＨＭＭ適用部３４、及び第２拡張ＦＨＭＭ適用部３６は、それぞれ上記ＦＨＭＭ適用手順［１］〜［８］を実行することにより、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔのアクティベーションＵｋ，ｔとに基づいて、ＦＨＭＭを用いて推定される、各時間ｔにユーザが滞在した各場所ωを表す推定値行列Ｘω，ｔと観測値行列Ｙω，ｔとの距離を表す予め求められた上記（７）式又は（９）式に示す目的関数の値が最小となるように、基底ｋ毎の各状態ｚｔｋにおける場所分布
【００９２】
【数２５】
0006448506.tif 000026
【００９３】
と、各時間ｔのアクティベーションＵｋ，ｔとを更新することを繰り返す。
【００９４】
本実施の形態の第１拡張ＦＨＭＭ適用部３４において用いる上記（７）式に示す目的関数は、観測値行列Ｙω，ｔの要素のうち、非ゼロの要素についての、推定値行列Ｘω，ｔと観測値行列Ｙω，ｔとの距離、及び観測値行列Ｙω，ｔの要素のうち、ゼロの要素についての、推定値行列Ｘω，ｔと更新前の推定値行列Ｘω，ｔとの距離を表すことを特徴とする。
【００９５】
第１拡張ＦＨＭＭ適用部３４は、状態遷移確率に基づいて、上記（７）式に示す目的関数の値が最小となるように、基底ｋ毎の各状態ｚｔｋを推定し、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔのアクティベーションＵｋ，ｔと、観測値行列Ｙω，ｔと、推定された基底ｋ毎の各状態ｚｔｋとに基づいて、前回更新された推定値行列Ｘω，ｔをＳω，ｔとして、上記（７）式に示す目的関数の値が最小となるように、上記（１０）式、及び以下（１３）式に従って、基底ｋ毎の各状態ｚｔｋにおける場所分布
【００９６】
【数２６】
0006448506.tif 000027
【００９７】
と、各時間ｔのアクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返す。なお、（１３）式は、上記（７）式をＵｋ，ｔについて偏微分した値を０と置いて、Ｕｋ，ｔを解くことにより得られる。
【００９８】
【数２７】
0006448506.tif 000028
【００９９】
ここで状態遷移確率とは、ある時間窓で状態がｉであったと推定された際に、全状態数をＮとして、次の時間窓に他の（Ｎ−１）個状態に遷移する確率をそれぞれ求めたものであり、状態ｉを出発点とした（Ｎ−１）個の状態への遷移確率の和が１になるものである。
【０１００】
収束条件としては、目的関数ＪＦＨＭＭの値が前回更新の値よりも閾値以上に小さくならない、あるいは前回更新の値よりも大きくなる場合を収束条件とし、各基底の状態数Ｓｋの増加を停止する。また、目的関数ＪＦＨＭＭの値が閾値以上に小さくなっていても、減少率が逓減してきた場合には収束したものとしてもよい。
【０１０１】
第２拡張ＦＨＭＭ適用部３６は、各時間ｔのアクティベーションＵｋ，ｔに基づいて、基底ｋ毎に周期を決定し、決定された基底ｋ毎の周期及び状態遷移確率に基づいて、上記（９）式に示す目的関数の値が最小となるように、基底ｋ毎の各状態ｚｔｋを推定し、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１０２】
【数２８】
0006448506.tif 000029
【０１０３】
と、各時間ｔのアクティベーションＵｋ，ｔと、観測値行列Ｙω，ｔと、推定された基底ｋ毎の各状態ｚｔｋとに基づいて、前回更新された推定値行列Ｘω，ｔをＳω，ｔとして、上記（９）式に示す目的関数の値が最小となるように、上記（１０）式、及び（１１）式に従って、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１０４】
【数２９】
0006448506.tif 000030
【０１０５】
と、各時間ｔのアクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返す。収束条件は第１拡張ＦＨＭＭ適用部３４と同様である。また、第２拡張ＦＨＭＭ適用部３４において用いる上記（９）式に示す目的関数は、アクティベーションＵｋ，ｔのスパース化を行うための項を含むことを特徴とする。
【０１０６】
第２拡張ＦＨＭＭ適用部３６においては、決定された基底ｋ毎の周期に基づいて、周期の開始地点｛ｂｅａｔｋ｝において状態遷移に制約を与えるように、基底ｋ毎の各状態ｚｔｋを推定することを特徴とする。
【０１０７】
また、第２拡張ＦＨＭＭ適用部３６は、初期周期決定部３８と、拡張ＦＨＭＭ適用部４０と、周期変更部４２とを含んで構成される。
【０１０８】
初期周期決定部３８は、第１拡張ＦＨＭＭ適用部により更新された各時間ｔのアクティベーションＵｋ，ｔを用いて、基底ｋ毎に周期を決定する。
【０１０９】
拡張ＦＨＭＭ適用部４０は、初期周期決定部３８又は後述する周期変更部４２によって決定された基底ｋ毎の周期と、状態遷移確率とに基づいて、上記（９）式に示す目的関数の値が最小となるように、基底ｋ毎の各状態ｚｔｋを推定し、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１１０】
【数３０】
0006448506.tif 000031
【０１１１】
と、各時間ｔのアクティベーションＵｋ，ｔと、観測値行列Ｙω，ｔと、推定された基底ｋ毎の各状態ｚｔｋとに基づいて、前回更新された推定値行列Ｘω，ｔをＳω，ｔとして、上記（９）式で表わされる目的関数の値が最小となるように、上記（１０）式、及び（１１）式に従って、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１１２】
【数３１】
0006448506.tif 000032
【０１１３】
と、各時間ｔのアクティベーションＵｋ，ｔとを更新する。
【０１１４】
周期変更部４２は、拡張ＦＨＭＭ適用部４０により更新された各時間ｔのアクティベーションＵｋ，ｔを用いて、基底ｋ毎に周期を決定する。
【０１１５】
拡張ＦＨＭＭ結果出力部４４は、第２拡張ＦＨＭＭ適用部３６で更新された基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１１６】
【数３２】
0006448506.tif 000033
【０１１７】
と、各時間ｔのアクティベーションＵｋ，ｔとを出力する。
【０１１８】
検出パターン描画部４６は拡張ＦＨＭＭ結果出力部４４から出力された基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１１９】
【数３３】
0006448506.tif 000034
【０１２０】
と、各時間ｔのアクティベーションＵｋ，ｔとを描画する処理を行い、出力部５０に出力する。ここで描画されたパターンの観察を行うことで、ユーザのパターンを検出し、ユーザの行動分析を行うことができる。
【０１２１】
＜本発明の実施の形態に係るパターン抽出装置の作用＞
【０１２２】
次に、本発明の実施の形態に係るパターン抽出装置１００の作用について説明する。入力部１０においてユーザの位置情報履歴を受け付け、位置情報ログ記憶部２８に記憶すると、パターン抽出装置１００は、図７に示すパターン抽出処理ルーチンを実行する。
【０１２３】
まず、ステップＳ１００では、位置情報ログ記憶部２８に記憶されているユーザの位置情報履歴における各時刻ｔの場所ω毎の訪問有無を集計し、観測値行列Ｙω，ｔを出力する。
【０１２４】
次に、ステップＳ１０２では、ステップＳ１００で出力された観測値行列Ｙω，ｔに対して非負値行列分解（ＮＭＦ）を適用し、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔにおける各基底ｋの有効性を表すアクティベーションＵｋ，ｔとを出力する。
【０１２５】
ステップＳ１０４では、状態遷移確率に基づいて、上記（７）式に示す目的関数の値が最小となるように、基底ｋ毎の各状態ｚｔｋを推定し、基底ｋ毎の場所分布Ｈω，ｋと、各時間ｔのアクティベーションＵｋ，ｔと、観測値行列Ｙω，ｔと、推定された基底ｋ毎の各状態ｚｔｋとに基づいて、前回更新された推定値行列Ｘω，ｔをＳω，ｔとして、上記（７）式で表わされる目的関数の値が最小となるように、上記（１０）式、及び（１３）式に従って、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１２６】
【数３４】
0006448506.tif 000035
【０１２７】
と、各時間ｔのアクティベーションＵｋ，ｔとを更新することを予め定めた収束条件を満たすまで繰り返す。
【０１２８】
ステップＳ１０６では、ステップＳ１０６により更新された各時間ｔのアクティベーションＵｋ，ｔを用いて、基底ｋ毎に周期を決定する。
【０１２９】
ステップＳ１０８では、ステップＳ１０６又はステップＳ１１０によって決定された基底ｋ毎の周期及び状態遷移確率に基づいて、上記（９）式に示す目的関数の値が最小となるように、基底ｋ毎の各状態ｚｔｋを推定し、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１３０】
【数３５】
0006448506.tif 000036
【０１３１】
と、各時間ｔのアクティベーションＵｋ，ｔと、観測値行列Ｙω，ｔと、推定された基底ｋ毎の各状態ｚｔｋとに基づいて、前回更新された推定値行列Ｘω，ｔをＳω，ｔとして、上記（９）式で表わされる目的関数の値が最小となるように、上記（１０）式、及び（１１）式に従って、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１３２】
【数３６】
0006448506.tif 000037
【０１３３】
と、各時間ｔのアクティベーションＵｋ，ｔとを更新する。
【０１３４】
ステップＳ１１０では、ステップＳ１０８により更新された各時間ｔのアクティベーションＵｋ，ｔを用いて、基底ｋ毎に周期を決定する。
【０１３５】
ステップＳ１１２では、ステップＳ１１０で決定された周期が周期収束条件を満たすかを判定し、満たしていればステップＳ１１４へ移行し、満たしていなければステップＳ１０８へ戻ってステップＳ１０８〜Ｓ１１０の処理を繰り返す。周期収束条件としては、「周期が最小周期であること」か、又は「アクティベーションが高くなる状態に偏りが生じていないこと」を条件とする。
【０１３６】
ステップＳ１１４では、ステップＳ１０６〜Ｓ１１２により更新された基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１３７】
【数３７】
0006448506.tif 000038
【０１３８】
と、各時間ｔのアクティベーションＵｋ，ｔとを出力する。
【０１３９】
ステップＳ１１６では、ステップＳ１１４で出力された基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１４０】
【数３８】
0006448506.tif 000039
【０１４１】
と、各時間ｔのアクティベーションＵｋ，ｔとのパターンを描画する処理を行い、出力部５０に出力し処理を終了する。
【０１４２】
上記ステップＳ１０４、及びステップＳ１０８は、以下に説明するＦＨＭＭ適用処理ルーチンによって実行される。
【０１４３】
図８に示すように、まず、ステップＳ２００では、ステップＳ１０２で得られた基底ｋ毎の場所分布Ｈω，ｋ又はＳ１０４で得られた基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１４４】
【数３９】
0006448506.tif 000040
【０１４５】
、各時間ｔのアクティベーションＵｋ，ｔを用いて、
【０１４６】
【数４０】
0006448506.tif 000041
【０１４７】
に初期値を入れる。
【０１４８】
ステップＳ２０２では、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１４９】
【数４１】
0006448506.tif 000042
【０１５０】
と、各時間ｔのアクティベーションＵｋ，ｔとに基づいて、上記（４）式に従ってλω，ｋ，ｔの初期値を計算する。
【０１５１】
ステップＳ２０４では、Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍにしたがって基底ｋ毎の各時間ｔの状態Ｚｔｋを更新する。ここでステップＳ１０４のＦＨＭＭ適用処理ルーチンにおいては、状態遷移確率に基づいて、上記（７）式に示す目的関数の値が最小となるように、基底ｋ毎の各時間ｔの状態Ｚｔｋを更新する。一方、ステップＳ１０８のＦＨＭＭ適用処理ルーチンにおいては、Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍにおいて用いる再帰計算に上記（１２）式を用い、決定された基底ｋ毎の周期及び状態遷移確率に基づいて、上記（９）式に示す目的関数の値が最小となるように、基底ｋ毎の各時間ｔの状態Ｚｔｋを更新する。
【０１５２】
ステップＳ２０６では、λω，ｋ，ｔと、各時間ｔのアクティベーションＵｋ，ｔと、観測値行列Ｙω，ｔとに基づいて、前回更新された推定値行列Ｘω，ｔをＳω，ｔとして、上記（１０）式に従って
【０１５３】
【数４２】
0006448506.tif 000043
【０１５４】
を更新し、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１５５】
【数４３】
0006448506.tif 000044
【０１５６】
と、λω，ｋ，ｔと、各時間ｔのアクティベーションＵｋ，ｔと、観測値行列Ｙω，ｔとに基づいて、前回更新された推定値行列Ｘω，ｔをＳω，ｔとして、ステップＳ１０４では上記（１３）式、ステップＳ１０８では上記（１１）式に従って各時間ｔのアクティベーションＵｋ，ｔを更新する。
【０１５７】
ステップＳ２０８では、ステップＳ２０４、及びステップＳ２０６で更新した値が収束したかを判定し、収束していればステップＳ２１０へ移行し、収束していなければステップＳ２０４〜Ｓ２０６を繰り返す。
【０１５８】
ステップＳ２１０では、基底ｋ毎の各状態ｚｔｋにおける場所分布
【０１５９】
【数４４】
0006448506.tif 000045
【０１６０】
と、各時間ｔのアクティベーションＵｋ，ｔとに基づいて、上記（４）式に従ってλω，ｋ，ｔの値を更新する。
【０１６１】
ステップＳ２１２では、目的関数ＪＦＨＭＭの値が十分に小さくなるまで収束したかを判定し、収束していればステップＳ２１４へ移行し、収束していなければステップＳ２０４〜Ｓ２１０を繰り返す。
【０１６２】
ステップＳ２１４では、ステップＳ２１２で収束した目的関数ＪＦＨＭＭの値が収束条件を満たすかを判定し、収束条件を満たしていなければ、ステップＳ２１６へ移行して各基底の状態数ＳｋをＳｋ＝Ｓｋ＋１と更新して、ステップＳ２００へ戻って更新を繰り返し、収束条件を満たしていれば、ＦＨＭＭ適用処理ルーチンを終了する。
【０１６３】
＜実施例＞
【０１６４】
実際の位置情報データを用いて、本発明の実施の形態に係る提案手法を検証する。検証実験については、Ｓｔａｎｆｏｒｄ大学がインターネットサイト（https://snap.stanford.edu/data/loc-gowalla.html）で公開しているＧｏｗａｌｌａのチェックインデータを利用する。
【０１６５】
チェックインデータでは、ユーザの能動的操作により、訪問履歴が記録される。基本的に、各地点に到着した際のみに訪問履歴の記録が実施され、各地点から離れる際の記録は行われないことが多い。チェックインデータの例を図９に示す。ユーザＩＤと、日付時刻、緯度経度に加え、同一の緯度経度に割り振られる場所ＩＤが格納されている。
【０１６６】
ここでは、ある特定のユーザのデータのみを抽出して検証実験を行った。場所ωとして場所ＩＤを用いた。時刻ｔについては、データに記載された時刻を０時台、１時台など１時間毎の時間窓に分割した上で、最も古いチェックインログが記録された時間窓から数えた時間窓数を用いた。計算の際のアンダーフローを抑制するため、Ｙω，ｔの値をすべて１００００倍にして扱った。
【０１６７】
図１０に、当該データを集計して作成したＹω，ｔを示す。スパース率が高く、スパース率は９９．７３１％である。
【０１６８】
次に、図１１に、第1拡張ＦＨＭＭ適用部適用時（欠損値補間は行うがアクティベーションＵｋ，ｔのスパース化と周期性の考慮は未適用）の、アクティベーションＵｋ，ｔと、決定した初期付与周期を示す。各折れ線グラフの横軸は時間窓ｔを示し、縦軸はＵｋ，ｔの大きさを示す。ほぼ毎日複数回のパターンが出現しているｋ＝１では、１日の中での行動パターンの把握を行うために２４時間の周期を与えた。また、ほぼ毎日、１日１回ずつアクティベーションが高くなっているｋ＝３では、曜日によって異なる行動パターンの把握を目的として１週間の周期を与えた。同様に、特定の曜日（主に平日）のみにパターンが出現しているｋ＝４についても、各曜日で異なるパターンの抽出を試みるために１週間の周期を与えた。アクティベーションが不定期に高くなっている基底ｋ＝２とｋ＝５については、周期性の付与は行わなかった。
【０１６９】
周期性付与の効果を検証するために、図１２に周期性の付与を行った場合と行わなかった場合のアクティベーションＵｋ，ｔの出力をそれぞれ示す。各ヒートマップの横軸は時間窓ｔを示し、縦軸は各状態を示す。状態数は基底毎にそれぞれ目的関数の減少の様子と照合して決定した。色が濃いほど、アクティベーションＵｋ，ｔが大きいことを示す。周期性の付与を全く行わなかったｋ＝２とｋ＝５については省略した。また、周期性の付与を行った全基底について、複数の状態でアクティベーションが高くなったため、周期の変更は実施しなかった。
【０１７０】
まず、同時間窓に複数の基底でアクティベーションが高くなってはおらず、アクティベーションのスパース化の効果が得られていることが分かる。ｋ＝１については、２４時間周期の周期性の付与を行うと、ほぼ１つの状態が選択され続けていることが分かる。従って、基底ｋ＝１には単一の行動パターンのみしか存在しないと考えられる。周期を与えないと、状態１、２の複数の状態が出現しているが、２つの状態の
【０１７１】
【数４５】
0006448506.tif 000046
【０１７２】
を比較すると、パターンが酷似しており、周期性の導入により類似した状態を統合することができたととらえることができる。
【０１７３】
ｋ＝３については、周期性の考慮により、冒頭部分でややアクティベーションの傾向が変化している。矩形で囲んだ箇所に５回、短時間で状態２から状態３へ遷移するパターンが発見できる。ｋ＝４についても、アクティベーションの傾向が変化しており、曜日ごとに異なるパターンを各基底に抽出できていると期待される。なお、アクティベーションのスパース化を行わないと、図１３に示すように、同一時間窓において複数の基底でアクティベーションが高くなってしまう。
【０１７４】
続いて、欠損値補間の効果を確認するために、図１４に基底ｋ＝３における各状態の
【０１７５】
【数４６】
0006448506.tif 000047
【０１７６】
の出力結果を示す。左はＮＭＦによって抽出された基底ｋ＝３の分布である。欠損値補間を行わないＮＭＦの結果に比べ、拡張ＦＨＭＭの結果では訪問可能性がある場所が薄く検出されていることが分かる。欠損箇所の補間を行わずにＦＨＭＭを適用すると、状態が遷移しなかったり、すべての場所への訪問可能性が０の分布が抽出されてしまう。欠損箇所の補間を行った上で、同時に複数の基底がＯＮにならないようなアクティベーションのスパース化を行うことにより、図１４の右に示されているような状態１〜３において行動パターンを抽出することが可能になった。加えて、薄く色がついている訪問場所には、実際に訪問した場所だけでなく、訪問可能性が高い場所群が表現されており、各状態が、場所群への「訪問気分」に該当すると期待される。
【０１７７】
抽出されたパターンの中身を分析してみると、状態１には非習慣的に訪問される店や住宅地が、状態２には特定地域の娯楽施設やカジュアルな飲食店が、状態３には状態２と同じ地域のバーや居酒屋と隣接県の駅や住宅街が分類されていることが分かった。状態２には主に昼間に訪問する場所群が、状態３には自宅を含め、夜間によく訪問される場所群が分類されていると捉えることができ、状態２から状態３へと続く１日の行動パターンが特定の曜日に複数回に渡って起こることを検出できた。上記図１２のｋ＝３の基底を見ると、５回目の状態２から３の遷移の際には状態２→状態１→状態３というパターン遷移が起きていることも分かる。この時には、昼によく行く状態２の場所群を訪問した後、非習慣的に他の場所で夜を過ごし、普段よりも間が空いた後に、普段通りの夜のパターン（状態３）に遷移していると理解することができる。このように、本発明の実施の形態に係る手法を適用することにより、一定の周期性で現れる行動系列を抽出することができることが確認できた。
【０１７８】
以上説明したように、本発明の実施の形態に係るパターン抽出装置によれば、各時間にユーザが滞在した各場所を表す位置情報履歴から得られる観測値行列に対して、非負値行列分解又は非負値テンソル分解を適用することにより、基底毎の場所分布と、各時間における各基底の有効性を表すアクティベーションとを出力し、基底毎の場所分布と、各時間のアクティベーションとに基づいて、ＦＨＭＭを用いて推定される、各時間にユーザが滞在した各場所を表す推定値行列と観測値行列との距離を表す上記（７）式又は（９）式に示す目的関数の値が最小となるように、基底毎の各状態における場所分布と、各時間のアクティベーションとを更新することを繰り返し、更新された基底毎の各状態における場所分布と、各時間のアクティベーションとを出力し、目的関数は、観測値行列の要素のうち、非ゼロの要素についての、推定値行列と観測値行列との距離、及び観測値行列の要素のうち、ゼロの要素についての、推定値行列と更新前の推定値行列との距離を表すことにより、ユーザの位置情報履歴から、周期的に出現するパターンを抽出することができる、という効果が得られる。
【０１７９】
また、欠損の多いデータにおいても、ユーザの訪問可能性がある場所群を検出することができる。
【０１８０】
また、複数のユーザに共通する行動パターンを把握することで、都市計画などへの応用が可能となる。
【０１８１】
また、ユーザ毎に特有な行動パターンを抽出することにより、行動を予測して情報配信の満足度を向上させるといった効果が期待できる。
【０１８２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１８３】
例えば、上述した実施の形態では、第１拡張ＦＨＭＭ適用部３４、及び第２拡張ＦＨＭＭ適用部３６により基底毎の各状態における場所分布と、各時間のアクティベーションとを更新する場合を例に説明したが、これに限定されるものではなく、第１拡張ＦＨＭＭ適用部３４、又は第２拡張ＦＨＭＭ適用部３６のいずれか一方により基底毎の各状態における場所分布と、各時間のアクティベーションとを更新するようにしてもよい。
【符号の説明】
【０１８４】
１０   入力部
２０   演算部
２８   位置情報ログ記憶部
３０   ログ集計部
３２   ＮＭＦ適用部
３４   第１拡張ＦＨＭＭ適用部
３６   第２拡張ＦＨＭＭ適用部
３８   初期周期決定部
４０   拡張ＦＨＭＭ適用部
４２   周期変更部
４４   拡張ＦＨＭＭ結果出力部
４６   検出パターン描画部
５０   出力部
１００ パターン抽出装置
【図１】
0006448506.tif 000057
【図２】
0006448506.tif 000058
【図３】
0006448506.tif 000059
【図４】
0006448506.tif 000060
【図５】
0006448506.tif 000061
【図６】
0006448506.tif 000062
【図７】
0006448506.tif 000063
【図８】
0006448506.tif 000064
【図９】
0006448506.tif 000065
【図１０】
0006448506.tif 000066
【図１１】
0006448506.tif 000067
【図１２】
0006448506.tif 000068
【図１３】
0006448506.tif 000069
【図１４】
0006448506.tif 000070
【図１５】
0006448506.tif 000071