データ解析システム、及びその方法
【課題】順序関係を示す情報を含む時系列データから、時系列パターンを抽出するデータ解析システム及び方法を提供する。
【解決手段】システムを構成するコンピュータ100のプロセッサ101は、メモリ102に記憶されたプログラムを実行し、時系列パターンの各時系列データにおいて繰り返される回数と、時系列パターンの繰り返し回数が所定の回数以上となる時系列データの数である出現頻度を数え上げることによって、所定の繰り返し回数以上であり、かつ、所定の時系列データの数以上で所定の繰り返し回数以上となる時系列パターンを抽出する。更に、時系列データ各々に所定の間隔でチェックポイントを設け、各チェックポイントにおいて各時系列データにおける時系列パターンの繰り返し回数の上限値を算出し、この上限値を用いて出現頻度を数え上げることによって、繰り返し回数を数え上げる時系列パターンと時系列データの範囲を限定する。
【解決手段】システムを構成するコンピュータ100のプロセッサ101は、メモリ102に記憶されたプログラムを実行し、時系列パターンの各時系列データにおいて繰り返される回数と、時系列パターンの繰り返し回数が所定の回数以上となる時系列データの数である出現頻度を数え上げることによって、所定の繰り返し回数以上であり、かつ、所定の時系列データの数以上で所定の繰り返し回数以上となる時系列パターンを抽出する。更に、時系列データ各々に所定の間隔でチェックポイントを設け、各チェックポイントにおいて各時系列データにおける時系列パターンの繰り返し回数の上限値を算出し、この上限値を用いて出現頻度を数え上げることによって、繰り返し回数を数え上げる時系列パターンと時系列データの範囲を限定する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、データ解析システム及び方法に関し、特にデータベースに含まれるデータの出現順序の規則性を明らかにするデータマイニング技術に関する。
【背景技術】
【0002】
モバイル端末、ICカード、ICタグなどのデータ収集環境の普及により、時々刻々の人の行動や物の状態をデータとして獲得し、大量に蓄積することが可能となった。この大量に蓄積された人の行動や物の状態のデータを解析し、特徴的または典型的な行動パターンや状態パターンを抽出し、マーケティングやヘルスケアなどに応用したいというニーズがある。その解決手段として、大量に蓄積されたデータを解析し、その中に埋もれた有用な規則性やパターンを抽出するデータマイニングが知られている。特に、データの時間軸上の出現順序のパターンを解析する技術として時系列パターンマイニングがある。
【0003】
例えば、クレジットカードの利用データの時系列パターンマイニングを考えてみる。顧客が店舗でクレジットカードを利用した履歴がクレジットカードの利用データとして、利用日時、利用店舗、利用額が記録される。大量のクレジットカード利用データから、複数の顧客に共通して現れるパターンとして、順序を伴うパターンである時系列パターンを抽出することが出来る。「店舗Aで購買した顧客は、その後に店舗Bで高額の購買をする場合が多い」のような時系列パターンが抽出された場合、店舗Aと店舗Bに併買行動の関係があることがわかり、店舗の配置、販売戦略に役立てることが出来る。また、Webサイトのアクセスログからユーザの典型的なアクセスパターンを抽出ことが可能であり、抽出されたアクセスパターンに含まれないアクセスが起きていること、過去のデータでは抽出されなかったアクセスパターンが新たなデータで抽出されたことなどの判定により、異常なアクセスの検出に活用出来る。また、建設機械の稼働履歴と故障やメンテナンスの履歴から、故障が発生しやすい稼働状態パターンや通常の稼働パターンを抽出することが可能であり、故障を防ぐ稼働プランの設計や異常な稼働状態の検出に役立てることが出来る。
【0004】
大量のデータから時系列パターンを抽出する研究は、データマイニングの分野
で行われてきた。例えば、特許文献1、非特許文献1に記載の方法がある。特許文献1と非特許文献1の方法では、アイテム(データ項目、事象)の組合せとタイムスタンプ(時刻)又は出現順所を示す識別子からなるデータベースから、ユーザが予め設定した支持度(出現頻度の全データに対する割合を表す)の最小値以上となる時系列パターンを抽出する。時系列パターンはアイテムの組合せ(アイテムセット)の出現順序を含んだパターンであり、1以上のn個のアイテムセットからなる時系列パターンは、<(IS1)・・・(ISn)>で表現される。ここで、(IS1)、・・・、(ISn)はアイテムセットであり、アイテムセットは1以上のアイテムからなる。ある時系列パターンの支持度は、全時系列データの中でその時系列パターンを含む時系列データの割合である。最小支持度以上となる時系列パターンは頻出時系列パターンと呼ばれる。頻出時系列パターン抽出は、候補となる時系列パターン(候補時系列パターン)の作成とデータベースからのデータ読み出しによる時系列データ中に該候補時系列パターンが現れる頻度の数え上げと、支持度の最小値以上の頻度となる時系列パターンの選出によって行われる。
【0005】
時系列パターンマイニングの別の問題として、1つの時系列データにおいて繰り返される時系列パターン(繰り返し時系列パターン)を抽出する問題もある。例えば、クレジットカードの利用データの繰り返し時系列パターン抽出を考えてみる。長期間に渡って利用された1利用者の利用データから、複数回繰り返される利用パターンである時系列パターンを抽出することが出来る。「店舗Cで購買し、次に店舗Dで購買したとき、その後に店舗Eで購買することが多い」のような時系列パターンが抽出された場合、店舗Cと店舗Dと店舗Eを決まった順序で定期的に利用していることが分かり、広告戦略、販売戦略に役立てることや、定期的な利用パターンの傾向から利用者のタイプを分類するセグメンテーションに役立てることが出来る。
【0006】
繰り返し時系列パターンを抽出する研究はデータマイニングの分野、バイオインフォマティクスの分野で行われてきた。例えば、特許文献2、3に記載の方法がある。特許文献2に記載の方法では、一人の時系列データにおいて、所定の頻度以上繰り返される時系列パターンを抽出ことにより、定期的に行っているパターンを抽出出来る。また、特許文献3に記載の方法では、実際に繰り返される厳密な回数を数え上げず、統計的に繰り返されていると判断されたパターンを抽出する。特許文献2と異なり、繰り返されるパターンは意味の無い部分と考えられており、それらを除去することが特許文献3のようなバイオの分野での繰り返しパターン抽出の目的である。特許文献2では、繰り返されるパターンが意味のある部分と考えられており、それらを厳密な出現回数と共に見つけ出すことが目的である。
【先行技術文献】
【特許文献】
【0007】
【特許文献1】特開平8-263346号公報
【特許文献2】特開2001-229202号公報
【特許文献3】米国特許出願公開US2003/0068617
【非特許文献】
【0008】
【非特許文献1】R.Agrawal, R.Srikant, "Mining Sequential Patterns:Generalizations and Performance Improvements", in proceedings ofInternational Conference on Extending Database Technology, 1996
【発明の概要】
【発明が解決しようとする課題】
【0009】
実際の解析あるいは分析では常に全データを分析対象とする訳ではない。例えば、人の行動分析においては、たまたま行われた行動はノイズとして除去し、ある程度の回数以上繰り返された行動のみを分析対象とする場合がある。多くのユーザが定期的に行った行動を有意な行動パターンとして抽出したいというニーズもある。購買分析においては、定期的に繰り返して購買してくれる顧客の購買パターンを知り、そのパターンでの購買を促進することにより、定期的に繰り返し購買をする顧客を生み出すことに役立てることが出来る。
【0010】
このように、前述の特許文献1と非特許文献1、特許文献2と3はそれぞれ、多人数の時系列データにおいて複数の顧客に共通して現れる時系列パターンの抽出、一人の時系列データにおいて複数回繰り返される時系列パターンの抽出が可能である。しかし、この両者を共に考慮して時系列パターンを抽出することは考慮されていなかった。
【0011】
単純には、まず個々の顧客の時系列データで繰り返しパターンを抽出し、それらの中から所定の数以上の顧客で抽出されたパターンを抽出することによって、両者の条件を満たすパターンを抽出出来る。しかし、顧客毎に繰り返す購買パターンは異なるため、単純に組み合わせた方法では不要なパターンの探索処理を膨大な時系列データに対して行うことになり、膨大な不要な処理が発生するため、現実的には困難である。
【0012】
本発明の目的は、各時系列データにおいて所定の回数以上繰り返される時系列パターンであり、所定の数以上の時系列データにおいて該繰り返し回数の条件を満たす時系列パターンである頻出繰り返し時系列パターンを抽出するデータ解析システム及び方法を提供することである。
【0013】
本発明の他の目的は、チェックポイントの利用と繰り返し回数と出現回数の上限値の算出によって、探索処理量を低減するデータ解析システム及び方法を提供することである。
【課題を解決するための手段】
【0014】
上記の目的を達成するため、本発明においては、処理部と記憶部とを備えた計算機を用い、事象と,事象の属するIDと,事象間の順序関係を示す情報の組が複数格納されたデータを、同じIDを有する事象をその順序関係に従って並べた時系列データとし,1以上の事象を順方向に並べた重複順列を時系列パターンとし,所定の数以上の時系列データにおいて,各時系列データにおける所定の回数以上繰り返される時系列パターンである頻出繰り返し時系列パターンを抽出するため,繰り返し回数が未知の時系列パターンについて,各時系列データにおける繰り返し回数を数え上げるステップと,この繰り返し回数が所定の繰り返し回数以上となる時系列データの数を数え上げるステップと,この数え上げた時系列データの数が所定の数以上となる時系列パターンを抽出するステップとを処理部で実行するデータ解析システム及び方法を構成する。
【0015】
また、上記の目的を達成するため、本発明においては、処理部と記憶部とを備えた計算機を用い、事象と,事象の属するIDと,事象間の順序関係を示す情報の組が複数格納されたデータを,同じIDを有する事象をその順序関係に従って並べた時系列データとし,1以上の事象を順方向に並べた重複順列を時系列パターンとし,所定の数以上の時系列データにおいて,各時系列データにおける所定の回数以上繰り返される時系列パターンである頻出繰り返し時系列パターンを抽出するため,各時系列データに,所定の間隔でチェックポイントを設定する第1のステップと,各時系列データにおける繰り返し回数が未知の時系列パターンについて,各時系列データについてチェックポイントから次のチェックポイントまでの範囲で該時系列パターンが繰り返される回数を数え上げる第2のステップと,
該時系列データにおける該時系列パターンの繰り返し回数の上限値を,既に数え上げられたチェックポイントまででの繰り返し回数と,該チェックポイント以降に現れる各事象の繰り返し回数との和から算出する第3のステップと,該算出された上限値が所定の繰り返し回数以上となる時系列データの数を数え上げる第4のステップと,該時系列データの数が所定の数以上となる時系列パターンを抽出する第5のステップと,該抽出された時系列パターンについて前記第2から第5のステップを最後のチェックポイントまで繰り返す第6のステップを処理部で実行するデータ解析システム及び方法を構成する。
【発明の効果】
【0016】
本発明によると、個々の時系列データにおいて所定の回数以上繰り返される時系列パターンであって、かつ、所定の数以上の時系列データにおいて該繰り返し条件を満たす時系列パターンを抽出することが可能となる。
【0017】
また、本発明のデータの処理単位毎に各時系列データの繰り返し回数の数え上げ処理において繰り返し回数の上限値を算出し、所定の繰り返し回数未満となる場合に以降の繰り返し回数の数え上げを回避すること、出現頻度の数え上げをデータの処理単位毎に行うことによって解析処理量を低減することが可能となる。
【図面の簡単な説明】
【0018】
【図1】第1の実施例のシステム構成例を示す図である。
【図2】第1の実施例に係る、ユーザインタフェースの一例を示す図である。
【図3】第1の実施例に係る、ユーザ操作とシステム動作の関連を示したフロー図である。
【図4】第1の実施例に係る、頻出繰り返し時系列パターン抽出処理の概要を示すフローチャート図である。
【図5】第1の実施例に係る、頻出繰り返しアイテム抽出処理を示すフローチャート図である。
【図6】第1の実施例に係る、時系列データ読み出し処理を示すフローチャート図である。
【図7】第1の実施例に係る、繰り返しパターン計数処理を示すフローチャート図である。
【図8】第1の実施例に係る、特定の時系列データに対する特定の時系列パターンの繰り返し回数の数え上げ処理を示すフローチャート図である。
【図9】第1の実施例に係る、本発明における出現回数計数処理を示すフローチャート図である。
【図10】第3の実施例のシステム構成例を示す図である。
【図11】第3の実施例に係る、ユーザインタフェース例を示す図である。
【図12】第3の実施例に係る、ユーザ操作とシステム動作の関連を示した図である。
【図13】第3の実施例に係る、特定の時系列データに対する特定の時系列パターンの繰り返し回数の数え上げ処理の変形例を示すフローチャート図である。
【図14】第1の実施例に係る、時系列データ読み出し処理と記憶装置から読み出される時系列データの関係示すイメージ図である。
【発明を実施するための形態】
【0019】
以下、図面を参照して本発明の実施の形態を説明する。
【0020】
はじめに、種々の実施の形態において利用するデータの構成を説明する。データベースはレコードの集合からなり、レコードは事象(アイテム)の組合せ(アイテムセット)と、その事象の組合せが属する識別子(時系列データID)と、タイムスタンプ又は順序関係を示す識別子の組からなる。同一の時系列データIDを持つ1以上のレコードを、タイムスタンプ又は順序関係を示す識別子の順に配置したアイテムセットのリストの組で表現したデータを時系列データと呼ぶ。ここで、アイテムは離散値である。アイテムが連続値の場合、範囲分割などによって区分けし、各区分けに特定の離散値を割り当てることにより、連続値を離散値に対応付けることが可能である。また、離散値をグループに分類し、各グループを特定の離散値に対応付けることにより、アイテムに含まれない離散値に対応付けることも可能である。
【0021】
例えば、クレジットカードの利用データの場合の一例を表1と表2に示す。表1は表形式の表現であり、クレジットカードの利用データの場合、1レコードは、ある顧客の一回の利用を意味し、時系列データIDは「カードID」、タイムスタンプは「利用日」、事象は「利用内容」となる。また、表2は時系列データ形式の表現であり、1時系列データは、ある顧客の長期間に渡る利用の履歴(利用履歴)を意味し、事象のリストは、利用した順に並べられた利用内容となる。
【0022】
時系列パターンはアイテムセットの重複順列であり、1以上のn個のアイテムセット(IS1)、・・・、(ISn)から構成される時系列パターンは<(IS1)・・・(ISn)>と表現される。ある時系列パターンが1つの時系列データ中に現れる回数である繰り返し回数と呼ぶ。ある時系列パターンは、該時系列パターンが所定の繰り返し回数以上現れる時系列データの数である出現頻度と、該時系列データにおける繰り返し回数の統計値を評価値として持つ。ここで、時系列データの数は、異なる時系列データIDの種類数と等しい。
【0023】
表1、2に示したデータの例では、時系列データ数は3であり、例えば、時系列パターン<(店舗A)(店舗B)>のカードIDがcard01のデータにおける繰り返し回数は2である。また、例えば、時系列パターン<(店舗A)(店舗B)>は,カードIDがcard01で繰り返し回数が2,card02で1,card03で3であることから,所定の繰り返し回数を2以上と設定した場合の出現頻度は2であり、card01とcard03が該当する。また,繰り返し回数の統計値は平均2.5、最大3、最小2である。
【0024】
【表1】
【0025】
【表2】
【実施例1】
【0026】
図1は、第1の実施例のデータ解析システムの一構成例を示す図である。このシステムは、処理部であるプロセッサ101と、記憶部を構成するメモリ102と記憶装置103を有する。プロセッサ101とメモリ102はコンピュータ100を構成し、解析対象のデータは記憶装置103に格納されている。本実施例の時系列パターン抽出プログラムはメモリ102に格納されており、プロセッサ101によって実行されることによって、図4に示す処理が実行される。
【0027】
メモリ102には、図1に示すように、実行プログラム106に加え、設定値情報107〜チェックポイント情報111が記憶される。設定値情報107は、解析対象データと繰り返し回数の最小値と出現頻度の最小値と解析対象データの処理単位の設定値をデータあるいはファイルなどの形式で保持する。時系列データ情報108は、記憶装置103から読み出した時系列データについて時系列データIDと時系列データを、例えば、card01、<(店舗A)(店舗C)(店舗A)(店舗B、高額決済)(店舗C)>のように、表形式あるいはリスト形式などで保持する。
【0028】
アイテム情報109は、解析対象のデータに現れる各アイテムについて、例えば(店舗A、card01、3、0)のように、アイテムと時系列データIDと時系列データにおける繰り返し回数と探索する時系列パターンの数え上げに利用するための繰り返し回数(カウント値と呼ぶ)との組を表形式あるいはリスト形式などで保持する。探索時系列パターン情報110は、探索する時系列パターンについて、例えば、(<(店舗A)(店舗B、高額決済)>、card01、1、0)のように、探索時系列パターンと時系列データIDと数え上げ済みの繰り返し回数と数え上げ済みの時系列パターンのパターン位置との組を表形式あるいはリスト形式などで保持する。
【0029】
また、メモリ102は、繰り返し回数の数え上げを行う時系列データの先頭位置をチェックポイント情報111として保持する。このチェックポイントについては後述する。更に、コンピュータ100には、キーボードやマウスなどを備える入力装置104、及びディスプレイやプリンタなどからなる出力装置105が接続されている。
【0030】
図2は、本実施例のユーザインタフェースの一例を示している。このユーザインタフェース200は、解析対象のデータを指定する解析データ指定部201、解析対象データの処理単位を指定するチェックポイント指定部202、抽出する時系列パターンの繰り返し回数の最小値(最小繰り返し回数)を指定する最小繰り返し回数入力部203と出現頻度の最小値(最小出現頻度)を指定する最小出現頻度入力部204、処理の実行を指令する実行ボタン205、抽出された時系列パターンとその評価値とを表示する結果表示部206からなる。
【0031】
ユーザは解析対象データを解析データ指定部201で指定し、処理単位をチェックポイント指定部202に、抽出する時系列パターンの繰り返し回数の最小値を最小繰り返し回数入力部203に、抽出する時系列パターンの出現頻度の最小値を最小出現頻度入力部204に、それぞれ入力する。そして、実行ボタン205によって、時系列パターン抽出処理を開始する。
【0032】
抽出された時系列パターンは、時系列パターンを構成するアイテムセットのリストと、時系列パターンの評価値である繰り返し回数の統計値と出現頻度とが結果表示部206に表示される。なお、結果表示部206では表形式を用いて時系列パターンを表示したが、時系列パターンを構成するアイテムセットをノードとする遷移図によって表示しても構わない。
【0033】
また、解析データ指定部201とチェックポイント指定部202と最小繰り返し回数入力部203と最小出現頻度入力部204とが入力装置104に、結果表示部206が出力装置105に対応している。なお、タッチパネルとして機能するディスプレイ等を用いることにより、この入力装置104と出力装置105を一体化構成として形成することができることは言うまでもない。
【0034】
図3は、本実施例の時系列パターン抽出処理におけるユーザによる操作とシステムによる操作のフローの一例を示した図である。
【0035】
はじめに、ユーザは入力装置104において、解析対象のデータを指定、解析対象データの処理単位を入力、抽出する時系列パターンの最小繰り返し回数と最小出現頻度を入力する(301)。次に、実行を指示する(302)ことによって、時系列パターン抽出処理を開始する。
【0036】
データ解析システムは実行指示と同時に解析データ、データの処理単位、最小繰り返し回数、最小出現頻度を取得してメモリ102に格納し、メモリ102に格納された実行プログラムをプロセッサ101で実行する(303)。実行プログラムは、記憶装置103からの時系列データの読み出し、繰り返し回数の計数処理、出現頻度の計数処理によって、頻出繰り返し時系列パターンを抽出する(304)。頻出繰り返し時系列パターンの抽出処理手順の詳細は後述する。最後に、抽出された時系列パターンを出力装置106に出力する(305)。ユーザは出力装置106に出力された時系列パターンをチェックすること(306)によって、時系列パターン抽出処理を終了する。
【0037】
図4は、本実施例における時系列パターン抽出処理の全体処理手順を説明するフローチャートである。
【0038】
はじめにユーザは、入力処理(301)に対応し、解析対象の解析データ、解析データの処理単位、最小繰り返し回数、最小出現頻度を入力装置104に入力する(401)。プロセッサ101は、入力された解析対象データ、解析処理単位、最小繰り返し回数、最小出現頻度をメモリ102に保持する。メモリ102では、解析対象のデータをデータベース名やファイル名として、データの処理単位と最小繰り返し回数と最小出現頻度を数値として、設定値情報107に保持し、チェックポイント情報111にデータ位置の先頭を示す0を設定する(401)。
【0039】
次に、プロセッサ101は、実行プログラムの処理(304)に対応して、メモリ102に格納された実行プログラム106を実行し、頻出繰り返しアイテムの抽出処理402、探索する候補となる時系列パターンの設定403、記憶装置103からの時系列データの読み出し処理404、繰り返しパターン計数処理405、出現頻度の計数処理406によって頻出繰り返し時系列パターンを抽出する。また、抽出された時系列パターンを出力装置105に出力する(409)。
【0040】
図4の頻出繰り返しアイテム抽出処理402は、記憶装置103から時系列データを読み出し、時系列データ毎の各アイテムの繰り返し回数の数え上げ、出現頻度の数え上げを行うことによって、最小繰り返し回数と最小出現頻度の条件を共に満たす全てのアイテムを抽出する。
【0041】
図5は、図4における頻出繰り返しアイテム抽出処理402の手順を詳細に説明するフローチャートである。はじめにアイテム情報109を初期化し、空にする(501)。アイテム情報109は探索するアイテムについて、アイテム、時系列データID、この時系列データIDの時系列データにおける繰り返し回数、カウント値の組を表形式あるいはリストで保持する。次に、記憶装置103から1つの時系列データを読み出し、時系列データ情報109に時系列データIDと時系列データを保持する(502)。次に、該時系列データに現れる各アイテムの繰り返し回数を数え上げ(503)、最小繰り返し回数以上となるアイテムについて、アイテム、該時系列データの時系列データID、該アイテムの該時系列データIDの時系列データにおける繰り返し回数、カウント値の初期値である0の組をアイテム情報に登録する(504)。全ての時系列データについて同様の処理を繰り返す(505)。
【0042】
全ての時系列データに対する処理が終了した時点で、アイテム情報109に登録された各アイテムについて、アイテム情報109に登録されている時系列データIDの数(出現頻度)を数え上げ(506)、該出現頻度が最小出現頻度未満となるアイテムのアイテムと時系列IDと繰り返し回数とカウント値の組をアイテム情報から削除する(507)。
【0043】
図5で説明した頻出繰り返しアイテム抽出処理402が終了した時点で、最小繰り返し回数と最小出現頻度を共に満たす全てのアイテムについて、アイテムと時系列データIDと該時系列データにおける繰り返し回数とカウント値の初期値の組がメモリ102のアイテム情報109に格納される。ここで、繰り返し回数の数え上げが終了した時系列データIDについては、時系列データ情報108に時系列データを保持しておく必要はなく、時系列データIDのみ保持し、時系列データは削除しても構わない。
【0044】
図4に戻り、次に候補となる探索時系列パターンが設定(403)される。該候補となる探索時系列パターンは、2つ以上のアイテムから構成され、各時系列データにおける繰り返し回数と出現頻度が未知の時系列パターンである。探索時系列パターン情報110に時系列パターン、時系列データID、数え上げ済みの繰り返し回数の初期値、数え上げ済みの時系列パターンの位置の初期値の組が保持される。ここで、探索時系列パターン情報110は、探索する時系列パターンの各時系列データにおける繰り返し回数を数え上げるために利用される。なお、数え上げ済みの繰り返し回数の初期値と数え上げ済みの時系列パターンのパターン位置の初期値は共に0が設定される。
【0045】
図4の時系列データ読み出し処理404は、記憶装置103から時系列データを読み出し、読み出した時系列データをメモリ102の時系列データ情報108に保持する。
【0046】
図6は、図4における時系列データ読み出し処理404の手順を詳細に説明するフローチャートである。はじめに、メモリ102の時系列データ情報108の各時系列データIDの時系列データが保持されている場合、時系列データIDのみ保持し、時系列データを削除する(601)。次に、チェックポイント情報111から現在の時系列データのデータ位置を読み出し(603)、時系列データ情報108に格納された各時系列データIDについて、現データ位置から設定値情報106の解析処理単位の分だけ後ろのデータ位置までの時系列データを記憶装置103から読み出し(604)、アイテム情報109に登録されているアイテムを選び出し、時系列データ情報108に該時系列データIDの時系列データとして保持し(605)、該時系列データに現れる各アイテムについてアイテム情報109のカウント値に該アイテムが現れる回数を加算する(606)。全ての時系列データについて同様の処理を繰り返す(607)。全ての時系列データに対する処理が終了した時点で、時系列データ情報108に設定情報106のデータの処理単位分の各時系列データIDの時系列データが保持される。
【0047】
再び図4に戻り、次に繰り返しパターン計数処理405が行われる。繰り返しパターン計数処理405は、メモリ102の時系列データ情報108、アイテム情報109、探索時系列パターン情報110を利用し、探索時系列パターン情報110に保持された時系列パターンの各時系列データにおける繰り返し回数を数え上げる。
【0048】
図7は、図4の1時系列データに対する繰り返しパターン計数処理405の手順を詳細に説明するフローチャートである。探索時系列パターン情報110に保持された各時系列パターンについて(701)、繰り返し回数の数え上げ処理を行い(702)、該探索時系列パターンの該時系列データにおける繰り返し回数を数え上げる。次に、該探索時系列パターンの該時系列データにおける繰り返し回数の上限値を算出する(703)。繰り返し回数の上限値は、該時系列データにおける数え上げ済みの繰り返し回数、該時系列パターンにおける数え上げ済みの位置、該探索時系列パターンを構成する各アイテムの該時系列データにおける繰り返し回数とカウント値から、次に示す式によって算出される。
数え上げ済みのパターン位置が時系列パターンの初期値の場合:
(繰り返し回数の上限値) = (数え上げ済み繰り返し回数) + min{アイテムaの
繰り返し回数 - アイテムaのカウント値}
ここで,aは探索時系列パターンを構成するアイテムである。
数え上げ済みのパターン位置が時系列パターンの初期値でない場合:
(繰り返し回数の上限値) = (数え上げ済み繰り返し回数) + min{アイテムaの
繰り返し回数 - アイテムaのカウント値} + 1
ここで,aは探索時系列パターンを構成するアイテムである。
【0049】
時系列パターンの繰り返し回数の厳密な値は、現在までに繰り返し回数の数え上げ処理を完了した時系列データにおける繰り返し回数と、繰り返し回数の数え上げ処理が未処理の時系列データにおける繰り返し回数の和からなる。探索時系列パターンが数え上げ処理済みの時系列データと未処理の時系列データに跨る場合には、前述の和に1を加算する必要がある。繰り返し回数の数え上げが未処理の時系列データにおける探索時系列パターンの繰り返し回数の厳密な値は数え上げ処理を完了するまで未知である。
【0050】
しかし、時系列パターンの繰り返し回数には、ある時系列パターンの繰り返し回数は該時系列パターンを構成する各アイテムの繰り返し回数以上になることはないという性質がある。したがって、該未処理の時系列データにおける探索時系列パターンの繰り返し回数は該未処理の時系列データにおける該探索時系列パターンを構成するアイテムの繰り返し回数の最小値より高い値にはなり得ない。数1は上記の時系列パターンの繰り返し回数の性質を利用して、時系列データにおける繰り返し回数の上限値を、時系列データにおける数え上げ済みの繰り返し回数、数え上げ済みの位置、探索時系列パターンを構成する各アイテムの時系列データにおける繰り返し回数とカウント値から算出する数式である。
【0051】
数1によって算出された値が最小繰り返し回数を満たさない場合、該探索時系列パターンについて該時系列データIDの未処理の時系列データを含めた末尾まで数え上げを行ったとしても、該探索時系列パターンは該時系列データにおいては最小繰り返し回数を満たすことがないことが分かるため、探索時系列パターン情報から該探索時系列パターンの該時系列データに対応する情報を削除し(705)、以降の該時系列データにおける該探索時系列パターンの数え上げ処理は省略する。
【0052】
図8は、図7の1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理702の手順を詳細に説明するフローチャートである。
【0053】
はじめに探索する時系列パターンの処理対象の時系列データIDにおける繰り返し回数数え上げ済みパターン位置を取得し、該取得したパターン位置が初期値でない場合には1つ後ろを現パターン位置に設定し,初期値の場合には現パターン位置に先頭のパターン位置を設定する(801)。繰り返し回数数え上げを開始する該時系列データのデータ位置を該時系列データの先頭に設定する(802)。以降、現データ位置のアイテムセットから順に(803)、該探索時系列パターンの現パターン位置のアイテムセットを含むデータ位置を探す(804)。
【0054】
該時系列データの現データ位置のアイテムセットが該探索時系列パターンの現パターン位置のアイテムセットを含まない場合、現データ位置が該時系列データの末尾かどうかを調べ(809)、末尾でない場合には、現データ位置を1つ後ろにずらし、該時系列データの現データ位置のアイテムセットが該時系列パターンの現パターン位置のアイテムセットを含むか調べる処理(804)以降を繰り返す。末尾の場合には、処理を終了する。
【0055】
また、該時系列データの現データ位置のアイテムセットが該探索時系列パターンの現パターン位置のアイテムセットを含む場合、現パターン位置が該探索時系列パターンの末尾かどうかを調べる(805)。末尾の場合には、探索時系列パターン情報110の数え上げ済み繰り返し回数の値を1増加し(806)、数え上げ済みの時系列パターンのパターン位置に先頭のパターン位置を設定する(807)。末尾でない場合には、探索時系列パターン情報110の数え上げ済みの時系列パターンのパターン位置に現パターン位置を設定する(808)。現データ位置が該時系列データの末尾かどうかを調べ(809)、末尾でない場合には、現データ位置を1つ後ろにずらし(810)、該時系列データの現データ位置のアイテムセットが該時系列パターンの現パターン位置のアイテムセットを含むかを調べる処理(804)に戻る。末尾まで処理が完了した時点で、探索時系列パターン情報110の該時系列データIDの数え上げ済み時系列パターン位置に現パターン位置を設定し(811)、終了する。
【0056】
再び図4に戻り、次に出現頻度計数処理406が行われる。出現頻度計数処理404は探索時系列パターンの出現回数を数え上げる。
【0057】
図9は、この出現頻度計数処理404の手順を詳細に説明するフローチャートである。メモリ102の探索時系列パターン情報110に登録された各探索時系列パターンについて(901)、該探索時系列パターンの時系列データIDの種類の数を数え上げ(902)、設定値情報107の最小出現回数未満となる探索時系列パターンを探索時系列パターン情報110から削除する(904)。探索時系列パターン情報に登録された全探索時系列パターンに対する同様の処理が終了した時点で、探索時系列パターン情報110に最小繰り返し回数と最小出現頻度の条件を共に満たす可能性のある探索時系列パターンのみが登録される。
【0058】
再び図4に戻り、次に、探索時系列パターン情報110に含まれない時系列データIDを時系列データ情報から削除する(407)。
【0059】
以上の処理を全時系列データの末尾まで終了した時点で、探索時系列パターン情報110に登録されている探索時系列パターンから抽出された時系列パターンとして繰り返し回数の統計値と出現頻度の統計値と共に出力する(409)。探索時系列パターン情報110には、各時系列パターンの各時系列データにおける繰り返し回数の厳密な値が格納されているため、繰り返し回数に関する統計値の算出が可能であり、各時系列パターンの出現頻度と全時系列データ数が既知
のため、出現頻度の統計値の算出が可能である。
【0060】
なお、図1の出力装置105の図2の結果表示部206には、繰り返し回数の統計値として平均値と最大値と最小値、出現頻度の統計値として頻度と全時系列データ数に対する割合を一例として示した。
【0061】
図14は、本実施例の図4のフローチャートにおける、時系列データ読み出し処理404、繰り返しパターン計数処理405、出現頻度計数処理406に対する記憶装置103から読み出される時系列データのチェックポイントによる処理単位のイメージ図である。
【0062】
1時系列データを一本の直線で示しており、1回目の時系列データ読み出し処理で、はじめにデータ1の先頭から最初のチェックポイントまでの時系列データが読み出される。該読み出された時系列データに対して、繰り返しパターン計数処理が行われる。データ1の繰り返しパターン計数処理が終了した時点で、次の時系列データであるデータ2の先頭から最初のチェックポイントまでの時系列データが読み出され、繰り返しパターン計数処理が行われる。すべての時系列データに対して先頭から最初のチェックポイントまでの時系列データ読み出し処理と繰り返しパターン計数処理が終了した時点で、出現頻度計数処理が行われる。
【0063】
一回目の時系列データ読み出し処理では、各時系列データについて先頭から最初のチェックポイントまでの時系列データが読み出される。出現頻度計数処理の結果が最小出現頻度以上である場合、最初のチェックポイントまでの繰り返しパターン計数処理における繰り返し回数の上限値が最小繰り返し回数以上であった時系列データについて、最初のチェックポイントから2番目のチェックポイントまでに対して、時系列データの読み出し処理、繰り返しパターン計数処理が行われ、すべての時系列データについて終了した時点で、出現頻度計数処理が行われる。
【0064】
出現頻度計数処理の結果が最小出現頻度以上である場合には、同様の処理が繰り返される。最後のチェックポイントまで終了した時点で、最小繰り返し回数以上となる時系列データにおける繰り返し回数、および、出現頻度を得ることができる。途中のチェックポイントまでの出現頻度計数処理の結果が最小出現頻度未満となる場合、その探索時系列パターンは最小出現頻度を満たさないことが分かるため、該途中のチェックポイント以降の時系列データについては処理を省略する。また、各時系列データについて、途中のチェックポイントまでの繰り返しパターン計数処理の結果の繰り返し回数の上限値が最小繰り返し回数未満となる場合、その探索時系列パターンは該時系列データにおいては最小繰り返し回数を満たさないことがわかるため、該途中のチェックポイント以降の時系列データについては処理を省略する。これらの結果、頻出繰り返し時系列パターンでない探索時系列パターンに対する処理を回避し、探索処理負荷を低減することが出来る。
【0065】
以上のように、本実施例によると、各時系列データにおける繰り返し回数の最小値と、全時系列データにおける出現頻度の最小値の条件を共に満たす時系列パターンを得ることが出来る。また、本実施例においては、解析処理の途中経過において繰り返し回数の上限値を算出すること、及び算出した繰り返し回数の上限値を用いて出現頻度を数え上げることにより、最小繰り返し回数を満たし得ない探索時系列パターンと最小出現回数を満たし得ない探索時系列パターンの繰り返し回数の数え上げ処理を途中で打ち切ることにより、繰り返し回数の数え上げ処理対象となる時系列データの範囲を限定し、解析処理負荷を低減することが可能となる。
【0066】
なお、以上で説明した実施例1では繰り返し回数、出現頻度を利用したが、繰り返し回数の各時系列データ長あるいは期間との商である繰り返し率、出現頻度の全時系列データ数との商である出現率(支持度)を利用することでも同様に解析処理を実施することが可能である。
【0067】
また,本実施例では時系列データの処理単位をチェックポイント指定部202に入力させたが,メモリ102の設定値情報107のチェックポイント情報に所定の値を予め設定しておくことによって,ユーザによる処理単位の入力を省略することも可能である。
【実施例2】
【0068】
次に、第2の実施例として、クレジットカードの利用データを例にとり、図1のデータ解析システムの実行プログラム106の処理と、メモリ102に格納される各種の情報を説明する。ここで、本実施例における解析対象のクレジットカードの利用データの一例を表3に示す。表3に明らかなように、時系列データ数20のデータが記憶装置103に格納されているものとする。また、入力装置104において、データの処理単位を5、最小繰り返し回数を3、最小出現頻度を5と入力されたとし、メモリ102の設定値情報107に格納されているとする。
【0069】
【表3】
【0070】
プロセッサ101はメモリ102に格納されている実行プログラム106を実行し、はじめに頻出繰り返しアイテム抽出処理402を行う。例えば、このアイテム抽出処理402により、card01の時系列データが記憶装置103から読み出され、各アイテムの繰り返し回数が数え上げられたとき、メモリ102のアイテム情報109に(店舗A、card01、3、0)、(店舗B、card01、4、0)、(店舗C、card01、3、0)、(店舗D、card01、1、0)、(店舗E、card01、1、0)、(高額決済、card01、3、0)が格納される。最小出現回数が3であることから、アイテム”店舗D”と”店舗E”がアイテム情報から削除され、メモリ102のアイテム情報109には(店舗A、card01、3、0)、(店舗B、card01、4、0)、(店舗C、card01、3、0)、(高額決済、card01、3、0)が保持される。
【0071】
ここで、探索時系列パターン設定処理403において、候補となる繰り返し回数が未知の探索時系列パターンとして、<(店舗A)(店舗B、高額決済)>と<(店舗C)(店舗A)>と<(店舗C)(店舗B)>が設定されたとする。
【0072】
次に、プロセッサ101は実行プログラム106の時系列データ読み出し処理404において、記憶装置103に格納された時系列データが読み出され、メモリ102の時系列データ情報108に処理単位毎に格納される。
【0073】
読み出された時系列データから頻出繰り返しアイテム以外を削除し、時系列データ情報108に格納すると共に、各アイテムの繰り返し回数が数え上げられ、アイテム情報109の繰り返し回数情報が更新される。例えば、card01の時系列データでは、最初の時系列データ読み出し処理では時系列データとして<(店舗A)(店舗C)(店舗A)(店舗B、高額決済)(店舗E)(店舗C)>が読み出され、頻出繰り返しアイテム以外が削除され、card01、<(店舗A)(店舗C)(店舗A)(店舗B、高額決済)(店舗C)>が時系列データ情報108に保持される。また、アイテム情報109のカウント値を(店舗A、card01、3、2)、(店舗B、card01、4、1)、(店舗C、card01、3、2)(高額決済、card01、3、1)と更新する。
【0074】
次に、繰り返しパターン計数処理405において、探索時系列パターンの各時系列データにおける繰り返し回数が数え上げられる。例えば、card01の時系列データについて説明する。まず、探索時系列パターン<(店舗A)(店舗B、高額決済)>が数え上げられる場合、メモリ102の探索時系列パターン情報110から、該探索パターンのcard01の情報として、数え上げ済みの繰り返し回数として0、数え上げ済みの時系列パターンのパターン位置として0が読み出される。
【0075】
その後、card01の時系列データについて、メモリ102の時系列データ情報108の先頭のデータ位置のアイテムセットから順に該探索パターンの1番目のパターン位置のアイテムセット(店舗A)が現れるデータ位置を探し、データ位置1番目に検出される。該探索パターンの1番目のデータ位置のアイテムセットは末尾でないため、探索パターン情報の数え上げ済み時系列パターンの位置を1に更新する。
【0076】
次に、該探索パターンの2番目のパターン位置のアイテムセット(店舗B、高額決済)が現れるデータ位置を該時系列データのデータ位置2番目以降で探し、データ位置4番目で検出される。該探索パターンの2番目のパターン位置のアイテムセットは末尾のため、探索パターン情報の数え上げ済み回数を1増加させ、時系列パターンのパターン位置を0に更新する。再び、該探索パターンの1番目のアイテムセット(店舗A)が現れるデータ位置を該時系列データのデータ位置5番目以降で探すが、該時系列パターンの末尾であるデータ位置5番目まで探しても検出されないため、探索時系列パターン情報110の時系列パターン<(店舗A)(店舗B、高額決済)>の時系列データIDがcard01の数え上げ済み時系列パターンのパターン位置を1に更新し、繰り返し回数の数え上げ処理を終了する。
【0077】
また、探索パターン<(店舗C)(店舗A)>が数え上げられる場合、メモリ102の探索時系列パターン情報110から、該探索パターンのcard01の情報として、数え上げ済みの繰り返し回数が0、数え上げ済みのパターン位置0が読み出される。その後、card01の時系列データについて、メモリ102の時系列データ情報108の先頭のデータ位置のアイテムセットから順に該探索パターンの1番目のパターン位置のアイテムセット(店舗C)が現れるデータ位置を探し、データ位置2番目に検出される。該探索パターンの1番目のパターン位置のアイテムセット(店舗C)は末尾でないため、現パターン位置を2に更新する(図8の808)。
【0078】
次に、該探索パターンの2番目のパターン位置のアイテムセット(店舗A)が現れるデータ位置を該時系列データのデータ位置3番目以降で探し、データ位置3番目で検出される。該探索パターンの2番目のパターン位置のアイテムセット(店舗A)は末尾のため、探索パターン情報の数え上げ済み回数を1増加させ(同806)、現パターンの位置を先頭に更新する(同807)。
【0079】
再び、該探索パターンの1番目のパターン位置のアイテムセット(店舗C)が現れるデータ位置を該時系列データのデータ位置3番目以降で探し、データ位置5番目で検出される。該探索パターンの1番目のパターン位置のアイテムセットは末尾でないため、現パターン位置を2に更新する。また再び、該探索パターンの2番目のパターン位置のアイテムセット(店舗A)が現れるデータ位置を該時系列データのデータ位置5番目以降で探そうとするが、該時系列パターンのデータ位置5番目が末尾のため(同809)、探索パターン情報110の数え上げ済み時系列パターンのパターン位置を2に設定し(同811)、繰り返し回数の数え上げ処理702を終了する。
【0080】
次に、図7のフローにおいて、繰り返し回数の上限値の算出703が行われる。例えば、card01における探索パターン<(店舗A)(店舗B、高額決済)>について、探索時系列パターン情報110には(<(店舗A)(店舗B、高額決済)>、card01、1、0)、アイテム情報109には(店舗A、card01、3、2)、(店舗B、card01、4、1)、(高額決済、card01、3、1)が保持されていることから、数1により上限値が2(=1+1)と算出される。
【0081】
該算出された上限値は最小繰り返し回数(本実施例では3)未満のため、該探索パターンが最小繰り返し回数以上となり得ないことが分かる。該探索パターンの情報を探索パターン情報110から削除することによって、プロセッサ010ではcard01の探索パターンの繰り返し回数数え上げ処理を打ち切り、2回目以降の時系列データ読み出し処理後の繰り返し数え上げ処理を省略する。
【0082】
また、探索パターン<(店舗C)(店舗A)>について、探索パターン情報には(<(店舗C)(店舗A)>、card01、1、1)、アイテム情報には(店舗A、card01、3、2)、(店舗C、card01、3、2)が保持されていることから、数1により上限値が3(=1+1+1)と算出される。該算出された上限値は最小繰り返し回数以上のため、該探索パターンが最小繰り返し回数以上の可能性があることから、2回目以降の時系列データ読み出し処理後の繰り返し数え上げ処理を省略することは出来ない。
【0083】
次に、図4の繰り返し時系列パターン抽出処理の出現頻度の計数処理406が行われる。プロセッサ101はメモリ102の探索時系列パターン情報110に格納された時系列パターンと時系列データIDから、各時系列パターンの時系列データIDの種類数を数え上げ、最小出現頻度未満となる時系列パターンの情報を探索パターン情報から削除する。例えば、探索パターン<(店舗C)(店舗B)>について、探索時系列パターン情報110には(<(店舗C)(店舗B)>、card01、1、1)、(<(店舗C)(店舗B)>、card05、2、1)、(<(店舗C)(店舗B)>、card08、2、0)が格納されているとする。該探索パターンの出現頻度は3であり、最小出現頻度(本実施例においては5)を満たさないことが分かる。この場合、プロセッサ101は探索パターン情報110から該探索パターンを含む情報を削除する。探索パターン情報110から削除された時系列パターンは、2回目以降の時系列データ読み出し処理後の繰り返し数え上げ処理を省略できる。
【0084】
出現頻度計数処理406の次に、時系列データ情報108の更新407が行われる。繰り返し回数数え上げ処理を行う必要のある時系列データIDは探索時系列パターン情報110に保持されている。探索時系列パターン情報110に保持されていない時系列データIDは繰り返し回数の数え上げ処理を行う必要がないため、2回目以降の時系列データ読み出し処理は不要である。探索時系列パターン情報110に保持されない時系列データIDがある場合、該時系列データIDを時系列データ情報108から削除する。例えば、card02、card04、card07が時系列データIDとして保持されていない場合、時系列データ情報108から削除する。
【0085】
以上の処理を各時系列データの末尾まで繰り返す。例えば、本実施例の2回目の時系列データ読み出し処理では、時系列データの順位位置6番目から10番目までが読み出され、card01について、<(店舗B)(店舗B、高額決済)(店舗A)(店舗C)(店舗B、高額決済)>が時系列データ情報108としてメモリ102に保持され、探索パターン<(店舗C)(店舗A)>を数え上げる場合、メモリ102の探索時系列パターン情報110から、該探索パターンのcard01の情報として、数え上げ済みの繰り返し回数が1、数え上げ済みの時系列パターンの位置が1が読み出される。その後、card01の時系列データについて、メモリ102の時系列データ情報108の先頭のアイテムセットから順に該探索パターンの2番目のアイテムセット(店舗A)が現れる順位位置を探す処理を開始する。
【0086】
以上詳述して本実施例の処理によって、最小繰り返し回数と最小出現頻度の条件を共に満たす時系列パターンを不要な繰り返し回数数え上げ処理を回避しつつ抽出することが出来る。
【0087】
本実施例の場合、例えば、card01における探索パターン<(店舗A)(店舗B、高額決済)>については2回目の時系列データ読み出し処理以降の繰り返し回数数え上げ処理を省略することができる。また、例えば、card02、card04、card07の時系列データは2回目以降の時系列データ読み出し処理を省略することができる。
【実施例3】
【0088】
次に、第3の実施例として、データ解析システムが、各時系列データに区切れが存在するデータを解析対象とする場合を説明する。1つの時系列データにおいて所定の句切れをまたがる時系列パターンは該時系列データに含まれないとしたい場合がある。例えば、人の行動パターンの分析において1日単位での行動パターンを考える場合、日付をまたがる行動パターンを数え上げてはならない。
【0089】
図10は、第3の実施例のシステム構成例を示す図である。このシステムは、図1のシステム構成のメモリ102に、解析対象データにおける時系列データの区切れの条件を条件式などの形式で区切れ条件1001として保持する。
【0090】
図11は、本実施例のユーザインタフェースの一例を示している。このユーザインタフェース1100は、図2のユーザインタフェース200に解析対象データにおける時系列データの区切れ条件を設定する区切れ条件設定部1101を加えた構成を取る。ユーザは解析対象データを解析データ指定部201で指定し、処理単位をチェックポイント指定部202に、抽出する時系列パターンの繰り返し回数の最小値を最小繰り返し回数入力部203に、抽出する時系列パターンの出現頻度の最小値を最小出現頻度入力部204に、時系列データの区切れ条件を区切れ条件設定部1101に、それぞれ入力する。実行ボタン205によって、時系列パターン抽出処理を開始する。抽出された時系列パターンは、時系列パターンを構成するアイテムセットのリストと、時系列パターンの評価値である繰り返し回数の統計値と出現頻度とが結果表示部206に表示される。
【0091】
図12は、本実施例の時系列パターン抽出処理におけるユーザによる操作とシステムによる操作のフローを示した図である。はじめに、ユーザは入力装置104において、解析対象のデータを指定、解析対象データの処理単位を入力、抽出する時系列パターンの最小繰り返し回数と最小出現頻度、および、時系列データの区切れ条件を設定部1101から入力する(1201)。以降の処理は、図3と同様である。
【0092】
解析対象の時系列データに区切れ条件が設定された場合の時系列パターン抽出の全体処理手順、頻出繰り返しアイテム抽出処理、候補とする探索時系列パターン設定処理、時系列データ読み出し処理、出現頻度計数処理は、前述の処理手順と同様である。この時系列データに区切れ条件が設定された場合の時系列パターン抽出処理では、繰り返しパターン計数処理における1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理が前述の処理手順と異なる。
【0093】
図13に1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理702の解析対象の時系列データに、区切れ条件が設定された場合の手順を詳細に説明するフローチャートを示す。処理の内容は、前述の図8における繰り返し回数数え上げのパターン位置を設定する処理801から時系列データの末尾まで処理したか調べる処理809までは同様である。現データ位置が該時系列データの末尾かどうかを調べ(809)、末尾でない場合には、現データ位置の直後がメモリ102の設定値情報107の区切れ条件1001を満たすかどうかを調べる(1301)。
【0094】
区切れ条件を満たす場合は現パターン位置を先頭のパターン位置に戻し(1302)、現データ位置を1つ後ろにずらし(810)、該時系列データの現データ位置のアイテムセットが該時系列パターンの現パターン位置のアイテムセットを含むか調べる処理(804)以降を繰り返す。区切れ条件を満たさない場合は現データ位置を1つ後ろにずらし(810)、該時系列データの現データ位置のアイテムセットが該時系列パターンの現パターン位置のアイテムセットを含むか調べる処理(804)以降を繰り返す。末尾の場合は前述と同様である。
【0095】
以上のように、本実施例によると、時系列パターンの区切れの条件を設定し、探索時系列パターンの繰り返し回数の数え上げ処理において、時系列データの句切れが存在する時点で、探索パターンの繰り返し回数を数え上げるパターン位置を先頭に戻すことによって、時系列パターンの句切れをまたがる場合の繰り返し回数の数え上げを回避することが出来る。これにより、時系列データに区切れを設定した場合にも時系列パターンを抽出することが出来る。
【実施例4】
【0096】
第4の実施例として、Webサイトのアクセスログデータを解析するデータ解析システムを説明する。すなわち、Webサイトのアクセスログデータを例にとり、上述したデータ解析システムにおける実行プログラム106において行われる、1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理702を説明する。Webアクセスログデータの場合、1レコードはあるユーザの一回のアクセスを意味し、時系列データIDはユーザID、タイムスタンプはアクセス日時、事象はアクセスしたページのURLとなる。また、Webサイトのアクセスログは一連のアクセスの単位を表わすセッション番号を持ち、同一のセッション番号を持つレコードは同一のセッションでのアクセスであるとする。
【0097】
例えば、表4のデータのuser01はセッション番号100、101、102の3つのセッションを持つ。セッション番号100では、最初にページAがアクセスされ、次にページBがアクセスされ、最後にページCがアクセスされたことを意味する。ここで、解析対象のアクセスログデータを表4に示すデータとし、記憶装置103に格納されているとする。また、入力装置104において、区切れ条件として“i番目のレコードのセッション番号≠(i+1)番目のレコードのセッション番号”が設定されたとし、メモリ102の設定情報に格納されているとする。
【0098】
【表4】
【0099】
1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理702として、user01の時系列データにおける探索パターン<(ページA)(ページB)>が数え上げられるとし、メモリ102の時系列データ情報108のuser01の時系列データにセッション番号とURLの組のリストとして(100、ページA)(100、ページB)(100、ページA)(101、ページA)(101、ページB)(101、ページD)(101、ページE)(101、ページD)(102、ページD)が保持されており、メモリ102の探索パターン情報110から、該探索パターンのuser01の情報として、数え上げ済み繰り返し回数が0、数え上げ済みの時系列パターンのパターン位置が0と読み出されたとする。本実施例では、探索パターンの先頭のパターン位置のアイテムセット(ページA)が含まれるデータ位置とメモリ102の時系列データ情報108の先頭のデータ位置から順に探索する(図13の803に対応)。
【0100】
はじめに、該探索パターンの先頭のパターン位置のアイテムセット(ページA)が該時系列データの先頭のデータ位置のアイテムセットに現れることが検出される。現パターン位置が該探索パターンの末尾でないため(同805のNo)、現パターン位置を次のパターン位置である2とする(同808)。
【0101】
次に、現データ位置が末尾であるか調べる(同809)が、現データ位置が末尾でないことから、現データ位置の直後が区切れであるかを調べる(同1301)。上述の通り、メモリ102の区切れ条件1001に句切れの条件としてセッション番号が異なること設定されているため、現データ位置のセッション番号と次のデータ位置のセッション番号を比較し、共に100と等しいセッション番号であるため、現データ位置を2とし(同810)、再び現パターン位置のアイテムセットが現データ位置に含まれるか調べる(同804)。本実施例の場合、現パターン位置が2のとき、現データ位置が2において現パターン位置のアイテムセット(ページB)が現データ位置に現れることが検出され、メモリ102の探索パターン情報110の数え上げ済み繰り返し回数を1に更新し(同806)、現パターン位置を先頭(同807)、現データ位置を3とする。
【0102】
次に、現パターン位置のアイテムセット(ページA)が現データ位置のアイテムセット(ページC)に含まれないため、現データ位置を次のデータ位置にずらそうとする。ここで、現データ位置のセッション番号が100、次のデータ位置のセッション番号が101であることから、区切れが存在することが検出され(同1301)、現データ位置を次のデータ位置にずらす前に、現パターン位置に先頭のパターン位置を設定する(同1302)。これよって、セッション番号100と101にまたがる時系列パターンの繰り返し回数の数え上げを回避することができる。以下、同様に繰り返し回数数え上げ処理が時系列データの末尾まで続行される。
【0103】
なお、本実施例では時系列データ情報にセッション番号とアイテムセットの組のリストを保持し、区切れの条件として条件式を設定したが、句切れの条件を所定の記号とし、時系列データの句切れに所定の記号を付加したデータを用いることでも同様に解析処理を実施することが可能である。例えば、表4のデータにおいて、セッション番号が異なる場合を区切れと設定し、句切れを表わす記号を“.”とした場合、表5の時系列データによって本実施例と同様に解析処理を実施することが可能となる。
【0104】
【表5】
【産業上の利用可能性】
【0105】
以上詳述した本発明は、データベース及びデータウェアハウスを対象としたデータ解析システム及び方法に関し、特にデータベースのレコードを解析してデータの出現順序の規則性を明らかにするデータマイニング技術として極めて有用である。
【符号の説明】
【0106】
100…コンピュータ
101…プロセッサ
102…メモリ
103…記憶装置
104…入力装置
105…出力装置
106…実行プログラム
107…設定値情報
108…時系列データ情報
109…アイテム情報
110…探索パターン情報
111…チェックポイント情報
1001…区切れ条件
1101…区切れ条件設定部
200…ユーザインタフェース
201…解析データ指定部
202…チェックポイント指定部
203…最小繰り返し回数入力部
204…最小出現頻度入力部
205…実行ボタン
206…結果表示部。
【技術分野】
【0001】
本発明は、データ解析システム及び方法に関し、特にデータベースに含まれるデータの出現順序の規則性を明らかにするデータマイニング技術に関する。
【背景技術】
【0002】
モバイル端末、ICカード、ICタグなどのデータ収集環境の普及により、時々刻々の人の行動や物の状態をデータとして獲得し、大量に蓄積することが可能となった。この大量に蓄積された人の行動や物の状態のデータを解析し、特徴的または典型的な行動パターンや状態パターンを抽出し、マーケティングやヘルスケアなどに応用したいというニーズがある。その解決手段として、大量に蓄積されたデータを解析し、その中に埋もれた有用な規則性やパターンを抽出するデータマイニングが知られている。特に、データの時間軸上の出現順序のパターンを解析する技術として時系列パターンマイニングがある。
【0003】
例えば、クレジットカードの利用データの時系列パターンマイニングを考えてみる。顧客が店舗でクレジットカードを利用した履歴がクレジットカードの利用データとして、利用日時、利用店舗、利用額が記録される。大量のクレジットカード利用データから、複数の顧客に共通して現れるパターンとして、順序を伴うパターンである時系列パターンを抽出することが出来る。「店舗Aで購買した顧客は、その後に店舗Bで高額の購買をする場合が多い」のような時系列パターンが抽出された場合、店舗Aと店舗Bに併買行動の関係があることがわかり、店舗の配置、販売戦略に役立てることが出来る。また、Webサイトのアクセスログからユーザの典型的なアクセスパターンを抽出ことが可能であり、抽出されたアクセスパターンに含まれないアクセスが起きていること、過去のデータでは抽出されなかったアクセスパターンが新たなデータで抽出されたことなどの判定により、異常なアクセスの検出に活用出来る。また、建設機械の稼働履歴と故障やメンテナンスの履歴から、故障が発生しやすい稼働状態パターンや通常の稼働パターンを抽出することが可能であり、故障を防ぐ稼働プランの設計や異常な稼働状態の検出に役立てることが出来る。
【0004】
大量のデータから時系列パターンを抽出する研究は、データマイニングの分野
で行われてきた。例えば、特許文献1、非特許文献1に記載の方法がある。特許文献1と非特許文献1の方法では、アイテム(データ項目、事象)の組合せとタイムスタンプ(時刻)又は出現順所を示す識別子からなるデータベースから、ユーザが予め設定した支持度(出現頻度の全データに対する割合を表す)の最小値以上となる時系列パターンを抽出する。時系列パターンはアイテムの組合せ(アイテムセット)の出現順序を含んだパターンであり、1以上のn個のアイテムセットからなる時系列パターンは、<(IS1)・・・(ISn)>で表現される。ここで、(IS1)、・・・、(ISn)はアイテムセットであり、アイテムセットは1以上のアイテムからなる。ある時系列パターンの支持度は、全時系列データの中でその時系列パターンを含む時系列データの割合である。最小支持度以上となる時系列パターンは頻出時系列パターンと呼ばれる。頻出時系列パターン抽出は、候補となる時系列パターン(候補時系列パターン)の作成とデータベースからのデータ読み出しによる時系列データ中に該候補時系列パターンが現れる頻度の数え上げと、支持度の最小値以上の頻度となる時系列パターンの選出によって行われる。
【0005】
時系列パターンマイニングの別の問題として、1つの時系列データにおいて繰り返される時系列パターン(繰り返し時系列パターン)を抽出する問題もある。例えば、クレジットカードの利用データの繰り返し時系列パターン抽出を考えてみる。長期間に渡って利用された1利用者の利用データから、複数回繰り返される利用パターンである時系列パターンを抽出することが出来る。「店舗Cで購買し、次に店舗Dで購買したとき、その後に店舗Eで購買することが多い」のような時系列パターンが抽出された場合、店舗Cと店舗Dと店舗Eを決まった順序で定期的に利用していることが分かり、広告戦略、販売戦略に役立てることや、定期的な利用パターンの傾向から利用者のタイプを分類するセグメンテーションに役立てることが出来る。
【0006】
繰り返し時系列パターンを抽出する研究はデータマイニングの分野、バイオインフォマティクスの分野で行われてきた。例えば、特許文献2、3に記載の方法がある。特許文献2に記載の方法では、一人の時系列データにおいて、所定の頻度以上繰り返される時系列パターンを抽出ことにより、定期的に行っているパターンを抽出出来る。また、特許文献3に記載の方法では、実際に繰り返される厳密な回数を数え上げず、統計的に繰り返されていると判断されたパターンを抽出する。特許文献2と異なり、繰り返されるパターンは意味の無い部分と考えられており、それらを除去することが特許文献3のようなバイオの分野での繰り返しパターン抽出の目的である。特許文献2では、繰り返されるパターンが意味のある部分と考えられており、それらを厳密な出現回数と共に見つけ出すことが目的である。
【先行技術文献】
【特許文献】
【0007】
【特許文献1】特開平8-263346号公報
【特許文献2】特開2001-229202号公報
【特許文献3】米国特許出願公開US2003/0068617
【非特許文献】
【0008】
【非特許文献1】R.Agrawal, R.Srikant, "Mining Sequential Patterns:Generalizations and Performance Improvements", in proceedings ofInternational Conference on Extending Database Technology, 1996
【発明の概要】
【発明が解決しようとする課題】
【0009】
実際の解析あるいは分析では常に全データを分析対象とする訳ではない。例えば、人の行動分析においては、たまたま行われた行動はノイズとして除去し、ある程度の回数以上繰り返された行動のみを分析対象とする場合がある。多くのユーザが定期的に行った行動を有意な行動パターンとして抽出したいというニーズもある。購買分析においては、定期的に繰り返して購買してくれる顧客の購買パターンを知り、そのパターンでの購買を促進することにより、定期的に繰り返し購買をする顧客を生み出すことに役立てることが出来る。
【0010】
このように、前述の特許文献1と非特許文献1、特許文献2と3はそれぞれ、多人数の時系列データにおいて複数の顧客に共通して現れる時系列パターンの抽出、一人の時系列データにおいて複数回繰り返される時系列パターンの抽出が可能である。しかし、この両者を共に考慮して時系列パターンを抽出することは考慮されていなかった。
【0011】
単純には、まず個々の顧客の時系列データで繰り返しパターンを抽出し、それらの中から所定の数以上の顧客で抽出されたパターンを抽出することによって、両者の条件を満たすパターンを抽出出来る。しかし、顧客毎に繰り返す購買パターンは異なるため、単純に組み合わせた方法では不要なパターンの探索処理を膨大な時系列データに対して行うことになり、膨大な不要な処理が発生するため、現実的には困難である。
【0012】
本発明の目的は、各時系列データにおいて所定の回数以上繰り返される時系列パターンであり、所定の数以上の時系列データにおいて該繰り返し回数の条件を満たす時系列パターンである頻出繰り返し時系列パターンを抽出するデータ解析システム及び方法を提供することである。
【0013】
本発明の他の目的は、チェックポイントの利用と繰り返し回数と出現回数の上限値の算出によって、探索処理量を低減するデータ解析システム及び方法を提供することである。
【課題を解決するための手段】
【0014】
上記の目的を達成するため、本発明においては、処理部と記憶部とを備えた計算機を用い、事象と,事象の属するIDと,事象間の順序関係を示す情報の組が複数格納されたデータを、同じIDを有する事象をその順序関係に従って並べた時系列データとし,1以上の事象を順方向に並べた重複順列を時系列パターンとし,所定の数以上の時系列データにおいて,各時系列データにおける所定の回数以上繰り返される時系列パターンである頻出繰り返し時系列パターンを抽出するため,繰り返し回数が未知の時系列パターンについて,各時系列データにおける繰り返し回数を数え上げるステップと,この繰り返し回数が所定の繰り返し回数以上となる時系列データの数を数え上げるステップと,この数え上げた時系列データの数が所定の数以上となる時系列パターンを抽出するステップとを処理部で実行するデータ解析システム及び方法を構成する。
【0015】
また、上記の目的を達成するため、本発明においては、処理部と記憶部とを備えた計算機を用い、事象と,事象の属するIDと,事象間の順序関係を示す情報の組が複数格納されたデータを,同じIDを有する事象をその順序関係に従って並べた時系列データとし,1以上の事象を順方向に並べた重複順列を時系列パターンとし,所定の数以上の時系列データにおいて,各時系列データにおける所定の回数以上繰り返される時系列パターンである頻出繰り返し時系列パターンを抽出するため,各時系列データに,所定の間隔でチェックポイントを設定する第1のステップと,各時系列データにおける繰り返し回数が未知の時系列パターンについて,各時系列データについてチェックポイントから次のチェックポイントまでの範囲で該時系列パターンが繰り返される回数を数え上げる第2のステップと,
該時系列データにおける該時系列パターンの繰り返し回数の上限値を,既に数え上げられたチェックポイントまででの繰り返し回数と,該チェックポイント以降に現れる各事象の繰り返し回数との和から算出する第3のステップと,該算出された上限値が所定の繰り返し回数以上となる時系列データの数を数え上げる第4のステップと,該時系列データの数が所定の数以上となる時系列パターンを抽出する第5のステップと,該抽出された時系列パターンについて前記第2から第5のステップを最後のチェックポイントまで繰り返す第6のステップを処理部で実行するデータ解析システム及び方法を構成する。
【発明の効果】
【0016】
本発明によると、個々の時系列データにおいて所定の回数以上繰り返される時系列パターンであって、かつ、所定の数以上の時系列データにおいて該繰り返し条件を満たす時系列パターンを抽出することが可能となる。
【0017】
また、本発明のデータの処理単位毎に各時系列データの繰り返し回数の数え上げ処理において繰り返し回数の上限値を算出し、所定の繰り返し回数未満となる場合に以降の繰り返し回数の数え上げを回避すること、出現頻度の数え上げをデータの処理単位毎に行うことによって解析処理量を低減することが可能となる。
【図面の簡単な説明】
【0018】
【図1】第1の実施例のシステム構成例を示す図である。
【図2】第1の実施例に係る、ユーザインタフェースの一例を示す図である。
【図3】第1の実施例に係る、ユーザ操作とシステム動作の関連を示したフロー図である。
【図4】第1の実施例に係る、頻出繰り返し時系列パターン抽出処理の概要を示すフローチャート図である。
【図5】第1の実施例に係る、頻出繰り返しアイテム抽出処理を示すフローチャート図である。
【図6】第1の実施例に係る、時系列データ読み出し処理を示すフローチャート図である。
【図7】第1の実施例に係る、繰り返しパターン計数処理を示すフローチャート図である。
【図8】第1の実施例に係る、特定の時系列データに対する特定の時系列パターンの繰り返し回数の数え上げ処理を示すフローチャート図である。
【図9】第1の実施例に係る、本発明における出現回数計数処理を示すフローチャート図である。
【図10】第3の実施例のシステム構成例を示す図である。
【図11】第3の実施例に係る、ユーザインタフェース例を示す図である。
【図12】第3の実施例に係る、ユーザ操作とシステム動作の関連を示した図である。
【図13】第3の実施例に係る、特定の時系列データに対する特定の時系列パターンの繰り返し回数の数え上げ処理の変形例を示すフローチャート図である。
【図14】第1の実施例に係る、時系列データ読み出し処理と記憶装置から読み出される時系列データの関係示すイメージ図である。
【発明を実施するための形態】
【0019】
以下、図面を参照して本発明の実施の形態を説明する。
【0020】
はじめに、種々の実施の形態において利用するデータの構成を説明する。データベースはレコードの集合からなり、レコードは事象(アイテム)の組合せ(アイテムセット)と、その事象の組合せが属する識別子(時系列データID)と、タイムスタンプ又は順序関係を示す識別子の組からなる。同一の時系列データIDを持つ1以上のレコードを、タイムスタンプ又は順序関係を示す識別子の順に配置したアイテムセットのリストの組で表現したデータを時系列データと呼ぶ。ここで、アイテムは離散値である。アイテムが連続値の場合、範囲分割などによって区分けし、各区分けに特定の離散値を割り当てることにより、連続値を離散値に対応付けることが可能である。また、離散値をグループに分類し、各グループを特定の離散値に対応付けることにより、アイテムに含まれない離散値に対応付けることも可能である。
【0021】
例えば、クレジットカードの利用データの場合の一例を表1と表2に示す。表1は表形式の表現であり、クレジットカードの利用データの場合、1レコードは、ある顧客の一回の利用を意味し、時系列データIDは「カードID」、タイムスタンプは「利用日」、事象は「利用内容」となる。また、表2は時系列データ形式の表現であり、1時系列データは、ある顧客の長期間に渡る利用の履歴(利用履歴)を意味し、事象のリストは、利用した順に並べられた利用内容となる。
【0022】
時系列パターンはアイテムセットの重複順列であり、1以上のn個のアイテムセット(IS1)、・・・、(ISn)から構成される時系列パターンは<(IS1)・・・(ISn)>と表現される。ある時系列パターンが1つの時系列データ中に現れる回数である繰り返し回数と呼ぶ。ある時系列パターンは、該時系列パターンが所定の繰り返し回数以上現れる時系列データの数である出現頻度と、該時系列データにおける繰り返し回数の統計値を評価値として持つ。ここで、時系列データの数は、異なる時系列データIDの種類数と等しい。
【0023】
表1、2に示したデータの例では、時系列データ数は3であり、例えば、時系列パターン<(店舗A)(店舗B)>のカードIDがcard01のデータにおける繰り返し回数は2である。また、例えば、時系列パターン<(店舗A)(店舗B)>は,カードIDがcard01で繰り返し回数が2,card02で1,card03で3であることから,所定の繰り返し回数を2以上と設定した場合の出現頻度は2であり、card01とcard03が該当する。また,繰り返し回数の統計値は平均2.5、最大3、最小2である。
【0024】
【表1】
【0025】
【表2】
【実施例1】
【0026】
図1は、第1の実施例のデータ解析システムの一構成例を示す図である。このシステムは、処理部であるプロセッサ101と、記憶部を構成するメモリ102と記憶装置103を有する。プロセッサ101とメモリ102はコンピュータ100を構成し、解析対象のデータは記憶装置103に格納されている。本実施例の時系列パターン抽出プログラムはメモリ102に格納されており、プロセッサ101によって実行されることによって、図4に示す処理が実行される。
【0027】
メモリ102には、図1に示すように、実行プログラム106に加え、設定値情報107〜チェックポイント情報111が記憶される。設定値情報107は、解析対象データと繰り返し回数の最小値と出現頻度の最小値と解析対象データの処理単位の設定値をデータあるいはファイルなどの形式で保持する。時系列データ情報108は、記憶装置103から読み出した時系列データについて時系列データIDと時系列データを、例えば、card01、<(店舗A)(店舗C)(店舗A)(店舗B、高額決済)(店舗C)>のように、表形式あるいはリスト形式などで保持する。
【0028】
アイテム情報109は、解析対象のデータに現れる各アイテムについて、例えば(店舗A、card01、3、0)のように、アイテムと時系列データIDと時系列データにおける繰り返し回数と探索する時系列パターンの数え上げに利用するための繰り返し回数(カウント値と呼ぶ)との組を表形式あるいはリスト形式などで保持する。探索時系列パターン情報110は、探索する時系列パターンについて、例えば、(<(店舗A)(店舗B、高額決済)>、card01、1、0)のように、探索時系列パターンと時系列データIDと数え上げ済みの繰り返し回数と数え上げ済みの時系列パターンのパターン位置との組を表形式あるいはリスト形式などで保持する。
【0029】
また、メモリ102は、繰り返し回数の数え上げを行う時系列データの先頭位置をチェックポイント情報111として保持する。このチェックポイントについては後述する。更に、コンピュータ100には、キーボードやマウスなどを備える入力装置104、及びディスプレイやプリンタなどからなる出力装置105が接続されている。
【0030】
図2は、本実施例のユーザインタフェースの一例を示している。このユーザインタフェース200は、解析対象のデータを指定する解析データ指定部201、解析対象データの処理単位を指定するチェックポイント指定部202、抽出する時系列パターンの繰り返し回数の最小値(最小繰り返し回数)を指定する最小繰り返し回数入力部203と出現頻度の最小値(最小出現頻度)を指定する最小出現頻度入力部204、処理の実行を指令する実行ボタン205、抽出された時系列パターンとその評価値とを表示する結果表示部206からなる。
【0031】
ユーザは解析対象データを解析データ指定部201で指定し、処理単位をチェックポイント指定部202に、抽出する時系列パターンの繰り返し回数の最小値を最小繰り返し回数入力部203に、抽出する時系列パターンの出現頻度の最小値を最小出現頻度入力部204に、それぞれ入力する。そして、実行ボタン205によって、時系列パターン抽出処理を開始する。
【0032】
抽出された時系列パターンは、時系列パターンを構成するアイテムセットのリストと、時系列パターンの評価値である繰り返し回数の統計値と出現頻度とが結果表示部206に表示される。なお、結果表示部206では表形式を用いて時系列パターンを表示したが、時系列パターンを構成するアイテムセットをノードとする遷移図によって表示しても構わない。
【0033】
また、解析データ指定部201とチェックポイント指定部202と最小繰り返し回数入力部203と最小出現頻度入力部204とが入力装置104に、結果表示部206が出力装置105に対応している。なお、タッチパネルとして機能するディスプレイ等を用いることにより、この入力装置104と出力装置105を一体化構成として形成することができることは言うまでもない。
【0034】
図3は、本実施例の時系列パターン抽出処理におけるユーザによる操作とシステムによる操作のフローの一例を示した図である。
【0035】
はじめに、ユーザは入力装置104において、解析対象のデータを指定、解析対象データの処理単位を入力、抽出する時系列パターンの最小繰り返し回数と最小出現頻度を入力する(301)。次に、実行を指示する(302)ことによって、時系列パターン抽出処理を開始する。
【0036】
データ解析システムは実行指示と同時に解析データ、データの処理単位、最小繰り返し回数、最小出現頻度を取得してメモリ102に格納し、メモリ102に格納された実行プログラムをプロセッサ101で実行する(303)。実行プログラムは、記憶装置103からの時系列データの読み出し、繰り返し回数の計数処理、出現頻度の計数処理によって、頻出繰り返し時系列パターンを抽出する(304)。頻出繰り返し時系列パターンの抽出処理手順の詳細は後述する。最後に、抽出された時系列パターンを出力装置106に出力する(305)。ユーザは出力装置106に出力された時系列パターンをチェックすること(306)によって、時系列パターン抽出処理を終了する。
【0037】
図4は、本実施例における時系列パターン抽出処理の全体処理手順を説明するフローチャートである。
【0038】
はじめにユーザは、入力処理(301)に対応し、解析対象の解析データ、解析データの処理単位、最小繰り返し回数、最小出現頻度を入力装置104に入力する(401)。プロセッサ101は、入力された解析対象データ、解析処理単位、最小繰り返し回数、最小出現頻度をメモリ102に保持する。メモリ102では、解析対象のデータをデータベース名やファイル名として、データの処理単位と最小繰り返し回数と最小出現頻度を数値として、設定値情報107に保持し、チェックポイント情報111にデータ位置の先頭を示す0を設定する(401)。
【0039】
次に、プロセッサ101は、実行プログラムの処理(304)に対応して、メモリ102に格納された実行プログラム106を実行し、頻出繰り返しアイテムの抽出処理402、探索する候補となる時系列パターンの設定403、記憶装置103からの時系列データの読み出し処理404、繰り返しパターン計数処理405、出現頻度の計数処理406によって頻出繰り返し時系列パターンを抽出する。また、抽出された時系列パターンを出力装置105に出力する(409)。
【0040】
図4の頻出繰り返しアイテム抽出処理402は、記憶装置103から時系列データを読み出し、時系列データ毎の各アイテムの繰り返し回数の数え上げ、出現頻度の数え上げを行うことによって、最小繰り返し回数と最小出現頻度の条件を共に満たす全てのアイテムを抽出する。
【0041】
図5は、図4における頻出繰り返しアイテム抽出処理402の手順を詳細に説明するフローチャートである。はじめにアイテム情報109を初期化し、空にする(501)。アイテム情報109は探索するアイテムについて、アイテム、時系列データID、この時系列データIDの時系列データにおける繰り返し回数、カウント値の組を表形式あるいはリストで保持する。次に、記憶装置103から1つの時系列データを読み出し、時系列データ情報109に時系列データIDと時系列データを保持する(502)。次に、該時系列データに現れる各アイテムの繰り返し回数を数え上げ(503)、最小繰り返し回数以上となるアイテムについて、アイテム、該時系列データの時系列データID、該アイテムの該時系列データIDの時系列データにおける繰り返し回数、カウント値の初期値である0の組をアイテム情報に登録する(504)。全ての時系列データについて同様の処理を繰り返す(505)。
【0042】
全ての時系列データに対する処理が終了した時点で、アイテム情報109に登録された各アイテムについて、アイテム情報109に登録されている時系列データIDの数(出現頻度)を数え上げ(506)、該出現頻度が最小出現頻度未満となるアイテムのアイテムと時系列IDと繰り返し回数とカウント値の組をアイテム情報から削除する(507)。
【0043】
図5で説明した頻出繰り返しアイテム抽出処理402が終了した時点で、最小繰り返し回数と最小出現頻度を共に満たす全てのアイテムについて、アイテムと時系列データIDと該時系列データにおける繰り返し回数とカウント値の初期値の組がメモリ102のアイテム情報109に格納される。ここで、繰り返し回数の数え上げが終了した時系列データIDについては、時系列データ情報108に時系列データを保持しておく必要はなく、時系列データIDのみ保持し、時系列データは削除しても構わない。
【0044】
図4に戻り、次に候補となる探索時系列パターンが設定(403)される。該候補となる探索時系列パターンは、2つ以上のアイテムから構成され、各時系列データにおける繰り返し回数と出現頻度が未知の時系列パターンである。探索時系列パターン情報110に時系列パターン、時系列データID、数え上げ済みの繰り返し回数の初期値、数え上げ済みの時系列パターンの位置の初期値の組が保持される。ここで、探索時系列パターン情報110は、探索する時系列パターンの各時系列データにおける繰り返し回数を数え上げるために利用される。なお、数え上げ済みの繰り返し回数の初期値と数え上げ済みの時系列パターンのパターン位置の初期値は共に0が設定される。
【0045】
図4の時系列データ読み出し処理404は、記憶装置103から時系列データを読み出し、読み出した時系列データをメモリ102の時系列データ情報108に保持する。
【0046】
図6は、図4における時系列データ読み出し処理404の手順を詳細に説明するフローチャートである。はじめに、メモリ102の時系列データ情報108の各時系列データIDの時系列データが保持されている場合、時系列データIDのみ保持し、時系列データを削除する(601)。次に、チェックポイント情報111から現在の時系列データのデータ位置を読み出し(603)、時系列データ情報108に格納された各時系列データIDについて、現データ位置から設定値情報106の解析処理単位の分だけ後ろのデータ位置までの時系列データを記憶装置103から読み出し(604)、アイテム情報109に登録されているアイテムを選び出し、時系列データ情報108に該時系列データIDの時系列データとして保持し(605)、該時系列データに現れる各アイテムについてアイテム情報109のカウント値に該アイテムが現れる回数を加算する(606)。全ての時系列データについて同様の処理を繰り返す(607)。全ての時系列データに対する処理が終了した時点で、時系列データ情報108に設定情報106のデータの処理単位分の各時系列データIDの時系列データが保持される。
【0047】
再び図4に戻り、次に繰り返しパターン計数処理405が行われる。繰り返しパターン計数処理405は、メモリ102の時系列データ情報108、アイテム情報109、探索時系列パターン情報110を利用し、探索時系列パターン情報110に保持された時系列パターンの各時系列データにおける繰り返し回数を数え上げる。
【0048】
図7は、図4の1時系列データに対する繰り返しパターン計数処理405の手順を詳細に説明するフローチャートである。探索時系列パターン情報110に保持された各時系列パターンについて(701)、繰り返し回数の数え上げ処理を行い(702)、該探索時系列パターンの該時系列データにおける繰り返し回数を数え上げる。次に、該探索時系列パターンの該時系列データにおける繰り返し回数の上限値を算出する(703)。繰り返し回数の上限値は、該時系列データにおける数え上げ済みの繰り返し回数、該時系列パターンにおける数え上げ済みの位置、該探索時系列パターンを構成する各アイテムの該時系列データにおける繰り返し回数とカウント値から、次に示す式によって算出される。
数え上げ済みのパターン位置が時系列パターンの初期値の場合:
(繰り返し回数の上限値) = (数え上げ済み繰り返し回数) + min{アイテムaの
繰り返し回数 - アイテムaのカウント値}
ここで,aは探索時系列パターンを構成するアイテムである。
数え上げ済みのパターン位置が時系列パターンの初期値でない場合:
(繰り返し回数の上限値) = (数え上げ済み繰り返し回数) + min{アイテムaの
繰り返し回数 - アイテムaのカウント値} + 1
ここで,aは探索時系列パターンを構成するアイテムである。
【0049】
時系列パターンの繰り返し回数の厳密な値は、現在までに繰り返し回数の数え上げ処理を完了した時系列データにおける繰り返し回数と、繰り返し回数の数え上げ処理が未処理の時系列データにおける繰り返し回数の和からなる。探索時系列パターンが数え上げ処理済みの時系列データと未処理の時系列データに跨る場合には、前述の和に1を加算する必要がある。繰り返し回数の数え上げが未処理の時系列データにおける探索時系列パターンの繰り返し回数の厳密な値は数え上げ処理を完了するまで未知である。
【0050】
しかし、時系列パターンの繰り返し回数には、ある時系列パターンの繰り返し回数は該時系列パターンを構成する各アイテムの繰り返し回数以上になることはないという性質がある。したがって、該未処理の時系列データにおける探索時系列パターンの繰り返し回数は該未処理の時系列データにおける該探索時系列パターンを構成するアイテムの繰り返し回数の最小値より高い値にはなり得ない。数1は上記の時系列パターンの繰り返し回数の性質を利用して、時系列データにおける繰り返し回数の上限値を、時系列データにおける数え上げ済みの繰り返し回数、数え上げ済みの位置、探索時系列パターンを構成する各アイテムの時系列データにおける繰り返し回数とカウント値から算出する数式である。
【0051】
数1によって算出された値が最小繰り返し回数を満たさない場合、該探索時系列パターンについて該時系列データIDの未処理の時系列データを含めた末尾まで数え上げを行ったとしても、該探索時系列パターンは該時系列データにおいては最小繰り返し回数を満たすことがないことが分かるため、探索時系列パターン情報から該探索時系列パターンの該時系列データに対応する情報を削除し(705)、以降の該時系列データにおける該探索時系列パターンの数え上げ処理は省略する。
【0052】
図8は、図7の1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理702の手順を詳細に説明するフローチャートである。
【0053】
はじめに探索する時系列パターンの処理対象の時系列データIDにおける繰り返し回数数え上げ済みパターン位置を取得し、該取得したパターン位置が初期値でない場合には1つ後ろを現パターン位置に設定し,初期値の場合には現パターン位置に先頭のパターン位置を設定する(801)。繰り返し回数数え上げを開始する該時系列データのデータ位置を該時系列データの先頭に設定する(802)。以降、現データ位置のアイテムセットから順に(803)、該探索時系列パターンの現パターン位置のアイテムセットを含むデータ位置を探す(804)。
【0054】
該時系列データの現データ位置のアイテムセットが該探索時系列パターンの現パターン位置のアイテムセットを含まない場合、現データ位置が該時系列データの末尾かどうかを調べ(809)、末尾でない場合には、現データ位置を1つ後ろにずらし、該時系列データの現データ位置のアイテムセットが該時系列パターンの現パターン位置のアイテムセットを含むか調べる処理(804)以降を繰り返す。末尾の場合には、処理を終了する。
【0055】
また、該時系列データの現データ位置のアイテムセットが該探索時系列パターンの現パターン位置のアイテムセットを含む場合、現パターン位置が該探索時系列パターンの末尾かどうかを調べる(805)。末尾の場合には、探索時系列パターン情報110の数え上げ済み繰り返し回数の値を1増加し(806)、数え上げ済みの時系列パターンのパターン位置に先頭のパターン位置を設定する(807)。末尾でない場合には、探索時系列パターン情報110の数え上げ済みの時系列パターンのパターン位置に現パターン位置を設定する(808)。現データ位置が該時系列データの末尾かどうかを調べ(809)、末尾でない場合には、現データ位置を1つ後ろにずらし(810)、該時系列データの現データ位置のアイテムセットが該時系列パターンの現パターン位置のアイテムセットを含むかを調べる処理(804)に戻る。末尾まで処理が完了した時点で、探索時系列パターン情報110の該時系列データIDの数え上げ済み時系列パターン位置に現パターン位置を設定し(811)、終了する。
【0056】
再び図4に戻り、次に出現頻度計数処理406が行われる。出現頻度計数処理404は探索時系列パターンの出現回数を数え上げる。
【0057】
図9は、この出現頻度計数処理404の手順を詳細に説明するフローチャートである。メモリ102の探索時系列パターン情報110に登録された各探索時系列パターンについて(901)、該探索時系列パターンの時系列データIDの種類の数を数え上げ(902)、設定値情報107の最小出現回数未満となる探索時系列パターンを探索時系列パターン情報110から削除する(904)。探索時系列パターン情報に登録された全探索時系列パターンに対する同様の処理が終了した時点で、探索時系列パターン情報110に最小繰り返し回数と最小出現頻度の条件を共に満たす可能性のある探索時系列パターンのみが登録される。
【0058】
再び図4に戻り、次に、探索時系列パターン情報110に含まれない時系列データIDを時系列データ情報から削除する(407)。
【0059】
以上の処理を全時系列データの末尾まで終了した時点で、探索時系列パターン情報110に登録されている探索時系列パターンから抽出された時系列パターンとして繰り返し回数の統計値と出現頻度の統計値と共に出力する(409)。探索時系列パターン情報110には、各時系列パターンの各時系列データにおける繰り返し回数の厳密な値が格納されているため、繰り返し回数に関する統計値の算出が可能であり、各時系列パターンの出現頻度と全時系列データ数が既知
のため、出現頻度の統計値の算出が可能である。
【0060】
なお、図1の出力装置105の図2の結果表示部206には、繰り返し回数の統計値として平均値と最大値と最小値、出現頻度の統計値として頻度と全時系列データ数に対する割合を一例として示した。
【0061】
図14は、本実施例の図4のフローチャートにおける、時系列データ読み出し処理404、繰り返しパターン計数処理405、出現頻度計数処理406に対する記憶装置103から読み出される時系列データのチェックポイントによる処理単位のイメージ図である。
【0062】
1時系列データを一本の直線で示しており、1回目の時系列データ読み出し処理で、はじめにデータ1の先頭から最初のチェックポイントまでの時系列データが読み出される。該読み出された時系列データに対して、繰り返しパターン計数処理が行われる。データ1の繰り返しパターン計数処理が終了した時点で、次の時系列データであるデータ2の先頭から最初のチェックポイントまでの時系列データが読み出され、繰り返しパターン計数処理が行われる。すべての時系列データに対して先頭から最初のチェックポイントまでの時系列データ読み出し処理と繰り返しパターン計数処理が終了した時点で、出現頻度計数処理が行われる。
【0063】
一回目の時系列データ読み出し処理では、各時系列データについて先頭から最初のチェックポイントまでの時系列データが読み出される。出現頻度計数処理の結果が最小出現頻度以上である場合、最初のチェックポイントまでの繰り返しパターン計数処理における繰り返し回数の上限値が最小繰り返し回数以上であった時系列データについて、最初のチェックポイントから2番目のチェックポイントまでに対して、時系列データの読み出し処理、繰り返しパターン計数処理が行われ、すべての時系列データについて終了した時点で、出現頻度計数処理が行われる。
【0064】
出現頻度計数処理の結果が最小出現頻度以上である場合には、同様の処理が繰り返される。最後のチェックポイントまで終了した時点で、最小繰り返し回数以上となる時系列データにおける繰り返し回数、および、出現頻度を得ることができる。途中のチェックポイントまでの出現頻度計数処理の結果が最小出現頻度未満となる場合、その探索時系列パターンは最小出現頻度を満たさないことが分かるため、該途中のチェックポイント以降の時系列データについては処理を省略する。また、各時系列データについて、途中のチェックポイントまでの繰り返しパターン計数処理の結果の繰り返し回数の上限値が最小繰り返し回数未満となる場合、その探索時系列パターンは該時系列データにおいては最小繰り返し回数を満たさないことがわかるため、該途中のチェックポイント以降の時系列データについては処理を省略する。これらの結果、頻出繰り返し時系列パターンでない探索時系列パターンに対する処理を回避し、探索処理負荷を低減することが出来る。
【0065】
以上のように、本実施例によると、各時系列データにおける繰り返し回数の最小値と、全時系列データにおける出現頻度の最小値の条件を共に満たす時系列パターンを得ることが出来る。また、本実施例においては、解析処理の途中経過において繰り返し回数の上限値を算出すること、及び算出した繰り返し回数の上限値を用いて出現頻度を数え上げることにより、最小繰り返し回数を満たし得ない探索時系列パターンと最小出現回数を満たし得ない探索時系列パターンの繰り返し回数の数え上げ処理を途中で打ち切ることにより、繰り返し回数の数え上げ処理対象となる時系列データの範囲を限定し、解析処理負荷を低減することが可能となる。
【0066】
なお、以上で説明した実施例1では繰り返し回数、出現頻度を利用したが、繰り返し回数の各時系列データ長あるいは期間との商である繰り返し率、出現頻度の全時系列データ数との商である出現率(支持度)を利用することでも同様に解析処理を実施することが可能である。
【0067】
また,本実施例では時系列データの処理単位をチェックポイント指定部202に入力させたが,メモリ102の設定値情報107のチェックポイント情報に所定の値を予め設定しておくことによって,ユーザによる処理単位の入力を省略することも可能である。
【実施例2】
【0068】
次に、第2の実施例として、クレジットカードの利用データを例にとり、図1のデータ解析システムの実行プログラム106の処理と、メモリ102に格納される各種の情報を説明する。ここで、本実施例における解析対象のクレジットカードの利用データの一例を表3に示す。表3に明らかなように、時系列データ数20のデータが記憶装置103に格納されているものとする。また、入力装置104において、データの処理単位を5、最小繰り返し回数を3、最小出現頻度を5と入力されたとし、メモリ102の設定値情報107に格納されているとする。
【0069】
【表3】
【0070】
プロセッサ101はメモリ102に格納されている実行プログラム106を実行し、はじめに頻出繰り返しアイテム抽出処理402を行う。例えば、このアイテム抽出処理402により、card01の時系列データが記憶装置103から読み出され、各アイテムの繰り返し回数が数え上げられたとき、メモリ102のアイテム情報109に(店舗A、card01、3、0)、(店舗B、card01、4、0)、(店舗C、card01、3、0)、(店舗D、card01、1、0)、(店舗E、card01、1、0)、(高額決済、card01、3、0)が格納される。最小出現回数が3であることから、アイテム”店舗D”と”店舗E”がアイテム情報から削除され、メモリ102のアイテム情報109には(店舗A、card01、3、0)、(店舗B、card01、4、0)、(店舗C、card01、3、0)、(高額決済、card01、3、0)が保持される。
【0071】
ここで、探索時系列パターン設定処理403において、候補となる繰り返し回数が未知の探索時系列パターンとして、<(店舗A)(店舗B、高額決済)>と<(店舗C)(店舗A)>と<(店舗C)(店舗B)>が設定されたとする。
【0072】
次に、プロセッサ101は実行プログラム106の時系列データ読み出し処理404において、記憶装置103に格納された時系列データが読み出され、メモリ102の時系列データ情報108に処理単位毎に格納される。
【0073】
読み出された時系列データから頻出繰り返しアイテム以外を削除し、時系列データ情報108に格納すると共に、各アイテムの繰り返し回数が数え上げられ、アイテム情報109の繰り返し回数情報が更新される。例えば、card01の時系列データでは、最初の時系列データ読み出し処理では時系列データとして<(店舗A)(店舗C)(店舗A)(店舗B、高額決済)(店舗E)(店舗C)>が読み出され、頻出繰り返しアイテム以外が削除され、card01、<(店舗A)(店舗C)(店舗A)(店舗B、高額決済)(店舗C)>が時系列データ情報108に保持される。また、アイテム情報109のカウント値を(店舗A、card01、3、2)、(店舗B、card01、4、1)、(店舗C、card01、3、2)(高額決済、card01、3、1)と更新する。
【0074】
次に、繰り返しパターン計数処理405において、探索時系列パターンの各時系列データにおける繰り返し回数が数え上げられる。例えば、card01の時系列データについて説明する。まず、探索時系列パターン<(店舗A)(店舗B、高額決済)>が数え上げられる場合、メモリ102の探索時系列パターン情報110から、該探索パターンのcard01の情報として、数え上げ済みの繰り返し回数として0、数え上げ済みの時系列パターンのパターン位置として0が読み出される。
【0075】
その後、card01の時系列データについて、メモリ102の時系列データ情報108の先頭のデータ位置のアイテムセットから順に該探索パターンの1番目のパターン位置のアイテムセット(店舗A)が現れるデータ位置を探し、データ位置1番目に検出される。該探索パターンの1番目のデータ位置のアイテムセットは末尾でないため、探索パターン情報の数え上げ済み時系列パターンの位置を1に更新する。
【0076】
次に、該探索パターンの2番目のパターン位置のアイテムセット(店舗B、高額決済)が現れるデータ位置を該時系列データのデータ位置2番目以降で探し、データ位置4番目で検出される。該探索パターンの2番目のパターン位置のアイテムセットは末尾のため、探索パターン情報の数え上げ済み回数を1増加させ、時系列パターンのパターン位置を0に更新する。再び、該探索パターンの1番目のアイテムセット(店舗A)が現れるデータ位置を該時系列データのデータ位置5番目以降で探すが、該時系列パターンの末尾であるデータ位置5番目まで探しても検出されないため、探索時系列パターン情報110の時系列パターン<(店舗A)(店舗B、高額決済)>の時系列データIDがcard01の数え上げ済み時系列パターンのパターン位置を1に更新し、繰り返し回数の数え上げ処理を終了する。
【0077】
また、探索パターン<(店舗C)(店舗A)>が数え上げられる場合、メモリ102の探索時系列パターン情報110から、該探索パターンのcard01の情報として、数え上げ済みの繰り返し回数が0、数え上げ済みのパターン位置0が読み出される。その後、card01の時系列データについて、メモリ102の時系列データ情報108の先頭のデータ位置のアイテムセットから順に該探索パターンの1番目のパターン位置のアイテムセット(店舗C)が現れるデータ位置を探し、データ位置2番目に検出される。該探索パターンの1番目のパターン位置のアイテムセット(店舗C)は末尾でないため、現パターン位置を2に更新する(図8の808)。
【0078】
次に、該探索パターンの2番目のパターン位置のアイテムセット(店舗A)が現れるデータ位置を該時系列データのデータ位置3番目以降で探し、データ位置3番目で検出される。該探索パターンの2番目のパターン位置のアイテムセット(店舗A)は末尾のため、探索パターン情報の数え上げ済み回数を1増加させ(同806)、現パターンの位置を先頭に更新する(同807)。
【0079】
再び、該探索パターンの1番目のパターン位置のアイテムセット(店舗C)が現れるデータ位置を該時系列データのデータ位置3番目以降で探し、データ位置5番目で検出される。該探索パターンの1番目のパターン位置のアイテムセットは末尾でないため、現パターン位置を2に更新する。また再び、該探索パターンの2番目のパターン位置のアイテムセット(店舗A)が現れるデータ位置を該時系列データのデータ位置5番目以降で探そうとするが、該時系列パターンのデータ位置5番目が末尾のため(同809)、探索パターン情報110の数え上げ済み時系列パターンのパターン位置を2に設定し(同811)、繰り返し回数の数え上げ処理702を終了する。
【0080】
次に、図7のフローにおいて、繰り返し回数の上限値の算出703が行われる。例えば、card01における探索パターン<(店舗A)(店舗B、高額決済)>について、探索時系列パターン情報110には(<(店舗A)(店舗B、高額決済)>、card01、1、0)、アイテム情報109には(店舗A、card01、3、2)、(店舗B、card01、4、1)、(高額決済、card01、3、1)が保持されていることから、数1により上限値が2(=1+1)と算出される。
【0081】
該算出された上限値は最小繰り返し回数(本実施例では3)未満のため、該探索パターンが最小繰り返し回数以上となり得ないことが分かる。該探索パターンの情報を探索パターン情報110から削除することによって、プロセッサ010ではcard01の探索パターンの繰り返し回数数え上げ処理を打ち切り、2回目以降の時系列データ読み出し処理後の繰り返し数え上げ処理を省略する。
【0082】
また、探索パターン<(店舗C)(店舗A)>について、探索パターン情報には(<(店舗C)(店舗A)>、card01、1、1)、アイテム情報には(店舗A、card01、3、2)、(店舗C、card01、3、2)が保持されていることから、数1により上限値が3(=1+1+1)と算出される。該算出された上限値は最小繰り返し回数以上のため、該探索パターンが最小繰り返し回数以上の可能性があることから、2回目以降の時系列データ読み出し処理後の繰り返し数え上げ処理を省略することは出来ない。
【0083】
次に、図4の繰り返し時系列パターン抽出処理の出現頻度の計数処理406が行われる。プロセッサ101はメモリ102の探索時系列パターン情報110に格納された時系列パターンと時系列データIDから、各時系列パターンの時系列データIDの種類数を数え上げ、最小出現頻度未満となる時系列パターンの情報を探索パターン情報から削除する。例えば、探索パターン<(店舗C)(店舗B)>について、探索時系列パターン情報110には(<(店舗C)(店舗B)>、card01、1、1)、(<(店舗C)(店舗B)>、card05、2、1)、(<(店舗C)(店舗B)>、card08、2、0)が格納されているとする。該探索パターンの出現頻度は3であり、最小出現頻度(本実施例においては5)を満たさないことが分かる。この場合、プロセッサ101は探索パターン情報110から該探索パターンを含む情報を削除する。探索パターン情報110から削除された時系列パターンは、2回目以降の時系列データ読み出し処理後の繰り返し数え上げ処理を省略できる。
【0084】
出現頻度計数処理406の次に、時系列データ情報108の更新407が行われる。繰り返し回数数え上げ処理を行う必要のある時系列データIDは探索時系列パターン情報110に保持されている。探索時系列パターン情報110に保持されていない時系列データIDは繰り返し回数の数え上げ処理を行う必要がないため、2回目以降の時系列データ読み出し処理は不要である。探索時系列パターン情報110に保持されない時系列データIDがある場合、該時系列データIDを時系列データ情報108から削除する。例えば、card02、card04、card07が時系列データIDとして保持されていない場合、時系列データ情報108から削除する。
【0085】
以上の処理を各時系列データの末尾まで繰り返す。例えば、本実施例の2回目の時系列データ読み出し処理では、時系列データの順位位置6番目から10番目までが読み出され、card01について、<(店舗B)(店舗B、高額決済)(店舗A)(店舗C)(店舗B、高額決済)>が時系列データ情報108としてメモリ102に保持され、探索パターン<(店舗C)(店舗A)>を数え上げる場合、メモリ102の探索時系列パターン情報110から、該探索パターンのcard01の情報として、数え上げ済みの繰り返し回数が1、数え上げ済みの時系列パターンの位置が1が読み出される。その後、card01の時系列データについて、メモリ102の時系列データ情報108の先頭のアイテムセットから順に該探索パターンの2番目のアイテムセット(店舗A)が現れる順位位置を探す処理を開始する。
【0086】
以上詳述して本実施例の処理によって、最小繰り返し回数と最小出現頻度の条件を共に満たす時系列パターンを不要な繰り返し回数数え上げ処理を回避しつつ抽出することが出来る。
【0087】
本実施例の場合、例えば、card01における探索パターン<(店舗A)(店舗B、高額決済)>については2回目の時系列データ読み出し処理以降の繰り返し回数数え上げ処理を省略することができる。また、例えば、card02、card04、card07の時系列データは2回目以降の時系列データ読み出し処理を省略することができる。
【実施例3】
【0088】
次に、第3の実施例として、データ解析システムが、各時系列データに区切れが存在するデータを解析対象とする場合を説明する。1つの時系列データにおいて所定の句切れをまたがる時系列パターンは該時系列データに含まれないとしたい場合がある。例えば、人の行動パターンの分析において1日単位での行動パターンを考える場合、日付をまたがる行動パターンを数え上げてはならない。
【0089】
図10は、第3の実施例のシステム構成例を示す図である。このシステムは、図1のシステム構成のメモリ102に、解析対象データにおける時系列データの区切れの条件を条件式などの形式で区切れ条件1001として保持する。
【0090】
図11は、本実施例のユーザインタフェースの一例を示している。このユーザインタフェース1100は、図2のユーザインタフェース200に解析対象データにおける時系列データの区切れ条件を設定する区切れ条件設定部1101を加えた構成を取る。ユーザは解析対象データを解析データ指定部201で指定し、処理単位をチェックポイント指定部202に、抽出する時系列パターンの繰り返し回数の最小値を最小繰り返し回数入力部203に、抽出する時系列パターンの出現頻度の最小値を最小出現頻度入力部204に、時系列データの区切れ条件を区切れ条件設定部1101に、それぞれ入力する。実行ボタン205によって、時系列パターン抽出処理を開始する。抽出された時系列パターンは、時系列パターンを構成するアイテムセットのリストと、時系列パターンの評価値である繰り返し回数の統計値と出現頻度とが結果表示部206に表示される。
【0091】
図12は、本実施例の時系列パターン抽出処理におけるユーザによる操作とシステムによる操作のフローを示した図である。はじめに、ユーザは入力装置104において、解析対象のデータを指定、解析対象データの処理単位を入力、抽出する時系列パターンの最小繰り返し回数と最小出現頻度、および、時系列データの区切れ条件を設定部1101から入力する(1201)。以降の処理は、図3と同様である。
【0092】
解析対象の時系列データに区切れ条件が設定された場合の時系列パターン抽出の全体処理手順、頻出繰り返しアイテム抽出処理、候補とする探索時系列パターン設定処理、時系列データ読み出し処理、出現頻度計数処理は、前述の処理手順と同様である。この時系列データに区切れ条件が設定された場合の時系列パターン抽出処理では、繰り返しパターン計数処理における1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理が前述の処理手順と異なる。
【0093】
図13に1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理702の解析対象の時系列データに、区切れ条件が設定された場合の手順を詳細に説明するフローチャートを示す。処理の内容は、前述の図8における繰り返し回数数え上げのパターン位置を設定する処理801から時系列データの末尾まで処理したか調べる処理809までは同様である。現データ位置が該時系列データの末尾かどうかを調べ(809)、末尾でない場合には、現データ位置の直後がメモリ102の設定値情報107の区切れ条件1001を満たすかどうかを調べる(1301)。
【0094】
区切れ条件を満たす場合は現パターン位置を先頭のパターン位置に戻し(1302)、現データ位置を1つ後ろにずらし(810)、該時系列データの現データ位置のアイテムセットが該時系列パターンの現パターン位置のアイテムセットを含むか調べる処理(804)以降を繰り返す。区切れ条件を満たさない場合は現データ位置を1つ後ろにずらし(810)、該時系列データの現データ位置のアイテムセットが該時系列パターンの現パターン位置のアイテムセットを含むか調べる処理(804)以降を繰り返す。末尾の場合は前述と同様である。
【0095】
以上のように、本実施例によると、時系列パターンの区切れの条件を設定し、探索時系列パターンの繰り返し回数の数え上げ処理において、時系列データの句切れが存在する時点で、探索パターンの繰り返し回数を数え上げるパターン位置を先頭に戻すことによって、時系列パターンの句切れをまたがる場合の繰り返し回数の数え上げを回避することが出来る。これにより、時系列データに区切れを設定した場合にも時系列パターンを抽出することが出来る。
【実施例4】
【0096】
第4の実施例として、Webサイトのアクセスログデータを解析するデータ解析システムを説明する。すなわち、Webサイトのアクセスログデータを例にとり、上述したデータ解析システムにおける実行プログラム106において行われる、1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理702を説明する。Webアクセスログデータの場合、1レコードはあるユーザの一回のアクセスを意味し、時系列データIDはユーザID、タイムスタンプはアクセス日時、事象はアクセスしたページのURLとなる。また、Webサイトのアクセスログは一連のアクセスの単位を表わすセッション番号を持ち、同一のセッション番号を持つレコードは同一のセッションでのアクセスであるとする。
【0097】
例えば、表4のデータのuser01はセッション番号100、101、102の3つのセッションを持つ。セッション番号100では、最初にページAがアクセスされ、次にページBがアクセスされ、最後にページCがアクセスされたことを意味する。ここで、解析対象のアクセスログデータを表4に示すデータとし、記憶装置103に格納されているとする。また、入力装置104において、区切れ条件として“i番目のレコードのセッション番号≠(i+1)番目のレコードのセッション番号”が設定されたとし、メモリ102の設定情報に格納されているとする。
【0098】
【表4】
【0099】
1つの探索時系列パターンに対する1つの時系列データにおける繰り返し回数数え上げ処理702として、user01の時系列データにおける探索パターン<(ページA)(ページB)>が数え上げられるとし、メモリ102の時系列データ情報108のuser01の時系列データにセッション番号とURLの組のリストとして(100、ページA)(100、ページB)(100、ページA)(101、ページA)(101、ページB)(101、ページD)(101、ページE)(101、ページD)(102、ページD)が保持されており、メモリ102の探索パターン情報110から、該探索パターンのuser01の情報として、数え上げ済み繰り返し回数が0、数え上げ済みの時系列パターンのパターン位置が0と読み出されたとする。本実施例では、探索パターンの先頭のパターン位置のアイテムセット(ページA)が含まれるデータ位置とメモリ102の時系列データ情報108の先頭のデータ位置から順に探索する(図13の803に対応)。
【0100】
はじめに、該探索パターンの先頭のパターン位置のアイテムセット(ページA)が該時系列データの先頭のデータ位置のアイテムセットに現れることが検出される。現パターン位置が該探索パターンの末尾でないため(同805のNo)、現パターン位置を次のパターン位置である2とする(同808)。
【0101】
次に、現データ位置が末尾であるか調べる(同809)が、現データ位置が末尾でないことから、現データ位置の直後が区切れであるかを調べる(同1301)。上述の通り、メモリ102の区切れ条件1001に句切れの条件としてセッション番号が異なること設定されているため、現データ位置のセッション番号と次のデータ位置のセッション番号を比較し、共に100と等しいセッション番号であるため、現データ位置を2とし(同810)、再び現パターン位置のアイテムセットが現データ位置に含まれるか調べる(同804)。本実施例の場合、現パターン位置が2のとき、現データ位置が2において現パターン位置のアイテムセット(ページB)が現データ位置に現れることが検出され、メモリ102の探索パターン情報110の数え上げ済み繰り返し回数を1に更新し(同806)、現パターン位置を先頭(同807)、現データ位置を3とする。
【0102】
次に、現パターン位置のアイテムセット(ページA)が現データ位置のアイテムセット(ページC)に含まれないため、現データ位置を次のデータ位置にずらそうとする。ここで、現データ位置のセッション番号が100、次のデータ位置のセッション番号が101であることから、区切れが存在することが検出され(同1301)、現データ位置を次のデータ位置にずらす前に、現パターン位置に先頭のパターン位置を設定する(同1302)。これよって、セッション番号100と101にまたがる時系列パターンの繰り返し回数の数え上げを回避することができる。以下、同様に繰り返し回数数え上げ処理が時系列データの末尾まで続行される。
【0103】
なお、本実施例では時系列データ情報にセッション番号とアイテムセットの組のリストを保持し、区切れの条件として条件式を設定したが、句切れの条件を所定の記号とし、時系列データの句切れに所定の記号を付加したデータを用いることでも同様に解析処理を実施することが可能である。例えば、表4のデータにおいて、セッション番号が異なる場合を区切れと設定し、句切れを表わす記号を“.”とした場合、表5の時系列データによって本実施例と同様に解析処理を実施することが可能となる。
【0104】
【表5】
【産業上の利用可能性】
【0105】
以上詳述した本発明は、データベース及びデータウェアハウスを対象としたデータ解析システム及び方法に関し、特にデータベースのレコードを解析してデータの出現順序の規則性を明らかにするデータマイニング技術として極めて有用である。
【符号の説明】
【0106】
100…コンピュータ
101…プロセッサ
102…メモリ
103…記憶装置
104…入力装置
105…出力装置
106…実行プログラム
107…設定値情報
108…時系列データ情報
109…アイテム情報
110…探索パターン情報
111…チェックポイント情報
1001…区切れ条件
1101…区切れ条件設定部
200…ユーザインタフェース
201…解析データ指定部
202…チェックポイント指定部
203…最小繰り返し回数入力部
204…最小出現頻度入力部
205…実行ボタン
206…結果表示部。
【特許請求の範囲】
【請求項1】
事象と,その事象の属するIDと,事象間の順序関係を示す情報の複数の組からなるデータをコンピュータによって解析するデータ解析システムであって,
前記コンピュータは、解析対象の前記データと、解析処理を行う実行プログラムを格納する記憶部と,前記実行プログラムを実行する処理部を有し,
前記処理部は、
同じIDを有する事象をその順序関係に従って並べた前記データを時系列データとして前記記憶部に格納する第1のステップと,
前記事象の重複順列からなる時系列パターンについて,前記時系列データ各々において繰り返される回数を数え上げる第2のステップと,
前記繰り返し回数が所定の回数以上となる前記時系列データの数を数え上げる第3のステップと,
数え上げた前記時系列データの数が所定の数以上となる時系列パターンを抽出する第4のステップと,
を実行することを特徴とするデータ解析システム。
【請求項2】
請求項1記載のデータ解析システムであって,
前記処理部は、
前記時系列データ各々に所定の間隔でチェックポイントを設け,前記第1のステップにおいて,前記時系列データ各々をチェックポイントから次のチェックポイントまでの範囲で前記記憶部に格納するステップと、
前記繰り返し回数が未知の時系列パターンの前記時系列データ各々における繰り返し回数について,前記第2のステップにおいて、前記記憶部に格納された範囲の前記時系列データから繰り返し回数を数え上げるステップと,
数え上げを実施した前記範囲における数え上げ回数と、数え上げが未実施の時系列データにおける該時系列パターンを構成する事象の繰り返し回数とを加算することによって,該時系列パターンの該時系列データにおける繰り返し回数の上限値を算出するステップと,
前記第3のステップにおいて、該繰り返し回数の上限値が所定の回数以上となる時系列パターンの時系列データの数を数え上げるステップと,
数え上げた前記時系列データの数が所定の数以上となる時系列パターンについて,前記ステップを繰り返すステップと,
を実行することを特徴とするデータ解析システム。
【請求項3】
請求項1記載のデータ解析システムであって、
前記時系列データは区切れを有するデータであり、
前記処理部は、
前記区切れ毎に、前記第2のステップと前記第3のステップと前記第4のステップを実行する、
ことを特徴とするデータ解析システム。
【請求項4】
請求項1記載のデータ解析システムであって、
前記時系列データは、Webサイトへのアクセス単位を示すセッション番号を含むアクセスログデータであり、
前記処理部は、
同一の前記セッション番号を有する前記アクセスログデータ毎に、前記第2のステップと前記第3のステップと前記第4のステップを実行する、
ことを特徴とするデータ解析システム。
【請求項5】
請求項1記載のデータ解析システムであって、
前記コンピュータは出力部を更に備え、
前記処理部は、抽出した前記時系列パターンを、前記第2のステップで数え上げられた前記回数と前記第3のステップで数え上げられた前記数と共に前記出力部に出力する、
ことを特徴とするデータ解析システム。
【請求項6】
請求項1記載のデータ解析システムであって、
前記コンピュータは前記所定の回数及び前記所定の数を入力可能な入力部を更に備える、
ことを特徴とするデータ解析システム。
【請求項7】
請求項3記載のデータ解析システムであって、
前記コンピュータは前記区切れを前記時系列データに設定する条件を入力可能な入力部を更に備えた、
ことを特徴とするデータ解析システム。
【請求項8】
事象と、前記事象の属するIDと、前記事象間の順序関係を示す情報の組が複数格納されたデータを、処理部と記憶部を備えた計算機で解析するデータ解析方法であって、
同じIDを有する前記事象をその順序関係に従って並べたデータを時系列データとし、1以上の前記事象を順方向に並べた重複順列を時系列パターンとし、
前記処理部は、
所定の数以上の前記時系列データにおいて、前記時系列データ各々における所定の回数以上繰り返される前記時系列パターンである頻出繰り返し時系列パターンを抽出するため、
繰り返し回数が未知の前記時系列パターンについて、前記時系列データ各々における繰り返し回数を数え上げるステップと、
前記繰り返し回数が所定の回数以上となる前記時系列データの数を出現頻度として数え上げるステップと、
前記出現頻度が所定の数以上となる前記時系列パターンを抽出するステップと、
を実行することを特徴とするデータ解析方法。
【請求項9】
請求項8記載のデータ解析方法であって、
前記時系列データは区切れが存在するデータであり、
前記処理部は、前記区切れ毎の前記時系列データに対し、前記ステップ各々を実行する、
ことを特徴とするデータ解析方法。
【請求項10】
請求項8記載のデータ解析方法であって、
前記時系列データは、Webサイトへのアクセス単位を示すセッション番号を有するアクセスログデータであり、
前記処理部は、同一の前記セッション番号を有する前記アクセスログデータ毎に、前記ステップ各々を実行する、
ことを特徴とするデータ解析方法。
【請求項11】
請求項8に記載のデータ解析方法であって、
前記計算機は表示部を更に備え、
前記処理部は、抽出された前記時系列パターンと対応する前記繰り返し回数と前記出現頻度とを前記表示部に表示する、
ことを特徴とするデータ解析方法。
【請求項12】
事象と、前記事象の属するIDと、前記事象間の順序関係を示す情報の組が複数格納されたデータを、処理部と記憶部を備えた計算機で解析処理するデータ解析方法であって、
前記処理部は、
同じIDを有する事象をその順序関係に従って並べたデータを時系列データとし、1以上の事象を順方向に並べた重複順列を時系列パターンとし、所定の数以上の前記時系列データにおいて、前記時系列データ各々における所定の回数以上繰り返される前記時系列パターンである頻出繰り返し時系列パターンを抽出するため、
前記時系列データ各々に、所定の間隔でチェックポイントを設定する第1のステップと、
前記時系列データ各々における繰り返し回数が未知の前記時系列パターンについて、前記時系列データ各々についてチェックポイントから次のチェックポイントまでの範囲で前記時系列パターンが繰り返される回数を数え上げる第2のステップと、
前記時系列データにおける前記時系列パターンの繰り返し回数の上限値を、既に数え上げられたチェックポイントまででの繰り返し回数と、当該チェックポイント以降に現れる各事象の繰り返し回数との和から算出する第3のステップと、
算出された前記上限値が所定の繰り返し回数以上となる時系列データの数を出現頻度として数え上げる第4のステップと、
数え上げた前記出現頻度が所定の数以上となる時系列パターンを抽出する第5のステップと、
抽出された前記時系列パターンについて、前記第2から第5のステップを最後のチェックポイントまで繰り返す第6のステップと、
を実行することを特徴とするデータ解析方法。
【請求項13】
請求項12に記載のデータ解析方法であって、
前記計算機は出力部を更に備え、
前記処理部は、
最後のチェックポイントまで処理した時点で、抽出された前記時系列パターンと対応する前記繰り返し回数と前記出現頻度とを前記出力部に出力する、
ことを特徴とするデータ解析方法。
【請求項14】
請求項12記載のデータ解析方法であって、
前記時系列データは区切れが存在するデータであり、
前記処理部は、前記区切れ毎の前記時系列データに対し、前記ステップ各々を実行する、
ことを特徴とするデータ解析方法。
【請求項15】
請求項12記載のデータ解析方法であって、
前記時系列データは、Webサイトへのアクセス単位を示すセッション番号を含むアクセスログデータであり、
前記処理部は、同一の前記セッション番号を有する前記アクセスログデータ毎に、前記ステップ各々を実行する、
ことを特徴とするデータ解析方法。
【請求項1】
事象と,その事象の属するIDと,事象間の順序関係を示す情報の複数の組からなるデータをコンピュータによって解析するデータ解析システムであって,
前記コンピュータは、解析対象の前記データと、解析処理を行う実行プログラムを格納する記憶部と,前記実行プログラムを実行する処理部を有し,
前記処理部は、
同じIDを有する事象をその順序関係に従って並べた前記データを時系列データとして前記記憶部に格納する第1のステップと,
前記事象の重複順列からなる時系列パターンについて,前記時系列データ各々において繰り返される回数を数え上げる第2のステップと,
前記繰り返し回数が所定の回数以上となる前記時系列データの数を数え上げる第3のステップと,
数え上げた前記時系列データの数が所定の数以上となる時系列パターンを抽出する第4のステップと,
を実行することを特徴とするデータ解析システム。
【請求項2】
請求項1記載のデータ解析システムであって,
前記処理部は、
前記時系列データ各々に所定の間隔でチェックポイントを設け,前記第1のステップにおいて,前記時系列データ各々をチェックポイントから次のチェックポイントまでの範囲で前記記憶部に格納するステップと、
前記繰り返し回数が未知の時系列パターンの前記時系列データ各々における繰り返し回数について,前記第2のステップにおいて、前記記憶部に格納された範囲の前記時系列データから繰り返し回数を数え上げるステップと,
数え上げを実施した前記範囲における数え上げ回数と、数え上げが未実施の時系列データにおける該時系列パターンを構成する事象の繰り返し回数とを加算することによって,該時系列パターンの該時系列データにおける繰り返し回数の上限値を算出するステップと,
前記第3のステップにおいて、該繰り返し回数の上限値が所定の回数以上となる時系列パターンの時系列データの数を数え上げるステップと,
数え上げた前記時系列データの数が所定の数以上となる時系列パターンについて,前記ステップを繰り返すステップと,
を実行することを特徴とするデータ解析システム。
【請求項3】
請求項1記載のデータ解析システムであって、
前記時系列データは区切れを有するデータであり、
前記処理部は、
前記区切れ毎に、前記第2のステップと前記第3のステップと前記第4のステップを実行する、
ことを特徴とするデータ解析システム。
【請求項4】
請求項1記載のデータ解析システムであって、
前記時系列データは、Webサイトへのアクセス単位を示すセッション番号を含むアクセスログデータであり、
前記処理部は、
同一の前記セッション番号を有する前記アクセスログデータ毎に、前記第2のステップと前記第3のステップと前記第4のステップを実行する、
ことを特徴とするデータ解析システム。
【請求項5】
請求項1記載のデータ解析システムであって、
前記コンピュータは出力部を更に備え、
前記処理部は、抽出した前記時系列パターンを、前記第2のステップで数え上げられた前記回数と前記第3のステップで数え上げられた前記数と共に前記出力部に出力する、
ことを特徴とするデータ解析システム。
【請求項6】
請求項1記載のデータ解析システムであって、
前記コンピュータは前記所定の回数及び前記所定の数を入力可能な入力部を更に備える、
ことを特徴とするデータ解析システム。
【請求項7】
請求項3記載のデータ解析システムであって、
前記コンピュータは前記区切れを前記時系列データに設定する条件を入力可能な入力部を更に備えた、
ことを特徴とするデータ解析システム。
【請求項8】
事象と、前記事象の属するIDと、前記事象間の順序関係を示す情報の組が複数格納されたデータを、処理部と記憶部を備えた計算機で解析するデータ解析方法であって、
同じIDを有する前記事象をその順序関係に従って並べたデータを時系列データとし、1以上の前記事象を順方向に並べた重複順列を時系列パターンとし、
前記処理部は、
所定の数以上の前記時系列データにおいて、前記時系列データ各々における所定の回数以上繰り返される前記時系列パターンである頻出繰り返し時系列パターンを抽出するため、
繰り返し回数が未知の前記時系列パターンについて、前記時系列データ各々における繰り返し回数を数え上げるステップと、
前記繰り返し回数が所定の回数以上となる前記時系列データの数を出現頻度として数え上げるステップと、
前記出現頻度が所定の数以上となる前記時系列パターンを抽出するステップと、
を実行することを特徴とするデータ解析方法。
【請求項9】
請求項8記載のデータ解析方法であって、
前記時系列データは区切れが存在するデータであり、
前記処理部は、前記区切れ毎の前記時系列データに対し、前記ステップ各々を実行する、
ことを特徴とするデータ解析方法。
【請求項10】
請求項8記載のデータ解析方法であって、
前記時系列データは、Webサイトへのアクセス単位を示すセッション番号を有するアクセスログデータであり、
前記処理部は、同一の前記セッション番号を有する前記アクセスログデータ毎に、前記ステップ各々を実行する、
ことを特徴とするデータ解析方法。
【請求項11】
請求項8に記載のデータ解析方法であって、
前記計算機は表示部を更に備え、
前記処理部は、抽出された前記時系列パターンと対応する前記繰り返し回数と前記出現頻度とを前記表示部に表示する、
ことを特徴とするデータ解析方法。
【請求項12】
事象と、前記事象の属するIDと、前記事象間の順序関係を示す情報の組が複数格納されたデータを、処理部と記憶部を備えた計算機で解析処理するデータ解析方法であって、
前記処理部は、
同じIDを有する事象をその順序関係に従って並べたデータを時系列データとし、1以上の事象を順方向に並べた重複順列を時系列パターンとし、所定の数以上の前記時系列データにおいて、前記時系列データ各々における所定の回数以上繰り返される前記時系列パターンである頻出繰り返し時系列パターンを抽出するため、
前記時系列データ各々に、所定の間隔でチェックポイントを設定する第1のステップと、
前記時系列データ各々における繰り返し回数が未知の前記時系列パターンについて、前記時系列データ各々についてチェックポイントから次のチェックポイントまでの範囲で前記時系列パターンが繰り返される回数を数え上げる第2のステップと、
前記時系列データにおける前記時系列パターンの繰り返し回数の上限値を、既に数え上げられたチェックポイントまででの繰り返し回数と、当該チェックポイント以降に現れる各事象の繰り返し回数との和から算出する第3のステップと、
算出された前記上限値が所定の繰り返し回数以上となる時系列データの数を出現頻度として数え上げる第4のステップと、
数え上げた前記出現頻度が所定の数以上となる時系列パターンを抽出する第5のステップと、
抽出された前記時系列パターンについて、前記第2から第5のステップを最後のチェックポイントまで繰り返す第6のステップと、
を実行することを特徴とするデータ解析方法。
【請求項13】
請求項12に記載のデータ解析方法であって、
前記計算機は出力部を更に備え、
前記処理部は、
最後のチェックポイントまで処理した時点で、抽出された前記時系列パターンと対応する前記繰り返し回数と前記出現頻度とを前記出力部に出力する、
ことを特徴とするデータ解析方法。
【請求項14】
請求項12記載のデータ解析方法であって、
前記時系列データは区切れが存在するデータであり、
前記処理部は、前記区切れ毎の前記時系列データに対し、前記ステップ各々を実行する、
ことを特徴とするデータ解析方法。
【請求項15】
請求項12記載のデータ解析方法であって、
前記時系列データは、Webサイトへのアクセス単位を示すセッション番号を含むアクセスログデータであり、
前記処理部は、同一の前記セッション番号を有する前記アクセスログデータ毎に、前記ステップ各々を実行する、
ことを特徴とするデータ解析方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【公開番号】特開2011−123652(P2011−123652A)
【公開日】平成23年6月23日(2011.6.23)
【国際特許分類】
【出願番号】特願2009−280525(P2009−280525)
【出願日】平成21年12月10日(2009.12.10)
【出願人】(000005108)株式会社日立製作所 (27,607)
【Fターム(参考)】
【公開日】平成23年6月23日(2011.6.23)
【国際特許分類】
【出願日】平成21年12月10日(2009.12.10)
【出願人】(000005108)株式会社日立製作所 (27,607)
【Fターム(参考)】
[ Back to top ]