[go: up one dir, main page]

JP5928165B2 - 異常遷移パターン検出方法、プログラム及び装置 - Google Patents

異常遷移パターン検出方法、プログラム及び装置 Download PDF

Info

Publication number
JP5928165B2
JP5928165B2 JP2012126438A JP2012126438A JP5928165B2 JP 5928165 B2 JP5928165 B2 JP 5928165B2 JP 2012126438 A JP2012126438 A JP 2012126438A JP 2012126438 A JP2012126438 A JP 2012126438A JP 5928165 B2 JP5928165 B2 JP 5928165B2
Authority
JP
Japan
Prior art keywords
pattern
transition
transition pattern
abnormal
episode
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
JP2012126438A
Other languages
English (en)
Other versions
JP2013250888A (ja
Inventor
裕章 森川
裕章 森川
達哉 浅井
達哉 浅井
多湖　真一郎
真一郎 多湖
孝 河東
孝 河東
稲越　宏弥
宏弥 稲越
湯上　伸弘
伸弘 湯上
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP2012126438A priority Critical patent/JP5928165B2/ja
Priority to US13/859,974 priority patent/US9299033B2/en
Publication of JP2013250888A publication Critical patent/JP2013250888A/ja
Application granted granted Critical
Publication of JP5928165B2 publication Critical patent/JP5928165B2/ja
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N5/00—Computing arrangements using knowledge-based models
    • G06N5/04—Inference or reasoning models
    • G06N5/046—Forward inferencing; Production systems
    • G06N5/047—Pattern matching networks; Rete networks
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N20/00—Machine learning
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N5/00—Computing arrangements using knowledge-based models
    • G06N5/02—Knowledge representation; Symbolic representation
    • G06N5/022—Knowledge engineering; Knowledge acquisition
    • G06N5/025—Extracting rules from data
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G06Q10/063—Operations research, analysis or management
    • G06Q10/0637—Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of effectiveness of goals
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V20/00—Scenes; Scene-specific elements
    • G06V20/50—Context or environment of the image
    • G06V20/52—Surveillance or monitoring of activities, e.g. for recognising suspicious objects
    • G06V20/54—Surveillance or monitoring of activities, e.g. for recognising suspicious objects of traffic, e.g. cars on the road, trains or boats
    • G—PHYSICS
    • G08—SIGNALLING
    • G08G—TRAFFIC CONTROL SYSTEMS
    • G08G1/00—Traffic control systems for road vehicles
    • G08G1/01—Detecting movement of traffic to be counted or controlled
    • G08G1/0104—Measuring and analyzing of parameters relative to traffic conditions
    • G08G1/0108—Measuring and analyzing of parameters relative to traffic conditions based on the source of data
    • G08G1/0112—Measuring and analyzing of parameters relative to traffic conditions based on the source of data from the vehicle, e.g. floating car data [FCD]
    • G—PHYSICS
    • G08—SIGNALLING
    • G08G—TRAFFIC CONTROL SYSTEMS
    • G08G1/00—Traffic control systems for road vehicles
    • G08G1/01—Detecting movement of traffic to be counted or controlled
    • G08G1/0104—Measuring and analyzing of parameters relative to traffic conditions
    • G08G1/0125—Traffic data processing
    • G08G1/0129—Traffic data processing for creating historical data or processing based on historical data
    • G—PHYSICS
    • G08—SIGNALLING
    • G08G—TRAFFIC CONTROL SYSTEMS
    • G08G1/00—Traffic control systems for road vehicles
    • G08G1/20—Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • General Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Economics (AREA)
  • Strategic Management (AREA)
  • Chemical & Material Sciences (AREA)
  • Educational Administration (AREA)
  • Analytical Chemistry (AREA)
  • Mathematical Physics (AREA)
  • Computing Systems (AREA)
  • Evolutionary Computation (AREA)
  • Data Mining & Analysis (AREA)
  • Artificial Intelligence (AREA)
  • Computational Linguistics (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Development Economics (AREA)
  • General Business, Economics & Management (AREA)
  • Tourism & Hospitality (AREA)
  • Quality & Reliability (AREA)
  • Operations Research (AREA)
  • Marketing (AREA)
  • Game Theory and Decision Science (AREA)
  • Multimedia (AREA)
  • Medical Informatics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Traffic Control Systems (AREA)

Description

本件は、異常遷移パターン検出方法、プログラム及び装置に関する。
従来、交通分野において、大量の軌跡データから他と異なる軌跡データを検出したり、ＢＰＭ（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）などの可搬型記録媒体の形態で販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
上述した実施形態は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
なお、以上の説明に関して更に以下の付記を開示する。
（付記１） 複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出方法であって、
一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出工程と、
前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出工程と、
前記第１抽出工程で抽出されたエピソードパターンに対応する前記第２抽出工程で抽出された遷移パターンがある場合に、前記第１抽出工程で抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出工程で抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定工程と、をコンピュータが実行することを特徴とする異常遷移パターン検出方法。
（付記２） 前記異常遷移パターンとして決定すべき遷移パターンの出現頻度の閾値をα、前記異常遷移パターンとして決定すべき遷移パターンと、当該遷移パターンと相補関係にある遷移パターンとの出現頻度の差の閾値をβとしたときに、
前記第１の頻度が２α＋βであり、前記第２の頻度がα＋βであることを特徴とする付記１に記載の異常遷移パターン検出方法。
（付記３） 前記遷移パターンは、異なる３つのアイテムを含み、
前記相補関係にある遷移パターン同士は、先頭又は末尾のアイテムが一致することを特徴とする付記１又は２に記載の異常遷移パターン検出方法。
（付記４） 前記第１抽出工程では、頻出エピソードマイニングの手法を用い、前記第２抽出工程では、頻出系列パターンマイニングの手法を用いることを特徴とする付記１〜３のいずれかに記載の異常遷移パターン検出方法。
（付記５） コンピュータに、複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出させる異常遷移パターン検出プログラムであって、
コンピュータに、
一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出し、
前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出し、
前記抽出された遷移パターンに、前記抽出されたエピソードパターンに対応する遷移パターンがある場合に、前記抽出されたエピソードパターンに含まれる遷移パターンのうち前記抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する、処理を実行させることを特徴とする異常遷移パターン検出プログラム。
（付記６） 前記異常遷移パターンとして決定すべき遷移パターンの出現頻度の閾値をα、前記異常遷移パターンとして決定すべき遷移パターンと、当該遷移パターンと相補関係にある遷移パターンとの出現頻度の差の閾値をβとしたときに、
前記第１の頻度が２α＋βであり、前記第２の頻度がα＋βであることを特徴とする付記５に記載の異常遷移パターン検出プログラム。
（付記７） 前記遷移パターンは、異なる３つのアイテムを含み、
前記相補関係にある遷移パターン同士は、先頭又は末尾のアイテムが一致することを特徴とする付記５又は６に記載の異常遷移パターン検出プログラム。
（付記８） 前記エピソードパターンを抽出する処理では、頻出エピソードマイニングの手法を用い、前記遷移パターンを抽出する処理では、頻出系列パターンマイニングの手法を用いることを特徴とする付記５〜７のいずれかに記載の異常遷移パターン検出プログラム。
（付記９） 複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出装置であって、
一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出部と、
前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出部と、
前記第１抽出部が抽出したエピソードパターンに対応する前記第２抽出部が抽出した遷移パターンがある場合に、前記第１抽出工程で抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部が抽出した遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定部と、を備える異常遷移パターン検出装置。
（付記１０） 前記異常遷移パターンとして決定すべき遷移パターンの出現頻度の閾値をα、前記異常遷移パターンとして決定すべき遷移パターンと、当該遷移パターンと相補関係にある遷移パターンとの出現頻度の差の閾値をβとしたときに、
前記第１の頻度が２α＋βであり、前記第２の頻度がα＋βであることを特徴とする付記９に記載の異常遷移パターン検出装置。
（付記１１） 前記遷移パターンは、異なる３つのアイテムを含み、
前記相補関係にある遷移パターン同士は、先頭又は末尾のアイテムが一致することを特徴とする付記９又は１０に記載の異常遷移パターン検出装置。
（付記１２） 前記第１抽出部は、頻出エピソードマイニングの手法を用い、前記第２抽出部は、頻出系列パターンマイニングの手法を用いることを特徴とする付記９〜１１のいずれかに記載の異常遷移パターン検出装置。
３０ サーバ（異常遷移パターン検出装置）
３６ 頻出マイニング実行部（第１抽出部、第２抽出部）
３８ 低頻度系列抽出部（決定部）

Claims (6)

  1. 複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出方法であって、
    第１抽出部が、一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出するステップと、
    第２抽出部が、前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出するステップと、
    決定部が、前記第１抽出部により抽出されたエピソードパターンに対応する前記第２抽出部により抽出された遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部により抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定するステップと、
    を含むことを特徴とする異常遷移パターン検出方法。
  2. 前記異常遷移パターンとして決定すべき遷移パターンの出現頻度の閾値をα、前記異常遷移パターンとして決定すべき遷移パターンと、当該遷移パターンと相補関係にある遷移パターンとの出現頻度の差の閾値をβとしたときに、
    前記第１の頻度が２α＋βであり、前記第２の頻度がα＋βであることを特徴とする請求項１に記載の異常遷移パターン検出方法。
  3. 前記遷移パターンは、異なる３つのアイテムを含み、
    前記相補関係にある遷移パターン同士は、先頭又は末尾のアイテムが一致することを特徴とする請求項１又は２に記載の異常遷移パターン検出方法。
  4. 前記第１抽出部は、頻出エピソードマイニングの手法を用い、前記第２抽出部は、頻出系列パターンマイニングの手法を用いることを特徴とする請求項１〜３のいずれか一項に記載の異常遷移パターン検出方法。
  5. コンピュータに、複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出させる異常遷移パターン検出プログラムであって、
    前記コンピュータを、
    一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出部、
    前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出部、及び
    前記第２抽出部により抽出された遷移パターンに、前記第１抽出部により抽出されたエピソードパターンに対応する遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部により抽出された遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定部、として機能させることを特徴とする異常遷移パターン検出プログラム。
  6. 複数のアイテムの並び順を表す遷移パターンの中から異常遷移パターンを検出する異常遷移パターン検出装置であって、
    一の遷移パターンと、当該一の遷移パターンのうち一部のアイテムの並び順が異なり相補関係にある遷移パターンと、を含む記述方式で表したエピソードパターンのうち、出現頻度が第１の頻度以上のエピソードパターンを抽出する第１抽出部と、
    前記遷移パターンのうち出現頻度が第２の頻度以上の遷移パターンを抽出する第２抽出部と、
    前記第１抽出部が抽出したエピソードパターンに対応する前記第２抽出部が抽出した遷移パターンがある場合に、前記第１抽出部により抽出されたエピソードパターンに含まれる遷移パターンのうち前記第２抽出部が抽出した遷移パターン以外の遷移パターンを特定し、当該特定された遷移パターンに基づいて異常遷移パターンを決定する決定部と、を備える異常遷移パターン検出装置。
JP2012126438A 2012-06-01 2012-06-01 異常遷移パターン検出方法、プログラム及び装置 Expired - Fee Related JP5928165B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP2012126438A JP5928165B2 (ja) 2012-06-01 2012-06-01 異常遷移パターン検出方法、プログラム及び装置
US13/859,974 US9299033B2 (en) 2012-06-01 2013-04-10 Method and apparatus for detecting abnormal transition pattern

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2012126438A JP5928165B2 (ja) 2012-06-01 2012-06-01 異常遷移パターン検出方法、プログラム及び装置

Publications (2)

Publication Number Publication Date
JP2013250888A JP2013250888A (ja) 2013-12-12
JP5928165B2 true JP5928165B2 (ja) 2016-06-01

Family

ID=49671522

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2012126438A Expired - Fee Related JP5928165B2 (ja) 2012-06-01 2012-06-01 異常遷移パターン検出方法、プログラム及び装置

Country Status (2)

Country Link
US (1) US9299033B2 (ja)
JP (1) JP5928165B2 (ja)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP6020031B2 (ja) 2012-10-19 2016-11-02 富士通株式会社 抽出プログラム、抽出装置及び抽出方法
JP6003561B2 (ja) 2012-11-15 2016-10-05 富士通株式会社 抽出プログラム、抽出装置及び抽出方法
JP5962471B2 (ja) * 2012-11-30 2016-08-03 富士通株式会社 抽出プログラム、抽出装置及び抽出方法
US20170132052A1 (en) * 2015-11-10 2017-05-11 Nice-Systems Ltd Analyzing and automating work-flow in a computerized user-interface

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6601048B1 (en) 1997-09-12 2003-07-29 Mci Communications Corporation System and method for detecting and managing fraud
JP3996428B2 (ja) * 2001-12-25 2007-10-24 松下電器産業株式会社 異常検知装置及び異常検知システム
US7571248B2 (en) * 2002-11-22 2009-08-04 Panasonic Corporation Operation history utilization system and method thereof
JP4476078B2 (ja) * 2004-09-01 2010-06-09 独立行政法人科学技術振興機構 時系列データ判定用プログラム
JP4484643B2 (ja) * 2004-09-10 2010-06-16 独立行政法人科学技術振興機構 時系列データ異常判定用プログラム及び時系列データ異常判別方法
US7944468B2 (en) 2005-07-05 2011-05-17 Northrop Grumman Systems Corporation Automated asymmetric threat detection using backward tracking and behavioral analysis
JP4953834B2 (ja) * 2007-01-17 2012-06-13 株式会社日立製作所 データ解析方法及びデータ解析システム
JP4822280B2 (ja) * 2007-03-12 2011-11-24 三菱電機株式会社 移動体行動解析装置
JP2010009112A (ja) 2008-06-24 2010-01-14 Toshiba Corp 時系列データを生成する装置および方法
US20100211192A1 (en) * 2009-02-17 2010-08-19 Honeywell International Inc. Apparatus and method for automated analysis of alarm data to support alarm rationalization
US8429165B1 (en) * 2012-03-07 2013-04-23 Xerox Corporation Systems and methods of partitioning data for synchronous parallel processing
JP6047017B2 (ja) * 2013-01-11 2016-12-21 キヤノン株式会社 パターン抽出装置および制御方法

Also Published As

Publication number Publication date
US20130325761A1 (en) 2013-12-05
US9299033B2 (en) 2016-03-29
JP2013250888A (ja) 2013-12-12

Similar Documents

Publication Publication Date Title
JP6047017B2 (ja) パターン抽出装置および制御方法
CN108133031B (zh) 一种过滤推荐视频候选结果的方法及装置
US20140207820A1 (en) Method for parallel mining of temporal relations in large event file
JP6295857B2 (ja) 抽出方法、装置、及びプログラム
JP5928165B2 (ja) 異常遷移パターン検出方法、プログラム及び装置
US20170185453A1 (en) Dynamically scalable data collection and analysis for target device
JP2009500704A5 (ja)
US20150135018A1 (en) Analysis method, analysis apparatus, computer-readable storage medium storing analysis program
JP2007334716A (ja) 運用管理システム、監視装置、被監視装置、運用管理方法及びプログラム
US10338197B2 (en) System and method for use of qualitative modeling for signal analysis
JP6988827B2 (ja) 異常識別システム、方法及びプログラム
WO2019142391A1 (ja) データ分析支援システム及びデータ分析支援方法
Kung et al. {CloudSense}: Continuous {Fine-Grain} Cloud Monitoring with Compressive Sensing
US8583754B2 (en) Business flow distributed processing system and method
US20180139288A1 (en) Method, device, and non-transitory computer-readable recording medium
JP7274162B2 (ja) 異常操作検知装置、異常操作検知方法、およびプログラム
JP6523799B2 (ja) 情報分析システム、情報分析方法
JP5104529B2 (ja) 分析支援プログラム、分析支援方法および分析支援装置
CN106407126B (zh) 覆盖率数据的处理方法、装置和服务器
CN110795215A (zh) 一种数据处理方法、计算机设备、存储介质
CN110782327B (zh) 一种异常信息发现方法、装置及设备
JP2016177728A (ja) データ分析装置、及びデータ分析方法
CN104951920A (zh) 服务界面处理装置和方法
CN109542729A (zh) 设备性能参数数据分析方法及装置
KR20150098400A (ko) 다차원 시간차 분석 방법 및 장치

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20150319

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20160122

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20160202

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20160307

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20160329

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20160411

R150 Certificate of patent or registration of utility model

Ref document number: 5928165

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

LAPS Cancellation because of no payment of annual fees