JP5668651B2 - 情報処理装置、プログラム、および要素抽出方法 - Google Patents

Description

本発明は、要素の集合を抽出する情報処理装置、プログラム、および要素抽出方法に関する。

情報通信技術（ＩＣＴ：Information and Communication Technology）の利用範囲の広がりに伴い、様々な情報の収集が可能となっている。収集した情報に対して例えばデータマイニングを行うことで、有用な知識を取り出すことができる。

ＩＣＴ技術で収集できる情報の一例として、各種商品などのトランザクション（取り引き）に関する情報（トランザクションデータ）がある。例えば、ＰＯＳ（Point Of Sales）システムを介して、顧客が一回の買い物で購入した品目をアイテムとして含むトランザクションデータを取得できる。この場合、トランザクションデータは、店舗で取り扱っている全品目の部分集合を示すデータセットである。

このようなトランザクションデータが与えられたときに、互いに同じトランザクションデータに含まれる（共起する）ことの多いアイテムの集合を、知識として抽出する場合がある。この場合、アイテムの集合が互いに同じトランザクションデータに含まれるというだけでなく、他の様々な情報を加味し、所定の抽出条件を満たすアイテム集合を抽出することができる。

各トランザクションが全アイテム集合の部分集合になっているデータセットから、所定の条件を満たすアイテム集合を抽出する場合、最も単純には、あらゆる組み合わせのアイテム集合に対して抽出条件を満たすかの確認処理が行われる。そして、抽出条件を満たすアイテム集合が抽出される。ただしこの方法は、アイテム数が多くなるとアイテムの組み合わせ数が爆発し、計算量が膨大になる。

そこで、アイテム集合の抽出条件に応じ、アイテム集合を抽出する際の処理を効率化する様々な技術が考えられている。例えば記号アイテムおよび数値アイテムを含む多数のトランザクションを探索対象として、事象共起関係の数値定量的解析を簡易かつ高精度に行える記号および数値バスケット分析方法が提案されている。また、処理の効率化技術として、グラフ操作の効率的なアルゴリズムも開示されている。

国際公開第２００６／０５７１０５号

J. Hopcroft, R. Tarjan, "Efficient algorithms for graph manipulation" Communications of the ACM Volume 16 Issue 6, June 1973, p.372-378

しかし、アイテムの共通性によって集められたトランザクションのうちの、いずれかのトランザクションに同時に含まれることの多いアイテムの集合を抽出する処理について、処理を効率化するための有効な技術はなかった。アイテムの共通性によって集められたトランザクションのうちの、いずれかのトランザクションに同時に含まれることの多いアイテムの集合は、以下のような知識の習得に利用できる。

例えば、食堂において顧客が注文した品目をアイテムとするトランザクションに基づいて、アイテムの共通性によってトランザクションを集める。そして集めたトランザクションのうちの、いずれかのトランザクションに同時に含まれることの多いアイテムの集合を抽出できる。このようにして抽出されたアイテムの集合で示される品目を掲載したメニューを作成することで、好みが似た多くの顧客が同時に注文する品目を網羅したメニューを作成できる。作成されたメニューは、好みが似た、多くの顧客にとって使いやすいメニューとなる。

なお、アイテムの共通性によって集められたトランザクションのうちの、いずれかのトランザクションに同時に含まれることの多いアイテムの集合により得られる知識は、上記のような食堂のメニューに掲載する品目に関する知識の習得に限られない。例えば、商品の小売店において、１つの商品棚に纏めて置くのに適した商品の知識の習得にも利用可能である。また、このようなデータマイニングによる知識習得処理の効率化は、トランザクションに基づく知識の習得に限らず、各種情報を要素とする集合に基づく知識習得一般に有用な技術である。

１つの側面では、本発明は、要素の共通性によって関連付けられた複数の集合のいずれかに、同時に含まれることの多い要素の集合を効率的に抽出する情報処理装置、プログラム、および要素抽出方法を提供することを目的とする。

１つの案では、第１の削除手段、グループ生成手段、第２の削除手段、および出力手段を有する情報処理装置が提供される。
第１の削除手段は、記憶手段に格納された、少なくとも１つの要素を含む複数の集合に対して、包含数閾値未満の要素しか含まない集合の削除と、出現数閾値未満の集合にしか含まれない要素の削除とを行う。グループ生成手段は、集合と要素との削除後に記憶手段内に残存する集合のうち、要素の共通性によって関連付けられた集合が属するグループを生成する。第２の削除手段は、生成されたグループごとに、記憶手段内の該グループに属する集合に対して、包含数閾値未満の要素しか含まない集合の削除と、該グループに属する集合のうち出現数閾値未満の集合にしか含まれない要素の削除とを行う。出力手段は、集合と要素との削除後にグループに残存する集合に含まれる要素のリストを出力する。

１態様によれば、要素の共通性によって関連付けられた複数の集合のいずれかに、同時に含まれることの多い複数の要素を効率的に抽出することができる。

第１の実施の形態に係る装置の機能構成例を示す図である。 第１の実施の形態における要素のリスト出力処理の手順の一例を示すフローチャートである。 第１の実施の形態による要素の抽出例を示す図である。 第２の実施の形態で想定するアイテム抽出例を示す図である。 利用しやすいメニューの条件に沿った品目集合の抽出例を示す図である。 第２の実施の形態のシステム構成例を示す図である。 第２の実施の形態に用いるサーバのハードウェアの一構成例を示す図である。 サーバの機能を示すブロック図である。 トランザクション記憶部のデータ構造の一例を示す図である。 グループ情報記憶部のデータ構造の一例を示す図である。 アイテム集合抽出処理の手順の一例を示すフローチャートである。 アイテム集合抽出処理の一例を示す図である。 最大アイテム集合抽出処理の手順の一例を示すフローチャートである。 最大アイテム集合抽出処理の一例を示す図である。 トランザクション集合分割処理の手順を示すフローチャートである。 トランザクション集合分割処理の一例を示す図である。 トランザクション集合が複数回分割される例を示す図である。

以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
第１の実施の形態では、要素の共通性によって関連付けられた複数の集合のいずれかに、同時に含まれることの多い要素の集合の抽出条件を以下のように定義する。

［第１の要素抽出条件］
抽出される複数の要素それぞれは、その要素を含む出現数閾値以上の集合が、１つのグループに属する複数の集合内に存在し、そのグループに属する各集合は、抽出される複数の要素のうちの包含数閾値以上の要素を含む。

［第２の要素抽出条件］
抽出される複数の要素に対して第１の要素抽出条件を満たすグループに属する複数の集合は、抽出される複数の要素のうちの共有数閾値以上の要素を共有する集合同士を関連付けることによる関連性を有する集合の集まりである。

次に、上記第１・第２の要素抽出条件を満たす複数の要素を抽出するための機能について説明する。
図１は、第１の実施の形態に係る装置の機能構成例を示す図である。情報処理装置Ｃは、記憶手段１、第１の削除手段２、グループ生成手段３、第２の削除手段４、別グループ生成手段５および出力手段６を有する。

記憶手段１は、少なくとも１つの要素を含む複数の集合１ａ，１ｂ，１ｃを記憶する。
第１の削除手段２は、記憶手段１に対して、包含数閾値未満の要素しか含まない集合の削除と、出現数閾値未満の集合にしか含まれない要素の削除とを、削除する集合および要素が無くなるまで繰り返す。

グループ生成手段３は、集合と要素との削除後に記憶手段１内に残存する集合のうち、要素の共通性によって関連付けられた集合が属するグループを生成する。例えばグループ生成手段３は、削除する集合および要素が無くなった記憶手段１内に残存する集合のうち、共有数閾値以上の要素を共有する集合間を関連付け、関連付けられた集合間を辿ることで到達可能な複数の集合が属するグループを生成する。

第２の削除手段４は、生成されたグループごとに集合と要素との削除処理を行う。例えば第２の削除手段４は、記憶手段１内のグループに属する集合に対して、包含数閾値未満の要素しか含まない集合の削除と、該グループに属する集合のうち出現数閾値未満の集合にしか含まれない要素の削除とを行う。第２の削除手段４は、集合と要素との削除処理を、削除する集合および要素が無くなるまで繰り返す。

別グループ生成手段５は、集合と要素との削除が行われたグループごとに、そのグループに残存する集合を、要素の共通性によって関連付ける。そして、別グループ生成手段５は、関連付けられた複数の集合がそのグループに残存する集合の一部の場合、関連付けられた複数の集合が属する別のグループを生成する。例えば、別グループ生成手段５は、集合と要素との削除が行われたグループに残存する集合のうち、共有数閾値以上の要素を共有する集合間を関連付け、関連付けられた集合間を辿ることで到達可能な複数の集合を求める。そして別グループ生成手段５は、求められた複数の集合が、元のグループに属する集合の一部である場合、求められた複数の集合が属する別のグループを生成する。

出力手段６は、集合と要素との削除が行われたグループに残存する集合に含まれる要素のリストを出力する。例えば出力手段６は、集合と要素との削除が行われたグループから別のグループが作成できなかった場合、集合と要素との削除が行われたグループに属する集合に含まれる要素のリストを出力する。

なお、第１の削除手段２、グループ生成手段３、第２の削除手段４、別グループ生成手段５および出力手段６は、情報処理装置Ｃが有するＣＰＵ（Central Processing Unit）により実現することができる。また、記憶手段１は、情報処理装置Ｃが有するＲＡＭ（Random Access Memory）やハードディスクドライブ（ＨＤＤ:Hard Disk Drive）などにより実現することができる。

また、図１に示した各機能間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
図２は、第１の実施の形態における要素のリスト出力処理の手順の一例を示すフローチャートである。以下、図２に示す処理をステップ番号に沿って説明する。なお、以下の処理は、例えばユーザによる実行指示の入力に応じて開始される。

［ステップＳ１］第１の削除手段２は、記憶手段１内のすべての集合１ａ，１ｂ，１ｃ，・・・を処理対象として、所定の削除条件を満たす集合と要素とを削除する。例えば第１の削除手段２は、記憶手段１に対して、包含数閾値未満の要素しか含まない集合の削除と、出現数閾値未満の集合にしか含まれない要素の削除とを、削除する集合および要素が無くなるまで繰り返す。

［ステップＳ２］グループ生成手段３は、記憶手段１内に残存する集合に基づいて、複数の集合からなるグループを生成する。例えばグループ生成手段３は、削除する集合および要素が無くなった記憶手段１内に残存する集合のうち、共有数閾値以上の要素を共有する集合間を関連付け、関連付けられた集合間を辿ることで到達可能な複数の集合が属するグループを生成する。

［ステップＳ３］第２の削除手段４は、ステップＳ２で生成されたグループに属する集合を処理対象として、所定の削除条件を満たす集合と要素とを削除する。例えば第２の削除手段４は、記憶手段１内のグループに属する集合に対して、包含数閾値未満の要素しか含まない集合の削除と、そのグループに属する集合のうち出現数閾値未満の集合にしか含まれない要素の削除とを行う。第２の削除手段４は、集合と要素との削除処理を、削除する集合および要素が無くなるまで繰り返す。

［ステップＳ４］別グループ生成手段５は、削除する集合および要素が無くなったグループごとに、そのグループの一部を分離した別のグループを生成する。例えば別グループ生成手段５は、既存のグループに残存する集合のうち、共有数閾値以上の要素を共有する集合間を関連付け、関連付けられた集合間を辿ることで到達可能な複数の集合を求める。別グループ生成手段５は、求められた複数の集合が、元のグループに属する集合の一部である場合、求められた複数の集合が属する別のグループを生成する。

［ステップＳ５］出力手段６は、ステップＳ４の処理において別のグループが生成できたか否かを判断する。出力手段６は、別のグループが生成できたのであれば、処理をステップＳ３に進める。また出力手段６は、別のグループが生成できていないのであれば、処理をステップＳ６に進める。

［ステップＳ６］出力手段６は、生成済みのグループそれぞれから、そのグループに残存する集合のいずれかに含まれる要素のリストを出力する。
このようにして、上記第１・第２の条件を満たす複数の要素が抽出される。

図３は、第１の実施の形態による要素の抽出例を示す図である。図３では、第１の実施の形態による要素抽出過程を、記憶手段１内の集合の状態遷移で示している。なお、図３の例では、出現数閾値、包含数閾値、および共有数閾値がすべて「２」であるものとする。

第１の状態は、記憶手段１に格納された集合の初期状態である。図３では、記憶手段１に７個の集合ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｇが格納されている。各集合の識別子の右に、その集合に含まれる要素がアルファベットで示されている。記憶手段１に格納された複数の集合のうち、集合ｅは要素を１つしか含んでおらず、包含数閾値未満の要素しか含んでいないこととなる。そのため、集合ｅは、記憶手段１から削除される。また、集合ｅの削除後に残存する各集合に含まれる要素の出現数をカウントすると、要素「Ｅ」の出現数が「１」であり、出現数閾値未満である。そこで、集合ｄから、要素「Ｅ」が削除される。

要素「Ｅ」が削除されたことにより、集合ｄに含まれる要素数は「２」から「１」に減少する。すると集合ｄに含まれる要素数は、包含数閾値未満となり、記憶手段１から集合ｄが削除される。これ以上、集合および要素を削除できないため、集合と要素との最初の削除処理は終了する。

第２の状態は、集合と要素との最初の削除処理は終了後の状態である。記憶手段１内に残存する集合のうち、共有数閾値以上の要素を共有する集合が関連付けられる。すると、集合ａ，ｂ，ｃが互いに共有数閾値以上の要素を共有しており、関連付けられる。また集合ｆ，ｇが共有数閾値以上の要素を共有しており、関連付けられる。そこで集合ａ，ｂ，ｃが属するグループ６ａと、集合ｆ，ｇが属するグループ６ｂとが生成される。

第３の状態は、グループ生成後の状態を示す図である。生成されたグループ６ａ，６ｂそれぞれについて、包含数閾値未満の要素しか含んでいない集合と、同一グループ内の出現数閾値未満の集合にしか含まれない要素とが削除される。すると、要素「Ｆ」は、グループ別に出現数をカウントすると、グループ６ａ，６ｂのいずれにおいても１回しか出現しない。そこで、各グループ６ａ，６ｂから、要素「Ｆ」が削除される。

第４の状態は、集合と要素との２回目の削除処理は終了後の状態である。第４の状態で各グループ６ａ，６ｂ内に残存する集合に基づいて、グループ内での集合の関連付けが行われる。図３の例では、既に生成されているグループ６ａ，６ｂの集合が互いに関連付けられるだけであり、元のグループの一部を分離した別のグループは生成されない。そこで既に生成されているグループ６ａ，６ｂごとに、そのグループに残存する集合に含まれる要素のリスト７ａ，７ｂが出力される。

このようにして出力された要素のリスト７ａ，７ｂは、上記の第１・第２の要素抽出条件を満たす。従って要素のリスト７ａ，７ｂは、要素の共通性によって関連付けられた複数の集合のいずれかに、同時に含まれることの多い要素の集合である。

しかも第１の実施の形態に示した処理は、第１・第２の要素抽出条件を満たさない集合および要素の削除と、要素の共通性による集合のグループ分けとを交互に行うことで要素を効率的に絞り込んでいる。そのため、複数の要素のあらゆる組み合わせについて、上記の第１・第２の要素抽出条件を満たすかどうかを判断する場合に比べて、計算量が少なくて済む。その結果、要素数が大量になっても、要素の共通性によって関連付けられた複数の集合のいずれかに、同時に含まれることの多い要素の集合を効率的に抽出することが可能となる。

なお、出現数閾値、包含数閾値、および共有数閾値の設定内容によっては、１つのグループの一部の集合が属する別のグループを生成できないことが、予め分かっている場合もある。例えば出現数閾値、包含数閾値、および共有数閾値が、すべて「２」の場合、最初にグループ化したときに関連付けられた集合間で共有された要素は、２つ以上の集合に含まれるため、その後の削除処理で削除されることはない。また、グループに属する集合は、削除されることのない２つ以上の要素を含む。そのため、集合が削除されることもない。そのため、そのグループに対して要素の共有性に基づく集合間の関連付けを行うと、グループ内のすべての集合が関連付けられ、別のグループは生成されない。このように別のグループが生成されないことが自明な場合には、図２のステップＳ４、Ｓ５の処理を実行せずに、集合と削除とを行ったグループから要素のリストを出力することができる。

〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、ＰＯＳからトランザクションデータを収集し、顧客に提示するメニュー一覧に載せるのに適したアイテムの組み合わせに関する知識を取得するものである。なお、トランザクションデータに含まれるアイテムは、第１の実施の形態に示した要素の一例である。またトランザクションデータは、第１の実施の形態に示した、要素を含む集合の一例である。

図４は、第２の実施の形態で想定するアイテム抽出例を示す図である。図４の例では、飲食店のＰＯＳ端末装置は、各顧客が注文した品目を含むＰＯＳデータ２１を記憶する。なお、ＰＯＳデータ２１に含まれる、顧客ごとの注文した品目のリストが、トランザクションデータである。図４では、例えば「顧客１」が、「炒飯、餃子、青椒肉絲」を注文したことが記憶されている。このようなＰＯＳデータ２１が所定の調査期間分記憶されると、そのＰＯＳデータ２１に基づいてデータマイニングを行う。

データマイニングでは、同時に注文されることの多い、できるだけ大きな品目の集合を生成する。そして、飲食店の店員は、同時に注文されることの多い品目の集合を載せたメニュー２２を作成する。例えば、「炒飯」、「餃子」、「青椒肉絲」、および「麻婆豆腐」が同時に抽出されることが多い場合、これらの品目を同一ページに載せたメニュー２２が作成される。このように抽出された集合に含まれる品目を、メニューの同じページに掲載しておくことで、顧客は、注文したい品目を１つのページ内で見つけることができ、注文がしやすくなる。

第２の実施の形態では、利用しやすいメニューを、以下のように定義する。
・メニュー中どの品目に対しても、そのメニュー他の多くの品目と併せて注文した顧客が、過去に多数存在すること。
・メニュー中の多くの品目を併せて注文した顧客の集まり（顧客群）は、好みが似た（メニューから多くのメニューを共通に注文した）顧客の集まりであること。

具体的には、以下の条件を満たすメニューを作成するものとする。なお、予め閾値ｋ，ｍ，ｎが設定されているものとする。ここでｋは２以上の整数、ｍは１以上の整数、ｎは１以上のｋ以下の整数である。

［条件１］メニューに含まれる各品目は、メニューに含まれる品目のうちｋ品以上の品目を注文した顧客群のなかのｍ人以上の顧客によって注文されていること。この条件をトランザクションデータに当てはめると、抽出されるアイテム集合中のどのアイテムも、アイテム集合中のｋ個以上のアイテムを含むようなｍ個以上のトランザクションに含まれることである。

［条件２」メニューからｋ品以上の品目を注文した顧客群に属する各顧客は、その顧客群に属する他の顧客との間で、メニュー内のｎ品以上の品目を共通に注文しているという関連付けによって結び付けられていること。この条件をトランザクションデータに当てはめると、アイテム集合中のｋ個以上のアイテムを含むようなトランザクションの集合は、アイテム集合中のｎ個以上のアイテムを共有することで関連付けられたトランザクションの集まりであることである。

図５は、利用しやすいメニューの条件に沿った品目集合の抽出例を示す図である。図５では、ＰＯＳデータ２１をグラフィカルに示している。図５に示したＰＯＳデータ２１では、顧客と、その顧客が注文した品目とを線で接続している。また、上記［条件１］、［条件２］における閾値ｋ，ｍ，ｎの値は、それぞれｋ＝２、ｍ＝２、ｎ＝２とする。

図５の例において、２つのアイテム集合ＭＡ，ＭＢについて、上記［条件１］、［条件２］を満たすか否かを検討する。
・アイテム集合ＭＡ
アイテム集合ＭＡには、顧客が注文した品目を示すアイテムとして「炒飯」、「餃子」、「青椒肉絲」、および「麻婆豆腐」が含まれている。

まずアイテム集合ＭＡに関して、［条件１］の適合の有無を検討する。アイテム集合ＭＡに含まれる品目のいずれかを注文した顧客は、「顧客１」、「顧客２」、「顧客３」、「顧客４」である。ここで「顧客１」、「顧客２」、「顧客３」は、アイテム集合ＭＡから３品の品目を注文している。一方「顧客４」は、アイテム集合ＭＡから１品の品目を注文している。すると、アイテム集合ＭＡに含まれる品目のうちｋ（＝２）品以上の注文をした顧客は、「顧客１」、「顧客２」、「顧客３」である。そこで「顧客１」、「顧客２」、「顧客３」を含む顧客群Ａが形成される。

アイテム集合の各品目のうち「炒飯」は、顧客群Ａに属する３人の顧客から注文されている。「餃子」、「青椒肉絲」、「麻婆豆腐」は、顧客群Ａに属する２人の顧客から注文されている。すると、いずれの品目もｍ（＝２）人以上の顧客によって注文されている。

以上により、アイテム集合ＭＡは［条件１］を満たしている。
次に、アイテム集合ＭＡに関して、［条件２］の適合の有無を検討する。顧客群Ａに属する「顧客１」は、顧客群Ａに属する他の「顧客２」との間で、アイテム集合ＭＡ内の「炒飯」、「餃子」を共通で注文している。顧客群Ａに属する「顧客２」は、顧客群Ａに属する他の「顧客３」との間で、アイテム集合ＭＡ内の「炒飯」、「麻婆豆腐」を共通で注文している。顧客群Ａに属する「顧客３」は、顧客群Ａに属する他の「顧客１」との間で、アイテム集合ＭＡ内の「炒飯」、「青椒肉絲」を共通で注文している。そうすると、顧客群Ａに属するいずれの顧客も、その顧客群に属する他の顧客との間で、アイテム集合ＭＡ内のｎ（＝２）品以上の品目を共通に注文している。従って［条件２］も満たされる。

その結果、アイテム集合ＭＡに含まれる品目を掲載したメニューは、利用しやすいメニューの条件を満たしていることとなる。例えばアイテム集合ＭＡに示される品目「炒飯」、「餃子」、「青椒肉絲」、および「麻婆豆腐」を載せたメニューは、「顧客１」、「顧客２」、「顧客３」と好みが似た多数の顧客にとって使いやすいメニューである。
・アイテム集合ＭＢ
アイテム集合ＭＢには、顧客が注文した品目を示すアイテムとして「ラーメン」、「蟹玉」、および「チャーシュー」が含まれている。

まずアイテム集合ＭＢに関して、［条件１］の適合の有無を検討する。アイテム集合ＭＢに含まれる品目のいずれかを注文した顧客は、「顧客６」、「顧客７」である。ここで「顧客６」、「顧客７」は、アイテム集合ＭＢから３品の品目を注文している。すると、アイテム集合ＭＢに含まれる品目のうちｋ（＝２）品以上の注文をした顧客は、「顧客６」、「顧客７」である。そこで「顧客６」、「顧客７」を含む顧客群Ｂが形成される。

アイテム集合の各品目のうち「ラーメン」、「蟹玉」、「チャーシュー」は、それぞれ顧客群Ｂに属する２人の顧客から注文されている。すると、いずれの品目もｍ（＝２）人以上の顧客によって注文されている。

以上により、アイテム集合ＭＢは［条件１］を満たしている。
次に、アイテム集合ＭＢに関して、［条件２］の適合の有無を検討する。顧客群Ｂに属する「顧客６」は、顧客群Ｂに属する他の「顧客７」との間で、アイテム集合ＭＢ内の「ラーメン」、「蟹玉」、「チャーシュー」を共通で注文している。そうすると、顧客群Ｂに属するいずれの顧客も、その顧客群に属する他の顧客との間で、アイテム集合ＭＢ内のｎ（＝２）品以上の品目を共通に注文している。従って［条件２］も満たされる。

その結果、アイテム集合ＭＢに含まれる品目を掲載したメニューは、利用しやすいメニューの条件を満たしていることとなる。
第２の実施の形態では、このような利用しやすいメニューに載せる品目の決定に利用可能なアイテム抽出処理を、効率的に行うことができる。例えばアイテム集合ＭＢに示される品目「ラーメン」、「蟹玉」、および「チャーシュー」を載せたメニューは、「顧客６」、「顧客７」と好みが似た多数の顧客にとって使いやすいメニューである。

このように、［条件１］と［条件２］とを満たすアイテム集合を抽出することで、有用なメニューが作成できる。このようなアイテム集合の条件を論理式で表すと、以下のようになる。すなわち、以下の条件を満たすアイテムの組み合わせＸを抽出することとなる。
∃Ｙ⊆Ｙ₀
（（∀ｙ∈Ｙ） ｆ（ｙ，Ｘ）≧ｋ） ∧
（（∀ｘ∈Ｘ） ｇ（ｘ，Ｙ）≧ｍ） ∧
（（∀｛ｙ_i，ｙ_j｝⊆Ｙ） ｒ（ｙ_i，ｙ_j，Ｘ，Ｙ，ｎ）＜∞）
・・・（１）
ここでＹ₀は、全トランザクション集合である。Ｙは、Ｙ₀の部分集合である。「∃Ｙ⊆Ｙ₀」で、Ｙ₀の任意の部分集合Ｙが定義されている。「∧」は、論理積を示す記号である。

「（∀ｙ∈Ｙ）」により、すべてのトランザクションｙが部分集合Ｙに属することが示されている。「ｆ（ｙ，Ｘ）」は、アイテムの組み合わせＸに含まれるアイテムのうち、トランザクションｙに含まれる個数である。

「（∀ｘ∈Ｘ）」により、すべてのアイテムｘが、アイテムの組み合わせＸに属することが示されている。「ｇ（ｘ，Ｙ）」は、Ｙに含まれるトランザクションのうち、アイテムｘを含む個数である。

ｙ_iは、ｉ番目（ｉは１以上の整数）のトランザクションｙを示す。ｙ_jは、ｊ番目（ｊは１以上の整数）のトランザクションｙを示す。「（∀｛ｙ_i，ｙ_j｝⊆Ｙ）」により、トランザクションｙ_iとトランザクションｙ_jと組み合わせのすべてが、トランザクションの部分集合Ｙの部分集合となることを示している。「ｒ（ｙ_i，ｙ_j，Ｘ，Ｙ，ｎ）」は、アイテムの組み合わせＸに含まれるアイテムをｎ個以上共有するトランザクションによって、部分集合Ｙに含まれるトランザクションをｙ_iからｙ_jまで辿ったときの最短パスの経路長である。例えば、ｙ_iとｙ_jとが、アイテムの組み合わせＸに含まれるアイテムをｎ個以上共有していれば、ｒ（ｙ_i，ｙ_j，Ｘ，Ｙ，ｎ）＝１となる。アイテムの組み合わせＸに含まれるアイテムをｎ個以上共有するトランザクションによって、部分集合Ｙに含まれるトランザクションをｙ_iからｙ_jまで辿るパスが存在しないときは、ｒ（ｙ_i，ｙ_j，Ｘ，Ｙ，ｎ）＝∞とする。従って、該当するパスが存在すれば、「ｒ（ｙ_i，ｙ_j，Ｘ，Ｙ，ｎ）＜∞」の条件は満たされる。

次に、このような論理式を満たすようなアイテム集合を抽出するシステムの構成について説明する。
図６は、第２の実施の形態のシステム構成例を示す図である。サーバ１００には、ネットワーク１０を介して複数のＰＯＳ端末装置３１〜３３が接続されている。ＰＯＳ端末装置３１〜３３は、それぞれ例えば同系列の飲食店に設置されている。ＰＯＳ端末装置３１〜３３は、顧客が注文した品目のリストを、トランザクションデータとして記憶する。そしてＰＯＳ端末装置３１〜３３は、記憶したトランザクションデータを、サーバ１００に送信する。

サーバ１００は、ＰＯＳ端末装置３１〜３３から収集したトランザクションデータに基づいて、データマイニングを行う。
図７は、第２の実施の形態に用いるサーバのハードウェアの一構成例を示す図である。サーバ１００は、ＣＰＵ１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０８を介してＲＡＭ１０２と複数の周辺機器が接続されている。

ＲＡＭ１０２は、サーバ１００の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。

バス１０８に接続されている周辺機器としては、ＨＤＤ１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１０７がある。

ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、サーバ１００の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。

グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。モニタ１１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。

入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。

光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク１４に記録されたデータの読み取りを行う。光ディスク１４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク１４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。

通信インタフェース１０７は、ネットワーク１０に接続されている。通信インタフェース１０７は、ネットワーク１０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。

以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。なお、第１の実施の形態に示した情報処理装置Ｃも、図３に示したコンピュータと同様のハードウェアにより実現することができる。

図８は、サーバの機能を示すブロック図である。サーバ１００は、収集部１１０、トランザクション記憶部１２０、アイテム集合抽出部１３０、トランザクション集合分割部１４０、グループ情報記憶部１５０、および出力部１６０を有する。

収集部１１０は、ＰＯＳ端末装置３１〜３３から、トランザクションデータを収集する。収集部１１０は、収集したとトランザクションデータをトランザクション記憶部１２０に格納する。

トランザクション記憶部１２０は、トランザクションデータを記憶する。なおトランザクション記憶部１２０に格納されたトランザクションデータは、アイテム集合抽出部１３０によって更新される。例えば、トランザクションデータの削除や、アイテムの削除が行われる。例えばＲＡＭ１０２またはＨＤＤ１０３の記憶領域の一部が、トランザクション記憶部１２０として使用される。

アイテム集合抽出部１３０は、トランザクション記憶部１２０に格納されたトランザクションデータに基づいて、上記の［条件１」を満たすメニューに含まれる品目を示すアイテム集合を抽出する。アイテム集合抽出部１３０は、アイテム集合の抽出過程で、トランザクション記憶部１２０内のトランザクションデータの更新を行う。なおアイテム集合抽出部１３０は、グループ情報記憶部１５０にトランザクションのグループが設定されている場合、同一グループのトランザクションに関するトランザクションデータに基づいて、アイテム集合の抽出処理を行う。

トランザクション集合分割部１４０は、アイテム集合抽出部１３０により抽出されたアイテムに基づいて、上記の［条件２］を満たす顧客のトランザクションデータ同士を同じグループに纏めるように、トランザクションを複数のグループに分類する。トランザクション集合分割部１４０は、分類の結果をグループ情報記憶部１５０に格納する。

グループ情報記憶部１５０は、トランザクションの各グループに属するトランザクションデータに関する情報を記憶する。例えばＲＡＭ１０２またはＨＤＤ１０３の記憶領域の一部が、グループ情報記憶部１５０として使用される。

出力部１６０は、トランザクション集合分割部１４０によって、これ以上細かく分類できないと判断された場合、トランザクション記憶部１２０とグループ情報記憶部１５０とを参照し、グループごとの最大アイテム集合を出力する。

なお、図８に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。また、トランザクション記憶部１２０は、図１に示した第１の実施の形態の記憶手段１の一例である。アイテム集合抽出部１３０は、図１に示した第１の実施の形態の第１の削除手段２と第２の削除手段４とを合わせた機能の一例である。トランザクション集合分割部１４０は、図１に示した第１の実施の形態のグループ生成手段３と別グループ生成手段５とを合わせた機能の一例である。出力部１６０は、図１に示した第１の実施の形態の出力手段６の一例である。

次に、図８に示す各記憶部のデータ構造例について説明する。
図９は、トランザクション記憶部のデータ構造の一例を示す図である。トランザクション記憶部１２０には、トランザクションテーブル１２１が格納されている。

トランザクションテーブル１２１には、トランザクションとアイテムとの欄が設けられている。トランザクションの欄には、収集されたトランザクションデータの識別情報（トランザクションＩＤ）が設定される。アイテムの欄には、収集されたトランザクションデータに含まれているアイテムの識別情報（アイテムＩＤ）が設定される。

図１０は、グループ情報記憶部のデータ構造の一例を示す図である。グループ情報記憶部１５０には、グループ管理テーブル１５１が格納されている。
グループ管理テーブル１５１には、グループとトランザクションとの欄が設けられている。グループの欄には、トランザクションのグループの識別情報（グループＩＤ）が設定される。トランザクションの欄には、対応するグループに属するトランザクションのトランザクションＩＤが設定される。

次に、第２の実施の形態におけるアイテム集合抽出処理の手順について説明する。
図１１は、アイテム集合抽出処理の手順の一例を示すフローチャートである。以下、図１１に示す処理をステップ番号に沿って説明する。

［ステップＳ１０１］収集部１１０は、ＰＯＳ端末装置３１〜３３からトランザクションデータを収集する。例えば収集部１１０は、ユーザからの指示に応じて、トランザクションデータを収集する。また収集部１１０は、所定の間隔で定期的にトランザクションデータを収集することもできる。また収集部１１０は、ＰＯＳ端末装置３１〜３３が任意のタイミングで送信したトランザクションデータを随時受信することもできる。収集部１１０は、収集したトランザクションデータをトランザクション記憶部１２０に格納する。

［ステップＳ１０２］アイテム集合抽出部１３０は、最大アイテム集合抽出処理を行う。例えばアイテム集合抽出部１３０は、ユーザからの指示に応じて最大アイテム集合抽出処理を行う。

なお、グループ情報記憶部１５０にトランザクションのグループが登録されていない場合、アイテム集合抽出部１３０は、トランザクション記憶部１２０に格納されているすべてのトランザクションデータで示されるトランザクションを１つのグループとする。そしてアイテム集合抽出部１３０は、すべてのトランザクションを処理対象として、最大アイテム集合抽出処理を行う。

また、グループ情報記憶部１５０にトランザクションのグループが登録されている場合、アイテム集合抽出部１３０は、グループごとに最大アイテム集合抽出処理を行う。グループの最大アイテム抽出処理では、そのグループに属するトランザクションが処理対象となる。最大アイテム集合抽出処理の詳細は後述する（図１３参照）。

［ステップＳ１０３］アイテム集合抽出部１３０は、ステップＳ１０２で得られた最大アイテム集合が空集合か否かを判断する。アイテム集合抽出部１３０は、最大アイテム集合が空集合であれば、処理を終了する。またアイテム集合抽出部１３０は、最大アイテム集合が空集合でなければ、処理をステップＳ１０４に進める。なおアイテム集合抽出部１３０は、最大アイテム集合が空集合でない場合、例えばトランザクション集合分割部１４０に、トランザクション集合の分割を指示する。

［ステップＳ１０４］トランザクション集合分割部１４０は、トランザクション集合分割処理を行う。例えばトランザクション集合分割部１４０は、アイテム集合抽出部１３０からのトランザクション集合の分割指示に応じて、トランザクション集合分割処理を行う。なお、トランザクション集合分割処理の詳細は後述する。

［ステップＳ１０５］トランザクション集合分割部１４０は、ステップＳ１０４の処理により、トランザクション集合を複数のグループに分割できたか否かを判断する。トランザクション集合分割部１４０は、分割できた場合、処理をステップＳ１０２に進める。またトランザクション集合分割部１４０は、分割できなかった場合、処理をステップＳ１０６に進める。なおトランザクション集合分割部１４０は、分割できなかった場合、例えば出力部１６０に、トランザクション群の分割を指示する。

［ステップＳ１０６］出力部１６０は、アイテム集合を出力する。例えば出力部１６０は、グループ情報記憶部１５０に格納されたトランザクションのグループを判断する。次に、出力部１６０は、トランザクション記憶部１２０を参照し、グループごとに、そのグループに属するトランザクションに関するトランザクションデータに含まれるアイテムを抽出する。そして出力部１６０は、グループごとに抽出したアイテムの集合を出力する。

図１２は、アイテム集合抽出処理の一例を示す図である。第１の状態は、アイテム集合抽出処理の入力データを示している。入力データは、トランザクションテーブル１２１に設定された各トランザクションデータと、各閾値（ｋ，ｍ，ｎ）の値である。アイテム集合抽出処理が開始されると、まず最大アイテム集合抽出処理が行われ、第２の状態に移行する。

第２の状態では、トランザクションテーブル１２１から、［条件１］を満たすことができないトランザクションデータとアイテムとが削除されている。すなわち、アイテム数がｋ個未満のトランザクションデータや、出現トランザクション数がｍ個未満のアイテムが削除されている。そして、トランザクションテーブル１２１に残存するトランザクションデータのいずれかに含まれるアイテムの集合が、最大アイテム集合４１として抽出されている。その後、トランザクション集合分割処理が行われ、第３の状態に移行する。

第３の状態は、トランザクション集合の分割後の状態である。トランザクション集合を分割することで、トランザクションのグループが複数生成されている。同一グループには、ｎ個以上のアイテムが共通するトランザクション間の関係を辿ることで、互いに到達可能なトランザクションが含まれる。トランザクション集合が分割されると、グループごとに、最大アイテム集合抽出処理が行われ、第４の状態に移行する。

第４の状態は、２回目の最大アイテム集合抽出処理後の状態である。２回目の最大アイテム集合抽出処理は、アイテム数がｋ個未満のトランザクションデータや、出現トランザクション数がｍ個未満のアイテムの削除が、グループごとに行われている。そしてグループごとに最大アイテム集合４２，４３が抽出されている。

その後、トランザクション集合分割処理が行われるが、これ以上、各グループを分割することができない。そこで、各グループの最大アイテム集合４２，４３が出力される。
このような最大アイテム集合抽出処理とトランザクション集合分割処理との繰り返しにより、［条件１］、［条件２］を満たす最大アイテム集合が生成される。

次に、最大アイテム集合抽出処理について説明する。
図１３は、最大アイテム集合抽出処理の手順の一例を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。

［ステップＳ１２１］アイテム集合抽出部１３０は、グループ管理テーブル１５１（図１０参照）にグループが登録されているか否かを判断する。アイテム集合抽出部１３０は、グループが登録されている場合、処理をステップＳ１２３に進める。またアイテム集合抽出部１３０は、グループが登録されていない場合、処理をステップＳ１２２に進める。

［ステップＳ１２２］アイテム集合抽出部１３０は、トランザクションテーブル１２１（図９参照）に登録されているすべてのトランザクションデータを処理対象に決定する。アイテム集合抽出部１３０は、その後、処理をステップＳ１２５に進める。

［ステップＳ１２３］アイテム集合抽出部１３０は、グループ管理テーブル１５１に登録されているグループから、ステップＳ１２５〜Ｓ１２８の処理が未処理のグループを１つ選択する。

［ステップＳ１２４］アイテム集合抽出部１３０は、選択したグループに属するトランザクションデータを処理対象に決定する。
［ステップＳ１２５］アイテム集合抽出部１３０は、処理対象のトランザクションデータのうち、アイテム数がｋ個未満のトランザクションデータを、トランザクションテーブル１２１から削除する。このとき、例えばアイテム集合抽出部１３０は、削除対象のトランザクションデータのトランクションＩＤがグループ管理テーブル１５１に設定されている場合、そのトランザクションＩＤを削除する。アイテム数がｋ個未満のトランザクションデータに示された注文を行った顧客は、［条件１］に示されている「ｋ品以上の品目を注文した顧客」には該当しない。アイテム数がｋ個未満のトランザクションデータを削除することで、以後の処理における解析対象の情報量が減少し、処理の効率化が図れる。

［ステップＳ１２６］アイテム集合抽出部１３０は、トランザクションテーブル１２１内の処理対象のトランザクションデータから、出現トランザクション数がｍ個未満のアイテムを削除する。出現トランザクション数がｍ個未満のアイテムに対応する品目は、［条件１］に示されている「ｍ人（ｍは１以上の整数）以上の顧客によって注文されている品目」には該当しない。出現トランザクション数がｍ個未満のアイテムを削除することで、以後の処理における解析対象の情報量が減少し、処理の効率化が図れる。

［ステップＳ１２７］アイテム集合抽出部１３０は、トランザクションテーブル１２１内の処理対象のトランザクションデータのうち、アイテム数がｋ個未満のトランザクションデータがあるか否かを判断する。ステップＳ１２６の処理によってアイテムが削除されたことで、トランザクションデータのアイテム数がｋ個未満となってしまう可能性がある。そこでアイテム集合抽出部１３０は、アイテム数がｋ個未満のトランザクションデータがある場合には、処理をステップＳ１２５に進め、再度トランザクションデータの削除を行う。またアイテム集合抽出部１３０は、アイテム数がｋ個未満のトランザクションデータがない場合、処理をステップＳ１２８に進める。

［ステップＳ１２８］アイテム集合抽出部１３０は、処理対象トランザクションデータのいずれか１つに含まれているアイテムの集合を、最大アイテム集合として出力する。
［ステップＳ１２９］アイテム集合抽出部１３０は、グループ管理テーブル１５１に未処理のグループがあるか否かを判断する。アイテム集合抽出部１３０は、未処理のグループがあれば処理をステップＳ１２３に進める。またアイテム集合抽出部１３０は、未処理のグループがなければ、最大アイテム集合抽出処理を終了する。

このようにして、最大アイテム集合が抽出される。
図１４は、最大アイテム集合抽出処理の一例を示す図である。図１４には、最大アイテム集合抽出処理に伴うトランザクションテーブル１２１の状態遷移状況を示している。図１４に示すトランザクションテーブル１２１では、左欄にトランザクションＩＤが示されており、トランザクションＩＤに対応づけて、トランザクションに含まれるアイテムのアイテムＩＤのリストが示されている。

なお図１４の例では、またトランザクションのグループが設定されていないものとする。従って、トランザクションテーブル１２１に登録されているすべてのトランザクションデータを処理対象とした最大アイテム集合の抽出処理が行われる。

第１の状態は、トランザクションテーブル１２１の初期状態である。初期状態において、トランザクションテーブル１２１から、アイテム数がｋ（＝２）未満のトランザクションデータが検出される。するとアイテム数が「１」の、トランザクションＩＤ「Ｔ５」のトランザクションデータが検出される。そして、そのトランザクションデータが、トランザクションテーブル１２１から削除される。

第２の状態は、アイテム数がｋ未満のトランザクションデータを削除後の状態である。第２の状態において、いずれかのトランザクションデータに出現するアイテムごとに、処理対象のトランザクションデータへの出現回数が計数される。そして、出現回数がｍ（＝２）未満のアイテムが検出される。図１４の例では、出現回数が「１」のアイテムＩＤ「Ｅ」のアイテムが検出される。そして検出されたアイテムが、トランザクションテーブル１２１内の処理対象のトランザクションデータから削除される。

第３の状態は、出現回数がｍ個未満のアイテムを削除後の状態である。図１４の例では、トランザクションＩＤ「Ｔ４」のトランザクションデータから、アイテムＩＤ「Ｆ」が削除されている。アイテムを削除後、再度、トランザクションテーブル１２１から、アイテム数がｋ個未満のトランザクションデータが検出される。するとアイテムの削除によってアイテム数が「１」になった、トランザクションＩＤ「Ｔ４」のトランザクションデータが検出される。そして、そのトランザクションデータが、トランザクションテーブル１２１から削除される。

第４の状態は、アイテム数がｋ個未満のトランザクションデータの２回目の削除処理後の状態である。第４の状態において、いずれかのトランザクションデータに出現するアイテムごとに、処理対象のトランザクションデータへの出現回数が計数される。そして、出現回数がｍ個未満のアイテムの検出処理が行われる。しかし、第４の状態では、出現回数がｍ未満のアイテムは存在しない。そこで、トランザクションテーブル１２１に残存しているトランザクションデータのいずれかに含まれるアイテムの集合が、最大アイテム集合４１として抽出される。

抽出された最大アイテム集合が空集合でなければ、トランザクション集合分割処理が行われる。
図１５は、トランザクション集合分割処理の手順を示すフローチャートである。以下、図１５に示す処理をステップ番号に沿って説明する。

［ステップＳ１３１］トランザクション集合分割部１４０は、グループ管理テーブル１５１（図１０参照）にグループが登録されているか否かを判断する。トランザクション集合分割部１４０は、グループが登録されている場合、処理をステップＳ１３３に進める。またトランザクション集合分割部１４０は、グループが登録されていない場合、処理をステップＳ１３２に進める。

［ステップＳ１３２］トランザクション集合分割部１４０は、トランザクションテーブル１２１（図９参照）に残存するすべてのトランザクションデータを処理対象に決定する。トランザクション集合分割部１４０は、その後、処理をステップＳ１３５に進める。

［ステップＳ１３３］トランザクション集合分割部１４０は、グループ管理テーブル１５１に登録されているグループから、ステップＳ１３５〜Ｓ１３７の処理が未処理のグループを１つ選択する。

［ステップＳ１３４］アイテム集合抽出部１３０は、選択したグループに属するトランザクションデータを処理対象に決定する。
［ステップＳ１３５］トランザクション集合分割部１４０は、処理対象のトランザクションデータのうち、共有アイテム数がｎ個以上のトランザクションデータによるネットワークを生成する。例えばトランザクション集合分割部１４０は、処理対象のトランザクションデータから２つのトランザクションデータを抽出して得られるすべての組み合わせについて、両方のトランザクションデータに含まれるアイテムの数（共有アイテム数）を計数する。そしてトランザクション集合分割部１４０は、共有アイテム数がｎ個以上のトランザクションデータの組み合わせについて、それらのトランザクションデータを関連付ける。トランザクション集合分割部１４０は、例えば共有アイテム数がｎ個以上のトランザクションデータ間に、関連を示すパスを設定する。これにより、パスで接続されたトランザクションのネットワークが生成される。

［ステップＳ１３６］トランザクション集合分割部１４０は、処理対象のトランザクションデータ全体によるネットワークを、ネットワーク上でパスを辿ることで到達可能なサブネットワークに分割する。なお、サブネットワークへの分割技術としては、例えば非特許文献１に開示されているConnected Component抽出アルゴリズムを利用できる。

［ステップＳ１３７］トランザクション集合分割部１４０は、サブネットワークごとのトランザクションのグループを生成する。例えばトランザクション集合分割部１４０は、ステップＳ１３６で生成されたサブネットワークに属するトランザクションを１つのグループとして、グループ管理テーブル１５１に新たなグループを登録する。またトランザクション集合分割部１４０は、ステップＳ１３３で選択したグループを分割したサブグループを登録した場合、分割前のグループをグループ管理テーブル１５１から削除する。

［ステップＳ１３８］トランザクション集合分割部１４０は、トランザクション集合分割処理の開始時点でグループ管理テーブル１５１に既に登録されていたグループのうち、未処理のグループがあるか否かを判断する。トランザクション集合分割部１４０は、未処理のグループがあれば、処理をステップＳ１３３に進める。またトランザクション集合分割部１４０は、未処理のグループがなければ、トランザクション集合分割処理を終了する。

図１６は、トランザクション集合分割処理の一例を示す図である。第１の状態は、トランザクション集合分割処理の開始時における、トランザクションテーブル１２１とグループ管理テーブル１５１との初期状態である。第１の状態におけるトランザクションテーブル１２１には、最大アイテム集合抽出処理を１回実行後に残存しているトランザクションデータが登録されている。グループ管理テーブル１５１には、グループは登録されていない。この場合、トランザクションテーブル１２１に登録されているすべてのトランザクションデータを処理対象として、トランザクション集合分割処理が行われる。トランザクション集合分割処理では、まずネットワーク５１が生成される。

第２の状態は、生成されたネットワーク５１を示している。ネットワーク５１は、処理対象のトランザクションデータのうち、ｎ個以上のアイテムが共通するトランザクションデータ間を関連付けたものである。図１６に示すネットワーク５１では、処理対象のトランザクションデータがノード６１〜６５で示され、トランザクションデータ間の関係づけが、ノード間を接続するエッジで示されている。

例えば、トランザクションＩＤ「Ｔ１」のトランザクションデータとトランザクションＩＤ「Ｔ２」のトランザクションデータとは、アイテムＩＤ「Ａ，Ｂ」の２つのアイテムが共通する。そのため、それらのトランザクションデータに対応するノード６１，６２間がエッジで接続されている。同様に、トランザクションＩＤ「Ｔ２」、「Ｔ３」それぞれのトランザクションデータに対応するノード６２，６３間がエッジで接続されている。トランザクションＩＤ「Ｔ１」、「Ｔ３」それぞれのトランザクションデータに対応するノード６１，６３間がエッジで接続されている。トランザクションＩＤ「Ｔ６」、「Ｔ７」それぞれのトランザクションデータに対応するノード６４，６５間がエッジで接続されている。

ここでネットワーク５１内のノードを、エッジによる接続関係を有するノードごとのサブネットワーク５２，５３に分けることができる。
第３の状態は、ネットワーク５１をサブネットワーク５２，５３に分割した後の状態である。サブネットワーク５２には、ノード６１，６２，６３が含まれる。サブネットワーク５３には、ノード６４，６５が含まれる。

なお、サブネットワーク５２内の各ノード６１〜６３は、他のすべてのノードと関連付けられているが、第２の実施の形態では、サブネットワーク５２内の各ノードは、同じサブネットワーク５２内の少なくとも１つの他のノードと関連付けられていればよい。例えば、ノード６３は２つのノード６１，６２にエッジで関連付けられているが、ノード６２に対して関連付けられていなくても、ノード６３はサブネットワーク５２に属することとなる。

第４の状態は、サブネットワーク５２，５３に応じたグループ生成後の状態である。第４の状態のグループ管理テーブル１５１には、トランザクションＩＤ「Ｔ１，Ｔ２，Ｔ３」のトランザクションが属するグループと、トランザクションＩＤ「Ｔ６，Ｔ７」のトランザクションが属するグループとが登録されている。

なお図１６の第４の状態は、図１２の第３の状態と同じである。すなわち、図１６の第４の状態の後、図１２に示した様に、再度最大アイテム集合抽出処理が行われる。
ところで、図１２に示した例は、２回目のトランザクション集合分割処理では、グループが分割できず、その時点の最大アイテム集合が出力されている。これは、ｋ＝２，ｍ＝２，ｎ＝２という、どのようなデータに対しても１回しか分割されることはない閾値を用いたためである。このような閾値の場合、１回目の分割で各トランザクションデータ間の結合の根拠となったアイテムは、グループ内の少なくとも２以上のトランザクションデータに含まれている。またグループのどのトランザクションデータにも２以上のアイテムが含まれる。そのため、２回目の最大アイテム集合抽出処理で削除されるトランザクションデータやアイテムはなく、それ以上分割されることはない。

閾値ｋ，ｍ，ｎの値を上記の例と異なる値にすれば、２回目移行のトランザクション集合分割処理でグループが更に分割される場合もある。
図１７は、トランザクション集合が複数回分割される例を示す図である。図１７の例では、閾値ｋ，ｍ，ｎの値がそれぞれｋ＝２，ｍ＝３，ｎ＝２である。第１の状態は、トランザクションテーブル１２１の初期状態である。図１７の例では、１２個のトランザクションデータがトランザクションテーブル１２１に登録されている。第１の状態で、最大アイテム集合抽出処理が行われる。図１７の例では、トランザクションＩＤ「Ｔ１２」のトランザクションデータのアイテム数が「１」であり、閾値ｋ（＝２）未満である。そこで該当するトランザクションデータが削除される。

トランザクションＩＤ「Ｔ１２」のトランザクションデータ削除後の各アイテムの出現数を計数すると、アイテムＩＤ「Ｉ」のアイテム数が「２」であり、閾値ｍ（＝３）未満である。そこでアイテムＩＤ「Ｉ」のアイテムがトランザクションテーブル１２１から削除される。すると、トランザクションＩＤ「Ｔ１１」のアイテム数が「２」から、ｋ個未満（＝２）の「１」に減少する。そこで該当するトランザクションデータが削除される。

第２の状態は、１回目の最大アイテム集合抽出処理後の状態である。最大アイテム集合抽出処理により、トランザクションテーブル１２１では、トランザクションＩＤ「Ｔ１１」、「Ｔ１２」のトランザクションデータと、アイテムＩＤ「Ｉ」のアイテムとが削除されている。第２の状態のトランザクションテーブル１２１に対して、トランザクション集合分割処理が行われる。

トランザクション集合分割処理で生成されるネットワーク７１は、２つのサブネットワーク７２，７３に分けられる。そこで、サブネットワーク７２，７３ごとのグループが生成される。図１７の例では、グループＩＤ「Ｇ１」のグループに、トランザクションＩＤ「Ｔ１，Ｔ２，Ｔ３，Ｔ４，Ｔ５，Ｔ６，Ｔ７」のトランザクションデータが含まれる。またグループＩＤ「Ｇ２」のグループに、トランザクションＩＤ「Ｔ８，Ｔ９，Ｔ１０」のトランザクションデータが含まれる。

第３の状態は、１回目のトランザクション集合分割処理後の状態である。第３の状態において、２回目の最大アイテム集合抽出処理が行われる。２回目の最大アイテム集合抽出処理では、グループごとに処理が行われる。グループＩＤ「Ｇ１」のグループの各アイテムの出現数を計数すると、アイテムＩＤ「Ｂ」のアイテム数が「２」であり、閾値ｍ（＝３）未満である。そこでアイテムＩＤ「Ｂ」のアイテムが、グループＩＤ「Ｇ１」のグループに属するトランザクションのトランザクションデータから削除される。またグループＩＤ「Ｇ２」のグループの各アイテムの出現数を計数すると、アイテムＩＤ「Ｂ」のアイテム数が「１」であり、閾値ｍ（＝３）未満である。そこでアイテムＩＤ「Ｂ」のアイテムが、グループＩＤ「Ｇ２」のグループに属するトランザクションのトランザクションデータから削除される。

第４の状態は、２回目の最大アイテム集合抽出処理後の状態である。第４の状態において、２回目のトランザクション集合分割処理が行われる。図１７の例では、２回目の最大アイテム集合抽出処理によって、各グループのトランザクションデータから、アイテムＩＤ「Ｂ」のアイテムが削除されている。そのため、トランザクションＩＤ「Ｔ４」のトランザクションデータとトランザクションＩＤ「Ｔ５」のトランザクションデータとに共に含まれるアイテムは、アイテムＩＤ「Ａ」のアイテムのみとなる。すると共に含まれるアイテム数「１」が閾値ｎ（＝２）未満となり、トランザクションＩＤ「Ｔ４」のトランザクションデータとトランザクション「Ｔ５」のトランザクションデータとの関連性は失われる。その結果、１回目のトランザクション集合分割処理で生成されたサブネットワーク７２は、さらに２つのサブネットワーク７４，７５に分割される。なおサブネットワーク７３は分割されない。

そこで、サブネットワーク７３〜７５ごとのグループが生成される。図１７の例では、グループＩＤ「Ｇ１−１」のグループに、トランザクションＩＤ「Ｔ１，Ｔ２，Ｔ３，Ｔ４」のトランザクションデータが含まれる。グループＩＤ「Ｇ１−２」のグループに、トランザクションＩＤ「Ｔ５，Ｔ６，Ｔ７」のトランザクションデータが含まれる。またグループＩＤ「Ｇ２」のグループに、トランザクションＩＤ「Ｔ８，Ｔ９，Ｔ１０」のトランザクションデータが含まれる。

第５の状態は、２回目のトランザクション集合分割処理後の状態である。第５の状態において、３回目の最大アイテム集合抽出処理が行われるが、トランザクションデータやアイテムは削除されない。そのため、２回目のトランザクション集合分割処理を行っても、分割されるグループはない。

そこで、第５の状態に示すトランザクションテーブル１２１に基づいて得られた、グループごとの最大アイテム集合７６が出力される。図１７の例では、グループＩＤ「Ｇ１−１」のグループに基づき、最大アイテム集合｛Ａ，Ｃ，Ｅ，Ｆ｝が出力されている。グループＩＤ「Ｇ１−２」のグループに基づき、最大アイテム集合｛Ａ，Ｄ｝が出力されている。グループＩＤ「Ｇ２」のグループに基づき、最大アイテム集合｛Ｇ，Ｈ｝が出力されている。

以上のようにして、［条件１］、［条件２］を満たす最大アイテム集合が得られる。第２の実施の形態に示した処理で最大アイテム集合を得ることで、効率的な計算が行われる。以下、第２の実施の形態における計算量について説明する。なお、以下の説明では、計算量をＯ記法で表す。

［最大アイテム集合抽出処理の計算量］
ここで、全アイテム数をＮ（Ｎは、１以上の整数）、全トランザクション数をＭ（Ｍは、１以上の整数）とする。

最初の最大アイテム集合抽出処理では、まず全トランザクションのアイテム数が集計される。この処理の計算量は、Ｏ（Ｍ）となる。
次に全アイテムのトランザクション数が集計される。この処理の計算量は、Ｏ（Ｎ）である。

この繰り返し処理の計算量は、大きく見積もってもＯ（Ｍ＋Ｎ）である。
すると、最大アイテム集合抽出処理の計算量は、Ｏ（Ｍ＋Ｎ）となる。
［トランザクション集合分割処理の計算量］
トランザクション集合分割処理の計算量は、上記非特許文献１に開示されているConnected Component抽出アルゴリズムの計算量となり、Ｏ（Ｍ＋Ｎ）である。

すると最大アイテム集合抽出処理とトランザクション集合分割処理を合わせた計算量は、Ｏ（Ｍ＋Ｎ）である。
第２の実施の形態では、最大アイテム集合抽出処理とトランザクション集合分割処理が、トランザクションのグループを分割できなくなるまで繰り返される。この場合の総計算量は、大きく見積もってもＯ（（Ｍ＋Ｎ）＋（Ｍ＋Ｎ−１）＋…＋１）＝Ｏ（（Ｍ＋Ｎ）²）である。

一方、第２の実施の形態の技術を用いずに、［条件１］と［条件２］とを満足する最大アイテム集合を求める場合、すべてのアイテムの組み合わせについて、［条件１］と［条件２］とを満たすかどうかを判断することとなる。この場合の計算量は、Ｏ（Ｍ×２^N）である。

すると第２の実施の形態の技術を用いた場合の計算量Ｏ（（Ｍ＋Ｎ）²）は、Ｎが大きいとき、第２の実施の形態の技術を用いない場合の計算量Ｏ（Ｍ×２^N）よりも、格段に少なくなる。すなわち、全アイテム数Ｎが多いほど、第２の実施の形態の技術による処理の効率化の効果が高まる。

以上にして出力された最大アイテム集合を用いることで、例えばできるだけ多くの顧客に役立つような品目が掲載されたメニューを作成できる。さらに、このメニューに掲載された品目は、注文する品目に同じ傾向の顧客によって併せて注文されることが多い。そのため、各顧客は、自分と同じ傾向の顧客に注文されることの多いメニューだけを見ることができる。

また第２の実施の形態によれば、グループごとの最大アイテム集合が抽出される。抽出される最大アイテム集合は、それぞれを有効に利用できる顧客の傾向が異なる。そのため、抽出された複数の最大アイテム集合それぞれに基づいて、別個のメニューを作成すれば、それぞれ異なる傾向を持つ顧客群にとって有用なメニューとなる。例えば、辛い料理を好む顧客群用のメニューや、低カロリーの料理を好む顧客群用のメニューなど、顧客の嗜好に合わせたメニューが作成できる。

［その他の実施の形態］
なお、上記の各実施の形態に示した処理機能は、コンピュータによって実現することができる。その場合、サーバ１００が有する機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。なお記録媒体には、一時的な伝送信号自体は含まれない。

プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。

プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。

また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。

以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。

１ 記憶手段
１ａ，１ｂ，１ｃ，・・・ 集合
２ 第１の削除手段
３ グループ生成手段
４ 第２の削除手段
５ 別グループ生成手段
６ 出力手段
Ｃ 情報処理装置

Claims (8)

1. 記憶手段に格納された、少なくとも１つの要素を含む複数の集合に対して、包含数閾値未満の要素しか含まない集合の削除と、出現数閾値未満の集合にしか含まれない要素の削除とを行う第１の削除手段と、
   集合と要素との削除後に前記記憶手段内に残存する集合のうち、要素の共通性によって関連付けられた集合が属するグループを生成するグループ生成手段と、
   生成されたグループごとに、前記記憶手段内の該グループに属する集合に対して、前記包含数閾値未満の要素しか含まない集合の削除と、該グループに属する集合のうち前記出現数閾値未満の集合にしか含まれない要素の削除とを行う第２の削除手段と、
   集合と要素との削除後にグループに残存する集合に含まれる要素のリストを出力する出力手段と、
   を有する情報処理装置。
2. 前記第１の削除手段と前記第２の削除手段とは、削除する集合および要素が無くなるまで、集合の削除と要素の削除とを交互に繰り返すことを特徴とする請求項１記載の情報処理装置。
3. 前記グループ生成手段は、集合と要素との削除後に前記記憶手段内に残存する集合のうち、共有数閾値以上の要素を共有する集合間を関連付け、関連付けられた集合間を辿ることで到達可能な複数の集合が属するグループを生成する、
   ことを特徴とする請求項１または２のいずれかに記載の情報処理装置。
4. 集合と要素との削除が行われたグループごとに、該グループに残存する集合を、要素の共通性によって関連付け、関連付けられた複数の集合が該グループに残存する集合の一部の場合、関連付けられた複数の集合が属する別のグループを生成する別グループ生成手段をさらに有し、
   前記出力手段は、集合と要素との削除が行われたグループから別のグループが生成できなかった場合、該グループに残存する集合に含まれる要素のリストを出力する、
   ことを特徴とする請求項１乃至３のいずれかに記載の情報処理装置。
5. 前記別グループ生成手段は、集合と要素との削除が行われたグループに残存する集合のうち、共有数閾値以上の要素を共有する集合間を関連付け、関連付けられた集合間を辿ることで到達可能な複数の集合が該グループに残存する集合の一部である場合、該複数の集合が属する別のグループを生成することを特徴とする請求項４記載の情報処理装置。
6. 要素は、取り引きの対象となる品目であり、集合は、同時に取り引きされた品目を含むトランザクションであることを特徴とする請求項１乃至５のいずれかに記載の情報処理装置。
7. コンピュータに、
   記憶手段に格納された、少なくとも１つの要素を含む複数の集合に対して、包含数閾値未満の要素しか含まない集合の削除と、出現数閾値未満の集合にしか含まれない要素の削除とを行い、
   集合と要素との削除後に前記記憶手段内に残存する集合のうち、要素の共通性によって関連付けられた集合が属するグループを生成し、
   生成されたグループごとに、前記記憶手段内の該グループに属する集合に対して、前記包含数閾値未満の要素しか含まない集合の削除と、該グループに属する集合のうち前記出現数閾値未満の集合にしか含まれない要素の削除とを行い、
   集合と要素との削除後にグループに残存する集合に含まれる要素のリストを出力する、
   処理を実行させるプログラム。
8. コンピュータが、
   記憶手段に格納された、少なくとも１つの要素を含む複数の集合に対して、包含数閾値未満の要素しか含まない集合の削除と、出現数閾値未満の集合にしか含まれない要素の削除とを行い、
   集合と要素との削除後に前記記憶手段内に残存する集合のうち、要素の共通性によって関連付けられた集合が属するグループを生成し、
   生成されたグループごとに、前記記憶手段内の該グループに属する集合に対して、前記包含数閾値未満の要素しか含まない集合の削除と、該グループに属する集合のうち前記出現数閾値未満の集合にしか含まれない要素の削除とを行い、
   集合と要素との削除後にグループに残存する集合に含まれる要素のリストを出力する、
   ことを特徴とする要素抽出方法。

Images