(57)【要約】【課題】分析者あるいは利用者の要求に適した系列パターンのみを漏れなく短時間で抽出すること【解決手段】抽出された系列パターンが含んでいなければならない系列データを表す制約系列データが予め指定される。入力された複数の系列データから、まずは系列長が１の系列パターン候補をもとめる。次に、この系列パターン候補の系列長を延長して複数の新たな系列パターン候補をもとめることにより、系列パターン候補の集合を生成する。この系列パターン候補集合において、制約系列データを含まない系列パターンしか生成し得ない系列パターン候補を削除したのち、制約系列データを含み、かつ頻出する系列データを新たな系列パターンとして抽出する。【選択図】図３
2007041683.tif 000002
【特許請求の範囲】
【請求項１】
複数の系列データにおいて頻出する系列データを系列パターンとして抽出する系列パターン抽出装置において、
抽出された系列パターンが含んでいなければならない系列データを表す制約系列データを記憶する制約系列データ記憶手段と、
既に生成された系列パターン候補集合の自己結合により、新たな系列パターン候補集合を生成する候補生成手段と、
生成された新たな系列パターン候補集合を記憶する系列パターン候補記憶手段と、
系列パターン候補を成す系列データと前記制約系列データとの間で項目の包含関係を規定する系列パターン候補条件に従い、該系列パターン候補条件を満たさない系列パターン候補を前記系列パターン候補記憶手段から削除する削除手段と、
前記系列パターン候補記憶手段に残存する系列パターン候補から前記制約系列データを含む系列パターンを新たな系列パターンとして抽出する抽出手段とを具備する系列パターン抽出装置。
【請求項２】
前記候補生成手段で生成された新たな系列パターン候補の系列長が３以上のときに、既に非頻出と判定された系列データを部分集合として含む系列パターン候補を前記系列パターン候補記憶手段から削除する非頻出候補削除手段をさらに具備することを特徴とする請求項１に記載の系列パターン抽出装置。
【請求項３】
前記候補生成手段は、系列パターン候補を
（１）制約系列データ集合に含まれているもの
（２）制約系列データ集合において出現頻度が高いもの
（３）同一順序位置の項目集合数が多いもの
の順序で処理する系列パターン整列手段を含むことを特徴とする請求項１又は２に記載の系列パターン抽出装置。
【請求項４】
前記系列パターン候補条件は
（ａ）  前記系列パターン候補を成す系列データが、前記制約系列データを完全に含むこと
（ｂ）前記系列パターン候補を成す系列データとの間で一端の項目を除く項目と一致する制約系列データの項目を、その制約系列データから取り除いた後に残った全ての項目が、前記一端の項目を除く全ての項目が互いに一致する系列パターン候補集合におけるいずれかの候補の前記一端の項目に含まれること
（ｃ）  前記一端の項目を除く全ての項目が互いに一致する系列パターン候補集合の中に、上記（ａ）、（ｂ）のいずれかの条件を満たす系列データが存在すること
を規定する請求項１に記載の系列パターン抽出装置。
【請求項５】
前記候補生成手段により生成された複数の系列パターン候補を、一つの系列パターン候補集合において複数の系列パターン候補を表す各々の系列データの前記一端の項目を除く全ての項目が互いに一致するように分類する分類手段をさらに具備する請求項１に記載の系列パターン抽出装置。
【請求項６】
前記系列パターン候補記憶手段は、前記候補生成手段により生成された複数の系列パターン候補を項目の並びに従って記憶するハッシュ木、トライ、Ｂ木のいずれかを含む請求項１に記載の系列パターン抽出装置。
【請求項７】
複数の系列データにおいて頻出する系列データを系列パターンとして抽出する系列パターン抽出装置において、
抽出された系列パターンが含んでいなければならない系列データを表す制約系列データを記憶する制約系列データ記憶手段と、
前記制約系列データのいずれかの項目が出現する位置を境界として、前記複数の系列データのうちの一つの系列データを第一の部分系列データと第二の部分系列データとに分解する分解手段と、
前記第一の部分系列データから前記制約系列データを含む第一の部分系列パターンを抽出し、前記第二の部分系列データから前記制約系列データを含む第二の部分系列パターンを抽出する第一の抽出手段と、
前記制約系列データと前記第一の部分系列パターンと前記第二の部分系列パターンとを併合することにより併合系列データを求める併合手段と、
前記複数の系列データにおいて頻出する併合系列データを新たな系列パターンとして抽出する第二の抽出手段とを具備する系列パターン抽出装置。
【請求項８】
複数の系列データにおいて頻出する系列データを系列パターンとして抽出する系列パターン抽出装置の作動方法において、
抽出された系列パターンが含んでいなければならない系列データを表す制約系列データを制約系列データ記憶手段が記憶するステップと、
既に生成された系列パターン候補集合の自己結合により、新たな系列パターン候補集合を候補生成手段が生成するステップと、
生成された新たな系列パターン候補集合を系列パターン候補記憶手段が記憶するステップと、
系列パターン候補を成す系列データと前記制約系列データとの間で項目の包含関係を規定する系列パターン候補条件に従い、該系列パターン候補条件を満たさない系列パターン候補を削除手段が前記系列パターン候補記憶手段から削除するステップと、
抽出手段が、前記系列パターン候補記憶手段に残存する系列パターン候補から前記制約系列データを含む系列パターンを新たな系列パターンとして抽出するステップとを具備する系列パターン抽出装置の作動方法。
【請求項９】
前記候補生成手段で生成された新たな系列パターン候補の系列長が３以上のときに、既に非頻出と判定された系列データを部分集合として含む系列パターン候補を前記系列パターン候補記憶手段から削除するステップをさらに具備することを特徴とする請求項８に記載の系列パターン抽出装置の作動方法。
【請求項１０】
前記候補生成手段により生成された系列パターン候補を
（１）制約系列データ集合に含まれているもの
（２）制約系列データ集合において出現頻度が高いもの
（３）同一順序位置の項目集合数が多いもの
の順序で処理するステップを含むことを特徴とする請求項８又は９に記載の系列パターン抽出装置の作動方法。
【請求項１１】
前記系列パターン候補条件は
（ａ）  前記系列パターン候補を成す系列データが、前記制約系列データを完全に含むこと
（ｂ）前記系列パターン候補を成す系列データとの間で一端の項目を除く項目と一致する制約系列データの項目を、その制約系列データから取り除いた後に残った全ての項目が、前記一端の項目を除く全ての項目が互いに一致する系列パターン候補集合におけるいずれかの候補の前記一端の項目に含まれること
（ｃ）  前記一端の項目を除く全ての項目が互いに一致する系列パターン候補集合の中に、上記（ａ）、（ｂ）のいずれかの条件を満たす系列データが存在すること
を規定する請求項８に記載の系列パターン抽出装置の作動方法。
【請求項１２】
前記候補生成手段により生成された複数の系列パターン候補を、一つの系列パターン候補集合において複数の系列パターン候補を表す各々の系列データの前記一端の項目を除く全ての項目が互いに一致するように分類手段が分類するステップをさらに具備する請求項８に記載の系列パターン抽出装置の作動方法。
【請求項１３】
前記系列パターン候補記憶手段は、前記候補生成手段により生成された複数の系列パターン候補を項目の並びに従って記憶するハッシュ木、トライ、Ｂ木のいずれかを含む請求項８に記載の系列パターン抽出装置の作動方法。
【請求項１４】
複数の系列データにおいて頻出する系列データを系列パターンとして抽出する系列パターン抽出装置の作動方法において、
抽出された系列パターンが含んでいなければならない系列データを表す制約系列データを制約系列データ記憶手段が記憶するステップと、
分解手段が、前記制約系列データのいずれかの項目が出現する位置を境界として、前記複数の系列データのうちの一つの系列データを第一の部分系列データと第二の部分系列データとに分解するステップと、
第一の抽出手段が、前記第一の部分系列データから前記制約系列データを含む第一の部分系列パターンを抽出し、前記第二の部分系列データから前記制約系列データを含む第二の部分系列パターンを抽出するステップと、
併合手段が、前記制約系列データと前記第一の部分系列パターンと前記第二の部分系列パターンとを併合することにより併合系列データを求めるステップと、
第二の抽出手段が、前記複数の系列データにおいて頻出する併合系列データを新たな系列パターンとして抽出するステップとを具備する系列パターン抽出装置の作動方法。
【請求項１５】
複数の系列データにおいて頻出する系列データを系列パターンとして抽出する系列パターン抽出プログラムにおいて、
抽出された系列パターンが含んでいなければならない系列データを表す制約系列データを制約系列データ記憶手段に記憶する手順と、
既に生成された系列パターン候補集合の自己結合により、新たな系列パターン候補集合を生成する手順と、
生成された新たな系列パターン候補集合を系列パターン候補記憶手段に記憶する手順と、
系列パターン候補を成す系列データと前記制約系列データとの間で項目の包含関係を規定する系列パターン候補条件に従い、該系列パターン候補条件を満たさない系列パターン候補を前記系列パターン候補記憶手段から削除する手順と、
前記系列パターン候補記憶手段に残存する系列パターン候補から前記制約系列データを含む系列パターンを新たな系列パターンとして抽出する手順とをコンピュータに実行させるための系列パターン抽出プログラム。
【請求項１６】
複数の系列データにおいて頻出する系列データを系列パターンとして抽出する系列パターン抽出プログラムにおいて、
抽出された系列パターンが含んでいなければならない系列データを表す制約系列データを制約系列データ記憶手段に記憶する手順と、
前記制約系列データのいずれかの項目が出現する位置を境界として、前記複数の系列データのうちの一つの系列データを第一の部分系列データと第二の部分系列データとに分解する手順と、
前記第一の部分系列データから前記制約系列データを含む第一の部分系列パターンを抽出し、前記第二の部分系列データから前記制約系列データを含む第二の部分系列パターンを抽出する手順と、
前記制約系列データと前記第一の部分系列パターンと前記第二の部分系列パターンとを併合することにより併合系列データを求める手順と、
前記複数の系列データにおいて頻出する併合系列データを新たな系列パターンとして抽出する手順とをコンピュータに実行させるための系列パターン抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、系列データより構成されるデータ集合から、頻出系列データを系列パターンとして抽出する、系列パターン抽出装置、系列パターン抽出方法、および系列パターン抽出プログラムに関する。
【背景技術】
【０００２】
パターン抽出装置では、予め指定する最小支持度を大きくすると自明なパターンしか抽出されない。一方、最小支持度を小さくすると抽出処理時間が長くなるとともに、分析者の要求の有無に関わらず高頻出のパターンが抽出されるために、大量の抽出結果が出力されることが多く解析が煩雑になりやすい。この性質は、扱うデータ量が増加するにつれて顕著となる。
【０００３】
これを解決するための方策として、下記特許文献１には、データ項目の重複度と価値を考慮し、適切なデータ項目のみを使用してパターン抽出を行うことで処理時間を短くすることが記載されている。
【０００４】
また、下記特許文献２には、予め指定した制約による処理対象データの絞込みと抽出結果の抑制を行うことで処理時間を短縮し、分析者が必要とする抽出パターンのみの出力を行うことが記載されている。
【特許文献１】特開平９−２５１４６７号公報
【特許文献２】特開２００４−１１０３２７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上記特許文献１に記載のものでは、適切でないと判断された項目を使用することによって有用なパターンが抽出されることもあるため、抽出された結果に漏れが生じるという問題点がある。また、上記特許文献２に記載のものでは、予め指定した制約はパターン抽出処理自体の効率化には寄与せず、制約による絞込み結果の処理対象データが膨大である場合に多大な抽出処理時間を要するという問題点がある。
【０００６】
したがって、従来の系列パターン抽出装置では、有用な系列パターンであっても抽出されないときがある、もしくは、抽出処理時間が長いという問題がある。
【０００７】
そこで本発明は、分析者あるいは利用者の要求に適した系列パターンのみを漏れなく短時間で抽出することのできる系列パターン抽出装置、系列パターン抽出方法、および系列パターン抽出プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一観点に係る系列パターン抽出装置は、複数の系列データにおいて頻出する系列データを系列パターンとして抽出する系列パターン抽出装置において、抽出された系列パターンが含んでいなければならない系列データを表す制約系列データを記憶する制約系列データ記憶手段と、既に生成された系列パターン候補集合の自己結合により、新たな系列パターン候補集合を生成する候補生成手段と、生成された新たな系列パターン候補集合を記憶する系列パターン候補記憶手段と、系列パターン候補を成す系列データと前記制約系列データとの間で項目の包含関係を規定する系列パターン候補条件に従い、該系列パターン候補条件を満たさない系列パターン候補を前記系列パターン候補記憶手段から削除する削除手段と、前記系列パターン候補記憶手段に残存する系列パターン候補から前記制約系列データを含む系列パターンを新たな系列パターンとして抽出する抽出手段とを具備する。
【発明の効果】
【０００９】
本発明によれば、分析者あるいは利用者の要求に適した系列パターンのみを漏れなく短時間で抽出することのできる系列パターン抽出装置、系列パターン抽出方法、および系列パターン抽出プログラムを提供できる。
【発明を実施するための最良の形態】
【００１０】
本発明の第一の実施形態は、アプリオリ性を利用する従来の系列パターン抽出装置に対して、指定された系列データを含んでいる頻出系列データのみを系列パターンとして抽出しなければならないという制約を与え、系列パターン抽出処理中に、制約を満たす系列パターンを生成し得ないと判断された系列データを系列パターン候補集合から取り除くことで、処理量の削減を図るというものである。「アプリオリ性」とは、系列データのいずれの部分集合についても、その頻度は、当該系列データの頻度よりも高くなることはない、という性質である。
【００１１】
また、制約を満たしているか否かの判断には、以下の性質が利用される。すなわち、系列パターン候補となる系列データにおいて、該系列データの要素数を増やすときに付加する要素を除く要素の並びに含まれない、制約として記憶された系列データのいずれかの要素が、分類された系列データの集合に含まれるいずれの系列データの、系列パターン候補となる系列データの要素数を増やすときに付加する要素にも含まれていないときに、その系列データからは制約を満たす頻出系列データは生成されない、という性質である。
【００１２】
本発明の第二の実施形態は、指定された系列データを含んでいる頻出系列データのみを系列パターンとして抽出しなければならない、という制約を与えるものである。特に第二の実施形態は、制約系列データに含まれる要素の位置を境界として解析対象の系列データを分割し、分割された系列データの集合ごとに系列パターンを抽出し、それらの系列パターンを併合することにより新たな系列パターンを抽出するというものである。この第二の実施形態によっても、第一の実施形態と同様に処理量の削減を図ることができる。
【００１３】
以下、本発明の実施形態の詳細な説明に先立ち、用語や表記等について説明する。
【００１４】
［系列データ］
本明細書において「系列データ」とは、順序概念を有するとともに一意に識別可能な「項目」と呼ばれる単一あるいは複数の情報を保有するデータのことをいう。各々の系列データは項目によって特徴付けられる。また、個々の系列データ内において、全ての項目は一意に順序付けられる。
【００１５】
一意に順序付けられているのであれば、順序付けの基準は、時間でもよいし、優先順位でもよいし、番号でもよい。また、複数の項目が、順序付けにおいて同一の順序位置にあることを可能とする。例えば、時間であれば同時、優先順位であれば同一順位、番号であれば同一番号、の複数の項目が存在していてもよい。
【００１６】
系列データの例を挙げる。購買履歴、貸し出し履歴、健康診断問診データ等は、系列データの例となる。また、特開２００４−２８７７９８号公報に記載されているような離散化手法等を用いることで、脈拍、脳波、ネットワークのトラフィック量推移データ等の波形データも系列データの例となる。また、特開２００５−８４９１９号公報に記載されているようなテキストマイニング手法等を用いることで、日誌、日報、ＷＥＢサイト、ＷＥＢ掲示板、ブログ等のテキストデータも系列データの例となる。以下では、営業日報データを例として説明をする。図１は、営業日報データから、テキストマイニング手法によって抽出した概念キーワードを用いて作成した系列データの集合を示している。なお、各系列データの左には識別子を付与してある。
【００１７】
次に、系列データの表記方法に関して説明する。
【００１８】
以下の説明では、系列データの表記として「＜問い合わせ，打ち合わせ予約，（打ち合わせ，好評）＞」のような表記を用いる。「＜」と「＞」で囲まれた要素は一つの系列データ示し、「，」は要素の区切りを示し、「（」と「）」で囲まれた要素は同一順序位置に生じていることを示す。また、左の要素ほど先に生じたことを示す。この場合、「問い合わせ」が生じた後「打ち合わせ予約」が生じ、「打ち合わせ予約」が生じた後「打ち合わせ」と「好評」が同一順序位置に生じたことを意味する。また、順序を入れ替えた系列データは別の系列データとする。例えば、＜打ち合わせ予約，打ち合わせ＞と＜打ち合わせ，打ち合わせ予約＞は別の系列データである。
【００１９】
ただし、「（」と「）」で囲まれた要素は、同一順序位置に生じているため順序を入れ替えても同じ系列データである。例えば、＜（打ち合わせ，好評）＞と＜（好評，打ち合わせ）＞は同じ系列データである。また、ある系列データが別の系列データに含まれるという場合は、順序を保持したまま含まれているとする。例えば、＜打ち合わせ予約，好評＞は、＜打ち合わせ予約，（打ち合わせ，好評）＞に含まれている。しかし、＜打ち合わせ，好評＞は、＜（打ち合わせ，好評）＞にも＜好評，打ち合わせ＞にも含まれてはいない。また、同一順序位置を有する複数項目を１つとして数えるやり方で、系列データ内に含まれる項目を数え上げたときの項目数をその系列データの「系列長」と称する。例えば、＜問い合わせ，打ち合わせ予約，（打ち合わせ，好評）＞は、系列長３である。
【００２０】
［系列パターンおよび系列データ制約］
本明細書において「系列パターン」とは、予め指定されている閾値より大きい支持度をもつ系列データのことである。「支持度」とは、解析対象の系列データ数に占める、着目している系列データを含んでいる解析対象系列データの数のことを指す。例えば、着目している系列データが＜開発＞、解析対象系列データが＜受注，開発＞、＜開発，受注，開発＞、＜受注＞の３つであるとき、＜開発＞を含んでいる解析対象系列データは２つであるから、支持度は２／３となる。また、ここで予め指定されている閾値のことを「最小支持度」と称する。また、最小支持度を越える支持度をもつことを「頻出」と判断する基準とする。
【００２１】
系列データを制約系列データとして一つあるいは複数指定したとき、抽出される系列パターンはいずれかの制約系列データを含んでいなければならないという制約を「系列データ制約」と称する。例えば、制約系列データとして＜問い合わせ，受注＞が指定されたとき、頻出系列データとして＜問い合わせ，受注，納入＞と＜問い合わせ，納入＞が発見されたとき、前者は系列データ制約を満たしているが後者は系列データ制約を満たしていないので、前者のみが系列パターンとして抽出される。また、系列データ制約は、次の参考文献に記載のような制約と組み合わせて用いることも可能である。
【００２２】
（参考文献１） Jiawiei Han, Micheline Kamber, “Data Mining Concepts and Techniques”, MORGAN KAUFMANN PUBLISHERS, 2001  
（参考文献２） Raymond T. Ng, Laks V. S. Lakshmanan, Jiawei Han, Alex Pang, “Exploratory Mining and Pruning Optimizations of Constrained Associations Rules”   
（参考文献３） Jian Pei, Jiawiei Han, Wei Wang, “Mining Sequential Patterns with Constraints in Large Databases”
（第一の実施形態）
図３は、本発明に係わる系列パターン抽出装置の概略構成図である。以下、図３に基づいて、処理の概要と各構成部の関係を説明する。
【００２３】
系列データ入力部１は、外部からの情報を系列パターンの抽出がなされる解析対象の系列データとして入力する。上記の機能を有するならば、入力手段は用途に応じて最適な選択をすることが可能であり、キーボード、マウス、ペン型入力装置、あるいはセンサーでもよい。
【００２４】
系列データ記憶部２は、系列パターンの抽出がなされる系列データを記憶する。系列データは予め記憶されている場合もあるし、系列データ入力部１から入力された系列データを記憶する場合もある。上記の機能を有するならば、記憶手段および記憶媒体は用途に応じて最適な選択をすることが可能であり、データベースを用いてもよいし、テキストデータを用いてもよいし、あるいは各アプリケーションに特化されたフォーマット形式のデータを用いてもよい。
【００２５】
制約系列データ記憶部３は、系列データ記憶部２に記憶されている系列データ、もしくは、系列データ入力部１から入力された系列データ、もしくはその双方の系列データのうち、抽出される系列パターンに必ず含まれなければならない系列データを制約系列データとして記憶する。さらに、１系列長パターン抽出部５もしくは系列パターン抽出部６により指定された、系列長２以上の系列パターンを生成する処理において不要となる系列データを削除する。上記の機能を有するならば、系列データ記憶部２と同様に、記憶手段および記憶媒体は用途に応じて最適な選択をすることが可能である。
【００２６】
制約含有系列データ記憶部４は、系列データ記憶部２に記憶されている系列データ、もしくは、系列データ入力部１から入力された系列データ、もしくはその双方の系列データのうち、系列パターンを抽出するのに必要となる系列データのみを制約含有系列データとして記憶する。
【００２７】
１系列長パターン抽出部５もしくは系列パターン抽出部６により指定された、系列長が２以上の系列パターンを生成する処理において不要となる系列データは、削除される。上記の機能を有するならば、系列データ記憶部２と同様に、記憶媒体は用途に応じて最適な選択をすることが可能である。
【００２８】
１系列長パターン抽出部５は、制約含有系列データ記憶部４より系列データを取り出し、系列長１の系列パターン候補を生成し、系列パターンを抽出する。
【００２９】
系列パターン抽出部６は、制約系列データ記憶部３、制約含有系列データ記憶部４、系列パターン候補記憶部７、および非頻出系列データ記憶部８から系列データを取り出し、系列パターンを抽出する。
【００３０】
系列パターン候補記憶部７は、１系列長パターン抽出部５もしくは系列パターン抽出部６により生成された系列パターン候補を記憶する。さらに、１系列長パターン抽出部５もしくは系列パターン抽出部６により指定された系列データを削除する。上記の機能を有するならば、系列データ記憶部２と同様に、記憶手段および記憶媒体は用途に応じて最適な選択をすることが可能である。
【００３１】
非頻出系列データ記憶部８は、系列パターン抽出部６により生成された非頻出系列データを記憶する。上記の機能を有するならば、系列データ記憶部２と同様に、記憶手段および記憶媒体は用途に応じて最適な選択をすることが可能である。
【００３２】
系列パターン記憶部９は、１系列長パターン抽出部５もしくは系列パターン抽出部６において抽出された系列パターンを記憶する。上記の機能を有するならば、系列データ記憶部２と同様に、記憶手段および記憶媒体は用途に応じて最適な選択をすることが可能である。
【００３３】
系列パターン出力部１０は、１系列長パターン抽出部５もしくは系列パターン抽出部６において抽出された系列パターンを出力する。上記の機能を有するならば、出力装置は用途に応じて最適な選択をすることが可能であり、ディスプレイ、プリンタ、あるいは携帯端末機器でもよい。また、上記の機能を有するならば、出力方法は用途に応じて最適な選択をすることが可能であり、一括出力、逐次出力、あるいは、支持度や信頼度に応じた整列出力などが想定される。
【００３４】
本発明は、以上のような構成要素を有する系列パターン抽出装置としてコンピュータを機能させるプログラムとして実施することができる。この場合、本発明に係るプログラムは、コンピュータ内のプログラム記憶装置に格納される。プログラム記憶装置は、例えば不揮発性半導体記憶装置や磁気ディスク装置等からなる。上記プログラムが図示しないＣＰＵからの制御でランダムアクセスメモリ（ＲＡＭ）に読み込まれ、同ＣＰＵにより実行されることにより、コンピュータを本発明に係る系列パターン抽出装置として機能させることができる。なお、このコンピュータには、各種コンピュータ資源を管理し、グラフィカルユーザインタフェース（ＧＵＩ）等を提供するオペレーティングシステムも導入されている。
【００３５】
図４は、本発明の第一の実施形態に係わる系列パターン抽出の処理手順を示すフローチャートである。以下、図４を参照しながら系列パターン抽出の処理手順を説明する。
【００３６】
まず、ステップ１（系列データ準備）では、解析対象の系列データと制約系列データを準備する。必要とされる系列データが、系列データ記憶部２にも制約系列データ記憶部３にも存在しない場合は、不足している解析対象の系列データと制約系列データを系列データ入力部１から入力する。図１は解析対象の系列データの例を示し、図２は制約系列データの例を示している。以下では、図２の制約系列データのいずれかを含み、最小支持度４０％以上となる頻出系列データを図１の系列データ集合から系列パターンとして抽出する処理を例に挙げて説明する。
【００３７】
次に、ステップ２（不要系列データ削除）では、解析対象である系列データの集合から、いずれかの制約系列データを含む系列データのみを取り出し、制約含有系列データとして制約含有系列データ記憶部４に記憶させる。どの制約系列データも含まない系列データから系列データ制約を満たす系列パターンを抽出することはできないことから、このステップが有効である。ここで、制約含有系列データの各々がどの制約系列データを含んでいるかという情報を記憶させておくことで、後のステップ５において処理量を削減することができる。ステップ２以降では、制約含有系列データのみを解析対象とする。また、いずれの制約含有系列データにも含まれていない制約系列データを制約系列データ集合から削除する。図５は、制約含有系列データの例である。図１の識別番号５の系列データはいずれの制約系列データも含んでいないため、図５の制約含有系列データには含まれていない。また、図２の制約系列データ＜（問い合わせ，不評），納入＞は、いずれの制約含有系列データにも含まれていないので、制約系列データ集合から削除され、図６の制約系列データ集合が得られる。
【００３８】
次に、ステップ３（１系列パターン候補生成）では、各制約含有系列データから１系列の部分集合を取り出し、制約含有系列データにおける出現回数から支持度をもとめ、その支持度が最小支持度以上となる１系列データを１系列パターン候補として抽出する。図７は、図５の制約含有系列データ集合から取り出した１系列データを示している。系列データの右に記されているのは、各１系列データを含んでいる制約含有系列データがいくつ存在しているかを数え上げた数である。例えば、＜検討＞は、図５の識別番号２、３、４、６の系列データに含まれているので４回とする。制約含有系列データの同一系列データ中に何度同じ系列データが出現しても１回と数える。例えば、図５の識別番号６の系列データにおいて、＜検討＞は２つ含まれているが、＜検討＞の出現回数は２回ではなく１回と考える。この例において、最小支持度４０％以上であるためには３回以上出現している必要がある。図８は、図７の１系列データ集合から、出現回数３未満の１系列データを取り除いた１系列データ集合である。この系列データ集合を系列パターンとなり得るという意味で「１系列の系列パターン候補集合」と称する。系列パターンは、必ず系列パターン候補集合に含まれる系列データから構成される。
【００３９】
次に、ステップ５（不要系列データ削除）では、ステップ３もしくはステップ４の結果を踏まえて、これ以降の系列パターン抽出処理に不要な制約系列データと制約含有系列データをそれぞれ制約含有系列データ集合と制約系列データ集合から取り除く。不要な制約系列データと判断される条件は以下の二つである。
【００４０】
［不要制約系列データ条件］
（ａ）  ステップ３もしくはステップ４で非頻出とされた系列データを含む
（ｂ）  系列パターン候補集合の系列データに、制約系列データのいずれの項目も含まれない
図９は、ステップ３において非頻出とされた１系列データ＜問い合わせ＞を含む制約系列データ＜（問い合わせ，好評），納入＞を取り除いた制約系列データ集合の例である。さらに、取り除かれた制約系列データのみしか含んでいない制約含有系列データはこれ以降の処理には不要であるから、制約含有系列データ集合から取り除く。図１０は、図５の制約含有系列データから、＜（問い合わせ，好評），納入＞のみしか制約系列データを含んでいない識別番号１の系列データを取り除いた制約含有系列データ集合の例である。
【００４１】
次に、ステップ６（系列パターン候補再計数）では、ステップ５で制約含有系列データの削除が行われたとき、再度、系列パターン候補集合内の系列データの出現回数を数え上げ、最小支持度未満の出現頻度となる系列データを系列候補集合から削除する。ステップ５で不要な系列データが取り除かれることによって、系列パターン候補集合に含まれる系列データの中から、出現頻度が最小支持度未満となるものが現れる可能性がある。最小支持度未満となる可能性のある系列パターン候補の系列データは以下の二つの条件を満たしている。
【００４２】
［再計数条件］
（ａ）  ステップ５で削除された制約含有系列データの部分集合である
（ｂ）  出現回数  ＜  最小支持度を満たす出現回数  ＋  削除制約含有系列データ数
図８の系列パターン候補集合の場合、図５の識別番号１の制約含有系列データの部分集合であり、かつ、出現回数４未満の系列データを再度数え上げる。図１１は、再度出現回数の計数を行った結果である。いずれも支持度が最小支持度より小さいので系列パターン候補集合から取り除かれる。図１２は、再度の出現回数計数により、出現頻度が最小支持度を下回った系列データを取り除いた系列パターン候補集合の例である。
【００４３】
次に、ステップ７（系列パターン抽出）では、系列パターン候補集合の系列データのうち、制約系列データを含んでいるものを系列パターンとして抽出する。抽出された系列パターンは、系列パターン記憶部９に記憶されてもよいし、系列パターン出力部１０から出力されてもよい。この例では、制約系列データの系列長が２であるため、１系列の系列パターンは何も抽出されない。
【００４４】
ステップ７が終了した時点における系列パターン候補集合が空でなければ、ステップ４からステップ７までの抽出処理を系列パターン候補集合が空になるまで続ける。この例では、図１２にあるように系列パターン候補集合が空ではないから、ステップ４に進む。
【００４５】
ステップ４（系列パターン候補生成）では、非頻出系列データ集合の生成に加え、非頻出系列データ集合による枝刈り、出現頻度計数および系列データ制約による枝刈りを随時行いながら、系列パターン候補集合の生成を行う。系列パターン候補集合の生成では、既に生成されている系列パターン候補集合の自己結合により系列長を延長して複数の新たな系列パターン候補集合を生成する。系列長の延長単位は、例えば１である。系列パターン候補集合の自己結合によって得られた系列データの支持度が最小支持度以上であり、かつ、系列データ制約による枝刈りで削除されなければ、その系列データはその系列長の系列パターン候補となる。
【００４６】
まず、系列長が１ほど大きい系列パターン候補の集合を生成するために、系列パターン候補集合同士で自己結合を行う。図１３は、図１２の１系列パターン候補集合同士を自己結合させた結果である。「自己結合」とは、同じ系列データ集合同士で組み合わせを生成する処理である。１系列データの自己結合では、系列パターン候補集合に含まれる各１系列データを組み合わせることにより２系列データを生成すればよい。例えば、＜開発＞と＜納入＞からは、＜開発，納入＞と＜納入，開発＞とが生成される。同一項目が連続して現れる系列パターンも抽出したい場合には、同一系列データ同士についても自己結合処理を行うようにする。例えば、＜納入＞同士を自己結合させると＜納入，納入＞となる。図１３は、同一項目が連続して現れる場合も考慮した自己結合を行った例である。
【００４７】
系列長が２以上の系列パターン候補集合同士の自己結合では、最後の項目を除く全ての項目が一致する系列データ同士において、互いに、一方の最後の項目を他方の最後の項目に付加する。例えば、＜開発，納入＞と＜開発，受注＞の自己結合では、＜開発，納入，受注＞と＜開発，受注，納入＞が生成される。なお、＜開発，納入＞と＜納入，開発＞では、最後の項目を除く項目が一致していないので、３系列データは生成されない。また、同一項目が連続して現れる系列パターンも抽出したい場合、同一系列データ同士についても自己結合処理を行う。例えば、＜開発，納入＞同士を自己結合すると＜開発，納入，納入＞となる。
【００４８】
次に、自己結合により生成された全ての系列データについて支持度（出現頻度）をもとめることは処理量の増大を招くことから、系列データ制約を満たす系列パターンを生成する可能性のある系列パターン候補のみの出現頻度をもとめる。そして、系列データ制約を満たす系列パターンを生成する可能性がないと判断された系列パターン候補は即座に系列パターン候補集合から削除する。支持度が最小支持度以上であるという頻出条件に加えて、系列データ制約を満たす系列パターンを生成する可能性のある系列パターン候補であるためには、以下三つの条件のうちいずれかを満たせばよい。
【００４９】
［系列パターン候補条件］
（ａ）  いずれかの制約系列データを、その項目の順序を含め、完全に含んでいる
（ｂ）  最後の項目を除く項目と順序を含めて一致する制約系列データの項目を、その制約系列データから取り除いた後に残った全ての項目が、最後の項目を除く全ての項目が互いに一致する系列パターン候補集合におけるいずれかの候補の最後の項目に含まれる
（ｃ）  最後の項目を除く全ての項目が一致する系列パターン候補集合の中に、上記（ａ）、（ｂ）のいずれかの条件を満たす系列データが存在する
系列パターン候補条件をみたさない系列パターン候補は、系列データ制約を満足しない系列パターン、すなわち制約系列データを含まない系列パターンしか生成し得ないと言うことができる。系列パターン候補条件は、系列パターン候補を成す系列データと制約系列データとの間で項目の包含関係を規定する。
【００５０】
まず、上記系列パターン候補条件（ａ）、（ｂ）が満たされているかを判定し、もし満たされていないならば、条件（ｃ）が満たされているかを判定し、該当する系列データ集合を、頻度計数を行うまでもなく系列パターン候補集合から削除する。系列パターン候補集合に含まれる系列データを、系列パターン候補条件を満たさないことを理由に系列パターン候補集合から削除することを系列データ制約による「枝刈り」と称する。
【００５１】
例として、まず、図１４のブロック１について考える。これは、最後の項目を除いた全ての項目＜（顧客要望，好評）＞が互いに一致する２系列パターン候補の集合である。まず、２系列パターン候補集合に含まれる＜（顧客要望，好評），納入＞は、制約系列データ＜（顧客要望，好評），納入＞を含んでいるので系列パターン候補条件（ａ）を満たす。このとき、＜（顧客要望，好評），納入＞を除く、ブロック１の全ての系列データは系列パターン候補条件（ｃ）を満たす。したがって、＜（顧客要望，好評），納入＞の支持度が最小支持度以上であれば、ブロック１の全ての系列データは系列データ制約を満たす系列パターンを生成する可能性があると判断される。
【００５２】
次に、＜（顧客要望，好評），納入＞の支持度（出現頻度）が最小支持度未満である場合を考える。最後の項目を除く項目と順序を含めて一致する制約系列データの項目＜（顧客要望，好評）＞をその制約系列データ＜（顧客要望，好評），納入＞から取り除いた後に残った部分集合としての１系列項目＜納入＞が、最後の項目を除く全ての項目が一致するいずれかの系列パターン候補の最後の項目に含まれてはいない。このとき、ブロック１の全ての系列データは系列データ制約を満たす系列パターンを生成することはないから、頻度計数を行うまでもなく系列パターン候補集合から削除することができる。
【００５３】
次に、図１４に示すブロック２を例として考える。これは、最後の項目を除いた全ての項目＜検討＞が互いに一致する２系列パターン候補の集合である。まず系列パターン候補条件（ａ）を満たす系列データは存在しない。次に、最後の項目を除く項目＜検討＞と一致する制約系列データの項目は存在しないので何も取り除かれない制約系列データ＜（顧客要望，好評），納入＞の全ての項目＜（顧客要望，好評）＞と＜納入＞が、最後の項目を除く全ての項目が互いに一致する＜検討，納入＞と＜検討，（顧客要望，好評）＞の系列パターン候補の最後の項目に含まれているので、系列パターン候補条件（ｂ）を満たす。同様に、制約系列データ＜（顧客要望，不評），納入＞に関しても、＜検討，納入＞と＜検討，（顧客要望，不評）＞の最後の項目が＜（顧客要望，不評）＞と＜納入＞を含んでいるので系列パターン候補条件（ｂ）を満たす。
【００５４】
したがって、＜検討，納入＞と＜検討，（顧客要望，好評）＞の支持度が最小支持度以上であれば、＜（顧客要望，好評），納入＞の系列データ制約を満たす系列パターンを生成する可能性が、ブロック２の全ての系列データにあると判断される。同様に、＜検討，納入＞と＜検討，（顧客要望，不評）＞の支持度が最小支持度以上であれば、＜（顧客要望，不評），納入＞の系列データ制約を満たす系列パターンを生成する可能性が、ブロック２の全ての系列データにあると判断される。
【００５５】
なお、＜検討，納入＞の支持度が最小支持度未満であるか、もしくは、＜検討，納入＞の支持度が最小支持度以上であっても、＜検討，（顧客要望，好評）＞と＜検討，（顧客要望，不評）＞の支持度が最小支持度未満であれば、ブロック２の全ての系列データは頻度計数を行うまでもなく系列パターン候補集合から削除することができる。系列パターン候補条件を満たしていない場合は、即座に系列パターン候補集合から削除することができるが、系列パターン候補条件を満たしていても非頻出の可能性はある。この場合、頻度計数が必要である。
【００５６】
上記で述べた性質を利用した系列パターン候補生成の手順を図１５のフローチャートを参照しながら説明する。
【００５７】
まずステップ４−１（系列パターン候補分類）では、系列データを処理単位ごとに参照しやすくするために、自己結合により生成された多数の系列パターン候補を分類することにより複数の系列パターン候補集合を得る。一つの系列パターン候補集合において、複数の系列パターン候補を表す各々の系列データは、最後の項目を除く全ての項目が互いに一致している。
【００５８】
ただし、系列パターン候補の記憶時に、系列パターン候補を項目の並びに従ってハッシュ木、トライ、Ｂ木等の木に格納しておくならば、ステップ４−１は不要である。図１６は、系列パターン候補を木に格納したときの例である。例えば、ルートノードの＜（顧客要望，好評）＞が指すポインタから子ノードを辿り＜不評＞を発見した場合、系列パターン候補に＜（顧客要望，好評），不評＞が含まれていることがわかる。また、系列データの最初２項目に＜（顧客要望，好評），不評＞を含む系列長３の系列パターン候補を得るには、＜（顧客要望，好評），不評＞より辿ることのできる子ノードに含まれる項目を全て調べればよい。
【００５９】
次にステップ４−２（制約含有チェック）では、分類された系列パターン候補の集合ごとに、最後の項目を除く各項目と制約系列データの各項目が順序を含めて一致しているかを調べる。
【００６０】
次に、ステップ４−３（チェック項目抽出）では、各制約系列データから、ステップ４−２で一致していることが判明した項目を取り除き、さらに１系列データの部分集合に分解して項目を抽出する。
【００６１】
次にステップ４−４（頻度計数なしの枝刈り）では、分類された系列データごとに枝刈りを行い、枝刈りで削除されなかった系列データに関して、ステップ４−３で生成された全ての項目が最終１要素に含まれているかを順次調べ、系列パターン候補条件（ａ）、（ｂ）、（ｃ）を満たさないものを系列パターン候補集合から削除する。
【００６２】
ここでの枝刈り処理は、系列パターン候補の部分集合に非頻出の系列データが含まれているときに、頻度計数をする前にその系列データを系列パターン候補集合から削除する処理である。非頻出の系列データを含む系列データが頻出と判断されることはないため、枝刈り処理を行うことで、頻度計数を行わずに非頻出の系列データを系列パターン候補集合から削除することができる。
【００６３】
従来の枝刈り処理では、枝刈り処理のなされている系列データの部分集合のいずれかが系列長の１小さい系列パターン候補集合に含まれていないとき、その系列データを系列パターン候補集合から削除するのが一般的である。しかし、仮に頻出であっても系列データ制約による枝刈りによって系列パターン候補集合から削除されている系列パターン候補が存在するので、従来の枝刈り処理をそのまま利用すると頻出であっても非頻出とみなされる可能性がある。そこで、頻度計数によって支持度が最小支持度未満と判断された系列長が２以上の系列データを非頻出系列データとして非頻出系列データ記憶部８に記憶しておき、非頻出系列データを部分集合として含む系列データを系列パターン候補集合から削除することで枝刈り処理を行う。非頻出系列データは、系列パターン候補と同様に、ハッシュ木やトライ等に格納することで、効率的に参照することができる。
【００６４】
次にステップ４−５（頻度計数ありの枝刈り）では、ステップ４−４の処理を経た系列パターン候補集合に対して、分類された系列データごとに頻度計数を行い、支持度（出現頻度）が最小支持度以上の系列データに関して、ステップ４−３で生成された全ての項目が最終１要素に含まれているかを順次調べ、系列パターン候補条件（ａ）、（ｂ）、（ｃ）を満たさないものを系列パターン候補集合から削除する。また、系列パターン候補集合において、ある系列データが他の異なる系列データに含まれるとき、（後者の）含む系列データが頻出であれば、（前者の）含まれる系列データも頻出である。このとき、含まれる系列データが、制約系列データを含んでいなければ、頻度計数を行わなくともよい。例えば、＜顧客要望，受注＞は＜（顧客要望，好評），受注＞に含まれている。このとき、＜（顧客要望，好評），受注＞が頻出であれば、＜顧客要望，受注＞は頻出であると判断できるから頻度計数を必要としない。
【００６５】
系列パターン候補生成においては、分類された系列データ集合を次の順序で処理する。
【００６６】
（１）制約系列データ集合に含まれている
（２）制約系列データ集合において出現頻度が高い
（３）同一順序位置の項目集合数が多い
したがって、上記の順序で各系列データを参照するのに適したデータ構造に、系列パターン候補が格納されていることが望ましい。例えば、系列パターン候補を格納するデータ構造として、ハッシュ木やＢ＋木のような木を採用した場合、ノード内に格納される各項目は、上記のような基準で整列されているとよい。
【００６７】
系列パターン候補生成について、より具体的な例を示しながら説明する。 
図１３に示す系列パターン候補集合は既にステップ４−１の処理を終えたものである。 
図１７は、図１３の系列データ集合に対して、ステップ４−５の処理を行った結果を示している。ブロック内で上位の系列データから順に頻度計数が行われるものとする。系列データの右の数値は出現回数であり、出現頻度計数が行われた系列データであることを示している。系列データの右に「×」が記されているものは、頻度計数ありの枝刈りが行われて系列パターン候補集合から削除されたものである。系列データの右に「□」が記されているものは、頻度計数の結果、非頻出と判断されたものである。
【００６８】
例えば、ブロック１では、＜（顧客要望，好評），納入＞が頻出であるため、系列パターン候補条件（ａ）が満たされ、ブロック１の全ての系列データが系列パターン候補条件（ｃ）を満たす。したがって、ブロック１の全ての系列データは頻度計数が行われている。
【００６９】
ブロック３では、＜不評，（顧客要望，好評）＞と＜不評，（顧客要望，不評）＞が非頻出であるため、系列パターン候補条件が満たされず、ブロック３の系列データ集合は系列パターン候補集合から削除される。
【００７０】
なお、系列長２の系列パターン候補生成時には、まだ非頻出系列データ集合が作成されていないので、ステップ４−５の枝刈りのみが行われている。すなわち、系列長が３以上の新たな候補を生成したときには、ステップ４−４と４−５の枝刈りを両方実施する。図１８は頻度計数が行われ、非頻出と判断された系列データである。また、図１９は、系列長２の系列パターン候補をまとめたものである。
【００７１】
頻度計数なしの枝刈りを含む例として、図２２の系列長３の系列パターン候補生成を考える。表記は図１７で用いられているものと同じであるが、それに加えて、系列データの右に「△」が記されているものは、非頻出系列データを部分集合として含んでいたために系列パターン候補集合から削除された系列データである。例えば、ブロック８では、＜受注，（納入，好評），納入＞の部分集合である＜（納入，好評），納入＞が、図１８の非頻出系列データに含まれているので、系列パターン候補集合から削除される。＜受注，（納入，好評），納入＞が削除されると、系列パターン候補条件（ｂ）が満たされないので、ブロック８の系列データ集合は、系列パターン候補集合から削除される。
【００７２】
図４に示したように、ステップ４を終えると、ステップ５、ステップ６、ステップ７に順次進む。図１９の系列パターン候補集合にステップ５の処理を施した結果、不要制約系列データ条件を（ａ）、（ｂ）ともに満たさないので、制約含有系列データも、制約系列データも変化はない。したがって、ステップ６における頻度の再計数も行われない。図２０は、図１９の系列パターン候補集合に対しステップ７の処理を施した結果を示しており、これは系列長２の系列パターンに相当する。
【００７３】
ステップ７を終えたときに、系列パターン候補集合が空であれば全ての系列パターンが抽出されたものと判断し、系列パターン抽出処理を終える。系列パターン候補集合が空でない場合は、ステップ４に戻り同様のステップを系列パターン候補集合が空になるまで続ける。図２１乃至図３６は、以上のステップを順次繰り返し、全ての系列パターンを抽出するまでの過程を示したものである。図３６は、抽出された系列パターンをまとめたものである。
【００７４】
本実施形態では、各系列データの最後の項目を除いた全ての項目が互いに一致する系列データ同士を自己結合させることにより系列長を延長して系列パターン候補を生成する系列パターン候補生成方法を採用した場合を一例として挙げたが、本発明は、別の系列パターン候補生成方法に対しても有効である。例えば、各系列データの最初の１項目を除いた全ての項目が互いに一致する系列データ同士を自己結合させることで、系列長の１大きい系列パターン候補を生成する系列パターン候補生成方法に関しても有効である。また、本発明は、最初の１項目を除く全ての項目と最後の項目を除く全ての項目が互いに一致する２つの系列データに関して、前者に対し後者の最後の項目を付加することで系列長の１大きい系列パターン候補を生成する系列パターン候補生成方法に関しても有効である。
【００７５】
以上の系列パターン抽出処理は、複数プロセッサによる並列処理や複数台の計算機による分散処理を行うことでさらに好適な結果を得ることができる。特に、ステップ３やステップ４における頻度計数は、系列パターン候補ごとに並列、分散させて独立に行うことができる。
【００７６】
以上説明したように、第一の実施形態の系列パターン抽出装置によれば、系列データ制約を満たさない系列パターンしか生成しない系列パターン候補が、随時に、系列パターン候補集合から削除されることから、不要な処理を大幅に削減し処理時間を短縮できるとともに、指定された系列データを含む系列パターンを漏れなく抽出することが可能となる。
【００７７】
（第二の実施形態）
図３７は、本発明に係わる系列パターン抽出装置の概略構成図である。以下、図３７に基づいて、処理の概要と各構成部の関係を説明する。
【００７８】
系列データ入力部２１は、外部からの情報を系列パターンの抽出がなされる解析対象の系列データとして入力する。上記の機能を有するならば、入力手段は用途に応じて最適な選択をすることが可能であり、キーボード、マウス、ペン型入力装置、あるいはセンサーでもよい。
【００７９】
系列データ記憶部２２は、系列パターンの抽出がなされる系列データを記憶する。系列データは予め記憶されている場合もあるし、系列データ入力部２１から入力された系列データを記憶する場合もある。上記の機能を有するならば、記憶手段および記憶媒体は用途に応じて最適な選択をすることが可能であり、データベースを用いてもよいし、テキストデータを用いてもよいし、あるいは各アプリケーションに特化されたフォーマット形式のデータを用いてもよい。
【００８０】
制約系列データ記憶部２３は、系列データ記憶部２２に記憶されている系列データ、もしくは、系列データ入力部２１から入力された系列データ、もしくはその双方に含まれる系列データのうち、抽出される系列パターンに必ず含まれなければならない系列データを制約系列データとして記憶する。さらに、系列データ分解部２４により指定された、系列パターンを生成する処理において不要となる系列データを削除する。上記の機能を有するならば、系列データ記憶部２２と同様に、記憶手段および記憶媒体は用途に応じて最適な選択をすることが可能である。
【００８１】
系列データ分解部２４は、系列データ入力部２１、系列データ記憶部２２、制約系列データ記憶部２３より系列データを取り出し、解析対象系列データを分解し、部分系列データを作成する。
【００８２】
部分系列データ記憶部２５は、系列データ分解部２４によって生成された部分系列データを記憶する。
【００８３】
制約含有系列データ記憶部２６は、制約系列データ記憶部２３に格納されている各制約系列データと解析対象系列データを関連付けて記憶する。いずれの制約系列データも含んでいない解析対象系列データは、系列パターン抽出処理で使用されないので記憶されない。上記の機能を有するならば、系列データ記憶部２２と同様に、記憶媒体は用途に応じて最適な選択をすることが可能である。
【００８４】
部分系列パターン抽出部２７は、部分系列データ記憶部２５より部分系列データを取り出し、部分系列パターンを抽出する。
【００８５】
部分系列パターン記憶部２８は、部分系列パターン抽出部２７において生成された部分系列パターンを記憶する。上記の機能を有するならば、系列データ記憶部２２と同様に、記憶媒体は用途に応じて最適な選択をすることが可能である。
【００８６】
部分系列パターン併合部２９は、制約含有系列データ記憶部２６、制約系列データ記憶部２３、部分系列パターン記憶部２８から系列データを取りだし、制約系列データと部分系列パターンを併合し、系列パターンを抽出する。
【００８７】
系列パターン記憶部３０は、部分系列パターン抽出部２７もしくは部分系列パターン併合部２９において抽出された系列パターンを、記憶する。上記の機能を有するならば、系列データ記憶部２２と同様に、記憶手段および記憶媒体は用途に応じて最適な選択をすることが可能である。
【００８８】
系列パターン出力部３１は、部分系列パターン抽出部２７もしくは部分系列パターン併合部２９において抽出された系列パターンを出力する。上記の機能を有するならば、出力装置は用途に応じて最適な選択をすることが可能であり、ディスプレイ、プリンタ、あるいは携帯端末機器でもよい。また、上記の機能を有するならば、出力方法は用途に応じて最適な選択をすることが可能であり、一括出力、逐次出力、あるいは、支持度や信頼度に応じた整列出力などが想定される。
【００８９】
図３８は、本発明の第二の実施形態に係る系列パターン抽出の処理手順を示すフローチャートである。以下、図３８を参照しながら系列パターン抽出の処理手順を説明する。
【００９０】
まず、ステップ１（系列データ準備）では、解析対象の系列データと制約系列データを準備する。必要とされる系列データが、系列データ記憶部２２と制約データ記憶部に存在しない場合には、不足している解析対象系列データと制約系列データとを、系列データ入力部２１から入力する。また、図１は解析対象の系列データ、図２は制約系列データの例である。これ以降は、図１の系列データ集合から、図２の制約系列データのいずれかを含み、最小支持度４０％以上となる系列パターンを抽出する処理を例として説明する。
【００９１】
次に、ステップ２（系列データ分割）では、制約系列データの項目を境界として、系列データを部分系列に分解する。分割された系列データには、境界とされた制約系列データの項目は含まない。例えば、＜開発＞が制約系列データであるとき、＜受注，開発，運用＞は、＜受注＞と＜運用＞に分解される。分割位置に複数の項目がある場合は、分割位置の項目集合から制約系列データの項目のみを取り除いた項目集合を、分割された系列データの片方だけに含める。分割位置の前、もしくは、後のどちらの系列データに含めるかは予め定めておく。
【００９２】
分割位置の項目集合から制約系列データの項目のみを取り除いた項目集合は、通常の項目とは異なっているものとして扱う。例えば、分割位置の項目集合を分割位置の前の系列データに含めると定め、＜開発＞が制約系列データであるとき、＜トラブル，受注，（開発，トラブル），運用＞は、＜トラブル，受注，＊トラブル＞と＜運用＞に分割される。ここで、分割位置の＜トラブル＞は、通常の＜トラブル＞と異なることを示すために、「＊」を付けて＜＊トラブル＞と表記した。頻度計数時には、＜トラブル＞と＜＊トラブル＞は別の項目として数え上げる。
【００９３】
分割対象となる系列データに、制約系列データの項目が複数含まれているときは、予め最初もしくは最後の項目で分割すると決めておく。これにより、分割の一意性が保たれ、同一項目の重複計数を避けることができる。例えば、最初の項目で分割すると定めているとき、＜開発，納入，開発，納入，運用＞を、制約系列データ＜納入＞で分解する場合、＜開発＞と＜開発，納入，運用＞に分解される。図１の系列データは、ステップ１の手続きに従うと図３９のように分解される。四角形で囲まれている系列データが分解された部分系列データであり、角丸四角形で囲まれている項目が制約系列データの項目である。なお、どの制約系列データにどの系列データが対応しているかを示すために、図３９の分解された系列データの左に識別番号を付記した。解析対象系列データは、各制約系列データに対応付けて、制約含有系列データとして記憶される。例えば、図３９では、制約系列データ＜（顧客要望，好評），納入＞に対応している制約含有系列データは、識別番号２、６、７の系列データのみである。
【００９４】
次に、ステップ３（不要系列データ削除）では、系列パターンが抽出され得ない制約系列データを制約系列データ集合から削除する。図３９の分割された系列データにおいて、＜（問い合わせ，好評），納入＞に対応する部分系列データは１つしかなく、＜（問い合わせ，不評），納入＞に対応する部分系列データはひとつもない。そこで、＜（問い合わせ，好評），納入＞と＜（問い合わせ，不評），納入＞はこれ以降の処理で不要となるから、制約系列データ集合から削除する。図３９は、ステップ２の手続きに従うと、図４０となる。
【００９５】
次に、ステップ４（部分系列パターン生成）では、分割された系列データごとにもとめられた系列パターンを部分系列パターンとして抽出する。各部分系列データの系列パターン抽出処理は、独立に実行することができる。また、系列パターン抽出方法は、頻出系列データを抽出する手法であればなんでもよく、部分系列データの性質や計算機資源、分析者の目的等に応じて最適な手法を選択できる。１つの部分系列パターンと制約系列データを組み合わせた系列データは系列パターンとして抽出される。その際、系列パターンの支持度は、部分系列パターンの支持度と同じである。また、制約系列データそのものも系列パターンとして抽出され、その出現回数は最大部分系列データ数と同じである。例えば、＜（顧客要望，不評），納入＞の出現回数は、図４０のブロック６、８、１０のうち、系列データ数が最大のブロック８の系列データ数３と等しい。
【００９６】
図４１乃至図４９は、各々の部分系列データに対して、アプリオリ性を利用した系列パターン抽出方法を適用した例である。上述したように、「アプリオリ性」とは、系列データのいずれの部分集合についても、その頻度は、当該系列データの頻度よりも高くなることはない、という性質である。
【００９７】
図４１は、各部分系列データごとに、系列長１の系列データの出現頻度を数え上げた結果を示している。例えば、図４１のブロック１における＜受注＞は、図４０のブロック１にある部分系列データに３回出現している。図４２は、各部分系列データごとに、頻出の系列長１の系列データを示したものである。図４３は、各部分系列において、系列長１の系列データ同士の自己結合を行って系列長２の系列データを生成し、頻度計数を行った結果である。図４４は、出現頻度が最小支持度以上の系列データである系列パターン候補のみを示したものである。図４５は、最後の項目以外が一致する系列長２の系列データ同士において、最後の項目を除く系列データの最後に最後の項目の組み合わせを付加するやり方で自己結合させて、系列長３の系列データを生成した例である。例えば、＜検討，好評＞と＜検討，開発＞は、＜検討＞が一致している。ここで、最後の項目＜好評＞と＜開発＞の組み合わせ＜好評，開発＞、＜開発，好評＞の２つを＜検討＞に付加すると、＜検討，好評，開発＞、＜検討，開発，好評＞と２つの系列長３の系列データが生成される。なお、ここでは、同じ項目が連続することが可能な自己結合方法を採用している。図４６は、枝刈りされた系列長３の系列データの出現頻度を計数した例である。枝刈りは、系列データが、系列長の１小さい系列パターン候補から構成されていないときに、頻度計数を行わずに非頻出系列データとして系列パターン抽出候補から取り除かれる処理である。例えば、＜検討，開発，開発＞は、＜開発，開発＞が系列長２の系列パターン候補でないから、枝刈りされ、頻度計数を行わずに系列パターン候補から削除される。図４７は、系列長３までの系列パターン候補を示した例である。図４８は、系列長２の系列データにおける自己結合処理と同様に、系列長３の系列データ同士を自己結合させて系列長４の系列データを生成した例である。この系列長４の系列データは枝刈りによって非頻出と判断されるので、部分系列パターン抽出は終了となる。図４９と図５０は、制約系列データごとに、部分系列パターン抽出処理を終えた時点で抽出された系列パターンをまとめたものである。図５０の＜（顧客要望，不評），納入＞に対応する部分系列パターンは、＜（顧客要望，不評）＞と＜納入＞の間にしか存在しないので、この時点で全ての系列パターンは抽出されている。
【００９８】
次に、ステップ５（部分系列パターン併合）では、個別に抽出された部分系列パターンと制約系列データを併合させて系列パターンを抽出する。併合処理は、制約系列データごとに行うことが可能である。制約系列データと複数の部分系列パターンを組み合わせてなる併合系列データが、ステップ２にて記憶された制約含有系列データに出現する回数を数え上げ、最小支持度以上の支持度を有する併合系列データを系列パターンとして抽出する。図５１は、制約系列データ＜（顧客要望，好評），納入＞に対応する系列パターンをもとめるために、各部分系列パターンを組み合わせて頻度計数を行った結果である。まず、ブロック１の部分系列パターンより、＜受注＞と＜（顧客要望，好評）＞と＜開発＞と＜納入＞を順序を保ったまま組み合わせて、＜受注，（顧客要望，好評），開発，納入＞を生成する。ブロック２は、＜（顧客要望，好評），納入＞に対応する系列含有系列データである。ブロック３は、ブロック２の系列含有系列データにおける、生成された系列データの頻度計数の結果であり、支持度が最小支持度を超えているので系列パターンとして抽出される。図５２は、抽出された系列パターン全てをまとめたものである。
【００９９】
以上の系列パターン抽出処理は、複数プロセッサによる並列処理や複数台の計算機による分散処理を行うことでさらに良好な結果を得ることができる。特に、ステップ４における部分系列パターン抽出は、分割された系列データごとに行うことが可能であり、並列処理や分散処理に適している。
【０１００】
以上説明したように、第二の実施形態の系列パターン抽出装置によれば、系列データ制約を満たす系列データのみから系列パターンを抽出することから、不要な処理を大幅に削減し処理時間を短縮できるとともに、指定された系列データを含む系列パターンを漏れなく抽出することが可能となる。
【０１０１】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１０２】
【図１】解析対象の系列データ集合（営業日報データ）を示す図
【図２】制約系列データ集合を示す図
【図３】本発明の第一の実施形態に係る系列パターン抽出装置を示すブロック図
【図４】本発明の第一の実施形態に係わる系列パターン抽出の処理手順を示すフローチャート
【図５】制約含有系列データ集合を示す図
【図６】制約系列データ集合を示す図
【図７】１系列データを示す図
【図８】１系列パターン候補集合を示す図
【図９】制約系列データ集合を示す図
【図１０】制約含有系列データ集合を示す図
【図１１】再計数対象の１系列パターン候補を示す図
【図１２】再計数後の１系列系列パターン候補集合を示す図
【図１３】１系列パターン候補集合の自己結合を示す図
【図１４】制約による枝刈りを説明するための図
【図１５】本発明の第一の実施形態における系列パターン候補生成の処理手順を示すフローチャート
【図１６】木に格納された系列パターン候補の例を示す図
【図１７】１系列パターン候補集合の自己結合を示す図
【図１８】非頻出系列データ集合を示す図
【図１９】系列長２の系列パターン候補集合を示す図
【図２０】２系列の系列パターンを示す図
【図２１】２系列パターン候補集合の自己結合を示す図
【図２２】３系列パターン候補集合の生成を示す図
【図２３】非頻出系列データ集合を示す図
【図２４】系列長３の系列パターン候補集合を示す図
【図２５】系列長３の系列パターンを示す図
【図２６】系列長３の系列パターン候補の自己結合を示す図
【図２７】系列長４の系列パターン候補の生成を示す図
【図２８】系列長４までの非頻出系列データを示す図
【図２９】系列長４の系列パターン候補集合を示す図
【図３０】系列長４の系列パターンを示す図
【図３１】系列長４の系列パターン候補の自己結合を示す図
【図３２】系列長５の系列パターン候補の生成を示す図
【図３３】系列長５の系列パターン候補を示す図
【図３４】系列長５の系列パターンを示す図
【図３５】系列長６の系列パターン候補の生成を示す図
【図３６】系列パターンを示す図
【図３７】本発明の第二の実施形態に係る系列パターン抽出装置を示すブロック図
【図３８】本発明の第二の実施形態に係る系列パターン抽出の処理手順を示すフローチャート
【図３９】部分系列データを示す図
【図４０】不要な系列データを削除した部分系列データを示す図
【図４１】部分系列パターン抽出（１系列パターン頻度計数）を示す図
【図４２】部分系列パターン抽出（１系列パターン候補）を示す図
【図４３】部分系列パターン抽出（２系列パターン候補の頻度計数）を示す図
【図４４】部分系列パターン抽出（２系列パターン候補）を示す図
【図４５】部分系列パターン抽出（３系列パターン候補の自己結合）を示す図
【図４６】部分系列パターン抽出（３系列パターン候補の頻度計数）を示す図
【図４７】部分系列パターン抽出（３系列パターン候補の頻度計数）を示す図
【図４８】部分系列パターン抽出（４系列パターン候補の自己結合）を示す図
【図４９】系列パターンを示す図
【図５０】系列パターンを示す図
【図５１】部分系列パターン併合を示す図
【図５２】最終的に得られた系列パターンを示す図
【符号の説明】
【０１０３】
１…系列データ入力部；
２…系列データ記憶部；
３…制約系列データ記憶部；
４…制約含有系列データ記憶部；
５…１系列長パターン抽出部；
６…系列パターン抽出部；
７…系列パターン候補記憶部；
８…非頻出系列データ記憶部；
９…系列パターン記憶部；
１０…系列パターン出力部
【図１】
2007041683.tif 000003
【図２】
2007041683.tif 000004
【図３】
2007041683.tif 000005
【図４】
2007041683.tif 000006
【図５】
2007041683.tif 000007
【図６】
2007041683.tif 000008
【図７】
2007041683.tif 000009
【図８】
2007041683.tif 000010
【図９】
2007041683.tif 000011
【図１０】
2007041683.tif 000012
【図１１】
2007041683.tif 000013
【図１２】
2007041683.tif 000014
【図１３】
2007041683.tif 000015
【図１４】
2007041683.tif 000016
【図１５】
2007041683.tif 000017
【図１６】
2007041683.tif 000018
【図１７】
2007041683.tif 000019
【図１８】
2007041683.tif 000020
【図１９】
2007041683.tif 000021
【図２０】
2007041683.tif 000022
【図２１】
2007041683.tif 000023
【図２２】
2007041683.tif 000024
【図２３】
2007041683.tif 000025
【図２４】
2007041683.tif 000026
【図２５】
2007041683.tif 000027
【図２６】
2007041683.tif 000028
【図２７】
2007041683.tif 000029
【図２８】
2007041683.tif 000030
【図２９】
2007041683.tif 000031
【図３０】
2007041683.tif 000032
【図３１】
2007041683.tif 000033
【図３２】
2007041683.tif 000034
【図３３】
2007041683.tif 000035
【図３４】
2007041683.tif 000036
【図３５】
2007041683.tif 000037
【図３６】
2007041683.tif 000038
【図３７】
2007041683.tif 000039
【図３８】
2007041683.tif 000040
【図３９】
2007041683.tif 000041
【図４０】
2007041683.tif 000042
【図４１】
2007041683.tif 000043
【図４２】
2007041683.tif 000044
【図４３】
2007041683.tif 000045
【図４４】
2007041683.tif 000046
【図４５】
2007041683.tif 000047
【図４６】
2007041683.tif 000048
【図４７】
2007041683.tif 000049
【図４８】
2007041683.tif 000050
【図４９】
2007041683.tif 000051
【図５０】
2007041683.tif 000052
【図５１】
2007041683.tif 000053
【図５２】
2007041683.tif 000054