(57)【要約】【課題】短期間の状況だけでなく、当該短期間の状況がまとまって出現する長期間の状況を時系列データから検出できるようにする。【解決手段】計測されたセンサデータを時系列的に取得し、文字列に変換したものから、出現頻度が所定の値以上の部分文字列をモチーフとして検出する。そして、上記検出された複数のモチーフを所定の距離内で類似するモチーフ毎にグルーピングすることによって複数のモチーフグループを生成する。さらに、検出された複数のモチーフが時系列の文字列に出現する時間位置をもとに、当該モチーフを含むモチーフグループの中から時系列上で所定の範囲内でまとまって出現するモチーフグループ群を検出する。【選択図】図２
2017156942.tif 000002
【特許請求の範囲】
【請求項１】
計測されたセンサデータを時系列的に取得する取得部と、
前記取得されたセンサデータを文字列に変換する変換部と、
前記変換された文字列から、出現頻度が所定の値以上の部分文字列をモチーフとして検出するモチーフ検出部と、
前記検出された複数のモチーフを所定の距離内で類似するモチーフ毎にグルーピングすることによって複数のモチーフグループを生成するグループ生成部と、
前記検出された複数のモチーフが前記時系列の文字列に出現する時間位置をもとに、当該モチーフを含む前記モチーフグループの中から時系列上で所定の範囲内でまとまって出現するモチーフグループ群を検出するモチーフ群検出部と、
前記検出されたモチーフグループ群を記憶する記憶部と
を具備することを特徴とする局所的パターン検出装置。
【請求項２】
前記グループ生成部は、階層的クラスタリング法を用いて前記モチーフグループを生成することを特徴とする請求項１に記載の局所的パターン検出装置。
【請求項３】
前記モチーフ群検出部は、前記モチーフグループの時系列上の出現順序から無向グラフを作成し、当該無向グラフのグラフ構造を分析することによって前記モチーフグループ群を検出することを特徴とする請求項１または請求項２に記載の局所的パターン検出装置。
【請求項４】
前記モチーフ群検出部は、
前記文字列を前記検出されたモチーフの長さと同じ長さの照合文字列に分割し、分割された照合文字列ごとに、前記検出された複数のモチーフの中から当該照合文字列と一致するモチーフを検出して、当該モチーフが属する前記モチーフグループを前記照合文字列と対応付ける手段と、
前記複数のモチーフグループを、当該モチーフグループに対応付けられた照合文字列の出現時間順に並べ、これらのモチーフグループのうち連続して出現するモチーフグループ同士をエッジで接続すると共に当該モチーフグループ同士の出現頻度を前記エッジに重み付けしたモチーフグラフを生成する手段と、
前記生成されたモチーフグラフを構成する複数のモチーフグループを前記エッジの重みに基づいて関連するモチーフグループ群に分割する手段と
を備えることを特徴とする請求項１乃至３のいずれかに記載の局所的パターン検出装置。
【請求項５】
計測されたセンサデータの中から局所的に変化する状況を表す局所的パターンを検出する装置が実行する局所的パターン検出方法であって、
計測されたセンサデータを時系列的に取得する過程と、
前記取得されたセンサデータを文字列に変換する過程と、
前記変換された文字列から、出現頻度が所定の値以上の部分文字列をモチーフとして検出する過程と、
前記検出された複数のモチーフを所定の距離内で類似するモチーフ毎にグルーピングすることによって複数のモチーフグループを生成する過程と、
前記検出された複数のモチーフが前記時系列の文字列に出現する時間位置をもとに、当該モチーフを含む前記モチーフグループの中から時系列上で所定の範囲内でまとまって出現するモチーフグループ群を検出する過程と、
前記検出されたモチーフグループ群を記憶する過程と
を具備することを特徴とする局所的パターン検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、センサによって取得された時系列データの中から、局所的に変化する状況を表すパターンを検出する局所的パターン検出装置および方法に関する。
【背景技術】
【０００２】
近年、歩数計や心拍センサを初めとする携帯型センサの開発に伴い、気温や交通量などの環境データのみならず、人の日常行動や体の状態などを表すデータも常時計測することが可能となっている。計測されたデータ（センサデータともいう）は、時系列的に取得されるため、様々な状況（或いは状態）と密接にリンクしていると考えられる。例えば、人の日常生活においては、「睡眠中」、「覚醒中」、「食事中」、「歩行中」および「走行中」などの様々な状況が局所的に存在し、それらの状況に応じてセンサデータの値が変動する。上記の状況に応じて適切な情報やサービスを提供したい場合に、時系列的に取得されたセンサデータ（時系列データともいう）から局所的に変化する状況を把握する必要がある。
【０００３】
時系列データから特徴的な変化を示す局所的系列（モチーフともいう）を検出する技術としては、例えば時系列データ全体を１つの文字列として表現し、当該文字列中に頻繁に出現する部分文字列をモチーフとして検出する技術（例えば非特許文献１を参照）などが提案されている。係る技術は、検出したモチーフと時系列データ取得時の状況を照合することによって、モチーフから当該取得時の状況を特定することができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Yoshiki Tanaka, Kazuhisa Iwamoto, and Kuniaki Uehara. “Discovery of Time-Series Motif from Multi-Dimensional Data Based on MDL Principle” Machine Learning 58.2-3 (2005): 269-300.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところが、従来のモチーフ単位での照合は、短期間の状況を検出することは可能であるものの、いくつかの特定のモチーフがまとまって出現する長期間の状況を検出することは困難である。例えば、「体操中」の状態を含む人の動作データに対して、従来では「腕振り」や「ひざの屈伸」などの要素運動は、「体操中」において出現頻度が高いためにモチーフとして検出されやすい。しかしながら、係る要素運動で構成される「体操種目（或いは体操種目の実施）」や複数の体操種目で構成される「体操競技中」などの長期間の状況は、要素運動に比べて出現頻度が低いために検出が難しい。
【０００６】
この発明は上記事情に着目してなされたもので、その目的とするところは、短期間の状況だけでなく、当該短期間の状況がまとまって出現する長期間の状況を検出することができる局所的パターン検出装置および方法を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するためにこの発明の第１の態様は、計測されたセンサデータを時系列的に取得し、文字列に変換したものから、出現頻度が所定の値以上の部分文字列をモチーフとして検出する。そして、上記検出された複数のモチーフを所定の距離内で類似するモチーフ毎にグルーピングすることによって複数のモチーフグループを生成する。さらに、検出された複数のモチーフが時系列の文字列に出現する時間位置をもとに、当該モチーフを含むモチーフグループの中から時系列上で所定の範囲内でまとまって出現するモチーフグループ群を検出するようにしたものである。
【０００８】
この発明の第２の態様は、上記モチーフグループを生成する際に、階層的クラスタリング法を用いてモチーフグループを生成するようにしたものである。
【０００９】
この発明の第３の態様は、上記モチーフグループ群を検出する際に、モチーフグループの時系列上の出現順序から無向グラフを作成し、当該無向グラフのグラフ構造を分析することによってモチーフグループ群を検出するようにしたものである。
【００１０】
この発明の第４の態様は、上記モチーフグループ群を検出する際に、上記無向グラフのノードをノード群に分割することによってグラフ構造を分析するようにしたものである。
【発明の効果】
【００１１】
この発明の第１の態様によれば、時系列データから検出されるモチーフをグループ分けし、モチーフグループの出現順序に基づいてモチーフグループ群を検出する。このため、個々のモチーフに対応する短期間に変化する状況のみでなく、類似するモチーフが集まったモチーフ群に対応する短期間の状況がまとまって出現する長期間の状況が検出可能である。また、モチーフ検出の際に設定するモチーフ長が短い場合でも、各々の状況において関連するモチーフは頻繁に存在する。従って、状況を検出する際にモチーフ長の違いによる影響を受けにくくなる。
【００１２】
この発明の第２の態様によれば、階層的クラスタリング法を用いてモチーフグループが生成される。階層的クラスタリング法を用いることで、予めモチーフグループの数を決める必要がなく、作成するモチーフグループの数を容易に選択或いは変更することができる。
【００１３】
この発明の第３及び第４の態様によれば、モチーフグループの時系列上の出現順序から無向グラフが作成され、当該無向グラフのノードをノード群に分割することによってグラフ構造が分析され、モチーフグループ群が検出される。従って、時系列データをグラフ構造に置き換えて分析することができるため、モチーフグループ同士の関連を容易に検出することができる。
【図面の簡単な説明】
【００１４】
【図１】この発明の一実施形態に係る局所的パターン検出装置を備えたシステムの全体構成を例示する図。
【図２】この発明の一実施形態に係る局所的パターン検出装置として使用されるサーバ装置の機能構成を例示するブロック図。
【図３】図２のサーバ装置による全体の処理手順と処理内容を例示するフローチャート。
【図４】図３の局所的パターン検出処理の手順と処理内容を例示するフローチャート。
【図５Ａ】モチーフグループの出現状況の一例を説明するための図。
【図５Ｂ】図５Ａのモチーフグループの出現状況から作成したモチーフグラフを例示する図。
【図６Ａ】ノードの統合によるノード群を例示する図。
【図６Ｂ】図６Ａのノード群におけるノードの統合過程を例示する図。
【発明を実施するための形態】
【００１５】
以下、図面を参照してこの発明に関わる実施形態を説明する。  
［一実施形態］
（構成）
図１は、この発明の一実施形態に係る局所的パターン検出装置を備えたシステムの全体構成を例示する図である。上記システムは、局所的パターン検出装置としての機能を有するサーバ装置ＳＶを備え、サーバ装置ＳＶとユーザが所持するユーザ端末ＴＭ１〜ＴＭｎとの間で、それぞれ通信ネットワークＮＷを介してデータ通信を可能にしたものである。尚、サーバ装置は、通信ネットワークを介さずにユーザ端末と直接通信してもよい。
【００１６】
通信ネットワークＮＷは、インターネットに代表されるＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｌ）網と、このＩＰ網にアクセスするためのアクセス網とから構成される。上記アクセス網としては、有線電話網、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、携帯電話網、無線ＬＡＮ、ＣＡＴＶ（Ｃａｂｌｅ  Ｔｅｌｅｖｉｓｉｏｎ）網等が用いられる。
【００１７】
ユーザ端末ＴＭ１〜ＴＭｎは、例えばウェアラブル端末、スマートフォン、タブレット型携帯情報端末、携帯型のオーディオプレーヤ等の携帯端末からなり、いずれもユーザの動作や状態をセンシングするセンサとして、例えば３軸加速度センサ、或いは心拍センサ等を内蔵している。尚、センサ群は必ずしも携帯端末に内蔵されていなくてもよく、センサ群により検出されたセンサデータがスマートフォン等の携帯端末を経由してサーバ装置ＳＶへ送信されるものであってもよい。また、上記ユーザ端末は、サーバ装置の構成（或いは機能）が実装されてもよい。
【００１８】
サーバ装置ＳＶは、図２に例示されるように構成される。サーバ装置ＳＶは、制御ユニット１と、記憶ユニット２と、通信インタフェースユニット３とを備えている。通信インタフェースユニット３は、制御ユニット１の制御の下、通信ネットワークＮＷにより規定されるプロトコルに従い、ユーザ端末ＴＭ１〜ＴＭｎとの間でデータ通信を行う。
【００１９】
制御ユニット１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等のプロセッサを有し、本実施形態を実施するために必要な処理機能として、センサデータ取得部１１（取得部）と、センサデータ／文字列変換部１２（変換部）と、モチーフ検出部１３と、モチーフグループ生成部１４（グループ生成部）と、モチーフグループ対応付け処理部１５（処理部）と、モチーフグループ群検出部１６とを備えている。これらの処理機能はいずれも図示しないプログラムメモリに格納されたプログラムを上記ＣＰＵに実行させることにより実現される。尚、モチーフグループ対応付け処理部１５およびモチーフグループ群検出部１６の処理機能を統合してモチーフ群検出部としてもよい。
【００２０】
センサデータ取得部１１は、予め設定した時間間隔で上記ユーザ端末ＴＭ１〜ＴＭｎからそれぞれセンサデータを取得する。センサデータ取得部１１は、ユーザ端末ＴＭ１〜ＴＭｎごとに、当該収集されたセンサデータを時刻などのセンシング状況を表す情報と対応付けてセンサデータ／文字列変換部１２へと出力する。尚、以降では、上記ユーザ端末ＴＭ１〜ＴＭｎのうちのいずれか一つのユーザ端末から取得したセンサデータの処理について説明する。
【００２１】
センサデータ／文字列変換部１２は、センサデータ取得部１１から着目するセンサデータ（例えば加速度データ）を受け取り、当該センサデータを文字列に変換する。センサデータ／文字列変換部１２は、文字列を後述する文字列記憶部２１へと出力する。
【００２２】
センサデータ／文字列変換部１２は、例えばＳＡＸ（Ｓｙｍｂｏｌｉｃ  Ａｇｇｒｅｇａｔｅ  Ａｐｐｒｏｘｉｍａｔｉｏｎ）法を用いて、上記センサデータを文字列に変換してもよい。ＳＡＸ法は、時系列データの分布を正規分布と仮定し、データの出現頻度が均等となるようにデータ領域を分割する。次に、分割したそれぞれのデータ領域に固有の文字を割り当て、それぞれのデータ領域内に含まれるデータに対応する文字をラベリングする。そして、ラベリングされた文字を時系列に並べることによって、時系列データを文字列に変換することができる。
【００２３】
具体的には、時系列データは、平均０、分散１となるように正規化された後、いくつかの領域に分割され、文字が割り当てられる。例えば、時系列データを３文字で表す場合には、正規化後のデータｘは、ｘ≦−０．４３、−０．４３＜ｘ≦０．４３、０．４３＜ｘの３つの領域に分割され、それぞれの領域を表す文字（例えばアルファベット）が割り当てられる。また、時系列データを５文字で表す場合には、正規化後のデータｘは、ｘ≦−０．８４、−０．８４＜ｘ≦−０．２５、−０．２５＜ｘ≦０．２５、０．２５＜ｘ≦０．８４、０．８４＜ｘの５つの領域に分割され、それぞれの領域を表す文字が割り当てられる。尚、分割する領域数、即ち、割り当てる文字の種類が多いほど、元のデータに近い精度を持った文字列を表現することができる。
【００２４】
尚、ＳＡＸ法については、 Jessica Lin, et al. “A Symbolic Representation of Time Series, with Implications for Streaming Algorithms” Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery. ACM, 2003. に詳しく記載されている。
【００２５】
モチーフ検出部１３は、文字列記憶部２１から文字列を読み込み、当該文字列から、出現頻度が所定の値以上の部分文字列をモチーフとして検出する。また、モチーフ検出部１３は、モチーフを検出する際に使用されるパラメータ（例えば出現頻度の閾値Ｆｔｈおよび部分文字列の長さＬｍなど）をユーザ端末から読み込んでもよい。モチーフ検出部１３は、検出した複数のモチーフを後述するモチーフ記憶部２２へと出力する。尚、上記パラメータは、センサデータ取得時に一緒に取得するようにしてもよい。
【００２６】
モチーフ検出部１３は、例えばＰｒｅｆｉｘＳｐａｎ（Ｐｒｅｆｉｘ−ｐｒｏｊｅｃｔｅｄ  Ｓｅｑｕｅｎｔｉａｌ  ｐａｔｔｅｒｎ  ｍｉｎｉｎｇ）を用いて、上記文字列から、出現頻度が所定の値以上である部分文字列をモチーフとして検出する。ＰｒｅｆｉｘＳｐａｎは、文字列に対して、１文字からなる部分文字列から検出をスタートし、当該部分文字列に続く文字のうち、Ｆｔｈ以上出現する文字を逐次的に検出する。そして、検出された順番に文字をつなぎ、つないだ文字列（部分文字列）の長さがＬｍとなった時に、その部分文字列をモチーフとして検出する。
【００２７】
尚、ＰｒｅｆｉｘＳｐａｎについては、 Jian Pei, et al. “Prefixspan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth” icccn. IEEE, 2001. に詳しく記載されている。
【００２８】
モチーフグループ生成部１４は、モチーフ記憶部２２から複数のモチーフを読み込み、当該複数のモチーフを所定の距離内で類似するモチーフ毎にグルーピングすることによって複数のモチーフグループを生成する。モチーフグループ生成部１４は、生成した複数のモチーフグループをモチーフグループ対応付け処理部１５へと出力する。
【００２９】
モチーフグループ生成部１４は、例えば階層的クラスタリング法を用いてモチーフのグルーピングを行う。階層的クラスタリング法は、例えばＮ個のモチーフｘｉ（ｉ＝１，２，・・・，Ｎ）が検出された場合に、それぞれのモチーフのみを含むＮ個のグループからスタートし、グループ間の距離が最も近い２つのグループを１つにまとめ、最終的に１つのグループとなるまで逐次的に統合する方法である。
【００３０】
上記のグループ間の距離を計算する方法には様々な方法が提案されている。本実施形態では、群平均法を利用した下記数式（１）によってグループＣｉとグループＣｊとの間の距離ｄ（Ｃｉ，Ｃｊ）を計算する。
【００３１】
【数１】
2017156942.tif 000003
【００３２】
上記数式（１）において、ｄ（ｘｉ，ｘｊ）は、モチーフｘｉとモチーフｘｊとの間の非類似度を表し、この値が大きいほどモチーフｘｉとモチーフｘｊとは共通点が少ないことを示す。
【００３３】
モチーフ間の非類似度は、例えばレーベンシュタイン距離を用いてもよい。レーベンシュタイン距離は、ある文字列から別の文字列へと変換する際に、一方の文字列に対して「挿入」、「削除」、および、「置換」の操作を繰り返し、最短の操作で他方の文字列へと変換するのに必要な最小コストを計算するものである。例えば、上記の各操作に対するコストを１とした場合に、上記の最小コストは、文字列を変換するために必要な最小の操作回数となる。
【００３４】
上記計算の具体例として、文字列ａおよび文字列ｂのレーベンシュタイン距離の計算について説明する。ここで、文字列ａおよび文字列ｂのｉ番目の文字をそれぞれａｉおよびｂｉと表し、文字列ａおよび文字列ｂの文字列長をそれぞれＬａおよびＬｂと表す。次に、インデックスが０から始まる（Ｌａ＋１）×（Ｌｂ＋１）の行列を考え、その行列の第（ｉ，ｊ）成分を表すｌｅｖａ，ｂ（ｉ，ｊ）を下記数式（２）によって計算する。
【００３５】
【数２】
2017156942.tif 000004
【００３６】
上記数式（２）において、ｌｅｖａ，ｂ（ｉ−１，ｊ）＋１は「挿入」に対応する値であり、ｌｅｖａ，ｂ（ｉ，ｊ−１）＋１は「削除」、ｌｅｖａ，ｂ（ｉ−１，ｊ−１）＋１（ａｉ≠ｂｊ）は「置換」にそれぞれ対応する値である。行列の左上から右下に向かって計算が行われるため、上記行列の第（Ｌａ，Ｌｂ）成分、即ちｌｅｖａ，ｂ（Ｌａ，Ｌｂ）の値がレーベンシュタイン距離（或いは非類似度）となる。
【００３７】
尚、レーベンシュタイン距離については、 Vladimir I. Levenshtein, “BINARY CODES CAPABLE OF CORRECTING DELETIONS, INSERTIONS, AND REVERSALS” Soviet physics doklady. Vol. 10. No. 8. 1966. に詳しく記載されている。
【００３８】
モチーフグループ対応付け処理部１５は、モチーフグループ生成部１４から複数のモチーフグループを受け取り、文字列記憶部２１から文字列を読み込み、モチーフ記憶部２２から複数のモチーフを読み込む。モチーフグループ対応付け処理部１５は、センサデータから変換された文字列に含まれるモチーフのそれぞれと一致する箇所に当該モチーフがグルーピングされたモチーフグループを対応付ける。モチーフグループ対応付け処理部１５は、文字列に含まれるモチーフのそれぞれと一致する箇所に対応付けられたモチーフグループをモチーフグループ群検出部１６へと出力する。尚、モチーフグループ対応付け処理部１５の具体的な動作は後述する。
【００３９】
モチーフグループ群検出部１６は、モチーフグループ対応付け処理部１５から、文字列に含まれるモチーフのそれぞれと一致する箇所に対応付けられたモチーフグループを受け取り、当該モチーフグループのそれぞれの出現順序に基づいてモチーフグループ群を検出する。モチーフグループ群検出部１６は、モチーフグループ群をユーザ端末、および、後述するモチーフグループ群記憶部２３へと出力する。尚、モチーフグループ群検出部１６の具体的な動作は後述する。
【００４０】
記憶ユニット２は、記憶媒体としてＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）やＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）等の書き込みおよび読み出しが随時可能な不揮発性メモリを使用したもので、本実施形態を実施するために必要な記憶部として、文字列記憶部２１と、モチーフ記憶部２２と、モチーフグループ群記憶部２３とを備えている。
【００４１】
文字列記憶部２１は、センサデータ／文字列変換部１２によって変換された文字列を時刻などのセンシング状況を表す情報と対応付けて記憶するために使用される。上記のセンシング状況を表す情報は、センサデータに対応付けられているものを用いてもよい。
【００４２】
モチーフ記憶部２２は、モチーフ検出部１３によって検出されたモチーフを記憶するために使用される。
【００４３】
モチーフグループ群記憶部２３は、モチーフグループ群検出部１６によって検出されたモチーフグループ群を記憶するために使用される。
【００４４】
（動作）
以上のように構成された局所的パターン検出装置は、図３に例示されるように動作する。即ち、先ずステップＳ３０１において、センサデータ取得部１１が、ユーザ端末からセンサデータを取得する。続いてステップＳ３０２において、センサデータ／文字列変換部１２が、センサデータを文字列に変換する。
【００４５】
次にステップＳ３０３において、モチーフ検出部１３が、文字列から、出現頻度が所定の値以上である部分文字列をモチーフとして検出する。そして、ステップＳ３０４において、モチーフグループ生成部１４が、上記検出されたモチーフのそれぞれを類似するモチーフ毎にグルーピングすることによってモチーフグループを生成する。
【００４６】
上記ステップＳ３０４の後に、ステップＳ３０５においてモチーフグループ対応付け処理部１５およびモチーフグループ群検出部１６が局所的パターン検出処理を実行する。この局所的パターン検出処理は、文字列に含まれるモチーフのそれぞれと一致する箇所に当該モチーフがグルーピングされたモチーフグループを対応付けて、当該モチーフグループのそれぞれの出現順序に基づいてモチーフグループ群を検出する処理である。換言すると、局所的パターン検出処理は、検出された複数のモチーフが時系列の文字列に出現する時間位置をもとに、当該モチーフを含むモチーフグループの中から時系列上で所定の範囲内でまとまって出現するモチーフグループ群を検出する処理である。
【００４７】
図４は、局所的パターン検出処理の詳細を例示する図である。すなわち、
モチーフグループ対応付け処理部１５は、先ず文字列を、検出したモチーフの長さ（以降、モチーフ長と称する）と同じ長さを持つ部分文字列（以降、照合文字列と称する）の単位に分割する（ステップＳ４０１）。
【００４８】
次にステップＳ４０２において、モチーフグループ対応付け処理部１５は、分割した文字列の出現時間順に１つの照合文字列を設定する。そして、ステップＳ４０３において、設定した照合文字列に一致するモチーフに対して、当該モチーフがグルーピングされたモチーフグループを対応付ける。このとき、処理中の照合文字列と一致するモチーフが無い場合は、対応付けの処理をスキップする。尚、照合文字列とモチーフとの一致を検出する際には、ある程度の違いを許容してもよい。例えば、照合文字列とモチーフとのレーベンシュタイン距離が２以内であれば、一致したとみなしてよい。
【００４９】
次にステップＳ４０４においてモチーフグループ対応付け処理部１５は、全ての照合文字列にモチーフグループを対応付けたか否かを判定する。全ての照合文字列にモチーフグループを対応付けた場合は、ステップＳ４０５へと進み、そうでなければステップＳ４０２へ戻る。
【００５０】
続いてステップＳ４０５において、モチーフグループ群検出部１６が、照合文字列の出現順に対応するモチーフグループを並べ、当該モチーフグループの時系列上の出現順序から無向グラフ（以降、モチーフグラフと称する）を作成する。具体的には、図５Ａに例示される５つのモチーフグループの出現状況から、図５Ｂに例示されるモチーフグラフを作成する。
【００５１】
図５Ａでは、モチーフグループ１，２，３，４の順にモチーフグループが出現した後に、一致グループの無い期間を挟み、モチーフグループ５，２，３の順にモチーフグループが出現している。
【００５２】
図５Ｂでは、モチーフグループに対応するノード（図中の丸数字）を配置し、図５Ａにおけるモチーフグループの出現順に、当該モチーフグループに対応するノード同士をエッジで接続することによって、モチーフグラフを作成している。
【００５３】
尚、本実施形態では、モチーフグラフ作成の際に、一致するモチーフグループの無い期間は考慮に入れず、この期間の前後に出現するモチーフグループに対応するノード同士をエッジで接続する。また、同じモチーフグループへの遷移が複数回出現する場合（例えば、モチーフグループ２からモチーフグループ３への遷移）には、それらに対応するノードに接続されるエッジに重みづけをしてもよい。エッジに重みづけをすることによって、重みの大きいエッジで接続されたノード同士は関連性が高いことを表すことができる。
【００５４】
ステップＳ４０６において、モチーフグループ群検出部１６は、モチーフグラフのグラフ構造を分析することによって、モチーフグループ群を検出する。具体的には、モチーフグループ群検出部１６は、関連するモチーフグループ群を検出するために、モチーフグラフのそれぞれのノードをノード群に統合する。この時、同じノード群に含まれるノード同士はエッジで密に接続され、異なるノード群にまたがるノード同士の接続は疎となるようにノードを統合する。
【００５５】
上記ノードの統合は、例えば、 Aaron Clauset, Mark EJ Newman, and Cristopher Moore. “Finding community structure in very large networks” Physical review E 70.6 (2004): 066111. に記載されているｇｒｅｅｄｙアルゴリズムを用いる。このアルゴリズムは下記数式（３）に示されるＱ値を最大化する。尚、Ｑ値は、クラスタリングの精度を測る指標値であり、値が１に近いほど精度が良いことを示す。
【００５６】
【数３】
2017156942.tif 000005
【００５７】
上記数式（３）において、Ｅはモチーフグラフのエッジ数を表し、ｋｉはノードｉに接続されるエッジ数を表し、ｃｉはノードｉが属しているノード群を表す。また、ｂｉｊはエッジの接続の有無を表し、ノードｉおよびノードｊが接続されていれば１となり、それ以外は０となる。さらに、δ（ｃｉ，ｃｊ）はノードｉおよびノードｊが同じノード群に属していれば１となり、それ以外は０を返す関数である。
【００５８】
上記ｇｒｅｅｄｙアルゴリズムは、初めに個々のノードをそれぞれノード群とみなしてＱ値を計算する。次に、任意の２つのノード群を統合した場合のＱ値を計算し、統合前のＱ値からの増加分ΔＱが最大となるノード群の組を求め、それらを１つのノード群に統合する。上記の統合処理を繰り返し、ノード群が１つになるか、異なるノード群の間にエッジが存在しなくなった場合に、Ｑ値が最大となるノード群の組み合わせを最適な統合がなされたものとする。結果として、同じノード群内のモチーフグループに含まれるモチーフが、まとまって出現するモチーフ群として検出される。尚、ノード統合の際に、モチーフグラフ作成によって求めたエッジの重みを考慮してもよい。
【００５９】
図６Ａにおいて、モチーフグラフを構成する１１個のノードを順次統合していき、３個のノード群まで統合された様子が例示される。具体的には、ノード１〜４のノード群、ノード５〜８のノード群、ノード９〜１１のノード群の３つのノード群に統合されている。上記の統合は、即ち、モチーフグラフを３つのノード群に最適分割したことと同様である。
【００６０】
図６Ｂにおいて、図６Ａに例示されたそれぞれのノード群の統合過程が例示される。この図では、統合ステップが増加する毎にノード群が統合されていくことを示す。或いは、分割されたノード群から統合ステップを逆に遡ることによって、ノード群に含まれるサブノード群を逐次的に求めることができる。
【００６１】
上記のサブノード群は、例えばノード１〜４のノード群におけるノード２および４のノード群などを表す。サブノード群に含まれるノードは、ノードの統合過程においてＱ値の増加分ΔＱが高かったものである。換言すると、サブノード群に含まれるノードは、文字列において頻繁に出現するモチーフグループを示す。
【００６２】
ステップＳ４０６の処理後に、図４の局所的パターン検出処理は終了し、さらに図３の処理も終了する。
【００６３】
（効果）
以上詳述したように一実施形態では、ユーザ端末からセンサデータを時系列的に取得し、取得したセンサデータを文字列に変換したのち、文字列から、出現頻度が所定の値以上である部分文字列をモチーフとして検出する。そして、上記モチーフのそれぞれを類似するモチーフ毎にグルーピングすることによってモチーフグループを生成し、上記文字列に含まれるモチーフのそれぞれと一致する箇所に当該モチーフがグルーピングされたモチーフグループを対応付ける。さらに、上記箇所に対応付けられたモチーフグループの出現順序に基づいてモチーフグループ群を検出するようにしている。
【００６４】
したがって、時系列データから検出されるモチーフをグループ分けし、モチーフグループの出現順序に基づいてモチーフグループ群を検出するため、個々のモチーフに対応する短期間に変化する状況のみでなく、類似するモチーフが集まったモチーフ群に対応する短期間の状況がまとまって出現する長期間の状況が検出可能である。また、モチーフ検出の際に設定するモチーフ長が短い場合でも、各々の状況において関連するモチーフは頻繁に存在する。よって、状況を検出する際にモチーフ長の違いによる影響を受けにくくなる。
【００６５】
また、モチーフグループを生成する際には、階層的クラスタリング法を用いることで、予めモチーフグループの数を決める必要がなく、作成するモチーフグループの数を容易に選択或いは変更することが可能となる。
【００６６】
さらに、モチーフグループ群を検出する際に、モチーフグループの時系列上の出現順序から無向グラフを作成し、当該無向グラフのノードをノード群に分割することによってグラフ構造を分析し、モチーフグループ群を検出する。このため、時系列データをグラフ構造に置き換えて分析することができるため、モチーフグループ同士の関連を容易に検出することができる。
【００６７】
［他の実施形態］
この発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、各実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００６８】
ＳＶ…サーバ装置、ＴＭ１〜ＴＭｎ…携帯端末、ＮＷ…通信ネットワーク、１…制御ユニット、２…記憶ユニット、３…通信インタフェースユニット、１１…センサデータ取得部、１２…センサデータ／文字列変換部、１３…モチーフ検出部、１４…モチーフグループ生成部、１５…モチーフグループ対応付け処理部、１６…モチーフグループ群検出部、２１…文字列記憶部、２２…モチーフ記憶部、２３…モチーフグループ群記憶部。
【図１】
2017156942.tif 000006
【図２】
2017156942.tif 000007
【図３】
2017156942.tif 000008
【図４】
2017156942.tif 000009
【図５Ａ】
2017156942.tif 000010
【図５Ｂ】
2017156942.tif 000011
【図６Ａ】
2017156942.tif 000012
【図６Ｂ】
2017156942.tif 000013