パターン抽出装置及び方法
【課題】複数のアイテムを含む対象情報から、アイテム間の関連性を反映させたパターン抽出の制御を行う。
【解決手段】実施形態のパターン抽出装置は、複数の対象情報を記憶する第1記憶部と、複数の対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成する候補パターン生成部と、生成された候補パターンが複数の対象情報それぞれに出現する出現頻度に基づいて、候補パターンの抽出評価値を算出する候補評価値算出部と、算出された抽出評価値が所定の閾値を満たす候補パターンを判別して抽出するパターン抽出部と、アイテム間の関連度を記憶する第2記憶部とを含み、候補評価値算出部は、候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び出現頻度に基づいて、抽出評価値を算出する。
【解決手段】実施形態のパターン抽出装置は、複数の対象情報を記憶する第1記憶部と、複数の対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成する候補パターン生成部と、生成された候補パターンが複数の対象情報それぞれに出現する出現頻度に基づいて、候補パターンの抽出評価値を算出する候補評価値算出部と、算出された抽出評価値が所定の閾値を満たす候補パターンを判別して抽出するパターン抽出部と、アイテム間の関連度を記憶する第2記憶部とを含み、候補評価値算出部は、候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び出現頻度に基づいて、抽出評価値を算出する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明の実施形態は、複数のアイテムを含む対象情報からアイテムの組合せパターンを抽出する制御に関する。
【背景技術】
【0002】
従来から各種の活動や事象などを分析するために、複数のアイテムで構成された対象情報から、分析目的等に応じた特定のパターンすなわちアイテムの組合せを、効率良く抽出するための装置や方法が研究されている。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2003−76937号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
アイテムを含む複数の対象情報から、アイテム間の関連性を反映させて、特定のパターンを抽出させるパターン抽出装置及び方法を提供する。
【課題を解決するための手段】
【0005】
実施形態のパターン抽出装置は、複数のアイテムを含む対象情報内に存在する相互に異なる2以上のアイテムの組合せのパターンを抽出するパターン抽出装置であって、複数の対象情報を記憶する第1記憶部と、複数の対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成する候補パターン生成部と、生成された候補パターンが複数の対象情報それぞれに出現する出現頻度に基づいて、候補パターンの抽出評価値を算出する候補評価値算出部と、算出された抽出評価値が所定の閾値を満たす候補パターンを判別し、閾値を満たす候補パターンを抽出するパターン抽出部と、を含むとともに、アイテム間の関連度を記憶する第2記憶部をさらに含む。候補評価値算出部は、候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び出現頻度に基づいて、抽出評価値を算出する。
【図面の簡単な説明】
【0006】
【図1】第1実施形態のパターン抽出装置の構成例を示す図であり、本装置を構成する各部間の関係を示すブロック図である。
【図2】データ格納部に格納される対象情報としてのトランザクション群の一例を示す図である。
【図3】アイテム間情報記憶部に記憶される関連度行列テーブルの一例を示す図である。
【図4】パターン抽出装置の動作を説明するためのフローチャートである。
【図5】アイテム抽出部が行う処理を説明するためのサブルーチンである。
【図6】長さが1となる候補パターンの頻度と支持度の一例を示す図である。
【図7】パターン格納部に格納される長さ1のパターンの一例を示す図である。
【図8】候補パターン生成部が行う処理を説明するためのサブルーチンである。
【図9】候補評価値算出部が行う処理を説明するためのサブルーチンである。
【図10】長さが2となる候補パターンの頻度と関連性支持度の一例を示す図である。
【図11】パターン格納部に格納される長さ2のパターンの一例を示す図である。
【図12】長さが3となる候補パターンの頻度と関連性支持度の一例を示す図である。
【図13】パターン格納部に格納される長さ3のパターンの一例を示す図である。
【図14】パターン抽出装置の他の実施形態の動作を説明するためのフローチャートである。
【発明を実施するための形態】
【0007】
以下、実施形態につき、図面を参照して説明する。
【0008】
実施形態に係るパターン抽出装置は、複数のアイテム(情報要素)を含む対象情報が複数与えられた場合に、アイテム間に存在する関係を利用して、当該複数の対象情報の中からアイテムの特徴的な組合せ(パターン)を抽出する制御を遂行するものである。
【0009】
なお、「パターン」の用語は、通常は2以上のアイテムの組合せを意味するが、以下の説明では、単一のアイテムに対しても「パターン」の用語が用いられる場合がある。一方、「パターン」の用語は、狭義には、上記「アイテムの特徴的な組合せ」を有するパターンを意味する。そして、かかる狭義のパターンを抽出するための候補となるパターンを「パターンの候補」または「候補パターン」と称する。
【0010】
本装置は、例えば、スーパーマーケットなどの日用品の販売における、購入商品の特徴的な組合せの発見、銀行業務における、店舗の特性と事務ミスの種類との間にある特徴的な因果関係の発見、番組推薦における、視聴者特性と視聴履歴との間にある視聴者の嗜好の発見などの分野に利用することができる。但し、これらは例示であって、これに限定されるものではない。
【0011】
以下の説明では、スーパーマーケットなどの日用品(食品)の販売業における商品をアイテムとして本装置で扱う場合について説明する。具体的には、あるスーパーマーケットでの食品を販売するフロアにおいて、購入者が購入した商品(食品)の特徴的な組合せ(すなわち「パターン」)を抽出、発見するために、商品購入者の一枚のレシートを1個の対象情報(トランザクション)とし、レシートに記載された商品(食品名等の品名)をアイテムとして扱う場合について説明する。
【0012】
図1から図13は、第1実施形態を示す図である。図1は、本実施形態のパターン抽出装置100のブロック構成図であり、図中の各ブロックを結線する矢印は、データの流れる方向を示している。本装置は、複数の対象情報としてトランザクションの集合を記憶する第1記憶部としてのデータ格納部10と、アイテム間の関連性に関する情報を記憶する第2記憶部としてのアイテム間情報格納部20と、トランザクションの集合からアイテムを抽出するアイテム抽出部30と、抽出されたアイテムを用いて、相互に異なる2以上のアイテムの組合せによるパターンの候補(候補パターン)を生成する候補パターン生成部40と、候補パターンがトランザクションに出現する頻度を算出する候補頻度算出部50と、候補パターンの頻度及び前記アイテム間の関連性に関する情報を用いて、候補パターンに対する抽出評価値を算出する候補評価値算出部60と、算出された抽出評価値が基準値を満たす候補パターンをパターンとして抽出する処理を行う候補評価部70およびパターン格納部80と、を含む。
【0013】
本装置は、後述する各処理を実行するプログラムのデータを図示しないハードディスク装置などの外部記憶媒体に格納し、かかるプログラムをパーソナルコンピュータ(PC)に読み込ませることで実現することができる。この場合、例えば当該コンピュータのハードディスク装置やRAMなどの記憶デバイスがデータ格納部10、アイテム間情報格納部20、パターン格納部80として機能し、CPUなどの制御デバイスがアイテム抽出部30、候補パターン生成部40、候補頻度算出部50、候補評価値算出部60、及び候補評価部70として機能することができる。
【0014】
データ格納部10は、後述する一連の処理に先立って、対象情報であるトランザクションの集合(以下、「トランザクション群」ともいう。)のデータを記憶するトランザクション記憶部として機能するとともに、後述する最小支持度に関するデータ、及び、アイテムの整列の優先度を示すデータを格納する。
【0015】
データ格納部10に記憶される対象情報としてのトランザクション群の一例を図2に示す。トランザクションは、複数のアイテム(この例では実際に購入された商品である「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の6個すなわち6種のアイテム)の内の1種以上のアイテムで構成されたものであり、図2ではA01、A02、A03、A04、A05の5個のトランザクションがトランザクション群としてデータ格納部10の所定記憶領域に記憶(格納)された場合を例示している。
【0016】
スーパーマーケットなどの日用品の販売業を対象とした場合、購入商品の一覧が記載された1枚のレシートが1つのトランザクション(例えばA01)に相当する。ただし、この例では、レシートに記載されている商品の金額や購入個数には着目しておらず、商品が購入されたかどうかに関する情報のみに着目している。このため、データ格納部10には、図2に例示したように、商品名の情報のみをアイテムとし、購入個数が複数であっても1つの商品名が複数個存在しない形態のトランザクションのデータが格納されることになる。
【0017】
本実施形態では、データ格納部10に格納されるトランザクション群のデータ構造として、各トランザクションを識別するためのトランザクション番号(A01〜A05)と、当該トランザクションを構成するアイテムの一覧を示すアイテムリスト(この例では購入リスト)と、が対応付けられた構造となっている。A01乃至A05の各トランザクションは、購入リストに示す1又は複数種類のアイテムから構成される。すなわち、トランザクションA01では4つのアイテム(換言すると4種類の商品、以下同様)、トランザクションA02では3つのアイテム、トランザクションA03では4つのアイテム、トランザクションA04では2つのアイテム、トランザクションA05では3つのアイテムで構成されていることが分かる。各トランザクションにおいて、各々のアイテムは、カンマ等の所定の記号で区切られることにより識別される。ここでは簡明のため、トランザクション群を構成する全てのトランザクションが複数のアイテムからなる場合を説明するが、1つ以上のアイテムがあればトランザクションとして成立し得る。
【0018】
また、データ格納部10に格納される最小支持度に関するデータは、分析者等により予め設定される数値データであり、本実施形態では、かかる数値は、後述する頻出アイテムを抽出するための基準値(閾値)であるとともに、複数のアイテムで構成された候補パターンから特徴的なパターンを抽出するための基準値(閾値)としても使用される。かかる最小支持度の数値データは、図示しないマウスやキーボードなどの操作入力部の操作により、処理に先立って、使用されるトランザクション群を構成するトランザクションの数やアイテムの構成等に応じて任意に設定、変更等することができる。
【0019】
以下は最小支持度の数値を40%とした場合について説明するが、この値に限定されるものではない。また、以下は最小支持度の数値を予め一律40%に設定とした場合について説明するが、パターンの次数ないし長さ(すなわち当該パターンが構成されるアイテムの個数)毎に異なる数値を予め設定することもできる。
【0020】
さらに、データ格納部10に格納されるアイテムの整列の優先度を示すデータは、後述する候補パターン生成の際に参照されるものであり、本例では、優先度の高い方から「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の順となっている。このデータも、処理に先立って、図示しないマウスやキーボードなどの操作入力部の操作により、任意に設定、変更等することができる。本実施形態の優先度は、パターンを構成する複数のアイテムの整列順を規定する情報であり、例えば、品目のカテゴリ順、カテゴリ内の品目順、辞書や「あいうえお」順等の一定のルールに基づいて複数のアイテムを整列させるためのものである。当該優先度を用いることで、例えば、候補パターンの生成処理を円滑かつ迅速に行うことができる。
【0021】
アイテム間情報格納部20は、後述する一連の処理に先立って、使用されるトランザクション群を構成する各アイテム間の関連性に関する情報(以下「アイテム間知識」ともいう。)のデータを記憶する。アイテム間知識のデータは、各アイテム相互間(同一アイテム間をも含む)の関連度のデータ、より詳細には、関連度の高低を示す数値データであり、本実施形態では、アイテム間の関連度が高いほど大きな数値となる。
【0022】
アイテム間情報格納部20に記憶されるアイテム間知識の一例を図3に示す。本例では、アイテム間知識として、トランザクション群中に存在する各アイテムを行列形式で配置したデータテーブルを使用している。ここで、アイテム間知識は、アイテムとアイテムとの間にどの程度の関係があるかを、0から1までの範囲の数値によって示したものであり、以下は、当該数値を「関連度」と称する。ここで、関連度は、アイテム間の関係が強い(関連度が高い)程その値が大きくなり、関係が弱い(関連度が低い)程その値が小さくなるように定義される。また、同一のアイテムに対する関連度は、最大値の1が与えられる。かかる関連度の具体的な数値は、図示しないマウスやキーボードなどの操作入力部の操作により、処理に先立って、処理対象となるトランザクションのアイテムの上位概念となるカテゴリの数やカテゴリの構造などに応じて、分析者らが任意に設定、変更等することができる。
【0023】
図3の例では、アイテム間情報格納部20に記憶されるアイテム間知識として、トランザクション群中に存在するn個の各アイテムを行(i)方向及び列(j)方向に整列し、2つのアイテム間の関係を数値で表した行列(以下、この行列を「関連度行列」とも称する。)形式により各アイテム同士の関連度の値を登録する関連度行列テーブルが用いられる。この関連度行列テーブルでは、1を最大値として、アイテム同士の関連度が高くなるほど大きな値が登録される。具体的には、同一のアイテム間(「鶏肉」と「鶏肉」、「豚肉」と「豚肉」など)には最大値である1が登録され、異なるアイテム同士(「鶏肉」と「豚肉」、「鶏肉」と「ビール」など)には、アイテム間の関係の強さに応じた値が登録される。この例では、アイテムの属するカテゴリが同じである場合、すなわち肉類同士(「鶏肉」と「豚肉」、「鶏肉」と「牛肉」、「豚肉」と「牛肉」)の場合、魚類同士(「鮪」と「鯵」)の場合には中程度の関連度として0.5の値が登録される。一方、アイテムの属するカテゴリが異なる場合、すなわち上記肉類に属するアイテムと、魚類に属するアイテムと、飲料品のカテゴリに属するアイテムであるビールと、の間には関連がないものとして0の値が登録される。
【0024】
なお、本実施形態において、「アイテム間知識」は、パターン(組合せ)として抽出したくないアイテム間の関連性の値と言い換えることもできる。すなわち、同じアイテム同士の組合せ(「鶏肉」と「鶏肉」、「豚肉」と「豚肉」など)は、分析時にパターンとして抽出しないように最大値(本例では1)が設定され、カテゴリが同じアイテムの組合せ(例えば「鶏肉」と「豚肉」)は、分析時にパターンとしてやや抽出しにくいような値(本例では0.5)が設定され、さらに、カテゴリが大きく異なるアイテムの組合せ(例えば「鶏肉」と「ビール」)は、分析時にパターンとしてより抽出されやすいような値(本例では0)が設定されることになる。
【0025】
アイテム抽出部30は、データ格納部10に格納されたトランザクション群のデータを読み出し、読み出されたデータから頻出するアイテムを抽出する処理を行う。具体的には、アイテム抽出部30は、データ格納部10から各トランザクション毎に構成するアイテムを抽出し、抽出されたアイテム毎に、その出現頻度すなわちアイテムが出現するトランザクションの個数(以下「アイテム頻度」ともいう)を算出する。算出されたアイテム頻度の情報は、アイテム抽出部30から候補パターン生成部40に渡される。さらに、アイテム抽出部30は、算出されたアイテム頻度に基づいて、当該アイテムに対する支持度を算出し、該算出値が上述したデータ格納部10に予め設定されている最小支持度(この例では40%)以上となるアイテムのみを、頻出アイテムとしてパターン格納部80に格納する。
【0026】
ここで、任意の1つのアイテム(it)に対する支持度の具体的な算出方法は、下記の数式1に従う。
【0027】
【数1】
【0028】
候補パターン生成部40は、トランザクション群を参照しつつ、アイテムの集合で構成されたパターンの候補を生成する。具体的には、候補パターン生成部40は、後述するパターン格納部80に格納された長さmのパターン(m=1の上述した頻出アイテム又は後述する高次(mは2以上)のパターン)を読み込み、データ格納部10内のトランザクション群を参照しながら、頻出アイテムまたはパターンから、所定条件を満たす長さm+1のパターンの候補(候補パターン)を生成する。候補パターン生成部40が作成する候補パターンには、頻出アイテムを2個ずつ並べた2次パターン(図10参照)、長さが2以上のパターン(図11参照)に対して当該パターンに含まれるアイテムのうち所定条件を満たすアイテムを加えた3次以上のパターン(図12参照)があり、かかる所定条件及び候補パターン生成部40が行う処理の詳細については後述する。
【0029】
また、パターン格納部80に格納された高次のパターンは、トランザクション群中の複数のトランザクションに出現する長さが2以上(2次以上)のパターンの内、アイテムの特徴的な組合せを有するものとして抽出、格納されたものであり、かかる抽出、格納の処理の詳細については後述する。
【0030】
候補頻度算出部50は、候補パターン生成部40により生成された候補パターンのトランザクション群中に出現する出現頻度(トランザクションの数)を、候補パターン毎に算出し、該算出された候補パターン毎の頻度の値を候補評価値算出部60に渡す。
【0031】
候補評価値算出部60は、候補頻度算出部50からの候補パターン毎の出現頻度の値と、上述したアイテム間知識(関連度行列テーブル)とを用いて、候補パターンに対する評価値として、当該パターンを構成するアイテム数の増大に対して単調に減少するように、アイテム間の関連性を反映させた評価値(抽出評価値)を算出する。以下、かかる評価値を「関連性支持度」と称する。候補評価値算出部60は、候補パターン毎に関連性支持度を算出し、該算出された関連性支持度の値を候補評価部70に渡す。
【0032】
候補評価部70は、候補評価値算出部60からの関連性支持度の値が所定の基準値を満たすか否かを候補パターン毎に判定し、かかる基準値を満たすと判定された候補パターンのデータをパターン格納部80に格納する。本実施形態では、候補評価部70は、データ格納部10に設定された最小支持値を参照して、当該候補パターンの関連性支持度の値が最小支持値(本例では40%)以上であるか否かを判定し、最小支持値以上の候補パターンのデータをパターン格納部80に格納する処理を行う。かかる処理により、候補パターンの内の「パターン」すなわちアイテムの特徴的な組合せを有するものが抽出され、パターン格納部80の記憶領域に保存される。
【0033】
パターン格納部80は、アイテム抽出部30または候補評価部70により頻出アイテムまたはパターンのデータが格納されると、当該データが格納された旨を候補パターン生成部40に通知し、格納されたパターンのデータを候補パターン生成部40に提供する。また、パターン格納部80に格納された頻出アイテムまたはパターンのデータは、格納に伴って自動で或いはユーザの操作入力部の操作により、適宜、図示しないLCDなどの表示部に表示したり不図示のプリンタなどで印字出力することができる。
【0034】
以下、フローチャートを参照して、パターン抽出装置100の詳細な処理内容について説明する。
【0035】
本実施形態のパターン抽出装置100は、図4のフローチャートのステップS1から処理を開始する。ステップS1では、アイテム抽出部30が、データ格納部10に格納されているトランザクション群の読み込みを行なう。かかる処理により、上述のトランザクションを構成するアイテムのデータが、各トランザクション番号毎にCPUの作業領域(RAM)に読み込まれる。図2の例では、トランザクションA01のアイテムとして「鶏肉」、「鮪」、「鯵」、「ビール」のデータが、トランザクションA02のアイテムとして「鶏肉」、「豚肉」、「ビール」のデータが、トランザクションA03のアイテムとして「鶏肉」、「豚肉」、「鮪」、「ビール」のデータが、トランザクションA04のアイテムとして「牛肉」、「鯵」のデータが、トランザクションA05のアイテムとして「鶏肉」、「鮪」、「鯵」のデータが、それぞれ読み込まれる。
【0036】
ステップS2では、候補評価値算出部60が、アイテム間情報格納部20に格納されているアイテム間知識の読み込みを行なう。かかる処理によって、図3で上述した関連度行列テーブルに登録された各アイテム間の数値データがCPUの作業領域(RAM)に読み込まれる。読み込まれた数値データは、後述する抽出評価値算出の処理で使用されることになる。
【0037】
続くステップS3では、アイテム抽出部30が図5のサブルーチンに従って、出現頻度の高いアイテム(頻出アイテム)の抽出及び格納の処理を行う。まず、アイテム抽出部30は、ステップS2で読み込まれたトランザクションの集合をサーチすることにより、トランザクションを構成するアイテムの種類をすべて抽出する(ステップS31)。例えば、図2のトランザクションの集合の場合、アイテム抽出部30は、「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の6種類のアイテムを抽出する。本実施形態では、抽出されたアイテムは、候補アイテムとして扱われ、換言すると、特徴的なパターンの候補となり得る1次(長さ1)の候補パターンとして扱われる(図6参照)。
【0038】
次に、アイテム抽出部30は、取り出された各アイテムに対して、アイテムごとに、以下のステップS32乃至ステップS35の処理を行う。まず、アイテム抽出部30は、取り出された各アイテムの内、1つのアイテムについて、ステップS2で読み込まれたトランザクション群を参照して、当該アイテムが出現するトランザクションの個数をアイテム頻度として算出する(ステップS32)。例えば、図2のトランザクション群の場合、アイテム「鶏肉」は、トランザクションA01、A02、A03、A05に含まれているため、「鶏肉」の頻度として「4」が算出される。
【0039】
次に、アイテム抽出部30は、算出された当該アイテムの頻度に基づいて、上述した数式1によりアイテムに対する支持度を算出し(ステップS33)、その値がデータ格納部10に予め設定されている最小支持度以上となるか否かを判定する(ステップS34)。例えば、頻度が4と算出された上述のアイテム「鶏肉」の場合、トランザクションの総数が5であるため、その支持度は(4/5×100=)80%となる。
【0040】
このとき、アイテム抽出部30は、算出されたアイテムの支持度がデータ格納部10に格納されている最小支持度(本例では40%)以上となる場合には、ステップS35で当該アイテムを頻出アイテムとしてパターン格納部80に格納してステップS36に移行する。一方、アイテム抽出部30は、算出されたアイテムの支持度が最小支持度(40%)に満たない場合には、当該アイテムをパターン格納部80に格納せずに、パターンの対象から除外(当該アイテムのデータを廃棄)してステップS36に移行する。ステップS36で、アイテム抽出部30は、ステップS31で抽出された全てのアイテムについての処理が完了したか否かを判定し、未だ処理が完了していない場合にはステップS32に戻って上述したステップS32乃至ステップS35の処理を繰り返し、一方、全てのアイテムについての処理が完了した場合にはステップS37に移行する。
【0041】
従って、支持度が80%と算出された上述のアイテム「鶏肉」の場合、最小支持度(40%)以上であるため(ステップS34でYES)、頻出アイテムとしてパターン格納部80に格納される。同様にして、他のアイテム「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」についても、アイテム抽出部30によって、頻度が各々「2」、「1」、「3」、「3」、「3」と算出され(ステップS32)、支持度は各々「40%」、「20%」、「60%」、「60%」、「60%」と算出され(ステップS33)、図6に示すように、長さ1の候補パターンとして各アイテムの頻度と支持度が算出される。そして、本例では最小支持度が40%に設定されているので、最小支持度に満たないアイテム「牛肉」だけがパターンの対象から除外され(ステップS34でNO)、図7に示すように、「牛肉」を除く、「鶏肉」、「豚肉」、「鮪」、「鯵」、「ビール」が、頻出アイテムとしてパターン格納部80に格納されることになる。
【0042】
ここで、後述する長さ2以上の候補パターン生成の処理のために、パターン格納部80に格納される頻出アイテムは、アイテム抽出部30がデータ格納部10の上述したアイテムの整列の優先度を示すデータを参照することにより、予め定められた順序に従って整列される。本実施形態では、図6に示すように、「鶏肉」、「豚肉」、「鮪」、「鯵」、「ビール」の優先順で各パターンが整列される。以上のように、ステップS3(ステップS31乃至ステップS36)の一連の処理を行うことにより、最小支持度に満たないアイテム(本例では「牛肉」)がパターンの候補から除外され、高次の候補パターンの要素とならなくなるので、コンピュータの処理負担が大幅に減少し、高次のパターン抽出までの時間が短縮化される。なお、本実施形態では、頻出アイテムは、パターンを構成するアイテムの数(パターンの長さ)が1となる「パターン」(すなわち特徴的な組合せ)とみなされる。
【0043】
ステップS37で、アイテム抽出部30は、パターン格納部80を参照して、頻出アイテムが存在するか否かについて判定し、存在すると判定された場合には頻出アイテムの抽出に成功したものとしてステップS4に移行し、一方、存在しないと判定された場合には頻出アイテムの抽出に失敗したものとして本装置の処理を終了する。すなわち、ステップS3の処理で頻出アイテムが1つも抽出されない場合には、本装置における処理が終了する。
【0044】
ステップS4では、候補パターン生成部40が図8のサブルーチンに従って、パターンの候補を生成する処理を行う。まず、候補パターン生成部40は、ステップS41で、パターン格納部80から取り出すパターンの長さ(mの値)を設定する。具体的には、候補パターン生成部40は、初めてステップS41を実行する場合には、パターンの長さmの値を1に設定し(m=1)、2度目以降はパターンの長さmの値に1を加算する(m=m+1)。
【0045】
次に、候補パターン生成部40は、パターン格納部80に格納されているパターン(長さ1の頻出アイテムまたは長さ2以上のパターン)の内、前ステップで設定された長さmのパターンが2個以上あるかを判定し(ステップS42)、NOすなわち0個又は1個しかないと判定された場合には、候補パターンを生成できないものとして処理を終了し、YESすなわち2個以上あると判定された場合には、該当するパターンを全て取り出し(ステップS43)、ステップS44に移行する。候補パターン生成部40は、ステップS44で、取り出された全てのパターンの内、候補パターン生成条件に合致する2つのパターンがあるかを判定し、無いと判定された場合には、候補パターンを生成できないものとして処理を終了し、あると判定された場合にはステップS45に移行する。
【0046】
本実施形態では、ステップS44の候補パターン生成条件として、「先頭からm−1個までのパターンが同一のアイテムであり、最後の1つのアイテムが異なっていること」が設定されている。ただし、この前提として、各パターンにおいては、アイテムは予め定められた順序に従って整列される必要がある。本例は、上述したように、「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の順で優先度が付けられているため、この優先度に従って各パターンが整列される。
【0047】
候補パターン生成部40は、ステップS44の候補パターン生成条件を満たすパターンを2個取り出し(ステップS45)、異なるアイテムを整列させて、ステップS41で設定されたパターン長mよりも1だけ長いパターンの候補(候補パターン)を生成する処理を行う(ステップS46)。
【0048】
すなわち、ステップS46で候補パターン生成部40は、取り出された2個のパターンに共通するm−1個のアイテムに対して、相互に異なる最後の2つのアイテムを、アイテムの順序を守るようにして並べた、(m−1+2=)m+1のパターンの長さを持つ候補パターンを1個生成する。続いて、候補パターン生成部40は、生成された候補パターンを候補頻度算出部50に提供する(ステップS47)。さらに、候補パターン生成部40は、長さm+1の候補パターンを全て生成するまでステップS45乃至ステップS48の処理を繰り返し、全て生成したと判定されるとステップS4の処理を終了する。すなわち、このようなパターンの抽出とパターンの候補の生成を繰り返し実施することにより、パターン格納部80に格納されている長さmの頻出アイテムまたはパターンから、m+1のパターンの長さを持つすべてのパターンの候補が生成される。
【0049】
以下、候補パターンの生成処理について具体例を挙げて詳述する。
【0050】
例えば、ステップS41でパターンの長さmが1に設定され、パターン格納部80には、図7に示す長さが1であるパターン(すなわち頻出アイテム)が格納されているものとする。ここで各アイテムは、上述のように「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の順で優先度が与えられていることから、パターン格納部80に格納される頻出アイテムは、「牛肉」を除いて「鶏肉」、「豚肉」、「鮪」、「鯵」、「ビール」の順で並べられている。
【0051】
このとき、図7の各パターンは、いずれも長さmが1であることから、ステップS42を経てステップS43で全て取り出される。一方、ステップS44の候補パターン生成条件については、パターンの長さmが1の場合には、共通するアイテムの個数は1個もない(すなわち0個である)ため、「前からm−1個までのパターンが同一のアイテム」であること及び「最後の1つのアイテムが異なっている」こととなり、図7の任意の2個のパターンの組合せが条件を満たすことになる。このため、候補パターン生成部40は、上述したアイテムの優先度に従って、「鶏肉、豚肉」、「鶏肉、鮪」、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、鮪」、「豚肉、鯵」、「豚肉、ビール」、「鮪、鯵」、「鮪、ビール」、「鯵、ビール」の順で2個のパターンを取り出し(ステップS45)、長さが2となる10種類のパターンの候補(2次の候補パターン)をステップS46で生成する(図10参照)。当該生成された10個の候補パターンの情報は、候補頻度算出部50に提供され、各候補パターン毎に後述するステップS5乃至ステップS9の処理が繰り返し実行される。そして、かかる10個全ての候補パターンについての処理が終了すると、ステップS9からステップS5に処理が戻される。
【0052】
ステップS5では、候補頻度算出部50が、候補パターン生成部40から提供された候補パターンの中で頻度算出の処理が完了していないものがあるかについて判定し、未だ処理が完了していないものがある場合には1つの候補パターンを取り出してステップS6に進み、全ての候補パターンの頻度算出処理が完了している場合には、本装置の処理を候補パターン生成に関するステップS4へと戻す。
【0053】
以下のステップS6からステップS10までは、取り出された1つの候補パターンに対する処理である。まず、ステップS6では、候補頻度算出部50が、ステップS1で読み込まれているトランザクションの集合を参照することにより、取り出した1つのパターンの候補に対して、当該候補の出現頻度すなわち当該候補パターンを含むトランザクションの個数を算出する。
【0054】
例えば、図2に示すトランザクションの集合がステップS1で読み込まれ、ステップS4で設定されたパターンの長さmが2であり、ステップS6でパターンの候補として「鶏肉、豚肉」が取り出されている場合、当該パターンの候補はA02及びA03のトランザクションに含まれているため、その出現頻度として2が算出される(図10参照)。同様に、他の候補パターンである「鶏肉、鮪」、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、鮪」、「豚肉、鯵」、「豚肉、ビール」、「鮪、鯵」、「鮪、ビール」、「鯵、ビール」に関しては、それぞれの出現頻度が、3、2、3、1、0、2、2、2、1と算出される。
【0055】
ステップS7では、候補評価値算出部60が、ステップS6で算出された候補パターンの出現頻度と、ステップS2で読み込まれたアイテム間知識(関連度行列テーブル)を用いて、当該パターンを構成するアイテム間の関連性を評価することにより、その頻度が低い程小さく、関連性の高いアイテムによってパターンが構成されている程小さくなる抽出評価値(以下、「関連性支持度」と称する。)を算出する。
【0056】
詳細には、図9のフローチャートに示すように、候補評価値算出部60は、ステップ6で算出された出現頻度から当該候補パターンの支持度を算出する(ステップS71)。ここで、候補パターンの支持度の算出は、上述した数式1と同様であり、かかる数式の「アイテムを含むトランザクションの個数」を「パターンを含むトランザクションの個数」と読み替えればよい。ステップS72で、候補評価値算出部60は、当該候補パターンに含まれる2個のアイテムの組合せを全て抽出する。ステップS73で、候補評価値算出部60は、ステップS2でアイテム間情報記憶部20から読み込まれたアイテム間知識を参照(識別)して、抽出された組合せに対応する関連度を全て抽出する。続いて、候補評価値算出部60は、抽出された関連度に基づく加重値を算出し(ステップS74)、算出された加重値をステップS71で算出された支持度に適用することで、当該候補パターンの抽出評価値(関連性支持度f(p))を算出する(ステップS75)。
【0057】
ここで、上述した加重値および関連性支持度f(p)は、パターンの長さmの増大に対して、単調に減少するように定義する必要がある。より詳細には、関連性支持度f(p)は、2つのパターンあるいはパターンの候補p1及びp2に対して、p1⊆p2(p1はp2の部分集合)の関係が成立する場合、f(p1)≧f(p2)といった関係が成立するように定義する必要がある。言い換えると、候補評価値算出部60は、パターンの長さmに対してトレードオフの関係が成り立つように加重値を算出する必要がある。
【0058】
このような加重値および関連性支持度の定義や算出式には多様なものが考えられる。例えば、候補評価値算出部60が算出する加重値の定義として、抽出された関連度を所定値(例えば1)から減じて得られる値を加重値とすることができる。あるいは、候補評価値算出部60が算出する加重値の定義の例として、抽出された関連度と加重値との合計値を一定(例えば1)に保持したまま、当該合計値と抽出された関連度との差分値を、加重値とすることができる。
【0059】
本実施形態では、候補評価値算出部60が算出する加重値及び関連度支持度として、下記数式2に示すように関連性支持度f(p)を定義する。
【0060】
【数2】
【0061】
ただし、数式2の第1項において、s(iti,itj)は、アイテムitiとアイテムitjとの関連度を表す。また、max{s(iti,itj)}は、パターンを構成する全てのアイテム(iti,itj)間の関連度の内の最大値である。
【0062】
数式2において、加重値である第1項は、パターンを構成する任意のアイテム間の関連度の最大値(max)を用いており、かかる関連度の最大値を定数1から減算している。このため、加重値である第1項は、パターンの長さmが増大すると、アイテム間の関連度の最大値が単調に増加し、定数1からかかる最大値を減算することで、単調に減少する値が得られることになる。また、数式2の第2項は、分母(トランザクションの総数)の値が固定値である一方、分子の値がパターンの長さmの増大に伴って単調に減少する。このため、第1項に第2項を掛けて定数倍した関連性支持度f(p)は、パターンの長さmの増大に対して、単調に減少するといえる。
【0063】
例えば、パターンの長さmが2である「鶏肉、豚肉」の場合、「鶏肉」と「豚肉」の関連度は図3に示すように0.5と設定されている。このため、加重値である数式2の第1項の値は(1−0.5=)0.5が算出される。また、上述のように、「鶏肉、豚肉」の頻度は2と算出される。このため、「鶏肉、豚肉」の関連性支持度f(p)は、(0.5×2/5×100=)20%と算出される。一方、同じくパターンの長さmが2である「鶏肉、鮪」の場合、「鶏肉」と「鮪」の関連度は0と設定されているので、数式2の第1項の値は(1−0=)1が算出される。このため、ステップS7で、候補評価値算出部60は、「鶏肉、鮪」の関連性支持度f(p)として、(1×3/5×100=)60%を算出する(ステップS75)。同様に、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、鮪」、「豚肉、鯵」、「豚肉、ビール」、「鮪、鯵」、「鮪、ビール」、「鯵、ビール」の関連性支持度は、図10の関連性支持度の欄に示すように、各々、40%、60%、20%、0%、40%、20%、40%、20%が算出される。
【0064】
ステップS8では、候補評価部70が、データ格納部10に格納されている最小支持度の値と、算出された候補パターンの関連性支持度f(p)の値とを比較して、当該関連性支持度f(p)の値が閾値である最小支持度の値を満たすか否かを判定する。このとき、候補評価部70は、当該候補の関連性支持度f(p)が最小支持度(本例では40%)以上の場合に、当該候補パターンを「パターン」すなわちアイテムの特徴的な組合せを有するものとして登録するために、ステップS9に処理を移行する。一方、関連性支持度が最小支持度未満の場合には、当該候補をパターン格納部80に登録することなくステップS5に処理を戻し、次の候補パターンについての処理を行なう。
【0065】
ステップS9では、候補評価部70が登録すると判定したパターンの候補を、アイテムの特徴的な組合せを有するパターンとして、パターン格納部80に格納する。例えば、図10に示すように、パターンの長さが2となる候補パターンに対して関連性支持度が算出された場合、本例ではデータ格納部10に格納されている最小支持度が40%であるため、図10に示す10個の候補パターンの内、「鶏肉、鮪」、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、ビール」、「鮪、ビール」の候補パターンに対しては、ステップS8で基準値を満たすと判定され、当該5つのパターンが、パターンとして図11に示すようにパターン格納部80に登録される。一方、「鶏肉、豚肉」、「豚肉、鮪」、「豚肉、鯵」、「鮪、鯵」、「鯵、ビール」の候補パターンに対しては、ステップS8で基準値を満たさないと判定され、パターン格納部80に格納されず、当該候補パターンのデータが廃棄される。このため、「鶏肉、豚肉」、「豚肉、鮪」、「豚肉、鯵」、「鮪、鯵」、「鯵、ビール」の候補パターンは、長さ3の候補パターン生成の対象から除外される。
【0066】
そして、本例では、図10に示す10個の2次候補パターンの全てについてステップS6乃至ステップS9の処理が完了すると、ステップS5を経てステップS4に処理が戻され、長さ3の3次候補パターンの生成が開始される。
【0067】
すなわち、パターン格納部80には、図7に示す頻出アイテムの他に、図11に示すように、長さ2のパターン(2次のパターン)が、上述したアイテムの優先度に従って、「鶏肉、鮪」、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、ビール」、「鮪、ビール」の順序で格納されている。この状態から、ステップS41で、候補パターン生成部40は、パターンの長さmを2に設定する。
【0068】
続いて候補パターン生成部40は、ステップS42を経て、長さmが2である図11の各パターンを全て取り出し(ステップS43)、長さ2のパターンを2つ組合せるために、候補パターン生成条件の適否を判定する(ステップS44)。
【0069】
ステップS44の候補パターン生成条件について、長さmが2の場合には、共通するアイテムの個数が最大で1となるため、「鶏肉、鮪」と「鶏肉、鯵」は、「前方のm−1個のパターン」換言すると「最初のアイテム」である「鶏肉」が共通しており、かつ最後の1個のアイテムが相互に異なるため、候補パターン生成条件を満たしている。これに対して、「鶏肉、鮪」と「豚肉、ビール」は、「前方のm−1個のパターン」すなわち「最初のアイテム」が一致しておらず、このため候補パターン生成条件を満たしていない。
【0070】
候補パターン生成部40は、このようにしてステップS44で候補パターン生成条件の適否を判定し、「鶏肉、鮪」と「鶏肉、鯵」、「鶏肉、鮪」と「鶏肉、ビール」、「鶏肉、鯵」と「鶏肉、ビール」の3組を、候補パターン生成条件を満たすものと判定し、かかる3組をステップS45で取り出す。さらに、候補パターン生成部40は、ステップS46で、長さが3となる3次の候補パターンとして、それぞれ、「鶏肉、鮪」と「鶏肉、鯵」から「鶏肉、鮪、鯵」を生成し、「鶏肉、鮪」と「鶏肉、ビール」から「鶏肉、鮪、ビール」を生成し、「鶏肉、鯵」と「鶏肉、ビール」から「鶏肉、鯵、ビール」を生成する(図12参照)。当該生成された「鶏肉、鮪、鯵」、「鶏肉、鮪、ビール」、「鶏肉、鯵、ビール」の3個の候補パターンの情報は、候補頻度算出部50に提供され、各候補パターン毎に上述したステップS5乃至ステップS9の処理が繰り返し実行される。そして、これら3個全ての候補パターンについての処理が終了すると、ステップS9からステップS5に処理が戻される。
【0071】
詳細には、ステップS5で、候補頻度算出部50は、候補パターン生成部40から提供された候補パターンから未処理の1つの候補パターン「鶏肉、鮪、鯵」を取り出してステップS6の頻度算出処理を行う。この場合、「鶏肉、鮪、鯵」はトランザクションA01及びA05に含まれているため、候補頻度算出部50によって頻度「2」が算出され(ステップS6)、候補評価値算出部60によって支持度40(%)が算出される(ステップS71)。
【0072】
続いて、候補評価値算出部60は、候補パターン「鶏肉、鮪、鯵」から2個のアイテムの全ての組合わせとして、「鶏肉、鮪」、「鶏肉、鯵」、「鮪、鯵」を抽出し(ステップS72)、かかる組合わせに対応する関連度として、0、0、0.5を抽出し(ステップS73)、抽出された関連度から、上述した数式2の第1項の加重値として、(1−max{0, 0, 0.5})すなわち(1−0.5=)0.5を算出する(ステップS74)。また、「鶏肉、鮪、鯵」の支持度として「40」が算出されているので、候補評価値算出部60は、ステップS75で、「鶏肉、鯵、鮪」の関連性支持度f(p)として、(0.5×40=)20%を算出する(図12参照)。この場合、関連性支持度が最小支持度(40%)未満であり(ステップS8でNO)、パターンとして登録することなくステップS5に処理が戻される。
【0073】
続いて、ステップS5で、候補頻度算出部50は、候補パターン生成部40から提供された長さ3の候補パターンからの中で未処理の1つの候補パターン「鶏肉、鮪、ビール」を取り出してステップS6の頻度算出処理を行う。この場合、「鶏肉、鮪、ビール」はトランザクションA01及びA03に含まれているため、候補頻度算出部50によって頻度「2」が算出され(ステップS6)、候補評価値算出部60によって支持度40(%)が算出される(ステップS71)。
【0074】
続いて、候補評価値算出部60は、候補パターン「鶏肉、鮪、ビール」から2個のアイテムの全ての組合わせとして、「鶏肉、鮪」、「鶏肉、ビール」、「鮪、ビール」を抽出し(ステップS72)、かかる組合わせに対応する関連度として、0、0、0を抽出し(ステップS73)、抽出された関連度から、上述した数式2の第1項の加重値として、(1−max{0, 0, 0})すなわち(1−0=)1を算出する(ステップS74)。また、「鶏肉、鮪、ビール」の支持度として「40」が算出されているので、候補評価値算出部60は、ステップS75で、「鶏肉、鮪、ビール」の関連性支持度f(p)として、(1×40=)40%を算出する(図12参照)。この場合、関連性支持度が閾値の最小支持度(40%)以上であるため、「鶏肉、鮪、ビール」の候補パターンは、「パターン」すなわち「アイテムの特徴的な組合せを有するもの」として、ステップS9でパターン格納部80に格納される(図13参照)。
【0075】
さらに、ステップS5で、候補頻度算出部50は、候補パターン生成部40から提供された候補パターンからの中で未処理の1つの候補パターン「鶏肉、鯵、ビール」を取り出してステップS6の頻度算出処理を行う。この場合、「鶏肉、鯵、ビール」はトランザクションA01のみに含まれているため、候補頻度算出部50によって頻度「1」が算出され(ステップS6)、候補評価値算出部60によって支持度20(%)が算出される(ステップS71)。
【0076】
続いて、候補評価値算出部60は、候補パターン「鶏肉、鯵、ビール」から2個のアイテムの全ての組合わせとして、「鶏肉、鯵」、「鶏肉、ビール」、「鯵、ビール」を抽出し(ステップS72)、かかる組合わせに対応する関連度として、0、0、0を抽出し(ステップS73)、抽出された関連度から、上述した数式2の第1項の加重値として、(1−max{0, 0, 0})すなわち(1−0=)1を算出する(ステップS74)。また、「鶏肉、鯵、ビール」の支持度として「20」が算出されているので、候補評価値算出部60は、ステップS75で、「鶏肉、鯵、ビール」の関連性支持度f(p)として、(1×20=)20%を算出する(図12参照)。この場合、関連性支持度が最小支持度(40%)未満であり(ステップS8でNO)、パターンとして登録することなくステップS5に処理が戻される。
【0077】
そして、本例では、図12に示す3個の3次候補パターンの全てについてステップS6乃至ステップS9の処理が完了すると、ステップS5を経てステップS4に処理が戻される。この場合、パターンの長さmが3に設定されるが(ステップS41)、パターン格納部80には、図13に示すように長さmが3のパターンが1個しか格納されていないために、候補パターン生成条件を満たすパターンの組合せを取り出して長さ4の候補パターンを生成することができない(ステップS42でNO)。したがって、この場合は、候補パターン生成部40によるステップS45での候補パターンの生成が出来ないものとして、本装置における処理を終了する。
【0078】
以上のように、パターンの長さが3の場合においては、図13に示すように、3つの候補パターンの内の「鶏肉、鮪、ビール」のみがパターンとして抽出され、パターン格納部80に登録されることになる。すなわち、頻度が同じ「2」であっても関連度の高いアイテムが含まれている「鶏肉、鯵、鮪」については、加重値ひいては抽出評価値(関連性支持度)が相対的に低く算出され、抽出対象とならない。また、関連度の低いアイテムのみで構成された「鶏肉、鯵、ビール」についても、頻度が低いために関連性支持度が低く算出され、やはり抽出対象とならない。
【0079】
また、上述した例で示したように、長さ2の候補パターン「鶏肉、鯵」、「鶏肉、ビール」、「鯵、ビール」の関連性支持度f(p)は、それぞれ、40%、60%、20%となり(図10参照)、かかる3つの候補パターンを含む長さ3の候補パターン「鶏肉、鯵、ビール」の関連性支持度f(p)は20%となる(図12参照)。従って、数式2を用いた候補評価値算出部60の演算結果によれば、パターンの長さの増大に伴って、抽出評価値である関連性支持度が単調に減少することを確認することができる。
【0080】
上述のように、本実施形態のパターン抽出装置100は、候補パターンに対する抽出評価値を算出する際にアイテム間の関連性を考慮し、関連性が高いアイテムを含む候補パターンの加重値を相対的に小さい値となるように算出することにより、関連性が高いアイテムを含む候補パターンが相対的に抽出されにくくなり、分析者にとって自明と思われる、相互に関連性の高いアイテムで構成されたパターンが抽出されることを防止することができ、分析者の興味を惹くと考えられる、相互に関連性の低いアイテムで構成されたパターンを効率良く抽出することができる。
【0081】
より具体的には、アイテム間の関連性を考慮せずに、単に最小支持度に基づいてパターンを抽出した場合には、図2のトランザクションから、出現頻度が2である候補パターン、すなわち肉類同士である「鶏肉、豚肉」や魚類同士である「鯵、鮪」もパターンとして抽出されることになる。このような相互に関連性の高いアイテムで構成されたパターンは、分析者にとって、自明(当たり前)との印象が強いものであり、興味を惹くパターンとならない。これに対して、本実施形態のパターン抽出装置100の抽出制御では、候補パターン中、ある程度出現頻度があり且つ関連性の低いアイテムで構成されたものが抽出対象となるので、上述の「鶏肉、豚肉」や「鯵、鮪」がパターンとして抽出されることを回避することができる。
【0082】
さらに、本実施形態で説明した対象情報としてのトランザクションは、説明の簡明化のため、極めて小規模な構造のものを例示したが、実際には、より多くのアイテムの種類を扱うとともに、大量のトランザクションが対象とされ得る。このため、アイテム間の関連性を考慮せずに、単に最小支持度に基づいてパターンを抽出した場合には、相互に関連性の高いアイテムで構成されたパターンが多数抽出される可能性があり、「豚肉、鯵」といったようなカテゴリの異なる商品(アイテム)で構成されたパターンが、多くの同種の商品のパターンの中に埋もれてしまう虞がある。したがって、アイテム間の関連性を考慮せずに、最小支持度に基づいてパターンを抽出した場合には、分析者の興味を惹くパターンを効率的に発見することが著しく困難であると考えられる。
【0083】
これに対し、本実施形態のパターン抽出制御では、上述のように、アイテム間の関連性を考慮し、候補パターンに含まれる各アイテム間の関連度をアイテム間情報記憶部20から抽出し、抽出された関連度に基づいて加重値を算出し、かかる加重値を当該候補パターンのトランザクション中の出現頻度に基づく支持度に適用して抽出評価値を算出するために、関連性の高くないアイテムで構成されたパターンを効率良く抽出することが可能となる。従って、本実施形態のパターン抽出装置100によれば、分析者の興味を惹く重要なパターンを、効率的に発見することが可能になる。
【0084】
なお、パターン抽出装置の構成は、上述した実施形態に限定されるものではない。例えば、抽出評価値である関連性支持度の算出方法として、数式2を採用したが、単調性を満たすような関連性支持度の定義式としては、下記の数式3、数式4に示すように、その定義を与えることもできる。
【0085】
【数3】
【0086】
【数4】
【0087】
ここで、数式3を用いた場合には、加重値となる第1項でアイテム同士の関連度を加算し、該加算値が1以上になると、第1項ひいては当該関連性支持度f(p)の値が0になる。したがって、数式3も、パターンの長さ(アイテム構成数の増大)に対して単調に減少する定義であることがわかる。
【0088】
一方、数式4を用いた場合には、加重値となる第1項はアイテム同士の関連度のかけ算をするので、実施形態の関連度行列の値をそのまま使うと、例えば「鶏肉」と「ビール」の場合に第1項ひいては当該関連性支持度f(p)の値が0になる。したがって、この場合には、アイテム間知識の他の実施形態として、同じアイテム同士の関連度を0とし、関連性が最も低いアイテム同士の関連度を1に設定すればよい。
【0089】
また、上述した実施形態では、アイテム抽出部30によるステップS37の判定で、パターン格納部80に頻出アイテムが存在しない場合には本装置の処理を終了することとしたが、これに限定されず、ステップS37で頻出アイテムが存在しないと判定された場合に、アイテム抽出部30が最小支持度の値(上記例では40%)から所定の値(例えば20%)だけ減算する処理を行い、該減算後の最小支持度以上の支持度のアイテムを頻出アイテムとして抽出するように、頻出アイテム抽出(ステップS3)の処理を再度やり直すこととしてもよい。この場合には、最小支持度の値を減少させて算出した旨及び算出に用いた最小支持度の値を表示部に適宜表示して分析者に知らせるようにすることが好ましい。
【0090】
さらに、上述とは逆に、抽出されパターン格納部80に格納された頻出アイテムが非常に多い場合、例えば、抽出対象となった頻出アイテムが、予め設定された所定数以上の場合、或いはステップS31で抽出されたアイテムの内の予め設定された所定割合(%)以上のアイテムが頻出アイテムとして格納された場合に、アイテム抽出部30が最小支持度の値を所定の値(例えば20%)だけ増加させる処理を行って、該変更後の最小支持度以上の支持度のアイテムを頻出アイテムとして抽出するように、再度ステップS3の処理をやり直すこととしてもよい。この場合にも、最小支持度の値を増加させて算出した旨及び算出に用いた最小支持度の値を表示部に適宜表示して分析者に知らせるようにすることが好ましい。
【0091】
さらにまた、長さ2以上の候補パターンに関する最小支持値についても同様の処理を行うことができる。図14は、パターン抽出装置の他の実施形態の動作を説明するためのフローチャートであり、ステップS5で未処理の候補が無いと判定された場合に、ステップS51でパターン格納部80内のパターンの有無を判別し、パターンがある場合にはステップS4に戻り、一方、無い場合にはステップS52で最小支持度の値(上記例では40%)から所定の値(例えば20%)だけ減算する処理を行い、該変更後の最小支持度でステップS8の判定処理を候補パターン毎に再度行う。
【0092】
さらに、パターン格納部80に格納されたパターンの個数が、予め定められた数未満(過少)の場合、または、予め定められた数を超える(過大の)場合に、最小支持度の値を減少させる処理、または、最小支持度の値を増加させる処理を行って、ステップS8の判定処理を候補パターン毎に再度行うこととしてもよい。
【0093】
また、上述の実施形態ではアイテム間情報格納部20に記憶するアイテム間知識として、2つのアイテム間の関係に対して関連度を定義していたが、これに限定されず、アイテム間知識は、アイテムの増大に対して単調性を保持するように与えることにより、3つ以上のアイテムに対して関連度を定義することもできる。
【0094】
また、上述の実施形態では、日用品の販売における、購入商品の特徴的な組合せの発見のためにパターン抽出装置100を使用する場合について例示して説明したが、これに限定されず、他の多様な業務に使用することができる。例えば、銀行業務における、店舗の特性と事務ミスの種類との間にある特徴的な因果関係の発見に使用する場合の一例として、店舗毎に1個のトランザクションを使用し、当該店舗で発生したミスの種類をアイテムとして使用することができる。また、番組推薦における、視聴者特性と視聴履歴との間にある視聴者の嗜好の発見などの分野に利用する場合の一例として、視聴者毎に1個のトランザクションを使用し、当該視聴者が視聴した番組をアイテムとして使用することができる。
【0095】
上述した各処理は、コンピュータで実行可能なプログラムとして実現することが可能であり、当該プログラムがインストールされたコンピュータは、実施形態に係る各処理を遂行する情報処理装置として動作することが可能である。例えば、不図示の補助記憶装置に当該プログラムが格納され、CPU等の制御部が補助記憶装置に格納されたプログラムを主記憶装置に読み出し、主記憶装置に読み出された該プログラムを制御部が実行し、コンピュータに実施形態に係る各処理を動作させることができる。
【0096】
また、上記プログラムは、コンピュータ読取可能な記録媒体に記録された状態で、コンピュータに適用することも可能であり、インターネット等のネットワークを通じてコンピュータにダウンロードすることも可能である。コンピュータ読取可能な記録媒体としては、CD−ROM等の光ディスク、DVD−ROM等の相変化型光ディスク、MO(Magnet Optical)やMD(Mini Disk)などの光磁気ディスク、フロッピー(登録商標)ディスクやリムーバブルハードディスクなどの磁気ディスク、コンパクトフラッシュ(登録商標)、スマートメディア、SDメモリカード、メモリスティック等のメモリカードが挙げられる。また、特別に設計されて構成された集積回路(ICチップ等)等のハードウェア装置も記録媒体として含まれる。
【0097】
また、上述の実施形態では、図1に示した各部を1台のコンピュータで構成したが、これに限定されず、図1に示した各部を適宜異なるサーバ装置等で実現し、ネットワーク等の通信回線を介して接続したコンピュータシステムとして構成することもできる。
【0098】
なお、本発明の実施形態を説明したが、当該実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。この新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【0099】
100 パターン抽出装置
10 データ格納部
20 アイテム間情報記憶部
30 アイテム抽出部
40 候補パターン生成部
50 候補頻度算出部
60 候補評価値算出部
70 候補評価部
80 パターン格納部
【技術分野】
【0001】
本発明の実施形態は、複数のアイテムを含む対象情報からアイテムの組合せパターンを抽出する制御に関する。
【背景技術】
【0002】
従来から各種の活動や事象などを分析するために、複数のアイテムで構成された対象情報から、分析目的等に応じた特定のパターンすなわちアイテムの組合せを、効率良く抽出するための装置や方法が研究されている。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2003−76937号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
アイテムを含む複数の対象情報から、アイテム間の関連性を反映させて、特定のパターンを抽出させるパターン抽出装置及び方法を提供する。
【課題を解決するための手段】
【0005】
実施形態のパターン抽出装置は、複数のアイテムを含む対象情報内に存在する相互に異なる2以上のアイテムの組合せのパターンを抽出するパターン抽出装置であって、複数の対象情報を記憶する第1記憶部と、複数の対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成する候補パターン生成部と、生成された候補パターンが複数の対象情報それぞれに出現する出現頻度に基づいて、候補パターンの抽出評価値を算出する候補評価値算出部と、算出された抽出評価値が所定の閾値を満たす候補パターンを判別し、閾値を満たす候補パターンを抽出するパターン抽出部と、を含むとともに、アイテム間の関連度を記憶する第2記憶部をさらに含む。候補評価値算出部は、候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び出現頻度に基づいて、抽出評価値を算出する。
【図面の簡単な説明】
【0006】
【図1】第1実施形態のパターン抽出装置の構成例を示す図であり、本装置を構成する各部間の関係を示すブロック図である。
【図2】データ格納部に格納される対象情報としてのトランザクション群の一例を示す図である。
【図3】アイテム間情報記憶部に記憶される関連度行列テーブルの一例を示す図である。
【図4】パターン抽出装置の動作を説明するためのフローチャートである。
【図5】アイテム抽出部が行う処理を説明するためのサブルーチンである。
【図6】長さが1となる候補パターンの頻度と支持度の一例を示す図である。
【図7】パターン格納部に格納される長さ1のパターンの一例を示す図である。
【図8】候補パターン生成部が行う処理を説明するためのサブルーチンである。
【図9】候補評価値算出部が行う処理を説明するためのサブルーチンである。
【図10】長さが2となる候補パターンの頻度と関連性支持度の一例を示す図である。
【図11】パターン格納部に格納される長さ2のパターンの一例を示す図である。
【図12】長さが3となる候補パターンの頻度と関連性支持度の一例を示す図である。
【図13】パターン格納部に格納される長さ3のパターンの一例を示す図である。
【図14】パターン抽出装置の他の実施形態の動作を説明するためのフローチャートである。
【発明を実施するための形態】
【0007】
以下、実施形態につき、図面を参照して説明する。
【0008】
実施形態に係るパターン抽出装置は、複数のアイテム(情報要素)を含む対象情報が複数与えられた場合に、アイテム間に存在する関係を利用して、当該複数の対象情報の中からアイテムの特徴的な組合せ(パターン)を抽出する制御を遂行するものである。
【0009】
なお、「パターン」の用語は、通常は2以上のアイテムの組合せを意味するが、以下の説明では、単一のアイテムに対しても「パターン」の用語が用いられる場合がある。一方、「パターン」の用語は、狭義には、上記「アイテムの特徴的な組合せ」を有するパターンを意味する。そして、かかる狭義のパターンを抽出するための候補となるパターンを「パターンの候補」または「候補パターン」と称する。
【0010】
本装置は、例えば、スーパーマーケットなどの日用品の販売における、購入商品の特徴的な組合せの発見、銀行業務における、店舗の特性と事務ミスの種類との間にある特徴的な因果関係の発見、番組推薦における、視聴者特性と視聴履歴との間にある視聴者の嗜好の発見などの分野に利用することができる。但し、これらは例示であって、これに限定されるものではない。
【0011】
以下の説明では、スーパーマーケットなどの日用品(食品)の販売業における商品をアイテムとして本装置で扱う場合について説明する。具体的には、あるスーパーマーケットでの食品を販売するフロアにおいて、購入者が購入した商品(食品)の特徴的な組合せ(すなわち「パターン」)を抽出、発見するために、商品購入者の一枚のレシートを1個の対象情報(トランザクション)とし、レシートに記載された商品(食品名等の品名)をアイテムとして扱う場合について説明する。
【0012】
図1から図13は、第1実施形態を示す図である。図1は、本実施形態のパターン抽出装置100のブロック構成図であり、図中の各ブロックを結線する矢印は、データの流れる方向を示している。本装置は、複数の対象情報としてトランザクションの集合を記憶する第1記憶部としてのデータ格納部10と、アイテム間の関連性に関する情報を記憶する第2記憶部としてのアイテム間情報格納部20と、トランザクションの集合からアイテムを抽出するアイテム抽出部30と、抽出されたアイテムを用いて、相互に異なる2以上のアイテムの組合せによるパターンの候補(候補パターン)を生成する候補パターン生成部40と、候補パターンがトランザクションに出現する頻度を算出する候補頻度算出部50と、候補パターンの頻度及び前記アイテム間の関連性に関する情報を用いて、候補パターンに対する抽出評価値を算出する候補評価値算出部60と、算出された抽出評価値が基準値を満たす候補パターンをパターンとして抽出する処理を行う候補評価部70およびパターン格納部80と、を含む。
【0013】
本装置は、後述する各処理を実行するプログラムのデータを図示しないハードディスク装置などの外部記憶媒体に格納し、かかるプログラムをパーソナルコンピュータ(PC)に読み込ませることで実現することができる。この場合、例えば当該コンピュータのハードディスク装置やRAMなどの記憶デバイスがデータ格納部10、アイテム間情報格納部20、パターン格納部80として機能し、CPUなどの制御デバイスがアイテム抽出部30、候補パターン生成部40、候補頻度算出部50、候補評価値算出部60、及び候補評価部70として機能することができる。
【0014】
データ格納部10は、後述する一連の処理に先立って、対象情報であるトランザクションの集合(以下、「トランザクション群」ともいう。)のデータを記憶するトランザクション記憶部として機能するとともに、後述する最小支持度に関するデータ、及び、アイテムの整列の優先度を示すデータを格納する。
【0015】
データ格納部10に記憶される対象情報としてのトランザクション群の一例を図2に示す。トランザクションは、複数のアイテム(この例では実際に購入された商品である「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の6個すなわち6種のアイテム)の内の1種以上のアイテムで構成されたものであり、図2ではA01、A02、A03、A04、A05の5個のトランザクションがトランザクション群としてデータ格納部10の所定記憶領域に記憶(格納)された場合を例示している。
【0016】
スーパーマーケットなどの日用品の販売業を対象とした場合、購入商品の一覧が記載された1枚のレシートが1つのトランザクション(例えばA01)に相当する。ただし、この例では、レシートに記載されている商品の金額や購入個数には着目しておらず、商品が購入されたかどうかに関する情報のみに着目している。このため、データ格納部10には、図2に例示したように、商品名の情報のみをアイテムとし、購入個数が複数であっても1つの商品名が複数個存在しない形態のトランザクションのデータが格納されることになる。
【0017】
本実施形態では、データ格納部10に格納されるトランザクション群のデータ構造として、各トランザクションを識別するためのトランザクション番号(A01〜A05)と、当該トランザクションを構成するアイテムの一覧を示すアイテムリスト(この例では購入リスト)と、が対応付けられた構造となっている。A01乃至A05の各トランザクションは、購入リストに示す1又は複数種類のアイテムから構成される。すなわち、トランザクションA01では4つのアイテム(換言すると4種類の商品、以下同様)、トランザクションA02では3つのアイテム、トランザクションA03では4つのアイテム、トランザクションA04では2つのアイテム、トランザクションA05では3つのアイテムで構成されていることが分かる。各トランザクションにおいて、各々のアイテムは、カンマ等の所定の記号で区切られることにより識別される。ここでは簡明のため、トランザクション群を構成する全てのトランザクションが複数のアイテムからなる場合を説明するが、1つ以上のアイテムがあればトランザクションとして成立し得る。
【0018】
また、データ格納部10に格納される最小支持度に関するデータは、分析者等により予め設定される数値データであり、本実施形態では、かかる数値は、後述する頻出アイテムを抽出するための基準値(閾値)であるとともに、複数のアイテムで構成された候補パターンから特徴的なパターンを抽出するための基準値(閾値)としても使用される。かかる最小支持度の数値データは、図示しないマウスやキーボードなどの操作入力部の操作により、処理に先立って、使用されるトランザクション群を構成するトランザクションの数やアイテムの構成等に応じて任意に設定、変更等することができる。
【0019】
以下は最小支持度の数値を40%とした場合について説明するが、この値に限定されるものではない。また、以下は最小支持度の数値を予め一律40%に設定とした場合について説明するが、パターンの次数ないし長さ(すなわち当該パターンが構成されるアイテムの個数)毎に異なる数値を予め設定することもできる。
【0020】
さらに、データ格納部10に格納されるアイテムの整列の優先度を示すデータは、後述する候補パターン生成の際に参照されるものであり、本例では、優先度の高い方から「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の順となっている。このデータも、処理に先立って、図示しないマウスやキーボードなどの操作入力部の操作により、任意に設定、変更等することができる。本実施形態の優先度は、パターンを構成する複数のアイテムの整列順を規定する情報であり、例えば、品目のカテゴリ順、カテゴリ内の品目順、辞書や「あいうえお」順等の一定のルールに基づいて複数のアイテムを整列させるためのものである。当該優先度を用いることで、例えば、候補パターンの生成処理を円滑かつ迅速に行うことができる。
【0021】
アイテム間情報格納部20は、後述する一連の処理に先立って、使用されるトランザクション群を構成する各アイテム間の関連性に関する情報(以下「アイテム間知識」ともいう。)のデータを記憶する。アイテム間知識のデータは、各アイテム相互間(同一アイテム間をも含む)の関連度のデータ、より詳細には、関連度の高低を示す数値データであり、本実施形態では、アイテム間の関連度が高いほど大きな数値となる。
【0022】
アイテム間情報格納部20に記憶されるアイテム間知識の一例を図3に示す。本例では、アイテム間知識として、トランザクション群中に存在する各アイテムを行列形式で配置したデータテーブルを使用している。ここで、アイテム間知識は、アイテムとアイテムとの間にどの程度の関係があるかを、0から1までの範囲の数値によって示したものであり、以下は、当該数値を「関連度」と称する。ここで、関連度は、アイテム間の関係が強い(関連度が高い)程その値が大きくなり、関係が弱い(関連度が低い)程その値が小さくなるように定義される。また、同一のアイテムに対する関連度は、最大値の1が与えられる。かかる関連度の具体的な数値は、図示しないマウスやキーボードなどの操作入力部の操作により、処理に先立って、処理対象となるトランザクションのアイテムの上位概念となるカテゴリの数やカテゴリの構造などに応じて、分析者らが任意に設定、変更等することができる。
【0023】
図3の例では、アイテム間情報格納部20に記憶されるアイテム間知識として、トランザクション群中に存在するn個の各アイテムを行(i)方向及び列(j)方向に整列し、2つのアイテム間の関係を数値で表した行列(以下、この行列を「関連度行列」とも称する。)形式により各アイテム同士の関連度の値を登録する関連度行列テーブルが用いられる。この関連度行列テーブルでは、1を最大値として、アイテム同士の関連度が高くなるほど大きな値が登録される。具体的には、同一のアイテム間(「鶏肉」と「鶏肉」、「豚肉」と「豚肉」など)には最大値である1が登録され、異なるアイテム同士(「鶏肉」と「豚肉」、「鶏肉」と「ビール」など)には、アイテム間の関係の強さに応じた値が登録される。この例では、アイテムの属するカテゴリが同じである場合、すなわち肉類同士(「鶏肉」と「豚肉」、「鶏肉」と「牛肉」、「豚肉」と「牛肉」)の場合、魚類同士(「鮪」と「鯵」)の場合には中程度の関連度として0.5の値が登録される。一方、アイテムの属するカテゴリが異なる場合、すなわち上記肉類に属するアイテムと、魚類に属するアイテムと、飲料品のカテゴリに属するアイテムであるビールと、の間には関連がないものとして0の値が登録される。
【0024】
なお、本実施形態において、「アイテム間知識」は、パターン(組合せ)として抽出したくないアイテム間の関連性の値と言い換えることもできる。すなわち、同じアイテム同士の組合せ(「鶏肉」と「鶏肉」、「豚肉」と「豚肉」など)は、分析時にパターンとして抽出しないように最大値(本例では1)が設定され、カテゴリが同じアイテムの組合せ(例えば「鶏肉」と「豚肉」)は、分析時にパターンとしてやや抽出しにくいような値(本例では0.5)が設定され、さらに、カテゴリが大きく異なるアイテムの組合せ(例えば「鶏肉」と「ビール」)は、分析時にパターンとしてより抽出されやすいような値(本例では0)が設定されることになる。
【0025】
アイテム抽出部30は、データ格納部10に格納されたトランザクション群のデータを読み出し、読み出されたデータから頻出するアイテムを抽出する処理を行う。具体的には、アイテム抽出部30は、データ格納部10から各トランザクション毎に構成するアイテムを抽出し、抽出されたアイテム毎に、その出現頻度すなわちアイテムが出現するトランザクションの個数(以下「アイテム頻度」ともいう)を算出する。算出されたアイテム頻度の情報は、アイテム抽出部30から候補パターン生成部40に渡される。さらに、アイテム抽出部30は、算出されたアイテム頻度に基づいて、当該アイテムに対する支持度を算出し、該算出値が上述したデータ格納部10に予め設定されている最小支持度(この例では40%)以上となるアイテムのみを、頻出アイテムとしてパターン格納部80に格納する。
【0026】
ここで、任意の1つのアイテム(it)に対する支持度の具体的な算出方法は、下記の数式1に従う。
【0027】
【数1】
【0028】
候補パターン生成部40は、トランザクション群を参照しつつ、アイテムの集合で構成されたパターンの候補を生成する。具体的には、候補パターン生成部40は、後述するパターン格納部80に格納された長さmのパターン(m=1の上述した頻出アイテム又は後述する高次(mは2以上)のパターン)を読み込み、データ格納部10内のトランザクション群を参照しながら、頻出アイテムまたはパターンから、所定条件を満たす長さm+1のパターンの候補(候補パターン)を生成する。候補パターン生成部40が作成する候補パターンには、頻出アイテムを2個ずつ並べた2次パターン(図10参照)、長さが2以上のパターン(図11参照)に対して当該パターンに含まれるアイテムのうち所定条件を満たすアイテムを加えた3次以上のパターン(図12参照)があり、かかる所定条件及び候補パターン生成部40が行う処理の詳細については後述する。
【0029】
また、パターン格納部80に格納された高次のパターンは、トランザクション群中の複数のトランザクションに出現する長さが2以上(2次以上)のパターンの内、アイテムの特徴的な組合せを有するものとして抽出、格納されたものであり、かかる抽出、格納の処理の詳細については後述する。
【0030】
候補頻度算出部50は、候補パターン生成部40により生成された候補パターンのトランザクション群中に出現する出現頻度(トランザクションの数)を、候補パターン毎に算出し、該算出された候補パターン毎の頻度の値を候補評価値算出部60に渡す。
【0031】
候補評価値算出部60は、候補頻度算出部50からの候補パターン毎の出現頻度の値と、上述したアイテム間知識(関連度行列テーブル)とを用いて、候補パターンに対する評価値として、当該パターンを構成するアイテム数の増大に対して単調に減少するように、アイテム間の関連性を反映させた評価値(抽出評価値)を算出する。以下、かかる評価値を「関連性支持度」と称する。候補評価値算出部60は、候補パターン毎に関連性支持度を算出し、該算出された関連性支持度の値を候補評価部70に渡す。
【0032】
候補評価部70は、候補評価値算出部60からの関連性支持度の値が所定の基準値を満たすか否かを候補パターン毎に判定し、かかる基準値を満たすと判定された候補パターンのデータをパターン格納部80に格納する。本実施形態では、候補評価部70は、データ格納部10に設定された最小支持値を参照して、当該候補パターンの関連性支持度の値が最小支持値(本例では40%)以上であるか否かを判定し、最小支持値以上の候補パターンのデータをパターン格納部80に格納する処理を行う。かかる処理により、候補パターンの内の「パターン」すなわちアイテムの特徴的な組合せを有するものが抽出され、パターン格納部80の記憶領域に保存される。
【0033】
パターン格納部80は、アイテム抽出部30または候補評価部70により頻出アイテムまたはパターンのデータが格納されると、当該データが格納された旨を候補パターン生成部40に通知し、格納されたパターンのデータを候補パターン生成部40に提供する。また、パターン格納部80に格納された頻出アイテムまたはパターンのデータは、格納に伴って自動で或いはユーザの操作入力部の操作により、適宜、図示しないLCDなどの表示部に表示したり不図示のプリンタなどで印字出力することができる。
【0034】
以下、フローチャートを参照して、パターン抽出装置100の詳細な処理内容について説明する。
【0035】
本実施形態のパターン抽出装置100は、図4のフローチャートのステップS1から処理を開始する。ステップS1では、アイテム抽出部30が、データ格納部10に格納されているトランザクション群の読み込みを行なう。かかる処理により、上述のトランザクションを構成するアイテムのデータが、各トランザクション番号毎にCPUの作業領域(RAM)に読み込まれる。図2の例では、トランザクションA01のアイテムとして「鶏肉」、「鮪」、「鯵」、「ビール」のデータが、トランザクションA02のアイテムとして「鶏肉」、「豚肉」、「ビール」のデータが、トランザクションA03のアイテムとして「鶏肉」、「豚肉」、「鮪」、「ビール」のデータが、トランザクションA04のアイテムとして「牛肉」、「鯵」のデータが、トランザクションA05のアイテムとして「鶏肉」、「鮪」、「鯵」のデータが、それぞれ読み込まれる。
【0036】
ステップS2では、候補評価値算出部60が、アイテム間情報格納部20に格納されているアイテム間知識の読み込みを行なう。かかる処理によって、図3で上述した関連度行列テーブルに登録された各アイテム間の数値データがCPUの作業領域(RAM)に読み込まれる。読み込まれた数値データは、後述する抽出評価値算出の処理で使用されることになる。
【0037】
続くステップS3では、アイテム抽出部30が図5のサブルーチンに従って、出現頻度の高いアイテム(頻出アイテム)の抽出及び格納の処理を行う。まず、アイテム抽出部30は、ステップS2で読み込まれたトランザクションの集合をサーチすることにより、トランザクションを構成するアイテムの種類をすべて抽出する(ステップS31)。例えば、図2のトランザクションの集合の場合、アイテム抽出部30は、「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の6種類のアイテムを抽出する。本実施形態では、抽出されたアイテムは、候補アイテムとして扱われ、換言すると、特徴的なパターンの候補となり得る1次(長さ1)の候補パターンとして扱われる(図6参照)。
【0038】
次に、アイテム抽出部30は、取り出された各アイテムに対して、アイテムごとに、以下のステップS32乃至ステップS35の処理を行う。まず、アイテム抽出部30は、取り出された各アイテムの内、1つのアイテムについて、ステップS2で読み込まれたトランザクション群を参照して、当該アイテムが出現するトランザクションの個数をアイテム頻度として算出する(ステップS32)。例えば、図2のトランザクション群の場合、アイテム「鶏肉」は、トランザクションA01、A02、A03、A05に含まれているため、「鶏肉」の頻度として「4」が算出される。
【0039】
次に、アイテム抽出部30は、算出された当該アイテムの頻度に基づいて、上述した数式1によりアイテムに対する支持度を算出し(ステップS33)、その値がデータ格納部10に予め設定されている最小支持度以上となるか否かを判定する(ステップS34)。例えば、頻度が4と算出された上述のアイテム「鶏肉」の場合、トランザクションの総数が5であるため、その支持度は(4/5×100=)80%となる。
【0040】
このとき、アイテム抽出部30は、算出されたアイテムの支持度がデータ格納部10に格納されている最小支持度(本例では40%)以上となる場合には、ステップS35で当該アイテムを頻出アイテムとしてパターン格納部80に格納してステップS36に移行する。一方、アイテム抽出部30は、算出されたアイテムの支持度が最小支持度(40%)に満たない場合には、当該アイテムをパターン格納部80に格納せずに、パターンの対象から除外(当該アイテムのデータを廃棄)してステップS36に移行する。ステップS36で、アイテム抽出部30は、ステップS31で抽出された全てのアイテムについての処理が完了したか否かを判定し、未だ処理が完了していない場合にはステップS32に戻って上述したステップS32乃至ステップS35の処理を繰り返し、一方、全てのアイテムについての処理が完了した場合にはステップS37に移行する。
【0041】
従って、支持度が80%と算出された上述のアイテム「鶏肉」の場合、最小支持度(40%)以上であるため(ステップS34でYES)、頻出アイテムとしてパターン格納部80に格納される。同様にして、他のアイテム「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」についても、アイテム抽出部30によって、頻度が各々「2」、「1」、「3」、「3」、「3」と算出され(ステップS32)、支持度は各々「40%」、「20%」、「60%」、「60%」、「60%」と算出され(ステップS33)、図6に示すように、長さ1の候補パターンとして各アイテムの頻度と支持度が算出される。そして、本例では最小支持度が40%に設定されているので、最小支持度に満たないアイテム「牛肉」だけがパターンの対象から除外され(ステップS34でNO)、図7に示すように、「牛肉」を除く、「鶏肉」、「豚肉」、「鮪」、「鯵」、「ビール」が、頻出アイテムとしてパターン格納部80に格納されることになる。
【0042】
ここで、後述する長さ2以上の候補パターン生成の処理のために、パターン格納部80に格納される頻出アイテムは、アイテム抽出部30がデータ格納部10の上述したアイテムの整列の優先度を示すデータを参照することにより、予め定められた順序に従って整列される。本実施形態では、図6に示すように、「鶏肉」、「豚肉」、「鮪」、「鯵」、「ビール」の優先順で各パターンが整列される。以上のように、ステップS3(ステップS31乃至ステップS36)の一連の処理を行うことにより、最小支持度に満たないアイテム(本例では「牛肉」)がパターンの候補から除外され、高次の候補パターンの要素とならなくなるので、コンピュータの処理負担が大幅に減少し、高次のパターン抽出までの時間が短縮化される。なお、本実施形態では、頻出アイテムは、パターンを構成するアイテムの数(パターンの長さ)が1となる「パターン」(すなわち特徴的な組合せ)とみなされる。
【0043】
ステップS37で、アイテム抽出部30は、パターン格納部80を参照して、頻出アイテムが存在するか否かについて判定し、存在すると判定された場合には頻出アイテムの抽出に成功したものとしてステップS4に移行し、一方、存在しないと判定された場合には頻出アイテムの抽出に失敗したものとして本装置の処理を終了する。すなわち、ステップS3の処理で頻出アイテムが1つも抽出されない場合には、本装置における処理が終了する。
【0044】
ステップS4では、候補パターン生成部40が図8のサブルーチンに従って、パターンの候補を生成する処理を行う。まず、候補パターン生成部40は、ステップS41で、パターン格納部80から取り出すパターンの長さ(mの値)を設定する。具体的には、候補パターン生成部40は、初めてステップS41を実行する場合には、パターンの長さmの値を1に設定し(m=1)、2度目以降はパターンの長さmの値に1を加算する(m=m+1)。
【0045】
次に、候補パターン生成部40は、パターン格納部80に格納されているパターン(長さ1の頻出アイテムまたは長さ2以上のパターン)の内、前ステップで設定された長さmのパターンが2個以上あるかを判定し(ステップS42)、NOすなわち0個又は1個しかないと判定された場合には、候補パターンを生成できないものとして処理を終了し、YESすなわち2個以上あると判定された場合には、該当するパターンを全て取り出し(ステップS43)、ステップS44に移行する。候補パターン生成部40は、ステップS44で、取り出された全てのパターンの内、候補パターン生成条件に合致する2つのパターンがあるかを判定し、無いと判定された場合には、候補パターンを生成できないものとして処理を終了し、あると判定された場合にはステップS45に移行する。
【0046】
本実施形態では、ステップS44の候補パターン生成条件として、「先頭からm−1個までのパターンが同一のアイテムであり、最後の1つのアイテムが異なっていること」が設定されている。ただし、この前提として、各パターンにおいては、アイテムは予め定められた順序に従って整列される必要がある。本例は、上述したように、「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の順で優先度が付けられているため、この優先度に従って各パターンが整列される。
【0047】
候補パターン生成部40は、ステップS44の候補パターン生成条件を満たすパターンを2個取り出し(ステップS45)、異なるアイテムを整列させて、ステップS41で設定されたパターン長mよりも1だけ長いパターンの候補(候補パターン)を生成する処理を行う(ステップS46)。
【0048】
すなわち、ステップS46で候補パターン生成部40は、取り出された2個のパターンに共通するm−1個のアイテムに対して、相互に異なる最後の2つのアイテムを、アイテムの順序を守るようにして並べた、(m−1+2=)m+1のパターンの長さを持つ候補パターンを1個生成する。続いて、候補パターン生成部40は、生成された候補パターンを候補頻度算出部50に提供する(ステップS47)。さらに、候補パターン生成部40は、長さm+1の候補パターンを全て生成するまでステップS45乃至ステップS48の処理を繰り返し、全て生成したと判定されるとステップS4の処理を終了する。すなわち、このようなパターンの抽出とパターンの候補の生成を繰り返し実施することにより、パターン格納部80に格納されている長さmの頻出アイテムまたはパターンから、m+1のパターンの長さを持つすべてのパターンの候補が生成される。
【0049】
以下、候補パターンの生成処理について具体例を挙げて詳述する。
【0050】
例えば、ステップS41でパターンの長さmが1に設定され、パターン格納部80には、図7に示す長さが1であるパターン(すなわち頻出アイテム)が格納されているものとする。ここで各アイテムは、上述のように「鶏肉」、「豚肉」、「牛肉」、「鮪」、「鯵」、「ビール」の順で優先度が与えられていることから、パターン格納部80に格納される頻出アイテムは、「牛肉」を除いて「鶏肉」、「豚肉」、「鮪」、「鯵」、「ビール」の順で並べられている。
【0051】
このとき、図7の各パターンは、いずれも長さmが1であることから、ステップS42を経てステップS43で全て取り出される。一方、ステップS44の候補パターン生成条件については、パターンの長さmが1の場合には、共通するアイテムの個数は1個もない(すなわち0個である)ため、「前からm−1個までのパターンが同一のアイテム」であること及び「最後の1つのアイテムが異なっている」こととなり、図7の任意の2個のパターンの組合せが条件を満たすことになる。このため、候補パターン生成部40は、上述したアイテムの優先度に従って、「鶏肉、豚肉」、「鶏肉、鮪」、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、鮪」、「豚肉、鯵」、「豚肉、ビール」、「鮪、鯵」、「鮪、ビール」、「鯵、ビール」の順で2個のパターンを取り出し(ステップS45)、長さが2となる10種類のパターンの候補(2次の候補パターン)をステップS46で生成する(図10参照)。当該生成された10個の候補パターンの情報は、候補頻度算出部50に提供され、各候補パターン毎に後述するステップS5乃至ステップS9の処理が繰り返し実行される。そして、かかる10個全ての候補パターンについての処理が終了すると、ステップS9からステップS5に処理が戻される。
【0052】
ステップS5では、候補頻度算出部50が、候補パターン生成部40から提供された候補パターンの中で頻度算出の処理が完了していないものがあるかについて判定し、未だ処理が完了していないものがある場合には1つの候補パターンを取り出してステップS6に進み、全ての候補パターンの頻度算出処理が完了している場合には、本装置の処理を候補パターン生成に関するステップS4へと戻す。
【0053】
以下のステップS6からステップS10までは、取り出された1つの候補パターンに対する処理である。まず、ステップS6では、候補頻度算出部50が、ステップS1で読み込まれているトランザクションの集合を参照することにより、取り出した1つのパターンの候補に対して、当該候補の出現頻度すなわち当該候補パターンを含むトランザクションの個数を算出する。
【0054】
例えば、図2に示すトランザクションの集合がステップS1で読み込まれ、ステップS4で設定されたパターンの長さmが2であり、ステップS6でパターンの候補として「鶏肉、豚肉」が取り出されている場合、当該パターンの候補はA02及びA03のトランザクションに含まれているため、その出現頻度として2が算出される(図10参照)。同様に、他の候補パターンである「鶏肉、鮪」、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、鮪」、「豚肉、鯵」、「豚肉、ビール」、「鮪、鯵」、「鮪、ビール」、「鯵、ビール」に関しては、それぞれの出現頻度が、3、2、3、1、0、2、2、2、1と算出される。
【0055】
ステップS7では、候補評価値算出部60が、ステップS6で算出された候補パターンの出現頻度と、ステップS2で読み込まれたアイテム間知識(関連度行列テーブル)を用いて、当該パターンを構成するアイテム間の関連性を評価することにより、その頻度が低い程小さく、関連性の高いアイテムによってパターンが構成されている程小さくなる抽出評価値(以下、「関連性支持度」と称する。)を算出する。
【0056】
詳細には、図9のフローチャートに示すように、候補評価値算出部60は、ステップ6で算出された出現頻度から当該候補パターンの支持度を算出する(ステップS71)。ここで、候補パターンの支持度の算出は、上述した数式1と同様であり、かかる数式の「アイテムを含むトランザクションの個数」を「パターンを含むトランザクションの個数」と読み替えればよい。ステップS72で、候補評価値算出部60は、当該候補パターンに含まれる2個のアイテムの組合せを全て抽出する。ステップS73で、候補評価値算出部60は、ステップS2でアイテム間情報記憶部20から読み込まれたアイテム間知識を参照(識別)して、抽出された組合せに対応する関連度を全て抽出する。続いて、候補評価値算出部60は、抽出された関連度に基づく加重値を算出し(ステップS74)、算出された加重値をステップS71で算出された支持度に適用することで、当該候補パターンの抽出評価値(関連性支持度f(p))を算出する(ステップS75)。
【0057】
ここで、上述した加重値および関連性支持度f(p)は、パターンの長さmの増大に対して、単調に減少するように定義する必要がある。より詳細には、関連性支持度f(p)は、2つのパターンあるいはパターンの候補p1及びp2に対して、p1⊆p2(p1はp2の部分集合)の関係が成立する場合、f(p1)≧f(p2)といった関係が成立するように定義する必要がある。言い換えると、候補評価値算出部60は、パターンの長さmに対してトレードオフの関係が成り立つように加重値を算出する必要がある。
【0058】
このような加重値および関連性支持度の定義や算出式には多様なものが考えられる。例えば、候補評価値算出部60が算出する加重値の定義として、抽出された関連度を所定値(例えば1)から減じて得られる値を加重値とすることができる。あるいは、候補評価値算出部60が算出する加重値の定義の例として、抽出された関連度と加重値との合計値を一定(例えば1)に保持したまま、当該合計値と抽出された関連度との差分値を、加重値とすることができる。
【0059】
本実施形態では、候補評価値算出部60が算出する加重値及び関連度支持度として、下記数式2に示すように関連性支持度f(p)を定義する。
【0060】
【数2】
【0061】
ただし、数式2の第1項において、s(iti,itj)は、アイテムitiとアイテムitjとの関連度を表す。また、max{s(iti,itj)}は、パターンを構成する全てのアイテム(iti,itj)間の関連度の内の最大値である。
【0062】
数式2において、加重値である第1項は、パターンを構成する任意のアイテム間の関連度の最大値(max)を用いており、かかる関連度の最大値を定数1から減算している。このため、加重値である第1項は、パターンの長さmが増大すると、アイテム間の関連度の最大値が単調に増加し、定数1からかかる最大値を減算することで、単調に減少する値が得られることになる。また、数式2の第2項は、分母(トランザクションの総数)の値が固定値である一方、分子の値がパターンの長さmの増大に伴って単調に減少する。このため、第1項に第2項を掛けて定数倍した関連性支持度f(p)は、パターンの長さmの増大に対して、単調に減少するといえる。
【0063】
例えば、パターンの長さmが2である「鶏肉、豚肉」の場合、「鶏肉」と「豚肉」の関連度は図3に示すように0.5と設定されている。このため、加重値である数式2の第1項の値は(1−0.5=)0.5が算出される。また、上述のように、「鶏肉、豚肉」の頻度は2と算出される。このため、「鶏肉、豚肉」の関連性支持度f(p)は、(0.5×2/5×100=)20%と算出される。一方、同じくパターンの長さmが2である「鶏肉、鮪」の場合、「鶏肉」と「鮪」の関連度は0と設定されているので、数式2の第1項の値は(1−0=)1が算出される。このため、ステップS7で、候補評価値算出部60は、「鶏肉、鮪」の関連性支持度f(p)として、(1×3/5×100=)60%を算出する(ステップS75)。同様に、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、鮪」、「豚肉、鯵」、「豚肉、ビール」、「鮪、鯵」、「鮪、ビール」、「鯵、ビール」の関連性支持度は、図10の関連性支持度の欄に示すように、各々、40%、60%、20%、0%、40%、20%、40%、20%が算出される。
【0064】
ステップS8では、候補評価部70が、データ格納部10に格納されている最小支持度の値と、算出された候補パターンの関連性支持度f(p)の値とを比較して、当該関連性支持度f(p)の値が閾値である最小支持度の値を満たすか否かを判定する。このとき、候補評価部70は、当該候補の関連性支持度f(p)が最小支持度(本例では40%)以上の場合に、当該候補パターンを「パターン」すなわちアイテムの特徴的な組合せを有するものとして登録するために、ステップS9に処理を移行する。一方、関連性支持度が最小支持度未満の場合には、当該候補をパターン格納部80に登録することなくステップS5に処理を戻し、次の候補パターンについての処理を行なう。
【0065】
ステップS9では、候補評価部70が登録すると判定したパターンの候補を、アイテムの特徴的な組合せを有するパターンとして、パターン格納部80に格納する。例えば、図10に示すように、パターンの長さが2となる候補パターンに対して関連性支持度が算出された場合、本例ではデータ格納部10に格納されている最小支持度が40%であるため、図10に示す10個の候補パターンの内、「鶏肉、鮪」、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、ビール」、「鮪、ビール」の候補パターンに対しては、ステップS8で基準値を満たすと判定され、当該5つのパターンが、パターンとして図11に示すようにパターン格納部80に登録される。一方、「鶏肉、豚肉」、「豚肉、鮪」、「豚肉、鯵」、「鮪、鯵」、「鯵、ビール」の候補パターンに対しては、ステップS8で基準値を満たさないと判定され、パターン格納部80に格納されず、当該候補パターンのデータが廃棄される。このため、「鶏肉、豚肉」、「豚肉、鮪」、「豚肉、鯵」、「鮪、鯵」、「鯵、ビール」の候補パターンは、長さ3の候補パターン生成の対象から除外される。
【0066】
そして、本例では、図10に示す10個の2次候補パターンの全てについてステップS6乃至ステップS9の処理が完了すると、ステップS5を経てステップS4に処理が戻され、長さ3の3次候補パターンの生成が開始される。
【0067】
すなわち、パターン格納部80には、図7に示す頻出アイテムの他に、図11に示すように、長さ2のパターン(2次のパターン)が、上述したアイテムの優先度に従って、「鶏肉、鮪」、「鶏肉、鯵」、「鶏肉、ビール」、「豚肉、ビール」、「鮪、ビール」の順序で格納されている。この状態から、ステップS41で、候補パターン生成部40は、パターンの長さmを2に設定する。
【0068】
続いて候補パターン生成部40は、ステップS42を経て、長さmが2である図11の各パターンを全て取り出し(ステップS43)、長さ2のパターンを2つ組合せるために、候補パターン生成条件の適否を判定する(ステップS44)。
【0069】
ステップS44の候補パターン生成条件について、長さmが2の場合には、共通するアイテムの個数が最大で1となるため、「鶏肉、鮪」と「鶏肉、鯵」は、「前方のm−1個のパターン」換言すると「最初のアイテム」である「鶏肉」が共通しており、かつ最後の1個のアイテムが相互に異なるため、候補パターン生成条件を満たしている。これに対して、「鶏肉、鮪」と「豚肉、ビール」は、「前方のm−1個のパターン」すなわち「最初のアイテム」が一致しておらず、このため候補パターン生成条件を満たしていない。
【0070】
候補パターン生成部40は、このようにしてステップS44で候補パターン生成条件の適否を判定し、「鶏肉、鮪」と「鶏肉、鯵」、「鶏肉、鮪」と「鶏肉、ビール」、「鶏肉、鯵」と「鶏肉、ビール」の3組を、候補パターン生成条件を満たすものと判定し、かかる3組をステップS45で取り出す。さらに、候補パターン生成部40は、ステップS46で、長さが3となる3次の候補パターンとして、それぞれ、「鶏肉、鮪」と「鶏肉、鯵」から「鶏肉、鮪、鯵」を生成し、「鶏肉、鮪」と「鶏肉、ビール」から「鶏肉、鮪、ビール」を生成し、「鶏肉、鯵」と「鶏肉、ビール」から「鶏肉、鯵、ビール」を生成する(図12参照)。当該生成された「鶏肉、鮪、鯵」、「鶏肉、鮪、ビール」、「鶏肉、鯵、ビール」の3個の候補パターンの情報は、候補頻度算出部50に提供され、各候補パターン毎に上述したステップS5乃至ステップS9の処理が繰り返し実行される。そして、これら3個全ての候補パターンについての処理が終了すると、ステップS9からステップS5に処理が戻される。
【0071】
詳細には、ステップS5で、候補頻度算出部50は、候補パターン生成部40から提供された候補パターンから未処理の1つの候補パターン「鶏肉、鮪、鯵」を取り出してステップS6の頻度算出処理を行う。この場合、「鶏肉、鮪、鯵」はトランザクションA01及びA05に含まれているため、候補頻度算出部50によって頻度「2」が算出され(ステップS6)、候補評価値算出部60によって支持度40(%)が算出される(ステップS71)。
【0072】
続いて、候補評価値算出部60は、候補パターン「鶏肉、鮪、鯵」から2個のアイテムの全ての組合わせとして、「鶏肉、鮪」、「鶏肉、鯵」、「鮪、鯵」を抽出し(ステップS72)、かかる組合わせに対応する関連度として、0、0、0.5を抽出し(ステップS73)、抽出された関連度から、上述した数式2の第1項の加重値として、(1−max{0, 0, 0.5})すなわち(1−0.5=)0.5を算出する(ステップS74)。また、「鶏肉、鮪、鯵」の支持度として「40」が算出されているので、候補評価値算出部60は、ステップS75で、「鶏肉、鯵、鮪」の関連性支持度f(p)として、(0.5×40=)20%を算出する(図12参照)。この場合、関連性支持度が最小支持度(40%)未満であり(ステップS8でNO)、パターンとして登録することなくステップS5に処理が戻される。
【0073】
続いて、ステップS5で、候補頻度算出部50は、候補パターン生成部40から提供された長さ3の候補パターンからの中で未処理の1つの候補パターン「鶏肉、鮪、ビール」を取り出してステップS6の頻度算出処理を行う。この場合、「鶏肉、鮪、ビール」はトランザクションA01及びA03に含まれているため、候補頻度算出部50によって頻度「2」が算出され(ステップS6)、候補評価値算出部60によって支持度40(%)が算出される(ステップS71)。
【0074】
続いて、候補評価値算出部60は、候補パターン「鶏肉、鮪、ビール」から2個のアイテムの全ての組合わせとして、「鶏肉、鮪」、「鶏肉、ビール」、「鮪、ビール」を抽出し(ステップS72)、かかる組合わせに対応する関連度として、0、0、0を抽出し(ステップS73)、抽出された関連度から、上述した数式2の第1項の加重値として、(1−max{0, 0, 0})すなわち(1−0=)1を算出する(ステップS74)。また、「鶏肉、鮪、ビール」の支持度として「40」が算出されているので、候補評価値算出部60は、ステップS75で、「鶏肉、鮪、ビール」の関連性支持度f(p)として、(1×40=)40%を算出する(図12参照)。この場合、関連性支持度が閾値の最小支持度(40%)以上であるため、「鶏肉、鮪、ビール」の候補パターンは、「パターン」すなわち「アイテムの特徴的な組合せを有するもの」として、ステップS9でパターン格納部80に格納される(図13参照)。
【0075】
さらに、ステップS5で、候補頻度算出部50は、候補パターン生成部40から提供された候補パターンからの中で未処理の1つの候補パターン「鶏肉、鯵、ビール」を取り出してステップS6の頻度算出処理を行う。この場合、「鶏肉、鯵、ビール」はトランザクションA01のみに含まれているため、候補頻度算出部50によって頻度「1」が算出され(ステップS6)、候補評価値算出部60によって支持度20(%)が算出される(ステップS71)。
【0076】
続いて、候補評価値算出部60は、候補パターン「鶏肉、鯵、ビール」から2個のアイテムの全ての組合わせとして、「鶏肉、鯵」、「鶏肉、ビール」、「鯵、ビール」を抽出し(ステップS72)、かかる組合わせに対応する関連度として、0、0、0を抽出し(ステップS73)、抽出された関連度から、上述した数式2の第1項の加重値として、(1−max{0, 0, 0})すなわち(1−0=)1を算出する(ステップS74)。また、「鶏肉、鯵、ビール」の支持度として「20」が算出されているので、候補評価値算出部60は、ステップS75で、「鶏肉、鯵、ビール」の関連性支持度f(p)として、(1×20=)20%を算出する(図12参照)。この場合、関連性支持度が最小支持度(40%)未満であり(ステップS8でNO)、パターンとして登録することなくステップS5に処理が戻される。
【0077】
そして、本例では、図12に示す3個の3次候補パターンの全てについてステップS6乃至ステップS9の処理が完了すると、ステップS5を経てステップS4に処理が戻される。この場合、パターンの長さmが3に設定されるが(ステップS41)、パターン格納部80には、図13に示すように長さmが3のパターンが1個しか格納されていないために、候補パターン生成条件を満たすパターンの組合せを取り出して長さ4の候補パターンを生成することができない(ステップS42でNO)。したがって、この場合は、候補パターン生成部40によるステップS45での候補パターンの生成が出来ないものとして、本装置における処理を終了する。
【0078】
以上のように、パターンの長さが3の場合においては、図13に示すように、3つの候補パターンの内の「鶏肉、鮪、ビール」のみがパターンとして抽出され、パターン格納部80に登録されることになる。すなわち、頻度が同じ「2」であっても関連度の高いアイテムが含まれている「鶏肉、鯵、鮪」については、加重値ひいては抽出評価値(関連性支持度)が相対的に低く算出され、抽出対象とならない。また、関連度の低いアイテムのみで構成された「鶏肉、鯵、ビール」についても、頻度が低いために関連性支持度が低く算出され、やはり抽出対象とならない。
【0079】
また、上述した例で示したように、長さ2の候補パターン「鶏肉、鯵」、「鶏肉、ビール」、「鯵、ビール」の関連性支持度f(p)は、それぞれ、40%、60%、20%となり(図10参照)、かかる3つの候補パターンを含む長さ3の候補パターン「鶏肉、鯵、ビール」の関連性支持度f(p)は20%となる(図12参照)。従って、数式2を用いた候補評価値算出部60の演算結果によれば、パターンの長さの増大に伴って、抽出評価値である関連性支持度が単調に減少することを確認することができる。
【0080】
上述のように、本実施形態のパターン抽出装置100は、候補パターンに対する抽出評価値を算出する際にアイテム間の関連性を考慮し、関連性が高いアイテムを含む候補パターンの加重値を相対的に小さい値となるように算出することにより、関連性が高いアイテムを含む候補パターンが相対的に抽出されにくくなり、分析者にとって自明と思われる、相互に関連性の高いアイテムで構成されたパターンが抽出されることを防止することができ、分析者の興味を惹くと考えられる、相互に関連性の低いアイテムで構成されたパターンを効率良く抽出することができる。
【0081】
より具体的には、アイテム間の関連性を考慮せずに、単に最小支持度に基づいてパターンを抽出した場合には、図2のトランザクションから、出現頻度が2である候補パターン、すなわち肉類同士である「鶏肉、豚肉」や魚類同士である「鯵、鮪」もパターンとして抽出されることになる。このような相互に関連性の高いアイテムで構成されたパターンは、分析者にとって、自明(当たり前)との印象が強いものであり、興味を惹くパターンとならない。これに対して、本実施形態のパターン抽出装置100の抽出制御では、候補パターン中、ある程度出現頻度があり且つ関連性の低いアイテムで構成されたものが抽出対象となるので、上述の「鶏肉、豚肉」や「鯵、鮪」がパターンとして抽出されることを回避することができる。
【0082】
さらに、本実施形態で説明した対象情報としてのトランザクションは、説明の簡明化のため、極めて小規模な構造のものを例示したが、実際には、より多くのアイテムの種類を扱うとともに、大量のトランザクションが対象とされ得る。このため、アイテム間の関連性を考慮せずに、単に最小支持度に基づいてパターンを抽出した場合には、相互に関連性の高いアイテムで構成されたパターンが多数抽出される可能性があり、「豚肉、鯵」といったようなカテゴリの異なる商品(アイテム)で構成されたパターンが、多くの同種の商品のパターンの中に埋もれてしまう虞がある。したがって、アイテム間の関連性を考慮せずに、最小支持度に基づいてパターンを抽出した場合には、分析者の興味を惹くパターンを効率的に発見することが著しく困難であると考えられる。
【0083】
これに対し、本実施形態のパターン抽出制御では、上述のように、アイテム間の関連性を考慮し、候補パターンに含まれる各アイテム間の関連度をアイテム間情報記憶部20から抽出し、抽出された関連度に基づいて加重値を算出し、かかる加重値を当該候補パターンのトランザクション中の出現頻度に基づく支持度に適用して抽出評価値を算出するために、関連性の高くないアイテムで構成されたパターンを効率良く抽出することが可能となる。従って、本実施形態のパターン抽出装置100によれば、分析者の興味を惹く重要なパターンを、効率的に発見することが可能になる。
【0084】
なお、パターン抽出装置の構成は、上述した実施形態に限定されるものではない。例えば、抽出評価値である関連性支持度の算出方法として、数式2を採用したが、単調性を満たすような関連性支持度の定義式としては、下記の数式3、数式4に示すように、その定義を与えることもできる。
【0085】
【数3】
【0086】
【数4】
【0087】
ここで、数式3を用いた場合には、加重値となる第1項でアイテム同士の関連度を加算し、該加算値が1以上になると、第1項ひいては当該関連性支持度f(p)の値が0になる。したがって、数式3も、パターンの長さ(アイテム構成数の増大)に対して単調に減少する定義であることがわかる。
【0088】
一方、数式4を用いた場合には、加重値となる第1項はアイテム同士の関連度のかけ算をするので、実施形態の関連度行列の値をそのまま使うと、例えば「鶏肉」と「ビール」の場合に第1項ひいては当該関連性支持度f(p)の値が0になる。したがって、この場合には、アイテム間知識の他の実施形態として、同じアイテム同士の関連度を0とし、関連性が最も低いアイテム同士の関連度を1に設定すればよい。
【0089】
また、上述した実施形態では、アイテム抽出部30によるステップS37の判定で、パターン格納部80に頻出アイテムが存在しない場合には本装置の処理を終了することとしたが、これに限定されず、ステップS37で頻出アイテムが存在しないと判定された場合に、アイテム抽出部30が最小支持度の値(上記例では40%)から所定の値(例えば20%)だけ減算する処理を行い、該減算後の最小支持度以上の支持度のアイテムを頻出アイテムとして抽出するように、頻出アイテム抽出(ステップS3)の処理を再度やり直すこととしてもよい。この場合には、最小支持度の値を減少させて算出した旨及び算出に用いた最小支持度の値を表示部に適宜表示して分析者に知らせるようにすることが好ましい。
【0090】
さらに、上述とは逆に、抽出されパターン格納部80に格納された頻出アイテムが非常に多い場合、例えば、抽出対象となった頻出アイテムが、予め設定された所定数以上の場合、或いはステップS31で抽出されたアイテムの内の予め設定された所定割合(%)以上のアイテムが頻出アイテムとして格納された場合に、アイテム抽出部30が最小支持度の値を所定の値(例えば20%)だけ増加させる処理を行って、該変更後の最小支持度以上の支持度のアイテムを頻出アイテムとして抽出するように、再度ステップS3の処理をやり直すこととしてもよい。この場合にも、最小支持度の値を増加させて算出した旨及び算出に用いた最小支持度の値を表示部に適宜表示して分析者に知らせるようにすることが好ましい。
【0091】
さらにまた、長さ2以上の候補パターンに関する最小支持値についても同様の処理を行うことができる。図14は、パターン抽出装置の他の実施形態の動作を説明するためのフローチャートであり、ステップS5で未処理の候補が無いと判定された場合に、ステップS51でパターン格納部80内のパターンの有無を判別し、パターンがある場合にはステップS4に戻り、一方、無い場合にはステップS52で最小支持度の値(上記例では40%)から所定の値(例えば20%)だけ減算する処理を行い、該変更後の最小支持度でステップS8の判定処理を候補パターン毎に再度行う。
【0092】
さらに、パターン格納部80に格納されたパターンの個数が、予め定められた数未満(過少)の場合、または、予め定められた数を超える(過大の)場合に、最小支持度の値を減少させる処理、または、最小支持度の値を増加させる処理を行って、ステップS8の判定処理を候補パターン毎に再度行うこととしてもよい。
【0093】
また、上述の実施形態ではアイテム間情報格納部20に記憶するアイテム間知識として、2つのアイテム間の関係に対して関連度を定義していたが、これに限定されず、アイテム間知識は、アイテムの増大に対して単調性を保持するように与えることにより、3つ以上のアイテムに対して関連度を定義することもできる。
【0094】
また、上述の実施形態では、日用品の販売における、購入商品の特徴的な組合せの発見のためにパターン抽出装置100を使用する場合について例示して説明したが、これに限定されず、他の多様な業務に使用することができる。例えば、銀行業務における、店舗の特性と事務ミスの種類との間にある特徴的な因果関係の発見に使用する場合の一例として、店舗毎に1個のトランザクションを使用し、当該店舗で発生したミスの種類をアイテムとして使用することができる。また、番組推薦における、視聴者特性と視聴履歴との間にある視聴者の嗜好の発見などの分野に利用する場合の一例として、視聴者毎に1個のトランザクションを使用し、当該視聴者が視聴した番組をアイテムとして使用することができる。
【0095】
上述した各処理は、コンピュータで実行可能なプログラムとして実現することが可能であり、当該プログラムがインストールされたコンピュータは、実施形態に係る各処理を遂行する情報処理装置として動作することが可能である。例えば、不図示の補助記憶装置に当該プログラムが格納され、CPU等の制御部が補助記憶装置に格納されたプログラムを主記憶装置に読み出し、主記憶装置に読み出された該プログラムを制御部が実行し、コンピュータに実施形態に係る各処理を動作させることができる。
【0096】
また、上記プログラムは、コンピュータ読取可能な記録媒体に記録された状態で、コンピュータに適用することも可能であり、インターネット等のネットワークを通じてコンピュータにダウンロードすることも可能である。コンピュータ読取可能な記録媒体としては、CD−ROM等の光ディスク、DVD−ROM等の相変化型光ディスク、MO(Magnet Optical)やMD(Mini Disk)などの光磁気ディスク、フロッピー(登録商標)ディスクやリムーバブルハードディスクなどの磁気ディスク、コンパクトフラッシュ(登録商標)、スマートメディア、SDメモリカード、メモリスティック等のメモリカードが挙げられる。また、特別に設計されて構成された集積回路(ICチップ等)等のハードウェア装置も記録媒体として含まれる。
【0097】
また、上述の実施形態では、図1に示した各部を1台のコンピュータで構成したが、これに限定されず、図1に示した各部を適宜異なるサーバ装置等で実現し、ネットワーク等の通信回線を介して接続したコンピュータシステムとして構成することもできる。
【0098】
なお、本発明の実施形態を説明したが、当該実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。この新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【0099】
100 パターン抽出装置
10 データ格納部
20 アイテム間情報記憶部
30 アイテム抽出部
40 候補パターン生成部
50 候補頻度算出部
60 候補評価値算出部
70 候補評価部
80 パターン格納部
【特許請求の範囲】
【請求項1】
複数のアイテムを含む対象情報内に存在する相互に異なる2以上のアイテムの組合せのパターンを抽出するパターン抽出装置であって、
複数の前記対象情報を記憶する第1記憶部と、
前記複数の対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成する候補パターン生成部と、
前記生成された候補パターンが前記複数の対象情報それぞれに出現する出現頻度に基づいて、前記候補パターンの抽出評価値を算出する候補評価値算出部と、
前記算出された抽出評価値が所定の閾値を満たす候補パターンを判別し、前記閾値を満たす候補パターンを抽出するパターン抽出部と、を含むとともに、
前記アイテム間の関連度を記憶する第2記憶部をさらに含み、
前記候補評価値算出部は、前記候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び前記出現頻度に基づいて、前記抽出評価値を算出することを特徴とするパターン抽出装置。
【請求項2】
前記候補評価値算出部は、任意のふたつの候補パターンp1、p2において、候補パターンp1が候補パターンp2の部分集合である場合に、候補パターンp2の抽出評価値が候補パターンp1の抽出評価値以下になるような単調性が成立する定義に基づいて、前記抽出評価値出を算出することを特徴とする請求項1記載のパターン抽出装置。
【請求項3】
前記候補評価値算出部は、前記候補パターンに含まれるアイテム間の関連度を前記第2記憶部から抽出し、前記抽出された関連度を所定値から減じて得られる値を前記加重値として算出することを特徴とする請求項1又は2に記載のパターン抽出装置。
【請求項4】
複数のアイテムを含む対象情報内に存在する相互に異なる2以上のアイテムの組合せのパターンを抽出するパターン抽出方法であって、
複数の前記対象情報を記憶領域に記憶するステップと、
前記複数の対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成するステップと、
前記アイテム間の関連度を記憶領域に記憶するステップと、
前記生成された候補パターンが前記複数の対象情報それぞれに出現する出現頻度に基づいて、前記候補パターンの抽出評価値を算出するステップと、
前記算出された抽出評価値が所定の閾値を満たす候補パターンを判別し、前記閾値を満たす候補パターンを抽出するステップと、
を含み、
前記候補パターンの抽出評価値を算出するステップは、前記候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び前記出現頻度に基づいて、前記抽出評価値を算出することを特徴とするパターン抽出方法。
【請求項5】
複数のアイテムを含む対象情報及び前記アイテム間の関連度を所定の記憶領域に記憶し、前記対象情報内に存在する相互に異なる2以上のアイテムの組合せのパターンを抽出するパターン抽出処理を遂行するコンピュータに、
複数の前記対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成する機能と、
前記生成された候補パターンが複数の前記対象情報それぞれに出現する出現頻度に基づいて、前記候補パターンの抽出評価値を算出する機能と、
前記算出された抽出評価値が所定の閾値を満たす候補パターンを判別し、前記閾値を満たす候補パターンを抽出する機能と、を実現させ、
前記候補パターンの抽出評価値を算出する機能は、前記候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び前記出現頻度に基づいて、前記抽出評価値を算出することを特徴とするプログラム。
【請求項1】
複数のアイテムを含む対象情報内に存在する相互に異なる2以上のアイテムの組合せのパターンを抽出するパターン抽出装置であって、
複数の前記対象情報を記憶する第1記憶部と、
前記複数の対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成する候補パターン生成部と、
前記生成された候補パターンが前記複数の対象情報それぞれに出現する出現頻度に基づいて、前記候補パターンの抽出評価値を算出する候補評価値算出部と、
前記算出された抽出評価値が所定の閾値を満たす候補パターンを判別し、前記閾値を満たす候補パターンを抽出するパターン抽出部と、を含むとともに、
前記アイテム間の関連度を記憶する第2記憶部をさらに含み、
前記候補評価値算出部は、前記候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び前記出現頻度に基づいて、前記抽出評価値を算出することを特徴とするパターン抽出装置。
【請求項2】
前記候補評価値算出部は、任意のふたつの候補パターンp1、p2において、候補パターンp1が候補パターンp2の部分集合である場合に、候補パターンp2の抽出評価値が候補パターンp1の抽出評価値以下になるような単調性が成立する定義に基づいて、前記抽出評価値出を算出することを特徴とする請求項1記載のパターン抽出装置。
【請求項3】
前記候補評価値算出部は、前記候補パターンに含まれるアイテム間の関連度を前記第2記憶部から抽出し、前記抽出された関連度を所定値から減じて得られる値を前記加重値として算出することを特徴とする請求項1又は2に記載のパターン抽出装置。
【請求項4】
複数のアイテムを含む対象情報内に存在する相互に異なる2以上のアイテムの組合せのパターンを抽出するパターン抽出方法であって、
複数の前記対象情報を記憶領域に記憶するステップと、
前記複数の対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成するステップと、
前記アイテム間の関連度を記憶領域に記憶するステップと、
前記生成された候補パターンが前記複数の対象情報それぞれに出現する出現頻度に基づいて、前記候補パターンの抽出評価値を算出するステップと、
前記算出された抽出評価値が所定の閾値を満たす候補パターンを判別し、前記閾値を満たす候補パターンを抽出するステップと、
を含み、
前記候補パターンの抽出評価値を算出するステップは、前記候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び前記出現頻度に基づいて、前記抽出評価値を算出することを特徴とするパターン抽出方法。
【請求項5】
複数のアイテムを含む対象情報及び前記アイテム間の関連度を所定の記憶領域に記憶し、前記対象情報内に存在する相互に異なる2以上のアイテムの組合せのパターンを抽出するパターン抽出処理を遂行するコンピュータに、
複数の前記対象情報それぞれに含まれる各アイテムに基づいて、相互に異なる2以上のアイテムで構成される候補パターンを生成する機能と、
前記生成された候補パターンが複数の前記対象情報それぞれに出現する出現頻度に基づいて、前記候補パターンの抽出評価値を算出する機能と、
前記算出された抽出評価値が所定の閾値を満たす候補パターンを判別し、前記閾値を満たす候補パターンを抽出する機能と、を実現させ、
前記候補パターンの抽出評価値を算出する機能は、前記候補パターンに含まれる各アイテム間の関連度を識別し、識別された関連度に基づく加重値及び前記出現頻度に基づいて、前記抽出評価値を算出することを特徴とするプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【公開番号】特開2012−256185(P2012−256185A)
【公開日】平成24年12月27日(2012.12.27)
【国際特許分類】
【出願番号】特願2011−128596(P2011−128596)
【出願日】平成23年6月8日(2011.6.8)
【出願人】(000003078)株式会社東芝 (54,554)
【出願人】(301063496)東芝ソリューション株式会社 (1,478)
【公開日】平成24年12月27日(2012.12.27)
【国際特許分類】
【出願日】平成23年6月8日(2011.6.8)
【出願人】(000003078)株式会社東芝 (54,554)
【出願人】(301063496)東芝ソリューション株式会社 (1,478)
[ Back to top ]