(57)【要約】【課題】属性数が大きいデータから頻出パターンを効率的に発見する。【解決手段】アイテムの集合であるレコードの集合から、頻出パターンを発見する頻出パターン発見装置１に、１以上のレコードを要素とする候補レコード集合を生成し、それらのレコードに共通して属するアイテムを抽出して候補アイテム集合を生成し、候補アイテム集合の長さを計算する候補パターン生成部１２と、最小パターン長未満の候補アイテム集合に対応する候補レコード集合を除去するパターン除去部１３と、候補アイテム集合から最小パターン長以上の部分集合を全て抽出する頻出パターン生成部１４とを備える。候補レコード集合生成部２１は、新たな候補レコード集合を生成できなくなるまでレコードの数が最も大きい候補レコード集合で要素が１つだけ異なる２つの候補レコード集合の和集合を新たな候補レコード集合として繰り返し生成する。【選択図】図１
2008159015.tif 000002
【特許請求の範囲】
【請求項１】
アイテムの集合であるレコードの集合の対象データから、あるレコードに属するアイテムの集合であるパターンであって、そのパターンに含まれるアイテムの数が最小パターン長以上で、かつ、そのパターンが最小サポートカウント以上のレコードに含まれる頻出パターンを発見する頻出パターン発見装置において、
前記対象データを記憶する対象データ記憶部と、
前記対象データに含まれる１以上のレコードを要素とする候補レコード集合を生成する候補レコード集合生成部と、
前記候補レコード集合に含まれる各レコードに共通して属するアイテムを抽出して候補アイテム集合を生成する候補アイテム集合生成部と、
前記候補アイテム集合に属するアイテムの数を計算して、その候補アイテム集合の長さとするパターン長計算部と、
長さが前記最小パターン長未満の前記候補アイテム集合に対応する前記候補レコード集合を除去するパターン除去部と、
対応する前記候補レコード集合に含まれるレコードの数が前記最小サポートカウント以上の前記候補アイテム集合の前記最小パターン長以上の部分集合を全て抽出して頻出パターンとする頻出パターン生成部と、
前記頻出パターンを記憶する頻出パターン記憶部と、
を有し、
前記候補レコード集合生成部は、前記候補レコード集合が存在しない場合には、前記対象データに含まれる１つのレコードを要素とする候補レコード集合を生成し、前記候補レコード集合が存在する場合には、新たな前記候補レコード集合を生成できなくなるまで繰り返し前記候補レコード集合のうち前記候補レコード集合の要素のレコードの数が最も大きい前記候補レコード集合から、要素が１つだけ異なる２つの前記候補レコード集合の和集合を新たな前記候補レコード集合として生成する、ことを特徴とする頻出パターン発見装置。
【請求項２】
前記対象データを１以上のアイテムごとに分割する属性分割部と、
前記属性分割部が分割した前記対象データを記憶する複数の分割データ記憶部と、
を有し、
前記候補アイテム集合生成部は、前記分割データ記憶部のそれぞれに対応して設けられて、それぞれが前記候補レコード集合に含まれる各レコードに共通して属する前記分割データ記憶部に記憶されたアイテムを抽出して分割候補アイテム集合を生成する分割候補アイテム集合生成部を備え、
前記パターン長計算部は、前記分割データ記憶部のそれぞれに対応して設けられて、それぞれが前記分割候補アイテム集合に属するアイテムの数を計算して、その分割候補アイテム集合の長さとする分割パターン長計算部と、前記分割データ記憶部のそれぞれに対応して設けられて、前記候補レコード集合に対応する全ての前記分割候補アイテム集合の長さの総和を求めてその候補レコード集合に対応する候補アイテム集合の長さとするパターン長同期部とを備え、
前記頻出パターン生成部は、対応する前記候補レコード集合に含まれるレコードの数が前記最小サポートカウント以上の前記分割候補アイテム集合の全ての和集合を求めて候補アイテム集合とする頻出パターン結合部をさらに備えることを特徴とする請求項１に記載の頻出パターン発見装置。
【請求項３】
アイテムの集合であるレコードの集合の対象データから、あるレコードに属するアイテムの集合であるパターンであって、そのパターンに含まれるアイテムの数が最小パターン長以上で、かつ、そのパターンが最小サポートカウント以上のレコードに含まれる頻出パターンを発見する頻出パターン発見方法において、
前記対象データに含まれる１以上のレコードを要素とする候補レコード集合を生成する候補レコード集合生成工程と、
前記候補レコード集合に含まれる各レコードに共通して属するアイテムを抽出して候補アイテム集合を生成する候補アイテム集合生成工程と、
前記候補アイテム集合に属するアイテムの数を計算して、その候補アイテム集合の長さとするパターン長計算工程と、
長さが前記最小パターン長未満の前記候補アイテム集合に対応する前記候補レコード集合を除去するパターン除去工程と、
対応する前記候補レコード集合に含まれるレコードの数が前記最小サポートカウント以上の前記候補アイテム集合の前記最小パターン長以上の部分集合を全て抽出して頻出パターンとする頻出パターン生成工程と、
を有し、
前記候補レコード集合生成工程は、前記候補レコード集合が存在しない場合には、前記対象データに含まれる１つのレコードを要素とする候補レコード集合を生成し、前記候補レコード集合が存在する場合には、新たな前記候補レコード集合を生成できなくなるまで繰り返し前記候補レコード集合のうち前記候補レコード集合の要素のレコードの数が最も大きい前記候補レコード集合から、要素が１つだけ異なる２つの前記候補レコード集合の和集合を新たな前記候補レコード集合として生成する、ことを特徴とする頻出パターン発見方法。
【請求項４】
前記対象データを１以上のアイテムごとに分割する属性分割工程、
を有し、
前記候補アイテム集合生成工程は、前記属性分割工程で分割された前記対象データのそれぞれに対して、前記候補レコード集合に含まれる各レコードに共通して属する前記分割データ記憶部に記憶されたアイテムを抽出して分割候補アイテム集合を生成する分割候補アイテム集合生成工程を備え、
前記パターン長計算工程は、前記属性分割工程で分割された前記対象データのそれぞれに対して、前記分割候補アイテム集合に属するアイテムの数を計算して、その分割候補アイテム集合の長さとする分割パターン長計算工程と、前記属性分割工程で分割された前記対象データのそれぞれに対して、前記候補レコード集合に対応する全ての前記分割候補アイテム集合の長さの総和を求めてその候補レコード集合に対応する候補アイテム集合の長さとするパターン長同期工程とを備え、
前記頻出パターン生成工程は、さらに対応する前記候補レコード集合に含まれるレコードの数が前記最小サポートカウント以上の前記分割候補アイテム集合の全ての和集合を求めて候補アイテム集合とすることを特徴とする請求項３に記載の頻出パターン発見方法。
【請求項５】
アイテムを順番に並べた集合である系列レコードの集合の対象データから、ある系列レコードに属するアイテムをその系列レコードでの順番に従って並べた集合である系列パターンであって、その系列パターンに含まれるアイテムの数が最小パターン長以上で、かつ、その系列パターンが最小サポートカウント以上の系列レコードに含まれる頻出系列パターンを発見する頻出パターン発見装置において、
前記対象データを記憶する対象データ記憶部と、
前記対象データに含まれる１以上の系列レコードを要素とする候補レコード集合を生成する候補レコード集合生成部と、
前記候補レコード集合に含まれる各系列レコードに共通して存在する系列パターンのうち最長のものを抽出して候補系列パターンを生成する候補系列パターン生成部と、
前記候補系列パターンに属するアイテムの数を計算して、その候補系列パターンの長さとするパターン長計算部と、
長さが前記最小パターン長未満の前記候補系列パターンに対応する前記候補レコード集合を除去するパターン除去部と、
前記パターン除去部で除去されなかった前記候補レコード集合を記憶する候補レコード集合記憶部と、
前記候補レコード集合に対して、その候補レコード集合よりも長さが短い部分集合を生成する部分集合生成部と、
前記候補レコード集合に対して生成された部分集合の少なくとも一つが前記候補レコード集合記憶部に記憶されていない場合には、その候補レコード集合を削除する部分集合検索部と、
対応する前記候補レコード集合に含まれる系列レコードの数が前記最小サポートカウント以上の前記候補系列パターンの前記最小パターン長以上の部分集合を全て抽出して頻出系列パターンとする頻出パターン生成部と、
前記頻出パターンを記憶する頻出パターン記憶部と、
を有し、
前記候補レコード集合生成部は、前記候補レコード集合が存在しない場合には、前記対象データに含まれる１つの系列レコードを要素とする候補レコード集合を生成し、前記候補レコード集合が存在する場合には、新たな前記候補レコード集合を生成できなくなるまで繰り返し前記候補レコード集合のうち前記候補レコード集合の要素の系列レコードの数が最も大きい前記候補レコード集合から、要素が１つだけ異なる２つの前記候補レコード集合の和集合を新たな前記候補レコード集合として生成する、ことを特徴とする頻出パターン発見装置。
【請求項６】
アイテムを順番に並べた集合である系列レコードの集合の対象データから、ある系列レコードに属するアイテムをその系列レコードでの順番に従って並べた集合である系列パターンであって、その系列パターンに含まれるアイテムの数が最小パターン長以上で、かつ、その系列パターンが最小サポートカウント以上の系列レコードに含まれる頻出系列パターンを発見する頻出パターン発見方法において、
前記対象データに含まれる１以上のレコードを要素とする候補レコード集合を生成する候補レコード集合生成工程と、
前記候補レコード集合に含まれる各レコードに共通して存在する系列パターンのうち最長のものを抽出して候補系列パターンを生成する候補アイテム集合生成工程と、
前記候補系列パターンに属するアイテムの数を計算して、その候補系列パターンの長さとするパターン長計算工程と、
長さが前記最小パターン長未満の前記候補系列パターンに対応する前記候補レコード集合を除去するパターン除去工程と、
前記パターン除去工程で除去されなかった前記候補レコード集合を候補レコード集合記憶部に記憶させる候補レコード集合記憶工程と、
前記候補レコード集合に対して、その候補レコード集合よりも長さが短い部分集合を生成する部分集合生成工程と、
前記候補レコード集合に対して生成された部分集合の少なくとも一つが前記候補レコード集合記憶部に記憶されていない場合には、その候補レコード集合を削除する部分集合検索工程と、
対応する前記候補レコード集合に含まれる系列レコードの数が前記最小サポートカウント以上の前記候補系列パターンの前記最小パターン長以上の部分集合を全て抽出して頻出パターンとする頻出パターン生成工程と、
を有し、
前記候補レコード集合生成工程は、前記候補レコード集合が存在しない場合には、前記対象データに含まれる１つの系列レコードを要素とする候補レコード集合を生成し、前記候補レコード集合が存在する場合には、新たな前記候補レコード集合を生成できなくなるまで繰り返し前記候補レコード集合のうち前記候補レコード集合の要素の系列レコードの数が最も大きい前記候補レコード集合から、要素が１つだけ異なる２つの前記候補レコード集合の和集合を新たな前記候補レコード集合として生成する、ことを特徴とする頻出パターン発見方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レコードの集合から、レコードの要素の集合のうち多くのレコードに含まれる頻出パターンを発見する頻出パターン発見装置および頻出パターン発見方法に関する。
【背景技術】
【０００２】
大量のデータから有用な知識を発見する技術は、データマイニングと呼ばれる。データマイニング手法の一つに、頻出パターン抽出がある。頻出パターン抽出とは、データベースに頻出する属性の組み合わせを発見することである。
【０００３】
頻出パターン抽出の方法として、属性空間（属性の組み合わせ）を探索する方法が非特許文献１に開示されている。これを並列化する方法が非特許文献２に開示されている。
【０００４】
また、データマイニングにおいて並列分散処理する方法は、たとえば特許文献１にも開示されている。
【特許文献１】特開２００１−１６７０９８号公報
【非特許文献１】R. Agrawal、他１名、"Fast Algorithms for Mining Association Rules"、Proc. of Intl. Conf. on Very Large Data Bases、ｐ487−499、１９９４年
【非特許文献２】R. Agrawal、他１名、"Parallel Mining of Association Rules"、IEEE Transactions on Knowledge and Data Engineering、Vol.8、Issue 6、１９９６年１２月
【非特許文献３】L. Bergroth、他２名、"A Survey of Longest Common Subsequence Algorithms"、Proc. Of the 7th Intl. Symposium on String Processing Information Retrieval、２０００年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
レコード数よりも属性数が大きい、たとえば遺伝子データなどのデータから頻出パターンを抽出する場合に、レコードごとに頻出パターンを生成すると、属性の組合せが爆発的に多くなる。このため計算時間も爆発的に長くなるという問題点がある。
【０００６】
そこで、本発明は、属性数が大きいデータから頻出パターンを効率的に発見することを目的とする。
【課題を解決するための手段】
【０００７】
上述の課題を解決するため、本発明は、アイテムの集合であるレコードの集合の対象データから、あるレコードに属するアイテムの集合であるパターンであって、そのパターンに含まれるアイテムの数が最小パターン長以上で、かつ、そのパターンが最小サポートカウント以上のレコードに含まれる頻出パターンを発見する頻出パターン発見装置において、前記対象データを記憶する対象データ記憶部と、前記対象データに含まれる１以上のレコードを要素とする候補レコード集合を生成する候補レコード集合生成部と、前記候補レコード集合に含まれる各レコードに共通して属するアイテムを抽出して候補アイテム集合を生成する候補アイテム集合生成部と、前記候補アイテム集合に属するアイテムの数を計算して、その候補アイテム集合の長さとするパターン長計算部と、長さが前記最小パターン長未満の前記候補アイテム集合に対応する前記候補レコード集合を除去するパターン除去部と、対応する前記候補レコード集合に含まれるレコードの数が前記最小サポートカウント以上の前記候補アイテム集合の前記最小パターン長以上の部分集合を全て抽出して頻出パターンとする頻出パターン生成部と、前記頻出パターンを記憶する頻出パターン記憶部と、を有し、前記候補レコード集合生成部は、前記候補レコード集合が存在しない場合には、前記対象データに含まれる１つのレコードを要素とする候補レコード集合を生成し、前記候補レコード集合が存在する場合には、新たな前記候補レコード集合を生成できなくなるまで繰り返し前記候補レコード集合のうち前記候補レコード集合の要素のレコードの数が最も大きい前記候補レコード集合から、要素が１つだけ異なる２つの前記候補レコード集合の和集合を新たな前記候補レコード集合として生成する、ことを特徴とする。
【０００８】
また、本発明は、アイテムの集合であるレコードの集合の対象データから、あるレコードに属するアイテムの集合であるパターンであって、そのパターンに含まれるアイテムの数が最小パターン長以上で、かつ、そのパターンが最小サポートカウント以上のレコードに含まれる頻出パターンを発見する頻出パターン発見方法において、前記対象データに含まれる１以上のレコードを要素とする候補レコード集合を生成する候補レコード集合生成工程と、前記候補レコード集合に含まれる各レコードに共通して属するアイテムを抽出して候補アイテム集合を生成する候補アイテム集合生成工程と、前記候補アイテム集合に属するアイテムの数を計算して、その候補アイテム集合の長さとするパターン長計算工程と、長さが前記最小パターン長未満の前記候補アイテム集合に対応する前記候補レコード集合を除去するパターン除去工程と、対応する前記候補レコード集合に含まれるレコードの数が前記最小サポートカウント以上の前記候補アイテム集合の前記最小パターン長以上の部分集合を全て抽出して頻出パターンとする頻出パターン生成工程と、を有し、前記候補レコード集合生成工程は、前記候補レコード集合が存在しない場合には、前記対象データに含まれる１つのレコードを要素とする候補レコード集合を生成し、前記候補レコード集合が存在する場合には、新たな前記候補レコード集合を生成できなくなるまで繰り返し前記候補レコード集合のうち前記候補レコード集合の要素のレコードの数が最も大きい前記候補レコード集合から、要素が１つだけ異なる２つの前記候補レコード集合の和集合を新たな前記候補レコード集合として生成する、ことを特徴とする。
【０００９】
また、本発明は、アイテムを順番に並べた集合である系列レコードの集合の対象データから、ある系列レコードに属するアイテムをその系列レコードでの順番に従って並べた集合である系列パターンであって、その系列パターンに含まれるアイテムの数が最小パターン長以上で、かつ、その系列パターンが最小サポートカウント以上の系列レコードに含まれる頻出系列パターンを発見する頻出パターン発見装置において、前記対象データを記憶する対象データ記憶部と、前記対象データに含まれる１以上の系列レコードを要素とする候補レコード集合を生成する候補レコード集合生成部と、前記候補レコード集合に含まれる各系列レコードに共通して存在する系列パターンのうち最長のものを抽出して候補系列パターンを生成する候補系列パターン生成部と、前記候補系列パターンに属するアイテムの数を計算して、その候補系列パターンの長さとするパターン長計算部と、長さが前記最小パターン長未満の前記候補系列パターンに対応する前記候補レコード集合を除去するパターン除去部と、前記パターン除去部で除去されなかった前記候補レコード集合を記憶する候補レコード集合記憶部と、前記候補レコード集合に対して、その候補レコード集合よりも長さが短い部分集合を生成する部分集合生成部と、前記候補レコード集合に対して生成された部分集合の少なくとも一つが前記候補レコード集合記憶部に記憶されていない場合には、その候補レコード集合を削除する部分集合検索部と、対応する前記候補レコード集合に含まれる系列レコードの数が前記最小サポートカウント以上の前記候補系列パターンの前記最小パターン長以上の部分集合を全て抽出して頻出系列パターンとする頻出パターン生成部と、前記頻出パターンを記憶する頻出パターン記憶部と、を有し、前記候補レコード集合生成部は、前記候補レコード集合が存在しない場合には、前記対象データに含まれる１つの系列レコードを要素とする候補レコード集合を生成し、前記候補レコード集合が存在する場合には、新たな前記候補レコード集合を生成できなくなるまで繰り返し前記候補レコード集合のうち前記候補レコード集合の要素の系列レコードの数が最も大きい前記候補レコード集合から、要素が１つだけ異なる２つの前記候補レコード集合の和集合を新たな前記候補レコード集合として生成する、ことを特徴とする。
【００１０】
また、本発明は、アイテムを順番に並べた集合である系列レコードの集合の対象データから、ある系列レコードに属するアイテムをその系列レコードでの順番に従って並べた集合である系列パターンであって、その系列パターンに含まれるアイテムの数が最小パターン長以上で、かつ、その系列パターンが最小サポートカウント以上の系列レコードに含まれる頻出系列パターンを発見する頻出パターン発見方法において、前記対象データに含まれる１以上のレコードを要素とする候補レコード集合を生成する候補レコード集合生成工程と、前記候補レコード集合に含まれる各レコードに共通して存在する系列パターンのうち最長のものを抽出して候補系列パターンを生成する候補アイテム集合生成工程と、前記候補系列パターンに属するアイテムの数を計算して、その候補系列パターンの長さとするパターン長計算工程と、長さが前記最小パターン長未満の前記候補系列パターンに対応する前記候補レコード集合を除去するパターン除去工程と、前記パターン除去工程で除去されなかった前記候補レコード集合を候補レコード集合記憶部に記憶させる候補レコード集合記憶工程と、前記候補レコード集合に対して、その候補レコード集合よりも長さが短い部分集合を生成する部分集合生成工程と、前記候補レコード集合に対して生成された部分集合の少なくとも一つが前記候補レコード集合記憶部に記憶されていない場合には、その候補レコード集合を削除する部分集合検索工程と、対応する前記候補レコード集合に含まれる系列レコードの数が前記最小サポートカウント以上の前記候補系列パターンの前記最小パターン長以上の部分集合を全て抽出して頻出パターンとする頻出パターン生成工程と、を有し、前記候補レコード集合生成工程は、前記候補レコード集合が存在しない場合には、前記対象データに含まれる１つの系列レコードを要素とする候補レコード集合を生成し、前記候補レコード集合が存在する場合には、新たな前記候補レコード集合を生成できなくなるまで繰り返し前記候補レコード集合のうち前記候補レコード集合の要素の系列レコードの数が最も大きい前記候補レコード集合から、要素が１つだけ異なる２つの前記候補レコード集合の和集合を新たな前記候補レコード集合として生成する、ことを特徴とする。
【発明の効果】
【００１１】
本発明によれば、属性数が大きいデータから頻出パターンを効率的に発見することができる。
【発明を実施するための最良の形態】
【００１２】
本発明に係る頻出パターン発見装置および頻出パターン発見方法の実施の形態を、図面を参照して説明する。なお、同一または類似の構成には同一の符号を付し、重複する説明は省略する。
【００１３】
［第１の実施の形態］
図１は、本発明に係る頻出パターン発見装置の第１の実施の形態におけるブロック図である。
【００１４】
頻出パターン発見装置１は、対象データ記憶部１１、候補パターン生成部１２、パターン除去部１３、頻出パターン生成部１４、頻出パターン記憶部１５、入力手段１６および出力手段１７を有している。
【００１５】
頻出パターンを発見する対象となる対象データは、入力手段１６から入力されて対象データ記憶部に記憶される。入力手段１６は、たとえば対象データを収集した別の計算機から対象データを受信するインターフェースである。
【００１６】
図２および図３は、頻出パターンを発見する対象となるデータの例である。
【００１７】
図２に示す対象データは、関係データベース形式の例である。関係データベースはレコードＩＤと属性の組合せで構成される。この例では、属性が２値の場合であり、レコードＩＤで特定されるレコードがその属性を持つ場合を○、持たない場合を空白で表記している。
【００１８】
なお、２値属性でなく、多値属性や連続値属性でも２値属性に変換可能である。たとえば、医療診断データベースにおいて血圧という多値属性があり、高い、並み、低いの３値を取るとする。この場合、血圧（高い）、血圧（並み）、血圧（低い）という３つの２値属性に変換可能である。また、身長のような連続値属性の場合であっても、身長（１５０ｃｍ未満）、身長（１５０ｃｍ以上１７０ｃｍ未満）、身長（１７０ｃｍ以上）のように離散化することによって、２値属性に変換可能である。
【００１９】
図３に示す対象データは、トランザクションデータベース形式の例であり、図２に示す関係データベース形式のデータを変換したものである。どのような関係データベース形式のデータでもトランザクションデータベース形式のデータに変換可能である。関係データベース形式の各レコードが持つ属性を抽出して属性名を列挙すればトランザクションデータベース形式になる。このとき、レコードをトランザクション、属性をアイテムと呼ぶことがある。
【００２０】
トランザクションデータベース形式のデータは、トランザクションＩＤで特定されるトランザクションの集合である。各トランザクションは、アイテムの集合である。
【００２１】
以下の説明では、レコードとトランザクションは同じ意味として用いる。属性とアイテムを同じ意味で用いる。また、レコードの集合をレコードＩＤの並びで表すこととする。たとえばレコードＩＤが０と１のレコードを要素とする集合を０１と表す。同様に、アイテムの集合は、アイテムの並びで表すこととする。たとえばＢ、Ｃ、Ｅを要素とするアイテムの集合をＢＣＥと表す。
【００２２】
頻出パターンとは、対象データに含まれる、最小サポートカウント以上のサポートカウントを持つ全てのパターンである。ここで、パターンとは、あるトランザクションに含まれるアイテムの組み合わせ、すなわちあるトランザクションを構成するアイテム集合の部分集合である。サポートカウントとは、そのパターンが含まれているトランザクションの数である。最小サポートカウントとは、そのパターンが、対象データ中に「頻出」であると判定される最小のサポートカウントである。
【００２３】
データが高次元であるとは、アイテム数（属性数）が多いことを指す。本実施の形態では、属性数が極めて大きい（数千から数万のオーダ）場合を想定している。例として医療診断データベースを挙げたが、本発明は任意のデータに適用可能である。
【００２４】
候補パターン生成部１２は、候補レコード集合生成部２１、候補アイテム集合生成部２２およびパターン長計算部２３を有している。
【００２５】
候補レコード集合生成部２１は、対象データに含まれる１以上のレコードを要素とする候補レコード集合を生成する。候補アイテム集合生成部２２は、候補レコード集合に含まれる各レコードに共通して属するアイテムを抽出して、その候補レコード集合に対応する候補アイテム集合を生成する。パターン長計算部２３は、候補アイテム集合のパターン長を計算する。パターン長とは、あるアイテム集合に属するアイテムの数である。
【００２６】
パターン除去部１３は、候補レコード集合のうち、その候補レコード集合に対応する候補アイテム集合のパターン長が最小パターン長未満の候補レコード集合を除去する。
【００２７】
頻出パターン生成部１４は、対応する候補レコード集合に含まれるレコードの数が最小サポートカウント以上の候補アイテム集合から、最小パターン長以上の部分集合を全て抽出して頻出パターンとする。
【００２８】
抽出された頻出パターンは、頻出パターン生成部１４から頻出パターン記憶部１５に伝達される。また、頻出パターン記憶部１５は、頻出パターンを出力手段１７に伝達する。出力手段１７は、たとえばディスプレイに頻出パターンを表示したり、別の計算機に頻出パターンを送信する。
【００２９】
次に、本実施の形態における頻出パターン発見方法を説明する。
【００３０】
図４は、本発明に係る頻出パターン発見方法の第１の実施の形態における流れ図である。
【００３１】
まず、対象データを入力手段１６から入力して対象データ記憶部１１に記憶する（工程Ｓ１）。また、繰り返しの回数ｋを１に設定する。
【００３２】
次に、候補レコード集合生成部２１は、長さがｋの候補レコード集合を生成する（工程Ｓ２）。候補レコード集合の長さとは、その候補レコード集合に含まれるレコードの数である。
【００３３】
１回目の繰り返し（パス）の場合には、長さ１の候補レコード集合を生成する。対象データに含まれるそれぞれのレコードを１つずつ含む集合を、長さ１の候補レコード集合とすることができる。これにより、対象データに含まれるレコードの総数と同じ数の候補レコード集合が生成される。
【００３４】
ｋ回目のパスにおいては、候補レコード集合生成部２１は、レコード長がｋ−１の候補レコード集合からレコード長がｋの候補レコード集合を生成する。rA、rBが、長さｋ−１の候補レコード集合とし、式（１）を満たすとき、式（２）によって長さｋのレコード集合を生成する。
【００３５】
(rA[1]=rB[1])∧(rA[2]=rB[2])∧…∧(rA[k-2]=rB[k-2])∧(rA[k-1]<rB[k-1])  （１）
rA[1]rA[2]rA[k-2]rA[k-1]rB[k-1]                                         （２）
ここで、「＜」は、辞書順を示し、rA[i]、rB[i]は、それぞれrA、rBのｉ番目のレコードとする。
【００３６】
次に、候補レコード集合生成部２１は、長さｋの候補レコード集合が存在するか否かを判定する（工程Ｓ３）。長さｋの候補レコード集合が存在していれば、工程Ｓ４ないし工程Ｓ６が実行され、存在しなければ工程Ｓ７および工程Ｓ８が実行される。このようにして、長さｋの候補レコード集合が空集合になるまで、ｋを１ずつ増加させながら、工程Ｓ３ないし工程Ｓ６が繰り返される。
【００３７】
工程Ｓ４では、候補アイテム集合生成部２２が、長さｋの候補レコード集合に含まれる全てのレコードに共通するアイテムの集合である候補アイテム集合を生成する。たとえばある候補レコード集合がrAおよびrBからなるとき、それらの候補レコード集合に含まれる候補アイテム集合をそれぞれＩＡ、ＩＢとすると、候補レコード集合rArBに共通するアイテムの集合であるＩＡ∩ＩＢを生成する。
【００３８】
工程Ｓ５では、パターン長計算部２３が、長さｋの各候補レコード集合に対応するそれぞれの候補アイテム集合のパターン長を計算する。
【００３９】
工程Ｓ６では、パターン除去部１３が、長さが最小パターン長未満である候補アイテム集合に対応する候補レコード集合を削除する。
【００４０】
工程Ｓ７では、頻出パターン生成部１４が、パターン除去部１３によって除去されなかった全ての候補レコード集合のうち、最小サポートカウント未満のレコード長の候補レコード集合を除去する。
【００４１】
工程Ｓ８では、頻出パターン生成部１４が、残った全ての候補レコード集合Ｆ’に対応する候補アイテム集合の、長さが最小パターン長以上の部分集合を全て抽出する。ここで抽出された集合Ｆが頻出パターンとなる。
【００４２】
次に、図２および図３で示した対象データから、最小パターン長を３、最小サポートカウントを３とした場合の、本実施の形態における頻出パターン発見の流れを説明する。
【００４３】
図５は、本発明に係る頻出パターン発見方法の第１の実施の形態におけるデータの木構造の例を示す図である。木は節と枝から構成される。図５において、直線（枝）で結ばれたそれぞれの数字は、レコードＩＤを示す節である。また、あるレコードＩＤの左側に直線で結ばれた全てのレコードＩＤの組が候補レコード集合を示している。アルファベットはアイテムを示し、候補レコード集合に対応する候補アイテム集合を、その候補レコード集合の最も右側に表示したレコードＩＤの近傍に示している。四角で囲んだ数字は、パターン長を示す。
【００４４】
図２および図３で示した対象データを対象データ記憶部１１に記憶した（工程Ｓ１）後、第１回目のパス（ｋ＝１）においては、長さ１の候補レコード集合である０，１，２，３，４，５の６つの集合が生成される（工程Ｓ２）。長さ１の候補レコード集合が存在するため（工程Ｓ３）、次に、それぞれの候補レコード集合に含まれる候補アイテム集合ＡＢＤＥ、ＢＣＥ、ＡＢＤＥ、ＡＢＣＥ、ＡＢＣＤＥ、ＢＣＤが計算される（工程Ｓ４）。また、それぞれの候補アイテム集合のパターン長が計算される（工程Ｓ５）。なお、ここでは、最小パターン長（３）に満たない候補レコード集合は存在しないため、工程Ｓ６で除去される候補レコード集合はない。
【００４５】
第２回目のパス（ｋ＝２）においては、長さ１の候補レコード集合から長さ２の候補レコード集合が生成される（工程Ｓ２）。たとえば、０と１という２つの候補レコード集合は、式（１）の関係を満たしているため、式（２）により、０１という候補レコード集合を生成する。同様に他の長さ１の候補レコード集合も組み合わせることにより、それぞれ長さ２の候補レコード集合である０１，０２，０３，０４，・・・，４５という１４個の集合が生成される。
【００４６】
長さ２の候補レコード集合が存在するため（工程Ｓ３）、次に候補アイテム集合を計算する（工程Ｓ４）。たとえば、０という候補レコード集合に含まれるアイテム集合がＡＢＤＥ、１に含まれるアイテム集合がＢＥである。したがって、０１という候補レコード集合に対応する候補アイテム集合は、ＡＢＤＥとＢＥに共通するアイテムの集合であるＢＥとなる。
【００４７】
次に、長さ２の候補レコード集合に対してアイテム集合の長さを計算する（工程Ｓ５）。たとえば０１という候補レコード集合に対応する候補アイテム集合はＢＥであり、その長さは２である。
【００４８】
全ての候補レコード集合に対して候補アイテム集合の長さを計算した後、最小パターン長（３）に満たない候補レコード集合を除去する（工程Ｓ６）。ここでは、候補アイテム集合の長さが３未満の、０１、０５、１２、１５、２５、３５という候補レコード集合が除去される。したがって、長さが２の候補レコード集合のうち、０２、０３、０４、１３、１４、２３、２４、３４、４５という９つの候補レコード集合が残る。
【００４９】
第３回目のパス（ｋ＝３）においては、長さ２の候補レコード集合から長さ３の候補レコード集合が生成される（工程Ｓ２）。この例では、０２３、０２４、０３４、１３４、２３４という５つの候補レコード集合が生成される。
【００５０】
長さ３の候補レコード集合が存在するため（工程Ｓ３）、候補アイテム集合が計算され（工程Ｓ４）、候補アイテム集合の長さが計算される（工程Ｓ５）。全ての候補アイテム集合の長さは最小レコード長（３）以上であるため、除去される候補レコード集合はない（工程Ｓ６）。
【００５１】
第４回目のパス（ｋ＝４）においては、長さ３の候補レコード集合から長さ４の候補レコード集合が生成される（工程Ｓ２）。この例では、０２３４という１つの候補レコード集合が生成される。
【００５２】
長さ４の候補レコード集合が存在するため（工程Ｓ３）、候補アイテム集合が計算され（工程Ｓ４）、候補アイテム集合の長さが計算される（工程Ｓ５）。全ての候補アイテム集合の長さは最小レコード長（３）以上であるため、除去される候補レコード集合はない（工程Ｓ６）。
【００５３】
第５回目のパス（ｋ＝５）においては、長さ４の候補レコード集合から長さ５の候補レコード集合が生成される（工程Ｓ２）。この例では、生成される候補レコード集合が存在しない。このため、工程Ｓ７および工程Ｓ８を実行する。
【００５４】
ここでは、最小サポートカウントを３としているので、レコード長が３未満、すなわち、レコード長が１または２の候補レコード集合は除去される（工程Ｓ７）。残った候補レコード集合は、０２３、０２４、０３４、１３４、２３４、０２３４の６つとなる。
【００５５】
これらの候補レコード集合に対応する候補アイテム集合は、それぞれＡＢＥ、ＡＢＤＥ、ＡＢＥ、ＢＣＥ、ＡＢＥ、ＡＢＥとなり、これらの候補アイテム集合の集合がＦ’である。このうち、ＡＢＥ、ＢＣＥには、最小パターン長（３）以上の部分集合は、それら自身しか存在しない。一方、ＡＢＤＥには、最小パターン長（３）以上の部分集合は、ＡＢＤ、ＡＢＥ、ＡＤＥ、ＢＤＥ、ＡＢＤＥの５つの部分集合が存在する。
【００５６】
したがって、これらの候補アイテム集合の最小パターン長以上の部分集合を全て抽出することにより、頻出パターンの集合Ｆとして、Ｆ＝｛ＡＢＤ、ＡＢＥ、ＡＤＥ、ＢＣＥ、ＢＤＥ、ＡＢＤＥ｝が得られる。
【００５７】
このように、本実施の形態における頻出パターンの発見では、属性空間（属性の組み合わせ）の探索ではなく、レコード空間（レコードの組み合わせ)の探索を行う。このため、属性数が多くなっても、属性の組み合わせの爆発的な増加が生じることがない。したがって、属性数が大きいデータから頻出パターンを効率的に発見することができる。
【００５８】
また、頻出パターンの最小の長さである最小パターン長によって、候補アイテム集合およびそれに対応する候補レコード集合を枝刈りするため、必要な演算が少なくなり、効率的に頻出パターン発見の処理を行うことができる。
【００５９】
［第２の実施の形態］
図６は、本発明に係る頻出パターン発見装置の第２の実施の形態におけるブロック図である。
【００６０】
本実施の形態の頻出パターン発見装置は、第１の実施の形態における頻出パターン発見装置の一部を分散メモリ型並列計算機で構成して、一部の処理を並列に行うようにしたものである。
【００６１】
頻出パターン発見装置２は、対象データ記憶部１１、属性分割部３１、データ配置部３２、複数の計算ユニット３６、頻出パターン結合生成部３７、頻出パターン記憶部１５、入力手段１６および出力手段１７を有している。なお、図６では計算ユニット３６の台数は４台であるが、適宜増減可能である。計算ユニット３６のそれぞれは、たとえば分散メモリ型並列計算機を構成するそれぞれの計算装置である。
【００６２】
属性分割部３１は、対象データ記憶部１１に記憶された対象データを属性方向に分割する。属性方向への分割とは、対象データに含まれる属性を複数の組に分割し、レコードＩＤと分割された属性の組に対応する属性のデータとから構成される分割データを生成することである。
【００６３】
データ配置部３２は、各分割データをそれぞれの計算ユニット３６に伝達する。
【００６４】
図７は、本発明に係る頻出パターン発見装置の第２の実施の形態における計算ユニットのブロック図である。
【００６５】
各計算ユニット３６は、分割データ記憶部３３、分割候補生成部３４、パターン長同期部３５およびパターン除去部１３を有している。分割データ記憶部３３には、データ配置部３２から伝達された分割データが記憶される。
【００６６】
分割候補生成部３４は、候補レコード集合生成部４１、分割候補アイテム集合生成部４２および分割パターン長計算部４３を有している。各分割候補生成部３４は、それぞれに割り振られた分割データに対して、第１の実施の形態の候補パターン生成部１２（図１参照）と同様の処理を行う。
【００６７】
パターン長同期部３５は、それぞれの計算ユニット３６で計算された分割データに対するパターン長を、他の全てのパターン長同期部３５に伝達する。それぞれのパターン長同期部３５は、全ての計算ユニット３６で計算された分割データに対するパターン長の総和をそれぞれ求めてパターン長を同期させ、対応する候補レコード集合に対応する候補アイテム集合の長さを求める。
【００６８】
パターン除去部１３は、パターン長同期部３５が同期したパターン長を用いて、候補レコード集合のうち、長さが最小パターン長未満の候補アイテム集合に対応する候補レコード集合を除去する。
【００６９】
頻出パターン結合生成部３７は、各計算ユニット３６が求めた分割データに対する分割候補アイテム集合を結合して候補アイテム集合を生成し、その候補アイテム集合を用いて、頻出パターンを生成する。
【００７０】
図８は、本発明に係る頻出パターン発見方法の第２の実施の形態における流れ図である。
【００７１】
まず、対象データを対象データ記憶部１１に記憶する（工程Ｓ１）。対象データ記憶部１１に記憶された対象データは、属性分割部３１によって１以上の属性ごとに分割される（工程Ｓ１１）。分割された対象データは、データ配置部３２によって各計算ユニット３６に伝達されて、分割データ記憶部３３に分割対象データとして記憶される（工程Ｓ１１）。
【００７２】
各計算ユニット３６は、それぞれの分割対象データに対して、並行して工程Ｓ２、工程Ｓ３、工程Ｓ４、工程Ｓ５１、工程Ｓ５２、工程Ｓ６を行う。
【００７３】
次に、各計算ユニット３６による分割候補アイテム集合の生成方法を説明する。
【００７４】
まず、繰り返しの回数ｋが１に設定される。
【００７５】
次に、各候補レコード集合生成部４１は、第１の実施の形態と同様に、長さがｋの候補レコード集合を生成する（工程Ｓ２）。なお、各候補レコード集合生成部４１が生成する候補レコード集合は、全て同一となる。
【００７６】
次に、候補レコード集合生成部４１は、第１の実施の形態と同様に、長さｋの候補レコード集合が空集合か否かを判定する（工程Ｓ３）。長さｋの候補レコード集合が空集合でなければ、工程Ｓ４、工程Ｓ５１、工程Ｓ５２および工程Ｓ６が実行され、空集合であれば工程Ｓ７１、工程Ｓ７および工程Ｓ８が実行される。このようにして、長さｋの候補レコード集合が空集合になるまで、工程Ｓ４、工程Ｓ５１、工程Ｓ５２および工程Ｓ６が繰り返される。
【００７７】
工程Ｓ４では、長さｋの候補レコード集合に共通するアイテムの集合を計算する。本実施の形態では、各分割候補アイテム集合生成部４２が、それぞれに割り振られた分割データ記憶部３３に記憶された分割データに含まれるアイテムの集合を生成する。このアイテムの集合を分割候補アイテム集合と呼ぶこととする。全ての分割候補アイテム集合を、対応する候補レコード集合ごとに結合した集合が、第１の実施の形態における候補アイテム集合に相当する。したがって、全ての分割候補アイテム集合生成部をまとめると、第１の実施の形態における候補アイテム集合生成部２２（図１参照）に相当する。
【００７８】
工程Ｓ５１では、それぞれの分割パターン長計算部４３が、長さｋの候補レコード集合に対応する分割候補アイテム集合のパターン長を計算し、パターン長同期部３５に伝達される。
【００７９】
工程Ｓ５２では、各パターン長同期部３５の間で相互に伝達して、候補アイテム集合のパターン長の同期を取る。つまり、各パターン長同期部３５は、それぞれの分割パターン長計算部４３が計算した分割候補アイテム集合のパターン長を他のパターン長同期部３５に伝達する。その後、全ての分割候補アイテム集合のパターン長の総和を計算することにより、それぞれの候補レコード集合に対応する候補アイテム集合のパターン長を算出する。これにより、全てのパターン長同期部３５は、それぞれの候補レコード集合に対応する候補アイテム集合のパターン長として同じ値を持つこととなる。したがって、すべての分割パターン長計算部４３とパターン長同期部３５をまとめると、第１の実施の形態におけるパターン長計算部２３（図１参照）に相当する。
【００８０】
なお、各分割候補生成部３４は、すべて同じ候補レコード集合を生成する。このため、候補レコード集合の並び方を各分割候補生成部３４で同じにしておくことができる。すると、工程Ｓ５２では、分割候補アイテム集合のパターン長の並びだけを相互に伝達しあうことによって、候補アイテム集合のパターン長の同期を取ることができる。
【００８１】
工程Ｓ６では、パターン除去部１３が、長さが最小パターン長未満である候補アイテム集合に対応する候補レコード集合を削除する。なお、ここで用いる候補アイテム集合のパターン長とは、工程Ｓ５２で同期を取った値を用いる。
【００８２】
工程Ｓ７では、頻出パターン結合生成部３７が、候補レコード集合のうち、最小サポートカウント未満のレコード長の候補レコード集合を除去する。工程Ｓ７１では、頻出パターン結合生成部３７が、パターン除去部１３によって除去されなかった全ての候補レコード集合に対して、それぞれの候補レコード集合に対応する分割候補アイテム集合の和集合を求めて、候補アイテム集合を生成する。
【００８３】
工程Ｓ８では、頻出パターン結合生成部３７が、残った全ての候補レコード集合Ｆ’に対応する候補アイテム集合の、長さが最小パターン長以上の部分集合を全て抽出する。ここで抽出された集合Ｆが頻出パターンとなる。
【００８４】
次に、第１の実施の形態と同じ対象データから、本実施の形態で頻出パターンを発見する流れについて説明する。なお、対象データを２つに分割する場合について説明するが、３以上に分割する場合でも同様である。
【００８５】
図９は、本実施の形態における対象データの分割方法の例を示す図である。
【００８６】
第１の実施の形態と同じ対象データ６０１は、アイテム（属性）ごとに分割されて、２つの分割対象データ６０２，６０３となり（工程Ｓ１１）、分割データ記憶部３３に記憶される（工程Ｓ１２）。以下の説明では、符号６０２で示すデータを第１の分割データ、符号６０３で示すデータを第２の分割データと呼ぶこととする。また、第１の分割データが記憶される分割データ記憶部３３を有する計算ユニット３６を第１の計算ユニット、第２の分割データが記憶される分割データ記憶部３３を有する計算ユニット３６を第２の計算ユニットと呼ぶこととする。
【００８７】
図１０および図１１は、本実施の形態における頻出パターン発見方法による分割データの木構造の例を示す図である。図１０は第１の分割データ、図１１は第２の分割データを示している。
【００８８】
第１回目のパス（ｋ＝１）においては、長さ１の候補レコード集合である０、１、２、３、４、５の６つの集合が、それぞれの候補レコード集合生成部で生成される（工程Ｓ２）。長さ１の候補レコード集合が存在するため（工程Ｓ３）、次に、それぞれの候補レコード集合に含まれる候補アイテム集合が計算される（工程Ｓ４）。
【００８９】
ここで、候補アイテム集合は、同一の計算ユニット３６内には存在しておらず、第１および第２の計算ユニット３６内に分割されて存在していることとなる。たとえば、０という候補レコード集合に対応する候補アイテム集合ＡＢＤＥは、第１の計算ユニットに存在するＡＢという分割候補アイテム集合と、第２の計算ユニットに存在するＤＥという分割候補アイテム集合の和集合である。また、これらの分割候補アイテム集合のそれぞれの長さ２および２は、第１および第２の計算ユニットの分割パターン長計算部４３でそれぞれ計算される。
【００９０】
また、それぞれの分割候補アイテム集合の長さが計算される（工程Ｓ５）。たとえば、０という候補レコード集合に対応するＡＢという分割候補アイテム集合とＤＥという分割候補アイテム集合それぞれの長さ２および２は、第１および第２の計算ユニットの分割パターン長計算部４３でそれぞれ計算される。
【００９１】
それぞれの分割パターン長計算部４３で計算された分割候補アイテム集合の長さは、工程Ｓ２で互いに伝達され、候補アイテム集合のパターン長の同期が取られる。たとえば、０という候補レコード集合に対応するＡＢという分割候補アイテム集合とＤＥという分割候補アイテム集合それぞれの長さ２および２は、第１および第２の計算ユニットの分割パターン長計算部４３の間で相互に伝達される。これによりそれぞれのパターン長同期部３５は、０という候補レコード集合に対応するＡＢＤＥのパターン長を２＋２と計算することができる。
【００９２】
第２回目のパス（ｋ＝２）においては、長さ１の候補レコード集合から長さ２の候補レコード集合が生成される（工程Ｓ２）。たとえば、０と１という２つの候補レコード集合は、１（＝ｋ−１）番目のレコードのみが異なり、式（１）の関係を満たしているため、式（２）により、０１という候補レコード集合を生成する。同様に他の長さ１の候補レコード集合も組み合わせることにより、それぞれ長さ２の候補レコード集合である０１，０２，０３，０４，・・・，４５という１４個の集合が生成される。
【００９３】
長さ２の候補レコード集合が存在するため（工程Ｓ３）、次に候補アイテム集合を計算する（工程Ｓ４）。
【００９４】
これらの候補レコード集合に対応する候補アイテム集合は、候補レコード集合５０４に含まれる個々のレコードに属するアイテム集合の共通アイテム集合である。たとえば、０という候補レコード集合に含まれるアイテム集合がＡＢＤＥ、１に含まれるアイテム集合がＢＥである。したがって、０１という候補レコード集合に対応する候補アイテム集合は、ＡＢＤＥとＢＥに共通するアイテムの集合であるＢＥとなる。
【００９５】
次に、長さ２の候補レコード集合に対してアイテム集合の長さを計算する（工程Ｓ５）。たとえば０１という候補レコード集合に対応する候補アイテム集合はＢＥであり、その長さは２である。
【００９６】
同様に繰り返し回数ｋを増加させながら、レコード長がｋの候補レコード集合が存在しなくなるまで、上述の処理が繰り返される。第５回目のパス（ｋ＝５）においては、長さ４の候補レコード集合から長さ５の候補レコード集合が生成される（工程Ｓ２）。この例では、生成される候補レコード集合が存在しなくなる。
【００９７】
この例では、最小サポートカウントを３としているので、レコード長が３未満、すなわち、レコード長が１または２の候補レコード集合は除去される（工程Ｓ７）。残った候補レコード集合は、０２３、０２４、０３４、１３４、２３４、０２３４の６つとなる。
【００９８】
次に、これらのそれぞれの候補レコード集合に対応する分割候補アイテム集合の和集合を求める（工程Ｓ７１）。たとえば０２３という候補レコード集合に対応する分割候補アイテム集合は、ＡＢおよびＥであるので、これらの和集合であるＡＢＥは候補アイテム集合となる。同様にして、第１の実施の形態と同じＡＢＥ、ＡＢＤＥ、ＡＢＥ、ＢＣＥ、ＡＢＥ、ＡＢＥという候補アイテム集合の集合Ｆ’が得られる。さらに第１の実施の形態と同様に、これらの候補アイテム集合の最小パターン長以上の部分集合を全て抽出することによって、頻出パターンの集合Ｆ＝｛ＡＢＤ、ＡＢＥ、ＡＤＥ、ＢＣＥ、ＢＤＥ、ＡＢＤＥ｝が得られる。
【００９９】
このように、本実施の形態の頻出パターンの発見では、属性空間を分割して、各計算ユニットに割り当てることが可能であり、各計算ユニットは、並列してレコード空間を探索することができるため、処理を高速化することができる。また、候補アイテム集合の長さを各計算ユニットで同期する必要があるが、計算ユニット間で通信する必要があるのは長さだけであるため、通信量は少なくてすむ。
【０１００】
［第３の実施の形態］
図１３は、本発明に係る頻出パターン発見装置の第３の実施の形態における頻出パターンを発見する対象となるデータの例である。
【０１０１】
本実施の形態では、対象となる系列データから、最小サポートカウント以上のサポートカウントを持つ全ての系列パターンを発見する。
【０１０２】
系列データとは、系列レコードの集合である。系列レコードとは、アイテムを順番に並べた集合である。また、系列パターンとは、ある系列レコードに属するアイテムをその系列レコードでの順番に従って並べた集合である。
【０１０３】
つまり、系列データとは、アイテム（属性）の集合であるレコード（トランザクション）の集合の一種であり、レコードを構成する属性の並びの順番も考慮する。系列レコードとは、時系列で得られるデータのように属性が順番に並んだレコードであり、同じ属性を持つ系列レコードであっても、各属性の順番が異なれば、異なる系列レコードとして取り扱う。系列レコードは、系列ＩＤで特定される。たとえば、図１３における系列ＩＤが１の「ＡＣＤＢＥ」という系列と、系列ＩＤが２の「ＡＤＣＢＥ」という系列は、同じ属性で構成される２つの系列であるが、属性の順番が異なっているため、異なる系列として取り扱う。
【０１０４】
また、系列パターンとは、系列における並びの順番を保ったまま、系列から属性を抜き出したものである。たとえば、図１３における系列ＩＤが１の系列と系列ＩＤが２の系列には、いずれも「ＡＢＥ」、「ＡＣＢＥ」、「ＡＤＢＥ」などの系列パターンが含まれている。系列パターンのうち、最小サポートカウント以上のサポートカウントを持つ全てのパターンを頻出系列パターンと呼ぶ。
【０１０５】
図１２は、本実施の形態における頻出パターン発見装置のブロック図である。
【０１０６】
この頻出パターン発見装置３は、第１の実施の形態の頻出パターン発見装置１（図１参照）の候補アイテム集合生成部２２に代えて候補系列パターン生成部５５を設け、候補生成条件判定部５１および候補レコード集合記憶部５４を追加したものである。候補生成条件判定部５１は、部分集合生成部５２および部分集合検索部５３を有している。
【０１０７】
候補レコード集合生成部２１は、対象系列データに含まれる１以上の系列を要素とする候補レコード集合を生成する。生成された候補レコード集合は、候補生成条件判定部５１の部分集合生成部５２に伝達される。
【０１０８】
部分集合生成部５２は、候補レコード集合生成部２１が生成した候補レコード集合から、その候補レコード集合よりも長さが１短い部分集合を生成する。部分集合検索部５３は、その部分集合が候補レコード集合記憶部５４に記憶されているか否かを検索し、少なくとも一つの部分集合が候補レコード集合記憶部５４に記憶されていない場合には、その部分集合に対応する候補レコード集合を除去する。
【０１０９】
候補系列パターン生成部５５は、候補レコード集合に含まれる各系列に共通して存在する系列パターンのうち最長のもの（最長共通部分系列）を抽出して、その候補レコード集合に対応する候補系列パターンを生成する。最長共通部分系列が２以上ある場合には、全ての組み合わせについて求める。パターン長計算部２３は、候補系列パターンのパターン長を計算する。最長共通部分系列の計算には、たとえば非特許文献３に開示されている方法を用いる。
【０１１０】
パターン除去部１３は、候補レコード集合のうち、その候補レコード集合に対応する候補系列パターンのパターン長が最小パターン長未満の候補レコード集合を除去する。また、除去されなかった候補レコード集合を候補レコード集合記憶部５４に記憶させる。候補レコード集合記憶部５４のデータ構造には、たとえばハッシュ木やトライが利用できる。また、他のデータ構造であってもよい。
【０１１１】
頻出パターン生成部１４は、対応する候補レコード集合に含まれる系列レコードの数が最小サポートカウント以上の候補系列パターンから、最小パターン長以上の部分集合を全て抽出して頻出系列パターンとする。
【０１１２】
抽出された頻出系列パターンは、頻出パターン生成部１４から頻出パターン記憶部１５に伝達される。また、頻出パターン記憶部１５は、頻出系列パターンを出力手段１７に伝達する。出力手段１７は、たとえばディスプレイに頻出系列パターンを表示したり、別の計算機に頻出系列パターンを送信する。
【０１１３】
次に、本実施の形態における頻出パターン発見方法を説明する。
【０１１４】
図１４は、本発明に係る頻出パターン発見方法の第３の実施の形態における流れ図である。
【０１１５】
まず、対象データを入力手段１６から入力して対象データ記憶部１１に記憶する（工程Ｓ１）。また、繰り返しの回数ｋを１に設定する。
【０１１６】
次に、候補レコード集合生成部２１は、長さがｋの候補レコード集合を生成する（工程Ｓ２）。１回目の繰り返し（パス）の場合には、長さ１の候補レコード集合を生成する。ｋ回目のパスにおいては、候補レコード集合生成部２１は、レコード長がｋ−１の候補レコード集合からレコード長がｋの候補レコード集合を生成する。
【０１１７】
次に、部分集合生成部５２は、候補レコード集合のそれぞれに対して、その候補レコード集合よりもレコード長が１短い部分集合を生成する（工程Ｓ２１）。部分集合検索部５３は、その部分集合が候補レコード集合記憶部５４に記憶されているかを検索し、少なくとも一つの部分集合が候補レコード集合記憶部５４に記憶されていない場合には、その部分集合に対応する候補レコード集合を除去する（工程Ｓ２２）。
【０１１８】
次に、候補レコード集合生成部２１は、長さｋの候補レコード集合が存在するか否かを判定する（工程Ｓ３）。長さｋの候補レコード集合が存在していれば、工程Ｓ４１、工程Ｓ５、工程Ｓ６および工程Ｓ６１が実行され、存在しなければ工程Ｓ７および工程Ｓ８が実行される。このようにして、長さｋの候補レコード集合が空集合になるまで、ｋを１ずつ増加させながら、工程Ｓ３、工程Ｓ４１、工程Ｓ５、工程Ｓ６および工程Ｓ６１が繰り返される。
【０１１９】
工程Ｓ４では、候補系列パターン生成部５５が、長さｋの候補レコード集合に含まれる全てのレコードに共通存在する系列パターンのうち最長のものを抽出して、候補系列パターンを生成する。
【０１２０】
工程Ｓ５では、パターン長計算部２３が、長さｋの各候補レコード集合に対応するそれぞれの候補系列パターンのパターン長を計算する。
【０１２１】
工程Ｓ６では、パターン除去部１３が、長さが最小パターン長未満である系列パターンに対応する候補レコード集合を削除する。
【０１２２】
工程Ｓ６１では、パターン除去部１３は、残った候補レコード集合を候補レコード集合記憶部に記憶する。
【０１２３】
工程Ｓ７では、頻出パターン生成部１４が、パターン除去部１３によって除去されなかった全ての候補レコード集合のうち、最小サポートカウント未満のレコード長の候補レコード集合を除去する。
【０１２４】
工程Ｓ８では、頻出パターン生成部１４が、残った全ての候補レコード集合に対応する候補系列パターンの、長さが最小パターン長以上の部分集合を全て抽出する。ここで抽出された集合が頻出系列パターンとなる。
【０１２５】
次に、図１３で示した対象データから、最小パターン長を４、最小サポートカウントを３とした場合の、本実施の形態における頻出パターン発見の流れを説明する。
【０１２６】
図１５は、本発明に係る頻出パターン発見方法の第３の実施の形態におけるデータの木構造の例を示す図である。
【０１２７】
図１３で示した対象データを対象データ記憶部１１に記憶した（工程Ｓ１）後、第１回目のパス（ｋ＝１）においては、長さ１の候補レコード集合である１，２，３，４，５の５つの集合が生成される（工程Ｓ２）。
【０１２８】
次に、部分集合生成部５２は、候補レコード集合のそれぞれに対して、その候補レコード集合よりもレコード長が１短い部分集合を生成し（工程Ｓ２１）、その部分集合が候補レコード集合記憶部５４に記憶されているかを検索する（工程Ｓ２２）。第１回目のパスでは、この部分集合は空集合となり、また、候補レコード集合記憶部５４には何も記憶されていないため、候補レコード集合は除去しないものとする。
【０１２９】
長さ１の候補レコード集合が存在するため（工程Ｓ３）、次に、それぞれの候補レコード集合に含まれる候補系列パターンが計算される（工程Ｓ４）。第１回目のパスでは、候補系列パターンは、対象データに含まれるすべての系列レコードＡＣＤＢＥ，ＡＤＣＢＥ，ＥＢＤＣ，ＣＤＡＢＥ，ＡＣＤＢＥとなる。
【０１３０】
また、それぞれの候補アイテム集合のパターン長が計算される（工程Ｓ５）。なお、ここでは、最小パターン長（３）に満たない候補レコード集合は存在しないため、工程Ｓ６で除去される候補レコード集合はない。また、工程Ｓ６１で、１，２，３，４，５という５つの候補レコード集合が候補レコード集合記憶部５４に記憶される。
【０１３１】
第２回目のパス（ｋ＝２）においては、長さ１の候補レコード集合から長さ２の候補レコード集合が生成される（工程Ｓ２）。たとえば、１と２という２つの候補レコード集合は、式（１）の関係を満たしているため、式（２）により、１２という候補レコード集合を生成する。同様に他の長さ１の候補レコード集合も組み合わせることにより、それぞれ長さ２の候補レコード集合である１２，１３，１４，１５，・・・，４５という１０個の集合が生成される。
【０１３２】
次に、部分集合生成部５２は、候補レコード集合のそれぞれに対して、その候補レコード集合よりもレコード長が１短い部分集合を生成する（工程Ｓ２１）。この部分集合は、たとえば１２という候補レコード集合に対しては、１，２という２つの集合となる。１および２という部分集合は、いずれも候補レコード集合記憶部５４に記憶されているため、１２という候補レコード集合は除去されない。残りの９個の候補レコード集合も同様に除去されないため、１０個の候補レコード集合が残る。
【０１３３】
長さ２の候補レコード集合が存在するため（工程Ｓ３）、次に候補系列パターンを計算する（工程Ｓ４）。たとえば、１という候補レコード集合の系列パターンがＡＣＤＢＥ、２という候補レコード集合の系列パターンがＡＤＣＢＥである。したがって、１２という候補レコード集合に対応する最長共通部分系列は、ＡＤＢＥおよびＡＣＢＥとなる。
【０１３４】
次に、長さ２の候補レコード集合に対して候補系列パターンの長さを計算する（工程Ｓ５）。たとえば１２という候補レコード集合に対応する候補系列パターンはＡＤＢＥおよびＡＣＢＥであり、その長さは４である。
【０１３５】
全ての候補レコード集合に対して候補系列パターンの長さを計算した後、最小パターン長（４）に満たない候補レコード集合を除去する（工程Ｓ６）。ここでは、候補系列パターンの長さが４未満の、１３、２３、２４、３４、３５という候補レコード集合が除去される。したがって、長さが２の候補レコード集合のうち、１２、１４、１５、２５、４５という５つの候補レコード集合が残る。これらの候補レコード集合は、候補レコード集合記憶部５４に記憶される（工程Ｓ６１）。
【０１３６】
第３回目のパス（ｋ＝３）においては、長さ２の候補レコード集合から長さ３の候補レコード集合が生成される（工程Ｓ２）。たとえば、１２と１４という２つの候補レコード集合は、式（１）の関係を満たしているため、式（２）により、１２４という候補レコード集合を生成する。同様に他の長さ１の候補レコード集合も組み合わせることにより、それぞれ長さ３の候補レコード集合である１２４，１２５，１４５という３個の集合が生成される。
【０１３７】
次に、部分集合生成部５２は、候補レコード集合のそれぞれに対して、その候補レコード集合よりもレコード長が１短い部分集合を生成する（工程Ｓ２１）。この部分集合は、たとえば１２４という候補レコード集合に対しては、１２，２４という２つの集合となる。１２および２４という部分集合のうち、２４という部分集合は候補レコード集合記憶部５４に記憶されていない、１２４という候補レコード集合は除去される。結果として、１２５，１４５の２つの候補レコード集合が残る。
【０１３８】
長さ３の候補レコード集合が存在するため（工程Ｓ３）、次に候補系列パターンを計算する（工程Ｓ４）。たとえば、１２という候補レコード集合に共通して存在する系列パターンがＡＤＢＥおよびＡＣＢＥ、２５という候補レコード集合の系列パターンがＡＤＢＥおよびＡＣＢＥである。したがって、１２５という候補レコード集合に対応する最長共通部分系列は、ＡＤＢＥおよびＡＣＢＥとなる。
【０１３９】
次に、長さ２の候補レコード集合に対して候補系列パターンの長さを計算する（工程Ｓ５）。たとえば１２という候補レコード集合に対応する候補系列パターンはＡＤＢＥおよびＡＣＢＥであり、その長さは４である。
【０１４０】
全ての候補レコード集合に対して候補系列パターンの長さを計算した後、最小パターン長（４）に満たない候補レコード集合を除去する（工程Ｓ６）。ここでは、候補系列パターンの長さが４未満の候補レコード集合はなく、１２５、１４５という２つの候補レコード集合が残る。これらの候補レコード集合は、候補レコード集合記憶部５４に記憶される（工程Ｓ６１）。
【０１４１】
第４回目のパス（ｋ＝４）においては、長さ３の候補レコード集合から長さ４の候補レコード集合が生成される（工程Ｓ２）。この例では、生成される候補レコード集合が存在しない。このため、工程Ｓ７および工程Ｓ８を実行する。
【０１４２】
ここでは、最小サポートカウントを４としているので、レコード長が４未満の候補レコード集合は除去される（工程Ｓ７）。残った候補レコード集合は、１２５、１４５の２つとなる。
【０１４３】
これらの候補レコード集合に対応する最長共通部分系列は、ＡＤＢＥ、ＡＣＢＥ、ＣＤＢＥとなり、これらの候補系列パターンの集合がＦ’である。これらの候補系列パターンの最小パターン長以上の部分集合を全て抽出することにより、頻出系列パターンの集合Ｆとして、Ｆ＝｛ＡＤＢＥ、ＡＣＢＥ、ＣＤＢＥ｝が得られる。
【０１４４】
このように、本実施の形態における頻出系列パターンの発見では、属性空間の探索ではなく、レコード空間の探索を行う。このため、属性数が多くなっても、属性の組み合わせの爆発的な増加が生じることがない。したがって、属性数が大きいデータから頻出系列パターンを効率的に発見することができる。
【０１４５】
また、候補レコード集合集合の部分集合の最長共通部分系列の長さよりも、その候補レコード集合の最長共通部分系列の長さが長くなることはない。そこで、部分集合が前回のパスで候補レコード集合記憶部に記憶されていない、すなわち、その部分集合の最長共通部分系列の長さが最小パターン長に満たない場合には、候補生成条件判定部において、その部分集合に対応する候補レコード集合を除去している。これにより、不要な演算を抑制し、頻出系列パターンを効率的に発見することができる。
【０１４６】
［その他の実施の形態］
なお、以上の説明は単なる例示であり、本発明は上述の各実施の形態に限定されず、様々な形態で実施することができる。また、各実施の形態の特徴を組み合わせて実施することもできる。たとえば、頻出パターン発見装置は、単一の計算機上に実現することもできるし、複数の計算機を組み合わせて実現することもできる。また、各計算ユニットは分散メモリ型並列計算機を用いることとしたが、共有メモリ型並列計算機、分散共有メモリ型並列計算機など、並列計算が可能な他のアーキテクチャのものでもよい。
【図面の簡単な説明】
【０１４７】
【図１】本発明に係る頻出パターン発見装置の第１の実施の形態におけるブロック図である。
【図２】頻出パターンを発見する対象となるデータの例である。
【図３】頻出パターンを発見する対象となるデータの例である。
【図４】本発明に係る頻出パターン発見方法の第１の実施の形態における流れ図である。
【図５】本発明に係る頻出パターン発見方法の第１の実施の形態におけるデータの木構造の例を示す図である。
【図６】本発明に係る頻出パターン発見装置の第２の実施の形態におけるブロック図である。
【図７】本発明に係る頻出パターン発見装置の第２の実施の形態における計算ユニットのブロック図である。
【図８】本発明に係る頻出パターン発見方法の第２の実施の形態における流れ図である。
【図９】本発明に係る頻出パターン発見方法の第２の実施の形態における対象データの分割方法の例を示す図である。
【図１０】本発明に係る頻出パターン発見方法の第２の実施の形態における分割データの木構造の例を示す図である。
【図１１】本発明に係る頻出パターン発見方法の第２の実施の形態における分割データの木構造の例を示す図である。
【図１２】本発明に係る頻出パターン発見装置の第３の実施の形態におけるブロック図である。
【図１３】頻出パターンを発見する対象となるデータの例である。
【図１４】本発明に係る頻出パターン発見方法の第３の実施の形態における流れ図である。
【図１５】本発明に係る頻出パターン発見方法の第３の実施の形態におけるデータの木構造の例を示す図である。
【符号の説明】
【０１４８】
１１…対象データ記憶部、１２…候補パターン生成部、１３…パターン除去部、１４…頻出パターン生成部、１５…頻出パターン記憶部、１６…入力手段、１７…出力手段、２１…候補レコード集合生成部、２２…候補アイテム集合生成部、２３…パターン長計算部、３１…属性分割部、３２…データ配置部、３３…分割データ記憶部、３４…分割候補生成部、３５…パターン長同期部、３６…計算ユニット、３７…頻出パターン結合生成部、４１…候補レコード集合生成部、４２…分割候補アイテム集合生成部、４３…分割パターン長計算部、５１…候補生成条件判定部、５２…部分集合生成部、５３…部分集合検索部、５４…候補レコード集合記憶部、５５…候補系列パターン生成部
【図１】
2008159015.tif 000003
【図２】
2008159015.tif 000004
【図３】
2008159015.tif 000005
【図４】
2008159015.tif 000006
【図５】
2008159015.tif 000007
【図６】
2008159015.tif 000008
【図７】
2008159015.tif 000009
【図８】
2008159015.tif 000010
【図９】
2008159015.tif 000011
【図１０】
2008159015.tif 000012
【図１１】
2008159015.tif 000013
【図１２】
2008159015.tif 000014
【図１３】
2008159015.tif 000015
【図１４】
2008159015.tif 000016
【図１５】
2008159015.tif 000017