(57)【要約】【課題】射影にかかる処理の効率化を図ることが可能な系列パタン抽出装置及び方法を提供する。【解決手段】系列データを構成するアイテムの配列毎に取得した射影の対象となるアイテムを特定するための射影位置を、当該射影の基点となるアイテムに関連付けて記憶し、系列パタンに対応する前記系列データでのアイテムのうち最後のアイテムを基点として、このアイテムに関連付けて記憶された前記射影位置により特定されるアイテムを前記系列データから抽出する。【選択図】        図２
2009169850.tif 000002
【特許請求の範囲】
【請求項１】
分析対象となるアイテムを順序付けて配列した系列データに対し、前記アイテムを部分的に配列した系列パタンと一致する前記系列データでのアイテムを基点として射影を行うことで、前記系列データから当該系列パタン以降に存在するアイテムを抽出する系列パタン抽出装置であって、
前記系列データを記憶する第１記憶手段と、
前記系列データを構成するアイテムに対し、当該アイテムが基点となった場合に前記系列データから抽出の対象となるアイテムを特定するための射影位置を関連付けて記憶する第２記憶手段と、
前記系列パタンに対応する前記系列データでのアイテムの配列うち、最後のアイテムを基点とし、このアイテムに関連付けて記憶された前記射影位置により特定されるアイテムを前記系列データから抽出する射影手段と、
を備えたことを特徴とする系列パタン抽出装置。
【請求項２】
前記系列データを構成するアイテムが基点とされた場合での前記射影位置をアイテム単位で取得する射影位置取得手段と、
前記射影位置を前記射影の基点となるアイテムに関連付けて前記第２記憶手段に記憶する記憶制御手段と、
を備えたことを特徴とする請求項１に記載の系列パタン抽出装置。
【請求項３】
前記第１記憶手段は、前記系列データを複数記憶し、
頻出か否かの判定基準となる最小支持度を入力する第１入力手段と、
前記射影手段により抽出された前記系列データ毎のアイテムを比較し、同一のアイテム種別において出現回数が前記最小支持度以上となるアイテムが存在するか否かを判定する判定手段と、
前記判定手段により存在すると判定された場合、前記系列パタンを頻出系列パタンとして出力する出力手段と、
を更に備えたことを特徴とする請求項２に記載の系列パタン抽出装置。
【請求項４】
前記射影位置取得手段は、前記系列データにおいて同一の順位に配列されたアイテムに射影する際の射影位置を、同順射影位置として取得することを特徴とする請求項２に記載の系列パタン抽出装置。
【請求項５】
前記系列データは、同一の順位に配列される１又は複数のアイテムを、当該系列データを構成する一連の要素として順序付けて配列した複数のアイテムセットから構成され、
前記射影位置取得手段は、
前記系列データを構成する配列順に前記アイテムセットを順次読み込む読込手段と、
前記読込手段により今回読み込まれたアイテムセットに、前回迄に読み込まれた各アイテムセットとは異なる新たなアイテムが含まれているか否かをアイテムセット毎に判定する判定手段と、
前記判定手段により前回迄に読み込まれたアイテムセットの何れかに前記新たなアイテムが含まれていないと判定された場合、前回迄に読み込まれたアイテムセットに含まれるアイテムのうち、前記新たなアイテムと同一種別のアイテムに対し、今回読み込まれたアイテムセットでの新たなアイテムの順位を前記同順射影位置として関連付けて記憶する同順射影位置記憶手段と、
を備えたことを特徴とする請求項４に記載の系列パタン抽出装置。
【請求項６】
前記同順射影位置記憶手段は、前記判定手段により最小支持度未満と判定された系列パタンでの最後のアイテムに関連付けて記憶された同順射影位置を削除することを特徴とする請求項５に記載の系列パタン抽出装置。
【請求項７】
前記射影位置取得手段は、前記系列データにおいて異なる順位に配列されたアイテムに射影する際の射影位置を、異順射影位置として取得することを特徴とする請求項２に記載の系列パタン抽出装置。
【請求項８】
前記系列データは、同一の順位に配列される１又は複数のアイテムを、当該系列データを構成する一連の要素として順序付けて配列した複数のアイテムセットから構成され、
前記射影位置取得手段は、
前記系列データを構成する配列順に前記アイテムセットを順次読み込む読込手段と、
前記読込手段により今回読み込まれたアイテムセットに含まれる各アイテムの順位を前記異順射影位置として前回読み込まれたアイテムセットに関連付けて記憶するとともに、今回読み込まれたアイテムセットに含まれるアイテムのうち、前回迄に読み込まれたアイテムセットに含まれない新たなアイテムの順位を、前記異順射影位置として当該新たなアイテムを含まないアイテムセットに関連付けて記憶する異順射影位置記憶手段と、
を備えたことを特徴とする請求項７に記載の系列パタン抽出装置。
【請求項９】
前記異順射影位置記憶手段は、前記アイテムセットに関連付けた順位を、当該アイテムセットに共通するアイテムの順位と当該アイテムセットに含まれた各アイテムに固有の順位とに分別して記憶することを特徴とする請求項８に記載の系列パタン抽出装置。
【請求項１０】
前記異順射影位置記憶手段は、前記判定手段により最小支持度未満と判定された系列パタンでの最後のアイテムに関連付けて記憶された異順射影位置を削除することを特徴とする請求項８に記載の系列パタン抽出装置。
【請求項１１】
前記頻出系列パタンの配列を制約する制約条件を入力する第２入力手段を更に備え、
前記射影位置取得手段は、前記制約条件を満たすアイテムの配列から前記射影位置を取得することを特徴とする請求項２に記載の系列パタン抽出装置。
【請求項１２】
分析対象となるアイテムを順序付けて配列した系列データに対し、前記アイテムを部分的に配列した系列パタンと一致する前記系列データでのアイテムを基点として射影を行うことで、前記系列データから当該系列パタン以降に順序付けられたアイテムを抽出する系列パタン抽出装置の系列パタン抽出方法であって、
前記系列パタン抽出装置は、前記系列データを記憶する第１記憶手段と、
前記系列データを構成するアイテムに対し、当該アイテムが基点となった場合に前記系列データから抽出の対象となるアイテムを特定するための射影位置を関連付けて記憶する第２記憶手段と、
を備え、
射影手段が、前記系列パタンに対応する前記系列データでのアイテムの配列うち、最後のアイテムを基点とし、このアイテムに関連付けて記憶された前記射影位置により特定されるアイテムを前記系列データから抽出する射影工程と、
を含むことを特徴とする系列パタン抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同質のアイテムを順序付けて配列した系列データから、特定の系列パタンを抽出する系列パタン抽出装置及び方法に関する。
【背景技術】
【０００２】
多量のデータ群から有用な情報を発見するデータマイニング技術のひとつに、頻出する系列パタンのみを効率的に発見する系列パタンマイニング技術がある。系列パタンマイニング技術では、系列データの集合から、利用者が指定した閾値より多く出現する系列パタン全てを効率的に発見することができる。
【０００３】
この系列パタンマイニング技術は、購買履歴やＤＮＡ配列、健康情報等の順序関係を有するデータの分析やルール生成に広く利用される他、語彙の頻度や出現パタンを利用したテキストマイニングにも用いられている。また、系列パタンマイニング技術は、各系列パタンの頻度を調べる方法に関して、頻出系列パタン候補を生成しながら数え上げる方法（以下、第１の方法という）と、データベースを射影しながら数え上げる方法（以下、第２の方法）とに大別することができる。
【０００４】
第１の方法を用いた技術としては、例えば、特許文献１や非特許文献１、非特許文献２が挙げられる。特許文献１には、ある系列パタンの出現頻度が閾値に満たない場合、その系列パタンを内部的に含む系列パタンに関する出現頻度を調べる処理を省略することで、頻出系列パタンを効率的に発見する技術が開示されている。非特許文献１には、系列データと系列データに含まれるアイテムの識別子リストの併合処理によって、系列パタンの出現頻度を数え上げる技術が記載されている。非特許文献２には、非特許文献１に記載の技術を、ビットマップを用いて実行することで、系列パタンの出現頻度をさらに高速に数え上げることを図った技術が記載されている。
【０００５】
また、第２の方法を用いた技術としては、非特許文献３が挙げられる。非特許文献３では、ｐｒｅｆｉｘと呼ばれる系列パタンの前半部分を固定し、残りの後半部に対応するパタンを順次射影していくことで系列パタンの頻度を数え上げる方法が記載されている。特に、この非特許文献３の技術では、系列パタン内に同時に出現するアイテムの平均数と比較してアイテムの種類の方が多いような系列パタンに対して効果が高いことが分かっている。
【０００６】
【特許文献１】特開平８−２６３３４６号公報
【非特許文献１】M.  J.  Zaki,  SPADE:  An  Efficient  Algorithm  for  Mining  Frequent  Sequences,  Machine  Learning,  Vol.  42,  No.1-2,  2001
【非特許文献２】J.  Ayres  et.  al.,  Sequential  Pattern  Mining  Using  Bitmaps,  Proceedings  of  the  Eighth  ACM  SIGKDD  International  Conference  on  Knoledge  Discovery  and  Data  Mining,  2002
【非特許文献３】J.  Pei  et.  al.,  Mining  Sequential  Patterns  by  Pattern-Growth  :  The  PrefixSpan  Approach,  IEEE  TRANSACTIONS  ON  KNOWLEDGE  AND  DATA  ENGINEERING,  Vol.  16,  No.  10,  2004
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献３の技術では、射影を行う毎に当該射影の対象となるアイテムを特定するための探索を繰り返し行うため、非効率的であるという問題がある。特に、系列パタン内に同時に出現するアイテムの平均数と比較してアイテムの種類が少ない系列データや、繰り返し同一種別のアイテムが出現するような系列データについては、射影に関係ないアイテムについても探索を行うため多くの時間を要するという問題がある。
【０００８】
本発明は上記に鑑みてなされたものであって、射影にかかる処理の効率化を図ることが可能な系列パタン抽出装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本発明は、分析対象となるアイテムを順序付けて配列した系列データに対し、前記アイテムを部分的に配列した系列パタンと一致する前記系列データでのアイテムを基点として射影を行うことで、前記系列データから当該系列パタン以降に存在するアイテムを抽出する系列パタン抽出装置であって、前記系列データを記憶する第１記憶手段と、前記系列データを構成するアイテムに対し、当該アイテムが基点となった場合に前記系列データから抽出の対象となるアイテムを特定するための射影位置を関連付けて記憶する第２記憶手段と、前記系列パタンに対応する前記系列データでの最後のアイテムを基点とし、このアイテムに関連付けて記憶された前記射影位置により特定されるアイテムを前記系列データから抽出する射影手段と、を備える。
【００１０】
また、本発明は、分析対象となるアイテムを順序付けて配列した系列データに対し、前記アイテムを部分的に配列した系列パタンと一致する前記系列データでのアイテムを基点として射影を行うことで、前記系列データから当該系列パタン以降に順序付けられたアイテムを抽出する系列パタン抽出装置の系列パタン抽出方法であって、前記系列パタン抽出装置は、前記系列データを記憶する第１記憶手段と、前記系列データを構成するアイテムに対し、当該アイテムが基点となった場合に前記系列データから抽出の対象となるアイテムを特定するための射影位置を関連付けて記憶する第２記憶手段と、を備え、射影手段が、前記系列パタンに対応する前記系列データでの最後のアイテムを基点とし、このアイテムに関連付けて記憶された前記射影位置により特定されるアイテムを前記系列データから抽出する射影工程と、を含む。
【発明の効果】
【００１１】
本発明によれば、系列データを構成するアイテムに対し、射影時において抽出の対象となるアイテムを特定するための射影位置を関連付けて記憶しておくことで、射影する位置を効率的に取得することができるため、射影にかかる処理を効率的に行うことができる。
【発明を実施するための最良の形態】
【００１２】
以下に添付図面を参照して、系列パタン抽出装置及び方法の最良な実施形態を詳細に説明する。
【００１３】
図１は、本実施形態にかかる系列パタン抽出装置のハードウェア構成を示したブロック図である。同図に示したように、系列パタン抽出装置はＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１３と、記憶部１４と、表示部１５と、操作部１６と、通信部１７とを備え、各部はバス１８を介して接続されている。
【００１４】
ＣＰＵ１１は、ＲＡＭ１３を作業領域として、ＲＯＭ１２又は記憶部１４に記憶されたプログラムとの協働により、各種処理を実行し情報処理装置の動作を統括的に制御する。また、ＣＰＵ１１は、ＲＯＭ１２又は記憶部１４に記憶されたプログラムとの協働により、後述する各機能部の機能を実現させる。
【００１５】
ＲＯＭ１２は、情報処理装置の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。ＲＡＭ１３は、ＳＤＲＡＭやＤＤＲメモリ等の揮発性メモリであって、ＣＰＵ１１の作業エリアとして機能する。
【００１６】
記憶部１４は、磁気的又は光学的に記録可能な記憶媒体を有し、情報処理装置の制御にかかるプログラムや各種情報を書き換え可能に記憶する。また、記憶部１４は、後述する系列データ記憶部２１や射影位置記憶部２４等の記憶手段を実現する。なお、これらの記憶手段では、記憶形式および記憶媒体は用途に応じて任意の設定を選択することが可能であるものとする。例えば、データベース（リレーショナルデータベース）を用いてもよいし、テキストデータを用いてもよい。
【００１７】
表示部１５は、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等の表示デバイスから構成され、ＣＰＵ１１の制御の下、文字や画像等を表示する。
【００１８】
操作部１６は、マウスやキーボード等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、ＣＰＵ１１に出力する。
【００１９】
通信部１７は、外部装置との間で通信を行うインターフェイスであって、外部装置から受信した各種情報をＣＰＵ１１に出力する。また、通信部１７は、ＣＰＵ１１の制御の下、各種情報を外部装置に送信する。
【００２０】
系列パタン抽出装置は、上述したＣＰＵ１１とＲＯＭ１２又は記憶部１４に記憶された所定のプログラムとの協働により、後述するアイテムを順序付けて配列した分析対象の系列データに対し、このアイテムを部分的に配列した系列パタンにより射影を繰り返すことで当該系列データ中に頻出する頻出系列パタンを抽出する。以下、第１〜第３の各実施形態にかかる系列パタン抽出装置について詳細に説明する。
【００２１】
［第１の実施形態］
図２は、第１の実施形態にかかる系列パタン抽出装置１００の機能構成を示した図である。同図に示したように、系列パタン抽出装置１００は、系列データ記憶部２１と、最小支持度入力部２２と、射影位置取得部２３と、射影位置記憶部２４と、射影部２５と、頻出系列パタン出力部２６とを備えている。
【００２２】
系列データ記憶部２１は、分析対象となる系列データを記憶する。ここで「系列データ」は、分析対象として同質のアイテムを順序付けて配列したデータを意味する。なお「アイテム」は、分析対象となるデータの構成要素を意味する。例えば、系列データが購買履歴データであれば、購入した「自動車」や「ビール」等の商品名がアイテムとなる。また、系列データがＤＮＡ配列であれば、アデニン、グアニン等の塩基成分がアイテムとなる。また、系列データが健康診断データであれば、高血圧、肥満等の診断記録がアイテムとなる。
【００２３】
アイテムは、パタン検出の際の単位となるため、予めアイテムの粒度を調整しておくことが望ましい。例えば、「自動車」であれば、型番が異なるものを別のアイテムとするか、型番が異なっていてもメーカーが同じであれば同一のアイテムとするか等を調整する。以下の説明では、説明の簡略化のためアルファベットを用いてアイテムを表記する。
【００２４】
系列データの順序付けの基準は、時間や優先順位、識別番号等、一意に順序付けることが可能であれば、任意の情報を用いることが可能である。また、複数のアイテムが同一の順序になっていてもよい。以下、同一順序のアイテムをまとめてアイテムセットと呼ぶ。なお、以下の説明では、系列データを“＜”と“＞”で囲むことで表し、同一順序にあるアイテムを“（”と“）”で囲むことで表す。
【００２５】
また、以下の説明では、アイテムは左から順に並んでいるとする。例えば、アイテムをａ、ｂ、ｃと表現すると、ｂが先頭で、その後に同一順序でａとｃが続く系列データは、＜（ｂ）（ａｃ）＞と表記される。ここで、（ｂ）と（ａｃ）は順序付けられているため、＜（ｂ）（ａｃ）＞と＜（ａｃ）（ｂ）＞とは別の系列データである。一方、ａとｃは同一順序であるため、＜（ｂ）（ａｃ）＞と＜（ｂ）（ｃａ）＞は同一の系列データである。なお、アイテムセットにアイテムが一つしか含まれていないときは、“（”と“）”とを省略しても混乱を招かないため、表記が煩雑になる場合は“（”と“）”とを省略することもある。例えば、＜ｂ（ａｃ）＞は、＜（ｂ）（ａｃ）＞と等しい。
【００２６】
図３は、系列データ記憶部２１に記憶された系列データ集合の一例を示した図である。同図において識別子は、各系列データを一意に識別するための識別情報であって、系列データ記憶部２１への記憶時に付与されたものである。
【００２７】
系列データを系列データ記憶部２１に記憶する際には、同一順序のアイテムを何らかの基準によって一意に整列させてから記憶することが好ましい。ここで、整列させるための基準は任意であり、例えば、アイテムの文字列順（アルファベット順）としてもよいし、各アイテムに識別子が割り当てられているならば、その識別子の順としてもよい。なお、文字列順で整列させるとき、＜（ｂａｄ）（ｄｂ）（ａｅｃ）＞は、＜（ａｂｄ）（ｄｂ）（ａｃｅ）＞として記憶される。以下では、この順序を「アイテム順序」と呼ぶ。
【００２８】
また、系列データに部分的に含まれた系列データ（アイテムの組み合わせ）を、「系列パタン」という。例えば、＜（ｂ）（ａｃ）＞からは、＜（ａ）＞、＜（ｂ）＞、＜（ｃ）＞、＜（ａｃ）＞、＜（ｂ）（ａ）＞、＜（ｂ）（ｃ）＞、＜（ｂ）（ａｃ）＞という系列パタンが得られる。ある系列パタンが、特定の系列パタンに含まれていると述べる場合、アイテムセットの順序を保持した状態で含まれていることを意味する。例えば、＜（ａ）（ｂｃ）＞は、＜（ａｃ）（ｂｃｄ）＞に含まれているが、＜（ｂｃ）（ａ）＞は含まれてはいない。
【００２９】
最小支持度入力部２２は、頻出か否かの判定基準となる最小支持度を射影位置取得部２３及び射影部２５に出力する。ここで「最小支持度」とは、系列パタンが頻出であるかを判定する閾値を意味する。最小支持度は、分析対象の系列データ集合に応じて利用者が決定する態様としてもよいし、最小支持度入力部２２が予め設定された最小支持度等に基づいて、自動的に決定する態様としてもよい。なお、前者の場合、操作部１６や通信部１７等を介して入力されるものとする。
【００３０】
最小支持度の指定方法として、出現頻度として指定する方法と、出現割合として指定する方法とが挙げられる。出現割合として算出する場合、分析対象の系列データ集合に含まれる系列パタンの数と最小支持度として指定される出現割合を掛け合わせた数を、判定閾値とする。例えば、分析対象系列データの数が１０００、最小支持度として１０％という値を指定した場合、１００が頻出と判定するための閾値となる。なお、頻出と判定するのに、閾値そのものを含むかについては使用する環境に応じて適宜変更することが可能である。本実施形態では、頻出の判定に閾値を含む場合について説明を行う。
【００３１】
分析対象である系列データ集合において、着目している系列パタンが最小支持度以上出現している系列パタンを「頻出系列パタン」という。系列パタンの出現数は、分析対象の系列データ集合に含まれた一つの系列データに、着目している系列パタンが含まれていれば、系列パタンを構成するアイテムの組み合わせに関わらず、１回出現として数える。例えば、系列データ＜ｂ（ａｃ）＞には、＜ｂａ＞が１回出現している。また、＜ｂ（ａｃ）ａ＞には、一番目のｂと二番目のａの組み合わせからなる＜ｂａ＞と、一番目のｂと三番目のａの組み合わせからなる＜ｂａ＞が存在するが、同一の系列データ内であるため１回出現と数える。
【００３２】
例として、図３に示した系列データ集合において、最小支持度２が指定された場合について考える。図３において、＜（ａｃ）（ｄ）＞は、識別子０００１と０００２の系列データに出現する。そのため、出現頻度は２となるから、＜（ａｃ）（ｄ）＞は頻出系列パタンであることが分かる。また、＜（ｂｄ）（ｆ）＞は、識別子０００２の系列データのみにしか出現しない。そのため、出現頻度は１となるから、＜（ｂｄ）（ｆ）＞は頻出系列パタンではないことが分かる。
【００３３】
頻出系列パタンは、様々な分野で利用することができる。例えば、購買履歴データを分析した場合、多くの人に共通する購買パタンを検出することができる。また、ＤＮＡ配列データであれば、特定の疾病や性質を有する人に共通するＤＮＡ配列を検出することができるため、疾病等に関係するＤＮＡ配列を特定するのに有効である。また、生活習慣データと、健康診断データとを組み合わせて分析した場合、高血圧等の症状と生活習慣の関係とを調べることが可能である。
【００３４】
図２に戻り、射影位置取得部２３は、系列データを構成する各アイテムが射影（ｐｒｏｊｅｃｔ）の基点とされた場合での、当該系列データから抽出の対象となるアイテムを特定するための射影位置をアイテム単位で取得し、射影の基点となるアイテムに関連付けて射影位置記憶部２４に記憶する。
【００３５】
ここで「射影」とは、系列データにおいて、基点となる特定の系列パタン以降に存在するアイテムを当該系列データから抽出する操作を意味する。このとき、基点となる系列パタンを「前置パタン」と呼ぶ。また、系列データと前置パタンを対応させたとき、前置パタンを抽出した残りのパタンを「後置パタン」と呼び、後置パタンの先頭のアイテムセットが前置パタンの最終アイテムセットと同じとき、その後置パタンの先頭アイテムセットを「後置アイテムセット」と呼ぶ。
【００３６】
例えば、系列データ＜ｄ（ａｂ）ｃ＞について、＜ａ＞を前置パタンとして射影を行うと、後置パタン＜ｂｃ＞が得られ、後置アイテムセットは＜ｂ＞となる。一方、前置パタンを＜ｄ＞として射影を行うと、後置パタンは＜（ａｂ）ｃ＞となるが、後置アイテムセットは存在しない。
【００３７】
また、射影は、抽出操作により得られた系列パタンにアクセス可能にすることと等価であるから、前置パタンに隣接しているアイテムの位置から、系列データにアクセスするようにさせることも射影と呼ぶ。例えば、系列データ＜ｄ（ａｂ）ｃ＞について、＜ａ＞を前置パタンとして射影を行うと、後置パタン＜ｂｃ＞が得られる。これは、“ｂ”からデータにアクセスさせることと同じである。計算機で実現する場合、先に定義した射影は、データのコピーに対応し、後に定義した射影はデータを読み込む際のポインタの位置を変更したことに対応する。以下では、前者を「直接射影方式」、後者を「擬似射影方式」と呼ぶ。
【００３８】
装置もしくは計算機上における実現方法は、用途に応じて適切なものを用いる。記憶領域を節約したい場合は直接射影方式を用い、高速に処理したい場合は擬似射影方式を用いることが多い。なお、本実施形態では擬似射影方式を中心に説明を行う。
【００３９】
射影には、前置パタンの最終アイテムと同一順序のアイテム、即ち、同一アイテムセット内のアイテムに射影するときと、最終アイテムと異なる順序のアイテム、即ち、他のアイテムセットのアイテムに射影するときの二種類がある。以下では、前者を「同順射影」、後者を「異順射影」と呼ぶ。また、射影されるアイテムと位置を、それぞれ「同順射影アイテム」、「同順射影位置」、「異順射影アイテム」、「異順射影位置」と呼ぶ。
【００４０】
なお、前置パタンと系列データを照合させたときに、系列データ内に前置パタンと一致する箇所が複数ある場合には、系列データの最も先頭に一致した前置パタンを射影の際の基点とする。例えば、前置パタン＜ａｂ＞を系列データ＜ａｂｂ＞と対応させた場合、＜ａｂｂ＞における一番目の“ａ”と二番目の“ｂ”から構成される＜ａｂ＞が基点となる。このとき、前置パタンの最終アイテムの位置とは、＜ａｂ＞の“ｂ”に対応する＜ａｂｂ＞の二番目の“ｂ”が該当する。以下、上述した同順射影、異順射影について説明する。
【００４１】
まず、同順射影について説明する。同順射影では、まず前置パタンの最終アイテムセットと、その最終アイテムセット中の最終アイテムに着目する。このとき、同順射影アイテムは、（１）最終アイテムより後に存在し、（２）最終アイテムよりアイテム順序が後のアイテムであり、（３）前置パタンの最終アイテムセットに含まれる全てのアイテムを含んだアイテムセット内に存在するアイテムのうち、同一種類のアイテムの中でもっとも前方に存在するアイテムである。また、このアイテムの位置（アイテム位置）が同順射影位置となる。
【００４２】
ここで、同順射影の例として、系列データが＜（ａｂｃ）（ｂｃｄ）（ｂｃｅ）（ａｃｄ）（ａｂｃｄ）＞のとき、前置パタンを＜（ａｃ）（ｂｃ）＞として射影したときの同順射影位置を考える。このとき、前置パタンの最終アイテムに対応する位置は、＜（ａｂｃ）（ｂｃｄ）（ｂｃｅ）（ａｃｄ）（ａｂｃｄ）＞の二番目のアイテムセットの“ｃ”の位置である。この位置より後に存在し、最終アイテムよりアイテム順序が後のアイテムは、二番目のアイテムセットの“ｄ”、三番目のアイテムセットの“ｅ”、四番目のアイテムセットの“ｄ”、五番目のアイテムセットの“ｄ”である。このうち、前置パタンの最終アイテムセットに含まれた“ｂ”と“ｃ”とを含むアイテムセット内に存在する他のアイテムは、二番目のアイテムセットの“ｄ”、三番目のアイテムセットの“ｅ”、五番目のアイテムセットの“ｄ”である。同一種類のアイテムが存在する場合、もっとも前方に存在するアイテムの位置のみを射影位置とするので、射影位置（同順射影位置）は、二番目のアイテムセットの“ｄ”の位置と、三番目のアイテムセットの“ｅ”の位置となる。同様に、前置パタンを＜（ｂ）（ｃｄ）（ｂｃ）＞として射影した場合、射影位置は三番目のアイテムセットの“ｅ”、五番目のアイテムセットの“ｄ”となる。
【００４３】
なお、射影位置取得部２３は、各系列データについて実際に射影が行われる上述した同順射影位置を記憶するのではなく、この実同順射影位置を特定するためのアイテムの位置を同順射影位置として射影位置記憶部２４に記憶する。以下の説明では、両同順射影位置の混同を避けるため、実際に射影が行われる同順射影位置を実同順射影位置と呼ぶ。
【００４４】
次に異順射影について説明する。異順射影では、まず前置パタンを構成する最終アイテムセットの最終アイテムに着目する。このとき、異順射影アイテムは、（１）最終アイテムより後方のアイテムセットに存在し、（２）同一種類のアイテムうち、最も前方に存在するアイテムである。また、このアイテムのアイテム位置が異順射影位置である。射影位置取得部２３は、この異順射影位置を、系列データ中の対応するアイテム（異順射影アイテム）と関連付けて射影位置記憶部２４に記憶する。
【００４５】
ここで、異順射影の例として、系列データが＜（ａｂｃ）（ｂｃｄ）（ｂｃｅ）（ａｃｄ）（ａｂｃｄ）＞のとき、前置パタンを＜（ａｃ）（ｂｃ）＞として射影したときの射影位置を考える。このとき、前置パタンの最終アイテムに対応する位置は、＜（ａｂｃ）（ｂｃｄ）（ｂｃｅ）（ａｃｄ）（ａｂｃｄ）＞の二番目のアイテムセットの“ｃ”の位置である。このアイテムより後のアイテムセット、つまり、三番目以降のアイテムセット、に存在するアイテムの種類は“ａ”、“ｂ”、“ｃ”、“ｄ”、“ｅ”である。各種類のアイテムの中で、最も前方に存在するアイテムは、三番目のアイテムセットの“ｂ”、“ｃ”、“ｅ”、四番目のアイテムセットの“ａ”、“ｄ”であるから、これらが射影位置（異順射影位置）となる。同様に、前置パタンを＜（ｂ）（ｃｄ）（ｂｃ）＞として射影した場合、射影位置は四番目のアイテムセットの“ａ”と“ｃ”と“ｄ”、五番目のアイテムセットの“ｂ”に対応する位置になる。
【００４６】
射影を行うアイテムの順番については、系列データを記憶する際に用いたアイテム順序を利用する。また、同順射影を先に行う方法と、異順射影を先に行う方法の二種類がある。射影順序は、一意に定められていればどちらでもよい。以下の説明では、同一順序のアイテムを最優先し、次にアイテムの文字列順に射影することとする。
【００４７】
例えば、系列データ＜（ａｃ）（ａ）（ａｂｃ）（ｂｃ）＞においては、前置パタンを＜ａ＞として射影した場合、三番目のアイテムセットの“ｂ”、一番目のアイテムセットの“ｃ”の位置に同順射影を行った後、二番目のアイテムセットの“ａ”、三番目のアイテムセットの“ｂ”、三番目のアイテムセットの“ｃ”の位置に異順射影を行う。
【００４８】
なお、射影位置記憶部２４への射影位置（同順射影位置、異順射影位置）の記憶方式は系列データ毎に異なっていてもよいので、系列データの特性に応じて適切な記憶方式を採用することが望ましい。また、射影自体の特性のため、射影位置を記憶しなくともよい場合がある。例えば、系列データの最終アイテムセットに含まれるアイテムの射影位置は自明であるため記憶する必要はない。また、系列データの末尾から二番目のアイテムセットに含まれるアイテムの異順射影位置は明らかであるため、これらのアイテムセットには射影位置を記憶する必要はない。さらに系列データの特性のため、射影位置を記憶しなくともよい場合がある。例えば、系列データに同時に出現するアイテムの平均数よりアイテム種類の方が十分多い系列データについては、射影位置を記憶しなくとも効率的な射影が可能である。射影位置取得部２３では、これらの事項に基づいて射影位置を射影位置記憶部２４に記憶する。
【００４９】
以下、射影位置の記憶方式について説明する。射影位置記憶部２４に記憶される射影位置の内容は、速度を優先するか、記憶領域を優先するかに応じて異なる。速度を優先する場合、射影位置を射影の優先度順に記憶し、先に射影が行われる位置を即座に取得できるようにすることで速度の向上を図ることができる。以下、これを「速度優先方式」と呼ぶ。一方、記憶領域を優先する場合、射影が必須の位置については記憶せず、系列データ全体を調べなければ射影位置が判明しないアイテムの位置のみを記憶することで記憶領域の削減を図ることができる。以下、これを「記憶領域優先方式」と呼ぶ。これらの記憶方式は、系列データ集合全体で統一させる必要はなく、系列データ毎に適切な方式を用いることができる。
【００５０】
例えば、記憶領域を比較的多く要する系列データについては、記憶領域優先方式を用いることで、射影位置を表すデータ量を削減することができる。また、速度優先方式で射影位置を記憶し始め、記憶領域の残量が所定の値に達した時点で、一部の系列データについて記憶領域優先方式を用いることとしてもよい。
【００５１】
さらに、隣接するアイテムもしくはアイテムセットとの射影位置の差分のみを記憶することで記憶領域の削減を図る方法が考えられる。以下、これを「差分方式」と呼ぶ。この差分方式は、ＤＮＡ配列等のアイテムセット内の平均アイテム数が少ない系列データに関して特に有効である。ただし、射影部２５での射影時に元の射影位置の状態を復元する処理が必要になるため、速度優先方式と比較して処理が煩雑となる。そのため、射影位置記憶部２４の残容量等に応じて利用することが好ましい。
【００５２】
以下、射影位置取得部２３が実行する射影位置を取得のための処理（射影位置取得処理）について説明する。なお、以下の説明では、系列データとして＜（ａｂｃｅ）（ｂｃｄ）（ａｂｄ）（ａｂｃｄ）（ｃｄｅ）＞の射影位置を取得する場合を考える。
【００５３】
まず、同順射影位置の取得にかかる処理（同順射影位置取得処理）について説明する。図４は、同順射影位置取得処理の手順を示したフローチャートである。以下では、読み込んだデータを行列的に記憶して処理する方法を説明するが、同等の処理が可能であれば別のデータ構造を用いてもよいし、系列データを走査することで代用してもよい。
【００５４】
まず、射影位置取得部２３は、系列データの一番目のアイテムセットを読み込むと、このアイテムセットに含まれた各アイテムの位置（アイテム位置）をＲＡＭ１３等に記憶する（ステップＳ１１）。以下、各アイテムの位置を記憶したものを「アイテム位置行列」と呼ぶ。
【００５５】
ここで、図５−１は、一番目のアイテムセットを読み込んだときの、系列データと、それに対応する同順射影位置と、アイテム位置行列とを示した図である。同図に示したように、アイテム位置行列の各行はアイテム種別に対応しており、各アイテムセットに含まれた各アイテムの位置（アイテム位置）が、列単位で記憶されるようになっている。なお、ここでは、説明の簡略化のため、各アイテムのアイテム位置を、系列データの左方から右方のアイテムにかけて付与した数値（０〜１６）で表している。以下、アイテム位置と表記した場合、図５−１と同様の概念を用いるものとする。
【００５６】
続いて、射影位置取得部２３は、次のアイテムセットを読み込むと、ステップＳ１１と同様に、このアイテムセットに含まれた各アイテムの位置をＲＡＭ１３等に記憶する（ステップＳ１２）。
【００５７】
次いで、射影位置取得部２３は、ステップＳ１２で今回読み込んだアイテムセットの中に、前回迄に読み込んだ各アイテムセットには含まれない新たなアイテムが存在するか否かをアイテムセット毎に判定する（ステップＳ１３）。ここで、何れのアイテムセットに対しても新たなアイテムが存在しないと判定した場合（ステップＳ１３；Ｎｏ）、ステップＳ１６の処理に直ちに移行する。
【００５８】
一方、ステップＳ１３において、新たなアイテムが存在すると判定した場合（ステップＳ１３；Ｙｅｓ）、射影位置取得部２３は、ステップＳ１２で今回読み込んだアイテムセットにおいて、ステップＳ１３で判定した新たなアイテムよりアイテム順序が先となるアイテムのアイテム位置を同順射影位置として取得する（ステップＳ１４）。
【００５９】
次いで、射影位置取得部２３は、ステップＳ１４で取得した同順射影位置を、ステップＳ１３で新たなアイテムを含まないと判定したアイテムセットで、且つ、同順射影位置のアイテムと同一種類のアイテムのアイテム位置と関連付けて、射影位置記憶部２４に記憶する（ステップＳ１５）。なお、ステップＳ１３の処理の際に、全てのアイテムに同順射影位置が記憶されたアイテムセットについては調べる必要はない。また、アイテム順序が先頭のアイテムについても調べる必要はない。
【００６０】
ここで、図５−２を参照して、ステップＳ１３〜Ｓ１５の処理を説明する。図５−２は、二番目のアイテムセットを読み込んだときの、系列データと、それに対応する同順射影位置と、アイテム位置行列とを示した図である。同図に示したように、アイテム位置行列のアイテム“ｂ”と“ｃ”には、一番目のアイテムセットでの位置１、２が記憶されている。一方、アイテム“ｄ”については、一番目のアイテムセットでの位置が記憶されておらず、対応するアイテムが存在しないので、新たなアイテムであることがわかる。このようなアイテムがあれば、射影位置取得部２３は、ステップＳ１４の処理に移行する。
【００６１】
続くステップＳ１４では、アイテム“ｄ”よりもアイテム順序が先のアイテム、即ち“ｂ”と“ｃ”のアイテム位置４、５を同順射影位置として取得する。次いで、射影位置取得部２３は、ステップＳ１５において、取得した同順射影位置を、ステップＳ１３で新たなアイテムを含まないと判定したアイテムセット、即ち、一番目のアイテムセットのアイテム“ｂ”、“ｃ”のアイテム位置に関連付けて射影位置記憶部２４に記憶する。なお、アイテム位置行列において、位置１と位置２に再度同順射影位置が記憶されることはないことから、該当するセルを斜線で示している。また、アイテム順序の最終アイテムの位置には同順射影位置は記憶されないので、これらも斜線で示している。
【００６２】
図４に戻り、続くステップＳ１６では、射影位置取得部２３が、系列データの終端までアイテムセットの読み込みが完了したか否かを判定する（ステップＳ１６）。終端まで読み込みが完了している場合は（ステップＳ１６；Ｙｅｓ）、本処理を終了する。まだ、終端に達していない場合は（ステップＳ１６；Ｎｏ）、ステップＳ１２の処理に再び戻る。
【００６３】
なお、図５−２で示した例では、系列データの最終アイテムセットまで読み込みが完了していないので、ステップＳ１２の処理に再び戻る。以下、上記のステップＳ１２〜Ｓ１６のループ処理を続けたときの、同順射影位置の取得状態について図５−３、５−４、５−５を参照して説明する。
【００６４】
図５−３は、三番目のアイテムセットを読み込んだときの系列データと、それに対応する同順射影位置と、アイテム位置行列とを示した図である。同図に示したように、今回ステップＳ１２で読み込まれたアイテムは“ａ”、“ｂ”、“ｄ”であり、これらアイテムのアイテム位置７、８、９がアイテム位置行列に夫々記憶されている。
【００６５】
ここで、一番目のアイテムセットには、今回読み込んだアイテム“ｄ”が存在しないことが分かる。そのため、射影位置取得部２３は、ステップＳ１４の処理に移行し、今回読み込んだアイテム“ａ”、“ｂ”についてのアイテム位置７、８を同順射影位置として取得する。なお、二番目のアイテムセットには、今回読み込んだアイテム“ａ”が存在しないが、アイテム順序の先頭アイテムであるため、処理の対象からは除外する。
【００６６】
次いで、射影位置取得部２３は、取得した同順射影位置７を、新たなアイテムを含まないと判定したアイテムセット、即ち、一番目のアイテムセットのアイテム“ａ”のアイテム位置に関連付けて射影位置記憶部２４に記憶する。なお、一番目のアイテムセットには、アイテム“ｄ”より先のアイテム順序のアイテム“ａ”、“ｂ”、“ｃ”が存在するが、アイテム“ｂ”と“ｃ”のアイテム位置にはすでに同順射影位置が関連付けて記憶されているため、処理の対象から除外する。
【００６７】
この時点で、一番目のアイテムセットに含まれるアイテム全てに同順射影位置が記憶されたので、これ以降ステップＳ１３の処理で一番目のアイテムセットを調べる必要はなくなる。また、射影位置取得部２３は、ステップＳ１６において、終端まで読み込んでいないと判定するためステップＳ１２に再び戻り、次のアイテムセットを読み込む。
【００６８】
図５−４は、四番目のアイテムセットを読み込んだときの系列データと、それに対応する同順射影位置と、アイテム位置行列とを示した図である。同図に示したように、今回ステップＳ１２で読み込まれたアイテムは“ａ”、“ｂ”、“ｃ”、“ｄ”であり、これらアイテムのアイテム位置１０、１１、１２、１３がアイテム位置行列に夫々記憶されている。
【００６９】
ここで、三番目のアイテムセットには、今回読み込んだアイテム“ｃ”が存在しないことが分かる。そのため、射影位置取得部２３は、ステップＳ１４の処理に移行し、今回読み込んだアイテム“ａ”、“ｂ”についてのアイテム位置１０、１１を同順射影位置として取得する。なお、二番目のアイテムセットには、今回読み込んだアイテム“ａ”が存在しないが、アイテム順序の先頭アイテムであるため、処理の対象からは除外する。
【００７０】
次いで、射影位置取得部２３は、取得した同順射影位置１０、１１を、新たなアイテムを含まないと判定したアイテムセット、即ち、三番目のアイテムセットのアイテム“ａ”、“ｂ”のアイテム位置に関連付けて射影位置記憶部２４に記憶する。また、射影位置取得部２３は、ステップＳ１６において、終端まで読み込んでいないと判定するためステップＳ１２に再び戻り、次のアイテムセットを読み込む。
【００７１】
図５−５は、五番目のアイテムセットを読み込んだときの系列データと、それに対応する同順射影位置と、アイテム位置行列とを示した図である。同図に示したように、今回ステップＳ１２で読み込まれたアイテムは“ｃ”、“ｄ”、“ｅ”であり、これらアイテムのアイテム位置１４、１５、１６がアイテム位置行列に夫々記憶されている。
【００７２】
ここで、二番目、三番目、四番目のアイテムセットには、今回読み込んだアイテム“ｅ”が存在しないことが分かる。そのため、射影位置取得部２３は、ステップＳ１４の処理に移行し、今回読み込んだアイテム“ｃ”、“ｄ”についてのアイテム位置１４、１５を同順射影位置として取得する。なお、三番目のアイテムセットには、今回読み込んだアイテム“ｃ”が存在しないが、今回読み込んだアイテムには、アイテム“ｃ”よりもアイテム順序が先のアイテムは存在しないため、処理の対象からは除外する。
【００７３】
次いで、射影位置取得部２３は、取得した同順射影位置１４、１５を、新たなアイテムを含まないと判定したアイテムセット、即ち、二番目、三番目及び四番目のアイテムセットのアイテム“ｃ”、“ｄ”のアイテム位置に関連付けて射影位置記憶部２４に記憶する。また、射影位置取得部２３は、ステップＳ１６において、系列データの終端まで読み込んだと判定するため本処理を終了する。
【００７４】
次に、異順射影位置の取得にかかる処理（異順射影位置取得処理）について説明する。図６は、異順射影位置取得処理の手順を示したフローチャートである。
【００７５】
まず、射影位置取得部２３は、系列データから二番目のアイテムセットを読み込み、このアイテムセットについてアイテム位置行列を生成する（ステップＳ２１）。ここで、異順射影のアイテム位置行列は、同順射影のアイテム位置行列と同じようにアイテム毎のアイテム位置を示した行列となるが、意味するものは異なっている。
【００７６】
図７−１は、系列データ＜（ａｂｃｅ）（ｂｃｄ）（ａｂｄ）（ａｂｃｄ）（ｃｄｅ）＞から二番目のアイテムセットを読み込んだときの、アイテム位置行列を示した図である。同図に示したように、アイテム位置行列の各行はアイテム種別に対応しており、各アイテムセットに含まれた各アイテムの位置（アイテム位置）が、列単位で記憶されるようになっている。
【００７７】
続いて、射影位置取得部２３は、系列データから次のアイテムセットを読み込み、このアイテムセットに含まれたアイテム毎の位置をアイテム位置行列に記憶する（ステップＳ２２）。ここで、図７−２は、系列データから三番目のアイテムセットを読み込んだときの、アイテム位置行列を示している。
【００７８】
次いで、射影位置取得部２３は、アイテム位置行列において、ステップＳ２２で読み込んだ各アイテム種別の行に、アイテム位置が空欄のセルが存在するか否かを列毎に判定する（ステップＳ２３）。ここで、アイテム位置が空欄のセルが存在しないと判定した場合には（ステップＳ２３；Ｎｏ）、ステップＳ２５の処理に直ちに移行する。
【００７９】
一方、ステップＳ２３において、アイテム位置が空欄のセルが存在すると判定した場合（ステップＳ２３；Ｙｅｓ）、射影位置取得部２３は、ステップＳ２２で今回読み込んだアイテムセットの各アイテム位置のうち、アイテム位置が空欄のセルとアイテム種別と同一、即ち、同じアイテム行のアイテム位置を、この空欄のセルに記憶する（ステップＳ２４）。例えば、図７−２では、アイテム“ａ”の一列目のセルが空欄であることがわかる。そのため、射影位置取得部２３は、この一列目のアイテム種別“ａ”のセルに、今回読み込んだ二列目のアイテム“ａ”のアイテム位置７を記憶し、図７−３に示したアイテム位置行列の状態とする。
【００８０】
続いて、射影位置取得部２３は、系列データの終端まで読み込みが完了したか否かを判定する（ステップＳ２５）。ここで、終端に達していないと判定した場合には（ステップＳ２５；Ｎｏ）、ステップＳ２２の処理に再び戻る。一方、終端に達していると判定した場合には（ステップＳ２５；Ｙｅｓ）、ステップＳ２６の処理に進む。
【００８１】
続くステップＳ２６において、射影位置取得部２３は、アイテム位置行列を構成する各列を異順射影位置として取得すると（ステップＳ２６）、系列データの対応するアイテムセットと関連付けて射影位置記憶部２４に記憶し（ステップＳ２７）、本処理を終了する。
【００８２】
なお、図７−３の例では、系列データの終端に達していないため、ステップＳ２２に再び戻り、ステップＳ２２〜Ｓ２５のループ処理を継続する。以下、図７−４、７−５、７−６、７−７を参照して、系列データ＜（ａｂｃｅ）（ｂｃｄ）（ａｂｄ）（ａｂｃｄ）（ｃｄｅ）＞の終端まで読み込みが完了するまでの流れを説明する。
【００８３】
図７−４は、四番目のアイテムセットを読み込んだ直後のアイテム位置行列の状態を示した図である。このとき、射影位置取得部２３は、ステップＳ２３の処理で、アイテム“ｃ”の二列目のセルが空欄であると判定するため、続くステップＳ２４の処理で、このセルに、今回読み込んだアイテム“ｃ”のアイテム位置１２を記憶する。このとき、アイテム位置行列の状態は、図７−５のようになる。まだ、射影位置取得部２３は、系列データの終端まで読み込みが完了していないと判定するため（ステップＳ２５；Ｎｏ）、ステップＳ２２の処理に再び戻る。
【００８４】
図７−６は、五番目のアイテムセットを読み込んだ直後のアイテム位置行列の状態を示した図である。このとき、射影位置取得部２３は、ステップＳ２３の処理で、アイテム“ｅ”の一列目、二列目、三列目のセルが空欄であると判定するため、続くステップＳ２４の処理で、これらのセルに、今回読み込んだアイテム“ｅ”のアイテム位置１６を記憶する。このとき、アイテム位置行列の状態は、図７−７のようになる。まだ、射影位置取得部２３は、系列データの終端まで読み込みが完了していないと判定するため（ステップＳ２５；Ｙｅｓ）、ステップＳ２６の処理に移行する。
【００８５】
ここで、アイテム位置行列の一列分の数値は、一つのアイテムセットの異順射影位置に対応する。そのため、射影位置取得部２３は、ステップＳ２６の処理で、アイテム位置行列の各列をアイテム順序で取得すると、対応するアイテムセットと関連付けて射影位置記憶部２４に記憶する。この結果、図７−８に示したように、系列データを構成する各アイテムセットに、対応する異順射影位置が関連付けて記憶される。なお、系列データの最終アイテムセットと、終端から二番目のアイテムセットについては、異順射影位置が必要ないため、アイテム位置行列の最右端の列は読み込む必要はない。
【００８６】
記憶領域優先方式を用いて異順射影位置を射影位置記憶部２４に記憶する場合は、上述した異順射影位置取得処理により速度優先方式の異順射影位置を取得した後、後方に隣接するアイテムセットのアイテム位置と重複する位置を、異順射影位置を削除する処理を行う。例として、図７−８に示した異順射影位置（速度優先方式）から、記憶領域優先方式の異順射影位置を取得する方法を説明する。
【００８７】
図７−８に示したように、系列データの一列目のアイテムセットに対応する異順射影位置は、位置７、４、５、６、１６である。一方、二列目のアイテムセットに含まれるアイテムのアイテム位置は４〜６であり、これらは一列目の異順射影位置に含まれている。そのため、一列目の異順射影位置から４〜６を削除し、残った異順射影位置７と１６とを一列目のアイテムセットの異順射影位置として記憶する。二列目、三列目についても同様の処理を行うことで、記憶領域優先方式での異順射影位置は図７−９のように表される。
【００８８】
また、差分方式を用いて異順射影位置を射影位置記憶部２４に記憶する場合には、速度優先方式或いは記憶領域優先方式の異順射影位置を取得した後、前方に隣接するアイテムセットの異順射影位置と共通する異順射影位置を削除する処理を行う。ここでは、例として、図７−９の記憶領域優先方式の異順射影位置から、差分方式の異順射影位置を取得する方法を説明する。
【００８９】
図７−９に示したように、系列データの一列目のアイテムセットには７と１６、二列目のアイテムセットには１２と１６の異順射影位置が関連付けて記憶されている。このうち、１６が共通しているので、二列目のアイテムセットから１６を削除し、位置１２のみを二列目のアイテムセットに対応する異順射影位置として記憶する。同様に三列目の異順射影位置も処理すると、差分方式での異順射影位置は図７−１０のように表される。
【００９０】
上記した、速度優先方式、記憶領域優先方式、差分方式の何れかの方式で系列データ毎の異順射影位置が射影位置記憶部２４に記憶されることになる。なお、何れの方式を用いるかは、任意であるとする。
【００９１】
図２に戻り、射影位置記憶部２４は、射影位置取得部２３によって取得された射影位置（同順射影位置、異順射影位置）を記憶する機能部である。同一順序のアイテム同士は異なる順序のアイテムに関する射影位置が重複するため、異なる順序位置毎、つまり、アイテムセット毎に代表となる射影位置を記憶する。このように、射影位置をあらかじめ記憶しておくことにより、余分なアイテムへのアクセスを削減することが可能になり、射影処理の効率化を図ることができる。
【００９２】
射影部２５は、射影位置記憶部２４に記憶された射影位置に基づいて射影を行い、最小支持度入力部２２から入力された最小支持度以上出現する頻出アイテムを、分析対象の系列データ集合から抽出する。なお、射影位置記憶部２４に記憶された射影位置の記憶方式により、射影位置の取得方法は異なるが、何れの記憶方式を用いた場合でも、射影位置に実際に射影が行われるには、射影位置が頻出であること、つまり、射影位置が最小支持度以上出現していることが必要条件となる。
【００９３】
頻出系列パタン出力部２６は、射影部２５により分析対象の系列データ集合から抽出された頻出アイテムを出力する機能部である。なお、出力とは、表示部１５を通じて利用者に頻出系列パタンを逐次提示することや、結果を再利用できるように記憶部１４にファイルとして記録させることだけではなく、後で一括して表示させるためにＲＡＭ１３等に記憶させることや、他のシステムで即座に再利用できるように通信部１７を介して外部装置に送信することも含む概念である。
【００９４】
以下、系列パタン抽出装置１００の動作について説明する。図８は、系列パタン抽出装置１００の各機能部により実行される頻出系列パタン発見処理の手順を示したフローチャートである。以下の処理では、図３に示した系列データの集合を分析の対象とし、最小支持度として２が指定された場合を例に説明する。
【００９５】
まず、最小支持度入力部２２は、最小支持度を射影位置取得部２３及び射影部２５に出力する（ステップＳ３１）。なお、最小支持度が割合として指定されていた場合には、最小支持度入力部２２は頻度に変換した後、出力を行うものとする。
【００９６】
続いて、射影位置取得部２３は、射影位置記憶部２４に記憶された分析対象の各系列データに含まれるアイテムから、ステップＳ３１で入力された最小支持度未満となるアイテムを削除する（ステップＳ３２）。例えば、図３に示した系列データ集合の場合、アイテム“ｆ”、“ｇ”、“ｈ”は識別子０００２のみにしか存在しないため削除する。図３の系列データ集合にステップＳ３２の処理を施した結果は、図９に示した系列データ集合となる。
【００９７】
なお、このとき単独で最小支持度以上となるアイテムのアイテム位置を記憶しておくことで、後述するステップＳ３４の処理で、前置パタンの先頭アイテムに対応する位置を再度探索する必要がなくなる。また、この時点で削除されなかったアイテムは、単独で頻出パタンとなるので、頻出系列パタン出力部２６により出力される。
【００９８】
次いで、射影位置取得部２３は、分析対象の各系列データ集合に関連する射影位置が射影位置記憶部２４に記憶されているかを判定する（ステップＳ３３）。ここで、射影位置記憶部２４に射影位置が記憶されていると判定した場合には（ステップＳ３３；Ｙｅｓ）、ステップＳ３５の処理に直ちに移行する。
【００９９】
一方、ステップＳ３３において、射影位置記憶部２４に射影位置が記憶されていないと判定した場合（ステップＳ３３；Ｎｏ）、射影位置取得部２３は、系列データ記憶部２１に記憶された分析対象の各系列データに対し、射影位置取得処理を実行する（ステップＳ３４）。以下、図１０を参照して、ステップＳ３４の射影位置取得処理について説明する。
【０１００】
図１０は、射影位置取得処理の手順を示したフローチャートである。まず、射影位置取得部２３は、系列データ記憶部２１に記憶された分析対象の系列データ集合から、処理対象とする系列データを一つ選択する（ステップＳ３４１）。
【０１０１】
続いて、射影位置取得部２３は、ステップＳ３４１で選択した処理対象の系列データに対し、同順射影位置取得処理を実行した後（ステップＳ３４２）、異順射影位置取得処理を実行する（ステップＳ３４３）。ここで、ステップＳ３４２の同順射影位置取得処理は、上述した図４の同順射影位置取得処理と同様であるため説明を省略する。また、ステップＳ３４３の異順射影位置取得処理は、上述した図６の異順射影位置取得処理と同様であるため説明を省略する。なお、同順射影位置取得処理、異順射影位置取得処理の順に処理することとしたが、これに限らず、異順射影位置取得処理から先に実行する態様としてもよいし、両処理を同時的に実行する態様としてもよい。
【０１０２】
次いで、射影位置取得部２３は、ステップ３４３の処理で得られた異順射影位置の記憶方式を判定する（ステップＳ３４４）。ここで、記憶方式は予め設定されている態様としてもよいし、射影位置記憶部２４の残容量に応じて自動的に決定する態様としてもよい。
【０１０３】
ステップＳ３４４において、速度優先方式と判定した場合（ステップＳ３４４；速度）、射影位置取得部２３は、ステップＳ３４７の処理に直ちに移行する。
【０１０４】
また、ステップＳ３４４において、記憶領域優先方式と判定した場合（ステップＳ３４４；記憶）、射影位置取得部２３は、記憶優先格納処理を実行する（ステップＳ３４５）。以下、ステップＳ３４５の記憶優先格納処理について説明する。
【０１０５】
図１１は、ステップＳ３４５の記憶優先格納処理の手順を示したフローチャートである。まず、射影位置取得部２３は、系列データの前方から処理対象とする一つのアイテムセットを順次選択する（ステップＳ３４５１）。
【０１０６】
続いて、射影位置取得部２３は、ステップＳ３４３の処理で射影位置記憶部２４に記憶された速度優先方式の異順射影位置を参照すると、処理対象のアイテムセットに対応付けられた異順射影位置と、このアイテムセットの後方に隣接するアイテムセットのアイテム位置とを比較し、重複した位置を処理対象のアイテムセットに関連付けられた異順射影位置から削除する（ステップＳ３４５２）。
【０１０７】
次いで、射影位置取得部２３は、処理対象のアイテムセットが、系列データでの終端から二番目のアイテムセットか否かを判定する（ステップＳ３４５３）。ここで、終端から二番目のアイテムセットではないと判定した場合には（ステップＳ３４５３；Ｎｏ）、ステップＳ３４５１に再び戻り、次のアイテムセットを処理対象とする。一方、ステップＳ３４５３において、終端から二番目のアイテムセットに該当すると判定した場合には（ステップＳ３４５３；Ｙｅｓ）、図１０のステップＳ３４７の処理に移行する。
【０１０８】
上述した記憶優先格納処理の動作例を、図３に示した系列データ集合を用いて説明する。まず、ステップＳ３４２、Ｓ３４３の処理により得られた各系列データについての射影位置（同順射影位置、異順射影位置）が、図１２−１、図１３−１、図１４−１に示す状態にあるとする。ここで、点線で囲まれた数値は、ステップＳ３４２で取得された同順射影位置を示しており、実線で囲まれた数値は、ステップＳ３４３で取得された異順射影位置を示している。ただし、前述のとおり同順射影位置として記憶されている位置は、実際に射影が行われる実同順射影位置ではなく、実同順射影位置を特定するために必要なアイテム位置を示している。なお、図１３−１に示したように、系列データ＜（ｂｄｅ）（ａｃｄ）（ａｃｄ）＞では、同順射影位置として記憶される位置は存在しないので、異順射影位置のみが記されている。
【０１０９】
ここで、図１２−２、図１３−２、図１４−２は、夫々図１２−１、図１３−１、図１４−１で示した各系列データに、ステップＳ３４５の記憶優先格納処理を施した結果を示した図である。表記については、速度優先方式と同じである。
【０１１０】
図１２−１を参照すると、最初のアイテムセット（ａｃｅ）に対応する異順射影位置に、二番目のアイテムセット（ｃｄ）のアイテム位置と重複する位置３、４が含まれている。そのため、ステップＳ３４３で取得された異順射影位置は、記憶優先格納処理が施されることで、図１２−２に示したように、最初の異順射影位置から３、４が削除された状態で射影位置記憶部２４に記憶されることになる。
【０１１１】
また、図１３−１を参照すると、最初のアイテムセット（ｂｄｅ）に対応する異順射影位置に、二番目のアイテムセット（ａｃｄ）のアイテム位置と重複する位置３、４、５が含まれている。そのため、ステップＳ３４３で取得された異順射影位置は、記憶優先格納処理が施されることで、図１３−２に示したように、最初の異順射影位置から３、４、５が削除された状態で射影位置記憶部２４に記憶されることになる。
【０１１２】
また、図１４−１を参照すると、最初のアイテムセット（ａｂ）に対応する異順射影位置に、このアイテムセットの後方に隣接する二番目アイテムセット（ａ）のアイテム位置と重複する位置２が含まれている。また、二番目のアイテムセット（ａ）に対応する異順射影位置に、三番目のアイテムセット（ｃ）のアイテム位置と重複する値３が含まれている。また、三番目のアイテムセット（ｃ）に対応する異順射影位置に、四番目のアイテムセット（ｂｄ）のアイテム位置と重複する位置４、５が含まれている。さらに、四番目のアイテムセット（ｂｄ）に対応する異順射影位置に、五番目のアイテムセット（ｂ）のアイテム位置と重複する位置６が含まれている。
【０１１３】
そのため、ステップＳ３４３で取得された異順射影位置は、記憶優先格納処理が施されることで、図１４−２に示したように、各アイテムセットの異順射影位置から重複した値が削除された状態で射影位置記憶部２４に記憶されることになる。
【０１１４】
このように、記憶領域優先方式を用いることで、速度優先方式と比較し、射影位置として記憶する情報量を削減することが可能であるため、射影位置記憶部２４の記憶領域を効率的に使うことができる。
【０１１５】
図１０に戻り、ステップＳ３４４の処理において、差分方式と判定した場合（ステップＳ３４４；差分）、射影位置取得部２３は、差分格納処理を実行する（ステップＳ３４６）。以下、ステップＳ３４６の差分格納処理について説明する。
【０１１６】
図１５は、ステップＳ３４６の差分格納処理の手順を示したフローチャートである。まず、射影位置取得部２３は、系列データの前方から処理対象とする一つのアイテムセットを順次選択する（ステップＳ３４６１）。
【０１１７】
続いて、射影位置取得部２３は、ステップＳ３４３の処理で射影位置記憶部２４に記憶された速度優先方式の異順射影位置を参照すると、処理対象のアイテムセットに対応付けられた異順射影位置と、このアイテムセットの後方に隣接するアイテムセットのアイテム位置とを比較し、重複した位置を処理対象のアイテムセットに関連付けられた異順射影位置から削除する（ステップＳ３４６２）。
【０１１８】
次いで、射影位置取得部２３は、処理対象のアイテムセットが、系列データ中での終端から二番目のアイテムセットか否かを判定する（ステップＳ３４６３）。なお、ここまでの処理は上述した記憶領域優先方式と同様の手順となっている。ステップＳ３４６３において、終端から二番目のアイテムセットではないと判定した場合には（ステップＳ３４６３；Ｎｏ）、ステップＳ３４６１に再び戻り、次のアイテムセットを処理対象とする。
【０１１９】
一方、ステップＳ３４７３において、終端から二番目のアイテムセットに該当すると判定した場合には（ステップＳ３４６３；Ｙｅｓ）、射影位置取得部２３は、系列データの終端から二番目のアイテムセットから前方方向にかけて処理対象とする一つのアイテムセットを順次選択する（ステップＳ３４６４）。
【０１２０】
続いて、射影位置取得部２３は、処理対象のアイテムセットに対応付けられた異順射影位置と、このアイテムセットの前方に隣接するアイテムセットに対応付けられた異順射影位置とを比較し、重複した位置を処理対象のアイテムセットに対応付けられた異順射影位置から削除する（ステップＳ３４６５）。
【０１２１】
次いで、射影位置取得部２３は、処理対象のアイテムセットが、系列データ中での先頭から二番目のアイテムセットか否かを判定する（ステップＳ３４６６）。ここで、先頭から二番目のアイテムセットではないと判定した場合には（ステップＳ３４６６；Ｎｏ）、ステップＳ３４６４の処理に再び戻り、次のアイテムセットを処理対象とする。
【０１２２】
一方、ステップＳ３４６６において、先頭から二番目のアイテムセットに該当すると判定した場合には（ステップＳ３４６６；Ｙｅｓ）、図１０のステップＳ３４７の処理に移行する。
【０１２３】
上述した差分格納処理の動作例を、系列データ集合＜ａｂｃａｃｂｄｂｂｃ＞、＜（ａｂ）（ａ）（ｃ）（ｂｄ）（ｂ）（ｂｃ）＞を用いて説明する。まず、ステップＳ３４６３迄の処理で得られた系列データ＜ａｂｃａｃｂｄｂｂｃ＞、＜（ａｂ）（ａ）（ｃ）（ｂｄ）（ｂ）（ｂｃ）＞についての射影位置（同順射影位置、異順射影位置）が、夫々図１６−１、１４−２に示す状態にあるとする。なお、図中の表記については図１２−１等と同様である。また、図１６−２、図１６−３は、図１６−１、図１４−２で示した各系列データに、ステップＳ３４６４〜Ｓ３４６６の処理を施した結果を夫々示した図である。
【０１２４】
ここで、図１６−１を参照すると、終端から三番目のアイテムセット（ｂ）に対応する異順射影位置９は、終端から四番目のアイテムセット（ｄ）の異順射影位置９と重複している。また、終端から四番目のアイテムセット（ｄ）に対応する異順射影位置９は、終端から五番目のアイテムセット（ｂ）の異順射影位置９と重複している。また、終端から五番目のアイテムセット（ｂ）に対応する異順射影位置９は、終端から六番目のアイテムセット（ｃ）の異順射影位置９と重複している。また、終端から六番目のアイテムセット（ｃ）に対応する異順射影位置６は、終端から七番目のアイテムセット（ａ）の異順射影位置６と重複している。また、終端から七番目のアイテムセット（ａ）に対応する異順射影位置５、６は、終端から八番目のアイテムセット（ｃ）の異順射影位置５、６と重複している。また、終端から八番目のアイテムセット（ｃ）に対応する異順射影位置５、６は、終端から九番目のアイテムセット（ｂ）の異順射影位置５、６と重複している。さらに、終端から九番目のアイテムセット（ｂ）に対応する異順射影位置３、６は、終端から十番目のアイテムセット、即ち先頭のアイテムセット（ａ）の異順射影位置３、６と重複している。
【０１２５】
そのため、ステップＳ３４３で取得された異順射影位置は、ステップＳ３４６４〜Ｓ３４６６の処理が施されることで、図１６−２に示したように、各アイテムセットの異順射影位置から、前方のアイテムセットに対して重複した位置が削除された状態で射影位置記憶部２４に記憶されることになる。
【０１２６】
また、図１４−２を参照すると、終端から三番目のアイテムセット（ｂｄ）に対応する異順射影位置８は、終端から四番目のアイテムセット（ｃ）の異順射影位置８と重複している。また、終端から五番目のアイテムセット（ａ）に対応する異順射影位置４、５は、終端から六番目のアイテムセット、即ち先頭のアイテムセット（ａｂ）の異順射影位置４、５と重複している。
【０１２７】
そのため、ステップＳ３４３で取得された異順射影位置は、ステップＳ３４６４〜Ｓ３４６６の処理が施されることで、図１６−３に示したように、各アイテムセットの異順射影位置から、前方のアイテムセットに対して重複した位置が削除された状態で射影位置記憶部２４に記憶されることになる。
【０１２８】
このように、差分方式を用いることで、記憶領域優先方式と比較し、射影位置として記憶する情報量をさらに削減することが可能であるため、射影位置記憶部２４の記憶領域をより効率的に使うことができる。なお、差分方式は、基本的に記憶領域優先方式とともに利用されるので、何れの例においても記憶領域優先方式を用いている。また、差分方式は、通常、異順射影位置のみに対して用いるので、この例でも異順射影のみに対して差分方式を適用している。
【０１２９】
図１０に戻り、射影位置取得部２３は、分析対象の系列データ全てを処理したか否かを判定する（ステップＳ３４７）。ここで、未処理の系列データが存在すると判定した場合には（ステップＳ３４７；Ｎｏ）、ステップＳ３４１に再び戻り、未処理の系列データについて射影位置を取得する。一方、ステップＳ３４７において、全ての系列データを処理したと判定した場合には（ステップＳ３４７；Ｙｅｓ）、図８のステップＳ３５の処理に移行する。
【０１３０】
図８に戻り、続くステップＳ３５では、射影部２５が射影処理を実行し、分析対象の各系列データ集合における各系列パタンの頻度を取得する（ステップＳ３５）。以下、ステップＳ３５の射影処理について説明する。なお、以下では、アイテム“ａ”から始まる系列パタンの頻度を調べる処理を説明するが、順次他のアイテムから始まる系列パタンの頻度を調べることで、全頻出系列パタンを列挙することができる。
【０１３１】
図１７は、射影処理の手順を示したフローチャートである。まず、射影部２５は、分析対象の系列データ集合から処理対象とする一つの系列データを選択する（ステップＳ３５１）。次いで、射影部２５は、処理対象の系列データに対応する射影位置からアイテムを取得するアイテム抽出処理を実行する（ステップＳ３５２）。以下、図１８を参照して、ステップＳ３５２のアイテム抽出処理を説明する。
【０１３２】
図１８は、アイテム抽出処理の手順を示したフローチャートである。まず、射影部２５は、前置パタンを構成するアイテムセットのうち、最終アイテムセットが単一のアイテムから構成されているか否かを判定する（ステップＳ３５２１）。
【０１３３】
ステップＳ３５２１において、単一のアイテムから構成されると判定した場合（ステップＳ３５２１；Ｙｅｓ）、射影部２５は、前置パタンの最終アイテムに対応する系列データのアイテム位置に関連付けて記憶された同順射影位置を特定する（ステップＳ３５２２）。次いで、射影部２５は、ステップＳ３５２２で特定した同順射影位置を順次辿ることで、実同順射影位置を得るための基点を設定し（ステップＳ３５２３）、ステップＳ３５２５の処理に移行する。
【０１３４】
一方、ステップＳ３５２１において、複数のアイテムから構成されると判定した場合（ステップＳ３５２１；Ｎｏ）、射影部２５は、系列データのうち前置パタンと一致したアイテムの組みのうち、この前置パタンの最終アイテムに対応するアイテム位置を、実同順射影位置を得るための基点と設定し（ステップＳ３５２４）、ステップＳ３５２５の処理に移行する。
【０１３５】
続くステップＳ３５２５において、射影部２５は、基点に対応するアイテムを含むアイテムセット内において、この基点から後方に探索することで基点後方のアイテム位置を、実際に射影を行う実同順射影位置に設定する（ステップＳ３５２５）。次いで、射影部２５は、ステップＳ３５２５で設定した各実同順射影位置でのアイテムを抽出（取得）する（ステップＳ３５２６）。
【０１３６】
続いて、射影部２５は、前置パタンと一致するアイテムのアイテムセットに関連付けられた異順射影位置を特定すると（ステップＳ３５２７）、この異順射影位置に対応するアイテム位置のアイテムを抽出（取得）し（ステップＳ３５２８）、図１７のステップＳ３５３の処理に移行する。なお、ステップＳ３５２８において、前置パタンに対応する位置が複数存在する場合には、最も前方のアイテムセットに関連付けて記憶された異順射影位置についてアイテムを取得するものとする。
【０１３７】
ここで、上述した射影処理の動作例を、図９に示した系列データ集合＜（ａｃｅ）（ｃｄ）（ａｃｄ）＞、＜（ｂｄｅ）（ａｃｄ）（ａｃｄ）＞、＜（ａｂ）（ａ）（ｃ）（ｂｄ）（ｂ）（ｂｃ）＞を用いて説明する。なお、以下では＜ａ＞を前置パタンとしたときの同順射影位置、異順射影位置の取得について説明する。
【０１３８】
前置パタンが＜ａ＞である場合、最終アイテムセットは単一のアイテム“ａ”のみから構成されているので、射影部２５は、単一アイテムの同順射影位置取得手順（ステップＳ３５２１；Ｙｅｓ）に従い射影位置を取得する。
【０１３９】
まず、図１２−１を参照して、識別番号００１の系列データ＜（ａｃｅ）（ｃｄ）（ａｃｄ）＞の射影位置取得について説明する。まず、射影部２５は、前置パタン＜ａ＞に対応するアイテム位置０を特定すると、このアイテム位置０に関連付けて記憶された同順射影位置を参照する。アイテム位置０に対応する同順射影位置には５が記憶されているので、射影部２５は、次いでアイテム位置５の同順射影位置を参照する。ここで、アイテム位置５の同順射影位置には何も記憶されていないので、射影部２５は、同順射影位置を辿ることを中止する。
【０１４０】
次に、射影部２５は、同順射影位置を辿ることで得られたアイテム位置０、５を基点として探索を行い、実際に射影を行う実同順射影位置を取得する。ここで、アイテム位置０の後方には、アイテム位置１、２が存在し、また、アイテム位置５の後方には、アイテム位置６、７が存在するため、これら１、２、６、７が実際に射影を行う実同順射影位置となる。そのため、射影部２５は、実同順射影位置のアイテムとして各実同順射影位置に対応するアイテム“ｃ”、“ｄ”、“ｅ”を取得する。
【０１４１】
また、射影部２５は、前置パタン＜ａ＞に対応する系列データのアイテム位置０に関連付けて記憶された異順射影位置３、４、５を、実際に射影を行う異順射影位置と設定する。そのため、射影部２５は、異順射影位置のアイテムとして各異順射影位置に対応するアイテム“ａ”、“ｃ”、“ｄ”を取得する。
【０１４２】
次に、図１３−１を参照して、識別番号００２の系列データ＜（ｂｄｅ）（ａｃｄ）（ａｃｄ）＞の射影位置取得について説明する。射影部２５は、前置パタン＜ａ＞に対応するアイテム位置３を特定すると、このアイテム位置３に関連付けて記憶された同順射影位置を参照する。ここで、アイテム位置３に関連付けられた同順射影位置は存在しないため、射影部２５は、同順射影されるアイテムが同一アイテムセット内に全て存在すると判断する。そのため、射影部２５は、アイテム位置３のアイテムセット内において、このアイテム位置３以後のアイテム位置４、５を実同順射影位置に設定し、これら実同順射影位置に対応するアイテム“ｃ”、“ｄ”を取得する。
【０１４３】
また、射影部２５は、前置パタン＜ａ＞に対応する系列データのアイテム位置３に関連付けて記憶された異順射影位置３、４、５を、実際に射影を行う異順射影位置に設定する。そのため、射影部２５は、異順射影位置のアイテムとして各異順射影位置に対応するアイテム“ａ”、“ｃ”、“ｄ”を取得する。
【０１４４】
次に、図１４−１を参照して、識別番号００３の系列データ＜（ａｂ）（ａ）（ｃ）（ｂｄ）（ｂ）（ｂｃ）＞の射影位置取得について説明する。射影部２５は、前置パタン＜ａ＞に対応するアイテム位置０を特定すると、このアイテム位置０に関連付けて記憶された同順射影位置を参照する。ここで、アイテム位置０に関連付けられた同順射影位置は存在しないため、射影部２５は、同順射影されるアイテムが同一アイテムセット内に全て存在すると判断する。そのため、射影部２５は、アイテム位置０のアイテムセット内において、このアイテム位置０以後のアイテム位置１を実同順射影位置に設定し、この実同順射影位置に対応するアイテム“ｂ”を取得する。
【０１４５】
また、射影部２５は、前置パタン＜ａ＞に対応する系列データのアイテム位置０に関連付けて記憶された異順射影位置２、３、４、５を、実際に射影を行う異順射影位置と設定する。そのため、射影部２５は、異順射影位置のアイテムとして各異順射影位置に対応するアイテム“ａ”、“ｂ”、“ｃ”、“ｄ”を取得する。
【０１４６】
なお、＜（ａｃ）＞等、前置パタンが複数のアイテムにより構成される場合には、射影部２５は、複数アイテムの同順射影位置取得手順（ステップＳ３５２１；Ｎｏ）に従い処理を行う。例えば、＜ａｃ＞が前置パタンのとき、識別番号００１の系列データ＜（ａｃｅ）（ｃｄ）（ａｃｄ）＞での対応するアイテム位置は１、６となる。このアイテム位置を基点として、各アイテム位置に対応するアイテムセット内の探索を行うと、アイテム位置１の後方には、アイテム位置２が存在し、アイテム位置６の後方には、アイテム位置７が存在するため、これら２、７が実際に射影を行う実同順射影位置となる。そのため、射影部２５は、実同順射影位置のアイテムとして各実同順射影位置に対応するアイテム“ｄ”、“ｅ”を取得する。
【０１４７】
射影位置を記憶していない場合、前置パタンに後続するアイテムを全て探索しなければ射影位置を得ることができない。しかしながら、本実施形態のように予め射影位置を記憶しておくことで、効率的に射影位置を取得することが可能となる。特にアイテム抽出処理は、射影処理において繰り返し実行されるため、射影位置の効率的な取得を可能にすることで、射影処理全体の効率を上げることが可能となる。
【０１４８】
なお、上記したアイテム抽出処理では、速度優先方式で記憶された射影位置の取得方法を説明している。以下、記憶領域優先方式、差分方式で射影位置が記憶されていた場合での、射影位置の取得方法について説明する。なお、同順射影位置の取得方法は、上述した速度優先方式と同じであるため説明を省略する。
【０１４９】
記憶領域優先方式では、異順射影位置として記憶されている射影位置だけでなく、後方に隣接するアイテムセットに含まれるアイテムの位置も異順射影位置となる。ここで、記憶領域優先方式による射影位置取得の例として、記憶領域優先方式による＜（ａｃｅ）（ｃｄ）（ａｃｄ）＞の射影位置を示した図１２−２を参照し、前置パタンを＜ｃ＞としたときでの異順射影位置について説明する。
【０１５０】
図１２−２に示したように、前置パタン＜ｃ＞に対応するアイテム位置１の異順射影位置は５であることから、この異順射影位置に対応するアイテム位置５は異順射影位置となる。また、前置パタン＜ｃ＞に対応するアイテムセットは、一番目のアイテムセットであるから、その後方に隣接する二番目のアイテムセットに含まれるアイテム位置３、４も異順射影位置となる。
【０１５１】
次に、差分方式での射影位置取得方法について説明する。差分方式では、一番目のアイテムセットの射影位置は、差分方式を用いていないときと同様となるため、そのまま取得することができる。それ以外の射影位置は、一つ前の射影処理において用いた射影位置と、射影元アイテムセットから着目アイテムセットまでに記憶されている射影位置のうち、「着目アイテムの射影位置＋１」より大きい射影位置とが、着目アイテムの射影位置となる。ただし、射影元と射影位置との幅より、射影位置と系列データの最終アイテムセットとの幅の方が短い場合は、記憶されている射影位置を用いず系列データの末端まで探索することで射影位置を取得する。
【０１５２】
また、前置パタンの一番目のアイテムが、系列データの一番目のアイテムセットに対応していない場合は、一番目のアイテムセットから着目アイテムセットまでに記憶されている射影位置のうち、「着目アイテムの射影位置＋１」より大きい射影位置が、着目アイテムの射影位置となる。
【０１５３】
差分方式による射影位置取得の例として、記憶領域優先方式における＜ａｂｃａｃｂｄｂｂｃ＞の射影位置を示した図１６−２を用いて説明する。まず、＜ａｃ＞を前置パタンとしたときの射影位置を考える。この場合、まず＜ａ＞を前置パタンとして射影が行われ、次に＜ａ＞に対応する位置が射影元となり、＜ａｃ＞に射影が行われる。＜ａ＞に対応する系列データのアイテムセットは一番目のアイテムセットなので、そのまま異順射影位置２、３、６を取得することができる。
【０１５４】
さらに、記憶領域優先方式であるため、アイテム位置１も異順射影位置となる。＜ａｃ＞の最終アイテムセットに対応する系列データのアイテム位置は、位置２である。射影元はアイテム“ａ”のアイテム位置０であるから、位置１から位置２までに記憶されている異順射影位置である、位置５と位置４とを取得する。取得した射影位置のうち、位置３より大きい位置は、位置４、５、６であるから、これが＜ａｃ＞を前置パタンとしたときの異順射影位置となる。
【０１５５】
同様に、＜ｂ＞を前置パタンとしたときの射影位置を考える。＜ｂ＞に対応する系列データのアイテム位置は、位置１であり、位置１に記憶されている異順射影位置は５である。また、一番目のアイテムセットの異順射影位置は、位置２、３、６となっている。したがって、位置２より大きな、位置３、５、６が異順射影位置となる。
【０１５６】
差分方式の最後の例として、＜ａｄ＞を前置パタンとしたときの異順射影位置を考える。射影元となる＜ａ＞に対応する位置は０であるが、＜ａｄ＞の最終アイテムに対応するアイテムセットはアイテム位置６であり、その差は６である。一方、系列データの最終アイテムの位置は９であり、射影元より系列データの最終アイテムとの距離の方が短い。この様なケースでは、系列データの最終アイテムまで探索することで、異順射影位置を取得する。
【０１５７】
図１７に戻り、射影部２５は、現在の前置パタンについて、分析対象の全ての系列データにステップＳ３５２の処理を施したか否かを判定する（ステップＳ３５３）。ここで、未処理の系列データが存在すると判定した場合（ステップＳ３５３；Ｎｏ）、ステップＳ３５１の処理に再び戻り、未処理の系列データを処理対象とする。一方、ステップＳ３５３において、全ての系列データを処理したと判定した場合（ステップＳ３５３；Ｙｅｓ）、ステップＳ３５４の処理に移行する。
【０１５８】
ここで、図１９は、＜（ａｃｅ）（ｃｄ）（ａｃｄ）＞、＜（ｂｄｅ）（ａｃｄ）（ａｃｄ）＞、＜（ａｂ）（ａ）（ｃ）（ｂｄ）（ｂ）（ｂｃ）＞の夫々の系列データに対し、上述したステップＳ３５２のアイテム抽出処理を施した結果を示した図である。同図では、前置パタンを点線枠で示しており、射影位置を実線枠で示している。なお、同順射影位置については、実際に射影される実同順射影位置ではなく、射影の基点となる位置を実線枠で示している。
【０１５９】
続くステップＳ３５４において、射影部２５は、ここまでの処理で取得したアイテムが、頻出であるか否かを判定する（ステップＳ３５４）。ここで、分析対象の系列データ集合＜（ａｃｅ）（ｃｄ）（ａｃｄ）＞、＜（ｂｄｅ）（ａｃｄ）（ａｃｄ）＞、＜（ａｂ）（ａ）（ｃ）（ｂｄ）（ｂ）（ｂｃ）＞についてのアイテムの出現回数を纏めると、同順射影については図２０、異順射影については図２１のようになる。なお、図２０、図２１において、○印は列名が示す系列データに、行名が示すアイテムが存在していることを表しており、×印は行名が示すアイテムが存在しないことを表している。
【０１６０】
ステップＳ３５４の判定では、最小支持度入力部２２から入力された最小支持度以上出現するアイテムを頻出とするから、例では、二回以上出現しているアイテムを頻出と判定する。したがって、同順射影での頻出アイテムは“ｃ”と“ｄ”、異順射影での頻出アイテムは“ａ”、“ｃ”、“ｄ”となる。この場合、頻出アイテムが存在するので（ステップＳ３５４；Ｙｅｓ）、ステップＳ３５５の処理に移行する。
【０１６１】
ステップＳ３５５において、射影部２５は、頻出アイテムの射影位置をスタックに記憶し（ステップＳ３５５）、ステップＳ３５８の処理に移行する。なお、スタックに記憶された頻出アイテムの射影位置は、後述するステップＳ３５７の処理で利用される。また、スタックに記憶される射影位置のうち、ステップＳ３５８の処理で新たな前置パタンの生成に用いられる頻出アイテムの射影位置については、スタックに記憶させる必要はない。
【０１６２】
本例では、識別子０００１の系列データについて、同順射影位置１と６と７、異順射影位置３と４と５をスタックに記憶し、識別子０００２の系列データについて、同順射影位置４と５、異順射影位置６と７と８をスタックに記憶し、識別子０００３の系列データについて、異順射影位置２と３と５をスタックに記憶する。同順射影において、ひとつの頻出アイテムに対して複数の射影位置が存在する場合、全ての射影位置を組にして記憶する。例えば、識別子０００１の同順射影のアイテム“ｃ”には、位置１と６の二つを組にして記憶する。
【０１６３】
図２２に、頻出する射影位置を二重線枠で示した。ここで、図２２は、図１９と対応する図であって、＜（ａｃｅ）（ｃｄ）（ａｃｄ）＞、＜（ｂｄｅ）（ａｃｄ）（ａｃｄ）＞、＜（ａｂ）（ａ）（ｃ）（ｂｄ）（ｂ）（ｂｃ）＞の夫々の系列データを示している。なお、上述したようにステップＳ３５８の処理で新たな前置パタンを構成するアイテムについては、位置をスタックに記憶させる必要はない。図２２の例では、識別子０００１の同順射影の位置１と６、識別子０００２の同順射影の位置４がステップＳ３５８の処理で新たな前置パタンを構成するアイテムとなるため、スタックに記憶させる必要はない。
【０１６４】
分析対象として長大な系列データを扱う場合には、スタックに記憶される射影位置の記憶領域も大きくなる。このような場合は、頻出アイテムの射影位置ではなく、前置パタンの最終アイテムの位置と、次に前置パタンを構成するアイテムのみを記憶する。この方法を用いる場合、後述するステップＳ３５７では、再度射影位置から頻出アイテムを取得し、記憶されているアイテムの次のアイテムを、ステップＳ３５８で新たに前置パタンを構成する頻出アイテムとする。
【０１６５】
続くステップＳ３５８では、射影部２５は、前置パタンと頻出アイテムを連結させて新たな前置パタンを生成する（ステップＳ３５８）。連結させる頻出アイテムには、まだ前置パタンと連結されていないアイテムのうち、射影順序の優先度がもっとも高いアイテムを用いる。例えば、頻出アイテムの射影順序は、同順射影の“ｃ”、“ｄ”次に異順射影の“ａ”、“ｃ”、“ｄ”という順になるから、同順射影のアイテム“ｃ”を連結させる頻出アイテムとする。初回の処理では前置パタンは＜ａ＞であるため、同順射影のアイテム“ｃ”と連結させると、＜(ａｃ)＞が新たな前置パタンとして生成される。
【０１６６】
続いて、頻出系列パタン出力部２６は、ステップＳ３５８で生成された前置パタンを、頻出系列パタンとして出力した後（ステップＳ３５９）、ステップＳ３５１に戻り、新たに生成された前置パタンを用いてステップＳ３５１〜３５９の処理を繰り返す。
【０１６７】
前置パタン＜(ａｃ)＞は、識別子０００１と０００２の系列データに存在し、識別子０００３の系列データには存在しない。そのため、＜(ａｃ)＞を前置パタンとした一連の射影処理では、識別子０００１と０００２の系列データのみが処理対象となる。なお、処理手順は＜ａ＞を前置パタンとしたときと同じである。
【０１６８】
図２３は、前置パタンが＜(ａｃ)＞のときの、射影位置を示した図である。なお、前置パタンを点線枠で示し、ステップＳ３５２の処理で得られる射影位置を実線枠で示している。ここで、識別子０００１の系列データには、前置パタンに対応する位置が二箇所あるため、アイテム位置５は前置パタンの一部となり、異順射影位置ともなる。
【０１６９】
図２４は、図２３に対応する図であって、ステップＳ３５４において頻出と判定されたアイテムを二重線枠で示したものである。射影順序は、同順射影の“ｄ”、異順射影の“ａ”、“ｃ”、“ｄ”の順であるから、ステップＳ３５８で新たに生成される前置パタンは＜(ａｃｄ)＞となる。
【０１７０】
図２５は、前置パタンが＜(ａｃｄ)＞のときの、射影位置を示した図である。なお、前置パタンを点線枠で示し、ステップＳ３５２の処理で得られる射影位置を実線枠で示している。ここで、識別子０００１を参照すると、アイテム位置５のみが前置パタンに対応するため、射影位置に該当するアイテムは存在しない。また、識別子０００３には、前置パタンに対応するものが存在しないため、射影位置に頻出と判定されるアイテム、即ち、２回以上出現するアイテムは存在しない。この場合、射影部２５は、ステップＳ３５４の処理において、頻出アイテムが存在しないと判定するため（ステップＳ３５４；Ｎｏ）、ステップＳ３５６の処理に移行する。
【０１７１】
続くステップＳ３５６において、射影部２５は、スタックが空であるか否かを判定する（ステップ３５６）。頻出となる可能性のあるパタンを全て探索し終えると、スタックに何も記憶されていない状態となる。そのため、射影部２５は、スタックが空と判定した場合（ステップＳ３５６；Ｙｅｓ）、射影処理を終了する。
【０１７２】
一方、ステップＳ３５６において、スタックが空ではないと判定した場合（ステップＳ３５６；Ｎｏ）、射影部２５は、スタックに記憶された頻出アイテムの射影位置を取得するとともに、この取得した射影位置をスタック上から削除する（ステップＳ３５７）。
【０１７３】
ステップＳ３５７の処理でスタックから得られるのは、一つ前に用いられた前置パタンで射影したときの頻出アイテムのアイテム位置である。ここで得られた位置の中から、この時点で用いられている前置パタンを生成するのに使われたアイテムの次に射影の優先度が高いアイテムの位置を取得し、ステップＳ３５８の処理に移行する。そして、射影部２５は、ステップＳ３５８において、ステップＳ３５７で取得したアイテム位置に対応するアイテムを用いて、新たな前置パタンを生成する。
【０１７４】
例では、この時点において、＜(ａｃ)＞を前置パタンとしたときの頻出する射影位置が記憶されている。この時点の前置パタン＜(ａｃｄ)＞を生成するのに同順射影の“ｄ”を使ったので、この次に射影の優先度が高い異順射影の“ａ”の位置を取得する。この位置は、識別子０００１の系列データではアイテム位置５であり、識別子０００２の系列データではアイテム位置６である。
【０１７５】
上述したように、射影部２５は、ステップＳ３５８において新たな前置パタンを生成する。ただし、ステップＳ３５８からステップＳ３５９に進んだ場合、新たな前置パタンを生成するのに使われる前置パタンは、この時点における前置パタンの最終アイテムを削除したものになる。例では、この時点の前置パタンは＜(ａｃｄ)＞であるから、新たな前置パタンを生成するのに利用される前置パタンは、＜(ａｃ)＞となる。連結されるアイテムは、異順射影の“ａ”であるから、新たに生成される前置パタンは＜(ａｃ)ａ＞である。前置パタンを生成した後、ステップＳ３５１の処理に再び戻る。
【０１７６】
なお、図２６−１は、前置パタンが＜(ａｃ)ａ＞のときの射影位置を示した図である。ここでは、図２５と同様、前置パタンを点線枠で示し、ステップＳ３５２の処理で得られる射影位置を実線枠で示している。また、図２６−２は、図２６−１に対応する図であって、図２６−１に示した射影位置において、ステップＳ３５４で頻出と判定されたアイテムを二重線枠で示したものである。
【０１７７】
以下、同様の処理を、スタックが空になり、且つ、頻出アイテムが存在しなくなるまで繰り返す。前述の処理を繰り返すと、例では、＜(ａｃ)(ａｃ)＞、＜(ａｃ)(ａｃｄ)＞、＜(ａｃ)(ａｄ)＞、＜(ａｃ)ｃ＞、＜(ａｃ)(ｃｄ)＞、＜(ａｃ)ｄ＞、＜(ａｄ)＞、＜ａａ＞、＜ａ(ａｃ)＞、＜ａ(ａｃｄ)＞、＜ａ(ａｄ)＞、＜ａｃ＞、＜ａ(ｃｄ)＞、＜ａｃｃ＞、＜ａｃｄ＞、＜ａｄ＞、＜ａｄｃ＞という順に前置パタンが生成される。
【０１７８】
図２７−１は、前置パタンが＜(ａｃ)(ａｃ)＞のときの射影位置を示した図である。なお、図２５と同様、前置パタンを点線枠で示し、ステップＳ３５２の処理で得られる射影位置を実線枠で示している（以下、図２２−１、２３−１、２４−１、２５−１、２６−１、２７−１、２８−１、２９−１、３０−１、３１−１、３２−１、３３−１、３４−１、３５−１、３６−１、３７−１、３８−１も同様である）。また、図２７−２は、図２７−１に対応する図であって、図２７−１に示した射影位置において、ステップＳ３５４で頻出と判定されたアイテムを二重線枠で示したものである。
【０１７９】
図２８は、前置パタンが＜(ａｃ)(ａｃｄ)＞のときの射影位置を示した図である。また、図２９は、前置パタンが＜(ａｃ)(ａｄ)＞のときの射影位置を示した図である。これらの場合、図面から明らかなように、頻出アイテムは存在しない。
【０１８０】
図３０−１は、前置パタンが＜(ａｃ)ｃ＞のときの射影位置を示した図である。また、図３０−２は、図３０−１に対応する図であって、図３０−１に示した射影位置において、ステップＳ３５４で頻出と判定されたアイテム“ｄ”を二重線枠で示したものである。
【０１８１】
図３１は、前置パタンが＜(ａｃ)(ｃｄ)＞のときの射影位置を示した図である。また、図３２は、前置パタンが＜(ａｃ)ｄ＞のときの射影位置を示した図である。また、図３３は、前置パタンが＜(ａｄ)＞のときの射影位置を示した図である。これらの場合、図面から明らかなように、頻出アイテムは存在しない。
【０１８２】
図３４−１は、前置パタンが＜ａａ＞のときの射影位置を示した図である。また、図３４−２は、図３４−１に対応する図であって、図３４−１に示した射影位置において、ステップＳ３５４で頻出と判定されたアイテム“ｃ”、“ｄ”を二重線枠で示したものである。
【０１８３】
図３５−１は、前置パタンが＜ａ(ａｃ)＞のときの射影位置を示した図である。また、図３５−２は、図３５−１に対応する図であって、図３５−１に示した射影位置において、ステップＳ３５４で頻出と判定されたアイテム“ｄ”を二重線枠で示したものである。
【０１８４】
図３６は、前置パタンが＜ａ(ａｃｄ)＞のときの射影位置を示した図である。また、図３７は、前置パタンが＜ａ(ａｄ)＞のときの射影位置を示した図である。これらの場合、図面から明らかなように、頻出アイテムは存在しない。
【０１８５】
図３８−１は、前置パタンが＜ａｃ＞のときの射影位置を示した図である。また、図３８−２は、図３８−１に対応する図であって、図３８−１に示した射影位置において、ステップＳ３５４で頻出と判定されたアイテム“ｄ”、“ｃ”を二重線枠で示したものである。
【０１８６】
図３９は、前置パタンが＜ａ(ｃｄ)＞のときの射影位置を示した図である。また、図４０は、前置パタンが＜ａｃｃ＞のときの射影位置を示した図である。また、図４１は、前置パタンが＜ａｃｄ＞のときの射影位置を示した図である。これらの場合、図面から明らかなように、頻出アイテムは存在しない。
【０１８７】
図４２−１は、前置パタンが＜ａｄ＞のときの射影位置を示した図である。また、図４２−２は、図４２−１に対応する図であって、図４２−１に示した射影位置において、ステップＳ３５４で頻出と判定されたアイテム“ｃ”を二重線枠で示したものである。また、図４３は、前置パタンが＜ａｄｃ＞のときの射影位置を示した図である。この場合、図面から明らかなように、頻出アイテムは存在しない。
【０１８８】
前置パタン＜ａｄｃ＞まで射影処理を行うと、ａから始まる前置パタンを生成可能なアイテムは出現しなくなり、且つ、スタックも空になるので、射影部２５は、一連の射影処理を終了する。
【０１８９】
なお、上記した例では、アイテム“ａ”についての処理は終了しているため、例えば、次に“b”を先頭とする頻出系列パタン発見処理を行い、順次“ｃ”、“ｄ”、“e”にも同様の処理を続けて、“e”から始まる頻出系列パタン発見処理が終了した時点で、本処理を終了する。
【０１９０】
以上のように、第１の実施形態によれば、系列データを構成するアイテムに対し、射影時において抽出の対象となるアイテムを特定するための射影位置を関連付けて記憶しておくことで、射影に関係ないアイテムについての探索時間を削減し、射影を行うアイテム位置を効率的に取得することができるため、射影にかかる処理を効率的に行うことができる。特に、アイテムの種類が系列パタン内に同時に出現するアイテムの平均数と比較して少ない系列データや、同一系列データ内に繰り返し同一のアイテムが出現する系列データ集合について有効である。
【０１９１】
［第２の実施形態］
以下、系列パタン抽出装置の第２の実施形態について、第１の実施形態との差分を中心に説明する。なお、上述した第１の実施形態と同様の構成については、同一の符号を付与し、その説明は省略する。
【０１９２】
図４４は、第２の実施形態にかかる系列パタン抽出装置２００の機能構成を示した図である。同図に示したように、系列パタン抽出装置２００は、系列データ記憶部２１と、最小支持度入力部２２と、射影位置取得部３１と、射影位置記憶部３２と、射影部３３と、頻出系列パタン出力部２６とを備えている。なお、系列パタン抽出装置２００のハードウェア構成は、図１と同様である。
【０１９３】
射影位置取得部３１は、射影位置取得部２３と同様の機能を備えるとともに、二つのアイテムから構成される系列パタンが頻出であるときに、その二つのアイテムを接続するための射影位置を射影位置記憶部３２に記憶する。以下、このような射影位置の記憶方式を、「頻出位置記憶方式」と呼ぶ。また、二つのアイテムから構成される系列パタン（例えば、＜ａｂ＞や＜(ａｃ)＞）を、「対パタン」と呼び、対パタンに対応する射影位置を「対射影位置」と呼ぶ。
【０１９４】
頻出位置記憶方式の例として、系列データ＜ｂｄ(ａｃ)＞において、＜ｂａ＞は頻出であるが、＜ｂｃ＞は頻出でない場合、アイテム位置０のアイテム“ｂ”に記憶されている射影位置を考える。この場合、アイテム“ａ”を示す射影位置２は記憶させるが、アイテム“ｃ”を示す射影位置３は記憶させない。なお、系列パタンが頻出か非頻出かの判定は、射影部３３による頻出判定結果を用いるものとする。
【０１９５】
頻出位置記憶方式では、異順射影位置をアイテム毎に記憶させた速度優先方式を採用する。前述の速度優先方式では、基本的に、異順射影位置は、後続するアイテムセットに含まれるアイテムとの関係から、アイテムセット毎に一意に定めることが可能である。一方、頻出位置記憶方式では、射影位置は、後続するアイテムセットに含まれるアイテムとの関係に加えて、それらのアイテムとの組み合わせが頻出系列パタンとなっているかに依存している。そのため、異順射影位置をアイテム毎に記憶させる必要がある。なお、記憶領域を節約するために、異順射影位置をアイテム毎に記憶させた記憶領域優先方式を採用することも可能であるが、後方に隣接するアイテムセットのアイテム全てにアクセスすることになるため、効率は低下する。また、差分方式と併用することも可能であるが、効率は低下する。そのため、以下では速度優先方式に基づいた頻出位置記憶方式を採用することを前提として説明を行う。
【０１９６】
アイテム毎の対パタンの頻度にあまりばらつきがない場合、同一アイテムセット内のアイテムに関連付けられて記憶されている異順射影位置は、アイテムセット内で共通するものが多くなる。そこで、このような場合には、アイテムセット毎に、共通する異順射影位置を纏めて記憶する。なお、頻出位置記憶方式での異順射影位置は、最後から二番目のアイテムセットにも記憶させる。
【０１９７】
図４５は、頻出位置記憶方式の例として、頻出する対パタンが＜(ａｂ)＞、＜(ｂｄ)＞、＜ａａ＞、＜ａｃ＞、＜ａｄ＞、＜ｂｃ＞、＜ｂｄ＞、＜ｃｃ＞、＜ｃｄ＞であるときの、系列データ＜(ａｂ)(ａ)(ｃ)(ｂｄ)(ｂ)(ｂｃ)＞の射影位置を示した図である。同図において、点線で囲んだ数値は同順射影位置として記憶されている位置を示し、実線で囲んだ数値はアイテム毎の異順射影位置として記憶されている位置を示し、二重線で囲んだ数値はアイテムセット毎に共通の異順射影位置を示している。なお、アイテム毎の異順射影位置については後述する。
【０１９８】
また、射影位置取得部３１は、上述した速度優先方式の射影位置取得手順に加えて、非頻出な対射影位置を削除する処理を行う。速度優先方式の射影位置を記憶する際に、非頻出な対射影位置を削除してもよいし、すでに速度優先方式の射影位置が記憶されているのであれば、記憶されている射影位置の中から、非頻出な対射影位置を削除することで、頻出位置記憶方式による射影位置の記憶状態を生成してもよい。以下では、すでに速度優先方式による射影位置が記憶されている状態から、非頻出な対射影位置を削除する方法を説明する。
【０１９９】
同順射影位置から非頻出な対射影位置を削除する際の処理（同順射影位置削除処理）について説明する。図４６は、同順射影位置削除処理の手順を示したフローチャートである。本処理では、例として、系列データ＜（ｂｄｅ）（ａｂｄ）（ｂｃｄ）（ｂｃｄｅ）＞について、非頻出な対パタンが＜（ｂｃ）＞のときの同順射影位置を削除する場合を考える。また、以下では、読み込んだデータを行列に記憶させて処理する方法を説明するが、同等の処理が可能であれば別のデータ構造を用いてもよい。
【０２００】
まず、射影位置取得部３１は、系列データを構成するアイテムセットに含まれた各アイテム位置をＲＡＭ１３等に記憶することで、この系列データについてのアイテム位置行列を生成する（ステップＳ４１）。ここで、アイテム位置行列全体を生成する必要はなく、非頻出な対パタンの一番目のアイテムのうちアイテム順序が最も前のアイテムより、前方のアイテムの行は不要である。例えば、アイテム行“ａ”、“ｂ”、“ｃ”、“ｄ”があり、非頻出な対パタンが＜（ｃｄ）＞のときは、アイテム“ａ”と“ｂ”の行は生成しなくともよい。
【０２０１】
図４７は、系列データ＜（ｂｄｅ）（ａｂｄ）（ｂｃｄ）（ｂｃｄｅ）＞のアイテム位置行列を示した図である。非頻出な対パタン＜（ｂｃ）＞の一番目のアイテムがｂであるため、アイテム“ａ”の行は生成していない。また、本処理（同順射影位置削除処理）が施される前の系列データ＜（ｂｄｅ）（ａｂｄ）（ｂｃｄ）（ｂｃｄｅ）＞に関連付けられた同順射影位置は、図４８で示した状態にあるものとする。
【０２０２】
図４６に戻り、射影位置取得部３１は、非頻出な対パタンの二番目のアイテム種別に対応する行において、空欄となったセルの位置を特定する（ステップＳ４２）。続いて、射影位置取得部３１は、ステップＳ４２で特定したセルの位置を順次基点とし（ステップＳ４３）、この基点からアイテム位置行列の列方向（行列の下方向）に探索を行い、基点位置以降に空の位置があるか否かを判定する（ステップＳ４４）。
【０２０３】
ステップＳ４４において、空の位置があると判定した場合（ステップＳ４４；Ｙｅｓ）、その空の行を右方に向かって探索し、空でない位置が存在するか否かを判定する（ステップＳ４５）。ここで、全てのセルが空と判定した場合には（ステップＳ４５；Ｎｏ）、ステップＳ４９の処理に移行する。
【０２０４】
また、ステップＳ４５において、アイテム位置が記憶されたセルが存在すると判定した場合（ステップＳ４５；Ｙｅｓ）、射影位置取得部３１は、そのアイテム位置が記憶されたセルが属する列に対パタンのアイテムが二つとも含まれているか否かを判定する（ステップＳ４６）。ここで、対パタンのアイテムが含まれていないと判定した場合には（ステップＳ４６；Ｎｏ）、ステップＳ４９の処理に移行する。
【０２０５】
また、ステップＳ４６において、対パタンのアイテムが二つとも含まれていると判定した場合（ステップＳ４６；Ｙｅｓ）、射影位置取得部３１は、その位置に記憶されている射影位置を新たな同順射影位置とし、従前の同順射影位置と置換した状態で記憶し（ステップＳ４７）、ステップＳ４９の処理に移行する。
【０２０６】
一方、ステップＳ４４において、基点からの列方向に空のセルが存在しないと判定した場合（ステップＳ４４；Ｎｏ）、射影位置取得部３１は、アイテム位置に関連付けて記憶された同順射影位置から、非頻出な対射影位置に該当する同順射影位置を削除し（ステップＳ４８）、ステップＳ４９の処理に移行する。
【０２０７】
続くステップＳ４９では、射影位置取得部３１が、ステップＳ４２で特定した全てのセルの位置を基点としたか否かを判定し、未処理の位置が存在すると判定した場合には（ステップＳ４９；Ｎｏ）、ステップＳ４３に再び戻り未処理の位置を基点とする。また、ステップＳ４９において、射影位置取得部３１が、全ての位置を基点としたと判定した場合には（ステップＳ４９；Ｙｅｓ）、本処理を終了する。
【０２０８】
図４７の例では、ｃ行の一列目と二列目が空欄であるため、ステップＳ４３の処理でこれらの空欄位置が探索の基点となる。ｃ行の一列目から列方向に探索しても、ｄ行とｅ行には位置が記憶されており空欄にはなっていない。したがって、ステップＳ４８の処理で位置０に関連付けて記憶された同順射影位置６は削除される。
【０２０９】
一方、ｃ行の二列目から列方向に探索すると、ｅ行に空欄が見つかる（ステップＳ４４；Ｙｅｓ）。そのため、射影位置取得部３１は、さらにｅ行二列目から右方向に探索を行うと、四列目にアイテム位置が記憶されていると判定する（ステップＳ４５；Ｙｅｓ）。また、四列目には対パタンのアイテムが二つとも含まれている（ステップS４６；Ｙｅｓ）。ここで、対パタンの一番目のアイテム“ｂ”に対応するｂ行の四列目にはアイテム位置９が記憶されているので、射影位置取得部３１は、この値を変更対象であった位置４の同順射影位置に記憶する。結果として、図４８に示した同順射影位置は、図４９に示した同順射影位置へと変更される。
【０２１０】
次に、異順射影位置から非頻出な対射影位置を削除する際の処理（異順射影位置削除処理）について説明する。図５０は、異順射影位置削除処理の手順を示したフローチャートである。本処理では、例として系列データ＜（ｂｄｅ）（ａｂｄ）（ｂｃｄ）（ｂｃｄｅ）＞について、非頻出な対パタンが＜ｂｃ＞、＜ｂｄ＞、＜ｄｃ＞のときの異順射影位置を削除する場合を考える。なお、図５１は、本処理（異順射影位置削除処理）が施される前の系列データ＜（ｂｄｅ）（ａｂｄ）（ｂｃｄ）（ｂｃｄｅ）＞に関連付けられた異順射影位置の状態を示した図である。なお、本処理では、アイテムセット内の各アイテムに関連付けて同順射影位置が記憶されているものとする。
【０２１１】
まず、射影位置取得部３１は、系列データの各アイテム位置（アイテムセット）に関連付けて記憶された異順射影位置を順次参照し（ステップＳ５１）、この異順射影位置に対応するアイテムの種類を系列データ記憶部２１から取得する（ステップＳ５２）。図５１の例では、まず一番目のアイテムセット（アイテム）に関連付けて記憶された異順射影位置３、４、７、５、１２に基づき、夫々対応するアイテム“ａ”、“ｂ”、“ｃ”、“ｄ”、“ｅ”を取得する。
【０２１２】
続いて、射影位置取得部３１は、ステップＳ５２で取得したアイテムのうち、現在参照しているアイテムセットに含まれるアイテムと組み合わせることで、非頻出な対パタンを構成可能なアイテムの異順射影位置を削除する（ステップＳ５３）。
【０２１３】
図５１の例では、一番目のアイテムセットに含まれるアイテム位置０のアイテム“ｂ”は、ステップＳ５２で得られたアイテム位置７のアイテム“ｃ”及びアイテム位置５のアイテム“ｄ”と組み合わせることで、非頻出な対パタン＜ｂｃ＞および＜ｂｄ＞を構成することができる。そのため、射影位置取得部３１は、アイテム位置０に関連付けて記憶されている異順射影位置から７と５を削除する。
【０２１４】
同様に、一番目のアイテムセットに含まれるアイテム位置１のアイテム“ｄ”は、ステップＳ５２で得られたアイテム位置７のアイテム“ｃ”と組み合わせることで、非頻出な対パタン＜ｄｃ＞を構成することができる。そのため、射影位置取得部３１は、アイテム位置１に関連付けて記憶されている異順射影位置から７を削除する。
【０２１５】
続いて、射影位置取得部３１は、アイテムセット毎に共通する異順射影位置を纏め、アイテムセット単位での異順射影位置として対応するアイテムセットと関連付けて射影位置記憶部３２に記憶する（ステップＳ５４）。
【０２１６】
ここで、共通する異順射影位置は、ステップＳ５３において何れのアイテムにおいても削除されなかった異順射影位置である。逆に、アイテム毎に記憶しなければならない異順射影位置は、ステップＳ５３において、何れかのアイテムについて削除された異順射影位置である。なお、各アイテム間で共通しない異順射影位置については、各アイテムに関連付けて記憶する。
【０２１７】
図５１の例では、元の異順射影位置３、４、７、５、１２のうち、アイテム“ｂ”に関して位置７と５が削除され、アイテム“ｄ”に関して位置７が削除されている。したがって、最初のアイテムセットに関連付けて記憶される異順射影位置は、３、４、１２である。一方、アイテム位置１のアイテム“ｄ”には位置５が、アイテム位置２のアイテム“ｅ”には位置７と５が個別に関連付けて記憶される（図５２参照）。
【０２１８】
次いで、射影位置取得部３１は、処理対象としたアイテムセットが、系列データの終端から二番目に該当するものか否かを判定する（ステップＳ５５）。ここで、処理対象としたアイテムセットが終端から二番目ではないと判定した場合（ステップＳ５５；Ｎｏ）、射影位置取得部３１は、ステップＳ５１の処理に再び戻り、次のアイテムセットを処理対象とする。一方、終端から二番目のアイテムセットと判定した場合には（ステップＳ５５；Ｙｅｓ）、本処理を終了する。
【０２１９】
図５１の例では、二回目のループ処理時に、二番目のアイテムセットについてステップＳ５２〜５４の一連の処理が施される。このとき、異順射影位置から得られるアイテム位置６、７、８、１２のうち、非頻出な対パタンを構成するのは、アイテム位置７のアイテム“ｃ”とアイテム位置８のアイテム“ｄ”である。したがって、射影位置取得部３１は、系列データでのアイテム位置４のアイテム“ｂ”について、異順射影位置７と８を削除するとともに、アイテム位置５のアイテム“ｄ”について、異順射影位置７を削除する。
【０２２０】
その結果、二番目のアイテムセットには、アイテムセット単位の異順射影位置として位置６と１２とが関連付けて記憶され、位置３のアイテム“ａ”には異順射影位置７と８、位置５のアイテム“ｄ”には異順射影位置８が個別に記憶される。二番目のアイテムセットは、最後から二番目のアイテムセットであるから、この時点で本処理を終了する。この結果、最終的には図５２に示した異順射影位置が得られる。ここで、異順射影位置（アイテム）が、各アイテムに関連付けて記憶された異順射影位置を意味しており、異順射影位置（アイテムセット）が、アイテムセットに関連付けて記憶された異順射影位置を意味している。
【０２２１】
図４４に戻り、射影位置記憶部３２は、射影位置記憶部２４と同様の機能を有するとともに、射影位置取得部３１により処理が施された射影位置（同順射影位置、異順射影位置）を対応する系列データと関連付けて記憶する。
【０２２２】
射影部３３は、射影位置記憶部３２に記憶された各系列データについての射影位置に基づいて射影を行い、最小支持度以上の頻度となった系列パタンを分析対象の系列データから抽出する。
【０２２３】
なお、射影部３３の動作は、異順射影位置に関して、アイテムセット毎に記憶されている射影位置と、アイテム毎に記憶されている射影位置との二種類を取得する必要があることを除けば、第１の実施形態で説明した速度優先方式の取得方法と同様である。
【０２２４】
以下、射影部３３の射影位置の特定にかかる動作について説明する。なお、射影位置に実際に射影が行われるには、射影位置が頻出であること、つまり、射影位置が最小支持度以上出現していることが必要条件である。そのため、以下の説明では、系列データに関連付けて記憶されている射影位置を頻出であると仮定する。
【０２２５】
例として、系列データ＜（ｂｄｅ）（ａｂｄ）（ｂｃｄ）（ｂｃｄｅ）＞について、非頻出な対パタンが＜（ｂｃ）＞、＜ｂｃ＞、＜ｂｄ＞、＜ｄｃ＞である状況を想定する。なお、このときの同順射影位置と異順射影位置が、図４９と図５２の状態にあるものとする。以下、前置パタンを＜ｄ＞としたときの、実同順射影位置及び異順射影位置の特定方法を説明する。
【０２２６】
図４９及び図５２から明らかなように、前置パタン＜ｄ＞に対応するアイテム位置は１であるから、射影部３３は、このアイテム位置に関連付けて記憶されている同順射影位置と異順射影位置を取得する。ここで、図４９を参照すると、非頻出な対射影位置を削除したため同順射影位置には何も記憶されていない。この場合、上述したようにアイテムセット内のアイテムのみが射影の対象となるため、射影部３３は、実同順射影位置としてアイテム位置２のアイテム“ｅ”を特定する。
【０２２７】
一方、異順射影位置には、アイテムセット毎の異順射影位置と、アイテム毎の異順射影位置とが存在する。そのため、射影部３３は、これら２種類の異順射影位置を夫々取得し、実際に射影を行う異順射影位置とする。
【０２２８】
図５２を参照すると、アイテム位置１のアイテムセットには、アイテムセット毎の異順射影位置３、４、１２が関連付けて記憶されている。そのため、射影部３３は、このアイテムセット毎の異順射影位置３、４、１２を取得する。また、アイテム位置１のアイテム“ｄ”には、アイテム毎の異順射影位置５が関連付けて記憶されている。そのため、射影部３３は、このアイテム毎の異順射影位置５を取得する。したがって、異順射影位置は、アイテム位置３、４、１２、５の各アイテムとなる。
【０２２９】
以下、系列パタン抽出装置２００の動作について説明する。図５３は、系列パタン抽出装置２００の各機能部により実行される頻出系列パタン発見処理の手順を示したフローチャートである。以下の処理では、図３（図９）に示した系列データの集合を分析の対象とし、最小支持度として２が指定された場合を例に説明する。なお、ステップＳ６１〜Ｓ６４の処理については、第１の実施形態で説明した頻出系列パタン発見処理のＳ３１〜Ｓ３４の処理と同様であるため説明は省略する。
【０２３０】
ステップＳ６３又はＳ６４の後、射影位置取得部３１は、射影位置削除処理を実行し、射影位置記憶部３２に記憶された各系列データの射影位置から、非頻出な対射影位置を削除する（ステップＳ６５）。このステップＳ６５で行われる処理は、上述した同順射影位置削除処理（図４６参照）及び異順射影位置削除処理（図５０参照）であるため説明は省略する。なお、同順射影位置取得処理と、異順射影位置取得処理とは個別に実行する態様としてもよいし、同時並列的に実行する態様としてもよい。
【０２３１】
図９に示した系列データ集合の場合、各系列データに含まれている非頻出な対パタンは、＜（ｂｃ）＞、＜ａｂ＞、＜ｂｂ＞、＜ｃｂ＞、＜ｄｂ＞である。また、非頻出な対射影位置を削除する前の各系列データについての射影位置の記憶状態は、上述したように図１２−１、１３−１、１４−１で示される。これらの系列データに対して、ステップＳ６５の処理を施すと、識別子０００３の系列データについてアイテム位置４の同順射影位置７と、一番目と二番目と三番目のアイテムセットの異順射影位置４と、四番目の異順射影位置６と、五番目の異順射影位置７は、非頻出な対射影位置であるため削除される。
【０２３２】
その結果、図９の各系列データの射影位置は、図５４−１、図５４−２、図５４−３のようになる。なお、図５４−１は、識別子０００１の系列データについての同順射影位置とアイテムセット毎の異順射影位置とを示した図である。また、図５４−２は、識別子０００２の系列データについての同順射影位置とアイテムセット毎の異順射影位置とを示した図である。図５４−３は、識別子０００３の系列データについての同順射影位置とアイテムセット毎の異順射影位置とを示した図である。
【０２３３】
続いて、射影部３３は、射影位置記憶部３２に記憶された射影位置に基づいて射影処理を実行し（ステップＳ６６）、本処理を終了する。なお、ステップＳ６６の射影処理は、上述したように異順射影位置についての処理以外は第１の実施形態での射影処理と同様であるため、説明を省略する。
【０２３４】
以下、上記の頻出系列パタン発見処理を図９の各系列パタンに適用した際での、各前置パタンと射影位置との関係を図５５−１から図７５に示す。また、各前置パタンでの頻出射影位置を図５５−２から図７４−２に示す。
【０２３５】
ここで、図５５−１は、前置パタンが＜ａ＞のときの射影位置を示した図である。なお、図１９等と同様、前置パタンを点線枠で示し、射影処理で実際に射影が行われる射影位置を実線枠で示している（以下、図５５−１、５６−１、５７、５８−１、５９−１、６０、６１、６２−１、６３、６４、６５、６６−１、６７−１、６８、６９、７０−１、７１、７２、７３、７４−１、７５も同様である）。また、図５５−２は、図５５−１に対応する図であって、図５５−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。
【０２３６】
図５６−１は、前置パタンが＜ａｃ＞のときの射影位置を示した図である。また、図５６−２は、図５６−１に対応する図であって、図５６−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。
【０２３７】
図５７は、前置パタンが＜(ａｃｄ)＞のときの射影位置を示した図である。この場合、図面から明らかなように、頻出アイテムは存在しない。
【０２３８】
図５８−１は、前置パタンが＜（ａｃ）ａ＞のときの射影位置を示した図である。また、図５８−２は、図５８−１に対応する図であって、図５８−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。
【０２３９】
図５９−１は、前置パタンが＜（ａｃ）（ａｃ）＞のときの射影位置を示した図である。また、図５９−２は、図５９−１に対応する図であって、図５９−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。
【０２４０】
図６０は、前置パタンが＜（ａｃ）（ａｃｄ）＞のときの射影位置を示した図である。また、図６１は、前置パタンが＜（ａｃ）（ａｄ）＞のときの射影位置を示した図である。この場合、図面から明らかなように、頻出アイテムは存在しない。
【０２４１】
図６２−１は、前置パタンが＜（ａｃ）（ｃ）＞のときの射影位置を示した図である。また、図６２−２は、図６２−１に対応する図であって、図６２−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。
【０２４２】
図６３は、前置パタンが＜（ａｃ）（ｃｄ）＞のときの射影位置を示した図である。また、図６４は、前置パタンが＜（ａｃ）（ｄ）＞のときの射影位置を示した図である。また、図６５は、前置パタンが＜（ａｄ）＞のときの射影位置を示した図である。これらの場合、図面から明らかなように、頻出アイテムは存在しない。
【０２４３】
図６６−１は、前置パタンが＜ａａ＞のときの射影位置を示した図である。また、図６６−２は、図６６−１に対応する図であって、図６６−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。
【０２４４】
図６７−１は、前置パタンが＜（ａ）（ａｃ）＞のときの射影位置を示した図である。また、図６７−２は、図６７−１に対応する図であって、図６７−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。
【０２４５】
図６８は、前置パタンが＜（ａ）（ａｃｄ）＞のときの射影位置を示した図である。また、図６９は、前置パタンが＜（ａ）（ａｄ）＞のときの射影位置を示した図である。これらの場合、図面から明らかなように、頻出アイテムは存在しない。
【０２４６】
図７０−１は、前置パタンが＜ａｃ＞のときの射影位置を示した図である。また、図７０−２は、図７０−１に対応する図であって、図７０−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。
【０２４７】
図７１は、前置パタンが＜（ａ）（ｃｄ）＞のときの射影位置を示した図である。また、図７２は、前置パタンが＜ａｃｃ＞のときの射影位置を示した図である。また、図７３は、前置パタンが＜ａｃｄ＞のときの射影位置を示した図である。これらの場合、図面から明らかなように、頻出アイテムは存在しない。
【０２４８】
図７４−１は、前置パタンが＜ａｄ＞のときの射影位置を示した図である。また、図７４−２は、図７４−１に対応する図であって、図７４−１に示した射影位置において、ステップＳ６６の射影処理で頻出と判定されたアイテムを二重線枠で示したものである。また、図７５は、前置パタンが＜ａｄｃ＞のときの射影位置を示した図である。この場合、図面から明らかなように、頻出アイテムは存在しない。
【０２４９】
これらの結果から射影位置に着目すると、ステップＳ６５の処理で非頻出な対射影位置を削除しているため、非頻出な対射影位置を利用した無駄な射影がなくなっていることがわかる。例えば、非頻出な＜ａｂ＞に対応する射影位置を削除しているため、図５５−１の状況では、識別子０００３でのアイテム位置４のアイテム“ｂ”を取得する処理を省略することができる。
【０２５０】
アイテムの種類が系列パタン内に同時に出現するアイテムの平均数と比較して多い系列データでは、非頻出な対射影位置を利用した無駄な射影が多くなる傾向がある。そのため、非頻出な対射影位置を削除し無駄な射影処理を削減することで、このような特性を有する系列データ集合でも計算効率の向上が見込まれる。
【０２５１】
以上のように、第２の実施形態によれば、非頻出であることが明らかな位置を除いて、射影時において抽出の対象となるアイテムを特定するための射影位置をアイテムに関連付けて記憶しておくことで、射影に関係ないアイテムについての探索時間を削減し、射影を行うアイテム位置を効率的に取得することができるため、射影にかかる処理をより効率的に行うことができる。
【０２５２】
なお、本実施形態では、射影位置削除処理（同順射影位置削除処理及び異順射影位置削除処理）を、独立した処理として実行する態様としたが、射影位置取得処理時に行われる態様としてもよい、また、射影部３３に、射影位置取得部３１の射影位置削除処理にかかる機能を付加することで、射影部３３により射影位置削除処理が実行される態様としてもよい。
【０２５３】
［第３の実施形態］
以下、系列パタン抽出装置の第３の実施形態について、第１の実施形態との差分を中心に説明する。なお、上述した第１の実施形態と同様の構成については、同一の符号を付与し、その説明は省略する。
【０２５４】
図７６は、第３の実施形態にかかる系列パタン抽出装置３００の機能構成を示した図である。同図に示したように、系列パタン抽出装置３００は、系列データ記憶部２１と、最小支持度入力部２２と、制約条件入力部４１と、射影位置取得部４２と、射影位置記憶部４３と、射影部４４と、頻出系列パタン出力部２６とを備えている。なお、系列パタン抽出装置３００のハードウェア構成は、図１と同様である。
【０２５５】
制約条件入力部４１は、制約条件の入力を受け付ける機能部である。ここで「制約条件」とは、系列パタンを構成するアイテムの組み合わせを制約するものであって、頻出系列パタンが満たさなければならない条件である。
【０２５６】
例えば、出力される頻出系列パタンは、指定した系列パタンを含まなければならないとする制約や、指定した系列パタンを含んではいけないとする制約が挙げられる。以下、前者の制約を「含有必須制約」と呼び、含まなければならないと指示される系列パタンを「含有必須パタン」と呼ぶ。また、後者の制約を「含有不可制約」と呼び、含んではいけないと指示される系列パタンを「含有不可パタン」と呼ぶ。
【０２５７】
含有必須制約では、例えば、含有必須パタンが＜ａｂ＞である場合、＜（ａｃ）ｂ＞や＜ａｄｂｃ＞等の＜ａｂ＞を含む系列パタンを出力することは許可されるが、＜（ａｃ）ｄ＞や＜ｄｂｃ＞等の＜ａｂ＞を含まない系列パタンの出力については禁止される。
【０２５８】
含有必須制約は、特定の系列パタンを抽出する場合に有効であり、この含有必須制約を用いることで、所望する系列パタンのみを得ることができる。例えば、健康診断データにおいて、飲酒（ａで示す）と高血圧（ｂで示す）の関係に着目している場合、含有必須制約として＜ａ（ａｂ）＞を指定すると、飲酒習慣があって高血圧になった人の生活習慣を調べることができる。
【０２５９】
また、含有不可制約では、例えば、含有不可パタンが＜ａｂ＞である場合、＜（ａｃ）ｄ＞や＜ｄｂｃ＞等の＜ａｂ＞を含まない系列パタンの出力については許可されるが、＜（ａｃ）ｂ＞や＜ａｄｂｃ＞等の＜ａｂ＞を含む系列パタンの出力については禁止される。
【０２６０】
含有不可制約は、除外すべき系列パタンがあるような場合に有効であり、含有不可制約を用いることで、不要な系列パタンを除いた系列パタンを得ることができる。例えば、健康診断データにおいて、高塩分（ａで示す）と高血圧（ｂで示す）の関係には着目していない場合、＜ａ（ａｂ）＞を指定すると、高塩分食品をよく食べていて高血圧になった人を取り除いた系列パタンを調べることができる。
【０２６１】
また、他の制約条件としては、系列パタンを構成するアイテム間の間隔を制約するものが挙げられる。以下、この制約を「間隔制約」と呼ぶ。間隔制約では、系列パタンを構成する全てのアイテム間に間隔を指定してもよいし、特定のアイテム間に間隔を指定してもよい。例えば、アイテム“ａ”と“ｂ”の間隔が１以下でなければならないという指定がされた場合、＜（ａｃ）ｂ＞や＜ｂｄａｃ＞は出力されるが、＜ａｃｄｂ＞や＜ｂ（ｃｄ）ｃａ＞は出力されない。
【０２６２】
間隔制約は、アイテムの時間間隔に着目している場合等に有効に用いることができる。例えば、１年毎に行われる健康診断のデータにおいて、過去二年間の喫煙と高血圧の関係に興味がある場合は、喫煙と高血圧の間隔を１に指定することで、過去二年以内に喫煙し高血圧になった人の系列パタンを調べることができる。
【０２６３】
射影位置取得部４２は、上述した射影位置取得部２３と同様の機能を有するとともに、制約条件入力部４１から入力される制約条件に応じて、射影位置記憶部４３に記憶された射影位置を更新する。
【０２６４】
具体的に、射影位置取得部４２は、制約条件として含有必須制約又は含有不可制約が入力されると、系列データ記憶部２１の系列データに対して含有必須パタン又は含有不可パタンを最も後方に照合し、当該パタンに対応したアイテムのアイテム位置を、系列データと関連付けて射影位置記憶部２４に記憶する。以下、このアイテム位置を「最終制約充足位置」と呼ぶ。
【０２６５】
例えば、系列データが＜ａｂａｂｂ＞のとき、含有必須パタンが＜ａｂ＞であったとすると、アイテム“ａ”に対応するアイテム位置２と、アイテム“ｂ”に対応するアイテム位置４とが最終制約充足位置となる。
【０２６６】
また、射影位置取得部４２は、制約条件として間隔制約が入力されると、射影位置記憶部４３に記憶された異順射影位置のうち、間隔制約で指示された制約を満たさないものを削除する又は修正する。なお、射影位置記憶部４３に射影位置が記憶されていない系列データを処理対象とする場合には、射影位置の取得時において、間隔制約で指示された制約を満たす異順射影位置のみを射影位置記憶部４３に記憶する態様としてもよい。
【０２６７】
以下、間隔制約が入力された際の射影位置取得部４２の動作例として、系列データ＜（ａｂｃｅ）（ｂｃｄ）（ａｂｄ）（ａｂｃｄ）（ｃｄｅ）＞を用いて説明する。なお、この系列データに対応する異順射影位置は、図７−８に示した状態であるものとする。まず、特定種類のアイテムを指定せず、何れのアイテムについても、アイテム間の間隔が特定数以上若しくは以下であることを指定するケースを考える。
【０２６８】
例えば、アイテム間の間隔が０以下と指定された場合、図７−８に示した一番目のアイテムセットの異順射影位置７、４、５、６、１６のうち、アイテム間の間隔が１以上となる二番目のアイテムセットのアイテム位置７、五番目のアイテムセットのアイテム位置１６に射影が行われることはない。また、二番目のアイテムセットの異順射影位置に着目すると、アイテム間の間隔が１以上となる四番目のアイテムセットのアイテム位置１２や、五番目のアイテムセットのアイテム位置１６に射影が行われることはない。また、同様に三番目のアイテムセットの異順射影位置に着目すると、アイテム間の間隔が１以上となる五番目のアイテムセットのアイテム位置１６に射影が行われることはない。
【０２６９】
そのため、射影位置取得部４２は、これらのアイテムセットに関連付けられた異順射影位置から、後方に隣接するアイテムセットのアイテム位置以外のアイテム位置を削除する。なお、図７７は、図７−８の異順射影位置に、アイテム間隔０以下の間隔制約を適用した結果を示した図である。
【０２７０】
また、アイテム間の間隔が１以上であると指定された場合、図７−８に示した一番目のアイテムセットの異順射影位置７、４、５、６、１６のうち、後方に隣接する二番目のアイテムセットのアイテム位置４、５、６に射影が行われることはない。また、二番目のアイテムセットの異順射影位置に着目すると、後方に隣接する三番目のアイテムセットのアイテム位置７、８、９に射影が行われることはない。また、同様に三番目のアイテムセットの異順射影位置に着目すると、後方に隣接する四番目のアイテムセットのアイテム位置１０、１１、１２、１３に射影が行われることはない。
【０２７１】
そのため、射影位置取得部４２は、これらのアイテムセットに関連付けられた異順射影位置から、後方に隣接するアイテムセットのアイテム位置を削除する。なお、図７８は、図７−８の異順射影位置に、アイテム間隔１以下の間隔制約を適用した結果を示した図である。
【０２７２】
次に、特定種類のアイテム間について、アイテム間の間隔が特定数以上もしくは以下であることが指定された場合を考える。このような場合、第２の実施形態で説明した射影位置の記憶方式を利用する。例えば、間隔制約として、順序が＜ａｂ＞であり、且つ、アイテム“ａ”とアイテム“ｂ”の間隔のみ１以上と指定された場合、射影位置取得部４２は、アイテム“ａ”から後方に隣接するアイテムセットに存在するアイテム“ｂ”への異順射影位置を削除するため、その結果は図７９の状態となる。
【０２７３】
なお、上記では速度優先方式を利用した場合について説明したが、記憶領域優先方式や頻出位置記憶方式でも同様に扱うことができる。また、複数種類の制約が指定されている場合は、適宜他の制約で用いられる射影位置記憶方式と併用させることができる。
【０２７４】
図７６に戻り、射影位置記憶部４３は、射影位置記憶部２４と同様の機能を有するとともに、射影位置取得部４２により処理が施された射影位置（同順射影位置、異順射影位置）を対応する系列データと関連付けて記憶する。
【０２７５】
射影部４４は、射影部２５と同様の機能を有するとともに、制約条件入力部４１より入力された制約条件に基づいて、分析対象の系列データ集合に対し射影を行う。なお、射影部４４の動作（射影処理）については、後述する。
【０２７６】
以下、系列パタン抽出装置３００の動作について説明する。図８０は、系列パタン抽出装置３００の各機能部により行われる頻出系列パタン発見処理の手順を示したフローチャートである。
【０２７７】
まず、最小支持度入力部２２は、最小支持度を射影位置取得部４２及び射影部４４に入力する（ステップＳ７１）。なお、最小支持度が割合として指定されていた場合には、最小支持度入力部２２は頻度に変換した後、出力を行うものとする。
【０２７８】
次いで、制約条件入力部４１は、制約条件を射影位置取得部４２及び射影部４４に出力する（ステップＳ７２）。なお、制約条件として指示される含有必須制約には、含有必須パタンが含まれているものとする。また、制約条件として指示される含有不可制約には、含有不可パタンが含まれているものとする。また、制約条件として指示される間隔制約には、アイテム間の間隔や、特定のアイテム種別等の条件が含まれているものとする。
【０２７９】
次いで、射影位置取得部４２は、系列データ記憶部２１に記憶された分析対象の各系列データに含まれるアイテムから、ステップＳ７１で入力された最小支持度未満となるアイテムを削除する（ステップＳ７３）。
【０２８０】
次いで、射影位置取得部４２は、分析対象の各系列データ集合に関連する射影位置が射影位置記憶部４３に記憶されているかを判定する（ステップＳ７４）。ここで、射影位置記憶部４３に射影位置が記憶されていると判定した場合には（ステップＳ７４；Ｙｅｓ）、ステップＳ７６の処理に直ちに移行する。
【０２８１】
一方、ステップＳ７４において、射影位置記憶部４３に射影位置が記憶されていないと判定した場合（ステップＳ７４；Ｎｏ）、射影位置取得部４２は、系列データ記憶部２１に記憶された分析対象の各系列データに対し、射影位置取得処理を実行する（ステップＳ７５）。なお、ステップＳ７５の射影位置取得処理は、上述した第１実施形態の射影位置取得処理（図１０参照）と同様であるため説明を省略する。また、第２の実施形態で説明した射影位置削除処理を併せて行う態様としてもよい。
【０２８２】
続いて、射影位置取得部４２は、ステップＳ７２で入力された制約条件が、間隔制約か否かを判定する（ステップＳ７６）。ここで、制約条件が含有必須制約又は含有不可制約であると判定した場合（ステップＳ７６；Ｎｏ）、射影位置取得部４２は、系列データの後方から含有必須パタン又は含有不可パタンを照合することで、最終制約充足位置を取得し、この系列データと関連付けて射影位置記憶部４３に記憶する（ステップＳ７７）。
【０２８３】
ここで、系列データ＜（ａｂｃｅ）（ｂｃｄ）（ａｂｄ）（ａｂｃｄ）（ｃｄｅ）＞を用いてステップＳ７７の処理を説明する。なお、この系列データの射影位置は、図５−５、図７−８に示した状態であるものとする。このとき、含有必須パタンが＜ａｂｃ＞であったとすると、系列データ＜（ａｂｃｅ）（ｂｃｄ）（ａｂｄ）（ａｂｃｄ）（ｃｄｅ）＞の後方から照合して行くことで、図８２に示したように最終制約充足位置は７、１１、１４となる。
【０２８４】
図８０に戻り、射影部４４は、ステップＳ７２で入力された制約条件が、含有必須制約か含有不可制約かを判定する（ステップＳ７８）。ここで、含有必須制約と判定した場合（ステップＳ７８；必須）、射影部４４は、含有必須射影処理を実行する（ステップＳ７９）。以下、ステップＳ７９の含有必須射影処理について説明する。
【０２８５】
図８１は、含有必須射影処理の手順を示したフローチャートである。まず、射影部４４は、前置パタンと含有必須パタンとを先頭から照合し、前置パタンを構成するアイテムのうち、どのアイテムまで含有必須パタンの条件を満たしているかを確認する（ステップＳ７９０１）。なお、前置パタンの制約充足度合いの確認は、前置パタン生成時に行うことで、より効率的に実行することが可能である。さらに、前置パタンと含有必須パタンがどれだけ一致したかを示すポインタを用いることで、より効率的に実行することが可能となる。
【０２８６】
続いて、射影部４４は、系列データ記憶部２１に記憶された分析対象の系列データ集合から、処理対象とする系列データを一つ選択する（ステップＳ７９０２）。
【０２８７】
次に、射影部４４は、含有必須パタンにおいて、前置パタンに包含されていないアイテムのうち、もっとも先頭のアイテムに対応する最終制約充足位置を取得する（Ｓ７９０３）。なお、前置パタンが＜ａｃｂ＞、含有必須パタンが＜ａｂ＞のように、既に前置パタンが制約を満たしている場合、この処理は不要である。
【０２８８】
ここで、図８２、図８３を参照しながら、ステップＳ７９０１、Ｓ７９０３の処理について説明する。図８３は、前置パタンが＜ａｃｂ＞、含有必須パタンが＜ａｂｃ＞である場合の関係を示した図である。同図に示したように、この場合、含有必須パタンのアイテム“ａ”、“ｂ”は前置パタン＜ａｃｂ＞のアイテム“ａ”“ｂ”により包含される。そのため、射影部４４は、前置パタンに含まれていないアイテムのうち、先頭のアイテムとして、含有必須パタンのアイテム位置２のアイテム“ｃ”を特定する。続いて、射影部４４は、射影位置記憶部４３を参照し、処理対象の系列データに関連付けて記憶された最終制約充足位置から、この含有必須パタンのアイテム“ｃ”に対応する最終制約充足位置１４を取得する。
【０２８９】
図８１に戻り、射影部４４は、処理対象の系列データに関連付けられた同順射影位置に基づいてアイテム抽出処理を実行する（ステップＳ７９０４）。なお、ステップＳ７９０４のアイテム抽出処理は、第１の実施形態で説明したアイテム抽出処理（図１８参照）のうち、ステップＳ３５２１〜Ｓ３５２６の処理と同様であるため説明は省略する。
【０２９０】
続いて、射影部４４は、ステップＳ７９０３で取得した最終制約充足位置に基づき、制約を満たす可能性のあるアイテムの射影位置を特定する（ステップＳ７９０５）。ここでは、記憶されている異順射影位置のうち、ステップＳ７９０３で取得した最終制約充足位置より前方の射影位置を特定する。ただし、ステップＳ７９０１にて、既に前置パタンが制約を満たしていると判定している場合は、全ての射影位置を特定する。
【０２９１】
図８４は、図８２に対応する図であって、系列データ＜（ａｂｃｅ）（ｂｃｄ）（ａｂｄ）（ａｂｃｄ）（ｃｄｅ）＞において、前置パタンが＜ａｃｂ＞のときの前置パタンの位置を点線枠で示した図である。図８４より、前置パタンが＜ａｃｂ＞のとき、この＜ａｃｂ＞に対応する異順射影位置は、三番目のアイテムセットに関連付けられたアイテム位置１０、１１、１２、１３、１６である。そのため、射影部４４は、ステップＳ７９０３で取得した最終制約充足位置１４より前方の異順射影位置、即ち１６を除く、１０、１１、１２、１３を特定する。
【０２９２】
図８１に戻り、射影部４４は、ステップＳ７９０５で特定した異順射影位置のアイテムを取得する（ステップＳ７９０６）。続いて、射影部４４は、現在の前置パタンについて全ての系列データを処理したか否かを判定し、未処理の系列データが存在すると判定した場合には（ステップＳ７９０７；Ｎｏ）、ステップＳ７９０２の処理に再び戻る。また、全ての系列データを処理したと判定した場合には（ステップＳ７９０７；Ｙｅｓ）、ステップＳ７９０８の処理に移行する。
【０２９３】
続くＳ７９０８〜Ｓ７９１３の処理は、上述した射影処理（図１７参照）でのステップＳ３５４〜Ｓ３５９と同様であるため説明を省略する。なお、ステップＳ７９１３の処理において、頻出系列パタン出力部２６は、前置パタンが含有必須パタンを充足する場合にのみ、頻出系列パタンとして出力する。
【０２９４】
このように、予め記憶しておいた射影位置と最終制約充足位置とを用いることで、制約を満たす可能性のあるアイテムのみに射影をすることが可能となるため、含有必須制約を満たし、且つ、利用者が指定した最小支持度以上出現する系列パタン全てを効率的に発見することができる。
【０２９５】
なお、上述したステップＳ７９０１〜Ｓ７９０６の処理は、含有必須パタンが複数ある場合も同様に処理することができるし、他の制約と組み合わせて利用する場合も同様に処理することができる。含有必須パタンが複数ある場合は、含有必須パタン毎に制約を満たす可能性があるかを判定し、何れかの含有必須パタンを含む場合を、制約を満たしていると判断する。
【０２９６】
複数の含有必須パタンを指定する場合、先頭から重複しているアイテムを共通化し、木構造を用いて表現することで、最終制約充足位置の効率的な処理が可能になる。このデータ構造を、「最終制約充足ツリー」と呼ぶ。例えば、含有必須パタンとして＜ｂａ＞と＜ｂｃｂ＞、＜ａｂ＞の三つが指定されているならば、最終制約充足ツリーは図８５のように表すことができる。同図においてアイテムの下に付した数値は、最終制約充足位置を示している。このとき、＜ｂａ＞と＜ｂｃｂ＞の先頭アイテムは共通しているので、一つのノードに纏めることができる。なお、一つに纏めたノードには、最も値の大きな最終制約充足位置を記憶させる。この例では、＜ｂａ＞の先頭アイテムの最終制約充足位置は８で、＜ｂｃｂ＞の最終制約充足位置は１であるため、８を記憶する。
【０２９７】
また、含有必須パタンを複数指定するときは、単一の含有必須パタンが複数指定された場合と、ステップＳ７９０１の処理が異なる。複数指定でのステップＳ７９０１では、まず、前置パタンと最終制約充足ツリーとを照合する。ここでの照合は、基本的にはツリーのルートノードから順に、子ノードの夫々に対して行う。これは、前置パタンと複数の含有必須パタンとを照合させるのと同等の処理であるが、共通化させているため効率的な照合が可能である。
【０２９８】
このとき、前置パタンの最終アイテムに対応するアイテム位置以下の値が記憶されているノードについては、次以降の照合処理は行わないように無効化する。なお、単一指定と同様、どこまで双方のパタンが一致したかを示すポインタを使うことで、より効率的に処理することができる。取得する最終制約充足位置は、前置パタンと一致している末端のノードの子ノードに記憶されている最終制約充足位置のうち、最も大きい値である。また、前置パタンと一致しているアイテムがない場合は、ルートノードの子ノードに記憶されている最終制約充足位置を取得する。なお、ステップＳ７９０４以降の処理は、単一の含有必須パタンについて処理するときと同様である。
【０２９９】
ここで、図８４、図８５を参照して、含有必須パタンが複数指定された場合の動作例を説明するなお、前置パタンは＜ｂ＞であるとする。まず、射影部４４は、図８５に示した最終制約充足ツリーのルートノードの子ノードアイテム“ａ”、“ｂ”と、前置パタン＜ｂ＞とを照合する。この場合、アイテム“ｂ”について一致するので、射影部４４は、子ノード１を辿って照合を終了する。
【０３００】
また、図８４に示した系列データにおいて、前置パタンの最終アイテム“ｂ”のアイテム位置は１なので、ノードの無効化は行わない。ノード１の子ノード（ノード２、３）には、最終制約充足位置１０と５が記憶されており、ルートノードの子ノード（ノード５）には最終制約充足位置７が記憶されているため、射影部４４は、これら最終制約充足位置のうち、最も大きな値となる最終制約充足位置１０を取得する。
【０３０１】
さらに、射影部４４は、前置パタンが＜ｂｂｄ＞となったときには、＜ｂ＞のときと同様にノード１まで照合を行う。図８４に示した系列データにおいて、前置パタンに対応する最終アイテム“ｄ”のアイテム位置は９となるので、射影部４４は、ノード３以下、ノード５以下のノードを無効化する。したがって、得られる最終制約充足位置はアイテム“ａ”の最終制約充足位置１０のみとなり、射影部４４は、この値を取得する。
【０３０２】
なお、特定アイテムが終端に含まれる系列パタンを取得しなければならないといった制約についても、前述の処理を応用することで実現することができる。例えば、終端にアイテム“ｂ”を含むパタンを抽出したい場合には、“ｂ”を含有必須パタンとする含有必須制約を用いるとともに、一度制約充足と判定された後もステップＳ７９０１〜ステップＳ７９０５の処理を行うことで、終端がアイテム“ｂ”となる頻出系列パタンを効率的に発見することができる。
【０３０３】
図８０に戻り、ステップＳ７８において、射影部４４が、ステップＳ７２で入力された制約条件が含有不可制約と判定した場合には（ステップＳ７８；不可）、含有不可射影処理を実行する（ステップＳ８０）。以下、ステップＳ８０の含有不可射影処理について説明する。
【０３０４】
図８６は、含有不可射影処理の手順を示したフローチャートである。まず、射影部４４は、前置パタンと含有不可パタンとを先頭から照合し、前置パタンを構成するアイテムのうち、どのアイテムまで含有不可パタンの条件を満たしているかを確認する（ステップＳ８００１）。以下に続くステップＳ８００２〜Ｓ８０１３の処理は、ステップＳ８００５とステップＳ８００６の処理を除き、図８１で説明した含有必須射影処理でのステップＳ７９０２〜Ｓ７９１３と同様であるため説明を省略する。以下ではステップＳ８００５、ステップＳ８００６の処理についてのみ説明する。なお、含有必須制約の説明と同じく、系列データには、図８２に示した＜（ａｂｃｅ）（ｂｃｄ）（ａｂｄ）（ａｂｃｄ）（ｃｄｅ）＞を用いて説明する。また、特に断りがなければ、例として、前置パタンを＜ａｃｂ＞、含有不可パタンを＜ａｂｃ＞とする。
【０３０５】
ステップＳ８００５において、射影部４４は、射影位置記憶部４３に記憶されている異順射影位置を取得するとともに、ステップＳ８００３で取得した最終制約充足位置に基づき、制約を満たすことが確定したアイテムの異順射影位置を特定する。ここで、射影位置記憶部４３に記憶された異順射影位置のうち、ステップＳ８００３で得られた最終制約充足位置より後方の射影位置が、制約を満たすことが確定したアイテムの射影位置である。
【０３０６】
図８２に示した系列データの例では、アイテム位置１６は、制約充足が確定される。なお、制約充足が確認されたアイテムと結合することで生成された系列パタンが前置パタンとなる場合には、最終制約充足位置と照合することなく、制約充足が確定される。
【０３０７】
続くステップＳ８００６において、射影部４４は、異順射影位置のアイテムを取得し、アイテムの有無と制約充足を確認する。ただし、ステップＳ８００５において、制約充足が確定とされた異順射影位置のアイテムについては、制約充足を確認しない。図８２に示した系列データの例では、アイテム位置１６に対応するアイテム“ｅ”の制約充足は確認しない。
【０３０８】
また、含有不可制約では、制約未充足のパタンの終端にアイテムを結合させて生成されるパタンも制約未充足であるから、制約未充足とされたアイテム、すなわち、前置パタンと結合させることで生成される前置パタンが含有不可パタンを含んでしまうアイテムについては、ステップＳ８００７以降の処理は行わない。
【０３０９】
例えば、前置パタンが＜ａｃｂ＞、含有不可パタンが＜ａｂｃ＞のとき、図８２に示した系列データのアイテム位置１４のアイテム“ｃ”は、前置パタンと結合させることで＜ａｃｂｃ＞となり、含有不可パタンを含んでしまうので、以降の処理を行わない。
【０３１０】
含有不可パタンが複数ある場合も同様に処理することができるし、他の制約と組み合わせて利用する場合も同様に処理することができる。含有不可パタンが複数ある場合は、含有必須制約と同様に、図８５のような最終制約充足ツリーを利用することで、効率的な制約充足確認をすることができる。
【０３１１】
このように、予め記憶しておいた射影位置と最終制約充足位置とを用いることで、含有不可制約を満たすことが確定した系列パタンの制約充足確認の回数を削減して、射影を行うことが可能となるため、含有不可制約を満たし、且つ、利用者が指定した最小支持度以上出現する系列パタン全てを効率的に発見することが可能となる。
【０３１２】
図８０に戻り、ステップＳ７６において、射影位置取得部４２が、制約条件が間隔制約であると判定した場合（ステップＳ７６；Ｙｅｓ）、上述したように間隔制約に応じて射影位置記憶部４３に記憶された異順射影位置を更新する（ステップＳ８１）。続いて、射影位置取得部４２は、射影位置記憶部４３に記憶された射影位置に基づいて、系列データ記憶部２１に記憶された各系列データに間隔射影処理を実行した後（ステップＳ８２）、本処理を終了する。なお、ステップＳ８２の間隔射影処理は、上述したステップＳ３５の射影処理（図１７参照）又はステップＳ６６の射影処理（図５３参照）と同様であるため、説明は省略する。
【０３１３】
このように、予め間隔制約を反映した射影位置を記憶しておくことで、制約を満たさない射影位置への射影を回避することが可能となるため、間隔制約を満たし、且つ、利用者が指定した最小支持度以上出現する系列パタン全てを効率的に発見することができる。
【０３１４】
なお、上述した含有必須制約、含有不可制約、間隔制約は、適宜組み合わせて利用することができる。例えば、含有必須制約と間隔制約を組み合わせることで、パタン＜ａｂ＞を含み、且つ、その“ａ”と“ｂ”の間隔は１以下となる頻出系列パタンを発見することができる。また、これらの制約を組み合わせることで、正規表現で指定された制約を満たす頻出系列パタンを発見することができる。例えば、「ｄｂ*｛ｂ｜ｃ｝」のような正規表現では、特定のアイテム“ｄ”と“ｂ”の間隔が０以下の間隔制約と、“ｄｂｂ”と“ｄｂｃ”を含有必須パタンとして指定する含有必須制約とを組み合わせて利用することで、実現することが可能である。
【０３１５】
以上、本発明にかかる第１〜第３の実施形態について説明したが、本発明はこれに限定されるものではなく、本発明の主旨を逸脱しない範囲での種々の変更、置換、追加などが可能である。
【０３１６】
例えば、上記の実施形態では、単一の系列パタン抽出装置が各機能部を備える態様としたが、複数の装置に分散して備える態様としてもよい。また、上記の実施形態では、分析対象となる系列データを単一の系列データ記憶部２１に記憶する態様としたが、これに限らず、複数の系列データ記憶部２１に分散して記憶する態様としてもよい。なお、この場合、系列データ記憶部２１毎に、射影位置取得部２３、射影位置記憶部２４は個別に備える態様としていてもよい。
【０３１７】
また、上記実施形態では、単一の系列パタン抽出装置内に上述した各機能部を備える態様としたが、これに限らず、複数の装置に分散して構成する態様としてもよい。例えば、系列データ記憶部２１、射影位置取得部２３、射影位置記憶部２４を備えた、分析データ収集・記憶を目的とする複数の装置と、射影部２５を備えた系列パタンの発見処理を目的とする装置とから構成することとしてもよい。このように各機能部の機能に応じて、複数の装置に分散して構成することで、データの読み込みを並列化させて高速化を図る、或いは、データの収集を容易にさせるために、物理的、地理的に異なる複数の場所に装置を設置することができる。
【０３１８】
また、上記実施形態の系列パタン抽出装置で実行されるプログラムは、ＲＯＭ１２や記憶部１４等に予め組み込まれて提供されるものとするが、これに限らず、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録して提供するように構成してもよい。
【０３１９】
また、このプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよく、インターネット等のネットワーク経由で提供又は配布するように構成してもよい。
【図面の簡単な説明】
【０３２０】
【図１】系列パタン抽出装置のハードウェア構成を示した図である。
【図２】第１の実施形態にかかる系列パタン抽出装置の機能構成を示した図である。
【図３】図１の系列データ記憶部に記憶された系列データ集合の一例を示した図である。
【図４】同順射影位置取得処理の手順を示したフローチャートである。
【図５−１】図４に示した同順射影位置取得処理を説明するための図である。
【図５−２】図４に示した同順射影位置取得処理を説明するための図である。
【図５−３】図４に示した同順射影位置取得処理を説明するための図である。
【図５−４】図４に示した同順射影位置取得処理を説明するための図である。
【図５−５】図４に示した同順射影位置取得処理を説明するための図である。
【図６】異順射影位置取得処理の手順を示したフローチャートである。
【図７−１】図６に示した異順射影位置取得処理を説明するための図である。
【図７−２】図６に示した異順射影位置取得処理を説明するための図である。
【図７−３】図６に示した異順射影位置取得処理を説明するための図である。
【図７−４】図６に示した異順射影位置取得処理を説明するための図である。
【図７−５】図６に示した異順射影位置取得処理を説明するための図である。
【図７−６】図６に示した異順射影位置取得処理を説明するための図である。
【図７−７】図６に示した異順射影位置取得処理を説明するための図である。
【図７−８】図６に示した異順射影位置取得処理を説明するための図である。
【図７−９】図６に示した異順射影位置取得処理を説明するための図である。
【図７−１０】図６に示した異順射影位置取得処理を説明するための図である。
【図８】第１の実施形態にかかる頻出系列パタン発見処理の手順を示したフローチャートである。
【図９】図３の系列データ集合から最小支持度未満のアイテムを削除した状態を示した図である。
【図１０】射影位置取得処理の手順を示したフローチャートである。
【図１１】記憶優先格納処理の手順を示したフローチャートである。
【図１２−１】図１１に示した記憶優先格納処理を説明するための図である。
【図１２−２】図１１に示した記憶優先格納処理を説明するための図である。
【図１３−１】図１１に示した記憶優先格納処理を説明するための図である。
【図１３−２】図１１に示した記憶優先格納処理を説明するための図である。
【図１４−１】図１１に示した記憶優先格納処理を説明するための図である。
【図１４−２】図１１に示した記憶優先格納処理を説明するための図である。
【図１５】差分格納処理の手順を示したフローチャートである。
【図１６−１】図１５に示した差分格納処理を説明するための図である。
【図１６−２】図１５に示した差分格納処理を説明するための図である。
【図１６−３】図１５に示した差分格納処理を説明するための図である。
【図１７】射影処理の手順を示したフローチャートである。
【図１８】アイテム抽出処理の手順を示したフローチャートである。
【図１９】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図２０】同順射影により取得されたアイテムを示した図である。
【図２１】異順射影により取得されたアイテムを示した図である。
【図２２】図１９の射影位置における頻出アイテムを示した図である。
【図２３】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図２４】図２３に示した射影位置における頻出アイテムを示した図である。
【図２５】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図２６−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図２６−２】図２６−１に示した射影位置における頻出アイテムを示した図である。
【図２７−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図２７−２】図２７−１に示した射影位置における頻出アイテムを示した図である。
【図２８】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図２９】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３０−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３０−２】図３０−１に示した射影位置における頻出アイテムを示した図である。
【図３１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３２】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３３】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３４−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３４−２】図３４−１に示した射影位置における頻出アイテムを示した図である。
【図３５−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３５−２】図３５−１に示した射影位置における頻出アイテムを示した図である。
【図３６】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３７】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３８−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図３８−２】図３８−１に示した射影位置における頻出アイテムを示した図である。
【図３９】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図４０】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図４１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図４２−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図４２−２】図４２−１に示した射影位置における頻出アイテムを示した図である。
【図４３】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図４４】第２の実施形態にかかる系列パタン抽出装置の機能構成を示した図である。
【図４５】頻出位置記憶方式で記憶した同順射影位置、異順射影位置を示した図である。
【図４６】同順射影位置削除処理の手順を示したフローチャートである。
【図４７】アイテム位置行列の一例を示した図である。
【図４８】同順射影位置削除処理が施される前の同順射影位置を示した図である。
【図４９】同順射影位置削除処理を施した後の同順射影位置を示した図である。
【図５０】異順射影位置削除処理の手順を示したフローチャートである。
【図５１】異順射影位置削除処理が施される前の異順射影位置を示した図である。
【図５２】異順射影位置削除処理が施した後の異順射影位置を示した図である。
【図５３】第２の実施形態にかかる頻出系列パタン発見処理の手順を示したフローチャートである。
【図５４−１】図５３の射影位置削除処理を説明するための図である。
【図５４−２】図５３の射影位置削除処理を説明するための図である。
【図５４−３】図５３の射影位置削除処理を説明するための図である。
【図５５−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図５５−２】図５５−１に示した射影位置における頻出アイテムを示した図である。
【図５６−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図５６−２】図５６−１に示した射影位置における頻出アイテムを示した図である。
【図５７】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図５８−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図５８−２】図５８−１に示した射影位置における頻出アイテムを示した図である。
【図５９−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図５９−２】図５９−１に示した射影位置における頻出アイテムを示した図である。
【図６０】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６２−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６２−２】図６２−１に示した射影位置における頻出アイテムを示した図である。
【図６３】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６４】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６５】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６６−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６６−２】図６６−１に示した射影位置における頻出アイテムを示した図である。
【図６７−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６７−２】図６７−１に示した射影位置における頻出アイテムを示した図である。
【図６８】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図６９】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図７０−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図７０−２】図７０−１に示した射影位置における頻出アイテムを示した図である。
【図７１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図７２】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図７３】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図７４−１】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図７４−２】図７４−１に示した射影位置における頻出アイテムを示した図である。
【図７５】図９の系列データ集合における前置パタンと射影位置とを示した図である。
【図７６】第３の実施形態にかかる系列パタン抽出装置の機能構成を示した図である。
【図７７】図７−８の異順射影位置に間隔制約を適用した結果を示した図である。
【図７８】図７−８の異順射影位置に間隔制約を適用した結果を示した図である。
【図７９】図７−８の異順射影位置に間隔制約を適用した結果を示した図である。
【図８０】第３の実施形態にかかる頻出系列パタン発見処理の手順を示したフローチャートである。
【図８１】含有必須射影処理の手順を示したフローチャートである。
【図８２】含有必須射影処理を説明するための図である。
【図８３】前置パタンと、含有必須パタンとの関係を示した図である。
【図８４】図８２の系列データにおける前置パタンの位置を示した図である。
【図８５】最終制約充足ツリーの一例を示した図である。
【図８６】含有不可射影処理の手順を示したフローチャートである。
【符号の説明】
【０３２１】
１００  系列パタン抽出装置
２００  系列パタン抽出装置
３００  系列パタン抽出装置
１１    ＣＰＵ
１２    ＲＯＭ
１３    ＲＡＭ
１４    記憶部
１５    表示部
１６    操作部
１７    通信部
１８    バス
２１    系列データ記憶部
２２    最小支持度入力部
２３    射影位置取得部
２４    射影位置記憶部
２５    射影部
２６    頻出系列パタン出力部
３１    射影位置取得部
３２    射影位置記憶部
３３    射影部
４１    制約条件入力部
４２    射影位置取得部
４３    射影位置記憶部
４４    射影部
【図１】
2009169850.tif 000003
【図２】
2009169850.tif 000004
【図３】
2009169850.tif 000005
【図４】
2009169850.tif 000006
【図５−１】
2009169850.tif 000007
【図５−２】
2009169850.tif 000008
【図５−３】
2009169850.tif 000009
【図５−４】
2009169850.tif 000010
【図５−５】
2009169850.tif 000011
【図６】
2009169850.tif 000012
【図７−１】
2009169850.tif 000013
【図７−２】
2009169850.tif 000014
【図７−３】
2009169850.tif 000015
【図７−４】
2009169850.tif 000016
【図７−５】
2009169850.tif 000017
【図７−６】
2009169850.tif 000018
【図７−７】
2009169850.tif 000019
【図７−８】
2009169850.tif 000020
【図７−９】
2009169850.tif 000021
【図７−１０】
2009169850.tif 000022
【図８】
2009169850.tif 000023
【図９】
2009169850.tif 000024
【図１０】
2009169850.tif 000025
【図１１】
2009169850.tif 000026
【図１２−１】
2009169850.tif 000027
【図１２−２】
2009169850.tif 000028
【図１３−１】
2009169850.tif 000029
【図１３−２】
2009169850.tif 000030
【図１４−１】
2009169850.tif 000031
【図１４−２】
2009169850.tif 000032
【図１５】
2009169850.tif 000033
【図１６−１】
2009169850.tif 000034
【図１６−２】
2009169850.tif 000035
【図１６−３】
2009169850.tif 000036
【図１７】
2009169850.tif 000037
【図１８】
2009169850.tif 000038
【図１９】
2009169850.tif 000039
【図２０】
2009169850.tif 000040
【図２１】
2009169850.tif 000041
【図２２】
2009169850.tif 000042
【図２３】
2009169850.tif 000043
【図２４】
2009169850.tif 000044
【図２５】
2009169850.tif 000045
【図２６−１】
2009169850.tif 000046
【図２６−２】
2009169850.tif 000047
【図２７−１】
2009169850.tif 000048
【図２７−２】
2009169850.tif 000049
【図２８】
2009169850.tif 000050
【図２９】
2009169850.tif 000051
【図３０−１】
2009169850.tif 000052
【図３０−２】
2009169850.tif 000053
【図３１】
2009169850.tif 000054
【図３２】
2009169850.tif 000055
【図３３】
2009169850.tif 000056
【図３４−１】
2009169850.tif 000057
【図３４−２】
2009169850.tif 000058
【図３５−１】
2009169850.tif 000059
【図３５−２】
2009169850.tif 000060
【図３６】
2009169850.tif 000061
【図３７】
2009169850.tif 000062
【図３８−１】
2009169850.tif 000063
【図３８−２】
2009169850.tif 000064
【図３９】
2009169850.tif 000065
【図４０】
2009169850.tif 000066
【図４１】
2009169850.tif 000067
【図４２−１】
2009169850.tif 000068
【図４２−２】
2009169850.tif 000069
【図４３】
2009169850.tif 000070
【図４４】
2009169850.tif 000071
【図４５】
2009169850.tif 000072
【図４６】
2009169850.tif 000073
【図４７】
2009169850.tif 000074
【図４８】
2009169850.tif 000075
【図４９】
2009169850.tif 000076
【図５０】
2009169850.tif 000077
【図５１】
2009169850.tif 000078
【図５２】
2009169850.tif 000079
【図５３】
2009169850.tif 000080
【図５４−１】
2009169850.tif 000081
【図５４−２】
2009169850.tif 000082
【図５４−３】
2009169850.tif 000083
【図５５−１】
2009169850.tif 000084
【図５５−２】
2009169850.tif 000085
【図５６−１】
2009169850.tif 000086
【図５６−２】
2009169850.tif 000087
【図５７】
2009169850.tif 000088
【図５８−１】
2009169850.tif 000089
【図５８−２】
2009169850.tif 000090
【図５９−１】
2009169850.tif 000091
【図５９−２】
2009169850.tif 000092
【図６０】
2009169850.tif 000093
【図６１】
2009169850.tif 000094
【図６２−１】
2009169850.tif 000095
【図６２−２】
2009169850.tif 000096
【図６３】
2009169850.tif 000097
【図６４】
2009169850.tif 000098
【図６５】
2009169850.tif 000099
【図６６−１】
2009169850.tif 000100
【図６６−２】
2009169850.tif 000101
【図６７−１】
2009169850.tif 000102
【図６７−２】
2009169850.tif 000103
【図６８】
2009169850.tif 000104
【図６９】
2009169850.tif 000105
【図７０−１】
2009169850.tif 000106
【図７０−２】
2009169850.tif 000107
【図７１】
2009169850.tif 000108
【図７２】
2009169850.tif 000109
【図７３】
2009169850.tif 000110
【図７４−１】
2009169850.tif 000111
【図７４−２】
2009169850.tif 000112
【図７５】
2009169850.tif 000113
【図７６】
2009169850.tif 000114
【図７７】
2009169850.tif 000115
【図７８】
2009169850.tif 000116
【図７９】
2009169850.tif 000117
【図８０】
2009169850.tif 000118
【図８１】
2009169850.tif 000119
【図８２】
2009169850.tif 000120
【図８３】
2009169850.tif 000121
【図８４】
2009169850.tif 000122
【図８５】
2009169850.tif 000123
【図８６】
2009169850.tif 000124