センサにより取得されたサンプルのストリームにおける変化を検出する方法
【課題】この発明方法は、センサによって取得されたサンプルのストリームにおける変化を検出する。
【解決手段】時間経過とともにセンサにより取得されたサンプルストリームがバッファに順次保存され、バッファが時間的に前方にスライドするサンプルのウィンドウを形成するように、バッファが満杯のとき、最も古いサンプルが捨てられて新しいサンプルが保存される。各新しいサンプルに対し、バッファは、サンプルのすべての可能な対の隣接する第１および第２サブウィンドウを含むサブウィンドウへ分割され、最新サンプルが１対のサブウィンドウの第２サブウィンドウに保存される。サンプルの各対の隣接するサブウィンドウの第１および第２サブウィンドウ間の差が求められ、最大差がメリットスコアとして割り当てられる。メリットスコアが所定の閾値より大きければ、サンプルストリームにおける変化を送信する。変化は、突然でも緩やかでもよい。
【解決手段】時間経過とともにセンサにより取得されたサンプルストリームがバッファに順次保存され、バッファが時間的に前方にスライドするサンプルのウィンドウを形成するように、バッファが満杯のとき、最も古いサンプルが捨てられて新しいサンプルが保存される。各新しいサンプルに対し、バッファは、サンプルのすべての可能な対の隣接する第１および第２サブウィンドウを含むサブウィンドウへ分割され、最新サンプルが１対のサブウィンドウの第２サブウィンドウに保存される。サンプルの各対の隣接するサブウィンドウの第１および第２サブウィンドウ間の差が求められ、最大差がメリットスコアとして割り当てられる。メリットスコアが所定の閾値より大きければ、サンプルストリームにおける変化を送信する。変化は、突然でも緩やかでもよい。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は一般に、センサで機器および環境を監視する技術、特にセンサのサンプルにおける変化を検出する技術に関する。
【背景技術】
【０００２】
センサデータ
これまで、センサによる機器および／または環境のリアルタイムの詳細な監視は、大規模で高価な、安全性およびミッション・クリティカルな設置に対してのみ経済的に実現可能であった。ところで、コンピュータ技術の飛躍的進歩、更に詳しく言うと、安価なセンサネットワーク、安価な無線通信、および強力な埋め込みプロセッサの到来は、電気モーター、タービン、電力開閉装置、冷暖房空調機器などの非常に安価な装置に対してばかりでなく、製油、食品加工、製品製造、大規模環境などの産業プロセスの拡大し続けている領域に対しても、器機状態監視（ＥＣＭ）技術を実施することを可能にした。
【０００３】
その結果生じる、センサネットワークから絶えず流れているセンサデータの量の増加は、データをモニタ（監視）する仕事を課されたどんな人間の監視者をも速やかに圧倒するであろう。速やかかつ正確にセンサデータを処理するという問題への唯一の実行可能な解決策は、自動化された変化検出（ＡＣＤ）方法を開発することである。そのような自動化手法は、よく訓練された人間の監視者の能力と汎用性（融通性）に達しそうにないが、自動化手法は、センサデータストリームにおける特定のイベントを探すように設計されると、まだ非常に効果的であり、かつ正確である場合がある。
【０００４】
これらのイベントの中で最も重要なものの１つはセンサデータにおける突然の変化である。そのような突然の変化を検出するのは、取るに足りない問題でない。その理由は、すべての、しかし、最も簡単なデータストリーム以外のすべてのデータストリームは、そのデータを生成する処理における変化が全く起こらないときでさえも、変化するからである。これは、たとえば、データがダイナミカル（動的）システムから来るときのように、処理の自然変動によって、または、測定誤差や隠れ変数などによるノイズによって、引き起こされるかもしれない。そのような場合、突然の変化の検出は統計的に行われる。すなわち、その問題は、その変化の前後に、データがサンプリングされた確率分布間の相違（差）を検出することに帰着する。製造への応用では、このタスクはしばしば統計的プロセス制御（ＳＰＣ）と呼ばれる。ＳＰＣでは、その目的は、データの制御内の分布から或る他の制御しきれない分布への逸脱を検出することにある。
【０００５】
累積集計（ＣＵＳＵＭ）
制御内（可能）および制御外（不可）の分布が既知のパラメトリック形式を有し、それぞれのパラメータが既知であるときには、累積集計（ＣＵＳＵＭ）処理手順が最適であることが知られている。パージュ（Ｐａｇｅ）、「連続測検査スキーム（Ｃｏｎｔｉｎｕｏｕｓ Ｉｎｓｐｅｃｔｉｏｎ Ｓｃｈｅｍｅｓ）」、バイオメトリカ（Ｂｉｏｍｅｔｒｉｋａ）４１、ｐｐ．１００−１１４、１９５４、およびバッセビル他（Ｂａｓｓｅｖｉｌｌｅ ｅｔ ａｌ．）、「突然の変化の検出：理論と応用（Ｄｅｔｅｃｔｉｏｎ ｏｆ Ａｂｒｕｐｔ Ｃｈａｎｇｅｓ：Ｔｈｅｏｒｙ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ）」、 エングルウッド クリフ、ニュージャージー：プレンティスホール（Ｅｎｇｌｅｗｏｏｄ Ｃｌｉｆｆｓ、ＮＪ：Ｐｒｅｎｔｉｃｅ Ｈａｌｌ）、１９９３。
【０００６】
ところで、制御内（可能）およびすべての制御外（不能）分布の明確なモデリングは、典型的には、困難（面倒）で高価なプロセスであり、解決困難でさえあるかもしれない。
したがって、単に、センサデータストリームを検査してそれらの確率分布に関して推論することによって、如何なる変化をも検出できる方法を提供することが望ましい。
【０００７】
突然の変化の検出
現時刻ｔでは、センササンプルストリームからのｄ次元データベクトルはｘｔである。
突然の変化を検出する問題は、そのような変化が現在時刻ｔで起こったか、またはその前に起こったかを判別することである。この問題に対する重要な前提は、変化が永続的である、すなわち、変化が起こった後、その後のリーディング（読み、解釈）が新しい分布からくると、仮定することである。これは、変化が破壊的であるとき、すなわち装置が故障するとき、産業機器に対して典型的な状況である。
【０００８】
その変化の前のすべてのセンサのサンプルは、独立しており、分布ｐ０（ｘ）からサンプリングされた、同じように分布している（ｉ．ｉ．ｄ．）確率変数であると仮定される。同様に、変化の後のすべてのサンプルは分布ｐ１（ｘ）からサンプリングされたｉ．ｉ．ｄ．変数であると仮定される。
【０００９】
分布ｐ０（ｘ）およびｐ１（ｘ）が既知であるとき、パージュ（Ｐａｇｅ）は、その２つの分布に対して電流サンプルの対数尤度を累算して、助変数（ｇｔ＝Ｓｔ−ｍｔ）に基づいて、次式に対する決定を行うＣＵＳＵＭ処理手順について説明している。
【００１０】
【数１】
【００１１】
所定の閾値ｈに対して、ｇｔ＞ｈの場合には、変化が生じたことが宣言される。
この決定は、与えられた偽陽性率に対して検出確率を最大にすることに関して最適になることを示すことができる。
【００１２】
ところで、ＣＵＳＵＭ方法には、分布ｐ０（ｘ）およびｐ１（ｘ）の両方をあらかじめ知っていなければならないという重大な欠点がある。産業機器の通常運転または或る環境における正常な状態に対して正確な確率分布ｐ０（ｘ）を特定することは、典型的には、その器機を設計した、まさしく当該技術者でさえも困難であり、かつ骨が折れることである。制御不能な場合に対してすべての可能な分布ｐ１（ｘ）を特定することは、率直に言えば、不可能であるかもしれない。その上、これらの分布に対して、正しいパラメトリック形式は利用できないかもしれない。
【００１３】
ＣＵＳＵＭのこれらの限界は、よりデータ駆動型であり、あらかじめ特定された分布に頼らない自動化された変化検出（ＡＣＤ）に対する代替方法の大規模な研究に拍車をかけた。この研究の重要な方向は、ノンパラメトリック統計学を使用することである。たとえば、ランク統計、ブロドスキー他（Ｂｒｏｄｓｋｙ ｅｔ ａｌ．），「変化点におけるノンパラメトリック法の問題（Ｎｏｎｐａｒａｍｅｔｒｉｃ Ｍｅｔｈｏｄｓ ｉｎ Ｃｈａｎｇｅ−Ｐｏｉｎｔ Ｐｒｏｂｌｅｍｓ）」、クルワー（Ｋｌｕｗｅｒ）、１９９１。
【００１４】
機械学習
この研究の別のラインは、機械学習に基づくＡＣＤ方法に焦点を合わせている。機械学習で、基本的な考えは、仮定された変化点の前後のサンプルから２つの確率分布を「学習（適合）」し、そして、しばしば情報理論的な距離尺度を使用して、２つの分布の差に対するテストをすることである。たとえば、クルバック・ライブラー・ダイバージェンス（Ｋｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ ｄｉｖｅｒｇｅｎｃｅ）や、レニー・ダイバージェンス（Ｒｅｎｙｉ ｄｉｖｅｒｇｅｎｃｅ）、グーハ他（Ｇｕｈａ ｅｔ ａｌ．）、「エントロピーと情報距離のストリーミングおよびサブリニア近似（Ｓｔｒｅａｍｉｎｇ ａｎｄ ｓｕｂｌｉｎｅａｒ ａｐｐｒｏｘｉｍａｔｉｏｎ ｏｆ ｅｎｔｒｏｐｙ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｄｉｓｔａｎｃｅｓ）」、ＳＯＤＡ’０６の論文集、ｐｐ．７３３．７４２、エーシーエム プレス（ＡＣＭ Ｐｒｅｓｓ）、２００６など。しかしながら、そのような方法には、多くの問題点がある。
【００１５】
第１の問題は、複数のサンプルから２つの分布を学習することである。２つの分布がガウス形として知られているとき、２つのサブウィンドウに対するサンプル平均とバリアンス（変化）を求めることができ、そして、スチューデントのｔ‐統計量を使用することで２つの分布を比較できる。ゴセット（Ｇｏｓｓｅｔ）、「平均の確率誤差（Ｔｈｅ ｐｒｏｂａｂｌｅ ｅｒｒｏｒ ｏｆ ｔｈｅ ｍｅａｎ）」、バイオメトリカ（Ｂｉｏｍｅｔｒｉｋａ）、１９０８。
【００１６】
さらに重要なケース（場合）は、これらの分布の２つの確率密度関数（ｐｄｆｓ）がガウス形でないときである。たとえば、それらの分布が幾つかの異なるモードを切り換えるシステムによりマルチモーダルであるときに、ガウシャンミックスチャモデル（ガウス形混合モデル）は、通常、マルチモーダル分布をモデル化するためには素晴らしい選択であるが、この特定の問題に対してはあまり良くない解決策である。その理由は、ガウス形混合モデルがパラメトリックであり、その適合には各パラメータの複数回の繰り返し調整が必要なためである。ヘイスティー他（Ｈａｓｔｉｅ ｅｔ ａｌ．）、「統計的学習の要素（Ｔｈｅ Ｅｌｅｍｅｎｔｓ ｏｆ Ｓｔａｔｉｓｔｉｃａｌ Ｌｅａｒｎｉｎｇ）」、スプリンガー（Ｓｐｒｉｎｇｅｒ）、２００１。多くの可能な変化点を考えるとき、これは法外に時間がかかる。このために、そのような方法は、スピード（時間）が重視される応用には向かない。
【００１７】
さらに良い代替策は、パーゼンの核密度推定値（Ｐａｒｚｅｎ’ｓ ｋｅｒｎｅｌ ｄｅｎｓｉｔｙ ｅｓｔｉｍａｔｅ）などのメモリベースの方法を使用することである。パーゼン（Ｐａｒｚｅｎ）、「確率密度関数とモードの推定に関して（Ｏｎ ｅｓｔｉｍａｔｉｏｎ ｏｆ ａ ｐｒｏｂａｂｉｌｉｔｙ ｄｅｎｓｉｔｙ ｆｕｎｃｔｉｏｎ ａｎｄ ｍｏｄｅ）」、Ａｎｎ．Ｍａｔｈ．Ｓｔａｔ．３３、ｐｐ．１０６５−１０７６、１９６２、また、確率密度関数のナダラヤ・ワトソン推定（ｔｈｅ Ｎａｄａｒａｙａ−Ｗａｔｓｏｎ ｅｓｔｉｍａｔｅ ｏｆ ａ ｐｒｏｂａｂｉｌｉｔｙ ｄｅｎｓｉｔｙ ｆｕｎｃｔｉｏｎ）として知られている、ヘイスティー他を参照。この方法では、確率密度ｐ（ｘ）は核値（ｋｅｒｎｅｌ ｖａｌｕｅｓ）の正規化された合計として表わされる。
【００１８】
【数２】
【００１９】
ここで、ｗは適宜選択された核関数であり、また、ｘｉ，ｉ＝１，ｎは、モデル化されるべき分布から得られたサンプルである。その核に対してポピュラーな選択は、ガウス分布および第２サブウィンドウ３立方（ｔｒｉｃｕｂｉｃ）分布である。
【００２０】
第２の問題は、それらの２つの分布を、それらのサンプルからの適合後に、比較することである。幾つかのポピュラーな方法は、周知のクルバック・ライブラー・ダイバージェンス（ＫＬダイバージェンス）などの情報理論的な距離尺度を使う。
【００２１】
【数３】
【００２２】
ＫＬダイバージェンスを使用するときの主な困難は、複数のサンプルｘのドメイン全体に亘って統合（積分）する必要性である。これは、１次元のドメインでさえ時間がかかる場合があり、多変量の場合には不可能であるかもしれない。レニー（Ｒｅｎｙｉ）ダイバージェス、ジェンセン・シャノン（Ｊｅｎｓｅｎ−Ｓｈａｎｎｏｎ）距離、ブレグマン（Ｂｒｅｇｍａｎ）ダイバージェンス、およびヘリンジャー・マツシタ・バッタチャリヤ（Ｈｅｌｌｉｎｇｅｒ−Ｍａｔｓｕｓｈｉｔａ−Ｂｈａｔｔａｃｈａｒｙａ）距離などの他のポピュラーな情報理論的な距離尺度を使用しても、同様の統合（積分）に関連した困難につながる。
【００２３】
その結果、多くの研究は、これらの距離の近似計算に集中した。たとえば、グーハ他（Ｇｕｈａ ｅｔ ａｌ．）は、多項式時間で上記距離の大部分に対して近似計算できる幾つかの多項式時間近似方式（ＰＴＡＳ）について記述している。しかし、理論上の観点からは貴重であるが、同様のＰＴＡＳの方法は、実用的応用においてモニタ（監視）するために使用できる実用的方法をそれほどもたらしそうにない。
【発明の開示】
【発明が解決しようとする課題】
【００２４】
機械学習に基づく他の方法は、２つのｐｄｆが推測されるサンプルを保存するバッファの２つのサブウィンドウを使用する。そのウィンドウのサイズ（寸法）を大きくすれば、データがサンプリングされた真実のｐｄｆへの漸近適合性（ａｓｙｍｐｔｏｔｉｃ ｆｉｔ）は良くなる。ところが、ウィンドウの寸法が大きいならば、新しいサンプルは非常にゆっくり変更後の分布に影響し始め、その結果、分布に実際の変化が起きる検出時間を増大させて、突然の変化を検出するのを難しくする。
【課題を解決するための手段】
【００２５】
この発明の実施の形態は、センササンプルのストリームにおける如何なる変化をも検出するための、矛盾に対処する方法を提供する。この発明は、可能な変化点の前後で、変化する寸法のサブウィンドウを使用する。これは、変化後の小さな寸法のサブウィンドウ、たとえば唯１つのサンプルに対して、激烈なまたは突然の変化に対する迅速な反応を可能にすると共に、より大きなウィンドウから学習された分布を使用することによって、より微妙な変化への感度の向上を可能にする。このアイデアを直接実施すると、Ｏ（Ｎ４）への計算の複雑性（計算量）の増大をもたらす。しかし、この発明の実施の形態は、このような複雑さの増大を減少させる方法を効率的に実現することを提供する。
【００２６】
この発明の実施の形態は、多変量センササンプルストリームにおける如何なる変化をも検出するための方法を提供する。すなわち、本方法は、リアルタイムで突然の変化を検出できると共に、より長い時間帯に亘って、ゆっくり生じる変化をも検出できる。本方法は、変化の前後でデータ分布の明確なモデルを利用できないときに、適用できる。
【発明の効果】
【００２７】
本方法は、メモリ（記憶）バッファに保存されたサンプルのスライディングウィンドウで作動する。バッファは、最新のＮ個のサンプルを保存する。各新しいサンプルにより、バッファから最も古いサンプルを置き換えて削除する。本方法は、可能な変化が起こったかもしれない時間の前後の、サンプルの２つの隣接するサブウィンドウへの、バッファのすべての可能な分割を考える。サンプルの各対の隣接するサブウィンドウ間の差が求められ、最大の差がメリット（長所）スコアとして割り当てられる。そして、メリットスコアが所定の閾値より大きければ、サンプルのストリームにおける変化を送信することができる。
【００２８】
本方法の１つの実施の形態は、サンプルのサブウィンドウの対の間の平均ユークリッド距離を決定変数として測定する。本方法の他の実施の形態は、従来のＣＵＳＵＭ方法に基づいている。しかし、対照的に、従来の方法では、確率密度関数は未知であるが、本方法は、既知の分布の対数尤度推定値を使用する代わりに、パーゼン（Ｐａｒｚｅｎ）の核密度推定値で分布を推測する。
【発明を実施するための最良の形態】
【００２９】
実施の形態１．
図１Ａは、センサ１０２により機器および／または環境１０３から時間経過とともに順次取得された多変量センサデータサンプルストリーム１０１における如何なる変化をも検出するための方法１００を示す。サンプル１０１はバッファ１７０に保存（記憶）１１０され、そこでは、バッファ１７０が時間的に前方にスライド（移動）するサンプルのウィンドウを形成するように、バッファ１７０が満杯のとき、最も古いサンプルが捨てられ、新しいサンプルが保存される。
【００３０】
次に、各新しいサンプルに対して、バッファは、可能な変化が生じたかもしれない時間１７１の前後のサンプルのすべての可能な対の隣接するサブウィンドウ１１１へ分割され１２０、最も新しいサンプルがその１対のサブウィンドウの第２のサブウィンドウに保存される。サンプルの各対のすべての可能な隣接するサブウィンドウ１１１間の差１３１が決定される１３０。最大の差はメリット（長所）スコアとして割り当てられ、そして、それは閾値化され１４０、またメリットスコアが所定の閾値より大きければ、変化１５１は送信される１５０。
【００３１】
この発明のすべての実施の形態は可変サイズを有するサンプルの複数組の近接するウィンドウで作動する。すなわち、本方法は、サイズＮのサンプルのバッファ１７０のすべての可能なパーティション（分割）を考える。両方の方法は、そのメモリバッファのすべての可能な分割を考える計算コストを可成り減少させるのに利用できる共通の計算構造を共有する。両方の方法は、最新のセンササンプルを含むバッファΓｔで働き、そのバッファΓｔは、便宜的に、ｘ１（最も古いサンプル）からｘＮ（最も新しいサンプル）まで常に再番号付けされる。すなわち、該バッファは、時間的に前方にスライド（移動）する複数のサンプルの１つのウィンドウである。
【００３２】
差の処理手順１３０αは、変化がそのバッファにおける複数のサンプルのスパン（期間）内に起こった可能性に比例する定量的なメリットスコアΥαｔを決定する。特に、メリットスコアΥαｔは、バッファ１７０の２つのサブウィンドウ間の距離尺度でありうるが、これに限定されるものではない。典型的には、従来の方法は、単にそのバッファを複数のサンプルの２つの等しいサブウィンドウに分割して、これら２つの等しい部分の差に対して検定（テスト）される。対照的に、我々は、そのバッファを、単一のサンプルを保存するサブウィンドウを含む、すべての可能な対のサブウィンドウに分割する。
【００３３】
図に１Ｂに示すように、ベクトルｘの形式の、サンプル１０１の時間的に順序づけられたウィンドウが、バッファ１７０に連続して（順番に）保存される。以下に述べる方法は、複数のセンササンプルｘの１つのウィンドウの複数のサブウィンドウのすべての可能な対のインデックス（ｉ、ｊ）を考える。そこで、１≦ｉ≦ｊ≦Ｎであり、複数のサンプルｘ１５２を格納するバッファΓｔ１７０は２つの隣接するサブウィンドウγｔｉ，ｊ−１およびγｔｊ，Ｎに分割される。
【００３４】
ここで、時間ｔは左から右へ増大し、次式が成立する。
【００３５】
【数４】
【００３６】
図２Ａは、サンプル１〜Ｎを有するバッファ１７０を示す。インデックスｉを有するサンプルは、その対の第１のサブウィンドウの始まり（開始）を定義し、また、インデックスｊを有するサンプルは第２のサブウィンドウの第１のサンプルを定義し、また、それぞれ分割１７１に関連する、仮定された変化点を定義する。第１のサブウィンドウのエンド（終端）のサンプルは、インデックスｊ−１を有し、その１対のサブウィンドウが接近（隣接）することを保証するが、第２のサブウィンドウのエンド（終端）は常に最も新しいサンプル（ｘＮ）である。
【００３７】
２つのサブウィンドウで保存されたサンプルの２つのサブセット（部分集合）は、それぞれ不等数のサンプルを持つことができる。１つのサブウィンドウは、単一のサンプルから構成されさえするかもしれない。したがって、複数のサンプルのサブウィンドウは一つまたは複数のサンプルを含むことができ、すなわち、１つのサブウィンドウ内のサンプルの数は範囲［１、Ｎ−１］でありうる。
【００３８】
差すなわちメリットスコアΥαｔ（ｉ，ｊ）が、リストに載っている制約条件にしたがって、各可能な対のサブウィンドウに対して求められるならば、全体のメリットスコアは、次式に示すように、すべての分割に亘って最大である。
【００３９】
【数５】
【００４０】
次に、モデリングの問題は、何れのメリットスコアを使用すべきかを判別することである。コンピュータの問題は、各新しいサンプルｘｔに対して計算上効率的な方法でこれを行うことである。
【００４１】
メモリベースのグラフ理論的な処理手順（ＭＢ−ＧＴ）
図２Ｂに示されるように、２の間の差２００（距離）に複数のサンプルの２つのサブウィンドウ２２１−２２２の２つの分布２１１−２１２間の差２００（距離）を求めるという問題に対する１つの解決策は、それらの複数のサンプル自体の間の平均距離（差）を求めることである。各サンプルは多次元のユークリッド空間におけるデータ点であるから、複数のサンプルｘｋおよびｘｌのサブウィンドウ間の固有距離尺度（ｎａｔｕｒａｌ ｄｉｓｔａｎｃｅ ｍｅａｓｕｒｅ）はそれらのユークリッド距離であり、次式で表される。
ｄｋ，ｌ＝｜｜ｘｋ−ｘｌ｜｜．
【００４２】
上記のように特定されたインデックス対（ｉ、ｊ）により定義された特別の分割に対して、次式に示すように、複数のサンプルの２つのサブウィンドウ間の平均距離を求めることができる。
【００４３】
【数６】
【００４４】
このメモリベースのグラフ理論的な方法は、次式のように、メリットスコアを有する。
【００４５】
【数７】
【００４６】
各Ｃｉｊを求めることはＯ（Ｎ２）の複雑さ（コンプレクシティ）であり、考慮すべきＯ（Ｎ２）個のそのような項（ターム）があり、全体の複雑さはＯ（Ｎ４）である。この複雑さは、実際的応用のためには、容認できない。
【００４７】
ところで個々のＣｉｊ項の判定には、計算の複雑性をＯ（Ｎ２）まで引き下げるために利用できる或る程度の冗長度と反復的な構造がある。
【００４８】
ここで、我々が次式のように定義する。
【００４９】
【数８】
【００５０】
このとき、次のような再帰的な関係が成立する。
【００５１】
【数９】
【００５２】
図３に示されるように、これらの再帰（リカランス）は次のような効率的な計算プロセスを示唆する。値βｉ，ｊおよびＣ’ｉ，ｊは概念的にマトリクスと同様のデータ構造３０１−３０２で保存される。このマトリクスは制約条件ｉ＜ｊによる上三角行列である。計算は、定義上は零である単一の要素Ｃ’Ｎ，Ｎを有する、このマトリクスの最下段の行３１０から始めることができる。前の行より１つ上の各行１≦ｉ≦Ｎに対して、最下段から最上段に進んで行き、次の２つの工程が行なわれる。
１）すべての値βｉ，ｊが、それらの直ぐ右隣のサンプルから、右から左に進んで、次の再帰式を使用して再帰的に計算される。
【００５３】
【数１０】
【００５４】
２）すべての値Ｃ’ｉ，ｊが、各値βｉ，ｊおよび現在の行の直ぐ下の行の値Ｃ’ｉ＋１，ｊから、再帰式Ｃ’ｉ，ｊ＝Ｃ’ｉ＋１，ｊ＋βｉ，ｊを使用して計算される。
【００５５】
メリットスコアΥαｔを求めることは、正規化を行いかつ最大値を求めるだけなので、個々の項Ｃ’ｉ，ｊの計算と同時に行うことができる。このため、すべての値Ｃ’ｉ，ｊおよびβｉ，ｊをバッファに保存する必要はない。値βｉの現在行ｉに対してＮ個のサンプルのサイズのバッファを確保し、また、Ｃ’ｉ，ｊおよびＣ’ｉ＋１，ｊに対して同じサイズの２つのバッファを確保すれば充分である。したがって、この処理手順に関するメモリ要求条件はＯ（Ｎ）に過ぎず、また、計算の複雑さはＯ（Ｎ２）に過ぎない。
【００５６】
メモリベースのＣＵＳＵＭ処理手順（ＭＢ−ＣＵＳＵＭ）
図４Ａに示されるように、この発明の第２の実施の形態は、本方法が或るモデリング条件の下で最適な変化の検出を実現するのを可能にする確率的な基礎を有する。サンプルの分布が未知であるので、我々は最初にパーゼンの核密度推定値、たとえば、ガウスまたは３立方（ｔｒｉｃｕｂｉｃ）確率分布関数で分布について学習する。図４Ａでは、垂直軸が分布の確率密度、また水平軸が時間を表す。
【００５７】
同時に、非常に異なる理論的基盤にもかかわらず、第２の方法は実施の形態１と同様の計算構造を持っている。我々は、同様に重要な計算の複雑さの改善を実現するために、この構造を如何に活用できるかについて説明する。
【００５８】
ＣＵＳＵＭの導出に続いて、私たちはバッファ１７０に保存されたＮ個のサンプル内の可能な変化に関して以下の仮説を考える。
【００５９】
【数１１】
【００６０】
ここで、我々は、最新のＮ−ｉ＋１のサンプルが取得されたが、何ら変化が生じないという帰無（ヌル）仮説Ｈｉ，０と、そのような変化が生じたという複数の対立仮説Ｈｉ，ｊについて考える。始めのインデックスｉを導入することによって、我々は、テストされる仮説のセット（組）を、ウィンドウ内のＮ個のすべてのサンプルを必ずしも使用するわけではないものに拡大している。
【００６１】
本願に引用して援用するネイマン・ピアソンの補助定理（ホーエル他（Ｈｏｅｌ ｅｔ ａｌ．）、「仮説検定（Ｔｅｓｔｉｎｇ Ｈｙｐｏｔｈｅｓｅｓ）」、統計理論への入門の第３章（Ｃｈ．３ ｉｎ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｓｔａｔｉｓｔｉｃａｌ Ｔｈｅｏｒｙ）、ニューヨーク（Ｎｅｗ Ｙｏｒｋ）：ホートン・ミフリン（Ｈｏｕｇｈｔｏｎ Ｍｉｆｆｌｉｎ），ｐｐ．５６−６７，１９７１）によれば、それぞれの特定の仮説Ｈｉ，ｊとＨｉ，０を検定（テスト）するときに行うことができる最も良い検定、すなわち偽の帰無（ｆａｌｓｅ ｎｕｌｌ）仮説を棄却する最も高い確率を有する検定は、次式で表す尤度比である。
【００６２】
【数１２】
【００６３】
便宜的に、対数尤度比率Ｓｉ，ｊ＝ｌｏｇ（Λｉｊ）が一般的に使用される。我々の方法では、我々は、真のｐｄｆ（ｐ０およびｐ１）を、式（１）に示すように、それらの核密度推定値で置換して、次式（５）を得る。
【００６４】
【数１３】
【００６５】
ここで、ｗｌ、ｋはその対のサンプル（ｘｌ、ｘｋ）対するカーネルウエイト（ｋｅｒｎｅｌ ｗｅｉｇｈｔ）であり、また、ウエイトｗｌ，ｋ＝ｗ（ｄｌ，ｋ）が成立する。最大尤度原理を使用することによって、この処理手順に対するメリットスコアは次式により表される。
【００６６】
【数１４】
【００６７】
上述のように、メリットスコアの計算は、Ｏ（Ｎ４）の計算複雑さを有する。しかし、このメリットスコアは、計算複雑さを減少させるのに再び利用できるこの発明の実施の形態の方法に対するメリットスコアに類似する構造を有する。
【００６８】
再び、図４Ｂに示すように、我々は、概念的にウィンドウＳｉ，ｊおよびＶ’ｉ，ｊ４０１−４０２の値を三角形のデータ構造において組織化して、次式のように助変数を定義できる。
【００６９】
【数１５】
【００７０】
計算すべき項はＯ（Ｎ３）ｖｌｉ，ｊであるように見えるが、式（５）を次式のように再帰的に再公式化する。
【００７１】
【数１６】
【００７２】
これにより、我々は、必ずしもすべての項が必要になるわけではないことを確信できる。さらにμ’ｊ＝μｊｊ、およびｖ’ｉ，ｊ＝ｖｊｉ，ｊを定義することによって、我々は、効率的な処理手順に対する基礎として以下の式を使用できる。
【００７３】
【数１７】
【００７４】
ｖ’ｉ，ｊに対する項だけが再帰的であること、すなわちμｊｊに対する項は直接的に計算されることに注意すべきである。これらの式は以下の処理手順を示唆する。
【００７５】
Ｓ１：式（８）ごとに、μ’ｊをｊ＝１，Ｎに対して直接的に計算する。
この計算は複雑さＯ（Ｎ２）を有するが、その結果をＯ（Ｎ）スペースに保存することができる。
【００７６】
Ｓ２：マトリクスＳｉ，ｊの各行ｉ＝Ｎ，１に対して、最下段行４１０（ｉ＝Ｎ）から始めて、第１行（ｉ＝１）まで上方に移動して、以下の２つの工程を行なう。
Ｓ２．１：式（８）ごとに、ｉ＋１とＮとの間のｊの各値に対して、下の行の対応するｖ’ｉ＋１，ｊおよびｗｊ，ｉからｖ’ｉ，ｊを計算する。
Ｓ２．２：Ｎとｉ＋１との間のｊの各値に対して、式（Ｓｉ，ｊ＝Ｓｉ，ｊ＋１＋ｌｏｇμ’ｊ−ｌｏｇｖ’ｉ，ｊ＋ｌｏｇ（ｊ−ｉ）−ｌｏｇ（Ｎ−ｊ＋１）を使用して、すべてのｉ＝１，Ｎに対して、Ｓｉ，Ｎ＋１＝０から始めて、Ｓｉ，ｊをその直ぐ右の値Ｓｉ，ｊ＋１から計算する。この工程における計算は、厳密に右から左（ｊ＝Ｎ、ｉ＋１）へ進む。
【００７７】
図５は、さらに詳細に判別する第１のメモリベースのグラフ理論的な（ＭＢ−ＧＴ）方法に対する擬似コードを示す。図３は判別する第２のメモリベースの累積集計（ＭＢ−ＣＵＳＵＭ）方法に対する変数を示し、また、図４は擬似コードをさらに詳細に示す。
【００７８】
この発明は好適な実施の形態を例に挙げて説明したが、この発明の精神および範囲内で種々の他の改変および変更を行うことができることを理解すべきである。したがって、添付クレームの目的は、この発明の真実の精神および範囲に含まれるようなすべての変形例および変更例をカバーすることである。
【図面の簡単な説明】
【００７９】
【図１Ａ】この発明の実施の形態１による多変量センサデータサンプルストリームにおける変化を検出するための方法のフロー図である。
【図１Ｂ】この発明の実施の形態１によるセンササンプルを保存（記憶）するバッファのブロック図である。
【図２Ａ】互いに等しくない（不等の）サブウィンドウに分割された、図２のバッファのブロック図である。
【図２Ｂ】この発明の実施の形態１によるサンプル値の異なる分布のブロック図である。
【図３】この発明の実施の形態１によるサンプルの差を求めるための三角形のデータ構造のブロック図である。
【図４Ａ】この発明の実施の形態１による核関数である。
【図４Ｂ】この発明の実施の形態１による三角形のデータ構造のブロック図である。
【図５】この発明の実施の形態１によるセンサデータにおける突然の変化を検出するためのメモリベースのグラフ理論的な（ＭＢ−ＧＴ）方法のための擬似コードのブロック図である。
【図６】この発明の実施の形態１によるセンサデータにおける突然の変化を検出するためのメモリベースの累積集計（ＭＢ−ＣＵＳＵＭ）方法で使用される変数のブロック図である。
【図７】メモリベースの累積集計方法で使用される擬似コードのブロック図である。
【技術分野】
【０００１】
この発明は一般に、センサで機器および環境を監視する技術、特にセンサのサンプルにおける変化を検出する技術に関する。
【背景技術】
【０００２】
センサデータ
これまで、センサによる機器および／または環境のリアルタイムの詳細な監視は、大規模で高価な、安全性およびミッション・クリティカルな設置に対してのみ経済的に実現可能であった。ところで、コンピュータ技術の飛躍的進歩、更に詳しく言うと、安価なセンサネットワーク、安価な無線通信、および強力な埋め込みプロセッサの到来は、電気モーター、タービン、電力開閉装置、冷暖房空調機器などの非常に安価な装置に対してばかりでなく、製油、食品加工、製品製造、大規模環境などの産業プロセスの拡大し続けている領域に対しても、器機状態監視（ＥＣＭ）技術を実施することを可能にした。
【０００３】
その結果生じる、センサネットワークから絶えず流れているセンサデータの量の増加は、データをモニタ（監視）する仕事を課されたどんな人間の監視者をも速やかに圧倒するであろう。速やかかつ正確にセンサデータを処理するという問題への唯一の実行可能な解決策は、自動化された変化検出（ＡＣＤ）方法を開発することである。そのような自動化手法は、よく訓練された人間の監視者の能力と汎用性（融通性）に達しそうにないが、自動化手法は、センサデータストリームにおける特定のイベントを探すように設計されると、まだ非常に効果的であり、かつ正確である場合がある。
【０００４】
これらのイベントの中で最も重要なものの１つはセンサデータにおける突然の変化である。そのような突然の変化を検出するのは、取るに足りない問題でない。その理由は、すべての、しかし、最も簡単なデータストリーム以外のすべてのデータストリームは、そのデータを生成する処理における変化が全く起こらないときでさえも、変化するからである。これは、たとえば、データがダイナミカル（動的）システムから来るときのように、処理の自然変動によって、または、測定誤差や隠れ変数などによるノイズによって、引き起こされるかもしれない。そのような場合、突然の変化の検出は統計的に行われる。すなわち、その問題は、その変化の前後に、データがサンプリングされた確率分布間の相違（差）を検出することに帰着する。製造への応用では、このタスクはしばしば統計的プロセス制御（ＳＰＣ）と呼ばれる。ＳＰＣでは、その目的は、データの制御内の分布から或る他の制御しきれない分布への逸脱を検出することにある。
【０００５】
累積集計（ＣＵＳＵＭ）
制御内（可能）および制御外（不可）の分布が既知のパラメトリック形式を有し、それぞれのパラメータが既知であるときには、累積集計（ＣＵＳＵＭ）処理手順が最適であることが知られている。パージュ（Ｐａｇｅ）、「連続測検査スキーム（Ｃｏｎｔｉｎｕｏｕｓ Ｉｎｓｐｅｃｔｉｏｎ Ｓｃｈｅｍｅｓ）」、バイオメトリカ（Ｂｉｏｍｅｔｒｉｋａ）４１、ｐｐ．１００−１１４、１９５４、およびバッセビル他（Ｂａｓｓｅｖｉｌｌｅ ｅｔ ａｌ．）、「突然の変化の検出：理論と応用（Ｄｅｔｅｃｔｉｏｎ ｏｆ Ａｂｒｕｐｔ Ｃｈａｎｇｅｓ：Ｔｈｅｏｒｙ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ）」、 エングルウッド クリフ、ニュージャージー：プレンティスホール（Ｅｎｇｌｅｗｏｏｄ Ｃｌｉｆｆｓ、ＮＪ：Ｐｒｅｎｔｉｃｅ Ｈａｌｌ）、１９９３。
【０００６】
ところで、制御内（可能）およびすべての制御外（不能）分布の明確なモデリングは、典型的には、困難（面倒）で高価なプロセスであり、解決困難でさえあるかもしれない。
したがって、単に、センサデータストリームを検査してそれらの確率分布に関して推論することによって、如何なる変化をも検出できる方法を提供することが望ましい。
【０００７】
突然の変化の検出
現時刻ｔでは、センササンプルストリームからのｄ次元データベクトルはｘｔである。
突然の変化を検出する問題は、そのような変化が現在時刻ｔで起こったか、またはその前に起こったかを判別することである。この問題に対する重要な前提は、変化が永続的である、すなわち、変化が起こった後、その後のリーディング（読み、解釈）が新しい分布からくると、仮定することである。これは、変化が破壊的であるとき、すなわち装置が故障するとき、産業機器に対して典型的な状況である。
【０００８】
その変化の前のすべてのセンサのサンプルは、独立しており、分布ｐ０（ｘ）からサンプリングされた、同じように分布している（ｉ．ｉ．ｄ．）確率変数であると仮定される。同様に、変化の後のすべてのサンプルは分布ｐ１（ｘ）からサンプリングされたｉ．ｉ．ｄ．変数であると仮定される。
【０００９】
分布ｐ０（ｘ）およびｐ１（ｘ）が既知であるとき、パージュ（Ｐａｇｅ）は、その２つの分布に対して電流サンプルの対数尤度を累算して、助変数（ｇｔ＝Ｓｔ−ｍｔ）に基づいて、次式に対する決定を行うＣＵＳＵＭ処理手順について説明している。
【００１０】
【数１】
【００１１】
所定の閾値ｈに対して、ｇｔ＞ｈの場合には、変化が生じたことが宣言される。
この決定は、与えられた偽陽性率に対して検出確率を最大にすることに関して最適になることを示すことができる。
【００１２】
ところで、ＣＵＳＵＭ方法には、分布ｐ０（ｘ）およびｐ１（ｘ）の両方をあらかじめ知っていなければならないという重大な欠点がある。産業機器の通常運転または或る環境における正常な状態に対して正確な確率分布ｐ０（ｘ）を特定することは、典型的には、その器機を設計した、まさしく当該技術者でさえも困難であり、かつ骨が折れることである。制御不能な場合に対してすべての可能な分布ｐ１（ｘ）を特定することは、率直に言えば、不可能であるかもしれない。その上、これらの分布に対して、正しいパラメトリック形式は利用できないかもしれない。
【００１３】
ＣＵＳＵＭのこれらの限界は、よりデータ駆動型であり、あらかじめ特定された分布に頼らない自動化された変化検出（ＡＣＤ）に対する代替方法の大規模な研究に拍車をかけた。この研究の重要な方向は、ノンパラメトリック統計学を使用することである。たとえば、ランク統計、ブロドスキー他（Ｂｒｏｄｓｋｙ ｅｔ ａｌ．），「変化点におけるノンパラメトリック法の問題（Ｎｏｎｐａｒａｍｅｔｒｉｃ Ｍｅｔｈｏｄｓ ｉｎ Ｃｈａｎｇｅ−Ｐｏｉｎｔ Ｐｒｏｂｌｅｍｓ）」、クルワー（Ｋｌｕｗｅｒ）、１９９１。
【００１４】
機械学習
この研究の別のラインは、機械学習に基づくＡＣＤ方法に焦点を合わせている。機械学習で、基本的な考えは、仮定された変化点の前後のサンプルから２つの確率分布を「学習（適合）」し、そして、しばしば情報理論的な距離尺度を使用して、２つの分布の差に対するテストをすることである。たとえば、クルバック・ライブラー・ダイバージェンス（Ｋｕｌｌｂａｃｋ−Ｌｅｉｂｌｅｒ ｄｉｖｅｒｇｅｎｃｅ）や、レニー・ダイバージェンス（Ｒｅｎｙｉ ｄｉｖｅｒｇｅｎｃｅ）、グーハ他（Ｇｕｈａ ｅｔ ａｌ．）、「エントロピーと情報距離のストリーミングおよびサブリニア近似（Ｓｔｒｅａｍｉｎｇ ａｎｄ ｓｕｂｌｉｎｅａｒ ａｐｐｒｏｘｉｍａｔｉｏｎ ｏｆ ｅｎｔｒｏｐｙ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｄｉｓｔａｎｃｅｓ）」、ＳＯＤＡ’０６の論文集、ｐｐ．７３３．７４２、エーシーエム プレス（ＡＣＭ Ｐｒｅｓｓ）、２００６など。しかしながら、そのような方法には、多くの問題点がある。
【００１５】
第１の問題は、複数のサンプルから２つの分布を学習することである。２つの分布がガウス形として知られているとき、２つのサブウィンドウに対するサンプル平均とバリアンス（変化）を求めることができ、そして、スチューデントのｔ‐統計量を使用することで２つの分布を比較できる。ゴセット（Ｇｏｓｓｅｔ）、「平均の確率誤差（Ｔｈｅ ｐｒｏｂａｂｌｅ ｅｒｒｏｒ ｏｆ ｔｈｅ ｍｅａｎ）」、バイオメトリカ（Ｂｉｏｍｅｔｒｉｋａ）、１９０８。
【００１６】
さらに重要なケース（場合）は、これらの分布の２つの確率密度関数（ｐｄｆｓ）がガウス形でないときである。たとえば、それらの分布が幾つかの異なるモードを切り換えるシステムによりマルチモーダルであるときに、ガウシャンミックスチャモデル（ガウス形混合モデル）は、通常、マルチモーダル分布をモデル化するためには素晴らしい選択であるが、この特定の問題に対してはあまり良くない解決策である。その理由は、ガウス形混合モデルがパラメトリックであり、その適合には各パラメータの複数回の繰り返し調整が必要なためである。ヘイスティー他（Ｈａｓｔｉｅ ｅｔ ａｌ．）、「統計的学習の要素（Ｔｈｅ Ｅｌｅｍｅｎｔｓ ｏｆ Ｓｔａｔｉｓｔｉｃａｌ Ｌｅａｒｎｉｎｇ）」、スプリンガー（Ｓｐｒｉｎｇｅｒ）、２００１。多くの可能な変化点を考えるとき、これは法外に時間がかかる。このために、そのような方法は、スピード（時間）が重視される応用には向かない。
【００１７】
さらに良い代替策は、パーゼンの核密度推定値（Ｐａｒｚｅｎ’ｓ ｋｅｒｎｅｌ ｄｅｎｓｉｔｙ ｅｓｔｉｍａｔｅ）などのメモリベースの方法を使用することである。パーゼン（Ｐａｒｚｅｎ）、「確率密度関数とモードの推定に関して（Ｏｎ ｅｓｔｉｍａｔｉｏｎ ｏｆ ａ ｐｒｏｂａｂｉｌｉｔｙ ｄｅｎｓｉｔｙ ｆｕｎｃｔｉｏｎ ａｎｄ ｍｏｄｅ）」、Ａｎｎ．Ｍａｔｈ．Ｓｔａｔ．３３、ｐｐ．１０６５−１０７６、１９６２、また、確率密度関数のナダラヤ・ワトソン推定（ｔｈｅ Ｎａｄａｒａｙａ−Ｗａｔｓｏｎ ｅｓｔｉｍａｔｅ ｏｆ ａ ｐｒｏｂａｂｉｌｉｔｙ ｄｅｎｓｉｔｙ ｆｕｎｃｔｉｏｎ）として知られている、ヘイスティー他を参照。この方法では、確率密度ｐ（ｘ）は核値（ｋｅｒｎｅｌ ｖａｌｕｅｓ）の正規化された合計として表わされる。
【００１８】
【数２】
【００１９】
ここで、ｗは適宜選択された核関数であり、また、ｘｉ，ｉ＝１，ｎは、モデル化されるべき分布から得られたサンプルである。その核に対してポピュラーな選択は、ガウス分布および第２サブウィンドウ３立方（ｔｒｉｃｕｂｉｃ）分布である。
【００２０】
第２の問題は、それらの２つの分布を、それらのサンプルからの適合後に、比較することである。幾つかのポピュラーな方法は、周知のクルバック・ライブラー・ダイバージェンス（ＫＬダイバージェンス）などの情報理論的な距離尺度を使う。
【００２１】
【数３】
【００２２】
ＫＬダイバージェンスを使用するときの主な困難は、複数のサンプルｘのドメイン全体に亘って統合（積分）する必要性である。これは、１次元のドメインでさえ時間がかかる場合があり、多変量の場合には不可能であるかもしれない。レニー（Ｒｅｎｙｉ）ダイバージェス、ジェンセン・シャノン（Ｊｅｎｓｅｎ−Ｓｈａｎｎｏｎ）距離、ブレグマン（Ｂｒｅｇｍａｎ）ダイバージェンス、およびヘリンジャー・マツシタ・バッタチャリヤ（Ｈｅｌｌｉｎｇｅｒ−Ｍａｔｓｕｓｈｉｔａ−Ｂｈａｔｔａｃｈａｒｙａ）距離などの他のポピュラーな情報理論的な距離尺度を使用しても、同様の統合（積分）に関連した困難につながる。
【００２３】
その結果、多くの研究は、これらの距離の近似計算に集中した。たとえば、グーハ他（Ｇｕｈａ ｅｔ ａｌ．）は、多項式時間で上記距離の大部分に対して近似計算できる幾つかの多項式時間近似方式（ＰＴＡＳ）について記述している。しかし、理論上の観点からは貴重であるが、同様のＰＴＡＳの方法は、実用的応用においてモニタ（監視）するために使用できる実用的方法をそれほどもたらしそうにない。
【発明の開示】
【発明が解決しようとする課題】
【００２４】
機械学習に基づく他の方法は、２つのｐｄｆが推測されるサンプルを保存するバッファの２つのサブウィンドウを使用する。そのウィンドウのサイズ（寸法）を大きくすれば、データがサンプリングされた真実のｐｄｆへの漸近適合性（ａｓｙｍｐｔｏｔｉｃ ｆｉｔ）は良くなる。ところが、ウィンドウの寸法が大きいならば、新しいサンプルは非常にゆっくり変更後の分布に影響し始め、その結果、分布に実際の変化が起きる検出時間を増大させて、突然の変化を検出するのを難しくする。
【課題を解決するための手段】
【００２５】
この発明の実施の形態は、センササンプルのストリームにおける如何なる変化をも検出するための、矛盾に対処する方法を提供する。この発明は、可能な変化点の前後で、変化する寸法のサブウィンドウを使用する。これは、変化後の小さな寸法のサブウィンドウ、たとえば唯１つのサンプルに対して、激烈なまたは突然の変化に対する迅速な反応を可能にすると共に、より大きなウィンドウから学習された分布を使用することによって、より微妙な変化への感度の向上を可能にする。このアイデアを直接実施すると、Ｏ（Ｎ４）への計算の複雑性（計算量）の増大をもたらす。しかし、この発明の実施の形態は、このような複雑さの増大を減少させる方法を効率的に実現することを提供する。
【００２６】
この発明の実施の形態は、多変量センササンプルストリームにおける如何なる変化をも検出するための方法を提供する。すなわち、本方法は、リアルタイムで突然の変化を検出できると共に、より長い時間帯に亘って、ゆっくり生じる変化をも検出できる。本方法は、変化の前後でデータ分布の明確なモデルを利用できないときに、適用できる。
【発明の効果】
【００２７】
本方法は、メモリ（記憶）バッファに保存されたサンプルのスライディングウィンドウで作動する。バッファは、最新のＮ個のサンプルを保存する。各新しいサンプルにより、バッファから最も古いサンプルを置き換えて削除する。本方法は、可能な変化が起こったかもしれない時間の前後の、サンプルの２つの隣接するサブウィンドウへの、バッファのすべての可能な分割を考える。サンプルの各対の隣接するサブウィンドウ間の差が求められ、最大の差がメリット（長所）スコアとして割り当てられる。そして、メリットスコアが所定の閾値より大きければ、サンプルのストリームにおける変化を送信することができる。
【００２８】
本方法の１つの実施の形態は、サンプルのサブウィンドウの対の間の平均ユークリッド距離を決定変数として測定する。本方法の他の実施の形態は、従来のＣＵＳＵＭ方法に基づいている。しかし、対照的に、従来の方法では、確率密度関数は未知であるが、本方法は、既知の分布の対数尤度推定値を使用する代わりに、パーゼン（Ｐａｒｚｅｎ）の核密度推定値で分布を推測する。
【発明を実施するための最良の形態】
【００２９】
実施の形態１．
図１Ａは、センサ１０２により機器および／または環境１０３から時間経過とともに順次取得された多変量センサデータサンプルストリーム１０１における如何なる変化をも検出するための方法１００を示す。サンプル１０１はバッファ１７０に保存（記憶）１１０され、そこでは、バッファ１７０が時間的に前方にスライド（移動）するサンプルのウィンドウを形成するように、バッファ１７０が満杯のとき、最も古いサンプルが捨てられ、新しいサンプルが保存される。
【００３０】
次に、各新しいサンプルに対して、バッファは、可能な変化が生じたかもしれない時間１７１の前後のサンプルのすべての可能な対の隣接するサブウィンドウ１１１へ分割され１２０、最も新しいサンプルがその１対のサブウィンドウの第２のサブウィンドウに保存される。サンプルの各対のすべての可能な隣接するサブウィンドウ１１１間の差１３１が決定される１３０。最大の差はメリット（長所）スコアとして割り当てられ、そして、それは閾値化され１４０、またメリットスコアが所定の閾値より大きければ、変化１５１は送信される１５０。
【００３１】
この発明のすべての実施の形態は可変サイズを有するサンプルの複数組の近接するウィンドウで作動する。すなわち、本方法は、サイズＮのサンプルのバッファ１７０のすべての可能なパーティション（分割）を考える。両方の方法は、そのメモリバッファのすべての可能な分割を考える計算コストを可成り減少させるのに利用できる共通の計算構造を共有する。両方の方法は、最新のセンササンプルを含むバッファΓｔで働き、そのバッファΓｔは、便宜的に、ｘ１（最も古いサンプル）からｘＮ（最も新しいサンプル）まで常に再番号付けされる。すなわち、該バッファは、時間的に前方にスライド（移動）する複数のサンプルの１つのウィンドウである。
【００３２】
差の処理手順１３０αは、変化がそのバッファにおける複数のサンプルのスパン（期間）内に起こった可能性に比例する定量的なメリットスコアΥαｔを決定する。特に、メリットスコアΥαｔは、バッファ１７０の２つのサブウィンドウ間の距離尺度でありうるが、これに限定されるものではない。典型的には、従来の方法は、単にそのバッファを複数のサンプルの２つの等しいサブウィンドウに分割して、これら２つの等しい部分の差に対して検定（テスト）される。対照的に、我々は、そのバッファを、単一のサンプルを保存するサブウィンドウを含む、すべての可能な対のサブウィンドウに分割する。
【００３３】
図に１Ｂに示すように、ベクトルｘの形式の、サンプル１０１の時間的に順序づけられたウィンドウが、バッファ１７０に連続して（順番に）保存される。以下に述べる方法は、複数のセンササンプルｘの１つのウィンドウの複数のサブウィンドウのすべての可能な対のインデックス（ｉ、ｊ）を考える。そこで、１≦ｉ≦ｊ≦Ｎであり、複数のサンプルｘ１５２を格納するバッファΓｔ１７０は２つの隣接するサブウィンドウγｔｉ，ｊ−１およびγｔｊ，Ｎに分割される。
【００３４】
ここで、時間ｔは左から右へ増大し、次式が成立する。
【００３５】
【数４】
【００３６】
図２Ａは、サンプル１〜Ｎを有するバッファ１７０を示す。インデックスｉを有するサンプルは、その対の第１のサブウィンドウの始まり（開始）を定義し、また、インデックスｊを有するサンプルは第２のサブウィンドウの第１のサンプルを定義し、また、それぞれ分割１７１に関連する、仮定された変化点を定義する。第１のサブウィンドウのエンド（終端）のサンプルは、インデックスｊ−１を有し、その１対のサブウィンドウが接近（隣接）することを保証するが、第２のサブウィンドウのエンド（終端）は常に最も新しいサンプル（ｘＮ）である。
【００３７】
２つのサブウィンドウで保存されたサンプルの２つのサブセット（部分集合）は、それぞれ不等数のサンプルを持つことができる。１つのサブウィンドウは、単一のサンプルから構成されさえするかもしれない。したがって、複数のサンプルのサブウィンドウは一つまたは複数のサンプルを含むことができ、すなわち、１つのサブウィンドウ内のサンプルの数は範囲［１、Ｎ−１］でありうる。
【００３８】
差すなわちメリットスコアΥαｔ（ｉ，ｊ）が、リストに載っている制約条件にしたがって、各可能な対のサブウィンドウに対して求められるならば、全体のメリットスコアは、次式に示すように、すべての分割に亘って最大である。
【００３９】
【数５】
【００４０】
次に、モデリングの問題は、何れのメリットスコアを使用すべきかを判別することである。コンピュータの問題は、各新しいサンプルｘｔに対して計算上効率的な方法でこれを行うことである。
【００４１】
メモリベースのグラフ理論的な処理手順（ＭＢ−ＧＴ）
図２Ｂに示されるように、２の間の差２００（距離）に複数のサンプルの２つのサブウィンドウ２２１−２２２の２つの分布２１１−２１２間の差２００（距離）を求めるという問題に対する１つの解決策は、それらの複数のサンプル自体の間の平均距離（差）を求めることである。各サンプルは多次元のユークリッド空間におけるデータ点であるから、複数のサンプルｘｋおよびｘｌのサブウィンドウ間の固有距離尺度（ｎａｔｕｒａｌ ｄｉｓｔａｎｃｅ ｍｅａｓｕｒｅ）はそれらのユークリッド距離であり、次式で表される。
ｄｋ，ｌ＝｜｜ｘｋ−ｘｌ｜｜．
【００４２】
上記のように特定されたインデックス対（ｉ、ｊ）により定義された特別の分割に対して、次式に示すように、複数のサンプルの２つのサブウィンドウ間の平均距離を求めることができる。
【００４３】
【数６】
【００４４】
このメモリベースのグラフ理論的な方法は、次式のように、メリットスコアを有する。
【００４５】
【数７】
【００４６】
各Ｃｉｊを求めることはＯ（Ｎ２）の複雑さ（コンプレクシティ）であり、考慮すべきＯ（Ｎ２）個のそのような項（ターム）があり、全体の複雑さはＯ（Ｎ４）である。この複雑さは、実際的応用のためには、容認できない。
【００４７】
ところで個々のＣｉｊ項の判定には、計算の複雑性をＯ（Ｎ２）まで引き下げるために利用できる或る程度の冗長度と反復的な構造がある。
【００４８】
ここで、我々が次式のように定義する。
【００４９】
【数８】
【００５０】
このとき、次のような再帰的な関係が成立する。
【００５１】
【数９】
【００５２】
図３に示されるように、これらの再帰（リカランス）は次のような効率的な計算プロセスを示唆する。値βｉ，ｊおよびＣ’ｉ，ｊは概念的にマトリクスと同様のデータ構造３０１−３０２で保存される。このマトリクスは制約条件ｉ＜ｊによる上三角行列である。計算は、定義上は零である単一の要素Ｃ’Ｎ，Ｎを有する、このマトリクスの最下段の行３１０から始めることができる。前の行より１つ上の各行１≦ｉ≦Ｎに対して、最下段から最上段に進んで行き、次の２つの工程が行なわれる。
１）すべての値βｉ，ｊが、それらの直ぐ右隣のサンプルから、右から左に進んで、次の再帰式を使用して再帰的に計算される。
【００５３】
【数１０】
【００５４】
２）すべての値Ｃ’ｉ，ｊが、各値βｉ，ｊおよび現在の行の直ぐ下の行の値Ｃ’ｉ＋１，ｊから、再帰式Ｃ’ｉ，ｊ＝Ｃ’ｉ＋１，ｊ＋βｉ，ｊを使用して計算される。
【００５５】
メリットスコアΥαｔを求めることは、正規化を行いかつ最大値を求めるだけなので、個々の項Ｃ’ｉ，ｊの計算と同時に行うことができる。このため、すべての値Ｃ’ｉ，ｊおよびβｉ，ｊをバッファに保存する必要はない。値βｉの現在行ｉに対してＮ個のサンプルのサイズのバッファを確保し、また、Ｃ’ｉ，ｊおよびＣ’ｉ＋１，ｊに対して同じサイズの２つのバッファを確保すれば充分である。したがって、この処理手順に関するメモリ要求条件はＯ（Ｎ）に過ぎず、また、計算の複雑さはＯ（Ｎ２）に過ぎない。
【００５６】
メモリベースのＣＵＳＵＭ処理手順（ＭＢ−ＣＵＳＵＭ）
図４Ａに示されるように、この発明の第２の実施の形態は、本方法が或るモデリング条件の下で最適な変化の検出を実現するのを可能にする確率的な基礎を有する。サンプルの分布が未知であるので、我々は最初にパーゼンの核密度推定値、たとえば、ガウスまたは３立方（ｔｒｉｃｕｂｉｃ）確率分布関数で分布について学習する。図４Ａでは、垂直軸が分布の確率密度、また水平軸が時間を表す。
【００５７】
同時に、非常に異なる理論的基盤にもかかわらず、第２の方法は実施の形態１と同様の計算構造を持っている。我々は、同様に重要な計算の複雑さの改善を実現するために、この構造を如何に活用できるかについて説明する。
【００５８】
ＣＵＳＵＭの導出に続いて、私たちはバッファ１７０に保存されたＮ個のサンプル内の可能な変化に関して以下の仮説を考える。
【００５９】
【数１１】
【００６０】
ここで、我々は、最新のＮ−ｉ＋１のサンプルが取得されたが、何ら変化が生じないという帰無（ヌル）仮説Ｈｉ，０と、そのような変化が生じたという複数の対立仮説Ｈｉ，ｊについて考える。始めのインデックスｉを導入することによって、我々は、テストされる仮説のセット（組）を、ウィンドウ内のＮ個のすべてのサンプルを必ずしも使用するわけではないものに拡大している。
【００６１】
本願に引用して援用するネイマン・ピアソンの補助定理（ホーエル他（Ｈｏｅｌ ｅｔ ａｌ．）、「仮説検定（Ｔｅｓｔｉｎｇ Ｈｙｐｏｔｈｅｓｅｓ）」、統計理論への入門の第３章（Ｃｈ．３ ｉｎ Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｓｔａｔｉｓｔｉｃａｌ Ｔｈｅｏｒｙ）、ニューヨーク（Ｎｅｗ Ｙｏｒｋ）：ホートン・ミフリン（Ｈｏｕｇｈｔｏｎ Ｍｉｆｆｌｉｎ），ｐｐ．５６−６７，１９７１）によれば、それぞれの特定の仮説Ｈｉ，ｊとＨｉ，０を検定（テスト）するときに行うことができる最も良い検定、すなわち偽の帰無（ｆａｌｓｅ ｎｕｌｌ）仮説を棄却する最も高い確率を有する検定は、次式で表す尤度比である。
【００６２】
【数１２】
【００６３】
便宜的に、対数尤度比率Ｓｉ，ｊ＝ｌｏｇ（Λｉｊ）が一般的に使用される。我々の方法では、我々は、真のｐｄｆ（ｐ０およびｐ１）を、式（１）に示すように、それらの核密度推定値で置換して、次式（５）を得る。
【００６４】
【数１３】
【００６５】
ここで、ｗｌ、ｋはその対のサンプル（ｘｌ、ｘｋ）対するカーネルウエイト（ｋｅｒｎｅｌ ｗｅｉｇｈｔ）であり、また、ウエイトｗｌ，ｋ＝ｗ（ｄｌ，ｋ）が成立する。最大尤度原理を使用することによって、この処理手順に対するメリットスコアは次式により表される。
【００６６】
【数１４】
【００６７】
上述のように、メリットスコアの計算は、Ｏ（Ｎ４）の計算複雑さを有する。しかし、このメリットスコアは、計算複雑さを減少させるのに再び利用できるこの発明の実施の形態の方法に対するメリットスコアに類似する構造を有する。
【００６８】
再び、図４Ｂに示すように、我々は、概念的にウィンドウＳｉ，ｊおよびＶ’ｉ，ｊ４０１−４０２の値を三角形のデータ構造において組織化して、次式のように助変数を定義できる。
【００６９】
【数１５】
【００７０】
計算すべき項はＯ（Ｎ３）ｖｌｉ，ｊであるように見えるが、式（５）を次式のように再帰的に再公式化する。
【００７１】
【数１６】
【００７２】
これにより、我々は、必ずしもすべての項が必要になるわけではないことを確信できる。さらにμ’ｊ＝μｊｊ、およびｖ’ｉ，ｊ＝ｖｊｉ，ｊを定義することによって、我々は、効率的な処理手順に対する基礎として以下の式を使用できる。
【００７３】
【数１７】
【００７４】
ｖ’ｉ，ｊに対する項だけが再帰的であること、すなわちμｊｊに対する項は直接的に計算されることに注意すべきである。これらの式は以下の処理手順を示唆する。
【００７５】
Ｓ１：式（８）ごとに、μ’ｊをｊ＝１，Ｎに対して直接的に計算する。
この計算は複雑さＯ（Ｎ２）を有するが、その結果をＯ（Ｎ）スペースに保存することができる。
【００７６】
Ｓ２：マトリクスＳｉ，ｊの各行ｉ＝Ｎ，１に対して、最下段行４１０（ｉ＝Ｎ）から始めて、第１行（ｉ＝１）まで上方に移動して、以下の２つの工程を行なう。
Ｓ２．１：式（８）ごとに、ｉ＋１とＮとの間のｊの各値に対して、下の行の対応するｖ’ｉ＋１，ｊおよびｗｊ，ｉからｖ’ｉ，ｊを計算する。
Ｓ２．２：Ｎとｉ＋１との間のｊの各値に対して、式（Ｓｉ，ｊ＝Ｓｉ，ｊ＋１＋ｌｏｇμ’ｊ−ｌｏｇｖ’ｉ，ｊ＋ｌｏｇ（ｊ−ｉ）−ｌｏｇ（Ｎ−ｊ＋１）を使用して、すべてのｉ＝１，Ｎに対して、Ｓｉ，Ｎ＋１＝０から始めて、Ｓｉ，ｊをその直ぐ右の値Ｓｉ，ｊ＋１から計算する。この工程における計算は、厳密に右から左（ｊ＝Ｎ、ｉ＋１）へ進む。
【００７７】
図５は、さらに詳細に判別する第１のメモリベースのグラフ理論的な（ＭＢ−ＧＴ）方法に対する擬似コードを示す。図３は判別する第２のメモリベースの累積集計（ＭＢ−ＣＵＳＵＭ）方法に対する変数を示し、また、図４は擬似コードをさらに詳細に示す。
【００７８】
この発明は好適な実施の形態を例に挙げて説明したが、この発明の精神および範囲内で種々の他の改変および変更を行うことができることを理解すべきである。したがって、添付クレームの目的は、この発明の真実の精神および範囲に含まれるようなすべての変形例および変更例をカバーすることである。
【図面の簡単な説明】
【００７９】
【図１Ａ】この発明の実施の形態１による多変量センサデータサンプルストリームにおける変化を検出するための方法のフロー図である。
【図１Ｂ】この発明の実施の形態１によるセンササンプルを保存（記憶）するバッファのブロック図である。
【図２Ａ】互いに等しくない（不等の）サブウィンドウに分割された、図２のバッファのブロック図である。
【図２Ｂ】この発明の実施の形態１によるサンプル値の異なる分布のブロック図である。
【図３】この発明の実施の形態１によるサンプルの差を求めるための三角形のデータ構造のブロック図である。
【図４Ａ】この発明の実施の形態１による核関数である。
【図４Ｂ】この発明の実施の形態１による三角形のデータ構造のブロック図である。
【図５】この発明の実施の形態１によるセンサデータにおける突然の変化を検出するためのメモリベースのグラフ理論的な（ＭＢ−ＧＴ）方法のための擬似コードのブロック図である。
【図６】この発明の実施の形態１によるセンサデータにおける突然の変化を検出するためのメモリベースの累積集計（ＭＢ−ＣＵＳＵＭ）方法で使用される変数のブロック図である。
【図７】メモリベースの累積集計方法で使用される擬似コードのブロック図である。
【特許請求の範囲】
【請求項１】
センサにより取得されたサンプルのストリームにおける変化を検出する方法であって、
時間経過とともにセンサにより取得されたサンプルのストリームをバッファに順次保存する工程であって、前記バッファでは、該バッファが時間的に前方にスライドするサンプルのウィンドウを形成するように、該バッファが満杯のとき、最も古いサンプルが捨てられて、新しいサンプルが保存される工程と、
各新しいサンプルに対して、前記バッファを、サンプルのすべての可能な対の隣接する、第１サブウィンドウおよび第２サブウィンドウを含むサブウィンドウへ分割する工程であって、最も新しいサンプルが１対のサブウィンドウの第２サブウィンドウに保存される工程と、
サンプルの各対の隣接するサブウィンドウの第１サブウィンドウおよび第２サブウィンドウ間の差を求める工程と、
最大の差をメリットスコアとして割り当てる工程と、
前記メリットスコアが所定の閾値より大きければ、前記サンプルのストリームにおける変化を送信する工程と、
を含む方法。
【請求項２】
前記変化は時間的に突然生じる、請求項１の方法。
【請求項３】
前記変化は時間経過とともに比較的ゆっくり生じる、請求項１の方法。
【請求項４】
前記サンプルの分布は未知である、請求項１の方法。
【請求項５】
前記差は、前記第１サブウィンドウと前記第２サブウィンドウにおける前記サンプルの値の間のユークリッド距離である、請求項１の方法。
【請求項６】
前記第１サブウィンドウおよび前記第２のサブウィンドウは、不等数のサンプルを有する、請求項１の方法。
【請求項７】
前記バッファにおけるサンプルの数がＮであり、前記サブウィンドウのサンプルの数が［１、Ｎ−１］の範囲でありうる、請求項１の方法。
【請求項８】
差判定の複雑さはＯ（Ｎ２）であり、ここで、Ｎは前記バッファに保存されたサンプルの数である、請求項１の方法。
【請求項９】
前記第１サブウィンドウおよび第２サブウィンドウのサンプルの値はそれぞれの三角マトリクスで保存され、前記差はすぐ隣同士のサンプルから再帰的に求められる、請求項１の方法。
【請求項１０】
パーゼンの核推定値を使用することにより前記分布を推測する工程をさらに備える、請求項１の方法。
【請求項１１】
前記差は、前記核推定値の対数尤度の累積集計処理手順を使用して求められる、請求項１０の方法。
【請求項１】
センサにより取得されたサンプルのストリームにおける変化を検出する方法であって、
時間経過とともにセンサにより取得されたサンプルのストリームをバッファに順次保存する工程であって、前記バッファでは、該バッファが時間的に前方にスライドするサンプルのウィンドウを形成するように、該バッファが満杯のとき、最も古いサンプルが捨てられて、新しいサンプルが保存される工程と、
各新しいサンプルに対して、前記バッファを、サンプルのすべての可能な対の隣接する、第１サブウィンドウおよび第２サブウィンドウを含むサブウィンドウへ分割する工程であって、最も新しいサンプルが１対のサブウィンドウの第２サブウィンドウに保存される工程と、
サンプルの各対の隣接するサブウィンドウの第１サブウィンドウおよび第２サブウィンドウ間の差を求める工程と、
最大の差をメリットスコアとして割り当てる工程と、
前記メリットスコアが所定の閾値より大きければ、前記サンプルのストリームにおける変化を送信する工程と、
を含む方法。
【請求項２】
前記変化は時間的に突然生じる、請求項１の方法。
【請求項３】
前記変化は時間経過とともに比較的ゆっくり生じる、請求項１の方法。
【請求項４】
前記サンプルの分布は未知である、請求項１の方法。
【請求項５】
前記差は、前記第１サブウィンドウと前記第２サブウィンドウにおける前記サンプルの値の間のユークリッド距離である、請求項１の方法。
【請求項６】
前記第１サブウィンドウおよび前記第２のサブウィンドウは、不等数のサンプルを有する、請求項１の方法。
【請求項７】
前記バッファにおけるサンプルの数がＮであり、前記サブウィンドウのサンプルの数が［１、Ｎ−１］の範囲でありうる、請求項１の方法。
【請求項８】
差判定の複雑さはＯ（Ｎ２）であり、ここで、Ｎは前記バッファに保存されたサンプルの数である、請求項１の方法。
【請求項９】
前記第１サブウィンドウおよび第２サブウィンドウのサンプルの値はそれぞれの三角マトリクスで保存され、前記差はすぐ隣同士のサンプルから再帰的に求められる、請求項１の方法。
【請求項１０】
パーゼンの核推定値を使用することにより前記分布を推測する工程をさらに備える、請求項１の方法。
【請求項１１】
前記差は、前記核推定値の対数尤度の累積集計処理手順を使用して求められる、請求項１０の方法。
【図１Ａ】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【公開番号】特開２００８−２６８１８２（Ｐ２００８−２６８１８２Ａ）
【公開日】平成２０年１１月６日（２００８．１１．６）
【国際特許分類】
【外国語出願】
【出願番号】特願２００８−１６５３３（Ｐ２００８−１６５３３）
【出願日】平成２０年１月２８日（２００８．１．２８）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成２０年１１月６日（２００８．１１．６）
【国際特許分類】
【出願番号】特願２００８−１６５３３（Ｐ２００８−１６５３３）
【出願日】平成２０年１月２８日（２００８．１．２８）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]