JP6018024B2 - 変化検知装置、変化検知システム、変化検知方法及びプログラム - Google Patents

Description

本発明は、変化検知装置、変化検知システム、変化検知方法及びプログラムに関する。

近年、ユーザが感想、気づき等を短い文書で手軽に投稿（エントリ）し共有するマイクロブログサービスが普及している。このマイクロブログサービスは、一般大衆の身近な意見をタイムリーに得られるため、マーケティング事業方針の判断材料等として注目を集めている。代表的なマイクロブログサービスのいくつかは、コンピュータにより自動でデータを取得可能なＡＰＩ（Application Programming Interface）を公開しており、マイクロブログに逐次エントリされたデータの集合であるマイクロブログストリームデータ（以下、ストリームデータと呼ぶ）の分析が普及しつつある。

上記のストリームデータは、形式的な特徴として、多数の一般ユーザが書き込むため、サービス全体として生成されるデータ量が多い。また、内容的な特徴として、書き込みの対象がユーザの関心事全てに及ぶため内容の種類は多岐にわたるという特徴を持つ。

一般的に、あるデータ特性を持つデータ分析をリアルタイム(タイムリー)に、最小限の費用で効率的に行うためには、分析対象となる所定データ（例えばマーケティング事業方針の判断材料となるターム（商品名など））のみをリアルタイムでフィルタリングし、処理すべきデータ量を削減する。さらに、一定期間内に生成されるデータ量の変化が激しい期間においては、いつもとは違う内容が出現する確率が高いため、データ量の変化が激しい期間を検知し、該当期間に生成されたデータを分析対象データとする。

しかし、マイクロブログサービスに加入しているユーザ、つまり人間がデータの生成主体であるため、生成されるデータ量は、短期的には人間のライフサイクルに従い周期的に変動する。また、長期的にはマイクロブログサービスの人気の推移に従い変化する。また、分析対象毎に生成されるデータ量もばらばらである。よって、分析対象となる所定データの出現頻度パターンの変化が激しい期間を判断するための基準(閾値)は上記要素の状態に従い時々刻々と変化する。このため、全ての要素を分析者が事前に考慮して、分析対象となる所定データの出現頻度パターンの変化が激しい期間をデータ出現頻度変化期間として判断する基準を設定・維持することは難しく、リアルタイムで自律的に変化を検知することは困難である。

上述したストリームデータについて、分析対象となる所定データのデータ出現頻度パターンの変化時点であり、所定データの出現頻度が急激に変化する時点をほぼ同時刻に検出するリアルタイム検知手法の最も簡単な手法としては、予め閾値を設けておき、所定データの出現頻度が閾値を超えた瞬間を変化する時点とみなして通知する手法がある。

また、周辺環境を途切れず測定し、測定値をストリームで伝送する多数の個別センサーで構成されるセンサーネットワークにおいて、センサーのデータ伝送量を減少させるデータ伝送量減少アルゴリズムを、上述したリアルタイム検知に用いる手法もある。データ伝送量減少アルゴリズムでは、自然界で測定されるデータ値は周期性を持つことが多いことに着目している。まず、周期を相互に被らない複数の部分期間に分解し、蓄積された過去のデータから部分期間毎の値の平均と標準偏差を計算する。個別センサーは、実測した値が、平均と標準偏差から計算した範囲を超える場合にデータを送信することでデータの伝送量を減少させている。また、計算した範囲の陳腐化を防ぐため、一定期間毎に過去データを利用して範囲を更新している。このデータ伝送量減少アルゴリズムにおける、センサーがデータを伝送するケースを、変化が発生したケースに置き換えることにより、リアルタイム検知に用いる。

Energy-Efficient Sensor Data Acquisition based on Periodic Patterns, Guan-Rong Lin, Yao-Chung Fan, En Tzu Wang, Tao Zou, Arbee L.P.Chen, 2009 15th International Conference on Parallel and Distributed Systems,IEEE COMPUTER SOCIETY, 2009

しかしながら、予め閾値を設ける手法では、閾値が固定されるため、時間経過、時間帯により正常と見なすことが可能となるような、分析対象となる所定データの出現頻度が異なる環境での検知精度がよくなかった。

また、データ伝送量減少アルゴリズムを用いる手法は、そもそもデータ伝送量の削減を目的とするアルゴリズムによる手法であるため、閾値の範囲外の値が測定されることが必ずしも所定データの出現頻度の変化を示すものではない。データ出現頻度の急激な変化を検知する精度の向上という課題に対して、データ伝送量減少アルゴリズムを用いる手法における詳細な評価と、その評価のフィードバックによる精度の向上は、上述した課題を考慮の対象としていないため、変化の検知精度の向上に寄与しない場合がある。また、一定期間毎に過去データを用い、その範囲を更新しているため、過去データを蓄積する必要があり、更新タイミング以前に判定基準(閾値)が変化した場合、その更新タイミングまで変化を反映できないことがある。

本発明は、上記に鑑みてなされたものであって、ストリームデータに含まれる分析対象となる所定データの出現頻度変化を、リアルタイムに精度よく検知することを可能とする変化検知装置、変化検知システム、変化検知方法及びプログラムを提供することを目的とする。

上述した課題を解決し、目的を達成するために、実施形態にかかる変化検知装置は、所定の周期内で分割した区分期間ごとに集計された、ストリームデータに含まれる所定データの出現頻度に基づいて、将来の区分期間における前記所定データの出現頻度の予測値を算出する予測部と、前記算出された予測値の中の、現在の区分期間における予測値と、前記現在の区分期間で集計された前記所定データの出現頻度との差が、前記区分期間ごとに集計された所定データの出現頻度のパターンに基づく閾値を超える場合に、前記所定データの出現頻度に変化が生じていると判定する判定部と、を備えることを特徴とする。

実施形態にかかる変化検知装置によれば、ストリームデータに含まれる分析対象となる所定データの出現頻度を、リアルタイムに精度よく検知することを可能とする、という効果を奏する。

図１は、実施形態にかかる変化検知システムの構成の一例を示す図である。 図２は、実施形態にかかる変化検知システムの動作の一例を示すラダーチャートである。 図３は、所定データの出現数についての周期を説明する図である。 図４は、所定データの出現頻度の加速度と、時間の経過との関係を例示するグラフである。 図５は、記憶領域の一例を示す図である。 図６−１は、通常予測の更新方式を例示するグラフである。 図６−２は、修正予測の更新方式を例示するグラフである。 図７は、ドリフト効果を例示するグラフである。 図８は、スケールによるバーストの誤検知を例示するグラフである。 図９は、閾値以下のＭＡＣＤ差分の連続出現におけるバーストを例示するグラフである。 図１０は、ドリフトのようなバーストの検知を例示するグラフである。 図１１は、通知部による通知を例示する図である。 図１２は、実施形態にかかる変化検知システムの変化検知装置における処理がコンピュータを用いて具体的に実現されることを示す図である。

以下、添付図面を参照して実施形態にかかる変化検知装置、変化検知システム、変化検知方法及びプログラムを詳細に説明する。なお、以下の説明において、同様の構成要素には共通の符号を付与するとともに、重複する説明を省略する。

図１は、実施形態にかかる変化検知システム１の構成の一例を示す図である。図２は、実施形態にかかる変化検知システム１の動作の一例を示すラダーチャートである。

図１に示すように、変化検知システム１は、パターン検出装置１０、頻度集計装置２０、変化検知装置３０を備え、マイクロブロクサービスなどで多くのユーザが途切れなくエントリするストリームデータにおいて、分析対象となる所定データの出現パターンを認識、そのパターンの出現状況を監視する。そして、変化検知システム１は、所定データの出現頻度が急激に変化する（バースト）時点を、パターン変化の発生時点として、変化時刻とほぼ同時刻に検出して通知する。ここでいう、分析対象となる所定データとは、マーケティング事業方針の判断材料となるタームなどであり、一例としては商品名であってよい。この所定データは、ユーザの入力操作などによって予め登録されているものとする。

パターン検出装置１０は、入力されるストリームデータを逐次監視しており、ストリームデータに対して予め登録した所定データの出現頻度のパターンを検出する（図２：Ｓ１）。パターン検出装置１０は、検出したパターンの説明と検出した事実を示す出現情報を頻度集計装置２０に検出毎にリアルタイムに通知する（図２：Ｓ２）。なお、パターン検出装置１０におけるリアルタイムの通知は、検出と通知の時間差が予め定められた時間以内であることを示す。本実施形態では、この時間差は１０秒以下であるものとする。

パターン検出装置１０が検出する所定データの出現頻度は、周期性をみせる環境があるとする。この周期性は、データをエントリするユーザの生活リズムなどが要因の一例として挙げられる。例えば、所定データが食品名などである場合は、１日周期の中でユーザの食事の時間帯に多くのエントリが見込まれ、食事の時間帯以外ではエントリが見込まれないこととなる。よって、周期を所定の間隔で区分した部分期間（区分期間）で出現頻度の集計を行うと、食事の時間帯に対応した部分期間における所定データの出現頻度が大きく、他の時間帯に対応した部分期間における所定データの出現頻度は小さくなる。

図３は、所定データの出現頻度についての周期を説明する図である。図３において、個々の周期をＴｎとする（ｎは自然数、観測開始時の周期を１とする）。一つの周期は、同じ長さを持ち、それぞれの時間を共有しない固定数の部分期間で構成される。この部分期間の数は分割元となる全ての周期において同一である。それぞれの部分期間は周期を構成する順序により連番を付与する。例えば、図３では周期は３個の部分期間を持ち、各周期を構成する部分期間はその構成順序により、１、２、３の連番が付与されている。

よって、各周期において、部分期間に付与された連番数が同じとなる部分期間は、過去、現在、未来において互いに対応する部分期間となる。例えば、現在時刻が周期Ｔ２の部分期間Ｔ２−２に相当する場合、その部分期間Ｔ２−２と対応する、１周期前の過去の部分期間はＴ１−２である。また、部分期間Ｔ２−２と対応する、未来の周期Ｔｎの部分期間はＴｎ−２である。図３に示すように、所定データの出現頻度は、部分期間Ｔ１−２、Ｔ２−２、…、Ｔｎ−２で大きく、他の部分期間では少なくなるような周期性を示している。

頻度集計装置２０は、検出された所定データの出現頻度を、所定の周期内で分割した部分期間ごとに集計する。具体的には、頻度集計装置２０は、パターン検出装置１０に登録されたパターンのリストを保持しており、パターン検出装置１０からの通知をパターン毎に集計する（図２：Ｓ３）。そして、頻度集計装置２０は、ＲＴＣ（Real Time Clock）機能により計時している時刻をもとに、部分期間が変化する時点で集計結果を頻度情報として変化検知装置３０へ出力する（図２：Ｓ４）。

なお、周期および部分期間については、ユーザの操作入力などを介して予め適正値が設定されているものとする。例えば、周期は１日単位、１周間単位、１月単位などであってよい。また、部分期間は、その周期を等分に分割するものであってよく、周期が１日単位で設定されている場合には、１０分単位、１時間単位などであってよい。

頻度集計装置２０は、集計結果を頻度情報として変化検知装置３０へ出力した後、パターン毎の集計結果を０にリセットし、集計を継続する。

例えば、ある部分期間（Ｔ２−１）中にパターンＡが３回、パターンＢが２回、パターンＣが０回、パターン検出装置１０から通知されたものとする。そして、それに続く部分期間（Ｔ２−２）中に、パターンＡが２回、パターンＢが０回、パターンＣが１回、パターン検出装置１０から通知されたものとする。

頻度集計装置２０は、ある部分期間（Ｔ２−１）に続く部分期間（Ｔ２−２）に遷移する時点で、パターンＡが３回、パターンＢが２回、パターンＣが０回現れた事実を変化検知装置３０に出力する。また、頻度集計装置２０は、続く部分期間（Ｔ２−２）から更に続く部分期間（Ｔ２−３）に遷移する時点で、パターンＡが２回、パターンＢが０回、パターンＣが１回現れた事実を変化検知装置３０に出力する。なお、本実施形態では、説明を簡単にするために０回の場合も通知したが、通知しない場合は０と見なし計算し、０回の場合は通知しなくてもよい。

また、本実施形態では、頻度集計装置２０は所定データの出現頻度パターン毎の出現頻度の単純集計の代わりに、異なるサイズの短い窓と長い窓を用いた出現頻度の指数平滑移動平均(Exponential Moving Average)を計算する。そして、頻度集計装置２０は、計算したＥＭＡ値の内、短い窓を用いたＥＭＡ値を所定データに関する出現頻度（出現数）とし、短い窓を用いたＥＭＡ値から長い窓を用いたＥＭＡ値を引いた差分である、ＭＡＣＤ(Moving Average Convergence and Divergence)の指数平滑移動平均(MACD Histogram)を利用する。

このＭＡＣＤ Ｈｉｓｔｏｇｒａｍは、出現頻度数変化の加速度である。また、ＥＭＡ値の計算は，複数の連続した部分期間で測定された所定データの出現頻度データを入力に用いるが、この計算の入力となる複数の連続した部分期間が窓に該当する。そして、“今現在”を起点として何個の部分期間まで遡るかを定めた値が窓のサイズとなる。例えば、本実施形態では、短い窓の長さを７、長い窓の長さを９、ＭＡＣＤ Ｈｉｓｔｏｇｒａｍを計算するための用いた窓の長さを５としたが、この値はシステムを適用する領域により適切な値を与えることが可能である。

変化検知装置３０は、予測部３１と、判定部３２とを備える。変化検知装置３０は、頻度集計装置２０から出力された頻度情報をもとに、予測部３１、判定部３２によって、所定データの出現頻度が急激に変化するバーストの時点を、パターン変化の発生時点として、変化時刻とほぼ同時刻に検出して通知する処理（図２：Ｓ５）を実行する。

予測部３１は、頻度集計装置２０により部分期間ごとに集計された、ストリームデータに含まれる所定データの出現頻度に基づいて、将来の部分期間における所定データの出現頻度の予測値を算出する（図２：Ｓ５１）。判定部３２は、予測部３１により算出された予測値の中の、現在の部分期間における予測値と、頻度集計装置２０により現在の部分期間として集計された所定データの出現頻度との差が、部分期間ごとに集計された所定データの出現頻度のパターンに基づく閾値を超える場合に、所定データの出現頻度に変化が生じているバーストと判定する（図２：Ｓ５２）。

判定部３２によりバーストとして判定された場合は、現在バーストが生じているとする変化の通知としてディスプレイなどに出力され、ユーザに通知される。また、判定部３２による判定結果（変化判定）は、予測部３１に通知される。予測部３１は、判定結果に基づき、現在の区分期間に対応した将来の区分期間における所定データの出現頻度の予測値を更新する。

図４は、所定データの出現頻度の加速度と、時間の経過との関係を例示するグラフである。具体的には、図４は、データ出現頻度パターンの急激な変化であるバーストが発生した時点（＝データ出現頻度パターンの異常発生のポイント）の検出を具体的に例示するためのグラフである。図４において、グラフの縦軸はＭＡＣＤ Ｈｉｓｔｏｇｒａｍ（加速度）の値を横軸は時間の経過を意味している。また、周期は１日単位であり、棒グラフの一つが一つの部分期間に該当している。

マイクロブログの情報は、ユーザである人間が生成(書き込む)するため、例えば日本のような一定地域に限定した場合、あるパターンの出現頻度は時間帯により変化する。例えば、食べ物に関する話題は食事の時間帯が多く、その他の時間帯にける出現頻度は食事の時間帯に比べて大幅に低下する。

従って、マイクロブログ等の世界では、図４の左から２番目の棒グラフのように、ある時間帯で急激に出現頻度が高くなったとしても、必ずしもバーストが発生しているとは限らない。図４の左から７番目の棒のように他の日の同じ時間帯でも同じ位増加していることがあり得るからである。従って、本実施形態では、上述したケースではバーストと見なさず、図４の左から８番目の棒のように他の日の同じ時間帯と異なって、出現頻度が急激に増加している時間帯ではバーストが生じていると検知する。

このため、予測部３１は、現時点まで実測した部分期間の頻度情報を基に未来の部分期間の予想値を管理する。そして、判定部３２は、部分期間の予測値と、現在の部分期間で実測した頻度情報と評価し、現在の部分期間にバーストが起きているか否かを判定する。

予測部３１は、部分期間の予想値を管理するための記憶領域を確保している。図５は、記憶領域Ｒの一例を示す図である。

図５に示すように、予測部３１は、少なくとも一つの周期を構成する部分期間を管理する記憶領域Ｒを設ける。なお、予測部３１は、複数の周期について、周期ごとに部分期間を管理する記憶領域Ｒを設けてもよい。本実施形態では、一つの周期は１４４個(６×２４)の部分期間で構成されるが、利用者は適用環境に適した値を選択することが可能である。記憶領域Ｒに確保された部分期間には、予測部３１が計算した予測値が格納される。この予測値は該当する部分期間の現在の実測値（頻度情報）を得たタイミングで新たな予測値に更新される。

具体的には、一つの周期は１日であり１日は１４４個のそれぞれの長さが１０分の部分期間で構成される。ここで、現在の時間が１０：０８であるとすると、６１(００：００から１０：１０)番までの部分期間には、未来(明日)の予測が格納されており、６２番から１４４番までの部分期間には今日１０：１０から２４：００までの予測が格納される。そして、予測部３１は、１０：１０に１０：００から１０：１０までの所定データに関する出現頻度データの実測値を計算し、６１番の予測値と、計算した実測値と判定部３２の判定結果を用いて、６１番目の部分期間の予測値(明日の１０：００から１０：１０までの予測値)を計算して更新する。

ここで、予測部３１における予測値の算出（予測値の更新）について、詳細に説明する。図６−１は、通常予測の更新方式を例示するグラフである。図６−２は、修正予測の更新方式を例示するグラフである。

図６−１、６−２に示すように、予測部３１は、現在の部分期間の出現頻度データの実測値（（今日）の最初の棒グラフ）と、その部分期間の出現頻度データの予測値を用い、未来の部分期間の出現頻度データの予測値（（明日）の最初の棒グラフ）を計算する。予測部３１は、予測の際、実測値と予測値に異なる重みを与える。一般的に実測値により重みを与えることにより、未来の予測値が既存の実測履歴を反映しながら、より現在の変化(トレンド)を反映するようになる。

具体的には、予測部３１は、次の式（１）をもとに、（更新方式１．そのまま）、（更新方式２．通常予測）、（更新方式３．修正予測）のいずれかの式を用いて予測値の算出を行う。

式（１）において、ＭＡＣＤＨｉｓｔｏｇｒａｍＲｅａｌ（ｐ，ｔ）は周期ｐの番目の部分期間のＭＡＣＤ Ｈｉｓｔｏｇｒａｍの実測値、ＭＡＣＤＨｉｓｔｏｇｒａｍＰｒｅｄｉｃｔｉｏｎ（ｐ，ｔ）は周期ｐのｔ番目の部分期間のＭＡＣＤ Ｈｉｓｔｏｇｒａｍの予測値を意味する。また、αは重み付けの値を意味する。

本実施形態では、重みαは０．５にしているが、適用先システムにより適切な値を選択可能である。このように未来を予想するにあたり、後述する２個の異常ケースを考慮する必要がある。異常ケースでない場合は、（更新方式２．通常予測）によって、重みα（＝０．５）を与えることにより、未来の予測値が既存の実測履歴を反映しながら、より現在の変化(トレンド)を反映した予測値が算出される。

異常ケースの一つは、現在の実測値がバーストでありかつバーストであることが分かるケースである。また、もう一つの異常ケースは、過去(現在の部分周期の一周期前の部分周期)の部分周期がバーストでありかつ該当過去の部分周期の予測値が存在しなかったケースである。例えば、二番目の異常ケースはシステム稼働の初期に現れる。

一番目の異常ケースは、実測値が異常であるため、この異常な実測値を含め未来を予想すると実態より大きい値を持つ未来予測になる。従って、一番目の異常ケースは、式（１）における（更新方式１．そのまま）のように、既存の予測値をそのまま未来の予測値とする。

二番目の異常ケースは、予測値が過大評価されているため修正する必要がある。具体的には、図６−２のように、現在の実測値をより未来値の予想に反映させる。この場合、予測部３１は、式（１）における（更新方式３．修正予測）によって予測値を算出する。

ここで、（更新方式３．修正予測）の閾値は、次の式（２）で求める。

なお、（更新方式３．修正予測）の閾値は、差分のスケールは実測値と予測値の差分のｌｏｇ値を用いているが、適用先システムにより適切な値を選択可能である。

また、予測部３１は判定部３２の判定補助のため、直近の未来の周期の所定データの最大出現頻度予測値（ＭａｘｉｍｕｍＡｐｐｅａｒａｎｃｅＣｏｕｎｔＰｒｅｄｉｃｔ（ｐ＋１））を次の式（３）を用いて計算する。

また、予測部３１は、未来の部分期間の所定データの現頻度予測値（ＡｐｐｅａｒａｎｃｅＣｏｕｎｔＰｒｅｄｉｃｔ（ｐ＋１， ｔ））を次の式（４）を用いて計算する。

ここで、ＡｐｐｅａｒａｎｃｅＣｏｕｎｔＰｒｅｄｉｃｔの計算方式は、次の式（５）のとおりである。

なお、ＭａｘｉｍｕｍＡｐｐｅａｒａｎｃｅＣｏｕｎｔＰｒｅｄｉｃｔ（ｐ）は周期ｐの所定データの最大の出現頻度の予測値、ＭａｘｉｍｕｍＡｐｐｅａｒａｎｃｅＣｏｕｎｔ（ｐ）は周期ｐの所定データの最大の出現頻度の実測値、ＡｐｐｅａｒａｎｃｅＣｏｕｎｔＰｒｅｄｉｃｔ（ｐ，ｔ）は周期ｐ、部分期間ｔの所定データの最大の出現頻度の予測値、ＡｐｐｅａｒａｎｃｅＣｏｕｎｔＲｅａｌ（ｐ，ｔ）は周期ｐ、部分期間ｔの所定データの最大の出現頻度の実測値をそれぞれ示す。

本実施形態に基づく検証では、ＡＣＣＥＰＴＡＮＣＥ＿ＲＡＴＩＯは１．３、Ｔ２は３０を用いて実施しているが、この値に限定されず、システムを適用する領域により適切な値を与えることが可能である。

判定部３２は、判断部３２１、通知部３２２、フィードバック部３２３を備える。判断部３２１は、予測部３１が計算した現在の部分区間における予想値と、頻度集計装置２０が集計した現在の部分期間の実測値を用い、現在の部分期間の実測値がバーストか否かを判定する（図２：Ｓ５２）。通知部３２２は、判断部３２１の判定結果をユーザと予測部３１とに通知する（図２：Ｓ５３）。

フィードバック部３２３は、通知部３２２がユーザに通知した判定結果の評価（ユーザ評価）を操作入力などによってそのユーザより受け付ける（図２：Ｓ５４）。そして、フィードバック部３２３は、受け付けたユーザ評価を予測部３１にフィードバックする（図２：Ｓ５５）。予測部３１では、フィードバック部３２３のフィードバックを基に、予測部３１における（更新方式１．そのまま）、（更新方式２．通常予測）、（更新方式３．修正予測）の選択にかかる評価（現在の部分期間におけるバースト発生の有無）を修正する。

判断部３２１は、予測部３１が計算した現在の部分区間における予想値と、頻度集計装置２０が集計した現在の部分期間の実測値との差が予め設定された閾値を超えたケースをバーストと判定する。ただし、閾値は、固定されているのではなく、対象となる所定データの出現頻度のパターンの特徴を考慮し自動で調整される。

本実施形態では、パターン毎に、各部分期間で出現頻度（短い窓のＥＭＡ）の規模とその周期での最大値（出現頻度の規模）との比率、部分期間でのＭＡＣＤ ｈｉｓｔｏｇｒａｍの規模、直前のＭＡＣＤ ｈｉｓｔｏｇｒａｍの差（直近の部分期間同士のＭＡＣＤ ｈｉｓｔｏｇｒａｍの差）の履歴を考慮して閾値を決定する。ここでいう規模とは、桁数などである。例えば、出現頻度の規模といった場合は、出現頻度の値の桁数を示し、桁数が大きい場合を出現頻度の規模が大きい、桁数が小さい場合を出現頻度の規模が小さいものとする。

ここで、バーストの判定において考慮すべき事象を、図７、８、９、１０を参照して説明する。図７は、ドリフト効果を例示するグラフである。図８は、スケールによるバーストの誤検知を例示するグラフである。図９は、閾値以下のＭＡＣＤ差分の連続出現におけるバーストを例示するグラフである。図１０は、ドリフトのようなバーストの検知を例示するグラフである。ここで、図７、８、９、１０における点線のグラフは、ある期間に対して、予測により計算した所定データの出現頻度パターンを示す。また、実線のグラフは、実測の所定データの出現頻度パターンを示す。

バーストの判定において考慮すべき事象の一つには、ドリフト効果がある。具体的には、図７に示すように、ドリフト効果とは、周期性のパターンの特性は予測と実測とで同じであるが、そのパターンが現れる部分期間が予測と実測との間で速くなったり遅くなったりする性質である。

人間の目でみた図７の点線のグラフと実線のグラフとの変化の推移は、変化時間のずれはあるものの同じと判断できる。しかし、機械的にＭＡＣＤ ｈｉｓｔｏｇｒａｍの差分を比較して一定閾値以上をバーストとする場合、図７でＤｒｉｆｔと示している部分をバーストと誤検知する可能性が高い。ただし、図１０に示すように、ドリフトのようなバーストについては、正しくバーストとして検知する必要がある。

また、バーストの判定において考慮すべき事象の一つには、平均スケールによる誤検知がある。具体的には、図８に示すように、所定データの出現頻度のパターンの平均スケールが（Ｓｍａｌｌ ｓｃａｌｅ）、（Ｂｉｇ ｓｃａｌｅ）のように異なる場合は、バーストの誤検知が生じることがある。

例えば、図８の（Ｓｍａｌｌ ｓｃａｌｅ）、（Ｂｉｇ ｓｃａｌｅ）のグラフのように、実測値と予測値のＭＡＣＤ ｈｉｓｔｏｇｒａｍ（加速度）の差分が同じの場合、出現頻度の差も同じである。しかし、出現頻度のスケールが小さい（Ｓｍａｌｌ ｓｃａｌｅ）のグラフではバーストと判定できても、出現頻度のスケールが大きい（Ｂｉｇ ｓｃａｌｅ）のグラフでは同じ差をバーストと判定することは困難になる。

また、バーストの判定において考慮すべき事象の一つには、閾値以下のＭＡＣＤ ｈｉｓｔｏｇｒａｍの連続出現がある。図９に示すように、閾値以下のＭＡＣＤ ｈｉｓｔｏｇｒａｍの連続出現によっては、バーストが生じていることがある。ここで、図９の上のグラフはある周期内の所定データの出現頻度のパターンの実測値と予測値である。また、図９の下のグラフは対応するＭＡＣＤ ｈｉｓｔｏｇｒａｍの差分である。また、下のグラフの太い横線はバーストを検知するための固定閾値である。図９に示すように、実際にはバーストであるが、対応するＭＡＣＤ ｈｉｓｔｏｇｒａｍが閾値以下のため、バーストとして検知されないケースがある。

上述した事象を考慮してバーストを判定するため、判断部３２１は、次の式（ａ）〜（ｄ）を用いてバーストであるか否かを判定する。

基本的には式（ａ）のように、判断部３２１は、周期ｐの部分期間ｔの判定スコア（ＩｄｅｎｔｉｆｉｃａｔｉｏｎＳｃｏｒｅ（ｐ，ｔ，ｗ））が閾値Ｔ以上の場合をバースト、Ｔ未満の場合をバーストではないと判定する。

判定スコアは、式（ｂ）のように、周期ｐの部分期間ｔとｔ以前の部分期間ｗ個の部分期間スコア（Ｐａｒｔｉａｌｐｅｒｉｏｄｓｃｏｒｅ（ｐ，ｔ））の合計である。ただし、ｔ−１， ｔ−２， … ｔ−ｗと引いていく過程で値が０以下のｘとなった場合、部分期間は一つ前の周期の部分期間を用いる（ｐ ＝ｐ−１， ｉ ＝ 最大部分期間番号−ｗ）。

部分期間スコアは、式（ｃ）のように、該当期間ｔの部分期間のＭＡＣＤＨｉｓｔｏｇｒａｍの実測値からＭＡＣＤＨｉｓｔｏｇｒａｍの予測値を引いた値に、現在の出現頻度カウンタの規模による重み（式の右側の括弧１番目）、現在の出現頻度カウンタと最大出現頻度カウンタ（予想値）との比率による重み（式の右側の括弧２番目）、括弧２番目の重みのキャンセル関数（式の右側の括弧３番目、式（ｄ）、以下キャンセル関数）をかけた値である。

出現頻度カウンタの規模による重みは、図８を参照して説明したスケールの問題を解決するためである。これにより、ＭＡＣＤＨｉｓｔｏｇｒａｍの実測値とＭＡＣＤＨｉｓｔｏｇｒａｍの予測値の差分（加速度の差）が同じであっても、データ出現頻度の規模が小さい方がよりバーストと判定されやすくなる。

また、現在の出現頻度カウンタと最大出現頻度カウンタ（予想値）との比率による重みは、図７を参照して説明したドリフトの問題を解決するためである。これにより、例えバーストと判定されるＭＡＣＤＨｉｓｔｏｇｒａｍの実測値とＭＡＣＤＨｉｓｔｏｇｒａｍの予測値の差（加速度の差）であっても、現在の出現頻度カウンタと最大出現頻度カウンタに近づいていなければ、バースト成分が低く評価される。

また、キャンセル関数は、図７を用い説明したドリフト問題を解く仮定で、図１０の様にドリフトのようなバーストのケースを検知するためである。実測値と予測値の差が閾値比率Ｗ３以上あるケースにおいては、ドリフトではなくバーストとして判断させるため、式（ｃ）の右側の括弧３番目の重みを打ち消す、括弧３番目の重みの逆数になっている。

また、図９を参照して説明した閾値以下のＭＡＣＤｈｉｓｔｏｇｒａｍの連続出現についての問題を解決するため、式（ｂ）のように直近の部分期間スコアの合計が閾値を超えているかをバースト判定の根拠とする。

なお、本実施形態に基づく検証において、ｗは３、Ｔは８、Ｗ１及びＷ２は１、Ｗ３は０．５を用いたが、利用者は適用環境に適した値を選択することが可能である。

判断部３２１は、上述したバースト判定のための計算を、所定データの出現頻度変化パターン毎に行うため、パターン毎に過去計算した直近のｗ個の部分期間のスコアを管理し、その値を取得可能な装置（記憶領域）を持つ。また、バースト判定のため、予測部３１から部分期間の所定データの出現頻度カウンタ実測値と予測値、出現頻度カウント予測値、ＭＡＣＤ Ｈｉｓｔｏｇｒａｍ実測値と予測値を受け取る。

通知部３２２は、判断部３２１の判定結果を、ユーザと予測部３１とに通知する。ここで、ユーザへの通知は、例えばディスプレイへの表示出力などで行う。図１１は、通知部３２２による通知を例示する図である。

図１１に示すように、判断部３２１がバーストと判断した部分期間に対して、実測値と予想値のそれぞれの絶対値を求め、実測値の絶対値が予想値の絶対値より小さい場合、通知部３２２は予測部３１に対して［更新方式３：修正予測］を通知し、ユーザには正常を通知する。また、予測値の絶対値が高い場合、通知部３２２は予測部３１に対し［更新方式１：そのまま］、ユーザに対しバーストを通知する。判断部３２１がバーストでないと判断したケースでは、通知部３２２は予測部３１に［更新方式１：通常予測］、ユーザに正常を通知する。

フィードバック部３２３は、所定データの出現頻度変化パターンに対し、ランダムな部分期間でのシステムの判定結果（例えば図１１の「ユーザ」項目の内容）と判断に用いた情報（例えば図９に例示したグラフなど）をディスプレイ表示などによりユーザに提示する。そして、フィードバック部３２３は、提示した部分期間におけるユーザ評価をコンソールなどの操作入力を介して受け付ける。

フィードバック部３２３は、システムの判定結果とユーザ評価が一致した場合（例えば判定結果「バースト」に対するユーザ評価「バースト」）はなにもしない。システムの判定結果がバーストでユーザ評価がバーストでない場合、フィードバック部３２３は判定部３２における式（ａ）の閾値Ｔを一定量増加させる。システムの判定結果がバーストでなく、ユーザ評価がバーストの場合、フィードバック部３２３は判定部３２における式（ａ）の閾値Ｔを一定量低減させる。これにより、ユーザ評価を反映したバースト判定を行うことが可能となる。

以上のように、変化検知装置３０は、所定の周期内で分割した部分期間ごとに集計された、ストリームデータに含まれる所定データの出現頻度に基づいて、将来の部分期間における所定データの出現頻度の予測値を算出する。そして、変化検知装置３０は、算出された予測値の中の、現在の部分期間における予測値と、現在の部分期間で集計された所定データの出現頻度との差が、部分期間ごとに集計された所定データの出現頻度のパターンに基づく閾値を超えている場合に、所定データの出現頻度に変化が生じていると判定する。したがって、変化検知装置３０は、計算のためのデータ格納を最低限に抑えながら、ストリームデータに含まれる分析対象となる所定データの出現頻度を、リアルタイムに精度よく検知することができる。

また、変化検知装置３０を用いることで、サーバ等少ない計算リソースとシステムチューニングの専門家ではない一般的な運用人員が、ストリームデータ環境で高精度な所定データに関する出現頻度パターンの変化を認識できるようになる。そのため、企業が大規模ストリームデータの解析を容易に行えるようになり、企業が新たな事業機会創出、製品評判調査、マーケット動向調査をすることが可能となる。また、解析作業において必要な情報を可能な限り削減させることにより、システムを構築に必要なサーバ等計算リソース量を低減することが可能となる。

なお、変化検知装置３０が所定データの出現頻度に変化が生じていると判定している現在の部分期間については、本実施形態では、リアルタイムにストリームデータを解析していることから、現時点の部分期間であるが、特に現時点の部分期間に限定しない。具体的には、現在の部分期間は、現在、判定についての処理対象となっている部分期間という意味であってよい。例えば、処理に必要なデータ（ストリームデータ）をバッファやハードディスクドライブ等の記憶装置に記憶しておき、後でストリームデータを解析する場合もある。この場合は、記憶装置から読み出して、所定データの出現頻度に変化が生じているか否かの処理の対象としている部分期間が現在の部分期間ということとなる。

また、上述した実施形態において説明したパターン検出装置１０、頻度集計装置２０及び変化検知装置３０が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。この場合、コンピュータがプログラムを実行することにより、上述した実施形態にかかる変化検知システム１の変化検知装置３０における処理と同様の効果を得ることができる。さらに、かかるプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませて実行することにより上述した実施形態と同様の処理を実現してもよい。以下に、上述したプログラムを実行するコンピュータの一例を説明する。

図１２は、実施形態にかかる変化検知システムの変化検知装置における処理がコンピュータを用いて具体的に実現されることを示す図である。図１２に例示するように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有し、これらの各部はバス１０８０によって接続される。

メモリ１０１０は、ＲＯＭ（Read Only Memory）１０１１及びＲＡＭ（Random Access Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic Input Output System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブに挿入される。シリアルポートインタフェース１０５０は、例えばマウス１０５１、キーボード１０５２に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１０６１に接続される。

ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、上記のプログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュール１０９３として、例えばハードディスクドライブ１０３１に記憶される。例えば、図１に例示した予測部３１、判定部３２と同様の情報処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０３１に記憶される。

また、上述した実施形態で説明した記憶領域Ｒなどは、ＲＡＭ１０１２に確保される。処理に必要な設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。

なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３やプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等）を介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。また、パターン検出装置１０、頻度集計装置２０、変化検知装置３０を備える変化検知システム１は、上述した一つのコンピュータで実現されるものであってよいことは言うまでもないことである。

１…変化検知システム、１０…パターン検出装置、２０…頻度集計装置、３０…変化検知装置、３１…予測部、３２…判定部、３２１…判断部、３２２…通知部、３２３…フィードバック部、Ｒ…記憶領域、１０００…コンピュータ。

Claims (7)

1. 所定の周期内で分割した区分期間ごとに集計された、投稿データであるストリームデータに含まれる所定データの出現頻度の指数平滑移動平均に基づいて、将来の区分期間における前記所定データの出現頻度の変化の加速度の予測値を算出し、第１の値で重み付けをした前記予測値と、前記第１の値より大きい第２の値で重み付けをした前記出現頻度の変化の加速度の実測値とを基に、前記予測値を更新する予測部と、
   前記算出された予測値の中の、現在の区分期間における予測値と、前記現在の区分期間で集計された前記所定データの出現頻度の変化の加速度との差が、前記区分期間ごとに集計された所定データの出現頻度のパターンに基づく閾値を超えている場合に、前記所定データの出現頻度に変化が生じていると判定する判定部と、
   を備えることを特徴とする変化検知装置。
2. 前記判定部は、前記区分期間ごとに集計された所定データの出現頻度の規模と当該区分期間の周期での出現頻度の規模の最大値との比率、前記出現頻度の変化の加速度の規模、直近の区分期間同士の前記加速度の差をもとに前記閾値を決定する、
   ことを特徴とする請求項１に記載の変化検知装置。
3. 前記判定部の判定結果を前記予測部に通知する通知部を更に備え、前記予測部は、前記通知された判定結果に基づいて、前記現在の区分期間に対応した将来の区分期間における前記所定データの出現頻度の変化の加速度の予測値を更新する、
   ことを特徴とする請求項１又は２に記載の変化検知装置。
4. 前記所定データの出現頻度に変化についてのユーザ入力を受け付け、当該入力結果に基づいた値を前記閾値にフィードバックするフィードバック部を更に備える、
   ことを特徴とする請求項１乃至３の何れか一項に記載の変化検知装置。
5. 入力される投稿データであるストリームデータをもとに、当該ストリームデータに含まれる所定データの出現頻度を検出する検出装置と、
   前記検出された所定データの出現頻度を、所定の周期内で分割した区分期間ごとに集計する集計装置と、
   前記区分期間ごとに集計された所定データの出現頻度の指数平滑移動平均に基づいて、将来の区分期間における前記所定データの出現頻度の変化の加速度の予測値を算出し、第１の値で重み付けをした前記予測値と、前記第１の値より大きい第２の値で重み付けをした前記出現頻度の変化の加速度の実測値とを基に、前記予測値を更新する予測部、および前記算出された予測値の中の、現在の区分期間における予測値と、前記現在の区分期間で集計された前記所定データの出現頻度の変化の加速度との差が、前記区分期間ごとに集計された所定データの出現頻度のパターンに基づく閾値を超える場合に、前記所定データの出現頻度に変化が生じていると判定する判定部を備える変化検知装置と、
   を備えることを特徴とする変化検知システム。
6. 変化検知装置によって実行される変化検知方法であって、
   所定の周期内で分割した区分期間ごとに集計された、投稿データであるストリームデータに含まれる所定データの出現頻度の指数平滑移動平均に基づいて、将来の区分期間における前記所定データの出現頻度の変化の加速度の予測値を算出し、第１の値で重み付けをした前記予測値と、前記第１の値より大きい第２の値で重み付けをした前記出現頻度の変化の加速度の実測値とを基に、前記予測値を更新する予測ステップと、
   前記算出された予測値の中の、現在の区分期間における予測値と、前記現在の区分期間で集計された前記所定データの出現頻度の変化の加速度との差が、前記区分期間ごとに集計された所定データの出現頻度のパターンに基づく閾値を超える場合に、前記所定データの出現頻度に変化が生じていると判定する判定ステップと、
   を含むことを特徴とする変化検知方法。
7. 変化検知装置のコンピュータに、
   所定の周期内で分割した区分期間ごとに集計された、投稿データであるストリームデータに含まれる所定データの出現頻度の指数平滑移動平均に基づいて、将来の区分期間における前記所定データの出現頻度の変化の加速度の予測値を算出し、第１の値で重み付けをした前記予測値と、前記第１の値より大きい第２の値で重み付けをした前記出現頻度の変化の加速度の実測値とを基に、前記予測値を更新する予測ステップと、
   前記算出された予測値の中の、現在の区分期間における予測値と、前記現在の区分期間で集計された前記所定データの出現頻度の変化の加速度との差が、前記区分期間ごとに集計された所定データの出現頻度のパターンに基づく閾値を超える場合に、前記所定データの出現頻度に変化が生じていると判定する判定ステップと、
   を実行させるためのプログラム。

Images