(57)【要約】      （修正有）【課題】位置データストリームの状態変化を高速高精度に検出する。【解決手段】対象の直前の状態をＢＬとして記録するステップと、位置データストリームから位置データを１つずつ受信するステップと、位置データを受信する度に、直前の状態ＢＬから各状態Ｂｉ（ｉ＝１，２，…Ｉ）への対象の累積状態変化傾向を決定するステップと、決定された累積状態変化傾向に基づいて、位置データストリーム内における状態変化点の有無を検出するステップとを備える。方法は、状態変化点を検出する際に、状態変化点の位置と変化先の対象の状態をさらに記述することができる。対象状態変化検出方法は、従来技術に比較して、より高速で高精度であり、かつ検出結果の記述性が高い。【選択図】図３
2010250807.tif 000002
【特許請求の範囲】
【請求項１】
位置データストリームから対象の状態変化を検出する方法であって、
対象の直前の状態をＢＬとして記録するステップと、
位置データストリームから位置データを１つずつ受信するステップと、
位置データを受信する度に、直前の状態ＢＬから各状態Ｂｉ（ｉ＝１，２，…Ｉ）への対象の累積状態変化傾向を決定するステップと、
決定された累積状態変化傾向に基づいて、位置データストリーム内における状態変化点の有無を検出するステップと
を有することを特徴とする方法。
【請求項２】
状態変化点を検出した場合に、状態変化点の位置と対象の変化後の状態とを記述するステップをさらに有することを特徴とする請求項１に記載の方法。
【請求項３】
状態変化点を検出した場合に、重要な状態変化点を検査するために、状態変化点について重要性チェックを実行するステップをさらに有することを特徴とする請求項１に記載の方法。
【請求項４】
前記累積状態変化傾向を決定するステップが、
予め記憶されている状態確率モデルと状態変化仮定とに基づいて、受信した各位置データｘｎについて対数仮定チェック確率比Rn(Hi|H0)を以下の式によって計算し、
【数７】
2010250807.tif 000009
（ここで、状態確率モデルは各位置データが各対象状態へマッピングされる確率を特徴付けるために使用され、状態変化仮定Hi (i = 0, 1, …I)は対象の状態の変化を特徴付けるために使用され、H0は対象の状態が変化しないことを意味し、Hi (i = 1, …I)は対象の状態が直前の状態BLから状態Bi
(i = 1, 2, …I)することを意味する）
位置データxnを受信した時に、累積状態変化確率比Ｔｉｎを以下の式によって計算する
【数８】
2010250807.tif 000010
（累積状態変化確率比Ｔｉｎは、位置データｘｎを受信した時に、直前の状態ＢＬから状態Ｂｉに変化する対象の累積状態変化傾向を特徴付ける）
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記検出ステップが、
位置データxnを受信した時に、算出された累積状態変化確率比Tin (i = 1, 2, …I)から
【数９】
2010250807.tif 000011
で得られる最大値Ti*nを見つけ、
Ti*n
≠ 0
であれば、位置データストリーム内に状態変化点が存在することを示す
ことを特徴とする請求項４に記載の方法。
【請求項６】
状態変化点を検出する場合、以下の式によって状態変化点の位置を決定し、
【数１０】
2010250807.tif 000012
最大累積状態変化確率比Ti*nに対応する状態変化仮定Hi*に基づいて態変化後の対象の状態を決定する
ことを特徴とする請求項５に記載の方法。
【請求項７】
最大累積状態変化確率比Ti*nを所定のしきい値と比較するステップと、
最大累積状態変化確率比Ti*nが所定のしきい値を上回る場合、対応する状態変化点λ*を受け入れ、そうでなければ、状態変化点を廃棄するステップをさらに有することを特徴とする請求項６に記載の方法。
【請求項８】
前記累積状態変化傾向を決定するステップにおいて、
直前の状態BL から各状態Bi
(i = 1, 2, …I)への対象の決定した累積状態変化傾向に重みを付加する（ここで、重み付けは対象の状態変化の重要性を反映し、状態変化の重要性が高いほど、より高い重みが状態変化に付加される）
ことを特徴とする請求項１に記載の方法。
【請求項９】
累積状態変化確率比Ｔｉｎを以下の式によって計算する
【数１１】
2010250807.tif 000013
（ここで、w(Bi|BL)は直前の状態BLから状態Bi
(i = 1, 2, …I)への対象の状態変化の重みである）
ことを特徴とする請求項４に記載の方法。
【請求項１０】
位置データストリームから対象の状態変化を検出するシステムであって、
対象の直前の状態をＢＬとして記録するための直前状態記録手段と、
位置データストリームから位置データを１つずつ受信するための位置データ受信手段と、
位置データを受信する度に、直前の状態ＢＬから各状態Ｂｉ（ｉ＝１，２，…Ｉ）への対象の累積状態変化傾向を決定するための累積状態変化傾向決定手段と、
決定された累積状態変化傾向に基づいて、位置データストリーム内における状態変化点の有無を検出するための状態変化点検出手段と
を備えることを特徴とするシステム。
【請求項１１】
前記状態変化点検出手段が状態変化点を検出した場合に、状態変化点の位置と、対象の変化後の状態とを記述するための記述手段をさらに備えることを特徴とする請求項１０に記載のシステム。
【請求項１２】
状態変化点を検出した場合に、重要な状態変化点を検査するために、前記状態変化点検出手段によって検出された状態変化点について重要性チェックを実行する重要性チェック手段をさらに備えることを特徴とする請求項１０に記載のシステム。
【請求項１３】
対象の各種の状態変化に対応する重みを格納のための状態変化重み記憶手段を備え、
状態変化の重要性が高いほど、より高い重みが状態変化に付加され、
前記累積状態変化傾向決定手段は、状態変化重み記憶手段に格納された対応する重みを用いて直前の状態BL から各状態Bi (i = 1, 2, …I)への対象の決定した累積状態変化傾向に重みを付加することを特徴とする請求項１０に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して位置データストリーム処理に関し、特に、位置データストリームから対象の状態変化を検出する方法およびシステムに関する。
【背景技術】
【０００２】
コンテキストアウェアコンピューティングの基盤となる移動対象（ユーザまたは実物）の状態は、一般に、リアルタイムの対象位置データによって暗黙に示され、そのデータからマイニングされる。状態マイニングを実行する上では、対象の状態変化の検出が重要かつ有用である。検出された状態変化を利用すると、ユーザに対し、コンテキストに基づく様々なサービスを時宜を得て提供することが可能になる。こうした用途のための状態変化の検出では、通常、１）高速（即時検出）、２）高精度（誤警報確率がほぼゼロ）、および３）高記述性（状態変化の発生時間だけでなく、発生した状態変化の種類も必要）、という３つの要件が必須となるが、既存の技術ではこれらの要件を完全に満たすことはできない。
【０００３】
状態変化の検出の目的は、観察に基づく位置データストリームを処理することにより、対象の状態変化点と状態変化パターンを特定することである。リアルタイムデータストリーム処理により根底にあるパターン変化を検出するための関連技術は、現在すでにいくつか存在している。例えば、非特許文献１（山西健司と竹内純一の論文「Ａ  ｕｎｉｆｙｉｎｇ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｄｅｔｅｃｔｉｎｇ  ｏｕｔｌｉｅｒｓ  ａｎｄ  ｃｈａｎｇｅ  ｐｏｉｎｔｓ  ｆｒｏｍ  ｎｏｎ−ｓｔａｔｉｏｎａｒｙ  ｔｉｍｅ  ｓｅｒｉｅｓ  ｄａｔａ（日本語論文タイトル：忘却型学習アルゴリズムを用いた外れ値検出と変化点検出の統一的扱い）」）においては、時系列データの統計的挙動を表現するためのＡＲ（自己回帰）モデルが提案されている。この論文ではさらに、ＡＲモデルをオンライン学習して根底の統計的挙動を記述するための、ＳＤＡＲ（ｓｅｑｕｅｎｔｉａｌｌｙ  ｄｉｓｃｏｕｎｔｉｎｇ  ＡＲ  ｍｏｄｅｌ  ｌｅａｒｎｉｎｇ）方式が提案されている。また、外れ値および変化点を検出するための、学習済みＡＲモデルに基づくスコア付け関数も提案されている。
【０００４】
上記に加えて、非特許文献２（Ｓｈａｉ  Ｂｅｎ−Ｄａｖｉｄ他による論文「Ｐａｐｅｒ：  Ｄｅｔｅｃｔｉｎｇ  Ｃｈａｎｇｅｓ  ｉｎ  Ｄａｔａ  Ｓｔｒｅａｍｓ（論文：データストリームにおける変化の検出）」）では、データストリームにおける変化を検出するためのノンパラメトリック法が提案されている。この方式は、長さの異なるスライドウィンドウと特徴ウィンドウを使用して並列差異テストを実行し、変化検出問題を、２つのサンプルが異なる分布により生成されたかどうかのテストに変換するものである。
【０００５】
図１は、Ｓｈａｉ  Ｂｅｎ−Ｄａｖｉｄ他が提案した状態変化検出システムを示す構造的ブロック図である。この解決法においては、データストリームは、根底の確率分布によって、１度に１データ点ずつ互いに独立した方法で生成される。データストリーム処理アルゴリズムにストリームの全履歴を記憶できるだけのメモリ容量を付与するのは非現実的であることから、この解決策は２ウィンドウパラダイムをベースとする変化検出アルゴリズムを用いている。このアルゴリズムは、「特徴ウィンドウ」内のデータを「スライドウィンドウ」内のデータと比較する。いずれのウィンドウも、固定数の連続データ点を含む。「スライドウィンドウ」はデータ点を受信する度に前方にスライドする。「特徴ウィンドウ」は参照ウィンドウであり、変化が検出される度に更新される。図１に示すように、合計Ｋ組のスライドウィンドウと特徴ウィンドウのペアがある。このＫ組のスライドウィンドウと特徴ウィンドウのペアを使用して、並列ウィンドウの比較により状態変化を検出するための並列変化判定法を実行するシステムが構築される。
【０００６】
図１に示すように、この状態変化検出システムは、Ｋ個の差異テスト手段１０１−１、１０１−２、…１０１−Ｋ−１および１０１−Ｋを含む。これらＫ個の差異テスト手段のウィンドウ長は、それぞれＬ１、Ｌ２、…ＬＫ−１、ＬＫである。このシステムはさらに、位置データストリーム更新手段１０２と、並列状態変化判定手段１０３と、直近状態変化点通知手段１０４とを含む。位置データストリーム更新手段１０２は、最新の位置データを含めることにより外部位置データストリームを更新する。この最新の位置データはＫ個の差異テスト手段１０１−１、１０１−２、…１０１−Ｋ−１および１０１−Ｋに供給され、それにより当該手段内のスライドウィンドウが更新される。差異テスト手段１０１−１、１０１−２、…１０１−Ｋ−１および１０１−Ｋの各々は、最新の位置データを追加し、古いデータを削除するためにスライドウィンドウを前方にスライドさせる、スライドウィンドウ更新ユニットを備える。スライドウィンドウは、新たなデータが着信する度に更新される。差異テスト手段１０１−１、１０１−２、…１０１−Ｋ−１および１０１−Ｋの各々はさらに、新たな変化が検出される度に特徴ウィンドウを更新する、特徴ウィンドウ更新ユニットを備える。特徴ウィンドウは静的なウィンドウであり、常に最後に検出された状態変化点まで移動されて、新たな変化が検出されるまで静的な状態を維持する。差異テスト手段１０１−１、１０１−２、…１０１−Ｋ−１および１０１−Ｋの各々はさらに、スライドウィンドウデータと特徴ウィンドウデータ間の距離をｄｉ＝  Ｄｉ  （ＳＷｉ，ＦＷｉ）（ｉ＝  １，２，…Ｋ）として計算する距離計算ユニットを備える。並列状態変化判定手段１０３は、異なるウィンドウ長を有する個々の差異テスト手段１０１−１、１０１−２、…１０１−Ｋ−１および１０１−Ｋから距離計算結果を受信し、Ｋ個の不等性について、これらの距離が対応するしきい値を上回るかどうか（すなわち、ｄｉ＞ｔｉ（ｉ＝１，２，…Ｋ）かどうか）を並列でチェックする。いくつかの分岐で状態変化が検出された場合（すなわち、ｄｉ＞ｔｉの分岐が検出された場合）、並列状態変化判定手段１０３は当該分岐における結果のトレードオフを実行して、状態変化点かどうかの判定を行う。その後、直近状態変化点通知手段１０４が、並列状態変化判定手段１０３によって決定された直近状態変化点を、アプリケーション（図示せず）と個々の特徴ウィンドウに通知する。
【０００７】
図１に示す従来技術によるシステムへの理解を助けるため、図２Ａ、図２Ｂ、図２Ｃに具体例を示す。図２Ａは、位置データ「１」および「２」のみで構成された、単純な位置データストリームの例である。並列差異テストは、２つの経路（すなわち、ウィンドウ長Ｌ１＝４およびＬ２＝１を有する２つの特徴ウィンドウ）を使用して実行される。２経路の特徴ウィンドウは、データストリームの特徴の直近の検出結果に従って、ＦＷ１＝｛２，２，２，２｝およびＦＷ２＝｛２｝に初期化される。初期スライドウィンドウはＳＷ１＝｛２，２，２，２｝とＳＷ２＝｛２｝である。スライドウィンドウは、１回に１点ずつ前方にスライドする。並列テストで使用される距離関数は、以下のとおりである。
【数１】
2010250807.tif 000003
しきい値は、ｔ１＝ｔ２＝１に設定される。図２Ｂは、ＳＷ１とＦＷ１（ウィンドウ長は４）を使用して実行された差異テストの段階的テスト結果である。図２Ｂの結果によれば、ウィンドウ長が４のとき、状態変化はｔ１０で検出されている。図２Ｃは、ＳＷ２とＦＷ２（ウィンドウ長は１）を使用して実行された差異テストの段階的テスト結果である。図２Ｃの結果によれば、ウィンドウ長が１のとき、状態変化はｔ４で検出されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】山西健司と竹内純一「Ａ  ｕｎｉｆｙｉｎｇ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｄｅｔｅｃｔｉｎｇ  ｏｕｔｌｉｅｒｓ  ａｎｄ  ｃｈａｎｇｅ  ｐｏｉｎｔｓ  ｆｒｏｍ  ｎｏｎ−ｓｔａｔｉｏｎａｒｙ  ｔｉｍｅ  ｓｅｒｉｅｓ  ｄａｔａ（日本語論文タイトル：忘却型学習アルゴリズムを用いた外れ値検出と変化点検出の統一的扱い）」
【非特許文献２】Ｓｈａｉ  Ｂｅｎ−Ｄａｖｉｄ他「Ｐａｐｅｒ：  Ｄｅｔｅｃｔｉｎｇ  Ｃｈａｎｇｅｓ  ｉｎ  Ｄａｔａ  Ｓｔｒｅａｍｓ（論文：データストリームにおける変化の検出）」
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記から、Ｓｈａｉ  Ｂｅｎ−Ｄａｖｉｄ他によって提案された従来技術では、異なるウィンドウ長を使用して差異テストを実行すると、状態変化の検出点が異なってくるため、判定が困難となる。さらに、この方法では「高速」と「精度」の間のバランスをとるのが難しい。すなわち、ウィンドウサイズを大きくすると検出が遅くなり、小さくすると誤警報を引き起こす結果となるので、異なる変化検出結果間で必要となるトレードオフは少なくない。
【００１０】
さらに、Ｋ個の並列分岐を伴う差異テストでは、計算量が膨大なだけでなく、計算の複雑性もきわめて高い。また、従来技術の方法ではウィンドウサイズと距離関数としきい値の選択が難しいため、ユーザが使いこなすのは困難である。
【課題を解決するための手段】
【００１１】
本発明は上記の問題を鑑みて提案されるものである。本発明においては、位置ストリーム内での状態変化の発生を検出できるだけでなく、状態変化点の場所と対象の変化後の状態を検出することも可能である。
【００１２】
本発明の１つの態様によれば、位置データストリームから対象の状態変化を検出する方法であって、対象の直前の状態をＢＬとして記録するステップと、位置データストリームから位置データを１つずつ受信するステップと、位置データを受信する度に、直前の状態ＢＬから各状態Ｂｉ（ｉ＝１，２，…Ｉ）への対象の累積状態変化傾向を決定するステップと、決定された累積状態変化傾向に基づいて、位置データストリーム内における状態変化点の有無を検出するステップとを備えることを特徴とする方法が提供される。
【００１３】
本発明の他の態様によれば、位置データストリームから対象の状態変化を検出するシステムであって、対象の直前の状態をＢＬとして記録するための直前状態記録手段と、位置データストリームから位置データを１つずつ受信するための位置データ受信手段と、位置データを受信する度に、直前の状態ＢＬから各状態Ｂｉ（ｉ＝１，２，…Ｉ）への対象の累積状態変化傾向を決定するための累積状態変化傾向決定手段と、決定された累積状態変化傾向に基づいて、位置データストリーム内における状態変化点の有無を検出するための状態変化点検出手段とを備えることを特徴とするシステムが提供される。本発明の一実施例によるシステムは、状態変化点が検出された場合に、状態変化点の位置と対象の変化後の状態とを記述するための記述手段をさらに備える。
【００１４】
従来技術の問題点を解決するため、本発明は、「状態確率モデル」と「状態変化仮説」という２つの概念を定める。このうち、「状態確率モデル」は各位置データが各対象状態に対応する確率を表し、「状態変化仮説」は状態変化のモデル化に使用され、各仮説は１種類の状態変化に対応する。
【発明の効果】
【００１５】
本発明による対象の状態変化を検出する方法およびシステムは、従来技術に比較して多数の利点を有する。本発明によれば、状態変化の検出は、新たな位置データが着信する度に順次実行されるため、従来技術よりも高速である。さらに、本発明においては、並列ウィンドウを使用せずに変化度合いの異なる変化を適応的に検出できるため、検出精度が向上する。また、本発明の方法は、状態変化点の具体的な位置と変化後の対象の状態も検出されるため、記述性が高い。本発明の方法は軽量である。さらに、ユーザはウィンドウサイズと距離関数について頭を悩ませる必要がない。
【００１６】
本発明の他の利点と特長は、以下の詳細な説明と図面を併せて参照することにより、明らかとなるであろう。ただし、本発明は図面に示す例や特定の実施例に限定されないことに留意されたい。
【図面の簡単な説明】
【００１７】
本発明は、以下に示す本発明の実施例の詳細な説明と添付図面からさらに明確に理解されるであろう。なお、添付図面では、類似の部品は同一の参照番号を使用して示している。
【図１】従来技術における状態変化検出システムを示す構造的ブロック図である。
【図２Ａ】図１に示す従来技術システムの動作原理を説明するための概略図である。
【図２Ｂ】図１に示す従来技術システムの動作原理を説明するための概略図である。
【図２Ｃ】図１に示す従来技術システムの動作原理を説明するための概略図である。
【図３】本発明の一実施例による状態変化検出システム３００を示す構造的ブロック図である。
【図４】図３に示すシステム３００の動作プロセスの一例を示すフローチャートである。
【図５】図３に示すシステム３００の動作原理を説明するための概略図である。
【図６】本発明の他の実施例による状態変化検出システム６００を示す構造的ブロック図である。
【図７】図６に示すシステム６００の動作原理を説明するための概略図である。
【発明を実施するための形態】
【００１８】
前述したように、本発明では、「状態確率モデル」と「状態変化仮説」という２つの概念を利用して、対象の状態変化の検出が円滑化される。本発明によれば、対象の状態変化は、位置データストリーム内の最新の位置データを順次評価して、直前の状態から有意に変化した有意状態変化点を発見することにより検出される。
【００１９】
図３は、本発明の一実施例による状態変化検出システム３００を示す構造的ブロック図である。図３に示すように、システム３００は、位置データストリーム更新手段３０１と、位置データ受信手段３０２と、直前状態記録手段３０３と、累積状態変化傾向決定手段３０４と、状態変化点検出手段３０５と、記述手段３０６（任意）と、重要性チェック手段３０７（任意）と、直近状態変化点通知手段３０８と、状態確率モデルと状態変化仮説とを記憶するための記憶装置３０９とを備える。図３においては、本発明の好適な実施例に含まれる記述手段３０６と重要性チェック手段３０７は、任意モジュールとして波線で示されている。記憶装置３０９は、用途別に事前に指定される、位置データから対象状態への変化の確率関係を記憶する。本システムにおいては、位置データストリーム更新手段３０１と直近状態変化点通知手段３０８の動作はそれぞれ、図１に示す従来技術システムにおける位置データストリームを更新するための手段、並びに直近の状態変化点と変化後の対象の状態とを通知するための手段の動作と同じである。ここでは、これらの構成要素の詳細な説明は省略する。
【００２０】
位置データ受信手段３０２は、位置データストリーム更新手段３０１から、状態検出の対象となる新たな位置データｘｎ（ｎ＝ｗ，ｗ＋１，…Ｎ）を１つずつ受信する。直前状態記録手段３０３は、直近の状態変化の検出点ｘｗにおける対象の直前の状態ＢＬを記録し、それを累積状態変化傾向決定手段３０４に入力する。累積状態変化傾向決定手段３０４は、位置データｘｎ（ｎ＝ｗ，ｗ＋１，…Ｎ）が着信する都度、対象の直前の状態ＢＬから各状態Ｂｉ（ｉ＝１，２，…Ｉ）への累積状態変化傾向を決定する。一例を挙げると、累積状態変化傾向決定手段３０４は、直前の状態ＢＬから各状態Ｂｉ（ｉ＝１，２，…Ｉ）への対象の累積状態変化確率比（下記に詳述）を計算するための特定の順次仮説テストを実行する。その後、状態変化点検出手段３０５が、累積状態変化傾向決定手段３０４が各状態について決定した累積状態変化傾向をチェックして、対象の状態変化の有無を判定する。例えば、どの状態についても顕著な累積状態変化傾向が見られない場合（すなわち、どの状態においても計算された累積状態変化確率比がゼロの場合）には、状態変化点検出手段３０５は対象の状態に変化がないと判定する。逆に、ある状態について計算された累積状態変化確率比がゼロではない場合には、状態変化点検出手段３０５は位置データストリーム内に状態変化点が存在すると判定する。状態変化点が存在する場合には、任意で、記述手段３０６が状態変化点の位置と対象の変化後の状態とを記述することも可能である。本発明においては、記述手段３０６を追加することにより、状態変化検出の記述性が従来技術よりも高くなる。例えば、本発明の一実施例においては、記述手段３０６は、様々な状態の中から、対象の最も顕著な累積状態変化傾向に対応する状態を対象の新たな状態として決定し、この状態に対応する対象の初期変化点を状態変化点として使用する。
【００２１】
さらに、状態変化点検出手段３０５が状態変化点を検出した場合には、重要性チェック手段３０７を任意に使用して、この種の状態変化の重要性をチェックしてもよい。例えば、重要性チェック手段３０７は、算出された累積状態変化傾向のうち最も顕著なものを事前に決定したしきい値と比較することにより、その状態変化が有意かどうかを判定する。その変化傾向がしきい値を上回ることが比較結果により示された場合には、重要性チェック手段３０７はその状態変化は有意であると判定する。変化傾向がしきい値を上回らない場合には、重要性チェック手段３０７はその状態変化を無視する。この重要性チェックにより、位置データストリーム内の有意な状態変化点と、それに対応する変化後の対象の状態のみが直近状態変化点通知手段３０８によって直前状態記録手段３０３に通知され、これにより対象の直前の状態が更新されて今後の状態変化の検出に利用される。
【００２２】
図４は、図３に示すシステム３００の動作プロセスの一例を示すフローチャートである。図４に示すように、プロセス４００はステップ４０１、すなわち、位置データ受信手段３０２が位置データストリームから最新の位置データｘｎを受信し、直前状態記録手段３０３が対象の直前の状態ＢＬを記録するステップから始まる。続いて、累積状態変化傾向決定手段３０４が、記憶装置３０９に予め記憶されている状態確率モデルと状態変化仮説とに基づいて、現在までの、直前の状態ＢＬから各状態Ｂｉ（ｉ＝１，２，…Ｉ）への対象の累積状態変化傾向を決定する。
【００２３】
前述したように、状態確率モデルは、位置データから対象の各状態Ｂｉ（ｉ＝１，２，…Ｉ）への変化の発生確率を定義する。これは、以下の３つによって定義される。
１．対象状態集合：｛Ｂｉ，ｉ＝１，２，…Ｉ｝
２．位置データ集合：｛ｘｊ，ｊ＝１，２，…Ｊ｝
３．状態確率モデル：｛Ｐ（ｘｊ｜Ｂｉ），ｉ＝１，２，…Ｉ；ｊ＝１，２，…Ｊ｝。これは、位置データがｘｊであるときに対象が状態Ｂｉである確率を表す。この定義は、例えば、ユーザがオフィス内にいるのであれば（例えば、位置データが１であれば）、ユーザが仕事をしている確率（尤度）は９０％、というように行うことができる。
【００２４】
対象の状態変化の特徴付けは、状態変化仮説を使用して行われる。例えば、次のように定義することが可能である。
Ｈ０：対象の状態は変化しない。
Ｈｉ：対象の状態はＢＬからＢｉ（ｉ＝１，２，…Ｉ）に変化する。
【００２５】
図４に戻ると、ステップ４０２において、累積状態変化傾向決定手段３０４は例えば、各位置データｘｎと累積状態変化確率比Ｔｉｎについて対数仮定チェック確率比Ｒｎ（Ｈｉ｜Ｈ０）を計算することにより、対象の様々な状態変化傾向を表すことができる。累積状態変化傾向決定手段３０４は、新たな位置データｘｎが着信すると、以下の式（１）を使用して位置データｘｎの対数仮定チェック確率比Ｒｎ（Ｈｉ｜Ｈ０）を計算する。
【数２】
2010250807.tif 000004
ここで、Ｒｎ（Ｈｉ｜Ｈ０）は、位置データｘｎが着信したときに対象の状態が直前の状態ＢＬから状態Ｂｉに変化する確率比を表す。Ｒｎ（Ｈｉ｜Ｈ０）の結果のうち、正の値は状態がＢＬからＢｉに変化する確率が高いことを意味し、負の値は状態がＢＬからＢｉに変化する確率が低いことを意味する。
【００２６】
その後、ステップ４０３において、以下の式により累積状態変化確率比Ｔｉｎが計算される。
【数３】
2010250807.tif 000005
【００２７】
前述したように、Ｔｉｎは、位置データｘｎが着信するまでに、対象が直前の状態ＢＬから状態Ｂｉ（ｉ＝１，２，…Ｉ）に変化する累積状態変化傾向を特徴付けるために使用される。
【００２８】
累積状態変化傾向決定手段３０４が、位置データｘｎが着信したときの、様々な状態  Ｂｉ（ｉ＝１，２，…Ｉ）に関するＴ１ｎからＴＩｎまでのすべての累積状態変化確率比を計算した後、ステップ４０４において状態変化点検出手段３０５が算出された累積状態変化確率比から最大値を検出する（すなわち、最も顕著な状態変化傾向を有する状態変化を特定する）。最大累積状態変化確率比Ｔｉ＊ｎは、以下の式により得られる。
【００２９】
【数４】
2010250807.tif 000006
【００３０】
その後、状態変化点検出手段３０５がステップ４０５において、最大累積状態変化確率比Ｔｉ＊ｎがゼロかどうかを判定する。最大累積状態変化確率比Ｔｉ＊ｎがゼロの場合は、位置データストリーム内に状態変化がないことを意味する。この場合（ステップ４０５の結果が「Ｎｏ」の場合）には、プロセス４００はステップ４０１に戻って新たな位置データを受信し、状態変化の検出を続ける。最大累積状態変化確率比Ｔｉ＊ｎがゼロではない場合（ステップ４０５の結果が「Ｙｅｓ」の場合）には、プロセス４００はステップ４０６に進む。ステップ４０６においては、算出された最大累積状態変化確率比Ｔｉ＊ｎに基づき、任意の記述手段３０６（図３に示す）を使用して、状態変化点の具体的な位置と変化先の対象の状態とが記述される。
【００３１】
具体的には、記述手段３０６はステップ４０６において、まず最大累積状態変化確率比Ｔｉ＊ｎに対応する状態変化仮説Ｈｉ＊を決定し、この状態変化仮説Ｈｉ＊から変化後の対象の状態をＢｉ＊として決定する。同時に、記述手段３０６が以下の式（４）を使用して、状態変化点の正確な位置λ＊を特定する。
【数５】
2010250807.tif 000007
【００３２】
ステップ４０７において、任意の重要性チェック手段３０７が、状態変化点検出手段３０５によって検出された最も顕著な累積状態変化傾向を有する状態変化の重要性を判定することもできる。例えば、重要性チェック手段３０７は、最大累積状態変化確率比Ｔｉ＊ｎを事前に決定されたしきい値Ｔｈと比較する。Ｔｉ＊ｎがＴｈを上回る場合、ステップ４０８において対応する状態変化点が受け入れ、記録される。逆にＴｉ＊ｎがＴｈを下回る場合には、この状態変化点を廃棄する（ステップ４０９）。その後、ステップ４１０において、受け入れられた状態変化点の位置λ＊と変化後の対象の状態とが、直近状態変化点通知手段３０８により直前状態記録手段３０３に通知され、対象の直前の状態ＢＬが更新される。更新された直前の状態は、次の状態変化の検出に利用される。
【００３３】
図５は、図３に示すシステム３００の動作原理を説明するための概略図である。この例においては、状態モデルは状態集合｛Ｂ１，Ｂ２｝と位置データ集合｛１，２｝とを有し、位置データｘｗが着信し、対象の直前の状態はＢＬ＝Ｂ２であるとする。状態確率モデルは、例えば以下のように定義することができる。
Ｐ（ｘｉ＝１｜Ｂ１）＝０．８；Ｐ（ｘｉ＝１｜Ｂ２）＝０．２；Ｐ（ｘｉ＝２｜Ｂ１）＝０．１；Ｐ（ｘｉ＝２｜Ｂ２）＝０．９
【００３４】
この場合、状態変化仮説は以下のように定義される。
Ｈ０：対象の状態は変化しない。
Ｈ１対象の状態は、ＢＬ＝Ｂ２からＢ１に変化する。
【００３５】
図４の動作プロセスを参照すると、位置データストリーム内の状態変化が検出され、その検出結果が図５に示されている。位置データｘｗ＋５、ｘｗ＋８、ｘｗ＋９の位置において非ゼロの累積状態変化確率比Ｔｉ＊ｎが算出されているため、これらの位置で状態変化が発生した可能性が高いと判断することができる。重要性チェックのしきい値が１に設定されているとすると、位置ｘｗ＋９において有意な状態変化が検出されるので、この状態変化はｘｗ＋７で発生したということになる。
【００３６】
図６は、本発明の他の実施例による状態変化検出システム６００を示す構造的ブロック図である。図３のシステム３００と比較すると、システム６００は状態変化重み記憶装置６０１をさらに含む点が異なる。
【００３７】
図３に示す実施例ではすべての状態変化が均等に扱われるが、実用用途においては、異なる状態変化に異なる重要性が付加されるケースが多い。本発明では、この事実を考慮して、この問題を解決するために図６に示す実施例が提供される。状態変化重み記憶装置６０１は、異なる状態変化の重要性に対応する重みを記憶するために使用される。状態変化の重要性が高いほど、大きな重みが付加される。この変更により、本発明は上記に加えてまた別の効果を実現することができる。その効果とは、異なる状態変化に異なる重みが割り当てられるため、重要な状態変化が検出される確率が高まり、しかも検出速度も速くなることである。
【００３８】
図６に示すように、状態変化重み記憶装置６０１は異なる状態変化の重要性に対応する重みを記憶している。例えば、仮説Ｈ０（対象の状態は変化しない）と仮説Ｈｉ（対象の状態はＢＬからＢｉ（ｉ＝１，２，…Ｉ）に変化する）が与えられた場合は、仮説Ｈｉに対応する重みであることを表す、重みｗ（Ｂｉ｜ＢＬ）が定義される。
【００３９】
対応する重みｗ（Ｂｉ｜ＢＬ）は累積状態変化傾向決定手段３０４に供給され、そこで、都度計算された累積状態変化傾向に重みが付加される。具体的には、累積状態変化傾向決定手段３０４は、累積状態変化確率比Ｔｉｎを計算するために、上記の式（２）を以下のように変更する。
【数６】
2010250807.tif 000008
これにより、重要な状態変化が検出される確率が高まる。重要な状態変化については、重要性チェックの実行時に確認することができる。
【００４０】
したがって、図５の例は、図７に示すプロセスのように変更することが可能である。この例においては、重みはｗ（Ｂ１｜Ｂ２）＝２．０およびｗ（Ｂ２｜Ｂ１）＝１．０として設定されるとする。この設定から、Ｂ２からＢ１への状態変化がより重要であることが分かる。図５の実施例では、ｘｗ＋５で検出された状態変化は重要性チェックに合格しないため、状態変化点とはみなされない。一方、重みが割り当てられる図７の例では、ｘｗ＋５で検出されたＢ２からＢ１への状態変化は重要な状態変化なので、確認済み状態変化点として受け入れられる。このように、重みを設定することにより重要な状態変化が検出される確率が高まるため、重要な状態変化の検出の精度と速度を高めることが可能になる。
【００４１】
上記では、添付図面を参照して、本発明による対象の状態変化を検出する方法とシステムについて説明した。本発明の検出方法は、従来技術に比較して、より高速で高精度であり、かつ記述性が高い。
【００４２】
添付図面を参照しながら本発明の特定の実施例を説明してきたが、本発明は、添付図面に示された特定の構成およびプロセスに限定されるものではない。上記では、説明を簡潔にするため、既知の方法および技術の詳細は省略している。また、上記の実施例では、いくつかの具体的なステップを例示したが、本発明の方法および処理は説明および図示に使用した特定のステップに限定されないため、当該技術に精通する当業者であれば、本発明の精神を一旦理解した後に、様々な変形、変更、追加を行い、またステップの順序を入れ替えることが可能である。
【００４３】
本発明の各要素は、ハードウェア、ソフトウェア、ファームウェア、またはその組み合わせとして実装し、そのシステム、サブシステム、コンポーネント、もしくはサブコンポーネント内で利用することができる。ソフトウェアとして実装された場合、本発明の各要素は、必要なタスクを実行するためのプログラムもしくはコードセクションとなる。これらのプログラムまたはコードセクションは、機械読取り可能な媒体に格納することも、あるいは、搬送波で搬送されるデータ信号を介して伝送媒体もしくは通信リンク上で伝送することもできる。「機械読取り可能な媒体」には、情報を格納または伝送できるあらゆる媒体が含まれる。機械読取り可能な媒体の例としては、電子回路、半導体記憶装置、ＲＯＭ、フラッシュメモリ、ＥＲＯＭ、フロッピーディスク、ＣＤ−ＲＯＭ、光ディスク、ハードディスク、光ファイバー媒体、ＲＦリンク等が挙げられる。コードセクションは、インターネットやイントラネット等のコンピュータネットワークを介してダウンロードすることができる。
【００４４】
本発明は、その精神および本質的な特徴から逸脱することなく、他の様々な形式で実装することができる。例えば、実施例で説明したアルゴリズムは、システムアーキテクチャが本発明の基本精神から逸脱しない限り、変更が可能である。したがって、上記の実施例は、あらゆる観点において限定的なものではなく、例示的なものとみなされる。本発明の範囲は、上記の説明よりもむしろ付記した請求項により定義されるため、請求項の範囲に入るあらゆる変形またはその等価物は本発明の範囲に含まれる。
【符号の説明】
【００４５】
１０２：位置データストリーム更新手段
１０１−１〜Ｋ：差異テスト手段
１０３：並列状態変化判定手段
１０４：直近状態変化点通知手段
３０１：位置データストリーム更新手段
３０２：位置データ受信手段
３０３：直前状態記録手段
３０４：累積状態変化傾向決定手段
３０５：状態変化点検出手段
３０６：記述手段
３０７：重要性チェック手段
３０８：直近状態変化点通知手段
３０９：記憶装置
６０１：状態変化重み記憶装置
【図１】
2010250807.tif 000014
【図２Ａ】
2010250807.tif 000015
【図２Ｂ】
2010250807.tif 000016
【図２Ｃ】
2010250807.tif 000017
【図３】
2010250807.tif 000018
【図４】
2010250807.tif 000019
【図５】
2010250807.tif 000020
【図６】
2010250807.tif 000021
【図７】
2010250807.tif 000022
【外国語明細書】
2010250807000001.pdf