(57)【特許請求の範囲】
【請求項１】
複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出方法であって、
第１抽出部が、一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出するステップと、
第２抽出部が、前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出するステップと、
決定部が、前記第１抽出部により抽出されたエピソードパターンに対応する前記第２抽出部により抽出された遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部により抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定するステップと、
を含むことを特徴とする異常遷移パターン検出方法。
【請求項２】
前記異常遷移パターンとして決定すべき遷移パターンの出現頻度の閾値をα、前記異常遷移パターンとして決定すべき遷移パターンと、当該遷移パターンと相補関係にある遷移パターンとの出現頻度の差の閾値をβとしたときに、
前記第１の頻度が２α＋βであり、前記第２の頻度がα＋βであることを特徴とする請求項１に記載の異常遷移パターン検出方法。
【請求項３】
前記遷移パターンは、異なる３つのアイテムを含み、
前記相補関係にある遷移パターン同士は、先頭又は末尾のアイテムが一致することを特徴とする請求項１又は２に記載の異常遷移パターン検出方法。
【請求項４】
前記第１抽出部は、頻出エピソードマイニングの手法を用い、前記第２抽出部は、頻出系列パターンマイニングの手法を用いることを特徴とする請求項１〜３のいずれか一項に記載の異常遷移パターン検出方法。
【請求項５】
コンピュータに、複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出させる異常遷移パターン検出プログラムであって、
前記コンピュータを、
一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出部、
前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出部、及び
前記第２抽出部により抽出された遷移パターンに、前記第１抽出部により抽出されたエピソードパターンに対応する遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部により抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定部、として機能させることを特徴とする異常遷移パターン検出プログラム。
【請求項６】
複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出装置であって、
一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出部と、
前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出部と、
前記第１抽出部が抽出したエピソードパターンに対応する前記第２抽出部が抽出した遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部が抽出した遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定部と、を備える異常遷移パターン検出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、異常遷移パターン検出方法、プログラム及び装置に関する。
【背景技術】
【０００２】
従来、交通分野において、大量の軌跡データから他と異なる軌跡データを検出したり、ＢＰＭ（Business Process Management）分野において、大量の業務の証跡ログから他と違う証跡パターンを検出したりするための方法について種々検討されている。
【０００３】
その１つとして、軌跡データや証跡ログを系列データ（アイテムの並び順を規定するデータ）で表し、各系列データにおいて出現するアイテムの組み合わせ（系列パターン）の出現頻度から、異常な系列データを検出する方法が知られている（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】R.Agrawal and Srikant. Mining sequential patterns. In ICDE'95
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記非特許文献１では、最初に出現頻度の高い系列パターンを検出し、当該出現頻度の高い系列パターンのアイテムの並び順を入れ替えた系列パターンの出現頻度を確認する。そして、並び順を入れ替えた系列パターンのうち出現頻度の低い系列パターンを含む系列データを異常データとする。
【０００６】
しかしながら、上記非特許文献１では、並び順を入れ替えた系列パターンの全てについて、各系列データにおける出現頻度を確認する必要があったため、関心のない系列パターンまで確認する必要があり、効率が悪かった。
【０００７】
そこで本件は上記の課題に鑑みてなされたものであり、効率の良い異常遷移パターンの検出を行うことが可能な異常遷移パターン検出方法、プログラム及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本明細書に記載の異常遷移パターン検出方法は、複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出方法であって、第１抽出部が、一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出するステップと、第２抽出部が、前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出するステップと、決定部が、前記第１抽出部により抽出されたエピソードパターンに対応する前記第２抽出部により抽出された遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部により抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定するステップと、を含むことを特徴とする異常遷移パターン検出方法である。
【０００９】
本明細書に記載の異常遷移パターン検出プログラムは、コンピュータに、複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出させる異常遷移パターン検出プログラムであって、前記コンピュータを、一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出部、前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出部、及び前記第２抽出部により抽出された遷移パターンに、前記第１抽出部により抽出されたエピソードパターンに対応する遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部により抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定部、として機能させるプログラムである。
【００１０】
本明細書に記載の異常遷移パターン検出装置は、複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出装置であって、一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出部と、前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出部と、前記第１抽出部が抽出したエピソードパターンに対応する前記第２抽出部が抽出した遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部が抽出した遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定部と、を備えている。
【発明の効果】
【００１１】
本明細書に記載の異常遷移パターン検出方法、プログラム及び装置は、効率の良い異常遷移パターンの検出を行うことが可能なできるという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】一実施形態に係る情報処理システムの構成を概略的に示す図である。
【図２】軌跡データの集合Ｔを示す図である。
【図３】図２の位置データＰｏｓを座標上にプロットし、各位置データＰｏｓを取得時刻順に結んだ状態を示す図である。
【図４】サーバのハードウェア構成を示す図である。
【図５】サーバの機能ブロック図である。
【図６】図６（ａ）は、軌跡データの集合Ｔが全て含まれる領域（分析対象領域Ｒ）をメッシュ粒度ｄで分割した状態を示す図であり、図６（ｂ）は、系列データの集合Ｓを示す図である。
【図７】サーバの処理の一連の流れを示すフローチャートである。
【図８】系列データ生成部による系列データ生成処理（ステップＳ１２）を示すフローチャートである。
【図９】頻出マイニング実行部による頻出マイニング処理（ステップＳ１４）を示すフローチャートである。
【図１０】図１０（ａ）、図１０（ｂ）は、一実施形態で処理対象とするエピソードパターンの例を示す図である。
【図１１】図１１（ａ）〜図１１（ｃ）は、頻出マイニング実行部の処理を説明するための図である。
【図１２】低頻度系列抽出部による低頻度系列抽出処理（ステップＳ１６）を示すフローチャートである。
【図１３】図１３（ａ）〜図１３（ｃ）は、低頻度系列抽出部の処理を説明するための図である。
【図１４】異常軌跡決定部による異常軌跡決定処理（ステップＳ１８）を示すフローチャートである。
【図１５】図１５（ａ）、図１５（ｂ）は、異常軌跡決定部の処理を説明するための図である。
【発明を実施するための形態】
【００１３】
以下、一実施形態について、図１〜図１５に基づいて詳細に説明する。図１には、一実施形態に係る情報処理システム１００の構成が概略的に示されている。
【００１４】
図１に示すように、情報処理システム１００は、車載装置１０と、ユーザ端末２０と、サーバ３０と、を備える。なお、車載装置１０、ユーザ端末２０及びサーバ３０は、インターネット等のネットワーク８０に接続されている。
【００１５】
車載装置１０は、タクシーなどの車両に設置される装置であり、ＧＰＳモジュールや通信装置などを含んでいる。車載装置１０は、ＧＰＳモジュールを用いて、車両の位置データを所定時間間隔で取得するとともに、通信装置を用いて、ユーザ端末２０に対して、取得した位置データを送信する。なお、位置データは、(時刻、ＩＤ、緯度、経度)の４つの属性を有する。
【００１６】
ユーザ端末２０は、例えばタクシー会社に設置されるＰＣなどの端末であり、各車載装置１０から送信されてくる車両の位置データを収集する。そして、ユーザ端末２０は、各車両の位置データを纏めて、図２に示すような軌跡データの集合Ｔを生成し、サーバ３０に対して送信する。なお、図２の軌跡データの集合Ｔは、ＩＤと、位置データＰｏｓ（緯度、経度）の各フィールドを有している。ＩＤのフィールドには、軌跡のＩＤ（例えば車両のＩＤと一致）が入力される。位置データＰｏｓ（緯度、経度）には、緯度、経度の情報が、取得時刻順に格納される。なお、図３には、図２の位置データＰｏｓを座標上にプロットし、各位置データＰｏｓを取得時刻順に結んだ状態が示されている。
【００１７】
図１に戻り、サーバ３０は、ユーザ端末２０からの依頼の下、ユーザ端末２０から送信されてくる軌跡データの集合Ｔの中から、異常な軌跡を決定する処理を実行する。また、サーバ３０は、処理結果をユーザ端末２０に対して出力する。なお、本実施形態においては、例えば、多数の車両がある位置Ｘ1、Ｘ2、Ｘ3を、Ｘ1→Ｘ2→Ｘ3の順に通過しているのに、わずかな数（例えば１台）の車両が異なる順（例えばＸ1→Ｘ3→Ｘ2）に通過しているような場合に、Ｘ1→Ｘ3→Ｘ2の順に通過する軌跡を「異常な軌跡」と呼ぶものとする。
【００１８】
図４には、サーバ３０のハードウェア構成が示されている。この図４に示すように、サーバ３０は、ＣＰＵ９０、ＲＯＭ９２、ＲＡＭ９４、記憶部（ここではＨＤＤ（Hard Disk Drive））９６、及び可搬型記憶媒体用ドライブ９９等を備えており、サーバ３０の構成各部は、バス９８に接続されている。サーバ３０では、ＲＯＭ９２あるいはＨＤＤ９６に格納されているプログラム（異常遷移パターン検出プログラム）、或いは可搬型記憶媒体用ドライブ９９が可搬型記憶媒体９１から読み取ったプログラム（異常遷移パターン検出プログラム）をＣＰＵ９０が実行することにより、図５の各部の機能が実現されている。
【００１９】
図５には、サーバ３０の機能ブロック図が示されている。図５に示すように、サーバ３０は、ＣＰＵ９０がプログラムを実行することで、データ取得部３２、系列データ生成部３４、頻出マイニング実行部３６、低頻度系列抽出部３８、異常軌跡決定部４０、及び出力部４２としての機能を実現する。
【００２０】
データ取得部３２は、ユーザ端末２０から送信されてくる軌跡データの集合Ｔを取得し、系列データ生成部３４に対して送信する。
【００２１】
系列データ生成部３４は、図６（ａ）に示すように、軌跡データの集合Ｔが全て含まれる領域（分析対象領域Ｒ）をメッシュ粒度ｄで分割する。また、系列データ生成部３４は、各メッシュにＩＤ（メッシュＩＤ＝Ａ，Ｂ，Ｃ…）を割り振り、軌跡データの集合Ｔに含まれる各データを、所定の変換規則の下、メッシュＩＤの系列データに変換する（図６（ｂ）参照）。なお、変換後の系列データの集合をＳとする。
【００２２】
頻出マイニング実行部３６は、系列データの集合Ｓに対し、頻出エピソードマイニングや、頻出系列マイニングを実行する。なお、頻出エピソードマイニングでは、並び順が例えばＡ→Ｂ→Ｃ（Ａ，Ｂ，Ｃはアイテムの一例）のような遷移パターン（以下、「系列パターン」と呼ぶ）と、並び順がＡ→Ｂ→Ｃと一部異なるＡ→Ｃ→Ｂのような相補関係にある系列パターンを含むエピソードパターン（Ａ→｛Ｂ，Ｃ｝と表記される）のうち、系列データの集合Ｓにおいて出現する頻度が所定の閾値以上であるエピソードパターンを抽出する。また、頻出系列マイニングでは、例えばＡ→Ｂ→Ｃのような所定の並び順の系列パターンのうち、系列データの集合Ｓにおいて出現する頻度が所定の閾値以上である系列パターンを抽出する。
【００２３】
低頻度系列抽出部３８は、頻出マイニング実行部３６の処理結果に基づいて、低頻度系列パターンｋcを抽出する。なお、低頻度系列パターンｋcは、異常な系列データに含まれる系列パターン（メッシュＩＤの並び）を意味する。なお、低頻度系列抽出部３８は、頻出エピソードマイニングで抽出されたエピソードパターン（例えば、Ａ→｛Ｂ，Ｃ｝）に、頻出系列マイニングで抽出された系列パターン（例えばＡ→Ｂ→Ｃ）が含まれる場合に、当該抽出されたエピソードパターンに含まれる系列パターンのうち、抽出された系列パターン以外の系列パターン（例えばＡ→Ｃ→Ｂ）で、所定の条件を満たす系列パターンを低頻度系列パターンｋcとする。
【００２４】
異常軌跡決定部４０は、低頻度系列抽出部３８で抽出された低頻度系列パターンｋcにマッチする（抽出された低頻度系列パターンｋcを含む）系列データを、系列データの集合Ｓの中から抽出し、異常軌跡として決定する。また、異常軌跡決定部４０は、低頻度系列パターンｋcに対応する通常系列パターンを含む系列データを系列データの集合Ｓの中から抽出し、通常軌跡として決定する。
【００２５】
出力部４２は、異常軌跡決定部４０で決定された異常軌跡及び通常軌跡を、ユーザ端末２０に対して出力する。
【００２６】
次に、本実施形態のサーバ３０の処理について、図７〜図１５に基づいて、詳細に説明する。図７の処理は、サーバ３０の処理の一連の流れを示すフローチャートである。図７の処理は、ユーザ端末２０が軌跡データの集合Ｔをデータ取得部３２に対して送信した時点から開始される。
【００２７】
図７の処理では、ステップＳ１０において、データ取得部３２が、軌跡データの集合Ｔを取得し、取得した集合Ｔを系列データ生成部３４に対して送信する。次いで、ステップＳ１２では、系列データ生成部３４が、系列データ生成処理を実行する。次いで、ステップＳ１４では、頻出マイニング実行部３６が頻出マイニング処理を実行する。次いで、ステップＳ１６では、低頻度系列抽出部３８が、低頻度系列抽出処理を実行し、次のステップＳ１８では、異常軌跡決定部４０が異常軌跡決定処理を実行する。そして、ステップＳ２０では、出力部４２が、異常軌跡決定処理による決定結果をユーザ端末２０へ出力する。
【００２８】
以下、ステップ１２〜Ｓ１８の処理について、詳細に説明する。
【００２９】
（ステップＳ１２：系列データ生成処理）
まず、系列データ生成部３４による系列データ生成処理（ステップＳ１２）について説明する。ステップＳ１２では、図８のフローチャートに沿った処理が実行される。図８の処理では、まず、ステップＳ３０において、系列データ生成部３４が、系列データの集合Ｓを初期化する。
【００３０】
次いで、ステップＳ３２では、系列データ生成部３４が、図６（ａ）に示すように、分析対象領域Ｒをメッシュ粒度ｄで分割する。なお、系列データ生成部３４は、分割された各メッシュにＩＤ（メッシュＩＤ＝Ａ，Ｂ，Ｃ…）を割り振るものとする。
【００３１】
次いで、ステップＳ３４では、系列データ生成部３４が、軌跡データの集合Ｔが空であるか否かを判断する。ここでの判断が肯定された場合、すなわち、集合Ｔに含まれる全ての軌跡データについての処理が終了したときには、系列データ生成部３４は、図８の全処理を終了する。
【００３２】
一方、ステップＳ３４の判断が否定された場合には、ステップＳ３６に移行する。ステップＳ３６では、系列データ生成部３４が、軌跡データの集合Ｔから軌跡データｔを１つ取り出す。例えば、系列データ生成部３４は、図２の軌跡データの集合Ｔから先頭の軌跡データｔ1を取り出す。
【００３３】
次いで、ステップＳ３８では、系列データ生成部３４が、ｓ、ｐpreを初期化する。なお、ｓは、系列データを意味し、ｐpreは、着目する（ステップＳ４４で取り出す）位置データの前の位置データを意味する。
【００３４】
次いで、ステップＳ４０では、系列データ生成部３４が、図２に示す位置データＰｏｓが空か否かを判断する。ここでの判断が否定された場合には、ステップＳ４４に移行する。
【００３５】
ステップＳ４４に移行すると、系列データ生成部３４が、位置データＰｏｓから先頭の位置データｐを１つ取り出す。例えば、系列データ生成部３４は、軌跡データｔ1の先頭の位置データ（36.25,135.55）（図６（ａ）のｐ1）を取り出す。
【００３６】
次いで、ステップＳ４６では、系列データ生成部３４が、ｐpreに位置データが格納されているか否かを判断する。ここでは、ステップＳ３８において、ｐpreが初期化されているので、判断は否定され、ステップＳ４８に移行する。
【００３７】
ステップＳ４８に移行した場合、系列データ生成部３４は、位置データ（ｐ1）をｐpreに格納する。その後は、ステップＳ４０に戻る。
【００３８】
ステップＳ４０に戻ると、系列データ生成部３４が、図２に示す位置データＰｏｓが空か否かを判断する。ここでの判断が否定された場合には、ステップＳ４４に移行し、系列データ生成部３４は、位置データＰｏｓから先頭の位置データｐを１つ取り出す。例えば、系列データ生成部３４は、軌跡データｔ1の２番目の位置データ（36.08,137.71）（図６（ａ）のｐ2）を取り出す。
【００３９】
次いで、ステップＳ４６では、系列データ生成部３４が、ｐpreに位置データが格納されているか否かを判断する。ここでは、前のステップＳ４８において、ｐpreに位置データｐ1が格納されたので、判断は肯定され、ステップＳ５０に移行する。
【００４０】
ステップＳ５０に移行した場合、系列データ生成部３４は、ｐpre（＝ｐ1）と位置データｐ（＝ｐ2）を結ぶ直線と交差するメッシュのメッシュＩＤを順にｓに連結する。ただし、ｓの右端(最後につなげたＩＤ)が交差するメッシュと同じメッシュＩＤならば連結しない（すなわち、同一のメッシュＩＤを連続して出力しないようにする）。ここでは、位置データｐ1とｐ2とを結ぶ直線が、メッシュＩＤ＝Ａのメッシュと交差するので、ｓにＡが連結されることになる。
【００４１】
その後は、ステップＳ４４，Ｓ４６，Ｓ５０の処理が繰り返されることにより、軌跡データｔ1を、ｔ1＝ＡＤＥＨＩと変換することができる。なお、１つの軌跡データの変換が終了すると、ステップＳ４０の判断が肯定されるので、ステップＳ４２に移行し、系列データ生成部３４は、系列データの集合Ｓに系列データｓを格納し（図６（ｂ）参照）、ステップＳ３４に戻る。
【００４２】
以降、ステップＳ３４の判断が肯定されるまで、ステップＳ３６〜Ｓ５０の処理・判断が繰り返され、集合Ｔが空になった段階（ステップＳ３４の判断が肯定された段階）で、図８の全処理が終了する。以上の処理により、図６（ｂ）に示すように、軌跡データｔ1〜ｔ8の系列データを集合Ｓに格納することができる。
【００４３】
（ステップＳ１４：頻出マイニング処理）
次に、頻出マイニング実行部３６による頻出マイニング処理（ステップＳ１４）について説明する。ステップＳ１４では、図９のフローチャートに沿った処理が実行される。
【００４４】
図９の処理では、まず、ステップＳ６０において、頻出マイニング実行部３６が、実行結果の集合Ｊfreq，Ｋfreqを初期化する。
【００４５】
次いで、ステップＳ６２において、頻出マイニング実行部３６が、γ＝２α＋βを閾値（第１の頻度）とし、パターンのサイズ（アイテム数）を３、型に扇型（またはその逆）を指定し、頻出エピソードマイニングを実行する。頻出マイニング実行部３６は、実行結果をＪfreqに格納する。
【００４６】
ここで、パターンのサイズが３で、型が扇型（またはその逆）のエピソードパターンとは、図１０（ａ）、図１０（ｂ）に示すようなエピソードパターンである。具体的には、図１０（ａ）に示すように、一例として、Ａ，Ｂ，Ｃ３つのアイテムを含むパターンであり、先頭のアイテム（Ａ）が共通で、後ろの２つのアイテム（Ｂ，Ｃ）が順不同である２つのパターン（Ａ→Ｂ→Ｃ，Ａ→Ｃ→Ｂ）を含むエピソードパターンが、扇型のエピソードパターンＡ→{Ｂ，Ｃ}と表される。また、図１０（ｂ）に示すように、一例として、Ａ，Ｂ，Ｃ３つのアイテムを含むパターンであり、末尾のアイテム（Ｃ）が共通で、前の２つのアイテム（Ａ，Ｂ）が順不同である２つのパターン（Ａ→Ｂ→Ｃ，Ｂ→Ａ→Ｃ）を含むエピソードパターンが、逆扇型のエピソードパターン{Ａ，Ｂ}→Ｃと表される。
【００４７】
本ステップＳ６２では、頻出マイニング実行部３６は、図１１（ａ）に示す系列データの集合Ｓにおいて、Ａ→{Ｂ，Ｃ}のように表すことのできるエピソードパターンの出現頻度が、閾値γ（＝２α＋β）以上であるものを見つけ出す。
【００４８】
ここで、αは、Ａ→Ｂ→ＣやＡ→Ｃ→Ｂなどで表される系列パターン（並び順が定められたパターン）のうち、異常な系列パターンとして決定すべき出現頻度の閾値を意味する。また、βは、異常な系列パターンとして決定すべき系列パターン（例えばＡ→Ｂ→Ｃ）と、当該系列パターンと相補関係にある（同一のエピソードパターンに含まれる）系列パターン（例えばＡ→Ｃ→Ｂ）との出現頻度の差の閾値を意味する。αとして１、βとして２が設定された場合、ステップＳ６２で用いる閾値γはγ＝２・１＋２＝４となる。
【００４９】
ステップＳ６２において、閾値γ＝４で頻出エピソードマイニングを行ったときの結果が図１１（ｂ）に示されている。この例では、出現頻度が閾値γ＝４以上のエピソードパターンとしてＡ→｛Ｅ，Ｉ｝が抽出されることになる（図１１（ｂ）において太線枠で示している）。
【００５０】
図９に戻り、次のステップＳ６４では、頻出マイニング実行部３６が、δ＝α＋βを閾値（第２の頻度）とし、パターンのサイズを３に指定し、頻出系列パターンマイニングを実行する。この場合、頻出マイニング実行部３６は、系列データの集合Ｓの中から、「Ａ→Ｂ→Ｃ」などで表現される系列パターンのうち、出現頻度が閾値δ＝３以上の系列パターンを抽出することになる。なお、頻出マイニング実行部３６は、実行結果をＫfreqに格納する。
【００５１】
この場合、前述したのと同様、αを１、βを２とすると、閾値δはδ＝１＋２＝３となる。
【００５２】
ステップＳ６４において、閾値δ＝３で頻出系列マイニングを行ったときの結果が図１１（ｃ）に示されている。この例では、出現頻度が閾値δ＝３以上の系列パターンとしてＡ→Ｅ→Ｉ、Ａ→Ｆ→Ｉ、Ｈ→Ｆ→Ｃが抽出されることになる（図１１（ｃ）において太線枠で示している）。
【００５３】
（ステップＳ１６：低頻度系列抽出処理）
次に、低頻度系列抽出部３８による低頻度系列抽出処理（ステップＳ１６）について説明する。ステップＳ１６では、図１２のフローチャートに沿った処理が実行される。
【００５４】
図１２の処理では、まず、ステップＳ７０において、低頻度系列抽出部３８は、相補系列パターン対の集合Ｃを初期化する。次いで、ステップＳ７２では、低頻度系列抽出部３８は、頻出エピソードマイニングの結果の集合Ｊfreq内を全て処理したか否かを判断する。ここでの判断が否定されると、ステップＳ７４に移行する。
【００５５】
ステップＳ７４に移行すると、低頻度系列抽出部３８は、頻出エピソードマイニングの実行結果の集合Ｊfreqからエピソードパターンｊを１つ取り出す。ここでは、頻出エピソードマイニングの実行結果の中から、図１３（ａ）において実線矢印で示す閾値γ＝４以上のエピソードパターンＡ→{Ｅ，Ｉ}を取り出す。
【００５６】
次いで、ステップＳ７６では、低頻度系列抽出部３８が、頻出系列マイニングの実行結果の集合Ｋfreq内の全てを処理したか否かを判断する。ここでの判断が否定されると、ステップＳ７８に移行する。
【００５７】
ステップＳ７８に移行すると、低頻度系列抽出部３８は、頻出系列マイニングの実行結果Ｋfreqから系列パターンｋを１つ取り出す。例えば、低頻度系列抽出部３８は、図１３（ｂ）において破線矢印で示すＡ→Ｅ→Ｉを取り出す。
【００５８】
次いで、ステップＳ８０では、低頻度系列抽出部３８がｊとｋから求まるパターンｋcと、ｋと、が相補系列パターン対であるか否かを判断する。ここで、低頻度系列抽出部３８は、エピソードパターンｊと系列パターンｋに基づいて、エピソードパターンｊに含まれる系列パターンのうち、系列パターンｋ以外の系列パターンをｋcとする。上記のように、エピソードパターンｊがＡ→{Ｅ，Ｉ}であり、系列パターンｋがＡ→Ｅ→Ｉである場合には、系列パターンｋcとして、Ａ→Ｉ→Ｅが求められる。そして、低頻度系列抽出部３８は、系列パターンｋとｋcとを比較し、系列パターンｋ：Ａ→Ｅ→Ｉと、系列パターンｋc：Ａ→Ｉ→Ｅとが相補系列パターン対をなすか否かを判断する。上記例の場合、系列パターンｋ：Ａ→Ｅ→Ｉと、系列パターンｋc：Ａ→Ｉ→Ｅは相補系列パターン対をなすので、ステップＳ８０の判断は肯定され、ステップＳ８２に移行する。
【００５９】
なお、ステップＳ７８において、例えば、系列パターンｋとしてＡ→Ｆ→Ｉが取り出された場合、ステップＳ８０では、エピソードパターンｊと系列パターンｋからパターンｋcを求めることができない。このような場合には、ステップＳ８０の判断が否定されて、ステップＳ７８に戻る。
【００６０】
ステップＳ８０の判断が肯定されて、ステップＳ８２に移行すると、低頻度系列抽出部３８は、系列パターンｋcの頻度がα（＝１）以上で、かつｋとｋcの頻度差がβ（＝２）以上であるか否かを判断する。ここでの判断が否定された場合には、ステップＳ７２に戻るが、肯定された場合には、ステップＳ８４に移行する。なお、上述した系列パターンｋc：Ａ→Ｉ→Ｅの場合、図１３（ｂ）に示すように、出現頻度は１であるので、判断は肯定されて、ステップＳ８４に移行する。
【００６１】
ステップＳ８４に移行された場合、低頻度系列抽出部３８は、Ｃに相補系列パターン対（ｋ，ｋc）を格納し（図１３（ｃ）参照）、ステップＳ７２に戻る。
【００６２】
その後は、ステップＳ７２以降の処理・判断を繰り返し、ステップＳ７２の判断が否定された段階で、図１２の全処理を終了する。なお、図１３に示す残りの系列パターンＡ→Ｆ→Ｉと、Ｈ→Ｆ→Ｃは、エピソードパターンＡ→{Ｅ，Ｉ}との間で系列パターンｋcを生成することができないので、これらに基づいて相補系列パターン対（ｋ，ｋc）がＣに格納されることはない。
【００６３】
（ステップＳ１８：異常軌跡決定処理）
次に、異常軌跡決定部４０による異常軌跡決定処理（ステップＳ１８）について説明する。ステップＳ１８では、図１４のフローチャートに沿った処理が実行される。
【００６４】
図１４の処理では、まず、ステップＳ１０２において、異常軌跡決定部４０は、集合Ａを初期化する。次いで、ステップＳ１０４では、異常軌跡決定部４０がＣ内（図１２の処理で格納された相補系列パターン対）を全て処理したか否かを判断する。ここでの判断が否定された場合には、ステップＳ１０６に移行する。
【００６５】
ステップＳ１０６に移行すると、異常軌跡決定部４０は、Ｃから相補系列パターン対（ｋ，ｋc)を１つ取り出す。ここでは、異常軌跡決定部４０は、図１３（ｃ）に示す（ｋ，ｋc）＝（Ａ→Ｅ→Ｉ，Ａ→Ｉ→Ｅ）を取り出すものとする。
【００６６】
次いで、ステップＳ１０８では、異常軌跡決定部４０が軌跡データの集合Ｔ（図２）内を全て処理したか否かを判断する。ここでの判断が否定された場合には、ステップＳ１１２に移行する。
【００６７】
ステップＳ１１２に移行すると、異常軌跡決定部４０は、集合Ｔから軌跡データｔを１つ取り出す。ここでは、例えば、ｔ1の軌跡データを取り出すものとする。
【００６８】
次いで、ステップＳ１１４では、異常軌跡決定部４０は、ＩＤnormal，ＩＤabnormalを初期化する。次いで、ステップＳ１１６では、異常軌跡決定部４０は、軌跡データｔが相補系列パターン対（ｋ，ｋc)に含まれる系列パターンｋのメッシュＩＤの領域を順番に全て通るか否かを判断する。ここでの判断が肯定された場合には、ステップＳ１１８に移行し、異常軌跡決定部４０は、ＩＤnormalにｔを格納し、ステップＳ１２０に移行する。一方、ステップＳ１１６の判断が否定された場合には、ステップＳ１１８を経ずに、ステップＳ１２０に移行する。
【００６９】
ステップＳ１２０に移行すると、異常軌跡決定部４０は、軌跡データｔが相補系列パターン対（ｋ，ｋc)に含まれる系列パターンｋcのメッシュＩＤの領域を順番に全て通るか否かを判断する。ここでの判断が肯定された場合には、ステップＳ１２２に移行し、異常軌跡決定部４０は、ＩＤabnormalにｔを格納し、ステップＳ１０８に戻る。一方、ステップＳ１２０の判断が否定された場合には、ステップＳ１２２を経ずに、ステップＳ１０８に戻る。
【００７０】
なお、本実施形態では、軌跡データｔ1はｔ1＝ＡＤＥＨＩであり、パターン対ｋ＝Ａ→Ｅ→Ｉの順番に全て通っているので、ステップＳ１１８において、ｔ1がＩＤnormalに格納されることになる。
【００７１】
ステップＳ１０８に戻った場合、上記と同様、異常軌跡決定部４０は、軌跡データの集合Ｔ（図２）内を全て処理したか否かを判断する。ここでの判断が肯定された場合には、ステップＳ１１０に移行し、異常軌跡決定部４０は、集合Ａに(ＩＤnormal，ＩＤabnormal)を格納する。その後は、ステップＳ１０４に戻る。なお、本実施形態では、図１５（ａ）に示すように、軌跡データｔ1〜ｔ8について、系列パターンｋ又はｋcが含まれるかを判断する。この場合、図１５（ａ）の座標上において太実線で示すｔ1、ｔ2、ｔ3が集合ＡのＩＤnormalに格納されることになる（図１５（ｂ）参照）。また、図１５（ａ）の座標上において太破線で示すｔ4が集合ＡのＩＤabnormalに格納されることになる（図１５（ｂ）参照）
【００７２】
図１４に戻り、ステップＳ１０４に戻ると、異常軌跡決定部４０は、上記と同様、Ｃ内（図１２の処理で格納された相補系列パターン対）を全て処理したか否かを判断する。ここでの判断が否定された場合には、ステップＳ１０６以降の処理を、上述したように実行する。一方、ステップＳ１０４の判断が肯定された場合には、図１４の全処理を終了する。
【００７３】
なお、出力部４２は、図１５（ｂ）に示す通常軌跡と異常軌跡の組の集合Ａを、ユーザ端末２０に対して出力する（図７のステップＳ２０）。
【００７４】
ここで、上述したように頻出エピソードマイニングの閾値γをγ＝２α＋βとし、系列エピソードマイニングの閾値δをδ＝α＋βとした理由について説明する。
【００７５】
相補系列パターン対(ｋ，ｋc)が存在した場合、系列パターンｋ，ｋcの出現頻度はともにα以上である。また、系列パターンｋ，ｋcのうち出現頻度の高い方をｋとすると、系列パターンｋ，ｋcの出現頻度差はβ以上なので、閾値（δ）としてはα＋βとするのが適切である。
【００７６】
また、系列パターンｋにマッチする軌跡データの数を｜ｋ｜、系列パターンｋcにマッチする軌跡データの数を｜ｋc｜、系列パターンｋ，ｋcに対応するエピソードパターンｊにマッチする軌跡データの数を｜ｊ｜とすると、相補系列パターン対の条件下では、|ｊ|≧|ｋ|＋|ｋc|が成り立つ。また、ｋcは頻度α以上のパターンである。よって、頻出エピソードマイニングに用いる閾値（γ）としてはγ＝２α＋βとするのが適切である。
【００７７】
このように、閾値γ、δを決定することで、頻出エピソードマイニングと頻出系列マイニングの処理を適切に行うことができる。すなわち、各閾値を上記よりも大きくすることにより生じる（ｋ，ｋc）の検出漏れや、各閾値を上記よりも小さくすることにより生じる無駄な処理の発生を抑制することができる。なお、閾値γやδを上記のように定めることとすれば、図１２のステップＳ８２の判断は不要となる。この場合、ステップＳ８０の判断が肯定された後は、直接ステップＳ８４に移行すればよい。
【００７８】
以上、詳細に説明したように、本実施形態によると、頻出マイニング実行部３６は、系列データの集合Ｓにおいて、閾値γ以上の出現頻度のエピソードパターンを頻出エピソードマイニングにより抽出するとともに、閾値δ以上の出現頻度の系列パターンを頻出系列マイニングにより抽出する。そして、低頻度系列抽出部３８は、抽出されたエピソードパターンに対応する系列パターンが抽出された場合に、当該エピソードパターンに含まれる系列パターンのうち抽出された系列パターン以外の系列パターンを特定し、特定された系列パターンから異常な系列パターンを決定する。これにより、本実施形態では、頻出エピソードマイニングと頻出系列マイニングを用いることで、異常な系列パターンである可能性のある系列パターンを絞り込むことができる（関心の無い系列パターンを除外することができる）ので、異常な系列パターンの決定のために必要な計算量や計算時間を低減することができる。したがって、本実施形態によれば、処理の効率化を図ることができる。
【００７９】
ここで、頻出系列マイニングのみを用いた場合（比較例：特許文献１）について、説明する。比較例の場合、頻出系列マイニングにより、例えば、高頻度の系列パターンとして、Ａ→Ｅ→Ｉの系列パターンが抽出されたとする（図６（ａ）、図６（ｂ）等参照）。この場合、サーバ３０では、Ａ→Ｅ→Ｉを並べ替えた系列パターン（Ａ→Ｉ→Ｅ、Ｉ→Ａ→Ｅ、Ｉ→Ｅ→Ａ、Ｅ→Ａ→Ｉ、Ｅ→Ｉ→Ａ）の全てについて頻度を調べ、低頻度（例えば出現頻度１以上）の系列パターンを抽出する必要があった。このように、比較例を採用すると、調べる必要のある系列パターンが多くなるため、計算量や計算時間の面で効率が悪かったが、本実施形態のような方法を採用することで、計算量や計算時間を低減することが可能となっている。
【００８０】
また、本実施形態では、図１３（ａ）に示す出現頻度が閾値３以下のエピソードパターンについては、一切処理を行わないので、この点からも効率がよいといえる。
【００８１】
また、本実施形態によれば、頻出エピソードマイニングで抽出するエピソードパターンの出現頻度をγ（＝２α＋β）以上とし、頻出系列マイニングで抽出するエピソードパターンの出現頻度をδ（＝α＋β）以上としている。これにより、異常な系列パターンである可能性のある系列パターンを適切に絞り込むことができる。
【００８２】
なお、上記実施形態では、図１０（ａ）に示すような扇型のエピソードパターンを例にとり説明したが、これに限られるものではなく、図１０（ｂ）に示すような逆扇形のエピソードパターンを用いることとしてもよい。
【００８３】
なお、上記実施形態では、出力部４２が、通常軌跡と異常軌跡の組をユーザ端末２０に対して出力する場合について説明したが、これに限られるものではなく、異常軌跡の情報のみをユーザ端末２０に対して出力することとしてもよい。
【００８４】
なお、上記実施形態では、交通分野において情報処理システム１００を適用する場合について説明したが、これに限られるものではなく、ＢＰＭ（Business Process Management）分野において、異常証跡データを検出するのにも用いることができる。例えば、通常、「起票→チェック→課長承認→部長承認→発注」の流れで業務が進む場合に、「起票→チェック→部長承認→課長承認→発注」となっている証跡パターンを検出するために、上記実施形態の情報処理システムを用いることができる。
【００８５】
なお、上記実施形態では、サーバ３０が図７の処理を行う場合について説明したが、これに限られるものではなく、例えば、ユーザ端末２０が図７の処理を行うこととしてもよい。
【００８６】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、処理装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体（ただし、物理的な形態を持たない媒体、例えば搬送波は含まないものとする）に記録しておくことができる。
【００８７】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ（Digital Versatile Disc）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）などの可搬型記録媒体の形態で販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【００８８】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【００８９】
上述した実施形態は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【００９０】
なお、以上の説明に関して更に以下の付記を開示する。
（付記１）  複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出方法であって、
一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出工程と、
前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出工程と、
前記第１抽出工程で抽出されたエピソードパターンに対応する前記第２抽出工程で抽出された遷移パターンがある場合に、前記第１抽出工程で抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出工程で抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定工程と、をコンピュータが実行することを特徴とする異常遷移パターン検出方法。
（付記２）  前記異常遷移パターンとして決定すべき遷移パターンの出現頻度の閾値をα、前記異常遷移パターンとして決定すべき遷移パターンと、当該遷移パターンと相補関係にある遷移パターンとの出現頻度の差の閾値をβとしたときに、
前記第１の頻度が２α＋βであり、前記第２の頻度がα＋βであることを特徴とする付記１に記載の異常遷移パターン検出方法。
（付記３）  前記遷移パターンは、異なる３つのアイテムを含み、
前記相補関係にある遷移パターン同士は、先頭又は末尾のアイテムが一致することを特徴とする付記１又は２に記載の異常遷移パターン検出方法。
（付記４）  前記第１抽出工程では、頻出エピソードマイニングの手法を用い、前記第２抽出工程では、頻出系列パターンマイニングの手法を用いることを特徴とする付記１〜３のいずれかに記載の異常遷移パターン検出方法。
（付記５）  コンピュータに、複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出させる異常遷移パターン検出プログラムであって、
コンピュータに、
一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出し、
前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出し、
前記抽出された遷移パターンに、前記抽出されたエピソードパターンに対応する遷移パターンがある場合に、前記抽出されたエピソードパターンに含まれる遷移パターンのうち前記抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する、処理を実行させることを特徴とする異常遷移パターン検出プログラム。
（付記６）  前記異常遷移パターンとして決定すべき遷移パターンの出現頻度の閾値をα、前記異常遷移パターンとして決定すべき遷移パターンと、当該遷移パターンと相補関係にある遷移パターンとの出現頻度の差の閾値をβとしたときに、
前記第１の頻度が２α＋βであり、前記第２の頻度がα＋βであることを特徴とする付記５に記載の異常遷移パターン検出プログラム。
（付記７）  前記遷移パターンは、異なる３つのアイテムを含み、
前記相補関係にある遷移パターン同士は、先頭又は末尾のアイテムが一致することを特徴とする付記５又は６に記載の異常遷移パターン検出プログラム。
（付記８）  前記エピソードパターンを抽出する処理では、頻出エピソードマイニングの手法を用い、前記遷移パターンを抽出する処理では、頻出系列パターンマイニングの手法を用いることを特徴とする付記５〜７のいずれかに記載の異常遷移パターン検出プログラム。
（付記９）  複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出装置であって、
一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出部と、
前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出部と、
前記第１抽出部が抽出したエピソードパターンに対応する前記第２抽出部が抽出した遷移パターンがある場合に、前記第１抽出工程で抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部が抽出した遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定部と、を備える異常遷移パターン検出装置。
（付記１０）  前記異常遷移パターンとして決定すべき遷移パターンの出現頻度の閾値をα、前記異常遷移パターンとして決定すべき遷移パターンと、当該遷移パターンと相補関係にある遷移パターンとの出現頻度の差の閾値をβとしたときに、
前記第１の頻度が２α＋βであり、前記第２の頻度がα＋βであることを特徴とする付記９に記載の異常遷移パターン検出装置。
（付記１１）  前記遷移パターンは、異なる３つのアイテムを含み、
前記相補関係にある遷移パターン同士は、先頭又は末尾のアイテムが一致することを特徴とする付記９又は１０に記載の異常遷移パターン検出装置。
（付記１２）  前記第１抽出部は、頻出エピソードマイニングの手法を用い、前記第２抽出部は、頻出系列パターンマイニングの手法を用いることを特徴とする付記９〜１１のいずれかに記載の異常遷移パターン検出装置。
【符号の説明】
【００９１】
３０  サーバ（異常遷移パターン検出装置）
３６  頻出マイニング実行部（第１抽出部、第２抽出部）
３８  低頻度系列抽出部（決定部）
【図１】
0005928165.tif 000002
【図２】
0005928165.tif 000003
【図３】
0005928165.tif 000004
【図４】
0005928165.tif 000005
【図５】
0005928165.tif 000006
【図６】
0005928165.tif 000007
【図７】
0005928165.tif 000008
【図８】
0005928165.tif 000009
【図９】
0005928165.tif 000010
【図１０】
0005928165.tif 000011
【図１１】
0005928165.tif 000012
【図１２】
0005928165.tif 000013
【図１３】
0005928165.tif 000014
【図１４】
0005928165.tif 000015
【図１５】
0005928165.tif 000016