(57)【要約】【課題】少ない計算コストでユーザが指定する最小長以上のアイテムパターンを抽出する。【解決手段】ノード選択部６０により、複数のアイテム集合のうち未探索のアイテム集合のいずれか１つを選択し、共通部分計算部６２により、選択されたアイテム集合と包含関係にないアイテム集合を前記複数のアイテム集合から探索し、選択されたアイテム集合と探索されたアイテム集合の各々とで共通するアイテム部分集合を共通部分集合として各々計算し、順序包含木更新部６４により、計算された共通部分集合を複数のアイテム集合に追加することを複数のアイテム集合の全てが探索済みとなるまで繰り返し行い、終了判定部６６により、複数のアイテム集合のうち予め定められた最小長以上のアイテム集合をアイテムパターンとして出力する。【選択図】図５
2014048911.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのアイテムからなる複数のアイテム集合と前記アイテム集合同士の共通部分集合とで表されるアイテムパターンを抽出するアイテムパターン抽出装置であって、
複数のアイテム集合を記憶した記憶手段と、
前記複数のアイテム集合のうち未探索のアイテム集合のいずれか１つを選択するアイテム集合選択手段と、
前記アイテム集合選択手段により選択されたアイテム集合と包含関係にないアイテム集合を前記複数のアイテム集合から探索し、前記選択されたアイテム集合と探索されたアイテム集合の各々とで共通するアイテム部分集合を共通部分集合として各々計算し、前記選択されたアイテム集合を探索済みアイテム集合とする共通部分計算手段と、
前記共通部分計算手段により計算された共通部分集合の各々を前記複数のアイテム集合に追加する追加手段と、
前記複数のアイテム集合の全てが探索済みアイテム集合となるまで、前記アイテム集合選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム集合のうち予め定められた最小長以上のアイテム集合を前記アイテムパターンとして出力する終了判定手段と
を備えたアイテムパターン抽出装置。
【請求項２】
前記記憶手段により記憶されている前記複数のアイテム集合に対応する複数のノードで構成される木構造であって、かつ、各親ノードのアイテム集合が子ノードのアイテム集合を包含し、兄弟ノードの各々のアイテム集合同士が互いに包含せず、兄弟ノードのうち左右のいずれか一方に位置するノードのアイテム集合が該ノードの前記左右のいずれか他方に位置する兄弟ノードの子孫ノードの各々のアイテム集合を包含しない、木構造を作成する木構造作成手段を更に含み、
前記共通部分計算手段は、前記アイテム集合選択手段により選択されたアイテム集合と包含関係にないアイテム集合として、前記選択されたアイテム集合に対応するノードの前記左右のいずれか他方に位置する兄弟ノードの各々のアイテム集合及び前記兄弟ノードの子孫ノードの各々のアイテム集合を探索して、前記共通部分集合を各々計算し、
前記追加手段は、前記共通部分計算手段により計算された共通部分集合の各々に対応するノードを、前記木構造に追加し、
前記終了判定手段は、木構造の各ノードのアイテム集合のうち前記最小長以上のアイテム集合を前記アイテムパターンとして出力する請求項１記載のアイテムパターン抽出装置。
【請求項３】
前記木構造作成手段は、前記記憶手段により記憶されている複数のアイテム集合のうち前記予め定められた最小長以上のアイテム集合の各々に対応する複数のノードで構成される前記木構造を作成し、
前記追加手段は、前記共通部分計算手段により計算された共通部分集合のうち前記予め定められた最小長以上のアイテム集合の各々に対応するノードを、前記木構造に追加する請求項２記載のアイテムパターン抽出装置。
【請求項４】
少なくとも１つのアイテムからなる複数のアイテム系列と前記アイテム系列同士の共通部分系列とで表されるアイテムパターンを抽出するアイテムパターン抽出装置であって、
複数のアイテム系列を記憶した記憶手段と、
前記複数のアイテム系列のうち未探索のアイテム系列のいずれか１つを選択するアイテム系列選択手段と、
前記アイテム系列選択手段により選択されたアイテム系列と包含関係にないアイテム系列を前記複数のアイテム系列から探索し、前記選択されたアイテム系列と探索されたアイテム系列の各々とで共通するアイテム部分系列を共通部分系列として各々計算し、前記選択されたアイテム系列を探索済みアイテム系列とする共通部分計算手段と、
前記共通部分計算手段により計算された共通部分系列の各々を前記複数のアイテム系列に追加する追加手段と、
前記複数のアイテム系列の全てが探索済みアイテム系列となるまで、前記アイテム系列選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム系列のうち予め定められた最小長以上のアイテム系列を前記アイテムパターンとして出力する終了判定手段と
を備えたアイテムパターン抽出装置。
【請求項５】
前記記憶手段により記憶されている前記複数のアイテム系列に対応する複数のノードで構成される木構造であって、かつ、各親ノードのアイテム系列が子ノードのアイテム系列を包含し、兄弟ノードの各々のアイテム系列同士が互いに包含せず、兄弟ノードのうち左右のいずれか一方に位置するノードのアイテム系列が該ノードの前記左右のいずれか他方に位置する兄弟ノードの子孫ノードの各々のアイテム系列を包含しない、木構造を作成する木構造作成手段を更に含み、
前記共通部分計算手段は、前記アイテム系列選択手段により選択されたアイテム系列と包含関係にないアイテム系列として、前記選択されたアイテム系列に対応するノードの前記左右のいずれか他方に位置する兄弟ノードの各々のアイテム系列及び前記兄弟ノードの子孫ノードの各々のアイテム系列を探索して、前記共通部分系列を各々計算し、
前記追加手段は、前記共通部分計算手段により計算された共通部分系列の各々に対応するノードを、前記木構造に追加し、
前記終了判定手段は、木構造の各ノードのアイテム系列のうち前記最小長以上のアイテム系列を前記アイテムパターンとして出力する請求項４記載のアイテムパターン抽出装置。
【請求項６】
複数のアイテム集合を記憶した記憶手段と、アイテム集合選択手段と、共通部分計算手段と、追加手段と、終了判定手段とを含み、少なくとも１つのアイテムからなる複数のアイテム集合と前記アイテム集合同士の共通部分集合とで表されるアイテムパターンを抽出するアイテムパターン抽出装置におけるアイテムパターン抽出方法であって、
前記アイテム集合選択手段は、前記複数のアイテム集合のうち未探索のアイテム集合のいずれか１つを選択し、
前記共通部分計算手段は、前記アイテム集合選択手段により選択されたアイテム集合と包含関係にないアイテム集合を前記複数のアイテム集合から探索し、前記選択されたアイテム集合と探索されたアイテム集合の各々とで共通するアイテム部分集合を共通部分集合として各々計算し、前記選択されたアイテム集合を探索済みアイテム集合とし、
前記追加手段は、前記共通部分計算手段により計算された共通部分集合の各々を前記複数のアイテム集合に追加し、
前記終了判定手段は、前記複数のアイテム集合の全てが探索済みアイテム集合となるまで、前記アイテム集合選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム集合のうち予め定められた最小長以上のアイテム集合を前記アイテムパターンとして出力する
アイテムパターン抽出方法。
【請求項７】
複数のアイテム系列を記憶した記憶手段と、アイテム系列選択手段と、共通部分計算手段と、追加手段と、終了判定手段とを含み、少なくとも１つのアイテムからなる複数のアイテム系列と前記アイテム系列同士の共通部分系列とで表されるアイテムパターンを抽出するアイテムパターン抽出装置におけるアイテムパターン抽出方法であって、
前記アイテム系列選択手段は、前記複数のアイテム系列のうち未探索のアイテム系列のいずれか１つを選択し、
前記共通部分計算手段は、前記アイテム系列選択手段により選択されたアイテム系列と包含関係にないアイテム系列を前記複数のアイテム系列から探索し、前記選択されたアイテム系列と探索されたアイテム系列の各々とで共通するアイテム部分系列を共通部分系列として各々計算し、前記選択されたアイテム系列を探索済みアイテム系列とし、
前記追加手段は、前記共通部分計算手段により計算された共通部分系列の各々を前記複数のアイテム系列に追加し、
前記終了判定手段は、前記複数のアイテム系列の全てが探索済みアイテム系列となるまで、前記アイテム系列選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム系列のうち予め定められた最小長以上のアイテム系列を前記アイテムパターンとして出力する
アイテムパターン抽出方法。
【請求項８】
コンピュータを、請求項１〜請求項５の何れか１項記載のアイテムパターン抽出装置を構成する各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アイテムパターン抽出装置、方法、プログラムに係り、特に、ユーザが指定する最小長以上のアイテムパターンをデータベースから抽出するアイテムパターン抽出装置、方法、プログラムに関する。
【背景技術】
【０００２】
アイテム集合パターンマイニングとは、アイテム集合で構成されるデータベースから、ユーザの指定する条件（例えばアイテム集合の頻度や長さ等）を満たすアイテムパターンを列挙することをいう。アイテム系列パターンマイニングとは、アイテム集合パターンマイニングと同様に、アイテム系列で構成されるデータベースから、ユーザの指定する条件を満たすアイテムパターンを列挙することをいう。
【０００３】
図１２にアイテム集合データベースの例を示す。図１２において、各アルファベット：ａ，ｂ，ｃ，… をアイテムと呼び、アイテムの集合を｛ａ，ｂ，ｃ｝のように表す。また、データベース中のｒ１＝｛ａ，ｂ，ｃ，ｄ｝やｒ２＝｛ｂ，ｃ，ｄ｝などをレコードと呼ぶ。アイテム集合の長さとは、アイテム集合に含まれるアイテムの数であり、｜｛・｝｜と表記する。例えば、ｒ１の長さは、｜ｒ１｜＝｜｛ａ，ｂ，ｃ，ｄ｝｜＝４である。また、アイテム集合の頻度とは、データベース中にアイテム集合が何回含まれているかを表し、例えば｛ｂ，ｃ，ｄ｝はｒ１，ｒ２，ｒ４に含まれているので、頻度は３である。アイテム集合は重複する要素を含まず、各集合内の各アイテムの順序は考慮されない。
【０００４】
図１３にアイテム系列データベースの例を示す。図１３において、｛ａ，ｂ，ｃ，ｄ，ｂ｝や｛ｂ，ｃ，ｄ，ｅ，ｃ｝などがアイテム系列である。アイテム系列はアイテム集合と異なり、アイテムの順序を考慮する。したがって、例えば｛ａ，ｂ，ｃ，ｄ｝と｛ｃ，ａ，ｂ，ｄ｝はアイテムの順序が異なるため異なるデータとして扱われる。また、系列データベースでは、｛ａ，ｂ，ｃ，ｄ，ｃ，ｂ}のように重複する要素を含むデータがあってもよい。アイテム系列の頻度や長さは、アイテム集合と同様に定義される。
【０００５】
レコードのアイテム集合またはアイテム系列と、レコード間の共通部分集合または共通部分系列とで表されるアイテムパターンを飽和パターンと呼ぶ。図１２の例では、｛ａ，ｂ，ｃ，ｄ｝＝ｒ１、｛ｂ，ｃ，ｄ，ｅ｝＝ｒ２、｛ａ，ｂ，ｄ，ｅ｝＝ｒ３、｛ｂ，ｃ，ｄ｝＝ｒ４、｛ａ，ｄ，ｅ｝＝ｒ５、｛ａ，ｂ，ｄ｝＝ｒ１∩ｒ３、｛ｂ，ｄ，ｅ｝＝ｒ２∩ｒ３、｛ａ，ｄ｝＝ｒ１∩ｒ５、｛ｄ，ｅ｝＝ｒ２∩ｒ５、｛ｂ，ｄ｝＝ｒ３∩ｒ４、｛ｄ｝＝ｒ４∩ｒ５の全１１種類が飽和パターンである。最小長：ｍｉｎｌｅｎ＝３に設定したとき、｛ａ，ｄ｝、｛ｄ，ｅ｝、｛ｂ，ｄ｝、｛ｄ｝のパターンは長さが３より短いため、最小長以上の飽和パターンの数は全部で７種類となる。このように、アイテム集合同士の共通部分（積集合）を計算することにより、飽和パターンを得ることができる。
【０００６】
データベースから飽和パターンが得られると、全てのアイテムパターンの頻度が得られることが知られている（例えば非特許文献１）。したがって、近年のパターンマイニング手法は、指定された条件を満たす飽和パターンのみを抽出するものが多い。
【０００７】
従来のパターンマイニング手法は、大きく二種類に分類することができる。一つは、列挙演算型で、長さの短いパターンから始めて、徐々に長いパターンを探索していくものである（例えば非特許文献１、非特許文献２）。もう一つは、共通部分演算型で、長さの長いパターン、すなわちレコードから始めて、徐々に短いパターンを探索していくものである（例えば非特許文献３）。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Zaki, M.J. and Hsiao, C.J.: CHARM: An Efficient Algorithm for Closed Itemset Mining, Database, In Proc. SIAM Int'l Conf. Data Mining(2002).
【非特許文献２】Grahne, G. and Zhu, J.: Efficiently Using Prefix-trees in Mining Frequent Itemsets, In Proc. of the ICDM Workshop on Frequent Itemset Mining Implementations (2003).
【非特許文献３】Mielikainen, T.: Intersecting Data to Closed Sets with Constraints, In Proc. of the ICDM Workshop on Frequent Item Set Mining Implementations (2003).
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、列挙演算型のパターンマイニング手法は、短いパターンから始めて徐々に長いパターンを探索するため、ユーザが指定する最小長以上のパターンのみを探索することができないという問題がある。
【００１０】
また、共通部分演算型のパターンマイニング手法は、長いパターンから始めて徐々に短いパターンを探索するため、ユーザが指定する最小長以上のパターンのみを探索することができる。しかしながら、これまでに提案されている共通部分演算型の手法（例えば非特許文献３）は、同じパターンを何度も探索してしまうことを回避できず、計算速度が非常に遅いという問題がある。
【００１１】
本発明では、上記問題点を解決するために成されたものであり、少ない計算コストでユーザが指定する最小長以上のアイテムパターンのみを複数のアイテム集合又はアイテム系列から抽出するアイテムパターン抽出装置、方法、プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、第１の発明のアイテムパターン抽出装置は、少なくとも１つのアイテムからなる複数のアイテム集合と前記アイテム集合同士の共通部分集合とで表されるアイテムパターンを抽出するアイテムパターン抽出装置であって、複数のアイテム集合を記憶した記憶手段と、前記複数のアイテム集合のうち未探索のアイテム集合のいずれか１つを選択するアイテム集合選択手段と、前記アイテム集合選択手段により選択されたアイテム集合と包含関係にないアイテム集合を前記複数のアイテム集合から探索し、前記選択されたアイテム集合と探索されたアイテム集合の各々とで共通するアイテム部分集合を共通部分集合として各々計算し、前記選択されたアイテム集合を探索済みアイテム集合とする共通部分計算手段と、前記共通部分計算手段により計算された共通部分集合の各々を前記複数のアイテム集合に追加する追加手段と、前記複数のアイテム集合の全てが探索済みアイテム集合となるまで、前記アイテム集合選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム集合のうち予め定められた最小長以上のアイテム集合を前記アイテムパターンとして出力する終了判定手段と、を含んで構成されている。
【００１３】
第２の発明のアイテムパターン抽出方法は、複数のアイテム集合を記憶した記憶手段と、アイテム集合選択手段と、共通部分計算手段と、追加手段と、終了判定手段とを含み、少なくとも１つのアイテムからなる複数のアイテム集合と前記アイテム集合同士の共通部分集合とで表されるアイテムパターンを抽出するアイテムパターン抽出装置におけるアイテムパターン抽出方法であって、前記アイテム集合選択手段は、前記複数のアイテム集合のうち未探索のアイテム集合のいずれか１つを選択し、前記共通部分計算手段は、前記アイテム集合選択手段により選択されたアイテム集合と包含関係にないアイテム集合を前記複数のアイテム集合から探索し、前記選択されたアイテム集合と探索されたアイテム集合の各々とで共通するアイテム部分集合を共通部分集合として各々計算し、前記選択されたアイテム集合を探索済みアイテム集合とし、前記追加手段は、前記共通部分計算手段により計算された共通部分集合の各々を前記複数のアイテム集合に追加し、前記終了判定手段は、前記複数のアイテム集合の全てが探索済みアイテム集合となるまで、前記アイテム集合選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム集合のうち予め定められた最小長以上のアイテム集合を前記アイテムパターンとして出力する。
【００１４】
第１の発明及び第２の発明によれば、記憶手段によって、複数のアイテム集合を記憶し、アイテム集合選択手段によって、複数のアイテム集合のうち未探索のアイテム集合のいずれか１つを選択し、共通部分計算手段によって、前記アイテム集合選択手段により選択されたアイテム集合と包含関係にないアイテム集合を前記複数のアイテム集合から探索し、前記選択されたアイテム集合と探索されたアイテム集合の各々とで共通するアイテム部分集合を共通部分集合として各々計算し、前記選択されたアイテム集合を探索済みアイテム集合とし、追加手段によって、前記共通部分計算手段により計算された共通部分集合の各々を前記複数のアイテム集合に追加し、終了判定手段によって、前記複数のアイテム集合の全てが探索済みアイテム集合となるまで、前記アイテム集合選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム集合のうち予め定められた最小長以上のアイテム集合を前記アイテムパターンとして出力する。
【００１５】
このように、複数のアイテム集合のうち未探索のアイテム集合のいずれか１つを選択し、選択されたアイテム集合と包含関係にないアイテム集合を複数のアイテム集合から探索し、選択されたアイテム集合と探索されたアイテム集合の各々とで共通するアイテム部分集合を共通部分集合として各々計算し、計算された共通部分集合の各々を複数のアイテム集合に追加することを繰り返し行い、複数のアイテム集合のうち予め定められた最小長以上のアイテム集合をアイテムパターンとして出力することにより、少ない計算コストでユーザが指定する最小長以上のアイテムパターンのみを複数のアイテム集合から抽出することができる。
【００１６】
なお、本発明のアイテムパターン抽出装置は、共通部分演算型に分類される。
【００１７】
第３の発明のアイテムパターン抽出装置は、少なくとも１つのアイテムからなる複数のアイテム系列と前記アイテム系列同士の共通部分系列とで表されるアイテムパターンを抽出するアイテムパターン抽出装置であって、複数のアイテム系列を記憶した記憶手段と、
前記複数のアイテム系列のうち未探索のアイテム系列のいずれか１つを選択するアイテム系列選択手段と、前記アイテム系列選択手段により選択されたアイテム系列と包含関係にないアイテム系列を前記複数のアイテム系列から探索し、前記選択されたアイテム系列と探索されたアイテム系列の各々とで共通するアイテム部分系列を共通部分系列として各々計算し、前記選択されたアイテム系列を探索済みアイテム系列とする共通部分計算手段と、前記共通部分計算手段により計算された共通部分系列の各々を前記複数のアイテム系列に追加する追加手段と、前記複数のアイテム系列の全てが探索済みアイテム系列となるまで、前記アイテム系列選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム系列のうち予め定められた最小長以上のアイテム系列を前記アイテムパターンとして出力する終了判定手段と、を含んで構成されている。
【００１８】
第４の発明のアイテムパターン抽出方法は、複数のアイテム系列を記憶した記憶手段と、アイテム系列選択手段と、共通部分計算手段と、追加手段と、終了判定手段とを含み、少なくとも１つのアイテムからなる複数のアイテム系列と前記アイテム系列同士の共通部分系列とで表されるアイテムパターンを抽出するアイテムパターン抽出装置におけるアイテムパターン抽出方法であって、前記アイテム系列選択手段は、前記複数のアイテム系列のうち未探索のアイテム系列のいずれか１つを選択し、前記共通部分計算手段は、前記アイテム系列選択手段により選択されたアイテム系列と包含関係にないアイテム系列を前記複数のアイテム系列から探索し、前記選択されたアイテム系列と探索されたアイテム系列の各々とで共通するアイテム部分系列を共通部分系列として各々計算し、前記選択されたアイテム系列を探索済みアイテム系列とし、前記追加手段は、前記共通部分計算手段により計算された共通部分系列の各々を前記複数のアイテム系列に追加し、前記終了判定手段は、前記複数のアイテム系列の全てが探索済みアイテム系列となるまで、前記アイテム系列選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム系列のうち予め定められた最小長以上のアイテム系列を前記アイテムパターンとして出力する。
【００１９】
第３の発明及び第４の発明によれば、記憶手段によって、複数のアイテム系列を記憶し、アイテム系列選択手段によって、複数のアイテム系列のうち未探索のアイテム系列のいずれか１つを選択し、共通部分計算手段によって、前記アイテム系列選択手段により選択されたアイテム系列と包含関係にないアイテム系列を前記複数のアイテム系列から探索し、前記選択されたアイテム系列と探索されたアイテム系列の各々とで共通するアイテム部分系列を共通部分系列として各々計算し、前記選択されたアイテム系列を探索済みアイテム系列とし、追加手段によって、前記共通部分計算手段により計算された共通部分系列の各々を前記複数のアイテム系列に追加し、終了判定手段によって、前記複数のアイテム系列の全てが探索済みアイテム系列となるまで、前記アイテム系列選択手段による選択と、前記共通部分計算手段による計算と、前記追加手段による追加とを繰り返し行い、前記複数のアイテム系列のうち予め定められた最小長以上のアイテム系列を前記アイテムパターンとして出力する。
【００２０】
このように、複数のアイテム系列のうち未探索のアイテム系列のいずれか１つを選択し、選択されたアイテム系列と包含関係にないアイテム系列を複数のアイテム系列から探索し、選択されたアイテム系列と探索されたアイテム系列の各々とで共通するアイテム部分系列を共通部分系列として各々計算し、計算された共通部分系列を複数のアイテム系列に追加することを繰り返し行い、複数のアイテム系列のうち予め定められた最小長以上のアイテム系列をアイテムパターンとして出力することにより、少ない計算コストでユーザが指定する最小長以上のアイテムパターンのみを複数のアイテム系列から抽出することができる。
【００２１】
上記第１の発明に係るアイテムパターン抽出装置は、前記記憶手段により記憶されている前記複数のアイテム集合に対応する複数のノードで構成される木構造であって、かつ、各親ノードのアイテム集合が子ノードのアイテム集合を包含し、兄弟ノードの各々のアイテム集合同士が互いに包含せず、兄弟ノードのうち左右のいずれか一方に位置するノードのアイテム集合が該ノードの前記左右のいずれか他方に位置する兄弟ノードの子孫ノードの各々のアイテム集合を包含しない、木構造を作成する木構造作成手段を更に含み、前記共通部分計算手段は、前記アイテム集合選択手段により選択されたアイテム集合と包含関係にないアイテム集合として、前記選択されたアイテム集合に対応するノードの前記左右のいずれか他方に位置する兄弟ノードの各々のアイテム集合及び前記兄弟ノードの子孫ノードの各々のアイテム集合を探索して、前記共通部分集合を各々計算し、前記追加手段は、前記共通部分計算手段により計算された共通部分集合の各々に対応するノードを、前記木構造に追加し、前記終了判定手段は、木構造の各ノードのアイテム集合のうち前記最小長以上のアイテム集合を前記アイテムパターンとして出力するようにすることができる。
【００２２】
このように、上記のような木構造を作成することで、包含関係にないアイテム集合同士の探索コストが低減するため、より少ない計算コストで、ユーザが指定する最小長以上のアイテムパターンのみを複数のアイテム集合から抽出することができる。
【００２３】
また、上記第１の発明に係る木構造作成手段は、前記記憶手段により記憶されている複数のアイテム集合のうち前記予め定められた最小長以上のアイテム集合の各々に対応する複数のノードで構成される前記木構造を作成し、前記追加手段は、前記共通部分計算手段により計算された共通部分集合のうち前記予め定められた最小長以上のアイテム集合の各々に対応するノードを、前記木構造に追加するようにすることができる。これにより、少ない計算コストで、ユーザが指定する最小長以上のアイテムパターンのみを複数のアイテム集合から抽出することができる。
【００２４】
上記第３の発明に係るアイテムパターン抽出装置は、前記記憶手段により記憶されている前記複数のアイテム系列に対応する複数のノードで構成される木構造であって、かつ、各親ノードのアイテム系列が子ノードのアイテム系列を包含し、兄弟ノードの各々のアイテム系列同士が互いに包含せず、兄弟ノードのうち左右のいずれか一方に位置するノードのアイテム系列が該ノードの前記左右のいずれか他方に位置する兄弟ノードの子孫ノードの各々のアイテム系列を包含しない、木構造を作成する木構造作成手段を更に含み、前記共通部分計算手段は、前記アイテム系列選択手段により選択されたアイテム系列と包含関係にないアイテム系列として、前記選択されたアイテム系列に対応するノードの前記左右のいずれか他方に位置する兄弟ノードの各々のアイテム系列及び前記兄弟ノードの子孫ノードの各々のアイテム系列を探索して、前記共通部分系列を各々計算し、前記追加手段は、前記共通部分計算手段により計算された共通部分系列の各々に対応するノードを、前記木構造に追加し、前記終了判定手段は、木構造の各ノードのアイテム系列のうち前記最小長以上のアイテム系列を前記アイテムパターンとして出力するようにすることができる。
【００２５】
このように、上記のような木構造を作成することで、包含関係にないアイテム系列同士の探索コストが低減するため、より少ない計算コストで、ユーザが指定する最小長以上のアイテムパターンのみを複数のアイテム系列から抽出することができる。
【００２６】
また、本発明のプログラムは、コンピュータを、上記のアイテムパターン抽出装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００２７】
以上説明したように、本発明のアイテムパターン抽出装置、方法、及びプログラムによれば、少ない計算コストでユーザが指定する最小長以上のアイテムパターンのみを複数のアイテム集合又はアイテム系列から抽出することができる。
【図面の簡単な説明】
【００２８】
【図１】本実施の形態のアイテムパターン抽出装置の機能的構成を示すブロック図である。
【図２】順序包含木を示す図である。
【図３】順序包含木構成部による順序包含木の構成例を示す図である。
【図４】本実施の形態の順序包含木構成部の機能的構成を示すブロック図である。
【図５】本実施の形態の共通部分演算部の機能的構成を示すブロック図である。
【図６】共通部分演算部の動作例（１）を示す図である。
【図７】本実施の形態のアイテムパターン抽出装置におけるアイテムパターン抽出処理ルーチンの内容を示すフローチャートである。
【図８】本実施の形態のアイテムパターン抽出装置における順序包含木構成処理ルーチンを示すフローチャートである。
【図９】本実施の形態のアイテムパターン抽出装置における親ノード探索処理ルーチンを示すフローチャートである。
【図１０】本実施の形態のアイテムパターン抽出装置における共通部分計算処理ルーチンを示すフローチャートである。
【図１１】共通部分演算部の動作例（２）を示す図である。
【図１２】アイテム集合データベースの例を示す図である。
【図１３】系列データベースの例を示す図である。
【図１４】計算コストの比較結果を示す図である。
【図１５】順序包含木のノードの順番を示す図である。
【発明を実施するための形態】
【００２９】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００３０】
＜本実施の形態の順序包含木＞
本実施の形態では、順序包含木と呼ばれる新たなデータ構造を利用する。ここで、本発明で利用する順序包含木について説明する。なお、順序包含木についてはアイテム集合を用いた例を説明するが、アイテム系列についても同様のことがいえる。
【００３１】
順序包含木ＸＯＩは、アイテム集合ｘの集合Ｘ＝｛ｘ，ｘ´，…｝を木構造へ変換したものである。ＸＯＩの根ノード：Ｒｏｏｔ（ＸＯＩ）のアイテム集合は、全てのアイテムを要素とするアイテム集合である。例えば、図１２のデータベースを順序包含木に変換した場合、アイテムはａ，ｂ，ｃ，ｄ，ｅの五種類なので、Ｒｏｏｔ（ＸＯＩ）＝｛ａ，ｂ，ｃ，ｄ，ｅ｝となる。また、ＸＯＩの根ノード以外の各ノードのアイテム集合は、何らかのアイテム集合ｘに対応する。図２は、図１２のデータベースＸ＝｛ｒ１，ｒ２，…，ｒ５｝を、順序包含木ＸＯＩへ変換したものである。順序包含木は、以下の三つの性質を満たすように構成される。
【００３２】
【数１】
2014048911.tif 000003
【００３３】
ただし、Ｐａｒｅｎｔ（ｘ）はｘの親ノード、Ｄｅｓｃ（ｘ）はｘの子孫ノードを表す。同様に、Ｃｈｉｌｄｒｅｎ（ｘ）はｘの子ノード、Ｒｏｏｔ（ＸＯＩ）はＸＯＩの根ノードを表すこととする。また、ｓｉ，ｓｊ（ｉ，ｊ＝１，２，…）は兄弟ノードとなっているｉ，ｊ番目のノードを表す。図２の例では、Ｒｏｏｔ（ＸＯＩ）のアイテム集合＝｛ａ，ｂ，ｃ，ｄ，ｅ｝、Ｐａｒｅｎｔ（｛ａ，ｂ，ｃ，ｄ｝）のアイテム集合＝｛ａ，ｂ，ｃ，ｄ，ｅ｝、Ｄｅｓｃ（｛ａ，ｂ，ｃ，ｄ｝）のアイテム集合＝｛ｂ，ｃ，ｄ｝である。また、｛ａ，ｂ，ｃ，ｄ｝をｓ１としたとき、｛ｂ，ｃ，ｄ，ｅ｝＝ｓ２，｛ａ，ｂ，ｄ，ｅ｝＝ｓ３は兄弟ノードである。
【００３４】
順序包含木の一つ目の性質は、全ての親ノードのアイテム集合は子ノードのアイテム集合を包含しなければならないという条件を表す。図２では、例えばＰａｒｅｎｔ（｛ｂ，ｃ，ｄ｝）のアイテム集合＝｛ａ，ｂ，ｃ，ｄ｝かつ｛ｂ，ｃ，ｄ｝⊂｛ａ，ｂ，ｃ，ｄ｝が成立し、順序包含木の性質を満たしている。二つ目の性質は、兄弟ノードの各々のアイテム集合同士は互いに包含関係が成立しないことを表している。図２では、例えば三つの兄弟ノードの各々のアイテム集合｛ａ，ｂ，ｃ，ｄ｝｛ｂ，ｃ，ｄ，ｅ｝｛ａ，ｂ，ｄ，ｅ｝間で互いに包含関係は成立しておらず、順序包含木の性質を満たしている。三つ目の条件は、あるノードｓｉ が他の兄弟ノードｓｊよりも順番が早い（ｉ＜ｊ）ならば、ｓｉのアイテム集合ｓｊの子孫ノード（子ノード、孫ノード、孫ノードの子ノードなど）の各々のアイテム集合を包含しないことを表す。図２では、例えば｛ａ，ｂ，ｃ，ｄ｝は、｛ａ，ｂ，ｄ，ｅ｝の子ノードのアイテム集合である｛ａ，ｄ，ｅ｝を包含しておらず、順序包含木の性質を満たしている。
【００３５】
＜アイテムパターン抽出装置の構成＞
次に、本発明の第１の実施の形態に係るアイテムパターン抽出装置の構成について説明する。図１に示すように、本発明の第１の実施の形態に係るアイテムパターン抽出装置１００は、ＣＰＵと、ＲＡＭと、後述するアイテムパターン抽出処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することができる。このアイテムパターン抽出装置１００は、機能的には、図１に示すように、入力部１０と、演算部２０と、出力部３０とを備えている。
【００３６】
入力部１０は、キーボードなどの入力装置から、抽出するパターンの最小長の値（ｍｉｎｌｅｎ）を受け付ける。なお、入力部１０は、ネットワーク等を介して外部から入力されたものを受け付けるようにしてもよい。
【００３７】
演算部２０は、記憶部３２、順序包含木記憶部３３、順序包含木構成部３４、及び共通部分演算部３６を備えている。
【００３８】
記憶部３２は、複数のアイテム集合からなる集合を記憶している。
【００３９】
順序包含木記憶部３３は、順序包含木構成部３４で作成された順序包含木及び、共通部分演算部３６で更新された順序包含木を記憶している。
【００４０】
順序包含木構成部３４は、記憶部３２に格納されたアイテム集合の集合から、アイテム集合の長さが最小長（ｍｉｎｌｅｎ）以上のものだけを用いて順序包含木Ｘ０Ｉを作成し、順序包含木記憶部３３へ出力する。共通部分演算部３６は、順序包含木記憶部３３に記憶されている順序包含木Ｘ０Ｉから、アイテム集合同士の共通部分を計算し、飽和アイテムパターンを表す順序包含木を生成する。そして、共通部分演算部３６は、新たに生成した順序包含木を出力部３０へ出力する。出力部３０は、共通部分演算部３６から入力された順序包含木を出力する。
【００４１】
＜順序包含木構成部の構成＞
次に、本発明の第１の実施の形態に係る順序包含木構成部の構成について詳細に説明する。順序包含木構成部３４は、まず、ノードＲｏｏｔ（ＸＯＩ）のみを持つ木構造を用意し、アイテム集合ｘに対応するノードを、長さの長い順番に木構造へ追加していくことで順序包含木ＸＯＩを構築する。図１２のデータベースから、アイテム集合ｘに対応するノードを１つずつ追加して順序包含木を構築する様子を図３に示す。図３では、まず図３（ａ）で根ノード｛ａ，ｂ，ｃ，ｄ，ｅ｝を設定し、一つずつ順番にアイテム集合に対応するノードを追加している。
【００４２】
順序包含木構成部３４の詳細構成を図４に示す。順序包含木構成部３４は、根ノード作成部５０、ノード選択部５２、親ノード探索部５４、ノード追加部５６、及び終了判定部５８、から構成される。
【００４３】
根ノード作成部５０は、入力部１０から入力された最小長（ｍｉｎｌｅｎ）の値と、記憶部３２から記憶部３２に記憶されているアイテム集合の集合を受け付け、最小長以上のアイテム集合ｘの集合Ｘを作成する。根ノード作成部５０は、入力された集合Ｘに含まれるすべてのアイテムを要素とするアイテム集合ｘ０を作成し、アイテム集合ｘ０に対応するノードを順序包含木ＸＯＩの根ノードに設定するとともに、アイテム集合ｘ０を集合Ｘから取り除いた集合（差集合）を新たな集合Ｘとして、ノード選択部５２に出力する。
【００４４】
ノード選択部５２は、根ノード作成部５０から入力された集合Ｘのうち最も長いアイテム集合ｘ１を選択し、選択したアイテム集合ｘ１を親ノード探索部５４及びノード追加部５６に出力するとともに、アイテム集合ｘ１を集合Ｘから取り除いた集合（差集合）を新たな集合Ｘとして終了判定部５８に出力する。
【００４５】
親ノード探索部５４は、ノード選択部５２から入力されたアイテム集合ｘ１の親ノードを順序包含木ＸＯＩから探索し、得られた親ノードｐをノード追加部５６に出力する。
【００４６】
ノード追加部５６は、ノード選択部５２から入力されたアイテム集合ｘ１(追加対象のノード)と、親ノード探索部５４から入力された親ノードｐを用い、ｘ１を順序包含木のＸＯＩにおけるノードｐの子ノードのアイテム集合として追加することにより順序包含木ＸＯＩを更新し、更新した順序包含木ＸＯＩを終了判定部５８に出力する。
【００４７】
終了判定部５８は、ノード選択部５２から入力された集合Ｘが空集合であるか否かを判定し、集合Ｘが空集合でない（まだ要素が残っている）場合には、ノード選択部５２に集合Ｘを入力し、順序包含木ＸＯＩへのノードの追加処理を繰り返す。集合Ｘが空集合の場合には、得られた順序包含木ＸＯＩを順序包含木記憶部３３に出力する。
【００４８】
＜共通部分演算部の構成＞
次に、本発明の第１の実施の形態に係る共通部分演算部３６の構成について詳細に説明する。共通部分演算部３６では、従来の方法と異なり、順序包含木ＸＯＩの情報に基づいて効率的な共通部分の計算を行う。共通部分演算部３６は図５に示すように、ノード選択部６０と、共通部分計算部６２と、順序包含木更新部６４と、終了判定部６６とを備える。
【００４９】
ノード選択部６０は、順序包含木記憶部３３に記憶されている順序包含木ＸＯＩの根ノードを除く未探索ノードの中から、最も順番の早いノードｙを選択し、共通部分計算部６２に出力する。ノードの順番は、図１５のように、根ノードの最も左の子ノードを１番とし、そこから深さ優先的に連番を付与するものとする。
【００５０】
共通部分計算部６２は、ノード選択部６０が選択したノードｙのアイテム集合と、ノードｙの右側にある兄弟ノードの各々のアイテム集合およびそれらの子孫ノードの各々のアイテム集合との間で共通するアイテム部分集合Ｙを各々計算し、順序包含木更新部６４に出力するとともに、ノードｙが探索済みノードであることを示す情報を順序包含木記憶部３３に記憶する。
【００５１】
順序包含木更新部６４は、共通部分計算部６２から入力された共通部分集合Ｙのうち、入力部１０から入力された最小長（ｍｉｎｌｅｎ）以上のアイテム集合に対応するノードを順序包含木ＸＯＩへ追加することにより、順序包含木ＸＯＩを更新し、更新した順序包含木ＸＯＩを順序包含木記憶部３３及び終了判定部６６に出力する。順序包含木更新部６４の具体処理は、順序包含木構成部３４のノード選択部５２、親ノード探索部５４、ノード追加部５６、及び終了判定部５８の処理と同じである。
【００５２】
終了判定部６６では、順序包含木更新部６４から入力された順序包含木ＸＯＩの全ノードが探索済であるか否かを判定し、全ノードが探索済であれば、順序包含木ＸＯＩを出力部３０に出力する。
【００５３】
＜アイテムパターン抽出装置の作用＞
次に、本発明の第１の実施の形態に係るアイテムパターン抽出装置１００の作用について説明する。アイテムパターン抽出装置１００のＲＯＭに記憶されたプログラムを、ＣＰＵが実行することにより、図７に示すアイテムパターン抽出処理ルーチンが実行される。
【００５４】
まず、ステップＳ１００において、入力部１０によって入力されたアイテムパターンの最小長（ｍｉｎｌｅｎ）を受け付ける。
【００５５】
次に、ステップＳ１０２において、記憶部３２に記憶されているアイテム集合を順序包含木構成部３４が読み込む。
【００５６】
次に、ステップＳ１０４において、ステップＳ１００において得られた最小長（ｍｉｎｌｅｎ）の値と、ステップＳ１０２において得られたアイテム集合とに基づいて、アイテム集合の長さが最小長（ｍｉｎｌｅｎ）以上のものだけを用いて順序包含木を構成し、順序包含木記憶部３３に記憶する。
【００５７】
次に、ステップＳ１０６において、ステップＳ１０４において得られた順序包含木を用いてアイテム集合同士の共通部分集合を計算し、順序包含木記憶部３３に記憶されている順序包含木を更新する。
【００５８】
次に、ステップＳ１０８において、ステップＳ１０６において得られた順序包含木を出力部３０により出力して処理を終了する。
【００５９】
上記ステップＳ１０４は、図８に示す順序包含木構成処理ルーチンによって実現される。
【００６０】
まず、ステップＳ２００で、ステップＳ１０２において得られた集合のうち、ステップＳ１００において得られた最小長（ｍｉｎｌｅｎ）の値よりも長いアイテム集合の集合Ｘを作成し、集合Ｘに含まれる全てのアイテムを要素とするアイテム集合ｘ０を作成し、順序包含木ＸＯＩの根ノードのアイテム集合に設定するとともに、アイテム集合ｘ０を集合Ｘから取り除いた集合（差集合）を新たな集合Ｘとする。
【００６１】
次に、ステップＳ２０２で、ステップＳ２００において得られた集合Ｘのうち最も長いアイテム集合ｘ１を選択し、選択したアイテム集合ｘ１を出力するとともに、アイテム集合ｘ１を集合Ｘから取り除いた集合（差集合）を新たな集合Ｘとする。
【００６２】
次に、ステップＳ２０４で、ステップＳ２０２で得られたアイテム集合ｘ１の親ノードを順序包含木ＸＯＩから探索する。
【００６３】
次に、ステップＳ２０６で、ステップＳ２０２で得られたアイテム集合ｘ１(追加対象のノード)と、親ノード探索部５４から入力された親ノードｐを用い、アイテム集合ｘ１を順序包含木のＸＯＩにおけるノードｐの子ノードのアイテム集合として追加し、順序包含木を更新する。
【００６４】
次に、ステップＳ２０８で、ステップＳ２０２で得られた集合Ｘが空集合か否かを判定する。集合Ｘが空集合の場合にはステップＳ２１０において、更新した順序包含木を出力して処理を終了する。集合Ｘが空集合でない場合には、ステップＳ２０２に移行して各処理を繰り返す。
【００６５】
上記ステップＳ２０４は、図９に示す親ノード探索処理ルーチンによって実現される。
【００６６】
まず、ステップＳ３００において、ステップＳ２００で得られた順序包含木ＸＯＩの根ノードＲｏｏｔ（ＸＯＩ）を暫定的な親ノードｐに設定する。
【００６７】
次に、ステップＳ３０２において、ステップＳ３００において得られた暫定的な親ノードｐにまだ調べていない子ノードがあるか否かを判定する。調べていない子ノードがある場合には、ステップＳ３０４に移行し、調べていない子ノードがない場合には、ステップＳ３１０に移行する。
【００６８】
次に、ステップＳ３０４において、まだ調べていない子ノードの中から未調査の子ノードを一つ選択してＳｉとする。
【００６９】
次に、ステップＳ３０６において、子ノードＳｉのアイテム集合がステップＳ２０２において選択されたアイテム集合ｘ１を包含する（Ｓｉ⊃ｘ１）かどうか判定する。子ノードＳｉのアイテム集合がアイテム集合ｘ１を包含する場合にはステップＳ３０８に移行し、アイテム集合ｘ１を包含しない場合にはステップＳ３０２に移行し、各処理を繰り返す。
【００７０】
次に、ステップＳ３０８において、ステップＳ３０４で得られた子ノードＳｉを暫定的な親ノードｐとして新たに設定し、ステップＳ３０２に移行して各処理を繰り返す。
【００７１】
ステップＳ３１０において、暫定的な親ノードｐがステップＳ２０２において選択されたアイテム集合ｘ１のノードの親ノードとして確定し、親ノードｐを出力して処理を終了する。
【００７２】
上記ステップＳ１０６は、図１０に示す共通部分計算処理ルーチンによって実現される。
【００７３】
まず、ステップＳ４００において、順序包含木ＸＯＩの根ノードを除く未探索ノードの中から、最も順番の早いノードｙを選択する。
【００７４】
次に、ステップＳ４０２において、ステップＳ４００において選択したノードｙのアイテム集合と、ノードｙの右側にある兄弟ノードの各々のアイテム集合およびそれらの子孫ノードの各々のアイテム集合との間で共通するアイテム部分集合Ｙを各々計算し、ノードｙを探索済みノードとして記憶する。
【００７５】
次に、ステップＳ４０４において、ステップＳ４０２において入力されたアイテム部分集合Ｙのうち、最小長（ｍｉｎｌｅｎ）以上のアイテム集合に対応するノードの各々を順序包含木ＸＯＩに追加して順序包含木ＸＯＩを更新する。
【００７６】
次に、ステップＳ４０６において、入力された順序包含木ＸＯＩの全ノードが探索済みであるか否かを判定する。全ノードが探索済みの場合、ステップＳ４０８に移行し、全ノードが探索済みでない場合にはステップＳ４００に移行し、各処理を繰り返す。
【００７７】
次に、ステップＳ４０８において、更新された順序包含木ＸＯＩを出力して処理を終了する。
【００７８】
＜共通部分計算処理ルーチンの例＞
図６及び図１１を用いて、共通部分計算処理ルーチンを実行した例を説明する。ここでは、最小長（ｍｉｎｌｅｎ）は１に設定するものとする。図６及び図１１では、未探索ノードを中抜きで、探索済ノードを黒塗りで表す。また、ノード選択部６０で現在選択されているノードを四角いノード（□）で、それ以外のノードを丸いノードで表す。さらに、ｙの兄弟ノードおよびそれらの子孫ノードをＲｉｇｈｔＳｉｂＤｅｓｃ（ｙ）と表し、ＲｉｇｈｔＳｉｂＤｅｓｃ（ｙ）の条件を満たすノードを丸い点線で囲んで表すものとする。
【００７９】
図６（ａ）は、順序包含木構成部３４から出力され、共通部分演算部３６に最初に入力される順序包含木ＸＯＩである。この時点では全てのノードが未探索ノードであるため、最初のステップＳ４００では、ノード選択部６０によりｙ＝｛ａ，ｂ，ｃ，ｄ｝が選択される。図６（ａ）では、ノード｛ａ，ｂ，ｃ，ｄ｝が選択されたことを示す四角い記号（□）で表されている。また、ｙ＝｛ａ，ｂ，ｃ，ｄ｝ に対して、ＲｉｇｈｔＳｉｂＤｅｓｃ（ｙ）＝｛｛ｂ，ｃ，ｄ，ｅ｝，｛ａ，ｂ，ｄ，ｅ｝，｛ａ，ｄ，ｅ｝｝である。図６（ａ）では、ＲｉｇｈｔＳｉｂＤｅｃ（ｙ）の要素である３つのノードを点線で囲んで示している。
【００８０】
ステップＳ４０２では、共通部分計算部６２により
【００８１】
【数２】
2014048911.tif 000004
【００８２】
の計算が行われ、共通部分Ｙ＝｛｛ｂ，ｃ，ｄ｝，｛ａ，ｂ，ｄ｝，｛ａ，ｄ｝｝が出力される。そして、ｙ＝｛ａ，ｂ，ｃ，ｄ｝を探索済ノードとして記録する。図６（ｂ）では、｛ａ，ｂ，ｃ，ｄ｝が探索済みノードであることを示す黒塗りの丸いノード（●）で表されている。
【００８３】
ステップＳ４０４では、順序包含木更新部６４により入力された共通部分集合Ｙ＝｛｛ｂ，ｃ，ｄ｝，｛ａ，ｂ，ｄ｝，｛ａ，ｄ｝｝から、最小長（ｍｉｎｌｅｎ）＝１以上のアイテム集合に対応するノードを順序包含木ＸＯＩに追加する。この例では、最小長（ｍｉｎｌｅｎ）＝１なので、Ｙの全ての要素が選択され、図６（ｂ）の順序包含木が得られる。
【００８４】
順序包含木ＸＯＩの中にまだ未探索のノードが含まれているため、ステップＳ４０６では、終了判定部６６によりノード選択部６０の処理を繰り返す。
【００８５】
次に、ステップＳ４００では、ノード選択部６０により図６（ｂ）の順序包含木ＸＯＩからノードを１つ選択する。｛ａ，ｂ，ｃ，ｄ｝は探索済ノードであるため、y=｛ｂ，ｃ，ｄ｝が選択される。そして、共通部分演算部３６が再び実行され、ＲｉｇｈｔＳｉｂＤｅｓｃ（ｙ）＝｛｛ａ，ｂ，ｄ｝，｛ａ，ｄ｝｝とｙ＝｛ｂ，ｃ，ｄ｝の共通部分の演算を行い、Ｙ＝｛｛ｂ，ｄ｝，｛ｄ｝｝が得られる。ｙ＝｛ｂ，ｃ，ｄ｝は探索済みノードとなるため、黒塗りの丸いノード（●）で表されている。
【００８６】
ステップＳ４０４では、順序包含木更新部６４によりＹ＝｛｛ｂ，ｄ｝，｛ｄ｝｝が順序包含木ＸＯＩに追加され、図６（ｃ）の順序包含木が得られる。
【００８７】
以上のステップを繰り返していくと、図６（ｄ），（ｅ），（ｆ），図１１（ａ），（ｂ），（ｃ），（ｄ），（ｅ），（ｆ）の順に順序包含木の探索及び更新が行われ、全てのノードが探索済になる（図１１（ｆ））。このとき、ステップＳ１０８において、終了判定部６６により順序包含木ＸＯＩに含まれる全てのアイテム集合をアイテムパターンとして出力し、処理を終了する。
【００８８】
以上、説明したように、本発明の第１の実施の形態に係るアイテムパターン抽出装置によれば、アイテム集合同士の共通部分のみを計算するため、不要な計算コストを削減することができる。
【００８９】
また、順序包含木と呼ばれる新たなデータ構造により、アイテム集合に存在する包含関係の情報を利用することで、何度も同じパターンを探索することを回避し、ユーザが指定する最小長以上のアイテムパターンを少ない計算コストで抽出することができる。
【００９０】
例えば、図６（ａ）において、｛ａ，ｂ，ｃ，ｄ｝と｛ｂ，ｃ，ｄ｝には親子関係があり、｛ａ，ｂ，ｃ，ｄ｝⊃｛ｂ，ｃ，ｄ｝が成立する。親子関係にあるアイテム集合同士の共通部分は、｛ａ，ｂ，ｃ，ｄ｝∩｛ｂ，ｃ，ｄ｝=｛ｂ，ｃ，ｄ｝となり、子ノードと必ず一致する。したがって、この演算は新たな飽和パターンを発見することにつながらず、不要である。順序包含木がアイテム集合同士の親子関係を保持したデータ構造であることを利用して、共通部分の計算を兄弟ノード及びその子ノードに限定することで、このような不要な共通部分演算を削減できる。
【００９１】
次に、第２の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【００９２】
第２の実施の形態では、複数のアイテム系列からアイテムパターンを抽出する点が第１の実施の形態と異なっている。
【００９３】
＜アイテムパターン抽出装置の構成＞
本発明の第２の実施の形態に係るアイテムパターン抽出装置１００は、入力部１０と、演算部２０と、出力部３０とを備えている。
【００９４】
演算部２０の記憶部３２は、複数のアイテム系列からなる集合を記憶している。
【００９５】
演算部２０の順序包含木構成部３４は、記憶部３２に格納されたアイテム系列の集合から、アイテム系列の長さが最小長（ｍｉｎｌｅｎ）以上のものだけを用いて順序包含木Ｘ０Ｉを作成し、順序包含木記憶部３３へ出力する。演算部２０の共通部分演算部３６は、順序包含木記憶部３３に記憶された順序包含木Ｘ０Ｉから、アイテム系列同士の共通部分を計算し、飽和アイテムパターンを表す順序包含木を生成する。そして、共通部分演算部３６は、新たに生成した順序包含木を出力部３０へ出力する。出力部３０は、共通部分演算部３６から入力された順序包含木を出力する。
【００９６】
＜順序包含木構成部の構成＞
次に、本発明の第２の実施の形態に係る順序包含木構成部の構成について詳細に説明する。順序包含木構成部３４は、まず、ノードＲｏｏｔ（ＸＯＩ）のみを持つ木構造を用意し、アイテム系列ｘに対応するノードを、長さの長い順番に木構造へ追加していくことで順序包含木ＸＯＩを構築する。
【００９７】
順序包含木構成部３４の根ノード作成部５０は、入力部１０から入力された最小長（ｍｉｎｌｅｎ）の値と、記憶部３２から記憶部３２に記憶されているアイテム系列の集合を受け付け、最小長以上のアイテム系列ｘの集合Ｘを作成する。根ノード作成部５０は、ノードＲｏｏｔ（ＸＯＩ）のみを持つ木構造を用意し、入力された集合Ｘに含まれるすべてのアイテム系列を並べた系列ｘ０を作成し、アイテム系列ｘ０に対応するノードを順序包含木ＸＯＩの根ノードＲｏｏｔ（ＸＯＩ）に設定するとともに、アイテム系列ｘ０を集合Ｘから取り除いた系列を新たな集合Ｘとして、ノード選択部５２に出力する。
【００９８】
順序包含木構成部３４のノード選択部５２は、根ノード作成部５０から入力された集合Ｘのうち最も長いアイテム系列ｘ１を選択し、選択したアイテム系列ｘ１を親ノード探索部５４及びノード追加部５６に出力するとともに、アイテム系列ｘ１を集合Ｘから取り除いた系列を新たな集合Ｘとして終了判定部５８に出力する。
【００９９】
順序包含木構成部３４の親ノード探索部５４は、ノード選択部５２から入力されたアイテム系列ｘ１の親ノードを順序包含木ＸＯＩから探索し、得られた親ノードｐをノード追加部５６に出力する。
【０１００】
順序包含木構成部３４のノード追加部５６は、ノード選択部５２から入力されたアイテム系列ｘ１(追加対象のノード)と、親ノード探索部５４から入力された親ノードｐを用い、アイテム系列ｘ１を順序包含木のＸＯＩにおけるノードｐの子ノードのアイテム系列として追加することにより順序包含木ＸＯＩを更新し、更新した順序包含木ＸＯＩを終了判定部５８に出力する。
【０１０１】
順序包含木構成部３４の終了判定部５８は、ノード選択部５２から入力された系列Ｘに要素が残っているか否かを判定し、系列Ｘにまだ要素が残っている場合には、ノード選択部５２に系列Ｘを入力し、順序包含木ＸＯＩへのノードの追加処理を繰り返す。系列Ｘに要素が残っていない場合には、得られた順序包含木ＸＯＩを順序包含木記憶部３３及び共通部分演算部３６に出力する。
【０１０２】
＜共通部分演算部の構成＞
次に、本発明の第２の実施の形態に係る共通部分演算部３６の構成について詳細に説明する。共通部分演算部３６では、従来の方法と異なり、順序包含木ＸＯＩの情報に基づいて効率的な共通部分の計算を行う。
【０１０３】
共通部分演算部３６の共通部分計算部６２は、ノード選択部６０が選択したノードｙのアイテム系列と、ノードｙの右側にある兄弟ノードの各々のアイテム系列およびそれらの子孫ノードの各々のアイテム系列との間で共通するアイテム部分系列Ｙを各々計算し、順序包含木更新部６４に出力するとともに、ノードｙが探索済みノードであることを示す情報を順序包含木記憶部３３に記憶する。なお、アイテム系列同士の共通部分は、Smith−Watermanアルゴリズム（非特許文献４： T. F. Smith and M. S. Waterman: Identification of Common Molecular Subsequences, Journal of molecular biology, Vol. 147, pp.195-197 (1981).）によって計算する。
【０１０４】
共通部分演算部３６の順序包含木更新部６４は、共通部分計算部６２から入力された共通部分系列Ｙのうち、入力部１０から入力された最小長（ｍｉｎｌｅｎ）以上のアイテム系列に対応するノードを順序包含木ＸＯＩへ追加することにより、順序包含木ＸＯＩを更新し、更新した順序包含木ＸＯＩを順序包含木記憶部３３及び終了判定部６６に出力する。順序包含木更新部６４の具体処理は、順序包含木構成部３４のノード選択部５２、親ノード探索部５４、ノード追加部５６、及び終了判定部５８の処理と同じである。
【０１０５】
なお、第２の実施の形態に係るアイテムパターン抽出装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１０６】
以上、説明したように、本発明の第２の実施の形態に係るアイテムパターン抽出装置によれば、アイテム系列同士の共通部分のみを計算するため、不要な計算コストを削減することができる。
【０１０７】
また、順序包含木と呼ばれる新たなデータ構造により、アイテム系列に存在する包含関係の情報を利用することで、何度も同じパターンを探索することを回避し、ユーザが指定する最小長以上のアイテムパターンを少ない計算コストで抽出することができる。
【０１０８】
＜効果確認実験＞
本発明の効果を検証するため、順序包含木を用いた場合と、用いない場合とでアイテム集合及びアイテム系列の各々のアイテムパターンマイニングに要する計算コストの比較を行った。計算コストは、全ての飽和パターンを抽出するのに要した共通部分演算の回数を用いて評価した。アイテム集合のデータベースとして、レコード数１０のｃｈｅｓｓデータベース(http://fimi.ua.ac.be/data/)を用いた。また、アイテム系列のデータベースとして、１５システムの機械翻訳器の出力を用いた。したがって、レコード数は１５である。また、最小長ｍｉｎｌｅｎ は１に設定した。図１４に計算コストの比較結果を示す。本発明の順序包含木を用いた場合は、アイテム集合およびアイテム系列のいずれの場合にも、順序包含木を用いない場合に比べて計算コストが低いことがわかる。
【０１０９】
なお、上記の実施の形態では、順序包含木構成部３４において順序包含木を作成する際、及び共通部分演算部３６において順序包含木にノードを追加する際に、追加するノードに対応するアイテム集合又はアイテム系列が最小長（ｍｉｎｌｅｎ）以上であるか否かの判断を行っているが、これに限定されるものではなく、最小長以上であるか否かに関わらず、アイテム集合またはアイテム系列に対応するノードで順序包含木に追加し、最終的に出力する段階において最小長（ｍｉｎｌｅｎ）以上となるアイテムパターンのみを出力するようにしてもよい。
【０１１０】
また、上記の実施の形態では、出力部３０において更新された順序包含木を出力するようにしているが、これに限定されるものではなく、更新された順序包含木に含まれるアイテム集合またはアイテム系列を出力するようにしてもよい。
【０１１１】
また、本発明は、上記実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１１２】
また、上述のアイテムパターン抽出装置１００は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０１１３】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。また、本実施の形態のアイテムパターン抽出装置１００の各部をハードウエアにより構成してもよい。また、アイテム集合又はアイテム系列が記憶されるデータベースとしては、ハードディスク装置やファイルサーバ等に例示される記憶手段によって実現可能であり、アイテムパターン抽出装置１００内部にデータベースを設けても良いし、外部装置に設けてもよい。
【符号の説明】
【０１１４】
１０   入力部
２０   演算部
３０   出力部
３２   記憶部
３３   順序包含木記憶部
３４   順序包含木構成部
３６   共通部分演算部
５０   根ノード作成部
５２、６０    ノード選択部
５４   親ノード探索部
５６   ノード追加部
５８、６６    終了判定部
６２   共通部分計算部
６４   順序包含木更新部
１００ アイテムパターン抽出装置
【図１】
2014048911.tif 000005
【図２】
2014048911.tif 000006
【図３】
2014048911.tif 000007
【図４】
2014048911.tif 000008
【図５】
2014048911.tif 000009
【図６】
2014048911.tif 000010
【図７】
2014048911.tif 000011
【図８】
2014048911.tif 000012
【図９】
2014048911.tif 000013
【図１０】
2014048911.tif 000014
【図１１】
2014048911.tif 000015
【図１２】
2014048911.tif 000016
【図１３】
2014048911.tif 000017
【図１４】
2014048911.tif 000018
【図１５】
2014048911.tif 000019